SSA化算法过程
SSA化算法过程
gcc中SSA化的算法描述
SSA化的流程可以简化为:
(1)对所有变量插入必要的phi函数
(2)依次重写各个变量的定值/使用(转化为SSA格式)
而具体到gcc中则大体分为4个步骤:
计算当前函数的支配结点边界
按照迭代的必经结点边界算法, 要想确定phi函数插入的位置,必须要先根据函数的CFG确定函数的支配结点边界(支配结点边界的定义和算法见[2]), 在gcc中则是
1) 先通过calculate_dominance_info计算当前函数的支配结点信息
2) 再通过compute_dominance_frontiers计算当前函数的支配结点边界信息
遍历并记录函数每条指令中出现的变量的defs/uses信息
此步主要是收集函数每条指令中出现的变量的defs/uses信息,这些信息保存在标量的bitmap中, 故可以按照任意的顺序遍历指令,而在gcc中则是采用基于支配树的深度优先遍历(DFS)顺序遍历各个基本块(bb)中的一条条指令
为每个变量计算phi函数的插入点
1)中已经计算出了每个bb的支配结点边界信息；2)中计算出了每个变量的defs/uses信息, 按照迭代的必经结点边界算法, 此变量每一个def出现的结点的必经结点边界结点均需要插入一个phi函数, 插入后的phi函数作为此变量的一个新定值(def)点参与迭代计算.
1
| 针对当前函数中的每个变量均需要通过此算法计算出其需要插入phi函数的结点信息,并在对应结点为每个变量分别插入phi函数
|
按照支配树的DFS遍历重写每个bb的每条指令并将整个函数SSA化
这里和步骤2)不同, SSA化的过程必须按照支配树的深度优先算法遍历结点,
1
2
3
4
5
6
7
8
9
| (1)对于每个结点顺序需遍历所有语句,对于每条语句:
A.若发现一个操作数中涉及变量使用(use)时,需要将此操作数改为对此变量在DFS上最新定义(SSA_NAME)的使用
B.若发现一个操作数中涉及变量定值(def)时,需要为此变量新创建一个SSA_NAME作为此变量的最新定义, 并将此此操作数改为新创建的SSA_NAME
(2) 语句处理完毕后续为此结点的每个后继结点的所有phi函数确定一个参数(phi函数的第x个参数来自其第x个前驱结点)
phi函数对应原始变量在4.4)-1)-2)中的最新定值(def)则为phi函数的第x个参数,代表运行时来若控制流来自第x个前驱,则当前参数x的定值应来自哪个SSA_NAME
|
gcc中ssa化的整体流程
pass_build_ssa
在gcc中 pass_build_ssa 负责对一个函数进行首次ssa转化,而 update_ssa则负责对转化后的ssa的更新, pass_build_ssa大体流程如下:
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
|
unsigned int pass_build_ssa::execute (function *fun)
{
bitmap_head *dfs;
basic_block bb;
init_ssa_operands (fun);
init_ssa_renamer ();
interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (fun));
bitmap_clear (interesting_blocks);
dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (fun));
FOR_EACH_BB_FN (bb, fun)
bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
calculate_dominance_info (CDI_DOMINATORS);
compute_dominance_frontiers (dfs);
mark_def_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
insert_phi_nodes (dfs);
rewrite_blocks (ENTRY_BLOCK_PTR_FOR_FN (fun), REWRITE_ALL);
......
return 0;
}
|
函数指令序列的def/use分析
要分析当前函数中所有变量的def/use信息,这是通过函数mark_def_dom_walker::walk()实现的:
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
| class mark_def_dom_walker : public dom_walker
{
public:
mark_def_dom_walker (cdi_direction direction);
~mark_def_dom_walker ();
virtual edge before_dom_children (basic_block);
private:
bitmap m_kills;
};
class dom_walker
{
......
void walk (basic_block);
......
}
void dom_walker::walk (basic_block bb)
{
int sp = 0;
basic_block dest;
basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) * 2);
......
while (true)
{
if (EDGE_COUNT (bb->preds) > 0 || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
{
edge taken_edge = NULL;
taken_edge = before_dom_children (bb);
worklist[sp++] = bb;
worklist[sp++] = NULL;
if (taken_edge != STOP)
{
int saved_sp = sp;
for (dest = first_dom_son (m_dom_direction, bb); dest; dest = next_dom_son (m_dom_direction, dest))
worklist[sp++] = dest;
if (sp - saved_sp > 1 && m_dom_direction == CDI_DOMINATORS && m_bb_to_rpo)
sort_bbs_postorder (&worklist[saved_sp], sp - saved_sp);
}
}
while (sp > 0 && !worklist[sp - 1])
{
--sp;
bb = worklist[--sp];
......
after_dom_children (bb);
}
if (sp)
bb = worklist[--sp];
else
break;
}
free (worklist);
}
|
由上可知, mark_def_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr); 实际上是通过其父类的walk函数从当前函数的入口bb开始根据DFS算法遍历了此函数的支配树,并对每个bb调用了回调函数mark_def_dom_walker::before_dom_children,此函数定义如下:
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
| edge mark_def_dom_walker::before_dom_children (basic_block bb)
{
gimple_stmt_iterator gsi;
bitmap_clear (m_kills);
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
mark_def_sites (bb, gsi_stmt (gsi), m_kills);
return NULL;
}
static void mark_def_sites (basic_block bb, gimple *stmt, bitmap kills)
{
tree def;
use_operand_p use_p;
ssa_op_iter iter;
update_stmt (stmt);
......
set_register_defs (stmt, false);
set_rewrite_uses (stmt, false);
......
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
{
tree sym = USE_FROM_PTR (use_p);
......
if (!bitmap_bit_p (kills, DECL_UID (sym)))
set_livein_block (sym, bb);
set_rewrite_uses (stmt, true);
}
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
{
......
set_def_block (def, bb, false);
bitmap_set_bit (kills, DECL_UID (def));
set_register_defs (stmt, true);
}
if (rewrite_uses_p (stmt) || register_defs_p (stmt))
bitmap_set_bit (interesting_blocks, bb->index);
}
|
为每个变量插入phi函数
分析完def/use信息后,则需要为当前函数的每个变量在需要的位置(bb)处插入phi函数,此过程是在函数 insert_phi_nodes中实现的：
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
|
static void insert_phi_nodes (bitmap_head *dfs)
{
var_info *info;
......
auto_vec<var_info *> vars (var_infos->elements ());
FOR_EACH_HASH_TABLE_ELEMENT (*var_infos, info, var_info_p, hi)
if (info->info.need_phi_state != NEED_PHI_STATE_NO)
vars.quick_push (info);
vars.qsort (insert_phi_nodes_compare_var_infos);
FOR_EACH_VEC_ELT (vars, i, info)
{
bitmap idf = compute_idf (info->info.def_blocks.def_blocks, dfs);
insert_phi_nodes_for (info->var, idf, false);
BITMAP_FREE (idf);
}
}
bitmap compute_idf (bitmap def_blocks, bitmap_head *dfs)
{
bitmap_iterator bi;
unsigned bb_index, i;
bitmap phi_insertion_points;
auto_vec<int> work_stack (2 * n_basic_blocks_for_fn (cfun));
phi_insertion_points = BITMAP_ALLOC (NULL);
EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi)
work_stack.quick_push (bb_index);
while (work_stack.length () > 0)
{
bb_index = work_stack.pop ();
EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs[bb_index], phi_insertion_points, 0, i, bi)
{
work_stack.quick_push (i);
bitmap_set_bit (phi_insertion_points, i);
}
}
return phi_insertion_points;
}
static void insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
{
unsigned bb_index;
edge e;
gphi *phi;
basic_block bb;
bitmap_iterator bi;
def_blocks *def_map = find_def_blocks_for (var);
......
prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks, def_map->livein_blocks);
EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
{
bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
if (update_p)
mark_block_for_update (bb);
if (TREE_CODE (var) == SSA_NAME) {
......
} else {
phi = create_phi_node (var, bb);
......
}
set_register_defs (phi, true);
mark_phi_for_rewrite (bb, phi);
}
}
|
指令重写(SSA化)
phi函数插入完毕后,需要对整个函数所有bb中的所有指令序列中所有的def/use变量进行重写,此过程是在函数rewrite_blocks 中完成的：
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
| static void rewrite_blocks (basic_block entry, enum rewrite_mode what)
{
......
if (what == REWRITE_ALL)
rewrite_dom_walker (CDI_DOMINATORS).walk (entry);
else if (what == REWRITE_UPDATE)
rewrite_update_dom_walker (CDI_DOMINATORS).walk (entry);
else
gcc_unreachable ();
......
}
struct def_blocks
{
bitmap def_blocks;
bitmap phi_blocks;
bitmap livein_blocks;
};
struct common_info
{
ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
tree current_def;
struct def_blocks def_blocks;
};
struct var_info
{
tree var;
common_info info;
};
edge rewrite_dom_walker::before_dom_children (basic_block bb)
{
......
block_defs_stack.safe_push (NULL_TREE);
for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
tree result = gimple_phi_result (gsi_stmt (gsi));
register_new_def (result, SSA_NAME_VAR (result));
}
if (bitmap_bit_p (interesting_blocks, bb->index))
for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
rewrite_stmt (&gsi);
rewrite_add_phi_arguments (bb);
return NULL;
}
static void rewrite_stmt (gimple_stmt_iterator *si)
{
gimple *stmt = gsi_stmt (*si);
if (!rewrite_uses_p (stmt) && !register_defs_p (stmt)) return;
if (rewrite_uses_p (stmt))
{
......
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
{
tree var = USE_FROM_PTR (use_p);
......
SET_USE (use_p, get_reaching_def (var));
}
}
if (register_defs_p (stmt))
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
{
tree var = DEF_FROM_PTR (def_p);
tree name;
......
if (TREE_CODE (var) == SSA_NAME) continue;
gcc_checking_assert (DECL_P (var));
......
name = make_ssa_name (var, stmt);
SET_DEF (def_p, name);
register_new_def (DEF_FROM_PTR (def_p), var);
......
}
}
void rewrite_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
{
while (block_defs_stack.length () > 0)
{
tree tmp = block_defs_stack.pop ();
tree saved_def, var;
if (tmp == NULL_TREE) break;
if (TREE_CODE (tmp) == SSA_NAME) {
saved_def = tmp;
var = SSA_NAME_VAR (saved_def);
......
} else {
saved_def = NULL;
var = tmp;
}
get_common_info (var)->current_def = saved_def;
}
}
static void rewrite_add_phi_arguments (basic_block bb)
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
{
gphi *phi;
gphi_iterator gsi;
for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
{
phi = gsi.phi ();
res = gimple_phi_result (phi);
currdef = get_reaching_def (SSA_NAME_VAR (res));
......
add_phi_arg (phi, currdef, e, loc);
}
}
}
|
SSA基本概念及原理参考文章
原文链接
