Mercurial > lcfOS

comparison python/transform.py @ 253:74c6a20302d5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added better logging
author Windel Bouwman
date Wed, 31 Jul 2013 17:57:03 +0200
parents c4370696ccc7
children 7416c923a02a
comparison
equal deleted inserted replaced
252:c4370696ccc7 253:74c6a20302d5
1 """ 1 """
2 Transformation to optimize IR-code 2 Transformation to optimize IR-code
3 """ 3 """
4 4
5 import logging
5 from ir import * 6 from ir import *
6 # Standard passes: 7 # Standard passes:
7 8
8 class FunctionPass: 9 class FunctionPass:
9 def run(self, ir): 10 def run(self, ir):
10 """ Main entry point for the pass """ 11 """ Main entry point for the pass """
11 self.prepare() 12 logging.info('Running pass {}'.format(type(self)))
12 for f in ir.Functions: 13 self.prepare()
13 self.onFunction(f) 14 for f in ir.Functions:
14 def onFunction(self, f): 15 self.onFunction(f)
15 """ Override this virtual method """ 16
16 raise NotImplementedError() 17 def onFunction(self, f):
17 def prepare(self): 18 """ Override this virtual method """
18 pass 19 raise NotImplementedError()
20
21 def prepare(self):
22 pass
19 23
20 24
21 class BasicBlockPass(FunctionPass): 25 class BasicBlockPass(FunctionPass):
22 def onFunction(self, f): 26 def onFunction(self, f):
23 for bb in f.BasicBlocks: 27 for bb in f.BasicBlocks:
62 vr = None 66 vr = None
63 return 67 return
64 self.constMap[i.result] = vr 68 self.constMap[i.result] = vr
65 i.removeDef(i.result) 69 i.removeDef(i.result)
66 i2 = ImmLoad(i.result, vr) 70 i2 = ImmLoad(i.result, vr)
67 print('Replacing', i) 71 logging.debug('Replacing {}'.format(i))
68 i.Parent.replaceInstruction(i, i2) 72 i.Parent.replaceInstruction(i, i2)
69 73
70 74
71 class DeadCodeDeleter(BasicBlockPass): 75 class DeadCodeDeleter(BasicBlockPass):
72 def onBasicBlock(self, bb): 76 def onBasicBlock(self, bb):
73 def instructionUsed(ins): 77 def instructionUsed(ins):
78 if not type(ins) in [ImmLoad, BinaryOperator]:
79 return True
74 if len(ins.defs) == 0: 80 if len(ins.defs) == 0:
75 # In case this instruction does not define any 81 # In case this instruction does not define any
76 # variables, assume it is usefull. 82 # variables, assume it is usefull.
77 return True 83 return True
78 return any(d.Used for d in ins.defs) 84 return any(d.Used for d in ins.defs)
94 for i in bb.Instructions: 100 for i in bb.Instructions:
95 if isinstance(i, ImmLoad): 101 if isinstance(i, ImmLoad):
96 if i.value in constMap: 102 if i.value in constMap:
97 t_new = constMap[i.value] 103 t_new = constMap[i.value]
98 t_old = i.target 104 t_old = i.target
105 logging.debug('Replacing {} with {}'.format(t_old, t_new))
99 for ui in t_old.used_by: 106 for ui in t_old.used_by:
100 ui.replaceValue(t_old, t_new) 107 ui.replaceValue(t_old, t_new)
101 to_remove.append(i) 108 to_remove.append(i)
102 else: 109 else:
103 constMap[i.value] = i.target 110 constMap[i.value] = i.target
104 elif isinstance(i, BinaryOperator): 111 elif isinstance(i, BinaryOperator):
105 k = (i.value1, i.operation, i.value2) 112 k = (i.value1, i.operation, i.value2)
106 if k in constMap: 113 if k in constMap:
107 print('Duplicate binop!', i)
108 t_old = i.result 114 t_old = i.result
109 t_new = constMap[k] 115 t_new = constMap[k]
116 logging.debug('Replacing {} with {}'.format(t_old, t_new))
110 for ui in t_old.used_by: 117 for ui in t_old.used_by:
111 ui.replaceValue(t_old, t_new) 118 ui.replaceValue(t_old, t_new)
112 to_remove.append(i) 119 to_remove.append(i)
113 else: 120 else:
114 constMap[k] = i.result 121 constMap[k] = i.result
115 for i in to_remove: 122 for i in to_remove:
116 print('removing ', i) 123 logging.debug('removing {}'.format(i))
117 bb.removeInstruction(i) 124 bb.removeInstruction(i)
118
119
120 125
121 126
122 class CleanPass(FunctionPass): 127 class CleanPass(FunctionPass):
123 def onFunction(self, f): 128 def onFunction(self, f):
124 bbs = list(f.BasicBlocks) 129 bbs = list(f.BasicBlocks)
125 for bb in bbs: 130 for bb in bbs:
126 # TODO: determine check for 'empty' 131 # If a block only contains a branch, it can be removed:
127 132 if len(bb.Instructions) == 1 and type(bb.LastInstruction) is Branch:
128 # If a block only contains a branch, it can be removed: 133 # This block is empty.
129 if len(bb.Instructions) == 1 and type(bb.LastInstruction) is Branch: 134 # find predecessors of this block and replace this block reference with the jumped reference.
130 # This block is empty. 135 ins = bb.LastInstruction
131 # find predecessors of this block and replace this block reference with the jumped reference. 136 preds = bb.Predecessors
132 ins = bb.LastInstruction 137 if bb in preds:
133 preds = bb.Predecessors
134 if bb in preds:
135 # Do not remove if preceeded by itself 138 # Do not remove if preceeded by itself
136 pass 139 pass
137 else: 140 else:
138 for pred in bb.Predecessors: 141 for pred in bb.Predecessors:
139 pred.LastInstruction.changeTarget(bb, ins.target) 142 pred.LastInstruction.changeTarget(bb, ins.target)
140 f.removeBasicBlock(bb) 143 f.removeBasicBlock(bb)
141 144
142 145
143 def isAllocPromotable(allocinst):
144 # Check if alloc value is only used by load and store operations.
145 assert type(allocinst) is Alloc
146 for use in allocinst.value.used_by:
147 if not type(use) in [Load, Store]:
148 # TODO: check volatile
149 return False
150 otherUse = True
151 return True
152 146
153 147
154 class Mem2RegPromotor(FunctionPass):
155 def promoteSingleBlock(self, ai):
156 print('Single block:', ai)
157 v = ai.value
158 bb = ai.Block
159
160 # Replace all loads with the value:
161 loads = [i for i in v.used_by if isinstance(i, Load)]
162 stores = [i for i in v.used_by if isinstance(i, Store)]
163 stores.sort(key=lambda s: s.Position)
164 stores.reverse()
165 print(stores)
166
167 for load in loads:
168 idx = load.Position
169 # Search upwards:
170 for store in stores:
171 if store.Position < load.Position:
172 break
173 #print('replace {} with {}'.format(load, store.value))
174 for use_ins in load.value.used_by:
175 use_ins.replaceValue(load.value, store.value)
176 assert not load.value.Used
177 print('removing {}'.format(load))
178 bb.removeInstruction(load)
179
180 # Remove store instructions:
181 for store in stores:
182 sv = store.value
183 print('removing {}'.format(store))
184 bb.removeInstruction(store)
185 #assert sv.Used
186
187 # Remove alloca instruction:
188 assert not ai.value.Used, ai.value.used_by
189 bb.removeInstruction(ai)
190
191
192
193 def promote(self, ai):
194 # Find load operations and replace them with assignments
195 v = ai.value
196 if len(ai.value.UsedInBlocks) == 1:
197 self.promoteSingleBlock(ai)
198 return
199
200 loads = [i for i in v.used_by if isinstance(i, Load)]
201 stores = [i for i in v.used_by if isinstance(i, Store)]
202
203 # Each store instruction can be removed (later).
204 # Instead of storing the value, we use it
205 # where the load would have been!
206 replMap = {}
207 for store in stores:
208 replMap[store] = store.value
209
210 # for each load, track back what the defining store
211 # was.
212 for load in loads:
213 print(load)
214
215 def onFunction(self, f):
216 # TODO
217 for bb in f.BasicBlocks:
218 allocs = [i for i in bb.Instructions if isinstance(i, Alloc)]
219 for i in allocs:
220 print(i, isAllocPromotable(i))
221 if isAllocPromotable(i):
222 self.promote(i)
223
224 def optimize(ir):
225 cf = ConstantFolder()
226 dcd = DeadCodeDeleter()
227 m2r = Mem2RegPromotor()
228 clr = CleanPass()
229 cse = CommonSubexpressionElimination()
230 ir.check()
231 cf.run(ir)
232 dcd.run(ir)
233 ir.check()
234 clr.run(ir)
235 ir.check()
236 m2r.run(ir)
237 ir.check()
238 cse.run(ir)
239 ir.check()
240