1 -- | Register coalescing.
4 module RegAlloc.Graph.Coalesce (
11 import RegAlloc.Liveness
24 -- | Do register coalescing on this top level thing
25 -- For Reg -> Reg moves, if the first reg dies at the same time the second reg is born
26 -- then the mov only serves to join live ranges. The two regs can be renamed to be
27 -- the same and the move instruction safely erased.
32 -> UniqSM [LiveCmmTop instr]
36 let joins = foldl' unionBags emptyBag
37 $ map slurpJoinMovs code
39 let alloc = foldl' buildAlloc emptyUFM
42 let patched = map (patchEraseLive (sinkReg alloc)) code
47 buildAlloc :: UniqFM Reg -> (Reg, Reg) -> UniqFM Reg
48 buildAlloc fm (r1, r2)
49 = let rmin = min r1 r2
51 in addToUFM fm rmax rmin
53 sinkReg :: UniqFM Reg -> Reg -> Reg
55 = case lookupUFM fm r of
57 Just r' -> sinkReg fm r'
60 -- | Slurp out mov instructions that only serve to join live ranges.
61 -- During a mov, if the source reg dies and the destiation reg is born
62 -- then we can rename the two regs to the same thing and eliminate the move.
70 = slurpCmm emptyBag live
72 slurpCmm rs CmmData{} = rs
73 slurpCmm rs (CmmProc _ _ _ sccs) = foldl' slurpBlock rs (flattenSCCs sccs)
74 slurpBlock rs (BasicBlock _ instrs) = foldl' slurpLI rs instrs
76 slurpLI rs (Instr _ Nothing) = rs
77 slurpLI rs (Instr instr (Just live))
78 | Just (r1, r2) <- takeRegRegMoveInstr instr
79 , elementOfUniqSet r1 $ liveDieRead live
80 , elementOfUniqSet r2 $ liveBorn live
82 -- only coalesce movs between two virtuals for now, else we end up with
83 -- allocatable regs in the live regs list..
84 , isVirtualReg r1 && isVirtualReg r2
90 slurpLI rs SPILL{} = rs
91 slurpLI rs RELOAD{} = rs