annotate python/transform.py @ 220:3f6c30a5d234

Major change in expression parsing to enable pointers and structs
author Windel Bouwman
date Sat, 06 Jul 2013 21:32:20 +0200
parents 1fa3e0050b49
children 1c7364bd74c7
rev   line source
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
1 from ir import *
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
2 # Standard passes:
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
3
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
4 class FunctionPass:
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
5 def run(self, ir):
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
6 """ Main entry point for the pass """
176
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
7 self.prepare()
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
8 for f in ir.Functions:
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
9 self.onFunction(f)
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
10 def onFunction(self, f):
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
11 """ Override this virtual method """
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
12 raise NotImplementedError()
176
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
13 def prepare(self):
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
14 pass
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
15
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
16 class BasicBlockPass(FunctionPass):
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
17 def onFunction(self, f):
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
18 for bb in f.BasicBlocks:
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
19 self.onBasicBlock(bb)
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
20 def onBasicBlock(self, bb):
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
21 """ Override this virtual method """
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
22 raise NotImplementedError()
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
23
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
24 class InstructionPass(BasicBlockPass):
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
25 def onBasicBlock(self, bb):
174
3eb06f5fb987 Added memory alloc for locals
Windel Bouwman
parents: 173
diff changeset
26 for ins in iter(bb.Instructions):
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
27 self.onInstruction(ins)
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
28 def onInstruction(self, ins):
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
29 """ Override this virtual method """
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
30 raise NotImplementedError()
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
31
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
32 # Usefull transforms:
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
33 class ConstantFolder(InstructionPass):
176
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
34 def prepare(self):
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
35 self.constMap = {}
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
36 def onInstruction(self, i):
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
37 if type(i) is ImmLoad:
176
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
38 self.constMap[i.target] = i.value
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
39 elif type(i) is BinaryOperator:
176
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
40 if i.value1 in self.constMap and i.value2 in self.constMap:
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
41 op = i.operation
176
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
42 va = self.constMap[i.value1]
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
43 vb = self.constMap[i.value2]
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
44 if op == '+':
176
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
45 vr = va + vb
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
46 elif op == '*':
176
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
47 vr = va * vb
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
48 elif op == '-':
176
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
49 vr = va - vb
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
50 else:
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
51 vr = None
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
52 return
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
53 self.constMap[i.result] = vr
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
54 i2 = ImmLoad(i.result, vr)
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
55 i.Parent.replaceInstruction(i, i2)
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
56
174
3eb06f5fb987 Added memory alloc for locals
Windel Bouwman
parents: 173
diff changeset
57 class DeadCodeDeleter(BasicBlockPass):
3eb06f5fb987 Added memory alloc for locals
Windel Bouwman
parents: 173
diff changeset
58 def onBasicBlock(self, bb):
3eb06f5fb987 Added memory alloc for locals
Windel Bouwman
parents: 173
diff changeset
59 def instructionUsed(ins):
3eb06f5fb987 Added memory alloc for locals
Windel Bouwman
parents: 173
diff changeset
60 if len(ins.defs) == 0:
3eb06f5fb987 Added memory alloc for locals
Windel Bouwman
parents: 173
diff changeset
61 # In case this instruction does not define any variables, assume it is usefull.
3eb06f5fb987 Added memory alloc for locals
Windel Bouwman
parents: 173
diff changeset
62 return True
3eb06f5fb987 Added memory alloc for locals
Windel Bouwman
parents: 173
diff changeset
63 for d in ins.defs:
3eb06f5fb987 Added memory alloc for locals
Windel Bouwman
parents: 173
diff changeset
64 if d.IsUsed:
3eb06f5fb987 Added memory alloc for locals
Windel Bouwman
parents: 173
diff changeset
65 return True
3eb06f5fb987 Added memory alloc for locals
Windel Bouwman
parents: 173
diff changeset
66 return False
3eb06f5fb987 Added memory alloc for locals
Windel Bouwman
parents: 173
diff changeset
67 bb.Instructions = list(filter(instructionUsed, bb.Instructions))
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
68
175
a51b3c956386 Added function call in expressions
Windel Bouwman
parents: 174
diff changeset
69 def isAllocPromotable(allocinst):
a51b3c956386 Added function call in expressions
Windel Bouwman
parents: 174
diff changeset
70 # Check if alloc value is only used by load and store operations.
a51b3c956386 Added function call in expressions
Windel Bouwman
parents: 174
diff changeset
71 assert type(allocinst) is Alloc
a51b3c956386 Added function call in expressions
Windel Bouwman
parents: 174
diff changeset
72 for use in ai.value.used_by:
a51b3c956386 Added function call in expressions
Windel Bouwman
parents: 174
diff changeset
73 print(use.user, use)
a51b3c956386 Added function call in expressions
Windel Bouwman
parents: 174
diff changeset
74 if not type(use.user) in [Load, Store]:
a51b3c956386 Added function call in expressions
Windel Bouwman
parents: 174
diff changeset
75 # TODO: check volatile
a51b3c956386 Added function call in expressions
Windel Bouwman
parents: 174
diff changeset
76 return False
a51b3c956386 Added function call in expressions
Windel Bouwman
parents: 174
diff changeset
77 otherUse = True
a51b3c956386 Added function call in expressions
Windel Bouwman
parents: 174
diff changeset
78 return True
a51b3c956386 Added function call in expressions
Windel Bouwman
parents: 174
diff changeset
79
177
460db5669efa Added clean pass for IR
Windel Bouwman
parents: 176
diff changeset
80 class CleanPass(FunctionPass):
219
1fa3e0050b49 Expanded ad hoc code generator
Windel Bouwman
parents: 177
diff changeset
81 def onFunction(self, f):
177
460db5669efa Added clean pass for IR
Windel Bouwman
parents: 176
diff changeset
82 bbs = list(f.BasicBlocks)
460db5669efa Added clean pass for IR
Windel Bouwman
parents: 176
diff changeset
83 for bb in bbs:
460db5669efa Added clean pass for IR
Windel Bouwman
parents: 176
diff changeset
84 # TODO: determine check for 'empty'
219
1fa3e0050b49 Expanded ad hoc code generator
Windel Bouwman
parents: 177
diff changeset
85
1fa3e0050b49 Expanded ad hoc code generator
Windel Bouwman
parents: 177
diff changeset
86 # If a block only contains a branch, it can be removed:
177
460db5669efa Added clean pass for IR
Windel Bouwman
parents: 176
diff changeset
87 if len(bb.Instructions) == 1:
460db5669efa Added clean pass for IR
Windel Bouwman
parents: 176
diff changeset
88 # This block is empty.
460db5669efa Added clean pass for IR
Windel Bouwman
parents: 176
diff changeset
89 # find predecessors of this block and replace this block reference with the jumped reference.
460db5669efa Added clean pass for IR
Windel Bouwman
parents: 176
diff changeset
90 ins = bb.LastInstruction
460db5669efa Added clean pass for IR
Windel Bouwman
parents: 176
diff changeset
91 if type(ins) is Branch:
219
1fa3e0050b49 Expanded ad hoc code generator
Windel Bouwman
parents: 177
diff changeset
92 print('Removing block {}'.format(bb))
1fa3e0050b49 Expanded ad hoc code generator
Windel Bouwman
parents: 177
diff changeset
93 #print(ins, bb.Predecessors)
1fa3e0050b49 Expanded ad hoc code generator
Windel Bouwman
parents: 177
diff changeset
94 preds = bb.Predecessors
1fa3e0050b49 Expanded ad hoc code generator
Windel Bouwman
parents: 177
diff changeset
95 if bb in preds:
1fa3e0050b49 Expanded ad hoc code generator
Windel Bouwman
parents: 177
diff changeset
96 # Do not remove if preceeded by itself
1fa3e0050b49 Expanded ad hoc code generator
Windel Bouwman
parents: 177
diff changeset
97 pass
1fa3e0050b49 Expanded ad hoc code generator
Windel Bouwman
parents: 177
diff changeset
98 else:
1fa3e0050b49 Expanded ad hoc code generator
Windel Bouwman
parents: 177
diff changeset
99 for pred in bb.Predecessors:
1fa3e0050b49 Expanded ad hoc code generator
Windel Bouwman
parents: 177
diff changeset
100 print('predecessor: {}'.format(pred))
1fa3e0050b49 Expanded ad hoc code generator
Windel Bouwman
parents: 177
diff changeset
101 pred.LastInstruction.changeTarget(bb, ins.target)
1fa3e0050b49 Expanded ad hoc code generator
Windel Bouwman
parents: 177
diff changeset
102 f.removeBasicBlock(bb)
177
460db5669efa Added clean pass for IR
Windel Bouwman
parents: 176
diff changeset
103
175
a51b3c956386 Added function call in expressions
Windel Bouwman
parents: 174
diff changeset
104 class Mem2RegPromotor(FunctionPass):
a51b3c956386 Added function call in expressions
Windel Bouwman
parents: 174
diff changeset
105 def onFunction(self, f):
176
5fd02aa38b42 Added while loop code generation
Windel Bouwman
parents: 175
diff changeset
106 # TODO
175
a51b3c956386 Added function call in expressions
Windel Bouwman
parents: 174
diff changeset
107 print(f)
a51b3c956386 Added function call in expressions
Windel Bouwman
parents: 174
diff changeset
108