annotate python/ppci/codegen/dag.py @ 301:6753763d3bec

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