GHC: Ticket #1512: NCG to handle cyclic fixups for rematching register assignment for jump blocks
http://ghc.haskell.org/trac/ghc/ticket/1512
<p>
joinToTargets in <a class="ext-link" href="http://darcs.haskell.org/ghc/compiler/nativeGen/RegisterAlloc.hs"><span class="icon"></span>RegisterAlloc.hs</a>
generates a jump to a particular target. On the first jump to a target, the virtual register assignment is associated with this target. All following jumps to the target must ensure that the current virtual register assignment matches that one of the target. If that's not the case, fixup code is generated before the branch instruction.
</p>
<p>
In rare cases, that occur when compiling the RTS on i386 in -fPIC -dynamic mode we have to generate cyclic fixup code. Here is one issue that comes from compiling PrimOps.cmm:
</p>
<p>
Assignment of target:
</p>
<ul><li>virtual register A in real register A
</li><li>virtual register B in real register B.
</li></ul><p>
Current assignment:
</p>
<ul><li>virtual register A in real register B
</li><li>virtual register B in real register A.
</li></ul><p>
Basically, we have to move A to B, and B to A. There is no move sequence that allows this without using a scratch register. <a class="ext-link" href="http://darcs.haskell.org/ghc/compiler/nativeGen/RegisterAlloc.hs"><span class="icon"></span>RegisterAlloc.hs</a> detects this by using stronglyConnCompR in joinToTargets (Line 869). At the moment, it does not provide a solution for this, it just fails.
</p>
<p>
My trivial approach would be:
</p>
<pre class="wiki">handleComponent (CyclicSCC ((vreg,src,dsts):rest))
= let sccs = stronglyConnCompR rest
in [makeMove vreg src (InMem empty_spill)] ++
concatMap handleComponent sccs ++
map (makeMove vreg (InMem empty_spill)) dsts
</pre><p>
I'm only having trouble to find empty_spill, namely an empty spill slot on the stack.
I have no clear idea what the (simulated) stack pointer is pointing at and whether it is save to assume that below (above?) is scratch space I can abuse for such a task.
</p>
en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/1512
Trac 1.0.1duncanMon, 09 Jul 2007 10:54:40 GMT
http://ghc.haskell.org/trac/ghc/ticket/1512#comment:1
http://ghc.haskell.org/trac/ghc/ticket/1512#comment:1
<pre class="wiki">Basically, we have to move A to B, and B to A. There is no move sequence that allows this without using a scratch register.
</pre><p>
As Ian pointed out, actually there is!
</p>
<pre class="wiki">x := x `xor` y;
y := x `xor` y;
x := x `xor` y
</pre><p>
This might give you a cheaper way out than spilling and using a scratch register.
</p>
TicketguestTue, 10 Jul 2007 11:17:47 GMT
http://ghc.haskell.org/trac/ghc/ticket/1512#comment:2
http://ghc.haskell.org/trac/ghc/ticket/1512#comment:2
<p>
I already considered xor swapping (that's why I restricted my claim to MOV instructions). <a class="ext-link" href="http://en.wikipedia.org/wiki/XOR_swap_algorithm"><span class="icon"></span>http://en.wikipedia.org/wiki/XOR_swap_algorithm</a> advises against using the XOR swap trick on modern CPUs and claims it'd be more inefficient than a scratch location.
</p>
<p>
Also using pure swapping doesn't sound very appealing to me. Consider a more complicated cycle involving more than just 2 nodes. The return value of the SCC doesn't give you the cycle, but a set of nodes that contains a cycle. It might contain leaves not involved in the cycle (as far as I understood it). How would you swap (InReg 1) with (InReg 2 and InMem 3)?
</p>
TicketiglooSat, 18 Aug 2007 00:50:03 GMTpriority changed; milestone set
http://ghc.haskell.org/trac/ghc/ticket/1512#comment:3
http://ghc.haskell.org/trac/ghc/ticket/1512#comment:3
<ul>
<li><strong>priority</strong>
changed from <em>normal</em> to <em>high</em>
</li>
<li><strong>milestone</strong>
set to <em>6.8</em>
</li>
</ul>
<p>
This is something we need to fix before 6.8, right?
</p>
TicketsimonmarMon, 20 Aug 2007 13:24:04 GMTstatus changed; resolution set
http://ghc.haskell.org/trac/ghc/ticket/1512#comment:4
http://ghc.haskell.org/trac/ghc/ticket/1512#comment:4
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
<p>
Already done:
</p>
<pre class="wiki">Sat Jul 14 09:32:41 BST 2007 Clemens Fruhwirth <clemens@endorphin.org>
* joinToTargets to emit fixup code even when movement graph contains cycles
</pre>
TicketiglooMon, 05 Nov 2007 15:03:50 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/1512#comment:5
http://ghc.haskell.org/trac/ghc/ticket/1512#comment:5
<ul>
<li><strong>milestone</strong>
changed from <em>6.8 branch</em> to <em>6.8.1</em>
</li>
</ul>
TicketsimonmarTue, 30 Sep 2008 15:39:46 GMTarchitecture changed
http://ghc.haskell.org/trac/ghc/ticket/1512#comment:6
http://ghc.haskell.org/trac/ghc/ticket/1512#comment:6
<ul>
<li><strong>architecture</strong>
changed from <em>Unknown</em> to <em>Unknown/Multiple</em>
</li>
</ul>
TicketsimonmarTue, 30 Sep 2008 15:50:52 GMTos changed
http://ghc.haskell.org/trac/ghc/ticket/1512#comment:7
http://ghc.haskell.org/trac/ghc/ticket/1512#comment:7
<ul>
<li><strong>os</strong>
changed from <em>Unknown</em> to <em>Unknown/Multiple</em>
</li>
</ul>
TicketsimonmarMon, 16 Nov 2009 13:11:39 GMTdifficulty changed
http://ghc.haskell.org/trac/ghc/ticket/1512#comment:8
http://ghc.haskell.org/trac/ghc/ticket/1512#comment:8
<ul>
<li><strong>difficulty</strong>
changed from <em>Moderate (1 day)</em> to <em>Moderate (less than a day)</em>
</li>
</ul>
Ticket