[LICM] Extend the MustExecute scope

[skatkov]

Summary

CanProveNotTakenFirstIteration utility does not handle the case when
condition of the branch is a constant. Add its handling.

[reames]

LGTM w/minor changes

Separately, Serguei, you should try to figure out what the pass ordering problem in our downstream pipeline was that we don't simplify the branches away before we get to LICM. This patch is definitely useful though, so that's an orthogonal improvement to pursue.

test/Analysis/MustExecute/const-cond.ll

5

Can you add a comment above to indicate the value of this w.r.t. eliminating pass ordering dependencies?

test/Transforms/LICM/hoist-mustexec.ll

221

This isn't the intent of this test. Can you tweak the test to ensure this keeps testing the negative case?

[skatkov]

Before landing.

Philip, I hope I correctly understood the intent of the test.

[reames]

Seems reasonable, go for it.

lib/Analysis/MustExecute.cpp

static bool CanProveNotTakenFirstIteration(BasicBlock *ExitBlock,
   auto *CondExitBlock = ExitBlock->getSinglePredecessor();
   if (!CondExitBlock)
     // expect unique exits
     return false;
   assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
   auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
   if (!BI || !BI->isConditional())
     return false;
+  // If condition is constant and false leads to ExitBlock then we always
+  // execute the true branch.
+  if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
+    return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
   auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
   if (!Cond)
     return false;
   // todo: this would be a lot more powerful if we used scev, but all the
   // plumbing is currently missing to pass a pointer in from the pass
   // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
   auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
   auto *RHS = Cond->getOperand(1);

test/Analysis/MustExecute/const-cond.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -disable-output -print-mustexecute %s 2>&1 | FileCheck %s
+
+; In general the CFG below is easily simplified but this is useful for
+; pass ordering issue elimination..
+define i1 @const_cond(i32 %high) {
+; CHECK-LABEL: @const_cond(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; (mustexec in: loop)
+; CHECK-NEXT:    br i1 true, label [[NEXT:%.*]], label [[NEVER1:%.*]] ; (mustexec in: loop)
+; CHECK:       next:
+; CHECK-NEXT:    br i1 false, label [[NEVER2:%.*]], label [[BACKEDGE]] ; (mustexec in: loop)
+; CHECK:       backedge:
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; (mustexec in: loop)
+; CHECK-NEXT:    [[EXIT_TEST:%.*]] = icmp slt i32 [[IV]], [[HIGH:%.*]] ; (mustexec in: loop)
+; CHECK-NEXT:    br i1 [[EXIT_TEST]], label [[LOOP]], label [[EXIT:%.*]] ; (mustexec in: loop)
+; CHECK:       exit:
+; CHECK-NEXT:    ret i1 false
+; CHECK:       never1:
+; CHECK-NEXT:    unreachable
+; CHECK:       never2:
+; CHECK-NEXT:    unreachable
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
+  br i1 true, label %next, label %never1
+next:
+  br i1 false, label %never2, label %backedge
+backedge:
+  %iv.next = add nsw nuw i32 %iv, 1
+  %exit.test = icmp slt i32 %iv, %high
+  br i1 %exit.test, label %loop, label %exit
+
+exit:
+  ret i1 false
+never1:
+  unreachable
+never2:
+  unreachable
+}
+

test/Transforms/LICM/hoist-mustexec.ll

 fail:
   call void @f()
   ret i32 -1
 }
 
 define i32 @test-wrongphi(i32* noalias nocapture readonly %a) nounwind uwtable {
 ; CHECK-LABEL: @test-wrongphi(
 entry:
   br label %for.body
   
 for.body:
   %iv = phi i32 [ 0, %entry ], [ %inc, %continue ]
   %acc = phi i32 [ 0, %entry ], [ %add, %continue ]
-  br label %dummy_block
-dummy_block:
-  %wrongphi = phi i32 [12, %for.body]
+  %cond = icmp ult i32 %iv, 500
+  br i1 %cond, label %dummy_block1, label %dummy_block2
+
+dummy_block1:
+  br label %dummy_block2
+
+dummy_block2:
+  %wrongphi = phi i32 [11, %for.body], [12, %dummy_block1]
   %r.chk = icmp ugt i32 %wrongphi, 2000
   br i1 %r.chk, label %fail, label %continue
 continue:
 ; CHECK-LABEL: continue
 ; CHECK: %i1 = load i32, i32* %a, align 4
   %i1 = load i32, i32* %a, align 4
   %add = add nsw i32 %i1, %acc
   %inc = add nuw nsw i32 %iv, 1