Make promoteLoopAccessesToScalars independent of AliasSet [NFC]

[asbirlea]

Summary

The current promoteLoopAccessesToScalars method receives an AliasSet, but
the information used is in fact a list of Value*, known to must alias.
Create the list ahead of time to make this method independent of the AliasSet class.

While there is no functionality change, this adds overhead for creating
a set of Value*, when promotion would normally exit earlier.
This is meant to be as a first refactoring step in order to start replacing
AliasSetTracker with MemorySSA.
And while the end goal is to redesign LICM, the first few steps will focus on
adding MemorySSA as an alternative to the AliasSetTracker using most of the
existing functionality.

[sanjoy]

lib/Transforms/Scalar/LICM.cpp

306

I'd just remove this.

309

Can you see duplicates here? If not, I'd suggest changing this to a SmallVector (and pass in an ArrayRef to promoteLoopAccessesToScalars).

[sanjoy]

Actually, one good reason for switching to passing in a vector of pointers to promoteLoopAccessesToScalars is that we probably (?) want a deterministic order of insertion into LoopUses since that will influence what LoopPromoter does.

[asbirlea]

Remove/update comments.

[asbirlea]

lib/Transforms/Scalar/LICM.cpp

309

I'm not 100% sure if I can see duplicates, but the way I see the AliasSets being built it looks possible. The values are stored as a list in AliasSet:PointerRec.

The actual reason for keeping the PointerMustAliases as a set, is that in the alternative implementation I have (using MemorySSA) values can be deleted.
This happens to enable promotion after promotion.
In the AliasSetTracker, when this case comes up, there's the callback in LoopPromoter that updates the AliasSet. With MemSSA, something similar updates a SmallPtrSet<Value*>.

FWIW, I'm not planning to land this until I get the follow-up patch up for review and get input on both.

[sanjoy]

lib/Transforms/Scalar/LICM.cpp

304

The indent looks off here (clang-format should fix it).

307

LLVM style avoids { for single statement loops and if statements.

1037

Does this modify PointerMustAliases? If not, make this a const reference.

1047

I think this can introduce non-determinism since SmallPtrSet does not have a deterministic order. You'll need some other way to pick a canonical address (just passing it in explicitly is fine).

1135

Whitespace is off (but again, clang-format will fix this).

And the iteration order is not deterministic here either and this can produce non-deterministic output (via LoopUses). I'm not a 100% sure about the non-determinism, but we should use a stable iteration order unless we can prove that the output will be deterministic.

[asbirlea]

Address comments.

[asbirlea]

Remove comment.

[sanjoy]

lib/Transforms/Scalar/LICM.cpp

953

You could also add a getSetRef() (like getArrayRef()) method to SetVector to expose the contained set and pass that into LoopPromoter instead of changing LoopPromoter itself.

But this is fine too.

[asbirlea]

Thanks for the review!

lib/Transforms/Scalar/LICM.cpp

953

Noted as a future change.

1047

Changed to SmallSetVector.

1135

As above, SmallSetVector.

include/llvm/Transforms/Utils/LoopUtils.h

 /// ORE. It returns changed status.
 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
                  LoopSafetyInfo *, OptimizationRemarkEmitter *ORE);
 
 /// \brief Try to promote memory values to scalars by sinking stores out of
 /// the loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are
-/// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks
-/// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop,
-/// AliasSet information for all instructions of the loop and loop safety
-/// information as arguments. Diagnostics is emitted via \p ORE. It returns
-/// changed status.
-bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock *> &,
+/// loop invariant. It takes a set of must-alias values, Loop exit blocks
+/// vector, loop exit blocks insertion point vector, PredIteratorCache,
+/// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions
+/// of the loop and loop safety information as arguments.
+/// Diagnostics is emitted via \p ORE. It returns changed status.
+bool promoteLoopAccessesToScalars(SmallPtrSetImpl<Value *> &,
+                                  SmallVectorImpl<BasicBlock *> &,
                                   SmallVectorImpl<Instruction *> &,
                                   PredIteratorCache &, LoopInfo *,
                                   DominatorTree *, const TargetLibraryInfo *,
                                   Loop *, AliasSetTracker *, LoopSafetyInfo *,
                                   OptimizationRemarkEmitter *);
 
 /// \brief Computes safety information for a loop
 /// checks loop body & header for the possibility of may throw

lib/Transforms/Scalar/LICM.cpp

if (!HasCatchSwitch) {
       for (BasicBlock *ExitBlock : ExitBlocks)
         InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
 
       PredIteratorCache PIC;
 
       bool Promoted = false;
 
       // Loop over all of the alias sets in the tracker object.
-      for (AliasSet &AS : *CurAST)
+      for (AliasSet &AS : *CurAST) {
+        // We can promote this alias set if it has a store, if it is a "Must" alias
+        // set, if the pointer is loop invariant, and if we are not eliminating any
+        // volatile loads or stores.
+        if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
+            AS.isVolatile() || !L->isLoopInvariant(AS.begin()->getValue()))
+          continue;
+
+        assert(!AS.empty() &&
+          "Must alias set should have at least one pointer element in it!");
+
+        SmallPtrSet<Value *, 4> PointerMustAliases;
+        for (const auto &ASI : AS) {
+          PointerMustAliases.insert(ASI.getValue());
+        }
+
         Promoted |=
-            promoteLoopAccessesToScalars(AS, ExitBlocks, InsertPts, PIC, LI, DT,
+            promoteLoopAccessesToScalars(PointerMustAliases,
+                                         ExitBlocks, InsertPts, PIC, LI, DT,
                                          TLI, L, CurAST, &SafetyInfo, ORE);
+      }
 
       // Once we have promoted values across the loop body we have to
       // recursively reform LCSSA as any nested loop may now have values defined
       // within the loop used in the outer loop.
       // FIXME: This is really heavy handed. It would be a bit better to use an
       // SSAUpdater strategy during promotion that was LCSSA aware and reformed
       // it as it went.
       if (Promoted)
static bool isSafeToExecuteUnconditionally(Instruction &Inst,
   }
 
   return GuaranteedToExecute;
 }
 
 namespace {
 class LoopPromoter : public LoadAndStorePromoter {
   Value *SomePtr; // Designated pointer to store to.
   SmallPtrSetImpl<Value *> &PointerMustAliases;
   SmallVectorImpl<BasicBlock *> &LoopExitBlocks;
   SmallVectorImpl<Instruction *> &LoopInsertPts;
   PredIteratorCache &PredCache;
   AliasSetTracker &AST;
   LoopInfo &LI;
   DebugLoc DL;
   int Alignment;
   bool UnorderedAtomic;

 } // end anon namespace
 
 /// Try to promote memory values to scalars by sinking stores out of the
 /// loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are
 /// loop invariant.
 ///
 bool llvm::promoteLoopAccessesToScalars(
-    AliasSet &AS, SmallVectorImpl<BasicBlock *> &ExitBlocks,
+    SmallPtrSetImpl<Value *> &PointerMustAliases,
+    SmallVectorImpl<BasicBlock *> &ExitBlocks,
     SmallVectorImpl<Instruction *> &InsertPts, PredIteratorCache &PIC,
     LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI,
     Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo,
     OptimizationRemarkEmitter *ORE) {
   // Verify inputs.
   assert(LI != nullptr && DT != nullptr && CurLoop != nullptr &&
          CurAST != nullptr && SafetyInfo != nullptr &&
          "Unexpected Input to promoteLoopAccessesToScalars");
 
-  // We can promote this alias set if it has a store, if it is a "Must" alias
-  // set, if the pointer is loop invariant, and if we are not eliminating any
-  // volatile loads or stores.
-  if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
-      AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue()))
-    return false;
-
-  assert(!AS.empty() &&
-         "Must alias set should have at least one pointer element in it!");
-
-  Value *SomePtr = AS.begin()->getValue();
+  Value *SomePtr = *PointerMustAliases.begin();
   BasicBlock *Preheader = CurLoop->getLoopPreheader();
 
   // It isn't safe to promote a load/store from the loop if the load/store is
   // conditional.  For example, turning:
   //
   //    for () { if (c) *P += 1; }
   //
   // into:
bool llvm::promoteLoopAccessesToScalars(
   // is different from the store being guaranteed to execute. For instance,
   // if an exception is thrown on the first iteration of the loop, the original
   // store is never executed, but the exit blocks are not executed either.
 
   bool DereferenceableInPH = false;
   bool SafeToInsertStore = false;
 
   SmallVector<Instruction *, 64> LoopUses;
-  SmallPtrSet<Value *, 4> PointerMustAliases;
 
   // We start with an alignment of one and try to find instructions that allow
   // us to prove better alignment.
   unsigned Alignment = 1;
   // Keep track of which types of access we see
   bool SawUnorderedAtomic = false; 
   bool SawNotAtomic = false;
   AAMDNodes AATags;
if (!isa<AllocaInst>(Object)) {
         return false;
       IsKnownNonEscapingObject = true;
     }
   }
 
   // Check that all of the pointers in the alias set have the same type.  We
   // cannot (yet) promote a memory location that is loaded and stored in
   // different sizes.  While we are at it, collect alignment and AA info.
-  for (const auto &ASI : AS) {
-    Value *ASIV = ASI.getValue();
-    PointerMustAliases.insert(ASIV);
-
+  for (Value * ASIV : PointerMustAliases) {
     // Check that all of the pointers in the alias set have the same type.  We
     // cannot (yet) promote a memory location that is loaded and stored in
     // different sizes.
     if (SomePtr->getType() != ASIV->getType())
       return false;
 
     for (User *U : ASIV->users()) {
       // Ignore instructions that are outside the loop.