|
240
|
1 """
|
|
|
2 Transformation to optimize IR-code
|
|
|
3 """
|
|
|
4
|
|
253
|
5 import logging
|
|
240
|
6 from ir import *
|
|
173
|
7 # Standard passes:
|
|
|
8
|
|
|
9 class FunctionPass:
|
|
253
|
10 def run(self, ir):
|
|
|
11 """ Main entry point for the pass """
|
|
|
12 logging.info('Running pass {}'.format(type(self)))
|
|
|
13 self.prepare()
|
|
|
14 for f in ir.Functions:
|
|
|
15 self.onFunction(f)
|
|
|
16
|
|
|
17 def onFunction(self, f):
|
|
|
18 """ Override this virtual method """
|
|
|
19 raise NotImplementedError()
|
|
|
20
|
|
|
21 def prepare(self):
|
|
|
22 pass
|
|
173
|
23
|
|
240
|
24
|
|
173
|
25 class BasicBlockPass(FunctionPass):
|
|
240
|
26 def onFunction(self, f):
|
|
|
27 for bb in f.BasicBlocks:
|
|
|
28 self.onBasicBlock(bb)
|
|
|
29
|
|
|
30 def onBasicBlock(self, bb):
|
|
|
31 """ Override this virtual method """
|
|
|
32 raise NotImplementedError()
|
|
|
33
|
|
|
34
|
|
173
|
35 class InstructionPass(BasicBlockPass):
|
|
240
|
36 def onBasicBlock(self, bb):
|
|
|
37 for ins in iter(bb.Instructions):
|
|
|
38 self.onInstruction(ins)
|
|
|
39
|
|
|
40 def onInstruction(self, ins):
|
|
|
41 """ Override this virtual method """
|
|
|
42 raise NotImplementedError()
|
|
173
|
43
|
|
|
44 # Usefull transforms:
|
|
|
45 class ConstantFolder(InstructionPass):
|
|
252
|
46 def prepare(self):
|
|
|
47 self.constMap = {}
|
|
|
48
|
|
|
49 def onInstruction(self, i):
|
|
173
|
50 if type(i) is ImmLoad:
|
|
176
|
51 self.constMap[i.target] = i.value
|
|
173
|
52 elif type(i) is BinaryOperator:
|
|
252
|
53 if i.value1 in self.constMap and i.value2 in self.constMap and i.operation in ['+', '-', '*', '<<']:
|
|
237
|
54 op = i.operation
|
|
|
55 va = self.constMap[i.value1]
|
|
|
56 vb = self.constMap[i.value2]
|
|
|
57 if op == '+':
|
|
|
58 vr = va + vb
|
|
|
59 elif op == '*':
|
|
|
60 vr = va * vb
|
|
|
61 elif op == '-':
|
|
|
62 vr = va - vb
|
|
252
|
63 elif op == '<<':
|
|
|
64 vr = va << vb
|
|
237
|
65 else:
|
|
|
66 vr = None
|
|
|
67 return
|
|
|
68 self.constMap[i.result] = vr
|
|
252
|
69 i.removeDef(i.result)
|
|
237
|
70 i2 = ImmLoad(i.result, vr)
|
|
253
|
71 logging.debug('Replacing {}'.format(i))
|
|
237
|
72 i.Parent.replaceInstruction(i, i2)
|
|
|
73
|
|
|
74
|
|
174
|
75 class DeadCodeDeleter(BasicBlockPass):
|
|
252
|
76 def onBasicBlock(self, bb):
|
|
|
77 def instructionUsed(ins):
|
|
253
|
78 if not type(ins) in [ImmLoad, BinaryOperator]:
|
|
|
79 return True
|
|
252
|
80 if len(ins.defs) == 0:
|
|
|
81 # In case this instruction does not define any
|
|
|
82 # variables, assume it is usefull.
|
|
|
83 return True
|
|
|
84 return any(d.Used for d in ins.defs)
|
|
|
85
|
|
|
86 change = True
|
|
|
87 while change:
|
|
|
88 change = False
|
|
|
89 for i in bb.Instructions:
|
|
|
90 if instructionUsed(i):
|
|
|
91 continue
|
|
|
92 bb.removeInstruction(i)
|
|
|
93 change = True
|
|
173
|
94
|
|
239
|
95
|
|
252
|
96 class CommonSubexpressionElimination(BasicBlockPass):
|
|
239
|
97 def onBasicBlock(self, bb):
|
|
|
98 constMap = {}
|
|
252
|
99 to_remove = []
|
|
|
100 for i in bb.Instructions:
|
|
|
101 if isinstance(i, ImmLoad):
|
|
|
102 if i.value in constMap:
|
|
|
103 t_new = constMap[i.value]
|
|
|
104 t_old = i.target
|
|
253
|
105 logging.debug('Replacing {} with {}'.format(t_old, t_new))
|
|
252
|
106 for ui in t_old.used_by:
|
|
|
107 ui.replaceValue(t_old, t_new)
|
|
|
108 to_remove.append(i)
|
|
|
109 else:
|
|
|
110 constMap[i.value] = i.target
|
|
|
111 elif isinstance(i, BinaryOperator):
|
|
|
112 k = (i.value1, i.operation, i.value2)
|
|
|
113 if k in constMap:
|
|
|
114 t_old = i.result
|
|
|
115 t_new = constMap[k]
|
|
253
|
116 logging.debug('Replacing {} with {}'.format(t_old, t_new))
|
|
252
|
117 for ui in t_old.used_by:
|
|
|
118 ui.replaceValue(t_old, t_new)
|
|
|
119 to_remove.append(i)
|
|
|
120 else:
|
|
|
121 constMap[k] = i.result
|
|
|
122 for i in to_remove:
|
|
253
|
123 logging.debug('removing {}'.format(i))
|
|
252
|
124 bb.removeInstruction(i)
|
|
240
|
125
|
|
|
126
|
|
177
|
127 class CleanPass(FunctionPass):
|
|
219
|
128 def onFunction(self, f):
|
|
239
|
129 bbs = list(f.BasicBlocks)
|
|
|
130 for bb in bbs:
|
|
253
|
131 # If a block only contains a branch, it can be removed:
|
|
|
132 if len(bb.Instructions) == 1 and type(bb.LastInstruction) is Branch:
|
|
|
133 # This block is empty.
|
|
|
134 # find predecessors of this block and replace this block reference with the jumped reference.
|
|
|
135 ins = bb.LastInstruction
|
|
|
136 preds = bb.Predecessors
|
|
|
137 if bb in preds:
|
|
219
|
138 # Do not remove if preceeded by itself
|
|
|
139 pass
|
|
253
|
140 else:
|
|
219
|
141 for pred in bb.Predecessors:
|
|
|
142 pred.LastInstruction.changeTarget(bb, ins.target)
|
|
|
143 f.removeBasicBlock(bb)
|
|
177
|
144
|
|
240
|
145
|
|
252
|
146
|
|
|
147
|
