-
Notifications
You must be signed in to change notification settings - Fork 14.6k
Description
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.