Safe Haskell	None
Language	GHC2021

GHC.CmmToAsm.Reg.Graph.Base

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 Source #

Constructors

ClassG32
ClassG16
ClassG8
ClassF64

Instances

Instances details

Enum RegClass Source #
Instance details 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] #
Show RegClass Source #
Instance details Defined in GHC.CmmToAsm.Reg.Graph.Base Methods showsPrec :: Int -> RegClass -> ShowS # show :: RegClass -> String # showList :: [RegClass] -> ShowS #
Eq RegClass Source #
Instance details Defined in GHC.CmmToAsm.Reg.Graph.Base Methods (==) :: RegClass -> RegClass -> Bool # (/=) :: RegClass -> RegClass -> Bool #

data Reg Source #

A register of some class

Constructors

Reg RegClass Int
RegSub RegSub Reg

Instances

Instances details

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

data RegSub Source #

A subcomponent of another register

Constructors

SubL16
SubL8
SubL8H

Instances

Instances details

Enum RegSub Source #
Instance details 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] #
Show RegSub Source #
Instance details Defined in GHC.CmmToAsm.Reg.Graph.Base Methods showsPrec :: Int -> RegSub -> ShowS # show :: RegSub -> String # showList :: [RegSub] -> ShowS #
Eq RegSub Source #
Instance details Defined in GHC.CmmToAsm.Reg.Graph.Base Methods (==) :: RegSub -> RegSub -> Bool # (/=) :: RegSub -> RegSub -> Bool #
Ord RegSub Source #
Instance details 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 #

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

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 Source #

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 Source #

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.