1*38fd1498Szrj /* Code sinking for trees
2*38fd1498Szrj Copyright (C) 2001-2018 Free Software Foundation, Inc.
3*38fd1498Szrj Contributed by Daniel Berlin <dan@dberlin.org>
4*38fd1498Szrj
5*38fd1498Szrj This file is part of GCC.
6*38fd1498Szrj
7*38fd1498Szrj GCC is free software; you can redistribute it and/or modify
8*38fd1498Szrj it under the terms of the GNU General Public License as published by
9*38fd1498Szrj the Free Software Foundation; either version 3, or (at your option)
10*38fd1498Szrj any later version.
11*38fd1498Szrj
12*38fd1498Szrj GCC is distributed in the hope that it will be useful,
13*38fd1498Szrj but WITHOUT ANY WARRANTY; without even the implied warranty of
14*38fd1498Szrj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15*38fd1498Szrj GNU General Public License for more details.
16*38fd1498Szrj
17*38fd1498Szrj You should have received a copy of the GNU General Public License
18*38fd1498Szrj along with GCC; see the file COPYING3. If not see
19*38fd1498Szrj <http://www.gnu.org/licenses/>. */
20*38fd1498Szrj
21*38fd1498Szrj #include "config.h"
22*38fd1498Szrj #include "system.h"
23*38fd1498Szrj #include "coretypes.h"
24*38fd1498Szrj #include "backend.h"
25*38fd1498Szrj #include "tree.h"
26*38fd1498Szrj #include "gimple.h"
27*38fd1498Szrj #include "cfghooks.h"
28*38fd1498Szrj #include "tree-pass.h"
29*38fd1498Szrj #include "ssa.h"
30*38fd1498Szrj #include "gimple-pretty-print.h"
31*38fd1498Szrj #include "fold-const.h"
32*38fd1498Szrj #include "stor-layout.h"
33*38fd1498Szrj #include "cfganal.h"
34*38fd1498Szrj #include "gimple-iterator.h"
35*38fd1498Szrj #include "tree-cfg.h"
36*38fd1498Szrj #include "cfgloop.h"
37*38fd1498Szrj #include "params.h"
38*38fd1498Szrj
39*38fd1498Szrj /* TODO:
40*38fd1498Szrj 1. Sinking store only using scalar promotion (IE without moving the RHS):
41*38fd1498Szrj
42*38fd1498Szrj *q = p;
43*38fd1498Szrj p = p + 1;
44*38fd1498Szrj if (something)
45*38fd1498Szrj *q = <not p>;
46*38fd1498Szrj else
47*38fd1498Szrj y = *q;
48*38fd1498Szrj
49*38fd1498Szrj
50*38fd1498Szrj should become
51*38fd1498Szrj sinktemp = p;
52*38fd1498Szrj p = p + 1;
53*38fd1498Szrj if (something)
54*38fd1498Szrj *q = <not p>;
55*38fd1498Szrj else
56*38fd1498Szrj {
57*38fd1498Szrj *q = sinktemp;
58*38fd1498Szrj y = *q
59*38fd1498Szrj }
60*38fd1498Szrj Store copy propagation will take care of the store elimination above.
61*38fd1498Szrj
62*38fd1498Szrj
63*38fd1498Szrj 2. Sinking using Partial Dead Code Elimination. */
64*38fd1498Szrj
65*38fd1498Szrj
66*38fd1498Szrj static struct
67*38fd1498Szrj {
68*38fd1498Szrj /* The number of statements sunk down the flowgraph by code sinking. */
69*38fd1498Szrj int sunk;
70*38fd1498Szrj
71*38fd1498Szrj } sink_stats;
72*38fd1498Szrj
73*38fd1498Szrj
74*38fd1498Szrj /* Given a PHI, and one of its arguments (DEF), find the edge for
75*38fd1498Szrj that argument and return it. If the argument occurs twice in the PHI node,
76*38fd1498Szrj we return NULL. */
77*38fd1498Szrj
78*38fd1498Szrj static basic_block
find_bb_for_arg(gphi * phi,tree def)79*38fd1498Szrj find_bb_for_arg (gphi *phi, tree def)
80*38fd1498Szrj {
81*38fd1498Szrj size_t i;
82*38fd1498Szrj bool foundone = false;
83*38fd1498Szrj basic_block result = NULL;
84*38fd1498Szrj for (i = 0; i < gimple_phi_num_args (phi); i++)
85*38fd1498Szrj if (PHI_ARG_DEF (phi, i) == def)
86*38fd1498Szrj {
87*38fd1498Szrj if (foundone)
88*38fd1498Szrj return NULL;
89*38fd1498Szrj foundone = true;
90*38fd1498Szrj result = gimple_phi_arg_edge (phi, i)->src;
91*38fd1498Szrj }
92*38fd1498Szrj return result;
93*38fd1498Szrj }
94*38fd1498Szrj
95*38fd1498Szrj /* When the first immediate use is in a statement, then return true if all
96*38fd1498Szrj immediate uses in IMM are in the same statement.
97*38fd1498Szrj We could also do the case where the first immediate use is in a phi node,
98*38fd1498Szrj and all the other uses are in phis in the same basic block, but this
99*38fd1498Szrj requires some expensive checking later (you have to make sure no def/vdef
100*38fd1498Szrj in the statement occurs for multiple edges in the various phi nodes it's
101*38fd1498Szrj used in, so that you only have one place you can sink it to. */
102*38fd1498Szrj
103*38fd1498Szrj static bool
all_immediate_uses_same_place(def_operand_p def_p)104*38fd1498Szrj all_immediate_uses_same_place (def_operand_p def_p)
105*38fd1498Szrj {
106*38fd1498Szrj tree var = DEF_FROM_PTR (def_p);
107*38fd1498Szrj imm_use_iterator imm_iter;
108*38fd1498Szrj use_operand_p use_p;
109*38fd1498Szrj
110*38fd1498Szrj gimple *firstuse = NULL;
111*38fd1498Szrj FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
112*38fd1498Szrj {
113*38fd1498Szrj if (is_gimple_debug (USE_STMT (use_p)))
114*38fd1498Szrj continue;
115*38fd1498Szrj if (firstuse == NULL)
116*38fd1498Szrj firstuse = USE_STMT (use_p);
117*38fd1498Szrj else
118*38fd1498Szrj if (firstuse != USE_STMT (use_p))
119*38fd1498Szrj return false;
120*38fd1498Szrj }
121*38fd1498Szrj
122*38fd1498Szrj return true;
123*38fd1498Szrj }
124*38fd1498Szrj
125*38fd1498Szrj /* Find the nearest common dominator of all of the immediate uses in IMM. */
126*38fd1498Szrj
127*38fd1498Szrj static basic_block
nearest_common_dominator_of_uses(def_operand_p def_p,bool * debug_stmts)128*38fd1498Szrj nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts)
129*38fd1498Szrj {
130*38fd1498Szrj tree var = DEF_FROM_PTR (def_p);
131*38fd1498Szrj auto_bitmap blocks;
132*38fd1498Szrj basic_block commondom;
133*38fd1498Szrj unsigned int j;
134*38fd1498Szrj bitmap_iterator bi;
135*38fd1498Szrj imm_use_iterator imm_iter;
136*38fd1498Szrj use_operand_p use_p;
137*38fd1498Szrj
138*38fd1498Szrj FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
139*38fd1498Szrj {
140*38fd1498Szrj gimple *usestmt = USE_STMT (use_p);
141*38fd1498Szrj basic_block useblock;
142*38fd1498Szrj
143*38fd1498Szrj if (gphi *phi = dyn_cast <gphi *> (usestmt))
144*38fd1498Szrj {
145*38fd1498Szrj int idx = PHI_ARG_INDEX_FROM_USE (use_p);
146*38fd1498Szrj
147*38fd1498Szrj useblock = gimple_phi_arg_edge (phi, idx)->src;
148*38fd1498Szrj }
149*38fd1498Szrj else if (is_gimple_debug (usestmt))
150*38fd1498Szrj {
151*38fd1498Szrj *debug_stmts = true;
152*38fd1498Szrj continue;
153*38fd1498Szrj }
154*38fd1498Szrj else
155*38fd1498Szrj {
156*38fd1498Szrj useblock = gimple_bb (usestmt);
157*38fd1498Szrj }
158*38fd1498Szrj
159*38fd1498Szrj /* Short circuit. Nothing dominates the entry block. */
160*38fd1498Szrj if (useblock == ENTRY_BLOCK_PTR_FOR_FN (cfun))
161*38fd1498Szrj return NULL;
162*38fd1498Szrj
163*38fd1498Szrj bitmap_set_bit (blocks, useblock->index);
164*38fd1498Szrj }
165*38fd1498Szrj commondom = BASIC_BLOCK_FOR_FN (cfun, bitmap_first_set_bit (blocks));
166*38fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
167*38fd1498Szrj commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
168*38fd1498Szrj BASIC_BLOCK_FOR_FN (cfun, j));
169*38fd1498Szrj return commondom;
170*38fd1498Szrj }
171*38fd1498Szrj
172*38fd1498Szrj /* Given EARLY_BB and LATE_BB, two blocks in a path through the dominator
173*38fd1498Szrj tree, return the best basic block between them (inclusive) to place
174*38fd1498Szrj statements.
175*38fd1498Szrj
176*38fd1498Szrj We want the most control dependent block in the shallowest loop nest.
177*38fd1498Szrj
178*38fd1498Szrj If the resulting block is in a shallower loop nest, then use it. Else
179*38fd1498Szrj only use the resulting block if it has significantly lower execution
180*38fd1498Szrj frequency than EARLY_BB to avoid gratutious statement movement. We
181*38fd1498Szrj consider statements with VOPS more desirable to move.
182*38fd1498Szrj
183*38fd1498Szrj This pass would obviously benefit from PDO as it utilizes block
184*38fd1498Szrj frequencies. It would also benefit from recomputing frequencies
185*38fd1498Szrj if profile data is not available since frequencies often get out
186*38fd1498Szrj of sync with reality. */
187*38fd1498Szrj
188*38fd1498Szrj static basic_block
select_best_block(basic_block early_bb,basic_block late_bb,gimple * stmt)189*38fd1498Szrj select_best_block (basic_block early_bb,
190*38fd1498Szrj basic_block late_bb,
191*38fd1498Szrj gimple *stmt)
192*38fd1498Szrj {
193*38fd1498Szrj basic_block best_bb = late_bb;
194*38fd1498Szrj basic_block temp_bb = late_bb;
195*38fd1498Szrj int threshold;
196*38fd1498Szrj
197*38fd1498Szrj while (temp_bb != early_bb)
198*38fd1498Szrj {
199*38fd1498Szrj /* If we've moved into a lower loop nest, then that becomes
200*38fd1498Szrj our best block. */
201*38fd1498Szrj if (bb_loop_depth (temp_bb) < bb_loop_depth (best_bb))
202*38fd1498Szrj best_bb = temp_bb;
203*38fd1498Szrj
204*38fd1498Szrj /* Walk up the dominator tree, hopefully we'll find a shallower
205*38fd1498Szrj loop nest. */
206*38fd1498Szrj temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb);
207*38fd1498Szrj }
208*38fd1498Szrj
209*38fd1498Szrj /* If we found a shallower loop nest, then we always consider that
210*38fd1498Szrj a win. This will always give us the most control dependent block
211*38fd1498Szrj within that loop nest. */
212*38fd1498Szrj if (bb_loop_depth (best_bb) < bb_loop_depth (early_bb))
213*38fd1498Szrj return best_bb;
214*38fd1498Szrj
215*38fd1498Szrj /* Get the sinking threshold. If the statement to be moved has memory
216*38fd1498Szrj operands, then increase the threshold by 7% as those are even more
217*38fd1498Szrj profitable to avoid, clamping at 100%. */
218*38fd1498Szrj threshold = PARAM_VALUE (PARAM_SINK_FREQUENCY_THRESHOLD);
219*38fd1498Szrj if (gimple_vuse (stmt) || gimple_vdef (stmt))
220*38fd1498Szrj {
221*38fd1498Szrj threshold += 7;
222*38fd1498Szrj if (threshold > 100)
223*38fd1498Szrj threshold = 100;
224*38fd1498Szrj }
225*38fd1498Szrj
226*38fd1498Szrj /* If BEST_BB is at the same nesting level, then require it to have
227*38fd1498Szrj significantly lower execution frequency to avoid gratutious movement. */
228*38fd1498Szrj if (bb_loop_depth (best_bb) == bb_loop_depth (early_bb)
229*38fd1498Szrj /* If result of comparsion is unknown, preffer EARLY_BB.
230*38fd1498Szrj Thus use !(...>=..) rather than (...<...) */
231*38fd1498Szrj && !(best_bb->count.apply_scale (100, 1)
232*38fd1498Szrj > (early_bb->count.apply_scale (threshold, 1))))
233*38fd1498Szrj return best_bb;
234*38fd1498Szrj
235*38fd1498Szrj /* No better block found, so return EARLY_BB, which happens to be the
236*38fd1498Szrj statement's original block. */
237*38fd1498Szrj return early_bb;
238*38fd1498Szrj }
239*38fd1498Szrj
240*38fd1498Szrj /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
241*38fd1498Szrj determine the location to sink the statement to, if any.
242*38fd1498Szrj Returns true if there is such location; in that case, TOGSI points to the
243*38fd1498Szrj statement before that STMT should be moved. */
244*38fd1498Szrj
245*38fd1498Szrj static bool
statement_sink_location(gimple * stmt,basic_block frombb,gimple_stmt_iterator * togsi,bool * zero_uses_p)246*38fd1498Szrj statement_sink_location (gimple *stmt, basic_block frombb,
247*38fd1498Szrj gimple_stmt_iterator *togsi, bool *zero_uses_p)
248*38fd1498Szrj {
249*38fd1498Szrj gimple *use;
250*38fd1498Szrj use_operand_p one_use = NULL_USE_OPERAND_P;
251*38fd1498Szrj basic_block sinkbb;
252*38fd1498Szrj use_operand_p use_p;
253*38fd1498Szrj def_operand_p def_p;
254*38fd1498Szrj ssa_op_iter iter;
255*38fd1498Szrj imm_use_iterator imm_iter;
256*38fd1498Szrj
257*38fd1498Szrj *zero_uses_p = false;
258*38fd1498Szrj
259*38fd1498Szrj /* We only can sink assignments and non-looping const/pure calls. */
260*38fd1498Szrj int cf;
261*38fd1498Szrj if (!is_gimple_assign (stmt)
262*38fd1498Szrj && (!is_gimple_call (stmt)
263*38fd1498Szrj || !((cf = gimple_call_flags (stmt)) & (ECF_CONST|ECF_PURE))
264*38fd1498Szrj || (cf & ECF_LOOPING_CONST_OR_PURE)))
265*38fd1498Szrj return false;
266*38fd1498Szrj
267*38fd1498Szrj /* We only can sink stmts with a single definition. */
268*38fd1498Szrj def_p = single_ssa_def_operand (stmt, SSA_OP_ALL_DEFS);
269*38fd1498Szrj if (def_p == NULL_DEF_OPERAND_P)
270*38fd1498Szrj return false;
271*38fd1498Szrj
272*38fd1498Szrj /* There are a few classes of things we can't or don't move, some because we
273*38fd1498Szrj don't have code to handle it, some because it's not profitable and some
274*38fd1498Szrj because it's not legal.
275*38fd1498Szrj
276*38fd1498Szrj We can't sink things that may be global stores, at least not without
277*38fd1498Szrj calculating a lot more information, because we may cause it to no longer
278*38fd1498Szrj be seen by an external routine that needs it depending on where it gets
279*38fd1498Szrj moved to.
280*38fd1498Szrj
281*38fd1498Szrj We can't sink statements that end basic blocks without splitting the
282*38fd1498Szrj incoming edge for the sink location to place it there.
283*38fd1498Szrj
284*38fd1498Szrj We can't sink statements that have volatile operands.
285*38fd1498Szrj
286*38fd1498Szrj We don't want to sink dead code, so anything with 0 immediate uses is not
287*38fd1498Szrj sunk.
288*38fd1498Szrj
289*38fd1498Szrj Don't sink BLKmode assignments if current function has any local explicit
290*38fd1498Szrj register variables, as BLKmode assignments may involve memcpy or memset
291*38fd1498Szrj calls or, on some targets, inline expansion thereof that sometimes need
292*38fd1498Szrj to use specific hard registers.
293*38fd1498Szrj
294*38fd1498Szrj */
295*38fd1498Szrj if (stmt_ends_bb_p (stmt)
296*38fd1498Szrj || gimple_has_side_effects (stmt)
297*38fd1498Szrj || (cfun->has_local_explicit_reg_vars
298*38fd1498Szrj && TYPE_MODE (TREE_TYPE (gimple_get_lhs (stmt))) == BLKmode))
299*38fd1498Szrj return false;
300*38fd1498Szrj
301*38fd1498Szrj /* Return if there are no immediate uses of this stmt. */
302*38fd1498Szrj if (has_zero_uses (DEF_FROM_PTR (def_p)))
303*38fd1498Szrj {
304*38fd1498Szrj *zero_uses_p = true;
305*38fd1498Szrj return false;
306*38fd1498Szrj }
307*38fd1498Szrj
308*38fd1498Szrj if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (DEF_FROM_PTR (def_p)))
309*38fd1498Szrj return false;
310*38fd1498Szrj
311*38fd1498Szrj FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
312*38fd1498Szrj {
313*38fd1498Szrj tree use = USE_FROM_PTR (use_p);
314*38fd1498Szrj if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
315*38fd1498Szrj return false;
316*38fd1498Szrj }
317*38fd1498Szrj
318*38fd1498Szrj use = NULL;
319*38fd1498Szrj
320*38fd1498Szrj /* If stmt is a store the one and only use needs to be the VOP
321*38fd1498Szrj merging PHI node. */
322*38fd1498Szrj if (virtual_operand_p (DEF_FROM_PTR (def_p)))
323*38fd1498Szrj {
324*38fd1498Szrj FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
325*38fd1498Szrj {
326*38fd1498Szrj gimple *use_stmt = USE_STMT (use_p);
327*38fd1498Szrj
328*38fd1498Szrj /* A killing definition is not a use. */
329*38fd1498Szrj if ((gimple_has_lhs (use_stmt)
330*38fd1498Szrj && operand_equal_p (gimple_get_lhs (stmt),
331*38fd1498Szrj gimple_get_lhs (use_stmt), 0))
332*38fd1498Szrj || stmt_kills_ref_p (use_stmt, gimple_get_lhs (stmt)))
333*38fd1498Szrj {
334*38fd1498Szrj /* If use_stmt is or might be a nop assignment then USE_STMT
335*38fd1498Szrj acts as a use as well as definition. */
336*38fd1498Szrj if (stmt != use_stmt
337*38fd1498Szrj && ref_maybe_used_by_stmt_p (use_stmt,
338*38fd1498Szrj gimple_get_lhs (stmt)))
339*38fd1498Szrj return false;
340*38fd1498Szrj continue;
341*38fd1498Szrj }
342*38fd1498Szrj
343*38fd1498Szrj if (gimple_code (use_stmt) != GIMPLE_PHI)
344*38fd1498Szrj return false;
345*38fd1498Szrj
346*38fd1498Szrj if (use
347*38fd1498Szrj && use != use_stmt)
348*38fd1498Szrj return false;
349*38fd1498Szrj
350*38fd1498Szrj use = use_stmt;
351*38fd1498Szrj }
352*38fd1498Szrj if (!use)
353*38fd1498Szrj return false;
354*38fd1498Szrj }
355*38fd1498Szrj /* If all the immediate uses are not in the same place, find the nearest
356*38fd1498Szrj common dominator of all the immediate uses. For PHI nodes, we have to
357*38fd1498Szrj find the nearest common dominator of all of the predecessor blocks, since
358*38fd1498Szrj that is where insertion would have to take place. */
359*38fd1498Szrj else if (gimple_vuse (stmt)
360*38fd1498Szrj || !all_immediate_uses_same_place (def_p))
361*38fd1498Szrj {
362*38fd1498Szrj bool debug_stmts = false;
363*38fd1498Szrj basic_block commondom = nearest_common_dominator_of_uses (def_p,
364*38fd1498Szrj &debug_stmts);
365*38fd1498Szrj
366*38fd1498Szrj if (commondom == frombb)
367*38fd1498Szrj return false;
368*38fd1498Szrj
369*38fd1498Szrj /* If this is a load then do not sink past any stores.
370*38fd1498Szrj ??? This is overly simple but cheap. We basically look
371*38fd1498Szrj for an existing load with the same VUSE in the path to one
372*38fd1498Szrj of the sink candidate blocks and we adjust commondom to the
373*38fd1498Szrj nearest to commondom. */
374*38fd1498Szrj if (gimple_vuse (stmt))
375*38fd1498Szrj {
376*38fd1498Szrj /* Do not sink loads from hard registers. */
377*38fd1498Szrj if (gimple_assign_single_p (stmt)
378*38fd1498Szrj && TREE_CODE (gimple_assign_rhs1 (stmt)) == VAR_DECL
379*38fd1498Szrj && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt)))
380*38fd1498Szrj return false;
381*38fd1498Szrj
382*38fd1498Szrj imm_use_iterator imm_iter;
383*38fd1498Szrj use_operand_p use_p;
384*38fd1498Szrj basic_block found = NULL;
385*38fd1498Szrj FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_vuse (stmt))
386*38fd1498Szrj {
387*38fd1498Szrj gimple *use_stmt = USE_STMT (use_p);
388*38fd1498Szrj basic_block bb = gimple_bb (use_stmt);
389*38fd1498Szrj /* For PHI nodes the block we know sth about
390*38fd1498Szrj is the incoming block with the use. */
391*38fd1498Szrj if (gimple_code (use_stmt) == GIMPLE_PHI)
392*38fd1498Szrj bb = EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src;
393*38fd1498Szrj /* Any dominator of commondom would be ok with
394*38fd1498Szrj adjusting commondom to that block. */
395*38fd1498Szrj bb = nearest_common_dominator (CDI_DOMINATORS, bb, commondom);
396*38fd1498Szrj if (!found)
397*38fd1498Szrj found = bb;
398*38fd1498Szrj else if (dominated_by_p (CDI_DOMINATORS, bb, found))
399*38fd1498Szrj found = bb;
400*38fd1498Szrj /* If we can't improve, stop. */
401*38fd1498Szrj if (found == commondom)
402*38fd1498Szrj break;
403*38fd1498Szrj }
404*38fd1498Szrj commondom = found;
405*38fd1498Szrj if (commondom == frombb)
406*38fd1498Szrj return false;
407*38fd1498Szrj }
408*38fd1498Szrj
409*38fd1498Szrj /* Our common dominator has to be dominated by frombb in order to be a
410*38fd1498Szrj trivially safe place to put this statement, since it has multiple
411*38fd1498Szrj uses. */
412*38fd1498Szrj if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
413*38fd1498Szrj return false;
414*38fd1498Szrj
415*38fd1498Szrj commondom = select_best_block (frombb, commondom, stmt);
416*38fd1498Szrj
417*38fd1498Szrj if (commondom == frombb)
418*38fd1498Szrj return false;
419*38fd1498Szrj
420*38fd1498Szrj *togsi = gsi_after_labels (commondom);
421*38fd1498Szrj
422*38fd1498Szrj return true;
423*38fd1498Szrj }
424*38fd1498Szrj else
425*38fd1498Szrj {
426*38fd1498Szrj FOR_EACH_IMM_USE_FAST (one_use, imm_iter, DEF_FROM_PTR (def_p))
427*38fd1498Szrj {
428*38fd1498Szrj if (is_gimple_debug (USE_STMT (one_use)))
429*38fd1498Szrj continue;
430*38fd1498Szrj break;
431*38fd1498Szrj }
432*38fd1498Szrj use = USE_STMT (one_use);
433*38fd1498Szrj
434*38fd1498Szrj if (gimple_code (use) != GIMPLE_PHI)
435*38fd1498Szrj {
436*38fd1498Szrj sinkbb = gimple_bb (use);
437*38fd1498Szrj sinkbb = select_best_block (frombb, gimple_bb (use), stmt);
438*38fd1498Szrj
439*38fd1498Szrj if (sinkbb == frombb)
440*38fd1498Szrj return false;
441*38fd1498Szrj
442*38fd1498Szrj *togsi = gsi_for_stmt (use);
443*38fd1498Szrj
444*38fd1498Szrj return true;
445*38fd1498Szrj }
446*38fd1498Szrj }
447*38fd1498Szrj
448*38fd1498Szrj sinkbb = find_bb_for_arg (as_a <gphi *> (use), DEF_FROM_PTR (def_p));
449*38fd1498Szrj
450*38fd1498Szrj /* This can happen if there are multiple uses in a PHI. */
451*38fd1498Szrj if (!sinkbb)
452*38fd1498Szrj return false;
453*38fd1498Szrj
454*38fd1498Szrj sinkbb = select_best_block (frombb, sinkbb, stmt);
455*38fd1498Szrj if (!sinkbb || sinkbb == frombb)
456*38fd1498Szrj return false;
457*38fd1498Szrj
458*38fd1498Szrj /* If the latch block is empty, don't make it non-empty by sinking
459*38fd1498Szrj something into it. */
460*38fd1498Szrj if (sinkbb == frombb->loop_father->latch
461*38fd1498Szrj && empty_block_p (sinkbb))
462*38fd1498Szrj return false;
463*38fd1498Szrj
464*38fd1498Szrj *togsi = gsi_after_labels (sinkbb);
465*38fd1498Szrj
466*38fd1498Szrj return true;
467*38fd1498Szrj }
468*38fd1498Szrj
469*38fd1498Szrj /* Perform code sinking on BB */
470*38fd1498Szrj
471*38fd1498Szrj static void
sink_code_in_bb(basic_block bb)472*38fd1498Szrj sink_code_in_bb (basic_block bb)
473*38fd1498Szrj {
474*38fd1498Szrj basic_block son;
475*38fd1498Szrj gimple_stmt_iterator gsi;
476*38fd1498Szrj edge_iterator ei;
477*38fd1498Szrj edge e;
478*38fd1498Szrj bool last = true;
479*38fd1498Szrj
480*38fd1498Szrj /* If this block doesn't dominate anything, there can't be any place to sink
481*38fd1498Szrj the statements to. */
482*38fd1498Szrj if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
483*38fd1498Szrj goto earlyout;
484*38fd1498Szrj
485*38fd1498Szrj /* We can't move things across abnormal edges, so don't try. */
486*38fd1498Szrj FOR_EACH_EDGE (e, ei, bb->succs)
487*38fd1498Szrj if (e->flags & EDGE_ABNORMAL)
488*38fd1498Szrj goto earlyout;
489*38fd1498Szrj
490*38fd1498Szrj for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
491*38fd1498Szrj {
492*38fd1498Szrj gimple *stmt = gsi_stmt (gsi);
493*38fd1498Szrj gimple_stmt_iterator togsi;
494*38fd1498Szrj bool zero_uses_p;
495*38fd1498Szrj
496*38fd1498Szrj if (!statement_sink_location (stmt, bb, &togsi, &zero_uses_p))
497*38fd1498Szrj {
498*38fd1498Szrj gimple_stmt_iterator saved = gsi;
499*38fd1498Szrj if (!gsi_end_p (gsi))
500*38fd1498Szrj gsi_prev (&gsi);
501*38fd1498Szrj /* If we face a dead stmt remove it as it possibly blocks
502*38fd1498Szrj sinking of uses. */
503*38fd1498Szrj if (zero_uses_p
504*38fd1498Szrj && ! gimple_vdef (stmt))
505*38fd1498Szrj {
506*38fd1498Szrj gsi_remove (&saved, true);
507*38fd1498Szrj release_defs (stmt);
508*38fd1498Szrj }
509*38fd1498Szrj else
510*38fd1498Szrj last = false;
511*38fd1498Szrj continue;
512*38fd1498Szrj }
513*38fd1498Szrj if (dump_file)
514*38fd1498Szrj {
515*38fd1498Szrj fprintf (dump_file, "Sinking ");
516*38fd1498Szrj print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS);
517*38fd1498Szrj fprintf (dump_file, " from bb %d to bb %d\n",
518*38fd1498Szrj bb->index, (gsi_bb (togsi))->index);
519*38fd1498Szrj }
520*38fd1498Szrj
521*38fd1498Szrj /* Update virtual operands of statements in the path we
522*38fd1498Szrj do not sink to. */
523*38fd1498Szrj if (gimple_vdef (stmt))
524*38fd1498Szrj {
525*38fd1498Szrj imm_use_iterator iter;
526*38fd1498Szrj use_operand_p use_p;
527*38fd1498Szrj gimple *vuse_stmt;
528*38fd1498Szrj
529*38fd1498Szrj FOR_EACH_IMM_USE_STMT (vuse_stmt, iter, gimple_vdef (stmt))
530*38fd1498Szrj if (gimple_code (vuse_stmt) != GIMPLE_PHI)
531*38fd1498Szrj FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
532*38fd1498Szrj SET_USE (use_p, gimple_vuse (stmt));
533*38fd1498Szrj }
534*38fd1498Szrj
535*38fd1498Szrj /* If this is the end of the basic block, we need to insert at the end
536*38fd1498Szrj of the basic block. */
537*38fd1498Szrj if (gsi_end_p (togsi))
538*38fd1498Szrj gsi_move_to_bb_end (&gsi, gsi_bb (togsi));
539*38fd1498Szrj else
540*38fd1498Szrj gsi_move_before (&gsi, &togsi);
541*38fd1498Szrj
542*38fd1498Szrj sink_stats.sunk++;
543*38fd1498Szrj
544*38fd1498Szrj /* If we've just removed the last statement of the BB, the
545*38fd1498Szrj gsi_end_p() test below would fail, but gsi_prev() would have
546*38fd1498Szrj succeeded, and we want it to succeed. So we keep track of
547*38fd1498Szrj whether we're at the last statement and pick up the new last
548*38fd1498Szrj statement. */
549*38fd1498Szrj if (last)
550*38fd1498Szrj {
551*38fd1498Szrj gsi = gsi_last_bb (bb);
552*38fd1498Szrj continue;
553*38fd1498Szrj }
554*38fd1498Szrj
555*38fd1498Szrj last = false;
556*38fd1498Szrj if (!gsi_end_p (gsi))
557*38fd1498Szrj gsi_prev (&gsi);
558*38fd1498Szrj
559*38fd1498Szrj }
560*38fd1498Szrj earlyout:
561*38fd1498Szrj for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
562*38fd1498Szrj son;
563*38fd1498Szrj son = next_dom_son (CDI_POST_DOMINATORS, son))
564*38fd1498Szrj {
565*38fd1498Szrj sink_code_in_bb (son);
566*38fd1498Szrj }
567*38fd1498Szrj }
568*38fd1498Szrj
569*38fd1498Szrj /* Perform code sinking.
570*38fd1498Szrj This moves code down the flowgraph when we know it would be
571*38fd1498Szrj profitable to do so, or it wouldn't increase the number of
572*38fd1498Szrj executions of the statement.
573*38fd1498Szrj
574*38fd1498Szrj IE given
575*38fd1498Szrj
576*38fd1498Szrj a_1 = b + c;
577*38fd1498Szrj if (<something>)
578*38fd1498Szrj {
579*38fd1498Szrj }
580*38fd1498Szrj else
581*38fd1498Szrj {
582*38fd1498Szrj foo (&b, &c);
583*38fd1498Szrj a_5 = b + c;
584*38fd1498Szrj }
585*38fd1498Szrj a_6 = PHI (a_5, a_1);
586*38fd1498Szrj USE a_6.
587*38fd1498Szrj
588*38fd1498Szrj we'll transform this into:
589*38fd1498Szrj
590*38fd1498Szrj if (<something>)
591*38fd1498Szrj {
592*38fd1498Szrj a_1 = b + c;
593*38fd1498Szrj }
594*38fd1498Szrj else
595*38fd1498Szrj {
596*38fd1498Szrj foo (&b, &c);
597*38fd1498Szrj a_5 = b + c;
598*38fd1498Szrj }
599*38fd1498Szrj a_6 = PHI (a_5, a_1);
600*38fd1498Szrj USE a_6.
601*38fd1498Szrj
602*38fd1498Szrj Note that this reduces the number of computations of a = b + c to 1
603*38fd1498Szrj when we take the else edge, instead of 2.
604*38fd1498Szrj */
605*38fd1498Szrj namespace {
606*38fd1498Szrj
607*38fd1498Szrj const pass_data pass_data_sink_code =
608*38fd1498Szrj {
609*38fd1498Szrj GIMPLE_PASS, /* type */
610*38fd1498Szrj "sink", /* name */
611*38fd1498Szrj OPTGROUP_NONE, /* optinfo_flags */
612*38fd1498Szrj TV_TREE_SINK, /* tv_id */
613*38fd1498Szrj /* PROP_no_crit_edges is ensured by running split_critical_edges in
614*38fd1498Szrj pass_data_sink_code::execute (). */
615*38fd1498Szrj ( PROP_cfg | PROP_ssa ), /* properties_required */
616*38fd1498Szrj 0, /* properties_provided */
617*38fd1498Szrj 0, /* properties_destroyed */
618*38fd1498Szrj 0, /* todo_flags_start */
619*38fd1498Szrj TODO_update_ssa, /* todo_flags_finish */
620*38fd1498Szrj };
621*38fd1498Szrj
622*38fd1498Szrj class pass_sink_code : public gimple_opt_pass
623*38fd1498Szrj {
624*38fd1498Szrj public:
pass_sink_code(gcc::context * ctxt)625*38fd1498Szrj pass_sink_code (gcc::context *ctxt)
626*38fd1498Szrj : gimple_opt_pass (pass_data_sink_code, ctxt)
627*38fd1498Szrj {}
628*38fd1498Szrj
629*38fd1498Szrj /* opt_pass methods: */
gate(function *)630*38fd1498Szrj virtual bool gate (function *) { return flag_tree_sink != 0; }
631*38fd1498Szrj virtual unsigned int execute (function *);
632*38fd1498Szrj
633*38fd1498Szrj }; // class pass_sink_code
634*38fd1498Szrj
635*38fd1498Szrj unsigned int
execute(function * fun)636*38fd1498Szrj pass_sink_code::execute (function *fun)
637*38fd1498Szrj {
638*38fd1498Szrj loop_optimizer_init (LOOPS_NORMAL);
639*38fd1498Szrj split_critical_edges ();
640*38fd1498Szrj connect_infinite_loops_to_exit ();
641*38fd1498Szrj memset (&sink_stats, 0, sizeof (sink_stats));
642*38fd1498Szrj calculate_dominance_info (CDI_DOMINATORS);
643*38fd1498Szrj calculate_dominance_info (CDI_POST_DOMINATORS);
644*38fd1498Szrj sink_code_in_bb (EXIT_BLOCK_PTR_FOR_FN (fun));
645*38fd1498Szrj statistics_counter_event (fun, "Sunk statements", sink_stats.sunk);
646*38fd1498Szrj free_dominance_info (CDI_POST_DOMINATORS);
647*38fd1498Szrj remove_fake_exit_edges ();
648*38fd1498Szrj loop_optimizer_finalize ();
649*38fd1498Szrj
650*38fd1498Szrj return 0;
651*38fd1498Szrj }
652*38fd1498Szrj
653*38fd1498Szrj } // anon namespace
654*38fd1498Szrj
655*38fd1498Szrj gimple_opt_pass *
make_pass_sink_code(gcc::context * ctxt)656*38fd1498Szrj make_pass_sink_code (gcc::context *ctxt)
657*38fd1498Szrj {
658*38fd1498Szrj return new pass_sink_code (ctxt);
659*38fd1498Szrj }
660