Mercurial > lcfOS

annotate python/ppci/codegen/registerallocator.py @ 314:38f5f298ce0e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add log for interference graph
author Windel Bouwman
date Wed, 18 Dec 2013 20:22:20 +0100
parents 2c9768114877
children e9fe6988497c
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:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
6 first = lambda x: next(iter(x))
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
7
300
Windel Bouwman
parents: 296
diff changeset
8
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
9 class RegisterAllocator:
277
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
10 """
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
11 Target independent register allocator.
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
12
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
13 Algorithm is iterated register coalescing by Appel and George.
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
14
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
15 Chaitin's algorithm: remove all nodes with less than K neighbours.
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
16 These nodes can be colored when added back.
277
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
17
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
18 The process consists of the following steps:
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
19 - build interference graph from the instruction list
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
20 - remove low degree non move related nodes.
277
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
21 - (optional) coalesc registers to remove redundant moves
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
22 - (optional) spill registers
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
23 - select registers
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
24 """
312
2c9768114877 Added cool logging formatter
Windel Bouwman
parents: 305
diff changeset
25 def __init__(self):
2c9768114877 Added cool logging formatter
Windel Bouwman
parents: 305
diff changeset
26 self.logger = logging.getLogger('registerallocator')
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
27
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
28 def InitData(self, f):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
29 self.f = f
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
30 # Register information:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
31 self.regs = set(f.regs)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
32 self.K = len(self.regs)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
33
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
34 # Move related sets:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
35 self.coalescedMoves = set()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
36 self.constrainedMoves = set()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
37 self.frozenMoves = set()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
38 self.activeMoves = set()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
39 self.worklistMoves = set()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
40
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
41 def Build(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
42 """ 1. Construct interference graph from instruction list """
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
43 self.f.cfg = FlowGraph(self.f.instructions)
312
2c9768114877 Added cool logging formatter
Windel Bouwman
parents: 305
diff changeset
44 self.logger.info('Constructed flowgraph', extra={'ra_cfg':self.f.cfg})
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
45 self.f.ig = InterferenceGraph(self.f.cfg)
312
2c9768114877 Added cool logging formatter
Windel Bouwman
parents: 305
diff changeset
46 self.logger.info('Constructed interferencegraph', extra={'ra_ig':self.f.ig})
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)
300
Windel Bouwman
parents: 296
diff changeset
70
278
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)
300
Windel Bouwman
parents: 296
diff changeset
111
278
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)
300
Windel Bouwman
parents: 296
diff changeset
129
278
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]
300
Windel Bouwman
parents: 296
diff changeset
152
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
153 def SelectSpill(self):
312
2c9768114877 Added cool logging formatter
Windel Bouwman
parents: 305
diff changeset
154 raise NotImplementedError("Spill is not implemented")
277
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
155
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
156 def AssignColors(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
157 """ Add nodes back to the graph to color it. """
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
158 while self.selectStack:
312
2c9768114877 Added cool logging formatter
Windel Bouwman
parents: 305
diff changeset
159 n = self.selectStack.pop(-1) # Start with the last added
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
160 self.f.ig.addNode(n)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
161 takenregs = set(self.color[m] for m in n.Adjecent)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
162 okColors = self.regs - takenregs
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
163 if okColors:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
164 self.color[n] = first(okColors)
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
165 n.color = self.color[n]
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
166 else:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
167 raise NotImplementedError('Spill required here!')
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
168
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
169 def ApplyColors(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
170 # Remove coalesced moves:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
171 for mv in self.coalescedMoves:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
172 self.f.instructions.remove(mv)
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
173
277
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
174 # Use allocated registers:
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
175 lookup = lambda t: self.color[self.Node(t)]
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
176 for i in self.f.instructions:
277
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
177 i.src = tuple(map(lookup, i.src))
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
178 i.dst = tuple(map(lookup, i.dst))
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
179
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
180 def allocFrame(self, f):
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
181 """ Do iterated register allocation for a single stack frame. """
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
182 self.InitData(f)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
183 self.Build()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
184 self.makeWorkList()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
185 while True:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
186 if self.SimplifyWorkSet:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
187 self.Simplify()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
188 elif self.worklistMoves:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
189 self.Coalesc()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
190 elif self.FreezeWorkSet:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
191 self.Freeze()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
192 elif self.SpillWorkSet:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
193 raise NotImplementedError('Spill not implemented')
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
194 else:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
195 break # Done!
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
196 self.AssignColors()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
197 self.ApplyColors()