1	/* Rewrite a program in Normal form into SSA.
2	Copyright (C) 2001-2023 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 %ld, %ld elements, %f collision/search ratio\n",
1711	(long) htab.size (),
1712	(long) htab.elements (),
1713	htab.collisions ());
1714	}
1715
1716
1717	/* Dump SSA statistics on FILE. */
1718
1719	void
1720	dump_tree_ssa_stats (FILE *file)
1721	{
1722	if (var_infos)
1723	{
1724	fprintf (stream: file, format: "\nHash table statistics:\n");
1725	fprintf (stream: file, format: " var_infos: ");
1726	htab_statistics (file, htab: *var_infos);
1727	fprintf (stream: file, format: "\n");
1728	}
1729	}
1730
1731
1732	/* Dump SSA statistics on stderr. */
1733
1734	DEBUG_FUNCTION void
1735	debug_tree_ssa_stats (void)
1736	{
1737	dump_tree_ssa_stats (stderr);
1738	}
1739
1740
1741	/* Callback for htab_traverse to dump the VAR_INFOS hash table. */
1742
1743	int
1744	debug_var_infos_r (var_info **slot, FILE *file)
1745	{
1746	var_info *info = *slot;
1747
1748	fprintf (stream: file, format: "VAR: ");
1749	print_generic_expr (file, info->var, dump_flags);
1750	bitmap_print (file, info->info.def_blocks.def_blocks,
1751	", DEF_BLOCKS: { ", "}");
1752	bitmap_print (file, info->info.def_blocks.livein_blocks,
1753	", LIVEIN_BLOCKS: { ", "}");
1754	bitmap_print (file, info->info.def_blocks.phi_blocks,
1755	", PHI_BLOCKS: { ", "}\n");
1756
1757	return 1;
1758	}
1759
1760
1761	/* Dump the VAR_INFOS hash table on FILE. */
1762
1763	void
1764	dump_var_infos (FILE *file)
1765	{
1766	fprintf (stream: file, format: "\n\nDefinition and live-in blocks:\n\n");
1767	if (var_infos)
1768	var_infos->traverse <FILE *, debug_var_infos_r> (argument: file);
1769	}
1770
1771
1772	/* Dump the VAR_INFOS hash table on stderr. */
1773
1774	DEBUG_FUNCTION void
1775	debug_var_infos (void)
1776	{
1777	dump_var_infos (stderr);
1778	}
1779
1780
1781	/* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
1782
1783	static inline void
1784	register_new_update_single (tree new_name, tree old_name)
1785	{
1786	common_info *info = get_common_info (var: old_name);
1787	tree currdef = info->current_def;
1788
1789	/* Push the current reaching definition into BLOCK_DEFS_STACK.
1790	This stack is later used by the dominator tree callbacks to
1791	restore the reaching definitions for all the variables
1792	defined in the block after a recursive visit to all its
1793	immediately dominated blocks. */
1794	block_defs_stack.reserve (nelems: 2);
1795	block_defs_stack.quick_push (obj: currdef);
1796	block_defs_stack.quick_push (obj: old_name);
1797
1798	/* Set the current reaching definition for OLD_NAME to be
1799	NEW_NAME. */
1800	info->current_def = new_name;
1801	}
1802
1803
1804	/* Register NEW_NAME to be the new reaching definition for all the
1805	names in OLD_NAMES. Used by the incremental SSA update routines to
1806	replace old SSA names with new ones. */
1807
1808	static inline void
1809	register_new_update_set (tree new_name, bitmap old_names)
1810	{
1811	bitmap_iterator bi;
1812	unsigned i;
1813
1814	EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
1815	register_new_update_single (new_name, ssa_name (i));
1816	}
1817
1818
1819
1820	/* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1821	it is a symbol marked for renaming, replace it with USE_P's current
1822	reaching definition. */
1823
1824	static inline void
1825	maybe_replace_use (use_operand_p use_p)
1826	{
1827	tree rdef = NULL_TREE;
1828	tree use = USE_FROM_PTR (use_p);
1829	tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1830
1831	if (marked_for_renaming (sym))
1832	rdef = get_reaching_def (var: sym);
1833	else if (is_old_name (name: use))
1834	rdef = get_reaching_def (var: use);
1835
1836	if (rdef && rdef != use)
1837	SET_USE (use_p, rdef);
1838	}
1839
1840
1841	/* Same as maybe_replace_use, but without introducing default stmts,
1842	returning false to indicate a need to do so. */
1843
1844	static inline bool
1845	maybe_replace_use_in_debug_stmt (use_operand_p use_p)
1846	{
1847	tree rdef = NULL_TREE;
1848	tree use = USE_FROM_PTR (use_p);
1849	tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1850
1851	if (marked_for_renaming (sym))
1852	rdef = get_var_info (decl: sym)->info.current_def;
1853	else if (is_old_name (name: use))
1854	{
1855	rdef = get_ssa_name_ann (name: use)->info.current_def;
1856	/* We can't assume that, if there's no current definition, the
1857	default one should be used. It could be the case that we've
1858	rearranged blocks so that the earlier definition no longer
1859	dominates the use. */
1860	if (!rdef && SSA_NAME_IS_DEFAULT_DEF (use))
1861	rdef = use;
1862	}
1863	else
1864	rdef = use;
1865
1866	if (rdef && rdef != use)
1867	SET_USE (use_p, rdef);
1868
1869	return rdef != NULL_TREE;
1870	}
1871
1872
1873	/* If DEF has x_5 = ASAN_POISON () as its current def, add
1874	ASAN_POISON_USE (x_5) stmt before GSI to denote the stmt writes into
1875	a poisoned (out of scope) variable. */
1876
1877	static void
1878	maybe_add_asan_poison_write (tree def, gimple_stmt_iterator *gsi)
1879	{
1880	tree cdef = get_current_def (var: def);
1881	if (cdef != NULL
1882	&& TREE_CODE (cdef) == SSA_NAME
1883	&& gimple_call_internal_p (SSA_NAME_DEF_STMT (cdef), fn: IFN_ASAN_POISON))
1884	{
1885	gcall *call
1886	= gimple_build_call_internal (IFN_ASAN_POISON_USE, 1, cdef);
1887	gimple_set_location (g: call, location: gimple_location (g: gsi_stmt (i: *gsi)));
1888	gsi_insert_before (gsi, call, GSI_SAME_STMT);
1889	}
1890	}
1891
1892
1893	/* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1894	or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1895	register it as the current definition for the names replaced by
1896	DEF_P. Returns whether the statement should be removed. */
1897
1898	static inline bool
1899	maybe_register_def (def_operand_p def_p, gimple *stmt,
1900	gimple_stmt_iterator gsi)
1901	{
1902	tree def = DEF_FROM_PTR (def_p);
1903	tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1904	bool to_delete = false;
1905
1906	/* If DEF is a naked symbol that needs renaming, create a new
1907	name for it. */
1908	if (marked_for_renaming (sym))
1909	{
1910	if (DECL_P (def))
1911	{
1912	if (gimple_clobber_p (s: stmt) && is_gimple_reg (sym))
1913	{
1914	tree defvar;
1915	if (VAR_P (sym))
1916	defvar = sym;
1917	else
1918	defvar = create_tmp_reg (TREE_TYPE (sym));
1919	/* Replace clobber stmts with a default def. This new use of a
1920	default definition may make it look like SSA_NAMEs have
1921	conflicting lifetimes, so we need special code to let them
1922	coalesce properly. */
1923	to_delete = true;
1924	def = get_or_create_ssa_default_def (cfun, defvar);
1925	}
1926	else
1927	{
1928	if (asan_sanitize_use_after_scope ())
1929	maybe_add_asan_poison_write (def, gsi: &gsi);
1930	def = make_ssa_name (var: def, stmt);
1931	}
1932	SET_DEF (def_p, def);
1933
1934	tree tracked_var = target_for_debug_bind (sym);
1935	if (tracked_var)
1936	{
1937	/* If stmt ends the bb, insert the debug stmt on the non-EH
1938	edge(s) from the stmt. */
1939	if (gsi_one_before_end_p (i: gsi) && stmt_ends_bb_p (stmt))
1940	{
1941	basic_block bb = gsi_bb (i: gsi);
1942	edge_iterator ei;
1943	edge e, ef = NULL;
1944	FOR_EACH_EDGE (e, ei, bb->succs)
1945	if (!(e->flags & EDGE_EH))
1946	{
1947	/* asm goto can have multiple non-EH edges from the
1948	stmt. Insert on all of them where it is
1949	possible. */
1950	gcc_checking_assert (!ef || (gimple_code (stmt)
1951	== GIMPLE_ASM));
1952	ef = e;
1953	/* If there are other predecessors to ef->dest, then
1954	there must be PHI nodes for the modified
1955	variable, and therefore there will be debug bind
1956	stmts after the PHI nodes. The debug bind notes
1957	we'd insert would force the creation of a new
1958	block (diverging codegen) and be redundant with
1959	the post-PHI bind stmts, so don't add them.
1960
1961	As for the exit edge, there wouldn't be redundant
1962	bind stmts, but there wouldn't be a PC to bind
1963	them to either, so avoid diverging the CFG. */
1964	if (e
1965	&& single_pred_p (bb: e->dest)
1966	&& gimple_seq_empty_p (s: phi_nodes (bb: e->dest))
1967	&& e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1968	{
1969	/* If there were PHI nodes in the node, we'd
1970	have to make sure the value we're binding
1971	doesn't need rewriting. But there shouldn't
1972	be PHI nodes in a single-predecessor block,
1973	so we just add the note. */
1974	gimple *note
1975	= gimple_build_debug_bind (tracked_var, def,
1976	stmt);
1977	gsi_insert_on_edge_immediate (ef, note);
1978	}
1979	}
1980	}
1981	else
1982	{
1983	gimple *note
1984	= gimple_build_debug_bind (tracked_var, def, stmt);
1985	gsi_insert_after (&gsi, note, GSI_SAME_STMT);
1986	}
1987	}
1988	}
1989
1990	register_new_update_single (new_name: def, old_name: sym);
1991	}
1992	else
1993	{
1994	/* If DEF is a new name, register it as a new definition
1995	for all the names replaced by DEF. */
1996	if (is_new_name (name: def))
1997	register_new_update_set (new_name: def, old_names: names_replaced_by (new_tree: def));
1998
1999	/* If DEF is an old name, register DEF as a new
2000	definition for itself. */
2001	if (is_old_name (name: def))
2002	register_new_update_single (new_name: def, old_name: def);
2003	}
2004
2005	return to_delete;
2006	}
2007
2008
2009	/* Update every variable used in the statement pointed-to by SI. The
2010	statement is assumed to be in SSA form already. Names in
2011	OLD_SSA_NAMES used by SI will be updated to their current reaching
2012	definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
2013	will be registered as a new definition for their corresponding name
2014	in OLD_SSA_NAMES. Returns whether STMT should be removed. */
2015
2016	static bool
2017	rewrite_update_stmt (gimple *stmt, gimple_stmt_iterator gsi)
2018	{
2019	use_operand_p use_p;
2020	def_operand_p def_p;
2021	ssa_op_iter iter;
2022
2023	/* Only update marked statements. */
2024	if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
2025	return false;
2026
2027	if (dump_file && (dump_flags & TDF_DETAILS))
2028	{
2029	fprintf (stream: dump_file, format: "Updating SSA information for statement ");
2030	print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2031	}
2032
2033	/* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
2034	symbol is marked for renaming. */
2035	if (rewrite_uses_p (stmt))
2036	{
2037	if (is_gimple_debug (gs: stmt))
2038	{
2039	bool failed = false;
2040
2041	FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
2042	if (!maybe_replace_use_in_debug_stmt (use_p))
2043	{
2044	failed = true;
2045	break;
2046	}
2047
2048	if (failed)
2049	{
2050	/* DOM sometimes threads jumps in such a way that a
2051	debug stmt ends up referencing a SSA variable that no
2052	longer dominates the debug stmt, but such that all
2053	incoming definitions refer to the same definition in
2054	an earlier dominator. We could try to recover that
2055	definition somehow, but this will have to do for now.
2056
2057	Introducing a default definition, which is what
2058	maybe_replace_use() would do in such cases, may
2059	modify code generation, for the otherwise-unused
2060	default definition would never go away, modifying SSA
2061	version numbers all over. */
2062	gimple_debug_bind_reset_value (dbg: stmt);
2063	update_stmt (s: stmt);
2064	}
2065	}
2066	else
2067	{
2068	FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
2069	maybe_replace_use (use_p);
2070	}
2071	}
2072
2073	/* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
2074	Also register definitions for names whose underlying symbol is
2075	marked for renaming. */
2076	bool to_delete = false;
2077	if (register_defs_p (stmt))
2078	FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
2079	to_delete |= maybe_register_def (def_p, stmt, gsi);
2080
2081	return to_delete;
2082	}
2083
2084
2085	/* Visit all the successor blocks of BB looking for PHI nodes. For
2086	every PHI node found, check if any of its arguments is in
2087	OLD_SSA_NAMES. If so, and if the argument has a current reaching
2088	definition, replace it. */
2089
2090	static void
2091	rewrite_update_phi_arguments (basic_block bb)
2092	{
2093	edge e;
2094	edge_iterator ei;
2095
2096	FOR_EACH_EDGE (e, ei, bb->succs)
2097	{
2098	vec<gphi *> phis;
2099
2100	if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
2101	continue;
2102
2103	phis = phis_to_rewrite[e->dest->index];
2104	for (gphi *phi : phis)
2105	{
2106	tree arg, lhs_sym, reaching_def = NULL;
2107	use_operand_p arg_p;
2108
2109	gcc_checking_assert (rewrite_uses_p (phi));
2110
2111	arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
2112	arg = USE_FROM_PTR (arg_p);
2113
2114	if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
2115	continue;
2116
2117	lhs_sym = SSA_NAME_VAR (gimple_phi_result (phi));
2118
2119	if (arg == NULL_TREE)
2120	{
2121	/* When updating a PHI node for a recently introduced
2122	symbol we may find NULL arguments. That's why we
2123	take the symbol from the LHS of the PHI node. */
2124	reaching_def = get_reaching_def (var: lhs_sym);
2125	}
2126	else
2127	{
2128	tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
2129
2130	if (marked_for_renaming (sym))
2131	reaching_def = get_reaching_def (var: sym);
2132	else if (is_old_name (name: arg))
2133	reaching_def = get_reaching_def (var: arg);
2134	}
2135
2136	/* Update the argument if there is a reaching def different
2137	from arg. */
2138	if (reaching_def && reaching_def != arg)
2139	{
2140	location_t locus;
2141	int arg_i = PHI_ARG_INDEX_FROM_USE (arg_p);
2142
2143	SET_USE (arg_p, reaching_def);
2144
2145	/* Virtual operands do not need a location. */
2146	if (virtual_operand_p (op: reaching_def))
2147	locus = UNKNOWN_LOCATION;
2148	/* If SSA update didn't insert this PHI the argument
2149	might have a location already, keep that. */
2150	else if (gimple_phi_arg_has_location (phi, i: arg_i))
2151	locus = gimple_phi_arg_location (phi, i: arg_i);
2152	else
2153	{
2154	gimple *stmt = SSA_NAME_DEF_STMT (reaching_def);
2155	gphi *other_phi = dyn_cast <gphi *> (p: stmt);
2156
2157	/* Single element PHI nodes behave like copies, so get the
2158	location from the phi argument. */
2159	if (other_phi
2160	&& gimple_phi_num_args (gs: other_phi) == 1)
2161	locus = gimple_phi_arg_location (phi: other_phi, i: 0);
2162	else
2163	locus = gimple_location (g: stmt);
2164	}
2165
2166	gimple_phi_arg_set_location (phi, i: arg_i, loc: locus);
2167	}
2168
2169	if (e->flags & EDGE_ABNORMAL)
2170	SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
2171	}
2172	}
2173	}
2174
2175	class rewrite_update_dom_walker : public dom_walker
2176	{
2177	public:
2178	rewrite_update_dom_walker (cdi_direction direction, int in_region_flag = -1)
2179	: dom_walker (direction, ALL_BLOCKS, (int *)(uintptr_t)-1),
2180	m_in_region_flag (in_region_flag) {}
2181
2182	edge before_dom_children (basic_block) final override;
2183	void after_dom_children (basic_block) final override;
2184
2185	int m_in_region_flag;
2186	};
2187
2188	/* Initialization of block data structures for the incremental SSA
2189	update pass. Create a block local stack of reaching definitions
2190	for new SSA names produced in this block (BLOCK_DEFS). Register
2191	new definitions for every PHI node in the block. */
2192
2193	edge
2194	rewrite_update_dom_walker::before_dom_children (basic_block bb)
2195	{
2196	bool is_abnormal_phi;
2197
2198	if (dump_file && (dump_flags & TDF_DETAILS))
2199	fprintf (stream: dump_file, format: "Registering new PHI nodes in block #%d\n",
2200	bb->index);
2201
2202	/* Mark the unwind point for this block. */
2203	block_defs_stack.safe_push (NULL_TREE);
2204
2205	if (m_in_region_flag != -1
2206	&& !(bb->flags & m_in_region_flag))
2207	return STOP;
2208
2209	if (!bitmap_bit_p (blocks_to_update, bb->index))
2210	return NULL;
2211
2212	/* Mark the LHS if any of the arguments flows through an abnormal
2213	edge. */
2214	is_abnormal_phi = bb_has_abnormal_pred (bb);
2215
2216	/* If any of the PHI nodes is a replacement for a name in
2217	OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
2218	register it as a new definition for its corresponding name. Also
2219	register definitions for names whose underlying symbols are
2220	marked for renaming. */
2221	for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (i: gsi);
2222	gsi_next (i: &gsi))
2223	{
2224	tree lhs, lhs_sym;
2225	gphi *phi = gsi.phi ();
2226
2227	if (!register_defs_p (stmt: phi))
2228	continue;
2229
2230	lhs = gimple_phi_result (gs: phi);
2231	lhs_sym = SSA_NAME_VAR (lhs);
2232
2233	if (marked_for_renaming (sym: lhs_sym))
2234	register_new_update_single (new_name: lhs, old_name: lhs_sym);
2235	else
2236	{
2237
2238	/* If LHS is a new name, register a new definition for all
2239	the names replaced by LHS. */
2240	if (is_new_name (name: lhs))
2241	register_new_update_set (new_name: lhs, old_names: names_replaced_by (new_tree: lhs));
2242
2243	/* If LHS is an OLD name, register it as a new definition
2244	for itself. */
2245	if (is_old_name (name: lhs))
2246	register_new_update_single (new_name: lhs, old_name: lhs);
2247	}
2248
2249	if (is_abnormal_phi)
2250	SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
2251	}
2252
2253	/* Step 2. Rewrite every variable used in each statement in the block. */
2254	for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); )
2255	if (rewrite_update_stmt (stmt: gsi_stmt (i: gsi), gsi))
2256	gsi_remove (&gsi, true);
2257	else
2258	gsi_next (i: &gsi);
2259
2260	/* Step 3. Update PHI nodes. */
2261	rewrite_update_phi_arguments (bb);
2262
2263	return NULL;
2264	}
2265
2266	/* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
2267	the current reaching definition of every name re-written in BB to
2268	the original reaching definition before visiting BB. This
2269	unwinding must be done in the opposite order to what is done in
2270	register_new_update_set. */
2271
2272	void
2273	rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
2274	{
2275	while (block_defs_stack.length () > 0)
2276	{
2277	tree var = block_defs_stack.pop ();
2278	tree saved_def;
2279
2280	/* NULL indicates the unwind stop point for this block (see
2281	rewrite_update_enter_block). */
2282	if (var == NULL)
2283	return;
2284
2285	saved_def = block_defs_stack.pop ();
2286	get_common_info (var)->current_def = saved_def;
2287	}
2288	}
2289
2290
2291	/* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
2292	form.
2293
2294	ENTRY indicates the block where to start. Every block dominated by
2295	ENTRY will be rewritten.
2296
2297	WHAT indicates what actions will be taken by the renamer (see enum
2298	rewrite_mode).
2299
2300	REGION is a SEME region of interesting blocks for the dominator walker
2301	to process. If this set is invalid, then all the nodes dominated
2302	by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
2303	are not present in BLOCKS are ignored. */
2304
2305	static void
2306	rewrite_blocks (basic_block entry, enum rewrite_mode what)
2307	{
2308	block_defs_stack.create (nelems: 10);
2309
2310	/* Recursively walk the dominator tree rewriting each statement in
2311	each basic block. */
2312	if (what == REWRITE_ALL)
2313	rewrite_dom_walker (CDI_DOMINATORS).walk (entry);
2314	else if (what == REWRITE_UPDATE)
2315	rewrite_update_dom_walker (CDI_DOMINATORS).walk (entry);
2316	else if (what == REWRITE_UPDATE_REGION)
2317	{
2318	/* First mark all blocks in the SEME region dominated by
2319	entry and exited by blocks not backwards reachable from
2320	blocks_to_update. Optimize for dense blocks_to_update
2321	so instead of seeding the worklist with a copy of
2322	blocks_to_update treat those blocks explicit. */
2323	auto_bb_flag in_region (cfun);
2324	auto_vec<basic_block, 64> extra_rgn;
2325	bitmap_iterator bi;
2326	unsigned int idx;
2327	EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, idx, bi)
2328	{
2329	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, idx);
2330	bb->flags |= in_region;
2331	}
2332	auto_bitmap worklist;
2333	EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, idx, bi)
2334	{
2335	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, idx);
2336	if (bb != entry)
2337	{
2338	edge_iterator ei;
2339	edge e;
2340	FOR_EACH_EDGE (e, ei, bb->preds)
2341	{
2342	if ((e->src->flags & in_region)
2343	|| dominated_by_p (CDI_DOMINATORS, e->src, bb))
2344	continue;
2345	bitmap_set_bit (worklist, e->src->index);
2346	}
2347	}
2348	}
2349	while (!bitmap_empty_p (map: worklist))
2350	{
2351	int idx = bitmap_clear_first_set_bit (worklist);
2352	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, idx);
2353	bb->flags |= in_region;
2354	extra_rgn.safe_push (obj: bb);
2355	if (bb != entry)
2356	{
2357	edge_iterator ei;
2358	edge e;
2359	FOR_EACH_EDGE (e, ei, bb->preds)
2360	{
2361	if ((e->src->flags & in_region)
2362	|| dominated_by_p (CDI_DOMINATORS, e->src, bb))
2363	continue;
2364	bitmap_set_bit (worklist, e->src->index);
2365	}
2366	}
2367	}
2368	rewrite_update_dom_walker (CDI_DOMINATORS, in_region).walk (entry);
2369	EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, idx, bi)
2370	{
2371	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, idx);
2372	bb->flags &= ~in_region;
2373	}
2374	for (auto bb : extra_rgn)
2375	bb->flags &= ~in_region;
2376	}
2377	else
2378	gcc_unreachable ();
2379
2380	/* Debugging dumps. */
2381	if (dump_file && (dump_flags & TDF_STATS))
2382	{
2383	dump_dfa_stats (dump_file);
2384	if (var_infos)
2385	dump_tree_ssa_stats (file: dump_file);
2386	}
2387
2388	block_defs_stack.release ();
2389	}
2390
2391	class mark_def_dom_walker : public dom_walker
2392	{
2393	public:
2394	mark_def_dom_walker (cdi_direction direction);
2395	~mark_def_dom_walker ();
2396
2397	edge before_dom_children (basic_block) final override;
2398
2399	private:
2400	/* Notice that this bitmap is indexed using variable UIDs, so it must be
2401	large enough to accommodate all the variables referenced in the
2402	function, not just the ones we are renaming. */
2403	bitmap m_kills;
2404	};
2405
2406	mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction)
2407	: dom_walker (direction, ALL_BLOCKS, NULL), m_kills (BITMAP_ALLOC (NULL))
2408	{
2409	}
2410
2411	mark_def_dom_walker::~mark_def_dom_walker ()
2412	{
2413	BITMAP_FREE (m_kills);
2414	}
2415
2416	/* Block processing routine for mark_def_sites. Clear the KILLS bitmap
2417	at the start of each block, and call mark_def_sites for each statement. */
2418
2419	edge
2420	mark_def_dom_walker::before_dom_children (basic_block bb)
2421	{
2422	gimple_stmt_iterator gsi;
2423
2424	bitmap_clear (m_kills);
2425	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
2426	mark_def_sites (bb, stmt: gsi_stmt (i: gsi), kills: m_kills);
2427	return NULL;
2428	}
2429
2430	/* Initialize internal data needed during renaming. */
2431
2432	static void
2433	init_ssa_renamer (void)
2434	{
2435	cfun->gimple_df->in_ssa_p = false;
2436
2437	/* Allocate memory for the DEF_BLOCKS hash table. */
2438	gcc_assert (!var_infos);
2439	var_infos = new hash_table<var_info_hasher>
2440	(vec_safe_length (cfun->local_decls));
2441
2442	bitmap_obstack_initialize (&update_ssa_obstack);
2443	}
2444
2445
2446	/* Deallocate internal data structures used by the renamer. */
2447
2448	static void
2449	fini_ssa_renamer (void)
2450	{
2451	delete var_infos;
2452	var_infos = NULL;
2453
2454	bitmap_obstack_release (&update_ssa_obstack);
2455
2456	cfun->gimple_df->ssa_renaming_needed = 0;
2457	cfun->gimple_df->rename_vops = 0;
2458	cfun->gimple_df->in_ssa_p = true;
2459	}
2460
2461	/* Main entry point into the SSA builder. The renaming process
2462	proceeds in four main phases:
2463
2464	1- Compute dominance frontier and immediate dominators, needed to
2465	insert PHI nodes and rename the function in dominator tree
2466	order.
2467
2468	2- Find and mark all the blocks that define variables.
2469
2470	3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2471
2472	4- Rename all the blocks (rewrite_blocks) and statements in the program.
2473
2474	Steps 3 and 4 are done using the dominator tree walker
2475	(walk_dominator_tree). */
2476
2477	namespace {
2478
2479	const pass_data pass_data_build_ssa =
2480	{
2481	.type: GIMPLE_PASS, /* type */
2482	.name: "ssa", /* name */
2483	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
2484	.tv_id: TV_TREE_INTO_SSA, /* tv_id */
2485	PROP_cfg, /* properties_required */
2486	PROP_ssa, /* properties_provided */
2487	.properties_destroyed: 0, /* properties_destroyed */
2488	.todo_flags_start: 0, /* todo_flags_start */
2489	TODO_remove_unused_locals, /* todo_flags_finish */
2490	};
2491
2492	class pass_build_ssa : public gimple_opt_pass
2493	{
2494	public:
2495	pass_build_ssa (gcc::context *ctxt)
2496	: gimple_opt_pass (pass_data_build_ssa, ctxt)
2497	{}
2498
2499	/* opt_pass methods: */
2500	bool gate (function *fun) final override
2501	{
2502	/* Do nothing for funcions that was produced already in SSA form. */
2503	return !(fun->curr_properties & PROP_ssa);
2504	}
2505
2506	unsigned int execute (function *) final override;
2507
2508	}; // class pass_build_ssa
2509
2510	unsigned int
2511	pass_build_ssa::execute (function *fun)
2512	{
2513	bitmap_head *dfs;
2514	basic_block bb;
2515
2516	/* Increase the set of variables we can rewrite into SSA form
2517	by clearing TREE_ADDRESSABLE and transform the IL to support this. */
2518	if (optimize)
2519	execute_update_addresses_taken ();
2520
2521	/* Initialize operand data structures. */
2522	init_ssa_operands (fn: fun);
2523
2524	/* Initialize internal data needed by the renamer. */
2525	init_ssa_renamer ();
2526
2527	/* Initialize the set of interesting blocks. The callback
2528	mark_def_sites will add to this set those blocks that the renamer
2529	should process. */
2530	interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (fun));
2531	bitmap_clear (interesting_blocks);
2532
2533	/* Initialize dominance frontier. */
2534	dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (fun));
2535	FOR_EACH_BB_FN (bb, fun)
2536	bitmap_initialize (head: &dfs[bb->index], obstack: &bitmap_default_obstack);
2537
2538	/* 1- Compute dominance frontiers. */
2539	calculate_dominance_info (CDI_DOMINATORS);
2540	compute_dominance_frontiers (dfs);
2541
2542	/* 2- Find and mark definition sites. */
2543	mark_def_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
2544
2545	/* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
2546	insert_phi_nodes (dfs);
2547
2548	/* 4- Rename all the blocks. */
2549	rewrite_blocks (ENTRY_BLOCK_PTR_FOR_FN (fun), what: REWRITE_ALL);
2550
2551	/* Free allocated memory. */
2552	FOR_EACH_BB_FN (bb, fun)
2553	bitmap_clear (&dfs[bb->index]);
2554	free (ptr: dfs);
2555
2556	sbitmap_free (map: interesting_blocks);
2557	interesting_blocks = NULL;
2558
2559	fini_ssa_renamer ();
2560
2561	/* Try to get rid of all gimplifier generated temporaries by making
2562	its SSA names anonymous. This way we can garbage collect them
2563	all after removing unused locals which we do in our TODO. */
2564	unsigned i;
2565	tree name;
2566
2567	FOR_EACH_SSA_NAME (i, name, cfun)
2568	{
2569	if (SSA_NAME_IS_DEFAULT_DEF (name))
2570	continue;
2571	tree decl = SSA_NAME_VAR (name);
2572	if (decl
2573	&& VAR_P (decl)
2574	&& !VAR_DECL_IS_VIRTUAL_OPERAND (decl)
2575	&& DECL_IGNORED_P (decl))
2576	SET_SSA_NAME_VAR_OR_IDENTIFIER (name, DECL_NAME (decl));
2577	}
2578
2579	/* Initialize SSA_NAME_POINTS_TO_READONLY_MEMORY. */
2580	tree fnspec_tree
2581	= lookup_attribute (attr_name: "fn spec",
2582	TYPE_ATTRIBUTES (TREE_TYPE (fun->decl)));
2583	if (fnspec_tree)
2584	{
2585	attr_fnspec fnspec (TREE_VALUE (TREE_VALUE (fnspec_tree)));
2586	unsigned i = 0;
2587	for (tree arg = DECL_ARGUMENTS (cfun->decl);
2588	arg; arg = DECL_CHAIN (arg), ++i)
2589	{
2590	if (!fnspec.arg_specified_p (i))
2591	break;
2592	if (fnspec.arg_readonly_p (i))
2593	{
2594	tree name = ssa_default_def (fun, arg);
2595	if (name)
2596	SSA_NAME_POINTS_TO_READONLY_MEMORY (name) = 1;
2597	}
2598	}
2599	}
2600
2601	return 0;
2602	}
2603
2604	} // anon namespace
2605
2606	gimple_opt_pass *
2607	make_pass_build_ssa (gcc::context *ctxt)
2608	{
2609	return new pass_build_ssa (ctxt);
2610	}
2611
2612
2613	/* Mark the definition of VAR at STMT and BB as interesting for the
2614	renamer. BLOCKS is the set of blocks that need updating. */
2615
2616	static void
2617	mark_def_interesting (tree var, gimple *stmt, basic_block bb,
2618	bool insert_phi_p)
2619	{
2620	gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
2621	set_register_defs (stmt, register_defs_p: true);
2622
2623	if (insert_phi_p)
2624	{
2625	bool is_phi_p = gimple_code (g: stmt) == GIMPLE_PHI;
2626
2627	set_def_block (var, bb, phi_p: is_phi_p);
2628
2629	/* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2630	site for both itself and all the old names replaced by it. */
2631	if (TREE_CODE (var) == SSA_NAME && is_new_name (name: var))
2632	{
2633	bitmap_iterator bi;
2634	unsigned i;
2635	bitmap set = names_replaced_by (new_tree: var);
2636	if (set)
2637	EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2638	set_def_block (ssa_name (i), bb, phi_p: is_phi_p);
2639	}
2640	}
2641	}
2642
2643
2644	/* Mark the use of VAR at STMT and BB as interesting for the
2645	renamer. INSERT_PHI_P is true if we are going to insert new PHI
2646	nodes. */
2647
2648	static inline void
2649	mark_use_interesting (tree var, gimple *stmt, basic_block bb,
2650	bool insert_phi_p)
2651	{
2652	basic_block def_bb = gimple_bb (g: stmt);
2653
2654	mark_block_for_update (bb: def_bb);
2655	mark_block_for_update (bb);
2656
2657	if (gimple_code (g: stmt) == GIMPLE_PHI)
2658	mark_phi_for_rewrite (bb: def_bb, phi: as_a <gphi *> (p: stmt));
2659	else
2660	{
2661	set_rewrite_uses (stmt, rewrite_p: true);
2662
2663	if (is_gimple_debug (gs: stmt))
2664	return;
2665	}
2666
2667	/* If VAR has not been defined in BB, then it is live-on-entry
2668	to BB. Note that we cannot just use the block holding VAR's
2669	definition because if VAR is one of the names in OLD_SSA_NAMES,
2670	it will have several definitions (itself and all the names that
2671	replace it). */
2672	if (insert_phi_p)
2673	{
2674	def_blocks *db_p = get_def_blocks_for (info: get_common_info (var));
2675	if (!bitmap_bit_p (db_p->def_blocks, bb->index))
2676	set_livein_block (var, bb);
2677	}
2678	}
2679
2680	/* Processing statements in BB that reference symbols in SSA operands.
2681	This is very similar to mark_def_sites, but the scan handles
2682	statements whose operands may already be SSA names.
2683
2684	If INSERT_PHI_P is true, mark those uses as live in the
2685	corresponding block. This is later used by the PHI placement
2686	algorithm to make PHI pruning decisions.
2687
2688	FIXME. Most of this would be unnecessary if we could associate a
2689	symbol to all the SSA names that reference it. But that
2690	sounds like it would be expensive to maintain. Still, it
2691	would be interesting to see if it makes better sense to do
2692	that. */
2693
2694	static void
2695	prepare_block_for_update_1 (basic_block bb, bool insert_phi_p)
2696	{
2697	edge e;
2698	edge_iterator ei;
2699
2700	mark_block_for_update (bb);
2701
2702	/* Process PHI nodes marking interesting those that define or use
2703	the symbols that we are interested in. */
2704	for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (i: si);
2705	gsi_next (i: &si))
2706	{
2707	gphi *phi = si.phi ();
2708	tree lhs_sym, lhs = gimple_phi_result (gs: phi);
2709
2710	if (TREE_CODE (lhs) == SSA_NAME
2711	&& (! virtual_operand_p (op: lhs)
2712	|| ! cfun->gimple_df->rename_vops))
2713	continue;
2714
2715	lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
2716	mark_for_renaming (sym: lhs_sym);
2717	mark_def_interesting (var: lhs_sym, stmt: phi, bb, insert_phi_p);
2718
2719	/* Mark the uses in phi nodes as interesting. It would be more correct
2720	to process the arguments of the phi nodes of the successor edges of
2721	BB at the end of prepare_block_for_update, however, that turns out
2722	to be significantly more expensive. Doing it here is conservatively
2723	correct -- it may only cause us to believe a value to be live in a
2724	block that also contains its definition, and thus insert a few more
2725	phi nodes for it. */
2726	FOR_EACH_EDGE (e, ei, bb->preds)
2727	mark_use_interesting (var: lhs_sym, stmt: phi, bb: e->src, insert_phi_p);
2728	}
2729
2730	/* Process the statements. */
2731	for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (i: si);
2732	gsi_next (i: &si))
2733	{
2734	gimple *stmt;
2735	ssa_op_iter i;
2736	use_operand_p use_p;
2737	def_operand_p def_p;
2738
2739	stmt = gsi_stmt (i: si);
2740
2741	if (cfun->gimple_df->rename_vops
2742	&& gimple_vuse (g: stmt))
2743	{
2744	tree use = gimple_vuse (g: stmt);
2745	tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
2746	mark_for_renaming (sym);
2747	mark_use_interesting (var: sym, stmt, bb, insert_phi_p);
2748	}
2749
2750	FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE)
2751	{
2752	tree use = USE_FROM_PTR (use_p);
2753	if (!DECL_P (use))
2754	continue;
2755	mark_for_renaming (sym: use);
2756	mark_use_interesting (var: use, stmt, bb, insert_phi_p);
2757	}
2758
2759	if (cfun->gimple_df->rename_vops
2760	&& gimple_vdef (g: stmt))
2761	{
2762	tree def = gimple_vdef (g: stmt);
2763	tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
2764	mark_for_renaming (sym);
2765	mark_def_interesting (var: sym, stmt, bb, insert_phi_p);
2766	}
2767
2768	FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF)
2769	{
2770	tree def = DEF_FROM_PTR (def_p);
2771	if (!DECL_P (def))
2772	continue;
2773	mark_for_renaming (sym: def);
2774	mark_def_interesting (var: def, stmt, bb, insert_phi_p);
2775	}
2776	}
2777
2778	}
2779
2780	/* Do a dominator walk starting at BB processing statements that
2781	reference symbols in SSA operands. This is very similar to
2782	mark_def_sites, but the scan handles statements whose operands may
2783	already be SSA names.
2784
2785	If INSERT_PHI_P is true, mark those uses as live in the
2786	corresponding block. This is later used by the PHI placement
2787	algorithm to make PHI pruning decisions.
2788
2789	FIXME. Most of this would be unnecessary if we could associate a
2790	symbol to all the SSA names that reference it. But that
2791	sounds like it would be expensive to maintain. Still, it
2792	would be interesting to see if it makes better sense to do
2793	that. */
2794	static void
2795	prepare_block_for_update (basic_block bb, bool insert_phi_p)
2796	{
2797	size_t sp = 0;
2798	basic_block *worklist;
2799
2800	/* Allocate the worklist. */
2801	worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
2802	/* Add the BB to the worklist. */
2803	worklist[sp++] = bb;
2804
2805	while (sp)
2806	{
2807	basic_block bb;
2808	basic_block son;
2809
2810	/* Pick a block from the worklist. */
2811	bb = worklist[--sp];
2812
2813	prepare_block_for_update_1 (bb, insert_phi_p);
2814
2815	/* Now add all the blocks dominated by BB to the worklist. */
2816	for (son = first_dom_son (CDI_DOMINATORS, bb);
2817	son;
2818	son = next_dom_son (CDI_DOMINATORS, son))
2819	worklist[sp++] = son;
2820	}
2821	free (ptr: worklist);
2822	}
2823
2824	/* Helper for prepare_names_to_update. Mark all the use sites for
2825	NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2826	prepare_names_to_update. */
2827
2828	static void
2829	prepare_use_sites_for (tree name, bool insert_phi_p)
2830	{
2831	use_operand_p use_p;
2832	imm_use_iterator iter;
2833
2834	/* If we rename virtual operands do not update them. */
2835	if (virtual_operand_p (op: name)
2836	&& cfun->gimple_df->rename_vops)
2837	return;
2838
2839	FOR_EACH_IMM_USE_FAST (use_p, iter, name)
2840	{
2841	gimple *stmt = USE_STMT (use_p);
2842	basic_block bb = gimple_bb (g: stmt);
2843
2844	if (gimple_code (g: stmt) == GIMPLE_PHI)
2845	{
2846	int ix = PHI_ARG_INDEX_FROM_USE (use_p);
2847	edge e = gimple_phi_arg_edge (phi: as_a <gphi *> (p: stmt), i: ix);
2848	mark_use_interesting (var: name, stmt, bb: e->src, insert_phi_p);
2849	}
2850	else
2851	{
2852	/* For regular statements, mark this as an interesting use
2853	for NAME. */
2854	mark_use_interesting (var: name, stmt, bb, insert_phi_p);
2855	}
2856	}
2857	}
2858
2859
2860	/* Helper for prepare_names_to_update. Mark the definition site for
2861	NAME as interesting. BLOCKS and INSERT_PHI_P are as in
2862	prepare_names_to_update. */
2863
2864	static void
2865	prepare_def_site_for (tree name, bool insert_phi_p)
2866	{
2867	gimple *stmt;
2868	basic_block bb;
2869
2870	gcc_checking_assert (names_to_release == NULL
2871	|| !bitmap_bit_p (names_to_release,
2872	SSA_NAME_VERSION (name)));
2873
2874	/* If we rename virtual operands do not update them. */
2875	if (virtual_operand_p (op: name)
2876	&& cfun->gimple_df->rename_vops)
2877	return;
2878
2879	stmt = SSA_NAME_DEF_STMT (name);
2880	bb = gimple_bb (g: stmt);
2881	if (bb)
2882	{
2883	gcc_checking_assert (bb->index < last_basic_block_for_fn (cfun));
2884	mark_block_for_update (bb);
2885	mark_def_interesting (var: name, stmt, bb, insert_phi_p);
2886	}
2887	}
2888
2889
2890	/* Mark definition and use sites of names in NEW_SSA_NAMES and
2891	OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
2892	PHI nodes for newly created names. */
2893
2894	static void
2895	prepare_names_to_update (bool insert_phi_p)
2896	{
2897	unsigned i = 0;
2898	bitmap_iterator bi;
2899	sbitmap_iterator sbi;
2900
2901	/* If a name N from NEW_SSA_NAMES is also marked to be released,
2902	remove it from NEW_SSA_NAMES so that we don't try to visit its
2903	defining basic block (which most likely doesn't exist). Notice
2904	that we cannot do the same with names in OLD_SSA_NAMES because we
2905	want to replace existing instances. */
2906	if (names_to_release)
2907	EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2908	bitmap_clear_bit (map: new_ssa_names, bitno: i);
2909
2910	/* First process names in NEW_SSA_NAMES. Otherwise, uses of old
2911	names may be considered to be live-in on blocks that contain
2912	definitions for their replacements. */
2913	EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2914	prepare_def_site_for (ssa_name (i), insert_phi_p);
2915
2916	/* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2917	OLD_SSA_NAMES, but we have to ignore its definition site. */
2918	EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
2919	{
2920	if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
2921	prepare_def_site_for (ssa_name (i), insert_phi_p);
2922	prepare_use_sites_for (ssa_name (i), insert_phi_p);
2923	}
2924	}
2925
2926
2927	/* Dump all the names replaced by NAME to FILE. */
2928
2929	void
2930	dump_names_replaced_by (FILE *file, tree name)
2931	{
2932	unsigned i;
2933	bitmap old_set;
2934	bitmap_iterator bi;
2935
2936	print_generic_expr (file, name);
2937	fprintf (stream: file, format: " -> { ");
2938
2939	old_set = names_replaced_by (new_tree: name);
2940	EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
2941	{
2942	print_generic_expr (file, ssa_name (i));
2943	fprintf (stream: file, format: " ");
2944	}
2945
2946	fprintf (stream: file, format: "}\n");
2947	}
2948
2949
2950	/* Dump all the names replaced by NAME to stderr. */
2951
2952	DEBUG_FUNCTION void
2953	debug_names_replaced_by (tree name)
2954	{
2955	dump_names_replaced_by (stderr, name);
2956	}
2957
2958
2959	/* Dump SSA update information to FILE. */
2960
2961	void
2962	dump_update_ssa (FILE *file)
2963	{
2964	unsigned i = 0;
2965	bitmap_iterator bi;
2966
2967	if (!need_ssa_update_p (cfun))
2968	return;
2969
2970	if (new_ssa_names && !bitmap_empty_p (new_ssa_names))
2971	{
2972	sbitmap_iterator sbi;
2973
2974	fprintf (stream: file, format: "\nSSA replacement table\n");
2975	fprintf (stream: file, format: "N_i -> { O_1 ... O_j } means that N_i replaces "
2976	"O_1, ..., O_j\n\n");
2977
2978	EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
2979	dump_names_replaced_by (file, ssa_name (i));
2980	}
2981
2982	if (symbols_to_rename_set && !bitmap_empty_p (map: symbols_to_rename_set))
2983	{
2984	fprintf (stream: file, format: "\nSymbols to be put in SSA form\n");
2985	dump_decl_set (file, symbols_to_rename_set);
2986	fprintf (stream: file, format: "\n");
2987	}
2988
2989	if (names_to_release && !bitmap_empty_p (map: names_to_release))
2990	{
2991	fprintf (stream: file, format: "\nSSA names to release after updating the SSA web\n\n");
2992	EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2993	{
2994	print_generic_expr (file, ssa_name (i));
2995	fprintf (stream: file, format: " ");
2996	}
2997	fprintf (stream: file, format: "\n");
2998	}
2999	}
3000
3001
3002	/* Dump SSA update information to stderr. */
3003
3004	DEBUG_FUNCTION void
3005	debug_update_ssa (void)
3006	{
3007	dump_update_ssa (stderr);
3008	}
3009
3010
3011	/* Initialize data structures used for incremental SSA updates. */
3012
3013	static void
3014	init_update_ssa (struct function *fn)
3015	{
3016	/* Reserve more space than the current number of names. The calls to
3017	add_new_name_mapping are typically done after creating new SSA
3018	names, so we'll need to reallocate these arrays. */
3019	old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
3020	bitmap_clear (old_ssa_names);
3021
3022	new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
3023	bitmap_clear (new_ssa_names);
3024
3025	bitmap_obstack_initialize (&update_ssa_obstack);
3026
3027	names_to_release = NULL;
3028	update_ssa_initialized_fn = fn;
3029	}
3030
3031
3032	/* Deallocate data structures used for incremental SSA updates. */
3033
3034	void
3035	delete_update_ssa (void)
3036	{
3037	unsigned i;
3038	bitmap_iterator bi;
3039
3040	sbitmap_free (map: old_ssa_names);
3041	old_ssa_names = NULL;
3042
3043	sbitmap_free (map: new_ssa_names);
3044	new_ssa_names = NULL;
3045
3046	BITMAP_FREE (symbols_to_rename_set);
3047	symbols_to_rename_set = NULL;
3048	symbols_to_rename.release ();
3049
3050	if (names_to_release)
3051	{
3052	EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
3053	release_ssa_name (ssa_name (i));
3054	BITMAP_FREE (names_to_release);
3055	}
3056
3057	clear_ssa_name_info ();
3058
3059	fini_ssa_renamer ();
3060
3061	if (blocks_with_phis_to_rewrite)
3062	EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
3063	phis_to_rewrite[i].release ();
3064
3065	BITMAP_FREE (blocks_with_phis_to_rewrite);
3066	BITMAP_FREE (blocks_to_update);
3067
3068	update_ssa_initialized_fn = NULL;
3069	}
3070
3071
3072	/* Create a new name for OLD_NAME in statement STMT and replace the
3073	operand pointed to by DEF_P with the newly created name. If DEF_P
3074	is NULL then STMT should be a GIMPLE assignment.
3075	Return the new name and register the replacement mapping <NEW, OLD> in
3076	update_ssa's tables. */
3077
3078	tree
3079	create_new_def_for (tree old_name, gimple *stmt, def_operand_p def)
3080	{
3081	tree new_name;
3082
3083	timevar_push (tv: TV_TREE_SSA_INCREMENTAL);
3084
3085	if (!update_ssa_initialized_fn)
3086	init_update_ssa (cfun);
3087
3088	gcc_assert (update_ssa_initialized_fn == cfun);
3089
3090	new_name = duplicate_ssa_name (var: old_name, stmt);
3091	if (def)
3092	SET_DEF (def, new_name);
3093	else
3094	gimple_assign_set_lhs (gs: stmt, lhs: new_name);
3095
3096	if (gimple_code (g: stmt) == GIMPLE_PHI)
3097	{
3098	basic_block bb = gimple_bb (g: stmt);
3099
3100	/* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
3101	SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = bb_has_abnormal_pred (bb);
3102	}
3103
3104	add_new_name_mapping (new_tree: new_name, old: old_name);
3105
3106	/* For the benefit of passes that will be updating the SSA form on
3107	their own, set the current reaching definition of OLD_NAME to be
3108	NEW_NAME. */
3109	get_ssa_name_ann (name: old_name)->info.current_def = new_name;
3110
3111	timevar_pop (tv: TV_TREE_SSA_INCREMENTAL);
3112
3113	return new_name;
3114	}
3115
3116
3117	/* Mark virtual operands of FN for renaming by update_ssa. */
3118
3119	void
3120	mark_virtual_operands_for_renaming (struct function *fn)
3121	{
3122	fn->gimple_df->ssa_renaming_needed = 1;
3123	fn->gimple_df->rename_vops = 1;
3124	}
3125
3126	/* Replace all uses of NAME by underlying variable and mark it
3127	for renaming. This assumes the defining statement of NAME is
3128	going to be removed. */
3129
3130	void
3131	mark_virtual_operand_for_renaming (tree name)
3132	{
3133	tree name_var = SSA_NAME_VAR (name);
3134	bool used = false;
3135	imm_use_iterator iter;
3136	use_operand_p use_p;
3137	gimple *stmt;
3138
3139	gcc_assert (VAR_DECL_IS_VIRTUAL_OPERAND (name_var));
3140	FOR_EACH_IMM_USE_STMT (stmt, iter, name)
3141	{
3142	FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3143	SET_USE (use_p, name_var);
3144	used = true;
3145	}
3146	if (used)
3147	mark_virtual_operands_for_renaming (cfun);
3148	}
3149
3150	/* Replace all uses of the virtual PHI result by its underlying variable
3151	and mark it for renaming. This assumes the PHI node is going to be
3152	removed. */
3153
3154	void
3155	mark_virtual_phi_result_for_renaming (gphi *phi)
3156	{
3157	if (dump_file && (dump_flags & TDF_DETAILS))
3158	{
3159	fprintf (stream: dump_file, format: "Marking result for renaming : ");
3160	print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
3161	fprintf (stream: dump_file, format: "\n");
3162	}
3163
3164	mark_virtual_operand_for_renaming (name: gimple_phi_result (gs: phi));
3165	}
3166
3167	/* Return true if there is any work to be done by update_ssa
3168	for function FN. */
3169
3170	bool
3171	need_ssa_update_p (struct function *fn)
3172	{
3173	gcc_assert (fn != NULL);
3174	return (update_ssa_initialized_fn == fn
3175	|| (fn->gimple_df && fn->gimple_df->ssa_renaming_needed));
3176	}
3177
3178	/* Return true if name N has been registered in the replacement table. */
3179
3180	bool
3181	name_registered_for_update_p (tree n ATTRIBUTE_UNUSED)
3182	{
3183	if (!update_ssa_initialized_fn)
3184	return false;
3185
3186	gcc_assert (update_ssa_initialized_fn == cfun);
3187
3188	return is_new_name (name: n) || is_old_name (name: n);
3189	}
3190
3191
3192	/* Mark NAME to be released after update_ssa has finished. */
3193
3194	void
3195	release_ssa_name_after_update_ssa (tree name)
3196	{
3197	gcc_assert (cfun && update_ssa_initialized_fn == cfun);
3198
3199	if (names_to_release == NULL)
3200	names_to_release = BITMAP_ALLOC (NULL);
3201
3202	bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
3203	}
3204
3205
3206	/* Insert new PHI nodes to replace VAR. DFS contains dominance
3207	frontier information.
3208
3209	This is slightly different than the regular PHI insertion
3210	algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
3211	real names (i.e., GIMPLE registers) are inserted:
3212
3213	- If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
3214	nodes inside the region affected by the block that defines VAR
3215	and the blocks that define all its replacements. All these
3216	definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
3217
3218	First, we compute the entry point to the region (ENTRY). This is
3219	given by the nearest common dominator to all the definition
3220	blocks. When computing the iterated dominance frontier (IDF), any
3221	block not strictly dominated by ENTRY is ignored.
3222
3223	We then call the standard PHI insertion algorithm with the pruned
3224	IDF.
3225
3226	- If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
3227	names is not pruned. PHI nodes are inserted at every IDF block. */
3228
3229	static void
3230	insert_updated_phi_nodes_for (tree var, bitmap_head *dfs,
3231	unsigned update_flags)
3232	{
3233	basic_block entry;
3234	def_blocks *db;
3235	bitmap idf, pruned_idf;
3236	bitmap_iterator bi;
3237	unsigned i;
3238
3239	if (TREE_CODE (var) == SSA_NAME)
3240	gcc_checking_assert (is_old_name (var));
3241	else
3242	gcc_checking_assert (marked_for_renaming (var));
3243
3244	/* Get all the definition sites for VAR. */
3245	db = find_def_blocks_for (var);
3246
3247	/* No need to do anything if there were no definitions to VAR. */
3248	if (db == NULL || bitmap_empty_p (map: db->def_blocks))
3249	return;
3250
3251	/* Compute the initial iterated dominance frontier. */
3252	idf = compute_idf (db->def_blocks, dfs);
3253	pruned_idf = BITMAP_ALLOC (NULL);
3254
3255	if (TREE_CODE (var) == SSA_NAME)
3256	{
3257	if (update_flags == TODO_update_ssa)
3258	{
3259	/* If doing regular SSA updates for GIMPLE registers, we are
3260	only interested in IDF blocks dominated by the nearest
3261	common dominator of all the definition blocks. */
3262	entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
3263	db->def_blocks);
3264	if (entry != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3265	EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
3266	if (BASIC_BLOCK_FOR_FN (cfun, i) != entry
3267	&& dominated_by_p (CDI_DOMINATORS,
3268	BASIC_BLOCK_FOR_FN (cfun, i), entry))
3269	bitmap_set_bit (pruned_idf, i);
3270	}
3271	else
3272	{
3273	/* Otherwise, do not prune the IDF for VAR. */
3274	gcc_checking_assert (update_flags == TODO_update_ssa_full_phi);
3275	bitmap_copy (pruned_idf, idf);
3276	}
3277	}
3278	else
3279	{
3280	/* Otherwise, VAR is a symbol that needs to be put into SSA form
3281	for the first time, so we need to compute the full IDF for
3282	it. */
3283	bitmap_copy (pruned_idf, idf);
3284	}
3285
3286	if (!bitmap_empty_p (map: pruned_idf))
3287	{
3288	/* Make sure that PRUNED_IDF blocks and all their feeding blocks
3289	are included in the region to be updated. The feeding blocks
3290	are important to guarantee that the PHI arguments are renamed
3291	properly. */
3292
3293	/* FIXME, this is not needed if we are updating symbols. We are
3294	already starting at the ENTRY block anyway. */
3295	EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
3296	{
3297	edge e;
3298	edge_iterator ei;
3299	basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
3300
3301	mark_block_for_update (bb);
3302	FOR_EACH_EDGE (e, ei, bb->preds)
3303	if (e->src->index >= 0)
3304	mark_block_for_update (bb: e->src);
3305	}
3306
3307	insert_phi_nodes_for (var, phi_insertion_points: pruned_idf, update_p: true);
3308	}
3309
3310	BITMAP_FREE (pruned_idf);
3311	BITMAP_FREE (idf);
3312	}
3313
3314	/* Sort symbols_to_rename after their DECL_UID. */
3315
3316	static int
3317	insert_updated_phi_nodes_compare_uids (const void *a, const void *b)
3318	{
3319	const_tree syma = *(const const_tree *)a;
3320	const_tree symb = *(const const_tree *)b;
3321	if (DECL_UID (syma) == DECL_UID (symb))
3322	return 0;
3323	return DECL_UID (syma) < DECL_UID (symb) ? -1 : 1;
3324	}
3325
3326	/* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
3327	existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
3328
3329	1- The names in OLD_SSA_NAMES dominated by the definitions of
3330	NEW_SSA_NAMES are all re-written to be reached by the
3331	appropriate definition from NEW_SSA_NAMES.
3332
3333	2- If needed, new PHI nodes are added to the iterated dominance
3334	frontier of the blocks where each of NEW_SSA_NAMES are defined.
3335
3336	The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
3337	calling create_new_def_for to create new defs for names that the
3338	caller wants to replace.
3339
3340	The caller cretaes the new names to be inserted and the names that need
3341	to be replaced by calling create_new_def_for for each old definition
3342	to be replaced. Note that the function assumes that the
3343	new defining statement has already been inserted in the IL.
3344
3345	For instance, given the following code:
3346
3347	1 L0:
3348	2 x_1 = PHI (0, x_5)
3349	3 if (x_1 < 10)
3350	4 if (x_1 > 7)
3351	5 y_2 = 0
3352	6 else
3353	7 y_3 = x_1 + x_7
3354	8 endif
3355	9 x_5 = x_1 + 1
3356	10 goto L0;
3357	11 endif
3358
3359	Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
3360
3361	1 L0:
3362	2 x_1 = PHI (0, x_5)
3363	3 if (x_1 < 10)
3364	4 x_10 = ...
3365	5 if (x_1 > 7)
3366	6 y_2 = 0
3367	7 else
3368	8 x_11 = ...
3369	9 y_3 = x_1 + x_7
3370	10 endif
3371	11 x_5 = x_1 + 1
3372	12 goto L0;
3373	13 endif
3374
3375	We want to replace all the uses of x_1 with the new definitions of
3376	x_10 and x_11. Note that the only uses that should be replaced are
3377	those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
3378	*not* be replaced (this is why we cannot just mark symbol 'x' for
3379	renaming).
3380
3381	Additionally, we may need to insert a PHI node at line 11 because
3382	that is a merge point for x_10 and x_11. So the use of x_1 at line
3383	11 will be replaced with the new PHI node. The insertion of PHI
3384	nodes is optional. They are not strictly necessary to preserve the
3385	SSA form, and depending on what the caller inserted, they may not
3386	even be useful for the optimizers. UPDATE_FLAGS controls various
3387	aspects of how update_ssa operates, see the documentation for
3388	TODO_update_ssa*. */
3389
3390	void
3391	update_ssa (unsigned update_flags)
3392	{
3393	basic_block bb, start_bb;
3394	bitmap_iterator bi;
3395	unsigned i = 0;
3396	bool insert_phi_p;
3397	sbitmap_iterator sbi;
3398	tree sym;
3399
3400	/* Only one update flag should be set. */
3401	gcc_assert (update_flags == TODO_update_ssa
3402	|| update_flags == TODO_update_ssa_no_phi
3403	|| update_flags == TODO_update_ssa_full_phi
3404	|| update_flags == TODO_update_ssa_only_virtuals);
3405
3406	if (!need_ssa_update_p (cfun))
3407	return;
3408
3409	if (flag_checking)
3410	{
3411	timevar_push (tv: TV_TREE_STMT_VERIFY);
3412
3413	bool err = false;
3414
3415	FOR_EACH_BB_FN (bb, cfun)
3416	{
3417	gimple_stmt_iterator gsi;
3418	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
3419	{
3420	gimple *stmt = gsi_stmt (i: gsi);
3421
3422	ssa_op_iter i;
3423	use_operand_p use_p;
3424	FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_ALL_USES)
3425	{
3426	tree use = USE_FROM_PTR (use_p);
3427	if (TREE_CODE (use) != SSA_NAME)
3428	continue;
3429
3430	if (SSA_NAME_IN_FREE_LIST (use))
3431	{
3432	error ("statement uses released SSA name");
3433	debug_gimple_stmt (stmt);
3434	fprintf (stderr, format: "The use of ");
3435	print_generic_expr (stderr, use);
3436	fprintf (stderr,format: " should have been replaced\n");
3437	err = true;
3438	}
3439	}
3440	}
3441	}
3442
3443	if (err)
3444	internal_error ("cannot update SSA form");
3445
3446	timevar_pop (tv: TV_TREE_STMT_VERIFY);
3447	}
3448
3449	timevar_push (tv: TV_TREE_SSA_INCREMENTAL);
3450
3451	if (dump_file && (dump_flags & TDF_DETAILS))
3452	fprintf (stream: dump_file, format: "\nUpdating SSA:\n");
3453
3454	if (!update_ssa_initialized_fn)
3455	init_update_ssa (cfun);
3456	else if (update_flags == TODO_update_ssa_only_virtuals)
3457	{
3458	/* If we only need to update virtuals, remove all the mappings for
3459	real names before proceeding. The caller is responsible for
3460	having dealt with the name mappings before calling update_ssa. */
3461	bitmap_clear (old_ssa_names);
3462	bitmap_clear (new_ssa_names);
3463	}
3464
3465	gcc_assert (update_ssa_initialized_fn == cfun);
3466
3467	blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
3468	if (!phis_to_rewrite.exists ())
3469	phis_to_rewrite.create (last_basic_block_for_fn (cfun) + 1);
3470	blocks_to_update = BITMAP_ALLOC (NULL);
3471
3472	insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
3473
3474	/* Ensure that the dominance information is up-to-date and when we
3475	are going to compute dominance frontiers fast queries are possible. */
3476	if (insert_phi_p || dom_info_state (CDI_DOMINATORS) == DOM_NONE)
3477	calculate_dominance_info (CDI_DOMINATORS);
3478
3479	/* If there are names defined in the replacement table, prepare
3480	definition and use sites for all the names in NEW_SSA_NAMES and
3481	OLD_SSA_NAMES. */
3482	if (!bitmap_empty_p (new_ssa_names))
3483	{
3484	statistics_counter_event (cfun, "Incremental SSA update", 1);
3485
3486	prepare_names_to_update (insert_phi_p);
3487
3488	/* If all the names in NEW_SSA_NAMES had been marked for
3489	removal, and there are no symbols to rename, then there's
3490	nothing else to do. */
3491	if (bitmap_empty_p (new_ssa_names)
3492	&& !cfun->gimple_df->ssa_renaming_needed)
3493	goto done;
3494	}
3495
3496	/* Next, determine the block at which to start the renaming process. */
3497	if (cfun->gimple_df->ssa_renaming_needed)
3498	{
3499	statistics_counter_event (cfun, "Symbol to SSA rewrite", 1);
3500
3501	/* If we rename bare symbols initialize the mapping to
3502	auxiliar info we need to keep track of. */
3503	var_infos = new hash_table<var_info_hasher> (47);
3504
3505	/* If we have to rename some symbols from scratch, we need to
3506	start the process at the root of the CFG. FIXME, it should
3507	be possible to determine the nearest block that had a
3508	definition for each of the symbols that are marked for
3509	updating. For now this seems more work than it's worth. */
3510	start_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3511
3512	/* Traverse the CFG looking for existing definitions and uses of
3513	symbols in SSA operands. Mark interesting blocks and
3514	statements and set local live-in information for the PHI
3515	placement heuristics. */
3516	prepare_block_for_update (bb: start_bb, insert_phi_p);
3517
3518	tree name;
3519
3520	if (flag_checking)
3521	FOR_EACH_SSA_NAME (i, name, cfun)
3522	{
3523	if (virtual_operand_p (op: name))
3524	continue;
3525
3526	/* For all but virtual operands, which do not have SSA names
3527	with overlapping life ranges, ensure that symbols marked
3528	for renaming do not have existing SSA names associated with
3529	them as we do not re-write them out-of-SSA before going
3530	into SSA for the remaining symbol uses. */
3531	if (marked_for_renaming (SSA_NAME_VAR (name)))
3532	{
3533	fprintf (stderr, format: "Existing SSA name for symbol marked for "
3534	"renaming: ");
3535	print_generic_expr (stderr, name, TDF_SLIM);
3536	fprintf (stderr, format: "\n");
3537	internal_error ("SSA corruption");
3538	}
3539	}
3540	}
3541	else
3542	{
3543	/* Otherwise, the entry block to the region is the nearest
3544	common dominator for the blocks in BLOCKS. */
3545	start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3546	blocks_to_update);
3547	}
3548
3549	/* If requested, insert PHI nodes at the iterated dominance frontier
3550	of every block, creating new definitions for names in OLD_SSA_NAMES
3551	and for symbols found. */
3552	if (insert_phi_p)
3553	{
3554	bitmap_head *dfs;
3555
3556	/* If the caller requested PHI nodes to be added, compute
3557	dominance frontiers. */
3558	dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
3559	FOR_EACH_BB_FN (bb, cfun)
3560	bitmap_initialize (head: &dfs[bb->index], obstack: &bitmap_default_obstack);
3561	compute_dominance_frontiers (dfs);
3562
3563	bitmap_tree_view (blocks_to_update);
3564
3565	/* insert_update_phi_nodes_for will call add_new_name_mapping
3566	when inserting new PHI nodes, but it will not add any
3567	new members to OLD_SSA_NAMES. */
3568	iterating_old_ssa_names = true;
3569	sbitmap_iterator sbi;
3570	EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
3571	insert_updated_phi_nodes_for (ssa_name (i), dfs, update_flags);
3572	iterating_old_ssa_names = false;
3573
3574	symbols_to_rename.qsort (insert_updated_phi_nodes_compare_uids);
3575	FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3576	insert_updated_phi_nodes_for (var: sym, dfs, update_flags);
3577
3578	bitmap_list_view (blocks_to_update);
3579
3580	FOR_EACH_BB_FN (bb, cfun)
3581	bitmap_clear (&dfs[bb->index]);
3582	free (ptr: dfs);
3583
3584	/* Insertion of PHI nodes may have added blocks to the region.
3585	We need to re-compute START_BB to include the newly added
3586	blocks. */
3587	if (start_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3588	start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3589	blocks_to_update);
3590	}
3591
3592	/* Reset the current definition for name and symbol before renaming
3593	the sub-graph. */
3594	EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
3595	get_ssa_name_ann (ssa_name (i))->info.current_def = NULL_TREE;
3596
3597	FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
3598	get_var_info (decl: sym)->info.current_def = NULL_TREE;
3599
3600	/* Now start the renaming process at START_BB. When not inserting PHIs
3601	and thus we are avoiding work on all blocks, try to confine the
3602	rewriting domwalk to the affected region, otherwise it's not worth it. */
3603	rewrite_blocks (entry: start_bb,
3604	what: insert_phi_p ? REWRITE_UPDATE : REWRITE_UPDATE_REGION);
3605
3606	/* Debugging dumps. */
3607	if (dump_file)
3608	{
3609	int c;
3610	unsigned i;
3611
3612	dump_update_ssa (file: dump_file);
3613
3614	fprintf (stream: dump_file, format: "Incremental SSA update started at block: %d\n",
3615	start_bb->index);
3616
3617	c = 0;
3618	EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3619	c++;
3620	fprintf (stream: dump_file, format: "Number of blocks in CFG: %d\n",
3621	last_basic_block_for_fn (cfun));
3622	fprintf (stream: dump_file, format: "Number of blocks to update: %d (%3.0f%%)\n",
3623	c, PERCENT (c, last_basic_block_for_fn (cfun)));
3624
3625	if (dump_flags & TDF_DETAILS)
3626	{
3627	fprintf (stream: dump_file, format: "Affected blocks:");
3628	EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3629	fprintf (stream: dump_file, format: " %u", i);
3630	fprintf (stream: dump_file, format: "\n");
3631	}
3632
3633	fprintf (stream: dump_file, format: "\n\n");
3634	}
3635
3636	/* Free allocated memory. */
3637	done:
3638	delete_update_ssa ();
3639
3640	timevar_pop (tv: TV_TREE_SSA_INCREMENTAL);
3641	}
3642