1 /* Tail merging for gimple.
2 Copyright (C) 2011, 2012 Free Software Foundation, Inc.
3 Contributed by Tom de Vries (tom@codesourcery.com)
4
5 This file is part of GCC.
6
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)
10 any later version.
11
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.
16
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/>. */
20
21 /* Pass overview.
22
23
24 MOTIVATIONAL EXAMPLE
25
26 gimple representation of gcc/testsuite/gcc.dg/pr43864.c at
27
28 hprofStartupp (charD.1 * outputFileNameD.2600, charD.1 * ctxD.2601)
29 {
30 struct FILED.1638 * fpD.2605;
31 charD.1 fileNameD.2604[1000];
32 intD.0 D.3915;
33 const charD.1 * restrict outputFileName.0D.3914;
34
35 # BLOCK 2 freq:10000
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);
48 if (D.3915_4 == 0)
49 goto <bb 3>;
50 else
51 goto <bb 4>;
52 # SUCC: 3 [10.0%] (true,exec) 4 [90.0%] (false,exec)
53
54 # BLOCK 3 freq:1000
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));
60 goto <bb 7>;
61 # SUCC: 7 [100.0%] (fallthru,exec)
62
63 # BLOCK 4 freq:9000
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);
70 if (fpD.2605_8 == 0B)
71 goto <bb 5>;
72 else
73 goto <bb 6>;
74 # SUCC: 5 [1.9%] (true,exec) 6 [98.1%] (false,exec)
75
76 # BLOCK 5 freq:173
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));
82 goto <bb 7>;
83 # SUCC: 7 [100.0%] (fallthru,exec)
84
85 # BLOCK 6 freq:8827
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)
92
93 # BLOCK 7 freq:10000
94 # PRED: 3 [100.0%] (fallthru,exec) 5 [100.0%] (fallthru,exec)
95 6 [100.0%] (fallthru,exec)
96 # PT = nonlocal null
97
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),
100 .MEMD.3923_18(6)>
101 # VUSE <.MEMD.3923_11>
102 return ctxD.2601_1;
103 # SUCC: EXIT [100.0%]
104 }
105
106 bb 3 and bb 5 can be merged. The blocks have different predecessors, but the
107 same successors, and the same operations.
108
109
110 CONTEXT
111
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.
119
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.
126
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.
132
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.
136
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.
143
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
150 to merge the blocks.
151
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.
155
156
157 IMPLEMENTATION
158
159 1. The pass first determines all groups of blocks with the same successor
160 blocks.
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.
165
166
167 LIMITATIONS/TODO
168
169 - block only
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.
177
178
179 SWITCHES
180
181 - ftree-tail-merge. On at -O2. We may have to enable it only at -Os. */
182
183 #include "config.h"
184 #include "system.h"
185 #include "coretypes.h"
186 #include "tm.h"
187 #include "tree.h"
188 #include "tm_p.h"
189 #include "basic-block.h"
190 #include "output.h"
191 #include "flags.h"
192 #include "function.h"
193 #include "tree-flow.h"
194 #include "timevar.h"
195 #include "bitmap.h"
196 #include "tree-ssa-alias.h"
197 #include "params.h"
198 #include "tree-pretty-print.h"
199 #include "hashtab.h"
200 #include "gimple-pretty-print.h"
201 #include "tree-ssa-sccvn.h"
202 #include "tree-dump.h"
203
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. */
210
211 struct same_succ_def
212 {
213 /* The bbs that have the same successor bbs. */
214 bitmap bbs;
215 /* The successor bbs. */
216 bitmap succs;
217 /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for
218 bb. */
219 bitmap inverse;
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. */
223 bool in_worklist;
224 /* The hash value of the struct. */
225 hashval_t hashval;
226 };
227 typedef struct same_succ_def *same_succ;
228 typedef const struct same_succ_def *const_same_succ;
229
230 /* A group of bbs where 1 bb from bbs can replace the other bbs. */
231
232 struct bb_cluster_def
233 {
234 /* The bbs in the cluster. */
235 bitmap bbs;
236 /* The preds of the bbs in the cluster. */
237 bitmap preds;
238 /* Index in all_clusters vector. */
239 int index;
240 /* The bb to replace the cluster with. */
241 basic_block rep_bb;
242 };
243 typedef struct bb_cluster_def *bb_cluster;
244 typedef const struct bb_cluster_def *const_bb_cluster;
245
246 /* Per bb-info. */
247
248 struct aux_bb_info
249 {
250 /* The number of non-debug statements in the bb. */
251 int size;
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. */
255 bb_cluster cluster;
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. */
258 tree vop_at_exit;
259 /* The bb that either contains or is dominated by the dependencies of the
260 bb. */
261 basic_block dep_bb;
262 };
263
264 /* Macros to access the fields of struct aux_bb_info. */
265
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)
271
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. */
276
277 static bool
gvn_uses_equal(tree val1,tree val2)278 gvn_uses_equal (tree val1, tree val2)
279 {
280 gcc_checking_assert (val1 != NULL_TREE && val2 != NULL_TREE);
281
282 if (val1 == val2)
283 return true;
284
285 if (vn_valueize (val1) != vn_valueize (val2))
286 return false;
287
288 return ((TREE_CODE (val1) == SSA_NAME || CONSTANT_CLASS_P (val1))
289 && (TREE_CODE (val2) == SSA_NAME || CONSTANT_CLASS_P (val2)));
290 }
291
292 /* Prints E to FILE. */
293
294 static void
same_succ_print(FILE * file,const same_succ e)295 same_succ_print (FILE *file, const same_succ e)
296 {
297 unsigned int i;
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");
305 }
306
307 /* Prints same_succ VE to VFILE. */
308
309 static int
same_succ_print_traverse(void ** ve,void * vfile)310 same_succ_print_traverse (void **ve, void *vfile)
311 {
312 const same_succ e = *((const same_succ *)ve);
313 FILE *file = ((FILE*)vfile);
314 same_succ_print (file, e);
315 return 1;
316 }
317
318 /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */
319
320 static void
update_dep_bb(basic_block use_bb,tree val)321 update_dep_bb (basic_block use_bb, tree val)
322 {
323 basic_block dep_bb;
324
325 /* Not a dep. */
326 if (TREE_CODE (val) != SSA_NAME)
327 return;
328
329 /* Skip use of global def. */
330 if (SSA_NAME_IS_DEFAULT_DEF (val))
331 return;
332
333 /* Skip use of local def. */
334 dep_bb = gimple_bb (SSA_NAME_DEF_STMT (val));
335 if (dep_bb == use_bb)
336 return;
337
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;
341 }
342
343 /* Update BB_DEP_BB, given the dependencies in STMT. */
344
345 static void
stmt_update_dep_bb(gimple stmt)346 stmt_update_dep_bb (gimple stmt)
347 {
348 ssa_op_iter iter;
349 use_operand_p use;
350
351 FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
352 update_dep_bb (gimple_bb (stmt), USE_FROM_PTR (use));
353 }
354
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. */
357
358 static bool
local_def(tree val)359 local_def (tree val)
360 {
361 gimple stmt, def_stmt;
362 basic_block bb, def_bb;
363 imm_use_iterator iter;
364 bool res;
365
366 if (TREE_CODE (val) != SSA_NAME)
367 return false;
368 def_stmt = SSA_NAME_DEF_STMT (val);
369 def_bb = gimple_bb (def_stmt);
370
371 res = true;
372 FOR_EACH_IMM_USE_STMT (stmt, iter, val)
373 {
374 if (is_gimple_debug (stmt))
375 continue;
376 bb = gimple_bb (stmt);
377 if (bb == def_bb)
378 continue;
379 if (gimple_code (stmt) == GIMPLE_PHI
380 && find_edge (def_bb, bb))
381 continue;
382 res = false;
383 BREAK_FROM_IMM_USE_STMT (iter);
384 }
385 return res;
386 }
387
388 /* Calculates hash value for same_succ VE. */
389
390 static hashval_t
same_succ_hash(const void * ve)391 same_succ_hash (const void *ve)
392 {
393 const_same_succ e = (const_same_succ)ve;
394 hashval_t hashval = bitmap_hash (e->succs);
395 int flags;
396 unsigned int i;
397 unsigned int first = bitmap_first_set_bit (e->bbs);
398 basic_block bb = BASIC_BLOCK (first);
399 int size = 0;
400 gimple_stmt_iterator gsi;
401 gimple stmt;
402 tree arg;
403 unsigned int s;
404 bitmap_iterator bs;
405
406 for (gsi = gsi_start_nondebug_bb (bb);
407 !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
408 {
409 stmt = gsi_stmt (gsi);
410 stmt_update_dep_bb (stmt);
411 if (is_gimple_assign (stmt) && local_def (gimple_get_lhs (stmt))
412 && !gimple_has_side_effects (stmt))
413 continue;
414 size++;
415
416 hashval = iterative_hash_hashval_t (gimple_code (stmt), hashval);
417 if (is_gimple_assign (stmt))
418 hashval = iterative_hash_hashval_t (gimple_assign_rhs_code (stmt),
419 hashval);
420 if (!is_gimple_call (stmt))
421 continue;
422 if (gimple_call_internal_p (stmt))
423 hashval = iterative_hash_hashval_t
424 ((hashval_t) gimple_call_internal_fn (stmt), hashval);
425 else
426 hashval = iterative_hash_expr (gimple_call_fn (stmt), hashval);
427 for (i = 0; i < gimple_call_num_args (stmt); i++)
428 {
429 arg = gimple_call_arg (stmt, i);
430 arg = vn_valueize (arg);
431 hashval = iterative_hash_expr (arg, hashval);
432 }
433 }
434
435 hashval = iterative_hash_hashval_t (size, hashval);
436 BB_SIZE (bb) = size;
437
438 for (i = 0; i < VEC_length (int, e->succ_flags); ++i)
439 {
440 flags = VEC_index (int, e->succ_flags, i);
441 flags = flags & ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
442 hashval = iterative_hash_hashval_t (flags, hashval);
443 }
444
445 EXECUTE_IF_SET_IN_BITMAP (e->succs, 0, s, bs)
446 {
447 int n = find_edge (bb, BASIC_BLOCK (s))->dest_idx;
448 for (gsi = gsi_start_phis (BASIC_BLOCK (s)); !gsi_end_p (gsi);
449 gsi_next (&gsi))
450 {
451 gimple phi = gsi_stmt (gsi);
452 tree lhs = gimple_phi_result (phi);
453 tree val = gimple_phi_arg_def (phi, n);
454
455 if (!is_gimple_reg (lhs))
456 continue;
457 update_dep_bb (bb, val);
458 }
459 }
460
461 return hashval;
462 }
463
464 /* Returns true if E1 and E2 have 2 successors, and if the successor flags
465 are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
466 the other edge flags. */
467
468 static bool
inverse_flags(const_same_succ e1,const_same_succ e2)469 inverse_flags (const_same_succ e1, const_same_succ e2)
470 {
471 int f1a, f1b, f2a, f2b;
472 int mask = ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
473
474 if (VEC_length (int, e1->succ_flags) != 2)
475 return false;
476
477 f1a = VEC_index (int, e1->succ_flags, 0);
478 f1b = VEC_index (int, e1->succ_flags, 1);
479 f2a = VEC_index (int, e2->succ_flags, 0);
480 f2b = VEC_index (int, e2->succ_flags, 1);
481
482 if (f1a == f2a && f1b == f2b)
483 return false;
484
485 return (f1a & mask) == (f2a & mask) && (f1b & mask) == (f2b & mask);
486 }
487
488 /* Compares SAME_SUCCs VE1 and VE2. */
489
490 static int
same_succ_equal(const void * ve1,const void * ve2)491 same_succ_equal (const void *ve1, const void *ve2)
492 {
493 const_same_succ e1 = (const_same_succ)ve1;
494 const_same_succ e2 = (const_same_succ)ve2;
495 unsigned int i, first1, first2;
496 gimple_stmt_iterator gsi1, gsi2;
497 gimple s1, s2;
498 basic_block bb1, bb2;
499
500 if (e1->hashval != e2->hashval)
501 return 0;
502
503 if (VEC_length (int, e1->succ_flags) != VEC_length (int, e2->succ_flags))
504 return 0;
505
506 if (!bitmap_equal_p (e1->succs, e2->succs))
507 return 0;
508
509 if (!inverse_flags (e1, e2))
510 {
511 for (i = 0; i < VEC_length (int, e1->succ_flags); ++i)
512 if (VEC_index (int, e1->succ_flags, i)
513 != VEC_index (int, e1->succ_flags, i))
514 return 0;
515 }
516
517 first1 = bitmap_first_set_bit (e1->bbs);
518 first2 = bitmap_first_set_bit (e2->bbs);
519
520 bb1 = BASIC_BLOCK (first1);
521 bb2 = BASIC_BLOCK (first2);
522
523 if (BB_SIZE (bb1) != BB_SIZE (bb2))
524 return 0;
525
526 gsi1 = gsi_start_nondebug_bb (bb1);
527 gsi2 = gsi_start_nondebug_bb (bb2);
528 while (!(gsi_end_p (gsi1) || gsi_end_p (gsi2)))
529 {
530 s1 = gsi_stmt (gsi1);
531 s2 = gsi_stmt (gsi2);
532 if (gimple_code (s1) != gimple_code (s2))
533 return 0;
534 if (is_gimple_call (s1) && !gimple_call_same_target_p (s1, s2))
535 return 0;
536 gsi_next_nondebug (&gsi1);
537 gsi_next_nondebug (&gsi2);
538 }
539
540 return 1;
541 }
542
543 /* Alloc and init a new SAME_SUCC. */
544
545 static same_succ
same_succ_alloc(void)546 same_succ_alloc (void)
547 {
548 same_succ same = XNEW (struct same_succ_def);
549
550 same->bbs = BITMAP_ALLOC (NULL);
551 same->succs = BITMAP_ALLOC (NULL);
552 same->inverse = BITMAP_ALLOC (NULL);
553 same->succ_flags = VEC_alloc (int, heap, 10);
554 same->in_worklist = false;
555
556 return same;
557 }
558
559 /* Delete same_succ VE. */
560
561 static void
same_succ_delete(void * ve)562 same_succ_delete (void *ve)
563 {
564 same_succ e = (same_succ)ve;
565
566 BITMAP_FREE (e->bbs);
567 BITMAP_FREE (e->succs);
568 BITMAP_FREE (e->inverse);
569 VEC_free (int, heap, e->succ_flags);
570
571 XDELETE (ve);
572 }
573
574 /* Reset same_succ SAME. */
575
576 static void
same_succ_reset(same_succ same)577 same_succ_reset (same_succ same)
578 {
579 bitmap_clear (same->bbs);
580 bitmap_clear (same->succs);
581 bitmap_clear (same->inverse);
582 VEC_truncate (int, same->succ_flags, 0);
583 }
584
585 /* Hash table with all same_succ entries. */
586
587 static htab_t same_succ_htab;
588
589 /* Array that is used to store the edge flags for a successor. */
590
591 static int *same_succ_edge_flags;
592
593 /* Bitmap that is used to mark bbs that are recently deleted. */
594
595 static bitmap deleted_bbs;
596
597 /* Bitmap that is used to mark predecessors of bbs that are
598 deleted. */
599
600 static bitmap deleted_bb_preds;
601
602 /* Prints same_succ_htab to stderr. */
603
604 extern void debug_same_succ (void);
605 DEBUG_FUNCTION void
debug_same_succ(void)606 debug_same_succ ( void)
607 {
608 htab_traverse (same_succ_htab, same_succ_print_traverse, stderr);
609 }
610
611 DEF_VEC_P (same_succ);
612 DEF_VEC_ALLOC_P (same_succ, heap);
613
614 /* Vector of bbs to process. */
615
VEC(same_succ,heap)616 static VEC (same_succ, heap) *worklist;
617
618 /* Prints worklist to FILE. */
619
620 static void
621 print_worklist (FILE *file)
622 {
623 unsigned int i;
624 for (i = 0; i < VEC_length (same_succ, worklist); ++i)
625 same_succ_print (file, VEC_index (same_succ, worklist, i));
626 }
627
628 /* Adds SAME to worklist. */
629
630 static void
add_to_worklist(same_succ same)631 add_to_worklist (same_succ same)
632 {
633 if (same->in_worklist)
634 return;
635
636 if (bitmap_count_bits (same->bbs) < 2)
637 return;
638
639 same->in_worklist = true;
640 VEC_safe_push (same_succ, heap, worklist, same);
641 }
642
643 /* Add BB to same_succ_htab. */
644
645 static void
find_same_succ_bb(basic_block bb,same_succ * same_p)646 find_same_succ_bb (basic_block bb, same_succ *same_p)
647 {
648 unsigned int j;
649 bitmap_iterator bj;
650 same_succ same = *same_p;
651 same_succ *slot;
652 edge_iterator ei;
653 edge e;
654
655 if (bb == NULL)
656 return;
657 bitmap_set_bit (same->bbs, bb->index);
658 FOR_EACH_EDGE (e, ei, bb->succs)
659 {
660 int index = e->dest->index;
661 bitmap_set_bit (same->succs, index);
662 same_succ_edge_flags[index] = e->flags;
663 }
664 EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
665 VEC_safe_push (int, heap, same->succ_flags, same_succ_edge_flags[j]);
666
667 same->hashval = same_succ_hash (same);
668
669 slot = (same_succ *) htab_find_slot_with_hash (same_succ_htab, same,
670 same->hashval, INSERT);
671 if (*slot == NULL)
672 {
673 *slot = same;
674 BB_SAME_SUCC (bb) = same;
675 add_to_worklist (same);
676 *same_p = NULL;
677 }
678 else
679 {
680 bitmap_set_bit ((*slot)->bbs, bb->index);
681 BB_SAME_SUCC (bb) = *slot;
682 add_to_worklist (*slot);
683 if (inverse_flags (same, *slot))
684 bitmap_set_bit ((*slot)->inverse, bb->index);
685 same_succ_reset (same);
686 }
687 }
688
689 /* Find bbs with same successors. */
690
691 static void
find_same_succ(void)692 find_same_succ (void)
693 {
694 same_succ same = same_succ_alloc ();
695 basic_block bb;
696
697 FOR_EACH_BB (bb)
698 {
699 find_same_succ_bb (bb, &same);
700 if (same == NULL)
701 same = same_succ_alloc ();
702 }
703
704 same_succ_delete (same);
705 }
706
707 /* Initializes worklist administration. */
708
709 static void
init_worklist(void)710 init_worklist (void)
711 {
712 alloc_aux_for_blocks (sizeof (struct aux_bb_info));
713 same_succ_htab
714 = htab_create (n_basic_blocks, same_succ_hash, same_succ_equal,
715 same_succ_delete);
716 same_succ_edge_flags = XCNEWVEC (int, last_basic_block);
717 deleted_bbs = BITMAP_ALLOC (NULL);
718 deleted_bb_preds = BITMAP_ALLOC (NULL);
719 worklist = VEC_alloc (same_succ, heap, n_basic_blocks);
720 find_same_succ ();
721
722 if (dump_file && (dump_flags & TDF_DETAILS))
723 {
724 fprintf (dump_file, "initial worklist:\n");
725 print_worklist (dump_file);
726 }
727 }
728
729 /* Deletes worklist administration. */
730
731 static void
delete_worklist(void)732 delete_worklist (void)
733 {
734 free_aux_for_blocks ();
735 htab_delete (same_succ_htab);
736 same_succ_htab = NULL;
737 XDELETEVEC (same_succ_edge_flags);
738 same_succ_edge_flags = NULL;
739 BITMAP_FREE (deleted_bbs);
740 BITMAP_FREE (deleted_bb_preds);
741 VEC_free (same_succ, heap, worklist);
742 }
743
744 /* Mark BB as deleted, and mark its predecessors. */
745
746 static void
mark_basic_block_deleted(basic_block bb)747 mark_basic_block_deleted (basic_block bb)
748 {
749 edge e;
750 edge_iterator ei;
751
752 bitmap_set_bit (deleted_bbs, bb->index);
753
754 FOR_EACH_EDGE (e, ei, bb->preds)
755 bitmap_set_bit (deleted_bb_preds, e->src->index);
756 }
757
758 /* Removes BB from its corresponding same_succ. */
759
760 static void
same_succ_flush_bb(basic_block bb)761 same_succ_flush_bb (basic_block bb)
762 {
763 same_succ same = BB_SAME_SUCC (bb);
764 BB_SAME_SUCC (bb) = NULL;
765 if (bitmap_single_bit_set_p (same->bbs))
766 htab_remove_elt_with_hash (same_succ_htab, same, same->hashval);
767 else
768 bitmap_clear_bit (same->bbs, bb->index);
769 }
770
771 /* Removes all bbs in BBS from their corresponding same_succ. */
772
773 static void
same_succ_flush_bbs(bitmap bbs)774 same_succ_flush_bbs (bitmap bbs)
775 {
776 unsigned int i;
777 bitmap_iterator bi;
778
779 EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
780 same_succ_flush_bb (BASIC_BLOCK (i));
781 }
782
783 /* Release the last vdef in BB, either normal or phi result. */
784
785 static void
release_last_vdef(basic_block bb)786 release_last_vdef (basic_block bb)
787 {
788 gimple_stmt_iterator i;
789
790 for (i = gsi_last_bb (bb); !gsi_end_p (i); gsi_prev_nondebug (&i))
791 {
792 gimple stmt = gsi_stmt (i);
793 if (gimple_vdef (stmt) == NULL_TREE)
794 continue;
795
796 mark_virtual_operand_for_renaming (gimple_vdef (stmt));
797 return;
798 }
799
800 for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
801 {
802 gimple phi = gsi_stmt (i);
803 tree res = gimple_phi_result (phi);
804
805 if (is_gimple_reg (res))
806 continue;
807
808 mark_virtual_phi_result_for_renaming (phi);
809 return;
810 }
811
812 }
813
814 /* For deleted_bb_preds, find bbs with same successors. */
815
816 static void
update_worklist(void)817 update_worklist (void)
818 {
819 unsigned int i;
820 bitmap_iterator bi;
821 basic_block bb;
822 same_succ same;
823
824 bitmap_and_compl_into (deleted_bb_preds, deleted_bbs);
825 bitmap_clear (deleted_bbs);
826
827 bitmap_clear_bit (deleted_bb_preds, ENTRY_BLOCK);
828 same_succ_flush_bbs (deleted_bb_preds);
829
830 same = same_succ_alloc ();
831 EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds, 0, i, bi)
832 {
833 bb = BASIC_BLOCK (i);
834 gcc_assert (bb != NULL);
835 find_same_succ_bb (bb, &same);
836 if (same == NULL)
837 same = same_succ_alloc ();
838 }
839 same_succ_delete (same);
840 bitmap_clear (deleted_bb_preds);
841 }
842
843 /* Prints cluster C to FILE. */
844
845 static void
print_cluster(FILE * file,bb_cluster c)846 print_cluster (FILE *file, bb_cluster c)
847 {
848 if (c == NULL)
849 return;
850 bitmap_print (file, c->bbs, "bbs:", "\n");
851 bitmap_print (file, c->preds, "preds:", "\n");
852 }
853
854 /* Prints cluster C to stderr. */
855
856 extern void debug_cluster (bb_cluster);
857 DEBUG_FUNCTION void
debug_cluster(bb_cluster c)858 debug_cluster (bb_cluster c)
859 {
860 print_cluster (stderr, c);
861 }
862
863 /* Update C->rep_bb, given that BB is added to the cluster. */
864
865 static void
update_rep_bb(bb_cluster c,basic_block bb)866 update_rep_bb (bb_cluster c, basic_block bb)
867 {
868 /* Initial. */
869 if (c->rep_bb == NULL)
870 {
871 c->rep_bb = bb;
872 return;
873 }
874
875 /* Current needs no deps, keep it. */
876 if (BB_DEP_BB (c->rep_bb) == NULL)
877 return;
878
879 /* Bb needs no deps, change rep_bb. */
880 if (BB_DEP_BB (bb) == NULL)
881 {
882 c->rep_bb = bb;
883 return;
884 }
885
886 /* Bb needs last deps earlier than current, change rep_bb. A potential
887 problem with this, is that the first deps might also be earlier, which
888 would mean we prefer longer lifetimes for the deps. To be able to check
889 for this, we would have to trace BB_FIRST_DEP_BB as well, besides
890 BB_DEP_BB, which is really BB_LAST_DEP_BB.
891 The benefit of choosing the bb with last deps earlier, is that it can
892 potentially be used as replacement for more bbs. */
893 if (dominated_by_p (CDI_DOMINATORS, BB_DEP_BB (c->rep_bb), BB_DEP_BB (bb)))
894 c->rep_bb = bb;
895 }
896
897 /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
898
899 static void
add_bb_to_cluster(bb_cluster c,basic_block bb)900 add_bb_to_cluster (bb_cluster c, basic_block bb)
901 {
902 edge e;
903 edge_iterator ei;
904
905 bitmap_set_bit (c->bbs, bb->index);
906
907 FOR_EACH_EDGE (e, ei, bb->preds)
908 bitmap_set_bit (c->preds, e->src->index);
909
910 update_rep_bb (c, bb);
911 }
912
913 /* Allocate and init new cluster. */
914
915 static bb_cluster
new_cluster(void)916 new_cluster (void)
917 {
918 bb_cluster c;
919 c = XCNEW (struct bb_cluster_def);
920 c->bbs = BITMAP_ALLOC (NULL);
921 c->preds = BITMAP_ALLOC (NULL);
922 c->rep_bb = NULL;
923 return c;
924 }
925
926 /* Delete clusters. */
927
928 static void
delete_cluster(bb_cluster c)929 delete_cluster (bb_cluster c)
930 {
931 if (c == NULL)
932 return;
933 BITMAP_FREE (c->bbs);
934 BITMAP_FREE (c->preds);
935 XDELETE (c);
936 }
937
938 DEF_VEC_P (bb_cluster);
939 DEF_VEC_ALLOC_P (bb_cluster, heap);
940
941 /* Array that contains all clusters. */
942
VEC(bb_cluster,heap)943 static VEC (bb_cluster, heap) *all_clusters;
944
945 /* Allocate all cluster vectors. */
946
947 static void
948 alloc_cluster_vectors (void)
949 {
950 all_clusters = VEC_alloc (bb_cluster, heap, n_basic_blocks);
951 }
952
953 /* Reset all cluster vectors. */
954
955 static void
reset_cluster_vectors(void)956 reset_cluster_vectors (void)
957 {
958 unsigned int i;
959 basic_block bb;
960 for (i = 0; i < VEC_length (bb_cluster, all_clusters); ++i)
961 delete_cluster (VEC_index (bb_cluster, all_clusters, i));
962 VEC_truncate (bb_cluster, all_clusters, 0);
963 FOR_EACH_BB (bb)
964 BB_CLUSTER (bb) = NULL;
965 }
966
967 /* Delete all cluster vectors. */
968
969 static void
delete_cluster_vectors(void)970 delete_cluster_vectors (void)
971 {
972 unsigned int i;
973 for (i = 0; i < VEC_length (bb_cluster, all_clusters); ++i)
974 delete_cluster (VEC_index (bb_cluster, all_clusters, i));
975 VEC_free (bb_cluster, heap, all_clusters);
976 }
977
978 /* Merge cluster C2 into C1. */
979
980 static void
merge_clusters(bb_cluster c1,bb_cluster c2)981 merge_clusters (bb_cluster c1, bb_cluster c2)
982 {
983 bitmap_ior_into (c1->bbs, c2->bbs);
984 bitmap_ior_into (c1->preds, c2->preds);
985 }
986
987 /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
988 all_clusters, or merge c with existing cluster. */
989
990 static void
set_cluster(basic_block bb1,basic_block bb2)991 set_cluster (basic_block bb1, basic_block bb2)
992 {
993 basic_block merge_bb, other_bb;
994 bb_cluster merge, old, c;
995
996 if (BB_CLUSTER (bb1) == NULL && BB_CLUSTER (bb2) == NULL)
997 {
998 c = new_cluster ();
999 add_bb_to_cluster (c, bb1);
1000 add_bb_to_cluster (c, bb2);
1001 BB_CLUSTER (bb1) = c;
1002 BB_CLUSTER (bb2) = c;
1003 c->index = VEC_length (bb_cluster, all_clusters);
1004 VEC_safe_push (bb_cluster, heap, all_clusters, c);
1005 }
1006 else if (BB_CLUSTER (bb1) == NULL || BB_CLUSTER (bb2) == NULL)
1007 {
1008 merge_bb = BB_CLUSTER (bb1) == NULL ? bb2 : bb1;
1009 other_bb = BB_CLUSTER (bb1) == NULL ? bb1 : bb2;
1010 merge = BB_CLUSTER (merge_bb);
1011 add_bb_to_cluster (merge, other_bb);
1012 BB_CLUSTER (other_bb) = merge;
1013 }
1014 else if (BB_CLUSTER (bb1) != BB_CLUSTER (bb2))
1015 {
1016 unsigned int i;
1017 bitmap_iterator bi;
1018
1019 old = BB_CLUSTER (bb2);
1020 merge = BB_CLUSTER (bb1);
1021 merge_clusters (merge, old);
1022 EXECUTE_IF_SET_IN_BITMAP (old->bbs, 0, i, bi)
1023 BB_CLUSTER (BASIC_BLOCK (i)) = merge;
1024 VEC_replace (bb_cluster, all_clusters, old->index, NULL);
1025 update_rep_bb (merge, old->rep_bb);
1026 delete_cluster (old);
1027 }
1028 else
1029 gcc_unreachable ();
1030 }
1031
1032 /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
1033 gimple_bb (s2) are members of SAME_SUCC. */
1034
1035 static bool
gimple_equal_p(same_succ same_succ,gimple s1,gimple s2)1036 gimple_equal_p (same_succ same_succ, gimple s1, gimple s2)
1037 {
1038 unsigned int i;
1039 tree lhs1, lhs2;
1040 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
1041 tree t1, t2;
1042 bool equal, inv_cond;
1043 enum tree_code code1, code2;
1044
1045 if (gimple_code (s1) != gimple_code (s2))
1046 return false;
1047
1048 switch (gimple_code (s1))
1049 {
1050 case GIMPLE_CALL:
1051 if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
1052 return false;
1053 if (!gimple_call_same_target_p (s1, s2))
1054 return false;
1055
1056 /* Eventually, we'll significantly complicate the CFG by adding
1057 back edges to properly model the effects of transaction restart.
1058 For the bulk of optimization this does not matter, but what we
1059 cannot recover from is tail merging blocks between two separate
1060 transactions. Avoid that by making commit not match. */
1061 if (gimple_call_builtin_p (s1, BUILT_IN_TM_COMMIT))
1062 return false;
1063
1064 equal = true;
1065 for (i = 0; i < gimple_call_num_args (s1); ++i)
1066 {
1067 t1 = gimple_call_arg (s1, i);
1068 t2 = gimple_call_arg (s2, i);
1069 if (operand_equal_p (t1, t2, 0))
1070 continue;
1071 if (gvn_uses_equal (t1, t2))
1072 continue;
1073 equal = false;
1074 break;
1075 }
1076 if (!equal)
1077 return false;
1078
1079 lhs1 = gimple_get_lhs (s1);
1080 lhs2 = gimple_get_lhs (s2);
1081 if (lhs1 == NULL_TREE && lhs2 == NULL_TREE)
1082 return true;
1083 if (lhs1 == NULL_TREE || lhs2 == NULL_TREE)
1084 return false;
1085 if (TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME)
1086 return vn_valueize (lhs1) == vn_valueize (lhs2);
1087 return operand_equal_p (lhs1, lhs2, 0);
1088
1089 case GIMPLE_ASSIGN:
1090 lhs1 = gimple_get_lhs (s1);
1091 lhs2 = gimple_get_lhs (s2);
1092 return (TREE_CODE (lhs1) == SSA_NAME
1093 && TREE_CODE (lhs2) == SSA_NAME
1094 && vn_valueize (lhs1) == vn_valueize (lhs2));
1095
1096 case GIMPLE_COND:
1097 t1 = gimple_cond_lhs (s1);
1098 t2 = gimple_cond_lhs (s2);
1099 if (!operand_equal_p (t1, t2, 0)
1100 && !gvn_uses_equal (t1, t2))
1101 return false;
1102
1103 t1 = gimple_cond_rhs (s1);
1104 t2 = gimple_cond_rhs (s2);
1105 if (!operand_equal_p (t1, t2, 0)
1106 && !gvn_uses_equal (t1, t2))
1107 return false;
1108
1109 code1 = gimple_expr_code (s1);
1110 code2 = gimple_expr_code (s2);
1111 inv_cond = (bitmap_bit_p (same_succ->inverse, bb1->index)
1112 != bitmap_bit_p (same_succ->inverse, bb2->index));
1113 if (inv_cond)
1114 {
1115 bool honor_nans
1116 = HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (s1))));
1117 code2 = invert_tree_comparison (code2, honor_nans);
1118 }
1119 return code1 == code2;
1120
1121 default:
1122 return false;
1123 }
1124 }
1125
1126 /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
1127 Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
1128 processed statements. */
1129
1130 static void
gsi_advance_bw_nondebug_nonlocal(gimple_stmt_iterator * gsi,tree * vuse,bool * vuse_escaped)1131 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse,
1132 bool *vuse_escaped)
1133 {
1134 gimple stmt;
1135 tree lvuse;
1136
1137 while (true)
1138 {
1139 if (gsi_end_p (*gsi))
1140 return;
1141 stmt = gsi_stmt (*gsi);
1142
1143 lvuse = gimple_vuse (stmt);
1144 if (lvuse != NULL_TREE)
1145 {
1146 *vuse = lvuse;
1147 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_DEF))
1148 *vuse_escaped = true;
1149 }
1150
1151 if (!(is_gimple_assign (stmt) && local_def (gimple_get_lhs (stmt))
1152 && !gimple_has_side_effects (stmt)))
1153 return;
1154 gsi_prev_nondebug (gsi);
1155 }
1156 }
1157
1158 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1159 clusters them. */
1160
1161 static void
find_duplicate(same_succ same_succ,basic_block bb1,basic_block bb2)1162 find_duplicate (same_succ same_succ, basic_block bb1, basic_block bb2)
1163 {
1164 gimple_stmt_iterator gsi1 = gsi_last_nondebug_bb (bb1);
1165 gimple_stmt_iterator gsi2 = gsi_last_nondebug_bb (bb2);
1166 tree vuse1 = NULL_TREE, vuse2 = NULL_TREE;
1167 bool vuse_escaped = false;
1168
1169 gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
1170 gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
1171
1172 while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2))
1173 {
1174 if (!gimple_equal_p (same_succ, gsi_stmt (gsi1), gsi_stmt (gsi2)))
1175 return;
1176
1177 gsi_prev_nondebug (&gsi1);
1178 gsi_prev_nondebug (&gsi2);
1179 gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
1180 gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
1181 }
1182
1183 if (!(gsi_end_p (gsi1) && gsi_end_p (gsi2)))
1184 return;
1185
1186 /* If the incoming vuses are not the same, and the vuse escaped into an
1187 SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
1188 which potentially means the semantics of one of the blocks will be changed.
1189 TODO: make this check more precise. */
1190 if (vuse_escaped && vuse1 != vuse2)
1191 return;
1192
1193 if (dump_file)
1194 fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1195 bb1->index, bb2->index);
1196
1197 set_cluster (bb1, bb2);
1198 }
1199
1200 /* Returns whether for all phis in DEST the phi alternatives for E1 and
1201 E2 are equal. */
1202
1203 static bool
same_phi_alternatives_1(basic_block dest,edge e1,edge e2)1204 same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
1205 {
1206 int n1 = e1->dest_idx, n2 = e2->dest_idx;
1207 gimple_stmt_iterator gsi;
1208
1209 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
1210 {
1211 gimple phi = gsi_stmt (gsi);
1212 tree lhs = gimple_phi_result (phi);
1213 tree val1 = gimple_phi_arg_def (phi, n1);
1214 tree val2 = gimple_phi_arg_def (phi, n2);
1215
1216 if (!is_gimple_reg (lhs))
1217 continue;
1218
1219 if (operand_equal_for_phi_arg_p (val1, val2))
1220 continue;
1221 if (gvn_uses_equal (val1, val2))
1222 continue;
1223
1224 return false;
1225 }
1226
1227 return true;
1228 }
1229
1230 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1231 phi alternatives for BB1 and BB2 are equal. */
1232
1233 static bool
same_phi_alternatives(same_succ same_succ,basic_block bb1,basic_block bb2)1234 same_phi_alternatives (same_succ same_succ, basic_block bb1, basic_block bb2)
1235 {
1236 unsigned int s;
1237 bitmap_iterator bs;
1238 edge e1, e2;
1239 basic_block succ;
1240
1241 EXECUTE_IF_SET_IN_BITMAP (same_succ->succs, 0, s, bs)
1242 {
1243 succ = BASIC_BLOCK (s);
1244 e1 = find_edge (bb1, succ);
1245 e2 = find_edge (bb2, succ);
1246 if (e1->flags & EDGE_COMPLEX
1247 || e2->flags & EDGE_COMPLEX)
1248 return false;
1249
1250 /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1251 the same value. */
1252 if (!same_phi_alternatives_1 (succ, e1, e2))
1253 return false;
1254 }
1255
1256 return true;
1257 }
1258
1259 /* Return true if BB has non-vop phis. */
1260
1261 static bool
bb_has_non_vop_phi(basic_block bb)1262 bb_has_non_vop_phi (basic_block bb)
1263 {
1264 gimple_seq phis = phi_nodes (bb);
1265 gimple phi;
1266
1267 if (phis == NULL)
1268 return false;
1269
1270 if (!gimple_seq_singleton_p (phis))
1271 return true;
1272
1273 phi = gimple_seq_first_stmt (phis);
1274 return is_gimple_reg (gimple_phi_result (phi));
1275 }
1276
1277 /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1278 invariant that uses in FROM are dominates by their defs. */
1279
1280 static bool
deps_ok_for_redirect_from_bb_to_bb(basic_block from,basic_block to)1281 deps_ok_for_redirect_from_bb_to_bb (basic_block from, basic_block to)
1282 {
1283 basic_block cd, dep_bb = BB_DEP_BB (to);
1284 edge_iterator ei;
1285 edge e;
1286 bitmap from_preds = BITMAP_ALLOC (NULL);
1287
1288 if (dep_bb == NULL)
1289 return true;
1290
1291 FOR_EACH_EDGE (e, ei, from->preds)
1292 bitmap_set_bit (from_preds, e->src->index);
1293 cd = nearest_common_dominator_for_set (CDI_DOMINATORS, from_preds);
1294 BITMAP_FREE (from_preds);
1295
1296 return dominated_by_p (CDI_DOMINATORS, dep_bb, cd);
1297 }
1298
1299 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1300 replacement bb) and vice versa maintains the invariant that uses in the
1301 replacement are dominates by their defs. */
1302
1303 static bool
deps_ok_for_redirect(basic_block bb1,basic_block bb2)1304 deps_ok_for_redirect (basic_block bb1, basic_block bb2)
1305 {
1306 if (BB_CLUSTER (bb1) != NULL)
1307 bb1 = BB_CLUSTER (bb1)->rep_bb;
1308
1309 if (BB_CLUSTER (bb2) != NULL)
1310 bb2 = BB_CLUSTER (bb2)->rep_bb;
1311
1312 return (deps_ok_for_redirect_from_bb_to_bb (bb1, bb2)
1313 && deps_ok_for_redirect_from_bb_to_bb (bb2, bb1));
1314 }
1315
1316 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1317
1318 static void
find_clusters_1(same_succ same_succ)1319 find_clusters_1 (same_succ same_succ)
1320 {
1321 basic_block bb1, bb2;
1322 unsigned int i, j;
1323 bitmap_iterator bi, bj;
1324 int nr_comparisons;
1325 int max_comparisons = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS);
1326
1327 EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, 0, i, bi)
1328 {
1329 bb1 = BASIC_BLOCK (i);
1330
1331 /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1332 phi-nodes in bb1 and bb2, with the same alternatives for the same
1333 preds. */
1334 if (bb_has_non_vop_phi (bb1))
1335 continue;
1336
1337 nr_comparisons = 0;
1338 EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, i + 1, j, bj)
1339 {
1340 bb2 = BASIC_BLOCK (j);
1341
1342 if (bb_has_non_vop_phi (bb2))
1343 continue;
1344
1345 if (BB_CLUSTER (bb1) != NULL && BB_CLUSTER (bb1) == BB_CLUSTER (bb2))
1346 continue;
1347
1348 /* Limit quadratic behaviour. */
1349 nr_comparisons++;
1350 if (nr_comparisons > max_comparisons)
1351 break;
1352
1353 /* This is a conservative dependency check. We could test more
1354 precise for allowed replacement direction. */
1355 if (!deps_ok_for_redirect (bb1, bb2))
1356 continue;
1357
1358 if (!(same_phi_alternatives (same_succ, bb1, bb2)))
1359 continue;
1360
1361 find_duplicate (same_succ, bb1, bb2);
1362 }
1363 }
1364 }
1365
1366 /* Find clusters of bbs which can be merged. */
1367
1368 static void
find_clusters(void)1369 find_clusters (void)
1370 {
1371 same_succ same;
1372
1373 while (!VEC_empty (same_succ, worklist))
1374 {
1375 same = VEC_pop (same_succ, worklist);
1376 same->in_worklist = false;
1377 if (dump_file && (dump_flags & TDF_DETAILS))
1378 {
1379 fprintf (dump_file, "processing worklist entry\n");
1380 same_succ_print (dump_file, same);
1381 }
1382 find_clusters_1 (same);
1383 }
1384 }
1385
1386 /* Returns the vop phi of BB, if any. */
1387
1388 static gimple
vop_phi(basic_block bb)1389 vop_phi (basic_block bb)
1390 {
1391 gimple stmt;
1392 gimple_stmt_iterator gsi;
1393 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1394 {
1395 stmt = gsi_stmt (gsi);
1396 if (is_gimple_reg (gimple_phi_result (stmt)))
1397 continue;
1398 return stmt;
1399 }
1400 return NULL;
1401 }
1402
1403 /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
1404
1405 static void
replace_block_by(basic_block bb1,basic_block bb2)1406 replace_block_by (basic_block bb1, basic_block bb2)
1407 {
1408 edge pred_edge;
1409 unsigned int i;
1410 gimple bb2_phi;
1411
1412 bb2_phi = vop_phi (bb2);
1413
1414 /* Mark the basic block as deleted. */
1415 mark_basic_block_deleted (bb1);
1416
1417 /* Redirect the incoming edges of bb1 to bb2. */
1418 for (i = EDGE_COUNT (bb1->preds); i > 0 ; --i)
1419 {
1420 pred_edge = EDGE_PRED (bb1, i - 1);
1421 pred_edge = redirect_edge_and_branch (pred_edge, bb2);
1422 gcc_assert (pred_edge != NULL);
1423
1424 if (bb2_phi == NULL)
1425 continue;
1426
1427 /* The phi might have run out of capacity when the redirect added an
1428 argument, which means it could have been replaced. Refresh it. */
1429 bb2_phi = vop_phi (bb2);
1430
1431 add_phi_arg (bb2_phi, SSA_NAME_VAR (gimple_phi_result (bb2_phi)),
1432 pred_edge, UNKNOWN_LOCATION);
1433 }
1434
1435 bb2->frequency += bb1->frequency;
1436 if (bb2->frequency > BB_FREQ_MAX)
1437 bb2->frequency = BB_FREQ_MAX;
1438 bb1->frequency = 0;
1439
1440 /* Do updates that use bb1, before deleting bb1. */
1441 release_last_vdef (bb1);
1442 same_succ_flush_bb (bb1);
1443
1444 delete_basic_block (bb1);
1445 }
1446
1447 /* Bbs for which update_debug_stmt need to be called. */
1448
1449 static bitmap update_bbs;
1450
1451 /* For each cluster in all_clusters, merge all cluster->bbs. Returns
1452 number of bbs removed. */
1453
1454 static int
apply_clusters(void)1455 apply_clusters (void)
1456 {
1457 basic_block bb1, bb2;
1458 bb_cluster c;
1459 unsigned int i, j;
1460 bitmap_iterator bj;
1461 int nr_bbs_removed = 0;
1462
1463 for (i = 0; i < VEC_length (bb_cluster, all_clusters); ++i)
1464 {
1465 c = VEC_index (bb_cluster, all_clusters, i);
1466 if (c == NULL)
1467 continue;
1468
1469 bb2 = c->rep_bb;
1470 bitmap_set_bit (update_bbs, bb2->index);
1471
1472 bitmap_clear_bit (c->bbs, bb2->index);
1473 EXECUTE_IF_SET_IN_BITMAP (c->bbs, 0, j, bj)
1474 {
1475 bb1 = BASIC_BLOCK (j);
1476 bitmap_clear_bit (update_bbs, bb1->index);
1477
1478 replace_block_by (bb1, bb2);
1479 nr_bbs_removed++;
1480 }
1481 }
1482
1483 return nr_bbs_removed;
1484 }
1485
1486 /* Resets debug statement STMT if it has uses that are not dominated by their
1487 defs. */
1488
1489 static void
update_debug_stmt(gimple stmt)1490 update_debug_stmt (gimple stmt)
1491 {
1492 use_operand_p use_p;
1493 ssa_op_iter oi;
1494 basic_block bbdef, bbuse;
1495 gimple def_stmt;
1496 tree name;
1497
1498 if (!gimple_debug_bind_p (stmt))
1499 return;
1500
1501 bbuse = gimple_bb (stmt);
1502 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
1503 {
1504 name = USE_FROM_PTR (use_p);
1505 gcc_assert (TREE_CODE (name) == SSA_NAME);
1506
1507 def_stmt = SSA_NAME_DEF_STMT (name);
1508 gcc_assert (def_stmt != NULL);
1509
1510 bbdef = gimple_bb (def_stmt);
1511 if (bbdef == NULL || bbuse == bbdef
1512 || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef))
1513 continue;
1514
1515 gimple_debug_bind_reset_value (stmt);
1516 update_stmt (stmt);
1517 }
1518 }
1519
1520 /* Resets all debug statements that have uses that are not
1521 dominated by their defs. */
1522
1523 static void
update_debug_stmts(void)1524 update_debug_stmts (void)
1525 {
1526 basic_block bb;
1527 bitmap_iterator bi;
1528 unsigned int i;
1529
1530 EXECUTE_IF_SET_IN_BITMAP (update_bbs, 0, i, bi)
1531 {
1532 gimple stmt;
1533 gimple_stmt_iterator gsi;
1534
1535 bb = BASIC_BLOCK (i);
1536 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1537 {
1538 stmt = gsi_stmt (gsi);
1539 if (!is_gimple_debug (stmt))
1540 continue;
1541 update_debug_stmt (stmt);
1542 }
1543 }
1544 }
1545
1546 /* Runs tail merge optimization. */
1547
1548 unsigned int
tail_merge_optimize(unsigned int todo)1549 tail_merge_optimize (unsigned int todo)
1550 {
1551 int nr_bbs_removed_total = 0;
1552 int nr_bbs_removed;
1553 bool loop_entered = false;
1554 int iteration_nr = 0;
1555 int max_iterations = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS);
1556
1557 if (!flag_tree_tail_merge || max_iterations == 0)
1558 return 0;
1559
1560 timevar_push (TV_TREE_TAIL_MERGE);
1561
1562 if (!dom_info_available_p (CDI_DOMINATORS))
1563 {
1564 /* PRE can leave us with unreachable blocks, remove them now. */
1565 delete_unreachable_blocks ();
1566 calculate_dominance_info (CDI_DOMINATORS);
1567 }
1568 init_worklist ();
1569
1570 while (!VEC_empty (same_succ, worklist))
1571 {
1572 if (!loop_entered)
1573 {
1574 loop_entered = true;
1575 alloc_cluster_vectors ();
1576 update_bbs = BITMAP_ALLOC (NULL);
1577 }
1578 else
1579 reset_cluster_vectors ();
1580
1581 iteration_nr++;
1582 if (dump_file && (dump_flags & TDF_DETAILS))
1583 fprintf (dump_file, "worklist iteration #%d\n", iteration_nr);
1584
1585 find_clusters ();
1586 gcc_assert (VEC_empty (same_succ, worklist));
1587 if (VEC_empty (bb_cluster, all_clusters))
1588 break;
1589
1590 nr_bbs_removed = apply_clusters ();
1591 nr_bbs_removed_total += nr_bbs_removed;
1592 if (nr_bbs_removed == 0)
1593 break;
1594
1595 free_dominance_info (CDI_DOMINATORS);
1596
1597 if (iteration_nr == max_iterations)
1598 break;
1599
1600 calculate_dominance_info (CDI_DOMINATORS);
1601 update_worklist ();
1602 }
1603
1604 if (dump_file && (dump_flags & TDF_DETAILS))
1605 fprintf (dump_file, "htab collision / search: %f\n",
1606 htab_collisions (same_succ_htab));
1607
1608 if (nr_bbs_removed_total > 0)
1609 {
1610 if (MAY_HAVE_DEBUG_STMTS)
1611 {
1612 calculate_dominance_info (CDI_DOMINATORS);
1613 update_debug_stmts ();
1614 }
1615
1616 if (dump_file && (dump_flags & TDF_DETAILS))
1617 {
1618 fprintf (dump_file, "Before TODOs.\n");
1619 dump_function_to_file (current_function_decl, dump_file, dump_flags);
1620 }
1621
1622 todo |= (TODO_verify_ssa | TODO_verify_stmts | TODO_verify_flow
1623 | TODO_dump_func);
1624 mark_sym_for_renaming (gimple_vop (cfun));
1625 }
1626
1627 delete_worklist ();
1628 if (loop_entered)
1629 {
1630 delete_cluster_vectors ();
1631 BITMAP_FREE (update_bbs);
1632 }
1633
1634 timevar_pop (TV_TREE_TAIL_MERGE);
1635
1636 return todo;
1637 }
1638