tree-into-ssa.cc source code [gcc/tree-into-ssa.cc]

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

source code of gcc/tree-into-ssa.cc