Mate/RegisterAllocation.hs

   1 {-# LANGUAGE CPP #-}
   2 module Mate.RegisterAllocation where
   3
   4
   5 #include "debug.h"
   6
   7 import Data.List
   8 import Data.Maybe
   9
  10
  11 type Label a = a
  12 type IEdge a = (Label a, Label a)
  13 data IGraph a = IGraph [IEdge a] deriving (Show)
  14
  15 -- TODO: make IEdge eq
  16
  17 --data IArchitecture = Arch { regs :: Integer  }
  18 type IArchitecture = Int --number of regs
  19
  20
  21 type Assignment a = (a, Int)
  22
  23
  24 edgeEq (from,to) (from',to') = from == from' && to == to'
  25
  26
  27 -- TODO: find combinator do match try semantics here
  28 -- Solution: use list because list is MonadPlus instance
  29 -- other solution add maybe monadplus implementation
  30 conflicts (IGraph xs) (label,anotherLabel) = let comparison  = edgeEq (label,anotherLabel)
  31                                                  comparison' = edgeEq (anotherLabel,label)
  32                                              in isJust (find comparison xs) || isJust (find comparison' xs)
  33
  34
  35 isParticipiant label (from,to) = from == label || to == label
  36
  37 count p = length . filter p
  38
  39 degree g@(IGraph xs) label = count (isParticipiant label) xs
  40
  41
  42 doChaitin81 :: (Eq a) => IArchitecture -> IGraph a -> [Assignment a]
  43 doChaitin81 numberOfRegisters graph = []
  44
  45 type IState a = ([a],IGraph a)
  46
  47 --chait81Simplification :: (Eq a) => IArchitecture -> SimplState
  48 --chait81Simplification regs = do (
  49
  50 testGraph = IGraph [("a", "b"), ("a","c"), ("c", "b"), ("b","d"), ("d","c"),("b","e"),("d","e")]
  51
  52