2 Copyright (C) 2005-2016 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
27 #include "fold-const.h"
29 #include "gimple-iterator.h"
31 #include "tree-ssa-threadupdate.h"
33 #include "tree-ssa-loop.h"
35 #include "tree-pass.h"
37 static int max_threaded_paths
;
39 /* Simple helper to get the last statement from BB, which is assumed
40 to be a control statement. Return NULL if the last statement is
41 not a control statement. */
44 get_gimple_control_stmt (basic_block bb
)
46 gimple_stmt_iterator gsi
= gsi_last_nondebug_bb (bb
);
51 gimple
*stmt
= gsi_stmt (gsi
);
52 enum gimple_code code
= gimple_code (stmt
);
53 if (code
== GIMPLE_COND
|| code
== GIMPLE_SWITCH
|| code
== GIMPLE_GOTO
)
58 /* Return true if the CFG contains at least one path from START_BB to END_BB.
59 When a path is found, record in PATH the blocks from END_BB to START_BB.
60 VISITED_BBS is used to make sure we don't fall into an infinite loop. Bound
61 the recursion to basic blocks belonging to LOOP. */
64 fsm_find_thread_path (basic_block start_bb
, basic_block end_bb
,
65 vec
<basic_block
, va_gc
> *&path
,
66 hash_set
<basic_block
> *visited_bbs
, loop_p loop
)
68 if (loop
!= start_bb
->loop_father
)
71 if (start_bb
== end_bb
)
73 vec_safe_push (path
, start_bb
);
77 if (!visited_bbs
->add (start_bb
))
81 FOR_EACH_EDGE (e
, ei
, start_bb
->succs
)
82 if (fsm_find_thread_path (e
->dest
, end_bb
, path
, visited_bbs
, loop
))
84 vec_safe_push (path
, start_bb
);
92 /* We trace the value of the SSA_NAME NAME back through any phi nodes looking
93 for places where it gets a constant value and save the path. Stop after
94 having recorded MAX_PATHS jump threading paths. */
97 fsm_find_control_statement_thread_paths (tree name
,
98 hash_set
<basic_block
> *visited_bbs
,
99 vec
<basic_block
, va_gc
> *&path
,
102 /* If NAME appears in an abnormal PHI, then don't try to trace its
103 value back through PHI nodes. */
104 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name
))
107 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
108 basic_block var_bb
= gimple_bb (def_stmt
);
113 /* For the moment we assume that an SSA chain only contains phi nodes, and
114 eventually one of the phi arguments will be an integer constant. In the
115 future, this could be extended to also handle simple assignments of
116 arithmetic operations. */
117 if (gimple_code (def_stmt
) != GIMPLE_PHI
118 || (gimple_phi_num_args (def_stmt
)
119 >= (unsigned) PARAM_VALUE (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS
)))
122 /* Avoid infinite recursion. */
123 if (visited_bbs
->add (var_bb
))
126 gphi
*phi
= as_a
<gphi
*> (def_stmt
);
127 int next_path_length
= 0;
128 basic_block last_bb_in_path
= path
->last ();
130 if (loop_containing_stmt (phi
)->header
== gimple_bb (phi
))
132 /* Do not walk through more than one loop PHI node. */
135 seen_loop_phi
= true;
138 /* Following the chain of SSA_NAME definitions, we jumped from a definition in
139 LAST_BB_IN_PATH to a definition in VAR_BB. When these basic blocks are
140 different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB. */
141 if (var_bb
!= last_bb_in_path
)
146 vec
<basic_block
, va_gc
> *next_path
;
147 vec_alloc (next_path
, 10);
149 /* When VAR_BB == LAST_BB_IN_PATH, then the first block in the path
150 will already be in VISITED_BBS. When they are not equal, then we
151 must ensure that first block is accounted for to ensure we do not
152 create bogus jump threading paths. */
153 visited_bbs
->add ((*path
)[0]);
154 FOR_EACH_EDGE (e
, ei
, last_bb_in_path
->preds
)
156 hash_set
<basic_block
> *visited_bbs
= new hash_set
<basic_block
>;
158 if (fsm_find_thread_path (var_bb
, e
->src
, next_path
, visited_bbs
,
159 e
->src
->loop_father
))
164 /* If there is more than one path, stop. */
167 vec_free (next_path
);
172 /* Stop if we have not found a path: this could occur when the recursion
173 is stopped by one of the bounds. */
176 vec_free (next_path
);
180 /* Make sure we haven't already visited any of the nodes in
181 NEXT_PATH. Don't add them here to avoid pollution. */
182 for (unsigned int i
= 0; i
< next_path
->length () - 1; i
++)
184 if (visited_bbs
->contains ((*next_path
)[i
]))
186 vec_free (next_path
);
191 /* Now add the nodes to VISISTED_BBS. */
192 for (unsigned int i
= 0; i
< next_path
->length () - 1; i
++)
193 visited_bbs
->add ((*next_path
)[i
]);
195 /* Append all the nodes from NEXT_PATH to PATH. */
196 vec_safe_splice (path
, next_path
);
197 next_path_length
= next_path
->length ();
198 vec_free (next_path
);
201 gcc_assert (path
->last () == var_bb
);
203 /* Iterate over the arguments of PHI. */
205 if (gimple_phi_num_args (phi
)
206 < (unsigned) PARAM_VALUE (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS
))
208 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
210 tree arg
= gimple_phi_arg_def (phi
, i
);
211 basic_block bbi
= gimple_phi_arg_edge (phi
, i
)->src
;
213 /* Skip edges pointing outside the current loop. */
214 if (!arg
|| var_bb
->loop_father
!= bbi
->loop_father
)
217 if (TREE_CODE (arg
) == SSA_NAME
)
219 vec_safe_push (path
, bbi
);
220 /* Recursively follow SSA_NAMEs looking for a constant
222 fsm_find_control_statement_thread_paths (arg
, visited_bbs
, path
,
229 if (TREE_CODE (arg
) != INTEGER_CST
)
232 /* Note BBI is not in the path yet, hence the +1 in the test below
233 to make sure BBI is accounted for in the path length test. */
234 int path_length
= path
->length ();
235 if (path_length
+ 1 > PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH
))
237 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
238 fprintf (dump_file
, "FSM jump-thread path not considered: "
239 "the number of basic blocks on the path "
240 "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
244 if (max_threaded_paths
<= 0)
246 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
247 fprintf (dump_file
, "FSM jump-thread path not considered: "
248 "the number of previously recorded FSM paths to "
249 "thread exceeds PARAM_MAX_FSM_THREAD_PATHS.\n");
253 /* Add BBI to the path. */
254 vec_safe_push (path
, bbi
);
258 gimple_stmt_iterator gsi
;
260 loop_p loop
= (*path
)[0]->loop_father
;
261 bool path_crosses_loops
= false;
262 bool threaded_through_latch
= false;
263 bool multiway_branch_in_path
= false;
264 bool threaded_multiway_branch
= false;
266 /* Count the number of instructions on the path: as these instructions
267 will have to be duplicated, we will not record the path if there
268 are too many instructions on the path. Also check that all the
269 blocks in the path belong to a single loop. */
270 for (j
= 0; j
< path_length
; j
++)
272 basic_block bb
= (*path
)[j
];
274 /* Remember, blocks in the path are stored in opposite order
275 in the PATH array. The last entry in the array represents
276 the block with an outgoing edge that we will redirect to the
277 jump threading path. Thus we don't care about that block's
278 loop father, nor how many statements are in that block because
279 it will not be copied or whether or not it ends in a multiway
281 if (j
< path_length
- 1)
283 if (bb
->loop_father
!= loop
)
285 path_crosses_loops
= true;
289 /* PHIs in the path will create degenerate PHIS in the
290 copied path which will then get propagated away, so
291 looking at just the duplicate path the PHIs would
294 But those PHIs, because they're assignments to objects
295 typically with lives that exist outside the thread path,
296 will tend to generate PHIs (or at least new PHI arguments)
297 at points where we leave the thread path and rejoin
298 the original blocks. So we do want to account for them.
300 We ignore virtual PHIs. We also ignore cases where BB
301 has a single incoming edge. That's the most common
302 degenerate PHI we'll see here. Finally we ignore PHIs
303 that are associated with the value we're tracking as
304 that object likely dies. */
305 if (EDGE_COUNT (bb
->succs
) > 1 && EDGE_COUNT (bb
->preds
) > 1)
307 for (gphi_iterator gsip
= gsi_start_phis (bb
);
311 gphi
*phi
= gsip
.phi ();
312 tree dst
= gimple_phi_result (phi
);
314 /* Note that if both NAME and DST are anonymous
315 SSA_NAMEs, then we do not have enough information
316 to consider them associated. */
317 if ((SSA_NAME_VAR (dst
) != SSA_NAME_VAR (name
)
318 || !SSA_NAME_VAR (dst
))
319 && !virtual_operand_p (dst
))
324 for (gsi
= gsi_after_labels (bb
);
326 gsi_next_nondebug (&gsi
))
328 gimple
*stmt
= gsi_stmt (gsi
);
329 /* Do not count empty statements and labels. */
330 if (gimple_code (stmt
) != GIMPLE_NOP
331 && !(gimple_code (stmt
) == GIMPLE_ASSIGN
332 && gimple_assign_rhs_code (stmt
) == ASSERT_EXPR
)
333 && !is_gimple_debug (stmt
))
337 /* We do not look at the block with the threaded branch
338 in this loop. So if any block with a last statement that
339 is a GIMPLE_SWITCH or GIMPLE_GOTO is seen, then we have a
340 multiway branch on our path.
342 The block in PATH[0] is special, it's the block were we're
343 going to be able to eliminate its branch. */
344 gimple
*last
= last_stmt (bb
);
345 if (last
&& (gimple_code (last
) == GIMPLE_SWITCH
346 || gimple_code (last
) == GIMPLE_GOTO
))
349 threaded_multiway_branch
= true;
351 multiway_branch_in_path
= true;
355 /* Note if we thread through the latch, we will want to include
356 the last entry in the array when determining if we thread
357 through the loop latch. */
358 if (loop
->latch
== bb
)
359 threaded_through_latch
= true;
362 /* We are going to remove the control statement at the end of the
363 last block in the threading path. So don't count it against our
367 gimple
*stmt
= get_gimple_control_stmt ((*path
)[0]);
369 /* We have found a constant value for ARG. For GIMPLE_SWITCH
370 and GIMPLE_GOTO, we use it as-is. However, for a GIMPLE_COND
371 we need to substitute, fold and simplify so we can determine
372 the edge taken out of the last block. */
373 if (gimple_code (stmt
) == GIMPLE_COND
)
375 enum tree_code cond_code
= gimple_cond_code (stmt
);
377 /* We know the underyling format of the condition. */
378 arg
= fold_binary (cond_code
, boolean_type_node
,
379 arg
, gimple_cond_rhs (stmt
));
382 /* If this path threaded through the loop latch back into the
383 same loop and the destination does not dominate the loop
384 latch, then this thread would create an irreducible loop.
386 We have to know the outgoing edge to figure this out. */
387 edge taken_edge
= find_taken_edge ((*path
)[0], arg
);
389 /* There are cases where we may not be able to extract the
390 taken edge. For example, a computed goto to an absolute
391 address. Handle those cases gracefully. */
392 if (taken_edge
== NULL
)
398 bool creates_irreducible_loop
= false;
399 if (threaded_through_latch
400 && loop
== taken_edge
->dest
->loop_father
401 && (determine_bb_domination_status (loop
, taken_edge
->dest
)
402 == DOMST_NONDOMINATING
))
403 creates_irreducible_loop
= true;
405 if (path_crosses_loops
)
407 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
408 fprintf (dump_file
, "FSM jump-thread path not considered: "
409 "the path crosses loops.\n");
414 if (n_insns
>= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATH_INSNS
))
416 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
417 fprintf (dump_file
, "FSM jump-thread path not considered: "
418 "the number of instructions on the path "
419 "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
424 /* We avoid creating irreducible inner loops unless we thread through
425 a multiway branch, in which case we have deemed it worth losing
426 other loop optimizations later.
428 We also consider it worth creating an irreducible inner loop if
429 the number of copied statement is low relative to the length of
430 the path -- in that case there's little the traditional loop
431 optimizer would have done anyway, so an irreducible loop is not
433 if (!threaded_multiway_branch
&& creates_irreducible_loop
434 && (n_insns
* PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS
)
435 > path_length
* PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS
)))
438 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
440 "FSM would create irreducible loop without threading "
441 "multiway branch.\n");
447 /* If this path does not thread through the loop latch, then we are
448 using the FSM threader to find old style jump threads. This
449 is good, except the FSM threader does not re-use an existing
450 threading path to reduce code duplication.
452 So for that case, drastically reduce the number of statements
453 we are allowed to copy. */
454 if (!(threaded_through_latch
&& threaded_multiway_branch
)
455 && (n_insns
* PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS
)
456 >= PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS
)))
458 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
460 "FSM did not thread around loop and would copy too "
461 "many statements.\n");
466 /* When there is a multi-way branch on the path, then threading can
467 explode the CFG due to duplicating the edges for that multi-way
468 branch. So like above, only allow a multi-way branch on the path
469 if we actually thread a multi-way branch. */
470 if (!threaded_multiway_branch
&& multiway_branch_in_path
)
472 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
474 "FSM Thread through multiway branch without threading "
475 "a multiway branch.\n");
480 vec
<jump_thread_edge
*> *jump_thread_path
481 = new vec
<jump_thread_edge
*> ();
483 /* Record the edges between the blocks in PATH. */
484 for (j
= 0; j
< path_length
- 1; j
++)
486 edge e
= find_edge ((*path
)[path_length
- j
- 1],
487 (*path
)[path_length
- j
- 2]);
489 jump_thread_edge
*x
= new jump_thread_edge (e
, EDGE_FSM_THREAD
);
490 jump_thread_path
->safe_push (x
);
493 /* Add the edge taken when the control variable has value ARG. */
495 = new jump_thread_edge (taken_edge
, EDGE_NO_COPY_SRC_BLOCK
);
496 jump_thread_path
->safe_push (x
);
498 register_jump_thread (jump_thread_path
);
499 --max_threaded_paths
;
501 /* Remove BBI from the path. */
506 /* Remove all the nodes that we added from NEXT_PATH. */
507 if (next_path_length
)
508 vec_safe_truncate (path
, (path
->length () - next_path_length
));
511 /* Search backwards from BB looking for paths where NAME (an SSA_NAME)
512 is a constant. Record such paths for jump threading.
514 It is assumed that BB ends with a control statement and that by
515 finding a path where NAME is a constant, we can thread the path. */
518 find_jump_threads_backwards (edge e
)
520 if (!flag_expensive_optimizations
521 || optimize_function_for_size_p (cfun
)
522 || e
->dest
->loop_father
!= e
->src
->loop_father
523 || loop_depth (e
->dest
->loop_father
) == 0)
526 gimple
*stmt
= get_gimple_control_stmt (e
->dest
);
530 enum gimple_code code
= gimple_code (stmt
);
532 if (code
== GIMPLE_SWITCH
)
533 name
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
534 else if (code
== GIMPLE_GOTO
)
535 name
= gimple_goto_dest (stmt
);
536 else if (code
== GIMPLE_COND
)
538 if (TREE_CODE (gimple_cond_lhs (stmt
)) == SSA_NAME
539 && TREE_CODE (gimple_cond_rhs (stmt
)) == INTEGER_CST
540 && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt
)))
541 || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt
)))))
542 name
= gimple_cond_lhs (stmt
);
545 if (!name
|| TREE_CODE (name
) != SSA_NAME
)
548 vec
<basic_block
, va_gc
> *bb_path
;
549 vec_alloc (bb_path
, 10);
550 vec_safe_push (bb_path
, e
->dest
);
551 hash_set
<basic_block
> *visited_bbs
= new hash_set
<basic_block
>;
553 max_threaded_paths
= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS
);
554 fsm_find_control_statement_thread_paths (name
, visited_bbs
, bb_path
, false);