Mercurial > lcfOS
annotate python/ppci/transform.py @ 391:a139da1f44f6
Merge
| author | Windel Bouwman |
|---|---|
| date | Fri, 16 May 2014 12:30:10 +0200 |
| parents | c49459768aaa |
| children | 988f3fb861e4 |
| rev | line source |
|---|---|
| 240 | 1 """ |
| 2 Transformation to optimize IR-code | |
| 3 """ | |
| 4 | |
| 253 | 5 import logging |
| 301 | 6 from . import ir |
| 173 | 7 # Standard passes: |
| 8 | |
| 9 class FunctionPass: | |
| 255 | 10 def __init__(self): |
| 316 | 11 self.logger = logging.getLogger(str(self.__class__.__name__)) |
| 255 | 12 |
| 355 | 13 def run(self, ir_module): |
| 253 | 14 """ Main entry point for the pass """ |
| 334 | 15 self.logger.debug('Running pass {}'.format(self.__class__.__name__)) |
| 253 | 16 self.prepare() |
| 355 | 17 if isinstance(ir_module, ir.Module): |
| 18 for f in ir_module.Functions: | |
| 19 self.onFunction(f) | |
| 20 elif isinstance(ir_module, ir.Function): | |
| 21 self.onFunction(ir_module) | |
| 22 else: | |
| 23 raise Exception() | |
| 253 | 24 |
| 25 def onFunction(self, f): | |
| 26 """ Override this virtual method """ | |
| 27 raise NotImplementedError() | |
| 28 | |
| 29 def prepare(self): | |
| 30 pass | |
| 173 | 31 |
| 240 | 32 |
| 173 | 33 class BasicBlockPass(FunctionPass): |
| 240 | 34 def onFunction(self, f): |
| 274 | 35 for bb in f.Blocks: |
| 240 | 36 self.onBasicBlock(bb) |
| 37 | |
| 38 def onBasicBlock(self, bb): | |
| 39 """ Override this virtual method """ | |
| 40 raise NotImplementedError() | |
| 41 | |
| 42 | |
| 173 | 43 class InstructionPass(BasicBlockPass): |
| 240 | 44 def onBasicBlock(self, bb): |
| 45 for ins in iter(bb.Instructions): | |
| 46 self.onInstruction(ins) | |
| 47 | |
| 48 def onInstruction(self, ins): | |
| 49 """ Override this virtual method """ | |
| 50 raise NotImplementedError() | |
| 173 | 51 |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
52 |
| 279 | 53 class BasePass(BasicBlockPass): |
| 255 | 54 def onBasicBlock(self, bb): |
| 279 | 55 pass |
| 56 | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
57 |
| 279 | 58 # Usefull transforms: |
| 59 class ConstantFolder(BasePass): | |
| 60 def __init__(self): | |
| 61 super().__init__() | |
| 62 self.ops = {} | |
| 63 self.ops['+'] = lambda x, y: x + y | |
| 64 self.ops['-'] = lambda x, y: x - y | |
| 65 self.ops['*'] = lambda x, y: x * y | |
| 66 self.ops['<<'] = lambda x, y: x << y | |
| 67 | |
| 68 def postExpr(self, expr): | |
| 69 if type(i) is BinaryOperator and i.operation in self.ops.keys() and type(i.a) is Const and type(i.b) is Const: | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
70 vr = self.ops[i.operation](i.a.value, i.b.value) |
| 279 | 71 return Const(vr) |
| 72 else: | |
| 73 return expr | |
| 237 | 74 |
| 75 | |
| 174 | 76 class DeadCodeDeleter(BasicBlockPass): |
| 252 | 77 def onBasicBlock(self, bb): |
| 78 def instructionUsed(ins): | |
| 253 | 79 if not type(ins) in [ImmLoad, BinaryOperator]: |
| 80 return True | |
| 252 | 81 if len(ins.defs) == 0: |
| 82 # In case this instruction does not define any | |
| 83 # variables, assume it is usefull. | |
| 84 return True | |
| 85 return any(d.Used for d in ins.defs) | |
| 86 | |
| 87 change = True | |
| 88 while change: | |
| 89 change = False | |
| 90 for i in bb.Instructions: | |
| 91 if instructionUsed(i): | |
| 92 continue | |
| 93 bb.removeInstruction(i) | |
| 94 change = True | |
| 173 | 95 |
| 239 | 96 |
| 252 | 97 class CommonSubexpressionElimination(BasicBlockPass): |
| 239 | 98 def onBasicBlock(self, bb): |
| 99 constMap = {} | |
| 252 | 100 to_remove = [] |
| 101 for i in bb.Instructions: | |
| 102 if isinstance(i, ImmLoad): | |
| 103 if i.value in constMap: | |
| 104 t_new = constMap[i.value] | |
| 105 t_old = i.target | |
| 253 | 106 logging.debug('Replacing {} with {}'.format(t_old, t_new)) |
| 261 | 107 t_old.replaceby(t_new) |
| 252 | 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)) |
| 261 | 117 t_old.replaceby(t_new) |
| 252 | 118 to_remove.append(i) |
| 119 else: | |
| 120 constMap[k] = i.result | |
| 121 for i in to_remove: | |
| 316 | 122 self.logger.debug('removing {}'.format(i)) |
| 252 | 123 bb.removeInstruction(i) |
| 240 | 124 |
| 355 | 125 |
| 126 child_nodes = {} | |
| 127 child_nodes[ir.Binop] = ['a', 'b'] | |
| 128 child_nodes[ir.Const] = [] | |
| 129 child_nodes[ir.Temp] = [] | |
| 130 child_nodes[ir.Exp] = ['e'] | |
| 131 child_nodes[ir.Mem] = ['e'] | |
| 132 child_nodes[ir.Addr] = ['e'] | |
| 133 child_nodes[ir.LocalVariable] = [] | |
| 364 | 134 child_nodes[ir.GlobalVariable] = [] |
| 355 | 135 child_nodes[ir.Parameter] = [] |
| 136 child_nodes[ir.Jump] = [] | |
| 137 child_nodes[ir.Terminator] = [] | |
| 138 child_nodes[ir.Call] = ['arguments'] | |
| 139 child_nodes[ir.CJump] = ['a', 'b'] | |
| 140 child_nodes[ir.Move] = ['src', 'dst'] | |
| 141 | |
| 142 | |
| 143 def apply_function(x, f): | |
| 144 """ Recursively apply function """ | |
| 145 # Handle list: | |
| 146 if type(x) is list: | |
| 147 for i in range(len(x)): | |
| 148 x[i] = apply_function(x[i], f) | |
| 149 return x | |
| 150 | |
| 151 # Normal node: | |
| 152 for child in child_nodes[type(x)]: | |
| 153 v = getattr(x, child) | |
| 154 v = apply_function(v, f) | |
| 155 assert not (v is None) | |
| 156 setattr(x, child, v) | |
| 157 # Apply function! | |
| 158 return f(x) | |
| 159 | |
| 160 | |
| 161 class ExpressionFixer(InstructionPass): | |
| 317 | 162 def onInstruction(self, i): |
| 355 | 163 apply_function(i, self.grok) |
| 164 | |
| 165 | |
| 166 class RemoveAddZero(ExpressionFixer): | |
| 167 def grok(self, v): | |
| 168 if type(v) is ir.Binop: | |
| 169 if v.operation == '+': | |
| 170 if type(v.b) is ir.Const and v.b.value == 0: | |
| 171 self.logger.debug('Folding {} to {}'.format(v, v.a)) | |
| 172 return v.a | |
| 173 elif v.operation == '*': | |
| 174 if type(v.b) is ir.Const and v.b.value == 1: | |
| 175 self.logger.debug('Multiple 1 {} to {}'.format(v, v.a)) | |
| 176 return v.a | |
| 177 return v | |
| 178 | |
| 240 | 179 |
| 177 | 180 class CleanPass(FunctionPass): |
| 219 | 181 def onFunction(self, f): |
| 316 | 182 self.remove_empty_blocks(f) |
| 317 | 183 self.remove_one_preds(f) |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
184 |
| 316 | 185 def remove_empty_blocks(self, f): |
| 186 """ Remove empty basic blocks from function. """ | |
| 187 # If a block only contains a branch, it can be removed: | |
| 188 empty = lambda b: type(b.FirstInstruction) is ir.Jump | |
| 189 empty_blocks = list(filter(empty, f.Blocks)) | |
| 190 for b in empty_blocks: | |
| 191 # Update predecessors | |
| 192 preds = b.Predecessors | |
| 193 if b not in preds + [f.entry]: | |
| 194 # Do not remove if preceeded by itself | |
| 195 tgt = b.LastInstruction.target | |
| 196 for pred in preds: | |
| 197 pred.LastInstruction.changeTarget(b, tgt) | |
| 198 self.logger.debug('Removing empty block: {}'.format(b)) | |
| 199 f.removeBlock(b) | |
| 317 | 200 |
| 201 def remove_one_preds(self, f): | |
| 202 """ Remove basic blocks with only one predecessor """ | |
| 203 change = True | |
| 204 while change: | |
| 205 change = False | |
| 206 for block in f.Blocks: | |
| 207 preds = block.Predecessors | |
| 208 if len(preds) == 1 and block not in preds and type(preds[0].LastInstruction) is ir.Jump and block is not f.epiloog: | |
| 209 self.glue_blocks(preds[0], block, f) | |
| 210 change = True | |
| 211 | |
| 212 def glue_blocks(self, block1, block2, f): | |
| 213 """ Glue two blocks together into the first block """ | |
|
336
d1ecc493384e
Added spiffy armtoken class for bit fiddeling. Added cool test that checks for build repeatability
Windel Bouwman
parents:
334
diff
changeset
|
214 self.logger.debug('Merging {} and {}'.format(block1.name, block2.name)) |
| 317 | 215 |
| 216 # Remove the last jump: | |
| 217 block1.removeInstruction(block1.LastInstruction) | |
| 218 | |
| 219 # Copy all instructions to block1: | |
| 220 for instruction in block2.Instructions: | |
| 221 block1.addInstruction(instruction) | |
| 222 # This does not work somehow: | |
| 223 #block2.parent.removeBlock(block2) |