From d972c63af4b395ed9285cd6184a5c3c8c56663d6 Mon Sep 17 00:00:00 2001 From: Eric Christopher Date: Thu, 12 Jul 2018 01:53:21 +0000 Subject: [PATCH] Temporarily revert "Recommit r328307: [IPSCCP] Use constant range information for comparisons of parameters." as it's causing miscompiles. A testcase was provided in the original review thread. This reverts commit r336098. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@336877 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/SCCP.cpp | 192 ++++++++++++--------- test/Transforms/SCCP/ip-constant-ranges.ll | 55 ++---- 2 files changed, 124 insertions(+), 123 deletions(-) diff --git a/lib/Transforms/Scalar/SCCP.cpp b/lib/Transforms/Scalar/SCCP.cpp index 6f3d798f704..6d674f447da 100644 --- a/lib/Transforms/Scalar/SCCP.cpp +++ b/lib/Transforms/Scalar/SCCP.cpp @@ -69,6 +69,8 @@ STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable"); STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP"); STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP"); STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP"); +STATISTIC(IPNumRangeInfoUsed, "Number of times constant range info was used by" + "IPSCCP"); namespace { @@ -337,13 +339,20 @@ public: return StructValues; } - const LatticeVal &getLatticeValueFor(Value *V) const { + ValueLatticeElement getLatticeValueFor(Value *V) { assert(!V->getType()->isStructTy() && "Should use getStructLatticeValueFor"); - DenseMap::const_iterator I = ValueState.find(V); - assert(I != ValueState.end() && - "V not found in ValueState nor Paramstate map!"); - return I->second; + std::pair::iterator, bool> + PI = ParamState.insert(std::make_pair(V, ValueLatticeElement())); + ValueLatticeElement &LV = PI.first->second; + if (PI.second) { + DenseMap::const_iterator I = ValueState.find(V); + assert(I != ValueState.end() && + "V not found in ValueState nor Paramstate map!"); + LV = I->second.toValueLattice(); + } + + return LV; } /// getTrackedRetVals - Get the inferred return value map. @@ -404,16 +413,15 @@ private: // markConstant - Make a value be marked as "constant". If the value // is not already a constant, add it to the instruction work list so that // the users of the instruction are updated later. - bool markConstant(LatticeVal &IV, Value *V, Constant *C) { - if (!IV.markConstant(C)) return false; + void markConstant(LatticeVal &IV, Value *V, Constant *C) { + if (!IV.markConstant(C)) return; LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n'); pushToWorkList(IV, V); - return true; } - bool markConstant(Value *V, Constant *C) { + void markConstant(Value *V, Constant *C) { assert(!V->getType()->isStructTy() && "structs should use mergeInValue"); - return markConstant(ValueState[V], V, C); + markConstant(ValueState[V], V, C); } void markForcedConstant(Value *V, Constant *C) { @@ -427,8 +435,8 @@ private: // 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) { - if (!IV.markOverdefined()) return false; + void markOverdefined(LatticeVal &IV, Value *V) { + if (!IV.markOverdefined()) return; LLVM_DEBUG(dbgs() << "markOverdefined: "; if (auto *F = dyn_cast(V)) dbgs() @@ -436,25 +444,23 @@ private: else dbgs() << *V << '\n'); // Only instructions go on the work list pushToWorkList(IV, V); - return true; } - bool mergeInValue(LatticeVal &IV, Value *V, LatticeVal MergeWithV) { + void mergeInValue(LatticeVal &IV, Value *V, LatticeVal MergeWithV) { if (IV.isOverdefined() || MergeWithV.isUnknown()) - return false; // Noop. + return; // 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); - return false; } - bool mergeInValue(Value *V, LatticeVal MergeWithV) { + void mergeInValue(Value *V, LatticeVal MergeWithV) { assert(!V->getType()->isStructTy() && "non-structs should use markConstant"); - return mergeInValue(ValueState[V], V, MergeWithV); + mergeInValue(ValueState[V], V, MergeWithV); } /// getValueState - Return the LatticeVal object that corresponds to the @@ -777,7 +783,7 @@ void SCCPSolver::visitPHINode(PHINode &PN) { // If this PN returns a struct, just mark the result overdefined. // TODO: We could do a lot better than this if code actually uses this. if (PN.getType()->isStructTy()) - return (void)markOverdefined(&PN); + return markOverdefined(&PN); if (getValueState(&PN).isOverdefined()) return; // Quick exit @@ -785,7 +791,7 @@ void SCCPSolver::visitPHINode(PHINode &PN) { // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant, // and slow us down a lot. Just mark them overdefined. if (PN.getNumIncomingValues() > 64) - return (void)markOverdefined(&PN); + return markOverdefined(&PN); // Look at all of the executable operands of the PHI node. If any of them // are overdefined, the PHI becomes overdefined as well. If they are all @@ -801,7 +807,7 @@ void SCCPSolver::visitPHINode(PHINode &PN) { continue; if (IV.isOverdefined()) // PHI node becomes overdefined! - return (void)markOverdefined(&PN); + return markOverdefined(&PN); if (!OperandVal) { // Grab the first value. OperandVal = IV.getConstant(); @@ -815,7 +821,7 @@ void SCCPSolver::visitPHINode(PHINode &PN) { // 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); + return markOverdefined(&PN); } // If we exited the loop, this means that the PHI node only has constant @@ -883,11 +889,11 @@ void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { // If this returns a struct, mark all elements over defined, we don't track // structs in structs. if (EVI.getType()->isStructTy()) - return (void)markOverdefined(&EVI); + return markOverdefined(&EVI); // If this is extracting from more than one level of struct, we don't know. if (EVI.getNumIndices() != 1) - return (void)markOverdefined(&EVI); + return markOverdefined(&EVI); Value *AggVal = EVI.getAggregateOperand(); if (AggVal->getType()->isStructTy()) { @@ -896,19 +902,19 @@ void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { mergeInValue(getValueState(&EVI), &EVI, EltVal); } else { // Otherwise, must be extracting from an array. - return (void)markOverdefined(&EVI); + return markOverdefined(&EVI); } } void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) { auto *STy = dyn_cast(IVI.getType()); if (!STy) - return (void)markOverdefined(&IVI); + return markOverdefined(&IVI); // If this has more than one index, we can't handle it, drive all results to // undef. if (IVI.getNumIndices() != 1) - return (void)markOverdefined(&IVI); + return markOverdefined(&IVI); Value *Aggr = IVI.getAggregateOperand(); unsigned Idx = *IVI.idx_begin(); @@ -937,7 +943,7 @@ void SCCPSolver::visitSelectInst(SelectInst &I) { // If this select returns a struct, just mark the result overdefined. // TODO: We could do a lot better than this if code actually uses this. if (I.getType()->isStructTy()) - return (void)markOverdefined(&I); + return markOverdefined(&I); LatticeVal CondValue = getValueState(I.getCondition()); if (CondValue.isUnknown()) @@ -958,12 +964,12 @@ void SCCPSolver::visitSelectInst(SelectInst &I) { // select ?, C, C -> C. if (TVal.isConstant() && FVal.isConstant() && TVal.getConstant() == FVal.getConstant()) - return (void)markConstant(&I, FVal.getConstant()); + return markConstant(&I, FVal.getConstant()); if (TVal.isUnknown()) // select ?, undef, X -> X. - return (void)mergeInValue(&I, FVal); + return mergeInValue(&I, FVal); if (FVal.isUnknown()) // select ?, X, undef -> X. - return (void)mergeInValue(&I, TVal); + return mergeInValue(&I, TVal); markOverdefined(&I); } @@ -981,7 +987,7 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { // X op Y -> undef. if (isa(C)) return; - return (void)markConstant(IV, &I, C); + return markConstant(IV, &I, C); } // If something is undef, wait for it to resolve. @@ -994,7 +1000,7 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { // 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()); + return markConstant(IV, &I, V1State.getConstant()); // If this is: // -> AND/MUL with 0 @@ -1017,12 +1023,12 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { // X and 0 = 0 // X * 0 = 0 if (NonOverdefVal->getConstant()->isNullValue()) - return (void)markConstant(IV, &I, NonOverdefVal->getConstant()); + return markConstant(IV, &I, NonOverdefVal->getConstant()); } else { // X or -1 = -1 if (ConstantInt *CI = NonOverdefVal->getConstantInt()) if (CI->isMinusOne()) - return (void)markConstant(IV, &I, NonOverdefVal->getConstant()); + return markConstant(IV, &I, NonOverdefVal->getConstant()); } } } @@ -1032,36 +1038,22 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) { // Handle ICmpInst instruction. void SCCPSolver::visitCmpInst(CmpInst &I) { + LatticeVal V1State = getValueState(I.getOperand(0)); + LatticeVal V2State = getValueState(I.getOperand(1)); + LatticeVal &IV = ValueState[&I]; if (IV.isOverdefined()) 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(); - - Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State); - if (C) { + if (V1State.isConstant() && V2State.isConstant()) { + Constant *C = ConstantExpr::getCompare( + I.getPredicate(), V1State.getConstant(), V2State.getConstant()); if (isa(C)) return; - LatticeVal CV; - CV.markConstant(C); - mergeInValue(&I, CV); - return; + return markConstant(IV, &I, C); } // If operands are still unknown, wait for it to resolve. - if (!V1State.isOverdefined() && !V2State.isOverdefined() && !IV.isConstant()) + if (!V1State.isOverdefined() && !V2State.isOverdefined()) return; markOverdefined(&I); @@ -1081,7 +1073,7 @@ void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { return; // Operands are not resolved yet. if (State.isOverdefined()) - return (void)markOverdefined(&I); + return markOverdefined(&I); assert(State.isConstant() && "Unknown state!"); Operands.push_back(State.getConstant()); @@ -1119,7 +1111,7 @@ void SCCPSolver::visitStoreInst(StoreInst &SI) { void SCCPSolver::visitLoadInst(LoadInst &I) { // If this load is of a struct, just mark the result overdefined. if (I.getType()->isStructTy()) - return (void)markOverdefined(&I); + return markOverdefined(&I); LatticeVal PtrVal = getValueState(I.getOperand(0)); if (PtrVal.isUnknown()) return; // The pointer is not resolved yet! @@ -1128,7 +1120,7 @@ void SCCPSolver::visitLoadInst(LoadInst &I) { if (IV.isOverdefined()) return; if (!PtrVal.isConstant() || I.isVolatile()) - return (void)markOverdefined(IV, &I); + return markOverdefined(IV, &I); Constant *Ptr = PtrVal.getConstant(); @@ -1157,7 +1149,7 @@ void SCCPSolver::visitLoadInst(LoadInst &I) { if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL)) { if (isa(C)) return; - return (void)markConstant(IV, &I, C); + return markConstant(IV, &I, C); } // Otherwise we cannot say for certain what value this load will produce. @@ -1189,7 +1181,7 @@ CallOverdefined: if (State.isUnknown()) return; // Operands are not resolved yet. if (State.isOverdefined()) - return (void)markOverdefined(I); + return markOverdefined(I); assert(State.isConstant() && "Unknown state!"); Operands.push_back(State.getConstant()); } @@ -1203,12 +1195,12 @@ CallOverdefined: // call -> undef. if (isa(C)) return; - return (void)markConstant(I, C); + return markConstant(I, C); } } // Otherwise, we don't know anything about this call, mark it overdefined. - return (void)markOverdefined(I); + return markOverdefined(I); } // If this is a local function that doesn't have its address taken, mark its @@ -1236,16 +1228,8 @@ CallOverdefined: } 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); + getParamState(&*AI).mergeIn(getValueState(*CAI).toValueLattice(), DL); + mergeInValue(&*AI, getValueState(*CAI)); } } } @@ -1538,11 +1522,7 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { break; case Instruction::ICmp: // X == undef -> undef. Other comparisons get more complicated. - Op0LV = getValueState(I.getOperand(0)); - Op1LV = getValueState(I.getOperand(1)); - - if ((Op0LV.isUnknown() || Op1LV.isUnknown()) && - cast(&I)->isEquality()) + if (cast(&I)->isEquality()) break; markOverdefined(&I); return true; @@ -1639,6 +1619,45 @@ bool SCCPSolver::ResolvedUndefsIn(Function &F) { return false; } +static bool tryToReplaceWithConstantRange(SCCPSolver &Solver, Value *V) { + bool Changed = false; + + // Currently we only use range information for integer values. + if (!V->getType()->isIntegerTy()) + return false; + + const ValueLatticeElement &IV = Solver.getLatticeValueFor(V); + if (!IV.isConstantRange()) + return false; + + for (auto UI = V->uses().begin(), E = V->uses().end(); UI != E;) { + const Use &U = *UI++; + auto *Icmp = dyn_cast(U.getUser()); + if (!Icmp || !Solver.isBlockExecutable(Icmp->getParent())) + continue; + + auto getIcmpLatticeValue = [&](Value *Op) { + if (auto *C = dyn_cast(Op)) + return ValueLatticeElement::get(C); + return Solver.getLatticeValueFor(Op); + }; + + ValueLatticeElement A = getIcmpLatticeValue(Icmp->getOperand(0)); + ValueLatticeElement B = getIcmpLatticeValue(Icmp->getOperand(1)); + + Constant *C = A.getCompare(Icmp->getPredicate(), Icmp->getType(), B); + if (C) { + Icmp->replaceAllUsesWith(C); + LLVM_DEBUG(dbgs() << "Replacing " << *Icmp << " with " << *C + << ", because of range information " << A << " " << B + << "\n"); + Icmp->eraseFromParent(); + Changed = true; + } + } + return Changed; +} + static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) { Constant *Const = nullptr; if (V->getType()->isStructTy()) { @@ -1656,11 +1675,19 @@ static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) { } Const = ConstantStruct::get(ST, ConstVals); } else { - const LatticeVal &IV = Solver.getLatticeValueFor(V); + const ValueLatticeElement &IV = Solver.getLatticeValueFor(V); if (IV.isOverdefined()) return false; - Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(V->getType()); + if (IV.isConstantRange()) { + if (IV.getConstantRange().isSingleElement()) + Const = + ConstantInt::get(V->getType(), IV.asConstantInteger().getValue()); + else + return false; + } else + Const = + IV.isConstant() ? IV.getConstant() : UndefValue::get(V->getType()); } assert(Const && "Constant is nullptr here!"); @@ -1901,6 +1928,9 @@ bool llvm::runIPSCCP(Module &M, const DataLayout &DL, ++IPNumArgsElimed; continue; } + + if (!AI->use_empty() && tryToReplaceWithConstantRange(Solver, &*AI)) + ++IPNumRangeInfoUsed; } for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { diff --git a/test/Transforms/SCCP/ip-constant-ranges.ll b/test/Transforms/SCCP/ip-constant-ranges.ll index 704ea97179b..22a239d1208 100644 --- a/test/Transforms/SCCP/ip-constant-ranges.ll +++ b/test/Transforms/SCCP/ip-constant-ranges.ll @@ -2,7 +2,11 @@ ; Constant range for %a is [1, 48) and for %b is [301, 1000) ; CHECK-LABEL: f1 -; CHECK: ret i32 undef +; CHECK-NOT: icmp +; CHECK: %a.1 = select i1 false, i32 1, i32 2 +; CHECK: %b.1 = select i1 true, i32 1, i32 2 +; CHECK: %a.2 = select i1 false, i32 1, i32 2 +; CHECK: %b.2 = select i1 true, i32 1, i32 2 define internal i32 @f1(i32 %a, i32 %b) { entry: %cmp.a = icmp sgt i32 %a, 300 @@ -24,11 +28,10 @@ entry: ; CHECK-LABEL: f2 ; CHECK: %cmp = icmp sgt i32 %x, 300 ; CHECK: %res1 = select i1 %cmp, i32 1, i32 2 +; CHECK-NEXT: %res2 = select i1 true, i32 3, i32 4 +; CHECK-NEXT: %res3 = select i1 true, i32 5, i32 6 ; CHECK-NEXT: %res4 = select i1 %cmp4, i32 3, i32 4 -; CHECK-NEXT: %res6 = add i32 %res1, 3 -; CHECK-NEXT: %res7 = add i32 5, %res4 -; CHECK-NEXT: %res = add i32 %res6, 5 -; CHECK-NEXT: ret i32 %res +; CHECK-NEXT: %res5 = select i1 true, i32 5, i32 6 define internal i32 @f2(i32 %x) { entry: %cmp = icmp sgt i32 %x, 300 @@ -54,7 +57,8 @@ entry: %call2 = tail call i32 @f1(i32 47, i32 999) %call3 = tail call i32 @f2(i32 47) %call4 = tail call i32 @f2(i32 301) - %res.1 = add nsw i32 12, %call3 + %res = add nsw i32 %call1, %call2 + %res.1 = add nsw i32 %res, %call3 %res.2 = add nsw i32 %res.1, %call4 ret i32 %res.2 } @@ -141,9 +145,9 @@ define double @test_struct({ double, double } %test) { ; Constant range for %x is [47, 302) ; CHECK-LABEL: @f5 ; CHECK-NEXT: entry: -; CHECK-NEXT: %cmp = icmp sgt i32 %x, undef -; CHECK-NEXT: %res1 = select i1 %cmp, i32 1, i32 2 -; CHECK-NEXT: %res = add i32 %res1, 3 +; CHECK-NEXT: %res1 = select i1 undef, i32 1, i32 2 +; CHECK-NEXT: %res2 = select i1 undef, i32 3, i32 4 +; CHECK-NEXT: %res = add i32 %res1, %res2 ; CHECK-NEXT: ret i32 %res define internal i32 @f5(i32 %x) { entry: @@ -163,36 +167,3 @@ entry: %res = add nsw i32 %call1, %call2 ret i32 %res } - -; Make sure we do re-evaluate the function after ParamState changes. -; CHECK-LABEL: @recursive_f -; CHECK-LABEL: entry: -; CHECK: %cmp = icmp eq i32 %i, 0 -; CHECK-NEXT: br i1 %cmp, label %if.then, label %if.else -define internal i32 @recursive_f(i32 %i) { -entry: - %cmp = icmp eq i32 %i, 0 - br i1 %cmp, label %if.then, label %if.else - -if.then: ; preds = %entry - br label %return - -if.else: ; preds = %entry - %sub = sub nsw i32 %i, 1 - %call = call i32 @recursive_f(i32 %sub) - %add = add i32 %i, %call - br label %return - -return: ; preds = %if.else, %if.then - %retval.0 = phi i32 [ 0, %if.then ], [ %add, %if.else ] - ret i32 %retval.0 -} - -; CHECK-LABEL: @caller5 -; CHECK: %call = call i32 @recursive_f(i32 42) -; CHECK-NEXT: ret i32 %call -define i32 @caller5() { -entry: - %call = call i32 @recursive_f(i32 42) - ret i32 %call -} -- 2.50.1