Mercurial > lcfOS

annotate python/ppci/codegen/registerallocator.py @ 366:39bf68bf1891

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