aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorNuno Lopes <nunoplopes@sapo.pt>2012-06-28 01:16:18 +0000
committerNuno Lopes <nunoplopes@sapo.pt>2012-06-28 01:16:18 +0000
commite4413947843c66cd71c160fffcb711a763c30914 (patch)
tree4ca6fc42d2ba2ed380e367d1dbe958dd3b4b73ce
parent532516a87bc57f21e6d99f49548e4c2adf835551 (diff)
downloadexternal_llvm-e4413947843c66cd71c160fffcb711a763c30914.zip
external_llvm-e4413947843c66cd71c160fffcb711a763c30914.tar.gz
external_llvm-e4413947843c66cd71c160fffcb711a763c30914.tar.bz2
make LVI::getEdgeValue() always intersect the constraints of the edge with the range of the block. Previously it was only performing the intersection for a few cases, thus losing precision
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159320 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r--lib/Analysis/LazyValueInfo.cpp89
-rw-r--r--test/Transforms/CorrelatedValuePropagation/range.ll44
2 files changed, 97 insertions, 36 deletions
diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp
index 7539d93..83786dd 100644
--- a/lib/Analysis/LazyValueInfo.cpp
+++ b/lib/Analysis/LazyValueInfo.cpp
@@ -172,7 +172,7 @@ public:
if (NewR.isEmptySet())
return markOverdefined();
- bool changed = Range == NewR;
+ bool changed = Range != NewR;
Range = NewR;
return changed;
}
@@ -457,8 +457,10 @@ void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
void LazyValueInfoCache::solve() {
while (!BlockValueStack.empty()) {
std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
- if (solveBlockValue(e.second, e.first))
+ if (solveBlockValue(e.second, e.first)) {
+ assert(BlockValueStack.top() == e);
BlockValueStack.pop();
+ }
}
}
@@ -766,15 +768,10 @@ bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
return true;
}
-/// getEdgeValue - This method attempts to infer more complex
-bool 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;
- }
-
+/// \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())) {
@@ -827,25 +824,8 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
// If we're interested in the false dest, invert the condition.
if (!isTrueDest) TrueValues = TrueValues.inverse();
-
- // Figure out the possible values of the query BEFORE this branch.
- if (!hasBlockValue(Val, BBFrom)) {
- BlockValueStack.push(std::make_pair(BBFrom, Val));
- return false;
- }
-
- LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
- if (!InBlock.isConstantRange()) {
- Result = LVILatticeVal::getRange(TrueValues);
- return true;
- }
-
- // Find all potential values that satisfy both the input and output
- // conditions.
- ConstantRange PossibleValues =
- TrueValues.intersectWith(InBlock.getConstantRange());
-
- Result = LVILatticeVal::getRange(PossibleValues);
+
+ Result = LVILatticeVal::getRange(TrueValues);
return true;
}
}
@@ -874,14 +854,51 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
return true;
}
}
-
- // Otherwise see if the value is known in the block.
- if (hasBlockValue(Val, BBFrom)) {
- Result = getBlockValue(Val, BBFrom);
+ return false;
+}
+
+/// \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,
+ 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;
}
- BlockValueStack.push(std::make_pair(BBFrom, Val));
- return false;
+
+ if (getEdgeValueLocal(Val, BBFrom, BBTo, Result)) {
+ if (!Result.isConstantRange() ||
+ Result.getConstantRange().getSingleElement())
+ return true;
+
+ // 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)) {
+ BlockValueStack.push(std::make_pair(BBFrom, Val));
+ return false;
+ }
+
+ // Try to intersect ranges of the BB and the constraint on the edge.
+ LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
+ if (!InBlock.isConstantRange())
+ return true;
+
+ ConstantRange Range =
+ Result.getConstantRange().intersectWith(InBlock.getConstantRange());
+ Result = LVILatticeVal::getRange(Range);
+ return true;
+ }
+
+ if (!hasBlockValue(Val, BBFrom)) {
+ BlockValueStack.push(std::make_pair(BBFrom, Val));
+ return false;
+ }
+
+ // 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) {
diff --git a/test/Transforms/CorrelatedValuePropagation/range.ll b/test/Transforms/CorrelatedValuePropagation/range.ll
index 4ac478b..a9e27d6 100644
--- a/test/Transforms/CorrelatedValuePropagation/range.ll
+++ b/test/Transforms/CorrelatedValuePropagation/range.ll
@@ -98,3 +98,47 @@ return:
%retval.0 = phi i32 [ 42, %sw.default ], [ 4, %if.then ], [ 9, %if.end ]
ret i32 %retval.0
}
+
+; CHECK: @test5
+define i1 @test5(i32 %c) nounwind {
+ %cmp = icmp slt i32 %c, 5
+ br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+ %cmp1 = icmp eq i32 %c, 4
+ br i1 %cmp1, label %if.end, label %if.end8
+
+if.end:
+ ret i1 true
+
+if.end8:
+ %cmp2 = icmp eq i32 %c, 3
+ %cmp3 = icmp eq i32 %c, 4
+ %cmp4 = icmp eq i32 %c, 6
+; CHECK: %or = or i1 false, false
+ %or = or i1 %cmp3, %cmp4
+; CHECK: ret i1 %cmp2
+ ret i1 %cmp2
+}
+
+; CHECK: @test6
+define i1 @test6(i32 %c) nounwind {
+ %cmp = icmp ule i32 %c, 7
+ br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+; CHECK: icmp eq i32 %c, 6
+; CHECK: br i1
+ switch i32 %c, label %if.end [
+ i32 6, label %sw.bb
+ i32 8, label %sw.bb
+ ]
+
+if.end:
+ ret i1 true
+
+sw.bb:
+ %cmp2 = icmp eq i32 %c, 6
+; CHECK: ret i1 true
+ ret i1 %cmp2
+}