[llvm-bugs] [Bug 25005] New: Loop rotate is breaking SCEV when ran before induction variable substitution

[via llvm-bugs]

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

            Bug ID: 25005
           Summary: Loop rotate is breaking SCEV when ran before induction
                    variable substitution
           Product: new-bugs
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: mehdi.amini at apple.com
                CC: llvm-bugs at lists.llvm.org
    Classification: Unclassified

Created attachment 14963
  --> https://llvm.org/bugs/attachment.cgi?id=14963&action=edit
Sample C++

Playing with the LTO pipeline, I obtained at some point a 4000 times speedup on 
SingleSource/Benchmarks/Shootout/nestedloop.c (basically the loop is fully
eliminated).
A quick hack to run loop-rotate after indvars (or vice-versa) showed that there
is potential for improvement in multiple SPEC benchmarks as well.

Taking as a basic example this loop nest:

for i=0; i<n; ++i
 for j=0; i<m; ++j
   ++result


Here is what's going on if I understand correctly:

Loop rotation will turn:

while(j < m) {
  ++result
} 

into:

if (m > 0) {
  do {
    ++result
  } while (j < m)
}

Induction variable simplication is able to do:

if (m > 0) {
  do {
    // nothing important
  } while (j < m)
  result += m;
}

The problem is that from the point of view of the enclosing loop it will be:

do {
  if (m > 0) {
    do {
      // nothing important
    } while (j < m)
    result += m;
  }
  // result = result + max(0, m)   <--- SCEV can't figure this out
} while (i < n)

There is a test in the body of the enclosing loop, SCEV doesn't know how to
join the result value at the exit of the test.
We would want SCEV to figure out that the join after the branch is possible
with a "max" as shown in the comment above in the code snippet.

-- 
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/20150930/49fe6232/attachment.html>