[LLVMbugs] [Bug 17305] New: missed opportunity for associative FP math in summation reduction (pairwise summation)

[bugzilla-daemon at llvm.org]

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

            Bug ID: 17305
           Summary: missed opportunity for associative FP math in
                    summation reduction (pairwise summation)
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: kkhoo at perfwizard.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

With the -fassociative-math flag, can the summation below be transformed using
an algorithm like:
http://en.wikipedia.org/wiki/Pairwise_summation

?


$ ./clang -v
clang version 3.4 (trunk 190938)
Target: x86_64-apple-darwin11.4.2
Thread model: posix

$ cat no_add_tree.c 
double foo(double x0, double x1, double x2, double x3, double x4, double x5,
double x6, double x7) {
    return x0 + x1 + x2 + x3 + x4 + x5 + x6 + x7;
}

$ ./clang -S -O3 -fassociative-math -fomit-frame-pointer -march=corei7-avx
no_add_tree.c -o -
    .section    __TEXT,__text,regular,pure_instructions
    .globl    _foo
    .align    4, 0x90
_foo:                                   ## @foo
    .cfi_startproc
## BB#0:                                ## %entry
    vaddsd    %xmm1, %xmm0, %xmm0
    vaddsd    %xmm2, %xmm0, %xmm0
    vaddsd    %xmm3, %xmm0, %xmm0
    vaddsd    %xmm4, %xmm0, %xmm0
    vaddsd    %xmm5, %xmm0, %xmm0
    vaddsd    %xmm6, %xmm0, %xmm0
    vaddsd    %xmm7, %xmm0, %xmm0
    ret


Using pairwise addition, we should end up with something like this:
        vaddsd  %xmm1, %xmm0, %xmm0
        vaddsd  %xmm3, %xmm2, %xmm2
        vaddsd  %xmm5, %xmm4, %xmm4
        vaddsd  %xmm7, %xmm6, %xmm6
        vaddsd  %xmm2, %xmm0, %xmm0
        vaddsd  %xmm6, %xmm4, %xmm4
        vaddsd  %xmm4, %xmm0, %xmm0

The equivalent source code hack would be:
        x0 = x0 + x1;
        x2 = x2 + x3;
        x4 = x4 + x5;
        x6 = x6 + x7;
        x0 = x0 + x2;
        x4 = x4 + x6;
        return x0 + x4;

"iaca" (
http://software.intel.com/en-us/articles/intel-architecture-code-analyzer )
shows that the throughput of the reassociated code is 9 cycles vs. 21 cycles
for the original code on Sandy Bridge; latency is improved to 12 cycles from 21
cycles. 

Real timing on a Sandy Bridge system confirms that the reassociated code runs
faster.

-- 
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/20130920/787d7f63/attachment.html>