[LNICM] Fix crashing problem

[uint256_t]

Summary

This patch fixes the problems reported in https://reviews.llvm.org/D107219.
Two crashed cases are mentioned there:

1. LNICM tries to sink an instruction whose users are used in the current loop, and crash.
2. LNICM tries to sink an instruction whose (PHI) user prevents from sinking for some reasons, and crash.

[uabelho]

I've verified that this patch solves the crash I saw.

As for the actual fix, I don't know the code so someone familiar with LICM should review it.

Thanks!

[fhahn]

Could you please describe the issue and fix in the pat h description? Is there anything we can do to proactively check for similar issues in the LICM code? Originally there were very few places which required special handling for the loop-nest mode, but now it seems more widespread changes might be necessary.

llvm/test/Transforms/LICM/lnicm-crash.ll

4

it would be good to check for something other than just the return code in this test. Also, can you clean up the basic block names and maybe get rid of the unreachable?

[uint256_t]

llvm/test/Transforms/LICM/lnicm-crash.ll

4

I was forgetting to clean up this test case. Actually this is the original test case (from https://reviews.llvm.org/D107219) to reproduce a crash.
I'll clean up the block names and unreachables. Thank you.

[uint256_t]

Created a new revision. I think this is not a widespread change. What you do think @fhahn?

llvm/lib/Transforms/Scalar/LICM.cpp

cl::opt<unsigned> llvm::SetLicmMssaNoAccForPromotionCap(
     "licm-mssa-max-acc-promotion", cl::init(250), cl::Hidden,
     cl::desc("[LICM & MemorySSA] When MSSA in LICM is disabled, this has no "
              "effect. When MSSA in LICM is enabled, then this is the maximum "
              "number of accesses allowed to be present in a loop in order to "
              "enable memory promotion."));
 
 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
 static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
+                                  const Loop *OutermostLoop,
                                   const LoopSafetyInfo *SafetyInfo,
-                                  TargetTransformInfo *TTI, bool &FreeInLoop,
-                                  bool LoopNestMode);
+                                  TargetTransformInfo *TTI, bool &FreeInLoop);
 static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
                   BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo,
                   MemorySSAUpdater *MSSAU, ScalarEvolution *SE,
                   OptimizationRemarkEmitter *ORE);
 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
                  BlockFrequencyInfo *BFI, const Loop *CurLoop,
                  ICFLoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU,
                  OptimizationRemarkEmitter *ORE);
for (BasicBlock::iterator II = BB->end(); II != BB->begin();) {
       }
 
       // Check to see if we can sink this instruction to the exit blocks
       // of the loop.  We can do this if the all users of the instruction are
       // outside of the loop.  In this case, it doesn't even matter if the
       // operands of the instruction are loop invariant.
       //
       bool FreeInLoop = false;
-      bool LoopNestMode = OutermostLoop != nullptr;
       if (!I.mayHaveSideEffects() &&
-          isNotUsedOrFreeInLoop(I, LoopNestMode ? OutermostLoop : CurLoop,
-                                SafetyInfo, TTI, FreeInLoop, LoopNestMode) &&
-          canSinkOrHoistInst(I, AA, DT, CurLoop, /*CurAST*/nullptr, MSSAU, true,
-                             &Flags, ORE)) {
+          isNotUsedOrFreeInLoop(I, CurLoop, OutermostLoop, SafetyInfo, TTI,
+                                FreeInLoop) &&
+          canSinkOrHoistInst(I, AA, DT, CurLoop, /*CurAST*/ nullptr, MSSAU,
+                             true, &Flags, ORE)) {
         if (sink(I, LI, DT, BFI, CurLoop, SafetyInfo, MSSAU, ORE)) {
           if (!FreeInLoop) {
             ++II;
             salvageDebugInfo(I);
             eraseInstruction(I, *SafetyInfo, MSSAU);
           }
           Changed = true;
         }

 
 /// Return true if the only users of this instruction are outside of
 /// the loop. If this is true, we can sink the instruction to the exit
 /// blocks of the loop.
 ///
 /// We also return true if the instruction could be folded away in lowering.
 /// (e.g.,  a GEP can be folded into a load as an addressing mode in the loop).
 static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
+                                  const Loop *OutermostLoop,
                                   const LoopSafetyInfo *SafetyInfo,
-                                  TargetTransformInfo *TTI, bool &FreeInLoop,
-                                  bool LoopNestMode) {
+                                  TargetTransformInfo *TTI, bool &FreeInLoop) {
   const auto &BlockColors = SafetyInfo->getBlockColors();
-  bool IsFree = isFreeInLoop(I, CurLoop, TTI);
+  const bool LoopNestMode = OutermostLoop != nullptr;
+  bool IsFree = isFreeInLoop(I, LoopNestMode ? OutermostLoop : CurLoop, TTI);
   for (const User *U : I.users()) {
     const Instruction *UI = cast<Instruction>(U);
     if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
       const BasicBlock *BB = PN->getParent();
       // We cannot sink uses in catchswitches.
       if (isa<CatchSwitchInst>(BB->getTerminator()))
         return false;
 
       // We need to sink a callsite to a unique funclet.  Avoid sinking if the
       // phi use is too muddled.
       if (isa<CallInst>(I))
         if (!BlockColors.empty() &&
             BlockColors.find(const_cast<BasicBlock *>(BB))->second.size() != 1)
           return false;
 
       if (LoopNestMode) {
         while (isa<PHINode>(UI) && UI->hasOneUser() &&
                UI->getNumOperands() == 1) {
-          if (!CurLoop->contains(UI))
+          if (CurLoop == OutermostLoop && CurLoop->contains(UI))
+            break;
+          if (!OutermostLoop->contains(UI))
             break;
           UI = cast<Instruction>(UI->user_back());
         }
       }
     }
 
-    if (CurLoop->contains(UI)) {
+    if ((LoopNestMode ? OutermostLoop : CurLoop)->contains(UI)) {
       if (IsFree) {
         FreeInLoop = true;
         continue;
       }
       return false;
     }
   }
   return true;

llvm/test/Transforms/LICM/lnicm-crash.ll

+; RUN: opt -passes='loop-mssa(licm)' -S %s
+; RUN: opt -passes='loop-mssa(lnicm)' -S %s
+
+define void @main() {
+entry:
+  br label %for.body1143
+
+land.rhs1135:                                     ; preds = %for.body1143
+  %v_299.017 = phi i40 [ %0, %for.body1143 ]
+  br i1 true, label %land.rhs1135.for.cond.cleanup1952_crit_edge, label %for.body1143
+
+for.body1143:                                     ; preds = %land.rhs1135, %entry
+  %0 = select i1 undef, i40 undef, i40 253841517325
+  br i1 true, label %for.body1143.for.cond.cleanup1952_crit_edge, label %land.rhs1135
+
+for.body1143.for.cond.cleanup1952_crit_edge:      ; preds = %for.body1143
+  %split = phi i40 [ %0, %for.body1143 ]
+  unreachable
+
+land.rhs1135.for.cond.cleanup1952_crit_edge:      ; preds = %land.rhs1135
+  %split1 = phi i40 [ %v_299.017, %land.rhs1135 ]
+  unreachable
+}