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
|
from rpython.jit.codewriter.flatten import Register, ListOfKind, Label, TLabel
from rpython.jit.codewriter.jitcode import SwitchDictDescr
# Some instructions require liveness information (the ones that can end up
# in generate_guard() in pyjitpl.py). This is done by putting special
# space operations called '-live-' in the graph. They turn into '-live-'
# operation in the ssarepr. Then the present module expands the arguments
# of the '-live-' operations to also include all values that are alive at
# this point (written to before, and read afterwards). You can also force
# extra variables to be alive by putting them as args of the '-live-'
# operation in the first place.
# For this to work properly, a special operation called '---' must be
# used to mark unreachable places (e.g. just after a 'goto').
# ____________________________________________________________
def compute_liveness(ssarepr):
label2alive = {}
while _compute_liveness_must_continue(ssarepr, label2alive):
pass
def _compute_liveness_must_continue(ssarepr, label2alive):
alive = set()
must_continue = False
def follow_label(lbl):
alive_at_point = label2alive.get(lbl.name, ())
alive.update(alive_at_point)
for i in range(len(ssarepr.insns)-1, -1, -1):
insn = ssarepr.insns[i]
if isinstance(insn[0], Label):
alive_at_point = label2alive.setdefault(insn[0].name, set())
prevlength = len(alive_at_point)
alive_at_point.update(alive)
if prevlength != len(alive_at_point):
must_continue = True
continue
if insn[0] == '-live-':
labels = []
for x in insn[1:]:
if isinstance(x, Register):
alive.add(x)
elif isinstance(x, TLabel):
follow_label(x)
labels.append(x)
ssarepr.insns[i] = insn[:1] + tuple(alive) + tuple(labels)
continue
if insn[0] == '---':
alive = set()
continue
args = insn[1:]
#
if len(args) >= 2 and args[-2] == '->':
reg = args[-1]
assert isinstance(reg, Register)
alive.discard(reg)
args = args[:-2]
#
for x in args:
if isinstance(x, Register):
alive.add(x)
elif isinstance(x, ListOfKind):
for y in x:
if isinstance(y, Register):
alive.add(y)
elif isinstance(x, TLabel):
follow_label(x)
elif isinstance(x, SwitchDictDescr):
for key, label in x._labels:
follow_label(label)
return must_continue
|
