Mercurial > lcfOS
view python/ppci/transform.py @ 318:e84047f29c78
Add burg and yacc initial attempts
author | Windel Bouwman |
---|---|
date | Tue, 31 Dec 2013 12:38:15 +0100 |
parents | e30a77ae359b |
children | 6f4753202b9a |
line wrap: on
line source
""" Transformation to optimize IR-code """ import logging from . import ir # Standard passes: class FunctionPass: def __init__(self): self.logger = logging.getLogger(str(self.__class__.__name__)) def run(self, ir): """ Main entry point for the pass """ self.logger.info('Running pass {}'.format(type(self))) self.prepare() for f in ir.Functions: self.onFunction(f) def onFunction(self, f): """ Override this virtual method """ raise NotImplementedError() def prepare(self): pass class BasicBlockPass(FunctionPass): def onFunction(self, f): for bb in f.Blocks: self.onBasicBlock(bb) def onBasicBlock(self, bb): """ Override this virtual method """ raise NotImplementedError() class InstructionPass(BasicBlockPass): def onBasicBlock(self, bb): for ins in iter(bb.Instructions): self.onInstruction(ins) def onInstruction(self, ins): """ Override this virtual method """ raise NotImplementedError() class BasePass(BasicBlockPass): def onBasicBlock(self, bb): pass # Usefull transforms: class ConstantFolder(BasePass): def __init__(self): super().__init__() self.ops = {} self.ops['+'] = lambda x, y: x + y self.ops['-'] = lambda x, y: x - y self.ops['*'] = lambda x, y: x * y self.ops['<<'] = lambda x, y: x << y def postExpr(self, expr): if type(i) is BinaryOperator and i.operation in self.ops.keys() and type(i.a) is Const and type(i.b) is Const: vr = self.ops[i.operation](i.a.value, i.b.value) return Const(vr) else: return expr class DeadCodeDeleter(BasicBlockPass): def onBasicBlock(self, bb): def instructionUsed(ins): if not type(ins) in [ImmLoad, BinaryOperator]: return True if len(ins.defs) == 0: # In case this instruction does not define any # variables, assume it is usefull. return True return any(d.Used for d in ins.defs) change = True while change: change = False for i in bb.Instructions: if instructionUsed(i): continue bb.removeInstruction(i) change = True class CommonSubexpressionElimination(BasicBlockPass): def onBasicBlock(self, bb): constMap = {} to_remove = [] for i in bb.Instructions: if isinstance(i, ImmLoad): if i.value in constMap: t_new = constMap[i.value] t_old = i.target logging.debug('Replacing {} with {}'.format(t_old, t_new)) t_old.replaceby(t_new) to_remove.append(i) else: constMap[i.value] = i.target elif isinstance(i, BinaryOperator): k = (i.value1, i.operation, i.value2) if k in constMap: t_old = i.result t_new = constMap[k] logging.debug('Replacing {} with {}'.format(t_old, t_new)) t_old.replaceby(t_new) to_remove.append(i) else: constMap[k] = i.result for i in to_remove: self.logger.debug('removing {}'.format(i)) bb.removeInstruction(i) class RemoveAddZero(InstructionPass): def onInstruction(self, i): if type(i) is ir.Binop: print(i) pass class CleanPass(FunctionPass): def onFunction(self, f): self.remove_empty_blocks(f) self.remove_one_preds(f) def remove_empty_blocks(self, f): """ Remove empty basic blocks from function. """ # If a block only contains a branch, it can be removed: empty = lambda b: type(b.FirstInstruction) is ir.Jump empty_blocks = list(filter(empty, f.Blocks)) for b in empty_blocks: # Update predecessors preds = b.Predecessors if b not in preds + [f.entry]: # Do not remove if preceeded by itself tgt = b.LastInstruction.target for pred in preds: pred.LastInstruction.changeTarget(b, tgt) self.logger.debug('Removing empty block: {}'.format(b)) f.removeBlock(b) def remove_one_preds(self, f): """ Remove basic blocks with only one predecessor """ change = True while change: change = False for block in f.Blocks: preds = block.Predecessors if len(preds) == 1 and block not in preds and type(preds[0].LastInstruction) is ir.Jump and block is not f.epiloog: self.glue_blocks(preds[0], block, f) change = True def glue_blocks(self, block1, block2, f): """ Glue two blocks together into the first block """ self.logger.info('Glueing {} and {}'.format(block1, block2)) # Remove the last jump: block1.removeInstruction(block1.LastInstruction) # Copy all instructions to block1: for instruction in block2.Instructions: block1.addInstruction(instruction) # This does not work somehow: #block2.parent.removeBlock(block2)