[LLVMbugs] [Bug 23538] New: ExitValue rewrite in IndVarSimplify introduced high cost operations in loop preheader

[bugzilla-daemon at llvm.org]

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

            Bug ID: 23538
           Summary: ExitValue rewrite in IndVarSimplify introduced high
                    cost operations in loop preheader
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: Loop Optimizer
          Assignee: unassignedbugs at nondot.org
          Reporter: wmi at google.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

Created attachment 14333
  --> https://llvm.org/bugs/attachment.cgi?id=14333&action=edit
testcase 1.cc

ExitValue rewrite in IndVarSimplify may introduce stmt (like div) with high
expansion cost in loop preheader. Existing implementation doesn't consider the
cost. If the loop is not hot enough or ExitValue rewrite doesn't reduce the
amount of IV processing in loop substantially, the high expansion cost in loop
preheader will be a problem.

The simple testcase 1.cc attached shows the problem.
~/workarea/llvm-r236609/build/bin/clang++ -O2 -S 1.cc

# BB#1:                                 # %while.body.lr.ph
-----------
        leal    -12(%rsi), %r8d
        movl    $2863311531, %ecx       # imm = 0xAAAAAAAB
        imulq   %r8, %rcx
        shrq    $35, %rcx
        shll    $2, %ecx
        leal    (%rcx,%rcx,2), %ecx
        subl    %ecx, %r8d
-----------
        movl    $-1640531527, %ecx      # imm = 0xFFFFFFFF9E3779B9
        .align  16, 0x90
.LBB0_2:                                # %while.body
                                        # =>This Inner Loop Header: Depth=1
        movl    (%rdi), %edx
        leal    (%rdx,%rdx), %eax
        andl    $16843008, %eax         # imm = 0x1010100
        addl    %ecx, %edx
        subl    %eax, %edx
        movl    %edx, 4(%rsp)
        addq    $12, %rdi
        addl    $-12, %esi
        cmpl    $11, %esi
        movl    %edx, %ecx
        ja      .LBB0_2

The insns between the two dash lines are the extra insns generated for ExitVal
rewrite in IndVarSimplify. 

It is not easy to evaluate whether ExitValue rewrite will or will not reduce
the amount of IV processing in loop in IndVarSimplify pass. Without profiling
information support, it is also difficult to know for sure whether a loop is
hot enough. So it may be good to be a little conservative here at least in
none-FDO mode (Feedback Optimization mode). 

I think ExitValue rewrite should use the similar logic as
LinearFunctionTestReplace which rewrites ICMP to ICMPZero only when expansion
cost is low.

The problem degraded one of our internal benchmark by 10% and another one by
1.5%. We didn't see >1% regression by simply turning off ExitValue rewrite.

-- 
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/20150515/e0ca4410/attachment.html>