Mercurial > lcfOS
changeset 173:c1d2b6b9f9a7
Rework into passes
| author | Windel Bouwman |
|---|---|
| date | Fri, 19 Apr 2013 12:42:21 +0200 |
| parents | 5a7d37d615ee |
| children | 3eb06f5fb987 |
| files | python/ir/basicblock.py python/ir/function.py python/ir/instruction.py python/ir/module.py python/registerallocator.py python/st-util.py python/testir.py python/transform.py python/x86.py |
| diffstat | 9 files changed, 153 insertions(+), 89 deletions(-) [+] |
line wrap: on
line diff
--- a/python/ir/basicblock.py Thu Apr 04 17:58:37 2013 +0200 +++ b/python/ir/basicblock.py Fri Apr 19 12:42:21 2013 +0200 @@ -5,9 +5,19 @@ self.name = name self.instructions = [] def __repr__(self): - return 'BB {0}'.format(self.name) - def addIns(self, i): + return 'BasicBlock {0}'.format(self.name) + def addInstruction(self, i): + i.parent = self self.instructions.append(i) + addIns = addInstruction + def replaceInstruction(self, i1, i2): + idx = self.instructions.index(i1) + i1.parent = None + i2.parent = self + self.instructions[idx] = i2 + def removeInstruction(self, i): + i.parent = None + self.instructions.remove(i) def getInstructions(self): return self.instructions Instructions = property(getInstructions) @@ -18,6 +28,13 @@ def Empty(self): return len(self.instructions) == 0 @property - def FirstIns(self): + def FirstInstruction(self): return self.instructions[0] + FirstIns = FirstInstruction + def getSuccessors(self): + if not self.Empty: + i = self.LastIns + return i.Targets + return [] + Successors = property(getSuccessors)
--- a/python/ir/function.py Thu Apr 04 17:58:37 2013 +0200 +++ b/python/ir/function.py Fri Apr 19 12:42:21 2013 +0200 @@ -6,7 +6,7 @@ self.bbs = [] self.entry = None def __repr__(self): - return 'FUNC {0}, entry:{1}'.format(self.name, self.entry) + return 'Function {0}'.format(self.name) def addBB(self, bb): self.bbs.append(bb) def getBBs(self):
--- a/python/ir/instruction.py Thu Apr 04 17:58:37 2013 +0200 +++ b/python/ir/instruction.py Fri Apr 19 12:42:21 2013 +0200 @@ -17,16 +17,18 @@ class Instruction: """ Base class for all instructions. """ def __init__(self): - # successors: - self.succ = set() - # predecessors: - self.pred = set() # live variables at this node: self.live_in = set() self.live_out = set() # What variables this instruction uses and defines: self.defs = set() self.uses = set() + def getParent(self): + return self.parent + Parent = property(getParent) + @property + def Targets(self): + return self.getTargets() # Function calling: class Call(Instruction): @@ -40,6 +42,8 @@ class Return(Instruction): def __repr__(self): return 'RET' + def getTargets(self): + return [] class ImmLoad(Instruction): def __init__(self, target, value): @@ -93,6 +97,8 @@ self.target = target def __repr__(self): return 'BRANCH {0}'.format(self.target) + def getTargets(self): + return [self.target] class ConditionalBranch(Instruction): def __init__(self, a, cond, b, lab1, lab2): @@ -110,6 +116,8 @@ self.lab2 = lab2 def __repr__(self): return 'IF {0} {1} {2} THEN {3} ELSE {4}'.format(self.a, self.cond, self.b, self.lab1, self.lab2) + def getTargets(self): + return [self.lab1, self.lab2] class PhiNode(Instruction): def __init__(self):
--- a/python/ir/module.py Thu Apr 04 17:58:37 2013 +0200 +++ b/python/ir/module.py Fri Apr 19 12:42:21 2013 +0200 @@ -37,10 +37,15 @@ print('END') def dumpgv(self, outf): outf.write('digraph G \n{\n') - for i in self.Instructions: - outf.write('{0} [label="{1}"];\n'.format(id(i), i)) - for succ in i.succ: - outf.write('"{0}" -> "{1}" [label="{2}"];\n'.format(id(i), id(succ), succ.live_in)) + for f in self.Functions: + outf.write('{0} [label="{1}"]\n'.format(id(f), f)) + for bb in f.BasicBlocks: + contents = str(bb) + '\n' + contents += '\n'.join([str(i) for i in bb.Instructions]) + outf.write('{0} [label="{1}"];\n'.format(id(bb), contents)) + for successor in bb.Successors: + outf.write('"{0}" -> "{1}"\n'.format(id(bb), id(successor))) + outf.write('"{0}" -> "{1}" [label="entry"]\n'.format(id(f), id(f.entry))) outf.write('}\n') # Analysis functions: @@ -51,73 +56,4 @@ assert type(t) is Value, "def must be Value, not {0}".format(type(t)) for t in i.uses: assert type(t) is Value, "use must be Value, not {0}".format(type(t)) - def analyze(self): - # Determine pred and succ: - def link(a, b): - a.succ.add(b) - b.pred.add(a) - for bb in self.BasicBlocks: - if not bb.Empty: - if len(bb.Instructions) > 1: - for i1, i2 in zip(bb.Instructions[:-1], bb.Instructions[1:]): - link(i1, i2) - else: - print('Only 1 long!', bb, bb.Instructions) - if type(bb.LastIns) is ConditionalBranch: - link(bb.LastIns, bb.LastIns.lab1.FirstIns) - link(bb.LastIns, bb.LastIns.lab2.FirstIns) - if type(bb.LastIns) is Branch: - link(bb.LastIns, bb.LastIns.target.FirstIns) - else: - print('Empty!', bb) - # We now have cfg - # Determine liveness: - for i in self.Instructions: - i.live_in = set() - i.live_out = set() - for z in range(50): - # TODO iterate until converge - for i in self.Instructions: - lo_mk = i.live_out.difference(i.defs) - i.live_in = i.uses.union(lo_mk) - lo = set() - for s in i.succ: - lo = lo.union(s.live_in) - i.live_out = lo - def constantProp(self): - """ Constant propagation. Pre-calculate constant values """ - for i in self.Instructions: - if type(i) is ImmLoad: - i.target.constval = i.value - elif type(i) is BinaryOperator: - a = i.value1 - b = i.value2 - if i.value1.constval and i.value2.constval: - op = i.operation - if op == '+': - i.result.constval = a + b - else: - raise NotImplementedError(op) - else: - i.result.constval = None - - def registerAllocate(self, regs): - print(regs) - allVals = [] - # construct interference: - for i in self.Instructions: - for v in i.live_in: - allVals.append(v) - for v2 in i.live_in: - if v != v2: - v.interferes.add(v2) - # assign random registers: - print(allVals) - regs = set(regs) - for v in allVals: - takenregs = set([iv.reg for iv in v.interferes]) - r2 = list(regs.difference(takenregs)) - # Pick next available: - v.reg = r2[0] -
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/registerallocator.py Fri Apr 19 12:42:21 2013 +0200 @@ -0,0 +1,35 @@ + +class RegisterAllocator: + def live_analyze(self): + # Determine liveness: + for i in self.Instructions: + i.live_in = set() + i.live_out = set() + for z in range(50): + # TODO iterate until converge + for i in self.Instructions: + lo_mk = i.live_out.difference(i.defs) + i.live_in = i.uses.union(lo_mk) + lo = set() + for s in i.succ: + lo = lo.union(s.live_in) + i.live_out = lo + def registerAllocate(self, ir, regs): + print(regs) + allVals = [] + # construct interference: + for i in ir.Instructions: + for v in i.live_in: + allVals.append(v) + for v2 in i.live_in: + if v != v2: + v.interferes.add(v2) + # assign random registers: + print(allVals) + regs = set(regs) + for v in allVals: + takenregs = set([iv.reg for iv in v.interferes]) + r2 = list(regs.difference(takenregs)) + # Pick next available: + v.reg = r2[0] +
--- a/python/st-util.py Thu Apr 04 17:58:37 2013 +0200 +++ b/python/st-util.py Fri Apr 19 12:42:21 2013 +0200 @@ -3,7 +3,7 @@ import sys from PyQt4.QtCore import * from PyQt4.QtGui import * -import stlink, devices, stm32 +import stlink, devices, stm32, usb from devices import Interface, Device from hexedit import HexEdit @@ -255,9 +255,13 @@ ip = idx.internalPointer() if isinstance(ip, Interface): if not ip.IsOpen: - ip.open() - # Try to get a device: - self.mdl.addDevice(ip.createDevice()) + try: + ip.open() + except usb.UsbError as e: + QMessageBox.critical(self, "Error", 'Error opening interface: "{0}"'.format(e)) + else: + # Try to get a device: + self.mdl.addDevice(ip.createDevice()) if isinstance(ip, Device): self.deviceSelected.emit(ip) def openMenu(self, pt):
--- a/python/testir.py Thu Apr 04 17:58:37 2013 +0200 +++ b/python/testir.py Fri Apr 19 12:42:21 2013 +0200 @@ -1,4 +1,4 @@ -import c3, ppci, ir, x86 +import c3, ppci, ir, x86, transform import os testsrc = """ @@ -39,9 +39,13 @@ cgenx86 = x86.X86CodeGen(diag) ir = builder.build(testsrc) diag.printErrors(testsrc) + #ir.dump() + cf = transform.ConstantFolder() + dcd = transform.DeadCodeDeleter() ir.check() - ir.analyze() - #ir.constantProp() + cf.run(ir) + cf.run(ir) + #dcd.run(ir) ir.dump() asm = cgenx86.genBin(ir) for a in asm:
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/transform.py Fri Apr 19 12:42:21 2013 +0200 @@ -0,0 +1,58 @@ +from ir import * +# Standard passes: + +class FunctionPass: + def run(self, ir): + """ Main entry point for the pass """ + for f in ir.Functions: + self.onFunction(f) + def onFunction(self, f): + """ Override this virtual method """ + raise NotImplementedError() + +class BasicBlockPass(FunctionPass): + def onFunction(self, f): + for bb in f.BasicBlocks: + self.onBasicBlock(bb) + def onBasicBlock(self, bb): + """ Override this virtual method """ + raise NotImplementedError() + +class InstructionPass(BasicBlockPass): + def onBasicBlock(self, bb): + for ins in bb.Instructions: + self.onInstruction(ins) + def onInstruction(self, ins): + """ Override this virtual method """ + raise NotImplementedError() + +# Usefull transforms: +class ConstantFolder(InstructionPass): + def onInstruction(self, i): + if type(i) is ImmLoad: + i.target.constval = i.value + print(type(i.value), i.value) + elif type(i) is BinaryOperator: + a = i.value1 + b = i.value2 + if hasattr(a, 'constval') and hasattr(b,'constval'): + op = i.operation + if op == '+': + i2 = ImmLoad(i.result, a.constval + b.constval) + print(i2) + i.Parent.replaceInstruction(i, i2) + elif op == '*': + i2 = ImmLoad(i.result, a.constval * b.constval) + print(i2) + i.Parent.replaceInstruction(i, i2) + elif op == '-': + i2 = ImmLoad(i.result, a.constval - b.constval) + print(i2) + i.Parent.replaceInstruction(i, i2) + +class DeadCodeDeleter(InstructionPass): + def onInstruction(self, ins): + print(ins, ins.Users) + if not ins.defs in ins.live_out: + ins.Parent.removeInstruction(ins) +
--- a/python/x86.py Thu Apr 04 17:58:37 2013 +0200 +++ b/python/x86.py Fri Apr 19 12:42:21 2013 +0200 @@ -1,5 +1,6 @@ import ppci import ir +import registerallocator class AsmLabel: def __init__(self, lab): @@ -33,7 +34,8 @@ def genBin(self, ir): self.asm = [] # Allocate registers: - ir.registerAllocate(self.regs) + ra = registerallocator.RegisterAllocator() + ra.registerAllocate(ir, self.regs) self.genModule(ir) return self.asm