Mercurial > lcfOS

annotate python/registerallocator.py @ 280:02385f62f250

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