1/* Thread edges through blocks and update the control flow and SSA graphs.
2 Copyright (C) 2004-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 "tree.h"
25#include "gimple.h"
26#include "cfghooks.h"
27#include "tree-pass.h"
28#include "ssa.h"
29#include "fold-const.h"
30#include "cfganal.h"
31#include "gimple-iterator.h"
32#include "tree-ssa.h"
33#include "tree-ssa-threadupdate.h"
34#include "cfgloop.h"
35#include "dbgcnt.h"
36#include "tree-cfg.h"
37#include "tree-vectorizer.h"
38
39/* Given a block B, update the CFG and SSA graph to reflect redirecting
40 one or more in-edges to B to instead reach the destination of an
41 out-edge from B while preserving any side effects in B.
42
43 i.e., given A->B and B->C, change A->B to be A->C yet still preserve the
44 side effects of executing B.
45
46 1. Make a copy of B (including its outgoing edges and statements). Call
47 the copy B'. Note B' has no incoming edges or PHIs at this time.
48
49 2. Remove the control statement at the end of B' and all outgoing edges
50 except B'->C.
51
52 3. Add a new argument to each PHI in C with the same value as the existing
53 argument associated with edge B->C. Associate the new PHI arguments
54 with the edge B'->C.
55
56 4. For each PHI in B, find or create a PHI in B' with an identical
57 PHI_RESULT. Add an argument to the PHI in B' which has the same
58 value as the PHI in B associated with the edge A->B. Associate
59 the new argument in the PHI in B' with the edge A->B.
60
61 5. Change the edge A->B to A->B'.
62
63 5a. This automatically deletes any PHI arguments associated with the
64 edge A->B in B.
65
66 5b. This automatically associates each new argument added in step 4
67 with the edge A->B'.
68
69 6. Repeat for other incoming edges into B.
70
71 7. Put the duplicated resources in B and all the B' blocks into SSA form.
72
73 Note that block duplication can be minimized by first collecting the
74 set of unique destination blocks that the incoming edges should
75 be threaded to.
76
77 We reduce the number of edges and statements we create by not copying all
78 the outgoing edges and the control statement in step #1. We instead create
79 a template block without the outgoing edges and duplicate the template.
80
81 Another case this code handles is threading through a "joiner" block. In
82 this case, we do not know the destination of the joiner block, but one
83 of the outgoing edges from the joiner block leads to a threadable path. This
84 case largely works as outlined above, except the duplicate of the joiner
85 block still contains a full set of outgoing edges and its control statement.
86 We just redirect one of its outgoing edges to our jump threading path. */
87
88
89/* Steps #5 and #6 of the above algorithm are best implemented by walking
90 all the incoming edges which thread to the same destination edge at
91 the same time. That avoids lots of table lookups to get information
92 for the destination edge.
93
94 To realize that implementation we create a list of incoming edges
95 which thread to the same outgoing edge. Thus to implement steps
96 #5 and #6 we traverse our hash table of outgoing edge information.
97 For each entry we walk the list of incoming edges which thread to
98 the current outgoing edge. */
99
100struct el
101{
102 edge e;
103 struct el *next;
104};
105
106/* Main data structure recording information regarding B's duplicate
107 blocks. */
108
109/* We need to efficiently record the unique thread destinations of this
110 block and specific information associated with those destinations. We
111 may have many incoming edges threaded to the same outgoing edge. This
112 can be naturally implemented with a hash table. */
113
114struct redirection_data : free_ptr_hash<redirection_data>
115{
116 /* We support wiring up two block duplicates in a jump threading path.
117
118 One is a normal block copy where we remove the control statement
119 and wire up its single remaining outgoing edge to the thread path.
120
121 The other is a joiner block where we leave the control statement
122 in place, but wire one of the outgoing edges to a thread path.
123
124 In theory we could have multiple block duplicates in a jump
125 threading path, but I haven't tried that.
126
127 The duplicate blocks appear in this array in the same order in
128 which they appear in the jump thread path. */
129 basic_block dup_blocks[2];
130
131 /* The jump threading path. */
132 vec<jump_thread_edge *> *path;
133
134 /* A list of incoming edges which we want to thread to the
135 same path. */
136 struct el *incoming_edges;
137
138 /* hash_table support. */
139 static inline hashval_t hash (const redirection_data *);
140 static inline int equal (const redirection_data *, const redirection_data *);
141};
142
143/* Dump a jump threading path, including annotations about each
144 edge in the path. */
145
146static void
147dump_jump_thread_path (FILE *dump_file, vec<jump_thread_edge *> path,
148 bool registering)
149{
150 fprintf (dump_file,
151 " %s%s jump thread: (%d, %d) incoming edge; ",
152 (registering ? "Registering" : "Cancelling"),
153 (path[0]->type == EDGE_FSM_THREAD ? " FSM": ""),
154 path[0]->e->src->index, path[0]->e->dest->index);
155
156 for (unsigned int i = 1; i < path.length (); i++)
157 {
158 /* We can get paths with a NULL edge when the final destination
159 of a jump thread turns out to be a constant address. We dump
160 those paths when debugging, so we have to be prepared for that
161 possibility here. */
162 if (path[i]->e == NULL)
163 continue;
164
165 if (path[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
166 fprintf (dump_file, " (%d, %d) joiner; ",
167 path[i]->e->src->index, path[i]->e->dest->index);
168 if (path[i]->type == EDGE_COPY_SRC_BLOCK)
169 fprintf (dump_file, " (%d, %d) normal;",
170 path[i]->e->src->index, path[i]->e->dest->index);
171 if (path[i]->type == EDGE_NO_COPY_SRC_BLOCK)
172 fprintf (dump_file, " (%d, %d) nocopy;",
173 path[i]->e->src->index, path[i]->e->dest->index);
174 if (path[0]->type == EDGE_FSM_THREAD)
175 fprintf (dump_file, " (%d, %d) ",
176 path[i]->e->src->index, path[i]->e->dest->index);
177 }
178 fputc ('\n', dump_file);
179}
180
181/* Simple hashing function. For any given incoming edge E, we're going
182 to be most concerned with the final destination of its jump thread
183 path. So hash on the block index of the final edge in the path. */
184
185inline hashval_t
186redirection_data::hash (const redirection_data *p)
187{
188 vec<jump_thread_edge *> *path = p->path;
189 return path->last ()->e->dest->index;
190}
191
192/* Given two hash table entries, return true if they have the same
193 jump threading path. */
194inline int
195redirection_data::equal (const redirection_data *p1, const redirection_data *p2)
196{
197 vec<jump_thread_edge *> *path1 = p1->path;
198 vec<jump_thread_edge *> *path2 = p2->path;
199
200 if (path1->length () != path2->length ())
201 return false;
202
203 for (unsigned int i = 1; i < path1->length (); i++)
204 {
205 if ((*path1)[i]->type != (*path2)[i]->type
206 || (*path1)[i]->e != (*path2)[i]->e)
207 return false;
208 }
209
210 return true;
211}
212
213/* Rather than search all the edges in jump thread paths each time
214 DOM is able to simply if control statement, we build a hash table
215 with the deleted edges. We only care about the address of the edge,
216 not its contents. */
217struct removed_edges : nofree_ptr_hash<edge_def>
218{
219 static hashval_t hash (edge e) { return htab_hash_pointer (e); }
220 static bool equal (edge e1, edge e2) { return e1 == e2; }
221};
222
223static hash_table<removed_edges> *removed_edges;
224
225/* Data structure of information to pass to hash table traversal routines. */
226struct ssa_local_info_t
227{
228 /* The current block we are working on. */
229 basic_block bb;
230
231 /* We only create a template block for the first duplicated block in a
232 jump threading path as we may need many duplicates of that block.
233
234 The second duplicate block in a path is specific to that path. Creating
235 and sharing a template for that block is considerably more difficult. */
236 basic_block template_block;
237
238 /* Blocks duplicated for the thread. */
239 bitmap duplicate_blocks;
240
241 /* TRUE if we thread one or more jumps, FALSE otherwise. */
242 bool jumps_threaded;
243
244 /* When we have multiple paths through a joiner which reach different
245 final destinations, then we may need to correct for potential
246 profile insanities. */
247 bool need_profile_correction;
248};
249
250/* Passes which use the jump threading code register jump threading
251 opportunities as they are discovered. We keep the registered
252 jump threading opportunities in this vector as edge pairs
253 (original_edge, target_edge). */
254static vec<vec<jump_thread_edge *> *> paths;
255
256/* When we start updating the CFG for threading, data necessary for jump
257 threading is attached to the AUX field for the incoming edge. Use these
258 macros to access the underlying structure attached to the AUX field. */
259#define THREAD_PATH(E) ((vec<jump_thread_edge *> *)(E)->aux)
260
261/* Jump threading statistics. */
262
263struct thread_stats_d
264{
265 unsigned long num_threaded_edges;
266};
267
268struct thread_stats_d thread_stats;
269
270
271/* Remove the last statement in block BB if it is a control statement
272 Also remove all outgoing edges except the edge which reaches DEST_BB.
273 If DEST_BB is NULL, then remove all outgoing edges. */
274
275void
276remove_ctrl_stmt_and_useless_edges (basic_block bb, basic_block dest_bb)
277{
278 gimple_stmt_iterator gsi;
279 edge e;
280 edge_iterator ei;
281
282 gsi = gsi_last_bb (bb);
283
284 /* If the duplicate ends with a control statement, then remove it.
285
286 Note that if we are duplicating the template block rather than the
287 original basic block, then the duplicate might not have any real
288 statements in it. */
289 if (!gsi_end_p (gsi)
290 && gsi_stmt (gsi)
291 && (gimple_code (gsi_stmt (gsi)) == GIMPLE_COND
292 || gimple_code (gsi_stmt (gsi)) == GIMPLE_GOTO
293 || gimple_code (gsi_stmt (gsi)) == GIMPLE_SWITCH))
294 gsi_remove (&gsi, true);
295
296 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
297 {
298 if (e->dest != dest_bb)
299 {
300 free_dom_edge_info (e);
301 remove_edge (e);
302 }
303 else
304 {
305 e->probability = profile_probability::always ();
306 ei_next (&ei);
307 }
308 }
309
310 /* If the remaining edge is a loop exit, there must have
311 a removed edge that was not a loop exit.
312
313 In that case BB and possibly other blocks were previously
314 in the loop, but are now outside the loop. Thus, we need
315 to update the loop structures. */
316 if (single_succ_p (bb)
317 && loop_outer (bb->loop_father)
318 && loop_exit_edge_p (bb->loop_father, single_succ_edge (bb)))
319 loops_state_set (LOOPS_NEED_FIXUP);
320}
321
322/* Create a duplicate of BB. Record the duplicate block in an array
323 indexed by COUNT stored in RD. */
324
325static void
326create_block_for_threading (basic_block bb,
327 struct redirection_data *rd,
328 unsigned int count,
329 bitmap *duplicate_blocks)
330{
331 edge_iterator ei;
332 edge e;
333
334 /* We can use the generic block duplication code and simply remove
335 the stuff we do not need. */
336 rd->dup_blocks[count] = duplicate_block (bb, NULL, NULL);
337
338 FOR_EACH_EDGE (e, ei, rd->dup_blocks[count]->succs)
339 e->aux = NULL;
340
341 /* Zero out the profile, since the block is unreachable for now. */
342 rd->dup_blocks[count]->count = profile_count::uninitialized ();
343 if (duplicate_blocks)
344 bitmap_set_bit (*duplicate_blocks, rd->dup_blocks[count]->index);
345}
346
347/* Main data structure to hold information for duplicates of BB. */
348
349static hash_table<redirection_data> *redirection_data;
350
351/* Given an outgoing edge E lookup and return its entry in our hash table.
352
353 If INSERT is true, then we insert the entry into the hash table if
354 it is not already present. INCOMING_EDGE is added to the list of incoming
355 edges associated with E in the hash table. */
356
357static struct redirection_data *
358lookup_redirection_data (edge e, enum insert_option insert)
359{
360 struct redirection_data **slot;
361 struct redirection_data *elt;
362 vec<jump_thread_edge *> *path = THREAD_PATH (e);
363
364 /* Build a hash table element so we can see if E is already
365 in the table. */
366 elt = XNEW (struct redirection_data);
367 elt->path = path;
368 elt->dup_blocks[0] = NULL;
369 elt->dup_blocks[1] = NULL;
370 elt->incoming_edges = NULL;
371
372 slot = redirection_data->find_slot (elt, insert);
373
374 /* This will only happen if INSERT is false and the entry is not
375 in the hash table. */
376 if (slot == NULL)
377 {
378 free (elt);
379 return NULL;
380 }
381
382 /* This will only happen if E was not in the hash table and
383 INSERT is true. */
384 if (*slot == NULL)
385 {
386 *slot = elt;
387 elt->incoming_edges = XNEW (struct el);
388 elt->incoming_edges->e = e;
389 elt->incoming_edges->next = NULL;
390 return elt;
391 }
392 /* E was in the hash table. */
393 else
394 {
395 /* Free ELT as we do not need it anymore, we will extract the
396 relevant entry from the hash table itself. */
397 free (elt);
398
399 /* Get the entry stored in the hash table. */
400 elt = *slot;
401
402 /* If insertion was requested, then we need to add INCOMING_EDGE
403 to the list of incoming edges associated with E. */
404 if (insert)
405 {
406 struct el *el = XNEW (struct el);
407 el->next = elt->incoming_edges;
408 el->e = e;
409 elt->incoming_edges = el;
410 }
411
412 return elt;
413 }
414}
415
416/* Similar to copy_phi_args, except that the PHI arg exists, it just
417 does not have a value associated with it. */
418
419static void
420copy_phi_arg_into_existing_phi (edge src_e, edge tgt_e)
421{
422 int src_idx = src_e->dest_idx;
423 int tgt_idx = tgt_e->dest_idx;
424
425 /* Iterate over each PHI in e->dest. */
426 for (gphi_iterator gsi = gsi_start_phis (src_e->dest),
427 gsi2 = gsi_start_phis (tgt_e->dest);
428 !gsi_end_p (gsi);
429 gsi_next (&gsi), gsi_next (&gsi2))
430 {
431 gphi *src_phi = gsi.phi ();
432 gphi *dest_phi = gsi2.phi ();
433 tree val = gimple_phi_arg_def (src_phi, src_idx);
434 source_location locus = gimple_phi_arg_location (src_phi, src_idx);
435
436 SET_PHI_ARG_DEF (dest_phi, tgt_idx, val);
437 gimple_phi_arg_set_location (dest_phi, tgt_idx, locus);
438 }
439}
440
441/* Given ssa_name DEF, backtrack jump threading PATH from node IDX
442 to see if it has constant value in a flow sensitive manner. Set
443 LOCUS to location of the constant phi arg and return the value.
444 Return DEF directly if either PATH or idx is ZERO. */
445
446static tree
447get_value_locus_in_path (tree def, vec<jump_thread_edge *> *path,
448 basic_block bb, int idx, source_location *locus)
449{
450 tree arg;
451 gphi *def_phi;
452 basic_block def_bb;
453
454 if (path == NULL || idx == 0)
455 return def;
456
457 def_phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (def));
458 if (!def_phi)
459 return def;
460
461 def_bb = gimple_bb (def_phi);
462 /* Don't propagate loop invariants into deeper loops. */
463 if (!def_bb || bb_loop_depth (def_bb) < bb_loop_depth (bb))
464 return def;
465
466 /* Backtrack jump threading path from IDX to see if def has constant
467 value. */
468 for (int j = idx - 1; j >= 0; j--)
469 {
470 edge e = (*path)[j]->e;
471 if (e->dest == def_bb)
472 {
473 arg = gimple_phi_arg_def (def_phi, e->dest_idx);
474 if (is_gimple_min_invariant (arg))
475 {
476 *locus = gimple_phi_arg_location (def_phi, e->dest_idx);
477 return arg;
478 }
479 break;
480 }
481 }
482
483 return def;
484}
485
486/* For each PHI in BB, copy the argument associated with SRC_E to TGT_E.
487 Try to backtrack jump threading PATH from node IDX to see if the arg
488 has constant value, copy constant value instead of argument itself
489 if yes. */
490
491static void
492copy_phi_args (basic_block bb, edge src_e, edge tgt_e,
493 vec<jump_thread_edge *> *path, int idx)
494{
495 gphi_iterator gsi;
496 int src_indx = src_e->dest_idx;
497
498 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
499 {
500 gphi *phi = gsi.phi ();
501 tree def = gimple_phi_arg_def (phi, src_indx);
502 source_location locus = gimple_phi_arg_location (phi, src_indx);
503
504 if (TREE_CODE (def) == SSA_NAME
505 && !virtual_operand_p (gimple_phi_result (phi)))
506 def = get_value_locus_in_path (def, path, bb, idx, &locus);
507
508 add_phi_arg (phi, def, tgt_e, locus);
509 }
510}
511
512/* We have recently made a copy of ORIG_BB, including its outgoing
513 edges. The copy is NEW_BB. Every PHI node in every direct successor of
514 ORIG_BB has a new argument associated with edge from NEW_BB to the
515 successor. Initialize the PHI argument so that it is equal to the PHI
516 argument associated with the edge from ORIG_BB to the successor.
517 PATH and IDX are used to check if the new PHI argument has constant
518 value in a flow sensitive manner. */
519
520static void
521update_destination_phis (basic_block orig_bb, basic_block new_bb,
522 vec<jump_thread_edge *> *path, int idx)
523{
524 edge_iterator ei;
525 edge e;
526
527 FOR_EACH_EDGE (e, ei, orig_bb->succs)
528 {
529 edge e2 = find_edge (new_bb, e->dest);
530 copy_phi_args (e->dest, e, e2, path, idx);
531 }
532}
533
534/* Given a duplicate block and its single destination (both stored
535 in RD). Create an edge between the duplicate and its single
536 destination.
537
538 Add an additional argument to any PHI nodes at the single
539 destination. IDX is the start node in jump threading path
540 we start to check to see if the new PHI argument has constant
541 value along the jump threading path. */
542
543static void
544create_edge_and_update_destination_phis (struct redirection_data *rd,
545 basic_block bb, int idx)
546{
547 edge e = make_single_succ_edge (bb, rd->path->last ()->e->dest, EDGE_FALLTHRU);
548
549 rescan_loop_exit (e, true, false);
550
551 /* We used to copy the thread path here. That was added in 2007
552 and dutifully updated through the representation changes in 2013.
553
554 In 2013 we added code to thread from an interior node through
555 the backedge to another interior node. That runs after the code
556 to thread through loop headers from outside the loop.
557
558 The latter may delete edges in the CFG, including those
559 which appeared in the jump threading path we copied here. Thus
560 we'd end up using a dangling pointer.
561
562 After reviewing the 2007/2011 code, I can't see how anything
563 depended on copying the AUX field and clearly copying the jump
564 threading path is problematical due to embedded edge pointers.
565 It has been removed. */
566 e->aux = NULL;
567
568 /* If there are any PHI nodes at the destination of the outgoing edge
569 from the duplicate block, then we will need to add a new argument
570 to them. The argument should have the same value as the argument
571 associated with the outgoing edge stored in RD. */
572 copy_phi_args (e->dest, rd->path->last ()->e, e, rd->path, idx);
573}
574
575/* Look through PATH beginning at START and return TRUE if there are
576 any additional blocks that need to be duplicated. Otherwise,
577 return FALSE. */
578static bool
579any_remaining_duplicated_blocks (vec<jump_thread_edge *> *path,
580 unsigned int start)
581{
582 for (unsigned int i = start + 1; i < path->length (); i++)
583 {
584 if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK
585 || (*path)[i]->type == EDGE_COPY_SRC_BLOCK)
586 return true;
587 }
588 return false;
589}
590
591
592/* Compute the amount of profile count coming into the jump threading
593 path stored in RD that we are duplicating, returned in PATH_IN_COUNT_PTR and
594 PATH_IN_FREQ_PTR, as well as the amount of counts flowing out of the
595 duplicated path, returned in PATH_OUT_COUNT_PTR. LOCAL_INFO is used to
596 identify blocks duplicated for jump threading, which have duplicated
597 edges that need to be ignored in the analysis. Return true if path contains
598 a joiner, false otherwise.
599
600 In the non-joiner case, this is straightforward - all the counts
601 flowing into the jump threading path should flow through the duplicated
602 block and out of the duplicated path.
603
604 In the joiner case, it is very tricky. Some of the counts flowing into
605 the original path go offpath at the joiner. The problem is that while
606 we know how much total count goes off-path in the original control flow,
607 we don't know how many of the counts corresponding to just the jump
608 threading path go offpath at the joiner.
609
610 For example, assume we have the following control flow and identified
611 jump threading paths:
612
613 A B C
614 \ | /
615 Ea \ |Eb / Ec
616 \ | /
617 v v v
618 J <-- Joiner
619 / \
620 Eoff/ \Eon
621 / \
622 v v
623 Soff Son <--- Normal
624 /\
625 Ed/ \ Ee
626 / \
627 v v
628 D E
629
630 Jump threading paths: A -> J -> Son -> D (path 1)
631 C -> J -> Son -> E (path 2)
632
633 Note that the control flow could be more complicated:
634 - Each jump threading path may have more than one incoming edge. I.e. A and
635 Ea could represent multiple incoming blocks/edges that are included in
636 path 1.
637 - There could be EDGE_NO_COPY_SRC_BLOCK edges after the joiner (either
638 before or after the "normal" copy block). These are not duplicated onto
639 the jump threading path, as they are single-successor.
640 - Any of the blocks along the path may have other incoming edges that
641 are not part of any jump threading path, but add profile counts along
642 the path.
643
644 In the above example, after all jump threading is complete, we will
645 end up with the following control flow:
646
647 A B C
648 | | |
649 Ea| |Eb |Ec
650 | | |
651 v v v
652 Ja J Jc
653 / \ / \Eon' / \
654 Eona/ \ ---/---\-------- \Eonc
655 / \ / / \ \
656 v v v v v
657 Sona Soff Son Sonc
658 \ /\ /
659 \___________ / \ _____/
660 \ / \/
661 vv v
662 D E
663
664 The main issue to notice here is that when we are processing path 1
665 (A->J->Son->D) we need to figure out the outgoing edge weights to
666 the duplicated edges Ja->Sona and Ja->Soff, while ensuring that the
667 sum of the incoming weights to D remain Ed. The problem with simply
668 assuming that Ja (and Jc when processing path 2) has the same outgoing
669 probabilities to its successors as the original block J, is that after
670 all paths are processed and other edges/counts removed (e.g. none
671 of Ec will reach D after processing path 2), we may end up with not
672 enough count flowing along duplicated edge Sona->D.
673
674 Therefore, in the case of a joiner, we keep track of all counts
675 coming in along the current path, as well as from predecessors not
676 on any jump threading path (Eb in the above example). While we
677 first assume that the duplicated Eona for Ja->Sona has the same
678 probability as the original, we later compensate for other jump
679 threading paths that may eliminate edges. We do that by keep track
680 of all counts coming into the original path that are not in a jump
681 thread (Eb in the above example, but as noted earlier, there could
682 be other predecessors incoming to the path at various points, such
683 as at Son). Call this cumulative non-path count coming into the path
684 before D as Enonpath. We then ensure that the count from Sona->D is as at
685 least as big as (Ed - Enonpath), but no bigger than the minimum
686 weight along the jump threading path. The probabilities of both the
687 original and duplicated joiner block J and Ja will be adjusted
688 accordingly after the updates. */
689
690static bool
691compute_path_counts (struct redirection_data *rd,
692 ssa_local_info_t *local_info,
693 profile_count *path_in_count_ptr,
694 profile_count *path_out_count_ptr)
695{
696 edge e = rd->incoming_edges->e;
697 vec<jump_thread_edge *> *path = THREAD_PATH (e);
698 edge elast = path->last ()->e;
699 profile_count nonpath_count = profile_count::zero ();
700 bool has_joiner = false;
701 profile_count path_in_count = profile_count::zero ();
702
703 /* Start by accumulating incoming edge counts to the path's first bb
704 into a couple buckets:
705 path_in_count: total count of incoming edges that flow into the
706 current path.
707 nonpath_count: total count of incoming edges that are not
708 flowing along *any* path. These are the counts
709 that will still flow along the original path after
710 all path duplication is done by potentially multiple
711 calls to this routine.
712 (any other incoming edge counts are for a different jump threading
713 path that will be handled by a later call to this routine.)
714 To make this easier, start by recording all incoming edges that flow into
715 the current path in a bitmap. We could add up the path's incoming edge
716 counts here, but we still need to walk all the first bb's incoming edges
717 below to add up the counts of the other edges not included in this jump
718 threading path. */
719 struct el *next, *el;
720 auto_bitmap in_edge_srcs;
721 for (el = rd->incoming_edges; el; el = next)
722 {
723 next = el->next;
724 bitmap_set_bit (in_edge_srcs, el->e->src->index);
725 }
726 edge ein;
727 edge_iterator ei;
728 FOR_EACH_EDGE (ein, ei, e->dest->preds)
729 {
730 vec<jump_thread_edge *> *ein_path = THREAD_PATH (ein);
731 /* Simply check the incoming edge src against the set captured above. */
732 if (ein_path
733 && bitmap_bit_p (in_edge_srcs, (*ein_path)[0]->e->src->index))
734 {
735 /* It is necessary but not sufficient that the last path edges
736 are identical. There may be different paths that share the
737 same last path edge in the case where the last edge has a nocopy
738 source block. */
739 gcc_assert (ein_path->last ()->e == elast);
740 path_in_count += ein->count ();
741 }
742 else if (!ein_path)
743 {
744 /* Keep track of the incoming edges that are not on any jump-threading
745 path. These counts will still flow out of original path after all
746 jump threading is complete. */
747 nonpath_count += ein->count ();
748 }
749 }
750
751 /* Now compute the fraction of the total count coming into the first
752 path bb that is from the current threading path. */
753 profile_count total_count = e->dest->count;
754 /* Handle incoming profile insanities. */
755 if (total_count < path_in_count)
756 path_in_count = total_count;
757 profile_probability onpath_scale = path_in_count.probability_in (total_count);
758
759 /* Walk the entire path to do some more computation in order to estimate
760 how much of the path_in_count will flow out of the duplicated threading
761 path. In the non-joiner case this is straightforward (it should be
762 the same as path_in_count, although we will handle incoming profile
763 insanities by setting it equal to the minimum count along the path).
764
765 In the joiner case, we need to estimate how much of the path_in_count
766 will stay on the threading path after the joiner's conditional branch.
767 We don't really know for sure how much of the counts
768 associated with this path go to each successor of the joiner, but we'll
769 estimate based on the fraction of the total count coming into the path
770 bb was from the threading paths (computed above in onpath_scale).
771 Afterwards, we will need to do some fixup to account for other threading
772 paths and possible profile insanities.
773
774 In order to estimate the joiner case's counts we also need to update
775 nonpath_count with any additional counts coming into the path. Other
776 blocks along the path may have additional predecessors from outside
777 the path. */
778 profile_count path_out_count = path_in_count;
779 profile_count min_path_count = path_in_count;
780 for (unsigned int i = 1; i < path->length (); i++)
781 {
782 edge epath = (*path)[i]->e;
783 profile_count cur_count = epath->count ();
784 if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
785 {
786 has_joiner = true;
787 cur_count = cur_count.apply_probability (onpath_scale);
788 }
789 /* In the joiner case we need to update nonpath_count for any edges
790 coming into the path that will contribute to the count flowing
791 into the path successor. */
792 if (has_joiner && epath != elast)
793 {
794 /* Look for other incoming edges after joiner. */
795 FOR_EACH_EDGE (ein, ei, epath->dest->preds)
796 {
797 if (ein != epath
798 /* Ignore in edges from blocks we have duplicated for a
799 threading path, which have duplicated edge counts until
800 they are redirected by an invocation of this routine. */
801 && !bitmap_bit_p (local_info->duplicate_blocks,
802 ein->src->index))
803 nonpath_count += ein->count ();
804 }
805 }
806 if (cur_count < path_out_count)
807 path_out_count = cur_count;
808 if (epath->count () < min_path_count)
809 min_path_count = epath->count ();
810 }
811
812 /* We computed path_out_count above assuming that this path targeted
813 the joiner's on-path successor with the same likelihood as it
814 reached the joiner. However, other thread paths through the joiner
815 may take a different path through the normal copy source block
816 (i.e. they have a different elast), meaning that they do not
817 contribute any counts to this path's elast. As a result, it may
818 turn out that this path must have more count flowing to the on-path
819 successor of the joiner. Essentially, all of this path's elast
820 count must be contributed by this path and any nonpath counts
821 (since any path through the joiner with a different elast will not
822 include a copy of this elast in its duplicated path).
823 So ensure that this path's path_out_count is at least the
824 difference between elast->count () and nonpath_count. Otherwise the edge
825 counts after threading will not be sane. */
826 if (local_info->need_profile_correction
827 && has_joiner && path_out_count < elast->count () - nonpath_count)
828 {
829 path_out_count = elast->count () - nonpath_count;
830 /* But neither can we go above the minimum count along the path
831 we are duplicating. This can be an issue due to profile
832 insanities coming in to this pass. */
833 if (path_out_count > min_path_count)
834 path_out_count = min_path_count;
835 }
836
837 *path_in_count_ptr = path_in_count;
838 *path_out_count_ptr = path_out_count;
839 return has_joiner;
840}
841
842
843/* Update the counts and frequencies for both an original path
844 edge EPATH and its duplicate EDUP. The duplicate source block
845 will get a count of PATH_IN_COUNT and PATH_IN_FREQ,
846 and the duplicate edge EDUP will have a count of PATH_OUT_COUNT. */
847static void
848update_profile (edge epath, edge edup, profile_count path_in_count,
849 profile_count path_out_count)
850{
851
852 /* First update the duplicated block's count. */
853 if (edup)
854 {
855 basic_block dup_block = edup->src;
856
857 /* Edup's count is reduced by path_out_count. We need to redistribute
858 probabilities to the remaining edges. */
859
860 edge esucc;
861 edge_iterator ei;
862 profile_probability edup_prob
863 = path_out_count.probability_in (path_in_count);
864
865 /* Either scale up or down the remaining edges.
866 probabilities are always in range <0,1> and thus we can't do
867 both by same loop. */
868 if (edup->probability > edup_prob)
869 {
870 profile_probability rev_scale
871 = (profile_probability::always () - edup->probability)
872 / (profile_probability::always () - edup_prob);
873 FOR_EACH_EDGE (esucc, ei, dup_block->succs)
874 if (esucc != edup)
875 esucc->probability /= rev_scale;
876 }
877 else if (edup->probability < edup_prob)
878 {
879 profile_probability scale
880 = (profile_probability::always () - edup_prob)
881 / (profile_probability::always () - edup->probability);
882 FOR_EACH_EDGE (esucc, ei, dup_block->succs)
883 if (esucc != edup)
884 esucc->probability *= scale;
885 }
886 if (edup_prob.initialized_p ())
887 edup->probability = edup_prob;
888
889 gcc_assert (!dup_block->count.initialized_p ());
890 dup_block->count = path_in_count;
891 }
892
893 if (path_in_count == profile_count::zero ())
894 return;
895
896 profile_count final_count = epath->count () - path_out_count;
897
898 /* Now update the original block's count in the
899 opposite manner - remove the counts/freq that will flow
900 into the duplicated block. Handle underflow due to precision/
901 rounding issues. */
902 epath->src->count -= path_in_count;
903
904 /* Next update this path edge's original and duplicated counts. We know
905 that the duplicated path will have path_out_count flowing
906 out of it (in the joiner case this is the count along the duplicated path
907 out of the duplicated joiner). This count can then be removed from the
908 original path edge. */
909
910 edge esucc;
911 edge_iterator ei;
912 profile_probability epath_prob = final_count.probability_in (epath->src->count);
913
914 if (epath->probability > epath_prob)
915 {
916 profile_probability rev_scale
917 = (profile_probability::always () - epath->probability)
918 / (profile_probability::always () - epath_prob);
919 FOR_EACH_EDGE (esucc, ei, epath->src->succs)
920 if (esucc != epath)
921 esucc->probability /= rev_scale;
922 }
923 else if (epath->probability < epath_prob)
924 {
925 profile_probability scale
926 = (profile_probability::always () - epath_prob)
927 / (profile_probability::always () - epath->probability);
928 FOR_EACH_EDGE (esucc, ei, epath->src->succs)
929 if (esucc != epath)
930 esucc->probability *= scale;
931 }
932 if (epath_prob.initialized_p ())
933 epath->probability = epath_prob;
934}
935
936/* Wire up the outgoing edges from the duplicate blocks and
937 update any PHIs as needed. Also update the profile counts
938 on the original and duplicate blocks and edges. */
939void
940ssa_fix_duplicate_block_edges (struct redirection_data *rd,
941 ssa_local_info_t *local_info)
942{
943 bool multi_incomings = (rd->incoming_edges->next != NULL);
944 edge e = rd->incoming_edges->e;
945 vec<jump_thread_edge *> *path = THREAD_PATH (e);
946 edge elast = path->last ()->e;
947 profile_count path_in_count = profile_count::zero ();
948 profile_count path_out_count = profile_count::zero ();
949
950 /* First determine how much profile count to move from original
951 path to the duplicate path. This is tricky in the presence of
952 a joiner (see comments for compute_path_counts), where some portion
953 of the path's counts will flow off-path from the joiner. In the
954 non-joiner case the path_in_count and path_out_count should be the
955 same. */
956 bool has_joiner = compute_path_counts (rd, local_info,
957 &path_in_count, &path_out_count);
958
959 for (unsigned int count = 0, i = 1; i < path->length (); i++)
960 {
961 edge epath = (*path)[i]->e;
962
963 /* If we were threading through an joiner block, then we want
964 to keep its control statement and redirect an outgoing edge.
965 Else we want to remove the control statement & edges, then create
966 a new outgoing edge. In both cases we may need to update PHIs. */
967 if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
968 {
969 edge victim;
970 edge e2;
971
972 gcc_assert (has_joiner);
973
974 /* This updates the PHIs at the destination of the duplicate
975 block. Pass 0 instead of i if we are threading a path which
976 has multiple incoming edges. */
977 update_destination_phis (local_info->bb, rd->dup_blocks[count],
978 path, multi_incomings ? 0 : i);
979
980 /* Find the edge from the duplicate block to the block we're
981 threading through. That's the edge we want to redirect. */
982 victim = find_edge (rd->dup_blocks[count], (*path)[i]->e->dest);
983
984 /* If there are no remaining blocks on the path to duplicate,
985 then redirect VICTIM to the final destination of the jump
986 threading path. */
987 if (!any_remaining_duplicated_blocks (path, i))
988 {
989 e2 = redirect_edge_and_branch (victim, elast->dest);
990 /* If we redirected the edge, then we need to copy PHI arguments
991 at the target. If the edge already existed (e2 != victim
992 case), then the PHIs in the target already have the correct
993 arguments. */
994 if (e2 == victim)
995 copy_phi_args (e2->dest, elast, e2,
996 path, multi_incomings ? 0 : i);
997 }
998 else
999 {
1000 /* Redirect VICTIM to the next duplicated block in the path. */
1001 e2 = redirect_edge_and_branch (victim, rd->dup_blocks[count + 1]);
1002
1003 /* We need to update the PHIs in the next duplicated block. We
1004 want the new PHI args to have the same value as they had
1005 in the source of the next duplicate block.
1006
1007 Thus, we need to know which edge we traversed into the
1008 source of the duplicate. Furthermore, we may have
1009 traversed many edges to reach the source of the duplicate.
1010
1011 Walk through the path starting at element I until we
1012 hit an edge marked with EDGE_COPY_SRC_BLOCK. We want
1013 the edge from the prior element. */
1014 for (unsigned int j = i + 1; j < path->length (); j++)
1015 {
1016 if ((*path)[j]->type == EDGE_COPY_SRC_BLOCK)
1017 {
1018 copy_phi_arg_into_existing_phi ((*path)[j - 1]->e, e2);
1019 break;
1020 }
1021 }
1022 }
1023
1024 /* Update the counts of both the original block
1025 and path edge, and the duplicates. The path duplicate's
1026 incoming count are the totals for all edges
1027 incoming to this jump threading path computed earlier.
1028 And we know that the duplicated path will have path_out_count
1029 flowing out of it (i.e. along the duplicated path out of the
1030 duplicated joiner). */
1031 update_profile (epath, e2, path_in_count, path_out_count);
1032 }
1033 else if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK)
1034 {
1035 remove_ctrl_stmt_and_useless_edges (rd->dup_blocks[count], NULL);
1036 create_edge_and_update_destination_phis (rd, rd->dup_blocks[count],
1037 multi_incomings ? 0 : i);
1038 if (count == 1)
1039 single_succ_edge (rd->dup_blocks[1])->aux = NULL;
1040
1041 /* Update the counts of both the original block
1042 and path edge, and the duplicates. Since we are now after
1043 any joiner that may have existed on the path, the count
1044 flowing along the duplicated threaded path is path_out_count.
1045 If we didn't have a joiner, then cur_path_freq was the sum
1046 of the total frequencies along all incoming edges to the
1047 thread path (path_in_freq). If we had a joiner, it would have
1048 been updated at the end of that handling to the edge frequency
1049 along the duplicated joiner path edge. */
1050 update_profile (epath, EDGE_SUCC (rd->dup_blocks[count], 0),
1051 path_out_count, path_out_count);
1052 }
1053 else
1054 {
1055 /* No copy case. In this case we don't have an equivalent block
1056 on the duplicated thread path to update, but we do need
1057 to remove the portion of the counts/freqs that were moved
1058 to the duplicated path from the counts/freqs flowing through
1059 this block on the original path. Since all the no-copy edges
1060 are after any joiner, the removed count is the same as
1061 path_out_count.
1062
1063 If we didn't have a joiner, then cur_path_freq was the sum
1064 of the total frequencies along all incoming edges to the
1065 thread path (path_in_freq). If we had a joiner, it would have
1066 been updated at the end of that handling to the edge frequency
1067 along the duplicated joiner path edge. */
1068 update_profile (epath, NULL, path_out_count, path_out_count);
1069 }
1070
1071 /* Increment the index into the duplicated path when we processed
1072 a duplicated block. */
1073 if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK
1074 || (*path)[i]->type == EDGE_COPY_SRC_BLOCK)
1075 {
1076 count++;
1077 }
1078 }
1079}
1080
1081/* Hash table traversal callback routine to create duplicate blocks. */
1082
1083int
1084ssa_create_duplicates (struct redirection_data **slot,
1085 ssa_local_info_t *local_info)
1086{
1087 struct redirection_data *rd = *slot;
1088
1089 /* The second duplicated block in a jump threading path is specific
1090 to the path. So it gets stored in RD rather than in LOCAL_DATA.
1091
1092 Each time we're called, we have to look through the path and see
1093 if a second block needs to be duplicated.
1094
1095 Note the search starts with the third edge on the path. The first
1096 edge is the incoming edge, the second edge always has its source
1097 duplicated. Thus we start our search with the third edge. */
1098 vec<jump_thread_edge *> *path = rd->path;
1099 for (unsigned int i = 2; i < path->length (); i++)
1100 {
1101 if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK
1102 || (*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
1103 {
1104 create_block_for_threading ((*path)[i]->e->src, rd, 1,
1105 &local_info->duplicate_blocks);
1106 break;
1107 }
1108 }
1109
1110 /* Create a template block if we have not done so already. Otherwise
1111 use the template to create a new block. */
1112 if (local_info->template_block == NULL)
1113 {
1114 create_block_for_threading ((*path)[1]->e->src, rd, 0,
1115 &local_info->duplicate_blocks);
1116 local_info->template_block = rd->dup_blocks[0];
1117
1118 /* We do not create any outgoing edges for the template. We will
1119 take care of that in a later traversal. That way we do not
1120 create edges that are going to just be deleted. */
1121 }
1122 else
1123 {
1124 create_block_for_threading (local_info->template_block, rd, 0,
1125 &local_info->duplicate_blocks);
1126
1127 /* Go ahead and wire up outgoing edges and update PHIs for the duplicate
1128 block. */
1129 ssa_fix_duplicate_block_edges (rd, local_info);
1130 }
1131
1132 /* Keep walking the hash table. */
1133 return 1;
1134}
1135
1136/* We did not create any outgoing edges for the template block during
1137 block creation. This hash table traversal callback creates the
1138 outgoing edge for the template block. */
1139
1140inline int
1141ssa_fixup_template_block (struct redirection_data **slot,
1142 ssa_local_info_t *local_info)
1143{
1144 struct redirection_data *rd = *slot;
1145
1146 /* If this is the template block halt the traversal after updating
1147 it appropriately.
1148
1149 If we were threading through an joiner block, then we want
1150 to keep its control statement and redirect an outgoing edge.
1151 Else we want to remove the control statement & edges, then create
1152 a new outgoing edge. In both cases we may need to update PHIs. */
1153 if (rd->dup_blocks[0] && rd->dup_blocks[0] == local_info->template_block)
1154 {
1155 ssa_fix_duplicate_block_edges (rd, local_info);
1156 return 0;
1157 }
1158
1159 return 1;
1160}
1161
1162/* Hash table traversal callback to redirect each incoming edge
1163 associated with this hash table element to its new destination. */
1164
1165int
1166ssa_redirect_edges (struct redirection_data **slot,
1167 ssa_local_info_t *local_info)
1168{
1169 struct redirection_data *rd = *slot;
1170 struct el *next, *el;
1171
1172 /* Walk over all the incoming edges associated with this hash table
1173 entry. */
1174 for (el = rd->incoming_edges; el; el = next)
1175 {
1176 edge e = el->e;
1177 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1178
1179 /* Go ahead and free this element from the list. Doing this now
1180 avoids the need for another list walk when we destroy the hash
1181 table. */
1182 next = el->next;
1183 free (el);
1184
1185 thread_stats.num_threaded_edges++;
1186
1187 if (rd->dup_blocks[0])
1188 {
1189 edge e2;
1190
1191 if (dump_file && (dump_flags & TDF_DETAILS))
1192 fprintf (dump_file, " Threaded jump %d --> %d to %d\n",
1193 e->src->index, e->dest->index, rd->dup_blocks[0]->index);
1194
1195 /* Redirect the incoming edge (possibly to the joiner block) to the
1196 appropriate duplicate block. */
1197 e2 = redirect_edge_and_branch (e, rd->dup_blocks[0]);
1198 gcc_assert (e == e2);
1199 flush_pending_stmts (e2);
1200 }
1201
1202 /* Go ahead and clear E->aux. It's not needed anymore and failure
1203 to clear it will cause all kinds of unpleasant problems later. */
1204 delete_jump_thread_path (path);
1205 e->aux = NULL;
1206
1207 }
1208
1209 /* Indicate that we actually threaded one or more jumps. */
1210 if (rd->incoming_edges)
1211 local_info->jumps_threaded = true;
1212
1213 return 1;
1214}
1215
1216/* Return true if this block has no executable statements other than
1217 a simple ctrl flow instruction. When the number of outgoing edges
1218 is one, this is equivalent to a "forwarder" block. */
1219
1220static bool
1221redirection_block_p (basic_block bb)
1222{
1223 gimple_stmt_iterator gsi;
1224
1225 /* Advance to the first executable statement. */
1226 gsi = gsi_start_bb (bb);
1227 while (!gsi_end_p (gsi)
1228 && (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL
1229 || is_gimple_debug (gsi_stmt (gsi))
1230 || gimple_nop_p (gsi_stmt (gsi))
1231 || gimple_clobber_p (gsi_stmt (gsi))))
1232 gsi_next (&gsi);
1233
1234 /* Check if this is an empty block. */
1235 if (gsi_end_p (gsi))
1236 return true;
1237
1238 /* Test that we've reached the terminating control statement. */
1239 return gsi_stmt (gsi)
1240 && (gimple_code (gsi_stmt (gsi)) == GIMPLE_COND
1241 || gimple_code (gsi_stmt (gsi)) == GIMPLE_GOTO
1242 || gimple_code (gsi_stmt (gsi)) == GIMPLE_SWITCH);
1243}
1244
1245/* BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB
1246 is reached via one or more specific incoming edges, we know which
1247 outgoing edge from BB will be traversed.
1248
1249 We want to redirect those incoming edges to the target of the
1250 appropriate outgoing edge. Doing so avoids a conditional branch
1251 and may expose new optimization opportunities. Note that we have
1252 to update dominator tree and SSA graph after such changes.
1253
1254 The key to keeping the SSA graph update manageable is to duplicate
1255 the side effects occurring in BB so that those side effects still
1256 occur on the paths which bypass BB after redirecting edges.
1257
1258 We accomplish this by creating duplicates of BB and arranging for
1259 the duplicates to unconditionally pass control to one specific
1260 successor of BB. We then revector the incoming edges into BB to
1261 the appropriate duplicate of BB.
1262
1263 If NOLOOP_ONLY is true, we only perform the threading as long as it
1264 does not affect the structure of the loops in a nontrivial way.
1265
1266 If JOINERS is true, then thread through joiner blocks as well. */
1267
1268static bool
1269thread_block_1 (basic_block bb, bool noloop_only, bool joiners)
1270{
1271 /* E is an incoming edge into BB that we may or may not want to
1272 redirect to a duplicate of BB. */
1273 edge e, e2;
1274 edge_iterator ei;
1275 ssa_local_info_t local_info;
1276
1277 local_info.duplicate_blocks = BITMAP_ALLOC (NULL);
1278 local_info.need_profile_correction = false;
1279
1280 /* To avoid scanning a linear array for the element we need we instead
1281 use a hash table. For normal code there should be no noticeable
1282 difference. However, if we have a block with a large number of
1283 incoming and outgoing edges such linear searches can get expensive. */
1284 redirection_data
1285 = new hash_table<struct redirection_data> (EDGE_COUNT (bb->succs));
1286
1287 /* Record each unique threaded destination into a hash table for
1288 efficient lookups. */
1289 edge last = NULL;
1290 FOR_EACH_EDGE (e, ei, bb->preds)
1291 {
1292 if (e->aux == NULL)
1293 continue;
1294
1295 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1296
1297 if (((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && !joiners)
1298 || ((*path)[1]->type == EDGE_COPY_SRC_BLOCK && joiners))
1299 continue;
1300
1301 e2 = path->last ()->e;
1302 if (!e2 || noloop_only)
1303 {
1304 /* If NOLOOP_ONLY is true, we only allow threading through the
1305 header of a loop to exit edges. */
1306
1307 /* One case occurs when there was loop header buried in a jump
1308 threading path that crosses loop boundaries. We do not try
1309 and thread this elsewhere, so just cancel the jump threading
1310 request by clearing the AUX field now. */
1311 if (bb->loop_father != e2->src->loop_father
1312 && !loop_exit_edge_p (e2->src->loop_father, e2))
1313 {
1314 /* Since this case is not handled by our special code
1315 to thread through a loop header, we must explicitly
1316 cancel the threading request here. */
1317 delete_jump_thread_path (path);
1318 e->aux = NULL;
1319 continue;
1320 }
1321
1322 /* Another case occurs when trying to thread through our
1323 own loop header, possibly from inside the loop. We will
1324 thread these later. */
1325 unsigned int i;
1326 for (i = 1; i < path->length (); i++)
1327 {
1328 if ((*path)[i]->e->src == bb->loop_father->header
1329 && (!loop_exit_edge_p (bb->loop_father, e2)
1330 || (*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK))
1331 break;
1332 }
1333
1334 if (i != path->length ())
1335 continue;
1336 }
1337
1338 /* Insert the outgoing edge into the hash table if it is not
1339 already in the hash table. */
1340 lookup_redirection_data (e, INSERT);
1341
1342 /* When we have thread paths through a common joiner with different
1343 final destinations, then we may need corrections to deal with
1344 profile insanities. See the big comment before compute_path_counts. */
1345 if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
1346 {
1347 if (!last)
1348 last = e2;
1349 else if (e2 != last)
1350 local_info.need_profile_correction = true;
1351 }
1352 }
1353
1354 /* We do not update dominance info. */
1355 free_dominance_info (CDI_DOMINATORS);
1356
1357 /* We know we only thread through the loop header to loop exits.
1358 Let the basic block duplication hook know we are not creating
1359 a multiple entry loop. */
1360 if (noloop_only
1361 && bb == bb->loop_father->header)
1362 set_loop_copy (bb->loop_father, loop_outer (bb->loop_father));
1363
1364 /* Now create duplicates of BB.
1365
1366 Note that for a block with a high outgoing degree we can waste
1367 a lot of time and memory creating and destroying useless edges.
1368
1369 So we first duplicate BB and remove the control structure at the
1370 tail of the duplicate as well as all outgoing edges from the
1371 duplicate. We then use that duplicate block as a template for
1372 the rest of the duplicates. */
1373 local_info.template_block = NULL;
1374 local_info.bb = bb;
1375 local_info.jumps_threaded = false;
1376 redirection_data->traverse <ssa_local_info_t *, ssa_create_duplicates>
1377 (&local_info);
1378
1379 /* The template does not have an outgoing edge. Create that outgoing
1380 edge and update PHI nodes as the edge's target as necessary.
1381
1382 We do this after creating all the duplicates to avoid creating
1383 unnecessary edges. */
1384 redirection_data->traverse <ssa_local_info_t *, ssa_fixup_template_block>
1385 (&local_info);
1386
1387 /* The hash table traversals above created the duplicate blocks (and the
1388 statements within the duplicate blocks). This loop creates PHI nodes for
1389 the duplicated blocks and redirects the incoming edges into BB to reach
1390 the duplicates of BB. */
1391 redirection_data->traverse <ssa_local_info_t *, ssa_redirect_edges>
1392 (&local_info);
1393
1394 /* Done with this block. Clear REDIRECTION_DATA. */
1395 delete redirection_data;
1396 redirection_data = NULL;
1397
1398 if (noloop_only
1399 && bb == bb->loop_father->header)
1400 set_loop_copy (bb->loop_father, NULL);
1401
1402 BITMAP_FREE (local_info.duplicate_blocks);
1403 local_info.duplicate_blocks = NULL;
1404
1405 /* Indicate to our caller whether or not any jumps were threaded. */
1406 return local_info.jumps_threaded;
1407}
1408
1409/* Wrapper for thread_block_1 so that we can first handle jump
1410 thread paths which do not involve copying joiner blocks, then
1411 handle jump thread paths which have joiner blocks.
1412
1413 By doing things this way we can be as aggressive as possible and
1414 not worry that copying a joiner block will create a jump threading
1415 opportunity. */
1416
1417static bool
1418thread_block (basic_block bb, bool noloop_only)
1419{
1420 bool retval;
1421 retval = thread_block_1 (bb, noloop_only, false);
1422 retval |= thread_block_1 (bb, noloop_only, true);
1423 return retval;
1424}
1425
1426/* Callback for dfs_enumerate_from. Returns true if BB is different
1427 from STOP and DBDS_CE_STOP. */
1428
1429static basic_block dbds_ce_stop;
1430static bool
1431dbds_continue_enumeration_p (const_basic_block bb, const void *stop)
1432{
1433 return (bb != (const_basic_block) stop
1434 && bb != dbds_ce_stop);
1435}
1436
1437/* Evaluates the dominance relationship of latch of the LOOP and BB, and
1438 returns the state. */
1439
1440enum bb_dom_status
1441determine_bb_domination_status (struct loop *loop, basic_block bb)
1442{
1443 basic_block *bblocks;
1444 unsigned nblocks, i;
1445 bool bb_reachable = false;
1446 edge_iterator ei;
1447 edge e;
1448
1449 /* This function assumes BB is a successor of LOOP->header.
1450 If that is not the case return DOMST_NONDOMINATING which
1451 is always safe. */
1452 {
1453 bool ok = false;
1454
1455 FOR_EACH_EDGE (e, ei, bb->preds)
1456 {
1457 if (e->src == loop->header)
1458 {
1459 ok = true;
1460 break;
1461 }
1462 }
1463
1464 if (!ok)
1465 return DOMST_NONDOMINATING;
1466 }
1467
1468 if (bb == loop->latch)
1469 return DOMST_DOMINATING;
1470
1471 /* Check that BB dominates LOOP->latch, and that it is back-reachable
1472 from it. */
1473
1474 bblocks = XCNEWVEC (basic_block, loop->num_nodes);
1475 dbds_ce_stop = loop->header;
1476 nblocks = dfs_enumerate_from (loop->latch, 1, dbds_continue_enumeration_p,
1477 bblocks, loop->num_nodes, bb);
1478 for (i = 0; i < nblocks; i++)
1479 FOR_EACH_EDGE (e, ei, bblocks[i]->preds)
1480 {
1481 if (e->src == loop->header)
1482 {
1483 free (bblocks);
1484 return DOMST_NONDOMINATING;
1485 }
1486 if (e->src == bb)
1487 bb_reachable = true;
1488 }
1489
1490 free (bblocks);
1491 return (bb_reachable ? DOMST_DOMINATING : DOMST_LOOP_BROKEN);
1492}
1493
1494/* Thread jumps through the header of LOOP. Returns true if cfg changes.
1495 If MAY_PEEL_LOOP_HEADERS is false, we avoid threading from entry edges
1496 to the inside of the loop. */
1497
1498static bool
1499thread_through_loop_header (struct loop *loop, bool may_peel_loop_headers)
1500{
1501 basic_block header = loop->header;
1502 edge e, tgt_edge, latch = loop_latch_edge (loop);
1503 edge_iterator ei;
1504 basic_block tgt_bb, atgt_bb;
1505 enum bb_dom_status domst;
1506
1507 /* We have already threaded through headers to exits, so all the threading
1508 requests now are to the inside of the loop. We need to avoid creating
1509 irreducible regions (i.e., loops with more than one entry block), and
1510 also loop with several latch edges, or new subloops of the loop (although
1511 there are cases where it might be appropriate, it is difficult to decide,
1512 and doing it wrongly may confuse other optimizers).
1513
1514 We could handle more general cases here. However, the intention is to
1515 preserve some information about the loop, which is impossible if its
1516 structure changes significantly, in a way that is not well understood.
1517 Thus we only handle few important special cases, in which also updating
1518 of the loop-carried information should be feasible:
1519
1520 1) Propagation of latch edge to a block that dominates the latch block
1521 of a loop. This aims to handle the following idiom:
1522
1523 first = 1;
1524 while (1)
1525 {
1526 if (first)
1527 initialize;
1528 first = 0;
1529 body;
1530 }
1531
1532 After threading the latch edge, this becomes
1533
1534 first = 1;
1535 if (first)
1536 initialize;
1537 while (1)
1538 {
1539 first = 0;
1540 body;
1541 }
1542
1543 The original header of the loop is moved out of it, and we may thread
1544 the remaining edges through it without further constraints.
1545
1546 2) All entry edges are propagated to a single basic block that dominates
1547 the latch block of the loop. This aims to handle the following idiom
1548 (normally created for "for" loops):
1549
1550 i = 0;
1551 while (1)
1552 {
1553 if (i >= 100)
1554 break;
1555 body;
1556 i++;
1557 }
1558
1559 This becomes
1560
1561 i = 0;
1562 while (1)
1563 {
1564 body;
1565 i++;
1566 if (i >= 100)
1567 break;
1568 }
1569 */
1570
1571 /* Threading through the header won't improve the code if the header has just
1572 one successor. */
1573 if (single_succ_p (header))
1574 goto fail;
1575
1576 if (!may_peel_loop_headers && !redirection_block_p (loop->header))
1577 goto fail;
1578 else
1579 {
1580 tgt_bb = NULL;
1581 tgt_edge = NULL;
1582 FOR_EACH_EDGE (e, ei, header->preds)
1583 {
1584 if (!e->aux)
1585 {
1586 if (e == latch)
1587 continue;
1588
1589 /* If latch is not threaded, and there is a header
1590 edge that is not threaded, we would create loop
1591 with multiple entries. */
1592 goto fail;
1593 }
1594
1595 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1596
1597 if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
1598 goto fail;
1599 tgt_edge = (*path)[1]->e;
1600 atgt_bb = tgt_edge->dest;
1601 if (!tgt_bb)
1602 tgt_bb = atgt_bb;
1603 /* Two targets of threading would make us create loop
1604 with multiple entries. */
1605 else if (tgt_bb != atgt_bb)
1606 goto fail;
1607 }
1608
1609 if (!tgt_bb)
1610 {
1611 /* There are no threading requests. */
1612 return false;
1613 }
1614
1615 /* Redirecting to empty loop latch is useless. */
1616 if (tgt_bb == loop->latch
1617 && empty_block_p (loop->latch))
1618 goto fail;
1619 }
1620
1621 /* The target block must dominate the loop latch, otherwise we would be
1622 creating a subloop. */
1623 domst = determine_bb_domination_status (loop, tgt_bb);
1624 if (domst == DOMST_NONDOMINATING)
1625 goto fail;
1626 if (domst == DOMST_LOOP_BROKEN)
1627 {
1628 /* If the loop ceased to exist, mark it as such, and thread through its
1629 original header. */
1630 mark_loop_for_removal (loop);
1631 return thread_block (header, false);
1632 }
1633
1634 if (tgt_bb->loop_father->header == tgt_bb)
1635 {
1636 /* If the target of the threading is a header of a subloop, we need
1637 to create a preheader for it, so that the headers of the two loops
1638 do not merge. */
1639 if (EDGE_COUNT (tgt_bb->preds) > 2)
1640 {
1641 tgt_bb = create_preheader (tgt_bb->loop_father, 0);
1642 gcc_assert (tgt_bb != NULL);
1643 }
1644 else
1645 tgt_bb = split_edge (tgt_edge);
1646 }
1647
1648 basic_block new_preheader;
1649
1650 /* Now consider the case entry edges are redirected to the new entry
1651 block. Remember one entry edge, so that we can find the new
1652 preheader (its destination after threading). */
1653 FOR_EACH_EDGE (e, ei, header->preds)
1654 {
1655 if (e->aux)
1656 break;
1657 }
1658
1659 /* The duplicate of the header is the new preheader of the loop. Ensure
1660 that it is placed correctly in the loop hierarchy. */
1661 set_loop_copy (loop, loop_outer (loop));
1662
1663 thread_block (header, false);
1664 set_loop_copy (loop, NULL);
1665 new_preheader = e->dest;
1666
1667 /* Create the new latch block. This is always necessary, as the latch
1668 must have only a single successor, but the original header had at
1669 least two successors. */
1670 loop->latch = NULL;
1671 mfb_kj_edge = single_succ_edge (new_preheader);
1672 loop->header = mfb_kj_edge->dest;
1673 latch = make_forwarder_block (tgt_bb, mfb_keep_just, NULL);
1674 loop->header = latch->dest;
1675 loop->latch = latch->src;
1676 return true;
1677
1678fail:
1679 /* We failed to thread anything. Cancel the requests. */
1680 FOR_EACH_EDGE (e, ei, header->preds)
1681 {
1682 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1683
1684 if (path)
1685 {
1686 delete_jump_thread_path (path);
1687 e->aux = NULL;
1688 }
1689 }
1690 return false;
1691}
1692
1693/* E1 and E2 are edges into the same basic block. Return TRUE if the
1694 PHI arguments associated with those edges are equal or there are no
1695 PHI arguments, otherwise return FALSE. */
1696
1697static bool
1698phi_args_equal_on_edges (edge e1, edge e2)
1699{
1700 gphi_iterator gsi;
1701 int indx1 = e1->dest_idx;
1702 int indx2 = e2->dest_idx;
1703
1704 for (gsi = gsi_start_phis (e1->dest); !gsi_end_p (gsi); gsi_next (&gsi))
1705 {
1706 gphi *phi = gsi.phi ();
1707
1708 if (!operand_equal_p (gimple_phi_arg_def (phi, indx1),
1709 gimple_phi_arg_def (phi, indx2), 0))
1710 return false;
1711 }
1712 return true;
1713}
1714
1715/* Walk through the registered jump threads and convert them into a
1716 form convenient for this pass.
1717
1718 Any block which has incoming edges threaded to outgoing edges
1719 will have its entry in THREADED_BLOCK set.
1720
1721 Any threaded edge will have its new outgoing edge stored in the
1722 original edge's AUX field.
1723
1724 This form avoids the need to walk all the edges in the CFG to
1725 discover blocks which need processing and avoids unnecessary
1726 hash table lookups to map from threaded edge to new target. */
1727
1728static void
1729mark_threaded_blocks (bitmap threaded_blocks)
1730{
1731 unsigned int i;
1732 bitmap_iterator bi;
1733 auto_bitmap tmp;
1734 basic_block bb;
1735 edge e;
1736 edge_iterator ei;
1737
1738 /* It is possible to have jump threads in which one is a subpath
1739 of the other. ie, (A, B), (B, C), (C, D) where B is a joiner
1740 block and (B, C), (C, D) where no joiner block exists.
1741
1742 When this occurs ignore the jump thread request with the joiner
1743 block. It's totally subsumed by the simpler jump thread request.
1744
1745 This results in less block copying, simpler CFGs. More importantly,
1746 when we duplicate the joiner block, B, in this case we will create
1747 a new threading opportunity that we wouldn't be able to optimize
1748 until the next jump threading iteration.
1749
1750 So first convert the jump thread requests which do not require a
1751 joiner block. */
1752 for (i = 0; i < paths.length (); i++)
1753 {
1754 vec<jump_thread_edge *> *path = paths[i];
1755
1756 if ((*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK)
1757 {
1758 edge e = (*path)[0]->e;
1759 e->aux = (void *)path;
1760 bitmap_set_bit (tmp, e->dest->index);
1761 }
1762 }
1763
1764 /* Now iterate again, converting cases where we want to thread
1765 through a joiner block, but only if no other edge on the path
1766 already has a jump thread attached to it. We do this in two passes,
1767 to avoid situations where the order in the paths vec can hide overlapping
1768 threads (the path is recorded on the incoming edge, so we would miss
1769 cases where the second path starts at a downstream edge on the same
1770 path). First record all joiner paths, deleting any in the unexpected
1771 case where there is already a path for that incoming edge. */
1772 for (i = 0; i < paths.length ();)
1773 {
1774 vec<jump_thread_edge *> *path = paths[i];
1775
1776 if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
1777 {
1778 /* Attach the path to the starting edge if none is yet recorded. */
1779 if ((*path)[0]->e->aux == NULL)
1780 {
1781 (*path)[0]->e->aux = path;
1782 i++;
1783 }
1784 else
1785 {
1786 paths.unordered_remove (i);
1787 if (dump_file && (dump_flags & TDF_DETAILS))
1788 dump_jump_thread_path (dump_file, *path, false);
1789 delete_jump_thread_path (path);
1790 }
1791 }
1792 else
1793 {
1794 i++;
1795 }
1796 }
1797
1798 /* Second, look for paths that have any other jump thread attached to
1799 them, and either finish converting them or cancel them. */
1800 for (i = 0; i < paths.length ();)
1801 {
1802 vec<jump_thread_edge *> *path = paths[i];
1803 edge e = (*path)[0]->e;
1804
1805 if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && e->aux == path)
1806 {
1807 unsigned int j;
1808 for (j = 1; j < path->length (); j++)
1809 if ((*path)[j]->e->aux != NULL)
1810 break;
1811
1812 /* If we iterated through the entire path without exiting the loop,
1813 then we are good to go, record it. */
1814 if (j == path->length ())
1815 {
1816 bitmap_set_bit (tmp, e->dest->index);
1817 i++;
1818 }
1819 else
1820 {
1821 e->aux = NULL;
1822 paths.unordered_remove (i);
1823 if (dump_file && (dump_flags & TDF_DETAILS))
1824 dump_jump_thread_path (dump_file, *path, false);
1825 delete_jump_thread_path (path);
1826 }
1827 }
1828 else
1829 {
1830 i++;
1831 }
1832 }
1833
1834 /* If optimizing for size, only thread through block if we don't have
1835 to duplicate it or it's an otherwise empty redirection block. */
1836 if (optimize_function_for_size_p (cfun))
1837 {
1838 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
1839 {
1840 bb = BASIC_BLOCK_FOR_FN (cfun, i);
1841 if (EDGE_COUNT (bb->preds) > 1
1842 && !redirection_block_p (bb))
1843 {
1844 FOR_EACH_EDGE (e, ei, bb->preds)
1845 {
1846 if (e->aux)
1847 {
1848 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1849 delete_jump_thread_path (path);
1850 e->aux = NULL;
1851 }
1852 }
1853 }
1854 else
1855 bitmap_set_bit (threaded_blocks, i);
1856 }
1857 }
1858 else
1859 bitmap_copy (threaded_blocks, tmp);
1860
1861 /* If we have a joiner block (J) which has two successors S1 and S2 and
1862 we are threading though S1 and the final destination of the thread
1863 is S2, then we must verify that any PHI nodes in S2 have the same
1864 PHI arguments for the edge J->S2 and J->S1->...->S2.
1865
1866 We used to detect this prior to registering the jump thread, but
1867 that prohibits propagation of edge equivalences into non-dominated
1868 PHI nodes as the equivalency test might occur before propagation.
1869
1870 This must also occur after we truncate any jump threading paths
1871 as this scenario may only show up after truncation.
1872
1873 This works for now, but will need improvement as part of the FSA
1874 optimization.
1875
1876 Note since we've moved the thread request data to the edges,
1877 we have to iterate on those rather than the threaded_edges vector. */
1878 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
1879 {
1880 bb = BASIC_BLOCK_FOR_FN (cfun, i);
1881 FOR_EACH_EDGE (e, ei, bb->preds)
1882 {
1883 if (e->aux)
1884 {
1885 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1886 bool have_joiner = ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK);
1887
1888 if (have_joiner)
1889 {
1890 basic_block joiner = e->dest;
1891 edge final_edge = path->last ()->e;
1892 basic_block final_dest = final_edge->dest;
1893 edge e2 = find_edge (joiner, final_dest);
1894
1895 if (e2 && !phi_args_equal_on_edges (e2, final_edge))
1896 {
1897 delete_jump_thread_path (path);
1898 e->aux = NULL;
1899 }
1900 }
1901 }
1902 }
1903 }
1904
1905 /* Look for jump threading paths which cross multiple loop headers.
1906
1907 The code to thread through loop headers will change the CFG in ways
1908 that invalidate the cached loop iteration information. So we must
1909 detect that case and wipe the cached information. */
1910 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
1911 {
1912 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1913 FOR_EACH_EDGE (e, ei, bb->preds)
1914 {
1915 if (e->aux)
1916 {
1917 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1918
1919 for (unsigned int i = 0, crossed_headers = 0;
1920 i < path->length ();
1921 i++)
1922 {
1923 basic_block dest = (*path)[i]->e->dest;
1924 basic_block src = (*path)[i]->e->src;
1925 /* If we enter a loop. */
1926 if (flow_loop_nested_p (src->loop_father, dest->loop_father))
1927 ++crossed_headers;
1928 /* If we step from a block outside an irreducible region
1929 to a block inside an irreducible region, then we have
1930 crossed into a loop. */
1931 else if (! (src->flags & BB_IRREDUCIBLE_LOOP)
1932 && (dest->flags & BB_IRREDUCIBLE_LOOP))
1933 ++crossed_headers;
1934 if (crossed_headers > 1)
1935 {
1936 vect_free_loop_info_assumptions
1937 ((*path)[path->length () - 1]->e->dest->loop_father);
1938 break;
1939 }
1940 }
1941 }
1942 }
1943 }
1944}
1945
1946
1947/* Verify that the REGION is a valid jump thread. A jump thread is a special
1948 case of SEME Single Entry Multiple Exits region in which all nodes in the
1949 REGION have exactly one incoming edge. The only exception is the first block
1950 that may not have been connected to the rest of the cfg yet. */
1951
1952DEBUG_FUNCTION void
1953verify_jump_thread (basic_block *region, unsigned n_region)
1954{
1955 for (unsigned i = 0; i < n_region; i++)
1956 gcc_assert (EDGE_COUNT (region[i]->preds) <= 1);
1957}
1958
1959/* Return true when BB is one of the first N items in BBS. */
1960
1961static inline bool
1962bb_in_bbs (basic_block bb, basic_block *bbs, int n)
1963{
1964 for (int i = 0; i < n; i++)
1965 if (bb == bbs[i])
1966 return true;
1967
1968 return false;
1969}
1970
1971/* Duplicates a jump-thread path of N_REGION basic blocks.
1972 The ENTRY edge is redirected to the duplicate of the region.
1973
1974 Remove the last conditional statement in the last basic block in the REGION,
1975 and create a single fallthru edge pointing to the same destination as the
1976 EXIT edge.
1977
1978 Returns false if it is unable to copy the region, true otherwise. */
1979
1980static bool
1981duplicate_thread_path (edge entry, edge exit, basic_block *region,
1982 unsigned n_region)
1983{
1984 unsigned i;
1985 struct loop *loop = entry->dest->loop_father;
1986 edge exit_copy;
1987 edge redirected;
1988 profile_count curr_count;
1989
1990 if (!can_copy_bbs_p (region, n_region))
1991 return false;
1992
1993 /* Some sanity checking. Note that we do not check for all possible
1994 missuses of the functions. I.e. if you ask to copy something weird,
1995 it will work, but the state of structures probably will not be
1996 correct. */
1997 for (i = 0; i < n_region; i++)
1998 {
1999 /* We do not handle subloops, i.e. all the blocks must belong to the
2000 same loop. */
2001 if (region[i]->loop_father != loop)
2002 return false;
2003 }
2004
2005 initialize_original_copy_tables ();
2006
2007 set_loop_copy (loop, loop);
2008
2009 basic_block *region_copy = XNEWVEC (basic_block, n_region);
2010 copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
2011 split_edge_bb_loc (entry), false);
2012
2013 /* Fix up: copy_bbs redirects all edges pointing to copied blocks. The
2014 following code ensures that all the edges exiting the jump-thread path are
2015 redirected back to the original code: these edges are exceptions
2016 invalidating the property that is propagated by executing all the blocks of
2017 the jump-thread path in order. */
2018
2019 curr_count = entry->count ();
2020
2021 for (i = 0; i < n_region; i++)
2022 {
2023 edge e;
2024 edge_iterator ei;
2025 basic_block bb = region_copy[i];
2026
2027 /* Watch inconsistent profile. */
2028 if (curr_count > region[i]->count)
2029 curr_count = region[i]->count;
2030 /* Scale current BB. */
2031 if (region[i]->count.nonzero_p () && curr_count.initialized_p ())
2032 {
2033 /* In the middle of the path we only scale the frequencies.
2034 In last BB we need to update probabilities of outgoing edges
2035 because we know which one is taken at the threaded path. */
2036 if (i + 1 != n_region)
2037 scale_bbs_frequencies_profile_count (region + i, 1,
2038 region[i]->count - curr_count,
2039 region[i]->count);
2040 else
2041 update_bb_profile_for_threading (region[i],
2042 curr_count,
2043 exit);
2044 scale_bbs_frequencies_profile_count (region_copy + i, 1, curr_count,
2045 region_copy[i]->count);
2046 }
2047
2048 if (single_succ_p (bb))
2049 {
2050 /* Make sure the successor is the next node in the path. */
2051 gcc_assert (i + 1 == n_region
2052 || region_copy[i + 1] == single_succ_edge (bb)->dest);
2053 if (i + 1 != n_region)
2054 {
2055 curr_count = single_succ_edge (bb)->count ();
2056 }
2057 continue;
2058 }
2059
2060 /* Special case the last block on the path: make sure that it does not
2061 jump back on the copied path, including back to itself. */
2062 if (i + 1 == n_region)
2063 {
2064 FOR_EACH_EDGE (e, ei, bb->succs)
2065 if (bb_in_bbs (e->dest, region_copy, n_region))
2066 {
2067 basic_block orig = get_bb_original (e->dest);
2068 if (orig)
2069 redirect_edge_and_branch_force (e, orig);
2070 }
2071 continue;
2072 }
2073
2074 /* Redirect all other edges jumping to non-adjacent blocks back to the
2075 original code. */
2076 FOR_EACH_EDGE (e, ei, bb->succs)
2077 if (region_copy[i + 1] != e->dest)
2078 {
2079 basic_block orig = get_bb_original (e->dest);
2080 if (orig)
2081 redirect_edge_and_branch_force (e, orig);
2082 }
2083 else
2084 {
2085 curr_count = e->count ();
2086 }
2087 }
2088
2089
2090 if (flag_checking)
2091 verify_jump_thread (region_copy, n_region);
2092
2093 /* Remove the last branch in the jump thread path. */
2094 remove_ctrl_stmt_and_useless_edges (region_copy[n_region - 1], exit->dest);
2095
2096 /* And fixup the flags on the single remaining edge. */
2097 edge fix_e = find_edge (region_copy[n_region - 1], exit->dest);
2098 fix_e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL);
2099 fix_e->flags |= EDGE_FALLTHRU;
2100
2101 edge e = make_edge (region_copy[n_region - 1], exit->dest, EDGE_FALLTHRU);
2102
2103 if (e)
2104 {
2105 rescan_loop_exit (e, true, false);
2106 e->probability = profile_probability::always ();
2107 }
2108
2109 /* Redirect the entry and add the phi node arguments. */
2110 if (entry->dest == loop->header)
2111 mark_loop_for_removal (loop);
2112 redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
2113 gcc_assert (redirected != NULL);
2114 flush_pending_stmts (entry);
2115
2116 /* Add the other PHI node arguments. */
2117 add_phi_args_after_copy (region_copy, n_region, NULL);
2118
2119 free (region_copy);
2120
2121 free_original_copy_tables ();
2122 return true;
2123}
2124
2125/* Return true when PATH is a valid jump-thread path. */
2126
2127static bool
2128valid_jump_thread_path (vec<jump_thread_edge *> *path)
2129{
2130 unsigned len = path->length ();
2131
2132 /* Check that the path is connected. */
2133 for (unsigned int j = 0; j < len - 1; j++)
2134 {
2135 edge e = (*path)[j]->e;
2136 if (e->dest != (*path)[j+1]->e->src)
2137 return false;
2138 }
2139 return true;
2140}
2141
2142/* Remove any queued jump threads that include edge E.
2143
2144 We don't actually remove them here, just record the edges into ax
2145 hash table. That way we can do the search once per iteration of
2146 DOM/VRP rather than for every case where DOM optimizes away a COND_EXPR. */
2147
2148void
2149remove_jump_threads_including (edge_def *e)
2150{
2151 if (!paths.exists ())
2152 return;
2153
2154 if (!removed_edges)
2155 removed_edges = new hash_table<struct removed_edges> (17);
2156
2157 edge *slot = removed_edges->find_slot (e, INSERT);
2158 *slot = e;
2159}
2160
2161/* Walk through all blocks and thread incoming edges to the appropriate
2162 outgoing edge for each edge pair recorded in THREADED_EDGES.
2163
2164 It is the caller's responsibility to fix the dominance information
2165 and rewrite duplicated SSA_NAMEs back into SSA form.
2166
2167 If MAY_PEEL_LOOP_HEADERS is false, we avoid threading edges through
2168 loop headers if it does not simplify the loop.
2169
2170 Returns true if one or more edges were threaded, false otherwise. */
2171
2172bool
2173thread_through_all_blocks (bool may_peel_loop_headers)
2174{
2175 bool retval = false;
2176 unsigned int i;
2177 struct loop *loop;
2178 auto_bitmap threaded_blocks;
2179
2180 if (!paths.exists ())
2181 {
2182 retval = false;
2183 goto out;
2184 }
2185
2186 memset (&thread_stats, 0, sizeof (thread_stats));
2187
2188 /* Remove any paths that referenced removed edges. */
2189 if (removed_edges)
2190 for (i = 0; i < paths.length (); )
2191 {
2192 unsigned int j;
2193 vec<jump_thread_edge *> *path = paths[i];
2194
2195 for (j = 0; j < path->length (); j++)
2196 {
2197 edge e = (*path)[j]->e;
2198 if (removed_edges->find_slot (e, NO_INSERT))
2199 break;
2200 }
2201
2202 if (j != path->length ())
2203 {
2204 delete_jump_thread_path (path);
2205 paths.unordered_remove (i);
2206 continue;
2207 }
2208 i++;
2209 }
2210
2211 /* Jump-thread all FSM threads before other jump-threads. */
2212 for (i = 0; i < paths.length ();)
2213 {
2214 vec<jump_thread_edge *> *path = paths[i];
2215 edge entry = (*path)[0]->e;
2216
2217 /* Only code-generate FSM jump-threads in this loop. */
2218 if ((*path)[0]->type != EDGE_FSM_THREAD)
2219 {
2220 i++;
2221 continue;
2222 }
2223
2224 /* Do not jump-thread twice from the same block. */
2225 if (bitmap_bit_p (threaded_blocks, entry->src->index)
2226 /* We may not want to realize this jump thread path
2227 for various reasons. So check it first. */
2228 || !valid_jump_thread_path (path))
2229 {
2230 /* Remove invalid FSM jump-thread paths. */
2231 delete_jump_thread_path (path);
2232 paths.unordered_remove (i);
2233 continue;
2234 }
2235
2236 unsigned len = path->length ();
2237 edge exit = (*path)[len - 1]->e;
2238 basic_block *region = XNEWVEC (basic_block, len - 1);
2239
2240 for (unsigned int j = 0; j < len - 1; j++)
2241 region[j] = (*path)[j]->e->dest;
2242
2243 if (duplicate_thread_path (entry, exit, region, len - 1))
2244 {
2245 /* We do not update dominance info. */
2246 free_dominance_info (CDI_DOMINATORS);
2247 bitmap_set_bit (threaded_blocks, entry->src->index);
2248 retval = true;
2249 thread_stats.num_threaded_edges++;
2250 }
2251
2252 delete_jump_thread_path (path);
2253 paths.unordered_remove (i);
2254 free (region);
2255 }
2256
2257 /* Remove from PATHS all the jump-threads starting with an edge already
2258 jump-threaded. */
2259 for (i = 0; i < paths.length ();)
2260 {
2261 vec<jump_thread_edge *> *path = paths[i];
2262 edge entry = (*path)[0]->e;
2263
2264 /* Do not jump-thread twice from the same block. */
2265 if (bitmap_bit_p (threaded_blocks, entry->src->index))
2266 {
2267 delete_jump_thread_path (path);
2268 paths.unordered_remove (i);
2269 }
2270 else
2271 i++;
2272 }
2273
2274 bitmap_clear (threaded_blocks);
2275
2276 mark_threaded_blocks (threaded_blocks);
2277
2278 initialize_original_copy_tables ();
2279
2280 /* The order in which we process jump threads can be important.
2281
2282 Consider if we have two jump threading paths A and B. If the
2283 target edge of A is the starting edge of B and we thread path A
2284 first, then we create an additional incoming edge into B->dest that
2285 we can not discover as a jump threading path on this iteration.
2286
2287 If we instead thread B first, then the edge into B->dest will have
2288 already been redirected before we process path A and path A will
2289 natually, with no further work, target the redirected path for B.
2290
2291 An post-order is sufficient here. Compute the ordering first, then
2292 process the blocks. */
2293 if (!bitmap_empty_p (threaded_blocks))
2294 {
2295 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
2296 unsigned int postorder_num = post_order_compute (postorder, false, false);
2297 for (unsigned int i = 0; i < postorder_num; i++)
2298 {
2299 unsigned int indx = postorder[i];
2300 if (bitmap_bit_p (threaded_blocks, indx))
2301 {
2302 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, indx);
2303 retval |= thread_block (bb, true);
2304 }
2305 }
2306 free (postorder);
2307 }
2308
2309 /* Then perform the threading through loop headers. We start with the
2310 innermost loop, so that the changes in cfg we perform won't affect
2311 further threading. */
2312 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
2313 {
2314 if (!loop->header
2315 || !bitmap_bit_p (threaded_blocks, loop->header->index))
2316 continue;
2317
2318 retval |= thread_through_loop_header (loop, may_peel_loop_headers);
2319 }
2320
2321 /* All jump threading paths should have been resolved at this
2322 point. Verify that is the case. */
2323 basic_block bb;
2324 FOR_EACH_BB_FN (bb, cfun)
2325 {
2326 edge_iterator ei;
2327 edge e;
2328 FOR_EACH_EDGE (e, ei, bb->preds)
2329 gcc_assert (e->aux == NULL);
2330 }
2331
2332 statistics_counter_event (cfun, "Jumps threaded",
2333 thread_stats.num_threaded_edges);
2334
2335 free_original_copy_tables ();
2336
2337 paths.release ();
2338
2339 if (retval)
2340 loops_state_set (LOOPS_NEED_FIXUP);
2341
2342 out:
2343 delete removed_edges;
2344 removed_edges = NULL;
2345 return retval;
2346}
2347
2348/* Delete the jump threading path PATH. We have to explicitly delete
2349 each entry in the vector, then the container. */
2350
2351void
2352delete_jump_thread_path (vec<jump_thread_edge *> *path)
2353{
2354 for (unsigned int i = 0; i < path->length (); i++)
2355 delete (*path)[i];
2356 path->release();
2357 delete path;
2358}
2359
2360/* Register a jump threading opportunity. We queue up all the jump
2361 threading opportunities discovered by a pass and update the CFG
2362 and SSA form all at once.
2363
2364 E is the edge we can thread, E2 is the new target edge, i.e., we
2365 are effectively recording that E->dest can be changed to E2->dest
2366 after fixing the SSA graph. */
2367
2368void
2369register_jump_thread (vec<jump_thread_edge *> *path)
2370{
2371 if (!dbg_cnt (registered_jump_thread))
2372 {
2373 delete_jump_thread_path (path);
2374 return;
2375 }
2376
2377 /* First make sure there are no NULL outgoing edges on the jump threading
2378 path. That can happen for jumping to a constant address. */
2379 for (unsigned int i = 0; i < path->length (); i++)
2380 {
2381 if ((*path)[i]->e == NULL)
2382 {
2383 if (dump_file && (dump_flags & TDF_DETAILS))
2384 {
2385 fprintf (dump_file,
2386 "Found NULL edge in jump threading path. Cancelling jump thread:\n");
2387 dump_jump_thread_path (dump_file, *path, false);
2388 }
2389
2390 delete_jump_thread_path (path);
2391 return;
2392 }
2393
2394 /* Only the FSM threader is allowed to thread across
2395 backedges in the CFG. */
2396 if (flag_checking
2397 && (*path)[0]->type != EDGE_FSM_THREAD)
2398 gcc_assert (((*path)[i]->e->flags & EDGE_DFS_BACK) == 0);
2399 }
2400
2401 if (dump_file && (dump_flags & TDF_DETAILS))
2402 dump_jump_thread_path (dump_file, *path, true);
2403
2404 if (!paths.exists ())
2405 paths.create (5);
2406
2407 paths.safe_push (path);
2408}
2409