Mercurial > lcfOS
annotate python/ppci/transform.py @ 334:6f4753202b9a
Added more recipes
| author | Windel Bouwman |
|---|---|
| date | Thu, 13 Feb 2014 22:02:08 +0100 |
| parents | e30a77ae359b |
| children | d1ecc493384e |
| 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 |
| 253 | 13 def run(self, ir): |
| 14 """ Main entry point for the pass """ | |
| 334 | 15 self.logger.debug('Running pass {}'.format(self.__class__.__name__)) |
| 253 | 16 self.prepare() |
| 17 for f in ir.Functions: | |
| 18 self.onFunction(f) | |
| 19 | |
| 20 def onFunction(self, f): | |
| 21 """ Override this virtual method """ | |
| 22 raise NotImplementedError() | |
| 23 | |
| 24 def prepare(self): | |
| 25 pass | |
| 173 | 26 |
| 240 | 27 |
| 173 | 28 class BasicBlockPass(FunctionPass): |
| 240 | 29 def onFunction(self, f): |
| 274 | 30 for bb in f.Blocks: |
| 240 | 31 self.onBasicBlock(bb) |
| 32 | |
| 33 def onBasicBlock(self, bb): | |
| 34 """ Override this virtual method """ | |
| 35 raise NotImplementedError() | |
| 36 | |
| 37 | |
| 173 | 38 class InstructionPass(BasicBlockPass): |
| 240 | 39 def onBasicBlock(self, bb): |
| 40 for ins in iter(bb.Instructions): | |
| 41 self.onInstruction(ins) | |
| 42 | |
| 43 def onInstruction(self, ins): | |
| 44 """ Override this virtual method """ | |
| 45 raise NotImplementedError() | |
| 173 | 46 |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
47 |
| 279 | 48 class BasePass(BasicBlockPass): |
| 255 | 49 def onBasicBlock(self, bb): |
| 279 | 50 pass |
| 51 | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
52 |
| 279 | 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: | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
65 vr = self.ops[i.operation](i.a.value, i.b.value) |
| 279 | 66 return Const(vr) |
| 67 else: | |
| 68 return expr | |
| 237 | 69 |
| 70 | |
| 174 | 71 class DeadCodeDeleter(BasicBlockPass): |
| 252 | 72 def onBasicBlock(self, bb): |
| 73 def instructionUsed(ins): | |
| 253 | 74 if not type(ins) in [ImmLoad, BinaryOperator]: |
| 75 return True | |
| 252 | 76 if len(ins.defs) == 0: |
| 77 # In case this instruction does not define any | |
| 78 # variables, assume it is usefull. | |
| 79 return True | |
| 80 return any(d.Used for d in ins.defs) | |
| 81 | |
| 82 change = True | |
| 83 while change: | |
| 84 change = False | |
| 85 for i in bb.Instructions: | |
| 86 if instructionUsed(i): | |
| 87 continue | |
| 88 bb.removeInstruction(i) | |
| 89 change = True | |
| 173 | 90 |
| 239 | 91 |
| 252 | 92 class CommonSubexpressionElimination(BasicBlockPass): |
| 239 | 93 def onBasicBlock(self, bb): |
| 94 constMap = {} | |
| 252 | 95 to_remove = [] |
| 96 for i in bb.Instructions: | |
| 97 if isinstance(i, ImmLoad): | |
| 98 if i.value in constMap: | |
| 99 t_new = constMap[i.value] | |
| 100 t_old = i.target | |
| 253 | 101 logging.debug('Replacing {} with {}'.format(t_old, t_new)) |
| 261 | 102 t_old.replaceby(t_new) |
| 252 | 103 to_remove.append(i) |
| 104 else: | |
| 105 constMap[i.value] = i.target | |
| 106 elif isinstance(i, BinaryOperator): | |
| 107 k = (i.value1, i.operation, i.value2) | |
| 108 if k in constMap: | |
| 109 t_old = i.result | |
| 110 t_new = constMap[k] | |
| 253 | 111 logging.debug('Replacing {} with {}'.format(t_old, t_new)) |
| 261 | 112 t_old.replaceby(t_new) |
| 252 | 113 to_remove.append(i) |
| 114 else: | |
| 115 constMap[k] = i.result | |
| 116 for i in to_remove: | |
| 316 | 117 self.logger.debug('removing {}'.format(i)) |
| 252 | 118 bb.removeInstruction(i) |
| 240 | 119 |
| 317 | 120 class RemoveAddZero(InstructionPass): |
| 121 def onInstruction(self, i): | |
| 122 if type(i) is ir.Binop: | |
| 123 print(i) | |
| 124 pass | |
| 240 | 125 |
| 177 | 126 class CleanPass(FunctionPass): |
| 219 | 127 def onFunction(self, f): |
| 316 | 128 self.remove_empty_blocks(f) |
| 317 | 129 self.remove_one_preds(f) |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
130 |
| 316 | 131 def remove_empty_blocks(self, f): |
| 132 """ Remove empty basic blocks from function. """ | |
| 133 # If a block only contains a branch, it can be removed: | |
| 134 empty = lambda b: type(b.FirstInstruction) is ir.Jump | |
| 135 empty_blocks = list(filter(empty, f.Blocks)) | |
| 136 for b in empty_blocks: | |
| 137 # Update predecessors | |
| 138 preds = b.Predecessors | |
| 139 if b not in preds + [f.entry]: | |
| 140 # Do not remove if preceeded by itself | |
| 141 tgt = b.LastInstruction.target | |
| 142 for pred in preds: | |
| 143 pred.LastInstruction.changeTarget(b, tgt) | |
| 144 self.logger.debug('Removing empty block: {}'.format(b)) | |
| 145 f.removeBlock(b) | |
| 317 | 146 |
| 147 def remove_one_preds(self, f): | |
| 148 """ Remove basic blocks with only one predecessor """ | |
| 149 change = True | |
| 150 while change: | |
| 151 change = False | |
| 152 for block in f.Blocks: | |
| 153 preds = block.Predecessors | |
| 154 if len(preds) == 1 and block not in preds and type(preds[0].LastInstruction) is ir.Jump and block is not f.epiloog: | |
| 155 self.glue_blocks(preds[0], block, f) | |
| 156 change = True | |
| 157 | |
| 158 def glue_blocks(self, block1, block2, f): | |
| 159 """ Glue two blocks together into the first block """ | |
| 334 | 160 self.logger.debug('Glueing {} and {}'.format(block1, block2)) |
| 317 | 161 |
| 162 # Remove the last jump: | |
| 163 block1.removeInstruction(block1.LastInstruction) | |
| 164 | |
| 165 # Copy all instructions to block1: | |
| 166 for instruction in block2.Instructions: | |
| 167 block1.addInstruction(instruction) | |
| 168 # This does not work somehow: | |
| 169 #block2.parent.removeBlock(block2) |