1 /* Tail merging for gimple.
2 Copyright (C) 2011 Free Software Foundation, Inc.
3 Contributed by Tom de Vries (tom@codesourcery.com)
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
26 gimple representation of gcc/testsuite/gcc.dg/pr43864.c at
28 hprofStartupp (charD.1 * outputFileNameD.2600, charD.1 * ctxD.2601)
30 struct FILED.1638 * fpD.2605;
31 charD.1 fileNameD.2604[1000];
33 const charD.1 * restrict outputFileName.0D.3914;
36 # PRED: ENTRY [100.0%] (fallthru,exec)
37 # PT = nonlocal { D.3926 } (restr)
38 outputFileName.0D.3914_3
39 = (const charD.1 * restrict) outputFileNameD.2600_2(D);
40 # .MEMD.3923_13 = VDEF <.MEMD.3923_12(D)>
41 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
42 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
43 sprintfD.759 (&fileNameD.2604, outputFileName.0D.3914_3);
44 # .MEMD.3923_14 = VDEF <.MEMD.3923_13>
45 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
46 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
47 D.3915_4 = accessD.2606 (&fileNameD.2604, 1);
52 # SUCC: 3 [10.0%] (true,exec) 4 [90.0%] (false,exec)
55 # PRED: 2 [10.0%] (true,exec)
56 # .MEMD.3923_15 = VDEF <.MEMD.3923_14>
57 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
58 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
59 freeD.898 (ctxD.2601_5(D));
61 # SUCC: 7 [100.0%] (fallthru,exec)
64 # PRED: 2 [90.0%] (false,exec)
65 # .MEMD.3923_16 = VDEF <.MEMD.3923_14>
66 # PT = nonlocal escaped
67 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
68 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
69 fpD.2605_8 = fopenD.1805 (&fileNameD.2604[0], 0B);
74 # SUCC: 5 [1.9%] (true,exec) 6 [98.1%] (false,exec)
77 # PRED: 4 [1.9%] (true,exec)
78 # .MEMD.3923_17 = VDEF <.MEMD.3923_16>
79 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
80 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
81 freeD.898 (ctxD.2601_5(D));
83 # SUCC: 7 [100.0%] (fallthru,exec)
86 # PRED: 4 [98.1%] (false,exec)
87 # .MEMD.3923_18 = VDEF <.MEMD.3923_16>
88 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
89 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
90 fooD.2599 (outputFileNameD.2600_2(D), fpD.2605_8);
91 # SUCC: 7 [100.0%] (fallthru,exec)
94 # PRED: 3 [100.0%] (fallthru,exec) 5 [100.0%] (fallthru,exec)
95 6 [100.0%] (fallthru,exec)
98 # ctxD.2601_1 = PHI <0B(3), 0B(5), ctxD.2601_5(D)(6)>
99 # .MEMD.3923_11 = PHI <.MEMD.3923_15(3), .MEMD.3923_17(5),
101 # VUSE <.MEMD.3923_11>
103 # SUCC: EXIT [100.0%]
106 bb 3 and bb 5 can be merged. The blocks have different predecessors, but the
107 same successors, and the same operations.
112 A technique called tail merging (or cross jumping) can fix the example
113 above. For a block, we look for common code at the end (the tail) of the
114 predecessor blocks, and insert jumps from one block to the other.
115 The example is a special case for tail merging, in that 2 whole blocks
116 can be merged, rather than just the end parts of it.
117 We currently only focus on whole block merging, so in that sense
118 calling this pass tail merge is a bit of a misnomer.
120 We distinguish 2 kinds of situations in which blocks can be merged:
121 - same operations, same predecessors. The successor edges coming from one
122 block are redirected to come from the other block.
123 - same operations, same successors. The predecessor edges entering one block
124 are redirected to enter the other block. Note that this operation might
125 involve introducing phi operations.
127 For efficient implementation, we would like to value numbers the blocks, and
128 have a comparison operator that tells us whether the blocks are equal.
129 Besides being runtime efficient, block value numbering should also abstract
130 from irrelevant differences in order of operations, much like normal value
131 numbering abstracts from irrelevant order of operations.
133 For the first situation (same_operations, same predecessors), normal value
134 numbering fits well. We can calculate a block value number based on the
135 value numbers of the defs and vdefs.
137 For the second situation (same operations, same successors), this approach
138 doesn't work so well. We can illustrate this using the example. The calls
139 to free use different vdefs: MEMD.3923_16 and MEMD.3923_14, and these will
140 remain different in value numbering, since they represent different memory
141 states. So the resulting vdefs of the frees will be different in value
142 numbering, so the block value numbers will be different.
144 The reason why we call the blocks equal is not because they define the same
145 values, but because uses in the blocks use (possibly different) defs in the
146 same way. To be able to detect this efficiently, we need to do some kind of
147 reverse value numbering, meaning number the uses rather than the defs, and
148 calculate a block value number based on the value number of the uses.
149 Ideally, a block comparison operator will also indicate which phis are needed
152 For the moment, we don't do block value numbering, but we do insn-by-insn
153 matching, using scc value numbers to match operations with results, and
154 structural comparison otherwise, while ignoring vop mismatches.
159 1. The pass first determines all groups of blocks with the same successor
161 2. Within each group, it tries to determine clusters of equal basic blocks.
162 3. The clusters are applied.
163 4. The same successor groups are updated.
164 5. This process is repeated from 2 onwards, until no more changes.
170 - handles only 'same operations, same successors'.
171 It handles same predecessors as a special subcase though.
172 - does not implement the reverse value numbering and block value numbering.
173 - improve memory allocation: use garbage collected memory, obstacks,
174 allocpools where appropriate.
175 - no insertion of gimple_reg phis, We only introduce vop-phis.
176 - handle blocks with gimple_reg phi_nodes.
181 - ftree-tail-merge. On at -O2. We may have to enable it only at -Os. */
185 #include "coretypes.h"
189 #include "basic-block.h"
192 #include "function.h"
193 #include "tree-flow.h"
196 #include "tree-ssa-alias.h"
198 #include "tree-pretty-print.h"
200 #include "gimple-pretty-print.h"
201 #include "tree-ssa-sccvn.h"
202 #include "tree-dump.h"
204 /* Describes a group of bbs with the same successors. The successor bbs are
205 cached in succs, and the successor edge flags are cached in succ_flags.
206 If a bb has the EDGE_TRUE/VALSE_VALUE flags swapped compared to succ_flags,
207 it's marked in inverse.
208 Additionally, the hash value for the struct is cached in hashval, and
209 in_worklist indicates whether it's currently part of worklist. */
213 /* The bbs that have the same successor bbs. */
215 /* The successor bbs. */
217 /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for
220 /* The edge flags for each of the successor bbs. */
221 VEC (int, heap) *succ_flags;
222 /* Indicates whether the struct is currently in the worklist. */
224 /* The hash value of the struct. */
227 typedef struct same_succ_def *same_succ;
228 typedef const struct same_succ_def *const_same_succ;
230 /* A group of bbs where 1 bb from bbs can replace the other bbs. */
232 struct bb_cluster_def
234 /* The bbs in the cluster. */
236 /* The preds of the bbs in the cluster. */
238 /* Index in all_clusters vector. */
240 /* The bb to replace the cluster with. */
243 typedef struct bb_cluster_def *bb_cluster;
244 typedef const struct bb_cluster_def *const_bb_cluster;
250 /* The number of non-debug statements in the bb. */
252 /* The same_succ that this bb is a member of. */
253 same_succ bb_same_succ;
254 /* The cluster that this bb is a member of. */
256 /* The vop state at the exit of a bb. This is shortlived data, used to
257 communicate data between update_block_by and update_vuses. */
259 /* The bb that either contains or is dominated by the dependencies of the
264 /* Macros to access the fields of struct aux_bb_info. */
266 #define BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size)
267 #define BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ)
268 #define BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster)
269 #define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
270 #define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)
272 /* VAL1 and VAL2 are either:
273 - uses in BB1 and BB2, or
274 - phi alternatives for BB1 and BB2.
275 Return true if the uses have the same gvn value. */
278 gvn_uses_equal (tree val1, tree val2)
280 gcc_checking_assert (val1 != NULL_TREE && val2 != NULL_TREE);
285 if (vn_valueize (val1) != vn_valueize (val2))
288 return ((TREE_CODE (val1) == SSA_NAME || CONSTANT_CLASS_P (val1))
289 && (TREE_CODE (val2) == SSA_NAME || CONSTANT_CLASS_P (val2)));
292 /* Prints E to FILE. */
295 same_succ_print (FILE *file, const same_succ e)
298 bitmap_print (file, e->bbs, "bbs:", "\n");
299 bitmap_print (file, e->succs, "succs:", "\n");
300 bitmap_print (file, e->inverse, "inverse:", "\n");
301 fprintf (file, "flags:");
302 for (i = 0; i < VEC_length (int, e->succ_flags); ++i)
303 fprintf (file, " %x", VEC_index (int, e->succ_flags, i));
304 fprintf (file, "\n");
307 /* Prints same_succ VE to VFILE. */
310 same_succ_print_traverse (void **ve, void *vfile)
312 const same_succ e = *((const same_succ *)ve);
313 FILE *file = ((FILE*)vfile);
314 same_succ_print (file, e);
318 /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */
321 update_dep_bb (basic_block use_bb, tree val)
326 if (TREE_CODE (val) != SSA_NAME)
329 /* Skip use of global def. */
330 if (SSA_NAME_IS_DEFAULT_DEF (val))
333 /* Skip use of local def. */
334 dep_bb = gimple_bb (SSA_NAME_DEF_STMT (val));
335 if (dep_bb == use_bb)
338 if (BB_DEP_BB (use_bb) == NULL
339 || dominated_by_p (CDI_DOMINATORS, dep_bb, BB_DEP_BB (use_bb)))
340 BB_DEP_BB (use_bb) = dep_bb;
343 /* Update BB_DEP_BB, given the dependencies in STMT. */
346 stmt_update_dep_bb (gimple stmt)
351 FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
352 update_dep_bb (gimple_bb (stmt), USE_FROM_PTR (use));
355 /* Returns whether VAL is used in the same bb as in which it is defined, or
356 in the phi of a successor bb. */
361 gimple stmt, def_stmt;
362 basic_block bb, def_bb;
363 imm_use_iterator iter;
366 if (TREE_CODE (val) != SSA_NAME)
368 def_stmt = SSA_NAME_DEF_STMT (val);
369 def_bb = gimple_bb (def_stmt);
372 FOR_EACH_IMM_USE_STMT (stmt, iter, val)
374 bb = gimple_bb (stmt);
377 if (gimple_code (stmt) == GIMPLE_PHI
378 && find_edge (def_bb, bb))
381 BREAK_FROM_IMM_USE_STMT (iter);
386 /* Calculates hash value for same_succ VE. */
389 same_succ_hash (const void *ve)
391 const_same_succ e = (const_same_succ)ve;
392 hashval_t hashval = bitmap_hash (e->succs);
395 unsigned int first = bitmap_first_set_bit (e->bbs);
396 basic_block bb = BASIC_BLOCK (first);
398 gimple_stmt_iterator gsi;
404 for (gsi = gsi_start_nondebug_bb (bb);
405 !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
407 stmt = gsi_stmt (gsi);
408 stmt_update_dep_bb (stmt);
409 if (is_gimple_assign (stmt) && local_def (gimple_get_lhs (stmt))
410 && !gimple_has_side_effects (stmt))
414 hashval = iterative_hash_hashval_t (gimple_code (stmt), hashval);
415 if (is_gimple_assign (stmt))
416 hashval = iterative_hash_hashval_t (gimple_assign_rhs_code (stmt),
418 if (!is_gimple_call (stmt))
420 if (gimple_call_internal_p (stmt))
421 hashval = iterative_hash_hashval_t
422 ((hashval_t) gimple_call_internal_fn (stmt), hashval);
424 hashval = iterative_hash_expr (gimple_call_fn (stmt), hashval);
425 for (i = 0; i < gimple_call_num_args (stmt); i++)
427 arg = gimple_call_arg (stmt, i);
428 arg = vn_valueize (arg);
429 hashval = iterative_hash_expr (arg, hashval);
433 hashval = iterative_hash_hashval_t (size, hashval);
436 for (i = 0; i < VEC_length (int, e->succ_flags); ++i)
438 flags = VEC_index (int, e->succ_flags, i);
439 flags = flags & ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
440 hashval = iterative_hash_hashval_t (flags, hashval);
443 EXECUTE_IF_SET_IN_BITMAP (e->succs, 0, s, bs)
445 int n = find_edge (bb, BASIC_BLOCK (s))->dest_idx;
446 for (gsi = gsi_start_phis (BASIC_BLOCK (s)); !gsi_end_p (gsi);
449 gimple phi = gsi_stmt (gsi);
450 tree lhs = gimple_phi_result (phi);
451 tree val = gimple_phi_arg_def (phi, n);
453 if (!is_gimple_reg (lhs))
455 update_dep_bb (bb, val);
462 /* Returns true if E1 and E2 have 2 successors, and if the successor flags
463 are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
464 the other edge flags. */
467 inverse_flags (const_same_succ e1, const_same_succ e2)
469 int f1a, f1b, f2a, f2b;
470 int mask = ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
472 if (VEC_length (int, e1->succ_flags) != 2)
475 f1a = VEC_index (int, e1->succ_flags, 0);
476 f1b = VEC_index (int, e1->succ_flags, 1);
477 f2a = VEC_index (int, e2->succ_flags, 0);
478 f2b = VEC_index (int, e2->succ_flags, 1);
480 if (f1a == f2a && f1b == f2b)
483 return (f1a & mask) == (f2a & mask) && (f1b & mask) == (f2b & mask);
486 /* Compares SAME_SUCCs VE1 and VE2. */
489 same_succ_equal (const void *ve1, const void *ve2)
491 const_same_succ e1 = (const_same_succ)ve1;
492 const_same_succ e2 = (const_same_succ)ve2;
493 unsigned int i, first1, first2;
494 gimple_stmt_iterator gsi1, gsi2;
496 basic_block bb1, bb2;
498 if (e1->hashval != e2->hashval)
501 if (VEC_length (int, e1->succ_flags) != VEC_length (int, e2->succ_flags))
504 if (!bitmap_equal_p (e1->succs, e2->succs))
507 if (!inverse_flags (e1, e2))
509 for (i = 0; i < VEC_length (int, e1->succ_flags); ++i)
510 if (VEC_index (int, e1->succ_flags, i)
511 != VEC_index (int, e1->succ_flags, i))
515 first1 = bitmap_first_set_bit (e1->bbs);
516 first2 = bitmap_first_set_bit (e2->bbs);
518 bb1 = BASIC_BLOCK (first1);
519 bb2 = BASIC_BLOCK (first2);
521 if (BB_SIZE (bb1) != BB_SIZE (bb2))
524 gsi1 = gsi_start_nondebug_bb (bb1);
525 gsi2 = gsi_start_nondebug_bb (bb2);
526 while (!(gsi_end_p (gsi1) || gsi_end_p (gsi2)))
528 s1 = gsi_stmt (gsi1);
529 s2 = gsi_stmt (gsi2);
530 if (gimple_code (s1) != gimple_code (s2))
532 if (is_gimple_call (s1) && !gimple_call_same_target_p (s1, s2))
534 gsi_next_nondebug (&gsi1);
535 gsi_next_nondebug (&gsi2);
541 /* Alloc and init a new SAME_SUCC. */
544 same_succ_alloc (void)
546 same_succ same = XNEW (struct same_succ_def);
548 same->bbs = BITMAP_ALLOC (NULL);
549 same->succs = BITMAP_ALLOC (NULL);
550 same->inverse = BITMAP_ALLOC (NULL);
551 same->succ_flags = VEC_alloc (int, heap, 10);
552 same->in_worklist = false;
557 /* Delete same_succ VE. */
560 same_succ_delete (void *ve)
562 same_succ e = (same_succ)ve;
564 BITMAP_FREE (e->bbs);
565 BITMAP_FREE (e->succs);
566 BITMAP_FREE (e->inverse);
567 VEC_free (int, heap, e->succ_flags);
572 /* Reset same_succ SAME. */
575 same_succ_reset (same_succ same)
577 bitmap_clear (same->bbs);
578 bitmap_clear (same->succs);
579 bitmap_clear (same->inverse);
580 VEC_truncate (int, same->succ_flags, 0);
583 /* Hash table with all same_succ entries. */
585 static htab_t same_succ_htab;
587 /* Array that is used to store the edge flags for a successor. */
589 static int *same_succ_edge_flags;
591 /* Bitmap that is used to mark bbs that are recently deleted. */
593 static bitmap deleted_bbs;
595 /* Bitmap that is used to mark predecessors of bbs that are
598 static bitmap deleted_bb_preds;
600 /* Prints same_succ_htab to stderr. */
602 extern void debug_same_succ (void);
604 debug_same_succ ( void)
606 htab_traverse (same_succ_htab, same_succ_print_traverse, stderr);
609 DEF_VEC_P (same_succ);
610 DEF_VEC_ALLOC_P (same_succ, heap);
612 /* Vector of bbs to process. */
614 static VEC (same_succ, heap) *worklist;
616 /* Prints worklist to FILE. */
619 print_worklist (FILE *file)
622 for (i = 0; i < VEC_length (same_succ, worklist); ++i)
623 same_succ_print (file, VEC_index (same_succ, worklist, i));
626 /* Adds SAME to worklist. */
629 add_to_worklist (same_succ same)
631 if (same->in_worklist)
634 if (bitmap_count_bits (same->bbs) < 2)
637 same->in_worklist = true;
638 VEC_safe_push (same_succ, heap, worklist, same);
641 /* Add BB to same_succ_htab. */
644 find_same_succ_bb (basic_block bb, same_succ *same_p)
648 same_succ same = *same_p;
655 bitmap_set_bit (same->bbs, bb->index);
656 FOR_EACH_EDGE (e, ei, bb->succs)
658 int index = e->dest->index;
659 bitmap_set_bit (same->succs, index);
660 same_succ_edge_flags[index] = e->flags;
662 EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
663 VEC_safe_push (int, heap, same->succ_flags, same_succ_edge_flags[j]);
665 same->hashval = same_succ_hash (same);
667 slot = (same_succ *) htab_find_slot_with_hash (same_succ_htab, same,
668 same->hashval, INSERT);
672 BB_SAME_SUCC (bb) = same;
673 add_to_worklist (same);
678 bitmap_set_bit ((*slot)->bbs, bb->index);
679 BB_SAME_SUCC (bb) = *slot;
680 add_to_worklist (*slot);
681 if (inverse_flags (same, *slot))
682 bitmap_set_bit ((*slot)->inverse, bb->index);
683 same_succ_reset (same);
687 /* Find bbs with same successors. */
690 find_same_succ (void)
692 same_succ same = same_succ_alloc ();
697 find_same_succ_bb (bb, &same);
699 same = same_succ_alloc ();
702 same_succ_delete (same);
705 /* Initializes worklist administration. */
710 alloc_aux_for_blocks (sizeof (struct aux_bb_info));
712 = htab_create (n_basic_blocks, same_succ_hash, same_succ_equal,
714 same_succ_edge_flags = XCNEWVEC (int, last_basic_block);
715 deleted_bbs = BITMAP_ALLOC (NULL);
716 deleted_bb_preds = BITMAP_ALLOC (NULL);
717 worklist = VEC_alloc (same_succ, heap, n_basic_blocks);
720 if (dump_file && (dump_flags & TDF_DETAILS))
722 fprintf (dump_file, "initial worklist:\n");
723 print_worklist (dump_file);
727 /* Deletes worklist administration. */
730 delete_worklist (void)
732 free_aux_for_blocks ();
733 htab_delete (same_succ_htab);
734 same_succ_htab = NULL;
735 XDELETEVEC (same_succ_edge_flags);
736 same_succ_edge_flags = NULL;
737 BITMAP_FREE (deleted_bbs);
738 BITMAP_FREE (deleted_bb_preds);
739 VEC_free (same_succ, heap, worklist);
742 /* Mark BB as deleted, and mark its predecessors. */
745 delete_basic_block_same_succ (basic_block bb)
750 bitmap_set_bit (deleted_bbs, bb->index);
752 FOR_EACH_EDGE (e, ei, bb->preds)
753 bitmap_set_bit (deleted_bb_preds, e->src->index);
756 /* Removes all bbs in BBS from their corresponding same_succ. */
759 same_succ_flush_bbs (bitmap bbs)
764 EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
766 basic_block bb = BASIC_BLOCK (i);
767 same_succ same = BB_SAME_SUCC (bb);
768 BB_SAME_SUCC (bb) = NULL;
769 if (bitmap_single_bit_set_p (same->bbs))
770 htab_remove_elt_with_hash (same_succ_htab, same, same->hashval);
772 bitmap_clear_bit (same->bbs, i);
776 /* Delete all deleted_bbs. */
784 same_succ_flush_bbs (deleted_bbs);
786 EXECUTE_IF_SET_IN_BITMAP (deleted_bbs, 0, i, bi)
787 delete_basic_block (BASIC_BLOCK (i));
789 bitmap_and_compl_into (deleted_bb_preds, deleted_bbs);
790 bitmap_clear (deleted_bbs);
793 /* For deleted_bb_preds, find bbs with same successors. */
796 update_worklist (void)
803 bitmap_clear_bit (deleted_bb_preds, ENTRY_BLOCK);
804 same_succ_flush_bbs (deleted_bb_preds);
806 same = same_succ_alloc ();
807 EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds, 0, i, bi)
809 bb = BASIC_BLOCK (i);
810 gcc_assert (bb != NULL);
811 find_same_succ_bb (bb, &same);
813 same = same_succ_alloc ();
815 same_succ_delete (same);
816 bitmap_clear (deleted_bb_preds);
819 /* Prints cluster C to FILE. */
822 print_cluster (FILE *file, bb_cluster c)
826 bitmap_print (file, c->bbs, "bbs:", "\n");
827 bitmap_print (file, c->preds, "preds:", "\n");
830 /* Prints cluster C to stderr. */
832 extern void debug_cluster (bb_cluster);
834 debug_cluster (bb_cluster c)
836 print_cluster (stderr, c);
839 /* Update C->rep_bb, given that BB is added to the cluster. */
842 update_rep_bb (bb_cluster c, basic_block bb)
845 if (c->rep_bb == NULL)
851 /* Current needs no deps, keep it. */
852 if (BB_DEP_BB (c->rep_bb) == NULL)
855 /* Bb needs no deps, change rep_bb. */
856 if (BB_DEP_BB (bb) == NULL)
862 /* Bb needs last deps earlier than current, change rep_bb. A potential
863 problem with this, is that the first deps might also be earlier, which
864 would mean we prefer longer lifetimes for the deps. To be able to check
865 for this, we would have to trace BB_FIRST_DEP_BB as well, besides
866 BB_DEP_BB, which is really BB_LAST_DEP_BB.
867 The benefit of choosing the bb with last deps earlier, is that it can
868 potentially be used as replacement for more bbs. */
869 if (dominated_by_p (CDI_DOMINATORS, BB_DEP_BB (c->rep_bb), BB_DEP_BB (bb)))
873 /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
876 add_bb_to_cluster (bb_cluster c, basic_block bb)
881 bitmap_set_bit (c->bbs, bb->index);
883 FOR_EACH_EDGE (e, ei, bb->preds)
884 bitmap_set_bit (c->preds, e->src->index);
886 update_rep_bb (c, bb);
889 /* Allocate and init new cluster. */
895 c = XCNEW (struct bb_cluster_def);
896 c->bbs = BITMAP_ALLOC (NULL);
897 c->preds = BITMAP_ALLOC (NULL);
902 /* Delete clusters. */
905 delete_cluster (bb_cluster c)
909 BITMAP_FREE (c->bbs);
910 BITMAP_FREE (c->preds);
914 DEF_VEC_P (bb_cluster);
915 DEF_VEC_ALLOC_P (bb_cluster, heap);
917 /* Array that contains all clusters. */
919 static VEC (bb_cluster, heap) *all_clusters;
921 /* Allocate all cluster vectors. */
924 alloc_cluster_vectors (void)
926 all_clusters = VEC_alloc (bb_cluster, heap, n_basic_blocks);
929 /* Reset all cluster vectors. */
932 reset_cluster_vectors (void)
936 for (i = 0; i < VEC_length (bb_cluster, all_clusters); ++i)
937 delete_cluster (VEC_index (bb_cluster, all_clusters, i));
938 VEC_truncate (bb_cluster, all_clusters, 0);
940 BB_CLUSTER (bb) = NULL;
943 /* Delete all cluster vectors. */
946 delete_cluster_vectors (void)
949 for (i = 0; i < VEC_length (bb_cluster, all_clusters); ++i)
950 delete_cluster (VEC_index (bb_cluster, all_clusters, i));
951 VEC_free (bb_cluster, heap, all_clusters);
954 /* Merge cluster C2 into C1. */
957 merge_clusters (bb_cluster c1, bb_cluster c2)
959 bitmap_ior_into (c1->bbs, c2->bbs);
960 bitmap_ior_into (c1->preds, c2->preds);
963 /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
964 all_clusters, or merge c with existing cluster. */
967 set_cluster (basic_block bb1, basic_block bb2)
969 basic_block merge_bb, other_bb;
970 bb_cluster merge, old, c;
972 if (BB_CLUSTER (bb1) == NULL && BB_CLUSTER (bb2) == NULL)
975 add_bb_to_cluster (c, bb1);
976 add_bb_to_cluster (c, bb2);
977 BB_CLUSTER (bb1) = c;
978 BB_CLUSTER (bb2) = c;
979 c->index = VEC_length (bb_cluster, all_clusters);
980 VEC_safe_push (bb_cluster, heap, all_clusters, c);
982 else if (BB_CLUSTER (bb1) == NULL || BB_CLUSTER (bb2) == NULL)
984 merge_bb = BB_CLUSTER (bb1) == NULL ? bb2 : bb1;
985 other_bb = BB_CLUSTER (bb1) == NULL ? bb1 : bb2;
986 merge = BB_CLUSTER (merge_bb);
987 add_bb_to_cluster (merge, other_bb);
988 BB_CLUSTER (other_bb) = merge;
990 else if (BB_CLUSTER (bb1) != BB_CLUSTER (bb2))
995 old = BB_CLUSTER (bb2);
996 merge = BB_CLUSTER (bb1);
997 merge_clusters (merge, old);
998 EXECUTE_IF_SET_IN_BITMAP (old->bbs, 0, i, bi)
999 BB_CLUSTER (BASIC_BLOCK (i)) = merge;
1000 VEC_replace (bb_cluster, all_clusters, old->index, NULL);
1001 update_rep_bb (merge, old->rep_bb);
1002 delete_cluster (old);
1008 /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
1009 gimple_bb (s2) are members of SAME_SUCC. */
1012 gimple_equal_p (same_succ same_succ, gimple s1, gimple s2)
1016 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
1018 bool equal, inv_cond;
1019 enum tree_code code1, code2;
1021 if (gimple_code (s1) != gimple_code (s2))
1024 switch (gimple_code (s1))
1027 if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
1029 if (!gimple_call_same_target_p (s1, s2))
1033 for (i = 0; i < gimple_call_num_args (s1); ++i)
1035 t1 = gimple_call_arg (s1, i);
1036 t2 = gimple_call_arg (s2, i);
1037 if (operand_equal_p (t1, t2, 0))
1039 if (gvn_uses_equal (t1, t2))
1047 lhs1 = gimple_get_lhs (s1);
1048 lhs2 = gimple_get_lhs (s2);
1049 return (lhs1 != NULL_TREE && lhs2 != NULL_TREE
1050 && TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME
1051 && vn_valueize (lhs1) == vn_valueize (lhs2));
1054 lhs1 = gimple_get_lhs (s1);
1055 lhs2 = gimple_get_lhs (s2);
1056 return (TREE_CODE (lhs1) == SSA_NAME
1057 && TREE_CODE (lhs2) == SSA_NAME
1058 && vn_valueize (lhs1) == vn_valueize (lhs2));
1061 t1 = gimple_cond_lhs (s1);
1062 t2 = gimple_cond_lhs (s2);
1063 if (!operand_equal_p (t1, t2, 0)
1064 && !gvn_uses_equal (t1, t2))
1067 t1 = gimple_cond_rhs (s1);
1068 t2 = gimple_cond_rhs (s2);
1069 if (!operand_equal_p (t1, t2, 0)
1070 && !gvn_uses_equal (t1, t2))
1073 code1 = gimple_expr_code (s1);
1074 code2 = gimple_expr_code (s2);
1075 inv_cond = (bitmap_bit_p (same_succ->inverse, bb1->index)
1076 != bitmap_bit_p (same_succ->inverse, bb2->index));
1080 = HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (s1))));
1081 code2 = invert_tree_comparison (code2, honor_nans);
1083 return code1 == code2;
1090 /* Let GSI skip backwards over local defs. */
1093 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi)
1099 if (gsi_end_p (*gsi))
1101 stmt = gsi_stmt (*gsi);
1102 if (!(is_gimple_assign (stmt) && local_def (gimple_get_lhs (stmt))
1103 && !gimple_has_side_effects (stmt)))
1105 gsi_prev_nondebug (gsi);
1109 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1113 find_duplicate (same_succ same_succ, basic_block bb1, basic_block bb2)
1115 gimple_stmt_iterator gsi1 = gsi_last_nondebug_bb (bb1);
1116 gimple_stmt_iterator gsi2 = gsi_last_nondebug_bb (bb2);
1118 gsi_advance_bw_nondebug_nonlocal (&gsi1);
1119 gsi_advance_bw_nondebug_nonlocal (&gsi2);
1121 while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2))
1123 if (!gimple_equal_p (same_succ, gsi_stmt (gsi1), gsi_stmt (gsi2)))
1126 gsi_prev_nondebug (&gsi1);
1127 gsi_prev_nondebug (&gsi2);
1128 gsi_advance_bw_nondebug_nonlocal (&gsi1);
1129 gsi_advance_bw_nondebug_nonlocal (&gsi2);
1132 if (!(gsi_end_p (gsi1) && gsi_end_p (gsi2)))
1136 fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1137 bb1->index, bb2->index);
1139 set_cluster (bb1, bb2);
1142 /* Returns whether for all phis in DEST the phi alternatives for E1 and
1146 same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
1148 int n1 = e1->dest_idx, n2 = e2->dest_idx;
1149 gimple_stmt_iterator gsi;
1151 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
1153 gimple phi = gsi_stmt (gsi);
1154 tree lhs = gimple_phi_result (phi);
1155 tree val1 = gimple_phi_arg_def (phi, n1);
1156 tree val2 = gimple_phi_arg_def (phi, n2);
1158 if (!is_gimple_reg (lhs))
1161 if (operand_equal_for_phi_arg_p (val1, val2))
1163 if (gvn_uses_equal (val1, val2))
1172 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1173 phi alternatives for BB1 and BB2 are equal. */
1176 same_phi_alternatives (same_succ same_succ, basic_block bb1, basic_block bb2)
1183 EXECUTE_IF_SET_IN_BITMAP (same_succ->succs, 0, s, bs)
1185 succ = BASIC_BLOCK (s);
1186 e1 = find_edge (bb1, succ);
1187 e2 = find_edge (bb2, succ);
1188 if (e1->flags & EDGE_COMPLEX
1189 || e2->flags & EDGE_COMPLEX)
1192 /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1194 if (!same_phi_alternatives_1 (succ, e1, e2))
1201 /* Return true if BB has non-vop phis. */
1204 bb_has_non_vop_phi (basic_block bb)
1206 gimple_seq phis = phi_nodes (bb);
1212 if (!gimple_seq_singleton_p (phis))
1215 phi = gimple_seq_first_stmt (phis);
1216 return is_gimple_reg (gimple_phi_result (phi));
1219 /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1220 invariant that uses in FROM are dominates by their defs. */
1223 deps_ok_for_redirect_from_bb_to_bb (basic_block from, basic_block to)
1225 basic_block cd, dep_bb = BB_DEP_BB (to);
1228 bitmap from_preds = BITMAP_ALLOC (NULL);
1233 FOR_EACH_EDGE (e, ei, from->preds)
1234 bitmap_set_bit (from_preds, e->src->index);
1235 cd = nearest_common_dominator_for_set (CDI_DOMINATORS, from_preds);
1236 BITMAP_FREE (from_preds);
1238 return dominated_by_p (CDI_DOMINATORS, dep_bb, cd);
1241 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1242 replacement bb) and vice versa maintains the invariant that uses in the
1243 replacement are dominates by their defs. */
1246 deps_ok_for_redirect (basic_block bb1, basic_block bb2)
1248 if (BB_CLUSTER (bb1) != NULL)
1249 bb1 = BB_CLUSTER (bb1)->rep_bb;
1251 if (BB_CLUSTER (bb2) != NULL)
1252 bb2 = BB_CLUSTER (bb2)->rep_bb;
1254 return (deps_ok_for_redirect_from_bb_to_bb (bb1, bb2)
1255 && deps_ok_for_redirect_from_bb_to_bb (bb2, bb1));
1258 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1261 find_clusters_1 (same_succ same_succ)
1263 basic_block bb1, bb2;
1265 bitmap_iterator bi, bj;
1267 int max_comparisons = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS);
1269 EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, 0, i, bi)
1271 bb1 = BASIC_BLOCK (i);
1273 /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1274 phi-nodes in bb1 and bb2, with the same alternatives for the same
1276 if (bb_has_non_vop_phi (bb1))
1280 EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, i + 1, j, bj)
1282 bb2 = BASIC_BLOCK (j);
1284 if (bb_has_non_vop_phi (bb2))
1287 if (BB_CLUSTER (bb1) != NULL && BB_CLUSTER (bb1) == BB_CLUSTER (bb2))
1290 /* Limit quadratic behaviour. */
1292 if (nr_comparisons > max_comparisons)
1295 /* This is a conservative dependency check. We could test more
1296 precise for allowed replacement direction. */
1297 if (!deps_ok_for_redirect (bb1, bb2))
1300 if (!(same_phi_alternatives (same_succ, bb1, bb2)))
1303 find_duplicate (same_succ, bb1, bb2);
1308 /* Find clusters of bbs which can be merged. */
1311 find_clusters (void)
1315 while (!VEC_empty (same_succ, worklist))
1317 same = VEC_pop (same_succ, worklist);
1318 same->in_worklist = false;
1319 if (dump_file && (dump_flags & TDF_DETAILS))
1321 fprintf (dump_file, "processing worklist entry\n");
1322 same_succ_print (dump_file, same);
1324 find_clusters_1 (same);
1328 /* Create or update a vop phi in BB2. Use VUSE1 arguments for all the
1329 REDIRECTED_EDGES, or if VUSE1 is NULL_TREE, use BB_VOP_AT_EXIT. If a new
1330 phis is created, use the phi instead of VUSE2 in BB2. */
1333 update_vuses (tree vuse1, tree vuse2, basic_block bb2,
1334 VEC (edge,heap) *redirected_edges)
1336 gimple stmt, phi = NULL;
1337 tree lhs = NULL_TREE, arg;
1340 imm_use_iterator iter;
1341 use_operand_p use_p;
1345 def_stmt2 = SSA_NAME_DEF_STMT (vuse2);
1347 if (gimple_bb (def_stmt2) == bb2)
1348 /* Update existing phi. */
1352 /* No need to create a phi with 2 equal arguments. */
1357 lhs = make_ssa_name (SSA_NAME_VAR (vuse2), NULL);
1359 phi = create_phi_node (lhs, bb2);
1360 SSA_NAME_DEF_STMT (lhs) = phi;
1362 /* Set default argument vuse2 for all preds. */
1363 FOR_EACH_EDGE (e, ei, bb2->preds)
1364 add_phi_arg (phi, vuse2, e, UNKNOWN_LOCATION);
1368 for (i = 0; i < EDGE_COUNT (redirected_edges); ++i)
1370 e = VEC_index (edge, redirected_edges, i);
1371 if (vuse1 != NULL_TREE)
1374 arg = BB_VOP_AT_EXIT (e->src);
1375 add_phi_arg (phi, arg, e, UNKNOWN_LOCATION);
1378 /* Return if we updated an existing phi. */
1379 if (gimple_bb (def_stmt2) == bb2)
1382 /* Replace relevant uses of vuse2 with the newly created phi. */
1383 FOR_EACH_IMM_USE_STMT (stmt, iter, vuse2)
1387 if (gimple_code (stmt) != GIMPLE_PHI)
1388 if (gimple_bb (stmt) != bb2)
1391 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1393 if (gimple_code (stmt) == GIMPLE_PHI)
1395 unsigned int pred_index = PHI_ARG_INDEX_FROM_USE (use_p);
1396 basic_block pred = EDGE_PRED (gimple_bb (stmt), pred_index)->src;
1400 SET_USE (use_p, lhs);
1406 /* Returns the vop phi of BB, if any. */
1409 vop_phi (basic_block bb)
1412 gimple_stmt_iterator gsi;
1413 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1415 stmt = gsi_stmt (gsi);
1416 if (is_gimple_reg (gimple_phi_result (stmt)))
1423 /* Returns the vop state at the entry of BB, if found in BB or a successor
1427 vop_at_entry (basic_block bb)
1429 gimple bb_phi, succ_phi;
1430 gimple_stmt_iterator gsi;
1435 bb_phi = vop_phi (bb);
1437 return gimple_phi_result (bb_phi);
1439 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1441 stmt = gsi_stmt (gsi);
1442 vuse = gimple_vuse (stmt);
1443 vdef = gimple_vdef (stmt);
1444 if (vuse != NULL_TREE)
1446 if (vdef != NULL_TREE)
1450 if (EDGE_COUNT (bb->succs) == 0)
1453 succ = EDGE_SUCC (bb, 0)->dest;
1454 succ_phi = vop_phi (succ);
1455 return (succ_phi != NULL
1456 ? PHI_ARG_DEF_FROM_EDGE (succ_phi, find_edge (bb, succ))
1460 /* Redirect all edges from BB1 to BB2, marks BB1 for removal, and if
1461 UPDATE_VOPS, inserts vop phis. */
1464 replace_block_by (basic_block bb1, basic_block bb2, bool update_vops)
1468 tree phi_vuse1 = NULL_TREE, phi_vuse2 = NULL_TREE, arg;
1469 VEC (edge,heap) *redirected_edges = NULL;
1475 /* Find the vops at entry of bb1 and bb2. */
1476 phi_vuse1 = vop_at_entry (bb1);
1477 phi_vuse2 = vop_at_entry (bb2);
1479 /* If one of the 2 not found, it means there's no need to update. */
1480 update_vops = phi_vuse1 != NULL_TREE && phi_vuse2 != NULL_TREE;
1483 if (update_vops && gimple_bb (SSA_NAME_DEF_STMT (phi_vuse1)) == bb1)
1485 /* If the vop at entry of bb1 is a phi, save the phi alternatives in
1486 BB_VOP_AT_EXIT, before we lose that information by redirecting the
1488 FOR_EACH_EDGE (e, ei, bb1->preds)
1490 arg = PHI_ARG_DEF_FROM_EDGE (SSA_NAME_DEF_STMT (phi_vuse1), e);
1491 BB_VOP_AT_EXIT (e->src) = arg;
1496 /* Mark the basic block for later deletion. */
1497 delete_basic_block_same_succ (bb1);
1500 redirected_edges = VEC_alloc (edge, heap, 10);
1502 /* Redirect the incoming edges of bb1 to bb2. */
1503 for (i = EDGE_COUNT (bb1->preds); i > 0 ; --i)
1505 pred_edge = EDGE_PRED (bb1, i - 1);
1506 pred_edge = redirect_edge_and_branch (pred_edge, bb2);
1507 gcc_assert (pred_edge != NULL);
1509 VEC_safe_push (edge, heap, redirected_edges, pred_edge);
1512 /* Update the vops. */
1515 update_vuses (phi_vuse1, phi_vuse2, bb2, redirected_edges);
1516 VEC_free (edge, heap, redirected_edges);
1520 /* Bbs for which update_debug_stmt need to be called. */
1522 static bitmap update_bbs;
1524 /* For each cluster in all_clusters, merge all cluster->bbs. Returns
1525 number of bbs removed. Insert vop phis if UPDATE_VOPS. */
1528 apply_clusters (bool update_vops)
1530 basic_block bb1, bb2;
1534 int nr_bbs_removed = 0;
1536 for (i = 0; i < VEC_length (bb_cluster, all_clusters); ++i)
1538 c = VEC_index (bb_cluster, all_clusters, i);
1543 bitmap_set_bit (update_bbs, bb2->index);
1545 bitmap_clear_bit (c->bbs, bb2->index);
1546 EXECUTE_IF_SET_IN_BITMAP (c->bbs, 0, j, bj)
1548 bb1 = BASIC_BLOCK (j);
1549 bitmap_clear_bit (update_bbs, bb1->index);
1551 replace_block_by (bb1, bb2, update_vops);
1556 return nr_bbs_removed;
1559 /* Resets debug statement STMT if it has uses that are not dominated by their
1563 update_debug_stmt (gimple stmt)
1565 use_operand_p use_p;
1567 basic_block bbdef, bbuse;
1571 if (!gimple_debug_bind_p (stmt))
1574 bbuse = gimple_bb (stmt);
1575 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
1577 name = USE_FROM_PTR (use_p);
1578 gcc_assert (TREE_CODE (name) == SSA_NAME);
1580 def_stmt = SSA_NAME_DEF_STMT (name);
1581 gcc_assert (def_stmt != NULL);
1583 bbdef = gimple_bb (def_stmt);
1584 if (bbdef == NULL || bbuse == bbdef
1585 || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef))
1588 gimple_debug_bind_reset_value (stmt);
1593 /* Resets all debug statements that have uses that are not
1594 dominated by their defs. */
1597 update_debug_stmts (void)
1603 if (!MAY_HAVE_DEBUG_STMTS)
1606 EXECUTE_IF_SET_IN_BITMAP (update_bbs, 0, i, bi)
1609 gimple_stmt_iterator gsi;
1611 bb = BASIC_BLOCK (i);
1612 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1614 stmt = gsi_stmt (gsi);
1615 if (!is_gimple_debug (stmt))
1617 update_debug_stmt (stmt);
1622 /* Runs tail merge optimization. */
1625 tail_merge_optimize (unsigned int todo)
1627 int nr_bbs_removed_total = 0;
1629 bool loop_entered = false;
1630 int iteration_nr = 0;
1631 bool update_vops = !symbol_marked_for_renaming (gimple_vop (cfun));
1632 int max_iterations = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS);
1634 if (!flag_tree_tail_merge || max_iterations == 0)
1637 timevar_push (TV_TREE_TAIL_MERGE);
1639 calculate_dominance_info (CDI_DOMINATORS);
1642 while (!VEC_empty (same_succ, worklist))
1646 loop_entered = true;
1647 alloc_cluster_vectors ();
1648 update_bbs = BITMAP_ALLOC (NULL);
1651 reset_cluster_vectors ();
1654 if (dump_file && (dump_flags & TDF_DETAILS))
1655 fprintf (dump_file, "worklist iteration #%d\n", iteration_nr);
1658 gcc_assert (VEC_empty (same_succ, worklist));
1659 if (VEC_empty (bb_cluster, all_clusters))
1662 nr_bbs_removed = apply_clusters (update_vops);
1663 nr_bbs_removed_total += nr_bbs_removed;
1664 if (nr_bbs_removed == 0)
1667 free_dominance_info (CDI_DOMINATORS);
1670 if (iteration_nr == max_iterations)
1673 calculate_dominance_info (CDI_DOMINATORS);
1677 if (dump_file && (dump_flags & TDF_DETAILS))
1678 fprintf (dump_file, "htab collision / search: %f\n",
1679 htab_collisions (same_succ_htab));
1681 if (nr_bbs_removed_total > 0)
1683 calculate_dominance_info (CDI_DOMINATORS);
1684 update_debug_stmts ();
1686 if (dump_file && (dump_flags & TDF_DETAILS))
1688 fprintf (dump_file, "Before TODOs.\n");
1689 dump_function_to_file (current_function_decl, dump_file, dump_flags);
1692 todo |= (TODO_verify_ssa | TODO_verify_stmts | TODO_verify_flow
1699 delete_cluster_vectors ();
1700 BITMAP_FREE (update_bbs);
1703 timevar_pop (TV_TREE_TAIL_MERGE);