Mercurial > lcfOS
annotate python/ppci/transform.py @ 306:b145f8e6050b
Start on c3 rewrite
| author | Windel Bouwman |
|---|---|
| date | Mon, 09 Dec 2013 19:00:21 +0100 |
| parents | 6753763d3bec |
| children | 56e6ff84f646 |
| 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): |
| 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 |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
49 |
| 279 | 50 class BasePass(BasicBlockPass): |
| 255 | 51 def onBasicBlock(self, bb): |
| 279 | 52 pass |
| 53 | |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
54 |
| 279 | 55 # Usefull transforms: |
| 56 class ConstantFolder(BasePass): | |
| 57 def __init__(self): | |
| 58 super().__init__() | |
| 59 self.ops = {} | |
| 60 self.ops['+'] = lambda x, y: x + y | |
| 61 self.ops['-'] = lambda x, y: x - y | |
| 62 self.ops['*'] = lambda x, y: x * y | |
| 63 self.ops['<<'] = lambda x, y: x << y | |
| 64 | |
| 65 def postExpr(self, expr): | |
| 66 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
|
67 vr = self.ops[i.operation](i.a.value, i.b.value) |
| 279 | 68 return Const(vr) |
| 69 else: | |
| 70 return expr | |
| 237 | 71 |
| 72 | |
| 174 | 73 class DeadCodeDeleter(BasicBlockPass): |
| 252 | 74 def onBasicBlock(self, bb): |
| 75 def instructionUsed(ins): | |
| 253 | 76 if not type(ins) in [ImmLoad, BinaryOperator]: |
| 77 return True | |
| 252 | 78 if len(ins.defs) == 0: |
| 79 # In case this instruction does not define any | |
| 80 # variables, assume it is usefull. | |
| 81 return True | |
| 82 return any(d.Used for d in ins.defs) | |
| 83 | |
| 84 change = True | |
| 85 while change: | |
| 86 change = False | |
| 87 for i in bb.Instructions: | |
| 88 if instructionUsed(i): | |
| 89 continue | |
| 90 bb.removeInstruction(i) | |
| 91 change = True | |
| 173 | 92 |
| 239 | 93 |
| 252 | 94 class CommonSubexpressionElimination(BasicBlockPass): |
| 239 | 95 def onBasicBlock(self, bb): |
| 96 constMap = {} | |
| 252 | 97 to_remove = [] |
| 98 for i in bb.Instructions: | |
| 99 if isinstance(i, ImmLoad): | |
| 100 if i.value in constMap: | |
| 101 t_new = constMap[i.value] | |
| 102 t_old = i.target | |
| 253 | 103 logging.debug('Replacing {} with {}'.format(t_old, t_new)) |
| 261 | 104 t_old.replaceby(t_new) |
| 252 | 105 to_remove.append(i) |
| 106 else: | |
| 107 constMap[i.value] = i.target | |
| 108 elif isinstance(i, BinaryOperator): | |
| 109 k = (i.value1, i.operation, i.value2) | |
| 110 if k in constMap: | |
| 111 t_old = i.result | |
| 112 t_new = constMap[k] | |
| 253 | 113 logging.debug('Replacing {} with {}'.format(t_old, t_new)) |
| 261 | 114 t_old.replaceby(t_new) |
| 252 | 115 to_remove.append(i) |
| 116 else: | |
| 117 constMap[k] = i.result | |
| 118 for i in to_remove: | |
| 253 | 119 logging.debug('removing {}'.format(i)) |
| 252 | 120 bb.removeInstruction(i) |
| 240 | 121 |
| 122 | |
| 177 | 123 class CleanPass(FunctionPass): |
| 219 | 124 def onFunction(self, f): |
|
280
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
125 removeEmptyBasicBlocks(f) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
126 |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
127 |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
128 def removeEmptyBlocks(f): |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
129 """ Remove empty basic blocks from function. """ |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
130 # If a block only contains a branch, it can be removed: |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
131 empty = lambda b: type(b.FirstInstruction) is ir.Jump |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
132 empty_blocks = list(filter(empty, f.Blocks)) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
133 for b in empty_blocks: |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
134 # Update predecessors |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
135 preds = b.Predecessors |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
136 if b not in preds + [f.entry]: |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
137 # Do not remove if preceeded by itself |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
138 tgt = b.LastInstruction.target |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
139 for pred in preds: |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
140 pred.LastInstruction.changeTarget(b, tgt) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
141 logging.debug('Removing empty block: {}'.format(b)) |
|
02385f62f250
Rework from str interface to Instruction interface
Windel Bouwman
parents:
279
diff
changeset
|
142 f.removeBlock(b) |