isInductionPHI - Add some safety checks

[syzaara]

Summary

This adds some safety checks into isInductionPHI so that users calling isInductionPHI do not need to do their own checks before calling the function.

[nickdesaulniers]

Untested, but LGTM; thanks for this cleanup!

[syzaara]

In D129653#3648500, @nickdesaulniers wrote:

Untested, but LGTM; thanks for this cleanup!

I'm not quite sure how to test this. I could test it through my use case in rewriteLoopExitValues for which I have tests already comitted (so it's more of an NFC). Or, it could be through some unit tests for isInductionPHI itself, I see tests in llvm/unittests/Analysis/IVDescriptorsTest.cpp. But these checks seem too trivial to add unit tests for. Is it okay to commit this without further testing?

[fhahn]

llvm/lib/Analysis/IVDescriptors.cpp

1521

This should never be called with Phi being null.

1546

This is overly restrictive, whether the loop has a pre-header or not shouldn't impact whether a phi is an induction or now.

[syzaara]

llvm/lib/Analysis/IVDescriptors.cpp

1546

On the line below, we query for AR->getLoop()->getLoopPreheader(). If it turns out that this is null, we will see a crash. I thought adding this would be safer rather than restrictive.

[nickdesaulniers]

llvm/lib/Analysis/IVDescriptors.cpp

1546

maybe Phi::getIncomingValueForBlock should return nullptr if passed nullptr?

[syzaara]

llvm/lib/Analysis/IVDescriptors.cpp

1546

Yes, the other option is it move this check into Phi::getIncomingValueForBlock. @fhahn would that be more preferable?

[nickdesaulniers]

llvm/lib/Analysis/IVDescriptors.cpp

1521

Sounds like a good case for Phi being a & (and additional const) rather than a non-const ptr.

[nikic]

llvm/lib/Analysis/IVDescriptors.cpp

1546

It would be possible to relax this to getLoopPredecessor(). Without a loop predecessor we would have to guard against multiple starting values, which is probably not worthwhile?

[fhahn]

llvm/lib/Analysis/IVDescriptors.cpp

1546

If it turns out that this is null, we will see a crash

Oh yes, this also seems overly restrictive :/

The main thing we need an IR value to use as start value.

Given that we already require a single latch, checking that all non-latch incoming values are the same should be fairly straight-forward :)

Or maybe it is fine to pick any one of the non-latch incoming values as start value. We require the phi to form an AddRec, so it should have a single start value. Even if the incoming values are different IR values, they should evaluate to the same concrete value.

[syzaara]

llvm/lib/Analysis/IVDescriptors.cpp

1546

Ok, I can try picking any of the non-latch incoming values and test that out. Another option is what isFPInductionPHI does:

// The loop may have multiple entrances or multiple exits; we can analyze                 
// this phi if it has a unique entry value and a unique backedge value.                   
if (Phi->getNumIncomingValues() != 2)                                                     
  return false;                                                                           
Value *BEValue = nullptr, *StartValue = nullptr;
if (TheLoop->contains(Phi->getIncomingBlock(0))) {                                        
  BEValue = Phi->getIncomingValue(0);                                                     
  StartValue = Phi->getIncomingValue(1);                                                  
} else {
  assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
         "Unexpected Phi node in the loop");
  BEValue = Phi->getIncomingValue(1);                                                     
  StartValue = Phi->getIncomingValue(0);
}

[fhahn]

llvm/lib/Analysis/IVDescriptors.cpp

1546

That seems like a good first step. IMO it would also make sense for them both to share the same logic to get the start value.

[syzaara]

llvm/lib/Analysis/IVDescriptors.cpp

1521

This would require many changes to all the places we call isInductionPHI from. Can we add the null check for now, and create a separate PR for this change? @fhahn

[MaskRay]

llvm/lib/Analysis/IVDescriptors.cpp

1521

No. Many APIs don't support null pointer arguments. The existing implementation of isInductionPHI requires this invariance and this patch should not regress it.

[syzaara]

llvm/lib/Analysis/IVDescriptors.cpp

1546

@fhahn can you please take a look for review? Thank you!

[syzaara]

ping

llvm/lib/Analysis/IVDescriptors.cpp

 }
 
 ConstantInt *InductionDescriptor::getConstIntStepValue() const {
   if (isa<SCEVConstant>(Step))
     return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());
   return nullptr;
 }
 
+// Check that the loop has a unique entry value and a unique backedge value and
+// initialize StartValue and BEValue with these values from the Phi.
+static bool getStartAndBEValues(Value *&StartValue, Value *&BEValue,
+                                const Loop *TheLoop, PHINode *Phi) {
+  // We can analyze this phi if it has a unique entry value and a unique
+  // backedge value.
+  if (Phi->getNumIncomingValues() != 2)
+    return false;
+  if (TheLoop->contains(Phi->getIncomingBlock(0))) {
+    BEValue = Phi->getIncomingValue(0);
+    StartValue = Phi->getIncomingValue(1);
+  } else {
+    assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
+           "Unexpected Phi node in the loop");
+    BEValue = Phi->getIncomingValue(1);
+    StartValue = Phi->getIncomingValue(0);
+  }
+  return true;
+}
+
 bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop,
                                            ScalarEvolution *SE,
                                            InductionDescriptor &D) {
 
   // Here we only handle FP induction variables.
   assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");
 
   if (TheLoop->getHeader() != Phi->getParent())
     return false;
 
   // The loop may have multiple entrances or multiple exits; we can analyze
   // this phi if it has a unique entry value and a unique backedge value.
   if (Phi->getNumIncomingValues() != 2)
     return false;
   Value *BEValue = nullptr, *StartValue = nullptr;
-  if (TheLoop->contains(Phi->getIncomingBlock(0))) {
-    BEValue = Phi->getIncomingValue(0);
-    StartValue = Phi->getIncomingValue(1);
-  } else {
-    assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&
-           "Unexpected Phi node in the loop");
-    BEValue = Phi->getIncomingValue(1);
-    StartValue = Phi->getIncomingValue(0);
-  }
-
+  if (!getStartAndBEValues(StartValue, BEValue, TheLoop, Phi))
+    return false;
   BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue);
   if (!BOp)
     return false;
 
   Value *Addend = nullptr;
   if (BOp->getOpcode() == Instruction::FAdd) {
     if (BOp->getOperand(0) == Phi)
       Addend = BOp->getOperand(1);
bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop,
 
   return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR);
 }
 
 bool InductionDescriptor::isInductionPHI(
     PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE,
     InductionDescriptor &D, const SCEV *Expr,
     SmallVectorImpl<Instruction *> *CastsToIgnore) {
+
+  if (TheLoop->getHeader() != Phi->getParent())
+    return false;
+
   Type *PhiTy = Phi->getType();
   // We only handle integer and pointer inductions variables.
   if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
     return false;
 
   // Check that the PHI is consecutive.
   const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
 
   if (!AR) {
     LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
     return false;
   }
 
   if (AR->getLoop() != TheLoop) {
     // FIXME: We should treat this as a uniform. Unfortunately, we
     // don't currently know how to handled uniform PHIs.
     LLVM_DEBUG(
         dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
     return false;
   }
 
-  Value *StartValue =
-      Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
+  Value *BEValue = nullptr, *StartValue = nullptr;
+  if (!getStartAndBEValues(StartValue, BEValue, TheLoop, Phi))
+    return false;
 
   BasicBlock *Latch = AR->getLoop()->getLoopLatch();
   if (!Latch)
     return false;
 
   const SCEV *Step = AR->getStepRecurrence(*SE);
   // Calculate the pointer stride and check if it is consecutive.
   // The stride may be a constant or a loop invariant integer value.

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.
-static 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;
-  return InductionDescriptor::isInductionPHI(Phi, L, SE, ID);
-}
-
 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 (!checkIsIndPhi(IndPhi, L, SE, ID))
+            if (!InductionDescriptor::isInductionPHI(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 != PN && !checkIsIndPhi(Phi, L, SE, ID))
+                  if (!Phi)
+                    return true;
+                  if (Phi != PN && !InductionDescriptor::isInductionPHI(Phi, L, SE, ID))
                     return true;
                   return false;
                 }))
               continue;
             if (B != ID.getInductionBinOp())
               continue;
           }
         }