Mercurial > lcfOS

comparison python/ir/module.py @ 173:c1d2b6b9f9a7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Rework into passes
author Windel Bouwman
date Fri, 19 Apr 2013 12:42:21 +0200
parents 5a7d37d615ee
children 3eb06f5fb987
comparison
equal deleted inserted replaced
172:5a7d37d615ee 173:c1d2b6b9f9a7
35 for ins in bb.Instructions: 35 for ins in bb.Instructions:
36 print(' ', ins) 36 print(' ', ins)
37 print('END') 37 print('END')
38 def dumpgv(self, outf): 38 def dumpgv(self, outf):
39 outf.write('digraph G \n{\n') 39 outf.write('digraph G \n{\n')
40 for i in self.Instructions: 40 for f in self.Functions:
41 outf.write('{0} [label="{1}"];\n'.format(id(i), i)) 41 outf.write('{0} [label="{1}"]\n'.format(id(f), f))
42 for succ in i.succ: 42 for bb in f.BasicBlocks:
43 outf.write('"{0}" -> "{1}" [label="{2}"];\n'.format(id(i), id(succ), succ.live_in)) 43 contents = str(bb) + '\n'
44 contents += '\n'.join([str(i) for i in bb.Instructions])
45 outf.write('{0} [label="{1}"];\n'.format(id(bb), contents))
46 for successor in bb.Successors:
47 outf.write('"{0}" -> "{1}"\n'.format(id(bb), id(successor)))
48 outf.write('"{0}" -> "{1}" [label="entry"]\n'.format(id(f), id(f.entry)))
44 outf.write('}\n') 49 outf.write('}\n')
45 50
46 # Analysis functions: 51 # Analysis functions:
47 def check(self): 52 def check(self):
48 """ Perform sanity check on module """ 53 """ Perform sanity check on module """
49 for i in self.Instructions: 54 for i in self.Instructions:
50 for t in i.defs: 55 for t in i.defs:
51 assert type(t) is Value, "def must be Value, not {0}".format(type(t)) 56 assert type(t) is Value, "def must be Value, not {0}".format(type(t))
52 for t in i.uses: 57 for t in i.uses:
53 assert type(t) is Value, "use must be Value, not {0}".format(type(t)) 58 assert type(t) is Value, "use must be Value, not {0}".format(type(t))
54 def analyze(self):
55 # Determine pred and succ:
56 def link(a, b):
57 a.succ.add(b)
58 b.pred.add(a)
59 for bb in self.BasicBlocks:
60 if not bb.Empty:
61 if len(bb.Instructions) > 1:
62 for i1, i2 in zip(bb.Instructions[:-1], bb.Instructions[1:]):
63 link(i1, i2)
64 else:
65 print('Only 1 long!', bb, bb.Instructions)
66 if type(bb.LastIns) is ConditionalBranch:
67 link(bb.LastIns, bb.LastIns.lab1.FirstIns)
68 link(bb.LastIns, bb.LastIns.lab2.FirstIns)
69 if type(bb.LastIns) is Branch:
70 link(bb.LastIns, bb.LastIns.target.FirstIns)
71 else:
72 print('Empty!', bb)
73 # We now have cfg
74 59
75 # Determine liveness:
76 for i in self.Instructions:
77 i.live_in = set()
78 i.live_out = set()
79 for z in range(50):
80 # TODO iterate until converge
81 for i in self.Instructions:
82 lo_mk = i.live_out.difference(i.defs)
83 i.live_in = i.uses.union(lo_mk)
84 lo = set()
85 for s in i.succ:
86 lo = lo.union(s.live_in)
87 i.live_out = lo
88 def constantProp(self):
89 """ Constant propagation. Pre-calculate constant values """
90 for i in self.Instructions:
91 if type(i) is ImmLoad:
92 i.target.constval = i.value
93 elif type(i) is BinaryOperator:
94 a = i.value1
95 b = i.value2
96 if i.value1.constval and i.value2.constval:
97 op = i.operation
98 if op == '+':
99 i.result.constval = a + b
100 else:
101 raise NotImplementedError(op)
102 else:
103 i.result.constval = None
104
105 def registerAllocate(self, regs):
106 print(regs)
107 allVals = []
108 # construct interference:
109 for i in self.Instructions:
110 for v in i.live_in:
111 allVals.append(v)
112 for v2 in i.live_in:
113 if v != v2:
114 v.interferes.add(v2)
115 # assign random registers:
116 print(allVals)
117 regs = set(regs)
118 for v in allVals:
119 takenregs = set([iv.reg for iv in v.interferes])
120 r2 = list(regs.difference(takenregs))
121 # Pick next available:
122 v.reg = r2[0]
123