[LLVMbugs] [Bug 2066] New: Suboptimal code for factorial function

[bugzilla-daemon at cs.uiuc.edu]

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

           Summary: Suboptimal code for factorial function
           Product: new-bugs
           Version: unspecified
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: new bugs
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: sharparrow1 at yahoo.com
                CC: llvmbugs at cs.uiuc.edu


Testcase (from http://llvm.org/demo/index.cgi):

int power(int X) {
  if (X == 0) return 1;
  return X*power(X-1);
}

currently compiles to (with clang -emit-llvm-bc | opt -std-compile-opts):
define i32 @power(i32 %X) nounwind  {
entry:
        %cmp3 = icmp eq i32 %X, 0
        br i1 %cmp3, label %ifthen, label %ifend

ifthen:         ; preds = %ifend, %entry
        %accumulator.tr.lcssa = phi i32 [ 1, %entry ], [ %mul, %ifend ]
        ret i32 %accumulator.tr.lcssa

ifend:          ; preds = %ifend, %entry
        %indvar = phi i32 [ %indvar.next, %ifend ], [ 0, %entry ]
        %accumulator.tr1 = phi i32 [ %mul, %ifend ], [ 1, %entry ]
        %X.tr2 = sub i32 %X, %indvar
        %mul = mul i32 %X.tr2, %accumulator.tr1
        %indvar.next = add i32 %indvar, 1
        %exitcond = icmp eq i32 %indvar.next, %X
        br i1 %exitcond, label %ifthen, label %ifend
}

Having two induction variables makes this code longer than it needs to be. 
Only one induction variable should be needed.

x86 asm for main loop:
.LBB1_4:        # ifend
        imull   %esi, %eax
        decl    %esi
        incl    %edx
        cmpl    %ecx, %edx
        jne     .LBB1_4 # ifend

compared to gcc:
.L5:
        imull   %edx, %eax
        subl    $1, %edx
        jne     .L5


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