<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On Sep 4, 2010, at 5:40 PM, Eli Friedman wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; font-family: Optima; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><span class="Apple-style-span" style="font-family: monospace; ">If you want to take a look at this yourself, the issue is easy to<br>reproduce with Thumb1:<br></span></span></blockquote></div><br><div>Thanks, Eli. Nice catch!</div><div><br></div><div>This IR:</div><div><br></div><div><div>target triple = "thumbv5-u-u"</div><div><br></div><div>define arm_aapcscc i64 @foo(i64 %a, i64 %b) nounwind readnone {</div><div>entry:</div><div> %xor = xor i64 %a, 18 ; <i64> [#uses=1]</div><div> %xor2 = xor i64 %xor, %b ; <i64> [#uses=1]</div><div> ret i64 %xor2</div><div>}</div></div><div><br></div><div>produces these instructions before coalescing:</div><div><br></div><div><div>4L %reg16387<def> = COPY %R3<kill></div><div>12L %reg16386<def> = COPY %R2<kill></div><div>28L %reg16384<def> = COPY %R0<kill></div><div>36L %reg16388<def> = COPY %reg16385<kill></div><div>44L %reg16388<def>, %CPSR<def,dead> = tEOR %reg16388, %reg16387<kill>, pred:14, pred:%reg0</div><div>56L %reg16389<def> = COPY %reg16384<kill></div><div>64L %reg16389<def>, %CPSR<def,dead> = tEOR %reg16389, %reg16386<kill>, pred:14, pred:%reg0</div><div>76L %reg16390<def>, %CPSR<def,dead> = tMOVi8 18, pred:14, pred:%reg0</div><div>88L %reg16391<def> = COPY %reg16390<kill></div><div>96L %reg16391<def>, %CPSR<def,dead> = tEOR %reg16391, %reg16389<kill>, pred:14, pred:%reg0</div><div>108L %R0<def> = COPY %reg16391<kill></div><div>116L %R1<def> = COPY %reg16388<kill></div><div>128L tBX_RET %R0<imp-use,kill>, %R1<imp-use,kill></div></div><div><br></div><div>and after:</div><div><br></div><div><div>44L %R1<def>, %CPSR<def,dead> = tEOR %R1, %R3<kill>, pred:14, pred:%reg0</div><div>56L %reg16389<def> = COPY %R0<kill></div><div>64L %reg16389<def>, %CPSR<def,dead> = tEOR %reg16389, %R2<kill>, pred:14, pred:%reg0</div><div>76L %R0<def>, %CPSR<def,dead> = tMOVi8 18, pred:14, pred:%reg0</div><div>96L %R0<def>, %CPSR<def,dead> = tEOR %R0, %reg16389<kill>, pred:14, pred:%reg0</div><div>128L tBX_RET %R0<imp-use,kill>, %R1<imp-use,kill></div></div><div><br></div><div>We see, as Borja pointed out, that %R0 from the 108L COPY has been joined with %reg16391 and %reg16390 so it is too late to commute the xor.</div><div><br></div><div>Passing -disable-physical-join to prevent the %R0 sabotage, we get:</div><div><br></div><div><div>4L %reg16387<def> = COPY %R3<kill>; tGPR:%reg16387</div><div>12L %reg16386<def> = COPY %R2<kill>; tGPR:%reg16386</div><div>20L %reg16388<def> = COPY %R1<kill>; tGPR:%reg16388</div><div>28L %reg16389<def> = COPY %R0<kill>; tGPR:%reg16389</div><div>44L %reg16388<def>, %CPSR<def,dead> = tEOR %reg16388, %reg16387<kill>, pred:14, pred:%reg0; tGPR:%reg16388,16387</div><div>64L %reg16389<def>, %CPSR<def,dead> = tEOR %reg16389, %reg16386<kill>, pred:14, pred:%reg0; tGPR:%reg16389,16386</div><div>76L %reg16391<def>, %CPSR<def,dead> = tMOVi8 18, pred:14, pred:%reg0; tGPR:%reg16391</div><div>96L %reg16391<def>, %CPSR<def,dead> = tEOR %reg16391, %reg16389<kill>, pred:14, pred:%reg0; tGPR:%reg16391,16389</div><div>108L %R0<def> = COPY %reg16391<kill>; tGPR:%reg16391</div><div>116L %R1<def> = COPY %reg16388<kill>; tGPR:%reg16388</div><div>128L tBX_RET %R0<imp-use,kill>, %R1<imp-use,kill></div></div><div><br></div><div>It is not easy to see here that the 96L tEOR should be commuted. You would have to notice that the hints for %reg16389 and %reg16391 are clashing.</div><div><br></div><div>After register allocation with hinting it becomes:</div><div><br></div><div><div> %R1<def>, %CPSR<def,dead> = tEOR %R1, %R3<kill>, pred:14, pred:%reg0</div><div> %R0<def>, %CPSR<def,dead> = tEOR %R0, %R2<kill>, pred:14, pred:%reg0</div><div> %R2<def>, %CPSR<def,dead> = tMOVi8 18, pred:14, pred:%reg0</div><div> %R2<def>, %CPSR<def,dead> = tEOR %R2, %R0<kill>, pred:14, pred:%reg0</div><div> %R0<def> = COPY %R2<kill></div><div> tBX_RET %R0<imp-use,kill>, %R1<imp-use,kill></div></div><div><br></div><div><br></div><div>There are two fundamental deficiencies here:</div><div><br></div><div>1. The coalescer is not very good at handling conflicting joins. The examples show that different orders of joining can give different results. The coalescer uses heuristics to pick an order. It doesn't try to find an optimal order.</div><div><br></div><div>2. Commuting two-address instructions is not really integrated into the coalescer algorithm. It is more of an afterthought, calling RemoveCopyByCommutingDef when a copy could otherwise not be removed.</div><div><br></div><div>/jakob</div><div><br></div><div><br></div></body></html>