[SimplifyCFG] Hoist common instructions on Switch.

[DianQK]

Summary

Sink common instructions are not always performance friendly. We need to implement hoist common instructions on switch instruction to solve the following problem:

define i1 @foo(i64 %a, i64 %b, i64 %c, i64 %d) {
start:
  %test = icmp eq i64 %a, %d
  br i1 %test, label %switch_bb, label %exit

switch_bb:                                        ; preds = %start
  switch i64 %a, label %bb0 [
    i64 1, label %bb1
    i64 2, label %bb2
  ]

bb0:                                              ; preds = %switch_bb
  %0 = icmp eq i64 %b, %c
  br label %exit

bb1:                                              ; preds = %switch_bb
  %1 = icmp eq i64 %b, %c
  br label %exit

bb2:                                              ; preds = %switch_bb
  %2 = icmp eq i64 %b, %c
  br label %exit

exit:                                             ; preds = %bb2, %bb1, %bb0, %start
  %result = phi i1 [ false, %start ], [ %0, %bb0 ], [ %1, %bb1 ], [ %2, %bb2 ]
  ret i1 %result
}

The pre-commit test is D156617.

[DianQK]

Added isSafeToHoistInstr check, but still need to fix patchable-function-entry-bti.ll failure.

[nikic]

Is it possible to instead generalize the HoistThenElseCodeToIf() transform to not require exactly two successors, so it can support switch as well?

[DianQK]

In D155711#4517725, @nikic wrote:

Is it possible to instead generalize the HoistThenElseCodeToIf() transform to not require exactly two successors, so it can support switch as well?

I considered that possibility. I'm concerned that this might have an impact on compile time for the two successors.
But it's more a question of whether the reordering and debug instructions can be more profitable for the switch instruction.
Using the same analysis on multiple successors can become more complex. Too long compile time?
But adding some options to control these behaviors may be appropriate. So I'll give it a new try.

Also, I feel like checking if the debug command is the same is a bit much.

[DianQK]

Maybe I need to know more about D84108.

[DianQK]

Now we can work with the unreachable instruction.
I will try to merge a generic hoist common instructions and add some test cases.

[DianQK]

Merge hoist common instructions, except that the termination instruction is not completed.

[DianQK]

Add the hoistCommonCodeFromSuccessors method as a generic hoist common code implementation.
The existing test cases look like they all pass. More test cases for the switch statement may need to be added.
There may be some duplicate calculations that can be eliminated, such as shouldHoistCommonInstructions. But I think most of the code is done.

[XChy]

Nice work to me! Just some nits here.
Can you create two patches to better show the difference before/after transform?
The first patch includes your unoptimized testcases without the fold. (Your first commit)
The second patch includes your optimized testcases and your code for the fold. (Your second commit, which is based on your first commit)
And then let the first patch be the parent revision of the second patch through "Edit Related Revisions".

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1552

Omit the braces of single-statement if/for.

llvm/test/Transforms/SimplifyCFG/hoist-common-code.ll

97 ↗

(On Diff #544763)

More positive/negative tests are needed.

[DianQK]

Split test cases and code changes into two commits.

[DianQK]

Remove redundant header files.

[DianQK]

In D155711#4544449, @XChy wrote:

Nice work to me! Just some nits here.
Can you create two patches to better show the difference before/after transform?
The first patch includes your unoptimized testcases without the fold. (Your first commit)
The second patch includes your optimized testcases and your code for the fold. (Your second commit, which is based on your first commit)
And then let the first patch be the parent revision of the second patch through "Edit Related Revisions".

Thanks, I tried it out.
Too busy this weekend to update this patch. But I've split the patch into two. It should look better now.
I should think carefully about test cases.

[DianQK]

Add more tests.

[DianQK]

Fixes backend-optimization-failure.cpp.
We should examine all instructions during each iteration to confirm the presence of a terminating one.

[DianQK]

Allows to hoist the side effect instruction.

[XChy]

LGTM. May commit it if no changes are requested by others in one day.

[nikic]

This looks pretty good to me. Only significant concern I have is the unreachable handling, which doesn't look quite correct to me.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1528

1563

instuctions -> instructions

Also this sounds like it's a count of instructions, while this is really a SkipFlags bitmask.

1593–1599

1599

Unless I'm missing something, I don't think this code is correct in the case where instructions are skipped. E.g. if the block is something like call @not_willreturn; unreachable and we skip over the first instruction and then see the unreachable, it would not be correct to ignore this successor. Is there a test for this?

I think you need to do the removal of unreachable blocks before the main loop, so you only handle the case where there is only unreachable in the block, not any other instructions.

1599

Omit braces for single line body.

1617

Could use all_of here.

1619

I think this may misbehave in the following case: You have BB1 and BB2 with same debug info and BB3 with different. Then BB1 and BB3 will skip it, but BB2 won't.

So I think you want to first do a check whether all are identical, and then skip or not skip debug info.

1630

This == 0 on a statistic doesn't really make sense to me... This is a global variable, not just for this run of the function.

1657

Why does this use a set rather than a vector?

1689

Omit braces for one line if.

1698

SmallVector

1703

Can always use the second code path? Should also work for branches.

7136

Leftover?

[DianQK]

Thanks to @XChy and @nikic. I apologize for making so many code issues. (T.T)

[DianQK]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1599

I moved this before the main loop to keep it simple. simplifyUnreachable and EarlyCSE have finished for this.

[DianQK]

Remove more braces.
Change remove_if to erase_if.

[DianQK]

Due to my rebase issue, re-update.

Probably due to my rebase last night causing https://reviews.llvm.org/D155711?vs=555039&id=555207#change-46AmBA3PEORL to get weird.

The full diff looks fine.

[DianQK]

ping @nikic
Will you continue to review here? Or should I migrate to GitHub?

[nikic]

This looks fine to me, but I think this is currently missing tests for the "hoist not first instruction" case for switch? We should have at least basic tests that this is supported and side effects are checked.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1579

I'd move this variable below the following if check (to before for (;;)).

1588

"hoist the instruction at the rest" -> "hoist instructions from the rest"?

1597

Drop llvm:: prefix.

1598

You are using iterator_range(SuccIterBegin, SuccIters.end()) in a lot of places. I think it may make sense to create a variable for this?

There is also make_first_range() to iterate over .first.

[DianQK]

Update as suggested.

[DianQK]

In D155711#4647910, @nikic wrote:

This looks fine to me, but I think this is currently missing tests for the "hoist not first instruction" case for switch? We should have at least basic tests that this is supported and side effects are checked.

Thanks. I added the switch variant to hoist-common-skip.ll.

[nikic]

LGTM, thanks!

[MaskRay]

Early heads-up we internally have identified a crash due to this change.

[MaskRay]

In D155711#4648928, @MaskRay wrote:

Early heads-up we internally have identified a crash due to this change.

I will try giving a reproduce later, but am reverting this now.

musttail call must precede a ret with an optional bitcast

[MaskRay]

In D155711#4648971, @MaskRay wrote:

In D155711#4648928, @MaskRay wrote:

Early heads-up we internally have identified a crash due to this change.

I will try giving a reproduce later, but am reverting this now.

musttail call must precede a ret with an optional bitcast

% cat x.ll
source_filename = "<stdin>"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define ptr @ham(ptr %arg, ptr %arg1, ptr %arg2, i64 %arg3, ptr %arg4, i64 %arg5) {
bb:
  %load = load i16, ptr %arg, align 2
  %and = and i16 %load, 1
  %icmp = icmp eq i16 %and, 0
  br i1 %icmp, label %bb7, label %bb6

bb6:                                              ; preds = %bb
  ret ptr null

bb7:                                              ; preds = %bb
  switch i16 %load, label %bb13 [
    i16 0, label %bb8
    i16 1, label %bb9
    i16 2, label %bb11
  ]

bb8:                                              ; preds = %bb7
  %call = musttail call ptr @zot(ptr %arg, ptr %arg1, ptr %arg2, i64 %arg3, ptr %arg4, i64 %arg5)
  ret ptr %call

bb9:                                              ; preds = %bb7
  %call10 = musttail call ptr @zot(ptr %arg, ptr %arg1, ptr %arg2, i64 %arg3, ptr %arg4, i64 %arg5)
  ret ptr %call10

bb11:                                             ; preds = %bb7
  %call12 = musttail call ptr @zot(ptr %arg, ptr %arg1, ptr %arg2, i64 %arg3, ptr %arg4, i64 %arg5)
  ret ptr %call12

bb13:                                             ; preds = %bb7
  unreachable
}

declare ptr @zot(ptr, ptr, ptr, i64, ptr, i64)
% opt -O2 -S < x.ll
musttail call must precede a ret with an optional bitcast
  %call = musttail call ptr @zot(ptr nonnull %arg, ptr %arg1, ptr %arg2, i64 %arg3, ptr %arg4, i64 %arg5)
LLVM ERROR: Broken module found, compilation aborted!
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
...

[DianQK]

In D155711#4648971, @MaskRay wrote:

In D155711#4648928, @MaskRay wrote:

Early heads-up we internally have identified a crash due to this change.

I will try giving a reproduce later, but am reverting this now.

musttail call must precede a ret with an optional bitcast

Okay. Thank you for the reproduce.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

class SimplifyCFGOpt {
   bool simplifyBranch(BranchInst *Branch, IRBuilder<> &Builder);
   bool simplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder);
   bool simplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder);
 
   bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
                                              IRBuilder<> &Builder);
 
   bool HoistThenElseCodeToIf(BranchInst *BI, bool EqTermsOnly);
+  bool hoistCommonInstsOnSwitch(SwitchInst *SI);
   bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB);
   bool SimplifyTerminatorOnSelect(Instruction *OldTerm, Value *Cond,
                                   BasicBlock *TrueBB, BasicBlock *FalseBB,
                                   uint32_t TrueWeight, uint32_t FalseWeight);
   bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder,
                                  const DataLayout &DL);
   bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select);
   bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);

 /// in the two blocks up into the branch block. The caller of this function
 /// guarantees that BI's block dominates BB1 and BB2. If EqTermsOnly is given,
 /// only perform hoisting in case both blocks only contain a terminator. In that
 /// case, only the original BI will be replaced and selects for PHIs are added.
 bool SimplifyCFGOpt::HoistThenElseCodeToIf(BranchInst *BI, bool EqTermsOnly) {
   // This does very trivial matching, with limited scanning, to find identical
   // instructions in the two blocks.  In particular, we don't want to get into
   // O(M*N) situations here where M and N are the sizes of BB1 and BB2.  As
   // such, we currently just scan for obviously identical instructions in an
   // identical order, possibly separated by the same number of non-identical
   // instructions.
   BasicBlock *BB1 = BI->getSuccessor(0); // The true destination.
   BasicBlock *BB2 = BI->getSuccessor(1); // The false destination
 
   // If either of the blocks has it's address taken, then we can't do this fold,
   // because the code we'd hoist would no longer run when we jump into the block
   // by it's address.
   if (BB1->hasAddressTaken() || BB2->hasAddressTaken())
     return false;
 
   BasicBlock::iterator BB1_Itr = BB1->begin();
   BasicBlock::iterator BB2_Itr = BB2->begin();
 
   Instruction *I1 = &*BB1_Itr++, *I2 = &*BB2_Itr++;
   // Skip debug info if it is not identical.
   DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);
   DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2);
   if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
     while (isa<DbgInfoIntrinsic>(I1))
       I1 = &*BB1_Itr++;
     while (isa<DbgInfoIntrinsic>(I2))
       I2 = &*BB2_Itr++;
   }
   if (isa<PHINode>(I1))
     return false;
 
   BasicBlock *BIParent = BI->getParent();
 
   bool Changed = false;
 
   auto _ = make_scope_exit([&]() {
     if (Changed)
       ++NumHoistCommonCode;
   });
 
   // Check if only hoisting terminators is allowed. This does not add new
   // instructions to the hoist location.
   if (EqTermsOnly) {
     // Skip any debug intrinsics, as they are free to hoist.
     auto *I1NonDbg = &*skipDebugIntrinsics(I1->getIterator());
     auto *I2NonDbg = &*skipDebugIntrinsics(I2->getIterator());
     if (!I1NonDbg->isIdenticalToWhenDefined(I2NonDbg))
       return false;
     if (!I1NonDbg->isTerminator())
       return false;
     // Now we know that we only need to hoist debug intrinsics and the
     // terminator. Let the loop below handle those 2 cases.
   }
 
   // Count how many instructions were not hoisted so far. There's a limit on how
   // many instructions we skip, serving as a compilation time control as well as
   // preventing excessive increase of life ranges.
   unsigned NumSkipped = 0;
 
   // Record any skipped instuctions that may read memory, write memory or have
   // side effects, or have implicit control flow.
   unsigned SkipFlagsBB1 = 0;
   unsigned SkipFlagsBB2 = 0;
 
   for (;;) {
     // If we are hoisting the terminator instruction, don't move one (making a
     // broken BB), instead clone it, and remove BI.
     if (I1->isTerminator() || I2->isTerminator()) {
       // If any instructions remain in the block, we cannot hoist terminators.
       if (NumSkipped || !I1->isIdenticalToWhenDefined(I2))
         return Changed;
       goto HoistTerminator;
     }
 
     if (I1->isIdenticalToWhenDefined(I2) &&
         // Even if the instructions are identical, it may not be safe to hoist
         // them if we have skipped over instructions with side effects or their
         // operands weren't hoisted.
         isSafeToHoistInstr(I1, SkipFlagsBB1) &&
         isSafeToHoistInstr(I2, SkipFlagsBB2) &&
         shouldHoistCommonInstructions(I1, I2, TTI)) {
       if (isa<DbgInfoIntrinsic>(I1) || isa<DbgInfoIntrinsic>(I2)) {
         assert(isa<DbgInfoIntrinsic>(I1) && isa<DbgInfoIntrinsic>(I2));
         // The debug location is an integral part of a debug info intrinsic
         // and can't be separated from it or replaced.  Instead of attempting
         // to merge locations, simply hoist both copies of the intrinsic.
         BIParent->splice(BI->getIterator(), BB1, I1->getIterator());
         BIParent->splice(BI->getIterator(), BB2, I2->getIterator());
       } else {
         // For a normal instruction, we just move one to right before the
         // branch, then replace all uses of the other with the first.  Finally,
         // we remove the now redundant second instruction.
         BIParent->splice(BI->getIterator(), BB1, I1->getIterator());
         if (!I2->use_empty())
           I2->replaceAllUsesWith(I1);
         I1->andIRFlags(I2);
         combineMetadataForCSE(I1, I2, true);
 
         // I1 and I2 are being combined into a single instruction.  Its debug
         // location is the merged locations of the original instructions.
         I1->applyMergedLocation(I1->getDebugLoc(), I2->getDebugLoc());
 
         I2->eraseFromParent();
       }
       Changed = true;
       ++NumHoistCommonInstrs;
     } else {
       if (NumSkipped >= HoistCommonSkipLimit)
         return Changed;
       // We are about to skip over a pair of non-identical instructions. Record
       // if any have characteristics that would prevent reordering instructions
       // across them.
       SkipFlagsBB1 |= skippedInstrFlags(I1);
       SkipFlagsBB2 |= skippedInstrFlags(I2);
if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
         I1 = &*BB1_Itr++;
       while (isa<DbgInfoIntrinsic>(I2))
         I2 = &*BB2_Itr++;
     }
   }
 
   return Changed;
 
 HoistTerminator:
   // It may not be possible to hoist an invoke.
   // FIXME: Can we define a safety predicate for CallBr?
   if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))
     return Changed;
 
   // TODO: callbr hoisting currently disabled pending further study.
   if (isa<CallBrInst>(I1))
     return Changed;
HoistTerminator:
 
   // Okay, it is safe to hoist the terminator.
   Instruction *NT = I1->clone();
   NT->insertInto(BIParent, BI->getIterator());
   if (!NT->getType()->isVoidTy()) {
     I1->replaceAllUsesWith(NT);
     I2->replaceAllUsesWith(NT);
     NT->takeName(I1);
   }
   Changed = true;
   ++NumHoistCommonInstrs;
 
   // Ensure terminator gets a debug location, even an unknown one, in case
   // it involves inlinable calls.
   NT->applyMergedLocation(I1->getDebugLoc(), I2->getDebugLoc());
 
   // PHIs created below will adopt NT's merged DebugLoc.
   IRBuilder<NoFolder> Builder(NT);
 
   // Hoisting one of the terminators from our successor is a great thing.
   // Unfortunately, the successors of the if/else blocks may have PHI nodes in
   // them.  If they do, all PHI entries for BB1/BB2 must agree for all PHI
   // nodes, so we insert select instruction to compute the final result.
   std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
   for (BasicBlock *Succ : successors(BB1)) {
     for (PHINode &PN : Succ->phis()) {
       Value *BB1V = PN.getIncomingValueForBlock(BB1);
       Value *BB2V = PN.getIncomingValueForBlock(BB2);
       if (BB1V == BB2V)
         continue;
 
for (BasicBlock *Succ : successors(BI))
       Updates.push_back({DominatorTree::Delete, BIParent, Succ});
 
   EraseTerminatorAndDCECond(BI);
   if (DTU)
     DTU->applyUpdates(Updates);
   return Changed;
 }
 
+/// Similar to HoistThenElseCodeToIf, but simpler. We don't care about
+/// instruction reordering and debugging instructions.
+bool SimplifyCFGOpt::hoistCommonInstsOnSwitch(SwitchInst *SI) {
+  unsigned NumSuccs = SI->getNumSuccessors();
+  if (NumSuccs < 2) {
+    return false;
+  }
+  auto *BB1 = SI->getSuccessor(0);
+  if (BB1->hasAddressTaken() || !BB1->getSinglePredecessor()) {
+    return false;
+  }
+
+  BasicBlock::iterator BB1Itr = BB1->begin();
+
+  Instruction *I1 = &*BB1Itr++;
+  if (isa<PHINode>(I1))
+    return false;
+
+  BasicBlock *BIParent = SI->getParent();
+
+  bool Changed = false;
+
+  auto _ = make_scope_exit([&]() {
+    if (Changed)
+      NumHoistCommonCode += NumSuccs;
+  });
+
+  SmallVector<BasicBlock::iterator, 8> OtherSuccIters;
+  OtherSuccIters.reserve(NumSuccs - 1);
+
+  for (unsigned Idx = 1; Idx < NumSuccs; ++Idx) {
+    auto *Succ = SI->getSuccessor(Idx);
+    if (Succ->hasAddressTaken() || !Succ->getSinglePredecessor()) {
+      return false;
+    }
+    BasicBlock::iterator SuccItr = Succ->begin();
+    OtherSuccIters.push_back(SuccItr);
+  }
+
+  for (;;) {
+    // We expect simplifyUncondBranch to complete the optimization of the
+    // termination instruction.
+    if (I1->isTerminator()) {
+      return Changed;
+    }
+    for (auto SuccIter : OtherSuccIters) {
+      Instruction *I2 = &*SuccIter;
+      if (!I1->isIdenticalToWhenDefined(I2) ||
+          !shouldHoistCommonInstructions(I1, I2, TTI)) {
+        return Changed;
+      }
+    }
+    for (auto SuccIter : OtherSuccIters) {
+      Instruction *I2 = &*SuccIter++;
+      BIParent->splice(SI->getIterator(), BB1, I1->getIterator());
+      if (!I2->use_empty())
+        I2->replaceAllUsesWith(I1);
+      I1->andIRFlags(I2);
+      combineMetadataForCSE(I1, I2, true);
+      I1->applyMergedLocation(I1->getDebugLoc(), I2->getDebugLoc());
+      I2->eraseFromParent();
+    }
+    I1 = &*BB1Itr++;
+    Changed = true;
+    ++NumHoistCommonInstrs;
+  }
+}
+
 // Check lifetime markers.
 static bool isLifeTimeMarker(const Instruction *I) {
   if (auto II = dyn_cast<IntrinsicInst>(I)) {
     switch (II->getIntrinsicID()) {
     default:
       break;
     case Intrinsic::lifetime_start:
     case Intrinsic::lifetime_end:
bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
   // optimisation pipeline.
   if (Options.ConvertSwitchToLookupTable &&
       SwitchToLookupTable(SI, Builder, DTU, DL, TTI))
     return requestResimplify();
 
   if (ReduceSwitchRange(SI, Builder, DL, TTI))
     return requestResimplify();
 
+  if (HoistCommon && hoistCommonInstsOnSwitch(SI))
+    return requestResimplify();
+
   return false;
 }
 
 bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
   BasicBlock *BB = IBI->getParent();
   bool Changed = false;
 
   // Eliminate redundant destinations.
bool SimplifyCFGOpt::simplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) {
   // from BI.  We know that the condbr dominates the two blocks, so see if
   // there is any identical code in the "then" and "else" blocks.  If so, we
   // can hoist it up to the branching block.
   if (BI->getSuccessor(0)->getSinglePredecessor()) {
     if (BI->getSuccessor(1)->getSinglePredecessor()) {
       if (HoistCommon && HoistThenElseCodeToIf(BI, !Options.HoistCommonInsts))
         return requestResimplify();
     } else {
       // If Successor #1 has multiple preds, we may be able to conditionally
       // execute Successor #0 if it branches to Successor #1.
       Instruction *Succ0TI = BI->getSuccessor(0)->getTerminator();
       if (Succ0TI->getNumSuccessors() == 1 &&
           Succ0TI->getSuccessor(0) == BI->getSuccessor(1))
         if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0)))
           return requestResimplify();
     }
   } else if (BI->getSuccessor(1)->getSinglePredecessor()) {

llvm/test/Transforms/SimplifyCFG/hoist-common-code-on-switch.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes='simplifycfg<hoist-common-insts;no-sink-common-insts>' -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s
+
+define i1 @foo(i64 %a, i64 %b, i64 %c) unnamed_addr {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i64 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    ret i1 [[TMP0]]
+;
+start:
+  switch i64 %a, label %bb0 [
+  i64 1, label %bb1
+  i64 2, label %bb2
+  ]
+
+bb0:                                              ; preds = %start
+  %0 = icmp eq i64 %b, %c
+  br label %exit
+
+bb1:                                              ; preds = %start
+  %1 = icmp eq i64 %b, %c
+  br label %exit
+
+bb2:                                              ; preds = %start
+  %2 = icmp eq i64 %b, %c
+  br label %exit
+
+exit:                                             ; preds = %bb2, %bb1, %bb0
+  %result = phi i1 [ %0, %bb0 ], [ %1, %bb1 ], [ %2, %bb2 ]
+  ret i1 %result
+}