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