Mercurial > lcfOS

comparison python/codegen/registerallocator.py @ 300:158068af716c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
yafm
author Windel Bouwman
date Tue, 03 Dec 2013 18:00:22 +0100
parents 9417caea2eb3
children
comparison
equal deleted inserted replaced
299:674789d9ff37 300:158068af716c
1 from .flowgraph import FlowGraph 1 from .flowgraph import FlowGraph
2 from .interferencegraph import InterferenceGraph 2 from .interferencegraph import InterferenceGraph
3 3
4 # Nifty first function: 4 # Nifty first function:
5 first = lambda x: next(iter(x)) 5 first = lambda x: next(iter(x))
6
6 7
7 class RegisterAllocator: 8 class RegisterAllocator:
8 """ 9 """
9 Target independent register allocator. 10 Target independent register allocator.
10 11
65 self.Node(mv.src[0]).moves.add(mv) 66 self.Node(mv.src[0]).moves.add(mv)
66 self.Node(mv.dst[0]).moves.add(mv) 67 self.Node(mv.dst[0]).moves.add(mv)
67 68
68 def NodeMoves(self, n): 69 def NodeMoves(self, n):
69 return n.moves & (self.activeMoves | self.worklistMoves) 70 return n.moves & (self.activeMoves | self.worklistMoves)
70 71
71 def MoveRelated(self, n): 72 def MoveRelated(self, n):
72 return bool(self.NodeMoves(n)) 73 return bool(self.NodeMoves(n))
73 74
74 @property 75 @property
75 def SpillWorkSet(self): 76 def SpillWorkSet(self):
106 for n in nodes: 107 for n in nodes:
107 for m in self.NodeMoves(n): 108 for m in self.NodeMoves(n):
108 if m in self.activeMoves: 109 if m in self.activeMoves:
109 self.activeMoves.remove(m) 110 self.activeMoves.remove(m)
110 self.worklistMoves.add(m) 111 self.worklistMoves.add(m)
111 112
112 def Coalesc(self): 113 def Coalesc(self):
113 """ Coalesc conservative. """ 114 """ Coalesc conservative. """
114 m = first(self.worklistMoves) 115 m = first(self.worklistMoves)
115 x = self.Node(m.dst[0]) 116 x = self.Node(m.dst[0])
116 y = self.Node(m.src[0]) 117 y = self.Node(m.src[0])
124 self.coalescedMoves.add(m) 125 self.coalescedMoves.add(m)
125 self.workSet.remove(v) 126 self.workSet.remove(v)
126 self.f.ig.Combine(u, v) 127 self.f.ig.Combine(u, v)
127 else: 128 else:
128 self.activeMoves.add(m) 129 self.activeMoves.add(m)
129 130
130 def Conservative(self, u, v): 131 def Conservative(self, u, v):
131 """ Briggs conservative criteria for coalesc """ 132 """ Briggs conservative criteria for coalesc """
132 nodes = u.Adjecent | v.Adjecent 133 nodes = u.Adjecent | v.Adjecent
133 c = lambda n: n.Degree >= self.K 134 c = lambda n: n.Degree >= self.K
134 k = len(list(filter(c, nodes))) 135 k = len(list(filter(c, nodes)))
147 else: 148 else:
148 sekf.worklistMoves.remove(m) 149 sekf.worklistMoves.remove(m)
149 self.frozenMoves.add(m) 150 self.frozenMoves.add(m)
150 # Check other part of the move for still being move related: 151 # 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 v = m.src[0] if u is m.dst[0] else m.dst[0]
152 153
153 def SelectSpill(self): 154 def SelectSpill(self):
154 # TODO 155 # TODO
155 pass 156 pass
156 157
157 def AssignColors(self): 158 def AssignColors(self):
158 """ Add nodes back to the graph to color it. """ 159 """ Add nodes back to the graph to color it. """
159 # Add nodes back to the graph: 160 # Add nodes back to the graph:
160 while self.selectStack: 161 while self.selectStack:
161 n = self.selectStack.pop(-1) 162 n = self.selectStack.pop(-1)
162 self.f.ig.addNode(n) 163 self.f.ig.addNode(n)
163 takenregs = set(self.color[m] for m in n.Adjecent) 164 takenregs = set(self.color[m] for m in n.Adjecent)
164 okColors = self.regs - takenregs 165 okColors = self.regs - takenregs