|
157
|
1 import ppci
|
|
158
|
2 import ir
|
|
173
|
3 import registerallocator
|
|
158
|
4
|
|
177
|
5 # Instruction selection with DAG (Directed Acyclic Graph)
|
|
|
6 class DagLeaf:
|
|
|
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
|
|
178
|
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
|
|
177
|
72 # x86 specific:
|
|
158
|
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:
|
|
171
|
80 def __init__(self, op, dst, src):
|
|
158
|
81 self.op = op
|
|
171
|
82 self.src = src
|
|
|
83 self.dst = dst
|
|
158
|
84 def __repr__(self):
|
|
171
|
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)
|
|
157
|
93
|
|
|
94 class X86CodeGen:
|
|
|
95 def __init__(self, diag):
|
|
|
96 self.diag = diag
|
|
160
|
97 self.regs = ['rax', 'rbx', 'rcx', 'rdx']
|
|
157
|
98
|
|
158
|
99 def emit(self, i):
|
|
|
100 self.asm.append(i)
|
|
|
101
|
|
171
|
102 def genBin(self, ir):
|
|
158
|
103 self.asm = []
|
|
171
|
104 # Allocate registers:
|
|
177
|
105 insSelect(ir)
|
|
173
|
106 ra = registerallocator.RegisterAllocator()
|
|
174
|
107 # TODO: do not register allocate on intermediate code:
|
|
173
|
108 ra.registerAllocate(ir, self.regs)
|
|
171
|
109 self.genModule(ir)
|
|
|
110 return self.asm
|
|
157
|
111
|
|
171
|
112 def genModule(self, ir):
|
|
174
|
113 for f in ir.Functions:
|
|
|
114 self.genFunction(f)
|
|
158
|
115 def genFunction(self, f):
|
|
|
116 self.emit('global {0}'.format(f.name))
|
|
|
117 self.emit(AsmLabel(f.name))
|
|
174
|
118 self.emit(Jmp('jmp', f.entry.name))
|
|
158
|
119 for bb in f.BasicBlocks:
|
|
|
120 self.genBB(bb)
|
|
|
121 def genBB(self, bb):
|
|
171
|
122 self.emit(AsmLabel(bb.name))
|
|
158
|
123 for i in bb.Instructions:
|
|
|
124 self.genIns(i)
|
|
|
125 def genIns(self, i):
|
|
|
126 if type(i) is ir.BinaryOperator:
|
|
171
|
127 ops = {'+':'add', '-':'sub', '*':'mul'}
|
|
|
128 if i.operation in ops:
|
|
|
129 self.emit(Op('mov', i.result.reg, i.value1.reg))
|
|
|
130 self.emit(Op(ops[i.operation], i.result.reg, i.value2.reg))
|
|
|
131 else:
|
|
|
132 raise NotImplementedError('op {0}'.format(i.operation))
|
|
|
133 elif type(i) is ir.Load:
|
|
174
|
134 self.emit(Op('mov', i.value, '[{0}]'.format(i.location)))
|
|
171
|
135 elif type(i) is ir.Return:
|
|
158
|
136 self.emit('ret')
|
|
171
|
137 elif type(i) is ir.Call:
|
|
160
|
138 self.emit('call')
|
|
171
|
139 elif type(i) is ir.ImmLoad:
|
|
|
140 self.emit(Op('mov', i.target, i.value))
|
|
|
141 elif type(i) is ir.Store:
|
|
174
|
142 self.emit(Op('mov', '[{0}]'.format(i.location), i.value))
|
|
171
|
143 elif type(i) is ir.ConditionalBranch:
|
|
|
144 self.emit(Op('cmp', i.a, i.b))
|
|
|
145 jmps = {'>':'jg', '<':'jl', '==':'je'}
|
|
|
146 if i.cond in jmps:
|
|
|
147 j = jmps[i.cond]
|
|
|
148 self.emit(Jmp(j, i.lab1.name))
|
|
|
149 else:
|
|
|
150 raise NotImplementedError('condition {0}'.format(i.cond))
|
|
|
151 self.emit(Jmp('jmp', i.lab2.name))
|
|
|
152 elif type(i) is ir.Branch:
|
|
|
153 self.emit(Jmp('jmp', i.target.name))
|
|
174
|
154 elif type(i) is ir.Alloc:
|
|
|
155 pass
|
|
158
|
156 else:
|
|
171
|
157 raise NotImplementedError('{0}'.format(i))
|
|
158
|
158
|
