[CodeMoverUtils][WIP] Move code motion related checks from LICM to CodeMoverUtils

[RithikSharma]

Summary

This patch is a part of attempt to standardize code motion checks into one place. LoopFuse already uses CodeMoverUtils. This is a work in progress until we move all generic code motion checks into CodeMoverUtils. We started with moving less aggressive checks from LICM to CodeMoverUtils which can also be used by other code motion clients.

[RithikSharma]

llvm/lib/Transforms/Scalar/LICM.cpp

255

@Whitney I'm not sure is it okay to do all these deep changes but they all exist because this LICM invocation requires analysis from AnalysisResult. I request your comment on this.

[fhahn]

llvm/include/llvm/Analysis/LoopAnalysisManager.h

63 ↗

(On Diff #272400)

Requiring those extra analysis here requires a strong motivation I think, as I think each loop pass has to make sure they are preserved or recomputed.

llvm/lib/Transforms/Scalar/LICM.cpp

1380

In order to make the transition to more general utils easier I think it might be worth considering making PDT/DI optional in the various utils and separate it from making DI & PDT required for all users, which potentially has quite a big impact.

Also, I think LICM already uses MemorySSA to figure out if it is legal to move memory access out of the loop.

[fhahn]

Thanks for working on consolidating various utilities! Some initial comments inline.

[bmahjour]

llvm/include/llvm/Transforms/Utils/LoopUtils.h

200 ↗

(On Diff #272400)

fix formatting

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

333 ↗

(On Diff #272400)

query functions should not change the dominator trees. why const is being removed here?

413 ↗

(On Diff #272400)

why const is dropped?

[asbirlea]

Thank you for the patch!

This needs to be split up into multiple changes, there's too much going on in this patch to review as is.

Cleaning up the utilities, adding const, clang-format are all awesome and straight-forward to review. They should be separate NFCs.

Adding those dependencies (PDT and DepAnalysis) are not correct in this format, in particular in the loop pass manager. The implication there is that *all* loop passes in *any* loop pipeline are guaranteed to preserve those analyses. At least for PDT, I know that's not the case. I'm not familiar with DepAnalysis, but it looks like its scope overlaps with MemorySSA.
The constraints are different for Loop vs Function passes (LICM is a loop pass, LoopVectorize is a function pass), so again, the changes need to be reviewed separately.

[Whitney]

llvm/include/llvm/Analysis/LoopAnalysisManager.h

48 ↗

(On Diff #272400)

nit: follow alphabetic order.

163 ↗

(On Diff #272400)

recommend not to do formatting changes on lines not changed by you.
This is a general comment to all your changes, this can make your patch smaller.

llvm/lib/Transforms/Scalar/LICM.cpp

255

Can you please elaborate what you mean by deep changes? Do you mean adding adding PDT and DI in AR?
We should consider extending CodeMover utilities to take in more analyses, where some of them can be optional, and depending on the available analysis do the best judgement.
Or if MSSA can be used to cover all cases currently covered on CodeMover, then we should change CodeMover to use MSSA.

[RithikSharma]

llvm/lib/Transforms/Scalar/LICM.cpp

255

Thanks, yes, I was referring to all the side effect changes that are required because of adding PDT and DI in AR. MSSA checks look really promising I was planning to get them in.

[RithikSharma]

Many thanks @asbirlea and @fhahn for the review, it surely makes more sense to keep CodeMoverUtils flexible with the required analysis. I've made all the analysis in CodeMotionUtils optional so now we need not add them in LICM.

[asbirlea]

The issue with this change is that there is a lot of unnecessary work done now. Before, we could exit early to decide an instruction could never be hoisted/sunk. Now, we're removing all those early checks and only when actually trying to move get the "actually, you can't". I expect this to get a big compile-time penalty.
Could you do some testing and include results in the patch summary?

[RithikSharma]

In D82293#2118122, @asbirlea wrote:

The issue with this change is that there is a lot of unnecessary work done now. Before, we could exit early to decide an instruction could never be hoisted/sunk. Now, we're removing all those early checks and only when actually trying to move get the "actually, you can't". I expect this to get a big compile-time penalty.
Could you do some testing and include results in the patch summary?

Totally agreed with the delayed check issue and I've moved it to a place that is more analogous to the original checks. LICM has very extensive code motion checks, moving the generalized checks to a unified place will greatly help other passes to take advantage of them. Does the updated diff look satisfactory to you?

[asbirlea]

Yes, the diff look good. Could you clarify what isSafeToMove does? I don't see it in the included file, only isSafeToMoveBefore. Is there a dependent patch not linked?

[RithikSharma]

Many thanks, updated the parent revision.

[asbirlea]

This looks only dependent on D82290, not D82566.

llvm/lib/Transforms/Scalar/LICM.cpp

 #include "llvm/InitializePasses.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/CodeMoverUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include <algorithm>
 #include <utility>
 using namespace llvm;
 
 #define DEBUG_TYPE "licm"

 PreservedAnalyses LICMPass::run(Loop &L, LoopAnalysisManager &AM,
                                 LoopStandardAnalysisResults &AR, LPMUpdater &) {
   // For the new PM, we also can't use OptimizationRemarkEmitter as an analysis
   // pass.  Function analyses need to be preserved across loop transformations
   // but ORE cannot be preserved (see comment before the pass definition).
   OptimizationRemarkEmitter ORE(L.getHeader()->getParent());
 
   LoopInvariantCodeMotion LICM(LicmMssaOptCap, LicmMssaNoAccForPromotionCap);
   if (!LICM.runOnLoop(&L, &AR.AA, &AR.LI, &AR.DT, &AR.TLI, &AR.TTI, &AR.SE,
                       AR.MSSA, &ORE))
     return PreservedAnalyses::all();
 
   auto PA = getLoopPassPreservedAnalyses();
 
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<LoopAnalysis>();
   if (AR.MSSA)
if (LocSizeInBits <= InvariantSizeInBits &&
         DT->properlyDominates(II->getParent(), CurLoop->getHeader()))
       return true;
   }
 
   return false;
 }
 
 namespace {
-/// Return true if-and-only-if we know how to (mechanically) both hoist and
-/// sink a given instruction out of a loop.  Does not address legality
-/// concerns such as aliasing or speculation safety.
-bool isHoistableAndSinkableInst(Instruction &I) {
-  // Only these instructions are hoistable/sinkable.
-  return (isa<LoadInst>(I) || isa<StoreInst>(I) || isa<CallInst>(I) ||
-          isa<FenceInst>(I) || isa<CastInst>(I) || isa<UnaryOperator>(I) ||
-          isa<BinaryOperator>(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) || isa<FreezeInst>(I));
-}
 /// Return true if all of the alias sets within this AST are known not to
 /// contain a Mod, or if MSSA knows thare are no MemoryDefs in the loop.
 bool isReadOnly(AliasSetTracker *CurAST, const MemorySSAUpdater *MSSAU,
                 const Loop *L) {
   if (CurAST) {
     for (AliasSet &AS : *CurAST) {
       if (!AS.isForwardingAliasSet() && AS.isMod()) {
         return false;

 }
 
 bool llvm::canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
                               Loop *CurLoop, AliasSetTracker *CurAST,
                               MemorySSAUpdater *MSSAU,
                               bool TargetExecutesOncePerLoop,
                               SinkAndHoistLICMFlags *Flags,
                               OptimizationRemarkEmitter *ORE) {
-  // If we don't understand the instruction, bail early.
-  if (!isHoistableAndSinkableInst(I))
-    return false;
-
   MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr;
   if (MSSA)
     assert(Flags != nullptr && "Flags cannot be null.");
 
   // 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 sink/hoist volatile or ordered 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->hasMetadata(LLVMContext::MD_invariant_load))
       return true;
 
     if (LI->isAtomic() && !TargetExecutesOncePerLoop)
if (ORE && Invalidated && CurLoop->isLoopInvariant(LI->getPointerOperand()))
         return OptimizationRemarkMissed(
                    DEBUG_TYPE, "LoadWithLoopInvariantAddressInvalidated", LI)
                << "failed to move load with loop-invariant address "
                   "because the loop may invalidate its value";
       });
 
     return !Invalidated;
   } 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))
-      return false;
-
-    // Don't sink calls which can throw.
-    if (CI->mayThrow())
-      return false;
-
     using namespace PatternMatch;
     if (match(CI, m_Intrinsic<Intrinsic::assume>()))
       // Assumes don't actually alias anything or throw
       return true;
 
     if (match(CI, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
       // Widenable conditions don't actually alias anything or throw
       return true;
if (CurAST) {
         // other memory op, give up
         return false;
       (void)FI; // suppress unused variable warning
       assert(UniqueI == FI && "AS must contain FI");
       return true;
     } else // MSSAU
       return isOnlyMemoryAccess(FI, CurLoop, MSSAU);
   } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
-    if (!SI->isUnordered())
-      return false; // Don't sink/hoist volatile or ordered atomic store!
-
-    // We can only hoist a store that we can prove writes a value which is not
-    // read or overwritten within the loop.  For those cases, we fallback to
     // load store promotion instead.  TODO: We can extend this to cases where
     // there is exactly one write to the location and that write dominates an
     // arbitrary number of reads in the loop.
     if (CurAST) {
       auto &AS = CurAST->getAliasSetFor(MemoryLocation::get(SI));
 
       if (AS.isRef() || !AS.isMustAlias())
         // Quick exit test, handled by the full path below as well.
static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo,
   SafetyInfo.removeInstruction(&I);
   I.eraseFromParent();
 }
 
 static void moveInstructionBefore(Instruction &I, Instruction &Dest,
                                   ICFLoopSafetyInfo &SafetyInfo,
                                   MemorySSAUpdater *MSSAU,
                                   ScalarEvolution *SE) {
+  if (!isSafeToMoveBefore(I, Dest))
+      return;
   SafetyInfo.removeInstruction(&I);
   SafetyInfo.insertInstructionTo(&I, Dest.getParent());
   I.moveBefore(&Dest);
   if (MSSAU)
     if (MemoryUseOrDef *OldMemAcc = cast_or_null<MemoryUseOrDef>(
             MSSAU->getMemorySSA()->getMemoryAccess(&I)))
       MSSAU->moveToPlace(OldMemAcc, Dest.getParent(),
                          MemorySSA::BeforeTerminator);
   if (SE)