[prev in list] [next in list] [prev in thread] [next in thread]
List: llvm-dev
Subject: [LLVMdev] [Patches] Some LazyValueInfo and related patches
From: Olivier Goffart <olivier () woboq ! com>
Date: 2014-01-21 13:21:43
Message-ID: 6765551.NP2hizf9Jg () finn
[Download RAW message or body]
Hi.
Attached you will find a set of patches which I did while I was trying to solve
two problems.
I did not manage to solve fully what i wanted to improve, but I think it is
still a step in the right direction.
The patches are hopefully self-explanatory.
The biggest change here is that LazyValueInfo do not maintain a separate stack
of work to do,
but do the work directly recursively.
The test included in the patch 4 also test the patch 2.
The first problem I was trying to solve is to be let the code give hint on the
range of the values.
Imagine, in a library:
class CopyOnWrite {
char *stuff;
int ref_count;
void detach_internal();
inline void detach() {
if (ref_count > 1) {
detach_internal();
/* ref_count = 1; */
}
}
public:
char &operator[](int i) { detach(); return stuff[i]; }
};
Then, in code like this:
int doStuffWithStuff(CoptOnWrite &stuff) {
return stuff[0] + stuff[1] * stuff[2];
}
The generated code will contains three test of ref_count, and three call to
detach_internal
Is there a way to tell the compiler that ref_count is actually smaller or
equal to 1 after a call to detach_internal?
Having the "ref_count=1" explicit in the code help (with my patches), but then
the operation itself is in the code, and I don't want that.
Something like
if (ref_count>1)
__builtin_unreachable()
Works fine in GCC, but does not work with LLVM.
Well, it almost work. but the problem is that the whole condition is removed
before the inlining is done.
So what can be done for that to work? Either delay the removal of
__builtin_unreachable() to after inlining (when?)
Another way could be, while removing branches because they are unreachable,
somehow leave the range information kept.
I was thinking about a !range metadata, but I don't know where to put it.
The other problem was that i was analyzing code like this:
void toLatin1(uchar *dst, const ushort *src, int length)
{
if (length) {
#if defined(__SSE2__)
if (length >= 16) {
for (int i = 0; i < length >> 4; ++i) {
/* skipped code using SSE2 intrinsics */
src += 16; dst += 16;
}
length = length % 16;
}
#endif
while (length--) {
*dst++ = (*src>0xff) ? '?' : (uchar) *src;
++src;
}
}
}
I was wondering, if compiling with AVX, would clang/LLVM be able to even
vectorize more the SSE2 intrinsics to wider vectors? Or would the non
intrinsics branch be better?
It turns out the result is not great. LLVM leaves the intrinsics code
unchanged (that's ok), but tries to also vectorize the second loop. (And the
result of this vectorisation is quite horrible.)
Shouldn't the compiler see that length is never bigger than 16 and hence
deduce that there is no point in vectorizing? This is why I implemented the
srem and urem in LVI.
But then, maybe some other pass a loop pass should use LVI to see than a loop
never enters, or loop vectorizer could use LVI to avoid creating the loop in
the first place.
--
Olivier
["0001-SCCP-Do-not-transform-load-of-a-null-pointer-into-0.patch" (0001-SCCP-Do-not-transform-load-of-a-null-pointer-into-0.patch)]
From 28de998c1edc682d0f0b0c35ecbfe82d32d60b95 Mon Sep 17 00:00:00 2001
From: Olivier Goffart <ogoffart@woboq.com>
Date: Sun, 27 Oct 2013 10:47:58 +0100
Subject: [PATCH 1/8] SCCP: Do not transform load of a null pointer into 0
Let some other pass mark them as undefined behaviour later.
---
lib/Transforms/Scalar/SCCP.cpp | 4 ----
1 file changed, 4 deletions(-)
diff --git a/lib/Transforms/Scalar/SCCP.cpp b/lib/Transforms/Scalar/SCCP.cpp
index 4364720..4ca7b01 100644
--- a/lib/Transforms/Scalar/SCCP.cpp
+++ b/lib/Transforms/Scalar/SCCP.cpp
@@ -1049,10 +1049,6 @@ void SCCPSolver::visitLoadInst(LoadInst &I) {
Constant *Ptr = PtrVal.getConstant();
- // load null -> null
- if (isa<ConstantPointerNull>(Ptr) && I.getPointerAddressSpace() == 0)
- return markConstant(IV, &I, Constant::getNullValue(I.getType()));
-
// Transform load (constant global) into the value loaded.
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
if (!TrackedGlobals.empty()) {
--
1.8.5.3
["0002-LVI-Be-able-to-optimize-the-condition-with-and-and-o.patch" (0002-LVI-Be-able-to-optimize-the-condition-with-and-and-o.patch)]
From 5d48a5421c25a28b6eba8554cf3bb215f23bc41e Mon Sep 17 00:00:00 2001
From: Olivier Goffart <ogoffart@woboq.com>
Date: Sat, 21 Dec 2013 11:06:03 +0100
Subject: [PATCH 2/8] LVI: Be able to optimize the condition with 'and' and
'or'
Example:
if (x < 4 && y > 5) {
if (x == 4) //should be removed
}
This actually fixes a regression in LLVM 3.4 because previous version
were not transforming && in a 'and' instruction before the correlated
value propagation pass.
---
lib/Analysis/LazyValueInfo.cpp | 153 ++++++++++++++++++++++++++++-------------
1 file changed, 106 insertions(+), 47 deletions(-)
diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp
index b6970af..9fcf816 100644
--- a/lib/Analysis/LazyValueInfo.cpp
+++ b/lib/Analysis/LazyValueInfo.cpp
@@ -774,12 +774,114 @@ bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
return true;
}
+static bool inferFromComparison(Value *Val, ICmpInst *ICI, bool isTrueDest,
+ LVILatticeVal &Result) {
+ if (ICI && isa<Constant>(ICI->getOperand(1))) {
+ if (ICI->isEquality() && ICI->getOperand(0) == Val) {
+ // We know that V has the RHS constant if this is a true SETEQ or
+ // false SETNE.
+ if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
+ Result = LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
+ else
+ Result = LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1)));
+ return true;
+ }
+
+ // Recognize the range checking idiom that InstCombine produces.
+ // (X-C1) u< C2 --> [C1, C1+C2)
+ ConstantInt *NegOffset = 0;
+ if (ICI->getPredicate() == ICmpInst::ICMP_ULT)
+ match(ICI->getOperand(0), m_Add(m_Specific(Val),
+ m_ConstantInt(NegOffset)));
+
+ ConstantInt *CI = dyn_cast<ConstantInt>(ICI->getOperand(1));
+ if (CI && (ICI->getOperand(0) == Val || NegOffset)) {
+ // Calculate the range of values that would satisfy the comparison.
+ ConstantRange CmpRange(CI->getValue());
+ ConstantRange TrueValues =
+ ConstantRange::makeICmpRegion(ICI->getPredicate(), CmpRange);
+
+ if (NegOffset) // Apply the offset from above.
+ TrueValues = TrueValues.subtract(NegOffset->getValue());
+
+ // If we're interested in the false dest, invert the condition.
+ if (!isTrueDest) TrueValues = TrueValues.inverse();
+
+ Result = LVILatticeVal::getRange(TrueValues);
+ return true;
+ }
+ }
+ return false;
+}
+
+bool inferFromCondition(Value* Val, Value *Condition, bool isTrueDest,
+ LVILatticeVal& Result) {
+
+
+ // If V is the condition of the branch itself, then we know exactly what
+ // it is.
+ if (Condition == Val) {
+ Result = LVILatticeVal::get(ConstantInt::get(
+ Type::getInt1Ty(Val->getContext()), isTrueDest));
+ return true;
+ }
+
+ // If the condition of the branch is an equality comparison, we may be
+ // able to infer the value.
+ if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
+ return inferFromComparison(Val, ICI, isTrueDest, Result);
+ }
+
+ // Try to match with conditions formed with Or or And
+ if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Condition)) {
+
+ if ((BO->getOpcode() == Instruction::Or && isTrueDest) ||
+ (BO->getOpcode() == Instruction::And && !isTrueDest)) {
+
+ // The union of all the results
+ LVILatticeVal Res1;
+ if (!inferFromCondition(Val, BO->getOperand(0), isTrueDest, Res1))
+ return false;
+ if (Res1.isOverdefined()) {
+ Result = Res1;
+ return true;
+ }
+ LVILatticeVal Res2;
+ if (!inferFromCondition(Val, BO->getOperand(1), isTrueDest, Res2))
+ return false;
+
+ Res1.mergeIn(Res2);
+ Result = Res1;
+ return true;
+ }
+ if ((BO->getOpcode() == Instruction::And && isTrueDest) ||
+ (BO->getOpcode() == Instruction::Or && !isTrueDest)) {
+
+ // The intersection of the results
+ if (!inferFromCondition(Val, BO->getOperand(0), isTrueDest, Result))
+ return inferFromCondition(Val, BO->getOperand(1), isTrueDest, Result);
+ LVILatticeVal Other;
+ if (inferFromCondition(Val, BO->getOperand(1), isTrueDest, Other)) {
+ // intersects Result and Other
+ if (Result.isOverdefined()) {
+ Result = Other;
+ } else if (Other.isUndefined()) {
+ Result = Other;
+ } else if (Result.isConstantRange() && Other.isConstantRange()) {
+ Result.markConstantRange(Result.getConstantRange().intersectWith(
+ Other.getConstantRange()));
+ }
+ }
+ return true;
+ }
+ }
+ return false;
+}
+
/// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
/// Val is not constrained on the edge.
static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
BasicBlock *BBTo, LVILatticeVal &Result) {
- // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
- // know that v != 0.
if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
// If this is a conditional branch and only one successor goes to BBTo, then
// we maybe able to infer something from the condition.
@@ -788,53 +890,10 @@ static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
bool isTrueDest = BI->getSuccessor(0) == BBTo;
assert(BI->getSuccessor(!isTrueDest) == BBTo &&
"BBTo isn't a successor of BBFrom");
-
- // If V is the condition of the branch itself, then we know exactly what
- // it is.
- if (BI->getCondition() == Val) {
- Result = LVILatticeVal::get(ConstantInt::get(
- Type::getInt1Ty(Val->getContext()), isTrueDest));
- return true;
- }
-
- // If the condition of the branch is an equality comparison, we may be
- // able to infer the value.
- ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition());
- if (ICI && isa<Constant>(ICI->getOperand(1))) {
- if (ICI->isEquality() && ICI->getOperand(0) == Val) {
- // We know that V has the RHS constant if this is a true SETEQ or
- // false SETNE.
- if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
- Result = LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
- else
- Result = LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1)));
- return true;
- }
- // Recognize the range checking idiom that InstCombine produces.
- // (X-C1) u< C2 --> [C1, C1+C2)
- ConstantInt *NegOffset = 0;
- if (ICI->getPredicate() == ICmpInst::ICMP_ULT)
- match(ICI->getOperand(0), m_Add(m_Specific(Val),
- m_ConstantInt(NegOffset)));
+ if (inferFromCondition(Val, BI->getCondition(), isTrueDest, Result))
+ return true;
- ConstantInt *CI = dyn_cast<ConstantInt>(ICI->getOperand(1));
- if (CI && (ICI->getOperand(0) == Val || NegOffset)) {
- // Calculate the range of values that would satisfy the comparison.
- ConstantRange CmpRange(CI->getValue());
- ConstantRange TrueValues =
- ConstantRange::makeICmpRegion(ICI->getPredicate(), CmpRange);
-
- if (NegOffset) // Apply the offset from above.
- TrueValues = TrueValues.subtract(NegOffset->getValue());
-
- // If we're interested in the false dest, invert the condition.
- if (!isTrueDest) TrueValues = TrueValues.inverse();
-
- Result = LVILatticeVal::getRange(TrueValues);
- return true;
- }
- }
}
}
--
1.8.5.3
["0003-LVI-Re-order-the-check-that-the-second-operand-is-co.patch" (0003-LVI-Re-order-the-check-that-the-second-operand-is-co.patch)]
From 005ad000702b1c3691304792250bafba85e7ca4f Mon Sep 17 00:00:00 2001
From: Olivier Goffart <ogoffart@woboq.com>
Date: Fri, 13 Dec 2013 17:06:10 +0100
Subject: [PATCH 3/8] LVI: Re-order the check that the second operand is
constant.
Only do the test once, and before computing the range of the second operand
---
lib/Analysis/LazyValueInfo.cpp | 40 ++++++++++++++++------------------------
1 file changed, 16 insertions(+), 24 deletions(-)
diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp
index 9fcf816..97c7486 100644
--- a/lib/Analysis/LazyValueInfo.cpp
+++ b/lib/Analysis/LazyValueInfo.cpp
@@ -540,17 +540,6 @@ bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
return ODCacheUpdater.markResult(true);
}
- // FIXME: We're currently limited to binops with a constant RHS. This should
- // be improved.
- BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
- if (BO && !isa<ConstantInt>(BO->getOperand(1))) {
- DEBUG(dbgs() << " compute BB '" << BB->getName()
- << "' - overdefined because inst def found.\n");
-
- BBLV.markOverdefined();
- return ODCacheUpdater.markResult(true);
- }
-
return ODCacheUpdater.markResult(solveBlockValueConstantRange(BBLV, BBI, BB));
}
@@ -696,19 +685,8 @@ bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
Instruction *BBI,
BasicBlock *BB) {
- // Figure out the range of the LHS. If that fails, bail.
- if (!hasBlockValue(BBI->getOperand(0), BB)) {
- BlockValueStack.push(std::make_pair(BB, BBI->getOperand(0)));
- return false;
- }
-
- LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
- if (!LHSVal.isConstantRange()) {
- BBLV.markOverdefined();
- return true;
- }
-
- ConstantRange LHSRange = LHSVal.getConstantRange();
+ // FIXME: We're currently limited to binops with a constant RHS. This should
+ // be improved.
ConstantRange RHSRange(1);
IntegerType *ResultTy = cast<IntegerType>(BBI->getType());
if (isa<BinaryOperator>(BBI)) {
@@ -720,6 +698,20 @@ bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
}
}
+ // Figure out the range of the LHS. If that fails, bail.
+ if (!hasBlockValue(BBI->getOperand(0), BB)) {
+ BlockValueStack.push(std::make_pair(BB, BBI->getOperand(0)));
+ return false;
+ }
+
+ LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
+ if (!LHSVal.isConstantRange()) {
+ BBLV.markOverdefined();
+ return true;
+ }
+
+ ConstantRange LHSRange = LHSVal.getConstantRange();
+
// NOTE: We're currently limited by the set of operations that ConstantRange
// can evaluate symbolically. Enhancing that set will allows us to analyze
// more definitions.
--
1.8.5.3
["0004-LVI-Look-recursively-the-dependencies-for-finding-ra.patch" (0004-LVI-Look-recursively-the-dependencies-for-finding-ra.patch)]
From 71b82e0825d3fc67b3906ab56ae7da91d9ff5f02 Mon Sep 17 00:00:00 2001
From: Olivier Goffart <ogoffart@woboq.com>
Date: Fri, 13 Dec 2013 22:01:45 +0100
Subject: [PATCH 4/8] LVI: Look recursively the dependencies for finding
ranges.
Otherwise we miss optimisations oportunities.
If we realize the current computation needs the range of another variable,
we used to return false and put that variable in the stacki of work.
Returning false means that the result should be computed again.
But in order to avoid cycles we already remember that this result is
overdefined and would therefore not re-compute this value later.
---
lib/Analysis/LazyValueInfo.cpp | 9 +++----
.../Transforms/CorrelatedValuePropagation/range.ll | 29 ++++++++++++++++++++++
2 files changed, 32 insertions(+), 6 deletions(-)
diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp
index 97c7486..73a4e3f 100644
--- a/lib/Analysis/LazyValueInfo.cpp
+++ b/lib/Analysis/LazyValueInfo.cpp
@@ -700,8 +700,7 @@ bool \
LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
// Figure out the range of the LHS. If that fails, bail.
if (!hasBlockValue(BBI->getOperand(0), BB)) {
- BlockValueStack.push(std::make_pair(BB, BBI->getOperand(0)));
- return false;
+ solveBlockValue(BBI->getOperand(0), BB);
}
LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
@@ -935,8 +934,7 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock \
*BBFrom,
// LVI better supports recursive values. Even for the single value case, we
// can intersect to detect dead code (an empty range).
if (!hasBlockValue(Val, BBFrom)) {
- BlockValueStack.push(std::make_pair(BBFrom, Val));
- return false;
+ solveBlockValue(Val, BBFrom);
}
// Try to intersect ranges of the BB and the constraint on the edge.
@@ -951,8 +949,7 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock \
*BBFrom, }
if (!hasBlockValue(Val, BBFrom)) {
- BlockValueStack.push(std::make_pair(BBFrom, Val));
- return false;
+ solveBlockValue(Val, BBFrom);
}
// if we couldn't compute the value on the edge, use the value from the BB
diff --git a/test/Transforms/CorrelatedValuePropagation/range.ll \
b/test/Transforms/CorrelatedValuePropagation/range.ll index e40c639..7e98d2d 100644
--- a/test/Transforms/CorrelatedValuePropagation/range.ll
+++ b/test/Transforms/CorrelatedValuePropagation/range.ll
@@ -165,3 +165,32 @@ sw.default:
%or2 = or i1 %cmp7, %cmp8
ret i1 false
}
+
+; CHECK-LABEL: @test8(
+define i32 @test8(i32 %a, i32 %b) nounwind {
+ %cmp1 = icmp ult i32 %a, 8
+ %cmp2 = icmp ugt i32 %b, 30
+ %and = and i1 %cmp1, %cmp2
+ br i1 %and, label %then, label %else
+
+then: ; a < 8 && b > 30
+ %off1 = add i32 %a, 60 ; off1 < 8+60
+ br label %do
+
+do:
+
+ %cmp3 = icmp eq i32 %off1, 67
+ %cmp4 = icmp eq i32 %off1, 68
+ %cmp5 = icmp eq i32 %off1, 69
+
+ ; CHECK: %or1 = or i1 %cmp3, false
+ %or1 = or i1 %cmp3, %cmp4
+ ; CHECK: %or2 = or i1 false, %cmp3
+ %or2 = or i1 %cmp5, %cmp3
+
+ ret i32 2
+
+
+else:
+ ret i32 1
+}
--
1.8.5.3
["0007-LVI-Support-range-detection-of-srem-and-urem.patch" (0007-LVI-Support-range-detection-of-srem-and-urem.patch)]
From c76a7e36b4d850ebbbb23c37754d6f34127f0639 Mon Sep 17 00:00:00 2001
From: Olivier Goffart <ogoffart@woboq.com>
Date: Thu, 19 Dec 2013 11:28:31 +0100
Subject: [PATCH 7/8] LVI: Support range detection of srem and urem
When there is code like foo = bar % 34; we know that foo < 34
---
include/llvm/Support/ConstantRange.h | 11 +++++
lib/Analysis/LazyValueInfo.cpp | 17 ++++++--
lib/Support/ConstantRange.cpp | 26 +++++++++++
.../Transforms/CorrelatedValuePropagation/range.ll | 13 ++++--
unittests/Support/ConstantRangeTest.cpp | 50 ++++++++++++++++++++++
5 files changed, 111 insertions(+), 6 deletions(-)
diff --git a/include/llvm/Support/ConstantRange.h \
b/include/llvm/Support/ConstantRange.h index f757c6e..935b65d 100644
--- a/include/llvm/Support/ConstantRange.h
+++ b/include/llvm/Support/ConstantRange.h
@@ -254,6 +254,17 @@ public:
/// \p Other.
ConstantRange lshr(const ConstantRange &Other) const;
+ /// srem - Return a new range representing the possible values resulting
+ /// from a reminder of signed division of a value in this range by a value
+ /// in \p Other.
+ ConstantRange srem(const ConstantRange &Other) const;
+
+ /// urem - Return a new range representing the possible values resulting
+ /// from a reminder of unsigned division of a value in this range by a value
+ /// in \p Other.
+ ConstantRange urem(const ConstantRange &Other) const;
+
+
/// inverse - Return a new range that is the logical not of the current set.
///
ConstantRange inverse() const;
diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp
index 8e9677e..c7ff34f 100644
--- a/lib/Analysis/LazyValueInfo.cpp
+++ b/lib/Analysis/LazyValueInfo.cpp
@@ -637,12 +637,17 @@ void \
LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV, }
LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
- if (!LHSVal.isConstantRange()) {
+ ConstantRange LHSRange(1);
+ if (LHSVal.isConstantRange()) {
+ LHSRange = LHSVal.getConstantRange();
+ } else if (!LHSVal.isOverdefined() ||
+ !BBI->getOperand(0)->getType()->isIntegerTy()) {
BBLV.markOverdefined();
return;
+ } else {
+ LHSRange = ConstantRange(
+ BBI->getOperand(0)->getType()->getIntegerBitWidth(), true);
}
-
- ConstantRange LHSRange = LHSVal.getConstantRange();
// NOTE: We're currently limited by the set of operations that ConstantRange
// can evaluate symbolically. Enhancing that set will allows us to analyze
@@ -685,6 +690,12 @@ void \
LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV, case \
Instruction::Or: Result.markConstantRange(LHSRange.binaryOr(RHSRange));
break;
+ case Instruction::SRem:
+ Result.markConstantRange(LHSRange.srem(RHSRange));
+ break;
+ case Instruction::URem:
+ Result.markConstantRange(LHSRange.urem(RHSRange));
+ break;
// Unhandled instructions are overdefined.
default:
diff --git a/lib/Support/ConstantRange.cpp b/lib/Support/ConstantRange.cpp
index 265b6e9..a3c1d4b 100644
--- a/lib/Support/ConstantRange.cpp
+++ b/lib/Support/ConstantRange.cpp
@@ -708,6 +708,32 @@ ConstantRange::lshr(const ConstantRange &Other) const {
return ConstantRange(min, max + 1);
}
+ConstantRange
+ConstantRange::srem(const ConstantRange &Other) const {
+ if (Other.isEmptySet() || isEmptySet() || Other.getUnsignedMax() == 0)
+ return ConstantRange(getBitWidth(), /*isFullSet=*/false);
+ if (Other.isFullSet() || Other.isWrappedSet())
+ return ConstantRange(getBitWidth(), /*isFullSet=*/true);
+ APInt min = APIntOps::smin(Other.getSignedMax().abs(), \
Other.getSignedMin().abs()); + if (min.sgt(getSignedMax()) && \
(-min).slt(getSignedMin())) + return *this;
+ APInt max = APIntOps::smax(Other.getSignedMax().abs(), \
Other.getSignedMin().abs()); + return ConstantRange(-max, max);
+}
+
+ConstantRange
+ConstantRange::urem(const ConstantRange &Other) const {
+ if (Other.isEmptySet() || isEmptySet() || Other.getUnsignedMax() == 0)
+ return ConstantRange(getBitWidth(), /*isFullSet=*/false);
+ if (Other.isFullSet() || Other.isWrappedSet())
+ return ConstantRange(getBitWidth(), /*isFullSet=*/true);
+ APInt min = Other.getUnsignedMin();
+ if (min.ugt(getUnsignedMax()))
+ return *this;
+ APInt max = Other.getUnsignedMax();
+ return ConstantRange(APInt(getBitWidth(), 0), max);
+}
+
ConstantRange ConstantRange::inverse() const {
if (isFullSet())
return ConstantRange(getBitWidth(), /*isFullSet=*/false);
diff --git a/test/Transforms/CorrelatedValuePropagation/range.ll \
b/test/Transforms/CorrelatedValuePropagation/range.ll index 7e98d2d..575af41 100644
--- a/test/Transforms/CorrelatedValuePropagation/range.ll
+++ b/test/Transforms/CorrelatedValuePropagation/range.ll
@@ -167,7 +167,7 @@ sw.default:
}
; CHECK-LABEL: @test8(
-define i32 @test8(i32 %a, i32 %b) nounwind {
+define i32 @test8(i32 %a, i32 %b, i32 %c) nounwind {
%cmp1 = icmp ult i32 %a, 8
%cmp2 = icmp ugt i32 %b, 30
%and = and i1 %cmp1, %cmp2
@@ -175,6 +175,7 @@ define i32 @test8(i32 %a, i32 %b) nounwind {
then: ; a < 8 && b > 30
%off1 = add i32 %a, 60 ; off1 < 8+60
+ %off2 = srem i32 %c, 43 ; off2 < 43
br label %do
do:
@@ -183,10 +184,16 @@ do:
%cmp4 = icmp eq i32 %off1, 68
%cmp5 = icmp eq i32 %off1, 69
+ %cmp6 = icmp eq i32 %off2, 42
+ %cmp7 = icmp eq i32 %off2, 43
+ %cmp8 = icmp eq i32 %off2, 44
+
; CHECK: %or1 = or i1 %cmp3, false
%or1 = or i1 %cmp3, %cmp4
- ; CHECK: %or2 = or i1 false, %cmp3
- %or2 = or i1 %cmp5, %cmp3
+ ; CHECK: %or2 = or i1 false, %cmp6
+ %or2 = or i1 %cmp5, %cmp6
+ ; CHECK: %or3 = or i1 false, false
+ %or3 = or i1 %cmp7, %cmp8
ret i32 2
diff --git a/unittests/Support/ConstantRangeTest.cpp \
b/unittests/Support/ConstantRangeTest.cpp index 3e0a085..2e770ee 100644
--- a/unittests/Support/ConstantRangeTest.cpp
+++ b/unittests/Support/ConstantRangeTest.cpp
@@ -502,6 +502,56 @@ TEST_F(ConstantRangeTest, Lshr) {
EXPECT_EQ(Wrap.lshr(Wrap), Full);
}
+
+TEST_F(ConstantRangeTest, Srem) {
+ EXPECT_EQ(Full.srem(Full), Full);
+ EXPECT_EQ(Full.srem(Empty), Empty);
+ EXPECT_EQ(Full.srem(One), ConstantRange(APInt(16, -0xa),
+ APInt(16, 0xa)));
+ EXPECT_EQ(Full.srem(Some), ConstantRange(APInt(16, -0xaa9),
+ APInt(16, 0xaa9)));
+ EXPECT_EQ(Full.srem(Wrap), Full);
+ EXPECT_EQ(Empty.srem(Empty), Empty);
+ EXPECT_EQ(Empty.srem(One), Empty);
+ EXPECT_EQ(Empty.srem(Some), Empty);
+ EXPECT_EQ(Empty.srem(Wrap), Empty);
+ EXPECT_EQ(Empty.srem(Full), Empty);
+ EXPECT_EQ(One.srem(One), ConstantRange(-One.getSignedMin(),
+ One.getSignedMax()));
+ EXPECT_EQ(One.srem(Some), ConstantRange(APInt(16, -0xaa9),
+ APInt(16, 0xaa9)));
+ EXPECT_EQ(One.srem(Wrap), Full);
+ EXPECT_EQ(Some.srem(Some), ConstantRange(APInt(16, -0xaa9),
+ APInt(16, 0xaa9)));
+ EXPECT_EQ(Some.srem(Wrap), Full);
+ EXPECT_EQ(Wrap.srem(Wrap), Full);
+}
+
+TEST_F(ConstantRangeTest, Urem) {
+ EXPECT_EQ(Full.urem(Full), Full);
+ EXPECT_EQ(Full.urem(Empty), Empty);
+ EXPECT_EQ(Full.urem(One), ConstantRange(APInt(16, 0),
+ APInt(16, 0xa)));
+ EXPECT_EQ(Full.urem(Some), ConstantRange(APInt(16, 0),
+ APInt(16, 0xaa9)));
+ EXPECT_EQ(Full.urem(Wrap), Full);
+ EXPECT_EQ(Empty.urem(Empty), Empty);
+ EXPECT_EQ(Empty.urem(One), Empty);
+ EXPECT_EQ(Empty.urem(Some), Empty);
+ EXPECT_EQ(Empty.urem(Wrap), Empty);
+ EXPECT_EQ(Empty.urem(Full), Empty);
+ EXPECT_EQ(One.urem(One), ConstantRange(APInt(16, 0),
+ One.getSignedMax()));
+ EXPECT_EQ(One.urem(Some), ConstantRange(APInt(16, 0),
+ APInt(16, 0xaa9)));
+ EXPECT_EQ(One.urem(Wrap), Full);
+ EXPECT_EQ(Some.urem(Some), ConstantRange(APInt(16, 0),
+ APInt(16, 0xaa9)));
+ EXPECT_EQ(Some.urem(Wrap), Full);
+ EXPECT_EQ(Wrap.urem(Wrap), Full);
+}
+
+
TEST(ConstantRange, MakeICmpRegion) {
// PR8250
ConstantRange SMax = ConstantRange(APInt::getSignedMaxValue(32));
--
1.8.5.3
["0005-LVI-simplify-a-bit-by-not-having-a-separate-stack.patch" (0005-LVI-simplify-a-bit-by-not-having-a-separate-stack.patch)]
From f07f0757953faadc5cf1044d98d54352e1bbce6a Mon Sep 17 00:00:00 2001
From: Olivier Goffart <ogoffart@woboq.com>
Date: Thu, 19 Dec 2013 14:24:28 +0100
Subject: [PATCH 5/8] LVI: simplify a bit by not having a separate stack
Last commit made that we did not use this stack anymore as we directly call
solve to compute the result.
---
lib/Analysis/LazyValueInfo.cpp | 126 +++++++++++++----------------------------
1 file changed, 39 insertions(+), 87 deletions(-)
diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp
index 73a4e3f..55ccfe1 100644
--- a/lib/Analysis/LazyValueInfo.cpp
+++ b/lib/Analysis/LazyValueInfo.cpp
@@ -333,11 +333,6 @@ namespace {
/// don't spend time removing unused blocks from our caches.
DenseSet<AssertingVH<BasicBlock> > SeenBlocks;
- /// BlockValueStack - This stack holds the state of the value solver
- /// during a query. It basically emulates the callstack of the naive
- /// recursive value lookup process.
- std::stack<std::pair<BasicBlock*, Value*> > BlockValueStack;
-
friend struct LVIValueHandle;
/// OverDefinedCacheUpdater - A helper object that ensures that the
@@ -352,33 +347,27 @@ namespace {
LazyValueInfoCache *P)
: Parent(P), Val(V), BB(B), BBLV(LV) { }
- bool markResult(bool changed) {
- if (changed && BBLV.isOverdefined())
+ ~OverDefinedCacheUpdater() {
+ if (BBLV.isOverdefined())
Parent->OverDefinedCache.insert(std::make_pair(BB, Val));
- return changed;
}
};
LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
- bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
+ void getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
LVILatticeVal &Result);
bool hasBlockValue(Value *Val, BasicBlock *BB);
// These methods process one work item and may add more. A false value
// returned means that the work item was not completely processed and must
// be revisited after going through the new items.
- bool solveBlockValue(Value *Val, BasicBlock *BB);
- bool solveBlockValueNonLocal(LVILatticeVal &BBLV,
- Value *Val, BasicBlock *BB);
- bool solveBlockValuePHINode(LVILatticeVal &BBLV,
- PHINode *PN, BasicBlock *BB);
- bool solveBlockValueConstantRange(LVILatticeVal &BBLV,
- Instruction *BBI, BasicBlock *BB);
+ void solveBlockValue(Value* Val, BasicBlock* BB);
+ void solveBlockValueNonLocal(LVILatticeVal& BBLV, Value* Val, BasicBlock* BB);
+ void solveBlockValuePHINode(LVILatticeVal& BBLV, PHINode* PN, BasicBlock* BB);
+ void solveBlockValueConstantRange(LVILatticeVal& BBLV, Instruction* BBI, BasicBlock* BB);
- void solve();
-
ValueCacheEntryTy &lookup(Value *V) {
return ValueCache[LVIValueHandle(V, this)];
}
@@ -454,16 +443,6 @@ void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
I->second.erase(BB);
}
-void LazyValueInfoCache::solve() {
- while (!BlockValueStack.empty()) {
- std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
- if (solveBlockValue(e.second, e.first)) {
- assert(BlockValueStack.top() == e);
- BlockValueStack.pop();
- }
- }
-}
-
bool LazyValueInfoCache::hasBlockValue(Value *Val, BasicBlock *BB) {
// If already a constant, there is nothing to compute.
if (isa<Constant>(Val))
@@ -485,31 +464,24 @@ LVILatticeVal LazyValueInfoCache::getBlockValue(Value *Val, BasicBlock *BB) {
return lookup(Val)[BB];
}
-bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
+void LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
if (isa<Constant>(Val))
- return true;
+ return;
ValueCacheEntryTy &Cache = lookup(Val);
SeenBlocks.insert(BB);
LVILatticeVal &BBLV = Cache[BB];
-
- // OverDefinedCacheUpdater is a helper object that will update
- // the OverDefinedCache for us when this method exits. Make sure to
- // call markResult on it as we exist, passing a bool to indicate if the
- // cache needs updating, i.e. if we have solve a new value or not.
- OverDefinedCacheUpdater ODCacheUpdater(Val, BB, BBLV, this);
// If we've already computed this block's value, return it.
if (!BBLV.isUndefined()) {
DEBUG(dbgs() << " reuse BB '" << BB->getName() << "' val=" << BBLV <<'\n');
-
- // Since we're reusing a cached value here, we don't need to update the
- // OverDefinedCahce. The cache will have been properly updated
- // whenever the cached value was inserted.
- ODCacheUpdater.markResult(false);
- return true;
+ return;
}
+ // OverDefinedCacheUpdater is a helper object that will update
+ // the OverDefinedCache for us when this method exits.
+ OverDefinedCacheUpdater ODCacheUpdater(Val, BB, BBLV, this);
+
// Otherwise, this is the first time we're seeing this block. Reset the
// lattice value to overdefined, so that cycles will terminate and be
// conservatively correct.
@@ -517,16 +489,18 @@ bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
Instruction *BBI = dyn_cast<Instruction>(Val);
if (BBI == 0 || BBI->getParent() != BB) {
- return ODCacheUpdater.markResult(solveBlockValueNonLocal(BBLV, Val, BB));
+ solveBlockValueNonLocal(BBLV, Val, BB);
+ return;
}
if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
- return ODCacheUpdater.markResult(solveBlockValuePHINode(BBLV, PN, BB));
+ solveBlockValuePHINode(BBLV, PN, BB);
+ return;
}
if (AllocaInst *AI = dyn_cast<AllocaInst>(BBI)) {
BBLV = LVILatticeVal::getNot(ConstantPointerNull::get(AI->getType()));
- return ODCacheUpdater.markResult(true);
+ return;
}
// We can only analyze the definitions of certain classes of instructions
@@ -537,10 +511,10 @@ bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
DEBUG(dbgs() << " compute BB '" << BB->getName()
<< "' - overdefined because inst def found.\n");
BBLV.markOverdefined();
- return ODCacheUpdater.markResult(true);
+ return;
}
- return ODCacheUpdater.markResult(solveBlockValueConstantRange(BBLV, BBI, BB));
+ solveBlockValueConstantRange(BBLV, BBI, BB);
}
static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
@@ -570,7 +544,7 @@ static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
return false;
}
-bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV,
+void LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV,
Value *Val, BasicBlock *BB) {
LVILatticeVal Result; // Start Undefined.
@@ -607,17 +581,14 @@ bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV,
Result.markOverdefined();
}
BBLV = Result;
- return true;
+ return;
}
// Loop over all of our predecessors, merging what we know from them into
// result.
- bool EdgesMissing = false;
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
LVILatticeVal EdgeResult;
- EdgesMissing |= !getEdgeValue(Val, *PI, BB, EdgeResult);
- if (EdgesMissing)
- continue;
+ getEdgeValue(Val, *PI, BB, EdgeResult);
Result.mergeIn(EdgeResult);
@@ -634,32 +605,27 @@ bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV,
}
BBLV = Result;
- return true;
+ return;
}
}
- if (EdgesMissing)
- return false;
// Return the merged value, which is more precise than 'overdefined'.
assert(!Result.isOverdefined());
BBLV = Result;
- return true;
+ return;
}
-bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
+void LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
PHINode *PN, BasicBlock *BB) {
LVILatticeVal Result; // Start Undefined.
// Loop over all of our predecessors, merging what we know from them into
// result.
- bool EdgesMissing = false;
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
BasicBlock *PhiBB = PN->getIncomingBlock(i);
Value *PhiVal = PN->getIncomingValue(i);
LVILatticeVal EdgeResult;
- EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult);
- if (EdgesMissing)
- continue;
+ getEdgeValue(PhiVal, PhiBB, BB, EdgeResult);
Result.mergeIn(EdgeResult);
@@ -670,19 +636,16 @@ bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
<< "' - overdefined because of pred.\n");
BBLV = Result;
- return true;
+ return;
}
}
- if (EdgesMissing)
- return false;
// Return the merged value, which is more precise than 'overdefined'.
assert(!Result.isOverdefined() && "Possible PHI in entry block?");
BBLV = Result;
- return true;
}
-bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
+void LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
Instruction *BBI,
BasicBlock *BB) {
// FIXME: We're currently limited to binops with a constant RHS. This should
@@ -694,7 +657,7 @@ bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
RHSRange = ConstantRange(RHS->getValue());
} else {
BBLV.markOverdefined();
- return true;
+ return;
}
}
@@ -706,7 +669,7 @@ bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
if (!LHSVal.isConstantRange()) {
BBLV.markOverdefined();
- return true;
+ return;
}
ConstantRange LHSRange = LHSVal.getConstantRange();
@@ -762,7 +725,6 @@ bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
}
BBLV = Result;
- return true;
}
static bool inferFromComparison(Value *Val, ICmpInst *ICI, bool isTrueDest,
@@ -917,18 +879,18 @@ static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
/// \brief Compute the value of Val on the edge BBFrom -> BBTo, or the value at
/// the basic block if the edge does not constraint Val.
-bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
+void LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
BasicBlock *BBTo, LVILatticeVal &Result) {
// If already a constant, there is nothing to compute.
if (Constant *VC = dyn_cast<Constant>(Val)) {
Result = LVILatticeVal::get(VC);
- return true;
+ return;
}
if (getEdgeValueLocal(Val, BBFrom, BBTo, Result)) {
if (!Result.isConstantRange() ||
Result.getConstantRange().getSingleElement())
- return true;
+ return;
// FIXME: this check should be moved to the beginning of the function when
// LVI better supports recursive values. Even for the single value case, we
@@ -940,12 +902,12 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
// Try to intersect ranges of the BB and the constraint on the edge.
LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
if (!InBlock.isConstantRange())
- return true;
+ return;
ConstantRange Range =
Result.getConstantRange().intersectWith(InBlock.getConstantRange());
Result = LVILatticeVal::getRange(Range);
- return true;
+ return;
}
if (!hasBlockValue(Val, BBFrom)) {
@@ -954,15 +916,10 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
// if we couldn't compute the value on the edge, use the value from the BB
Result = getBlockValue(Val, BBFrom);
- return true;
}
LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) {
- DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
- << BB->getName() << "'\n");
-
- BlockValueStack.push(std::make_pair(BB, V));
- solve();
+ solveBlockValue(V, BB);
LVILatticeVal Result = getBlockValue(V, BB);
DEBUG(dbgs() << " Result = " << Result << "\n");
@@ -975,12 +932,7 @@ getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB) {
<< FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
LVILatticeVal Result;
- if (!getEdgeValue(V, FromBB, ToBB, Result)) {
- solve();
- bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result);
- (void)WasFastQuery;
- assert(WasFastQuery && "More work to do after problem solved?");
- }
+ getEdgeValue(V, FromBB, ToBB, Result);
DEBUG(dbgs() << " Result = " << Result << "\n");
return Result;
--
1.8.5.3
["0008-CVP-Look-for-LVI-information-when-there-is-a-compari.patch" (0008-CVP-Look-for-LVI-information-when-there-is-a-compari.patch)]
From 4445438bf2a7a2d74c7c55e9e76e1587c89fa8ae Mon Sep 17 00:00:00 2001
From: Olivier Goffart <ogoffart@woboq.com>
Date: Sun, 22 Dec 2013 17:05:33 +0100
Subject: [PATCH 8/8] CVP: Look for LVI information when there is a comparison
on values on this block
Because the condition can be infered from ranges.
---
include/llvm/Analysis/LazyValueInfo.h | 8 +-
lib/Analysis/LazyValueInfo.cpp | 88 +++++++++++++++-------
.../Scalar/CorrelatedValuePropagation.cpp | 19 +----
.../Transforms/CorrelatedValuePropagation/range.ll | 22 ++++++
4 files changed, 92 insertions(+), 45 deletions(-)
diff --git a/include/llvm/Analysis/LazyValueInfo.h \
b/include/llvm/Analysis/LazyValueInfo.h index 197e94e..22e68df 100644
--- a/include/llvm/Analysis/LazyValueInfo.h
+++ b/include/llvm/Analysis/LazyValueInfo.h
@@ -51,8 +51,12 @@ public:
/// Pred is a CmpInst predicate.
Tristate getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
BasicBlock *FromBB, BasicBlock *ToBB);
-
-
+
+ /// getPredicateOnBlock - Determine whether the specified value comparison
+ /// with a constant is known to be true or false in the specified basic block.
+ Tristate getPredicateOnBlock(unsigned Pred, Value *V, Constant *C,
+ BasicBlock *BB);
+
/// getConstant - Determine whether the specified value is known to be a
/// constant at the end of the specified block. Return null if not.
Constant *getConstant(Value *V, BasicBlock *BB);
diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp
index c7ff34f..1fc9d31 100644
--- a/lib/Analysis/LazyValueInfo.cpp
+++ b/lib/Analysis/LazyValueInfo.cpp
@@ -1031,6 +1031,36 @@ Constant *LazyValueInfo::getConstantOnEdge(Value *V, \
BasicBlock *FromBB, return 0;
}
+static LazyValueInfo::Tristate
+getPredicateFromRange(unsigned Pred, const ConstantRange &CR,
+ Constant *C) {
+ ConstantInt *CI = dyn_cast<ConstantInt>(C);
+ if (!CI) return LazyValueInfo::Unknown;
+
+ if (Pred == ICmpInst::ICMP_EQ) {
+ if (!CR.contains(CI->getValue()))
+ return LazyValueInfo::False;
+
+ if (CR.isSingleElement() && CR.contains(CI->getValue()))
+ return LazyValueInfo::True;
+ } else if (Pred == ICmpInst::ICMP_NE) {
+ if (!CR.contains(CI->getValue()))
+ return LazyValueInfo::True;
+
+ if (CR.isSingleElement() && CR.contains(CI->getValue()))
+ return LazyValueInfo::False;
+ }
+
+ // Handle more complex predicates.
+ ConstantRange TrueValues =
+ ICmpInst::makeConstantRange((ICmpInst::Predicate)Pred, CI->getValue());
+ if (TrueValues.contains(CR))
+ return LazyValueInfo::True;
+ if (TrueValues.inverse().contains(CR))
+ return LazyValueInfo::False;
+ return LazyValueInfo::Unknown;
+}
+
/// getPredicateOnEdge - Determine whether the specified value comparison
/// with a constant is known to be true or false on the specified CFG edge.
/// Pred is a CmpInst predicate.
@@ -1050,32 +1080,7 @@ LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, \
Constant *C, }
if (Result.isConstantRange()) {
- ConstantInt *CI = dyn_cast<ConstantInt>(C);
- if (!CI) return Unknown;
-
- ConstantRange CR = Result.getConstantRange();
- if (Pred == ICmpInst::ICMP_EQ) {
- if (!CR.contains(CI->getValue()))
- return False;
-
- if (CR.isSingleElement() && CR.contains(CI->getValue()))
- return True;
- } else if (Pred == ICmpInst::ICMP_NE) {
- if (!CR.contains(CI->getValue()))
- return True;
-
- if (CR.isSingleElement() && CR.contains(CI->getValue()))
- return False;
- }
-
- // Handle more complex predicates.
- ConstantRange TrueValues =
- ICmpInst::makeConstantRange((ICmpInst::Predicate)Pred, CI->getValue());
- if (TrueValues.contains(CR))
- return True;
- if (TrueValues.inverse().contains(CR))
- return False;
- return Unknown;
+ return getPredicateFromRange(Pred, Result.getConstantRange(), C);
}
if (Result.isNotConstant()) {
@@ -1102,6 +1107,37 @@ LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, \
Constant *C, return Unknown;
}
+/// getPredicateOnBlock - Determine whether the specified value comparison
+/// with a constant is known to be true or false in the specified basic block.
+LazyValueInfo::Tristate
+LazyValueInfo::getPredicateOnBlock(unsigned Pred, Value *V, Constant *C,
+ BasicBlock *BB) {
+ if (isa<Instruction>(V) &&
+ cast<Instruction>(V)->getParent() == BB) {
+
+ LVILatticeVal Result = getCache(PImpl).getValueInBlock(V, BB);
+ if (!Result.isConstantRange())
+ return LazyValueInfo::Unknown;
+
+ return getPredicateFromRange(Pred, Result.getConstantRange(), C);
+ }
+
+ pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
+ if (PI == PE) return LazyValueInfo::Unknown;
+
+ LazyValueInfo::Tristate Result = getPredicateOnEdge(Pred, V, C, *PI, BB);
+ if (Result == LazyValueInfo::Unknown) return Result;
+
+ ++PI;
+ while (PI != PE) {
+ LazyValueInfo::Tristate Res = getPredicateOnEdge(Pred, V, C, *PI, BB);
+ if (Res != Result) return LazyValueInfo::Unknown;
+ ++PI;
+ }
+
+ return Result;
+}
+
void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
BasicBlock *NewSucc) {
if (PImpl) getCache(PImpl).threadEdge(PredBB, OldSucc, NewSucc);
diff --git a/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp \
b/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp index 995782e..73c06bf 100644
--- a/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
+++ b/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
@@ -160,29 +160,14 @@ bool CorrelatedValuePropagation::processMemAccess(Instruction \
*I) { /// available on that edge. If a given static evaluation is true on ALL
/// incoming edges, then it's true universally and we can simplify the compare.
bool CorrelatedValuePropagation::processCmp(CmpInst *C) {
- Value *Op0 = C->getOperand(0);
- if (isa<Instruction>(Op0) &&
- cast<Instruction>(Op0)->getParent() == C->getParent())
- return false;
Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
if (!Op1) return false;
- pred_iterator PI = pred_begin(C->getParent()), PE = pred_end(C->getParent());
- if (PI == PE) return false;
-
- LazyValueInfo::Tristate Result = LVI->getPredicateOnEdge(C->getPredicate(),
- C->getOperand(0), Op1, *PI, C->getParent());
+ LazyValueInfo::Tristate Result = LVI->getPredicateOnBlock(C->getPredicate(),
+ C->getOperand(0), Op1, C->getParent());
if (Result == LazyValueInfo::Unknown) return false;
- ++PI;
- while (PI != PE) {
- LazyValueInfo::Tristate Res = LVI->getPredicateOnEdge(C->getPredicate(),
- C->getOperand(0), Op1, *PI, C->getParent());
- if (Res != Result) return false;
- ++PI;
- }
-
++NumCmps;
if (Result == LazyValueInfo::True)
diff --git a/test/Transforms/CorrelatedValuePropagation/range.ll \
b/test/Transforms/CorrelatedValuePropagation/range.ll index 575af41..0e701b3 100644
--- a/test/Transforms/CorrelatedValuePropagation/range.ll
+++ b/test/Transforms/CorrelatedValuePropagation/range.ll
@@ -201,3 +201,25 @@ do:
else:
ret i32 1
}
+
+
+define i32 @test9(i32 %a) nounwind {
+ %cmp = icmp ult i32 %a, 8
+ br i1 %cmp, label %then, label %else
+
+then:
+
+ %a.off = add i32 %a, 2
+ %dead = icmp ugt i32 %a.off, 11
+ br i1 %dead, label %end, label %else
+
+else:
+ ret i32 1
+
+end:
+ ret i32 2
+
+; CHECK-LABEL: @test9(
+; CHECK: br i1 false, label %end, label %else
+}
+
--
1.8.5.3
["0006-LVI-simplify-remove-hasBlockValue-and-solve-from-get.patch" (0006-LVI-simplify-remove-hasBlockValue-and-solve-from-get.patch)]
From 0f67571904b3f635005d5c826c4267481d92b6a1 Mon Sep 17 00:00:00 2001
From: Olivier Goffart <ogoffart@woboq.com>
Date: Thu, 19 Dec 2013 14:46:26 +0100
Subject: [PATCH 6/8] LVI: simplify: remove hasBlockValue and solve from
getBlockValue
We always did something like that:
if (!hasBlockValue(Val, BBFrom)) {
solveBlockValue(Val, BBFrom);
}
Result = getBlockValue(Val, BBFrom);
Each function did a lookup in the cache. By merging the three function we
only do one lookup.
---
lib/Analysis/LazyValueInfo.cpp | 64 ++++++++----------------------------------
1 file changed, 11 insertions(+), 53 deletions(-)
diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp
index 55ccfe1..8e9677e 100644
--- a/lib/Analysis/LazyValueInfo.cpp
+++ b/lib/Analysis/LazyValueInfo.cpp
@@ -352,18 +352,11 @@ namespace {
Parent->OverDefinedCache.insert(std::make_pair(BB, Val));
}
};
-
-
LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
void getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
LVILatticeVal &Result);
- bool hasBlockValue(Value *Val, BasicBlock *BB);
- // These methods process one work item and may add more. A false value
- // returned means that the work item was not completely processed and must
- // be revisited after going through the new items.
- void solveBlockValue(Value* Val, BasicBlock* BB);
void solveBlockValueNonLocal(LVILatticeVal& BBLV, Value* Val, BasicBlock* BB);
void solveBlockValuePHINode(LVILatticeVal& BBLV, PHINode* PN, BasicBlock* BB);
void solveBlockValueConstantRange(LVILatticeVal& BBLV, Instruction* BBI, BasicBlock* BB);
@@ -443,17 +436,6 @@ void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
I->second.erase(BB);
}
-bool LazyValueInfoCache::hasBlockValue(Value *Val, BasicBlock *BB) {
- // If already a constant, there is nothing to compute.
- if (isa<Constant>(Val))
- return true;
-
- LVIValueHandle ValHandle(Val, this);
- std::map<LVIValueHandle, ValueCacheEntryTy>::iterator I =
- ValueCache.find(ValHandle);
- if (I == ValueCache.end()) return false;
- return I->second.count(BB);
-}
LVILatticeVal LazyValueInfoCache::getBlockValue(Value *Val, BasicBlock *BB) {
// If already a constant, there is nothing to compute.
@@ -461,46 +443,38 @@ LVILatticeVal LazyValueInfoCache::getBlockValue(Value *Val, BasicBlock *BB) {
return LVILatticeVal::get(VC);
SeenBlocks.insert(BB);
- return lookup(Val)[BB];
-}
-
-void LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
- if (isa<Constant>(Val))
- return;
-
ValueCacheEntryTy &Cache = lookup(Val);
- SeenBlocks.insert(BB);
LVILatticeVal &BBLV = Cache[BB];
// If we've already computed this block's value, return it.
if (!BBLV.isUndefined()) {
DEBUG(dbgs() << " reuse BB '" << BB->getName() << "' val=" << BBLV <<'\n');
- return;
+ return BBLV;
}
- // OverDefinedCacheUpdater is a helper object that will update
- // the OverDefinedCache for us when this method exits.
- OverDefinedCacheUpdater ODCacheUpdater(Val, BB, BBLV, this);
-
// Otherwise, this is the first time we're seeing this block. Reset the
// lattice value to overdefined, so that cycles will terminate and be
// conservatively correct.
BBLV.markOverdefined();
-
+
+ // OverDefinedCacheUpdater is a helper object that will update
+ // the OverDefinedCache for us when this method exits.
+ OverDefinedCacheUpdater ODCacheUpdater(Val, BB, BBLV, this);
+
Instruction *BBI = dyn_cast<Instruction>(Val);
if (BBI == 0 || BBI->getParent() != BB) {
solveBlockValueNonLocal(BBLV, Val, BB);
- return;
+ return BBLV;
}
if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
solveBlockValuePHINode(BBLV, PN, BB);
- return;
+ return BBLV;
}
if (AllocaInst *AI = dyn_cast<AllocaInst>(BBI)) {
BBLV = LVILatticeVal::getNot(ConstantPointerNull::get(AI->getType()));
- return;
+ return BBLV;
}
// We can only analyze the definitions of certain classes of instructions
@@ -511,10 +485,11 @@ void LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
DEBUG(dbgs() << " compute BB '" << BB->getName()
<< "' - overdefined because inst def found.\n");
BBLV.markOverdefined();
- return;
+ return BBLV;
}
solveBlockValueConstantRange(BBLV, BBI, BB);
+ return BBLV;
}
static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
@@ -661,11 +636,6 @@ void LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
}
}
- // Figure out the range of the LHS. If that fails, bail.
- if (!hasBlockValue(BBI->getOperand(0), BB)) {
- solveBlockValue(BBI->getOperand(0), BB);
- }
-
LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
if (!LHSVal.isConstantRange()) {
BBLV.markOverdefined();
@@ -892,13 +862,6 @@ void LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
Result.getConstantRange().getSingleElement())
return;
- // FIXME: this check should be moved to the beginning of the function when
- // LVI better supports recursive values. Even for the single value case, we
- // can intersect to detect dead code (an empty range).
- if (!hasBlockValue(Val, BBFrom)) {
- solveBlockValue(Val, BBFrom);
- }
-
// Try to intersect ranges of the BB and the constraint on the edge.
LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
if (!InBlock.isConstantRange())
@@ -910,16 +873,11 @@ void LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
return;
}
- if (!hasBlockValue(Val, BBFrom)) {
- solveBlockValue(Val, BBFrom);
- }
-
// if we couldn't compute the value on the edge, use the value from the BB
Result = getBlockValue(Val, BBFrom);
}
LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) {
- solveBlockValue(V, BB);
LVILatticeVal Result = getBlockValue(V, BB);
DEBUG(dbgs() << " Result = " << Result << "\n");
--
1.8.5.3
_______________________________________________
LLVM Developers mailing list
LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic