diff options
-rw-r--r-- | lib/Analysis/LazyValueInfo.cpp | 89 | ||||
-rw-r--r-- | test/Transforms/CorrelatedValuePropagation/range.ll | 44 |
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 +} |