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