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"
38 #include "tree-inline.h"
40 static int max_threaded_paths
;
42 /* Simple helper to get the last statement from BB, which is assumed
43 to be a control statement. Return NULL if the last statement is
44 not a control statement. */
47 get_gimple_control_stmt (basic_block bb
)
49 gimple_stmt_iterator gsi
= gsi_last_nondebug_bb (bb
);
54 gimple
*stmt
= gsi_stmt (gsi
);
55 enum gimple_code code
= gimple_code (stmt
);
56 if (code
== GIMPLE_COND
|| code
== GIMPLE_SWITCH
|| code
== GIMPLE_GOTO
)
61 /* Return true if the CFG contains at least one path from START_BB to END_BB.
62 When a path is found, record in PATH the blocks from END_BB to START_BB.
63 VISITED_BBS is used to make sure we don't fall into an infinite loop. Bound
64 the recursion to basic blocks belonging to LOOP. */
67 fsm_find_thread_path (basic_block start_bb
, basic_block end_bb
,
68 vec
<basic_block
, va_gc
> *&path
,
69 hash_set
<basic_block
> *visited_bbs
, loop_p loop
)
71 if (loop
!= start_bb
->loop_father
)
74 if (start_bb
== end_bb
)
76 vec_safe_push (path
, start_bb
);
80 if (!visited_bbs
->add (start_bb
))
84 FOR_EACH_EDGE (e
, ei
, start_bb
->succs
)
85 if (fsm_find_thread_path (e
->dest
, end_bb
, path
, visited_bbs
, loop
))
87 vec_safe_push (path
, start_bb
);
95 /* Examine jump threading path PATH to which we want to add BBI.
97 If the resulting path is profitable to thread, then return the
98 final taken edge from the path, NULL otherwise.
100 NAME is the SSA_NAME of the variable we found to have a constant
101 value on PATH. ARG is the value of that SSA_NAME.
103 BBI will be appended to PATH when we have a profitable jump threading
104 path. Callers are responsible for removing BBI from PATH in that case. */
107 profitable_jump_thread_path (vec
<basic_block
, va_gc
> *&path
,
108 basic_block bbi
, tree name
, tree arg
)
110 /* Note BBI is not in the path yet, hence the +1 in the test below
111 to make sure BBI is accounted for in the path length test. */
112 int path_length
= path
->length ();
114 /* We can get a length of 0 here when the statement that
115 makes a conditional generate a compile-time constant
116 result is in the same block as the conditional.
118 That's not really a jump threading opportunity, but instead is
119 simple cprop & simplification. We could handle it here if we
120 wanted by wiring up all the incoming edges. If we run this
121 early in IPA, that might be worth doing. For now we just
123 if (path_length
== 0)
126 if (path_length
+ 1 > PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH
))
128 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
129 fprintf (dump_file
, "FSM jump-thread path not considered: "
130 "the number of basic blocks on the path "
131 "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
135 if (max_threaded_paths
<= 0)
137 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
138 fprintf (dump_file
, "FSM jump-thread path not considered: "
139 "the number of previously recorded FSM paths to "
140 "thread exceeds PARAM_MAX_FSM_THREAD_PATHS.\n");
144 /* Add BBI to the path.
145 From this point onward, if we decide we the path is not profitable
146 to thread, we must remove BBI from the path. */
147 vec_safe_push (path
, bbi
);
151 gimple_stmt_iterator gsi
;
153 loop_p loop
= (*path
)[0]->loop_father
;
154 bool path_crosses_loops
= false;
155 bool threaded_through_latch
= false;
156 bool multiway_branch_in_path
= false;
157 bool threaded_multiway_branch
= false;
159 /* Count the number of instructions on the path: as these instructions
160 will have to be duplicated, we will not record the path if there
161 are too many instructions on the path. Also check that all the
162 blocks in the path belong to a single loop. */
163 for (j
= 0; j
< path_length
; j
++)
165 basic_block bb
= (*path
)[j
];
167 /* Remember, blocks in the path are stored in opposite order
168 in the PATH array. The last entry in the array represents
169 the block with an outgoing edge that we will redirect to the
170 jump threading path. Thus we don't care about that block's
171 loop father, nor how many statements are in that block because
172 it will not be copied or whether or not it ends in a multiway
174 if (j
< path_length
- 1)
176 if (bb
->loop_father
!= loop
)
178 path_crosses_loops
= true;
182 /* PHIs in the path will create degenerate PHIS in the
183 copied path which will then get propagated away, so
184 looking at just the duplicate path the PHIs would
187 But those PHIs, because they're assignments to objects
188 typically with lives that exist outside the thread path,
189 will tend to generate PHIs (or at least new PHI arguments)
190 at points where we leave the thread path and rejoin
191 the original blocks. So we do want to account for them.
193 We ignore virtual PHIs. We also ignore cases where BB
194 has a single incoming edge. That's the most common
195 degenerate PHI we'll see here. Finally we ignore PHIs
196 that are associated with the value we're tracking as
197 that object likely dies. */
198 if (EDGE_COUNT (bb
->succs
) > 1 && EDGE_COUNT (bb
->preds
) > 1)
200 for (gphi_iterator gsip
= gsi_start_phis (bb
);
204 gphi
*phi
= gsip
.phi ();
205 tree dst
= gimple_phi_result (phi
);
207 /* Note that if both NAME and DST are anonymous
208 SSA_NAMEs, then we do not have enough information
209 to consider them associated. */
210 if ((SSA_NAME_VAR (dst
) != SSA_NAME_VAR (name
)
211 || !SSA_NAME_VAR (dst
))
212 && !virtual_operand_p (dst
))
217 for (gsi
= gsi_after_labels (bb
);
219 gsi_next_nondebug (&gsi
))
221 gimple
*stmt
= gsi_stmt (gsi
);
222 /* Do not count empty statements and labels. */
223 if (gimple_code (stmt
) != GIMPLE_NOP
224 && !(gimple_code (stmt
) == GIMPLE_ASSIGN
225 && gimple_assign_rhs_code (stmt
) == ASSERT_EXPR
)
226 && !is_gimple_debug (stmt
))
227 n_insns
+= estimate_num_insns (stmt
, &eni_size_weights
);
230 /* We do not look at the block with the threaded branch
231 in this loop. So if any block with a last statement that
232 is a GIMPLE_SWITCH or GIMPLE_GOTO is seen, then we have a
233 multiway branch on our path.
235 The block in PATH[0] is special, it's the block were we're
236 going to be able to eliminate its branch. */
237 gimple
*last
= last_stmt (bb
);
238 if (last
&& (gimple_code (last
) == GIMPLE_SWITCH
239 || gimple_code (last
) == GIMPLE_GOTO
))
242 threaded_multiway_branch
= true;
244 multiway_branch_in_path
= true;
248 /* Note if we thread through the latch, we will want to include
249 the last entry in the array when determining if we thread
250 through the loop latch. */
251 if (loop
->latch
== bb
)
252 threaded_through_latch
= true;
255 gimple
*stmt
= get_gimple_control_stmt ((*path
)[0]);
258 /* We are going to remove the control statement at the end of the
259 last block in the threading path. So don't count it against our
262 n_insns
-= estimate_num_insns (stmt
, &eni_size_weights
);
264 /* We have found a constant value for ARG. For GIMPLE_SWITCH
265 and GIMPLE_GOTO, we use it as-is. However, for a GIMPLE_COND
266 we need to substitute, fold and simplify so we can determine
267 the edge taken out of the last block. */
268 if (gimple_code (stmt
) == GIMPLE_COND
)
270 enum tree_code cond_code
= gimple_cond_code (stmt
);
272 /* We know the underyling format of the condition. */
273 arg
= fold_binary (cond_code
, boolean_type_node
,
274 arg
, gimple_cond_rhs (stmt
));
277 /* If this path threaded through the loop latch back into the
278 same loop and the destination does not dominate the loop
279 latch, then this thread would create an irreducible loop.
281 We have to know the outgoing edge to figure this out. */
282 edge taken_edge
= find_taken_edge ((*path
)[0], arg
);
284 /* There are cases where we may not be able to extract the
285 taken edge. For example, a computed goto to an absolute
286 address. Handle those cases gracefully. */
287 if (taken_edge
== NULL
)
293 bool creates_irreducible_loop
= false;
294 if (threaded_through_latch
295 && loop
== taken_edge
->dest
->loop_father
296 && (determine_bb_domination_status (loop
, taken_edge
->dest
)
297 == DOMST_NONDOMINATING
))
298 creates_irreducible_loop
= true;
300 if (path_crosses_loops
)
302 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
303 fprintf (dump_file
, "FSM jump-thread path not considered: "
304 "the path crosses loops.\n");
309 if (optimize_edge_for_speed_p (taken_edge
))
311 if (n_insns
>= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATH_INSNS
))
313 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
314 fprintf (dump_file
, "FSM jump-thread path not considered: "
315 "the number of instructions on the path "
316 "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
321 else if (n_insns
> 1)
323 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
324 fprintf (dump_file
, "FSM jump-thread path not considered: "
325 "duplication of %i insns is needed and optimizing for size.\n",
331 /* We avoid creating irreducible inner loops unless we thread through
332 a multiway branch, in which case we have deemed it worth losing
333 other loop optimizations later.
335 We also consider it worth creating an irreducible inner loop if
336 the number of copied statement is low relative to the length of
337 the path -- in that case there's little the traditional loop
338 optimizer would have done anyway, so an irreducible loop is not
340 if (!threaded_multiway_branch
&& creates_irreducible_loop
341 && (n_insns
* PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS
)
342 > path_length
* PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS
)))
345 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
347 "FSM would create irreducible loop without threading "
348 "multiway branch.\n");
354 /* If this path does not thread through the loop latch, then we are
355 using the FSM threader to find old style jump threads. This
356 is good, except the FSM threader does not re-use an existing
357 threading path to reduce code duplication.
359 So for that case, drastically reduce the number of statements
360 we are allowed to copy. */
361 if (!(threaded_through_latch
&& threaded_multiway_branch
)
362 && (n_insns
* PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS
)
363 >= PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS
)))
365 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
367 "FSM did not thread around loop and would copy too "
368 "many statements.\n");
373 /* When there is a multi-way branch on the path, then threading can
374 explode the CFG due to duplicating the edges for that multi-way
375 branch. So like above, only allow a multi-way branch on the path
376 if we actually thread a multi-way branch. */
377 if (!threaded_multiway_branch
&& multiway_branch_in_path
)
379 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
381 "FSM Thread through multiway branch without threading "
382 "a multiway branch.\n");
389 /* PATH is vector of blocks forming a jump threading path in reverse
390 order. TAKEN_EDGE is the edge taken from path[0].
392 Convert that path into the form used by register_jump_thread and
393 register the path. */
396 convert_and_register_jump_thread_path (vec
<basic_block
, va_gc
> *path
,
399 vec
<jump_thread_edge
*> *jump_thread_path
= new vec
<jump_thread_edge
*> ();
401 /* Record the edges between the blocks in PATH. */
402 for (unsigned int j
= 0; j
< path
->length () - 1; j
++)
404 basic_block bb1
= (*path
)[path
->length () - j
- 1];
405 basic_block bb2
= (*path
)[path
->length () - j
- 2];
407 edge e
= find_edge (bb1
, bb2
);
409 jump_thread_edge
*x
= new jump_thread_edge (e
, EDGE_FSM_THREAD
);
410 jump_thread_path
->safe_push (x
);
413 /* Add the edge taken when the control variable has value ARG. */
415 = new jump_thread_edge (taken_edge
, EDGE_NO_COPY_SRC_BLOCK
);
416 jump_thread_path
->safe_push (x
);
418 register_jump_thread (jump_thread_path
);
419 --max_threaded_paths
;
422 /* We trace the value of the SSA_NAME NAME back through any phi nodes looking
423 for places where it gets a constant value and save the path. Stop after
424 having recorded MAX_PATHS jump threading paths. */
427 fsm_find_control_statement_thread_paths (tree name
,
428 hash_set
<basic_block
> *visited_bbs
,
429 vec
<basic_block
, va_gc
> *&path
,
432 /* If NAME appears in an abnormal PHI, then don't try to trace its
433 value back through PHI nodes. */
434 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name
))
437 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
438 basic_block var_bb
= gimple_bb (def_stmt
);
443 /* We allow the SSA chain to contains PHIs and simple copies and constant
445 if (gimple_code (def_stmt
) != GIMPLE_PHI
446 && gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
449 if (gimple_code (def_stmt
) == GIMPLE_PHI
450 && (gimple_phi_num_args (def_stmt
)
451 >= (unsigned) PARAM_VALUE (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS
)))
454 if (gimple_code (def_stmt
) == GIMPLE_ASSIGN
455 && gimple_assign_rhs_code (def_stmt
) != INTEGER_CST
456 && gimple_assign_rhs_code (def_stmt
) != SSA_NAME
)
459 /* Avoid infinite recursion. */
460 if (visited_bbs
->add (var_bb
))
463 int next_path_length
= 0;
464 basic_block last_bb_in_path
= path
->last ();
466 if (loop_containing_stmt (def_stmt
)->header
== gimple_bb (def_stmt
))
468 /* Do not walk through more than one loop PHI node. */
471 seen_loop_phi
= true;
474 if (bb_loop_depth (last_bb_in_path
) > bb_loop_depth (var_bb
))
477 /* Following the chain of SSA_NAME definitions, we jumped from a definition in
478 LAST_BB_IN_PATH to a definition in VAR_BB. When these basic blocks are
479 different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB. */
480 if (var_bb
!= last_bb_in_path
)
485 vec
<basic_block
, va_gc
> *next_path
;
486 vec_alloc (next_path
, 10);
488 /* When VAR_BB == LAST_BB_IN_PATH, then the first block in the path
489 will already be in VISITED_BBS. When they are not equal, then we
490 must ensure that first block is accounted for to ensure we do not
491 create bogus jump threading paths. */
492 visited_bbs
->add ((*path
)[0]);
493 FOR_EACH_EDGE (e
, ei
, last_bb_in_path
->preds
)
495 hash_set
<basic_block
> *visited_bbs
= new hash_set
<basic_block
>;
497 if (fsm_find_thread_path (var_bb
, e
->src
, next_path
, visited_bbs
,
498 e
->src
->loop_father
))
503 /* If there is more than one path, stop. */
506 vec_free (next_path
);
511 /* Stop if we have not found a path: this could occur when the recursion
512 is stopped by one of the bounds. */
515 vec_free (next_path
);
519 /* Make sure we haven't already visited any of the nodes in
520 NEXT_PATH. Don't add them here to avoid pollution. */
521 for (unsigned int i
= 0; i
< next_path
->length () - 1; i
++)
523 if (visited_bbs
->contains ((*next_path
)[i
])
524 || (bb_loop_depth (last_bb_in_path
)
525 > bb_loop_depth ((*next_path
)[i
])))
527 vec_free (next_path
);
532 /* Now add the nodes to VISISTED_BBS. */
533 for (unsigned int i
= 0; i
< next_path
->length () - 1; i
++)
534 visited_bbs
->add ((*next_path
)[i
]);
536 /* Append all the nodes from NEXT_PATH to PATH. */
537 vec_safe_splice (path
, next_path
);
538 next_path_length
= next_path
->length ();
539 vec_free (next_path
);
542 gcc_assert (path
->last () == var_bb
);
544 /* Iterate over the arguments of PHI. */
546 if (gimple_code (def_stmt
) == GIMPLE_PHI
)
548 gphi
*phi
= as_a
<gphi
*> (def_stmt
);
549 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
551 tree arg
= gimple_phi_arg_def (phi
, i
);
552 basic_block bbi
= gimple_phi_arg_edge (phi
, i
)->src
;
554 /* Skip edges pointing outside the current loop. */
555 if (!arg
|| var_bb
->loop_father
!= bbi
->loop_father
)
558 if (TREE_CODE (arg
) == SSA_NAME
)
560 vec_safe_push (path
, bbi
);
561 /* Recursively follow SSA_NAMEs looking for a constant
563 fsm_find_control_statement_thread_paths (arg
, visited_bbs
, path
,
570 if (TREE_CODE (arg
) != INTEGER_CST
)
573 /* If this is a profitable jump thread path, then convert it
574 into the canonical form and register it. */
575 edge taken_edge
= profitable_jump_thread_path (path
, bbi
, name
, arg
);
578 if (bb_loop_depth (taken_edge
->src
)
579 >= bb_loop_depth (taken_edge
->dest
))
580 convert_and_register_jump_thread_path (path
, taken_edge
);
585 else if (gimple_code (def_stmt
) == GIMPLE_ASSIGN
)
587 tree arg
= gimple_assign_rhs1 (def_stmt
);
589 if (TREE_CODE (arg
) == SSA_NAME
)
590 fsm_find_control_statement_thread_paths (arg
, visited_bbs
,
591 path
, seen_loop_phi
);
595 /* profitable_jump_thread_path is going to push the current
596 block onto the path. But the path will always have the current
597 block at this point. So we can just pop it. */
600 edge taken_edge
= profitable_jump_thread_path (path
, var_bb
,
604 if (bb_loop_depth (taken_edge
->src
)
605 >= bb_loop_depth (taken_edge
->dest
))
606 convert_and_register_jump_thread_path (path
, taken_edge
);
610 /* And put the current block back onto the path so that the
611 state of the stack is unchanged when we leave. */
612 vec_safe_push (path
, var_bb
);
616 /* Remove all the nodes that we added from NEXT_PATH. */
617 if (next_path_length
)
618 vec_safe_truncate (path
, (path
->length () - next_path_length
));
621 /* Search backwards from BB looking for paths where NAME (an SSA_NAME)
622 is a constant. Record such paths for jump threading.
624 It is assumed that BB ends with a control statement and that by
625 finding a path where NAME is a constant, we can thread the path. */
628 find_jump_threads_backwards (basic_block bb
)
630 gimple
*stmt
= get_gimple_control_stmt (bb
);
634 enum gimple_code code
= gimple_code (stmt
);
636 if (code
== GIMPLE_SWITCH
)
637 name
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
638 else if (code
== GIMPLE_GOTO
)
639 name
= gimple_goto_dest (stmt
);
640 else if (code
== GIMPLE_COND
)
642 if (TREE_CODE (gimple_cond_lhs (stmt
)) == SSA_NAME
643 && TREE_CODE (gimple_cond_rhs (stmt
)) == INTEGER_CST
644 && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt
)))
645 || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt
)))))
646 name
= gimple_cond_lhs (stmt
);
649 if (!name
|| TREE_CODE (name
) != SSA_NAME
)
652 vec
<basic_block
, va_gc
> *bb_path
;
653 vec_alloc (bb_path
, 10);
654 vec_safe_push (bb_path
, bb
);
655 hash_set
<basic_block
> *visited_bbs
= new hash_set
<basic_block
>;
657 max_threaded_paths
= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS
);
658 fsm_find_control_statement_thread_paths (name
, visited_bbs
, bb_path
, false);
666 const pass_data pass_data_thread_jumps
=
671 TV_TREE_SSA_THREAD_JUMPS
,
672 ( PROP_cfg
| PROP_ssa
),
676 ( TODO_cleanup_cfg
| TODO_update_ssa
),
679 class pass_thread_jumps
: public gimple_opt_pass
682 pass_thread_jumps (gcc::context
*ctxt
)
683 : gimple_opt_pass (pass_data_thread_jumps
, ctxt
)
686 opt_pass
* clone (void) { return new pass_thread_jumps (m_ctxt
); }
687 virtual bool gate (function
*);
688 virtual unsigned int execute (function
*);
692 pass_thread_jumps::gate (function
*fun ATTRIBUTE_UNUSED
)
694 return flag_expensive_optimizations
;
699 pass_thread_jumps::execute (function
*fun
)
701 /* Try to thread each block with more than one successor. */
703 FOR_EACH_BB_FN (bb
, fun
)
705 if (EDGE_COUNT (bb
->succs
) > 1)
706 find_jump_threads_backwards (bb
);
708 thread_through_all_blocks (true);
715 make_pass_thread_jumps (gcc::context
*ctxt
)
717 return new pass_thread_jumps (ctxt
);