[llvm-bugs] [Bug 52374] New: Jump threading is quadratic on large consecutive swicthes

[via llvm-bugs]

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

            Bug ID: 52374
           Summary: Jump threading is quadratic on large consecutive
                    swicthes
           Product: libraries
           Version: 11.0
          Hardware: PC
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: tamas at hudson-trading.com
                CC: llvm-bugs at lists.llvm.org

Created attachment 25410
  --> https://bugs.llvm.org/attachment.cgi?id=25410&action=edit
Script to generate large example

struct Message0 { static int id1; static int id2; };
struct Message1 { static int id1; static int id2; };
int* getId(int id) {
  int id1 = 0;
  switch (id) {
    case 0:
      id1 = Message0::id1;
      break;
    case 1:
      id1 = Message1::id1;
      break;
  }
  int* data = new int[1 + id1 % 4];
  switch (id) {
    case 0:
      data[0] = Message0::id2;
      break;
    case 1:
      data[0] = Message1::id2;
      break;
  }
  return data;
}

If I take the above code but instead of having 2 different types of messages I
have 100+ messages then the "Jump threading" pass will become quadratic in the
number of cases when compiling with -O3. With 2000 different messages it takes
over a minute to compile the above file while if I break up the function so
that the two switches are in different functions than it compiles in ~0.5s
(while g++*10 compiles the original file in ~4s).

A larger example can be generated with "python make_cc.py <num_structs>".

-- 
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/20211101/0b9ba64a/attachment.html>