Mercurial > lcfOS

annotate python/ppci/codegen/registerallocator.py @ 394:988f3fb861e4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
c3 code generator rewrite
author Windel Bouwman
date Thu, 22 May 2014 08:14:12 +0200
parents 39bf68bf1891
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()