Mercurial > lcfOS

comparison python/registerallocator.py @ 279:2ccd57b1d78c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix register allocator to do burn2 OK
author Windel Bouwman
date Sat, 12 Oct 2013 09:56:23 +0200
parents 9fca39eebe50
children 02385f62f250
comparison
equal deleted inserted replaced
278:9fca39eebe50 279:2ccd57b1d78c
32 self.constrainedMoves = set() 32 self.constrainedMoves = set()
33 self.frozenMoves = set() 33 self.frozenMoves = set()
34 self.activeMoves = set() 34 self.activeMoves = set()
35 self.worklistMoves = set() 35 self.worklistMoves = set()
36 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
37 def Build(self): 43 def Build(self):
38 """ 1. Construct interference graph from instruction list """ 44 """ 1. Construct interference graph from instruction list """
39 self.f.cfg = FlowGraph(self.f.instructions) 45 self.f.cfg = FlowGraph(self.f.instructions)
40 self.f.ig = InterferenceGraph(self.f.cfg) 46 self.f.ig = InterferenceGraph(self.f.cfg)
47 self.printLive()
48
41 self.Node = self.f.ig.getNode 49 self.Node = self.f.ig.getNode
42 50
43 # Divide nodes into pre-colored and initial: 51 # Divide nodes into pre-colored and initial:
44 pre_tmp = list(self.f.tempMap.keys()) 52 pre_tmp = list(self.f.tempMap.keys())
45 self.precolored = set(self.Node(tmp) for tmp in pre_tmp) 53 self.precolored = set(self.Node(tmp) for tmp in pre_tmp)
54 for tmp, c in self.f.tempMap.items(): 62 for tmp, c in self.f.tempMap.items():
55 self.color[self.Node(tmp)] = c 63 self.color[self.Node(tmp)] = c
56 dict(self.f.tempMap) # start with pre-colored 64 dict(self.f.tempMap) # start with pre-colored
57 65
58 self.moves = [i for i in self.f.instructions if i.ismove] 66 self.moves = [i for i in self.f.instructions if i.ismove]
67 print(self.moves)
59 for mv in self.moves: 68 for mv in self.moves:
60 self.Node(mv.src[0]).moves.add(mv) 69 self.Node(mv.src[0]).moves.add(mv)
61 self.Node(mv.dst[0]).moves.add(mv) 70 self.Node(mv.dst[0]).moves.add(mv)
62 71
63 def NodeMoves(self, n): 72 def NodeMoves(self, n):
157 self.f.ig.addNode(n) 166 self.f.ig.addNode(n)
158 takenregs = set(self.color[m] for m in n.Adjecent) 167 takenregs = set(self.color[m] for m in n.Adjecent)
159 okColors = self.regs - takenregs 168 okColors = self.regs - takenregs
160 if okColors: 169 if okColors:
161 self.color[n] = first(okColors) 170 self.color[n] = first(okColors)
171 n.color = self.color[n]
162 else: 172 else:
163 raise NotImplementedError('Spill required here!') 173 raise NotImplementedError('Spill required here!')
164 174
165 def ApplyColors(self): 175 def ApplyColors(self):
166 # Remove coalesced moves: 176 # Remove coalesced moves:
167 for mv in self.coalescedMoves: 177 for mv in self.coalescedMoves:
168 self.f.instructions.remove(mv) 178 self.f.instructions.remove(mv)
179
169 # Use allocated registers: 180 # Use allocated registers:
170 lookup = lambda t: self.color[self.Node(t)] 181 lookup = lambda t: self.color[self.Node(t)]
171 for i in self.f.instructions: 182 for i in self.f.instructions:
172 i.src = tuple(map(lookup, i.src)) 183 i.src = tuple(map(lookup, i.src))
173 i.dst = tuple(map(lookup, i.dst)) 184 i.dst = tuple(map(lookup, i.dst))
174 185
175 def allocFrame(self, f): 186 def allocFrame(self, f):
176 """ Do register allocation for a single stack frame. """ 187 """ Do iterated register allocation for a single stack frame. """
177 self.InitData(f) 188 self.InitData(f)
178 self.Build() 189 self.Build()
179 self.makeWorkList() 190 self.makeWorkList()
180 while True: 191 while True:
181 if self.SimplifyWorkSet: 192 if self.SimplifyWorkSet: