Skip to content

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

@mikaelholmen

Description

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions