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