[SimplifyCFG] Expanding scope for hoisting common instructions after branch

[inouehrs]

Summary

SimplifyCFG scans common instructions in two basic blocks after conditional branch and hoist them before the branch.
The current implementation finds common instructions if the common instruction sequence starts from the top of the BBs without other instructions.
This patch allows other instructions to be placed before the common instruction sequence by scanning more instructions in BBs. To avoid excessive cost, the scan is limited to up to 10 instructions from the top of the BB.
This additional hoisting gives code size reduction and also may result in further CFG optimizations, e.g. using a select instruction instead of the branch.

With this patch, about 67k more instructions are hoisted while bootstrap test (it is about 1.5x increase). The limit of the scan range (10 instructions) covers about 95% of the opportunity. The changes in the build time of the bootstrap test was almost negligible.

[efriedma]

LLVM has a GVNHoist pass, which is both more efficient and more effective than anything we can do in SimplifyCFG. (It's currently off by default, but it could probably be turned on with a bit more testing/bugfixing.) I would rather focus on getting that turned on, instead of doing something like this.

lib/Transforms/Utils/SimplifyCFG.cpp

1275

The way you're counting instructions here is wrong: you have to skip debug info.

It looks like this can only hoist one instruction each time HoistThenElseCodeToIf is called?

[inouehrs]

@efriedma I agree. I confirmed that GVNHoist can optimize my motivating examples. So I abandon this.
I hope GVNHoist will become default on soon. Thanks!

lib/Transforms/Utils/SimplifyCFG.cpp

 
 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I);
 
 /// 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.
+  // This does matching to find identical instructions in the two blocks.
+
   BasicBlock *BB1 = BI->getSuccessor(0); // The true destination.
   BasicBlock *BB2 = BI->getSuccessor(1); // The false destination
 
   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) ||
+
+  // We try to match instructions in two basic blocks.
+  // To avoid excessive cost for matching, we limit the range to scan
+  // by up to SCAN_LIMIT instructions.
+  const unsigned SCAN_LIMIT = 10;
+
+  // If we hoist instructions other than the first one in the block,
+  // we remember what instructions we skipped for the later check.
+  bool SkippedInst = false, SkippedStore = false, SkippedLoad = false;
+  bool Found = false;
+  BasicBlock::iterator TmpItr1(I1);
+  for (unsigned Count1 = 0;
+       TmpItr1 != BB1->end() && Count1 < SCAN_LIMIT; Count1++) {
+    Instruction *TmpI1 = &*TmpItr1++;
+    BasicBlock::iterator TmpItr2(I2);
+    for (unsigned Count2 = 0;
+        TmpItr2 != BB2->end() && Count2 < SCAN_LIMIT; Count2++) {
+      Instruction *TmpI2 = &*TmpItr2++;
+      if (TmpI1->isIdenticalToWhenDefined(TmpI2)) {
+        Found = true;
+        if (Count1 || Count2) {
+          SkippedInst = true;
+
+          // Advancing iterators over skipped instructions.
+          // We also check memory accesses by the skipped instructions.
+          for (unsigned I = 0; I < Count1; I++) {
+            if (I1->mayWriteToMemory()) SkippedStore = true;
+            if (I1->mayReadFromMemory()) SkippedLoad = true;
+            I1 = &*BB1_Itr++;
+          }
+          for (unsigned I = 0; I < Count2; I++) {
+            if (I2->mayWriteToMemory()) SkippedStore = true;
+            if (I2->mayReadFromMemory()) SkippedLoad = true;
+            I2 = &*BB2_Itr++;
+          }
+        }
+        break;
+      }
+      // We do not move instructions over atomic op (e.g. fence) or method call
+      if (TmpI2->isAtomic() || isa<CallInst>(TmpI2) || isa<InvokeInst>(TmpI2))
+        break;
+    }
+    if (Found ||
+        TmpI1->isAtomic() || isa<CallInst>(TmpI1) || isa<InvokeInst>(TmpI1))
+      break;
+  }
+
+  if (!Found)
+    return false;
+
+  if (isa<PHINode>(I1) ||
       (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;
 
+    // We don't hoist a load or store instruction over potentially conflicting
+    // memory accesses. To do: refine based on alias analysis.
+    if ((I1->mayReadFromMemory() && SkippedStore) ||
+        (I1->mayWriteToMemory() && (SkippedStore || SkippedLoad)))
+      return Changed;
+
     // 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
     // marked as such. Otherwise, we might end up in a situation where we hoist
     // from a block where the terminator is a `ret` to a block where the terminator
     // is a `br`, and `musttail` calls expect to be followed by a return.
     auto *C1 = dyn_cast<CallInst>(I1);
     auto *C2 = dyn_cast<CallInst>(I2);
     if (C1 && C2)
static bool HoistThenElseCodeToIf(BranchInst *BI,
 
   return true;
 
 HoistTerminator:
   // It may not be possible to hoist an invoke.
   if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))
     return Changed;
 
+  // If we have remaining instructions in a BB due to skip,
+  // we cannot hoist branch instruction.
+  if (SkippedInst)
+    return Changed;
+
   for (BasicBlock *Succ : successors(BB1)) {
     for (PHINode &PN : Succ->phis()) {
       Value *BB1V = PN.getIncomingValueForBlock(BB1);
       Value *BB2V = PN.getIncomingValueForBlock(BB2);
       if (BB1V == BB2V)
         continue;
 
       // Check for passingValueIsAlwaysUndefined here because we would rather

test/Transforms/SimplifyCFG/phi-undef-loadstore.ll

 ; RUN: opt -simplifycfg -S < %s | FileCheck %s
 
+declare void @foo() nounwind
 declare void @bar() nounwind
 
 define i32 @test1(i32* %a, i32 %b, i32* %c, i32 %d) nounwind {
 entry:
   %tobool = icmp eq i32 %b, 0
   br i1 %tobool, label %if.else, label %if.then
 
 if.then:                                          ; preds = %entry
-  tail call void @bar() nounwind
+  tail call void @foo() nounwind
   br label %if.end7
 
 if.else:                                          ; preds = %entry
   %tobool3 = icmp eq i32 %d, 0
   br i1 %tobool3, label %if.end7, label %if.then4
 
 if.then4:                                         ; preds = %if.else
   tail call void @bar() nounwind

 }
 
 define i32 @test2(i32* %a, i32 %b, i32* %c, i32 %d) nounwind {
 entry:
   %tobool = icmp eq i32 %b, 0
   br i1 %tobool, label %if.else, label %if.then
 
 if.then:                                          ; preds = %entry
-  tail call void @bar() nounwind
+  tail call void @foo() nounwind
   br label %if.end7
 
 if.else:                                          ; preds = %entry
   %tobool3 = icmp eq i32 %d, 0
   br i1 %tobool3, label %if.end7, label %if.then4
 
 if.then4:                                         ; preds = %if.else
   tail call void @bar() nounwind

 }
 
 define i32 @test3(i32* %a, i32 %b, i32* %c, i32 %d) nounwind {
 entry:
   %tobool = icmp eq i32 %b, 0
   br i1 %tobool, label %if.else, label %if.then
 
 if.then:                                          ; preds = %entry
-  tail call void @bar() nounwind
+  tail call void @foo() nounwind
   br label %if.end7
 
 if.else:                                          ; preds = %entry
   %tobool3 = icmp eq i32 %d, 0
   br i1 %tobool3, label %if.end7, label %if.then4
 
 if.then4:                                         ; preds = %if.else
   tail call void @bar() nounwind

 }
 
 define i32 @test4(i32* %a, i32 %b, i32* %c, i32 %d) nounwind {
 entry:
   %tobool = icmp eq i32 %b, 0
   br i1 %tobool, label %if.else, label %if.then
 
 if.then:                                          ; preds = %entry
-  tail call void @bar() nounwind
+  tail call void @foo() nounwind
   br label %if.end7
 
 if.else:                                          ; preds = %entry
   %tobool3 = icmp eq i32 %d, 0
   br i1 %tobool3, label %if.end7, label %if.then4
 
 if.then4:                                         ; preds = %if.else
   tail call void @bar() nounwind

test/Transforms/SimplifyCFG/skip.ll

+; RUN: opt -simplifycfg -S < %s | FileCheck %s
+
+declare void @foo() nounwind
+
+define i32 @test1(i32 %a, i32 %b, i32* %c) {
+; We expect load i32, i32* %c is hoisted into %entry from %if.then and %if.else
+; CHECK-LABEL: test1
+; CHECK: load i32, i32* %c
+; CHECK-LABEL: if.then
+; CHECK-NOT: load i32, i32* %c
+
+entry:
+  %tobool = icmp eq i32 %b, 0
+  br i1 %tobool, label %if.else, label %if.then
+
+if.then:
+  %0 = add nsw i32 %a, 1
+  %1 = load i32, i32* %c
+  br label %if.end
+
+if.else:
+  %2 = mul nsw i32 %a, 5
+  %3 = load i32, i32* %c
+  call void @foo() ; to avoid further simplification
+  br label %if.end
+
+if.end:
+  %4 = phi i32 [ %0, %if.then ], [ %2, %if.else ]
+  %5 = phi i32 [ %1, %if.then ], [ %3, %if.else ]
+  %6 = add nsw i32 %4, %5
+  ret i32 %6
+}
+
+define i32 @test2(i32 %a, i32 %b, i32* %c) {
+; We expect load i32, i32* %c is hoisted into %entry from %if.then and %if.else
+; Then the branch is further optimized using select.
+; CHECK-LABEL: test2
+; CHECK: select
+; CHECK-NOT: if.else
+; CHECK-NOT: if.then
+; CHECK: ret
+
+entry:
+  %tobool = icmp eq i32 %b, 0
+  br i1 %tobool, label %if.else, label %if.then
+
+if.then:
+  %0 = add nsw i32 %a, 1
+  %1 = load i32, i32* %c
+  br label %if.end
+
+if.else:
+  %2 = mul nsw i32 %a, 5
+  %3 = load i32, i32* %c
+  br label %if.end
+
+if.end:
+  %4 = phi i32 [ %0, %if.then ], [ %2, %if.else ]
+  %5 = phi i32 [ %1, %if.then ], [ %3, %if.else ]
+  %6 = add nsw i32 %4, %5
+  ret i32 %6
+}
+
+define i32 @test3(i32 %a, i32 %b, i32* %c) {
+; We expect load i32, i32* %c is NOT hoisted due to a call instruction
+; CHECK-LABEL: test3
+; CHECK-NOT: load i32, i32* %c
+; CHECK-LABEL: if.then
+; CHECKT: load i32, i32* %c
+
+entry:
+  %tobool = icmp eq i32 %b, 0
+  br i1 %tobool, label %if.else, label %if.then
+
+if.then:
+  %0 = add nsw i32 %a, 1
+  %1 = load i32, i32* %c
+  br label %if.end
+
+if.else:
+  %2 = mul nsw i32 %a, 5
+  call void @foo()
+  %3 = load i32, i32* %c
+  br label %if.end
+
+if.end:
+  %4 = phi i32 [ %0, %if.then ], [ %2, %if.else ]
+  %5 = phi i32 [ %1, %if.then ], [ %3, %if.else ]
+  %6 = add nsw i32 %4, %5
+  ret i32 %6
+}
+
+define i32 @test4(i32 %a, i32 %b, i32* %c) {
+; We expect load i32, i32* %c is NOT hoisted due to a fence instruction
+; CHECK-LABEL: test4
+; CHECK-NOT: load i32, i32* %c
+; CHECK-LABEL: if.then
+; CHECKT: load i32, i32* %c
+
+entry:
+  %tobool = icmp eq i32 %b, 0
+  br i1 %tobool, label %if.else, label %if.then
+
+if.then:
+  fence acquire
+  %0 = add nsw i32 %a, 1
+  %1 = load i32, i32* %c
+  br label %if.end
+
+if.else:
+  %2 = mul nsw i32 %a, 5
+  %3 = load i32, i32* %c
+  br label %if.end
+
+if.end:
+  %4 = phi i32 [ %0, %if.then ], [ %2, %if.else ]
+  %5 = phi i32 [ %1, %if.then ], [ %3, %if.else ]
+  %6 = add nsw i32 %4, %5
+  ret i32 %6
+}
+
+define i32 @test5(i32 %a, i32 %b, i32* %c) {
+; We expect load i32, i32* %c is NOT hoisted due to a store instruction
+; CHECK-LABEL: test5
+; CHECK-NOT: load i32, i32* %c
+; CHECK-LABEL: if.then
+; CHECKT: load i32, i32* %c
+
+entry:
+  %tobool = icmp eq i32 %b, 0
+  br i1 %tobool, label %if.else, label %if.then
+
+if.then:
+  %0 = add nsw i32 %a, 1
+  store i32 %0, i32* %c
+  %1 = load i32, i32* %c
+  br label %if.end
+
+if.else:
+  %2 = mul nsw i32 %a, 5
+  %3 = load i32, i32* %c
+  br label %if.end
+
+if.end:
+  %4 = phi i32 [ %0, %if.then ], [ %2, %if.else ]
+  %5 = phi i32 [ %1, %if.then ], [ %3, %if.else ]
+  %6 = add nsw i32 %4, %5
+  ret i32 %6
+}
+
+%struct.s = type { i32, i32 }
+
+define signext i32 @func(%struct.s* nocapture readonly %p, i32 signext %f) {
+; Equivalent C code
+; int func(struct s *p, int f) {
+;  int v = 0;
+;  if (f) v = p->a + p->b;
+;  else   v = p->b - p->a;
+;  return v;
+;}
+
+; CHECK-LABEL: func
+; CHECK: select
+; CHECK-NOT: if.else
+; CHECK-NOT: if.then
+; CHECK: ret
+entry:
+  %tobool = icmp eq i32 %f, 0
+  br i1 %tobool, label %if.else, label %if.then
+
+if.then:
+  %a = getelementptr inbounds %struct.s, %struct.s* %p, i64 0, i32 0
+  %0 = load i32, i32* %a, align 4
+  %b = getelementptr inbounds %struct.s, %struct.s* %p, i64 0, i32 1
+  %1 = load i32, i32* %b, align 4
+  %add = add nsw i32 %1, %0
+  br label %if.end
+
+if.else:
+  %b1 = getelementptr inbounds %struct.s, %struct.s* %p, i64 0, i32 1
+  %2 = load i32, i32* %b1, align 4
+  %a2 = getelementptr inbounds %struct.s, %struct.s* %p, i64 0, i32 0
+  %3 = load i32, i32* %a2, align 4
+  %sub = sub nsw i32 %2, %3
+  br label %if.end
+
+if.end:
+  %v.0 = phi i32 [ %add, %if.then ], [ %sub, %if.else ]
+  ret i32 %v.0
+}