1/* Tail merging for gimple.
2 Copyright (C) 2011-2017 Free Software Foundation, Inc.
3 Contributed by Tom de Vries (tom@codesourcery.com)
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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 PASS PLACEMENT
180 This 'pass' is not a stand-alone gimple pass, but runs as part of
181 pass_pre, in order to share the value numbering.
182
183
184 SWITCHES
185
186 - ftree-tail-merge. On at -O2. We may have to enable it only at -Os. */
187
188#include "config.h"
189#include "system.h"
190#include "coretypes.h"
191#include "backend.h"
192#include "tree.h"
193#include "gimple.h"
194#include "cfghooks.h"
195#include "tree-pass.h"
196#include "ssa.h"
197#include "fold-const.h"
198#include "trans-mem.h"
199#include "cfganal.h"
200#include "cfgcleanup.h"
201#include "gimple-iterator.h"
202#include "tree-cfg.h"
203#include "tree-into-ssa.h"
204#include "params.h"
205#include "tree-ssa-sccvn.h"
206#include "cfgloop.h"
207#include "tree-eh.h"
208#include "tree-cfgcleanup.h"
209
210const int ignore_edge_flags = EDGE_DFS_BACK | EDGE_EXECUTABLE;
211
212/* Describes a group of bbs with the same successors. The successor bbs are
213 cached in succs, and the successor edge flags are cached in succ_flags.
214 If a bb has the EDGE_TRUE/FALSE_VALUE flags swapped compared to succ_flags,
215 it's marked in inverse.
216 Additionally, the hash value for the struct is cached in hashval, and
217 in_worklist indicates whether it's currently part of worklist. */
218
219struct same_succ : pointer_hash <same_succ>
220{
221 /* The bbs that have the same successor bbs. */
222 bitmap bbs;
223 /* The successor bbs. */
224 bitmap succs;
225 /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for
226 bb. */
227 bitmap inverse;
228 /* The edge flags for each of the successor bbs. */
229 vec<int> succ_flags;
230 /* Indicates whether the struct is currently in the worklist. */
231 bool in_worklist;
232 /* The hash value of the struct. */
233 hashval_t hashval;
234
235 /* hash_table support. */
236 static inline hashval_t hash (const same_succ *);
237 static int equal (const same_succ *, const same_succ *);
238 static void remove (same_succ *);
239};
240
241/* hash routine for hash_table support, returns hashval of E. */
242
243inline hashval_t
244same_succ::hash (const same_succ *e)
245{
246 return e->hashval;
247}
248
249/* A group of bbs where 1 bb from bbs can replace the other bbs. */
250
251struct bb_cluster
252{
253 /* The bbs in the cluster. */
254 bitmap bbs;
255 /* The preds of the bbs in the cluster. */
256 bitmap preds;
257 /* Index in all_clusters vector. */
258 int index;
259 /* The bb to replace the cluster with. */
260 basic_block rep_bb;
261};
262
263/* Per bb-info. */
264
265struct aux_bb_info
266{
267 /* The number of non-debug statements in the bb. */
268 int size;
269 /* The same_succ that this bb is a member of. */
270 same_succ *bb_same_succ;
271 /* The cluster that this bb is a member of. */
272 bb_cluster *cluster;
273 /* The vop state at the exit of a bb. This is shortlived data, used to
274 communicate data between update_block_by and update_vuses. */
275 tree vop_at_exit;
276 /* The bb that either contains or is dominated by the dependencies of the
277 bb. */
278 basic_block dep_bb;
279};
280
281/* Macros to access the fields of struct aux_bb_info. */
282
283#define BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size)
284#define BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ)
285#define BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster)
286#define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
287#define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)
288
289/* Returns true if the only effect a statement STMT has, is to define locally
290 used SSA_NAMEs. */
291
292static bool
293stmt_local_def (gimple *stmt)
294{
295 basic_block bb, def_bb;
296 imm_use_iterator iter;
297 use_operand_p use_p;
298 tree val;
299 def_operand_p def_p;
300
301 if (gimple_vdef (stmt) != NULL_TREE
302 || gimple_has_side_effects (stmt)
303 || gimple_could_trap_p_1 (stmt, false, false)
304 || gimple_vuse (stmt) != NULL_TREE)
305 return false;
306
307 def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
308 if (def_p == NULL)
309 return false;
310
311 val = DEF_FROM_PTR (def_p);
312 if (val == NULL_TREE || TREE_CODE (val) != SSA_NAME)
313 return false;
314
315 def_bb = gimple_bb (stmt);
316
317 FOR_EACH_IMM_USE_FAST (use_p, iter, val)
318 {
319 if (is_gimple_debug (USE_STMT (use_p)))
320 continue;
321 bb = gimple_bb (USE_STMT (use_p));
322 if (bb == def_bb)
323 continue;
324
325 if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI
326 && EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src == def_bb)
327 continue;
328
329 return false;
330 }
331
332 return true;
333}
334
335/* Let GSI skip forwards over local defs. */
336
337static void
338gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator *gsi)
339{
340 gimple *stmt;
341
342 while (true)
343 {
344 if (gsi_end_p (*gsi))
345 return;
346 stmt = gsi_stmt (*gsi);
347 if (!stmt_local_def (stmt))
348 return;
349 gsi_next_nondebug (gsi);
350 }
351}
352
353/* VAL1 and VAL2 are either:
354 - uses in BB1 and BB2, or
355 - phi alternatives for BB1 and BB2.
356 Return true if the uses have the same gvn value. */
357
358static bool
359gvn_uses_equal (tree val1, tree val2)
360{
361 gcc_checking_assert (val1 != NULL_TREE && val2 != NULL_TREE);
362
363 if (val1 == val2)
364 return true;
365
366 if (vn_valueize (val1) != vn_valueize (val2))
367 return false;
368
369 return ((TREE_CODE (val1) == SSA_NAME || CONSTANT_CLASS_P (val1))
370 && (TREE_CODE (val2) == SSA_NAME || CONSTANT_CLASS_P (val2)));
371}
372
373/* Prints E to FILE. */
374
375static void
376same_succ_print (FILE *file, const same_succ *e)
377{
378 unsigned int i;
379 bitmap_print (file, e->bbs, "bbs:", "\n");
380 bitmap_print (file, e->succs, "succs:", "\n");
381 bitmap_print (file, e->inverse, "inverse:", "\n");
382 fprintf (file, "flags:");
383 for (i = 0; i < e->succ_flags.length (); ++i)
384 fprintf (file, " %x", e->succ_flags[i]);
385 fprintf (file, "\n");
386}
387
388/* Prints same_succ VE to VFILE. */
389
390inline int
391ssa_same_succ_print_traverse (same_succ **pe, FILE *file)
392{
393 const same_succ *e = *pe;
394 same_succ_print (file, e);
395 return 1;
396}
397
398/* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */
399
400static void
401update_dep_bb (basic_block use_bb, tree val)
402{
403 basic_block dep_bb;
404
405 /* Not a dep. */
406 if (TREE_CODE (val) != SSA_NAME)
407 return;
408
409 /* Skip use of global def. */
410 if (SSA_NAME_IS_DEFAULT_DEF (val))
411 return;
412
413 /* Skip use of local def. */
414 dep_bb = gimple_bb (SSA_NAME_DEF_STMT (val));
415 if (dep_bb == use_bb)
416 return;
417
418 if (BB_DEP_BB (use_bb) == NULL
419 || dominated_by_p (CDI_DOMINATORS, dep_bb, BB_DEP_BB (use_bb)))
420 BB_DEP_BB (use_bb) = dep_bb;
421}
422
423/* Update BB_DEP_BB, given the dependencies in STMT. */
424
425static void
426stmt_update_dep_bb (gimple *stmt)
427{
428 ssa_op_iter iter;
429 use_operand_p use;
430
431 FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
432 update_dep_bb (gimple_bb (stmt), USE_FROM_PTR (use));
433}
434
435/* Calculates hash value for same_succ VE. */
436
437static hashval_t
438same_succ_hash (const same_succ *e)
439{
440 inchash::hash hstate (bitmap_hash (e->succs));
441 int flags;
442 unsigned int i;
443 unsigned int first = bitmap_first_set_bit (e->bbs);
444 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, first);
445 int size = 0;
446 gimple *stmt;
447 tree arg;
448 unsigned int s;
449 bitmap_iterator bs;
450
451 for (gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
452 !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
453 {
454 stmt = gsi_stmt (gsi);
455 stmt_update_dep_bb (stmt);
456 if (stmt_local_def (stmt))
457 continue;
458 size++;
459
460 hstate.add_int (gimple_code (stmt));
461 if (is_gimple_assign (stmt))
462 hstate.add_int (gimple_assign_rhs_code (stmt));
463 if (!is_gimple_call (stmt))
464 continue;
465 if (gimple_call_internal_p (stmt))
466 hstate.add_int (gimple_call_internal_fn (stmt));
467 else
468 {
469 inchash::add_expr (gimple_call_fn (stmt), hstate);
470 if (gimple_call_chain (stmt))
471 inchash::add_expr (gimple_call_chain (stmt), hstate);
472 }
473 for (i = 0; i < gimple_call_num_args (stmt); i++)
474 {
475 arg = gimple_call_arg (stmt, i);
476 arg = vn_valueize (arg);
477 inchash::add_expr (arg, hstate);
478 }
479 }
480
481 hstate.add_int (size);
482 BB_SIZE (bb) = size;
483
484 hstate.add_int (bb->loop_father->num);
485
486 for (i = 0; i < e->succ_flags.length (); ++i)
487 {
488 flags = e->succ_flags[i];
489 flags = flags & ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
490 hstate.add_int (flags);
491 }
492
493 EXECUTE_IF_SET_IN_BITMAP (e->succs, 0, s, bs)
494 {
495 int n = find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, s))->dest_idx;
496 for (gphi_iterator gsi = gsi_start_phis (BASIC_BLOCK_FOR_FN (cfun, s));
497 !gsi_end_p (gsi);
498 gsi_next (&gsi))
499 {
500 gphi *phi = gsi.phi ();
501 tree lhs = gimple_phi_result (phi);
502 tree val = gimple_phi_arg_def (phi, n);
503
504 if (virtual_operand_p (lhs))
505 continue;
506 update_dep_bb (bb, val);
507 }
508 }
509
510 return hstate.end ();
511}
512
513/* Returns true if E1 and E2 have 2 successors, and if the successor flags
514 are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
515 the other edge flags. */
516
517static bool
518inverse_flags (const same_succ *e1, const same_succ *e2)
519{
520 int f1a, f1b, f2a, f2b;
521 int mask = ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
522
523 if (e1->succ_flags.length () != 2)
524 return false;
525
526 f1a = e1->succ_flags[0];
527 f1b = e1->succ_flags[1];
528 f2a = e2->succ_flags[0];
529 f2b = e2->succ_flags[1];
530
531 if (f1a == f2a && f1b == f2b)
532 return false;
533
534 return (f1a & mask) == (f2a & mask) && (f1b & mask) == (f2b & mask);
535}
536
537/* Compares SAME_SUCCs E1 and E2. */
538
539int
540same_succ::equal (const same_succ *e1, const same_succ *e2)
541{
542 unsigned int i, first1, first2;
543 gimple_stmt_iterator gsi1, gsi2;
544 gimple *s1, *s2;
545 basic_block bb1, bb2;
546
547 if (e1 == e2)
548 return 1;
549
550 if (e1->hashval != e2->hashval)
551 return 0;
552
553 if (e1->succ_flags.length () != e2->succ_flags.length ())
554 return 0;
555
556 if (!bitmap_equal_p (e1->succs, e2->succs))
557 return 0;
558
559 if (!inverse_flags (e1, e2))
560 {
561 for (i = 0; i < e1->succ_flags.length (); ++i)
562 if (e1->succ_flags[i] != e2->succ_flags[i])
563 return 0;
564 }
565
566 first1 = bitmap_first_set_bit (e1->bbs);
567 first2 = bitmap_first_set_bit (e2->bbs);
568
569 bb1 = BASIC_BLOCK_FOR_FN (cfun, first1);
570 bb2 = BASIC_BLOCK_FOR_FN (cfun, first2);
571
572 if (BB_SIZE (bb1) != BB_SIZE (bb2))
573 return 0;
574
575 if (bb1->loop_father != bb2->loop_father)
576 return 0;
577
578 gsi1 = gsi_start_nondebug_bb (bb1);
579 gsi2 = gsi_start_nondebug_bb (bb2);
580 gsi_advance_fw_nondebug_nonlocal (&gsi1);
581 gsi_advance_fw_nondebug_nonlocal (&gsi2);
582 while (!(gsi_end_p (gsi1) || gsi_end_p (gsi2)))
583 {
584 s1 = gsi_stmt (gsi1);
585 s2 = gsi_stmt (gsi2);
586 if (gimple_code (s1) != gimple_code (s2))
587 return 0;
588 if (is_gimple_call (s1) && !gimple_call_same_target_p (s1, s2))
589 return 0;
590 gsi_next_nondebug (&gsi1);
591 gsi_next_nondebug (&gsi2);
592 gsi_advance_fw_nondebug_nonlocal (&gsi1);
593 gsi_advance_fw_nondebug_nonlocal (&gsi2);
594 }
595
596 return 1;
597}
598
599/* Alloc and init a new SAME_SUCC. */
600
601static same_succ *
602same_succ_alloc (void)
603{
604 same_succ *same = XNEW (struct same_succ);
605
606 same->bbs = BITMAP_ALLOC (NULL);
607 same->succs = BITMAP_ALLOC (NULL);
608 same->inverse = BITMAP_ALLOC (NULL);
609 same->succ_flags.create (10);
610 same->in_worklist = false;
611
612 return same;
613}
614
615/* Delete same_succ E. */
616
617void
618same_succ::remove (same_succ *e)
619{
620 BITMAP_FREE (e->bbs);
621 BITMAP_FREE (e->succs);
622 BITMAP_FREE (e->inverse);
623 e->succ_flags.release ();
624
625 XDELETE (e);
626}
627
628/* Reset same_succ SAME. */
629
630static void
631same_succ_reset (same_succ *same)
632{
633 bitmap_clear (same->bbs);
634 bitmap_clear (same->succs);
635 bitmap_clear (same->inverse);
636 same->succ_flags.truncate (0);
637}
638
639static hash_table<same_succ> *same_succ_htab;
640
641/* Array that is used to store the edge flags for a successor. */
642
643static int *same_succ_edge_flags;
644
645/* Bitmap that is used to mark bbs that are recently deleted. */
646
647static bitmap deleted_bbs;
648
649/* Bitmap that is used to mark predecessors of bbs that are
650 deleted. */
651
652static bitmap deleted_bb_preds;
653
654/* Prints same_succ_htab to stderr. */
655
656extern void debug_same_succ (void);
657DEBUG_FUNCTION void
658debug_same_succ ( void)
659{
660 same_succ_htab->traverse <FILE *, ssa_same_succ_print_traverse> (stderr);
661}
662
663
664/* Vector of bbs to process. */
665
666static vec<same_succ *> worklist;
667
668/* Prints worklist to FILE. */
669
670static void
671print_worklist (FILE *file)
672{
673 unsigned int i;
674 for (i = 0; i < worklist.length (); ++i)
675 same_succ_print (file, worklist[i]);
676}
677
678/* Adds SAME to worklist. */
679
680static void
681add_to_worklist (same_succ *same)
682{
683 if (same->in_worklist)
684 return;
685
686 if (bitmap_count_bits (same->bbs) < 2)
687 return;
688
689 same->in_worklist = true;
690 worklist.safe_push (same);
691}
692
693/* Add BB to same_succ_htab. */
694
695static void
696find_same_succ_bb (basic_block bb, same_succ **same_p)
697{
698 unsigned int j;
699 bitmap_iterator bj;
700 same_succ *same = *same_p;
701 same_succ **slot;
702 edge_iterator ei;
703 edge e;
704
705 if (bb == NULL)
706 return;
707 bitmap_set_bit (same->bbs, bb->index);
708 FOR_EACH_EDGE (e, ei, bb->succs)
709 {
710 int index = e->dest->index;
711 bitmap_set_bit (same->succs, index);
712 same_succ_edge_flags[index] = (e->flags & ~ignore_edge_flags);
713 }
714 EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
715 same->succ_flags.safe_push (same_succ_edge_flags[j]);
716
717 same->hashval = same_succ_hash (same);
718
719 slot = same_succ_htab->find_slot_with_hash (same, same->hashval, INSERT);
720 if (*slot == NULL)
721 {
722 *slot = same;
723 BB_SAME_SUCC (bb) = same;
724 add_to_worklist (same);
725 *same_p = NULL;
726 }
727 else
728 {
729 bitmap_set_bit ((*slot)->bbs, bb->index);
730 BB_SAME_SUCC (bb) = *slot;
731 add_to_worklist (*slot);
732 if (inverse_flags (same, *slot))
733 bitmap_set_bit ((*slot)->inverse, bb->index);
734 same_succ_reset (same);
735 }
736}
737
738/* Find bbs with same successors. */
739
740static void
741find_same_succ (void)
742{
743 same_succ *same = same_succ_alloc ();
744 basic_block bb;
745
746 FOR_EACH_BB_FN (bb, cfun)
747 {
748 find_same_succ_bb (bb, &same);
749 if (same == NULL)
750 same = same_succ_alloc ();
751 }
752
753 same_succ::remove (same);
754}
755
756/* Initializes worklist administration. */
757
758static void
759init_worklist (void)
760{
761 alloc_aux_for_blocks (sizeof (struct aux_bb_info));
762 same_succ_htab = new hash_table<same_succ> (n_basic_blocks_for_fn (cfun));
763 same_succ_edge_flags = XCNEWVEC (int, last_basic_block_for_fn (cfun));
764 deleted_bbs = BITMAP_ALLOC (NULL);
765 deleted_bb_preds = BITMAP_ALLOC (NULL);
766 worklist.create (n_basic_blocks_for_fn (cfun));
767 find_same_succ ();
768
769 if (dump_file && (dump_flags & TDF_DETAILS))
770 {
771 fprintf (dump_file, "initial worklist:\n");
772 print_worklist (dump_file);
773 }
774}
775
776/* Deletes worklist administration. */
777
778static void
779delete_worklist (void)
780{
781 free_aux_for_blocks ();
782 delete same_succ_htab;
783 same_succ_htab = NULL;
784 XDELETEVEC (same_succ_edge_flags);
785 same_succ_edge_flags = NULL;
786 BITMAP_FREE (deleted_bbs);
787 BITMAP_FREE (deleted_bb_preds);
788 worklist.release ();
789}
790
791/* Mark BB as deleted, and mark its predecessors. */
792
793static void
794mark_basic_block_deleted (basic_block bb)
795{
796 edge e;
797 edge_iterator ei;
798
799 bitmap_set_bit (deleted_bbs, bb->index);
800
801 FOR_EACH_EDGE (e, ei, bb->preds)
802 bitmap_set_bit (deleted_bb_preds, e->src->index);
803}
804
805/* Removes BB from its corresponding same_succ. */
806
807static void
808same_succ_flush_bb (basic_block bb)
809{
810 same_succ *same = BB_SAME_SUCC (bb);
811 if (! same)
812 return;
813
814 BB_SAME_SUCC (bb) = NULL;
815 if (bitmap_single_bit_set_p (same->bbs))
816 same_succ_htab->remove_elt_with_hash (same, same->hashval);
817 else
818 bitmap_clear_bit (same->bbs, bb->index);
819}
820
821/* Removes all bbs in BBS from their corresponding same_succ. */
822
823static void
824same_succ_flush_bbs (bitmap bbs)
825{
826 unsigned int i;
827 bitmap_iterator bi;
828
829 EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
830 same_succ_flush_bb (BASIC_BLOCK_FOR_FN (cfun, i));
831}
832
833/* Release the last vdef in BB, either normal or phi result. */
834
835static void
836release_last_vdef (basic_block bb)
837{
838 for (gimple_stmt_iterator i = gsi_last_bb (bb); !gsi_end_p (i);
839 gsi_prev_nondebug (&i))
840 {
841 gimple *stmt = gsi_stmt (i);
842 if (gimple_vdef (stmt) == NULL_TREE)
843 continue;
844
845 mark_virtual_operand_for_renaming (gimple_vdef (stmt));
846 return;
847 }
848
849 for (gphi_iterator i = gsi_start_phis (bb); !gsi_end_p (i);
850 gsi_next (&i))
851 {
852 gphi *phi = i.phi ();
853 tree res = gimple_phi_result (phi);
854
855 if (!virtual_operand_p (res))
856 continue;
857
858 mark_virtual_phi_result_for_renaming (phi);
859 return;
860 }
861}
862
863/* For deleted_bb_preds, find bbs with same successors. */
864
865static void
866update_worklist (void)
867{
868 unsigned int i;
869 bitmap_iterator bi;
870 basic_block bb;
871 same_succ *same;
872
873 bitmap_and_compl_into (deleted_bb_preds, deleted_bbs);
874 bitmap_clear (deleted_bbs);
875
876 bitmap_clear_bit (deleted_bb_preds, ENTRY_BLOCK);
877 same_succ_flush_bbs (deleted_bb_preds);
878
879 same = same_succ_alloc ();
880 EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds, 0, i, bi)
881 {
882 bb = BASIC_BLOCK_FOR_FN (cfun, i);
883 gcc_assert (bb != NULL);
884 find_same_succ_bb (bb, &same);
885 if (same == NULL)
886 same = same_succ_alloc ();
887 }
888 same_succ::remove (same);
889 bitmap_clear (deleted_bb_preds);
890}
891
892/* Prints cluster C to FILE. */
893
894static void
895print_cluster (FILE *file, bb_cluster *c)
896{
897 if (c == NULL)
898 return;
899 bitmap_print (file, c->bbs, "bbs:", "\n");
900 bitmap_print (file, c->preds, "preds:", "\n");
901}
902
903/* Prints cluster C to stderr. */
904
905extern void debug_cluster (bb_cluster *);
906DEBUG_FUNCTION void
907debug_cluster (bb_cluster *c)
908{
909 print_cluster (stderr, c);
910}
911
912/* Update C->rep_bb, given that BB is added to the cluster. */
913
914static void
915update_rep_bb (bb_cluster *c, basic_block bb)
916{
917 /* Initial. */
918 if (c->rep_bb == NULL)
919 {
920 c->rep_bb = bb;
921 return;
922 }
923
924 /* Current needs no deps, keep it. */
925 if (BB_DEP_BB (c->rep_bb) == NULL)
926 return;
927
928 /* Bb needs no deps, change rep_bb. */
929 if (BB_DEP_BB (bb) == NULL)
930 {
931 c->rep_bb = bb;
932 return;
933 }
934
935 /* Bb needs last deps earlier than current, change rep_bb. A potential
936 problem with this, is that the first deps might also be earlier, which
937 would mean we prefer longer lifetimes for the deps. To be able to check
938 for this, we would have to trace BB_FIRST_DEP_BB as well, besides
939 BB_DEP_BB, which is really BB_LAST_DEP_BB.
940 The benefit of choosing the bb with last deps earlier, is that it can
941 potentially be used as replacement for more bbs. */
942 if (dominated_by_p (CDI_DOMINATORS, BB_DEP_BB (c->rep_bb), BB_DEP_BB (bb)))
943 c->rep_bb = bb;
944}
945
946/* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
947
948static void
949add_bb_to_cluster (bb_cluster *c, basic_block bb)
950{
951 edge e;
952 edge_iterator ei;
953
954 bitmap_set_bit (c->bbs, bb->index);
955
956 FOR_EACH_EDGE (e, ei, bb->preds)
957 bitmap_set_bit (c->preds, e->src->index);
958
959 update_rep_bb (c, bb);
960}
961
962/* Allocate and init new cluster. */
963
964static bb_cluster *
965new_cluster (void)
966{
967 bb_cluster *c;
968 c = XCNEW (bb_cluster);
969 c->bbs = BITMAP_ALLOC (NULL);
970 c->preds = BITMAP_ALLOC (NULL);
971 c->rep_bb = NULL;
972 return c;
973}
974
975/* Delete clusters. */
976
977static void
978delete_cluster (bb_cluster *c)
979{
980 if (c == NULL)
981 return;
982 BITMAP_FREE (c->bbs);
983 BITMAP_FREE (c->preds);
984 XDELETE (c);
985}
986
987
988/* Array that contains all clusters. */
989
990static vec<bb_cluster *> all_clusters;
991
992/* Allocate all cluster vectors. */
993
994static void
995alloc_cluster_vectors (void)
996{
997 all_clusters.create (n_basic_blocks_for_fn (cfun));
998}
999
1000/* Reset all cluster vectors. */
1001
1002static void
1003reset_cluster_vectors (void)
1004{
1005 unsigned int i;
1006 basic_block bb;
1007 for (i = 0; i < all_clusters.length (); ++i)
1008 delete_cluster (all_clusters[i]);
1009 all_clusters.truncate (0);
1010 FOR_EACH_BB_FN (bb, cfun)
1011 BB_CLUSTER (bb) = NULL;
1012}
1013
1014/* Delete all cluster vectors. */
1015
1016static void
1017delete_cluster_vectors (void)
1018{
1019 unsigned int i;
1020 for (i = 0; i < all_clusters.length (); ++i)
1021 delete_cluster (all_clusters[i]);
1022 all_clusters.release ();
1023}
1024
1025/* Merge cluster C2 into C1. */
1026
1027static void
1028merge_clusters (bb_cluster *c1, bb_cluster *c2)
1029{
1030 bitmap_ior_into (c1->bbs, c2->bbs);
1031 bitmap_ior_into (c1->preds, c2->preds);
1032}
1033
1034/* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
1035 all_clusters, or merge c with existing cluster. */
1036
1037static void
1038set_cluster (basic_block bb1, basic_block bb2)
1039{
1040 basic_block merge_bb, other_bb;
1041 bb_cluster *merge, *old, *c;
1042
1043 if (BB_CLUSTER (bb1) == NULL && BB_CLUSTER (bb2) == NULL)
1044 {
1045 c = new_cluster ();
1046 add_bb_to_cluster (c, bb1);
1047 add_bb_to_cluster (c, bb2);
1048 BB_CLUSTER (bb1) = c;
1049 BB_CLUSTER (bb2) = c;
1050 c->index = all_clusters.length ();
1051 all_clusters.safe_push (c);
1052 }
1053 else if (BB_CLUSTER (bb1) == NULL || BB_CLUSTER (bb2) == NULL)
1054 {
1055 merge_bb = BB_CLUSTER (bb1) == NULL ? bb2 : bb1;
1056 other_bb = BB_CLUSTER (bb1) == NULL ? bb1 : bb2;
1057 merge = BB_CLUSTER (merge_bb);
1058 add_bb_to_cluster (merge, other_bb);
1059 BB_CLUSTER (other_bb) = merge;
1060 }
1061 else if (BB_CLUSTER (bb1) != BB_CLUSTER (bb2))
1062 {
1063 unsigned int i;
1064 bitmap_iterator bi;
1065
1066 old = BB_CLUSTER (bb2);
1067 merge = BB_CLUSTER (bb1);
1068 merge_clusters (merge, old);
1069 EXECUTE_IF_SET_IN_BITMAP (old->bbs, 0, i, bi)
1070 BB_CLUSTER (BASIC_BLOCK_FOR_FN (cfun, i)) = merge;
1071 all_clusters[old->index] = NULL;
1072 update_rep_bb (merge, old->rep_bb);
1073 delete_cluster (old);
1074 }
1075 else
1076 gcc_unreachable ();
1077}
1078
1079/* Return true if gimple operands T1 and T2 have the same value. */
1080
1081static bool
1082gimple_operand_equal_value_p (tree t1, tree t2)
1083{
1084 if (t1 == t2)
1085 return true;
1086
1087 if (t1 == NULL_TREE
1088 || t2 == NULL_TREE)
1089 return false;
1090
1091 if (operand_equal_p (t1, t2, OEP_MATCH_SIDE_EFFECTS))
1092 return true;
1093
1094 return gvn_uses_equal (t1, t2);
1095}
1096
1097/* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
1098 gimple_bb (s2) are members of SAME_SUCC. */
1099
1100static bool
1101gimple_equal_p (same_succ *same_succ, gimple *s1, gimple *s2)
1102{
1103 unsigned int i;
1104 tree lhs1, lhs2;
1105 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
1106 tree t1, t2;
1107 bool inv_cond;
1108 enum tree_code code1, code2;
1109
1110 if (gimple_code (s1) != gimple_code (s2))
1111 return false;
1112
1113 switch (gimple_code (s1))
1114 {
1115 case GIMPLE_CALL:
1116 if (!gimple_call_same_target_p (s1, s2))
1117 return false;
1118
1119 t1 = gimple_call_chain (s1);
1120 t2 = gimple_call_chain (s2);
1121 if (!gimple_operand_equal_value_p (t1, t2))
1122 return false;
1123
1124 if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
1125 return false;
1126
1127 for (i = 0; i < gimple_call_num_args (s1); ++i)
1128 {
1129 t1 = gimple_call_arg (s1, i);
1130 t2 = gimple_call_arg (s2, i);
1131 if (!gimple_operand_equal_value_p (t1, t2))
1132 return false;
1133 }
1134
1135 lhs1 = gimple_get_lhs (s1);
1136 lhs2 = gimple_get_lhs (s2);
1137 if (lhs1 == NULL_TREE && lhs2 == NULL_TREE)
1138 return true;
1139 if (lhs1 == NULL_TREE || lhs2 == NULL_TREE)
1140 return false;
1141 if (TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME)
1142 return vn_valueize (lhs1) == vn_valueize (lhs2);
1143 return operand_equal_p (lhs1, lhs2, 0);
1144
1145 case GIMPLE_ASSIGN:
1146 lhs1 = gimple_get_lhs (s1);
1147 lhs2 = gimple_get_lhs (s2);
1148 if (TREE_CODE (lhs1) != SSA_NAME
1149 && TREE_CODE (lhs2) != SSA_NAME)
1150 return (operand_equal_p (lhs1, lhs2, 0)
1151 && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1),
1152 gimple_assign_rhs1 (s2)));
1153 else if (TREE_CODE (lhs1) == SSA_NAME
1154 && TREE_CODE (lhs2) == SSA_NAME)
1155 return operand_equal_p (gimple_assign_rhs1 (s1),
1156 gimple_assign_rhs1 (s2), 0);
1157 return false;
1158
1159 case GIMPLE_COND:
1160 t1 = gimple_cond_lhs (s1);
1161 t2 = gimple_cond_lhs (s2);
1162 if (!gimple_operand_equal_value_p (t1, t2))
1163 return false;
1164
1165 t1 = gimple_cond_rhs (s1);
1166 t2 = gimple_cond_rhs (s2);
1167 if (!gimple_operand_equal_value_p (t1, t2))
1168 return false;
1169
1170 code1 = gimple_expr_code (s1);
1171 code2 = gimple_expr_code (s2);
1172 inv_cond = (bitmap_bit_p (same_succ->inverse, bb1->index)
1173 != bitmap_bit_p (same_succ->inverse, bb2->index));
1174 if (inv_cond)
1175 {
1176 bool honor_nans = HONOR_NANS (t1);
1177 code2 = invert_tree_comparison (code2, honor_nans);
1178 }
1179 return code1 == code2;
1180
1181 default:
1182 return false;
1183 }
1184}
1185
1186/* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
1187 Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
1188 processed statements. */
1189
1190static void
1191gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse,
1192 bool *vuse_escaped)
1193{
1194 gimple *stmt;
1195 tree lvuse;
1196
1197 while (true)
1198 {
1199 if (gsi_end_p (*gsi))
1200 return;
1201 stmt = gsi_stmt (*gsi);
1202
1203 lvuse = gimple_vuse (stmt);
1204 if (lvuse != NULL_TREE)
1205 {
1206 *vuse = lvuse;
1207 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_DEF))
1208 *vuse_escaped = true;
1209 }
1210
1211 if (!stmt_local_def (stmt))
1212 return;
1213 gsi_prev_nondebug (gsi);
1214 }
1215}
1216
1217/* Return true if equal (in the sense of gimple_equal_p) statements STMT1 and
1218 STMT2 are allowed to be merged. */
1219
1220static bool
1221merge_stmts_p (gimple *stmt1, gimple *stmt2)
1222{
1223 /* What could be better than this here is to blacklist the bb
1224 containing the stmt, when encountering the stmt f.i. in
1225 same_succ_hash. */
1226 if (is_tm_ending (stmt1))
1227 return false;
1228
1229 /* Verify EH landing pads. */
1230 if (lookup_stmt_eh_lp_fn (cfun, stmt1) != lookup_stmt_eh_lp_fn (cfun, stmt2))
1231 return false;
1232
1233 if (is_gimple_call (stmt1)
1234 && gimple_call_internal_p (stmt1))
1235 switch (gimple_call_internal_fn (stmt1))
1236 {
1237 case IFN_UBSAN_NULL:
1238 case IFN_UBSAN_BOUNDS:
1239 case IFN_UBSAN_VPTR:
1240 case IFN_UBSAN_CHECK_ADD:
1241 case IFN_UBSAN_CHECK_SUB:
1242 case IFN_UBSAN_CHECK_MUL:
1243 case IFN_UBSAN_OBJECT_SIZE:
1244 case IFN_UBSAN_PTR:
1245 case IFN_ASAN_CHECK:
1246 /* For these internal functions, gimple_location is an implicit
1247 parameter, which will be used explicitly after expansion.
1248 Merging these statements may cause confusing line numbers in
1249 sanitizer messages. */
1250 return gimple_location (stmt1) == gimple_location (stmt2);
1251 default:
1252 break;
1253 }
1254
1255 return true;
1256}
1257
1258/* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1259 clusters them. */
1260
1261static void
1262find_duplicate (same_succ *same_succ, basic_block bb1, basic_block bb2)
1263{
1264 gimple_stmt_iterator gsi1 = gsi_last_nondebug_bb (bb1);
1265 gimple_stmt_iterator gsi2 = gsi_last_nondebug_bb (bb2);
1266 tree vuse1 = NULL_TREE, vuse2 = NULL_TREE;
1267 bool vuse_escaped = false;
1268
1269 gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
1270 gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
1271
1272 while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2))
1273 {
1274 gimple *stmt1 = gsi_stmt (gsi1);
1275 gimple *stmt2 = gsi_stmt (gsi2);
1276
1277 if (gimple_code (stmt1) == GIMPLE_LABEL
1278 && gimple_code (stmt2) == GIMPLE_LABEL)
1279 break;
1280
1281 if (!gimple_equal_p (same_succ, stmt1, stmt2))
1282 return;
1283
1284 if (!merge_stmts_p (stmt1, stmt2))
1285 return;
1286
1287 gsi_prev_nondebug (&gsi1);
1288 gsi_prev_nondebug (&gsi2);
1289 gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
1290 gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
1291 }
1292
1293 while (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
1294 {
1295 tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1)));
1296 if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
1297 return;
1298 gsi_prev_nondebug (&gsi1);
1299 }
1300 while (!gsi_end_p (gsi2) && gimple_code (gsi_stmt (gsi2)) == GIMPLE_LABEL)
1301 {
1302 tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi2)));
1303 if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
1304 return;
1305 gsi_prev_nondebug (&gsi2);
1306 }
1307 if (!(gsi_end_p (gsi1) && gsi_end_p (gsi2)))
1308 return;
1309
1310 /* If the incoming vuses are not the same, and the vuse escaped into an
1311 SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
1312 which potentially means the semantics of one of the blocks will be changed.
1313 TODO: make this check more precise. */
1314 if (vuse_escaped && vuse1 != vuse2)
1315 return;
1316
1317 if (dump_file)
1318 fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1319 bb1->index, bb2->index);
1320
1321 set_cluster (bb1, bb2);
1322}
1323
1324/* Returns whether for all phis in DEST the phi alternatives for E1 and
1325 E2 are equal. */
1326
1327static bool
1328same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
1329{
1330 int n1 = e1->dest_idx, n2 = e2->dest_idx;
1331 gphi_iterator gsi;
1332
1333 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
1334 {
1335 gphi *phi = gsi.phi ();
1336 tree lhs = gimple_phi_result (phi);
1337 tree val1 = gimple_phi_arg_def (phi, n1);
1338 tree val2 = gimple_phi_arg_def (phi, n2);
1339
1340 if (virtual_operand_p (lhs))
1341 continue;
1342
1343 if (operand_equal_for_phi_arg_p (val1, val2))
1344 continue;
1345 if (gvn_uses_equal (val1, val2))
1346 continue;
1347
1348 return false;
1349 }
1350
1351 return true;
1352}
1353
1354/* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1355 phi alternatives for BB1 and BB2 are equal. */
1356
1357static bool
1358same_phi_alternatives (same_succ *same_succ, basic_block bb1, basic_block bb2)
1359{
1360 unsigned int s;
1361 bitmap_iterator bs;
1362 edge e1, e2;
1363 basic_block succ;
1364
1365 EXECUTE_IF_SET_IN_BITMAP (same_succ->succs, 0, s, bs)
1366 {
1367 succ = BASIC_BLOCK_FOR_FN (cfun, s);
1368 e1 = find_edge (bb1, succ);
1369 e2 = find_edge (bb2, succ);
1370 if (e1->flags & EDGE_COMPLEX
1371 || e2->flags & EDGE_COMPLEX)
1372 return false;
1373
1374 /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1375 the same value. */
1376 if (!same_phi_alternatives_1 (succ, e1, e2))
1377 return false;
1378 }
1379
1380 return true;
1381}
1382
1383/* Return true if BB has non-vop phis. */
1384
1385static bool
1386bb_has_non_vop_phi (basic_block bb)
1387{
1388 gimple_seq phis = phi_nodes (bb);
1389 gimple *phi;
1390
1391 if (phis == NULL)
1392 return false;
1393
1394 if (!gimple_seq_singleton_p (phis))
1395 return true;
1396
1397 phi = gimple_seq_first_stmt (phis);
1398 return !virtual_operand_p (gimple_phi_result (phi));
1399}
1400
1401/* Returns true if redirecting the incoming edges of FROM to TO maintains the
1402 invariant that uses in FROM are dominates by their defs. */
1403
1404static bool
1405deps_ok_for_redirect_from_bb_to_bb (basic_block from, basic_block to)
1406{
1407 basic_block cd, dep_bb = BB_DEP_BB (to);
1408 edge_iterator ei;
1409 edge e;
1410
1411 if (dep_bb == NULL)
1412 return true;
1413
1414 bitmap from_preds = BITMAP_ALLOC (NULL);
1415 FOR_EACH_EDGE (e, ei, from->preds)
1416 bitmap_set_bit (from_preds, e->src->index);
1417 cd = nearest_common_dominator_for_set (CDI_DOMINATORS, from_preds);
1418 BITMAP_FREE (from_preds);
1419
1420 return dominated_by_p (CDI_DOMINATORS, dep_bb, cd);
1421}
1422
1423/* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1424 replacement bb) and vice versa maintains the invariant that uses in the
1425 replacement are dominates by their defs. */
1426
1427static bool
1428deps_ok_for_redirect (basic_block bb1, basic_block bb2)
1429{
1430 if (BB_CLUSTER (bb1) != NULL)
1431 bb1 = BB_CLUSTER (bb1)->rep_bb;
1432
1433 if (BB_CLUSTER (bb2) != NULL)
1434 bb2 = BB_CLUSTER (bb2)->rep_bb;
1435
1436 return (deps_ok_for_redirect_from_bb_to_bb (bb1, bb2)
1437 && deps_ok_for_redirect_from_bb_to_bb (bb2, bb1));
1438}
1439
1440/* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1441
1442static void
1443find_clusters_1 (same_succ *same_succ)
1444{
1445 basic_block bb1, bb2;
1446 unsigned int i, j;
1447 bitmap_iterator bi, bj;
1448 int nr_comparisons;
1449 int max_comparisons = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS);
1450
1451 EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, 0, i, bi)
1452 {
1453 bb1 = BASIC_BLOCK_FOR_FN (cfun, i);
1454
1455 /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1456 phi-nodes in bb1 and bb2, with the same alternatives for the same
1457 preds. */
1458 if (bb_has_non_vop_phi (bb1) || bb_has_eh_pred (bb1))
1459 continue;
1460
1461 nr_comparisons = 0;
1462 EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, i + 1, j, bj)
1463 {
1464 bb2 = BASIC_BLOCK_FOR_FN (cfun, j);
1465
1466 if (bb_has_non_vop_phi (bb2) || bb_has_eh_pred (bb2))
1467 continue;
1468
1469 if (BB_CLUSTER (bb1) != NULL && BB_CLUSTER (bb1) == BB_CLUSTER (bb2))
1470 continue;
1471
1472 /* Limit quadratic behavior. */
1473 nr_comparisons++;
1474 if (nr_comparisons > max_comparisons)
1475 break;
1476
1477 /* This is a conservative dependency check. We could test more
1478 precise for allowed replacement direction. */
1479 if (!deps_ok_for_redirect (bb1, bb2))
1480 continue;
1481
1482 if (!(same_phi_alternatives (same_succ, bb1, bb2)))
1483 continue;
1484
1485 find_duplicate (same_succ, bb1, bb2);
1486 }
1487 }
1488}
1489
1490/* Find clusters of bbs which can be merged. */
1491
1492static void
1493find_clusters (void)
1494{
1495 same_succ *same;
1496
1497 while (!worklist.is_empty ())
1498 {
1499 same = worklist.pop ();
1500 same->in_worklist = false;
1501 if (dump_file && (dump_flags & TDF_DETAILS))
1502 {
1503 fprintf (dump_file, "processing worklist entry\n");
1504 same_succ_print (dump_file, same);
1505 }
1506 find_clusters_1 (same);
1507 }
1508}
1509
1510/* Returns the vop phi of BB, if any. */
1511
1512static gphi *
1513vop_phi (basic_block bb)
1514{
1515 gphi *stmt;
1516 gphi_iterator gsi;
1517 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1518 {
1519 stmt = gsi.phi ();
1520 if (! virtual_operand_p (gimple_phi_result (stmt)))
1521 continue;
1522 return stmt;
1523 }
1524 return NULL;
1525}
1526
1527/* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
1528
1529static void
1530replace_block_by (basic_block bb1, basic_block bb2)
1531{
1532 edge pred_edge;
1533 unsigned int i;
1534 gphi *bb2_phi;
1535
1536 bb2_phi = vop_phi (bb2);
1537
1538 /* Mark the basic block as deleted. */
1539 mark_basic_block_deleted (bb1);
1540
1541 /* Redirect the incoming edges of bb1 to bb2. */
1542 for (i = EDGE_COUNT (bb1->preds); i > 0 ; --i)
1543 {
1544 pred_edge = EDGE_PRED (bb1, i - 1);
1545 pred_edge = redirect_edge_and_branch (pred_edge, bb2);
1546 gcc_assert (pred_edge != NULL);
1547
1548 if (bb2_phi == NULL)
1549 continue;
1550
1551 /* The phi might have run out of capacity when the redirect added an
1552 argument, which means it could have been replaced. Refresh it. */
1553 bb2_phi = vop_phi (bb2);
1554
1555 add_phi_arg (bb2_phi, SSA_NAME_VAR (gimple_phi_result (bb2_phi)),
1556 pred_edge, UNKNOWN_LOCATION);
1557 }
1558
1559
1560 /* Merge the outgoing edge counts from bb1 onto bb2. */
1561 edge e1, e2;
1562 edge_iterator ei;
1563
1564 if (bb2->count.initialized_p ())
1565 FOR_EACH_EDGE (e1, ei, bb1->succs)
1566 {
1567 e2 = find_edge (bb2, e1->dest);
1568 gcc_assert (e2);
1569
1570 /* If probabilities are same, we are done.
1571 If counts are nonzero we can distribute accordingly. In remaining
1572 cases just avreage the values and hope for the best. */
1573 if (e1->probability == e2->probability)
1574 ;
1575 else if (bb1->count.nonzero_p () || bb2->count.nonzero_p ())
1576 e2->probability
1577 = e2->probability
1578 * bb2->count.probability_in (bb1->count + bb2->count)
1579 + e1->probability
1580 * bb1->count.probability_in (bb1->count + bb2->count);
1581 else
1582 e2->probability = e2->probability * profile_probability::even ()
1583 + e1->probability * profile_probability::even ();
1584 }
1585 bb2->count += bb1->count;
1586
1587 /* Move over any user labels from bb1 after the bb2 labels. */
1588 gimple_stmt_iterator gsi1 = gsi_start_bb (bb1);
1589 if (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
1590 {
1591 gimple_stmt_iterator gsi2 = gsi_after_labels (bb2);
1592 while (!gsi_end_p (gsi1)
1593 && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
1594 {
1595 tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1)));
1596 gcc_assert (!DECL_NONLOCAL (label) && !FORCED_LABEL (label));
1597 if (DECL_ARTIFICIAL (label))
1598 gsi_next (&gsi1);
1599 else
1600 gsi_move_before (&gsi1, &gsi2);
1601 }
1602 }
1603
1604 /* Clear range info from all stmts in BB2 -- this transformation
1605 could make them out of date. */
1606 reset_flow_sensitive_info_in_bb (bb2);
1607
1608 /* Do updates that use bb1, before deleting bb1. */
1609 release_last_vdef (bb1);
1610 same_succ_flush_bb (bb1);
1611
1612 delete_basic_block (bb1);
1613}
1614
1615/* Bbs for which update_debug_stmt need to be called. */
1616
1617static bitmap update_bbs;
1618
1619/* For each cluster in all_clusters, merge all cluster->bbs. Returns
1620 number of bbs removed. */
1621
1622static int
1623apply_clusters (void)
1624{
1625 basic_block bb1, bb2;
1626 bb_cluster *c;
1627 unsigned int i, j;
1628 bitmap_iterator bj;
1629 int nr_bbs_removed = 0;
1630
1631 for (i = 0; i < all_clusters.length (); ++i)
1632 {
1633 c = all_clusters[i];
1634 if (c == NULL)
1635 continue;
1636
1637 bb2 = c->rep_bb;
1638 bitmap_set_bit (update_bbs, bb2->index);
1639
1640 bitmap_clear_bit (c->bbs, bb2->index);
1641 EXECUTE_IF_SET_IN_BITMAP (c->bbs, 0, j, bj)
1642 {
1643 bb1 = BASIC_BLOCK_FOR_FN (cfun, j);
1644 bitmap_clear_bit (update_bbs, bb1->index);
1645
1646 replace_block_by (bb1, bb2);
1647 nr_bbs_removed++;
1648 }
1649 }
1650
1651 return nr_bbs_removed;
1652}
1653
1654/* Resets debug statement STMT if it has uses that are not dominated by their
1655 defs. */
1656
1657static void
1658update_debug_stmt (gimple *stmt)
1659{
1660 use_operand_p use_p;
1661 ssa_op_iter oi;
1662 basic_block bbuse;
1663
1664 if (!gimple_debug_bind_p (stmt))
1665 return;
1666
1667 bbuse = gimple_bb (stmt);
1668 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
1669 {
1670 tree name = USE_FROM_PTR (use_p);
1671 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1672 basic_block bbdef = gimple_bb (def_stmt);
1673 if (bbdef == NULL || bbuse == bbdef
1674 || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef))
1675 continue;
1676
1677 gimple_debug_bind_reset_value (stmt);
1678 update_stmt (stmt);
1679 break;
1680 }
1681}
1682
1683/* Resets all debug statements that have uses that are not
1684 dominated by their defs. */
1685
1686static void
1687update_debug_stmts (void)
1688{
1689 basic_block bb;
1690 bitmap_iterator bi;
1691 unsigned int i;
1692
1693 EXECUTE_IF_SET_IN_BITMAP (update_bbs, 0, i, bi)
1694 {
1695 gimple *stmt;
1696 gimple_stmt_iterator gsi;
1697
1698 bb = BASIC_BLOCK_FOR_FN (cfun, i);
1699 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1700 {
1701 stmt = gsi_stmt (gsi);
1702 if (!is_gimple_debug (stmt))
1703 continue;
1704 update_debug_stmt (stmt);
1705 }
1706 }
1707}
1708
1709/* Runs tail merge optimization. */
1710
1711unsigned int
1712tail_merge_optimize (unsigned int todo)
1713{
1714 int nr_bbs_removed_total = 0;
1715 int nr_bbs_removed;
1716 bool loop_entered = false;
1717 int iteration_nr = 0;
1718 int max_iterations = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS);
1719
1720 if (!flag_tree_tail_merge
1721 || max_iterations == 0)
1722 return 0;
1723
1724 timevar_push (TV_TREE_TAIL_MERGE);
1725
1726 /* We enter from PRE which has critical edges split. Elimination
1727 does not process trivially dead code so cleanup the CFG if we
1728 are told so. And re-split critical edges then. */
1729 if (todo & TODO_cleanup_cfg)
1730 {
1731 cleanup_tree_cfg ();
1732 todo &= ~TODO_cleanup_cfg;
1733 split_critical_edges ();
1734 }
1735
1736 if (!dom_info_available_p (CDI_DOMINATORS))
1737 {
1738 /* PRE can leave us with unreachable blocks, remove them now. */
1739 delete_unreachable_blocks ();
1740 calculate_dominance_info (CDI_DOMINATORS);
1741 }
1742 init_worklist ();
1743
1744 while (!worklist.is_empty ())
1745 {
1746 if (!loop_entered)
1747 {
1748 loop_entered = true;
1749 alloc_cluster_vectors ();
1750 update_bbs = BITMAP_ALLOC (NULL);
1751 }
1752 else
1753 reset_cluster_vectors ();
1754
1755 iteration_nr++;
1756 if (dump_file && (dump_flags & TDF_DETAILS))
1757 fprintf (dump_file, "worklist iteration #%d\n", iteration_nr);
1758
1759 find_clusters ();
1760 gcc_assert (worklist.is_empty ());
1761 if (all_clusters.is_empty ())
1762 break;
1763
1764 nr_bbs_removed = apply_clusters ();
1765 nr_bbs_removed_total += nr_bbs_removed;
1766 if (nr_bbs_removed == 0)
1767 break;
1768
1769 free_dominance_info (CDI_DOMINATORS);
1770
1771 if (iteration_nr == max_iterations)
1772 break;
1773
1774 calculate_dominance_info (CDI_DOMINATORS);
1775 update_worklist ();
1776 }
1777
1778 if (dump_file && (dump_flags & TDF_DETAILS))
1779 fprintf (dump_file, "htab collision / search: %f\n",
1780 same_succ_htab->collisions ());
1781
1782 if (nr_bbs_removed_total > 0)
1783 {
1784 if (MAY_HAVE_DEBUG_BIND_STMTS)
1785 {
1786 calculate_dominance_info (CDI_DOMINATORS);
1787 update_debug_stmts ();
1788 }
1789
1790 if (dump_file && (dump_flags & TDF_DETAILS))
1791 {
1792 fprintf (dump_file, "Before TODOs.\n");
1793 dump_function_to_file (current_function_decl, dump_file, dump_flags);
1794 }
1795
1796 mark_virtual_operands_for_renaming (cfun);
1797 }
1798
1799 delete_worklist ();
1800 if (loop_entered)
1801 {
1802 delete_cluster_vectors ();
1803 BITMAP_FREE (update_bbs);
1804 }
1805
1806 timevar_pop (TV_TREE_TAIL_MERGE);
1807
1808 return todo;
1809}
1810