[LSR] Fix bug - check if loop has preheader before calling isInductionPHI

[syzaara]

Summary

Fix bug exposed by https://reviews.llvm.org/D125990, rewriteLoopExitValues calls InductionDescriptor::isInductionPHI which requires the PHI node to have an incoming edge from the loop preheader. This adds checks before calling InductionDescriptor::isInductionPHI to see that the loop has a preheader. Also did some refactoring.

[Meinersbur]

In the interest to not block @nathanchance with a crashing compiler, I suggest to commit as soon as possible. However, a complete patch would also include a regression test.

llvm/lib/Transforms/Utils/LoopUtils.cpp

1249

Please add a doxygen comment briefly describing what this is checking.

[nickdesaulniers]

Yes, please add a regression test. Thanks for a quick fix!

[syzaara]

Addressed review comments, added test.

[nickdesaulniers]

llvm/test/Transforms/LoopStrengthReduce/remove_scev_indvars.ll

97–123

via llvm-reduce, I was able to reduce this test case to:

define void @kernfs_path_from_node() {
entry:
  callbr void asm sideeffect "", "i"(i8* blockaddress(@kernfs_path_from_node, %while.body))
          to label %asm.fallthrough [label %while.body]

asm.fallthrough:                                  ; preds = %entry
  br label %while.body

while.body:                                       ; preds = %while.body, %asm.fallthrough, %entry
  %depth.04 = phi i32 [ %inc, %while.body ], [ 0, %asm.fallthrough ], [ 0, %entry ]
  %inc = add i32 %depth.04, 1
  br i1 false, label %while.end, label %while.body

while.end:                                        ; preds = %while.body
  %inc.lcssa = phi i32 [ %depth.04, %while.body ]
  store i32 %inc.lcssa, i32* null, align 4
  ret void
}

[nickdesaulniers]

llvm/lib/Transforms/Utils/LoopUtils.cpp

1249

This comment is not done yet. Please mark checkIsIndPhi as having static linkage.

1260–1262

could these three statements simply be:

return InductionDescriptor::isInductionPHI(Phi, L, SE, ID));

?

[syzaara]

Address review

[nickdesaulniers]

Please mark comments as "done" in phab once they're addressed.

llvm/lib/Transforms/Utils/LoopUtils.cpp

1249–1259

Regarding the comment, should any of these be sunk into the definition of InductionDescriptor::isInductionPHI?

For instance, it seems like InductionDescriptor::isInductionPHI probably should check that its pointer parameters are not nullptr. Other callers of InductionDescriptor::isInductionPHI could probably then remove their nullptr checks (if they have any).

Otherwise, if the !L->getLoopPreheader() and Phi->getParent() != L->getHeader() guards should NOT be sunk into the definition of InductionDescriptor::isInductionPHI, the added comment doesn't explain _why_ beyond if it is safe to call. _Why_?

For instance InductionDescriptor::isFPInductionPHI has a guard

if (TheLoop->getHeader() != Phi->getParent())
    return false;

_why_ doesn't InductionDescriptor::isInductionPHI? Perhaps it should?

[syzaara]

llvm/lib/Transforms/Utils/LoopUtils.cpp

1249–1259

I think it makes sense that these checks could be sink into isInductionPHI. As you said, isFPInductionPHI already checks for

TheLoop->getHeader() != Phi->getParent()

I think this can moved into isInductionPHI. Also since isInductionPHI calls:

Value *StartValue =
    Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());

It would make sense that we check that the loop has a preheader before passing a possible null value.

I can open a new PR to address this suggestion.

[nickdesaulniers]

llvm/lib/Transforms/Utils/LoopUtils.cpp

1249–1259

SGTM; please cc me for review.

llvm/lib/Transforms/Utils/LoopUtils.cpp

for (auto *BB : L->blocks())
     if (llvm::any_of(*BB, [](Instruction &I) {
           return I.mayHaveSideEffects();
         }))
       return false;
 
   return true;
 }
 
+/// Checks if it is safe to call InductionDescriptor::isInductionPHI for \p Phi,
+/// and returns true if this Phi is an induction phi in the loop. When
+/// isInductionPHI returns true, \p ID will be also be set by isInductionPHI.
+bool checkIsIndPhi(PHINode *Phi, Loop *L, ScalarEvolution *SE,
+                   InductionDescriptor &ID) {
+  if (!Phi)
+    return false;
+  if (!L->getLoopPreheader())
+    return false;
+  if (Phi->getParent() != L->getHeader())
+    return false;
+  if (!InductionDescriptor::isInductionPHI(Phi, L, SE, ID))
+    return false;
+  return true;
+}
+
 int llvm::rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
                                 ScalarEvolution *SE,
                                 const TargetTransformInfo *TTI,
                                 SCEVExpander &Rewriter, DominatorTree *DT,
                                 ReplaceExitVal ReplaceExitValue,
                                 SmallVector<WeakTrackingVH, 16> &DeadInsts) {
   // Check a pre-condition.
   assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
while ((PN = dyn_cast<PHINode>(BBI++))) {
         // unused in the loop, with the only use being the exit block PhiNode,
         // and the induction variable update binary operator.
         // The exit value can be replaced with the final value when it is cheap
         // to do so.
         if (ReplaceExitValue == UnusedIndVarInLoop) {
           InductionDescriptor ID;
           PHINode *IndPhi = dyn_cast<PHINode>(Inst);
           if (IndPhi) {
-            if (IndPhi->getParent() != L->getHeader())
-              continue;
-            // Do not consider non induction phis.
-            if (!InductionDescriptor::isInductionPHI(IndPhi, L, SE, ID))
+            if (!checkIsIndPhi(IndPhi, L, SE, ID))
               continue;
             // This is an induction PHI. Check that the only users are PHI
             // nodes, and induction variable update binary operators.
             if (llvm::any_of(Inst->users(), [&](User *U) {
                   if (!isa<PHINode>(U) && !isa<BinaryOperator>(U))
                     return true;
                   BinaryOperator *B = dyn_cast<BinaryOperator>(U);
                   if (B && B != ID.getInductionBinOp())
                     return true;
                   return false;
                 }))
               continue;
           } else {
             // If it is not an induction phi, it must be an induction update
             // binary operator with an induction phi user.
             BinaryOperator *B = dyn_cast<BinaryOperator>(Inst);
             if (!B)
               continue;
             if (llvm::any_of(Inst->users(), [&](User *U) {
                   PHINode *Phi = dyn_cast<PHINode>(U);
-                  if (!Phi)
+                  if (Phi != PN && !checkIsIndPhi(Phi, L, SE, ID))
                     return true;
-                  if (Phi->getParent() == L->getHeader()) {
-                    if (!InductionDescriptor::isInductionPHI(Phi, L, SE, ID))
-                      return true;
-                  }
                   return false;
                 }))
               continue;
             if (B != ID.getInductionBinOp())
               continue;
           }
         }
 

llvm/test/Transforms/LoopStrengthReduce/remove_scev_indvars.ll

 ; induction variables
 ; CHECK: %.lcssa221 = phi i32 [ %2, %for.cond6418 ]
   %.lcssa221 = phi i32 [ %2, %for.cond6418 ]
   ret void
 
 dead:                                             ; No predecessors!
   br label %for.cond6403
 }
+
+
+; Check that this doesn't crash
+%struct.kernfs_node = type { %struct.kernfs_node* }
+
+@kernfs_path_from_node_locked_kn_to = dso_local local_unnamed_addr global %struct.kernfs_node zeroinitializer, align 8
+@kernfs_path_from_node_locked___trans_tmp_1 = dso_local local_unnamed_addr global i32 0, align 4
+
+define dso_local void @kernfs_path_from_node() {
+entry:
+  callbr void asm sideeffect "", "i"(i8* blockaddress(@kernfs_path_from_node, %while.body))
+          to label %asm.fallthrough [label %while.body]
+
+asm.fallthrough:                                  ; preds = %entry
+  br label %while.body
+
+while.body:                                       ; preds = %entry, %asm.fallthrough, %while.body
+  %depth.04 = phi i32 [ %inc, %while.body ], [ undef, %asm.fallthrough ], [ undef, %entry ]
+  %to.03 = phi %struct.kernfs_node* [ %0, %while.body ], [ @kernfs_path_from_node_locked_kn_to, %asm.fallthrough ], [ @kernfs_path_from_node_locked_kn_to, %entry ]
+  %inc = add i32 %depth.04, 1
+  %parent = getelementptr inbounds %struct.kernfs_node, %struct.kernfs_node* %to.03, i64 0, i32 0
+  %0 = load %struct.kernfs_node*, %struct.kernfs_node** %parent, align 8
+  %tobool.not = icmp eq %struct.kernfs_node* %0, null
+  br i1 %tobool.not, label %while.end, label %while.body
+
+while.end:                                        ; preds = %while.body
+  %inc.lcssa = phi i32 [ %inc, %while.body ]
+  store i32 %inc.lcssa, i32* @kernfs_path_from_node_locked___trans_tmp_1, align 4
+  ret void
+}