[LLVMbugs] [Bug 2242] New: Canonicalization of induction variables needs some heuristics

[bugzilla-daemon at cs.uiuc.edu]

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

           Summary: Canonicalization of induction variables needs some
                    heuristics
           Product: new-bugs
           Version: unspecified
          Platform: PC
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: new bugs
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: dalej at apple.com
                CC: llvmbugs at cs.uiuc.edu


The optimization to construct canonical induction variables needs some
heuristics to determine whether it's a good idea to do this.  Take the example
in UnitTests/2008-04-18-LoopBug.c.  Using opt -std-compile-opts we get this on
Darwin x86-32:
LBB1_1: ## bb.preheader
        movl    $3, %edx
        subl    %eax, %edx
        movl    %eax, %esi
        notl    %esi
        cmpl    $4294967293, %esi
        movl    $1, %esi
        cmovb   %esi, %edx
        xorl    %esi, %esi
        movl    %ecx, %edi
        .align  4,0x90
LBB1_2: ## bb
        movl    8(%edi), %ebx
        movl    %ebx, 12(%edi)
        addl    $4294967292, %edi
        incl    %esi
        cmpl    %edx, %esi
        jne     LBB1_2  ## bb
Removing -indvars from the opt line results in:
LBB1_1: ## entry.bb_crit_edge
        movl    $3, %edx
        movl    %ecx, %esi
        .align  4,0x90
LBB1_2: ## bb
        movl    8(%esi), %edi
        movl    %edi, 12(%esi)
        addl    $4294967292, %esi
        decl    %edx
        cmpl    %eax, %edx
        ja      LBB1_2  ## bb
Not much of an optimization.  Things to consider in the heuristics (there are
probably more):
- If we can share/eliminate multiple induction variables by using a canonical
form, that is a good thing.
- If the replacement initialization expression is more complex than the
original, that's a bad thing.  (that's what happens here)
- Testing against a constant can be better than against a non-constant because
of register pressure.
- Some targets have a decrement-and-branch-on-nonzero instruction; using that
is a win when available (currently unimplemented in llvm).
The tradeoff among these is not obvious and is target-dependent.


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