[LLVMbugs] [Bug 10880] New: indvars doesn't update scev's analyses, for the worse

[bugzilla-daemon at llvm.org]

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

           Summary: indvars doesn't update scev's analyses, for the worse
           Product: libraries
           Version: trunk
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: Loop Optimizer
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: nicholas at mxc.ca
                CC: llvmbugs at cs.uiuc.edu, atrick at apple.com


Created an attachment (id=7233)
 --> (http://llvm.org/bugs/attachment.cgi?id=7233)
testcase

This testcase is a simplified version of:

  vector<int> v;
  for (int i = 0; i < n; ++i)
    v[i]++;

Note that vector<int>::operator[] takes a int64, while the index is an int32.
This is an extremely common pattern in our (Google's) codebase, thanks to our
style rules.

The attached testcase is from right before we go into -indvars. The main
problem is visible if you just run -O2 over it, there's an extra
add(zext(add(n, 1)), -1) in the middle. (The slowdown each time is small, but
over our codebase, it accumulates, and GCC doesn't have this problem.)

What happened? Let's take a look:
$ opt -analyze -scalar-evolution 2011-01-17-LinearReplaceForgetLoop.ll
[...]
Determining loop execution counts for: @test
Loop %for.body: backedge-taken count is (-1 + %n)
Loop %for.body: max backedge-taken count is 2147483646
$ opt -indvars -analyze -scalar-evolution 2011-01-17-LinearReplaceForgetLoop.ll
[...]
Determining loop execution counts for: @test
Loop %for.body: backedge-taken count is (-1 + %n)
Loop %for.body: max backedge-taken count is 2147483646
$ opt -indvars 2011-01-17-LinearReplaceForgetLoop.ll | opt -analyze
-scalar-evolution
[...]
Determining loop execution counts for: @test
Loop %for.body: backedge-taken count is (-1 + (zext i32 %n to i64))
Loop %for.body: max backedge-taken count is (-1 + (zext i32 %n to i64))

Indvars changed the backedge-taken count (consider %n = 0), but only in cases
where the loop wouldn't be entered anyways. However, SCEV doesn't do enough
analysis to determine what happened. It also bails on the max backedge-taken
count.

Finally, if you run "opt -indvars 2011-01-17-LinearReplaceForgetLoop.ll | opt
-O2 -S -o -", then the unnecessary +1/-1 pairing around the zext is gone. This
is directly caused by the different information returned by SCEV, not by other
optz'ns happening in the -O2 pipeline.

-- 
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.