[llvm-bugs] [Bug 24680] New: Very long compile time caused by unfolded constant select

[via llvm-bugs]

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

            Bug ID: 24680
           Summary: Very long compile time caused by unfolded constant
                    select
           Product: new-bugs
           Version: trunk
          Hardware: All
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: rob.lougher at gmail.com
                CC: llvm-bugs at lists.llvm.org
    Classification: Unclassified

Compiling the following test program with:

clang -O2 -emit-llvm -S test.cpp

Will cause the compiler to hang.

// ===================== test.cpp ==================================
typedef float __attribute__((ext_vector_type(16))) v16;
typedef long long __attribute__((ext_vector_type(8))) l8;

bool foo();

static v16 bar(v16 in) {
  for (unsigned i = 0; i < 16; ++i)
    if (foo())
      in[i] = 1;
  return in;
}

static v16 baz(v16 in) {
  for (unsigned i = 0; i < 16; ++i)
    if ((in[i]) > 1)
      in[i] += 1;
  return in;
}

v16 test518() {
  union {
    l8 l;
    v16 v;
  };
  l = (l8) {(long long)&baz};
  return bar(baz(v));
}
// =================================================================


The hang is not infinite as reducing the size of the loops allows
the compiler to complete.

Investigation of the hang indicates that it is caused by instruction
combining creating a huge constant select instruction (after inlining
and unrolling).  We start with an initial constant select which cannot be
folded - instruction combining then combines this with other instructions
to create a larger instruction which also cannot be folded.  This continues
leading to a massive tree.  The asm writer then hangs traversing this tree
when writing the select instruction (the bitcode writer similarly hangs
when enumerating values).

The size of the .ll file for loops of size N shows that the tree
increases rapidly as N increases:

1 60K
2 1.1M
3 19M
4 328M
5 5.8G
6 70+G

The reason the constant select cannot be folded is because it has
the address of a function embedded in it (although constant the value
is not known at compile time).  This can be seen in the smaller
example:

int test() {
  return ((long long)&test)&4 ? 0 : 1;
}

This generates:

define i32 @_Z4testv() {
entry:
  ret i32 select (i1 icmp ne (i64 and
     (i64 ptrtoint (i32 ()* @_Z4testv to i64), i64 4), i64 0), i32 0, i32 1)
}

-- 
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/20150902/9df8d6d1/attachment.html>