GHC.CmmToAsm.Reg.Graph.Base

Utils for calculating general worst, bound, squeese and free, functions.

as per: "A Generalized Algorithm for Graph-Coloring Register Allocation" Michael Smith, Normal Ramsey, Glenn Holloway. PLDI 2004

These general versions are not used in GHC proper because they are too slow. Instead, hand written optimised versions are provided for each architecture in MachRegs*.hs

This code is here because we can test the architecture specific code against it.

Documentation

data RegClass

Constructors

ClassG32

ClassG16

ClassG8

ClassF64

Instances

Enum RegClass

Defined in GHC.CmmToAsm.Reg.Graph.Base

Methods

succ :: RegClass -> RegClass

pred :: RegClass -> RegClass

toEnum :: Int -> RegClass

fromEnum :: RegClass -> Int

enumFrom :: RegClass -> [RegClass]

enumFromThen :: RegClass -> RegClass -> [RegClass]

enumFromTo :: RegClass -> RegClass -> [RegClass]

enumFromThenTo :: RegClass -> RegClass -> RegClass -> [RegClass]

Eq RegClass

Defined in GHC.CmmToAsm.Reg.Graph.Base

Methods

(==) :: RegClass -> RegClass -> Bool

(/=) :: RegClass -> RegClass -> Bool

Show RegClass

Defined in GHC.CmmToAsm.Reg.Graph.Base

Methods

showsPrec :: Int -> RegClass -> ShowS

show :: RegClass -> String

showList :: [RegClass] -> ShowS

data Reg

A register of some class

Constructors

Reg RegClass Int

RegSub RegSub Reg

Instances

Eq Reg

Defined in GHC.CmmToAsm.Reg.Graph.Base

Methods

(==) :: Reg -> Reg -> Bool

(/=) :: Reg -> Reg -> Bool

Show Reg

Defined in GHC.CmmToAsm.Reg.Graph.Base

Methods

showsPrec :: Int -> Reg -> ShowS

show :: Reg -> String

showList :: [Reg] -> ShowS

Uniquable Reg

so we can put regs in UniqSets

Defined in GHC.CmmToAsm.Reg.Graph.Base

Methods

getUnique :: Reg -> Unique

data RegSub

A subcomponent of another register

Constructors

SubL16

SubL8

SubL8H

Instances

Enum RegSub

Defined in GHC.CmmToAsm.Reg.Graph.Base

Methods

succ :: RegSub -> RegSub

pred :: RegSub -> RegSub

toEnum :: Int -> RegSub

fromEnum :: RegSub -> Int

enumFrom :: RegSub -> [RegSub]

enumFromThen :: RegSub -> RegSub -> [RegSub]

enumFromTo :: RegSub -> RegSub -> [RegSub]

enumFromThenTo :: RegSub -> RegSub -> RegSub -> [RegSub]

Eq RegSub

Defined in GHC.CmmToAsm.Reg.Graph.Base

Methods

(==) :: RegSub -> RegSub -> Bool

(/=) :: RegSub -> RegSub -> Bool

Ord RegSub

Defined in GHC.CmmToAsm.Reg.Graph.Base

Methods

compare :: RegSub -> RegSub -> Ordering

(<) :: RegSub -> RegSub -> Bool

(<=) :: RegSub -> RegSub -> Bool

(>) :: RegSub -> RegSub -> Bool

(>=) :: RegSub -> RegSub -> Bool

max :: RegSub -> RegSub -> RegSub

min :: RegSub -> RegSub -> RegSub

Show RegSub

Defined in GHC.CmmToAsm.Reg.Graph.Base

Methods

showsPrec :: Int -> RegSub -> ShowS

show :: RegSub -> String

showList :: [RegSub] -> ShowS

worst :: (RegClass -> UniqSet Reg) -> (Reg -> UniqSet Reg) -> Int -> RegClass -> RegClass -> Int

Worst case displacement

a node N of classN has some number of neighbors, all of which are from classC.

(worst neighbors classN classC) is the maximum number of potential colors for N that can be lost by coloring its neighbors.

This should be hand coded/cached for each particular architecture, because the compute time is very long..

bound :: (RegClass -> UniqSet Reg) -> (Reg -> UniqSet Reg) -> RegClass -> [RegClass] -> Int

For a node N of classN and neighbors of classesC (bound classN classesC) is the maximum number of potential colors for N that can be lost by coloring its neighbors.

squeese :: (RegClass -> UniqSet Reg) -> (Reg -> UniqSet Reg) -> RegClass -> [(Int, RegClass)] -> Int

The total squeese on a particular node with a list of neighbors.

A version of this should be constructed for each particular architecture, possibly including uses of bound, so that aliased registers don't get counted twice, as per the paper.