# HG changeset patch # User Windel Bouwman # Date 1375286223 -7200 # Node ID 74c6a20302d5fad0465bc6b7a1481036e45bd675 # Parent c4370696ccc7d6968a99d4c7ac79b558457f19f3 Added better logging diff -r c4370696ccc7 -r 74c6a20302d5 python/ir/function.py --- a/python/ir/function.py Tue Jul 30 17:57:46 2013 +0200 +++ b/python/ir/function.py Wed Jul 31 17:57:03 2013 +0200 @@ -29,6 +29,23 @@ BasicBlocks = property(getBBs) + @property + def Entry(self): + return self.BasicBlocks[0] + def check(self): for bb in self.BasicBlocks: bb.check() + + def call(self, *args): + print(args) + varmap = {} + bb = self.Entry + ip = 0 + while True: + i = bb.Instructions[ip] + ip += 1 + print(i) + return + + diff -r c4370696ccc7 -r 74c6a20302d5 python/ir/module.py --- a/python/ir/module.py Tue Jul 30 17:57:46 2013 +0200 +++ b/python/ir/module.py Wed Jul 31 17:57:03 2013 +0200 @@ -3,51 +3,52 @@ from .basicblock import BasicBlock class Module: - """ Main container for a piece of code. """ - def __init__(self, name): + """ Main container for a piece of code. """ + def __init__(self, name): self.name = name self.funcs = [] self.variables = [] - def __repr__(self): - return 'IR-module [{0}]'.format(self.name) + def __repr__(self): + return 'IR-module [{0}]'.format(self.name) - def getInstructions(self): + def getInstructions(self): ins = [] for bb in self.BasicBlocks: ins += bb.Instructions return ins - Instructions = property(getInstructions) + Instructions = property(getInstructions) - def getBBs(self): + def getBBs(self): bbs = [] for f in self.Functions: bbs += f.BasicBlocks return bbs - BasicBlocks = property(getBBs) - def addFunc(self, f): + BasicBlocks = property(getBBs) + def addFunc(self, f): self.funcs.append(f) - addFunction = addFunc + addFunction = addFunc - def addVariable(self, v): + def addVariable(self, v): self.variables.append(v) - def getVariables(self): + def getVariables(self): return self.variables - Variables = property(getVariables) + Variables = property(getVariables) - def getFunctions(self): - return self.funcs - Functions = property(getFunctions) + def getFunctions(self): + return self.funcs + Functions = property(getFunctions) - def findFunction(self, name): + def findFunction(self, name): for f in self.funcs: if f.name == name: return f raise KeyError(name) + getFunction = findFunction - def dump(self): + def dump(self): print(self) for v in self.Variables: print(' ', v) @@ -58,7 +59,7 @@ for ins in bb.Instructions: print(' ', ins) - def dumpgv(self, outf): + def dumpgv(self, outf): outf.write('digraph G \n{\n') for f in self.Functions: outf.write('{0} [label="{1}" shape=box3d]\n'.format(id(f), f)) @@ -76,14 +77,14 @@ outf.write('"{0}" -> "{1}" [label="entry"]\n'.format(id(f), id(f.entry))) outf.write('}\n') - # Analysis functions: - def check(self): + # Analysis functions: + def check(self): """ Perform sanity check on module """ for i in self.Instructions: - for t in i.defs: - assert type(t) is Value, "def must be Value, not {0}".format(type(t)) - for t in i.uses: - assert type(t) is Use, "use must be Value, not {0}".format(type(t)) + for t in i.defs: + assert type(t) is Value, "def must be Value, not {0}".format(type(t)) + for t in i.uses: + assert type(t) is Use, "use must be Value, not {0}".format(type(t)) for f in self.Functions: f.check() diff -r c4370696ccc7 -r 74c6a20302d5 python/mem2reg.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/mem2reg.py Wed Jul 31 17:57:03 2013 +0200 @@ -0,0 +1,72 @@ +import logging +from transform import FunctionPass +from ir import * + +def isAllocPromotable(allocinst): + # Check if alloc value is only used by load and store operations. + assert type(allocinst) is Alloc + return all(type(use) in [Load,Store] for use in allocinst.value.used_by) + +class Mem2RegPromotor(FunctionPass): + def promoteSingleBlock(self, ai): + v = ai.value + bb = ai.Block + + # Replace all loads with the value: + loads = [i for i in v.used_by if isinstance(i, Load)] + stores = [i for i in v.used_by if isinstance(i, Store)] + stores.sort(key=lambda s: s.Position) + stores.reverse() + + for load in loads: + idx = load.Position + # Search upwards: + for store in stores: + if store.Position < load.Position: + break + for use_ins in load.value.used_by: + use_ins.replaceValue(load.value, store.value) + assert not load.value.Used + logging.debug('replaced {} with {}'.format(load, store.value)) + bb.removeInstruction(load) + + # Remove store instructions: + for store in stores: + sv = store.value + logging.debug('removing {}'.format(store)) + bb.removeInstruction(store) + #assert sv.Used + + # Remove alloca instruction: + assert not ai.value.Used, ai.value.used_by + bb.removeInstruction(ai) + + def promote(self, ai): + # Find load operations and replace them with assignments + v = ai.value + if len(ai.value.UsedInBlocks) == 1: + self.promoteSingleBlock(ai) + return + + loads = [i for i in v.used_by if isinstance(i, Load)] + stores = [i for i in v.used_by if isinstance(i, Store)] + + # Each store instruction can be removed (later). + # Instead of storing the value, we use it + # where the load would have been! + replMap = {} + for store in stores: + replMap[store] = store.value + + # for each load, track back what the defining store + # was. + for load in loads: + pass + + def onFunction(self, f): + for bb in f.BasicBlocks: + allocs = [i for i in bb.Instructions if isinstance(i, Alloc)] + for i in allocs: + if isAllocPromotable(i): + self.promote(i) + diff -r c4370696ccc7 -r 74c6a20302d5 python/optimize.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/optimize.py Wed Jul 31 17:57:03 2013 +0200 @@ -0,0 +1,23 @@ +from mem2reg import Mem2RegPromotor +from transform import CommonSubexpressionElimination, CleanPass +from transform import DeadCodeDeleter, ConstantFolder + +def optimize(ir): + cf = ConstantFolder() + dcd = DeadCodeDeleter() + m2r = Mem2RegPromotor() + clr = CleanPass() + cse = CommonSubexpressionElimination() + ir.check() + cf.run(ir) + dcd.run(ir) + ir.check() + clr.run(ir) + ir.check() + m2r.run(ir) + ir.check() + cse.run(ir) + ir.check() + + + diff -r c4370696ccc7 -r 74c6a20302d5 python/testir.py --- a/python/testir.py Tue Jul 30 17:57:46 2013 +0200 +++ b/python/testir.py Wed Jul 31 17:57:03 2013 +0200 @@ -2,6 +2,24 @@ import sys import c3, ppci, ir, x86, transform +class IrCodeTestCase(unittest.TestCase): + def setUp(self): + self.b = ir.Builder() + self.m = ir.Module('test') + self.b.setModule(self.m) + + def testBuilder(self): + f = self.b.newFunction('add') + self.b.setFunction(f) + bb = self.b.newBB() + self.b.setBB(bb) + v1 = self.b.newTmp('t') + self.b.addIns(ir.Return(v1)) + self.m.check() + # Run interpreter: + r = self.m.getFunction('add').call(1, 2) + #self.assertEqual(3, r) + class ConstantFolderTestCase(unittest.TestCase): def setUp(self): self.b = ir.Builder() diff -r c4370696ccc7 -r 74c6a20302d5 python/transform.py --- a/python/transform.py Tue Jul 30 17:57:46 2013 +0200 +++ b/python/transform.py Wed Jul 31 17:57:03 2013 +0200 @@ -2,20 +2,24 @@ Transformation to optimize IR-code """ +import logging from ir import * # Standard passes: class FunctionPass: - def run(self, ir): - """ Main entry point for the pass """ - self.prepare() - for f in ir.Functions: - self.onFunction(f) - def onFunction(self, f): - """ Override this virtual method """ - raise NotImplementedError() - def prepare(self): - pass + def run(self, ir): + """ Main entry point for the pass """ + logging.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): @@ -64,13 +68,15 @@ self.constMap[i.result] = vr i.removeDef(i.result) i2 = ImmLoad(i.result, vr) - print('Replacing', i) + logging.debug('Replacing {}'.format(i)) i.Parent.replaceInstruction(i, i2) 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. @@ -96,6 +102,7 @@ if i.value in constMap: t_new = constMap[i.value] t_old = i.target + logging.debug('Replacing {} with {}'.format(t_old, t_new)) for ui in t_old.used_by: ui.replaceValue(t_old, t_new) to_remove.append(i) @@ -104,137 +111,37 @@ elif isinstance(i, BinaryOperator): k = (i.value1, i.operation, i.value2) if k in constMap: - print('Duplicate binop!', i) t_old = i.result t_new = constMap[k] + logging.debug('Replacing {} with {}'.format(t_old, t_new)) for ui in t_old.used_by: ui.replaceValue(t_old, t_new) to_remove.append(i) else: constMap[k] = i.result for i in to_remove: - print('removing ', i) + logging.debug('removing {}'.format(i)) bb.removeInstruction(i) - - class CleanPass(FunctionPass): def onFunction(self, f): bbs = list(f.BasicBlocks) for bb in bbs: - # TODO: determine check for 'empty' - - # If a block only contains a branch, it can be removed: - if len(bb.Instructions) == 1 and type(bb.LastInstruction) is Branch: - # This block is empty. - # find predecessors of this block and replace this block reference with the jumped reference. - ins = bb.LastInstruction - preds = bb.Predecessors - if bb in preds: + # If a block only contains a branch, it can be removed: + if len(bb.Instructions) == 1 and type(bb.LastInstruction) is Branch: + # This block is empty. + # find predecessors of this block and replace this block reference with the jumped reference. + ins = bb.LastInstruction + preds = bb.Predecessors + if bb in preds: # Do not remove if preceeded by itself pass - else: + else: for pred in bb.Predecessors: pred.LastInstruction.changeTarget(bb, ins.target) f.removeBasicBlock(bb) -def isAllocPromotable(allocinst): - # Check if alloc value is only used by load and store operations. - assert type(allocinst) is Alloc - for use in allocinst.value.used_by: - if not type(use) in [Load, Store]: - # TODO: check volatile - return False - otherUse = True - return True -class Mem2RegPromotor(FunctionPass): - def promoteSingleBlock(self, ai): - print('Single block:', ai) - v = ai.value - bb = ai.Block - - # Replace all loads with the value: - loads = [i for i in v.used_by if isinstance(i, Load)] - stores = [i for i in v.used_by if isinstance(i, Store)] - stores.sort(key=lambda s: s.Position) - stores.reverse() - print(stores) - - for load in loads: - idx = load.Position - # Search upwards: - for store in stores: - if store.Position < load.Position: - break - #print('replace {} with {}'.format(load, store.value)) - for use_ins in load.value.used_by: - use_ins.replaceValue(load.value, store.value) - assert not load.value.Used - print('removing {}'.format(load)) - bb.removeInstruction(load) - - # Remove store instructions: - for store in stores: - sv = store.value - print('removing {}'.format(store)) - bb.removeInstruction(store) - #assert sv.Used - - # Remove alloca instruction: - assert not ai.value.Used, ai.value.used_by - bb.removeInstruction(ai) - - - - def promote(self, ai): - # Find load operations and replace them with assignments - v = ai.value - if len(ai.value.UsedInBlocks) == 1: - self.promoteSingleBlock(ai) - return - - loads = [i for i in v.used_by if isinstance(i, Load)] - stores = [i for i in v.used_by if isinstance(i, Store)] - - # Each store instruction can be removed (later). - # Instead of storing the value, we use it - # where the load would have been! - replMap = {} - for store in stores: - replMap[store] = store.value - - # for each load, track back what the defining store - # was. - for load in loads: - print(load) - - def onFunction(self, f): - # TODO - for bb in f.BasicBlocks: - allocs = [i for i in bb.Instructions if isinstance(i, Alloc)] - for i in allocs: - print(i, isAllocPromotable(i)) - if isAllocPromotable(i): - self.promote(i) - -def optimize(ir): - cf = ConstantFolder() - dcd = DeadCodeDeleter() - m2r = Mem2RegPromotor() - clr = CleanPass() - cse = CommonSubexpressionElimination() - ir.check() - cf.run(ir) - dcd.run(ir) - ir.check() - clr.run(ir) - ir.check() - m2r.run(ir) - ir.check() - cse.run(ir) - ir.check() - diff -r c4370696ccc7 -r 74c6a20302d5 python/zcc.py --- a/python/zcc.py Tue Jul 30 17:57:46 2013 +0200 +++ b/python/zcc.py Wed Jul 31 17:57:03 2013 +0200 @@ -3,27 +3,37 @@ import sys, argparse import c3, ppci, codegen import codegenarm -import transform +from optimize import optimize import outstream import hexfile +import logging + +def logLevel(s): + numeric_level = getattr(logging, s.upper(), None) + if not isinstance(numeric_level, int): + raise ValueError('Invalid log level: {}'.format(s)) + return numeric_level # Parse arguments: parser = argparse.ArgumentParser(description='lcfos Compiler') parser.add_argument('source', type=argparse.FileType('r'), \ help='the source file to build') -parser.add_argument('-d', '--dumpir', action='store_true', help="Dump IR-code") +parser.add_argument('--dumpir', action='store_true', help="Dump IR-code") parser.add_argument('-o', '--output', help='Output file', metavar='filename') parser.add_argument('--hexfile', help='Output hexfile', type=argparse.FileType('w')) +parser.add_argument('--log', help='Log level (INFO,DEBUG)', type=logLevel) def zcc(src, outs, diag, dumpir=False): # Front end: c3b = c3.Builder(diag) ircode = c3b.build(src) + logging.info('Intermediate code generated') if not ircode: return # Optimization passes: - transform.optimize(ircode) + optimize(ircode) + logging.info('IR-code optimized') if dumpir: ircode.dump() @@ -34,8 +44,10 @@ return True def main(args): + logging.basicConfig(format='%(asctime)s %(levelname)s %(message)s', level=args.log) src = args.source.read() args.source.close() + logging.info('Source loaded') diag = ppci.DiagnosticsManager() outs = outstream.TextOutputStream() @@ -45,8 +57,8 @@ diag.printErrors(src) sys.exit(1) - if args.dumpir: - outs.dump() + #if args.dumpir: + # outs.dump() code_bytes = outs.sections['code'].to_bytes() #print('bytes:', code_bytes) @@ -62,6 +74,7 @@ hf = hexfile.HexFile() hf.addRegion(0x08000000, code_bytes) hf.save(args.hexfile) + logging.info('Hexfile created') if __name__ == '__main__': arguments = parser.parse_args()