Branch data Line data Source code
1 : : /* Hooks for cfg representation specific functions.
2 : : Copyright (C) 2003-2026 Free Software Foundation, Inc.
3 : : Contributed by Sebastian Pop <s.pop@laposte.net>
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 : : #define INCLUDE_VECTOR
22 : : #include "config.h"
23 : : #include "system.h"
24 : : #include "coretypes.h"
25 : : #include "backend.h"
26 : : #include "rtl.h"
27 : : #include "cfghooks.h"
28 : : #include "timevar.h"
29 : : #include "pretty-print.h"
30 : : #include "diagnostic-core.h"
31 : : #include "dumpfile.h"
32 : : #include "cfganal.h"
33 : : #include "tree.h"
34 : : #include "tree-ssa.h"
35 : : #include "cfgloop.h"
36 : : #include "sreal.h"
37 : : #include "profile.h"
38 : : #include "diagnostics/sarif-sink.h"
39 : : #include "custom-sarif-properties/cfg.h"
40 : :
41 : : /* Disable warnings about missing quoting in GCC diagnostics. */
42 : : #if __GNUC__ >= 10
43 : : # pragma GCC diagnostic push
44 : : # pragma GCC diagnostic ignored "-Wformat-diag"
45 : : #endif
46 : :
47 : : /* A pointer to one of the hooks containers. */
48 : : static struct cfg_hooks *cfg_hooks;
49 : :
50 : : /* Initialization of functions specific to the rtl IR. */
51 : : void
52 : 4020329 : rtl_register_cfg_hooks (void)
53 : : {
54 : 4020329 : cfg_hooks = &rtl_cfg_hooks;
55 : 4020329 : }
56 : :
57 : : /* Initialization of functions specific to the rtl IR. */
58 : : void
59 : 2532315 : cfg_layout_rtl_register_cfg_hooks (void)
60 : : {
61 : 2532315 : cfg_hooks = &cfg_layout_rtl_cfg_hooks;
62 : 2532315 : }
63 : :
64 : : /* Initialization of functions specific to the tree IR. */
65 : :
66 : : void
67 : 14459192 : gimple_register_cfg_hooks (void)
68 : : {
69 : 14459192 : cfg_hooks = &gimple_cfg_hooks;
70 : 14459192 : }
71 : :
72 : : struct cfg_hooks
73 : 770 : get_cfg_hooks (void)
74 : : {
75 : 770 : return *cfg_hooks;
76 : : }
77 : :
78 : : void
79 : 1540 : set_cfg_hooks (struct cfg_hooks new_cfg_hooks)
80 : : {
81 : 1540 : *cfg_hooks = new_cfg_hooks;
82 : 1540 : }
83 : :
84 : : /* Returns current ir type. */
85 : :
86 : : enum ir_type
87 : 276036398 : current_ir_type (void)
88 : : {
89 : 276036398 : if (cfg_hooks == &gimple_cfg_hooks)
90 : : return IR_GIMPLE;
91 : 118518032 : else if (cfg_hooks == &rtl_cfg_hooks)
92 : : return IR_RTL_CFGRTL;
93 : 41116673 : else if (cfg_hooks == &cfg_layout_rtl_cfg_hooks)
94 : : return IR_RTL_CFGLAYOUT;
95 : : else
96 : 0 : gcc_unreachable ();
97 : : }
98 : :
99 : : /* Verify the CFG consistency.
100 : :
101 : : Currently it does following: checks edge and basic block list correctness
102 : : and calls into IL dependent checking then. */
103 : :
104 : : DEBUG_FUNCTION void
105 : 328628487 : verify_flow_info (void)
106 : : {
107 : 328628487 : size_t *edge_checksum;
108 : 328628487 : bool err = false;
109 : 328628487 : basic_block bb, last_bb_seen;
110 : 328628487 : basic_block *last_visited;
111 : :
112 : 328628487 : timevar_push (TV_CFG_VERIFY);
113 : 328628487 : last_visited = XCNEWVEC (basic_block, last_basic_block_for_fn (cfun));
114 : 328628487 : edge_checksum = XCNEWVEC (size_t, last_basic_block_for_fn (cfun));
115 : :
116 : : /* Check bb chain & numbers. */
117 : 328628487 : last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun);
118 : 3712856432 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb)
119 : : {
120 : 3384227945 : if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
121 : 3384227945 : && bb != BASIC_BLOCK_FOR_FN (cfun, bb->index))
122 : : {
123 : 0 : error ("bb %d on wrong place", bb->index);
124 : 0 : err = true;
125 : : }
126 : :
127 : 3384227945 : if (bb->prev_bb != last_bb_seen)
128 : : {
129 : 0 : error ("prev_bb of %d should be %d, not %d",
130 : : bb->index, last_bb_seen->index, bb->prev_bb->index);
131 : 0 : err = true;
132 : : }
133 : :
134 : 3384227945 : last_bb_seen = bb;
135 : : }
136 : :
137 : : /* Now check the basic blocks (boundaries etc.) */
138 : 3384227945 : FOR_EACH_BB_REVERSE_FN (bb, cfun)
139 : : {
140 : 3055599458 : int n_fallthru = 0;
141 : 3055599458 : edge e;
142 : 3055599458 : edge_iterator ei;
143 : :
144 : 3055599458 : if (bb->loop_father != NULL && current_loops == NULL)
145 : : {
146 : 0 : error ("verify_flow_info: Block %i has loop_father, but there are no loops",
147 : : bb->index);
148 : 0 : err = true;
149 : : }
150 : 3055599458 : if (bb->loop_father == NULL && current_loops != NULL)
151 : : {
152 : 0 : error ("verify_flow_info: Block %i lacks loop_father", bb->index);
153 : 0 : err = true;
154 : : }
155 : :
156 : 3055599458 : if (!bb->count.verify ())
157 : : {
158 : 0 : error ("verify_flow_info: Wrong count of block %i", bb->index);
159 : 0 : err = true;
160 : : }
161 : : /* FIXME: Graphite and SLJL and target code still tends to produce
162 : : edges with no probability. */
163 : 3055599458 : if (profile_status_for_fn (cfun) >= PROFILE_GUESSED
164 : : && !bb->count.initialized_p () && !flag_graphite && 0)
165 : : {
166 : : error ("verify_flow_info: Missing count of block %i", bb->index);
167 : : err = true;
168 : : }
169 : :
170 : 3055599458 : if (bb->flags & ~cfun->cfg->bb_flags_allocated)
171 : : {
172 : 0 : error ("verify_flow_info: unallocated flag set on BB %d", bb->index);
173 : 0 : err = true;
174 : : }
175 : :
176 : 7388622130 : FOR_EACH_EDGE (e, ei, bb->succs)
177 : : {
178 : 4333022672 : if (last_visited [e->dest->index] == bb)
179 : : {
180 : 0 : error ("verify_flow_info: Duplicate edge %i->%i",
181 : 0 : e->src->index, e->dest->index);
182 : 0 : err = true;
183 : : }
184 : : /* FIXME: Graphite and SLJL and target code still tends to produce
185 : : edges with no probability. */
186 : 4333022672 : if (profile_status_for_fn (cfun) >= PROFILE_GUESSED
187 : : && !e->probability.initialized_p () && !flag_graphite && 0)
188 : : {
189 : : error ("Uninitialized probability of edge %i->%i", e->src->index,
190 : : e->dest->index);
191 : : err = true;
192 : : }
193 : 4333022672 : if (!e->probability.verify ())
194 : : {
195 : 0 : error ("verify_flow_info: Wrong probability of edge %i->%i",
196 : 0 : e->src->index, e->dest->index);
197 : 0 : err = true;
198 : : }
199 : :
200 : 4333022672 : last_visited [e->dest->index] = bb;
201 : :
202 : 4333022672 : if (e->flags & EDGE_FALLTHRU)
203 : 1657913556 : n_fallthru++;
204 : :
205 : 4333022672 : if (e->src != bb)
206 : : {
207 : 0 : error ("verify_flow_info: Basic block %d succ edge is corrupted",
208 : : bb->index);
209 : 0 : fprintf (stderr, "Predecessor: ");
210 : 0 : dump_edge_info (stderr, e, TDF_DETAILS, 0);
211 : 0 : fprintf (stderr, "\nSuccessor: ");
212 : 0 : dump_edge_info (stderr, e, TDF_DETAILS, 1);
213 : 0 : fprintf (stderr, "\n");
214 : 0 : err = true;
215 : : }
216 : :
217 : 4333022672 : if (e->flags & ~cfun->cfg->edge_flags_allocated)
218 : : {
219 : 0 : error ("verify_flow_info: unallocated edge flag set on %d -> %d",
220 : 0 : e->src->index, e->dest->index);
221 : 0 : err = true;
222 : : }
223 : :
224 : 4333022672 : edge_checksum[e->dest->index] += (size_t) e;
225 : : }
226 : 3055599458 : if (n_fallthru > 1)
227 : : {
228 : 0 : error ("wrong amount of branch edges after unconditional jump %i", bb->index);
229 : 0 : err = true;
230 : : }
231 : :
232 : 7385893651 : FOR_EACH_EDGE (e, ei, bb->preds)
233 : : {
234 : 4330294193 : if (e->dest != bb)
235 : : {
236 : 0 : error ("basic block %d pred edge is corrupted", bb->index);
237 : 0 : fputs ("Predecessor: ", stderr);
238 : 0 : dump_edge_info (stderr, e, TDF_DETAILS, 0);
239 : 0 : fputs ("\nSuccessor: ", stderr);
240 : 0 : dump_edge_info (stderr, e, TDF_DETAILS, 1);
241 : 0 : fputc ('\n', stderr);
242 : 0 : err = true;
243 : : }
244 : :
245 : 4330294193 : if (ei.index != e->dest_idx)
246 : : {
247 : 0 : error ("basic block %d pred edge is corrupted", bb->index);
248 : 0 : error ("its dest_idx should be %d, not %d",
249 : : ei.index, e->dest_idx);
250 : 0 : fputs ("Predecessor: ", stderr);
251 : 0 : dump_edge_info (stderr, e, TDF_DETAILS, 0);
252 : 0 : fputs ("\nSuccessor: ", stderr);
253 : 0 : dump_edge_info (stderr, e, TDF_DETAILS, 1);
254 : 0 : fputc ('\n', stderr);
255 : 0 : err = true;
256 : : }
257 : :
258 : 4330294193 : edge_checksum[e->dest->index] -= (size_t) e;
259 : : }
260 : : }
261 : :
262 : : /* Complete edge checksumming for ENTRY and EXIT. */
263 : 328628487 : {
264 : 328628487 : edge e;
265 : 328628487 : edge_iterator ei;
266 : :
267 : 657256974 : FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
268 : 328628487 : edge_checksum[e->dest->index] += (size_t) e;
269 : :
270 : 659985453 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
271 : 331356966 : edge_checksum[e->dest->index] -= (size_t) e;
272 : : }
273 : :
274 : 4041484919 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
275 : 3712856432 : if (edge_checksum[bb->index])
276 : : {
277 : 0 : error ("basic block %i edge lists are corrupted", bb->index);
278 : 0 : err = true;
279 : : }
280 : :
281 : : /* Clean up. */
282 : 328628487 : free (last_visited);
283 : 328628487 : free (edge_checksum);
284 : :
285 : 328628487 : if (cfg_hooks->verify_flow_info)
286 : 328628487 : if (cfg_hooks->verify_flow_info ())
287 : : err = true;
288 : :
289 : 328628487 : if (err)
290 : 0 : internal_error ("verify_flow_info failed");
291 : 328628487 : timevar_pop (TV_CFG_VERIFY);
292 : 328628487 : }
293 : :
294 : : /* Print out one basic block BB to file OUTF. INDENT is printed at the
295 : : start of each new line. FLAGS are the TDF_* flags in dumpfile.h.
296 : :
297 : : This function takes care of the purely graph related information.
298 : : The cfg hook for the active representation should dump
299 : : representation-specific information. */
300 : :
301 : : void
302 : 295368 : dump_bb (FILE *outf, basic_block bb, int indent, dump_flags_t flags)
303 : : {
304 : 295368 : if (flags & TDF_BLOCKS)
305 : 46520 : dump_bb_info (outf, bb, indent, flags, true, false);
306 : 295368 : if (cfg_hooks->dump_bb)
307 : 295368 : cfg_hooks->dump_bb (outf, bb, indent, flags);
308 : 295368 : if (flags & TDF_BLOCKS)
309 : 46520 : dump_bb_info (outf, bb, indent, flags, false, true);
310 : 295368 : fputc ('\n', outf);
311 : 295368 : }
312 : :
313 : : DEBUG_FUNCTION void
314 : 0 : debug (basic_block_def &ref)
315 : : {
316 : 0 : dump_bb (stderr, &ref, 0, TDF_NONE);
317 : 0 : }
318 : :
319 : : DEBUG_FUNCTION void
320 : 0 : debug (basic_block_def *ptr)
321 : : {
322 : 0 : if (ptr)
323 : 0 : debug (*ptr);
324 : : else
325 : 0 : fprintf (stderr, "<nil>\n");
326 : 0 : }
327 : :
328 : : static void
329 : 0 : debug_slim (basic_block ptr)
330 : : {
331 : 0 : fprintf (stderr, "<basic_block %p (%d)>", (void *) ptr, ptr->index);
332 : 0 : }
333 : :
334 : 0 : DEFINE_DEBUG_VEC (basic_block_def *)
335 : 0 : DEFINE_DEBUG_HASH_SET (basic_block_def *)
336 : :
337 : : /* Dumps basic block BB to pretty-printer PP, for use as a label of
338 : : a DOT graph record-node. The implementation of this hook is
339 : : expected to write the label to the stream that is attached to PP.
340 : : Field separators between instructions are pipe characters printed
341 : : verbatim. Instructions should be written with some characters
342 : : escaped, using pp_write_text_as_dot_label_to_stream(). */
343 : :
344 : : void
345 : 451 : dump_bb_for_graph (pretty_printer *pp, basic_block bb)
346 : : {
347 : 451 : if (!cfg_hooks->dump_bb_for_graph)
348 : 0 : internal_error ("%s does not support dump_bb_for_graph",
349 : : cfg_hooks->name);
350 : : /* TODO: Add pretty printer for counter. */
351 : 451 : if (bb->count.initialized_p ())
352 : 352 : pp_printf (pp, "COUNT:" "%" PRId64, bb->count.to_gcov_type ());
353 : 451 : pp_write_text_to_stream (pp);
354 : 451 : if (!(dump_flags & TDF_SLIM))
355 : 451 : cfg_hooks->dump_bb_for_graph (pp, bb);
356 : 451 : }
357 : :
358 : : void
359 : 540 : dump_bb_as_sarif_properties (diagnostics::sarif_builder *builder,
360 : : json::object &output_bag,
361 : : basic_block bb)
362 : : {
363 : 540 : if (!cfg_hooks->dump_bb_for_graph)
364 : 0 : internal_error ("%s does not support dump_bb_as_sarif_properties",
365 : : cfg_hooks->name);
366 : 540 : namespace bb_property_names = custom_sarif_properties::cfg::basic_block;
367 : 540 : if (bb->index == ENTRY_BLOCK)
368 : 90 : output_bag.set_string (bb_property_names::kind, "entry");
369 : 450 : else if (bb->index == EXIT_BLOCK)
370 : 90 : output_bag.set_string (bb_property_names::kind, "exit");
371 : 360 : else if (BB_PARTITION (bb) == BB_HOT_PARTITION)
372 : 0 : output_bag.set_string (bb_property_names::kind, "hot");
373 : 360 : else if (BB_PARTITION (bb) == BB_COLD_PARTITION)
374 : 0 : output_bag.set_string (bb_property_names::kind, "cold");
375 : 540 : if (bb->count.initialized_p ())
376 : : {
377 : 0 : pretty_printer pp;
378 : 0 : pp_printf (&pp, "%" PRId64, bb->count.to_gcov_type ());
379 : 0 : output_bag.set_string (bb_property_names::count,
380 : : pp_formatted_text (&pp));
381 : 0 : }
382 : 540 : cfg_hooks->dump_bb_as_sarif_properties (builder, output_bag, bb);
383 : 540 : }
384 : :
385 : : /* Dump the complete CFG to FILE. FLAGS are the TDF_* flags in dumpfile.h. */
386 : : void
387 : 288 : dump_flow_info (FILE *file, dump_flags_t flags)
388 : : {
389 : 288 : basic_block bb;
390 : :
391 : 288 : fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks_for_fn (cfun),
392 : 288 : n_edges_for_fn (cfun));
393 : 2591 : FOR_ALL_BB_FN (bb, cfun)
394 : 2303 : dump_bb (file, bb, 0, flags);
395 : :
396 : 288 : putc ('\n', file);
397 : 288 : }
398 : :
399 : : /* Like above, but dump to stderr. To be called from debuggers. */
400 : : void debug_flow_info (void);
401 : : DEBUG_FUNCTION void
402 : 0 : debug_flow_info (void)
403 : : {
404 : 0 : dump_flow_info (stderr, TDF_DETAILS);
405 : 0 : }
406 : :
407 : : /* Redirect edge E to the given basic block DEST and update underlying program
408 : : representation. Returns edge representing redirected branch (that may not
409 : : be equivalent to E in the case of duplicate edges being removed) or NULL
410 : : if edge is not easily redirectable for whatever reason. */
411 : :
412 : : edge
413 : 75691996 : redirect_edge_and_branch (edge e, basic_block dest)
414 : : {
415 : 75691996 : edge ret;
416 : :
417 : 75691996 : if (!cfg_hooks->redirect_edge_and_branch)
418 : 0 : internal_error ("%s does not support redirect_edge_and_branch",
419 : : cfg_hooks->name);
420 : :
421 : 75691996 : ret = cfg_hooks->redirect_edge_and_branch (e, dest);
422 : :
423 : : /* If RET != E, then either the redirection failed, or the edge E
424 : : was removed since RET already lead to the same destination. */
425 : 75691996 : if (current_loops != NULL && ret == e)
426 : 62938154 : rescan_loop_exit (e, false, false);
427 : :
428 : 75691996 : return ret;
429 : : }
430 : :
431 : : /* Returns true if it is possible to remove the edge E by redirecting it
432 : : to the destination of the other edge going from its source. */
433 : :
434 : : bool
435 : 431484 : can_remove_branch_p (const_edge e)
436 : : {
437 : 431484 : if (!cfg_hooks->can_remove_branch_p)
438 : 0 : internal_error ("%s does not support can_remove_branch_p",
439 : : cfg_hooks->name);
440 : :
441 : 431484 : if (EDGE_COUNT (e->src->succs) != 2)
442 : : return false;
443 : :
444 : 431484 : return cfg_hooks->can_remove_branch_p (e);
445 : : }
446 : :
447 : : /* Removes E, by redirecting it to the destination of the other edge going
448 : : from its source. Can_remove_branch_p must be true for E, hence this
449 : : operation cannot fail. */
450 : :
451 : : void
452 : 431542 : remove_branch (edge e)
453 : : {
454 : 431542 : edge other;
455 : 431542 : basic_block src = e->src;
456 : 431542 : int irr;
457 : :
458 : 431542 : gcc_assert (EDGE_COUNT (e->src->succs) == 2);
459 : :
460 : 431542 : other = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
461 : 431542 : irr = other->flags & EDGE_IRREDUCIBLE_LOOP;
462 : :
463 : 431542 : e = redirect_edge_and_branch (e, other->dest);
464 : 431542 : gcc_assert (e != NULL);
465 : :
466 : 431542 : e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
467 : 431542 : e->flags |= irr;
468 : 431542 : }
469 : :
470 : : /* Removes edge E from cfg. Unlike remove_branch, it does not update IL. */
471 : :
472 : : void
473 : 84565311 : remove_edge (edge e)
474 : : {
475 : 84565311 : if (current_loops != NULL)
476 : : {
477 : 75264355 : rescan_loop_exit (e, false, true);
478 : :
479 : : /* Removal of an edge inside an irreducible region or which leads
480 : : to an irreducible region can turn the region into a natural loop.
481 : : In that case, ask for the loop structure fixups.
482 : :
483 : : FIXME: Note that LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS is not always
484 : : set, so always ask for fixups when removing an edge in that case. */
485 : 75264355 : if (!loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
486 : 8020343 : || (e->flags & EDGE_IRREDUCIBLE_LOOP)
487 : 83281215 : || (e->dest->flags & BB_IRREDUCIBLE_LOOP))
488 : 67248112 : loops_state_set (LOOPS_NEED_FIXUP);
489 : : }
490 : :
491 : : /* This is probably not needed, but it doesn't hurt. */
492 : : /* FIXME: This should be called via a remove_edge hook. */
493 : 84565311 : if (current_ir_type () == IR_GIMPLE)
494 : 68410764 : redirect_edge_var_map_clear (e);
495 : :
496 : 84565311 : remove_edge_raw (e);
497 : 84565311 : }
498 : :
499 : : /* Like redirect_edge_succ but avoid possible duplicate edge. */
500 : :
501 : : edge
502 : 81105014 : redirect_edge_succ_nodup (edge e, basic_block new_succ)
503 : : {
504 : 81105014 : edge s;
505 : :
506 : 81105014 : s = find_edge (e->src, new_succ);
507 : 81105014 : if (s && s != e)
508 : : {
509 : 416961 : s->flags |= e->flags;
510 : 416961 : s->probability += e->probability;
511 : : /* FIXME: This should be called via a hook and only for IR_GIMPLE. */
512 : 416961 : redirect_edge_var_map_dup (s, e);
513 : 416961 : remove_edge (e);
514 : 416961 : e = s;
515 : : }
516 : : else
517 : 80688053 : redirect_edge_succ (e, new_succ);
518 : :
519 : 81105014 : return e;
520 : : }
521 : :
522 : : /* Redirect the edge E to basic block DEST even if it requires creating
523 : : of a new basic block; then it returns the newly created basic block.
524 : : Aborts when redirection is impossible. */
525 : :
526 : : basic_block
527 : 9145541 : redirect_edge_and_branch_force (edge e, basic_block dest)
528 : : {
529 : 9145541 : basic_block ret, src = e->src;
530 : :
531 : 9145541 : if (!cfg_hooks->redirect_edge_and_branch_force)
532 : 0 : internal_error ("%s does not support redirect_edge_and_branch_force",
533 : : cfg_hooks->name);
534 : :
535 : 9145541 : if (current_loops != NULL)
536 : 7458211 : rescan_loop_exit (e, false, true);
537 : :
538 : 9145541 : ret = cfg_hooks->redirect_edge_and_branch_force (e, dest);
539 : :
540 : 9145541 : if (ret != NULL && dom_info_available_p (CDI_DOMINATORS))
541 : 43408 : set_immediate_dominator (CDI_DOMINATORS, ret, src);
542 : :
543 : 9145541 : if (current_loops != NULL)
544 : : {
545 : 7458211 : if (ret != NULL)
546 : : {
547 : 3 : class loop *loop
548 : 3 : = find_common_loop (single_pred (ret)->loop_father,
549 : 3 : single_succ (ret)->loop_father);
550 : 3 : add_bb_to_loop (ret, loop);
551 : : }
552 : 7458208 : else if (find_edge (src, dest) == e)
553 : 7458201 : rescan_loop_exit (e, true, false);
554 : : }
555 : :
556 : 9145541 : return ret;
557 : : }
558 : :
559 : : /* Splits basic block BB after the specified instruction I (but at least after
560 : : the labels). If I is NULL, splits just after labels. The newly created edge
561 : : is returned. The new basic block is created just after the old one. */
562 : :
563 : : static edge
564 : 8560094 : split_block_1 (basic_block bb, void *i)
565 : : {
566 : 8560094 : basic_block new_bb;
567 : 8560094 : edge res;
568 : :
569 : 8560094 : if (!cfg_hooks->split_block)
570 : 0 : internal_error ("%s does not support split_block", cfg_hooks->name);
571 : :
572 : 8560094 : new_bb = cfg_hooks->split_block (bb, i);
573 : 8560094 : if (!new_bb)
574 : : return NULL;
575 : :
576 : 8560094 : new_bb->count = bb->count;
577 : :
578 : 8560094 : if (dom_info_available_p (CDI_DOMINATORS))
579 : : {
580 : 663099 : redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
581 : 663099 : set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
582 : : }
583 : :
584 : 8560094 : if (current_loops != NULL)
585 : : {
586 : 7603864 : edge_iterator ei;
587 : 7603864 : edge e;
588 : 7603864 : add_bb_to_loop (new_bb, bb->loop_father);
589 : : /* Identify all loops bb may have been the latch of and adjust them. */
590 : 18762229 : FOR_EACH_EDGE (e, ei, new_bb->succs)
591 : 11158365 : if (e->dest->loop_father->latch == bb)
592 : 127151 : e->dest->loop_father->latch = new_bb;
593 : : }
594 : :
595 : 8560094 : res = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
596 : :
597 : 8560094 : if (bb->flags & BB_IRREDUCIBLE_LOOP)
598 : : {
599 : 6179 : new_bb->flags |= BB_IRREDUCIBLE_LOOP;
600 : 6179 : res->flags |= EDGE_IRREDUCIBLE_LOOP;
601 : : }
602 : :
603 : : return res;
604 : : }
605 : :
606 : : edge
607 : 5440404 : split_block (basic_block bb, gimple *i)
608 : : {
609 : 5440404 : return split_block_1 (bb, i);
610 : : }
611 : :
612 : : edge
613 : 3001939 : split_block (basic_block bb, rtx i)
614 : : {
615 : 3001939 : return split_block_1 (bb, i);
616 : : }
617 : :
618 : : /* Splits block BB just after labels. The newly created edge is returned. */
619 : :
620 : : edge
621 : 117751 : split_block_after_labels (basic_block bb)
622 : : {
623 : 117751 : return split_block_1 (bb, NULL);
624 : : }
625 : :
626 : : /* Moves block BB immediately after block AFTER. Returns false if the
627 : : movement was impossible. */
628 : :
629 : : bool
630 : 23368063 : move_block_after (basic_block bb, basic_block after)
631 : : {
632 : 23368063 : bool ret;
633 : :
634 : 23368063 : if (!cfg_hooks->move_block_after)
635 : 0 : internal_error ("%s does not support move_block_after", cfg_hooks->name);
636 : :
637 : 23368063 : ret = cfg_hooks->move_block_after (bb, after);
638 : :
639 : 23368063 : return ret;
640 : : }
641 : :
642 : : /* Deletes the basic block BB. */
643 : :
644 : : void
645 : 43069866 : delete_basic_block (basic_block bb)
646 : : {
647 : 43069866 : if (!cfg_hooks->delete_basic_block)
648 : 0 : internal_error ("%s does not support delete_basic_block", cfg_hooks->name);
649 : :
650 : 43069866 : cfg_hooks->delete_basic_block (bb);
651 : :
652 : 43069866 : if (current_loops != NULL)
653 : : {
654 : 37946365 : class loop *loop = bb->loop_father;
655 : :
656 : : /* If we remove the header or the latch of a loop, mark the loop for
657 : : removal. */
658 : 37946365 : if (loop->latch == bb
659 : 37736640 : || loop->header == bb)
660 : 257536 : mark_loop_for_removal (loop);
661 : :
662 : 37946365 : remove_bb_from_loops (bb);
663 : : }
664 : :
665 : : /* Remove the edges into and out of this block. Note that there may
666 : : indeed be edges in, if we are removing an unreachable loop. */
667 : 86862089 : while (EDGE_COUNT (bb->preds) != 0)
668 : 689698 : remove_edge (EDGE_PRED (bb, 0));
669 : 49812958 : while (EDGE_COUNT (bb->succs) != 0)
670 : 6743092 : remove_edge (EDGE_SUCC (bb, 0));
671 : :
672 : 43069866 : if (dom_info_available_p (CDI_DOMINATORS))
673 : 30193171 : delete_from_dominance_info (CDI_DOMINATORS, bb);
674 : 43069866 : if (dom_info_available_p (CDI_POST_DOMINATORS))
675 : 422761 : delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
676 : :
677 : : /* Remove the basic block from the array. */
678 : 43069866 : expunge_block (bb);
679 : 43069866 : }
680 : :
681 : : /* Splits edge E and returns the newly created basic block. */
682 : :
683 : : basic_block
684 : 30245820 : split_edge (edge e)
685 : : {
686 : 30245820 : basic_block ret;
687 : 30245820 : profile_count count = e->count ();
688 : 30245820 : edge f;
689 : 30245820 : bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
690 : 30245820 : bool back = (e->flags & EDGE_DFS_BACK) != 0;
691 : 30245820 : class loop *loop;
692 : 30245820 : basic_block src = e->src, dest = e->dest;
693 : :
694 : 30245820 : if (!cfg_hooks->split_edge)
695 : 0 : internal_error ("%s does not support split_edge", cfg_hooks->name);
696 : :
697 : 30245820 : if (current_loops != NULL)
698 : 28750656 : rescan_loop_exit (e, false, true);
699 : :
700 : 30245820 : ret = cfg_hooks->split_edge (e);
701 : 30245820 : ret->count = count;
702 : 30245820 : single_succ_edge (ret)->probability = profile_probability::always ();
703 : :
704 : 30245820 : if (irr)
705 : : {
706 : 72626 : ret->flags |= BB_IRREDUCIBLE_LOOP;
707 : 72626 : single_pred_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
708 : 72626 : single_succ_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
709 : : }
710 : 30245820 : if (back)
711 : : {
712 : 2092425 : single_pred_edge (ret)->flags &= ~EDGE_DFS_BACK;
713 : 2092425 : single_succ_edge (ret)->flags |= EDGE_DFS_BACK;
714 : : }
715 : :
716 : 30245820 : if (dom_info_available_p (CDI_DOMINATORS))
717 : 26021650 : set_immediate_dominator (CDI_DOMINATORS, ret, single_pred (ret));
718 : :
719 : 30245820 : if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
720 : : {
721 : : /* There are two cases:
722 : :
723 : : If the immediate dominator of e->dest is not e->src, it
724 : : remains unchanged.
725 : :
726 : : If immediate dominator of e->dest is e->src, it may become
727 : : ret, provided that all other predecessors of e->dest are
728 : : dominated by e->dest. */
729 : :
730 : 26021650 : if (get_immediate_dominator (CDI_DOMINATORS, single_succ (ret))
731 : 26021650 : == single_pred (ret))
732 : : {
733 : 9076731 : edge_iterator ei;
734 : 19953616 : FOR_EACH_EDGE (f, ei, single_succ (ret)->preds)
735 : : {
736 : 15693770 : if (f == single_succ_edge (ret))
737 : 6872834 : continue;
738 : :
739 : 8820936 : if (!dominated_by_p (CDI_DOMINATORS, f->src,
740 : 8820936 : single_succ (ret)))
741 : : break;
742 : : }
743 : :
744 : 9076731 : if (!f)
745 : 4259846 : set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret);
746 : : }
747 : : }
748 : :
749 : 30245820 : if (current_loops != NULL)
750 : : {
751 : 28750656 : loop = find_common_loop (src->loop_father, dest->loop_father);
752 : 28750656 : add_bb_to_loop (ret, loop);
753 : :
754 : : /* If we split the latch edge of loop adjust the latch block. */
755 : 28750656 : if (loop->latch == src
756 : 6326957 : && loop->header == dest)
757 : 6326872 : loop->latch = ret;
758 : : }
759 : :
760 : 30245820 : return ret;
761 : : }
762 : :
763 : : /* Creates a new basic block just after the basic block AFTER.
764 : : HEAD and END are the first and the last statement belonging
765 : : to the block. If both are NULL, an empty block is created. */
766 : :
767 : : static basic_block
768 : 84151623 : create_basic_block_1 (void *head, void *end, basic_block after)
769 : : {
770 : 84151623 : basic_block ret;
771 : :
772 : 84151623 : if (!cfg_hooks->create_basic_block)
773 : 0 : internal_error ("%s does not support create_basic_block", cfg_hooks->name);
774 : :
775 : 84151623 : ret = cfg_hooks->create_basic_block (head, end, after);
776 : :
777 : 84151623 : if (dom_info_available_p (CDI_DOMINATORS))
778 : 31535120 : add_to_dominance_info (CDI_DOMINATORS, ret);
779 : 84151623 : if (dom_info_available_p (CDI_POST_DOMINATORS))
780 : 181599 : add_to_dominance_info (CDI_POST_DOMINATORS, ret);
781 : :
782 : 84151623 : return ret;
783 : : }
784 : :
785 : : basic_block
786 : 35793392 : create_basic_block (gimple_seq seq, basic_block after)
787 : : {
788 : 35793392 : return create_basic_block_1 (seq, NULL, after);
789 : : }
790 : :
791 : : basic_block
792 : 13258252 : create_basic_block (rtx head, rtx end, basic_block after)
793 : : {
794 : 13258252 : return create_basic_block_1 (head, end, after);
795 : : }
796 : :
797 : :
798 : : /* Creates an empty basic block just after basic block AFTER. */
799 : :
800 : : basic_block
801 : 35099979 : create_empty_bb (basic_block after)
802 : : {
803 : 35099979 : return create_basic_block_1 (NULL, NULL, after);
804 : : }
805 : :
806 : : /* Checks whether we may merge blocks BB1 and BB2. */
807 : :
808 : : bool
809 : 417433382 : can_merge_blocks_p (basic_block bb1, basic_block bb2)
810 : : {
811 : 417433382 : bool ret;
812 : :
813 : 417433382 : if (!cfg_hooks->can_merge_blocks_p)
814 : 0 : internal_error ("%s does not support can_merge_blocks_p", cfg_hooks->name);
815 : :
816 : 417433382 : ret = cfg_hooks->can_merge_blocks_p (bb1, bb2);
817 : :
818 : 417433382 : return ret;
819 : : }
820 : :
821 : : void
822 : 6167107 : predict_edge (edge e, enum br_predictor predictor, int probability)
823 : : {
824 : 6167107 : if (!cfg_hooks->predict_edge)
825 : 0 : internal_error ("%s does not support predict_edge", cfg_hooks->name);
826 : :
827 : 6167107 : cfg_hooks->predict_edge (e, predictor, probability);
828 : 6167107 : }
829 : :
830 : : bool
831 : 3163845 : predicted_by_p (const_basic_block bb, enum br_predictor predictor)
832 : : {
833 : 3163845 : if (!cfg_hooks->predict_edge)
834 : 0 : internal_error ("%s does not support predicted_by_p", cfg_hooks->name);
835 : :
836 : 3163845 : return cfg_hooks->predicted_by_p (bb, predictor);
837 : : }
838 : :
839 : : /* Merges basic block B into basic block A. */
840 : :
841 : : void
842 : 21514648 : merge_blocks (basic_block a, basic_block b)
843 : : {
844 : 21514648 : edge e;
845 : 21514648 : edge_iterator ei;
846 : :
847 : 21514648 : if (!cfg_hooks->merge_blocks)
848 : 0 : internal_error ("%s does not support merge_blocks", cfg_hooks->name);
849 : :
850 : : /* Pick the more reliable count. If both qualities agrees, pick the larger
851 : : one since turning mistakely hot code to cold is more harmful. */
852 : 21514648 : if (!a->count.initialized_p ())
853 : 11681125 : a->count = b->count;
854 : 9833523 : else if (a->count.quality () < b->count.quality ())
855 : 4989 : a->count = b->count;
856 : 9828534 : else if (a->count.quality () == b->count.quality ())
857 : 9822877 : a->count = profile_count::max_prefer_initialized (a->count, b->count);
858 : :
859 : 21514648 : cfg_hooks->merge_blocks (a, b);
860 : :
861 : 21514648 : if (current_loops != NULL)
862 : : {
863 : : /* If the block we merge into is a loop header do nothing unless ... */
864 : 18326815 : if (a->loop_father->header == a)
865 : : {
866 : : /* ... we merge two loop headers, in which case we kill
867 : : the inner loop. */
868 : 642963 : if (b->loop_father->header == b)
869 : 424 : mark_loop_for_removal (b->loop_father);
870 : : }
871 : : /* If we merge a loop header into its predecessor, update the loop
872 : : structure. */
873 : 17683852 : else if (b->loop_father->header == b)
874 : : {
875 : 173 : remove_bb_from_loops (a);
876 : 173 : add_bb_to_loop (a, b->loop_father);
877 : 173 : a->loop_father->header = a;
878 : : }
879 : : /* If we merge a loop latch into its predecessor, update the loop
880 : : structure. */
881 : 18326815 : if (b->loop_father->latch
882 : 18202962 : && b->loop_father->latch == b)
883 : 256629 : b->loop_father->latch = a;
884 : 18326815 : remove_bb_from_loops (b);
885 : : }
886 : :
887 : : /* Normally there should only be one successor of A and that is B, but
888 : : partway though the merge of blocks for conditional_execution we'll
889 : : be merging a TEST block with THEN and ELSE successors. Free the
890 : : whole lot of them and hope the caller knows what they're doing. */
891 : :
892 : 43029296 : while (EDGE_COUNT (a->succs) != 0)
893 : 21514648 : remove_edge (EDGE_SUCC (a, 0));
894 : :
895 : : /* Adjust the edges out of B for the new owner. */
896 : 48858262 : FOR_EACH_EDGE (e, ei, b->succs)
897 : : {
898 : 27343614 : e->src = a;
899 : 27343614 : if (current_loops != NULL)
900 : : {
901 : : /* If b was a latch, a now is. */
902 : 23757020 : if (e->dest->loop_father->latch == b)
903 : 693 : e->dest->loop_father->latch = a;
904 : 23757020 : rescan_loop_exit (e, true, false);
905 : : }
906 : : }
907 : 21514648 : a->succs = b->succs;
908 : 21514648 : a->flags |= b->flags;
909 : :
910 : : /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
911 : 21514648 : b->preds = b->succs = NULL;
912 : :
913 : 21514648 : if (dom_info_available_p (CDI_DOMINATORS))
914 : 16828483 : redirect_immediate_dominators (CDI_DOMINATORS, b, a);
915 : :
916 : 21514648 : if (dom_info_available_p (CDI_DOMINATORS))
917 : 16828483 : delete_from_dominance_info (CDI_DOMINATORS, b);
918 : 21514648 : if (dom_info_available_p (CDI_POST_DOMINATORS))
919 : 116564 : delete_from_dominance_info (CDI_POST_DOMINATORS, b);
920 : :
921 : 21514648 : expunge_block (b);
922 : 21514648 : }
923 : :
924 : : /* Split BB into entry part and the rest (the rest is the newly created block).
925 : : Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
926 : : part. Returns the edge connecting the entry part to the rest. */
927 : :
928 : : edge
929 : 91845 : make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
930 : : void (*new_bb_cbk) (basic_block))
931 : : {
932 : 91845 : edge e, fallthru;
933 : 91845 : edge_iterator ei;
934 : 91845 : basic_block dummy, jump;
935 : 91845 : class loop *loop, *ploop, *cloop;
936 : :
937 : 91845 : if (!cfg_hooks->make_forwarder_block)
938 : 0 : internal_error ("%s does not support make_forwarder_block",
939 : : cfg_hooks->name);
940 : :
941 : 91845 : fallthru = split_block_after_labels (bb);
942 : 91845 : dummy = fallthru->src;
943 : 91845 : dummy->count = profile_count::zero ();
944 : 91845 : bb = fallthru->dest;
945 : :
946 : : /* Redirect back edges we want to keep. */
947 : 394913 : for (ei = ei_start (dummy->preds); (e = ei_safe_edge (ei)); )
948 : : {
949 : 303068 : basic_block e_src;
950 : :
951 : 303068 : if (redirect_edge_p (e))
952 : : {
953 : 208855 : dummy->count += e->count ();
954 : 208855 : ei_next (&ei);
955 : 208855 : continue;
956 : : }
957 : :
958 : 94213 : e_src = e->src;
959 : 94213 : jump = redirect_edge_and_branch_force (e, bb);
960 : 94213 : if (jump != NULL)
961 : : {
962 : : /* If we redirected the loop latch edge, the JUMP block now acts like
963 : : the new latch of the loop. */
964 : 2 : if (current_loops != NULL
965 : 2 : && dummy->loop_father != NULL
966 : 2 : && dummy->loop_father->header == dummy
967 : 2 : && dummy->loop_father->latch == e_src)
968 : 0 : dummy->loop_father->latch = jump;
969 : :
970 : 2 : if (new_bb_cbk != NULL)
971 : 0 : new_bb_cbk (jump);
972 : : }
973 : : }
974 : :
975 : 91845 : if (dom_info_available_p (CDI_DOMINATORS))
976 : : {
977 : 48916 : vec<basic_block> doms_to_fix;
978 : 48916 : doms_to_fix.create (2);
979 : 48916 : doms_to_fix.quick_push (dummy);
980 : 48916 : doms_to_fix.quick_push (bb);
981 : 48916 : iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, false);
982 : 48916 : doms_to_fix.release ();
983 : : }
984 : :
985 : 91845 : if (current_loops != NULL)
986 : : {
987 : : /* If we do not split a loop header, then both blocks belong to the
988 : : same loop. In case we split loop header and do not redirect the
989 : : latch edge to DUMMY, then DUMMY belongs to the outer loop, and
990 : : BB becomes the new header. If latch is not recorded for the loop,
991 : : we leave this updating on the caller (this may only happen during
992 : : loop analysis). */
993 : 91845 : loop = dummy->loop_father;
994 : 91845 : if (loop->header == dummy
995 : 91689 : && loop->latch != NULL
996 : 159538 : && find_edge (loop->latch, dummy) == NULL)
997 : : {
998 : 67661 : remove_bb_from_loops (dummy);
999 : 67661 : loop->header = bb;
1000 : :
1001 : 67661 : cloop = loop;
1002 : 219044 : FOR_EACH_EDGE (e, ei, dummy->preds)
1003 : : {
1004 : 151383 : cloop = find_common_loop (cloop, e->src->loop_father);
1005 : : }
1006 : 67661 : add_bb_to_loop (dummy, cloop);
1007 : : }
1008 : :
1009 : : /* In case we split loop latch, update it. */
1010 : 305529 : for (ploop = loop; ploop; ploop = loop_outer (ploop))
1011 : 213684 : if (ploop->latch == dummy)
1012 : 0 : ploop->latch = bb;
1013 : : }
1014 : :
1015 : 91845 : cfg_hooks->make_forwarder_block (fallthru);
1016 : :
1017 : 91845 : return fallthru;
1018 : : }
1019 : :
1020 : : /* Try to make the edge fallthru. */
1021 : :
1022 : : void
1023 : 818842 : tidy_fallthru_edge (edge e)
1024 : : {
1025 : 818842 : if (cfg_hooks->tidy_fallthru_edge)
1026 : 818842 : cfg_hooks->tidy_fallthru_edge (e);
1027 : 818842 : }
1028 : :
1029 : : /* Fix up edges that now fall through, or rather should now fall through
1030 : : but previously required a jump around now deleted blocks. Simplify
1031 : : the search by only examining blocks numerically adjacent, since this
1032 : : is how they were created.
1033 : :
1034 : : ??? This routine is currently RTL specific. */
1035 : :
1036 : : void
1037 : 452757 : tidy_fallthru_edges (void)
1038 : : {
1039 : 452757 : basic_block b, c;
1040 : :
1041 : 452757 : if (!cfg_hooks->tidy_fallthru_edge)
1042 : : return;
1043 : :
1044 : 129462 : if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1045 : : return;
1046 : :
1047 : 4294515 : FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb,
1048 : : EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb, next_bb)
1049 : : {
1050 : 4165053 : edge s;
1051 : :
1052 : 4165053 : c = b->next_bb;
1053 : :
1054 : : /* We care about simple conditional or unconditional jumps with
1055 : : a single successor.
1056 : :
1057 : : If we had a conditional branch to the next instruction when
1058 : : CFG was built, then there will only be one out edge for the
1059 : : block which ended with the conditional branch (since we do
1060 : : not create duplicate edges).
1061 : :
1062 : : Furthermore, the edge will be marked as a fallthru because we
1063 : : merge the flags for the duplicate edges. So we do not want to
1064 : : check that the edge is not a FALLTHRU edge. */
1065 : :
1066 : 6138644 : if (single_succ_p (b))
1067 : : {
1068 : 1973591 : s = single_succ_edge (b);
1069 : 1973591 : if (! (s->flags & EDGE_COMPLEX)
1070 : 1913347 : && s->dest == c
1071 : 2817948 : && !(JUMP_P (BB_END (b)) && CROSSING_JUMP_P (BB_END (b))))
1072 : 811818 : tidy_fallthru_edge (s);
1073 : : }
1074 : : }
1075 : : }
1076 : :
1077 : : /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1078 : : (and possibly create new basic block) to make edge non-fallthru.
1079 : : Return newly created BB or NULL if none. */
1080 : :
1081 : : basic_block
1082 : 788818 : force_nonfallthru (edge e)
1083 : : {
1084 : 788818 : basic_block ret, src = e->src;
1085 : :
1086 : 788818 : if (!cfg_hooks->force_nonfallthru)
1087 : 0 : internal_error ("%s does not support force_nonfallthru",
1088 : : cfg_hooks->name);
1089 : :
1090 : 788818 : ret = cfg_hooks->force_nonfallthru (e);
1091 : 788818 : if (ret != NULL)
1092 : : {
1093 : 184192 : if (dom_info_available_p (CDI_DOMINATORS))
1094 : 9486 : set_immediate_dominator (CDI_DOMINATORS, ret, src);
1095 : :
1096 : 184192 : if (current_loops != NULL)
1097 : : {
1098 : 69032 : basic_block pred = single_pred (ret);
1099 : 69032 : basic_block succ = single_succ (ret);
1100 : 69032 : class loop *loop
1101 : 69032 : = find_common_loop (pred->loop_father, succ->loop_father);
1102 : 69032 : rescan_loop_exit (e, false, true);
1103 : 69032 : add_bb_to_loop (ret, loop);
1104 : :
1105 : : /* If we split the latch edge of loop adjust the latch block. */
1106 : 69032 : if (loop->latch == pred
1107 : 3922 : && loop->header == succ)
1108 : 3922 : loop->latch = ret;
1109 : : }
1110 : : }
1111 : :
1112 : 788818 : return ret;
1113 : : }
1114 : :
1115 : : /* Returns true if we can duplicate basic block BB. */
1116 : :
1117 : : bool
1118 : 18075394 : can_duplicate_block_p (const_basic_block bb)
1119 : : {
1120 : 18075394 : if (!cfg_hooks->can_duplicate_block_p)
1121 : 0 : internal_error ("%s does not support can_duplicate_block_p",
1122 : : cfg_hooks->name);
1123 : :
1124 : 18075394 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1125 : : return false;
1126 : :
1127 : 18075394 : return cfg_hooks->can_duplicate_block_p (bb);
1128 : : }
1129 : :
1130 : : /* Duplicate basic block BB, place it after AFTER (if non-null) and redirect
1131 : : edge E to it (if non-null). Return the new basic block.
1132 : :
1133 : : If BB contains a returns_twice call, the caller is responsible for recreating
1134 : : incoming abnormal edges corresponding to the "second return" for the copy.
1135 : : gimple_can_duplicate_bb_p rejects such blocks, while RTL likes to live
1136 : : dangerously.
1137 : :
1138 : : If BB has incoming abnormal edges for some other reason, their destinations
1139 : : should be tied to label(s) of the original BB and not the copy. */
1140 : :
1141 : : basic_block
1142 : 4630049 : duplicate_block (basic_block bb, edge e, basic_block after, copy_bb_data *id)
1143 : : {
1144 : 4630049 : edge s, n;
1145 : 4630049 : basic_block new_bb;
1146 : 4904468 : profile_count new_count = e ? e->count (): profile_count::uninitialized ();
1147 : 4630049 : edge_iterator ei;
1148 : :
1149 : 4630049 : if (!cfg_hooks->duplicate_block)
1150 : 0 : internal_error ("%s does not support duplicate_block",
1151 : : cfg_hooks->name);
1152 : :
1153 : 4630049 : if (bb->count < new_count)
1154 : 1190 : new_count = bb->count;
1155 : :
1156 : 4630049 : gcc_checking_assert (can_duplicate_block_p (bb));
1157 : :
1158 : 4630049 : new_bb = cfg_hooks->duplicate_block (bb, id);
1159 : 4630049 : if (after)
1160 : 4256067 : move_block_after (new_bb, after);
1161 : :
1162 : 4630049 : new_bb->flags = (bb->flags & ~BB_DUPLICATED);
1163 : 12782802 : FOR_EACH_EDGE (s, ei, bb->succs)
1164 : : {
1165 : : /* Since we are creating edges from a new block to successors
1166 : : of another block (which therefore are known to be disjoint), there
1167 : : is no need to actually check for duplicated edges. */
1168 : 8152753 : n = unchecked_make_edge (new_bb, s->dest, s->flags);
1169 : 8152753 : n->probability = s->probability;
1170 : 8152753 : n->aux = s->aux;
1171 : : }
1172 : :
1173 : 4630049 : if (e)
1174 : : {
1175 : 274419 : new_bb->count = new_count;
1176 : 274419 : bb->count -= new_count;
1177 : :
1178 : 274419 : redirect_edge_and_branch_force (e, new_bb);
1179 : : }
1180 : : else
1181 : 4355630 : new_bb->count = bb->count;
1182 : :
1183 : 4630049 : set_bb_original (new_bb, bb);
1184 : 4630049 : set_bb_copy (bb, new_bb);
1185 : :
1186 : : /* Add the new block to the copy of the loop of BB, or directly to the loop
1187 : : of BB if the loop is not being copied. */
1188 : 4630049 : if (current_loops != NULL)
1189 : : {
1190 : 4329949 : class loop *cloop = bb->loop_father;
1191 : 4329949 : class loop *copy = get_loop_copy (cloop);
1192 : : /* If we copied the loop header block but not the loop
1193 : : we have created a loop with multiple entries. Ditch the loop,
1194 : : add the new block to the outer loop and arrange for a fixup. */
1195 : 4329949 : if (!copy
1196 : 379450 : && cloop->header == bb)
1197 : : {
1198 : 373 : add_bb_to_loop (new_bb, loop_outer (cloop));
1199 : 373 : mark_loop_for_removal (cloop);
1200 : : }
1201 : : else
1202 : : {
1203 : 4329576 : add_bb_to_loop (new_bb, copy ? copy : cloop);
1204 : : /* If we copied the loop latch block but not the loop, adjust
1205 : : loop state. */
1206 : 4329576 : if (!copy
1207 : 379077 : && cloop->latch == bb)
1208 : : {
1209 : 598 : cloop->latch = NULL;
1210 : 598 : loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
1211 : : }
1212 : : }
1213 : : }
1214 : :
1215 : 4630049 : return new_bb;
1216 : : }
1217 : :
1218 : : /* Return 1 if BB ends with a call, possibly followed by some
1219 : : instructions that must stay with the call, 0 otherwise. */
1220 : :
1221 : : bool
1222 : 9843579 : block_ends_with_call_p (basic_block bb)
1223 : : {
1224 : 9843579 : if (!cfg_hooks->block_ends_with_call_p)
1225 : 0 : internal_error ("%s does not support block_ends_with_call_p", cfg_hooks->name);
1226 : :
1227 : 9843579 : return (cfg_hooks->block_ends_with_call_p) (bb);
1228 : : }
1229 : :
1230 : : /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
1231 : :
1232 : : bool
1233 : 1741 : block_ends_with_condjump_p (const_basic_block bb)
1234 : : {
1235 : 1741 : if (!cfg_hooks->block_ends_with_condjump_p)
1236 : 0 : internal_error ("%s does not support block_ends_with_condjump_p",
1237 : : cfg_hooks->name);
1238 : :
1239 : 1741 : return (cfg_hooks->block_ends_with_condjump_p) (bb);
1240 : : }
1241 : :
1242 : : /* Add fake edges to the function exit for any non constant and non noreturn
1243 : : calls, volatile inline assembly in the bitmap of blocks specified by
1244 : : BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
1245 : : that were split.
1246 : :
1247 : : The goal is to expose cases in which entering a basic block does not imply
1248 : : that all subsequent instructions must be executed. */
1249 : :
1250 : : int
1251 : 2543 : flow_call_edges_add (sbitmap blocks)
1252 : : {
1253 : 2543 : if (!cfg_hooks->flow_call_edges_add)
1254 : 0 : internal_error ("%s does not support flow_call_edges_add",
1255 : : cfg_hooks->name);
1256 : :
1257 : 2543 : return (cfg_hooks->flow_call_edges_add) (blocks);
1258 : : }
1259 : :
1260 : : /* This function is called immediately after edge E is added to the
1261 : : edge vector E->dest->preds. */
1262 : :
1263 : : void
1264 : 203030846 : execute_on_growing_pred (edge e)
1265 : : {
1266 : 203030846 : if (! (e->dest->flags & BB_DUPLICATED)
1267 : 200766701 : && cfg_hooks->execute_on_growing_pred)
1268 : 159884543 : cfg_hooks->execute_on_growing_pred (e);
1269 : 203030846 : }
1270 : :
1271 : : /* This function is called immediately before edge E is removed from
1272 : : the edge vector E->dest->preds. */
1273 : :
1274 : : void
1275 : 171649134 : execute_on_shrinking_pred (edge e)
1276 : : {
1277 : 171649134 : if (! (e->dest->flags & BB_DUPLICATED)
1278 : 169384989 : && cfg_hooks->execute_on_shrinking_pred)
1279 : 131137110 : cfg_hooks->execute_on_shrinking_pred (e);
1280 : 171649134 : }
1281 : :
1282 : : /* This is used inside loop versioning when we want to insert
1283 : : stmts/insns on the edges, which have a different behavior
1284 : : in tree's and in RTL, so we made a CFG hook. */
1285 : : void
1286 : 38778 : lv_flush_pending_stmts (edge e)
1287 : : {
1288 : 38778 : if (cfg_hooks->flush_pending_stmts)
1289 : 38778 : cfg_hooks->flush_pending_stmts (e);
1290 : 38778 : }
1291 : :
1292 : : /* Loop versioning uses the duplicate_loop_body_to_header_edge to create
1293 : : a new version of the loop basic-blocks, the parameters here are
1294 : : exactly the same as in duplicate_loop_body_to_header_edge or
1295 : : tree_duplicate_loop_body_to_header_edge; while in tree-ssa there is
1296 : : additional work to maintain ssa information that's why there is
1297 : : a need to call the tree_duplicate_loop_body_to_header_edge rather
1298 : : than duplicate_loop_body_to_header_edge when we are in tree mode. */
1299 : : bool
1300 : 38788 : cfg_hook_duplicate_loop_body_to_header_edge (class loop *loop, edge e,
1301 : : unsigned int ndupl,
1302 : : sbitmap wont_exit, edge orig,
1303 : : vec<edge> *to_remove, int flags)
1304 : : {
1305 : 38788 : gcc_assert (cfg_hooks->cfg_hook_duplicate_loop_body_to_header_edge);
1306 : 38788 : return cfg_hooks->cfg_hook_duplicate_loop_body_to_header_edge (
1307 : 38788 : loop, e, ndupl, wont_exit, orig, to_remove, flags);
1308 : : }
1309 : :
1310 : : /* Conditional jumps are represented differently in trees and RTL,
1311 : : this hook takes a basic block that is known to have a cond jump
1312 : : at its end and extracts the taken and not taken edges out of it
1313 : : and store it in E1 and E2 respectively. */
1314 : : void
1315 : 0 : extract_cond_bb_edges (basic_block b, edge *e1, edge *e2)
1316 : : {
1317 : 0 : gcc_assert (cfg_hooks->extract_cond_bb_edges);
1318 : 0 : cfg_hooks->extract_cond_bb_edges (b, e1, e2);
1319 : 0 : }
1320 : :
1321 : : /* Responsible for updating the ssa info (PHI nodes) on the
1322 : : new condition basic block that guards the versioned loop. */
1323 : : void
1324 : 38778 : lv_adjust_loop_header_phi (basic_block first, basic_block second,
1325 : : basic_block new_block, edge e)
1326 : : {
1327 : 38778 : if (cfg_hooks->lv_adjust_loop_header_phi)
1328 : 38778 : cfg_hooks->lv_adjust_loop_header_phi (first, second, new_block, e);
1329 : 38778 : }
1330 : :
1331 : : /* Conditions in trees and RTL are different so we need
1332 : : a different handling when we add the condition to the
1333 : : versioning code. */
1334 : : void
1335 : 38778 : lv_add_condition_to_bb (basic_block first, basic_block second,
1336 : : basic_block new_block, void *cond)
1337 : : {
1338 : 38778 : gcc_assert (cfg_hooks->lv_add_condition_to_bb);
1339 : 38778 : cfg_hooks->lv_add_condition_to_bb (first, second, new_block, cond);
1340 : 38778 : }
1341 : :
1342 : : /* Checks whether all N blocks in BBS array can be copied. */
1343 : : bool
1344 : 3227826 : can_copy_bbs_p (basic_block *bbs, unsigned n)
1345 : : {
1346 : 3227826 : unsigned i;
1347 : 3227826 : edge e;
1348 : 3227826 : int ret = true;
1349 : :
1350 : 11593192 : for (i = 0; i < n; i++)
1351 : 8365366 : bbs[i]->flags |= BB_DUPLICATED;
1352 : :
1353 : 11448151 : for (i = 0; i < n; i++)
1354 : : {
1355 : : /* In case we should redirect abnormal edge during duplication, fail. */
1356 : 8231179 : edge_iterator ei;
1357 : 21917009 : FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1358 : 13694989 : if ((e->flags & EDGE_ABNORMAL)
1359 : 113387 : && (e->dest->flags & BB_DUPLICATED))
1360 : : {
1361 : 9159 : ret = false;
1362 : 9159 : goto end;
1363 : : }
1364 : :
1365 : 8222020 : if (!can_duplicate_block_p (bbs[i]))
1366 : : {
1367 : 1695 : ret = false;
1368 : 1695 : break;
1369 : : }
1370 : : }
1371 : :
1372 : 3216972 : end:
1373 : 11593192 : for (i = 0; i < n; i++)
1374 : 8365366 : bbs[i]->flags &= ~BB_DUPLICATED;
1375 : :
1376 : 3227826 : return ret;
1377 : : }
1378 : :
1379 : : /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1380 : : are placed into array NEW_BBS in the same order. Edges from basic blocks
1381 : : in BBS are also duplicated and copies of those that lead into BBS are
1382 : : redirected to appropriate newly created block. The function assigns bbs
1383 : : into loops (copy of basic block bb is assigned to bb->loop_father->copy
1384 : : loop, so this must be set up correctly in advance)
1385 : :
1386 : : If UPDATE_DOMINANCE is true then this function updates dominators locally
1387 : : (LOOPS structure that contains the information about dominators is passed
1388 : : to enable this), otherwise it does not update the dominator information
1389 : : and it assumed that the caller will do this, perhaps by destroying and
1390 : : recreating it instead of trying to do an incremental update like this
1391 : : function does when update_dominance is true.
1392 : :
1393 : : BASE is the superloop to that basic block belongs; if its header or latch
1394 : : is copied, we do not set the new blocks as header or latch.
1395 : :
1396 : : Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1397 : : also in the same order.
1398 : :
1399 : : Newly created basic blocks are put after the basic block AFTER in the
1400 : : instruction stream, and the order of the blocks in BBS array is preserved. */
1401 : :
1402 : : void
1403 : 2403768 : copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1404 : : edge *edges, unsigned num_edges, edge *new_edges,
1405 : : class loop *base, basic_block after, bool update_dominance)
1406 : : {
1407 : 2403768 : unsigned i, j;
1408 : 2403768 : basic_block bb, new_bb, dom_bb;
1409 : 2403768 : edge e;
1410 : 2403768 : copy_bb_data id;
1411 : :
1412 : : /* Mark the blocks to be copied. This is used by edge creation hooks
1413 : : to decide whether to reallocate PHI nodes capacity to avoid reallocating
1414 : : PHIs in the set of source BBs. */
1415 : 6385586 : for (i = 0; i < n; i++)
1416 : 3981818 : bbs[i]->flags |= BB_DUPLICATED;
1417 : :
1418 : : /* Duplicate bbs, update dominators, assign bbs to loops. */
1419 : 6385586 : for (i = 0; i < n; i++)
1420 : : {
1421 : : /* Duplicate. */
1422 : 3981818 : bb = bbs[i];
1423 : 3981818 : new_bb = new_bbs[i] = duplicate_block (bb, NULL, after, &id);
1424 : 3981818 : after = new_bb;
1425 : 3981818 : if (bb->loop_father)
1426 : : {
1427 : : /* Possibly set loop header. */
1428 : 3981818 : if (bb->loop_father->header == bb && bb->loop_father != base)
1429 : 40776 : new_bb->loop_father->header = new_bb;
1430 : : /* Or latch. */
1431 : 3981818 : if (bb->loop_father->latch == bb && bb->loop_father != base)
1432 : 40776 : new_bb->loop_father->latch = new_bb;
1433 : : }
1434 : : }
1435 : :
1436 : : /* Set dominators. */
1437 : 2403768 : if (update_dominance)
1438 : : {
1439 : 3349535 : for (i = 0; i < n; i++)
1440 : : {
1441 : 2212513 : bb = bbs[i];
1442 : 2212513 : new_bb = new_bbs[i];
1443 : :
1444 : 2212513 : dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1445 : 2212513 : if (dom_bb->flags & BB_DUPLICATED)
1446 : : {
1447 : 1075491 : dom_bb = get_bb_copy (dom_bb);
1448 : 1075491 : set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1449 : : }
1450 : : }
1451 : : }
1452 : :
1453 : : /* Redirect edges. */
1454 : 6385586 : for (i = 0; i < n; i++)
1455 : : {
1456 : 3981818 : edge_iterator ei;
1457 : 3981818 : new_bb = new_bbs[i];
1458 : 3981818 : bb = bbs[i];
1459 : :
1460 : 11053801 : FOR_EACH_EDGE (e, ei, new_bb->succs)
1461 : : {
1462 : 7071983 : if (!(e->dest->flags & BB_DUPLICATED))
1463 : 4807838 : continue;
1464 : 2264145 : redirect_edge_and_branch_force (e, get_bb_copy (e->dest));
1465 : : }
1466 : : }
1467 : 5341107 : for (j = 0; j < num_edges; j++)
1468 : : {
1469 : 2937339 : if (!edges[j])
1470 : 79662 : new_edges[j] = NULL;
1471 : : else
1472 : : {
1473 : 2857677 : basic_block src = edges[j]->src;
1474 : 2857677 : basic_block dest = edges[j]->dest;
1475 : 2857677 : if (src->flags & BB_DUPLICATED)
1476 : 2857677 : src = get_bb_copy (src);
1477 : 2857677 : if (dest->flags & BB_DUPLICATED)
1478 : 495288 : dest = get_bb_copy (dest);
1479 : 2857677 : new_edges[j] = find_edge (src, dest);
1480 : : }
1481 : : }
1482 : :
1483 : : /* Clear information about duplicates. */
1484 : 6385586 : for (i = 0; i < n; i++)
1485 : 3981818 : bbs[i]->flags &= ~BB_DUPLICATED;
1486 : 2403768 : }
1487 : :
1488 : : /* Return true if BB contains only labels or non-executable
1489 : : instructions */
1490 : : bool
1491 : 14157309 : empty_block_p (basic_block bb)
1492 : : {
1493 : 14157309 : gcc_assert (cfg_hooks->empty_block_p);
1494 : 14157309 : return cfg_hooks->empty_block_p (bb);
1495 : : }
1496 : :
1497 : : /* Split a basic block if it ends with a conditional branch and if
1498 : : the other part of the block is not empty. */
1499 : : basic_block
1500 : 556 : split_block_before_cond_jump (basic_block bb)
1501 : : {
1502 : 556 : gcc_assert (cfg_hooks->split_block_before_cond_jump);
1503 : 556 : return cfg_hooks->split_block_before_cond_jump (bb);
1504 : : }
1505 : :
1506 : : /* Work-horse for passes.cc:check_profile_consistency.
1507 : : Do book-keeping of the CFG for the profile consistency checker.
1508 : : Store the counting in RECORD. */
1509 : :
1510 : : void
1511 : 0 : profile_record_check_consistency (profile_record *record)
1512 : : {
1513 : 0 : basic_block bb;
1514 : 0 : edge_iterator ei;
1515 : 0 : edge e;
1516 : :
1517 : 0 : FOR_ALL_BB_FN (bb, cfun)
1518 : : {
1519 : 0 : if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
1520 : 0 : && profile_status_for_fn (cfun) != PROFILE_ABSENT
1521 : 0 : && EDGE_COUNT (bb->succs))
1522 : : {
1523 : 0 : sreal sum = 0;
1524 : 0 : bool found = false;
1525 : 0 : FOR_EACH_EDGE (e, ei, bb->succs)
1526 : : {
1527 : 0 : if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
1528 : 0 : found = true;
1529 : 0 : if (e->probability.initialized_p ())
1530 : 0 : sum += e->probability.to_sreal ();
1531 : : }
1532 : 0 : double dsum = sum.to_double ();
1533 : 0 : if (found && (dsum < 0.9 || dsum > 1.1)
1534 : 0 : && !(bb->count == profile_count::zero ()))
1535 : : {
1536 : 0 : record->num_mismatched_prob_out++;
1537 : 0 : dsum = dsum > 1 ? dsum - 1 : 1 - dsum;
1538 : 0 : if (profile_info)
1539 : : {
1540 : 0 : if (ENTRY_BLOCK_PTR_FOR_FN
1541 : 0 : (cfun)->count.ipa ().initialized_p ()
1542 : 0 : && ENTRY_BLOCK_PTR_FOR_FN
1543 : 0 : (cfun)->count.ipa ().nonzero_p ()
1544 : 0 : && bb->count.ipa ().initialized_p ())
1545 : 0 : record->dyn_mismatched_prob_out
1546 : 0 : += dsum * bb->count.ipa ().to_gcov_type ();
1547 : : }
1548 : 0 : else if (bb->count.initialized_p ())
1549 : 0 : record->dyn_mismatched_prob_out
1550 : 0 : += dsum * bb->count.to_sreal_scale
1551 : 0 : (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count).to_double ();
1552 : : }
1553 : : }
1554 : 0 : if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1555 : 0 : && profile_status_for_fn (cfun) != PROFILE_ABSENT)
1556 : : {
1557 : 0 : profile_count lsum = profile_count::zero ();
1558 : 0 : FOR_EACH_EDGE (e, ei, bb->preds)
1559 : 0 : lsum += e->count ();
1560 : 0 : if (lsum.differs_from_p (bb->count))
1561 : : {
1562 : 0 : record->num_mismatched_count_in++;
1563 : 0 : profile_count max;
1564 : 0 : if (lsum < bb->count)
1565 : 0 : max = bb->count;
1566 : : else
1567 : 0 : max = lsum;
1568 : 0 : if (profile_info)
1569 : : {
1570 : 0 : if (ENTRY_BLOCK_PTR_FOR_FN
1571 : 0 : (cfun)->count.ipa ().initialized_p ()
1572 : 0 : && ENTRY_BLOCK_PTR_FOR_FN
1573 : 0 : (cfun)->count.ipa ().nonzero_p ()
1574 : 0 : && max.ipa ().initialized_p ())
1575 : 0 : record->dyn_mismatched_count_in
1576 : 0 : += max.ipa ().to_gcov_type ();
1577 : : }
1578 : 0 : else if (bb->count.initialized_p ())
1579 : 0 : record->dyn_mismatched_prob_out
1580 : 0 : += max.to_sreal_scale
1581 : 0 : (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count).to_double ();
1582 : : }
1583 : : }
1584 : 0 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
1585 : : || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1586 : 0 : continue;
1587 : : }
1588 : 0 : }
1589 : :
1590 : : /* Work-horse for passes.cc:acount_profile.
1591 : : Do book-keeping of the CFG for the profile accounting.
1592 : : Store the counting in RECORD. */
1593 : :
1594 : : void
1595 : 0 : profile_record_account_profile (profile_record *record)
1596 : : {
1597 : 0 : basic_block bb;
1598 : :
1599 : 0 : FOR_ALL_BB_FN (bb, cfun)
1600 : : {
1601 : 0 : gcc_assert (cfg_hooks->account_profile_record);
1602 : 0 : cfg_hooks->account_profile_record (bb, record);
1603 : : }
1604 : 0 : }
1605 : :
1606 : : #if __GNUC__ >= 10
1607 : : # pragma GCC diagnostic pop
1608 : : #endif
|
