1/* Backward propagation of indirect loads through PHIs.
2 Copyright (C) 2007-2017 Free Software Foundation, Inc.
3 Contributed by Richard Guenther <rguenther@suse.de>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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 "backend.h"
25#include "tree.h"
26#include "gimple.h"
27#include "tree-pass.h"
28#include "ssa.h"
29#include "gimple-pretty-print.h"
30#include "fold-const.h"
31#include "tree-eh.h"
32#include "gimplify.h"
33#include "gimple-iterator.h"
34#include "stor-layout.h"
35#include "tree-ssa-loop.h"
36
37/* This pass propagates indirect loads through the PHI node for its
38 address to make the load source possibly non-addressable and to
39 allow for PHI optimization to trigger.
40
41 For example the pass changes
42
43 # addr_1 = PHI <&a, &b>
44 tmp_1 = *addr_1;
45
46 to
47
48 # tmp_1 = PHI <a, b>
49
50 but also handles more complex scenarios like
51
52 D.2077_2 = &this_1(D)->a1;
53 ...
54
55 # b_12 = PHI <&c(2), D.2077_2(3)>
56 D.2114_13 = *b_12;
57 ...
58
59 # b_15 = PHI <b_12(4), &b(5)>
60 D.2080_5 = &this_1(D)->a0;
61 ...
62
63 # b_18 = PHI <D.2080_5(6), &c(7)>
64 ...
65
66 # b_21 = PHI <b_15(8), b_18(9)>
67 D.2076_8 = *b_21;
68
69 where the addresses loaded are defined by PHIs itself.
70 The above happens for
71
72 std::max(std::min(a0, c), std::min(std::max(a1, c), b))
73
74 where this pass transforms it to a form later PHI optimization
75 recognizes and transforms it to the simple
76
77 D.2109_10 = this_1(D)->a1;
78 D.2110_11 = c;
79 D.2114_31 = MAX_EXPR <D.2109_10, D.2110_11>;
80 D.2115_14 = b;
81 D.2125_17 = MIN_EXPR <D.2115_14, D.2114_31>;
82 D.2119_16 = this_1(D)->a0;
83 D.2124_32 = MIN_EXPR <D.2110_11, D.2119_16>;
84 D.2076_33 = MAX_EXPR <D.2125_17, D.2124_32>;
85
86 The pass does a dominator walk processing loads using a basic-block
87 local analysis and stores the result for use by transformations on
88 dominated basic-blocks. */
89
90
91/* Structure to keep track of the value of a dereferenced PHI result
92 and the virtual operand used for that dereference. */
93
94struct phiprop_d
95{
96 tree value;
97 tree vuse;
98};
99
100/* Verify if the value recorded for NAME in PHIVN is still valid at
101 the start of basic block BB. */
102
103static bool
104phivn_valid_p (struct phiprop_d *phivn, tree name, basic_block bb)
105{
106 tree vuse = phivn[SSA_NAME_VERSION (name)].vuse;
107 gimple *use_stmt;
108 imm_use_iterator ui2;
109 bool ok = true;
110
111 /* The def stmts of the virtual uses need to be dominated by bb. */
112 gcc_assert (vuse != NULL_TREE);
113
114 FOR_EACH_IMM_USE_STMT (use_stmt, ui2, vuse)
115 {
116 /* If BB does not dominate a VDEF, the value is invalid. */
117 if ((gimple_vdef (use_stmt) != NULL_TREE
118 || gimple_code (use_stmt) == GIMPLE_PHI)
119 && !dominated_by_p (CDI_DOMINATORS, gimple_bb (use_stmt), bb))
120 {
121 ok = false;
122 BREAK_FROM_IMM_USE_STMT (ui2);
123 }
124 }
125
126 return ok;
127}
128
129/* Insert a new phi node for the dereference of PHI at basic_block
130 BB with the virtual operands from USE_STMT. */
131
132static tree
133phiprop_insert_phi (basic_block bb, gphi *phi, gimple *use_stmt,
134 struct phiprop_d *phivn, size_t n)
135{
136 tree res;
137 gphi *new_phi = NULL;
138 edge_iterator ei;
139 edge e;
140
141 gcc_assert (is_gimple_assign (use_stmt)
142 && gimple_assign_rhs_code (use_stmt) == MEM_REF);
143
144 /* Build a new PHI node to replace the definition of
145 the indirect reference lhs. */
146 res = gimple_assign_lhs (use_stmt);
147 if (TREE_CODE (res) == SSA_NAME)
148 new_phi = create_phi_node (res, bb);
149
150 if (dump_file && (dump_flags & TDF_DETAILS))
151 {
152 fprintf (dump_file, "Inserting PHI for result of load ");
153 print_gimple_stmt (dump_file, use_stmt, 0);
154 }
155
156 /* Add PHI arguments for each edge inserting loads of the
157 addressable operands. */
158 FOR_EACH_EDGE (e, ei, bb->preds)
159 {
160 tree old_arg, new_var;
161 gassign *tmp;
162 source_location locus;
163
164 old_arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
165 locus = gimple_phi_arg_location_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 locus = gimple_location (def_stmt);
173 }
174
175 if (TREE_CODE (old_arg) == SSA_NAME)
176 {
177 if (dump_file && (dump_flags & TDF_DETAILS))
178 {
179 fprintf (dump_file, " for edge defining ");
180 print_generic_expr (dump_file, PHI_ARG_DEF_FROM_EDGE (phi, e));
181 fprintf (dump_file, " reusing PHI result ");
182 print_generic_expr (dump_file,
183 phivn[SSA_NAME_VERSION (old_arg)].value);
184 fprintf (dump_file, "\n");
185 }
186 /* Reuse a formerly created dereference. */
187 new_var = phivn[SSA_NAME_VERSION (old_arg)].value;
188 }
189 else
190 {
191 tree rhs = gimple_assign_rhs1 (use_stmt);
192 gcc_assert (TREE_CODE (old_arg) == ADDR_EXPR);
193 if (TREE_CODE (res) == SSA_NAME)
194 new_var = make_ssa_name (TREE_TYPE (rhs));
195 else
196 new_var = unshare_expr (res);
197 if (!is_gimple_min_invariant (old_arg))
198 old_arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
199 else
200 old_arg = unshare_expr (old_arg);
201 tmp = gimple_build_assign (new_var,
202 fold_build2 (MEM_REF, TREE_TYPE (rhs),
203 old_arg,
204 TREE_OPERAND (rhs, 1)));
205 gimple_set_location (tmp, locus);
206
207 gsi_insert_on_edge (e, tmp);
208 update_stmt (tmp);
209
210 if (dump_file && (dump_flags & TDF_DETAILS))
211 {
212 fprintf (dump_file, " for edge defining ");
213 print_generic_expr (dump_file, PHI_ARG_DEF_FROM_EDGE (phi, e));
214 fprintf (dump_file, " inserting load ");
215 print_gimple_stmt (dump_file, tmp, 0);
216 }
217 }
218
219 if (new_phi)
220 add_phi_arg (new_phi, new_var, e, locus);
221 }
222
223 if (new_phi)
224 {
225 update_stmt (new_phi);
226
227 if (dump_file && (dump_flags & TDF_DETAILS))
228 print_gimple_stmt (dump_file, new_phi, 0);
229 }
230
231 return res;
232}
233
234/* Verify if *idx is available at *DATA. */
235
236static bool
237chk_uses (tree, tree *idx, void *data)
238{
239 basic_block dom = (basic_block) data;
240 if (TREE_CODE (*idx) == SSA_NAME)
241 return (SSA_NAME_IS_DEFAULT_DEF (*idx)
242 || ! dominated_by_p (CDI_DOMINATORS,
243 gimple_bb (SSA_NAME_DEF_STMT (*idx)), dom));
244 return true;
245}
246
247/* Propagate between the phi node arguments of PHI in BB and phi result
248 users. For now this matches
249 # p_2 = PHI <&x, &y>
250 <Lx>:;
251 p_3 = p_2;
252 z_2 = *p_3;
253 and converts it to
254 # z_2 = PHI <x, y>
255 <Lx>:;
256 Returns true if a transformation was done and edge insertions
257 need to be committed. Global data PHIVN and N is used to track
258 past transformation results. We need to be especially careful here
259 with aliasing issues as we are moving memory reads. */
260
261static bool
262propagate_with_phi (basic_block bb, gphi *phi, struct phiprop_d *phivn,
263 size_t n)
264{
265 tree ptr = PHI_RESULT (phi);
266 gimple *use_stmt;
267 tree res = NULL_TREE;
268 gimple_stmt_iterator gsi;
269 imm_use_iterator ui;
270 use_operand_p arg_p, use;
271 ssa_op_iter i;
272 bool phi_inserted;
273 tree type = NULL_TREE;
274
275 if (!POINTER_TYPE_P (TREE_TYPE (ptr))
276 || (!is_gimple_reg_type (TREE_TYPE (TREE_TYPE (ptr)))
277 && TYPE_MODE (TREE_TYPE (TREE_TYPE (ptr))) == BLKmode))
278 return false;
279
280 /* Check if we can "cheaply" dereference all phi arguments. */
281 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
282 {
283 tree arg = USE_FROM_PTR (arg_p);
284 /* Walk the ssa chain until we reach a ssa name we already
285 created a value for or we reach a definition of the form
286 ssa_name_n = &var; */
287 while (TREE_CODE (arg) == SSA_NAME
288 && !SSA_NAME_IS_DEFAULT_DEF (arg)
289 && (SSA_NAME_VERSION (arg) >= n
290 || phivn[SSA_NAME_VERSION (arg)].value == NULL_TREE))
291 {
292 gimple *def_stmt = SSA_NAME_DEF_STMT (arg);
293 if (!gimple_assign_single_p (def_stmt))
294 return false;
295 arg = gimple_assign_rhs1 (def_stmt);
296 }
297 if (TREE_CODE (arg) != ADDR_EXPR
298 && !(TREE_CODE (arg) == SSA_NAME
299 && SSA_NAME_VERSION (arg) < n
300 && phivn[SSA_NAME_VERSION (arg)].value != NULL_TREE
301 && (!type
302 || types_compatible_p
303 (type, TREE_TYPE (phivn[SSA_NAME_VERSION (arg)].value)))
304 && phivn_valid_p (phivn, arg, bb)))
305 return false;
306 if (!type
307 && TREE_CODE (arg) == SSA_NAME)
308 type = TREE_TYPE (phivn[SSA_NAME_VERSION (arg)].value);
309 }
310
311 /* Find a dereferencing use. First follow (single use) ssa
312 copy chains for ptr. */
313 while (single_imm_use (ptr, &use, &use_stmt)
314 && gimple_assign_ssa_name_copy_p (use_stmt))
315 ptr = gimple_assign_lhs (use_stmt);
316
317 /* Replace the first dereference of *ptr if there is one and if we
318 can move the loads to the place of the ptr phi node. */
319 phi_inserted = false;
320 FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr)
321 {
322 gimple *def_stmt;
323 tree vuse;
324
325 /* Only replace loads in blocks that post-dominate the PHI node. That
326 makes sure we don't end up speculating loads. */
327 if (!dominated_by_p (CDI_POST_DOMINATORS,
328 bb, gimple_bb (use_stmt)))
329 continue;
330
331 /* Check whether this is a load of *ptr. */
332 if (!(is_gimple_assign (use_stmt)
333 && gimple_assign_rhs_code (use_stmt) == MEM_REF
334 && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == ptr
335 && integer_zerop (TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 1))
336 && (!type
337 || types_compatible_p
338 (TREE_TYPE (gimple_assign_lhs (use_stmt)), type))
339 /* We cannot replace a load that may throw or is volatile. */
340 && !stmt_can_throw_internal (use_stmt)))
341 continue;
342
343 /* Check if we can move the loads. The def stmt of the virtual use
344 needs to be in a different basic block dominating bb. When the
345 def is an edge-inserted one we know it dominates us. */
346 vuse = gimple_vuse (use_stmt);
347 def_stmt = SSA_NAME_DEF_STMT (vuse);
348 if (!SSA_NAME_IS_DEFAULT_DEF (vuse)
349 && (gimple_bb (def_stmt) == bb
350 || (gimple_bb (def_stmt)
351 && !dominated_by_p (CDI_DOMINATORS,
352 bb, gimple_bb (def_stmt)))))
353 goto next;
354
355 /* Found a proper dereference with an aggregate copy. Just
356 insert aggregate copies on the edges instead. */
357 if (!is_gimple_reg_type (TREE_TYPE (gimple_assign_lhs (use_stmt))))
358 {
359 if (!gimple_vdef (use_stmt))
360 goto next;
361
362 /* As we replicate the lhs on each incoming edge all
363 used SSA names have to be available there. */
364 if (! for_each_index (gimple_assign_lhs_ptr (use_stmt),
365 chk_uses,
366 get_immediate_dominator (CDI_DOMINATORS,
367 gimple_bb (phi))))
368 goto next;
369
370 gimple *vuse_stmt;
371 imm_use_iterator vui;
372 use_operand_p vuse_p;
373 /* In order to move the aggregate copies earlier, make sure
374 there are no statements that could read from memory
375 aliasing the lhs in between the start of bb and use_stmt.
376 As we require use_stmt to have a VDEF above, loads after
377 use_stmt will use a different virtual SSA_NAME. */
378 FOR_EACH_IMM_USE_FAST (vuse_p, vui, vuse)
379 {
380 vuse_stmt = USE_STMT (vuse_p);
381 if (vuse_stmt == use_stmt)
382 continue;
383 if (!dominated_by_p (CDI_DOMINATORS,
384 gimple_bb (vuse_stmt), bb))
385 continue;
386 if (ref_maybe_used_by_stmt_p (vuse_stmt,
387 gimple_assign_lhs (use_stmt)))
388 goto next;
389 }
390
391 phiprop_insert_phi (bb, phi, use_stmt, phivn, n);
392
393 /* Remove old stmt. The phi is taken care of by DCE. */
394 gsi = gsi_for_stmt (use_stmt);
395 /* Unlinking the VDEF here is fine as we are sure that we process
396 stmts in execution order due to aggregate copies having VDEFs
397 and we emit loads on the edges in the very same order.
398 We get multiple copies (or intermediate register loads) handled
399 only by walking PHIs or immediate uses in a lucky order though,
400 so we could signal the caller to re-start iterating over PHIs
401 when we come here which would make it quadratic in the number
402 of PHIs. */
403 unlink_stmt_vdef (use_stmt);
404 gsi_remove (&gsi, true);
405
406 phi_inserted = true;
407 }
408
409 /* Found a proper dereference. Insert a phi node if this
410 is the first load transformation. */
411 else if (!phi_inserted)
412 {
413 res = phiprop_insert_phi (bb, phi, use_stmt, phivn, n);
414 type = TREE_TYPE (res);
415
416 /* Remember the value we created for *ptr. */
417 phivn[SSA_NAME_VERSION (ptr)].value = res;
418 phivn[SSA_NAME_VERSION (ptr)].vuse = vuse;
419
420 /* Remove old stmt. The phi is taken care of by DCE, if we
421 want to delete it here we also have to delete all intermediate
422 copies. */
423 gsi = gsi_for_stmt (use_stmt);
424 gsi_remove (&gsi, true);
425
426 phi_inserted = true;
427 }
428 else
429 {
430 /* Further replacements are easy, just make a copy out of the
431 load. */
432 gimple_assign_set_rhs1 (use_stmt, res);
433 update_stmt (use_stmt);
434 }
435
436next:;
437 /* Continue searching for a proper dereference. */
438 }
439
440 return phi_inserted;
441}
442
443/* Main entry for phiprop pass. */
444
445namespace {
446
447const pass_data pass_data_phiprop =
448{
449 GIMPLE_PASS, /* type */
450 "phiprop", /* name */
451 OPTGROUP_NONE, /* optinfo_flags */
452 TV_TREE_PHIPROP, /* tv_id */
453 ( PROP_cfg | PROP_ssa ), /* properties_required */
454 0, /* properties_provided */
455 0, /* properties_destroyed */
456 0, /* todo_flags_start */
457 TODO_update_ssa, /* todo_flags_finish */
458};
459
460class pass_phiprop : public gimple_opt_pass
461{
462public:
463 pass_phiprop (gcc::context *ctxt)
464 : gimple_opt_pass (pass_data_phiprop, ctxt)
465 {}
466
467 /* opt_pass methods: */
468 virtual bool gate (function *) { return flag_tree_phiprop; }
469 virtual unsigned int execute (function *);
470
471}; // class pass_phiprop
472
473unsigned int
474pass_phiprop::execute (function *fun)
475{
476 vec<basic_block> bbs;
477 struct phiprop_d *phivn;
478 bool did_something = false;
479 basic_block bb;
480 gphi_iterator gsi;
481 unsigned i;
482 size_t n;
483
484 calculate_dominance_info (CDI_DOMINATORS);
485 calculate_dominance_info (CDI_POST_DOMINATORS);
486
487 n = num_ssa_names;
488 phivn = XCNEWVEC (struct phiprop_d, n);
489
490 /* Walk the dominator tree in preorder. */
491 bbs = get_all_dominated_blocks (CDI_DOMINATORS,
492 single_succ (ENTRY_BLOCK_PTR_FOR_FN (fun)));
493 FOR_EACH_VEC_ELT (bbs, i, bb)
494 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
495 did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n);
496
497 if (did_something)
498 gsi_commit_edge_inserts ();
499
500 bbs.release ();
501 free (phivn);
502
503 free_dominance_info (CDI_POST_DOMINATORS);
504
505 return 0;
506}
507
508} // anon namespace
509
510gimple_opt_pass *
511make_pass_phiprop (gcc::context *ctxt)
512{
513 return new pass_phiprop (ctxt);
514}
515