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"
36 #include "gimple-ssa.h"
37 #include "tree-phinodes.h"
39 static int max_threaded_paths
;
41 /* Simple helper to get the last statement from BB, which is assumed
42 to be a control statement. Return NULL if the last statement is
43 not a control statement. */
46 get_gimple_control_stmt (basic_block bb
)
48 gimple_stmt_iterator gsi
= gsi_last_nondebug_bb (bb
);
53 gimple
*stmt
= gsi_stmt (gsi
);
54 enum gimple_code code
= gimple_code (stmt
);
55 if (code
== GIMPLE_COND
|| code
== GIMPLE_SWITCH
|| code
== GIMPLE_GOTO
)
60 /* Return true if the CFG contains at least one path from START_BB to END_BB.
61 When a path is found, record in PATH the blocks from END_BB to START_BB.
62 VISITED_BBS is used to make sure we don't fall into an infinite loop. Bound
63 the recursion to basic blocks belonging to LOOP. */
66 fsm_find_thread_path (basic_block start_bb
, basic_block end_bb
,
67 vec
<basic_block
, va_gc
> *&path
,
68 hash_set
<basic_block
> *visited_bbs
, loop_p loop
)
70 if (loop
!= start_bb
->loop_father
)
73 if (start_bb
== end_bb
)
75 vec_safe_push (path
, start_bb
);
79 if (!visited_bbs
->add (start_bb
))
83 FOR_EACH_EDGE (e
, ei
, start_bb
->succs
)
84 if (fsm_find_thread_path (e
->dest
, end_bb
, path
, visited_bbs
, loop
))
86 vec_safe_push (path
, start_bb
);
94 /* Examine jump threading path PATH to which we want to add BBI.
96 If the resulting path is profitable to thread, then return the
97 final taken edge from the path, NULL otherwise.
99 NAME is the SSA_NAME of the variable we found to have a constant
100 value on PATH. ARG is the value of that SSA_NAME.
102 BBI will be appended to PATH when we have a profitable jump threading
103 path. Callers are responsible for removing BBI from PATH in that case. */
106 profitable_jump_thread_path (vec
<basic_block
, va_gc
> *&path
,
107 basic_block bbi
, tree name
, tree arg
)
109 /* Note BBI is not in the path yet, hence the +1 in the test below
110 to make sure BBI is accounted for in the path length test. */
111 int path_length
= path
->length ();
112 if (path_length
+ 1 > PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH
))
114 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
115 fprintf (dump_file
, "FSM jump-thread path not considered: "
116 "the number of basic blocks on the path "
117 "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
121 if (max_threaded_paths
<= 0)
123 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
124 fprintf (dump_file
, "FSM jump-thread path not considered: "
125 "the number of previously recorded FSM paths to "
126 "thread exceeds PARAM_MAX_FSM_THREAD_PATHS.\n");
130 /* Add BBI to the path.
131 From this point onward, if we decide we the path is not profitable
132 to thread, we must remove BBI from the path. */
133 vec_safe_push (path
, bbi
);
137 gimple_stmt_iterator gsi
;
139 loop_p loop
= (*path
)[0]->loop_father
;
140 bool path_crosses_loops
= false;
141 bool threaded_through_latch
= false;
142 bool multiway_branch_in_path
= false;
143 bool threaded_multiway_branch
= false;
145 /* Count the number of instructions on the path: as these instructions
146 will have to be duplicated, we will not record the path if there
147 are too many instructions on the path. Also check that all the
148 blocks in the path belong to a single loop. */
149 for (j
= 0; j
< path_length
; j
++)
151 basic_block bb
= (*path
)[j
];
153 /* Remember, blocks in the path are stored in opposite order
154 in the PATH array. The last entry in the array represents
155 the block with an outgoing edge that we will redirect to the
156 jump threading path. Thus we don't care about that block's
157 loop father, nor how many statements are in that block because
158 it will not be copied or whether or not it ends in a multiway
160 if (j
< path_length
- 1)
162 if (bb
->loop_father
!= loop
)
164 path_crosses_loops
= true;
168 /* PHIs in the path will create degenerate PHIS in the
169 copied path which will then get propagated away, so
170 looking at just the duplicate path the PHIs would
173 But those PHIs, because they're assignments to objects
174 typically with lives that exist outside the thread path,
175 will tend to generate PHIs (or at least new PHI arguments)
176 at points where we leave the thread path and rejoin
177 the original blocks. So we do want to account for them.
179 We ignore virtual PHIs. We also ignore cases where BB
180 has a single incoming edge. That's the most common
181 degenerate PHI we'll see here. Finally we ignore PHIs
182 that are associated with the value we're tracking as
183 that object likely dies. */
184 if (EDGE_COUNT (bb
->succs
) > 1 && EDGE_COUNT (bb
->preds
) > 1)
186 for (gphi_iterator gsip
= gsi_start_phis (bb
);
190 gphi
*phi
= gsip
.phi ();
191 tree dst
= gimple_phi_result (phi
);
193 /* Note that if both NAME and DST are anonymous
194 SSA_NAMEs, then we do not have enough information
195 to consider them associated. */
196 if ((SSA_NAME_VAR (dst
) != SSA_NAME_VAR (name
)
197 || !SSA_NAME_VAR (dst
))
198 && !virtual_operand_p (dst
))
203 for (gsi
= gsi_after_labels (bb
);
205 gsi_next_nondebug (&gsi
))
207 gimple
*stmt
= gsi_stmt (gsi
);
208 /* Do not count empty statements and labels. */
209 if (gimple_code (stmt
) != GIMPLE_NOP
210 && !(gimple_code (stmt
) == GIMPLE_ASSIGN
211 && gimple_assign_rhs_code (stmt
) == ASSERT_EXPR
)
212 && !is_gimple_debug (stmt
))
216 /* We do not look at the block with the threaded branch
217 in this loop. So if any block with a last statement that
218 is a GIMPLE_SWITCH or GIMPLE_GOTO is seen, then we have a
219 multiway branch on our path.
221 The block in PATH[0] is special, it's the block were we're
222 going to be able to eliminate its branch. */
223 gimple
*last
= last_stmt (bb
);
224 if (last
&& (gimple_code (last
) == GIMPLE_SWITCH
225 || gimple_code (last
) == GIMPLE_GOTO
))
228 threaded_multiway_branch
= true;
230 multiway_branch_in_path
= true;
234 /* Note if we thread through the latch, we will want to include
235 the last entry in the array when determining if we thread
236 through the loop latch. */
237 if (loop
->latch
== bb
)
238 threaded_through_latch
= true;
241 /* We are going to remove the control statement at the end of the
242 last block in the threading path. So don't count it against our
246 gimple
*stmt
= get_gimple_control_stmt ((*path
)[0]);
248 /* We have found a constant value for ARG. For GIMPLE_SWITCH
249 and GIMPLE_GOTO, we use it as-is. However, for a GIMPLE_COND
250 we need to substitute, fold and simplify so we can determine
251 the edge taken out of the last block. */
252 if (gimple_code (stmt
) == GIMPLE_COND
)
254 enum tree_code cond_code
= gimple_cond_code (stmt
);
256 /* We know the underyling format of the condition. */
257 arg
= fold_binary (cond_code
, boolean_type_node
,
258 arg
, gimple_cond_rhs (stmt
));
261 /* If this path threaded through the loop latch back into the
262 same loop and the destination does not dominate the loop
263 latch, then this thread would create an irreducible loop.
265 We have to know the outgoing edge to figure this out. */
266 edge taken_edge
= find_taken_edge ((*path
)[0], arg
);
268 /* There are cases where we may not be able to extract the
269 taken edge. For example, a computed goto to an absolute
270 address. Handle those cases gracefully. */
271 if (taken_edge
== NULL
)
277 bool creates_irreducible_loop
= false;
278 if (threaded_through_latch
279 && loop
== taken_edge
->dest
->loop_father
280 && (determine_bb_domination_status (loop
, taken_edge
->dest
)
281 == DOMST_NONDOMINATING
))
282 creates_irreducible_loop
= true;
284 if (path_crosses_loops
)
286 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
287 fprintf (dump_file
, "FSM jump-thread path not considered: "
288 "the path crosses loops.\n");
293 if (n_insns
>= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATH_INSNS
))
295 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
296 fprintf (dump_file
, "FSM jump-thread path not considered: "
297 "the number of instructions on the path "
298 "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
303 /* We avoid creating irreducible inner loops unless we thread through
304 a multiway branch, in which case we have deemed it worth losing
305 other loop optimizations later.
307 We also consider it worth creating an irreducible inner loop if
308 the number of copied statement is low relative to the length of
309 the path -- in that case there's little the traditional loop
310 optimizer would have done anyway, so an irreducible loop is not
312 if (!threaded_multiway_branch
&& creates_irreducible_loop
313 && (n_insns
* PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS
)
314 > path_length
* PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS
)))
317 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
319 "FSM would create irreducible loop without threading "
320 "multiway branch.\n");
326 /* If this path does not thread through the loop latch, then we are
327 using the FSM threader to find old style jump threads. This
328 is good, except the FSM threader does not re-use an existing
329 threading path to reduce code duplication.
331 So for that case, drastically reduce the number of statements
332 we are allowed to copy. */
333 if (!(threaded_through_latch
&& threaded_multiway_branch
)
334 && (n_insns
* PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS
)
335 >= PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS
)))
337 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
339 "FSM did not thread around loop and would copy too "
340 "many statements.\n");
345 /* When there is a multi-way branch on the path, then threading can
346 explode the CFG due to duplicating the edges for that multi-way
347 branch. So like above, only allow a multi-way branch on the path
348 if we actually thread a multi-way branch. */
349 if (!threaded_multiway_branch
&& multiway_branch_in_path
)
351 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
353 "FSM Thread through multiway branch without threading "
354 "a multiway branch.\n");
361 /* PATH is vector of blocks forming a jump threading path in reverse
362 order. TAKEN_EDGE is the edge taken from path[0].
364 Convert that path into the form used by register_jump_thread and
365 register the path. */
368 convert_and_register_jump_thread_path (vec
<basic_block
, va_gc
> *&path
,
371 vec
<jump_thread_edge
*> *jump_thread_path
= new vec
<jump_thread_edge
*> ();
373 /* Record the edges between the blocks in PATH. */
374 for (unsigned int j
= 0; j
< path
->length () - 1; j
++)
376 basic_block bb1
= (*path
)[path
->length () - j
- 1];
377 basic_block bb2
= (*path
)[path
->length () - j
- 2];
379 /* This can happen when we have an SSA_NAME as a PHI argument and
380 its initialization block is the head of the PHI argument's
385 edge e
= find_edge (bb1
, bb2
);
387 jump_thread_edge
*x
= new jump_thread_edge (e
, EDGE_FSM_THREAD
);
388 jump_thread_path
->safe_push (x
);
391 /* As a consequence of the test for duplicate blocks in the path
392 above, we can get a path with no blocks. This happens if a
393 conditional can be fully evaluated at compile time using just
394 defining statements in the same block as the test.
396 When we no longer push the block associated with a PHI argument
397 onto the stack, then this as well as the test in the loop above
399 if (jump_thread_path
->length () == 0)
401 jump_thread_path
->release ();
402 delete jump_thread_path
;
407 /* Add the edge taken when the control variable has value ARG. */
409 = new jump_thread_edge (taken_edge
, EDGE_NO_COPY_SRC_BLOCK
);
410 jump_thread_path
->safe_push (x
);
412 register_jump_thread (jump_thread_path
);
413 --max_threaded_paths
;
415 /* Remove BBI from the path. */
419 /* We trace the value of the SSA_NAME NAME back through any phi nodes looking
420 for places where it gets a constant value and save the path. Stop after
421 having recorded MAX_PATHS jump threading paths. */
424 fsm_find_control_statement_thread_paths (tree name
,
425 hash_set
<basic_block
> *visited_bbs
,
426 vec
<basic_block
, va_gc
> *&path
,
429 /* If NAME appears in an abnormal PHI, then don't try to trace its
430 value back through PHI nodes. */
431 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name
))
434 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
435 basic_block var_bb
= gimple_bb (def_stmt
);
440 /* We allow the SSA chain to contains PHIs and simple copies and constant
442 if (gimple_code (def_stmt
) != GIMPLE_PHI
443 && gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
446 if (gimple_code (def_stmt
) == GIMPLE_PHI
447 && (gimple_phi_num_args (def_stmt
)
448 >= (unsigned) PARAM_VALUE (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS
)))
451 if (gimple_code (def_stmt
) == GIMPLE_ASSIGN
452 && gimple_assign_rhs_code (def_stmt
) != INTEGER_CST
453 && gimple_assign_rhs_code (def_stmt
) != SSA_NAME
)
456 /* Avoid infinite recursion. */
457 if (visited_bbs
->add (var_bb
))
460 int next_path_length
= 0;
461 basic_block last_bb_in_path
= path
->last ();
463 if (loop_containing_stmt (def_stmt
)->header
== gimple_bb (def_stmt
))
465 /* Do not walk through more than one loop PHI node. */
468 seen_loop_phi
= true;
471 /* Following the chain of SSA_NAME definitions, we jumped from a definition in
472 LAST_BB_IN_PATH to a definition in VAR_BB. When these basic blocks are
473 different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB. */
474 if (var_bb
!= last_bb_in_path
)
479 vec
<basic_block
, va_gc
> *next_path
;
480 vec_alloc (next_path
, 10);
482 /* When VAR_BB == LAST_BB_IN_PATH, then the first block in the path
483 will already be in VISITED_BBS. When they are not equal, then we
484 must ensure that first block is accounted for to ensure we do not
485 create bogus jump threading paths. */
486 visited_bbs
->add ((*path
)[0]);
487 FOR_EACH_EDGE (e
, ei
, last_bb_in_path
->preds
)
489 hash_set
<basic_block
> *visited_bbs
= new hash_set
<basic_block
>;
491 if (fsm_find_thread_path (var_bb
, e
->src
, next_path
, visited_bbs
,
492 e
->src
->loop_father
))
497 /* If there is more than one path, stop. */
500 vec_free (next_path
);
505 /* Stop if we have not found a path: this could occur when the recursion
506 is stopped by one of the bounds. */
509 vec_free (next_path
);
513 /* Make sure we haven't already visited any of the nodes in
514 NEXT_PATH. Don't add them here to avoid pollution. */
515 for (unsigned int i
= 0; i
< next_path
->length () - 1; i
++)
517 if (visited_bbs
->contains ((*next_path
)[i
]))
519 vec_free (next_path
);
524 /* Now add the nodes to VISISTED_BBS. */
525 for (unsigned int i
= 0; i
< next_path
->length () - 1; i
++)
526 visited_bbs
->add ((*next_path
)[i
]);
528 /* Append all the nodes from NEXT_PATH to PATH. */
529 vec_safe_splice (path
, next_path
);
530 next_path_length
= next_path
->length ();
531 vec_free (next_path
);
534 gcc_assert (path
->last () == var_bb
);
536 /* Iterate over the arguments of PHI. */
538 if (gimple_code (def_stmt
) == GIMPLE_PHI
)
540 gphi
*phi
= as_a
<gphi
*> (def_stmt
);
541 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
543 tree arg
= gimple_phi_arg_def (phi
, i
);
544 basic_block bbi
= gimple_phi_arg_edge (phi
, i
)->src
;
546 /* Skip edges pointing outside the current loop. */
547 if (!arg
|| var_bb
->loop_father
!= bbi
->loop_father
)
550 if (TREE_CODE (arg
) == SSA_NAME
)
552 vec_safe_push (path
, bbi
);
553 /* Recursively follow SSA_NAMEs looking for a constant
555 fsm_find_control_statement_thread_paths (arg
, visited_bbs
, path
,
562 if (TREE_CODE (arg
) != INTEGER_CST
)
565 /* If this is a profitable jump thread path, then convert it
566 into the canonical form and register it. */
567 edge taken_edge
= profitable_jump_thread_path (path
, bbi
, name
, arg
);
569 convert_and_register_jump_thread_path (path
, taken_edge
);
572 else if (gimple_code (def_stmt
) == GIMPLE_ASSIGN
)
574 tree arg
= gimple_assign_rhs1 (def_stmt
);
576 if (TREE_CODE (arg
) == SSA_NAME
)
577 fsm_find_control_statement_thread_paths (arg
, visited_bbs
,
578 path
, seen_loop_phi
);
582 edge taken_edge
= profitable_jump_thread_path (path
, var_bb
,
585 convert_and_register_jump_thread_path (path
, taken_edge
);
589 /* Remove all the nodes that we added from NEXT_PATH. */
590 if (next_path_length
)
591 vec_safe_truncate (path
, (path
->length () - next_path_length
));
594 /* Search backwards from BB looking for paths where NAME (an SSA_NAME)
595 is a constant. Record such paths for jump threading.
597 It is assumed that BB ends with a control statement and that by
598 finding a path where NAME is a constant, we can thread the path. */
601 find_jump_threads_backwards (basic_block bb
)
603 if (!flag_expensive_optimizations
604 || optimize_function_for_size_p (cfun
))
607 gimple
*stmt
= get_gimple_control_stmt (bb
);
611 enum gimple_code code
= gimple_code (stmt
);
613 if (code
== GIMPLE_SWITCH
)
614 name
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
615 else if (code
== GIMPLE_GOTO
)
616 name
= gimple_goto_dest (stmt
);
617 else if (code
== GIMPLE_COND
)
619 if (TREE_CODE (gimple_cond_lhs (stmt
)) == SSA_NAME
620 && TREE_CODE (gimple_cond_rhs (stmt
)) == INTEGER_CST
621 && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt
)))
622 || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt
)))))
623 name
= gimple_cond_lhs (stmt
);
626 if (!name
|| TREE_CODE (name
) != SSA_NAME
)
629 vec
<basic_block
, va_gc
> *bb_path
;
630 vec_alloc (bb_path
, 10);
631 vec_safe_push (bb_path
, bb
);
632 hash_set
<basic_block
> *visited_bbs
= new hash_set
<basic_block
>;
634 max_threaded_paths
= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS
);
635 fsm_find_control_statement_thread_paths (name
, visited_bbs
, bb_path
, false);
643 const pass_data pass_data_thread_jumps
=
648 TV_TREE_SSA_THREAD_JUMPS
,
649 ( PROP_cfg
| PROP_ssa
),
653 ( TODO_cleanup_cfg
| TODO_update_ssa
),
656 class pass_thread_jumps
: public gimple_opt_pass
659 pass_thread_jumps (gcc::context
*ctxt
)
660 : gimple_opt_pass (pass_data_thread_jumps
, ctxt
)
663 opt_pass
* clone (void) { return new pass_thread_jumps (m_ctxt
); }
664 virtual bool gate (function
*);
665 virtual unsigned int execute (function
*);
669 pass_thread_jumps::gate (function
*fun ATTRIBUTE_UNUSED
)
671 return (flag_expensive_optimizations
672 && ! optimize_function_for_size_p (cfun
));
677 pass_thread_jumps::execute (function
*fun
)
679 /* Try to thread each block with more than one successor. */
681 FOR_EACH_BB_FN (bb
, fun
)
683 if (EDGE_COUNT (bb
->succs
) > 1)
684 find_jump_threads_backwards (bb
);
686 thread_through_all_blocks (true);
693 make_pass_thread_jumps (gcc::context
*ctxt
)
695 return new pass_thread_jumps (ctxt
);