[GuardUtils] Add asserts about loop varying widenable conditions

[anna]

Summary

We have now seen two miscompiles because of widening widenable
conditions at incorrect IR points and thereby changing a branch's loop
invariant condition to a loop-varying one (see PR60234 and PR61963).

This patch adds asserts in common guard utilities that we use for
widening to proactively catch these bugs in future.
Note that these asserts will not fire if we were to sink a widenable
condition from out of a loop into a loop (that's also incorrect for the
same reason as above).

Tested this without the fix for PR60234 (guard widening miscompile) and
confirmed the assert fires.

[anna]

Note that this does not fire for LoopPredication currently since we also incorrectly sunk the widenable call into the loop (thereby already making it loop-varying branch before we even used the utility widenWidenableBranch.
So, this can be landed orthogonal to D147662.

[mkazantsev]

I like the general idea, but using L->isLoopInvariant might be too strict, because it can return false for things that are in fact invariant (just computed inside the loop). Can we find a better API for it?

llvm/lib/Transforms/Utils/GuardUtils.cpp

116

This might be too strict. L->isLoopInvariant is only checking placement of instruction. Imagine you have invariant a and b and WidenableBr->getCondition() = add a, b. It is still invariant, no matter if the actual add instruction is placed inside of loop or not. Or, for example, condition is a load marked as !invariant_load; it's still same value no matter where we move it.

If we had SCEV, the good approximation for what we want is isAvailableAtLoopEntry; we need something similar with instructions.

I mean, we *can* go this strict way, but be ready that it will fail when there is no real bug.

[anna]

llvm/lib/Transforms/Utils/GuardUtils.cpp

116

This is true, but it would be a pass-ordering issue. LICM should have hoisted such IR out.
We can strengthen against pass-ordering, but to what extent? In short, failing the assert shows we have one of 2 problems: either an actual bug or a missed performance opportunity, both of which needs investigation :)
I think we can use canHoistOrSinkInstruction API from LICM if we want to have lesser false positives, but that API needs AA to make sure we are hoisting correctly in presence of AA.

[mkazantsev]

Okay... Let's give it a try, but please add WARNING to commit message. If we'll end up finding such situation, we'll need to do something about it. The person who finds this should know this is, kind of, expected.

[anna]

addressed review comment (and also added the message in the code above assert). Rebase.

[anna]

fix test failure in test3 in GuardWidening::loop_invariant_widenable_condition.ll.
Through GW itself, we are placing an invariant condition within the loop.
Strengthened against this in API introduced isLoopInvariantWidenableCond.

[anna]

Hitting this downstream. Assert maybe too strict. Will revert for now and investigate.
During offline discussion with Artur, he had an idea to change the API completely from widening a *branch* to widening a *widenable condition* (i.e. rather than change one use of a widenable condition, we should change all uses). Also, this way, we will never run into change a loop-invariant condition to a loop-varying one (since we're widening at the widenable condition which has to be outside the loop for it to be loop-invariant in the first place).

llvm/include/llvm/Transforms/Utils/GuardUtils.h

 #ifndef LLVM_TRANSFORMS_UTILS_GUARDUTILS_H
 #define LLVM_TRANSFORMS_UTILS_GUARDUTILS_H
 
 namespace llvm {
 
 class BranchInst;
 class CallInst;
 class Function;
+class LoopInfo;
 class Value;
 
 /// Splits control flow at point of \p Guard, replacing it with explicit branch
 /// by the condition of guard's first argument. The taken branch then goes to
 /// the block that contains  \p Guard's successors, and the non-taken branch
 /// goes to a newly-created deopt block that contains a sole call of the
 /// deoptimize function \p DeoptIntrinsic.  If 'UseWC' is set, preserve the
 /// widenable nature of the guard by lowering to equivelent form.  If not set,
 /// lower to a form without widenable semantics.
 void makeGuardControlFlowExplicit(Function *DeoptIntrinsic, CallInst *Guard,
                                   bool UseWC);
 
 /// Given a branch we know is widenable (defined per Analysis/GuardUtils.h),
 /// widen it such that condition 'NewCond' is also known to hold on the taken
 /// path.  Branch remains widenable after transform.
-void widenWidenableBranch(BranchInst *WidenableBR, Value *NewCond);
+void widenWidenableBranch(BranchInst *WidenableBR, Value *NewCond,
+                          const LoopInfo &LI);
 
 /// Given a branch we know is widenable (defined per Analysis/GuardUtils.h),
 /// *set* it's condition such that (only) 'Cond' is known to hold on the taken
 /// path and that the branch remains widenable after transform.
-void setWidenableBranchCond(BranchInst *WidenableBR, Value *Cond);
+void setWidenableBranchCond(BranchInst *WidenableBR, Value *Cond,
+                            const LoopInfo &LI);
 
 } // llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_GUARDUTILS_H

llvm/lib/Transforms/Scalar/GuardWidening.cpp

class GuardWideningImpl {
   /// true (in addition to whatever it is already checking).
   void widenGuard(Instruction *ToWiden, Value *NewCondition,
                   bool InvertCondition) {
     Value *Result;
     Instruction *InsertPt = findInsertionPointForWideCondition(ToWiden);
     widenCondCommon(getCondition(ToWiden), NewCondition, InsertPt, Result,
                     InvertCondition);
     if (isGuardAsWidenableBranch(ToWiden)) {
-      setWidenableBranchCond(cast<BranchInst>(ToWiden), Result);
+      setWidenableBranchCond(cast<BranchInst>(ToWiden), Result, LI);
       return;
     }
     setCondition(ToWiden, Result);
   }
 
 public:
   explicit GuardWideningImpl(DominatorTree &DT, PostDominatorTree *PDT,
                              LoopInfo &LI, AssumptionCache &AC,

llvm/lib/Transforms/Scalar/LoopPredication.cpp

for (BasicBlock *ExitingBB : ExitingBlocks) {
     }
     assert(!Latch || DT->dominates(ExitingBB, Latch));
     Value *NewCond = B.CreateICmp(ICmpInst::ICMP_UGT, ECV, RHS);
     // Freeze poison or undef to an arbitrary bit pattern to ensure we can
     // branch without introducing UB.  See NOTE ON POISON/UNDEF above for
     // context.
     NewCond = B.CreateFreeze(NewCond);
 
-    widenWidenableBranch(WidenableBR, NewCond);
+    widenWidenableBranch(WidenableBR, NewCond, *LI);
 
     Value *OldCond = BI->getCondition();
     BI->setCondition(ConstantInt::get(OldCond->getType(), !ExitIfTrue));
     InvalidateLoop = true;
   }
 
   if (InvalidateLoop)
     // We just mutated a bunch of loop exits changing there exit counts

llvm/lib/Transforms/Utils/GuardUtils.cpp

 //===-- GuardUtils.cpp - Utils for work with guards -------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 // Utils that are used to perform transformations related to guards and their
 // conditions.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/GuardUtils.h"
 #include "llvm/Analysis/GuardUtils.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
if (UseWC) {
     auto *WC = B.CreateIntrinsic(Intrinsic::experimental_widenable_condition,
                                  {}, {}, nullptr, "widenable_cond");
     CheckBI->setCondition(B.CreateAnd(CheckBI->getCondition(), WC,
                                       "exiplicit_guard_cond"));
     assert(isWidenableBranch(CheckBI) && "Branch must be widenable.");
   }
 }
 
-
-void llvm::widenWidenableBranch(BranchInst *WidenableBR, Value *NewCond) {
+void llvm::widenWidenableBranch(BranchInst *WidenableBR, Value *NewCond,
+                                const LoopInfo &LI) {
   assert(isWidenableBranch(WidenableBR) && "precondition");
 
   // The tempting trivially option is to produce something like this:
   // br (and oldcond, newcond) where oldcond is assumed to contain a widenable
   // condition, but that doesn't match the pattern parseWidenableBranch expects
   // so we have to be more sophisticated.
 
   Use *C, *WC;
   BasicBlock *IfTrueBB, *IfFalseBB;
   parseWidenableBranch(WidenableBR, C, WC, IfTrueBB, IfFalseBB);
+#ifndef NDEBUG
+  bool IsLoopInvariantWidenableBR = false;
+  auto *L = LI.getLoopFor(WidenableBR->getParent());
+  if (L)
+    IsLoopInvariantWidenableBR =
+        L->isLoopInvariant(WidenableBR->getCondition());
+#endif
   if (!C) {
     // br (wc()), ... form
     IRBuilder<> B(WidenableBR);
     WidenableBR->setCondition(B.CreateAnd(NewCond, WC->get()));
   } else {
     // br (wc & C), ... form
     IRBuilder<> B(WidenableBR);
     C->set(B.CreateAnd(NewCond, C->get()));
     Instruction *WCAnd = cast<Instruction>(WidenableBR->getCondition());
     // Condition is only guaranteed to dominate branch
     WCAnd->moveBefore(WidenableBR);    
   }
+#ifndef NDEBUG
+  if (IsLoopInvariantWidenableBR) {
+    auto *L = LI.getLoopFor(WidenableBR->getParent());
+    // NB! This can also be loop-varying if we missed hoisting the IR out, which
+    // was infact loop-invariant. This would imply a pass-ordering issue and the
+    // assert should be dealt with as such.
+    assert(L->isLoopInvariant(WidenableBR->getCondition()) &&
+           "Loop invariant widenable condition made loop variant!");
+  }
+#endif
   assert(isWidenableBranch(WidenableBR) && "preserve widenabiliy");
 }
 
-void llvm::setWidenableBranchCond(BranchInst *WidenableBR, Value *NewCond) {
+void llvm::setWidenableBranchCond(BranchInst *WidenableBR, Value *NewCond,
+                                  const LoopInfo &LI) {
   assert(isWidenableBranch(WidenableBR) && "precondition");
 
   Use *C, *WC;
   BasicBlock *IfTrueBB, *IfFalseBB;
   parseWidenableBranch(WidenableBR, C, WC, IfTrueBB, IfFalseBB);
+#ifndef NDEBUG
+  bool IsLoopInvariantWidenableBR = false;
+  auto *L = LI.getLoopFor(WidenableBR->getParent());
+  if (L)
+    IsLoopInvariantWidenableBR =
+        L->isLoopInvariant(WidenableBR->getCondition());
+#endif
   if (!C) {
     // br (wc()), ... form
     IRBuilder<> B(WidenableBR);
     WidenableBR->setCondition(B.CreateAnd(NewCond, WC->get()));
   } else {
     // br (wc & C), ... form
     Instruction *WCAnd = cast<Instruction>(WidenableBR->getCondition());
     // Condition is only guaranteed to dominate branch
     WCAnd->moveBefore(WidenableBR);
     C->set(NewCond);
   }
+#ifndef NDEBUG
+  if (IsLoopInvariantWidenableBR) {
+    auto *L = LI.getLoopFor(WidenableBR->getParent());
+    // NB! This can also be loop-varying if we missed hoisting the IR out, which
+    // was infact loop-invariant. This would imply a pass-ordering issue and the
+    // assert should be dealt with as such.
+    assert(L->isLoopInvariant(WidenableBR->getCondition()) &&
+           "Loop invariant widenable condition made loop variant!");
+  }
+#endif
   assert(isWidenableBranch(WidenableBR) && "preserve widenabiliy");
 }