1 /* Backward propagation of indirect loads through PHIs.
2 Copyright (C) 2007-2016 Free Software Foundation, Inc.
3 Contributed by Richard Guenther <rguenther@suse.de>
5 This file is part of GCC.
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)
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.
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/>. */
23 #include "coretypes.h"
27 #include "tree-pass.h"
29 #include "gimple-pretty-print.h"
30 #include "fold-const.h"
33 #include "gimple-iterator.h"
34 #include "stor-layout.h"
36 /* This pass propagates indirect loads through the PHI node for its
37 address to make the load source possibly non-addressable and to
38 allow for PHI optimization to trigger.
40 For example the pass changes
42 # addr_1 = PHI <&a, &b>
49 but also handles more complex scenarios like
51 D.2077_2 = &this_1(D)->a1;
54 # b_12 = PHI <&c(2), D.2077_2(3)>
58 # b_15 = PHI <b_12(4), &b(5)>
59 D.2080_5 = &this_1(D)->a0;
62 # b_18 = PHI <D.2080_5(6), &c(7)>
65 # b_21 = PHI <b_15(8), b_18(9)>
68 where the addresses loaded are defined by PHIs itself.
71 std::max(std::min(a0, c), std::min(std::max(a1, c), b))
73 where this pass transforms it to a form later PHI optimization
74 recognizes and transforms it to the simple
76 D.2109_10 = this_1(D)->a1;
78 D.2114_31 = MAX_EXPR <D.2109_10, D.2110_11>;
80 D.2125_17 = MIN_EXPR <D.2115_14, D.2114_31>;
81 D.2119_16 = this_1(D)->a0;
82 D.2124_32 = MIN_EXPR <D.2110_11, D.2119_16>;
83 D.2076_33 = MAX_EXPR <D.2125_17, D.2124_32>;
85 The pass does a dominator walk processing loads using a basic-block
86 local analysis and stores the result for use by transformations on
87 dominated basic-blocks. */
90 /* Structure to keep track of the value of a dereferenced PHI result
91 and the virtual operand used for that dereference. */
99 /* Verify if the value recorded for NAME in PHIVN is still valid at
100 the start of basic block BB. */
103 phivn_valid_p (struct phiprop_d
*phivn
, tree name
, basic_block bb
)
105 tree vuse
= phivn
[SSA_NAME_VERSION (name
)].vuse
;
107 imm_use_iterator ui2
;
110 /* The def stmts of the virtual uses need to be dominated by bb. */
111 gcc_assert (vuse
!= NULL_TREE
);
113 FOR_EACH_IMM_USE_STMT (use_stmt
, ui2
, vuse
)
115 /* If BB does not dominate a VDEF, the value is invalid. */
116 if ((gimple_vdef (use_stmt
) != NULL_TREE
117 || gimple_code (use_stmt
) == GIMPLE_PHI
)
118 && !dominated_by_p (CDI_DOMINATORS
, gimple_bb (use_stmt
), bb
))
121 BREAK_FROM_IMM_USE_STMT (ui2
);
128 /* Insert a new phi node for the dereference of PHI at basic_block
129 BB with the virtual operands from USE_STMT. */
132 phiprop_insert_phi (basic_block bb
, gphi
*phi
, gimple
*use_stmt
,
133 struct phiprop_d
*phivn
, size_t n
)
136 gphi
*new_phi
= NULL
;
140 gcc_assert (is_gimple_assign (use_stmt
)
141 && gimple_assign_rhs_code (use_stmt
) == MEM_REF
);
143 /* Build a new PHI node to replace the definition of
144 the indirect reference lhs. */
145 res
= gimple_assign_lhs (use_stmt
);
146 if (TREE_CODE (res
) == SSA_NAME
)
147 new_phi
= create_phi_node (res
, bb
);
149 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
151 fprintf (dump_file
, "Inserting PHI for result of load ");
152 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
155 /* Add PHI arguments for each edge inserting loads of the
156 addressable operands. */
157 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
159 tree old_arg
, new_var
;
161 source_location locus
;
163 old_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
164 locus
= gimple_phi_arg_location_from_edge (phi
, e
);
165 while (TREE_CODE (old_arg
) == SSA_NAME
166 && (SSA_NAME_VERSION (old_arg
) >= n
167 || phivn
[SSA_NAME_VERSION (old_arg
)].value
== NULL_TREE
))
169 gimple
*def_stmt
= SSA_NAME_DEF_STMT (old_arg
);
170 old_arg
= gimple_assign_rhs1 (def_stmt
);
171 locus
= gimple_location (def_stmt
);
174 if (TREE_CODE (old_arg
) == SSA_NAME
)
176 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
178 fprintf (dump_file
, " for edge defining ");
179 print_generic_expr (dump_file
, PHI_ARG_DEF_FROM_EDGE (phi
, e
), 0);
180 fprintf (dump_file
, " reusing PHI result ");
181 print_generic_expr (dump_file
,
182 phivn
[SSA_NAME_VERSION (old_arg
)].value
, 0);
183 fprintf (dump_file
, "\n");
185 /* Reuse a formerly created dereference. */
186 new_var
= phivn
[SSA_NAME_VERSION (old_arg
)].value
;
190 tree rhs
= gimple_assign_rhs1 (use_stmt
);
191 gcc_assert (TREE_CODE (old_arg
) == ADDR_EXPR
);
192 if (TREE_CODE (res
) == SSA_NAME
)
193 new_var
= make_ssa_name (TREE_TYPE (rhs
));
195 new_var
= unshare_expr (res
);
196 if (!is_gimple_min_invariant (old_arg
))
197 old_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
199 old_arg
= unshare_expr (old_arg
);
200 tmp
= gimple_build_assign (new_var
,
201 fold_build2 (MEM_REF
, TREE_TYPE (rhs
),
203 TREE_OPERAND (rhs
, 1)));
204 gimple_set_location (tmp
, locus
);
206 gsi_insert_on_edge (e
, tmp
);
209 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
211 fprintf (dump_file
, " for edge defining ");
212 print_generic_expr (dump_file
, PHI_ARG_DEF_FROM_EDGE (phi
, e
), 0);
213 fprintf (dump_file
, " inserting load ");
214 print_gimple_stmt (dump_file
, tmp
, 0, 0);
219 add_phi_arg (new_phi
, new_var
, e
, locus
);
224 update_stmt (new_phi
);
226 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
227 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
233 /* Propagate between the phi node arguments of PHI in BB and phi result
234 users. For now this matches
242 Returns true if a transformation was done and edge insertions
243 need to be committed. Global data PHIVN and N is used to track
244 past transformation results. We need to be especially careful here
245 with aliasing issues as we are moving memory reads. */
248 propagate_with_phi (basic_block bb
, gphi
*phi
, struct phiprop_d
*phivn
,
251 tree ptr
= PHI_RESULT (phi
);
253 tree res
= NULL_TREE
;
254 gimple_stmt_iterator gsi
;
256 use_operand_p arg_p
, use
;
259 tree type
= NULL_TREE
;
261 if (!POINTER_TYPE_P (TREE_TYPE (ptr
))
262 || (!is_gimple_reg_type (TREE_TYPE (TREE_TYPE (ptr
)))
263 && TYPE_MODE (TREE_TYPE (TREE_TYPE (ptr
))) == BLKmode
))
266 /* Check if we can "cheaply" dereference all phi arguments. */
267 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_USE
)
269 tree arg
= USE_FROM_PTR (arg_p
);
270 /* Walk the ssa chain until we reach a ssa name we already
271 created a value for or we reach a definition of the form
272 ssa_name_n = &var; */
273 while (TREE_CODE (arg
) == SSA_NAME
274 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
275 && (SSA_NAME_VERSION (arg
) >= n
276 || phivn
[SSA_NAME_VERSION (arg
)].value
== NULL_TREE
))
278 gimple
*def_stmt
= SSA_NAME_DEF_STMT (arg
);
279 if (!gimple_assign_single_p (def_stmt
))
281 arg
= gimple_assign_rhs1 (def_stmt
);
283 if (TREE_CODE (arg
) != ADDR_EXPR
284 && !(TREE_CODE (arg
) == SSA_NAME
285 && SSA_NAME_VERSION (arg
) < n
286 && phivn
[SSA_NAME_VERSION (arg
)].value
!= NULL_TREE
288 || types_compatible_p
289 (type
, TREE_TYPE (phivn
[SSA_NAME_VERSION (arg
)].value
)))
290 && phivn_valid_p (phivn
, arg
, bb
)))
293 && TREE_CODE (arg
) == SSA_NAME
)
294 type
= TREE_TYPE (phivn
[SSA_NAME_VERSION (arg
)].value
);
297 /* Find a dereferencing use. First follow (single use) ssa
298 copy chains for ptr. */
299 while (single_imm_use (ptr
, &use
, &use_stmt
)
300 && gimple_assign_ssa_name_copy_p (use_stmt
))
301 ptr
= gimple_assign_lhs (use_stmt
);
303 /* Replace the first dereference of *ptr if there is one and if we
304 can move the loads to the place of the ptr phi node. */
305 phi_inserted
= false;
306 FOR_EACH_IMM_USE_STMT (use_stmt
, ui
, ptr
)
311 /* Only replace loads in blocks that post-dominate the PHI node. That
312 makes sure we don't end up speculating loads. */
313 if (!dominated_by_p (CDI_POST_DOMINATORS
,
314 bb
, gimple_bb (use_stmt
)))
317 /* Check whether this is a load of *ptr. */
318 if (!(is_gimple_assign (use_stmt
)
319 && gimple_assign_rhs_code (use_stmt
) == MEM_REF
320 && TREE_OPERAND (gimple_assign_rhs1 (use_stmt
), 0) == ptr
321 && integer_zerop (TREE_OPERAND (gimple_assign_rhs1 (use_stmt
), 1))
323 || types_compatible_p
324 (TREE_TYPE (gimple_assign_lhs (use_stmt
)), type
))
325 /* We cannot replace a load that may throw or is volatile. */
326 && !stmt_can_throw_internal (use_stmt
)))
329 /* Check if we can move the loads. The def stmt of the virtual use
330 needs to be in a different basic block dominating bb. */
331 vuse
= gimple_vuse (use_stmt
);
332 def_stmt
= SSA_NAME_DEF_STMT (vuse
);
333 if (!SSA_NAME_IS_DEFAULT_DEF (vuse
)
334 && (gimple_bb (def_stmt
) == bb
335 || !dominated_by_p (CDI_DOMINATORS
,
336 bb
, gimple_bb (def_stmt
))))
339 /* Found a proper dereference with an aggregate copy. Just
340 insert aggregate copies on the edges instead. */
341 if (!is_gimple_reg_type (TREE_TYPE (TREE_TYPE (ptr
))))
343 phiprop_insert_phi (bb
, phi
, use_stmt
, phivn
, n
);
345 /* Remove old stmt. The phi is taken care of by DCE. */
346 gsi
= gsi_for_stmt (use_stmt
);
347 /* Unlinking the VDEF here is fine as we are sure that we process
348 stmts in execution order due to aggregate copies having VDEFs
349 and we emit loads on the edges in the very same order.
350 We get multiple copies (or intermediate register loads) handled
351 only by walking PHIs or immediate uses in a lucky order though,
352 so we could signal the caller to re-start iterating over PHIs
353 when we come here which would make it quadratic in the number
355 unlink_stmt_vdef (use_stmt
);
356 gsi_remove (&gsi
, true);
361 /* Found a proper dereference. Insert a phi node if this
362 is the first load transformation. */
363 else if (!phi_inserted
)
365 res
= phiprop_insert_phi (bb
, phi
, use_stmt
, phivn
, n
);
366 type
= TREE_TYPE (res
);
368 /* Remember the value we created for *ptr. */
369 phivn
[SSA_NAME_VERSION (ptr
)].value
= res
;
370 phivn
[SSA_NAME_VERSION (ptr
)].vuse
= vuse
;
372 /* Remove old stmt. The phi is taken care of by DCE, if we
373 want to delete it here we also have to delete all intermediate
375 gsi
= gsi_for_stmt (use_stmt
);
376 gsi_remove (&gsi
, true);
382 /* Further replacements are easy, just make a copy out of the
384 gimple_assign_set_rhs1 (use_stmt
, res
);
385 update_stmt (use_stmt
);
389 /* Continue searching for a proper dereference. */
395 /* Main entry for phiprop pass. */
399 const pass_data pass_data_phiprop
=
401 GIMPLE_PASS
, /* type */
402 "phiprop", /* name */
403 OPTGROUP_NONE
, /* optinfo_flags */
404 TV_TREE_PHIPROP
, /* tv_id */
405 ( PROP_cfg
| PROP_ssa
), /* properties_required */
406 0, /* properties_provided */
407 0, /* properties_destroyed */
408 0, /* todo_flags_start */
409 TODO_update_ssa
, /* todo_flags_finish */
412 class pass_phiprop
: public gimple_opt_pass
415 pass_phiprop (gcc::context
*ctxt
)
416 : gimple_opt_pass (pass_data_phiprop
, ctxt
)
419 /* opt_pass methods: */
420 virtual bool gate (function
*) { return flag_tree_phiprop
; }
421 virtual unsigned int execute (function
*);
423 }; // class pass_phiprop
426 pass_phiprop::execute (function
*fun
)
428 vec
<basic_block
> bbs
;
429 struct phiprop_d
*phivn
;
430 bool did_something
= false;
436 calculate_dominance_info (CDI_DOMINATORS
);
437 calculate_dominance_info (CDI_POST_DOMINATORS
);
440 phivn
= XCNEWVEC (struct phiprop_d
, n
);
442 /* Walk the dominator tree in preorder. */
443 bbs
= get_all_dominated_blocks (CDI_DOMINATORS
,
444 single_succ (ENTRY_BLOCK_PTR_FOR_FN (fun
)));
445 FOR_EACH_VEC_ELT (bbs
, i
, bb
)
446 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
447 did_something
|= propagate_with_phi (bb
, gsi
.phi (), phivn
, n
);
450 gsi_commit_edge_inserts ();
455 free_dominance_info (CDI_POST_DOMINATORS
);
463 make_pass_phiprop (gcc::context
*ctxt
)
465 return new pass_phiprop (ctxt
);