Index: lib/Transforms/Scalar/SCCP.cpp
===================================================================
--- lib/Transforms/Scalar/SCCP.cpp
+++ lib/Transforms/Scalar/SCCP.cpp
@@ -33,6 +33,7 @@
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IRBuilder.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
@@ -73,29 +74,38 @@
/// overdefined - This instruction is not known to be constant, and we know
/// it has a value.
- overdefined
+ overdefined,
+
+ range
};
/// Val: This stores the current lattice value along with the Constant* for
/// the constant if this is a 'constant' or 'forcedconstant' value.
- PointerIntPair<Constant *, 2, LatticeValueTy> Val;
+ LatticeValueTy Ty;
+
+ Constant *ConstPtr;
+ std::pair<long, long> ConstRange;
LatticeValueTy getLatticeValue() const {
- return Val.getInt();
+ return Ty;
}
public:
- LatticeVal() : Val(nullptr, unknown) {}
+ LatticeVal() : Ty(unknown), ConstPtr(nullptr), ConstRange() {}
bool isUnknown() const { return getLatticeValue() == unknown; }
bool isConstant() const {
return getLatticeValue() == constant || getLatticeValue() == forcedconstant;
}
+ bool isRange() const {
+ return getLatticeValue() == range;
+ }
+
bool isOverdefined() const { return getLatticeValue() == overdefined; }
Constant *getConstant() const {
assert(isConstant() && "Cannot get the constant of a non-constant!");
- return Val.getPointer();
+ return ConstPtr;
}
/// markOverdefined - Return true if this is a change in status.
@@ -103,10 +113,34 @@
if (isOverdefined())
return false;
- Val.setInt(overdefined);
+ Ty = overdefined;
return true;
}
+ bool isRangeOrConstantInt() const {
+ if (getLatticeValue() == constant)
+ return isa<ConstantInt>(getConstant());
+ return getLatticeValue() == range;
+ }
+
+ long getRangeLower() const {
+ assert(isRangeOrConstantInt());
+ if (getLatticeValue() == constant) {
+ auto *C = dyn_cast<ConstantInt>(getConstant());
+ return (C->isNegative() ? (-1) : 1) * C->getLimitedValue();
+ }
+ return ConstRange.first;
+ }
+
+ long getRangeUpper() const {
+ assert(isRangeOrConstantInt());
+ if (getLatticeValue() == constant) {
+ auto *C = dyn_cast<ConstantInt>(getConstant());
+ return (C->isNegative() ? (-1) : 1) * C->getLimitedValue();
+ }
+ return ConstRange.second;
+ }
+
/// markConstant - Return true if this is a change in status.
bool markConstant(Constant *V) {
if (getLatticeValue() == constant) { // Constant but not forcedconstant.
@@ -115,9 +149,9 @@
}
if (isUnknown()) {
- Val.setInt(constant);
+ Ty = constant;
assert(V && "Marking constant with NULL");
- Val.setPointer(V);
+ ConstPtr= V;
} else {
assert(getLatticeValue() == forcedconstant &&
"Cannot move from overdefined to constant!");
@@ -127,11 +161,23 @@
// 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);
+ Ty = overdefined;
}
return true;
}
+ /// markConstant - Return true if this is a change in status.
+ bool markRange(Value *V, long low, long upper) {
+ if (getLatticeValue() == range && getRangeLower() == low && getRangeUpper() == upper)
+ return false;
+
+ ConstRange.first = low;
+ ConstRange.second = upper;
+ Ty = range;
+ return true;
+ }
+
+
/// getConstantInt - If this is a constant with a ConstantInt value, return it
/// otherwise return null.
ConstantInt *getConstantInt() const {
@@ -150,8 +196,8 @@
void markForcedConstant(Constant *V) {
assert(isUnknown() && "Can't force a defined value!");
- Val.setInt(forcedconstant);
- Val.setPointer(V);
+ Ty = forcedconstant;
+ ConstPtr= V;
}
};
} // end anonymous namespace.
@@ -165,6 +211,7 @@
/// Constant Propagation.
///
class SCCPSolver : public InstVisitor<SCCPSolver> {
+ public:
const DataLayout &DL;
const TargetLibraryInfo *TLI;
SmallPtrSet<BasicBlock*, 8> BBExecutable; // The BBs that are executable.
@@ -290,7 +337,7 @@
return StructValues;
}
- LatticeVal getLatticeValueFor(Value *V) const {
+ const LatticeVal& getLatticeValueFor(Value *V) const {
DenseMap<Value*, LatticeVal>::const_iterator I = ValueState.find(V);
assert(I != ValueState.end() && "V is not in valuemap!");
return I->second;
@@ -361,6 +408,18 @@
markConstant(ValueState[V], V, C);
}
+ void markRange(LatticeVal &IV, Value *V, long lower, long upper) {
+ if (!IV.markRange(V, lower, upper)) return;
+ DEBUG(dbgs() << "markRange: (" << lower << ", " << upper << ") : " << *V << '\n');
+ pushToWorkList(IV, V);
+ }
+
+ void markRange(Value *V, long lower, long upper) {
+ assert(V->getType()->isIntegerTy() && "structs should use mergeInValue");
+ markRange(ValueState[V], V, lower, upper);
+ }
+
+
void markForcedConstant(Value *V, Constant *C) {
assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
LatticeVal &IV = ValueState[V];
@@ -392,8 +451,22 @@
return markOverdefined(IV, V);
if (IV.isUnknown())
return markConstant(IV, V, MergeWithV.getConstant());
- if (IV.getConstant() != MergeWithV.getConstant())
- return markOverdefined(IV, V);
+ if (IV.isConstant() && MergeWithV.isConstant() && IV.getConstant() != MergeWithV.getConstant()) {
+ if (IV.isRangeOrConstantInt() && MergeWithV.isRangeOrConstantInt())
+ return markRange(V, std::min(IV.getRangeLower(),
+ MergeWithV.getRangeLower()),
+ std::max(IV.getRangeUpper(),
+ MergeWithV.getRangeUpper()));
+ else
+ return markOverdefined(IV, V);
+ }
+ if (IV.isRangeOrConstantInt() && MergeWithV.isRangeOrConstantInt())
+ return markRange(V, std::min(IV.getRangeLower(),
+ MergeWithV.getRangeLower()),
+ std::max(IV.getRangeUpper(),
+ MergeWithV.getRangeUpper()));
+
+ return markOverdefined(IV, V);
}
void mergeInValue(Value *V, LatticeVal MergeWithV) {
@@ -402,7 +475,6 @@
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.
@@ -1573,9 +1645,10 @@
}
Const = ConstantStruct::get(ST, ConstVals);
} else {
- LatticeVal IV = Solver.getLatticeValueFor(V);
- if (IV.isOverdefined())
+ const LatticeVal &IV = Solver.getLatticeValueFor(V);
+ if (IV.isOverdefined() || IV.isRange()) {
return false;
+ }
Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(V->getType());
}
assert(Const && "Constant is nullptr here!");
@@ -1607,6 +1680,7 @@
Solver.Solve();
DEBUG(dbgs() << "RESOLVING UNDEFs\n");
ResolvedUndefs = Solver.ResolvedUndefsIn(F);
+
}
bool MadeChanges = false;
@@ -1635,10 +1709,6 @@
continue;
if (tryToReplaceWithConstant(Solver, Inst)) {
- if (isInstructionTriviallyDead(Inst))
- Inst->eraseFromParent();
- // Hey, we just changed something!
- MadeChanges = true;
++NumInstRemoved;
}
}
@@ -1801,8 +1871,9 @@
DEBUG(dbgs() << "RESOLVING UNDEFS\n");
ResolvedUndefs = false;
- for (Function &F : M)
+ for (Function &F : M) {
ResolvedUndefs |= Solver.ResolvedUndefsIn(F);
+ }
}
bool MadeChanges = false;
@@ -1818,9 +1889,30 @@
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() && AI->getType()->isIntegerTy()) {
+ const LatticeVal &IV = Solver.getLatticeValueFor(&*AI);
+ if (IV.isOverdefined())
+ continue;
+
+ if (IV.isRange()) {
+ IRBuilder<> IRB(F.getEntryBlock().getFirstNonPHI());
+ Value *GE = IRB.CreateICmpSGE(&*AI, ConstantInt::get(AI->getType(),
+ IV.getRangeLower()));
+ Value *AS1 = IRB.CreateAssumption(GE);
+ Solver.markOverdefined(GE);
+ Solver.markOverdefined(AS1);
+ Value *LE = IRB.CreateICmpSLE(&*AI, ConstantInt::get(AI->getType(),
+ IV.getRangeUpper()));
+ Value *AS2 = IRB.CreateAssumption(LE);
+ Solver.markOverdefined(LE);
+ Solver.markOverdefined(AS2);
+ continue;
+ }
+ }
if (!AI->use_empty() && tryToReplaceWithConstant(Solver, &*AI))
++IPNumArgsElimed;
+ }
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
if (!Solver.isBlockExecutable(&*BB)) {