RegAlloc.Graph.ArchBase

ghc-8.4.4: The GHC API

Safe Haskell | None
Language | Haskell2010

RegAlloc.Graph.ArchBase

Description

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.

Synopsis

- data RegClass
  - = ClassG32
  - | ClassG16
  - | ClassG8
  - | ClassF64
- data Reg
  - = Reg RegClass Int
  - | RegSub RegSub Reg
- data RegSub
  - = SubL16
  - | SubL8
  - | SubL8H
- worst :: (RegClass -> UniqSet Reg) -> (Reg -> UniqSet Reg) -> Int -> RegClass -> RegClass -> Int
- bound :: (RegClass -> UniqSet Reg) -> (Reg -> UniqSet Reg) -> RegClass -> [RegClass] -> Int
- squeese :: (RegClass -> UniqSet Reg) -> (Reg -> UniqSet Reg) -> RegClass -> [(Int, RegClass)] -> Int

# Documentation

data RegClass #

Constructors

ClassG32 |
ClassG16 |
ClassG8 |
ClassF64 |

Instances

Enum RegClass # |
Instance details Defined in RegAlloc.Graph.ArchBase Methods succ :: RegClass -> RegClass Source # pred :: RegClass -> RegClass Source # toEnum :: Int -> RegClass Source # fromEnum :: RegClass -> Int Source # enumFrom :: RegClass -> [RegClass] Source # enumFromThen :: RegClass -> RegClass -> [RegClass] Source # enumFromTo :: RegClass -> RegClass -> [RegClass] Source # enumFromThenTo :: RegClass -> RegClass -> RegClass -> [RegClass] Source #
Eq RegClass # |
Instance details Defined in RegAlloc.Graph.ArchBase Methods (==) :: RegClass -> RegClass -> Bool # (/=) :: RegClass -> RegClass -> Bool #
Show RegClass # |
Instance details Defined in RegAlloc.Graph.ArchBase Methods showsPrec :: Int -> RegClass -> ShowS Source # show :: RegClass -> String Source # showList :: [RegClass] -> ShowS Source #

data Reg #

A register of some class

Constructors

Reg RegClass Int |
RegSub RegSub Reg |

Instances

Eq Reg # |
Instance details Defined in RegAlloc.Graph.ArchBase Methods (==) :: Reg -> Reg -> Bool # (/=) :: Reg -> Reg -> Bool #
Show Reg # |
Instance details Defined in RegAlloc.Graph.ArchBase Methods showsPrec :: Int -> Reg -> ShowS Source # show :: Reg -> String Source # showList :: [Reg] -> ShowS Source #
Uniquable Reg # | so we can put regs in UniqSets
Instance details Defined in RegAlloc.Graph.ArchBase Methods getUnique :: Reg -> Unique #

data RegSub #

A subcomponent of another register

Constructors

SubL16 |
SubL8 |
SubL8H |

Instances

Enum RegSub # |
Instance details Defined in RegAlloc.Graph.ArchBase Methods succ :: RegSub -> RegSub Source # pred :: RegSub -> RegSub Source # toEnum :: Int -> RegSub Source # fromEnum :: RegSub -> Int Source # enumFrom :: RegSub -> [RegSub] Source # enumFromThen :: RegSub -> RegSub -> [RegSub] Source # enumFromTo :: RegSub -> RegSub -> [RegSub] Source # enumFromThenTo :: RegSub -> RegSub -> RegSub -> [RegSub] Source #
Eq RegSub # |
Instance details Defined in RegAlloc.Graph.ArchBase Methods (==) :: RegSub -> RegSub -> Bool # (/=) :: RegSub -> RegSub -> Bool #
Ord RegSub # |
Instance details Defined in RegAlloc.Graph.ArchBase 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 # |
Instance details Defined in RegAlloc.Graph.ArchBase Methods showsPrec :: Int -> RegSub -> ShowS Source # show :: RegSub -> String Source # showList :: [RegSub] -> ShowS Source #

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 alised registers don't get counted twice, as per the paper.