1*38fd1498Szrj /* Const/Copy propagation originating from degenerate PHIs
2*38fd1498Szrj Copyright (C) 2001-2018 Free Software Foundation, Inc.
3*38fd1498Szrj
4*38fd1498Szrj This file is part of GCC.
5*38fd1498Szrj
6*38fd1498Szrj GCC is free software; you can redistribute it and/or modify
7*38fd1498Szrj it under the terms of the GNU General Public License as published by
8*38fd1498Szrj the Free Software Foundation; either version 3, or (at your option)
9*38fd1498Szrj any later version.
10*38fd1498Szrj
11*38fd1498Szrj GCC is distributed in the hope that it will be useful,
12*38fd1498Szrj but WITHOUT ANY WARRANTY; without even the implied warranty of
13*38fd1498Szrj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14*38fd1498Szrj GNU General Public License for more details.
15*38fd1498Szrj
16*38fd1498Szrj You should have received a copy of the GNU General Public License
17*38fd1498Szrj along with GCC; see the file COPYING3. If not see
18*38fd1498Szrj <http://www.gnu.org/licenses/>. */
19*38fd1498Szrj
20*38fd1498Szrj #include "config.h"
21*38fd1498Szrj #include "system.h"
22*38fd1498Szrj #include "coretypes.h"
23*38fd1498Szrj #include "backend.h"
24*38fd1498Szrj #include "cfghooks.h"
25*38fd1498Szrj #include "tree.h"
26*38fd1498Szrj #include "gimple.h"
27*38fd1498Szrj #include "ssa.h"
28*38fd1498Szrj #include "fold-const.h"
29*38fd1498Szrj #include "cfgloop.h"
30*38fd1498Szrj #include "gimple-pretty-print.h"
31*38fd1498Szrj #include "gimple-fold.h"
32*38fd1498Szrj #include "tree-eh.h"
33*38fd1498Szrj #include "gimple-iterator.h"
34*38fd1498Szrj #include "tree-cfg.h"
35*38fd1498Szrj #include "tree-pass.h"
36*38fd1498Szrj #include "tree-ssa-propagate.h"
37*38fd1498Szrj
38*38fd1498Szrj
39*38fd1498Szrj /* PHI-ONLY copy and constant propagation. This pass is meant to clean
40*38fd1498Szrj up degenerate PHIs created by or exposed by jump threading. */
41*38fd1498Szrj
42*38fd1498Szrj /* Given a statement STMT, which is either a PHI node or an assignment,
43*38fd1498Szrj remove it from the IL. */
44*38fd1498Szrj
45*38fd1498Szrj static void
remove_stmt_or_phi(gimple * stmt)46*38fd1498Szrj remove_stmt_or_phi (gimple *stmt)
47*38fd1498Szrj {
48*38fd1498Szrj gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
49*38fd1498Szrj
50*38fd1498Szrj if (gimple_code (stmt) == GIMPLE_PHI)
51*38fd1498Szrj remove_phi_node (&gsi, true);
52*38fd1498Szrj else
53*38fd1498Szrj {
54*38fd1498Szrj gsi_remove (&gsi, true);
55*38fd1498Szrj release_defs (stmt);
56*38fd1498Szrj }
57*38fd1498Szrj }
58*38fd1498Szrj
59*38fd1498Szrj /* Given a statement STMT, which is either a PHI node or an assignment,
60*38fd1498Szrj return the "rhs" of the node, in the case of a non-degenerate
61*38fd1498Szrj phi, NULL is returned. */
62*38fd1498Szrj
63*38fd1498Szrj static tree
get_rhs_or_phi_arg(gimple * stmt)64*38fd1498Szrj get_rhs_or_phi_arg (gimple *stmt)
65*38fd1498Szrj {
66*38fd1498Szrj if (gimple_code (stmt) == GIMPLE_PHI)
67*38fd1498Szrj return degenerate_phi_result (as_a <gphi *> (stmt));
68*38fd1498Szrj else if (gimple_assign_single_p (stmt))
69*38fd1498Szrj return gimple_assign_rhs1 (stmt);
70*38fd1498Szrj else
71*38fd1498Szrj gcc_unreachable ();
72*38fd1498Szrj }
73*38fd1498Szrj
74*38fd1498Szrj
75*38fd1498Szrj /* Given a statement STMT, which is either a PHI node or an assignment,
76*38fd1498Szrj return the "lhs" of the node. */
77*38fd1498Szrj
78*38fd1498Szrj static tree
get_lhs_or_phi_result(gimple * stmt)79*38fd1498Szrj get_lhs_or_phi_result (gimple *stmt)
80*38fd1498Szrj {
81*38fd1498Szrj if (gimple_code (stmt) == GIMPLE_PHI)
82*38fd1498Szrj return gimple_phi_result (stmt);
83*38fd1498Szrj else if (is_gimple_assign (stmt))
84*38fd1498Szrj return gimple_assign_lhs (stmt);
85*38fd1498Szrj else
86*38fd1498Szrj gcc_unreachable ();
87*38fd1498Szrj }
88*38fd1498Szrj
89*38fd1498Szrj /* Propagate RHS into all uses of LHS (when possible).
90*38fd1498Szrj
91*38fd1498Szrj RHS and LHS are derived from STMT, which is passed in solely so
92*38fd1498Szrj that we can remove it if propagation is successful.
93*38fd1498Szrj
94*38fd1498Szrj When propagating into a PHI node or into a statement which turns
95*38fd1498Szrj into a trivial copy or constant initialization, set the
96*38fd1498Szrj appropriate bit in INTERESTING_NAMEs so that we will visit those
97*38fd1498Szrj nodes as well in an effort to pick up secondary optimization
98*38fd1498Szrj opportunities.
99*38fd1498Szrj
100*38fd1498Szrj NEED_EH_CLEANUP tracks blocks that need their EH information
101*38fd1498Szrj cleaned up after changing EH information on a statement. */
102*38fd1498Szrj
103*38fd1498Szrj static bool
propagate_rhs_into_lhs(gimple * stmt,tree lhs,tree rhs,bitmap interesting_names,bitmap need_eh_cleanup)104*38fd1498Szrj propagate_rhs_into_lhs (gimple *stmt, tree lhs, tree rhs,
105*38fd1498Szrj bitmap interesting_names, bitmap need_eh_cleanup)
106*38fd1498Szrj {
107*38fd1498Szrj bool cfg_altered = false;
108*38fd1498Szrj
109*38fd1498Szrj /* First verify that propagation is valid. */
110*38fd1498Szrj if (may_propagate_copy (lhs, rhs))
111*38fd1498Szrj {
112*38fd1498Szrj use_operand_p use_p;
113*38fd1498Szrj imm_use_iterator iter;
114*38fd1498Szrj gimple *use_stmt;
115*38fd1498Szrj bool all = true;
116*38fd1498Szrj
117*38fd1498Szrj /* Dump details. */
118*38fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
119*38fd1498Szrj {
120*38fd1498Szrj fprintf (dump_file, " Replacing '");
121*38fd1498Szrj print_generic_expr (dump_file, lhs, dump_flags);
122*38fd1498Szrj fprintf (dump_file, "' with %s '",
123*38fd1498Szrj (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable"));
124*38fd1498Szrj print_generic_expr (dump_file, rhs, dump_flags);
125*38fd1498Szrj fprintf (dump_file, "'\n");
126*38fd1498Szrj }
127*38fd1498Szrj
128*38fd1498Szrj /* Walk over every use of LHS and try to replace the use with RHS.
129*38fd1498Szrj At this point the only reason why such a propagation would not
130*38fd1498Szrj be successful would be if the use occurs in an ASM_EXPR. */
131*38fd1498Szrj FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
132*38fd1498Szrj {
133*38fd1498Szrj /* Leave debug stmts alone. If we succeed in propagating
134*38fd1498Szrj all non-debug uses, we'll drop the DEF, and propagation
135*38fd1498Szrj into debug stmts will occur then. */
136*38fd1498Szrj if (gimple_debug_bind_p (use_stmt))
137*38fd1498Szrj continue;
138*38fd1498Szrj
139*38fd1498Szrj /* It's not always safe to propagate into an ASM_EXPR. */
140*38fd1498Szrj if (gimple_code (use_stmt) == GIMPLE_ASM
141*38fd1498Szrj && ! may_propagate_copy_into_asm (lhs))
142*38fd1498Szrj {
143*38fd1498Szrj all = false;
144*38fd1498Szrj continue;
145*38fd1498Szrj }
146*38fd1498Szrj
147*38fd1498Szrj /* It's not ok to propagate into the definition stmt of RHS.
148*38fd1498Szrj <bb 9>:
149*38fd1498Szrj # prephitmp.12_36 = PHI <g_67.1_6(9)>
150*38fd1498Szrj g_67.1_6 = prephitmp.12_36;
151*38fd1498Szrj goto <bb 9>;
152*38fd1498Szrj While this is strictly all dead code we do not want to
153*38fd1498Szrj deal with this here. */
154*38fd1498Szrj if (TREE_CODE (rhs) == SSA_NAME
155*38fd1498Szrj && SSA_NAME_DEF_STMT (rhs) == use_stmt)
156*38fd1498Szrj {
157*38fd1498Szrj all = false;
158*38fd1498Szrj continue;
159*38fd1498Szrj }
160*38fd1498Szrj
161*38fd1498Szrj /* Dump details. */
162*38fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
163*38fd1498Szrj {
164*38fd1498Szrj fprintf (dump_file, " Original statement:");
165*38fd1498Szrj print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
166*38fd1498Szrj }
167*38fd1498Szrj
168*38fd1498Szrj /* Propagate the RHS into this use of the LHS. */
169*38fd1498Szrj FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
170*38fd1498Szrj propagate_value (use_p, rhs);
171*38fd1498Szrj
172*38fd1498Szrj /* Special cases to avoid useless calls into the folding
173*38fd1498Szrj routines, operand scanning, etc.
174*38fd1498Szrj
175*38fd1498Szrj Propagation into a PHI may cause the PHI to become
176*38fd1498Szrj a degenerate, so mark the PHI as interesting. No other
177*38fd1498Szrj actions are necessary. */
178*38fd1498Szrj if (gimple_code (use_stmt) == GIMPLE_PHI)
179*38fd1498Szrj {
180*38fd1498Szrj tree result;
181*38fd1498Szrj
182*38fd1498Szrj /* Dump details. */
183*38fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
184*38fd1498Szrj {
185*38fd1498Szrj fprintf (dump_file, " Updated statement:");
186*38fd1498Szrj print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
187*38fd1498Szrj }
188*38fd1498Szrj
189*38fd1498Szrj result = get_lhs_or_phi_result (use_stmt);
190*38fd1498Szrj bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
191*38fd1498Szrj continue;
192*38fd1498Szrj }
193*38fd1498Szrj
194*38fd1498Szrj /* From this point onward we are propagating into a
195*38fd1498Szrj real statement. Folding may (or may not) be possible,
196*38fd1498Szrj we may expose new operands, expose dead EH edges,
197*38fd1498Szrj etc. */
198*38fd1498Szrj /* NOTE tuples. In the tuples world, fold_stmt_inplace
199*38fd1498Szrj cannot fold a call that simplifies to a constant,
200*38fd1498Szrj because the GIMPLE_CALL must be replaced by a
201*38fd1498Szrj GIMPLE_ASSIGN, and there is no way to effect such a
202*38fd1498Szrj transformation in-place. We might want to consider
203*38fd1498Szrj using the more general fold_stmt here. */
204*38fd1498Szrj {
205*38fd1498Szrj gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
206*38fd1498Szrj fold_stmt_inplace (&gsi);
207*38fd1498Szrj }
208*38fd1498Szrj
209*38fd1498Szrj /* Sometimes propagation can expose new operands to the
210*38fd1498Szrj renamer. */
211*38fd1498Szrj update_stmt (use_stmt);
212*38fd1498Szrj
213*38fd1498Szrj /* Dump details. */
214*38fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
215*38fd1498Szrj {
216*38fd1498Szrj fprintf (dump_file, " Updated statement:");
217*38fd1498Szrj print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
218*38fd1498Szrj }
219*38fd1498Szrj
220*38fd1498Szrj /* If we replaced a variable index with a constant, then
221*38fd1498Szrj we would need to update the invariant flag for ADDR_EXPRs. */
222*38fd1498Szrj if (gimple_assign_single_p (use_stmt)
223*38fd1498Szrj && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR)
224*38fd1498Szrj recompute_tree_invariant_for_addr_expr
225*38fd1498Szrj (gimple_assign_rhs1 (use_stmt));
226*38fd1498Szrj
227*38fd1498Szrj /* If we cleaned up EH information from the statement,
228*38fd1498Szrj mark its containing block as needing EH cleanups. */
229*38fd1498Szrj if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt))
230*38fd1498Szrj {
231*38fd1498Szrj bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index);
232*38fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
233*38fd1498Szrj fprintf (dump_file, " Flagged to clear EH edges.\n");
234*38fd1498Szrj }
235*38fd1498Szrj
236*38fd1498Szrj /* Propagation may expose new trivial copy/constant propagation
237*38fd1498Szrj opportunities. */
238*38fd1498Szrj if (gimple_assign_single_p (use_stmt)
239*38fd1498Szrj && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
240*38fd1498Szrj && (TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
241*38fd1498Szrj || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt))))
242*38fd1498Szrj {
243*38fd1498Szrj tree result = get_lhs_or_phi_result (use_stmt);
244*38fd1498Szrj bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
245*38fd1498Szrj }
246*38fd1498Szrj
247*38fd1498Szrj /* Propagation into these nodes may make certain edges in
248*38fd1498Szrj the CFG unexecutable. We want to identify them as PHI nodes
249*38fd1498Szrj at the destination of those unexecutable edges may become
250*38fd1498Szrj degenerates. */
251*38fd1498Szrj else if (gimple_code (use_stmt) == GIMPLE_COND
252*38fd1498Szrj || gimple_code (use_stmt) == GIMPLE_SWITCH
253*38fd1498Szrj || gimple_code (use_stmt) == GIMPLE_GOTO)
254*38fd1498Szrj {
255*38fd1498Szrj tree val;
256*38fd1498Szrj
257*38fd1498Szrj if (gimple_code (use_stmt) == GIMPLE_COND)
258*38fd1498Szrj val = fold_binary_loc (gimple_location (use_stmt),
259*38fd1498Szrj gimple_cond_code (use_stmt),
260*38fd1498Szrj boolean_type_node,
261*38fd1498Szrj gimple_cond_lhs (use_stmt),
262*38fd1498Szrj gimple_cond_rhs (use_stmt));
263*38fd1498Szrj else if (gimple_code (use_stmt) == GIMPLE_SWITCH)
264*38fd1498Szrj val = gimple_switch_index (as_a <gswitch *> (use_stmt));
265*38fd1498Szrj else
266*38fd1498Szrj val = gimple_goto_dest (use_stmt);
267*38fd1498Szrj
268*38fd1498Szrj if (val && is_gimple_min_invariant (val))
269*38fd1498Szrj {
270*38fd1498Szrj basic_block bb = gimple_bb (use_stmt);
271*38fd1498Szrj edge te = find_taken_edge (bb, val);
272*38fd1498Szrj if (!te)
273*38fd1498Szrj continue;
274*38fd1498Szrj
275*38fd1498Szrj edge_iterator ei;
276*38fd1498Szrj edge e;
277*38fd1498Szrj gimple_stmt_iterator gsi;
278*38fd1498Szrj gphi_iterator psi;
279*38fd1498Szrj
280*38fd1498Szrj /* Remove all outgoing edges except TE. */
281*38fd1498Szrj for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));)
282*38fd1498Szrj {
283*38fd1498Szrj if (e != te)
284*38fd1498Szrj {
285*38fd1498Szrj /* Mark all the PHI nodes at the destination of
286*38fd1498Szrj the unexecutable edge as interesting. */
287*38fd1498Szrj for (psi = gsi_start_phis (e->dest);
288*38fd1498Szrj !gsi_end_p (psi);
289*38fd1498Szrj gsi_next (&psi))
290*38fd1498Szrj {
291*38fd1498Szrj gphi *phi = psi.phi ();
292*38fd1498Szrj
293*38fd1498Szrj tree result = gimple_phi_result (phi);
294*38fd1498Szrj int version = SSA_NAME_VERSION (result);
295*38fd1498Szrj
296*38fd1498Szrj bitmap_set_bit (interesting_names, version);
297*38fd1498Szrj }
298*38fd1498Szrj
299*38fd1498Szrj te->probability += e->probability;
300*38fd1498Szrj
301*38fd1498Szrj remove_edge (e);
302*38fd1498Szrj cfg_altered = true;
303*38fd1498Szrj }
304*38fd1498Szrj else
305*38fd1498Szrj ei_next (&ei);
306*38fd1498Szrj }
307*38fd1498Szrj
308*38fd1498Szrj gsi = gsi_last_bb (gimple_bb (use_stmt));
309*38fd1498Szrj gsi_remove (&gsi, true);
310*38fd1498Szrj
311*38fd1498Szrj /* And fixup the flags on the single remaining edge. */
312*38fd1498Szrj te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
313*38fd1498Szrj te->flags &= ~EDGE_ABNORMAL;
314*38fd1498Szrj te->flags |= EDGE_FALLTHRU;
315*38fd1498Szrj }
316*38fd1498Szrj }
317*38fd1498Szrj }
318*38fd1498Szrj
319*38fd1498Szrj /* Ensure there is nothing else to do. */
320*38fd1498Szrj gcc_assert (!all || has_zero_uses (lhs));
321*38fd1498Szrj
322*38fd1498Szrj /* If we were able to propagate away all uses of LHS, then
323*38fd1498Szrj we can remove STMT. */
324*38fd1498Szrj if (all)
325*38fd1498Szrj remove_stmt_or_phi (stmt);
326*38fd1498Szrj }
327*38fd1498Szrj return cfg_altered;
328*38fd1498Szrj }
329*38fd1498Szrj
330*38fd1498Szrj /* STMT is either a PHI node (potentially a degenerate PHI node) or
331*38fd1498Szrj a statement that is a trivial copy or constant initialization.
332*38fd1498Szrj
333*38fd1498Szrj Attempt to eliminate STMT by propagating its RHS into all uses of
334*38fd1498Szrj its LHS. This may in turn set new bits in INTERESTING_NAMES
335*38fd1498Szrj for nodes we want to revisit later.
336*38fd1498Szrj
337*38fd1498Szrj All exit paths should clear INTERESTING_NAMES for the result
338*38fd1498Szrj of STMT.
339*38fd1498Szrj
340*38fd1498Szrj NEED_EH_CLEANUP tracks blocks that need their EH information
341*38fd1498Szrj cleaned up after changing EH information on a statement. It is
342*38fd1498Szrj not set or queried here, but passed along to children. */
343*38fd1498Szrj
344*38fd1498Szrj static bool
eliminate_const_or_copy(gimple * stmt,bitmap interesting_names,bitmap need_eh_cleanup)345*38fd1498Szrj eliminate_const_or_copy (gimple *stmt, bitmap interesting_names,
346*38fd1498Szrj bitmap need_eh_cleanup)
347*38fd1498Szrj {
348*38fd1498Szrj tree lhs = get_lhs_or_phi_result (stmt);
349*38fd1498Szrj tree rhs;
350*38fd1498Szrj int version = SSA_NAME_VERSION (lhs);
351*38fd1498Szrj bool cfg_altered = false;
352*38fd1498Szrj
353*38fd1498Szrj /* If the LHS of this statement or PHI has no uses, then we can
354*38fd1498Szrj just eliminate it. This can occur if, for example, the PHI
355*38fd1498Szrj was created by block duplication due to threading and its only
356*38fd1498Szrj use was in the conditional at the end of the block which was
357*38fd1498Szrj deleted. */
358*38fd1498Szrj if (has_zero_uses (lhs))
359*38fd1498Szrj {
360*38fd1498Szrj bitmap_clear_bit (interesting_names, version);
361*38fd1498Szrj remove_stmt_or_phi (stmt);
362*38fd1498Szrj return cfg_altered;
363*38fd1498Szrj }
364*38fd1498Szrj
365*38fd1498Szrj /* Get the RHS of the assignment or PHI node if the PHI is a
366*38fd1498Szrj degenerate. */
367*38fd1498Szrj rhs = get_rhs_or_phi_arg (stmt);
368*38fd1498Szrj if (!rhs)
369*38fd1498Szrj {
370*38fd1498Szrj bitmap_clear_bit (interesting_names, version);
371*38fd1498Szrj return cfg_altered;
372*38fd1498Szrj }
373*38fd1498Szrj
374*38fd1498Szrj if (!virtual_operand_p (lhs))
375*38fd1498Szrj cfg_altered = propagate_rhs_into_lhs (stmt, lhs, rhs,
376*38fd1498Szrj interesting_names, need_eh_cleanup);
377*38fd1498Szrj else
378*38fd1498Szrj {
379*38fd1498Szrj gimple *use_stmt;
380*38fd1498Szrj imm_use_iterator iter;
381*38fd1498Szrj use_operand_p use_p;
382*38fd1498Szrj /* For virtual operands we have to propagate into all uses as
383*38fd1498Szrj otherwise we will create overlapping life-ranges. */
384*38fd1498Szrj FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
385*38fd1498Szrj FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
386*38fd1498Szrj SET_USE (use_p, rhs);
387*38fd1498Szrj if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
388*38fd1498Szrj SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs) = 1;
389*38fd1498Szrj remove_stmt_or_phi (stmt);
390*38fd1498Szrj }
391*38fd1498Szrj
392*38fd1498Szrj /* Note that STMT may well have been deleted by now, so do
393*38fd1498Szrj not access it, instead use the saved version # to clear
394*38fd1498Szrj T's entry in the worklist. */
395*38fd1498Szrj bitmap_clear_bit (interesting_names, version);
396*38fd1498Szrj return cfg_altered;
397*38fd1498Szrj }
398*38fd1498Szrj
399*38fd1498Szrj /* The first phase in degenerate PHI elimination.
400*38fd1498Szrj
401*38fd1498Szrj Eliminate the degenerate PHIs in BB, then recurse on the
402*38fd1498Szrj dominator children of BB.
403*38fd1498Szrj
404*38fd1498Szrj INTERESTING_NAMES tracks SSA_NAMEs that we may want to revisit
405*38fd1498Szrj in the future. It is not set or queried here, but passed along
406*38fd1498Szrj to children.
407*38fd1498Szrj
408*38fd1498Szrj NEED_EH_CLEANUP tracks blocks that need their EH information
409*38fd1498Szrj cleaned up after changing EH information on a statement. It is
410*38fd1498Szrj not set or queried here, but passed along to children. */
411*38fd1498Szrj
412*38fd1498Szrj static bool
eliminate_degenerate_phis_1(basic_block bb,bitmap interesting_names,bitmap need_eh_cleanup)413*38fd1498Szrj eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names,
414*38fd1498Szrj bitmap need_eh_cleanup)
415*38fd1498Szrj {
416*38fd1498Szrj gphi_iterator gsi;
417*38fd1498Szrj basic_block son;
418*38fd1498Szrj bool cfg_altered = false;
419*38fd1498Szrj
420*38fd1498Szrj for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);)
421*38fd1498Szrj {
422*38fd1498Szrj gphi *phi = gsi.phi ();
423*38fd1498Szrj /* We might end up removing PHI so advance the iterator now. */
424*38fd1498Szrj gsi_next (&gsi);
425*38fd1498Szrj cfg_altered |= eliminate_const_or_copy (phi, interesting_names,
426*38fd1498Szrj need_eh_cleanup);
427*38fd1498Szrj }
428*38fd1498Szrj
429*38fd1498Szrj /* Recurse into the dominator children of BB. */
430*38fd1498Szrj for (son = first_dom_son (CDI_DOMINATORS, bb);
431*38fd1498Szrj son;
432*38fd1498Szrj son = next_dom_son (CDI_DOMINATORS, son))
433*38fd1498Szrj cfg_altered |= eliminate_degenerate_phis_1 (son, interesting_names,
434*38fd1498Szrj need_eh_cleanup);
435*38fd1498Szrj
436*38fd1498Szrj return cfg_altered;
437*38fd1498Szrj }
438*38fd1498Szrj
439*38fd1498Szrj
440*38fd1498Szrj /* A very simple pass to eliminate degenerate PHI nodes from the
441*38fd1498Szrj IL. This is meant to be fast enough to be able to be run several
442*38fd1498Szrj times in the optimization pipeline.
443*38fd1498Szrj
444*38fd1498Szrj Certain optimizations, particularly those which duplicate blocks
445*38fd1498Szrj or remove edges from the CFG can create or expose PHIs which are
446*38fd1498Szrj trivial copies or constant initializations.
447*38fd1498Szrj
448*38fd1498Szrj While we could pick up these optimizations in DOM or with the
449*38fd1498Szrj combination of copy-prop and CCP, those solutions are far too
450*38fd1498Szrj heavy-weight for our needs.
451*38fd1498Szrj
452*38fd1498Szrj This implementation has two phases so that we can efficiently
453*38fd1498Szrj eliminate the first order degenerate PHIs and second order
454*38fd1498Szrj degenerate PHIs.
455*38fd1498Szrj
456*38fd1498Szrj The first phase performs a dominator walk to identify and eliminate
457*38fd1498Szrj the vast majority of the degenerate PHIs. When a degenerate PHI
458*38fd1498Szrj is identified and eliminated any affected statements or PHIs
459*38fd1498Szrj are put on a worklist.
460*38fd1498Szrj
461*38fd1498Szrj The second phase eliminates degenerate PHIs and trivial copies
462*38fd1498Szrj or constant initializations using the worklist. This is how we
463*38fd1498Szrj pick up the secondary optimization opportunities with minimal
464*38fd1498Szrj cost. */
465*38fd1498Szrj
466*38fd1498Szrj namespace {
467*38fd1498Szrj
468*38fd1498Szrj const pass_data pass_data_phi_only_cprop =
469*38fd1498Szrj {
470*38fd1498Szrj GIMPLE_PASS, /* type */
471*38fd1498Szrj "phicprop", /* name */
472*38fd1498Szrj OPTGROUP_NONE, /* optinfo_flags */
473*38fd1498Szrj TV_TREE_PHI_CPROP, /* tv_id */
474*38fd1498Szrj ( PROP_cfg | PROP_ssa ), /* properties_required */
475*38fd1498Szrj 0, /* properties_provided */
476*38fd1498Szrj 0, /* properties_destroyed */
477*38fd1498Szrj 0, /* todo_flags_start */
478*38fd1498Szrj ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */
479*38fd1498Szrj };
480*38fd1498Szrj
481*38fd1498Szrj class pass_phi_only_cprop : public gimple_opt_pass
482*38fd1498Szrj {
483*38fd1498Szrj public:
pass_phi_only_cprop(gcc::context * ctxt)484*38fd1498Szrj pass_phi_only_cprop (gcc::context *ctxt)
485*38fd1498Szrj : gimple_opt_pass (pass_data_phi_only_cprop, ctxt)
486*38fd1498Szrj {}
487*38fd1498Szrj
488*38fd1498Szrj /* opt_pass methods: */
clone()489*38fd1498Szrj opt_pass * clone () { return new pass_phi_only_cprop (m_ctxt); }
gate(function *)490*38fd1498Szrj virtual bool gate (function *) { return flag_tree_dom != 0; }
491*38fd1498Szrj virtual unsigned int execute (function *);
492*38fd1498Szrj
493*38fd1498Szrj }; // class pass_phi_only_cprop
494*38fd1498Szrj
495*38fd1498Szrj unsigned int
execute(function * fun)496*38fd1498Szrj pass_phi_only_cprop::execute (function *fun)
497*38fd1498Szrj {
498*38fd1498Szrj bool cfg_altered = false;
499*38fd1498Szrj
500*38fd1498Szrj /* Bitmap of blocks which need EH information updated. We can not
501*38fd1498Szrj update it on-the-fly as doing so invalidates the dominator tree. */
502*38fd1498Szrj auto_bitmap need_eh_cleanup;
503*38fd1498Szrj
504*38fd1498Szrj /* INTERESTING_NAMES is effectively our worklist, indexed by
505*38fd1498Szrj SSA_NAME_VERSION.
506*38fd1498Szrj
507*38fd1498Szrj A set bit indicates that the statement or PHI node which
508*38fd1498Szrj defines the SSA_NAME should be (re)examined to determine if
509*38fd1498Szrj it has become a degenerate PHI or trivial const/copy propagation
510*38fd1498Szrj opportunity.
511*38fd1498Szrj
512*38fd1498Szrj Experiments have show we generally get better compilation
513*38fd1498Szrj time behavior with bitmaps rather than sbitmaps. */
514*38fd1498Szrj auto_bitmap interesting_names;
515*38fd1498Szrj auto_bitmap interesting_names1;
516*38fd1498Szrj
517*38fd1498Szrj calculate_dominance_info (CDI_DOMINATORS);
518*38fd1498Szrj cfg_altered = false;
519*38fd1498Szrj
520*38fd1498Szrj /* First phase. Eliminate degenerate PHIs via a dominator
521*38fd1498Szrj walk of the CFG.
522*38fd1498Szrj
523*38fd1498Szrj Experiments have indicated that we generally get better
524*38fd1498Szrj compile-time behavior by visiting blocks in the first
525*38fd1498Szrj phase in dominator order. Presumably this is because walking
526*38fd1498Szrj in dominator order leaves fewer PHIs for later examination
527*38fd1498Szrj by the worklist phase. */
528*38fd1498Szrj cfg_altered = eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR_FOR_FN (fun),
529*38fd1498Szrj interesting_names,
530*38fd1498Szrj need_eh_cleanup);
531*38fd1498Szrj
532*38fd1498Szrj /* Second phase. Eliminate second order degenerate PHIs as well
533*38fd1498Szrj as trivial copies or constant initializations identified by
534*38fd1498Szrj the first phase or this phase. Basically we keep iterating
535*38fd1498Szrj until our set of INTERESTING_NAMEs is empty. */
536*38fd1498Szrj while (!bitmap_empty_p (interesting_names))
537*38fd1498Szrj {
538*38fd1498Szrj unsigned int i;
539*38fd1498Szrj bitmap_iterator bi;
540*38fd1498Szrj
541*38fd1498Szrj /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap
542*38fd1498Szrj changed during the loop. Copy it to another bitmap and
543*38fd1498Szrj use that. */
544*38fd1498Szrj bitmap_copy (interesting_names1, interesting_names);
545*38fd1498Szrj
546*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi)
547*38fd1498Szrj {
548*38fd1498Szrj tree name = ssa_name (i);
549*38fd1498Szrj
550*38fd1498Szrj /* Ignore SSA_NAMEs that have been released because
551*38fd1498Szrj their defining statement was deleted (unreachable). */
552*38fd1498Szrj if (name)
553*38fd1498Szrj cfg_altered
554*38fd1498Szrj |= eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)),
555*38fd1498Szrj interesting_names, need_eh_cleanup);
556*38fd1498Szrj }
557*38fd1498Szrj }
558*38fd1498Szrj
559*38fd1498Szrj if (cfg_altered)
560*38fd1498Szrj {
561*38fd1498Szrj free_dominance_info (CDI_DOMINATORS);
562*38fd1498Szrj /* If we changed the CFG schedule loops for fixup by cfgcleanup. */
563*38fd1498Szrj loops_state_set (LOOPS_NEED_FIXUP);
564*38fd1498Szrj }
565*38fd1498Szrj
566*38fd1498Szrj /* Propagation of const and copies may make some EH edges dead. Purge
567*38fd1498Szrj such edges from the CFG as needed. */
568*38fd1498Szrj if (!bitmap_empty_p (need_eh_cleanup))
569*38fd1498Szrj gimple_purge_all_dead_eh_edges (need_eh_cleanup);
570*38fd1498Szrj
571*38fd1498Szrj return 0;
572*38fd1498Szrj }
573*38fd1498Szrj
574*38fd1498Szrj } // anon namespace
575*38fd1498Szrj
576*38fd1498Szrj gimple_opt_pass *
make_pass_phi_only_cprop(gcc::context * ctxt)577*38fd1498Szrj make_pass_phi_only_cprop (gcc::context *ctxt)
578*38fd1498Szrj {
579*38fd1498Szrj return new pass_phi_only_cprop (ctxt);
580*38fd1498Szrj }
581