1	/* CFG cleanup for trees.
2	Copyright (C) 2001-2023 Free Software Foundation, Inc.
3
4	This file is part of GCC.
5
6	GCC is free software; you can redistribute it and/or modify
7	it under the terms of the GNU General Public License as published by
8	the Free Software Foundation; either version 3, or (at your option)
9	any later version.
10
11	GCC is distributed in the hope that it will be useful,
12	but WITHOUT ANY WARRANTY; without even the implied warranty of
13	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14	GNU General Public License for more details.
15
16	You should have received a copy of the GNU General Public License
17	along with GCC; see the file COPYING3. If not see
18	<http://www.gnu.org/licenses/>. */
19
20	#include "config.h"
21	#include "system.h"
22	#include "coretypes.h"
23	#include "backend.h"
24	#include "rtl.h"
25	#include "tree.h"
26	#include "gimple.h"
27	#include "cfghooks.h"
28	#include "tree-pass.h"
29	#include "ssa.h"
30	#include "diagnostic-core.h"
31	#include "fold-const.h"
32	#include "cfganal.h"
33	#include "cfgcleanup.h"
34	#include "tree-eh.h"
35	#include "gimplify.h"
36	#include "gimple-iterator.h"
37	#include "tree-cfg.h"
38	#include "tree-ssa-loop-manip.h"
39	#include "tree-dfa.h"
40	#include "tree-ssa.h"
41	#include "cfgloop.h"
42	#include "tree-scalar-evolution.h"
43	#include "gimple-match.h"
44	#include "gimple-fold.h"
45	#include "tree-ssa-loop-niter.h"
46	#include "cgraph.h"
47	#include "tree-into-ssa.h"
48	#include "tree-cfgcleanup.h"
49
50
51	/* The set of blocks in that at least one of the following changes happened:
52	-- the statement at the end of the block was changed
53	-- the block was newly created
54	-- the set of the predecessors of the block changed
55	-- the set of the successors of the block changed
56	??? Maybe we could track these changes separately, since they determine
57	what cleanups it makes sense to try on the block. */
58	bitmap cfgcleanup_altered_bbs;
59
60	/* Remove any fallthru edge from EV. Return true if an edge was removed. */
61
62	static bool
63	remove_fallthru_edge (vec<edge, va_gc> *ev)
64	{
65	edge_iterator ei;
66	edge e;
67
68	FOR_EACH_EDGE (e, ei, ev)
69	if ((e->flags & EDGE_FALLTHRU) != 0)
70	{
71	if (e->flags & EDGE_COMPLEX)
72	e->flags &= ~EDGE_FALLTHRU;
73	else
74	remove_edge_and_dominated_blocks (e);
75	return true;
76	}
77	return false;
78	}
79
80	/* Convert a SWTCH with single non-default case to gcond and replace it
81	at GSI. */
82
83	static bool
84	convert_single_case_switch (gswitch *swtch, gimple_stmt_iterator &gsi)
85	{
86	if (gimple_switch_num_labels (gs: swtch) != 2)
87	return false;
88
89	tree index = gimple_switch_index (gs: swtch);
90	tree label = gimple_switch_label (gs: swtch, index: 1);
91	tree low = CASE_LOW (label);
92	tree high = CASE_HIGH (label);
93
94	basic_block default_bb = gimple_switch_default_bb (cfun, swtch);
95	basic_block case_bb = label_to_block (cfun, CASE_LABEL (label));
96
97	basic_block bb = gimple_bb (g: swtch);
98	gcond *cond;
99
100	/* Replace switch statement with condition statement. */
101	if (high)
102	{
103	tree lhs, rhs;
104	if (range_check_type (TREE_TYPE (index)) == NULL_TREE)
105	return false;
106	generate_range_test (bb, index, low, high, lhs: &lhs, rhs: &rhs);
107	cond = gimple_build_cond (LE_EXPR, lhs, rhs, NULL_TREE, NULL_TREE);
108	}
109	else
110	cond = gimple_build_cond (EQ_EXPR, index,
111	fold_convert (TREE_TYPE (index), low),
112	NULL_TREE, NULL_TREE);
113
114	gsi_replace (&gsi, cond, true);
115
116	/* Update edges. */
117	edge case_edge = find_edge (bb, case_bb);
118	edge default_edge = find_edge (bb, default_bb);
119
120	case_edge->flags |= EDGE_TRUE_VALUE;
121	default_edge->flags |= EDGE_FALSE_VALUE;
122	return true;
123	}
124
125	/* Disconnect an unreachable block in the control expression starting
126	at block BB. */
127
128	static bool
129	cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi)
130	{
131	edge taken_edge;
132	bool retval = false;
133	gimple *stmt = gsi_stmt (i: gsi);
134
135	if (!single_succ_p (bb))
136	{
137	edge e;
138	edge_iterator ei;
139	bool warned;
140	tree val = NULL_TREE;
141
142	/* Try to convert a switch with just a single non-default case to
143	GIMPLE condition. */
144	if (gimple_code (g: stmt) == GIMPLE_SWITCH
145	&& convert_single_case_switch (swtch: as_a<gswitch *> (p: stmt), gsi))
146	stmt = gsi_stmt (i: gsi);
147
148	fold_defer_overflow_warnings ();
149	switch (gimple_code (g: stmt))
150	{
151	case GIMPLE_COND:
152	{
153	gimple_match_op res_op;
154	if (gimple_simplify (stmt, &res_op, NULL, no_follow_ssa_edges,
155	no_follow_ssa_edges)
156	&& res_op.code == INTEGER_CST)
157	val = res_op.ops[0];
158	}
159	break;
160
161	case GIMPLE_SWITCH:
162	val = gimple_switch_index (gs: as_a <gswitch *> (p: stmt));
163	break;
164
165	default:
166	;
167	}
168	taken_edge = find_taken_edge (bb, val);
169	if (!taken_edge)
170	{
171	fold_undefer_and_ignore_overflow_warnings ();
172	return false;
173	}
174
175	/* Remove all the edges except the one that is always executed. */
176	warned = false;
177	for (ei = ei_start (bb->succs); (e = ei_safe_edge (i: ei)); )
178	{
179	if (e != taken_edge)
180	{
181	if (!warned)
182	{
183	fold_undefer_overflow_warnings
184	(true, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
185	warned = true;
186	}
187
188	taken_edge->probability += e->probability;
189	remove_edge_and_dominated_blocks (e);
190	retval = true;
191	}
192	else
193	ei_next (i: &ei);
194	}
195	if (!warned)
196	fold_undefer_and_ignore_overflow_warnings ();
197	}
198	else
199	taken_edge = single_succ_edge (bb);
200
201	bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
202	gsi_remove (&gsi, true);
203	taken_edge->flags = EDGE_FALLTHRU;
204
205	return retval;
206	}
207
208	/* Cleanup the GF_CALL_CTRL_ALTERING flag according to
209	to updated gimple_call_flags. */
210
211	static void
212	cleanup_call_ctrl_altering_flag (basic_block bb, gimple *bb_end)
213	{
214	if (!is_gimple_call (gs: bb_end)
215	|| !gimple_call_ctrl_altering_p (gs: bb_end)
216	|| (/* IFN_UNIQUE should be the last insn, to make checking for it
217	as cheap as possible. */
218	gimple_call_internal_p (gs: bb_end)
219	&& gimple_call_internal_unique_p (gs: bb_end)))
220	return;
221
222	int flags = gimple_call_flags (bb_end);
223	if (!(flags & ECF_NORETURN)
224	&& (((flags & (ECF_CONST | ECF_PURE))
225	&& !(flags & ECF_LOOPING_CONST_OR_PURE))
226	|| (flags & ECF_LEAF)))
227	gimple_call_set_ctrl_altering (s: bb_end, ctrl_altering_p: false);
228	else
229	{
230	edge_iterator ei;
231	edge e;
232	bool found = false;
233	FOR_EACH_EDGE (e, ei, bb->succs)
234	if (e->flags & EDGE_FALLTHRU)
235	found = true;
236	else if (e->flags & EDGE_ABNORMAL)
237	{
238	found = false;
239	break;
240	}
241	/* If there's no abnormal edge and a fallthru edge the call
242	isn't control-altering anymore. */
243	if (found)
244	gimple_call_set_ctrl_altering (s: bb_end, ctrl_altering_p: false);
245	}
246	}
247
248	/* Try to remove superfluous control structures in basic block BB. Returns
249	true if anything changes. */
250
251	static bool
252	cleanup_control_flow_bb (basic_block bb)
253	{
254	gimple_stmt_iterator gsi;
255	bool retval = false;
256	gimple *stmt;
257
258	/* If the last statement of the block could throw and now cannot,
259	we need to prune cfg. */
260	retval |= gimple_purge_dead_eh_edges (bb);
261
262	gsi = gsi_last_nondebug_bb (bb);
263	if (gsi_end_p (i: gsi))
264	return retval;
265
266	stmt = gsi_stmt (i: gsi);
267
268	/* Try to cleanup ctrl altering flag for call which ends bb. */
269	cleanup_call_ctrl_altering_flag (bb, bb_end: stmt);
270
271	if (gimple_code (g: stmt) == GIMPLE_COND
272	|| gimple_code (g: stmt) == GIMPLE_SWITCH)
273	{
274	gcc_checking_assert (gsi_stmt (gsi_last_bb (bb)) == stmt);
275	retval |= cleanup_control_expr_graph (bb, gsi);
276	}
277	else if (gimple_code (g: stmt) == GIMPLE_GOTO
278	&& TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR
279	&& (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt), 0))
280	== LABEL_DECL))
281	{
282	/* If we had a computed goto which has a compile-time determinable
283	destination, then we can eliminate the goto. */
284	edge e;
285	tree label;
286	edge_iterator ei;
287	basic_block target_block;
288
289	gcc_checking_assert (gsi_stmt (gsi_last_bb (bb)) == stmt);
290	/* First look at all the outgoing edges. Delete any outgoing
291	edges which do not go to the right block. For the one
292	edge which goes to the right block, fix up its flags. */
293	label = TREE_OPERAND (gimple_goto_dest (stmt), 0);
294	if (DECL_CONTEXT (label) != cfun->decl)
295	return retval;
296	target_block = label_to_block (cfun, label);
297	for (ei = ei_start (bb->succs); (e = ei_safe_edge (i: ei)); )
298	{
299	if (e->dest != target_block)
300	remove_edge_and_dominated_blocks (e);
301	else
302	{
303	/* Turn off the EDGE_ABNORMAL flag. */
304	e->flags &= ~EDGE_ABNORMAL;
305
306	/* And set EDGE_FALLTHRU. */
307	e->flags |= EDGE_FALLTHRU;
308	ei_next (i: &ei);
309	}
310	}
311
312	bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
313	bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index);
314
315	/* Remove the GOTO_EXPR as it is not needed. The CFG has all the
316	relevant information we need. */
317	gsi_remove (&gsi, true);
318	retval = true;
319	}
320
321	/* Check for indirect calls that have been turned into
322	noreturn calls. */
323	else if (is_gimple_call (gs: stmt)
324	&& gimple_call_noreturn_p (s: stmt))
325	{
326	/* If there are debug stmts after the noreturn call, remove them
327	now, they should be all unreachable anyway. */
328	for (gsi_next (i: &gsi); !gsi_end_p (i: gsi); )
329	gsi_remove (&gsi, true);
330	if (remove_fallthru_edge (ev: bb->succs))
331	retval = true;
332	tree lhs = gimple_call_lhs (gs: stmt);
333	if (!lhs
334	|| !should_remove_lhs_p (lhs))
335	gimple_call_set_ctrl_altering (s: stmt, ctrl_altering_p: true);
336	}
337
338	return retval;
339	}
340
341	/* Return true if basic block BB does nothing except pass control
342	flow to another block and that we can safely insert a label at
343	the start of the successor block.
344
345	As a precondition, we require that BB be not equal to
346	the entry block. */
347
348	static bool
349	tree_forwarder_block_p (basic_block bb, bool phi_wanted)
350	{
351	gimple_stmt_iterator gsi;
352	location_t locus;
353
354	/* BB must have a single outgoing edge. */
355	if (single_succ_p (bb) != 1
356	/* If PHI_WANTED is false, BB must not have any PHI nodes.
357	Otherwise, BB must have PHI nodes. */
358	|| gimple_seq_empty_p (s: phi_nodes (bb)) == phi_wanted
359	/* BB may not be a predecessor of the exit block. */
360	|| single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
361	/* Nor should this be an infinite loop. */
362	|| single_succ (bb) == bb
363	/* BB may not have an abnormal outgoing edge. */
364	|| (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
365	return false;
366
367	gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
368
369	locus = single_succ_edge (bb)->goto_locus;
370
371	/* There should not be an edge coming from entry, or an EH edge. */
372	{
373	edge_iterator ei;
374	edge e;
375
376	FOR_EACH_EDGE (e, ei, bb->preds)
377	if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || (e->flags & EDGE_EH))
378	return false;
379	/* If goto_locus of any of the edges differs, prevent removing
380	the forwarder block when not optimizing. */
381	else if (!optimize
382	&& (LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
383	|| LOCATION_LOCUS (locus) != UNKNOWN_LOCATION)
384	&& e->goto_locus != locus)
385	return false;
386	}
387
388	/* Now walk through the statements backward. We can ignore labels,
389	anything else means this is not a forwarder block. */
390	for (gsi = gsi_last_bb (bb); !gsi_end_p (i: gsi); gsi_prev (i: &gsi))
391	{
392	gimple *stmt = gsi_stmt (i: gsi);
393
394	switch (gimple_code (g: stmt))
395	{
396	case GIMPLE_LABEL:
397	if (DECL_NONLOCAL (gimple_label_label (as_a <glabel *> (stmt))))
398	return false;
399	if (!optimize
400	&& (gimple_has_location (g: stmt)
401	|| LOCATION_LOCUS (locus) != UNKNOWN_LOCATION)
402	&& gimple_location (g: stmt) != locus)
403	return false;
404	break;
405
406	/* ??? For now, hope there's a corresponding debug
407	assignment at the destination. */
408	case GIMPLE_DEBUG:
409	break;
410
411	default:
412	return false;
413	}
414	}
415
416	if (current_loops)
417	{
418	basic_block dest;
419	/* Protect loop headers. */
420	if (bb_loop_header_p (bb))
421	return false;
422
423	dest = EDGE_SUCC (bb, 0)->dest;
424	/* Protect loop preheaders and latches if requested. */
425	if (dest->loop_father->header == dest)
426	{
427	if (bb->loop_father == dest->loop_father)
428	{
429	if (loops_state_satisfies_p (flags: LOOPS_HAVE_SIMPLE_LATCHES))
430	return false;
431	/* If bb doesn't have a single predecessor we'd make this
432	loop have multiple latches. Don't do that if that
433	would in turn require disambiguating them. */
434	return (single_pred_p (bb)
435	|| loops_state_satisfies_p
436	(flags: LOOPS_MAY_HAVE_MULTIPLE_LATCHES));
437	}
438	else if (bb->loop_father == loop_outer (loop: dest->loop_father))
439	return !loops_state_satisfies_p (flags: LOOPS_HAVE_PREHEADERS);
440	/* Always preserve other edges into loop headers that are
441	not simple latches or preheaders. */
442	return false;
443	}
444	}
445
446	return true;
447	}
448
449	/* If all the PHI nodes in DEST have alternatives for E1 and E2 and
450	those alternatives are equal in each of the PHI nodes, then return
451	true, else return false. */
452
453	bool
454	phi_alternatives_equal (basic_block dest, edge e1, edge e2)
455	{
456	int n1 = e1->dest_idx;
457	int n2 = e2->dest_idx;
458	gphi_iterator gsi;
459
460	for (gsi = gsi_start_phis (dest); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
461	{
462	gphi *phi = gsi.phi ();
463	tree val1 = gimple_phi_arg_def (gs: phi, index: n1);
464	tree val2 = gimple_phi_arg_def (gs: phi, index: n2);
465
466	gcc_assert (val1 != NULL_TREE);
467	gcc_assert (val2 != NULL_TREE);
468
469	if (!operand_equal_for_phi_arg_p (val1, val2))
470	return false;
471	}
472
473	return true;
474	}
475
476	/* Move debug stmts from the forwarder block SRC to DEST or PRED. */
477
478	static void
479	move_debug_stmts_from_forwarder (basic_block src,
480	basic_block dest, bool dest_single_pred_p,
481	basic_block pred, bool pred_single_succ_p)
482	{
483	if (!MAY_HAVE_DEBUG_STMTS)
484	return;
485
486	/* If we cannot move to the destination but to the predecessor do that. */
487	if (!dest_single_pred_p && pred_single_succ_p)
488	{
489	gimple_stmt_iterator gsi_to = gsi_last_bb (bb: pred);
490	if (gsi_end_p (i: gsi_to) || !stmt_ends_bb_p (gsi_stmt (i: gsi_to)))
491	{
492	for (gimple_stmt_iterator gsi = gsi_after_labels (bb: src);
493	!gsi_end_p (i: gsi);)
494	{
495	gimple *debug = gsi_stmt (i: gsi);
496	gcc_assert (is_gimple_debug (debug));
497	gsi_move_after (&gsi, &gsi_to);
498	}
499	return;
500	}
501	}
502
503	/* Else move to DEST or drop/reset them. */
504	gimple_stmt_iterator gsi_to = gsi_after_labels (bb: dest);
505	for (gimple_stmt_iterator gsi = gsi_after_labels (bb: src); !gsi_end_p (i: gsi);)
506	{
507	gimple *debug = gsi_stmt (i: gsi);
508	gcc_assert (is_gimple_debug (debug));
509	/* Move debug binds anyway, but not anything else like begin-stmt
510	markers unless they are always valid at the destination. */
511	if (dest_single_pred_p
512	|| gimple_debug_bind_p (s: debug))
513	{
514	gsi_move_before (&gsi, &gsi_to);
515	/* Reset debug-binds that are not always valid at the destination.
516	Simply dropping them can cause earlier values to become live,
517	generating wrong debug information.
518	??? There are several things we could improve here. For
519	one we might be able to move stmts to the predecessor.
520	For anther, if the debug stmt is immediately followed by a
521	(debug) definition in the destination (on a post-dominated path?)
522	we can elide it without any bad effects. */
523	if (!dest_single_pred_p)
524	{
525	gimple_debug_bind_reset_value (dbg: debug);
526	update_stmt (s: debug);
527	}
528	}
529	else
530	gsi_next (i: &gsi);
531	}
532	}
533
534	/* Removes forwarder block BB. Returns false if this failed. */
535
536	static bool
537	remove_forwarder_block (basic_block bb)
538	{
539	edge succ = single_succ_edge (bb), e, s;
540	basic_block dest = succ->dest;
541	gimple *stmt;
542	edge_iterator ei;
543	gimple_stmt_iterator gsi, gsi_to;
544
545	/* We check for infinite loops already in tree_forwarder_block_p.
546	However it may happen that the infinite loop is created
547	afterwards due to removal of forwarders. */
548	if (dest == bb)
549	return false;
550
551	/* If the destination block consists of a nonlocal label or is a
552	EH landing pad, do not merge it. */
553	stmt = first_stmt (dest);
554	if (stmt)
555	if (glabel *label_stmt = dyn_cast <glabel *> (p: stmt))
556	if (DECL_NONLOCAL (gimple_label_label (label_stmt))
557	|| EH_LANDING_PAD_NR (gimple_label_label (label_stmt)) != 0)
558	return false;
559
560	/* If there is an abnormal edge to basic block BB, but not into
561	dest, problems might occur during removal of the phi node at out
562	of ssa due to overlapping live ranges of registers.
563
564	If there is an abnormal edge in DEST, the problems would occur
565	anyway since cleanup_dead_labels would then merge the labels for
566	two different eh regions, and rest of exception handling code
567	does not like it.
568
569	So if there is an abnormal edge to BB, proceed only if there is
570	no abnormal edge to DEST and there are no phi nodes in DEST. */
571	if (bb_has_abnormal_pred (bb)
572	&& (bb_has_abnormal_pred (bb: dest)
573	|| !gimple_seq_empty_p (s: phi_nodes (bb: dest))))
574	return false;
575
576	/* If there are phi nodes in DEST, and some of the blocks that are
577	predecessors of BB are also predecessors of DEST, check that the
578	phi node arguments match. */
579	if (!gimple_seq_empty_p (s: phi_nodes (bb: dest)))
580	{
581	FOR_EACH_EDGE (e, ei, bb->preds)
582	{
583	s = find_edge (e->src, dest);
584	if (!s)
585	continue;
586
587	if (!phi_alternatives_equal (dest, e1: succ, e2: s))
588	return false;
589	}
590	}
591
592	basic_block pred = NULL;
593	if (single_pred_p (bb))
594	pred = single_pred (bb);
595	bool dest_single_pred_p = single_pred_p (bb: dest);
596
597	/* Redirect the edges. */
598	for (ei = ei_start (bb->preds); (e = ei_safe_edge (i: ei)); )
599	{
600	bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
601
602	if (e->flags & EDGE_ABNORMAL)
603	{
604	/* If there is an abnormal edge, redirect it anyway, and
605	move the labels to the new block to make it legal. */
606	s = redirect_edge_succ_nodup (e, dest);
607	}
608	else
609	s = redirect_edge_and_branch (e, dest);
610
611	if (s == e)
612	{
613	/* Copy arguments for the phi nodes, since the edge was not
614	here before. */
615	copy_phi_arg_into_existing_phi (succ, s);
616	}
617	}
618
619	/* Move nonlocal labels and computed goto targets as well as user
620	defined labels and labels with an EH landing pad number to the
621	new block, so that the redirection of the abnormal edges works,
622	jump targets end up in a sane place and debug information for
623	labels is retained. */
624	gsi_to = gsi_start_bb (bb: dest);
625	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); )
626	{
627	stmt = gsi_stmt (i: gsi);
628	if (is_gimple_debug (gs: stmt))
629	break;
630
631	/* Forwarder blocks can only contain labels and debug stmts, and
632	labels must come first, so if we get to this point, we know
633	we're looking at a label. */
634	tree decl = gimple_label_label (gs: as_a <glabel *> (p: stmt));
635	if (EH_LANDING_PAD_NR (decl) != 0
636	|| DECL_NONLOCAL (decl)
637	|| FORCED_LABEL (decl)
638	|| !DECL_ARTIFICIAL (decl))
639	gsi_move_before (&gsi, &gsi_to);
640	else
641	gsi_next (i: &gsi);
642	}
643
644	/* Move debug statements. Reset them if the destination does not
645	have a single predecessor. */
646	move_debug_stmts_from_forwarder (src: bb, dest, dest_single_pred_p,
647	pred, pred_single_succ_p: pred && single_succ_p (bb: pred));
648
649	bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
650
651	/* Update the dominators. */
652	if (dom_info_available_p (CDI_DOMINATORS))
653	{
654	basic_block dom, dombb, domdest;
655
656	dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
657	domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
658	if (domdest == bb)
659	{
660	/* Shortcut to avoid calling (relatively expensive)
661	nearest_common_dominator unless necessary. */
662	dom = dombb;
663	}
664	else
665	dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
666
667	set_immediate_dominator (CDI_DOMINATORS, dest, dom);
668	}
669
670	/* Adjust latch infomation of BB's parent loop as otherwise
671	the cfg hook has a hard time not to kill the loop. */
672	if (current_loops && bb->loop_father->latch == bb)
673	bb->loop_father->latch = pred;
674
675	/* And kill the forwarder block. */
676	delete_basic_block (bb);
677
678	return true;
679	}
680
681	/* STMT is a call that has been discovered noreturn. Split the
682	block to prepare fixing up the CFG and remove LHS.
683	Return true if cleanup-cfg needs to run. */
684
685	bool
686	fixup_noreturn_call (gimple *stmt)
687	{
688	basic_block bb = gimple_bb (g: stmt);
689	bool changed = false;
690
691	if (gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
692	return false;
693
694	/* First split basic block if stmt is not last. */
695	if (stmt != gsi_stmt (i: gsi_last_bb (bb)))
696	{
697	if (stmt == gsi_stmt (i: gsi_last_nondebug_bb (bb)))
698	{
699	/* Don't split if there are only debug stmts
700	after stmt, that can result in -fcompare-debug
701	failures. Remove the debug stmts instead,
702	they should be all unreachable anyway. */
703	gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
704	for (gsi_next (i: &gsi); !gsi_end_p (i: gsi); )
705	gsi_remove (&gsi, true);
706	}
707	else
708	{
709	split_block (bb, stmt);
710	changed = true;
711	}
712	}
713
714	/* If there is an LHS, remove it, but only if its type has fixed size.
715	The LHS will need to be recreated during RTL expansion and creating
716	temporaries of variable-sized types is not supported. Also don't
717	do this with TREE_ADDRESSABLE types, as assign_temp will abort.
718	Drop LHS regardless of TREE_ADDRESSABLE, if the function call
719	has been changed into a call that does not return a value, like
720	__builtin_unreachable or __cxa_pure_virtual. */
721	tree lhs = gimple_call_lhs (gs: stmt);
722	if (lhs
723	&& (should_remove_lhs_p (lhs)
724	|| VOID_TYPE_P (TREE_TYPE (gimple_call_fntype (stmt)))))
725	{
726	gimple_call_set_lhs (gs: stmt, NULL_TREE);
727
728	/* We need to fix up the SSA name to avoid checking errors. */
729	if (TREE_CODE (lhs) == SSA_NAME)
730	{
731	tree new_var = create_tmp_reg (TREE_TYPE (lhs));
732	SET_SSA_NAME_VAR_OR_IDENTIFIER (lhs, new_var);
733	SSA_NAME_DEF_STMT (lhs) = gimple_build_nop ();
734	set_ssa_default_def (cfun, new_var, lhs);
735	}
736
737	update_stmt (s: stmt);
738	}
739
740	/* Mark the call as altering control flow. */
741	if (!gimple_call_ctrl_altering_p (gs: stmt))
742	{
743	gimple_call_set_ctrl_altering (s: stmt, ctrl_altering_p: true);
744	changed = true;
745	}
746
747	return changed;
748	}
749
750	/* Return true if we want to merge BB1 and BB2 into a single block. */
751
752	static bool
753	want_merge_blocks_p (basic_block bb1, basic_block bb2)
754	{
755	if (!can_merge_blocks_p (bb1, bb2))
756	return false;
757	gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb: bb1);
758	if (gsi_end_p (i: gsi) || !stmt_can_terminate_bb_p (gsi_stmt (i: gsi)))
759	return true;
760	return bb1->count.ok_for_merging (other: bb2->count);
761	}
762
763
764	/* Tries to cleanup cfg in basic block BB by merging blocks. Returns
765	true if anything changes. */
766
767	static bool
768	cleanup_tree_cfg_bb (basic_block bb)
769	{
770	if (tree_forwarder_block_p (bb, phi_wanted: false)
771	&& remove_forwarder_block (bb))
772	return true;
773
774	/* If there is a merge opportunity with the predecessor
775	do nothing now but wait until we process the predecessor.
776	This happens when we visit BBs in a non-optimal order and
777	avoids quadratic behavior with adjusting stmts BB pointer. */
778	if (single_pred_p (bb)
779	&& want_merge_blocks_p (bb1: single_pred (bb), bb2: bb))
780	/* But make sure we _do_ visit it. When we remove unreachable paths
781	ending in a backedge we fail to mark the destinations predecessors
782	as changed. */
783	bitmap_set_bit (cfgcleanup_altered_bbs, single_pred (bb)->index);
784
785	/* Merging the blocks may create new opportunities for folding
786	conditional branches (due to the elimination of single-valued PHI
787	nodes). */
788	else if (single_succ_p (bb)
789	&& want_merge_blocks_p (bb1: bb, bb2: single_succ (bb)))
790	{
791	merge_blocks (bb, single_succ (bb));
792	return true;
793	}
794
795	return false;
796	}
797
798	/* Return true if E is an EDGE_ABNORMAL edge for returns_twice calls,
799	i.e. one going from .ABNORMAL_DISPATCHER to basic block which doesn't
800	start with a forced or nonlocal label. Calls which return twice can return
801	the second time only if they are called normally the first time, so basic
802	blocks which can be only entered through these abnormal edges but not
803	normally are effectively unreachable as well. Additionally ignore
804	__builtin_setjmp_receiver starting blocks, which have one FORCED_LABEL
805	and which are always only reachable through EDGE_ABNORMAL edge. They are
806	handled in cleanup_control_flow_pre. */
807
808	static bool
809	maybe_dead_abnormal_edge_p (edge e)
810	{
811	if ((e->flags & (EDGE_ABNORMAL | EDGE_EH)) != EDGE_ABNORMAL)
812	return false;
813
814	gimple_stmt_iterator gsi = gsi_start_nondebug_after_labels_bb (bb: e->src);
815	gimple *g = gsi_stmt (i: gsi);
816	if (!g || !gimple_call_internal_p (gs: g, fn: IFN_ABNORMAL_DISPATCHER))
817	return false;
818
819	tree target = NULL_TREE;
820	for (gsi = gsi_start_bb (bb: e->dest); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
821	if (glabel *label_stmt = dyn_cast <glabel *> (p: gsi_stmt (i: gsi)))
822	{
823	tree this_target = gimple_label_label (gs: label_stmt);
824	if (DECL_NONLOCAL (this_target))
825	return false;
826	if (FORCED_LABEL (this_target))
827	{
828	if (target)
829	return false;
830	target = this_target;
831	}
832	}
833	else
834	break;
835
836	if (target)
837	{
838	/* If there was a single FORCED_LABEL, check for
839	__builtin_setjmp_receiver with address of that label. */
840	if (!gsi_end_p (i: gsi) && is_gimple_debug (gs: gsi_stmt (i: gsi)))
841	gsi_next_nondebug (i: &gsi);
842	if (gsi_end_p (i: gsi))
843	return false;
844	if (!gimple_call_builtin_p (gsi_stmt (i: gsi), BUILT_IN_SETJMP_RECEIVER))
845	return false;
846
847	tree arg = gimple_call_arg (gs: gsi_stmt (i: gsi), index: 0);
848	if (TREE_CODE (arg) != ADDR_EXPR || TREE_OPERAND (arg, 0) != target)
849	return false;
850	}
851	return true;
852	}
853
854	/* If BB is a basic block ending with __builtin_setjmp_setup, return edge
855	from .ABNORMAL_DISPATCHER basic block to corresponding
856	__builtin_setjmp_receiver basic block, otherwise return NULL. */
857	static edge
858	builtin_setjmp_setup_bb (basic_block bb)
859	{
860	if (EDGE_COUNT (bb->succs) != 2
861	|| ((EDGE_SUCC (bb, 0)->flags
862	& (EDGE_ABNORMAL | EDGE_EH)) != EDGE_ABNORMAL
863	&& (EDGE_SUCC (bb, 1)->flags
864	& (EDGE_ABNORMAL | EDGE_EH)) != EDGE_ABNORMAL))
865	return NULL;
866
867	gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
868	if (gsi_end_p (i: gsi)
869	|| !gimple_call_builtin_p (gsi_stmt (i: gsi), BUILT_IN_SETJMP_SETUP))
870	return NULL;
871
872	tree arg = gimple_call_arg (gs: gsi_stmt (i: gsi), index: 1);
873	if (TREE_CODE (arg) != ADDR_EXPR
874	|| TREE_CODE (TREE_OPERAND (arg, 0)) != LABEL_DECL)
875	return NULL;
876
877	basic_block recv_bb = label_to_block (cfun, TREE_OPERAND (arg, 0));
878	if (EDGE_COUNT (recv_bb->preds) != 1
879	|| (EDGE_PRED (recv_bb, 0)->flags
880	& (EDGE_ABNORMAL | EDGE_EH)) != EDGE_ABNORMAL
881	|| (EDGE_SUCC (bb, 0)->dest != EDGE_PRED (recv_bb, 0)->src
882	&& EDGE_SUCC (bb, 1)->dest != EDGE_PRED (recv_bb, 0)->src))
883	return NULL;
884
885	/* EDGE_PRED (recv_bb, 0)->src should be the .ABNORMAL_DISPATCHER bb. */
886	return EDGE_PRED (recv_bb, 0);
887	}
888
889	/* Do cleanup_control_flow_bb in PRE order. */
890
891	static bool
892	cleanup_control_flow_pre ()
893	{
894	bool retval = false;
895
896	/* We want remove_edge_and_dominated_blocks to only remove edges,
897	not dominated blocks which it does when dom info isn't available.
898	Pretend so. */
899	dom_state saved_state = dom_info_state (CDI_DOMINATORS);
900	set_dom_info_availability (CDI_DOMINATORS, DOM_NONE);
901
902	auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 2);
903	auto_sbitmap visited (last_basic_block_for_fn (cfun));
904	bitmap_clear (visited);
905
906	vec<edge, va_gc> *setjmp_vec = NULL;
907	auto_vec<basic_block, 4> abnormal_dispatchers;
908
909	stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
910
911	while (! stack.is_empty ())
912	{
913	/* Look at the edge on the top of the stack. */
914	edge_iterator ei = stack.last ();
915	basic_block dest = ei_edge (i: ei)->dest;
916
917	if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
918	&& !bitmap_bit_p (map: visited, bitno: dest->index)
919	&& (ei_container (i: ei) == setjmp_vec
920	|| !maybe_dead_abnormal_edge_p (e: ei_edge (i: ei))))
921	{
922	bitmap_set_bit (map: visited, bitno: dest->index);
923	/* We only possibly remove edges from DEST here, leaving
924	possibly unreachable code in the IL. */
925	retval |= cleanup_control_flow_bb (bb: dest);
926
927	/* Check for __builtin_setjmp_setup. Edges from .ABNORMAL_DISPATCH
928	to __builtin_setjmp_receiver will be normally ignored by
929	maybe_dead_abnormal_edge_p. If DEST is a visited
930	__builtin_setjmp_setup, queue edge from .ABNORMAL_DISPATCH
931	to __builtin_setjmp_receiver, so that it will be visited too. */
932	if (edge e = builtin_setjmp_setup_bb (bb: dest))
933	{
934	vec_safe_push (v&: setjmp_vec, obj: e);
935	if (vec_safe_length (v: setjmp_vec) == 1)
936	stack.quick_push (ei_start (setjmp_vec));
937	}
938
939	if ((ei_edge (i: ei)->flags
940	& (EDGE_ABNORMAL | EDGE_EH)) == EDGE_ABNORMAL)
941	{
942	gimple_stmt_iterator gsi
943	= gsi_start_nondebug_after_labels_bb (bb: dest);
944	gimple *g = gsi_stmt (i: gsi);
945	if (g && gimple_call_internal_p (gs: g, fn: IFN_ABNORMAL_DISPATCHER))
946	abnormal_dispatchers.safe_push (obj: dest);
947	}
948
949	if (EDGE_COUNT (dest->succs) > 0)
950	stack.quick_push (ei_start (dest->succs));
951	}
952	else
953	{
954	if (!ei_one_before_end_p (i: ei))
955	ei_next (i: &stack.last ());
956	else
957	{
958	if (ei_container (i: ei) == setjmp_vec)
959	vec_safe_truncate (v: setjmp_vec, size: 0);
960	stack.pop ();
961	}
962	}
963	}
964
965	vec_free (v&: setjmp_vec);
966
967	/* If we've marked .ABNORMAL_DISPATCHER basic block(s) as visited
968	above, but haven't marked any of their successors as visited,
969	unmark them now, so that they can be removed as useless. */
970	for (basic_block dispatcher_bb : abnormal_dispatchers)
971	{
972	edge e;
973	edge_iterator ei;
974	FOR_EACH_EDGE (e, ei, dispatcher_bb->succs)
975	if (bitmap_bit_p (map: visited, bitno: e->dest->index))
976	break;
977	if (e == NULL)
978	bitmap_clear_bit (map: visited, bitno: dispatcher_bb->index);
979	}
980
981	set_dom_info_availability (CDI_DOMINATORS, saved_state);
982
983	/* We are deleting BBs in non-reverse dominator order, make sure
984	insert_debug_temps_for_defs is prepared for that. */
985	if (retval)
986	free_dominance_info (CDI_DOMINATORS);
987
988	/* Remove all now (and previously) unreachable blocks. */
989	for (int i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); ++i)
990	{
991	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
992	if (bb && !bitmap_bit_p (map: visited, bitno: bb->index))
993	{
994	if (!retval)
995	free_dominance_info (CDI_DOMINATORS);
996	delete_basic_block (bb);
997	retval = true;
998	}
999	}
1000
1001	return retval;
1002	}
1003
1004	static bool
1005	mfb_keep_latches (edge e)
1006	{
1007	return !((dom_info_available_p (CDI_DOMINATORS)
1008	&& dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
1009	|| (e->flags & EDGE_DFS_BACK));
1010	}
1011
1012	/* Remove unreachable blocks and other miscellaneous clean up work.
1013	Return true if the flowgraph was modified, false otherwise. */
1014
1015	static bool
1016	cleanup_tree_cfg_noloop (unsigned ssa_update_flags)
1017	{
1018	timevar_push (tv: TV_TREE_CLEANUP_CFG);
1019
1020	/* Ensure that we have single entries into loop headers. Otherwise
1021	if one of the entries is becoming a latch due to CFG cleanup
1022	(from formerly being part of an irreducible region) then we mess
1023	up loop fixup and associate the old loop with a different region
1024	which makes niter upper bounds invalid. See for example PR80549.
1025	This needs to be done before we remove trivially dead edges as
1026	we need to capture the dominance state before the pending transform. */
1027	if (current_loops)
1028	{
1029	/* This needs backedges or dominators. */
1030	if (!dom_info_available_p (CDI_DOMINATORS))
1031	mark_dfs_back_edges ();
1032
1033	for (loop_p loop : *get_loops (cfun))
1034	if (loop && loop->header)
1035	{
1036	basic_block bb = loop->header;
1037	edge_iterator ei;
1038	edge e;
1039	bool found_latch = false;
1040	bool any_abnormal = false;
1041	unsigned n = 0;
1042	/* We are only interested in preserving existing loops, but
1043	we need to check whether they are still real and of course
1044	if we need to add a preheader at all. */
1045	FOR_EACH_EDGE (e, ei, bb->preds)
1046	{
1047	if (e->flags & EDGE_ABNORMAL)
1048	{
1049	any_abnormal = true;
1050	break;
1051	}
1052	if ((dom_info_available_p (CDI_DOMINATORS)
1053	&& dominated_by_p (CDI_DOMINATORS, e->src, bb))
1054	|| (e->flags & EDGE_DFS_BACK))
1055	{
1056	found_latch = true;
1057	continue;
1058	}
1059	n++;
1060	}
1061	/* If we have more than one entry to the loop header
1062	create a forwarder. */
1063	if (found_latch && ! any_abnormal && n > 1)
1064	{
1065	edge fallthru = make_forwarder_block (bb, mfb_keep_latches,
1066	NULL);
1067	loop->header = fallthru->dest;
1068	if (! loops_state_satisfies_p (flags: LOOPS_NEED_FIXUP))
1069	{
1070	/* The loop updating from the CFG hook is incomplete
1071	when we have multiple latches, fixup manually. */
1072	remove_bb_from_loops (fallthru->src);
1073	loop_p cloop = loop;
1074	FOR_EACH_EDGE (e, ei, fallthru->src->preds)
1075	cloop = find_common_loop (cloop, e->src->loop_father);
1076	add_bb_to_loop (fallthru->src, cloop);
1077	}
1078	}
1079	}
1080	}
1081
1082	/* Prepare the worklists of altered blocks. */
1083	cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
1084
1085	/* Start by iterating over all basic blocks in PRE order looking for
1086	edge removal opportunities. Do this first because incoming SSA form
1087	may be invalid and we want to avoid performing SSA related tasks such
1088	as propgating out a PHI node during BB merging in that state. This
1089	also gets rid of unreachable blocks. */
1090	bool changed = cleanup_control_flow_pre ();
1091
1092	/* After doing the above SSA form should be valid (or an update SSA
1093	should be required). */
1094	if (ssa_update_flags)
1095	{
1096	timevar_pop (tv: TV_TREE_CLEANUP_CFG);
1097	update_ssa (ssa_update_flags);
1098	timevar_push (tv: TV_TREE_CLEANUP_CFG);
1099	}
1100
1101	/* Compute dominator info which we need for the iterative process below.
1102	Avoid computing the fast query DFS numbers since any block merging
1103	done will invalidate them anyway. */
1104	if (!dom_info_available_p (CDI_DOMINATORS))
1105	calculate_dominance_info (CDI_DOMINATORS, false);
1106	else
1107	checking_verify_dominators (dir: CDI_DOMINATORS);
1108
1109	/* During forwarder block cleanup, we may redirect edges out of
1110	SWITCH_EXPRs, which can get expensive. So we want to enable
1111	recording of edge to CASE_LABEL_EXPR. */
1112	start_recording_case_labels ();
1113
1114	/* Continue by iterating over all basic blocks looking for BB merging
1115	opportunities. We cannot use FOR_EACH_BB_FN for the BB iteration
1116	since the basic blocks may get removed. */
1117	unsigned n = last_basic_block_for_fn (cfun);
1118	for (unsigned i = NUM_FIXED_BLOCKS; i < n; i++)
1119	{
1120	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1121	if (bb)
1122	changed |= cleanup_tree_cfg_bb (bb);
1123	}
1124
1125	/* Now process the altered blocks, as long as any are available. */
1126	while (!bitmap_empty_p (map: cfgcleanup_altered_bbs))
1127	{
1128	unsigned i = bitmap_clear_first_set_bit (cfgcleanup_altered_bbs);
1129	if (i < NUM_FIXED_BLOCKS)
1130	continue;
1131
1132	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1133	if (!bb)
1134	continue;
1135
1136	/* BB merging done by cleanup_tree_cfg_bb can end up propagating
1137	out single-argument PHIs which in turn can expose
1138	cleanup_control_flow_bb opportunities so we have to repeat
1139	that here. */
1140	changed |= cleanup_control_flow_bb (bb);
1141	changed |= cleanup_tree_cfg_bb (bb);
1142	}
1143
1144	end_recording_case_labels ();
1145	BITMAP_FREE (cfgcleanup_altered_bbs);
1146
1147	gcc_assert (dom_info_available_p (CDI_DOMINATORS));
1148
1149	/* Do not renumber blocks if the SCEV cache is active, it is indexed by
1150	basic-block numbers. */
1151	if (! scev_initialized_p ())
1152	compact_blocks ();
1153
1154	checking_verify_flow_info ();
1155
1156	timevar_pop (tv: TV_TREE_CLEANUP_CFG);
1157
1158	if (changed && current_loops)
1159	{
1160	/* Removing edges and/or blocks may make recorded bounds refer
1161	to stale GIMPLE stmts now, so clear them. */
1162	free_numbers_of_iterations_estimates (cfun);
1163	loops_state_set (flags: LOOPS_NEED_FIXUP);
1164	}
1165
1166	return changed;
1167	}
1168
1169	/* Repairs loop structures. */
1170
1171	static void
1172	repair_loop_structures (void)
1173	{
1174	bitmap changed_bbs;
1175	unsigned n_new_or_deleted_loops;
1176
1177	calculate_dominance_info (CDI_DOMINATORS);
1178
1179	timevar_push (tv: TV_REPAIR_LOOPS);
1180	changed_bbs = BITMAP_ALLOC (NULL);
1181	n_new_or_deleted_loops = fix_loop_structure (changed_bbs);
1182
1183	/* This usually does nothing. But sometimes parts of cfg that originally
1184	were inside a loop get out of it due to edge removal (since they
1185	become unreachable by back edges from latch). Also a former
1186	irreducible loop can become reducible - in this case force a full
1187	rewrite into loop-closed SSA form. */
1188	if (loops_state_satisfies_p (flags: LOOP_CLOSED_SSA)
1189	&& (!bitmap_empty_p (map: changed_bbs) || n_new_or_deleted_loops))
1190	rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1191
1192	BITMAP_FREE (changed_bbs);
1193
1194	checking_verify_loop_structure ();
1195	scev_reset ();
1196
1197	timevar_pop (tv: TV_REPAIR_LOOPS);
1198	}
1199
1200	/* Cleanup cfg and repair loop structures. */
1201
1202	bool
1203	cleanup_tree_cfg (unsigned ssa_update_flags)
1204	{
1205	bool changed = cleanup_tree_cfg_noloop (ssa_update_flags);
1206
1207	if (current_loops != NULL
1208	&& loops_state_satisfies_p (flags: LOOPS_NEED_FIXUP))
1209	repair_loop_structures ();
1210
1211	return changed;
1212	}
1213
1214	/* Tries to merge the PHI nodes at BB into those at BB's sole successor.
1215	Returns true if successful. */
1216
1217	static bool
1218	remove_forwarder_block_with_phi (basic_block bb)
1219	{
1220	edge succ = single_succ_edge (bb);
1221	basic_block dest = succ->dest;
1222	gimple *label;
1223	basic_block dombb, domdest, dom;
1224
1225	/* We check for infinite loops already in tree_forwarder_block_p.
1226	However it may happen that the infinite loop is created
1227	afterwards due to removal of forwarders. */
1228	if (dest == bb)
1229	return false;
1230
1231	/* Removal of forwarders may expose new natural loops and thus
1232	a block may turn into a loop header. */
1233	if (current_loops && bb_loop_header_p (bb))
1234	return false;
1235
1236	/* If the destination block consists of a nonlocal label, do not
1237	merge it. */
1238	label = first_stmt (dest);
1239	if (label)
1240	if (glabel *label_stmt = dyn_cast <glabel *> (p: label))
1241	if (DECL_NONLOCAL (gimple_label_label (label_stmt)))
1242	return false;
1243
1244	/* Record BB's single pred in case we need to update the father
1245	loop's latch information later. */
1246	basic_block pred = NULL;
1247	if (single_pred_p (bb))
1248	pred = single_pred (bb);
1249	bool dest_single_pred_p = single_pred_p (bb: dest);
1250
1251	/* Redirect each incoming edge to BB to DEST. */
1252	while (EDGE_COUNT (bb->preds) > 0)
1253	{
1254	edge e = EDGE_PRED (bb, 0), s;
1255	gphi_iterator gsi;
1256
1257	s = find_edge (e->src, dest);
1258	if (s)
1259	{
1260	/* We already have an edge S from E->src to DEST. If S and
1261	E->dest's sole successor edge have the same PHI arguments
1262	at DEST, redirect S to DEST. */
1263	if (phi_alternatives_equal (dest, e1: s, e2: succ))
1264	{
1265	e = redirect_edge_and_branch (e, dest);
1266	redirect_edge_var_map_clear (e);
1267	continue;
1268	}
1269
1270	/* PHI arguments are different. Create a forwarder block by
1271	splitting E so that we can merge PHI arguments on E to
1272	DEST. */
1273	e = single_succ_edge (bb: split_edge (e));
1274	}
1275	else
1276	{
1277	/* If we merge the forwarder into a loop header verify if we
1278	are creating another loop latch edge. If so, reset
1279	number of iteration information of the loop. */
1280	if (dest->loop_father->header == dest
1281	&& dominated_by_p (CDI_DOMINATORS, e->src, dest))
1282	{
1283	dest->loop_father->any_upper_bound = false;
1284	dest->loop_father->any_likely_upper_bound = false;
1285	free_numbers_of_iterations_estimates (dest->loop_father);
1286	}
1287	}
1288
1289	s = redirect_edge_and_branch (e, dest);
1290
1291	/* redirect_edge_and_branch must not create a new edge. */
1292	gcc_assert (s == e);
1293
1294	/* Add to the PHI nodes at DEST each PHI argument removed at the
1295	destination of E. */
1296	for (gsi = gsi_start_phis (dest);
1297	!gsi_end_p (i: gsi);
1298	gsi_next (i: &gsi))
1299	{
1300	gphi *phi = gsi.phi ();
1301	tree def = gimple_phi_arg_def (gs: phi, index: succ->dest_idx);
1302	location_t locus = gimple_phi_arg_location_from_edge (phi, e: succ);
1303
1304	if (TREE_CODE (def) == SSA_NAME)
1305	{
1306	/* If DEF is one of the results of PHI nodes removed during
1307	redirection, replace it with the PHI argument that used
1308	to be on E. */
1309	vec<edge_var_map> *head = redirect_edge_var_map_vector (e);
1310	size_t length = head ? head->length () : 0;
1311	for (size_t i = 0; i < length; i++)
1312	{
1313	edge_var_map *vm = &(*head)[i];
1314	tree old_arg = redirect_edge_var_map_result (v: vm);
1315	tree new_arg = redirect_edge_var_map_def (v: vm);
1316
1317	if (def == old_arg)
1318	{
1319	def = new_arg;
1320	locus = redirect_edge_var_map_location (v: vm);
1321	break;
1322	}
1323	}
1324	}
1325
1326	add_phi_arg (phi, def, s, locus);
1327	}
1328
1329	redirect_edge_var_map_clear (e);
1330	}
1331
1332	/* Move debug statements. Reset them if the destination does not
1333	have a single predecessor. */
1334	move_debug_stmts_from_forwarder (src: bb, dest, dest_single_pred_p,
1335	pred, pred_single_succ_p: pred && single_succ_p (bb: pred));
1336
1337	/* Update the dominators. */
1338	dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
1339	domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
1340	if (domdest == bb)
1341	{
1342	/* Shortcut to avoid calling (relatively expensive)
1343	nearest_common_dominator unless necessary. */
1344	dom = dombb;
1345	}
1346	else
1347	dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
1348
1349	set_immediate_dominator (CDI_DOMINATORS, dest, dom);
1350
1351	/* Adjust latch infomation of BB's parent loop as otherwise
1352	the cfg hook has a hard time not to kill the loop. */
1353	if (current_loops && bb->loop_father->latch == bb)
1354	bb->loop_father->latch = pred;
1355
1356	/* Remove BB since all of BB's incoming edges have been redirected
1357	to DEST. */
1358	delete_basic_block (bb);
1359
1360	return true;
1361	}
1362
1363	/* This pass merges PHI nodes if one feeds into another. For example,
1364	suppose we have the following:
1365
1366	goto <bb 9> (<L9>);
1367
1368	<L8>:;
1369	tem_17 = foo ();
1370
1371	# tem_6 = PHI <tem_17(8), tem_23(7)>;
1372	<L9>:;
1373
1374	# tem_3 = PHI <tem_6(9), tem_2(5)>;
1375	<L10>:;
1376
1377	Then we merge the first PHI node into the second one like so:
1378
1379	goto <bb 9> (<L10>);
1380
1381	<L8>:;
1382	tem_17 = foo ();
1383
1384	# tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
1385	<L10>:;
1386	*/
1387
1388	namespace {
1389
1390	const pass_data pass_data_merge_phi =
1391	{
1392	.type: GIMPLE_PASS, /* type */
1393	.name: "mergephi", /* name */
1394	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
1395	.tv_id: TV_TREE_MERGE_PHI, /* tv_id */
1396	.properties_required: ( PROP_cfg | PROP_ssa ), /* properties_required */
1397	.properties_provided: 0, /* properties_provided */
1398	.properties_destroyed: 0, /* properties_destroyed */
1399	.todo_flags_start: 0, /* todo_flags_start */
1400	.todo_flags_finish: 0, /* todo_flags_finish */
1401	};
1402
1403	class pass_merge_phi : public gimple_opt_pass
1404	{
1405	public:
1406	pass_merge_phi (gcc::context *ctxt)
1407	: gimple_opt_pass (pass_data_merge_phi, ctxt)
1408	{}
1409
1410	/* opt_pass methods: */
1411	opt_pass * clone () final override { return new pass_merge_phi (m_ctxt); }
1412	unsigned int execute (function *) final override;
1413
1414	}; // class pass_merge_phi
1415
1416	unsigned int
1417	pass_merge_phi::execute (function *fun)
1418	{
1419	basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
1420	basic_block *current = worklist;
1421	basic_block bb;
1422
1423	calculate_dominance_info (CDI_DOMINATORS);
1424
1425	/* Find all PHI nodes that we may be able to merge. */
1426	FOR_EACH_BB_FN (bb, fun)
1427	{
1428	basic_block dest;
1429
1430	/* Look for a forwarder block with PHI nodes. */
1431	if (!tree_forwarder_block_p (bb, phi_wanted: true))
1432	continue;
1433
1434	dest = single_succ (bb);
1435
1436	/* We have to feed into another basic block with PHI
1437	nodes. */
1438	if (gimple_seq_empty_p (s: phi_nodes (bb: dest))
1439	/* We don't want to deal with a basic block with
1440	abnormal edges. */
1441	|| bb_has_abnormal_pred (bb))
1442	continue;
1443
1444	if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
1445	{
1446	/* If BB does not dominate DEST, then the PHI nodes at
1447	DEST must be the only users of the results of the PHI
1448	nodes at BB. */
1449	*current++ = bb;
1450	}
1451	else
1452	{
1453	gphi_iterator gsi;
1454	unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
1455
1456	/* BB dominates DEST. There may be many users of the PHI
1457	nodes in BB. However, there is still a trivial case we
1458	can handle. If the result of every PHI in BB is used
1459	only by a PHI in DEST, then we can trivially merge the
1460	PHI nodes from BB into DEST. */
1461	for (gsi = gsi_start_phis (bb); !gsi_end_p (i: gsi);
1462	gsi_next (i: &gsi))
1463	{
1464	gphi *phi = gsi.phi ();
1465	tree result = gimple_phi_result (gs: phi);
1466	use_operand_p imm_use;
1467	gimple *use_stmt;
1468
1469	/* If the PHI's result is never used, then we can just
1470	ignore it. */
1471	if (has_zero_uses (var: result))
1472	continue;
1473
1474	/* Get the single use of the result of this PHI node. */
1475	if (!single_imm_use (var: result, use_p: &imm_use, stmt: &use_stmt)
1476	|| gimple_code (g: use_stmt) != GIMPLE_PHI
1477	|| gimple_bb (g: use_stmt) != dest
1478	|| gimple_phi_arg_def (gs: use_stmt, index: dest_idx) != result)
1479	break;
1480	}
1481
1482	/* If the loop above iterated through all the PHI nodes
1483	in BB, then we can merge the PHIs from BB into DEST. */
1484	if (gsi_end_p (i: gsi))
1485	*current++ = bb;
1486	}
1487	}
1488
1489	/* Now let's drain WORKLIST. */
1490	bool changed = false;
1491	while (current != worklist)
1492	{
1493	bb = *--current;
1494	changed |= remove_forwarder_block_with_phi (bb);
1495	}
1496	free (ptr: worklist);
1497
1498	/* Removing forwarder blocks can cause formerly irreducible loops
1499	to become reducible if we merged two entry blocks. */
1500	if (changed
1501	&& current_loops)
1502	loops_state_set (flags: LOOPS_NEED_FIXUP);
1503
1504	return 0;
1505	}
1506
1507	} // anon namespace
1508
1509	gimple_opt_pass *
1510	make_pass_merge_phi (gcc::context *ctxt)
1511	{
1512	return new pass_merge_phi (ctxt);
1513	}
1514
1515	/* Pass: cleanup the CFG just before expanding trees to RTL.
1516	This is just a round of label cleanups and case node grouping
1517	because after the tree optimizers have run such cleanups may
1518	be necessary. */
1519
1520	static unsigned int
1521	execute_cleanup_cfg_post_optimizing (void)
1522	{
1523	unsigned int todo = execute_fixup_cfg ();
1524	if (cleanup_tree_cfg ())
1525	{
1526	todo &= ~TODO_cleanup_cfg;
1527	todo |= TODO_update_ssa;
1528	}
1529	maybe_remove_unreachable_handlers ();
1530	cleanup_dead_labels ();
1531	if (group_case_labels ())
1532	todo |= TODO_cleanup_cfg;
1533	if ((flag_compare_debug_opt || flag_compare_debug)
1534	&& flag_dump_final_insns)
1535	{
1536	FILE *final_output = fopen (flag_dump_final_insns, modes: "a");
1537
1538	if (!final_output)
1539	{
1540	error ("could not open final insn dump file %qs: %m",
1541	flag_dump_final_insns);
1542	flag_dump_final_insns = NULL;
1543	}
1544	else
1545	{
1546	int save_unnumbered = flag_dump_unnumbered;
1547	int save_noaddr = flag_dump_noaddr;
1548
1549	flag_dump_noaddr = flag_dump_unnumbered = 1;
1550	fprintf (stream: final_output, format: "\n");
1551	dump_enumerated_decls (final_output,
1552	dump_flags | TDF_SLIM | TDF_NOUID);
1553	flag_dump_noaddr = save_noaddr;
1554	flag_dump_unnumbered = save_unnumbered;
1555	if (fclose (stream: final_output))
1556	{
1557	error ("could not close final insn dump file %qs: %m",
1558	flag_dump_final_insns);
1559	flag_dump_final_insns = NULL;
1560	}
1561	}
1562	}
1563	return todo;
1564	}
1565
1566	namespace {
1567
1568	const pass_data pass_data_cleanup_cfg_post_optimizing =
1569	{
1570	.type: GIMPLE_PASS, /* type */
1571	.name: "optimized", /* name */
1572	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
1573	.tv_id: TV_TREE_CLEANUP_CFG, /* tv_id */
1574	PROP_cfg, /* properties_required */
1575	.properties_provided: 0, /* properties_provided */
1576	.properties_destroyed: 0, /* properties_destroyed */
1577	.todo_flags_start: 0, /* todo_flags_start */
1578	TODO_remove_unused_locals, /* todo_flags_finish */
1579	};
1580
1581	class pass_cleanup_cfg_post_optimizing : public gimple_opt_pass
1582	{
1583	public:
1584	pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1585	: gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing, ctxt)
1586	{}
1587
1588	/* opt_pass methods: */
1589	unsigned int execute (function *) final override
1590	{
1591	return execute_cleanup_cfg_post_optimizing ();
1592	}
1593
1594	}; // class pass_cleanup_cfg_post_optimizing
1595
1596	} // anon namespace
1597
1598	gimple_opt_pass *
1599	make_pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1600	{
1601	return new pass_cleanup_cfg_post_optimizing (ctxt);
1602	}
1603
1604
1605	/* Delete all unreachable basic blocks and update callgraph.
1606	Doing so is somewhat nontrivial because we need to update all clones and
1607	remove inline function that become unreachable. */
1608
1609	bool
1610	delete_unreachable_blocks_update_callgraph (cgraph_node *dst_node,
1611	bool update_clones)
1612	{
1613	bool changed = false;
1614	basic_block b, next_bb;
1615
1616	find_unreachable_blocks ();
1617
1618	/* Delete all unreachable basic blocks. */
1619
1620	for (b = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; b
1621	!= EXIT_BLOCK_PTR_FOR_FN (cfun); b = next_bb)
1622	{
1623	next_bb = b->next_bb;
1624
1625	if (!(b->flags & BB_REACHABLE))
1626	{
1627	gimple_stmt_iterator bsi;
1628
1629	for (bsi = gsi_start_bb (bb: b); !gsi_end_p (i: bsi); gsi_next (i: &bsi))
1630	{
1631	struct cgraph_edge *e;
1632	struct cgraph_node *node;
1633
1634	dst_node->remove_stmt_references (stmt: gsi_stmt (i: bsi));
1635
1636	if (gimple_code (g: gsi_stmt (i: bsi)) == GIMPLE_CALL
1637	&&(e = dst_node->get_edge (call_stmt: gsi_stmt (i: bsi))) != NULL)
1638	{
1639	if (!e->inline_failed)
1640	e->callee->remove_symbol_and_inline_clones (forbidden_node: dst_node);
1641	else
1642	cgraph_edge::remove (edge: e);
1643	}
1644	if (update_clones && dst_node->clones)
1645	for (node = dst_node->clones; node != dst_node;)
1646	{
1647	node->remove_stmt_references (stmt: gsi_stmt (i: bsi));
1648	if (gimple_code (g: gsi_stmt (i: bsi)) == GIMPLE_CALL
1649	&& (e = node->get_edge (call_stmt: gsi_stmt (i: bsi))) != NULL)
1650	{
1651	if (!e->inline_failed)
1652	e->callee->remove_symbol_and_inline_clones (forbidden_node: dst_node);
1653	else
1654	cgraph_edge::remove (edge: e);
1655	}
1656
1657	if (node->clones)
1658	node = node->clones;
1659	else if (node->next_sibling_clone)
1660	node = node->next_sibling_clone;
1661	else
1662	{
1663	while (node != dst_node && !node->next_sibling_clone)
1664	node = node->clone_of;
1665	if (node != dst_node)
1666	node = node->next_sibling_clone;
1667	}
1668	}
1669	}
1670	delete_basic_block (b);
1671	changed = true;
1672	}
1673	}
1674
1675	return changed;
1676	}
1677
1678