<html>
<head>
<base href="http://llvm.org/bugs/" />
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW --- - missed opportunity for associative FP math in summation reduction (pairwise summation)"
href="http://llvm.org/bugs/show_bug.cgi?id=17305">17305</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>missed opportunity for associative FP math in summation reduction (pairwise summation)
</td>
</tr>
<tr>
<th>Product</th>
<td>libraries
</td>
</tr>
<tr>
<th>Version</th>
<td>trunk
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>All
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>normal
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>Scalar Optimizations
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>kkhoo@perfwizard.com
</td>
</tr>
<tr>
<th>CC</th>
<td>llvmbugs@cs.uiuc.edu
</td>
</tr>
<tr>
<th>Classification</th>
<td>Unclassified
</td>
</tr></table>
<p>
<div>
<pre>With the -fassociative-math flag, can the summation below be transformed using
an algorithm like:
<a href="http://en.wikipedia.org/wiki/Pairwise_summation">http://en.wikipedia.org/wiki/Pairwise_summation</a>
?
$ ./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" (
<a href="http://software.intel.com/en-us/articles/intel-architecture-code-analyzer">http://software.intel.com/en-us/articles/intel-architecture-code-analyzer</a> )
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.</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>