# HG changeset patch # User Windel Bouwman # Date 1374508645 -7200 # Node ID 63bb40758066cd3c88bf7eb5a858c11057d0781e # Parent 90637d1bbfad3ac0ffae2e234ffedc561e538f10 added check diff -r 90637d1bbfad -r 63bb40758066 python/ir/basicblock.py --- a/python/ir/basicblock.py Sat Jul 20 13:18:04 2013 +0200 +++ b/python/ir/basicblock.py Mon Jul 22 17:57:25 2013 +0200 @@ -2,25 +2,27 @@ class BasicBlock: """ Uninterrupted sequence of instructions. """ def __init__(self, name): - self.name = name - self.instructions = [] + self.name = name + self.instructions = [] + def __repr__(self): - return 'BasicBlock {0}'.format(self.name) + return 'BasicBlock {0}'.format(self.name) + def addInstruction(self, i): - i.parent = self - self.instructions.append(i) + i.parent = self + self.instructions.append(i) addIns = addInstruction def replaceInstruction(self, i1, i2): - idx = self.instructions.index(i1) - i1.parent = None - i1.delete() - i2.parent = self - self.instructions[idx] = i2 + idx = self.instructions.index(i1) + i1.parent = None + i1.delete() + i2.parent = self + self.instructions[idx] = i2 def removeInstruction(self, i): - i.parent = None - self.instructions.remove(i) + i.parent = None + self.instructions.remove(i) def getInstructions(self): return self.instructions @@ -34,14 +36,16 @@ Instructions = property(getInstructions, setInstructions) def getLastIns(self): - return self.instructions[-1] + return self.instructions[-1] LastInstruction = property(getLastIns) + @property def Empty(self): - return len(self.instructions) == 0 + return len(self.instructions) == 0 + @property def FirstInstruction(self): - return self.instructions[0] + return self.instructions[0] FirstIns = FirstInstruction def getSuccessors(self): @@ -52,10 +56,14 @@ Successors = property(getSuccessors) def getPredecessors(self): - preds = [] - for bb in self.parent.BasicBlocks: - if self in bb.Successors: - preds.append(bb) - return preds + preds = [] + for bb in self.parent.BasicBlocks: + if self in bb.Successors: + preds.append(bb) + return preds Predecessors = property(getPredecessors) + def check(self): + for ins in self.Instructions: + ins.check() + diff -r 90637d1bbfad -r 63bb40758066 python/ir/function.py --- a/python/ir/function.py Sat Jul 20 13:18:04 2013 +0200 +++ b/python/ir/function.py Mon Jul 22 17:57:25 2013 +0200 @@ -29,4 +29,6 @@ BasicBlocks = property(getBBs) - + def check(self): + for bb in self.BasicBlocks: + bb.check() diff -r 90637d1bbfad -r 63bb40758066 python/ir/instruction.py --- a/python/ir/instruction.py Sat Jul 20 13:18:04 2013 +0200 +++ b/python/ir/instruction.py Mon Jul 22 17:57:25 2013 +0200 @@ -5,58 +5,116 @@ class Value: """ Temporary SSA value (value that is assigned only once! """ def __init__(self, name): - # TODO: add typing? for now only handle integers - self.name = name - self.used_by = [] + # TODO: add typing? for now only handle integers + self.name = name + self.used_by = [] + self.Setter = None def __repr__(self): return '{0}'.format(self.name) # + str(self.IsUsed) @property def IsUsed(self): - return len(self.used_by) > 0 + return len(self.used_by) > 0 + + def onlyUsedInBlock(self, bb): + for use in self.used_by: + ins = use + if ins.parent != bb: + return False + return True + class Variable(Value): pass + class Use: - def __init__(self, user, val): - self.user = user - assert isinstance(val, Value) - self.val = val - self.val.used_by.append(self.user) - def delete(self): - self.val.used_by.remove(self.user) + def __init__(self, user, val): + self.user = user + assert isinstance(val, Value) + self.val = val + self.val.used_by.append(self.user) + + def delete(self): + self.val.used_by.remove(self.user) + class Instruction: - """ Base class for all instructions. """ - def __init__(self): - # live variables at this node: - self.live_in = set() - self.live_out = set() - # What variables this instruction uses and defines: - self.defs = [] - self.uses = [] - def delete(self): + """ Base class for all instructions. """ + def __init__(self): + # live variables at this node: + self.live_in = set() + self.live_out = set() + # What variables this instruction uses and defines: + self.defs = [] + self.uses = [] + def delete(self): while self.uses: use = self.uses.pop() use.delete() - def addUse(self, val): - self.uses.append(Use(self, val)) - def addDef(self, v): - self.defs.append(v) - def getParent(self): - return self.parent - def setParent(self, p): - self.parent = p - Parent = property(getParent, setParent) + while self.defs: + d = self.defs.pop() + d.Setter = None + + def addUse(self, val): + self.uses.append(Use(self, val)) + + def removeUse(self, val): + for u in self.uses: + if u.val is val: + theUse = u + theUse.delete() + self.uses.remove(theUse) + + def addDef(self, v): + self.defs.append(v) + assert v.Setter == None + v.Setter = self + + def removeDef(self, v): + assert v.Setter is self + v.Setter = None + self.defs.remove(v) + + def getParent(self): + return self.parent + + def setParent(self, p): + self.parent = p + Parent = property(getParent, setParent) + + def replaceValue(self, old, new): + raise NotImplementedError() + + @property + def Position(self): + return self.parent.Instructions.index(self) + + def check(self): + # Check that the variables defined by this instruction + # are only used in the same block + for v in self.defs: + assert v.Setter is self + for ub in v.used_by: + assert ub.parent == self.parent + + # Check that variables used are defined earlier: + for u in self.uses: + v = u.val + assert self.Position > v.Setter.Position + + + class Terminator(Instruction): - @property - def Targets(self): - return self.getTargets() - def changeTarget(self, tfrom, tto): - pass + @property + def Targets(self): + return self.getTargets() + + def changeTarget(self, tfrom, tto): + pass + # Function calling: class Call(Instruction): @@ -112,7 +170,7 @@ self.value = value self.addDef(target) def __repr__(self): - return '{0} = {1}'.format(self.target, self.value) + return '{} = {}'.format(self.target, self.value) # Data operations class BinaryOperator(Instruction): @@ -129,10 +187,23 @@ self.addUse(value1) self.addUse(value2) self.operation = operation + def __repr__(self): a, b = self.value1, self.value2 return '{} = {} {} {}'.format(self.result, a, self.operation, b) + def replaceValue(self, old, new): + if old is self.value1: + self.value1 = new + elif old is self.value2: + self.value2 = new + elif old is self.result: + self.result = new + else: + raise Exception() + self.removeUse(old) + self.addUse(new) + # Memory functions: class Load(Instruction): def __init__(self, location, value): diff -r 90637d1bbfad -r 63bb40758066 python/ir/module.py --- a/python/ir/module.py Sat Jul 20 13:18:04 2013 +0200 +++ b/python/ir/module.py Mon Jul 22 17:57:25 2013 +0200 @@ -78,10 +78,13 @@ # Analysis functions: def check(self): - """ Perform sanity check on module """ - for i in self.Instructions: + """ 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 f in self.Functions: + f.check() + diff -r 90637d1bbfad -r 63bb40758066 python/transform.py --- a/python/transform.py Sat Jul 20 13:18:04 2013 +0200 +++ b/python/transform.py Mon Jul 22 17:57:25 2013 +0200 @@ -51,6 +51,7 @@ vr = None return self.constMap[i.result] = vr + i.removeDef(i.result) i2 = ImmLoad(i.result, vr) i.Parent.replaceInstruction(i, i2) @@ -97,6 +98,27 @@ return False bb.Instructions = list(filter(instructionUsed, bb.Instructions)) + +class SameImmLoadDeletePass(BasicBlockPass): + def onBasicBlock(self, bb): + constMap = {} + imms = filter(lambda i: isinstance(i, ImmLoad), bb.Instructions) + for ins in list(imms): + if ins.value in constMap: + # remove this immload and update all references to the target + t_old = ins.target + if not t_old.onlyUsedInBlock(bb): + continue + # update all references: + t_new = constMap[ins.value] + print('Replace {} with {}'.format(t_old, t_new)) + for use in t_old.used_by: + use.replaceValue(t_old, t_new) + bb.removeInstruction(ins) + else: + constMap[ins.value] = ins.target + + def isAllocPromotable(allocinst): # Check if alloc value is only used by load and store operations. assert type(allocinst) is Alloc @@ -109,21 +131,20 @@ class CleanPass(FunctionPass): def onFunction(self, f): - bbs = list(f.BasicBlocks) - for bb in bbs: + 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: + 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 - if type(ins) is Branch: - preds = bb.Predecessors - if bb in preds: + 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) diff -r 90637d1bbfad -r 63bb40758066 python/zcc.py --- a/python/zcc.py Sat Jul 20 13:18:04 2013 +0200 +++ b/python/zcc.py Mon Jul 22 17:57:25 2013 +0200 @@ -3,7 +3,7 @@ import sys, argparse import c3, ppci, codegen import codegenarm -from transform import CleanPass +from transform import CleanPass, SameImmLoadDeletePass import outstream # Parse arguments: @@ -26,8 +26,13 @@ sys.exit(1) # Optimization passes: + ircode.check() cp = CleanPass() cp.run(ircode) + ircode.check() + sidp = SameImmLoadDeletePass() + sidp.run(ircode) + ircode.check() if args.dumpir: ircode.dump()