Mercurial > lcfOS

comparison python/ppci/codegen/registerallocator.py @ 312:2c9768114877

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added cool logging formatter
author Windel Bouwman
date Mon, 16 Dec 2013 17:58:15 +0100
parents 0615b5308710
children e9fe6988497c
comparison
equal deleted inserted replaced
311:ff665880a6b0 312:2c9768114877
1 import logging
1 from .flowgraph import FlowGraph 2 from .flowgraph import FlowGraph
2 from .interferencegraph import InterferenceGraph 3 from .interferencegraph import InterferenceGraph
3 4
4 # Nifty first function: 5 # Nifty first function:
5 first = lambda x: next(iter(x)) 6 first = lambda x: next(iter(x))
19 - remove low degree non move related nodes. 20 - remove low degree non move related nodes.
20 - (optional) coalesc registers to remove redundant moves 21 - (optional) coalesc registers to remove redundant moves
21 - (optional) spill registers 22 - (optional) spill registers
22 - select registers 23 - select registers
23 """ 24 """
25 def __init__(self):
26 self.logger = logging.getLogger('registerallocator')
24 27
25 def InitData(self, f): 28 def InitData(self, f):
26 self.f = f 29 self.f = f
27 # Register information: 30 # Register information:
28 self.regs = set(f.regs) 31 self.regs = set(f.regs)
36 self.worklistMoves = set() 39 self.worklistMoves = set()
37 40
38 def Build(self): 41 def Build(self):
39 """ 1. Construct interference graph from instruction list """ 42 """ 1. Construct interference graph from instruction list """
40 self.f.cfg = FlowGraph(self.f.instructions) 43 self.f.cfg = FlowGraph(self.f.instructions)
44 self.logger.info('Constructed flowgraph', extra={'ra_cfg':self.f.cfg})
41 self.f.ig = InterferenceGraph(self.f.cfg) 45 self.f.ig = InterferenceGraph(self.f.cfg)
46 self.logger.info('Constructed interferencegraph', extra={'ra_ig':self.f.ig})
42 47
43 self.Node = self.f.ig.getNode 48 self.Node = self.f.ig.getNode
44 49
45 # Divide nodes into pre-colored and initial: 50 # Divide nodes into pre-colored and initial:
46 pre_tmp = list(self.f.tempMap.keys()) 51 pre_tmp = list(self.f.tempMap.keys())
144 self.frozenMoves.add(m) 149 self.frozenMoves.add(m)
145 # Check other part of the move for still being move related: 150 # Check other part of the move for still being move related:
146 v = m.src[0] if u is m.dst[0] else m.dst[0] 151 v = m.src[0] if u is m.dst[0] else m.dst[0]
147 152
148 def SelectSpill(self): 153 def SelectSpill(self):
149 # TODO 154 raise NotImplementedError("Spill is not implemented")
150 pass
151 155
152 def AssignColors(self): 156 def AssignColors(self):
153 """ Add nodes back to the graph to color it. """ 157 """ Add nodes back to the graph to color it. """
154 # Add nodes back to the graph:
155 while self.selectStack: 158 while self.selectStack:
156 n = self.selectStack.pop(-1) 159 n = self.selectStack.pop(-1) # Start with the last added
157 self.f.ig.addNode(n) 160 self.f.ig.addNode(n)
158 takenregs = set(self.color[m] for m in n.Adjecent) 161 takenregs = set(self.color[m] for m in n.Adjecent)
159 okColors = self.regs - takenregs 162 okColors = self.regs - takenregs
160 if okColors: 163 if okColors:
161 self.color[n] = first(okColors) 164 self.color[n] = first(okColors)
190 raise NotImplementedError('Spill not implemented') 193 raise NotImplementedError('Spill not implemented')
191 else: 194 else:
192 break # Done! 195 break # Done!
193 self.AssignColors() 196 self.AssignColors()
194 self.ApplyColors() 197 self.ApplyColors()
195