1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
from rpython.translator.translator import TranslationContext, graphof
from rpython.translator.backendopt.support import \
find_loop_blocks, find_backedges, compute_reachability
#__________________________________________________________
# test compute_reachability
def test_simple_compute_reachability():
def f(x):
if x < 0:
if x == -1:
return x+1
else:
return x+2
else:
if x == 1:
return x-1
else:
return x-2
t = TranslationContext()
g = t.buildflowgraph(f)
reach = compute_reachability(g)
assert len(reach[g.startblock]) == 7
assert len(reach[g.startblock.exits[0].target]) == 3
assert len(reach[g.startblock.exits[1].target]) == 3
#__________________________________________________________
# test loop detection
def test_find_backedges():
def f(k):
result = 0
for i in range(k):
result += 1
for j in range(k):
result += 1
return result
t = TranslationContext()
t.buildannotator().build_types(f, [int])
t.buildrtyper().specialize()
graph = graphof(t, f)
backedges = find_backedges(graph)
assert len(backedges) == 2
def test_find_loop_blocks():
def f(k):
result = 0
for i in range(k):
result += 1
for j in range(k):
result += 1
return result
t = TranslationContext()
t.buildannotator().build_types(f, [int])
t.buildrtyper().specialize()
graph = graphof(t, f)
loop_blocks = find_loop_blocks(graph)
assert len(loop_blocks) == 4
def test_find_loop_blocks_simple():
def f(a):
if a <= 0:
return 1
return f(a - 1)
t = TranslationContext()
t.buildannotator().build_types(f, [int])
t.buildrtyper().specialize()
graph = graphof(t, f)
backedges = find_backedges(graph)
assert backedges == []
loop_blocks = find_loop_blocks(graph)
assert len(loop_blocks) == 0
def test_find_loop_blocks2():
class A:
pass
def f(n):
a1 = A()
a1.x = 1
a2 = A()
a2.x = 2
if n > 0:
a = a1
else:
a = a2
return a.x
t = TranslationContext()
t.buildannotator().build_types(f, [int])
t.buildrtyper().specialize()
graph = graphof(t, f)
backedges = find_backedges(graph)
assert backedges == []
loop_blocks = find_loop_blocks(graph)
assert len(loop_blocks) == 0
def test_find_loop_blocks3():
import os
def ps(loops):
return 42.0, 42.1
def f(loops):
benchtime, stones = ps(abs(loops))
s = '' # annotator happiness
if loops >= 0:
s = ("RPystone(%s) time for %d passes = %f" %
(23, loops, benchtime) + '\n' + (
"This machine benchmarks at %f pystones/second" % stones))
os.write(1, s)
if loops == 12345:
f(loops-1)
t = TranslationContext()
t.buildannotator().build_types(f, [int])
t.buildrtyper().specialize()
graph = graphof(t, f)
backedges = find_backedges(graph)
assert backedges == []
loop_blocks = find_loop_blocks(graph)
assert len(loop_blocks) == 0
|