diff --git a/llvm/include/llvm/Analysis/ValueLattice.h b/llvm/include/llvm/Analysis/ValueLattice.h --- a/llvm/include/llvm/Analysis/ValueLattice.h +++ b/llvm/include/llvm/Analysis/ValueLattice.h @@ -36,6 +36,8 @@ /// as constant.) constant, + forcedconstant, + /// This Value is known to not have the specified value. (For constant /// integers, constantrange is used instead. As above, integer typed /// constantexprs can appear here.) @@ -69,6 +71,7 @@ case overdefined: case undefined: case constant: + case forcedconstant: case notconstant: break; case constantrange: @@ -105,6 +108,7 @@ Range = Other.Range; break; case constant: + case forcedconstant: case notconstant: ConstVal = Other.ConstVal; break; @@ -140,13 +144,15 @@ } bool isUndefined() const { return Tag == undefined; } - bool isConstant() const { return Tag == constant; } + bool isConstant() const { return Tag == constant || Tag == forcedconstant; } + bool isForcedConstant() const { return Tag == forcedconstant; } bool isNotConstant() const { return Tag == notconstant; } bool isConstantRange() const { return Tag == constantrange; } bool isOverdefined() const { return Tag == overdefined; } Constant *getConstant() const { - assert(isConstant() && "Cannot get the constant of a non-constant!"); + assert((isConstant() || isForcedConstant()) && + "Cannot get the constant of a non-constant!"); return ConstVal; } @@ -170,68 +176,91 @@ return None; } -private: - void markOverdefined() { + bool markOverdefined() { if (isOverdefined()) - return; + return false; if (isConstant() || isNotConstant()) ConstVal = nullptr; if (isConstantRange()) Range.~ConstantRange(); Tag = overdefined; + return true; } - void markConstant(Constant *V) { + bool markConstant(Constant *V) { + if (isa(V)) + return false; + assert(V && "Marking constant with NULL"); - if (ConstantInt *CI = dyn_cast(V)) { - markConstantRange(ConstantRange(CI->getValue())); - return; + + if (isForcedConstant() && V != getConstant()) + return markOverdefined(); + + if (isConstant()) { + assert(getConstant() == V && "Marking constant with different value"); + return false; } + + if (ConstantInt *CI = dyn_cast(V)) + return markConstantRange(ConstantRange(CI->getValue())); + + assert(isUndefined()); + Tag = constant; + ConstVal = V; + return true; + } + + bool markForcedConstant(Constant *V) { + assert(V && "Marking constant with NULL"); if (isa(V)) - return; + return false; - assert((!isConstant() || getConstant() == V) && + assert((!isForcedConstant() || getConstant() == V) && "Marking constant with different value"); assert(isUndefined()); - Tag = constant; + Tag = forcedconstant; ConstVal = V; + return true; } - void markNotConstant(Constant *V) { + bool markNotConstant(Constant *V) { assert(V && "Marking constant with NULL"); - if (ConstantInt *CI = dyn_cast(V)) { - markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue())); - return; - } + if (ConstantInt *CI = dyn_cast(V)) + return markConstantRange( + ConstantRange(CI->getValue() + 1, CI->getValue())); + if (isa(V)) - return; + return false; + + if (isNotConstant()) { + assert(getNotConstant() == V && "Marking !constant with different value"); + return false; + } - assert((!isConstant() || getConstant() != V) && - "Marking constant !constant with same value"); - assert((!isNotConstant() || getNotConstant() == V) && - "Marking !constant with different value"); - assert(isUndefined() || isConstant()); + assert(isUndefined()); Tag = notconstant; ConstVal = V; + return true; } - void markConstantRange(ConstantRange NewR) { + bool markConstantRange(ConstantRange NewR) { if (isConstantRange()) { if (NewR.isEmptySet()) markOverdefined(); else { + assert(getConstantRange().difference(NewR).isEmptySet()); Range = std::move(NewR); } - return; + return true; } assert(isUndefined()); if (NewR.isEmptySet()) - markOverdefined(); - else { - Tag = constantrange; - new (&Range) ConstantRange(std::move(NewR)); - } + return markOverdefined(); + + Tag = constantrange; + new (&Range) ConstantRange(std::move(NewR)); + return true; } public: @@ -250,6 +279,10 @@ return !RHS.isUndefined(); } + if (isForcedConstant() || RHS.isForcedConstant()) { + markOverdefined(); + return true; + } if (isConstant()) { if (RHS.isConstant() && getConstant() == RHS.getConstant()) return false; @@ -273,18 +306,16 @@ } ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange()); if (NewR.isFullSet()) - markOverdefined(); + return markOverdefined(); else if (NewR == getConstantRange()) return false; else - markConstantRange(std::move(NewR)); - return true; + return markConstantRange(std::move(NewR)); } ConstantInt *getConstantInt() const { - assert(isConstant() && isa(getConstant()) && - "No integer constant"); - return cast(getConstant()); + assert((isConstant() || isForcedConstant()) && "No integer constant"); + return dyn_cast(getConstant()); } /// Compares this symbolic value with Other using Pred and returns either @@ -298,13 +329,22 @@ if (isConstant() && Other.isConstant()) return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant()); - // Integer constants are represented as ConstantRanges with single - // elements. - if (!isConstantRange() || !Other.isConstantRange()) + ConstantRange CR = ConstantRange::getEmpty(1); + if (isConstantRange()) + CR = getConstantRange(); + else if (isConstant() && getConstantInt()) + CR = ConstantRange(getConstantInt()->getValue()); + else + return nullptr; + + ConstantRange OtherCR = ConstantRange::getEmpty(1); + if (Other.isConstantRange()) + OtherCR = Other.getConstantRange(); + else if (Other.isConstant() && Other.getConstantInt()) + OtherCR = ConstantRange(Other.getConstantInt()->getValue()); + else return nullptr; - const auto &CR = getConstantRange(); - const auto &OtherCR = Other.getConstantRange(); if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR)) return ConstantInt::getTrue(Ty); if (ConstantRange::makeSatisfyingICmpRegion( diff --git a/llvm/lib/Analysis/ValueLattice.cpp b/llvm/lib/Analysis/ValueLattice.cpp --- a/llvm/lib/Analysis/ValueLattice.cpp +++ b/llvm/lib/Analysis/ValueLattice.cpp @@ -20,6 +20,8 @@ if (Val.isConstantRange()) return OS << "constantrange<" << Val.getConstantRange().getLower() << ", " << Val.getConstantRange().getUpper() << ">"; + if (Val.isForcedConstant()) + return OS << "forcedconstant<" << *Val.getConstant() << ">"; return OS << "constant<" << *Val.getConstant() << ">"; } } // end namespace llvm diff --git a/llvm/lib/Transforms/Scalar/SCCP.cpp b/llvm/lib/Transforms/Scalar/SCCP.cpp --- a/llvm/lib/Transforms/Scalar/SCCP.cpp +++ b/llvm/lib/Transforms/Scalar/SCCP.cpp @@ -71,117 +71,26 @@ STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP"); 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 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(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(getConstant()); - return nullptr; - } - - void markForcedConstant(Constant *V) { - assert(isUnknown() && "Can't force a defined value!"); - Val.setInt(forcedconstant); - Val.setPointer(V); - } - - ValueLatticeElement toValueLattice() const { - if (isOverdefined()) - return ValueLatticeElement::getOverdefined(); - if (isConstant()) - return ValueLatticeElement::get(getConstant()); - return ValueLatticeElement(); - } -}; +/// Helper to return a Constant if \p IV is either a constant or a constant +/// range with a single element. +static Constant *getConstant(const ValueLatticeElement &IV, Type *T) { + if (IV.isConstant()) { + return IV.getConstant(); + } + if (IV.isConstantRange()) { + auto &CR = IV.getConstantRange(); + if (CR.getSingleElement()) + return ConstantInt::get(T, *CR.getSingleElement()); + } + return nullptr; +} +// +/// Helper to check if \p IV is either a constant or a constant +/// range. +bool isConstant(const ValueLatticeElement &IV) { + return IV.isConstant() || + (IV.isConstantRange() && IV.getConstantRange().isSingleElement()); +} //===----------------------------------------------------------------------===// // @@ -192,28 +101,28 @@ const DataLayout &DL; const TargetLibraryInfo *TLI; SmallPtrSet BBExecutable; // The BBs that are executable. - DenseMap ValueState; // The state each value is in. - // The state each parameter is in. - DenseMap ParamState; + DenseMap + 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, LatticeVal> StructValueState; + DenseMap, 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 TrackedGlobals; + DenseMap 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. - DenseMap TrackedRetVals; + DenseMap TrackedRetVals; /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions /// that return multiple values. - DenseMap, LatticeVal> TrackedMultipleRetVals; + DenseMap, ValueLatticeElement> + TrackedMultipleRetVals; /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is /// represented here for efficient lookup. @@ -289,7 +198,7 @@ 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(GV->getInitializer())) IV.markConstant(GV->getInitializer()); } @@ -303,10 +212,10 @@ if (auto *STy = dyn_cast(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 @@ -349,10 +258,12 @@ // block to the 'To' basic block is currently feasible. bool isEdgeFeasible(BasicBlock *From, BasicBlock *To); - std::vector getStructLatticeValueFor(Value *V) const { - std::vector StructValues; + std::vector + getStructValueLatticeElementFor(Value *V) const { + std::vector StructValues; auto *STy = dyn_cast(V->getType()); - assert(STy && "getStructLatticeValueFor() can be called only on structs"); + assert(STy && + "getStructValueLatticeElementueFor() can be called only on structs"); for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { auto I = StructValueState.find(std::make_pair(V, i)); assert(I != StructValueState.end() && "Value not in valuemap!"); @@ -361,23 +272,23 @@ return StructValues; } - const LatticeVal &getLatticeValueFor(Value *V) const { + ValueLatticeElement &getValueLatticeElementFor(Value *V) { assert(!V->getType()->isStructTy() && - "Should use getStructLatticeValueFor"); - DenseMap::const_iterator I = ValueState.find(V); + "Should use getStructValueLatticeElementueFor"); + DenseMap::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 DenseMap &getTrackedRetVals() { + const DenseMap &getTrackedRetVals() { return TrackedRetVals; } /// getTrackedGlobals - Get and return the set of inferred initializers for /// global variables. - const DenseMap &getTrackedGlobals() { + const DenseMap &getTrackedGlobals() { return TrackedGlobals; } @@ -410,16 +321,36 @@ 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; } private: + ConstantInt *getConstantInt(const ValueLatticeElement &IV, Value *V) const { + if (IV.isConstant() || IV.isForcedConstant()) + return IV.getConstantInt(); + + if (IV.isConstantRange()) { + auto &CR = IV.getConstantRange(); + if (CR.getSingleElement()) + return ConstantInt::get(V->getContext(), *CR.getSingleElement()); + } + return nullptr; + } // pushToWorkList - Helper for markConstant/markForcedConstant/markOverdefined - void pushToWorkList(LatticeVal &IV, Value *V) { + 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'); if (IV.isOverdefined()) return OverdefinedInstWorkList.push_back(V); InstWorkList.push_back(V); @@ -428,7 +359,7 @@ // 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) { + bool markConstant(ValueLatticeElement &IV, Value *V, Constant *C) { if (!IV.markConstant(C)) return false; LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n'); pushToWorkList(IV, V); @@ -442,7 +373,7 @@ void markForcedConstant(Value *V, Constant *C) { assert(!V->getType()->isStructTy() && "structs should use mergeInValue"); - LatticeVal &IV = ValueState[V]; + ValueLatticeElement &IV = ValueState[V]; IV.markForcedConstant(C); LLVM_DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n'); pushToWorkList(IV, V); @@ -451,7 +382,7 @@ // 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: "; @@ -463,33 +394,32 @@ 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); + bool mergeInValue(ValueLatticeElement &IV, Value *V, + ValueLatticeElement MergeWithV) { + if (IV.mergeIn(MergeWithV, DL)) { + 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) { assert(!V->getType()->isStructTy() && "non-structs should use markConstant"); return mergeInValue(ValueState[V], V, MergeWithV); } - /// 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::iterator, bool> I = - ValueState.insert(std::make_pair(V, LatticeVal())); - LatticeVal &LV = I.first->second; + std::pair::iterator, bool> I = + ValueState.insert(std::make_pair(V, ValueLatticeElement())); + ValueLatticeElement &LV = I.first->second; if (!I.second) return LV; // Common case, already in the map. @@ -504,30 +434,20 @@ return LV; } - ValueLatticeElement &getParamState(Value *V) { - assert(!V->getType()->isStructTy() && "Should use getStructValueState"); - - std::pair::iterator, bool> - PI = ParamState.insert(std::make_pair(V, ValueLatticeElement())); - ValueLatticeElement &LV = PI.first->second; - if (PI.second) - LV = getValueState(V).toValueLattice(); - - 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(V->getType())->getNumElements() && "Invalid element #"); - std::pair, LatticeVal>::iterator, - bool> I = StructValueState.insert( - std::make_pair(std::make_pair(V, i), LatticeVal())); - LatticeVal &LV = I.first->second; + std::pair< + DenseMap, ValueLatticeElement>::iterator, + bool> + 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. @@ -669,12 +589,12 @@ return; } - LatticeVal BCValue = getValueState(BI->getCondition()); - ConstantInt *CI = BCValue.getConstantInt(); + ValueLatticeElement BCValue = getValueState(BI->getCondition()); + ConstantInt *CI = getConstantInt(BCValue, BI->getCondition()); if (!CI) { // Overdefined condition variables, and branches on unfoldable constant // conditions, mean the branch could go either way. - if (!BCValue.isUnknown()) + if (!BCValue.isUndefined()) Succs[0] = Succs[1] = true; return; } @@ -695,12 +615,12 @@ Succs[0] = true; return; } - LatticeVal SCValue = getValueState(SI->getCondition()); - ConstantInt *CI = SCValue.getConstantInt(); + ValueLatticeElement SCValue = getValueState(SI->getCondition()); + ConstantInt *CI = getConstantInt(SCValue, SI->getCondition()); if (!CI) { // Overdefined or unknown condition? // All destinations are executable! - if (!SCValue.isUnknown()) + if (!SCValue.isUndefined()) Succs.assign(TI.getNumSuccessors(), true); return; } @@ -713,11 +633,13 @@ // the target as executable. if (auto *IBR = dyn_cast(&TI)) { // Casts are folded by visitCastInst. - LatticeVal IBRValue = getValueState(IBR->getAddress()); - BlockAddress *Addr = IBRValue.getBlockAddress(); + ValueLatticeElement IBRValue = getValueState(IBR->getAddress()); + BlockAddress *Addr = IBRValue.isConstant() + ? dyn_cast(IBRValue.getConstant()) + : nullptr; if (!Addr) { // Overdefined or unknown condition? // All destinations are executable! - if (!IBRValue.isUnknown()) + if (!IBRValue.isUndefined()) Succs.assign(TI.getNumSuccessors(), true); return; } @@ -794,38 +716,23 @@ // 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; + bool Changed = false; 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. + ValueLatticeElement IV = getValueState(PN.getIncomingValue(i)); + if (IV.isUndefined()) + 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); + ValueLatticeElement &Res = getValueState(&PN); + Changed |= Res.mergeIn(IV, DL); - 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 (Res.isOverdefined()) + break; } - - // 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 + if (Changed) + pushToWorkListMsg(ValueState[&PN], &PN); } void SCCPSolver::visitReturnInst(ReturnInst &I) { @@ -836,8 +743,8 @@ // If we are tracking the return value of this function, merge it in. if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) { - DenseMap::iterator TFRVI = - TrackedRetVals.find(F); + DenseMap::iterator TFRVI = + TrackedRetVals.find(F); if (TFRVI != TrackedRetVals.end()) { mergeInValue(TFRVI->second, F, getValueState(ResultOp)); return; @@ -867,18 +774,16 @@ } void SCCPSolver::visitCastInst(CastInst &I) { - LatticeVal OpSt = getValueState(I.getOperand(0)); - if (OpSt.isOverdefined()) // Inherit overdefinedness of operand - markOverdefined(&I); - else if (OpSt.isConstant()) { + ValueLatticeElement OpSt = getValueState(I.getOperand(0)); + if (Constant *OpC = getConstant(OpSt, I.getOperand(0)->getType())) { // 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(C)) return; // Propagate constant value markConstant(&I, C); - } + } else if (!OpSt.isUndefined()) + markOverdefined(&I); } void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { @@ -894,7 +799,7 @@ 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. @@ -919,7 +824,7 @@ 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; } @@ -929,7 +834,7 @@ // 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); } } @@ -941,11 +846,11 @@ if (I.getType()->isStructTy()) return (void)markOverdefined(&I); - LatticeVal CondValue = getValueState(I.getCondition()); - if (CondValue.isUnknown()) + ValueLatticeElement CondValue = getValueState(I.getCondition()); + if (CondValue.isUndefined()) return; - if (ConstantInt *CondCB = CondValue.getConstantInt()) { + if (ConstantInt *CondCB = getConstantInt(CondValue, &I)) { Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue(); mergeInValue(&I, getValueState(OpVal)); return; @@ -954,30 +859,68 @@ // 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, DL); + Changed |= ValueState[&I].mergeIn(FVal, DL); + if (Changed) + pushToWorkListMsg(ValueState[&I], &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]; + ValueLatticeElement &IV = ValueState[&I]; if (IV.isOverdefined()) return; - if (V1State.isConstant() && V2State.isConstant()) { + // If something is undef, wait for it to resolve. + if (V1State.isUndefined() || V2State.isUndefined()) + return; + + // TODO: could do better than that in some cases. + if (V1State.isNotConstant() || V2State.isNotConstant()) + return (void)markOverdefined(&I); + + if (V1State.isOverdefined() && V2State.isOverdefined()) + return (void)markOverdefined(&I); + + if (isConstant(V1State) && isConstant(V2State)) { + Constant *C = ConstantExpr::get( + I.getOpcode(), getConstant(V1State, I.getOperand(0)->getType()), + getConstant(V2State, I.getOperand(1)->getType())); + if (isa(C)) + return; + return (void)markConstant(IV, &I, C); + } + + if (!V1State.isOverdefined() && !V2State.isOverdefined()) { + // Deal with operands that are ranges. + if (V1State.isConstantRange() || V2State.isConstantRange()) { + 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(&I)->getOpcode(), B); + + // Very simple widening. If we set a range twice, go to overdefined. + if (!IV.isConstantRange() || IV.getConstantRange() == R) + mergeInValue(&I, ValueLatticeElement::getRange(R)); + else + markOverdefined(&I); + return; + } + + // Deal with non-integer constants. + assert(V1State.isConstant() && V2State.isConstant() && + "Non-constants should be handled elsewhere"); Constant *C = ConstantExpr::get(I.getOpcode(), V1State.getConstant(), V2State.getConstant()); // X op Y -> undef. @@ -986,17 +929,14 @@ return (void)markConstant(IV, &I, C); } - // If something is undef, wait for it to resolve. - if (!V1State.isOverdefined() && !V2State.isOverdefined()) - 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 (Constant *C = getConstant(V1State, I.getOperand(0)->getType())) + if (C->isNullValue()) + return (void)mergeInValue(&I, ValueLatticeElement::get(C)); // If this is: // -> AND/MUL with 0 @@ -1004,27 +944,28 @@ // 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()) + ValueLatticeElement *NonOverdefVal = nullptr; + if (isConstant(V1State)) NonOverdefVal = &V1State; - else if (!V2State.isOverdefined()) + else if (isConstant(V2State)) NonOverdefVal = &V2State; if (NonOverdefVal) { - if (NonOverdefVal->isUnknown()) + Constant *CNonOver = getConstant(*NonOverdefVal, I.getType()); + if (NonOverdefVal->isUndefined() || !CNonOver) return; 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()); + if (getConstant(*NonOverdefVal, I.getType())->isNullValue()) + return (void)mergeInValue(&I, *NonOverdefVal); } else { // X or -1 = -1 - if (ConstantInt *CI = NonOverdefVal->getConstantInt()) + if (ConstantInt *CI = getConstantInt(*NonOverdefVal, &I)) if (CI->isMinusOne()) - return (void)markConstant(IV, &I, NonOverdefVal->getConstant()); + return (void)mergeInValue(&I, *NonOverdefVal); } } } @@ -1041,33 +982,24 @@ 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(); + ValueLatticeElement V1State = getValueState(Op1); - auto V2Param = ParamState.find(Op2); - ValueLatticeElement V2State = V2Param != ParamState.end() - ? V2Param->second - : getValueState(Op2).toValueLattice(); + ValueLatticeElement V2State = getValueState(Op2); + + // If operands are still unknown, wait for it to resolve. + if ((V1State.isUndefined() || V2State.isUndefined())) + return; Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State); if (C) { if (isa(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()) - return; - markOverdefined(&I); } @@ -1080,15 +1012,19 @@ 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.isUndefined()) return; // Operands are not resolved yet. if (State.isOverdefined()) return (void)markOverdefined(&I); - assert(State.isConstant() && "Unknown state!"); - Operands.push_back(State.getConstant()); + if (Constant *C = getConstant(State, I.getOperand(i)->getType())) { + Operands.push_back(C); + continue; + } + + return (void)markOverdefined(&I); } Constant *Ptr = Operands[0]; @@ -1097,7 +1033,7 @@ ConstantExpr::getGetElementPtr(I.getSourceElementType(), Ptr, Indices); if (isa(C)) return; - markConstant(&I, C); + mergeInValue(&I, ValueLatticeElement::get(C)); } void SCCPSolver::visitStoreInst(StoreInst &SI) { @@ -1109,8 +1045,10 @@ return; GlobalVariable *GV = cast(SI.getOperand(1)); - DenseMap::iterator I = TrackedGlobals.find(GV); - if (I == TrackedGlobals.end() || I->second.isOverdefined()) return; + DenseMap::iterator 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))); @@ -1125,16 +1063,17 @@ if (I.getType()->isStructTy()) return (void)markOverdefined(&I); - LatticeVal PtrVal = getValueState(I.getOperand(0)); - if (PtrVal.isUnknown()) return; // The pointer is not resolved yet! + ValueLatticeElement PtrVal = getValueState(I.getOperand(0)); + if (PtrVal.isUndefined()) + return; // The pointer is not resolved yet! - LatticeVal &IV = ValueState[&I]; + ValueLatticeElement &IV = ValueState[&I]; if (IV.isOverdefined()) return; - if (!PtrVal.isConstant() || I.isVolatile()) + if (!isConstant(PtrVal) || I.isVolatile()) return (void)markOverdefined(IV, &I); - Constant *Ptr = PtrVal.getConstant(); + Constant *Ptr = getConstant(PtrVal, I.getType()); // load null is undefined. if (isa(Ptr)) { @@ -1148,10 +1087,10 @@ if (auto *GV = dyn_cast(Ptr)) { if (!TrackedGlobals.empty()) { // If we are tracking this global, merge in the known value for it. - DenseMap::iterator It = - TrackedGlobals.find(GV); + DenseMap::iterator It = + TrackedGlobals.find(GV); if (It != TrackedGlobals.end()) { - mergeInValue(IV, &I, It->second); + mergeInValue(&I, It->second); return; } } @@ -1208,9 +1147,9 @@ if (CmpOp0 != CopyOf) std::swap(CmpOp0, CmpOp1); - LatticeVal OriginalVal = getValueState(CopyOf); - LatticeVal EqVal = getValueState(CmpOp1); - LatticeVal &IV = ValueState[I]; + ValueLatticeElement OriginalVal = getValueState(CopyOf); + ValueLatticeElement EqVal = getValueState(CmpOp1); + ValueLatticeElement &IV = ValueState[I]; if (PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_EQ) { addAdditionalUser(CmpOp1, I); if (OriginalVal.isConstant()) @@ -1249,14 +1188,13 @@ AI != E; ++AI) { if (AI->get()->getType()->isStructTy()) return markOverdefined(I); // Can't handle struct args. - LatticeVal State = getValueState(*AI); + ValueLatticeElement State = getValueState(*AI); - if (State.isUnknown()) + if (State.isUndefined()) return; // Operands are not resolved yet. - if (State.isOverdefined()) + if (!isConstant(State)) return (void)markOverdefined(I); - assert(State.isConstant() && "Unknown state!"); - Operands.push_back(State.getConstant()); + Operands.push_back(getConstant(State, (*AI)->getType())); } if (getValueState(I).isOverdefined()) @@ -1296,22 +1234,13 @@ if (auto *STy = dyn_cast(AI->getType())) { for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { - LatticeVal CallArg = getStructValueState(*CAI, i); + ValueLatticeElement 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); + ValueLatticeElement ConcreteArgument = getValueState(*CAI); + // dbgs() << "Concrete " << ConcreteArgument << "\n"; + mergeInValue(&*AI, ConcreteArgument); } } } @@ -1327,7 +1256,8 @@ mergeInValue(getStructValueState(I, i), I, TrackedMultipleRetVals[std::make_pair(F, i)]); } else { - DenseMap::iterator TFRVI = TrackedRetVals.find(F); + DenseMap::iterator TFRVI = + TrackedRetVals.find(F); if (TFRVI == TrackedRetVals.end()) goto CallOverdefined; // Not tracking this callee. @@ -1432,29 +1362,31 @@ // 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.isUndefined()) markOverdefined(LV, &I); } continue; } - LatticeVal &LV = getValueState(&I); - if (!LV.isUnknown()) continue; + ValueLatticeElement &LV = getValueState(&I); + if (!LV.isUndefined()) + continue; // extractvalue is safe; check here because the argument is a struct. if (isa(I)) continue; - // Compute the operand LatticeVals, for convenience below. + // Compute the operand ValueLatticeElements, 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; + ValueLatticeElement Op0LV = getValueState(I.getOperand(0)); + ValueLatticeElement Op1LV; + Constant *C1 = nullptr; if (I.getNumOperands() == 2) { if (I.getOperand(1)->getType()->isStructTy()) { markOverdefined(&I); @@ -1462,7 +1394,9 @@ } Op1LV = getValueState(I.getOperand(1)); + C1 = getConstant(Op1LV, I.getOperand(1)->getType()); } + // If this is an instructions whose result is defined even if the input is // not fully defined, propagate the information. Type *ITy = I.getType(); @@ -1479,7 +1413,7 @@ case Instruction::FDiv: case Instruction::FRem: // Floating-point binary operation: be conservative. - if (Op0LV.isUnknown() && Op1LV.isUnknown()) + if (Op0LV.isUndefined() && Op1LV.isUndefined()) markForcedConstant(&I, Constant::getNullValue(ITy)); else markOverdefined(&I); @@ -1499,7 +1433,7 @@ case Instruction::Mul: case Instruction::And: // Both operands undef -> undef - if (Op0LV.isUnknown() && Op1LV.isUnknown()) + if (Op0LV.isUndefined() && Op1LV.isUndefined()) break; // undef * X -> 0. X could be zero. // undef & X -> 0. X could be zero. @@ -1507,7 +1441,7 @@ return true; case Instruction::Or: // Both operands undef -> undef - if (Op0LV.isUnknown() && Op1LV.isUnknown()) + if (Op0LV.isUndefined() && Op1LV.isUndefined()) break; // undef | X -> -1. X could be -1. markForcedConstant(&I, Constant::getAllOnesValue(ITy)); @@ -1516,7 +1450,7 @@ // 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()) { + if (Op0LV.isUndefined() && Op1LV.isUndefined()) { markForcedConstant(&I, Constant::getNullValue(ITy)); return true; } @@ -1528,11 +1462,12 @@ case Instruction::URem: // X / undef -> undef. No change. // X % undef -> undef. No change. - if (Op1LV.isUnknown()) break; + if (Op1LV.isUndefined()) + break; // X / 0 -> undef. No change. // X % 0 -> undef. No change. - if (Op1LV.isConstant() && Op1LV.getConstant()->isZeroValue()) + if (C1 && C1->isZeroValue()) break; // undef / X -> 0. X could be maxint. @@ -1541,15 +1476,14 @@ return true; case Instruction::AShr: // X >>a undef -> undef. - if (Op1LV.isUnknown()) break; + if (Op1LV.isUndefined()) + break; // Shifting by the bitwidth or more is undefined. - if (Op1LV.isConstant()) { - if (auto *ShiftAmt = Op1LV.getConstantInt()) - if (ShiftAmt->getLimitedValue() >= - ShiftAmt->getType()->getScalarSizeInBits()) - break; - } + if (auto *ShiftAmt = getConstantInt(Op1LV, &I)) + if (ShiftAmt->getLimitedValue() >= + ShiftAmt->getType()->getScalarSizeInBits()) + break; // undef >>a X -> 0 markForcedConstant(&I, Constant::getNullValue(ITy)); @@ -1558,15 +1492,14 @@ case Instruction::Shl: // X << undef -> undef. // X >> undef -> undef. - if (Op1LV.isUnknown()) break; + if (Op1LV.isUndefined()) + break; // Shifting by the bitwidth or more is undefined. - if (Op1LV.isConstant()) { - if (auto *ShiftAmt = Op1LV.getConstantInt()) - if (ShiftAmt->getLimitedValue() >= - ShiftAmt->getType()->getScalarSizeInBits()) - break; - } + if (auto *ShiftAmt = getConstantInt(Op1LV, &I)) + if (ShiftAmt->getLimitedValue() >= + ShiftAmt->getType()->getScalarSizeInBits()) + break; // undef << X -> 0 // undef >> X -> 0 @@ -1575,21 +1508,21 @@ 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. + if (Op0LV.isUndefined()) { + if (!isConstant(Op1LV)) // Pick the constant one if there is any. Op1LV = getValueState(I.getOperand(2)); - } else if (Op1LV.isUnknown()) { + } else if (Op1LV.isUndefined()) { // c ? undef : undef -> undef. No change. Op1LV = getValueState(I.getOperand(2)); - if (Op1LV.isUnknown()) + if (Op1LV.isUndefined()) break; // Otherwise, c ? undef : x -> x. } else { - // Leave Op1LV as Operand(1)'s LatticeValue. + // Leave Op1LV as Operand(1)'s ValueLatticeElementue. } - if (Op1LV.isConstant()) - markForcedConstant(&I, Op1LV.getConstant()); + if (Constant *C = getConstant(Op1LV, I.getOperand(1)->getType())) + markForcedConstant(&I, C); else markOverdefined(&I); return true; @@ -1603,7 +1536,7 @@ Op0LV = getValueState(I.getOperand(0)); Op1LV = getValueState(I.getOperand(1)); - if ((Op0LV.isUnknown() || Op1LV.isUnknown()) && + if ((Op0LV.isUndefined() || Op1LV.isUndefined()) && cast(&I)->isEquality()) break; markOverdefined(&I); @@ -1638,7 +1571,7 @@ Instruction *TI = BB.getTerminator(); if (auto *BI = dyn_cast(TI)) { if (!BI->isConditional()) continue; - if (!getValueState(BI->getCondition()).isUnknown()) + if (!getValueState(BI->getCondition()).isUndefined()) continue; // If the input to SCCP is actually branch on undef, fix the undef to @@ -1666,7 +1599,7 @@ if (IBR->getNumSuccessors() < 1) continue; - if (!getValueState(IBR->getAddress()).isUnknown()) + if (!getValueState(IBR->getAddress()).isUndefined()) continue; // If the input to SCCP is actually branch on undef, fix the undef to @@ -1690,7 +1623,8 @@ } if (auto *SI = dyn_cast(TI)) { - if (!SI->getNumCases() || !getValueState(SI->getCondition()).isUnknown()) + if (!SI->getNumCases() || + !getValueState(SI->getCondition()).isUndefined()) continue; // If the input to SCCP is actually switch on undef, fix the undef to @@ -1719,25 +1653,32 @@ static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) { Constant *Const = nullptr; if (V->getType()->isStructTy()) { - std::vector IVs = Solver.getStructLatticeValueFor(V); - if (llvm::any_of(IVs, - [](const LatticeVal &LV) { return LV.isOverdefined(); })) + std::vector IVs = + Solver.getStructValueLatticeElementFor(V); + if (llvm::any_of(IVs, [](const ValueLatticeElement &LV) { + return !LV.isUndefined() && !isConstant(LV); + })) return false; std::vector ConstVals; auto *ST = dyn_cast(V->getType()); for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { - LatticeVal V = IVs[i]; - ConstVals.push_back(V.isConstant() - ? V.getConstant() - : UndefValue::get(ST->getElementType(i))); + ValueLatticeElement V = IVs[i]; + if (Constant *C = getConstant(V, ST->getElementType(i))) + Const = C; + else + Const = UndefValue::get(ST->getElementType(i)); + ConstVals.push_back(Const); } Const = ConstantStruct::get(ST, ConstVals); } else { - const LatticeVal &IV = Solver.getLatticeValueFor(V); - if (IV.isOverdefined()) + const ValueLatticeElement &IV = Solver.getValueLatticeElementFor(V); + if (!IV.isUndefined() && !isConstant(IV)) return false; - Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(V->getType()); + if (Constant *C = getConstant(IV, V->getType())) + Const = C; + else + Const = UndefValue::get(V->getType()); } assert(Const && "Constant is nullptr here!"); @@ -1923,7 +1864,7 @@ C = SI->case_begin()->getCaseValue(); } } else if (BranchInst *BI = dyn_cast(I)) { - if (!isa(BI->getCondition())) { + if (BI->isConditional() && !isa(BI->getCondition())) { // Indeterminate branch; use false. Dest = BI->getSuccessor(1); C = ConstantInt::getFalse(BI->getContext()); @@ -2068,6 +2009,7 @@ // use ConstantFoldTerminator to get rid of in-edges, record DT updates and // delete dead BBs. for (BasicBlock *DeadBB : BlocksToErase) { + // If there are any PHI nodes in this successor, drop entries for BB now. for (Value::user_iterator UI = DeadBB->user_begin(), UE = DeadBB->user_end(); @@ -2122,10 +2064,12 @@ // whether other functions are optimizable. SmallVector ReturnsToZap; - const DenseMap &RV = Solver.getTrackedRetVals(); + const DenseMap &RV = + Solver.getTrackedRetVals(); for (const auto &I : RV) { Function *F = I.first; - if (I.second.isOverdefined() || F->getReturnType()->isVoidTy()) + if (!(I.second.isUndefined() || isConstant(I.second)) || + F->getReturnType()->isVoidTy()) continue; findReturnsToZap(*F, ReturnsToZap, Solver); } @@ -2146,11 +2090,16 @@ // If we inferred constant or undef values for globals variables, we can // delete the global and any stores that remain to it. - const DenseMap &TG = Solver.getTrackedGlobals(); - for (DenseMap::const_iterator I = TG.begin(), - E = TG.end(); I != E; ++I) { + const DenseMap &TG = + Solver.getTrackedGlobals(); + for (DenseMap::const_iterator + I = TG.begin(), + E = TG.end(); + I != E; ++I) { GlobalVariable *GV = I->first; - assert(!I->second.isOverdefined() && + if (!isConstant(I->second)) + continue; + assert(isConstant(I->second) && "Overdefined values should have been taken out of the map!"); LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName() << "' is constant!\n"); diff --git a/llvm/test/Transforms/SCCP/ip-constant-ranges.ll b/llvm/test/Transforms/SCCP/ip-constant-ranges.ll --- a/llvm/test/Transforms/SCCP/ip-constant-ranges.ll +++ b/llvm/test/Transforms/SCCP/ip-constant-ranges.ll @@ -61,10 +61,8 @@ ; x is overdefined, because constant ranges are only used for parameter ; values. -; CHECK-LABEL: f3 -; CHECK: %cmp = icmp sgt i32 %x, 300 -; CHECK: %res = select i1 %cmp, i32 1, i32 2 -; CHECK: ret i32 %res +; CHECK-LABEL: define internal i32 @f3 +; CHECK: ret i32 undef define internal i32 @f3(i32 %x) { entry: %cmp = icmp sgt i32 %x, 300 @@ -72,6 +70,11 @@ ret i32 %res } +; CHECK-LABEL: @caller2 +; CHECK-LABEL: end: +; CHECK-NEXT: %res = phi i32 [ 0, %entry ], [ 1, %if.true ] +; CHECK-NEXT: %call1 = tail call i32 @f3(i32 %res) +; CHECK-NEXT: ret i32 2 ; The phi node could be converted in a ConstantRange. define i32 @caller2(i1 %cmp) { entry: diff --git a/llvm/test/Transforms/SCCP/ipsccp-range-crashes.ll b/llvm/test/Transforms/SCCP/ipsccp-range-crashes.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/SCCP/ipsccp-range-crashes.ll @@ -0,0 +1,123 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -ipsccp -S %s | FileCheck %s + +; A few test cases exposing crashes with the initial range implementation. + +@global.2 = external dso_local unnamed_addr constant [25 x i8], align 1 +@global = internal local_unnamed_addr global i32 0, align 4 +@global.3 = internal local_unnamed_addr global i32 0, align 4 + +define void @main(i8** %arg) { +; CHECK-LABEL: @main( +; CHECK-NEXT: bb: +; CHECK-NEXT: [[TMP:%.*]] = getelementptr inbounds i8*, i8** [[ARG:%.*]], i64 undef +; CHECK-NEXT: [[TMP1:%.*]] = load i8*, i8** [[TMP]], align 8 +; CHECK-NEXT: [[TMP2:%.*]] = load i8, i8* [[TMP1]], align 1 +; CHECK-NEXT: [[TMP3:%.*]] = sext i8 [[TMP2]] to i32 +; CHECK-NEXT: [[TMP4:%.*]] = icmp ne i32 [[TMP3]], 45 +; CHECK-NEXT: [[TMP5:%.*]] = select i1 [[TMP4]], i32 2, i32 4 +; CHECK-NEXT: ret void +; +bb: + %tmp = getelementptr inbounds i8*, i8** %arg, i64 undef + %tmp1 = load i8*, i8** %tmp, align 8 + %tmp2 = load i8, i8* %tmp1, align 1 + %tmp3 = sext i8 %tmp2 to i32 + %tmp4 = icmp ne i32 %tmp3, 45 + %tmp5 = select i1 %tmp4, i32 2, i32 4 + ret void +} + +define void @ham() local_unnamed_addr { +; CHECK-LABEL: @ham( +; CHECK-NEXT: bb: +; CHECK-NEXT: br label [[BB1:%.*]] +; CHECK: bb1: +; CHECK-NEXT: [[TMP:%.*]] = icmp slt i32 undef, 40 +; CHECK-NEXT: br i1 [[TMP]], label [[BB2:%.*]], label [[BB4:%.*]] +; CHECK: bb2: +; CHECK-NEXT: br label [[BB7:%.*]] +; CHECK: bb3: +; CHECK-NEXT: br label [[BB4]] +; CHECK: bb4: +; CHECK-NEXT: [[TMP5:%.*]] = phi i64 [ 0, [[BB1]] ], [ 15, [[BB3:%.*]] ] +; CHECK-NEXT: [[TMP6:%.*]] = add i64 [[TMP5]], add (i64 xor (i64 ptrtoint ([25 x i8]* @global.2 to i64), i64 -1), i64 1) +; CHECK-NEXT: unreachable +; CHECK: bb7: +; CHECK-NEXT: br label [[BB3]] +; +bb: + br label %bb1 + +bb1: ; preds = %bb + %tmp = icmp slt i32 undef, 40 + br i1 %tmp, label %bb2, label %bb4 + +bb2: ; preds = %bb1 + br label %bb7 + +bb3: ; preds = %bb7 + br label %bb4 + +bb4: ; preds = %bb3, %bb1 + %tmp5 = phi i64 [ 0, %bb1 ], [ %tmp10, %bb3 ] + %tmp6 = add i64 %tmp5, add (i64 xor (i64 ptrtoint ([25 x i8]* @global.2 to i64), i64 -1), i64 1) + unreachable + +bb7: ; preds = %bb2 + %tmp8 = add i64 0, 15 + %tmp9 = add i64 %tmp8, 0 + %tmp10 = add i64 %tmp9, 0 + br label %bb3 +} + +declare i32 @barney.4() + +define void @wobble() { +; CHECK-LABEL: @wobble( +; CHECK-NEXT: bb: +; CHECK-NEXT: [[TMP:%.*]] = load i32, i32* @global, align 4 +; CHECK-NEXT: store i32 [[TMP]], i32* @global.3, align 4 +; CHECK-NEXT: ret void +; +bb: + %tmp = load i32, i32* @global, align 4 + store i32 %tmp, i32* @global.3, align 4 + ret void +} + +define i32 @wobble.5(i32 %arg) { +bb: + %tmp = load i32, i32* @global.3, align 4 + %tmp1 = sdiv i32 0, %tmp + ret i32 %tmp1 +} + +define void @eggs() { +; CHECK-LABEL: @eggs( +; CHECK-NEXT: bb: +; CHECK-NEXT: br label [[BB1:%.*]] +; CHECK: bb1: +; CHECK-NEXT: [[TMP:%.*]] = phi i32 [ 0, [[BB:%.*]] ], [ [[TMP2:%.*]], [[BB1]] ] +; CHECK-NEXT: [[TMP2]] = add nsw i32 [[TMP]], 1 +; CHECK-NEXT: [[TMP3:%.*]] = call i32 @barney.4() +; CHECK-NEXT: [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 1 +; CHECK-NEXT: br i1 [[TMP4]], label [[BB1]], label [[BB5:%.*]] +; CHECK: bb5: +; CHECK-NEXT: store i32 [[TMP2]], i32* @global, align 4 +; CHECK-NEXT: ret void +; +bb: + br label %bb1 + +bb1: ; preds = %bb1, %bb + %tmp = phi i32 [ 0, %bb ], [ %tmp2, %bb1 ] + %tmp2 = add nsw i32 %tmp, 1 + %tmp3 = call i32 @barney.4() + %tmp4 = icmp eq i32 %tmp3, 1 + br i1 %tmp4, label %bb1, label %bb5 + +bb5: ; preds = %bb1 + store i32 %tmp2, i32* @global, align 4 + ret void +}