Index: lib/Transforms/Scalar/SCCP.cpp =================================================================== --- lib/Transforms/Scalar/SCCP.cpp +++ lib/Transforms/Scalar/SCCP.cpp @@ -30,6 +30,7 @@ #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/Analysis/ValueLattice.h" #include "llvm/Analysis/ValueLatticeUtils.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CallSite.h" @@ -70,6 +71,8 @@ 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 { @@ -174,6 +177,14 @@ Val.setInt(forcedconstant); Val.setPointer(V); } + + ValueLatticeElement toValueLattice() const { + if (isOverdefined()) + return ValueLatticeElement::getOverdefined(); + if (isConstant()) + return ValueLatticeElement::get(getConstant()); + return ValueLatticeElement(); + } }; //===----------------------------------------------------------------------===// @@ -186,6 +197,8 @@ 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; /// StructValueState - This maintains ValueState for values that have /// StructType, for example for formal arguments, calls, insertelement, etc. @@ -312,10 +325,18 @@ return StructValues; } - LatticeVal getLatticeValueFor(Value *V) const { - DenseMap::const_iterator I = ValueState.find(V); - assert(I != ValueState.end() && "V is not in valuemap!"); - return I->second; + ValueLatticeElement getLatticeValueFor(Value *V) { + 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. @@ -444,6 +465,18 @@ 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. @@ -1170,6 +1203,9 @@ 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. + getParamState(&*AI).mergeIn(getValueState(*CAI).toValueLattice(), DL); mergeInValue(&*AI, getValueState(*CAI)); } } @@ -1560,6 +1596,43 @@ return false; } +static bool tryToReplaceWithConstantRange(SCCPSolver &Solver, Value *V) { + bool Changed = false; + + const ValueLatticeElement &IV = Solver.getLatticeValueFor(V); + if (IV.isOverdefined()) + return false; + + // Currently we only use range information for integer values. + if (!(V->getType()->isIntegerTy() && 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 A = Solver.getLatticeValueFor(Icmp->getOperand(0)); + auto B = Solver.getLatticeValueFor(Icmp->getOperand(1)); + Constant *C = nullptr; + if (A.satisfiesPredicate(Icmp->getPredicate(), B)) + C = ConstantInt::getTrue(Icmp->getType()); + else if (A.satisfiesPredicate(Icmp->getInversePredicate(), B)) + C = ConstantInt::getFalse(Icmp->getType()); + + if (C) { + Icmp->replaceAllUsesWith(C); + 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()) { @@ -1577,10 +1650,19 @@ } Const = ConstantStruct::get(ST, ConstVals); } else { - 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!"); DEBUG(dbgs() << " Constant: " << *Const << " = " << *V << '\n'); @@ -1781,10 +1863,14 @@ if (Solver.isBlockExecutable(&F.front())) for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E; - ++AI) + ++AI) { if (!AI->use_empty() && tryToReplaceWithConstant(Solver, &*AI)) ++IPNumArgsElimed; + if (!AI->use_empty() && tryToReplaceWithConstantRange(Solver, &*AI)) + ++IPNumRangeInfoUsed; + } + for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { if (!Solver.isBlockExecutable(&*BB)) { DEBUG(dbgs() << " BasicBlock Dead:" << *BB); Index: test/Transforms/SCCP/ip-constan-ranges.ll =================================================================== --- /dev/null +++ test/Transforms/SCCP/ip-constan-ranges.ll @@ -0,0 +1,135 @@ +; RUN: opt < %s -ipsccp -S | FileCheck %s + +; Constant range for %a is [1, 48) and for %b is [301, 1000) +; CHECK-LABEL: f1 +; 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 + %cmp.b = icmp sgt i32 %b, 300 + %cmp.a2 = icmp ugt i32 %a, 300 + %cmp.b2 = icmp ugt i32 %b, 300 + + %a.1 = select i1 %cmp.a, i32 1, i32 2 + %b.1 = select i1 %cmp.b, i32 1, i32 2 + %a.2 = select i1 %cmp.a2, i32 1, i32 2 + %b.2 = select i1 %cmp.b2, i32 1, i32 2 + %res1 = add i32 %a.1, %b.1 + %res2 = add i32 %a.2, %b.2 + %res3 = add i32 %res1, %res2 + ret i32 %res3 +} + +; Constant range for %x is [47, 302) +; 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: %res5 = select i1 true, i32 5, i32 6 +define internal i32 @f2(i32 %x) { +entry: + %cmp = icmp sgt i32 %x, 300 + %cmp2 = icmp ne i32 %x, 10 + %cmp3 = icmp sge i32 %x, 47 + %cmp4 = icmp ugt i32 %x, 300 + %cmp5 = icmp uge i32 %x, 47 + %res1 = select i1 %cmp, i32 1, i32 2 + %res2 = select i1 %cmp2, i32 3, i32 4 + %res3 = select i1 %cmp3, i32 5, i32 6 + %res4 = select i1 %cmp4, i32 3, i32 4 + %res5 = select i1 %cmp5, i32 5, i32 6 + + %res6 = add i32 %res1, %res2 + %res7 = add i32 %res3, %res4 + %res = add i32 %res6, %res5 + ret i32 %res +} + +define i32 @caller1() { +entry: + %call1 = tail call i32 @f1(i32 1, i32 301) + %call2 = tail call i32 @f1(i32 47, i32 999) + %call3 = tail call i32 @f2(i32 47) + %call4 = tail call i32 @f2(i32 301) + %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 +} + +; 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 +define internal i32 @f3(i32 %x) { +entry: + %cmp = icmp sgt i32 %x, 300 + %res = select i1 %cmp, i32 1, i32 2 + ret i32 %res +} + +; The phi node could be converted in a ConstantRange. +define i32 @caller2(i1 %cmp) { +entry: + br i1 %cmp, label %if.true, label %end + +if.true: + br label %end + +end: + %res = phi i32 [ 0, %entry], [ 1, %if.true ] + %call1 = tail call i32 @f3(i32 %res) + ret i32 %call1 +} + +; CHECK-LABEL: f4 +; CHECK: %cmp = icmp sgt i32 %x, 300 +; CHECK: %res = select i1 %cmp, i32 1, i32 2 +; CHECK: ret i32 %res +define internal i32 @f4(i32 %x) { +entry: + %cmp = icmp sgt i32 %x, 300 + %res = select i1 %cmp, i32 1, i32 2 + ret i32 %res +} + +; ICmp could introduce bounds on ConstantRanges. +define i32 @caller3(i32 %x) { +entry: + %cmp = icmp sgt i32 %x, 300 + br i1 %cmp, label %if.true, label %end + +if.true: + %x.1 = tail call i32 @f4(i32 %x) + br label %end + +end: + %res = phi i32 [ 0, %entry], [ %x.1, %if.true ] + ret i32 %res +} + +; Check to make sure we do not attempt to access lattice values in unreachable +; blocks. +define i32 @test_unreachable() { +entry: + call i1 @test_unreachable_callee(i32 1) + call i1 @test_unreachable_callee(i32 2) + ret i32 1 +} + +define internal i1 @test_unreachable_callee(i32 %a) { +entry: + ret i1 true + +unreachablebb: + %cmp = icmp eq i32 undef, %a + unreachable +}