Index: include/llvm/Analysis/ValueLattice.h =================================================================== --- /dev/null +++ include/llvm/Analysis/ValueLattice.h @@ -0,0 +1,263 @@ +//===- ValueLattice.h - Value constraint analysis ---------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the interface for lazy computation of value constraint +// information. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_VALUELATTICE_H +#define LLVM_ANALYSIS_VALUELATTICE_H + +#include "llvm/IR/ConstantRange.h" +#include "llvm/IR/Constants.h" + +namespace llvm { +class LVILatticeVal { + enum LatticeValueTy { + /// This Value has no known value yet. As a result, this implies the + /// producing instruction is dead. Caution: We use this as the starting + /// state in our local meet rules. In this usage, it's taken to mean + /// "nothing known yet". + undefined, + + /// This Value has a specific constant value. (For constant integers, + /// constantrange is used instead. Integer typed constantexprs can appear + /// as constant.) + constant, + + /// This Value is known to not have the specified value. (For constant + /// integers, constantrange is used instead. As above, integer typed + /// constantexprs can appear here.) + notconstant, + + /// The Value falls within this range. (Used only for integer typed values.) + constantrange, + + /// We can not precisely model the dynamic values this value might take. + overdefined + }; + + /// Val: This stores the current lattice value along with the Constant* for + /// the constant if this is a 'constant' or 'notconstant' value. + LatticeValueTy Tag; + Constant *Val; + ConstantRange Range; + +public: + LVILatticeVal() : Tag(undefined), Val(nullptr), Range(1, true) {} + + static LVILatticeVal get(Constant *C) { + LVILatticeVal Res; + if (!isa(C)) + Res.markConstant(C); + return Res; + } + static LVILatticeVal getNot(Constant *C) { + LVILatticeVal Res; + if (!isa(C)) + Res.markNotConstant(C); + return Res; + } + static LVILatticeVal getRange(ConstantRange CR) { + LVILatticeVal Res; + Res.markConstantRange(std::move(CR)); + return Res; + } + static LVILatticeVal getOverdefined() { + LVILatticeVal Res; + Res.markOverdefined(); + return Res; + } + + bool isUndefined() const { return Tag == undefined; } + bool isConstant() const { return Tag == constant; } + bool isNotConstant() const { return Tag == notconstant; } + bool isConstantRange() const { return Tag == constantrange; } + bool isOverdefined() const { return Tag == overdefined; } + + Constant *getConstant() const { + assert(isConstant() && "Cannot get the constant of a non-constant!"); + return Val; + } + + Constant *getNotConstant() const { + assert(isNotConstant() && "Cannot get the constant of a non-notconstant!"); + return Val; + } + + const ConstantRange &getConstantRange() const { + assert(isConstantRange() && + "Cannot get the constant-range of a non-constant-range!"); + return Range; + } + + Optional asConstantInteger() const { + if (isConstant() && isa(Val)) { + return cast(Val)->getValue(); + } else if (isConstantRange() && Range.isSingleElement()) { + return *Range.getSingleElement(); + } + return None; + } + +private: + void markOverdefined() { + if (isOverdefined()) + return; + Tag = overdefined; + } + + void markConstant(Constant *V) { + assert(V && "Marking constant with NULL"); + if (ConstantInt *CI = dyn_cast(V)) { + markConstantRange(ConstantRange(CI->getValue())); + return; + } + if (isa(V)) + return; + + assert((!isConstant() || getConstant() == V) && + "Marking constant with different value"); + assert(isUndefined()); + Tag = constant; + Val = V; + } + + void markNotConstant(Constant *V) { + assert(V && "Marking constant with NULL"); + if (ConstantInt *CI = dyn_cast(V)) { + markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue())); + return; + } + if (isa(V)) + return; + + assert((!isConstant() || getConstant() != V) && + "Marking constant !constant with same value"); + assert((!isNotConstant() || getNotConstant() == V) && + "Marking !constant with different value"); + assert(isUndefined() || isConstant()); + Tag = notconstant; + Val = V; + } + + void markConstantRange(ConstantRange NewR) { + if (isConstantRange()) { + if (NewR.isEmptySet()) + markOverdefined(); + else { + Range = std::move(NewR); + } + return; + } + + assert(isUndefined()); + if (NewR.isEmptySet()) + markOverdefined(); + else { + Tag = constantrange; + Range = std::move(NewR); + } + } + +public: + + /// Merge the specified lattice value into this one, updating this + /// one and returning true if anything changed. + bool mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) { + if (RHS.isUndefined() || isOverdefined()) + return false; + if (RHS.isOverdefined()) { + markOverdefined(); + return true; + } + + if (isUndefined()) { + *this = RHS; + return !RHS.isUndefined(); + } + + if (isConstant()) { + if (RHS.isConstant() && Val == RHS.Val) + return false; + markOverdefined(); + return true; + } + + if (isNotConstant()) { + if (RHS.isNotConstant() && Val == RHS.Val) + return false; + markOverdefined(); + return true; + } + + assert(isConstantRange() && "New LVILattice type?"); + if (!RHS.isConstantRange()) { + // We can get here if we've encountered a constantexpr of integer type + // and merge it with a constantrange. + markOverdefined(); + return true; + } + ConstantRange NewR = Range.unionWith(RHS.getConstantRange()); + if (NewR.isFullSet()) + markOverdefined(); + else + markConstantRange(std::move(NewR)); + return true; + } + + ConstantInt *getConstantInt() const { + assert(isConstant() && isa(getConstant()) && + "No integer constant"); + return cast(getConstant()); + } + + bool satisfiesPredicate(CmpInst::Predicate Pred, + const LVILatticeVal &Other) const { + // TODO: share with LVI getPredicateResult. + // Integer constants are represented as ConstantRanges with single + // elements. + if (!isConstantRange() || !Other.isConstantRange()) + return false; + + const auto &CR = getConstantRange(); + const auto &OtherCR = Other.getConstantRange(); + switch (Pred) { + case CmpInst::ICMP_NE: + return CR.intersectWith(OtherCR).isEmptySet(); + case CmpInst::ICMP_EQ: + return CR.isSingleElement() && OtherCR.isSingleElement() && + CR == OtherCR; + default: + return ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR); + } + } + +}; +raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) + LLVM_ATTRIBUTE_USED; +raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) { + if (Val.isUndefined()) + return OS << "undefined"; + if (Val.isOverdefined()) + return OS << "overdefined"; + + if (Val.isNotConstant()) + return OS << "notconstant<" << *Val.getNotConstant() << '>'; + if (Val.isConstantRange()) + return OS << "constantrange<" << Val.getConstantRange().getLower() << ", " + << Val.getConstantRange().getUpper() << '>'; + return OS << "constant<" << *Val.getConstant() << '>'; +} + + +} // end namespace llvm + +#endif Index: lib/Transforms/Scalar/SCCP.cpp =================================================================== --- lib/Transforms/Scalar/SCCP.cpp +++ lib/Transforms/Scalar/SCCP.cpp @@ -25,6 +25,7 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/ValueLattice.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/IR/CallSite.h" @@ -153,6 +154,14 @@ Val.setInt(forcedconstant); Val.setPointer(V); } + + LVILatticeVal toLVI() const { + if (isOverdefined()) + return LVILatticeVal::getOverdefined(); + if (isConstant()) + return LVILatticeVal::get(getConstant()); + return LVILatticeVal(); + } }; } // end anonymous namespace. @@ -169,6 +178,7 @@ const TargetLibraryInfo *TLI; SmallPtrSet BBExecutable; // The BBs that are executable. DenseMap ValueState; // The state each value is in. + DenseMap ParamState; // The state each parameter is in. /// StructValueState - This maintains ValueState for values that have /// StructType, for example for formal arguments, calls, insertelement, etc. @@ -290,10 +300,15 @@ 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; + LVILatticeVal getLatticeValueFor(Value *V) { + if (ParamState.count(V) == 0) { + DenseMap::const_iterator I = ValueState.find(V); + assert(I != ValueState.end() && + "V not found in ValueState nor Paramstate map!"); + ParamState[V] = I->second.toLVI(); + } + + return ParamState[V]; } /// getTrackedRetVals - Get the inferred return value map. @@ -426,6 +441,15 @@ return LV; } + LVILatticeVal &getParamState(Value *V) { + assert(!V->getType()->isStructTy() && "Should use getStructValueState"); + + if (ParamState.count(V) == 0) + ParamState[V] = getValueState(V).toLVI(); + + return ParamState[V]; + } + /// 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. @@ -1162,6 +1186,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).toLVI(), DL); mergeInValue(&*AI, getValueState(*CAI)); } } @@ -1557,8 +1584,9 @@ return false; } -static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) { +static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V, SmallPtrSet &ToRemove) { Constant *Const = nullptr; + bool Changed = false; if (V->getType()->isStructTy()) { std::vector IVs = Solver.getStructLatticeValueFor(V); if (any_of(IVs, [](const LatticeVal &LV) { return LV.isOverdefined(); })) @@ -1572,18 +1600,52 @@ : UndefValue::get(ST->getElementType(i))); } Const = ConstantStruct::get(ST, ConstVals); + Changed = true; } else { - LatticeVal IV = Solver.getLatticeValueFor(V); + const LVILatticeVal &IV = Solver.getLatticeValueFor(V); if (IV.isOverdefined()) return false; - Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(V->getType()); + + if (V->getType()->isIntegerTy() && + (IV.isConstantRange())) { + for (auto &Use : V->uses()) { + if (auto *Icmp = dyn_cast(Use.getUser())) { + 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"); + ToRemove.insert(Icmp); + Changed = true; + } + } + } + } + if (IV.isConstantRange()) { + if(IV.getConstantRange().isSingleElement()) + Const = ConstantInt::get(V->getType(), IV.asConstantInteger().getValue()); + else + return Changed; + } else + Const = IV.isConstant() ? IV.getConstant() : + UndefValue::get(V->getType()); + + Changed = true; } assert(Const && "Constant is nullptr here!"); DEBUG(dbgs() << " Constant: " << *Const << " = " << *V << '\n'); // Replaces all of the uses of a variable with uses of the constant. V->replaceAllUsesWith(Const); - return true; + return Changed; } // runSCCP() - Run the Sparse Conditional Constant Propagation algorithm, @@ -1629,19 +1691,23 @@ // Iterate over all of the instructions in a function, replacing them with // constants if we have found them to be of constant values. // + SmallPtrSet ToRemove; for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) { Instruction *Inst = &*BI++; if (Inst->getType()->isVoidTy() || isa(Inst)) continue; - if (tryToReplaceWithConstant(Solver, Inst)) { + if (tryToReplaceWithConstant(Solver, Inst, ToRemove)) { if (isInstructionTriviallyDead(Inst)) - Inst->eraseFromParent(); - // Hey, we just changed something! - MadeChanges = true; - ++NumInstRemoved; + ToRemove.insert(Inst); } } + for (auto *Inst : ToRemove) { + Inst->eraseFromParent(); + // Hey, we just changed something! + MadeChanges = true; + ++IPNumInstRemoved; + } } return MadeChanges; @@ -1816,12 +1882,20 @@ if (F.isDeclaration()) continue; - if (Solver.isBlockExecutable(&F.front())) + if (Solver.isBlockExecutable(&F.front())) { + SmallPtrSet ToRemove; for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E; ++AI) - if (!AI->use_empty() && tryToReplaceWithConstant(Solver, &*AI)) + if (!AI->use_empty() && tryToReplaceWithConstant(Solver, &*AI, + ToRemove)) ++IPNumArgsElimed; + for (auto *Inst : ToRemove) { + Inst->eraseFromParent(); + ++IPNumInstRemoved; + } + } + for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { if (!Solver.isBlockExecutable(&*BB)) { DEBUG(dbgs() << " BasicBlock Dead:" << *BB); @@ -1837,18 +1911,23 @@ continue; } + + SmallPtrSet ToRemove; for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { Instruction *Inst = &*BI++; if (Inst->getType()->isVoidTy()) continue; - if (tryToReplaceWithConstant(Solver, Inst)) { + if (tryToReplaceWithConstant(Solver, Inst, ToRemove)) { if (!isa(Inst) && !isa(Inst)) - Inst->eraseFromParent(); - // Hey, we just changed something! - MadeChanges = true; - ++IPNumInstRemoved; + ToRemove.insert(Inst); } } + for (auto *Inst : ToRemove) { + Inst->eraseFromParent(); + // Hey, we just changed something! + MadeChanges = true; + ++IPNumInstRemoved; + } } // Now that all instructions in the function are constant folded, erase dead Index: test/Transforms/SCCP/ip-constan-ranges.ll =================================================================== --- /dev/null +++ test/Transforms/SCCP/ip-constan-ranges.ll @@ -0,0 +1,117 @@ +; 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 +}