<html>
<head>
<base href="https://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 --- - DAG-Level reassociation makes expression trees deeper"
href="https://llvm.org/bugs/show_bug.cgi?id=30657">30657</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>DAG-Level reassociation makes expression trees deeper
</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>Linux
</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>Common Code Generator Code
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>mkuper@google.com
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org
</td>
</tr>
<tr>
<th>Classification</th>
<td>Unclassified
</td>
</tr></table>
<p>
<div>
<pre>As part of the DAG combiner's efforts to perform constant-folding, we have the
following two combines:
// (op (op x, c1), y) -> (op (op x, y), c1) iff x+c1 has one use
// (op x, (op y, c1)) -> (op (op x, y), c1) iff x+c1 [sic] has one use
These combines take constants and bring them closer to the expression tree's
root. This works well if we have several constants in the expression tree, but
makes the tree deeper for no good reason if there's only one constant - which
serves to reduce available ILP.
For example, consider:
define i32 @better(i32 %a, i32 %b) {
%r1 = xor i32 %a, 14
%r2 = xor i32 %b, 11
%r3 = xor i32 %r1, %r2
ret i32 %r3
}
define i32 @worse(i32 %a, i32 %b, i32 %c) {
%r1 = xor i32 %a, 14
%r2 = xor i32 %b, %c
%r3 = xor i32 %r1, %r2
ret i32 %r3
}
With the current reassociation step we get, with bin/llc -mtriple=x86_64
-mcpu=nehalem:
(Note that without specifying a CPU we get the same bad re-association from the
machine combiner, but that's justifiable, since without scheduling information,
it can't make a reasonable decision):
better:
xorl %esi, %edi
xorl $5, %edi
movl %edi, %eax
retq
worse:
xorl %edx, %esi
xorl %edi, %esi
xorl $14, %esi
movl %esi, %eax
retq
Without reassociation, we get:
better:
xorl $14, %edi
xorl $11, %esi
xorl %edi, %esi
movl %esi, %eax
retq
worse:
xorl $14, %edi
xorl %edx, %esi
xorl %edi, %esi
movl %esi, %eax
retq
So, for the 'worse' case, we now have a 3-instruction critical path, instead of
a 2-instruction one.
I'm not really sure what we should do about this. The three options I see:
1) Stop doing re-association in DAG. We already perform reassociation in the
IR, and should come out of the IR with good, balanced trees. Lowering may
introduce additional constants, but at least the common case of GEP lowering
doesn't seem to create patterns that require this transformation.
2) Do better re-association in DAG - try to push all constants together, but,
say, towards, the rightmost leaf, instead of towards the root. I don't quite
see how to do this with local transformations, though.
3) Leave the DAG combine as is, and let the MachineCombiner undo this
per-target. I think that's not very appealing. While, in a sense, this is the
MachineCombiner's job - what the DAG combiner does seems decidedly
"non-canonical" - it's intentionally making the expression tree worse.
More practically speaking, fixing this post-selection will not be very easy -
for example, on x86, we may need to undo LEA selection.
Any thoughts?</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>