[LoopInterchange] Disallow interchange when memory accesses are guarded by control flow (PR48057)

[TaWeiTu]

Summary

If instructions that have side effects are guarded by control flow,
the order of execution might differ after interchanging the loops
and results in incorrect behaviour (the branch condition may depends
on the execution order).

This fixes https://bugs.llvm.org/show_bug.cgi?id=48057

[TaWeiTu]

This comment was removed by TaWeiTu.

[TaWeiTu]

This comment was removed by TaWeiTu.

[TaWeiTu]

• Remove unnecessary lines in the test case

[Whitney]

This comment was removed by Whitney.

[fhahn]

Is this fixing a similar issue to D91228 /D87879?

[TaWeiTu]

In D97828#2607047, @fhahn wrote:

Is this fixing a similar issue to D91228 /D87879?

Yes, the intention is the same.
I didn't know about these patches before, and I just test the reproducer PR47523 (the one D87879 is trying to address) against my patch, and the issue is indeed resolved (D91228 is addressing the exact same PR as this one does).

[TaWeiTu]

The following test in lcssa.ll is failing:

define void @lcssa_05(i32* %ptr) {
entry:
  br label %outer.header

outer.header:                                     ; preds = %outer.inc, %entry
  %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
  br label %for.body3

for.body3:                                        ; preds = %bb3, %outer.header
  %iv.inner = phi i64 [ %iv.inner.next, %bb3 ], [ 1, %outer.header ]
  br i1 undef, label %bb2, label %bb3

bb2:                                              ; preds = %for.body3
  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
  %vA = load i32, i32* %arrayidx5
  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
  %vC = load i32, i32* %arrayidx9
  %add = add nsw i32 %vA, %vC
  br label %bb3

bb3:                                              ; preds = %bb2, %for.body3
  %addp = phi i32 [ %add, %bb2 ], [ 0, %for.body3 ]
  store i32 %addp, i32* %ptr
  %iv.inner.next = add nuw nsw i64 %iv.inner, 1
  %exitcond = icmp eq i64 %iv.inner.next, 100
  br i1 %exitcond, label %outer.inc, label %for.body3

outer.inc:                                        ; preds = %bb3
  %iv.inner.lcssa = phi i64 [ %iv.inner, %bb3 ]
  %iv.outer.next = add nsw i64 %iv.outer, 1
  %cmp = icmp eq i64 %iv.outer.next, 100
  br i1 %cmp, label %outer.header, label %for.exit

for.exit:                                         ; preds = %outer.inc
  %iv.inner.lcssa.lcssa = phi i64 [ %iv.inner.lcssa, %outer.inc ]
  store i64 %iv.inner.lcssa.lcssa, i64* @Y
  br label %for.end16

for.end16:                                        ; preds = %for.exit
  ret void
}

The test is expecting the loops to be interchanged, but judging from br i1 undef, label %bb2, label %bb3 I think the interchange should probabily be considered invalid in this case?

[TaWeiTu]

• Add testcase of PR47523

[Whitney]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1153

can use getLoopFor?
https://llvm.org/doxygen/classllvm_1_1LoopInfoBase.html#a7a7c8e0e4f836c13c015b62e18f386bd

[TaWeiTu]

• Use LoopInfo::getLoopFor

[Whitney]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1150

In what scenario, outer loop contains instructions guarded by control flow?
(I assume loop interchange operate on tight loops.)

[TaWeiTu]

• Only check basic blocks in the inner loop

[TaWeiTu]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1150

Thanks for pointing that out! I think you are right.

[TaWeiTu]

ping

[Whitney]

Have you considered the case where the blocks guarded by control flow doesn't have memory operation, but affect memory operation through phi?

bb1:
  br %cond, bb2, bb3
bb2:
  br bb4
bb3:
  br bb4
bb4:
  %t = phi [ %t2, %bb2 ], [ %t3, %bb3 ]
  store %t, %p

[TaWeiTu]

Consider instructions that are indirectly affected by the control flow

[TaWeiTu]

In D97828#2624775, @Whitney wrote:

Have you considered the case where the blocks guarded by control flow doesn't have memory operation, but affect memory operation through phi?

bb1:
  br %cond, bb2, bb3
bb2:
  br bb4
bb3:
  br bb4
bb4:
  %t = phi [ %t2, %bb2 ], [ %t3, %bb3 ]
  store %t, %p

I've updated the patch to perform a more comprehensive check that consider instructions that are indirectly guarded by the control flow.

[TaWeiTu]

Gentle ping

[TaWeiTu]

Ping

[TaWeiTu]

Ping

[Whitney]

@TaWeiTu How do you want to handle the lcssa.ll failure? Maybe we can only disallow memory accesses that are guarded by loop variant condition?

[TaWeiTu]

• Skip loop-invariant-guarded blocks

[TaWeiTu]

In D97828#2674875, @Whitney wrote:

@TaWeiTu How do you want to handle the lcssa.ll failure? Maybe we can only disallow memory accesses that are guarded by loop variant condition?

Now only loop-variant-guarded blocks are considered "bad". lcssa.ll should be fixed.
We should probably also add logic to check whether the orders of memory accesses actually change after interchanging the loop, but I think it's beyond the scope of this patch and can be improved in the future.

[Whitney]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

989

  br cond, BB1, BB2
BB1:
  br BB3
BB2
  br BB3

BB3 should not guarded by a loop variant block, but this function would return BB1, BB2, and BB3.

[congzhe]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

989

I agree with this concern. I'm wondering if we can do this: instead of the entire worklist algorithm in this function, can we just loop over all BBs in the inner loop that are successors of loop-variant cmps, and check if they dominate the loop latch?

Currently in loop interchange the inner loop latch is also the (only) inner loop exiting block, therefore a BB that does not dominate the inner latch can be considered as involved in control-flow divergence. This way the treatment of the above case would be seemingly easier.

1035

is OpBlock is not from LoopVariantGuardedBlocks, would interchange be legal?

1048

would it simplify the logic if we use only GuardedInst instead of both GuardedInst and Worklist, and directly check for every instruction I in GuardedInst, if any of I or users of I accesses memory then we bail out (detailed checks in the suggestion below)?

This way we can also avoid looping over all instructions in the loop as in line 1061.

1066

IMHO maybe we make the check more fine-grained.

1. If the value being stored is a loop-invariant, then it would not break legality.

2. Otherwise if we store (loop-variants) to the same location, then bail out.

3. Otherwise if we store (loop-variants) not to the same location and the memory locations do not alias, then it would not break legality. I'm thinking of cases like cond && B[i][j] = A[i][j] inside the inner loop.

Suggestion No.3 might be less straightforward to implement, but No.1/No.2 is hopefully more straightforward to implement.

llvm/test/Transforms/LoopInterchange/control-flow.ll

153

is %tobool a loop-invariant? I guess interchange in this case is actually legal should %0 is a loop-invariant?

If in this IR we hoist %0 outside of the loop nest (can we add the corresponding test case), I guess loop interchange should not bail out but with this patch it would bail out. Maybe it makes more sense to use SCEV::isLoopInvariant() rather than Loop::isLoopInvariant() in function getLoopVariantGuardedBlocks().

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) {
   return nullptr;
 }
 
 namespace {
 
 /// LoopInterchangeLegality checks if it is legal to interchange the loop.
 class LoopInterchangeLegality {
 public:
-  LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
-                          OptimizationRemarkEmitter *ORE)
-      : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
+  LoopInterchangeLegality(Loop *Outer, Loop *Inner, DominatorTree *DT,
+                          ScalarEvolution *SE, OptimizationRemarkEmitter *ORE)
+      : OuterLoop(Outer), InnerLoop(Inner), DT(DT), SE(SE), ORE(ORE) {}
 
   /// Check if the loops can be interchanged.
   bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
                            CharMatrix &DepMatrix);
 
   /// Check if the loop structure is understood. We do not handle triangular
   /// loops for now.
   bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
private:
   /// to be passed as \p InnerLoop.
   bool findInductionAndReductions(Loop *L,
                                   SmallVector<PHINode *, 8> &Inductions,
                                   Loop *InnerLoop);
 
   Loop *OuterLoop;
   Loop *InnerLoop;
 
+  DominatorTree *DT;
   ScalarEvolution *SE;
 
   /// Interface to emit optimization remarks.
   OptimizationRemarkEmitter *ORE;
 
   /// Set of reduction PHIs taking part of a reduction across the inner and
   /// outer loop.
   SmallPtrSet<PHINode *, 4> OuterInnerReductions;
#endif
     return Changed;
   }
 
   bool processLoop(Loop *InnerLoop, Loop *OuterLoop, unsigned InnerLoopId,
                    unsigned OuterLoopId, BasicBlock *LoopNestExit,
                    std::vector<std::vector<char>> &DependencyMatrix) {
     LLVM_DEBUG(dbgs() << "Processing InnerLoopId = " << InnerLoopId
                       << " and OuterLoopId = " << OuterLoopId << "\n");
-    LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE);
+    LoopInterchangeLegality LIL(OuterLoop, InnerLoop, DT, SE, ORE);
     if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
       LLVM_DEBUG(dbgs() << "Not interchanging loops. Cannot prove legality.\n");
       return false;
     }
     LLVM_DEBUG(dbgs() << "Loops are legal to interchange\n");
     LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE, ORE);
     if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) {
       LLVM_DEBUG(dbgs() << "Interchanging loops not profitable.\n");
for (PHINode &PHI : LoopNestExit->phis()) {
      //        well.
      if (OuterLoop->getLoopLatch()->getUniquePredecessor() == nullptr)
        return false;
     }
   }
   return true;
 }
 
+// Get a list of blocks that are guarded by branches operating on loop variant
+// conditions, excluding the backedges of the loop.
+static DenseSet<BasicBlock *> getLoopVariantGuardedBlocks(Loop *L) {
+  SmallVector<BasicBlock *> Worklist;
+  DenseSet<BasicBlock *> GuardedBlocks;
+
+  const BasicBlock *Header = L->getHeader();
+
+  for (BasicBlock *BB : L->getBlocks()) {
+    if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
+      if (BI->isUnconditional())
+        continue;
+      Value *Cond = BI->getCondition();
+      if (!L->isLoopInvariant(Cond))
+        Worklist.push_back(BB);
+    }
+  }
+
+  while (!Worklist.empty()) {
+    BasicBlock *BB = Worklist.pop_back_val();
+    for (BasicBlock *Succ : successors(BB)) {
+      // If this is a backedge or the successor is not contained in the loop.
+      if (Succ == Header || !L->contains(Succ))
+        continue;
+      auto Result = GuardedBlocks.insert(Succ);
+      if (Result.second)
+        Worklist.push_back(Succ);
+    }
+  }
+
+  LLVM_DEBUG({
+    dbgs() << "List of guarded blocks:";
+    for (BasicBlock *BB : GuardedBlocks)
+      dbgs() << " " << BB->getName();
+    dbgs() << "\n";
+  });
+
+  return GuardedBlocks;
+}
+
+// Check whether there are unsafe instructions guarded by control flow. That is,
+// if an unsafe instruction directly or indirectly depends on how the control
+// flow goes, the loop interchange should be considered illegal.
+static bool haveControlFlowGuardedUnsafeInstructions(Loop *L,
+                                                     DominatorTree *DT) {
+  const BasicBlock *LoopLatch = L->getLoopLatch();
+  const DenseSet<BasicBlock *> LoopVariantGuardedBlocks =
+      getLoopVariantGuardedBlocks(L);
+
+  DenseSet<Instruction *> GuardedInst;
+  SmallVector<Instruction *, 8> Worklist;
+
+  // First of all, we put all instructions located in basic blocks that are
+  // directly guarded by control flow into the worklist. This includes PHI nodes
+  // that depend on such blocks as well.
+  for (BasicBlock *BB : L->getBlocks()) {
+    // Skip blocks which are only guarded by branches operating on loop
+    // invariant conditions.
+    if (!LoopVariantGuardedBlocks.count(BB))
+      continue;
+    bool Dominate = DT->dominates(BB, LoopLatch);
+    for (Instruction &I : *BB) {
+      bool Guarded = !Dominate;
+      if (PHINode *PHI = dyn_cast<PHINode>(&I)) {
+        for (BasicBlock *OpBlock : PHI->blocks())
+          Guarded |= !DT->dominates(OpBlock, LoopLatch);
+      }
+
+      if (Guarded) {
+        GuardedInst.insert(&I);
+        Worklist.push_back(&I);
+      }
+    }
+  }
+
+  // Calculate all instructions that are directly or indirectly dependant on
+  // instructions in the worklist.
+  while (!Worklist.empty()) {
+    Instruction *Inst = Worklist.pop_back_val();
+    for (User *U : Inst->users()) {
+      if (Instruction *I = dyn_cast<Instruction>(U)) {
+        auto Result = GuardedInst.insert(I);
+        if (Result.second)
+          Worklist.push_back(I);
+      }
+    }
+  }
+
+  // Check if either the loop contains unsafe instructions guarded by
+  // control flow.
+  for (BasicBlock *BB : L->getBlocks()) {
+    for (Instruction &I : *BB) {
+      if (!I.mayHaveSideEffects() && !I.mayReadFromMemory())
+        continue;
+      if (GuardedInst.find(&I) != GuardedInst.end())
+        return true;
+    }
+  }
+  return false;
+}
+
 bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
                                                   unsigned OuterLoopId,
                                                   CharMatrix &DepMatrix) {
   if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
     LLVM_DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
                       << " and OuterLoopId = " << OuterLoopId
                       << " due to dependence\n");
     ORE->emit([&]() {
ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
                                       OuterLoop->getStartLoc(),
                                       OuterLoop->getHeader())
              << "Found unsupported PHI node in loop exit.";
     });
     return false;
   }
 
+  if (haveControlFlowGuardedUnsafeInstructions(InnerLoop, DT)) {
+    LLVM_DEBUG(dbgs() << "Instructions guarded by control flow may break "
+                         "loop interchange.\n");
+    ORE->emit([&]() {
+      return OptimizationRemarkMissed(
+                 DEBUG_TYPE, "InvalidInstructionWithControlFlow",
+                 InnerLoop->getStartLoc(), InnerLoop->getHeader())
+             << "Instructions guarded by control flow may break loop "
+                "interchange.\n";
+    });
+    return false;
+  }
+
   return true;
 }
 
 int LoopInterchangeProfitability::getInstrOrderCost() {
   unsigned GoodOrder, BadOrder;
   BadOrder = GoodOrder = 0;
   for (BasicBlock *BB : InnerLoop->blocks()) {
     for (Instruction &Ins : *BB) {

llvm/test/Transforms/LoopInterchange/control-flow.ll

+; RUN: opt -loop-interchange -debug-only=loop-interchange 2>&1 %s | FileCheck %s
+
+; Test case of PR48057.
+
+; CHECK: Instructions guarded by control flow may break loop interchange.
+; CHECK-NEXT: Not interchanging loops. Cannot prove legality.
+
+@b = dso_local global [7 x [8 x i8]] [[8 x i8] zeroinitializer, [8 x i8] zeroinitializer, [8 x i8] zeroinitializer, [8 x i8] zeroinitializer, [8 x i8] c"\05\00\00\00\00\00\00\00", [8 x i8] zeroinitializer, [8 x i8] c"\02\03\00\00\00\00\00\00"], align 16
+@c = dso_local global i32 0, align 4
+@d = dso_local global i32 0, align 4
+@e = dso_local global i16 0, align 2
+
+define internal fastcc void @func() {
+entry:
+  %.pr = load i32, i32* @c, align 4
+  %cmp2 = icmp slt i32 %.pr, 8
+  br i1 %cmp2, label %for.cond1.preheader.preheader, label %for.end13
+
+for.cond1.preheader.preheader:                    ; preds = %entry
+  %0 = sext i32 %.pr to i64
+  %1 = sub i32 7, %.pr
+  %2 = zext i32 %1 to i64
+  %3 = add i64 %0, %2
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond1.preheader.preheader, %for.inc12
+  %indvars.iv4 = phi i64 [ %0, %for.cond1.preheader.preheader ], [ %indvars.iv.next5, %for.inc12 ]
+  br label %for.body2
+
+for.body2:                                        ; preds = %for.cond1.preheader, %land.end
+  %indvars.iv = phi i64 [ 4, %for.cond1.preheader ], [ %indvars.iv.next, %land.end ]
+  %4 = add nuw nsw i64 %indvars.iv, 2
+  %arrayidx4 = getelementptr inbounds [7 x [8 x i8]], [7 x [8 x i8]]* @b, i64 0, i64 %4, i64 %indvars.iv4
+  %5 = load i8, i8* %arrayidx4, align 1
+  %tobool5.not = icmp eq i8 %5, 0
+  br i1 %tobool5.not, label %land.end, label %land.rhs
+
+land.rhs:                                         ; preds = %for.body2
+  %arrayidx8 = getelementptr inbounds [7 x [8 x i8]], [7 x [8 x i8]]* @b, i64 0, i64 %indvars.iv, i64 0
+  %6 = load i8, i8* %arrayidx8, align 8
+  %conv9 = sext i8 %6 to i16
+  store i16 %conv9, i16* @e, align 2
+  br label %land.end
+
+land.end:                                         ; preds = %land.rhs, %for.body2
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %tobool.not = icmp eq i64 %indvars.iv.next, 0
+  br i1 %tobool.not, label %for.inc12, label %for.body2
+
+for.inc12:                                        ; preds = %land.end
+  %indvars.iv.next5 = add nsw i64 %indvars.iv4, 1
+  %exitcond = icmp ne i64 %indvars.iv.next5, 8
+  br i1 %exitcond, label %for.cond1.preheader, label %for.cond.for.end13_crit_edge
+
+for.cond.for.end13_crit_edge:                     ; preds = %for.inc12
+  %7 = add i64 %3, 1
+  %8 = trunc i64 %7 to i32
+  store i32 0, i32* @d, align 4
+  store i32 %8, i32* @c, align 4
+  br label %for.end13
+
+for.end13:                                        ; preds = %for.cond.for.end13_crit_edge, %entry
+  ret void
+}
+
+; Test case of PR47523.
+
+; CHECK: Instructions guarded by control flow may break loop interchange.
+; CHECK-NEXT: Not interchanging loops. Cannot prove legality.
+
+%struct.a = type { i8 }
+
+@f = dso_local local_unnamed_addr global [4 x [9 x i32]] [[9 x i32] [i32 5, i32 3, i32 0, i32 0, i32 0, i32 0, i32 0, i32 0, i32 0], [9 x i32] zeroinitializer, [9 x i32] zeroinitializer, [9 x i32] zeroinitializer], align 4
+@g = common dso_local local_unnamed_addr global i32 0, align 4
+@h = common dso_local global [1 x %struct.a] zeroinitializer, align 1
+
+define dso_local i32 @main() local_unnamed_addr {
+for.cond2.preheader.preheader.i:
+  %0 = sext i32 undef to i64
+  br label %for.cond2.preheader.i
+
+for.cond2.preheader.i:                            ; preds = %for.end11.i, %for.cond2.preheader.preheader.i
+  %indvars.iv20.i = phi i64 [ %0, %for.cond2.preheader.preheader.i ], [ %indvars.iv.next21.i, %for.end11.i ]
+  br label %for.body4.i
+
+for.body4.i:                                      ; preds = %if.end.i, %for.cond2.preheader.i
+  %indvars.iv.i = phi i64 [ 0, %for.cond2.preheader.i ], [ %indvars.iv.next.i, %if.end.i ]
+  %arrayidx6.i = getelementptr inbounds [4 x [9 x i32]], [4 x [9 x i32]]* @f, i64 0, i64 %indvars.iv.i, i64 %indvars.iv20.i
+  %1 = load i32, i32* %arrayidx6.i, align 4
+  %tobool.i = icmp eq i32 %1, 0
+  br i1 %tobool.i, label %land.end.i, label %land.rhs.i
+
+land.rhs.i:                                       ; preds = %for.body4.i
+  store i16 3, i16* bitcast (i32* @g to i16*), align 4
+  br label %land.end.i
+
+land.end.i:                                       ; preds = %land.rhs.i, %for.body4.i
+  br i1 icmp eq (i64 urem (i64 zext (i16 ptrtoint ([1 x %struct.a]* @h to i16) to i64), i64 4073709551606), i64 0), label %if.end.i, label %if.then.i
+
+if.then.i:                                        ; preds = %land.end.i
+  %2 = load i16, i16* bitcast (i32* @g to i16*), align 4
+  %inc.i = add i16 %2, 1
+  store i16 %inc.i, i16* bitcast (i32* @g to i16*), align 4
+  br label %if.end.i
+
+if.end.i:                                         ; preds = %if.then.i, %land.end.i
+  %indvars.iv.next.i = add nuw nsw i64 %indvars.iv.i, 1
+  %exitcond.i = icmp eq i64 %indvars.iv.next.i, 3
+  br i1 %exitcond.i, label %for.end11.i, label %for.body4.i
+
+for.end11.i:                                      ; preds = %if.end.i
+  %indvars.iv.next21.i = add nsw i64 %indvars.iv20.i, 1
+  %cmp.i = icmp slt i64 %indvars.iv20.i, 2
+  br i1 %cmp.i, label %for.cond2.preheader.i, label %for.cond.for.end14_crit_edge.i
+
+for.cond.for.end14_crit_edge.i:                   ; preds = %for.end11.i
+  br label %h.exit
+
+h.exit:                                           ; preds = %for.cond.for.end14_crit_edge.i
+  %3 = load i32, i32* @g, align 4
+  ret i32 0
+}
+
+; void control_flow(bool *cond) {
+;   for (int i = 0; i < 100; ++i) {
+;     for (int j = 0; j < 100; ++j) {
+;       int *ptr = *cond ? &B : &C;
+;       A[j][i] = *ptr;
+;     }
+;   }
+; }
+;
+; Interchange is illegal because the value of *ptr depends on the value of *cond.
+; The store into A[j][i] is implicitly guarded by control flow according to its operands.
+
+@A = dso_local global [100 x [100 x i32]] zeroinitializer, align 16
+@B = dso_local global i32 0, align 4
+@C = dso_local global i32 0, align 4
+
+; CHECK: Instructions guarded by control flow may break loop interchange.
+; CHECK-NEXT: Not interchanging loops. Cannot prove legality.
+define dso_local void @_Z12control_flowPVb(i8* %cond) #0 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.inc6
+  %i.02 = phi i32 [ 0, %entry ], [ %inc7, %for.inc6 ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body, %for.inc
+  %j.01 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
+  %0 = load i8, i8* %cond, align 1
+  %tobool = trunc i8 %0 to i1
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %for.body3
+  br label %if.end
+
+if.else:                                          ; preds = %for.body3
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %ptr.0 = phi i32* [ @B, %if.then ], [ @C, %if.else ]
+  %1 = load i32, i32* %ptr.0, align 4
+  %idxprom = sext i32 %j.01 to i64
+  %arrayidx = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %idxprom
+  %idxprom4 = sext i32 %i.02 to i64
+  %arrayidx5 = getelementptr inbounds [100 x i32], [100 x i32]* %arrayidx, i64 0, i64 %idxprom4
+  store i32 %1, i32* %arrayidx5, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %inc = add nsw i32 %j.01, 1
+  %cmp2 = icmp slt i32 %inc, 100
+  br i1 %cmp2, label %for.body3, label %for.end
+
+for.end:                                          ; preds = %for.inc
+  br label %for.inc6
+
+for.inc6:                                         ; preds = %for.end
+  %inc7 = add nsw i32 %i.02, 1
+  %cmp = icmp slt i32 %inc7, 100
+  br i1 %cmp, label %for.body, label %for.end8
+
+for.end8:                                         ; preds = %for.inc6
+  ret void
+}