[LICM] Avoid duplicate work during building AliasSetTracker

[skatkov]

Summary

Currently we re-use cached info from sub loops or traverse them
to populate AliasSetTracker. But after that we traverse all basic blocks
from the current loop. This is redundant work.

All what we need is traversing the all basic blocks from the loop except
those which are used to get the data from the cache.

This should improve compile time only.

[reames]

This looks correct to me, but this is so glaringly bad I'd like a second set of eyes to make sure I'm not missing something. Can someone else confirm?

lib/Transforms/Scalar/LICM.cpp

1545

I'm fine with this implementation, but if you wanted, you could structure this one of two ways:

1. Use a SmallVector<BasicBlock> since the sets of BBs are distinct by assumption.
2. Keep track of which loops are handle, then check the containing loop for each BB using LoopInfo (it has a map from BB to innermost containing loop).

[reames]

lib/Transforms/Scalar/LICM.cpp

1545

Or just inline mergeLoop and restore the check removed by cce6712519 for the parent loop. That's the change which appears to have introduced this compile time regression. :)

Yeah for compile time problems which go unfound for 20 months...

[skatkov]

lib/Transforms/Scalar/LICM.cpp

1545

1. The main operation for HandledBBs we need is to find whether some BB is in this set. I do not think that SmallVector is a good candidate for that.
2. I do not think it is a right solution. When we go over all basic blocks of the loop L we can take a BB which is a part of inner inner loop (with depth = depth(L) + 2 or more. When we traversed inner loops we considered only immediate sub loops. So if we collect all used sub loops (AllSL) and now we consider BB then it is not enough to check that Loop(BB) is in ALLSL set. We must ensure that some element of ALLSL contains BB. This does not look like a less complexity than just collect all BBs and check whether it is already handled like I did in the patch.

[skatkov]

lib/Transforms/Scalar/LICM.cpp

1559

Actually this comment worries me most. What if another loop pass executing in the same LoopPassManager modifies the inner loop in the way that AST is changed?
If it is possible then removing the caching entirely is most safe thing to do probably.

[skatkov]

is it better?

[reames]

Looked at the history in more detail, and decided I'm comfortable with this fix. So, LGTM.

Serguei, the invalidation question is a separate one. Let's see what falls out from this, and then revisit as needed.

lib/Transforms/Scalar/LICM.cpp

 /// FIXME: In new pass manager, there is no helper function to handle loop
 /// analysis such as cloneBasicBlockAnalysis, so the AST needs to be recomputed
 /// from scratch for every loop. Hook up with the helper functions when
 /// available in the new pass manager to avoid redundant computation.
 std::unique_ptr<AliasSetTracker>
 LoopInvariantCodeMotion::collectAliasInfoForLoop(Loop *L, LoopInfo *LI,
                                                  AliasAnalysis *AA) {
   std::unique_ptr<AliasSetTracker> CurAST;
-  SmallVector<Loop *, 4> RecomputeLoops;
-  auto mergeLoop = [&CurAST](Loop *L) {
-    // Loop over the body of this loop, looking for calls, invokes, and stores.
-    for (BasicBlock *BB : L->blocks())
-      CurAST->add(*BB); // Incorporate the specified basic block
-  };
+  DenseSet<BasicBlock *> HandledBBs;
+
+  // Try to re-use cached info from sub loops.
   for (Loop *InnerL : L->getSubLoops()) {
     auto MapI = LoopToAliasSetMap.find(InnerL);
     // If the AST for this inner loop is missing it may have been merged into
     // some other loop's AST and then that loop unrolled, and so we need to
     // recompute it.
-    if (MapI == LoopToAliasSetMap.end()) {
-      RecomputeLoops.push_back(InnerL);
+    if (MapI == LoopToAliasSetMap.end())
       continue;
-    }
+
     std::unique_ptr<AliasSetTracker> InnerAST = std::move(MapI->second);
 
     if (CurAST) {
       // What if InnerLoop was modified by other passes ?
       // Once we've incorporated the inner loop's AST into ours, we don't need
       // the subloop's anymore.
       CurAST->add(*InnerAST);
     } else {
       CurAST = std::move(InnerAST);
     }
     LoopToAliasSetMap.erase(MapI);
+    // Inner loop has been handled, so no need to process its BBs again.
+    HandledBBs.insert(InnerL->block_begin(), InnerL->block_end());
   }
   if (!CurAST)
     CurAST = make_unique<AliasSetTracker>(*AA);
 
-  // Add everything from the sub loops that are no longer directly available.
-  for (Loop *InnerL : RecomputeLoops)
-    mergeLoop(InnerL);
-
-  // And merge in this loop.
-  mergeLoop(L);
+  // Loop over the body of this loop, looking for calls, invokes, and stores.
+  // Do not traverse already handled BBs.
+  for (BasicBlock *BB : L->blocks())
+    if (!HandledBBs.count(BB))
+      CurAST->add(*BB); // Incorporate the specified basic block
 
   return CurAST;
 }
 
 /// Simple analysis hook. Clone alias set info.
 ///
 void LegacyLICMPass::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To,
                                              Loop *L) {