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 43185533 : same_succ::hash (const same_succ *e)
244 : {
245 43185533 : 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 13601282 : tail_merge_valueize (tree name)
292 : {
293 13601282 : if (TREE_CODE (name) == SSA_NAME
294 13601282 : && has_VN_INFO (name))
295 : {
296 5092136 : tree tem = VN_INFO (name)->valnum;
297 5092136 : 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 39402997 : stmt_local_def (gimple *stmt)
308 : {
309 39402997 : basic_block bb, def_bb;
310 39402997 : imm_use_iterator iter;
311 39402997 : use_operand_p use_p;
312 39402997 : tree val;
313 39402997 : def_operand_p def_p;
314 :
315 39402997 : if (gimple_vdef (stmt) != NULL_TREE
316 25246620 : || gimple_has_side_effects (stmt)
317 24120660 : || gimple_could_trap_p_1 (stmt, false, false)
318 23296354 : || 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 47911769 : || is_gimple_call (stmt))
327 23600345 : return false;
328 :
329 15802652 : def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
330 15802652 : if (def_p == NULL)
331 : return false;
332 :
333 8295601 : val = DEF_FROM_PTR (def_p);
334 8295601 : if (val == NULL_TREE || TREE_CODE (val) != SSA_NAME)
335 : return false;
336 :
337 8295601 : def_bb = gimple_bb (stmt);
338 :
339 8295601 : bool any_use = false;
340 25940203 : FOR_EACH_IMM_USE_FAST (use_p, iter, val)
341 : {
342 10838611 : if (is_gimple_debug (USE_STMT (use_p)))
343 1515694 : continue;
344 :
345 9322917 : any_use = true;
346 9322917 : bb = gimple_bb (USE_STMT (use_p));
347 9322917 : if (bb == def_bb)
348 7062889 : continue;
349 :
350 3030446 : if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI
351 2260028 : && EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src == def_bb)
352 770418 : continue;
353 :
354 1489610 : return false;
355 1489610 : }
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 6805991 : 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 7530594 : gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator *gsi)
369 : {
370 8068031 : gimple *stmt;
371 :
372 8605468 : while (true)
373 : {
374 8068031 : if (gsi_end_p (*gsi))
375 : return;
376 3024331 : stmt = gsi_stmt (*gsi);
377 3024331 : if (!stmt_local_def (stmt))
378 : return;
379 537437 : 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 1298600 : gvn_uses_equal (tree val1, tree val2)
390 : {
391 1298600 : gcc_checking_assert (val1 != NULL_TREE && val2 != NULL_TREE);
392 :
393 1298600 : if (val1 == val2)
394 : return true;
395 :
396 1298600 : 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 19592 : && (TREE_CODE (val2) == SSA_NAME || CONSTANT_CLASS_P (val2)));
401 : }
402 :
403 : /* Prints E to FILE. */
404 :
405 : static void
406 16 : same_succ_print (FILE *file, const same_succ *e)
407 : {
408 16 : unsigned int i;
409 16 : bitmap_print (file, e->bbs, "bbs:", "\n");
410 16 : bitmap_print (file, e->succs, "succs:", "\n");
411 16 : bitmap_print (file, e->inverse, "inverse:", "\n");
412 16 : fprintf (file, "flags:");
413 48 : for (i = 0; i < e->succ_flags.length (); ++i)
414 16 : fprintf (file, " %x", e->succ_flags[i]);
415 16 : fprintf (file, "\n");
416 16 : }
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 36218371 : update_dep_bb (basic_block use_bb, tree val)
432 : {
433 36218371 : basic_block dep_bb;
434 :
435 : /* Not a dep. */
436 36218371 : if (TREE_CODE (val) != SSA_NAME)
437 : return;
438 :
439 : /* Skip use of global def. */
440 34616880 : if (SSA_NAME_IS_DEFAULT_DEF (val))
441 : return;
442 :
443 : /* Skip use of local def. */
444 30257006 : dep_bb = gimple_bb (SSA_NAME_DEF_STMT (val));
445 30257006 : if (dep_bb == use_bb)
446 : return;
447 :
448 11496332 : if (BB_DEP_BB (use_bb) == NULL
449 11496332 : || dominated_by_p (CDI_DOMINATORS, dep_bb, BB_DEP_BB (use_bb)))
450 9720303 : BB_DEP_BB (use_bb) = dep_bb;
451 : }
452 :
453 : /* Update BB_DEP_BB, given the dependencies in STMT. */
454 :
455 : static void
456 35240587 : stmt_update_dep_bb (gimple *stmt)
457 : {
458 35240587 : ssa_op_iter iter;
459 35240587 : use_operand_p use;
460 :
461 65430894 : FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
462 30190307 : update_dep_bb (gimple_bb (stmt), USE_FROM_PTR (use));
463 35240587 : }
464 :
465 : /* Calculates hash value for same_succ VE. */
466 :
467 : static hashval_t
468 14231109 : same_succ_hash (const same_succ *e)
469 : {
470 14231109 : inchash::hash hstate (bitmap_hash (e->succs));
471 14231109 : int flags;
472 14231109 : unsigned int i;
473 14231109 : unsigned int first = bitmap_first_set_bit (e->bbs);
474 14231109 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, first);
475 14231109 : int size = 0;
476 14231109 : gimple *stmt;
477 14231109 : tree arg;
478 14231109 : unsigned int s;
479 14231109 : bitmap_iterator bs;
480 :
481 14231109 : for (gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
482 49471696 : !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
483 : {
484 35240587 : stmt = gsi_stmt (gsi);
485 35240587 : if (is_gimple_debug (stmt))
486 0 : continue;
487 :
488 35240587 : stmt_update_dep_bb (stmt);
489 35240587 : if (stmt_local_def (stmt))
490 6239043 : continue;
491 29001544 : size++;
492 :
493 29001544 : hstate.add_int (gimple_code (stmt));
494 29001544 : if (is_gimple_assign (stmt))
495 16045841 : hstate.add_int (gimple_assign_rhs_code (stmt));
496 29001544 : if (!is_gimple_call (stmt))
497 23416190 : continue;
498 5585354 : if (gimple_call_internal_p (stmt))
499 106097 : hstate.add_int (gimple_call_internal_fn (stmt));
500 : else
501 : {
502 5479257 : inchash::add_expr (gimple_call_fn (stmt), hstate);
503 5479257 : if (gimple_call_chain (stmt))
504 30320 : inchash::add_expr (gimple_call_chain (stmt), hstate);
505 : }
506 16582218 : for (i = 0; i < gimple_call_num_args (stmt); i++)
507 : {
508 10996864 : arg = gimple_call_arg (stmt, i);
509 10996864 : arg = tail_merge_valueize (arg);
510 10996864 : inchash::add_expr (arg, hstate);
511 : }
512 : }
513 :
514 14231109 : hstate.add_int (size);
515 14231109 : BB_SIZE (bb) = size;
516 :
517 14231109 : hstate.add_int (bb->loop_father->num);
518 :
519 33509509 : for (i = 0; i < e->succ_flags.length (); ++i)
520 : {
521 19278400 : flags = e->succ_flags[i];
522 19278400 : flags = flags & ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
523 19278400 : hstate.add_int (flags);
524 : }
525 :
526 33509509 : EXECUTE_IF_SET_IN_BITMAP (e->succs, 0, s, bs)
527 : {
528 19278400 : int n = find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, s))->dest_idx;
529 19278400 : for (gphi_iterator gsi = gsi_start_phis (BASIC_BLOCK_FOR_FN (cfun, s));
530 29851367 : !gsi_end_p (gsi);
531 10572967 : gsi_next (&gsi))
532 : {
533 10572967 : gphi *phi = gsi.phi ();
534 10572967 : tree lhs = gimple_phi_result (phi);
535 10572967 : tree val = gimple_phi_arg_def (phi, n);
536 :
537 21145934 : if (virtual_operand_p (lhs))
538 4544903 : continue;
539 6028064 : update_dep_bb (bb, val);
540 : }
541 : }
542 :
543 14231109 : 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 5043842 : inverse_flags (const same_succ *e1, const same_succ *e2)
552 : {
553 5043842 : int f1a, f1b, f2a, f2b;
554 5043842 : int mask = ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
555 :
556 5056480 : if (e1->succ_flags.length () != 2)
557 : return false;
558 :
559 14400 : f1a = e1->succ_flags[0];
560 14400 : f1b = e1->succ_flags[1];
561 14400 : f2a = e2->succ_flags[0];
562 14400 : f2b = e2->succ_flags[1];
563 :
564 14400 : if (f1a == f2a && f1b == f2b)
565 : return false;
566 :
567 1762 : return (f1a & mask) == (f2a & mask) && (f1b & mask) == (f2b & mask);
568 : }
569 :
570 : /* Compares SAME_SUCCs E1 and E2. */
571 :
572 : int
573 51806150 : same_succ::equal (const same_succ *e1, const same_succ *e2)
574 : {
575 51806150 : unsigned int i, first1, first2;
576 51806150 : gimple_stmt_iterator gsi1, gsi2;
577 51806150 : gimple *s1, *s2;
578 51806150 : basic_block bb1, bb2;
579 :
580 51806150 : if (e1 == e2)
581 : return 1;
582 :
583 50639740 : if (e1->hashval != e2->hashval)
584 : return 0;
585 :
586 7980039 : if (e1->succ_flags.length () != e2->succ_flags.length ())
587 : return 0;
588 :
589 2660013 : if (!bitmap_equal_p (e1->succs, e2->succs))
590 : return 0;
591 :
592 2521992 : if (!inverse_flags (e1, e2))
593 : {
594 4676800 : for (i = 0; i < e1->succ_flags.length (); ++i)
595 2155689 : if (e1->succ_flags[i] != e2->succ_flags[i])
596 : return 0;
597 : }
598 :
599 2521992 : first1 = bitmap_first_set_bit (e1->bbs);
600 2521992 : first2 = bitmap_first_set_bit (e2->bbs);
601 :
602 2521992 : bb1 = BASIC_BLOCK_FOR_FN (cfun, first1);
603 2521992 : bb2 = BASIC_BLOCK_FOR_FN (cfun, first2);
604 :
605 2521992 : if (BB_SIZE (bb1) != BB_SIZE (bb2))
606 : return 0;
607 :
608 2521992 : if (bb1->loop_father != bb2->loop_father)
609 : return 0;
610 :
611 2521992 : gsi1 = gsi_start_nondebug_bb (bb1);
612 2521992 : gsi2 = gsi_start_nondebug_bb (bb2);
613 2521992 : gsi_advance_fw_nondebug_nonlocal (&gsi1);
614 2521992 : gsi_advance_fw_nondebug_nonlocal (&gsi2);
615 6287289 : while (!(gsi_end_p (gsi1) || gsi_end_p (gsi2)))
616 : {
617 1243447 : s1 = gsi_stmt (gsi1);
618 1243447 : s2 = gsi_stmt (gsi2);
619 1243447 : if (gimple_code (s1) != gimple_code (s2))
620 : return 0;
621 1243447 : if (is_gimple_call (s1) && !gimple_call_same_target_p (s1, s2))
622 : return 0;
623 1243305 : gsi_next_nondebug (&gsi1);
624 1243305 : gsi_next_nondebug (&gsi2);
625 1243305 : gsi_advance_fw_nondebug_nonlocal (&gsi1);
626 1243305 : 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 12876405 : same_succ_alloc (void)
636 : {
637 12876405 : same_succ *same = XNEW (struct same_succ);
638 :
639 12876405 : same->bbs = BITMAP_ALLOC (NULL);
640 12876405 : same->succs = BITMAP_ALLOC (NULL);
641 12876405 : same->inverse = BITMAP_ALLOC (NULL);
642 12876405 : same->succ_flags.create (10);
643 12876405 : same->in_worklist = false;
644 :
645 12876405 : return same;
646 : }
647 :
648 : /* Delete same_succ E. */
649 :
650 : void
651 12876405 : same_succ::remove (same_succ *e)
652 : {
653 12876405 : BITMAP_FREE (e->bbs);
654 12876405 : BITMAP_FREE (e->succs);
655 12876405 : BITMAP_FREE (e->inverse);
656 12876405 : e->succ_flags.release ();
657 :
658 12876405 : XDELETE (e);
659 12876405 : }
660 :
661 : /* Reset same_succ SAME. */
662 :
663 : static void
664 2521850 : same_succ_reset (same_succ *same)
665 : {
666 2521850 : bitmap_clear (same->bbs);
667 2521850 : bitmap_clear (same->succs);
668 2521850 : bitmap_clear (same->inverse);
669 2521850 : same->succ_flags.truncate (0);
670 2521850 : }
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 22 : for (i = 0; i < worklist.length (); ++i)
708 8 : same_succ_print (file, worklist[i]);
709 14 : }
710 :
711 : /* Adds SAME to worklist. */
712 :
713 : static void
714 14231109 : add_to_worklist (same_succ *same)
715 : {
716 14231109 : if (same->in_worklist)
717 : return;
718 :
719 12830528 : if (bitmap_count_bits (same->bbs) < 2)
720 : return;
721 :
722 1121269 : same->in_worklist = true;
723 1121269 : worklist.safe_push (same);
724 : }
725 :
726 : /* Add BB to same_succ_htab. */
727 :
728 : static void
729 14231109 : find_same_succ_bb (basic_block bb, same_succ **same_p)
730 : {
731 14231109 : unsigned int j;
732 14231109 : bitmap_iterator bj;
733 14231109 : same_succ *same = *same_p;
734 14231109 : same_succ **slot;
735 14231109 : edge_iterator ei;
736 14231109 : edge e;
737 :
738 14231109 : if (bb == NULL)
739 0 : return;
740 14231109 : bitmap_set_bit (same->bbs, bb->index);
741 33509509 : FOR_EACH_EDGE (e, ei, bb->succs)
742 : {
743 19278400 : int index = e->dest->index;
744 19278400 : bitmap_set_bit (same->succs, index);
745 19278400 : same_succ_edge_flags[index] = (e->flags & ~ignore_edge_flags);
746 : }
747 33509509 : EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
748 19278400 : same->succ_flags.safe_push (same_succ_edge_flags[j]);
749 :
750 14231109 : same->hashval = same_succ_hash (same);
751 :
752 14231109 : slot = same_succ_htab->find_slot_with_hash (same, same->hashval, INSERT);
753 14231109 : if (*slot == NULL)
754 : {
755 11709259 : *slot = same;
756 11709259 : BB_SAME_SUCC (bb) = same;
757 11709259 : add_to_worklist (same);
758 11709259 : *same_p = NULL;
759 : }
760 : else
761 : {
762 2521850 : bitmap_set_bit ((*slot)->bbs, bb->index);
763 2521850 : BB_SAME_SUCC (bb) = *slot;
764 2521850 : add_to_worklist (*slot);
765 2521850 : if (inverse_flags (same, *slot))
766 881 : bitmap_set_bit ((*slot)->inverse, bb->index);
767 2521850 : same_succ_reset (same);
768 : }
769 : }
770 :
771 : /* Find bbs with same successors. */
772 :
773 : static void
774 960544 : find_same_succ (void)
775 : {
776 960544 : same_succ *same = same_succ_alloc ();
777 960544 : basic_block bb;
778 :
779 14024803 : FOR_EACH_BB_FN (bb, cfun)
780 : {
781 13064259 : find_same_succ_bb (bb, &same);
782 13064259 : if (same == NULL)
783 10592088 : same = same_succ_alloc ();
784 : }
785 :
786 960544 : same_succ::remove (same);
787 960544 : }
788 :
789 : /* Initializes worklist administration. */
790 :
791 : static void
792 960544 : init_worklist (void)
793 : {
794 960544 : alloc_aux_for_blocks (sizeof (struct aux_bb_info));
795 960544 : same_succ_htab = new hash_table<same_succ> (n_basic_blocks_for_fn (cfun));
796 960544 : same_succ_edge_flags = XCNEWVEC (int, last_basic_block_for_fn (cfun));
797 960544 : deleted_bbs = BITMAP_ALLOC (NULL);
798 960544 : deleted_bb_preds = BITMAP_ALLOC (NULL);
799 960544 : worklist.create (n_basic_blocks_for_fn (cfun));
800 960544 : find_same_succ ();
801 :
802 960544 : if (dump_file && (dump_flags & TDF_DETAILS))
803 : {
804 14 : fprintf (dump_file, "initial worklist:\n");
805 14 : print_worklist (dump_file);
806 : }
807 960544 : }
808 :
809 : /* Deletes worklist administration. */
810 :
811 : static void
812 960544 : delete_worklist (void)
813 : {
814 960544 : free_aux_for_blocks ();
815 960544 : delete same_succ_htab;
816 960544 : same_succ_htab = NULL;
817 960544 : XDELETEVEC (same_succ_edge_flags);
818 960544 : same_succ_edge_flags = NULL;
819 960544 : BITMAP_FREE (deleted_bbs);
820 960544 : BITMAP_FREE (deleted_bb_preds);
821 960544 : worklist.release ();
822 960544 : }
823 :
824 : /* Mark BB as deleted, and mark its predecessors. */
825 :
826 : static void
827 1269955 : mark_basic_block_deleted (basic_block bb)
828 : {
829 1269955 : edge e;
830 1269955 : edge_iterator ei;
831 :
832 1269955 : bitmap_set_bit (deleted_bbs, bb->index);
833 :
834 2660878 : FOR_EACH_EDGE (e, ei, bb->preds)
835 1390923 : bitmap_set_bit (deleted_bb_preds, e->src->index);
836 1269955 : }
837 :
838 : /* Removes BB from its corresponding same_succ. */
839 :
840 : static void
841 2436805 : same_succ_flush_bb (basic_block bb)
842 : {
843 2436805 : same_succ *same = BB_SAME_SUCC (bb);
844 2436805 : if (! same)
845 0 : return;
846 :
847 2436805 : BB_SAME_SUCC (bb) = NULL;
848 2436805 : if (bitmap_single_bit_set_p (same->bbs))
849 1166410 : same_succ_htab->remove_elt_with_hash (same, same->hashval);
850 : else
851 1270395 : 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 206602 : same_succ_flush_bbs (bitmap bbs)
858 : {
859 206602 : unsigned int i;
860 206602 : bitmap_iterator bi;
861 :
862 1373452 : EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
863 1166850 : same_succ_flush_bb (BASIC_BLOCK_FOR_FN (cfun, i));
864 206602 : }
865 :
866 : /* Release the last vdef in BB, either normal or phi result. */
867 :
868 : static void
869 1269955 : release_last_vdef (basic_block bb)
870 : {
871 2692764 : for (gimple_stmt_iterator i = gsi_last_bb (bb); !gsi_end_p (i);
872 152854 : gsi_prev_nondebug (&i))
873 : {
874 424067 : gimple *stmt = gsi_stmt (i);
875 831830 : if (gimple_vdef (stmt) == NULL_TREE)
876 152854 : continue;
877 :
878 271213 : mark_virtual_operand_for_renaming (gimple_vdef (stmt));
879 271213 : return;
880 : }
881 :
882 998742 : 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 206602 : update_worklist (void)
900 : {
901 206602 : unsigned int i;
902 206602 : bitmap_iterator bi;
903 206602 : basic_block bb;
904 206602 : same_succ *same;
905 :
906 206602 : bitmap_and_compl_into (deleted_bb_preds, deleted_bbs);
907 206602 : bitmap_clear (deleted_bbs);
908 :
909 206602 : bitmap_clear_bit (deleted_bb_preds, ENTRY_BLOCK);
910 206602 : same_succ_flush_bbs (deleted_bb_preds);
911 :
912 206602 : same = same_succ_alloc ();
913 1373452 : EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds, 0, i, bi)
914 : {
915 1166850 : bb = BASIC_BLOCK_FOR_FN (cfun, i);
916 1166850 : gcc_assert (bb != NULL);
917 1166850 : find_same_succ_bb (bb, &same);
918 1166850 : if (same == NULL)
919 1117171 : same = same_succ_alloc ();
920 : }
921 206602 : same_succ::remove (same);
922 206602 : bitmap_clear (deleted_bb_preds);
923 206602 : }
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 1886685 : update_rep_bb (bb_cluster *c, basic_block bb)
949 : {
950 : /* Initial. */
951 1886685 : if (c->rep_bb == NULL)
952 : {
953 616730 : c->rep_bb = bb;
954 616730 : return;
955 : }
956 :
957 : /* Current needs no deps, keep it. */
958 1269955 : if (BB_DEP_BB (c->rep_bb) == NULL)
959 : return;
960 :
961 : /* Bb needs no deps, change rep_bb. */
962 19981 : 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 19901 : if (dominated_by_p (CDI_DOMINATORS, BB_DEP_BB (c->rep_bb), BB_DEP_BB (bb)))
976 19608 : 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 1886685 : add_bb_to_cluster (bb_cluster *c, basic_block bb)
983 : {
984 1886685 : edge e;
985 1886685 : edge_iterator ei;
986 :
987 1886685 : bitmap_set_bit (c->bbs, bb->index);
988 :
989 4042872 : FOR_EACH_EDGE (e, ei, bb->preds)
990 2156187 : bitmap_set_bit (c->preds, e->src->index);
991 :
992 1886685 : update_rep_bb (c, bb);
993 1886685 : }
994 :
995 : /* Allocate and init new cluster. */
996 :
997 : static bb_cluster *
998 616730 : new_cluster (void)
999 : {
1000 616730 : bb_cluster *c;
1001 616730 : c = XCNEW (bb_cluster);
1002 616730 : c->bbs = BITMAP_ALLOC (NULL);
1003 616730 : c->preds = BITMAP_ALLOC (NULL);
1004 616730 : c->rep_bb = NULL;
1005 616730 : return c;
1006 : }
1007 :
1008 : /* Delete clusters. */
1009 :
1010 : static void
1011 616730 : delete_cluster (bb_cluster *c)
1012 : {
1013 616730 : if (c == NULL)
1014 : return;
1015 616730 : BITMAP_FREE (c->bbs);
1016 616730 : BITMAP_FREE (c->preds);
1017 616730 : 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 262797 : alloc_cluster_vectors (void)
1029 : {
1030 262797 : all_clusters.create (n_basic_blocks_for_fn (cfun));
1031 262797 : }
1032 :
1033 : /* Reset all cluster vectors. */
1034 :
1035 : static void
1036 11739 : reset_cluster_vectors (void)
1037 : {
1038 11739 : unsigned int i;
1039 11739 : basic_block bb;
1040 128257 : for (i = 0; i < all_clusters.length (); ++i)
1041 116518 : delete_cluster (all_clusters[i]);
1042 11739 : all_clusters.truncate (0);
1043 1215558 : FOR_EACH_BB_FN (bb, cfun)
1044 1203819 : BB_CLUSTER (bb) = NULL;
1045 11739 : }
1046 :
1047 : /* Delete all cluster vectors. */
1048 :
1049 : static void
1050 262797 : delete_cluster_vectors (void)
1051 : {
1052 262797 : unsigned int i;
1053 763009 : for (i = 0; i < all_clusters.length (); ++i)
1054 500212 : delete_cluster (all_clusters[i]);
1055 262797 : all_clusters.release ();
1056 262797 : }
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 1269955 : set_cluster (basic_block bb1, basic_block bb2)
1072 : {
1073 1269955 : basic_block merge_bb, other_bb;
1074 1269955 : bb_cluster *merge, *old, *c;
1075 :
1076 1269955 : if (BB_CLUSTER (bb1) == NULL && BB_CLUSTER (bb2) == NULL)
1077 : {
1078 616730 : c = new_cluster ();
1079 616730 : add_bb_to_cluster (c, bb1);
1080 616730 : add_bb_to_cluster (c, bb2);
1081 616730 : BB_CLUSTER (bb1) = c;
1082 616730 : BB_CLUSTER (bb2) = c;
1083 616730 : c->index = all_clusters.length ();
1084 616730 : all_clusters.safe_push (c);
1085 : }
1086 653225 : else if (BB_CLUSTER (bb1) == NULL || BB_CLUSTER (bb2) == NULL)
1087 : {
1088 653225 : merge_bb = BB_CLUSTER (bb1) == NULL ? bb2 : bb1;
1089 653225 : other_bb = BB_CLUSTER (bb1) == NULL ? bb1 : bb2;
1090 653225 : merge = BB_CLUSTER (merge_bb);
1091 653225 : add_bb_to_cluster (merge, other_bb);
1092 653225 : 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 1269955 : }
1111 :
1112 : /* Return true if gimple operands T1 and T2 have the same value. */
1113 :
1114 : static bool
1115 802459 : gimple_operand_equal_value_p (tree t1, tree t2)
1116 : {
1117 802459 : if (t1 == t2)
1118 : return true;
1119 :
1120 155668 : if (t1 == NULL_TREE
1121 155668 : || t2 == NULL_TREE)
1122 : return false;
1123 :
1124 155668 : if (operand_equal_p (t1, t2, OEP_MATCH_SIDE_EFFECTS))
1125 : return true;
1126 :
1127 54992 : 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 552055 : gimple_equal_p (same_succ *same_succ, gimple *s1, gimple *s2)
1135 : {
1136 552055 : unsigned int i;
1137 552055 : tree lhs1, lhs2;
1138 552055 : basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
1139 552055 : tree t1, t2;
1140 552055 : bool inv_cond;
1141 552055 : enum tree_code code1, code2;
1142 :
1143 552055 : if (gimple_code (s1) != gimple_code (s2))
1144 : return false;
1145 :
1146 552055 : switch (gimple_code (s1))
1147 : {
1148 426247 : case GIMPLE_CALL:
1149 426247 : if (!gimple_call_same_target_p (s1, s2))
1150 : return false;
1151 :
1152 426247 : t1 = gimple_call_chain (s1);
1153 426247 : t2 = gimple_call_chain (s2);
1154 426247 : if (!gimple_operand_equal_value_p (t1, t2))
1155 : return false;
1156 :
1157 426247 : if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
1158 : return false;
1159 :
1160 694030 : for (i = 0; i < gimple_call_num_args (s1); ++i)
1161 : {
1162 267789 : t1 = gimple_call_arg (s1, i);
1163 267789 : t2 = gimple_call_arg (s2, i);
1164 267789 : if (!gimple_operand_equal_value_p (t1, t2))
1165 : return false;
1166 : }
1167 :
1168 426241 : lhs1 = gimple_get_lhs (s1);
1169 426241 : lhs2 = gimple_get_lhs (s2);
1170 426241 : if (lhs1 == NULL_TREE && lhs2 == NULL_TREE)
1171 : return true;
1172 3966 : if (lhs1 == NULL_TREE || lhs2 == NULL_TREE)
1173 : return false;
1174 3966 : if (TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME)
1175 3609 : return tail_merge_valueize (lhs1) == tail_merge_valueize (lhs2);
1176 357 : return operand_equal_p (lhs1, lhs2, 0);
1177 :
1178 116536 : case GIMPLE_ASSIGN:
1179 116536 : if (gimple_assign_rhs_code (s1) != gimple_assign_rhs_code (s2))
1180 : return false;
1181 :
1182 116536 : lhs1 = gimple_get_lhs (s1);
1183 116536 : lhs2 = gimple_get_lhs (s2);
1184 116536 : if (TREE_CODE (lhs1) != SSA_NAME
1185 105935 : && TREE_CODE (lhs2) != SSA_NAME)
1186 105935 : return (operand_equal_p (lhs1, lhs2, 0)
1187 105935 : && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1),
1188 : gimple_assign_rhs1 (s2)));
1189 :
1190 10601 : if (TREE_CODE (lhs1) != SSA_NAME
1191 10601 : || TREE_CODE (lhs2) != SSA_NAME)
1192 : return false;
1193 :
1194 10523 : gcc_checking_assert (gimple_num_args (s1) == gimple_num_args (s2));
1195 20918 : for (i = 0; i < gimple_num_args (s1); ++i)
1196 : {
1197 10688 : t1 = gimple_arg (s1, i);
1198 10688 : t2 = gimple_arg (s2, i);
1199 23558 : while (handled_component_p (t1) && handled_component_p (t2))
1200 : {
1201 2395 : if (TREE_CODE (t1) != TREE_CODE (t2)
1202 2395 : || TREE_THIS_VOLATILE (t1) != TREE_THIS_VOLATILE (t2))
1203 : return false;
1204 2395 : switch (TREE_CODE (t1))
1205 : {
1206 2317 : case COMPONENT_REF:
1207 2317 : if (TREE_OPERAND (t1, 1) != TREE_OPERAND (t2, 1)
1208 4421 : || !gimple_operand_equal_value_p (TREE_OPERAND (t1, 2),
1209 2104 : TREE_OPERAND (t2, 2)))
1210 213 : return false;
1211 : break;
1212 58 : case ARRAY_REF:
1213 58 : case ARRAY_RANGE_REF:
1214 58 : if (!gimple_operand_equal_value_p (TREE_OPERAND (t1, 3),
1215 58 : TREE_OPERAND (t2, 3)))
1216 : return false;
1217 : /* Fallthru. */
1218 78 : case BIT_FIELD_REF:
1219 78 : if (!gimple_operand_equal_value_p (TREE_OPERAND (t1, 1),
1220 78 : TREE_OPERAND (t2, 1))
1221 156 : || !gimple_operand_equal_value_p (TREE_OPERAND (t1, 2),
1222 78 : 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 2182 : t1 = TREE_OPERAND (t1, 0);
1233 2182 : t2 = TREE_OPERAND (t2, 0);
1234 : }
1235 10475 : if (TREE_CODE (t1) == MEM_REF && TREE_CODE (t2) == MEM_REF)
1236 : {
1237 5870 : if (TREE_THIS_VOLATILE (t1) != TREE_THIS_VOLATILE (t2)
1238 5870 : || TYPE_ALIGN (TREE_TYPE (t1)) != TYPE_ALIGN (TREE_TYPE (t2))
1239 5870 : || !gimple_operand_equal_value_p (TREE_OPERAND (t1, 0),
1240 5870 : TREE_OPERAND (t2, 0))
1241 11740 : || TREE_OPERAND (t1, 1) != TREE_OPERAND (t2, 1))
1242 62 : return false;
1243 : }
1244 4605 : else if (!gimple_operand_equal_value_p (t1, t2))
1245 : return false;
1246 : }
1247 : return true;
1248 :
1249 4090 : case GIMPLE_COND:
1250 4090 : t1 = gimple_cond_lhs (s1);
1251 4090 : t2 = gimple_cond_lhs (s2);
1252 4090 : 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 3649202 : gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse,
1282 : bool *vuse_escaped)
1283 : {
1284 3656379 : gimple *stmt;
1285 3656379 : tree lvuse;
1286 :
1287 3663556 : while (true)
1288 : {
1289 3656379 : if (gsi_end_p (*gsi))
1290 : return;
1291 1138079 : stmt = gsi_stmt (*gsi);
1292 :
1293 1138079 : lvuse = gimple_vuse (stmt);
1294 1097135 : if (lvuse != NULL_TREE)
1295 : {
1296 839304 : *vuse = lvuse;
1297 839304 : if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_DEF))
1298 27774 : *vuse_escaped = true;
1299 : }
1300 :
1301 1138079 : if (!stmt_local_def (stmt))
1302 : return;
1303 7177 : 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 483331 : 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 483331 : if (is_tm_ending (stmt1))
1317 : return false;
1318 :
1319 : /* Verify EH landing pads. */
1320 483279 : if (lookup_stmt_eh_lp_fn (cfun, stmt1) != lookup_stmt_eh_lp_fn (cfun, stmt2))
1321 : return false;
1322 :
1323 475657 : if (is_gimple_call (stmt1)
1324 475657 : && 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 1348944 : find_duplicate (same_succ *same_succ, basic_block bb1, basic_block bb2)
1353 : {
1354 1348944 : gimple_stmt_iterator gsi1 = gsi_last_nondebug_bb (bb1);
1355 1348944 : gimple_stmt_iterator gsi2 = gsi_last_nondebug_bb (bb2);
1356 1348944 : tree vuse1 = NULL_TREE, vuse2 = NULL_TREE;
1357 1348944 : bool vuse_escaped = false;
1358 :
1359 1348944 : gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
1360 1348944 : gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
1361 :
1362 3173545 : while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2))
1363 : {
1364 565451 : gimple *stmt1 = gsi_stmt (gsi1);
1365 565451 : gimple *stmt2 = gsi_stmt (gsi2);
1366 :
1367 565451 : if (gimple_code (stmt1) == GIMPLE_LABEL
1368 565451 : && gimple_code (stmt2) == GIMPLE_LABEL)
1369 : break;
1370 :
1371 552055 : if (!gimple_equal_p (same_succ, stmt1, stmt2))
1372 78989 : return;
1373 :
1374 483331 : if (!merge_stmts_p (stmt1, stmt2))
1375 : return;
1376 :
1377 475657 : gsi_prev_nondebug (&gsi1);
1378 475657 : gsi_prev_nondebug (&gsi2);
1379 475657 : gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
1380 475657 : gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
1381 : }
1382 :
1383 13397 : while (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
1384 : {
1385 13397 : tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1)));
1386 26794 : if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
1387 : return;
1388 1299330 : gsi_prev (&gsi1);
1389 : }
1390 13392 : while (!gsi_end_p (gsi2) && gimple_code (gsi_stmt (gsi2)) == GIMPLE_LABEL)
1391 : {
1392 13392 : tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi2)));
1393 26784 : if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
1394 : return;
1395 1299325 : gsi_prev (&gsi2);
1396 : }
1397 1272541 : 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 1272541 : if (vuse_escaped && vuse1 != vuse2)
1405 : return;
1406 :
1407 1269955 : if (dump_file)
1408 26 : fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1409 : bb1->index, bb2->index);
1410 :
1411 1269955 : 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 2207813 : same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
1419 : {
1420 2207813 : int n1 = e1->dest_idx, n2 = e2->dest_idx;
1421 2207813 : gphi_iterator gsi;
1422 :
1423 3034846 : for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
1424 : {
1425 2059053 : gphi *phi = gsi.phi ();
1426 2059053 : tree lhs = gimple_phi_result (phi);
1427 2059053 : tree val1 = gimple_phi_arg_def (phi, n1);
1428 2059053 : tree val2 = gimple_phi_arg_def (phi, n2);
1429 :
1430 4118106 : if (virtual_operand_p (lhs))
1431 580948 : continue;
1432 :
1433 1478105 : if (operand_equal_for_phi_arg_p (val1, val2))
1434 234497 : continue;
1435 1243608 : if (gvn_uses_equal (val1, val2))
1436 11588 : 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 2580964 : same_phi_alternatives (same_succ *same_succ, basic_block bb1, basic_block bb2)
1449 : {
1450 2580964 : unsigned int s;
1451 2580964 : bitmap_iterator bs;
1452 2580964 : edge e1, e2;
1453 2580964 : basic_block succ;
1454 :
1455 3556757 : EXECUTE_IF_SET_IN_BITMAP (same_succ->succs, 0, s, bs)
1456 : {
1457 2207813 : succ = BASIC_BLOCK_FOR_FN (cfun, s);
1458 2207813 : e1 = find_edge (bb1, succ);
1459 2207813 : e2 = find_edge (bb2, succ);
1460 2207813 : if (e1->flags & EDGE_COMPLEX
1461 2207813 : || 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 2207813 : 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 20482685 : bb_has_non_vop_phi (basic_block bb)
1477 : {
1478 20482685 : gimple_seq phis = phi_nodes (bb);
1479 20482685 : gimple *phi;
1480 :
1481 20482685 : if (phis == NULL)
1482 : return false;
1483 :
1484 127854 : if (!gimple_seq_singleton_p (phis))
1485 : return true;
1486 :
1487 99609 : phi = gimple_seq_first_stmt (phis);
1488 199218 : 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 4234569 : deps_ok_for_redirect_from_bb_to_bb (basic_block from, basic_block to)
1496 : {
1497 4234569 : basic_block cd, dep_bb = BB_DEP_BB (to);
1498 4234569 : edge_iterator ei;
1499 4234569 : edge e;
1500 :
1501 4234569 : if (dep_bb == NULL)
1502 : return true;
1503 :
1504 2002851 : bitmap from_preds = BITMAP_ALLOC (NULL);
1505 4052785 : FOR_EACH_EDGE (e, ei, from->preds)
1506 2049934 : bitmap_set_bit (from_preds, e->src->index);
1507 2002851 : cd = nearest_common_dominator_for_set (CDI_DOMINATORS, from_preds);
1508 2002851 : BITMAP_FREE (from_preds);
1509 :
1510 2002851 : 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 3372893 : deps_ok_for_redirect (basic_block &bb1, basic_block &bb2)
1519 : {
1520 3372893 : basic_block b1 = bb1;
1521 3372893 : basic_block b2 = bb2;
1522 3372893 : if (BB_CLUSTER (b1) != NULL)
1523 979363 : b1 = BB_CLUSTER (b1)->rep_bb;
1524 :
1525 3372893 : if (BB_CLUSTER (b2) != NULL)
1526 97079 : b2 = BB_CLUSTER (b2)->rep_bb;
1527 :
1528 3372893 : if (deps_ok_for_redirect_from_bb_to_bb (b1, b2))
1529 : return true;
1530 861676 : if (deps_ok_for_redirect_from_bb_to_bb (b2, b1))
1531 : {
1532 69747 : std::swap (bb1, bb2);
1533 69747 : 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 1121269 : find_clusters_1 (same_succ *same_succ)
1542 : {
1543 1121269 : basic_block bb1, bb2;
1544 1121269 : unsigned int i, j;
1545 1121269 : bitmap_iterator bi, bj;
1546 1121269 : int nr_comparisons;
1547 1121269 : int max_comparisons = param_max_tail_merge_comparisons;
1548 :
1549 4764813 : EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, 0, i, bi)
1550 : {
1551 3643544 : 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 7260166 : if (bb_has_non_vop_phi (bb1) || bb_has_eh_pred (bb1)
1557 6674260 : || bb_has_abnormal_pred (bb1))
1558 612946 : continue;
1559 :
1560 3030598 : nr_comparisons = 0;
1561 19754346 : EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, i + 1, j, bj)
1562 : {
1563 16839141 : bb2 = BASIC_BLOCK_FOR_FN (cfun, j);
1564 :
1565 33661176 : if (bb_has_non_vop_phi (bb2) || bb_has_eh_pred (bb2)
1566 33660811 : || bb_has_abnormal_pred (bb2))
1567 17471 : continue;
1568 :
1569 16821670 : if (BB_CLUSTER (bb1) != NULL && BB_CLUSTER (bb1) == BB_CLUSTER (bb2))
1570 13333384 : continue;
1571 :
1572 : /* Limit quadratic behavior. */
1573 3488286 : nr_comparisons++;
1574 3488286 : 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 3372893 : if (!deps_ok_for_redirect (bb1, bb2))
1580 791929 : continue;
1581 :
1582 2580964 : if (!(same_phi_alternatives (same_succ, bb1, bb2)))
1583 1232020 : continue;
1584 :
1585 1348944 : find_duplicate (same_succ, bb1, bb2);
1586 : }
1587 : }
1588 1121269 : }
1589 :
1590 : /* Find clusters of bbs which can be merged. */
1591 :
1592 : static void
1593 274536 : find_clusters (void)
1594 : {
1595 274536 : same_succ *same;
1596 :
1597 1395805 : while (!worklist.is_empty ())
1598 : {
1599 1121269 : same = worklist.pop ();
1600 1121269 : same->in_worklist = false;
1601 81 : if (dump_file && (dump_flags & TDF_DETAILS))
1602 : {
1603 8 : fprintf (dump_file, "processing worklist entry\n");
1604 8 : same_succ_print (dump_file, same);
1605 : }
1606 1121269 : find_clusters_1 (same);
1607 : }
1608 274536 : }
1609 :
1610 : /* Returns the vop phi of BB, if any. */
1611 :
1612 : static gphi *
1613 1287962 : vop_phi (basic_block bb)
1614 : {
1615 1287962 : gphi *stmt;
1616 1287962 : gphi_iterator gsi;
1617 1287962 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1618 : {
1619 29777 : stmt = gsi.phi ();
1620 59554 : 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 1269955 : replace_block_by (basic_block bb1, basic_block bb2)
1631 : {
1632 1269955 : edge pred_edge;
1633 1269955 : unsigned int i;
1634 1269955 : gphi *bb2_phi;
1635 :
1636 1269955 : bb2_phi = vop_phi (bb2);
1637 :
1638 : /* Mark the basic block as deleted. */
1639 1269955 : mark_basic_block_deleted (bb1);
1640 :
1641 : /* Redirect the incoming edges of bb1 to bb2. */
1642 3930833 : for (i = EDGE_COUNT (bb1->preds); i > 0 ; --i)
1643 : {
1644 1390923 : pred_edge = EDGE_PRED (bb1, i - 1);
1645 1390923 : pred_edge = redirect_edge_and_branch (pred_edge, bb2);
1646 1390923 : gcc_assert (pred_edge != NULL);
1647 :
1648 1390923 : if (bb2_phi == NULL)
1649 1372916 : 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 18007 : bb2_phi = vop_phi (bb2);
1654 :
1655 18007 : 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 1269955 : edge e1, e2;
1662 1269955 : edge_iterator ei;
1663 :
1664 1269955 : if (bb2->count.initialized_p ())
1665 2176152 : FOR_EACH_EDGE (e1, ei, bb1->succs)
1666 : {
1667 906297 : e2 = find_edge (bb2, e1->dest);
1668 906297 : 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 906297 : e2->probability = e1->probability.combine_with_count
1674 906297 : (bb1->count, e2->probability, bb2->count);
1675 : }
1676 1269955 : bb2->count += bb1->count;
1677 :
1678 : /* Move over any user labels from bb1 after the bb2 labels. */
1679 1269955 : gimple_stmt_iterator gsi1 = gsi_start_bb (bb1);
1680 1269955 : if (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
1681 : {
1682 13361 : gimple_stmt_iterator gsi2 = gsi_after_labels (bb2);
1683 26723 : while (!gsi_end_p (gsi1)
1684 26723 : && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
1685 : {
1686 13362 : tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1)));
1687 26724 : gcc_assert (!DECL_NONLOCAL (label) && !FORCED_LABEL (label));
1688 13362 : if (DECL_ARTIFICIAL (label))
1689 13165 : gsi_next (&gsi1);
1690 : else
1691 197 : 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 1269955 : reset_flow_sensitive_info_in_bb (bb2);
1698 :
1699 : /* Do updates that use bb1, before deleting bb1. */
1700 1269955 : release_last_vdef (bb1);
1701 1269955 : same_succ_flush_bb (bb1);
1702 :
1703 1269955 : delete_basic_block (bb1);
1704 1269955 : }
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 213505 : apply_clusters (void)
1715 : {
1716 213505 : basic_block bb1, bb2;
1717 213505 : bb_cluster *c;
1718 213505 : unsigned int i, j;
1719 213505 : bitmap_iterator bj;
1720 213505 : int nr_bbs_removed = 0;
1721 :
1722 830235 : for (i = 0; i < all_clusters.length (); ++i)
1723 : {
1724 616730 : c = all_clusters[i];
1725 616730 : if (c == NULL)
1726 0 : continue;
1727 :
1728 616730 : bb2 = c->rep_bb;
1729 616730 : bitmap_set_bit (update_bbs, bb2->index);
1730 :
1731 616730 : bitmap_clear_bit (c->bbs, bb2->index);
1732 1886685 : EXECUTE_IF_SET_IN_BITMAP (c->bbs, 0, j, bj)
1733 : {
1734 1269955 : bb1 = BASIC_BLOCK_FOR_FN (cfun, j);
1735 1269955 : bitmap_clear_bit (update_bbs, bb1->index);
1736 :
1737 1269955 : replace_block_by (bb1, bb2);
1738 1269955 : nr_bbs_removed++;
1739 : }
1740 : }
1741 :
1742 213505 : 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 133737 : update_debug_stmt (gimple *stmt)
1750 : {
1751 133737 : use_operand_p use_p;
1752 133737 : ssa_op_iter oi;
1753 133737 : basic_block bbuse;
1754 :
1755 133737 : if (!gimple_debug_bind_p (stmt))
1756 21667 : return;
1757 :
1758 112070 : bbuse = gimple_bb (stmt);
1759 117151 : FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
1760 : {
1761 5511 : tree name = USE_FROM_PTR (use_p);
1762 5511 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1763 5511 : basic_block bbdef = gimple_bb (def_stmt);
1764 10592 : if (bbdef == NULL || bbuse == bbdef
1765 5511 : || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef))
1766 5081 : 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 139440 : update_debug_stmts (void)
1779 : {
1780 139440 : basic_block bb;
1781 139440 : bitmap_iterator bi;
1782 139440 : unsigned int i;
1783 :
1784 580089 : EXECUTE_IF_SET_IN_BITMAP (update_bbs, 0, i, bi)
1785 : {
1786 440649 : gimple *stmt;
1787 440649 : gimple_stmt_iterator gsi;
1788 :
1789 440649 : bb = BASIC_BLOCK_FOR_FN (cfun, i);
1790 1093553 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1791 : {
1792 212255 : stmt = gsi_stmt (gsi);
1793 212255 : if (!is_gimple_debug (stmt))
1794 78518 : continue;
1795 133737 : update_debug_stmt (stmt);
1796 : }
1797 : }
1798 139440 : }
1799 :
1800 : /* Runs tail merge optimization. */
1801 :
1802 : unsigned int
1803 960589 : tail_merge_optimize (bool need_crit_edge_split)
1804 : {
1805 960589 : int nr_bbs_removed_total = 0;
1806 960589 : int nr_bbs_removed;
1807 960589 : bool loop_entered = false;
1808 960589 : int iteration_nr = 0;
1809 960589 : int max_iterations = param_max_tail_merge_iterations;
1810 :
1811 960589 : if (!flag_tree_tail_merge
1812 960544 : || max_iterations == 0)
1813 : return 0;
1814 :
1815 960544 : timevar_push (TV_TREE_TAIL_MERGE);
1816 :
1817 : /* Re-split critical edges when PRE did a CFG cleanup. */
1818 960544 : if (need_crit_edge_split)
1819 137591 : split_edges_for_insertion ();
1820 :
1821 960544 : 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 960544 : init_worklist ();
1828 :
1829 2127690 : while (!worklist.is_empty ())
1830 : {
1831 274536 : if (!loop_entered)
1832 : {
1833 262797 : loop_entered = true;
1834 262797 : alloc_cluster_vectors ();
1835 262797 : update_bbs = BITMAP_ALLOC (NULL);
1836 : }
1837 : else
1838 11739 : reset_cluster_vectors ();
1839 :
1840 274536 : iteration_nr++;
1841 274536 : if (dump_file && (dump_flags & TDF_DETAILS))
1842 7 : fprintf (dump_file, "worklist iteration #%d\n", iteration_nr);
1843 :
1844 274536 : find_clusters ();
1845 274536 : gcc_assert (worklist.is_empty ());
1846 274536 : if (all_clusters.is_empty ())
1847 : break;
1848 :
1849 213505 : nr_bbs_removed = apply_clusters ();
1850 213505 : nr_bbs_removed_total += nr_bbs_removed;
1851 213505 : if (nr_bbs_removed == 0)
1852 : break;
1853 :
1854 213505 : free_dominance_info (CDI_DOMINATORS);
1855 :
1856 213505 : if (iteration_nr == max_iterations)
1857 : break;
1858 :
1859 206602 : calculate_dominance_info (CDI_DOMINATORS);
1860 206602 : update_worklist ();
1861 : }
1862 :
1863 960544 : if (dump_file && (dump_flags & TDF_DETAILS))
1864 28 : fprintf (dump_file, "htab collision / search: %f\n",
1865 : same_succ_htab->collisions ());
1866 :
1867 960544 : if (nr_bbs_removed_total > 0)
1868 : {
1869 206602 : if (MAY_HAVE_DEBUG_BIND_STMTS)
1870 : {
1871 139440 : calculate_dominance_info (CDI_DOMINATORS);
1872 139440 : update_debug_stmts ();
1873 : }
1874 :
1875 206602 : 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 206602 : mark_virtual_operands_for_renaming (cfun);
1882 : }
1883 :
1884 960544 : delete_worklist ();
1885 960544 : if (loop_entered)
1886 : {
1887 262797 : delete_cluster_vectors ();
1888 262797 : BITMAP_FREE (update_bbs);
1889 : }
1890 :
1891 960544 : timevar_pop (TV_TREE_TAIL_MERGE);
1892 :
1893 960544 : return 0;
1894 : }
|
