PR rtl-optimization/57003
[official-gcc.git] / gcc / tree-ssa-threadupdate.c
blob125f6f8776d98a0d7235e2b10d41ed7453cb774d
1 /* Thread edges through blocks and update the control flow and SSA graphs.
2 Copyright (C) 2004-2014 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)
9 any later version.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tree.h"
24 #include "flags.h"
25 #include "basic-block.h"
26 #include "function.h"
27 #include "hash-table.h"
28 #include "tree-ssa-alias.h"
29 #include "internal-fn.h"
30 #include "gimple-expr.h"
31 #include "is-a.h"
32 #include "gimple.h"
33 #include "gimple-iterator.h"
34 #include "gimple-ssa.h"
35 #include "tree-phinodes.h"
36 #include "tree-ssa.h"
37 #include "tree-ssa-threadupdate.h"
38 #include "ssa-iterators.h"
39 #include "dumpfile.h"
40 #include "cfgloop.h"
41 #include "dbgcnt.h"
42 #include "tree-cfg.h"
43 #include "tree-pass.h"
45 /* Given a block B, update the CFG and SSA graph to reflect redirecting
46 one or more in-edges to B to instead reach the destination of an
47 out-edge from B while preserving any side effects in B.
49 i.e., given A->B and B->C, change A->B to be A->C yet still preserve the
50 side effects of executing B.
52 1. Make a copy of B (including its outgoing edges and statements). Call
53 the copy B'. Note B' has no incoming edges or PHIs at this time.
55 2. Remove the control statement at the end of B' and all outgoing edges
56 except B'->C.
58 3. Add a new argument to each PHI in C with the same value as the existing
59 argument associated with edge B->C. Associate the new PHI arguments
60 with the edge B'->C.
62 4. For each PHI in B, find or create a PHI in B' with an identical
63 PHI_RESULT. Add an argument to the PHI in B' which has the same
64 value as the PHI in B associated with the edge A->B. Associate
65 the new argument in the PHI in B' with the edge A->B.
67 5. Change the edge A->B to A->B'.
69 5a. This automatically deletes any PHI arguments associated with the
70 edge A->B in B.
72 5b. This automatically associates each new argument added in step 4
73 with the edge A->B'.
75 6. Repeat for other incoming edges into B.
77 7. Put the duplicated resources in B and all the B' blocks into SSA form.
79 Note that block duplication can be minimized by first collecting the
80 set of unique destination blocks that the incoming edges should
81 be threaded to.
83 We reduce the number of edges and statements we create by not copying all
84 the outgoing edges and the control statement in step #1. We instead create
85 a template block without the outgoing edges and duplicate the template.
87 Another case this code handles is threading through a "joiner" block. In
88 this case, we do not know the destination of the joiner block, but one
89 of the outgoing edges from the joiner block leads to a threadable path. This
90 case largely works as outlined above, except the duplicate of the joiner
91 block still contains a full set of outgoing edges and its control statement.
92 We just redirect one of its outgoing edges to our jump threading path. */
95 /* Steps #5 and #6 of the above algorithm are best implemented by walking
96 all the incoming edges which thread to the same destination edge at
97 the same time. That avoids lots of table lookups to get information
98 for the destination edge.
100 To realize that implementation we create a list of incoming edges
101 which thread to the same outgoing edge. Thus to implement steps
102 #5 and #6 we traverse our hash table of outgoing edge information.
103 For each entry we walk the list of incoming edges which thread to
104 the current outgoing edge. */
106 struct el
108 edge e;
109 struct el *next;
112 /* Main data structure recording information regarding B's duplicate
113 blocks. */
115 /* We need to efficiently record the unique thread destinations of this
116 block and specific information associated with those destinations. We
117 may have many incoming edges threaded to the same outgoing edge. This
118 can be naturally implemented with a hash table. */
120 struct redirection_data : typed_free_remove<redirection_data>
122 /* We support wiring up two block duplicates in a jump threading path.
124 One is a normal block copy where we remove the control statement
125 and wire up its single remaining outgoing edge to the thread path.
127 The other is a joiner block where we leave the control statement
128 in place, but wire one of the outgoing edges to a thread path.
130 In theory we could have multiple block duplicates in a jump
131 threading path, but I haven't tried that.
133 The duplicate blocks appear in this array in the same order in
134 which they appear in the jump thread path. */
135 basic_block dup_blocks[2];
137 /* The jump threading path. */
138 vec<jump_thread_edge *> *path;
140 /* A list of incoming edges which we want to thread to the
141 same path. */
142 struct el *incoming_edges;
144 /* hash_table support. */
145 typedef redirection_data value_type;
146 typedef redirection_data compare_type;
147 static inline hashval_t hash (const value_type *);
148 static inline int equal (const value_type *, const compare_type *);
151 /* Dump a jump threading path, including annotations about each
152 edge in the path. */
154 static void
155 dump_jump_thread_path (FILE *dump_file, vec<jump_thread_edge *> path,
156 bool registering)
158 fprintf (dump_file,
159 " %s jump thread: (%d, %d) incoming edge; ",
160 (registering ? "Registering" : "Cancelling"),
161 path[0]->e->src->index, path[0]->e->dest->index);
163 for (unsigned int i = 1; i < path.length (); i++)
165 /* We can get paths with a NULL edge when the final destination
166 of a jump thread turns out to be a constant address. We dump
167 those paths when debugging, so we have to be prepared for that
168 possibility here. */
169 if (path[i]->e == NULL)
170 continue;
172 if (path[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
173 fprintf (dump_file, " (%d, %d) joiner; ",
174 path[i]->e->src->index, path[i]->e->dest->index);
175 if (path[i]->type == EDGE_COPY_SRC_BLOCK)
176 fprintf (dump_file, " (%d, %d) normal;",
177 path[i]->e->src->index, path[i]->e->dest->index);
178 if (path[i]->type == EDGE_NO_COPY_SRC_BLOCK)
179 fprintf (dump_file, " (%d, %d) nocopy;",
180 path[i]->e->src->index, path[i]->e->dest->index);
182 fputc ('\n', dump_file);
185 /* Simple hashing function. For any given incoming edge E, we're going
186 to be most concerned with the final destination of its jump thread
187 path. So hash on the block index of the final edge in the path. */
189 inline hashval_t
190 redirection_data::hash (const value_type *p)
192 vec<jump_thread_edge *> *path = p->path;
193 return path->last ()->e->dest->index;
196 /* Given two hash table entries, return true if they have the same
197 jump threading path. */
198 inline int
199 redirection_data::equal (const value_type *p1, const compare_type *p2)
201 vec<jump_thread_edge *> *path1 = p1->path;
202 vec<jump_thread_edge *> *path2 = p2->path;
204 if (path1->length () != path2->length ())
205 return false;
207 for (unsigned int i = 1; i < path1->length (); i++)
209 if ((*path1)[i]->type != (*path2)[i]->type
210 || (*path1)[i]->e != (*path2)[i]->e)
211 return false;
214 return true;
217 /* Data structure of information to pass to hash table traversal routines. */
218 struct ssa_local_info_t
220 /* The current block we are working on. */
221 basic_block bb;
223 /* We only create a template block for the first duplicated block in a
224 jump threading path as we may need many duplicates of that block.
226 The second duplicate block in a path is specific to that path. Creating
227 and sharing a template for that block is considerably more difficult. */
228 basic_block template_block;
230 /* TRUE if we thread one or more jumps, FALSE otherwise. */
231 bool jumps_threaded;
233 /* Blocks duplicated for the thread. */
234 bitmap duplicate_blocks;
237 /* Passes which use the jump threading code register jump threading
238 opportunities as they are discovered. We keep the registered
239 jump threading opportunities in this vector as edge pairs
240 (original_edge, target_edge). */
241 static vec<vec<jump_thread_edge *> *> paths;
243 /* When we start updating the CFG for threading, data necessary for jump
244 threading is attached to the AUX field for the incoming edge. Use these
245 macros to access the underlying structure attached to the AUX field. */
246 #define THREAD_PATH(E) ((vec<jump_thread_edge *> *)(E)->aux)
248 /* Jump threading statistics. */
250 struct thread_stats_d
252 unsigned long num_threaded_edges;
255 struct thread_stats_d thread_stats;
258 /* Remove the last statement in block BB if it is a control statement
259 Also remove all outgoing edges except the edge which reaches DEST_BB.
260 If DEST_BB is NULL, then remove all outgoing edges. */
262 static void
263 remove_ctrl_stmt_and_useless_edges (basic_block bb, basic_block dest_bb)
265 gimple_stmt_iterator gsi;
266 edge e;
267 edge_iterator ei;
269 gsi = gsi_last_bb (bb);
271 /* If the duplicate ends with a control statement, then remove it.
273 Note that if we are duplicating the template block rather than the
274 original basic block, then the duplicate might not have any real
275 statements in it. */
276 if (!gsi_end_p (gsi)
277 && gsi_stmt (gsi)
278 && (gimple_code (gsi_stmt (gsi)) == GIMPLE_COND
279 || gimple_code (gsi_stmt (gsi)) == GIMPLE_GOTO
280 || gimple_code (gsi_stmt (gsi)) == GIMPLE_SWITCH))
281 gsi_remove (&gsi, true);
283 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
285 if (e->dest != dest_bb)
286 remove_edge (e);
287 else
288 ei_next (&ei);
292 /* Create a duplicate of BB. Record the duplicate block in an array
293 indexed by COUNT stored in RD. */
295 static void
296 create_block_for_threading (basic_block bb,
297 struct redirection_data *rd,
298 unsigned int count,
299 bitmap *duplicate_blocks)
301 edge_iterator ei;
302 edge e;
304 /* We can use the generic block duplication code and simply remove
305 the stuff we do not need. */
306 rd->dup_blocks[count] = duplicate_block (bb, NULL, NULL);
308 FOR_EACH_EDGE (e, ei, rd->dup_blocks[count]->succs)
309 e->aux = NULL;
311 /* Zero out the profile, since the block is unreachable for now. */
312 rd->dup_blocks[count]->frequency = 0;
313 rd->dup_blocks[count]->count = 0;
314 if (duplicate_blocks)
315 bitmap_set_bit (*duplicate_blocks, rd->dup_blocks[count]->index);
318 /* Main data structure to hold information for duplicates of BB. */
320 static hash_table<redirection_data> *redirection_data;
322 /* Given an outgoing edge E lookup and return its entry in our hash table.
324 If INSERT is true, then we insert the entry into the hash table if
325 it is not already present. INCOMING_EDGE is added to the list of incoming
326 edges associated with E in the hash table. */
328 static struct redirection_data *
329 lookup_redirection_data (edge e, enum insert_option insert)
331 struct redirection_data **slot;
332 struct redirection_data *elt;
333 vec<jump_thread_edge *> *path = THREAD_PATH (e);
335 /* Build a hash table element so we can see if E is already
336 in the table. */
337 elt = XNEW (struct redirection_data);
338 elt->path = path;
339 elt->dup_blocks[0] = NULL;
340 elt->dup_blocks[1] = NULL;
341 elt->incoming_edges = NULL;
343 slot = redirection_data->find_slot (elt, insert);
345 /* This will only happen if INSERT is false and the entry is not
346 in the hash table. */
347 if (slot == NULL)
349 free (elt);
350 return NULL;
353 /* This will only happen if E was not in the hash table and
354 INSERT is true. */
355 if (*slot == NULL)
357 *slot = elt;
358 elt->incoming_edges = XNEW (struct el);
359 elt->incoming_edges->e = e;
360 elt->incoming_edges->next = NULL;
361 return elt;
363 /* E was in the hash table. */
364 else
366 /* Free ELT as we do not need it anymore, we will extract the
367 relevant entry from the hash table itself. */
368 free (elt);
370 /* Get the entry stored in the hash table. */
371 elt = *slot;
373 /* If insertion was requested, then we need to add INCOMING_EDGE
374 to the list of incoming edges associated with E. */
375 if (insert)
377 struct el *el = XNEW (struct el);
378 el->next = elt->incoming_edges;
379 el->e = e;
380 elt->incoming_edges = el;
383 return elt;
387 /* Similar to copy_phi_args, except that the PHI arg exists, it just
388 does not have a value associated with it. */
390 static void
391 copy_phi_arg_into_existing_phi (edge src_e, edge tgt_e)
393 int src_idx = src_e->dest_idx;
394 int tgt_idx = tgt_e->dest_idx;
396 /* Iterate over each PHI in e->dest. */
397 for (gimple_stmt_iterator gsi = gsi_start_phis (src_e->dest),
398 gsi2 = gsi_start_phis (tgt_e->dest);
399 !gsi_end_p (gsi);
400 gsi_next (&gsi), gsi_next (&gsi2))
402 gimple src_phi = gsi_stmt (gsi);
403 gimple dest_phi = gsi_stmt (gsi2);
404 tree val = gimple_phi_arg_def (src_phi, src_idx);
405 source_location locus = gimple_phi_arg_location (src_phi, src_idx);
407 SET_PHI_ARG_DEF (dest_phi, tgt_idx, val);
408 gimple_phi_arg_set_location (dest_phi, tgt_idx, locus);
412 /* Given ssa_name DEF, backtrack jump threading PATH from node IDX
413 to see if it has constant value in a flow sensitive manner. Set
414 LOCUS to location of the constant phi arg and return the value.
415 Return DEF directly if either PATH or idx is ZERO. */
417 static tree
418 get_value_locus_in_path (tree def, vec<jump_thread_edge *> *path,
419 basic_block bb, int idx, source_location *locus)
421 tree arg;
422 gimple def_phi;
423 basic_block def_bb;
425 if (path == NULL || idx == 0)
426 return def;
428 def_phi = SSA_NAME_DEF_STMT (def);
429 if (gimple_code (def_phi) != GIMPLE_PHI)
430 return def;
432 def_bb = gimple_bb (def_phi);
433 /* Don't propagate loop invariants into deeper loops. */
434 if (!def_bb || bb_loop_depth (def_bb) < bb_loop_depth (bb))
435 return def;
437 /* Backtrack jump threading path from IDX to see if def has constant
438 value. */
439 for (int j = idx - 1; j >= 0; j--)
441 edge e = (*path)[j]->e;
442 if (e->dest == def_bb)
444 arg = gimple_phi_arg_def (def_phi, e->dest_idx);
445 if (is_gimple_min_invariant (arg))
447 *locus = gimple_phi_arg_location (def_phi, e->dest_idx);
448 return arg;
450 break;
454 return def;
457 /* For each PHI in BB, copy the argument associated with SRC_E to TGT_E.
458 Try to backtrack jump threading PATH from node IDX to see if the arg
459 has constant value, copy constant value instead of argument itself
460 if yes. */
462 static void
463 copy_phi_args (basic_block bb, edge src_e, edge tgt_e,
464 vec<jump_thread_edge *> *path, int idx)
466 gimple_stmt_iterator gsi;
467 int src_indx = src_e->dest_idx;
469 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
471 gimple phi = gsi_stmt (gsi);
472 tree def = gimple_phi_arg_def (phi, src_indx);
473 source_location locus = gimple_phi_arg_location (phi, src_indx);
475 if (TREE_CODE (def) == SSA_NAME
476 && !virtual_operand_p (gimple_phi_result (phi)))
477 def = get_value_locus_in_path (def, path, bb, idx, &locus);
479 add_phi_arg (phi, def, tgt_e, locus);
483 /* We have recently made a copy of ORIG_BB, including its outgoing
484 edges. The copy is NEW_BB. Every PHI node in every direct successor of
485 ORIG_BB has a new argument associated with edge from NEW_BB to the
486 successor. Initialize the PHI argument so that it is equal to the PHI
487 argument associated with the edge from ORIG_BB to the successor.
488 PATH and IDX are used to check if the new PHI argument has constant
489 value in a flow sensitive manner. */
491 static void
492 update_destination_phis (basic_block orig_bb, basic_block new_bb,
493 vec<jump_thread_edge *> *path, int idx)
495 edge_iterator ei;
496 edge e;
498 FOR_EACH_EDGE (e, ei, orig_bb->succs)
500 edge e2 = find_edge (new_bb, e->dest);
501 copy_phi_args (e->dest, e, e2, path, idx);
505 /* Given a duplicate block and its single destination (both stored
506 in RD). Create an edge between the duplicate and its single
507 destination.
509 Add an additional argument to any PHI nodes at the single
510 destination. IDX is the start node in jump threading path
511 we start to check to see if the new PHI argument has constant
512 value along the jump threading path. */
514 static void
515 create_edge_and_update_destination_phis (struct redirection_data *rd,
516 basic_block bb, int idx)
518 edge e = make_edge (bb, rd->path->last ()->e->dest, EDGE_FALLTHRU);
520 rescan_loop_exit (e, true, false);
521 e->probability = REG_BR_PROB_BASE;
522 e->count = bb->count;
524 /* We used to copy the thread path here. That was added in 2007
525 and dutifully updated through the representation changes in 2013.
527 In 2013 we added code to thread from an interior node through
528 the backedge to another interior node. That runs after the code
529 to thread through loop headers from outside the loop.
531 The latter may delete edges in the CFG, including those
532 which appeared in the jump threading path we copied here. Thus
533 we'd end up using a dangling pointer.
535 After reviewing the 2007/2011 code, I can't see how anything
536 depended on copying the AUX field and clearly copying the jump
537 threading path is problematical due to embedded edge pointers.
538 It has been removed. */
539 e->aux = NULL;
541 /* If there are any PHI nodes at the destination of the outgoing edge
542 from the duplicate block, then we will need to add a new argument
543 to them. The argument should have the same value as the argument
544 associated with the outgoing edge stored in RD. */
545 copy_phi_args (e->dest, rd->path->last ()->e, e, rd->path, idx);
548 /* Look through PATH beginning at START and return TRUE if there are
549 any additional blocks that need to be duplicated. Otherwise,
550 return FALSE. */
551 static bool
552 any_remaining_duplicated_blocks (vec<jump_thread_edge *> *path,
553 unsigned int start)
555 for (unsigned int i = start + 1; i < path->length (); i++)
557 if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK
558 || (*path)[i]->type == EDGE_COPY_SRC_BLOCK)
559 return true;
561 return false;
565 /* Compute the amount of profile count/frequency coming into the jump threading
566 path stored in RD that we are duplicating, returned in PATH_IN_COUNT_PTR and
567 PATH_IN_FREQ_PTR, as well as the amount of counts flowing out of the
568 duplicated path, returned in PATH_OUT_COUNT_PTR. LOCAL_INFO is used to
569 identify blocks duplicated for jump threading, which have duplicated
570 edges that need to be ignored in the analysis. Return true if path contains
571 a joiner, false otherwise.
573 In the non-joiner case, this is straightforward - all the counts/frequency
574 flowing into the jump threading path should flow through the duplicated
575 block and out of the duplicated path.
577 In the joiner case, it is very tricky. Some of the counts flowing into
578 the original path go offpath at the joiner. The problem is that while
579 we know how much total count goes off-path in the original control flow,
580 we don't know how many of the counts corresponding to just the jump
581 threading path go offpath at the joiner.
583 For example, assume we have the following control flow and identified
584 jump threading paths:
586 A B C
587 \ | /
588 Ea \ |Eb / Ec
589 \ | /
590 v v v
591 J <-- Joiner
593 Eoff/ \Eon
596 Soff Son <--- Normal
598 Ed/ \ Ee
603 Jump threading paths: A -> J -> Son -> D (path 1)
604 C -> J -> Son -> E (path 2)
606 Note that the control flow could be more complicated:
607 - Each jump threading path may have more than one incoming edge. I.e. A and
608 Ea could represent multiple incoming blocks/edges that are included in
609 path 1.
610 - There could be EDGE_NO_COPY_SRC_BLOCK edges after the joiner (either
611 before or after the "normal" copy block). These are not duplicated onto
612 the jump threading path, as they are single-successor.
613 - Any of the blocks along the path may have other incoming edges that
614 are not part of any jump threading path, but add profile counts along
615 the path.
617 In the aboe example, after all jump threading is complete, we will
618 end up with the following control flow:
620 A B C
621 | | |
622 Ea| |Eb |Ec
623 | | |
624 v v v
625 Ja J Jc
626 / \ / \Eon' / \
627 Eona/ \ ---/---\-------- \Eonc
628 / \ / / \ \
629 v v v v v
630 Sona Soff Son Sonc
631 \ /\ /
632 \___________ / \ _____/
633 \ / \/
634 vv v
637 The main issue to notice here is that when we are processing path 1
638 (A->J->Son->D) we need to figure out the outgoing edge weights to
639 the duplicated edges Ja->Sona and Ja->Soff, while ensuring that the
640 sum of the incoming weights to D remain Ed. The problem with simply
641 assuming that Ja (and Jc when processing path 2) has the same outgoing
642 probabilities to its successors as the original block J, is that after
643 all paths are processed and other edges/counts removed (e.g. none
644 of Ec will reach D after processing path 2), we may end up with not
645 enough count flowing along duplicated edge Sona->D.
647 Therefore, in the case of a joiner, we keep track of all counts
648 coming in along the current path, as well as from predecessors not
649 on any jump threading path (Eb in the above example). While we
650 first assume that the duplicated Eona for Ja->Sona has the same
651 probability as the original, we later compensate for other jump
652 threading paths that may eliminate edges. We do that by keep track
653 of all counts coming into the original path that are not in a jump
654 thread (Eb in the above example, but as noted earlier, there could
655 be other predecessors incoming to the path at various points, such
656 as at Son). Call this cumulative non-path count coming into the path
657 before D as Enonpath. We then ensure that the count from Sona->D is as at
658 least as big as (Ed - Enonpath), but no bigger than the minimum
659 weight along the jump threading path. The probabilities of both the
660 original and duplicated joiner block J and Ja will be adjusted
661 accordingly after the updates. */
663 static bool
664 compute_path_counts (struct redirection_data *rd,
665 ssa_local_info_t *local_info,
666 gcov_type *path_in_count_ptr,
667 gcov_type *path_out_count_ptr,
668 int *path_in_freq_ptr)
670 edge e = rd->incoming_edges->e;
671 vec<jump_thread_edge *> *path = THREAD_PATH (e);
672 edge elast = path->last ()->e;
673 gcov_type nonpath_count = 0;
674 bool has_joiner = false;
675 gcov_type path_in_count = 0;
676 int path_in_freq = 0;
678 /* Start by accumulating incoming edge counts to the path's first bb
679 into a couple buckets:
680 path_in_count: total count of incoming edges that flow into the
681 current path.
682 nonpath_count: total count of incoming edges that are not
683 flowing along *any* path. These are the counts
684 that will still flow along the original path after
685 all path duplication is done by potentially multiple
686 calls to this routine.
687 (any other incoming edge counts are for a different jump threading
688 path that will be handled by a later call to this routine.)
689 To make this easier, start by recording all incoming edges that flow into
690 the current path in a bitmap. We could add up the path's incoming edge
691 counts here, but we still need to walk all the first bb's incoming edges
692 below to add up the counts of the other edges not included in this jump
693 threading path. */
694 struct el *next, *el;
695 bitmap in_edge_srcs = BITMAP_ALLOC (NULL);
696 for (el = rd->incoming_edges; el; el = next)
698 next = el->next;
699 bitmap_set_bit (in_edge_srcs, el->e->src->index);
701 edge ein;
702 edge_iterator ei;
703 FOR_EACH_EDGE (ein, ei, e->dest->preds)
705 vec<jump_thread_edge *> *ein_path = THREAD_PATH (ein);
706 /* Simply check the incoming edge src against the set captured above. */
707 if (ein_path
708 && bitmap_bit_p (in_edge_srcs, (*ein_path)[0]->e->src->index))
710 /* It is necessary but not sufficient that the last path edges
711 are identical. There may be different paths that share the
712 same last path edge in the case where the last edge has a nocopy
713 source block. */
714 gcc_assert (ein_path->last ()->e == elast);
715 path_in_count += ein->count;
716 path_in_freq += EDGE_FREQUENCY (ein);
718 else if (!ein_path)
720 /* Keep track of the incoming edges that are not on any jump-threading
721 path. These counts will still flow out of original path after all
722 jump threading is complete. */
723 nonpath_count += ein->count;
726 BITMAP_FREE (in_edge_srcs);
728 /* Now compute the fraction of the total count coming into the first
729 path bb that is from the current threading path. */
730 gcov_type total_count = e->dest->count;
731 /* Handle incoming profile insanities. */
732 if (total_count < path_in_count)
733 path_in_count = total_count;
734 int onpath_scale = GCOV_COMPUTE_SCALE (path_in_count, total_count);
736 /* Walk the entire path to do some more computation in order to estimate
737 how much of the path_in_count will flow out of the duplicated threading
738 path. In the non-joiner case this is straightforward (it should be
739 the same as path_in_count, although we will handle incoming profile
740 insanities by setting it equal to the minimum count along the path).
742 In the joiner case, we need to estimate how much of the path_in_count
743 will stay on the threading path after the joiner's conditional branch.
744 We don't really know for sure how much of the counts
745 associated with this path go to each successor of the joiner, but we'll
746 estimate based on the fraction of the total count coming into the path
747 bb was from the threading paths (computed above in onpath_scale).
748 Afterwards, we will need to do some fixup to account for other threading
749 paths and possible profile insanities.
751 In order to estimate the joiner case's counts we also need to update
752 nonpath_count with any additional counts coming into the path. Other
753 blocks along the path may have additional predecessors from outside
754 the path. */
755 gcov_type path_out_count = path_in_count;
756 gcov_type min_path_count = path_in_count;
757 for (unsigned int i = 1; i < path->length (); i++)
759 edge epath = (*path)[i]->e;
760 gcov_type cur_count = epath->count;
761 if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
763 has_joiner = true;
764 cur_count = apply_probability (cur_count, onpath_scale);
766 /* In the joiner case we need to update nonpath_count for any edges
767 coming into the path that will contribute to the count flowing
768 into the path successor. */
769 if (has_joiner && epath != elast)
771 /* Look for other incoming edges after joiner. */
772 FOR_EACH_EDGE (ein, ei, epath->dest->preds)
774 if (ein != epath
775 /* Ignore in edges from blocks we have duplicated for a
776 threading path, which have duplicated edge counts until
777 they are redirected by an invocation of this routine. */
778 && !bitmap_bit_p (local_info->duplicate_blocks,
779 ein->src->index))
780 nonpath_count += ein->count;
783 if (cur_count < path_out_count)
784 path_out_count = cur_count;
785 if (epath->count < min_path_count)
786 min_path_count = epath->count;
789 /* We computed path_out_count above assuming that this path targeted
790 the joiner's on-path successor with the same likelihood as it
791 reached the joiner. However, other thread paths through the joiner
792 may take a different path through the normal copy source block
793 (i.e. they have a different elast), meaning that they do not
794 contribute any counts to this path's elast. As a result, it may
795 turn out that this path must have more count flowing to the on-path
796 successor of the joiner. Essentially, all of this path's elast
797 count must be contributed by this path and any nonpath counts
798 (since any path through the joiner with a different elast will not
799 include a copy of this elast in its duplicated path).
800 So ensure that this path's path_out_count is at least the
801 difference between elast->count and nonpath_count. Otherwise the edge
802 counts after threading will not be sane. */
803 if (has_joiner && path_out_count < elast->count - nonpath_count)
805 path_out_count = elast->count - nonpath_count;
806 /* But neither can we go above the minimum count along the path
807 we are duplicating. This can be an issue due to profile
808 insanities coming in to this pass. */
809 if (path_out_count > min_path_count)
810 path_out_count = min_path_count;
813 *path_in_count_ptr = path_in_count;
814 *path_out_count_ptr = path_out_count;
815 *path_in_freq_ptr = path_in_freq;
816 return has_joiner;
820 /* Update the counts and frequencies for both an original path
821 edge EPATH and its duplicate EDUP. The duplicate source block
822 will get a count/frequency of PATH_IN_COUNT and PATH_IN_FREQ,
823 and the duplicate edge EDUP will have a count of PATH_OUT_COUNT. */
824 static void
825 update_profile (edge epath, edge edup, gcov_type path_in_count,
826 gcov_type path_out_count, int path_in_freq)
829 /* First update the duplicated block's count / frequency. */
830 if (edup)
832 basic_block dup_block = edup->src;
833 gcc_assert (dup_block->count == 0);
834 gcc_assert (dup_block->frequency == 0);
835 dup_block->count = path_in_count;
836 dup_block->frequency = path_in_freq;
839 /* Now update the original block's count and frequency in the
840 opposite manner - remove the counts/freq that will flow
841 into the duplicated block. Handle underflow due to precision/
842 rounding issues. */
843 epath->src->count -= path_in_count;
844 if (epath->src->count < 0)
845 epath->src->count = 0;
846 epath->src->frequency -= path_in_freq;
847 if (epath->src->frequency < 0)
848 epath->src->frequency = 0;
850 /* Next update this path edge's original and duplicated counts. We know
851 that the duplicated path will have path_out_count flowing
852 out of it (in the joiner case this is the count along the duplicated path
853 out of the duplicated joiner). This count can then be removed from the
854 original path edge. */
855 if (edup)
856 edup->count = path_out_count;
857 epath->count -= path_out_count;
858 gcc_assert (epath->count >= 0);
862 /* The duplicate and original joiner blocks may end up with different
863 probabilities (different from both the original and from each other).
864 Recompute the probabilities here once we have updated the edge
865 counts and frequencies. */
867 static void
868 recompute_probabilities (basic_block bb)
870 edge esucc;
871 edge_iterator ei;
872 FOR_EACH_EDGE (esucc, ei, bb->succs)
874 if (bb->count)
875 esucc->probability = GCOV_COMPUTE_SCALE (esucc->count,
876 bb->count);
877 if (esucc->probability > REG_BR_PROB_BASE)
879 /* Can happen with missing/guessed probabilities, since we
880 may determine that more is flowing along duplicated
881 path than joiner succ probabilities allowed.
882 Counts and freqs will be insane after jump threading,
883 at least make sure probability is sane or we will
884 get a flow verification error.
885 Not much we can do to make counts/freqs sane without
886 redoing the profile estimation. */
887 esucc->probability = REG_BR_PROB_BASE;
893 /* Update the counts of the original and duplicated edges from a joiner
894 that go off path, given that we have already determined that the
895 duplicate joiner DUP_BB has incoming count PATH_IN_COUNT and
896 outgoing count along the path PATH_OUT_COUNT. The original (on-)path
897 edge from joiner is EPATH. */
899 static void
900 update_joiner_offpath_counts (edge epath, basic_block dup_bb,
901 gcov_type path_in_count,
902 gcov_type path_out_count)
904 /* Compute the count that currently flows off path from the joiner.
905 In other words, the total count of joiner's out edges other than
906 epath. Compute this by walking the successors instead of
907 subtracting epath's count from the joiner bb count, since there
908 are sometimes slight insanities where the total out edge count is
909 larger than the bb count (possibly due to rounding/truncation
910 errors). */
911 gcov_type total_orig_off_path_count = 0;
912 edge enonpath;
913 edge_iterator ei;
914 FOR_EACH_EDGE (enonpath, ei, epath->src->succs)
916 if (enonpath == epath)
917 continue;
918 total_orig_off_path_count += enonpath->count;
921 /* For the path that we are duplicating, the amount that will flow
922 off path from the duplicated joiner is the delta between the
923 path's cumulative in count and the portion of that count we
924 estimated above as flowing from the joiner along the duplicated
925 path. */
926 gcov_type total_dup_off_path_count = path_in_count - path_out_count;
928 /* Now do the actual updates of the off-path edges. */
929 FOR_EACH_EDGE (enonpath, ei, epath->src->succs)
931 /* Look for edges going off of the threading path. */
932 if (enonpath == epath)
933 continue;
935 /* Find the corresponding edge out of the duplicated joiner. */
936 edge enonpathdup = find_edge (dup_bb, enonpath->dest);
937 gcc_assert (enonpathdup);
939 /* We can't use the original probability of the joiner's out
940 edges, since the probabilities of the original branch
941 and the duplicated branches may vary after all threading is
942 complete. But apportion the duplicated joiner's off-path
943 total edge count computed earlier (total_dup_off_path_count)
944 among the duplicated off-path edges based on their original
945 ratio to the full off-path count (total_orig_off_path_count).
947 int scale = GCOV_COMPUTE_SCALE (enonpath->count,
948 total_orig_off_path_count);
949 /* Give the duplicated offpath edge a portion of the duplicated
950 total. */
951 enonpathdup->count = apply_scale (scale,
952 total_dup_off_path_count);
953 /* Now update the original offpath edge count, handling underflow
954 due to rounding errors. */
955 enonpath->count -= enonpathdup->count;
956 if (enonpath->count < 0)
957 enonpath->count = 0;
962 /* Check if the paths through RD all have estimated frequencies but zero
963 profile counts. This is more accurate than checking the entry block
964 for a zero profile count, since profile insanities sometimes creep in. */
966 static bool
967 estimated_freqs_path (struct redirection_data *rd)
969 edge e = rd->incoming_edges->e;
970 vec<jump_thread_edge *> *path = THREAD_PATH (e);
971 edge ein;
972 edge_iterator ei;
973 bool non_zero_freq = false;
974 FOR_EACH_EDGE (ein, ei, e->dest->preds)
976 if (ein->count)
977 return false;
978 non_zero_freq |= ein->src->frequency != 0;
981 for (unsigned int i = 1; i < path->length (); i++)
983 edge epath = (*path)[i]->e;
984 if (epath->src->count)
985 return false;
986 non_zero_freq |= epath->src->frequency != 0;
987 edge esucc;
988 FOR_EACH_EDGE (esucc, ei, epath->src->succs)
990 if (esucc->count)
991 return false;
992 non_zero_freq |= esucc->src->frequency != 0;
995 return non_zero_freq;
999 /* Invoked for routines that have guessed frequencies and no profile
1000 counts to record the block and edge frequencies for paths through RD
1001 in the profile count fields of those blocks and edges. This is because
1002 ssa_fix_duplicate_block_edges incrementally updates the block and
1003 edge counts as edges are redirected, and it is difficult to do that
1004 for edge frequencies which are computed on the fly from the source
1005 block frequency and probability. When a block frequency is updated
1006 its outgoing edge frequencies are affected and become difficult to
1007 adjust. */
1009 static void
1010 freqs_to_counts_path (struct redirection_data *rd)
1012 edge e = rd->incoming_edges->e;
1013 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1014 edge ein;
1015 edge_iterator ei;
1016 FOR_EACH_EDGE (ein, ei, e->dest->preds)
1018 /* Scale up the frequency by REG_BR_PROB_BASE, to avoid rounding
1019 errors applying the probability when the frequencies are very
1020 small. */
1021 ein->count = apply_probability (ein->src->frequency * REG_BR_PROB_BASE,
1022 ein->probability);
1025 for (unsigned int i = 1; i < path->length (); i++)
1027 edge epath = (*path)[i]->e;
1028 edge esucc;
1029 /* Scale up the frequency by REG_BR_PROB_BASE, to avoid rounding
1030 errors applying the edge probability when the frequencies are very
1031 small. */
1032 epath->src->count = epath->src->frequency * REG_BR_PROB_BASE;
1033 FOR_EACH_EDGE (esucc, ei, epath->src->succs)
1034 esucc->count = apply_probability (esucc->src->count,
1035 esucc->probability);
1040 /* For routines that have guessed frequencies and no profile counts, where we
1041 used freqs_to_counts_path to record block and edge frequencies for paths
1042 through RD, we clear the counts after completing all updates for RD.
1043 The updates in ssa_fix_duplicate_block_edges are based off the count fields,
1044 but the block frequencies and edge probabilities were updated as well,
1045 so we can simply clear the count fields. */
1047 static void
1048 clear_counts_path (struct redirection_data *rd)
1050 edge e = rd->incoming_edges->e;
1051 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1052 edge ein, esucc;
1053 edge_iterator ei;
1054 FOR_EACH_EDGE (ein, ei, e->dest->preds)
1055 ein->count = 0;
1057 /* First clear counts along original path. */
1058 for (unsigned int i = 1; i < path->length (); i++)
1060 edge epath = (*path)[i]->e;
1061 FOR_EACH_EDGE (esucc, ei, epath->src->succs)
1062 esucc->count = 0;
1063 epath->src->count = 0;
1065 /* Also need to clear the counts along duplicated path. */
1066 for (unsigned int i = 0; i < 2; i++)
1068 basic_block dup = rd->dup_blocks[i];
1069 if (!dup)
1070 continue;
1071 FOR_EACH_EDGE (esucc, ei, dup->succs)
1072 esucc->count = 0;
1073 dup->count = 0;
1077 /* Wire up the outgoing edges from the duplicate blocks and
1078 update any PHIs as needed. Also update the profile counts
1079 on the original and duplicate blocks and edges. */
1080 void
1081 ssa_fix_duplicate_block_edges (struct redirection_data *rd,
1082 ssa_local_info_t *local_info)
1084 bool multi_incomings = (rd->incoming_edges->next != NULL);
1085 edge e = rd->incoming_edges->e;
1086 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1087 edge elast = path->last ()->e;
1088 gcov_type path_in_count = 0;
1089 gcov_type path_out_count = 0;
1090 int path_in_freq = 0;
1092 /* This routine updates profile counts, frequencies, and probabilities
1093 incrementally. Since it is difficult to do the incremental updates
1094 using frequencies/probabilities alone, for routines without profile
1095 data we first take a snapshot of the existing block and edge frequencies
1096 by copying them into the empty profile count fields. These counts are
1097 then used to do the incremental updates, and cleared at the end of this
1098 routine. If the function is marked as having a profile, we still check
1099 to see if the paths through RD are using estimated frequencies because
1100 the routine had zero profile counts. */
1101 bool do_freqs_to_counts = (profile_status_for_fn (cfun) != PROFILE_READ
1102 || estimated_freqs_path (rd));
1103 if (do_freqs_to_counts)
1104 freqs_to_counts_path (rd);
1106 /* First determine how much profile count to move from original
1107 path to the duplicate path. This is tricky in the presence of
1108 a joiner (see comments for compute_path_counts), where some portion
1109 of the path's counts will flow off-path from the joiner. In the
1110 non-joiner case the path_in_count and path_out_count should be the
1111 same. */
1112 bool has_joiner = compute_path_counts (rd, local_info,
1113 &path_in_count, &path_out_count,
1114 &path_in_freq);
1116 int cur_path_freq = path_in_freq;
1117 for (unsigned int count = 0, i = 1; i < path->length (); i++)
1119 edge epath = (*path)[i]->e;
1121 /* If we were threading through an joiner block, then we want
1122 to keep its control statement and redirect an outgoing edge.
1123 Else we want to remove the control statement & edges, then create
1124 a new outgoing edge. In both cases we may need to update PHIs. */
1125 if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
1127 edge victim;
1128 edge e2;
1130 gcc_assert (has_joiner);
1132 /* This updates the PHIs at the destination of the duplicate
1133 block. Pass 0 instead of i if we are threading a path which
1134 has multiple incoming edges. */
1135 update_destination_phis (local_info->bb, rd->dup_blocks[count],
1136 path, multi_incomings ? 0 : i);
1138 /* Find the edge from the duplicate block to the block we're
1139 threading through. That's the edge we want to redirect. */
1140 victim = find_edge (rd->dup_blocks[count], (*path)[i]->e->dest);
1142 /* If there are no remaining blocks on the path to duplicate,
1143 then redirect VICTIM to the final destination of the jump
1144 threading path. */
1145 if (!any_remaining_duplicated_blocks (path, i))
1147 e2 = redirect_edge_and_branch (victim, elast->dest);
1148 /* If we redirected the edge, then we need to copy PHI arguments
1149 at the target. If the edge already existed (e2 != victim
1150 case), then the PHIs in the target already have the correct
1151 arguments. */
1152 if (e2 == victim)
1153 copy_phi_args (e2->dest, elast, e2,
1154 path, multi_incomings ? 0 : i);
1156 else
1158 /* Redirect VICTIM to the next duplicated block in the path. */
1159 e2 = redirect_edge_and_branch (victim, rd->dup_blocks[count + 1]);
1161 /* We need to update the PHIs in the next duplicated block. We
1162 want the new PHI args to have the same value as they had
1163 in the source of the next duplicate block.
1165 Thus, we need to know which edge we traversed into the
1166 source of the duplicate. Furthermore, we may have
1167 traversed many edges to reach the source of the duplicate.
1169 Walk through the path starting at element I until we
1170 hit an edge marked with EDGE_COPY_SRC_BLOCK. We want
1171 the edge from the prior element. */
1172 for (unsigned int j = i + 1; j < path->length (); j++)
1174 if ((*path)[j]->type == EDGE_COPY_SRC_BLOCK)
1176 copy_phi_arg_into_existing_phi ((*path)[j - 1]->e, e2);
1177 break;
1182 /* Update the counts and frequency of both the original block
1183 and path edge, and the duplicates. The path duplicate's
1184 incoming count and frequency are the totals for all edges
1185 incoming to this jump threading path computed earlier.
1186 And we know that the duplicated path will have path_out_count
1187 flowing out of it (i.e. along the duplicated path out of the
1188 duplicated joiner). */
1189 update_profile (epath, e2, path_in_count, path_out_count,
1190 path_in_freq);
1192 /* Next we need to update the counts of the original and duplicated
1193 edges from the joiner that go off path. */
1194 update_joiner_offpath_counts (epath, e2->src, path_in_count,
1195 path_out_count);
1197 /* Finally, we need to set the probabilities on the duplicated
1198 edges out of the duplicated joiner (e2->src). The probabilities
1199 along the original path will all be updated below after we finish
1200 processing the whole path. */
1201 recompute_probabilities (e2->src);
1203 /* Record the frequency flowing to the downstream duplicated
1204 path blocks. */
1205 cur_path_freq = EDGE_FREQUENCY (e2);
1207 else if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK)
1209 remove_ctrl_stmt_and_useless_edges (rd->dup_blocks[count], NULL);
1210 create_edge_and_update_destination_phis (rd, rd->dup_blocks[count],
1211 multi_incomings ? 0 : i);
1212 if (count == 1)
1213 single_succ_edge (rd->dup_blocks[1])->aux = NULL;
1215 /* Update the counts and frequency of both the original block
1216 and path edge, and the duplicates. Since we are now after
1217 any joiner that may have existed on the path, the count
1218 flowing along the duplicated threaded path is path_out_count.
1219 If we didn't have a joiner, then cur_path_freq was the sum
1220 of the total frequencies along all incoming edges to the
1221 thread path (path_in_freq). If we had a joiner, it would have
1222 been updated at the end of that handling to the edge frequency
1223 along the duplicated joiner path edge. */
1224 update_profile (epath, EDGE_SUCC (rd->dup_blocks[count], 0),
1225 path_out_count, path_out_count,
1226 cur_path_freq);
1228 else
1230 /* No copy case. In this case we don't have an equivalent block
1231 on the duplicated thread path to update, but we do need
1232 to remove the portion of the counts/freqs that were moved
1233 to the duplicated path from the counts/freqs flowing through
1234 this block on the original path. Since all the no-copy edges
1235 are after any joiner, the removed count is the same as
1236 path_out_count.
1238 If we didn't have a joiner, then cur_path_freq was the sum
1239 of the total frequencies along all incoming edges to the
1240 thread path (path_in_freq). If we had a joiner, it would have
1241 been updated at the end of that handling to the edge frequency
1242 along the duplicated joiner path edge. */
1243 update_profile (epath, NULL, path_out_count, path_out_count,
1244 cur_path_freq);
1247 /* Increment the index into the duplicated path when we processed
1248 a duplicated block. */
1249 if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK
1250 || (*path)[i]->type == EDGE_COPY_SRC_BLOCK)
1252 count++;
1256 /* Now walk orig blocks and update their probabilities, since the
1257 counts and freqs should be updated properly by above loop. */
1258 for (unsigned int i = 1; i < path->length (); i++)
1260 edge epath = (*path)[i]->e;
1261 recompute_probabilities (epath->src);
1264 /* Done with all profile and frequency updates, clear counts if they
1265 were copied. */
1266 if (do_freqs_to_counts)
1267 clear_counts_path (rd);
1270 /* Hash table traversal callback routine to create duplicate blocks. */
1273 ssa_create_duplicates (struct redirection_data **slot,
1274 ssa_local_info_t *local_info)
1276 struct redirection_data *rd = *slot;
1278 /* The second duplicated block in a jump threading path is specific
1279 to the path. So it gets stored in RD rather than in LOCAL_DATA.
1281 Each time we're called, we have to look through the path and see
1282 if a second block needs to be duplicated.
1284 Note the search starts with the third edge on the path. The first
1285 edge is the incoming edge, the second edge always has its source
1286 duplicated. Thus we start our search with the third edge. */
1287 vec<jump_thread_edge *> *path = rd->path;
1288 for (unsigned int i = 2; i < path->length (); i++)
1290 if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK
1291 || (*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
1293 create_block_for_threading ((*path)[i]->e->src, rd, 1,
1294 &local_info->duplicate_blocks);
1295 break;
1299 /* Create a template block if we have not done so already. Otherwise
1300 use the template to create a new block. */
1301 if (local_info->template_block == NULL)
1303 create_block_for_threading ((*path)[1]->e->src, rd, 0,
1304 &local_info->duplicate_blocks);
1305 local_info->template_block = rd->dup_blocks[0];
1307 /* We do not create any outgoing edges for the template. We will
1308 take care of that in a later traversal. That way we do not
1309 create edges that are going to just be deleted. */
1311 else
1313 create_block_for_threading (local_info->template_block, rd, 0,
1314 &local_info->duplicate_blocks);
1316 /* Go ahead and wire up outgoing edges and update PHIs for the duplicate
1317 block. */
1318 ssa_fix_duplicate_block_edges (rd, local_info);
1321 /* Keep walking the hash table. */
1322 return 1;
1325 /* We did not create any outgoing edges for the template block during
1326 block creation. This hash table traversal callback creates the
1327 outgoing edge for the template block. */
1329 inline int
1330 ssa_fixup_template_block (struct redirection_data **slot,
1331 ssa_local_info_t *local_info)
1333 struct redirection_data *rd = *slot;
1335 /* If this is the template block halt the traversal after updating
1336 it appropriately.
1338 If we were threading through an joiner block, then we want
1339 to keep its control statement and redirect an outgoing edge.
1340 Else we want to remove the control statement & edges, then create
1341 a new outgoing edge. In both cases we may need to update PHIs. */
1342 if (rd->dup_blocks[0] && rd->dup_blocks[0] == local_info->template_block)
1344 ssa_fix_duplicate_block_edges (rd, local_info);
1345 return 0;
1348 return 1;
1351 /* Hash table traversal callback to redirect each incoming edge
1352 associated with this hash table element to its new destination. */
1355 ssa_redirect_edges (struct redirection_data **slot,
1356 ssa_local_info_t *local_info)
1358 struct redirection_data *rd = *slot;
1359 struct el *next, *el;
1361 /* Walk over all the incoming edges associated associated with this
1362 hash table entry. */
1363 for (el = rd->incoming_edges; el; el = next)
1365 edge e = el->e;
1366 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1368 /* Go ahead and free this element from the list. Doing this now
1369 avoids the need for another list walk when we destroy the hash
1370 table. */
1371 next = el->next;
1372 free (el);
1374 thread_stats.num_threaded_edges++;
1376 if (rd->dup_blocks[0])
1378 edge e2;
1380 if (dump_file && (dump_flags & TDF_DETAILS))
1381 fprintf (dump_file, " Threaded jump %d --> %d to %d\n",
1382 e->src->index, e->dest->index, rd->dup_blocks[0]->index);
1384 /* If we redirect a loop latch edge cancel its loop. */
1385 if (e->src == e->src->loop_father->latch)
1386 mark_loop_for_removal (e->src->loop_father);
1388 /* Redirect the incoming edge (possibly to the joiner block) to the
1389 appropriate duplicate block. */
1390 e2 = redirect_edge_and_branch (e, rd->dup_blocks[0]);
1391 gcc_assert (e == e2);
1392 flush_pending_stmts (e2);
1395 /* Go ahead and clear E->aux. It's not needed anymore and failure
1396 to clear it will cause all kinds of unpleasant problems later. */
1397 delete_jump_thread_path (path);
1398 e->aux = NULL;
1402 /* Indicate that we actually threaded one or more jumps. */
1403 if (rd->incoming_edges)
1404 local_info->jumps_threaded = true;
1406 return 1;
1409 /* Return true if this block has no executable statements other than
1410 a simple ctrl flow instruction. When the number of outgoing edges
1411 is one, this is equivalent to a "forwarder" block. */
1413 static bool
1414 redirection_block_p (basic_block bb)
1416 gimple_stmt_iterator gsi;
1418 /* Advance to the first executable statement. */
1419 gsi = gsi_start_bb (bb);
1420 while (!gsi_end_p (gsi)
1421 && (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL
1422 || is_gimple_debug (gsi_stmt (gsi))
1423 || gimple_nop_p (gsi_stmt (gsi))))
1424 gsi_next (&gsi);
1426 /* Check if this is an empty block. */
1427 if (gsi_end_p (gsi))
1428 return true;
1430 /* Test that we've reached the terminating control statement. */
1431 return gsi_stmt (gsi)
1432 && (gimple_code (gsi_stmt (gsi)) == GIMPLE_COND
1433 || gimple_code (gsi_stmt (gsi)) == GIMPLE_GOTO
1434 || gimple_code (gsi_stmt (gsi)) == GIMPLE_SWITCH);
1437 /* BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB
1438 is reached via one or more specific incoming edges, we know which
1439 outgoing edge from BB will be traversed.
1441 We want to redirect those incoming edges to the target of the
1442 appropriate outgoing edge. Doing so avoids a conditional branch
1443 and may expose new optimization opportunities. Note that we have
1444 to update dominator tree and SSA graph after such changes.
1446 The key to keeping the SSA graph update manageable is to duplicate
1447 the side effects occurring in BB so that those side effects still
1448 occur on the paths which bypass BB after redirecting edges.
1450 We accomplish this by creating duplicates of BB and arranging for
1451 the duplicates to unconditionally pass control to one specific
1452 successor of BB. We then revector the incoming edges into BB to
1453 the appropriate duplicate of BB.
1455 If NOLOOP_ONLY is true, we only perform the threading as long as it
1456 does not affect the structure of the loops in a nontrivial way.
1458 If JOINERS is true, then thread through joiner blocks as well. */
1460 static bool
1461 thread_block_1 (basic_block bb, bool noloop_only, bool joiners)
1463 /* E is an incoming edge into BB that we may or may not want to
1464 redirect to a duplicate of BB. */
1465 edge e, e2;
1466 edge_iterator ei;
1467 ssa_local_info_t local_info;
1469 local_info.duplicate_blocks = BITMAP_ALLOC (NULL);
1471 /* To avoid scanning a linear array for the element we need we instead
1472 use a hash table. For normal code there should be no noticeable
1473 difference. However, if we have a block with a large number of
1474 incoming and outgoing edges such linear searches can get expensive. */
1475 redirection_data
1476 = new hash_table<struct redirection_data> (EDGE_COUNT (bb->succs));
1478 /* Record each unique threaded destination into a hash table for
1479 efficient lookups. */
1480 FOR_EACH_EDGE (e, ei, bb->preds)
1482 if (e->aux == NULL)
1483 continue;
1485 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1487 if (((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && !joiners)
1488 || ((*path)[1]->type == EDGE_COPY_SRC_BLOCK && joiners))
1489 continue;
1491 e2 = path->last ()->e;
1492 if (!e2 || noloop_only)
1494 /* If NOLOOP_ONLY is true, we only allow threading through the
1495 header of a loop to exit edges. */
1497 /* One case occurs when there was loop header buried in a jump
1498 threading path that crosses loop boundaries. We do not try
1499 and thread this elsewhere, so just cancel the jump threading
1500 request by clearing the AUX field now. */
1501 if ((bb->loop_father != e2->src->loop_father
1502 && !loop_exit_edge_p (e2->src->loop_father, e2))
1503 || (e2->src->loop_father != e2->dest->loop_father
1504 && !loop_exit_edge_p (e2->src->loop_father, e2)))
1506 /* Since this case is not handled by our special code
1507 to thread through a loop header, we must explicitly
1508 cancel the threading request here. */
1509 delete_jump_thread_path (path);
1510 e->aux = NULL;
1511 continue;
1514 /* Another case occurs when trying to thread through our
1515 own loop header, possibly from inside the loop. We will
1516 thread these later. */
1517 unsigned int i;
1518 for (i = 1; i < path->length (); i++)
1520 if ((*path)[i]->e->src == bb->loop_father->header
1521 && (!loop_exit_edge_p (bb->loop_father, e2)
1522 || (*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK))
1523 break;
1526 if (i != path->length ())
1527 continue;
1530 /* Insert the outgoing edge into the hash table if it is not
1531 already in the hash table. */
1532 lookup_redirection_data (e, INSERT);
1535 /* We do not update dominance info. */
1536 free_dominance_info (CDI_DOMINATORS);
1538 /* We know we only thread through the loop header to loop exits.
1539 Let the basic block duplication hook know we are not creating
1540 a multiple entry loop. */
1541 if (noloop_only
1542 && bb == bb->loop_father->header)
1543 set_loop_copy (bb->loop_father, loop_outer (bb->loop_father));
1545 /* Now create duplicates of BB.
1547 Note that for a block with a high outgoing degree we can waste
1548 a lot of time and memory creating and destroying useless edges.
1550 So we first duplicate BB and remove the control structure at the
1551 tail of the duplicate as well as all outgoing edges from the
1552 duplicate. We then use that duplicate block as a template for
1553 the rest of the duplicates. */
1554 local_info.template_block = NULL;
1555 local_info.bb = bb;
1556 local_info.jumps_threaded = false;
1557 redirection_data->traverse <ssa_local_info_t *, ssa_create_duplicates>
1558 (&local_info);
1560 /* The template does not have an outgoing edge. Create that outgoing
1561 edge and update PHI nodes as the edge's target as necessary.
1563 We do this after creating all the duplicates to avoid creating
1564 unnecessary edges. */
1565 redirection_data->traverse <ssa_local_info_t *, ssa_fixup_template_block>
1566 (&local_info);
1568 /* The hash table traversals above created the duplicate blocks (and the
1569 statements within the duplicate blocks). This loop creates PHI nodes for
1570 the duplicated blocks and redirects the incoming edges into BB to reach
1571 the duplicates of BB. */
1572 redirection_data->traverse <ssa_local_info_t *, ssa_redirect_edges>
1573 (&local_info);
1575 /* Done with this block. Clear REDIRECTION_DATA. */
1576 delete redirection_data;
1577 redirection_data = NULL;
1579 if (noloop_only
1580 && bb == bb->loop_father->header)
1581 set_loop_copy (bb->loop_father, NULL);
1583 BITMAP_FREE (local_info.duplicate_blocks);
1584 local_info.duplicate_blocks = NULL;
1586 /* Indicate to our caller whether or not any jumps were threaded. */
1587 return local_info.jumps_threaded;
1590 /* Wrapper for thread_block_1 so that we can first handle jump
1591 thread paths which do not involve copying joiner blocks, then
1592 handle jump thread paths which have joiner blocks.
1594 By doing things this way we can be as aggressive as possible and
1595 not worry that copying a joiner block will create a jump threading
1596 opportunity. */
1598 static bool
1599 thread_block (basic_block bb, bool noloop_only)
1601 bool retval;
1602 retval = thread_block_1 (bb, noloop_only, false);
1603 retval |= thread_block_1 (bb, noloop_only, true);
1604 return retval;
1608 /* Threads edge E through E->dest to the edge THREAD_TARGET (E). Returns the
1609 copy of E->dest created during threading, or E->dest if it was not necessary
1610 to copy it (E is its single predecessor). */
1612 static basic_block
1613 thread_single_edge (edge e)
1615 basic_block bb = e->dest;
1616 struct redirection_data rd;
1617 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1618 edge eto = (*path)[1]->e;
1620 for (unsigned int i = 0; i < path->length (); i++)
1621 delete (*path)[i];
1622 delete path;
1623 e->aux = NULL;
1625 thread_stats.num_threaded_edges++;
1627 if (single_pred_p (bb))
1629 /* If BB has just a single predecessor, we should only remove the
1630 control statements at its end, and successors except for ETO. */
1631 remove_ctrl_stmt_and_useless_edges (bb, eto->dest);
1633 /* And fixup the flags on the single remaining edge. */
1634 eto->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL);
1635 eto->flags |= EDGE_FALLTHRU;
1637 return bb;
1640 /* Otherwise, we need to create a copy. */
1641 if (e->dest == eto->src)
1642 update_bb_profile_for_threading (bb, EDGE_FREQUENCY (e), e->count, eto);
1644 vec<jump_thread_edge *> *npath = new vec<jump_thread_edge *> ();
1645 jump_thread_edge *x = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
1646 npath->safe_push (x);
1648 x = new jump_thread_edge (eto, EDGE_COPY_SRC_BLOCK);
1649 npath->safe_push (x);
1650 rd.path = npath;
1652 create_block_for_threading (bb, &rd, 0, NULL);
1653 remove_ctrl_stmt_and_useless_edges (rd.dup_blocks[0], NULL);
1654 create_edge_and_update_destination_phis (&rd, rd.dup_blocks[0], 0);
1656 if (dump_file && (dump_flags & TDF_DETAILS))
1657 fprintf (dump_file, " Threaded jump %d --> %d to %d\n",
1658 e->src->index, e->dest->index, rd.dup_blocks[0]->index);
1660 rd.dup_blocks[0]->count = e->count;
1661 rd.dup_blocks[0]->frequency = EDGE_FREQUENCY (e);
1662 single_succ_edge (rd.dup_blocks[0])->count = e->count;
1663 redirect_edge_and_branch (e, rd.dup_blocks[0]);
1664 flush_pending_stmts (e);
1666 return rd.dup_blocks[0];
1669 /* Callback for dfs_enumerate_from. Returns true if BB is different
1670 from STOP and DBDS_CE_STOP. */
1672 static basic_block dbds_ce_stop;
1673 static bool
1674 dbds_continue_enumeration_p (const_basic_block bb, const void *stop)
1676 return (bb != (const_basic_block) stop
1677 && bb != dbds_ce_stop);
1680 /* Evaluates the dominance relationship of latch of the LOOP and BB, and
1681 returns the state. */
1683 enum bb_dom_status
1685 /* BB does not dominate latch of the LOOP. */
1686 DOMST_NONDOMINATING,
1687 /* The LOOP is broken (there is no path from the header to its latch. */
1688 DOMST_LOOP_BROKEN,
1689 /* BB dominates the latch of the LOOP. */
1690 DOMST_DOMINATING
1693 static enum bb_dom_status
1694 determine_bb_domination_status (struct loop *loop, basic_block bb)
1696 basic_block *bblocks;
1697 unsigned nblocks, i;
1698 bool bb_reachable = false;
1699 edge_iterator ei;
1700 edge e;
1702 /* This function assumes BB is a successor of LOOP->header.
1703 If that is not the case return DOMST_NONDOMINATING which
1704 is always safe. */
1706 bool ok = false;
1708 FOR_EACH_EDGE (e, ei, bb->preds)
1710 if (e->src == loop->header)
1712 ok = true;
1713 break;
1717 if (!ok)
1718 return DOMST_NONDOMINATING;
1721 if (bb == loop->latch)
1722 return DOMST_DOMINATING;
1724 /* Check that BB dominates LOOP->latch, and that it is back-reachable
1725 from it. */
1727 bblocks = XCNEWVEC (basic_block, loop->num_nodes);
1728 dbds_ce_stop = loop->header;
1729 nblocks = dfs_enumerate_from (loop->latch, 1, dbds_continue_enumeration_p,
1730 bblocks, loop->num_nodes, bb);
1731 for (i = 0; i < nblocks; i++)
1732 FOR_EACH_EDGE (e, ei, bblocks[i]->preds)
1734 if (e->src == loop->header)
1736 free (bblocks);
1737 return DOMST_NONDOMINATING;
1739 if (e->src == bb)
1740 bb_reachable = true;
1743 free (bblocks);
1744 return (bb_reachable ? DOMST_DOMINATING : DOMST_LOOP_BROKEN);
1747 /* Return true if BB is part of the new pre-header that is created
1748 when threading the latch to DATA. */
1750 static bool
1751 def_split_header_continue_p (const_basic_block bb, const void *data)
1753 const_basic_block new_header = (const_basic_block) data;
1754 const struct loop *l;
1756 if (bb == new_header
1757 || loop_depth (bb->loop_father) < loop_depth (new_header->loop_father))
1758 return false;
1759 for (l = bb->loop_father; l; l = loop_outer (l))
1760 if (l == new_header->loop_father)
1761 return true;
1762 return false;
1765 /* Thread jumps through the header of LOOP. Returns true if cfg changes.
1766 If MAY_PEEL_LOOP_HEADERS is false, we avoid threading from entry edges
1767 to the inside of the loop. */
1769 static bool
1770 thread_through_loop_header (struct loop *loop, bool may_peel_loop_headers)
1772 basic_block header = loop->header;
1773 edge e, tgt_edge, latch = loop_latch_edge (loop);
1774 edge_iterator ei;
1775 basic_block tgt_bb, atgt_bb;
1776 enum bb_dom_status domst;
1778 /* We have already threaded through headers to exits, so all the threading
1779 requests now are to the inside of the loop. We need to avoid creating
1780 irreducible regions (i.e., loops with more than one entry block), and
1781 also loop with several latch edges, or new subloops of the loop (although
1782 there are cases where it might be appropriate, it is difficult to decide,
1783 and doing it wrongly may confuse other optimizers).
1785 We could handle more general cases here. However, the intention is to
1786 preserve some information about the loop, which is impossible if its
1787 structure changes significantly, in a way that is not well understood.
1788 Thus we only handle few important special cases, in which also updating
1789 of the loop-carried information should be feasible:
1791 1) Propagation of latch edge to a block that dominates the latch block
1792 of a loop. This aims to handle the following idiom:
1794 first = 1;
1795 while (1)
1797 if (first)
1798 initialize;
1799 first = 0;
1800 body;
1803 After threading the latch edge, this becomes
1805 first = 1;
1806 if (first)
1807 initialize;
1808 while (1)
1810 first = 0;
1811 body;
1814 The original header of the loop is moved out of it, and we may thread
1815 the remaining edges through it without further constraints.
1817 2) All entry edges are propagated to a single basic block that dominates
1818 the latch block of the loop. This aims to handle the following idiom
1819 (normally created for "for" loops):
1821 i = 0;
1822 while (1)
1824 if (i >= 100)
1825 break;
1826 body;
1827 i++;
1830 This becomes
1832 i = 0;
1833 while (1)
1835 body;
1836 i++;
1837 if (i >= 100)
1838 break;
1842 /* Threading through the header won't improve the code if the header has just
1843 one successor. */
1844 if (single_succ_p (header))
1845 goto fail;
1847 /* If we threaded the latch using a joiner block, we cancel the
1848 threading opportunity out of an abundance of caution. However,
1849 still allow threading from outside to inside the loop. */
1850 if (latch->aux)
1852 vec<jump_thread_edge *> *path = THREAD_PATH (latch);
1853 if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
1855 delete_jump_thread_path (path);
1856 latch->aux = NULL;
1860 if (latch->aux)
1862 vec<jump_thread_edge *> *path = THREAD_PATH (latch);
1863 tgt_edge = (*path)[1]->e;
1864 tgt_bb = tgt_edge->dest;
1866 else if (!may_peel_loop_headers
1867 && !redirection_block_p (loop->header))
1868 goto fail;
1869 else
1871 tgt_bb = NULL;
1872 tgt_edge = NULL;
1873 FOR_EACH_EDGE (e, ei, header->preds)
1875 if (!e->aux)
1877 if (e == latch)
1878 continue;
1880 /* If latch is not threaded, and there is a header
1881 edge that is not threaded, we would create loop
1882 with multiple entries. */
1883 goto fail;
1886 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1888 if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
1889 goto fail;
1890 tgt_edge = (*path)[1]->e;
1891 atgt_bb = tgt_edge->dest;
1892 if (!tgt_bb)
1893 tgt_bb = atgt_bb;
1894 /* Two targets of threading would make us create loop
1895 with multiple entries. */
1896 else if (tgt_bb != atgt_bb)
1897 goto fail;
1900 if (!tgt_bb)
1902 /* There are no threading requests. */
1903 return false;
1906 /* Redirecting to empty loop latch is useless. */
1907 if (tgt_bb == loop->latch
1908 && empty_block_p (loop->latch))
1909 goto fail;
1912 /* The target block must dominate the loop latch, otherwise we would be
1913 creating a subloop. */
1914 domst = determine_bb_domination_status (loop, tgt_bb);
1915 if (domst == DOMST_NONDOMINATING)
1916 goto fail;
1917 if (domst == DOMST_LOOP_BROKEN)
1919 /* If the loop ceased to exist, mark it as such, and thread through its
1920 original header. */
1921 mark_loop_for_removal (loop);
1922 return thread_block (header, false);
1925 if (tgt_bb->loop_father->header == tgt_bb)
1927 /* If the target of the threading is a header of a subloop, we need
1928 to create a preheader for it, so that the headers of the two loops
1929 do not merge. */
1930 if (EDGE_COUNT (tgt_bb->preds) > 2)
1932 tgt_bb = create_preheader (tgt_bb->loop_father, 0);
1933 gcc_assert (tgt_bb != NULL);
1935 else
1936 tgt_bb = split_edge (tgt_edge);
1939 if (latch->aux)
1941 basic_block *bblocks;
1942 unsigned nblocks, i;
1944 /* First handle the case latch edge is redirected. We are copying
1945 the loop header but not creating a multiple entry loop. Make the
1946 cfg manipulation code aware of that fact. */
1947 set_loop_copy (loop, loop);
1948 loop->latch = thread_single_edge (latch);
1949 set_loop_copy (loop, NULL);
1950 gcc_assert (single_succ (loop->latch) == tgt_bb);
1951 loop->header = tgt_bb;
1953 /* Remove the new pre-header blocks from our loop. */
1954 bblocks = XCNEWVEC (basic_block, loop->num_nodes);
1955 nblocks = dfs_enumerate_from (header, 0, def_split_header_continue_p,
1956 bblocks, loop->num_nodes, tgt_bb);
1957 for (i = 0; i < nblocks; i++)
1958 if (bblocks[i]->loop_father == loop)
1960 remove_bb_from_loops (bblocks[i]);
1961 add_bb_to_loop (bblocks[i], loop_outer (loop));
1963 free (bblocks);
1965 /* If the new header has multiple latches mark it so. */
1966 FOR_EACH_EDGE (e, ei, loop->header->preds)
1967 if (e->src->loop_father == loop
1968 && e->src != loop->latch)
1970 loop->latch = NULL;
1971 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
1974 /* Cancel remaining threading requests that would make the
1975 loop a multiple entry loop. */
1976 FOR_EACH_EDGE (e, ei, header->preds)
1978 edge e2;
1980 if (e->aux == NULL)
1981 continue;
1983 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1984 e2 = path->last ()->e;
1986 if (e->src->loop_father != e2->dest->loop_father
1987 && e2->dest != loop->header)
1989 delete_jump_thread_path (path);
1990 e->aux = NULL;
1994 /* Thread the remaining edges through the former header. */
1995 thread_block (header, false);
1997 else
1999 basic_block new_preheader;
2001 /* Now consider the case entry edges are redirected to the new entry
2002 block. Remember one entry edge, so that we can find the new
2003 preheader (its destination after threading). */
2004 FOR_EACH_EDGE (e, ei, header->preds)
2006 if (e->aux)
2007 break;
2010 /* The duplicate of the header is the new preheader of the loop. Ensure
2011 that it is placed correctly in the loop hierarchy. */
2012 set_loop_copy (loop, loop_outer (loop));
2014 thread_block (header, false);
2015 set_loop_copy (loop, NULL);
2016 new_preheader = e->dest;
2018 /* Create the new latch block. This is always necessary, as the latch
2019 must have only a single successor, but the original header had at
2020 least two successors. */
2021 loop->latch = NULL;
2022 mfb_kj_edge = single_succ_edge (new_preheader);
2023 loop->header = mfb_kj_edge->dest;
2024 latch = make_forwarder_block (tgt_bb, mfb_keep_just, NULL);
2025 loop->header = latch->dest;
2026 loop->latch = latch->src;
2029 return true;
2031 fail:
2032 /* We failed to thread anything. Cancel the requests. */
2033 FOR_EACH_EDGE (e, ei, header->preds)
2035 vec<jump_thread_edge *> *path = THREAD_PATH (e);
2037 if (path)
2039 delete_jump_thread_path (path);
2040 e->aux = NULL;
2043 return false;
2046 /* E1 and E2 are edges into the same basic block. Return TRUE if the
2047 PHI arguments associated with those edges are equal or there are no
2048 PHI arguments, otherwise return FALSE. */
2050 static bool
2051 phi_args_equal_on_edges (edge e1, edge e2)
2053 gimple_stmt_iterator gsi;
2054 int indx1 = e1->dest_idx;
2055 int indx2 = e2->dest_idx;
2057 for (gsi = gsi_start_phis (e1->dest); !gsi_end_p (gsi); gsi_next (&gsi))
2059 gimple phi = gsi_stmt (gsi);
2061 if (!operand_equal_p (gimple_phi_arg_def (phi, indx1),
2062 gimple_phi_arg_def (phi, indx2), 0))
2063 return false;
2065 return true;
2068 /* Walk through the registered jump threads and convert them into a
2069 form convenient for this pass.
2071 Any block which has incoming edges threaded to outgoing edges
2072 will have its entry in THREADED_BLOCK set.
2074 Any threaded edge will have its new outgoing edge stored in the
2075 original edge's AUX field.
2077 This form avoids the need to walk all the edges in the CFG to
2078 discover blocks which need processing and avoids unnecessary
2079 hash table lookups to map from threaded edge to new target. */
2081 static void
2082 mark_threaded_blocks (bitmap threaded_blocks)
2084 unsigned int i;
2085 bitmap_iterator bi;
2086 bitmap tmp = BITMAP_ALLOC (NULL);
2087 basic_block bb;
2088 edge e;
2089 edge_iterator ei;
2091 /* It is possible to have jump threads in which one is a subpath
2092 of the other. ie, (A, B), (B, C), (C, D) where B is a joiner
2093 block and (B, C), (C, D) where no joiner block exists.
2095 When this occurs ignore the jump thread request with the joiner
2096 block. It's totally subsumed by the simpler jump thread request.
2098 This results in less block copying, simpler CFGs. More importantly,
2099 when we duplicate the joiner block, B, in this case we will create
2100 a new threading opportunity that we wouldn't be able to optimize
2101 until the next jump threading iteration.
2103 So first convert the jump thread requests which do not require a
2104 joiner block. */
2105 for (i = 0; i < paths.length (); i++)
2107 vec<jump_thread_edge *> *path = paths[i];
2109 if ((*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK)
2111 edge e = (*path)[0]->e;
2112 e->aux = (void *)path;
2113 bitmap_set_bit (tmp, e->dest->index);
2117 /* Now iterate again, converting cases where we want to thread
2118 through a joiner block, but only if no other edge on the path
2119 already has a jump thread attached to it. We do this in two passes,
2120 to avoid situations where the order in the paths vec can hide overlapping
2121 threads (the path is recorded on the incoming edge, so we would miss
2122 cases where the second path starts at a downstream edge on the same
2123 path). First record all joiner paths, deleting any in the unexpected
2124 case where there is already a path for that incoming edge. */
2125 for (i = 0; i < paths.length (); i++)
2127 vec<jump_thread_edge *> *path = paths[i];
2129 if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
2131 /* Attach the path to the starting edge if none is yet recorded. */
2132 if ((*path)[0]->e->aux == NULL)
2133 (*path)[0]->e->aux = path;
2134 else if (dump_file && (dump_flags & TDF_DETAILS))
2135 dump_jump_thread_path (dump_file, *path, false);
2138 /* Second, look for paths that have any other jump thread attached to
2139 them, and either finish converting them or cancel them. */
2140 for (i = 0; i < paths.length (); i++)
2142 vec<jump_thread_edge *> *path = paths[i];
2143 edge e = (*path)[0]->e;
2145 if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && e->aux == path)
2147 unsigned int j;
2148 for (j = 1; j < path->length (); j++)
2149 if ((*path)[j]->e->aux != NULL)
2150 break;
2152 /* If we iterated through the entire path without exiting the loop,
2153 then we are good to go, record it. */
2154 if (j == path->length ())
2155 bitmap_set_bit (tmp, e->dest->index);
2156 else
2158 e->aux = NULL;
2159 if (dump_file && (dump_flags & TDF_DETAILS))
2160 dump_jump_thread_path (dump_file, *path, false);
2165 /* If optimizing for size, only thread through block if we don't have
2166 to duplicate it or it's an otherwise empty redirection block. */
2167 if (optimize_function_for_size_p (cfun))
2169 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2171 bb = BASIC_BLOCK_FOR_FN (cfun, i);
2172 if (EDGE_COUNT (bb->preds) > 1
2173 && !redirection_block_p (bb))
2175 FOR_EACH_EDGE (e, ei, bb->preds)
2177 if (e->aux)
2179 vec<jump_thread_edge *> *path = THREAD_PATH (e);
2180 delete_jump_thread_path (path);
2181 e->aux = NULL;
2185 else
2186 bitmap_set_bit (threaded_blocks, i);
2189 else
2190 bitmap_copy (threaded_blocks, tmp);
2192 /* Look for jump threading paths which cross multiple loop headers.
2194 The code to thread through loop headers will change the CFG in ways
2195 that break assumptions made by the loop optimization code.
2197 We don't want to blindly cancel the requests. We can instead do better
2198 by trimming off the end of the jump thread path. */
2199 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2201 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
2202 FOR_EACH_EDGE (e, ei, bb->preds)
2204 if (e->aux)
2206 vec<jump_thread_edge *> *path = THREAD_PATH (e);
2208 for (unsigned int i = 0, crossed_headers = 0;
2209 i < path->length ();
2210 i++)
2212 basic_block dest = (*path)[i]->e->dest;
2213 crossed_headers += (dest == dest->loop_father->header);
2214 if (crossed_headers > 1)
2216 /* Trim from entry I onwards. */
2217 for (unsigned int j = i; j < path->length (); j++)
2218 delete (*path)[j];
2219 path->truncate (i);
2221 /* Now that we've truncated the path, make sure
2222 what's left is still valid. We need at least
2223 two edges on the path and the last edge can not
2224 be a joiner. This should never happen, but let's
2225 be safe. */
2226 if (path->length () < 2
2227 || (path->last ()->type
2228 == EDGE_COPY_SRC_JOINER_BLOCK))
2230 delete_jump_thread_path (path);
2231 e->aux = NULL;
2233 break;
2240 /* If we have a joiner block (J) which has two successors S1 and S2 and
2241 we are threading though S1 and the final destination of the thread
2242 is S2, then we must verify that any PHI nodes in S2 have the same
2243 PHI arguments for the edge J->S2 and J->S1->...->S2.
2245 We used to detect this prior to registering the jump thread, but
2246 that prohibits propagation of edge equivalences into non-dominated
2247 PHI nodes as the equivalency test might occur before propagation.
2249 This must also occur after we truncate any jump threading paths
2250 as this scenario may only show up after truncation.
2252 This works for now, but will need improvement as part of the FSA
2253 optimization.
2255 Note since we've moved the thread request data to the edges,
2256 we have to iterate on those rather than the threaded_edges vector. */
2257 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2259 bb = BASIC_BLOCK_FOR_FN (cfun, i);
2260 FOR_EACH_EDGE (e, ei, bb->preds)
2262 if (e->aux)
2264 vec<jump_thread_edge *> *path = THREAD_PATH (e);
2265 bool have_joiner = ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK);
2267 if (have_joiner)
2269 basic_block joiner = e->dest;
2270 edge final_edge = path->last ()->e;
2271 basic_block final_dest = final_edge->dest;
2272 edge e2 = find_edge (joiner, final_dest);
2274 if (e2 && !phi_args_equal_on_edges (e2, final_edge))
2276 delete_jump_thread_path (path);
2277 e->aux = NULL;
2284 BITMAP_FREE (tmp);
2288 /* Return TRUE if BB ends with a switch statement or a computed goto.
2289 Otherwise return false. */
2290 static bool
2291 bb_ends_with_multiway_branch (basic_block bb ATTRIBUTE_UNUSED)
2293 gimple stmt = last_stmt (bb);
2294 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
2295 return true;
2296 if (stmt && gimple_code (stmt) == GIMPLE_GOTO
2297 && TREE_CODE (gimple_goto_dest (stmt)) == SSA_NAME)
2298 return true;
2299 return false;
2302 /* Walk through all blocks and thread incoming edges to the appropriate
2303 outgoing edge for each edge pair recorded in THREADED_EDGES.
2305 It is the caller's responsibility to fix the dominance information
2306 and rewrite duplicated SSA_NAMEs back into SSA form.
2308 If MAY_PEEL_LOOP_HEADERS is false, we avoid threading edges through
2309 loop headers if it does not simplify the loop.
2311 Returns true if one or more edges were threaded, false otherwise. */
2313 bool
2314 thread_through_all_blocks (bool may_peel_loop_headers)
2316 bool retval = false;
2317 unsigned int i;
2318 bitmap_iterator bi;
2319 bitmap threaded_blocks;
2320 struct loop *loop;
2322 if (!paths.exists ())
2323 return false;
2325 threaded_blocks = BITMAP_ALLOC (NULL);
2326 memset (&thread_stats, 0, sizeof (thread_stats));
2328 mark_threaded_blocks (threaded_blocks);
2330 initialize_original_copy_tables ();
2332 /* First perform the threading requests that do not affect
2333 loop structure. */
2334 EXECUTE_IF_SET_IN_BITMAP (threaded_blocks, 0, i, bi)
2336 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
2338 if (EDGE_COUNT (bb->preds) > 0)
2339 retval |= thread_block (bb, true);
2342 /* Then perform the threading through loop headers. We start with the
2343 innermost loop, so that the changes in cfg we perform won't affect
2344 further threading. */
2345 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
2347 if (!loop->header
2348 || !bitmap_bit_p (threaded_blocks, loop->header->index))
2349 continue;
2351 retval |= thread_through_loop_header (loop, may_peel_loop_headers);
2354 /* Any jump threading paths that are still attached to edges at this
2355 point must be one of two cases.
2357 First, we could have a jump threading path which went from outside
2358 a loop to inside a loop that was ignored because a prior jump thread
2359 across a backedge was realized (which indirectly causes the loop
2360 above to ignore the latter thread). We can detect these because the
2361 loop structures will be different and we do not currently try to
2362 optimize this case.
2364 Second, we could be threading across a backedge to a point within the
2365 same loop. This occurrs for the FSA/FSM optimization and we would
2366 like to optimize it. However, we have to be very careful as this
2367 may completely scramble the loop structures, with the result being
2368 irreducible loops causing us to throw away our loop structure.
2370 As a compromise for the latter case, if the thread path ends in
2371 a block where the last statement is a multiway branch, then go
2372 ahead and thread it, else ignore it. */
2373 basic_block bb;
2374 edge e;
2375 FOR_EACH_BB_FN (bb, cfun)
2377 /* If we do end up threading here, we can remove elements from
2378 BB->preds. Thus we can not use the FOR_EACH_EDGE iterator. */
2379 for (edge_iterator ei = ei_start (bb->preds);
2380 (e = ei_safe_edge (ei));)
2381 if (e->aux)
2383 vec<jump_thread_edge *> *path = THREAD_PATH (e);
2385 /* Case 1, threading from outside to inside the loop
2386 after we'd already threaded through the header. */
2387 if ((*path)[0]->e->dest->loop_father
2388 != path->last ()->e->src->loop_father)
2390 delete_jump_thread_path (path);
2391 e->aux = NULL;
2392 ei_next (&ei);
2394 else if (bb_ends_with_multiway_branch (path->last ()->e->src))
2396 /* The code to thread through loop headers may have
2397 split a block with jump threads attached to it.
2399 We can identify this with a disjoint jump threading
2400 path. If found, just remove it. */
2401 for (unsigned int i = 0; i < path->length () - 1; i++)
2402 if ((*path)[i]->e->dest != (*path)[i + 1]->e->src)
2404 delete_jump_thread_path (path);
2405 e->aux = NULL;
2406 ei_next (&ei);
2407 break;
2410 /* Our path is still valid, thread it. */
2411 if (e->aux)
2413 struct loop *loop = (*path)[0]->e->dest->loop_father;
2415 if (thread_block ((*path)[0]->e->dest, false))
2417 /* This jump thread likely totally scrambled this loop.
2418 So arrange for it to be fixed up. */
2419 loop->header = NULL;
2420 loop->latch = NULL;
2421 e->aux = NULL;
2423 else
2425 delete_jump_thread_path (path);
2426 e->aux = NULL;
2427 ei_next (&ei);
2431 else
2433 delete_jump_thread_path (path);
2434 e->aux = NULL;
2435 ei_next (&ei);
2438 else
2439 ei_next (&ei);
2442 statistics_counter_event (cfun, "Jumps threaded",
2443 thread_stats.num_threaded_edges);
2445 free_original_copy_tables ();
2447 BITMAP_FREE (threaded_blocks);
2448 threaded_blocks = NULL;
2449 paths.release ();
2451 if (retval)
2452 loops_state_set (LOOPS_NEED_FIXUP);
2454 return retval;
2457 /* Delete the jump threading path PATH. We have to explcitly delete
2458 each entry in the vector, then the container. */
2460 void
2461 delete_jump_thread_path (vec<jump_thread_edge *> *path)
2463 for (unsigned int i = 0; i < path->length (); i++)
2464 delete (*path)[i];
2465 path->release();
2468 /* Register a jump threading opportunity. We queue up all the jump
2469 threading opportunities discovered by a pass and update the CFG
2470 and SSA form all at once.
2472 E is the edge we can thread, E2 is the new target edge, i.e., we
2473 are effectively recording that E->dest can be changed to E2->dest
2474 after fixing the SSA graph. */
2476 void
2477 register_jump_thread (vec<jump_thread_edge *> *path)
2479 if (!dbg_cnt (registered_jump_thread))
2481 delete_jump_thread_path (path);
2482 return;
2485 /* First make sure there are no NULL outgoing edges on the jump threading
2486 path. That can happen for jumping to a constant address. */
2487 for (unsigned int i = 0; i < path->length (); i++)
2488 if ((*path)[i]->e == NULL)
2490 if (dump_file && (dump_flags & TDF_DETAILS))
2492 fprintf (dump_file,
2493 "Found NULL edge in jump threading path. Cancelling jump thread:\n");
2494 dump_jump_thread_path (dump_file, *path, false);
2497 delete_jump_thread_path (path);
2498 return;
2501 if (dump_file && (dump_flags & TDF_DETAILS))
2502 dump_jump_thread_path (dump_file, *path, true);
2504 if (!paths.exists ())
2505 paths.create (5);
2507 paths.safe_push (path);