2 Copyright (C) 2005-2015 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. */
42 get_gimple_control_stmt (basic_block bb
)
44 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
49 gimple
*stmt
= gsi_stmt (gsi
);
50 enum gimple_code code
= gimple_code (stmt
);
51 gcc_assert (code
== GIMPLE_COND
|| code
== GIMPLE_SWITCH
|| code
== GIMPLE_GOTO
);
55 /* Return true if the CFG contains at least one path from START_BB to END_BB.
56 When a path is found, record in PATH the blocks from END_BB to START_BB.
57 VISITED_BBS is used to make sure we don't fall into an infinite loop. Bound
58 the recursion to basic blocks belonging to LOOP. */
61 fsm_find_thread_path (basic_block start_bb
, basic_block end_bb
,
62 vec
<basic_block
, va_gc
> *&path
,
63 hash_set
<basic_block
> *visited_bbs
, loop_p loop
)
65 if (loop
!= start_bb
->loop_father
)
68 if (start_bb
== end_bb
)
70 vec_safe_push (path
, start_bb
);
74 if (!visited_bbs
->add (start_bb
))
78 FOR_EACH_EDGE (e
, ei
, start_bb
->succs
)
79 if (fsm_find_thread_path (e
->dest
, end_bb
, path
, visited_bbs
, loop
))
81 vec_safe_push (path
, start_bb
);
89 /* We trace the value of the SSA_NAME NAME back through any phi nodes looking
90 for places where it gets a constant value and save the path. Stop after
91 having recorded MAX_PATHS jump threading paths. */
94 fsm_find_control_statement_thread_paths (tree name
,
95 hash_set
<basic_block
> *visited_bbs
,
96 vec
<basic_block
, va_gc
> *&path
,
99 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
100 basic_block var_bb
= gimple_bb (def_stmt
);
105 /* For the moment we assume that an SSA chain only contains phi nodes, and
106 eventually one of the phi arguments will be an integer constant. In the
107 future, this could be extended to also handle simple assignments of
108 arithmetic operations. */
109 if (gimple_code (def_stmt
) != GIMPLE_PHI
)
112 /* Avoid infinite recursion. */
113 if (visited_bbs
->add (var_bb
))
116 gphi
*phi
= as_a
<gphi
*> (def_stmt
);
117 int next_path_length
= 0;
118 basic_block last_bb_in_path
= path
->last ();
120 if (loop_containing_stmt (phi
)->header
== gimple_bb (phi
))
122 /* Do not walk through more than one loop PHI node. */
125 seen_loop_phi
= true;
128 /* Following the chain of SSA_NAME definitions, we jumped from a definition in
129 LAST_BB_IN_PATH to a definition in VAR_BB. When these basic blocks are
130 different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB. */
131 if (var_bb
!= last_bb_in_path
)
136 vec
<basic_block
, va_gc
> *next_path
;
137 vec_alloc (next_path
, n_basic_blocks_for_fn (cfun
));
139 /* When VAR_BB == LAST_BB_IN_PATH, then the first block in the path
140 will already be in VISITED_BBS. When they are not equal, then we
141 must ensure that first block is accounted for to ensure we do not
142 create bogus jump threading paths. */
143 visited_bbs
->add ((*path
)[0]);
144 FOR_EACH_EDGE (e
, ei
, last_bb_in_path
->preds
)
146 hash_set
<basic_block
> *visited_bbs
= new hash_set
<basic_block
>;
148 if (fsm_find_thread_path (var_bb
, e
->src
, next_path
, visited_bbs
,
149 e
->src
->loop_father
))
154 /* If there is more than one path, stop. */
157 vec_free (next_path
);
162 /* Stop if we have not found a path: this could occur when the recursion
163 is stopped by one of the bounds. */
166 vec_free (next_path
);
170 /* Make sure we haven't already visited any of the nodes in
171 NEXT_PATH. Don't add them here to avoid pollution. */
172 for (unsigned int i
= 0; i
< next_path
->length () - 1; i
++)
174 if (visited_bbs
->contains ((*next_path
)[i
]))
176 vec_free (next_path
);
181 /* Now add the nodes to VISISTED_BBS. */
182 for (unsigned int i
= 0; i
< next_path
->length () - 1; i
++)
183 visited_bbs
->add ((*next_path
)[i
]);
185 /* Append all the nodes from NEXT_PATH to PATH. */
186 vec_safe_splice (path
, next_path
);
187 next_path_length
= next_path
->length ();
188 vec_free (next_path
);
191 gcc_assert (path
->last () == var_bb
);
193 /* Iterate over the arguments of PHI. */
195 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
197 tree arg
= gimple_phi_arg_def (phi
, i
);
198 basic_block bbi
= gimple_phi_arg_edge (phi
, i
)->src
;
200 /* Skip edges pointing outside the current loop. */
201 if (!arg
|| var_bb
->loop_father
!= bbi
->loop_father
)
204 if (TREE_CODE (arg
) == SSA_NAME
)
206 vec_safe_push (path
, bbi
);
207 /* Recursively follow SSA_NAMEs looking for a constant definition. */
208 fsm_find_control_statement_thread_paths (arg
, visited_bbs
, path
,
215 if (TREE_CODE (arg
) != INTEGER_CST
)
218 int path_length
= path
->length ();
219 if (path_length
> PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH
))
221 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
222 fprintf (dump_file
, "FSM jump-thread path not considered: "
223 "the number of basic blocks on the path "
224 "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
228 if (max_threaded_paths
<= 0)
230 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
231 fprintf (dump_file
, "FSM jump-thread path not considered: "
232 "the number of previously recorded FSM paths to thread "
233 "exceeds PARAM_MAX_FSM_THREAD_PATHS.\n");
237 /* Add BBI to the path. */
238 vec_safe_push (path
, bbi
);
242 gimple_stmt_iterator gsi
;
244 loop_p loop
= (*path
)[0]->loop_father
;
245 bool path_crosses_loops
= false;
247 /* Count the number of instructions on the path: as these instructions
248 will have to be duplicated, we will not record the path if there are
249 too many instructions on the path. Also check that all the blocks in
250 the path belong to a single loop. */
251 for (j
= 1; j
< path_length
- 1; j
++)
253 basic_block bb
= (*path
)[j
];
255 if (bb
->loop_father
!= loop
)
257 path_crosses_loops
= true;
261 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
263 gimple
*stmt
= gsi_stmt (gsi
);
264 /* Do not count empty statements and labels. */
265 if (gimple_code (stmt
) != GIMPLE_NOP
266 && gimple_code (stmt
) != GIMPLE_LABEL
267 && !is_gimple_debug (stmt
))
272 if (path_crosses_loops
)
274 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
275 fprintf (dump_file
, "FSM jump-thread path not considered: "
276 "the path crosses loops.\n");
281 if (n_insns
>= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATH_INSNS
))
283 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
284 fprintf (dump_file
, "FSM jump-thread path not considered: "
285 "the number of instructions on the path "
286 "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
291 vec
<jump_thread_edge
*> *jump_thread_path
292 = new vec
<jump_thread_edge
*> ();
294 /* Record the edges between the blocks in PATH. */
295 for (j
= 0; j
< path_length
- 1; j
++)
297 edge e
= find_edge ((*path
)[path_length
- j
- 1],
298 (*path
)[path_length
- j
- 2]);
300 jump_thread_edge
*x
= new jump_thread_edge (e
, EDGE_FSM_THREAD
);
301 jump_thread_path
->safe_push (x
);
304 gimple
*stmt
= get_gimple_control_stmt ((*path
)[0]);
306 /* We have found a constant value for ARG. For GIMPLE_SWITCH
307 and GIMPLE_GOTO, we use it as-is. However, for a GIMPLE_COND
308 we need to substitute, fold and simplify. */
309 if (gimple_code (stmt
) == GIMPLE_COND
)
311 enum tree_code cond_code
= gimple_cond_code (stmt
);
313 /* We know the underyling format of the condition. */
314 arg
= fold_binary (cond_code
, boolean_type_node
,
315 arg
, gimple_cond_rhs (stmt
));
318 /* Add the edge taken when the control variable has value ARG. */
319 edge taken_edge
= find_taken_edge ((*path
)[0], arg
);
321 = new jump_thread_edge (taken_edge
, EDGE_NO_COPY_SRC_BLOCK
);
322 jump_thread_path
->safe_push (x
);
324 register_jump_thread (jump_thread_path
);
325 --max_threaded_paths
;
327 /* Remove BBI from the path. */
331 /* Remove all the nodes that we added from NEXT_PATH. */
332 if (next_path_length
)
333 vec_safe_truncate (path
, (path
->length () - next_path_length
));
336 /* Search backwards from BB looking for paths where NAME (an SSA_NAME)
337 is a constant. Record such paths for jump threading.
339 It is assumed that BB ends with a control statement and that by
340 finding a path where NAME is a constant, we can thread the path. */
343 find_jump_threads_backwards (tree name
, basic_block bb
)
345 vec
<basic_block
, va_gc
> *bb_path
;
346 vec_alloc (bb_path
, n_basic_blocks_for_fn (cfun
));
347 vec_safe_push (bb_path
, bb
);
348 hash_set
<basic_block
> *visited_bbs
= new hash_set
<basic_block
>;
350 max_threaded_paths
= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS
);
351 fsm_find_control_statement_thread_paths (name
, visited_bbs
, bb_path
, false);