Branch data Line data Source code
1 : : /* Tail merging for gimple.
2 : : Copyright (C) 2011-2025 Free Software Foundation, Inc.
3 : : Contributed by Tom de Vries (tom@codesourcery.com)
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify
8 : : it under the terms of the GNU General Public License as published by
9 : : the Free Software Foundation; either version 3, or (at your option)
10 : : any later version.
11 : :
12 : : GCC is distributed in the hope that it will be useful,
13 : : but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : : GNU General Public License for more details.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not see
19 : : <http://www.gnu.org/licenses/>. */
20 : :
21 : : /* Pass overview.
22 : :
23 : :
24 : : MOTIVATIONAL EXAMPLE
25 : :
26 : : gimple representation of gcc/testsuite/gcc.dg/pr43864.c at
27 : :
28 : : hprofStartupp (charD.1 * outputFileNameD.2600, charD.1 * ctxD.2601)
29 : : {
30 : : struct FILED.1638 * fpD.2605;
31 : : charD.1 fileNameD.2604[1000];
32 : : intD.0 D.3915;
33 : : const charD.1 * restrict outputFileName.0D.3914;
34 : :
35 : : # BLOCK 2 freq:10000
36 : : # PRED: ENTRY [100.0%] (fallthru,exec)
37 : : # PT = nonlocal { D.3926 } (restr)
38 : : outputFileName.0D.3914_3
39 : : = (const charD.1 * restrict) outputFileNameD.2600_2(D);
40 : : # .MEMD.3923_13 = VDEF <.MEMD.3923_12(D)>
41 : : # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
42 : : # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
43 : : sprintfD.759 (&fileNameD.2604, outputFileName.0D.3914_3);
44 : : # .MEMD.3923_14 = VDEF <.MEMD.3923_13>
45 : : # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
46 : : # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
47 : : D.3915_4 = accessD.2606 (&fileNameD.2604, 1);
48 : : if (D.3915_4 == 0)
49 : : goto <bb 3>;
50 : : else
51 : : goto <bb 4>;
52 : : # SUCC: 3 [10.0%] (true,exec) 4 [90.0%] (false,exec)
53 : :
54 : : # BLOCK 3 freq:1000
55 : : # PRED: 2 [10.0%] (true,exec)
56 : : # .MEMD.3923_15 = VDEF <.MEMD.3923_14>
57 : : # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
58 : : # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
59 : : freeD.898 (ctxD.2601_5(D));
60 : : goto <bb 7>;
61 : : # SUCC: 7 [100.0%] (fallthru,exec)
62 : :
63 : : # BLOCK 4 freq:9000
64 : : # PRED: 2 [90.0%] (false,exec)
65 : : # .MEMD.3923_16 = VDEF <.MEMD.3923_14>
66 : : # PT = nonlocal escaped
67 : : # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
68 : : # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
69 : : fpD.2605_8 = fopenD.1805 (&fileNameD.2604[0], 0B);
70 : : if (fpD.2605_8 == 0B)
71 : : goto <bb 5>;
72 : : else
73 : : goto <bb 6>;
74 : : # SUCC: 5 [1.9%] (true,exec) 6 [98.1%] (false,exec)
75 : :
76 : : # BLOCK 5 freq:173
77 : : # PRED: 4 [1.9%] (true,exec)
78 : : # .MEMD.3923_17 = VDEF <.MEMD.3923_16>
79 : : # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
80 : : # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
81 : : freeD.898 (ctxD.2601_5(D));
82 : : goto <bb 7>;
83 : : # SUCC: 7 [100.0%] (fallthru,exec)
84 : :
85 : : # BLOCK 6 freq:8827
86 : : # PRED: 4 [98.1%] (false,exec)
87 : : # .MEMD.3923_18 = VDEF <.MEMD.3923_16>
88 : : # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
89 : : # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
90 : : fooD.2599 (outputFileNameD.2600_2(D), fpD.2605_8);
91 : : # SUCC: 7 [100.0%] (fallthru,exec)
92 : :
93 : : # BLOCK 7 freq:10000
94 : : # PRED: 3 [100.0%] (fallthru,exec) 5 [100.0%] (fallthru,exec)
95 : : 6 [100.0%] (fallthru,exec)
96 : : # PT = nonlocal null
97 : :
98 : : # ctxD.2601_1 = PHI <0B(3), 0B(5), ctxD.2601_5(D)(6)>
99 : : # .MEMD.3923_11 = PHI <.MEMD.3923_15(3), .MEMD.3923_17(5),
100 : : .MEMD.3923_18(6)>
101 : : # VUSE <.MEMD.3923_11>
102 : : return ctxD.2601_1;
103 : : # SUCC: EXIT [100.0%]
104 : : }
105 : :
106 : : bb 3 and bb 5 can be merged. The blocks have different predecessors, but the
107 : : same successors, and the same operations.
108 : :
109 : :
110 : : CONTEXT
111 : :
112 : : A technique called tail merging (or cross jumping) can fix the example
113 : : above. For a block, we look for common code at the end (the tail) of the
114 : : predecessor blocks, and insert jumps from one block to the other.
115 : : The example is a special case for tail merging, in that 2 whole blocks
116 : : can be merged, rather than just the end parts of it.
117 : : We currently only focus on whole block merging, so in that sense
118 : : calling this pass tail merge is a bit of a misnomer.
119 : :
120 : : We distinguish 2 kinds of situations in which blocks can be merged:
121 : : - same operations, same predecessors. The successor edges coming from one
122 : : block are redirected to come from the other block.
123 : : - same operations, same successors. The predecessor edges entering one block
124 : : are redirected to enter the other block. Note that this operation might
125 : : involve introducing phi operations.
126 : :
127 : : For efficient implementation, we would like to value numbers the blocks, and
128 : : have a comparison operator that tells us whether the blocks are equal.
129 : : Besides being runtime efficient, block value numbering should also abstract
130 : : from irrelevant differences in order of operations, much like normal value
131 : : numbering abstracts from irrelevant order of operations.
132 : :
133 : : For the first situation (same_operations, same predecessors), normal value
134 : : numbering fits well. We can calculate a block value number based on the
135 : : value numbers of the defs and vdefs.
136 : :
137 : : For the second situation (same operations, same successors), this approach
138 : : doesn't work so well. We can illustrate this using the example. The calls
139 : : to free use different vdefs: MEMD.3923_16 and MEMD.3923_14, and these will
140 : : remain different in value numbering, since they represent different memory
141 : : states. So the resulting vdefs of the frees will be different in value
142 : : numbering, so the block value numbers will be different.
143 : :
144 : : The reason why we call the blocks equal is not because they define the same
145 : : values, but because uses in the blocks use (possibly different) defs in the
146 : : same way. To be able to detect this efficiently, we need to do some kind of
147 : : reverse value numbering, meaning number the uses rather than the defs, and
148 : : calculate a block value number based on the value number of the uses.
149 : : Ideally, a block comparison operator will also indicate which phis are needed
150 : : to merge the blocks.
151 : :
152 : : For the moment, we don't do block value numbering, but we do insn-by-insn
153 : : matching, using scc value numbers to match operations with results, and
154 : : structural comparison otherwise, while ignoring vop mismatches.
155 : :
156 : :
157 : : IMPLEMENTATION
158 : :
159 : : 1. The pass first determines all groups of blocks with the same successor
160 : : blocks.
161 : : 2. Within each group, it tries to determine clusters of equal basic blocks.
162 : : 3. The clusters are applied.
163 : : 4. The same successor groups are updated.
164 : : 5. This process is repeated from 2 onwards, until no more changes.
165 : :
166 : :
167 : : LIMITATIONS/TODO
168 : :
169 : : - block only
170 : : - handles only 'same operations, same successors'.
171 : : It handles same predecessors as a special subcase though.
172 : : - does not implement the reverse value numbering and block value numbering.
173 : : - improve memory allocation: use garbage collected memory, obstacks,
174 : : allocpools where appropriate.
175 : : - no insertion of gimple_reg phis, We only introduce vop-phis.
176 : : - handle blocks with gimple_reg phi_nodes.
177 : :
178 : :
179 : : PASS PLACEMENT
180 : : This 'pass' is not a stand-alone gimple pass, but runs as part of
181 : : pass_pre, in order to share the value numbering.
182 : :
183 : :
184 : : SWITCHES
185 : :
186 : : - ftree-tail-merge. On at -O2. We may have to enable it only at -Os. */
187 : :
188 : : #include "config.h"
189 : : #include "system.h"
190 : : #include "coretypes.h"
191 : : #include "backend.h"
192 : : #include "tree.h"
193 : : #include "gimple.h"
194 : : #include "cfghooks.h"
195 : : #include "tree-pass.h"
196 : : #include "ssa.h"
197 : : #include "fold-const.h"
198 : : #include "trans-mem.h"
199 : : #include "cfganal.h"
200 : : #include "cfgcleanup.h"
201 : : #include "gimple-iterator.h"
202 : : #include "tree-cfg.h"
203 : : #include "tree-into-ssa.h"
204 : : #include "tree-ssa-sccvn.h"
205 : : #include "cfgloop.h"
206 : : #include "tree-eh.h"
207 : : #include "tree-cfgcleanup.h"
208 : :
209 : : const int ignore_edge_flags = EDGE_DFS_BACK | EDGE_EXECUTABLE;
210 : :
211 : : /* Describes a group of bbs with the same successors. The successor bbs are
212 : : cached in succs, and the successor edge flags are cached in succ_flags.
213 : : If a bb has the EDGE_TRUE/FALSE_VALUE flags swapped compared to succ_flags,
214 : : it's marked in inverse.
215 : : Additionally, the hash value for the struct is cached in hashval, and
216 : : in_worklist indicates whether it's currently part of worklist. */
217 : :
218 : : struct same_succ : pointer_hash <same_succ>
219 : : {
220 : : /* The bbs that have the same successor bbs. */
221 : : bitmap bbs;
222 : : /* The successor bbs. */
223 : : bitmap succs;
224 : : /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for
225 : : bb. */
226 : : bitmap inverse;
227 : : /* The edge flags for each of the successor bbs. */
228 : : vec<int> succ_flags;
229 : : /* Indicates whether the struct is currently in the worklist. */
230 : : bool in_worklist;
231 : : /* The hash value of the struct. */
232 : : hashval_t hashval;
233 : :
234 : : /* hash_table support. */
235 : : static inline hashval_t hash (const same_succ *);
236 : : static int equal (const same_succ *, const same_succ *);
237 : : static void remove (same_succ *);
238 : : };
239 : :
240 : : /* hash routine for hash_table support, returns hashval of E. */
241 : :
242 : : inline hashval_t
243 : 40823431 : same_succ::hash (const same_succ *e)
244 : : {
245 : 40823431 : return e->hashval;
246 : : }
247 : :
248 : : /* A group of bbs where 1 bb from bbs can replace the other bbs. */
249 : :
250 : : struct bb_cluster
251 : : {
252 : : /* The bbs in the cluster. */
253 : : bitmap bbs;
254 : : /* The preds of the bbs in the cluster. */
255 : : bitmap preds;
256 : : /* Index in all_clusters vector. */
257 : : int index;
258 : : /* The bb to replace the cluster with. */
259 : : basic_block rep_bb;
260 : : };
261 : :
262 : : /* Per bb-info. */
263 : :
264 : : struct aux_bb_info
265 : : {
266 : : /* The number of non-debug statements in the bb. */
267 : : int size;
268 : : /* The same_succ that this bb is a member of. */
269 : : same_succ *bb_same_succ;
270 : : /* The cluster that this bb is a member of. */
271 : : bb_cluster *cluster;
272 : : /* The vop state at the exit of a bb. This is shortlived data, used to
273 : : communicate data between update_block_by and update_vuses. */
274 : : tree vop_at_exit;
275 : : /* The bb that either contains or is dominated by the dependencies of the
276 : : bb. */
277 : : basic_block dep_bb;
278 : : };
279 : :
280 : : /* Macros to access the fields of struct aux_bb_info. */
281 : :
282 : : #define BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size)
283 : : #define BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ)
284 : : #define BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster)
285 : : #define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
286 : : #define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)
287 : :
288 : : /* Valueization helper querying the VN lattice. */
289 : :
290 : : static tree
291 : 12934771 : tail_merge_valueize (tree name)
292 : : {
293 : 12934771 : if (TREE_CODE (name) == SSA_NAME
294 : 12934771 : && has_VN_INFO (name))
295 : : {
296 : 4854675 : tree tem = VN_INFO (name)->valnum;
297 : 4854675 : if (tem != VN_TOP)
298 : : return tem;
299 : : }
300 : : return name;
301 : : }
302 : :
303 : : /* Returns true if the only effect a statement STMT has, is to define locally
304 : : used SSA_NAMEs. */
305 : :
306 : : static bool
307 : 37860573 : stmt_local_def (gimple *stmt)
308 : : {
309 : 37860573 : basic_block bb, def_bb;
310 : 37860573 : imm_use_iterator iter;
311 : 37860573 : use_operand_p use_p;
312 : 37860573 : tree val;
313 : 37860573 : def_operand_p def_p;
314 : :
315 : 37860573 : if (gimple_vdef (stmt) != NULL_TREE
316 : 24254660 : || gimple_has_side_effects (stmt)
317 : 23182408 : || gimple_could_trap_p_1 (stmt, false, false)
318 : 22437977 : || gimple_vuse (stmt) != NULL_TREE
319 : : /* Copied from tree-ssa-ifcombine.cc:bb_no_side_effects_p():
320 : : const calls don't match any of the above, yet they could
321 : : still have some side-effects - they could contain
322 : : gimple_could_trap_p statements, like floating point
323 : : exceptions or integer division by zero. See PR70586.
324 : : FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
325 : : should handle this. */
326 : 45960843 : || is_gimple_call (stmt))
327 : 22715353 : return false;
328 : :
329 : 15145220 : def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
330 : 15145220 : if (def_p == NULL)
331 : : return false;
332 : :
333 : 7853315 : val = DEF_FROM_PTR (def_p);
334 : 7853315 : if (val == NULL_TREE || TREE_CODE (val) != SSA_NAME)
335 : : return false;
336 : :
337 : 7853315 : def_bb = gimple_bb (stmt);
338 : :
339 : 7853315 : bool any_use = false;
340 : 16495606 : FOR_EACH_IMM_USE_FAST (use_p, iter, val)
341 : : {
342 : 9996502 : if (is_gimple_debug (USE_STMT (use_p)))
343 : 1201026 : continue;
344 : :
345 : 8795476 : any_use = true;
346 : 8795476 : bb = gimple_bb (USE_STMT (use_p));
347 : 8795476 : if (bb == def_bb)
348 : 6745567 : continue;
349 : :
350 : 2745607 : if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI
351 : 2049909 : && EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src == def_bb)
352 : 695698 : continue;
353 : :
354 : : return false;
355 : : }
356 : :
357 : : /* When there is no use avoid making the stmt live on other paths.
358 : : This can happen with DCE disabled or not done as seen in PR98845. */
359 : 6499104 : if (!any_use)
360 : : return false;
361 : :
362 : : return true;
363 : : }
364 : :
365 : : /* Let GSI skip forwards over local defs. */
366 : :
367 : : static void
368 : 7451126 : gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator *gsi)
369 : : {
370 : 7930896 : gimple *stmt;
371 : :
372 : 8410666 : while (true)
373 : : {
374 : 7930896 : if (gsi_end_p (*gsi))
375 : : return;
376 : 3040156 : stmt = gsi_stmt (*gsi);
377 : 3040156 : if (!stmt_local_def (stmt))
378 : : return;
379 : 479770 : gsi_next_nondebug (gsi);
380 : : }
381 : : }
382 : :
383 : : /* VAL1 and VAL2 are either:
384 : : - uses in BB1 and BB2, or
385 : : - phi alternatives for BB1 and BB2.
386 : : Return true if the uses have the same gvn value. */
387 : :
388 : : static bool
389 : 1195333 : gvn_uses_equal (tree val1, tree val2)
390 : : {
391 : 1195333 : gcc_checking_assert (val1 != NULL_TREE && val2 != NULL_TREE);
392 : :
393 : 1195333 : if (val1 == val2)
394 : : return true;
395 : :
396 : 1195333 : if (tail_merge_valueize (val1) != tail_merge_valueize (val2))
397 : : return false;
398 : :
399 : 0 : return ((TREE_CODE (val1) == SSA_NAME || CONSTANT_CLASS_P (val1))
400 : 27465 : && (TREE_CODE (val2) == SSA_NAME || CONSTANT_CLASS_P (val2)));
401 : : }
402 : :
403 : : /* Prints E to FILE. */
404 : :
405 : : static void
406 : 20 : same_succ_print (FILE *file, const same_succ *e)
407 : : {
408 : 20 : unsigned int i;
409 : 20 : bitmap_print (file, e->bbs, "bbs:", "\n");
410 : 20 : bitmap_print (file, e->succs, "succs:", "\n");
411 : 20 : bitmap_print (file, e->inverse, "inverse:", "\n");
412 : 20 : fprintf (file, "flags:");
413 : 60 : for (i = 0; i < e->succ_flags.length (); ++i)
414 : 20 : fprintf (file, " %x", e->succ_flags[i]);
415 : 20 : fprintf (file, "\n");
416 : 20 : }
417 : :
418 : : /* Prints same_succ VE to VFILE. */
419 : :
420 : : inline int
421 : 0 : ssa_same_succ_print_traverse (same_succ **pe, FILE *file)
422 : : {
423 : 0 : const same_succ *e = *pe;
424 : 0 : same_succ_print (file, e);
425 : 0 : return 1;
426 : : }
427 : :
428 : : /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */
429 : :
430 : : static void
431 : 33968026 : update_dep_bb (basic_block use_bb, tree val)
432 : : {
433 : 33968026 : basic_block dep_bb;
434 : :
435 : : /* Not a dep. */
436 : 33968026 : if (TREE_CODE (val) != SSA_NAME)
437 : : return;
438 : :
439 : : /* Skip use of global def. */
440 : 32489996 : if (SSA_NAME_IS_DEFAULT_DEF (val))
441 : : return;
442 : :
443 : : /* Skip use of local def. */
444 : 28292965 : dep_bb = gimple_bb (SSA_NAME_DEF_STMT (val));
445 : 28292965 : if (dep_bb == use_bb)
446 : : return;
447 : :
448 : 10445740 : if (BB_DEP_BB (use_bb) == NULL
449 : 10445740 : || dominated_by_p (CDI_DOMINATORS, dep_bb, BB_DEP_BB (use_bb)))
450 : 8992376 : BB_DEP_BB (use_bb) = dep_bb;
451 : : }
452 : :
453 : : /* Update BB_DEP_BB, given the dependencies in STMT. */
454 : :
455 : : static void
456 : 33743249 : stmt_update_dep_bb (gimple *stmt)
457 : : {
458 : 33743249 : ssa_op_iter iter;
459 : 33743249 : use_operand_p use;
460 : :
461 : 62243812 : FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
462 : 28500563 : update_dep_bb (gimple_bb (stmt), USE_FROM_PTR (use));
463 : 33743249 : }
464 : :
465 : : /* Calculates hash value for same_succ VE. */
466 : :
467 : : static hashval_t
468 : 13431121 : same_succ_hash (const same_succ *e)
469 : : {
470 : 13431121 : inchash::hash hstate (bitmap_hash (e->succs));
471 : 13431121 : int flags;
472 : 13431121 : unsigned int i;
473 : 13431121 : unsigned int first = bitmap_first_set_bit (e->bbs);
474 : 13431121 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, first);
475 : 13431121 : int size = 0;
476 : 13431121 : gimple *stmt;
477 : 13431121 : tree arg;
478 : 13431121 : unsigned int s;
479 : 13431121 : bitmap_iterator bs;
480 : :
481 : 13431121 : for (gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
482 : 47174370 : !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
483 : : {
484 : 33743249 : stmt = gsi_stmt (gsi);
485 : 33743249 : if (is_gimple_debug (stmt))
486 : 0 : continue;
487 : :
488 : 33743249 : stmt_update_dep_bb (stmt);
489 : 33743249 : if (stmt_local_def (stmt))
490 : 5995141 : continue;
491 : 27748108 : size++;
492 : :
493 : 27748108 : hstate.add_int (gimple_code (stmt));
494 : 27748108 : if (is_gimple_assign (stmt))
495 : 15429020 : hstate.add_int (gimple_assign_rhs_code (stmt));
496 : 27748108 : if (!is_gimple_call (stmt))
497 : 22415495 : continue;
498 : 5332613 : if (gimple_call_internal_p (stmt))
499 : 85426 : hstate.add_int (gimple_call_internal_fn (stmt));
500 : : else
501 : : {
502 : 5247187 : inchash::add_expr (gimple_call_fn (stmt), hstate);
503 : 5247187 : if (gimple_call_chain (stmt))
504 : 30273 : inchash::add_expr (gimple_call_chain (stmt), hstate);
505 : : }
506 : 15869628 : for (i = 0; i < gimple_call_num_args (stmt); i++)
507 : : {
508 : 10537015 : arg = gimple_call_arg (stmt, i);
509 : 10537015 : arg = tail_merge_valueize (arg);
510 : 10537015 : inchash::add_expr (arg, hstate);
511 : : }
512 : : }
513 : :
514 : 13431121 : hstate.add_int (size);
515 : 13431121 : BB_SIZE (bb) = size;
516 : :
517 : 13431121 : hstate.add_int (bb->loop_father->num);
518 : :
519 : 31624873 : for (i = 0; i < e->succ_flags.length (); ++i)
520 : : {
521 : 18193752 : flags = e->succ_flags[i];
522 : 18193752 : flags = flags & ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
523 : 18193752 : hstate.add_int (flags);
524 : : }
525 : :
526 : 31624873 : EXECUTE_IF_SET_IN_BITMAP (e->succs, 0, s, bs)
527 : : {
528 : 18193752 : int n = find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, s))->dest_idx;
529 : 18193752 : for (gphi_iterator gsi = gsi_start_phis (BASIC_BLOCK_FOR_FN (cfun, s));
530 : 27916085 : !gsi_end_p (gsi);
531 : 9722333 : gsi_next (&gsi))
532 : : {
533 : 9722333 : gphi *phi = gsi.phi ();
534 : 9722333 : tree lhs = gimple_phi_result (phi);
535 : 9722333 : tree val = gimple_phi_arg_def (phi, n);
536 : :
537 : 19444666 : if (virtual_operand_p (lhs))
538 : 4254870 : continue;
539 : 5467463 : update_dep_bb (bb, val);
540 : : }
541 : : }
542 : :
543 : 13431121 : return hstate.end ();
544 : : }
545 : :
546 : : /* Returns true if E1 and E2 have 2 successors, and if the successor flags
547 : : are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
548 : : the other edge flags. */
549 : :
550 : : static bool
551 : 4890783 : inverse_flags (const same_succ *e1, const same_succ *e2)
552 : : {
553 : 4890783 : int f1a, f1b, f2a, f2b;
554 : 4890783 : int mask = ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
555 : :
556 : 4904081 : if (e1->succ_flags.length () != 2)
557 : : return false;
558 : :
559 : 14872 : f1a = e1->succ_flags[0];
560 : 14872 : f1b = e1->succ_flags[1];
561 : 14872 : f2a = e2->succ_flags[0];
562 : 14872 : f2b = e2->succ_flags[1];
563 : :
564 : 14872 : if (f1a == f2a && f1b == f2b)
565 : : return false;
566 : :
567 : 1574 : return (f1a & mask) == (f2a & mask) && (f1b & mask) == (f2b & mask);
568 : : }
569 : :
570 : : /* Compares SAME_SUCCs E1 and E2. */
571 : :
572 : : int
573 : 48920118 : same_succ::equal (const same_succ *e1, const same_succ *e2)
574 : : {
575 : 48920118 : unsigned int i, first1, first2;
576 : 48920118 : gimple_stmt_iterator gsi1, gsi2;
577 : 48920118 : gimple *s1, *s2;
578 : 48920118 : basic_block bb1, bb2;
579 : :
580 : 48920118 : if (e1 == e2)
581 : : return 1;
582 : :
583 : 47837494 : if (e1->hashval != e2->hashval)
584 : : return 0;
585 : :
586 : 7718313 : if (e1->succ_flags.length () != e2->succ_flags.length ())
587 : : return 0;
588 : :
589 : 2572771 : if (!bitmap_equal_p (e1->succs, e2->succs))
590 : : return 0;
591 : :
592 : 2445413 : if (!inverse_flags (e1, e2))
593 : : {
594 : 4558797 : for (i = 0; i < e1->succ_flags.length (); ++i)
595 : 2114171 : if (e1->succ_flags[i] != e2->succ_flags[i])
596 : : return 0;
597 : : }
598 : :
599 : 2445413 : first1 = bitmap_first_set_bit (e1->bbs);
600 : 2445413 : first2 = bitmap_first_set_bit (e2->bbs);
601 : :
602 : 2445413 : bb1 = BASIC_BLOCK_FOR_FN (cfun, first1);
603 : 2445413 : bb2 = BASIC_BLOCK_FOR_FN (cfun, first2);
604 : :
605 : 2445413 : if (BB_SIZE (bb1) != BB_SIZE (bb2))
606 : : return 0;
607 : :
608 : 2445413 : if (bb1->loop_father != bb2->loop_father)
609 : : return 0;
610 : :
611 : 2445413 : gsi1 = gsi_start_nondebug_bb (bb1);
612 : 2445413 : gsi2 = gsi_start_nondebug_bb (bb2);
613 : 2445413 : gsi_advance_fw_nondebug_nonlocal (&gsi1);
614 : 2445413 : gsi_advance_fw_nondebug_nonlocal (&gsi2);
615 : 6170976 : while (!(gsi_end_p (gsi1) || gsi_end_p (gsi2)))
616 : : {
617 : 1280193 : s1 = gsi_stmt (gsi1);
618 : 1280193 : s2 = gsi_stmt (gsi2);
619 : 1280193 : if (gimple_code (s1) != gimple_code (s2))
620 : : return 0;
621 : 1280193 : if (is_gimple_call (s1) && !gimple_call_same_target_p (s1, s2))
622 : : return 0;
623 : 1280150 : gsi_next_nondebug (&gsi1);
624 : 1280150 : gsi_next_nondebug (&gsi2);
625 : 1280150 : gsi_advance_fw_nondebug_nonlocal (&gsi1);
626 : 1280150 : gsi_advance_fw_nondebug_nonlocal (&gsi2);
627 : : }
628 : :
629 : : return 1;
630 : : }
631 : :
632 : : /* Alloc and init a new SAME_SUCC. */
633 : :
634 : : static same_succ *
635 : 12108552 : same_succ_alloc (void)
636 : : {
637 : 12108552 : same_succ *same = XNEW (struct same_succ);
638 : :
639 : 12108552 : same->bbs = BITMAP_ALLOC (NULL);
640 : 12108552 : same->succs = BITMAP_ALLOC (NULL);
641 : 12108552 : same->inverse = BITMAP_ALLOC (NULL);
642 : 12108552 : same->succ_flags.create (10);
643 : 12108552 : same->in_worklist = false;
644 : :
645 : 12108552 : return same;
646 : : }
647 : :
648 : : /* Delete same_succ E. */
649 : :
650 : : void
651 : 12108552 : same_succ::remove (same_succ *e)
652 : : {
653 : 12108552 : BITMAP_FREE (e->bbs);
654 : 12108552 : BITMAP_FREE (e->succs);
655 : 12108552 : BITMAP_FREE (e->inverse);
656 : 12108552 : e->succ_flags.release ();
657 : :
658 : 12108552 : XDELETE (e);
659 : 12108552 : }
660 : :
661 : : /* Reset same_succ SAME. */
662 : :
663 : : static void
664 : 2445370 : same_succ_reset (same_succ *same)
665 : : {
666 : 2445370 : bitmap_clear (same->bbs);
667 : 2445370 : bitmap_clear (same->succs);
668 : 2445370 : bitmap_clear (same->inverse);
669 : 2445370 : same->succ_flags.truncate (0);
670 : 2445370 : }
671 : :
672 : : static hash_table<same_succ> *same_succ_htab;
673 : :
674 : : /* Array that is used to store the edge flags for a successor. */
675 : :
676 : : static int *same_succ_edge_flags;
677 : :
678 : : /* Bitmap that is used to mark bbs that are recently deleted. */
679 : :
680 : : static bitmap deleted_bbs;
681 : :
682 : : /* Bitmap that is used to mark predecessors of bbs that are
683 : : deleted. */
684 : :
685 : : static bitmap deleted_bb_preds;
686 : :
687 : : /* Prints same_succ_htab to stderr. */
688 : :
689 : : extern void debug_same_succ (void);
690 : : DEBUG_FUNCTION void
691 : 0 : debug_same_succ ( void)
692 : : {
693 : 0 : same_succ_htab->traverse <FILE *, ssa_same_succ_print_traverse> (stderr);
694 : 0 : }
695 : :
696 : :
697 : : /* Vector of bbs to process. */
698 : :
699 : : static vec<same_succ *> worklist;
700 : :
701 : : /* Prints worklist to FILE. */
702 : :
703 : : static void
704 : 14 : print_worklist (FILE *file)
705 : : {
706 : 14 : unsigned int i;
707 : 24 : for (i = 0; i < worklist.length (); ++i)
708 : 10 : same_succ_print (file, worklist[i]);
709 : 14 : }
710 : :
711 : : /* Adds SAME to worklist. */
712 : :
713 : : static void
714 : 13431121 : add_to_worklist (same_succ *same)
715 : : {
716 : 13431121 : if (same->in_worklist)
717 : : return;
718 : :
719 : 12042788 : if (bitmap_count_bits (same->bbs) < 2)
720 : : return;
721 : :
722 : 1057037 : same->in_worklist = true;
723 : 1057037 : worklist.safe_push (same);
724 : : }
725 : :
726 : : /* Add BB to same_succ_htab. */
727 : :
728 : : static void
729 : 13431121 : find_same_succ_bb (basic_block bb, same_succ **same_p)
730 : : {
731 : 13431121 : unsigned int j;
732 : 13431121 : bitmap_iterator bj;
733 : 13431121 : same_succ *same = *same_p;
734 : 13431121 : same_succ **slot;
735 : 13431121 : edge_iterator ei;
736 : 13431121 : edge e;
737 : :
738 : 13431121 : if (bb == NULL)
739 : 0 : return;
740 : 13431121 : bitmap_set_bit (same->bbs, bb->index);
741 : 31624873 : FOR_EACH_EDGE (e, ei, bb->succs)
742 : : {
743 : 18193752 : int index = e->dest->index;
744 : 18193752 : bitmap_set_bit (same->succs, index);
745 : 18193752 : same_succ_edge_flags[index] = (e->flags & ~ignore_edge_flags);
746 : : }
747 : 31624873 : EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
748 : 18193752 : same->succ_flags.safe_push (same_succ_edge_flags[j]);
749 : :
750 : 13431121 : same->hashval = same_succ_hash (same);
751 : :
752 : 13431121 : slot = same_succ_htab->find_slot_with_hash (same, same->hashval, INSERT);
753 : 13431121 : if (*slot == NULL)
754 : : {
755 : 10985751 : *slot = same;
756 : 10985751 : BB_SAME_SUCC (bb) = same;
757 : 10985751 : add_to_worklist (same);
758 : 10985751 : *same_p = NULL;
759 : : }
760 : : else
761 : : {
762 : 2445370 : bitmap_set_bit ((*slot)->bbs, bb->index);
763 : 2445370 : BB_SAME_SUCC (bb) = *slot;
764 : 2445370 : add_to_worklist (*slot);
765 : 2445370 : if (inverse_flags (same, *slot))
766 : 787 : bitmap_set_bit ((*slot)->inverse, bb->index);
767 : 2445370 : same_succ_reset (same);
768 : : }
769 : : }
770 : :
771 : : /* Find bbs with same successors. */
772 : :
773 : : static void
774 : 927912 : find_same_succ (void)
775 : : {
776 : 927912 : same_succ *same = same_succ_alloc ();
777 : 927912 : basic_block bb;
778 : :
779 : 13272936 : FOR_EACH_BB_FN (bb, cfun)
780 : : {
781 : 12345024 : find_same_succ_bb (bb, &same);
782 : 12345024 : if (same == NULL)
783 : 9952516 : same = same_succ_alloc ();
784 : : }
785 : :
786 : 927912 : same_succ::remove (same);
787 : 927912 : }
788 : :
789 : : /* Initializes worklist administration. */
790 : :
791 : : static void
792 : 927912 : init_worklist (void)
793 : : {
794 : 927912 : alloc_aux_for_blocks (sizeof (struct aux_bb_info));
795 : 927912 : same_succ_htab = new hash_table<same_succ> (n_basic_blocks_for_fn (cfun));
796 : 927912 : same_succ_edge_flags = XCNEWVEC (int, last_basic_block_for_fn (cfun));
797 : 927912 : deleted_bbs = BITMAP_ALLOC (NULL);
798 : 927912 : deleted_bb_preds = BITMAP_ALLOC (NULL);
799 : 927912 : worklist.create (n_basic_blocks_for_fn (cfun));
800 : 927912 : find_same_succ ();
801 : :
802 : 927912 : if (dump_file && (dump_flags & TDF_DETAILS))
803 : : {
804 : 14 : fprintf (dump_file, "initial worklist:\n");
805 : 14 : print_worklist (dump_file);
806 : : }
807 : 927912 : }
808 : :
809 : : /* Deletes worklist administration. */
810 : :
811 : : static void
812 : 927912 : delete_worklist (void)
813 : : {
814 : 927912 : free_aux_for_blocks ();
815 : 927912 : delete same_succ_htab;
816 : 927912 : same_succ_htab = NULL;
817 : 927912 : XDELETEVEC (same_succ_edge_flags);
818 : 927912 : same_succ_edge_flags = NULL;
819 : 927912 : BITMAP_FREE (deleted_bbs);
820 : 927912 : BITMAP_FREE (deleted_bb_preds);
821 : 927912 : worklist.release ();
822 : 927912 : }
823 : :
824 : : /* Mark BB as deleted, and mark its predecessors. */
825 : :
826 : : static void
827 : 1181238 : mark_basic_block_deleted (basic_block bb)
828 : : {
829 : 1181238 : edge e;
830 : 1181238 : edge_iterator ei;
831 : :
832 : 1181238 : bitmap_set_bit (deleted_bbs, bb->index);
833 : :
834 : 2485104 : FOR_EACH_EDGE (e, ei, bb->preds)
835 : 1303866 : bitmap_set_bit (deleted_bb_preds, e->src->index);
836 : 1181238 : }
837 : :
838 : : /* Removes BB from its corresponding same_succ. */
839 : :
840 : : static void
841 : 2267335 : same_succ_flush_bb (basic_block bb)
842 : : {
843 : 2267335 : same_succ *same = BB_SAME_SUCC (bb);
844 : 2267335 : if (! same)
845 : 0 : return;
846 : :
847 : 2267335 : BB_SAME_SUCC (bb) = NULL;
848 : 2267335 : if (bitmap_single_bit_set_p (same->bbs))
849 : 1082624 : same_succ_htab->remove_elt_with_hash (same, same->hashval);
850 : : else
851 : 1184711 : bitmap_clear_bit (same->bbs, bb->index);
852 : : }
853 : :
854 : : /* Removes all bbs in BBS from their corresponding same_succ. */
855 : :
856 : : static void
857 : 194889 : same_succ_flush_bbs (bitmap bbs)
858 : : {
859 : 194889 : unsigned int i;
860 : 194889 : bitmap_iterator bi;
861 : :
862 : 1280986 : EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
863 : 1086097 : same_succ_flush_bb (BASIC_BLOCK_FOR_FN (cfun, i));
864 : 194889 : }
865 : :
866 : : /* Release the last vdef in BB, either normal or phi result. */
867 : :
868 : : static void
869 : 1181238 : release_last_vdef (basic_block bb)
870 : : {
871 : 2505272 : for (gimple_stmt_iterator i = gsi_last_bb (bb); !gsi_end_p (i);
872 : 142796 : gsi_prev_nondebug (&i))
873 : : {
874 : 386592 : gimple *stmt = gsi_stmt (i);
875 : 757515 : if (gimple_vdef (stmt) == NULL_TREE)
876 : 142796 : continue;
877 : :
878 : 243796 : mark_virtual_operand_for_renaming (gimple_vdef (stmt));
879 : 243796 : return;
880 : : }
881 : :
882 : 937442 : for (gphi_iterator i = gsi_start_phis (bb); !gsi_end_p (i);
883 : 0 : gsi_next (&i))
884 : : {
885 : 690 : gphi *phi = i.phi ();
886 : 690 : tree res = gimple_phi_result (phi);
887 : :
888 : 1380 : if (!virtual_operand_p (res))
889 : 0 : continue;
890 : :
891 : 690 : mark_virtual_phi_result_for_renaming (phi);
892 : 690 : return;
893 : : }
894 : : }
895 : :
896 : : /* For deleted_bb_preds, find bbs with same successors. */
897 : :
898 : : static void
899 : 194889 : update_worklist (void)
900 : : {
901 : 194889 : unsigned int i;
902 : 194889 : bitmap_iterator bi;
903 : 194889 : basic_block bb;
904 : 194889 : same_succ *same;
905 : :
906 : 194889 : bitmap_and_compl_into (deleted_bb_preds, deleted_bbs);
907 : 194889 : bitmap_clear (deleted_bbs);
908 : :
909 : 194889 : bitmap_clear_bit (deleted_bb_preds, ENTRY_BLOCK);
910 : 194889 : same_succ_flush_bbs (deleted_bb_preds);
911 : :
912 : 194889 : same = same_succ_alloc ();
913 : 1280986 : EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds, 0, i, bi)
914 : : {
915 : 1086097 : bb = BASIC_BLOCK_FOR_FN (cfun, i);
916 : 1086097 : gcc_assert (bb != NULL);
917 : 1086097 : find_same_succ_bb (bb, &same);
918 : 1086097 : if (same == NULL)
919 : 1033235 : same = same_succ_alloc ();
920 : : }
921 : 194889 : same_succ::remove (same);
922 : 194889 : bitmap_clear (deleted_bb_preds);
923 : 194889 : }
924 : :
925 : : /* Prints cluster C to FILE. */
926 : :
927 : : static void
928 : 0 : print_cluster (FILE *file, bb_cluster *c)
929 : : {
930 : 0 : if (c == NULL)
931 : : return;
932 : 0 : bitmap_print (file, c->bbs, "bbs:", "\n");
933 : 0 : bitmap_print (file, c->preds, "preds:", "\n");
934 : : }
935 : :
936 : : /* Prints cluster C to stderr. */
937 : :
938 : : extern void debug_cluster (bb_cluster *);
939 : : DEBUG_FUNCTION void
940 : 0 : debug_cluster (bb_cluster *c)
941 : : {
942 : 0 : print_cluster (stderr, c);
943 : 0 : }
944 : :
945 : : /* Update C->rep_bb, given that BB is added to the cluster. */
946 : :
947 : : static void
948 : 1753339 : update_rep_bb (bb_cluster *c, basic_block bb)
949 : : {
950 : : /* Initial. */
951 : 1753339 : if (c->rep_bb == NULL)
952 : : {
953 : 572101 : c->rep_bb = bb;
954 : 572101 : return;
955 : : }
956 : :
957 : : /* Current needs no deps, keep it. */
958 : 1181238 : if (BB_DEP_BB (c->rep_bb) == NULL)
959 : : return;
960 : :
961 : : /* Bb needs no deps, change rep_bb. */
962 : 17133 : if (BB_DEP_BB (bb) == NULL)
963 : : {
964 : 92 : c->rep_bb = bb;
965 : 92 : return;
966 : : }
967 : :
968 : : /* Bb needs last deps earlier than current, change rep_bb. A potential
969 : : problem with this, is that the first deps might also be earlier, which
970 : : would mean we prefer longer lifetimes for the deps. To be able to check
971 : : for this, we would have to trace BB_FIRST_DEP_BB as well, besides
972 : : BB_DEP_BB, which is really BB_LAST_DEP_BB.
973 : : The benefit of choosing the bb with last deps earlier, is that it can
974 : : potentially be used as replacement for more bbs. */
975 : 17041 : if (dominated_by_p (CDI_DOMINATORS, BB_DEP_BB (c->rep_bb), BB_DEP_BB (bb)))
976 : 16718 : c->rep_bb = bb;
977 : : }
978 : :
979 : : /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
980 : :
981 : : static void
982 : 1753339 : add_bb_to_cluster (bb_cluster *c, basic_block bb)
983 : : {
984 : 1753339 : edge e;
985 : 1753339 : edge_iterator ei;
986 : :
987 : 1753339 : bitmap_set_bit (c->bbs, bb->index);
988 : :
989 : 3782770 : FOR_EACH_EDGE (e, ei, bb->preds)
990 : 2029431 : bitmap_set_bit (c->preds, e->src->index);
991 : :
992 : 1753339 : update_rep_bb (c, bb);
993 : 1753339 : }
994 : :
995 : : /* Allocate and init new cluster. */
996 : :
997 : : static bb_cluster *
998 : 572101 : new_cluster (void)
999 : : {
1000 : 572101 : bb_cluster *c;
1001 : 572101 : c = XCNEW (bb_cluster);
1002 : 572101 : c->bbs = BITMAP_ALLOC (NULL);
1003 : 572101 : c->preds = BITMAP_ALLOC (NULL);
1004 : 572101 : c->rep_bb = NULL;
1005 : 572101 : return c;
1006 : : }
1007 : :
1008 : : /* Delete clusters. */
1009 : :
1010 : : static void
1011 : 572101 : delete_cluster (bb_cluster *c)
1012 : : {
1013 : 572101 : if (c == NULL)
1014 : : return;
1015 : 572101 : BITMAP_FREE (c->bbs);
1016 : 572101 : BITMAP_FREE (c->preds);
1017 : 572101 : XDELETE (c);
1018 : : }
1019 : :
1020 : :
1021 : : /* Array that contains all clusters. */
1022 : :
1023 : : static vec<bb_cluster *> all_clusters;
1024 : :
1025 : : /* Allocate all cluster vectors. */
1026 : :
1027 : : static void
1028 : 250261 : alloc_cluster_vectors (void)
1029 : : {
1030 : 250261 : all_clusters.create (n_basic_blocks_for_fn (cfun));
1031 : 250261 : }
1032 : :
1033 : : /* Reset all cluster vectors. */
1034 : :
1035 : : static void
1036 : 11682 : reset_cluster_vectors (void)
1037 : : {
1038 : 11682 : unsigned int i;
1039 : 11682 : basic_block bb;
1040 : 126767 : for (i = 0; i < all_clusters.length (); ++i)
1041 : 115085 : delete_cluster (all_clusters[i]);
1042 : 11682 : all_clusters.truncate (0);
1043 : 1244492 : FOR_EACH_BB_FN (bb, cfun)
1044 : 1232810 : BB_CLUSTER (bb) = NULL;
1045 : 11682 : }
1046 : :
1047 : : /* Delete all cluster vectors. */
1048 : :
1049 : : static void
1050 : 250261 : delete_cluster_vectors (void)
1051 : : {
1052 : 250261 : unsigned int i;
1053 : 707277 : for (i = 0; i < all_clusters.length (); ++i)
1054 : 457016 : delete_cluster (all_clusters[i]);
1055 : 250261 : all_clusters.release ();
1056 : 250261 : }
1057 : :
1058 : : /* Merge cluster C2 into C1. */
1059 : :
1060 : : static void
1061 : 0 : merge_clusters (bb_cluster *c1, bb_cluster *c2)
1062 : : {
1063 : 0 : bitmap_ior_into (c1->bbs, c2->bbs);
1064 : 0 : bitmap_ior_into (c1->preds, c2->preds);
1065 : 0 : }
1066 : :
1067 : : /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
1068 : : all_clusters, or merge c with existing cluster. */
1069 : :
1070 : : static void
1071 : 1181238 : set_cluster (basic_block bb1, basic_block bb2)
1072 : : {
1073 : 1181238 : basic_block merge_bb, other_bb;
1074 : 1181238 : bb_cluster *merge, *old, *c;
1075 : :
1076 : 1181238 : if (BB_CLUSTER (bb1) == NULL && BB_CLUSTER (bb2) == NULL)
1077 : : {
1078 : 572101 : c = new_cluster ();
1079 : 572101 : add_bb_to_cluster (c, bb1);
1080 : 572101 : add_bb_to_cluster (c, bb2);
1081 : 572101 : BB_CLUSTER (bb1) = c;
1082 : 572101 : BB_CLUSTER (bb2) = c;
1083 : 572101 : c->index = all_clusters.length ();
1084 : 572101 : all_clusters.safe_push (c);
1085 : : }
1086 : 609137 : else if (BB_CLUSTER (bb1) == NULL || BB_CLUSTER (bb2) == NULL)
1087 : : {
1088 : 609137 : merge_bb = BB_CLUSTER (bb1) == NULL ? bb2 : bb1;
1089 : 609137 : other_bb = BB_CLUSTER (bb1) == NULL ? bb1 : bb2;
1090 : 609137 : merge = BB_CLUSTER (merge_bb);
1091 : 609137 : add_bb_to_cluster (merge, other_bb);
1092 : 609137 : BB_CLUSTER (other_bb) = merge;
1093 : : }
1094 : 0 : else if (BB_CLUSTER (bb1) != BB_CLUSTER (bb2))
1095 : : {
1096 : 0 : unsigned int i;
1097 : 0 : bitmap_iterator bi;
1098 : :
1099 : 0 : old = BB_CLUSTER (bb2);
1100 : 0 : merge = BB_CLUSTER (bb1);
1101 : 0 : merge_clusters (merge, old);
1102 : 0 : EXECUTE_IF_SET_IN_BITMAP (old->bbs, 0, i, bi)
1103 : 0 : BB_CLUSTER (BASIC_BLOCK_FOR_FN (cfun, i)) = merge;
1104 : 0 : all_clusters[old->index] = NULL;
1105 : 0 : update_rep_bb (merge, old->rep_bb);
1106 : 0 : delete_cluster (old);
1107 : : }
1108 : : else
1109 : 0 : gcc_unreachable ();
1110 : 1181238 : }
1111 : :
1112 : : /* Return true if gimple operands T1 and T2 have the same value. */
1113 : :
1114 : : static bool
1115 : 816710 : gimple_operand_equal_value_p (tree t1, tree t2)
1116 : : {
1117 : 816710 : if (t1 == t2)
1118 : : return true;
1119 : :
1120 : 184686 : if (t1 == NULL_TREE
1121 : 184686 : || t2 == NULL_TREE)
1122 : : return false;
1123 : :
1124 : 184686 : if (operand_equal_p (t1, t2, OEP_MATCH_SIDE_EFFECTS))
1125 : : return true;
1126 : :
1127 : 57379 : return gvn_uses_equal (t1, t2);
1128 : : }
1129 : :
1130 : : /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
1131 : : gimple_bb (s2) are members of SAME_SUCC. */
1132 : :
1133 : : static bool
1134 : 522276 : gimple_equal_p (same_succ *same_succ, gimple *s1, gimple *s2)
1135 : : {
1136 : 522276 : unsigned int i;
1137 : 522276 : tree lhs1, lhs2;
1138 : 522276 : basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
1139 : 522276 : tree t1, t2;
1140 : 522276 : bool inv_cond;
1141 : 522276 : enum tree_code code1, code2;
1142 : :
1143 : 522276 : if (gimple_code (s1) != gimple_code (s2))
1144 : : return false;
1145 : :
1146 : 522276 : switch (gimple_code (s1))
1147 : : {
1148 : 403368 : case GIMPLE_CALL:
1149 : 403368 : if (!gimple_call_same_target_p (s1, s2))
1150 : : return false;
1151 : :
1152 : 403368 : t1 = gimple_call_chain (s1);
1153 : 403368 : t2 = gimple_call_chain (s2);
1154 : 403368 : if (!gimple_operand_equal_value_p (t1, t2))
1155 : : return false;
1156 : :
1157 : 403368 : if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
1158 : : return false;
1159 : :
1160 : 712394 : for (i = 0; i < gimple_call_num_args (s1); ++i)
1161 : : {
1162 : 309034 : t1 = gimple_call_arg (s1, i);
1163 : 309034 : t2 = gimple_call_arg (s2, i);
1164 : 309034 : if (!gimple_operand_equal_value_p (t1, t2))
1165 : : return false;
1166 : : }
1167 : :
1168 : 403360 : lhs1 = gimple_get_lhs (s1);
1169 : 403360 : lhs2 = gimple_get_lhs (s2);
1170 : 403360 : if (lhs1 == NULL_TREE && lhs2 == NULL_TREE)
1171 : : return true;
1172 : 3699 : if (lhs1 == NULL_TREE || lhs2 == NULL_TREE)
1173 : : return false;
1174 : 3699 : if (TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME)
1175 : 3545 : return tail_merge_valueize (lhs1) == tail_merge_valueize (lhs2);
1176 : 154 : return operand_equal_p (lhs1, lhs2, 0);
1177 : :
1178 : 109387 : case GIMPLE_ASSIGN:
1179 : 109387 : if (gimple_assign_rhs_code (s1) != gimple_assign_rhs_code (s2))
1180 : : return false;
1181 : :
1182 : 109387 : lhs1 = gimple_get_lhs (s1);
1183 : 109387 : lhs2 = gimple_get_lhs (s2);
1184 : 109387 : if (TREE_CODE (lhs1) != SSA_NAME
1185 : 92126 : && TREE_CODE (lhs2) != SSA_NAME)
1186 : 92052 : return (operand_equal_p (lhs1, lhs2, 0)
1187 : 92052 : && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1),
1188 : : gimple_assign_rhs1 (s2)));
1189 : :
1190 : 17335 : if (TREE_CODE (lhs1) != SSA_NAME
1191 : 17261 : || TREE_CODE (lhs2) != SSA_NAME)
1192 : : return false;
1193 : :
1194 : 17261 : gcc_checking_assert (gimple_num_args (s1) == gimple_num_args (s2));
1195 : 34401 : for (i = 0; i < gimple_num_args (s1); ++i)
1196 : : {
1197 : 17422 : t1 = gimple_arg (s1, i);
1198 : 17422 : t2 = gimple_arg (s2, i);
1199 : 38031 : while (handled_component_p (t1) && handled_component_p (t2))
1200 : : {
1201 : 3396 : if (TREE_CODE (t1) != TREE_CODE (t2)
1202 : 3396 : || TREE_THIS_VOLATILE (t1) != TREE_THIS_VOLATILE (t2))
1203 : : return false;
1204 : 3396 : switch (TREE_CODE (t1))
1205 : : {
1206 : 3322 : case COMPONENT_REF:
1207 : 3322 : if (TREE_OPERAND (t1, 1) != TREE_OPERAND (t2, 1)
1208 : 6435 : || !gimple_operand_equal_value_p (TREE_OPERAND (t1, 2),
1209 : 3113 : TREE_OPERAND (t2, 2)))
1210 : 209 : return false;
1211 : : break;
1212 : 54 : case ARRAY_REF:
1213 : 54 : case ARRAY_RANGE_REF:
1214 : 54 : if (!gimple_operand_equal_value_p (TREE_OPERAND (t1, 3),
1215 : 54 : TREE_OPERAND (t2, 3)))
1216 : : return false;
1217 : : /* Fallthru. */
1218 : 74 : case BIT_FIELD_REF:
1219 : 74 : if (!gimple_operand_equal_value_p (TREE_OPERAND (t1, 1),
1220 : 74 : TREE_OPERAND (t2, 1))
1221 : 148 : || !gimple_operand_equal_value_p (TREE_OPERAND (t1, 2),
1222 : 74 : TREE_OPERAND (t2, 2)))
1223 : 0 : return false;
1224 : : break;
1225 : : case REALPART_EXPR:
1226 : : case IMAGPART_EXPR:
1227 : : case VIEW_CONVERT_EXPR:
1228 : : break;
1229 : : default:
1230 : : gcc_unreachable ();
1231 : : }
1232 : 3187 : t1 = TREE_OPERAND (t1, 0);
1233 : 3187 : t2 = TREE_OPERAND (t2, 0);
1234 : : }
1235 : 17213 : if (TREE_CODE (t1) == MEM_REF && TREE_CODE (t2) == MEM_REF)
1236 : : {
1237 : 6298 : if (TREE_THIS_VOLATILE (t1) != TREE_THIS_VOLATILE (t2)
1238 : 6298 : || TYPE_ALIGN (TREE_TYPE (t1)) != TYPE_ALIGN (TREE_TYPE (t2))
1239 : 6298 : || !gimple_operand_equal_value_p (TREE_OPERAND (t1, 0),
1240 : 6298 : TREE_OPERAND (t2, 0))
1241 : 12596 : || TREE_OPERAND (t1, 1) != TREE_OPERAND (t2, 1))
1242 : 55 : return false;
1243 : : }
1244 : 10915 : else if (!gimple_operand_equal_value_p (t1, t2))
1245 : : return false;
1246 : : }
1247 : : return true;
1248 : :
1249 : 4317 : case GIMPLE_COND:
1250 : 4317 : t1 = gimple_cond_lhs (s1);
1251 : 4317 : t2 = gimple_cond_lhs (s2);
1252 : 4317 : if (!gimple_operand_equal_value_p (t1, t2))
1253 : : return false;
1254 : :
1255 : 1551 : t1 = gimple_cond_rhs (s1);
1256 : 1551 : t2 = gimple_cond_rhs (s2);
1257 : 1551 : if (!gimple_operand_equal_value_p (t1, t2))
1258 : : return false;
1259 : :
1260 : 841 : code1 = gimple_cond_code (s1);
1261 : 841 : code2 = gimple_cond_code (s2);
1262 : 841 : inv_cond = (bitmap_bit_p (same_succ->inverse, bb1->index)
1263 : 841 : != bitmap_bit_p (same_succ->inverse, bb2->index));
1264 : 841 : if (inv_cond)
1265 : : {
1266 : 23 : bool honor_nans = HONOR_NANS (t1);
1267 : 23 : code2 = invert_tree_comparison (code2, honor_nans);
1268 : : }
1269 : 841 : return code1 == code2;
1270 : :
1271 : : default:
1272 : : return false;
1273 : : }
1274 : : }
1275 : :
1276 : : /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
1277 : : Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
1278 : : processed statements. */
1279 : :
1280 : : static void
1281 : 3422464 : gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse,
1282 : : bool *vuse_escaped)
1283 : : {
1284 : 3428876 : gimple *stmt;
1285 : 3428876 : tree lvuse;
1286 : :
1287 : 3435288 : while (true)
1288 : : {
1289 : 3428876 : if (gsi_end_p (*gsi))
1290 : : return;
1291 : 1077168 : stmt = gsi_stmt (*gsi);
1292 : :
1293 : 1077168 : lvuse = gimple_vuse (stmt);
1294 : 1036180 : if (lvuse != NULL_TREE)
1295 : : {
1296 : 796256 : *vuse = lvuse;
1297 : 796256 : if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_DEF))
1298 : 41150 : *vuse_escaped = true;
1299 : : }
1300 : :
1301 : 1077168 : if (!stmt_local_def (stmt))
1302 : : return;
1303 : 6412 : gsi_prev_nondebug (gsi);
1304 : : }
1305 : : }
1306 : :
1307 : : /* Return true if equal (in the sense of gimple_equal_p) statements STMT1 and
1308 : : STMT2 are allowed to be merged. */
1309 : :
1310 : : static bool
1311 : 460177 : merge_stmts_p (gimple *stmt1, gimple *stmt2)
1312 : : {
1313 : : /* What could be better than this here is to blacklist the bb
1314 : : containing the stmt, when encountering the stmt f.i. in
1315 : : same_succ_hash. */
1316 : 460177 : if (is_tm_ending (stmt1))
1317 : : return false;
1318 : :
1319 : : /* Verify EH landing pads. */
1320 : 460125 : if (lookup_stmt_eh_lp_fn (cfun, stmt1) != lookup_stmt_eh_lp_fn (cfun, stmt2))
1321 : : return false;
1322 : :
1323 : 452678 : if (is_gimple_call (stmt1)
1324 : 452678 : && gimple_call_internal_p (stmt1))
1325 : 31 : switch (gimple_call_internal_fn (stmt1))
1326 : : {
1327 : 0 : case IFN_UBSAN_NULL:
1328 : 0 : case IFN_UBSAN_BOUNDS:
1329 : 0 : case IFN_UBSAN_VPTR:
1330 : 0 : case IFN_UBSAN_CHECK_ADD:
1331 : 0 : case IFN_UBSAN_CHECK_SUB:
1332 : 0 : case IFN_UBSAN_CHECK_MUL:
1333 : 0 : case IFN_UBSAN_OBJECT_SIZE:
1334 : 0 : case IFN_UBSAN_PTR:
1335 : 0 : case IFN_ASAN_CHECK:
1336 : : /* For these internal functions, gimple_location is an implicit
1337 : : parameter, which will be used explicitly after expansion.
1338 : : Merging these statements may cause confusing line numbers in
1339 : : sanitizer messages. */
1340 : 0 : return gimple_location (stmt1) == gimple_location (stmt2);
1341 : : default:
1342 : : break;
1343 : : }
1344 : :
1345 : : return true;
1346 : : }
1347 : :
1348 : : /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1349 : : clusters them. */
1350 : :
1351 : : static void
1352 : 1258554 : find_duplicate (same_succ *same_succ, basic_block bb1, basic_block bb2)
1353 : : {
1354 : 1258554 : gimple_stmt_iterator gsi1 = gsi_last_nondebug_bb (bb1);
1355 : 1258554 : gimple_stmt_iterator gsi2 = gsi_last_nondebug_bb (bb2);
1356 : 1258554 : tree vuse1 = NULL_TREE, vuse2 = NULL_TREE;
1357 : 1258554 : bool vuse_escaped = false;
1358 : :
1359 : 1258554 : gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
1360 : 1258554 : gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
1361 : :
1362 : 2969786 : while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2))
1363 : : {
1364 : 535378 : gimple *stmt1 = gsi_stmt (gsi1);
1365 : 535378 : gimple *stmt2 = gsi_stmt (gsi2);
1366 : :
1367 : 535378 : if (gimple_code (stmt1) == GIMPLE_LABEL
1368 : 535378 : && gimple_code (stmt2) == GIMPLE_LABEL)
1369 : : break;
1370 : :
1371 : 522276 : if (!gimple_equal_p (same_succ, stmt1, stmt2))
1372 : 77316 : return;
1373 : :
1374 : 460177 : if (!merge_stmts_p (stmt1, stmt2))
1375 : : return;
1376 : :
1377 : 452678 : gsi_prev_nondebug (&gsi1);
1378 : 452678 : gsi_prev_nondebug (&gsi2);
1379 : 452678 : gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
1380 : 452678 : gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
1381 : : }
1382 : :
1383 : 13103 : while (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
1384 : : {
1385 : 13103 : tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1)));
1386 : 26206 : if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
1387 : : return;
1388 : 1215114 : gsi_prev (&gsi1);
1389 : : }
1390 : 13079 : while (!gsi_end_p (gsi2) && gimple_code (gsi_stmt (gsi2)) == GIMPLE_LABEL)
1391 : : {
1392 : 13079 : tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi2)));
1393 : 26158 : if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
1394 : : return;
1395 : 1215090 : gsi_prev (&gsi2);
1396 : : }
1397 : 1188932 : if (!(gsi_end_p (gsi1) && gsi_end_p (gsi2)))
1398 : 0 : return;
1399 : :
1400 : : /* If the incoming vuses are not the same, and the vuse escaped into an
1401 : : SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
1402 : : which potentially means the semantics of one of the blocks will be changed.
1403 : : TODO: make this check more precise. */
1404 : 1188932 : if (vuse_escaped && vuse1 != vuse2)
1405 : : return;
1406 : :
1407 : 1181238 : if (dump_file)
1408 : 26 : fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1409 : : bb1->index, bb2->index);
1410 : :
1411 : 1181238 : set_cluster (bb1, bb2);
1412 : : }
1413 : :
1414 : : /* Returns whether for all phis in DEST the phi alternatives for E1 and
1415 : : E2 are equal. */
1416 : :
1417 : : static bool
1418 : 2042889 : same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
1419 : : {
1420 : 2042889 : int n1 = e1->dest_idx, n2 = e2->dest_idx;
1421 : 2042889 : gphi_iterator gsi;
1422 : :
1423 : 2795428 : for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
1424 : : {
1425 : 1878473 : gphi *phi = gsi.phi ();
1426 : 1878473 : tree lhs = gimple_phi_result (phi);
1427 : 1878473 : tree val1 = gimple_phi_arg_def (phi, n1);
1428 : 1878473 : tree val2 = gimple_phi_arg_def (phi, n2);
1429 : :
1430 : 3756946 : if (virtual_operand_p (lhs))
1431 : 536957 : continue;
1432 : :
1433 : 1341516 : if (operand_equal_for_phi_arg_p (val1, val2))
1434 : 203562 : continue;
1435 : 1137954 : if (gvn_uses_equal (val1, val2))
1436 : 12020 : continue;
1437 : :
1438 : : return false;
1439 : : }
1440 : :
1441 : : return true;
1442 : : }
1443 : :
1444 : : /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1445 : : phi alternatives for BB1 and BB2 are equal. */
1446 : :
1447 : : static bool
1448 : 2384488 : same_phi_alternatives (same_succ *same_succ, basic_block bb1, basic_block bb2)
1449 : : {
1450 : 2384488 : unsigned int s;
1451 : 2384488 : bitmap_iterator bs;
1452 : 2384488 : edge e1, e2;
1453 : 2384488 : basic_block succ;
1454 : :
1455 : 3301443 : EXECUTE_IF_SET_IN_BITMAP (same_succ->succs, 0, s, bs)
1456 : : {
1457 : 2042889 : succ = BASIC_BLOCK_FOR_FN (cfun, s);
1458 : 2042889 : e1 = find_edge (bb1, succ);
1459 : 2042889 : e2 = find_edge (bb2, succ);
1460 : 2042889 : if (e1->flags & EDGE_COMPLEX
1461 : 2042889 : || e2->flags & EDGE_COMPLEX)
1462 : : return false;
1463 : :
1464 : : /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1465 : : the same value. */
1466 : 2042889 : if (!same_phi_alternatives_1 (succ, e1, e2))
1467 : : return false;
1468 : : }
1469 : :
1470 : : return true;
1471 : : }
1472 : :
1473 : : /* Return true if BB has non-vop phis. */
1474 : :
1475 : : static bool
1476 : 20122671 : bb_has_non_vop_phi (basic_block bb)
1477 : : {
1478 : 20122671 : gimple_seq phis = phi_nodes (bb);
1479 : 20122671 : gimple *phi;
1480 : :
1481 : 20122671 : if (phis == NULL)
1482 : : return false;
1483 : :
1484 : 142702 : if (!gimple_seq_singleton_p (phis))
1485 : : return true;
1486 : :
1487 : 105101 : phi = gimple_seq_first_stmt (phis);
1488 : 210202 : return !virtual_operand_p (gimple_phi_result (phi));
1489 : : }
1490 : :
1491 : : /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1492 : : invariant that uses in FROM are dominates by their defs. */
1493 : :
1494 : : static bool
1495 : 3914738 : deps_ok_for_redirect_from_bb_to_bb (basic_block from, basic_block to)
1496 : : {
1497 : 3914738 : basic_block cd, dep_bb = BB_DEP_BB (to);
1498 : 3914738 : edge_iterator ei;
1499 : 3914738 : edge e;
1500 : :
1501 : 3914738 : if (dep_bb == NULL)
1502 : : return true;
1503 : :
1504 : 1849176 : bitmap from_preds = BITMAP_ALLOC (NULL);
1505 : 3740136 : FOR_EACH_EDGE (e, ei, from->preds)
1506 : 1890960 : bitmap_set_bit (from_preds, e->src->index);
1507 : 1849176 : cd = nearest_common_dominator_for_set (CDI_DOMINATORS, from_preds);
1508 : 1849176 : BITMAP_FREE (from_preds);
1509 : :
1510 : 1849176 : return dominated_by_p (CDI_DOMINATORS, dep_bb, cd);
1511 : : }
1512 : :
1513 : : /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1514 : : replacement bb) and vice versa maintains the invariant that uses in the
1515 : : replacement are dominates by their defs. */
1516 : :
1517 : : static bool
1518 : 3120302 : deps_ok_for_redirect (basic_block &bb1, basic_block &bb2)
1519 : : {
1520 : 3120302 : basic_block b1 = bb1;
1521 : 3120302 : basic_block b2 = bb2;
1522 : 3120302 : if (BB_CLUSTER (b1) != NULL)
1523 : 914808 : b1 = BB_CLUSTER (b1)->rep_bb;
1524 : :
1525 : 3120302 : if (BB_CLUSTER (b2) != NULL)
1526 : 89693 : b2 = BB_CLUSTER (b2)->rep_bb;
1527 : :
1528 : 3120302 : if (deps_ok_for_redirect_from_bb_to_bb (b1, b2))
1529 : : return true;
1530 : 794436 : if (deps_ok_for_redirect_from_bb_to_bb (b2, b1))
1531 : : {
1532 : 58622 : std::swap (bb1, bb2);
1533 : 58622 : return true;
1534 : : }
1535 : : return false;
1536 : : }
1537 : :
1538 : : /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1539 : :
1540 : : static void
1541 : 1057037 : find_clusters_1 (same_succ *same_succ)
1542 : : {
1543 : 1057037 : basic_block bb1, bb2;
1544 : 1057037 : unsigned int i, j;
1545 : 1057037 : bitmap_iterator bi, bj;
1546 : 1057037 : int nr_comparisons;
1547 : 1057037 : int max_comparisons = param_max_tail_merge_comparisons;
1548 : :
1549 : 4561941 : EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, 0, i, bi)
1550 : : {
1551 : 3504904 : bb1 = BASIC_BLOCK_FOR_FN (cfun, i);
1552 : :
1553 : : /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1554 : : phi-nodes in bb1 and bb2, with the same alternatives for the same
1555 : : preds. */
1556 : 6974617 : if (bb_has_non_vop_phi (bb1) || bb_has_eh_pred (bb1)
1557 : 6306375 : || bb_has_abnormal_pred (bb1))
1558 : 703551 : continue;
1559 : :
1560 : 2801353 : nr_comparisons = 0;
1561 : 19306283 : EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, i + 1, j, bj)
1562 : : {
1563 : 16617767 : bb2 = BASIC_BLOCK_FOR_FN (cfun, j);
1564 : :
1565 : 33215686 : if (bb_has_non_vop_phi (bb2) || bb_has_eh_pred (bb2)
1566 : 33215385 : || bb_has_abnormal_pred (bb2))
1567 : 20149 : continue;
1568 : :
1569 : 16597618 : if (BB_CLUSTER (bb1) != NULL && BB_CLUSTER (bb1) == BB_CLUSTER (bb2))
1570 : 13364479 : continue;
1571 : :
1572 : : /* Limit quadratic behavior. */
1573 : 3233139 : nr_comparisons++;
1574 : 3233139 : if (nr_comparisons > max_comparisons)
1575 : : break;
1576 : :
1577 : : /* This is a conservative dependency check. We could test more
1578 : : precise for allowed replacement direction. */
1579 : 3120302 : if (!deps_ok_for_redirect (bb1, bb2))
1580 : 735814 : continue;
1581 : :
1582 : 2384488 : if (!(same_phi_alternatives (same_succ, bb1, bb2)))
1583 : 1125934 : continue;
1584 : :
1585 : 1258554 : find_duplicate (same_succ, bb1, bb2);
1586 : : }
1587 : : }
1588 : 1057037 : }
1589 : :
1590 : : /* Find clusters of bbs which can be merged. */
1591 : :
1592 : : static void
1593 : 261943 : find_clusters (void)
1594 : : {
1595 : 261943 : same_succ *same;
1596 : :
1597 : 1318980 : while (!worklist.is_empty ())
1598 : : {
1599 : 1057037 : same = worklist.pop ();
1600 : 1057037 : same->in_worklist = false;
1601 : 81 : if (dump_file && (dump_flags & TDF_DETAILS))
1602 : : {
1603 : 10 : fprintf (dump_file, "processing worklist entry\n");
1604 : 10 : same_succ_print (dump_file, same);
1605 : : }
1606 : 1057037 : find_clusters_1 (same);
1607 : : }
1608 : 261943 : }
1609 : :
1610 : : /* Returns the vop phi of BB, if any. */
1611 : :
1612 : : static gphi *
1613 : 1207236 : vop_phi (basic_block bb)
1614 : : {
1615 : 1207236 : gphi *stmt;
1616 : 1207236 : gphi_iterator gsi;
1617 : 1207236 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1618 : : {
1619 : 45184 : stmt = gsi.phi ();
1620 : 90368 : if (! virtual_operand_p (gimple_phi_result (stmt)))
1621 : 0 : continue;
1622 : : return stmt;
1623 : : }
1624 : : return NULL;
1625 : : }
1626 : :
1627 : : /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
1628 : :
1629 : : static void
1630 : 1181238 : replace_block_by (basic_block bb1, basic_block bb2)
1631 : : {
1632 : 1181238 : edge pred_edge;
1633 : 1181238 : unsigned int i;
1634 : 1181238 : gphi *bb2_phi;
1635 : :
1636 : 1181238 : bb2_phi = vop_phi (bb2);
1637 : :
1638 : : /* Mark the basic block as deleted. */
1639 : 1181238 : mark_basic_block_deleted (bb1);
1640 : :
1641 : : /* Redirect the incoming edges of bb1 to bb2. */
1642 : 3666342 : for (i = EDGE_COUNT (bb1->preds); i > 0 ; --i)
1643 : : {
1644 : 1303866 : pred_edge = EDGE_PRED (bb1, i - 1);
1645 : 1303866 : pred_edge = redirect_edge_and_branch (pred_edge, bb2);
1646 : 1303866 : gcc_assert (pred_edge != NULL);
1647 : :
1648 : 1303866 : if (bb2_phi == NULL)
1649 : 1277868 : continue;
1650 : :
1651 : : /* The phi might have run out of capacity when the redirect added an
1652 : : argument, which means it could have been replaced. Refresh it. */
1653 : 25998 : bb2_phi = vop_phi (bb2);
1654 : :
1655 : 25998 : add_phi_arg (bb2_phi, SSA_NAME_VAR (gimple_phi_result (bb2_phi)),
1656 : : pred_edge, UNKNOWN_LOCATION);
1657 : : }
1658 : :
1659 : :
1660 : : /* Merge the outgoing edge counts from bb1 onto bb2. */
1661 : 1181238 : edge e1, e2;
1662 : 1181238 : edge_iterator ei;
1663 : :
1664 : 1181238 : if (bb2->count.initialized_p ())
1665 : 2034324 : FOR_EACH_EDGE (e1, ei, bb1->succs)
1666 : : {
1667 : 853175 : e2 = find_edge (bb2, e1->dest);
1668 : 853175 : gcc_assert (e2);
1669 : :
1670 : : /* If probabilities are same, we are done.
1671 : : If counts are nonzero we can distribute accordingly. In remaining
1672 : : cases just average the values and hope for the best. */
1673 : 853175 : e2->probability = e1->probability.combine_with_count
1674 : 853175 : (bb1->count, e2->probability, bb2->count);
1675 : : }
1676 : 1181238 : bb2->count += bb1->count;
1677 : :
1678 : : /* Move over any user labels from bb1 after the bb2 labels. */
1679 : 1181238 : gimple_stmt_iterator gsi1 = gsi_start_bb (bb1);
1680 : 1181238 : if (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
1681 : : {
1682 : 13076 : gimple_stmt_iterator gsi2 = gsi_after_labels (bb2);
1683 : 26153 : while (!gsi_end_p (gsi1)
1684 : 26153 : && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
1685 : : {
1686 : 13077 : tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1)));
1687 : 26154 : gcc_assert (!DECL_NONLOCAL (label) && !FORCED_LABEL (label));
1688 : 13077 : if (DECL_ARTIFICIAL (label))
1689 : 12720 : gsi_next (&gsi1);
1690 : : else
1691 : 357 : gsi_move_before (&gsi1, &gsi2);
1692 : : }
1693 : : }
1694 : :
1695 : : /* Clear range info from all stmts in BB2 -- this transformation
1696 : : could make them out of date. */
1697 : 1181238 : reset_flow_sensitive_info_in_bb (bb2);
1698 : :
1699 : : /* Do updates that use bb1, before deleting bb1. */
1700 : 1181238 : release_last_vdef (bb1);
1701 : 1181238 : same_succ_flush_bb (bb1);
1702 : :
1703 : 1181238 : delete_basic_block (bb1);
1704 : 1181238 : }
1705 : :
1706 : : /* Bbs for which update_debug_stmt need to be called. */
1707 : :
1708 : : static bitmap update_bbs;
1709 : :
1710 : : /* For each cluster in all_clusters, merge all cluster->bbs. Returns
1711 : : number of bbs removed. */
1712 : :
1713 : : static int
1714 : 201651 : apply_clusters (void)
1715 : : {
1716 : 201651 : basic_block bb1, bb2;
1717 : 201651 : bb_cluster *c;
1718 : 201651 : unsigned int i, j;
1719 : 201651 : bitmap_iterator bj;
1720 : 201651 : int nr_bbs_removed = 0;
1721 : :
1722 : 773752 : for (i = 0; i < all_clusters.length (); ++i)
1723 : : {
1724 : 572101 : c = all_clusters[i];
1725 : 572101 : if (c == NULL)
1726 : 0 : continue;
1727 : :
1728 : 572101 : bb2 = c->rep_bb;
1729 : 572101 : bitmap_set_bit (update_bbs, bb2->index);
1730 : :
1731 : 572101 : bitmap_clear_bit (c->bbs, bb2->index);
1732 : 1753339 : EXECUTE_IF_SET_IN_BITMAP (c->bbs, 0, j, bj)
1733 : : {
1734 : 1181238 : bb1 = BASIC_BLOCK_FOR_FN (cfun, j);
1735 : 1181238 : bitmap_clear_bit (update_bbs, bb1->index);
1736 : :
1737 : 1181238 : replace_block_by (bb1, bb2);
1738 : 1181238 : nr_bbs_removed++;
1739 : : }
1740 : : }
1741 : :
1742 : 201651 : return nr_bbs_removed;
1743 : : }
1744 : :
1745 : : /* Resets debug statement STMT if it has uses that are not dominated by their
1746 : : defs. */
1747 : :
1748 : : static void
1749 : 184970 : update_debug_stmt (gimple *stmt)
1750 : : {
1751 : 184970 : use_operand_p use_p;
1752 : 184970 : ssa_op_iter oi;
1753 : 184970 : basic_block bbuse;
1754 : :
1755 : 184970 : if (!gimple_debug_bind_p (stmt))
1756 : 29429 : return;
1757 : :
1758 : 155541 : bbuse = gimple_bb (stmt);
1759 : 160136 : FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
1760 : : {
1761 : 5568 : tree name = USE_FROM_PTR (use_p);
1762 : 5568 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1763 : 5568 : basic_block bbdef = gimple_bb (def_stmt);
1764 : 10163 : if (bbdef == NULL || bbuse == bbdef
1765 : 5568 : || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef))
1766 : 4595 : continue;
1767 : :
1768 : 973 : gimple_debug_bind_reset_value (stmt);
1769 : 973 : update_stmt (stmt);
1770 : 973 : break;
1771 : : }
1772 : : }
1773 : :
1774 : : /* Resets all debug statements that have uses that are not
1775 : : dominated by their defs. */
1776 : :
1777 : : static void
1778 : 131788 : update_debug_stmts (void)
1779 : : {
1780 : 131788 : basic_block bb;
1781 : 131788 : bitmap_iterator bi;
1782 : 131788 : unsigned int i;
1783 : :
1784 : 537090 : EXECUTE_IF_SET_IN_BITMAP (update_bbs, 0, i, bi)
1785 : : {
1786 : 405302 : gimple *stmt;
1787 : 405302 : gimple_stmt_iterator gsi;
1788 : :
1789 : 405302 : bb = BASIC_BLOCK_FOR_FN (cfun, i);
1790 : 1068687 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1791 : : {
1792 : 258083 : stmt = gsi_stmt (gsi);
1793 : 258083 : if (!is_gimple_debug (stmt))
1794 : 73113 : continue;
1795 : 184970 : update_debug_stmt (stmt);
1796 : : }
1797 : : }
1798 : 131788 : }
1799 : :
1800 : : /* Runs tail merge optimization. */
1801 : :
1802 : : unsigned int
1803 : 927955 : tail_merge_optimize (bool need_crit_edge_split)
1804 : : {
1805 : 927955 : int nr_bbs_removed_total = 0;
1806 : 927955 : int nr_bbs_removed;
1807 : 927955 : bool loop_entered = false;
1808 : 927955 : int iteration_nr = 0;
1809 : 927955 : int max_iterations = param_max_tail_merge_iterations;
1810 : :
1811 : 927955 : if (!flag_tree_tail_merge
1812 : 927912 : || max_iterations == 0)
1813 : : return 0;
1814 : :
1815 : 927912 : timevar_push (TV_TREE_TAIL_MERGE);
1816 : :
1817 : : /* Re-split critical edges when PRE did a CFG cleanup. */
1818 : 927912 : if (need_crit_edge_split)
1819 : 132155 : split_edges_for_insertion ();
1820 : :
1821 : 927912 : if (!dom_info_available_p (CDI_DOMINATORS))
1822 : : {
1823 : : /* PRE can leave us with unreachable blocks, remove them now. */
1824 : 0 : delete_unreachable_blocks ();
1825 : 0 : calculate_dominance_info (CDI_DOMINATORS);
1826 : : }
1827 : 927912 : init_worklist ();
1828 : :
1829 : 2050713 : while (!worklist.is_empty ())
1830 : : {
1831 : 261943 : if (!loop_entered)
1832 : : {
1833 : 250261 : loop_entered = true;
1834 : 250261 : alloc_cluster_vectors ();
1835 : 250261 : update_bbs = BITMAP_ALLOC (NULL);
1836 : : }
1837 : : else
1838 : 11682 : reset_cluster_vectors ();
1839 : :
1840 : 261943 : iteration_nr++;
1841 : 261943 : if (dump_file && (dump_flags & TDF_DETAILS))
1842 : 9 : fprintf (dump_file, "worklist iteration #%d\n", iteration_nr);
1843 : :
1844 : 261943 : find_clusters ();
1845 : 261943 : gcc_assert (worklist.is_empty ());
1846 : 261943 : if (all_clusters.is_empty ())
1847 : : break;
1848 : :
1849 : 201651 : nr_bbs_removed = apply_clusters ();
1850 : 201651 : nr_bbs_removed_total += nr_bbs_removed;
1851 : 201651 : if (nr_bbs_removed == 0)
1852 : : break;
1853 : :
1854 : 201651 : free_dominance_info (CDI_DOMINATORS);
1855 : :
1856 : 201651 : if (iteration_nr == max_iterations)
1857 : : break;
1858 : :
1859 : 194889 : calculate_dominance_info (CDI_DOMINATORS);
1860 : 194889 : update_worklist ();
1861 : : }
1862 : :
1863 : 927912 : if (dump_file && (dump_flags & TDF_DETAILS))
1864 : 28 : fprintf (dump_file, "htab collision / search: %f\n",
1865 : : same_succ_htab->collisions ());
1866 : :
1867 : 927912 : if (nr_bbs_removed_total > 0)
1868 : : {
1869 : 194889 : if (MAY_HAVE_DEBUG_BIND_STMTS)
1870 : : {
1871 : 131788 : calculate_dominance_info (CDI_DOMINATORS);
1872 : 131788 : update_debug_stmts ();
1873 : : }
1874 : :
1875 : 194889 : if (dump_file && (dump_flags & TDF_DETAILS))
1876 : : {
1877 : 2 : fprintf (dump_file, "Before TODOs.\n");
1878 : 2 : dump_function_to_file (current_function_decl, dump_file, dump_flags);
1879 : : }
1880 : :
1881 : 194889 : mark_virtual_operands_for_renaming (cfun);
1882 : : }
1883 : :
1884 : 927912 : delete_worklist ();
1885 : 927912 : if (loop_entered)
1886 : : {
1887 : 250261 : delete_cluster_vectors ();
1888 : 250261 : BITMAP_FREE (update_bbs);
1889 : : }
1890 : :
1891 : 927912 : timevar_pop (TV_TREE_TAIL_MERGE);
1892 : :
1893 : 927912 : return 0;
1894 : : }
|
