[FlattenCFG] Fix `MergeIfRegion` in case then-path is empty

[ekatz]

Summary

In case the then-path of an if-region is empty, then merging with the else-path should be handled with the inverse of the condition (leading to that path).

Fix PR37662

[ekatz]

Ping

[ekatz]

Ping

[kuhar]

I followed the new tests and the patch seems fine to me, but I'd rather someone else took a look too.

llvm/lib/Transforms/Utils/FlattenCFG.cpp

486–497

Is there a better name for Invert2? I think until this point it's difficult to tell what it's actually for.

llvm/test/Transforms/Util/flattencfg.ll

32

Good catch!

[ekatz]

llvm/lib/Transforms/Utils/FlattenCFG.cpp

486–497

Sure, I'll find a better name.

[ekatz]

Rename Invert2 variable to InvertCond2.
Hope it makes more sense.

[kuhar]

In D78881#2031146, @ekatz wrote:

Rename Invert2 variable to InvertCond2.
Hope it makes more sense.

Thanks!

[ekatz]

Ping

[sameerds]

I am NOT familiar with this transformation. But I believe that the patch is well-formed, and I was able to follow the logic. The tests also demonstrate that it works as intended. LGTM.

llvm/lib/Transforms/Utils/FlattenCFG.cpp

class FlattenCFGOpt {
   bool FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder);
 
   /// If \param BB is the merge block of an if-region, attempt to merge
   /// the if-region with an adjacent if-region upstream if two if-regions
   /// contain identical instructions.
   bool MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder);
 
   /// Compare a pair of blocks: \p Block1 and \p Block2, which
-  /// are from two if-regions whose entry blocks are \p Head1 and \p
-  /// Head2.  \returns true if \p Block1 and \p Block2 contain identical
+  /// are from two if-regions, where \p Head2 is the entry block of the 2nd
+  /// if-region.  \returns true if \p Block1 and \p Block2 contain identical
   /// instructions, and have no memory reference alias with \p Head2.
   /// This is used as a legality check for merging if-regions.
-  bool CompareIfRegionBlock(BasicBlock *Head1, BasicBlock *Head2,
-                            BasicBlock *Block1, BasicBlock *Block2);
+  bool CompareIfRegionBlock(BasicBlock *Block1, BasicBlock *Block2,
+                            BasicBlock *Head2);
 
 public:
   FlattenCFGOpt(AliasAnalysis *AA) : AA(AA) {}
 
   bool run(BasicBlock *BB);
 };
 
 } // end anonymous namespace
do {
     // make CB unreachable and let downstream to delete the block.
     new UnreachableInst(CB->getContext(), CB);
   } while (Iteration);
 
   LLVM_DEBUG(dbgs() << "Use parallel and/or in:\n" << *FirstCondBlock);
   return true;
 }
 
-/// Compare blocks from two if-regions, where \param Head1 is the entry of the
-/// 1st if-region. \param Head2 is the entry of the 2nd if-region. \param
-/// Block1 is a block in the 1st if-region to compare. \param Block2 is a block
-//  in the 2nd if-region to compare.  \returns true if \param Block1 and \param
-/// Block2 have identical instructions and do not have memory reference alias
-/// with \param Head2.
-bool FlattenCFGOpt::CompareIfRegionBlock(BasicBlock *Head1, BasicBlock *Head2,
-                                         BasicBlock *Block1,
-                                         BasicBlock *Block2) {
+/// Compare blocks from two if-regions, where \param Head2 is the entry of the
+/// 2nd if-region. \param Block1 is a block in the 1st if-region to compare.
+/// \param Block2 is a block in the 2nd if-region to compare.  \returns true if
+/// \param Block1 and \param Block2 have identical instructions and do not have
+/// memory reference alias with \param Head2.
+bool FlattenCFGOpt::CompareIfRegionBlock(BasicBlock *Block1, BasicBlock *Block2,
+                                         BasicBlock *Head2) {
   Instruction *PTI2 = Head2->getTerminator();
   Instruction *PBI2 = &Head2->front();
 
-  bool eq1 = (Block1 == Head1);
-  bool eq2 = (Block2 == Head2);
-  if (eq1 || eq2) {
-    // An empty then-path or else-path.
-    return (eq1 == eq2);
-  }
-
   // Check whether instructions in Block1 and Block2 are identical
   // and do not alias with instructions in Head2.
   BasicBlock::iterator iter1 = Block1->begin();
   BasicBlock::iterator end1 = Block1->getTerminator()->getIterator();
   BasicBlock::iterator iter2 = Block2->begin();
   BasicBlock::iterator end2 = Block2->getTerminator()->getIterator();
 
   while (true) {

 /// if (a)
 ///   statement;
 /// if (b)
 ///   statement;
 ///
 /// To:
 /// if (a || b)
 ///   statement;
+///
+///
+/// And from:
+/// if (a)
+///   ;
+/// else
+///   statement;
+/// if (b)
+///   ;
+/// else
+///   statement;
+///
+/// To:
+/// if (a && b)
+///   ;
+/// else
+///   statement;
+///
+/// We always take the form of the first if-region. This means that if the
+/// statement in the first if-region, is in the "then-path", while in the second
+/// if-region it is in the "else-path", then we convert the second to the first
+/// form, by inverting the condition and the branch successors. The same
+/// approach goes for the opposite case.
 bool FlattenCFGOpt::MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder) {
   BasicBlock *IfTrue2, *IfFalse2;
   Value *IfCond2 = GetIfCondition(BB, IfTrue2, IfFalse2);
   Instruction *CInst2 = dyn_cast_or_null<Instruction>(IfCond2);
   if (!CInst2)
     return false;
 
   BasicBlock *SecondEntryBlock = CInst2->getParent();
   if (SecondEntryBlock->hasAddressTaken())
     return false;
 
   BasicBlock *IfTrue1, *IfFalse1;
   Value *IfCond1 = GetIfCondition(SecondEntryBlock, IfTrue1, IfFalse1);
   Instruction *CInst1 = dyn_cast_or_null<Instruction>(IfCond1);
   if (!CInst1)
     return false;
 
   BasicBlock *FirstEntryBlock = CInst1->getParent();
 
   // Either then-path or else-path should be empty.
-  if ((IfTrue1 != FirstEntryBlock) && (IfFalse1 != FirstEntryBlock))
-    return false;
-  if ((IfTrue2 != SecondEntryBlock) && (IfFalse2 != SecondEntryBlock))
+  bool InvertCond2 = false;
+  BinaryOperator::BinaryOps CombineOp;
+  if (IfFalse1 == FirstEntryBlock) {
+    // The else-path is empty, so we must use "or" operation to combine the
+    // conditions.
+    CombineOp = BinaryOperator::Or;
+    if (IfFalse2 != SecondEntryBlock) {
+      if (IfTrue2 != SecondEntryBlock)
         return false;
 
-  Instruction *PTI2 = SecondEntryBlock->getTerminator();
-  Instruction *PBI2 = &SecondEntryBlock->front();
+      InvertCond2 = true;
+      std::swap(IfTrue2, IfFalse2);
+    }
 
-  if (!CompareIfRegionBlock(FirstEntryBlock, SecondEntryBlock, IfTrue1,
-                            IfTrue2))
+    if (!CompareIfRegionBlock(IfTrue1, IfTrue2, SecondEntryBlock))
+      return false;
+  } else if (IfTrue1 == FirstEntryBlock) {
+    // The then-path is empty, so we must use "and" operation to combine the
+    // conditions.
+    CombineOp = BinaryOperator::And;
+    if (IfTrue2 != SecondEntryBlock) {
+      if (IfFalse2 != SecondEntryBlock)
         return false;
 
-  if (!CompareIfRegionBlock(FirstEntryBlock, SecondEntryBlock, IfFalse1,
-                            IfFalse2))
+      InvertCond2 = true;
+      std::swap(IfTrue2, IfFalse2);
+    }
+
+    if (!CompareIfRegionBlock(IfFalse1, IfFalse2, SecondEntryBlock))
+      return false;
+  } else
     return false;
 
+  Instruction *PTI2 = SecondEntryBlock->getTerminator();
+  Instruction *PBI2 = &SecondEntryBlock->front();
+
   // Check whether \param SecondEntryBlock has side-effect and is safe to
   // speculate.
   for (BasicBlock::iterator BI(PBI2), BE(PTI2); BI != BE; ++BI) {
     Instruction *CI = &*BI;
     if (isa<PHINode>(CI) || CI->mayHaveSideEffects() ||
         !isSafeToSpeculativelyExecute(CI))
       return false;
   }
 
   // Merge \param SecondEntryBlock into \param FirstEntryBlock.
   FirstEntryBlock->getInstList().pop_back();
   FirstEntryBlock->getInstList()
       .splice(FirstEntryBlock->end(), SecondEntryBlock->getInstList());
   BranchInst *PBI = cast<BranchInst>(FirstEntryBlock->getTerminator());
-  Value *CC = PBI->getCondition();
+  assert(PBI->getCondition() == IfCond2);
   BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
   BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
   Builder.SetInsertPoint(PBI);
-  Value *NC = Builder.CreateOr(CInst1, CC);
-  PBI->replaceUsesOfWith(CC, NC);
+  if (InvertCond2) {
+    // If this is a "cmp" instruction, only used for branching (and nowhere
+    // else), then we can simply invert the predicate.
+    auto Cmp2 = dyn_cast<CmpInst>(CInst2);
+    if (Cmp2 && Cmp2->hasOneUse())
+      Cmp2->setPredicate(Cmp2->getInversePredicate());
+    else
+      CInst2 = cast<Instruction>(Builder.CreateNot(CInst2));
+    PBI->swapSuccessors();
+  }
+  Value *NC = Builder.CreateBinOp(CombineOp, CInst1, CInst2);
+  PBI->replaceUsesOfWith(IfCond2, NC);
   Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt);
 
   // Handle PHI node to replace its predecessors to FirstEntryBlock.
   for (BasicBlock *Succ : successors(PBI)) {
     for (PHINode &Phi : Succ->phis()) {
       for (unsigned i = 0, e = Phi.getNumIncomingValues(); i != e; ++i) {
         if (Phi.getIncomingBlock(i) == SecondEntryBlock)
           Phi.setIncomingBlock(i, FirstEntryBlock);

llvm/test/Transforms/Util/flattencfg.ll

 exit:                               ; preds = %entry, %b0, %b1
   ret void
 }
 
 ; CHECK-LABEL: @test_not_crash2
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    %0 = fcmp ult float %a
 ; CHECK-NEXT:    %1 = fcmp ult float %b
-; CHECK-NEXT:    [[COND:%[a-z0-9]+]] = or i1 %0, %1
+; CHECK-NEXT:    [[COND:%[a-z0-9]+]] = and i1 %0, %1
 ; CHECK-NEXT:    br i1 [[COND]], label %bb4, label %bb3
 ; CHECK:       bb3:
 ; CHECK-NEXT:    br label %bb4
 ; CHECK:       bb4:
 ; CHECK-NEXT:    ret void
 define void @test_not_crash2(float %a, float %b) #0 {
 entry:
   %0 = fcmp ult float %a, 1.000000e+00

 
 bb2:                                              ; preds = %bb1
   br label %bb3
 
 bb3:                                              ; preds = %bb2, %bb1
   %check_badref = phi i32 [ 17, %bb1 ], [ 11, %bb2 ]
   ret void
 }
+
+
+@g = global i32 0, align 4
+
+; CHECK-LABEL: @test_then
+; CHECK-NEXT:  entry.x:
+; CHECK-NEXT:    %cmp.x = icmp ne i32 %x, 0
+; CHECK-NEXT:    %cmp.y = icmp ne i32 %y, 0
+; CHECK-NEXT:    [[COND:%[a-z0-9]+]] = or i1 %cmp.x, %cmp.y
+; CHECK-NEXT:    br i1 [[COND]], label %if.then.y, label %exit
+; CHECK:       if.then.y:
+; CHECK-NEXT:    store i32 %z, i32* @g, align 4
+; CHECK-NEXT:    br label %exit
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+define void @test_then(i32 %x, i32 %y, i32 %z) {
+entry.x:
+  %cmp.x = icmp ne i32 %x, 0
+  br i1 %cmp.x, label %if.then.x, label %entry.y
+
+if.then.x:
+  store i32 %z, i32* @g, align 4
+  br label %entry.y
+
+entry.y:
+  %cmp.y = icmp ne i32 %y, 0
+  br i1 %cmp.y, label %if.then.y, label %exit
+
+if.then.y:
+  store i32 %z, i32* @g, align 4
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test_else
+; CHECK-NEXT:  entry.x:
+; CHECK-NEXT:    %cmp.x = icmp eq i32 %x, 0
+; CHECK-NEXT:    %cmp.y = icmp eq i32 %y, 0
+; CHECK-NEXT:    [[COND:%[a-z0-9]+]] = and i1 %cmp.x, %cmp.y
+; CHECK-NEXT:    br i1 [[COND]], label %exit, label %if.else.y
+; CHECK:       if.else.y:
+; CHECK-NEXT:    store i32 %z, i32* @g, align 4
+; CHECK-NEXT:    br label %exit
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+define void @test_else(i32 %x, i32 %y, i32 %z) {
+entry.x:
+  %cmp.x = icmp eq i32 %x, 0
+  br i1 %cmp.x, label %entry.y, label %if.else.x
+
+if.else.x:
+  store i32 %z, i32* @g, align 4
+  br label %entry.y
+
+entry.y:
+  %cmp.y = icmp eq i32 %y, 0
+  br i1 %cmp.y, label %exit, label %if.else.y
+
+if.else.y:
+  store i32 %z, i32* @g, align 4
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test_combine_and
+; CHECK-NEXT:  entry.x:
+; CHECK-NEXT:    %cmp.x = icmp eq i32 %x, 0
+; CHECK-NEXT:    %cmp.y = icmp eq i32 %y, 0
+; CHECK-NEXT:    [[COND:%[a-z0-9]+]] = and i1 %cmp.x, %cmp.y
+; CHECK-NEXT:    br i1 [[COND]], label %exit, label %if.then.y
+; CHECK:       if.then.y:
+; CHECK-NEXT:    store i32 %z, i32* @g, align 4
+; CHECK-NEXT:    br label %exit
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+define void @test_combine_and(i32 %x, i32 %y, i32 %z) {
+entry.x:
+  %cmp.x = icmp eq i32 %x, 0
+  br i1 %cmp.x, label %entry.y, label %if.else.x
+
+if.else.x:
+  store i32 %z, i32* @g, align 4
+  br label %entry.y
+
+entry.y:
+  %cmp.y = icmp ne i32 %y, 0
+  br i1 %cmp.y, label %if.then.y, label %exit
+
+if.then.y:
+  store i32 %z, i32* @g, align 4
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test_combine_or
+; CHECK-NEXT:  entry.x:
+; CHECK-NEXT:    %cmp.x = icmp ne i32 %x, 0
+; CHECK-NEXT:    %cmp.y = icmp ne i32 %y, 0
+; CHECK-NEXT:    [[COND:%[a-z0-9]+]] = or i1 %cmp.x, %cmp.y
+; CHECK-NEXT:    br i1 [[COND]], label %if.else.y, label %exit
+; CHECK:       if.else.y:
+; CHECK-NEXT:    store i32 %z, i32* @g, align 4
+; CHECK-NEXT:    br label %exit
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+define void @test_combine_or(i32 %x, i32 %y, i32 %z) {
+entry.x:
+  %cmp.x = icmp ne i32 %x, 0
+  br i1 %cmp.x, label %if.then.x, label %entry.y
+
+if.then.x:
+  store i32 %z, i32* @g, align 4
+  br label %entry.y
+
+entry.y:
+  %cmp.y = icmp eq i32 %y, 0
+  br i1 %cmp.y, label %exit, label %if.else.y
+
+if.else.y:
+  store i32 %z, i32* @g, align 4
+  br label %exit
+
+exit:
+  ret void
+}