[Pass Manager] Excessive scheduled passes

[patrick-rivos]

Affects LLVM 13 up to and including trunk.

Program:

short a, b;
signed char c;
short d[52];
static char e() {
  for (;; b--) {
    a = 0;
    for (; a <= 3; a++) {
      c = 2;
      for (; c >= 0; c--)
        if ((short)(b * (c + 1) * 4))
          if (d[c * 4 + a])
            return 0;
    }
  }
}
void f() { e(); }

Godbolt: https://godbolt.org/z/hKcezobh8

Reduced LLVM IR:

@b = external global i16
@c = external global i8
@d = external global [52 x i16]

define void @f() {
entry:
  %call = call i8 @e()
  ret void
}

define internal i8 @e() {
entry:
  br label %for.cond

for.cond:                                         ; preds = %for.inc21, %entry
  br label %for.cond1

for.cond1:                                        ; preds = %for.inc19, %for.cond
  %0 = phi i16 [ 0, %for.cond ], [ %inc, %for.inc19 ]
  %cmp = icmp slt i16 %0, 4
  br i1 %cmp, label %for.cond3, label %for.inc21

for.cond3:                                        ; preds = %for.inc, %for.cond1
  %1 = phi i8 [ %dec, %for.inc ], [ 2, %for.cond1 ]
  store i8 %1, ptr @c, align 1
  %cmp5 = icmp sgt i8 %1, -1
  br i1 %cmp5, label %for.body7, label %for.inc19

for.body7:                                        ; preds = %for.cond3
  %2 = load i16, ptr @b, align 2
  %narrow = add i8 %1, 1
  %add = zext i8 %narrow to i16
  %mul = mul i16 %2, %add
  %mul10.mask = and i16 %mul, 16383
  %tobool.not = icmp eq i16 %mul10.mask, 0
  br i1 %tobool.not, label %for.inc, label %if.then

if.then:                                          ; preds = %for.body7
  %conv12 = zext i8 %1 to i32
  %mul13 = shl i32 %conv12, 2
  %conv14 = sext i16 %0 to i32
  %add15 = or i32 %mul13, %conv14
  %idxprom = sext i32 %add15 to i64
  %arrayidx = getelementptr [52 x i16], ptr @d, i64 0, i64 %idxprom
  %3 = load i16, ptr %arrayidx, align 2
  %tobool16.not = icmp eq i16 %3, 0
  br i1 %tobool16.not, label %for.inc, label %if.then17

if.then17:                                        ; preds = %if.then
  ret i8 0

for.inc:                                          ; preds = %if.then, %for.body7
  %dec = add i8 %1, -1
  br label %for.cond3

for.inc19:                                        ; preds = %for.cond3
  %inc = add i16 %0, 1
  br label %for.cond1

for.inc21:                                        ; preds = %for.cond1
  %4 = load i16, ptr @b, align 2
  %dec22 = add i16 %4, 1
  store i16 %dec22, ptr @b, align 2
  br label %for.cond
}

Godbolt: https://godbolt.org/z/xzr8bEx8W

From -opt-bisect-limit=3000 it seems like it gets into a loop with these 6 passes:

SimpleLoopUnswitchPass on for.inc.i.us186.us3650.us.us.us
LoopInstSimplifyPass on for.inc.i.us186.us3650.us.us.us
LoopSimplifyCFGPass on for.inc.i.us186.us3650.us.us.us
LICMPass on for.inc.i.us186.us3650.us.us.us
LoopRotatePass on for.inc.i.us186.us3650.us.us.us
LICMPass on for.inc.i.us186.us3650.us.us.us
... (repeat)

Found via fuzzer.

[preames]

0229-after-LICMPass.ll.txt

While investigating this, I found a different compile time issue with simple-loop-unswitch and non-trivial unswitching. This one requires only a single pass invocation.

~/llvm-dev/build/bin/opt -passes="loop(simple-loop-unswitch)" 0229-after-LICMPass.ll -S -o /dev/null -enable-nontrivial-unswitch

This is not a hang per se. I left this running, and after about 15m it does eventually finish.

I haven't figured out if this is related to the original report, but I'm currently suspecting not as the invocation in the loop should be trivial unswitching only.

[preames]

In the multiple pass version, unswitch is producing (select i1 %c, i1 true, i1 false) - i.e. a trivial select - and loop inst simplify is cleaning it up. We're looping on that. If I adjust unswitch to eagerly clean this up, we still iterate - but with a different looking pattern.

From the delta, it looks like what was previously ~8 runs of unswitch is done in a single pass, and the new iteration is between loop rotate, the loop-simplify-cfg, and then unswitch. From the look of it, the two are basically collaborating to unroll a loop - one iteration at a time.

I suspect the second pattern existed before the loop-unswitch change, and just had a long enough period I didn't notice it manually.

[preames]

A correction to a previous assumption - this is not a hang. It's a very long compile, but an unmodified opt compiles this example in about 13 minutes. It is still interesting as a compile time outlier though.