<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 --- - Redundant copy in reduction loop"
href="http://llvm.org/bugs/show_bug.cgi?id=22074">22074</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Redundant copy in reduction loop
</td>
</tr>
<tr>
<th>Product</th>
<td>libraries
</td>
</tr>
<tr>
<th>Version</th>
<td>trunk
</td>
</tr>
<tr>
<th>Hardware</th>
<td>All
</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>Common Code Generator Code
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>michael.m.kuperstein@intel.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>The code below performs a trivial reduction on an array (basically, calculating
a checksum):
target triple = "i386-linux"
define zeroext i16 @loop(i16* readonly %p, i16* readnone %q) #0 {
entry:
%cmp4 = icmp eq i16* %p, %q
br i1 %cmp4, label %while.end, label %while.body
while.body:
%v.06 = phi i32 [ %add, %while.body ], [ 0, %entry ]
%p.addr.05 = phi i16* [ %incdec.ptr, %while.body ], [ %p, %entry ]
%incdec.ptr = getelementptr inbounds i16* %p.addr.05, i32 1
%0 = load i16* %p.addr.05, align 2
%conv = zext i16 %0 to i32
%add = add i32 %conv, %v.06
%cmp = icmp eq i16* %incdec.ptr, %q
br i1 %cmp, label %while.cond.while.end_crit_edge, label %while.body
while.cond.while.end_crit_edge:
%phitmp = trunc i32 %add to i16
br label %while.end
while.end:
%v.0.lcssa = phi i16 [ %phitmp, %while.cond.while.end_crit_edge ], [ 0,
%entry ]
ret i16 %v.0.lcssa
}
The code we currently get for the loop body is:
.LBB0_1:
movl %eax, %esi
movzwl (%edx), %eax
addl $2, %edx
addl %esi, %eax
cmpl %edx, %ecx
jne .LBB0_1
.LBB0_2:
Instead of the expected:
.LBB0_1:
movzwl (%edx), %esi
addl $2, %edx
addl %esi, %eax
cmpl %edx, %ecx
jne .LBB0_1
.LBB0_2:
The problem is that instead of adding the loaded value into the accumulator, we
do the reverse, forcing us to copy the accumulator between iterations.
There are three different things here that could go right instead of going
wrong:
1) The two-address instruction pass tries to guess when it's worth to commute
the instruction when doing the 3-addr -> 2-addr transformation. The heuristic
there is rather limited, and it doesn't fire in this case.
2) The register coalescer also tries to commute two-address instructions when
it runs into situations it considers profitable.
Specifically, if it gets this:
BB#2:
%vreg3<def> = MOVZX32rm16 %vreg15, 1, %noreg, 0, %noreg; mem:LD2[%p.addr.05]
GR32:%vreg3,%vreg15
%vreg15<def,tied1> = ADD32ri8 %vreg15<tied0>, 2, %EFLAGS<imp-def,dead>;
GR32:%vreg15
%vreg3<def,tied1> = ADD32rr %vreg3<tied0>, %vreg14, %EFLAGS<imp-def,dead>;
GR32:%vreg3,%vreg14
CMP32rr %vreg7, %vreg15, %EFLAGS<imp-def>; GR32:%vreg7,%vreg15
%vreg14<def> = COPY %vreg3; GR32:%vreg14,%vreg3
JNE_4 <BB#2>, %EFLAGS<imp-use,kill>
JMP_4 <BB#3>
Where it can't coalesce vreg14 and vreg3 because of the def of vreg3 in the
beginning of the loop, it will commute the ADD32rr that is the def of the
copied register, making the copy a nop.
However, what we actually get is:
BB#0:
[...]
%vreg14<def> = MOV32r0 %EFLAGS<imp-def,dead>; GR32:%vreg14
[...]
BB#2:
%vreg0<def> = COPY %vreg14; GR32:%vreg0,%vreg14
%vreg14<def> = MOVZX32rm16 %vreg15, 1, %noreg, 0, %noreg; mem:LD2[%p.addr.05]
GR32:%vreg14,%vreg15
%vreg15<def,tied1> = ADD32ri8 %vreg15<tied0>, 2, %EFLAGS<imp-def,dead>;
GR32:%vreg15
%vreg14<def,tied1> = ADD32rr %vreg14<tied0>, %vreg0, %EFLAGS<imp-def,dead>;
GR32:%vreg14,%vreg0
CMP32rr %vreg7, %vreg15, %EFLAGS<imp-def>; GR32:%vreg7,%vreg15
JNE_4 <BB#2>, %EFLAGS<imp-use,kill>
JMP_4 <BB#3>
The copy we have is the remnant of PHI elimination, and can see two defs of
vreg14. This pattern isn't caught by the current code, so we don't commute.
3) The reason we see the "wrong" copy has to do with the order register
coalescing tries to eliminate the copies. When eliminating the copies bottom
-up (-join-globalcopies=false) we end up with the copy the coalescer will try
to commute. However, with join-globalcopies enabled, we try to eliminate the
"outgoing" copy of %vreg14 first, and get stuck with the one we don't know how
to handle.
Any suggestions on where this should be fixed - (1), (2) or (3)?
I'm a bit at a loss...</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>