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