diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp --- a/llvm/lib/IR/ConstantRange.cpp +++ b/llvm/lib/IR/ConstantRange.cpp @@ -1009,6 +1009,8 @@ ConstantRange::udiv(const ConstantRange &RHS) const { if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue()) return getEmpty(); + if (isSingleElement() && getSingleElement()->isNullValue()) + return *this; if (RHS.isFullSet()) return getFull(); 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,142 +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, - - /// This Value is known to not have the specified value. - notconstant, - - /// 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 isNotConstant() const { return getLatticeValue() == notconstant; } - - 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; - } - - bool markNotConstant(Constant *V) { - assert(V && "Marking constant with NULL"); - if (isa(V)) - return false; - - assert((!isNotConstant() || getNotConstant() == V) && - "Marking !constant with different value"); - assert(isUnknown() || isNotConstant()); - Val.setPointer(V); - Val.setInt(notconstant); - 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; - } - - Constant *getNotConstant() const { - assert(isNotConstant() && "Cannot get the constant of a non-notconstant!"); - return Val.getPointer(); - } - - /// 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()); - if (isNotConstant()) - return ValueLatticeElement::getNot(getNotConstant()); - 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()); +} //===----------------------------------------------------------------------===// // @@ -217,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. @@ -314,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()); } @@ -328,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 @@ -374,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!"); @@ -386,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; } @@ -435,16 +321,27 @@ 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); @@ -453,7 +350,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); @@ -467,13 +364,13 @@ 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); } - bool markNotConstant(LatticeVal &IV, Value *V, Constant *C) { + bool markNotConstant(ValueLatticeElement &IV, Value *V, Constant *C) { if (!IV.markNotConstant(C)) return false; LLVM_DEBUG(dbgs() << "markNotConstant: " << *C << ": " << *V << '\n'); @@ -484,7 +381,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: "; @@ -496,51 +393,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()) { - if (MergeWithV.isNotConstant()) - return markNotConstant(IV, V, MergeWithV.getNotConstant()); - else { - assert(MergeWithV.isConstant() && "Unexpected lattice value type"); - return markConstant(IV, V, MergeWithV.getConstant()); - } - } - - if (IV.isNotConstant()) { - if (MergeWithV.isNotConstant() && - IV.getNotConstant() == MergeWithV.getNotConstant()) - return false; - return markOverdefined(IV, V); - } - - if (IV.isConstant()) { - if (MergeWithV.isConstant() && - IV.getConstant() == MergeWithV.getConstant()) - return false; - 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. @@ -555,30 +433,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. @@ -720,12 +588,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; } @@ -746,12 +614,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; } @@ -764,11 +632,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; } @@ -845,41 +715,20 @@ // 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); - - if (IV.isNotConstant()) - 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); + ValueLatticeElement &Res = getValueState(&PN); + Changed |= Res.mergeIn(IV, DL); } - - // 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) + pushToWorkList(ValueState[&PN], &PN); } void SCCPSolver::visitReturnInst(ReturnInst &I) { @@ -890,8 +739,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; @@ -921,19 +770,16 @@ } void SCCPSolver::visitCastInst(CastInst &I) { - LatticeVal OpSt = getValueState(I.getOperand(0)); - if (OpSt.isOverdefined() || - OpSt.isNotConstant()) // 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) { @@ -949,7 +795,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. @@ -974,7 +820,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; } @@ -984,7 +830,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); } } @@ -996,11 +842,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; @@ -1009,34 +855,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) + pushToWorkList(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 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.isConstant() && V2State.isConstant()) { + 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. @@ -1045,17 +925,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 @@ -1063,27 +940,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() && !V1State.isNotConstant()) + ValueLatticeElement *NonOverdefVal = nullptr; + if (isConstant(V1State)) NonOverdefVal = &V1State; - else if (!V2State.isOverdefined() && !V2State.isNotConstant()) + 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); } } } @@ -1100,33 +978,25 @@ 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; + + // dbgs() << "CMP " << V1State << " " << V2State << "\n"; 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); } @@ -1139,15 +1009,16 @@ 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() || State.isNotConstant()) - return (void)markOverdefined(&I); + if (Constant *C = getConstant(State, I.getOperand(i)->getType())) { + Operands.push_back(C); + continue; + } - assert(State.isConstant() && "Unknown state!"); - Operands.push_back(State.getConstant()); + return (void)markOverdefined(&I); } Constant *Ptr = Operands[0]; @@ -1156,7 +1027,7 @@ ConstantExpr::getGetElementPtr(I.getSourceElementType(), Ptr, Indices); if (isa(C)) return; - markConstant(&I, C); + mergeInValue(&I, ValueLatticeElement::get(C)); } void SCCPSolver::visitStoreInst(StoreInst &SI) { @@ -1168,8 +1039,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))); @@ -1184,16 +1057,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)) { @@ -1207,10 +1081,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; } } @@ -1267,10 +1141,10 @@ if (CmpOp0 != CopyOf) std::swap(CmpOp0, CmpOp1); - LatticeVal OriginalVal = getValueState(CopyOf); - LatticeVal EqVal = getValueState(CmpOp1); - LatticeVal &IV = ValueState[I]; - if (OriginalVal.isConstant()) { + ValueLatticeElement OriginalVal = getValueState(CopyOf); + ValueLatticeElement EqVal = getValueState(CmpOp1); + ValueLatticeElement &IV = ValueState[I]; + if (isConstant(OriginalVal)) { mergeInValue(IV, I, OriginalVal); return; } @@ -1281,12 +1155,16 @@ mergeInValue(IV, I, EqVal); return; } else { - if (EqVal.isConstant() && - (IV.isUnknown() || + if (isConstant(EqVal) && + (IV.isUndefined() || (IV.isNotConstant() && - IV.getNotConstant() == EqVal.getConstant()))) { + IV.getNotConstant() == getConstant(EqVal, CmpOp1->getType())) || + (IV.isConstantRange() && + IV.getConstantRange() == + ConstantRange(getConstantInt(EqVal, I)->getValue() + 1, + getConstantInt(EqVal, I)->getValue())))) { addAdditionalUser(CmpOp1, I); - markNotConstant(IV, I, EqVal.getConstant()); + markNotConstant(IV, I, getConstant(EqVal, CmpOp1->getType())); return; } } @@ -1296,12 +1174,16 @@ mergeInValue(IV, I, EqVal); return; } else { - if (EqVal.isConstant() && - (IV.isUnknown() || + if (isConstant(EqVal) && + (IV.isUndefined() || (IV.isNotConstant() && - IV.getNotConstant() == EqVal.getConstant()))) { + IV.getNotConstant() == getConstant(EqVal, CmpOp1->getType())) || + (IV.isConstantRange() && + IV.getConstantRange() == + ConstantRange(getConstantInt(EqVal, I)->getValue() + 1, + getConstantInt(EqVal, I)->getValue())))) { addAdditionalUser(CmpOp1, I); - markNotConstant(IV, I, EqVal.getConstant()); + markNotConstant(IV, I, getConstant(EqVal, CmpOp1->getType())); return; } } @@ -1328,14 +1210,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() || State.isNotConstant()) + if (!isConstant(State)) return (void)markOverdefined(I); - assert(State.isConstant()); - Operands.push_back(State.getConstant()); + Operands.push_back(getConstant(State, (*AI)->getType())); } if (getValueState(I).isOverdefined()) @@ -1375,22 +1256,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); } } } @@ -1406,7 +1278,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. @@ -1511,29 +1384,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); @@ -1541,7 +1416,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(); @@ -1558,7 +1435,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); @@ -1578,7 +1455,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. @@ -1586,7 +1463,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)); @@ -1595,7 +1472,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; } @@ -1607,11 +1484,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. @@ -1620,15 +1498,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)); @@ -1637,15 +1514,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 @@ -1654,21 +1530,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; @@ -1682,7 +1558,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); @@ -1717,7 +1593,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 @@ -1745,7 +1621,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 @@ -1769,7 +1645,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 @@ -1798,26 +1675,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) { + std::vector IVs = + Solver.getStructValueLatticeElementFor(V); + if (llvm::any_of(IVs, [](const ValueLatticeElement &LV) { return LV.isOverdefined() || LV.isNotConstant(); })) 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() || IV.isNotConstant()) + 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!"); @@ -1985,6 +1868,7 @@ return; } + // dbgs() << *BB.getTerminator() << "ZZZZ\n"; if (auto *RI = dyn_cast(BB.getTerminator())) if (!isa(RI->getOperand(0))) ReturnsToZap.push_back(RI); @@ -2202,10 +2086,11 @@ // 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.isUnknown() || I.second.isConstant()) || + if (!(I.second.isUndefined() || isConstant(I.second)) || F->getReturnType()->isVoidTy()) continue; findReturnsToZap(*F, ReturnsToZap, Solver); @@ -2227,11 +2112,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-notnull.ll b/llvm/test/Transforms/SCCP/ipsccp-notnull.ll --- a/llvm/test/Transforms/SCCP/ipsccp-notnull.ll +++ b/llvm/test/Transforms/SCCP/ipsccp-notnull.ll @@ -62,3 +62,154 @@ if.end: ; preds = %entry ret i64 %num } + +%struct._IO_FILE.1.3.5.7.11.13.15.17.21.23.25.27.43 = type { i32, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, %struct._IO_marker.0.2.4.6.10.12.14.16.20.22.24.26.42*, %struct._IO_FILE.1.3.5.7.11.13.15.17.21.23.25.27.43*, i32, i32, i64, i16, i8, [1 x i8], i8*, i64, i8*, i8*, i8*, i8*, i64, i32, [20 x i8] } +%struct._IO_marker.0.2.4.6.10.12.14.16.20.22.24.26.42 = type { %struct._IO_marker.0.2.4.6.10.12.14.16.20.22.24.26.42*, %struct._IO_FILE.1.3.5.7.11.13.15.17.21.23.25.27.43*, i32 } + +@.str = external dso_local unnamed_addr constant [3 x i8], align 1 +@stderr = external dso_local global %struct._IO_FILE.1.3.5.7.11.13.15.17.21.23.25.27.43*, align 8 +@.str.1 = external dso_local unnamed_addr constant [32 x i8], align 1 +@g_program = external dso_local global i8*, align 8 +@.str.2 = external dso_local unnamed_addr constant [32 x i8], align 1 +@.str.3 = external dso_local unnamed_addr constant [47 x i8], align 1 +@.str.4 = external dso_local unnamed_addr constant [41 x i8], align 1 +@.str.5 = external dso_local unnamed_addr constant [46 x i8], align 1 +@.str.6 = external dso_local unnamed_addr constant [74 x i8], align 1 +@.str.7 = external dso_local unnamed_addr constant [57 x i8], align 1 +@.str.8 = external dso_local unnamed_addr constant [58 x i8], align 1 +@.str.9 = external dso_local unnamed_addr constant [50 x i8], align 1 +@.str.10 = external dso_local unnamed_addr constant [29 x i8], align 1 +@.str.11 = external dso_local unnamed_addr constant [46 x i8], align 1 +@.str.12 = external dso_local unnamed_addr constant [31 x i8], align 1 +@.str.13 = external dso_local unnamed_addr constant [34 x i8], align 1 +@.str.14 = external dso_local unnamed_addr constant [40 x i8], align 1 +@.str.15 = external dso_local unnamed_addr constant [37 x i8], align 1 +@.str.16 = external dso_local unnamed_addr constant [47 x i8], align 1 +@.str.17 = external dso_local unnamed_addr constant [87 x i8], align 1 + + +define dso_local i8* @load_file(i8* %path, i64* %size_out) #0 { +entry: + %call = call %struct._IO_FILE.1.3.5.7.11.13.15.17.21.23.25.27.43* @fopen(i8* %path, i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i32 0, i32 0)) + %tobool = icmp ne %struct._IO_FILE.1.3.5.7.11.13.15.17.21.23.25.27.43* %call, null + br i1 %tobool, label %if.end, label %if.then + +if.then: ; preds = %entry + unreachable + +if.end: ; preds = %entry + %call2 = call i32 @fseek(%struct._IO_FILE.1.3.5.7.11.13.15.17.21.23.25.27.43* %call, i64 0, i32 2) + unreachable +} + +; Function Attrs: nounwind +declare dso_local noalias %struct._IO_FILE.1.3.5.7.11.13.15.17.21.23.25.27.43* @fopen(i8* nocapture readonly, i8* nocapture readonly) #2 + +; Function Attrs: nounwind +declare dso_local i32 @fseek(%struct._IO_FILE.1.3.5.7.11.13.15.17.21.23.25.27.43* nocapture, i64, i32) #2 + + +@g_append_exitstats = internal global i32 0, align 4 + +; Function Attrs: nounwind uwtable +define dso_local void @main1(i8** %argv) #0 { +entry: + br label %for.body + +for.body: ; preds = %entry + %arrayidx1 = getelementptr inbounds i8*, i8** %argv, i64 undef + %0 = load i8*, i8** %arrayidx1, align 8, !tbaa !1 + %1 = load i8, i8* %0, align 1, !tbaa !5 + %conv = sext i8 %1 to i32 + %cmp3 = icmp ne i32 %conv, 45 + br i1 %cmp3, label %if.then, label %if.end + +if.then: ; preds = %for.body + call void @execute() + ret void + +if.end: ; preds = %for.body + store i32 1, i32* @g_append_exitstats, align 4, !tbaa !6 + unreachable +} + +; Function Attrs: nounwind uwtable +define dso_local void @execute() #0 { +entry: + call void @monitor_child_process() + ret void +} + +; Function Attrs: nounwind uwtable +define dso_local void @monitor_child_process() #0 { +entry: + %0 = load i32, i32* @g_append_exitstats, align 4, !tbaa !6 + ret void +} + + +; Function Attrs: nounwind uwtable +define dso_local void @main3() #0 { +entry: + br label %for.cond6 + +for.cond6: ; preds = %for.cond6, %entry + %0 = call i64 @llvm.ctlz.i64(i64 0, i1 true) + br label %for.cond6 +} + +; Function Attrs: nounwind readnone speculatable +declare i64 @llvm.ctlz.i64(i64, i1) #1 + + +define dso_local void @ercConcealInterFrame() #0 { +entry: + br label %for.cond + +for.cond: ; preds = %entry + br label %for.cond18 + +for.cond18: ; preds = %for.cond + %cmp19 = icmp slt i32 0, undef + br i1 %cmp19, label %for.body21, label %for.inc162 + +for.body21: ; preds = %for.cond18 + call void @concealByTrial() + unreachable + +for.inc162: ; preds = %for.cond18 + unreachable +} + +; Function Attrs: nounwind uwtable +define dso_local void @concealByTrial() #0 { +entry: + br label %do.body30 + +do.body30: ; preds = %for.end276, %entry + br label %for.cond + +for.cond: ; preds = %do.body30 + br label %for.end276 + +for.end276: ; preds = %for.cond + %cmp277 = icmp sge i32 undef, 2 + %0 = select i1 %cmp277, i1 undef, i1 false + br i1 %0, label %do.body30, label %do.end + +do.end: ; preds = %for.end276 + unreachable +} + +attributes #0 = { nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="broadwell" "target-features"="+64bit,+adx,+aes,+avx,+avx2,+bmi,+bmi2,+cmov,+cx16,+f16c,+fma,+fsgsbase,+fxsr,+invpcid,+lzcnt,+mmx,+movbe,+pclmul,+popcnt,+prfchw,+rdrnd,+rdseed,+rtm,+sahf,+sse,+sse2,+sse3,+sse4.1,+sse4.2,+ssse3,+x87,+xsave,+xsaveopt,-avx512bitalg,-avx512bw,-avx512cd,-avx512dq,-avx512er,-avx512f,-avx512ifma,-avx512pf,-avx512vbmi,-avx512vbmi2,-avx512vl,-avx512vnni,-avx512vpopcntdq,-cldemote,-clflushopt,-clwb,-clzero,-fma4,-gfni,-lwp,-movdir64b,-movdiri,-mwaitx,-pconfig,-pku,-prefetchwt1,-ptwrite,-rdpid,-sgx,-sha,-shstk,-sse4a,-tbm,-vaes,-vpclmulqdq,-waitpkg,-wbnoinvd,-xop,-xsavec,-xsaves" "unsafe-fp-math"="false" "use-soft-float"="false" } + +!llvm.ident = !{!0} + +!0 = !{!"clang version 8.0.0 (https://github.com/llvm-mirror/clang.git dafd68092ceda14b5b4a24fabef35bec783876a7) (/space/flohah01/llvm-space/work2/llvm 7f058c8e6e2481e1d22150ff258ac6219f9953ea)"} +!1 = !{!2, !2, i64 0} +!2 = !{!"any pointer", !3, i64 0} +!3 = !{!"omnipotent char", !4, i64 0} +!4 = !{!"Simple C/C++ TBAA"} +!5 = !{!3, !3, i64 0} +!6 = !{!7, !7, i64 0} +!7 = !{!"int", !3, i64 0} 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 +}