1//===- SCCPSolver.cpp - SCCP Utility --------------------------- *- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// \file
10// This file implements the Sparse Conditional Constant Propagation (SCCP)
11// utility.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Transforms/Utils/SCCPSolver.h"
16#include "llvm/ADT/SetVector.h"
17#include "llvm/Analysis/ConstantFolding.h"
18#include "llvm/Analysis/InstructionSimplify.h"
19#include "llvm/Analysis/Loads.h"
20#include "llvm/Analysis/ValueLattice.h"
21#include "llvm/Analysis/ValueLatticeUtils.h"
22#include "llvm/Analysis/ValueTracking.h"
23#include "llvm/IR/ConstantRange.h"
24#include "llvm/IR/DerivedTypes.h"
25#include "llvm/IR/IRBuilder.h"
26#include "llvm/IR/InstVisitor.h"
27#include "llvm/IR/Instructions.h"
28#include "llvm/IR/NoFolder.h"
29#include "llvm/IR/Operator.h"
30#include "llvm/IR/PatternMatch.h"
31#include "llvm/Support/Casting.h"
32#include "llvm/Support/Debug.h"
33#include "llvm/Support/ErrorHandling.h"
34#include "llvm/Support/raw_ostream.h"
35#include "llvm/Transforms/Utils/Local.h"
36#include <cassert>
37#include <utility>
38#include <vector>
39
40using namespace llvm;
41using namespace PatternMatch;
42
43#define DEBUG_TYPE "sccp"
44
45// The maximum number of range extensions allowed for operations requiring
46// widening.
47static const unsigned MaxNumRangeExtensions = 10;
48
49/// Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions.
50static ValueLatticeElement::MergeOptions getMaxWidenStepsOpts() {
51 return ValueLatticeElement::MergeOptions().setMaxWidenSteps(
52 MaxNumRangeExtensions);
53}
54
55namespace llvm {
56
57bool SCCPSolver::isConstant(const ValueLatticeElement &LV) {
58 return LV.isConstant() ||
59 (LV.isConstantRange() && LV.getConstantRange().isSingleElement());
60}
61
62bool SCCPSolver::isReplaceableConstant(const ValueLatticeElement &LV) {
63 return isConstant(LV) && !LV.mayHaveDifferentProvenance();
64}
65
66bool SCCPSolver::isOverdefined(const ValueLatticeElement &LV) {
67 return !LV.isUnknownOrUndef() && !SCCPSolver::isConstant(LV);
68}
69
70bool SCCPSolver::tryToReplaceWithConstant(Value *V) {
71 Constant *Const = getConstantOrNull(V);
72 if (!Const)
73 return false;
74 // Replacing `musttail` instructions with constant breaks `musttail` invariant
75 // unless the call itself can be removed.
76 // Calls with "clang.arc.attachedcall" implicitly use the return value and
77 // those uses cannot be updated with a constant.
78 CallBase *CB = dyn_cast<CallBase>(Val: V);
79 if (CB && ((CB->isMustTailCall() && !wouldInstructionBeTriviallyDead(I: CB)) ||
80 CB->getOperandBundle(ID: LLVMContext::OB_clang_arc_attachedcall))) {
81 Function *F = CB->getCalledFunction();
82
83 // Don't zap returns of the callee
84 if (F)
85 addToMustPreserveReturnsInFunctions(F);
86
87 LLVM_DEBUG(dbgs() << " Can\'t treat the result of call " << *CB
88 << " as a constant\n");
89 return false;
90 }
91
92 // For pointer constants derived from PredicateInfo, the constant may have
93 // different provenance. Take this into account during constant pointer
94 // propagation.
95 if (V->getType()->isPointerTy()) {
96 const auto &LV = getLatticeValueFor(V);
97 if (LV.mayHaveDifferentProvenance()) {
98 const DataLayout &DL = getDataLayout();
99 bool Changed = V->replaceUsesWithIf(New: Const, ShouldReplace: [&](Use &U) {
100 bool CanReplace = canReplacePointersInUseIfEqual(U, To: Const, DL);
101 if (CanReplace)
102 LLVM_DEBUG(dbgs() << " Constant pointer: " << *Const << " = " << *V
103 << '\n');
104 return CanReplace;
105 });
106 return Changed;
107 }
108 }
109
110 LLVM_DEBUG(dbgs() << " Constant: " << *Const << " = " << *V << '\n');
111
112 // Replaces all of the uses of a variable with uses of the constant.
113 V->replaceAllUsesWith(V: Const);
114 return true;
115}
116
117/// Helper for propagting !implicit.ref metadata from callee to caller before
118/// erasing a call instruction. This ensures that references to global objects
119/// (e.g., copyright strings) are preserved even when calls are optimized away.
120static void propagateImplicitRefFromCall(CallBase *CB) {
121 Function *Callee = CB->getCalledFunction();
122 if (!Callee)
123 return;
124
125 if (!Callee->hasMetadata(KindID: LLVMContext::MD_implicit_ref))
126 return;
127
128 Function *Caller = CB->getParent()->getParent();
129 if (!Caller)
130 return;
131
132 SmallVector<MDNode *> MDs;
133 Callee->getMetadata(KindID: LLVMContext::MD_implicit_ref, MDs);
134 for (MDNode *MD : MDs)
135 Caller->addMetadata(KindID: LLVMContext::MD_implicit_ref, MD&: *MD);
136}
137
138/// Helper for getting ranges from \p Solver. Instructions inserted during
139/// simplification are unavailable in the solver, so we return a full range for
140/// them.
141static ConstantRange getRange(Value *Op, SCCPSolver &Solver,
142 const SmallPtrSetImpl<Value *> &InsertedValues) {
143 if (auto *Const = dyn_cast<Constant>(Val: Op))
144 return Const->toConstantRange();
145 if (InsertedValues.contains(Ptr: Op)) {
146 unsigned Bitwidth = Op->getType()->getScalarSizeInBits();
147 return ConstantRange::getFull(BitWidth: Bitwidth);
148 }
149 return Solver.getLatticeValueFor(V: Op).asConstantRange(Ty: Op->getType(),
150 /*UndefAllowed=*/false);
151}
152
153/// Try to use \p Inst's value range from \p Solver to infer the NUW flag.
154static bool refineInstruction(SCCPSolver &Solver,
155 const SmallPtrSetImpl<Value *> &InsertedValues,
156 Instruction &Inst) {
157 bool Changed = false;
158 auto GetRange = [&Solver, &InsertedValues](Value *Op) {
159 return getRange(Op, Solver, InsertedValues);
160 };
161
162 if (isa<OverflowingBinaryOperator>(Val: Inst)) {
163 if (Inst.hasNoSignedWrap() && Inst.hasNoUnsignedWrap())
164 return false;
165
166 auto RangeA = GetRange(Inst.getOperand(i: 0));
167 auto RangeB = GetRange(Inst.getOperand(i: 1));
168 if (!Inst.hasNoUnsignedWrap()) {
169 auto NUWRange = ConstantRange::makeGuaranteedNoWrapRegion(
170 BinOp: Instruction::BinaryOps(Inst.getOpcode()), Other: RangeB,
171 NoWrapKind: OverflowingBinaryOperator::NoUnsignedWrap);
172 if (NUWRange.contains(CR: RangeA)) {
173 Inst.setHasNoUnsignedWrap();
174 Changed = true;
175 }
176 }
177 if (!Inst.hasNoSignedWrap()) {
178 auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(
179 BinOp: Instruction::BinaryOps(Inst.getOpcode()), Other: RangeB,
180 NoWrapKind: OverflowingBinaryOperator::NoSignedWrap);
181 if (NSWRange.contains(CR: RangeA)) {
182 Inst.setHasNoSignedWrap();
183 Changed = true;
184 }
185 }
186 } else if (isa<PossiblyNonNegInst>(Val: Inst) && !Inst.hasNonNeg()) {
187 auto Range = GetRange(Inst.getOperand(i: 0));
188 if (Range.isAllNonNegative()) {
189 Inst.setNonNeg();
190 Changed = true;
191 }
192 } else if (TruncInst *TI = dyn_cast<TruncInst>(Val: &Inst)) {
193 if (TI->hasNoSignedWrap() && TI->hasNoUnsignedWrap())
194 return false;
195
196 auto Range = GetRange(Inst.getOperand(i: 0));
197 uint64_t DestWidth = TI->getDestTy()->getScalarSizeInBits();
198 if (!TI->hasNoUnsignedWrap()) {
199 if (Range.getActiveBits() <= DestWidth) {
200 TI->setHasNoUnsignedWrap(true);
201 Changed = true;
202 }
203 }
204 if (!TI->hasNoSignedWrap()) {
205 if (Range.getMinSignedBits() <= DestWidth) {
206 TI->setHasNoSignedWrap(true);
207 Changed = true;
208 }
209 }
210 } else if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: &Inst)) {
211 if (GEP->hasNoUnsignedWrap() || !GEP->hasNoUnsignedSignedWrap())
212 return false;
213
214 if (all_of(Range: GEP->indices(),
215 P: [&](Value *V) { return GetRange(V).isAllNonNegative(); })) {
216 GEP->setNoWrapFlags(GEP->getNoWrapFlags() |
217 GEPNoWrapFlags::noUnsignedWrap());
218 Changed = true;
219 }
220 }
221
222 return Changed;
223}
224
225/// Try to replace signed instructions with their unsigned equivalent.
226static bool replaceSignedInst(SCCPSolver &Solver,
227 SmallPtrSetImpl<Value *> &InsertedValues,
228 Instruction &Inst) {
229 // Determine if a signed value is known to be >= 0.
230 auto isNonNegative = [&Solver, &InsertedValues](Value *V) {
231 return getRange(Op: V, Solver, InsertedValues).isAllNonNegative();
232 };
233
234 Instruction *NewInst = nullptr;
235 switch (Inst.getOpcode()) {
236 case Instruction::SIToFP:
237 case Instruction::SExt: {
238 // If the source value is not negative, this is a zext/uitofp.
239 Value *Op0 = Inst.getOperand(i: 0);
240 if (!isNonNegative(Op0))
241 return false;
242 NewInst = CastInst::Create(Inst.getOpcode() == Instruction::SExt
243 ? Instruction::ZExt
244 : Instruction::UIToFP,
245 S: Op0, Ty: Inst.getType(), Name: "", InsertBefore: Inst.getIterator());
246 NewInst->setNonNeg();
247 break;
248 }
249 case Instruction::AShr: {
250 // If the shifted value is not negative, this is a logical shift right.
251 Value *Op0 = Inst.getOperand(i: 0);
252 if (!isNonNegative(Op0))
253 return false;
254 NewInst = BinaryOperator::CreateLShr(V1: Op0, V2: Inst.getOperand(i: 1), Name: "", InsertBefore: Inst.getIterator());
255 NewInst->setIsExact(Inst.isExact());
256 break;
257 }
258 case Instruction::SDiv:
259 case Instruction::SRem: {
260 // If both operands are not negative, this is the same as udiv/urem.
261 Value *Op0 = Inst.getOperand(i: 0), *Op1 = Inst.getOperand(i: 1);
262 if (!isNonNegative(Op0) || !isNonNegative(Op1))
263 return false;
264 auto NewOpcode = Inst.getOpcode() == Instruction::SDiv ? Instruction::UDiv
265 : Instruction::URem;
266 NewInst = BinaryOperator::Create(Op: NewOpcode, S1: Op0, S2: Op1, Name: "", InsertBefore: Inst.getIterator());
267 if (Inst.getOpcode() == Instruction::SDiv)
268 NewInst->setIsExact(Inst.isExact());
269 break;
270 }
271 default:
272 return false;
273 }
274
275 // Wire up the new instruction and update state.
276 assert(NewInst && "Expected replacement instruction");
277 NewInst->takeName(V: &Inst);
278 InsertedValues.insert(Ptr: NewInst);
279 Inst.replaceAllUsesWith(V: NewInst);
280 NewInst->setDebugLoc(Inst.getDebugLoc());
281 Solver.removeLatticeValueFor(V: &Inst);
282 Inst.eraseFromParent();
283 return true;
284}
285
286/// Try to use \p Inst's value range from \p Solver to simplify it.
287static Value *simplifyInstruction(SCCPSolver &Solver,
288 SmallPtrSetImpl<Value *> &InsertedValues,
289 Instruction &Inst) {
290 auto GetRange = [&Solver, &InsertedValues](Value *Op) {
291 return getRange(Op, Solver, InsertedValues);
292 };
293
294 Value *X;
295 const APInt *RHSC;
296 // Remove masking operations.
297 if (match(V: &Inst, P: m_And(L: m_Value(V&: X), R: m_LowBitMask(V&: RHSC)))) {
298 ConstantRange LRange = GetRange(X);
299 if (LRange.getUnsignedMax().ule(RHS: *RHSC))
300 return X;
301 }
302
303 // Check if we can simplify [us]cmp(X, Y) to X - Y.
304 if (auto *Cmp = dyn_cast<CmpIntrinsic>(Val: &Inst)) {
305 Value *LHS = Cmp->getOperand(i_nocapture: 0);
306 Value *RHS = Cmp->getOperand(i_nocapture: 1);
307 unsigned BitWidth = LHS->getType()->getScalarSizeInBits();
308 // Bail out on 1-bit comparisons.
309 if (BitWidth == 1)
310 return nullptr;
311 ConstantRange LRange = GetRange(LHS);
312 if (LRange.isSizeLargerThan(MaxSize: 3))
313 return nullptr;
314 ConstantRange RRange = GetRange(RHS);
315 if (RRange.isSizeLargerThan(MaxSize: 3))
316 return nullptr;
317 ConstantRange RHSLower = RRange.sub(Other: APInt(BitWidth, 1));
318 ConstantRange RHSUpper = RRange.add(Other: APInt(BitWidth, 1));
319 ICmpInst::Predicate Pred =
320 Cmp->isSigned() ? CmpInst::ICMP_SLE : CmpInst::ICMP_ULE;
321 if (!RHSLower.icmp(Pred, Other: LRange) || !LRange.icmp(Pred, Other: RHSUpper))
322 return nullptr;
323
324 IRBuilder<NoFolder> Builder(&Inst);
325 Value *Sub = Builder.CreateSub(LHS, RHS, Name: Inst.getName(), /*HasNUW=*/false,
326 /*HasNSW=*/Cmp->isSigned());
327 InsertedValues.insert(Ptr: Sub);
328 if (Sub->getType() != Inst.getType()) {
329 Sub = Builder.CreateSExtOrTrunc(V: Sub, DestTy: Inst.getType());
330 InsertedValues.insert(Ptr: Sub);
331 }
332 return Sub;
333 }
334
335 // Relax range checks.
336 if (auto *ICmp = dyn_cast<ICmpInst>(Val: &Inst)) {
337 Value *X;
338 auto MatchTwoInstructionExactRangeCheck =
339 [&]() -> std::optional<ConstantRange> {
340 const APInt *RHSC;
341 if (!match(V: ICmp->getOperand(i_nocapture: 1), P: m_APInt(Res&: RHSC)))
342 return std::nullopt;
343
344 Value *LHS = ICmp->getOperand(i_nocapture: 0);
345 ICmpInst::Predicate Pred = ICmp->getPredicate();
346 const APInt *Offset;
347 if (match(V: LHS, P: m_OneUse(SubPattern: m_AddLike(L: m_Value(V&: X), R: m_APInt(Res&: Offset)))))
348 return ConstantRange::makeExactICmpRegion(Pred, Other: *RHSC).sub(Other: *Offset);
349 // Match icmp eq/ne X & NegPow2, C
350 if (ICmp->isEquality()) {
351 const APInt *Mask;
352 if (match(V: LHS, P: m_OneUse(SubPattern: m_And(L: m_Value(V&: X), R: m_NegatedPower2(V&: Mask)))) &&
353 RHSC->countr_zero() >= Mask->countr_zero()) {
354 ConstantRange CR(*RHSC, *RHSC - *Mask);
355 return Pred == ICmpInst::ICMP_EQ ? CR : CR.inverse();
356 }
357 }
358 return std::nullopt;
359 };
360
361 if (auto CR = MatchTwoInstructionExactRangeCheck()) {
362 ConstantRange LRange = GetRange(X);
363 // Early exit if we know nothing about X.
364 if (LRange.isFullSet())
365 return nullptr;
366 auto ConvertCRToICmp =
367 [&](const std::optional<ConstantRange> &NewCR) -> Value * {
368 ICmpInst::Predicate Pred;
369 APInt RHS;
370 // Check if we can represent NewCR as an icmp predicate.
371 if (NewCR && NewCR->getEquivalentICmp(Pred, RHS)) {
372 IRBuilder<NoFolder> Builder(&Inst);
373 Value *NewICmp =
374 Builder.CreateICmp(P: Pred, LHS: X, RHS: ConstantInt::get(Ty: X->getType(), V: RHS));
375 InsertedValues.insert(Ptr: NewICmp);
376 return NewICmp;
377 }
378 return nullptr;
379 };
380 // We are allowed to refine the comparison to either true or false for out
381 // of range inputs.
382 // Here we refine the comparison to false, and check if we can narrow the
383 // range check to a simpler test.
384 if (auto *V = ConvertCRToICmp(CR->exactIntersectWith(CR: LRange)))
385 return V;
386 // Here we refine the comparison to true, i.e. we relax the range check.
387 if (auto *V = ConvertCRToICmp(CR->exactUnionWith(CR: LRange.inverse())))
388 return V;
389 }
390 }
391
392 return nullptr;
393}
394
395bool SCCPSolver::simplifyInstsInBlock(BasicBlock &BB,
396 SmallPtrSetImpl<Value *> &InsertedValues,
397 Statistic &InstRemovedStat,
398 Statistic &InstReplacedStat) {
399 bool MadeChanges = false;
400 for (Instruction &Inst : make_early_inc_range(Range&: BB)) {
401 if (Inst.getType()->isVoidTy())
402 continue;
403 if (tryToReplaceWithConstant(V: &Inst)) {
404 if (isInstructionTriviallyDead(I: &Inst)) {
405 // Propagate !implicit.ref before erasing the call.
406 if (auto *CB = dyn_cast<CallBase>(Val: &Inst))
407 propagateImplicitRefFromCall(CB);
408
409 Inst.eraseFromParent();
410 ++InstRemovedStat;
411 }
412 MadeChanges = true;
413 } else if (replaceSignedInst(Solver&: *this, InsertedValues, Inst)) {
414 MadeChanges = true;
415 ++InstReplacedStat;
416 } else if (refineInstruction(Solver&: *this, InsertedValues, Inst)) {
417 MadeChanges = true;
418 } else if (auto *V = simplifyInstruction(Solver&: *this, InsertedValues, Inst)) {
419 Inst.replaceAllUsesWith(V);
420 Inst.eraseFromParent();
421 ++InstRemovedStat;
422 MadeChanges = true;
423 }
424 }
425 return MadeChanges;
426}
427
428bool SCCPSolver::removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU,
429 BasicBlock *&NewUnreachableBB) const {
430 SmallPtrSet<BasicBlock *, 8> FeasibleSuccessors;
431 bool HasNonFeasibleEdges = false;
432 for (BasicBlock *Succ : successors(BB)) {
433 if (isEdgeFeasible(From: BB, To: Succ))
434 FeasibleSuccessors.insert(Ptr: Succ);
435 else
436 HasNonFeasibleEdges = true;
437 }
438
439 // All edges feasible, nothing to do.
440 if (!HasNonFeasibleEdges)
441 return false;
442
443 // SCCP can only determine non-feasible edges for br, switch and indirectbr.
444 Instruction *TI = BB->getTerminator();
445 assert((isa<UncondBrInst, CondBrInst, SwitchInst, IndirectBrInst>(TI)) &&
446 "Terminator must be a br, switch or indirectbr");
447
448 if (FeasibleSuccessors.size() == 0) {
449 // Branch on undef/poison, replace with unreachable.
450 SmallPtrSet<BasicBlock *, 8> SeenSuccs;
451 SmallVector<DominatorTree::UpdateType, 8> Updates;
452 for (BasicBlock *Succ : successors(BB)) {
453 Succ->removePredecessor(Pred: BB);
454 if (SeenSuccs.insert(Ptr: Succ).second)
455 Updates.push_back(Elt: {DominatorTree::Delete, BB, Succ});
456 }
457 TI->eraseFromParent();
458 new UnreachableInst(BB->getContext(), BB);
459 DTU.applyUpdatesPermissive(Updates);
460 } else if (FeasibleSuccessors.size() == 1) {
461 // Replace with an unconditional branch to the only feasible successor.
462 BasicBlock *OnlyFeasibleSuccessor = *FeasibleSuccessors.begin();
463 SmallVector<DominatorTree::UpdateType, 8> Updates;
464 bool HaveSeenOnlyFeasibleSuccessor = false;
465 for (BasicBlock *Succ : successors(BB)) {
466 if (Succ == OnlyFeasibleSuccessor && !HaveSeenOnlyFeasibleSuccessor) {
467 // Don't remove the edge to the only feasible successor the first time
468 // we see it. We still do need to remove any multi-edges to it though.
469 HaveSeenOnlyFeasibleSuccessor = true;
470 continue;
471 }
472
473 Succ->removePredecessor(Pred: BB);
474 Updates.push_back(Elt: {DominatorTree::Delete, BB, Succ});
475 }
476
477 Instruction *BI = UncondBrInst::Create(Target: OnlyFeasibleSuccessor, InsertBefore: BB);
478 BI->setDebugLoc(TI->getDebugLoc());
479 TI->eraseFromParent();
480 DTU.applyUpdatesPermissive(Updates);
481 } else if (FeasibleSuccessors.size() > 1) {
482 SwitchInstProfUpdateWrapper SI(*cast<SwitchInst>(Val: TI));
483 SmallVector<DominatorTree::UpdateType, 8> Updates;
484
485 // If the default destination is unfeasible it will never be taken. Replace
486 // it with a new block with a single Unreachable instruction.
487 BasicBlock *DefaultDest = SI->getDefaultDest();
488 if (!FeasibleSuccessors.contains(Ptr: DefaultDest)) {
489 if (!NewUnreachableBB) {
490 NewUnreachableBB =
491 BasicBlock::Create(Context&: DefaultDest->getContext(), Name: "default.unreachable",
492 Parent: DefaultDest->getParent(), InsertBefore: DefaultDest);
493 auto *UI =
494 new UnreachableInst(DefaultDest->getContext(), NewUnreachableBB);
495 UI->setDebugLoc(DebugLoc::getTemporary());
496 }
497
498 DefaultDest->removePredecessor(Pred: BB);
499 SI->setDefaultDest(NewUnreachableBB);
500 Updates.push_back(Elt: {DominatorTree::Delete, BB, DefaultDest});
501 Updates.push_back(Elt: {DominatorTree::Insert, BB, NewUnreachableBB});
502 }
503
504 for (auto CI = SI->case_begin(); CI != SI->case_end();) {
505 if (FeasibleSuccessors.contains(Ptr: CI->getCaseSuccessor())) {
506 ++CI;
507 continue;
508 }
509
510 BasicBlock *Succ = CI->getCaseSuccessor();
511 Succ->removePredecessor(Pred: BB);
512 Updates.push_back(Elt: {DominatorTree::Delete, BB, Succ});
513 SI.removeCase(I: CI);
514 // Don't increment CI, as we removed a case.
515 }
516
517 DTU.applyUpdatesPermissive(Updates);
518 } else {
519 llvm_unreachable("Must have at least one feasible successor");
520 }
521 return true;
522}
523
524static void inferAttribute(Function *F, unsigned AttrIndex,
525 const ValueLatticeElement &Val) {
526 // If there is a known constant range for the value, add range attribute.
527 if (Val.isConstantRange() && !Val.getConstantRange().isSingleElement()) {
528 // Do not add range attribute if the value may include undef.
529 if (Val.isConstantRangeIncludingUndef())
530 return;
531
532 // Take the intersection of the existing attribute and the inferred range.
533 Attribute OldAttr = F->getAttributeAtIndex(i: AttrIndex, Kind: Attribute::Range);
534 ConstantRange CR = Val.getConstantRange();
535 if (OldAttr.isValid())
536 CR = CR.intersectWith(CR: OldAttr.getRange());
537 F->addAttributeAtIndex(
538 i: AttrIndex, Attr: Attribute::get(Context&: F->getContext(), Kind: Attribute::Range, CR));
539 return;
540 }
541 // Infer nonnull attribute.
542 if (Val.isNotConstant() && Val.getNotConstant()->getType()->isPointerTy() &&
543 Val.getNotConstant()->isNullValue() &&
544 !F->hasAttributeAtIndex(Idx: AttrIndex, Kind: Attribute::NonNull)) {
545 F->addAttributeAtIndex(i: AttrIndex,
546 Attr: Attribute::get(Context&: F->getContext(), Kind: Attribute::NonNull));
547 }
548}
549
550void SCCPSolver::inferReturnAttributes() const {
551 for (const auto &[F, ReturnValue] : getTrackedRetVals())
552 inferAttribute(F, AttrIndex: AttributeList::ReturnIndex, Val: ReturnValue);
553}
554
555void SCCPSolver::inferArgAttributes() const {
556 for (Function *F : getArgumentTrackedFunctions()) {
557 if (!isBlockExecutable(BB: &F->front()))
558 continue;
559 for (Argument &A : F->args())
560 if (!A.getType()->isStructTy())
561 inferAttribute(F, AttrIndex: AttributeList::FirstArgIndex + A.getArgNo(),
562 Val: getLatticeValueFor(V: &A));
563 }
564}
565
566/// Helper class for SCCPSolver. This implements the instruction visitor and
567/// holds all the state.
568class SCCPInstVisitor : public InstVisitor<SCCPInstVisitor> {
569 const DataLayout &DL;
570 std::function<const TargetLibraryInfo &(Function &)> GetTLI;
571 /// Basic blocks that are executable (but may not have been visited yet).
572 SmallPtrSet<BasicBlock *, 8> BBExecutable;
573 /// Basic blocks that are executable and have been visited at least once.
574 SmallPtrSet<BasicBlock *, 8> BBVisited;
575 DenseMap<Value *, ValueLatticeElement>
576 ValueState; // The state each value is in.
577
578 /// StructValueState - This maintains ValueState for values that have
579 /// StructType, for example for formal arguments, calls, insertelement, etc.
580 DenseMap<std::pair<Value *, unsigned>, ValueLatticeElement> StructValueState;
581
582 /// GlobalValue - If we are tracking any values for the contents of a global
583 /// variable, we keep a mapping from the constant accessor to the element of
584 /// the global, to the currently known value. If the value becomes
585 /// overdefined, it's entry is simply removed from this map.
586 DenseMap<GlobalVariable *, ValueLatticeElement> TrackedGlobals;
587
588 /// TrackedRetVals - If we are tracking arguments into and the return
589 /// value out of a function, it will have an entry in this map, indicating
590 /// what the known return value for the function is.
591 MapVector<Function *, ValueLatticeElement> TrackedRetVals;
592
593 /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions
594 /// that return multiple values.
595 MapVector<std::pair<Function *, unsigned>, ValueLatticeElement>
596 TrackedMultipleRetVals;
597
598 /// The set of values whose lattice has been invalidated.
599 /// Populated by resetLatticeValueFor(), cleared after resolving undefs.
600 DenseSet<Value *> Invalidated;
601
602 /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is
603 /// represented here for efficient lookup.
604 SmallPtrSet<Function *, 16> MRVFunctionsTracked;
605
606 /// A list of functions whose return cannot be modified.
607 SmallPtrSet<Function *, 16> MustPreserveReturnsInFunctions;
608
609 /// TrackingIncomingArguments - This is the set of functions for whose
610 /// arguments we make optimistic assumptions about and try to prove as
611 /// constants.
612 SmallPtrSet<Function *, 16> TrackingIncomingArguments;
613
614 /// Worklist of instructions to re-visit. This only includes instructions
615 /// in blocks that have already been visited at least once.
616 SmallSetVector<Instruction *, 16> InstWorkList;
617
618 /// Current instruction while visiting a block for the first time, used to
619 /// avoid unnecessary instruction worklist insertions. Null if an instruction
620 /// is visited outside a whole-block visitation.
621 Instruction *CurI = nullptr;
622
623 // The BasicBlock work list
624 SmallVector<BasicBlock *, 64> BBWorkList;
625
626 /// KnownFeasibleEdges - Entries in this set are edges which have already had
627 /// PHI nodes retriggered.
628 using Edge = std::pair<BasicBlock *, BasicBlock *>;
629 DenseSet<Edge> KnownFeasibleEdges;
630
631 DenseMap<Function *, std::unique_ptr<PredicateInfo>> FnPredicateInfo;
632
633 DenseMap<Value *, SmallSetVector<User *, 2>> AdditionalUsers;
634
635 LLVMContext &Ctx;
636
637 BumpPtrAllocator PredicateInfoAllocator;
638
639private:
640 ConstantInt *getConstantInt(const ValueLatticeElement &IV, Type *Ty) const {
641 return dyn_cast_or_null<ConstantInt>(Val: getConstant(LV: IV, Ty));
642 }
643
644 /// Push instruction \p I to the worklist.
645 void pushToWorkList(Instruction *I);
646
647 /// Push users of value \p V to the worklist.
648 void pushUsersToWorkList(Value *V);
649
650 /// Like pushUsersToWorkList(), but also prints a debug message with the
651 /// updated value.
652 void pushUsersToWorkListMsg(ValueLatticeElement &IV, Value *V);
653
654 // markConstant - Make a value be marked as "constant". If the value
655 // is not already a constant, add it to the instruction work list so that
656 // the users of the instruction are updated later.
657 bool markConstant(ValueLatticeElement &IV, Value *V, Constant *C,
658 bool MayIncludeUndef = false);
659
660 bool markConstant(Value *V, Constant *C) {
661 assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
662 return markConstant(IV&: ValueState[V], V, C);
663 }
664
665 bool markNotConstant(ValueLatticeElement &IV, Value *V, Constant *C);
666
667 bool markNotNull(ValueLatticeElement &IV, Value *V) {
668 return markNotConstant(IV, V, C: Constant::getNullValue(Ty: V->getType()));
669 }
670
671 /// markConstantRange - Mark the object as constant range with \p CR. If the
672 /// object is not a constant range with the range \p CR, add it to the
673 /// instruction work list so that the users of the instruction are updated
674 /// later.
675 bool markConstantRange(ValueLatticeElement &IV, Value *V,
676 const ConstantRange &CR);
677
678 // markOverdefined - Make a value be marked as "overdefined". If the
679 // value is not already overdefined, add it to the overdefined instruction
680 // work list so that the users of the instruction are updated later.
681 bool markOverdefined(ValueLatticeElement &IV, Value *V);
682
683 /// Merge \p MergeWithV into \p IV and push \p V to the worklist, if \p IV
684 /// changes.
685 bool mergeInValue(ValueLatticeElement &IV, Value *V,
686 const ValueLatticeElement &MergeWithV,
687 ValueLatticeElement::MergeOptions Opts = {
688 /*MayIncludeUndef=*/false, /*CheckWiden=*/false});
689
690 /// getValueState - Return the ValueLatticeElement object that corresponds to
691 /// the value. This function handles the case when the value hasn't been seen
692 /// yet by properly seeding constants etc.
693 ValueLatticeElement &getValueState(Value *V) {
694 assert(!V->getType()->isStructTy() && "Should use getStructValueState");
695
696 auto I = ValueState.try_emplace(Key: V);
697 ValueLatticeElement &LV = I.first->second;
698
699 if (!I.second)
700 return LV; // Common case, already in the map.
701
702 if (auto *C = dyn_cast<Constant>(Val: V))
703 LV.markConstant(V: C); // Constants are constant
704
705 // All others are unknown by default.
706 return LV;
707 }
708
709 /// getStructValueState - Return the ValueLatticeElement object that
710 /// corresponds to the value/field pair. This function handles the case when
711 /// the value hasn't been seen yet by properly seeding constants etc.
712 ValueLatticeElement &getStructValueState(Value *V, unsigned i) {
713 assert(V->getType()->isStructTy() && "Should use getValueState");
714 assert(i < cast<StructType>(V->getType())->getNumElements() &&
715 "Invalid element #");
716
717 auto I = StructValueState.insert(
718 KV: std::make_pair(x: std::make_pair(x&: V, y&: i), y: ValueLatticeElement()));
719 ValueLatticeElement &LV = I.first->second;
720
721 if (!I.second)
722 return LV; // Common case, already in the map.
723
724 if (auto *C = dyn_cast<Constant>(Val: V)) {
725 Constant *Elt = C->getAggregateElement(Elt: i);
726
727 if (!Elt)
728 LV.markOverdefined(); // Unknown sort of constant.
729 else
730 LV.markConstant(V: Elt); // Constants are constant.
731 }
732
733 // All others are underdefined by default.
734 return LV;
735 }
736
737 template <typename FnTy> void forEachLatticeElement(Value *V, FnTy Fn) {
738 if (auto *STy = dyn_cast<StructType>(Val: V->getType())) {
739 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
740 Fn([this, i](Value *Op) -> ValueLatticeElement & {
741 return getStructValueState(V: Op, i);
742 });
743 } else {
744 Fn([this](Value *Op) -> ValueLatticeElement & {
745 return getValueState(V: Op);
746 });
747 }
748 }
749
750 /// Traverse the use-def chain of \p Call, marking itself and its users as
751 /// "unknown" on the way.
752 void invalidate(CallBase *Call) {
753 SmallVector<Instruction *, 64> ToInvalidate;
754 ToInvalidate.push_back(Elt: Call);
755
756 while (!ToInvalidate.empty()) {
757 Instruction *Inst = ToInvalidate.pop_back_val();
758
759 if (!Invalidated.insert(V: Inst).second)
760 continue;
761
762 if (!BBExecutable.count(Ptr: Inst->getParent()))
763 continue;
764
765 Value *V = nullptr;
766 // For return instructions we need to invalidate the tracked returns map.
767 // Anything else has its lattice in the value map.
768 if (auto *RetInst = dyn_cast<ReturnInst>(Val: Inst)) {
769 Function *F = RetInst->getParent()->getParent();
770 bool Reset = false;
771 if (auto It = TrackedRetVals.find(Key: F); It != TrackedRetVals.end()) {
772 It->second = ValueLatticeElement();
773 Reset = true;
774 } else if (MRVFunctionsTracked.count(Ptr: F)) {
775 auto *STy = cast<StructType>(Val: F->getReturnType());
776 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I)
777 TrackedMultipleRetVals[{F, I}] = ValueLatticeElement();
778 Reset = true;
779 }
780 if (Reset) {
781 LLVM_DEBUG(dbgs() << "Invalidated lattice for function "
782 << F->getName() << "\n");
783
784 for (User *U : F->users())
785 if (auto *CB = dyn_cast<CallBase>(Val: U))
786 if (CB->getCalledFunction() == F)
787 ToInvalidate.push_back(Elt: CB);
788 }
789 } else if (auto *STy = dyn_cast<StructType>(Val: Inst->getType())) {
790 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {
791 if (auto It = StructValueState.find(Val: {Inst, I});
792 It != StructValueState.end()) {
793 It->second = ValueLatticeElement();
794 V = Inst;
795 }
796 }
797 } else if (auto It = ValueState.find(Val: Inst); It != ValueState.end()) {
798 It->second = ValueLatticeElement();
799 V = Inst;
800 }
801
802 if (V) {
803 LLVM_DEBUG(dbgs() << "Invalidated lattice for " << *V << "\n");
804
805 for (User *U : V->users())
806 if (auto *UI = dyn_cast<Instruction>(Val: U))
807 ToInvalidate.push_back(Elt: UI);
808
809 auto It = AdditionalUsers.find(Val: V);
810 if (It != AdditionalUsers.end())
811 for (User *U : It->second)
812 if (auto *UI = dyn_cast<Instruction>(Val: U))
813 ToInvalidate.push_back(Elt: UI);
814 }
815 }
816 }
817
818 /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
819 /// work list if it is not already executable.
820 bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
821
822 // getFeasibleSuccessors - Return a vector of booleans to indicate which
823 // successors are reachable from a given terminator instruction.
824 void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl<bool> &Succs);
825
826 // Add U as additional user of V.
827 void addAdditionalUser(Value *V, User *U) { AdditionalUsers[V].insert(X: U); }
828
829 void handlePredicate(Instruction *I, Value *CopyOf, const PredicateBase *PI);
830 void handleCallOverdefined(CallBase &CB);
831 void handleCallResult(CallBase &CB);
832 void handleCallArguments(CallBase &CB);
833 void handleExtractOfWithOverflow(ExtractValueInst &EVI,
834 const WithOverflowInst *WO, unsigned Idx);
835 bool isInstFullyOverDefined(Instruction &Inst);
836
837private:
838 friend class InstVisitor<SCCPInstVisitor>;
839
840 // visit implementations - Something changed in this instruction. Either an
841 // operand made a transition, or the instruction is newly executable. Change
842 // the value type of I to reflect these changes if appropriate.
843 void visitPHINode(PHINode &I);
844
845 // Terminators
846
847 void visitReturnInst(ReturnInst &I);
848 void visitTerminator(Instruction &TI);
849
850 void visitCastInst(CastInst &I);
851 void visitSelectInst(SelectInst &I);
852 void visitUnaryOperator(Instruction &I);
853 void visitFreezeInst(FreezeInst &I);
854 void visitBinaryOperator(Instruction &I);
855 void visitCmpInst(CmpInst &I);
856 void visitExtractValueInst(ExtractValueInst &EVI);
857 void visitInsertValueInst(InsertValueInst &IVI);
858
859 void visitCatchSwitchInst(CatchSwitchInst &CPI) {
860 markOverdefined(V: &CPI);
861 visitTerminator(TI&: CPI);
862 }
863
864 // Instructions that cannot be folded away.
865
866 void visitStoreInst(StoreInst &I);
867 void visitLoadInst(LoadInst &I);
868 void visitGetElementPtrInst(GetElementPtrInst &I);
869 void visitAllocaInst(AllocaInst &AI);
870
871 void visitInvokeInst(InvokeInst &II) {
872 visitCallBase(CB&: II);
873 visitTerminator(TI&: II);
874 }
875
876 void visitCallBrInst(CallBrInst &CBI) {
877 visitCallBase(CB&: CBI);
878 visitTerminator(TI&: CBI);
879 }
880
881 void visitCallBase(CallBase &CB);
882 void visitResumeInst(ResumeInst &I) { /*returns void*/
883 }
884 void visitUnreachableInst(UnreachableInst &I) { /*returns void*/
885 }
886 void visitFenceInst(FenceInst &I) { /*returns void*/
887 }
888
889 void visitInstruction(Instruction &I);
890
891public:
892 const DataLayout &getDataLayout() const { return DL; }
893
894 void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC) {
895 FnPredicateInfo.insert(KV: {&F, std::make_unique<PredicateInfo>(
896 args&: F, args&: DT, args&: AC, args&: PredicateInfoAllocator)});
897 }
898
899 void removeSSACopies(Function &F) {
900 auto It = FnPredicateInfo.find(Val: &F);
901 if (It == FnPredicateInfo.end())
902 return;
903
904 for (BasicBlock &BB : F) {
905 for (Instruction &Inst : llvm::make_early_inc_range(Range&: BB)) {
906 if (auto *BC = dyn_cast<BitCastInst>(Val: &Inst)) {
907 if (BC->getType() == BC->getOperand(i_nocapture: 0)->getType()) {
908 if (It->second->getPredicateInfoFor(V: &Inst)) {
909 Value *Op = BC->getOperand(i_nocapture: 0);
910 Inst.replaceAllUsesWith(V: Op);
911 Inst.eraseFromParent();
912 }
913 }
914 }
915 }
916 }
917 }
918
919 void visitCallInst(CallInst &I) { visitCallBase(CB&: I); }
920
921 bool markBlockExecutable(BasicBlock *BB);
922
923 const PredicateBase *getPredicateInfoFor(Instruction *I) {
924 auto It = FnPredicateInfo.find(Val: I->getParent()->getParent());
925 if (It == FnPredicateInfo.end())
926 return nullptr;
927 return It->second->getPredicateInfoFor(V: I);
928 }
929
930 SCCPInstVisitor(const DataLayout &DL,
931 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
932 LLVMContext &Ctx)
933 : DL(DL), GetTLI(GetTLI), Ctx(Ctx) {}
934
935 void trackValueOfGlobalVariable(GlobalVariable *GV) {
936 // We only track the contents of scalar globals.
937 if (GV->getValueType()->isSingleValueType()) {
938 ValueLatticeElement &IV = TrackedGlobals[GV];
939 IV.markConstant(V: GV->getInitializer());
940 }
941 }
942
943 void addTrackedFunction(Function *F) {
944 // Add an entry, F -> undef.
945 if (auto *STy = dyn_cast<StructType>(Val: F->getReturnType())) {
946 MRVFunctionsTracked.insert(Ptr: F);
947 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
948 TrackedMultipleRetVals.try_emplace(Key: std::make_pair(x&: F, y&: i));
949 } else if (!F->getReturnType()->isVoidTy())
950 TrackedRetVals.try_emplace(Key: F);
951 }
952
953 void addToMustPreserveReturnsInFunctions(Function *F) {
954 MustPreserveReturnsInFunctions.insert(Ptr: F);
955 }
956
957 bool mustPreserveReturn(Function *F) {
958 return MustPreserveReturnsInFunctions.count(Ptr: F);
959 }
960
961 void addArgumentTrackedFunction(Function *F) {
962 TrackingIncomingArguments.insert(Ptr: F);
963 }
964
965 bool isArgumentTrackedFunction(Function *F) {
966 return TrackingIncomingArguments.count(Ptr: F);
967 }
968
969 const SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions() const {
970 return TrackingIncomingArguments;
971 }
972
973 void solve();
974
975 bool resolvedUndef(Instruction &I);
976
977 bool resolvedUndefsIn(Function &F);
978
979 bool isBlockExecutable(BasicBlock *BB) const {
980 return BBExecutable.count(Ptr: BB);
981 }
982
983 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
984
985 std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const {
986 std::vector<ValueLatticeElement> StructValues;
987 auto *STy = dyn_cast<StructType>(Val: V->getType());
988 assert(STy && "getStructLatticeValueFor() can be called only on structs");
989 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
990 auto I = StructValueState.find(Val: std::make_pair(x&: V, y&: i));
991 assert(I != StructValueState.end() && "Value not in valuemap!");
992 StructValues.push_back(x: I->second);
993 }
994 return StructValues;
995 }
996
997 void removeLatticeValueFor(Value *V) { ValueState.erase(Val: V); }
998
999 /// Invalidate the Lattice Value of \p Call and its users after specializing
1000 /// the call. Then recompute it.
1001 void resetLatticeValueFor(CallBase *Call) {
1002 // Calls to void returning functions do not need invalidation.
1003 Function *F = Call->getCalledFunction();
1004 (void)F;
1005 assert(!F->getReturnType()->isVoidTy() &&
1006 (TrackedRetVals.count(F) || MRVFunctionsTracked.count(F)) &&
1007 "All non void specializations should be tracked");
1008 invalidate(Call);
1009 handleCallResult(CB&: *Call);
1010 }
1011
1012 const ValueLatticeElement &getLatticeValueFor(Value *V) const {
1013 assert(!V->getType()->isStructTy() &&
1014 "Should use getStructLatticeValueFor");
1015 auto I = ValueState.find(Val: V);
1016 assert(I != ValueState.end() &&
1017 "V not found in ValueState nor Paramstate map!");
1018 return I->second;
1019 }
1020
1021 const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals() const {
1022 return TrackedRetVals;
1023 }
1024
1025 const DenseMap<GlobalVariable *, ValueLatticeElement> &
1026 getTrackedGlobals() const {
1027 return TrackedGlobals;
1028 }
1029
1030 const SmallPtrSet<Function *, 16> &getMRVFunctionsTracked() const {
1031 return MRVFunctionsTracked;
1032 }
1033
1034 void markOverdefined(Value *V) {
1035 if (auto *STy = dyn_cast<StructType>(Val: V->getType()))
1036 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1037 markOverdefined(IV&: getStructValueState(V, i), V);
1038 else
1039 markOverdefined(IV&: ValueState[V], V);
1040 }
1041
1042 ValueLatticeElement getArgAttributeVL(Argument *A) {
1043 if (A->getType()->isIntOrIntVectorTy()) {
1044 if (std::optional<ConstantRange> Range = A->getRange())
1045 return ValueLatticeElement::getRange(CR: *Range);
1046 }
1047 if (A->hasNonNullAttr())
1048 return ValueLatticeElement::getNot(C: Constant::getNullValue(Ty: A->getType()));
1049 // Assume nothing about the incoming arguments without attributes.
1050 return ValueLatticeElement::getOverdefined();
1051 }
1052
1053 void trackValueOfArgument(Argument *A) {
1054 if (A->getType()->isStructTy())
1055 return (void)markOverdefined(V: A);
1056 mergeInValue(IV&: ValueState[A], V: A, MergeWithV: getArgAttributeVL(A));
1057 }
1058
1059 bool isStructLatticeConstant(Function *F, StructType *STy);
1060
1061 Constant *getConstant(const ValueLatticeElement &LV, Type *Ty) const;
1062
1063 Constant *getConstantOrNull(Value *V) const;
1064
1065 void setLatticeValueForSpecializationArguments(Function *F,
1066 const SmallVectorImpl<ArgInfo> &Args);
1067
1068 void markFunctionUnreachable(Function *F) {
1069 for (auto &BB : *F)
1070 BBExecutable.erase(Ptr: &BB);
1071 }
1072
1073 void solveWhileResolvedUndefsIn(Module &M) {
1074 bool ResolvedUndefs = true;
1075 while (ResolvedUndefs) {
1076 solve();
1077 ResolvedUndefs = false;
1078 for (Function &F : M)
1079 ResolvedUndefs |= resolvedUndefsIn(F);
1080 }
1081 }
1082
1083 void solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList) {
1084 bool ResolvedUndefs = true;
1085 while (ResolvedUndefs) {
1086 solve();
1087 ResolvedUndefs = false;
1088 for (Function *F : WorkList)
1089 ResolvedUndefs |= resolvedUndefsIn(F&: *F);
1090 }
1091 }
1092
1093 void solveWhileResolvedUndefs() {
1094 bool ResolvedUndefs = true;
1095 while (ResolvedUndefs) {
1096 solve();
1097 ResolvedUndefs = false;
1098 for (Value *V : Invalidated)
1099 if (auto *I = dyn_cast<Instruction>(Val: V))
1100 ResolvedUndefs |= resolvedUndef(I&: *I);
1101 }
1102 Invalidated.clear();
1103 }
1104};
1105
1106} // namespace llvm
1107
1108bool SCCPInstVisitor::markBlockExecutable(BasicBlock *BB) {
1109 if (!BBExecutable.insert(Ptr: BB).second)
1110 return false;
1111 LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n');
1112 BBWorkList.push_back(Elt: BB); // Add the block to the work list!
1113 return true;
1114}
1115
1116void SCCPInstVisitor::pushToWorkList(Instruction *I) {
1117 // If we're currently visiting a block, do not push any instructions in the
1118 // same blocks that are after the current one, as they will be visited
1119 // anyway. We do have to push updates to earlier instructions (e.g. phi
1120 // nodes or loads of tracked globals).
1121 if (CurI && I->getParent() == CurI->getParent() && CurI->comesBefore(Other: I))
1122 return;
1123 // Only push instructions in already visited blocks. Otherwise we'll handle
1124 // it when we visit the block for the first time.
1125 if (BBVisited.contains(Ptr: I->getParent()))
1126 InstWorkList.insert(X: I);
1127}
1128
1129void SCCPInstVisitor::pushUsersToWorkList(Value *V) {
1130 for (User *U : V->users())
1131 if (auto *UI = dyn_cast<Instruction>(Val: U))
1132 pushToWorkList(I: UI);
1133
1134 auto Iter = AdditionalUsers.find(Val: V);
1135 if (Iter != AdditionalUsers.end()) {
1136 // Copy additional users before notifying them of changes, because new
1137 // users may be added, potentially invalidating the iterator.
1138 SmallVector<Instruction *, 2> ToNotify;
1139 for (User *U : Iter->second)
1140 if (auto *UI = dyn_cast<Instruction>(Val: U))
1141 ToNotify.push_back(Elt: UI);
1142 for (Instruction *UI : ToNotify)
1143 pushToWorkList(I: UI);
1144 }
1145}
1146
1147void SCCPInstVisitor::pushUsersToWorkListMsg(ValueLatticeElement &IV,
1148 Value *V) {
1149 LLVM_DEBUG(dbgs() << "updated " << IV << ": " << *V << '\n');
1150 pushUsersToWorkList(V);
1151}
1152
1153bool SCCPInstVisitor::markConstant(ValueLatticeElement &IV, Value *V,
1154 Constant *C, bool MayIncludeUndef) {
1155 if (!IV.markConstant(V: C, MayIncludeUndef))
1156 return false;
1157 LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');
1158 pushUsersToWorkList(V);
1159 return true;
1160}
1161
1162bool SCCPInstVisitor::markNotConstant(ValueLatticeElement &IV, Value *V,
1163 Constant *C) {
1164 if (!IV.markNotConstant(V: C))
1165 return false;
1166 LLVM_DEBUG(dbgs() << "markNotConstant: " << *C << ": " << *V << '\n');
1167 pushUsersToWorkList(V);
1168 return true;
1169}
1170
1171bool SCCPInstVisitor::markConstantRange(ValueLatticeElement &IV, Value *V,
1172 const ConstantRange &CR) {
1173 if (!IV.markConstantRange(NewR: CR))
1174 return false;
1175 LLVM_DEBUG(dbgs() << "markConstantRange: " << CR << ": " << *V << '\n');
1176 pushUsersToWorkList(V);
1177 return true;
1178}
1179
1180bool SCCPInstVisitor::markOverdefined(ValueLatticeElement &IV, Value *V) {
1181 if (!IV.markOverdefined())
1182 return false;
1183
1184 LLVM_DEBUG(dbgs() << "markOverdefined: ";
1185 if (auto *F = dyn_cast<Function>(V)) dbgs()
1186 << "Function '" << F->getName() << "'\n";
1187 else dbgs() << *V << '\n');
1188 // Only instructions go on the work list
1189 pushUsersToWorkList(V);
1190 return true;
1191}
1192
1193bool SCCPInstVisitor::isStructLatticeConstant(Function *F, StructType *STy) {
1194 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1195 const auto &It = TrackedMultipleRetVals.find(Key: std::make_pair(x&: F, y&: i));
1196 assert(It != TrackedMultipleRetVals.end());
1197 if (!SCCPSolver::isReplaceableConstant(LV: It->second))
1198 return false;
1199 }
1200 return true;
1201}
1202
1203Constant *SCCPInstVisitor::getConstant(const ValueLatticeElement &LV,
1204 Type *Ty) const {
1205 if (LV.isConstant()) {
1206 Constant *C = LV.getConstant();
1207 assert(C->getType() == Ty && "Type mismatch");
1208 return C;
1209 }
1210
1211 if (LV.isConstantRange()) {
1212 const auto &CR = LV.getConstantRange();
1213 if (CR.getSingleElement())
1214 return ConstantInt::get(Ty, V: *CR.getSingleElement());
1215 }
1216 return nullptr;
1217}
1218
1219Constant *SCCPInstVisitor::getConstantOrNull(Value *V) const {
1220 Constant *Const = nullptr;
1221 if (V->getType()->isStructTy()) {
1222 std::vector<ValueLatticeElement> LVs = getStructLatticeValueFor(V);
1223 if (any_of(Range&: LVs, P: SCCPSolver::isOverdefined))
1224 return nullptr;
1225 std::vector<Constant *> ConstVals;
1226 auto *ST = cast<StructType>(Val: V->getType());
1227 for (unsigned I = 0, E = ST->getNumElements(); I != E; ++I) {
1228 const ValueLatticeElement &LV = LVs[I];
1229 ConstVals.push_back(x: SCCPSolver::isConstant(LV)
1230 ? getConstant(LV, Ty: ST->getElementType(N: I))
1231 : UndefValue::get(T: ST->getElementType(N: I)));
1232 }
1233 Const = ConstantStruct::get(T: ST, V: ConstVals);
1234 } else {
1235 const ValueLatticeElement &LV = getLatticeValueFor(V);
1236 if (SCCPSolver::isOverdefined(LV))
1237 return nullptr;
1238 Const = SCCPSolver::isConstant(LV) ? getConstant(LV, Ty: V->getType())
1239 : UndefValue::get(T: V->getType());
1240 }
1241 assert(Const && "Constant is nullptr here!");
1242 return Const;
1243}
1244
1245void SCCPInstVisitor::setLatticeValueForSpecializationArguments(Function *F,
1246 const SmallVectorImpl<ArgInfo> &Args) {
1247 assert(!Args.empty() && "Specialization without arguments");
1248 assert(F->arg_size() == Args[0].Formal->getParent()->arg_size() &&
1249 "Functions should have the same number of arguments");
1250
1251 auto Iter = Args.begin();
1252 Function::arg_iterator NewArg = F->arg_begin();
1253 Function::arg_iterator OldArg = Args[0].Formal->getParent()->arg_begin();
1254 for (auto End = F->arg_end(); NewArg != End; ++NewArg, ++OldArg) {
1255
1256 LLVM_DEBUG(dbgs() << "SCCP: Marking argument "
1257 << NewArg->getNameOrAsOperand() << "\n");
1258
1259 // Mark the argument constants in the new function
1260 // or copy the lattice state over from the old function.
1261 if (Iter != Args.end() && Iter->Formal == &*OldArg) {
1262 if (auto *STy = dyn_cast<StructType>(Val: NewArg->getType())) {
1263 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {
1264 ValueLatticeElement &NewValue = StructValueState[{&*NewArg, I}];
1265 NewValue.markConstant(V: Iter->Actual->getAggregateElement(Elt: I));
1266 }
1267 } else {
1268 ValueState[&*NewArg].markConstant(V: Iter->Actual);
1269 }
1270 ++Iter;
1271 } else {
1272 if (auto *STy = dyn_cast<StructType>(Val: NewArg->getType())) {
1273 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {
1274 ValueLatticeElement &NewValue = StructValueState[{&*NewArg, I}];
1275 NewValue = StructValueState[{&*OldArg, I}];
1276 }
1277 } else {
1278 ValueLatticeElement &NewValue = ValueState[&*NewArg];
1279 NewValue = ValueState[&*OldArg];
1280 }
1281 }
1282 }
1283}
1284
1285void SCCPInstVisitor::visitInstruction(Instruction &I) {
1286 // All the instructions we don't do any special handling for just
1287 // go to overdefined.
1288 LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n');
1289 markOverdefined(V: &I);
1290}
1291
1292bool SCCPInstVisitor::mergeInValue(ValueLatticeElement &IV, Value *V,
1293 const ValueLatticeElement &MergeWithV,
1294 ValueLatticeElement::MergeOptions Opts) {
1295 if (IV.mergeIn(RHS: MergeWithV, Opts)) {
1296 pushUsersToWorkList(V);
1297 LLVM_DEBUG(dbgs() << "Merged " << MergeWithV << " into " << *V << " : "
1298 << IV << "\n");
1299 return true;
1300 }
1301 return false;
1302}
1303
1304bool SCCPInstVisitor::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
1305 if (!KnownFeasibleEdges.insert(V: Edge(Source, Dest)).second)
1306 return false; // This edge is already known to be executable!
1307
1308 if (!markBlockExecutable(BB: Dest)) {
1309 // If the destination is already executable, we just made an *edge*
1310 // feasible that wasn't before. Revisit the PHI nodes in the block
1311 // because they have potentially new operands.
1312 LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
1313 << " -> " << Dest->getName() << '\n');
1314
1315 for (PHINode &PN : Dest->phis())
1316 pushToWorkList(I: &PN);
1317 }
1318 return true;
1319}
1320
1321// getFeasibleSuccessors - Return a vector of booleans to indicate which
1322// successors are reachable from a given terminator instruction.
1323void SCCPInstVisitor::getFeasibleSuccessors(Instruction &TI,
1324 SmallVectorImpl<bool> &Succs) {
1325 Succs.resize(N: TI.getNumSuccessors());
1326 if (isa<UncondBrInst>(Val: TI)) {
1327 Succs[0] = true;
1328 return;
1329 }
1330
1331 if (auto *BI = dyn_cast<CondBrInst>(Val: &TI)) {
1332 const ValueLatticeElement &BCValue = getValueState(V: BI->getCondition());
1333 ConstantInt *CI = getConstantInt(IV: BCValue, Ty: BI->getCondition()->getType());
1334 if (!CI) {
1335 // Overdefined condition variables, and branches on unfoldable constant
1336 // conditions, mean the branch could go either way.
1337 if (!BCValue.isUnknownOrUndef())
1338 Succs[0] = Succs[1] = true;
1339 return;
1340 }
1341
1342 // Constant condition variables mean the branch can only go a single way.
1343 Succs[CI->isZero()] = true;
1344 return;
1345 }
1346
1347 // We cannot analyze special terminators, so consider all successors
1348 // executable.
1349 if (TI.isSpecialTerminator()) {
1350 Succs.assign(NumElts: TI.getNumSuccessors(), Elt: true);
1351 return;
1352 }
1353
1354 if (auto *SI = dyn_cast<SwitchInst>(Val: &TI)) {
1355 if (!SI->getNumCases()) {
1356 Succs[0] = true;
1357 return;
1358 }
1359 const ValueLatticeElement &SCValue = getValueState(V: SI->getCondition());
1360 if (ConstantInt *CI =
1361 getConstantInt(IV: SCValue, Ty: SI->getCondition()->getType())) {
1362 Succs[SI->findCaseValue(C: CI)->getSuccessorIndex()] = true;
1363 return;
1364 }
1365
1366 // TODO: Switch on undef is UB. Stop passing false once the rest of LLVM
1367 // is ready.
1368 if (SCValue.isConstantRange(/*UndefAllowed=*/false)) {
1369 const ConstantRange &Range = SCValue.getConstantRange();
1370 unsigned ReachableCaseCount = 0;
1371 for (const auto &Case : SI->cases()) {
1372 const APInt &CaseValue = Case.getCaseValue()->getValue();
1373 if (Range.contains(Val: CaseValue)) {
1374 Succs[Case.getSuccessorIndex()] = true;
1375 ++ReachableCaseCount;
1376 }
1377 }
1378
1379 Succs[SI->case_default()->getSuccessorIndex()] =
1380 Range.isSizeLargerThan(MaxSize: ReachableCaseCount);
1381 return;
1382 }
1383
1384 // Overdefined or unknown condition? All destinations are executable!
1385 if (!SCValue.isUnknownOrUndef())
1386 Succs.assign(NumElts: TI.getNumSuccessors(), Elt: true);
1387 return;
1388 }
1389
1390 // In case of indirect branch and its address is a blockaddress, we mark
1391 // the target as executable.
1392 if (auto *IBR = dyn_cast<IndirectBrInst>(Val: &TI)) {
1393 // Casts are folded by visitCastInst.
1394 const ValueLatticeElement &IBRValue = getValueState(V: IBR->getAddress());
1395 BlockAddress *Addr = dyn_cast_or_null<BlockAddress>(
1396 Val: getConstant(LV: IBRValue, Ty: IBR->getAddress()->getType()));
1397 if (!Addr) { // Overdefined or unknown condition?
1398 // All destinations are executable!
1399 if (!IBRValue.isUnknownOrUndef())
1400 Succs.assign(NumElts: TI.getNumSuccessors(), Elt: true);
1401 return;
1402 }
1403
1404 BasicBlock *T = Addr->getBasicBlock();
1405 assert(Addr->getFunction() == T->getParent() &&
1406 "Block address of a different function ?");
1407 for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {
1408 // This is the target.
1409 if (IBR->getDestination(i) == T) {
1410 Succs[i] = true;
1411 return;
1412 }
1413 }
1414
1415 // If we didn't find our destination in the IBR successor list, then we
1416 // have undefined behavior. Its ok to assume no successor is executable.
1417 return;
1418 }
1419
1420 LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n');
1421 llvm_unreachable("SCCP: Don't know how to handle this terminator!");
1422}
1423
1424// isEdgeFeasible - Return true if the control flow edge from the 'From' basic
1425// block to the 'To' basic block is currently feasible.
1426bool SCCPInstVisitor::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const {
1427 // Check if we've called markEdgeExecutable on the edge yet. (We could
1428 // be more aggressive and try to consider edges which haven't been marked
1429 // yet, but there isn't any need.)
1430 return KnownFeasibleEdges.count(V: Edge(From, To));
1431}
1432
1433// visit Implementations - Something changed in this instruction, either an
1434// operand made a transition, or the instruction is newly executable. Change
1435// the value type of I to reflect these changes if appropriate. This method
1436// makes sure to do the following actions:
1437//
1438// 1. If a phi node merges two constants in, and has conflicting value coming
1439// from different branches, or if the PHI node merges in an overdefined
1440// value, then the PHI node becomes overdefined.
1441// 2. If a phi node merges only constants in, and they all agree on value, the
1442// PHI node becomes a constant value equal to that.
1443// 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
1444// 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
1445// 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
1446// 6. If a conditional branch has a value that is constant, make the selected
1447// destination executable
1448// 7. If a conditional branch has a value that is overdefined, make all
1449// successors executable.
1450void SCCPInstVisitor::visitPHINode(PHINode &PN) {
1451 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
1452 // and slow us down a lot. Just mark them overdefined.
1453 if (PN.getNumIncomingValues() > 64)
1454 return (void)markOverdefined(V: &PN);
1455
1456 if (isInstFullyOverDefined(Inst&: PN))
1457 return;
1458 SmallVector<unsigned> FeasibleIncomingIndices;
1459 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1460 if (!isEdgeFeasible(From: PN.getIncomingBlock(i), To: PN.getParent()))
1461 continue;
1462 FeasibleIncomingIndices.push_back(Elt: i);
1463 }
1464
1465 // Look at all of the executable operands of the PHI node. If any of them
1466 // are overdefined, the PHI becomes overdefined as well. If they are all
1467 // constant, and they agree with each other, the PHI becomes the identical
1468 // constant. If they are constant and don't agree, the PHI is a constant
1469 // range. If there are no executable operands, the PHI remains unknown.
1470 forEachLatticeElement(V: &PN, Fn: [&](auto GetValueState) {
1471 ValueLatticeElement PhiState = GetValueState(&PN);
1472 if (PhiState.isOverdefined())
1473 return;
1474 for (unsigned i : FeasibleIncomingIndices) {
1475 PhiState.mergeIn(RHS: GetValueState(PN.getIncomingValue(i)));
1476 if (PhiState.isOverdefined())
1477 break;
1478 }
1479 // We allow up to 1 range extension per active incoming value and one
1480 // additional extension. Note that we manually adjust the number of range
1481 // extensions to match the number of active incoming values. This helps to
1482 // limit multiple extensions caused by the same incoming value, if other
1483 // incoming values are equal.
1484 ValueLatticeElement &PhiStateRef = GetValueState(&PN);
1485 mergeInValue(IV&: PhiStateRef, V: &PN, MergeWithV: PhiState,
1486 Opts: ValueLatticeElement::MergeOptions().setMaxWidenSteps(
1487 FeasibleIncomingIndices.size() + 1));
1488 PhiStateRef.setNumRangeExtensions(
1489 std::max(a: (unsigned)FeasibleIncomingIndices.size(),
1490 b: PhiStateRef.getNumRangeExtensions()));
1491 });
1492}
1493
1494void SCCPInstVisitor::visitReturnInst(ReturnInst &I) {
1495 if (I.getNumOperands() == 0)
1496 return; // ret void
1497
1498 Function *F = I.getParent()->getParent();
1499 Value *ResultOp = I.getOperand(i_nocapture: 0);
1500
1501 // If we are tracking the return value of this function, merge it in.
1502 if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) {
1503 auto TFRVI = TrackedRetVals.find(Key: F);
1504 if (TFRVI != TrackedRetVals.end()) {
1505 mergeInValue(IV&: TFRVI->second, V: F, MergeWithV: getValueState(V: ResultOp));
1506 return;
1507 }
1508 }
1509
1510 // Handle functions that return multiple values.
1511 if (!TrackedMultipleRetVals.empty()) {
1512 if (auto *STy = dyn_cast<StructType>(Val: ResultOp->getType()))
1513 if (MRVFunctionsTracked.count(Ptr: F))
1514 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1515 mergeInValue(IV&: TrackedMultipleRetVals[std::make_pair(x&: F, y&: i)], V: F,
1516 MergeWithV: getStructValueState(V: ResultOp, i));
1517 }
1518}
1519
1520void SCCPInstVisitor::visitTerminator(Instruction &TI) {
1521 SmallVector<bool, 16> SuccFeasible;
1522 getFeasibleSuccessors(TI, Succs&: SuccFeasible);
1523
1524 BasicBlock *BB = TI.getParent();
1525
1526 // Mark all feasible successors executable.
1527 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
1528 if (SuccFeasible[i])
1529 markEdgeExecutable(Source: BB, Dest: TI.getSuccessor(Idx: i));
1530}
1531
1532void SCCPInstVisitor::visitCastInst(CastInst &I) {
1533 // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1534 // discover a concrete value later.
1535 if (ValueState[&I].isOverdefined())
1536 return;
1537
1538 if (auto *BC = dyn_cast<BitCastInst>(Val: &I)) {
1539 if (BC->getType() == BC->getOperand(i_nocapture: 0)->getType()) {
1540 if (const PredicateBase *PI = getPredicateInfoFor(I: &I)) {
1541 handlePredicate(I: &I, CopyOf: I.getOperand(i_nocapture: 0), PI);
1542 return;
1543 }
1544 }
1545 }
1546
1547 const ValueLatticeElement &OpSt = getValueState(V: I.getOperand(i_nocapture: 0));
1548 if (OpSt.isUnknownOrUndef())
1549 return;
1550
1551 if (Constant *OpC = getConstant(LV: OpSt, Ty: I.getOperand(i_nocapture: 0)->getType())) {
1552 // Fold the constant as we build.
1553 if (Constant *C =
1554 ConstantFoldCastOperand(Opcode: I.getOpcode(), C: OpC, DestTy: I.getType(), DL)) {
1555 auto &LV = ValueState[&I];
1556 mergeInValue(IV&: LV, V: &I, MergeWithV: ValueLatticeElement::get(C));
1557 return;
1558 }
1559 }
1560
1561 // Ignore bitcasts, as they may change the number of vector elements.
1562 if (I.getDestTy()->isIntOrIntVectorTy() &&
1563 I.getSrcTy()->isIntOrIntVectorTy() &&
1564 I.getOpcode() != Instruction::BitCast) {
1565 ConstantRange OpRange =
1566 OpSt.asConstantRange(Ty: I.getSrcTy(), /*UndefAllowed=*/false);
1567 auto &LV = getValueState(V: &I);
1568
1569 Type *DestTy = I.getDestTy();
1570 ConstantRange Res = ConstantRange::getEmpty(BitWidth: DestTy->getScalarSizeInBits());
1571 if (auto *Trunc = dyn_cast<TruncInst>(Val: &I))
1572 Res = OpRange.truncate(BitWidth: DestTy->getScalarSizeInBits(),
1573 NoWrapKind: Trunc->getNoWrapKind());
1574 else
1575 Res = OpRange.castOp(CastOp: I.getOpcode(), BitWidth: DestTy->getScalarSizeInBits());
1576 mergeInValue(IV&: LV, V: &I, MergeWithV: ValueLatticeElement::getRange(CR: Res));
1577 } else
1578 markOverdefined(V: &I);
1579}
1580
1581void SCCPInstVisitor::handleExtractOfWithOverflow(ExtractValueInst &EVI,
1582 const WithOverflowInst *WO,
1583 unsigned Idx) {
1584 Value *LHS = WO->getLHS(), *RHS = WO->getRHS();
1585 Type *Ty = LHS->getType();
1586
1587 addAdditionalUser(V: LHS, U: &EVI);
1588 addAdditionalUser(V: RHS, U: &EVI);
1589
1590 const ValueLatticeElement &L = getValueState(V: LHS);
1591 if (L.isUnknownOrUndef())
1592 return; // Wait to resolve.
1593 ConstantRange LR = L.asConstantRange(Ty, /*UndefAllowed=*/false);
1594
1595 const ValueLatticeElement &R = getValueState(V: RHS);
1596 if (R.isUnknownOrUndef())
1597 return; // Wait to resolve.
1598
1599 ConstantRange RR = R.asConstantRange(Ty, /*UndefAllowed=*/false);
1600 if (Idx == 0) {
1601 ConstantRange Res = LR.binaryOp(BinOp: WO->getBinaryOp(), Other: RR);
1602 mergeInValue(IV&: ValueState[&EVI], V: &EVI, MergeWithV: ValueLatticeElement::getRange(CR: Res));
1603 } else {
1604 assert(Idx == 1 && "Index can only be 0 or 1");
1605 ConstantRange NWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1606 BinOp: WO->getBinaryOp(), Other: RR, NoWrapKind: WO->getNoWrapKind());
1607 if (NWRegion.contains(CR: LR))
1608 return (void)markConstant(V: &EVI, C: ConstantInt::getFalse(Ty: EVI.getType()));
1609 markOverdefined(V: &EVI);
1610 }
1611}
1612
1613void SCCPInstVisitor::visitExtractValueInst(ExtractValueInst &EVI) {
1614 // If this returns a struct, mark all elements over defined, we don't track
1615 // structs in structs.
1616 if (EVI.getType()->isStructTy())
1617 return (void)markOverdefined(V: &EVI);
1618
1619 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1620 // discover a concrete value later.
1621 if (ValueState[&EVI].isOverdefined())
1622 return (void)markOverdefined(V: &EVI);
1623
1624 // If this is extracting from more than one level of struct, we don't know.
1625 if (EVI.getNumIndices() != 1)
1626 return (void)markOverdefined(V: &EVI);
1627
1628 Value *AggVal = EVI.getAggregateOperand();
1629 if (AggVal->getType()->isStructTy()) {
1630 unsigned i = *EVI.idx_begin();
1631 if (auto *WO = dyn_cast<WithOverflowInst>(Val: AggVal))
1632 return handleExtractOfWithOverflow(EVI, WO, Idx: i);
1633 ValueLatticeElement EltVal = getStructValueState(V: AggVal, i);
1634 mergeInValue(IV&: ValueState[&EVI], V: &EVI, MergeWithV: EltVal);
1635 } else {
1636 // Otherwise, must be extracting from an array.
1637 return (void)markOverdefined(V: &EVI);
1638 }
1639}
1640
1641void SCCPInstVisitor::visitInsertValueInst(InsertValueInst &IVI) {
1642 auto *STy = dyn_cast<StructType>(Val: IVI.getType());
1643 if (!STy)
1644 return (void)markOverdefined(V: &IVI);
1645
1646 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1647 // discover a concrete value later.
1648 if (ValueState[&IVI].isOverdefined())
1649 return (void)markOverdefined(V: &IVI);
1650
1651 // If this has more than one index, we can't handle it, drive all results to
1652 // undef.
1653 if (IVI.getNumIndices() != 1)
1654 return (void)markOverdefined(V: &IVI);
1655
1656 Value *Aggr = IVI.getAggregateOperand();
1657 unsigned Idx = *IVI.idx_begin();
1658
1659 // Compute the result based on what we're inserting.
1660 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1661 // This passes through all values that aren't the inserted element.
1662 if (i != Idx) {
1663 ValueLatticeElement EltVal = getStructValueState(V: Aggr, i);
1664 mergeInValue(IV&: getStructValueState(V: &IVI, i), V: &IVI, MergeWithV: EltVal);
1665 continue;
1666 }
1667
1668 Value *Val = IVI.getInsertedValueOperand();
1669 if (Val->getType()->isStructTy())
1670 // We don't track structs in structs.
1671 markOverdefined(IV&: getStructValueState(V: &IVI, i), V: &IVI);
1672 else {
1673 ValueLatticeElement InVal = getValueState(V: Val);
1674 mergeInValue(IV&: getStructValueState(V: &IVI, i), V: &IVI, MergeWithV: InVal);
1675 }
1676 }
1677}
1678
1679void SCCPInstVisitor::visitSelectInst(SelectInst &I) {
1680 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1681 // discover a concrete value later.
1682 if (isInstFullyOverDefined(Inst&: I))
1683 return (void)markOverdefined(V: &I);
1684
1685 const ValueLatticeElement &CondValue = getValueState(V: I.getCondition());
1686 if (CondValue.isUnknownOrUndef())
1687 return;
1688
1689 if (ConstantInt *CondCB =
1690 getConstantInt(IV: CondValue, Ty: I.getCondition()->getType())) {
1691 Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue();
1692 forEachLatticeElement(V: &I, Fn: [&](auto GetValueState) {
1693 ValueLatticeElement OpValState = GetValueState(OpVal);
1694 mergeInValue(IV&: GetValueState(&I), V: &I, MergeWithV: OpValState);
1695 });
1696 return;
1697 }
1698
1699 // Otherwise, the condition is overdefined or a constant we can't evaluate.
1700 // See if we can produce something better than overdefined based on the T/F
1701 // value.
1702 forEachLatticeElement(V: &I, Fn: [&](auto GetValueState) {
1703 ValueLatticeElement TVal = GetValueState(I.getTrueValue());
1704 ValueLatticeElement FVal = GetValueState(I.getFalseValue());
1705
1706 ValueLatticeElement &State = GetValueState(&I);
1707 bool Changed = State.mergeIn(RHS: TVal);
1708 Changed |= State.mergeIn(RHS: FVal);
1709 if (Changed)
1710 pushUsersToWorkListMsg(IV&: State, V: &I);
1711 });
1712}
1713
1714// Handle Unary Operators.
1715void SCCPInstVisitor::visitUnaryOperator(Instruction &I) {
1716 ValueLatticeElement V0State = getValueState(V: I.getOperand(i: 0));
1717
1718 ValueLatticeElement &IV = ValueState[&I];
1719 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1720 // discover a concrete value later.
1721 if (IV.isOverdefined())
1722 return (void)markOverdefined(V: &I);
1723
1724 // If something is unknown/undef, wait for it to resolve.
1725 if (V0State.isUnknownOrUndef())
1726 return;
1727
1728 if (SCCPSolver::isConstant(LV: V0State))
1729 if (Constant *C = ConstantFoldUnaryOpOperand(
1730 Opcode: I.getOpcode(), Op: getConstant(LV: V0State, Ty: I.getType()), DL))
1731 return (void)markConstant(IV, V: &I, C);
1732
1733 markOverdefined(V: &I);
1734}
1735
1736void SCCPInstVisitor::visitFreezeInst(FreezeInst &I) {
1737 // If this freeze returns a struct, just mark the result overdefined.
1738 // TODO: We could do a lot better than this.
1739 if (I.getType()->isStructTy())
1740 return (void)markOverdefined(V: &I);
1741
1742 ValueLatticeElement V0State = getValueState(V: I.getOperand(i_nocapture: 0));
1743 ValueLatticeElement &IV = ValueState[&I];
1744 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1745 // discover a concrete value later.
1746 if (IV.isOverdefined())
1747 return (void)markOverdefined(V: &I);
1748
1749 // If something is unknown/undef, wait for it to resolve.
1750 if (V0State.isUnknownOrUndef())
1751 return;
1752
1753 if (SCCPSolver::isConstant(LV: V0State) &&
1754 isGuaranteedNotToBeUndefOrPoison(V: getConstant(LV: V0State, Ty: I.getType())))
1755 return (void)markConstant(IV, V: &I, C: getConstant(LV: V0State, Ty: I.getType()));
1756
1757 markOverdefined(V: &I);
1758}
1759
1760// Handle Binary Operators.
1761void SCCPInstVisitor::visitBinaryOperator(Instruction &I) {
1762 ValueLatticeElement V1State = getValueState(V: I.getOperand(i: 0));
1763 ValueLatticeElement V2State = getValueState(V: I.getOperand(i: 1));
1764
1765 ValueLatticeElement &IV = ValueState[&I];
1766 if (IV.isOverdefined())
1767 return;
1768
1769 // If something is undef, wait for it to resolve.
1770 if (V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef())
1771 return;
1772
1773 if (V1State.isOverdefined() && V2State.isOverdefined())
1774 return (void)markOverdefined(V: &I);
1775
1776 // If either of the operands is a constant, try to fold it to a constant.
1777 // TODO: Use information from notconstant better.
1778 if ((V1State.isConstant() || V2State.isConstant())) {
1779 Value *V1 = SCCPSolver::isConstant(LV: V1State)
1780 ? getConstant(LV: V1State, Ty: I.getOperand(i: 0)->getType())
1781 : I.getOperand(i: 0);
1782 Value *V2 = SCCPSolver::isConstant(LV: V2State)
1783 ? getConstant(LV: V2State, Ty: I.getOperand(i: 1)->getType())
1784 : I.getOperand(i: 1);
1785 Value *R;
1786 if (auto *FPOp = dyn_cast<FPMathOperator>(Val: &I))
1787 R = simplifyBinOp(Opcode: I.getOpcode(), LHS: V1, RHS: V2, FMF: FPOp->getFastMathFlags(),
1788 Q: SimplifyQuery(DL, &I));
1789 else
1790 R = simplifyBinOp(Opcode: I.getOpcode(), LHS: V1, RHS: V2, Q: SimplifyQuery(DL, &I));
1791 auto *C = dyn_cast_or_null<Constant>(Val: R);
1792 if (C) {
1793 // Conservatively assume that the result may be based on operands that may
1794 // be undef. Note that we use mergeInValue to combine the constant with
1795 // the existing lattice value for I, as different constants might be found
1796 // after one of the operands go to overdefined, e.g. due to one operand
1797 // being a special floating value.
1798 ValueLatticeElement NewV;
1799 NewV.markConstant(V: C, /*MayIncludeUndef=*/true);
1800 return (void)mergeInValue(IV&: ValueState[&I], V: &I, MergeWithV: NewV);
1801 }
1802 }
1803
1804 // Only use ranges for binary operators on integers.
1805 if (!I.getType()->isIntOrIntVectorTy())
1806 return markOverdefined(V: &I);
1807
1808 // Try to simplify to a constant range.
1809 ConstantRange A =
1810 V1State.asConstantRange(Ty: I.getType(), /*UndefAllowed=*/false);
1811 ConstantRange B =
1812 V2State.asConstantRange(Ty: I.getType(), /*UndefAllowed=*/false);
1813
1814 auto *BO = cast<BinaryOperator>(Val: &I);
1815 ConstantRange R = A.binaryOp(BO: *BO, Other: B);
1816 mergeInValue(IV&: ValueState[&I], V: &I, MergeWithV: ValueLatticeElement::getRange(CR: R));
1817}
1818
1819// Handle ICmpInst instruction.
1820void SCCPInstVisitor::visitCmpInst(CmpInst &I) {
1821 // Do not cache this lookup, getValueState calls later in the function might
1822 // invalidate the reference.
1823 if (ValueState[&I].isOverdefined())
1824 return (void)markOverdefined(V: &I);
1825
1826 Value *Op1 = I.getOperand(i_nocapture: 0);
1827 Value *Op2 = I.getOperand(i_nocapture: 1);
1828
1829 // For parameters, use ParamState which includes constant range info if
1830 // available.
1831 auto V1State = getValueState(V: Op1);
1832 auto V2State = getValueState(V: Op2);
1833
1834 Constant *C = V1State.getCompare(Pred: I.getPredicate(), Ty: I.getType(), Other: V2State, DL);
1835 if (C) {
1836 ValueLatticeElement CV;
1837 CV.markConstant(V: C);
1838 mergeInValue(IV&: ValueState[&I], V: &I, MergeWithV: CV);
1839 return;
1840 }
1841
1842 // If operands are still unknown, wait for it to resolve.
1843 if ((V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef()) &&
1844 !SCCPSolver::isConstant(LV: ValueState[&I]))
1845 return;
1846
1847 markOverdefined(V: &I);
1848}
1849
1850// Handle getelementptr instructions. If all operands are constants then we
1851// can turn this into a getelementptr ConstantExpr.
1852void SCCPInstVisitor::visitGetElementPtrInst(GetElementPtrInst &I) {
1853 if (ValueState[&I].isOverdefined())
1854 return (void)markOverdefined(V: &I);
1855
1856 const ValueLatticeElement &PtrState = getValueState(V: I.getPointerOperand());
1857 if (PtrState.isUnknownOrUndef())
1858 return;
1859
1860 // gep inbounds/nuw of non-null is non-null.
1861 if (PtrState.isNotConstant() && PtrState.getNotConstant()->isNullValue()) {
1862 if (I.hasNoUnsignedWrap() ||
1863 (I.isInBounds() &&
1864 !NullPointerIsDefined(F: I.getFunction(), AS: I.getAddressSpace())))
1865 return (void)markNotNull(IV&: ValueState[&I], V: &I);
1866 return (void)markOverdefined(V: &I);
1867 }
1868
1869 SmallVector<Constant *, 8> Operands;
1870 Operands.reserve(N: I.getNumOperands());
1871 bool PtrMayHaveDifferentProvenance = PtrState.mayHaveDifferentProvenance();
1872
1873 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
1874 const ValueLatticeElement &State = getValueState(V: I.getOperand(i_nocapture: i));
1875 if (State.isUnknownOrUndef())
1876 return; // Operands are not resolved yet.
1877
1878 if (Constant *C = getConstant(LV: State, Ty: I.getOperand(i_nocapture: i)->getType())) {
1879 Operands.push_back(Elt: C);
1880 continue;
1881 }
1882
1883 return (void)markOverdefined(V: &I);
1884 }
1885
1886 if (Constant *C = ConstantFoldInstOperands(I: &I, Ops: Operands, DL)) {
1887 mergeInValue(IV&: ValueState[&I], V: &I, MergeWithV: ValueLatticeElement::get(C));
1888 // The pointer operand's lattice has found to be a constant, however, the
1889 // returned pointer of the GEP may not be freely substituted, as it may have
1890 // been derived from a pointer with potentially different provenance.
1891 if (PtrMayHaveDifferentProvenance)
1892 ValueState[&I].setMayHaveDifferentProvenance(true);
1893 } else
1894 markOverdefined(V: &I);
1895}
1896
1897void SCCPInstVisitor::visitAllocaInst(AllocaInst &I) {
1898 if (!NullPointerIsDefined(F: I.getFunction(), AS: I.getAddressSpace()))
1899 return (void)markNotNull(IV&: ValueState[&I], V: &I);
1900
1901 markOverdefined(V: &I);
1902}
1903
1904void SCCPInstVisitor::visitStoreInst(StoreInst &SI) {
1905 // If this store is of a struct, ignore it.
1906 if (SI.getOperand(i_nocapture: 0)->getType()->isStructTy())
1907 return;
1908
1909 if (TrackedGlobals.empty() || !isa<GlobalVariable>(Val: SI.getOperand(i_nocapture: 1)))
1910 return;
1911
1912 GlobalVariable *GV = cast<GlobalVariable>(Val: SI.getOperand(i_nocapture: 1));
1913 auto I = TrackedGlobals.find(Val: GV);
1914 if (I == TrackedGlobals.end())
1915 return;
1916
1917 // Get the value we are storing into the global, then merge it.
1918 mergeInValue(IV&: I->second, V: GV, MergeWithV: getValueState(V: SI.getOperand(i_nocapture: 0)),
1919 Opts: ValueLatticeElement::MergeOptions().setCheckWiden(false));
1920 if (I->second.isOverdefined())
1921 TrackedGlobals.erase(I); // No need to keep tracking this!
1922}
1923
1924static ValueLatticeElement getValueFromMetadata(const Instruction *I) {
1925 if (const auto *CB = dyn_cast<CallBase>(Val: I)) {
1926 if (CB->getType()->isIntOrIntVectorTy())
1927 if (std::optional<ConstantRange> Range = CB->getRange())
1928 return ValueLatticeElement::getRange(CR: *Range);
1929 if (CB->getType()->isPointerTy() && CB->isReturnNonNull())
1930 return ValueLatticeElement::getNot(
1931 C: ConstantPointerNull::get(T: cast<PointerType>(Val: I->getType())));
1932 }
1933
1934 if (I->getType()->isIntOrIntVectorTy())
1935 if (MDNode *Ranges = I->getMetadata(KindID: LLVMContext::MD_range))
1936 return ValueLatticeElement::getRange(
1937 CR: getConstantRangeFromMetadata(RangeMD: *Ranges));
1938 if (I->hasMetadata(KindID: LLVMContext::MD_nonnull))
1939 return ValueLatticeElement::getNot(
1940 C: ConstantPointerNull::get(T: cast<PointerType>(Val: I->getType())));
1941
1942 return ValueLatticeElement::getOverdefined();
1943}
1944
1945// Handle load instructions. If the operand is a constant pointer to a constant
1946// global, we can replace the load with the loaded constant value!
1947void SCCPInstVisitor::visitLoadInst(LoadInst &I) {
1948 // If this load is of a struct or the load is volatile, just mark the result
1949 // as overdefined.
1950 if (I.getType()->isStructTy() || I.isVolatile())
1951 return (void)markOverdefined(V: &I);
1952
1953 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1954 // discover a concrete value later.
1955 if (ValueState[&I].isOverdefined())
1956 return (void)markOverdefined(V: &I);
1957
1958 const ValueLatticeElement &PtrVal = getValueState(V: I.getOperand(i_nocapture: 0));
1959 if (PtrVal.isUnknownOrUndef())
1960 return; // The pointer is not resolved yet!
1961
1962 if (SCCPSolver::isConstant(LV: PtrVal)) {
1963 Constant *Ptr = getConstant(LV: PtrVal, Ty: I.getOperand(i_nocapture: 0)->getType());
1964 ValueLatticeElement &IV = ValueState[&I];
1965
1966 // load null is undefined.
1967 if (isa<ConstantPointerNull>(Val: Ptr)) {
1968 if (NullPointerIsDefined(F: I.getFunction(), AS: I.getPointerAddressSpace()))
1969 return (void)markOverdefined(IV, V: &I);
1970 else
1971 return;
1972 }
1973
1974 // Transform load (constant global) into the value loaded.
1975 if (auto *GV = dyn_cast<GlobalVariable>(Val: Ptr)) {
1976 if (!TrackedGlobals.empty()) {
1977 // If we are tracking this global, merge in the known value for it.
1978 auto It = TrackedGlobals.find(Val: GV);
1979 if (It != TrackedGlobals.end()) {
1980 mergeInValue(IV, V: &I, MergeWithV: It->second, Opts: getMaxWidenStepsOpts());
1981 return;
1982 }
1983 }
1984 }
1985
1986 // Transform load from a constant into a constant if possible.
1987 if (Constant *C = ConstantFoldLoadFromConstPtr(C: Ptr, Ty: I.getType(), DL))
1988 return (void)markConstant(IV, V: &I, C);
1989 }
1990
1991 // Fall back to metadata.
1992 mergeInValue(IV&: ValueState[&I], V: &I, MergeWithV: getValueFromMetadata(I: &I));
1993}
1994
1995void SCCPInstVisitor::visitCallBase(CallBase &CB) {
1996 handleCallResult(CB);
1997 handleCallArguments(CB);
1998}
1999
2000void SCCPInstVisitor::handleCallOverdefined(CallBase &CB) {
2001 Function *F = CB.getCalledFunction();
2002
2003 // Void return and not tracking callee, just bail.
2004 if (CB.getType()->isVoidTy())
2005 return;
2006
2007 // Always mark struct return as overdefined.
2008 if (CB.getType()->isStructTy())
2009 return (void)markOverdefined(V: &CB);
2010
2011 if (!F || !F->isDeclaration())
2012 return (void)mergeInValue(IV&: ValueState[&CB], V: &CB, MergeWithV: getValueFromMetadata(I: &CB));
2013
2014 // Otherwise, if we have a single return value case, and if the function is
2015 // a declaration, maybe we can constant fold it.
2016 const TargetLibraryInfo *TLI = &GetTLI(*F);
2017 if (canConstantFoldCallTo(Call: &CB, F, TLI)) {
2018 SmallVector<Constant *, 8> Operands;
2019 for (const Use &A : CB.args()) {
2020 if (A.get()->getType()->isStructTy())
2021 return markOverdefined(V: &CB); // Can't handle struct args.
2022 if (A.get()->getType()->isMetadataTy())
2023 continue; // Carried in CB, not allowed in Operands.
2024 const ValueLatticeElement &State = getValueState(V: A);
2025
2026 if (State.isUnknownOrUndef())
2027 return; // Operands are not resolved yet.
2028 if (SCCPSolver::isOverdefined(LV: State))
2029 return (void)markOverdefined(V: &CB);
2030 assert(SCCPSolver::isConstant(State) && "Unknown state!");
2031 Operands.push_back(Elt: getConstant(LV: State, Ty: A->getType()));
2032 }
2033
2034 if (SCCPSolver::isOverdefined(LV: getValueState(V: &CB)))
2035 return (void)markOverdefined(V: &CB);
2036
2037 // If we can constant fold this, mark the result of the call as a
2038 // constant.
2039 if (Constant *C = ConstantFoldCall(Call: &CB, F, Operands, TLI)) {
2040 mergeInValue(IV&: ValueState[&CB], V: &CB, MergeWithV: ValueLatticeElement::get(C));
2041 return;
2042 }
2043 }
2044
2045 // Fall back to metadata.
2046 mergeInValue(IV&: ValueState[&CB], V: &CB, MergeWithV: getValueFromMetadata(I: &CB));
2047}
2048
2049void SCCPInstVisitor::handleCallArguments(CallBase &CB) {
2050 Function *F = CB.getCalledFunction();
2051 // If this is a local function that doesn't have its address taken, mark its
2052 // entry block executable and merge in the actual arguments to the call into
2053 // the formal arguments of the function.
2054 if (TrackingIncomingArguments.count(Ptr: F)) {
2055 markBlockExecutable(BB: &F->front());
2056
2057 // Propagate information from this call site into the callee.
2058 auto CAI = CB.arg_begin();
2059 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
2060 ++AI, ++CAI) {
2061 // If this argument is byval, and if the function is not readonly, there
2062 // will be an implicit copy formed of the input aggregate.
2063 if (AI->hasByValAttr() && !F->onlyReadsMemory()) {
2064 markOverdefined(V: &*AI);
2065 continue;
2066 }
2067
2068 if (auto *STy = dyn_cast<StructType>(Val: AI->getType())) {
2069 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
2070 ValueLatticeElement CallArg = getStructValueState(V: *CAI, i);
2071 mergeInValue(IV&: getStructValueState(V: &*AI, i), V: &*AI, MergeWithV: CallArg,
2072 Opts: getMaxWidenStepsOpts());
2073 }
2074 } else {
2075 ValueLatticeElement CallArg =
2076 getValueState(V: *CAI).intersect(Other: getArgAttributeVL(A: &*AI));
2077 mergeInValue(IV&: ValueState[&*AI], V: &*AI, MergeWithV: CallArg, Opts: getMaxWidenStepsOpts());
2078 }
2079 }
2080 }
2081}
2082
2083void SCCPInstVisitor::handlePredicate(Instruction *I, Value *CopyOf,
2084 const PredicateBase *PI) {
2085 ValueLatticeElement CopyOfVal = getValueState(V: CopyOf);
2086 const std::optional<PredicateConstraint> &Constraint = PI->getConstraint();
2087 if (!Constraint) {
2088 mergeInValue(IV&: ValueState[I], V: I, MergeWithV: CopyOfVal);
2089 return;
2090 }
2091
2092 CmpInst::Predicate Pred = Constraint->Predicate;
2093 Value *OtherOp = Constraint->OtherOp;
2094
2095 // Wait until OtherOp is resolved.
2096 if (getValueState(V: OtherOp).isUnknown()) {
2097 addAdditionalUser(V: OtherOp, U: I);
2098 return;
2099 }
2100
2101 ValueLatticeElement CondVal = getValueState(V: OtherOp);
2102 ValueLatticeElement &IV = ValueState[I];
2103 if (CondVal.isConstantRange() || CopyOfVal.isConstantRange()) {
2104 auto ImposedCR =
2105 ConstantRange::getFull(BitWidth: DL.getTypeSizeInBits(Ty: CopyOf->getType()));
2106
2107 // Get the range imposed by the condition.
2108 if (CondVal.isConstantRange())
2109 ImposedCR = ConstantRange::makeAllowedICmpRegion(
2110 Pred, Other: CondVal.getConstantRange());
2111
2112 // Combine range info for the original value with the new range from the
2113 // condition.
2114 auto CopyOfCR = CopyOfVal.asConstantRange(Ty: CopyOf->getType(),
2115 /*UndefAllowed=*/true);
2116 // Treat an unresolved input like a full range.
2117 if (CopyOfCR.isEmptySet())
2118 CopyOfCR = ConstantRange::getFull(BitWidth: CopyOfCR.getBitWidth());
2119 auto NewCR = ImposedCR.intersectWith(CR: CopyOfCR);
2120 // If the existing information is != x, do not use the information from
2121 // a chained predicate, as the != x information is more likely to be
2122 // helpful in practice.
2123 if (!CopyOfCR.contains(CR: NewCR) && CopyOfCR.getSingleMissingElement())
2124 NewCR = std::move(CopyOfCR);
2125
2126 // The new range is based on a branch condition. That guarantees that
2127 // neither of the compare operands can be undef in the branch targets,
2128 // unless we have conditions that are always true/false (e.g. icmp ule
2129 // i32, %a, i32_max). For the latter overdefined/empty range will be
2130 // inferred, but the branch will get folded accordingly anyways.
2131 addAdditionalUser(V: OtherOp, U: I);
2132 mergeInValue(
2133 IV, V: I, MergeWithV: ValueLatticeElement::getRange(CR: NewCR, /*MayIncludeUndef*/ false));
2134 return;
2135 } else if (Pred == CmpInst::ICMP_EQ &&
2136 (CondVal.isConstant() || CondVal.isNotConstant())) {
2137 // For non-integer values or integer constant expressions, only
2138 // propagate equal constants or not-constants.
2139 addAdditionalUser(V: OtherOp, U: I);
2140 if (CopyOf->getType()->isPointerTy())
2141 CondVal.setMayHaveDifferentProvenance(true);
2142 mergeInValue(IV, V: I, MergeWithV: CondVal);
2143 return;
2144 } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant()) {
2145 // Propagate inequalities.
2146 addAdditionalUser(V: OtherOp, U: I);
2147 mergeInValue(IV, V: I, MergeWithV: ValueLatticeElement::getNot(C: CondVal.getConstant()));
2148 return;
2149 }
2150
2151 return (void)mergeInValue(IV, V: I, MergeWithV: CopyOfVal);
2152}
2153
2154void SCCPInstVisitor::handleCallResult(CallBase &CB) {
2155 Function *F = CB.getCalledFunction();
2156
2157 if (auto *II = dyn_cast<IntrinsicInst>(Val: &CB)) {
2158 if (II->getIntrinsicID() == Intrinsic::vscale) {
2159 unsigned BitWidth = CB.getType()->getScalarSizeInBits();
2160 const ConstantRange Result = getVScaleRange(F: II->getFunction(), BitWidth);
2161 return (void)mergeInValue(IV&: ValueState[II], V: II,
2162 MergeWithV: ValueLatticeElement::getRange(CR: Result));
2163 }
2164 if (II->getIntrinsicID() == Intrinsic::experimental_get_vector_length) {
2165 Value *CountArg = II->getArgOperand(i: 0);
2166 Value *VF = II->getArgOperand(i: 1);
2167 bool Scalable = cast<ConstantInt>(Val: II->getArgOperand(i: 2))->isOne();
2168
2169 // Computation happens in the larger type.
2170 unsigned BitWidth = std::max(a: CountArg->getType()->getScalarSizeInBits(),
2171 b: VF->getType()->getScalarSizeInBits());
2172
2173 ConstantRange Count = getValueState(V: CountArg)
2174 .asConstantRange(Ty: CountArg->getType(), UndefAllowed: false)
2175 .zeroExtend(BitWidth);
2176 ConstantRange MaxLanes = getValueState(V: VF)
2177 .asConstantRange(Ty: VF->getType(), UndefAllowed: false)
2178 .zeroExtend(BitWidth);
2179 if (Scalable)
2180 MaxLanes =
2181 MaxLanes.multiply(Other: getVScaleRange(F: II->getFunction(), BitWidth));
2182
2183 // The result is always less than both Count and MaxLanes.
2184 ConstantRange Result = ConstantRange::getNonEmpty(
2185 Lower: APInt::getZero(numBits: BitWidth),
2186 Upper: APIntOps::umin(A: Count.getUnsignedMax(), B: MaxLanes.getUnsignedMax()) +
2187 1);
2188
2189 // If Count <= MaxLanes, getvectorlength(Count, MaxLanes) = Count
2190 if (Count.icmp(Pred: CmpInst::ICMP_ULE, Other: MaxLanes))
2191 Result = std::move(Count);
2192
2193 Result = Result.truncate(BitWidth: II->getType()->getScalarSizeInBits());
2194 return (void)mergeInValue(IV&: ValueState[II], V: II,
2195 MergeWithV: ValueLatticeElement::getRange(CR: Result));
2196 }
2197
2198 if (ConstantRange::isIntrinsicSupported(IntrinsicID: II->getIntrinsicID())) {
2199 // Compute result range for intrinsics supported by ConstantRange.
2200 // Do this even if we don't know a range for all operands, as we may
2201 // still know something about the result range, e.g. of abs(x).
2202 SmallVector<ConstantRange, 2> OpRanges;
2203 for (Value *Op : II->args()) {
2204 const ValueLatticeElement &State = getValueState(V: Op);
2205 if (State.isUnknownOrUndef())
2206 return;
2207 OpRanges.push_back(
2208 Elt: State.asConstantRange(Ty: Op->getType(), /*UndefAllowed=*/false));
2209 }
2210
2211 ConstantRange Result =
2212 ConstantRange::intrinsic(IntrinsicID: II->getIntrinsicID(), Ops: OpRanges);
2213 return (void)mergeInValue(IV&: ValueState[II], V: II,
2214 MergeWithV: ValueLatticeElement::getRange(CR: Result));
2215 }
2216 }
2217
2218 // The common case is that we aren't tracking the callee, either because we
2219 // are not doing interprocedural analysis or the callee is indirect, or is
2220 // external. Handle these cases first.
2221 if (!F || F->isDeclaration())
2222 return handleCallOverdefined(CB);
2223
2224 // If this is a single/zero retval case, see if we're tracking the function.
2225 if (auto *STy = dyn_cast<StructType>(Val: F->getReturnType())) {
2226 if (!MRVFunctionsTracked.count(Ptr: F))
2227 return handleCallOverdefined(CB); // Not tracking this callee.
2228
2229 // If we are tracking this callee, propagate the result of the function
2230 // into this call site.
2231 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
2232 mergeInValue(IV&: getStructValueState(V: &CB, i), V: &CB,
2233 MergeWithV: TrackedMultipleRetVals[std::make_pair(x&: F, y&: i)],
2234 Opts: getMaxWidenStepsOpts());
2235 } else {
2236 auto TFRVI = TrackedRetVals.find(Key: F);
2237 if (TFRVI == TrackedRetVals.end())
2238 return handleCallOverdefined(CB); // Not tracking this callee.
2239
2240 // If so, propagate the return value of the callee into this call result.
2241 mergeInValue(IV&: ValueState[&CB], V: &CB, MergeWithV: TFRVI->second, Opts: getMaxWidenStepsOpts());
2242 }
2243}
2244
2245bool SCCPInstVisitor::isInstFullyOverDefined(Instruction &Inst) {
2246 // For structure Type, we handle each member separately.
2247 // A structure object won't be considered as overdefined when
2248 // there is at least one member that is not overdefined.
2249 if (StructType *STy = dyn_cast<StructType>(Val: Inst.getType())) {
2250 for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i) {
2251 if (!getStructValueState(V: &Inst, i).isOverdefined())
2252 return false;
2253 }
2254 return true;
2255 }
2256
2257 return getValueState(V: &Inst).isOverdefined();
2258}
2259
2260void SCCPInstVisitor::solve() {
2261 // Process the work lists until they are empty!
2262 while (!BBWorkList.empty() || !InstWorkList.empty()) {
2263 // Process the instruction work list.
2264 while (!InstWorkList.empty()) {
2265 Instruction *I = InstWorkList.pop_back_val();
2266 Invalidated.erase(V: I);
2267
2268 LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');
2269
2270 visit(I);
2271 }
2272
2273 // Process the basic block work list.
2274 while (!BBWorkList.empty()) {
2275 BasicBlock *BB = BBWorkList.pop_back_val();
2276 BBVisited.insert(Ptr: BB);
2277
2278 LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n');
2279 for (Instruction &I : *BB) {
2280 CurI = &I;
2281 visit(I);
2282 }
2283 CurI = nullptr;
2284 }
2285 }
2286}
2287
2288bool SCCPInstVisitor::resolvedUndef(Instruction &I) {
2289 // Look for instructions which produce undef values.
2290 if (I.getType()->isVoidTy())
2291 return false;
2292
2293 if (auto *STy = dyn_cast<StructType>(Val: I.getType())) {
2294 // Only a few things that can be structs matter for undef.
2295
2296 // Tracked calls must never be marked overdefined in resolvedUndefsIn.
2297 if (auto *CB = dyn_cast<CallBase>(Val: &I))
2298 if (Function *F = CB->getCalledFunction())
2299 if (MRVFunctionsTracked.count(Ptr: F))
2300 return false;
2301
2302 // extractvalue and insertvalue don't need to be marked; they are
2303 // tracked as precisely as their operands.
2304 if (isa<ExtractValueInst>(Val: I) || isa<InsertValueInst>(Val: I))
2305 return false;
2306 // Send the results of everything else to overdefined. We could be
2307 // more precise than this but it isn't worth bothering.
2308 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
2309 ValueLatticeElement &LV = getStructValueState(V: &I, i);
2310 if (LV.isUnknown()) {
2311 markOverdefined(IV&: LV, V: &I);
2312 return true;
2313 }
2314 }
2315 return false;
2316 }
2317
2318 ValueLatticeElement &LV = getValueState(V: &I);
2319 if (!LV.isUnknown())
2320 return false;
2321
2322 // There are two reasons a call can have an undef result
2323 // 1. It could be tracked.
2324 // 2. It could be constant-foldable.
2325 // Because of the way we solve return values, tracked calls must
2326 // never be marked overdefined in resolvedUndefsIn.
2327 if (auto *CB = dyn_cast<CallBase>(Val: &I))
2328 if (Function *F = CB->getCalledFunction())
2329 if (TrackedRetVals.count(Key: F))
2330 return false;
2331
2332 if (isa<LoadInst>(Val: I)) {
2333 // A load here means one of two things: a load of undef from a global,
2334 // a load from an unknown pointer. Either way, having it return undef
2335 // is okay.
2336 return false;
2337 }
2338
2339 markOverdefined(V: &I);
2340 return true;
2341}
2342
2343/// While solving the dataflow for a function, we don't compute a result for
2344/// operations with an undef operand, to allow undef to be lowered to a
2345/// constant later. For example, constant folding of "zext i8 undef to i16"
2346/// would result in "i16 0", and if undef is later lowered to "i8 1", then the
2347/// zext result would become "i16 1" and would result into an overdefined
2348/// lattice value once merged with the previous result. Not computing the
2349/// result of the zext (treating undef the same as unknown) allows us to handle
2350/// a later undef->constant lowering more optimally.
2351///
2352/// However, if the operand remains undef when the solver returns, we do need
2353/// to assign some result to the instruction (otherwise we would treat it as
2354/// unreachable). For simplicity, we mark any instructions that are still
2355/// unknown as overdefined.
2356bool SCCPInstVisitor::resolvedUndefsIn(Function &F) {
2357 bool MadeChange = false;
2358 for (BasicBlock &BB : F) {
2359 if (!BBExecutable.count(Ptr: &BB))
2360 continue;
2361
2362 for (Instruction &I : BB)
2363 MadeChange |= resolvedUndef(I);
2364 }
2365
2366 LLVM_DEBUG(if (MadeChange) dbgs()
2367 << "\nResolved undefs in " << F.getName() << '\n');
2368
2369 return MadeChange;
2370}
2371
2372//===----------------------------------------------------------------------===//
2373//
2374// SCCPSolver implementations
2375//
2376SCCPSolver::SCCPSolver(
2377 const DataLayout &DL,
2378 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
2379 LLVMContext &Ctx)
2380 : Visitor(new SCCPInstVisitor(DL, std::move(GetTLI), Ctx)) {}
2381
2382SCCPSolver::~SCCPSolver() = default;
2383
2384const DataLayout &SCCPSolver::getDataLayout() const {
2385 return Visitor->getDataLayout();
2386}
2387
2388void SCCPSolver::addPredicateInfo(Function &F, DominatorTree &DT,
2389 AssumptionCache &AC) {
2390 Visitor->addPredicateInfo(F, DT, AC);
2391}
2392
2393void SCCPSolver::removeSSACopies(Function &F) {
2394 Visitor->removeSSACopies(F);
2395}
2396
2397bool SCCPSolver::markBlockExecutable(BasicBlock *BB) {
2398 return Visitor->markBlockExecutable(BB);
2399}
2400
2401const PredicateBase *SCCPSolver::getPredicateInfoFor(Instruction *I) {
2402 return Visitor->getPredicateInfoFor(I);
2403}
2404
2405void SCCPSolver::trackValueOfGlobalVariable(GlobalVariable *GV) {
2406 Visitor->trackValueOfGlobalVariable(GV);
2407}
2408
2409void SCCPSolver::addTrackedFunction(Function *F) {
2410 Visitor->addTrackedFunction(F);
2411}
2412
2413void SCCPSolver::addToMustPreserveReturnsInFunctions(Function *F) {
2414 Visitor->addToMustPreserveReturnsInFunctions(F);
2415}
2416
2417bool SCCPSolver::mustPreserveReturn(Function *F) {
2418 return Visitor->mustPreserveReturn(F);
2419}
2420
2421void SCCPSolver::addArgumentTrackedFunction(Function *F) {
2422 Visitor->addArgumentTrackedFunction(F);
2423}
2424
2425bool SCCPSolver::isArgumentTrackedFunction(Function *F) {
2426 return Visitor->isArgumentTrackedFunction(F);
2427}
2428
2429const SmallPtrSetImpl<Function *> &
2430SCCPSolver::getArgumentTrackedFunctions() const {
2431 return Visitor->getArgumentTrackedFunctions();
2432}
2433
2434void SCCPSolver::solve() { Visitor->solve(); }
2435
2436bool SCCPSolver::resolvedUndefsIn(Function &F) {
2437 return Visitor->resolvedUndefsIn(F);
2438}
2439
2440void SCCPSolver::solveWhileResolvedUndefsIn(Module &M) {
2441 Visitor->solveWhileResolvedUndefsIn(M);
2442}
2443
2444void
2445SCCPSolver::solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList) {
2446 Visitor->solveWhileResolvedUndefsIn(WorkList);
2447}
2448
2449void SCCPSolver::solveWhileResolvedUndefs() {
2450 Visitor->solveWhileResolvedUndefs();
2451}
2452
2453bool SCCPSolver::isBlockExecutable(BasicBlock *BB) const {
2454 return Visitor->isBlockExecutable(BB);
2455}
2456
2457bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const {
2458 return Visitor->isEdgeFeasible(From, To);
2459}
2460
2461std::vector<ValueLatticeElement>
2462SCCPSolver::getStructLatticeValueFor(Value *V) const {
2463 return Visitor->getStructLatticeValueFor(V);
2464}
2465
2466void SCCPSolver::removeLatticeValueFor(Value *V) {
2467 return Visitor->removeLatticeValueFor(V);
2468}
2469
2470void SCCPSolver::resetLatticeValueFor(CallBase *Call) {
2471 Visitor->resetLatticeValueFor(Call);
2472}
2473
2474const ValueLatticeElement &SCCPSolver::getLatticeValueFor(Value *V) const {
2475 return Visitor->getLatticeValueFor(V);
2476}
2477
2478const MapVector<Function *, ValueLatticeElement> &
2479SCCPSolver::getTrackedRetVals() const {
2480 return Visitor->getTrackedRetVals();
2481}
2482
2483const DenseMap<GlobalVariable *, ValueLatticeElement> &
2484SCCPSolver::getTrackedGlobals() const {
2485 return Visitor->getTrackedGlobals();
2486}
2487
2488const SmallPtrSet<Function *, 16> &SCCPSolver::getMRVFunctionsTracked() const {
2489 return Visitor->getMRVFunctionsTracked();
2490}
2491
2492void SCCPSolver::markOverdefined(Value *V) { Visitor->markOverdefined(V); }
2493
2494void SCCPSolver::trackValueOfArgument(Argument *V) {
2495 Visitor->trackValueOfArgument(A: V);
2496}
2497
2498bool SCCPSolver::isStructLatticeConstant(Function *F, StructType *STy) {
2499 return Visitor->isStructLatticeConstant(F, STy);
2500}
2501
2502Constant *SCCPSolver::getConstant(const ValueLatticeElement &LV,
2503 Type *Ty) const {
2504 return Visitor->getConstant(LV, Ty);
2505}
2506
2507Constant *SCCPSolver::getConstantOrNull(Value *V) const {
2508 return Visitor->getConstantOrNull(V);
2509}
2510
2511void SCCPSolver::setLatticeValueForSpecializationArguments(Function *F,
2512 const SmallVectorImpl<ArgInfo> &Args) {
2513 Visitor->setLatticeValueForSpecializationArguments(F, Args);
2514}
2515
2516void SCCPSolver::markFunctionUnreachable(Function *F) {
2517 Visitor->markFunctionUnreachable(F);
2518}
2519
2520void SCCPSolver::visit(Instruction *I) { Visitor->visit(I); }
2521
2522void SCCPSolver::visitCall(CallInst &I) { Visitor->visitCall(I); }
2523