<html>
<head>
<base href="https://bugs.llvm.org/">
</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 - Register Coalescing: missed optimization opportunity"
href="https://bugs.llvm.org/show_bug.cgi?id=41864">41864</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Register Coalescing: missed optimization opportunity
</td>
</tr>
<tr>
<th>Product</th>
<td>libraries
</td>
</tr>
<tr>
<th>Version</th>
<td>8.0
</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>enhancement
</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>mgudim@gmail.com
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org
</td>
</tr></table>
<p>
<div>
<pre>In the course of our work, we came across an example which (as we believe)
proves that it is profitable to add a heuristics to decide the order in which
RegisterCoalescer looks at copies in a basic block.
We have the following pattern generated from an innermost loop with one basic
block body (unfortunately, we cannot post the exact IR):
# *** IR Dump After Live Variable Analysis ***:
BB#24: derived from LLVM BB %for.body181
%vreg381<def> = PHI %vreg361, <BB#23>, %vreg378, <BB#24>;
%vreg382<def> = PHI %vreg361, <BB#23>, %vreg378, <BB#24>;
...
STORE %vreg381, %vreg385, -2; mem:ST2[%269](noalias=!11);
...
%vreg373<def,tied1> = INST %vreg381<tied0>, %vreg387<kill>, %vreg382, 1;
...
%vreg378<def,tied1> = INST %vreg373<kill,tied0>, %vreg370<kill>,
%vreg382<kill>, 0;
...
CONDITIONAL_BRANCH <BB#24>;
# *** IR Dump After Two-Address instruction pass ***:
BB#24: derived from LLVM BB %for.body181
Predecessors according to CFG: BB#23 BB#24
%vreg382<def> = COPY %vreg639;
%vreg381<def> = COPY %vreg639<kill>;
STORE %vreg381, %vreg385, -2;
...
%vreg373<def> = COPY %vreg381;
%vreg373<def,tied1> = INST %vreg373<tied0>, %vreg387<kill>, %vreg382, 1;
...
%vreg378<def> = COPY %vreg373<kill>;
%vreg378<def,tied1> = INST %vreg378<tied0>, %vreg370<kill>, %vreg382<kill>,
0;
...
%vreg639<def> = COPY %vreg378<kill>;
...
CONDITIONAL_BRANCH<BB#24>;
The RegisterCoalescer works through the basic block from the first copy to last
as follows:
Remove %vreg382<def> = COPY %vreg639:
%vreg381<def> = COPY %vreg639;
%vreg369<def> = COPY %vreg639;
...
%vreg373<def> = COPY %vreg381;
%vreg373<def,tied1> = INSTR %vreg373<tied0>, %vreg644, %vreg639, 1;
...
%vreg378<def> = COPY %vreg373;
%vreg378<def,tied1> = INSTR %vreg378<tied0>, %vreg370, %vreg639, 0;
...
%vreg639<def> = COPY %vreg378;
...
CONDITIONAL_BRANCH<BB#24>;
Remove %vreg381<def> = COPY %vreg639:
BB#24: derived from LLVM BB %for.body181
Predecessors according to CFG: BB#23 BB#24
STORE %vreg639, %vreg642, -2;
...
%vreg373<def> = COPY %vreg639;
%vreg373<def,tied1> = INST %vreg373<tied0>, %vreg644, %vreg373, 1;
...
%vreg378<def> = COPY %vreg373;
%vreg378<def,tied1> = INST %vreg378<tied0>, %vreg370, %vreg639, 0;
...
%vreg639<def> = COPY %vreg378;
...
COND_BRANCH <BB#24>;
Remove %vreg373<def> = COPY %vreg639: Interference!
Remove %vreg378<def> = COPY %vreg373:
BB#24: derived from LLVM BB %for.body181
STORE %vreg639, %vreg642, -2; mem:ST2[%269](noalias=!11);
...
%vreg378<def> = COPY %vreg639;
%vreg378<def,tied1> = INSTR %vreg378<tied0>, %vreg644, %vreg378, 1;
...
%vreg378<def,tied1> = INSTR %vreg378<tied0>, %vreg370, %vreg639, 0;
...
%vreg639<def> = COPY %vreg378;
...
CONDITIONAL_BRANCH<BB#25>
Remove %vreg639<def> = COPY %vreg378: Interference!
So we end up with the following assembly code:
copy from v0 to v4
...
copy from v4 to v0
The last copy can be removed, as we have verified.
We believe this problem can be fixed in RegisterCoalescer. We hacked the
RegisterCoalescer so that it works through the copies in the problematic basic
block in the reversed order of the original (from last copy to the first). With
the reversed order the redundant copy disappears and correct assembly is
generated. This lets us conclude that there should be some heuristic for
ordering input copies or perhaps delaying the decision of coalescing.
We would like to hear community opinion on how to approach this problem. In
particular, should this kind of optimization be inside RegisterCoalescer? If
yes, has any work been done in this direction?
Ideally, we want to find a proper solution and contribute it to the llvm
project.
Thank you and looking forward to your suggestions,
Mikhail Gudim</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>