[LLVMbugs] [Bug 23816] New: Invariant loads are not hoisted all the way out of certain simple nested loops

[bugzilla-daemon at llvm.org]

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

            Bug ID: 23816
           Summary: Invariant loads are not hoisted all the way out of
                    certain simple nested loops
           Product: tools
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: opt
          Assignee: unassignedbugs at nondot.org
          Reporter: broune at google.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

In this simple example, *a is hoisted out of the inner loop, but not out of the
outer loop with -O2. I think -O2 should be powerful enough to hoist *a out of
both loops for this example.

__attribute__((noinline))
float computeSum(float* a, int N, int M) {
  float sum = 0;
#pragma nounroll
  for (int i = 0; i < N; ++i) {
#pragma nounroll
    for (int j = 0; j < M; ++j) {
      sum += *a;
    }
  }
  return sum;
}

int main(int argc, char** argv) {
  float a = 42;
  return computeSum(&a, 1000, 1);
}

The reason is that -O2 does not have loop unswitching enabled. To have a safe
place to hoist *a out to, we need to loop unswitch on the condition M > 0. I
assume loop unswitching is disabled because it can cause code bloat and slower
code in some cases, though note that in this case, the version of the loop for
M <= 0 does nothing, so a safe version of loop unswitching that only fires on
such cases could run with -O2. This wouldn't work for cases where the outer
loop does more than just run an inner loop, but it would be a good start and it
would also speed things up by not having to check M>0 for every iteration of
the outer loop.

An alternative would be for licm to introduce a check for M>0 outside the outer
loop, which would create a safe place to put the load.

With -O3 the load does get hoisted all the way out as loop unswitching is
enabled there. However, loop unswitching only fires on loops that are smaller
than a threshold. If we set the threshold to a smaller value like 10, to
simulate a larger loop, then loop unswitching does not fire here and the load
does not get hoisted even for -O3. The loop unswitch pass does have code to
detect trivial cases where one of the two versions of the loop is empty, but
it's not powerful enough to recognize that for this example (it mostly detects
cases similar to "if (loop-invariant) break;").

This bug is for -O2 to handle (i.e. hoist loads all the way out) the above
simple example and for -O3 to handle similar loops that are larger than the
threshold for loop unswitching.

-- 
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/20150611/8efe4ead/attachment.html>