Fix FlattenCFG to invert test when different index is encountered, and add one more operator to invert.

[jsjodin]

Summary

This patch improves FlattenCFG so that it will invert a branch when indices do not match so that the transform can be applied in more cases. One more operator was added to do branch niversion on asl well. The old way which the branch inversion was used could actually prevent branch merging in some cases.

[jsjodin]

Added check in branch inversion to break if we encounter a block without a single predecessor.

[hfinkel]

lib/Transforms/Utils/FlattenCFG.cpp

202

I think that I'm missing something here: We currently might perform this change when CIdx == Idx, and with this patch, we only ever do it when CIdx != Idx. Don't you want to do it in both cases?

[jsjodin]

lib/Transforms/Utils/FlattenCFG.cpp

202

I'm not sure why branch inversion should done when CIdx == Idx. It shouldn't matter which block jumps into the other from the last CondBlock, and if branch inversion is done, then the indices will no longer be the same and the optimization does not apply anymore.

[jvesely]

sorry for the really long delay. I don't know enough about this code to review this patch (and won't have time to study it in the near future). You want Tom or Matt to have a look.

[arsenm]

Is this still necessary?

[arsenm]

Is this still needed?

[jsjodin]

I don't know if this is needed anymore. We could probably abandon it if it does not seem useful.

[arsenm]

Can you rebase and see if this still makes a difference? I think CodeGenPrepare may also do this in some cases now

[arsenm]

Is this still relevant?

[jsjodin]

Unlikely to be needed anymore.

lib/Transforms/Utils/FlattenCFG.cpp

for (SmallPtrSetIterator<BasicBlock *> PI = Preds.begin(), PE = Preds.end();
     // for all of its predecessors.
     BasicBlock *PS1 = PBI->getSuccessor(0);
     BasicBlock *PS2 = PBI->getSuccessor(1);
     BasicBlock *PS = (PS1 == BB) ? PS2 : PS1;
     int CIdx = (PS1 == BB) ? 0 : 1;
 
     if (Idx == -1)
       Idx = CIdx;
-    else if (CIdx != Idx)
-      return false;
+    else if (CIdx != Idx) {
+      bool EverChanged = false;
+      if (FirstCondBlock && LastCondBlock) {
+        // Do branch inversion.
+        BasicBlock *CurrBlock = LastCondBlock;
+
+        for (; CurrBlock != FirstCondBlock;
+             CurrBlock = CurrBlock->getSinglePredecessor()) {
+          if (!CurrBlock)
+            break;
+          BranchInst *BI = dyn_cast<BranchInst>(CurrBlock->getTerminator());
+          CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
+          if (!CI)
+            continue;
+
+          CmpInst::Predicate Predicate = CI->getPredicate();
+          // Canonicalize icmp_ne -> icmp_eq, fcmp_one -> fcmp_oeq
+          if ((Predicate == CmpInst::ICMP_NE) ||
+              (Predicate == CmpInst::FCMP_ONE) ||
+              (Predicate == CmpInst::FCMP_UNE)) {
+            CI->setPredicate(ICmpInst::getInversePredicate(Predicate));
+            BI->swapSuccessors();
+            EverChanged = true;
+          }
+        }
+      }
+      return EverChanged;
+    }
 
     // PS is the successor which is not BB. Check successors to identify
     // the last conditional branch.
     if (Preds.count(PS) == 0) {
       // Case 2.
       LastCondBlock = Pred;
     } else {
       // Case 1
       BranchInst *BPS = dyn_cast<BranchInst>(PS->getTerminator());
       if (BPS && BPS->isUnconditional()) {
         // Case 1: PS(BB3) should be an unconditional branch.
         LastCondBlock = Pred;
       }
     }
   }
 
   if (!FirstCondBlock || !LastCondBlock || (FirstCondBlock == LastCondBlock))
     return false;
 
   TerminatorInst *TBB = LastCondBlock->getTerminator();
   BasicBlock *PS1 = TBB->getSuccessor(0);
   BasicBlock *PS2 = TBB->getSuccessor(1);
   BranchInst *PBI1 = dyn_cast<BranchInst>(PS1->getTerminator());
-  BranchInst *PBI2 = dyn_cast<BranchInst>(PS2->getTerminator());
-
-  // If PS1 does not jump into PS2, but PS2 jumps into PS1,
-  // attempt branch inversion.
-  if (!PBI1 || !PBI1->isUnconditional() ||
-      (PS1->getTerminator()->getSuccessor(0) != PS2)) {
-    // Check whether PS2 jumps into PS1.
-    if (!PBI2 || !PBI2->isUnconditional() ||
-        (PS2->getTerminator()->getSuccessor(0) != PS1))
-      return false;
-
-    // Do branch inversion.
-    BasicBlock *CurrBlock = LastCondBlock;
-    bool EverChanged = false;
-    for (;CurrBlock != FirstCondBlock;
-          CurrBlock = CurrBlock->getSinglePredecessor()) {
-      BranchInst *BI = dyn_cast<BranchInst>(CurrBlock->getTerminator());
-      CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
-      if (!CI)
-        continue;
-
-      CmpInst::Predicate Predicate = CI->getPredicate();
-      // Canonicalize icmp_ne -> icmp_eq, fcmp_one -> fcmp_oeq
-      if ((Predicate == CmpInst::ICMP_NE) || (Predicate == CmpInst::FCMP_ONE)) {
-        CI->setPredicate(ICmpInst::getInversePredicate(Predicate));
-        BI->swapSuccessors();
-        EverChanged = true;
-      }
-    }
-    return EverChanged;
-  }
 
   // PS1 must have a conditional branch.
   if (!PBI1 || !PBI1->isUnconditional())
     return false;
 
   // PS2 should not contain PHI node.
   PHI = dyn_cast<PHINode>(PS2->begin());
   if (PHI)

test/Transforms/Util/flattencfg.ll

b0:                                ; preds = %entry
   br i1 %cond1, label %exit, label %b1
 
 b1:                                       ; preds = %entry, %b0
   br label %exit
 
 exit:                               ; preds = %entry, %b0, %b1
   ret void
 }
+
+; CHECK: and
+define void @test_fold_and(i32 %in_a) #0 {
+entry:
+  %cmp0 = icmp eq i32 %in_a, -1
+  br i1 %cmp0, label %b0, label %exit
+
+b0:                                ; preds = %entry
+  %cmp1 = icmp eq i32 %in_a, 0
+  br i1 %cmp1, label %b1, label %exit
+
+b1:                                       ; preds = %entry, %b0
+  br label %exit
+
+exit:                               ; preds = %entry, %b0, %b1
+  ret void
+}
+
+; CHECK: and
+define void @test_fold_and_reverse(i32 %in_a) #0 {
+entry:
+  %cmp0 = icmp eq i32 %in_a, -1
+  br i1 %cmp0, label %b0, label %exit
+
+b0:                                ; preds = %entry
+  %cmp1 = icmp ne i32 %in_a, 0
+  br i1 %cmp1, label %exit, label %b1
+
+b1:                                       ; preds = %entry, %b0
+  br label %exit
+
+exit:                               ; preds = %entry, %b0, %b1
+  ret void
+}
+
+; CHECK: or
+define void @test_fold_or(i32 %in_a) #0 {
+entry:
+  %cmp0 = icmp eq i32 %in_a, -1
+  br i1 %cmp0, label %b1, label %b0
+
+b0:                                ; preds = %entry
+  %cmp1 = icmp eq i32 %in_a, 0
+  br i1 %cmp1, label %b1, label %exit
+
+b1:                                       ; preds = %entry, %b0
+  br label %exit
+
+exit:                               ; preds = %entry, %b0, %b1
+  ret void
+}
+
+; CHECK: or
+define void @test_fold_or_reverse(i32 %in_a) #0 {
+entry:
+  %cmp0 = icmp eq i32 %in_a, -1
+  br i1 %cmp0, label %b1, label %b0
+
+b0:                                ; preds = %entry
+  %cmp1 = icmp ne i32 %in_a, 0
+  br i1 %cmp1, label %exit, label %b1
+
+b1:                                       ; preds = %entry, %b0
+  br label %exit
+
+exit:                               ; preds = %entry, %b0, %b1
+  ret void
+}