Tweak the LICM code to reuse the first sub-loop instead of creating a new one

[gareevroman]

Summary

LICM starts with an *empty* AST, and then merges in each sub-loop. While the add code is appropriate for sub-loop 2 and up, it's utterly unnecessary for sub-loop 1. If the AST starts off empty, we can just clone/move the contents of the subloop into the containing AST.

It passes the LLVM regression tests and helps to reduce the runtime of 'opt -basicaa -licm out.opt.ll’ from 130ms to 74ms and the runtime of 'opt -basicaa -licm out.opt2.ll’ from 117ms to 68ms.

[reames]

Looks functionally correct, but stylistically could use some work.

lib/Transforms/Scalar/LICM.cpp

205 ↗

(On Diff #46484)

Extracting this code as a helper function would make it much cleaner.

The other option would be to turn add(AST&) into add(AST&&) - e.g. move the parameter.

You might also get away with special casing the copy into an empty AST.

The general point of each of my comments above is that the complexity in ownership in the new code is high and it would be nice to reduce that if possible.

[gareevroman]

In D16753#341351, @reames wrote:

Looks functionally correct, but stylistically could use some work.

Thank you for the comments.

Extracting this code as a helper function would make it much cleaner.

The other option would be to turn add(AST&) into add(AST&&) - e.g. move the parameter.

If I’m not mistaken, ilist doesn’t support move semantics. Should we copy contents of ilist<AliasSet> AliasSets in this case?

You might also get away with special casing the copy into an empty AST.

I have a question related to this. Could you please advise me a preferred way to copy contents of one ilist<AliasSet> AliasSets to another AliasSets?

The general point of each of my comments above is that the complexity in ownership in the new code is high and it would be nice to reduce that if possible.

OK. If in this case the simplicity in ownership is more preferable than the simplicity of AliasTracker::add, let’s modify AliasTracker::add.

[gareevroman]

Extract code as a helper function.

[gareevroman]

In D16753#342889, @gareevroman wrote:

In D16753#341351, @reames wrote:

Looks functionally correct, but stylistically could use some work.

Thank you for the comments.

Extracting this code as a helper function would make it much cleaner.

The other option would be to turn add(AST&) into add(AST&&) - e.g. move the parameter.

If I’m not mistaken, ilist doesn’t support move semantics. Should we copy contents of ilist<AliasSet> AliasSets in this case?

If I’m not mistaken, swap of iplist, which is a base class of ilist, is temporary disabled, because it doesn’t use list traits callback correctly yet. Maybe we could extract this code as a helper function and git rid of it, when iplist::swap is available and it is easier to turn add(AST&) into add(AST&&). What do you think about it?

You might also get away with special casing the copy into an empty AST.

I have a question related to this. Could you please advise me a preferred way to copy contents of one ilist<AliasSet> AliasSets to another AliasSets?

I’ve tried to use ilist::assign to do this. However, I get a compile time error, because a copy constructor of the AliasSet is deleted.

The general point of each of my comments above is that the complexity in ownership in the new code is high and it would be nice to reduce that if possible.

OK. If in this case the simplicity in ownership is more preferable than the simplicity of AliasTracker::add, let’s modify AliasTracker::add.

[gareevroman]

Extracting this code as a helper function would make it much cleaner.

Philip, did you propose to extract another code as a helper function? Sorry, maybe I missed something.

[reames]

Minor comments only. This looks really close to landing.

lib/Transforms/Scalar/LICM.cpp

225 ↗

(On Diff #47162)

Move this bit of code into your helpful function as well. With it being outside the function, the naming is misleading.

Alternatively, rename the function to something like collectAliasInfoForSubLoops.

[gareevroman]

Rename the function.

[gareevroman]

In D16753#350857, @reames wrote:

Minor comments only. This looks really close to landing.

Thank you for the comments.

[reames]

LGTM w/minor comment fix.

lib/Transforms/Scalar/LICM.cpp

1058 ↗

(On Diff #47773)

minor: a better comment would be: 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.

[gareevroman]

In D16753#351517, @reames wrote:

LGTM w/minor comment fix.

Thank you for the review!

llvm/trunk/lib/Transforms/Scalar/LICM.cpp

void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To,
                                  Loop *L) override;
 
     /// 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);
   };
 }
 
 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 = new AliasSetTracker(*AA);
-  // Collect Alias info from subloops.
-  for (Loop *InnerL : L->getSubLoops()) {
-    AliasSetTracker *InnerAST = LoopToAliasSetMap[InnerL];
-    assert(InnerAST && "Where is my AST?");
-
-    // 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;
-    LoopToAliasSetMap.erase(InnerL);
-  }
+  CurAST = collectAliasInfoFromSubLoops(L);
 
   CurLoop = L;
 
   // Get the preheader block to move instructions into...
   Preheader = L->getLoopPreheader();
 
   // 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
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.
+///
+AliasSetTracker *LICM::collectAliasInfoFromSubLoops(Loop *L) {
+  AliasSetTracker *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;
+}
+
 /// Simple analysis hook. Clone alias set info.
 ///
 void LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) {
   AliasSetTracker *AST = LoopToAliasSetMap.lookup(L);
   if (!AST)
     return;
 
   AST->copyValue(From, To);