Mercurial > lcfOS

comparison python/registerallocator.py @ 275:6f2423df0675

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fixed serve arm-as
author Windel Bouwman
date Sat, 14 Sep 2013 17:29:10 +0200
parents cdc76d183bcc
children 046017431c6a
comparison
equal deleted inserted replaced
274:ea93e0a7a31e 275:6f2423df0675
10 return '{}'.format(self.varname) 10 return '{}'.format(self.varname)
11 11
12 12
13 class InterferenceGraph(graph.Graph): 13 class InterferenceGraph(graph.Graph):
14 def __init__(self, flowgraph): 14 def __init__(self, flowgraph):
15 """ Create a new interference graph from a flowgraph """ 15 """
16 Create a new interference graph from a flowgraph
17 """
16 super().__init__() 18 super().__init__()
17 # Mapping from node to live set 19 # Mapping from node to live set
18 self.liveMap = {} 20 self.liveMap = {}
19 self.tempMap = {} 21 self.tempMap = {}
20 # Calculate liveness in CFG: 22 # Calculate liveness in CFG:
58 return n 60 return n
59 61
60 62
61 class RegisterAllocator: 63 class RegisterAllocator:
62 """ Target independent register allocator """ 64 """ Target independent register allocator """
63 def registerAllocate(self, ig, regs): 65 def registerAllocate(self, ig, regs, precolored):
64 """ Color the given interference graph with the provided registers """ 66 """
65 regMap = {} 67 Color the given interference graph with the provided registers
68 """
69 regMap = dict(precolored)
66 regs = set(regs) 70 regs = set(regs)
67 K = len(regs) 71 K = len(regs)
68 allvars = list(ig.nodes) 72 allvars = list(n for n in ig.nodes if n.varname not in regMap)
69 73
70 # Chaitin's algorithm: 74 # Chaitin's algorithm:
71 # remove all nodes that have less than K neighbours: 75 # remove all nodes that have less than K neighbours:
72 worklist = [] 76 worklist = []
73 while allvars: 77 while allvars:
83 n = worklist.pop(-1) 87 n = worklist.pop(-1)
84 adj = n.Adj - set(worklist) 88 adj = n.Adj - set(worklist)
85 possibleregs = set(regs) - set(regMap[n.varname] for n in adj) 89 possibleregs = set(regs) - set(regMap[n.varname] for n in adj)
86 regMap[n.varname] = list(possibleregs)[0] 90 regMap[n.varname] = list(possibleregs)[0]
87 # We have a register mapping! 91 # We have a register mapping!
88 #print(self.regMap) 92 # print(regMap)
93 # TODO: implement spilling
94 # TODO: implement coalescing
89 return regMap 95 return regMap
90 96
91 # TODO: implement spilling
92 # TODO: implement coalescing
93 97