[IfConversion] Keep the CFG updated incrementally in IfConvertTriangle

[uabelho]

Summary

Instead of using RemoveExtraEdges (which uses analyzeBranch, which cannot
always be trusted) at the end to fixup the CFG we keep the CFG updated as
we go along and remove or add branches and merge blocks.

This way we won't have any problems if the involved MBBs contain
unanalyzable instructions.

This fixes PR32721.

In that case we had a triangle

EBB
| \
|  |
| TBB
|  /
FBB

where FBB didn't have any successors at all since it ended with an
unconditional return. Then TBB and FBB were be merged into EBB, but EBB
would still keep its successors, and the use of analyzeBranch and
CorrectExtraCFGEdges wouldn't help to remove them since the return
instruction is not analyzable (at least not on ARM).

[uabelho]

I have on purpose not attacked IfConvertSimple, IfConvertForkedDiamond
and IfConvertDiamond to keep the size of the patch down, and I haven't seen any
test case where they actually go wrong, but I think they suffer from similar
problems since they also use RemoveExtraEdges/analyzeBranch to fix the CFG at
the end.

If you think this patch changes IfConversion in the right direction then I think
it would be good idea to try to remove the other uses of RemoveExtraEdges as well
later.

[iteratee]

In D33037#750855, @uabelho wrote:

I have on purpose not attacked IfConvertSimple, IfConvertForkedDiamond
and IfConvertDiamond to keep the size of the patch down, and I haven't seen any
test case where they actually go wrong, but I think they suffer from similar
problems since they also use RemoveExtraEdges/analyzeBranch to fix the CFG at
the end.

IfConvertForkedDiamond only applies to analyzable branches, so it should be safe.
If you change the others, it would be good to change it as well for consistency.

I'll leave time for others to comment, but overall it looks fine to me.

[uabelho]

In D33037#751100, @iteratee wrote:

In D33037#750855, @uabelho wrote:

I have on purpose not attacked IfConvertSimple, IfConvertForkedDiamond
and IfConvertDiamond to keep the size of the patch down, and I haven't seen any
test case where they actually go wrong, but I think they suffer from similar
problems since they also use RemoveExtraEdges/analyzeBranch to fix the CFG at
the end.

IfConvertForkedDiamond only applies to analyzable branches, so it should be safe.

Possible. I haven't tried to provoke it to miscompile due to unanalyzable instructions.

If you change the others, it would be good to change it as well for consistency.

Yes I think so too.

In general I think we should try to avoid uses of analyzeBranch to fix things since it cannot be
trusted in all cases anyway. Doing optimizations based on its result is no problem but the use
in RemoveExtraEdges is problematic.

I'll leave time for others to comment, but overall it looks fine to me.

Thanks!

[uabelho]

Btw, without the fix we get the following result from IfConversion for the testcase:

body: |

bb.0:

bb.1:
  successors: %bb.2(0x40000000), %bb.1(0x00000000)

  BX_RET 14, 0

bb.2:

...

So bb.1 has both bb.2 and itself as successors, even if it only contains an unconditional return.

[MatzeB]

In D33037#751973, @uabelho wrote:

Btw, without the fix we get the following result from IfConversion for the testcase:

body: |

bb.0:

bb.1:
  successors: %bb.2(0x40000000), %bb.1(0x00000000)

  BX_RET 14, 0

bb.2:

...

So bb.1 has both bb.2 and itself as successors, even if it only contains an unconditional return.

This is indeed wrong (but hard to catch with the MachineVerifier so it probably went unnoticed).

I leave the patch review to @iteratee.

test/CodeGen/MIR/ARM/PR32721_ifcvt_triangle_unanalyzable.mir

6

FYI: The latest MIR parser can finally deduce the successor lists in most cases if you leave them out. It should work for this test.

[iteratee]

Feel free to send me patches that update the other parts of IfConversion

[uabelho]

Removed the "successors" lists in the test case as suggested by Matthias since
they are computed correctly anyway by the MIr pasrser.

[uabelho]

test/CodeGen/MIR/ARM/PR32721_ifcvt_triangle_unanalyzable.mir

6

Thanks!

[uabelho]

In D33037#752454, @iteratee wrote:

Feel free to send me patches that update the other parts of IfConversion

Thanks!

I'll try to find the time to do that!

lib/CodeGen/IfConversion.cpp

bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
   if (HasEarlyExit) {
     // Get probabilities before modifying CvtMBB and BBI.BB.
     CvtNext = MBPI->getEdgeProbability(&CvtMBB, &NextMBB);
     CvtFalse = MBPI->getEdgeProbability(&CvtMBB, CvtBBI->FalseBB);
     BBNext = MBPI->getEdgeProbability(BBI.BB, &NextMBB);
     BBCvt = MBPI->getEdgeProbability(BBI.BB, &CvtMBB);
   }
 
+  // To be able to insert code freely at the end of BBI we sometimes remove
+  // the branch from BBI to NextMBB temporarily. Remember if this happened.
+  bool RemovedBranchToNextMBB = false;
   if (CvtMBB.pred_size() > 1) {
     BBI.NonPredSize -= TII->removeBranch(*BBI.BB);
     // Copy instructions in the true block, predicate them, and add them to
     // the entry block.
     CopyAndPredicateBlock(BBI, *CvtBBI, Cond, true);
 
-    // RemoveExtraEdges won't work if the block has an unanalyzable branch, so
-    // explicitly remove CvtBBI as a successor.
+    // Keep the CFG updated.
     BBI.BB->removeSuccessor(&CvtMBB, true);
   } else {
     // Predicate the 'true' block after removing its branch.
     CvtBBI->NonPredSize -= TII->removeBranch(CvtMBB);
     PredicateBlock(*CvtBBI, CvtMBB.end(), Cond);
 
-    // Now merge the entry of the triangle with the true block.
+    // Remove the branch from the entry of the triangle to NextBB to be able to
+    // do the merge below. Keep the CFG updated, but remember we removed the
+    // branch since we do want to execute NextMBB, either by introducing a
+    // branch to it again, or merging it into the entry block.
+    // How it's handled is decided further down.
     BBI.NonPredSize -= TII->removeBranch(*BBI.BB);
+    BBI.BB->removeSuccessor(&NextMBB, true);
+    RemovedBranchToNextMBB = true;
+
+    // Now merge the entry of the triangle with the true block.
     MergeBlocks(BBI, *CvtBBI, false);
   }
 
   // If 'true' block has a 'false' successor, add an exit branch to it.
   if (HasEarlyExit) {
     SmallVector<MachineOperand, 4> RevCond(CvtBBI->BrCond.begin(),
                                            CvtBBI->BrCond.end());
     if (TII->reverseBranchCondition(RevCond))
bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
   bool FalseBBDead = false;
   bool IterIfcvt = true;
   bool isFallThrough = canFallThroughTo(*BBI.BB, NextMBB);
   if (!isFallThrough) {
     // Only merge them if the true block does not fallthrough to the false
     // block. By not merging them, we make it possible to iteratively
     // ifcvt the blocks.
     if (!HasEarlyExit &&
-        NextMBB.pred_size() == 1 && !NextBBI->HasFallThrough &&
+        // We might have removed BBI from NextMBB's predecessor list above but
+        // we want it to be there, so consider that too.
+        (NextMBB.pred_size() == (RemovedBranchToNextMBB ? 0 : 1)) &&
+        !NextBBI->HasFallThrough &&
         !NextMBB.hasAddressTaken()) {
+      // We will merge NextBBI into BBI, and thus remove the current
+      // fallthrough from BBI into CvtBBI.
+      BBI.BB->removeSuccessor(&CvtMBB, true);
       MergeBlocks(BBI, *NextBBI);
       FalseBBDead = true;
     } else {
       InsertUncondBranch(*BBI.BB, NextMBB, TII);
+      BBI.BB->addSuccessor(&NextMBB);
       BBI.HasFallThrough = false;
     }
     // Mixed predicated and unpredicated code. This cannot be iteratively
     // predicated.
     IterIfcvt = false;
   }
 
-  RemoveExtraEdges(BBI);
-
   // Update block info. BB can be iteratively if-converted.
   if (!IterIfcvt)
     BBI.IsDone = true;
   InvalidatePreds(*BBI.BB);
   CvtBBI->IsDone = true;
   if (FalseBBDead)
     NextBBI->IsDone = true;
 

test/CodeGen/MIR/ARM/PR32721_ifcvt_triangle_unanalyzable.mir

+# RUN: llc -mtriple=arm-apple-ios -run-pass=if-converter %s -o - | FileCheck %s
+---
+name:            foo
+body:             |
+  bb.0:
+    successors: %bb.2
+
+    B %bb.2
+
+  bb.1:
+
+    BX_RET 14, 0
+
+  bb.2:
+    successors: %bb.3, %bb.1
+
+    Bcc %bb.1, 1, %cpsr
+
+  bb.3:
+    successors: %bb.1
+
+    B %bb.1
+
+...
+
+# We should get a single block containing the BX_RET, with no successors at all
+
+# CHECK:      body:
+# CHECK-NEXT:   bb.0:
+# CHECK-NEXT:     BX_RET
+