comparison gcc/tree-ssa-sink.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents f6334be47118
children 84e7813d76e9
comparison
equal deleted inserted replaced
15:561a7518be6b 16:04ced10e8804
1 /* Code sinking for trees 1 /* Code sinking for trees
2 Copyright (C) 2001, 2002, 2003, 2004, 2007, 2008, 2009, 2010 2 Copyright (C) 2001-2017 Free Software Foundation, Inc.
3 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin <dan@dberlin.org> 3 Contributed by Daniel Berlin <dan@dberlin.org>
5 4
6 This file is part of GCC. 5 This file is part of GCC.
7 6
8 GCC is free software; you can redistribute it and/or modify 7 GCC is free software; you can redistribute it and/or modify
20 <http://www.gnu.org/licenses/>. */ 19 <http://www.gnu.org/licenses/>. */
21 20
22 #include "config.h" 21 #include "config.h"
23 #include "system.h" 22 #include "system.h"
24 #include "coretypes.h" 23 #include "coretypes.h"
25 #include "tm.h" 24 #include "backend.h"
26 #include "tree.h" 25 #include "tree.h"
27 #include "basic-block.h" 26 #include "gimple.h"
27 #include "cfghooks.h"
28 #include "tree-pass.h"
29 #include "ssa.h"
28 #include "gimple-pretty-print.h" 30 #include "gimple-pretty-print.h"
29 #include "tree-inline.h" 31 #include "fold-const.h"
30 #include "tree-flow.h" 32 #include "stor-layout.h"
31 #include "gimple.h" 33 #include "cfganal.h"
32 #include "tree-dump.h" 34 #include "gimple-iterator.h"
33 #include "timevar.h" 35 #include "tree-cfg.h"
34 #include "fibheap.h"
35 #include "hashtab.h"
36 #include "tree-iterator.h"
37 #include "alloc-pool.h"
38 #include "tree-pass.h"
39 #include "flags.h"
40 #include "bitmap.h"
41 #include "langhooks.h"
42 #include "cfgloop.h" 36 #include "cfgloop.h"
37 #include "params.h"
43 38
44 /* TODO: 39 /* TODO:
45 1. Sinking store only using scalar promotion (IE without moving the RHS): 40 1. Sinking store only using scalar promotion (IE without moving the RHS):
46 41
47 *q = p; 42 *q = p;
79 /* Given a PHI, and one of its arguments (DEF), find the edge for 74 /* Given a PHI, and one of its arguments (DEF), find the edge for
80 that argument and return it. If the argument occurs twice in the PHI node, 75 that argument and return it. If the argument occurs twice in the PHI node,
81 we return NULL. */ 76 we return NULL. */
82 77
83 static basic_block 78 static basic_block
84 find_bb_for_arg (gimple phi, tree def) 79 find_bb_for_arg (gphi *phi, tree def)
85 { 80 {
86 size_t i; 81 size_t i;
87 bool foundone = false; 82 bool foundone = false;
88 basic_block result = NULL; 83 basic_block result = NULL;
89 for (i = 0; i < gimple_phi_num_args (phi); i++) 84 for (i = 0; i < gimple_phi_num_args (phi); i++)
104 requires some expensive checking later (you have to make sure no def/vdef 99 requires some expensive checking later (you have to make sure no def/vdef
105 in the statement occurs for multiple edges in the various phi nodes it's 100 in the statement occurs for multiple edges in the various phi nodes it's
106 used in, so that you only have one place you can sink it to. */ 101 used in, so that you only have one place you can sink it to. */
107 102
108 static bool 103 static bool
109 all_immediate_uses_same_place (gimple stmt) 104 all_immediate_uses_same_place (def_operand_p def_p)
110 { 105 {
111 gimple firstuse = NULL; 106 tree var = DEF_FROM_PTR (def_p);
112 ssa_op_iter op_iter;
113 imm_use_iterator imm_iter; 107 imm_use_iterator imm_iter;
114 use_operand_p use_p; 108 use_operand_p use_p;
115 tree var; 109
116 110 gimple *firstuse = NULL;
117 FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS) 111 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
118 { 112 {
119 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var) 113 if (is_gimple_debug (USE_STMT (use_p)))
120 { 114 continue;
121 if (is_gimple_debug (USE_STMT (use_p))) 115 if (firstuse == NULL)
122 continue; 116 firstuse = USE_STMT (use_p);
123 if (firstuse == NULL) 117 else
124 firstuse = USE_STMT (use_p); 118 if (firstuse != USE_STMT (use_p))
125 else 119 return false;
126 if (firstuse != USE_STMT (use_p))
127 return false;
128 }
129 } 120 }
130 121
131 return true; 122 return true;
132 } 123 }
133 124
134 /* Some global stores don't necessarily have VDEF's of global variables,
135 but we still must avoid moving them around. */
136
137 bool
138 is_hidden_global_store (gimple stmt)
139 {
140 /* Check virtual definitions. If we get here, the only virtual
141 definitions we should see are those generated by assignment or call
142 statements. */
143 if (gimple_vdef (stmt))
144 {
145 tree lhs;
146
147 gcc_assert (is_gimple_assign (stmt) || is_gimple_call (stmt));
148
149 /* Note that we must not check the individual virtual operands
150 here. In particular, if this is an aliased store, we could
151 end up with something like the following (SSA notation
152 redacted for brevity):
153
154 foo (int *p, int i)
155 {
156 int x;
157 p_1 = (i_2 > 3) ? &x : p;
158
159 # x_4 = VDEF <x_3>
160 *p_1 = 5;
161
162 return 2;
163 }
164
165 Notice that the store to '*p_1' should be preserved, if we
166 were to check the virtual definitions in that store, we would
167 not mark it needed. This is because 'x' is not a global
168 variable.
169
170 Therefore, we check the base address of the LHS. If the
171 address is a pointer, we check if its name tag or symbol tag is
172 a global variable. Otherwise, we check if the base variable
173 is a global. */
174 lhs = gimple_get_lhs (stmt);
175
176 if (REFERENCE_CLASS_P (lhs))
177 lhs = get_base_address (lhs);
178
179 if (lhs == NULL_TREE)
180 {
181 /* If LHS is NULL, it means that we couldn't get the base
182 address of the reference. In which case, we should not
183 move this store. */
184 return true;
185 }
186 else if (DECL_P (lhs))
187 {
188 /* If the store is to a global symbol, we need to keep it. */
189 if (is_global_var (lhs))
190 return true;
191
192 }
193 else if (INDIRECT_REF_P (lhs)
194 || TREE_CODE (lhs) == MEM_REF
195 || TREE_CODE (lhs) == TARGET_MEM_REF)
196 return ptr_deref_may_alias_global_p (TREE_OPERAND (lhs, 0));
197 else if (CONSTANT_CLASS_P (lhs))
198 return true;
199 else
200 gcc_unreachable ();
201 }
202
203 return false;
204 }
205
206 /* Find the nearest common dominator of all of the immediate uses in IMM. */ 125 /* Find the nearest common dominator of all of the immediate uses in IMM. */
207 126
208 static basic_block 127 static basic_block
209 nearest_common_dominator_of_uses (gimple stmt, bool *debug_stmts) 128 nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts)
210 { 129 {
211 bitmap blocks = BITMAP_ALLOC (NULL); 130 tree var = DEF_FROM_PTR (def_p);
131 auto_bitmap blocks;
212 basic_block commondom; 132 basic_block commondom;
213 unsigned int j; 133 unsigned int j;
214 bitmap_iterator bi; 134 bitmap_iterator bi;
215 ssa_op_iter op_iter;
216 imm_use_iterator imm_iter; 135 imm_use_iterator imm_iter;
217 use_operand_p use_p; 136 use_operand_p use_p;
218 tree var; 137
219 138 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
220 bitmap_clear (blocks); 139 {
221 FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS) 140 gimple *usestmt = USE_STMT (use_p);
222 { 141 basic_block useblock;
223 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var) 142
224 { 143 if (gphi *phi = dyn_cast <gphi *> (usestmt))
225 gimple usestmt = USE_STMT (use_p); 144 {
226 basic_block useblock; 145 int idx = PHI_ARG_INDEX_FROM_USE (use_p);
227 146
228 if (gimple_code (usestmt) == GIMPLE_PHI) 147 useblock = gimple_phi_arg_edge (phi, idx)->src;
229 { 148 }
230 int idx = PHI_ARG_INDEX_FROM_USE (use_p); 149 else if (is_gimple_debug (usestmt))
231 150 {
232 useblock = gimple_phi_arg_edge (usestmt, idx)->src; 151 *debug_stmts = true;
233 } 152 continue;
234 else if (is_gimple_debug (usestmt)) 153 }
235 { 154 else
236 *debug_stmts = true; 155 {
237 continue; 156 useblock = gimple_bb (usestmt);
238 } 157 }
239 else 158
240 { 159 /* Short circuit. Nothing dominates the entry block. */
241 useblock = gimple_bb (usestmt); 160 if (useblock == ENTRY_BLOCK_PTR_FOR_FN (cfun))
242 } 161 return NULL;
243 162
244 /* Short circuit. Nothing dominates the entry block. */ 163 bitmap_set_bit (blocks, useblock->index);
245 if (useblock == ENTRY_BLOCK_PTR) 164 }
246 { 165 commondom = BASIC_BLOCK_FOR_FN (cfun, bitmap_first_set_bit (blocks));
247 BITMAP_FREE (blocks);
248 return NULL;
249 }
250 bitmap_set_bit (blocks, useblock->index);
251 }
252 }
253 commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
254 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi) 166 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
255 commondom = nearest_common_dominator (CDI_DOMINATORS, commondom, 167 commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
256 BASIC_BLOCK (j)); 168 BASIC_BLOCK_FOR_FN (cfun, j));
257 BITMAP_FREE (blocks);
258 return commondom; 169 return commondom;
170 }
171
172 /* Given EARLY_BB and LATE_BB, two blocks in a path through the dominator
173 tree, return the best basic block between them (inclusive) to place
174 statements.
175
176 We want the most control dependent block in the shallowest loop nest.
177
178 If the resulting block is in a shallower loop nest, then use it. Else
179 only use the resulting block if it has significantly lower execution
180 frequency than EARLY_BB to avoid gratutious statement movement. We
181 consider statements with VOPS more desirable to move.
182
183 This pass would obviously benefit from PDO as it utilizes block
184 frequencies. It would also benefit from recomputing frequencies
185 if profile data is not available since frequencies often get out
186 of sync with reality. */
187
188 static basic_block
189 select_best_block (basic_block early_bb,
190 basic_block late_bb,
191 gimple *stmt)
192 {
193 basic_block best_bb = late_bb;
194 basic_block temp_bb = late_bb;
195 int threshold;
196
197 while (temp_bb != early_bb)
198 {
199 /* If we've moved into a lower loop nest, then that becomes
200 our best block. */
201 if (bb_loop_depth (temp_bb) < bb_loop_depth (best_bb))
202 best_bb = temp_bb;
203
204 /* Walk up the dominator tree, hopefully we'll find a shallower
205 loop nest. */
206 temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb);
207 }
208
209 /* If we found a shallower loop nest, then we always consider that
210 a win. This will always give us the most control dependent block
211 within that loop nest. */
212 if (bb_loop_depth (best_bb) < bb_loop_depth (early_bb))
213 return best_bb;
214
215 /* Get the sinking threshold. If the statement to be moved has memory
216 operands, then increase the threshold by 7% as those are even more
217 profitable to avoid, clamping at 100%. */
218 threshold = PARAM_VALUE (PARAM_SINK_FREQUENCY_THRESHOLD);
219 if (gimple_vuse (stmt) || gimple_vdef (stmt))
220 {
221 threshold += 7;
222 if (threshold > 100)
223 threshold = 100;
224 }
225
226 /* If BEST_BB is at the same nesting level, then require it to have
227 significantly lower execution frequency to avoid gratutious movement. */
228 if (bb_loop_depth (best_bb) == bb_loop_depth (early_bb)
229 && best_bb->frequency < (early_bb->frequency * threshold / 100.0))
230 return best_bb;
231
232 /* No better block found, so return EARLY_BB, which happens to be the
233 statement's original block. */
234 return early_bb;
259 } 235 }
260 236
261 /* Given a statement (STMT) and the basic block it is currently in (FROMBB), 237 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
262 determine the location to sink the statement to, if any. 238 determine the location to sink the statement to, if any.
263 Returns true if there is such location; in that case, TOGSI points to the 239 Returns true if there is such location; in that case, TOGSI points to the
264 statement before that STMT should be moved. */ 240 statement before that STMT should be moved. */
265 241
266 static bool 242 static bool
267 statement_sink_location (gimple stmt, basic_block frombb, 243 statement_sink_location (gimple *stmt, basic_block frombb,
268 gimple_stmt_iterator *togsi) 244 gimple_stmt_iterator *togsi, bool *zero_uses_p)
269 { 245 {
270 gimple use; 246 gimple *use;
271 tree def;
272 use_operand_p one_use = NULL_USE_OPERAND_P; 247 use_operand_p one_use = NULL_USE_OPERAND_P;
273 basic_block sinkbb; 248 basic_block sinkbb;
274 use_operand_p use_p; 249 use_operand_p use_p;
275 def_operand_p def_p; 250 def_operand_p def_p;
276 ssa_op_iter iter; 251 ssa_op_iter iter;
277 imm_use_iterator imm_iter; 252 imm_use_iterator imm_iter;
278 253
279 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 254 *zero_uses_p = false;
280 { 255
281 FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def) 256 /* We only can sink assignments and non-looping const/pure calls. */
282 { 257 int cf;
283 if (is_gimple_debug (USE_STMT (one_use))) 258 if (!is_gimple_assign (stmt)
284 continue; 259 && (!is_gimple_call (stmt)
285 260 || !((cf = gimple_call_flags (stmt)) & (ECF_CONST|ECF_PURE))
286 break; 261 || (cf & ECF_LOOPING_CONST_OR_PURE)))
287 }
288 if (one_use != NULL_USE_OPERAND_P)
289 break;
290 }
291
292 /* Return if there are no immediate uses of this stmt. */
293 if (one_use == NULL_USE_OPERAND_P)
294 return false; 262 return false;
295 263
296 if (gimple_code (stmt) != GIMPLE_ASSIGN) 264 /* We only can sink stmts with a single definition. */
265 def_p = single_ssa_def_operand (stmt, SSA_OP_ALL_DEFS);
266 if (def_p == NULL_DEF_OPERAND_P)
297 return false; 267 return false;
298 268
299 /* There are a few classes of things we can't or don't move, some because we 269 /* There are a few classes of things we can't or don't move, some because we
300 don't have code to handle it, some because it's not profitable and some 270 don't have code to handle it, some because it's not profitable and some
301 because it's not legal. 271 because it's not legal.
303 We can't sink things that may be global stores, at least not without 273 We can't sink things that may be global stores, at least not without
304 calculating a lot more information, because we may cause it to no longer 274 calculating a lot more information, because we may cause it to no longer
305 be seen by an external routine that needs it depending on where it gets 275 be seen by an external routine that needs it depending on where it gets
306 moved to. 276 moved to.
307 277
308 We don't want to sink loads from memory.
309
310 We can't sink statements that end basic blocks without splitting the 278 We can't sink statements that end basic blocks without splitting the
311 incoming edge for the sink location to place it there. 279 incoming edge for the sink location to place it there.
312 280
313 We can't sink statements that have volatile operands. 281 We can't sink statements that have volatile operands.
314 282
321 to use specific hard registers. 289 to use specific hard registers.
322 290
323 */ 291 */
324 if (stmt_ends_bb_p (stmt) 292 if (stmt_ends_bb_p (stmt)
325 || gimple_has_side_effects (stmt) 293 || gimple_has_side_effects (stmt)
326 || is_hidden_global_store (stmt)
327 || gimple_has_volatile_ops (stmt)
328 || gimple_vuse (stmt)
329 || (cfun->has_local_explicit_reg_vars 294 || (cfun->has_local_explicit_reg_vars
330 && TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))) == BLKmode)) 295 && TYPE_MODE (TREE_TYPE (gimple_get_lhs (stmt))) == BLKmode))
331 return false; 296 return false;
332 297
333 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS) 298 /* Return if there are no immediate uses of this stmt. */
334 { 299 if (has_zero_uses (DEF_FROM_PTR (def_p)))
335 tree def = DEF_FROM_PTR (def_p); 300 {
336 if (is_global_var (SSA_NAME_VAR (def)) 301 *zero_uses_p = true;
337 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)) 302 return false;
338 return false; 303 }
339 } 304
305 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (DEF_FROM_PTR (def_p)))
306 return false;
340 307
341 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) 308 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
342 { 309 {
343 tree use = USE_FROM_PTR (use_p); 310 tree use = USE_FROM_PTR (use_p);
344 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use)) 311 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
345 return false; 312 return false;
346 } 313 }
347 314
315 use = NULL;
316
317 /* If stmt is a store the one and only use needs to be the VOP
318 merging PHI node. */
319 if (virtual_operand_p (DEF_FROM_PTR (def_p)))
320 {
321 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
322 {
323 gimple *use_stmt = USE_STMT (use_p);
324
325 /* A killing definition is not a use. */
326 if ((gimple_has_lhs (use_stmt)
327 && operand_equal_p (gimple_get_lhs (stmt),
328 gimple_get_lhs (use_stmt), 0))
329 || stmt_kills_ref_p (use_stmt, gimple_get_lhs (stmt)))
330 {
331 /* If use_stmt is or might be a nop assignment then USE_STMT
332 acts as a use as well as definition. */
333 if (stmt != use_stmt
334 && ref_maybe_used_by_stmt_p (use_stmt,
335 gimple_get_lhs (stmt)))
336 return false;
337 continue;
338 }
339
340 if (gimple_code (use_stmt) != GIMPLE_PHI)
341 return false;
342
343 if (use
344 && use != use_stmt)
345 return false;
346
347 use = use_stmt;
348 }
349 if (!use)
350 return false;
351 }
348 /* If all the immediate uses are not in the same place, find the nearest 352 /* If all the immediate uses are not in the same place, find the nearest
349 common dominator of all the immediate uses. For PHI nodes, we have to 353 common dominator of all the immediate uses. For PHI nodes, we have to
350 find the nearest common dominator of all of the predecessor blocks, since 354 find the nearest common dominator of all of the predecessor blocks, since
351 that is where insertion would have to take place. */ 355 that is where insertion would have to take place. */
352 if (!all_immediate_uses_same_place (stmt)) 356 else if (gimple_vuse (stmt)
357 || !all_immediate_uses_same_place (def_p))
353 { 358 {
354 bool debug_stmts = false; 359 bool debug_stmts = false;
355 basic_block commondom = nearest_common_dominator_of_uses (stmt, 360 basic_block commondom = nearest_common_dominator_of_uses (def_p,
356 &debug_stmts); 361 &debug_stmts);
357 362
358 if (commondom == frombb) 363 if (commondom == frombb)
359 return false; 364 return false;
365
366 /* If this is a load then do not sink past any stores.
367 ??? This is overly simple but cheap. We basically look
368 for an existing load with the same VUSE in the path to one
369 of the sink candidate blocks and we adjust commondom to the
370 nearest to commondom. */
371 if (gimple_vuse (stmt))
372 {
373 /* Do not sink loads from hard registers. */
374 if (gimple_assign_single_p (stmt)
375 && TREE_CODE (gimple_assign_rhs1 (stmt)) == VAR_DECL
376 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt)))
377 return false;
378
379 imm_use_iterator imm_iter;
380 use_operand_p use_p;
381 basic_block found = NULL;
382 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_vuse (stmt))
383 {
384 gimple *use_stmt = USE_STMT (use_p);
385 basic_block bb = gimple_bb (use_stmt);
386 /* For PHI nodes the block we know sth about
387 is the incoming block with the use. */
388 if (gimple_code (use_stmt) == GIMPLE_PHI)
389 bb = EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src;
390 /* Any dominator of commondom would be ok with
391 adjusting commondom to that block. */
392 bb = nearest_common_dominator (CDI_DOMINATORS, bb, commondom);
393 if (!found)
394 found = bb;
395 else if (dominated_by_p (CDI_DOMINATORS, bb, found))
396 found = bb;
397 /* If we can't improve, stop. */
398 if (found == commondom)
399 break;
400 }
401 commondom = found;
402 if (commondom == frombb)
403 return false;
404 }
360 405
361 /* Our common dominator has to be dominated by frombb in order to be a 406 /* Our common dominator has to be dominated by frombb in order to be a
362 trivially safe place to put this statement, since it has multiple 407 trivially safe place to put this statement, since it has multiple
363 uses. */ 408 uses. */
364 if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb)) 409 if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
365 return false; 410 return false;
366 411
367 /* It doesn't make sense to move to a dominator that post-dominates 412 commondom = select_best_block (frombb, commondom, stmt);
368 frombb, because it means we've just moved it into a path that always 413
369 executes if frombb executes, instead of reducing the number of 414 if (commondom == frombb)
370 executions . */ 415 return false;
371 if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
372 {
373 if (dump_file && (dump_flags & TDF_DETAILS))
374 fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
375 return false;
376 }
377
378 if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
379 return false;
380 if (dump_file && (dump_flags & TDF_DETAILS))
381 {
382 fprintf (dump_file, "Common dominator of all uses is %d\n",
383 commondom->index);
384 }
385 416
386 *togsi = gsi_after_labels (commondom); 417 *togsi = gsi_after_labels (commondom);
387 418
388 return true; 419 return true;
389 } 420 }
390 421 else
391 use = USE_STMT (one_use); 422 {
392 if (gimple_code (use) != GIMPLE_PHI) 423 FOR_EACH_IMM_USE_FAST (one_use, imm_iter, DEF_FROM_PTR (def_p))
393 { 424 {
394 sinkbb = gimple_bb (use); 425 if (is_gimple_debug (USE_STMT (one_use)))
395 if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth 426 continue;
396 || sinkbb->loop_father != frombb->loop_father) 427 break;
397 return false; 428 }
398 429 use = USE_STMT (one_use);
399 /* Move the expression to a post dominator can't reduce the number of 430
400 executions. */ 431 if (gimple_code (use) != GIMPLE_PHI)
401 if (dominated_by_p (CDI_POST_DOMINATORS, frombb, sinkbb)) 432 {
402 return false; 433 sinkbb = gimple_bb (use);
403 434 sinkbb = select_best_block (frombb, gimple_bb (use), stmt);
404 *togsi = gsi_for_stmt (use); 435
405 436 if (sinkbb == frombb)
406 return true; 437 return false;
407 } 438
408 439 *togsi = gsi_for_stmt (use);
409 /* Note that at this point, all uses must be in the same statement, so it 440
410 doesn't matter which def op we choose, pick the first one. */ 441 return true;
411 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 442 }
412 break; 443 }
413 444
414 sinkbb = find_bb_for_arg (use, def); 445 sinkbb = find_bb_for_arg (as_a <gphi *> (use), DEF_FROM_PTR (def_p));
446
447 /* This can happen if there are multiple uses in a PHI. */
415 if (!sinkbb) 448 if (!sinkbb)
416 return false; 449 return false;
417 450
418 /* This will happen when you have 451 sinkbb = select_best_block (frombb, sinkbb, stmt);
419 a_3 = PHI <a_13, a_26> 452 if (!sinkbb || sinkbb == frombb)
420
421 a_26 = VDEF <a_3>
422
423 If the use is a phi, and is in the same bb as the def,
424 we can't sink it. */
425
426 if (gimple_bb (use) == frombb)
427 return false;
428 if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
429 || sinkbb->loop_father != frombb->loop_father)
430 return false; 453 return false;
431 454
432 /* If the latch block is empty, don't make it non-empty by sinking 455 /* If the latch block is empty, don't make it non-empty by sinking
433 something into it. */ 456 something into it. */
434 if (sinkbb == frombb->loop_father->latch 457 if (sinkbb == frombb->loop_father->latch
435 && empty_block_p (sinkbb)) 458 && empty_block_p (sinkbb))
436 return false; 459 return false;
437 460
438 /* Move the expression to a post dominator can't reduce the number of
439 executions. */
440 if (dominated_by_p (CDI_POST_DOMINATORS, frombb, sinkbb))
441 return false;
442
443 *togsi = gsi_after_labels (sinkbb); 461 *togsi = gsi_after_labels (sinkbb);
444 462
445 return true; 463 return true;
446 } 464 }
447 465
466 if (e->flags & EDGE_ABNORMAL) 484 if (e->flags & EDGE_ABNORMAL)
467 goto earlyout; 485 goto earlyout;
468 486
469 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);) 487 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
470 { 488 {
471 gimple stmt = gsi_stmt (gsi); 489 gimple *stmt = gsi_stmt (gsi);
472 gimple_stmt_iterator togsi; 490 gimple_stmt_iterator togsi;
473 491 bool zero_uses_p;
474 if (!statement_sink_location (stmt, bb, &togsi)) 492
475 { 493 if (!statement_sink_location (stmt, bb, &togsi, &zero_uses_p))
494 {
495 gimple_stmt_iterator saved = gsi;
476 if (!gsi_end_p (gsi)) 496 if (!gsi_end_p (gsi))
477 gsi_prev (&gsi); 497 gsi_prev (&gsi);
478 last = false; 498 /* If we face a dead stmt remove it as it possibly blocks
499 sinking of uses. */
500 if (zero_uses_p
501 && ! gimple_vdef (stmt))
502 {
503 gsi_remove (&saved, true);
504 release_defs (stmt);
505 }
506 else
507 last = false;
479 continue; 508 continue;
480 } 509 }
481 if (dump_file) 510 if (dump_file)
482 { 511 {
483 fprintf (dump_file, "Sinking "); 512 fprintf (dump_file, "Sinking ");
484 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS); 513 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS);
485 fprintf (dump_file, " from bb %d to bb %d\n", 514 fprintf (dump_file, " from bb %d to bb %d\n",
486 bb->index, (gsi_bb (togsi))->index); 515 bb->index, (gsi_bb (togsi))->index);
516 }
517
518 /* Update virtual operands of statements in the path we
519 do not sink to. */
520 if (gimple_vdef (stmt))
521 {
522 imm_use_iterator iter;
523 use_operand_p use_p;
524 gimple *vuse_stmt;
525
526 FOR_EACH_IMM_USE_STMT (vuse_stmt, iter, gimple_vdef (stmt))
527 if (gimple_code (vuse_stmt) != GIMPLE_PHI)
528 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
529 SET_USE (use_p, gimple_vuse (stmt));
487 } 530 }
488 531
489 /* If this is the end of the basic block, we need to insert at the end 532 /* If this is the end of the basic block, we need to insert at the end
490 of the basic block. */ 533 of the basic block. */
491 if (gsi_end_p (togsi)) 534 if (gsi_end_p (togsi))
554 USE a_6. 597 USE a_6.
555 598
556 Note that this reduces the number of computations of a = b + c to 1 599 Note that this reduces the number of computations of a = b + c to 1
557 when we take the else edge, instead of 2. 600 when we take the else edge, instead of 2.
558 */ 601 */
559 static void 602 namespace {
560 execute_sink_code (void) 603
604 const pass_data pass_data_sink_code =
605 {
606 GIMPLE_PASS, /* type */
607 "sink", /* name */
608 OPTGROUP_NONE, /* optinfo_flags */
609 TV_TREE_SINK, /* tv_id */
610 /* PROP_no_crit_edges is ensured by running split_critical_edges in
611 pass_data_sink_code::execute (). */
612 ( PROP_cfg | PROP_ssa ), /* properties_required */
613 0, /* properties_provided */
614 0, /* properties_destroyed */
615 0, /* todo_flags_start */
616 TODO_update_ssa, /* todo_flags_finish */
617 };
618
619 class pass_sink_code : public gimple_opt_pass
620 {
621 public:
622 pass_sink_code (gcc::context *ctxt)
623 : gimple_opt_pass (pass_data_sink_code, ctxt)
624 {}
625
626 /* opt_pass methods: */
627 virtual bool gate (function *) { return flag_tree_sink != 0; }
628 virtual unsigned int execute (function *);
629
630 }; // class pass_sink_code
631
632 unsigned int
633 pass_sink_code::execute (function *fun)
561 { 634 {
562 loop_optimizer_init (LOOPS_NORMAL); 635 loop_optimizer_init (LOOPS_NORMAL);
563 636 split_critical_edges ();
564 connect_infinite_loops_to_exit (); 637 connect_infinite_loops_to_exit ();
565 memset (&sink_stats, 0, sizeof (sink_stats)); 638 memset (&sink_stats, 0, sizeof (sink_stats));
566 calculate_dominance_info (CDI_DOMINATORS); 639 calculate_dominance_info (CDI_DOMINATORS);
567 calculate_dominance_info (CDI_POST_DOMINATORS); 640 calculate_dominance_info (CDI_POST_DOMINATORS);
568 sink_code_in_bb (EXIT_BLOCK_PTR); 641 sink_code_in_bb (EXIT_BLOCK_PTR_FOR_FN (fun));
569 statistics_counter_event (cfun, "Sunk statements", sink_stats.sunk); 642 statistics_counter_event (fun, "Sunk statements", sink_stats.sunk);
570 free_dominance_info (CDI_POST_DOMINATORS); 643 free_dominance_info (CDI_POST_DOMINATORS);
571 remove_fake_exit_edges (); 644 remove_fake_exit_edges ();
572 loop_optimizer_finalize (); 645 loop_optimizer_finalize ();
573 } 646
574
575 /* Gate and execute functions for PRE. */
576
577 static unsigned int
578 do_sink (void)
579 {
580 execute_sink_code ();
581 return 0; 647 return 0;
582 } 648 }
583 649
584 static bool 650 } // anon namespace
585 gate_sink (void) 651
586 { 652 gimple_opt_pass *
587 return flag_tree_sink != 0; 653 make_pass_sink_code (gcc::context *ctxt)
588 } 654 {
589 655 return new pass_sink_code (ctxt);
590 struct gimple_opt_pass pass_sink_code = 656 }
591 {
592 {
593 GIMPLE_PASS,
594 "sink", /* name */
595 gate_sink, /* gate */
596 do_sink, /* execute */
597 NULL, /* sub */
598 NULL, /* next */
599 0, /* static_pass_number */
600 TV_TREE_SINK, /* tv_id */
601 PROP_no_crit_edges | PROP_cfg
602 | PROP_ssa, /* properties_required */
603 0, /* properties_provided */
604 0, /* properties_destroyed */
605 0, /* todo_flags_start */
606 TODO_update_ssa
607 | TODO_verify_ssa
608 | TODO_verify_flow
609 | TODO_dump_func
610 | TODO_ggc_collect /* todo_flags_finish */
611 }
612 };