Proper handling of diamond-like cases in if-conversion

[kparzysz]

Summary

If converter was somewhat careless about "diamond" cases, where there was no join block, or in other words, where the true/false blocks did not have analyzable branches. In such cases, it was possible for it to remove the (necessary) branches, resulting in a loss of entire basic blocks.

[kparzysz]

Hello?

[MatzeB]

I am not too familiar with the if conversion code, but reading it so far it looks to me like ValidDiamond is not supposed to handle case where there is not common join block. I would expect a branch ending in return to hit the ValidSimple() case.

My understanding if the code is that return instructions are not analyzable and the code sequence at the beginning of ValidDiamond() should reject cases where both blocks do not end in analyzable branches (the 4th if should reject them I think).

if (!TT && blockAlwaysFallThrough(TrueBBI))
  TT = getNextBlock(TrueBBI.BB);
if (!FT && blockAlwaysFallThrough(FalseBBI))
  FT = getNextBlock(FalseBBI.BB);
if (TT != FT)
  return false;
if (!TT && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable))
  return false;
if  (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
  return false;

Can you reproduce the issue with other backends? I am not convinced yet that the problem is not AnalyzeBranch() reporting unexpected values.

[kparzysz]

The 4th statement will return if TT is null (actually both TT and FT), and both branches are analyzable. You are right---returns are not analyzable, and this condition is not triggered. The AnalyzeBranch from Hexagon does not differ in that respect from that from other targets.

I have tried other backends, but I couldn't get just the right optimizations to kick in. Both function calls need to be tail calls, and a jump table needs to be created. Moreover, the block with the jump table branch needs to be a target of a conditional branch that will be recognized as a diamond by the if converter. For other backends, the code never looked right enough to trigger this condition, but I don't think there is anything Hexagon-specific (except the testcase itself).

[MatzeB]

In D16156#330410, @kparzysz wrote:

The 4th statement will return if TT is null (actually both TT and FT), and both branches are analyzable. You are right---returns are not analyzable, and this condition is not triggered. The AnalyzeBranch from Hexagon does not differ in that respect from that from other targets.

Your patch description states that you fix diamond cases with no join block (doesn't sound like a diamond case to me, and I'm not convinced the code in ValidDiamond is supposed to handle that). Anyway if both TT and FT end in a return, then I would expect TT and FT to be nullptr at this point and as none of the two branches was analyzable we end in a return false

[MatzeB]

In D16156#330482, @MatzeB wrote:

In D16156#330410, @kparzysz wrote:

The 4th statement will return if TT is null (actually both TT and FT), and both branches are analyzable. You are right---returns are not analyzable, and this condition is not triggered. The AnalyzeBranch from Hexagon does not differ in that respect from that from other targets.

Your patch description states that you fix diamond cases with no join block (doesn't sound like a diamond case to me, and I'm not convinced the code in ValidDiamond is supposed to handle that). Anyway if both TT and FT end in a return, then I would expect TT and FT to be nullptr at this point and as none of the two branches was analyzable we end in a return false

Ignore this comment, you will indeed not hit this case. I still have to read the code some more to understand why ValidSimple() doesn't kick in here and whether ValidDiamond() is supposed to handle this case.

[kparzysz]

Yes, the "diamond" in this context is a misnomer as the diamond code tries to handle cases without a join block (which is obviously not an actual diamond). I think it used to only handle real diamonds and then was extended to handle more relaxed cases. The function names remain but they do more than what the names suggest.

[MatzeB]

LGTM, with nitpick addressed.

lib/CodeGen/IfConversion.cpp

1492–1493

I'd prefer an explicit MachineBasicBlock::iterator here instead of auto.

[kparzysz]

lib/CodeGen/IfConversion.cpp

1492–1493

Done.

lib/CodeGen/IfConversion.cpp

if (!TIB->isIdenticalTo(FIB))
       break;
     ++Dups1;
     ++TIB;
     ++FIB;
   }
 
   // Now, in preparation for counting duplicate instructions at the ends of the
   // blocks, move the end iterators up past any branch instructions.
-  while (TIE != TIB) {
-    --TIE;
-    if (!TIE->isBranch())
-      break;
-  }
-  while (FIE != FIB) {
-    --FIE;
-    if (!FIE->isBranch())
-      break;
+  // If both blocks are returning don't skip the branches, since they will
+  // likely be both identical return instructions. In such cases the return
+  // can be left unpredicated.
+  // Check for already containing all of the block.
+  if (TIB == TIE || FIB == FIE)
+    return true;
+  if (!TrueBBI.BB->succ_empty() || !FalseBBI.BB->succ_empty()) {
+    while (TIE != TIB && TIE->isBranch())
+      --TIE;
+    while (FIE != FIB && FIE->isBranch())
+      --FIE;
   }
 
   // If Dups1 includes all of a block, then don't count duplicate
   // instructions at the end of the blocks.
   if (TIB == TIE || FIB == FIE)
     return true;
 
   // Count duplicate instructions at the ends of the blocks.
bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
   for (MachineBasicBlock::const_iterator I = BBI1->BB->begin(), E = DI1; I != E;
        ++I) {
     SmallVector<std::pair<unsigned, const MachineOperand*>, 4> IgnoredClobbers;
     Redefs.stepForward(*I, IgnoredClobbers);
   }
   BBI.BB->splice(BBI.BB->end(), BBI1->BB, BBI1->BB->begin(), DI1);
   BBI2->BB->erase(BBI2->BB->begin(), DI2);
 
-  // Remove branch from 'true' block and remove duplicated instructions.
+  // Remove branch from the 'true' block, unless it was not analyzable.
+  // Non-analyzable branches need to be preserved, since in such cases,
+  // the CFG structure is not an actual diamond (the join block may not
+  // be present).
+  if (BBI1->IsBrAnalyzable)
     BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB);
+  // Remove duplicated instructions.
   DI1 = BBI1->BB->end();
   for (unsigned i = 0; i != NumDups2; ) {
     // NumDups2 only counted non-dbg_value instructions, so this won't
     // run off the head of the list.
     assert (DI1 != BBI1->BB->begin());
     --DI1;
     // skip dbg_value instructions
     if (!DI1->isDebugValue())
       ++i;
   }
   BBI1->BB->erase(DI1, BBI1->BB->end());
 
   // Kill flags in the true block for registers living into the false block
   // must be removed.
   RemoveKills(BBI1->BB->begin(), BBI1->BB->end(), DontKill, *TRI);
 
-  // Remove 'false' block branch and find the last instruction to predicate.
+  // Remove 'false' block branch (unless it was not analyzable), and find
+  // the last instruction to predicate.
+  if (BBI2->IsBrAnalyzable)
     BBI2->NonPredSize -= TII->RemoveBranch(*BBI2->BB);
   DI2 = BBI2->BB->end();
   while (NumDups2 != 0) {
     // NumDups2 only counted non-dbg_value instructions, so this won't
     // run off the head of the list.
     assert (DI2 != BBI2->BB->begin());
     --DI2;
     // skip dbg_value instructions
     if (!DI2->isDebugValue())
for (MachineBasicBlock::iterator FI = BBI2->BB->begin(); FI != DI2; ++FI) {
         }
       }
     }
   }
 
   // Predicate the 'true' block.
   PredicateBlock(*BBI1, BBI1->BB->end(), *Cond1, &RedefsByFalse);
 
+  // After predicating BBI1, if there is a predicated terminator in BBI1 and
+  // a non-predicated in BBI2, then we don't want to predicate the one from
+  // BBI2. The reason is that if we merged these blocks, we would end up with
+  // two predicated terminators in the same block.
+  if (!BBI2->BB->empty() && (DI2 == BBI2->BB->end())) {
+    auto BBI1T = BBI1->BB->getFirstTerminator();
+    auto BBI2T = BBI2->BB->getFirstTerminator();
+    if ((BBI1T != BBI1->BB->end()) && TII->isPredicated(BBI1T) &&
+       ((BBI2T != BBI2->BB->end()) && !TII->isPredicated(BBI2T)))
+      --DI2;
+  }
+
   // Predicate the 'false' block.
   PredicateBlock(*BBI2, DI2, *Cond2);
 
   // Merge the true block into the entry of the diamond.
   MergeBlocks(BBI, *BBI1, TailBB == nullptr);
   MergeBlocks(BBI, *BBI2, TailBB == nullptr);
 
   // If the if-converted block falls through or unconditionally branches into
   // the tail block, and the tail block does not have other predecessors, then
   // fold the tail block in as well. Otherwise, unless it falls through to the
   // tail, add a unconditional branch to it.
   if (TailBB) {
     BBInfo &TailBBI = BBAnalysis[TailBB->getNumber()];
     bool CanMergeTail = !TailBBI.HasFallThrough &&
       !TailBBI.BB->hasAddressTaken();
+    // The if-converted block can still have a predicated terminator
+    // (e.g. a predicated return). If that is the case, we cannot merge
+    // it with the tail block.
+    MachineBasicBlock::const_iterator TI = BBI.BB->getFirstTerminator();
+    if (TI != BBI.BB->end() && TII->isPredicated(TI))
+      CanMergeTail = false;
     // There may still be a fall-through edge from BBI1 or BBI2 to TailBB;
     // check if there are any other predecessors besides those.
     unsigned NumPreds = TailBB->pred_size();
     if (NumPreds > 1)
       CanMergeTail = false;
     else if (NumPreds == 1 && CanMergeTail) {
       MachineBasicBlock::pred_iterator PI = TailBB->pred_begin();
       if (*PI != BBI1->BB && *PI != BBI2->BB)

 /// This will leave FromBB as an empty block, so remove all of its
 /// successor edges except for the fall-through edge.  If AddEdges is true,
 /// i.e., when FromBBI's branch is being moved, add those successor edges to
 /// ToBBI.
 void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {
   assert(!FromBBI.BB->hasAddressTaken() &&
          "Removing a BB whose address is taken!");
 
-  ToBBI.BB->splice(ToBBI.BB->end(),
-                   FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end());
+  // In case FromBBI.BB contains terminators (e.g. return instruction),
+  // first move the non-terminator instructions, then the terminators.
+  MachineBasicBlock::iterator FromTI = FromBBI.BB->getFirstTerminator();
+  MachineBasicBlock::iterator ToTI = ToBBI.BB->getFirstTerminator();
+  ToBBI.BB->splice(ToTI, FromBBI.BB, FromBBI.BB->begin(), FromTI);
+
+  // If FromBB has non-predicated terminator we should copy it at the end.
+  if ((FromTI != FromBBI.BB->end()) && !TII->isPredicated(FromTI))
+    ToTI = ToBBI.BB->end();
+  ToBBI.BB->splice(ToTI, FromBBI.BB, FromTI, FromBBI.BB->end());
 
   // Force normalizing the successors' probabilities of ToBBI.BB to convert all
   // unknown probabilities into known ones.
   // FIXME: This usage is too tricky and in the future we would like to
   // eliminate all unknown probabilities in MBB.
   ToBBI.BB->normalizeSuccProbs();
 
   SmallVector<MachineBasicBlock *, 4> FromSuccs(FromBBI.BB->succ_begin(),

test/CodeGen/Hexagon/ifcvt-diamond-bad.ll

+; RUN: llc -march=hexagon -minimum-jump-tables=1 < %s
+; REQUIRES: asserts
+
+target datalayout = "e-m:e-p:32:32:32-i64:64:64-i32:32:32-i16:16:16-i1:8:8-f64:64:64-f32:32:32-v64:64:64-v32:32:32-a:0-n16:32"
+target triple = "hexagon"
+
+%struct.t0 = type { i8, [2 x i8] }
+%struct.t1 = type { i8, i8, [1900 x i8], %struct.t0 }
+
+@var = internal global [3 x %struct.t1] zeroinitializer, align 8
+declare void @foo() #2
+declare void @bar(i32, i32) #2
+
+; Function Attrs: nounwind
+define void @fred(i8 signext %a, i8 signext %b) #1 {
+entry:
+  %i = sext i8 %a to i32
+  %t = getelementptr inbounds [3 x %struct.t1], [3 x %struct.t1]* @var, i32 0, i32 %i, i32 3, i32 0
+  %0 = load i8, i8* %t, align 8
+  switch i8 %0, label %if.end14 [
+    i8 1, label %if.then
+    i8 0, label %do.body
+  ]
+
+if.then:                                          ; preds = %entry
+  %j = sext i8 %b to i32
+  %u = getelementptr inbounds [3 x %struct.t1], [3 x %struct.t1]* @var, i32 0, i32 %i, i32 3, i32 1, i32 %j
+  store i8 1, i8* %u, align 1
+  tail call void @foo() #0
+  br label %if.end14
+
+do.body:                                          ; preds = %entry
+  %conv11 = sext i8 %b to i32
+  tail call void @bar(i32 %i, i32 %conv11) #0
+  br label %if.end14
+
+if.end14:                                         ; preds = %entry, %do.body, %if.then
+  ret void
+}
+
+attributes #0 = { nounwind }
+attributes #1 = { nounwind "disable-tail-calls"="false" }
+attributes #2 = { "disable-tail-calls"="false" }