[LoopUnswitch] Unswitch on conditions feeding into guards

[sanjoy]

Summary

This is a straightforward extension of what LoopUnswitch does to
branches to guards. That is, we unswitch

for (;;) {
  ...
  guard(loop_invariant_cond);
  ...
}

into

if (loop_invariant_cond) {
  for (;;) {
    ...
    // There is no need to emit guard(true)
    ...
  }
} else {
  for (;;) {
    ...
    guard(false);
    // SimplifyCFG will clean this up by adding an
    // unreachable after the guard(false)
    ...
  }
}

[majnemer]

lib/Transforms/Scalar/LoopUnswitch.cpp

518–533

For some reason my eye is hunting for punctuation, maybe throw on a ':'

526

Perhaps "That loops don't contain ..."

527

.

532

Is it safe to make this an AssertingVH? Could unswitching one guard lead to another guard getting cloned while the original gets erased?

[sanjoy]

• address review

lib/Transforms/Scalar/LoopUnswitch.cpp

532

Good point. Added a test case and changed to keep raw pointers for now.

[majnemer]

lib/Transforms/Scalar/LoopUnswitch.cpp

532

Hmm, does switching to a raw pointer help? In the even in which the guard was cloned and destroyed, the guard in your list would be a bad pointer.

[sanjoy]

• Add comment

lib/Transforms/Scalar/LoopUnswitch.cpp

532

My reading of the code is that that's fine, since if we do invalidate something in Guards, we'll return and never look at Guards again. I've added a comment for that.

[majnemer]

LGTM

lib/Transforms/Scalar/LoopUnswitch.cpp

 #include <map>
 #include <set>
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-unswitch"
 
 STATISTIC(NumBranches, "Number of branches unswitched");
 STATISTIC(NumSwitches, "Number of switches unswitched");
+STATISTIC(NumGuards,   "Number of guards unswitched");
 STATISTIC(NumSelects , "Number of selects unswitched");
 STATISTIC(NumTrivial , "Number of unswitches that are trivial");
 STATISTIC(NumSimplify, "Number of simplifications of unswitched code");
 STATISTIC(TotalInsts,  "Total number of instructions analyzed");
 
 // The specific value of 100 here was chosen based only on intuition and a
 // few specific examples.
 static cl::opt<unsigned>
if (!BranchesInfo.countLoop(
           AC))
     return false;
 
   // Try trivial unswitch first before loop over other basic blocks in the loop.
   if (TryTrivialLoopUnswitch(Changed)) {
     return true;
   }
 
-  // Do not unswitch loops containing convergent operations, as we might be
-  // making them control dependent on the unswitch value when they were not
-  // before.
-  // FIXME: This could be refined to only bail if the convergent operation is
-  // not already control-dependent on the unswitch value.
+  // Run through the instructions in the loop, keeping track of three things:
+  //
+  //  - That we do not unswitch loops containing convergent operations, as we
+  //    might be making them control dependent on the unswitch value when they
+  //    were not before.
+  //    FIXME: This could be refined to only bail if the convergent operation is
+  //    not already control-dependent on the unswitch value.
+  //
+  //  - That basic blocks in the loop contain invokes whose predecessor edges we
+  //    cannot split.
+  //
+  //  - The set of guard intrinsics encountered (these are non terminator
+  //    instructions that are also profitable to be unswitched).
+
+  SmallVector<IntrinsicInst *, 4> Guards;
+
   for (const auto BB : currentLoop->blocks()) {
     for (auto &I : *BB) {
       auto CS = CallSite(&I);
       if (!CS) continue;
       if (CS.hasFnAttr(Attribute::Convergent))
         return false;
-      // Return false if any loop blocks contain invokes whose predecessor edges
-      // we cannot split.
       if (auto *II = dyn_cast<InvokeInst>(&I))
         if (!II->getUnwindDest()->canSplitPredecessors())
           return false;
+      if (auto *II = dyn_cast<IntrinsicInst>(&I))
+        if (II->getIntrinsicID() == Intrinsic::experimental_guard)
+          Guards.push_back(II);
     }
   }
 
   // Do not do non-trivial unswitch while optimizing for size.
   // FIXME: Use Function::optForSize().
   if (OptimizeForSize ||
       loopHeader->getParent()->hasFnAttribute(Attribute::OptimizeForSize))
     return false;
 
   if (LoopUnswitchWithBlockFrequency && EnabledPGO) {
     // Compute the weighted frequency of the hottest block in the
     // loop (loopHeader in this case since inner loops should be
     // processed before outer loop). If it is less than ColdFrequency,
     // we should not unswitch.
     BlockFrequency LoopEntryFreq = BFI.getBlockFreq(loopHeader);
     if (LoopEntryFreq < ColdEntryFreq)
       return false;
   }
 
+  for (IntrinsicInst *Guard : Guards) {
+    Value *LoopCond =
+        FindLIVLoopCondition(Guard->getOperand(0), currentLoop, Changed);
+    if (LoopCond &&
+        UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context))) {
+      // NB! Unswitching (if successful) could have erased some of the
+      // instructions in Guards leaving dangling pointers there.  This is fine
+      // because we're returning now, and won't look at Guards again.
+      ++NumGuards;
+      return true;
+    }
+  }
+
   // Loop over all of the basic blocks in the loop.  If we find an interior
   // block that is branching on a loop-invariant condition, we can unswitch this
   // loop.
   for (Loop::block_iterator I = currentLoop->block_begin(),
          E = currentLoop->block_end(); I != E; ++I) {
     TerminatorInst *TI = (*I)->getTerminator();
 
     // Unswitching on a potentially uninitialized predicate is not

test/Transforms/LoopUnswitch/guards.ll

+; RUN: opt -S -loop-unswitch < %s | FileCheck %s
+
+declare void @llvm.experimental.guard(i1, ...)
+
+define void @f_0(i32 %n, i32* %ptr, i1 %c) {
+; CHECK-LABEL: @f_0(
+; CHECK: loop.us:
+; CHECK-NOT: guard
+; CHECK: loop:
+; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ]
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add i32 %iv, 1
+  call void(i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+  store volatile i32 0, i32* %ptr
+  %becond = icmp ult i32 %iv.inc, %n
+  br i1 %becond, label %leave, label %loop
+
+leave:
+  ret void
+}
+
+define void @f_1(i32 %n, i32* %ptr, i1 %c_0, i1 %c_1) {
+; CHECK-LABEL: @f_1(
+; CHECK: loop.us.us:
+; CHECK-NOT: guard
+; CHECK: loop.us:
+; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"(i32 2) ]
+; CHECK-NOT: guard
+; CHECK: loop.us1:
+; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"(i32 1) ]
+; CHECK-NOT: guard
+; CHECK: loop:
+; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"(i32 1) ]
+; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"(i32 2) ]
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add i32 %iv, 1
+  call void(i1, ...) @llvm.experimental.guard(i1 %c_0) [ "deopt"(i32 1) ]
+  store volatile i32 0, i32* %ptr
+  call void(i1, ...) @llvm.experimental.guard(i1 %c_1) [ "deopt"(i32 2) ]
+  %becond = icmp ult i32 %iv.inc, %n
+  br i1 %becond, label %leave, label %loop
+
+leave:
+  ret void
+}
+
+; Basic negative test
+
+define void @f_3(i32 %n, i32* %ptr, i1* %c_ptr) {
+; CHECK-LABEL: @f_3(
+; CHECK-NOT: loop.us:
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add i32 %iv, 1
+  %c = load volatile i1, i1* %c_ptr
+  call void(i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+  store volatile i32 0, i32* %ptr
+  %becond = icmp ult i32 %iv.inc, %n
+  br i1 %becond, label %leave, label %loop
+
+leave:
+  ret void
+}
+
+define void @f_4(i32 %n, i32* %ptr, i1 %c) {
+; CHECK-LABEL: @f_4(
+;
+; Demonstrate that unswitching on one guard can cause another guard to
+; be erased (this has implications on what guards we can keep raw
+; pointers to).
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add i32 %iv, 1
+  call void(i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"(i32 1) ]
+  store volatile i32 0, i32* %ptr
+  %neg = xor i1 %c, 1
+  call void(i1, ...) @llvm.experimental.guard(i1 %neg) [ "deopt"(i32 2) ]
+  %becond = icmp ult i32 %iv.inc, %n
+  br i1 %becond, label %leave, label %loop
+
+leave:
+  ret void
+}