From 7ac40c3ffabcdac9510e7efc4dc75a8ed2b32edb Mon Sep 17 00:00:00 2001 From: Frits van Bommel Date: Sun, 5 Dec 2010 18:29:03 +0000 Subject: [PATCH] Teach SimplifyCFG to turn (indirectbr (select cond, blockaddress(@fn, BlockA), blockaddress(@fn, BlockB))) into (br cond, BlockA, BlockB). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120943 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Utils/SimplifyCFG.cpp | 74 ++++++++++++++++++- test/Transforms/SimplifyCFG/indirectbr.ll | 118 ++++++++++++++++++++++++++++++ 2 files changed, 190 insertions(+), 2 deletions(-) diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index de1f12ec1b7..8e3ca419af8 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -374,6 +374,8 @@ static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { } else if (BranchInst *BI = dyn_cast(TI)) { if (BI->isConditional()) Cond = dyn_cast(BI->getCondition()); + } else if (IndirectBrInst *IBI = dyn_cast(TI)) { + Cond = dyn_cast(IBI->getAddress()); } TI->eraseFromParent(); @@ -1718,6 +1720,71 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { return true; } +// SimplifyIndirectBrOnSelect - Replaces +// (indirectbr (select cond, blockaddress(@fn, BlockA), +// blockaddress(@fn, BlockB))) +// with +// (br cond, BlockA, BlockB). +static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { + // Check that both operands of the select are block addresses. + BlockAddress *TBA = dyn_cast(SI->getTrueValue()); + BlockAddress *FBA = dyn_cast(SI->getFalseValue()); + if (!TBA || !FBA) + return false; + + // Extract the actual blocks. + BasicBlock *TrueBB = TBA->getBasicBlock(); + BasicBlock *FalseBB = FBA->getBasicBlock(); + + // Remove any superfluous successor edges from the CFG. + // First, figure out which successors to preserve. + // If TrueBB and FalseBB are equal, only try to preserve one copy of that + // successor. + BasicBlock *KeepEdge1 = TrueBB; + BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : 0; + + // Then remove the rest. + for (unsigned I = 0, E = IBI->getNumSuccessors(); I != E; ++I) { + BasicBlock *Succ = IBI->getSuccessor(I); + // Make sure only to keep exactly one copy of each edge. + if (Succ == KeepEdge1) + KeepEdge1 = 0; + else if (Succ == KeepEdge2) + KeepEdge2 = 0; + else + Succ->removePredecessor(IBI->getParent()); + } + + // Insert an appropriate new terminator. + if ((KeepEdge1 == 0) && (KeepEdge2 == 0)) { + if (TrueBB == FalseBB) + // We were only looking for one successor, and it was present. + // Create an unconditional branch to it. + BranchInst::Create(TrueBB, IBI); + else + // We found both of the successors we were looking for. + // Create a conditional branch sharing the condition of the select. + BranchInst::Create(TrueBB, FalseBB, SI->getCondition(), IBI); + } else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) { + // Neither of the selected blocks were successors, so this + // indirectbr must be unreachable. + new UnreachableInst(IBI->getContext(), IBI); + } else { + // One of the selected values was a successor, but the other wasn't. + // Insert an unconditional branch to the one that was found; + // the edge to the one that wasn't must be unreachable. + if (KeepEdge1 == 0) + // Only TrueBB was found. + BranchInst::Create(TrueBB, IBI); + else + // Only FalseBB was found. + BranchInst::Create(FalseBB, IBI); + } + + EraseTerminatorInstAndDCECond(IBI); + return true; +} + bool SimplifyCFGOpt::run(BasicBlock *BB) { bool Changed = false; Function *Fn = BB->getParent(); @@ -2072,13 +2139,16 @@ bool SimplifyCFGOpt::run(BasicBlock *BB) { if (IBI->getNumDestinations() == 0) { // If the indirectbr has no successors, change it to unreachable. new UnreachableInst(IBI->getContext(), IBI); - IBI->eraseFromParent(); + EraseTerminatorInstAndDCECond(IBI); Changed = true; } else if (IBI->getNumDestinations() == 1) { // If the indirectbr has one successor, change it to a direct branch. BranchInst::Create(IBI->getDestination(0), IBI); - IBI->eraseFromParent(); + EraseTerminatorInstAndDCECond(IBI); Changed = true; + } else if (SelectInst *SI = dyn_cast(IBI->getAddress())) { + if (SimplifyIndirectBrOnSelect(IBI, SI)) + return SimplifyCFG(BB) | true; } } diff --git a/test/Transforms/SimplifyCFG/indirectbr.ll b/test/Transforms/SimplifyCFG/indirectbr.ll index de4f5b60755..7fb4def5b93 100644 --- a/test/Transforms/SimplifyCFG/indirectbr.ll +++ b/test/Transforms/SimplifyCFG/indirectbr.ll @@ -62,3 +62,121 @@ entry: BB0: ret void } + + +; Make sure the blocks in the next few tests aren't trivially removable as +; successors by taking their addresses. + +@anchor = constant [13 x i8*] [ + i8* blockaddress(@indbrtest3, %L1), i8* blockaddress(@indbrtest3, %L2), i8* blockaddress(@indbrtest3, %L3), + i8* blockaddress(@indbrtest4, %L1), i8* blockaddress(@indbrtest4, %L2), i8* blockaddress(@indbrtest4, %L3), + i8* blockaddress(@indbrtest5, %L1), i8* blockaddress(@indbrtest5, %L2), i8* blockaddress(@indbrtest5, %L3), i8* blockaddress(@indbrtest5, %L4), + i8* blockaddress(@indbrtest6, %L1), i8* blockaddress(@indbrtest6, %L2), i8* blockaddress(@indbrtest6, %L3) +] + +; SimplifyCFG should turn the indirectbr into a conditional branch on the +; condition of the select. + +; CHECK: @indbrtest3 +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond, label %L1, label %L2 +; CHECK-NOT: indirectbr +; CHECK-NOT: br +; CHECK-NOT: L3: +define void @indbrtest3(i1 %cond, i8* %address) nounwind { +entry: + %indirect.goto.dest = select i1 %cond, i8* blockaddress(@indbrtest3, %L1), i8* blockaddress(@indbrtest3, %L2) + indirectbr i8* %indirect.goto.dest, [label %L1, label %L2, label %L3] + +L1: + call void @A() + ret void +L2: + call void @C() + ret void +L3: + call void @foo() + ret void +} + +; SimplifyCFG should turn the indirectbr into an unconditional branch to the +; only possible destination. +; As in @indbrtest1, it should really remove the branch entirely, but it doesn't +; because it's in the entry block. + +; CHECK: @indbrtest4 +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %L1 +define void @indbrtest4(i1 %cond) nounwind { +entry: + %indirect.goto.dest = select i1 %cond, i8* blockaddress(@indbrtest4, %L1), i8* blockaddress(@indbrtest4, %L1) + indirectbr i8* %indirect.goto.dest, [label %L1, label %L2, label %L3] + +L1: + call void @A() + ret void +L2: + call void @C() + ret void +L3: + call void @foo() + ret void +} + +; SimplifyCFG should turn the indirectbr into an unreachable because neither +; destination is listed as a successor. + +; CHECK: @indbrtest5 +; CHECK-NEXT: entry: +; CHECK-NEXT: unreachable +; CHECK-NEXT: } +define void @indbrtest5(i1 %cond, i8* %anchor) nounwind { +entry: + %indirect.goto.dest = select i1 %cond, i8* blockaddress(@indbrtest5, %L1), i8* blockaddress(@indbrtest5, %L2) +; This needs to have more than one successor for this test, otherwise it gets +; replaced with an unconditional branch to the single successor. + indirectbr i8* %indirect.goto.dest, [label %L3, label %L4] + +L1: + call void @A() + ret void +L2: + call void @C() + ret void +L3: + call void @foo() + ret void +L4: + call void @foo() + +; This keeps blockaddresses not otherwise listed as successors from being zapped +; before SimplifyCFG even looks at the indirectbr. + indirectbr i8* %anchor, [label %L1, label %L2] +} + +; The same as above, except the selected addresses are equal. + +; CHECK: @indbrtest6 +; CHECK-NEXT: entry: +; CHECK-NEXT: unreachable +; CHECK-NEXT: } +define void @indbrtest6(i1 %cond, i8* %anchor) nounwind { +entry: + %indirect.goto.dest = select i1 %cond, i8* blockaddress(@indbrtest6, %L1), i8* blockaddress(@indbrtest6, %L1) +; This needs to have more than one successor for this test, otherwise it gets +; replaced with an unconditional branch to the single successor. + indirectbr i8* %indirect.goto.dest, [label %L2, label %L3] + +L1: + call void @A() + ret void +L2: + call void @C() + ret void +L3: + call void @foo() + +; This keeps blockaddresses not otherwise listed as successors from being zapped +; before SimplifyCFG even looks at the indirectbr. + indirectbr i8* %anchor, [label %L1, label %L2] +} -- 2.11.0