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 @@ -144,6 +144,7 @@ } bool isUndefined() const { return Tag == undefined; } + bool isUnknown() const { return Tag == undefined; } bool isConstant() const { return Tag == constant || Tag == forcedconstant; } bool isForcedConstant() const { return Tag == forcedconstant; } bool isNotConstant() const { return Tag == notconstant; } @@ -245,6 +246,9 @@ bool markConstantRange(ConstantRange NewR) { if (isConstantRange()) { + if (getConstantRange().contains(NewR)) + return false; + if (NewR.isEmptySet()) markOverdefined(); else { 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 @@ -74,116 +74,21 @@ 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); - } +// Use ValueLatticeElement as LatticeVal. +using LatticeVal = ValueLatticeElement; + +/// Helper to check if \p LV is either a constant or a constant +/// range with a single element. +bool isConstant(const LatticeVal &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 unknown, a constant or a constant range +/// with a single element. +bool isUnknownOrConstant(const LatticeVal &LV) { + return LV.isUnknown() || isConstant(LV); +} //===----------------------------------------------------------------------===// // @@ -195,8 +100,6 @@ std::function GetTLI; SmallPtrSet BBExecutable; // The BBs that are executable. DenseMap ValueState; // The state each value is in. - // The state each parameter is in. - DenseMap ParamState; /// StructValueState - This maintains ValueState for values that have /// StructType, for example for formal arguments, calls, insertelement, etc. @@ -251,6 +154,8 @@ DenseMap AnalysisResults; DenseMap> AdditionalUsers; + LLVMContext &Ctx; + public: void addAnalysis(Function &F, AnalysisResultsForFn A) { AnalysisResults.insert({&F, std::move(A)}); @@ -270,8 +175,9 @@ } SCCPSolver(const DataLayout &DL, - std::function GetTLI) - : DL(DL), GetTLI(std::move(GetTLI)) {} + std::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. @@ -407,20 +313,40 @@ } // 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()) + 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 LatticeVal &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: + ConstantInt *getConstantInt(const LatticeVal &IV) const { + if (IV.isConstant()) + return IV.getConstantInt(); + return cast_or_null(getConstant(IV)); + } + // pushToWorkList - Helper for markConstant/markForcedConstant/markOverdefined void pushToWorkList(LatticeVal &IV, Value *V) { if (IV.isOverdefined()) @@ -428,6 +354,15 @@ 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(LatticeVal &IV, Value *V) { + LLVM_DEBUG(dbgs() << "updated " << IV << ": " << *V << '\n'); + if (IV.isOverdefined()) + return OverdefinedInstWorkList.push_back(V); + InstWorkList.push_back(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. @@ -466,22 +401,29 @@ 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(LatticeVal &IV, Value *V, LatticeVal MergeWithV, + bool Widen = true) { + // Do a simple form of widening, to avoid extending a range repeatedly in a + // loop. If IV is a constant range, it means we already set it once. If + // MergeWithV would extend IV, mark V as overdefined. + if (Widen && IV.isConstantRange() && MergeWithV.isConstantRange() && + !IV.getConstantRange().contains(MergeWithV.getConstantRange())) { + markOverdefined(IV, V); + return true; + } + 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, LatticeVal MergeWithV, bool Widen = true) { assert(!V->getType()->isStructTy() && "non-structs should use markConstant"); - return mergeInValue(ValueState[V], V, MergeWithV); + return mergeInValue(ValueState[V], V, MergeWithV, Widen); } /// getValueState - Return the LatticeVal object that corresponds to the @@ -507,18 +449,6 @@ 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. @@ -674,7 +604,7 @@ } LatticeVal BCValue = getValueState(BI->getCondition()); - ConstantInt *CI = BCValue.getConstantInt(); + ConstantInt *CI = getConstantInt(BCValue); if (!CI) { // Overdefined condition variables, and branches on unfoldable constant // conditions, mean the branch could go either way. @@ -700,7 +630,7 @@ return; } LatticeVal SCValue = getValueState(SI->getCondition()); - ConstantInt *CI = SCValue.getConstantInt(); + ConstantInt *CI = getConstantInt(SCValue); if (!CI) { // Overdefined or unknown condition? // All destinations are executable! @@ -718,7 +648,7 @@ if (auto *IBR = dyn_cast(&TI)) { // Casts are folded by visitCastInst. LatticeVal IBRValue = getValueState(IBR->getAddress()); - BlockAddress *Addr = IBRValue.getBlockAddress(); + BlockAddress *Addr = dyn_cast_or_null(getConstant(IBRValue)); if (!Addr) { // Overdefined or unknown condition? // All destinations are executable! if (!IBRValue.isUnknown()) @@ -785,8 +715,9 @@ if (PN.getType()->isStructTy()) return (void)markOverdefined(&PN); - if (getValueState(&PN).isOverdefined()) - return; // Quick exit + if (!isUnknownOrConstant(getValueState(&PN))) { + return (void)markOverdefined(&PN); + } // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant, // and slow us down a lot. Just mark them overdefined. @@ -806,11 +737,11 @@ if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) continue; - if (IV.isOverdefined()) // PHI node becomes overdefined! + if (!isUnknownOrConstant(IV)) // PHI node becomes overdefined! return (void)markOverdefined(&PN); if (!OperandVal) { // Grab the first value. - OperandVal = IV.getConstant(); + OperandVal = getConstant(IV); continue; } @@ -820,7 +751,7 @@ // Check to see if there are two different constants merging, if so, the PHI // node is overdefined. - if (IV.getConstant() != OperandVal) + if (getConstant(IV) != OperandVal) return (void)markOverdefined(&PN); } @@ -872,17 +803,15 @@ void SCCPSolver::visitCastInst(CastInst &I) { LatticeVal OpSt = getValueState(I.getOperand(0)); - if (OpSt.isOverdefined()) // Inherit overdefinedness of operand - markOverdefined(&I); - else if (OpSt.isConstant()) { + 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(C)) return; // Propagate constant value markConstant(&I, C); - } + } else if (!OpSt.isUnknown()) + markOverdefined(&I); } void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { @@ -949,7 +878,7 @@ if (CondValue.isUnknown()) return; - if (ConstantInt *CondCB = CondValue.getConstantInt()) { + if (ConstantInt *CondCB = getConstantInt(CondValue)) { Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue(); mergeInValue(&I, getValueState(OpVal)); return; @@ -962,9 +891,9 @@ 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 (isConstant(TVal) && isConstant(FVal) && + getConstant(TVal) == getConstant(FVal)) + return (void)markConstant(&I, getConstant(FVal)); if (TVal.isUnknown()) // select ?, undef, X -> X. return (void)mergeInValue(&I, FVal); @@ -978,10 +907,13 @@ LatticeVal V0State = getValueState(I.getOperand(0)); LatticeVal &IV = ValueState[&I]; - if (IV.isOverdefined()) return; + if (!isUnknownOrConstant(IV)) { + markOverdefined(&I); + return; + } - 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(C)) @@ -1002,11 +934,14 @@ LatticeVal V2State = getValueState(I.getOperand(1)); LatticeVal &IV = ValueState[&I]; - if (IV.isOverdefined()) return; + if (!isUnknownOrConstant(IV)) { + markOverdefined(&I); + return; + } - if (V1State.isConstant() && V2State.isConstant()) { - Constant *C = ConstantExpr::get(I.getOpcode(), V1State.getConstant(), - V2State.getConstant()); + if (isConstant(V1State) && isConstant(V2State)) { + Constant *C = ConstantExpr::get(I.getOpcode(), getConstant(V1State), + getConstant(V2State)); // X op Y -> undef. if (isa(C)) return; @@ -1014,7 +949,7 @@ } // If something is undef, wait for it to resolve. - if (!V1State.isOverdefined() && !V2State.isOverdefined()) + if (V1State.isUnknown() || V2State.isUnknown()) return; // Otherwise, one of our operands is overdefined. Try to produce something @@ -1022,8 +957,8 @@ // 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 (isConstant(V1State) && getConstant(V1State)->isNullValue()) + return (void)markConstant(IV, &I, getConstant(V1State)); // If this is: // -> AND/MUL with 0 @@ -1032,9 +967,9 @@ if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Mul || I.getOpcode() == Instruction::Or) { LatticeVal *NonOverdefVal = nullptr; - if (!V1State.isOverdefined()) + if (isUnknownOrConstant(V1State)) NonOverdefVal = &V1State; - else if (!V2State.isOverdefined()) + else if (isUnknownOrConstant(V2State)) NonOverdefVal = &V2State; if (NonOverdefVal) { @@ -1045,13 +980,13 @@ 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)->isNullValue()) + return (void)markConstant(IV, &I, getConstant(*NonOverdefVal)); } else { // X or -1 = -1 - if (ConstantInt *CI = NonOverdefVal->getConstantInt()) + if (ConstantInt *CI = getConstantInt(*NonOverdefVal)) if (CI->isMinusOne()) - return (void)markConstant(IV, &I, NonOverdefVal->getConstant()); + return (void)markConstant(IV, &I, CI); } } } @@ -1063,22 +998,18 @@ 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 (!isUnknownOrConstant(ValueState[&I])) { + markOverdefined(&I); + return; + } 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) { @@ -1091,8 +1022,8 @@ } // If operands are still unknown, wait for it to resolve. - if (!V1State.isOverdefined() && !V2State.isOverdefined() && - !ValueState[&I].isConstant()) + if ((V1State.isUnknown() || V2State.isUnknown()) && + !isConstant(ValueState[&I])) return; markOverdefined(&I); @@ -1114,8 +1045,12 @@ if (State.isOverdefined()) 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]; @@ -1137,7 +1072,8 @@ GlobalVariable *GV = cast(SI.getOperand(1)); DenseMap::iterator I = TrackedGlobals.find(GV); - if (I == TrackedGlobals.end() || I->second.isOverdefined()) return; + 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))); @@ -1158,10 +1094,10 @@ LatticeVal &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); // load null is undefined. if (isa(Ptr)) { @@ -1240,7 +1176,7 @@ LatticeVal &IV = ValueState[I]; if (PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_EQ) { addAdditionalUser(CmpOp1, I); - if (OriginalVal.isConstant()) + if (isConstant(OriginalVal)) mergeInValue(IV, I, OriginalVal); else mergeInValue(IV, I, EqVal); @@ -1248,7 +1184,7 @@ } if (!PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_NE) { addAdditionalUser(CmpOp1, I); - if (OriginalVal.isConstant()) + if (isConstant(OriginalVal)) mergeInValue(IV, I, OriginalVal); else mergeInValue(IV, I, EqVal); @@ -1280,10 +1216,9 @@ if (State.isUnknown()) 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)); } if (getValueState(I).isOverdefined()) @@ -1324,22 +1259,10 @@ if (auto *STy = dyn_cast(AI->getType())) { for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { LatticeVal CallArg = getStructValueState(*CAI, i); - mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg); + mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg, false); } - } 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); - } + } else + mergeInValue(&*AI, getValueState(*CAI), false); } } @@ -1499,6 +1422,7 @@ } LatticeVal Op0LV = getValueState(I.getOperand(0)); LatticeVal Op1LV; + Constant *C1 = nullptr; if (I.getNumOperands() == 2) { if (I.getOperand(1)->getType()->isStructTy()) { markOverdefined(&I); @@ -1506,7 +1430,9 @@ } Op1LV = getValueState(I.getOperand(1)); + C1 = getConstant(Op1LV); } + // If this is an instructions whose result is defined even if the input is // not fully defined, propagate the information. Type *ITy = I.getType(); @@ -1578,7 +1504,7 @@ // 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. @@ -1590,12 +1516,10 @@ 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; - } + if (auto *ShiftAmt = getConstantInt(Op1LV)) + if (ShiftAmt->getLimitedValue() >= + ShiftAmt->getType()->getScalarSizeInBits()) + break; // undef >>a X -> 0 markForcedConstant(&I, Constant::getNullValue(ITy)); @@ -1607,12 +1531,10 @@ 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; - } + if (auto *ShiftAmt = getConstantInt(Op1LV)) + if (ShiftAmt->getLimitedValue() >= + ShiftAmt->getType()->getScalarSizeInBits()) + break; // undef << X -> 0 // undef >> X -> 0 @@ -1622,7 +1544,7 @@ 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 (!isConstant(Op1LV)) // Pick the constant one if there is any. Op1LV = getValueState(I.getOperand(2)); } else if (Op1LV.isUnknown()) { // c ? undef : undef -> undef. No change. @@ -1634,8 +1556,8 @@ // Leave Op1LV as Operand(1)'s LatticeValue. } - if (Op1LV.isConstant()) - markForcedConstant(&I, Op1LV.getConstant()); + if (Constant *C = getConstant(Op1LV)) + markForcedConstant(&I, C); else markOverdefined(&I); return true; @@ -1754,24 +1676,25 @@ Constant *Const = nullptr; if (V->getType()->isStructTy()) { std::vector IVs = Solver.getStructLatticeValueFor(V); - if (llvm::any_of(IVs, - [](const LatticeVal &LV) { return LV.isOverdefined(); })) + if (any_of(IVs, + [](const LatticeVal &LV) { return !isUnknownOrConstant(LV); })) return false; std::vector ConstVals; auto *ST = cast(V->getType()); for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { LatticeVal V = IVs[i]; - ConstVals.push_back(V.isConstant() - ? V.getConstant() + 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()) + if (!isUnknownOrConstant(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!"); @@ -1804,7 +1727,8 @@ 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()); @@ -2006,7 +1930,7 @@ Module &M, const DataLayout &DL, std::function GetTLI, function_ref 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. @@ -2192,7 +2116,7 @@ const MapVector &RV = Solver.getTrackedRetVals(); for (const auto &I : RV) { Function *F = I.first; - if (I.second.isOverdefined() || F->getReturnType()->isVoidTy()) + if (!isUnknownOrConstant(I.second) || F->getReturnType()->isVoidTy()) continue; findReturnsToZap(*F, ReturnsToZap, Solver); } @@ -2217,8 +2141,8 @@ for (DenseMap::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!"); + if (!isUnknownOrConstant(I->second)) + continue; LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName() << "' is constant!\n"); while (!GV->use_empty()) { 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 @@ -196,3 +196,41 @@ %call = call i32 @recursive_f(i32 42) ret i32 %call } + +define internal i32 @callee6.1(i32 %i) { +; CHECK-LABEL: define internal i32 @callee6.1( +; CHECK-NEXT: %res = call i32 @callee6.2(i32 %i) +; CHECK-NEXT: ret i32 undef +; + %res = call i32 @callee6.2(i32 %i) + ret i32 %res +} + +define internal i32 @callee6.2(i32 %i) { +; CHECK-LABEL: define internal i32 @callee6.2(i32 %i) { +; CHECK-NEXT: br label %if.then + +; CHECK-LABEL: if.then: +; CHECK-NEXT: ret i32 undef +; + %cmp = icmp ne i32 %i, 0 + br i1 %cmp, label %if.then, label %if.else + +if.then: ; preds = %entry + ret i32 1 + +if.else: ; preds = %entry + ret i32 2 +} + +define i32 @caller6() { +; CHECK-LABEL: define i32 @caller6() { +; CHECK-NEXT: %call.1 = call i32 @callee6.1(i32 30) +; CHECK-NEXT: %call.2 = call i32 @callee6.1(i32 43) +; CHECK-NEXT: ret i32 2 +; + %call.1 = call i32 @callee6.1(i32 30) + %call.2 = call i32 @callee6.1(i32 43) + %res = add i32 %call.1, %call.2 + ret i32 %res +} 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 +} diff --git a/llvm/test/Transforms/SCCP/ipsccp-range-structs.ll b/llvm/test/Transforms/SCCP/ipsccp-range-structs.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/SCCP/ipsccp-range-structs.ll @@ -0,0 +1,45 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -sccp -S %s | FileCheck %s + +declare i32* @bar(i32) local_unnamed_addr #3 + +; Function Attrs: nounwind ssp uwtable +define { i8, i32* } @_ZN4llvm3EVT12getIntegerVTERNS_11LLVMContextEj(i32 %BitWidth) local_unnamed_addr #0 align 2 { +; CHECK-LABEL: @_ZN4llvm3EVT12getIntegerVTERNS_11LLVMContextEj( +; CHECK-NEXT: entry: +; CHECK-NEXT: switch i32 [[BITWIDTH:%.*]], label [[IF_END:%.*]] [ +; CHECK-NEXT: i32 1, label [[CLEANUP:%.*]] +; CHECK-NEXT: i32 8, label [[SW_BB1_I:%.*]] +; CHECK-NEXT: ] +; CHECK: sw.bb1.i: +; CHECK-NEXT: br label [[CLEANUP]] +; CHECK: if.end: +; CHECK-NEXT: [[CALL_I:%.*]] = tail call i32* @bar(i32 [[BITWIDTH]]) +; CHECK-NEXT: br label [[CLEANUP]] +; CHECK: cleanup: +; CHECK-NEXT: [[V1:%.*]] = phi i32* [ [[CALL_I]], [[IF_END]] ], [ null, [[SW_BB1_I]] ], [ null, [[ENTRY:%.*]] ] +; CHECK-NEXT: [[V2:%.*]] = phi i8 [ 0, [[IF_END]] ], [ 3, [[SW_BB1_I]] ], [ 2, [[ENTRY]] ] +; CHECK-NEXT: [[DOTFCA_0_INSERT:%.*]] = insertvalue { i8, i32* } undef, i8 [[V2]], 0 +; CHECK-NEXT: [[DOTFCA_1_INSERT:%.*]] = insertvalue { i8, i32* } [[DOTFCA_0_INSERT]], i32* [[V1]], 1 +; CHECK-NEXT: ret { i8, i32* } [[DOTFCA_1_INSERT]] +; +entry: + switch i32 %BitWidth, label %if.end [ + i32 1, label %cleanup + i32 8, label %sw.bb1.i + ] + +sw.bb1.i: ; preds = %entry + br label %cleanup + +if.end: ; preds = %entry + %call.i = tail call i32* @bar(i32 %BitWidth) + br label %cleanup + +cleanup: ; preds = %entry, %sw.bb1.i, %sw.bb2.i, %sw.bb3.i, %sw.bb4.i, %sw.bb5.i, %if.end + %v1 = phi i32* [ %call.i, %if.end ], [ null, %sw.bb1.i ], [ null, %entry ] + %v2 = phi i8 [ 0, %if.end ], [ 3, %sw.bb1.i ], [ 2, %entry ] + %.fca.0.insert = insertvalue { i8, i32* } undef, i8 %v2, 0 + %.fca.1.insert = insertvalue { i8, i32* } %.fca.0.insert, i32* %v1, 1 + ret { i8, i32* } %.fca.1.insert +}