|
240
|
1 """
|
|
|
2 Transformation to optimize IR-code
|
|
|
3 """
|
|
|
4
|
|
|
5 from ir import *
|
|
173
|
6 # Standard passes:
|
|
|
7
|
|
|
8 class FunctionPass:
|
|
|
9 def run(self, ir):
|
|
|
10 """ Main entry point for the pass """
|
|
176
|
11 self.prepare()
|
|
173
|
12 for f in ir.Functions:
|
|
|
13 self.onFunction(f)
|
|
|
14 def onFunction(self, f):
|
|
|
15 """ Override this virtual method """
|
|
|
16 raise NotImplementedError()
|
|
176
|
17 def prepare(self):
|
|
|
18 pass
|
|
173
|
19
|
|
240
|
20
|
|
173
|
21 class BasicBlockPass(FunctionPass):
|
|
240
|
22 def onFunction(self, f):
|
|
|
23 for bb in f.BasicBlocks:
|
|
|
24 self.onBasicBlock(bb)
|
|
|
25
|
|
|
26 def onBasicBlock(self, bb):
|
|
|
27 """ Override this virtual method """
|
|
|
28 raise NotImplementedError()
|
|
|
29
|
|
|
30
|
|
173
|
31 class InstructionPass(BasicBlockPass):
|
|
240
|
32 def onBasicBlock(self, bb):
|
|
|
33 for ins in iter(bb.Instructions):
|
|
|
34 self.onInstruction(ins)
|
|
|
35
|
|
|
36 def onInstruction(self, ins):
|
|
|
37 """ Override this virtual method """
|
|
|
38 raise NotImplementedError()
|
|
173
|
39
|
|
|
40 # Usefull transforms:
|
|
|
41 class ConstantFolder(InstructionPass):
|
|
176
|
42 def prepare(self):
|
|
|
43 self.constMap = {}
|
|
173
|
44 def onInstruction(self, i):
|
|
|
45 if type(i) is ImmLoad:
|
|
176
|
46 self.constMap[i.target] = i.value
|
|
173
|
47 elif type(i) is BinaryOperator:
|
|
176
|
48 if i.value1 in self.constMap and i.value2 in self.constMap:
|
|
173
|
49 op = i.operation
|
|
176
|
50 va = self.constMap[i.value1]
|
|
|
51 vb = self.constMap[i.value2]
|
|
173
|
52 if op == '+':
|
|
176
|
53 vr = va + vb
|
|
173
|
54 elif op == '*':
|
|
176
|
55 vr = va * vb
|
|
173
|
56 elif op == '-':
|
|
176
|
57 vr = va - vb
|
|
|
58 else:
|
|
|
59 vr = None
|
|
|
60 return
|
|
|
61 self.constMap[i.result] = vr
|
|
239
|
62 i.removeDef(i.result)
|
|
176
|
63 i2 = ImmLoad(i.result, vr)
|
|
|
64 i.Parent.replaceInstruction(i, i2)
|
|
173
|
65
|
|
237
|
66
|
|
|
67 class ConstantMerge(InstructionPass):
|
|
|
68 def prepare(self):
|
|
|
69 self.constMap = {}
|
|
|
70 def onInstruction(self, i):
|
|
|
71 if type(i) is ImmLoad:
|
|
|
72 v = i.value
|
|
|
73 if v in self.constMap:
|
|
|
74 # v is already defined, re-use the imm-load from elsewhere
|
|
|
75 pass
|
|
|
76 else:
|
|
|
77 self.constMap[v] = i
|
|
|
78 elif type(i) is BinaryOperator:
|
|
|
79 if i.value1 in self.constMap and i.value2 in self.constMap:
|
|
|
80 op = i.operation
|
|
|
81 va = self.constMap[i.value1]
|
|
|
82 vb = self.constMap[i.value2]
|
|
|
83 if op == '+':
|
|
|
84 vr = va + vb
|
|
|
85 elif op == '*':
|
|
|
86 vr = va * vb
|
|
|
87 elif op == '-':
|
|
|
88 vr = va - vb
|
|
|
89 else:
|
|
|
90 vr = None
|
|
|
91 return
|
|
|
92 self.constMap[i.result] = vr
|
|
|
93 i2 = ImmLoad(i.result, vr)
|
|
|
94 i.Parent.replaceInstruction(i, i2)
|
|
|
95
|
|
|
96
|
|
174
|
97 class DeadCodeDeleter(BasicBlockPass):
|
|
|
98 def onBasicBlock(self, bb):
|
|
|
99 def instructionUsed(ins):
|
|
|
100 if len(ins.defs) == 0:
|
|
240
|
101 # In case this instruction does not define any
|
|
|
102 # variables, assume it is usefull.
|
|
174
|
103 return True
|
|
|
104 for d in ins.defs:
|
|
|
105 if d.IsUsed:
|
|
|
106 return True
|
|
|
107 return False
|
|
|
108 bb.Instructions = list(filter(instructionUsed, bb.Instructions))
|
|
173
|
109
|
|
239
|
110
|
|
|
111 class SameImmLoadDeletePass(BasicBlockPass):
|
|
|
112 def onBasicBlock(self, bb):
|
|
|
113 constMap = {}
|
|
|
114 imms = filter(lambda i: isinstance(i, ImmLoad), bb.Instructions)
|
|
|
115 for ins in list(imms):
|
|
|
116 if ins.value in constMap:
|
|
|
117 # remove this immload and update all references to the target
|
|
|
118 t_old = ins.target
|
|
|
119 if not t_old.onlyUsedInBlock(bb):
|
|
|
120 continue
|
|
|
121 # update all references:
|
|
|
122 t_new = constMap[ins.value]
|
|
|
123 for use in t_old.used_by:
|
|
|
124 use.replaceValue(t_old, t_new)
|
|
|
125 bb.removeInstruction(ins)
|
|
|
126 else:
|
|
|
127 constMap[ins.value] = ins.target
|
|
240
|
128
|
|
239
|
129
|
|
175
|
130 def isAllocPromotable(allocinst):
|
|
|
131 # Check if alloc value is only used by load and store operations.
|
|
|
132 assert type(allocinst) is Alloc
|
|
|
133 for use in ai.value.used_by:
|
|
|
134 if not type(use.user) in [Load, Store]:
|
|
|
135 # TODO: check volatile
|
|
|
136 return False
|
|
|
137 otherUse = True
|
|
|
138 return True
|
|
|
139
|
|
240
|
140
|
|
177
|
141 class CleanPass(FunctionPass):
|
|
219
|
142 def onFunction(self, f):
|
|
239
|
143 bbs = list(f.BasicBlocks)
|
|
|
144 for bb in bbs:
|
|
177
|
145 # TODO: determine check for 'empty'
|
|
219
|
146
|
|
|
147 # If a block only contains a branch, it can be removed:
|
|
239
|
148 if len(bb.Instructions) == 1 and type(bb.LastInstruction) is Branch:
|
|
177
|
149 # This block is empty.
|
|
|
150 # find predecessors of this block and replace this block reference with the jumped reference.
|
|
|
151 ins = bb.LastInstruction
|
|
239
|
152 preds = bb.Predecessors
|
|
|
153 if bb in preds:
|
|
219
|
154 # Do not remove if preceeded by itself
|
|
|
155 pass
|
|
239
|
156 else:
|
|
219
|
157 for pred in bb.Predecessors:
|
|
|
158 pred.LastInstruction.changeTarget(bb, ins.target)
|
|
|
159 f.removeBasicBlock(bb)
|
|
177
|
160
|
|
240
|
161
|
|
175
|
162 class Mem2RegPromotor(FunctionPass):
|
|
|
163 def onFunction(self, f):
|
|
176
|
164 # TODO
|
|
235
|
165 pass
|
|
175
|
166
|
