[llvm-bugs] [Bug 30895] New: Canonicalization/simplification loop between LoopSimplify and CFGSimplify can cause compilation time slowdown

[via llvm-bugs]

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

            Bug ID: 30895
           Summary: Canonicalization/simplification loop between
                    LoopSimplify and CFGSimplify can cause compilation
                    time slowdown
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: Loop Optimizer
          Assignee: unassignedbugs at nondot.org
          Reporter: igor at azulsystems.com
                CC: llvm-bugs at lists.llvm.org
    Classification: Unclassified

LoopSimplify requires loop preheader to dominate all exit blocks. In order to
achieve that it splits loop exit blocks that have predecessors outside of the
loop. CFGSimplify merges them back. This cycle repeats multiple times during
compilation.

This process causes around 40% compile time slowdown on one of our internal
out-of-tree tests. This test is somewhat absurd since it contains around 1700
loops nested in each other up to the 8th level.

You can observe described behaviour using this simple reproducer:

declare void @some_call()

define i32 @test(i32 %cnt, i32 %cnt-inner) personality i32* ()*
@"personality_function" {
entry:
  br label %loop

loop:
  %i = phi i32 [0, %entry], [%i.next, %loop-latch]
  invoke void @some_call()
    to label %inner-loop unwind label %exception1

inner-loop:
  %j = phi i32 [0, %loop], [%j.next, %inner-loop-latch]
  invoke void @some_call()
    to label %inner-loop-latch unwind label %exception1

inner-loop-latch:
  %j.next = add i32 %j, 1
  %inner-exit-cond = icmp sle i32 %j.next, %cnt-inner
  br i1 %inner-exit-cond, label %inner-loop, label %loop-latch

loop-latch:
  %i.next = add i32 %i, 1
  %exit-cond = icmp sle i32 %i.next, %cnt
  br i1 %exit-cond, label %loop, label %loop-normal-exit

loop-normal-exit:
  ret i32 0

exception1:
  %landing-pad1 = landingpad { i8*, i32 }
          cleanup
  ret i32 1

exception2:
  %landing-pad2 = landingpad { i8*, i32 }
          cleanup
  ret i32 2
}

declare i32* @"personality_function"()

-- 
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/20161103/f4d89ccc/attachment.html>