[LLVMbugs] [Bug 20813] New: Failure to remove trivial loop iterations

[bugzilla-daemon at llvm.org]

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

            Bug ID: 20813
           Summary: Failure to remove trivial loop iterations
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: Loop Optimizer
          Assignee: unassignedbugs at nondot.org
          Reporter: listmail at philipreames.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

Created attachment 12963
  --> http://llvm.org/bugs/attachment.cgi?id=12963&action=edit
C++ source code for example

Given a loop where some of the iterations are trivial, LLVM current fails to
change the iteration space to remove them.  Consider this example:
void test_cont_high_gt() {
  for(int i = 0; i < 20; i++) {
    if( i > 10 ) continue;
    counter++;
  }
}

In this example, iterations 10+ of this loop can simple be removed.  This would
leave a substaintially simpiler loop:
void test_cont_high_gt() {
  for(int i = 0; i < 11; i++) {
    counter++;
  }
}

The attached file has a number of variants of this example.  This does not
appear to be a pass ordering problem.  Running the IR through O3 repeatedly
does not improve the quality.

I suspect this particular pattern is simply a missing case from LoopSimplify. 
By inspecting the exit conditions of the loop in combination with the induction
variable, we should be able to rewrite the range of the induction variable to
shrink the iteration space.  

This example can also be viewed as a special case of loop splitting (i.e.
dividing the loop iteration space into two non-overlapping sections via two
loops) followed by dead loop deletion.  I doubt it is worth implementing the
more general optimization strategy (loop splitting) just to get this case.

-- 
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/20140829/724a643e/attachment.html>