Mercurial > lcfOS

comparison python/ir/module.py @ 171:3eb9b9e2958d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Improved IR code
author Windel Bouwman
date Wed, 03 Apr 2013 22:20:20 +0200
parents 4348da5ca307
children 5a7d37d615ee
comparison
equal deleted inserted replaced
170:4348da5ca307 171:3eb9b9e2958d
1 # IR-Structures: 1 # IR-Structures:
2 from .instruction import *
3 from .basicblock import BasicBlock
2 4
3 class Module: 5 class Module:
4 """ Main container for a piece of code. """ 6 """ Main container for a piece of code. """
5 def __init__(self, name): 7 def __init__(self, name):
6 self.name = name 8 self.name = name
7 self.instructions = [] 9 self.bbs = []
8 def __repr__(self): 10 def __repr__(self):
9 return 'IR-module [{0}]'.format(self.name) 11 return 'IR-module [{0}]'.format(self.name)
10 def getInstructions(self): 12 def getInstructions(self):
11 return self.instructions 13 ins = []
14 for bb in self.bbs:
15 ins += bb.Instructions
16 return ins
12 Instructions = property(getInstructions) 17 Instructions = property(getInstructions)
18 def addBB(self, bb):
19 self.bbs.append(bb)
20 def getBBs(self):
21 return self.bbs
22 BasicBlocks = property(getBBs)
13 def dump(self): 23 def dump(self):
14 print(self) 24 print(self)
15 for i in self.Instructions: 25 for i in self.Instructions:
16 print(i) 26 print(i, 'live vars:', list(i.live_in), 'uses', list(i.uses), 'defs', list(i.defs))
17 print('END') 27 print('END')
28 def dumpgv(self, outf):
29 outf.write('digraph G \n{\n')
30 for i in self.Instructions:
31 outf.write('{0} [label="{1}"];\n'.format(id(i), i))
32 for succ in i.succ:
33 outf.write('"{0}" -> "{1}" [label="{2}"];\n'.format(id(i), id(succ), succ.live_in))
34 outf.write('}\n')
18 35
36 # Analysis functions:
37 def check(self):
38 """ Perform sanity check on module """
39 for i in self.Instructions:
40 for t in i.defs:
41 assert type(t) is Value, "def must be Value, not {0}".format(type(t))
42 for t in i.uses:
43 assert type(t) is Value, "use must be Value, not {0}".format(type(t))
44 def analyze(self):
45 # Determine pred and succ:
46 def link(a, b):
47 a.succ.add(b)
48 b.pred.add(a)
49 for bb in self.bbs:
50 if not bb.Empty:
51 if len(bb.Instructions) > 1:
52 for i1, i2 in zip(bb.Instructions[:-1], bb.Instructions[1:]):
53 link(i1, i2)
54 else:
55 print('Only 1 long!', bb, bb.Instructions)
56 if type(bb.LastIns) is ConditionalBranch:
57 link(bb.LastIns, bb.LastIns.lab1.FirstIns)
58 link(bb.LastIns, bb.LastIns.lab2.FirstIns)
59 if type(bb.LastIns) is Branch:
60 link(bb.LastIns, bb.LastIns.target.FirstIns)
61 else:
62 print('Empty!', bb)
63 # We now have cfg
64
65 # Determine liveness:
66 for i in self.Instructions:
67 i.live_in = set()
68 i.live_out = set()
69 for z in range(50):
70 # TODO iterate until converge
71 for i in self.Instructions:
72 lo_mk = i.live_out.difference(i.defs)
73 i.live_in = i.uses.union(lo_mk)
74 lo = set()
75 for s in i.succ:
76 lo = lo.union(s.live_in)
77 i.live_out = lo
78 def constantProp(self):
79 """ Constant propagation. Pre-calculate constant values """
80 for i in self.Instructions:
81 if type(i) is ImmLoad:
82 i.target.constval = i.value
83 elif type(i) is BinaryOperator:
84 a = i.value1
85 b = i.value2
86 if i.value1.constval and i.value2.constval:
87 op = i.operation
88 if op == '+':
89 i.result.constval = a + b
90 else:
91 raise NotImplementedError(op)
92 else:
93 i.result.constval = None
94
95 def registerAllocate(self, regs):
96 print(regs)
97 allVals = []
98 # construct interference:
99 for i in self.Instructions:
100 for v in i.live_in:
101 allVals.append(v)
102 for v2 in i.live_in:
103 if v != v2:
104 v.interferes.add(v2)
105 # assign random registers:
106 print(allVals)
107 regs = set(regs)
108 for v in allVals:
109 takenregs = set([iv.reg for iv in v.interferes])
110 r2 = list(regs.difference(takenregs))
111 # Pick next available:
112 v.reg = r2[0]
113