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