← Back to branch summary

~ubuntu-branches/ubuntu/precise/ghc/precise

« back to all changes in this revision

Viewing changes to compiler/utils/GraphBase.hs

  • Committer: Bazaar Package Importer
  • Author(s): Joachim Breitner
  • Date: 2011-01-17 12:49:24 UTC
  • Revision ID: james.westby@ubuntu.com-20110117124924-do1pym1jlf5o636m
Tags: upstream-7.0.1
Import upstream version 7.0.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
compiler/utils/GraphBase.hs
 
1
 
 
2
-- | Types for the general graph colorer.
 
3
 
 
4
module GraphBase (
 
5
        Triv,
 
6
        Graph (..),
 
7
        initGraph,
 
8
        graphMapModify,
 
9
 
 
10
        Node  (..),     newNode,
 
11
)
 
12
        
 
13
 
 
14
where
 
15
 
 
16
import UniqSet
 
17
import UniqFM
 
18
 
 
19
 
 
20
-- | A fn to check if a node is trivially colorable
 
21
--      For graphs who's color classes are disjoint then a node is 'trivially colorable'
 
22
--      when it has less neighbors and exclusions than available colors for that node.
 
23
--
 
24
--      For graph's who's color classes overlap, ie some colors alias other colors, then
 
25
--      this can be a bit more tricky. There is a general way to calculate this, but 
 
26
--      it's likely be too slow for use in the code. The coloring algorithm takes
 
27
--      a canned function which can be optimised by the user to be specific to the 
 
28
--      specific graph being colored.
 
29
--
 
30
--      for details, see  "A Generalised Algorithm for Graph-Coloring Register Allocation"
 
31
--                              Smith, Ramsey, Holloway - PLDI 2004.
 
32
--
 
33
type Triv k cls color
 
34
        =  cls                  -- the class of the node we're trying to color.
 
35
        -> UniqSet k            -- the node's neighbors.
 
36
        -> UniqSet color        -- the node's exclusions.
 
37
        -> Bool         
 
38
 
 
39
 
 
40
-- | The Interference graph.
 
41
--      There used to be more fields, but they were turfed out in a previous revision.
 
42
--      maybe we'll want more later..
 
43
--
 
44
data Graph k cls color
 
45
        = Graph { 
 
46
        -- | All active nodes in the graph.
 
47
          graphMap              :: UniqFM (Node k cls color)  }
 
48
 
 
49
 
 
50
-- | An empty graph.    
 
51
initGraph :: Graph k cls color
 
52
initGraph
 
53
        = Graph
 
54
        { graphMap              = emptyUFM }
 
55
 
 
56
 
 
57
-- | Modify the finite map holding the nodes in the graph.
 
58
graphMapModify 
 
59
        :: (UniqFM (Node k cls color) -> UniqFM (Node k cls color))
 
60
        -> Graph k cls color -> Graph k cls color
 
61
 
 
62
graphMapModify f graph
 
63
        = graph { graphMap      = f (graphMap graph) }
 
64
        
 
65
                
 
66
 
 
67
-- | Graph nodes.
 
68
--      Represents a thing that can conflict with another thing.
 
69
--      For the register allocater the nodes represent registers.
 
70
--
 
71
data Node k cls color
 
72
        = Node {        
 
73
        -- | A unique identifier for this node.
 
74
          nodeId                :: k
 
75
 
 
76
        -- | The class of this node,
 
77
        --      determines the set of colors that can be used.
 
78
        , nodeClass             :: cls
 
79
 
 
80
        -- | The color of this node, if any.
 
81
        , nodeColor             :: Maybe color
 
82
 
 
83
        -- | Neighbors which must be colored differently to this node.
 
84
        , nodeConflicts         :: UniqSet k
 
85
 
 
86
        -- | Colors that cannot be used by this node.
 
87
        , nodeExclusions        :: UniqSet color
 
88
 
 
89
        -- | Colors that this node would prefer to be, in decending order.
 
90
        , nodePreference        :: [color]  
 
91
 
 
92
        -- | Neighbors that this node would like to be colored the same as.
 
93
        , nodeCoalesce          :: UniqSet k }
 
94
 
 
95
 
 
96
-- | An empty node.
 
97
newNode :: k -> cls -> Node k cls color
 
98
newNode k cls
 
99
        = Node
 
100
        { nodeId                = k
 
101
        , nodeClass             = cls
 
102
        , nodeColor             = Nothing
 
103
        , nodeConflicts         = emptyUniqSet
 
104
        , nodeExclusions        = emptyUniqSet
 
105
        , nodePreference        = [] 
 
106
        , nodeCoalesce          = emptyUniqSet }
 
107
 
 
108
 
 
109
 
 
110
 
 
111