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
|
import random
from rpython.tool.algo.unionfind import UnionFind
from rpython.translator.backendopt.graphanalyze import (Dependency,
DependencyTracker, BoolGraphAnalyzer)
class FakeGraphAnalyzer:
def __init__(self):
self._analyzed_calls = UnionFind(lambda graph: Dependency(self))
@staticmethod
def bottom_result():
return 0
@staticmethod
def join_two_results(result1, result2):
return result1 | result2
def test_random_graphs():
for _ in range(100):
N = 10
edges = [(random.randrange(N), random.randrange(N))
for i in range(N*N//3)]
def expected(node1):
prev = set()
seen = set([node1])
while len(seen) > len(prev):
prev = set(seen)
for a, b in edges:
if a in seen:
seen.add(b)
return sum([1 << n for n in seen])
def rectrack(n, tracker):
if not tracker.enter(n):
return tracker.get_cached_result(n)
result = 1 << n
for a, b in edges:
if a == n:
result |= rectrack(b, tracker)
tracker.leave_with(result)
return result
analyzer = FakeGraphAnalyzer()
for n in range(N):
tracker = DependencyTracker(analyzer)
method1 = rectrack(n, tracker)
method2 = expected(n)
assert method1 == method2
def test_delayed_fnptr():
from rpython.flowspace.model import SpaceOperation
from rpython.rtyper.annlowlevel import MixLevelHelperAnnotator
from rpython.translator.translator import TranslationContext
t = TranslationContext()
t.buildannotator()
t.buildrtyper()
annhelper = MixLevelHelperAnnotator(t.rtyper)
def f():
pass
c_f = annhelper.constfunc(f, [], None)
op = SpaceOperation('direct_call', [c_f], None)
analyzer = BoolGraphAnalyzer(t)
assert analyzer.analyze(op)
def test_null_fnptr():
from rpython.flowspace.model import SpaceOperation, Constant
from rpython.rtyper.lltypesystem.lltype import Void, FuncType, nullptr
from rpython.translator.translator import TranslationContext
t = TranslationContext()
fnptr = nullptr(FuncType([], Void))
op = SpaceOperation('direct_call', [Constant(fnptr)], None)
analyzer = BoolGraphAnalyzer(t)
assert not analyzer.analyze(op)
|
