1/* SSA Jump Threading
2 Copyright (C) 2005-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation; either version 3, or (at your option)
9any later version.
10
11GCC is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
20#include "config.h"
21#include "system.h"
22#include "coretypes.h"
23#include "backend.h"
24#include "predict.h"
25#include "tree.h"
26#include "gimple.h"
27#include "fold-const.h"
28#include "cfgloop.h"
29#include "gimple-iterator.h"
30#include "tree-cfg.h"
31#include "tree-ssa-threadupdate.h"
32#include "params.h"
33#include "tree-ssa-loop.h"
34#include "cfganal.h"
35#include "tree-pass.h"
36#include "gimple-ssa.h"
37#include "tree-phinodes.h"
38#include "tree-inline.h"
39#include "tree-vectorizer.h"
40
41class thread_jumps
42{
43 public:
44 void find_jump_threads_backwards (basic_block bb, bool speed_p);
45 private:
46 edge profitable_jump_thread_path (basic_block bbi, tree name, tree arg,
47 bool *creates_irreducible_loop);
48 void convert_and_register_current_path (edge taken_edge);
49 void register_jump_thread_path_if_profitable (tree name, tree arg,
50 basic_block def_bb);
51 void handle_assignment (gimple *stmt, tree name, basic_block def_bb);
52 void handle_phi (gphi *phi, tree name, basic_block def_bb);
53 void fsm_find_control_statement_thread_paths (tree name);
54 bool check_subpath_and_update_thread_path (basic_block last_bb,
55 basic_block new_bb,
56 int *next_path_length);
57
58 /* Maximum number of BBs we are allowed to thread. */
59 int m_max_threaded_paths;
60 /* Hash to keep track of seen bbs. */
61 hash_set<basic_block> m_visited_bbs;
62 /* Current path we're analyzing. */
63 auto_vec<basic_block> m_path;
64 /* Tracks if we have recursed through a loop PHI node. */
65 bool m_seen_loop_phi;
66 /* Indicate that we could increase code size to improve the
67 code path. */
68 bool m_speed_p;
69};
70
71/* Simple helper to get the last statement from BB, which is assumed
72 to be a control statement. Return NULL if the last statement is
73 not a control statement. */
74
75static gimple *
76get_gimple_control_stmt (basic_block bb)
77{
78 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
79
80 if (gsi_end_p (gsi))
81 return NULL;
82
83 gimple *stmt = gsi_stmt (gsi);
84 enum gimple_code code = gimple_code (stmt);
85 if (code == GIMPLE_COND || code == GIMPLE_SWITCH || code == GIMPLE_GOTO)
86 return stmt;
87 return NULL;
88}
89
90/* Return true if the CFG contains at least one path from START_BB to
91 END_BB. When a path is found, record in PATH the blocks from
92 END_BB to START_BB. LOCAL_VISITED_BBS is used to make sure we
93 don't fall into an infinite loop. Bound the recursion to basic
94 blocks belonging to LOOP. */
95
96static bool
97fsm_find_thread_path (basic_block start_bb, basic_block end_bb,
98 vec<basic_block> &path,
99 hash_set<basic_block> &local_visited_bbs,
100 loop_p loop)
101{
102 if (loop != start_bb->loop_father)
103 return false;
104
105 if (start_bb == end_bb)
106 {
107 path.safe_push (start_bb);
108 return true;
109 }
110
111 if (!local_visited_bbs.add (start_bb))
112 {
113 edge e;
114 edge_iterator ei;
115 FOR_EACH_EDGE (e, ei, start_bb->succs)
116 if (fsm_find_thread_path (e->dest, end_bb, path, local_visited_bbs,
117 loop))
118 {
119 path.safe_push (start_bb);
120 return true;
121 }
122 }
123
124 return false;
125}
126
127/* Examine jump threading path PATH to which we want to add BBI.
128
129 If the resulting path is profitable to thread, then return the
130 final taken edge from the path, NULL otherwise.
131
132 NAME is the SSA_NAME of the variable we found to have a constant
133 value on PATH. ARG is the constant value of NAME on that path.
134
135 BBI will be appended to PATH when we have a profitable jump
136 threading path. Callers are responsible for removing BBI from PATH
137 in that case. */
138
139edge
140thread_jumps::profitable_jump_thread_path (basic_block bbi, tree name,
141 tree arg,
142 bool *creates_irreducible_loop)
143{
144 /* Note BBI is not in the path yet, hence the +1 in the test below
145 to make sure BBI is accounted for in the path length test. */
146
147 /* We can get a length of 0 here when the statement that
148 makes a conditional generate a compile-time constant
149 result is in the same block as the conditional.
150
151 That's not really a jump threading opportunity, but instead is
152 simple cprop & simplification. We could handle it here if we
153 wanted by wiring up all the incoming edges. If we run this
154 early in IPA, that might be worth doing. For now we just
155 reject that case. */
156 if (m_path.is_empty ())
157 return NULL;
158
159 if (m_path.length () + 1
160 > (unsigned) PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH))
161 {
162 if (dump_file && (dump_flags & TDF_DETAILS))
163 fprintf (dump_file, "FSM jump-thread path not considered: "
164 "the number of basic blocks on the path "
165 "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
166 return NULL;
167 }
168
169 if (m_max_threaded_paths <= 0)
170 {
171 if (dump_file && (dump_flags & TDF_DETAILS))
172 fprintf (dump_file, "FSM jump-thread path not considered: "
173 "the number of previously recorded FSM paths to "
174 "thread exceeds PARAM_MAX_FSM_THREAD_PATHS.\n");
175 return NULL;
176 }
177
178 /* Add BBI to the path.
179 From this point onward, if we decide we the path is not profitable
180 to thread, we must remove BBI from the path. */
181 m_path.safe_push (bbi);
182
183 int n_insns = 0;
184 gimple_stmt_iterator gsi;
185 loop_p loop = m_path[0]->loop_father;
186 bool path_crosses_loops = false;
187 bool threaded_through_latch = false;
188 bool multiway_branch_in_path = false;
189 bool threaded_multiway_branch = false;
190 bool contains_hot_bb = false;
191
192 if (dump_file && (dump_flags & TDF_DETAILS))
193 fprintf (dump_file, "Checking profitability of path (backwards): ");
194
195 /* Count the number of instructions on the path: as these instructions
196 will have to be duplicated, we will not record the path if there
197 are too many instructions on the path. Also check that all the
198 blocks in the path belong to a single loop. */
199 for (unsigned j = 0; j < m_path.length (); j++)
200 {
201 basic_block bb = m_path[j];
202
203 if (dump_file && (dump_flags & TDF_DETAILS))
204 fprintf (dump_file, " bb:%i", bb->index);
205 /* Remember, blocks in the path are stored in opposite order
206 in the PATH array. The last entry in the array represents
207 the block with an outgoing edge that we will redirect to the
208 jump threading path. Thus we don't care about that block's
209 loop father, nor how many statements are in that block because
210 it will not be copied or whether or not it ends in a multiway
211 branch. */
212 if (j < m_path.length () - 1)
213 {
214 int orig_n_insns = n_insns;
215 if (bb->loop_father != loop)
216 {
217 path_crosses_loops = true;
218 break;
219 }
220
221 /* PHIs in the path will create degenerate PHIS in the
222 copied path which will then get propagated away, so
223 looking at just the duplicate path the PHIs would
224 seem unimportant.
225
226 But those PHIs, because they're assignments to objects
227 typically with lives that exist outside the thread path,
228 will tend to generate PHIs (or at least new PHI arguments)
229 at points where we leave the thread path and rejoin
230 the original blocks. So we do want to account for them.
231
232 We ignore virtual PHIs. We also ignore cases where BB
233 has a single incoming edge. That's the most common
234 degenerate PHI we'll see here. Finally we ignore PHIs
235 that are associated with the value we're tracking as
236 that object likely dies. */
237 if (EDGE_COUNT (bb->succs) > 1 && EDGE_COUNT (bb->preds) > 1)
238 {
239 for (gphi_iterator gsip = gsi_start_phis (bb);
240 !gsi_end_p (gsip);
241 gsi_next (&gsip))
242 {
243 gphi *phi = gsip.phi ();
244 tree dst = gimple_phi_result (phi);
245
246 /* Note that if both NAME and DST are anonymous
247 SSA_NAMEs, then we do not have enough information
248 to consider them associated. */
249 if (dst != name
250 && (SSA_NAME_VAR (dst) != SSA_NAME_VAR (name)
251 || !SSA_NAME_VAR (dst))
252 && !virtual_operand_p (dst))
253 ++n_insns;
254 }
255 }
256
257 if (!contains_hot_bb && m_speed_p)
258 contains_hot_bb |= optimize_bb_for_speed_p (bb);
259 for (gsi = gsi_after_labels (bb);
260 !gsi_end_p (gsi);
261 gsi_next_nondebug (&gsi))
262 {
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_ASSIGN
267 && gimple_assign_rhs_code (stmt) == ASSERT_EXPR)
268 && !is_gimple_debug (stmt))
269 n_insns += estimate_num_insns (stmt, &eni_size_weights);
270 }
271 if (dump_file && (dump_flags & TDF_DETAILS))
272 fprintf (dump_file, " (%i insns)", n_insns-orig_n_insns);
273
274 /* We do not look at the block with the threaded branch
275 in this loop. So if any block with a last statement that
276 is a GIMPLE_SWITCH or GIMPLE_GOTO is seen, then we have a
277 multiway branch on our path.
278
279 The block in PATH[0] is special, it's the block were we're
280 going to be able to eliminate its branch. */
281 gimple *last = last_stmt (bb);
282 if (last && (gimple_code (last) == GIMPLE_SWITCH
283 || gimple_code (last) == GIMPLE_GOTO))
284 {
285 if (j == 0)
286 threaded_multiway_branch = true;
287 else
288 multiway_branch_in_path = true;
289 }
290 }
291
292 /* Note if we thread through the latch, we will want to include
293 the last entry in the array when determining if we thread
294 through the loop latch. */
295 if (loop->latch == bb)
296 threaded_through_latch = true;
297 }
298
299 gimple *stmt = get_gimple_control_stmt (m_path[0]);
300 gcc_assert (stmt);
301
302 /* We are going to remove the control statement at the end of the
303 last block in the threading path. So don't count it against our
304 statement count. */
305
306 int stmt_insns = estimate_num_insns (stmt, &eni_size_weights);
307 n_insns-= stmt_insns;
308
309 if (dump_file && (dump_flags & TDF_DETAILS))
310 fprintf (dump_file, "\n Control statement insns: %i\n"
311 " Overall: %i insns\n",
312 stmt_insns, n_insns);
313
314 /* We have found a constant value for ARG. For GIMPLE_SWITCH
315 and GIMPLE_GOTO, we use it as-is. However, for a GIMPLE_COND
316 we need to substitute, fold and simplify so we can determine
317 the edge taken out of the last block. */
318 if (gimple_code (stmt) == GIMPLE_COND)
319 {
320 enum tree_code cond_code = gimple_cond_code (stmt);
321
322 /* We know the underyling format of the condition. */
323 arg = fold_binary (cond_code, boolean_type_node,
324 arg, gimple_cond_rhs (stmt));
325 }
326
327 /* If this path threaded through the loop latch back into the
328 same loop and the destination does not dominate the loop
329 latch, then this thread would create an irreducible loop.
330
331 We have to know the outgoing edge to figure this out. */
332 edge taken_edge = find_taken_edge (m_path[0], arg);
333
334 /* There are cases where we may not be able to extract the
335 taken edge. For example, a computed goto to an absolute
336 address. Handle those cases gracefully. */
337 if (taken_edge == NULL)
338 {
339 m_path.pop ();
340 return NULL;
341 }
342
343 *creates_irreducible_loop = false;
344 if (threaded_through_latch
345 && loop == taken_edge->dest->loop_father
346 && (determine_bb_domination_status (loop, taken_edge->dest)
347 == DOMST_NONDOMINATING))
348 *creates_irreducible_loop = true;
349
350 if (path_crosses_loops)
351 {
352 if (dump_file && (dump_flags & TDF_DETAILS))
353 fprintf (dump_file, "FSM jump-thread path not considered: "
354 "the path crosses loops.\n");
355 m_path.pop ();
356 return NULL;
357 }
358
359 /* Threading is profitable if the path duplicated is hot but also
360 in a case we separate cold path from hot path and permit optimization
361 of the hot path later. Be on the agressive side here. In some testcases,
362 as in PR 78407 this leads to noticeable improvements. */
363 if (m_speed_p && (optimize_edge_for_speed_p (taken_edge) || contains_hot_bb))
364 {
365 if (n_insns >= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATH_INSNS))
366 {
367 if (dump_file && (dump_flags & TDF_DETAILS))
368 fprintf (dump_file, "FSM jump-thread path not considered: "
369 "the number of instructions on the path "
370 "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
371 m_path.pop ();
372 return NULL;
373 }
374 }
375 else if (n_insns > 1)
376 {
377 if (dump_file && (dump_flags & TDF_DETAILS))
378 fprintf (dump_file, "FSM jump-thread path not considered: "
379 "duplication of %i insns is needed and optimizing for size.\n",
380 n_insns);
381 m_path.pop ();
382 return NULL;
383 }
384
385 /* We avoid creating irreducible inner loops unless we thread through
386 a multiway branch, in which case we have deemed it worth losing
387 other loop optimizations later.
388
389 We also consider it worth creating an irreducible inner loop if
390 the number of copied statement is low relative to the length of
391 the path -- in that case there's little the traditional loop
392 optimizer would have done anyway, so an irreducible loop is not
393 so bad. */
394 if (!threaded_multiway_branch && *creates_irreducible_loop
395 && (n_insns * (unsigned) PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS)
396 > (m_path.length () *
397 (unsigned) PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS))))
398
399 {
400 if (dump_file && (dump_flags & TDF_DETAILS))
401 fprintf (dump_file,
402 "FSM would create irreducible loop without threading "
403 "multiway branch.\n");
404 m_path.pop ();
405 return NULL;
406 }
407
408
409 /* If this path does not thread through the loop latch, then we are
410 using the FSM threader to find old style jump threads. This
411 is good, except the FSM threader does not re-use an existing
412 threading path to reduce code duplication.
413
414 So for that case, drastically reduce the number of statements
415 we are allowed to copy. */
416 if (!(threaded_through_latch && threaded_multiway_branch)
417 && (n_insns * PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS)
418 >= PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS)))
419 {
420 if (dump_file && (dump_flags & TDF_DETAILS))
421 fprintf (dump_file,
422 "FSM did not thread around loop and would copy too "
423 "many statements.\n");
424 m_path.pop ();
425 return NULL;
426 }
427
428 /* When there is a multi-way branch on the path, then threading can
429 explode the CFG due to duplicating the edges for that multi-way
430 branch. So like above, only allow a multi-way branch on the path
431 if we actually thread a multi-way branch. */
432 if (!threaded_multiway_branch && multiway_branch_in_path)
433 {
434 if (dump_file && (dump_flags & TDF_DETAILS))
435 fprintf (dump_file,
436 "FSM Thread through multiway branch without threading "
437 "a multiway branch.\n");
438 m_path.pop ();
439 return NULL;
440 }
441 return taken_edge;
442}
443
444/* The current path PATH is a vector of blocks forming a jump threading
445 path in reverse order. TAKEN_EDGE is the edge taken from path[0].
446
447 Convert the current path into the form used by register_jump_thread and
448 register it. */
449
450void
451thread_jumps::convert_and_register_current_path (edge taken_edge)
452{
453 vec<jump_thread_edge *> *jump_thread_path = new vec<jump_thread_edge *> ();
454
455 /* Record the edges between the blocks in PATH. */
456 for (unsigned int j = 0; j + 1 < m_path.length (); j++)
457 {
458 basic_block bb1 = m_path[m_path.length () - j - 1];
459 basic_block bb2 = m_path[m_path.length () - j - 2];
460
461 edge e = find_edge (bb1, bb2);
462 gcc_assert (e);
463 jump_thread_edge *x = new jump_thread_edge (e, EDGE_FSM_THREAD);
464 jump_thread_path->safe_push (x);
465 }
466
467 /* Add the edge taken when the control variable has value ARG. */
468 jump_thread_edge *x
469 = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
470 jump_thread_path->safe_push (x);
471
472 register_jump_thread (jump_thread_path);
473 --m_max_threaded_paths;
474}
475
476/* While following a chain of SSA_NAME definitions, we jumped from a
477 definition in LAST_BB to a definition in NEW_BB (walking
478 backwards).
479
480 Verify there is a single path between the blocks and none of the
481 blocks in the path is already in VISITED_BBS. If so, then update
482 VISISTED_BBS, add the new blocks to PATH and return TRUE.
483 Otherwise return FALSE.
484
485 Store the length of the subpath in NEXT_PATH_LENGTH. */
486
487bool
488thread_jumps::check_subpath_and_update_thread_path (basic_block last_bb,
489 basic_block new_bb,
490 int *next_path_length)
491{
492 edge e;
493 int e_count = 0;
494 edge_iterator ei;
495 auto_vec<basic_block> next_path;
496
497 FOR_EACH_EDGE (e, ei, last_bb->preds)
498 {
499 hash_set<basic_block> local_visited_bbs;
500
501 if (fsm_find_thread_path (new_bb, e->src, next_path,
502 local_visited_bbs, e->src->loop_father))
503 ++e_count;
504
505 /* If there is more than one path, stop. */
506 if (e_count > 1)
507 return false;
508 }
509
510 /* Stop if we have not found a path: this could occur when the recursion
511 is stopped by one of the bounds. */
512 if (e_count == 0)
513 return false;
514
515 /* Make sure we haven't already visited any of the nodes in
516 NEXT_PATH. Don't add them here to avoid pollution. */
517 for (unsigned int i = 0; i + 1 < next_path.length (); i++)
518 {
519 if (m_visited_bbs.contains (next_path[i]))
520 return false;
521 }
522
523 /* Now add the nodes to VISISTED_BBS. */
524 for (unsigned int i = 0; i + 1 < next_path.length (); i++)
525 m_visited_bbs.add (next_path[i]);
526
527 /* Append all the nodes from NEXT_PATH to PATH. */
528 m_path.safe_splice (next_path);
529 *next_path_length = next_path.length ();
530
531 return true;
532}
533
534/* If this is a profitable jump thread path, register it.
535
536 NAME is an SSA NAME with a possible constant value of ARG on PATH.
537
538 DEF_BB is the basic block that ultimately defines the constant. */
539
540void
541thread_jumps::register_jump_thread_path_if_profitable (tree name, tree arg,
542 basic_block def_bb)
543{
544 if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant)
545 return;
546
547 bool irreducible = false;
548 edge taken_edge = profitable_jump_thread_path (def_bb, name, arg,
549 &irreducible);
550 if (taken_edge)
551 {
552 convert_and_register_current_path (taken_edge);
553 m_path.pop ();
554
555 if (irreducible)
556 vect_free_loop_info_assumptions (m_path[0]->loop_father);
557 }
558}
559
560/* Given PHI which defines NAME in block DEF_BB, recurse through the
561 PHI's arguments searching for paths where NAME will ultimately have
562 a constant value.
563
564 PATH contains the series of blocks to traverse that will result in
565 NAME having a constant value. */
566
567void
568thread_jumps::handle_phi (gphi *phi, tree name, basic_block def_bb)
569{
570 /* Iterate over the arguments of PHI. */
571 for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++)
572 {
573 tree arg = gimple_phi_arg_def (phi, i);
574 basic_block bbi = gimple_phi_arg_edge (phi, i)->src;
575
576 /* Skip edges pointing outside the current loop. */
577 if (!arg || def_bb->loop_father != bbi->loop_father)
578 continue;
579
580 if (TREE_CODE (arg) == SSA_NAME)
581 {
582 m_path.safe_push (bbi);
583 /* Recursively follow SSA_NAMEs looking for a constant
584 definition. */
585 fsm_find_control_statement_thread_paths (arg);
586
587 m_path.pop ();
588 continue;
589 }
590
591 register_jump_thread_path_if_profitable (name, arg, bbi);
592 }
593}
594
595/* Return TRUE if STMT is a gimple assignment we want to either directly
596 handle or recurse through. Return FALSE otherwise.
597
598 Note that adding more cases here requires adding cases to handle_assignment
599 below. */
600
601static bool
602handle_assignment_p (gimple *stmt)
603{
604 if (is_gimple_assign (stmt))
605 {
606 enum tree_code def_code = gimple_assign_rhs_code (stmt);
607
608 /* If the RHS is an SSA_NAME, then we will recurse through it.
609 Go ahead and filter out cases where the SSA_NAME is a default
610 definition. There's little to be gained by trying to handle that. */
611 if (def_code == SSA_NAME
612 && !SSA_NAME_IS_DEFAULT_DEF (gimple_assign_rhs1 (stmt)))
613 return true;
614
615 /* If the RHS is a constant, then it's a terminal that we'll want
616 to handle as well. */
617 if (TREE_CODE_CLASS (def_code) == tcc_constant)
618 return true;
619 }
620
621 /* Anything not explicitly allowed is not handled. */
622 return false;
623}
624
625/* Given STMT which defines NAME in block DEF_BB, recurse through the
626 PHI's arguments searching for paths where NAME will ultimately have
627 a constant value.
628
629 PATH contains the series of blocks to traverse that will result in
630 NAME having a constant value. */
631
632void
633thread_jumps::handle_assignment (gimple *stmt, tree name, basic_block def_bb)
634{
635 tree arg = gimple_assign_rhs1 (stmt);
636
637 if (TREE_CODE (arg) == SSA_NAME)
638 fsm_find_control_statement_thread_paths (arg);
639
640 else
641 {
642 /* register_jump_thread_path_if_profitable will push the current
643 block onto the path. But the path will always have the current
644 block at this point. So we can just pop it. */
645 m_path.pop ();
646
647 register_jump_thread_path_if_profitable (name, arg, def_bb);
648
649 /* And put the current block back onto the path so that the
650 state of the stack is unchanged when we leave. */
651 m_path.safe_push (def_bb);
652 }
653}
654
655/* We trace the value of the SSA_NAME NAME back through any phi nodes
656 looking for places where it gets a constant value and save the
657 path. */
658
659void
660thread_jumps::fsm_find_control_statement_thread_paths (tree name)
661{
662 /* If NAME appears in an abnormal PHI, then don't try to trace its
663 value back through PHI nodes. */
664 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
665 return;
666
667 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
668 basic_block def_bb = gimple_bb (def_stmt);
669
670 if (def_bb == NULL)
671 return;
672
673 /* We allow the SSA chain to contains PHIs and simple copies and constant
674 initializations. */
675 if (gimple_code (def_stmt) != GIMPLE_PHI
676 && gimple_code (def_stmt) != GIMPLE_ASSIGN)
677 return;
678
679 if (gimple_code (def_stmt) == GIMPLE_PHI
680 && (gimple_phi_num_args (def_stmt)
681 >= (unsigned) PARAM_VALUE (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS)))
682 return;
683
684 if (is_gimple_assign (def_stmt)
685 && ! handle_assignment_p (def_stmt))
686 return;
687
688 /* Avoid infinite recursion. */
689 if (m_visited_bbs.add (def_bb))
690 return;
691
692 int next_path_length = 0;
693 basic_block last_bb_in_path = m_path.last ();
694
695 if (loop_containing_stmt (def_stmt)->header == gimple_bb (def_stmt))
696 {
697 /* Do not walk through more than one loop PHI node. */
698 if (m_seen_loop_phi)
699 return;
700 m_seen_loop_phi = true;
701 }
702
703 /* Following the chain of SSA_NAME definitions, we jumped from a definition in
704 LAST_BB_IN_PATH to a definition in DEF_BB. When these basic blocks are
705 different, append to PATH the blocks from LAST_BB_IN_PATH to DEF_BB. */
706 if (def_bb != last_bb_in_path)
707 {
708 /* When DEF_BB == LAST_BB_IN_PATH, then the first block in the path
709 will already be in VISITED_BBS. When they are not equal, then we
710 must ensure that first block is accounted for to ensure we do not
711 create bogus jump threading paths. */
712 m_visited_bbs.add (m_path[0]);
713 if (!check_subpath_and_update_thread_path (last_bb_in_path, def_bb,
714 &next_path_length))
715 return;
716 }
717
718 gcc_assert (m_path.last () == def_bb);
719
720 if (gimple_code (def_stmt) == GIMPLE_PHI)
721 handle_phi (as_a <gphi *> (def_stmt), name, def_bb);
722 else if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
723 handle_assignment (def_stmt, name, def_bb);
724
725 /* Remove all the nodes that we added from NEXT_PATH. */
726 if (next_path_length)
727 m_path.truncate (m_path.length () - next_path_length);
728}
729
730/* Search backwards from BB looking for paths where NAME (an SSA_NAME)
731 is a constant. Record such paths for jump threading.
732
733 It is assumed that BB ends with a control statement and that by
734 finding a path where NAME is a constant, we can thread the path.
735 SPEED_P indicates that we could increase code size to improve the
736 code path. */
737
738void
739thread_jumps::find_jump_threads_backwards (basic_block bb, bool speed_p)
740{
741 gimple *stmt = get_gimple_control_stmt (bb);
742 if (!stmt)
743 return;
744
745 enum gimple_code code = gimple_code (stmt);
746 tree name = NULL;
747 if (code == GIMPLE_SWITCH)
748 name = gimple_switch_index (as_a <gswitch *> (stmt));
749 else if (code == GIMPLE_GOTO)
750 name = gimple_goto_dest (stmt);
751 else if (code == GIMPLE_COND)
752 {
753 if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
754 && TREE_CODE_CLASS (TREE_CODE (gimple_cond_rhs (stmt))) == tcc_constant
755 && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
756 || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))))
757 name = gimple_cond_lhs (stmt);
758 }
759
760 if (!name || TREE_CODE (name) != SSA_NAME)
761 return;
762
763 /* Initialize pass local data that's different for each BB. */
764 m_path.truncate (0);
765 m_path.safe_push (bb);
766 m_visited_bbs.empty ();
767 m_seen_loop_phi = false;
768 m_speed_p = speed_p;
769 m_max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS);
770
771 fsm_find_control_statement_thread_paths (name);
772}
773
774namespace {
775
776const pass_data pass_data_thread_jumps =
777{
778 GIMPLE_PASS,
779 "thread",
780 OPTGROUP_NONE,
781 TV_TREE_SSA_THREAD_JUMPS,
782 ( PROP_cfg | PROP_ssa ),
783 0,
784 0,
785 0,
786 TODO_update_ssa,
787};
788
789class pass_thread_jumps : public gimple_opt_pass
790{
791public:
792 pass_thread_jumps (gcc::context *ctxt)
793 : gimple_opt_pass (pass_data_thread_jumps, ctxt)
794 {}
795
796 opt_pass * clone (void) { return new pass_thread_jumps (m_ctxt); }
797 virtual bool gate (function *);
798 virtual unsigned int execute (function *);
799};
800
801bool
802pass_thread_jumps::gate (function *fun ATTRIBUTE_UNUSED)
803{
804 return flag_expensive_optimizations;
805}
806
807
808unsigned int
809pass_thread_jumps::execute (function *fun)
810{
811 loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
812
813 /* Try to thread each block with more than one successor. */
814 thread_jumps threader;
815 basic_block bb;
816 FOR_EACH_BB_FN (bb, fun)
817 {
818 if (EDGE_COUNT (bb->succs) > 1)
819 threader.find_jump_threads_backwards (bb, true);
820 }
821 bool changed = thread_through_all_blocks (true);
822
823 loop_optimizer_finalize ();
824 return changed ? TODO_cleanup_cfg : 0;
825}
826
827}
828
829gimple_opt_pass *
830make_pass_thread_jumps (gcc::context *ctxt)
831{
832 return new pass_thread_jumps (ctxt);
833}
834
835namespace {
836
837const pass_data pass_data_early_thread_jumps =
838{
839 GIMPLE_PASS,
840 "ethread",
841 OPTGROUP_NONE,
842 TV_TREE_SSA_THREAD_JUMPS,
843 ( PROP_cfg | PROP_ssa ),
844 0,
845 0,
846 0,
847 ( TODO_cleanup_cfg | TODO_update_ssa ),
848};
849
850class pass_early_thread_jumps : public gimple_opt_pass
851{
852public:
853 pass_early_thread_jumps (gcc::context *ctxt)
854 : gimple_opt_pass (pass_data_early_thread_jumps, ctxt)
855 {}
856
857 opt_pass * clone (void) { return new pass_early_thread_jumps (m_ctxt); }
858 virtual bool gate (function *);
859 virtual unsigned int execute (function *);
860};
861
862bool
863pass_early_thread_jumps::gate (function *fun ATTRIBUTE_UNUSED)
864{
865 return true;
866}
867
868
869unsigned int
870pass_early_thread_jumps::execute (function *fun)
871{
872 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
873
874 /* Try to thread each block with more than one successor. */
875 thread_jumps threader;
876 basic_block bb;
877 FOR_EACH_BB_FN (bb, fun)
878 {
879 if (EDGE_COUNT (bb->succs) > 1)
880 threader.find_jump_threads_backwards (bb, false);
881 }
882 thread_through_all_blocks (true);
883
884 loop_optimizer_finalize ();
885 return 0;
886}
887
888}
889
890gimple_opt_pass *
891make_pass_early_thread_jumps (gcc::context *ctxt)
892{
893 return new pass_early_thread_jumps (ctxt);
894}
895