[LICM] Break the assumption that the sub loops cannot be modified by other loop passes

[haicheng]

Summary

LICM assumes that the sub loops cannot be modified by other loop passes (See the deleted comment starting with "What if"). It is true for the current loop optimization pipeline. However, if the pipeline is changed, the assumption may not be true (e.g. test/Transforms/LICM/AliasSetMemSet.ll which is discussed in this thread).

This patch first tests if there are more than one loop passes run together. If it is true, it calculates the AST from the scratch without using the LoopToAliasSetMap cache. This patch has no impact on either function or compilation time for the current loop optimization pipeline.

[mssimpso]

Haicheng, would it be difficult construct a test case here that demonstrates the caching problem? Perhaps something like the memset example that exposed the issue?

[haicheng]

In D17370#356139, @mssimpso wrote:

Haicheng, would it be difficult construct a test case here that demonstrates the caching problem? Perhaps something like the memset example that exposed the issue?

I think this test case (test/Transforms/LICM/AliasSetMemSet.ll) can show the problem. Do you think it is good enough?

[haicheng]

Now LICM can update AST if the sub-loops are changed by loop unroll. It might be better to do the same for LIR instead of re-computing the AST.

lib/Transforms/Scalar/LICM.cpp

private:
 
     /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias
     /// set.
     void deleteAnalysisValue(Value *V, Loop *L) override;
 
     /// Simple Analysis hook. Delete loop L from alias set map.
     void deleteAnalysisLoop(Loop *L) override;
 
-    /// Returns an owning pointer to an alias set which incorporates aliasing
-    /// info from all subloops of L, but does not include instructions in L
-    /// itself.
-    AliasSetTracker *collectAliasInfoFromSubLoops(Loop *L);
+    /// Calculates an alias set which incorporates aliasing info from all
+    /// subloops of L and L itself by using LoopToAliasSetMap.
+    void collectAliasInfoFastPath(Loop *L);
   };
 }
 
 char LICM::ID = 0;
 INITIALIZE_PASS_BEGIN(LICM, "licm", "Loop Invariant Code Motion", false, false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) {
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 
   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 
   assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
 
-  CurAST = collectAliasInfoFromSubLoops(L);
+  // Use the fast path to collect alias info if no other loop passes can modify
+  // the sub loops.
+  bool FastPath = (LPM.getNumContainedPasses() == 1);
 
-  CurLoop = L;
-
-  // Get the preheader block to move instructions into...
-  Preheader = L->getLoopPreheader();
+  if (FastPath) {
+    collectAliasInfoFastPath(L);
+  } else {
+    CurAST = new AliasSetTracker(*AA);
 
     // Loop over the body of this loop, looking for calls, invokes, and stores.
-  // Because subloops have already been incorporated into AST, we skip blocks in
-  // subloops.
-  //
-  for (BasicBlock *BB : L->blocks()) {
-    if (LI->getLoopFor(BB) == L)        // Ignore blocks in subloops.
-      CurAST->add(*BB);                 // Incorporate the specified basic block
+    for (BasicBlock *BB : L->blocks())
+      CurAST->add(*BB); // Incorporate the specified basic block
   }
 
+  CurLoop = L;
+
+  // Get the preheader block to move instructions into...
+  Preheader = L->getLoopPreheader();
+
   // Compute loop safety information.
   LICMSafetyInfo SafetyInfo;
   computeLICMSafetyInfo(&SafetyInfo, CurLoop);
 
   // We want to visit all of the instructions in this loop... that are not parts
   // of our subloops (they have already had their invariants hoisted out of
   // their loop, into this loop, so there is no need to process the BODIES of
   // the subloops).
assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) &&
          "Parent loop not left in LCSSA form after LICM!");
 
   // Clear out loops state information for the next iteration
   CurLoop = nullptr;
   Preheader = nullptr;
 
   // If this loop is nested inside of another one, save the alias information
   // for when we process the outer loop.
-  if (L->getParentLoop())
+  if (L->getParentLoop() && FastPath)
     LoopToAliasSetMap[L] = CurAST;
   else
     delete CurAST;
   return Changed;
 }
 
 /// Walk the specified region of the CFG (defined by all blocks dominated by
 /// the specified block, and that are in the current loop) in reverse depth 
bool llvm::promoteLoopAccessesToScalars(AliasSet &AS,
 
   // If the SSAUpdater didn't use the load in the preheader, just zap it now.
   if (PreheaderLoad->use_empty())
     PreheaderLoad->eraseFromParent();
 
   return Changed;
 }
 
-/// Returns an owning pointer to an alias set which incorporates aliasing info
-/// from all subloops of L, but does not include instructions in L itself.
+/// Calculates an alias set which incorporates aliasing info from all subloops
+/// of L and L itself by using LoopToAliasSetMap.
 ///
-AliasSetTracker *LICM::collectAliasInfoFromSubLoops(Loop *L) {
-  AliasSetTracker *CurAST = nullptr;
+void LICM::collectAliasInfoFastPath(Loop *L) {
+  CurAST = nullptr;
   for (Loop *InnerL : L->getSubLoops()) {
     AliasSetTracker *InnerAST = LoopToAliasSetMap[InnerL];
     assert(InnerAST && "Where is my AST?");
 
     if (CurAST != nullptr) {
-      // What if InnerLoop was modified by other passes ?
       CurAST->add(*InnerAST);
 
       // Once we've incorporated the inner loop's AST into ours, we don't need
       // the subloop's anymore.
       delete InnerAST;
     } else {
       CurAST = InnerAST;
     }
     LoopToAliasSetMap.erase(InnerL);
   }
   if (CurAST == nullptr)
     CurAST = new AliasSetTracker(*AA);
-  return CurAST;
+
+  // Loop over the body of this loop, looking for calls, invokes, and stores.
+  // Because subloops have already been incorporated into AST, we skip blocks in
+  // subloops.
+  //
+  for (BasicBlock *BB : L->blocks()) {
+    if (LI->getLoopFor(BB) == L) // Ignore blocks in subloops.
+      CurAST->add(*BB);          // Incorporate the specified basic block
+  }
+
+  return;
 }
 
 /// Simple analysis hook. Clone alias set info.
 ///
 void LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) {
   AliasSetTracker *AST = LoopToAliasSetMap.lookup(L);
   if (!AST)
     return;