[GuardWidening] Insert fictive guards to loop preheader to increase chances of widening

[mkazantsev]

Summary

Sometimes we have something like:

preheader:
  guard(%c1)[];
  %c2 =<some cond>;
  br i1 %loop

loop:
  ...
  guard(%c2)
  ...

Despite %c2 being loop invariant, we cannot widen the 2nd guard into
the 1st one in case if %c2 is not available at the point of 1st guard. To
solve that situation, we can insert the fictive guard with true condition
like this:

preheader:
  guard(%c1)[];
  %c2 =<some cond>;
  guard(true)[];
  br i1 %loop

loop:
  ...
  guard(%c2)
  ...

And then widen the condition of guard in loop into this fictive guard. In case
if it didn't help, we can just safely delete the fictive guard we've just inserted.

[sanjoy]

Did you consider phrasing this as an "LICM" on guard? It is a bit of a code smell in LLVM to do an operation speculatively and then undo it immediately.

[reames]

I think this is the wrong approach. I'd suggest tackling the example in two ways:

1. Try to hoist c2 above the existing guard. We have lots of precedent for such things, look for makeAvailableAt.
2. Hoisting a guard from within a loop to the preheader is worthwhile. I've been cleaning up the pieces of LICM needed to make this easy. We can chat offline if you want to pick that up and finish it.

[mkazantsev]

After some discussion, I'll try making some variation of this in LICM.

[mkazantsev]

Abandon in favor of https://reviews.llvm.org/D50501

lib/Transforms/Scalar/GuardWidening.cpp

static cl::opt<unsigned> FrequentBranchThreshold(
     cl::desc("When WidenFrequentBranches is set to true, this option is used "
              "to determine which branches are frequently taken. The criteria "
              "that a branch is taken more often than "
              "((FrequentBranchThreshold - 1) / FrequentBranchThreshold), then "
              "it is considered frequently taken"),
     cl::init(1000));
 
 
+static cl::opt<bool> InsertFictiveGuardsToPreheader(
+    "loop-guard-widening-insert-fictive-guards-to-preheader", cl::Hidden,
+    cl::desc("When turned on, loop guard widening will attempt to insert "
+             "fictive guards to loop preheader when it thinks that it may "
+             "enable more widening opportunities"),
+    cl::init(false));
+
 namespace {
 
 // Get the condition of \p I. It can either be a guard or a conditional branch.
 static Value *getCondition(Instruction *I) {
   if (IntrinsicInst *GI = dyn_cast<IntrinsicInst>(I)) {
     assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
            "Bad guard intrinsic?");
     return GI->getArgOperand(0);

 /// scheduled with other loop passes w/o breaking out of LPM
 struct LoopGuardWideningLegacyPass : public LoopPass {
   static char ID;
 
   LoopGuardWideningLegacyPass() : LoopPass(ID) {
     initializeLoopGuardWideningLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
+  Instruction *insertFictiveGuardToPreheader(const Loop *L) {
+    // If the option is disabled, bail.
+    if (!InsertFictiveGuardsToPreheader)
+      return nullptr;
+    // Make sure that the loop has a preheader.
+    BasicBlock *Preheader = L->getLoopPreheader();
+    if (!Preheader)
+      return nullptr;
+
+    // Find last guard instruction in preheader. Insert a fictive guard after it
+    // but before any instruction that can write memory and invalidate the deopt
+    // bundle.
+    Instruction *InsertionPoint = nullptr;
+    IntrinsicInst *LastSeenGuard = nullptr;
+
+    for (Instruction &I : *Preheader)
+      if (isa<IntrinsicInst>(I) && isGuard(&I)) {
+        LastSeenGuard = cast<IntrinsicInst>(&I);
+        InsertionPoint = nullptr;
+      } else if (!InsertionPoint && (I.mayWriteToMemory() || I.isTerminator()))
+        InsertionPoint = &I;
+
+    // If there are no instructions between the guard and the insertion point,
+    // it makes to sense to insert the fictive guard.
+    if (!LastSeenGuard || LastSeenGuard->getNextNode() == InsertionPoint)
+      return nullptr;
+
+    assert(InsertionPoint && "Should be!");
+    // If we think that inserting a fictive guard with "true" condition here
+    // might be profitable, do it.
+    auto *NewGuard = LastSeenGuard->clone();
+    setCondition(NewGuard, ConstantInt::getTrue(LastSeenGuard->getContext()));
+    NewGuard->insertBefore(InsertionPoint);
+    return NewGuard;
+  }
+
   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     if (skipLoop(L))
       return false;
     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
     auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
     BasicBlock *RootBB = L->getLoopPredecessor();
     if (!RootBB)
       RootBB = L->getHeader();
     auto BlockFilter = [&](BasicBlock *BB) {
       return BB == RootBB || L->contains(BB);
     };
     BranchProbabilityInfo *BPI = nullptr;
     if (WidenFrequentBranches)
       BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
-    return GuardWideningImpl(DT, PDT, LI, BPI,
+    Instruction *FictiveGuard = insertFictiveGuardToPreheader(L);
+    bool Changed = GuardWideningImpl(DT, PDT, LI, BPI,
                                      DT.getNode(RootBB), BlockFilter).run();
+    // If the fictive guard wasn't useful for widening, erase it.
+    if (FictiveGuard && FictiveGuard->getParent() &&
+        getCondition(FictiveGuard) ==
+            ConstantInt::getTrue(FictiveGuard->getContext()))
+      // Do not use eliminateGuard because we don't want to mess the statistics.
+      eliminateGuard(FictiveGuard);
+    return Changed;
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     if (WidenFrequentBranches)
       AU.addRequired<BranchProbabilityInfoWrapperPass>();
     AU.setPreservesCFG();
     getLoopAnalysisUsage(AU);
     AU.addPreserved<PostDominatorTreeWrapperPass>();

test/Transforms/GuardWidening/fictive-guards.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -loop-guard-widening-insert-fictive-guards-to-preheader=true -S -loop-guard-widening < %s | FileCheck %s
+
+; Test fictive guards insertion mechanism.
+
+declare void @llvm.experimental.guard(i1,...)
+
+; Check that we can insert another guard and widen into it if widening into the
+; existing guard is impossible.
+define void @test_01(i1 %c, i32* %p) {
+; CHECK-LABEL: @test_01(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[C:%.*]]) [ "deopt"() ]
+; CHECK-NEXT:    [[A:%.*]] = load i32, i32* [[P:%.*]]
+; CHECK-NEXT:    [[INVARIANT_COND:%.*]] = icmp ne i32 [[A]], 100
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 true, [[INVARIANT_COND]]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], 1000
+; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+  %a = load i32, i32* %p
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i32 %iv, 1
+  %invariant_cond = icmp ne i32 %a, 100
+  call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond) [ "deopt"() ]
+  %loop_cond = icmp slt i32 %iv.next, 1000
+  br i1 %loop_cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Make sure that the fictive guard does not exist after widening.
+define void @test_02(i1 %c, i1 %c2, i32* %p) {
+; CHECK-LABEL: @test_02(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[C:%.*]], [[C2:%.*]]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
+; CHECK-NEXT:    [[UNNEEDED_COND:%.*]] = or i1 [[C]], [[C2]]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], 1000
+; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+  %unneeded_cond = or i1 %c, %c2
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i32 %iv, 1
+  call void (i1, ...) @llvm.experimental.guard(i1 %c2) [ "deopt"() ]
+  %loop_cond = icmp slt i32 %iv.next, 1000
+  br i1 %loop_cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Make sure that we don't insert a fictive guard after the memory-writing
+; instruction.
+define void @test_03(i1 %c, i32* %p, i32* %s) {
+; CHECK-LABEL: @test_03(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[C:%.*]]) [ "deopt"() ]
+; CHECK-NEXT:    [[A:%.*]] = load i32, i32* [[P:%.*]]
+; CHECK-NEXT:    [[INVARIANT_COND:%.*]] = icmp ne i32 [[A]], 100
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 true, [[INVARIANT_COND]]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
+; CHECK-NEXT:    store i32 0, i32* [[S:%.*]]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], 1000
+; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+  %a = load i32, i32* %p
+  store i32 0, i32* %s
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
+  %iv.next = add i32 %iv, 1
+  %invariant_cond = icmp ne i32 %a, 100
+  call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond) [ "deopt"() ]
+  %loop_cond = icmp slt i32 %iv.next, 1000
+  br i1 %loop_cond, label %loop, label %exit
+
+exit:
+  ret void
+}