From 109e11fccf6b8351bc40e20bf4d0343eefcf85dc Mon Sep 17 00:00:00 2001 From: "Ben.Lippmeier@anu.edu.au" Date: Thu, 23 Aug 2007 09:48:19 +0000 Subject: [PATCH] Use UniqSet instead of Data.Set --- compiler/nativeGen/RegArchBase.hs | 71 ++++++++++++++++++++++--------------- compiler/nativeGen/RegArchX86.hs | 29 ++++++++------- 2 files changed, 56 insertions(+), 44 deletions(-) diff --git a/compiler/nativeGen/RegArchBase.hs b/compiler/nativeGen/RegArchBase.hs index 5cf5403..86f0f0e 100644 --- a/compiler/nativeGen/RegArchBase.hs +++ b/compiler/nativeGen/RegArchBase.hs @@ -24,13 +24,9 @@ module RegArchBase ( where - ----- -import qualified Data.Set as Set -import Data.Set (Set) - --- import qualified Data.Map as Map --- import Data.Map (Map) +import UniqSet +import Unique -- Some basic register classes. @@ -45,7 +41,7 @@ data RegClass -- floating point regs | ClassF64 -- 64 bit FPRs - deriving (Show, Ord, Eq) + deriving (Show, Eq, Enum) -- | A register of some class @@ -55,8 +51,21 @@ data Reg -- a sub-component of one of the other regs | RegSub RegSub Reg - deriving (Show, Ord, Eq) + deriving (Show, Eq) + + +-- | so we can put regs in UniqSets +instance Uniquable Reg where + getUnique (Reg c i) + = mkUnique 'R' + $ fromEnum c * 1000 + i + getUnique (RegSub s (Reg c i)) + = mkUnique 'S' + $ fromEnum s * 10000 + fromEnum c * 1000 + i + + getUnique (RegSub s (RegSub c _)) + = error "RegArchBase.getUnique: can't have a sub-reg of a sub-reg." -- | A subcomponent of another register data RegSub @@ -66,7 +75,6 @@ data RegSub deriving (Show, Enum, Ord, Eq) - -- | Worst case displacement -- -- a node N of classN has some number of neighbors, @@ -79,26 +87,28 @@ data RegSub -- because the compute time is very long.. worst - :: (RegClass -> Set Reg) - -> (Reg -> Set Reg) + :: (RegClass -> UniqSet Reg) + -> (Reg -> UniqSet Reg) -> Int -> RegClass -> RegClass -> Int worst regsOfClass regAlias neighbors classN classC - = let regAliasS regs = unionsS $ Set.map regAlias regs + = let regAliasS regs = unionManyUniqSets + $ map regAlias + $ uniqSetToList regs -- all the regs in classes N, C regsN = regsOfClass classN regsC = regsOfClass classC -- all the possible subsets of c which have size < m - regsS = Set.filter (\s -> Set.size s >= 1 && Set.size s <= neighbors) - $ powerset regsC + regsS = filter (\s -> sizeUniqSet s >= 1 && sizeUniqSet s <= neighbors) + $ powersetLS regsC -- for each of the subsets of C, the regs which conflict with posiblities for N regsS_conflict - = Set.map (\s -> Set.intersection regsN (regAliasS s)) regsS + = map (\s -> intersectUniqSets regsN (regAliasS s)) regsS - in Set.findMax $ Set.map Set.size $ regsS_conflict + in maximum $ map sizeUniqSet $ regsS_conflict -- | For a node N of classN and neighbors of classesC @@ -107,20 +117,22 @@ worst regsOfClass regAlias neighbors classN classC -- bound - :: (RegClass -> Set Reg) - -> (Reg -> Set Reg) + :: (RegClass -> UniqSet Reg) + -> (Reg -> UniqSet Reg) -> RegClass -> [RegClass] -> Int bound regsOfClass regAlias classN classesC - = let regAliasS regs = unionsS $ Set.map regAlias regs + = let regAliasS regs = unionManyUniqSets + $ map regAlias + $ uniqSetToList regs regsC_aliases - = Set.unions + = unionManyUniqSets $ map (regAliasS . regsOfClass) classesC - overlap = Set.intersection (regsOfClass classN) regsC_aliases + overlap = intersectUniqSets (regsOfClass classN) regsC_aliases - in Set.size overlap + in sizeUniqSet overlap -- | The total squeese on a particular node with a list of neighbors. @@ -130,8 +142,8 @@ bound regsOfClass regAlias classN classesC -- twice, as per the paper. -- squeese - :: (RegClass -> Set Reg) - -> (Reg -> Set Reg) + :: (RegClass -> UniqSet Reg) + -> (Reg -> UniqSet Reg) -> RegClass -> [(Int, RegClass)] -> Int squeese regsOfClass regAlias classN countCs @@ -139,15 +151,16 @@ squeese regsOfClass regAlias classN countCs -- | powerset (for lists) -powersetL :: Ord a => [a] -> [[a]] +powersetL :: [a] -> [[a]] powersetL = map concat . mapM (\x -> [[],[x]]) --- | powerset (for sets) -powerset :: Ord a => Set a -> Set (Set a) -powerset s = Set.fromList $ map Set.fromList $ powersetL $ Set.toList s +-- | powersetLS (list of sets) +powersetLS :: Uniquable a => UniqSet a -> [UniqSet a] +powersetLS s = map mkUniqSet $ powersetL $ uniqSetToList s +{- -- | unions (for sets) unionsS :: Ord a => Set (Set a) -> Set a unionsS ss = Set.unions $ Set.toList ss - +-} diff --git a/compiler/nativeGen/RegArchX86.hs b/compiler/nativeGen/RegArchX86.hs index 53f9929..21ac781 100644 --- a/compiler/nativeGen/RegArchX86.hs +++ b/compiler/nativeGen/RegArchX86.hs @@ -16,8 +16,7 @@ module RegArchX86 ( import RegArchBase (Reg(..), RegSub(..), RegClass(..)) -import qualified Data.Set as Set -import Data.Set (Set) +import UniqSet -- | Determine the class of a register classOfReg :: Reg -> RegClass @@ -32,22 +31,22 @@ classOfReg reg -- | Determine all the regs that make up a certain class. -- -regsOfClass :: RegClass -> Set Reg +regsOfClass :: RegClass -> UniqSet Reg regsOfClass c = case c of ClassG32 - -> Set.fromList [ Reg ClassG32 i | i <- [0..7] ] + -> mkUniqSet [ Reg ClassG32 i | i <- [0..7] ] ClassG16 - -> Set.fromList [ RegSub SubL16 (Reg ClassG32 i) | i <- [0..7] ] + -> mkUniqSet [ RegSub SubL16 (Reg ClassG32 i) | i <- [0..7] ] ClassG8 - -> Set.union - (Set.fromList [ RegSub SubL8 (Reg ClassG32 i) | i <- [0..3] ]) - (Set.fromList [ RegSub SubL8H (Reg ClassG32 i) | i <- [0..3] ]) + -> unionUniqSets + (mkUniqSet [ RegSub SubL8 (Reg ClassG32 i) | i <- [0..3] ]) + (mkUniqSet [ RegSub SubL8H (Reg ClassG32 i) | i <- [0..3] ]) ClassF64 - -> Set.fromList [ Reg ClassF64 i | i <- [0..5] ] + -> mkUniqSet [ Reg ClassF64 i | i <- [0..5] ] -- | Determine the common name of a reg @@ -72,7 +71,7 @@ regName reg -- | Which regs alias what other regs -regAlias :: Reg -> Set Reg +regAlias :: Reg -> UniqSet Reg regAlias reg = case reg of @@ -81,11 +80,11 @@ regAlias reg -- for eax, ebx, ecx, eds | i <= 3 - -> Set.fromList $ [ Reg ClassG32 i, RegSub SubL16 reg, RegSub SubL8 reg, RegSub SubL8H reg ] + -> mkUniqSet $ [ Reg ClassG32 i, RegSub SubL16 reg, RegSub SubL8 reg, RegSub SubL8H reg ] -- for esi, edi, esp, ebp | 4 <= i && i <= 7 - -> Set.fromList $ [ Reg ClassG32 i, RegSub SubL16 reg ] + -> mkUniqSet $ [ Reg ClassG32 i, RegSub SubL16 reg ] -- 16 bit subregs alias the whole reg @@ -94,14 +93,14 @@ regAlias reg -- 8 bit subregs alias the 32 and 16, but not the other 8 bit subreg RegSub SubL8 r@(Reg ClassG32 i) - -> Set.fromList $ [ r, RegSub SubL16 r, RegSub SubL8 r ] + -> mkUniqSet $ [ r, RegSub SubL16 r, RegSub SubL8 r ] RegSub SubL8H r@(Reg ClassG32 i) - -> Set.fromList $ [ r, RegSub SubL16 r, RegSub SubL8H r ] + -> mkUniqSet $ [ r, RegSub SubL16 r, RegSub SubL8H r ] -- fp Reg ClassF64 i - -> Set.singleton reg + -> unitUniqSet reg _ -> error "regAlias: invalid register" -- 1.7.10.4