Refactor LICM pass in preparation for LoopSink pass.

[danielcdh]

Summary

LoopSink pass uses some common function in LICM. This patch refactor the LICM code to make it usable by LoopSink pass (https://reviews.llvm.org/D22778).

[danielcdh]

This is an obvious change, I will commit it without review.

[chandlerc]

In D24168#532233, @danielcdh wrote:

This is an obvious change, I will commit it without review.

So, in the code review where I asked for the change, I mentioned I had some comments that should be attached to it. So that might signify that it isn't fully obvious...

And once you *ask* for a pre-commit review, it seem much more polite to see it through. Comments inbound shortly.

[chandlerc]

lib/Transforms/Scalar/LICM.cpp

449–455

Why this change?

We try to avoid testing isa<T> just before we do a dyn_cast<T> because it duplicates work. So the other arrangement is in many ways much more common.

If you're worried about the performance of this code or just trying to make it more readable what goes where, there are perhaps better patterns that can be used, but I'm not sure which to suggest without understanding the motivation.

464

Any particular reason to make this change? It's not necessarily a bad change, but it seems surprising here.

530–531

Please prefer early return:

if (!SafetyInfo)
  return true;

// ...
return isSafeTo...

[danielcdh]

In D24168#532400, @chandlerc wrote:

In D24168#532233, @danielcdh wrote:

This is an obvious change, I will commit it without review.

So, in the code review where I asked for the change, I mentioned I had some comments that should be attached to it. So that might signify that it isn't fully obvious...

Indeed did not notice/understand that comment, sorry about that.

And once you *ask* for a pre-commit review, it seem much more polite to see it through. Comments inbound shortly.

As noted in the other review, I misunderstood that self-approving patch is common-practice, no mean to be rude, please don't take it personally.

lib/Transforms/Scalar/LICM.cpp

449–455

I remember I had a reason for that... But it's a long time ago, I could not think of it now...

I'm doing some more testing without hoisting it, if I still cannot find the justification, I'll revert this change.

464

This is not related to this patch, just found it easier to read thus went ahead with the change. I can back it out if you want.

[danielcdh]

refactor

[danielcdh]

update comment, which will be moved to header later.

[danielcdh]

ping...

[danielcdh]

ping^2 PTAL

[danielcdh]

ping...

[hfinkel]

lib/Transforms/Scalar/LICM.cpp

523

Why is this not returning a conservative answer?

[danielcdh]

lib/Transforms/Scalar/LICM.cpp

523

SafetyInfo will be non-null for LICM, and will be nullptr for LoopSink, which is always safe. Basically, I used this pointer to distinguish between LICM and LoopSink usage to reuse the code as much as possible without introduce new parameter to the API. Let me know if you think that is confusing:

• Shall I add comment to clarify here?
• Or shall I simply add a new parameter to indicate if it's for hoisting or sinking?

[chandlerc]

lib/Transforms/Scalar/LICM.cpp

523

This is a good question, it may just mean that "SafetyInfo" needs a better name or this needs a comment to explain why this is correct.

Alternatively, we could require that SafetyInfo is always provided.

[chandlerc]

lib/Transforms/Scalar/LICM.cpp

523

(sorry, crossing replies)

I think making it more clear that the difference is between *hoisting* and *sinking* would really help. That explains the reason you don't need to call isSafeToExecuteUnconditionally at all.

[danielcdh]

lib/Transforms/Scalar/LICM.cpp

523

Do you mean that I add a comment to the early return?

[hfinkel]

lib/Transforms/Scalar/LICM.cpp

523

I agree. This makes sense, but please add a comment here, and also a comment in LoopUtils.h for each relevant interface explaining that passing nullptr for SafetyInfo is for sinking.

[hfinkel]

lib/Transforms/Scalar/LICM.cpp

523

Yes. The comment before the early return should specifically point out that for sinking we don't need to check isSafeToExecuteUnconditionally.

[danielcdh]

update comments

[danielcdh]

Commends updated to LICM.cpp. This change does not affect other functions in LoopUtils.h. But when I move canSinkOrHoistInst to LoopUtils.h in the next patch, I'll have the updated comment there too.

[hfinkel]

LGTM

lib/Transforms/Scalar/LICM.cpp

440

sinking instruction from should be "sinking instructions from" or "sinking this instruction from"

[danielcdh]

update comment

[chandlerc]

(FWIW, LGTM to me too, thanks!)

[danielcdh]

Thanks for the reviews!

As this was original proposed by Chandler, I'll hold this until later today and see if he has more comment.

Hal, it would be great if you can also shed some lights on https://reviews.llvm.org/D22778 (I'll do a quick rebase now). Thanks!

lib/Transforms/Scalar/LICM.cpp

 static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
                                      const AAMDNodes &AAInfo,
                                      AliasSetTracker *CurAST);
 static Instruction *
 CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
                             const LoopInfo *LI,
                             const LoopSafetyInfo *SafetyInfo);
 static bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA,
-                               DominatorTree *DT, TargetLibraryInfo *TLI,
+                               DominatorTree *DT,
                                Loop *CurLoop, AliasSetTracker *CurAST,
                                LoopSafetyInfo *SafetyInfo);
 
 namespace {
 struct LoopInvariantCodeMotion {
   bool runOnLoop(Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT,
                  TargetLibraryInfo *TLI, ScalarEvolution *SE, bool DeleteAST);
 
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, TLI, CurLoop, CurAST, SafetyInfo)) {
+        canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo)) {
       ++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, TLI, CurLoop, CurAST, SafetyInfo) &&
+          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo) &&
           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)
void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop) {
   // personality routine.
   Function *Fn = CurLoop->getHeader()->getParent();
   if (Fn->hasPersonalityFn())
     if (Constant *PersonalityFn = Fn->getPersonalityFn())
       if (isFuncletEHPersonality(classifyEHPersonality(PersonalityFn)))
         SafetyInfo->BlockColors = colorEHFunclets(*Fn);
 }
 
-/// canSinkOrHoistInst - Return true if the hoister and sinker can handle this
-/// instruction.
+/// Returns true if the hoister and sinker can handle this instruction.
+/// If SafetyInfo is nullptr, we are checking for sinking instruction from
+/// preheader to loop body (no speculation).
+/// If SafetyInfo is not nullptr, we are checking for hoisting/sinking
+/// instructions from loop body to preheader/exit. Check if the instruction
+/// can execute specultatively.
 ///
-bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA, DominatorTree *DT,
-                        TargetLibraryInfo *TLI, Loop *CurLoop,
-                        AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo) {
+bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
+                        Loop *CurLoop, AliasSetTracker *CurAST,
+                        LoopSafetyInfo *SafetyInfo) {
   // 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)))
       return true;
     if (LI->getMetadata(LLVMContext::MD_invariant_load))
       return true;
 
     // Don't hoist loads which have may-aliased stores in loop.
     uint64_t Size = 0;
     if (LI->getType()->isSized())
       Size = I.getModule()->getDataLayout().getTypeStoreSize(LI->getType());
 
     AAMDNodes AAInfo;
     LI->getAAMetadata(AAInfo);
 
     return !pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo, CurAST);
   } else if (CallInst *CI = dyn_cast<CallInst>(&I)) {
     // Don't sink or hoist dbg info; it's legal, but not useful.
     if (isa<DbgInfoIntrinsic>(I))
bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
   // 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)
+    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);
 }
 
 /// 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) {
   for (const Value *IncValue : PN.incoming_values())