[LLVMbugs] [Bug 13361] New: LSR + SCEV "hangs" on reasonably sized test with sequence of loops

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=13361

             Bug #: 13361
           Summary: LSR + SCEV "hangs" on reasonably sized test with
                    sequence of loops
           Product: new-bugs
           Version: trunk
          Platform: PC
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: new bugs
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: atrick at apple.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified


Created attachment 8895
  --> http://llvm.org/bugs/attachment.cgi?id=8895
Reduced bitcode test case.

llc reduced.ll -time-passes
   1.5491 ( 98.7%)   0.0093 ( 73.2%)   1.5584 ( 98.5%)   1.5584 ( 98.5%)
      Loop Strength Reduction

Note that the original test case effectively hangs. This is a tiny example to
demonstrate the problem.

There appear to be two exponential algorithms that are multiplied.

Problem (1): LSR "cross-use offsets" performs a combinatorial search that is
exponentional in the SCEV recurrence depth. The recurence depth is the number
of loops in a sequence that affect some value.
Potential fix: Teach LSR not to explore the entire search space for a nested
recurrence.

Problem (2): SCEV getZeroExtend can be exponential in the depth of the
recurrence.
Potential fix: cache the AddRecs that are known not to overflow, or more
generally cache cast operations that were succesfully folded.

I'd like to fix LSR (problem #1) first. That will probably be sufficient for
this bug. Problem #2 is a fundamental design issue within SCEV. I don't see a
quick hack being very helpful in general.

-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.