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