[SimplifyCFG] Hoist common if-then-else code if used by two-entry PHI nodes

[labrinea]

Summary

The current algorithm for hoisting if-then-else code is limited to only match identical instructions with the exact same ordering. The reason is to keep the complexity low. There are cases where the InstCombiner cannot sink the common code and we end up with trivial PHIs which cannot be eliminated. This prevents if-conversion. SimplifyCFG is not the best place for this kind of transformation but it is a short-term solution until GVN-Hoist gets fixed/enabled.

[• dberlin]

I'm confused ... Is there a reason to not just go fix/enable gvn-hoist?

[labrinea]

My argument would be that this change is fairly small. To be honest I don't know what is the status of GVN-Hoist. If it is in a good shape, then enabling it is the best way to go. If there are a few bugs to fix I am happy to help, but if it is far from being in a good shape then a workaround like this should be acceptable.

[• dberlin]

Okay, i'll bite

In D48122#1131183, @labrinea wrote:

My argument would be that this change is fairly small.

It's also not like SimplifyCFG started out large.
Like all things, it does so much because of small changes accumulating without a real plan :)

To be honest I don't know what is the status of GVN-Hoist.

I"m only aware of a single bug ATM.

If it is in a good shape, then enabling it is the best way to go. If there are a few bugs to fix I am happy to help, but if it is far from being in a good shape then a workaround like this should be acceptable.

At least to me, the shape is not so important as what the plan is.
If you are saying things like "this should go away when gvnhoist is fixed/enabled", that should really be part of a plan, and we should have that plan first. Based on the timelines in that plan, we should be deciding whether or not we want a short term workaround.

It doesn't have to be super formal or super-correct, but we should at least understand what the state and what we want it to be before we decide whether to add workarounds.

[efriedma]

GVNHoist is generally pretty stable; my team has used it to build a lot of code without any issues. There are a few known bugs (https://bugs.llvm.org/show_bug.cgi?id=37791, https://bugs.llvm.org/show_bug.cgi?id=36635, https://bugs.llvm.org/show_bug.cgi?id=37445 ) that we probably need to fix before turning it on by default.

lib/Transforms/Utils/SimplifyCFG.cpp

for (const PHINode &PN : Succ->phis()) {
       }
     }
   }
   return true;
 }
 
 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I);
 
+// Given a conditional branch BI that goes to BB1 and BB2, which are the
+// basic blocks of the instructions I1 and I2 respectively, hoist I1 and
+// I2 up into the branch block. The caller of this function guarantees
+// that I1->isIdenticalToWhenDefined(I2) and that BI's block dominates
+// BB1 and BB2.
+static void HoistThenElseInstructionToIf(BranchInst *BI, Instruction *I1,
+                                         Instruction *I2) {
+  // Move I1 to right before the branch, then replace all uses of I2.
+  BI->getParent()->getInstList().splice(BI->getIterator(),
+                                        I1->getParent()->getInstList(), I1);
+  if (!I2->use_empty())
+    I2->replaceAllUsesWith(I1);
+  I1->andIRFlags(I2);
+  unsigned KnownIDs[] = {LLVMContext::MD_tbaa,
+                         LLVMContext::MD_range,
+                         LLVMContext::MD_fpmath,
+                         LLVMContext::MD_invariant_load,
+                         LLVMContext::MD_nonnull,
+                         LLVMContext::MD_invariant_group,
+                         LLVMContext::MD_align,
+                         LLVMContext::MD_dereferenceable,
+                         LLVMContext::MD_dereferenceable_or_null,
+                         LLVMContext::MD_mem_parallel_loop_access};
+  combineMetadata(I1, I2, KnownIDs);
+
+  // I1 and I2 are being combined into a single instruction. Its debug
+  // location is the merged locations of the original instructions.
+  I1->applyMergedLocation(I1->getDebugLoc(), I2->getDebugLoc());
+
+  I2->eraseFromParent();
+}
+
+// Scan the basic block BB of an instruction I, which is candidate for hoisting,
+// to make sure there are no instructions before I that may write to memory.
+// First check that the instruction I itself doesn't write to memory.
+static bool isSafeToHoistInstruction(BasicBlock *BB, Instruction *I) {
+  if (I->mayWriteToMemory())
+    return false;
+
+  for (BasicBlock::iterator IT = BB->begin(), ITE = BasicBlock::iterator(I);
+       IT != ITE; ++IT)
+    if (IT->mayWriteToMemory())
+      return false;
+
+  return true;
+}
+
 /// Given a conditional branch that goes to BB1 and BB2, hoist any common code
 /// in the two blocks up into the branch block. The caller of this function
 /// guarantees that BI's block dominates BB1 and BB2.
 static bool HoistThenElseCodeToIf(BranchInst *BI,
                                   const TargetTransformInfo &TTI) {
   // This does very trivial matching, with limited scanning, to find identical
   // instructions in the two blocks.  In particular, we don't want to get into
   // O(M*N) situations here where M and N are the sizes of BB1 and BB2.  As
   // such, we currently just scan for obviously identical instructions in an
   // identical order.
   BasicBlock *BB1 = BI->getSuccessor(0); // The true destination.
   BasicBlock *BB2 = BI->getSuccessor(1); // The false destination
 
+  bool Changed = false;
+
+  // Before we start scanning the two side blocks, we first identify if
+  // there's a diamond structure. We try to hoist common instructions
+  // from the side blocks to the entry if they are used by PHI-nodes of
+  // the exit block. This might enable PHI-node reduction which in turn
+  // could trigger further CFG simplifications like if-conversion.
+  //
+  // FIXME: GVNHoist could do it for us but it's currently disabled.
+  BasicBlock *IfEnd = BB1->getSingleSuccessor();
+  if (IfEnd && (IfEnd == BB2->getSingleSuccessor())) {
+
+    for (PHINode &PN : IfEnd->phis()) {
+      auto *I1 = dyn_cast<Instruction>(PN.getIncomingValueForBlock(BB1));
+      auto *I2 = dyn_cast<Instruction>(PN.getIncomingValueForBlock(BB2));
+
+      if (I1 && I1->getParent() == BB1 &&
+          I2 && I2->getParent() == BB2 &&
+          I1->isIdenticalToWhenDefined(I2)) {
+
+        // We don't preserve alias analysis therefore we have to make sure
+        // it's legal to hoist instructions.
+        //
+        // We scan all the instructions of BB1 up to I1 inclusive and bail
+        // if we find anything that might write to memory. Then we do the
+        // same for BB2.
+        if (!isSafeToHoistInstruction(BB1, I1) ||
+            !isSafeToHoistInstruction(BB2, I2))
+          continue;
+
+        HoistThenElseInstructionToIf(BI, I1, I2);
+        Changed = true;
+      }
+    }
+  }
+
   BasicBlock::iterator BB1_Itr = BB1->begin();
   BasicBlock::iterator BB2_Itr = BB2->begin();
 
   Instruction *I1 = &*BB1_Itr++, *I2 = &*BB2_Itr++;
   // Skip debug info if it is not identical.
   DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);
   DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2);
   if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
     while (isa<DbgInfoIntrinsic>(I1))
       I1 = &*BB1_Itr++;
     while (isa<DbgInfoIntrinsic>(I2))
       I2 = &*BB2_Itr++;
   }
   if (isa<PHINode>(I1) || !I1->isIdenticalToWhenDefined(I2) ||
       (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)))
     return false;
 
   BasicBlock *BIParent = BI->getParent();
 
-  bool Changed = false;
   do {
     // If we are hoisting the terminator instruction, don't move one (making a
     // broken BB), instead clone it, and remove BI.
     if (isa<TerminatorInst>(I1))
       goto HoistTerminator;
 
     // If we're going to hoist a call, make sure that the two instructions we're
     // commoning/hoisting are both marked with musttail, or neither of them is
if (isa<DbgInfoIntrinsic>(I1) || isa<DbgInfoIntrinsic>(I2)) {
                                      BB1->getInstList(), I1);
       BIParent->getInstList().splice(BI->getIterator(),
                                      BB2->getInstList(), I2);
       Changed = true;
     } else {
       // For a normal instruction, we just move one to right before the branch,
       // then replace all uses of the other with the first.  Finally, we remove
       // the now redundant second instruction.
-      BIParent->getInstList().splice(BI->getIterator(),
-                                     BB1->getInstList(), I1);
-      if (!I2->use_empty())
-        I2->replaceAllUsesWith(I1);
-      I1->andIRFlags(I2);
-      unsigned KnownIDs[] = {LLVMContext::MD_tbaa,
-                             LLVMContext::MD_range,
-                             LLVMContext::MD_fpmath,
-                             LLVMContext::MD_invariant_load,
-                             LLVMContext::MD_nonnull,
-                             LLVMContext::MD_invariant_group,
-                             LLVMContext::MD_align,
-                             LLVMContext::MD_dereferenceable,
-                             LLVMContext::MD_dereferenceable_or_null,
-                             LLVMContext::MD_mem_parallel_loop_access};
-      combineMetadata(I1, I2, KnownIDs);
-
-      // I1 and I2 are being combined into a single instruction.  Its debug
-      // location is the merged locations of the original instructions.
-      I1->applyMergedLocation(I1->getDebugLoc(), I2->getDebugLoc());
-
-      I2->eraseFromParent();
+      HoistThenElseInstructionToIf(BI, I1, I2);
       Changed = true;
     }
 
     I1 = &*BB1_Itr++;
     I2 = &*BB2_Itr++;
     // Skip debug info if it is not identical.
     DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);
     DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2);

test/Transforms/SimplifyCFG/HoistThenElseCodeToIf.ll

+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+
+define void @isLegalToHoist_x_z(i1 %cmp, i32* %x, i32* %y, i32* %z) {
+; CHECK-LABEL: @isLegalToHoist_x_z(
+; CHECK:     entry:
+; CHECK:       [[X:%.*]] = load i32, i32* %x, align 4
+; CHECK:       [[Z:%.*]] = load i32, i32* %z, align 4
+; CHECK:     if.then:
+; CHECK-NOT:   load i32, i32* %x, align 4
+; CHECK-NOT:   load i32, i32* %z, align 4
+; CHECK:     if.else:
+; CHECK-NOT:   load i32, i32* %x, align 4
+; CHECK-NOT:   load i32, i32* %z, align 4
+; CHECK:     if.end:
+; CHECK:       phi i32 [ [[X]], %if.else ], [ [[X]], %if.then ]
+; CHECK:       phi i32 [ [[Z]], %if.else ], [ [[Z]], %if.then ]
+;
+entry:
+  br i1 %cmp, label %if.else, label %if.then
+
+if.then:
+  %0 = getelementptr inbounds i32, i32* %y, i64 1
+  %1 = getelementptr inbounds i32, i32* %y, i64 2
+  %2 = load i32, i32* %x, align 4
+  %3 = load i32, i32* %z, align 4
+  store i32 %2, i32* %0, align 4
+  store i32 %3, i32* %1, align 4
+  br label %if.end
+
+if.else:
+  %4 = getelementptr inbounds i32, i32* %y, i64 2
+  %5 = getelementptr inbounds i32, i32* %y, i64 1
+  %6 = load i32, i32* %x, align 4
+  %7 = load i32, i32* %z, align 4
+  store i32 %6, i32* %4, align 4
+  store i32 %7, i32* %5, align 4
+  br label %if.end
+
+if.end:
+  %8 = phi i32* [ %4, %if.else ], [ %0, %if.then ]
+  %9 = phi i32* [ %5, %if.else ], [ %1, %if.then ]
+  %10 = phi i32 [ %6, %if.else ], [ %2, %if.then ]
+  %11 = phi i32 [ %7, %if.else ], [ %3, %if.then ]
+  %12 = add i32 %10, %11
+  store i32 %12, i32* %8, align 4
+  store i32 %12, i32* %9, align 4
+  ret void
+}
+
+define void @isLegalToHoist_x(i1 %cmp, i32* %x, i32* %y, i32* %z) {
+; CHECK-LABEL: @isLegalToHoist_x(
+; CHECK:     entry:
+; CHECK:       [[X:%.*]] = load i32, i32* %x, align 4
+; CHECK-NOT:   load volatile i32, i32* %z, align 4
+; CHECK:     if.then:
+; CHECK-NOT:   load i32, i32* %x, align 4
+; CHECK:       load volatile i32, i32* %z, align 4
+; CHECK:     if.else:
+; CHECK-NOT:   load i32, i32* %x, align 4
+; CHECK:       load volatile i32, i32* %z, align 4
+; CHECK:     if.end:
+; CHECK:       phi i32 [ [[X]], %if.else ], [ [[X]], %if.then ]
+;
+entry:
+  br i1 %cmp, label %if.else, label %if.then
+
+if.then:
+  %0 = getelementptr inbounds i32, i32* %y, i64 1
+  %1 = getelementptr inbounds i32, i32* %y, i64 2
+  %2 = load i32, i32* %x, align 4
+  %3 = load volatile i32, i32* %z, align 4
+  store i32 %2, i32* %0, align 4
+  store i32 %3, i32* %1, align 4
+  br label %if.end
+
+if.else:
+  %4 = getelementptr inbounds i32, i32* %y, i64 2
+  %5 = getelementptr inbounds i32, i32* %y, i64 1
+  %6 = load i32, i32* %x, align 4
+  %7 = load volatile i32, i32* %z, align 4
+  store i32 %6, i32* %4, align 4
+  store i32 %7, i32* %5, align 4
+  br label %if.end
+
+if.end:
+  %8 = phi i32* [ %4, %if.else ], [ %0, %if.then ]
+  %9 = phi i32* [ %5, %if.else ], [ %1, %if.then ]
+  %10 = phi i32 [ %6, %if.else ], [ %2, %if.then ]
+  %11 = phi i32 [ %7, %if.else ], [ %3, %if.then ]
+  %12 = add i32 %10, %11
+  store i32 %12, i32* %8, align 4
+  store i32 %12, i32* %9, align 4
+  ret void
+}
+
+define void @isIllegalToHoist(i1 %cmp, i32* %x, i32* %y, i32* %z) {
+; CHECK-LABEL: @isIllegalToHoist(
+; CHECK:     entry:
+; CHECK-NOT:   load volatile i32, i32* %x, align 4
+; CHECK-NOT:   load i32, i32* %z, align 4
+; CHECK:     if.then:
+; CHECK:       load volatile i32, i32* %x, align 4
+; CHECK:       load i32, i32* %z, align 4
+; CHECK:     if.else:
+; CHECK:       load volatile i32, i32* %x, align 4
+; CHECK:       load i32, i32* %z, align 4
+; CHECK:     if.end:
+;
+entry:
+  br i1 %cmp, label %if.else, label %if.then
+
+if.then:
+  %0 = getelementptr inbounds i32, i32* %y, i64 1
+  %1 = getelementptr inbounds i32, i32* %y, i64 2
+  %2 = load volatile i32, i32* %x, align 4
+  %3 = load i32, i32* %z, align 4
+  store i32 %2, i32* %0, align 4
+  store i32 %3, i32* %1, align 4
+  br label %if.end
+
+if.else:
+  %4 = getelementptr inbounds i32, i32* %y, i64 2
+  %5 = getelementptr inbounds i32, i32* %y, i64 1
+  %6 = load volatile i32, i32* %x, align 4
+  %7 = load i32, i32* %z, align 4
+  store i32 %6, i32* %4, align 4
+  store i32 %7, i32* %5, align 4
+  br label %if.end
+
+if.end:
+  %8 = phi i32* [ %4, %if.else ], [ %0, %if.then ]
+  %9 = phi i32* [ %5, %if.else ], [ %1, %if.then ]
+  %10 = phi i32 [ %6, %if.else ], [ %2, %if.then ]
+  %11 = phi i32 [ %7, %if.else ], [ %3, %if.then ]
+  %12 = add i32 %10, %11
+  store i32 %12, i32* %8, align 4
+  store i32 %12, i32* %9, align 4
+  ret void
+}