1 //===- SCCPSolver.cpp - SCCP Utility --------------------------- *- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
10 // This file implements the Sparse Conditional Constant Propagation (SCCP)
13 //===----------------------------------------------------------------------===//
15 #include "llvm/Transforms/Utils/SCCPSolver.h"
16 #include "llvm/Analysis/ConstantFolding.h"
17 #include "llvm/Analysis/InstructionSimplify.h"
18 #include "llvm/Analysis/ValueTracking.h"
19 #include "llvm/InitializePasses.h"
20 #include "llvm/Pass.h"
21 #include "llvm/Support/Casting.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/ErrorHandling.h"
24 #include "llvm/Support/raw_ostream.h"
25 #include "llvm/Transforms/Utils/Local.h"
32 #define DEBUG_TYPE "sccp"
34 // The maximum number of range extensions allowed for operations requiring
36 static const unsigned MaxNumRangeExtensions = 10;
38 /// Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions.
39 static ValueLatticeElement::MergeOptions getMaxWidenStepsOpts() {
40 return ValueLatticeElement::MergeOptions().setMaxWidenSteps(
41 MaxNumRangeExtensions);
46 // Helper to check if \p LV is either a constant or a constant
47 // range with a single element. This should cover exactly the same cases as the
48 // old ValueLatticeElement::isConstant() and is intended to be used in the
49 // transition to ValueLatticeElement.
50 bool isConstant(const ValueLatticeElement &LV) {
51 return LV.isConstant() ||
52 (LV.isConstantRange() && LV.getConstantRange().isSingleElement());
55 // Helper to check if \p LV is either overdefined or a constant range with more
56 // than a single element. This should cover exactly the same cases as the old
57 // ValueLatticeElement::isOverdefined() and is intended to be used in the
58 // transition to ValueLatticeElement.
59 bool isOverdefined(const ValueLatticeElement &LV) {
60 return !LV.isUnknownOrUndef() && !isConstant(LV);
67 /// Helper class for SCCPSolver. This implements the instruction visitor and
68 /// holds all the state.
69 class SCCPInstVisitor : public InstVisitor<SCCPInstVisitor> {
71 std::function<const TargetLibraryInfo &(Function &)> GetTLI;
72 SmallPtrSet<BasicBlock *, 8> BBExecutable; // The BBs that are executable.
73 DenseMap<Value *, ValueLatticeElement>
74 ValueState; // The state each value is in.
76 /// StructValueState - This maintains ValueState for values that have
77 /// StructType, for example for formal arguments, calls, insertelement, etc.
78 DenseMap<std::pair<Value *, unsigned>, ValueLatticeElement> StructValueState;
80 /// GlobalValue - If we are tracking any values for the contents of a global
81 /// variable, we keep a mapping from the constant accessor to the element of
82 /// the global, to the currently known value. If the value becomes
83 /// overdefined, it's entry is simply removed from this map.
84 DenseMap<GlobalVariable *, ValueLatticeElement> TrackedGlobals;
86 /// TrackedRetVals - If we are tracking arguments into and the return
87 /// value out of a function, it will have an entry in this map, indicating
88 /// what the known return value for the function is.
89 MapVector<Function *, ValueLatticeElement> TrackedRetVals;
91 /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions
92 /// that return multiple values.
93 MapVector<std::pair<Function *, unsigned>, ValueLatticeElement>
94 TrackedMultipleRetVals;
96 /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is
97 /// represented here for efficient lookup.
98 SmallPtrSet<Function *, 16> MRVFunctionsTracked;
100 /// A list of functions whose return cannot be modified.
101 SmallPtrSet<Function *, 16> MustPreserveReturnsInFunctions;
103 /// TrackingIncomingArguments - This is the set of functions for whose
104 /// arguments we make optimistic assumptions about and try to prove as
106 SmallPtrSet<Function *, 16> TrackingIncomingArguments;
108 /// The reason for two worklists is that overdefined is the lowest state
109 /// on the lattice, and moving things to overdefined as fast as possible
110 /// makes SCCP converge much faster.
112 /// By having a separate worklist, we accomplish this because everything
113 /// possibly overdefined will become overdefined at the soonest possible
115 SmallVector<Value *, 64> OverdefinedInstWorkList;
116 SmallVector<Value *, 64> InstWorkList;
118 // The BasicBlock work list
119 SmallVector<BasicBlock *, 64> BBWorkList;
121 /// KnownFeasibleEdges - Entries in this set are edges which have already had
122 /// PHI nodes retriggered.
123 using Edge = std::pair<BasicBlock *, BasicBlock *>;
124 DenseSet<Edge> KnownFeasibleEdges;
126 DenseMap<Function *, AnalysisResultsForFn> AnalysisResults;
127 DenseMap<Value *, SmallPtrSet<User *, 2>> AdditionalUsers;
132 ConstantInt *getConstantInt(const ValueLatticeElement &IV) const {
133 return dyn_cast_or_null<ConstantInt>(getConstant(IV));
136 // pushToWorkList - Helper for markConstant/markOverdefined
137 void pushToWorkList(ValueLatticeElement &IV, Value *V);
139 // Helper to push \p V to the worklist, after updating it to \p IV. Also
140 // prints a debug message with the updated value.
141 void pushToWorkListMsg(ValueLatticeElement &IV, Value *V);
143 // markConstant - Make a value be marked as "constant". If the value
144 // is not already a constant, add it to the instruction work list so that
145 // the users of the instruction are updated later.
146 bool markConstant(ValueLatticeElement &IV, Value *V, Constant *C,
147 bool MayIncludeUndef = false);
149 bool markConstant(Value *V, Constant *C) {
150 assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
151 return markConstant(ValueState[V], V, C);
154 // markOverdefined - Make a value be marked as "overdefined". If the
155 // value is not already overdefined, add it to the overdefined instruction
156 // work list so that the users of the instruction are updated later.
157 bool markOverdefined(ValueLatticeElement &IV, Value *V);
159 /// Merge \p MergeWithV into \p IV and push \p V to the worklist, if \p IV
161 bool mergeInValue(ValueLatticeElement &IV, Value *V,
162 ValueLatticeElement MergeWithV,
163 ValueLatticeElement::MergeOptions Opts = {
164 /*MayIncludeUndef=*/false, /*CheckWiden=*/false});
166 bool mergeInValue(Value *V, ValueLatticeElement MergeWithV,
167 ValueLatticeElement::MergeOptions Opts = {
168 /*MayIncludeUndef=*/false, /*CheckWiden=*/false}) {
169 assert(!V->getType()->isStructTy() &&
170 "non-structs should use markConstant");
171 return mergeInValue(ValueState[V], V, MergeWithV, Opts);
174 /// getValueState - Return the ValueLatticeElement object that corresponds to
175 /// the value. This function handles the case when the value hasn't been seen
176 /// yet by properly seeding constants etc.
177 ValueLatticeElement &getValueState(Value *V) {
178 assert(!V->getType()->isStructTy() && "Should use getStructValueState");
180 auto I = ValueState.insert(std::make_pair(V, ValueLatticeElement()));
181 ValueLatticeElement &LV = I.first->second;
184 return LV; // Common case, already in the map.
186 if (auto *C = dyn_cast<Constant>(V))
187 LV.markConstant(C); // Constants are constant
189 // All others are unknown by default.
193 /// getStructValueState - Return the ValueLatticeElement object that
194 /// corresponds to the value/field pair. This function handles the case when
195 /// the value hasn't been seen yet by properly seeding constants etc.
196 ValueLatticeElement &getStructValueState(Value *V, unsigned i) {
197 assert(V->getType()->isStructTy() && "Should use getValueState");
198 assert(i < cast<StructType>(V->getType())->getNumElements() &&
199 "Invalid element #");
201 auto I = StructValueState.insert(
202 std::make_pair(std::make_pair(V, i), ValueLatticeElement()));
203 ValueLatticeElement &LV = I.first->second;
206 return LV; // Common case, already in the map.
208 if (auto *C = dyn_cast<Constant>(V)) {
209 Constant *Elt = C->getAggregateElement(i);
212 LV.markOverdefined(); // Unknown sort of constant.
213 else if (isa<UndefValue>(Elt))
214 ; // Undef values remain unknown.
216 LV.markConstant(Elt); // Constants are constant.
219 // All others are underdefined by default.
223 /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
224 /// work list if it is not already executable.
225 bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
227 // getFeasibleSuccessors - Return a vector of booleans to indicate which
228 // successors are reachable from a given terminator instruction.
229 void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl<bool> &Succs);
231 // OperandChangedState - This method is invoked on all of the users of an
232 // instruction that was just changed state somehow. Based on this
233 // information, we need to update the specified user of this instruction.
234 void operandChangedState(Instruction *I) {
235 if (BBExecutable.count(I->getParent())) // Inst is executable?
239 // Add U as additional user of V.
240 void addAdditionalUser(Value *V, User *U) {
241 auto Iter = AdditionalUsers.insert({V, {}});
242 Iter.first->second.insert(U);
245 // Mark I's users as changed, including AdditionalUsers.
246 void markUsersAsChanged(Value *I) {
247 // Functions include their arguments in the use-list. Changed function
248 // values mean that the result of the function changed. We only need to
249 // update the call sites with the new function result and do not have to
250 // propagate the call arguments.
251 if (isa<Function>(I)) {
252 for (User *U : I->users()) {
253 if (auto *CB = dyn_cast<CallBase>(U))
254 handleCallResult(*CB);
257 for (User *U : I->users())
258 if (auto *UI = dyn_cast<Instruction>(U))
259 operandChangedState(UI);
262 auto Iter = AdditionalUsers.find(I);
263 if (Iter != AdditionalUsers.end()) {
264 // Copy additional users before notifying them of changes, because new
265 // users may be added, potentially invalidating the iterator.
266 SmallVector<Instruction *, 2> ToNotify;
267 for (User *U : Iter->second)
268 if (auto *UI = dyn_cast<Instruction>(U))
269 ToNotify.push_back(UI);
270 for (Instruction *UI : ToNotify)
271 operandChangedState(UI);
274 void handleCallOverdefined(CallBase &CB);
275 void handleCallResult(CallBase &CB);
276 void handleCallArguments(CallBase &CB);
279 friend class InstVisitor<SCCPInstVisitor>;
281 // visit implementations - Something changed in this instruction. Either an
282 // operand made a transition, or the instruction is newly executable. Change
283 // the value type of I to reflect these changes if appropriate.
284 void visitPHINode(PHINode &I);
288 void visitReturnInst(ReturnInst &I);
289 void visitTerminator(Instruction &TI);
291 void visitCastInst(CastInst &I);
292 void visitSelectInst(SelectInst &I);
293 void visitUnaryOperator(Instruction &I);
294 void visitBinaryOperator(Instruction &I);
295 void visitCmpInst(CmpInst &I);
296 void visitExtractValueInst(ExtractValueInst &EVI);
297 void visitInsertValueInst(InsertValueInst &IVI);
299 void visitCatchSwitchInst(CatchSwitchInst &CPI) {
300 markOverdefined(&CPI);
301 visitTerminator(CPI);
304 // Instructions that cannot be folded away.
306 void visitStoreInst(StoreInst &I);
307 void visitLoadInst(LoadInst &I);
308 void visitGetElementPtrInst(GetElementPtrInst &I);
310 void visitInvokeInst(InvokeInst &II) {
315 void visitCallBrInst(CallBrInst &CBI) {
317 visitTerminator(CBI);
320 void visitCallBase(CallBase &CB);
321 void visitResumeInst(ResumeInst &I) { /*returns void*/
323 void visitUnreachableInst(UnreachableInst &I) { /*returns void*/
325 void visitFenceInst(FenceInst &I) { /*returns void*/
328 void visitInstruction(Instruction &I);
331 void addAnalysis(Function &F, AnalysisResultsForFn A) {
332 AnalysisResults.insert({&F, std::move(A)});
335 void visitCallInst(CallInst &I) { visitCallBase(I); }
337 bool markBlockExecutable(BasicBlock *BB);
339 const PredicateBase *getPredicateInfoFor(Instruction *I) {
340 auto A = AnalysisResults.find(I->getParent()->getParent());
341 if (A == AnalysisResults.end())
343 return A->second.PredInfo->getPredicateInfoFor(I);
346 DomTreeUpdater getDTU(Function &F) {
347 auto A = AnalysisResults.find(&F);
348 assert(A != AnalysisResults.end() && "Need analysis results for function.");
349 return {A->second.DT, A->second.PDT, DomTreeUpdater::UpdateStrategy::Lazy};
352 SCCPInstVisitor(const DataLayout &DL,
353 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
355 : DL(DL), GetTLI(GetTLI), Ctx(Ctx) {}
357 void trackValueOfGlobalVariable(GlobalVariable *GV) {
358 // We only track the contents of scalar globals.
359 if (GV->getValueType()->isSingleValueType()) {
360 ValueLatticeElement &IV = TrackedGlobals[GV];
361 if (!isa<UndefValue>(GV->getInitializer()))
362 IV.markConstant(GV->getInitializer());
366 void addTrackedFunction(Function *F) {
367 // Add an entry, F -> undef.
368 if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
369 MRVFunctionsTracked.insert(F);
370 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
371 TrackedMultipleRetVals.insert(
372 std::make_pair(std::make_pair(F, i), ValueLatticeElement()));
373 } else if (!F->getReturnType()->isVoidTy())
374 TrackedRetVals.insert(std::make_pair(F, ValueLatticeElement()));
377 void addToMustPreserveReturnsInFunctions(Function *F) {
378 MustPreserveReturnsInFunctions.insert(F);
381 bool mustPreserveReturn(Function *F) {
382 return MustPreserveReturnsInFunctions.count(F);
385 void addArgumentTrackedFunction(Function *F) {
386 TrackingIncomingArguments.insert(F);
389 bool isArgumentTrackedFunction(Function *F) {
390 return TrackingIncomingArguments.count(F);
395 bool resolvedUndefsIn(Function &F);
397 bool isBlockExecutable(BasicBlock *BB) const {
398 return BBExecutable.count(BB);
401 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
403 std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const {
404 std::vector<ValueLatticeElement> StructValues;
405 auto *STy = dyn_cast<StructType>(V->getType());
406 assert(STy && "getStructLatticeValueFor() can be called only on structs");
407 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
408 auto I = StructValueState.find(std::make_pair(V, i));
409 assert(I != StructValueState.end() && "Value not in valuemap!");
410 StructValues.push_back(I->second);
415 void removeLatticeValueFor(Value *V) { ValueState.erase(V); }
417 const ValueLatticeElement &getLatticeValueFor(Value *V) const {
418 assert(!V->getType()->isStructTy() &&
419 "Should use getStructLatticeValueFor");
420 DenseMap<Value *, ValueLatticeElement>::const_iterator I =
422 assert(I != ValueState.end() &&
423 "V not found in ValueState nor Paramstate map!");
427 const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals() {
428 return TrackedRetVals;
431 const DenseMap<GlobalVariable *, ValueLatticeElement> &getTrackedGlobals() {
432 return TrackedGlobals;
435 const SmallPtrSet<Function *, 16> getMRVFunctionsTracked() {
436 return MRVFunctionsTracked;
439 void markOverdefined(Value *V) {
440 if (auto *STy = dyn_cast<StructType>(V->getType()))
441 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
442 markOverdefined(getStructValueState(V, i), V);
444 markOverdefined(ValueState[V], V);
447 bool isStructLatticeConstant(Function *F, StructType *STy);
449 Constant *getConstant(const ValueLatticeElement &LV) const;
451 SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions() {
452 return TrackingIncomingArguments;
455 void markArgInFuncSpecialization(Function *F, Argument *A, Constant *C);
457 void markFunctionUnreachable(Function *F) {
459 BBExecutable.erase(&BB);
465 bool SCCPInstVisitor::markBlockExecutable(BasicBlock *BB) {
466 if (!BBExecutable.insert(BB).second)
468 LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n');
469 BBWorkList.push_back(BB); // Add the block to the work list!
473 void SCCPInstVisitor::pushToWorkList(ValueLatticeElement &IV, Value *V) {
474 if (IV.isOverdefined())
475 return OverdefinedInstWorkList.push_back(V);
476 InstWorkList.push_back(V);
479 void SCCPInstVisitor::pushToWorkListMsg(ValueLatticeElement &IV, Value *V) {
480 LLVM_DEBUG(dbgs() << "updated " << IV << ": " << *V << '\n');
481 pushToWorkList(IV, V);
484 bool SCCPInstVisitor::markConstant(ValueLatticeElement &IV, Value *V,
485 Constant *C, bool MayIncludeUndef) {
486 if (!IV.markConstant(C, MayIncludeUndef))
488 LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');
489 pushToWorkList(IV, V);
493 bool SCCPInstVisitor::markOverdefined(ValueLatticeElement &IV, Value *V) {
494 if (!IV.markOverdefined())
497 LLVM_DEBUG(dbgs() << "markOverdefined: ";
498 if (auto *F = dyn_cast<Function>(V)) dbgs()
499 << "Function '" << F->getName() << "'\n";
500 else dbgs() << *V << '\n');
501 // Only instructions go on the work list
502 pushToWorkList(IV, V);
506 bool SCCPInstVisitor::isStructLatticeConstant(Function *F, StructType *STy) {
507 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
508 const auto &It = TrackedMultipleRetVals.find(std::make_pair(F, i));
509 assert(It != TrackedMultipleRetVals.end());
510 ValueLatticeElement LV = It->second;
517 Constant *SCCPInstVisitor::getConstant(const ValueLatticeElement &LV) const {
519 return LV.getConstant();
521 if (LV.isConstantRange()) {
522 const auto &CR = LV.getConstantRange();
523 if (CR.getSingleElement())
524 return ConstantInt::get(Ctx, *CR.getSingleElement());
529 void SCCPInstVisitor::markArgInFuncSpecialization(Function *F, Argument *A,
531 assert(F->arg_size() == A->getParent()->arg_size() &&
532 "Functions should have the same number of arguments");
534 // Mark the argument constant in the new function.
537 // For the remaining arguments in the new function, copy the lattice state
538 // over from the old function.
539 for (auto I = F->arg_begin(), J = A->getParent()->arg_begin(),
542 if (J != A && ValueState.count(I)) {
543 // Note: This previously looked like this:
544 // ValueState[J] = ValueState[I];
545 // This is incorrect because the DenseMap class may resize the underlying
546 // memory when inserting `J`, which will invalidate the reference to `I`.
547 // Instead, we make sure `J` exists, then set it to `I` afterwards.
548 auto &NewValue = ValueState[J];
549 NewValue = ValueState[I];
550 pushToWorkList(NewValue, J);
554 void SCCPInstVisitor::visitInstruction(Instruction &I) {
555 // All the instructions we don't do any special handling for just
556 // go to overdefined.
557 LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n');
561 bool SCCPInstVisitor::mergeInValue(ValueLatticeElement &IV, Value *V,
562 ValueLatticeElement MergeWithV,
563 ValueLatticeElement::MergeOptions Opts) {
564 if (IV.mergeIn(MergeWithV, Opts)) {
565 pushToWorkList(IV, V);
566 LLVM_DEBUG(dbgs() << "Merged " << MergeWithV << " into " << *V << " : "
573 bool SCCPInstVisitor::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
574 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
575 return false; // This edge is already known to be executable!
577 if (!markBlockExecutable(Dest)) {
578 // If the destination is already executable, we just made an *edge*
579 // feasible that wasn't before. Revisit the PHI nodes in the block
580 // because they have potentially new operands.
581 LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
582 << " -> " << Dest->getName() << '\n');
584 for (PHINode &PN : Dest->phis())
590 // getFeasibleSuccessors - Return a vector of booleans to indicate which
591 // successors are reachable from a given terminator instruction.
592 void SCCPInstVisitor::getFeasibleSuccessors(Instruction &TI,
593 SmallVectorImpl<bool> &Succs) {
594 Succs.resize(TI.getNumSuccessors());
595 if (auto *BI = dyn_cast<BranchInst>(&TI)) {
596 if (BI->isUnconditional()) {
601 ValueLatticeElement BCValue = getValueState(BI->getCondition());
602 ConstantInt *CI = getConstantInt(BCValue);
604 // Overdefined condition variables, and branches on unfoldable constant
605 // conditions, mean the branch could go either way.
606 if (!BCValue.isUnknownOrUndef())
607 Succs[0] = Succs[1] = true;
611 // Constant condition variables mean the branch can only go a single way.
612 Succs[CI->isZero()] = true;
616 // Unwinding instructions successors are always executable.
617 if (TI.isExceptionalTerminator()) {
618 Succs.assign(TI.getNumSuccessors(), true);
622 if (auto *SI = dyn_cast<SwitchInst>(&TI)) {
623 if (!SI->getNumCases()) {
627 const ValueLatticeElement &SCValue = getValueState(SI->getCondition());
628 if (ConstantInt *CI = getConstantInt(SCValue)) {
629 Succs[SI->findCaseValue(CI)->getSuccessorIndex()] = true;
633 // TODO: Switch on undef is UB. Stop passing false once the rest of LLVM
635 if (SCValue.isConstantRange(/*UndefAllowed=*/false)) {
636 const ConstantRange &Range = SCValue.getConstantRange();
637 for (const auto &Case : SI->cases()) {
638 const APInt &CaseValue = Case.getCaseValue()->getValue();
639 if (Range.contains(CaseValue))
640 Succs[Case.getSuccessorIndex()] = true;
643 // TODO: Determine whether default case is reachable.
644 Succs[SI->case_default()->getSuccessorIndex()] = true;
648 // Overdefined or unknown condition? All destinations are executable!
649 if (!SCValue.isUnknownOrUndef())
650 Succs.assign(TI.getNumSuccessors(), true);
654 // In case of indirect branch and its address is a blockaddress, we mark
655 // the target as executable.
656 if (auto *IBR = dyn_cast<IndirectBrInst>(&TI)) {
657 // Casts are folded by visitCastInst.
658 ValueLatticeElement IBRValue = getValueState(IBR->getAddress());
659 BlockAddress *Addr = dyn_cast_or_null<BlockAddress>(getConstant(IBRValue));
660 if (!Addr) { // Overdefined or unknown condition?
661 // All destinations are executable!
662 if (!IBRValue.isUnknownOrUndef())
663 Succs.assign(TI.getNumSuccessors(), true);
667 BasicBlock *T = Addr->getBasicBlock();
668 assert(Addr->getFunction() == T->getParent() &&
669 "Block address of a different function ?");
670 for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {
671 // This is the target.
672 if (IBR->getDestination(i) == T) {
678 // If we didn't find our destination in the IBR successor list, then we
679 // have undefined behavior. Its ok to assume no successor is executable.
683 // In case of callbr, we pessimistically assume that all successors are
685 if (isa<CallBrInst>(&TI)) {
686 Succs.assign(TI.getNumSuccessors(), true);
690 LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n');
691 llvm_unreachable("SCCP: Don't know how to handle this terminator!");
694 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
695 // block to the 'To' basic block is currently feasible.
696 bool SCCPInstVisitor::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const {
697 // Check if we've called markEdgeExecutable on the edge yet. (We could
698 // be more aggressive and try to consider edges which haven't been marked
699 // yet, but there isn't any need.)
700 return KnownFeasibleEdges.count(Edge(From, To));
703 // visit Implementations - Something changed in this instruction, either an
704 // operand made a transition, or the instruction is newly executable. Change
705 // the value type of I to reflect these changes if appropriate. This method
706 // makes sure to do the following actions:
708 // 1. If a phi node merges two constants in, and has conflicting value coming
709 // from different branches, or if the PHI node merges in an overdefined
710 // value, then the PHI node becomes overdefined.
711 // 2. If a phi node merges only constants in, and they all agree on value, the
712 // PHI node becomes a constant value equal to that.
713 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
714 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
715 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
716 // 6. If a conditional branch has a value that is constant, make the selected
717 // destination executable
718 // 7. If a conditional branch has a value that is overdefined, make all
719 // successors executable.
720 void SCCPInstVisitor::visitPHINode(PHINode &PN) {
721 // If this PN returns a struct, just mark the result overdefined.
722 // TODO: We could do a lot better than this if code actually uses this.
723 if (PN.getType()->isStructTy())
724 return (void)markOverdefined(&PN);
726 if (getValueState(&PN).isOverdefined())
727 return; // Quick exit
729 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
730 // and slow us down a lot. Just mark them overdefined.
731 if (PN.getNumIncomingValues() > 64)
732 return (void)markOverdefined(&PN);
734 unsigned NumActiveIncoming = 0;
736 // Look at all of the executable operands of the PHI node. If any of them
737 // are overdefined, the PHI becomes overdefined as well. If they are all
738 // constant, and they agree with each other, the PHI becomes the identical
739 // constant. If they are constant and don't agree, the PHI is a constant
740 // range. If there are no executable operands, the PHI remains unknown.
741 ValueLatticeElement PhiState = getValueState(&PN);
742 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
743 if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent()))
746 ValueLatticeElement IV = getValueState(PN.getIncomingValue(i));
747 PhiState.mergeIn(IV);
749 if (PhiState.isOverdefined())
753 // We allow up to 1 range extension per active incoming value and one
754 // additional extension. Note that we manually adjust the number of range
755 // extensions to match the number of active incoming values. This helps to
756 // limit multiple extensions caused by the same incoming value, if other
757 // incoming values are equal.
758 mergeInValue(&PN, PhiState,
759 ValueLatticeElement::MergeOptions().setMaxWidenSteps(
760 NumActiveIncoming + 1));
761 ValueLatticeElement &PhiStateRef = getValueState(&PN);
762 PhiStateRef.setNumRangeExtensions(
763 std::max(NumActiveIncoming, PhiStateRef.getNumRangeExtensions()));
766 void SCCPInstVisitor::visitReturnInst(ReturnInst &I) {
767 if (I.getNumOperands() == 0)
770 Function *F = I.getParent()->getParent();
771 Value *ResultOp = I.getOperand(0);
773 // If we are tracking the return value of this function, merge it in.
774 if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) {
775 auto TFRVI = TrackedRetVals.find(F);
776 if (TFRVI != TrackedRetVals.end()) {
777 mergeInValue(TFRVI->second, F, getValueState(ResultOp));
782 // Handle functions that return multiple values.
783 if (!TrackedMultipleRetVals.empty()) {
784 if (auto *STy = dyn_cast<StructType>(ResultOp->getType()))
785 if (MRVFunctionsTracked.count(F))
786 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
787 mergeInValue(TrackedMultipleRetVals[std::make_pair(F, i)], F,
788 getStructValueState(ResultOp, i));
792 void SCCPInstVisitor::visitTerminator(Instruction &TI) {
793 SmallVector<bool, 16> SuccFeasible;
794 getFeasibleSuccessors(TI, SuccFeasible);
796 BasicBlock *BB = TI.getParent();
798 // Mark all feasible successors executable.
799 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
801 markEdgeExecutable(BB, TI.getSuccessor(i));
804 void SCCPInstVisitor::visitCastInst(CastInst &I) {
805 // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
806 // discover a concrete value later.
807 if (ValueState[&I].isOverdefined())
810 ValueLatticeElement OpSt = getValueState(I.getOperand(0));
811 if (OpSt.isUnknownOrUndef())
814 if (Constant *OpC = getConstant(OpSt)) {
815 // Fold the constant as we build.
816 Constant *C = ConstantFoldCastOperand(I.getOpcode(), OpC, I.getType(), DL);
817 if (isa<UndefValue>(C))
819 // Propagate constant value
821 } else if (I.getDestTy()->isIntegerTy()) {
822 auto &LV = getValueState(&I);
823 ConstantRange OpRange =
824 OpSt.isConstantRange()
825 ? OpSt.getConstantRange()
826 : ConstantRange::getFull(
827 I.getOperand(0)->getType()->getScalarSizeInBits());
829 Type *DestTy = I.getDestTy();
830 // Vectors where all elements have the same known constant range are treated
831 // as a single constant range in the lattice. When bitcasting such vectors,
832 // there is a mis-match between the width of the lattice value (single
833 // constant range) and the original operands (vector). Go to overdefined in
835 if (I.getOpcode() == Instruction::BitCast &&
836 I.getOperand(0)->getType()->isVectorTy() &&
837 OpRange.getBitWidth() < DL.getTypeSizeInBits(DestTy))
838 return (void)markOverdefined(&I);
841 OpRange.castOp(I.getOpcode(), DL.getTypeSizeInBits(DestTy));
842 mergeInValue(LV, &I, ValueLatticeElement::getRange(Res));
847 void SCCPInstVisitor::visitExtractValueInst(ExtractValueInst &EVI) {
848 // If this returns a struct, mark all elements over defined, we don't track
849 // structs in structs.
850 if (EVI.getType()->isStructTy())
851 return (void)markOverdefined(&EVI);
853 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
854 // discover a concrete value later.
855 if (ValueState[&EVI].isOverdefined())
856 return (void)markOverdefined(&EVI);
858 // If this is extracting from more than one level of struct, we don't know.
859 if (EVI.getNumIndices() != 1)
860 return (void)markOverdefined(&EVI);
862 Value *AggVal = EVI.getAggregateOperand();
863 if (AggVal->getType()->isStructTy()) {
864 unsigned i = *EVI.idx_begin();
865 ValueLatticeElement EltVal = getStructValueState(AggVal, i);
866 mergeInValue(getValueState(&EVI), &EVI, EltVal);
868 // Otherwise, must be extracting from an array.
869 return (void)markOverdefined(&EVI);
873 void SCCPInstVisitor::visitInsertValueInst(InsertValueInst &IVI) {
874 auto *STy = dyn_cast<StructType>(IVI.getType());
876 return (void)markOverdefined(&IVI);
878 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
879 // discover a concrete value later.
880 if (isOverdefined(ValueState[&IVI]))
881 return (void)markOverdefined(&IVI);
883 // If this has more than one index, we can't handle it, drive all results to
885 if (IVI.getNumIndices() != 1)
886 return (void)markOverdefined(&IVI);
888 Value *Aggr = IVI.getAggregateOperand();
889 unsigned Idx = *IVI.idx_begin();
891 // Compute the result based on what we're inserting.
892 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
893 // This passes through all values that aren't the inserted element.
895 ValueLatticeElement EltVal = getStructValueState(Aggr, i);
896 mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal);
900 Value *Val = IVI.getInsertedValueOperand();
901 if (Val->getType()->isStructTy())
902 // We don't track structs in structs.
903 markOverdefined(getStructValueState(&IVI, i), &IVI);
905 ValueLatticeElement InVal = getValueState(Val);
906 mergeInValue(getStructValueState(&IVI, i), &IVI, InVal);
911 void SCCPInstVisitor::visitSelectInst(SelectInst &I) {
912 // If this select returns a struct, just mark the result overdefined.
913 // TODO: We could do a lot better than this if code actually uses this.
914 if (I.getType()->isStructTy())
915 return (void)markOverdefined(&I);
917 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
918 // discover a concrete value later.
919 if (ValueState[&I].isOverdefined())
920 return (void)markOverdefined(&I);
922 ValueLatticeElement CondValue = getValueState(I.getCondition());
923 if (CondValue.isUnknownOrUndef())
926 if (ConstantInt *CondCB = getConstantInt(CondValue)) {
927 Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue();
928 mergeInValue(&I, getValueState(OpVal));
932 // Otherwise, the condition is overdefined or a constant we can't evaluate.
933 // See if we can produce something better than overdefined based on the T/F
935 ValueLatticeElement TVal = getValueState(I.getTrueValue());
936 ValueLatticeElement FVal = getValueState(I.getFalseValue());
938 bool Changed = ValueState[&I].mergeIn(TVal);
939 Changed |= ValueState[&I].mergeIn(FVal);
941 pushToWorkListMsg(ValueState[&I], &I);
944 // Handle Unary Operators.
945 void SCCPInstVisitor::visitUnaryOperator(Instruction &I) {
946 ValueLatticeElement V0State = getValueState(I.getOperand(0));
948 ValueLatticeElement &IV = ValueState[&I];
949 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
950 // discover a concrete value later.
951 if (isOverdefined(IV))
952 return (void)markOverdefined(&I);
954 if (isConstant(V0State)) {
955 Constant *C = ConstantExpr::get(I.getOpcode(), getConstant(V0State));
958 if (isa<UndefValue>(C))
960 return (void)markConstant(IV, &I, C);
963 // If something is undef, wait for it to resolve.
964 if (!isOverdefined(V0State))
970 // Handle Binary Operators.
971 void SCCPInstVisitor::visitBinaryOperator(Instruction &I) {
972 ValueLatticeElement V1State = getValueState(I.getOperand(0));
973 ValueLatticeElement V2State = getValueState(I.getOperand(1));
975 ValueLatticeElement &IV = ValueState[&I];
976 if (IV.isOverdefined())
979 // If something is undef, wait for it to resolve.
980 if (V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef())
983 if (V1State.isOverdefined() && V2State.isOverdefined())
984 return (void)markOverdefined(&I);
986 // If either of the operands is a constant, try to fold it to a constant.
987 // TODO: Use information from notconstant better.
988 if ((V1State.isConstant() || V2State.isConstant())) {
989 Value *V1 = isConstant(V1State) ? getConstant(V1State) : I.getOperand(0);
990 Value *V2 = isConstant(V2State) ? getConstant(V2State) : I.getOperand(1);
991 Value *R = SimplifyBinOp(I.getOpcode(), V1, V2, SimplifyQuery(DL));
992 auto *C = dyn_cast_or_null<Constant>(R);
995 if (isa<UndefValue>(C))
997 // Conservatively assume that the result may be based on operands that may
998 // be undef. Note that we use mergeInValue to combine the constant with
999 // the existing lattice value for I, as different constants might be found
1000 // after one of the operands go to overdefined, e.g. due to one operand
1001 // being a special floating value.
1002 ValueLatticeElement NewV;
1003 NewV.markConstant(C, /*MayIncludeUndef=*/true);
1004 return (void)mergeInValue(&I, NewV);
1008 // Only use ranges for binary operators on integers.
1009 if (!I.getType()->isIntegerTy())
1010 return markOverdefined(&I);
1012 // Try to simplify to a constant range.
1013 ConstantRange A = ConstantRange::getFull(I.getType()->getScalarSizeInBits());
1014 ConstantRange B = ConstantRange::getFull(I.getType()->getScalarSizeInBits());
1015 if (V1State.isConstantRange())
1016 A = V1State.getConstantRange();
1017 if (V2State.isConstantRange())
1018 B = V2State.getConstantRange();
1020 ConstantRange R = A.binaryOp(cast<BinaryOperator>(&I)->getOpcode(), B);
1021 mergeInValue(&I, ValueLatticeElement::getRange(R));
1023 // TODO: Currently we do not exploit special values that produce something
1024 // better than overdefined with an overdefined operand for vector or floating
1025 // point types, like and <4 x i32> overdefined, zeroinitializer.
1028 // Handle ICmpInst instruction.
1029 void SCCPInstVisitor::visitCmpInst(CmpInst &I) {
1030 // Do not cache this lookup, getValueState calls later in the function might
1031 // invalidate the reference.
1032 if (isOverdefined(ValueState[&I]))
1033 return (void)markOverdefined(&I);
1035 Value *Op1 = I.getOperand(0);
1036 Value *Op2 = I.getOperand(1);
1038 // For parameters, use ParamState which includes constant range info if
1040 auto V1State = getValueState(Op1);
1041 auto V2State = getValueState(Op2);
1043 Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State);
1045 if (isa<UndefValue>(C))
1047 ValueLatticeElement CV;
1049 mergeInValue(&I, CV);
1053 // If operands are still unknown, wait for it to resolve.
1054 if ((V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef()) &&
1055 !isConstant(ValueState[&I]))
1058 markOverdefined(&I);
1061 // Handle getelementptr instructions. If all operands are constants then we
1062 // can turn this into a getelementptr ConstantExpr.
1063 void SCCPInstVisitor::visitGetElementPtrInst(GetElementPtrInst &I) {
1064 if (isOverdefined(ValueState[&I]))
1065 return (void)markOverdefined(&I);
1067 SmallVector<Constant *, 8> Operands;
1068 Operands.reserve(I.getNumOperands());
1070 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
1071 ValueLatticeElement State = getValueState(I.getOperand(i));
1072 if (State.isUnknownOrUndef())
1073 return; // Operands are not resolved yet.
1075 if (isOverdefined(State))
1076 return (void)markOverdefined(&I);
1078 if (Constant *C = getConstant(State)) {
1079 Operands.push_back(C);
1083 return (void)markOverdefined(&I);
1086 Constant *Ptr = Operands[0];
1087 auto Indices = makeArrayRef(Operands.begin() + 1, Operands.end());
1089 ConstantExpr::getGetElementPtr(I.getSourceElementType(), Ptr, Indices);
1090 if (isa<UndefValue>(C))
1092 markConstant(&I, C);
1095 void SCCPInstVisitor::visitStoreInst(StoreInst &SI) {
1096 // If this store is of a struct, ignore it.
1097 if (SI.getOperand(0)->getType()->isStructTy())
1100 if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1)))
1103 GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1));
1104 auto I = TrackedGlobals.find(GV);
1105 if (I == TrackedGlobals.end())
1108 // Get the value we are storing into the global, then merge it.
1109 mergeInValue(I->second, GV, getValueState(SI.getOperand(0)),
1110 ValueLatticeElement::MergeOptions().setCheckWiden(false));
1111 if (I->second.isOverdefined())
1112 TrackedGlobals.erase(I); // No need to keep tracking this!
1115 static ValueLatticeElement getValueFromMetadata(const Instruction *I) {
1116 if (MDNode *Ranges = I->getMetadata(LLVMContext::MD_range))
1117 if (I->getType()->isIntegerTy())
1118 return ValueLatticeElement::getRange(
1119 getConstantRangeFromMetadata(*Ranges));
1120 if (I->hasMetadata(LLVMContext::MD_nonnull))
1121 return ValueLatticeElement::getNot(
1122 ConstantPointerNull::get(cast<PointerType>(I->getType())));
1123 return ValueLatticeElement::getOverdefined();
1126 // Handle load instructions. If the operand is a constant pointer to a constant
1127 // global, we can replace the load with the loaded constant value!
1128 void SCCPInstVisitor::visitLoadInst(LoadInst &I) {
1129 // If this load is of a struct or the load is volatile, just mark the result
1131 if (I.getType()->isStructTy() || I.isVolatile())
1132 return (void)markOverdefined(&I);
1134 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1135 // discover a concrete value later.
1136 if (ValueState[&I].isOverdefined())
1137 return (void)markOverdefined(&I);
1139 ValueLatticeElement PtrVal = getValueState(I.getOperand(0));
1140 if (PtrVal.isUnknownOrUndef())
1141 return; // The pointer is not resolved yet!
1143 ValueLatticeElement &IV = ValueState[&I];
1145 if (isConstant(PtrVal)) {
1146 Constant *Ptr = getConstant(PtrVal);
1148 // load null is undefined.
1149 if (isa<ConstantPointerNull>(Ptr)) {
1150 if (NullPointerIsDefined(I.getFunction(), I.getPointerAddressSpace()))
1151 return (void)markOverdefined(IV, &I);
1156 // Transform load (constant global) into the value loaded.
1157 if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) {
1158 if (!TrackedGlobals.empty()) {
1159 // If we are tracking this global, merge in the known value for it.
1160 auto It = TrackedGlobals.find(GV);
1161 if (It != TrackedGlobals.end()) {
1162 mergeInValue(IV, &I, It->second, getMaxWidenStepsOpts());
1168 // Transform load from a constant into a constant if possible.
1169 if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL)) {
1170 if (isa<UndefValue>(C))
1172 return (void)markConstant(IV, &I, C);
1176 // Fall back to metadata.
1177 mergeInValue(&I, getValueFromMetadata(&I));
1180 void SCCPInstVisitor::visitCallBase(CallBase &CB) {
1181 handleCallResult(CB);
1182 handleCallArguments(CB);
1185 void SCCPInstVisitor::handleCallOverdefined(CallBase &CB) {
1186 Function *F = CB.getCalledFunction();
1188 // Void return and not tracking callee, just bail.
1189 if (CB.getType()->isVoidTy())
1192 // Always mark struct return as overdefined.
1193 if (CB.getType()->isStructTy())
1194 return (void)markOverdefined(&CB);
1196 // Otherwise, if we have a single return value case, and if the function is
1197 // a declaration, maybe we can constant fold it.
1198 if (F && F->isDeclaration() && canConstantFoldCallTo(&CB, F)) {
1199 SmallVector<Constant *, 8> Operands;
1200 for (const Use &A : CB.args()) {
1201 if (A.get()->getType()->isStructTy())
1202 return markOverdefined(&CB); // Can't handle struct args.
1203 ValueLatticeElement State = getValueState(A);
1205 if (State.isUnknownOrUndef())
1206 return; // Operands are not resolved yet.
1207 if (isOverdefined(State))
1208 return (void)markOverdefined(&CB);
1209 assert(isConstant(State) && "Unknown state!");
1210 Operands.push_back(getConstant(State));
1213 if (isOverdefined(getValueState(&CB)))
1214 return (void)markOverdefined(&CB);
1216 // If we can constant fold this, mark the result of the call as a
1218 if (Constant *C = ConstantFoldCall(&CB, F, Operands, &GetTLI(*F))) {
1220 if (isa<UndefValue>(C))
1222 return (void)markConstant(&CB, C);
1226 // Fall back to metadata.
1227 mergeInValue(&CB, getValueFromMetadata(&CB));
1230 void SCCPInstVisitor::handleCallArguments(CallBase &CB) {
1231 Function *F = CB.getCalledFunction();
1232 // If this is a local function that doesn't have its address taken, mark its
1233 // entry block executable and merge in the actual arguments to the call into
1234 // the formal arguments of the function.
1235 if (!TrackingIncomingArguments.empty() &&
1236 TrackingIncomingArguments.count(F)) {
1237 markBlockExecutable(&F->front());
1239 // Propagate information from this call site into the callee.
1240 auto CAI = CB.arg_begin();
1241 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
1243 // If this argument is byval, and if the function is not readonly, there
1244 // will be an implicit copy formed of the input aggregate.
1245 if (AI->hasByValAttr() && !F->onlyReadsMemory()) {
1246 markOverdefined(&*AI);
1250 if (auto *STy = dyn_cast<StructType>(AI->getType())) {
1251 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1252 ValueLatticeElement CallArg = getStructValueState(*CAI, i);
1253 mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg,
1254 getMaxWidenStepsOpts());
1257 mergeInValue(&*AI, getValueState(*CAI), getMaxWidenStepsOpts());
1262 void SCCPInstVisitor::handleCallResult(CallBase &CB) {
1263 Function *F = CB.getCalledFunction();
1265 if (auto *II = dyn_cast<IntrinsicInst>(&CB)) {
1266 if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
1267 if (ValueState[&CB].isOverdefined())
1270 Value *CopyOf = CB.getOperand(0);
1271 ValueLatticeElement CopyOfVal = getValueState(CopyOf);
1272 const auto *PI = getPredicateInfoFor(&CB);
1273 assert(PI && "Missing predicate info for ssa.copy");
1275 const Optional<PredicateConstraint> &Constraint = PI->getConstraint();
1277 mergeInValue(ValueState[&CB], &CB, CopyOfVal);
1281 CmpInst::Predicate Pred = Constraint->Predicate;
1282 Value *OtherOp = Constraint->OtherOp;
1284 // Wait until OtherOp is resolved.
1285 if (getValueState(OtherOp).isUnknown()) {
1286 addAdditionalUser(OtherOp, &CB);
1290 // TODO: Actually filp MayIncludeUndef for the created range to false,
1291 // once most places in the optimizer respect the branches on
1292 // undef/poison are UB rule. The reason why the new range cannot be
1293 // undef is as follows below:
1294 // The new range is based on a branch condition. That guarantees that
1295 // neither of the compare operands can be undef in the branch targets,
1296 // unless we have conditions that are always true/false (e.g. icmp ule
1297 // i32, %a, i32_max). For the latter overdefined/empty range will be
1298 // inferred, but the branch will get folded accordingly anyways.
1299 bool MayIncludeUndef = !isa<PredicateAssume>(PI);
1301 ValueLatticeElement CondVal = getValueState(OtherOp);
1302 ValueLatticeElement &IV = ValueState[&CB];
1303 if (CondVal.isConstantRange() || CopyOfVal.isConstantRange()) {
1305 ConstantRange::getFull(DL.getTypeSizeInBits(CopyOf->getType()));
1307 // Get the range imposed by the condition.
1308 if (CondVal.isConstantRange())
1309 ImposedCR = ConstantRange::makeAllowedICmpRegion(
1310 Pred, CondVal.getConstantRange());
1312 // Combine range info for the original value with the new range from the
1314 auto CopyOfCR = CopyOfVal.isConstantRange()
1315 ? CopyOfVal.getConstantRange()
1316 : ConstantRange::getFull(
1317 DL.getTypeSizeInBits(CopyOf->getType()));
1318 auto NewCR = ImposedCR.intersectWith(CopyOfCR);
1319 // If the existing information is != x, do not use the information from
1320 // a chained predicate, as the != x information is more likely to be
1321 // helpful in practice.
1322 if (!CopyOfCR.contains(NewCR) && CopyOfCR.getSingleMissingElement())
1325 addAdditionalUser(OtherOp, &CB);
1326 mergeInValue(IV, &CB,
1327 ValueLatticeElement::getRange(NewCR, MayIncludeUndef));
1329 } else if (Pred == CmpInst::ICMP_EQ && CondVal.isConstant()) {
1330 // For non-integer values or integer constant expressions, only
1331 // propagate equal constants.
1332 addAdditionalUser(OtherOp, &CB);
1333 mergeInValue(IV, &CB, CondVal);
1335 } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant() &&
1337 // Propagate inequalities.
1338 addAdditionalUser(OtherOp, &CB);
1339 mergeInValue(IV, &CB,
1340 ValueLatticeElement::getNot(CondVal.getConstant()));
1344 return (void)mergeInValue(IV, &CB, CopyOfVal);
1347 if (ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) {
1348 // Compute result range for intrinsics supported by ConstantRange.
1349 // Do this even if we don't know a range for all operands, as we may
1350 // still know something about the result range, e.g. of abs(x).
1351 SmallVector<ConstantRange, 2> OpRanges;
1352 for (Value *Op : II->args()) {
1353 const ValueLatticeElement &State = getValueState(Op);
1354 if (State.isConstantRange())
1355 OpRanges.push_back(State.getConstantRange());
1358 ConstantRange::getFull(Op->getType()->getScalarSizeInBits()));
1361 ConstantRange Result =
1362 ConstantRange::intrinsic(II->getIntrinsicID(), OpRanges);
1363 return (void)mergeInValue(II, ValueLatticeElement::getRange(Result));
1367 // The common case is that we aren't tracking the callee, either because we
1368 // are not doing interprocedural analysis or the callee is indirect, or is
1369 // external. Handle these cases first.
1370 if (!F || F->isDeclaration())
1371 return handleCallOverdefined(CB);
1373 // If this is a single/zero retval case, see if we're tracking the function.
1374 if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
1375 if (!MRVFunctionsTracked.count(F))
1376 return handleCallOverdefined(CB); // Not tracking this callee.
1378 // If we are tracking this callee, propagate the result of the function
1379 // into this call site.
1380 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1381 mergeInValue(getStructValueState(&CB, i), &CB,
1382 TrackedMultipleRetVals[std::make_pair(F, i)],
1383 getMaxWidenStepsOpts());
1385 auto TFRVI = TrackedRetVals.find(F);
1386 if (TFRVI == TrackedRetVals.end())
1387 return handleCallOverdefined(CB); // Not tracking this callee.
1389 // If so, propagate the return value of the callee into this call result.
1390 mergeInValue(&CB, TFRVI->second, getMaxWidenStepsOpts());
1394 void SCCPInstVisitor::solve() {
1395 // Process the work lists until they are empty!
1396 while (!BBWorkList.empty() || !InstWorkList.empty() ||
1397 !OverdefinedInstWorkList.empty()) {
1398 // Process the overdefined instruction's work list first, which drives other
1399 // things to overdefined more quickly.
1400 while (!OverdefinedInstWorkList.empty()) {
1401 Value *I = OverdefinedInstWorkList.pop_back_val();
1403 LLVM_DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n');
1405 // "I" got into the work list because it either made the transition from
1406 // bottom to constant, or to overdefined.
1408 // Anything on this worklist that is overdefined need not be visited
1409 // since all of its users will have already been marked as overdefined
1410 // Update all of the users of this instruction's value.
1412 markUsersAsChanged(I);
1415 // Process the instruction work list.
1416 while (!InstWorkList.empty()) {
1417 Value *I = InstWorkList.pop_back_val();
1419 LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');
1421 // "I" got into the work list because it made the transition from undef to
1424 // Anything on this worklist that is overdefined need not be visited
1425 // since all of its users will have already been marked as overdefined.
1426 // Update all of the users of this instruction's value.
1428 if (I->getType()->isStructTy() || !getValueState(I).isOverdefined())
1429 markUsersAsChanged(I);
1432 // Process the basic block work list.
1433 while (!BBWorkList.empty()) {
1434 BasicBlock *BB = BBWorkList.pop_back_val();
1436 LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n');
1438 // Notify all instructions in this basic block that they are newly
1445 /// resolvedUndefsIn - While solving the dataflow for a function, we assume
1446 /// that branches on undef values cannot reach any of their successors.
1447 /// However, this is not a safe assumption. After we solve dataflow, this
1448 /// method should be use to handle this. If this returns true, the solver
1449 /// should be rerun.
1451 /// This method handles this by finding an unresolved branch and marking it one
1452 /// of the edges from the block as being feasible, even though the condition
1453 /// doesn't say it would otherwise be. This allows SCCP to find the rest of the
1454 /// CFG and only slightly pessimizes the analysis results (by marking one,
1455 /// potentially infeasible, edge feasible). This cannot usefully modify the
1456 /// constraints on the condition of the branch, as that would impact other users
1459 /// This scan also checks for values that use undefs. It conservatively marks
1460 /// them as overdefined.
1461 bool SCCPInstVisitor::resolvedUndefsIn(Function &F) {
1462 bool MadeChange = false;
1463 for (BasicBlock &BB : F) {
1464 if (!BBExecutable.count(&BB))
1467 for (Instruction &I : BB) {
1468 // Look for instructions which produce undef values.
1469 if (I.getType()->isVoidTy())
1472 if (auto *STy = dyn_cast<StructType>(I.getType())) {
1473 // Only a few things that can be structs matter for undef.
1475 // Tracked calls must never be marked overdefined in resolvedUndefsIn.
1476 if (auto *CB = dyn_cast<CallBase>(&I))
1477 if (Function *F = CB->getCalledFunction())
1478 if (MRVFunctionsTracked.count(F))
1481 // extractvalue and insertvalue don't need to be marked; they are
1482 // tracked as precisely as their operands.
1483 if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I))
1485 // Send the results of everything else to overdefined. We could be
1486 // more precise than this but it isn't worth bothering.
1487 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1488 ValueLatticeElement &LV = getStructValueState(&I, i);
1489 if (LV.isUnknownOrUndef()) {
1490 markOverdefined(LV, &I);
1497 ValueLatticeElement &LV = getValueState(&I);
1498 if (!LV.isUnknownOrUndef())
1501 // There are two reasons a call can have an undef result
1502 // 1. It could be tracked.
1503 // 2. It could be constant-foldable.
1504 // Because of the way we solve return values, tracked calls must
1505 // never be marked overdefined in resolvedUndefsIn.
1506 if (auto *CB = dyn_cast<CallBase>(&I))
1507 if (Function *F = CB->getCalledFunction())
1508 if (TrackedRetVals.count(F))
1511 if (isa<LoadInst>(I)) {
1512 // A load here means one of two things: a load of undef from a global,
1513 // a load from an unknown pointer. Either way, having it return undef
1518 markOverdefined(&I);
1522 // Check to see if we have a branch or switch on an undefined value. If so
1523 // we force the branch to go one way or the other to make the successor
1524 // values live. It doesn't really matter which way we force it.
1525 Instruction *TI = BB.getTerminator();
1526 if (auto *BI = dyn_cast<BranchInst>(TI)) {
1527 if (!BI->isConditional())
1529 if (!getValueState(BI->getCondition()).isUnknownOrUndef())
1532 // If the input to SCCP is actually branch on undef, fix the undef to
1534 if (isa<UndefValue>(BI->getCondition())) {
1535 BI->setCondition(ConstantInt::getFalse(BI->getContext()));
1536 markEdgeExecutable(&BB, TI->getSuccessor(1));
1541 // Otherwise, it is a branch on a symbolic value which is currently
1542 // considered to be undef. Make sure some edge is executable, so a
1543 // branch on "undef" always flows somewhere.
1544 // FIXME: Distinguish between dead code and an LLVM "undef" value.
1545 BasicBlock *DefaultSuccessor = TI->getSuccessor(1);
1546 if (markEdgeExecutable(&BB, DefaultSuccessor))
1552 if (auto *IBR = dyn_cast<IndirectBrInst>(TI)) {
1553 // Indirect branch with no successor ?. Its ok to assume it branches
1555 if (IBR->getNumSuccessors() < 1)
1558 if (!getValueState(IBR->getAddress()).isUnknownOrUndef())
1561 // If the input to SCCP is actually branch on undef, fix the undef to
1562 // the first successor of the indirect branch.
1563 if (isa<UndefValue>(IBR->getAddress())) {
1564 IBR->setAddress(BlockAddress::get(IBR->getSuccessor(0)));
1565 markEdgeExecutable(&BB, IBR->getSuccessor(0));
1570 // Otherwise, it is a branch on a symbolic value which is currently
1571 // considered to be undef. Make sure some edge is executable, so a
1572 // branch on "undef" always flows somewhere.
1573 // FIXME: IndirectBr on "undef" doesn't actually need to go anywhere:
1574 // we can assume the branch has undefined behavior instead.
1575 BasicBlock *DefaultSuccessor = IBR->getSuccessor(0);
1576 if (markEdgeExecutable(&BB, DefaultSuccessor))
1582 if (auto *SI = dyn_cast<SwitchInst>(TI)) {
1583 if (!SI->getNumCases() ||
1584 !getValueState(SI->getCondition()).isUnknownOrUndef())
1587 // If the input to SCCP is actually switch on undef, fix the undef to
1588 // the first constant.
1589 if (isa<UndefValue>(SI->getCondition())) {
1590 SI->setCondition(SI->case_begin()->getCaseValue());
1591 markEdgeExecutable(&BB, SI->case_begin()->getCaseSuccessor());
1596 // Otherwise, it is a branch on a symbolic value which is currently
1597 // considered to be undef. Make sure some edge is executable, so a
1598 // branch on "undef" always flows somewhere.
1599 // FIXME: Distinguish between dead code and an LLVM "undef" value.
1600 BasicBlock *DefaultSuccessor = SI->case_begin()->getCaseSuccessor();
1601 if (markEdgeExecutable(&BB, DefaultSuccessor))
1611 //===----------------------------------------------------------------------===//
1613 // SCCPSolver implementations
1615 SCCPSolver::SCCPSolver(
1616 const DataLayout &DL,
1617 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
1619 : Visitor(new SCCPInstVisitor(DL, std::move(GetTLI), Ctx)) {}
1621 SCCPSolver::~SCCPSolver() {}
1623 void SCCPSolver::addAnalysis(Function &F, AnalysisResultsForFn A) {
1624 return Visitor->addAnalysis(F, std::move(A));
1627 bool SCCPSolver::markBlockExecutable(BasicBlock *BB) {
1628 return Visitor->markBlockExecutable(BB);
1631 const PredicateBase *SCCPSolver::getPredicateInfoFor(Instruction *I) {
1632 return Visitor->getPredicateInfoFor(I);
1635 DomTreeUpdater SCCPSolver::getDTU(Function &F) { return Visitor->getDTU(F); }
1637 void SCCPSolver::trackValueOfGlobalVariable(GlobalVariable *GV) {
1638 Visitor->trackValueOfGlobalVariable(GV);
1641 void SCCPSolver::addTrackedFunction(Function *F) {
1642 Visitor->addTrackedFunction(F);
1645 void SCCPSolver::addToMustPreserveReturnsInFunctions(Function *F) {
1646 Visitor->addToMustPreserveReturnsInFunctions(F);
1649 bool SCCPSolver::mustPreserveReturn(Function *F) {
1650 return Visitor->mustPreserveReturn(F);
1653 void SCCPSolver::addArgumentTrackedFunction(Function *F) {
1654 Visitor->addArgumentTrackedFunction(F);
1657 bool SCCPSolver::isArgumentTrackedFunction(Function *F) {
1658 return Visitor->isArgumentTrackedFunction(F);
1661 void SCCPSolver::solve() { Visitor->solve(); }
1663 bool SCCPSolver::resolvedUndefsIn(Function &F) {
1664 return Visitor->resolvedUndefsIn(F);
1667 bool SCCPSolver::isBlockExecutable(BasicBlock *BB) const {
1668 return Visitor->isBlockExecutable(BB);
1671 bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const {
1672 return Visitor->isEdgeFeasible(From, To);
1675 std::vector<ValueLatticeElement>
1676 SCCPSolver::getStructLatticeValueFor(Value *V) const {
1677 return Visitor->getStructLatticeValueFor(V);
1680 void SCCPSolver::removeLatticeValueFor(Value *V) {
1681 return Visitor->removeLatticeValueFor(V);
1684 const ValueLatticeElement &SCCPSolver::getLatticeValueFor(Value *V) const {
1685 return Visitor->getLatticeValueFor(V);
1688 const MapVector<Function *, ValueLatticeElement> &
1689 SCCPSolver::getTrackedRetVals() {
1690 return Visitor->getTrackedRetVals();
1693 const DenseMap<GlobalVariable *, ValueLatticeElement> &
1694 SCCPSolver::getTrackedGlobals() {
1695 return Visitor->getTrackedGlobals();
1698 const SmallPtrSet<Function *, 16> SCCPSolver::getMRVFunctionsTracked() {
1699 return Visitor->getMRVFunctionsTracked();
1702 void SCCPSolver::markOverdefined(Value *V) { Visitor->markOverdefined(V); }
1704 bool SCCPSolver::isStructLatticeConstant(Function *F, StructType *STy) {
1705 return Visitor->isStructLatticeConstant(F, STy);
1708 Constant *SCCPSolver::getConstant(const ValueLatticeElement &LV) const {
1709 return Visitor->getConstant(LV);
1712 SmallPtrSetImpl<Function *> &SCCPSolver::getArgumentTrackedFunctions() {
1713 return Visitor->getArgumentTrackedFunctions();
1716 void SCCPSolver::markArgInFuncSpecialization(Function *F, Argument *A,
1718 Visitor->markArgInFuncSpecialization(F, A, C);
1721 void SCCPSolver::markFunctionUnreachable(Function *F) {
1722 Visitor->markFunctionUnreachable(F);
1725 void SCCPSolver::visit(Instruction *I) { Visitor->visit(I); }
1727 void SCCPSolver::visitCall(CallInst &I) { Visitor->visitCall(I); }