1	/* Rewrite a program in Normal form into SSA.
2	Copyright (C) 2001-2024 Free Software Foundation, Inc.
3	Contributed by Diego Novillo <dnovillo@redhat.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	#include "config.h"
22	#include "system.h"
23	#include "coretypes.h"
24	#include "backend.h"
25	#include "rtl.h"
26	#include "tree.h"
27	#include "gimple.h"
28	#include "tree-pass.h"
29	#include "ssa.h"
30	#include "gimple-pretty-print.h"
31	#include "diagnostic-core.h"
32	#include "langhooks.h"
33	#include "cfganal.h"
34	#include "gimple-iterator.h"
35	#include "tree-cfg.h"
36	#include "tree-into-ssa.h"
37	#include "tree-dfa.h"
38	#include "tree-ssa.h"
39	#include "domwalk.h"
40	#include "statistics.h"
41	#include "stringpool.h"
42	#include "attribs.h"
43	#include "asan.h"
44	#include "attr-fnspec.h"
45
46	#define PERCENT(x,y) ((float)(x) * 100.0 / (float)(y))
47
48	/* This file builds the SSA form for a function as described in:
49	R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
50	Computing Static Single Assignment Form and the Control Dependence
51	Graph. ACM Transactions on Programming Languages and Systems,
52	13(4):451-490, October 1991. */
53
54	/* Structure to map a variable VAR to the set of blocks that contain
55	definitions for VAR. */
56	struct def_blocks
57	{
58	/* Blocks that contain definitions of VAR. Bit I will be set if the
59	Ith block contains a definition of VAR. */
60	bitmap def_blocks;
61
62	/* Blocks that contain a PHI node for VAR. */
63	bitmap phi_blocks;
64
65	/* Blocks where VAR is live-on-entry. Similar semantics as
66	DEF_BLOCKS. */
67	bitmap livein_blocks;
68	};
69
70	/* Stack of trees used to restore the global currdefs to its original
71	state after completing rewriting of a block and its dominator
72	children. Its elements have the following properties:
73
74	- An SSA_NAME (N) indicates that the current definition of the
75	underlying variable should be set to the given SSA_NAME. If the
76	symbol associated with the SSA_NAME is not a GIMPLE register, the
77	next slot in the stack must be a _DECL node (SYM). In this case,
78	the name N in the previous slot is the current reaching
79	definition for SYM.
80
81	- A _DECL node indicates that the underlying variable has no
82	current definition.
83
84	- A NULL node at the top entry is used to mark the last slot
85	associated with the current block. */
86	static vec<tree> block_defs_stack;
87
88
89	/* Set of existing SSA names being replaced by update_ssa. */
90	static sbitmap old_ssa_names;
91
92	/* Set of new SSA names being added by update_ssa. Note that both
93	NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
94	the operations done on them are presence tests. */
95	static sbitmap new_ssa_names;
96
97	static sbitmap interesting_blocks;
98
99	/* Set of SSA names that have been marked to be released after they
100	were registered in the replacement table. They will be finally
101	released after we finish updating the SSA web. */
102	bitmap names_to_release;
103
104	/* vec of vec of PHIs to rewrite in a basic block. Element I corresponds
105	the to basic block with index I. Allocated once per compilation, *not*
106	released between different functions. */
107	static vec< vec<gphi *> > phis_to_rewrite;
108
109	/* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
110	static bitmap blocks_with_phis_to_rewrite;
111
112	/* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
113	to grow as the callers to create_new_def_for will create new names on
114	the fly.
115	FIXME. Currently set to 1/3 to avoid frequent reallocations but still
116	need to find a reasonable growth strategy. */
117	#define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
118
119
120	/* The function the SSA updating data structures have been initialized for.
121	NULL if they need to be initialized by create_new_def_for. */
122	static struct function *update_ssa_initialized_fn = NULL;
123
124	/* Global data to attach to the main dominator walk structure. */
125	struct mark_def_sites_global_data
126	{
127	/* This bitmap contains the variables which are set before they
128	are used in a basic block. */
129	bitmap kills;
130	};
131
132	/* It is advantageous to avoid things like life analysis for variables which
133	do not need PHI nodes. This enum describes whether or not a particular
134	variable may need a PHI node. */
135
136	enum need_phi_state {
137	/* This is the default. If we are still in this state after finding
138	all the definition and use sites, then we will assume the variable
139	needs PHI nodes. This is probably an overly conservative assumption. */
140	NEED_PHI_STATE_UNKNOWN,
141
142	/* This state indicates that we have seen one or more sets of the
143	variable in a single basic block and that the sets dominate all
144	uses seen so far. If after finding all definition and use sites
145	we are still in this state, then the variable does not need any
146	PHI nodes. */
147	NEED_PHI_STATE_NO,
148
149	/* This state indicates that we have either seen multiple definitions of
150	the variable in multiple blocks, or that we encountered a use in a
151	block that was not dominated by the block containing the set(s) of
152	this variable. This variable is assumed to need PHI nodes. */
153	NEED_PHI_STATE_MAYBE
154	};
155
156	/* Information stored for both SSA names and decls. */
157	struct common_info
158	{
159	/* This field indicates whether or not the variable may need PHI nodes.
160	See the enum's definition for more detailed information about the
161	states. */
162	ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
163
164	/* The current reaching definition replacing this var. */
165	tree current_def;
166
167	/* Definitions for this var. */
168	struct def_blocks def_blocks;
169	};
170
171	/* Information stored for decls. */
172	struct var_info
173	{
174	/* The variable. */
175	tree var;
176
177	/* Information stored for both SSA names and decls. */
178	common_info info;
179	};
180
181
182	/* VAR_INFOS hashtable helpers. */
183
184	struct var_info_hasher : free_ptr_hash <var_info>
185	{
186	static inline hashval_t hash (const value_type &);
187	static inline bool equal (const value_type &, const compare_type &);
188	};
189
190	inline hashval_t
191	var_info_hasher::hash (const value_type &p)
192	{
193	return DECL_UID (p->var);
194	}
195
196	inline bool
197	var_info_hasher::equal (const value_type &p1, const compare_type &p2)
198	{
199	return p1->var == p2->var;
200	}
201
202
203	/* Each entry in VAR_INFOS contains an element of type STRUCT
204	VAR_INFO_D. */
205	static hash_table<var_info_hasher> *var_infos;
206
207
208	/* Information stored for SSA names. */
209	struct ssa_name_info
210	{
211	/* Age of this record (so that info_for_ssa_name table can be cleared
212	quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
213	are assumed to be null. */
214	unsigned age;
215
216	/* Replacement mappings, allocated from update_ssa_obstack. */
217	bitmap repl_set;
218
219	/* Information stored for both SSA names and decls. */
220	common_info info;
221	};
222
223	static vec<ssa_name_info *> info_for_ssa_name;
224	static unsigned current_info_for_ssa_name_age;
225
226	static bitmap_obstack update_ssa_obstack;
227
228	/* The set of blocks affected by update_ssa. */
229	static bitmap blocks_to_update;
230
231	/* The main entry point to the SSA renamer (rewrite_blocks) may be
232	called several times to do different, but related, tasks.
233	Initially, we need it to rename the whole program into SSA form.
234	At other times, we may need it to only rename into SSA newly
235	exposed symbols. Finally, we can also call it to incrementally fix
236	an already built SSA web. */
237	enum rewrite_mode {
238	/* Convert the whole function into SSA form. */
239	REWRITE_ALL,
240
241	/* Incrementally update the SSA web by replacing existing SSA
242	names with new ones. See update_ssa for details. */
243	REWRITE_UPDATE,
244	REWRITE_UPDATE_REGION
245	};
246
247	/* The set of symbols we ought to re-write into SSA form in update_ssa. */
248	static bitmap symbols_to_rename_set;
249	static vec<tree> symbols_to_rename;
250
251	/* Mark SYM for renaming. */
252
253	static void
254	mark_for_renaming (tree sym)
255	{
256	if (!symbols_to_rename_set)
257	symbols_to_rename_set = BITMAP_ALLOC (NULL);
258	if (bitmap_set_bit (symbols_to_rename_set, DECL_UID (sym)))
259	symbols_to_rename.safe_push (obj: sym);
260	}
261
262	/* Return true if SYM is marked for renaming. */
263
264	static bool
265	marked_for_renaming (tree sym)
266	{
267	if (!symbols_to_rename_set || sym == NULL_TREE)
268	return false;
269	return bitmap_bit_p (symbols_to_rename_set, DECL_UID (sym));
270	}
271
272
273	/* Return true if STMT needs to be rewritten. When renaming a subset
274	of the variables, not all statements will be processed. This is
275	decided in mark_def_sites. */
276
277	static inline bool
278	rewrite_uses_p (gimple *stmt)
279	{
280	return gimple_visited_p (stmt);
281	}
282
283
284	/* Set the rewrite marker on STMT to the value given by REWRITE_P. */
285
286	static inline void
287	set_rewrite_uses (gimple *stmt, bool rewrite_p)
288	{
289	gimple_set_visited (stmt, visited_p: rewrite_p);
290	}
291
292
293	/* Return true if the DEFs created by statement STMT should be
294	registered when marking new definition sites. This is slightly
295	different than rewrite_uses_p: it's used by update_ssa to
296	distinguish statements that need to have both uses and defs
297	processed from those that only need to have their defs processed.
298	Statements that define new SSA names only need to have their defs
299	registered, but they don't need to have their uses renamed. */
300
301	static inline bool
302	register_defs_p (gimple *stmt)
303	{
304	return gimple_plf (stmt, plf: GF_PLF_1) != 0;
305	}
306
307
308	/* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered. */
309
310	static inline void
311	set_register_defs (gimple *stmt, bool register_defs_p)
312	{
313	gimple_set_plf (stmt, plf: GF_PLF_1, val_p: register_defs_p);
314	}
315
316
317	/* Get the information associated with NAME. */
318
319	static inline ssa_name_info *
320	get_ssa_name_ann (tree name)
321	{
322	unsigned ver = SSA_NAME_VERSION (name);
323	unsigned len = info_for_ssa_name.length ();
324	struct ssa_name_info *info;
325
326	/* Re-allocate the vector at most once per update/into-SSA. */
327	if (ver >= len)
328	info_for_ssa_name.safe_grow_cleared (num_ssa_names, exact: true);
329
330	/* But allocate infos lazily. */
331	info = info_for_ssa_name[ver];
332	if (!info)
333	{
334	info = XCNEW (struct ssa_name_info);
335	info->age = current_info_for_ssa_name_age;
336	info->info.need_phi_state = NEED_PHI_STATE_UNKNOWN;
337	info_for_ssa_name[ver] = info;
338	}
339
340	if (info->age < current_info_for_ssa_name_age)
341	{
342	info->age = current_info_for_ssa_name_age;
343	info->repl_set = NULL;
344	info->info.need_phi_state = NEED_PHI_STATE_UNKNOWN;
345	info->info.current_def = NULL_TREE;
346	info->info.def_blocks.def_blocks = NULL;
347	info->info.def_blocks.phi_blocks = NULL;
348	info->info.def_blocks.livein_blocks = NULL;
349	}
350
351	return info;
352	}
353
354	/* Return and allocate the auxiliar information for DECL. */
355
356	static inline var_info *
357	get_var_info (tree decl)
358	{
359	var_info vi;
360	var_info **slot;
361	vi.var = decl;
362	slot = var_infos->find_slot_with_hash (comparable: &vi, DECL_UID (decl), insert: INSERT);
363	if (*slot == NULL)
364	{
365	var_info *v = XCNEW (var_info);
366	v->var = decl;
367	*slot = v;
368	return v;
369	}
370	return *slot;
371	}
372
373
374	/* Clears info for SSA names. */
375
376	static void
377	clear_ssa_name_info (void)
378	{
379	current_info_for_ssa_name_age++;
380
381	/* If current_info_for_ssa_name_age wraps we use stale information.
382	Asser that this does not happen. */
383	gcc_assert (current_info_for_ssa_name_age != 0);
384	}
385
386
387	/* Get access to the auxiliar information stored per SSA name or decl. */
388
389	static inline common_info *
390	get_common_info (tree var)
391	{
392	if (TREE_CODE (var) == SSA_NAME)
393	return &get_ssa_name_ann (name: var)->info;
394	else
395	return &get_var_info (decl: var)->info;
396	}
397
398
399	/* Return the current definition for VAR. */
400
401	tree
402	get_current_def (tree var)
403	{
404	return get_common_info (var)->current_def;
405	}
406
407
408	/* Sets current definition of VAR to DEF. */
409
410	void
411	set_current_def (tree var, tree def)
412	{
413	get_common_info (var)->current_def = def;
414	}
415
416	/* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
417	all statements in basic block BB. */
418
419	static void
420	initialize_flags_in_bb (basic_block bb)
421	{
422	gimple *stmt;
423	gimple_stmt_iterator gsi;
424
425	for (gsi = gsi_start_phis (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
426	{
427	gimple *phi = gsi_stmt (i: gsi);
428	set_rewrite_uses (stmt: phi, rewrite_p: false);
429	set_register_defs (stmt: phi, register_defs_p: false);
430	}
431
432	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
433	{
434	stmt = gsi_stmt (i: gsi);
435
436	/* We are going to use the operand cache API, such as
437	SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
438	cache for each statement should be up-to-date. */
439	gcc_checking_assert (!gimple_modified_p (stmt));
440	set_rewrite_uses (stmt, rewrite_p: false);
441	set_register_defs (stmt, register_defs_p: false);
442	}
443	}
444
445	/* Mark block BB as interesting for update_ssa. */
446
447	static void
448	mark_block_for_update (basic_block bb)
449	{
450	gcc_checking_assert (blocks_to_update != NULL);
451	if (!bitmap_set_bit (blocks_to_update, bb->index))
452	return;
453	initialize_flags_in_bb (bb);
454	}
455
456	/* Return the set of blocks where variable VAR is defined and the blocks
457	where VAR is live on entry (livein). If no entry is found in
458	DEF_BLOCKS, a new one is created and returned. */
459
460	static inline def_blocks *
461	get_def_blocks_for (common_info *info)
462	{
463	def_blocks *db_p = &info->def_blocks;
464	if (!db_p->def_blocks)
465	{
466	db_p->def_blocks = BITMAP_ALLOC (obstack: &update_ssa_obstack);
467	db_p->phi_blocks = BITMAP_ALLOC (obstack: &update_ssa_obstack);
468	db_p->livein_blocks = BITMAP_ALLOC (obstack: &update_ssa_obstack);
469	}
470
471	return db_p;
472	}
473
474
475	/* Mark block BB as the definition site for variable VAR. PHI_P is true if
476	VAR is defined by a PHI node. */
477
478	static void
479	set_def_block (tree var, basic_block bb, bool phi_p)
480	{
481	def_blocks *db_p;
482	common_info *info;
483
484	info = get_common_info (var);
485	db_p = get_def_blocks_for (info);
486
487	/* Set the bit corresponding to the block where VAR is defined. */
488	bitmap_set_bit (db_p->def_blocks, bb->index);
489	if (phi_p)
490	bitmap_set_bit (db_p->phi_blocks, bb->index);
491
492	/* Keep track of whether or not we may need to insert PHI nodes.
493
494	If we are in the UNKNOWN state, then this is the first definition
495	of VAR. Additionally, we have not seen any uses of VAR yet, so
496	we do not need a PHI node for this variable at this time (i.e.,
497	transition to NEED_PHI_STATE_NO).
498
499	If we are in any other state, then we either have multiple definitions
500	of this variable occurring in different blocks or we saw a use of the
501	variable which was not dominated by the block containing the
502	definition(s). In this case we may need a PHI node, so enter
503	state NEED_PHI_STATE_MAYBE. */
504	if (info->need_phi_state == NEED_PHI_STATE_UNKNOWN)
505	info->need_phi_state = NEED_PHI_STATE_NO;
506	else
507	info->need_phi_state = NEED_PHI_STATE_MAYBE;
508	}
509
510
511	/* Mark block BB as having VAR live at the entry to BB. */
512
513	static void
514	set_livein_block (tree var, basic_block bb)
515	{
516	common_info *info;
517	def_blocks *db_p;
518
519	info = get_common_info (var);
520	db_p = get_def_blocks_for (info);
521
522	/* Set the bit corresponding to the block where VAR is live in. */
523	bitmap_set_bit (db_p->livein_blocks, bb->index);
524
525	/* Keep track of whether or not we may need to insert PHI nodes.
526
527	If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
528	by the single block containing the definition(s) of this variable. If
529	it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
530	NEED_PHI_STATE_MAYBE. */
531	if (info->need_phi_state == NEED_PHI_STATE_NO)
532	{
533	int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
534
535	if (def_block_index == -1
536	|| ! dominated_by_p (CDI_DOMINATORS, bb,
537	BASIC_BLOCK_FOR_FN (cfun, def_block_index)))
538	info->need_phi_state = NEED_PHI_STATE_MAYBE;
539	}
540	else
541	info->need_phi_state = NEED_PHI_STATE_MAYBE;
542	}
543
544
545	/* Return true if NAME is in OLD_SSA_NAMES. */
546
547	static inline bool
548	is_old_name (tree name)
549	{
550	unsigned ver = SSA_NAME_VERSION (name);
551	if (!old_ssa_names)
552	return false;
553	return (ver < SBITMAP_SIZE (old_ssa_names)
554	&& bitmap_bit_p (map: old_ssa_names, bitno: ver));
555	}
556
557
558	/* Return true if NAME is in NEW_SSA_NAMES. */
559
560	static inline bool
561	is_new_name (tree name)
562	{
563	unsigned ver = SSA_NAME_VERSION (name);
564	if (!new_ssa_names)
565	return false;
566	return (ver < SBITMAP_SIZE (new_ssa_names)
567	&& bitmap_bit_p (map: new_ssa_names, bitno: ver));
568	}
569
570
571	/* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET). */
572
573	static inline bitmap
574	names_replaced_by (tree new_tree)
575	{
576	return get_ssa_name_ann (name: new_tree)->repl_set;
577	}
578
579
580	/* Add OLD to REPL_TBL[NEW_TREE].SET. */
581
582	static inline void
583	add_to_repl_tbl (tree new_tree, tree old)
584	{
585	bitmap *set = &get_ssa_name_ann (name: new_tree)->repl_set;
586	if (!*set)
587	*set = BITMAP_ALLOC (obstack: &update_ssa_obstack);
588	bitmap_set_bit (*set, SSA_NAME_VERSION (old));
589	}
590
591	/* Debugging aid to fence old_ssa_names changes when iterating over it. */
592	static bool iterating_old_ssa_names;
593
594	/* Add a new mapping NEW_TREE -> OLD REPL_TBL. Every entry N_i in REPL_TBL
595	represents the set of names O_1 ... O_j replaced by N_i. This is
596	used by update_ssa and its helpers to introduce new SSA names in an
597	already formed SSA web. */
598
599	static void
600	add_new_name_mapping (tree new_tree, tree old)
601	{
602	/* OLD and NEW_TREE must be different SSA names for the same symbol. */
603	gcc_checking_assert (new_tree != old
604	&& SSA_NAME_VAR (new_tree) == SSA_NAME_VAR (old));
605
606	/* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
607	caller may have created new names since the set was created. */
608	if (SBITMAP_SIZE (new_ssa_names) <= SSA_NAME_VERSION (new_tree))
609	{
610	unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
611	new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
612	}
613	if (SBITMAP_SIZE (old_ssa_names) <= SSA_NAME_VERSION (old))
614	{
615	gcc_assert (!iterating_old_ssa_names);
616	unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
617	old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
618	}
619
620	/* Update the REPL_TBL table. */
621	add_to_repl_tbl (new_tree, old);
622
623	/* If OLD had already been registered as a new name, then all the
624	names that OLD replaces should also be replaced by NEW_TREE. */
625	if (is_new_name (name: old))
626	bitmap_ior_into (names_replaced_by (new_tree), names_replaced_by (new_tree: old));
627
628	/* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
629	respectively. */
630	if (iterating_old_ssa_names)
631	gcc_assert (bitmap_bit_p (old_ssa_names, SSA_NAME_VERSION (old)));
632	else
633	bitmap_set_bit (map: old_ssa_names, SSA_NAME_VERSION (old));
634	bitmap_set_bit (map: new_ssa_names, SSA_NAME_VERSION (new_tree));
635	}
636
637
638	/* Call back for walk_dominator_tree used to collect definition sites
639	for every variable in the function. For every statement S in block
640	BB:
641
642	1- Variables defined by S in the DEFS of S are marked in the bitmap
643	KILLS.
644
645	2- If S uses a variable VAR and there is no preceding kill of VAR,
646	then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
647
648	This information is used to determine which variables are live
649	across block boundaries to reduce the number of PHI nodes
650	we create. */
651
652	static void
653	mark_def_sites (basic_block bb, gimple *stmt, bitmap kills)
654	{
655	tree def;
656	use_operand_p use_p;
657	ssa_op_iter iter;
658
659	/* Since this is the first time that we rewrite the program into SSA
660	form, force an operand scan on every statement. */
661	update_stmt (s: stmt);
662
663	gcc_checking_assert (blocks_to_update == NULL);
664	set_register_defs (stmt, register_defs_p: false);
665	set_rewrite_uses (stmt, rewrite_p: false);
666
667	if (is_gimple_debug (gs: stmt))
668	{
669	FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
670	{
671	tree sym = USE_FROM_PTR (use_p);
672	gcc_checking_assert (DECL_P (sym));
673	set_rewrite_uses (stmt, rewrite_p: true);
674	}
675	if (rewrite_uses_p (stmt))
676	bitmap_set_bit (map: interesting_blocks, bitno: bb->index);
677	return;
678	}
679
680	/* If a variable is used before being set, then the variable is live
681	across a block boundary, so mark it live-on-entry to BB. */
682	FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
683	{
684	tree sym = USE_FROM_PTR (use_p);
685	if (TREE_CODE (sym) == SSA_NAME)
686	continue;
687	gcc_checking_assert (DECL_P (sym));
688	if (!bitmap_bit_p (kills, DECL_UID (sym)))
689	set_livein_block (var: sym, bb);
690	set_rewrite_uses (stmt, rewrite_p: true);
691	}
692
693	/* Now process the defs. Mark BB as the definition block and add
694	each def to the set of killed symbols. */
695	FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
696	{
697	if (TREE_CODE (def) == SSA_NAME)
698	continue;
699	gcc_checking_assert (DECL_P (def));
700	set_def_block (var: def, bb, phi_p: false);
701	bitmap_set_bit (kills, DECL_UID (def));
702	set_register_defs (stmt, register_defs_p: true);
703	}
704
705	/* If we found the statement interesting then also mark the block BB
706	as interesting. */
707	if (rewrite_uses_p (stmt) || register_defs_p (stmt))
708	bitmap_set_bit (map: interesting_blocks, bitno: bb->index);
709	}
710
711	/* Structure used by prune_unused_phi_nodes to record bounds of the intervals
712	in the dfs numbering of the dominance tree. */
713
714	struct dom_dfsnum
715	{
716	/* Basic block whose index this entry corresponds to. */
717	unsigned bb_index;
718
719	/* The dfs number of this node. */
720	unsigned dfs_num;
721	};
722
723	/* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
724	for qsort. */
725
726	static int
727	cmp_dfsnum (const void *a, const void *b)
728	{
729	const struct dom_dfsnum *const da = (const struct dom_dfsnum *) a;
730	const struct dom_dfsnum *const db = (const struct dom_dfsnum *) b;
731
732	return (int) da->dfs_num - (int) db->dfs_num;
733	}
734
735	/* Among the intervals starting at the N points specified in DEFS, find
736	the one that contains S, and return its bb_index. */
737
738	static unsigned
739	find_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s)
740	{
741	unsigned f = 0, t = n, m;
742
743	while (t > f + 1)
744	{
745	m = (f + t) / 2;
746	if (defs[m].dfs_num <= s)
747	f = m;
748	else
749	t = m;
750	}
751
752	return defs[f].bb_index;
753	}
754
755	/* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
756	KILLS is a bitmap of blocks where the value is defined before any use. */
757
758	static void
759	prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses)
760	{
761	bitmap_iterator bi;
762	unsigned i, b, p, u, top;
763	bitmap live_phis;
764	basic_block def_bb, use_bb;
765	edge e;
766	edge_iterator ei;
767	bitmap to_remove;
768	struct dom_dfsnum *defs;
769	unsigned n_defs, adef;
770
771	if (bitmap_empty_p (map: uses))
772	{
773	bitmap_clear (phis);
774	return;
775	}
776
777	/* The phi must dominate a use, or an argument of a live phi. Also, we
778	do not create any phi nodes in def blocks, unless they are also livein. */
779	to_remove = BITMAP_ALLOC (NULL);
780	bitmap_and_compl (to_remove, kills, uses);
781	bitmap_and_compl_into (phis, to_remove);
782	if (bitmap_empty_p (map: phis))
783	{
784	BITMAP_FREE (to_remove);
785	return;
786	}
787
788	/* We want to remove the unnecessary phi nodes, but we do not want to compute
789	liveness information, as that may be linear in the size of CFG, and if
790	there are lot of different variables to rewrite, this may lead to quadratic
791	behavior.
792
793	Instead, we basically emulate standard dce. We put all uses to worklist,
794	then for each of them find the nearest def that dominates them. If this
795	def is a phi node, we mark it live, and if it was not live before, we
796	add the predecessors of its basic block to the worklist.
797
798	To quickly locate the nearest def that dominates use, we use dfs numbering
799	of the dominance tree (that is already available in order to speed up
800	queries). For each def, we have the interval given by the dfs number on
801	entry to and on exit from the corresponding subtree in the dominance tree.
802	The nearest dominator for a given use is the smallest of these intervals
803	that contains entry and exit dfs numbers for the basic block with the use.
804	If we store the bounds for all the uses to an array and sort it, we can
805	locate the nearest dominating def in logarithmic time by binary search.*/
806	bitmap_ior (to_remove, kills, phis);
807	n_defs = bitmap_count_bits (to_remove);
808	defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1);
809	defs[0].bb_index = 1;
810	defs[0].dfs_num = 0;
811	adef = 1;
812	EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi)
813	{
814	def_bb = BASIC_BLOCK_FOR_FN (cfun, i);
815	defs[adef].bb_index = i;
816	defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb);
817	defs[adef + 1].bb_index = i;
818	defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb);
819	adef += 2;
820	}
821	BITMAP_FREE (to_remove);
822	gcc_assert (adef == 2 * n_defs + 1);
823	qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum);
824	gcc_assert (defs[0].bb_index == 1);
825
826	/* Now each DEFS entry contains the number of the basic block to that the
827	dfs number corresponds. Change them to the number of basic block that
828	corresponds to the interval following the dfs number. Also, for the
829	dfs_out numbers, increase the dfs number by one (so that it corresponds
830	to the start of the following interval, not to the end of the current
831	one). We use WORKLIST as a stack. */
832	auto_vec<int> worklist (n_defs + 1);
833	worklist.quick_push (obj: 1);
834	top = 1;
835	n_defs = 1;
836	for (i = 1; i < adef; i++)
837	{
838	b = defs[i].bb_index;
839	if (b == top)
840	{
841	/* This is a closing element. Interval corresponding to the top
842	of the stack after removing it follows. */
843	worklist.pop ();
844	top = worklist[worklist.length () - 1];
845	defs[n_defs].bb_index = top;
846	defs[n_defs].dfs_num = defs[i].dfs_num + 1;
847	}
848	else
849	{
850	/* Opening element. Nothing to do, just push it to the stack and move
851	it to the correct position. */
852	defs[n_defs].bb_index = defs[i].bb_index;
853	defs[n_defs].dfs_num = defs[i].dfs_num;
854	worklist.quick_push (obj: b);
855	top = b;
856	}
857
858	/* If this interval starts at the same point as the previous one, cancel
859	the previous one. */
860	if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num)
861	defs[n_defs - 1].bb_index = defs[n_defs].bb_index;
862	else
863	n_defs++;
864	}
865	worklist.pop ();
866	gcc_assert (worklist.is_empty ());
867
868	/* Now process the uses. */
869	live_phis = BITMAP_ALLOC (NULL);
870	EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi)
871	{
872	worklist.safe_push (obj: i);
873	}
874
875	while (!worklist.is_empty ())
876	{
877	b = worklist.pop ();
878	if (b == ENTRY_BLOCK)
879	continue;
880
881	/* If there is a phi node in USE_BB, it is made live. Otherwise,
882	find the def that dominates the immediate dominator of USE_BB
883	(the kill in USE_BB does not dominate the use). */
884	if (bitmap_bit_p (phis, b))
885	p = b;
886	else
887	{
888	use_bb = get_immediate_dominator (CDI_DOMINATORS,
889	BASIC_BLOCK_FOR_FN (cfun, b));
890	p = find_dfsnum_interval (defs, n: n_defs,
891	s: bb_dom_dfs_in (CDI_DOMINATORS, use_bb));
892	if (!bitmap_bit_p (phis, p))
893	continue;
894	}
895
896	/* If the phi node is already live, there is nothing to do. */
897	if (!bitmap_set_bit (live_phis, p))
898	continue;
899
900	/* Add the new uses to the worklist. */
901	def_bb = BASIC_BLOCK_FOR_FN (cfun, p);
902	FOR_EACH_EDGE (e, ei, def_bb->preds)
903	{
904	u = e->src->index;
905	if (bitmap_bit_p (uses, u))
906	continue;
907
908	/* In case there is a kill directly in the use block, do not record
909	the use (this is also necessary for correctness, as we assume that
910	uses dominated by a def directly in their block have been filtered
911	out before). */
912	if (bitmap_bit_p (kills, u))
913	continue;
914
915	bitmap_set_bit (uses, u);
916	worklist.safe_push (obj: u);
917	}
918	}
919
920	bitmap_copy (phis, live_phis);
921	BITMAP_FREE (live_phis);
922	free (ptr: defs);
923	}
924
925	/* Return the set of blocks where variable VAR is defined and the blocks
926	where VAR is live on entry (livein). Return NULL, if no entry is
927	found in DEF_BLOCKS. */
928
929	static inline def_blocks *
930	find_def_blocks_for (tree var)
931	{
932	def_blocks *p = &get_common_info (var)->def_blocks;
933	if (!p->def_blocks)
934	return NULL;
935	return p;
936	}
937
938
939	/* Marks phi node PHI in basic block BB for rewrite. */
940
941	static void
942	mark_phi_for_rewrite (basic_block bb, gphi *phi)
943	{
944	vec<gphi *> phis;
945	unsigned n, idx = bb->index;
946
947	if (rewrite_uses_p (stmt: phi))
948	return;
949
950	set_rewrite_uses (stmt: phi, rewrite_p: true);
951
952	if (!blocks_with_phis_to_rewrite)
953	return;
954
955	if (bitmap_set_bit (blocks_with_phis_to_rewrite, idx))
956	{
957	n = (unsigned) last_basic_block_for_fn (cfun) + 1;
958	if (phis_to_rewrite.length () < n)
959	phis_to_rewrite.safe_grow_cleared (len: n, exact: true);
960
961	phis = phis_to_rewrite[idx];
962	gcc_assert (!phis.exists ());
963	phis.create (nelems: 10);
964	}
965	else
966	phis = phis_to_rewrite[idx];
967
968	phis.safe_push (obj: phi);
969	phis_to_rewrite[idx] = phis;
970	}
971
972	/* Insert PHI nodes for variable VAR using the iterated dominance
973	frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
974	function assumes that the caller is incrementally updating the
975	existing SSA form, in which case VAR may be an SSA name instead of
976	a symbol.
977
978	PHI_INSERTION_POINTS is updated to reflect nodes that already had a
979	PHI node for VAR. On exit, only the nodes that received a PHI node
980	for VAR will be present in PHI_INSERTION_POINTS. */
981
982	static void
983	insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
984	{
985	unsigned bb_index;
986	edge e;
987	gphi *phi;
988	basic_block bb;
989	bitmap_iterator bi;
990	def_blocks *def_map = find_def_blocks_for (var);
991
992	/* Remove the blocks where we already have PHI nodes for VAR. */
993	bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
994
995	/* Remove obviously useless phi nodes. */
996	prune_unused_phi_nodes (phis: phi_insertion_points, kills: def_map->def_blocks,
997	uses: def_map->livein_blocks);
998
999	/* And insert the PHI nodes. */
1000	EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
1001	{
1002	bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1003	if (update_p)
1004	mark_block_for_update (bb);
1005
1006	if (dump_file && (dump_flags & TDF_DETAILS))
1007	{
1008	fprintf (stream: dump_file, format: "creating PHI node in block #%d for ", bb_index);
1009	print_generic_expr (dump_file, var, TDF_SLIM);
1010	fprintf (stream: dump_file, format: "\n");
1011	}
1012	phi = NULL;
1013
1014	if (TREE_CODE (var) == SSA_NAME)
1015	{
1016	/* If we are rewriting SSA names, create the LHS of the PHI
1017	node by duplicating VAR. This is useful in the case of
1018	pointers, to also duplicate pointer attributes (alias
1019	information, in particular). */
1020	edge_iterator ei;
1021	tree new_lhs;
1022
1023	gcc_checking_assert (update_p);
1024	new_lhs = duplicate_ssa_name (var, NULL);
1025	phi = create_phi_node (new_lhs, bb);
1026	add_new_name_mapping (new_tree: new_lhs, old: var);
1027
1028	/* Add VAR to every argument slot of PHI. We need VAR in
1029	every argument so that rewrite_update_phi_arguments knows
1030	which name is this PHI node replacing. If VAR is a
1031	symbol marked for renaming, this is not necessary, the
1032	renamer will use the symbol on the LHS to get its
1033	reaching definition. */
1034	FOR_EACH_EDGE (e, ei, bb->preds)
1035	add_phi_arg (phi, var, e, UNKNOWN_LOCATION);
1036	}
1037	else
1038	{
1039	tree tracked_var;
1040
1041	gcc_checking_assert (DECL_P (var));
1042	phi = create_phi_node (var, bb);
1043
1044	tracked_var = target_for_debug_bind (var);
1045	if (tracked_var)
1046	{
1047	gimple *note = gimple_build_debug_bind (tracked_var,
1048	PHI_RESULT (phi),
1049	phi);
1050	gimple_stmt_iterator si = gsi_after_labels (bb);
1051	gsi_insert_before (&si, note, GSI_SAME_STMT);
1052	}
1053	}
1054
1055	/* Mark this PHI node as interesting for update_ssa. */
1056	set_register_defs (stmt: phi, register_defs_p: true);
1057	mark_phi_for_rewrite (bb, phi);
1058	}
1059	}
1060
1061	/* Sort var_infos after DECL_UID of their var. */
1062
1063	static int
1064	insert_phi_nodes_compare_var_infos (const void *a, const void *b)
1065	{
1066	const var_info *defa = *(var_info * const *)a;
1067	const var_info *defb = *(var_info * const *)b;
1068	if (DECL_UID (defa->var) < DECL_UID (defb->var))
1069	return -1;
1070	else
1071	return 1;
1072	}
1073
1074	/* Insert PHI nodes at the dominance frontier of blocks with variable
1075	definitions. DFS contains the dominance frontier information for
1076	the flowgraph. */
1077
1078	static void
1079	insert_phi_nodes (bitmap_head *dfs)
1080	{
1081	hash_table<var_info_hasher>::iterator hi;
1082	unsigned i;
1083	var_info *info;
1084
1085	/* When the gimplifier introduces SSA names it cannot easily avoid
1086	situations where abnormal edges added by CFG construction break
1087	the use-def dominance requirement. For this case rewrite SSA
1088	names with broken use-def dominance out-of-SSA and register them
1089	for PHI insertion. We only need to do this if abnormal edges
1090	can appear in the function. */
1091	tree name;
1092	if (cfun->calls_setjmp
1093	|| cfun->has_nonlocal_label)
1094	FOR_EACH_SSA_NAME (i, name, cfun)
1095	{
1096	gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1097	if (SSA_NAME_IS_DEFAULT_DEF (name))
1098	continue;
1099
1100	basic_block def_bb = gimple_bb (g: def_stmt);
1101	imm_use_iterator it;
1102	gimple *use_stmt;
1103	bool need_phis = false;
1104	FOR_EACH_IMM_USE_STMT (use_stmt, it, name)
1105	{
1106	basic_block use_bb = gimple_bb (g: use_stmt);
1107	if (use_bb != def_bb
1108	&& ! dominated_by_p (CDI_DOMINATORS, use_bb, def_bb))
1109	need_phis = true;
1110	}
1111	if (need_phis)
1112	{
1113	tree var = create_tmp_reg (TREE_TYPE (name));
1114	use_operand_p use_p;
1115	FOR_EACH_IMM_USE_STMT (use_stmt, it, name)
1116	{
1117	basic_block use_bb = gimple_bb (g: use_stmt);
1118	FOR_EACH_IMM_USE_ON_STMT (use_p, it)
1119	SET_USE (use_p, var);
1120	update_stmt (s: use_stmt);
1121	set_livein_block (var, bb: use_bb);
1122	set_rewrite_uses (stmt: use_stmt, rewrite_p: true);
1123	bitmap_set_bit (map: interesting_blocks, bitno: use_bb->index);
1124	}
1125	def_operand_p def_p;
1126	ssa_op_iter dit;
1127	FOR_EACH_SSA_DEF_OPERAND (def_p, def_stmt, dit, SSA_OP_DEF)
1128	if (DEF_FROM_PTR (def_p) == name)
1129	SET_DEF (def_p, var);
1130	update_stmt (s: def_stmt);
1131	set_def_block (var, bb: def_bb, phi_p: false);
1132	set_register_defs (stmt: def_stmt, register_defs_p: true);
1133	bitmap_set_bit (map: interesting_blocks, bitno: def_bb->index);
1134	release_ssa_name (name);
1135	}
1136	}
1137
1138	auto_vec<var_info *> vars (var_infos->elements ());
1139	FOR_EACH_HASH_TABLE_ELEMENT (*var_infos, info, var_info_p, hi)
1140	if (info->info.need_phi_state != NEED_PHI_STATE_NO)
1141	vars.quick_push (obj: info);
1142
1143	/* Do two stages to avoid code generation differences for UID
1144	differences but no UID ordering differences. */
1145	vars.qsort (insert_phi_nodes_compare_var_infos);
1146
1147	FOR_EACH_VEC_ELT (vars, i, info)
1148	{
1149	bitmap idf = compute_idf (info->info.def_blocks.def_blocks, dfs);
1150	insert_phi_nodes_for (var: info->var, phi_insertion_points: idf, update_p: false);
1151	BITMAP_FREE (idf);
1152	}
1153	}
1154
1155
1156	/* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
1157	register DEF (an SSA_NAME) to be a new definition for SYM. */
1158
1159	static void
1160	register_new_def (tree def, tree sym)
1161	{
1162	common_info *info = get_common_info (var: sym);
1163	tree currdef;
1164
1165	/* If this variable is set in a single basic block and all uses are
1166	dominated by the set(s) in that single basic block, then there is
1167	no reason to record anything for this variable in the block local
1168	definition stacks. Doing so just wastes time and memory.
1169
1170	This is the same test to prune the set of variables which may
1171	need PHI nodes. So we just use that information since it's already
1172	computed and available for us to use. */
1173	if (info->need_phi_state == NEED_PHI_STATE_NO)
1174	{
1175	info->current_def = def;
1176	return;
1177	}
1178
1179	currdef = info->current_def;
1180
1181	/* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
1182	SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM
1183	in the stack so that we know which symbol is being defined by
1184	this SSA name when we unwind the stack. */
1185	if (currdef && !is_gimple_reg (sym))
1186	block_defs_stack.safe_push (obj: sym);
1187
1188	/* Push the current reaching definition into BLOCK_DEFS_STACK. This
1189	stack is later used by the dominator tree callbacks to restore
1190	the reaching definitions for all the variables defined in the
1191	block after a recursive visit to all its immediately dominated
1192	blocks. If there is no current reaching definition, then just
1193	record the underlying _DECL node. */
1194	block_defs_stack.safe_push (obj: currdef ? currdef : sym);
1195
1196	/* Set the current reaching definition for SYM to be DEF. */
1197	info->current_def = def;
1198	}
1199
1200
1201	/* Perform a depth-first traversal of the dominator tree looking for
1202	variables to rename. BB is the block where to start searching.
1203	Renaming is a five step process:
1204
1205	1- Every definition made by PHI nodes at the start of the blocks is
1206	registered as the current definition for the corresponding variable.
1207
1208	2- Every statement in BB is rewritten. USE and VUSE operands are
1209	rewritten with their corresponding reaching definition. DEF and
1210	VDEF targets are registered as new definitions.
1211
1212	3- All the PHI nodes in successor blocks of BB are visited. The
1213	argument corresponding to BB is replaced with its current reaching
1214	definition.
1215
1216	4- Recursively rewrite every dominator child block of BB.
1217
1218	5- Restore (in reverse order) the current reaching definition for every
1219	new definition introduced in this block. This is done so that when
1220	we return from the recursive call, all the current reaching
1221	definitions are restored to the names that were valid in the
1222	dominator parent of BB. */
1223
1224	/* Return the current definition for variable VAR. If none is found,
1225	create a new SSA name to act as the zeroth definition for VAR. */
1226
1227	static tree
1228	get_reaching_def (tree var)
1229	{
1230	common_info *info = get_common_info (var);
1231	tree currdef;
1232
1233	/* Lookup the current reaching definition for VAR. */
1234	currdef = info->current_def;
1235
1236	/* If there is no reaching definition for VAR, create and register a
1237	default definition for it (if needed). */
1238	if (currdef == NULL_TREE)
1239	{
1240	tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
1241	if (! sym)
1242	sym = create_tmp_reg (TREE_TYPE (var));
1243	currdef = get_or_create_ssa_default_def (cfun, sym);
1244	}
1245
1246	/* Return the current reaching definition for VAR, or the default
1247	definition, if we had to create one. */
1248	return currdef;
1249	}
1250
1251
1252	/* Helper function for rewrite_stmt. Rewrite uses in a debug stmt. */
1253
1254	static void
1255	rewrite_debug_stmt_uses (gimple *stmt)
1256	{
1257	use_operand_p use_p;
1258	ssa_op_iter iter;
1259	bool update = false;
1260
1261	FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1262	{
1263	tree var = USE_FROM_PTR (use_p), def;
1264	common_info *info = get_common_info (var);
1265	gcc_checking_assert (DECL_P (var));
1266	def = info->current_def;
1267	if (!def)
1268	{
1269	if (TREE_CODE (var) == PARM_DECL
1270	&& single_succ_p (ENTRY_BLOCK_PTR_FOR_FN (cfun)))
1271	{
1272	gimple_stmt_iterator gsi
1273	=
1274	gsi_after_labels (bb: single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1275	int lim;
1276	/* Search a few source bind stmts at the start of first bb to
1277	see if a DEBUG_EXPR_DECL can't be reused. */
1278	for (lim = 32;
1279	!gsi_end_p (i: gsi) && lim > 0;
1280	gsi_next (i: &gsi), lim--)
1281	{
1282	gimple *gstmt = gsi_stmt (i: gsi);
1283	if (!gimple_debug_source_bind_p (s: gstmt))
1284	break;
1285	if (gimple_debug_source_bind_get_value (dbg: gstmt) == var)
1286	{
1287	def = gimple_debug_source_bind_get_var (dbg: gstmt);
1288	if (TREE_CODE (def) == DEBUG_EXPR_DECL)
1289	break;
1290	else
1291	def = NULL_TREE;
1292	}
1293	}
1294	/* If not, add a new source bind stmt. */
1295	if (def == NULL_TREE)
1296	{
1297	gimple *def_temp;
1298	def = build_debug_expr_decl (TREE_TYPE (var));
1299	/* FIXME: Is setting the mode really necessary? */
1300	SET_DECL_MODE (def, DECL_MODE (var));
1301	def_temp = gimple_build_debug_source_bind (def, var, NULL);
1302	gsi =
1303	gsi_after_labels (bb: single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1304	gsi_insert_before (&gsi, def_temp, GSI_SAME_STMT);
1305	}
1306	update = true;
1307	}
1308	}
1309	else
1310	{
1311	/* Check if info->current_def can be trusted. */
1312	basic_block bb = gimple_bb (g: stmt);
1313	basic_block def_bb
1314	= SSA_NAME_IS_DEFAULT_DEF (def)
1315	? NULL : gimple_bb (SSA_NAME_DEF_STMT (def));
1316
1317	/* If definition is in current bb, it is fine. */
1318	if (bb == def_bb)
1319	;
1320	/* If definition bb doesn't dominate the current bb,
1321	it can't be used. */
1322	else if (def_bb && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
1323	def = NULL;
1324	/* If there is just one definition and dominates the current
1325	bb, it is fine. */
1326	else if (info->need_phi_state == NEED_PHI_STATE_NO)
1327	;
1328	else
1329	{
1330	def_blocks *db_p = get_def_blocks_for (info);
1331
1332	/* If there are some non-debug uses in the current bb,
1333	it is fine. */
1334	if (bitmap_bit_p (db_p->livein_blocks, bb->index))
1335	;
1336	/* Otherwise give up for now. */
1337	else
1338	def = NULL;
1339	}
1340	}
1341	if (def == NULL)
1342	{
1343	gimple_debug_bind_reset_value (dbg: stmt);
1344	update_stmt (s: stmt);
1345	return;
1346	}
1347	SET_USE (use_p, def);
1348	}
1349	if (update)
1350	update_stmt (s: stmt);
1351	}
1352
1353	/* SSA Rewriting Step 2. Rewrite every variable used in each statement in
1354	the block with its immediate reaching definitions. Update the current
1355	definition of a variable when a new real or virtual definition is found. */
1356
1357	static void
1358	rewrite_stmt (gimple_stmt_iterator *si)
1359	{
1360	use_operand_p use_p;
1361	def_operand_p def_p;
1362	ssa_op_iter iter;
1363	gimple *stmt = gsi_stmt (i: *si);
1364
1365	/* If mark_def_sites decided that we don't need to rewrite this
1366	statement, ignore it. */
1367	gcc_assert (blocks_to_update == NULL);
1368	if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
1369	return;
1370
1371	if (dump_file && (dump_flags & TDF_DETAILS))
1372	{
1373	fprintf (stream: dump_file, format: "Renaming statement ");
1374	print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1375	fprintf (stream: dump_file, format: "\n");
1376	}
1377
1378	/* Step 1. Rewrite USES in the statement. */
1379	if (rewrite_uses_p (stmt))
1380	{
1381	if (is_gimple_debug (gs: stmt))
1382	rewrite_debug_stmt_uses (stmt);
1383	else
1384	FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1385	{
1386	tree var = USE_FROM_PTR (use_p);
1387	if (TREE_CODE (var) == SSA_NAME)
1388	continue;
1389	gcc_checking_assert (DECL_P (var));
1390	SET_USE (use_p, get_reaching_def (var));
1391	}
1392	}
1393
1394	/* Step 2. Register the statement's DEF operands. */
1395	if (register_defs_p (stmt))
1396	FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1397	{
1398	tree var = DEF_FROM_PTR (def_p);
1399	tree name;
1400	tree tracked_var;
1401
1402	if (TREE_CODE (var) == SSA_NAME)
1403	continue;
1404	gcc_checking_assert (DECL_P (var));
1405
1406	if (gimple_clobber_p (s: stmt)
1407	&& is_gimple_reg (var))
1408	{
1409	/* If we rewrite a DECL into SSA form then drop its
1410	clobber stmts and replace uses with a new default def. */
1411	gcc_checking_assert (VAR_P (var) && !gimple_vdef (stmt));
1412	gsi_replace (si, gimple_build_nop (), true);
1413	register_new_def (def: get_or_create_ssa_default_def (cfun, var), sym: var);
1414	break;
1415	}
1416
1417	name = make_ssa_name (var, stmt);
1418	SET_DEF (def_p, name);
1419	register_new_def (DEF_FROM_PTR (def_p), sym: var);
1420
1421	/* Do not insert debug stmts if the stmt ends the BB. */
1422	if (stmt_ends_bb_p (stmt))
1423	continue;
1424
1425	tracked_var = target_for_debug_bind (var);
1426	if (tracked_var)
1427	{
1428	gimple *note = gimple_build_debug_bind (tracked_var, name, stmt);
1429	gsi_insert_after (si, note, GSI_SAME_STMT);
1430	}
1431	}
1432	}
1433
1434
1435	/* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
1436	PHI nodes. For every PHI node found, add a new argument containing the
1437	current reaching definition for the variable and the edge through which
1438	that definition is reaching the PHI node. */
1439
1440	static void
1441	rewrite_add_phi_arguments (basic_block bb)
1442	{
1443	edge e;
1444	edge_iterator ei;
1445
1446	FOR_EACH_EDGE (e, ei, bb->succs)
1447	{
1448	gphi *phi;
1449	gphi_iterator gsi;
1450
1451	for (gsi = gsi_start_phis (e->dest); !gsi_end_p (i: gsi);
1452	gsi_next (i: &gsi))
1453	{
1454	tree currdef, res;
1455	location_t loc;
1456
1457	phi = gsi.phi ();
1458	res = gimple_phi_result (gs: phi);
1459	currdef = get_reaching_def (SSA_NAME_VAR (res));
1460	/* Virtual operand PHI args do not need a location. */
1461	if (virtual_operand_p (op: res))
1462	loc = UNKNOWN_LOCATION;
1463	else
1464	loc = gimple_location (SSA_NAME_DEF_STMT (currdef));
1465	add_phi_arg (phi, currdef, e, loc);
1466	}
1467	}
1468	}
1469
1470	class rewrite_dom_walker : public dom_walker
1471	{
1472	public:
1473	rewrite_dom_walker (cdi_direction direction)
1474	: dom_walker (direction, ALL_BLOCKS, NULL) {}
1475
1476	edge before_dom_children (basic_block) final override;
1477	void after_dom_children (basic_block) final override;
1478	};
1479
1480	/* SSA Rewriting Step 1. Initialization, create a block local stack
1481	of reaching definitions for new SSA names produced in this block
1482	(BLOCK_DEFS). Register new definitions for every PHI node in the
1483	block. */
1484
1485	edge
1486	rewrite_dom_walker::before_dom_children (basic_block bb)
1487	{
1488	if (dump_file && (dump_flags & TDF_DETAILS))
1489	fprintf (stream: dump_file, format: "\n\nRenaming block #%d\n\n", bb->index);
1490
1491	/* Mark the unwind point for this block. */
1492	block_defs_stack.safe_push (NULL_TREE);
1493
1494	/* Step 1. Register new definitions for every PHI node in the block.
1495	Conceptually, all the PHI nodes are executed in parallel and each PHI
1496	node introduces a new version for the associated variable. */
1497	for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (i: gsi);
1498	gsi_next (i: &gsi))
1499	{
1500	tree result = gimple_phi_result (gs: gsi_stmt (i: gsi));
1501	register_new_def (def: result, SSA_NAME_VAR (result));
1502	}
1503
1504	/* Step 2. Rewrite every variable used in each statement in the block
1505	with its immediate reaching definitions. Update the current definition
1506	of a variable when a new real or virtual definition is found. */
1507	if (bitmap_bit_p (map: interesting_blocks, bitno: bb->index))
1508	for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi);
1509	gsi_next (i: &gsi))
1510	rewrite_stmt (si: &gsi);
1511
1512	/* Step 3. Visit all the successor blocks of BB looking for PHI nodes.
1513	For every PHI node found, add a new argument containing the current
1514	reaching definition for the variable and the edge through which that
1515	definition is reaching the PHI node. */
1516	rewrite_add_phi_arguments (bb);
1517
1518	return NULL;
1519	}
1520
1521
1522
1523	/* Called after visiting all the statements in basic block BB and all
1524	of its dominator children. Restore CURRDEFS to its original value. */
1525
1526	void
1527	rewrite_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
1528	{
1529	/* Restore CURRDEFS to its original state. */
1530	while (block_defs_stack.length () > 0)
1531	{
1532	tree tmp = block_defs_stack.pop ();
1533	tree saved_def, var;
1534
1535	if (tmp == NULL_TREE)
1536	break;
1537
1538	if (TREE_CODE (tmp) == SSA_NAME)
1539	{
1540	/* If we recorded an SSA_NAME, then make the SSA_NAME the
1541	current definition of its underlying variable. Note that
1542	if the SSA_NAME is not for a GIMPLE register, the symbol
1543	being defined is stored in the next slot in the stack.
1544	This mechanism is needed because an SSA name for a
1545	non-register symbol may be the definition for more than
1546	one symbol (e.g., SFTs, aliased variables, etc). */
1547	saved_def = tmp;
1548	var = SSA_NAME_VAR (saved_def);
1549	if (!is_gimple_reg (var))
1550	var = block_defs_stack.pop ();
1551	}
1552	else
1553	{
1554	/* If we recorded anything else, it must have been a _DECL
1555	node and its current reaching definition must have been
1556	NULL. */
1557	saved_def = NULL;
1558	var = tmp;
1559	}
1560
1561	get_common_info (var)->current_def = saved_def;
1562	}
1563	}
1564
1565
1566	/* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
1567
1568	DEBUG_FUNCTION void
1569	debug_decl_set (bitmap set)
1570	{
1571	dump_decl_set (stderr, set);
1572	fprintf (stderr, format: "\n");
1573	}
1574
1575
1576	/* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
1577	stack up to a maximum of N levels. If N is -1, the whole stack is
1578	dumped. New levels are created when the dominator tree traversal
1579	used for renaming enters a new sub-tree. */
1580
1581	void
1582	dump_defs_stack (FILE *file, int n)
1583	{
1584	int i, j;
1585
1586	fprintf (stream: file, format: "\n\nRenaming stack");
1587	if (n > 0)
1588	fprintf (stream: file, format: " (up to %d levels)", n);
1589	fprintf (stream: file, format: "\n\n");
1590
1591	i = 1;
1592	fprintf (stream: file, format: "Level %d (current level)\n", i);
1593	for (j = (int) block_defs_stack.length () - 1; j >= 0; j--)
1594	{
1595	tree name, var;
1596
1597	name = block_defs_stack[j];
1598	if (name == NULL_TREE)
1599	{
1600	i++;
1601	if (n > 0 && i > n)
1602	break;
1603	fprintf (stream: file, format: "\nLevel %d\n", i);
1604	continue;
1605	}
1606
1607	if (DECL_P (name))
1608	{
1609	var = name;
1610	name = NULL_TREE;
1611	}
1612	else
1613	{
1614	var = SSA_NAME_VAR (name);
1615	if (!is_gimple_reg (var))
1616	{
1617	j--;
1618	var = block_defs_stack[j];
1619	}
1620	}
1621
1622	fprintf (stream: file, format: " Previous CURRDEF (");
1623	print_generic_expr (file, var);
1624	fprintf (stream: file, format: ") = ");
1625	if (name)
1626	print_generic_expr (file, name);
1627	else
1628	fprintf (stream: file, format: "<NIL>");
1629	fprintf (stream: file, format: "\n");
1630	}
1631	}
1632
1633
1634	/* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
1635	stack up to a maximum of N levels. If N is -1, the whole stack is
1636	dumped. New levels are created when the dominator tree traversal
1637	used for renaming enters a new sub-tree. */
1638
1639	DEBUG_FUNCTION void
1640	debug_defs_stack (int n)
1641	{
1642	dump_defs_stack (stderr, n);
1643	}
1644
1645
1646	/* Dump the current reaching definition of every symbol to FILE. */
1647
1648	void
1649	dump_currdefs (FILE *file)
1650	{
1651	if (symbols_to_rename.is_empty ())
1652	return;
1653
1654	fprintf (stream: file, format: "\n\nCurrent reaching definitions\n\n");
1655	for (tree var : symbols_to_rename)
1656	{
1657	common_info *info = get_common_info (var);
1658	fprintf (stream: file, format: "CURRDEF (");
1659	print_generic_expr (file, var);
1660	fprintf (stream: file, format: ") = ");
1661	if (info->current_def)
1662	print_generic_expr (file, info->current_def);
1663	else
1664	fprintf (stream: file, format: "<NIL>");
1665	fprintf (stream: file, format: "\n");
1666	}
1667	}
1668
1669
1670	/* Dump the current reaching definition of every symbol to stderr. */
1671
1672	DEBUG_FUNCTION void
1673	debug_currdefs (void)
1674	{
1675	dump_currdefs (stderr);
1676	}
1677
1678
1679	/* Dump SSA information to FILE. */
1680
1681	void
1682	dump_tree_ssa (FILE *file)
1683	{
1684	const char *funcname
1685	= lang_hooks.decl_printable_name (current_function_decl, 2);
1686
1687	fprintf (stream: file, format: "SSA renaming information for %s\n\n", funcname);
1688
1689	dump_var_infos (file);
1690	dump_defs_stack (file, n: -1);
1691	dump_currdefs (file);
1692	dump_tree_ssa_stats (file);
1693	}
1694
1695
1696	/* Dump SSA information to stderr. */
1697
1698	DEBUG_FUNCTION void
1699	debug_tree_ssa (void)
1700	{
1701	dump_tree_ssa (stderr);
1702	}
1703
1704
1705	/* Dump statistics for the hash table HTAB. */
1706
1707	static void
1708	htab_statistics (FILE *file, const hash_table<var_info_hasher> &htab)
1709	{
1710	fprintf (stream: file, format: "size " HOST_SIZE_T_PRINT_DEC ", " HOST_SIZE_T_PRINT_DEC
1711	" elements, %f collision/search ratio\n",
1712	(fmt_size_t) htab.size (),
1713	(fmt_size_t) htab.elements (),
1714	htab.collisions ());
1715	}
1716
1717
1718	/* Dump SSA statistics on FILE. */
1719
1720	void
1721	dump_tree_ssa_stats (FILE *file)
1722	{
1723	if (var_infos)
1724	{
1725	fprintf (stream: file, format: "\nHash table statistics:\n");
1726	fprintf (stream: file, format: " var_infos: ");
1727	htab_statistics (file, htab: *var_infos);
1728	fprintf (stream: file, format: "\n");
1729	}
1730	}
1731
1732
1733	/* Dump SSA statistics on stderr. */
1734
1735	DEBUG_FUNCTION void
1736	debug_tree_ssa_stats (void)
1737	{
1738	dump_tree_ssa_stats (stderr);
1739	}
1740
1741
1742	/* Callback for htab_traverse to dump the VAR_INFOS hash table. */
1743
1744	int
1745	debug_var_infos_r (var_info **slot, FILE *file)
1746	{
1747	var_info *info = *slot;
1748
1749	fprintf (stream: file, format: "VAR: ");
1750	print_generic_expr (file, info->var, dump_flags);
1751	bitmap_print (file, info->info.def_blocks.def_blocks,
1752	", DEF_BLOCKS: { ", "}");
1753	bitmap_print (file, info->info.def_blocks.livein_blocks,
1754	", LIVEIN_BLOCKS: { ", "}");
1755	bitmap_print (file, info->info.def_blocks.phi_blocks,
1756	", PHI_BLOCKS: { ", "}\n");
1757
1758	return 1;
1759	}
1760
1761
1762	/* Dump the VAR_INFOS hash table on FILE. */
1763
1764	void
1765	dump_var_infos (FILE *file)
1766	{
1767	fprintf (stream: file, format: "\n\nDefinition and live-in blocks:\n\n");
1768	if (var_infos)
1769	var_infos->traverse <FILE *, debug_var_infos_r> (argument: file);
1770	}
1771
1772
1773	/* Dump the VAR_INFOS hash table on stderr. */
1774
1775	DEBUG_FUNCTION void
1776	debug_var_infos (void)
1777	{
1778	dump_var_infos (stderr);
1779	}
1780
1781
1782	/* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1783
1784	static inline void
1785	register_new_update_single (tree new_name, tree old_name)
1786	{
1787	common_info *info = get_common_info (var: old_name);
1788	tree currdef = info->current_def;
1789
1790	/* Push the current reaching definition into BLOCK_DEFS_STACK.
1791	This stack is later used by the dominator tree callbacks to
1792	restore the reaching definitions for all the variables
1793	defined in the block after a recursive visit to all its
1794	immediately dominated blocks. */
1795	block_defs_stack.reserve (nelems: 2);
1796	block_defs_stack.quick_push (obj: currdef);
1797	block_defs_stack.quick_push (obj: old_name);
1798
1799	/* Set the current reaching definition for OLD_NAME to be
1800	NEW_NAME. */
1801	info->current_def = new_name;
1802	}
1803
1804
1805	/* Register NEW_NAME to be the new reaching definition for all the
1806	names in OLD_NAMES. Used by the incremental SSA update routines to
1807	replace old SSA names with new ones. */
1808
1809	static inline void
1810	register_new_update_set (tree new_name, bitmap old_names)
1811	{
1812	bitmap_iterator bi;
1813	unsigned i;
1814
1815	EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
1816	register_new_update_single (new_name, ssa_name (i));
1817	}
1818
1819
1820
1821	/* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1822	it is a symbol marked for renaming, replace it with USE_P's current
1823	reaching definition. */
1824
1825	static inline void
1826	maybe_replace_use (use_operand_p use_p)
1827	{
1828	tree rdef = NULL_TREE;
1829	tree use = USE_FROM_PTR (use_p);
1830	tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1831
1832	if (marked_for_renaming (sym))
1833	rdef = get_reaching_def (var: sym);
1834	else if (is_old_name (name: use))
1835	rdef = get_reaching_def (var: use);
1836
1837	if (rdef && rdef != use)
1838	SET_USE (use_p, rdef);
1839	}
1840
1841
1842	/* Same as maybe_replace_use, but without introducing default stmts,
1843	returning false to indicate a need to do so. */
1844
1845	static inline bool
1846	maybe_replace_use_in_debug_stmt (use_operand_p use_p)
1847	{
1848	tree rdef = NULL_TREE;
1849	tree use = USE_FROM_PTR (use_p);
1850	tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1851
1852	if (marked_for_renaming (sym))
1853	rdef = get_var_info (decl: sym)->info.current_def;
1854	else if (is_old_name (name: use))
1855	{
1856	rdef = get_ssa_name_ann (name: use)->info.current_def;
1857	/* We can't assume that, if there's no current definition, the
1858	default one should be used. It could be the case that we've
1859	rearranged blocks so that the earlier definition no longer
1860	dominates the use. */
1861	if (!rdef && SSA_NAME_IS_DEFAULT_DEF (use))
1862	rdef = use;
1863	}
1864	else
1865	rdef = use;
1866
1867	if (rdef && rdef != use)
1868	SET_USE (use_p, rdef);
1869
1870	return rdef != NULL_TREE;
1871	}
1872
1873
1874	/* If DEF has x_5 = ASAN_POISON () as its current def, add
1875	ASAN_POISON_USE (x_5) stmt before GSI to denote the stmt writes into
1876	a poisoned (out of scope) variable. */
1877
1878	static void
1879	maybe_add_asan_poison_write (tree def, gimple_stmt_iterator *gsi)
1880	{
1881	tree cdef = get_current_def (var: def);
1882	if (cdef != NULL
1883	&& TREE_CODE (cdef) == SSA_NAME
1884	&& gimple_call_internal_p (SSA_NAME_DEF_STMT (cdef), fn: IFN_ASAN_POISON))
1885	{
1886	gcall *call
1887	= gimple_build_call_internal (IFN_ASAN_POISON_USE, 1, cdef);
1888	gimple_set_location (g: call, location: gimple_location (g: gsi_stmt (i: *gsi)));
1889	gsi_insert_before (gsi, call, GSI_SAME_STMT);
1890	}
1891	}
1892
1893
1894	/* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1895	or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1896	register it as the current definition for the names replaced by
1897	DEF_P. Returns whether the statement should be removed. */
1898
1899	static inline bool
1900	maybe_register_def (def_operand_p def_p, gimple *stmt,
1901	gimple_stmt_iterator gsi)
1902	{
1903	tree def = DEF_FROM_PTR (def_p);
1904	tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1905	bool to_delete = false;
1906
1907	/* If DEF is a naked symbol that needs renaming, create a new
1908	name for it. */
1909	if (marked_for_renaming (sym))
1910	{
1911	if (DECL_P (def))
1912	{
1913	if (gimple_clobber_p (s: stmt) && is_gimple_reg (sym))
1914	{
1915	tree defvar;
1916	if (VAR_P (sym))
1917	defvar = sym;
1918	else
1919	defvar = create_tmp_reg (TREE_TYPE (sym));
1920	/* Replace clobber stmts with a default def. This new use of a
1921	default definition may make it look like SSA_NAMEs have
1922	conflicting lifetimes, so we need special code to let them
1923	coalesce properly. */
1924	to_delete = true;
1925	def = get_or_create_ssa_default_def (cfun, defvar);
1926	}
1927	else
1928	{
1929	if (asan_sanitize_use_after_scope ())
1930	maybe_add_asan_poison_write (def, gsi: &gsi);
1931	def = make_ssa_name (var: def, stmt);
1932	}
1933	SET_DEF (def_p, def);
1934
1935	tree tracked_var = target_for_debug_bind (sym);
1936	if (tracked_var)
1937	{
1938	/* If stmt ends the bb, insert the debug stmt on the non-EH
1939	edge(s) from the stmt. */
1940	if (gsi_one_before_end_p (i: gsi) && stmt_ends_bb_p (stmt))
1941	{
1942	basic_block bb = gsi_bb (i: gsi);
1943	edge_iterator ei;
1944	edge e, ef = NULL;
1945	FOR_EACH_EDGE (e, ei, bb->succs)
1946	if (!(e->flags & EDGE_EH))
1947	{
1948	/* asm goto can have multiple non-EH edges from the
1949	stmt. Insert on all of them where it is
1950	possible. */
1951	gcc_checking_assert (!ef || (gimple_code (stmt)
1952	== GIMPLE_ASM));
1953	ef = e;
1954	/* If there are other predecessors to ef->dest, then
1955	there must be PHI nodes for the modified
1956	variable, and therefore there will be debug bind
1957	stmts after the PHI nodes. The debug bind notes
1958	we'd insert would force the creation of a new
1959	block (diverging codegen) and be redundant with
1960	the post-PHI bind stmts, so don't add them.
1961
1962	As for the exit edge, there wouldn't be redundant
1963	bind stmts, but there wouldn't be a PC to bind
1964	them to either, so avoid diverging the CFG. */
1965	if (e
1966	&& single_pred_p (bb: e->dest)
1967	&& gimple_seq_empty_p (s: phi_nodes (bb: e->dest))
1968	&& e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1969	{
1970	/* If there were PHI nodes in the node, we'd
1971	have to make sure the value we're binding
1972	doesn't need rewriting. But there shouldn't
1973	be PHI nodes in a single-predecessor block,
1974	so we just add the note. */
1975	gimple *note
1976	= gimple_build_debug_bind (tracked_var, def,
1977	stmt);
1978	gsi_insert_on_edge_immediate (ef, note);
1979	}
1980	}
1981	}
1982	else
1983	{
1984	gimple *note
1985	= gimple_build_debug_bind (tracked_var, def, stmt);
1986	gsi_insert_after (&gsi, note, GSI_SAME_STMT);
1987	}
1988	}
1989	}
1990
1991	register_new_update_single (new_name: def, old_name: sym);
1992	}
1993	else
1994	{
1995	/* If DEF is a new name, register it as a new definition
1996	for all the names replaced by DEF. */
1997	if (is_new_name (name: def))
1998	register_new_update_set (new_name: def, old_names: names_replaced_by (new_tree: def));
1999
2000	/* If DEF is an old name, register DEF as a new
2001	definition for itself. */
2002	if (is_old_name (name: def))
2003	register_new_update_single (new_name: def, old_name: def);
2004	}
2005
2006	return to_delete;
2007	}
2008
2009
2010	/* Update every variable used in the statement pointed-to by SI. The
2011	statement is assumed to be in SSA form already. Names in
2012	OLD_SSA_NAMES used by SI will be updated to their current reaching
2013	definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
2014	will be registered as a new definition for their corresponding name
2015	in OLD_SSA_NAMES. Returns whether STMT should be removed. */
2016
2017	static bool
2018	rewrite_update_stmt (gimple *stmt, gimple_stmt_iterator gsi)
2019	{
2020	use_operand_p use_p;
2021	def_operand_p def_p;
2022	ssa_op_iter iter;
2023
2024	/* Only update marked statements. */
2025	if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
2026	return false;
2027
2028	if (dump_file && (dump_flags & TDF_DETAILS))
2029	{
2030	fprintf (stream: dump_file, format: "Updating SSA information for statement ");
2031	print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2032	}
2033
2034	/* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
2035	symbol is marked for renaming. */
2036	if (rewrite_uses_p (stmt))
2037	{
2038	if (is_gimple_debug (gs: stmt))
2039	{
2040	bool failed = false;
2041
2042	FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
2043	if (!maybe_replace_use_in_debug_stmt (use_p))
2044	{
2045	failed = true;
2046	break;
2047	}
2048
2049	if (failed)
2050	{
2051	/* DOM sometimes threads jumps in such a way that a
2052	debug stmt ends up referencing a SSA variable that no
2053	longer dominates the debug stmt, but such that all
2054	incoming definitions refer to the same definition in
2055	an earlier dominator. We could try to recover that
2056	definition somehow, but this will have to do for now.
2057
2058	Introducing a default definition, which is what
2059	maybe_replace_use() would do in such cases, may
2060	modify code generation, for the otherwise-unused
2061	default definition would never go away, modifying SSA
2062	version numbers all over. */
2063	gimple_debug_bind_reset_value (dbg: stmt);
2064	update_stmt (s: stmt);
2065	}
2066	}
2067	else
2068	{
2069	FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
2070	maybe_replace_use (use_p);
2071	}
2072	}
2073
2074	/* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
2075	Also register definitions for names whose underlying symbol is
2076	marked for renaming. */
2077	bool to_delete = false;
2078	if (register_defs_p (stmt))
2079	FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
2080	to_delete |= maybe_register_def (def_p, stmt, gsi);
2081
2082	return to_delete;
2083	}
2084
2085
2086	/* Visit all the successor blocks of BB looking for PHI nodes. For
2087	every PHI node found, check if any of its arguments is in
2088	OLD_SSA_NAMES. If so, and if the argument has a current reaching
2089	definition, replace it. */
2090
2091	static void
2092	rewrite_update_phi_arguments (basic_block bb)
2093	{
2094	edge e;
2095	edge_iterator ei;
2096
2097	FOR_EACH_EDGE (e, ei, bb->succs)
2098	{
2099	vec<gphi *> phis;
2100
2101	if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
2102	continue;
2103
2104	phis = phis_to_rewrite[e->dest->index];
2105	for (gphi *phi : phis)
2106	{
2107	tree arg, lhs_sym, reaching_def = NULL;
2108	use_operand_p arg_p;
2109
2110	gcc_checking_assert (rewrite_uses_p (phi));
2111
2112	arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
2113	arg = USE_FROM_PTR (arg_p);
2114
2115	if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
2116	continue;
2117
2118	lhs_sym = SSA_NAME_VAR (gimple_phi_result (phi));
2119
2120	if (arg == NULL_TREE)
2121	{
2122	/* When updating a PHI node for a recently introduced
2123	symbol we may find NULL arguments. That's why we
2124	take the symbol from the LHS of the PHI node. */
2125	reaching_def = get_reaching_def (var: lhs_sym);
2126	}
2127	else
2128	{
2129	tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
2130
2131	if (marked_for_renaming (sym))
2132	reaching_def = get_reaching_def (var: sym);
2133	else if (is_old_name (name: arg))
2134	reaching_def = get_reaching_def (var: arg);
2135	}
2136
2137	/* Update the argument if there is a reaching def different
2138	from arg. */
2139	if (reaching_def && reaching_def != arg)
2140	{
2141	location_t locus;
2142	int arg_i = PHI_ARG_INDEX_FROM_USE (arg_p);
2143
2144	SET_USE (arg_p, reaching_def);
2145
2146	/* Virtual operands do not need a location. */
2147	if (virtual_operand_p (op: reaching_def))
2148	locus = UNKNOWN_LOCATION;
2149	/* If SSA update didn't insert this PHI the argument
2150	might have a location already, keep that. */
2151	else if (gimple_phi_arg_has_location (phi, i: arg_i))
2152	locus = gimple_phi_arg_location (phi, i: arg_i);
2153	else
2154	{
2155	gimple *stmt = SSA_NAME_DEF_STMT (reaching_def);
2156	gphi *other_phi = dyn_cast <gphi *> (p: stmt);
2157
2158	/* Single element PHI nodes behave like copies, so get the
2159	location from the phi argument. */
2160	if (other_phi
2161	&& gimple_phi_num_args (gs: other_phi) == 1)
2162	locus = gimple_phi_arg_location (phi: other_phi, i: 0);
2163	else
2164	locus = gimple_location (g: stmt);
2165	}
2166
2167	gimple_phi_arg_set_location (phi, i: arg_i, loc: locus);
2168	}
2169
2170	if (e->flags & EDGE_ABNORMAL)
2171	SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
2172	}
2173	}
2174	}
2175
2176	class rewrite_update_dom_walker : public dom_walker
2177	{
2178	public:
2179	rewrite_update_dom_walker (cdi_direction direction, int in_region_flag = -1)
2180	: dom_walker (direction, ALL_BLOCKS, (int *)(uintptr_t)-1),
2181	m_in_region_flag (in_region_flag) {}
2182
2183	edge before_dom_children (basic_block) final override;
2184	void after_dom_children (basic_block) final override;
2185
2186	int m_in_region_flag;
2187	};
2188
2189	/* Initialization of block data structures for the incremental SSA
2190	update pass. Create a block local stack of reaching definitions
2191	for new SSA names produced in this block (BLOCK_DEFS). Register
2192	new definitions for every PHI node in the block. */
2193
2194	edge
2195	rewrite_update_dom_walker::before_dom_children (basic_block bb)
2196	{
2197	bool is_abnormal_phi;
2198
2199	if (dump_file && (dump_flags & TDF_DETAILS))
2200	fprintf (stream: dump_file, format: "Registering new PHI nodes in block #%d\n",
2201	bb->index);
2202
2203	/* Mark the unwind point for this block. */
2204	block_defs_stack.safe_push (NULL_TREE);
2205
2206	if (m_in_region_flag != -1
2207	&& !(bb->flags & m_in_region_flag))
2208	return STOP;
2209
2210	if (!bitmap_bit_p (blocks_to_update, bb->index))
2211	return NULL;
2212
2213	/* Mark the LHS if any of the arguments flows through an abnormal
2214	edge. */
2215	is_abnormal_phi = bb_has_abnormal_pred (bb);
2216
2217	/* If any of the PHI nodes is a replacement for a name in
2218	OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
2219	register it as a new definition for its corresponding name. Also
2220	register definitions for names whose underlying symbols are
2221	marked for renaming. */
2222	for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (i: gsi);
2223	gsi_next (i: &gsi))
2224	{
2225	tree lhs, lhs_sym;
2226	gphi *phi = gsi.phi ();
2227
2228	if (!register_defs_p (stmt: phi))
2229	continue;
2230
2231	lhs = gimple_phi_result (gs: phi);
2232	lhs_sym = SSA_NAME_VAR (lhs);
2233
2234	if (marked_for_renaming (sym: lhs_sym))
2235	register_new_update_single (new_name: lhs, old_name: lhs_sym);
2236	else
2237	{
2238
2239	/* If LHS is a new name, register a new definition for all
2240	the names replaced by LHS. */
2241	if (is_new_name (name: lhs))
2242	register_new_update_set (new_name: lhs, old_names: names_replaced_by (new_tree: lhs));
2243
2244	/* If LHS is an OLD name, register it as a new definition
2245	for itself. */
2246	if (is_old_name (name: lhs))
2247	register_new_update_single (new_name: lhs, old_name: lhs);
2248	}
2249
2250	if (is_abnormal_phi)
2251	SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
2252	}
2253
2254	/* Step 2. Rewrite every variable used in each statement in the block. */
2255	for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); )
2256	if (rewrite_update_stmt (stmt: gsi_stmt (i: gsi), gsi))
2257	gsi_remove (&gsi, true);
2258	else
2259	gsi_next (i: &gsi);
2260
2261	/* Step 3. Update PHI nodes. */
2262	rewrite_update_phi_arguments (bb);
2263
2264	return NULL;
2265	}
2266
2267	/* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
2268	the current reaching definition of every name re-written in BB to
2269	the original reaching definition before visiting BB. This
2270	unwinding must be done in the opposite order to what is done in
2271	register_new_update_set. */
2272
2273	void
2274	rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
2275	{
2276	while (block_defs_stack.length () > 0)
2277	{
2278	tree var = block_defs_stack.pop ();
2279	tree saved_def;
2280
2281	/* NULL indicates the unwind stop point for this block (see
2282	rewrite_update_enter_block). */
2283	if (var == NULL)
2284	return;
2285
2286	saved_def = block_defs_stack.pop ();
2287	get_common_info (var)->current_def = saved_def;
2288	}
2289	}
2290
2291
2292	/* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2293	form.
2294
2295	ENTRY indicates the block where to start. Every block dominated by
2296	ENTRY will be rewritten.
2297
2298	WHAT indicates what actions will be taken by the renamer (see enum
2299	rewrite_mode).
2300
2301	REGION is a SEME region of interesting blocks for the dominator walker
2302	to process. If this set is invalid, then all the nodes dominated
2303	by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2304	are not present in BLOCKS are ignored. */
2305
2306	static void
2307	rewrite_blocks (basic_block entry, enum rewrite_mode what)
2308	{
2309	block_defs_stack.create (nelems: 10);
2310
2311	/* Recursively walk the dominator tree rewriting each statement in
2312	each basic block. */
2313	if (what == REWRITE_ALL)
2314	rewrite_dom_walker (CDI_DOMINATORS).walk (entry);
2315	else if (what == REWRITE_UPDATE)
2316	rewrite_update_dom_walker (CDI_DOMINATORS).walk (entry);
2317	else if (what == REWRITE_UPDATE_REGION)
2318	{
2319	/* First mark all blocks in the SEME region dominated by
2320	entry and exited by blocks not backwards reachable from
2321	blocks_to_update. Optimize for dense blocks_to_update
2322	so instead of seeding the worklist with a copy of
2323	blocks_to_update treat those blocks explicit. */
2324	auto_bb_flag in_region (cfun);
2325	auto_vec<basic_block, 64> extra_rgn;
2326	bitmap_iterator bi;
2327	unsigned int idx;
2328	EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, idx, bi)
2329	{
2330	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, idx);
2331	bb->flags |= in_region;
2332	}
2333	auto_bitmap worklist;
2334	EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, idx, bi)
2335	{
2336	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, idx);
2337	if (bb != entry)
2338	{
2339	edge_iterator ei;
2340	edge e;
2341	FOR_EACH_EDGE (e, ei, bb->preds)
2342	{
2343	if ((e->src->flags & in_region)
2344	|| dominated_by_p (CDI_DOMINATORS, e->src, bb))
2345	continue;
2346	bitmap_set_bit (worklist, e->src->index);
2347	}
2348	}
2349	}
2350	while (!bitmap_empty_p (map: worklist))
2351	{
2352	int idx = bitmap_clear_first_set_bit (worklist);
2353	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, idx);
2354	bb->flags |= in_region;
2355	extra_rgn.safe_push (obj: bb);
2356	if (bb != entry)
2357	{
2358	edge_iterator ei;
2359	edge e;
2360	FOR_EACH_EDGE (e, ei, bb->preds)
2361	{
2362	if ((e->src->flags & in_region)
2363	|| dominated_by_p (CDI_DOMINATORS, e->src, bb))
2364	continue;
2365	bitmap_set_bit (worklist, e->src->index);
2366	}
2367	}
2368	}
2369	rewrite_update_dom_walker (CDI_DOMINATORS, in_region).walk (entry);
2370	EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, idx, bi)
2371	{
2372	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, idx);
2373	bb->flags &= ~in_region;
2374	}
2375	for (auto bb : extra_rgn)
2376	bb->flags &= ~in_region;
2377	}
2378	else
2379	gcc_unreachable ();
2380
2381	/* Debugging dumps. */
2382	if (dump_file && (dump_flags & TDF_STATS))
2383	{
2384	dump_dfa_stats (dump_file);
2385	if (var_infos)
2386	dump_tree_ssa_stats (file: dump_file);
2387	}
2388
2389	block_defs_stack.release ();
2390	}
2391
2392	class mark_def_dom_walker : public dom_walker
2393	{
2394	public:
2395	mark_def_dom_walker (cdi_direction direction);
2396	~mark_def_dom_walker ();
2397
2398	edge before_dom_children (basic_block) final override;
2399
2400	private:
2401	/* Notice that this bitmap is indexed using variable UIDs, so it must be
2402	large enough to accommodate all the variables referenced in the
2403	function, not just the ones we are renaming. */
2404	bitmap m_kills;
2405	};
2406
2407	mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction)
2408	: dom_walker (direction, ALL_BLOCKS, NULL), m_kills (BITMAP_ALLOC (NULL))
2409	{
2410	}
2411
2412	mark_def_dom_walker::~mark_def_dom_walker ()
2413	{
2414	BITMAP_FREE (m_kills);
2415	}
2416
2417	/* Block processing routine for mark_def_sites. Clear the KILLS bitmap
2418	at the start of each block, and call mark_def_sites for each statement. */
2419
2420	edge
2421	mark_def_dom_walker::before_dom_children (basic_block bb)
2422	{
2423	gimple_stmt_iterator gsi;
2424
2425	bitmap_clear (m_kills);
2426	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
2427	mark_def_sites (bb, stmt: gsi_stmt (i: gsi), kills: m_kills);
2428	return NULL;
2429	}
2430
2431	/* Initialize internal data needed during renaming. */
2432
2433	static void
2434	init_ssa_renamer (void)
2435	{
2436	cfun->gimple_df->in_ssa_p = false;
2437
2438	/* Allocate memory for the DEF_BLOCKS hash table. */
2439	gcc_assert (!var_infos);
2440	var_infos = new hash_table<var_info_hasher>
2441	(vec_safe_length (cfun->local_decls));
2442
2443	bitmap_obstack_initialize (&update_ssa_obstack);
2444	}
2445
2446
2447	/* Deallocate internal data structures used by the renamer. */
2448
2449	static void
2450	fini_ssa_renamer (void)
2451	{
2452	delete var_infos;
2453	var_infos = NULL;
2454
2455	bitmap_obstack_release (&update_ssa_obstack);
2456
2457	cfun->gimple_df->ssa_renaming_needed = 0;
2458	cfun->gimple_df->rename_vops = 0;
2459	cfun->gimple_df->in_ssa_p = true;
2460	}
2461
2462	/* Main entry point into the SSA builder. The renaming process
2463	proceeds in four main phases:
2464
2465	1- Compute dominance frontier and immediate dominators, needed to
2466	insert PHI nodes and rename the function in dominator tree
2467	order.
2468
2469	2- Find and mark all the blocks that define variables.
2470
2471	3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2472
2473	4- Rename all the blocks (rewrite_blocks) and statements in the program.
2474
2475	Steps 3 and 4 are done using the dominator tree walker
2476	(walk_dominator_tree). */
2477
2478	namespace {
2479
2480	const pass_data pass_data_build_ssa =
2481	{
2482	.type: GIMPLE_PASS, /* type */
2483	.name: "ssa", /* name */
2484	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
2485	.tv_id: TV_TREE_INTO_SSA, /* tv_id */
2486	PROP_cfg, /* properties_required */
2487	PROP_ssa, /* properties_provided */
2488	.properties_destroyed: 0, /* properties_destroyed */
2489	.todo_flags_start: 0, /* todo_flags_start */
2490	TODO_remove_unused_locals, /* todo_flags_finish */
2491	};
2492
2493	class pass_build_ssa : public gimple_opt_pass
2494	{
2495	public:
2496	pass_build_ssa (gcc::context *ctxt)
2497	: gimple_opt_pass (pass_data_build_ssa, ctxt)
2498	{}
2499
2500	/* opt_pass methods: */
2501	bool gate (function *fun) final override
2502	{
2503	/* Do nothing for functions that were produced already in SSA form. */
2504	return !(fun->curr_properties & PROP_ssa);
2505	}
2506
2507	unsigned int execute (function *) final override;
2508
2509	}; // class pass_build_ssa
2510
2511	unsigned int
2512	pass_build_ssa::execute (function *fun)
2513	{
2514	bitmap_head *dfs;
2515	basic_block bb;
2516
2517	/* Increase the set of variables we can rewrite into SSA form
2518	by clearing TREE_ADDRESSABLE and transform the IL to support this. */
2519	if (optimize)
2520	execute_update_addresses_taken ();
2521
2522	/* Initialize operand data structures. */
2523	init_ssa_operands (fn: fun);
2524
2525	/* Initialize internal data needed by the renamer. */
2526	init_ssa_renamer ();
2527
2528	/* Initialize the set of interesting blocks. The callback
2529	mark_def_sites will add to this set those blocks that the renamer
2530	should process. */
2531	interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (fun));
2532	bitmap_clear (interesting_blocks);
2533
2534	/* Initialize dominance frontier. */
2535	dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (fun));
2536	FOR_EACH_BB_FN (bb, fun)
2537	bitmap_initialize (head: &dfs[bb->index], obstack: &bitmap_default_obstack);
2538
2539	/* 1- Compute dominance frontiers. */
2540	calculate_dominance_info (CDI_DOMINATORS);
2541	compute_dominance_frontiers (dfs);
2542
2543	/* 2- Find and mark definition sites. */
2544	mark_def_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
2545
2546	/* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2547	insert_phi_nodes (dfs);
2548
2549	/* 4- Rename all the blocks. */
2550	rewrite_blocks (ENTRY_BLOCK_PTR_FOR_FN (fun), what: REWRITE_ALL);
2551
2552	/* Free allocated memory. */
2553	FOR_EACH_BB_FN (bb, fun)
2554	bitmap_clear (&dfs[bb->index]);
2555	free (ptr: dfs);
2556
2557	sbitmap_free (map: interesting_blocks);
2558	interesting_blocks = NULL;
2559
2560	fini_ssa_renamer ();
2561
2562	/* Try to get rid of all gimplifier generated temporaries by making
2563	its SSA names anonymous. This way we can garbage collect them
2564	all after removing unused locals which we do in our TODO. */
2565	unsigned i;
2566	tree name;
2567
2568	FOR_EACH_SSA_NAME (i, name, cfun)
2569	{
2570	if (SSA_NAME_IS_DEFAULT_DEF (name))
2571	continue;
2572	tree decl = SSA_NAME_VAR (name);
2573	if (decl
2574	&& VAR_P (decl)
2575	&& !VAR_DECL_IS_VIRTUAL_OPERAND (decl)
2576	&& DECL_IGNORED_P (decl))
2577	SET_SSA_NAME_VAR_OR_IDENTIFIER (name, DECL_NAME (decl));
2578	}
2579
2580	/* Initialize SSA_NAME_POINTS_TO_READONLY_MEMORY. */
2581	tree fnspec_tree
2582	= lookup_attribute (attr_name: "fn spec",
2583	TYPE_ATTRIBUTES (TREE_TYPE (fun->decl)));
2584	if (fnspec_tree)
2585	{
2586	attr_fnspec fnspec (TREE_VALUE (TREE_VALUE (fnspec_tree)));
2587	unsigned i = 0;
2588	for (tree arg = DECL_ARGUMENTS (cfun->decl);
2589	arg; arg = DECL_CHAIN (arg), ++i)
2590	{
2591	if (!fnspec.arg_specified_p (i))
2592	break;
2593	if (fnspec.arg_readonly_p (i))
2594	{
2595	tree name = ssa_default_def (fun, arg);
2596	if (name)
2597	SSA_NAME_POINTS_TO_READONLY_MEMORY (name) = 1;
2598	}
2599	}
2600	}
2601
2602	return 0;
2603	}
2604
2605	} // anon namespace
2606
2607	gimple_opt_pass *
2608	make_pass_build_ssa (gcc::context *ctxt)
2609	{
2610	return new pass_build_ssa (ctxt);
2611	}
2612
2613
2614	/* Mark the definition of VAR at STMT and BB as interesting for the
2615	renamer. BLOCKS is the set of blocks that need updating. */
2616
2617	static void
2618	mark_def_interesting (tree var, gimple *stmt, basic_block bb,
2619	bool insert_phi_p)
2620	{
2621	gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
2622	set_register_defs (stmt, register_defs_p: true);
2623
2624	if (insert_phi_p)
2625	{
2626	bool is_phi_p = gimple_code (g: stmt) == GIMPLE_PHI;
2627
2628	set_def_block (var, bb, phi_p: is_phi_p);
2629
2630	/* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2631	site for both itself and all the old names replaced by it. */
2632	if (TREE_CODE (var) == SSA_NAME && is_new_name (name: var))
2633	{
2634	bitmap_iterator bi;
2635	unsigned i;
2636	bitmap set = names_replaced_by (new_tree: var);
2637	if (set)
2638	EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2639	set_def_block (ssa_name (i), bb, phi_p: is_phi_p);
2640	}
2641	}
2642	}
2643
2644
2645	/* Mark the use of VAR at STMT and BB as interesting for the
2646	renamer. INSERT_PHI_P is true if we are going to insert new PHI
2647	nodes. */
2648
2649	static inline void
2650	mark_use_interesting (tree var, gimple *stmt, basic_block bb,
2651	bool insert_phi_p)
2652	{
2653	basic_block def_bb = gimple_bb (g: stmt);
2654
2655	mark_block_for_update (bb: def_bb);
2656	mark_block_for_update (bb);
2657
2658	if (gimple_code (g: stmt) == GIMPLE_PHI)
2659	mark_phi_for_rewrite (bb: def_bb, phi: as_a <gphi *> (p: stmt));
2660	else
2661	{
2662	set_rewrite_uses (stmt, rewrite_p: true);
2663
2664	if (is_gimple_debug (gs: stmt))
2665	return;
2666	}
2667
2668	/* If VAR has not been defined in BB, then it is live-on-entry
2669	to BB. Note that we cannot just use the block holding VAR's
2670	definition because if VAR is one of the names in OLD_SSA_NAMES,
2671	it will have several definitions (itself and all the names that
2672	replace it). */
2673	if (insert_phi_p)
2674	{
2675	def_blocks *db_p = get_def_blocks_for (info: get_common_info (var));
2676	if (!bitmap_bit_p (db_p->def_blocks, bb->index))
2677	set_livein_block (var, bb);
2678	}
2679	}
2680
2681	/* Processing statements in BB that reference symbols in SSA operands.
2682	This is very similar to mark_def_sites, but the scan handles
2683	statements whose operands may already be SSA names.
2684
2685	If INSERT_PHI_P is true, mark those uses as live in the
2686	corresponding block. This is later used by the PHI placement
2687	algorithm to make PHI pruning decisions.
2688
2689	FIXME. Most of this would be unnecessary if we could associate a
2690	symbol to all the SSA names that reference it. But that
2691	sounds like it would be expensive to maintain. Still, it
2692	would be interesting to see if it makes better sense to do
2693	that. */
2694
2695	static void
2696	prepare_block_for_update_1 (basic_block bb, bool insert_phi_p)
2697	{
2698	edge e;
2699	edge_iterator ei;
2700
2701	mark_block_for_update (bb);
2702
2703	/* Process PHI nodes marking interesting those that define or use
2704	the symbols that we are interested in. */
2705	for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (i: si);
2706	gsi_next (i: &si))
2707	{
2708	gphi *phi = si.phi ();
2709	tree lhs_sym, lhs = gimple_phi_result (gs: phi);
2710
2711	if (TREE_CODE (lhs) == SSA_NAME
2712	&& (! virtual_operand_p (op: lhs)
2713	|| ! cfun->gimple_df->rename_vops))
2714	continue;
2715
2716	lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
2717	mark_for_renaming (sym: lhs_sym);
2718	mark_def_interesting (var: lhs_sym, stmt: phi, bb, insert_phi_p);
2719
2720	/* Mark the uses in phi nodes as interesting. It would be more correct
2721	to process the arguments of the phi nodes of the successor edges of
2722	BB at the end of prepare_block_for_update, however, that turns out
2723	to be significantly more expensive. Doing it here is conservatively
2724	correct -- it may only cause us to believe a value to be live in a
2725	block that also contains its definition, and thus insert a few more
2726	phi nodes for it. */
2727	FOR_EACH_EDGE (e, ei, bb->preds)
2728	mark_use_interesting (var: lhs_sym, stmt: phi, bb: e->src, insert_phi_p);
2729	}
2730
2731	/* Process the statements. */
2732	for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (i: si);
2733	gsi_next (i: &si))
2734	{
2735	gimple *stmt;
2736	ssa_op_iter i;
2737	use_operand_p use_p;
2738	def_operand_p def_p;
2739
2740	stmt = gsi_stmt (i: si);
2741
2742	if (cfun->gimple_df->rename_vops
2743	&& gimple_vuse (g: stmt))
2744	{
2745	tree use = gimple_vuse (g: stmt);
2746	tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
2747	mark_for_renaming (sym);
2748	mark_use_interesting (var: sym, stmt, bb, insert_phi_p);
2749	}
2750
2751	FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE)
2752	{
2753	tree use = USE_FROM_PTR (use_p);
2754	if (!DECL_P (use))
2755	continue;
2756	mark_for_renaming (sym: use);
2757	mark_use_interesting (var: use, stmt, bb, insert_phi_p);
2758	}
2759
2760	if (cfun->gimple_df->rename_vops
2761	&& gimple_vdef (g: stmt))
2762	{
2763	tree def = gimple_vdef (g: stmt);
2764	tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
2765	mark_for_renaming (sym);
2766	mark_def_interesting (var: sym, stmt, bb, insert_phi_p);
2767	}
2768
2769	FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF)
2770	{
2771	tree def = DEF_FROM_PTR (def_p);
2772	if (!DECL_P (def))
2773	continue;
2774	mark_for_renaming (sym: def);
2775	mark_def_interesting (var: def, stmt, bb, insert_phi_p);
2776	}
2777	}
2778
2779	}
2780
2781	/* Do a dominator walk starting at BB processing statements that
2782	reference symbols in SSA operands. This is very similar to
2783	mark_def_sites, but the scan handles statements whose operands may
2784	already be SSA names.
2785
2786	If INSERT_PHI_P is true, mark those uses as live in the
2787	corresponding block. This is later used by the PHI placement
2788	algorithm to make PHI pruning decisions.
2789
2790	FIXME. Most of this would be unnecessary if we could associate a
2791	symbol to all the SSA names that reference it. But that
2792	sounds like it would be expensive to maintain. Still, it
2793	would be interesting to see if it makes better sense to do
2794	that. */
2795	static void
2796	prepare_block_for_update (basic_block bb, bool insert_phi_p)
2797	{
2798	size_t sp = 0;
2799	basic_block *worklist;
2800
2801	/* Allocate the worklist. */
2802	worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
2803	/* Add the BB to the worklist. */
2804	worklist[sp++] = bb;
2805
2806	while (sp)
2807	{
2808	basic_block bb;
2809	basic_block son;
2810
2811	/* Pick a block from the worklist. */
2812	bb = worklist[--sp];
2813
2814	prepare_block_for_update_1 (bb, insert_phi_p);
2815
2816	/* Now add all the blocks dominated by BB to the worklist. */
2817	for (son = first_dom_son (CDI_DOMINATORS, bb);
2818	son;
2819	son = next_dom_son (CDI_DOMINATORS, son))
2820	worklist[sp++] = son;
2821	}
2822	free (ptr: worklist);
2823	}
2824
2825	/* Helper for prepare_names_to_update. Mark all the use sites for
2826	NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2827	prepare_names_to_update. */
2828
2829	static void
2830	prepare_use_sites_for (tree name, bool insert_phi_p)
2831	{
2832	use_operand_p use_p;
2833	imm_use_iterator iter;
2834
2835	/* If we rename virtual operands do not update them. */
2836	if (virtual_operand_p (op: name)
2837	&& cfun->gimple_df->rename_vops)
2838	return;
2839
2840	FOR_EACH_IMM_USE_FAST (use_p, iter, name)
2841	{
2842	gimple *stmt = USE_STMT (use_p);
2843	basic_block bb = gimple_bb (g: stmt);
2844
2845	if (gimple_code (g: stmt) == GIMPLE_PHI)
2846	{
2847	int ix = PHI_ARG_INDEX_FROM_USE (use_p);
2848	edge e = gimple_phi_arg_edge (phi: as_a <gphi *> (p: stmt), i: ix);
2849	mark_use_interesting (var: name, stmt, bb: e->src, insert_phi_p);
2850	}
2851	else
2852	{
2853	/* For regular statements, mark this as an interesting use
2854	for NAME. */
2855	mark_use_interesting (var: name, stmt, bb, insert_phi_p);
2856	}
2857	}
2858	}
2859
2860
2861	/* Helper for prepare_names_to_update. Mark the definition site for
2862	NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2863	prepare_names_to_update. */
2864
2865	static void
2866	prepare_def_site_for (tree name, bool insert_phi_p)
2867	{
2868	gimple *stmt;
2869	basic_block bb;
2870
2871	gcc_checking_assert (names_to_release == NULL
2872	|| !bitmap_bit_p (names_to_release,
2873	SSA_NAME_VERSION (name)));
2874
2875	/* If we rename virtual operands do not update them. */
2876	if (virtual_operand_p (op: name)
2877	&& cfun->gimple_df->rename_vops)
2878	return;
2879
2880	stmt = SSA_NAME_DEF_STMT (name);
2881	bb = gimple_bb (g: stmt);
2882	if (bb)
2883	{
2884	gcc_checking_assert (bb->index < last_basic_block_for_fn (cfun));
2885	mark_block_for_update (bb);
2886	mark_def_interesting (var: name, stmt, bb, insert_phi_p);
2887	}
2888	}
2889
2890
2891	/* Mark definition and use sites of names in NEW_SSA_NAMES and
2892	OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2893	PHI nodes for newly created names. */
2894
2895	static void
2896	prepare_names_to_update (bool insert_phi_p)
2897	{
2898	unsigned i = 0;
2899	bitmap_iterator bi;
2900	sbitmap_iterator sbi;
2901
2902	/* If a name N from NEW_SSA_NAMES is also marked to be released,
2903	remove it from NEW_SSA_NAMES so that we don't try to visit its
2904	defining basic block (which most likely doesn't exist). Notice
2905	that we cannot do the same with names in OLD_SSA_NAMES because we
2906	want to replace existing instances. */
2907	if (names_to_release)
2908	EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2909	bitmap_clear_bit (map: new_ssa_names, bitno: i);
2910
2911	/* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2912	names may be considered to be live-in on blocks that contain
2913	definitions for their replacements. */
2914	EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2915	prepare_def_site_for (ssa_name (i), insert_phi_p);
2916
2917	/* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2918	OLD_SSA_NAMES, but we have to ignore its definition site. */
2919	EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
2920	{
2921	if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
2922	prepare_def_site_for (ssa_name (i), insert_phi_p);
2923	prepare_use_sites_for (ssa_name (i), insert_phi_p);
2924	}
2925	}
2926
2927
2928	/* Dump all the names replaced by NAME to FILE. */
2929
2930	void
2931	dump_names_replaced_by (FILE *file, tree name)
2932	{
2933	unsigned i;
2934	bitmap old_set;
2935	bitmap_iterator bi;
2936
2937	print_generic_expr (file, name);
2938	fprintf (stream: file, format: " -> { ");
2939
2940	old_set = names_replaced_by (new_tree: name);
2941	EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
2942	{
2943	print_generic_expr (file, ssa_name (i));
2944	fprintf (stream: file, format: " ");
2945	}
2946
2947	fprintf (stream: file, format: "}\n");
2948	}
2949
2950
2951	/* Dump all the names replaced by NAME to stderr. */
2952
2953	DEBUG_FUNCTION void
2954	debug_names_replaced_by (tree name)
2955	{
2956	dump_names_replaced_by (stderr, name);
2957	}
2958
2959
2960	/* Dump SSA update information to FILE. */
2961
2962	void
2963	dump_update_ssa (FILE *file)
2964	{
2965	unsigned i = 0;
2966	bitmap_iterator bi;
2967
2968	if (!need_ssa_update_p (cfun))
2969	return;
2970
2971	if (new_ssa_names && !bitmap_empty_p (new_ssa_names))
2972	{
2973	sbitmap_iterator sbi;
2974
2975	fprintf (stream: file, format: "\nSSA replacement table\n");
2976	fprintf (stream: file, format: "N_i -> { O_1 ... O_j } means that N_i replaces "
2977	"O_1, ..., O_j\n\n");
2978
2979	EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2980	dump_names_replaced_by (file, ssa_name (i));
2981	}
2982
2983	if (symbols_to_rename_set && !bitmap_empty_p (map: symbols_to_rename_set))
2984	{
2985	fprintf (stream: file, format: "\nSymbols to be put in SSA form\n");
2986	dump_decl_set (file, symbols_to_rename_set);
2987	fprintf (stream: file, format: "\n");
2988	}
2989
2990	if (names_to_release && !bitmap_empty_p (map: names_to_release))
2991	{
2992	fprintf (stream: file, format: "\nSSA names to release after updating the SSA web\n\n");
2993	EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2994	{
2995	print_generic_expr (file, ssa_name (i));
2996	fprintf (stream: file, format: " ");
2997	}
2998	fprintf (stream: file, format: "\n");
2999	}
3000	}
3001
3002
3003	/* Dump SSA update information to stderr. */
3004
3005	DEBUG_FUNCTION void
3006	debug_update_ssa (void)
3007	{
3008	dump_update_ssa (stderr);
3009	}
3010
3011
3012	/* Initialize data structures used for incremental SSA updates. */
3013
3014	static void
3015	init_update_ssa (struct function *fn)
3016	{
3017	/* Reserve more space than the current number of names. The calls to
3018	add_new_name_mapping are typically done after creating new SSA
3019	names, so we'll need to reallocate these arrays. */
3020	old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
3021	bitmap_clear (old_ssa_names);
3022
3023	new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
3024	bitmap_clear (new_ssa_names);
3025
3026	bitmap_obstack_initialize (&update_ssa_obstack);
3027
3028	names_to_release = NULL;
3029	update_ssa_initialized_fn = fn;
3030	}
3031
3032
3033	/* Deallocate data structures used for incremental SSA updates. */
3034
3035	void
3036	delete_update_ssa (void)
3037	{
3038	unsigned i;
3039	bitmap_iterator bi;
3040
3041	sbitmap_free (map: old_ssa_names);
3042	old_ssa_names = NULL;
3043
3044	sbitmap_free (map: new_ssa_names);
3045	new_ssa_names = NULL;
3046
3047	BITMAP_FREE (symbols_to_rename_set);
3048	symbols_to_rename_set = NULL;
3049	symbols_to_rename.release ();
3050
3051	if (names_to_release)
3052	{
3053	EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
3054	release_ssa_name (ssa_name (i));
3055	BITMAP_FREE (names_to_release);
3056	}
3057
3058	clear_ssa_name_info ();
3059
3060	fini_ssa_renamer ();
3061
3062	if (blocks_with_phis_to_rewrite)
3063	EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
3064	phis_to_rewrite[i].release ();
3065
3066	BITMAP_FREE (blocks_with_phis_to_rewrite);
3067	BITMAP_FREE (blocks_to_update);
3068
3069	update_ssa_initialized_fn = NULL;
3070	}
3071
3072
3073	/* Create a new name for OLD_NAME in statement STMT and replace the
3074	operand pointed to by DEF_P with the newly created name. If DEF_P
3075	is NULL then STMT should be a GIMPLE assignment.
3076	Return the new name and register the replacement mapping <NEW, OLD> in
3077	update_ssa's tables. */
3078
3079	tree
3080	create_new_def_for (tree old_name, gimple *stmt, def_operand_p def)
3081	{
3082	tree new_name;
3083
3084	timevar_push (tv: TV_TREE_SSA_INCREMENTAL);
3085
3086	if (!update_ssa_initialized_fn)
3087	init_update_ssa (cfun);
3088
3089	gcc_assert (update_ssa_initialized_fn == cfun);
3090
3091	new_name = duplicate_ssa_name (var: old_name, stmt);
3092	if (def)
3093	SET_DEF (def, new_name);
3094	else
3095	gimple_assign_set_lhs (gs: stmt, lhs: new_name);
3096
3097	if (gimple_code (g: stmt) == GIMPLE_PHI)
3098	{
3099	basic_block bb = gimple_bb (g: stmt);
3100
3101	/* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
3102	SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = bb_has_abnormal_pred (bb);
3103	}
3104
3105	add_new_name_mapping (new_tree: new_name, old: old_name);
3106
3107	/* For the benefit of passes that will be updating the SSA form on
3108	their own, set the current reaching definition of OLD_NAME to be
3109	NEW_NAME. */
3110	get_ssa_name_ann (name: old_name)->info.current_def = new_name;
3111
3112	timevar_pop (tv: TV_TREE_SSA_INCREMENTAL);
3113
3114	return new_name;
3115	}
3116
3117
3118	/* Mark virtual operands of FN for renaming by update_ssa. */
3119
3120	void
3121	mark_virtual_operands_for_renaming (struct function *fn)
3122	{
3123	fn->gimple_df->ssa_renaming_needed = 1;
3124	fn->gimple_df->rename_vops = 1;
3125	}
3126
3127	/* Replace all uses of NAME by underlying variable and mark it
3128	for renaming. This assumes the defining statement of NAME is
3129	going to be removed. */
3130
3131	void
3132	mark_virtual_operand_for_renaming (tree name)
3133	{
3134	tree name_var = SSA_NAME_VAR (name);
3135	bool used = false;
3136	imm_use_iterator iter;
3137	use_operand_p use_p;
3138	gimple *stmt;
3139
3140	gcc_assert (VAR_DECL_IS_VIRTUAL_OPERAND (name_var));
3141	FOR_EACH_IMM_USE_STMT (stmt, iter, name)
3142	{
3143	FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3144	SET_USE (use_p, name_var);
3145	used = true;
3146	}
3147	if (used)
3148	mark_virtual_operands_for_renaming (cfun);
3149	}
3150
3151	/* Replace all uses of the virtual PHI result by its underlying variable
3152	and mark it for renaming. This assumes the PHI node is going to be
3153	removed. */
3154
3155	void
3156	mark_virtual_phi_result_for_renaming (gphi *phi)
3157	{
3158	if (dump_file && (dump_flags & TDF_DETAILS))
3159	{
3160	fprintf (stream: dump_file, format: "Marking result for renaming : ");
3161	print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
3162	fprintf (stream: dump_file, format: "\n");
3163	}
3164
3165	mark_virtual_operand_for_renaming (name: gimple_phi_result (gs: phi));
3166	}
3167
3168	/* Return true if there is any work to be done by update_ssa
3169	for function FN. */
3170
3171	bool
3172	need_ssa_update_p (struct function *fn)
3173	{
3174	gcc_assert (fn != NULL);
3175	return (update_ssa_initialized_fn == fn
3176	|| (fn->gimple_df && fn->gimple_df->ssa_renaming_needed));
3177	}
3178
3179	/* Return true if name N has been registered in the replacement table. */
3180
3181	bool
3182	name_registered_for_update_p (tree n ATTRIBUTE_UNUSED)
3183	{
3184	if (!update_ssa_initialized_fn)
3185	return false;
3186
3187	gcc_assert (update_ssa_initialized_fn == cfun);
3188
3189	return is_new_name (name: n) || is_old_name (name: n);
3190	}
3191
3192
3193	/* Mark NAME to be released after update_ssa has finished. */
3194
3195	void
3196	release_ssa_name_after_update_ssa (tree name)
3197	{
3198	gcc_assert (cfun && update_ssa_initialized_fn == cfun);
3199
3200	if (names_to_release == NULL)
3201	names_to_release = BITMAP_ALLOC (NULL);
3202
3203	bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
3204	}
3205
3206
3207	/* Insert new PHI nodes to replace VAR. DFS contains dominance
3208	frontier information.
3209
3210	This is slightly different than the regular PHI insertion
3211	algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
3212	real names (i.e., GIMPLE registers) are inserted:
3213
3214	- If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
3215	nodes inside the region affected by the block that defines VAR
3216	and the blocks that define all its replacements. All these
3217	definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
3218
3219	First, we compute the entry point to the region (ENTRY). This is
3220	given by the nearest common dominator to all the definition
3221	blocks. When computing the iterated dominance frontier (IDF), any
3222	block not strictly dominated by ENTRY is ignored.
3223
3224	We then call the standard PHI insertion algorithm with the pruned
3225	IDF.
3226
3227	- If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
3228	names is not pruned. PHI nodes are inserted at every IDF block. */
3229
3230	static void
3231	insert_updated_phi_nodes_for (tree var, bitmap_head *dfs,
3232	unsigned update_flags)
3233	{
3234	basic_block entry;
3235	def_blocks *db;
3236	bitmap idf, pruned_idf;
3237	bitmap_iterator bi;
3238	unsigned i;
3239
3240	if (TREE_CODE (var) == SSA_NAME)
3241	gcc_checking_assert (is_old_name (var));
3242	else
3243	gcc_checking_assert (marked_for_renaming (var));
3244
3245	/* Get all the definition sites for VAR. */
3246	db = find_def_blocks_for (var);
3247
3248	/* No need to do anything if there were no definitions to VAR. */
3249	if (db == NULL || bitmap_empty_p (map: db->def_blocks))
3250	return;
3251
3252	/* Compute the initial iterated dominance frontier. */
3253	idf = compute_idf (db->def_blocks, dfs);
3254	pruned_idf = BITMAP_ALLOC (NULL);
3255
3256	if (TREE_CODE (var) == SSA_NAME)
3257	{
3258	if (update_flags == TODO_update_ssa)
3259	{
3260	/* If doing regular SSA updates for GIMPLE registers, we are
3261	only interested in IDF blocks dominated by the nearest
3262	common dominator of all the definition blocks. */
3263	entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
3264	db->def_blocks);
3265	if (entry != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3266	EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
3267	if (BASIC_BLOCK_FOR_FN (cfun, i) != entry
3268	&& dominated_by_p (CDI_DOMINATORS,
3269	BASIC_BLOCK_FOR_FN (cfun, i), entry))
3270	bitmap_set_bit (pruned_idf, i);
3271	}
3272	else
3273	{
3274	/* Otherwise, do not prune the IDF for VAR. */
3275	gcc_checking_assert (update_flags == TODO_update_ssa_full_phi);
3276	bitmap_copy (pruned_idf, idf);
3277	}
3278	}
3279	else
3280	{
3281	/* Otherwise, VAR is a symbol that needs to be put into SSA form
3282	for the first time, so we need to compute the full IDF for
3283	it. */
3284	bitmap_copy (pruned_idf, idf);
3285	}
3286
3287	if (!bitmap_empty_p (map: pruned_idf))
3288	{
3289	/* Make sure that PRUNED_IDF blocks and all their feeding blocks
3290	are included in the region to be updated. The feeding blocks
3291	are important to guarantee that the PHI arguments are renamed
3292	properly. */
3293
3294	/* FIXME, this is not needed if we are updating symbols. We are
3295	already starting at the ENTRY block anyway. */
3296	EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
3297	{
3298	edge e;
3299	edge_iterator ei;
3300	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
3301
3302	mark_block_for_update (bb);
3303	FOR_EACH_EDGE (e, ei, bb->preds)
3304	if (e->src->index >= 0)
3305	mark_block_for_update (bb: e->src);
3306	}
3307
3308	insert_phi_nodes_for (var, phi_insertion_points: pruned_idf, update_p: true);
3309	}
3310
3311	BITMAP_FREE (pruned_idf);
3312	BITMAP_FREE (idf);
3313	}
3314
3315	/* Sort symbols_to_rename after their DECL_UID. */
3316
3317	static int
3318	insert_updated_phi_nodes_compare_uids (const void *a, const void *b)
3319	{
3320	const_tree syma = *(const const_tree *)a;
3321	const_tree symb = *(const const_tree *)b;
3322	if (DECL_UID (syma) == DECL_UID (symb))
3323	return 0;
3324	return DECL_UID (syma) < DECL_UID (symb) ? -1 : 1;
3325	}
3326
3327	/* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3328	existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3329
3330	1- The names in OLD_SSA_NAMES dominated by the definitions of
3331	NEW_SSA_NAMES are all re-written to be reached by the
3332	appropriate definition from NEW_SSA_NAMES.
3333
3334	2- If needed, new PHI nodes are added to the iterated dominance
3335	frontier of the blocks where each of NEW_SSA_NAMES are defined.
3336
3337	The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3338	calling create_new_def_for to create new defs for names that the
3339	caller wants to replace.
3340
3341	The caller cretaes the new names to be inserted and the names that need
3342	to be replaced by calling create_new_def_for for each old definition
3343	to be replaced. Note that the function assumes that the
3344	new defining statement has already been inserted in the IL.
3345
3346	For instance, given the following code:
3347
3348	1 L0:
3349	2 x_1 = PHI (0, x_5)
3350	3 if (x_1 < 10)
3351	4 if (x_1 > 7)
3352	5 y_2 = 0
3353	6 else
3354	7 y_3 = x_1 + x_7
3355	8 endif
3356	9 x_5 = x_1 + 1
3357	10 goto L0;
3358	11 endif
3359
3360	Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3361
3362	1 L0:
3363	2 x_1 = PHI (0, x_5)
3364	3 if (x_1 < 10)
3365	4 x_10 = ...
3366	5 if (x_1 > 7)
3367	6 y_2 = 0
3368	7 else
3369	8 x_11 = ...
3370	9 y_3 = x_1 + x_7
3371	10 endif
3372	11 x_5 = x_1 + 1
3373	12 goto L0;
3374	13 endif
3375
3376	We want to replace all the uses of x_1 with the new definitions of
3377	x_10 and x_11. Note that the only uses that should be replaced are
3378	those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3379	*not* be replaced (this is why we cannot just mark symbol 'x' for
3380	renaming).
3381
3382	Additionally, we may need to insert a PHI node at line 11 because
3383	that is a merge point for x_10 and x_11. So the use of x_1 at line
3384	11 will be replaced with the new PHI node. The insertion of PHI
3385	nodes is optional. They are not strictly necessary to preserve the
3386	SSA form, and depending on what the caller inserted, they may not
3387	even be useful for the optimizers. UPDATE_FLAGS controls various
3388	aspects of how update_ssa operates, see the documentation for
3389	TODO_update_ssa*. */
3390
3391	void
3392	update_ssa (unsigned update_flags)
3393	{
3394	basic_block bb, start_bb;
3395	bitmap_iterator bi;
3396	unsigned i = 0;
3397	bool insert_phi_p;
3398	sbitmap_iterator sbi;
3399	tree sym;
3400
3401	/* Only one update flag should be set. */
3402	gcc_assert (update_flags == TODO_update_ssa
3403	|| update_flags == TODO_update_ssa_no_phi
3404	|| update_flags == TODO_update_ssa_full_phi
3405	|| update_flags == TODO_update_ssa_only_virtuals);
3406
3407	if (!need_ssa_update_p (cfun))
3408	return;
3409
3410	if (flag_checking)
3411	{
3412	timevar_push (tv: TV_TREE_STMT_VERIFY);
3413
3414	bool err = false;
3415
3416	FOR_EACH_BB_FN (bb, cfun)
3417	{
3418	gimple_stmt_iterator gsi;
3419	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
3420	{
3421	gimple *stmt = gsi_stmt (i: gsi);
3422
3423	ssa_op_iter i;
3424	use_operand_p use_p;
3425	FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_ALL_USES)
3426	{
3427	tree use = USE_FROM_PTR (use_p);
3428	if (TREE_CODE (use) != SSA_NAME)
3429	continue;
3430
3431	if (SSA_NAME_IN_FREE_LIST (use))
3432	{
3433	error ("statement uses released SSA name");
3434	debug_gimple_stmt (stmt);
3435	fprintf (stderr, format: "The use of ");
3436	print_generic_expr (stderr, use);
3437	fprintf (stderr,format: " should have been replaced\n");
3438	err = true;
3439	}
3440	}
3441	}
3442	}
3443
3444	if (err)
3445	internal_error ("cannot update SSA form");
3446
3447	timevar_pop (tv: TV_TREE_STMT_VERIFY);
3448	}
3449
3450	timevar_push (tv: TV_TREE_SSA_INCREMENTAL);
3451
3452	if (dump_file && (dump_flags & TDF_DETAILS))
3453	fprintf (stream: dump_file, format: "\nUpdating SSA:\n");
3454
3455	if (!update_ssa_initialized_fn)
3456	init_update_ssa (cfun);
3457	else if (update_flags == TODO_update_ssa_only_virtuals)
3458	{
3459	/* If we only need to update virtuals, remove all the mappings for
3460	real names before proceeding. The caller is responsible for
3461	having dealt with the name mappings before calling update_ssa. */
3462	bitmap_clear (old_ssa_names);
3463	bitmap_clear (new_ssa_names);
3464	}
3465
3466	gcc_assert (update_ssa_initialized_fn == cfun);
3467
3468	blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
3469	if (!phis_to_rewrite.exists ())
3470	phis_to_rewrite.create (last_basic_block_for_fn (cfun) + 1);
3471	blocks_to_update = BITMAP_ALLOC (NULL);
3472
3473	insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
3474
3475	/* Ensure that the dominance information is up-to-date and when we
3476	are going to compute dominance frontiers fast queries are possible. */
3477	if (insert_phi_p || dom_info_state (CDI_DOMINATORS) == DOM_NONE)
3478	calculate_dominance_info (CDI_DOMINATORS);
3479
3480	/* If there are names defined in the replacement table, prepare
3481	definition and use sites for all the names in NEW_SSA_NAMES and
3482	OLD_SSA_NAMES. */
3483	if (!bitmap_empty_p (new_ssa_names))
3484	{
3485	statistics_counter_event (cfun, "Incremental SSA update", 1);
3486
3487	prepare_names_to_update (insert_phi_p);
3488
3489	/* If all the names in NEW_SSA_NAMES had been marked for
3490	removal, and there are no symbols to rename, then there's
3491	nothing else to do. */
3492	if (bitmap_empty_p (new_ssa_names)
3493	&& !cfun->gimple_df->ssa_renaming_needed)
3494	goto done;
3495	}
3496
3497	/* Next, determine the block at which to start the renaming process. */
3498	if (cfun->gimple_df->ssa_renaming_needed)
3499	{
3500	statistics_counter_event (cfun, "Symbol to SSA rewrite", 1);
3501
3502	/* If we rename bare symbols initialize the mapping to
3503	auxiliar info we need to keep track of. */
3504	var_infos = new hash_table<var_info_hasher> (47);
3505
3506	/* If we have to rename some symbols from scratch, we need to
3507	start the process at the root of the CFG. FIXME, it should
3508	be possible to determine the nearest block that had a
3509	definition for each of the symbols that are marked for
3510	updating. For now this seems more work than it's worth. */
3511	start_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3512
3513	/* Traverse the CFG looking for existing definitions and uses of
3514	symbols in SSA operands. Mark interesting blocks and
3515	statements and set local live-in information for the PHI
3516	placement heuristics. */
3517	prepare_block_for_update (bb: start_bb, insert_phi_p);
3518
3519	tree name;
3520
3521	if (flag_checking)
3522	FOR_EACH_SSA_NAME (i, name, cfun)
3523	{
3524	if (virtual_operand_p (op: name))
3525	continue;
3526
3527	/* For all but virtual operands, which do not have SSA names
3528	with overlapping life ranges, ensure that symbols marked
3529	for renaming do not have existing SSA names associated with
3530	them as we do not re-write them out-of-SSA before going
3531	into SSA for the remaining symbol uses. */
3532	if (marked_for_renaming (SSA_NAME_VAR (name)))
3533	{
3534	fprintf (stderr, format: "Existing SSA name for symbol marked for "
3535	"renaming: ");
3536	print_generic_expr (stderr, name, TDF_SLIM);
3537	fprintf (stderr, format: "\n");
3538	internal_error ("SSA corruption");
3539	}
3540	}
3541	}
3542	else
3543	{
3544	/* Otherwise, the entry block to the region is the nearest
3545	common dominator for the blocks in BLOCKS. */
3546	start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3547	blocks_to_update);
3548	}
3549
3550	/* If requested, insert PHI nodes at the iterated dominance frontier
3551	of every block, creating new definitions for names in OLD_SSA_NAMES
3552	and for symbols found. */
3553	if (insert_phi_p)
3554	{
3555	bitmap_head *dfs;
3556
3557	/* If the caller requested PHI nodes to be added, compute
3558	dominance frontiers. */
3559	dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
3560	FOR_EACH_BB_FN (bb, cfun)
3561	bitmap_initialize (head: &dfs[bb->index], obstack: &bitmap_default_obstack);
3562	compute_dominance_frontiers (dfs);
3563
3564	bitmap_tree_view (blocks_to_update);
3565
3566	/* insert_update_phi_nodes_for will call add_new_name_mapping
3567	when inserting new PHI nodes, but it will not add any
3568	new members to OLD_SSA_NAMES. */
3569	iterating_old_ssa_names = true;
3570	sbitmap_iterator sbi;
3571	EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
3572	insert_updated_phi_nodes_for (ssa_name (i), dfs, update_flags);
3573	iterating_old_ssa_names = false;
3574
3575	symbols_to_rename.qsort (insert_updated_phi_nodes_compare_uids);
3576	FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3577	insert_updated_phi_nodes_for (var: sym, dfs, update_flags);
3578
3579	bitmap_list_view (blocks_to_update);
3580
3581	FOR_EACH_BB_FN (bb, cfun)
3582	bitmap_clear (&dfs[bb->index]);
3583	free (ptr: dfs);
3584
3585	/* Insertion of PHI nodes may have added blocks to the region.
3586	We need to re-compute START_BB to include the newly added
3587	blocks. */
3588	if (start_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3589	start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3590	blocks_to_update);
3591	}
3592
3593	/* Reset the current definition for name and symbol before renaming
3594	the sub-graph. */
3595	EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
3596	get_ssa_name_ann (ssa_name (i))->info.current_def = NULL_TREE;
3597
3598	FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3599	get_var_info (decl: sym)->info.current_def = NULL_TREE;
3600
3601	/* Now start the renaming process at START_BB. When not inserting PHIs
3602	and thus we are avoiding work on all blocks, try to confine the
3603	rewriting domwalk to the affected region, otherwise it's not worth it. */
3604	rewrite_blocks (entry: start_bb,
3605	what: insert_phi_p ? REWRITE_UPDATE : REWRITE_UPDATE_REGION);
3606
3607	/* Debugging dumps. */
3608	if (dump_file)
3609	{
3610	int c;
3611	unsigned i;
3612
3613	dump_update_ssa (file: dump_file);
3614
3615	fprintf (stream: dump_file, format: "Incremental SSA update started at block: %d\n",
3616	start_bb->index);
3617
3618	c = 0;
3619	EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3620	c++;
3621	fprintf (stream: dump_file, format: "Number of blocks in CFG: %d\n",
3622	last_basic_block_for_fn (cfun));
3623	fprintf (stream: dump_file, format: "Number of blocks to update: %d (%3.0f%%)\n",
3624	c, PERCENT (c, last_basic_block_for_fn (cfun)));
3625
3626	if (dump_flags & TDF_DETAILS)
3627	{
3628	fprintf (stream: dump_file, format: "Affected blocks:");
3629	EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3630	fprintf (stream: dump_file, format: " %u", i);
3631	fprintf (stream: dump_file, format: "\n");
3632	}
3633
3634	fprintf (stream: dump_file, format: "\n\n");
3635	}
3636
3637	/* Free allocated memory. */
3638	done:
3639	delete_update_ssa ();
3640
3641	timevar_pop (tv: TV_TREE_SSA_INCREMENTAL);
3642	}
3643