diff options
| -rw-r--r-- | lib/Analysis/LazyValueInfo.cpp | 3 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/JumpThreading.cpp | 39 | ||||
| -rw-r--r-- | test/Transforms/JumpThreading/basic.ll | 14 | ||||
| -rw-r--r-- | test/Transforms/JumpThreading/lvi-load.ll | 3 |
4 files changed, 53 insertions, 6 deletions
diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp index 31ca2de283..7e00f143c6 100644 --- a/lib/Analysis/LazyValueInfo.cpp +++ b/lib/Analysis/LazyValueInfo.cpp @@ -656,7 +656,8 @@ LVILatticeVal LVIQuery::getEdgeValue(BasicBlock *BBFrom, BasicBlock *BBTo) { // Figure out the possible values of the query BEFORE this branch. LVILatticeVal InBlock = getBlockValue(BBFrom); - if (!InBlock.isConstantRange()) return InBlock; + if (!InBlock.isConstantRange()) + return LVILatticeVal::getRange(TrueValues); // Find all potential values that satisfy both the input and output // conditions. diff --git a/lib/Transforms/Scalar/JumpThreading.cpp b/lib/Transforms/Scalar/JumpThreading.cpp index 8abd842038..3d4db285da 100644 --- a/lib/Transforms/Scalar/JumpThreading.cpp +++ b/lib/Transforms/Scalar/JumpThreading.cpp @@ -669,6 +669,45 @@ bool JumpThreading::ProcessBlock(BasicBlock *BB) { } } } + + // For a comparison where the LHS is outside this block, it's possible + // that we've branch on it before. Used LVI to see if we can simplify + // the branch based on that. + BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator()); + Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1)); + if (LVI && CondBr && CondConst && CondBr->isConditional() && + (!isa<Instruction>(CondCmp->getOperand(0)) || + cast<Instruction>(CondCmp->getOperand(0))->getParent() != BB)) { + // For predecessor edge, determine if the comparison is true or false + // on that edge. If they're all true or all false, we can simplify the + // branch. + // FIXME: We could handle mixed true/false by duplicating code. + unsigned Trues = 0, Falses = 0, predcount = 0; + for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);PI != PE; ++PI){ + ++predcount; + LazyValueInfo::Tristate Ret = + LVI->getPredicateOnEdge(CondCmp->getPredicate(), + CondCmp->getOperand(0), CondConst, *PI, BB); + if (Ret == LazyValueInfo::True) + ++Trues; + else if (Ret == LazyValueInfo::False) + ++Falses; + } + + // If we can determine the branch direction statically, converted + // the conditional branch to an unconditional one. + if (Trues && Trues == predcount) { + RemovePredecessorAndSimplify(CondBr->getSuccessor(1), BB, TD); + BranchInst::Create(CondBr->getSuccessor(0), CondBr); + CondBr->eraseFromParent(); + return true; + } else if (Falses && Falses == predcount) { + RemovePredecessorAndSimplify(CondBr->getSuccessor(0), BB, TD); + BranchInst::Create(CondBr->getSuccessor(1), CondBr); + CondBr->eraseFromParent(); + return true; + } + } } // Check for some cases that are worth simplifying. Right now we want to look diff --git a/test/Transforms/JumpThreading/basic.ll b/test/Transforms/JumpThreading/basic.ll index 503d301892..ab1ab73f4e 100644 --- a/test/Transforms/JumpThreading/basic.ll +++ b/test/Transforms/JumpThreading/basic.ll @@ -147,11 +147,17 @@ define i32 @test6(i32 %A) { ; CHECK: @test6 %tmp455 = icmp eq i32 %A, 42 br i1 %tmp455, label %BB1, label %BB2 - -BB2: + +; CHECK: call i32 @f2() +; CHECK-NEXT: ret i32 3 + ; CHECK: call i32 @f1() -; CHECK-NEXT: call void @f3() -; CHECK-NEXT: ret i32 4 +; CHECK-NOT: br +; CHECK: call void @f3() +; CHECK-NOT: br +; CHECK: ret i32 4 + +BB2: call i32 @f1() br label %BB1 diff --git a/test/Transforms/JumpThreading/lvi-load.ll b/test/Transforms/JumpThreading/lvi-load.ll index c6af7b51d6..0bf4187d54 100644 --- a/test/Transforms/JumpThreading/lvi-load.ll +++ b/test/Transforms/JumpThreading/lvi-load.ll @@ -1,4 +1,4 @@ -; RUN: opt -S -jump-threading -enable-jump-threading-lvi < %s | FileCheck %s +; RUN: opt -S -jump-threading -enable-jump-threading-lvi -dce < %s | FileCheck %s target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" target triple = "x86_64-apple-darwin10.4" @@ -25,6 +25,7 @@ bb.i: ; preds = %entry %toBoolnot.i.i = icmp ult i8 %1, 21 ; <i1> [#uses=1] br i1 %toBoolnot.i.i, label %bb6.i.i, label %_ZN4llvm8dyn_castINS_11InstructionEPNS_5ValueEEENS_10cast_rettyIT_T0_E8ret_typeERKS6_.exit +; CHECK-NOT: assert bb6.i.i: ; preds = %bb.i tail call void @__assert_rtn(i8* getelementptr inbounds ([5 x i8]* @_ZZN4llvm4castINS_11InstructionEPNS_5ValueEEENS_10cast_rettyIT_T0_E8ret_typeERKS6_E8__func__, i64 0, i64 0), i8* getelementptr inbounds ([31 x i8]* @.str, i64 0, i64 0), i32 202, i8* getelementptr inbounds ([59 x i8]* @.str1, i64 0, i64 0)) noreturn unreachable |