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

bugzilla-daemon at llvm.org bugzilla-daemon at llvm.org
Fri Sep 20 12:49:01 PDT 2013

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

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
.section    __TEXT,__text,regular,pure_instructions
.globl    _foo
.align    4, 0x90
_foo:                                   ## @foo
.cfi_startproc
## BB#0:                                ## %entry
ret

Using pairwise addition, we should end up with something like this:

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