Mercurial > lcfOS

comparison python/codegen/registerallocator.py @ 296:9417caea2eb3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Directorized some backend files
author Windel Bouwman
date Sun, 01 Dec 2013 13:36:58 +0100
parents python/registerallocator.py@02385f62f250
children 158068af716c
comparison
equal deleted inserted replaced
295:917eab04b8b7 296:9417caea2eb3
1 from .flowgraph import FlowGraph
2 from .interferencegraph import InterferenceGraph
3
4 # Nifty first function:
5 first = lambda x: next(iter(x))
6
7 class RegisterAllocator:
8 """
9 Target independent register allocator.
10
11 Algorithm is iterated register coalescing by Appel and George.
12
13 Chaitin's algorithm: remove all nodes with less than K neighbours.
14 These nodes can be colored when added back.
15
16 The process consists of the following steps:
17 - build interference graph from the instruction list
18 - remove low degree non move related nodes.
19 - (optional) coalesc registers to remove redundant moves
20 - (optional) spill registers
21 - select registers
22 """
23
24 def InitData(self, f):
25 self.f = f
26 # Register information:
27 self.regs = set(f.regs)
28 self.K = len(self.regs)
29
30 # Move related sets:
31 self.coalescedMoves = set()
32 self.constrainedMoves = set()
33 self.frozenMoves = set()
34 self.activeMoves = set()
35 self.worklistMoves = set()
36
37 def printLive(self):
38 print('Liveness:')
39 for i in self.f.instructions:
40 cfgn = self.f.cfg._map[i]
41 print(i, cfgn.live_in)
42
43 def Build(self):
44 """ 1. Construct interference graph from instruction list """
45 self.f.cfg = FlowGraph(self.f.instructions)
46 self.f.ig = InterferenceGraph(self.f.cfg)
47
48 self.Node = self.f.ig.getNode
49
50 # Divide nodes into pre-colored and initial:
51 pre_tmp = list(self.f.tempMap.keys())
52 self.precolored = set(self.Node(tmp) for tmp in pre_tmp)
53 self.workSet = set(self.f.ig.nodes - self.precolored)
54
55 for n in self.precolored:
56 n.addDegree = 100 + len(self.f.ig.nodes) + self.K
57
58 # Initialize color map:
59 self.color = {}
60 for tmp, c in self.f.tempMap.items():
61 self.color[self.Node(tmp)] = c
62
63 self.moves = [i for i in self.f.instructions if i.ismove]
64 for mv in self.moves:
65 self.Node(mv.src[0]).moves.add(mv)
66 self.Node(mv.dst[0]).moves.add(mv)
67
68 def NodeMoves(self, n):
69 return n.moves & (self.activeMoves | self.worklistMoves)
70
71 def MoveRelated(self, n):
72 return bool(self.NodeMoves(n))
73
74 @property
75 def SpillWorkSet(self):
76 c = lambda n: n.Degree >= self.K
77 return set(filter(c, self.workSet))
78
79 @property
80 def FreezeWorkSet(self):
81 c = lambda n: n.Degree < self.K and self.MoveRelated(n)
82 return set(filter(c, self.workSet))
83
84 @property
85 def SimplifyWorkSet(self):
86 c = lambda n: n.Degree < self.K and not self.MoveRelated(n)
87 return set(filter(c, self.workSet))
88
89 def makeWorkList(self):
90 """ Divide initial nodes into worklists """
91 self.selectStack = []
92
93 # Fill initial move set:
94 for m in self.moves:
95 self.worklistMoves.add(m)
96
97 def Simplify(self):
98 """ 2. Remove nodes from the graph """
99 n = first(self.SimplifyWorkSet)
100 self.workSet.remove(n)
101 self.selectStack.append(n)
102 # Pop out of graph:
103 self.f.ig.delNode(n)
104
105 def EnableMoves(self, nodes):
106 for n in nodes:
107 for m in self.NodeMoves(n):
108 if m in self.activeMoves:
109 self.activeMoves.remove(m)
110 self.worklistMoves.add(m)
111
112 def Coalesc(self):
113 """ Coalesc conservative. """
114 m = first(self.worklistMoves)
115 x = self.Node(m.dst[0])
116 y = self.Node(m.src[0])
117 u, v = (y, x) if y in self.precolored else (x, y)
118 self.worklistMoves.remove(m)
119 if u is v:
120 self.coalescedMoves.add(m)
121 elif v in self.precolored or self.f.ig.hasEdge(u, v):
122 self.constrainedMoves.add(m)
123 elif u not in self.precolored and self.Conservative(u, v):
124 self.coalescedMoves.add(m)
125 self.workSet.remove(v)
126 self.f.ig.Combine(u, v)
127 else:
128 self.activeMoves.add(m)
129
130 def Conservative(self, u, v):
131 """ Briggs conservative criteria for coalesc """
132 nodes = u.Adjecent | v.Adjecent
133 c = lambda n: n.Degree >= self.K
134 k = len(list(filter(c, nodes)))
135 return k < self.K
136
137 def Freeze(self):
138 """ Give up coalescing on some node """
139 u = first(self.FreezeWorkSet)
140 self.freezeMoves(u)
141
142 def freezeMoves(self, u):
143 """ Freeze moves for node u """
144 for m in self.NodeMoves(u):
145 if m in self.activeMoves:
146 self.activeMoves.remove(m)
147 else:
148 sekf.worklistMoves.remove(m)
149 self.frozenMoves.add(m)
150 # Check other part of the move for still being move related:
151 v = m.src[0] if u is m.dst[0] else m.dst[0]
152
153 def SelectSpill(self):
154 # TODO
155 pass
156
157 def AssignColors(self):
158 """ Add nodes back to the graph to color it. """
159 # Add nodes back to the graph:
160 while self.selectStack:
161 n = self.selectStack.pop(-1)
162 self.f.ig.addNode(n)
163 takenregs = set(self.color[m] for m in n.Adjecent)
164 okColors = self.regs - takenregs
165 if okColors:
166 self.color[n] = first(okColors)
167 n.color = self.color[n]
168 else:
169 raise NotImplementedError('Spill required here!')
170
171 def ApplyColors(self):
172 # Remove coalesced moves:
173 for mv in self.coalescedMoves:
174 self.f.instructions.remove(mv)
175
176 # Use allocated registers:
177 lookup = lambda t: self.color[self.Node(t)]
178 for i in self.f.instructions:
179 i.src = tuple(map(lookup, i.src))
180 i.dst = tuple(map(lookup, i.dst))
181
182 def allocFrame(self, f):
183 """ Do iterated register allocation for a single stack frame. """
184 self.InitData(f)
185 self.Build()
186 self.makeWorkList()
187 while True:
188 if self.SimplifyWorkSet:
189 self.Simplify()
190 elif self.worklistMoves:
191 self.Coalesc()
192 elif self.FreezeWorkSet:
193 self.Freeze()
194 elif self.SpillWorkSet:
195 raise NotImplementedError('Spill not implemented')
196 else:
197 break # Done!
198 self.AssignColors()
199 self.ApplyColors()
200