Mercurial > lcfOS

annotate test/testgraph.py @ 409:8fe299cd2d55 devel

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Close devel branch
author Windel Bouwman
date Sat, 21 Feb 2015 12:20:10 +0100
parents 86b02c98a717
children
rev   line source
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
1 #!/usr/bin/python
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
2
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
3 import unittest
323
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 301
diff changeset
4 from ppci.codegen.graph import Graph, Node, DiGraph, DiNode
301
6753763d3bec merge codegen into ppci package
Windel Bouwman
parents: 296
diff changeset
5 from ppci.codegen.interferencegraph import InterferenceGraph
6753763d3bec merge codegen into ppci package
Windel Bouwman
parents: 296
diff changeset
6 from ppci.codegen.flowgraph import FlowGraph
6753763d3bec merge codegen into ppci package
Windel Bouwman
parents: 296
diff changeset
7 from ppci import ir
6753763d3bec merge codegen into ppci package
Windel Bouwman
parents: 296
diff changeset
8 from ppci.irmach import AbstractInstruction as AI
342
86b02c98a717 Moved target directory
Windel Bouwman
parents: 337
diff changeset
9 from ppci.target import Nop
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
10
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
11
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
12 class GraphTestCase(unittest.TestCase):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
13 def testEdge(self):
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 290
diff changeset
14 g = Graph()
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 290
diff changeset
15 n1 = Node(g)
337
b00219172a42 Added cool lm3s811 qemu project
Windel Bouwman
parents: 323
diff changeset
16 g.add_node(n1)
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 290
diff changeset
17 n2 = Node(g)
337
b00219172a42 Added cool lm3s811 qemu project
Windel Bouwman
parents: 323
diff changeset
18 g.add_node(n2)
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
19 g.addEdge(n1, n2)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
20 self.assertTrue(g.hasEdge(n2, n1))
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
21 self.assertTrue(g.hasEdge(n1, n2))
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
22 g.delNode(n1)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
23 g.delNode(n2)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
24
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
25 def testDegree(self):
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 290
diff changeset
26 g = Graph()
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 290
diff changeset
27 n1 = Node(g)
337
b00219172a42 Added cool lm3s811 qemu project
Windel Bouwman
parents: 323
diff changeset
28 g.add_node(n1)
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 290
diff changeset
29 n2 = Node(g)
337
b00219172a42 Added cool lm3s811 qemu project
Windel Bouwman
parents: 323
diff changeset
30 g.add_node(n2)
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 290
diff changeset
31 n3 = Node(g)
337
b00219172a42 Added cool lm3s811 qemu project
Windel Bouwman
parents: 323
diff changeset
32 g.add_node(n3)
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
33 g.addEdge(n1, n2)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
34 g.addEdge(n1, n3)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
35 self.assertEqual(2, n1.Degree)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
36 self.assertEqual(1, n2.Degree)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
37 g.delNode(n2)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
38 self.assertEqual(1, n1.Degree)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
39
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
40
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
41 class DigraphTestCase(unittest.TestCase):
323
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 301
diff changeset
42 def testSuccessor(self):
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 301
diff changeset
43 g = DiGraph()
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 301
diff changeset
44 a = DiNode(g)
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 301
diff changeset
45 b = DiNode(g)
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 301
diff changeset
46 c = DiNode(g)
337
b00219172a42 Added cool lm3s811 qemu project
Windel Bouwman
parents: 323
diff changeset
47 g.add_node(a)
b00219172a42 Added cool lm3s811 qemu project
Windel Bouwman
parents: 323
diff changeset
48 g.add_node(b)
b00219172a42 Added cool lm3s811 qemu project
Windel Bouwman
parents: 323
diff changeset
49 g.add_node(c)
323
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 301
diff changeset
50 g.addEdge(a, b)
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 301
diff changeset
51 g.addEdge(b, c)
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 301
diff changeset
52 self.assertEqual({b}, a.Succ)
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 301
diff changeset
53 self.assertEqual({b}, c.Pred)
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 301
diff changeset
54 g.delNode(c)
e9fe6988497c Used burg for generating expressions
Windel Bouwman
parents: 301
diff changeset
55 self.assertEqual(set(), b.Succ)
290
7b38782ed496 File moves
Windel Bouwman
parents: 284
diff changeset
56
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
57
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
58 class InterferenceGraphTestCase(unittest.TestCase):
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
59 def testNormalUse(self):
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
60 t1 = ir.Temp('t1')
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
61 t2 = ir.Temp('t2')
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
62 t3 = ir.Temp('t3')
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
63 t4 = ir.Temp('t4')
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
64 t5 = ir.Temp('t5')
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
65 t6 = ir.Temp('t6')
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
66 instrs = []
280
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
67 instrs.append(AI(Nop, dst=[t1]))
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
68 instrs.append(AI(Nop, dst=[t2]))
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
69 instrs.append(AI(Nop, dst=[t3]))
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 290
diff changeset
70 cfg = FlowGraph(instrs)
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 290
diff changeset
71 ig = InterferenceGraph(cfg)
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
72
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
73 def testCombine(self):
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
74 t1 = ir.Temp('t1')
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
75 t2 = ir.Temp('t2')
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
76 t3 = ir.Temp('t3')
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
77 t4 = ir.Temp('t4')
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
78 instrs = []
280
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
79 instrs.append(AI(Nop, dst=[t1]))
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
80 instrs.append(AI(Nop, dst=[t2]))
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
81 instrs.append(AI(Nop, dst=[t3]))
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
82 instrs.append(AI(Nop, dst=[t4], src=[t3]))
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
83 instrs.append(AI(Nop, src=[t4]))
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
84 instrs.append(AI(Nop, src=[t1]))
02385f62f250 Rework from str interface to Instruction interface
Windel Bouwman
parents: 279
diff changeset
85 instrs.append(AI(Nop, src=[t2]))
296
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 290
diff changeset
86 cfg = FlowGraph(instrs)
9417caea2eb3 Directorized some backend files
Windel Bouwman
parents: 290
diff changeset
87 ig = InterferenceGraph(cfg)
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
88 ig.Combine(ig.getNode(t4), ig.getNode(t3))
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
89 self.assertIs(ig.getNode(t4), ig.getNode(t3))
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
90
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
91
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
92 if __name__ == '__main__':
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
93 unittest.main()