[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

5

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

5

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::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 LoopSafetyInfo *SafetyInfo,
                                   TargetTransformInfo *TTI, bool &FreeInLoop,
-                                  bool LoopNestMode);
+                                  const Loop *LoopNestCurLoop);
 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();) {
       // 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)) {
+                                SafetyInfo, TTI, FreeInLoop,
+                                LoopNestMode ? CurLoop : nullptr) &&
+          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;
         }

 /// 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 LoopSafetyInfo *SafetyInfo,
                                   TargetTransformInfo *TTI, bool &FreeInLoop,
-                                  bool LoopNestMode) {
+                                  const Loop *LoopNestCurLoop) {
   const auto &BlockColors = SafetyInfo->getBlockColors();
   bool IsFree = isFreeInLoop(I, 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) {
+      // In loop nest mode, CurLoop is always the outermost loop.
+      // So the actual current loop is given as LoopNestCurLoop.
+      if (LoopNestCurLoop) {
+        // Skip PHI chain inside the loop nest that may have been created by
+        // lcssa pass.
         while (isa<PHINode>(UI) && UI->hasOneUser() &&
                UI->getNumOperands() == 1) {
+          // If UI is inside the current loop, return false.
+          if (LoopNestCurLoop->contains(UI))
+            return false;
+          // If UI is outside the loop nest, stop skipping.
           if (!CurLoop->contains(UI))
             break;
           UI = cast<Instruction>(UI->user_back());
         }
+        // If UI is a PHI that prevents sinking, return false.
+        if (isa<PHINode>(UI) && (!UI->hasOneUser() || UI->getNumOperands() > 1))
+          return false;
       }
     }
 
     if (CurLoop->contains(UI)) {
       if (IsFree) {
         FreeInLoop = true;
         continue;
       }

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

+; RUN: opt -passes='loop-mssa(licm)' -S %s | FileCheck %s --check-prefixes CHECK
+; RUN: opt -passes='loop-mssa(lnicm)' -S %s | FileCheck %s --check-prefixes CHECK
+
+define void @main() {
+entry:
+  br label %for.body
+
+for.body:
+  %0 = select i1 undef, i40 undef, i40 253841517325
+  br i1 true, label %for.end, label %for.body2
+
+for.body2:
+  %v_299.017 = phi i40 [ %0, %for.body ]
+  br i1 true, label %for.end2, label %for.body
+
+; CHECK: for.end:
+; CHECK-NEXT: [[SPLIT:%.*]] = phi i40 [ undef, %for.body ]
+for.end:
+  %split = phi i40 [ %0, %for.body ]
+  br label %end
+
+; CHECK: for.end2:
+; CHECK-NEXT: [[SPLIT1:%.*]] = phi i40 [ undef, %for.body2 ]
+for.end2:
+  %split1 = phi i40 [ %v_299.017, %for.body2 ]
+  br label %end
+
+end:
+  ret void
+}

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

+; RUN: opt -passes='function(loop-mssa(licm,loop-rotate,loop-deletion,lnicm))' -S %s | FileCheck %s --check-prefixes CHECK
+
+target datalayout = "n16:32"
+
+@f.a = external dso_local global i32, align 1
+@f.c = external dso_local global i16*, align 1
+
+define void @f() {
+entry:
+  br label %for.cond
+
+for.cond:
+  br label %lbl1
+
+; CHECK-LABEL: lbl1
+; CHECK: [[LOAD:%.*]] = load i32, i32* @f.a, align 1
+; CHECK: [[CONV:%.*]] = trunc i32 [[LOAD]] to i16
+lbl1:
+  %0 = load i16*, i16** @f.c, align 1
+  store i16 0, i16* %0, align 1
+  br label %lbl2
+
+lbl2:
+  br label %for.cond1
+
+for.cond1:
+  %tobool = icmp ne i16 undef, 0
+  br i1 %tobool, label %for.body, label %for.cond3
+
+for.body:
+  br i1 undef, label %lbl1, label %if.end
+
+if.end:
+  br label %for.cond1
+
+for.cond3:
+  br i1 false, label %for.body4, label %for.end5
+
+for.body4:
+  %1 = load i32, i32* @f.a, align 1
+  %conv = trunc i32 %1 to i16
+  store i16 %conv, i16* undef, align 1
+  br label %lbl2
+
+for.end5:
+  br label %for.cond
+}
+