Execution time of Bitcode Writer grows exponentially with number of loop rounds

[mikaelholmen]

Bugzilla Link	45545
Version	trunk
OS	Linux
Attachments	bbi-41722.ll reproducer
CC	@fhahn

Extended Description

Reproducer:
opt -o /dev/null bbi-41722.ll -indvars

In the input the number of loop iterations is determined by the constant in the following phi instruction:
%i.0 = phi i16 [ 12, %entry ], [ %dec, %for.body ]

With -debug-pass=Executions we can see the execution time for the 'Bitcode Writer' pass for different iteration counts.

N : time : bc output size
10: 0.3s : 1820
11: 1.6s : 1876
12: 8.1s : 1932
13: 35s : 1992
14: 3m : 2052

so the time increases exponentially but the size of the output doesn't.

The increased time seems to be spent in ValueEnumerator::EnumerateOperandType
called from the ValueEnumerator constructor:

for (const BasicBlock &BB : F)
  for (const Instruction &I : BB) {
    for (const Use &Op : I.operands()) {
      auto *MD = dyn_cast<MetadataAsValue>(&Op);
      if (!MD) {
        EnumerateOperandType(Op);
        continue;
      }

For N == 2 we get this load instruction after -indvars, as printed with -print-after-all:

store i16 sub (i16 zext (i1 icmp sgt (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16)) to i16), i16 select (i1 icmp slt (i16 and (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 add (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 xor (i16 lshr (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 15), i16 -1))), i16 0), i16 0, i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16))), i16* @​f.a, align 1

For N == 3:

store i16 sub (i16 zext (i1 icmp sgt (i16 sub (i16 zext (i1 icmp sgt (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16)) to i16), i16 select (i1 icmp slt (i16 and (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 add (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 xor (i16 lshr (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 15), i16 -1))), i16 0), i16 0, i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16))), i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16)) to i16), i16 select (i1 icmp slt (i16 and (i16 sub (i16 zext (i1 icmp sgt (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16)) to i16), i16 select (i1 icmp slt (i16 and (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 add (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 xor (i16 lshr (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 15), i16 -1))), i16 0), i16 0, i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16))), i16 add (i16 sub (i16 zext (i1 icmp sgt (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16)) to i16), i16 select (i1 icmp slt (i16 and (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 add (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 xor (i16 lshr (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 15), i16 -1))), i16 0), i16 0, i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16))), i16 xor (i16 lshr (i16 sub (i16 zext (i1 icmp sgt (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16)) to i16), i16 select (i1 icmp slt (i16 and (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 add (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 xor (i16 lshr (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 15), i16 -1))), i16 0), i16 0, i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16))), i16 15), i16 -1))), i16 0), i16 0, i16 sub (i16 zext (i1 icmp sgt (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16)) to i16), i16 select (i1 icmp slt (i16 and (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 add (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 xor (i16 lshr (i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16), i16 15), i16 -1))), i16 0), i16 0, i16 zext (i1 icmp slt (i16 zext (i1 icmp eq (i16** bitcast (i16* @​f.a to i16**), i16** @​f.c) to i16), i16 0) to i16))))), i16* @​f.a, align 1

etc.

I think that ValueEnumerator::EnumerateOperandType is called recursively on each operand in the constant expression.