-
Notifications
You must be signed in to change notification settings - Fork 23
/
xform_ssa.py
258 lines (207 loc) · 9.08 KB
/
xform_ssa.py
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
# ScratchABlock - Program analysis and decompilation framework
#
# Copyright (c) 2015-2018 Paul Sokolovsky
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
"""SSA related transformations"""
from collections import defaultdict
from core import *
from cfgutils import foreach_inst
import xform_expr
import xform_cfg
def is_phi(inst):
return inst.op == "=" and is_sfunc(inst.args[0], "phi")
def insert_phi_maximal(cfg, fully_maximal=False):
"""Insert phi functions to produce maximal SSA form.
Described e.g. in Appel 1998 "SSA is Functional Programming" (not named
"maximal" there, but the name is quite obvious, especially if contrasted
with well-known "minimal SSA form"):
"A really crude approach is to split every variable at every basic-block
boundary, and put φ-functions for every variable in every block"
The algorithm below already contains an obvious optimization - phi
functions are inserted only to blocks with multiple predecessors. Note
that this requires rename function to process basic block from successors
to predecessors, to correctly propagate renamings thru such phi-less
blocks. (If on the other hand we inserted phi's to each block, we could
process their renaming in arbitrary order, because each basic block would
have its local definition for every variable).
"""
if fully_maximal:
min_preds = 1
else:
min_preds = 2
all_vars = sorted(xform_cfg.local_defines(cfg))
for n, nprops in cfg.nodes_props():
if cfg.degree_in(n) >= min_preds:
bb = nprops["val"]
preds = cfg.pred(n)
phi_no = 0
for v in all_vars:
inst = Inst(v, "=", [EXPR("SFUNC", [SFUNC("phi")] + [v] * len(preds))], addr=bb.addr + ".phi_%s" % v.name)
bb.items.insert(phi_no, inst)
phi_no += 1
def insert_phi_fully_maximal(cfg):
insert_phi_maximal(cfg, fully_maximal=True)
def rename_ssa_vars(cfg, use_addrs=False):
"""Generic routine to rename registers to follow SSA form.
This should be called after phi-insertion pass, and this routine will
work with insertion algorithm (whether constructing maximal, minimal,
pruned or whatever form). Can rename registers to use either sequential
subscripts or instruction addresses where register is defined.
"""
def rename_reg(e):
if is_reg(e):
return REG("%s_%s" % (e.name, var_map[e.name]))
if use_addrs:
var_map = defaultdict(lambda: "0")
else:
var_map = defaultdict(int)
# Process basic blocks in such a way that we have renamings (if any!) for
# current block, before we proceed to its successors.
for n in cfg.iter_rev_postorder():
bb = cfg[n]["val"]
# Rename variables within basic block.
for inst in bb:
# Don't rename args of phi funcs, those names come from
# predecessor blocks.
if not is_phi(inst):
for i, arg in enumerate(inst.args):
inst.args[i] = xform_expr.expr_xform(arg, rename_reg)
# Rename destination
if is_reg(inst.dest):
# If it's a register, this defines a new register version
if use_addrs:
if is_phi(inst):
suffix = bb.addr + "_phi"
else:
suffix = inst.addr
var_map[inst.dest.name] = suffix
else:
var_map[inst.dest.name] += 1
inst.dest = rename_reg(inst.dest)
else:
# Otherwise, it's more complex expression which may contain
# reference to reg as a subexpression
inst.dest = xform_expr.expr_xform(inst.dest, rename_reg)
# Now rename arguments of phi functions in successor blocks, in the
# position which correspond to the current block's predecessor edge
for next_n in cfg.succ(n):
my_pos = cfg.pred(next_n).index(n)
next_bb = cfg[next_n]["val"]
for inst in next_bb:
if not is_phi(inst):
break
# +1 because first arg is SFUNC("phi")
new_reg = rename_reg(inst.args[0].args[my_pos + 1])
inst.args[0].args[my_pos + 1] = new_reg
def rename_ssa_vars_fully_maximal(cfg, use_addrs=False):
def rename_reg(e):
if is_reg(e):
return REG("%s_%s" % (e.name, var_map[e.name]))
if use_addrs:
var_map = defaultdict(lambda: "0")
else:
var_map = defaultdict(int)
# This algorithm could process basic blocks in any order. But for human
# consumption, it's better when variable are numbered from the start of
# a function.
for n in cfg.iter_rev_postorder():
bb = cfg[n]["val"]
# Rename variables within basic block.
for inst in bb:
# Don't rename args of phi funcs, those names come from
# predecessor blocks.
if not is_phi(inst):
for i, arg in enumerate(inst.args):
inst.args[i] = xform_expr.expr_xform(arg, rename_reg)
# Rename destination
if is_reg(inst.dest):
# If it's a register, this defines a new register version
if use_addrs:
if is_phi(inst):
suffix = bb.addr + "_phi"
else:
suffix = inst.addr
var_map[inst.dest.name] = suffix
else:
var_map[inst.dest.name] += 1
inst.dest = rename_reg(inst.dest)
else:
# Otherwise, it's more complex expression which may contain
# reference to reg as a subexpression
inst.dest = xform_expr.expr_xform(inst.dest, rename_reg)
# Now rename arguments of phi functions in successor blocks, in the
# position which correspond to the current block's predecessor edge
for next_n in cfg.succ(n):
my_pos = cfg.pred(next_n).index(n)
next_bb = cfg[next_n]["val"]
for inst in next_bb:
if not is_phi(inst):
break
# +1 because first arg is SFUNC("phi")
new_reg = rename_reg(inst.args[0].args[my_pos + 1])
inst.args[0].args[my_pos + 1] = new_reg
def rename_ssa_vars_subscripts(cfg):
rename_ssa_vars(cfg, False)
def rename_ssa_vars_addrs(cfg):
rename_ssa_vars(cfg, True)
def verify_ssa(cfg):
"Verify that structural properties of SSA hold."
# Step 1: Verify that each var is assigned only once.
all_defs = set()
def check_single_assign(inst):
for d in inst.defs():
assert d not in all_defs
all_defs.add(d)
foreach_inst(cfg, check_single_assign)
# Step 2: Verify that each use is dominated by definition.
def check_doms(inst_addr, node, reg):
# All "_0" regs are assumed to be implicitly defined on entry
# (e.g. func params).
if reg.name.endswith("_0"):
return
dom_list = []
while True:
# We start with testing current passed node to handle the
# case of this func being called for phi statement, where
# its predecessor node is passed here. For normal statement,
# this will check its own node in vain, but that's fine.
defs = cfg[node]["val"].defs()
if reg in defs:
return
dom_list.append(node)
node = cfg[node]["idom"]
if not node:
assert False, "@%s: Use of %s is not dominated by definition, " \
"expected to be in one of bblocks: %s, instead in: %s" % (
inst_addr, reg, dom_list, xform_cfg.find_1st_def(cfg, reg, in_bblock=True)
)
for n, info in cfg.nodes_props():
bb = info["val"]
inst_map = {}
for i, inst in enumerate(bb.items):
for d in inst.defs():
inst_map[d] = i
for i in range(len(bb.items) - 1, -1, -1):
inst = bb.items[i]
if is_phi(inst):
preds = cfg.pred(n)
for i, u in enumerate(inst.args[0].args[1:]):
check_doms(inst.addr, preds[i], u)
continue
for u in inst.uses():
if u in inst_map:
assert inst_map[u] < i
else:
check_doms(inst.addr, n, u)