OSDN Git Service

* builtins.c, c-pragma.h, c-typeck.c, cgraph.c, cgraphunit.c,
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-threadupdate.c
1 /* Thread edges through blocks and update the control flow and SSA graphs.
2    Copyright (C) 2004, 2005 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 2, 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 COPYING.  If not, write to
18 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
19 Boston, MA 02110-1301, USA.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "flags.h"
27 #include "rtl.h"
28 #include "tm_p.h"
29 #include "ggc.h"
30 #include "basic-block.h"
31 #include "output.h"
32 #include "expr.h"
33 #include "function.h"
34 #include "diagnostic.h"
35 #include "tree-flow.h"
36 #include "tree-dump.h"
37 #include "tree-pass.h"
38 #include "cfgloop.h"
39
40 /* Given a block B, update the CFG and SSA graph to reflect redirecting
41    one or more in-edges to B to instead reach the destination of an
42    out-edge from B while preserving any side effects in B.
43
44    i.e., given A->B and B->C, change A->B to be A->C yet still preserve the
45    side effects of executing B.
46
47      1. Make a copy of B (including its outgoing edges and statements).  Call
48         the copy B'.  Note B' has no incoming edges or PHIs at this time.
49
50      2. Remove the control statement at the end of B' and all outgoing edges
51         except B'->C.
52
53      3. Add a new argument to each PHI in C with the same value as the existing
54         argument associated with edge B->C.  Associate the new PHI arguments
55         with the edge B'->C.
56
57      4. For each PHI in B, find or create a PHI in B' with an identical
58         PHI_RESULT.  Add an argument to the PHI in B' which has the same
59         value as the PHI in B associated with the edge A->B.  Associate
60         the new argument in the PHI in B' with the edge A->B.
61
62      5. Change the edge A->B to A->B'.
63
64         5a. This automatically deletes any PHI arguments associated with the
65             edge A->B in B.
66
67         5b. This automatically associates each new argument added in step 4
68             with the edge A->B'.
69
70      6. Repeat for other incoming edges into B.
71
72      7. Put the duplicated resources in B and all the B' blocks into SSA form.
73
74    Note that block duplication can be minimized by first collecting the
75    the set of unique destination blocks that the incoming edges should
76    be threaded to.  Block duplication can be further minimized by using
77    B instead of creating B' for one destination if all edges into B are
78    going to be threaded to a successor of B.
79
80    We further reduce the number of edges and statements we create by
81    not copying all the outgoing edges and the control statement in
82    step #1.  We instead create a template block without the outgoing
83    edges and duplicate the template.  */
84
85
86 /* Steps #5 and #6 of the above algorithm are best implemented by walking
87    all the incoming edges which thread to the same destination edge at
88    the same time.  That avoids lots of table lookups to get information
89    for the destination edge.
90
91    To realize that implementation we create a list of incoming edges
92    which thread to the same outgoing edge.  Thus to implement steps
93    #5 and #6 we traverse our hash table of outgoing edge information.
94    For each entry we walk the list of incoming edges which thread to
95    the current outgoing edge.  */
96
97 struct el
98 {
99   edge e;
100   struct el *next;
101 };
102
103 /* Main data structure recording information regarding B's duplicate
104    blocks.  */
105
106 /* We need to efficiently record the unique thread destinations of this
107    block and specific information associated with those destinations.  We
108    may have many incoming edges threaded to the same outgoing edge.  This
109    can be naturally implemented with a hash table.  */
110
111 struct redirection_data
112 {
113   /* A duplicate of B with the trailing control statement removed and which
114      targets a single successor of B.  */
115   basic_block dup_block;
116
117   /* An outgoing edge from B.  DUP_BLOCK will have OUTGOING_EDGE->dest as
118      its single successor.  */
119   edge outgoing_edge;
120
121   /* A list of incoming edges which we want to thread to
122      OUTGOING_EDGE->dest.  */
123   struct el *incoming_edges;
124
125   /* Flag indicating whether or not we should create a duplicate block
126      for this thread destination.  This is only true if we are threading
127      all incoming edges and thus are using BB itself as a duplicate block.  */
128   bool do_not_duplicate;
129 };
130
131 /* Main data structure to hold information for duplicates of BB.  */
132 static htab_t redirection_data;
133
134 bool rediscover_loops_after_threading;
135
136 /* Data structure of information to pass to hash table traversal routines.  */
137 struct local_info
138 {
139   /* The current block we are working on.  */
140   basic_block bb;
141
142   /* A template copy of BB with no outgoing edges or control statement that
143      we use for creating copies.  */
144   basic_block template_block;
145
146   /* TRUE if we thread one or more jumps, FALSE otherwise.  */
147   bool jumps_threaded;
148 };
149
150 /* Passes which use the jump threading code register jump threading
151    opportunities as they are discovered.  We keep the registered
152    jump threading opportunities in this vector as edge pairs
153    (original_edge, target_edge).  */
154 DEF_VEC_ALLOC_P(edge,heap);
155 static VEC(edge,heap) *threaded_edges;
156
157
158 /* Jump threading statistics.  */
159
160 struct thread_stats_d
161 {
162   unsigned long num_threaded_edges;
163 };
164
165 struct thread_stats_d thread_stats;
166
167
168 /* Remove the last statement in block BB if it is a control statement
169    Also remove all outgoing edges except the edge which reaches DEST_BB.
170    If DEST_BB is NULL, then remove all outgoing edges.  */
171
172 static void
173 remove_ctrl_stmt_and_useless_edges (basic_block bb, basic_block dest_bb)
174 {
175   block_stmt_iterator bsi;
176   edge e;
177   edge_iterator ei;
178
179   bsi = bsi_last (bb);
180
181   /* If the duplicate ends with a control statement, then remove it.
182
183      Note that if we are duplicating the template block rather than the
184      original basic block, then the duplicate might not have any real
185      statements in it.  */
186   if (!bsi_end_p (bsi)
187       && bsi_stmt (bsi)
188       && (TREE_CODE (bsi_stmt (bsi)) == COND_EXPR
189           || TREE_CODE (bsi_stmt (bsi)) == GOTO_EXPR
190           || TREE_CODE (bsi_stmt (bsi)) == SWITCH_EXPR))
191     bsi_remove (&bsi, true);
192
193   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
194     {
195       if (e->dest != dest_bb)
196         remove_edge (e);
197       else
198         ei_next (&ei);
199     }
200 }
201
202 /* Create a duplicate of BB which only reaches the destination of the edge
203    stored in RD.  Record the duplicate block in RD.  */
204
205 static void
206 create_block_for_threading (basic_block bb, struct redirection_data *rd)
207 {
208   /* We can use the generic block duplication code and simply remove
209      the stuff we do not need.  */
210   rd->dup_block = duplicate_block (bb, NULL, NULL);
211
212   /* Zero out the profile, since the block is unreachable for now.  */
213   rd->dup_block->frequency = 0;
214   rd->dup_block->count = 0;
215
216   /* The call to duplicate_block will copy everything, including the
217      useless COND_EXPR or SWITCH_EXPR at the end of BB.  We just remove
218      the useless COND_EXPR or SWITCH_EXPR here rather than having a
219      specialized block copier.  We also remove all outgoing edges
220      from the duplicate block.  The appropriate edge will be created
221      later.  */
222   remove_ctrl_stmt_and_useless_edges (rd->dup_block, NULL);
223 }
224
225 /* Hashing and equality routines for our hash table.  */
226 static hashval_t
227 redirection_data_hash (const void *p)
228 {
229   edge e = ((struct redirection_data *)p)->outgoing_edge;
230   return e->dest->index;
231 }
232
233 static int
234 redirection_data_eq (const void *p1, const void *p2)
235 {
236   edge e1 = ((struct redirection_data *)p1)->outgoing_edge;
237   edge e2 = ((struct redirection_data *)p2)->outgoing_edge;
238
239   return e1 == e2;
240 }
241
242 /* Given an outgoing edge E lookup and return its entry in our hash table.
243
244    If INSERT is true, then we insert the entry into the hash table if
245    it is not already present.  INCOMING_EDGE is added to the list of incoming
246    edges associated with E in the hash table.  */
247
248 static struct redirection_data *
249 lookup_redirection_data (edge e, edge incoming_edge, enum insert_option insert)
250 {
251   void **slot;
252   struct redirection_data *elt;
253
254  /* Build a hash table element so we can see if E is already
255      in the table.  */
256   elt = XNEW (struct redirection_data);
257   elt->outgoing_edge = e;
258   elt->dup_block = NULL;
259   elt->do_not_duplicate = false;
260   elt->incoming_edges = NULL;
261
262   slot = htab_find_slot (redirection_data, elt, insert);
263
264   /* This will only happen if INSERT is false and the entry is not
265      in the hash table.  */
266   if (slot == NULL)
267     {
268       free (elt);
269       return NULL;
270     }
271
272   /* This will only happen if E was not in the hash table and
273      INSERT is true.  */
274   if (*slot == NULL)
275     {
276       *slot = (void *)elt;
277       elt->incoming_edges = XNEW (struct el);
278       elt->incoming_edges->e = incoming_edge;
279       elt->incoming_edges->next = NULL;
280       return elt;
281     }
282   /* E was in the hash table.  */
283   else
284     {
285       /* Free ELT as we do not need it anymore, we will extract the
286          relevant entry from the hash table itself.  */
287       free (elt);
288
289       /* Get the entry stored in the hash table.  */
290       elt = (struct redirection_data *) *slot;
291
292       /* If insertion was requested, then we need to add INCOMING_EDGE
293          to the list of incoming edges associated with E.  */
294       if (insert)
295         {
296           struct el *el = XNEW (struct el);
297           el->next = elt->incoming_edges;
298           el->e = incoming_edge;
299           elt->incoming_edges = el;
300         }
301
302       return elt;
303     }
304 }
305
306 /* Given a duplicate block and its single destination (both stored
307    in RD).  Create an edge between the duplicate and its single
308    destination.
309
310    Add an additional argument to any PHI nodes at the single
311    destination.  */
312
313 static void
314 create_edge_and_update_destination_phis (struct redirection_data *rd)
315 {
316   edge e = make_edge (rd->dup_block, rd->outgoing_edge->dest, EDGE_FALLTHRU);
317   tree phi;
318
319   e->probability = REG_BR_PROB_BASE;
320   e->count = rd->dup_block->count;
321
322   /* If there are any PHI nodes at the destination of the outgoing edge
323      from the duplicate block, then we will need to add a new argument
324      to them.  The argument should have the same value as the argument
325      associated with the outgoing edge stored in RD.  */
326   for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
327     {
328       int indx = rd->outgoing_edge->dest_idx;
329       add_phi_arg (phi, PHI_ARG_DEF (phi, indx), e);
330     }
331 }
332
333 /* Hash table traversal callback routine to create duplicate blocks.  */
334
335 static int
336 create_duplicates (void **slot, void *data)
337 {
338   struct redirection_data *rd = (struct redirection_data *) *slot;
339   struct local_info *local_info = (struct local_info *)data;
340
341   /* If this entry should not have a duplicate created, then there's
342      nothing to do.  */
343   if (rd->do_not_duplicate)
344     return 1;
345
346   /* Create a template block if we have not done so already.  Otherwise
347      use the template to create a new block.  */
348   if (local_info->template_block == NULL)
349     {
350       create_block_for_threading (local_info->bb, rd);
351       local_info->template_block = rd->dup_block;
352
353       /* We do not create any outgoing edges for the template.  We will
354          take care of that in a later traversal.  That way we do not
355          create edges that are going to just be deleted.  */
356     }
357   else
358     {
359       create_block_for_threading (local_info->template_block, rd);
360
361       /* Go ahead and wire up outgoing edges and update PHIs for the duplicate
362          block.  */
363       create_edge_and_update_destination_phis (rd);
364     }
365
366   /* Keep walking the hash table.  */
367   return 1;
368 }
369
370 /* We did not create any outgoing edges for the template block during
371    block creation.  This hash table traversal callback creates the
372    outgoing edge for the template block.  */
373
374 static int
375 fixup_template_block (void **slot, void *data)
376 {
377   struct redirection_data *rd = (struct redirection_data *) *slot;
378   struct local_info *local_info = (struct local_info *)data;
379
380   /* If this is the template block, then create its outgoing edges
381      and halt the hash table traversal.  */
382   if (rd->dup_block && rd->dup_block == local_info->template_block)
383     {
384       create_edge_and_update_destination_phis (rd);
385       return 0;
386     }
387
388   return 1;
389 }
390
391 /* Not all jump threading requests are useful.  In particular some
392    jump threading requests can create irreducible regions which are
393    undesirable.
394
395    This routine will examine the BB's incoming edges for jump threading
396    requests which, if acted upon, would create irreducible regions.  Any
397    such jump threading requests found will be pruned away.  */
398
399 static void
400 prune_undesirable_thread_requests (basic_block bb)
401 {
402   edge e;
403   edge_iterator ei;
404   bool may_create_irreducible_region = false;
405   unsigned int num_outgoing_edges_into_loop = 0;
406
407   /* For the heuristics below, we need to know if BB has more than
408      one outgoing edge into a loop.  */
409   FOR_EACH_EDGE (e, ei, bb->succs)
410     num_outgoing_edges_into_loop += ((e->flags & EDGE_LOOP_EXIT) == 0);
411
412   if (num_outgoing_edges_into_loop > 1)
413     {
414       edge backedge = NULL;
415
416       /* Consider the effect of threading the edge (0, 1) to 2 on the left
417          CFG to produce the right CFG:
418     
419
420              0            0
421              |            |
422              1<--+        2<--------+
423             / \  |        |         |
424            2   3 |        4<----+   |
425             \ /  |       / \    |   |
426              4---+      E   1-- | --+
427              |              |   |
428              E              3---+
429
430
431         Threading the (0, 1) edge to 2 effectively creates two loops
432         (2, 4, 1) and (4, 1, 3) which are neither disjoint nor nested.
433         This is not good.
434
435         However, we do need to be able to thread  (0, 1) to 2 or 3
436         in the left CFG below (which creates the middle and right
437         CFGs with nested loops).
438
439              0          0             0
440              |          |             |
441              1<--+      2<----+       3<-+<-+
442             /|   |      |     |       |  |  |
443            2 |   |      3<-+  |       1--+  |
444             \|   |      |  |  |       |     |
445              3---+      1--+--+       2-----+
446
447          
448          A safe heuristic appears to be to only allow threading if BB
449          has a single incoming backedge from one of its direct successors.  */
450
451       FOR_EACH_EDGE (e, ei, bb->preds)
452         {
453           if (e->flags & EDGE_DFS_BACK)
454             {
455               if (backedge)
456                 {
457                   backedge = NULL;
458                   break;
459                 }
460               else
461                 {
462                   backedge = e;
463                 }
464             }
465         }
466
467       if (backedge && find_edge (bb, backedge->src))
468         ;
469       else
470         may_create_irreducible_region = true;
471     }
472   else
473     {
474       edge dest = NULL;
475
476       /* If we thread across the loop entry block (BB) into the
477          loop and BB is still reached from outside the loop, then
478          we would create an irreducible CFG.  Consider the effect
479          of threading the edge (1, 4) to 5 on the left CFG to produce
480          the right CFG
481
482              0               0
483             / \             / \
484            1   2           1   2
485             \ /            |   |
486              4<----+       5<->4
487             / \    |           |
488            E   5---+           E
489
490
491          Threading the (1, 4) edge to 5 creates two entry points
492          into the loop (4, 5) (one from block 1, the other from
493          block 2).  A classic irreducible region. 
494
495          So look at all of BB's incoming edges which are not
496          backedges and which are not threaded to the loop exit.
497          If that subset of incoming edges do not all thread
498          to the same block, then threading any of them will create
499          an irreducible region.  */
500
501       FOR_EACH_EDGE (e, ei, bb->preds)
502         {
503           edge e2;
504
505           /* We ignore back edges for now.  This may need refinement
506              as threading a backedge creates an inner loop which
507              we would need to verify has a single entry point. 
508
509              If all backedges thread to new locations, then this
510              block will no longer have incoming backedges and we
511              need not worry about creating irreducible regions
512              by threading through BB.  I don't think this happens
513              enough in practice to worry about it.  */
514           if (e->flags & EDGE_DFS_BACK)
515             continue;
516
517           /* If the incoming edge threads to the loop exit, then it
518              is clearly safe.  */
519           e2 = e->aux;
520           if (e2 && (e2->flags & EDGE_LOOP_EXIT))
521             continue;
522
523           /* E enters the loop header and is not threaded.  We can
524              not allow any other incoming edges to thread into
525              the loop as that would create an irreducible region.  */
526           if (!e2)
527             {
528               may_create_irreducible_region = true;
529               break;
530             }
531
532           /* We know that this incoming edge threads to a block inside
533              the loop.  This edge must thread to the same target in
534              the loop as any previously seen threaded edges.  Otherwise
535              we will create an irreducible region.  */
536           if (!dest)
537             dest = e2;
538           else if (e2 != dest)
539             {
540               may_create_irreducible_region = true;
541               break;
542             }
543         }
544     }
545
546   /* If we might create an irreducible region, then cancel any of
547      the jump threading requests for incoming edges which are
548      not backedges and which do not thread to the exit block.  */
549   if (may_create_irreducible_region)
550     {
551       FOR_EACH_EDGE (e, ei, bb->preds)
552         {
553           edge e2;
554
555           /* Ignore back edges.  */
556           if (e->flags & EDGE_DFS_BACK)
557             continue;
558
559           e2 = e->aux;
560
561           /* If this incoming edge was not threaded, then there is
562              nothing to do.  */
563           if (!e2)
564             continue;
565
566           /* If this incoming edge threaded to the loop exit,
567              then it can be ignored as it is safe.  */
568           if (e2->flags & EDGE_LOOP_EXIT)
569             continue;
570
571           if (e2)
572             {
573               /* This edge threaded into the loop and the jump thread
574                  request must be cancelled.  */
575               if (dump_file && (dump_flags & TDF_DETAILS))
576                 fprintf (dump_file, "  Not threading jump %d --> %d to %d\n",
577                          e->src->index, e->dest->index, e2->dest->index);
578               e->aux = NULL;
579             }
580         }
581     }
582 }
583
584 /* Hash table traversal callback to redirect each incoming edge
585    associated with this hash table element to its new destination.  */
586
587 static int
588 redirect_edges (void **slot, void *data)
589 {
590   struct redirection_data *rd = (struct redirection_data *) *slot;
591   struct local_info *local_info = (struct local_info *)data;
592   struct el *next, *el;
593
594   /* Walk over all the incoming edges associated associated with this
595      hash table entry.  */
596   for (el = rd->incoming_edges; el; el = next)
597     {
598       edge e = el->e;
599
600       /* Go ahead and free this element from the list.  Doing this now
601          avoids the need for another list walk when we destroy the hash
602          table.  */
603       next = el->next;
604       free (el);
605
606       /* Go ahead and clear E->aux.  It's not needed anymore and failure
607          to clear it will cause all kinds of unpleasant problems later.  */
608       e->aux = NULL;
609
610       thread_stats.num_threaded_edges++;
611
612       if (rd->dup_block)
613         {
614           edge e2;
615
616           if (dump_file && (dump_flags & TDF_DETAILS))
617             fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
618                      e->src->index, e->dest->index, rd->dup_block->index);
619
620           rd->dup_block->count += e->count;
621           rd->dup_block->frequency += EDGE_FREQUENCY (e);
622           EDGE_SUCC (rd->dup_block, 0)->count += e->count;
623           /* Redirect the incoming edge to the appropriate duplicate
624              block.  */
625           e2 = redirect_edge_and_branch (e, rd->dup_block);
626           flush_pending_stmts (e2);
627
628           if ((dump_file && (dump_flags & TDF_DETAILS))
629               && e->src != e2->src)
630             fprintf (dump_file, "    basic block %d created\n", e2->src->index);
631         }
632       else
633         {
634           if (dump_file && (dump_flags & TDF_DETAILS))
635             fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
636                      e->src->index, e->dest->index, local_info->bb->index);
637
638           /* We are using BB as the duplicate.  Remove the unnecessary
639              outgoing edges and statements from BB.  */
640           remove_ctrl_stmt_and_useless_edges (local_info->bb,
641                                               rd->outgoing_edge->dest);
642
643           /* And fixup the flags on the single remaining edge.  */
644           single_succ_edge (local_info->bb)->flags
645             &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL);
646           single_succ_edge (local_info->bb)->flags |= EDGE_FALLTHRU;
647         }
648     }
649
650   /* Indicate that we actually threaded one or more jumps.  */
651   if (rd->incoming_edges)
652     local_info->jumps_threaded = true;
653
654   return 1;
655 }
656
657 /* BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB
658    is reached via one or more specific incoming edges, we know which
659    outgoing edge from BB will be traversed.
660
661    We want to redirect those incoming edges to the target of the
662    appropriate outgoing edge.  Doing so avoids a conditional branch
663    and may expose new optimization opportunities.  Note that we have
664    to update dominator tree and SSA graph after such changes.
665
666    The key to keeping the SSA graph update manageable is to duplicate
667    the side effects occurring in BB so that those side effects still
668    occur on the paths which bypass BB after redirecting edges.
669
670    We accomplish this by creating duplicates of BB and arranging for
671    the duplicates to unconditionally pass control to one specific
672    successor of BB.  We then revector the incoming edges into BB to
673    the appropriate duplicate of BB.
674
675    BB and its duplicates will have assignments to the same set of
676    SSA_NAMEs.  Right now, we just call into update_ssa to update the
677    SSA graph for those names.
678
679    We are also going to experiment with a true incremental update
680    scheme for the duplicated resources.  One of the interesting
681    properties we can exploit here is that all the resources set
682    in BB will have the same IDFS, so we have one IDFS computation
683    per block with incoming threaded edges, which can lower the
684    cost of the true incremental update algorithm.  */
685
686 static bool
687 thread_block (basic_block bb)
688 {
689   /* E is an incoming edge into BB that we may or may not want to
690      redirect to a duplicate of BB.  */
691   edge e;
692   edge_iterator ei;
693   struct local_info local_info;
694
695   /* FOUND_BACKEDGE indicates that we found an incoming backedge
696      into BB, in which case we may ignore certain jump threads
697      to avoid creating irreducible regions.  */
698   bool found_backedge = false;
699
700   /* ALL indicates whether or not all incoming edges into BB should
701      be threaded to a duplicate of BB.  */
702   bool all = true;
703
704   /* To avoid scanning a linear array for the element we need we instead
705      use a hash table.  For normal code there should be no noticeable
706      difference.  However, if we have a block with a large number of
707      incoming and outgoing edges such linear searches can get expensive.  */
708   redirection_data = htab_create (EDGE_COUNT (bb->succs),
709                                   redirection_data_hash,
710                                   redirection_data_eq,
711                                   free);
712
713   FOR_EACH_EDGE (e, ei, bb->preds)
714     found_backedge |= ((e->flags & EDGE_DFS_BACK) != 0);
715
716   /* If BB has incoming backedges, then threading across BB might
717      introduce an irreducible region, which would be undesirable
718      as that inhibits various optimizations later.  Prune away
719      any jump threading requests which we know will result in
720      an irreducible region.  */
721   if (found_backedge)
722     prune_undesirable_thread_requests (bb);
723
724   /* Record each unique threaded destination into a hash table for
725      efficient lookups.  */
726   FOR_EACH_EDGE (e, ei, bb->preds)
727     {
728       if (!e->aux)
729         {
730           all = false;
731         }
732       else
733         {
734           edge e2 = e->aux;
735           update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e),
736                                            e->count, e->aux);
737
738           /* If we thread to a loop exit edge, then we will need to 
739              rediscover the loop exit edges.  While it may seem that
740              the new edge is a loop exit edge, that is not the case.
741              Consider threading the edge (5,6) to E in the CFG on the
742              left which creates the CFG on the right:
743
744
745                       0<--+            0<---+
746                      / \  |           / \   |
747                     1   2 |          1   2  |
748                    / \  | |         / \  |  |
749                   3   4 | |        3   4 6--+
750                    \ /  | |         \ /
751                     5   | |          5
752                      \ /  |          |
753                       6---+          E
754                       |
755                       E
756
757              After threading, the edge (0, 1)  is the loop exit edge and
758              the nodes 0, 2, 6 are the only nodes in the loop.  */
759           if (e2->flags & EDGE_LOOP_EXIT)
760             rediscover_loops_after_threading = true;
761
762           /* Insert the outgoing edge into the hash table if it is not
763              already in the hash table.  */
764           lookup_redirection_data (e2, e, INSERT);
765         }
766     }
767
768   /* If we are going to thread all incoming edges to an outgoing edge, then
769      BB will become unreachable.  Rather than just throwing it away, use
770      it for one of the duplicates.  Mark the first incoming edge with the
771      DO_NOT_DUPLICATE attribute.  */
772   if (all)
773     {
774       edge e = EDGE_PRED (bb, 0)->aux;
775       lookup_redirection_data (e, NULL, NO_INSERT)->do_not_duplicate = true;
776     }
777
778   /* Now create duplicates of BB.
779
780      Note that for a block with a high outgoing degree we can waste
781      a lot of time and memory creating and destroying useless edges.
782
783      So we first duplicate BB and remove the control structure at the
784      tail of the duplicate as well as all outgoing edges from the
785      duplicate.  We then use that duplicate block as a template for
786      the rest of the duplicates.  */
787   local_info.template_block = NULL;
788   local_info.bb = bb;
789   local_info.jumps_threaded = false;
790   htab_traverse (redirection_data, create_duplicates, &local_info);
791
792   /* The template does not have an outgoing edge.  Create that outgoing
793      edge and update PHI nodes as the edge's target as necessary.
794
795      We do this after creating all the duplicates to avoid creating
796      unnecessary edges.  */
797   htab_traverse (redirection_data, fixup_template_block, &local_info);
798
799   /* The hash table traversals above created the duplicate blocks (and the
800      statements within the duplicate blocks).  This loop creates PHI nodes for
801      the duplicated blocks and redirects the incoming edges into BB to reach
802      the duplicates of BB.  */
803   htab_traverse (redirection_data, redirect_edges, &local_info);
804
805   /* Done with this block.  Clear REDIRECTION_DATA.  */
806   htab_delete (redirection_data);
807   redirection_data = NULL;
808
809   /* Indicate to our caller whether or not any jumps were threaded.  */
810   return local_info.jumps_threaded;
811 }
812
813 /* Walk through the registered jump threads and convert them into a
814    form convenient for this pass.
815
816    Any block which has incoming edges threaded to outgoing edges
817    will have its entry in THREADED_BLOCK set.
818
819    Any threaded edge will have its new outgoing edge stored in the
820    original edge's AUX field.
821
822    This form avoids the need to walk all the edges in the CFG to
823    discover blocks which need processing and avoids unnecessary
824    hash table lookups to map from threaded edge to new target.  */
825
826 static void
827 mark_threaded_blocks (bitmap threaded_blocks)
828 {
829   unsigned int i;
830
831   for (i = 0; i < VEC_length (edge, threaded_edges); i += 2)
832     {
833       edge e = VEC_index (edge, threaded_edges, i);
834       edge e2 = VEC_index (edge, threaded_edges, i + 1);
835
836       e->aux = e2;
837       bitmap_set_bit (threaded_blocks, e->dest->index);
838     }
839 }
840
841
842 /* Walk through all blocks and thread incoming edges to the appropriate
843    outgoing edge for each edge pair recorded in THREADED_EDGES.
844
845    It is the caller's responsibility to fix the dominance information
846    and rewrite duplicated SSA_NAMEs back into SSA form.
847
848    Returns true if one or more edges were threaded, false otherwise.  */
849
850 bool
851 thread_through_all_blocks (void)
852 {
853   bool retval = false;
854   unsigned int i;
855   bitmap_iterator bi;
856   bitmap threaded_blocks;
857
858   if (threaded_edges == NULL)
859     return false;
860
861   threaded_blocks = BITMAP_ALLOC (NULL);
862   rediscover_loops_after_threading = false;
863   memset (&thread_stats, 0, sizeof (thread_stats));
864
865   mark_threaded_blocks (threaded_blocks);
866
867   EXECUTE_IF_SET_IN_BITMAP (threaded_blocks, 0, i, bi)
868     {
869       basic_block bb = BASIC_BLOCK (i);
870
871       if (EDGE_COUNT (bb->preds) > 0)
872         retval |= thread_block (bb);
873     }
874
875   if (dump_file && (dump_flags & TDF_STATS))
876     fprintf (dump_file, "\nJumps threaded: %lu\n",
877              thread_stats.num_threaded_edges);
878
879   BITMAP_FREE (threaded_blocks);
880   threaded_blocks = NULL;
881   VEC_free (edge, heap, threaded_edges);
882   threaded_edges = NULL;
883   return retval;
884 }
885
886 /* Register a jump threading opportunity.  We queue up all the jump
887    threading opportunities discovered by a pass and update the CFG
888    and SSA form all at once.
889
890    E is the edge we can thread, E2 is the new target edge.  ie, we
891    are effectively recording that E->dest can be changed to E2->dest
892    after fixing the SSA graph.  */
893
894 void
895 register_jump_thread (edge e, edge e2)
896 {
897   if (threaded_edges == NULL)
898     threaded_edges = VEC_alloc (edge, heap, 10);
899
900   VEC_safe_push (edge, heap, threaded_edges, e);
901   VEC_safe_push (edge, heap, threaded_edges, e2);
902 }