joinToTargets to emit fixup code even when movement graph contains cycles

First, cycles can only start of with registers and their destination
must involve a register location. This is because memory locations are
allocated exclusively for a virtual register and hence can never cause
a conflict in the assignment, hence need no fixup code. Therefore, we
only have to deal with InReg -> InReg, or InReg -> InReg/InMem
movements.

The strategy is to take the first cycle element, which is guaranteed
to start with a register, spill it to a fresh memory location, compute
the fixup for the rest, and restore from the spill slot to its
destinations. The "rest" will degenerate into an acyclic scc, so we do
not need take care of the empty list case in CyclicScc.
 ***END OF DESCRIPTION***

Place the long patch description above the ***END OF DESCRIPTION*** marker.
The first line of this file will be the patch name.

This patch contains the following changes:

M ./compiler/nativeGen/RegisterAlloc.hs -6 +27

diff --git a/compiler/nativeGen/RegisterAlloc.hs b/compiler/nativeGen/RegisterAlloc.hs
index 20f7b61..8f7a656 100644 (file)
--- a/compiler/nativeGen/RegisterAlloc.hs
+++ b/compiler/nativeGen/RegisterAlloc.hs
@@ -901,11 +901,31 @@ joinToTargets block_live new_blocks instr (dest:dests) = do
                -- we have eliminated any possibility of single-node cylces
                -- in expandNode above.
                   handleComponent (AcyclicSCC (vreg,src,dsts))
-                      = map (makeMove vreg src) dsts
-                  handleComponent (CyclicSCC things)
-                      = panic $ "Register Allocator: handleComponent: cyclic"
-                                ++ " (workaround: use -fviaC)"
-                  
+                      = return $ map (makeMove vreg src) dsts
+
+               -- we can not have cycles that involve memory
+               -- locations as source nor as single destination
+               -- because memory locations (stack slots) are
+               -- allocated exclusively for a virtual register and
+               -- therefore can not require a fixup
+                  handleComponent (CyclicSCC ((vreg,src@(InReg sreg),dsts):rest))
+                      = do
+                          spill_id <- getUniqueR
+                          (saveInstr,slot) <- spillR (RealReg sreg) spill_id
+                          remainingFixUps <- mapM handleComponent (stronglyConnCompR rest)
+                          restoreAndFixInstr <- getRestoreMoves dsts slot
+                          return ([instr] ++ concat remainingFixUps ++ restoreAndFixInstr)
+                        where
+                          getRestoreMoves [r@(InReg reg), mem@(InMem _)] slot
+                            = do
+                                restoreToReg <- loadR (RealReg reg) slot
+                                return $ [restoreToReg, makeMove vreg r mem]
+                          getRestoreMoves [InReg reg] slot
+                            = loadR (RealReg reg) slot >>= return . (:[])
+                          getRestoreMoves [InMem _] _ = panic "getRestoreMoves can not handle memory only restores"
+                          getRestoreMoves _ _ = panic "getRestoreMoves unknown case"
+                  handleComponent (CyclicSCC _)
+                      = panic "Register Allocator: handleComponent cyclic"
                   makeMove vreg (InReg src) (InReg dst)
                       = mkRegRegMoveInstr (RealReg src) (RealReg dst)
                   makeMove vreg (InMem src) (InReg dst)
@@ -918,8 +938,9 @@ joinToTargets block_live new_blocks instr (dest:dests) = do
                                 ++ " (workaround: use -fviaC)"
             
               block_id <- getUniqueR
+              fixUpInstrs <- mapM handleComponent sccs
               let block = BasicBlock (BlockId block_id) $
-                      concatMap handleComponent sccs ++ mkBranchInstr dest
+                      concat fixUpInstrs ++ mkBranchInstr dest
               let instr' = patchJump instr dest (BlockId block_id)
               joinToTargets block_live (block : new_blocks) instr' dests
   where