Branch data Line data Source code
1 : : /* Tail merging for gimple.
2 : : Copyright (C) 2011-2024 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 : 37862321 : same_succ::hash (const same_succ *e)
244 : : {
245 : 37862321 : 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 : 11949997 : tail_merge_valueize (tree name)
292 : : {
293 : 11949997 : if (TREE_CODE (name) == SSA_NAME
294 : 11949997 : && has_VN_INFO (name))
295 : : {
296 : 4275141 : tree tem = VN_INFO (name)->valnum;
297 : 4275141 : 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 : 35649233 : stmt_local_def (gimple *stmt)
308 : : {
309 : 35649233 : basic_block bb, def_bb;
310 : 35649233 : imm_use_iterator iter;
311 : 35649233 : use_operand_p use_p;
312 : 35649233 : tree val;
313 : 35649233 : def_operand_p def_p;
314 : :
315 : 35649233 : if (gimple_vdef (stmt) != NULL_TREE
316 : 22557633 : || gimple_has_side_effects (stmt)
317 : 21859360 : || gimple_could_trap_p_1 (stmt, false, false)
318 : 21123498 : || 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 : 43284737 : || is_gimple_call (stmt))
327 : 21402484 : return false;
328 : :
329 : 14246749 : def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
330 : 14246749 : if (def_p == NULL)
331 : : return false;
332 : :
333 : 7407324 : val = DEF_FROM_PTR (def_p);
334 : 7407324 : if (val == NULL_TREE || TREE_CODE (val) != SSA_NAME)
335 : : return false;
336 : :
337 : 7407324 : def_bb = gimple_bb (stmt);
338 : :
339 : 15556382 : FOR_EACH_IMM_USE_FAST (use_p, iter, val)
340 : : {
341 : 9393348 : if (is_gimple_debug (USE_STMT (use_p)))
342 : 1072383 : continue;
343 : 8320965 : bb = gimple_bb (USE_STMT (use_p));
344 : 8320965 : if (bb == def_bb)
345 : 6420875 : continue;
346 : :
347 : 2555890 : if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI
348 : 1900090 : && EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src == def_bb)
349 : 655800 : continue;
350 : :
351 : : return false;
352 : : }
353 : :
354 : : return true;
355 : : }
356 : :
357 : : /* Let GSI skip forwards over local defs. */
358 : :
359 : : static void
360 : 6814544 : gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator *gsi)
361 : : {
362 : 7273122 : gimple *stmt;
363 : :
364 : 7731700 : while (true)
365 : : {
366 : 7273122 : if (gsi_end_p (*gsi))
367 : : return;
368 : 2748212 : stmt = gsi_stmt (*gsi);
369 : 2748212 : if (!stmt_local_def (stmt))
370 : : return;
371 : 458578 : gsi_next_nondebug (gsi);
372 : : }
373 : : }
374 : :
375 : : /* VAL1 and VAL2 are either:
376 : : - uses in BB1 and BB2, or
377 : : - phi alternatives for BB1 and BB2.
378 : : Return true if the uses have the same gvn value. */
379 : :
380 : : static bool
381 : 918374 : gvn_uses_equal (tree val1, tree val2)
382 : : {
383 : 918374 : gcc_checking_assert (val1 != NULL_TREE && val2 != NULL_TREE);
384 : :
385 : 918374 : if (val1 == val2)
386 : : return true;
387 : :
388 : 918374 : if (tail_merge_valueize (val1) != tail_merge_valueize (val2))
389 : : return false;
390 : :
391 : 0 : return ((TREE_CODE (val1) == SSA_NAME || CONSTANT_CLASS_P (val1))
392 : 25872 : && (TREE_CODE (val2) == SSA_NAME || CONSTANT_CLASS_P (val2)));
393 : : }
394 : :
395 : : /* Prints E to FILE. */
396 : :
397 : : static void
398 : 22 : same_succ_print (FILE *file, const same_succ *e)
399 : : {
400 : 22 : unsigned int i;
401 : 22 : bitmap_print (file, e->bbs, "bbs:", "\n");
402 : 22 : bitmap_print (file, e->succs, "succs:", "\n");
403 : 22 : bitmap_print (file, e->inverse, "inverse:", "\n");
404 : 22 : fprintf (file, "flags:");
405 : 110 : for (i = 0; i < e->succ_flags.length (); ++i)
406 : 22 : fprintf (file, " %x", e->succ_flags[i]);
407 : 22 : fprintf (file, "\n");
408 : 22 : }
409 : :
410 : : /* Prints same_succ VE to VFILE. */
411 : :
412 : : inline int
413 : 0 : ssa_same_succ_print_traverse (same_succ **pe, FILE *file)
414 : : {
415 : 0 : const same_succ *e = *pe;
416 : 0 : same_succ_print (file, e);
417 : 0 : return 1;
418 : : }
419 : :
420 : : /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */
421 : :
422 : : static void
423 : 32272007 : update_dep_bb (basic_block use_bb, tree val)
424 : : {
425 : 32272007 : basic_block dep_bb;
426 : :
427 : : /* Not a dep. */
428 : 32272007 : if (TREE_CODE (val) != SSA_NAME)
429 : : return;
430 : :
431 : : /* Skip use of global def. */
432 : 30884591 : if (SSA_NAME_IS_DEFAULT_DEF (val))
433 : : return;
434 : :
435 : : /* Skip use of local def. */
436 : 26816785 : dep_bb = gimple_bb (SSA_NAME_DEF_STMT (val));
437 : 26816785 : if (dep_bb == use_bb)
438 : : return;
439 : :
440 : 9800844 : if (BB_DEP_BB (use_bb) == NULL
441 : 9800844 : || dominated_by_p (CDI_DOMINATORS, dep_bb, BB_DEP_BB (use_bb)))
442 : 8385127 : BB_DEP_BB (use_bb) = dep_bb;
443 : : }
444 : :
445 : : /* Update BB_DEP_BB, given the dependencies in STMT. */
446 : :
447 : : static void
448 : 32053252 : stmt_update_dep_bb (gimple *stmt)
449 : : {
450 : 32053252 : ssa_op_iter iter;
451 : 32053252 : use_operand_p use;
452 : :
453 : 59158254 : FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
454 : 27105002 : update_dep_bb (gimple_bb (stmt), USE_FROM_PTR (use));
455 : 32053252 : }
456 : :
457 : : /* Calculates hash value for same_succ VE. */
458 : :
459 : : static hashval_t
460 : 12645745 : same_succ_hash (const same_succ *e)
461 : : {
462 : 12645745 : inchash::hash hstate (bitmap_hash (e->succs));
463 : 12645745 : int flags;
464 : 12645745 : unsigned int i;
465 : 12645745 : unsigned int first = bitmap_first_set_bit (e->bbs);
466 : 12645745 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, first);
467 : 12645745 : int size = 0;
468 : 12645745 : gimple *stmt;
469 : 12645745 : tree arg;
470 : 12645745 : unsigned int s;
471 : 12645745 : bitmap_iterator bs;
472 : :
473 : 12645745 : for (gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
474 : 44698997 : !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
475 : : {
476 : 32053252 : stmt = gsi_stmt (gsi);
477 : 32053252 : if (is_gimple_debug (stmt))
478 : 0 : continue;
479 : :
480 : 32053252 : stmt_update_dep_bb (stmt);
481 : 32053252 : if (stmt_local_def (stmt))
482 : 5699189 : continue;
483 : 26354063 : size++;
484 : :
485 : 26354063 : hstate.add_int (gimple_code (stmt));
486 : 26354063 : if (is_gimple_assign (stmt))
487 : 14697539 : hstate.add_int (gimple_assign_rhs_code (stmt));
488 : 26354063 : if (!is_gimple_call (stmt))
489 : 21272667 : continue;
490 : 5081396 : if (gimple_call_internal_p (stmt))
491 : 84714 : hstate.add_int (gimple_call_internal_fn (stmt));
492 : : else
493 : : {
494 : 4996682 : inchash::add_expr (gimple_call_fn (stmt), hstate);
495 : 4996682 : if (gimple_call_chain (stmt))
496 : 30130 : inchash::add_expr (gimple_call_chain (stmt), hstate);
497 : : }
498 : 15187281 : for (i = 0; i < gimple_call_num_args (stmt); i++)
499 : : {
500 : 10105885 : arg = gimple_call_arg (stmt, i);
501 : 10105885 : arg = tail_merge_valueize (arg);
502 : 10105885 : inchash::add_expr (arg, hstate);
503 : : }
504 : : }
505 : :
506 : 12645745 : hstate.add_int (size);
507 : 12645745 : BB_SIZE (bb) = size;
508 : :
509 : 12645745 : hstate.add_int (bb->loop_father->num);
510 : :
511 : 59552196 : for (i = 0; i < e->succ_flags.length (); ++i)
512 : : {
513 : 17130353 : flags = e->succ_flags[i];
514 : 17130353 : flags = flags & ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
515 : 17130353 : hstate.add_int (flags);
516 : : }
517 : :
518 : 29776098 : EXECUTE_IF_SET_IN_BITMAP (e->succs, 0, s, bs)
519 : : {
520 : 17130353 : int n = find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, s))->dest_idx;
521 : 17130353 : for (gphi_iterator gsi = gsi_start_phis (BASIC_BLOCK_FOR_FN (cfun, s));
522 : 26433747 : !gsi_end_p (gsi);
523 : 9303394 : gsi_next (&gsi))
524 : : {
525 : 9303394 : gphi *phi = gsi.phi ();
526 : 9303394 : tree lhs = gimple_phi_result (phi);
527 : 9303394 : tree val = gimple_phi_arg_def (phi, n);
528 : :
529 : 18606788 : if (virtual_operand_p (lhs))
530 : 4136389 : continue;
531 : 5167005 : update_dep_bb (bb, val);
532 : : }
533 : : }
534 : :
535 : 12645745 : return hstate.end ();
536 : : }
537 : :
538 : : /* Returns true if E1 and E2 have 2 successors, and if the successor flags
539 : : are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
540 : : the other edge flags. */
541 : :
542 : : static bool
543 : 4524968 : inverse_flags (const same_succ *e1, const same_succ *e2)
544 : : {
545 : 4524968 : int f1a, f1b, f2a, f2b;
546 : 4524968 : int mask = ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
547 : :
548 : 4537014 : if (e1->succ_flags.length () != 2)
549 : : return false;
550 : :
551 : 13522 : f1a = e1->succ_flags[0];
552 : 13522 : f1b = e1->succ_flags[1];
553 : 13522 : f2a = e2->succ_flags[0];
554 : 13522 : f2b = e2->succ_flags[1];
555 : :
556 : 13522 : if (f1a == f2a && f1b == f2b)
557 : : return false;
558 : :
559 : 1476 : return (f1a & mask) == (f2a & mask) && (f1b & mask) == (f2b & mask);
560 : : }
561 : :
562 : : /* Compares SAME_SUCCs E1 and E2. */
563 : :
564 : : int
565 : 45342124 : same_succ::equal (const same_succ *e1, const same_succ *e2)
566 : : {
567 : 45342124 : unsigned int i, first1, first2;
568 : 45342124 : gimple_stmt_iterator gsi1, gsi2;
569 : 45342124 : gimple *s1, *s2;
570 : 45342124 : basic_block bb1, bb2;
571 : :
572 : 45342124 : if (e1 == e2)
573 : : return 1;
574 : :
575 : 44393560 : if (e1->hashval != e2->hashval)
576 : : return 0;
577 : :
578 : 7115634 : if (e1->succ_flags.length () != e2->succ_flags.length ())
579 : : return 0;
580 : :
581 : 2371878 : if (!bitmap_equal_p (e1->succs, e2->succs))
582 : : return 0;
583 : :
584 : 2262513 : if (!inverse_flags (e1, e2))
585 : : {
586 : 8575242 : for (i = 0; i < e1->succ_flags.length (); ++i)
587 : 2025846 : if (e1->succ_flags[i] != e2->succ_flags[i])
588 : : return 0;
589 : : }
590 : :
591 : 2262513 : first1 = bitmap_first_set_bit (e1->bbs);
592 : 2262513 : first2 = bitmap_first_set_bit (e2->bbs);
593 : :
594 : 2262513 : bb1 = BASIC_BLOCK_FOR_FN (cfun, first1);
595 : 2262513 : bb2 = BASIC_BLOCK_FOR_FN (cfun, first2);
596 : :
597 : 2262513 : if (BB_SIZE (bb1) != BB_SIZE (bb2))
598 : : return 0;
599 : :
600 : 2262513 : if (bb1->loop_father != bb2->loop_father)
601 : : return 0;
602 : :
603 : 2262513 : gsi1 = gsi_start_nondebug_bb (bb1);
604 : 2262513 : gsi2 = gsi_start_nondebug_bb (bb2);
605 : 2262513 : gsi_advance_fw_nondebug_nonlocal (&gsi1);
606 : 2262513 : gsi_advance_fw_nondebug_nonlocal (&gsi2);
607 : 5669785 : while (!(gsi_end_p (gsi1) || gsi_end_p (gsi2)))
608 : : {
609 : 1144817 : s1 = gsi_stmt (gsi1);
610 : 1144817 : s2 = gsi_stmt (gsi2);
611 : 1144817 : if (gimple_code (s1) != gimple_code (s2))
612 : : return 0;
613 : 1144817 : if (is_gimple_call (s1) && !gimple_call_same_target_p (s1, s2))
614 : : return 0;
615 : 1144759 : gsi_next_nondebug (&gsi1);
616 : 1144759 : gsi_next_nondebug (&gsi2);
617 : 1144759 : gsi_advance_fw_nondebug_nonlocal (&gsi1);
618 : 1144759 : gsi_advance_fw_nondebug_nonlocal (&gsi2);
619 : : }
620 : :
621 : : return 1;
622 : : }
623 : :
624 : : /* Alloc and init a new SAME_SUCC. */
625 : :
626 : : static same_succ *
627 : 11473509 : same_succ_alloc (void)
628 : : {
629 : 11473509 : same_succ *same = XNEW (struct same_succ);
630 : :
631 : 11473509 : same->bbs = BITMAP_ALLOC (NULL);
632 : 11473509 : same->succs = BITMAP_ALLOC (NULL);
633 : 11473509 : same->inverse = BITMAP_ALLOC (NULL);
634 : 11473509 : same->succ_flags.create (10);
635 : 11473509 : same->in_worklist = false;
636 : :
637 : 11473509 : return same;
638 : : }
639 : :
640 : : /* Delete same_succ E. */
641 : :
642 : : void
643 : 11473509 : same_succ::remove (same_succ *e)
644 : : {
645 : 11473509 : BITMAP_FREE (e->bbs);
646 : 11473509 : BITMAP_FREE (e->succs);
647 : 11473509 : BITMAP_FREE (e->inverse);
648 : 11473509 : e->succ_flags.release ();
649 : :
650 : 11473509 : XDELETE (e);
651 : 11473509 : }
652 : :
653 : : /* Reset same_succ SAME. */
654 : :
655 : : static void
656 : 2262455 : same_succ_reset (same_succ *same)
657 : : {
658 : 2262455 : bitmap_clear (same->bbs);
659 : 2262455 : bitmap_clear (same->succs);
660 : 2262455 : bitmap_clear (same->inverse);
661 : 2262455 : same->succ_flags.truncate (0);
662 : 2262455 : }
663 : :
664 : : static hash_table<same_succ> *same_succ_htab;
665 : :
666 : : /* Array that is used to store the edge flags for a successor. */
667 : :
668 : : static int *same_succ_edge_flags;
669 : :
670 : : /* Bitmap that is used to mark bbs that are recently deleted. */
671 : :
672 : : static bitmap deleted_bbs;
673 : :
674 : : /* Bitmap that is used to mark predecessors of bbs that are
675 : : deleted. */
676 : :
677 : : static bitmap deleted_bb_preds;
678 : :
679 : : /* Prints same_succ_htab to stderr. */
680 : :
681 : : extern void debug_same_succ (void);
682 : : DEBUG_FUNCTION void
683 : 0 : debug_same_succ ( void)
684 : : {
685 : 0 : same_succ_htab->traverse <FILE *, ssa_same_succ_print_traverse> (stderr);
686 : 0 : }
687 : :
688 : :
689 : : /* Vector of bbs to process. */
690 : :
691 : : static vec<same_succ *> worklist;
692 : :
693 : : /* Prints worklist to FILE. */
694 : :
695 : : static void
696 : 16 : print_worklist (FILE *file)
697 : : {
698 : 16 : unsigned int i;
699 : 54 : for (i = 0; i < worklist.length (); ++i)
700 : 11 : same_succ_print (file, worklist[i]);
701 : 16 : }
702 : :
703 : : /* Adds SAME to worklist. */
704 : :
705 : : static void
706 : 12645745 : add_to_worklist (same_succ *same)
707 : : {
708 : 12645745 : if (same->in_worklist)
709 : : return;
710 : :
711 : 11365262 : if (bitmap_count_bits (same->bbs) < 2)
712 : : return;
713 : :
714 : 981972 : same->in_worklist = true;
715 : 981972 : worklist.safe_push (same);
716 : : }
717 : :
718 : : /* Add BB to same_succ_htab. */
719 : :
720 : : static void
721 : 12645745 : find_same_succ_bb (basic_block bb, same_succ **same_p)
722 : : {
723 : 12645745 : unsigned int j;
724 : 12645745 : bitmap_iterator bj;
725 : 12645745 : same_succ *same = *same_p;
726 : 12645745 : same_succ **slot;
727 : 12645745 : edge_iterator ei;
728 : 12645745 : edge e;
729 : :
730 : 12645745 : if (bb == NULL)
731 : 0 : return;
732 : 12645745 : bitmap_set_bit (same->bbs, bb->index);
733 : 29776098 : FOR_EACH_EDGE (e, ei, bb->succs)
734 : : {
735 : 17130353 : int index = e->dest->index;
736 : 17130353 : bitmap_set_bit (same->succs, index);
737 : 17130353 : same_succ_edge_flags[index] = (e->flags & ~ignore_edge_flags);
738 : : }
739 : 29776098 : EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
740 : 17130353 : same->succ_flags.safe_push (same_succ_edge_flags[j]);
741 : :
742 : 12645745 : same->hashval = same_succ_hash (same);
743 : :
744 : 12645745 : slot = same_succ_htab->find_slot_with_hash (same, same->hashval, INSERT);
745 : 12645745 : if (*slot == NULL)
746 : : {
747 : 10383290 : *slot = same;
748 : 10383290 : BB_SAME_SUCC (bb) = same;
749 : 10383290 : add_to_worklist (same);
750 : 10383290 : *same_p = NULL;
751 : : }
752 : : else
753 : : {
754 : 2262455 : bitmap_set_bit ((*slot)->bbs, bb->index);
755 : 2262455 : BB_SAME_SUCC (bb) = *slot;
756 : 2262455 : add_to_worklist (*slot);
757 : 2262455 : if (inverse_flags (same, *slot))
758 : 738 : bitmap_set_bit ((*slot)->inverse, bb->index);
759 : 2262455 : same_succ_reset (same);
760 : : }
761 : : }
762 : :
763 : : /* Find bbs with same successors. */
764 : :
765 : : static void
766 : 904945 : find_same_succ (void)
767 : : {
768 : 904945 : same_succ *same = same_succ_alloc ();
769 : 904945 : basic_block bb;
770 : :
771 : 12598792 : FOR_EACH_BB_FN (bb, cfun)
772 : : {
773 : 11693847 : find_same_succ_bb (bb, &same);
774 : 11693847 : if (same == NULL)
775 : 9482087 : same = same_succ_alloc ();
776 : : }
777 : :
778 : 904945 : same_succ::remove (same);
779 : 904945 : }
780 : :
781 : : /* Initializes worklist administration. */
782 : :
783 : : static void
784 : 904945 : init_worklist (void)
785 : : {
786 : 904945 : alloc_aux_for_blocks (sizeof (struct aux_bb_info));
787 : 904945 : same_succ_htab = new hash_table<same_succ> (n_basic_blocks_for_fn (cfun));
788 : 904945 : same_succ_edge_flags = XCNEWVEC (int, last_basic_block_for_fn (cfun));
789 : 904945 : deleted_bbs = BITMAP_ALLOC (NULL);
790 : 904945 : deleted_bb_preds = BITMAP_ALLOC (NULL);
791 : 904945 : worklist.create (n_basic_blocks_for_fn (cfun));
792 : 904945 : find_same_succ ();
793 : :
794 : 904945 : if (dump_file && (dump_flags & TDF_DETAILS))
795 : : {
796 : 16 : fprintf (dump_file, "initial worklist:\n");
797 : 16 : print_worklist (dump_file);
798 : : }
799 : 904945 : }
800 : :
801 : : /* Deletes worklist administration. */
802 : :
803 : : static void
804 : 904945 : delete_worklist (void)
805 : : {
806 : 904945 : free_aux_for_blocks ();
807 : 904945 : delete same_succ_htab;
808 : 904945 : same_succ_htab = NULL;
809 : 904945 : XDELETEVEC (same_succ_edge_flags);
810 : 904945 : same_succ_edge_flags = NULL;
811 : 904945 : BITMAP_FREE (deleted_bbs);
812 : 904945 : BITMAP_FREE (deleted_bb_preds);
813 : 904945 : worklist.release ();
814 : 904945 : }
815 : :
816 : : /* Mark BB as deleted, and mark its predecessors. */
817 : :
818 : : static void
819 : 1044253 : mark_basic_block_deleted (basic_block bb)
820 : : {
821 : 1044253 : edge e;
822 : 1044253 : edge_iterator ei;
823 : :
824 : 1044253 : bitmap_set_bit (deleted_bbs, bb->index);
825 : :
826 : 2207987 : FOR_EACH_EDGE (e, ei, bb->preds)
827 : 1163734 : bitmap_set_bit (deleted_bb_preds, e->src->index);
828 : 1044253 : }
829 : :
830 : : /* Removes BB from its corresponding same_succ. */
831 : :
832 : : static void
833 : 1996151 : same_succ_flush_bb (basic_block bb)
834 : : {
835 : 1996151 : same_succ *same = BB_SAME_SUCC (bb);
836 : 1996151 : if (! same)
837 : 0 : return;
838 : :
839 : 1996151 : BB_SAME_SUCC (bb) = NULL;
840 : 1996151 : if (bitmap_single_bit_set_p (same->bbs))
841 : 948564 : same_succ_htab->remove_elt_with_hash (same, same->hashval);
842 : : else
843 : 1047587 : bitmap_clear_bit (same->bbs, bb->index);
844 : : }
845 : :
846 : : /* Removes all bbs in BBS from their corresponding same_succ. */
847 : :
848 : : static void
849 : 185274 : same_succ_flush_bbs (bitmap bbs)
850 : : {
851 : 185274 : unsigned int i;
852 : 185274 : bitmap_iterator bi;
853 : :
854 : 1137172 : EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
855 : 951898 : same_succ_flush_bb (BASIC_BLOCK_FOR_FN (cfun, i));
856 : 185274 : }
857 : :
858 : : /* Release the last vdef in BB, either normal or phi result. */
859 : :
860 : : static void
861 : 1044253 : release_last_vdef (basic_block bb)
862 : : {
863 : 2153614 : for (gimple_stmt_iterator i = gsi_last_bb (bb); !gsi_end_p (i);
864 : 65108 : gsi_prev_nondebug (&i))
865 : : {
866 : 288855 : gimple *stmt = gsi_stmt (i);
867 : 563963 : if (gimple_vdef (stmt) == NULL_TREE)
868 : 65108 : continue;
869 : :
870 : 223747 : mark_virtual_operand_for_renaming (gimple_vdef (stmt));
871 : 223747 : return;
872 : : }
873 : :
874 : 820506 : for (gphi_iterator i = gsi_start_phis (bb); !gsi_end_p (i);
875 : 0 : gsi_next (&i))
876 : : {
877 : 578 : gphi *phi = i.phi ();
878 : 578 : tree res = gimple_phi_result (phi);
879 : :
880 : 1156 : if (!virtual_operand_p (res))
881 : 0 : continue;
882 : :
883 : 578 : mark_virtual_phi_result_for_renaming (phi);
884 : 578 : return;
885 : : }
886 : : }
887 : :
888 : : /* For deleted_bb_preds, find bbs with same successors. */
889 : :
890 : : static void
891 : 185274 : update_worklist (void)
892 : : {
893 : 185274 : unsigned int i;
894 : 185274 : bitmap_iterator bi;
895 : 185274 : basic_block bb;
896 : 185274 : same_succ *same;
897 : :
898 : 185274 : bitmap_and_compl_into (deleted_bb_preds, deleted_bbs);
899 : 185274 : bitmap_clear (deleted_bbs);
900 : :
901 : 185274 : bitmap_clear_bit (deleted_bb_preds, ENTRY_BLOCK);
902 : 185274 : same_succ_flush_bbs (deleted_bb_preds);
903 : :
904 : 185274 : same = same_succ_alloc ();
905 : 1137172 : EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds, 0, i, bi)
906 : : {
907 : 951898 : bb = BASIC_BLOCK_FOR_FN (cfun, i);
908 : 951898 : gcc_assert (bb != NULL);
909 : 951898 : find_same_succ_bb (bb, &same);
910 : 951898 : if (same == NULL)
911 : 901203 : same = same_succ_alloc ();
912 : : }
913 : 185274 : same_succ::remove (same);
914 : 185274 : bitmap_clear (deleted_bb_preds);
915 : 185274 : }
916 : :
917 : : /* Prints cluster C to FILE. */
918 : :
919 : : static void
920 : 0 : print_cluster (FILE *file, bb_cluster *c)
921 : : {
922 : 0 : if (c == NULL)
923 : : return;
924 : 0 : bitmap_print (file, c->bbs, "bbs:", "\n");
925 : 0 : bitmap_print (file, c->preds, "preds:", "\n");
926 : : }
927 : :
928 : : /* Prints cluster C to stderr. */
929 : :
930 : : extern void debug_cluster (bb_cluster *);
931 : : DEBUG_FUNCTION void
932 : 0 : debug_cluster (bb_cluster *c)
933 : : {
934 : 0 : print_cluster (stderr, c);
935 : 0 : }
936 : :
937 : : /* Update C->rep_bb, given that BB is added to the cluster. */
938 : :
939 : : static void
940 : 1566891 : update_rep_bb (bb_cluster *c, basic_block bb)
941 : : {
942 : : /* Initial. */
943 : 1566891 : if (c->rep_bb == NULL)
944 : : {
945 : 522638 : c->rep_bb = bb;
946 : 522638 : return;
947 : : }
948 : :
949 : : /* Current needs no deps, keep it. */
950 : 1044253 : if (BB_DEP_BB (c->rep_bb) == NULL)
951 : : return;
952 : :
953 : : /* Bb needs no deps, change rep_bb. */
954 : 298 : if (BB_DEP_BB (bb) == NULL)
955 : : {
956 : 20 : c->rep_bb = bb;
957 : 20 : return;
958 : : }
959 : :
960 : : /* Bb needs last deps earlier than current, change rep_bb. A potential
961 : : problem with this, is that the first deps might also be earlier, which
962 : : would mean we prefer longer lifetimes for the deps. To be able to check
963 : : for this, we would have to trace BB_FIRST_DEP_BB as well, besides
964 : : BB_DEP_BB, which is really BB_LAST_DEP_BB.
965 : : The benefit of choosing the bb with last deps earlier, is that it can
966 : : potentially be used as replacement for more bbs. */
967 : 278 : if (dominated_by_p (CDI_DOMINATORS, BB_DEP_BB (c->rep_bb), BB_DEP_BB (bb)))
968 : 278 : c->rep_bb = bb;
969 : : }
970 : :
971 : : /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
972 : :
973 : : static void
974 : 1566891 : add_bb_to_cluster (bb_cluster *c, basic_block bb)
975 : : {
976 : 1566891 : edge e;
977 : 1566891 : edge_iterator ei;
978 : :
979 : 1566891 : bitmap_set_bit (c->bbs, bb->index);
980 : :
981 : 3401959 : FOR_EACH_EDGE (e, ei, bb->preds)
982 : 1835068 : bitmap_set_bit (c->preds, e->src->index);
983 : :
984 : 1566891 : update_rep_bb (c, bb);
985 : 1566891 : }
986 : :
987 : : /* Allocate and init new cluster. */
988 : :
989 : : static bb_cluster *
990 : 522638 : new_cluster (void)
991 : : {
992 : 522638 : bb_cluster *c;
993 : 522638 : c = XCNEW (bb_cluster);
994 : 522638 : c->bbs = BITMAP_ALLOC (NULL);
995 : 522638 : c->preds = BITMAP_ALLOC (NULL);
996 : 522638 : c->rep_bb = NULL;
997 : 522638 : return c;
998 : : }
999 : :
1000 : : /* Delete clusters. */
1001 : :
1002 : : static void
1003 : 522638 : delete_cluster (bb_cluster *c)
1004 : : {
1005 : 522638 : if (c == NULL)
1006 : : return;
1007 : 522638 : BITMAP_FREE (c->bbs);
1008 : 522638 : BITMAP_FREE (c->preds);
1009 : 522638 : XDELETE (c);
1010 : : }
1011 : :
1012 : :
1013 : : /* Array that contains all clusters. */
1014 : :
1015 : : static vec<bb_cluster *> all_clusters;
1016 : :
1017 : : /* Allocate all cluster vectors. */
1018 : :
1019 : : static void
1020 : 241753 : alloc_cluster_vectors (void)
1021 : : {
1022 : 241753 : all_clusters.create (n_basic_blocks_for_fn (cfun));
1023 : 241753 : }
1024 : :
1025 : : /* Reset all cluster vectors. */
1026 : :
1027 : : static void
1028 : 10105 : reset_cluster_vectors (void)
1029 : : {
1030 : 10105 : unsigned int i;
1031 : 10105 : basic_block bb;
1032 : 227104 : for (i = 0; i < all_clusters.length (); ++i)
1033 : 103447 : delete_cluster (all_clusters[i]);
1034 : 10105 : all_clusters.truncate (0);
1035 : 1034747 : FOR_EACH_BB_FN (bb, cfun)
1036 : 1024642 : BB_CLUSTER (bb) = NULL;
1037 : 10105 : }
1038 : :
1039 : : /* Delete all cluster vectors. */
1040 : :
1041 : : static void
1042 : 241753 : delete_cluster_vectors (void)
1043 : : {
1044 : 241753 : unsigned int i;
1045 : 1321888 : for (i = 0; i < all_clusters.length (); ++i)
1046 : 419191 : delete_cluster (all_clusters[i]);
1047 : 241753 : all_clusters.release ();
1048 : 241753 : }
1049 : :
1050 : : /* Merge cluster C2 into C1. */
1051 : :
1052 : : static void
1053 : 0 : merge_clusters (bb_cluster *c1, bb_cluster *c2)
1054 : : {
1055 : 0 : bitmap_ior_into (c1->bbs, c2->bbs);
1056 : 0 : bitmap_ior_into (c1->preds, c2->preds);
1057 : 0 : }
1058 : :
1059 : : /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
1060 : : all_clusters, or merge c with existing cluster. */
1061 : :
1062 : : static void
1063 : 1044253 : set_cluster (basic_block bb1, basic_block bb2)
1064 : : {
1065 : 1044253 : basic_block merge_bb, other_bb;
1066 : 1044253 : bb_cluster *merge, *old, *c;
1067 : :
1068 : 1044253 : if (BB_CLUSTER (bb1) == NULL && BB_CLUSTER (bb2) == NULL)
1069 : : {
1070 : 522638 : c = new_cluster ();
1071 : 522638 : add_bb_to_cluster (c, bb1);
1072 : 522638 : add_bb_to_cluster (c, bb2);
1073 : 522638 : BB_CLUSTER (bb1) = c;
1074 : 522638 : BB_CLUSTER (bb2) = c;
1075 : 522638 : c->index = all_clusters.length ();
1076 : 522638 : all_clusters.safe_push (c);
1077 : : }
1078 : 521615 : else if (BB_CLUSTER (bb1) == NULL || BB_CLUSTER (bb2) == NULL)
1079 : : {
1080 : 521615 : merge_bb = BB_CLUSTER (bb1) == NULL ? bb2 : bb1;
1081 : 521615 : other_bb = BB_CLUSTER (bb1) == NULL ? bb1 : bb2;
1082 : 521615 : merge = BB_CLUSTER (merge_bb);
1083 : 521615 : add_bb_to_cluster (merge, other_bb);
1084 : 521615 : BB_CLUSTER (other_bb) = merge;
1085 : : }
1086 : 0 : else if (BB_CLUSTER (bb1) != BB_CLUSTER (bb2))
1087 : : {
1088 : 0 : unsigned int i;
1089 : 0 : bitmap_iterator bi;
1090 : :
1091 : 0 : old = BB_CLUSTER (bb2);
1092 : 0 : merge = BB_CLUSTER (bb1);
1093 : 0 : merge_clusters (merge, old);
1094 : 0 : EXECUTE_IF_SET_IN_BITMAP (old->bbs, 0, i, bi)
1095 : 0 : BB_CLUSTER (BASIC_BLOCK_FOR_FN (cfun, i)) = merge;
1096 : 0 : all_clusters[old->index] = NULL;
1097 : 0 : update_rep_bb (merge, old->rep_bb);
1098 : 0 : delete_cluster (old);
1099 : : }
1100 : : else
1101 : 0 : gcc_unreachable ();
1102 : 1044253 : }
1103 : :
1104 : : /* Return true if gimple operands T1 and T2 have the same value. */
1105 : :
1106 : : static bool
1107 : 677240 : gimple_operand_equal_value_p (tree t1, tree t2)
1108 : : {
1109 : 677240 : if (t1 == t2)
1110 : : return true;
1111 : :
1112 : 181182 : if (t1 == NULL_TREE
1113 : 181182 : || t2 == NULL_TREE)
1114 : : return false;
1115 : :
1116 : 181182 : if (operand_equal_p (t1, t2, OEP_MATCH_SIDE_EFFECTS))
1117 : : return true;
1118 : :
1119 : 49053 : return gvn_uses_equal (t1, t2);
1120 : : }
1121 : :
1122 : : /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
1123 : : gimple_bb (s2) are members of SAME_SUCC. */
1124 : :
1125 : : static bool
1126 : 409096 : gimple_equal_p (same_succ *same_succ, gimple *s1, gimple *s2)
1127 : : {
1128 : 409096 : unsigned int i;
1129 : 409096 : tree lhs1, lhs2;
1130 : 409096 : basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
1131 : 409096 : tree t1, t2;
1132 : 409096 : bool inv_cond;
1133 : 409096 : enum tree_code code1, code2;
1134 : :
1135 : 409096 : if (gimple_code (s1) != gimple_code (s2))
1136 : : return false;
1137 : :
1138 : 409096 : switch (gimple_code (s1))
1139 : : {
1140 : 308386 : case GIMPLE_CALL:
1141 : 308386 : if (!gimple_call_same_target_p (s1, s2))
1142 : : return false;
1143 : :
1144 : 308386 : t1 = gimple_call_chain (s1);
1145 : 308386 : t2 = gimple_call_chain (s2);
1146 : 308386 : if (!gimple_operand_equal_value_p (t1, t2))
1147 : : return false;
1148 : :
1149 : 308386 : if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
1150 : : return false;
1151 : :
1152 : 587091 : for (i = 0; i < gimple_call_num_args (s1); ++i)
1153 : : {
1154 : 278705 : t1 = gimple_call_arg (s1, i);
1155 : 278705 : t2 = gimple_call_arg (s2, i);
1156 : 278705 : if (!gimple_operand_equal_value_p (t1, t2))
1157 : : return false;
1158 : : }
1159 : :
1160 : 308386 : lhs1 = gimple_get_lhs (s1);
1161 : 308386 : lhs2 = gimple_get_lhs (s2);
1162 : 308386 : if (lhs1 == NULL_TREE && lhs2 == NULL_TREE)
1163 : : return true;
1164 : 3827 : if (lhs1 == NULL_TREE || lhs2 == NULL_TREE)
1165 : : return false;
1166 : 3827 : if (TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME)
1167 : 3682 : return tail_merge_valueize (lhs1) == tail_merge_valueize (lhs2);
1168 : 145 : return operand_equal_p (lhs1, lhs2, 0);
1169 : :
1170 : 92480 : case GIMPLE_ASSIGN:
1171 : 92480 : if (gimple_assign_rhs_code (s1) != gimple_assign_rhs_code (s2))
1172 : : return false;
1173 : :
1174 : 92480 : lhs1 = gimple_get_lhs (s1);
1175 : 92480 : lhs2 = gimple_get_lhs (s2);
1176 : 92480 : if (TREE_CODE (lhs1) != SSA_NAME
1177 : 74895 : && TREE_CODE (lhs2) != SSA_NAME)
1178 : 74895 : return (operand_equal_p (lhs1, lhs2, 0)
1179 : 74895 : && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1),
1180 : : gimple_assign_rhs1 (s2)));
1181 : :
1182 : 17585 : if (TREE_CODE (lhs1) != SSA_NAME
1183 : 17585 : || TREE_CODE (lhs2) != SSA_NAME)
1184 : : return false;
1185 : :
1186 : 17585 : gcc_checking_assert (gimple_num_args (s1) == gimple_num_args (s2));
1187 : 34906 : for (i = 0; i < gimple_num_args (s1); ++i)
1188 : : {
1189 : 17621 : t1 = gimple_arg (s1, i);
1190 : 17621 : t2 = gimple_arg (s2, i);
1191 : 17621 : if (!gimple_operand_equal_value_p (t1, t2))
1192 : : return false;
1193 : : }
1194 : : return true;
1195 : :
1196 : 2887 : case GIMPLE_COND:
1197 : 2887 : t1 = gimple_cond_lhs (s1);
1198 : 2887 : t2 = gimple_cond_lhs (s2);
1199 : 2887 : if (!gimple_operand_equal_value_p (t1, t2))
1200 : : return false;
1201 : :
1202 : 1608 : t1 = gimple_cond_rhs (s1);
1203 : 1608 : t2 = gimple_cond_rhs (s2);
1204 : 1608 : if (!gimple_operand_equal_value_p (t1, t2))
1205 : : return false;
1206 : :
1207 : 1300 : code1 = gimple_cond_code (s1);
1208 : 1300 : code2 = gimple_cond_code (s2);
1209 : 1300 : inv_cond = (bitmap_bit_p (same_succ->inverse, bb1->index)
1210 : 1300 : != bitmap_bit_p (same_succ->inverse, bb2->index));
1211 : 1300 : if (inv_cond)
1212 : : {
1213 : 23 : bool honor_nans = HONOR_NANS (t1);
1214 : 23 : code2 = invert_tree_comparison (code2, honor_nans);
1215 : : }
1216 : 1300 : return code1 == code2;
1217 : :
1218 : : default:
1219 : : return false;
1220 : : }
1221 : : }
1222 : :
1223 : : /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
1224 : : Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
1225 : : processed statements. */
1226 : :
1227 : : static void
1228 : 2922032 : gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse,
1229 : : bool *vuse_escaped)
1230 : : {
1231 : 2927299 : gimple *stmt;
1232 : 2927299 : tree lvuse;
1233 : :
1234 : 2932566 : while (true)
1235 : : {
1236 : 2927299 : if (gsi_end_p (*gsi))
1237 : : return;
1238 : 847769 : stmt = gsi_stmt (*gsi);
1239 : :
1240 : 847769 : lvuse = gimple_vuse (stmt);
1241 : 812031 : if (lvuse != NULL_TREE)
1242 : : {
1243 : 725392 : *vuse = lvuse;
1244 : 725392 : if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_DEF))
1245 : 42260 : *vuse_escaped = true;
1246 : : }
1247 : :
1248 : 847769 : if (!stmt_local_def (stmt))
1249 : : return;
1250 : 5267 : gsi_prev_nondebug (gsi);
1251 : : }
1252 : : }
1253 : :
1254 : : /* Return true if equal (in the sense of gimple_equal_p) statements STMT1 and
1255 : : STMT2 are allowed to be merged. */
1256 : :
1257 : : static bool
1258 : 362899 : merge_stmts_p (gimple *stmt1, gimple *stmt2)
1259 : : {
1260 : : /* What could be better than this here is to blacklist the bb
1261 : : containing the stmt, when encountering the stmt f.i. in
1262 : : same_succ_hash. */
1263 : 362899 : if (is_tm_ending (stmt1))
1264 : : return false;
1265 : :
1266 : : /* Verify EH landing pads. */
1267 : 362839 : if (lookup_stmt_eh_lp_fn (cfun, stmt1) != lookup_stmt_eh_lp_fn (cfun, stmt2))
1268 : : return false;
1269 : :
1270 : 355626 : if (is_gimple_call (stmt1)
1271 : 355626 : && gimple_call_internal_p (stmt1))
1272 : 23 : switch (gimple_call_internal_fn (stmt1))
1273 : : {
1274 : 0 : case IFN_UBSAN_NULL:
1275 : 0 : case IFN_UBSAN_BOUNDS:
1276 : 0 : case IFN_UBSAN_VPTR:
1277 : 0 : case IFN_UBSAN_CHECK_ADD:
1278 : 0 : case IFN_UBSAN_CHECK_SUB:
1279 : 0 : case IFN_UBSAN_CHECK_MUL:
1280 : 0 : case IFN_UBSAN_OBJECT_SIZE:
1281 : 0 : case IFN_UBSAN_PTR:
1282 : 0 : case IFN_ASAN_CHECK:
1283 : : /* For these internal functions, gimple_location is an implicit
1284 : : parameter, which will be used explicitly after expansion.
1285 : : Merging these statements may cause confusing line numbers in
1286 : : sanitizer messages. */
1287 : 0 : return gimple_location (stmt1) == gimple_location (stmt2);
1288 : : default:
1289 : : break;
1290 : : }
1291 : :
1292 : : return true;
1293 : : }
1294 : :
1295 : : /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1296 : : clusters them. */
1297 : :
1298 : : static void
1299 : 1105390 : find_duplicate (same_succ *same_succ, basic_block bb1, basic_block bb2)
1300 : : {
1301 : 1105390 : gimple_stmt_iterator gsi1 = gsi_last_nondebug_bb (bb1);
1302 : 1105390 : gimple_stmt_iterator gsi2 = gsi_last_nondebug_bb (bb2);
1303 : 1105390 : tree vuse1 = NULL_TREE, vuse2 = NULL_TREE;
1304 : 1105390 : bool vuse_escaped = false;
1305 : :
1306 : 1105390 : gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
1307 : 1105390 : gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
1308 : :
1309 : 2566406 : while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2))
1310 : : {
1311 : 421251 : gimple *stmt1 = gsi_stmt (gsi1);
1312 : 421251 : gimple *stmt2 = gsi_stmt (gsi2);
1313 : :
1314 : 421251 : if (gimple_code (stmt1) == GIMPLE_LABEL
1315 : 421251 : && gimple_code (stmt2) == GIMPLE_LABEL)
1316 : : break;
1317 : :
1318 : 409096 : if (!gimple_equal_p (same_succ, stmt1, stmt2))
1319 : 61137 : return;
1320 : :
1321 : 362899 : if (!merge_stmts_p (stmt1, stmt2))
1322 : : return;
1323 : :
1324 : 355626 : gsi_prev_nondebug (&gsi1);
1325 : 355626 : gsi_prev_nondebug (&gsi2);
1326 : 355626 : gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
1327 : 355626 : gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
1328 : : }
1329 : :
1330 : 12156 : while (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
1331 : : {
1332 : 12156 : tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1)));
1333 : 24312 : if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
1334 : : return;
1335 : 1076232 : gsi_prev (&gsi1);
1336 : : }
1337 : 12156 : while (!gsi_end_p (gsi2) && gimple_code (gsi_stmt (gsi2)) == GIMPLE_LABEL)
1338 : : {
1339 : 12156 : tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi2)));
1340 : 24312 : if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
1341 : : return;
1342 : 1076232 : gsi_prev (&gsi2);
1343 : : }
1344 : 1051920 : if (!(gsi_end_p (gsi1) && gsi_end_p (gsi2)))
1345 : 0 : return;
1346 : :
1347 : : /* If the incoming vuses are not the same, and the vuse escaped into an
1348 : : SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
1349 : : which potentially means the semantics of one of the blocks will be changed.
1350 : : TODO: make this check more precise. */
1351 : 1051920 : if (vuse_escaped && vuse1 != vuse2)
1352 : : return;
1353 : :
1354 : 1044253 : if (dump_file)
1355 : 26 : fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1356 : : bb1->index, bb2->index);
1357 : :
1358 : 1044253 : set_cluster (bb1, bb2);
1359 : : }
1360 : :
1361 : : /* Returns whether for all phis in DEST the phi alternatives for E1 and
1362 : : E2 are equal. */
1363 : :
1364 : : static bool
1365 : 1716766 : same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
1366 : : {
1367 : 1716766 : int n1 = e1->dest_idx, n2 = e2->dest_idx;
1368 : 1716766 : gphi_iterator gsi;
1369 : :
1370 : 2355902 : for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
1371 : : {
1372 : 1498194 : gphi *phi = gsi.phi ();
1373 : 1498194 : tree lhs = gimple_phi_result (phi);
1374 : 1498194 : tree val1 = gimple_phi_arg_def (phi, n1);
1375 : 1498194 : tree val2 = gimple_phi_arg_def (phi, n2);
1376 : :
1377 : 2996388 : if (virtual_operand_p (lhs))
1378 : 485356 : continue;
1379 : :
1380 : 1012838 : if (operand_equal_for_phi_arg_p (val1, val2))
1381 : 143517 : continue;
1382 : 869321 : if (gvn_uses_equal (val1, val2))
1383 : 10263 : continue;
1384 : :
1385 : : return false;
1386 : : }
1387 : :
1388 : : return true;
1389 : : }
1390 : :
1391 : : /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1392 : : phi alternatives for BB1 and BB2 are equal. */
1393 : :
1394 : : static bool
1395 : 1964448 : same_phi_alternatives (same_succ *same_succ, basic_block bb1, basic_block bb2)
1396 : : {
1397 : 1964448 : unsigned int s;
1398 : 1964448 : bitmap_iterator bs;
1399 : 1964448 : edge e1, e2;
1400 : 1964448 : basic_block succ;
1401 : :
1402 : 2822156 : EXECUTE_IF_SET_IN_BITMAP (same_succ->succs, 0, s, bs)
1403 : : {
1404 : 1716766 : succ = BASIC_BLOCK_FOR_FN (cfun, s);
1405 : 1716766 : e1 = find_edge (bb1, succ);
1406 : 1716766 : e2 = find_edge (bb2, succ);
1407 : 1716766 : if (e1->flags & EDGE_COMPLEX
1408 : 1716766 : || e2->flags & EDGE_COMPLEX)
1409 : : return false;
1410 : :
1411 : : /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1412 : : the same value. */
1413 : 1716766 : if (!same_phi_alternatives_1 (succ, e1, e2))
1414 : : return false;
1415 : : }
1416 : :
1417 : : return true;
1418 : : }
1419 : :
1420 : : /* Return true if BB has non-vop phis. */
1421 : :
1422 : : static bool
1423 : 17799799 : bb_has_non_vop_phi (basic_block bb)
1424 : : {
1425 : 17799799 : gimple_seq phis = phi_nodes (bb);
1426 : 17799799 : gimple *phi;
1427 : :
1428 : 17799799 : if (phis == NULL)
1429 : : return false;
1430 : :
1431 : 135670 : if (!gimple_seq_singleton_p (phis))
1432 : : return true;
1433 : :
1434 : 97160 : phi = gimple_seq_first_stmt (phis);
1435 : 194320 : return !virtual_operand_p (gimple_phi_result (phi));
1436 : : }
1437 : :
1438 : : /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1439 : : invariant that uses in FROM are dominates by their defs. */
1440 : :
1441 : : static bool
1442 : 5134923 : deps_ok_for_redirect_from_bb_to_bb (basic_block from, basic_block to)
1443 : : {
1444 : 5134923 : basic_block cd, dep_bb = BB_DEP_BB (to);
1445 : 5134923 : edge_iterator ei;
1446 : 5134923 : edge e;
1447 : :
1448 : 5134923 : if (dep_bb == NULL)
1449 : : return true;
1450 : :
1451 : 1337592 : bitmap from_preds = BITMAP_ALLOC (NULL);
1452 : 2706653 : FOR_EACH_EDGE (e, ei, from->preds)
1453 : 1369061 : bitmap_set_bit (from_preds, e->src->index);
1454 : 1337592 : cd = nearest_common_dominator_for_set (CDI_DOMINATORS, from_preds);
1455 : 1337592 : BITMAP_FREE (from_preds);
1456 : :
1457 : 1337592 : return dominated_by_p (CDI_DOMINATORS, dep_bb, cd);
1458 : : }
1459 : :
1460 : : /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1461 : : replacement bb) and vice versa maintains the invariant that uses in the
1462 : : replacement are dominates by their defs. */
1463 : :
1464 : : static bool
1465 : 2952630 : deps_ok_for_redirect (basic_block bb1, basic_block bb2)
1466 : : {
1467 : 2952630 : if (BB_CLUSTER (bb1) != NULL)
1468 : 749766 : bb1 = BB_CLUSTER (bb1)->rep_bb;
1469 : :
1470 : 2952630 : if (BB_CLUSTER (bb2) != NULL)
1471 : 72027 : bb2 = BB_CLUSTER (bb2)->rep_bb;
1472 : :
1473 : 2952630 : return (deps_ok_for_redirect_from_bb_to_bb (bb1, bb2)
1474 : 2952630 : && deps_ok_for_redirect_from_bb_to_bb (bb2, bb1));
1475 : : }
1476 : :
1477 : : /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1478 : :
1479 : : static void
1480 : 981972 : find_clusters_1 (same_succ *same_succ)
1481 : : {
1482 : 981972 : basic_block bb1, bb2;
1483 : 981972 : unsigned int i, j;
1484 : 981972 : bitmap_iterator bi, bj;
1485 : 981972 : int nr_comparisons;
1486 : 981972 : int max_comparisons = param_max_tail_merge_comparisons;
1487 : :
1488 : 4228764 : EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, 0, i, bi)
1489 : : {
1490 : 3246792 : bb1 = BASIC_BLOCK_FOR_FN (cfun, i);
1491 : :
1492 : : /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1493 : : phi-nodes in bb1 and bb2, with the same alternatives for the same
1494 : : preds. */
1495 : 6461237 : if (bb_has_non_vop_phi (bb1) || bb_has_eh_pred (bb1)
1496 : 5822053 : || bb_has_abnormal_pred (bb1))
1497 : 671649 : continue;
1498 : :
1499 : 2575143 : nr_comparisons = 0;
1500 : 17020467 : EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, i + 1, j, bj)
1501 : : {
1502 : 14553007 : bb2 = BASIC_BLOCK_FOR_FN (cfun, j);
1503 : :
1504 : 29083186 : if (bb_has_non_vop_phi (bb2) || bb_has_eh_pred (bb2)
1505 : 29082887 : || bb_has_abnormal_pred (bb2))
1506 : 23127 : continue;
1507 : :
1508 : 14529880 : if (BB_CLUSTER (bb1) != NULL && BB_CLUSTER (bb1) == BB_CLUSTER (bb2))
1509 : 11469567 : continue;
1510 : :
1511 : : /* Limit quadratic behavior. */
1512 : 3060313 : nr_comparisons++;
1513 : 3060313 : if (nr_comparisons > max_comparisons)
1514 : : break;
1515 : :
1516 : : /* This is a conservative dependency check. We could test more
1517 : : precise for allowed replacement direction. */
1518 : 2952630 : if (!deps_ok_for_redirect (bb1, bb2))
1519 : 988182 : continue;
1520 : :
1521 : 1964448 : if (!(same_phi_alternatives (same_succ, bb1, bb2)))
1522 : 859058 : continue;
1523 : :
1524 : 1105390 : find_duplicate (same_succ, bb1, bb2);
1525 : : }
1526 : : }
1527 : 981972 : }
1528 : :
1529 : : /* Find clusters of bbs which can be merged. */
1530 : :
1531 : : static void
1532 : 251858 : find_clusters (void)
1533 : : {
1534 : 251858 : same_succ *same;
1535 : :
1536 : 1233830 : while (!worklist.is_empty ())
1537 : : {
1538 : 981972 : same = worklist.pop ();
1539 : 981972 : same->in_worklist = false;
1540 : 82 : if (dump_file && (dump_flags & TDF_DETAILS))
1541 : : {
1542 : 11 : fprintf (dump_file, "processing worklist entry\n");
1543 : 11 : same_succ_print (dump_file, same);
1544 : : }
1545 : 981972 : find_clusters_1 (same);
1546 : : }
1547 : 251858 : }
1548 : :
1549 : : /* Returns the vop phi of BB, if any. */
1550 : :
1551 : : static gphi *
1552 : 1068943 : vop_phi (basic_block bb)
1553 : : {
1554 : 1068943 : gphi *stmt;
1555 : 1068943 : gphi_iterator gsi;
1556 : 1068943 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1557 : : {
1558 : 43170 : stmt = gsi.phi ();
1559 : 86340 : if (! virtual_operand_p (gimple_phi_result (stmt)))
1560 : 0 : continue;
1561 : : return stmt;
1562 : : }
1563 : : return NULL;
1564 : : }
1565 : :
1566 : : /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
1567 : :
1568 : : static void
1569 : 1044253 : replace_block_by (basic_block bb1, basic_block bb2)
1570 : : {
1571 : 1044253 : edge pred_edge;
1572 : 1044253 : unsigned int i;
1573 : 1044253 : gphi *bb2_phi;
1574 : :
1575 : 1044253 : bb2_phi = vop_phi (bb2);
1576 : :
1577 : : /* Mark the basic block as deleted. */
1578 : 1044253 : mark_basic_block_deleted (bb1);
1579 : :
1580 : : /* Redirect the incoming edges of bb1 to bb2. */
1581 : 3252240 : for (i = EDGE_COUNT (bb1->preds); i > 0 ; --i)
1582 : : {
1583 : 1163734 : pred_edge = EDGE_PRED (bb1, i - 1);
1584 : 1163734 : pred_edge = redirect_edge_and_branch (pred_edge, bb2);
1585 : 1163734 : gcc_assert (pred_edge != NULL);
1586 : :
1587 : 1163734 : if (bb2_phi == NULL)
1588 : 1139044 : continue;
1589 : :
1590 : : /* The phi might have run out of capacity when the redirect added an
1591 : : argument, which means it could have been replaced. Refresh it. */
1592 : 24690 : bb2_phi = vop_phi (bb2);
1593 : :
1594 : 24690 : add_phi_arg (bb2_phi, SSA_NAME_VAR (gimple_phi_result (bb2_phi)),
1595 : : pred_edge, UNKNOWN_LOCATION);
1596 : : }
1597 : :
1598 : :
1599 : : /* Merge the outgoing edge counts from bb1 onto bb2. */
1600 : 1044253 : edge e1, e2;
1601 : 1044253 : edge_iterator ei;
1602 : :
1603 : 1044253 : if (bb2->count.initialized_p ())
1604 : 1855949 : FOR_EACH_EDGE (e1, ei, bb1->succs)
1605 : : {
1606 : 811782 : e2 = find_edge (bb2, e1->dest);
1607 : 811782 : gcc_assert (e2);
1608 : :
1609 : : /* If probabilities are same, we are done.
1610 : : If counts are nonzero we can distribute accordingly. In remaining
1611 : : cases just average the values and hope for the best. */
1612 : 811782 : e2->probability = e1->probability.combine_with_count
1613 : 811782 : (bb1->count, e2->probability, bb2->count);
1614 : : }
1615 : 1044253 : bb2->count += bb1->count;
1616 : :
1617 : : /* Move over any user labels from bb1 after the bb2 labels. */
1618 : 1044253 : gimple_stmt_iterator gsi1 = gsi_start_bb (bb1);
1619 : 1044253 : if (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
1620 : : {
1621 : 12155 : gimple_stmt_iterator gsi2 = gsi_after_labels (bb2);
1622 : 24311 : while (!gsi_end_p (gsi1)
1623 : 24311 : && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
1624 : : {
1625 : 12156 : tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1)));
1626 : 24312 : gcc_assert (!DECL_NONLOCAL (label) && !FORCED_LABEL (label));
1627 : 12156 : if (DECL_ARTIFICIAL (label))
1628 : 11799 : gsi_next (&gsi1);
1629 : : else
1630 : 357 : gsi_move_before (&gsi1, &gsi2);
1631 : : }
1632 : : }
1633 : :
1634 : : /* Clear range info from all stmts in BB2 -- this transformation
1635 : : could make them out of date. */
1636 : 1044253 : reset_flow_sensitive_info_in_bb (bb2);
1637 : :
1638 : : /* Do updates that use bb1, before deleting bb1. */
1639 : 1044253 : release_last_vdef (bb1);
1640 : 1044253 : same_succ_flush_bb (bb1);
1641 : :
1642 : 1044253 : delete_basic_block (bb1);
1643 : 1044253 : }
1644 : :
1645 : : /* Bbs for which update_debug_stmt need to be called. */
1646 : :
1647 : : static bitmap update_bbs;
1648 : :
1649 : : /* For each cluster in all_clusters, merge all cluster->bbs. Returns
1650 : : number of bbs removed. */
1651 : :
1652 : : static int
1653 : 191562 : apply_clusters (void)
1654 : : {
1655 : 191562 : basic_block bb1, bb2;
1656 : 191562 : bb_cluster *c;
1657 : 191562 : unsigned int i, j;
1658 : 191562 : bitmap_iterator bj;
1659 : 191562 : int nr_bbs_removed = 0;
1660 : :
1661 : 1428400 : for (i = 0; i < all_clusters.length (); ++i)
1662 : : {
1663 : 522638 : c = all_clusters[i];
1664 : 522638 : if (c == NULL)
1665 : 0 : continue;
1666 : :
1667 : 522638 : bb2 = c->rep_bb;
1668 : 522638 : bitmap_set_bit (update_bbs, bb2->index);
1669 : :
1670 : 522638 : bitmap_clear_bit (c->bbs, bb2->index);
1671 : 1566891 : EXECUTE_IF_SET_IN_BITMAP (c->bbs, 0, j, bj)
1672 : : {
1673 : 1044253 : bb1 = BASIC_BLOCK_FOR_FN (cfun, j);
1674 : 1044253 : bitmap_clear_bit (update_bbs, bb1->index);
1675 : :
1676 : 1044253 : replace_block_by (bb1, bb2);
1677 : 1044253 : nr_bbs_removed++;
1678 : : }
1679 : : }
1680 : :
1681 : 191562 : return nr_bbs_removed;
1682 : : }
1683 : :
1684 : : /* Resets debug statement STMT if it has uses that are not dominated by their
1685 : : defs. */
1686 : :
1687 : : static void
1688 : 173428 : update_debug_stmt (gimple *stmt)
1689 : : {
1690 : 173428 : use_operand_p use_p;
1691 : 173428 : ssa_op_iter oi;
1692 : 173428 : basic_block bbuse;
1693 : :
1694 : 173428 : if (!gimple_debug_bind_p (stmt))
1695 : 25274 : return;
1696 : :
1697 : 148154 : bbuse = gimple_bb (stmt);
1698 : 151516 : FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
1699 : : {
1700 : 9576 : tree name = USE_FROM_PTR (use_p);
1701 : 9576 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1702 : 9576 : basic_block bbdef = gimple_bb (def_stmt);
1703 : 12938 : if (bbdef == NULL || bbuse == bbdef
1704 : 9576 : || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef))
1705 : 3362 : continue;
1706 : :
1707 : 6214 : gimple_debug_bind_reset_value (stmt);
1708 : 6214 : update_stmt (stmt);
1709 : 6214 : break;
1710 : : }
1711 : : }
1712 : :
1713 : : /* Resets all debug statements that have uses that are not
1714 : : dominated by their defs. */
1715 : :
1716 : : static void
1717 : 123126 : update_debug_stmts (void)
1718 : : {
1719 : 123126 : basic_block bb;
1720 : 123126 : bitmap_iterator bi;
1721 : 123126 : unsigned int i;
1722 : :
1723 : 486611 : EXECUTE_IF_SET_IN_BITMAP (update_bbs, 0, i, bi)
1724 : : {
1725 : 363485 : gimple *stmt;
1726 : 363485 : gimple_stmt_iterator gsi;
1727 : :
1728 : 363485 : bb = BASIC_BLOCK_FOR_FN (cfun, i);
1729 : 959796 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1730 : : {
1731 : 232826 : stmt = gsi_stmt (gsi);
1732 : 232826 : if (!is_gimple_debug (stmt))
1733 : 59398 : continue;
1734 : 173428 : update_debug_stmt (stmt);
1735 : : }
1736 : : }
1737 : 123126 : }
1738 : :
1739 : : /* Runs tail merge optimization. */
1740 : :
1741 : : unsigned int
1742 : 904990 : tail_merge_optimize (bool need_crit_edge_split)
1743 : : {
1744 : 904990 : int nr_bbs_removed_total = 0;
1745 : 904990 : int nr_bbs_removed;
1746 : 904990 : bool loop_entered = false;
1747 : 904990 : int iteration_nr = 0;
1748 : 904990 : int max_iterations = param_max_tail_merge_iterations;
1749 : :
1750 : 904990 : if (!flag_tree_tail_merge
1751 : 904945 : || max_iterations == 0)
1752 : : return 0;
1753 : :
1754 : 904945 : timevar_push (TV_TREE_TAIL_MERGE);
1755 : :
1756 : : /* Re-split critical edges when PRE did a CFG cleanup. */
1757 : 904945 : if (need_crit_edge_split)
1758 : 126144 : split_edges_for_insertion ();
1759 : :
1760 : 904945 : if (!dom_info_available_p (CDI_DOMINATORS))
1761 : : {
1762 : : /* PRE can leave us with unreachable blocks, remove them now. */
1763 : 0 : delete_unreachable_blocks ();
1764 : 0 : calculate_dominance_info (CDI_DOMINATORS);
1765 : : }
1766 : 904945 : init_worklist ();
1767 : :
1768 : 1995164 : while (!worklist.is_empty ())
1769 : : {
1770 : 251858 : if (!loop_entered)
1771 : : {
1772 : 241753 : loop_entered = true;
1773 : 241753 : alloc_cluster_vectors ();
1774 : 241753 : update_bbs = BITMAP_ALLOC (NULL);
1775 : : }
1776 : : else
1777 : 10105 : reset_cluster_vectors ();
1778 : :
1779 : 251858 : iteration_nr++;
1780 : 251858 : if (dump_file && (dump_flags & TDF_DETAILS))
1781 : 10 : fprintf (dump_file, "worklist iteration #%d\n", iteration_nr);
1782 : :
1783 : 251858 : find_clusters ();
1784 : 251858 : gcc_assert (worklist.is_empty ());
1785 : 251858 : if (all_clusters.is_empty ())
1786 : : break;
1787 : :
1788 : 191562 : nr_bbs_removed = apply_clusters ();
1789 : 191562 : nr_bbs_removed_total += nr_bbs_removed;
1790 : 191562 : if (nr_bbs_removed == 0)
1791 : : break;
1792 : :
1793 : 191562 : free_dominance_info (CDI_DOMINATORS);
1794 : :
1795 : 191562 : if (iteration_nr == max_iterations)
1796 : : break;
1797 : :
1798 : 185274 : calculate_dominance_info (CDI_DOMINATORS);
1799 : 185274 : update_worklist ();
1800 : : }
1801 : :
1802 : 904945 : if (dump_file && (dump_flags & TDF_DETAILS))
1803 : 32 : fprintf (dump_file, "htab collision / search: %f\n",
1804 : : same_succ_htab->collisions ());
1805 : :
1806 : 904945 : if (nr_bbs_removed_total > 0)
1807 : : {
1808 : 185274 : if (MAY_HAVE_DEBUG_BIND_STMTS)
1809 : : {
1810 : 123126 : calculate_dominance_info (CDI_DOMINATORS);
1811 : 123126 : update_debug_stmts ();
1812 : : }
1813 : :
1814 : 185274 : if (dump_file && (dump_flags & TDF_DETAILS))
1815 : : {
1816 : 2 : fprintf (dump_file, "Before TODOs.\n");
1817 : 2 : dump_function_to_file (current_function_decl, dump_file, dump_flags);
1818 : : }
1819 : :
1820 : 185274 : mark_virtual_operands_for_renaming (cfun);
1821 : : }
1822 : :
1823 : 904945 : delete_worklist ();
1824 : 904945 : if (loop_entered)
1825 : : {
1826 : 241753 : delete_cluster_vectors ();
1827 : 241753 : BITMAP_FREE (update_bbs);
1828 : : }
1829 : :
1830 : 904945 : timevar_pop (TV_TREE_TAIL_MERGE);
1831 : :
1832 : 904945 : return 0;
1833 : : }
|