+
+
+-- | Construct a graph of register/spill movements.
+--
+-- We cut some corners by
+-- a) not handling cyclic components
+-- b) not handling memory-to-memory moves.
+--
+-- Cyclic components seem to occur only very rarely,
+-- and we don't need memory-to-memory moves because we
+-- make sure that every temporary always gets its own
+-- stack slot.
+
+makeRegMovementGraph :: RegMap Loc -> RegMap Loc -> [(Unique, Loc, [Loc])]
+makeRegMovementGraph adjusted_assig dest_assig
+ = let
+ mkNodes src vreg
+ = expandNode vreg src
+ $ lookupWithDefaultUFM_Directly
+ dest_assig
+ (panic "RegisterAlloc.joinToTargets")
+ vreg
+
+ in [ node | (vreg, src) <- ufmToList adjusted_assig
+ , node <- mkNodes src vreg ]
+
+-- The InBoth handling is a little tricky here. If
+-- the destination is InBoth, then we must ensure that
+-- the value ends up in both locations. An InBoth
+-- destination must conflict with an InReg or InMem
+-- source, so we expand an InBoth destination as
+-- necessary. An InBoth source is slightly different:
+-- we only care about the register that the source value
+-- is in, so that we can move it to the destinations.
+
+expandNode vreg loc@(InReg src) (InBoth dst mem)
+ | src == dst = [(vreg, loc, [InMem mem])]
+ | otherwise = [(vreg, loc, [InReg dst, InMem mem])]
+
+expandNode vreg loc@(InMem src) (InBoth dst mem)
+ | src == mem = [(vreg, loc, [InReg dst])]
+ | otherwise = [(vreg, loc, [InReg dst, InMem mem])]
+
+expandNode vreg loc@(InBoth _ src) (InMem dst)
+ | src == dst = [] -- guaranteed to be true
+
+expandNode vreg loc@(InBoth src _) (InReg dst)
+ | src == dst = []
+
+expandNode vreg loc@(InBoth src _) dst
+ = expandNode vreg (InReg src) dst
+
+expandNode vreg src dst
+ | src == dst = []
+ | otherwise = [(vreg, src, [dst])]
+
+
+-- | Make a move instruction between these two locations so we
+-- can join together allocations for different basic blocks.
+--
+makeMove :: Int -> Unique -> Loc -> Loc -> RegM Instr
+makeMove delta vreg (InReg src) (InReg dst)
+ = do recordSpill (SpillJoinRR vreg)
+ return $ mkRegRegMoveInstr (RealReg src) (RealReg dst)
+
+makeMove delta vreg (InMem src) (InReg dst)
+ = do recordSpill (SpillJoinRM vreg)
+ return $ mkLoadInstr (RealReg dst) delta src
+
+makeMove delta vreg (InReg src) (InMem dst)
+ = do recordSpill (SpillJoinRM vreg)
+ return $ mkSpillInstr (RealReg src) delta dst
+
+makeMove delta vreg src dst
+ = panic $ "makeMove " ++ show vreg ++ " (" ++ show src ++ ") ("
+ ++ show dst ++ ")"
+ ++ " (workaround: use -fviaC)"
+
+
+-- we have eliminated any possibility of single-node cylces
+-- in expandNode above.
+handleComponent :: Int -> Instr -> SCC (Unique, Loc, [Loc]) -> RegM [Instr]
+handleComponent delta instr (AcyclicSCC (vreg,src,dsts))
+ = mapM (makeMove delta 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 delta instr (CyclicSCC ((vreg,src@(InReg sreg),dsts):rest))
+ = do
+ spill_id <- getUniqueR
+ (saveInstr,slot) <- spillR (RealReg sreg) spill_id
+ remainingFixUps <- mapM (handleComponent delta instr) (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
+ moveInstr <- makeMove delta vreg r mem
+ return $ [COMMENT FSLIT("spill join move"), restoreToReg, moveInstr]
+
+ 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 delta instr (CyclicSCC _)
+ = panic "Register Allocator: handleComponent cyclic"
+
+