From 26e097ca4bdb31000655ff9ec39fe7d9b7ea226d Mon Sep 17 00:00:00 2001 From: Frits van Bommel Date: Wed, 15 Dec 2010 09:51:20 +0000 Subject: [PATCH] Teach jump threading to "look through" a select when the branch direction of a terminator depends on it. When it sees a promising select it now tries to figure out whether the condition of the select is known in any of the predecessors and if so it maps the operands appropriately. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121859 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/JumpThreading.cpp | 34 +++++++ test/Transforms/JumpThreading/select.ll | 123 ++++++++++++++++++++++++ 2 files changed, 157 insertions(+) create mode 100644 test/Transforms/JumpThreading/select.ll diff --git a/lib/Transforms/Scalar/JumpThreading.cpp b/lib/Transforms/Scalar/JumpThreading.cpp index b44bc5efef5..e59ae31e134 100644 --- a/lib/Transforms/Scalar/JumpThreading.cpp +++ b/lib/Transforms/Scalar/JumpThreading.cpp @@ -538,6 +538,40 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, } } + if (SelectInst *SI = dyn_cast(I)) { + // Handle select instructions where at least one operand is a known constant + // and we can figure out the condition value for any predecessor block. + Constant *TrueVal = getKnownConstant(SI->getTrueValue(), Preference); + Constant *FalseVal = getKnownConstant(SI->getFalseValue(), Preference); + PredValueInfoTy Conds; + if ((TrueVal || FalseVal) && + ComputeValueKnownInPredecessors(SI->getCondition(), BB, Conds, + WantInteger)) { + for (unsigned i = 0, e = Conds.size(); i != e; ++i) { + Constant *Cond = Conds[i].first; + + // Figure out what value to use for the condition. + bool KnownCond; + if (ConstantInt *CI = dyn_cast(Cond)) { + // A known boolean. + KnownCond = CI->isOne(); + } else { + assert(isa(Cond) && "Unexpected condition value"); + // Either operand will do, so be sure to pick the one that's a known + // constant. + // FIXME: Do this more cleverly if both values are known constants? + KnownCond = (TrueVal != 0); + } + + // See if the select has a known constant value for this predecessor. + if (Constant *Val = KnownCond ? TrueVal : FalseVal) + Result.push_back(std::make_pair(Val, Conds[i].second)); + } + + return !Result.empty(); + } + } + // If all else fails, see if LVI can figure out a constant value for us. Constant *CI = LVI->getConstant(V, BB); if (Constant *KC = getKnownConstant(CI, Preference)) { diff --git a/test/Transforms/JumpThreading/select.ll b/test/Transforms/JumpThreading/select.ll new file mode 100644 index 00000000000..8a81857736a --- /dev/null +++ b/test/Transforms/JumpThreading/select.ll @@ -0,0 +1,123 @@ +; RUN: opt -S -jump-threading < %s | FileCheck %s + +declare void @foo() +declare void @bar() +declare void @baz() +declare void @quux() + + +; Jump threading of branch with select as condition. +; Mostly theoretical since instruction combining simplifies all selects of +; booleans where at least one operand is true/false/undef. + +; CHECK: @test_br +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond, label %L1, +define void @test_br(i1 %cond, i1 %value) nounwind { +entry: + br i1 %cond, label %L0, label %L3 +L0: + %expr = select i1 %cond, i1 true, i1 %value + br i1 %expr, label %L1, label %L2 + +L1: + call void @foo() + ret void +L2: + call void @bar() + ret void +L3: + call void @baz() + br label %L0 +} + + +; Jump threading of switch with select as condition. + +; CHECK: @test_switch +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond, label %L1, +define void @test_switch(i1 %cond, i8 %value) nounwind { +entry: + br i1 %cond, label %L0, label %L4 +L0: + %expr = select i1 %cond, i8 1, i8 %value + switch i8 %expr, label %L3 [i8 1, label %L1 i8 2, label %L2] + +L1: + call void @foo() + ret void +L2: + call void @bar() + ret void +L3: + call void @baz() + ret void +L4: + call void @quux() + br label %L0 +} + +; Make sure the blocks in the indirectbr test aren't trivially removable as +; successors by taking their addresses. +@anchor = constant [3 x i8*] [ + i8* blockaddress(@test_indirectbr, %L1), + i8* blockaddress(@test_indirectbr, %L2), + i8* blockaddress(@test_indirectbr, %L3) +] + + +; Jump threading of indirectbr with select as address. + +; CHECK: @test_indirectbr +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond, label %L1, label %L3 +define void @test_indirectbr(i1 %cond, i8* %address) nounwind { +entry: + br i1 %cond, label %L0, label %L3 +L0: + %indirect.goto.dest = select i1 %cond, i8* blockaddress(@test_indirectbr, %L1), i8* %address + indirectbr i8* %indirect.goto.dest, [label %L1, label %L2, label %L3] + +L1: + call void @foo() + ret void +L2: + call void @bar() + ret void +L3: + call void @baz() + ret void +} + + +; A more complicated case: the condition is a select based on a comparison. + +; CHECK: @test_switch_cmp +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond, label %L0, label %[[THREADED:[A-Za-z.0-9]+]] +; CHECK: [[THREADED]]: +; CHECK-NEXT: call void @quux +; CHECK-NEXT: br label %L1 +define void @test_switch_cmp(i1 %cond, i32 %val, i8 %value) nounwind { +entry: + br i1 %cond, label %L0, label %L4 +L0: + %val.phi = phi i32 [%val, %entry], [-1, %L4] + %cmp = icmp slt i32 %val.phi, 0 + %expr = select i1 %cmp, i8 1, i8 %value + switch i8 %expr, label %L3 [i8 1, label %L1 i8 2, label %L2] + +L1: + call void @foo() + ret void +L2: + call void @bar() + ret void +L3: + call void @baz() + ret void +L4: + call void @quux() + br label %L0 +} -- 2.34.1