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