Mercurial > lcfOS
diff python/registerallocator.py @ 278:9fca39eebe50
First implementation of regalloc with coalsesc
author | Windel Bouwman |
---|---|
date | Sun, 29 Sep 2013 14:08:15 +0200 |
parents | 046017431c6a |
children | 2ccd57b1d78c |
line wrap: on
line diff
--- a/python/registerallocator.py Thu Sep 26 21:14:25 2013 +0200 +++ b/python/registerallocator.py Sun Sep 29 14:08:15 2013 +0200 @@ -1,125 +1,193 @@ from flowgraph import FlowGraph from interferencegraph import InterferenceGraph +# Nifty first function: +first = lambda x: next(iter(x)) class RegisterAllocator: """ Target independent register allocator. - Algorithm is iterated .. (ITR) by Appel and George + Algorithm is iterated register coalescing by Appel and George. + + Chaitin's algorithm: remove all nodes with less than K neighbours. + These nodes can be colored when added back. The process consists of the following steps: - build interference graph from the instruction list + - remove low degree non move related nodes. - (optional) coalesc registers to remove redundant moves - (optional) spill registers - select registers """ - def __init__(self): + + def InitData(self, f): + self.f = f + # Register information: + self.regs = set(f.regs) + self.K = len(self.regs) + + # Move related sets: + self.coalescedMoves = set() + self.constrainedMoves = set() + self.frozenMoves = set() + self.activeMoves = set() + self.worklistMoves = set() + + def Build(self): + """ 1. Construct interference graph from instruction list """ + self.f.cfg = FlowGraph(self.f.instructions) + self.f.ig = InterferenceGraph(self.f.cfg) + self.Node = self.f.ig.getNode + + # Divide nodes into pre-colored and initial: + pre_tmp = list(self.f.tempMap.keys()) + self.precolored = set(self.Node(tmp) for tmp in pre_tmp) + self.workSet = set(self.f.ig.nodes - self.precolored) + + # Make degree table: + for n in self.precolored: + n.addDegree = 100 + len(self.f.ig.nodes) + self.K + + # Initialize color map: + self.color = {} + for tmp, c in self.f.tempMap.items(): + self.color[self.Node(tmp)] = c + dict(self.f.tempMap) # start with pre-colored + + self.moves = [i for i in self.f.instructions if i.ismove] + for mv in self.moves: + self.Node(mv.src[0]).moves.add(mv) + self.Node(mv.dst[0]).moves.add(mv) + + def NodeMoves(self, n): + return n.moves & (self.activeMoves | self.worklistMoves) + + def MoveRelated(self, n): + return bool(self.NodeMoves(n)) + + @property + def SpillWorkSet(self): + c = lambda n: n.Degree >= self.K + return set(filter(c, self.workSet)) + + @property + def FreezeWorkSet(self): + c = lambda n: n.Degree < self.K and self.MoveRelated(n) + return set(filter(c, self.workSet)) + + @property + def SimplifyWorkSet(self): + c = lambda n: n.Degree < self.K and not self.MoveRelated(n) + return set(filter(c, self.workSet)) + + def makeWorkList(self): + """ Divide initial nodes into worklists """ + self.selectStack = [] + + # Fill initial move set: + for m in self.moves: + self.worklistMoves.add(m) + + def Simplify(self): + """ 2. Remove nodes from the graph """ + n = first(self.SimplifyWorkSet) + self.workSet.remove(n) + self.selectStack.append(n) + # Pop out of graph: + self.f.ig.delNode(n) + + def EnableMoves(self, nodes): + for n in nodes: + for m in self.NodeMoves(n): + if m in self.activeMoves: + self.activeMoves.remove(m) + self.worklistMoves.add(m) + + def Coalesc(self): + """ Coalesc conservative. """ + m = first(self.worklistMoves) + x = self.Node(m.dst[0]) + y = self.Node(m.src[0]) + u, v = (y, x) if y in self.precolored else (x, y) + self.worklistMoves.remove(m) + if u is v: + self.coalescedMoves.add(m) + elif v in self.precolored or self.f.ig.hasEdge(u, v): + self.constrainedMoves.add(m) + elif u not in self.precolored and self.Conservative(u, v): + self.coalescedMoves.add(m) + self.workSet.remove(v) + self.f.ig.Combine(u, v) + else: + self.activeMoves.add(m) + + def Conservative(self, u, v): + """ Briggs conservative criteria for coalesc """ + nodes = u.Adjecent | v.Adjecent + c = lambda n: n.Degree >= self.K + k = len(list(filter(c, nodes))) + return k < self.K + + def Freeze(self): + """ Give up coalescing on some node """ + u = first(self.FreezeWorkSet) + self.freezeMoves(u) + + def freezeMoves(self, u): + """ Freeze moves for node u """ + for m in self.NodeMoves(u): + if m in self.activeMoves: + self.activeMoves.remove(m) + else: + sekf.worklistMoves.remove(m) + self.frozenMoves.add(m) + # Check other part of the move for still being move related: + v = m.src[0] if u is m.dst[0] else m.dst[0] + + def SelectSpill(self): + # TODO pass - def useUnused(self, inslist): - # Use unused temporaries at the end of the list - defTemps = [] - useTemps = [] - for i in inslist: - for d in iter(i.dst): - defTemps.append(d) - for s in iter(i.src): - useTemps.append(s) - defTemps = set(defTemps) - useTemps = set(useTemps) - unUsed = defTemps - useTemps - assert not unUsed - - def build(self, f): - """ 1. Construct interference graph from instruction list """ - self.useUnused(f.instructions) - f.cfg = FlowGraph(f.instructions) - f.ig = InterferenceGraph(f.cfg) - self.pre_colored = set(n for n in f.ig.nodes if n.varname in f.tempMap.keys()) - print('pre-colored:', self.pre_colored) - self.moves = [i for i in f.instructions if i.ismove] - print('move instructions:', self.moves) - self.nodestack = [] - - def getMoveRelated(self, f): - mr = set() - for i in self.moves: - mr.add(f.ig.getNode(i.src[0])) - mr.add(f.ig.getNode(i.dst[0])) - return mr - - def simplify(self, f): - """ 2. Remove nodes from the graph """ - # Chaitin's algorithm: - # remove all non move related nodes that have less than K neighbours: - # Also do not remove pre-colored nodes. - # move_related = self.getMoveRelated(f) - #print('move related', move_related) - # o_nodes = f.ig.nodes - (self.pre_colored | move_related) - o_nodes = f.ig.nodes - self.pre_colored - #print('o_nodes', o_nodes) - while o_nodes: - less_k = [n for n in o_nodes if n.Degree < self.K] - if not less_k: - raise NotImplementedError('Spilling not implemented') - n = less_k[0] - self.nodestack.append(n) - f.ig.delNode(n) - o_nodes.remove(n) - - def coalesc(self, f): - # for mov in ins: - # if mov.src is not connected to mov.dst - # and the node being coalesced has less than K nodes - # of significant degree, then the node can be coalesced. - # This is briggs algorithm. - for m in self.moves: - src = f.ig.getNode(m.src[0]) - dst = f.ig.getNode(m.dst[0]) - assert not f.ig.hasEdge(src, dst) - neighbours = src.Adj | dst.Adj - # neighbours with significant degree: - sd_nb = set(n for n in neighbours if n.Degree >= self.K) - print('neighbours with significant degree', sd_nb) - if len(sd_nb) < self.K: - print('Coalesc:', m) - if dst in self.pre_colored: - if src in self.pre_colored: - break - v2 = src - for i in f.instructions: - rf = lambda x: x - i.src = rf(i.src) - i.dst = rf(i.dst) - f.instructions.remove(m) - - def select(self, f): - """ Add nodes of less than K degree back to the graph to color it. """ - regMap = dict(f.tempMap) # start with pre-colored - + def AssignColors(self): + """ Add nodes back to the graph to color it. """ # Add nodes back to the graph: - while self.nodestack: - n = self.nodestack.pop(-1) - f.ig.addNode(n) - takenregs = set(regMap[m.varname] for m in n.Adj) - possibleregs = set(self.regs) - takenregs - regMap[n.varname] = list(possibleregs)[0] - # We have a register mapping! - print(regMap) + while self.selectStack: + n = self.selectStack.pop(-1) + self.f.ig.addNode(n) + takenregs = set(self.color[m] for m in n.Adjecent) + okColors = self.regs - takenregs + if okColors: + self.color[n] = first(okColors) + else: + raise NotImplementedError('Spill required here!') + + def ApplyColors(self): + # Remove coalesced moves: + for mv in self.coalescedMoves: + self.f.instructions.remove(mv) # Use allocated registers: - lookup = lambda t: regMap[t] - for i in f.instructions: + lookup = lambda t: self.color[self.Node(t)] + for i in self.f.instructions: i.src = tuple(map(lookup, i.src)) i.dst = tuple(map(lookup, i.dst)) def allocFrame(self, f): """ Do register allocation for a single stack frame. """ - self.regs = set(f.regs) - self.K = len(self.regs) - self.build(f) - self.simplify(f) - # TODO: implement spilling - #self.coalesc(f) # Optional! - self.select(f) + self.InitData(f) + self.Build() + self.makeWorkList() + while True: + if self.SimplifyWorkSet: + self.Simplify() + elif self.worklistMoves: + self.Coalesc() + elif self.FreezeWorkSet: + self.Freeze() + elif self.SpillWorkSet: + raise NotImplementedError('Spill not implemented') + else: + break # Done! + self.AssignColors() + self.ApplyColors()