[LoopLoadElim] Make sure all loops are in simplify form. PR48150

[mkazantsev]

Summary

LoopLoadElim may end up expanding an AddRec from a loop
which is not the current loop. This loop may not be in simplify
form. We figure it out after the no-return point, so cannot bail
in this case.

AddRec requires simplify form to expand. The only way to ensure
this does not crash is to simplify all loops beforehand.

The issue only exists in new PM. Old PM requests LoopSimplify
required pass and it simplifies all loops before the opt begins.

[mkazantsev]

Ping.

[lebedev.ri]

(this is new-pm-specific)

[aeubanks]

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

627

does every loop need to be simplified? or can the call be moved into the processing of the Worklist below?

[mkazantsev]

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

627

We might need any loop in simplified form, and the worklist only contains inner loops.

[aeubanks]

I'm not super familiar with this, do you know why this only affects the new PM? (the code looks fine, I'd just like to understand what's going on better)

llvm/test/Transforms/LoopLoadElim/pr-48150.ll

1–2

is this still necessary?

[mkazantsev]

In D91525#2412162, @aeubanks wrote:

I'm not super familiar with this, do you know why this only affects the new PM? (the code looks fine, I'd just like to understand what's going on better)

void getAnalysisUsage(AnalysisUsage &AU) const override {
  AU.addRequiredID(LoopSimplifyID);

Because of this, all loops in old PM are simplified before the opt starts.

llvm/test/Transforms/LoopLoadElim/pr-48150.ll

1–2

Nope.

[asbirlea]

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

668

Comments on nullptr args.

[aeubanks]

Oh I see, thanks

[uabelho]

I noticed a new crash with this patch when using the old PM.
I wrote
https://bugs.llvm.org/show_bug.cgi?id=49141
about it.

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.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/Utils.h"
+#include "llvm/Transforms/Utils/LoopSimplify.h"
 #include "llvm/Transforms/Utils/LoopVersioning.h"
 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
 #include "llvm/Transforms/Utils/SizeOpts.h"
 #include <algorithm>
 #include <cassert>
 #include <forward_list>
 #include <set>
 #include <tuple>
private:
   PredicatedScalarEvolution PSE;
 };
 
 } // end anonymous namespace
 
 static bool
 eliminateLoadsAcrossLoops(Function &F, LoopInfo &LI, DominatorTree &DT,
                           BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
+                          ScalarEvolution *SE, AssumptionCache *AC,
                           function_ref<const LoopAccessInfo &(Loop &)> GetLAI) {
   // Build up a worklist of inner-loops to transform to avoid iterator
   // invalidation.
   // FIXME: This logic comes from other passes that actually change the loop
   // nest structure. It isn't clear this is necessary (or useful) for a pass
   // which merely optimizes the use of loads in a loop.
   SmallVector<Loop *, 8> Worklist;
 
+  bool Changed = false;
+
   for (Loop *TopLevelLoop : LI)
-    for (Loop *L : depth_first(TopLevelLoop))
+    for (Loop *L : depth_first(TopLevelLoop)) {
+      Changed |= simplifyLoop(L, &DT, &LI, SE, AC, /*MSSAU*/ nullptr, false);
       // We only handle inner-most loops.
       if (L->isInnermost())
         Worklist.push_back(L);
+    }
 
   // Now walk the identified inner loops.
-  bool Changed = false;
   for (Loop *L : Worklist) {
     // The actual work is performed by LoadEliminationForLoop.
     LoadEliminationForLoop LEL(L, &LI, GetLAI(*L), &DT, BFI, PSI);
     Changed |= LEL.processLoop();
   }
   return Changed;
 }
 
bool runOnFunction(Function &F) override {
     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
     auto *BFI = (PSI && PSI->hasProfileSummary()) ?
                 &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI() :
                 nullptr;
 
     // Process each loop nest in the function.
     return eliminateLoadsAcrossLoops(
-        F, LI, DT, BFI, PSI,
+        F, LI, DT, BFI, PSI, /*SE*/ nullptr, /*AC*/ nullptr,
         [&LAA](Loop &L) -> const LoopAccessInfo & { return LAA.getInfo(&L); });
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequiredID(LoopSimplifyID);
     AU.addRequired<LoopInfoWrapperPass>();
     AU.addPreserved<LoopInfoWrapperPass>();
     AU.addRequired<LoopAccessLegacyAnalysis>();
PreservedAnalyses LoopLoadEliminationPass::run(Function &F,
   auto *BFI = (PSI && PSI->hasProfileSummary()) ?
       &AM.getResult<BlockFrequencyAnalysis>(F) : nullptr;
   MemorySSA *MSSA = EnableMSSALoopDependency
                         ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA()
                         : nullptr;
 
   auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
   bool Changed = eliminateLoadsAcrossLoops(
-      F, LI, DT, BFI, PSI, [&](Loop &L) -> const LoopAccessInfo & {
+      F, LI, DT, BFI, PSI, &SE, &AC, [&](Loop &L) -> const LoopAccessInfo & {
         LoopStandardAnalysisResults AR = {AA,  AC,  DT,      LI,  SE,
                                           TLI, TTI, nullptr, MSSA};
         return LAM.getResult<LoopAccessAnalysis>(L, AR);
       });
 
   if (!Changed)
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   return PA;
 }

llvm/test/Transforms/LoopLoadElim/pr-48150.ll

 ; RUN: opt -passes=loop-load-elim -S < %s | FileCheck %s
-; REQUIRES: asserts
-; XFAIL: *
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @test() {
 ; CHECK-LABEL: test
 bb:
   br i1 undef, label %bb1, label %bb2