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 : 40815119 : same_succ::hash (const same_succ *e)
244 : : {
245 : 40815119 : 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 : 12819787 : tail_merge_valueize (tree name)
292 : : {
293 : 12819787 : if (TREE_CODE (name) == SSA_NAME
294 : 12819787 : && has_VN_INFO (name))
295 : : {
296 : 4842617 : tree tem = VN_INFO (name)->valnum;
297 : 4842617 : 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 : 37666478 : stmt_local_def (gimple *stmt)
308 : : {
309 : 37666478 : basic_block bb, def_bb;
310 : 37666478 : imm_use_iterator iter;
311 : 37666478 : use_operand_p use_p;
312 : 37666478 : tree val;
313 : 37666478 : def_operand_p def_p;
314 : :
315 : 37666478 : if (gimple_vdef (stmt) != NULL_TREE
316 : 24145871 : || gimple_has_side_effects (stmt)
317 : 23071029 : || gimple_could_trap_p_1 (stmt, false, false)
318 : 22326579 : || 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 : 45721621 : || is_gimple_call (stmt))
327 : 22583164 : return false;
328 : :
329 : 15083314 : def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
330 : 15083314 : if (def_p == NULL)
331 : : return false;
332 : :
333 : 7828242 : val = DEF_FROM_PTR (def_p);
334 : 7828242 : if (val == NULL_TREE || TREE_CODE (val) != SSA_NAME)
335 : : return false;
336 : :
337 : 7828242 : def_bb = gimple_bb (stmt);
338 : :
339 : 16460621 : FOR_EACH_IMM_USE_FAST (use_p, iter, val)
340 : : {
341 : 9978354 : if (is_gimple_debug (USE_STMT (use_p)))
342 : 1210699 : continue;
343 : 8767655 : bb = gimple_bb (USE_STMT (use_p));
344 : 8767655 : if (bb == def_bb)
345 : 6727535 : continue;
346 : :
347 : 2734265 : if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI
348 : 2040120 : && EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src == def_bb)
349 : 694145 : 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 : 7395714 : gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator *gsi)
361 : : {
362 : 7878176 : gimple *stmt;
363 : :
364 : 8360638 : while (true)
365 : : {
366 : 7878176 : if (gsi_end_p (*gsi))
367 : : return;
368 : 3019772 : stmt = gsi_stmt (*gsi);
369 : 3019772 : if (!stmt_local_def (stmt))
370 : : return;
371 : 482462 : 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 : 1192225 : gvn_uses_equal (tree val1, tree val2)
382 : : {
383 : 1192225 : gcc_checking_assert (val1 != NULL_TREE && val2 != NULL_TREE);
384 : :
385 : 1192225 : if (val1 == val2)
386 : : return true;
387 : :
388 : 1192225 : 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 : 27502 : && (TREE_CODE (val2) == SSA_NAME || CONSTANT_CLASS_P (val2)));
393 : : }
394 : :
395 : : /* Prints E to FILE. */
396 : :
397 : : static void
398 : 20 : same_succ_print (FILE *file, const same_succ *e)
399 : : {
400 : 20 : unsigned int i;
401 : 20 : bitmap_print (file, e->bbs, "bbs:", "\n");
402 : 20 : bitmap_print (file, e->succs, "succs:", "\n");
403 : 20 : bitmap_print (file, e->inverse, "inverse:", "\n");
404 : 20 : fprintf (file, "flags:");
405 : 60 : for (i = 0; i < e->succ_flags.length (); ++i)
406 : 20 : fprintf (file, " %x", e->succ_flags[i]);
407 : 20 : fprintf (file, "\n");
408 : 20 : }
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 : 33811596 : update_dep_bb (basic_block use_bb, tree val)
424 : : {
425 : 33811596 : basic_block dep_bb;
426 : :
427 : : /* Not a dep. */
428 : 33811596 : if (TREE_CODE (val) != SSA_NAME)
429 : : return;
430 : :
431 : : /* Skip use of global def. */
432 : 32339144 : if (SSA_NAME_IS_DEFAULT_DEF (val))
433 : : return;
434 : :
435 : : /* Skip use of local def. */
436 : 28162568 : dep_bb = gimple_bb (SSA_NAME_DEF_STMT (val));
437 : 28162568 : if (dep_bb == use_bb)
438 : : return;
439 : :
440 : 10397100 : if (BB_DEP_BB (use_bb) == NULL
441 : 10397100 : || dominated_by_p (CDI_DOMINATORS, dep_bb, BB_DEP_BB (use_bb)))
442 : 8945826 : BB_DEP_BB (use_bb) = dep_bb;
443 : : }
444 : :
445 : : /* Update BB_DEP_BB, given the dependencies in STMT. */
446 : :
447 : : static void
448 : 33591371 : stmt_update_dep_bb (gimple *stmt)
449 : : {
450 : 33591371 : ssa_op_iter iter;
451 : 33591371 : use_operand_p use;
452 : :
453 : 61968358 : FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
454 : 28376987 : update_dep_bb (gimple_bb (stmt), USE_FROM_PTR (use));
455 : 33591371 : }
456 : :
457 : : /* Calculates hash value for same_succ VE. */
458 : :
459 : : static hashval_t
460 : 13349713 : same_succ_hash (const same_succ *e)
461 : : {
462 : 13349713 : inchash::hash hstate (bitmap_hash (e->succs));
463 : 13349713 : int flags;
464 : 13349713 : unsigned int i;
465 : 13349713 : unsigned int first = bitmap_first_set_bit (e->bbs);
466 : 13349713 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, first);
467 : 13349713 : int size = 0;
468 : 13349713 : gimple *stmt;
469 : 13349713 : tree arg;
470 : 13349713 : unsigned int s;
471 : 13349713 : bitmap_iterator bs;
472 : :
473 : 13349713 : for (gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
474 : 46941084 : !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
475 : : {
476 : 33591371 : stmt = gsi_stmt (gsi);
477 : 33591371 : if (is_gimple_debug (stmt))
478 : 0 : continue;
479 : :
480 : 33591371 : stmt_update_dep_bb (stmt);
481 : 33591371 : if (stmt_local_def (stmt))
482 : 5992976 : continue;
483 : 27598395 : size++;
484 : :
485 : 27598395 : hstate.add_int (gimple_code (stmt));
486 : 27598395 : if (is_gimple_assign (stmt))
487 : 15367507 : hstate.add_int (gimple_assign_rhs_code (stmt));
488 : 27598395 : if (!is_gimple_call (stmt))
489 : 22312636 : continue;
490 : 5285759 : if (gimple_call_internal_p (stmt))
491 : 85352 : hstate.add_int (gimple_call_internal_fn (stmt));
492 : : else
493 : : {
494 : 5200407 : inchash::add_expr (gimple_call_fn (stmt), hstate);
495 : 5200407 : if (gimple_call_chain (stmt))
496 : 30250 : inchash::add_expr (gimple_call_chain (stmt), hstate);
497 : : }
498 : 15714008 : for (i = 0; i < gimple_call_num_args (stmt); i++)
499 : : {
500 : 10428249 : arg = gimple_call_arg (stmt, i);
501 : 10428249 : arg = tail_merge_valueize (arg);
502 : 10428249 : inchash::add_expr (arg, hstate);
503 : : }
504 : : }
505 : :
506 : 13349713 : hstate.add_int (size);
507 : 13349713 : BB_SIZE (bb) = size;
508 : :
509 : 13349713 : hstate.add_int (bb->loop_father->num);
510 : :
511 : 31436723 : for (i = 0; i < e->succ_flags.length (); ++i)
512 : : {
513 : 18087010 : flags = e->succ_flags[i];
514 : 18087010 : flags = flags & ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
515 : 18087010 : hstate.add_int (flags);
516 : : }
517 : :
518 : 31436723 : EXECUTE_IF_SET_IN_BITMAP (e->succs, 0, s, bs)
519 : : {
520 : 18087010 : int n = find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, s))->dest_idx;
521 : 18087010 : for (gphi_iterator gsi = gsi_start_phis (BASIC_BLOCK_FOR_FN (cfun, s));
522 : 27756935 : !gsi_end_p (gsi);
523 : 9669925 : gsi_next (&gsi))
524 : : {
525 : 9669925 : gphi *phi = gsi.phi ();
526 : 9669925 : tree lhs = gimple_phi_result (phi);
527 : 9669925 : tree val = gimple_phi_arg_def (phi, n);
528 : :
529 : 19339850 : if (virtual_operand_p (lhs))
530 : 4235316 : continue;
531 : 5434609 : update_dep_bb (bb, val);
532 : : }
533 : : }
534 : :
535 : 13349713 : 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 : 4858471 : inverse_flags (const same_succ *e1, const same_succ *e2)
544 : : {
545 : 4858471 : int f1a, f1b, f2a, f2b;
546 : 4858471 : int mask = ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
547 : :
548 : 4871775 : if (e1->succ_flags.length () != 2)
549 : : return false;
550 : :
551 : 14878 : f1a = e1->succ_flags[0];
552 : 14878 : f1b = e1->succ_flags[1];
553 : 14878 : f2a = e2->succ_flags[0];
554 : 14878 : f2b = e2->succ_flags[1];
555 : :
556 : 14878 : if (f1a == f2a && f1b == f2b)
557 : : return false;
558 : :
559 : 1574 : return (f1a & mask) == (f2a & mask) && (f1b & mask) == (f2b & mask);
560 : : }
561 : :
562 : : /* Compares SAME_SUCCs E1 and E2. */
563 : :
564 : : int
565 : 48861807 : same_succ::equal (const same_succ *e1, const same_succ *e2)
566 : : {
567 : 48861807 : unsigned int i, first1, first2;
568 : 48861807 : gimple_stmt_iterator gsi1, gsi2;
569 : 48861807 : gimple *s1, *s2;
570 : 48861807 : basic_block bb1, bb2;
571 : :
572 : 48861807 : if (e1 == e2)
573 : : return 1;
574 : :
575 : 47791567 : if (e1->hashval != e2->hashval)
576 : : return 0;
577 : :
578 : 7669893 : if (e1->succ_flags.length () != e2->succ_flags.length ())
579 : : return 0;
580 : :
581 : 2556631 : if (!bitmap_equal_p (e1->succs, e2->succs))
582 : : return 0;
583 : :
584 : 2429269 : if (!inverse_flags (e1, e2))
585 : : {
586 : 4538054 : for (i = 0; i < e1->succ_flags.length (); ++i)
587 : 2109572 : if (e1->succ_flags[i] != e2->succ_flags[i])
588 : : return 0;
589 : : }
590 : :
591 : 2429269 : first1 = bitmap_first_set_bit (e1->bbs);
592 : 2429269 : first2 = bitmap_first_set_bit (e2->bbs);
593 : :
594 : 2429269 : bb1 = BASIC_BLOCK_FOR_FN (cfun, first1);
595 : 2429269 : bb2 = BASIC_BLOCK_FOR_FN (cfun, first2);
596 : :
597 : 2429269 : if (BB_SIZE (bb1) != BB_SIZE (bb2))
598 : : return 0;
599 : :
600 : 2429269 : if (bb1->loop_father != bb2->loop_father)
601 : : return 0;
602 : :
603 : 2429269 : gsi1 = gsi_start_nondebug_bb (bb1);
604 : 2429269 : gsi2 = gsi_start_nondebug_bb (bb2);
605 : 2429269 : gsi_advance_fw_nondebug_nonlocal (&gsi1);
606 : 2429269 : gsi_advance_fw_nondebug_nonlocal (&gsi2);
607 : 6127126 : while (!(gsi_end_p (gsi1) || gsi_end_p (gsi2)))
608 : : {
609 : 1268655 : s1 = gsi_stmt (gsi1);
610 : 1268655 : s2 = gsi_stmt (gsi2);
611 : 1268655 : if (gimple_code (s1) != gimple_code (s2))
612 : : return 0;
613 : 1268655 : if (is_gimple_call (s1) && !gimple_call_same_target_p (s1, s2))
614 : : return 0;
615 : 1268588 : gsi_next_nondebug (&gsi1);
616 : 1268588 : gsi_next_nondebug (&gsi2);
617 : 1268588 : gsi_advance_fw_nondebug_nonlocal (&gsi1);
618 : 1268588 : 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 : 12038567 : same_succ_alloc (void)
628 : : {
629 : 12038567 : same_succ *same = XNEW (struct same_succ);
630 : :
631 : 12038567 : same->bbs = BITMAP_ALLOC (NULL);
632 : 12038567 : same->succs = BITMAP_ALLOC (NULL);
633 : 12038567 : same->inverse = BITMAP_ALLOC (NULL);
634 : 12038567 : same->succ_flags.create (10);
635 : 12038567 : same->in_worklist = false;
636 : :
637 : 12038567 : return same;
638 : : }
639 : :
640 : : /* Delete same_succ E. */
641 : :
642 : : void
643 : 12038567 : same_succ::remove (same_succ *e)
644 : : {
645 : 12038567 : BITMAP_FREE (e->bbs);
646 : 12038567 : BITMAP_FREE (e->succs);
647 : 12038567 : BITMAP_FREE (e->inverse);
648 : 12038567 : e->succ_flags.release ();
649 : :
650 : 12038567 : XDELETE (e);
651 : 12038567 : }
652 : :
653 : : /* Reset same_succ SAME. */
654 : :
655 : : static void
656 : 2429202 : same_succ_reset (same_succ *same)
657 : : {
658 : 2429202 : bitmap_clear (same->bbs);
659 : 2429202 : bitmap_clear (same->succs);
660 : 2429202 : bitmap_clear (same->inverse);
661 : 2429202 : same->succ_flags.truncate (0);
662 : 2429202 : }
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 : 14 : print_worklist (FILE *file)
697 : : {
698 : 14 : unsigned int i;
699 : 24 : for (i = 0; i < worklist.length (); ++i)
700 : 10 : same_succ_print (file, worklist[i]);
701 : 14 : }
702 : :
703 : : /* Adds SAME to worklist. */
704 : :
705 : : static void
706 : 13349713 : add_to_worklist (same_succ *same)
707 : : {
708 : 13349713 : if (same->in_worklist)
709 : : return;
710 : :
711 : 11971781 : if (bitmap_count_bits (same->bbs) < 2)
712 : : return;
713 : :
714 : 1051270 : same->in_worklist = true;
715 : 1051270 : worklist.safe_push (same);
716 : : }
717 : :
718 : : /* Add BB to same_succ_htab. */
719 : :
720 : : static void
721 : 13349713 : find_same_succ_bb (basic_block bb, same_succ **same_p)
722 : : {
723 : 13349713 : unsigned int j;
724 : 13349713 : bitmap_iterator bj;
725 : 13349713 : same_succ *same = *same_p;
726 : 13349713 : same_succ **slot;
727 : 13349713 : edge_iterator ei;
728 : 13349713 : edge e;
729 : :
730 : 13349713 : if (bb == NULL)
731 : 0 : return;
732 : 13349713 : bitmap_set_bit (same->bbs, bb->index);
733 : 31436723 : FOR_EACH_EDGE (e, ei, bb->succs)
734 : : {
735 : 18087010 : int index = e->dest->index;
736 : 18087010 : bitmap_set_bit (same->succs, index);
737 : 18087010 : same_succ_edge_flags[index] = (e->flags & ~ignore_edge_flags);
738 : : }
739 : 31436723 : EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
740 : 18087010 : same->succ_flags.safe_push (same_succ_edge_flags[j]);
741 : :
742 : 13349713 : same->hashval = same_succ_hash (same);
743 : :
744 : 13349713 : slot = same_succ_htab->find_slot_with_hash (same, same->hashval, INSERT);
745 : 13349713 : if (*slot == NULL)
746 : : {
747 : 10920511 : *slot = same;
748 : 10920511 : BB_SAME_SUCC (bb) = same;
749 : 10920511 : add_to_worklist (same);
750 : 10920511 : *same_p = NULL;
751 : : }
752 : : else
753 : : {
754 : 2429202 : bitmap_set_bit ((*slot)->bbs, bb->index);
755 : 2429202 : BB_SAME_SUCC (bb) = *slot;
756 : 2429202 : add_to_worklist (*slot);
757 : 2429202 : if (inverse_flags (same, *slot))
758 : 787 : bitmap_set_bit ((*slot)->inverse, bb->index);
759 : 2429202 : same_succ_reset (same);
760 : : }
761 : : }
762 : :
763 : : /* Find bbs with same successors. */
764 : :
765 : : static void
766 : 924251 : find_same_succ (void)
767 : : {
768 : 924251 : same_succ *same = same_succ_alloc ();
769 : 924251 : basic_block bb;
770 : :
771 : 13200237 : FOR_EACH_BB_FN (bb, cfun)
772 : : {
773 : 12275986 : find_same_succ_bb (bb, &same);
774 : 12275986 : if (same == NULL)
775 : 9899533 : same = same_succ_alloc ();
776 : : }
777 : :
778 : 924251 : same_succ::remove (same);
779 : 924251 : }
780 : :
781 : : /* Initializes worklist administration. */
782 : :
783 : : static void
784 : 924251 : init_worklist (void)
785 : : {
786 : 924251 : alloc_aux_for_blocks (sizeof (struct aux_bb_info));
787 : 924251 : same_succ_htab = new hash_table<same_succ> (n_basic_blocks_for_fn (cfun));
788 : 924251 : same_succ_edge_flags = XCNEWVEC (int, last_basic_block_for_fn (cfun));
789 : 924251 : deleted_bbs = BITMAP_ALLOC (NULL);
790 : 924251 : deleted_bb_preds = BITMAP_ALLOC (NULL);
791 : 924251 : worklist.create (n_basic_blocks_for_fn (cfun));
792 : 924251 : find_same_succ ();
793 : :
794 : 924251 : if (dump_file && (dump_flags & TDF_DETAILS))
795 : : {
796 : 14 : fprintf (dump_file, "initial worklist:\n");
797 : 14 : print_worklist (dump_file);
798 : : }
799 : 924251 : }
800 : :
801 : : /* Deletes worklist administration. */
802 : :
803 : : static void
804 : 924251 : delete_worklist (void)
805 : : {
806 : 924251 : free_aux_for_blocks ();
807 : 924251 : delete same_succ_htab;
808 : 924251 : same_succ_htab = NULL;
809 : 924251 : XDELETEVEC (same_succ_edge_flags);
810 : 924251 : same_succ_edge_flags = NULL;
811 : 924251 : BITMAP_FREE (deleted_bbs);
812 : 924251 : BITMAP_FREE (deleted_bb_preds);
813 : 924251 : worklist.release ();
814 : 924251 : }
815 : :
816 : : /* Mark BB as deleted, and mark its predecessors. */
817 : :
818 : : static void
819 : 1168538 : mark_basic_block_deleted (basic_block bb)
820 : : {
821 : 1168538 : edge e;
822 : 1168538 : edge_iterator ei;
823 : :
824 : 1168538 : bitmap_set_bit (deleted_bbs, bb->index);
825 : :
826 : 2459954 : FOR_EACH_EDGE (e, ei, bb->preds)
827 : 1291416 : bitmap_set_bit (deleted_bb_preds, e->src->index);
828 : 1168538 : }
829 : :
830 : : /* Removes BB from its corresponding same_succ. */
831 : :
832 : : static void
833 : 2242265 : same_succ_flush_bb (basic_block bb)
834 : : {
835 : 2242265 : same_succ *same = BB_SAME_SUCC (bb);
836 : 2242265 : if (! same)
837 : 0 : return;
838 : :
839 : 2242265 : BB_SAME_SUCC (bb) = NULL;
840 : 2242265 : if (bitmap_single_bit_set_p (same->bbs))
841 : 1070240 : same_succ_htab->remove_elt_with_hash (same, same->hashval);
842 : : else
843 : 1172025 : 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 : 193805 : same_succ_flush_bbs (bitmap bbs)
850 : : {
851 : 193805 : unsigned int i;
852 : 193805 : bitmap_iterator bi;
853 : :
854 : 1267532 : EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
855 : 1073727 : same_succ_flush_bb (BASIC_BLOCK_FOR_FN (cfun, i));
856 : 193805 : }
857 : :
858 : : /* Release the last vdef in BB, either normal or phi result. */
859 : :
860 : : static void
861 : 1168538 : release_last_vdef (basic_block bb)
862 : : {
863 : 2480765 : for (gimple_stmt_iterator i = gsi_last_bb (bb); !gsi_end_p (i);
864 : 143689 : gsi_prev_nondebug (&i))
865 : : {
866 : 375270 : gimple *stmt = gsi_stmt (i);
867 : 734824 : if (gimple_vdef (stmt) == NULL_TREE)
868 : 143689 : continue;
869 : :
870 : 231581 : mark_virtual_operand_for_renaming (gimple_vdef (stmt));
871 : 231581 : return;
872 : : }
873 : :
874 : 936957 : for (gphi_iterator i = gsi_start_phis (bb); !gsi_end_p (i);
875 : 0 : gsi_next (&i))
876 : : {
877 : 701 : gphi *phi = i.phi ();
878 : 701 : tree res = gimple_phi_result (phi);
879 : :
880 : 1402 : if (!virtual_operand_p (res))
881 : 0 : continue;
882 : :
883 : 701 : mark_virtual_phi_result_for_renaming (phi);
884 : 701 : return;
885 : : }
886 : : }
887 : :
888 : : /* For deleted_bb_preds, find bbs with same successors. */
889 : :
890 : : static void
891 : 193805 : update_worklist (void)
892 : : {
893 : 193805 : unsigned int i;
894 : 193805 : bitmap_iterator bi;
895 : 193805 : basic_block bb;
896 : 193805 : same_succ *same;
897 : :
898 : 193805 : bitmap_and_compl_into (deleted_bb_preds, deleted_bbs);
899 : 193805 : bitmap_clear (deleted_bbs);
900 : :
901 : 193805 : bitmap_clear_bit (deleted_bb_preds, ENTRY_BLOCK);
902 : 193805 : same_succ_flush_bbs (deleted_bb_preds);
903 : :
904 : 193805 : same = same_succ_alloc ();
905 : 1267532 : EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds, 0, i, bi)
906 : : {
907 : 1073727 : bb = BASIC_BLOCK_FOR_FN (cfun, i);
908 : 1073727 : gcc_assert (bb != NULL);
909 : 1073727 : find_same_succ_bb (bb, &same);
910 : 1073727 : if (same == NULL)
911 : 1020978 : same = same_succ_alloc ();
912 : : }
913 : 193805 : same_succ::remove (same);
914 : 193805 : bitmap_clear (deleted_bb_preds);
915 : 193805 : }
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 : 1738081 : update_rep_bb (bb_cluster *c, basic_block bb)
941 : : {
942 : : /* Initial. */
943 : 1738081 : if (c->rep_bb == NULL)
944 : : {
945 : 569543 : c->rep_bb = bb;
946 : 569543 : return;
947 : : }
948 : :
949 : : /* Current needs no deps, keep it. */
950 : 1168538 : if (BB_DEP_BB (c->rep_bb) == NULL)
951 : : return;
952 : :
953 : : /* Bb needs no deps, change rep_bb. */
954 : 17181 : if (BB_DEP_BB (bb) == NULL)
955 : : {
956 : 182 : c->rep_bb = bb;
957 : 182 : 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 : 16999 : if (dominated_by_p (CDI_DOMINATORS, BB_DEP_BB (c->rep_bb), BB_DEP_BB (bb)))
968 : 16664 : 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 : 1738081 : add_bb_to_cluster (bb_cluster *c, basic_block bb)
975 : : {
976 : 1738081 : edge e;
977 : 1738081 : edge_iterator ei;
978 : :
979 : 1738081 : bitmap_set_bit (c->bbs, bb->index);
980 : :
981 : 3752808 : FOR_EACH_EDGE (e, ei, bb->preds)
982 : 2014727 : bitmap_set_bit (c->preds, e->src->index);
983 : :
984 : 1738081 : update_rep_bb (c, bb);
985 : 1738081 : }
986 : :
987 : : /* Allocate and init new cluster. */
988 : :
989 : : static bb_cluster *
990 : 569543 : new_cluster (void)
991 : : {
992 : 569543 : bb_cluster *c;
993 : 569543 : c = XCNEW (bb_cluster);
994 : 569543 : c->bbs = BITMAP_ALLOC (NULL);
995 : 569543 : c->preds = BITMAP_ALLOC (NULL);
996 : 569543 : c->rep_bb = NULL;
997 : 569543 : return c;
998 : : }
999 : :
1000 : : /* Delete clusters. */
1001 : :
1002 : : static void
1003 : 569543 : delete_cluster (bb_cluster *c)
1004 : : {
1005 : 569543 : if (c == NULL)
1006 : : return;
1007 : 569543 : BITMAP_FREE (c->bbs);
1008 : 569543 : BITMAP_FREE (c->preds);
1009 : 569543 : 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 : 248871 : alloc_cluster_vectors (void)
1021 : : {
1022 : 248871 : all_clusters.create (n_basic_blocks_for_fn (cfun));
1023 : 248871 : }
1024 : :
1025 : : /* Reset all cluster vectors. */
1026 : :
1027 : : static void
1028 : 11701 : reset_cluster_vectors (void)
1029 : : {
1030 : 11701 : unsigned int i;
1031 : 11701 : basic_block bb;
1032 : 126638 : for (i = 0; i < all_clusters.length (); ++i)
1033 : 114937 : delete_cluster (all_clusters[i]);
1034 : 11701 : all_clusters.truncate (0);
1035 : 1248329 : FOR_EACH_BB_FN (bb, cfun)
1036 : 1236628 : BB_CLUSTER (bb) = NULL;
1037 : 11701 : }
1038 : :
1039 : : /* Delete all cluster vectors. */
1040 : :
1041 : : static void
1042 : 248871 : delete_cluster_vectors (void)
1043 : : {
1044 : 248871 : unsigned int i;
1045 : 703477 : for (i = 0; i < all_clusters.length (); ++i)
1046 : 454606 : delete_cluster (all_clusters[i]);
1047 : 248871 : all_clusters.release ();
1048 : 248871 : }
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 : 1168538 : set_cluster (basic_block bb1, basic_block bb2)
1064 : : {
1065 : 1168538 : basic_block merge_bb, other_bb;
1066 : 1168538 : bb_cluster *merge, *old, *c;
1067 : :
1068 : 1168538 : if (BB_CLUSTER (bb1) == NULL && BB_CLUSTER (bb2) == NULL)
1069 : : {
1070 : 569543 : c = new_cluster ();
1071 : 569543 : add_bb_to_cluster (c, bb1);
1072 : 569543 : add_bb_to_cluster (c, bb2);
1073 : 569543 : BB_CLUSTER (bb1) = c;
1074 : 569543 : BB_CLUSTER (bb2) = c;
1075 : 569543 : c->index = all_clusters.length ();
1076 : 569543 : all_clusters.safe_push (c);
1077 : : }
1078 : 598995 : else if (BB_CLUSTER (bb1) == NULL || BB_CLUSTER (bb2) == NULL)
1079 : : {
1080 : 598995 : merge_bb = BB_CLUSTER (bb1) == NULL ? bb2 : bb1;
1081 : 598995 : other_bb = BB_CLUSTER (bb1) == NULL ? bb1 : bb2;
1082 : 598995 : merge = BB_CLUSTER (merge_bb);
1083 : 598995 : add_bb_to_cluster (merge, other_bb);
1084 : 598995 : 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 : 1168538 : }
1103 : :
1104 : : /* Return true if gimple operands T1 and T2 have the same value. */
1105 : :
1106 : : static bool
1107 : 775514 : gimple_operand_equal_value_p (tree t1, tree t2)
1108 : : {
1109 : 775514 : if (t1 == t2)
1110 : : return true;
1111 : :
1112 : 184826 : if (t1 == NULL_TREE
1113 : 184826 : || t2 == NULL_TREE)
1114 : : return false;
1115 : :
1116 : 184826 : if (operand_equal_p (t1, t2, OEP_MATCH_SIDE_EFFECTS))
1117 : : return true;
1118 : :
1119 : 57378 : 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 : 511149 : gimple_equal_p (same_succ *same_succ, gimple *s1, gimple *s2)
1127 : : {
1128 : 511149 : unsigned int i;
1129 : 511149 : tree lhs1, lhs2;
1130 : 511149 : basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
1131 : 511149 : tree t1, t2;
1132 : 511149 : bool inv_cond;
1133 : 511149 : enum tree_code code1, code2;
1134 : :
1135 : 511149 : if (gimple_code (s1) != gimple_code (s2))
1136 : : return false;
1137 : :
1138 : 511149 : switch (gimple_code (s1))
1139 : : {
1140 : 391851 : case GIMPLE_CALL:
1141 : 391851 : if (!gimple_call_same_target_p (s1, s2))
1142 : : return false;
1143 : :
1144 : 391851 : t1 = gimple_call_chain (s1);
1145 : 391851 : t2 = gimple_call_chain (s2);
1146 : 391851 : if (!gimple_operand_equal_value_p (t1, t2))
1147 : : return false;
1148 : :
1149 : 391851 : if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
1150 : : return false;
1151 : :
1152 : 671081 : for (i = 0; i < gimple_call_num_args (s1); ++i)
1153 : : {
1154 : 279238 : t1 = gimple_call_arg (s1, i);
1155 : 279238 : t2 = gimple_call_arg (s2, i);
1156 : 279238 : if (!gimple_operand_equal_value_p (t1, t2))
1157 : : return false;
1158 : : }
1159 : :
1160 : 391843 : lhs1 = gimple_get_lhs (s1);
1161 : 391843 : lhs2 = gimple_get_lhs (s2);
1162 : 391843 : if (lhs1 == NULL_TREE && lhs2 == NULL_TREE)
1163 : : return true;
1164 : 3698 : if (lhs1 == NULL_TREE || lhs2 == NULL_TREE)
1165 : : return false;
1166 : 3698 : if (TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME)
1167 : 3544 : return tail_merge_valueize (lhs1) == tail_merge_valueize (lhs2);
1168 : 154 : return operand_equal_p (lhs1, lhs2, 0);
1169 : :
1170 : 109752 : case GIMPLE_ASSIGN:
1171 : 109752 : if (gimple_assign_rhs_code (s1) != gimple_assign_rhs_code (s2))
1172 : : return false;
1173 : :
1174 : 109752 : lhs1 = gimple_get_lhs (s1);
1175 : 109752 : lhs2 = gimple_get_lhs (s2);
1176 : 109752 : if (TREE_CODE (lhs1) != SSA_NAME
1177 : 92475 : && TREE_CODE (lhs2) != SSA_NAME)
1178 : 92403 : return (operand_equal_p (lhs1, lhs2, 0)
1179 : 92403 : && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1),
1180 : : gimple_assign_rhs1 (s2)));
1181 : :
1182 : 17349 : if (TREE_CODE (lhs1) != SSA_NAME
1183 : 17277 : || TREE_CODE (lhs2) != SSA_NAME)
1184 : : return false;
1185 : :
1186 : 17277 : gcc_checking_assert (gimple_num_args (s1) == gimple_num_args (s2));
1187 : 34432 : for (i = 0; i < gimple_num_args (s1); ++i)
1188 : : {
1189 : 17437 : t1 = gimple_arg (s1, i);
1190 : 17437 : t2 = gimple_arg (s2, i);
1191 : 38105 : while (handled_component_p (t1) && handled_component_p (t2))
1192 : : {
1193 : 3440 : if (TREE_CODE (t1) != TREE_CODE (t2)
1194 : 3440 : || TREE_THIS_VOLATILE (t1) != TREE_THIS_VOLATILE (t2))
1195 : : return false;
1196 : 3440 : switch (TREE_CODE (t1))
1197 : : {
1198 : 3366 : case COMPONENT_REF:
1199 : 3366 : if (TREE_OPERAND (t1, 1) != TREE_OPERAND (t2, 1)
1200 : 6523 : || !gimple_operand_equal_value_p (TREE_OPERAND (t1, 2),
1201 : 3157 : TREE_OPERAND (t2, 2)))
1202 : 209 : return false;
1203 : : break;
1204 : 54 : case ARRAY_REF:
1205 : 54 : case ARRAY_RANGE_REF:
1206 : 54 : if (!gimple_operand_equal_value_p (TREE_OPERAND (t1, 3),
1207 : 54 : TREE_OPERAND (t2, 3)))
1208 : : return false;
1209 : : /* Fallthru. */
1210 : 74 : case BIT_FIELD_REF:
1211 : 74 : if (!gimple_operand_equal_value_p (TREE_OPERAND (t1, 1),
1212 : 74 : TREE_OPERAND (t2, 1))
1213 : 148 : || !gimple_operand_equal_value_p (TREE_OPERAND (t1, 2),
1214 : 74 : TREE_OPERAND (t2, 2)))
1215 : 0 : return false;
1216 : : break;
1217 : : case REALPART_EXPR:
1218 : : case IMAGPART_EXPR:
1219 : : case VIEW_CONVERT_EXPR:
1220 : : break;
1221 : : default:
1222 : : gcc_unreachable ();
1223 : : }
1224 : 3231 : t1 = TREE_OPERAND (t1, 0);
1225 : 3231 : t2 = TREE_OPERAND (t2, 0);
1226 : : }
1227 : 17228 : if (TREE_CODE (t1) == MEM_REF && TREE_CODE (t2) == MEM_REF)
1228 : : {
1229 : 6313 : if (TREE_THIS_VOLATILE (t1) != TREE_THIS_VOLATILE (t2)
1230 : 6313 : || TYPE_ALIGN (TREE_TYPE (t1)) != TYPE_ALIGN (TREE_TYPE (t2))
1231 : 6313 : || !gimple_operand_equal_value_p (TREE_OPERAND (t1, 0),
1232 : 6313 : TREE_OPERAND (t2, 0))
1233 : 12626 : || TREE_OPERAND (t1, 1) != TREE_OPERAND (t2, 1))
1234 : 55 : return false;
1235 : : }
1236 : 10915 : else if (!gimple_operand_equal_value_p (t1, t2))
1237 : : return false;
1238 : : }
1239 : : return true;
1240 : :
1241 : 4315 : case GIMPLE_COND:
1242 : 4315 : t1 = gimple_cond_lhs (s1);
1243 : 4315 : t2 = gimple_cond_lhs (s2);
1244 : 4315 : if (!gimple_operand_equal_value_p (t1, t2))
1245 : : return false;
1246 : :
1247 : 1551 : t1 = gimple_cond_rhs (s1);
1248 : 1551 : t2 = gimple_cond_rhs (s2);
1249 : 1551 : if (!gimple_operand_equal_value_p (t1, t2))
1250 : : return false;
1251 : :
1252 : 843 : code1 = gimple_cond_code (s1);
1253 : 843 : code2 = gimple_cond_code (s2);
1254 : 843 : inv_cond = (bitmap_bit_p (same_succ->inverse, bb1->index)
1255 : 843 : != bitmap_bit_p (same_succ->inverse, bb2->index));
1256 : 843 : if (inv_cond)
1257 : : {
1258 : 23 : bool honor_nans = HONOR_NANS (t1);
1259 : 23 : code2 = invert_tree_comparison (code2, honor_nans);
1260 : : }
1261 : 843 : return code1 == code2;
1262 : :
1263 : : default:
1264 : : return false;
1265 : : }
1266 : : }
1267 : :
1268 : : /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
1269 : : Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
1270 : : processed statements. */
1271 : :
1272 : : static void
1273 : 3374814 : gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse,
1274 : : bool *vuse_escaped)
1275 : : {
1276 : 3381643 : gimple *stmt;
1277 : 3381643 : tree lvuse;
1278 : :
1279 : 3388472 : while (true)
1280 : : {
1281 : 3381643 : if (gsi_end_p (*gsi))
1282 : : return;
1283 : 1055335 : stmt = gsi_stmt (*gsi);
1284 : :
1285 : 1055335 : lvuse = gimple_vuse (stmt);
1286 : 1014293 : if (lvuse != NULL_TREE)
1287 : : {
1288 : 772662 : *vuse = lvuse;
1289 : 772662 : if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_DEF))
1290 : 41172 : *vuse_escaped = true;
1291 : : }
1292 : :
1293 : 1055335 : if (!stmt_local_def (stmt))
1294 : : return;
1295 : 6829 : gsi_prev_nondebug (gsi);
1296 : : }
1297 : : }
1298 : :
1299 : : /* Return true if equal (in the sense of gimple_equal_p) statements STMT1 and
1300 : : STMT2 are allowed to be merged. */
1301 : :
1302 : : static bool
1303 : 448751 : merge_stmts_p (gimple *stmt1, gimple *stmt2)
1304 : : {
1305 : : /* What could be better than this here is to blacklist the bb
1306 : : containing the stmt, when encountering the stmt f.i. in
1307 : : same_succ_hash. */
1308 : 448751 : if (is_tm_ending (stmt1))
1309 : : return false;
1310 : :
1311 : : /* Verify EH landing pads. */
1312 : 448699 : if (lookup_stmt_eh_lp_fn (cfun, stmt1) != lookup_stmt_eh_lp_fn (cfun, stmt2))
1313 : : return false;
1314 : :
1315 : 441222 : if (is_gimple_call (stmt1)
1316 : 441222 : && gimple_call_internal_p (stmt1))
1317 : 31 : switch (gimple_call_internal_fn (stmt1))
1318 : : {
1319 : 0 : case IFN_UBSAN_NULL:
1320 : 0 : case IFN_UBSAN_BOUNDS:
1321 : 0 : case IFN_UBSAN_VPTR:
1322 : 0 : case IFN_UBSAN_CHECK_ADD:
1323 : 0 : case IFN_UBSAN_CHECK_SUB:
1324 : 0 : case IFN_UBSAN_CHECK_MUL:
1325 : 0 : case IFN_UBSAN_OBJECT_SIZE:
1326 : 0 : case IFN_UBSAN_PTR:
1327 : 0 : case IFN_ASAN_CHECK:
1328 : : /* For these internal functions, gimple_location is an implicit
1329 : : parameter, which will be used explicitly after expansion.
1330 : : Merging these statements may cause confusing line numbers in
1331 : : sanitizer messages. */
1332 : 0 : return gimple_location (stmt1) == gimple_location (stmt2);
1333 : : default:
1334 : : break;
1335 : : }
1336 : :
1337 : : return true;
1338 : : }
1339 : :
1340 : : /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
1341 : : clusters them. */
1342 : :
1343 : : static void
1344 : 1246185 : find_duplicate (same_succ *same_succ, basic_block bb1, basic_block bb2)
1345 : : {
1346 : 1246185 : gimple_stmt_iterator gsi1 = gsi_last_nondebug_bb (bb1);
1347 : 1246185 : gimple_stmt_iterator gsi2 = gsi_last_nondebug_bb (bb2);
1348 : 1246185 : tree vuse1 = NULL_TREE, vuse2 = NULL_TREE;
1349 : 1246185 : bool vuse_escaped = false;
1350 : :
1351 : 1246185 : gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
1352 : 1246185 : gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
1353 : :
1354 : 2933592 : while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2))
1355 : : {
1356 : 524253 : gimple *stmt1 = gsi_stmt (gsi1);
1357 : 524253 : gimple *stmt2 = gsi_stmt (gsi2);
1358 : :
1359 : 524253 : if (gimple_code (stmt1) == GIMPLE_LABEL
1360 : 524253 : && gimple_code (stmt2) == GIMPLE_LABEL)
1361 : : break;
1362 : :
1363 : 511149 : if (!gimple_equal_p (same_succ, stmt1, stmt2))
1364 : 77647 : return;
1365 : :
1366 : 448751 : if (!merge_stmts_p (stmt1, stmt2))
1367 : : return;
1368 : :
1369 : 441222 : gsi_prev_nondebug (&gsi1);
1370 : 441222 : gsi_prev_nondebug (&gsi2);
1371 : 441222 : gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
1372 : 441222 : gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
1373 : : }
1374 : :
1375 : 13105 : while (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
1376 : : {
1377 : 13105 : tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1)));
1378 : 26210 : if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
1379 : : return;
1380 : 1202420 : gsi_prev (&gsi1);
1381 : : }
1382 : 13081 : while (!gsi_end_p (gsi2) && gimple_code (gsi_stmt (gsi2)) == GIMPLE_LABEL)
1383 : : {
1384 : 13081 : tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi2)));
1385 : 26162 : if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
1386 : : return;
1387 : 1202396 : gsi_prev (&gsi2);
1388 : : }
1389 : 1176234 : if (!(gsi_end_p (gsi1) && gsi_end_p (gsi2)))
1390 : 0 : return;
1391 : :
1392 : : /* If the incoming vuses are not the same, and the vuse escaped into an
1393 : : SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
1394 : : which potentially means the semantics of one of the blocks will be changed.
1395 : : TODO: make this check more precise. */
1396 : 1176234 : if (vuse_escaped && vuse1 != vuse2)
1397 : : return;
1398 : :
1399 : 1168538 : if (dump_file)
1400 : 26 : fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
1401 : : bb1->index, bb2->index);
1402 : :
1403 : 1168538 : set_cluster (bb1, bb2);
1404 : : }
1405 : :
1406 : : /* Returns whether for all phis in DEST the phi alternatives for E1 and
1407 : : E2 are equal. */
1408 : :
1409 : : static bool
1410 : 2038925 : same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
1411 : : {
1412 : 2038925 : int n1 = e1->dest_idx, n2 = e2->dest_idx;
1413 : 2038925 : gphi_iterator gsi;
1414 : :
1415 : 2790293 : for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
1416 : : {
1417 : 1874174 : gphi *phi = gsi.phi ();
1418 : 1874174 : tree lhs = gimple_phi_result (phi);
1419 : 1874174 : tree val1 = gimple_phi_arg_def (phi, n1);
1420 : 1874174 : tree val2 = gimple_phi_arg_def (phi, n2);
1421 : :
1422 : 3748348 : if (virtual_operand_p (lhs))
1423 : 536247 : continue;
1424 : :
1425 : 1337927 : if (operand_equal_for_phi_arg_p (val1, val2))
1426 : 203080 : continue;
1427 : 1134847 : if (gvn_uses_equal (val1, val2))
1428 : 12041 : continue;
1429 : :
1430 : : return false;
1431 : : }
1432 : :
1433 : : return true;
1434 : : }
1435 : :
1436 : : /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
1437 : : phi alternatives for BB1 and BB2 are equal. */
1438 : :
1439 : : static bool
1440 : 2368991 : same_phi_alternatives (same_succ *same_succ, basic_block bb1, basic_block bb2)
1441 : : {
1442 : 2368991 : unsigned int s;
1443 : 2368991 : bitmap_iterator bs;
1444 : 2368991 : edge e1, e2;
1445 : 2368991 : basic_block succ;
1446 : :
1447 : 3285110 : EXECUTE_IF_SET_IN_BITMAP (same_succ->succs, 0, s, bs)
1448 : : {
1449 : 2038925 : succ = BASIC_BLOCK_FOR_FN (cfun, s);
1450 : 2038925 : e1 = find_edge (bb1, succ);
1451 : 2038925 : e2 = find_edge (bb2, succ);
1452 : 2038925 : if (e1->flags & EDGE_COMPLEX
1453 : 2038925 : || e2->flags & EDGE_COMPLEX)
1454 : : return false;
1455 : :
1456 : : /* For all phis in bb, the phi alternatives for e1 and e2 need to have
1457 : : the same value. */
1458 : 2038925 : if (!same_phi_alternatives_1 (succ, e1, e2))
1459 : : return false;
1460 : : }
1461 : :
1462 : : return true;
1463 : : }
1464 : :
1465 : : /* Return true if BB has non-vop phis. */
1466 : :
1467 : : static bool
1468 : 19347872 : bb_has_non_vop_phi (basic_block bb)
1469 : : {
1470 : 19347872 : gimple_seq phis = phi_nodes (bb);
1471 : 19347872 : gimple *phi;
1472 : :
1473 : 19347872 : if (phis == NULL)
1474 : : return false;
1475 : :
1476 : 142361 : if (!gimple_seq_singleton_p (phis))
1477 : : return true;
1478 : :
1479 : 105327 : phi = gimple_seq_first_stmt (phis);
1480 : 210654 : return !virtual_operand_p (gimple_phi_result (phi));
1481 : : }
1482 : :
1483 : : /* Returns true if redirecting the incoming edges of FROM to TO maintains the
1484 : : invariant that uses in FROM are dominates by their defs. */
1485 : :
1486 : : static bool
1487 : 3896466 : deps_ok_for_redirect_from_bb_to_bb (basic_block from, basic_block to)
1488 : : {
1489 : 3896466 : basic_block cd, dep_bb = BB_DEP_BB (to);
1490 : 3896466 : edge_iterator ei;
1491 : 3896466 : edge e;
1492 : :
1493 : 3896466 : if (dep_bb == NULL)
1494 : : return true;
1495 : :
1496 : 1844309 : bitmap from_preds = BITMAP_ALLOC (NULL);
1497 : 3730468 : FOR_EACH_EDGE (e, ei, from->preds)
1498 : 1886159 : bitmap_set_bit (from_preds, e->src->index);
1499 : 1844309 : cd = nearest_common_dominator_for_set (CDI_DOMINATORS, from_preds);
1500 : 1844309 : BITMAP_FREE (from_preds);
1501 : :
1502 : 1844309 : return dominated_by_p (CDI_DOMINATORS, dep_bb, cd);
1503 : : }
1504 : :
1505 : : /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
1506 : : replacement bb) and vice versa maintains the invariant that uses in the
1507 : : replacement are dominates by their defs. */
1508 : :
1509 : : static bool
1510 : 3103388 : deps_ok_for_redirect (basic_block &bb1, basic_block &bb2)
1511 : : {
1512 : 3103388 : basic_block b1 = bb1;
1513 : 3103388 : basic_block b2 = bb2;
1514 : 3103388 : if (BB_CLUSTER (b1) != NULL)
1515 : 904402 : b1 = BB_CLUSTER (b1)->rep_bb;
1516 : :
1517 : 3103388 : if (BB_CLUSTER (b2) != NULL)
1518 : 89521 : b2 = BB_CLUSTER (b2)->rep_bb;
1519 : :
1520 : 3103388 : if (deps_ok_for_redirect_from_bb_to_bb (b1, b2))
1521 : : return true;
1522 : 793078 : if (deps_ok_for_redirect_from_bb_to_bb (b2, b1))
1523 : : {
1524 : 58681 : std::swap (bb1, bb2);
1525 : 58681 : return true;
1526 : : }
1527 : : return false;
1528 : : }
1529 : :
1530 : : /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
1531 : :
1532 : : static void
1533 : 1051270 : find_clusters_1 (same_succ *same_succ)
1534 : : {
1535 : 1051270 : basic_block bb1, bb2;
1536 : 1051270 : unsigned int i, j;
1537 : 1051270 : bitmap_iterator bi, bj;
1538 : 1051270 : int nr_comparisons;
1539 : 1051270 : int max_comparisons = param_max_tail_merge_comparisons;
1540 : :
1541 : 4534245 : EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, 0, i, bi)
1542 : : {
1543 : 3482975 : bb1 = BASIC_BLOCK_FOR_FN (cfun, i);
1544 : :
1545 : : /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
1546 : : phi-nodes in bb1 and bb2, with the same alternatives for the same
1547 : : preds. */
1548 : 6931213 : if (bb_has_non_vop_phi (bb1) || bb_has_eh_pred (bb1)
1549 : 6263267 : || bb_has_abnormal_pred (bb1))
1550 : 702801 : continue;
1551 : :
1552 : 2780174 : nr_comparisons = 0;
1553 : 18533291 : EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, i + 1, j, bj)
1554 : : {
1555 : 15864897 : bb2 = BASIC_BLOCK_FOR_FN (cfun, j);
1556 : :
1557 : 31710041 : if (bb_has_non_vop_phi (bb2) || bb_has_eh_pred (bb2)
1558 : 31709741 : || bb_has_abnormal_pred (bb2))
1559 : 20053 : continue;
1560 : :
1561 : 15844844 : if (BB_CLUSTER (bb1) != NULL && BB_CLUSTER (bb1) == BB_CLUSTER (bb2))
1562 : 12629676 : continue;
1563 : :
1564 : : /* Limit quadratic behavior. */
1565 : 3215168 : nr_comparisons++;
1566 : 3215168 : if (nr_comparisons > max_comparisons)
1567 : : break;
1568 : :
1569 : : /* This is a conservative dependency check. We could test more
1570 : : precise for allowed replacement direction. */
1571 : 3103388 : if (!deps_ok_for_redirect (bb1, bb2))
1572 : 734397 : continue;
1573 : :
1574 : 2368991 : if (!(same_phi_alternatives (same_succ, bb1, bb2)))
1575 : 1122806 : continue;
1576 : :
1577 : 1246185 : find_duplicate (same_succ, bb1, bb2);
1578 : : }
1579 : : }
1580 : 1051270 : }
1581 : :
1582 : : /* Find clusters of bbs which can be merged. */
1583 : :
1584 : : static void
1585 : 260572 : find_clusters (void)
1586 : : {
1587 : 260572 : same_succ *same;
1588 : :
1589 : 1311842 : while (!worklist.is_empty ())
1590 : : {
1591 : 1051270 : same = worklist.pop ();
1592 : 1051270 : same->in_worklist = false;
1593 : 81 : if (dump_file && (dump_flags & TDF_DETAILS))
1594 : : {
1595 : 10 : fprintf (dump_file, "processing worklist entry\n");
1596 : 10 : same_succ_print (dump_file, same);
1597 : : }
1598 : 1051270 : find_clusters_1 (same);
1599 : : }
1600 : 260572 : }
1601 : :
1602 : : /* Returns the vop phi of BB, if any. */
1603 : :
1604 : : static gphi *
1605 : 1194378 : vop_phi (basic_block bb)
1606 : : {
1607 : 1194378 : gphi *stmt;
1608 : 1194378 : gphi_iterator gsi;
1609 : 1194378 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1610 : : {
1611 : 44867 : stmt = gsi.phi ();
1612 : 89734 : if (! virtual_operand_p (gimple_phi_result (stmt)))
1613 : 0 : continue;
1614 : : return stmt;
1615 : : }
1616 : : return NULL;
1617 : : }
1618 : :
1619 : : /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
1620 : :
1621 : : static void
1622 : 1168538 : replace_block_by (basic_block bb1, basic_block bb2)
1623 : : {
1624 : 1168538 : edge pred_edge;
1625 : 1168538 : unsigned int i;
1626 : 1168538 : gphi *bb2_phi;
1627 : :
1628 : 1168538 : bb2_phi = vop_phi (bb2);
1629 : :
1630 : : /* Mark the basic block as deleted. */
1631 : 1168538 : mark_basic_block_deleted (bb1);
1632 : :
1633 : : /* Redirect the incoming edges of bb1 to bb2. */
1634 : 3628492 : for (i = EDGE_COUNT (bb1->preds); i > 0 ; --i)
1635 : : {
1636 : 1291416 : pred_edge = EDGE_PRED (bb1, i - 1);
1637 : 1291416 : pred_edge = redirect_edge_and_branch (pred_edge, bb2);
1638 : 1291416 : gcc_assert (pred_edge != NULL);
1639 : :
1640 : 1291416 : if (bb2_phi == NULL)
1641 : 1265576 : continue;
1642 : :
1643 : : /* The phi might have run out of capacity when the redirect added an
1644 : : argument, which means it could have been replaced. Refresh it. */
1645 : 25840 : bb2_phi = vop_phi (bb2);
1646 : :
1647 : 25840 : add_phi_arg (bb2_phi, SSA_NAME_VAR (gimple_phi_result (bb2_phi)),
1648 : : pred_edge, UNKNOWN_LOCATION);
1649 : : }
1650 : :
1651 : :
1652 : : /* Merge the outgoing edge counts from bb1 onto bb2. */
1653 : 1168538 : edge e1, e2;
1654 : 1168538 : edge_iterator ei;
1655 : :
1656 : 1168538 : if (bb2->count.initialized_p ())
1657 : 2020518 : FOR_EACH_EDGE (e1, ei, bb1->succs)
1658 : : {
1659 : 852069 : e2 = find_edge (bb2, e1->dest);
1660 : 852069 : gcc_assert (e2);
1661 : :
1662 : : /* If probabilities are same, we are done.
1663 : : If counts are nonzero we can distribute accordingly. In remaining
1664 : : cases just average the values and hope for the best. */
1665 : 852069 : e2->probability = e1->probability.combine_with_count
1666 : 852069 : (bb1->count, e2->probability, bb2->count);
1667 : : }
1668 : 1168538 : bb2->count += bb1->count;
1669 : :
1670 : : /* Move over any user labels from bb1 after the bb2 labels. */
1671 : 1168538 : gimple_stmt_iterator gsi1 = gsi_start_bb (bb1);
1672 : 1168538 : if (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
1673 : : {
1674 : 13078 : gimple_stmt_iterator gsi2 = gsi_after_labels (bb2);
1675 : 26157 : while (!gsi_end_p (gsi1)
1676 : 26157 : && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
1677 : : {
1678 : 13079 : tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1)));
1679 : 26158 : gcc_assert (!DECL_NONLOCAL (label) && !FORCED_LABEL (label));
1680 : 13079 : if (DECL_ARTIFICIAL (label))
1681 : 12722 : gsi_next (&gsi1);
1682 : : else
1683 : 357 : gsi_move_before (&gsi1, &gsi2);
1684 : : }
1685 : : }
1686 : :
1687 : : /* Clear range info from all stmts in BB2 -- this transformation
1688 : : could make them out of date. */
1689 : 1168538 : reset_flow_sensitive_info_in_bb (bb2);
1690 : :
1691 : : /* Do updates that use bb1, before deleting bb1. */
1692 : 1168538 : release_last_vdef (bb1);
1693 : 1168538 : same_succ_flush_bb (bb1);
1694 : :
1695 : 1168538 : delete_basic_block (bb1);
1696 : 1168538 : }
1697 : :
1698 : : /* Bbs for which update_debug_stmt need to be called. */
1699 : :
1700 : : static bitmap update_bbs;
1701 : :
1702 : : /* For each cluster in all_clusters, merge all cluster->bbs. Returns
1703 : : number of bbs removed. */
1704 : :
1705 : : static int
1706 : 200585 : apply_clusters (void)
1707 : : {
1708 : 200585 : basic_block bb1, bb2;
1709 : 200585 : bb_cluster *c;
1710 : 200585 : unsigned int i, j;
1711 : 200585 : bitmap_iterator bj;
1712 : 200585 : int nr_bbs_removed = 0;
1713 : :
1714 : 770128 : for (i = 0; i < all_clusters.length (); ++i)
1715 : : {
1716 : 569543 : c = all_clusters[i];
1717 : 569543 : if (c == NULL)
1718 : 0 : continue;
1719 : :
1720 : 569543 : bb2 = c->rep_bb;
1721 : 569543 : bitmap_set_bit (update_bbs, bb2->index);
1722 : :
1723 : 569543 : bitmap_clear_bit (c->bbs, bb2->index);
1724 : 1738081 : EXECUTE_IF_SET_IN_BITMAP (c->bbs, 0, j, bj)
1725 : : {
1726 : 1168538 : bb1 = BASIC_BLOCK_FOR_FN (cfun, j);
1727 : 1168538 : bitmap_clear_bit (update_bbs, bb1->index);
1728 : :
1729 : 1168538 : replace_block_by (bb1, bb2);
1730 : 1168538 : nr_bbs_removed++;
1731 : : }
1732 : : }
1733 : :
1734 : 200585 : return nr_bbs_removed;
1735 : : }
1736 : :
1737 : : /* Resets debug statement STMT if it has uses that are not dominated by their
1738 : : defs. */
1739 : :
1740 : : static void
1741 : 185058 : update_debug_stmt (gimple *stmt)
1742 : : {
1743 : 185058 : use_operand_p use_p;
1744 : 185058 : ssa_op_iter oi;
1745 : 185058 : basic_block bbuse;
1746 : :
1747 : 185058 : if (!gimple_debug_bind_p (stmt))
1748 : 29578 : return;
1749 : :
1750 : 155480 : bbuse = gimple_bb (stmt);
1751 : 160118 : FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
1752 : : {
1753 : 5611 : tree name = USE_FROM_PTR (use_p);
1754 : 5611 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1755 : 5611 : basic_block bbdef = gimple_bb (def_stmt);
1756 : 10249 : if (bbdef == NULL || bbuse == bbdef
1757 : 5611 : || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef))
1758 : 4638 : continue;
1759 : :
1760 : 973 : gimple_debug_bind_reset_value (stmt);
1761 : 973 : update_stmt (stmt);
1762 : 973 : break;
1763 : : }
1764 : : }
1765 : :
1766 : : /* Resets all debug statements that have uses that are not
1767 : : dominated by their defs. */
1768 : :
1769 : : static void
1770 : 131251 : update_debug_stmts (void)
1771 : : {
1772 : 131251 : basic_block bb;
1773 : 131251 : bitmap_iterator bi;
1774 : 131251 : unsigned int i;
1775 : :
1776 : 534841 : EXECUTE_IF_SET_IN_BITMAP (update_bbs, 0, i, bi)
1777 : : {
1778 : 403590 : gimple *stmt;
1779 : 403590 : gimple_stmt_iterator gsi;
1780 : :
1781 : 403590 : bb = BASIC_BLOCK_FOR_FN (cfun, i);
1782 : 1065158 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1783 : : {
1784 : 257978 : stmt = gsi_stmt (gsi);
1785 : 257978 : if (!is_gimple_debug (stmt))
1786 : 72920 : continue;
1787 : 185058 : update_debug_stmt (stmt);
1788 : : }
1789 : : }
1790 : 131251 : }
1791 : :
1792 : : /* Runs tail merge optimization. */
1793 : :
1794 : : unsigned int
1795 : 924294 : tail_merge_optimize (bool need_crit_edge_split)
1796 : : {
1797 : 924294 : int nr_bbs_removed_total = 0;
1798 : 924294 : int nr_bbs_removed;
1799 : 924294 : bool loop_entered = false;
1800 : 924294 : int iteration_nr = 0;
1801 : 924294 : int max_iterations = param_max_tail_merge_iterations;
1802 : :
1803 : 924294 : if (!flag_tree_tail_merge
1804 : 924251 : || max_iterations == 0)
1805 : : return 0;
1806 : :
1807 : 924251 : timevar_push (TV_TREE_TAIL_MERGE);
1808 : :
1809 : : /* Re-split critical edges when PRE did a CFG cleanup. */
1810 : 924251 : if (need_crit_edge_split)
1811 : 131047 : split_edges_for_insertion ();
1812 : :
1813 : 924251 : if (!dom_info_available_p (CDI_DOMINATORS))
1814 : : {
1815 : : /* PRE can leave us with unreachable blocks, remove them now. */
1816 : 0 : delete_unreachable_blocks ();
1817 : 0 : calculate_dominance_info (CDI_DOMINATORS);
1818 : : }
1819 : 924251 : init_worklist ();
1820 : :
1821 : 2042307 : while (!worklist.is_empty ())
1822 : : {
1823 : 260572 : if (!loop_entered)
1824 : : {
1825 : 248871 : loop_entered = true;
1826 : 248871 : alloc_cluster_vectors ();
1827 : 248871 : update_bbs = BITMAP_ALLOC (NULL);
1828 : : }
1829 : : else
1830 : 11701 : reset_cluster_vectors ();
1831 : :
1832 : 260572 : iteration_nr++;
1833 : 260572 : if (dump_file && (dump_flags & TDF_DETAILS))
1834 : 9 : fprintf (dump_file, "worklist iteration #%d\n", iteration_nr);
1835 : :
1836 : 260572 : find_clusters ();
1837 : 260572 : gcc_assert (worklist.is_empty ());
1838 : 260572 : if (all_clusters.is_empty ())
1839 : : break;
1840 : :
1841 : 200585 : nr_bbs_removed = apply_clusters ();
1842 : 200585 : nr_bbs_removed_total += nr_bbs_removed;
1843 : 200585 : if (nr_bbs_removed == 0)
1844 : : break;
1845 : :
1846 : 200585 : free_dominance_info (CDI_DOMINATORS);
1847 : :
1848 : 200585 : if (iteration_nr == max_iterations)
1849 : : break;
1850 : :
1851 : 193805 : calculate_dominance_info (CDI_DOMINATORS);
1852 : 193805 : update_worklist ();
1853 : : }
1854 : :
1855 : 924251 : if (dump_file && (dump_flags & TDF_DETAILS))
1856 : 28 : fprintf (dump_file, "htab collision / search: %f\n",
1857 : : same_succ_htab->collisions ());
1858 : :
1859 : 924251 : if (nr_bbs_removed_total > 0)
1860 : : {
1861 : 193805 : if (MAY_HAVE_DEBUG_BIND_STMTS)
1862 : : {
1863 : 131251 : calculate_dominance_info (CDI_DOMINATORS);
1864 : 131251 : update_debug_stmts ();
1865 : : }
1866 : :
1867 : 193805 : if (dump_file && (dump_flags & TDF_DETAILS))
1868 : : {
1869 : 2 : fprintf (dump_file, "Before TODOs.\n");
1870 : 2 : dump_function_to_file (current_function_decl, dump_file, dump_flags);
1871 : : }
1872 : :
1873 : 193805 : mark_virtual_operands_for_renaming (cfun);
1874 : : }
1875 : :
1876 : 924251 : delete_worklist ();
1877 : 924251 : if (loop_entered)
1878 : : {
1879 : 248871 : delete_cluster_vectors ();
1880 : 248871 : BITMAP_FREE (update_bbs);
1881 : : }
1882 : :
1883 : 924251 : timevar_pop (TV_TREE_TAIL_MERGE);
1884 : :
1885 : 924251 : return 0;
1886 : : }
|
