Mercurial > lcfOS

comparison python/ppci/codegen/registerallocator.py @ 301:6753763d3bec

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