[llvm-bugs] [Bug 45545] New: Execution time of Bitcode Writer grows exponentially with number of loop rounds

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=45545

            Bug ID: 45545
           Summary: Execution time of Bitcode Writer grows exponentially
                    with number of loop rounds
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Bitcode Writer
          Assignee: unassignedbugs at nondot.org
          Reporter: mikael.holmen at ericsson.com
                CC: llvm-bugs at lists.llvm.org

Created attachment 23359
  --> https://bugs.llvm.org/attachment.cgi?id=23359&action=edit
bbi-41722.ll reproducer

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.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20200415/c3fd2901/attachment-0001.html>