annotate python/dag.py @ 196:ec2b423cdbea

Merge asm and asmlib files
author Windel Bouwman
date Sat, 01 Jun 2013 11:55:49 +0200
parents 6b2bec5653f1
children bd26dc13f270
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)
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
18 def buildFromBB(self, bb):
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
19 for ins in bb.Instructions:
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
20 if type(ins) is ir.BinaryOperator:
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
21 if not ins.value1 in self.mapping:
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
22 self.mapping[ins.value1] = DagNode(ins.value1)
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
23 if not ins.value2 in self.mapping:
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
24 self.mapping[ins.value2] = DagNode(ins.value2)
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
25 # look for op with left and right operand the same:
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
26 N = None
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
27 lnode = self.mapping[ins.value1]
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
28 rnode = self.mapping[ins.value2]
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
29 for node in self.mapping.values():
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
30 if node.name == ins.operation:
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
31 if node.children[0] == lnode and node.children[1] == rnode:
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
32 N = node
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
33 break
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
34 if not N:
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
35 # Create a node.
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
36 N = DagNode(ins.operation)
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
37 N.children.append(lnode)
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
38 N.children.append(rnode)
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
39 self.mapping[ins.result] = N
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
40 else:
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
41 pass
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
42 def dumpgv(self, outf):
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
43 outf.write('subgraph {0} {{\n'.format(id(self)))
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
44 for node in self.mapping.values():
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
45 outf.write('{0} [label="{1}"];\n'.format(id(node), node.name))
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
46 for c in node.children:
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
47 outf.write('{0} -> {1};\n'.format(id(node), id(c)))
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
48 outf.write('label="dag"}\n')
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
49
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
50 def insSelect(mod):
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
51 """ Create DAG from ir-code """
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
52 for bb in mod.BasicBlocks:
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
53 print(bb)
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
54 dag = Dag(bb)
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
55 print(dag.mapping)
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
56 bb.dag = dag
6b2bec5653f1 Added assembler testset
Windel Bouwman
parents:
diff changeset
57