Exponential output growth introduced in the IndVarsSimplify pass

[Quuxplusone]

Bugzilla Link	PR28166
Status	NEW
Importance	P normal
Reported by	David Stenberg (david.stenberg@ericsson.com)
Reported on	2016-06-17 09:02:24 -0700
Last modified on	2016-08-10 10:25:50 -0700
Version	trunk
Hardware	PC Linux
CC	hfinkel@anl.gov, llvm-bugs@lists.llvm.org
Fixed by commit(s)
Attachments	bugpoint-reduced-simplified.ll (1434 bytes, application/octet-stream) bugpoint-reduced-simplified2.ll (900 bytes, application/octet-stream)
Blocks
Blocked by
See also

Created attachment 16565
Reproducer

When running opt:

  opt -S -Oz -O1 bugpoint-reduced-simplified.ll

with the attached bugpoint-reduced-simplified.ll file, the resulting output
file seems to grow exponentially with the number of loop iterations (40 in the
bugpoint-reduced-simplified.ll), as seen here for N=20, 21, and 22:

  $ du -h out-*
  74M   out-20.ll
  148M  out-21.ll
  295M  out-22.ll

The problem seems to be introduced in the Induction Variable Simplification
pass, where the condition for the br instruction in bb3 grows:

N = 1:
  br i1 icmp sge (i16 ptrtoint (i16* @bar to i16), i16 0),
  label %bb4.preheader, label %bb5

N = 2:
  br i1 icmp sge (i16 xor (i16 zext (i1 icmp sge
  (i16 ptrtoint (i16* @bar to i16), i16 0) to i16),
  i16 ptrtoint (i16* @bar to i16)), i16 zext (i1 icmp sge
  (i16 ptrtoint (i16* @bar to i16), i16 0) to i16)),
  label %bb4.preheader, label %bb5

And so on.

The issue might be related to how the passes are executed, as passing any
combination of the -O[z123] flags triggers the issue. When passing just one of
the flags, the issue is not seen.

[Quuxplusone]

Attached bugpoint-reduced-simplified.ll (1434 bytes, application/octet-stream): Reproducer

[Quuxplusone]

Attached bugpoint-reduced-simplified2.ll (900 bytes, application/octet-stream): Simplified reproducer