[LICM] Untangle some of the logic in LICM canSinkOrHoistInst

[trentxintong]

Summary

This patch fixes 2 problems.

• For some instructions that work on SSA values, we check isSafeToExecuteUnconditionally twice in case of hoisting. This is unnecessary.

• For the same set of instructions that work on SSA values, we fail to sink them if they can not meet conditions in isSafeToExecuteUnconditionally. This is a missed opportunity, we can sink these instructions (with no side effects) to the dominated exit blocks, even they do not meet the conditions in isSafeToExecuteUnconditionally. I added a test to demostrate this.

[danielcdh]

lib/Transforms/Scalar/LICM.cpp

366

isSafeToExecuteUnconditionally will not be called in this function, is it safe?

422

isSafeToExecuteUnconditionally was called twice (without the patch):

• once in canSinkOrHoistInst, with CtxI=nullptr
• once here, with Ctxl=CurLoop->getLoopPreheader()->getTerminator()

I'm not quite familiar with isSafeToExecuteUnconditionally, but looks to me different CtxI may have different meaning to check? Or am I missing something?

[mkuper]

I'm a bit confused about the distinction between "legal" and "safe". I'd assume them to mean the same thing.

lib/Transforms/Scalar/LICM.cpp

422

Passing CtxI == nullptr is conservative w.r.t any other CtxI, so that looks like it should be fine.

[trentxintong]

lib/Transforms/Scalar/LICM.cpp

366

I think it is safe.

This is the way I see LICM in case of sinking.

Say originally, the sunk instruction is InstructionX in BasicBlockX

Is there a way we sink the instruction to some exit blocks where the instruction is used and the exit block could get executed even the BBX does not. (If thats the case we may have a problem as its not safe to speculate the instruction then). From what I see, we cant, because if we use InstructionX in this exit block in a special _single incoming value_ phi node, BBX must dominate this exit block. This means by the time we execute the exit block, BBX must have been executed already.

NOTE: There is the case of the block not dominating the exit block where the value is used, this is done by Phi nodes with multiple incoming value in the exit block. Then we would not sink this value. This is checked in isNotUsedInLoop.

[trentxintong]

In D28241#634319, @mkuper wrote:

I'm a bit confused about the distinction between "legal" and "safe". I'd assume them to mean the same thing.

By "legal" I mean the instructions in question is loop invariant, i.e. every iteration of the loop, same value is produced.

By "safe" I mean its safe to speculate the instruction, i.e. the compiler will not create a program that faults given a program that does not fault. In case of hoisting, we can guarantee so by either of the isSafeToSpeculativelyExecute or isGuaranteedToExecute.

I feel word choices can be improved. "Legal" ==> "Loop Invariant" and "Safe" ==> "Safe To Execute Unconditionally"

[trentxintong]

Rework the sinking and hoisting logic a bit more. And also take into existing
suggestions.

[trentxintong]

I realized what i want to achieve can be done much simpler.

[trentxintong]

@hfinkel can you please confirm this is correct. Basically, I do not think we need to check for isSafeToExecuteUnconditionally for the set of SSA instructions we handle when we are sinking.

[hfinkel]

In D28241#639213, @trentxintong wrote:

@hfinkel can you please confirm this is correct. Basically, I do not think we need to check for isSafeToExecuteUnconditionally for the set of SSA instructions we handle when we are sinking.

Sinking into the exit block should be safe, subject to aliasing considerations for memory accesses, even for instructions not safe to speculate, so long as it is a dedicated exit (i.e. LI->hasDedicatedExits() returns true).

include/llvm/Transforms/Utils/LoopUtils.h

 
 /// Helper to consistently add the set of standard passes to a loop pass's \c
 /// AnalysisUsage.
 ///
 /// All loop passes should call this as part of implementing their \c
 /// getAnalysisUsage.
 void getLoopAnalysisUsage(AnalysisUsage &AU);
 
-/// Returns true if the hoister and sinker can handle this instruction.
-/// If SafetyInfo is null, we are checking for sinking instructions from
-/// preheader to loop body (no speculation).
-/// If SafetyInfo is not null, we are checking for hoisting/sinking
-/// instructions from loop body to preheader/exit. Check if the instruction
-/// can execute specultatively.
-///
+/// Return true if its safe to hoist or sink the instruction.
 bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
-                        Loop *CurLoop, AliasSetTracker *CurAST,
-                        LoopSafetyInfo *SafetyInfo);
+                        Loop *CurLoop, AliasSetTracker *CurAST);
 }
 
 #endif

lib/Transforms/Scalar/LICM.cpp

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.
     //
     if (isNotUsedInLoop(I, CurLoop, SafetyInfo) &&
-        canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo)) {
+        canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST)) {
       ++II;
       Changed |= sink(I, LI, DT, CurLoop, CurAST, SafetyInfo);
     }
   }
   return Changed;
 }
 
 /// Walk the specified region of the CFG (defined by all blocks dominated by
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
         continue;
       }
 
       // Try hoisting the instruction out to the preheader.  We can only do this
       // if all of the operands of the instruction are loop invariant and if it
       // is safe to hoist the instruction.
       //
       if (CurLoop->hasLoopInvariantOperands(&I) &&
-          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo) &&
+          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST) &&
           isSafeToExecuteUnconditionally(
               I, DT, CurLoop, SafetyInfo,
               CurLoop->getLoopPreheader()->getTerminator()))
         Changed |= hoist(I, DT, CurLoop, SafetyInfo);
     }
 
   const std::vector<DomTreeNode *> &Children = N->getChildren();
   for (DomTreeNode *Child : Children)
     Changed |= hoistRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
   return Changed;
 }
void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop) {
   Function *Fn = CurLoop->getHeader()->getParent();
   if (Fn->hasPersonalityFn())
     if (Constant *PersonalityFn = Fn->getPersonalityFn())
       if (isFuncletEHPersonality(classifyEHPersonality(PersonalityFn)))
         SafetyInfo->BlockColors = colorEHFunclets(*Fn);
 }
 
 bool llvm::canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
-                              Loop *CurLoop, AliasSetTracker *CurAST,
-                              LoopSafetyInfo *SafetyInfo) {
+                              Loop *CurLoop, AliasSetTracker *CurAST) {
   // Loads have extra constraints we have to verify before we can hoist them.
   if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
     if (!LI->isUnordered())
       return false; // Don't hoist volatile/atomic loads!
 
     // Loads from constant memory are always safe to move, even if they end up
     // in the same alias set as something that ends up being modified.
     if (AA->pointsToConstantMemory(LI->getOperand(0)))
if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
     }
 
     // FIXME: This should use mod/ref information to see if we can hoist or
     // sink the call.
 
     return false;
   }
 
-  // Only these instructions are hoistable/sinkable.
-  if (!isa<BinaryOperator>(I) && !isa<CastInst>(I) && !isa<SelectInst>(I) &&
-      !isa<GetElementPtrInst>(I) && !isa<CmpInst>(I) &&
-      !isa<InsertElementInst>(I) && !isa<ExtractElementInst>(I) &&
-      !isa<ShuffleVectorInst>(I) && !isa<ExtractValueInst>(I) &&
-      !isa<InsertValueInst>(I))
-    return false;
-
-  // SafetyInfo is nullptr if we are checking for sinking from preheader to
-  // loop body. It will be always safe as there is no speculative execution.
-  if (!SafetyInfo)
+  // These instructions work on SSA values and have not side effects, and
+  // known to be moveable.
+  if (isa<BinaryOperator>(I) || isa<CastInst>(I) || isa<SelectInst>(I) ||
+      isa<GetElementPtrInst>(I) || isa<CmpInst>(I) ||
+      isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) ||
+      isa<ShuffleVectorInst>(I) || isa<ExtractValueInst>(I) ||
+      isa<InsertValueInst>(I))
     return true;
 
-  // TODO: Plumb the context instruction through to make hoisting and sinking
-  // more powerful. Hoisting of loads already works due to the special casing
-  // above.
-  return isSafeToExecuteUnconditionally(I, DT, CurLoop, SafetyInfo, nullptr);
+  // We do not know much about this instruction, return conservatively.
+  return false;
 }
 
 /// Returns true if a PHINode is a trivially replaceable with an
 /// Instruction.
 /// This is true when all incoming values are that instruction.
 /// This pattern occurs most often with LCSSA PHI nodes.
 ///
 static bool isTriviallyReplacablePHI(const PHINode &PN, const Instruction &I) {

lib/Transforms/Scalar/LoopSink.cpp

std::stable_sort(ColdLoopBBs.begin(), ColdLoopBBs.end(),
                      return BFI.getBlockFreq(A) < BFI.getBlockFreq(B);
                    });
 
   // Traverse preheader's instructions in reverse order becaue if A depends
   // on B (A appears after B), A needs to be sinked first before B can be
   // sinked.
   for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) {
     Instruction *I = &*II++;
-    if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, nullptr))
+    if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST))
       continue;
     if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI))
       Changed = true;
   }
 
   if (Changed && SE)
     SE->forgetLoopDispositions(&L);
   return Changed;

test/Transforms/LICM/sinking.ll

 lab60:
 ; CHECK: lab60:
 ; CHECK: store
 ; CHECK-NEXT: indirectbr
   store i32 2145244101, i32* undef, align 4
   indirectbr i8* undef, [label %lab21, label %lab19]
 }
 
+; We can sink the sdiv in the loop here as it has no visible
+; side effect.
+; CHECK: define i32 @sink_sdiv
+define i32 @sink_sdiv(i32, i32, i32)  {
+  %4 = icmp slt i32 0, %0
+  br i1 %4, label %preheader, label %ret
+
+preheader:
+  br label %header
+
+header:
+  %5 = phi i32 [ 0, %preheader ], [ %7, %latch ]
+  %6 = sdiv i32 %1, %2
+  call void @g()
+  br label %latch
+
+latch:
+  %7 = add nsw i32 %5, 1
+  %8 = icmp slt i32 %7, %0
+  br i1 %8, label %header, label %exit
+
+exit:
+; CHECK: exit:
+; CHECK: sdiv
+  %lcssa = phi i32 [ %6, %latch ]
+  br label %ret
+
+ret:
+  %ret.lcssa = phi i32 [ %lcssa, %exit ], [ 0, %3 ]
+  ret i32 %ret.lcssa
+}
+
 declare void @f(i32*)
 
 declare void @g()