diff options
Diffstat (limited to 'llvm/lib/Transforms/Scalar/SCCP.cpp')
| -rw-r--r-- | llvm/lib/Transforms/Scalar/SCCP.cpp | 1367 |
1 files changed, 614 insertions, 753 deletions
diff --git a/llvm/lib/Transforms/Scalar/SCCP.cpp b/llvm/lib/Transforms/Scalar/SCCP.cpp index e696ea83a300..5ebd3b71fe78 100644 --- a/llvm/lib/Transforms/Scalar/SCCP.cpp +++ b/llvm/lib/Transforms/Scalar/SCCP.cpp @@ -27,12 +27,13 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/DomTreeUpdater.h" #include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueLattice.h" #include "llvm/Analysis/ValueLatticeUtils.h" #include "llvm/IR/BasicBlock.h" -#include "llvm/IR/CallSite.h" #include "llvm/IR/Constant.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" @@ -67,123 +68,44 @@ using namespace llvm; STATISTIC(NumInstRemoved, "Number of instructions removed"); STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable"); +STATISTIC(NumInstReplaced, + "Number of instructions replaced with (simpler) instruction"); STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP"); STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP"); STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP"); - +STATISTIC( + IPNumInstReplaced, + "Number of instructions replaced with (simpler) instruction by IPSCCP"); + +// The maximum number of range extensions allowed for operations requiring +// widening. +static const unsigned MaxNumRangeExtensions = 10; + +/// Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions. +static ValueLatticeElement::MergeOptions getMaxWidenStepsOpts() { + return ValueLatticeElement::MergeOptions().setMaxWidenSteps( + MaxNumRangeExtensions); +} namespace { -/// LatticeVal class - This class represents the different lattice values that -/// an LLVM value may occupy. It is a simple class with value semantics. -/// -class LatticeVal { - enum LatticeValueTy { - /// unknown - This LLVM Value has no known value yet. - unknown, - - /// constant - This LLVM Value has a specific constant value. - constant, - - /// forcedconstant - This LLVM Value was thought to be undef until - /// ResolvedUndefsIn. This is treated just like 'constant', but if merged - /// with another (different) constant, it goes to overdefined, instead of - /// asserting. - forcedconstant, - - /// overdefined - This instruction is not known to be constant, and we know - /// it has a value. - overdefined - }; - - /// Val: This stores the current lattice value along with the Constant* for - /// the constant if this is a 'constant' or 'forcedconstant' value. - PointerIntPair<Constant *, 2, LatticeValueTy> Val; - - LatticeValueTy getLatticeValue() const { - return Val.getInt(); - } - -public: - LatticeVal() : Val(nullptr, unknown) {} - - bool isUnknown() const { return getLatticeValue() == unknown; } - - bool isConstant() const { - return getLatticeValue() == constant || getLatticeValue() == forcedconstant; - } - - bool isOverdefined() const { return getLatticeValue() == overdefined; } - - Constant *getConstant() const { - assert(isConstant() && "Cannot get the constant of a non-constant!"); - return Val.getPointer(); - } - - /// markOverdefined - Return true if this is a change in status. - bool markOverdefined() { - if (isOverdefined()) - return false; - - Val.setInt(overdefined); - return true; - } - - /// markConstant - Return true if this is a change in status. - bool markConstant(Constant *V) { - if (getLatticeValue() == constant) { // Constant but not forcedconstant. - assert(getConstant() == V && "Marking constant with different value"); - return false; - } - - if (isUnknown()) { - Val.setInt(constant); - assert(V && "Marking constant with NULL"); - Val.setPointer(V); - } else { - assert(getLatticeValue() == forcedconstant && - "Cannot move from overdefined to constant!"); - // Stay at forcedconstant if the constant is the same. - if (V == getConstant()) return false; - - // Otherwise, we go to overdefined. Assumptions made based on the - // forced value are possibly wrong. Assuming this is another constant - // could expose a contradiction. - Val.setInt(overdefined); - } - return true; - } - - /// getConstantInt - If this is a constant with a ConstantInt value, return it - /// otherwise return null. - ConstantInt *getConstantInt() const { - if (isConstant()) - return dyn_cast<ConstantInt>(getConstant()); - return nullptr; - } - - /// getBlockAddress - If this is a constant with a BlockAddress value, return - /// it, otherwise return null. - BlockAddress *getBlockAddress() const { - if (isConstant()) - return dyn_cast<BlockAddress>(getConstant()); - return nullptr; - } - - void markForcedConstant(Constant *V) { - assert(isUnknown() && "Can't force a defined value!"); - Val.setInt(forcedconstant); - Val.setPointer(V); - } +// Helper to check if \p LV is either a constant or a constant +// range with a single element. This should cover exactly the same cases as the +// old ValueLatticeElement::isConstant() and is intended to be used in the +// transition to ValueLatticeElement. +bool isConstant(const ValueLatticeElement &LV) { + return LV.isConstant() || + (LV.isConstantRange() && LV.getConstantRange().isSingleElement()); +} - ValueLatticeElement toValueLattice() const { - if (isOverdefined()) - return ValueLatticeElement::getOverdefined(); - if (isConstant()) - return ValueLatticeElement::get(getConstant()); - return ValueLatticeElement(); - } -}; +// Helper to check if \p LV is either overdefined or a constant range with more +// than a single element. This should cover exactly the same cases as the old +// ValueLatticeElement::isOverdefined() and is intended to be used in the +// transition to ValueLatticeElement. +bool isOverdefined(const ValueLatticeElement &LV) { + return LV.isOverdefined() || + (LV.isConstantRange() && !LV.getConstantRange().isSingleElement()); +} //===----------------------------------------------------------------------===// // @@ -194,28 +116,28 @@ class SCCPSolver : public InstVisitor<SCCPSolver> { const DataLayout &DL; std::function<const TargetLibraryInfo &(Function &)> GetTLI; SmallPtrSet<BasicBlock *, 8> BBExecutable; // The BBs that are executable. - DenseMap<Value *, LatticeVal> ValueState; // The state each value is in. - // The state each parameter is in. - DenseMap<Value *, ValueLatticeElement> ParamState; + DenseMap<Value *, ValueLatticeElement> + ValueState; // The state each value is in. /// StructValueState - This maintains ValueState for values that have /// StructType, for example for formal arguments, calls, insertelement, etc. - DenseMap<std::pair<Value *, unsigned>, LatticeVal> StructValueState; + DenseMap<std::pair<Value *, unsigned>, ValueLatticeElement> StructValueState; /// GlobalValue - If we are tracking any values for the contents of a global /// variable, we keep a mapping from the constant accessor to the element of /// the global, to the currently known value. If the value becomes /// overdefined, it's entry is simply removed from this map. - DenseMap<GlobalVariable *, LatticeVal> TrackedGlobals; + DenseMap<GlobalVariable *, ValueLatticeElement> TrackedGlobals; /// TrackedRetVals - If we are tracking arguments into and the return /// value out of a function, it will have an entry in this map, indicating /// what the known return value for the function is. - MapVector<Function *, LatticeVal> TrackedRetVals; + MapVector<Function *, ValueLatticeElement> TrackedRetVals; /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions /// that return multiple values. - MapVector<std::pair<Function *, unsigned>, LatticeVal> TrackedMultipleRetVals; + MapVector<std::pair<Function *, unsigned>, ValueLatticeElement> + TrackedMultipleRetVals; /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is /// represented here for efficient lookup. @@ -251,6 +173,8 @@ class SCCPSolver : public InstVisitor<SCCPSolver> { DenseMap<Function *, AnalysisResultsForFn> AnalysisResults; DenseMap<Value *, SmallPtrSet<User *, 2>> AdditionalUsers; + LLVMContext &Ctx; + public: void addAnalysis(Function &F, AnalysisResultsForFn A) { AnalysisResults.insert({&F, std::move(A)}); @@ -270,8 +194,9 @@ public: } SCCPSolver(const DataLayout &DL, - std::function<const TargetLibraryInfo &(Function &)> GetTLI) - : DL(DL), GetTLI(std::move(GetTLI)) {} + std::function<const TargetLibraryInfo &(Function &)> GetTLI, + LLVMContext &Ctx) + : DL(DL), GetTLI(std::move(GetTLI)), Ctx(Ctx) {} /// MarkBlockExecutable - This method can be used by clients to mark all of /// the blocks that are known to be intrinsically live in the processed unit. @@ -292,7 +217,7 @@ public: void TrackValueOfGlobalVariable(GlobalVariable *GV) { // We only track the contents of scalar globals. if (GV->getValueType()->isSingleValueType()) { - LatticeVal &IV = TrackedGlobals[GV]; + ValueLatticeElement &IV = TrackedGlobals[GV]; if (!isa<UndefValue>(GV->getInitializer())) IV.markConstant(GV->getInitializer()); } @@ -306,10 +231,10 @@ public: if (auto *STy = dyn_cast<StructType>(F->getReturnType())) { MRVFunctionsTracked.insert(F); for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) - TrackedMultipleRetVals.insert(std::make_pair(std::make_pair(F, i), - LatticeVal())); + TrackedMultipleRetVals.insert( + std::make_pair(std::make_pair(F, i), ValueLatticeElement())); } else - TrackedRetVals.insert(std::make_pair(F, LatticeVal())); + TrackedRetVals.insert(std::make_pair(F, ValueLatticeElement())); } /// AddMustTailCallee - If the SCCP solver finds that this function is called @@ -352,8 +277,8 @@ public: // block to the 'To' basic block is currently feasible. bool isEdgeFeasible(BasicBlock *From, BasicBlock *To); - std::vector<LatticeVal> getStructLatticeValueFor(Value *V) const { - std::vector<LatticeVal> StructValues; + std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const { + std::vector<ValueLatticeElement> StructValues; auto *STy = dyn_cast<StructType>(V->getType()); assert(STy && "getStructLatticeValueFor() can be called only on structs"); for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { @@ -364,23 +289,26 @@ public: return StructValues; } - const LatticeVal &getLatticeValueFor(Value *V) const { + void removeLatticeValueFor(Value *V) { ValueState.erase(V); } + + const ValueLatticeElement &getLatticeValueFor(Value *V) const { assert(!V->getType()->isStructTy() && "Should use getStructLatticeValueFor"); - DenseMap<Value *, LatticeVal>::const_iterator I = ValueState.find(V); + DenseMap<Value *, ValueLatticeElement>::const_iterator I = + ValueState.find(V); assert(I != ValueState.end() && "V not found in ValueState nor Paramstate map!"); return I->second; } /// getTrackedRetVals - Get the inferred return value map. - const MapVector<Function*, LatticeVal> &getTrackedRetVals() { + const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals() { return TrackedRetVals; } /// getTrackedGlobals - Get and return the set of inferred initializers for /// global variables. - const DenseMap<GlobalVariable*, LatticeVal> &getTrackedGlobals() { + const DenseMap<GlobalVariable *, ValueLatticeElement> &getTrackedGlobals() { return TrackedGlobals; } @@ -407,32 +335,59 @@ public: } // isStructLatticeConstant - Return true if all the lattice values - // corresponding to elements of the structure are not overdefined, + // corresponding to elements of the structure are constants, // false otherwise. bool isStructLatticeConstant(Function *F, StructType *STy) { for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { const auto &It = TrackedMultipleRetVals.find(std::make_pair(F, i)); assert(It != TrackedMultipleRetVals.end()); - LatticeVal LV = It->second; - if (LV.isOverdefined()) + ValueLatticeElement LV = It->second; + if (!isConstant(LV)) return false; } return true; } + /// Helper to return a Constant if \p LV is either a constant or a constant + /// range with a single element. + Constant *getConstant(const ValueLatticeElement &LV) const { + if (LV.isConstant()) + return LV.getConstant(); + + if (LV.isConstantRange()) { + auto &CR = LV.getConstantRange(); + if (CR.getSingleElement()) + return ConstantInt::get(Ctx, *CR.getSingleElement()); + } + return nullptr; + } + private: - // pushToWorkList - Helper for markConstant/markForcedConstant/markOverdefined - void pushToWorkList(LatticeVal &IV, Value *V) { + ConstantInt *getConstantInt(const ValueLatticeElement &IV) const { + return dyn_cast_or_null<ConstantInt>(getConstant(IV)); + } + + // pushToWorkList - Helper for markConstant/markOverdefined + void pushToWorkList(ValueLatticeElement &IV, Value *V) { if (IV.isOverdefined()) return OverdefinedInstWorkList.push_back(V); InstWorkList.push_back(V); } + // Helper to push \p V to the worklist, after updating it to \p IV. Also + // prints a debug message with the updated value. + void pushToWorkListMsg(ValueLatticeElement &IV, Value *V) { + LLVM_DEBUG(dbgs() << "updated " << IV << ": " << *V << '\n'); + pushToWorkList(IV, V); + } + // markConstant - Make a value be marked as "constant". If the value // is not already a constant, add it to the instruction work list so that // the users of the instruction are updated later. - bool markConstant(LatticeVal &IV, Value *V, Constant *C) { - if (!IV.markConstant(C)) return false; + bool markConstant(ValueLatticeElement &IV, Value *V, Constant *C, + bool MayIncludeUndef = false) { + if (!IV.markConstant(C, MayIncludeUndef)) + return false; LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n'); pushToWorkList(IV, V); return true; @@ -443,18 +398,10 @@ private: return markConstant(ValueState[V], V, C); } - void markForcedConstant(Value *V, Constant *C) { - assert(!V->getType()->isStructTy() && "structs should use mergeInValue"); - LatticeVal &IV = ValueState[V]; - IV.markForcedConstant(C); - LLVM_DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n'); - pushToWorkList(IV, V); - } - // markOverdefined - Make a value be marked as "overdefined". If the // value is not already overdefined, add it to the overdefined instruction // work list so that the users of the instruction are updated later. - bool markOverdefined(LatticeVal &IV, Value *V) { + bool markOverdefined(ValueLatticeElement &IV, Value *V) { if (!IV.markOverdefined()) return false; LLVM_DEBUG(dbgs() << "markOverdefined: "; @@ -466,71 +413,59 @@ private: return true; } - bool mergeInValue(LatticeVal &IV, Value *V, LatticeVal MergeWithV) { - if (IV.isOverdefined() || MergeWithV.isUnknown()) - return false; // Noop. - if (MergeWithV.isOverdefined()) - return markOverdefined(IV, V); - if (IV.isUnknown()) - return markConstant(IV, V, MergeWithV.getConstant()); - if (IV.getConstant() != MergeWithV.getConstant()) - return markOverdefined(IV, V); + /// Merge \p MergeWithV into \p IV and push \p V to the worklist, if \p IV + /// changes. + bool mergeInValue(ValueLatticeElement &IV, Value *V, + ValueLatticeElement MergeWithV, + ValueLatticeElement::MergeOptions Opts = { + /*MayIncludeUndef=*/false, /*CheckWiden=*/false}) { + if (IV.mergeIn(MergeWithV, Opts)) { + pushToWorkList(IV, V); + LLVM_DEBUG(dbgs() << "Merged " << MergeWithV << " into " << *V << " : " + << IV << "\n"); + return true; + } return false; } - bool mergeInValue(Value *V, LatticeVal MergeWithV) { + bool mergeInValue(Value *V, ValueLatticeElement MergeWithV, + ValueLatticeElement::MergeOptions Opts = { + /*MayIncludeUndef=*/false, /*CheckWiden=*/false}) { assert(!V->getType()->isStructTy() && "non-structs should use markConstant"); - return mergeInValue(ValueState[V], V, MergeWithV); + return mergeInValue(ValueState[V], V, MergeWithV, Opts); } - /// getValueState - Return the LatticeVal object that corresponds to the - /// value. This function handles the case when the value hasn't been seen yet - /// by properly seeding constants etc. - LatticeVal &getValueState(Value *V) { + /// getValueState - Return the ValueLatticeElement object that corresponds to + /// the value. This function handles the case when the value hasn't been seen + /// yet by properly seeding constants etc. + ValueLatticeElement &getValueState(Value *V) { assert(!V->getType()->isStructTy() && "Should use getStructValueState"); - std::pair<DenseMap<Value*, LatticeVal>::iterator, bool> I = - ValueState.insert(std::make_pair(V, LatticeVal())); - LatticeVal &LV = I.first->second; + auto I = ValueState.insert(std::make_pair(V, ValueLatticeElement())); + ValueLatticeElement &LV = I.first->second; if (!I.second) return LV; // Common case, already in the map. - if (auto *C = dyn_cast<Constant>(V)) { - // Undef values remain unknown. - if (!isa<UndefValue>(V)) - LV.markConstant(C); // Constants are constant - } - - // All others are underdefined by default. - return LV; - } - - ValueLatticeElement &getParamState(Value *V) { - assert(!V->getType()->isStructTy() && "Should use getStructValueState"); - - std::pair<DenseMap<Value*, ValueLatticeElement>::iterator, bool> - PI = ParamState.insert(std::make_pair(V, ValueLatticeElement())); - ValueLatticeElement &LV = PI.first->second; - if (PI.second) - LV = getValueState(V).toValueLattice(); + if (auto *C = dyn_cast<Constant>(V)) + LV.markConstant(C); // Constants are constant + // All others are unknown by default. return LV; } - /// getStructValueState - Return the LatticeVal object that corresponds to the - /// value/field pair. This function handles the case when the value hasn't - /// been seen yet by properly seeding constants etc. - LatticeVal &getStructValueState(Value *V, unsigned i) { + /// getStructValueState - Return the ValueLatticeElement object that + /// corresponds to the value/field pair. This function handles the case when + /// the value hasn't been seen yet by properly seeding constants etc. + ValueLatticeElement &getStructValueState(Value *V, unsigned i) { assert(V->getType()->isStructTy() && "Should use getValueState"); assert(i < cast<StructType>(V->getType())->getNumElements() && "Invalid element #"); - std::pair<DenseMap<std::pair<Value*, unsigned>, LatticeVal>::iterator, - bool> I = StructValueState.insert( - std::make_pair(std::make_pair(V, i), LatticeVal())); - LatticeVal &LV = I.first->second; + auto I = StructValueState.insert( + std::make_pair(std::make_pair(V, i), ValueLatticeElement())); + ValueLatticeElement &LV = I.first->second; if (!I.second) return LV; // Common case, already in the map. @@ -589,9 +524,20 @@ private: // Mark I's users as changed, including AdditionalUsers. void markUsersAsChanged(Value *I) { - for (User *U : I->users()) - if (auto *UI = dyn_cast<Instruction>(U)) - OperandChangedState(UI); + // Functions include their arguments in the use-list. Changed function + // values mean that the result of the function changed. We only need to + // update the call sites with the new function result and do not have to + // propagate the call arguments. + if (isa<Function>(I)) { + for (User *U : I->users()) { + if (auto *CB = dyn_cast<CallBase>(U)) + handleCallResult(*CB); + } + } else { + for (User *U : I->users()) + if (auto *UI = dyn_cast<Instruction>(U)) + OperandChangedState(UI); + } auto Iter = AdditionalUsers.find(I); if (Iter != AdditionalUsers.end()) { @@ -600,6 +546,9 @@ private: OperandChangedState(UI); } } + void handleCallOverdefined(CallBase &CB); + void handleCallResult(CallBase &CB); + void handleCallArguments(CallBase &CB); private: friend class InstVisitor<SCCPSolver>; @@ -634,20 +583,20 @@ private: void visitGetElementPtrInst(GetElementPtrInst &I); void visitCallInst (CallInst &I) { - visitCallSite(&I); + visitCallBase(I); } void visitInvokeInst (InvokeInst &II) { - visitCallSite(&II); + visitCallBase(II); visitTerminator(II); } void visitCallBrInst (CallBrInst &CBI) { - visitCallSite(&CBI); + visitCallBase(CBI); visitTerminator(CBI); } - void visitCallSite (CallSite CS); + void visitCallBase (CallBase &CB); void visitResumeInst (ResumeInst &I) { /*returns void*/ } void visitUnreachableInst(UnreachableInst &I) { /*returns void*/ } void visitFenceInst (FenceInst &I) { /*returns void*/ } @@ -673,12 +622,12 @@ void SCCPSolver::getFeasibleSuccessors(Instruction &TI, return; } - LatticeVal BCValue = getValueState(BI->getCondition()); - ConstantInt *CI = BCValue.getConstantInt(); + ValueLatticeElement BCValue = getValueState(BI->getCondition()); + ConstantInt *CI = getConstantInt(BCValue); if (!CI) { // Overdefined condition variables, and branches on unfoldable constant // conditions, mean the branch could go either way. - if (!BCValue.isUnknown()) + if (!BCValue.isUnknownOrUndef()) Succs[0] = Succs[1] = true; return; } @@ -699,12 +648,12 @@ void SCCPSolver::getFeasibleSuccessors(Instruction &TI, Succs[0] = true; return; } - LatticeVal SCValue = getValueState(SI->getCondition()); - ConstantInt *CI = SCValue.getConstantInt(); + ValueLatticeElement SCValue = getValueState(SI->getCondition()); + ConstantInt *CI = getConstantInt(SCValue); if (!CI) { // Overdefined or unknown condition? // All destinations are executable! - if (!SCValue.isUnknown()) + if (!SCValue.isUnknownOrUndef()) Succs.assign(TI.getNumSuccessors(), true); return; } @@ -717,11 +666,11 @@ void SCCPSolver::getFeasibleSuccessors(Instruction &TI, // the target as executable. if (auto *IBR = dyn_cast<IndirectBrInst>(&TI)) { // Casts are folded by visitCastInst. - LatticeVal IBRValue = getValueState(IBR->getAddress()); - BlockAddress *Addr = IBRValue.getBlockAddress(); + ValueLatticeElement IBRValue = getValueState(IBR->getAddress()); + BlockAddress *Addr = dyn_cast_or_null<BlockAddress>(getConstant(IBRValue)); if (!Addr) { // Overdefined or unknown condition? // All destinations are executable! - if (!IBRValue.isUnknown()) + if (!IBRValue.isUnknownOrUndef()) Succs.assign(TI.getNumSuccessors(), true); return; } @@ -786,50 +735,43 @@ void SCCPSolver::visitPHINode(PHINode &PN) { return (void)markOverdefined(&PN); if (getValueState(&PN).isOverdefined()) - return; // Quick exit + return; // Quick exit // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant, // and slow us down a lot. Just mark them overdefined. if (PN.getNumIncomingValues() > 64) return (void)markOverdefined(&PN); + unsigned NumActiveIncoming = 0; + // Look at all of the executable operands of the PHI node. If any of them // are overdefined, the PHI becomes overdefined as well. If they are all // constant, and they agree with each other, the PHI becomes the identical - // constant. If they are constant and don't agree, the PHI is overdefined. - // If there are no executable operands, the PHI remains unknown. - Constant *OperandVal = nullptr; + // constant. If they are constant and don't agree, the PHI is a constant + // range. If there are no executable operands, the PHI remains unknown. + ValueLatticeElement PhiState = getValueState(&PN); for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { - LatticeVal IV = getValueState(PN.getIncomingValue(i)); - if (IV.isUnknown()) continue; // Doesn't influence PHI node. - if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) continue; - if (IV.isOverdefined()) // PHI node becomes overdefined! - return (void)markOverdefined(&PN); - - if (!OperandVal) { // Grab the first value. - OperandVal = IV.getConstant(); - continue; - } - - // There is already a reachable operand. If we conflict with it, - // then the PHI node becomes overdefined. If we agree with it, we - // can continue on. - - // Check to see if there are two different constants merging, if so, the PHI - // node is overdefined. - if (IV.getConstant() != OperandVal) - return (void)markOverdefined(&PN); - } - - // If we exited the loop, this means that the PHI node only has constant - // arguments that agree with each other(and OperandVal is the constant) or - // OperandVal is null because there are no defined incoming arguments. If - // this is the case, the PHI remains unknown. - if (OperandVal) - markConstant(&PN, OperandVal); // Acquire operand value + ValueLatticeElement IV = getValueState(PN.getIncomingValue(i)); + PhiState.mergeIn(IV); + NumActiveIncoming++; + if (PhiState.isOverdefined()) + break; + } + + // We allow up to 1 range extension per active incoming value and one + // additional extension. Note that we manually adjust the number of range + // extensions to match the number of active incoming values. This helps to + // limit multiple extensions caused by the same incoming value, if other + // incoming values are equal. + mergeInValue(&PN, PhiState, + ValueLatticeElement::MergeOptions().setMaxWidenSteps( + NumActiveIncoming + 1)); + ValueLatticeElement &PhiStateRef = getValueState(&PN); + PhiStateRef.setNumRangeExtensions( + std::max(NumActiveIncoming, PhiStateRef.getNumRangeExtensions())); } void SCCPSolver::visitReturnInst(ReturnInst &I) { @@ -840,8 +782,7 @@ void SCCPSolver::visitReturnInst(ReturnInst &I) { // If we are tracking the return value of this function, merge it in. if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) { - MapVector<Function*, LatticeVal>::iterator TFRVI = - TrackedRetVals.find(F); + auto TFRVI = TrackedRetVals.find(F); if (TFRVI != TrackedRetVals.end()) { mergeInValue(TFRVI->second, F, getValueState(ResultOp)); return; @@ -871,18 +812,28 @@ void SCCPSolver::visitTerminator(Instruction &TI) { } void SCCPSolver::visitCastInst(CastInst &I) { - LatticeVal OpSt = getValueState(I.getOperand(0)); - if (OpSt.isOverdefined()) // Inherit overdefinedness of operand - markOverdefined(&I); - else if (OpSt.isConstant()) { + // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would + // discover a concrete value later. + if (ValueState[&I].isOverdefined()) + return; + + ValueLatticeElement OpSt = getValueState(I.getOperand(0)); + if (Constant *OpC = getConstant(OpSt)) { // Fold the constant as we build. - Constant *C = ConstantFoldCastOperand(I.getOpcode(), OpSt.getConstant(), - I.getType(), DL); + Constant *C = ConstantFoldCastOperand(I.getOpcode(), OpC, I.getType(), DL); if (isa<UndefValue>(C)) return; // Propagate constant value markConstant(&I, C); - } + } else if (OpSt.isConstantRange() && I.getDestTy()->isIntegerTy()) { + auto &LV = getValueState(&I); + ConstantRange OpRange = OpSt.getConstantRange(); + Type *DestTy = I.getDestTy(); + ConstantRange Res = + OpRange.castOp(I.getOpcode(), DL.getTypeSizeInBits(DestTy)); + mergeInValue(LV, &I, ValueLatticeElement::getRange(Res)); + } else if (!OpSt.isUnknownOrUndef()) + markOverdefined(&I); } void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { @@ -891,6 +842,11 @@ void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { if (EVI.getType()->isStructTy()) return (void)markOverdefined(&EVI); + // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would + // discover a concrete value later. + if (ValueState[&EVI].isOverdefined()) + return (void)markOverdefined(&EVI); + // If this is extracting from more than one level of struct, we don't know. if (EVI.getNumIndices() != 1) return (void)markOverdefined(&EVI); @@ -898,7 +854,7 @@ void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { Value *AggVal = EVI.getAggregateOperand(); if (AggVal->getType()->isStructTy()) { unsigned i = *EVI.idx_begin(); - LatticeVal EltVal = getStructValueState(AggVal, i); + ValueLatticeElement EltVal = getStructValueState(AggVal, i); mergeInValue(getValueState(&EVI), &EVI, EltVal); } else { // Otherwise, must be extracting from an array. @@ -911,6 +867,11 @@ void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) { if (!STy) return (void)markOverdefined(&IVI); + // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would + // discover a concrete value later. + if (isOverdefined(ValueState[&IVI])) + return (void)markOverdefined(&IVI); + // If this has more than one index, we can't handle it, drive all results to // undef. if (IVI.getNumIndices() != 1) @@ -923,7 +884,7 @@ void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) { for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { // This passes through all values that aren't the inserted element. if (i != Idx) { - LatticeVal EltVal = getStructValueState(Aggr, i); + ValueLatticeElement EltVal = getStructValueState(Aggr, i); mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal); continue; } @@ -933,7 +894,7 @@ void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) { // We don't track structs in structs. markOverdefined(getStructValueState(&IVI, i), &IVI); else { - LatticeVal InVal = getValueState(Val); + ValueLatticeElement InVal = getValueState(Val); mergeInValue(getStructValueState(&IVI, i), &IVI, InVal); } } @@ -945,11 +906,16 @@ void SCCPSolver::visitSelectInst(SelectInst &I) { if (I.getType()->isStructTy()) return (void)markOverdefined(&I); - LatticeVal CondValue = getValueState(I.getCondition()); - if (CondValue.isUnknown()) + // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would + // discover a concrete value later. + if (ValueState[&I].isOverdefined()) + return (void)markOverdefined(&I); + + ValueLatticeElement CondValue = getValueState(I.getCondition()); + if (CondValue.isUnknownOrUndef()) return; - if (ConstantInt *CondCB = CondValue.getConstantInt()) { + if (ConstantInt *CondCB = getConstantInt(CondValue)) { Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue(); mergeInValue(&I, getValueState(OpVal)); return; @@ -958,30 +924,27 @@ void SCCPSolver::visitSelectInst(SelectInst &I) { // Otherwise, the condition is overdefined or a constant we can't evaluate. // See if we can produce something better than overdefined based on the T/F // value. - LatticeVal TVal = getValueState(I.getTrueValue()); - LatticeVal FVal = getValueState(I.getFalseValue()); - - // select ?, C, C -> C. - if (TVal.isConstant() && FVal.isConstant() && - TVal.getConstant() == FVal.getConstant()) - return (void)markConstant(&I, FVal.getConstant()); - - if (TVal.isUnknown()) // select ?, undef, X -> X. - return (void)mergeInValue(&I, FVal); - if (FVal.isUnknown()) // select ?, X, undef -> X. - return (void)mergeInValue(&I, TVal); - markOverdefined(&I); + ValueLatticeElement TVal = getValueState(I.getTrueValue()); + ValueLatticeElement FVal = getValueState(I.getFalseValue()); + + bool Changed = ValueState[&I].mergeIn(TVal); + Changed |= ValueState[&I].mergeIn(FVal); + if (Changed) + pushToWorkListMsg(ValueState[&I], &I); } // Handle Unary Operators. void SCCPSolver::visitUnaryOperator(Instruction &I) { - LatticeVal V0State = getValueState(I.getOperand(0)); + ValueLatticeElement V0State = getValueState(I.getOperand(0)); - LatticeVal &IV = ValueState[&I]; - if (IV.isOverdefined()) return; + ValueLatticeElement &IV = ValueState[&I]; + // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would + // discover a concrete value later. + if (isOverdefined(IV)) + return (void)markOverdefined(&I); - if (V0State.isConstant()) { - Constant *C = ConstantExpr::get(I.getOpcode(), V0State.getConstant()); + if (isConstant(V0State)) { + Constant *C = ConstantExpr::get(I.getOpcode(), getConstant(V0State)); // op Y -> undef. if (isa<UndefValue>(C)) @@ -990,7 +953,7 @@ void SCCPSolver::visitUnaryOperator(Instruction &I) { } // If something is undef, wait for it to resolve. - if (!V0State.isOverdefined()) + if (!isOverdefined(V0State)) return; markOverdefined(&I); @@ -998,101 +961,90 @@ void SCCPSolver::visitUnaryOperator(Instruction &I) { // Handle Binary Operators. void SCCPSolver::visitBinaryOperator(Instruction &I) { - LatticeVal V1State = getValueState(I.getOperand(0)); - LatticeVal V2State = getValueState(I.getOperand(1)); + ValueLatticeElement V1State = getValueState(I.getOperand(0)); + ValueLatticeElement V2State = getValueState(I.getOperand(1)); - LatticeVal &IV = ValueState[&I]; - if (IV.isOverdefined()) return; - - if (V1State.isConstant() && V2State.isConstant()) { - Constant *C = ConstantExpr::get(I.getOpcode(), V1State.getConstant(), - V2State.getConstant()); - // X op Y -> undef. - if (isa<UndefValue>(C)) - return; - return (void)markConstant(IV, &I, C); - } + ValueLatticeElement &IV = ValueState[&I]; + if (IV.isOverdefined()) + return; // If something is undef, wait for it to resolve. - if (!V1State.isOverdefined() && !V2State.isOverdefined()) + if (V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef()) return; - // Otherwise, one of our operands is overdefined. Try to produce something - // better than overdefined with some tricks. - // If this is 0 / Y, it doesn't matter that the second operand is - // overdefined, and we can replace it with zero. - if (I.getOpcode() == Instruction::UDiv || I.getOpcode() == Instruction::SDiv) - if (V1State.isConstant() && V1State.getConstant()->isNullValue()) - return (void)markConstant(IV, &I, V1State.getConstant()); - - // If this is: - // -> AND/MUL with 0 - // -> OR with -1 - // it doesn't matter that the other operand is overdefined. - if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Mul || - I.getOpcode() == Instruction::Or) { - LatticeVal *NonOverdefVal = nullptr; - if (!V1State.isOverdefined()) - NonOverdefVal = &V1State; - else if (!V2State.isOverdefined()) - NonOverdefVal = &V2State; - - if (NonOverdefVal) { - if (NonOverdefVal->isUnknown()) - return; + if (V1State.isOverdefined() && V2State.isOverdefined()) + return (void)markOverdefined(&I); - if (I.getOpcode() == Instruction::And || - I.getOpcode() == Instruction::Mul) { - // X and 0 = 0 - // X * 0 = 0 - if (NonOverdefVal->getConstant()->isNullValue()) - return (void)markConstant(IV, &I, NonOverdefVal->getConstant()); - } else { - // X or -1 = -1 - if (ConstantInt *CI = NonOverdefVal->getConstantInt()) - if (CI->isMinusOne()) - return (void)markConstant(IV, &I, NonOverdefVal->getConstant()); - } + // If either of the operands is a constant, try to fold it to a constant. + // TODO: Use information from notconstant better. + if ((V1State.isConstant() || V2State.isConstant())) { + Value *V1 = isConstant(V1State) ? getConstant(V1State) : I.getOperand(0); + Value *V2 = isConstant(V2State) ? getConstant(V2State) : I.getOperand(1); + Value *R = SimplifyBinOp(I.getOpcode(), V1, V2, SimplifyQuery(DL)); + auto *C = dyn_cast_or_null<Constant>(R); + if (C) { + // X op Y -> undef. + if (isa<UndefValue>(C)) + return; + // Conservatively assume that the result may be based on operands that may + // be undef. Note that we use mergeInValue to combine the constant with + // the existing lattice value for I, as different constants might be found + // after one of the operands go to overdefined, e.g. due to one operand + // being a special floating value. + ValueLatticeElement NewV; + NewV.markConstant(C, /*MayIncludeUndef=*/true); + return (void)mergeInValue(&I, NewV); } } - markOverdefined(&I); + // Only use ranges for binary operators on integers. + if (!I.getType()->isIntegerTy()) + return markOverdefined(&I); + + // Try to simplify to a constant range. + ConstantRange A = ConstantRange::getFull(I.getType()->getScalarSizeInBits()); + ConstantRange B = ConstantRange::getFull(I.getType()->getScalarSizeInBits()); + if (V1State.isConstantRange()) + A = V1State.getConstantRange(); + if (V2State.isConstantRange()) + B = V2State.getConstantRange(); + + ConstantRange R = A.binaryOp(cast<BinaryOperator>(&I)->getOpcode(), B); + mergeInValue(&I, ValueLatticeElement::getRange(R)); + + // TODO: Currently we do not exploit special values that produce something + // better than overdefined with an overdefined operand for vector or floating + // point types, like and <4 x i32> overdefined, zeroinitializer. } // Handle ICmpInst instruction. void SCCPSolver::visitCmpInst(CmpInst &I) { // Do not cache this lookup, getValueState calls later in the function might // invalidate the reference. - if (ValueState[&I].isOverdefined()) return; + if (isOverdefined(ValueState[&I])) + return (void)markOverdefined(&I); Value *Op1 = I.getOperand(0); Value *Op2 = I.getOperand(1); // For parameters, use ParamState which includes constant range info if // available. - auto V1Param = ParamState.find(Op1); - ValueLatticeElement V1State = (V1Param != ParamState.end()) - ? V1Param->second - : getValueState(Op1).toValueLattice(); - - auto V2Param = ParamState.find(Op2); - ValueLatticeElement V2State = V2Param != ParamState.end() - ? V2Param->second - : getValueState(Op2).toValueLattice(); + auto V1State = getValueState(Op1); + auto V2State = getValueState(Op2); Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State); if (C) { if (isa<UndefValue>(C)) return; - LatticeVal CV; + ValueLatticeElement CV; CV.markConstant(C); mergeInValue(&I, CV); return; } // If operands are still unknown, wait for it to resolve. - if (!V1State.isOverdefined() && !V2State.isOverdefined() && - !ValueState[&I].isConstant()) + if ((V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef()) && + !isConstant(ValueState[&I])) return; markOverdefined(&I); @@ -1101,21 +1053,26 @@ void SCCPSolver::visitCmpInst(CmpInst &I) { // Handle getelementptr instructions. If all operands are constants then we // can turn this into a getelementptr ConstantExpr. void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { - if (ValueState[&I].isOverdefined()) return; + if (isOverdefined(ValueState[&I])) + return (void)markOverdefined(&I); SmallVector<Constant*, 8> Operands; Operands.reserve(I.getNumOperands()); for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { - LatticeVal State = getValueState(I.getOperand(i)); - if (State.isUnknown()) + ValueLatticeElement State = getValueState(I.getOperand(i)); + if (State.isUnknownOrUndef()) return; // Operands are not resolved yet. - if (State.isOverdefined()) + if (isOverdefined(State)) return (void)markOverdefined(&I); - assert(State.isConstant() && "Unknown state!"); - Operands.push_back(State.getConstant()); + if (Constant *C = getConstant(State)) { + Operands.push_back(C); + continue; + } + + return (void)markOverdefined(&I); } Constant *Ptr = Operands[0]; @@ -1136,230 +1093,297 @@ void SCCPSolver::visitStoreInst(StoreInst &SI) { return; GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1)); - DenseMap<GlobalVariable*, LatticeVal>::iterator I = TrackedGlobals.find(GV); - if (I == TrackedGlobals.end() || I->second.isOverdefined()) return; + auto I = TrackedGlobals.find(GV); + if (I == TrackedGlobals.end()) + return; // Get the value we are storing into the global, then merge it. - mergeInValue(I->second, GV, getValueState(SI.getOperand(0))); + mergeInValue(I->second, GV, getValueState(SI.getOperand(0)), + ValueLatticeElement::MergeOptions().setCheckWiden(false)); if (I->second.isOverdefined()) TrackedGlobals.erase(I); // No need to keep tracking this! } +static ValueLatticeElement getValueFromMetadata(const Instruction *I) { + if (MDNode *Ranges = I->getMetadata(LLVMContext::MD_range)) + if (I->getType()->isIntegerTy()) + return ValueLatticeElement::getRange( + getConstantRangeFromMetadata(*Ranges)); + // TODO: Also handle MD_nonnull. + return ValueLatticeElement::getOverdefined(); +} + // Handle load instructions. If the operand is a constant pointer to a constant // global, we can replace the load with the loaded constant value! void SCCPSolver::visitLoadInst(LoadInst &I) { - // If this load is of a struct, just mark the result overdefined. - if (I.getType()->isStructTy()) + // If this load is of a struct or the load is volatile, just mark the result + // as overdefined. + if (I.getType()->isStructTy() || I.isVolatile()) return (void)markOverdefined(&I); - LatticeVal PtrVal = getValueState(I.getOperand(0)); - if (PtrVal.isUnknown()) return; // The pointer is not resolved yet! - - LatticeVal &IV = ValueState[&I]; - if (IV.isOverdefined()) return; + // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would + // discover a concrete value later. + if (ValueState[&I].isOverdefined()) + return (void)markOverdefined(&I); - if (!PtrVal.isConstant() || I.isVolatile()) - return (void)markOverdefined(IV, &I); + ValueLatticeElement PtrVal = getValueState(I.getOperand(0)); + if (PtrVal.isUnknownOrUndef()) + return; // The pointer is not resolved yet! - Constant *Ptr = PtrVal.getConstant(); + ValueLatticeElement &IV = ValueState[&I]; - // load null is undefined. - if (isa<ConstantPointerNull>(Ptr)) { - if (NullPointerIsDefined(I.getFunction(), I.getPointerAddressSpace())) - return (void)markOverdefined(IV, &I); - else - return; - } + if (isConstant(PtrVal)) { + Constant *Ptr = getConstant(PtrVal); - // Transform load (constant global) into the value loaded. - if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) { - if (!TrackedGlobals.empty()) { - // If we are tracking this global, merge in the known value for it. - DenseMap<GlobalVariable*, LatticeVal>::iterator It = - TrackedGlobals.find(GV); - if (It != TrackedGlobals.end()) { - mergeInValue(IV, &I, It->second); + // load null is undefined. + if (isa<ConstantPointerNull>(Ptr)) { + if (NullPointerIsDefined(I.getFunction(), I.getPointerAddressSpace())) + return (void)markOverdefined(IV, &I); + else return; + } + + // Transform load (constant global) into the value loaded. + if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) { + if (!TrackedGlobals.empty()) { + // If we are tracking this global, merge in the known value for it. + auto It = TrackedGlobals.find(GV); + if (It != TrackedGlobals.end()) { + mergeInValue(IV, &I, It->second, getMaxWidenStepsOpts()); + return; + } } } - } - // Transform load from a constant into a constant if possible. - if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL)) { - if (isa<UndefValue>(C)) - return; - return (void)markConstant(IV, &I, C); + // Transform load from a constant into a constant if possible. + if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL)) { + if (isa<UndefValue>(C)) + return; + return (void)markConstant(IV, &I, C); + } } - // Otherwise we cannot say for certain what value this load will produce. - // Bail out. - markOverdefined(IV, &I); + // Fall back to metadata. + mergeInValue(&I, getValueFromMetadata(&I)); } -void SCCPSolver::visitCallSite(CallSite CS) { - Function *F = CS.getCalledFunction(); - Instruction *I = CS.getInstruction(); +void SCCPSolver::visitCallBase(CallBase &CB) { + handleCallResult(CB); + handleCallArguments(CB); +} - if (auto *II = dyn_cast<IntrinsicInst>(I)) { - if (II->getIntrinsicID() == Intrinsic::ssa_copy) { - if (ValueState[I].isOverdefined()) +void SCCPSolver::handleCallOverdefined(CallBase &CB) { + Function *F = CB.getCalledFunction(); + + // Void return and not tracking callee, just bail. + if (CB.getType()->isVoidTy()) + return; + + // Always mark struct return as overdefined. + if (CB.getType()->isStructTy()) + return (void)markOverdefined(&CB); + + // Otherwise, if we have a single return value case, and if the function is + // a declaration, maybe we can constant fold it. + if (F && F->isDeclaration() && canConstantFoldCallTo(&CB, F)) { + SmallVector<Constant *, 8> Operands; + for (auto AI = CB.arg_begin(), E = CB.arg_end(); AI != E; ++AI) { + if (AI->get()->getType()->isStructTy()) + return markOverdefined(&CB); // Can't handle struct args. + ValueLatticeElement State = getValueState(*AI); + + if (State.isUnknownOrUndef()) + return; // Operands are not resolved yet. + if (isOverdefined(State)) + return (void)markOverdefined(&CB); + assert(isConstant(State) && "Unknown state!"); + Operands.push_back(getConstant(State)); + } + + if (isOverdefined(getValueState(&CB))) + return (void)markOverdefined(&CB); + + // If we can constant fold this, mark the result of the call as a + // constant. + if (Constant *C = ConstantFoldCall(&CB, F, Operands, &GetTLI(*F))) { + // call -> undef. + if (isa<UndefValue>(C)) return; + return (void)markConstant(&CB, C); + } + } + + // Fall back to metadata. + mergeInValue(&CB, getValueFromMetadata(&CB)); +} + +void SCCPSolver::handleCallArguments(CallBase &CB) { + Function *F = CB.getCalledFunction(); + // If this is a local function that doesn't have its address taken, mark its + // entry block executable and merge in the actual arguments to the call into + // the formal arguments of the function. + if (!TrackingIncomingArguments.empty() && + TrackingIncomingArguments.count(F)) { + MarkBlockExecutable(&F->front()); + + // Propagate information from this call site into the callee. + auto CAI = CB.arg_begin(); + for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; + ++AI, ++CAI) { + // If this argument is byval, and if the function is not readonly, there + // will be an implicit copy formed of the input aggregate. + if (AI->hasByValAttr() && !F->onlyReadsMemory()) { + markOverdefined(&*AI); + continue; + } + + if (auto *STy = dyn_cast<StructType>(AI->getType())) { + for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { + ValueLatticeElement CallArg = getStructValueState(*CAI, i); + mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg, + getMaxWidenStepsOpts()); + } + } else + mergeInValue(&*AI, getValueState(*CAI), getMaxWidenStepsOpts()); + } + } +} + +void SCCPSolver::handleCallResult(CallBase &CB) { + Function *F = CB.getCalledFunction(); - auto *PI = getPredicateInfoFor(I); - if (!PI) + if (auto *II = dyn_cast<IntrinsicInst>(&CB)) { + if (II->getIntrinsicID() == Intrinsic::ssa_copy) { + if (ValueState[&CB].isOverdefined()) return; - Value *CopyOf = I->getOperand(0); - auto *PBranch = dyn_cast<PredicateBranch>(PI); - if (!PBranch) { - mergeInValue(ValueState[I], I, getValueState(CopyOf)); + Value *CopyOf = CB.getOperand(0); + ValueLatticeElement CopyOfVal = getValueState(CopyOf); + auto *PI = getPredicateInfoFor(&CB); + assert(PI && "Missing predicate info for ssa.copy"); + + CmpInst *Cmp; + bool TrueEdge; + if (auto *PBranch = dyn_cast<PredicateBranch>(PI)) { + Cmp = dyn_cast<CmpInst>(PBranch->Condition); + TrueEdge = PBranch->TrueEdge; + } else if (auto *PAssume = dyn_cast<PredicateAssume>(PI)) { + Cmp = dyn_cast<CmpInst>(PAssume->Condition); + TrueEdge = true; + } else { + mergeInValue(ValueState[&CB], &CB, CopyOfVal); return; } - Value *Cond = PBranch->Condition; - // Everything below relies on the condition being a comparison. - auto *Cmp = dyn_cast<CmpInst>(Cond); if (!Cmp) { - mergeInValue(ValueState[I], I, getValueState(CopyOf)); + mergeInValue(ValueState[&CB], &CB, CopyOfVal); return; } + Value *RenamedOp = PI->RenamedOp; Value *CmpOp0 = Cmp->getOperand(0); Value *CmpOp1 = Cmp->getOperand(1); - if (CopyOf != CmpOp0 && CopyOf != CmpOp1) { - mergeInValue(ValueState[I], I, getValueState(CopyOf)); + // Bail out if neither of the operands matches RenamedOp. + if (CmpOp0 != RenamedOp && CmpOp1 != RenamedOp) { + mergeInValue(ValueState[&CB], &CB, getValueState(CopyOf)); return; } - if (CmpOp0 != CopyOf) + auto Pred = Cmp->getPredicate(); + if (CmpOp1 == RenamedOp) { std::swap(CmpOp0, CmpOp1); + Pred = Cmp->getSwappedPredicate(); + } - LatticeVal OriginalVal = getValueState(CopyOf); - LatticeVal EqVal = getValueState(CmpOp1); - LatticeVal &IV = ValueState[I]; - if (PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_EQ) { - addAdditionalUser(CmpOp1, I); - if (OriginalVal.isConstant()) - mergeInValue(IV, I, OriginalVal); - else - mergeInValue(IV, I, EqVal); + // Wait until CmpOp1 is resolved. + if (getValueState(CmpOp1).isUnknown()) { + addAdditionalUser(CmpOp1, &CB); return; } - if (!PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_NE) { - addAdditionalUser(CmpOp1, I); - if (OriginalVal.isConstant()) - mergeInValue(IV, I, OriginalVal); - else - mergeInValue(IV, I, EqVal); + + // The code below relies on PredicateInfo only inserting copies for the + // true branch when the branch condition is an AND and only inserting + // copies for the false branch when the branch condition is an OR. This + // ensures we can intersect the range from the condition with the range of + // CopyOf. + if (!TrueEdge) + Pred = CmpInst::getInversePredicate(Pred); + + ValueLatticeElement CondVal = getValueState(CmpOp1); + ValueLatticeElement &IV = ValueState[&CB]; + if (CondVal.isConstantRange() || CopyOfVal.isConstantRange()) { + auto ImposedCR = + ConstantRange::getFull(DL.getTypeSizeInBits(CopyOf->getType())); + + // Get the range imposed by the condition. + if (CondVal.isConstantRange()) + ImposedCR = ConstantRange::makeAllowedICmpRegion( + Pred, CondVal.getConstantRange()); + + // Combine range info for the original value with the new range from the + // condition. + auto CopyOfCR = CopyOfVal.isConstantRange() + ? CopyOfVal.getConstantRange() + : ConstantRange::getFull( + DL.getTypeSizeInBits(CopyOf->getType())); + auto NewCR = ImposedCR.intersectWith(CopyOfCR); + // If the existing information is != x, do not use the information from + // a chained predicate, as the != x information is more likely to be + // helpful in practice. + if (!CopyOfCR.contains(NewCR) && CopyOfCR.getSingleMissingElement()) + NewCR = CopyOfCR; + + addAdditionalUser(CmpOp1, &CB); + // TODO: Actually filp MayIncludeUndef for the created range to false, + // once most places in the optimizer respect the branches on + // undef/poison are UB rule. The reason why the new range cannot be + // undef is as follows below: + // The new range is based on a branch condition. That guarantees that + // neither of the compare operands can be undef in the branch targets, + // unless we have conditions that are always true/false (e.g. icmp ule + // i32, %a, i32_max). For the latter overdefined/empty range will be + // inferred, but the branch will get folded accordingly anyways. + mergeInValue( + IV, &CB, + ValueLatticeElement::getRange(NewCR, /*MayIncludeUndef=*/true)); + return; + } else if (Pred == CmpInst::ICMP_EQ && CondVal.isConstant()) { + // For non-integer values or integer constant expressions, only + // propagate equal constants. + addAdditionalUser(CmpOp1, &CB); + mergeInValue(IV, &CB, CondVal); return; } - return (void)mergeInValue(IV, I, getValueState(CopyOf)); + return (void)mergeInValue(IV, &CB, CopyOfVal); } } // The common case is that we aren't tracking the callee, either because we // are not doing interprocedural analysis or the callee is indirect, or is // external. Handle these cases first. - if (!F || F->isDeclaration()) { -CallOverdefined: - // Void return and not tracking callee, just bail. - if (I->getType()->isVoidTy()) return; - - // Otherwise, if we have a single return value case, and if the function is - // a declaration, maybe we can constant fold it. - if (F && F->isDeclaration() && !I->getType()->isStructTy() && - canConstantFoldCallTo(cast<CallBase>(CS.getInstruction()), F)) { - SmallVector<Constant*, 8> Operands; - for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); - AI != E; ++AI) { - if (AI->get()->getType()->isStructTy()) - return markOverdefined(I); // Can't handle struct args. - LatticeVal State = getValueState(*AI); - - if (State.isUnknown()) - return; // Operands are not resolved yet. - if (State.isOverdefined()) - return (void)markOverdefined(I); - assert(State.isConstant() && "Unknown state!"); - Operands.push_back(State.getConstant()); - } - - if (getValueState(I).isOverdefined()) - return; - - // If we can constant fold this, mark the result of the call as a - // constant. - if (Constant *C = ConstantFoldCall(cast<CallBase>(CS.getInstruction()), F, - Operands, &GetTLI(*F))) { - // call -> undef. - if (isa<UndefValue>(C)) - return; - return (void)markConstant(I, C); - } - } - - // Otherwise, we don't know anything about this call, mark it overdefined. - return (void)markOverdefined(I); - } - - // If this is a local function that doesn't have its address taken, mark its - // entry block executable and merge in the actual arguments to the call into - // the formal arguments of the function. - if (!TrackingIncomingArguments.empty() && TrackingIncomingArguments.count(F)){ - MarkBlockExecutable(&F->front()); - - // Propagate information from this call site into the callee. - CallSite::arg_iterator CAI = CS.arg_begin(); - for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); - AI != E; ++AI, ++CAI) { - // If this argument is byval, and if the function is not readonly, there - // will be an implicit copy formed of the input aggregate. - if (AI->hasByValAttr() && !F->onlyReadsMemory()) { - markOverdefined(&*AI); - continue; - } - - if (auto *STy = dyn_cast<StructType>(AI->getType())) { - for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { - LatticeVal CallArg = getStructValueState(*CAI, i); - mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg); - } - } else { - // Most other parts of the Solver still only use the simpler value - // lattice, so we propagate changes for parameters to both lattices. - LatticeVal ConcreteArgument = getValueState(*CAI); - bool ParamChanged = - getParamState(&*AI).mergeIn(ConcreteArgument.toValueLattice(), DL); - bool ValueChanged = mergeInValue(&*AI, ConcreteArgument); - // Add argument to work list, if the state of a parameter changes but - // ValueState does not change (because it is already overdefined there), - // We have to take changes in ParamState into account, as it is used - // when evaluating Cmp instructions. - if (!ValueChanged && ParamChanged) - pushToWorkList(ValueState[&*AI], &*AI); - } - } - } + if (!F || F->isDeclaration()) + return handleCallOverdefined(CB); // If this is a single/zero retval case, see if we're tracking the function. if (auto *STy = dyn_cast<StructType>(F->getReturnType())) { if (!MRVFunctionsTracked.count(F)) - goto CallOverdefined; // Not tracking this callee. + return handleCallOverdefined(CB); // Not tracking this callee. // If we are tracking this callee, propagate the result of the function // into this call site. for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) - mergeInValue(getStructValueState(I, i), I, - TrackedMultipleRetVals[std::make_pair(F, i)]); + mergeInValue(getStructValueState(&CB, i), &CB, + TrackedMultipleRetVals[std::make_pair(F, i)], + getMaxWidenStepsOpts()); } else { - MapVector<Function*, LatticeVal>::iterator TFRVI = TrackedRetVals.find(F); + auto TFRVI = TrackedRetVals.find(F); if (TFRVI == TrackedRetVals.end()) - goto CallOverdefined; // Not tracking this callee. + return handleCallOverdefined(CB); // Not tracking this callee. // If so, propagate the return value of the callee into this call result. - mergeInValue(I, TFRVI->second); + mergeInValue(&CB, TFRVI->second, getMaxWidenStepsOpts()); } } @@ -1429,10 +1453,8 @@ void SCCPSolver::Solve() { /// constraints on the condition of the branch, as that would impact other users /// of the value. /// -/// This scan also checks for values that use undefs, whose results are actually -/// defined. For example, 'zext i8 undef to i32' should produce all zeros -/// conservatively, as "(zext i8 X -> i32) & 0xFF00" must always return zero, -/// even if X isn't defined. +/// This scan also checks for values that use undefs. It conservatively marks +/// them as overdefined. bool SCCPSolver::ResolvedUndefsIn(Function &F) { for (BasicBlock &BB : F) { if (!BBExecutable.count(&BB)) @@ -1446,8 +1468,8 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { // Only a few things that can be structs matter for undef. // Tracked calls must never be marked overdefined in ResolvedUndefsIn. - if (CallSite CS = CallSite(&I)) - if (Function *F = CS.getCalledFunction()) + if (auto *CB = dyn_cast<CallBase>(&I)) + if (Function *F = CB->getCalledFunction()) if (MRVFunctionsTracked.count(F)) continue; @@ -1455,19 +1477,18 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { // tracked as precisely as their operands. if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I)) continue; - // Send the results of everything else to overdefined. We could be // more precise than this but it isn't worth bothering. for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { - LatticeVal &LV = getStructValueState(&I, i); - if (LV.isUnknown()) + ValueLatticeElement &LV = getStructValueState(&I, i); + if (LV.isUnknownOrUndef()) markOverdefined(LV, &I); } continue; } - LatticeVal &LV = getValueState(&I); - if (!LV.isUnknown()) + ValueLatticeElement &LV = getValueState(&I); + if (!LV.isUnknownOrUndef()) continue; // There are two reasons a call can have an undef result @@ -1475,195 +1496,20 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { // 2. It could be constant-foldable. // Because of the way we solve return values, tracked calls must // never be marked overdefined in ResolvedUndefsIn. - if (CallSite CS = CallSite(&I)) { - if (Function *F = CS.getCalledFunction()) + if (auto *CB = dyn_cast<CallBase>(&I)) + if (Function *F = CB->getCalledFunction()) if (TrackedRetVals.count(F)) continue; - // If the call is constant-foldable, we mark it overdefined because - // we do not know what return values are valid. - markOverdefined(&I); - return true; - } - - // extractvalue is safe; check here because the argument is a struct. - if (isa<ExtractValueInst>(I)) - continue; - - // Compute the operand LatticeVals, for convenience below. - // Anything taking a struct is conservatively assumed to require - // overdefined markings. - if (I.getOperand(0)->getType()->isStructTy()) { - markOverdefined(&I); - return true; - } - LatticeVal Op0LV = getValueState(I.getOperand(0)); - LatticeVal Op1LV; - if (I.getNumOperands() == 2) { - if (I.getOperand(1)->getType()->isStructTy()) { - markOverdefined(&I); - return true; - } - - Op1LV = getValueState(I.getOperand(1)); - } - // If this is an instructions whose result is defined even if the input is - // not fully defined, propagate the information. - Type *ITy = I.getType(); - switch (I.getOpcode()) { - case Instruction::Add: - case Instruction::Sub: - case Instruction::Trunc: - case Instruction::FPTrunc: - case Instruction::BitCast: - break; // Any undef -> undef - case Instruction::FSub: - case Instruction::FAdd: - case Instruction::FMul: - case Instruction::FDiv: - case Instruction::FRem: - // Floating-point binary operation: be conservative. - if (Op0LV.isUnknown() && Op1LV.isUnknown()) - markForcedConstant(&I, Constant::getNullValue(ITy)); - else - markOverdefined(&I); - return true; - case Instruction::FNeg: - break; // fneg undef -> undef - case Instruction::ZExt: - case Instruction::SExt: - case Instruction::FPToUI: - case Instruction::FPToSI: - case Instruction::FPExt: - case Instruction::PtrToInt: - case Instruction::IntToPtr: - case Instruction::SIToFP: - case Instruction::UIToFP: - // undef -> 0; some outputs are impossible - markForcedConstant(&I, Constant::getNullValue(ITy)); - return true; - case Instruction::Mul: - case Instruction::And: - // Both operands undef -> undef - if (Op0LV.isUnknown() && Op1LV.isUnknown()) - break; - // undef * X -> 0. X could be zero. - // undef & X -> 0. X could be zero. - markForcedConstant(&I, Constant::getNullValue(ITy)); - return true; - case Instruction::Or: - // Both operands undef -> undef - if (Op0LV.isUnknown() && Op1LV.isUnknown()) - break; - // undef | X -> -1. X could be -1. - markForcedConstant(&I, Constant::getAllOnesValue(ITy)); - return true; - case Instruction::Xor: - // undef ^ undef -> 0; strictly speaking, this is not strictly - // necessary, but we try to be nice to people who expect this - // behavior in simple cases - if (Op0LV.isUnknown() && Op1LV.isUnknown()) { - markForcedConstant(&I, Constant::getNullValue(ITy)); - return true; - } - // undef ^ X -> undef - break; - case Instruction::SDiv: - case Instruction::UDiv: - case Instruction::SRem: - case Instruction::URem: - // X / undef -> undef. No change. - // X % undef -> undef. No change. - if (Op1LV.isUnknown()) break; - - // X / 0 -> undef. No change. - // X % 0 -> undef. No change. - if (Op1LV.isConstant() && Op1LV.getConstant()->isZeroValue()) - break; - - // undef / X -> 0. X could be maxint. - // undef % X -> 0. X could be 1. - markForcedConstant(&I, Constant::getNullValue(ITy)); - return true; - case Instruction::AShr: - // X >>a undef -> undef. - if (Op1LV.isUnknown()) break; - - // Shifting by the bitwidth or more is undefined. - if (Op1LV.isConstant()) { - if (auto *ShiftAmt = Op1LV.getConstantInt()) - if (ShiftAmt->getLimitedValue() >= - ShiftAmt->getType()->getScalarSizeInBits()) - break; - } - - // undef >>a X -> 0 - markForcedConstant(&I, Constant::getNullValue(ITy)); - return true; - case Instruction::LShr: - case Instruction::Shl: - // X << undef -> undef. - // X >> undef -> undef. - if (Op1LV.isUnknown()) break; - - // Shifting by the bitwidth or more is undefined. - if (Op1LV.isConstant()) { - if (auto *ShiftAmt = Op1LV.getConstantInt()) - if (ShiftAmt->getLimitedValue() >= - ShiftAmt->getType()->getScalarSizeInBits()) - break; - } - - // undef << X -> 0 - // undef >> X -> 0 - markForcedConstant(&I, Constant::getNullValue(ITy)); - return true; - case Instruction::Select: - Op1LV = getValueState(I.getOperand(1)); - // undef ? X : Y -> X or Y. There could be commonality between X/Y. - if (Op0LV.isUnknown()) { - if (!Op1LV.isConstant()) // Pick the constant one if there is any. - Op1LV = getValueState(I.getOperand(2)); - } else if (Op1LV.isUnknown()) { - // c ? undef : undef -> undef. No change. - Op1LV = getValueState(I.getOperand(2)); - if (Op1LV.isUnknown()) - break; - // Otherwise, c ? undef : x -> x. - } else { - // Leave Op1LV as Operand(1)'s LatticeValue. - } - - if (Op1LV.isConstant()) - markForcedConstant(&I, Op1LV.getConstant()); - else - markOverdefined(&I); - return true; - case Instruction::Load: + if (isa<LoadInst>(I)) { // A load here means one of two things: a load of undef from a global, // a load from an unknown pointer. Either way, having it return undef // is okay. - break; - case Instruction::ICmp: - // X == undef -> undef. Other comparisons get more complicated. - Op0LV = getValueState(I.getOperand(0)); - Op1LV = getValueState(I.getOperand(1)); - - if ((Op0LV.isUnknown() || Op1LV.isUnknown()) && - cast<ICmpInst>(&I)->isEquality()) - break; - markOverdefined(&I); - return true; - case Instruction::Call: - case Instruction::Invoke: - case Instruction::CallBr: - llvm_unreachable("Call-like instructions should have be handled early"); - default: - // If we don't know what should happen here, conservatively mark it - // overdefined. - markOverdefined(&I); - return true; + continue; } + + markOverdefined(&I); + return true; } // Check to see if we have a branch or switch on an undefined value. If so @@ -1672,7 +1518,7 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { Instruction *TI = BB.getTerminator(); if (auto *BI = dyn_cast<BranchInst>(TI)) { if (!BI->isConditional()) continue; - if (!getValueState(BI->getCondition()).isUnknown()) + if (!getValueState(BI->getCondition()).isUnknownOrUndef()) continue; // If the input to SCCP is actually branch on undef, fix the undef to @@ -1700,7 +1546,7 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { if (IBR->getNumSuccessors() < 1) continue; - if (!getValueState(IBR->getAddress()).isUnknown()) + if (!getValueState(IBR->getAddress()).isUnknownOrUndef()) continue; // If the input to SCCP is actually branch on undef, fix the undef to @@ -1724,7 +1570,8 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { } if (auto *SI = dyn_cast<SwitchInst>(TI)) { - if (!SI->getNumCases() || !getValueState(SI->getCondition()).isUnknown()) + if (!SI->getNumCases() || + !getValueState(SI->getCondition()).isUnknownOrUndef()) continue; // If the input to SCCP is actually switch on undef, fix the undef to @@ -1753,25 +1600,26 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) { Constant *Const = nullptr; if (V->getType()->isStructTy()) { - std::vector<LatticeVal> IVs = Solver.getStructLatticeValueFor(V); - if (llvm::any_of(IVs, - [](const LatticeVal &LV) { return LV.isOverdefined(); })) + std::vector<ValueLatticeElement> IVs = Solver.getStructLatticeValueFor(V); + if (any_of(IVs, + [](const ValueLatticeElement &LV) { return isOverdefined(LV); })) return false; std::vector<Constant *> ConstVals; auto *ST = cast<StructType>(V->getType()); for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { - LatticeVal V = IVs[i]; - ConstVals.push_back(V.isConstant() - ? V.getConstant() + ValueLatticeElement V = IVs[i]; + ConstVals.push_back(isConstant(V) + ? Solver.getConstant(V) : UndefValue::get(ST->getElementType(i))); } Const = ConstantStruct::get(ST, ConstVals); } else { - const LatticeVal &IV = Solver.getLatticeValueFor(V); - if (IV.isOverdefined()) + const ValueLatticeElement &IV = Solver.getLatticeValueFor(V); + if (isOverdefined(IV)) return false; - Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(V->getType()); + Const = + isConstant(IV) ? Solver.getConstant(IV) : UndefValue::get(V->getType()); } assert(Const && "Constant is nullptr here!"); @@ -1779,8 +1627,7 @@ static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) { // unless the call itself can be removed CallInst *CI = dyn_cast<CallInst>(V); if (CI && CI->isMustTailCall() && !CI->isSafeToRemove()) { - CallSite CS(CI); - Function *F = CS.getCalledFunction(); + Function *F = CI->getCalledFunction(); // Don't zap returns of the callee if (F) @@ -1798,13 +1645,49 @@ static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) { return true; } +static bool simplifyInstsInBlock(SCCPSolver &Solver, BasicBlock &BB, + SmallPtrSetImpl<Value *> &InsertedValues, + Statistic &InstRemovedStat, + Statistic &InstReplacedStat) { + bool MadeChanges = false; + for (Instruction &Inst : make_early_inc_range(BB)) { + if (Inst.getType()->isVoidTy()) + continue; + if (tryToReplaceWithConstant(Solver, &Inst)) { + if (Inst.isSafeToRemove()) + Inst.eraseFromParent(); + // Hey, we just changed something! + MadeChanges = true; + ++InstRemovedStat; + } else if (isa<SExtInst>(&Inst)) { + Value *ExtOp = Inst.getOperand(0); + if (isa<Constant>(ExtOp) || InsertedValues.count(ExtOp)) + continue; + const ValueLatticeElement &IV = Solver.getLatticeValueFor(ExtOp); + if (!IV.isConstantRange(/*UndefAllowed=*/false)) + continue; + if (IV.getConstantRange().isAllNonNegative()) { + auto *ZExt = new ZExtInst(ExtOp, Inst.getType(), "", &Inst); + InsertedValues.insert(ZExt); + Inst.replaceAllUsesWith(ZExt); + Solver.removeLatticeValueFor(&Inst); + Inst.eraseFromParent(); + InstReplacedStat++; + MadeChanges = true; + } + } + } + return MadeChanges; +} + // runSCCP() - Run the Sparse Conditional Constant Propagation algorithm, // and return true if the function was modified. static bool runSCCP(Function &F, const DataLayout &DL, const TargetLibraryInfo *TLI) { LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n"); SCCPSolver Solver( - DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; }); + DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; }, + F.getContext()); // Mark the first block of the function as being executable. Solver.MarkBlockExecutable(&F.front()); @@ -1827,6 +1710,7 @@ static bool runSCCP(Function &F, const DataLayout &DL, // delete their contents now. Note that we cannot actually delete the blocks, // as we cannot modify the CFG of the function. + SmallPtrSet<Value *, 32> InsertedValues; for (BasicBlock &BB : F) { if (!Solver.isBlockExecutable(&BB)) { LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB); @@ -1838,21 +1722,8 @@ static bool runSCCP(Function &F, const DataLayout &DL, continue; } - // Iterate over all of the instructions in a function, replacing them with - // constants if we have found them to be of constant values. - for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) { - Instruction *Inst = &*BI++; - if (Inst->getType()->isVoidTy() || Inst->isTerminator()) - continue; - - if (tryToReplaceWithConstant(Solver, Inst)) { - if (isInstructionTriviallyDead(Inst)) - Inst->eraseFromParent(); - // Hey, we just changed something! - MadeChanges = true; - ++NumInstRemoved; - } - } + MadeChanges |= simplifyInstsInBlock(Solver, BB, InsertedValues, + NumInstRemoved, NumInstReplaced); } return MadeChanges; @@ -1942,14 +1813,15 @@ static void findReturnsToZap(Function &F, // uses (like blockaddresses) could stuck around, without being // used in the underlying IR, meaning we do not have lattice // values for them. - if (!CallSite(U)) + if (!isa<CallBase>(U)) return true; if (U->getType()->isStructTy()) { - return all_of( - Solver.getStructLatticeValueFor(U), - [](const LatticeVal &LV) { return !LV.isOverdefined(); }); + return all_of(Solver.getStructLatticeValueFor(U), + [](const ValueLatticeElement &LV) { + return !isOverdefined(LV); + }); } - return !Solver.getLatticeValueFor(U).isOverdefined(); + return !isOverdefined(Solver.getLatticeValueFor(U)); }) && "We can only zap functions where all live users have a concrete value"); @@ -2006,7 +1878,7 @@ bool llvm::runIPSCCP( Module &M, const DataLayout &DL, std::function<const TargetLibraryInfo &(Function &)> GetTLI, function_ref<AnalysisResultsForFn(Function &)> getAnalysis) { - SCCPSolver Solver(DL, GetTLI); + SCCPSolver Solver(DL, GetTLI, M.getContext()); // Loop over all functions, marking arguments to those with their addresses // taken or that are external as overdefined. @@ -2080,30 +1952,21 @@ bool llvm::runIPSCCP( } } - for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { - if (!Solver.isBlockExecutable(&*BB)) { - LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << *BB); + SmallPtrSet<Value *, 32> InsertedValues; + for (BasicBlock &BB : F) { + if (!Solver.isBlockExecutable(&BB)) { + LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB); ++NumDeadBlocks; MadeChanges = true; - if (&*BB != &F.front()) - BlocksToErase.push_back(&*BB); + if (&BB != &F.front()) + BlocksToErase.push_back(&BB); continue; } - for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { - Instruction *Inst = &*BI++; - if (Inst->getType()->isVoidTy()) - continue; - if (tryToReplaceWithConstant(Solver, Inst)) { - if (Inst->isSafeToRemove()) - Inst->eraseFromParent(); - // Hey, we just changed something! - MadeChanges = true; - ++IPNumInstRemoved; - } - } + MadeChanges |= simplifyInstsInBlock(Solver, BB, InsertedValues, + IPNumInstRemoved, IPNumInstReplaced); } DomTreeUpdater DTU = Solver.getDTU(F); @@ -2189,10 +2052,9 @@ bool llvm::runIPSCCP( // whether other functions are optimizable. SmallVector<ReturnInst*, 8> ReturnsToZap; - const MapVector<Function*, LatticeVal> &RV = Solver.getTrackedRetVals(); - for (const auto &I : RV) { + for (const auto &I : Solver.getTrackedRetVals()) { Function *F = I.first; - if (I.second.isOverdefined() || F->getReturnType()->isVoidTy()) + if (isOverdefined(I.second) || F->getReturnType()->isVoidTy()) continue; findReturnsToZap(*F, ReturnsToZap, Solver); } @@ -2213,17 +2075,16 @@ bool llvm::runIPSCCP( // If we inferred constant or undef values for globals variables, we can // delete the global and any stores that remain to it. - const DenseMap<GlobalVariable*, LatticeVal> &TG = Solver.getTrackedGlobals(); - for (DenseMap<GlobalVariable*, LatticeVal>::const_iterator I = TG.begin(), - E = TG.end(); I != E; ++I) { - GlobalVariable *GV = I->first; - assert(!I->second.isOverdefined() && - "Overdefined values should have been taken out of the map!"); + for (auto &I : make_early_inc_range(Solver.getTrackedGlobals())) { + GlobalVariable *GV = I.first; + if (isOverdefined(I.second)) + continue; LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName() << "' is constant!\n"); while (!GV->use_empty()) { StoreInst *SI = cast<StoreInst>(GV->user_back()); SI->eraseFromParent(); + MadeChanges = true; } M.getGlobalList().erase(GV); ++IPNumGlobalConst; |