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>
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"
29 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-pass.h"
34 #include "tree-dump.h"
35 #include "langhooks.h"
38 /* This pass propagates indirect loads through the PHI node for its
39 address to make the load source possiby non-addressable and to
40 allow for PHI optimization to trigger.
42 For example the pass changes
44 # addr_1 = PHI <&a, &b>
51 but also handles more complex cenarios like
53 D.2077_2 = &this_1(D)->a1;
56 # b_12 = PHI <&c(2), D.2077_2(3)>
60 # b_15 = PHI <b_12(4), &b(5)>
61 D.2080_5 = &this_1(D)->a0;
64 # b_18 = PHI <D.2080_5(6), &c(7)>
67 # b_21 = PHI <b_15(8), b_18(9)>
70 where the addresses loaded are defined by PHIs itself.
73 std::max(std::min(a0, c), std::min(std::max(a1, c), b))
75 where this pass transforms it to a form later PHI optimization
76 recognizes and transforms it to the simple
78 D.2109_10 = this_1(D)->a1;
80 D.2114_31 = MAX_EXPR <D.2109_10, D.2110_11>;
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>;
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. */
92 /* Structure to keep track of the value of a dereferenced PHI result
93 and the set of virtual operands used for that dereference. */
101 /* Verify if the value recorded for NAME in PHIVN is still valid at
102 the start of basic block BB. */
105 phivn_valid_p (struct phiprop_d
*phivn
, tree name
, basic_block bb
)
107 tree vop_stmt
= phivn
[SSA_NAME_VERSION (name
)].vop_stmt
;
111 /* The def stmts of all virtual uses need to be post-dominated
113 FOR_EACH_SSA_TREE_OPERAND (vuse
, vop_stmt
, ui
, SSA_OP_VUSE
)
116 imm_use_iterator ui2
;
119 FOR_EACH_IMM_USE_STMT (use_stmt
, ui2
, vuse
)
121 /* If BB does not dominate a VDEF, the value is invalid. */
122 if (((TREE_CODE (use_stmt
) == GIMPLE_MODIFY_STMT
123 && !ZERO_SSA_OPERANDS (use_stmt
, SSA_OP_VDEF
))
124 || TREE_CODE (use_stmt
) == PHI_NODE
)
125 && !dominated_by_p (CDI_DOMINATORS
, bb_for_stmt (use_stmt
), bb
))
128 BREAK_FROM_IMM_USE_STMT (ui2
);
138 /* Insert a new phi node for the dereference of PHI at basic_block
139 BB with the virtual operands from USE_STMT. */
142 phiprop_insert_phi (basic_block bb
, tree phi
, tree use_stmt
,
143 struct phiprop_d
*phivn
, size_t n
)
149 /* Build a new PHI node to replace the definition of
150 the indirect reference lhs. */
151 res
= GIMPLE_STMT_OPERAND (use_stmt
, 0);
152 SSA_NAME_DEF_STMT (res
) = new_phi
= create_phi_node (res
, bb
);
154 /* Add PHI arguments for each edge inserting loads of the
155 addressable operands. */
156 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
158 tree old_arg
, new_var
, tmp
;
160 old_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
161 while (TREE_CODE (old_arg
) == SSA_NAME
162 && (SSA_NAME_VERSION (old_arg
) >= n
163 || phivn
[SSA_NAME_VERSION (old_arg
)].value
== NULL_TREE
))
165 tree def_stmt
= SSA_NAME_DEF_STMT (old_arg
);
166 old_arg
= GIMPLE_STMT_OPERAND (def_stmt
, 1);
169 if (TREE_CODE (old_arg
) == SSA_NAME
)
170 /* Reuse a formerly created dereference. */
171 new_var
= phivn
[SSA_NAME_VERSION (old_arg
)].value
;
174 old_arg
= TREE_OPERAND (old_arg
, 0);
175 new_var
= create_tmp_var (TREE_TYPE (old_arg
), NULL
);
176 tmp
= build2 (GIMPLE_MODIFY_STMT
, void_type_node
,
177 NULL_TREE
, unshare_expr (old_arg
));
178 if (TREE_CODE (TREE_TYPE (old_arg
)) == COMPLEX_TYPE
179 || TREE_CODE (TREE_TYPE (old_arg
)) == VECTOR_TYPE
)
180 DECL_GIMPLE_REG_P (new_var
) = 1;
181 add_referenced_var (new_var
);
182 new_var
= make_ssa_name (new_var
, tmp
);
183 GIMPLE_STMT_OPERAND (tmp
, 0) = new_var
;
185 bsi_insert_on_edge (e
, tmp
);
188 mark_symbols_for_renaming (tmp
);
191 add_phi_arg (new_phi
, new_var
, e
);
194 update_stmt (new_phi
);
199 /* Propagate between the phi node arguments of PHI in BB and phi result
200 users. For now this matches
208 Returns true if a transformation was done and edge insertions
209 need to be committed. Global data PHIVN and N is used to track
210 past transformation results. We need to be especially careful here
211 with aliasing issues as we are moving memory reads. */
214 propagate_with_phi (basic_block bb
, tree phi
, struct phiprop_d
*phivn
, size_t n
)
216 tree ptr
= PHI_RESULT (phi
);
217 tree use_stmt
, res
= NULL_TREE
;
218 block_stmt_iterator bsi
;
220 use_operand_p arg_p
, use
;
224 if (MTAG_P (SSA_NAME_VAR (ptr
))
225 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
226 || !is_gimple_reg_type (TREE_TYPE (TREE_TYPE (ptr
))))
229 /* Check if we can "cheaply" dereference all phi arguments. */
230 FOR_EACH_PHI_ARG (arg_p
, phi
, i
, SSA_OP_USE
)
232 tree arg
= USE_FROM_PTR (arg_p
);
233 /* Walk the ssa chain until we reach a ssa name we already
234 created a value for or we reach a definition of the form
235 ssa_name_n = &var; */
236 while (TREE_CODE (arg
) == SSA_NAME
237 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
238 && (SSA_NAME_VERSION (arg
) >= n
239 || phivn
[SSA_NAME_VERSION (arg
)].value
== NULL_TREE
))
241 tree def_stmt
= SSA_NAME_DEF_STMT (arg
);
242 if (TREE_CODE (def_stmt
) != GIMPLE_MODIFY_STMT
)
244 arg
= GIMPLE_STMT_OPERAND (def_stmt
, 1);
246 if ((TREE_CODE (arg
) != ADDR_EXPR
247 /* Avoid to have to decay *&a to a[0] later. */
248 || !is_gimple_reg_type (TREE_TYPE (TREE_OPERAND (arg
, 0))))
249 && !(TREE_CODE (arg
) == SSA_NAME
250 && phivn
[SSA_NAME_VERSION (arg
)].value
!= NULL_TREE
251 && phivn_valid_p (phivn
, arg
, bb
)))
255 /* Find a dereferencing use. First follow (single use) ssa
256 copy chains for ptr. */
257 while (single_imm_use (ptr
, &use
, &use_stmt
)
258 && TREE_CODE (use_stmt
) == GIMPLE_MODIFY_STMT
259 && GIMPLE_STMT_OPERAND (use_stmt
, 1) == ptr
260 && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 0)) == SSA_NAME
)
261 ptr
= GIMPLE_STMT_OPERAND (use_stmt
, 0);
263 /* Replace the first dereference of *ptr if there is one and if we
264 can move the loads to the place of the ptr phi node. */
265 phi_inserted
= false;
266 FOR_EACH_IMM_USE_STMT (use_stmt
, ui
, ptr
)
271 /* Check whether this is a load of *ptr. */
272 if (!(TREE_CODE (use_stmt
) == GIMPLE_MODIFY_STMT
273 && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 0)) == SSA_NAME
274 && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 1)) == INDIRECT_REF
275 && TREE_OPERAND (GIMPLE_STMT_OPERAND (use_stmt
, 1), 0) == ptr
276 /* We cannot replace a load that may throw or is volatile. */
277 && !tree_can_throw_internal (use_stmt
)))
280 /* Check if we can move the loads. The def stmts of all virtual uses
281 need to be post-dominated by bb. */
282 FOR_EACH_SSA_TREE_OPERAND (vuse
, use_stmt
, ui2
, SSA_OP_VUSE
)
284 tree def_stmt
= SSA_NAME_DEF_STMT (vuse
);
285 if (!SSA_NAME_IS_DEFAULT_DEF (vuse
)
286 && (bb_for_stmt (def_stmt
) == bb
287 || !dominated_by_p (CDI_DOMINATORS
,
288 bb
, bb_for_stmt (def_stmt
))))
292 /* Found a proper dereference. Insert a phi node if this
293 is the first load transformation. */
296 res
= phiprop_insert_phi (bb
, phi
, use_stmt
, phivn
, n
);
298 /* Remember the value we created for *ptr. */
299 phivn
[SSA_NAME_VERSION (ptr
)].value
= res
;
300 phivn
[SSA_NAME_VERSION (ptr
)].vop_stmt
= use_stmt
;
302 /* Remove old stmt. The phi is taken care of by DCE, if we
303 want to delete it here we also have to delete all intermediate
305 bsi
= bsi_for_stmt (use_stmt
);
306 bsi_remove (&bsi
, 0);
312 /* Further replacements are easy, just make a copy out of the
314 GIMPLE_STMT_OPERAND (use_stmt
, 1) = res
;
315 update_stmt (use_stmt
);
319 /* Continue searching for a proper dereference. */
325 /* Helper walking the dominator tree starting from BB and processing
326 phi nodes with global data PHIVN and N. */
329 tree_ssa_phiprop_1 (basic_block bb
, struct phiprop_d
*phivn
, size_t n
)
331 bool did_something
= false;
335 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
336 did_something
|= propagate_with_phi (bb
, phi
, phivn
, n
);
338 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
340 son
= next_dom_son (CDI_DOMINATORS
, son
))
341 did_something
|= tree_ssa_phiprop_1 (son
, phivn
, n
);
343 return did_something
;
346 /* Main entry for phiprop pass. */
349 tree_ssa_phiprop (void)
351 struct phiprop_d
*phivn
;
353 calculate_dominance_info (CDI_DOMINATORS
);
355 phivn
= XCNEWVEC (struct phiprop_d
, num_ssa_names
);
357 if (tree_ssa_phiprop_1 (ENTRY_BLOCK_PTR
, phivn
, num_ssa_names
))
358 bsi_commit_edge_inserts ();
371 struct tree_opt_pass pass_phiprop
= {
372 "phiprop", /* name */
373 gate_phiprop
, /* gate */
374 tree_ssa_phiprop
, /* execute */
377 0, /* static_pass_number */
378 TV_TREE_PHIPROP
, /* tv_id */
379 PROP_cfg
| PROP_ssa
, /* properties_required */
380 0, /* properties_provided */
381 0, /* properties_destroyed */
382 0, /* todo_flags_start */
386 | TODO_verify_ssa
, /* todo_flags_finish */