|
191
|
1
|
|
|
2 # Instruction selection with DAG (Directed Acyclic Graph)
|
|
|
3 class DagLeaf:
|
|
|
4 def __init__(self, v):
|
|
|
5 self.v = v
|
|
|
6
|
|
|
7 class DagNode:
|
|
|
8 def __init__(self, name):
|
|
|
9 self.name = name
|
|
|
10 self.children = []
|
|
|
11 def __repr__(self):
|
|
|
12 return str(self.name)
|
|
|
13
|
|
|
14 class Dag:
|
|
|
15 def __init__(self, bb):
|
|
|
16 self.mapping = {}
|
|
|
17 self.buildFromBB(bb)
|
|
254
|
18
|
|
191
|
19 def buildFromBB(self, bb):
|
|
|
20 for ins in bb.Instructions:
|
|
|
21 if type(ins) is ir.BinaryOperator:
|
|
|
22 if not ins.value1 in self.mapping:
|
|
|
23 self.mapping[ins.value1] = DagNode(ins.value1)
|
|
|
24 if not ins.value2 in self.mapping:
|
|
|
25 self.mapping[ins.value2] = DagNode(ins.value2)
|
|
|
26 # look for op with left and right operand the same:
|
|
|
27 N = None
|
|
|
28 lnode = self.mapping[ins.value1]
|
|
|
29 rnode = self.mapping[ins.value2]
|
|
|
30 for node in self.mapping.values():
|
|
|
31 if node.name == ins.operation:
|
|
|
32 if node.children[0] == lnode and node.children[1] == rnode:
|
|
|
33 N = node
|
|
|
34 break
|
|
|
35 if not N:
|
|
|
36 # Create a node.
|
|
|
37 N = DagNode(ins.operation)
|
|
|
38 N.children.append(lnode)
|
|
|
39 N.children.append(rnode)
|
|
|
40 self.mapping[ins.result] = N
|
|
|
41 else:
|
|
|
42 pass
|
|
254
|
43
|
|
191
|
44 def dumpgv(self, outf):
|
|
|
45 outf.write('subgraph {0} {{\n'.format(id(self)))
|
|
|
46 for node in self.mapping.values():
|
|
|
47 outf.write('{0} [label="{1}"];\n'.format(id(node), node.name))
|
|
|
48 for c in node.children:
|
|
|
49 outf.write('{0} -> {1};\n'.format(id(node), id(c)))
|
|
|
50 outf.write('label="dag"}\n')
|
|
|
51
|
|
|
52 def insSelect(mod):
|
|
|
53 """ Create DAG from ir-code """
|
|
|
54 for bb in mod.BasicBlocks:
|
|
|
55 print(bb)
|
|
|
56 dag = Dag(bb)
|
|
|
57 print(dag.mapping)
|
|
|
58 bb.dag = dag
|
|
|
59
|
