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