Mercurial > lcfOS

comparison python/registerallocator.py @ 278:9fca39eebe50

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