Index: include/llvm/Analysis/ValueLattice.h =================================================================== --- /dev/null +++ include/llvm/Analysis/ValueLattice.h @@ -0,0 +1,252 @@ +//===- 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. + void mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) { + if (RHS.isUndefined() || isOverdefined()) + return; + if (RHS.isOverdefined()) { + markOverdefined(); + return; + } + + if (isUndefined()) { + *this = RHS; + return; + } + + if (isConstant()) { + if (RHS.isConstant() && Val == RHS.Val) + return; + markOverdefined(); + return; + } + + if (isNotConstant()) { + if (RHS.isNotConstant() && Val == RHS.Val) + return; + markOverdefined(); + return; + } + + 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; + } + ConstantRange NewR = Range.unionWith(RHS.getConstantRange()); + if (NewR.isFullSet()) + markOverdefined(); + else + markConstantRange(std::move(NewR)); + } + + ConstantInt *getConstantInt() const { + assert(isConstant() && isa(getConstant()) && + "No integer constant"); + return cast(getConstant()); + } + + bool satisfiesPredicate(CmpInst::Predicate Pred, + const LVILatticeVal &Other) const { + // Integer constants are represented as ConstantRanges with single + // elements. + if (!isConstantRange() || !Other.isConstantRange()) + return false; + + return getConstantRange().satisfiesPredicate(Pred, + Other.getConstantRange()); + } + +}; +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: include/llvm/IR/ConstantRange.h =================================================================== --- include/llvm/IR/ConstantRange.h +++ include/llvm/IR/ConstantRange.h @@ -316,6 +316,10 @@ /// Return a new range that is the logical not of the current set. ConstantRange inverse() const; + /// Returns true if the range satisfies Pred when compared with Other. + bool satisfiesPredicate(CmpInst::Predicate Pred, + const ConstantRange &Other) const; + /// Print out the bounds to a stream. void print(raw_ostream &OS) const; Index: lib/IR/ConstantRange.cpp =================================================================== --- lib/IR/ConstantRange.cpp +++ lib/IR/ConstantRange.cpp @@ -930,6 +930,18 @@ return ConstantRange(Upper, Lower); } +bool ConstantRange::satisfiesPredicate(CmpInst::Predicate Pred, + const ConstantRange &Other) const { + switch (Pred) { + case CmpInst::ICMP_SGT: + return getLower().sge(Other.getUpper()); + case CmpInst::ICMP_SLE: + return getUpper().slt(Other.getLower()); + default: + return false; + } +} + void ConstantRange::print(raw_ostream &OS) const { if (isFullSet()) OS << "full-set"; 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" @@ -169,6 +170,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. @@ -220,6 +222,22 @@ SCCPSolver(const DataLayout &DL, const TargetLibraryInfo *tli) : DL(DL), TLI(tli) {} + LVILatticeVal &getParamState(Value *V) { + assert(!V->getType()->isStructTy() && "Should use getStructValueState"); + + if (ParamState.count(V) == 0) { + LVILatticeVal Val; + if (auto *C = dyn_cast(V)) { + // Undef values remain unknown. + if (!isa(V)) + Val = LVILatticeVal::get(C); + } + ParamState[V] = Val; + } + + return ParamState[V]; + } + /// MarkBlockExecutable - This method can be used by clients to mark all of /// the blocks that are known to be intrinsically live in the processed unit. /// @@ -290,10 +308,21 @@ 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!"); + auto VS = I->second; + LVILatticeVal LVI; + if (VS.isOverdefined()) + LVI = LVILatticeVal::getOverdefined(); + if (VS.isConstant()) + LVI = LVILatticeVal::get(VS.getConstant()); + ParamState[V] = LVI; + } + + return ParamState[V]; } /// getTrackedRetVals - Get the inferred return value map. @@ -1162,6 +1191,13 @@ mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg); } } else { + auto ActualArgState = getValueState(*CAI); + LVILatticeVal AS; + if (ActualArgState.isOverdefined()) + AS = LVILatticeVal::getOverdefined(); + if (ActualArgState.isConstant()) + AS = LVILatticeVal::get(ActualArgState.getConstant()); + getParamState(&*AI).mergeIn(AS, DL); mergeInValue(&*AI, getValueState(*CAI)); } } @@ -1559,6 +1595,7 @@ static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) { 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 +1609,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"); + Icmp->eraseFromParent(); + 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, Index: test/Transforms/SCCP/ip-constan-ranges.ll =================================================================== --- /dev/null +++ test/Transforms/SCCP/ip-constan-ranges.ll @@ -0,0 +1,95 @@ +; RUN: opt < %s -ipsccp -S | FileCheck %s + +define internal i32 @f1(i32 %a, i32 %b) { +entry: + %cmp.a = icmp sgt i32 %a, 300 + %cmp.b = icmp sgt i32 %b, 300 + %a.1 = select i1 %cmp.a, i32 1, i32 2 + %b.1 = select i1 %cmp.b, i32 1, i32 2 + %res = add i32 %a.1, %b.1 + ret i32 %res +} +; Constant range for %x is [1, 47], icmp evaluates to false. +; 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 + +define internal i32 @f2(i32 %x) { +entry: + %cmp = icmp sgt i32 %x, 300 + %res = select i1 %cmp, i32 1, i32 2 + ret i32 %res +} +; Constant range for %x is [47, 301], so neither %x > 300 or %x <= 300 is +; satisfied. +; CHECK-LABEL: f2 +; CHECK: %cmp = icmp sgt i32 %x, 300 +; CHECK: %res = select i1 %cmp, i32 1, i32 2 +; CHECK: 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 +} + +define internal i32 @f3(i32 %x) { +entry: + %cmp = icmp sgt i32 %x, 300 + %res = select i1 %cmp, i32 1, i32 2 + ret i32 %res +} +; 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 + +; 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 +} + +define internal i32 @f4(i32 %x) { +entry: + %cmp = icmp sgt i32 %x, 300 + %res = select i1 %cmp, i32 1, i32 2 + ret i32 %res +} +; CHECK-LABEL: f4 +; CHECK: %cmp = icmp sgt i32 %x, 300 +; CHECK: %res = select i1 %cmp, i32 1, i32 2 +; CHECK: 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 +}