Mercurial > lcfOS

comparison python/x86.py @ 180:25a0753da4cf

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Re-organized files
author Windel Bouwman
date Thu, 09 May 2013 17:35:19 +0200
parents c694ec551f34
children 6b2bec5653f1
comparison
equal deleted inserted replaced
179:0f3b1adfd416 180:25a0753da4cf
1 import ppci 1 import ppci
2 import ir 2 import ir
3 import registerallocator
4 3
5 # Instruction selection with DAG (Directed Acyclic Graph) 4 class X86CodeGenSimple:
6 class DagLeaf: 5 """ Inefficient code generation, assume stack machine """
7 def __init__(self, v):
8 self.v = v
9
10 class DagNode:
11 def __init__(self, name):
12 self.name = name
13 self.children = []
14 def __repr__(self):
15 return str(self.name)
16
17 class Dag:
18 def __init__(self, bb):
19 self.mapping = {}
20 self.buildFromBB(bb)
21 def buildFromBB(self, bb):
22 for ins in bb.Instructions:
23 if type(ins) is ir.BinaryOperator:
24 if not ins.value1 in self.mapping:
25 self.mapping[ins.value1] = DagNode(ins.value1)
26 if not ins.value2 in self.mapping:
27 self.mapping[ins.value2] = DagNode(ins.value2)
28 # look for op with left and right operand the same:
29 N = None
30 lnode = self.mapping[ins.value1]
31 rnode = self.mapping[ins.value2]
32 for node in self.mapping.values():
33 if node.name == ins.operation:
34 if node.children[0] == lnode and node.children[1] == rnode:
35 N = node
36 break
37 if not N:
38 # Create a node.
39 N = DagNode(ins.operation)
40 N.children.append(lnode)
41 N.children.append(rnode)
42 self.mapping[ins.result] = N
43 else:
44 pass
45 def dumpgv(self, outf):
46 outf.write('subgraph {0} {{\n'.format(id(self)))
47 for node in self.mapping.values():
48 outf.write('{0} [label="{1}"];\n'.format(id(node), node.name))
49 for c in node.children:
50 outf.write('{0} -> {1};\n'.format(id(node), id(c)))
51 outf.write('label="dag"}\n')
52
53 def insSelect(mod):
54 """ Create DAG from ir-code """
55 for bb in mod.BasicBlocks:
56 print(bb)
57 dag = Dag(bb)
58 print(dag.mapping)
59 bb.dag = dag
60
61 # Machine code interface:
62 class MachineOperand:
63 """ Single machine operand """
64 pass
65
66 class MachineInstruction:
67 def __init__(self, opcode):
68 self.opcode = opcode
69 self.operands = []
70
71
72 # x86 specific:
73 class AsmLabel:
74 def __init__(self, lab):
75 self.lab = lab
76 def __repr__(self):
77 return '{0}:'.format(self.lab)
78
79 class Op:
80 def __init__(self, op, dst, src):
81 self.op = op
82 self.src = src
83 self.dst = dst
84 def __repr__(self):
85 return '{0} {1}, {2}'.format(self.op, self.dst, self.src)
86
87 class Jmp:
88 def __init__(self, j, target):
89 self.j = j
90 self.target = target
91 def __repr__(self):
92 return '{0} {1}'.format(self.j, self.target)
93
94 class X86CodeGen:
95 def __init__(self, diag): 6 def __init__(self, diag):
96 self.diag = diag 7 self.diag = diag
97 self.regs = ['rax', 'rbx', 'rcx', 'rdx']
98 8
99 def emit(self, i): 9 def emit(self, i):
100 self.asm.append(i) 10 self.asm.append(i)
101 11
102 def genBin(self, ir): 12 def genBin(self, ir):
103 self.asm = [] 13 self.asm = []
104 # Allocate registers:
105 insSelect(ir)
106 ra = registerallocator.RegisterAllocator()
107 # TODO: do not register allocate on intermediate code:
108 ra.registerAllocate(ir, self.regs)
109 self.genModule(ir) 14 self.genModule(ir)
110 return self.asm 15 return self.asm
111 16
112 def genModule(self, ir): 17 def genModule(self, ir):
113 for f in ir.Functions: 18 for f in ir.Functions:
114 self.genFunction(f) 19 self.genFunction(f)
115 def genFunction(self, f): 20 def genFunction(self, f):
116 self.emit('global {0}'.format(f.name)) 21 self.emit('global {0}'.format(f.name))
117 self.emit(AsmLabel(f.name)) 22 self.emit('{0}:'.format(f.name))
118 self.emit(Jmp('jmp', f.entry.name)) 23 self.emit('jmp {0}'.format(f.entry.name))
119 for bb in f.BasicBlocks: 24 for bb in f.BasicBlocks:
120 self.genBB(bb) 25 self.genBB(bb)
121 def genBB(self, bb): 26 def genBB(self, bb):
122 self.emit(AsmLabel(bb.name)) 27 self.emit('{0}:'.format(bb.name))
123 for i in bb.Instructions: 28 for i in bb.Instructions:
124 self.genIns(i) 29 self.genIns(i)
125 def genIns(self, i): 30 def genIns(self, i):
126 if type(i) is ir.BinaryOperator: 31 if type(i) is ir.BinaryOperator:
127 ops = {'+':'add', '-':'sub', '*':'mul'} 32 ops = {'+':'add', '-':'sub', '*':'mul'}
128 if i.operation in ops: 33 if i.operation in ops:
129 self.emit(Op('mov', i.result.reg, i.value1.reg)) 34 i.result.reg = 'rax'
130 self.emit(Op(ops[i.operation], i.result.reg, i.value2.reg)) 35 i.value1.reg = 'rbx'
36 i.value2.reg = 'rbx'
37 self.emit('mov {0}, {1}'.format(i.result.reg, i.value1.reg))
38 self.emit('{0} {1}, {2}'.format(ops[i.operation], i.result.reg, i.value2.reg))
131 else: 39 else:
132 raise NotImplementedError('op {0}'.format(i.operation)) 40 raise NotImplementedError('op {0}'.format(i.operation))
133 elif type(i) is ir.Load: 41 elif type(i) is ir.Load:
134 self.emit(Op('mov', i.value, '[{0}]'.format(i.location))) 42 self.emit('mov {0}, [{1}]'.format(i.value, i.location))
135 elif type(i) is ir.Return: 43 elif type(i) is ir.Return:
136 self.emit('ret') 44 self.emit('ret')
137 elif type(i) is ir.Call: 45 elif type(i) is ir.Call:
138 self.emit('call') 46 self.emit('call')
139 elif type(i) is ir.ImmLoad: 47 elif type(i) is ir.ImmLoad:
140 self.emit(Op('mov', i.target, i.value)) 48 self.emit('mov {0}, {1}'.format(i.target, i.value))
141 elif type(i) is ir.Store: 49 elif type(i) is ir.Store:
142 self.emit(Op('mov', '[{0}]'.format(i.location), i.value)) 50 self.emit('mov [{0}], {1}'.format(i.location, i.value))
143 elif type(i) is ir.ConditionalBranch: 51 elif type(i) is ir.ConditionalBranch:
144 self.emit(Op('cmp', i.a, i.b)) 52 self.emit('cmp {0}, {1}'.format(i.a, i.b))
145 jmps = {'>':'jg', '<':'jl', '==':'je'} 53 jmps = {'>':'jg', '<':'jl', '==':'je'}
146 if i.cond in jmps: 54 if i.cond in jmps:
147 j = jmps[i.cond] 55 j = jmps[i.cond]
148 self.emit(Jmp(j, i.lab1.name)) 56 self.emit('{0} {1}'.format(j, i.lab1.name))
149 else: 57 else:
150 raise NotImplementedError('condition {0}'.format(i.cond)) 58 raise NotImplementedError('condition {0}'.format(i.cond))
151 self.emit(Jmp('jmp', i.lab2.name)) 59 self.emit('jmp {0}'.format(i.lab2.name))
152 elif type(i) is ir.Branch: 60 elif type(i) is ir.Branch:
153 self.emit(Jmp('jmp', i.target.name)) 61 self.emit('jmp {0}'.format(i.target.name))
154 elif type(i) is ir.Alloc: 62 elif type(i) is ir.Alloc:
155 pass 63 pass
156 else: 64 else:
157 raise NotImplementedError('{0}'.format(i)) 65 raise NotImplementedError('{0}'.format(i))
158 66