[PM/OptBisect] Don't crash with some particular values of -opt-bisect-limit=

[davide]

Summary

So, while trying to reduce a testcase I realized I can trigger a crash in LICM if I specify a given value of -opt-bisect-limit
(the repro is the one from https://llvm.org/bugs/show_bug.cgi?id=30708)

$ ./opt unopt.ll -opt-bisect-limit=53 -O3
[...]
BISECT: running pass (43) Loop Invariant Code Motion on loop                                                                                                                                                                                                                                                                                   │··························
BISECT: running pass (44) Unswitch loops on loop                                                                                                                                                                                                                                                                                               │··························
BISECT: running pass (45) Rotate Loops on loop                                                                                                                                                                                                                                                                                                 │··························
BISECT: running pass (46) Loop Invariant Code Motion on loop                                                                                                                                                                                                                                                                                   │··························
BISECT: running pass (47) Unswitch loops on loop                                                                                                                                                                                                                                                                                               │··························
BISECT: running pass (48) Rotate Loops on loop                                                                                                                                                                                                                                                                                                 │··························
BISECT: running pass (49) Loop Invariant Code Motion on loop                                                                                                                                                                                                                                                                                   │··························
BISECT: running pass (50) Unswitch loops on loop                                                                                                                                                                                                                                                                                               │··························
BISECT: running pass (51) Rotate Loops on loop                                                                                                                                                                                                                                                                                                 │··························
BISECT: running pass (52) Loop Invariant Code Motion on loop                                                                                                                                                                                                                                                                                   │··························
BISECT: running pass (53) Unswitch loops on loop                                                                                                                                                                                                                                                                                               │··························
BISECT: NOT running pass (54) Rotate Loops on loop                                                                                                                                                                                                                                                                                             │··························
BISECT: NOT running pass (55) Loop Invariant Code Motion on loop                                                                                                                                                                                                                                                                               │··························
BISECT: NOT running pass (56) Unswitch loops on loop                                                                                                                                                                                                                                                                                           │··························
BISECT: NOT running pass (57) Rotate Loops on loop                                                                                                                                                                                                                                                                                             │··························
[...]
opt: /home/davide/work/llvm-monorepo/llvm/lib/Transforms/Scalar/LICM.cpp:156: virtual bool {anonymous}::LegacyLICMPass::doFinalization(): Assertion `LICM.getLoopToAliasSetMap().empty() && "Didn't free loop alias sets"' failed.                                                                                                      

I do think that the problem here is that if skipLoop(L) is true, we don't call the deleteSimpleAnalysisLoop() hook in the Loop Pass Manager, this leaves some pending elements inside LICM internal data structures -> doFinalization() checks for the map to be empty, and hits the assertion.

[davide]

FWIW, this only happens in the current PM. I'm not sure how the situation should be handled in the new pass manager, probably it's a discussion we can defer as long as a) the infrastructure for loopPM isn't complete in the new pm b) opt-bisect doesn't work with the new PM (to the best of my knowledge)

[davide]

updated a new patch with context

[andrew.w.kaylor]

lib/Analysis/LoopPass.cpp

208 ↗

(On Diff #75365)

This function shouldn't be called here. The pass has already run (or not) by this point, and this call will cause the OptBisect component to increment its counter again and skipLoop() may return true here after having returned false when the current LoopPass was run.

[andrew.w.kaylor]

I'm trying to understand where the data structured entry gets removed when the pass is not skipped. I tried downloading the reproducer from the PR you mentioned, but I can't seem to get this to happen with that file and the command line you listed above. I have seen this problem before, but I'm having trouble making it happen now.

Can you send me the .ll file you are using and the LLVM version number you built with?

[davide]

In D25848#579195, @andrew.w.kaylor wrote:

I'm trying to understand where the data structured entry gets removed when the pass is not skipped. I tried downloading the reproducer from the PR you mentioned, but I can't seem to get this to happen with that file and the command line you listed above. I have seen this problem before, but I'm having trouble making it happen now.

Can you send me the .ll file you are using and the LLVM version number you built with?

I completely missed your comment. This still hits an assertion on trunk @r288671.
To reproduce, just run

$ ./opt unopt.ll -opt-bisect-limit=53 -O3

on the following testcase:

@d = global i32 1, align 4
@e = common global i32 0, align 4
@c = common global i32 0, align 4
@b = common global i32 0, align 4
@a = common global i32 0, align 4
@.str = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1
define void @fn1() {
  %i = alloca i16, align 2
  %f = alloca i32, align 4
  store i32 53, i32* %f, align 4
  br label %for.cond
for.cond:                                         ; preds = %for.cond1, %0
  br label %for.cond1
for.cond1:                                        ; preds = %for.end, %for.cond
  %dec12.sink = phi i32 [ 0, %for.end ], [ 1, %for.cond ]
  store i32 %dec12.sink, i32* @c, align 4
  %tmp = load i32, i32* @c, align 4
  %tobool = icmp ne i32 %tmp, 0
  br i1 %tobool, label %for.body, label %for.cond
for.body:                                         ; preds = %for.cond1
  %tmp1 = load i32, i32* %f, align 4
  %cmp = icmp sgt i32 %tmp1, 1
  %tmp2 = load i32, i32* %f, align 4
  %shr = ashr i32 1, %tmp2
  %cond = select i1 %cmp, i32 1, i32 %shr
  %conv = trunc i32 %cond to i16
  store i16 %conv, i16* %i, align 2
  %tmp3 = load i16, i16* %i, align 2
  %conv2 = zext i16 %tmp3 to i32
  %tmp4 = load i32, i32* @c, align 4
  %cmp3 = icmp eq i32 %conv2, %tmp4
  %conv4 = zext i1 %cmp3 to i32
  store i32 %conv4, i32* @b, align 4
  store i32 0, i32* %f, align 4
  store i32 1, i32* @a, align 4
  br label %for.cond5
for.cond5:                                        ; preds = %if.end, %for.body
  %tmp5 = load i32, i32* @a, align 4
  %tobool6 = icmp ne i32 %tmp5, 0
  br i1 %tobool6, label %for.body7, label %for.end
for.body7:                                        ; preds = %for.cond5
  %tmp6 = load i32, i32* @e, align 4
  %tobool8 = icmp ne i32 %tmp6, 0
  br i1 %tobool8, label %if.then, label %if.end
if.then:                                          ; preds = %for.body7
  store i32 0, i32* @a, align 4
  br label %if.end
if.end:                                           ; preds = %if.then, %for.body7
  %tmp8 = load i32, i32* @d, align 4
  %tobool9 = icmp ne i32 %tmp8, 0
  br i1 %tobool9, label %if.then10, label %for.cond5
if.then10:                                        ; preds = %if.end
  ret void
for.end:                                          ; preds = %for.cond5
  br label %for.cond1
}
define void @main() {
  call void @fn1()
  %tmp = load i32, i32* @b, align 4
  call void (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0), i32 %tmp)
  ret void
}
declare void @printf(i8*, ...)

[andrew.w.kaylor]

Sorry this is moving so slowly. I just reproduced the problem with the test file from your last comment. I'll take a closer look and see if I can understand what's going on.

[andrew.w.kaylor]

What do you think of this change instead?

Index: lib/Transforms/Scalar/LICM.cpp
===================================================================
--- lib/Transforms/Scalar/LICM.cpp	(revision 289480)
+++ lib/Transforms/Scalar/LICM.cpp	(working copy)
@@ -124,8 +124,13 @@
   }
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
-    if (skipLoop(L))
+    if (skipLoop(L)) {
+      // If we have run LICM on a previous loop but now we are skipping
+      // (because we've hit the opt-bisect limit), we need to clear the
+      // loop alias information.
+      LICM.getLoopToAliasSetMap().clear();
       return false;
+    }
 
     auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
     return LICM.runOnLoop(L,

[davide]

In D25848#624162, @andrew.w.kaylor wrote:

What do you think of this change instead?

Index: lib/Transforms/Scalar/LICM.cpp
===================================================================
--- lib/Transforms/Scalar/LICM.cpp	(revision 289480)
+++ lib/Transforms/Scalar/LICM.cpp	(working copy)
@@ -124,8 +124,13 @@
   }
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
-    if (skipLoop(L))
+    if (skipLoop(L)) {
+      // If we have run LICM on a previous loop but now we are skipping
+      // (because we've hit the opt-bisect limit), we need to clear the
+      // loop alias information.
+      LICM.getLoopToAliasSetMap().clear();
       return false;
+    }
 
     auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
     return LICM.runOnLoop(L,

I consider this reasonable, but I don't feel qualified enough to review as I'm not a LICM expert, so I'm CC:ing @danielcdh . I'm slightly worried about other passes hitting a similar issue (expecting some state to be freed and asserting in doFinalization())

[andrew.w.kaylor]

In D25848#624177, @davide wrote:

I consider this reasonable, but I don't feel qualified enough to review as I'm not a LICM expert, so I'm CC:ing @danielcdh . I'm slightly worried about other passes hitting a similar issue (expecting some state to be freed and asserting in doFinalization())

I think that's a reasonable concern, but I'm inclined to believe that this occurring is an indication of sloppy design in such passes that just happens to be exposed by OptBisect. For instance, the reason the problem surfaced in this case is that one instance of the LICM pass was creating state that it expected to be cleaned up by a later instance of the same pass. This kind of cross-pass dependency really should be avoided. I'm not entirely clear how LICM is using this information, but it makes me wonder if LICM should be a function pass, since it is apparently operating beyond the scope of a single loop.

[davide]

In D25848#624324, @andrew.w.kaylor wrote:

In D25848#624177, @davide wrote:

I consider this reasonable, but I don't feel qualified enough to review as I'm not a LICM expert, so I'm CC:ing @danielcdh . I'm slightly worried about other passes hitting a similar issue (expecting some state to be freed and asserting in doFinalization())

I think that's a reasonable concern, but I'm inclined to believe that this occurring is an indication of sloppy design in such passes that just happens to be exposed by OptBisect. For instance, the reason the problem surfaced in this case is that one instance of the LICM pass was creating state that it expected to be cleaned up by a later instance of the same pass. This kind of cross-pass dependency really should be avoided. I'm not entirely clear how LICM is using this information, but it makes me wonder if LICM should be a function pass, since it is apparently operating beyond the scope of a single loop.

In D25848#624177, @davide wrote:

In D25848#624162, @andrew.w.kaylor wrote:

What do you think of this change instead?

Index: lib/Transforms/Scalar/LICM.cpp
===================================================================
--- lib/Transforms/Scalar/LICM.cpp	(revision 289480)
+++ lib/Transforms/Scalar/LICM.cpp	(working copy)
@@ -124,8 +124,13 @@
   }
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
-    if (skipLoop(L))
+    if (skipLoop(L)) {
+      // If we have run LICM on a previous loop but now we are skipping
+      // (because we've hit the opt-bisect limit), we need to clear the
+      // loop alias information.
+      LICM.getLoopToAliasSetMap().clear();
       return false;
+    }
 
     auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
     return LICM.runOnLoop(L,

I consider this reasonable, but I don't feel qualified enough to review as I'm not a LICM expert, so I'm CC:ing @danielcdh . I'm slightly worried about other passes hitting a similar issue (expecting some state to be freed and asserting in doFinalization())

@danielcdh Dehao, ping?

[chandlerc]

In D25848#624324, @andrew.w.kaylor wrote:

In D25848#624177, @davide wrote:

I consider this reasonable, but I don't feel qualified enough to review as I'm not a LICM expert, so I'm CC:ing @danielcdh . I'm slightly worried about other passes hitting a similar issue (expecting some state to be freed and asserting in doFinalization())

I think that's a reasonable concern, but I'm inclined to believe that this occurring is an indication of sloppy design in such passes that just happens to be exposed by OptBisect. For instance, the reason the problem surfaced in this case is that one instance of the LICM pass was creating state that it expected to be cleaned up by a later instance of the same pass. This kind of cross-pass dependency really should be avoided. I'm not entirely clear how LICM is using this information, but it makes me wonder if LICM should be a function pass, since it is apparently operating beyond the scope of a single loop.

I agree with Andy here.

Fundamentally, LICM is playing *very* fast and loose with the pass infrastructure. bisect is catching it, good! We can't really fix it in the current pass manager. =[ So the best we can do is hack around it, and I think Andy's suggested hack is reasonable. I think this will be fairly rare at least, and the new pass manager gives us options to specifically avoid this design trap.

The key issue is that LICM wants to save state from one loop to use in the next. If we had, say, a LoopAnalysisManager (as we have in the new PM) which could cache such state and provide it later on, this would Just Work with no weird state buried in the pass.

Anyways, Andy's proposed patch LGTM. Davide, if you want to clean it up and land it, go for it. No need for more review here, just explain what is going on. Thanks for chasing this down1

[danielcdh]

In D25848#628880, @davide wrote:

In D25848#624324, @andrew.w.kaylor wrote:

In D25848#624177, @davide wrote:

I consider this reasonable, but I don't feel qualified enough to review as I'm not a LICM expert, so I'm CC:ing @danielcdh . I'm slightly worried about other passes hitting a similar issue (expecting some state to be freed and asserting in doFinalization())

I think that's a reasonable concern, but I'm inclined to believe that this occurring is an indication of sloppy design in such passes that just happens to be exposed by OptBisect. For instance, the reason the problem surfaced in this case is that one instance of the LICM pass was creating state that it expected to be cleaned up by a later instance of the same pass. This kind of cross-pass dependency really should be avoided. I'm not entirely clear how LICM is using this information, but it makes me wonder if LICM should be a function pass, since it is apparently operating beyond the scope of a single loop.

In D25848#624177, @davide wrote:

In D25848#624162, @andrew.w.kaylor wrote:

What do you think of this change instead?

Index: lib/Transforms/Scalar/LICM.cpp
===================================================================
--- lib/Transforms/Scalar/LICM.cpp	(revision 289480)
+++ lib/Transforms/Scalar/LICM.cpp	(working copy)
@@ -124,8 +124,13 @@
   }
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
-    if (skipLoop(L))
+    if (skipLoop(L)) {
+      // If we have run LICM on a previous loop but now we are skipping
+      // (because we've hit the opt-bisect limit), we need to clear the
+      // loop alias information.
+      LICM.getLoopToAliasSetMap().clear();
       return false;
+    }
 
     auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
     return LICM.runOnLoop(L,

I consider this reasonable, but I don't feel qualified enough to review as I'm not a LICM expert, so I'm CC:ing @danielcdh . I'm slightly worried about other passes hitting a similar issue (expecting some state to be freed and asserting in doFinalization())

@danielcdh Dehao, ping?

cloneBasicBlockAnalysis deleteAnalysisValue deleteAnalysisLoop are used to maintain intermediate states between nested loops. Anything that uses these function (only LICM so far) need to have special handling to clear intermediate data structure when skipLoop is called, otherwise there will be memory leak.

For the new pass manager, as from the following comment:

/ 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.

The above 3 functions is not available to enable caching. So each loop is independently handled and no need to handle intermediate data structure.

Andy's change LGTM.

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

 
 struct LegacyLICMPass : public LoopPass {
   static char ID; // Pass identification, replacement for typeid
   LegacyLICMPass() : LoopPass(ID) {
     initializeLegacyLICMPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
-    if (skipLoop(L))
+    if (skipLoop(L)) {
+      // If we have run LICM on a previous loop but now we are skipping
+      // (because we've hit the opt-bisect limit), we need to clear the
+      // loop alias information.
+      LICM.getLoopToAliasSetMap().clear();
       return false;
+    }
 
     auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
     return LICM.runOnLoop(L,
                           &getAnalysis<AAResultsWrapperPass>().getAAResults(),
                           &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
                           &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
                           &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
                           SE ? &SE->getSE() : nullptr, false);

llvm/trunk/test/Transforms/LICM/bisect-state.ll

+; Make sure we don't crash in LICM.
+; RUN: opt %s -licm -opt-bisect-limit=1
+
+define void @patatino() {
+for.cond1:
+  br label %for.body
+for.body:
+  br label %for.cond5
+for.cond5:
+  br i1 true, label %if.end, label %for.end
+if.end:
+  br label %for.cond5
+for.end:
+  br label %for.body
+}