|
0
|
1 /* Backward propagation of indirect loads through PHIs.
|
|
|
2 Copyright (C) 2007, 2008 Free Software Foundation, Inc.
|
|
|
3 Contributed by Richard Guenther <rguenther@suse.de>
|
|
|
4
|
|
|
5 This file is part of GCC.
|
|
|
6
|
|
|
7 GCC is free software; you can redistribute it and/or modify
|
|
|
8 it under the terms of the GNU General Public License as published by
|
|
|
9 the Free Software Foundation; either version 3, or (at your option)
|
|
|
10 any later version.
|
|
|
11
|
|
|
12 GCC is distributed in the hope that it will be useful,
|
|
|
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
15 GNU General Public License for more details.
|
|
|
16
|
|
|
17 You should have received a copy of the GNU General Public License
|
|
|
18 along with GCC; see the file COPYING3. If not see
|
|
|
19 <http://www.gnu.org/licenses/>. */
|
|
|
20
|
|
|
21 #include "config.h"
|
|
|
22 #include "system.h"
|
|
|
23 #include "coretypes.h"
|
|
|
24 #include "tm.h"
|
|
|
25 #include "ggc.h"
|
|
|
26 #include "tree.h"
|
|
|
27 #include "rtl.h"
|
|
|
28 #include "tm_p.h"
|
|
|
29 #include "basic-block.h"
|
|
|
30 #include "timevar.h"
|
|
|
31 #include "diagnostic.h"
|
|
|
32 #include "tree-flow.h"
|
|
|
33 #include "tree-pass.h"
|
|
|
34 #include "tree-dump.h"
|
|
|
35 #include "langhooks.h"
|
|
|
36 #include "flags.h"
|
|
|
37
|
|
|
38 /* This pass propagates indirect loads through the PHI node for its
|
|
|
39 address to make the load source possibly non-addressable and to
|
|
|
40 allow for PHI optimization to trigger.
|
|
|
41
|
|
|
42 For example the pass changes
|
|
|
43
|
|
|
44 # addr_1 = PHI <&a, &b>
|
|
|
45 tmp_1 = *addr_1;
|
|
|
46
|
|
|
47 to
|
|
|
48
|
|
|
49 # tmp_1 = PHI <a, b>
|
|
|
50
|
|
|
51 but also handles more complex scenarios like
|
|
|
52
|
|
|
53 D.2077_2 = &this_1(D)->a1;
|
|
|
54 ...
|
|
|
55
|
|
|
56 # b_12 = PHI <&c(2), D.2077_2(3)>
|
|
|
57 D.2114_13 = *b_12;
|
|
|
58 ...
|
|
|
59
|
|
|
60 # b_15 = PHI <b_12(4), &b(5)>
|
|
|
61 D.2080_5 = &this_1(D)->a0;
|
|
|
62 ...
|
|
|
63
|
|
|
64 # b_18 = PHI <D.2080_5(6), &c(7)>
|
|
|
65 ...
|
|
|
66
|
|
|
67 # b_21 = PHI <b_15(8), b_18(9)>
|
|
|
68 D.2076_8 = *b_21;
|
|
|
69
|
|
|
70 where the addresses loaded are defined by PHIs itself.
|
|
|
71 The above happens for
|
|
|
72
|
|
|
73 std::max(std::min(a0, c), std::min(std::max(a1, c), b))
|
|
|
74
|
|
|
75 where this pass transforms it to a form later PHI optimization
|
|
|
76 recognizes and transforms it to the simple
|
|
|
77
|
|
|
78 D.2109_10 = this_1(D)->a1;
|
|
|
79 D.2110_11 = c;
|
|
|
80 D.2114_31 = MAX_EXPR <D.2109_10, D.2110_11>;
|
|
|
81 D.2115_14 = b;
|
|
|
82 D.2125_17 = MIN_EXPR <D.2115_14, D.2114_31>;
|
|
|
83 D.2119_16 = this_1(D)->a0;
|
|
|
84 D.2124_32 = MIN_EXPR <D.2110_11, D.2119_16>;
|
|
|
85 D.2076_33 = MAX_EXPR <D.2125_17, D.2124_32>;
|
|
|
86
|
|
|
87 The pass does a dominator walk processing loads using a basic-block
|
|
|
88 local analysis and stores the result for use by transformations on
|
|
|
89 dominated basic-blocks. */
|
|
|
90
|
|
|
91
|
|
|
92 /* Structure to keep track of the value of a dereferenced PHI result
|
|
|
93 and the set of virtual operands used for that dereference. */
|
|
|
94
|
|
|
95 struct phiprop_d
|
|
|
96 {
|
|
|
97 tree value;
|
|
|
98 gimple vop_stmt;
|
|
|
99 };
|
|
|
100
|
|
|
101 /* Verify if the value recorded for NAME in PHIVN is still valid at
|
|
|
102 the start of basic block BB. */
|
|
|
103
|
|
|
104 static bool
|
|
|
105 phivn_valid_p (struct phiprop_d *phivn, tree name, basic_block bb)
|
|
|
106 {
|
|
|
107 gimple vop_stmt = phivn[SSA_NAME_VERSION (name)].vop_stmt;
|
|
|
108 ssa_op_iter ui;
|
|
|
109 tree vuse;
|
|
|
110
|
|
|
111 /* The def stmts of all virtual uses need to be post-dominated
|
|
|
112 by bb. */
|
|
|
113 FOR_EACH_SSA_TREE_OPERAND (vuse, vop_stmt, ui, SSA_OP_VUSE)
|
|
|
114 {
|
|
|
115 gimple use_stmt;
|
|
|
116 imm_use_iterator ui2;
|
|
|
117 bool ok = true;
|
|
|
118
|
|
|
119 FOR_EACH_IMM_USE_STMT (use_stmt, ui2, vuse)
|
|
|
120 {
|
|
|
121 /* If BB does not dominate a VDEF, the value is invalid. */
|
|
|
122 if (((is_gimple_assign (use_stmt)
|
|
|
123 && !ZERO_SSA_OPERANDS (use_stmt, SSA_OP_VDEF))
|
|
|
124 || gimple_code (use_stmt) == GIMPLE_PHI)
|
|
|
125 && !dominated_by_p (CDI_DOMINATORS, gimple_bb (use_stmt), bb))
|
|
|
126 {
|
|
|
127 ok = false;
|
|
|
128 BREAK_FROM_IMM_USE_STMT (ui2);
|
|
|
129 }
|
|
|
130 }
|
|
|
131 if (!ok)
|
|
|
132 return false;
|
|
|
133 }
|
|
|
134
|
|
|
135 return true;
|
|
|
136 }
|
|
|
137
|
|
|
138 /* Insert a new phi node for the dereference of PHI at basic_block
|
|
|
139 BB with the virtual operands from USE_STMT. */
|
|
|
140
|
|
|
141 static tree
|
|
|
142 phiprop_insert_phi (basic_block bb, gimple phi, gimple use_stmt,
|
|
|
143 struct phiprop_d *phivn, size_t n)
|
|
|
144 {
|
|
|
145 tree res;
|
|
|
146 gimple new_phi;
|
|
|
147 edge_iterator ei;
|
|
|
148 edge e;
|
|
|
149
|
|
|
150 gcc_assert (is_gimple_assign (use_stmt)
|
|
|
151 && gimple_assign_rhs_code (use_stmt) == INDIRECT_REF);
|
|
|
152
|
|
|
153 /* Build a new PHI node to replace the definition of
|
|
|
154 the indirect reference lhs. */
|
|
|
155 res = gimple_assign_lhs (use_stmt);
|
|
|
156 SSA_NAME_DEF_STMT (res) = new_phi = create_phi_node (res, bb);
|
|
|
157
|
|
|
158 /* Add PHI arguments for each edge inserting loads of the
|
|
|
159 addressable operands. */
|
|
|
160 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
161 {
|
|
|
162 tree old_arg, new_var;
|
|
|
163 gimple tmp;
|
|
|
164
|
|
|
165 old_arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
|
|
|
166 while (TREE_CODE (old_arg) == SSA_NAME
|
|
|
167 && (SSA_NAME_VERSION (old_arg) >= n
|
|
|
168 || phivn[SSA_NAME_VERSION (old_arg)].value == NULL_TREE))
|
|
|
169 {
|
|
|
170 gimple def_stmt = SSA_NAME_DEF_STMT (old_arg);
|
|
|
171 old_arg = gimple_assign_rhs1 (def_stmt);
|
|
|
172 }
|
|
|
173
|
|
|
174 if (TREE_CODE (old_arg) == SSA_NAME)
|
|
|
175 /* Reuse a formerly created dereference. */
|
|
|
176 new_var = phivn[SSA_NAME_VERSION (old_arg)].value;
|
|
|
177 else
|
|
|
178 {
|
|
|
179 gcc_assert (TREE_CODE (old_arg) == ADDR_EXPR);
|
|
|
180 old_arg = TREE_OPERAND (old_arg, 0);
|
|
|
181 new_var = create_tmp_var (TREE_TYPE (old_arg), NULL);
|
|
|
182 tmp = gimple_build_assign (new_var, unshare_expr (old_arg));
|
|
|
183 if (TREE_CODE (TREE_TYPE (old_arg)) == COMPLEX_TYPE
|
|
|
184 || TREE_CODE (TREE_TYPE (old_arg)) == VECTOR_TYPE)
|
|
|
185 DECL_GIMPLE_REG_P (new_var) = 1;
|
|
|
186 gcc_assert (is_gimple_reg (new_var));
|
|
|
187 add_referenced_var (new_var);
|
|
|
188 new_var = make_ssa_name (new_var, tmp);
|
|
|
189 gimple_assign_set_lhs (tmp, new_var);
|
|
|
190
|
|
|
191 gsi_insert_on_edge (e, tmp);
|
|
|
192
|
|
|
193 update_stmt (tmp);
|
|
|
194 mark_symbols_for_renaming (tmp);
|
|
|
195 }
|
|
|
196
|
|
|
197 add_phi_arg (new_phi, new_var, e);
|
|
|
198 }
|
|
|
199
|
|
|
200 update_stmt (new_phi);
|
|
|
201
|
|
|
202 return res;
|
|
|
203 }
|
|
|
204
|
|
|
205 /* Propagate between the phi node arguments of PHI in BB and phi result
|
|
|
206 users. For now this matches
|
|
|
207 # p_2 = PHI <&x, &y>
|
|
|
208 <Lx>:;
|
|
|
209 p_3 = p_2;
|
|
|
210 z_2 = *p_3;
|
|
|
211 and converts it to
|
|
|
212 # z_2 = PHI <x, y>
|
|
|
213 <Lx>:;
|
|
|
214 Returns true if a transformation was done and edge insertions
|
|
|
215 need to be committed. Global data PHIVN and N is used to track
|
|
|
216 past transformation results. We need to be especially careful here
|
|
|
217 with aliasing issues as we are moving memory reads. */
|
|
|
218
|
|
|
219 static bool
|
|
|
220 propagate_with_phi (basic_block bb, gimple phi, struct phiprop_d *phivn,
|
|
|
221 size_t n)
|
|
|
222 {
|
|
|
223 tree ptr = PHI_RESULT (phi);
|
|
|
224 gimple use_stmt;
|
|
|
225 tree res = NULL_TREE;
|
|
|
226 gimple_stmt_iterator gsi;
|
|
|
227 imm_use_iterator ui;
|
|
|
228 use_operand_p arg_p, use;
|
|
|
229 ssa_op_iter i;
|
|
|
230 bool phi_inserted;
|
|
|
231
|
|
|
232 if (MTAG_P (SSA_NAME_VAR (ptr))
|
|
|
233 || !POINTER_TYPE_P (TREE_TYPE (ptr))
|
|
|
234 || !is_gimple_reg_type (TREE_TYPE (TREE_TYPE (ptr))))
|
|
|
235 return false;
|
|
|
236
|
|
|
237 /* Check if we can "cheaply" dereference all phi arguments. */
|
|
|
238 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
|
|
|
239 {
|
|
|
240 tree arg = USE_FROM_PTR (arg_p);
|
|
|
241 /* Walk the ssa chain until we reach a ssa name we already
|
|
|
242 created a value for or we reach a definition of the form
|
|
|
243 ssa_name_n = &var; */
|
|
|
244 while (TREE_CODE (arg) == SSA_NAME
|
|
|
245 && !SSA_NAME_IS_DEFAULT_DEF (arg)
|
|
|
246 && (SSA_NAME_VERSION (arg) >= n
|
|
|
247 || phivn[SSA_NAME_VERSION (arg)].value == NULL_TREE))
|
|
|
248 {
|
|
|
249 gimple def_stmt = SSA_NAME_DEF_STMT (arg);
|
|
|
250 if (!gimple_assign_single_p (def_stmt))
|
|
|
251 return false;
|
|
|
252 arg = gimple_assign_rhs1 (def_stmt);
|
|
|
253 }
|
|
|
254 if ((TREE_CODE (arg) != ADDR_EXPR
|
|
|
255 /* Avoid to have to decay *&a to a[0] later. */
|
|
|
256 || !is_gimple_reg_type (TREE_TYPE (TREE_OPERAND (arg, 0))))
|
|
|
257 && !(TREE_CODE (arg) == SSA_NAME
|
|
|
258 && phivn[SSA_NAME_VERSION (arg)].value != NULL_TREE
|
|
|
259 && phivn_valid_p (phivn, arg, bb)))
|
|
|
260 return false;
|
|
|
261 }
|
|
|
262
|
|
|
263 /* Find a dereferencing use. First follow (single use) ssa
|
|
|
264 copy chains for ptr. */
|
|
|
265 while (single_imm_use (ptr, &use, &use_stmt)
|
|
|
266 && gimple_assign_ssa_name_copy_p (use_stmt))
|
|
|
267 ptr = gimple_assign_lhs (use_stmt);
|
|
|
268
|
|
|
269 /* Replace the first dereference of *ptr if there is one and if we
|
|
|
270 can move the loads to the place of the ptr phi node. */
|
|
|
271 phi_inserted = false;
|
|
|
272 FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr)
|
|
|
273 {
|
|
|
274 ssa_op_iter ui2;
|
|
|
275 tree vuse;
|
|
|
276
|
|
|
277 /* Check whether this is a load of *ptr. */
|
|
|
278 if (!(is_gimple_assign (use_stmt)
|
|
|
279 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
|
|
|
280 && gimple_assign_rhs_code (use_stmt) == INDIRECT_REF
|
|
|
281 && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == ptr
|
|
|
282 /* We cannot replace a load that may throw or is volatile. */
|
|
|
283 && !stmt_can_throw_internal (use_stmt)))
|
|
|
284 continue;
|
|
|
285
|
|
|
286 /* Check if we can move the loads. The def stmts of all virtual uses
|
|
|
287 need to be post-dominated by bb. */
|
|
|
288 FOR_EACH_SSA_TREE_OPERAND (vuse, use_stmt, ui2, SSA_OP_VUSE)
|
|
|
289 {
|
|
|
290 gimple def_stmt = SSA_NAME_DEF_STMT (vuse);
|
|
|
291 if (!SSA_NAME_IS_DEFAULT_DEF (vuse)
|
|
|
292 && (gimple_bb (def_stmt) == bb
|
|
|
293 || !dominated_by_p (CDI_DOMINATORS,
|
|
|
294 bb, gimple_bb (def_stmt))))
|
|
|
295 goto next;
|
|
|
296 }
|
|
|
297
|
|
|
298 /* Found a proper dereference. Insert a phi node if this
|
|
|
299 is the first load transformation. */
|
|
|
300 if (!phi_inserted)
|
|
|
301 {
|
|
|
302 res = phiprop_insert_phi (bb, phi, use_stmt, phivn, n);
|
|
|
303
|
|
|
304 /* Remember the value we created for *ptr. */
|
|
|
305 phivn[SSA_NAME_VERSION (ptr)].value = res;
|
|
|
306 phivn[SSA_NAME_VERSION (ptr)].vop_stmt = use_stmt;
|
|
|
307
|
|
|
308 /* Remove old stmt. The phi is taken care of by DCE, if we
|
|
|
309 want to delete it here we also have to delete all intermediate
|
|
|
310 copies. */
|
|
|
311 gsi = gsi_for_stmt (use_stmt);
|
|
|
312 gsi_remove (&gsi, false);
|
|
|
313
|
|
|
314 phi_inserted = true;
|
|
|
315 }
|
|
|
316 else
|
|
|
317 {
|
|
|
318 /* Further replacements are easy, just make a copy out of the
|
|
|
319 load. */
|
|
|
320 gimple_assign_set_rhs1 (use_stmt, res);
|
|
|
321 update_stmt (use_stmt);
|
|
|
322 }
|
|
|
323
|
|
|
324 next:;
|
|
|
325 /* Continue searching for a proper dereference. */
|
|
|
326 }
|
|
|
327
|
|
|
328 return phi_inserted;
|
|
|
329 }
|
|
|
330
|
|
|
331 /* Helper walking the dominator tree starting from BB and processing
|
|
|
332 phi nodes with global data PHIVN and N. */
|
|
|
333
|
|
|
334 static bool
|
|
|
335 tree_ssa_phiprop_1 (basic_block bb, struct phiprop_d *phivn, size_t n)
|
|
|
336 {
|
|
|
337 bool did_something = false;
|
|
|
338 basic_block son;
|
|
|
339 gimple_stmt_iterator gsi;
|
|
|
340
|
|
|
341 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
342 did_something |= propagate_with_phi (bb, gsi_stmt (gsi), phivn, n);
|
|
|
343
|
|
|
344 for (son = first_dom_son (CDI_DOMINATORS, bb);
|
|
|
345 son;
|
|
|
346 son = next_dom_son (CDI_DOMINATORS, son))
|
|
|
347 did_something |= tree_ssa_phiprop_1 (son, phivn, n);
|
|
|
348
|
|
|
349 return did_something;
|
|
|
350 }
|
|
|
351
|
|
|
352 /* Main entry for phiprop pass. */
|
|
|
353
|
|
|
354 static unsigned int
|
|
|
355 tree_ssa_phiprop (void)
|
|
|
356 {
|
|
|
357 struct phiprop_d *phivn;
|
|
|
358
|
|
|
359 calculate_dominance_info (CDI_DOMINATORS);
|
|
|
360
|
|
|
361 phivn = XCNEWVEC (struct phiprop_d, num_ssa_names);
|
|
|
362
|
|
|
363 if (tree_ssa_phiprop_1 (ENTRY_BLOCK_PTR, phivn, num_ssa_names))
|
|
|
364 gsi_commit_edge_inserts ();
|
|
|
365
|
|
|
366 free (phivn);
|
|
|
367
|
|
|
368 return 0;
|
|
|
369 }
|
|
|
370
|
|
|
371 static bool
|
|
|
372 gate_phiprop (void)
|
|
|
373 {
|
|
|
374 return 1;
|
|
|
375 }
|
|
|
376
|
|
|
377 struct gimple_opt_pass pass_phiprop =
|
|
|
378 {
|
|
|
379 {
|
|
|
380 GIMPLE_PASS,
|
|
|
381 "phiprop", /* name */
|
|
|
382 gate_phiprop, /* gate */
|
|
|
383 tree_ssa_phiprop, /* execute */
|
|
|
384 NULL, /* sub */
|
|
|
385 NULL, /* next */
|
|
|
386 0, /* static_pass_number */
|
|
|
387 TV_TREE_PHIPROP, /* tv_id */
|
|
|
388 PROP_cfg | PROP_ssa, /* properties_required */
|
|
|
389 0, /* properties_provided */
|
|
|
390 0, /* properties_destroyed */
|
|
|
391 0, /* todo_flags_start */
|
|
|
392 TODO_dump_func
|
|
|
393 | TODO_ggc_collect
|
|
|
394 | TODO_update_ssa
|
|
|
395 | TODO_verify_ssa /* todo_flags_finish */
|
|
|
396 }
|
|
|
397 };
|
