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