stor-layout.c (finish_builtin_struct): Copy fields into the variants.
[gcc.git] / gcc / tree-ssa-threadupdate.c
1 /* Thread edges through blocks and update the control flow and SSA graphs.
2 Copyright (C) 2004-2014 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 "tree.h"
24 #include "flags.h"
25 #include "basic-block.h"
26 #include "function.h"
27 #include "hash-table.h"
28 #include "tree-ssa-alias.h"
29 #include "internal-fn.h"
30 #include "gimple-expr.h"
31 #include "is-a.h"
32 #include "gimple.h"
33 #include "gimple-iterator.h"
34 #include "gimple-ssa.h"
35 #include "tree-phinodes.h"
36 #include "tree-ssa.h"
37 #include "tree-ssa-threadupdate.h"
38 #include "ssa-iterators.h"
39 #include "dumpfile.h"
40 #include "cfgloop.h"
41 #include "dbgcnt.h"
42 #include "tree-cfg.h"
43 #include "tree-pass.h"
44
45 /* Given a block B, update the CFG and SSA graph to reflect redirecting
46 one or more in-edges to B to instead reach the destination of an
47 out-edge from B while preserving any side effects in B.
48
49 i.e., given A->B and B->C, change A->B to be A->C yet still preserve the
50 side effects of executing B.
51
52 1. Make a copy of B (including its outgoing edges and statements). Call
53 the copy B'. Note B' has no incoming edges or PHIs at this time.
54
55 2. Remove the control statement at the end of B' and all outgoing edges
56 except B'->C.
57
58 3. Add a new argument to each PHI in C with the same value as the existing
59 argument associated with edge B->C. Associate the new PHI arguments
60 with the edge B'->C.
61
62 4. For each PHI in B, find or create a PHI in B' with an identical
63 PHI_RESULT. Add an argument to the PHI in B' which has the same
64 value as the PHI in B associated with the edge A->B. Associate
65 the new argument in the PHI in B' with the edge A->B.
66
67 5. Change the edge A->B to A->B'.
68
69 5a. This automatically deletes any PHI arguments associated with the
70 edge A->B in B.
71
72 5b. This automatically associates each new argument added in step 4
73 with the edge A->B'.
74
75 6. Repeat for other incoming edges into B.
76
77 7. Put the duplicated resources in B and all the B' blocks into SSA form.
78
79 Note that block duplication can be minimized by first collecting the
80 set of unique destination blocks that the incoming edges should
81 be threaded to.
82
83 We reduce the number of edges and statements we create by not copying all
84 the outgoing edges and the control statement in step #1. We instead create
85 a template block without the outgoing edges and duplicate the template.
86
87 Another case this code handles is threading through a "joiner" block. In
88 this case, we do not know the destination of the joiner block, but one
89 of the outgoing edges from the joiner block leads to a threadable path. This
90 case largely works as outlined above, except the duplicate of the joiner
91 block still contains a full set of outgoing edges and its control statement.
92 We just redirect one of its outgoing edges to our jump threading path. */
93
94
95 /* Steps #5 and #6 of the above algorithm are best implemented by walking
96 all the incoming edges which thread to the same destination edge at
97 the same time. That avoids lots of table lookups to get information
98 for the destination edge.
99
100 To realize that implementation we create a list of incoming edges
101 which thread to the same outgoing edge. Thus to implement steps
102 #5 and #6 we traverse our hash table of outgoing edge information.
103 For each entry we walk the list of incoming edges which thread to
104 the current outgoing edge. */
105
106 struct el
107 {
108 edge e;
109 struct el *next;
110 };
111
112 /* Main data structure recording information regarding B's duplicate
113 blocks. */
114
115 /* We need to efficiently record the unique thread destinations of this
116 block and specific information associated with those destinations. We
117 may have many incoming edges threaded to the same outgoing edge. This
118 can be naturally implemented with a hash table. */
119
120 struct redirection_data : typed_free_remove<redirection_data>
121 {
122 /* We support wiring up two block duplicates in a jump threading path.
123
124 One is a normal block copy where we remove the control statement
125 and wire up its single remaining outgoing edge to the thread path.
126
127 The other is a joiner block where we leave the control statement
128 in place, but wire one of the outgoing edges to a thread path.
129
130 In theory we could have multiple block duplicates in a jump
131 threading path, but I haven't tried that.
132
133 The duplicate blocks appear in this array in the same order in
134 which they appear in the jump thread path. */
135 basic_block dup_blocks[2];
136
137 /* The jump threading path. */
138 vec<jump_thread_edge *> *path;
139
140 /* A list of incoming edges which we want to thread to the
141 same path. */
142 struct el *incoming_edges;
143
144 /* hash_table support. */
145 typedef redirection_data value_type;
146 typedef redirection_data compare_type;
147 static inline hashval_t hash (const value_type *);
148 static inline int equal (const value_type *, const compare_type *);
149 };
150
151 /* Dump a jump threading path, including annotations about each
152 edge in the path. */
153
154 static void
155 dump_jump_thread_path (FILE *dump_file, vec<jump_thread_edge *> path,
156 bool registering)
157 {
158 fprintf (dump_file,
159 " %s jump thread: (%d, %d) incoming edge; ",
160 (registering ? "Registering" : "Cancelling"),
161 path[0]->e->src->index, path[0]->e->dest->index);
162
163 for (unsigned int i = 1; i < path.length (); i++)
164 {
165 /* We can get paths with a NULL edge when the final destination
166 of a jump thread turns out to be a constant address. We dump
167 those paths when debugging, so we have to be prepared for that
168 possibility here. */
169 if (path[i]->e == NULL)
170 continue;
171
172 if (path[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
173 fprintf (dump_file, " (%d, %d) joiner; ",
174 path[i]->e->src->index, path[i]->e->dest->index);
175 if (path[i]->type == EDGE_COPY_SRC_BLOCK)
176 fprintf (dump_file, " (%d, %d) normal;",
177 path[i]->e->src->index, path[i]->e->dest->index);
178 if (path[i]->type == EDGE_NO_COPY_SRC_BLOCK)
179 fprintf (dump_file, " (%d, %d) nocopy;",
180 path[i]->e->src->index, path[i]->e->dest->index);
181 }
182 fputc ('\n', dump_file);
183 }
184
185 /* Simple hashing function. For any given incoming edge E, we're going
186 to be most concerned with the final destination of its jump thread
187 path. So hash on the block index of the final edge in the path. */
188
189 inline hashval_t
190 redirection_data::hash (const value_type *p)
191 {
192 vec<jump_thread_edge *> *path = p->path;
193 return path->last ()->e->dest->index;
194 }
195
196 /* Given two hash table entries, return true if they have the same
197 jump threading path. */
198 inline int
199 redirection_data::equal (const value_type *p1, const compare_type *p2)
200 {
201 vec<jump_thread_edge *> *path1 = p1->path;
202 vec<jump_thread_edge *> *path2 = p2->path;
203
204 if (path1->length () != path2->length ())
205 return false;
206
207 for (unsigned int i = 1; i < path1->length (); i++)
208 {
209 if ((*path1)[i]->type != (*path2)[i]->type
210 || (*path1)[i]->e != (*path2)[i]->e)
211 return false;
212 }
213
214 return true;
215 }
216
217 /* Data structure of information to pass to hash table traversal routines. */
218 struct ssa_local_info_t
219 {
220 /* The current block we are working on. */
221 basic_block bb;
222
223 /* We only create a template block for the first duplicated block in a
224 jump threading path as we may need many duplicates of that block.
225
226 The second duplicate block in a path is specific to that path. Creating
227 and sharing a template for that block is considerably more difficult. */
228 basic_block template_block;
229
230 /* TRUE if we thread one or more jumps, FALSE otherwise. */
231 bool jumps_threaded;
232 };
233
234 /* Passes which use the jump threading code register jump threading
235 opportunities as they are discovered. We keep the registered
236 jump threading opportunities in this vector as edge pairs
237 (original_edge, target_edge). */
238 static vec<vec<jump_thread_edge *> *> paths;
239
240 /* When we start updating the CFG for threading, data necessary for jump
241 threading is attached to the AUX field for the incoming edge. Use these
242 macros to access the underlying structure attached to the AUX field. */
243 #define THREAD_PATH(E) ((vec<jump_thread_edge *> *)(E)->aux)
244
245 /* Jump threading statistics. */
246
247 struct thread_stats_d
248 {
249 unsigned long num_threaded_edges;
250 };
251
252 struct thread_stats_d thread_stats;
253
254
255 /* Remove the last statement in block BB if it is a control statement
256 Also remove all outgoing edges except the edge which reaches DEST_BB.
257 If DEST_BB is NULL, then remove all outgoing edges. */
258
259 static void
260 remove_ctrl_stmt_and_useless_edges (basic_block bb, basic_block dest_bb)
261 {
262 gimple_stmt_iterator gsi;
263 edge e;
264 edge_iterator ei;
265
266 gsi = gsi_last_bb (bb);
267
268 /* If the duplicate ends with a control statement, then remove it.
269
270 Note that if we are duplicating the template block rather than the
271 original basic block, then the duplicate might not have any real
272 statements in it. */
273 if (!gsi_end_p (gsi)
274 && gsi_stmt (gsi)
275 && (gimple_code (gsi_stmt (gsi)) == GIMPLE_COND
276 || gimple_code (gsi_stmt (gsi)) == GIMPLE_GOTO
277 || gimple_code (gsi_stmt (gsi)) == GIMPLE_SWITCH))
278 gsi_remove (&gsi, true);
279
280 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
281 {
282 if (e->dest != dest_bb)
283 remove_edge (e);
284 else
285 ei_next (&ei);
286 }
287 }
288
289 /* Create a duplicate of BB. Record the duplicate block in an array
290 indexed by COUNT stored in RD. */
291
292 static void
293 create_block_for_threading (basic_block bb,
294 struct redirection_data *rd,
295 unsigned int count)
296 {
297 edge_iterator ei;
298 edge e;
299
300 /* We can use the generic block duplication code and simply remove
301 the stuff we do not need. */
302 rd->dup_blocks[count] = duplicate_block (bb, NULL, NULL);
303
304 FOR_EACH_EDGE (e, ei, rd->dup_blocks[count]->succs)
305 e->aux = NULL;
306
307 /* Zero out the profile, since the block is unreachable for now. */
308 rd->dup_blocks[count]->frequency = 0;
309 rd->dup_blocks[count]->count = 0;
310 }
311
312 /* Main data structure to hold information for duplicates of BB. */
313
314 static hash_table<redirection_data> *redirection_data;
315
316 /* Given an outgoing edge E lookup and return its entry in our hash table.
317
318 If INSERT is true, then we insert the entry into the hash table if
319 it is not already present. INCOMING_EDGE is added to the list of incoming
320 edges associated with E in the hash table. */
321
322 static struct redirection_data *
323 lookup_redirection_data (edge e, enum insert_option insert)
324 {
325 struct redirection_data **slot;
326 struct redirection_data *elt;
327 vec<jump_thread_edge *> *path = THREAD_PATH (e);
328
329 /* Build a hash table element so we can see if E is already
330 in the table. */
331 elt = XNEW (struct redirection_data);
332 elt->path = path;
333 elt->dup_blocks[0] = NULL;
334 elt->dup_blocks[1] = NULL;
335 elt->incoming_edges = NULL;
336
337 slot = redirection_data->find_slot (elt, insert);
338
339 /* This will only happen if INSERT is false and the entry is not
340 in the hash table. */
341 if (slot == NULL)
342 {
343 free (elt);
344 return NULL;
345 }
346
347 /* This will only happen if E was not in the hash table and
348 INSERT is true. */
349 if (*slot == NULL)
350 {
351 *slot = elt;
352 elt->incoming_edges = XNEW (struct el);
353 elt->incoming_edges->e = e;
354 elt->incoming_edges->next = NULL;
355 return elt;
356 }
357 /* E was in the hash table. */
358 else
359 {
360 /* Free ELT as we do not need it anymore, we will extract the
361 relevant entry from the hash table itself. */
362 free (elt);
363
364 /* Get the entry stored in the hash table. */
365 elt = *slot;
366
367 /* If insertion was requested, then we need to add INCOMING_EDGE
368 to the list of incoming edges associated with E. */
369 if (insert)
370 {
371 struct el *el = XNEW (struct el);
372 el->next = elt->incoming_edges;
373 el->e = e;
374 elt->incoming_edges = el;
375 }
376
377 return elt;
378 }
379 }
380
381 /* Similar to copy_phi_args, except that the PHI arg exists, it just
382 does not have a value associated with it. */
383
384 static void
385 copy_phi_arg_into_existing_phi (edge src_e, edge tgt_e)
386 {
387 int src_idx = src_e->dest_idx;
388 int tgt_idx = tgt_e->dest_idx;
389
390 /* Iterate over each PHI in e->dest. */
391 for (gimple_stmt_iterator gsi = gsi_start_phis (src_e->dest),
392 gsi2 = gsi_start_phis (tgt_e->dest);
393 !gsi_end_p (gsi);
394 gsi_next (&gsi), gsi_next (&gsi2))
395 {
396 gimple src_phi = gsi_stmt (gsi);
397 gimple dest_phi = gsi_stmt (gsi2);
398 tree val = gimple_phi_arg_def (src_phi, src_idx);
399 source_location locus = gimple_phi_arg_location (src_phi, src_idx);
400
401 SET_PHI_ARG_DEF (dest_phi, tgt_idx, val);
402 gimple_phi_arg_set_location (dest_phi, tgt_idx, locus);
403 }
404 }
405
406 /* Given ssa_name DEF, backtrack jump threading PATH from node IDX
407 to see if it has constant value in a flow sensitive manner. Set
408 LOCUS to location of the constant phi arg and return the value.
409 Return DEF directly if either PATH or idx is ZERO. */
410
411 static tree
412 get_value_locus_in_path (tree def, vec<jump_thread_edge *> *path,
413 basic_block bb, int idx, source_location *locus)
414 {
415 tree arg;
416 gimple def_phi;
417 basic_block def_bb;
418
419 if (path == NULL || idx == 0)
420 return def;
421
422 def_phi = SSA_NAME_DEF_STMT (def);
423 if (gimple_code (def_phi) != GIMPLE_PHI)
424 return def;
425
426 def_bb = gimple_bb (def_phi);
427 /* Don't propagate loop invariants into deeper loops. */
428 if (!def_bb || bb_loop_depth (def_bb) < bb_loop_depth (bb))
429 return def;
430
431 /* Backtrack jump threading path from IDX to see if def has constant
432 value. */
433 for (int j = idx - 1; j >= 0; j--)
434 {
435 edge e = (*path)[j]->e;
436 if (e->dest == def_bb)
437 {
438 arg = gimple_phi_arg_def (def_phi, e->dest_idx);
439 if (is_gimple_min_invariant (arg))
440 {
441 *locus = gimple_phi_arg_location (def_phi, e->dest_idx);
442 return arg;
443 }
444 break;
445 }
446 }
447
448 return def;
449 }
450
451 /* For each PHI in BB, copy the argument associated with SRC_E to TGT_E.
452 Try to backtrack jump threading PATH from node IDX to see if the arg
453 has constant value, copy constant value instead of argument itself
454 if yes. */
455
456 static void
457 copy_phi_args (basic_block bb, edge src_e, edge tgt_e,
458 vec<jump_thread_edge *> *path, int idx)
459 {
460 gimple_stmt_iterator gsi;
461 int src_indx = src_e->dest_idx;
462
463 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
464 {
465 gimple phi = gsi_stmt (gsi);
466 tree def = gimple_phi_arg_def (phi, src_indx);
467 source_location locus = gimple_phi_arg_location (phi, src_indx);
468
469 if (TREE_CODE (def) == SSA_NAME
470 && !virtual_operand_p (gimple_phi_result (phi)))
471 def = get_value_locus_in_path (def, path, bb, idx, &locus);
472
473 add_phi_arg (phi, def, tgt_e, locus);
474 }
475 }
476
477 /* We have recently made a copy of ORIG_BB, including its outgoing
478 edges. The copy is NEW_BB. Every PHI node in every direct successor of
479 ORIG_BB has a new argument associated with edge from NEW_BB to the
480 successor. Initialize the PHI argument so that it is equal to the PHI
481 argument associated with the edge from ORIG_BB to the successor.
482 PATH and IDX are used to check if the new PHI argument has constant
483 value in a flow sensitive manner. */
484
485 static void
486 update_destination_phis (basic_block orig_bb, basic_block new_bb,
487 vec<jump_thread_edge *> *path, int idx)
488 {
489 edge_iterator ei;
490 edge e;
491
492 FOR_EACH_EDGE (e, ei, orig_bb->succs)
493 {
494 edge e2 = find_edge (new_bb, e->dest);
495 copy_phi_args (e->dest, e, e2, path, idx);
496 }
497 }
498
499 /* Given a duplicate block and its single destination (both stored
500 in RD). Create an edge between the duplicate and its single
501 destination.
502
503 Add an additional argument to any PHI nodes at the single
504 destination. IDX is the start node in jump threading path
505 we start to check to see if the new PHI argument has constant
506 value along the jump threading path. */
507
508 static void
509 create_edge_and_update_destination_phis (struct redirection_data *rd,
510 basic_block bb, int idx)
511 {
512 edge e = make_edge (bb, rd->path->last ()->e->dest, EDGE_FALLTHRU);
513
514 rescan_loop_exit (e, true, false);
515 e->probability = REG_BR_PROB_BASE;
516 e->count = bb->count;
517
518 /* We used to copy the thread path here. That was added in 2007
519 and dutifully updated through the representation changes in 2013.
520
521 In 2013 we added code to thread from an interior node through
522 the backedge to another interior node. That runs after the code
523 to thread through loop headers from outside the loop.
524
525 The latter may delete edges in the CFG, including those
526 which appeared in the jump threading path we copied here. Thus
527 we'd end up using a dangling pointer.
528
529 After reviewing the 2007/2011 code, I can't see how anything
530 depended on copying the AUX field and clearly copying the jump
531 threading path is problematical due to embedded edge pointers.
532 It has been removed. */
533 e->aux = NULL;
534
535 /* If there are any PHI nodes at the destination of the outgoing edge
536 from the duplicate block, then we will need to add a new argument
537 to them. The argument should have the same value as the argument
538 associated with the outgoing edge stored in RD. */
539 copy_phi_args (e->dest, rd->path->last ()->e, e, rd->path, idx);
540 }
541
542 /* Look through PATH beginning at START and return TRUE if there are
543 any additional blocks that need to be duplicated. Otherwise,
544 return FALSE. */
545 static bool
546 any_remaining_duplicated_blocks (vec<jump_thread_edge *> *path,
547 unsigned int start)
548 {
549 for (unsigned int i = start + 1; i < path->length (); i++)
550 {
551 if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK
552 || (*path)[i]->type == EDGE_COPY_SRC_BLOCK)
553 return true;
554 }
555 return false;
556 }
557
558 /* Wire up the outgoing edges from the duplicate blocks and
559 update any PHIs as needed. */
560 void
561 ssa_fix_duplicate_block_edges (struct redirection_data *rd,
562 ssa_local_info_t *local_info)
563 {
564 bool multi_incomings = (rd->incoming_edges->next != NULL);
565 edge e = rd->incoming_edges->e;
566 vec<jump_thread_edge *> *path = THREAD_PATH (e);
567
568 for (unsigned int count = 0, i = 1; i < path->length (); i++)
569 {
570 /* If we were threading through an joiner block, then we want
571 to keep its control statement and redirect an outgoing edge.
572 Else we want to remove the control statement & edges, then create
573 a new outgoing edge. In both cases we may need to update PHIs. */
574 if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
575 {
576 edge victim;
577 edge e2;
578
579 /* This updates the PHIs at the destination of the duplicate
580 block. Pass 0 instead of i if we are threading a path which
581 has multiple incoming edges. */
582 update_destination_phis (local_info->bb, rd->dup_blocks[count],
583 path, multi_incomings ? 0 : i);
584
585 /* Find the edge from the duplicate block to the block we're
586 threading through. That's the edge we want to redirect. */
587 victim = find_edge (rd->dup_blocks[count], (*path)[i]->e->dest);
588
589 /* If there are no remaining blocks on the path to duplicate,
590 then redirect VICTIM to the final destination of the jump
591 threading path. */
592 if (!any_remaining_duplicated_blocks (path, i))
593 {
594 e2 = redirect_edge_and_branch (victim, path->last ()->e->dest);
595 e2->count = path->last ()->e->count;
596 /* If we redirected the edge, then we need to copy PHI arguments
597 at the target. If the edge already existed (e2 != victim
598 case), then the PHIs in the target already have the correct
599 arguments. */
600 if (e2 == victim)
601 copy_phi_args (e2->dest, path->last ()->e, e2,
602 path, multi_incomings ? 0 : i);
603 }
604 else
605 {
606 /* Redirect VICTIM to the next duplicated block in the path. */
607 e2 = redirect_edge_and_branch (victim, rd->dup_blocks[count + 1]);
608
609 /* We need to update the PHIs in the next duplicated block. We
610 want the new PHI args to have the same value as they had
611 in the source of the next duplicate block.
612
613 Thus, we need to know which edge we traversed into the
614 source of the duplicate. Furthermore, we may have
615 traversed many edges to reach the source of the duplicate.
616
617 Walk through the path starting at element I until we
618 hit an edge marked with EDGE_COPY_SRC_BLOCK. We want
619 the edge from the prior element. */
620 for (unsigned int j = i + 1; j < path->length (); j++)
621 {
622 if ((*path)[j]->type == EDGE_COPY_SRC_BLOCK)
623 {
624 copy_phi_arg_into_existing_phi ((*path)[j - 1]->e, e2);
625 break;
626 }
627 }
628 }
629 count++;
630 }
631 else if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK)
632 {
633 remove_ctrl_stmt_and_useless_edges (rd->dup_blocks[count], NULL);
634 create_edge_and_update_destination_phis (rd, rd->dup_blocks[count],
635 multi_incomings ? 0 : i);
636 if (count == 1)
637 single_succ_edge (rd->dup_blocks[1])->aux = NULL;
638 count++;
639 }
640 }
641 }
642
643 /* Hash table traversal callback routine to create duplicate blocks. */
644
645 int
646 ssa_create_duplicates (struct redirection_data **slot,
647 ssa_local_info_t *local_info)
648 {
649 struct redirection_data *rd = *slot;
650
651 /* The second duplicated block in a jump threading path is specific
652 to the path. So it gets stored in RD rather than in LOCAL_DATA.
653
654 Each time we're called, we have to look through the path and see
655 if a second block needs to be duplicated.
656
657 Note the search starts with the third edge on the path. The first
658 edge is the incoming edge, the second edge always has its source
659 duplicated. Thus we start our search with the third edge. */
660 vec<jump_thread_edge *> *path = rd->path;
661 for (unsigned int i = 2; i < path->length (); i++)
662 {
663 if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK
664 || (*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
665 {
666 create_block_for_threading ((*path)[i]->e->src, rd, 1);
667 break;
668 }
669 }
670
671 /* Create a template block if we have not done so already. Otherwise
672 use the template to create a new block. */
673 if (local_info->template_block == NULL)
674 {
675 create_block_for_threading ((*path)[1]->e->src, rd, 0);
676 local_info->template_block = rd->dup_blocks[0];
677
678 /* We do not create any outgoing edges for the template. We will
679 take care of that in a later traversal. That way we do not
680 create edges that are going to just be deleted. */
681 }
682 else
683 {
684 create_block_for_threading (local_info->template_block, rd, 0);
685
686 /* Go ahead and wire up outgoing edges and update PHIs for the duplicate
687 block. */
688 ssa_fix_duplicate_block_edges (rd, local_info);
689 }
690
691 /* Keep walking the hash table. */
692 return 1;
693 }
694
695 /* We did not create any outgoing edges for the template block during
696 block creation. This hash table traversal callback creates the
697 outgoing edge for the template block. */
698
699 inline int
700 ssa_fixup_template_block (struct redirection_data **slot,
701 ssa_local_info_t *local_info)
702 {
703 struct redirection_data *rd = *slot;
704
705 /* If this is the template block halt the traversal after updating
706 it appropriately.
707
708 If we were threading through an joiner block, then we want
709 to keep its control statement and redirect an outgoing edge.
710 Else we want to remove the control statement & edges, then create
711 a new outgoing edge. In both cases we may need to update PHIs. */
712 if (rd->dup_blocks[0] && rd->dup_blocks[0] == local_info->template_block)
713 {
714 ssa_fix_duplicate_block_edges (rd, local_info);
715 return 0;
716 }
717
718 return 1;
719 }
720
721 /* Hash table traversal callback to redirect each incoming edge
722 associated with this hash table element to its new destination. */
723
724 int
725 ssa_redirect_edges (struct redirection_data **slot,
726 ssa_local_info_t *local_info)
727 {
728 struct redirection_data *rd = *slot;
729 struct el *next, *el;
730
731 /* Walk over all the incoming edges associated associated with this
732 hash table entry. */
733 for (el = rd->incoming_edges; el; el = next)
734 {
735 edge e = el->e;
736 vec<jump_thread_edge *> *path = THREAD_PATH (e);
737
738 /* Go ahead and free this element from the list. Doing this now
739 avoids the need for another list walk when we destroy the hash
740 table. */
741 next = el->next;
742 free (el);
743
744 thread_stats.num_threaded_edges++;
745
746 if (rd->dup_blocks[0])
747 {
748 edge e2;
749
750 if (dump_file && (dump_flags & TDF_DETAILS))
751 fprintf (dump_file, " Threaded jump %d --> %d to %d\n",
752 e->src->index, e->dest->index, rd->dup_blocks[0]->index);
753
754 rd->dup_blocks[0]->count += e->count;
755
756 /* Excessive jump threading may make frequencies large enough so
757 the computation overflows. */
758 if (rd->dup_blocks[0]->frequency < BB_FREQ_MAX * 2)
759 rd->dup_blocks[0]->frequency += EDGE_FREQUENCY (e);
760
761 /* In the case of threading through a joiner block, the outgoing
762 edges from the duplicate block were updated when they were
763 redirected during ssa_fix_duplicate_block_edges. */
764 if ((*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK)
765 EDGE_SUCC (rd->dup_blocks[0], 0)->count += e->count;
766
767 /* If we redirect a loop latch edge cancel its loop. */
768 if (e->src == e->src->loop_father->latch)
769 {
770 e->src->loop_father->header = NULL;
771 e->src->loop_father->latch = NULL;
772 loops_state_set (LOOPS_NEED_FIXUP);
773 }
774
775 /* Redirect the incoming edge (possibly to the joiner block) to the
776 appropriate duplicate block. */
777 e2 = redirect_edge_and_branch (e, rd->dup_blocks[0]);
778 gcc_assert (e == e2);
779 flush_pending_stmts (e2);
780 }
781
782 /* Go ahead and clear E->aux. It's not needed anymore and failure
783 to clear it will cause all kinds of unpleasant problems later. */
784 delete_jump_thread_path (path);
785 e->aux = NULL;
786
787 }
788
789 /* Indicate that we actually threaded one or more jumps. */
790 if (rd->incoming_edges)
791 local_info->jumps_threaded = true;
792
793 return 1;
794 }
795
796 /* Return true if this block has no executable statements other than
797 a simple ctrl flow instruction. When the number of outgoing edges
798 is one, this is equivalent to a "forwarder" block. */
799
800 static bool
801 redirection_block_p (basic_block bb)
802 {
803 gimple_stmt_iterator gsi;
804
805 /* Advance to the first executable statement. */
806 gsi = gsi_start_bb (bb);
807 while (!gsi_end_p (gsi)
808 && (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL
809 || is_gimple_debug (gsi_stmt (gsi))
810 || gimple_nop_p (gsi_stmt (gsi))))
811 gsi_next (&gsi);
812
813 /* Check if this is an empty block. */
814 if (gsi_end_p (gsi))
815 return true;
816
817 /* Test that we've reached the terminating control statement. */
818 return gsi_stmt (gsi)
819 && (gimple_code (gsi_stmt (gsi)) == GIMPLE_COND
820 || gimple_code (gsi_stmt (gsi)) == GIMPLE_GOTO
821 || gimple_code (gsi_stmt (gsi)) == GIMPLE_SWITCH);
822 }
823
824 /* BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB
825 is reached via one or more specific incoming edges, we know which
826 outgoing edge from BB will be traversed.
827
828 We want to redirect those incoming edges to the target of the
829 appropriate outgoing edge. Doing so avoids a conditional branch
830 and may expose new optimization opportunities. Note that we have
831 to update dominator tree and SSA graph after such changes.
832
833 The key to keeping the SSA graph update manageable is to duplicate
834 the side effects occurring in BB so that those side effects still
835 occur on the paths which bypass BB after redirecting edges.
836
837 We accomplish this by creating duplicates of BB and arranging for
838 the duplicates to unconditionally pass control to one specific
839 successor of BB. We then revector the incoming edges into BB to
840 the appropriate duplicate of BB.
841
842 If NOLOOP_ONLY is true, we only perform the threading as long as it
843 does not affect the structure of the loops in a nontrivial way.
844
845 If JOINERS is true, then thread through joiner blocks as well. */
846
847 static bool
848 thread_block_1 (basic_block bb, bool noloop_only, bool joiners)
849 {
850 /* E is an incoming edge into BB that we may or may not want to
851 redirect to a duplicate of BB. */
852 edge e, e2;
853 edge_iterator ei;
854 ssa_local_info_t local_info;
855
856 /* To avoid scanning a linear array for the element we need we instead
857 use a hash table. For normal code there should be no noticeable
858 difference. However, if we have a block with a large number of
859 incoming and outgoing edges such linear searches can get expensive. */
860 redirection_data
861 = new hash_table<struct redirection_data> (EDGE_COUNT (bb->succs));
862
863 /* Record each unique threaded destination into a hash table for
864 efficient lookups. */
865 FOR_EACH_EDGE (e, ei, bb->preds)
866 {
867 if (e->aux == NULL)
868 continue;
869
870 vec<jump_thread_edge *> *path = THREAD_PATH (e);
871
872 if (((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && !joiners)
873 || ((*path)[1]->type == EDGE_COPY_SRC_BLOCK && joiners))
874 continue;
875
876 e2 = path->last ()->e;
877 if (!e2 || noloop_only)
878 {
879 /* If NOLOOP_ONLY is true, we only allow threading through the
880 header of a loop to exit edges. */
881
882 /* One case occurs when there was loop header buried in a jump
883 threading path that crosses loop boundaries. We do not try
884 and thread this elsewhere, so just cancel the jump threading
885 request by clearing the AUX field now. */
886 if ((bb->loop_father != e2->src->loop_father
887 && !loop_exit_edge_p (e2->src->loop_father, e2))
888 || (e2->src->loop_father != e2->dest->loop_father
889 && !loop_exit_edge_p (e2->src->loop_father, e2)))
890 {
891 /* Since this case is not handled by our special code
892 to thread through a loop header, we must explicitly
893 cancel the threading request here. */
894 delete_jump_thread_path (path);
895 e->aux = NULL;
896 continue;
897 }
898
899 /* Another case occurs when trying to thread through our
900 own loop header, possibly from inside the loop. We will
901 thread these later. */
902 unsigned int i;
903 for (i = 1; i < path->length (); i++)
904 {
905 if ((*path)[i]->e->src == bb->loop_father->header
906 && (!loop_exit_edge_p (bb->loop_father, e2)
907 || (*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK))
908 break;
909 }
910
911 if (i != path->length ())
912 continue;
913 }
914
915 if (e->dest == e2->src)
916 update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e),
917 e->count, (*THREAD_PATH (e))[1]->e);
918
919 /* Insert the outgoing edge into the hash table if it is not
920 already in the hash table. */
921 lookup_redirection_data (e, INSERT);
922 }
923
924 /* We do not update dominance info. */
925 free_dominance_info (CDI_DOMINATORS);
926
927 /* We know we only thread through the loop header to loop exits.
928 Let the basic block duplication hook know we are not creating
929 a multiple entry loop. */
930 if (noloop_only
931 && bb == bb->loop_father->header)
932 set_loop_copy (bb->loop_father, loop_outer (bb->loop_father));
933
934 /* Now create duplicates of BB.
935
936 Note that for a block with a high outgoing degree we can waste
937 a lot of time and memory creating and destroying useless edges.
938
939 So we first duplicate BB and remove the control structure at the
940 tail of the duplicate as well as all outgoing edges from the
941 duplicate. We then use that duplicate block as a template for
942 the rest of the duplicates. */
943 local_info.template_block = NULL;
944 local_info.bb = bb;
945 local_info.jumps_threaded = false;
946 redirection_data->traverse <ssa_local_info_t *, ssa_create_duplicates>
947 (&local_info);
948
949 /* The template does not have an outgoing edge. Create that outgoing
950 edge and update PHI nodes as the edge's target as necessary.
951
952 We do this after creating all the duplicates to avoid creating
953 unnecessary edges. */
954 redirection_data->traverse <ssa_local_info_t *, ssa_fixup_template_block>
955 (&local_info);
956
957 /* The hash table traversals above created the duplicate blocks (and the
958 statements within the duplicate blocks). This loop creates PHI nodes for
959 the duplicated blocks and redirects the incoming edges into BB to reach
960 the duplicates of BB. */
961 redirection_data->traverse <ssa_local_info_t *, ssa_redirect_edges>
962 (&local_info);
963
964 /* Done with this block. Clear REDIRECTION_DATA. */
965 delete redirection_data;
966 redirection_data = NULL;
967
968 if (noloop_only
969 && bb == bb->loop_father->header)
970 set_loop_copy (bb->loop_father, NULL);
971
972 /* Indicate to our caller whether or not any jumps were threaded. */
973 return local_info.jumps_threaded;
974 }
975
976 /* Wrapper for thread_block_1 so that we can first handle jump
977 thread paths which do not involve copying joiner blocks, then
978 handle jump thread paths which have joiner blocks.
979
980 By doing things this way we can be as aggressive as possible and
981 not worry that copying a joiner block will create a jump threading
982 opportunity. */
983
984 static bool
985 thread_block (basic_block bb, bool noloop_only)
986 {
987 bool retval;
988 retval = thread_block_1 (bb, noloop_only, false);
989 retval |= thread_block_1 (bb, noloop_only, true);
990 return retval;
991 }
992
993
994 /* Threads edge E through E->dest to the edge THREAD_TARGET (E). Returns the
995 copy of E->dest created during threading, or E->dest if it was not necessary
996 to copy it (E is its single predecessor). */
997
998 static basic_block
999 thread_single_edge (edge e)
1000 {
1001 basic_block bb = e->dest;
1002 struct redirection_data rd;
1003 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1004 edge eto = (*path)[1]->e;
1005
1006 for (unsigned int i = 0; i < path->length (); i++)
1007 delete (*path)[i];
1008 delete path;
1009 e->aux = NULL;
1010
1011 thread_stats.num_threaded_edges++;
1012
1013 if (single_pred_p (bb))
1014 {
1015 /* If BB has just a single predecessor, we should only remove the
1016 control statements at its end, and successors except for ETO. */
1017 remove_ctrl_stmt_and_useless_edges (bb, eto->dest);
1018
1019 /* And fixup the flags on the single remaining edge. */
1020 eto->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL);
1021 eto->flags |= EDGE_FALLTHRU;
1022
1023 return bb;
1024 }
1025
1026 /* Otherwise, we need to create a copy. */
1027 if (e->dest == eto->src)
1028 update_bb_profile_for_threading (bb, EDGE_FREQUENCY (e), e->count, eto);
1029
1030 vec<jump_thread_edge *> *npath = new vec<jump_thread_edge *> ();
1031 jump_thread_edge *x = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
1032 npath->safe_push (x);
1033
1034 x = new jump_thread_edge (eto, EDGE_COPY_SRC_BLOCK);
1035 npath->safe_push (x);
1036 rd.path = npath;
1037
1038 create_block_for_threading (bb, &rd, 0);
1039 remove_ctrl_stmt_and_useless_edges (rd.dup_blocks[0], NULL);
1040 create_edge_and_update_destination_phis (&rd, rd.dup_blocks[0], 0);
1041
1042 if (dump_file && (dump_flags & TDF_DETAILS))
1043 fprintf (dump_file, " Threaded jump %d --> %d to %d\n",
1044 e->src->index, e->dest->index, rd.dup_blocks[0]->index);
1045
1046 rd.dup_blocks[0]->count = e->count;
1047 rd.dup_blocks[0]->frequency = EDGE_FREQUENCY (e);
1048 single_succ_edge (rd.dup_blocks[0])->count = e->count;
1049 redirect_edge_and_branch (e, rd.dup_blocks[0]);
1050 flush_pending_stmts (e);
1051
1052 return rd.dup_blocks[0];
1053 }
1054
1055 /* Callback for dfs_enumerate_from. Returns true if BB is different
1056 from STOP and DBDS_CE_STOP. */
1057
1058 static basic_block dbds_ce_stop;
1059 static bool
1060 dbds_continue_enumeration_p (const_basic_block bb, const void *stop)
1061 {
1062 return (bb != (const_basic_block) stop
1063 && bb != dbds_ce_stop);
1064 }
1065
1066 /* Evaluates the dominance relationship of latch of the LOOP and BB, and
1067 returns the state. */
1068
1069 enum bb_dom_status
1070 {
1071 /* BB does not dominate latch of the LOOP. */
1072 DOMST_NONDOMINATING,
1073 /* The LOOP is broken (there is no path from the header to its latch. */
1074 DOMST_LOOP_BROKEN,
1075 /* BB dominates the latch of the LOOP. */
1076 DOMST_DOMINATING
1077 };
1078
1079 static enum bb_dom_status
1080 determine_bb_domination_status (struct loop *loop, basic_block bb)
1081 {
1082 basic_block *bblocks;
1083 unsigned nblocks, i;
1084 bool bb_reachable = false;
1085 edge_iterator ei;
1086 edge e;
1087
1088 /* This function assumes BB is a successor of LOOP->header.
1089 If that is not the case return DOMST_NONDOMINATING which
1090 is always safe. */
1091 {
1092 bool ok = false;
1093
1094 FOR_EACH_EDGE (e, ei, bb->preds)
1095 {
1096 if (e->src == loop->header)
1097 {
1098 ok = true;
1099 break;
1100 }
1101 }
1102
1103 if (!ok)
1104 return DOMST_NONDOMINATING;
1105 }
1106
1107 if (bb == loop->latch)
1108 return DOMST_DOMINATING;
1109
1110 /* Check that BB dominates LOOP->latch, and that it is back-reachable
1111 from it. */
1112
1113 bblocks = XCNEWVEC (basic_block, loop->num_nodes);
1114 dbds_ce_stop = loop->header;
1115 nblocks = dfs_enumerate_from (loop->latch, 1, dbds_continue_enumeration_p,
1116 bblocks, loop->num_nodes, bb);
1117 for (i = 0; i < nblocks; i++)
1118 FOR_EACH_EDGE (e, ei, bblocks[i]->preds)
1119 {
1120 if (e->src == loop->header)
1121 {
1122 free (bblocks);
1123 return DOMST_NONDOMINATING;
1124 }
1125 if (e->src == bb)
1126 bb_reachable = true;
1127 }
1128
1129 free (bblocks);
1130 return (bb_reachable ? DOMST_DOMINATING : DOMST_LOOP_BROKEN);
1131 }
1132
1133 /* Return true if BB is part of the new pre-header that is created
1134 when threading the latch to DATA. */
1135
1136 static bool
1137 def_split_header_continue_p (const_basic_block bb, const void *data)
1138 {
1139 const_basic_block new_header = (const_basic_block) data;
1140 const struct loop *l;
1141
1142 if (bb == new_header
1143 || loop_depth (bb->loop_father) < loop_depth (new_header->loop_father))
1144 return false;
1145 for (l = bb->loop_father; l; l = loop_outer (l))
1146 if (l == new_header->loop_father)
1147 return true;
1148 return false;
1149 }
1150
1151 /* Thread jumps through the header of LOOP. Returns true if cfg changes.
1152 If MAY_PEEL_LOOP_HEADERS is false, we avoid threading from entry edges
1153 to the inside of the loop. */
1154
1155 static bool
1156 thread_through_loop_header (struct loop *loop, bool may_peel_loop_headers)
1157 {
1158 basic_block header = loop->header;
1159 edge e, tgt_edge, latch = loop_latch_edge (loop);
1160 edge_iterator ei;
1161 basic_block tgt_bb, atgt_bb;
1162 enum bb_dom_status domst;
1163
1164 /* We have already threaded through headers to exits, so all the threading
1165 requests now are to the inside of the loop. We need to avoid creating
1166 irreducible regions (i.e., loops with more than one entry block), and
1167 also loop with several latch edges, or new subloops of the loop (although
1168 there are cases where it might be appropriate, it is difficult to decide,
1169 and doing it wrongly may confuse other optimizers).
1170
1171 We could handle more general cases here. However, the intention is to
1172 preserve some information about the loop, which is impossible if its
1173 structure changes significantly, in a way that is not well understood.
1174 Thus we only handle few important special cases, in which also updating
1175 of the loop-carried information should be feasible:
1176
1177 1) Propagation of latch edge to a block that dominates the latch block
1178 of a loop. This aims to handle the following idiom:
1179
1180 first = 1;
1181 while (1)
1182 {
1183 if (first)
1184 initialize;
1185 first = 0;
1186 body;
1187 }
1188
1189 After threading the latch edge, this becomes
1190
1191 first = 1;
1192 if (first)
1193 initialize;
1194 while (1)
1195 {
1196 first = 0;
1197 body;
1198 }
1199
1200 The original header of the loop is moved out of it, and we may thread
1201 the remaining edges through it without further constraints.
1202
1203 2) All entry edges are propagated to a single basic block that dominates
1204 the latch block of the loop. This aims to handle the following idiom
1205 (normally created for "for" loops):
1206
1207 i = 0;
1208 while (1)
1209 {
1210 if (i >= 100)
1211 break;
1212 body;
1213 i++;
1214 }
1215
1216 This becomes
1217
1218 i = 0;
1219 while (1)
1220 {
1221 body;
1222 i++;
1223 if (i >= 100)
1224 break;
1225 }
1226 */
1227
1228 /* Threading through the header won't improve the code if the header has just
1229 one successor. */
1230 if (single_succ_p (header))
1231 goto fail;
1232
1233 /* If we threaded the latch using a joiner block, we cancel the
1234 threading opportunity out of an abundance of caution. However,
1235 still allow threading from outside to inside the loop. */
1236 if (latch->aux)
1237 {
1238 vec<jump_thread_edge *> *path = THREAD_PATH (latch);
1239 if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
1240 {
1241 delete_jump_thread_path (path);
1242 latch->aux = NULL;
1243 }
1244 }
1245
1246 if (latch->aux)
1247 {
1248 vec<jump_thread_edge *> *path = THREAD_PATH (latch);
1249 tgt_edge = (*path)[1]->e;
1250 tgt_bb = tgt_edge->dest;
1251 }
1252 else if (!may_peel_loop_headers
1253 && !redirection_block_p (loop->header))
1254 goto fail;
1255 else
1256 {
1257 tgt_bb = NULL;
1258 tgt_edge = NULL;
1259 FOR_EACH_EDGE (e, ei, header->preds)
1260 {
1261 if (!e->aux)
1262 {
1263 if (e == latch)
1264 continue;
1265
1266 /* If latch is not threaded, and there is a header
1267 edge that is not threaded, we would create loop
1268 with multiple entries. */
1269 goto fail;
1270 }
1271
1272 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1273
1274 if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
1275 goto fail;
1276 tgt_edge = (*path)[1]->e;
1277 atgt_bb = tgt_edge->dest;
1278 if (!tgt_bb)
1279 tgt_bb = atgt_bb;
1280 /* Two targets of threading would make us create loop
1281 with multiple entries. */
1282 else if (tgt_bb != atgt_bb)
1283 goto fail;
1284 }
1285
1286 if (!tgt_bb)
1287 {
1288 /* There are no threading requests. */
1289 return false;
1290 }
1291
1292 /* Redirecting to empty loop latch is useless. */
1293 if (tgt_bb == loop->latch
1294 && empty_block_p (loop->latch))
1295 goto fail;
1296 }
1297
1298 /* The target block must dominate the loop latch, otherwise we would be
1299 creating a subloop. */
1300 domst = determine_bb_domination_status (loop, tgt_bb);
1301 if (domst == DOMST_NONDOMINATING)
1302 goto fail;
1303 if (domst == DOMST_LOOP_BROKEN)
1304 {
1305 /* If the loop ceased to exist, mark it as such, and thread through its
1306 original header. */
1307 loop->header = NULL;
1308 loop->latch = NULL;
1309 loops_state_set (LOOPS_NEED_FIXUP);
1310 return thread_block (header, false);
1311 }
1312
1313 if (tgt_bb->loop_father->header == tgt_bb)
1314 {
1315 /* If the target of the threading is a header of a subloop, we need
1316 to create a preheader for it, so that the headers of the two loops
1317 do not merge. */
1318 if (EDGE_COUNT (tgt_bb->preds) > 2)
1319 {
1320 tgt_bb = create_preheader (tgt_bb->loop_father, 0);
1321 gcc_assert (tgt_bb != NULL);
1322 }
1323 else
1324 tgt_bb = split_edge (tgt_edge);
1325 }
1326
1327 if (latch->aux)
1328 {
1329 basic_block *bblocks;
1330 unsigned nblocks, i;
1331
1332 /* First handle the case latch edge is redirected. We are copying
1333 the loop header but not creating a multiple entry loop. Make the
1334 cfg manipulation code aware of that fact. */
1335 set_loop_copy (loop, loop);
1336 loop->latch = thread_single_edge (latch);
1337 set_loop_copy (loop, NULL);
1338 gcc_assert (single_succ (loop->latch) == tgt_bb);
1339 loop->header = tgt_bb;
1340
1341 /* Remove the new pre-header blocks from our loop. */
1342 bblocks = XCNEWVEC (basic_block, loop->num_nodes);
1343 nblocks = dfs_enumerate_from (header, 0, def_split_header_continue_p,
1344 bblocks, loop->num_nodes, tgt_bb);
1345 for (i = 0; i < nblocks; i++)
1346 if (bblocks[i]->loop_father == loop)
1347 {
1348 remove_bb_from_loops (bblocks[i]);
1349 add_bb_to_loop (bblocks[i], loop_outer (loop));
1350 }
1351 free (bblocks);
1352
1353 /* If the new header has multiple latches mark it so. */
1354 FOR_EACH_EDGE (e, ei, loop->header->preds)
1355 if (e->src->loop_father == loop
1356 && e->src != loop->latch)
1357 {
1358 loop->latch = NULL;
1359 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
1360 }
1361
1362 /* Cancel remaining threading requests that would make the
1363 loop a multiple entry loop. */
1364 FOR_EACH_EDGE (e, ei, header->preds)
1365 {
1366 edge e2;
1367
1368 if (e->aux == NULL)
1369 continue;
1370
1371 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1372 e2 = path->last ()->e;
1373
1374 if (e->src->loop_father != e2->dest->loop_father
1375 && e2->dest != loop->header)
1376 {
1377 delete_jump_thread_path (path);
1378 e->aux = NULL;
1379 }
1380 }
1381
1382 /* Thread the remaining edges through the former header. */
1383 thread_block (header, false);
1384 }
1385 else
1386 {
1387 basic_block new_preheader;
1388
1389 /* Now consider the case entry edges are redirected to the new entry
1390 block. Remember one entry edge, so that we can find the new
1391 preheader (its destination after threading). */
1392 FOR_EACH_EDGE (e, ei, header->preds)
1393 {
1394 if (e->aux)
1395 break;
1396 }
1397
1398 /* The duplicate of the header is the new preheader of the loop. Ensure
1399 that it is placed correctly in the loop hierarchy. */
1400 set_loop_copy (loop, loop_outer (loop));
1401
1402 thread_block (header, false);
1403 set_loop_copy (loop, NULL);
1404 new_preheader = e->dest;
1405
1406 /* Create the new latch block. This is always necessary, as the latch
1407 must have only a single successor, but the original header had at
1408 least two successors. */
1409 loop->latch = NULL;
1410 mfb_kj_edge = single_succ_edge (new_preheader);
1411 loop->header = mfb_kj_edge->dest;
1412 latch = make_forwarder_block (tgt_bb, mfb_keep_just, NULL);
1413 loop->header = latch->dest;
1414 loop->latch = latch->src;
1415 }
1416
1417 return true;
1418
1419 fail:
1420 /* We failed to thread anything. Cancel the requests. */
1421 FOR_EACH_EDGE (e, ei, header->preds)
1422 {
1423 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1424
1425 if (path)
1426 {
1427 delete_jump_thread_path (path);
1428 e->aux = NULL;
1429 }
1430 }
1431 return false;
1432 }
1433
1434 /* E1 and E2 are edges into the same basic block. Return TRUE if the
1435 PHI arguments associated with those edges are equal or there are no
1436 PHI arguments, otherwise return FALSE. */
1437
1438 static bool
1439 phi_args_equal_on_edges (edge e1, edge e2)
1440 {
1441 gimple_stmt_iterator gsi;
1442 int indx1 = e1->dest_idx;
1443 int indx2 = e2->dest_idx;
1444
1445 for (gsi = gsi_start_phis (e1->dest); !gsi_end_p (gsi); gsi_next (&gsi))
1446 {
1447 gimple phi = gsi_stmt (gsi);
1448
1449 if (!operand_equal_p (gimple_phi_arg_def (phi, indx1),
1450 gimple_phi_arg_def (phi, indx2), 0))
1451 return false;
1452 }
1453 return true;
1454 }
1455
1456 /* Walk through the registered jump threads and convert them into a
1457 form convenient for this pass.
1458
1459 Any block which has incoming edges threaded to outgoing edges
1460 will have its entry in THREADED_BLOCK set.
1461
1462 Any threaded edge will have its new outgoing edge stored in the
1463 original edge's AUX field.
1464
1465 This form avoids the need to walk all the edges in the CFG to
1466 discover blocks which need processing and avoids unnecessary
1467 hash table lookups to map from threaded edge to new target. */
1468
1469 static void
1470 mark_threaded_blocks (bitmap threaded_blocks)
1471 {
1472 unsigned int i;
1473 bitmap_iterator bi;
1474 bitmap tmp = BITMAP_ALLOC (NULL);
1475 basic_block bb;
1476 edge e;
1477 edge_iterator ei;
1478
1479 /* It is possible to have jump threads in which one is a subpath
1480 of the other. ie, (A, B), (B, C), (C, D) where B is a joiner
1481 block and (B, C), (C, D) where no joiner block exists.
1482
1483 When this occurs ignore the jump thread request with the joiner
1484 block. It's totally subsumed by the simpler jump thread request.
1485
1486 This results in less block copying, simpler CFGs. More importantly,
1487 when we duplicate the joiner block, B, in this case we will create
1488 a new threading opportunity that we wouldn't be able to optimize
1489 until the next jump threading iteration.
1490
1491 So first convert the jump thread requests which do not require a
1492 joiner block. */
1493 for (i = 0; i < paths.length (); i++)
1494 {
1495 vec<jump_thread_edge *> *path = paths[i];
1496
1497 if ((*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK)
1498 {
1499 edge e = (*path)[0]->e;
1500 e->aux = (void *)path;
1501 bitmap_set_bit (tmp, e->dest->index);
1502 }
1503 }
1504
1505 /* Now iterate again, converting cases where we want to thread
1506 through a joiner block, but only if no other edge on the path
1507 already has a jump thread attached to it. */
1508 for (i = 0; i < paths.length (); i++)
1509 {
1510 vec<jump_thread_edge *> *path = paths[i];
1511
1512 if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
1513 {
1514 unsigned int j;
1515
1516 for (j = 0; j < path->length (); j++)
1517 if ((*path)[j]->e->aux != NULL)
1518 break;
1519
1520 /* If we iterated through the entire path without exiting the loop,
1521 then we are good to go, attach the path to the starting edge. */
1522 if (j == path->length ())
1523 {
1524 edge e = (*path)[0]->e;
1525 e->aux = path;
1526 bitmap_set_bit (tmp, e->dest->index);
1527 }
1528 else if (dump_file && (dump_flags & TDF_DETAILS))
1529 {
1530 dump_jump_thread_path (dump_file, *path, false);
1531 }
1532 }
1533 }
1534
1535
1536 /* If optimizing for size, only thread through block if we don't have
1537 to duplicate it or it's an otherwise empty redirection block. */
1538 if (optimize_function_for_size_p (cfun))
1539 {
1540 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
1541 {
1542 bb = BASIC_BLOCK_FOR_FN (cfun, i);
1543 if (EDGE_COUNT (bb->preds) > 1
1544 && !redirection_block_p (bb))
1545 {
1546 FOR_EACH_EDGE (e, ei, bb->preds)
1547 {
1548 if (e->aux)
1549 {
1550 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1551 delete_jump_thread_path (path);
1552 e->aux = NULL;
1553 }
1554 }
1555 }
1556 else
1557 bitmap_set_bit (threaded_blocks, i);
1558 }
1559 }
1560 else
1561 bitmap_copy (threaded_blocks, tmp);
1562
1563 /* Look for jump threading paths which cross multiple loop headers.
1564
1565 The code to thread through loop headers will change the CFG in ways
1566 that break assumptions made by the loop optimization code.
1567
1568 We don't want to blindly cancel the requests. We can instead do better
1569 by trimming off the end of the jump thread path. */
1570 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
1571 {
1572 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1573 FOR_EACH_EDGE (e, ei, bb->preds)
1574 {
1575 if (e->aux)
1576 {
1577 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1578
1579 for (unsigned int i = 0, crossed_headers = 0;
1580 i < path->length ();
1581 i++)
1582 {
1583 basic_block dest = (*path)[i]->e->dest;
1584 crossed_headers += (dest == dest->loop_father->header);
1585 if (crossed_headers > 1)
1586 {
1587 /* Trim from entry I onwards. */
1588 for (unsigned int j = i; j < path->length (); j++)
1589 delete (*path)[j];
1590 path->truncate (i);
1591
1592 /* Now that we've truncated the path, make sure
1593 what's left is still valid. We need at least
1594 two edges on the path and the last edge can not
1595 be a joiner. This should never happen, but let's
1596 be safe. */
1597 if (path->length () < 2
1598 || (path->last ()->type
1599 == EDGE_COPY_SRC_JOINER_BLOCK))
1600 {
1601 delete_jump_thread_path (path);
1602 e->aux = NULL;
1603 }
1604 break;
1605 }
1606 }
1607 }
1608 }
1609 }
1610
1611 /* If we have a joiner block (J) which has two successors S1 and S2 and
1612 we are threading though S1 and the final destination of the thread
1613 is S2, then we must verify that any PHI nodes in S2 have the same
1614 PHI arguments for the edge J->S2 and J->S1->...->S2.
1615
1616 We used to detect this prior to registering the jump thread, but
1617 that prohibits propagation of edge equivalences into non-dominated
1618 PHI nodes as the equivalency test might occur before propagation.
1619
1620 This must also occur after we truncate any jump threading paths
1621 as this scenario may only show up after truncation.
1622
1623 This works for now, but will need improvement as part of the FSA
1624 optimization.
1625
1626 Note since we've moved the thread request data to the edges,
1627 we have to iterate on those rather than the threaded_edges vector. */
1628 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
1629 {
1630 bb = BASIC_BLOCK_FOR_FN (cfun, i);
1631 FOR_EACH_EDGE (e, ei, bb->preds)
1632 {
1633 if (e->aux)
1634 {
1635 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1636 bool have_joiner = ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK);
1637
1638 if (have_joiner)
1639 {
1640 basic_block joiner = e->dest;
1641 edge final_edge = path->last ()->e;
1642 basic_block final_dest = final_edge->dest;
1643 edge e2 = find_edge (joiner, final_dest);
1644
1645 if (e2 && !phi_args_equal_on_edges (e2, final_edge))
1646 {
1647 delete_jump_thread_path (path);
1648 e->aux = NULL;
1649 }
1650 }
1651 }
1652 }
1653 }
1654
1655 BITMAP_FREE (tmp);
1656 }
1657
1658
1659 /* Return TRUE if BB ends with a switch statement or a computed goto.
1660 Otherwise return false. */
1661 static bool
1662 bb_ends_with_multiway_branch (basic_block bb ATTRIBUTE_UNUSED)
1663 {
1664 gimple stmt = last_stmt (bb);
1665 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1666 return true;
1667 if (stmt && gimple_code (stmt) == GIMPLE_GOTO
1668 && TREE_CODE (gimple_goto_dest (stmt)) == SSA_NAME)
1669 return true;
1670 return false;
1671 }
1672
1673 /* Walk through all blocks and thread incoming edges to the appropriate
1674 outgoing edge for each edge pair recorded in THREADED_EDGES.
1675
1676 It is the caller's responsibility to fix the dominance information
1677 and rewrite duplicated SSA_NAMEs back into SSA form.
1678
1679 If MAY_PEEL_LOOP_HEADERS is false, we avoid threading edges through
1680 loop headers if it does not simplify the loop.
1681
1682 Returns true if one or more edges were threaded, false otherwise. */
1683
1684 bool
1685 thread_through_all_blocks (bool may_peel_loop_headers)
1686 {
1687 bool retval = false;
1688 unsigned int i;
1689 bitmap_iterator bi;
1690 bitmap threaded_blocks;
1691 struct loop *loop;
1692
1693 if (!paths.exists ())
1694 return false;
1695
1696 threaded_blocks = BITMAP_ALLOC (NULL);
1697 memset (&thread_stats, 0, sizeof (thread_stats));
1698
1699 mark_threaded_blocks (threaded_blocks);
1700
1701 initialize_original_copy_tables ();
1702
1703 /* First perform the threading requests that do not affect
1704 loop structure. */
1705 EXECUTE_IF_SET_IN_BITMAP (threaded_blocks, 0, i, bi)
1706 {
1707 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1708
1709 if (EDGE_COUNT (bb->preds) > 0)
1710 retval |= thread_block (bb, true);
1711 }
1712
1713 /* Then perform the threading through loop headers. We start with the
1714 innermost loop, so that the changes in cfg we perform won't affect
1715 further threading. */
1716 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1717 {
1718 if (!loop->header
1719 || !bitmap_bit_p (threaded_blocks, loop->header->index))
1720 continue;
1721
1722 retval |= thread_through_loop_header (loop, may_peel_loop_headers);
1723 }
1724
1725 /* Any jump threading paths that are still attached to edges at this
1726 point must be one of two cases.
1727
1728 First, we could have a jump threading path which went from outside
1729 a loop to inside a loop that was ignored because a prior jump thread
1730 across a backedge was realized (which indirectly causes the loop
1731 above to ignore the latter thread). We can detect these because the
1732 loop structures will be different and we do not currently try to
1733 optimize this case.
1734
1735 Second, we could be threading across a backedge to a point within the
1736 same loop. This occurrs for the FSA/FSM optimization and we would
1737 like to optimize it. However, we have to be very careful as this
1738 may completely scramble the loop structures, with the result being
1739 irreducible loops causing us to throw away our loop structure.
1740
1741 As a compromise for the latter case, if the thread path ends in
1742 a block where the last statement is a multiway branch, then go
1743 ahead and thread it, else ignore it. */
1744 basic_block bb;
1745 edge e;
1746 FOR_EACH_BB_FN (bb, cfun)
1747 {
1748 /* If we do end up threading here, we can remove elements from
1749 BB->preds. Thus we can not use the FOR_EACH_EDGE iterator. */
1750 for (edge_iterator ei = ei_start (bb->preds);
1751 (e = ei_safe_edge (ei));)
1752 if (e->aux)
1753 {
1754 vec<jump_thread_edge *> *path = THREAD_PATH (e);
1755
1756 /* Case 1, threading from outside to inside the loop
1757 after we'd already threaded through the header. */
1758 if ((*path)[0]->e->dest->loop_father
1759 != path->last ()->e->src->loop_father)
1760 {
1761 delete_jump_thread_path (path);
1762 e->aux = NULL;
1763 ei_next (&ei);
1764 }
1765 else if (bb_ends_with_multiway_branch (path->last ()->e->src))
1766 {
1767 /* The code to thread through loop headers may have
1768 split a block with jump threads attached to it.
1769
1770 We can identify this with a disjoint jump threading
1771 path. If found, just remove it. */
1772 for (unsigned int i = 0; i < path->length () - 1; i++)
1773 if ((*path)[i]->e->dest != (*path)[i + 1]->e->src)
1774 {
1775 delete_jump_thread_path (path);
1776 e->aux = NULL;
1777 ei_next (&ei);
1778 break;
1779 }
1780
1781 /* Our path is still valid, thread it. */
1782 if (e->aux)
1783 {
1784 struct loop *loop = (*path)[0]->e->dest->loop_father;
1785
1786 if (thread_block ((*path)[0]->e->dest, false))
1787 {
1788 /* This jump thread likely totally scrambled this loop.
1789 So arrange for it to be fixed up. */
1790 loop->header = NULL;
1791 loop->latch = NULL;
1792 e->aux = NULL;
1793 }
1794 else
1795 {
1796 delete_jump_thread_path (path);
1797 e->aux = NULL;
1798 ei_next (&ei);
1799 }
1800 }
1801 }
1802 else
1803 {
1804 delete_jump_thread_path (path);
1805 e->aux = NULL;
1806 ei_next (&ei);
1807 }
1808 }
1809 else
1810 ei_next (&ei);
1811 }
1812
1813 statistics_counter_event (cfun, "Jumps threaded",
1814 thread_stats.num_threaded_edges);
1815
1816 free_original_copy_tables ();
1817
1818 BITMAP_FREE (threaded_blocks);
1819 threaded_blocks = NULL;
1820 paths.release ();
1821
1822 if (retval)
1823 loops_state_set (LOOPS_NEED_FIXUP);
1824
1825 return retval;
1826 }
1827
1828 /* Delete the jump threading path PATH. We have to explcitly delete
1829 each entry in the vector, then the container. */
1830
1831 void
1832 delete_jump_thread_path (vec<jump_thread_edge *> *path)
1833 {
1834 for (unsigned int i = 0; i < path->length (); i++)
1835 delete (*path)[i];
1836 path->release();
1837 }
1838
1839 /* Register a jump threading opportunity. We queue up all the jump
1840 threading opportunities discovered by a pass and update the CFG
1841 and SSA form all at once.
1842
1843 E is the edge we can thread, E2 is the new target edge, i.e., we
1844 are effectively recording that E->dest can be changed to E2->dest
1845 after fixing the SSA graph. */
1846
1847 void
1848 register_jump_thread (vec<jump_thread_edge *> *path)
1849 {
1850 if (!dbg_cnt (registered_jump_thread))
1851 {
1852 delete_jump_thread_path (path);
1853 return;
1854 }
1855
1856 /* First make sure there are no NULL outgoing edges on the jump threading
1857 path. That can happen for jumping to a constant address. */
1858 for (unsigned int i = 0; i < path->length (); i++)
1859 if ((*path)[i]->e == NULL)
1860 {
1861 if (dump_file && (dump_flags & TDF_DETAILS))
1862 {
1863 fprintf (dump_file,
1864 "Found NULL edge in jump threading path. Cancelling jump thread:\n");
1865 dump_jump_thread_path (dump_file, *path, false);
1866 }
1867
1868 delete_jump_thread_path (path);
1869 return;
1870 }
1871
1872 if (dump_file && (dump_flags & TDF_DETAILS))
1873 dump_jump_thread_path (dump_file, *path, true);
1874
1875 if (!paths.exists ())
1876 paths.create (5);
1877
1878 paths.safe_push (path);
1879 }