1	/* Passes for transactional memory support.
2	Copyright (C) 2008-2023 Free Software Foundation, Inc.
3	Contributed by Richard Henderson <rth@redhat.com>
4	and Aldy Hernandez <aldyh@redhat.com>.
5
6	This file is part of GCC.
7
8	GCC is free software; you can redistribute it and/or modify it under
9	the terms of the GNU General Public License as published by the Free
10	Software Foundation; either version 3, or (at your option) any later
11	version.
12
13	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14	WARRANTY; without even the implied warranty of MERCHANTABILITY or
15	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16	for more details.
17
18	You should have received a copy of the GNU General Public License
19	along with GCC; see the file COPYING3. If not see
20	<http://www.gnu.org/licenses/>. */
21
22	#include "config.h"
23	#include "system.h"
24	#include "coretypes.h"
25	#include "backend.h"
26	#include "target.h"
27	#include "rtl.h"
28	#include "tree.h"
29	#include "gimple.h"
30	#include "cfghooks.h"
31	#include "tree-pass.h"
32	#include "ssa.h"
33	#include "cgraph.h"
34	#include "gimple-pretty-print.h"
35	#include "diagnostic-core.h"
36	#include "fold-const.h"
37	#include "tree-eh.h"
38	#include "calls.h"
39	#include "gimplify.h"
40	#include "gimple-iterator.h"
41	#include "gimplify-me.h"
42	#include "gimple-walk.h"
43	#include "tree-cfg.h"
44	#include "tree-into-ssa.h"
45	#include "tree-inline.h"
46	#include "demangle.h"
47	#include "output.h"
48	#include "trans-mem.h"
49	#include "langhooks.h"
50	#include "cfgloop.h"
51	#include "tree-ssa-address.h"
52	#include "stringpool.h"
53	#include "attribs.h"
54	#include "alloc-pool.h"
55	#include "symbol-summary.h"
56	#include "symtab-thunks.h"
57
58	#define A_RUNINSTRUMENTEDCODE 0x0001
59	#define A_RUNUNINSTRUMENTEDCODE 0x0002
60	#define A_SAVELIVEVARIABLES 0x0004
61	#define A_RESTORELIVEVARIABLES 0x0008
62	#define A_ABORTTRANSACTION 0x0010
63
64	#define AR_USERABORT 0x0001
65	#define AR_USERRETRY 0x0002
66	#define AR_TMCONFLICT 0x0004
67	#define AR_EXCEPTIONBLOCKABORT 0x0008
68	#define AR_OUTERABORT 0x0010
69
70	#define MODE_SERIALIRREVOCABLE 0x0000
71
72
73	/* The representation of a transaction changes several times during the
74	lowering process. In the beginning, in the front-end we have the
75	GENERIC tree TRANSACTION_EXPR. For example,
76
77	__transaction {
78	local++;
79	if (++global == 10)
80	__tm_abort;
81	}
82
83	During initial gimplification (gimplify.cc) the TRANSACTION_EXPR node is
84	trivially replaced with a GIMPLE_TRANSACTION node.
85
86	During pass_lower_tm, we examine the body of transactions looking
87	for aborts. Transactions that do not contain an abort may be
88	merged into an outer transaction. We also add a TRY-FINALLY node
89	to arrange for the transaction to be committed on any exit.
90
91	[??? Think about how this arrangement affects throw-with-commit
92	and throw-with-abort operations. In this case we want the TRY to
93	handle gotos, but not to catch any exceptions because the transaction
94	will already be closed.]
95
96	GIMPLE_TRANSACTION [label=NULL] {
97	try {
98	local = local + 1;
99	t0 = global;
100	t1 = t0 + 1;
101	global = t1;
102	if (t1 == 10)
103	__builtin___tm_abort ();
104	} finally {
105	__builtin___tm_commit ();
106	}
107	}
108
109	During pass_lower_eh, we create EH regions for the transactions,
110	intermixed with the regular EH stuff. This gives us a nice persistent
111	mapping (all the way through rtl) from transactional memory operation
112	back to the transaction, which allows us to get the abnormal edges
113	correct to model transaction aborts and restarts:
114
115	GIMPLE_TRANSACTION [label=over]
116	local = local + 1;
117	t0 = global;
118	t1 = t0 + 1;
119	global = t1;
120	if (t1 == 10)
121	__builtin___tm_abort ();
122	__builtin___tm_commit ();
123	over:
124
125	This is the end of all_lowering_passes, and so is what is present
126	during the IPA passes, and through all of the optimization passes.
127
128	During pass_ipa_tm, we examine all GIMPLE_TRANSACTION blocks in all
129	functions and mark functions for cloning.
130
131	At the end of gimple optimization, before exiting SSA form,
132	pass_tm_edges replaces statements that perform transactional
133	memory operations with the appropriate TM builtins, and swap
134	out function calls with their transactional clones. At this
135	point we introduce the abnormal transaction restart edges and
136	complete lowering of the GIMPLE_TRANSACTION node.
137
138	x = __builtin___tm_start (MAY_ABORT);
139	eh_label:
140	if (x & abort_transaction)
141	goto over;
142	local = local + 1;
143	t0 = __builtin___tm_load (global);
144	t1 = t0 + 1;
145	__builtin___tm_store (&global, t1);
146	if (t1 == 10)
147	__builtin___tm_abort ();
148	__builtin___tm_commit ();
149	over:
150	*/
151
152	static void *expand_regions (struct tm_region *,
153	void *(*callback)(struct tm_region *, void *),
154	void *, bool);
155
156
157	/* Return the attributes we want to examine for X, or NULL if it's not
158	something we examine. We look at function types, but allow pointers
159	to function types and function decls and peek through. */
160
161	static tree
162	get_attrs_for (const_tree x)
163	{
164	if (x == NULL_TREE)
165	return NULL_TREE;
166
167	switch (TREE_CODE (x))
168	{
169	case FUNCTION_DECL:
170	return TYPE_ATTRIBUTES (TREE_TYPE (x));
171
172	default:
173	if (TYPE_P (x))
174	return NULL_TREE;
175	x = TREE_TYPE (x);
176	if (TREE_CODE (x) != POINTER_TYPE)
177	return NULL_TREE;
178	/* FALLTHRU */
179
180	case POINTER_TYPE:
181	x = TREE_TYPE (x);
182	if (TREE_CODE (x) != FUNCTION_TYPE && TREE_CODE (x) != METHOD_TYPE)
183	return NULL_TREE;
184	/* FALLTHRU */
185
186	case FUNCTION_TYPE:
187	case METHOD_TYPE:
188	return TYPE_ATTRIBUTES (x);
189	}
190	}
191
192	/* Return true if X has been marked TM_PURE. */
193
194	bool
195	is_tm_pure (const_tree x)
196	{
197	unsigned flags;
198
199	switch (TREE_CODE (x))
200	{
201	case FUNCTION_DECL:
202	case FUNCTION_TYPE:
203	case METHOD_TYPE:
204	break;
205
206	default:
207	if (TYPE_P (x))
208	return false;
209	x = TREE_TYPE (x);
210	if (TREE_CODE (x) != POINTER_TYPE)
211	return false;
212	/* FALLTHRU */
213
214	case POINTER_TYPE:
215	x = TREE_TYPE (x);
216	if (TREE_CODE (x) != FUNCTION_TYPE && TREE_CODE (x) != METHOD_TYPE)
217	return false;
218	break;
219	}
220
221	flags = flags_from_decl_or_type (x);
222	return (flags & ECF_TM_PURE) != 0;
223	}
224
225	/* Return true if X has been marked TM_IRREVOCABLE. */
226
227	static bool
228	is_tm_irrevocable (tree x)
229	{
230	tree attrs = get_attrs_for (x);
231
232	if (attrs && lookup_attribute (attr_name: "transaction_unsafe", list: attrs))
233	return true;
234
235	/* A call to the irrevocable builtin is by definition,
236	irrevocable. */
237	if (TREE_CODE (x) == ADDR_EXPR)
238	x = TREE_OPERAND (x, 0);
239	if (TREE_CODE (x) == FUNCTION_DECL
240	&& fndecl_built_in_p (node: x, name1: BUILT_IN_TM_IRREVOCABLE))
241	return true;
242
243	return false;
244	}
245
246	/* Return true if X has been marked TM_SAFE. */
247
248	bool
249	is_tm_safe (const_tree x)
250	{
251	if (flag_tm)
252	{
253	tree attrs = get_attrs_for (x);
254	if (attrs)
255	{
256	if (lookup_attribute (attr_name: "transaction_safe", list: attrs))
257	return true;
258	if (lookup_attribute (attr_name: "transaction_may_cancel_outer", list: attrs))
259	return true;
260	}
261	}
262	return false;
263	}
264
265	/* Return true if CALL is const, or tm_pure. */
266
267	static bool
268	is_tm_pure_call (gimple *call)
269	{
270	return (gimple_call_flags (call) & (ECF_CONST | ECF_TM_PURE)) != 0;
271	}
272
273	/* Return true if X has been marked TM_CALLABLE. */
274
275	static bool
276	is_tm_callable (tree x)
277	{
278	tree attrs = get_attrs_for (x);
279	if (attrs)
280	{
281	if (lookup_attribute (attr_name: "transaction_callable", list: attrs))
282	return true;
283	if (lookup_attribute (attr_name: "transaction_safe", list: attrs))
284	return true;
285	if (lookup_attribute (attr_name: "transaction_may_cancel_outer", list: attrs))
286	return true;
287	}
288	return false;
289	}
290
291	/* Return true if X has been marked TRANSACTION_MAY_CANCEL_OUTER. */
292
293	bool
294	is_tm_may_cancel_outer (tree x)
295	{
296	tree attrs = get_attrs_for (x);
297	if (attrs)
298	return lookup_attribute (attr_name: "transaction_may_cancel_outer", list: attrs) != NULL;
299	return false;
300	}
301
302	/* Return true for built in functions that "end" a transaction. */
303
304	bool
305	is_tm_ending_fndecl (tree fndecl)
306	{
307	if (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
308	switch (DECL_FUNCTION_CODE (decl: fndecl))
309	{
310	case BUILT_IN_TM_COMMIT:
311	case BUILT_IN_TM_COMMIT_EH:
312	case BUILT_IN_TM_ABORT:
313	case BUILT_IN_TM_IRREVOCABLE:
314	return true;
315	default:
316	break;
317	}
318
319	return false;
320	}
321
322	/* Return true if STMT is a built in function call that "ends" a
323	transaction. */
324
325	bool
326	is_tm_ending (gimple *stmt)
327	{
328	tree fndecl;
329
330	if (gimple_code (g: stmt) != GIMPLE_CALL)
331	return false;
332
333	fndecl = gimple_call_fndecl (gs: stmt);
334	return (fndecl != NULL_TREE
335	&& is_tm_ending_fndecl (fndecl));
336	}
337
338	/* Return true if STMT is a TM load. */
339
340	static bool
341	is_tm_load (gimple *stmt)
342	{
343	tree fndecl;
344
345	if (gimple_code (g: stmt) != GIMPLE_CALL)
346	return false;
347
348	fndecl = gimple_call_fndecl (gs: stmt);
349	return (fndecl
350	&& fndecl_built_in_p (node: fndecl, klass: BUILT_IN_NORMAL)
351	&& BUILTIN_TM_LOAD_P (DECL_FUNCTION_CODE (fndecl)));
352	}
353
354	/* Same as above, but for simple TM loads, that is, not the
355	after-write, after-read, etc optimized variants. */
356
357	static bool
358	is_tm_simple_load (gimple *stmt)
359	{
360	tree fndecl;
361
362	if (gimple_code (g: stmt) != GIMPLE_CALL)
363	return false;
364
365	fndecl = gimple_call_fndecl (gs: stmt);
366	if (fndecl && fndecl_built_in_p (node: fndecl, klass: BUILT_IN_NORMAL))
367	{
368	enum built_in_function fcode = DECL_FUNCTION_CODE (decl: fndecl);
369	return (fcode == BUILT_IN_TM_LOAD_1
370	|| fcode == BUILT_IN_TM_LOAD_2
371	|| fcode == BUILT_IN_TM_LOAD_4
372	|| fcode == BUILT_IN_TM_LOAD_8
373	|| fcode == BUILT_IN_TM_LOAD_FLOAT
374	|| fcode == BUILT_IN_TM_LOAD_DOUBLE
375	|| fcode == BUILT_IN_TM_LOAD_LDOUBLE
376	|| fcode == BUILT_IN_TM_LOAD_M64
377	|| fcode == BUILT_IN_TM_LOAD_M128
378	|| fcode == BUILT_IN_TM_LOAD_M256);
379	}
380	return false;
381	}
382
383	/* Return true if STMT is a TM store. */
384
385	static bool
386	is_tm_store (gimple *stmt)
387	{
388	tree fndecl;
389
390	if (gimple_code (g: stmt) != GIMPLE_CALL)
391	return false;
392
393	fndecl = gimple_call_fndecl (gs: stmt);
394	return (fndecl
395	&& fndecl_built_in_p (node: fndecl, klass: BUILT_IN_NORMAL)
396	&& BUILTIN_TM_STORE_P (DECL_FUNCTION_CODE (fndecl)));
397	}
398
399	/* Same as above, but for simple TM stores, that is, not the
400	after-write, after-read, etc optimized variants. */
401
402	static bool
403	is_tm_simple_store (gimple *stmt)
404	{
405	tree fndecl;
406
407	if (gimple_code (g: stmt) != GIMPLE_CALL)
408	return false;
409
410	fndecl = gimple_call_fndecl (gs: stmt);
411	if (fndecl
412	&& fndecl_built_in_p (node: fndecl, klass: BUILT_IN_NORMAL))
413	{
414	enum built_in_function fcode = DECL_FUNCTION_CODE (decl: fndecl);
415	return (fcode == BUILT_IN_TM_STORE_1
416	|| fcode == BUILT_IN_TM_STORE_2
417	|| fcode == BUILT_IN_TM_STORE_4
418	|| fcode == BUILT_IN_TM_STORE_8
419	|| fcode == BUILT_IN_TM_STORE_FLOAT
420	|| fcode == BUILT_IN_TM_STORE_DOUBLE
421	|| fcode == BUILT_IN_TM_STORE_LDOUBLE
422	|| fcode == BUILT_IN_TM_STORE_M64
423	|| fcode == BUILT_IN_TM_STORE_M128
424	|| fcode == BUILT_IN_TM_STORE_M256);
425	}
426	return false;
427	}
428
429	/* Return true if FNDECL is BUILT_IN_TM_ABORT. */
430
431	static bool
432	is_tm_abort (tree fndecl)
433	{
434	return (fndecl && fndecl_built_in_p (node: fndecl, name1: BUILT_IN_TM_ABORT));
435	}
436
437	/* Build a GENERIC tree for a user abort. This is called by front ends
438	while transforming the __tm_abort statement. */
439
440	tree
441	build_tm_abort_call (location_t loc, bool is_outer)
442	{
443	return build_call_expr_loc (loc, builtin_decl_explicit (fncode: BUILT_IN_TM_ABORT), 1,
444	build_int_cst (integer_type_node,
445	AR_USERABORT
446	| (is_outer ? AR_OUTERABORT : 0)));
447	}
448
449	/* Map for arbitrary function replacement under TM, as created
450	by the tm_wrap attribute. */
451
452	struct tm_wrapper_hasher : ggc_cache_ptr_hash<tree_map>
453	{
454	static inline hashval_t hash (tree_map *m) { return m->hash; }
455	static inline bool
456	equal (tree_map *a, tree_map *b)
457	{
458	return a->base.from == b->base.from;
459	}
460
461	static int
462	keep_cache_entry (tree_map *&m)
463	{
464	return ggc_marked_p (m->base.from);
465	}
466	};
467
468	static GTY((cache)) hash_table<tm_wrapper_hasher> *tm_wrap_map;
469
470	void
471	record_tm_replacement (tree from, tree to)
472	{
473	struct tree_map **slot, *h;
474
475	/* Do not inline wrapper functions that will get replaced in the TM
476	pass.
477
478	Suppose you have foo() that will get replaced into tmfoo(). Make
479	sure the inliner doesn't try to outsmart us and inline foo()
480	before we get a chance to do the TM replacement. */
481	DECL_UNINLINABLE (from) = 1;
482
483	if (tm_wrap_map == NULL)
484	tm_wrap_map = hash_table<tm_wrapper_hasher>::create_ggc (n: 32);
485
486	h = ggc_alloc<tree_map> ();
487	h->hash = htab_hash_pointer (from);
488	h->base.from = from;
489	h->to = to;
490
491	slot = tm_wrap_map->find_slot_with_hash (comparable: h, hash: h->hash, insert: INSERT);
492	*slot = h;
493	}
494
495	/* Return a TM-aware replacement function for DECL. */
496
497	static tree
498	find_tm_replacement_function (tree fndecl)
499	{
500	if (tm_wrap_map)
501	{
502	struct tree_map *h, in;
503
504	in.base.from = fndecl;
505	in.hash = htab_hash_pointer (fndecl);
506	h = tm_wrap_map->find_with_hash (comparable: &in, hash: in.hash);
507	if (h)
508	return h->to;
509	}
510
511	/* ??? We may well want TM versions of most of the common <string.h>
512	functions. For now, we've already these two defined. */
513	/* Adjust expand_call_tm() attributes as necessary for the cases
514	handled here: */
515	if (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
516	switch (DECL_FUNCTION_CODE (decl: fndecl))
517	{
518	case BUILT_IN_MEMCPY:
519	return builtin_decl_explicit (fncode: BUILT_IN_TM_MEMCPY);
520	case BUILT_IN_MEMMOVE:
521	return builtin_decl_explicit (fncode: BUILT_IN_TM_MEMMOVE);
522	case BUILT_IN_MEMSET:
523	return builtin_decl_explicit (fncode: BUILT_IN_TM_MEMSET);
524	default:
525	return NULL;
526	}
527
528	return NULL;
529	}
530
531	/* When appropriate, record TM replacement for memory allocation functions.
532
533	FROM is the FNDECL to wrap. */
534	void
535	tm_malloc_replacement (tree from)
536	{
537	const char *str;
538	tree to;
539
540	if (TREE_CODE (from) != FUNCTION_DECL)
541	return;
542
543	/* If we have a previous replacement, the user must be explicitly
544	wrapping malloc/calloc/free. They better know what they're
545	doing... */
546	if (find_tm_replacement_function (fndecl: from))
547	return;
548
549	str = IDENTIFIER_POINTER (DECL_NAME (from));
550
551	if (!strcmp (s1: str, s2: "malloc"))
552	to = builtin_decl_explicit (fncode: BUILT_IN_TM_MALLOC);
553	else if (!strcmp (s1: str, s2: "calloc"))
554	to = builtin_decl_explicit (fncode: BUILT_IN_TM_CALLOC);
555	else if (!strcmp (s1: str, s2: "free"))
556	to = builtin_decl_explicit (fncode: BUILT_IN_TM_FREE);
557	else
558	return;
559
560	TREE_NOTHROW (to) = 0;
561
562	record_tm_replacement (from, to);
563	}
564
565	/* Diagnostics for tm_safe functions/regions. Called by the front end
566	once we've lowered the function to high-gimple. */
567
568	/* Subroutine of diagnose_tm_safe_errors, called through walk_gimple_seq.
569	Process exactly one statement. WI->INFO is set to non-null when in
570	the context of a tm_safe function, and null for a __transaction block. */
571
572	#define DIAG_TM_OUTER 1
573	#define DIAG_TM_SAFE 2
574	#define DIAG_TM_RELAXED 4
575
576	struct diagnose_tm
577	{
578	unsigned int summary_flags : 8;
579	unsigned int block_flags : 8;
580	unsigned int func_flags : 8;
581	unsigned int saw_volatile : 1;
582	gimple *stmt;
583	};
584
585	/* Return true if T is a volatile lvalue of some kind. */
586
587	static bool
588	volatile_lvalue_p (tree t)
589	{
590	return ((SSA_VAR_P (t) || REFERENCE_CLASS_P (t))
591	&& TREE_THIS_VOLATILE (TREE_TYPE (t)));
592	}
593
594	/* Tree callback function for diagnose_tm pass. */
595
596	static tree
597	diagnose_tm_1_op (tree *tp, int *walk_subtrees, void *data)
598	{
599	struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
600	struct diagnose_tm *d = (struct diagnose_tm *) wi->info;
601
602	if (TYPE_P (*tp))
603	*walk_subtrees = false;
604	else if (volatile_lvalue_p (t: *tp)
605	&& !d->saw_volatile)
606	{
607	d->saw_volatile = 1;
608	if (d->block_flags & DIAG_TM_SAFE)
609	error_at (gimple_location (g: d->stmt),
610	"invalid use of volatile lvalue inside transaction");
611	else if (d->func_flags & DIAG_TM_SAFE)
612	error_at (gimple_location (g: d->stmt),
613	"invalid use of volatile lvalue inside %<transaction_safe%> "
614	"function");
615	}
616
617	return NULL_TREE;
618	}
619
620	static inline bool
621	is_tm_safe_or_pure (const_tree x)
622	{
623	return is_tm_safe (x) || is_tm_pure (x);
624	}
625
626	static tree
627	diagnose_tm_1 (gimple_stmt_iterator *gsi, bool *handled_ops_p,
628	struct walk_stmt_info *wi)
629	{
630	gimple *stmt = gsi_stmt (i: *gsi);
631	struct diagnose_tm *d = (struct diagnose_tm *) wi->info;
632
633	/* Save stmt for use in leaf analysis. */
634	d->stmt = stmt;
635
636	switch (gimple_code (g: stmt))
637	{
638	case GIMPLE_CALL:
639	{
640	if (gimple_call_internal_p (gs: stmt))
641	break;
642
643	tree fn = gimple_call_fn (gs: stmt);
644
645	if ((d->summary_flags & DIAG_TM_OUTER) == 0
646	&& is_tm_may_cancel_outer (x: fn))
647	error_at (gimple_location (g: stmt),
648	"%<transaction_may_cancel_outer%> function call not within"
649	" outer transaction or %<transaction_may_cancel_outer%>");
650
651	if (d->summary_flags & DIAG_TM_SAFE)
652	{
653	bool is_safe, direct_call_p;
654	tree replacement;
655
656	if (TREE_CODE (fn) == ADDR_EXPR
657	&& TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL)
658	{
659	direct_call_p = true;
660	replacement = TREE_OPERAND (fn, 0);
661	replacement = find_tm_replacement_function (fndecl: replacement);
662	if (replacement)
663	fn = replacement;
664	}
665	else
666	{
667	direct_call_p = false;
668	replacement = NULL_TREE;
669	}
670
671	if (is_tm_safe_or_pure (x: fn))
672	is_safe = true;
673	else if (is_tm_callable (x: fn) || is_tm_irrevocable (x: fn))
674	{
675	/* A function explicitly marked transaction_callable as
676	opposed to transaction_safe is being defined to be
677	unsafe as part of its ABI, regardless of its contents. */
678	is_safe = false;
679	}
680	else if (direct_call_p)
681	{
682	if (IS_TYPE_OR_DECL_P (fn)
683	&& flags_from_decl_or_type (fn) & ECF_TM_BUILTIN)
684	is_safe = true;
685	else if (replacement)
686	{
687	/* ??? At present we've been considering replacements
688	merely transaction_callable, and therefore might
689	enter irrevocable. The tm_wrap attribute has not
690	yet made it into the new language spec. */
691	is_safe = false;
692	}
693	else
694	{
695	/* ??? Diagnostics for unmarked direct calls moved into
696	the IPA pass. Section 3.2 of the spec details how
697	functions not marked should be considered "implicitly
698	safe" based on having examined the function body. */
699	is_safe = true;
700	}
701	}
702	else
703	{
704	/* An unmarked indirect call. Consider it unsafe even
705	though optimization may yet figure out how to inline. */
706	is_safe = false;
707	}
708
709	if (!is_safe)
710	{
711	if (TREE_CODE (fn) == ADDR_EXPR)
712	fn = TREE_OPERAND (fn, 0);
713	if (d->block_flags & DIAG_TM_SAFE)
714	{
715	if (direct_call_p)
716	error_at (gimple_location (g: stmt),
717	"unsafe function call %qD within "
718	"atomic transaction", fn);
719	else
720	{
721	if ((!DECL_P (fn) || DECL_NAME (fn))
722	&& TREE_CODE (fn) != SSA_NAME)
723	error_at (gimple_location (g: stmt),
724	"unsafe function call %qE within "
725	"atomic transaction", fn);
726	else
727	error_at (gimple_location (g: stmt),
728	"unsafe indirect function call within "
729	"atomic transaction");
730	}
731	}
732	else
733	{
734	if (direct_call_p)
735	error_at (gimple_location (g: stmt),
736	"unsafe function call %qD within "
737	"%<transaction_safe%> function", fn);
738	else
739	{
740	if ((!DECL_P (fn) || DECL_NAME (fn))
741	&& TREE_CODE (fn) != SSA_NAME)
742	error_at (gimple_location (g: stmt),
743	"unsafe function call %qE within "
744	"%<transaction_safe%> function", fn);
745	else
746	error_at (gimple_location (g: stmt),
747	"unsafe indirect function call within "
748	"%<transaction_safe%> function");
749	}
750	}
751	}
752	}
753	}
754	break;
755
756	case GIMPLE_ASM:
757	/* ??? We ought to come up with a way to add attributes to
758	asm statements, and then add "transaction_safe" to it.
759	Either that or get the language spec to resurrect __tm_waiver. */
760	if (d->block_flags & DIAG_TM_SAFE)
761	error_at (gimple_location (g: stmt),
762	"%<asm%> not allowed in atomic transaction");
763	else if (d->func_flags & DIAG_TM_SAFE)
764	error_at (gimple_location (g: stmt),
765	"%<asm%> not allowed in %<transaction_safe%> function");
766	break;
767
768	case GIMPLE_TRANSACTION:
769	{
770	gtransaction *trans_stmt = as_a <gtransaction *> (p: stmt);
771	unsigned char inner_flags = DIAG_TM_SAFE;
772
773	if (gimple_transaction_subcode (transaction_stmt: trans_stmt) & GTMA_IS_RELAXED)
774	{
775	if (d->block_flags & DIAG_TM_SAFE)
776	error_at (gimple_location (g: stmt),
777	"relaxed transaction in atomic transaction");
778	else if (d->func_flags & DIAG_TM_SAFE)
779	error_at (gimple_location (g: stmt),
780	"relaxed transaction in %<transaction_safe%> function");
781	inner_flags = DIAG_TM_RELAXED;
782	}
783	else if (gimple_transaction_subcode (transaction_stmt: trans_stmt) & GTMA_IS_OUTER)
784	{
785	if (d->block_flags)
786	error_at (gimple_location (g: stmt),
787	"outer transaction in transaction");
788	else if (d->func_flags & DIAG_TM_OUTER)
789	error_at (gimple_location (g: stmt),
790	"outer transaction in "
791	"%<transaction_may_cancel_outer%> function");
792	else if (d->func_flags & DIAG_TM_SAFE)
793	error_at (gimple_location (g: stmt),
794	"outer transaction in %<transaction_safe%> function");
795	inner_flags |= DIAG_TM_OUTER;
796	}
797
798	*handled_ops_p = true;
799	if (gimple_transaction_body (transaction_stmt: trans_stmt))
800	{
801	struct walk_stmt_info wi_inner;
802	struct diagnose_tm d_inner;
803
804	memset (s: &d_inner, c: 0, n: sizeof (d_inner));
805	d_inner.func_flags = d->func_flags;
806	d_inner.block_flags = d->block_flags | inner_flags;
807	d_inner.summary_flags = d_inner.func_flags | d_inner.block_flags;
808
809	memset (s: &wi_inner, c: 0, n: sizeof (wi_inner));
810	wi_inner.info = &d_inner;
811
812	walk_gimple_seq (gimple_transaction_body (transaction_stmt: trans_stmt),
813	diagnose_tm_1, diagnose_tm_1_op, &wi_inner);
814	}
815	}
816	break;
817
818	default:
819	break;
820	}
821
822	return NULL_TREE;
823	}
824
825	static unsigned int
826	diagnose_tm_blocks (void)
827	{
828	struct walk_stmt_info wi;
829	struct diagnose_tm d;
830
831	memset (s: &d, c: 0, n: sizeof (d));
832	if (is_tm_may_cancel_outer (x: current_function_decl))
833	d.func_flags = DIAG_TM_OUTER | DIAG_TM_SAFE;
834	else if (is_tm_safe (x: current_function_decl))
835	d.func_flags = DIAG_TM_SAFE;
836	d.summary_flags = d.func_flags;
837
838	memset (s: &wi, c: 0, n: sizeof (wi));
839	wi.info = &d;
840
841	walk_gimple_seq (gimple_body (current_function_decl),
842	diagnose_tm_1, diagnose_tm_1_op, &wi);
843
844	return 0;
845	}
846
847	namespace {
848
849	const pass_data pass_data_diagnose_tm_blocks =
850	{
851	.type: GIMPLE_PASS, /* type */
852	.name: "*diagnose_tm_blocks", /* name */
853	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
854	.tv_id: TV_TRANS_MEM, /* tv_id */
855	PROP_gimple_any, /* properties_required */
856	.properties_provided: 0, /* properties_provided */
857	.properties_destroyed: 0, /* properties_destroyed */
858	.todo_flags_start: 0, /* todo_flags_start */
859	.todo_flags_finish: 0, /* todo_flags_finish */
860	};
861
862	class pass_diagnose_tm_blocks : public gimple_opt_pass
863	{
864	public:
865	pass_diagnose_tm_blocks (gcc::context *ctxt)
866	: gimple_opt_pass (pass_data_diagnose_tm_blocks, ctxt)
867	{}
868
869	/* opt_pass methods: */
870	bool gate (function *) final override { return flag_tm; }
871	unsigned int execute (function *) final override
872	{
873	return diagnose_tm_blocks ();
874	}
875
876	}; // class pass_diagnose_tm_blocks
877
878	} // anon namespace
879
880	gimple_opt_pass *
881	make_pass_diagnose_tm_blocks (gcc::context *ctxt)
882	{
883	return new pass_diagnose_tm_blocks (ctxt);
884	}
885
886	/* Instead of instrumenting thread private memory, we save the
887	addresses in a log which we later use to save/restore the addresses
888	upon transaction start/restart.
889
890	The log is keyed by address, where each element contains individual
891	statements among different code paths that perform the store.
892
893	This log is later used to generate either plain save/restore of the
894	addresses upon transaction start/restart, or calls to the ITM_L*
895	logging functions.
896
897	So for something like:
898
899	struct large { int x[1000]; };
900	struct large lala = { 0 };
901	__transaction {
902	lala.x[i] = 123;
903	...
904	}
905
906	We can either save/restore:
907
908	lala = { 0 };
909	trxn = _ITM_startTransaction ();
910	if (trxn & a_saveLiveVariables)
911	tmp_lala1 = lala.x[i];
912	else if (a & a_restoreLiveVariables)
913	lala.x[i] = tmp_lala1;
914
915	or use the logging functions:
916
917	lala = { 0 };
918	trxn = _ITM_startTransaction ();
919	_ITM_LU4 (&lala.x[i]);
920
921	Obviously, if we use _ITM_L* to log, we prefer to call _ITM_L* as
922	far up the dominator tree to shadow all of the writes to a given
923	location (thus reducing the total number of logging calls), but not
924	so high as to be called on a path that does not perform a
925	write. */
926
927	/* One individual log entry. We may have multiple statements for the
928	same location if neither dominate each other (on different
929	execution paths). */
930	struct tm_log_entry
931	{
932	/* Address to save. */
933	tree addr;
934	/* Entry block for the transaction this address occurs in. */
935	basic_block entry_block;
936	/* Dominating statements the store occurs in. */
937	vec<gimple *> stmts;
938	/* Initially, while we are building the log, we place a nonzero
939	value here to mean that this address *will* be saved with a
940	save/restore sequence. Later, when generating the save sequence
941	we place the SSA temp generated here. */
942	tree save_var;
943	};
944
945
946	/* Log entry hashtable helpers. */
947
948	struct log_entry_hasher : pointer_hash <tm_log_entry>
949	{
950	static inline hashval_t hash (const tm_log_entry *);
951	static inline bool equal (const tm_log_entry *, const tm_log_entry *);
952	static inline void remove (tm_log_entry *);
953	};
954
955	/* Htab support. Return hash value for a `tm_log_entry'. */
956	inline hashval_t
957	log_entry_hasher::hash (const tm_log_entry *log)
958	{
959	return iterative_hash_expr (tree: log->addr, seed: 0);
960	}
961
962	/* Htab support. Return true if two log entries are the same. */
963	inline bool
964	log_entry_hasher::equal (const tm_log_entry *log1, const tm_log_entry *log2)
965	{
966	/* FIXME:
967
968	rth: I suggest that we get rid of the component refs etc.
969	I.e. resolve the reference to base + offset.
970
971	We may need to actually finish a merge with mainline for this,
972	since we'd like to be presented with Richi's MEM_REF_EXPRs more
973	often than not. But in the meantime your tm_log_entry could save
974	the results of get_inner_reference.
975
976	See: g++.dg/tm/pr46653.C
977	*/
978
979	/* Special case plain equality because operand_equal_p() below will
980	return FALSE if the addresses are equal but they have
981	side-effects (e.g. a volatile address). */
982	if (log1->addr == log2->addr)
983	return true;
984
985	return operand_equal_p (log1->addr, log2->addr, flags: 0);
986	}
987
988	/* Htab support. Free one tm_log_entry. */
989	inline void
990	log_entry_hasher::remove (tm_log_entry *lp)
991	{
992	lp->stmts.release ();
993	free (ptr: lp);
994	}
995
996
997	/* The actual log. */
998	static hash_table<log_entry_hasher> *tm_log;
999
1000	/* Addresses to log with a save/restore sequence. These should be in
1001	dominator order. */
1002	static vec<tree> tm_log_save_addresses;
1003
1004	enum thread_memory_type
1005	{
1006	mem_non_local = 0,
1007	mem_thread_local,
1008	mem_transaction_local,
1009	mem_max
1010	};
1011
1012	struct tm_new_mem_map
1013	{
1014	/* SSA_NAME being dereferenced. */
1015	tree val;
1016	enum thread_memory_type local_new_memory;
1017	};
1018
1019	/* Hashtable helpers. */
1020
1021	struct tm_mem_map_hasher : free_ptr_hash <tm_new_mem_map>
1022	{
1023	static inline hashval_t hash (const tm_new_mem_map *);
1024	static inline bool equal (const tm_new_mem_map *, const tm_new_mem_map *);
1025	};
1026
1027	inline hashval_t
1028	tm_mem_map_hasher::hash (const tm_new_mem_map *v)
1029	{
1030	return (intptr_t)v->val >> 4;
1031	}
1032
1033	inline bool
1034	tm_mem_map_hasher::equal (const tm_new_mem_map *v, const tm_new_mem_map *c)
1035	{
1036	return v->val == c->val;
1037	}
1038
1039	/* Map for an SSA_NAME originally pointing to a non aliased new piece
1040	of memory (malloc, alloc, etc). */
1041	static hash_table<tm_mem_map_hasher> *tm_new_mem_hash;
1042
1043	/* Initialize logging data structures. */
1044	static void
1045	tm_log_init (void)
1046	{
1047	tm_log = new hash_table<log_entry_hasher> (10);
1048	tm_new_mem_hash = new hash_table<tm_mem_map_hasher> (5);
1049	tm_log_save_addresses.create (nelems: 5);
1050	}
1051
1052	/* Free logging data structures. */
1053	static void
1054	tm_log_delete (void)
1055	{
1056	delete tm_log;
1057	tm_log = NULL;
1058	delete tm_new_mem_hash;
1059	tm_new_mem_hash = NULL;
1060	tm_log_save_addresses.release ();
1061	}
1062
1063	/* Return true if MEM is a transaction invariant memory for the TM
1064	region starting at REGION_ENTRY_BLOCK. */
1065	static bool
1066	transaction_invariant_address_p (const_tree mem, basic_block region_entry_block)
1067	{
1068	if ((INDIRECT_REF_P (mem) || TREE_CODE (mem) == MEM_REF)
1069	&& TREE_CODE (TREE_OPERAND (mem, 0)) == SSA_NAME)
1070	{
1071	basic_block def_bb;
1072
1073	def_bb = gimple_bb (SSA_NAME_DEF_STMT (TREE_OPERAND (mem, 0)));
1074	return def_bb != region_entry_block
1075	&& dominated_by_p (CDI_DOMINATORS, region_entry_block, def_bb);
1076	}
1077
1078	mem = strip_invariant_refs (mem);
1079	return mem && (CONSTANT_CLASS_P (mem) || decl_address_invariant_p (mem));
1080	}
1081
1082	/* Given an address ADDR in STMT, find it in the memory log or add it,
1083	making sure to keep only the addresses highest in the dominator
1084	tree.
1085
1086	ENTRY_BLOCK is the entry_block for the transaction.
1087
1088	If we find the address in the log, make sure it's either the same
1089	address, or an equivalent one that dominates ADDR.
1090
1091	If we find the address, but neither ADDR dominates the found
1092	address, nor the found one dominates ADDR, we're on different
1093	execution paths. Add it.
1094
1095	If known, ENTRY_BLOCK is the entry block for the region, otherwise
1096	NULL. */
1097	static void
1098	tm_log_add (basic_block entry_block, tree addr, gimple *stmt)
1099	{
1100	tm_log_entry **slot;
1101	struct tm_log_entry l, *lp;
1102
1103	l.addr = addr;
1104	slot = tm_log->find_slot (value: &l, insert: INSERT);
1105	if (!*slot)
1106	{
1107	tree type = TREE_TYPE (addr);
1108
1109	lp = XNEW (struct tm_log_entry);
1110	lp->addr = addr;
1111	*slot = lp;
1112
1113	/* Small invariant addresses can be handled as save/restores. */
1114	if (entry_block
1115	&& transaction_invariant_address_p (mem: lp->addr, region_entry_block: entry_block)
1116	&& TYPE_SIZE_UNIT (type) != NULL
1117	&& tree_fits_uhwi_p (TYPE_SIZE_UNIT (type))
1118	&& ((HOST_WIDE_INT) tree_to_uhwi (TYPE_SIZE_UNIT (type))
1119	< param_tm_max_aggregate_size)
1120	/* We must be able to copy this type normally. I.e., no
1121	special constructors and the like. */
1122	&& !TREE_ADDRESSABLE (type))
1123	{
1124	lp->save_var = create_tmp_reg (TREE_TYPE (lp->addr), "tm_save");
1125	lp->stmts.create (nelems: 0);
1126	lp->entry_block = entry_block;
1127	/* Save addresses separately in dominator order so we don't
1128	get confused by overlapping addresses in the save/restore
1129	sequence. */
1130	tm_log_save_addresses.safe_push (obj: lp->addr);
1131	}
1132	else
1133	{
1134	/* Use the logging functions. */
1135	lp->stmts.create (nelems: 5);
1136	lp->stmts.quick_push (obj: stmt);
1137	lp->save_var = NULL;
1138	}
1139	}
1140	else
1141	{
1142	size_t i;
1143	gimple *oldstmt;
1144
1145	lp = *slot;
1146
1147	/* If we're generating a save/restore sequence, we don't care
1148	about statements. */
1149	if (lp->save_var)
1150	return;
1151
1152	for (i = 0; lp->stmts.iterate (ix: i, ptr: &oldstmt); ++i)
1153	{
1154	if (stmt == oldstmt)
1155	return;
1156	/* We already have a store to the same address, higher up the
1157	dominator tree. Nothing to do. */
1158	if (dominated_by_p (CDI_DOMINATORS,
1159	gimple_bb (g: stmt), gimple_bb (g: oldstmt)))
1160	return;
1161	/* We should be processing blocks in dominator tree order. */
1162	gcc_assert (!dominated_by_p (CDI_DOMINATORS,
1163	gimple_bb (oldstmt), gimple_bb (stmt)));
1164	}
1165	/* Store is on a different code path. */
1166	lp->stmts.safe_push (obj: stmt);
1167	}
1168	}
1169
1170	/* Gimplify the address of a TARGET_MEM_REF. Return the SSA_NAME
1171	result, insert the new statements before GSI. */
1172
1173	static tree
1174	gimplify_addr (gimple_stmt_iterator *gsi, tree x)
1175	{
1176	if (TREE_CODE (x) == TARGET_MEM_REF)
1177	x = tree_mem_ref_addr (build_pointer_type (TREE_TYPE (x)), x);
1178	else
1179	x = build_fold_addr_expr (x);
1180	return force_gimple_operand_gsi (gsi, x, true, NULL, true, GSI_SAME_STMT);
1181	}
1182
1183	/* Instrument one address with the logging functions.
1184	ADDR is the address to save.
1185	STMT is the statement before which to place it. */
1186	static void
1187	tm_log_emit_stmt (tree addr, gimple *stmt)
1188	{
1189	tree type = TREE_TYPE (addr);
1190	gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1191	gimple *log;
1192	enum built_in_function code = BUILT_IN_TM_LOG;
1193
1194	if (type == float_type_node)
1195	code = BUILT_IN_TM_LOG_FLOAT;
1196	else if (type == double_type_node)
1197	code = BUILT_IN_TM_LOG_DOUBLE;
1198	else if (type == long_double_type_node)
1199	code = BUILT_IN_TM_LOG_LDOUBLE;
1200	else if (TYPE_SIZE (type) != NULL
1201	&& tree_fits_uhwi_p (TYPE_SIZE (type)))
1202	{
1203	unsigned HOST_WIDE_INT type_size = tree_to_uhwi (TYPE_SIZE (type));
1204
1205	if (TREE_CODE (type) == VECTOR_TYPE)
1206	{
1207	switch (type_size)
1208	{
1209	case 64:
1210	code = BUILT_IN_TM_LOG_M64;
1211	break;
1212	case 128:
1213	code = BUILT_IN_TM_LOG_M128;
1214	break;
1215	case 256:
1216	code = BUILT_IN_TM_LOG_M256;
1217	break;
1218	default:
1219	goto unhandled_vec;
1220	}
1221	if (!builtin_decl_explicit_p (fncode: code))
1222	goto unhandled_vec;
1223	}
1224	else
1225	{
1226	unhandled_vec:
1227	switch (type_size)
1228	{
1229	case 8:
1230	code = BUILT_IN_TM_LOG_1;
1231	break;
1232	case 16:
1233	code = BUILT_IN_TM_LOG_2;
1234	break;
1235	case 32:
1236	code = BUILT_IN_TM_LOG_4;
1237	break;
1238	case 64:
1239	code = BUILT_IN_TM_LOG_8;
1240	break;
1241	}
1242	}
1243	}
1244
1245	if (code != BUILT_IN_TM_LOG && !builtin_decl_explicit_p (fncode: code))
1246	code = BUILT_IN_TM_LOG;
1247	tree decl = builtin_decl_explicit (fncode: code);
1248
1249	addr = gimplify_addr (gsi: &gsi, x: addr);
1250	if (code == BUILT_IN_TM_LOG)
1251	log = gimple_build_call (decl, 2, addr, TYPE_SIZE_UNIT (type));
1252	else
1253	log = gimple_build_call (decl, 1, addr);
1254	gsi_insert_before (&gsi, log, GSI_SAME_STMT);
1255	}
1256
1257	/* Go through the log and instrument address that must be instrumented
1258	with the logging functions. Leave the save/restore addresses for
1259	later. */
1260	static void
1261	tm_log_emit (void)
1262	{
1263	hash_table<log_entry_hasher>::iterator hi;
1264	struct tm_log_entry *lp;
1265
1266	FOR_EACH_HASH_TABLE_ELEMENT (*tm_log, lp, tm_log_entry_t, hi)
1267	{
1268	size_t i;
1269	gimple *stmt;
1270
1271	if (dump_file)
1272	{
1273	fprintf (stream: dump_file, format: "TM thread private mem logging: ");
1274	print_generic_expr (dump_file, lp->addr);
1275	fprintf (stream: dump_file, format: "\n");
1276	}
1277
1278	if (lp->save_var)
1279	{
1280	if (dump_file)
1281	fprintf (stream: dump_file, format: "DUMPING to variable\n");
1282	continue;
1283	}
1284	else
1285	{
1286	if (dump_file)
1287	fprintf (stream: dump_file, format: "DUMPING with logging functions\n");
1288	for (i = 0; lp->stmts.iterate (ix: i, ptr: &stmt); ++i)
1289	tm_log_emit_stmt (addr: lp->addr, stmt);
1290	}
1291	}
1292	}
1293
1294	/* Emit the save sequence for the corresponding addresses in the log.
1295	ENTRY_BLOCK is the entry block for the transaction.
1296	BB is the basic block to insert the code in. */
1297	static void
1298	tm_log_emit_saves (basic_block entry_block, basic_block bb)
1299	{
1300	size_t i;
1301	gimple_stmt_iterator gsi = gsi_last_bb (bb);
1302	gimple *stmt;
1303	struct tm_log_entry l, *lp;
1304
1305	for (i = 0; i < tm_log_save_addresses.length (); ++i)
1306	{
1307	l.addr = tm_log_save_addresses[i];
1308	lp = *(tm_log->find_slot (value: &l, insert: NO_INSERT));
1309	gcc_assert (lp->save_var != NULL);
1310
1311	/* We only care about variables in the current transaction. */
1312	if (lp->entry_block != entry_block)
1313	continue;
1314
1315	stmt = gimple_build_assign (lp->save_var, unshare_expr (lp->addr));
1316
1317	/* Make sure we can create an SSA_NAME for this type. For
1318	instance, aggregates aren't allowed, in which case the system
1319	will create a VOP for us and everything will just work. */
1320	if (is_gimple_reg_type (TREE_TYPE (lp->save_var)))
1321	{
1322	lp->save_var = make_ssa_name (var: lp->save_var, stmt);
1323	gimple_assign_set_lhs (gs: stmt, lhs: lp->save_var);
1324	}
1325
1326	gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1327	}
1328	}
1329
1330	/* Emit the restore sequence for the corresponding addresses in the log.
1331	ENTRY_BLOCK is the entry block for the transaction.
1332	BB is the basic block to insert the code in. */
1333	static void
1334	tm_log_emit_restores (basic_block entry_block, basic_block bb)
1335	{
1336	int i;
1337	struct tm_log_entry l, *lp;
1338	gimple_stmt_iterator gsi;
1339	gimple *stmt;
1340
1341	for (i = tm_log_save_addresses.length () - 1; i >= 0; i--)
1342	{
1343	l.addr = tm_log_save_addresses[i];
1344	lp = *(tm_log->find_slot (value: &l, insert: NO_INSERT));
1345	gcc_assert (lp->save_var != NULL);
1346
1347	/* We only care about variables in the current transaction. */
1348	if (lp->entry_block != entry_block)
1349	continue;
1350
1351	/* Restores are in LIFO order from the saves in case we have
1352	overlaps. */
1353	gsi = gsi_start_bb (bb);
1354
1355	stmt = gimple_build_assign (unshare_expr (lp->addr), lp->save_var);
1356	gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
1357	}
1358	}
1359
1360
1361	static tree lower_sequence_tm (gimple_stmt_iterator *, bool *,
1362	struct walk_stmt_info *);
1363	static tree lower_sequence_no_tm (gimple_stmt_iterator *, bool *,
1364	struct walk_stmt_info *);
1365
1366	/* Evaluate an address X being dereferenced and determine if it
1367	originally points to a non aliased new chunk of memory (malloc,
1368	alloca, etc).
1369
1370	Return MEM_THREAD_LOCAL if it points to a thread-local address.
1371	Return MEM_TRANSACTION_LOCAL if it points to a transaction-local address.
1372	Return MEM_NON_LOCAL otherwise.
1373
1374	ENTRY_BLOCK is the entry block to the transaction containing the
1375	dereference of X. */
1376	static enum thread_memory_type
1377	thread_private_new_memory (basic_block entry_block, tree x)
1378	{
1379	gimple *stmt = NULL;
1380	enum tree_code code;
1381	tm_new_mem_map **slot;
1382	tm_new_mem_map elt, *elt_p;
1383	tree val = x;
1384	enum thread_memory_type retval = mem_transaction_local;
1385
1386	if (!entry_block
1387	|| TREE_CODE (x) != SSA_NAME
1388	/* Possible uninitialized use, or a function argument. In
1389	either case, we don't care. */
1390	|| SSA_NAME_IS_DEFAULT_DEF (x))
1391	return mem_non_local;
1392
1393	/* Look in cache first. */
1394	elt.val = x;
1395	slot = tm_new_mem_hash->find_slot (value: &elt, insert: INSERT);
1396	elt_p = *slot;
1397	if (elt_p)
1398	return elt_p->local_new_memory;
1399
1400	/* Optimistically assume the memory is transaction local during
1401	processing. This catches recursion into this variable. */
1402	*slot = elt_p = XNEW (tm_new_mem_map);
1403	elt_p->val = val;
1404	elt_p->local_new_memory = mem_transaction_local;
1405
1406	/* Search DEF chain to find the original definition of this address. */
1407	do
1408	{
1409	if (ptr_deref_may_alias_global_p (x, true))
1410	{
1411	/* Address escapes. This is not thread-private. */
1412	retval = mem_non_local;
1413	goto new_memory_ret;
1414	}
1415
1416	stmt = SSA_NAME_DEF_STMT (x);
1417
1418	/* If the malloc call is outside the transaction, this is
1419	thread-local. */
1420	if (retval != mem_thread_local
1421	&& !dominated_by_p (CDI_DOMINATORS, gimple_bb (g: stmt), entry_block))
1422	retval = mem_thread_local;
1423
1424	if (is_gimple_assign (gs: stmt))
1425	{
1426	code = gimple_assign_rhs_code (gs: stmt);
1427	/* x = foo ==> foo */
1428	if (code == SSA_NAME)
1429	x = gimple_assign_rhs1 (gs: stmt);
1430	/* x = foo + n ==> foo */
1431	else if (code == POINTER_PLUS_EXPR)
1432	x = gimple_assign_rhs1 (gs: stmt);
1433	/* x = (cast*) foo ==> foo */
1434	else if (code == VIEW_CONVERT_EXPR || CONVERT_EXPR_CODE_P (code))
1435	x = gimple_assign_rhs1 (gs: stmt);
1436	/* x = c ? op1 : op2 == > op1 or op2 just like a PHI */
1437	else if (code == COND_EXPR)
1438	{
1439	tree op1 = gimple_assign_rhs2 (gs: stmt);
1440	tree op2 = gimple_assign_rhs3 (gs: stmt);
1441	enum thread_memory_type mem;
1442	retval = thread_private_new_memory (entry_block, x: op1);
1443	if (retval == mem_non_local)
1444	goto new_memory_ret;
1445	mem = thread_private_new_memory (entry_block, x: op2);
1446	retval = MIN (retval, mem);
1447	goto new_memory_ret;
1448	}
1449	else
1450	{
1451	retval = mem_non_local;
1452	goto new_memory_ret;
1453	}
1454	}
1455	else
1456	{
1457	if (gimple_code (g: stmt) == GIMPLE_PHI)
1458	{
1459	unsigned int i;
1460	enum thread_memory_type mem;
1461	tree phi_result = gimple_phi_result (gs: stmt);
1462
1463	/* If any of the ancestors are non-local, we are sure to
1464	be non-local. Otherwise we can avoid doing anything
1465	and inherit what has already been generated. */
1466	retval = mem_max;
1467	for (i = 0; i < gimple_phi_num_args (gs: stmt); ++i)
1468	{
1469	tree op = PHI_ARG_DEF (stmt, i);
1470
1471	/* Exclude self-assignment. */
1472	if (phi_result == op)
1473	continue;
1474
1475	mem = thread_private_new_memory (entry_block, x: op);
1476	if (mem == mem_non_local)
1477	{
1478	retval = mem;
1479	goto new_memory_ret;
1480	}
1481	retval = MIN (retval, mem);
1482	}
1483	goto new_memory_ret;
1484	}
1485	break;
1486	}
1487	}
1488	while (TREE_CODE (x) == SSA_NAME);
1489
1490	if (stmt && is_gimple_call (gs: stmt) && gimple_call_flags (stmt) & ECF_MALLOC)
1491	/* Thread-local or transaction-local. */
1492	;
1493	else
1494	retval = mem_non_local;
1495
1496	new_memory_ret:
1497	elt_p->local_new_memory = retval;
1498	return retval;
1499	}
1500
1501	/* Determine whether X has to be instrumented using a read
1502	or write barrier.
1503
1504	ENTRY_BLOCK is the entry block for the region where stmt resides
1505	in. NULL if unknown.
1506
1507	STMT is the statement in which X occurs in. It is used for thread
1508	private memory instrumentation. If no TPM instrumentation is
1509	desired, STMT should be null. */
1510	static bool
1511	requires_barrier (basic_block entry_block, tree x, gimple *stmt)
1512	{
1513	tree orig = x;
1514	while (handled_component_p (t: x))
1515	x = TREE_OPERAND (x, 0);
1516
1517	switch (TREE_CODE (x))
1518	{
1519	case INDIRECT_REF:
1520	case MEM_REF:
1521	{
1522	enum thread_memory_type ret;
1523
1524	ret = thread_private_new_memory (entry_block, TREE_OPERAND (x, 0));
1525	if (ret == mem_non_local)
1526	return true;
1527	if (stmt && ret == mem_thread_local)
1528	/* ?? Should we pass `orig', or the INDIRECT_REF X. ?? */
1529	tm_log_add (entry_block, addr: orig, stmt);
1530
1531	/* Transaction-locals require nothing at all. For malloc, a
1532	transaction restart frees the memory and we reallocate.
1533	For alloca, the stack pointer gets reset by the retry and
1534	we reallocate. */
1535	return false;
1536	}
1537
1538	case TARGET_MEM_REF:
1539	if (TREE_CODE (TMR_BASE (x)) != ADDR_EXPR)
1540	return true;
1541	x = TREE_OPERAND (TMR_BASE (x), 0);
1542	if (TREE_CODE (x) == PARM_DECL)
1543	return false;
1544	gcc_assert (VAR_P (x));
1545	/* FALLTHRU */
1546
1547	case PARM_DECL:
1548	case RESULT_DECL:
1549	case VAR_DECL:
1550	if (DECL_BY_REFERENCE (x))
1551	{
1552	/* ??? This value is a pointer, but aggregate_value_p has been
1553	jigged to return true which confuses needs_to_live_in_memory.
1554	This ought to be cleaned up generically.
1555
1556	FIXME: Verify this still happens after the next mainline
1557	merge. Testcase ie g++.dg/tm/pr47554.C.
1558	*/
1559	return false;
1560	}
1561
1562	if (is_global_var (t: x))
1563	return !TREE_READONLY (x);
1564	if (/* FIXME: This condition should actually go below in the
1565	tm_log_add() call, however is_call_clobbered() depends on
1566	aliasing info which is not available during
1567	gimplification. Since requires_barrier() gets called
1568	during lower_sequence_tm/gimplification, leave the call
1569	to needs_to_live_in_memory until we eliminate
1570	lower_sequence_tm altogether. */
1571	needs_to_live_in_memory (x))
1572	return true;
1573	else
1574	{
1575	/* For local memory that doesn't escape (aka thread private
1576	memory), we can either save the value at the beginning of
1577	the transaction and restore on restart, or call a tm
1578	function to dynamically save and restore on restart
1579	(ITM_L*). */
1580	if (stmt)
1581	tm_log_add (entry_block, addr: orig, stmt);
1582	return false;
1583	}
1584
1585	default:
1586	return false;
1587	}
1588	}
1589
1590	/* Mark the GIMPLE_ASSIGN statement as appropriate for being inside
1591	a transaction region. */
1592
1593	static void
1594	examine_assign_tm (unsigned *state, gimple_stmt_iterator *gsi)
1595	{
1596	gimple *stmt = gsi_stmt (i: *gsi);
1597
1598	if (requires_barrier (/*entry_block=*/NULL, x: gimple_assign_rhs1 (gs: stmt), NULL))
1599	*state |= GTMA_HAVE_LOAD;
1600	if (requires_barrier (/*entry_block=*/NULL, x: gimple_assign_lhs (gs: stmt), NULL))
1601	*state |= GTMA_HAVE_STORE;
1602	}
1603
1604	/* Mark a GIMPLE_CALL as appropriate for being inside a transaction. */
1605
1606	static void
1607	examine_call_tm (unsigned *state, gimple_stmt_iterator *gsi)
1608	{
1609	gimple *stmt = gsi_stmt (i: *gsi);
1610	tree fn;
1611
1612	if (is_tm_pure_call (call: stmt))
1613	return;
1614
1615	/* Check if this call is a transaction abort. */
1616	fn = gimple_call_fndecl (gs: stmt);
1617	if (is_tm_abort (fndecl: fn))
1618	*state |= GTMA_HAVE_ABORT;
1619
1620	/* Note that something may happen. */
1621	*state |= GTMA_HAVE_LOAD | GTMA_HAVE_STORE;
1622	}
1623
1624	/* Iterate through the statements in the sequence, moving labels
1625	(and thus edges) of transactions from "label_norm" to "label_uninst". */
1626
1627	static tree
1628	make_tm_uninst (gimple_stmt_iterator *gsi, bool *handled_ops_p,
1629	struct walk_stmt_info *)
1630	{
1631	gimple *stmt = gsi_stmt (i: *gsi);
1632
1633	if (gtransaction *txn = dyn_cast <gtransaction *> (p: stmt))
1634	{
1635	*handled_ops_p = true;
1636	txn->label_uninst = txn->label_norm;
1637	txn->label_norm = NULL;
1638	}
1639	else
1640	*handled_ops_p = !gimple_has_substatements (g: stmt);
1641
1642	return NULL_TREE;
1643	}
1644
1645	/* Lower a GIMPLE_TRANSACTION statement. */
1646
1647	static void
1648	lower_transaction (gimple_stmt_iterator *gsi, struct walk_stmt_info *wi)
1649	{
1650	gimple *g;
1651	gtransaction *stmt = as_a <gtransaction *> (p: gsi_stmt (i: *gsi));
1652	unsigned int *outer_state = (unsigned int *) wi->info;
1653	unsigned int this_state = 0;
1654	struct walk_stmt_info this_wi;
1655
1656	/* First, lower the body. The scanning that we do inside gives
1657	us some idea of what we're dealing with. */
1658	memset (s: &this_wi, c: 0, n: sizeof (this_wi));
1659	this_wi.info = (void *) &this_state;
1660	walk_gimple_seq_mod (gimple_transaction_body_ptr (transaction_stmt: stmt),
1661	lower_sequence_tm, NULL, &this_wi);
1662
1663	/* If there was absolutely nothing transaction related inside the
1664	transaction, we may elide it. Likewise if this is a nested
1665	transaction and does not contain an abort. */
1666	if (this_state == 0
1667	|| (!(this_state & GTMA_HAVE_ABORT) && outer_state != NULL))
1668	{
1669	if (outer_state)
1670	*outer_state |= this_state;
1671
1672	gsi_insert_seq_before (gsi, gimple_transaction_body (transaction_stmt: stmt),
1673	GSI_SAME_STMT);
1674	gimple_transaction_set_body (transaction_stmt: stmt, NULL);
1675
1676	gsi_remove (gsi, true);
1677	wi->removed_stmt = true;
1678	return;
1679	}
1680
1681	/* Wrap the body of the transaction in a try-finally node so that
1682	the commit call is always properly called. */
1683	g = gimple_build_call (builtin_decl_explicit (fncode: BUILT_IN_TM_COMMIT), 0);
1684	if (flag_exceptions)
1685	{
1686	tree ptr;
1687	gimple_seq n_seq, e_seq;
1688
1689	n_seq = gimple_seq_alloc_with_stmt (stmt: g);
1690	e_seq = NULL;
1691
1692	g = gimple_build_call (builtin_decl_explicit (fncode: BUILT_IN_EH_POINTER),
1693	1, integer_zero_node);
1694	ptr = create_tmp_var (ptr_type_node);
1695	gimple_call_set_lhs (gs: g, lhs: ptr);
1696	gimple_seq_add_stmt (&e_seq, g);
1697
1698	g = gimple_build_call (builtin_decl_explicit (fncode: BUILT_IN_TM_COMMIT_EH),
1699	1, ptr);
1700	gimple_seq_add_stmt (&e_seq, g);
1701
1702	g = gimple_build_eh_else (n_seq, e_seq);
1703	}
1704
1705	g = gimple_build_try (gimple_transaction_body (transaction_stmt: stmt),
1706	gimple_seq_alloc_with_stmt (stmt: g), GIMPLE_TRY_FINALLY);
1707
1708	/* For a (potentially) outer transaction, create two paths. */
1709	gimple_seq uninst = NULL;
1710	if (outer_state == NULL)
1711	{
1712	uninst = copy_gimple_seq_and_replace_locals (seq: g);
1713	/* In the uninstrumented copy, reset inner transactions to have only
1714	an uninstrumented code path. */
1715	memset (s: &this_wi, c: 0, n: sizeof (this_wi));
1716	walk_gimple_seq (uninst, make_tm_uninst, NULL, &this_wi);
1717	}
1718
1719	tree label1 = create_artificial_label (UNKNOWN_LOCATION);
1720	gsi_insert_after (gsi, gimple_build_label (label: label1), GSI_CONTINUE_LINKING);
1721	gsi_insert_after (gsi, g, GSI_CONTINUE_LINKING);
1722	gimple_transaction_set_label_norm (transaction_stmt: stmt, label: label1);
1723
1724	/* If the transaction calls abort or if this is an outer transaction,
1725	add an "over" label afterwards. */
1726	tree label3 = NULL;
1727	if ((this_state & GTMA_HAVE_ABORT)
1728	|| outer_state == NULL
1729	|| (gimple_transaction_subcode (transaction_stmt: stmt) & GTMA_IS_OUTER))
1730	{
1731	label3 = create_artificial_label (UNKNOWN_LOCATION);
1732	gimple_transaction_set_label_over (transaction_stmt: stmt, label: label3);
1733	}
1734
1735	if (uninst != NULL)
1736	{
1737	gsi_insert_after (gsi, gimple_build_goto (dest: label3), GSI_CONTINUE_LINKING);
1738
1739	tree label2 = create_artificial_label (UNKNOWN_LOCATION);
1740	gsi_insert_after (gsi, gimple_build_label (label: label2), GSI_CONTINUE_LINKING);
1741	gsi_insert_seq_after (gsi, uninst, GSI_CONTINUE_LINKING);
1742	gimple_transaction_set_label_uninst (transaction_stmt: stmt, label: label2);
1743	}
1744
1745	if (label3 != NULL)
1746	gsi_insert_after (gsi, gimple_build_label (label: label3), GSI_CONTINUE_LINKING);
1747
1748	gimple_transaction_set_body (transaction_stmt: stmt, NULL);
1749
1750	/* Record the set of operations found for use later. */
1751	this_state |= gimple_transaction_subcode (transaction_stmt: stmt) & GTMA_DECLARATION_MASK;
1752	gimple_transaction_set_subcode (transaction_stmt: stmt, subcode: this_state);
1753	}
1754
1755	/* Iterate through the statements in the sequence, lowering them all
1756	as appropriate for being in a transaction. */
1757
1758	static tree
1759	lower_sequence_tm (gimple_stmt_iterator *gsi, bool *handled_ops_p,
1760	struct walk_stmt_info *wi)
1761	{
1762	unsigned int *state = (unsigned int *) wi->info;
1763	gimple *stmt = gsi_stmt (i: *gsi);
1764
1765	*handled_ops_p = true;
1766	switch (gimple_code (g: stmt))
1767	{
1768	case GIMPLE_ASSIGN:
1769	/* Only memory reads/writes need to be instrumented. */
1770	if (gimple_assign_single_p (gs: stmt))
1771	examine_assign_tm (state, gsi);
1772	break;
1773
1774	case GIMPLE_CALL:
1775	examine_call_tm (state, gsi);
1776	break;
1777
1778	case GIMPLE_ASM:
1779	*state |= GTMA_MAY_ENTER_IRREVOCABLE;
1780	break;
1781
1782	case GIMPLE_TRANSACTION:
1783	lower_transaction (gsi, wi);
1784	break;
1785
1786	default:
1787	*handled_ops_p = !gimple_has_substatements (g: stmt);
1788	break;
1789	}
1790
1791	return NULL_TREE;
1792	}
1793
1794	/* Iterate through the statements in the sequence, lowering them all
1795	as appropriate for being outside of a transaction. */
1796
1797	static tree
1798	lower_sequence_no_tm (gimple_stmt_iterator *gsi, bool *handled_ops_p,
1799	struct walk_stmt_info * wi)
1800	{
1801	gimple *stmt = gsi_stmt (i: *gsi);
1802
1803	if (gimple_code (g: stmt) == GIMPLE_TRANSACTION)
1804	{
1805	*handled_ops_p = true;
1806	lower_transaction (gsi, wi);
1807	}
1808	else
1809	*handled_ops_p = !gimple_has_substatements (g: stmt);
1810
1811	return NULL_TREE;
1812	}
1813
1814	/* Main entry point for flattening GIMPLE_TRANSACTION constructs. After
1815	this, GIMPLE_TRANSACTION nodes still exist, but the nested body has
1816	been moved out, and all the data required for constructing a proper
1817	CFG has been recorded. */
1818
1819	static unsigned int
1820	execute_lower_tm (void)
1821	{
1822	struct walk_stmt_info wi;
1823	gimple_seq body;
1824
1825	/* Transactional clones aren't created until a later pass. */
1826	gcc_assert (!decl_is_tm_clone (current_function_decl));
1827
1828	body = gimple_body (current_function_decl);
1829	memset (s: &wi, c: 0, n: sizeof (wi));
1830	walk_gimple_seq_mod (&body, lower_sequence_no_tm, NULL, &wi);
1831	gimple_set_body (current_function_decl, body);
1832
1833	return 0;
1834	}
1835
1836	namespace {
1837
1838	const pass_data pass_data_lower_tm =
1839	{
1840	.type: GIMPLE_PASS, /* type */
1841	.name: "tmlower", /* name */
1842	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
1843	.tv_id: TV_TRANS_MEM, /* tv_id */
1844	PROP_gimple_lcf, /* properties_required */
1845	.properties_provided: 0, /* properties_provided */
1846	.properties_destroyed: 0, /* properties_destroyed */
1847	.todo_flags_start: 0, /* todo_flags_start */
1848	.todo_flags_finish: 0, /* todo_flags_finish */
1849	};
1850
1851	class pass_lower_tm : public gimple_opt_pass
1852	{
1853	public:
1854	pass_lower_tm (gcc::context *ctxt)
1855	: gimple_opt_pass (pass_data_lower_tm, ctxt)
1856	{}
1857
1858	/* opt_pass methods: */
1859	bool gate (function *) final override { return flag_tm; }
1860	unsigned int execute (function *) final override
1861	{
1862	return execute_lower_tm ();
1863	}
1864
1865	}; // class pass_lower_tm
1866
1867	} // anon namespace
1868
1869	gimple_opt_pass *
1870	make_pass_lower_tm (gcc::context *ctxt)
1871	{
1872	return new pass_lower_tm (ctxt);
1873	}
1874
1875	/* Collect region information for each transaction. */
1876
1877	struct tm_region
1878	{
1879	public:
1880
1881	/* The field "transaction_stmt" is initially a gtransaction *,
1882	but eventually gets lowered to a gcall *(to BUILT_IN_TM_START).
1883
1884	Helper method to get it as a gtransaction *, with code-checking
1885	in a checked-build. */
1886
1887	gtransaction *
1888	get_transaction_stmt () const
1889	{
1890	return as_a <gtransaction *> (p: transaction_stmt);
1891	}
1892
1893	public:
1894
1895	/* Link to the next unnested transaction. */
1896	struct tm_region *next;
1897
1898	/* Link to the next inner transaction. */
1899	struct tm_region *inner;
1900
1901	/* Link to the next outer transaction. */
1902	struct tm_region *outer;
1903
1904	/* The GIMPLE_TRANSACTION statement beginning this transaction.
1905	After TM_MARK, this gets replaced by a call to
1906	BUILT_IN_TM_START.
1907	Hence this will be either a gtransaction *or a gcall *. */
1908	gimple *transaction_stmt;
1909
1910	/* After TM_MARK expands the GIMPLE_TRANSACTION into a call to
1911	BUILT_IN_TM_START, this field is true if the transaction is an
1912	outer transaction. */
1913	bool original_transaction_was_outer;
1914
1915	/* Return value from BUILT_IN_TM_START. */
1916	tree tm_state;
1917
1918	/* The entry block to this region. This will always be the first
1919	block of the body of the transaction. */
1920	basic_block entry_block;
1921
1922	/* The first block after an expanded call to _ITM_beginTransaction. */
1923	basic_block restart_block;
1924
1925	/* The set of all blocks that end the region; NULL if only EXIT_BLOCK.
1926	These blocks are still a part of the region (i.e., the border is
1927	inclusive). Note that this set is only complete for paths in the CFG
1928	starting at ENTRY_BLOCK, and that there is no exit block recorded for
1929	the edge to the "over" label. */
1930	bitmap exit_blocks;
1931
1932	/* The set of all blocks that have an TM_IRREVOCABLE call. */
1933	bitmap irr_blocks;
1934	};
1935
1936	/* True if there are pending edge statements to be committed for the
1937	current function being scanned in the tmmark pass. */
1938	bool pending_edge_inserts_p;
1939
1940	static struct tm_region *all_tm_regions;
1941	static bitmap_obstack tm_obstack;
1942
1943
1944	/* A subroutine of tm_region_init. Record the existence of the
1945	GIMPLE_TRANSACTION statement in a tree of tm_region elements. */
1946
1947	static struct tm_region *
1948	tm_region_init_0 (struct tm_region *outer, basic_block bb,
1949	gtransaction *stmt)
1950	{
1951	struct tm_region *region;
1952
1953	region = (struct tm_region *)
1954	obstack_alloc (&tm_obstack.obstack, sizeof (struct tm_region));
1955
1956	if (outer)
1957	{
1958	region->next = outer->inner;
1959	outer->inner = region;
1960	}
1961	else
1962	{
1963	region->next = all_tm_regions;
1964	all_tm_regions = region;
1965	}
1966	region->inner = NULL;
1967	region->outer = outer;
1968
1969	region->transaction_stmt = stmt;
1970	region->original_transaction_was_outer = false;
1971	region->tm_state = NULL;
1972
1973	/* There are either one or two edges out of the block containing
1974	the GIMPLE_TRANSACTION, one to the actual region and one to the
1975	"over" label if the region contains an abort. The former will
1976	always be the one marked FALLTHRU. */
1977	region->entry_block = FALLTHRU_EDGE (bb)->dest;
1978
1979	region->exit_blocks = BITMAP_ALLOC (obstack: &tm_obstack);
1980	region->irr_blocks = BITMAP_ALLOC (obstack: &tm_obstack);
1981
1982	return region;
1983	}
1984
1985	/* A subroutine of tm_region_init. Record all the exit and
1986	irrevocable blocks in BB into the region's exit_blocks and
1987	irr_blocks bitmaps. Returns the new region being scanned. */
1988
1989	static struct tm_region *
1990	tm_region_init_1 (struct tm_region *region, basic_block bb)
1991	{
1992	gimple_stmt_iterator gsi;
1993	gimple *g;
1994
1995	if (!region
1996	|| (!region->irr_blocks && !region->exit_blocks))
1997	return region;
1998
1999	/* Check to see if this is the end of a region by seeing if it
2000	contains a call to __builtin_tm_commit{,_eh}. Note that the
2001	outermost region for DECL_IS_TM_CLONE need not collect this. */
2002	for (gsi = gsi_last_bb (bb); !gsi_end_p (i: gsi); gsi_prev (i: &gsi))
2003	{
2004	g = gsi_stmt (i: gsi);
2005	if (gimple_code (g) == GIMPLE_CALL)
2006	{
2007	tree fn = gimple_call_fndecl (gs: g);
2008	if (fn && fndecl_built_in_p (node: fn, klass: BUILT_IN_NORMAL))
2009	{
2010	if ((DECL_FUNCTION_CODE (decl: fn) == BUILT_IN_TM_COMMIT
2011	|| DECL_FUNCTION_CODE (decl: fn) == BUILT_IN_TM_COMMIT_EH)
2012	&& region->exit_blocks)
2013	{
2014	bitmap_set_bit (region->exit_blocks, bb->index);
2015	region = region->outer;
2016	break;
2017	}
2018	if (DECL_FUNCTION_CODE (decl: fn) == BUILT_IN_TM_IRREVOCABLE)
2019	bitmap_set_bit (region->irr_blocks, bb->index);
2020	}
2021	}
2022	}
2023	return region;
2024	}
2025
2026	/* Collect all of the transaction regions within the current function
2027	and record them in ALL_TM_REGIONS. The REGION parameter may specify
2028	an "outermost" region for use by tm clones. */
2029
2030	static void
2031	tm_region_init (struct tm_region *region)
2032	{
2033	gimple *g;
2034	edge_iterator ei;
2035	edge e;
2036	basic_block bb;
2037	auto_vec<basic_block> queue;
2038	bitmap visited_blocks = BITMAP_ALLOC (NULL);
2039	struct tm_region *old_region;
2040	auto_vec<tm_region *> bb_regions;
2041
2042	/* We could store this information in bb->aux, but we may get called
2043	through get_all_tm_blocks() from another pass that may be already
2044	using bb->aux. */
2045	bb_regions.safe_grow_cleared (last_basic_block_for_fn (cfun), exact: true);
2046
2047	all_tm_regions = region;
2048	bb = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
2049	queue.safe_push (obj: bb);
2050	bitmap_set_bit (visited_blocks, bb->index);
2051	bb_regions[bb->index] = region;
2052
2053	do
2054	{
2055	bb = queue.pop ();
2056	region = bb_regions[bb->index];
2057	bb_regions[bb->index] = NULL;
2058
2059	/* Record exit and irrevocable blocks. */
2060	region = tm_region_init_1 (region, bb);
2061
2062	/* Check for the last statement in the block beginning a new region. */
2063	g = last_nondebug_stmt (bb);
2064	old_region = region;
2065	if (g)
2066	if (gtransaction *trans_stmt = dyn_cast <gtransaction *> (p: g))
2067	region = tm_region_init_0 (outer: region, bb, stmt: trans_stmt);
2068
2069	/* Process subsequent blocks. */
2070	FOR_EACH_EDGE (e, ei, bb->succs)
2071	if (!bitmap_bit_p (visited_blocks, e->dest->index))
2072	{
2073	bitmap_set_bit (visited_blocks, e->dest->index);
2074	queue.safe_push (obj: e->dest);
2075
2076	/* If the current block started a new region, make sure that only
2077	the entry block of the new region is associated with this region.
2078	Other successors are still part of the old region. */
2079	if (old_region != region && e->dest != region->entry_block)
2080	bb_regions[e->dest->index] = old_region;
2081	else
2082	bb_regions[e->dest->index] = region;
2083	}
2084	}
2085	while (!queue.is_empty ());
2086	BITMAP_FREE (visited_blocks);
2087	}
2088
2089	/* The "gate" function for all transactional memory expansion and optimization
2090	passes. We collect region information for each top-level transaction, and
2091	if we don't find any, we skip all of the TM passes. Each region will have
2092	all of the exit blocks recorded, and the originating statement. */
2093
2094	static bool
2095	gate_tm_init (void)
2096	{
2097	if (!flag_tm)
2098	return false;
2099
2100	calculate_dominance_info (CDI_DOMINATORS);
2101	bitmap_obstack_initialize (&tm_obstack);
2102
2103	/* If the function is a TM_CLONE, then the entire function is the region. */
2104	if (decl_is_tm_clone (fndecl: current_function_decl))
2105	{
2106	struct tm_region *region = (struct tm_region *)
2107	obstack_alloc (&tm_obstack.obstack, sizeof (struct tm_region));
2108	memset (s: region, c: 0, n: sizeof (*region));
2109	region->entry_block = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
2110	/* For a clone, the entire function is the region. But even if
2111	we don't need to record any exit blocks, we may need to
2112	record irrevocable blocks. */
2113	region->irr_blocks = BITMAP_ALLOC (obstack: &tm_obstack);
2114
2115	tm_region_init (region);
2116	}
2117	else
2118	{
2119	tm_region_init (NULL);
2120
2121	/* If we didn't find any regions, cleanup and skip the whole tree
2122	of tm-related optimizations. */
2123	if (all_tm_regions == NULL)
2124	{
2125	bitmap_obstack_release (&tm_obstack);
2126	return false;
2127	}
2128	}
2129
2130	return true;
2131	}
2132
2133	namespace {
2134
2135	const pass_data pass_data_tm_init =
2136	{
2137	.type: GIMPLE_PASS, /* type */
2138	.name: "*tminit", /* name */
2139	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
2140	.tv_id: TV_TRANS_MEM, /* tv_id */
2141	.properties_required: ( PROP_ssa | PROP_cfg ), /* properties_required */
2142	.properties_provided: 0, /* properties_provided */
2143	.properties_destroyed: 0, /* properties_destroyed */
2144	.todo_flags_start: 0, /* todo_flags_start */
2145	.todo_flags_finish: 0, /* todo_flags_finish */
2146	};
2147
2148	class pass_tm_init : public gimple_opt_pass
2149	{
2150	public:
2151	pass_tm_init (gcc::context *ctxt)
2152	: gimple_opt_pass (pass_data_tm_init, ctxt)
2153	{}
2154
2155	/* opt_pass methods: */
2156	bool gate (function *) final override { return gate_tm_init (); }
2157
2158	}; // class pass_tm_init
2159
2160	} // anon namespace
2161
2162	gimple_opt_pass *
2163	make_pass_tm_init (gcc::context *ctxt)
2164	{
2165	return new pass_tm_init (ctxt);
2166	}
2167
2168	/* Add FLAGS to the GIMPLE_TRANSACTION subcode for the transaction region
2169	represented by STATE. */
2170
2171	static inline void
2172	transaction_subcode_ior (struct tm_region *region, unsigned flags)
2173	{
2174	if (region && region->transaction_stmt)
2175	{
2176	gtransaction *transaction_stmt = region->get_transaction_stmt ();
2177	flags |= gimple_transaction_subcode (transaction_stmt);
2178	gimple_transaction_set_subcode (transaction_stmt, subcode: flags);
2179	}
2180	}
2181
2182	/* Construct a memory load in a transactional context. Return the
2183	gimple statement performing the load, or NULL if there is no
2184	TM_LOAD builtin of the appropriate size to do the load.
2185
2186	LOC is the location to use for the new statement(s). */
2187
2188	static gcall *
2189	build_tm_load (location_t loc, tree lhs, tree rhs, gimple_stmt_iterator *gsi)
2190	{
2191	tree t, type = TREE_TYPE (rhs);
2192	gcall *gcall;
2193
2194	built_in_function code;
2195	if (type == float_type_node)
2196	code = BUILT_IN_TM_LOAD_FLOAT;
2197	else if (type == double_type_node)
2198	code = BUILT_IN_TM_LOAD_DOUBLE;
2199	else if (type == long_double_type_node)
2200	code = BUILT_IN_TM_LOAD_LDOUBLE;
2201	else
2202	{
2203	if (TYPE_SIZE (type) == NULL || !tree_fits_uhwi_p (TYPE_SIZE (type)))
2204	return NULL;
2205	unsigned HOST_WIDE_INT type_size = tree_to_uhwi (TYPE_SIZE (type));
2206
2207	if (TREE_CODE (type) == VECTOR_TYPE)
2208	{
2209	switch (type_size)
2210	{
2211	case 64:
2212	code = BUILT_IN_TM_LOAD_M64;
2213	break;
2214	case 128:
2215	code = BUILT_IN_TM_LOAD_M128;
2216	break;
2217	case 256:
2218	code = BUILT_IN_TM_LOAD_M256;
2219	break;
2220	default:
2221	goto unhandled_vec;
2222	}
2223	if (!builtin_decl_explicit_p (fncode: code))
2224	goto unhandled_vec;
2225	}
2226	else
2227	{
2228	unhandled_vec:
2229	switch (type_size)
2230	{
2231	case 8:
2232	code = BUILT_IN_TM_LOAD_1;
2233	break;
2234	case 16:
2235	code = BUILT_IN_TM_LOAD_2;
2236	break;
2237	case 32:
2238	code = BUILT_IN_TM_LOAD_4;
2239	break;
2240	case 64:
2241	code = BUILT_IN_TM_LOAD_8;
2242	break;
2243	default:
2244	return NULL;
2245	}
2246	}
2247	}
2248
2249	tree decl = builtin_decl_explicit (fncode: code);
2250	gcc_assert (decl);
2251
2252	t = gimplify_addr (gsi, x: rhs);
2253	gcall = gimple_build_call (decl, 1, t);
2254	gimple_set_location (g: gcall, location: loc);
2255
2256	t = TREE_TYPE (TREE_TYPE (decl));
2257	if (useless_type_conversion_p (type, t))
2258	{
2259	gimple_call_set_lhs (gs: gcall, lhs);
2260	gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2261	}
2262	else
2263	{
2264	gimple *g;
2265	tree temp;
2266
2267	temp = create_tmp_reg (t);
2268	gimple_call_set_lhs (gs: gcall, lhs: temp);
2269	gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2270
2271	t = fold_build1 (VIEW_CONVERT_EXPR, type, temp);
2272	g = gimple_build_assign (lhs, t);
2273	gsi_insert_before (gsi, g, GSI_SAME_STMT);
2274	}
2275
2276	return gcall;
2277	}
2278
2279
2280	/* Similarly for storing TYPE in a transactional context. */
2281
2282	static gcall *
2283	build_tm_store (location_t loc, tree lhs, tree rhs, gimple_stmt_iterator *gsi)
2284	{
2285	tree t, fn, type = TREE_TYPE (rhs), simple_type;
2286	gcall *gcall;
2287
2288	built_in_function code;
2289	if (type == float_type_node)
2290	code = BUILT_IN_TM_STORE_FLOAT;
2291	else if (type == double_type_node)
2292	code = BUILT_IN_TM_STORE_DOUBLE;
2293	else if (type == long_double_type_node)
2294	code = BUILT_IN_TM_STORE_LDOUBLE;
2295	else
2296	{
2297	if (TYPE_SIZE (type) == NULL || !tree_fits_uhwi_p (TYPE_SIZE (type)))
2298	return NULL;
2299	unsigned HOST_WIDE_INT type_size = tree_to_uhwi (TYPE_SIZE (type));
2300
2301	if (TREE_CODE (type) == VECTOR_TYPE)
2302	{
2303	switch (type_size)
2304	{
2305	case 64:
2306	code = BUILT_IN_TM_STORE_M64;
2307	break;
2308	case 128:
2309	code = BUILT_IN_TM_STORE_M128;
2310	break;
2311	case 256:
2312	code = BUILT_IN_TM_STORE_M256;
2313	break;
2314	default:
2315	goto unhandled_vec;
2316	}
2317	if (!builtin_decl_explicit_p (fncode: code))
2318	goto unhandled_vec;
2319	}
2320	else
2321	{
2322	unhandled_vec:
2323	switch (type_size)
2324	{
2325	case 8:
2326	code = BUILT_IN_TM_STORE_1;
2327	break;
2328	case 16:
2329	code = BUILT_IN_TM_STORE_2;
2330	break;
2331	case 32:
2332	code = BUILT_IN_TM_STORE_4;
2333	break;
2334	case 64:
2335	code = BUILT_IN_TM_STORE_8;
2336	break;
2337	default:
2338	return NULL;
2339	}
2340	}
2341	}
2342
2343	fn = builtin_decl_explicit (fncode: code);
2344	gcc_assert (fn);
2345
2346	simple_type = TREE_VALUE (TREE_CHAIN (TYPE_ARG_TYPES (TREE_TYPE (fn))));
2347
2348	if (TREE_CODE (rhs) == CONSTRUCTOR)
2349	{
2350	/* Handle the easy initialization to zero. */
2351	if (!CONSTRUCTOR_ELTS (rhs))
2352	rhs = build_int_cst (simple_type, 0);
2353	else
2354	{
2355	/* ...otherwise punt to the caller and probably use
2356	BUILT_IN_TM_MEMMOVE, because we can't wrap a
2357	VIEW_CONVERT_EXPR around a CONSTRUCTOR (below) and produce
2358	valid gimple. */
2359	return NULL;
2360	}
2361	}
2362	else if (!useless_type_conversion_p (simple_type, type))
2363	{
2364	gimple *g;
2365	tree temp;
2366
2367	temp = create_tmp_reg (simple_type);
2368	t = fold_build1 (VIEW_CONVERT_EXPR, simple_type, rhs);
2369	g = gimple_build_assign (temp, t);
2370	gimple_set_location (g, location: loc);
2371	gsi_insert_before (gsi, g, GSI_SAME_STMT);
2372
2373	rhs = temp;
2374	}
2375
2376	t = gimplify_addr (gsi, x: lhs);
2377	gcall = gimple_build_call (fn, 2, t, rhs);
2378	gimple_set_location (g: gcall, location: loc);
2379	gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2380
2381	return gcall;
2382	}
2383
2384
2385	/* Expand an assignment statement into transactional builtins. */
2386
2387	static void
2388	expand_assign_tm (struct tm_region *region, gimple_stmt_iterator *gsi)
2389	{
2390	gimple *stmt = gsi_stmt (i: *gsi);
2391	location_t loc = gimple_location (g: stmt);
2392	tree lhs = gimple_assign_lhs (gs: stmt);
2393	tree rhs = gimple_assign_rhs1 (gs: stmt);
2394	bool store_p = requires_barrier (entry_block: region->entry_block, x: lhs, NULL);
2395	bool load_p = requires_barrier (entry_block: region->entry_block, x: rhs, NULL);
2396	gimple *gcall = NULL;
2397
2398	if (!load_p && !store_p)
2399	{
2400	/* Add thread private addresses to log if applicable. */
2401	requires_barrier (entry_block: region->entry_block, x: lhs, stmt);
2402	gsi_next (i: gsi);
2403	return;
2404	}
2405
2406	if (load_p)
2407	transaction_subcode_ior (region, GTMA_HAVE_LOAD);
2408	if (store_p)
2409	transaction_subcode_ior (region, GTMA_HAVE_STORE);
2410
2411	// Remove original load/store statement.
2412	gsi_remove (gsi, true);
2413
2414	// Attempt to use a simple load/store helper function.
2415	if (load_p && !store_p)
2416	gcall = build_tm_load (loc, lhs, rhs, gsi);
2417	else if (store_p && !load_p)
2418	gcall = build_tm_store (loc, lhs, rhs, gsi);
2419
2420	// If gcall has not been set, then we do not have a simple helper
2421	// function available for the type. This may be true of larger
2422	// structures, vectors, and non-standard float types.
2423	if (!gcall)
2424	{
2425	tree lhs_addr, rhs_addr, ltmp = NULL, copy_fn;
2426
2427	// If this is a type that we couldn't handle above, but it's
2428	// in a register, we must spill it to memory for the copy.
2429	if (is_gimple_reg (lhs))
2430	{
2431	ltmp = create_tmp_var (TREE_TYPE (lhs));
2432	lhs_addr = build_fold_addr_expr (ltmp);
2433	}
2434	else
2435	lhs_addr = gimplify_addr (gsi, x: lhs);
2436	if (is_gimple_reg (rhs))
2437	{
2438	tree rtmp = create_tmp_var (TREE_TYPE (rhs));
2439	TREE_ADDRESSABLE (rtmp) = 1;
2440	rhs_addr = build_fold_addr_expr (rtmp);
2441	gcall = gimple_build_assign (rtmp, rhs);
2442	gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2443	}
2444	else
2445	rhs_addr = gimplify_addr (gsi, x: rhs);
2446
2447	// Choose the appropriate memory transfer function.
2448	if (load_p && store_p)
2449	{
2450	// ??? Figure out if there's any possible overlap between
2451	// the LHS and the RHS and if not, use MEMCPY.
2452	copy_fn = builtin_decl_explicit (fncode: BUILT_IN_TM_MEMMOVE);
2453	}
2454	else if (load_p)
2455	{
2456	// Note that the store is non-transactional and cannot overlap.
2457	copy_fn = builtin_decl_explicit (fncode: BUILT_IN_TM_MEMCPY_RTWN);
2458	}
2459	else
2460	{
2461	// Note that the load is non-transactional and cannot overlap.
2462	copy_fn = builtin_decl_explicit (fncode: BUILT_IN_TM_MEMCPY_RNWT);
2463	}
2464
2465	gcall = gimple_build_call (copy_fn, 3, lhs_addr, rhs_addr,
2466	TYPE_SIZE_UNIT (TREE_TYPE (lhs)));
2467	gimple_set_location (g: gcall, location: loc);
2468	gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2469
2470	if (ltmp)
2471	{
2472	gcall = gimple_build_assign (lhs, ltmp);
2473	gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2474	}
2475	}
2476
2477	// Now that we have the load/store in its instrumented form, add
2478	// thread private addresses to the log if applicable.
2479	if (!store_p)
2480	requires_barrier (entry_block: region->entry_block, x: lhs, stmt: gcall);
2481	}
2482
2483
2484	/* Expand a call statement as appropriate for a transaction. That is,
2485	either verify that the call does not affect the transaction, or
2486	redirect the call to a clone that handles transactions, or change
2487	the transaction state to IRREVOCABLE. Return true if the call is
2488	one of the builtins that end a transaction. */
2489
2490	static bool
2491	expand_call_tm (struct tm_region *region,
2492	gimple_stmt_iterator *gsi)
2493	{
2494	gcall *stmt = as_a <gcall *> (p: gsi_stmt (i: *gsi));
2495	tree lhs = gimple_call_lhs (gs: stmt);
2496	tree fn_decl;
2497	struct cgraph_node *node;
2498	bool retval = false;
2499
2500	fn_decl = gimple_call_fndecl (gs: stmt);
2501
2502	if (fn_decl == builtin_decl_explicit (fncode: BUILT_IN_TM_MEMCPY)
2503	|| fn_decl == builtin_decl_explicit (fncode: BUILT_IN_TM_MEMMOVE))
2504	transaction_subcode_ior (region, GTMA_HAVE_STORE | GTMA_HAVE_LOAD);
2505	if (fn_decl == builtin_decl_explicit (fncode: BUILT_IN_TM_MEMSET))
2506	transaction_subcode_ior (region, GTMA_HAVE_STORE);
2507
2508	if (is_tm_pure_call (call: stmt))
2509	return false;
2510
2511	if (fn_decl)
2512	retval = is_tm_ending_fndecl (fndecl: fn_decl);
2513	if (!retval)
2514	{
2515	/* Assume all non-const/pure calls write to memory, except
2516	transaction ending builtins. */
2517	transaction_subcode_ior (region, GTMA_HAVE_STORE);
2518	}
2519
2520	/* For indirect calls, we already generated a call into the runtime. */
2521	if (!fn_decl)
2522	{
2523	tree fn = gimple_call_fn (gs: stmt);
2524
2525	/* We are guaranteed never to go irrevocable on a safe or pure
2526	call, and the pure call was handled above. */
2527	if (is_tm_safe (x: fn))
2528	return false;
2529	else
2530	transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
2531
2532	return false;
2533	}
2534
2535	node = cgraph_node::get (decl: fn_decl);
2536	/* All calls should have cgraph here. */
2537	if (!node)
2538	{
2539	/* We can have a nodeless call here if some pass after IPA-tm
2540	added uninstrumented calls. For example, loop distribution
2541	can transform certain loop constructs into __builtin_mem*
2542	calls. In this case, see if we have a suitable TM
2543	replacement and fill in the gaps. */
2544	gcc_assert (DECL_BUILT_IN_CLASS (fn_decl) == BUILT_IN_NORMAL);
2545	enum built_in_function code = DECL_FUNCTION_CODE (decl: fn_decl);
2546	gcc_assert (code == BUILT_IN_MEMCPY
2547	|| code == BUILT_IN_MEMMOVE
2548	|| code == BUILT_IN_MEMSET);
2549
2550	tree repl = find_tm_replacement_function (fndecl: fn_decl);
2551	if (repl)
2552	{
2553	gimple_call_set_fndecl (gs: stmt, decl: repl);
2554	update_stmt (s: stmt);
2555	node = cgraph_node::create (decl: repl);
2556	node->tm_may_enter_irr = false;
2557	return expand_call_tm (region, gsi);
2558	}
2559	gcc_unreachable ();
2560	}
2561	if (node->tm_may_enter_irr)
2562	transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
2563
2564	if (is_tm_abort (fndecl: fn_decl))
2565	{
2566	transaction_subcode_ior (region, GTMA_HAVE_ABORT);
2567	return true;
2568	}
2569
2570	/* Instrument the store if needed.
2571
2572	If the assignment happens inside the function call (return slot
2573	optimization), there is no instrumentation to be done, since
2574	the callee should have done the right thing. */
2575	if (lhs && requires_barrier (entry_block: region->entry_block, x: lhs, stmt)
2576	&& !gimple_call_return_slot_opt_p (s: stmt))
2577	{
2578	tree tmp = create_tmp_reg (TREE_TYPE (lhs));
2579	location_t loc = gimple_location (g: stmt);
2580	edge fallthru_edge = NULL;
2581	gassign *assign_stmt;
2582
2583	/* Remember if the call was going to throw. */
2584	if (stmt_can_throw_internal (cfun, stmt))
2585	{
2586	edge_iterator ei;
2587	edge e;
2588	basic_block bb = gimple_bb (g: stmt);
2589
2590	FOR_EACH_EDGE (e, ei, bb->succs)
2591	if (e->flags & EDGE_FALLTHRU)
2592	{
2593	fallthru_edge = e;
2594	break;
2595	}
2596	}
2597
2598	gimple_call_set_lhs (gs: stmt, lhs: tmp);
2599	update_stmt (s: stmt);
2600	assign_stmt = gimple_build_assign (lhs, tmp);
2601	gimple_set_location (g: assign_stmt, location: loc);
2602
2603	/* We cannot throw in the middle of a BB. If the call was going
2604	to throw, place the instrumentation on the fallthru edge, so
2605	the call remains the last statement in the block. */
2606	if (fallthru_edge)
2607	{
2608	gimple_seq fallthru_seq = gimple_seq_alloc_with_stmt (stmt: assign_stmt);
2609	gimple_stmt_iterator fallthru_gsi = gsi_start (seq&: fallthru_seq);
2610	expand_assign_tm (region, gsi: &fallthru_gsi);
2611	gsi_insert_seq_on_edge (fallthru_edge, fallthru_seq);
2612	pending_edge_inserts_p = true;
2613	}
2614	else
2615	{
2616	gsi_insert_after (gsi, assign_stmt, GSI_CONTINUE_LINKING);
2617	expand_assign_tm (region, gsi);
2618	}
2619
2620	transaction_subcode_ior (region, GTMA_HAVE_STORE);
2621	}
2622
2623	return retval;
2624	}
2625
2626
2627	/* Expand all statements in BB as appropriate for being inside
2628	a transaction. */
2629
2630	static void
2631	expand_block_tm (struct tm_region *region, basic_block bb)
2632	{
2633	gimple_stmt_iterator gsi;
2634
2635	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); )
2636	{
2637	gimple *stmt = gsi_stmt (i: gsi);
2638	switch (gimple_code (g: stmt))
2639	{
2640	case GIMPLE_ASSIGN:
2641	/* Only memory reads/writes need to be instrumented. */
2642	if (gimple_assign_single_p (gs: stmt)
2643	&& !gimple_clobber_p (s: stmt))
2644	{
2645	expand_assign_tm (region, gsi: &gsi);
2646	continue;
2647	}
2648	break;
2649
2650	case GIMPLE_CALL:
2651	if (expand_call_tm (region, gsi: &gsi))
2652	return;
2653	break;
2654
2655	case GIMPLE_ASM:
2656	gcc_unreachable ();
2657
2658	default:
2659	break;
2660	}
2661	if (!gsi_end_p (i: gsi))
2662	gsi_next (i: &gsi);
2663	}
2664	}
2665
2666	/* Return the list of basic-blocks in REGION.
2667
2668	STOP_AT_IRREVOCABLE_P is true if caller is uninterested in blocks
2669	following a TM_IRREVOCABLE call.
2670
2671	INCLUDE_UNINSTRUMENTED_P is TRUE if we should include the
2672	uninstrumented code path blocks in the list of basic blocks
2673	returned, false otherwise. */
2674
2675	static vec<basic_block>
2676	get_tm_region_blocks (basic_block entry_block,
2677	bitmap exit_blocks,
2678	bitmap irr_blocks,
2679	bitmap all_region_blocks,
2680	bool stop_at_irrevocable_p,
2681	bool include_uninstrumented_p = true)
2682	{
2683	vec<basic_block> bbs = vNULL;
2684	unsigned i;
2685	edge e;
2686	edge_iterator ei;
2687	bitmap visited_blocks = BITMAP_ALLOC (NULL);
2688
2689	i = 0;
2690	bbs.safe_push (obj: entry_block);
2691	bitmap_set_bit (visited_blocks, entry_block->index);
2692
2693	do
2694	{
2695	basic_block bb = bbs[i++];
2696
2697	if (exit_blocks &&
2698	bitmap_bit_p (exit_blocks, bb->index))
2699	continue;
2700
2701	if (stop_at_irrevocable_p
2702	&& irr_blocks
2703	&& bitmap_bit_p (irr_blocks, bb->index))
2704	continue;
2705
2706	FOR_EACH_EDGE (e, ei, bb->succs)
2707	if ((include_uninstrumented_p
2708	|| !(e->flags & EDGE_TM_UNINSTRUMENTED))
2709	&& !bitmap_bit_p (visited_blocks, e->dest->index))
2710	{
2711	bitmap_set_bit (visited_blocks, e->dest->index);
2712	bbs.safe_push (obj: e->dest);
2713	}
2714	}
2715	while (i < bbs.length ());
2716
2717	if (all_region_blocks)
2718	bitmap_ior_into (all_region_blocks, visited_blocks);
2719
2720	BITMAP_FREE (visited_blocks);
2721	return bbs;
2722	}
2723
2724	// Callback data for collect_bb2reg.
2725	struct bb2reg_stuff
2726	{
2727	vec<tm_region *> *bb2reg;
2728	bool include_uninstrumented_p;
2729	};
2730
2731	// Callback for expand_regions, collect innermost region data for each bb.
2732	static void *
2733	collect_bb2reg (struct tm_region *region, void *data)
2734	{
2735	struct bb2reg_stuff *stuff = (struct bb2reg_stuff *)data;
2736	vec<tm_region *> *bb2reg = stuff->bb2reg;
2737	vec<basic_block> queue;
2738	unsigned int i;
2739	basic_block bb;
2740
2741	queue = get_tm_region_blocks (entry_block: region->entry_block,
2742	exit_blocks: region->exit_blocks,
2743	irr_blocks: region->irr_blocks,
2744	NULL,
2745	/*stop_at_irr_p=*/stop_at_irrevocable_p: true,
2746	include_uninstrumented_p: stuff->include_uninstrumented_p);
2747
2748	// We expect expand_region to perform a post-order traversal of the region
2749	// tree. Therefore the last region seen for any bb is the innermost.
2750	FOR_EACH_VEC_ELT (queue, i, bb)
2751	(*bb2reg)[bb->index] = region;
2752
2753	queue.release ();
2754	return NULL;
2755	}
2756
2757	// Returns a vector, indexed by BB->INDEX, of the innermost tm_region to
2758	// which a basic block belongs. Note that we only consider the instrumented
2759	// code paths for the region; the uninstrumented code paths are ignored if
2760	// INCLUDE_UNINSTRUMENTED_P is false.
2761	//
2762	// ??? This data is very similar to the bb_regions array that is collected
2763	// during tm_region_init. Or, rather, this data is similar to what could
2764	// be used within tm_region_init. The actual computation in tm_region_init
2765	// begins and ends with bb_regions entirely full of NULL pointers, due to
2766	// the way in which pointers are swapped in and out of the array.
2767	//
2768	// ??? Our callers expect that blocks are not shared between transactions.
2769	// When the optimizers get too smart, and blocks are shared, then during
2770	// the tm_mark phase we'll add log entries to only one of the two transactions,
2771	// and in the tm_edge phase we'll add edges to the CFG that create invalid
2772	// cycles. The symptom being SSA defs that do not dominate their uses.
2773	// Note that the optimizers were locally correct with their transformation,
2774	// as we have no info within the program that suggests that the blocks cannot
2775	// be shared.
2776	//
2777	// ??? There is currently a hack inside tree-ssa-pre.cc to work around the
2778	// only known instance of this block sharing.
2779
2780	static vec<tm_region *>
2781	get_bb_regions_instrumented (bool traverse_clones,
2782	bool include_uninstrumented_p)
2783	{
2784	unsigned n = last_basic_block_for_fn (cfun);
2785	struct bb2reg_stuff stuff;
2786	vec<tm_region *> ret;
2787
2788	ret.create (nelems: n);
2789	ret.safe_grow_cleared (len: n, exact: true);
2790	stuff.bb2reg = &ret;
2791	stuff.include_uninstrumented_p = include_uninstrumented_p;
2792	expand_regions (all_tm_regions, callback: collect_bb2reg, &stuff, traverse_clones);
2793
2794	return ret;
2795	}
2796
2797	/* Set the IN_TRANSACTION for all gimple statements that appear in a
2798	transaction. */
2799
2800	void
2801	compute_transaction_bits (void)
2802	{
2803	struct tm_region *region;
2804	vec<basic_block> queue;
2805	unsigned int i;
2806	basic_block bb;
2807
2808	/* ?? Perhaps we need to abstract gate_tm_init further, because we
2809	certainly don't need it to calculate CDI_DOMINATOR info. */
2810	gate_tm_init ();
2811
2812	FOR_EACH_BB_FN (bb, cfun)
2813	bb->flags &= ~BB_IN_TRANSACTION;
2814
2815	for (region = all_tm_regions; region; region = region->next)
2816	{
2817	queue = get_tm_region_blocks (entry_block: region->entry_block,
2818	exit_blocks: region->exit_blocks,
2819	irr_blocks: region->irr_blocks,
2820	NULL,
2821	/*stop_at_irr_p=*/stop_at_irrevocable_p: true);
2822	for (i = 0; queue.iterate (ix: i, ptr: &bb); ++i)
2823	bb->flags |= BB_IN_TRANSACTION;
2824	queue.release ();
2825	}
2826
2827	if (all_tm_regions)
2828	bitmap_obstack_release (&tm_obstack);
2829	}
2830
2831	/* Replace the GIMPLE_TRANSACTION in this region with the corresponding
2832	call to BUILT_IN_TM_START. */
2833
2834	static void *
2835	expand_transaction (struct tm_region *region, void *data ATTRIBUTE_UNUSED)
2836	{
2837	tree tm_start = builtin_decl_explicit (fncode: BUILT_IN_TM_START);
2838	basic_block transaction_bb = gimple_bb (g: region->transaction_stmt);
2839	tree tm_state = region->tm_state;
2840	tree tm_state_type = TREE_TYPE (tm_state);
2841	edge abort_edge = NULL;
2842	edge inst_edge = NULL;
2843	edge uninst_edge = NULL;
2844	edge fallthru_edge = NULL;
2845
2846	// Identify the various successors of the transaction start.
2847	{
2848	edge_iterator i;
2849	edge e;
2850	FOR_EACH_EDGE (e, i, transaction_bb->succs)
2851	{
2852	if (e->flags & EDGE_TM_ABORT)
2853	abort_edge = e;
2854	else if (e->flags & EDGE_TM_UNINSTRUMENTED)
2855	uninst_edge = e;
2856	else
2857	inst_edge = e;
2858	if (e->flags & EDGE_FALLTHRU)
2859	fallthru_edge = e;
2860	}
2861	}
2862
2863	/* ??? There are plenty of bits here we're not computing. */
2864	{
2865	int subcode = gimple_transaction_subcode (transaction_stmt: region->get_transaction_stmt ());
2866	int flags = 0;
2867	if (subcode & GTMA_DOES_GO_IRREVOCABLE)
2868	flags |= PR_DOESGOIRREVOCABLE;
2869	if ((subcode & GTMA_MAY_ENTER_IRREVOCABLE) == 0)
2870	flags |= PR_HASNOIRREVOCABLE;
2871	/* If the transaction does not have an abort in lexical scope and is not
2872	marked as an outer transaction, then it will never abort. */
2873	if ((subcode & GTMA_HAVE_ABORT) == 0 && (subcode & GTMA_IS_OUTER) == 0)
2874	flags |= PR_HASNOABORT;
2875	if ((subcode & GTMA_HAVE_STORE) == 0)
2876	flags |= PR_READONLY;
2877	if (inst_edge && !(subcode & GTMA_HAS_NO_INSTRUMENTATION))
2878	flags |= PR_INSTRUMENTEDCODE;
2879	if (uninst_edge)
2880	flags |= PR_UNINSTRUMENTEDCODE;
2881	if (subcode & GTMA_IS_OUTER)
2882	region->original_transaction_was_outer = true;
2883	tree t = build_int_cst (tm_state_type, flags);
2884	gcall *call = gimple_build_call (tm_start, 1, t);
2885	gimple_call_set_lhs (gs: call, lhs: tm_state);
2886	gimple_set_location (g: call, location: gimple_location (g: region->transaction_stmt));
2887
2888	// Replace the GIMPLE_TRANSACTION with the call to BUILT_IN_TM_START.
2889	gimple_stmt_iterator gsi = gsi_last_bb (bb: transaction_bb);
2890	gcc_assert (gsi_stmt (gsi) == region->transaction_stmt);
2891	gsi_insert_before (&gsi, call, GSI_SAME_STMT);
2892	gsi_remove (&gsi, true);
2893	region->transaction_stmt = call;
2894	}
2895
2896	// Generate log saves.
2897	if (!tm_log_save_addresses.is_empty ())
2898	tm_log_emit_saves (entry_block: region->entry_block, bb: transaction_bb);
2899
2900	// In the beginning, we've no tests to perform on transaction restart.
2901	// Note that after this point, transaction_bb becomes the "most recent
2902	// block containing tests for the transaction".
2903	region->restart_block = region->entry_block;
2904
2905	// Generate log restores.
2906	if (!tm_log_save_addresses.is_empty ())
2907	{
2908	basic_block test_bb = create_empty_bb (transaction_bb);
2909	basic_block code_bb = create_empty_bb (test_bb);
2910	basic_block join_bb = create_empty_bb (code_bb);
2911	add_bb_to_loop (test_bb, transaction_bb->loop_father);
2912	add_bb_to_loop (code_bb, transaction_bb->loop_father);
2913	add_bb_to_loop (join_bb, transaction_bb->loop_father);
2914	if (region->restart_block == region->entry_block)
2915	region->restart_block = test_bb;
2916
2917	tree t1 = create_tmp_reg (tm_state_type);
2918	tree t2 = build_int_cst (tm_state_type, A_RESTORELIVEVARIABLES);
2919	gimple *stmt = gimple_build_assign (t1, BIT_AND_EXPR, tm_state, t2);
2920	gimple_stmt_iterator gsi = gsi_last_bb (bb: test_bb);
2921	gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
2922
2923	t2 = build_int_cst (tm_state_type, 0);
2924	stmt = gimple_build_cond (NE_EXPR, t1, t2, NULL, NULL);
2925	gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
2926
2927	tm_log_emit_restores (entry_block: region->entry_block, bb: code_bb);
2928
2929	edge ei = make_edge (transaction_bb, test_bb, EDGE_FALLTHRU);
2930	edge et = make_edge (test_bb, code_bb, EDGE_TRUE_VALUE);
2931	edge ef = make_edge (test_bb, join_bb, EDGE_FALSE_VALUE);
2932	redirect_edge_pred (fallthru_edge, join_bb);
2933
2934	join_bb->count = test_bb->count = transaction_bb->count;
2935
2936	ei->probability = profile_probability::always ();
2937	et->probability = profile_probability::likely ();
2938	ef->probability = profile_probability::unlikely ();
2939
2940	code_bb->count = et->count ();
2941
2942	transaction_bb = join_bb;
2943	}
2944
2945	// If we have an ABORT edge, create a test to perform the abort.
2946	if (abort_edge)
2947	{
2948	basic_block test_bb = create_empty_bb (transaction_bb);
2949	add_bb_to_loop (test_bb, transaction_bb->loop_father);
2950	if (region->restart_block == region->entry_block)
2951	region->restart_block = test_bb;
2952
2953	tree t1 = create_tmp_reg (tm_state_type);
2954	tree t2 = build_int_cst (tm_state_type, A_ABORTTRANSACTION);
2955	gimple *stmt = gimple_build_assign (t1, BIT_AND_EXPR, tm_state, t2);
2956	gimple_stmt_iterator gsi = gsi_last_bb (bb: test_bb);
2957	gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
2958
2959	t2 = build_int_cst (tm_state_type, 0);
2960	stmt = gimple_build_cond (NE_EXPR, t1, t2, NULL, NULL);
2961	gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
2962
2963	edge ei = make_edge (transaction_bb, test_bb, EDGE_FALLTHRU);
2964	test_bb->count = transaction_bb->count;
2965	ei->probability = profile_probability::always ();
2966
2967	// Not abort edge. If both are live, chose one at random as we'll
2968	// we'll be fixing that up below.
2969	redirect_edge_pred (fallthru_edge, test_bb);
2970	fallthru_edge->flags = EDGE_FALSE_VALUE;
2971	fallthru_edge->probability = profile_probability::very_likely ();
2972
2973	// Abort/over edge.
2974	redirect_edge_pred (abort_edge, test_bb);
2975	abort_edge->flags = EDGE_TRUE_VALUE;
2976	abort_edge->probability = profile_probability::unlikely ();
2977
2978	transaction_bb = test_bb;
2979	}
2980
2981	// If we have both instrumented and uninstrumented code paths, select one.
2982	if (inst_edge && uninst_edge)
2983	{
2984	basic_block test_bb = create_empty_bb (transaction_bb);
2985	add_bb_to_loop (test_bb, transaction_bb->loop_father);
2986	if (region->restart_block == region->entry_block)
2987	region->restart_block = test_bb;
2988
2989	tree t1 = create_tmp_reg (tm_state_type);
2990	tree t2 = build_int_cst (tm_state_type, A_RUNUNINSTRUMENTEDCODE);
2991
2992	gimple *stmt = gimple_build_assign (t1, BIT_AND_EXPR, tm_state, t2);
2993	gimple_stmt_iterator gsi = gsi_last_bb (bb: test_bb);
2994	gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
2995
2996	t2 = build_int_cst (tm_state_type, 0);
2997	stmt = gimple_build_cond (NE_EXPR, t1, t2, NULL, NULL);
2998	gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
2999
3000	// Create the edge into test_bb first, as we want to copy values
3001	// out of the fallthru edge.
3002	edge e = make_edge (transaction_bb, test_bb, fallthru_edge->flags);
3003	e->probability = fallthru_edge->probability;
3004	test_bb->count = fallthru_edge->count ();
3005
3006	// Now update the edges to the inst/uninist implementations.
3007	// For now assume that the paths are equally likely. When using HTM,
3008	// we'll try the uninst path first and fallback to inst path if htm
3009	// buffers are exceeded. Without HTM we start with the inst path and
3010	// use the uninst path when falling back to serial mode.
3011	redirect_edge_pred (inst_edge, test_bb);
3012	inst_edge->flags = EDGE_FALSE_VALUE;
3013	inst_edge->probability = profile_probability::even ();
3014
3015	redirect_edge_pred (uninst_edge, test_bb);
3016	uninst_edge->flags = EDGE_TRUE_VALUE;
3017	uninst_edge->probability = profile_probability::even ();
3018	}
3019
3020	// If we have no previous special cases, and we have PHIs at the beginning
3021	// of the atomic region, this means we have a loop at the beginning of the
3022	// atomic region that shares the first block. This can cause problems with
3023	// the transaction restart abnormal edges to be added in the tm_edges pass.
3024	// Solve this by adding a new empty block to receive the abnormal edges.
3025	if (region->restart_block == region->entry_block
3026	&& phi_nodes (bb: region->entry_block))
3027	{
3028	basic_block empty_bb = create_empty_bb (transaction_bb);
3029	region->restart_block = empty_bb;
3030	add_bb_to_loop (empty_bb, transaction_bb->loop_father);
3031
3032	redirect_edge_pred (fallthru_edge, empty_bb);
3033	make_edge (transaction_bb, empty_bb, EDGE_FALLTHRU);
3034	}
3035
3036	return NULL;
3037	}
3038
3039	/* Generate the temporary to be used for the return value of
3040	BUILT_IN_TM_START. */
3041
3042	static void *
3043	generate_tm_state (struct tm_region *region, void *data ATTRIBUTE_UNUSED)
3044	{
3045	tree tm_start = builtin_decl_explicit (fncode: BUILT_IN_TM_START);
3046	region->tm_state =
3047	create_tmp_reg (TREE_TYPE (TREE_TYPE (tm_start)), "tm_state");
3048
3049	// Reset the subcode, post optimizations. We'll fill this in
3050	// again as we process blocks.
3051	if (region->exit_blocks)
3052	{
3053	gtransaction *transaction_stmt = region->get_transaction_stmt ();
3054	unsigned int subcode = gimple_transaction_subcode (transaction_stmt);
3055
3056	if (subcode & GTMA_DOES_GO_IRREVOCABLE)
3057	subcode &= (GTMA_DECLARATION_MASK | GTMA_DOES_GO_IRREVOCABLE
3058	| GTMA_MAY_ENTER_IRREVOCABLE
3059	| GTMA_HAS_NO_INSTRUMENTATION);
3060	else
3061	subcode &= GTMA_DECLARATION_MASK;
3062	gimple_transaction_set_subcode (transaction_stmt, subcode);
3063	}
3064
3065	return NULL;
3066	}
3067
3068	// Propagate flags from inner transactions outwards.
3069	static void
3070	propagate_tm_flags_out (struct tm_region *region)
3071	{
3072	if (region == NULL)
3073	return;
3074	propagate_tm_flags_out (region: region->inner);
3075
3076	if (region->outer && region->outer->transaction_stmt)
3077	{
3078	unsigned s
3079	= gimple_transaction_subcode (transaction_stmt: region->get_transaction_stmt ());
3080	s &= (GTMA_HAVE_ABORT | GTMA_HAVE_LOAD | GTMA_HAVE_STORE
3081	| GTMA_MAY_ENTER_IRREVOCABLE);
3082	s |= gimple_transaction_subcode (transaction_stmt: region->outer->get_transaction_stmt ());
3083	gimple_transaction_set_subcode (transaction_stmt: region->outer->get_transaction_stmt (),
3084	subcode: s);
3085	}
3086
3087	propagate_tm_flags_out (region: region->next);
3088	}
3089
3090	/* Entry point to the MARK phase of TM expansion. Here we replace
3091	transactional memory statements with calls to builtins, and function
3092	calls with their transactional clones (if available). But we don't
3093	yet lower GIMPLE_TRANSACTION or add the transaction restart back-edges. */
3094
3095	static unsigned int
3096	execute_tm_mark (void)
3097	{
3098	pending_edge_inserts_p = false;
3099
3100	expand_regions (all_tm_regions, callback: generate_tm_state, NULL,
3101	/*traverse_clones=*/true);
3102
3103	tm_log_init ();
3104
3105	vec<tm_region *> bb_regions
3106	= get_bb_regions_instrumented (/*traverse_clones=*/true,
3107	/*include_uninstrumented_p=*/false);
3108	struct tm_region *r;
3109	unsigned i;
3110
3111	// Expand memory operations into calls into the runtime.
3112	// This collects log entries as well.
3113	FOR_EACH_VEC_ELT (bb_regions, i, r)
3114	{
3115	if (r != NULL)
3116	{
3117	if (r->transaction_stmt)
3118	{
3119	unsigned sub
3120	= gimple_transaction_subcode (transaction_stmt: r->get_transaction_stmt ());
3121
3122	/* If we're sure to go irrevocable, there won't be
3123	anything to expand, since the run-time will go
3124	irrevocable right away. */
3125	if (sub & GTMA_DOES_GO_IRREVOCABLE
3126	&& sub & GTMA_MAY_ENTER_IRREVOCABLE)
3127	continue;
3128	}
3129	expand_block_tm (region: r, BASIC_BLOCK_FOR_FN (cfun, i));
3130	}
3131	}
3132
3133	bb_regions.release ();
3134
3135	// Propagate flags from inner transactions outwards.
3136	propagate_tm_flags_out (region: all_tm_regions);
3137
3138	// Expand GIMPLE_TRANSACTIONs into calls into the runtime.
3139	expand_regions (all_tm_regions, callback: expand_transaction, NULL,
3140	/*traverse_clones=*/false);
3141
3142	tm_log_emit ();
3143	tm_log_delete ();
3144
3145	if (pending_edge_inserts_p)
3146	gsi_commit_edge_inserts ();
3147	free_dominance_info (CDI_DOMINATORS);
3148	return 0;
3149	}
3150
3151	namespace {
3152
3153	const pass_data pass_data_tm_mark =
3154	{
3155	.type: GIMPLE_PASS, /* type */
3156	.name: "tmmark", /* name */
3157	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
3158	.tv_id: TV_TRANS_MEM, /* tv_id */
3159	.properties_required: ( PROP_ssa | PROP_cfg ), /* properties_required */
3160	.properties_provided: 0, /* properties_provided */
3161	.properties_destroyed: 0, /* properties_destroyed */
3162	.todo_flags_start: 0, /* todo_flags_start */
3163	TODO_update_ssa, /* todo_flags_finish */
3164	};
3165
3166	class pass_tm_mark : public gimple_opt_pass
3167	{
3168	public:
3169	pass_tm_mark (gcc::context *ctxt)
3170	: gimple_opt_pass (pass_data_tm_mark, ctxt)
3171	{}
3172
3173	/* opt_pass methods: */
3174	unsigned int execute (function *) final override
3175	{
3176	return execute_tm_mark ();
3177	}
3178
3179	}; // class pass_tm_mark
3180
3181	} // anon namespace
3182
3183	gimple_opt_pass *
3184	make_pass_tm_mark (gcc::context *ctxt)
3185	{
3186	return new pass_tm_mark (ctxt);
3187	}
3188
3189
3190	/* Create an abnormal edge from STMT at iter, splitting the block
3191	as necessary. Adjust *PNEXT as needed for the split block. */
3192
3193	static inline void
3194	split_bb_make_tm_edge (gimple *stmt, basic_block dest_bb,
3195	gimple_stmt_iterator iter, gimple_stmt_iterator *pnext)
3196	{
3197	basic_block bb = gimple_bb (g: stmt);
3198	if (!gsi_one_before_end_p (i: iter))
3199	{
3200	edge e = split_block (bb, stmt);
3201	*pnext = gsi_start_bb (bb: e->dest);
3202	}
3203	edge e = make_edge (bb, dest_bb, EDGE_ABNORMAL);
3204	if (e)
3205	e->probability = profile_probability::guessed_never ();
3206
3207	// Record the need for the edge for the benefit of the rtl passes.
3208	if (cfun->gimple_df->tm_restart == NULL)
3209	cfun->gimple_df->tm_restart
3210	= hash_table<tm_restart_hasher>::create_ggc (n: 31);
3211
3212	struct tm_restart_node dummy;
3213	dummy.stmt = stmt;
3214	dummy.label_or_list = gimple_block_label (dest_bb);
3215
3216	tm_restart_node **slot = cfun->gimple_df->tm_restart->find_slot (value: &dummy,
3217	insert: INSERT);
3218	struct tm_restart_node *n = *slot;
3219	if (n == NULL)
3220	{
3221	*slot = n = ggc_alloc<tm_restart_node> ();
3222	*n = dummy;
3223	}
3224	else
3225	{
3226	tree old = n->label_or_list;
3227	if (TREE_CODE (old) == LABEL_DECL)
3228	old = tree_cons (NULL, old, NULL);
3229	n->label_or_list = tree_cons (NULL, dummy.label_or_list, old);
3230	}
3231	}
3232
3233	/* Split block BB as necessary for every builtin function we added, and
3234	wire up the abnormal back edges implied by the transaction restart. */
3235
3236	static void
3237	expand_block_edges (struct tm_region *const region, basic_block bb)
3238	{
3239	gimple_stmt_iterator gsi, next_gsi;
3240
3241	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi = next_gsi)
3242	{
3243	gimple *stmt = gsi_stmt (i: gsi);
3244	gcall *call_stmt;
3245
3246	next_gsi = gsi;
3247	gsi_next (i: &next_gsi);
3248
3249	// ??? Shouldn't we split for any non-pure, non-irrevocable function?
3250	call_stmt = dyn_cast <gcall *> (p: stmt);
3251	if ((!call_stmt)
3252	|| (gimple_call_flags (call_stmt) & ECF_TM_BUILTIN) == 0)
3253	continue;
3254
3255	if (gimple_call_builtin_p (call_stmt, BUILT_IN_TM_ABORT))
3256	{
3257	// If we have a ``_transaction_cancel [[outer]]'', there is only
3258	// one abnormal edge: to the transaction marked OUTER.
3259	// All compiler-generated instances of BUILT_IN_TM_ABORT have a
3260	// constant argument, which we can examine here. Users invoking
3261	// TM_ABORT directly get what they deserve.
3262	tree arg = gimple_call_arg (gs: call_stmt, index: 0);
3263	if (TREE_CODE (arg) == INTEGER_CST
3264	&& (TREE_INT_CST_LOW (arg) & AR_OUTERABORT) != 0
3265	&& !decl_is_tm_clone (fndecl: current_function_decl))
3266	{
3267	// Find the GTMA_IS_OUTER transaction.
3268	for (struct tm_region *o = region; o; o = o->outer)
3269	if (o->original_transaction_was_outer)
3270	{
3271	split_bb_make_tm_edge (stmt: call_stmt, dest_bb: o->restart_block,
3272	iter: gsi, pnext: &next_gsi);
3273	break;
3274	}
3275
3276	// Otherwise, the front-end should have semantically checked
3277	// outer aborts, but in either case the target region is not
3278	// within this function.
3279	continue;
3280	}
3281
3282	// Non-outer, TM aborts have an abnormal edge to the inner-most
3283	// transaction, the one being aborted;
3284	split_bb_make_tm_edge (stmt: call_stmt, dest_bb: region->restart_block, iter: gsi,
3285	pnext: &next_gsi);
3286	}
3287
3288	// All TM builtins have an abnormal edge to the outer-most transaction.
3289	// We never restart inner transactions. For tm clones, we know a-priori
3290	// that the outer-most transaction is outside the function.
3291	if (decl_is_tm_clone (fndecl: current_function_decl))
3292	continue;
3293
3294	if (cfun->gimple_df->tm_restart == NULL)
3295	cfun->gimple_df->tm_restart
3296	= hash_table<tm_restart_hasher>::create_ggc (n: 31);
3297
3298	// All TM builtins have an abnormal edge to the outer-most transaction.
3299	// We never restart inner transactions.
3300	for (struct tm_region *o = region; o; o = o->outer)
3301	if (!o->outer)
3302	{
3303	split_bb_make_tm_edge (stmt: call_stmt, dest_bb: o->restart_block, iter: gsi, pnext: &next_gsi);
3304	break;
3305	}
3306
3307	// Delete any tail-call annotation that may have been added.
3308	// The tail-call pass may have mis-identified the commit as being
3309	// a candidate because we had not yet added this restart edge.
3310	gimple_call_set_tail (s: call_stmt, tail_p: false);
3311	}
3312	}
3313
3314	/* Entry point to the final expansion of transactional nodes. */
3315
3316	namespace {
3317
3318	const pass_data pass_data_tm_edges =
3319	{
3320	.type: GIMPLE_PASS, /* type */
3321	.name: "tmedge", /* name */
3322	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
3323	.tv_id: TV_TRANS_MEM, /* tv_id */
3324	.properties_required: ( PROP_ssa | PROP_cfg ), /* properties_required */
3325	.properties_provided: 0, /* properties_provided */
3326	.properties_destroyed: 0, /* properties_destroyed */
3327	.todo_flags_start: 0, /* todo_flags_start */
3328	TODO_update_ssa, /* todo_flags_finish */
3329	};
3330
3331	class pass_tm_edges : public gimple_opt_pass
3332	{
3333	public:
3334	pass_tm_edges (gcc::context *ctxt)
3335	: gimple_opt_pass (pass_data_tm_edges, ctxt)
3336	{}
3337
3338	/* opt_pass methods: */
3339	unsigned int execute (function *) final override;
3340
3341	}; // class pass_tm_edges
3342
3343	unsigned int
3344	pass_tm_edges::execute (function *fun)
3345	{
3346	vec<tm_region *> bb_regions
3347	= get_bb_regions_instrumented (/*traverse_clones=*/false,
3348	/*include_uninstrumented_p=*/true);
3349	struct tm_region *r;
3350	unsigned i;
3351
3352	FOR_EACH_VEC_ELT (bb_regions, i, r)
3353	if (r != NULL)
3354	expand_block_edges (region: r, BASIC_BLOCK_FOR_FN (fun, i));
3355
3356	bb_regions.release ();
3357
3358	/* We've got to release the dominance info now, to indicate that it
3359	must be rebuilt completely. Otherwise we'll crash trying to update
3360	the SSA web in the TODO section following this pass. */
3361	free_dominance_info (CDI_DOMINATORS);
3362	/* We'ge also wrecked loops badly with inserting of abnormal edges. */
3363	loops_state_set (flags: LOOPS_NEED_FIXUP);
3364	bitmap_obstack_release (&tm_obstack);
3365	all_tm_regions = NULL;
3366
3367	return 0;
3368	}
3369
3370	} // anon namespace
3371
3372	gimple_opt_pass *
3373	make_pass_tm_edges (gcc::context *ctxt)
3374	{
3375	return new pass_tm_edges (ctxt);
3376	}
3377
3378	/* Helper function for expand_regions. Expand REGION and recurse to
3379	the inner region. Call CALLBACK on each region. CALLBACK returns
3380	NULL to continue the traversal, otherwise a non-null value which
3381	this function will return as well. TRAVERSE_CLONES is true if we
3382	should traverse transactional clones. */
3383
3384	static void *
3385	expand_regions_1 (struct tm_region *region,
3386	void *(*callback)(struct tm_region *, void *),
3387	void *data,
3388	bool traverse_clones)
3389	{
3390	void *retval = NULL;
3391	if (region->exit_blocks
3392	|| (traverse_clones && decl_is_tm_clone (fndecl: current_function_decl)))
3393	{
3394	retval = callback (region, data);
3395	if (retval)
3396	return retval;
3397	}
3398	if (region->inner)
3399	{
3400	retval = expand_regions (region->inner, callback, data, traverse_clones);
3401	if (retval)
3402	return retval;
3403	}
3404	return retval;
3405	}
3406
3407	/* Traverse the regions enclosed and including REGION. Execute
3408	CALLBACK for each region, passing DATA. CALLBACK returns NULL to
3409	continue the traversal, otherwise a non-null value which this
3410	function will return as well. TRAVERSE_CLONES is true if we should
3411	traverse transactional clones. */
3412
3413	static void *
3414	expand_regions (struct tm_region *region,
3415	void *(*callback)(struct tm_region *, void *),
3416	void *data,
3417	bool traverse_clones)
3418	{
3419	void *retval = NULL;
3420	while (region)
3421	{
3422	retval = expand_regions_1 (region, callback, data, traverse_clones);
3423	if (retval)
3424	return retval;
3425	region = region->next;
3426	}
3427	return retval;
3428	}
3429
3430
3431	/* A unique TM memory operation. */
3432	struct tm_memop
3433	{
3434	/* Unique ID that all memory operations to the same location have. */
3435	unsigned int value_id;
3436	/* Address of load/store. */
3437	tree addr;
3438	};
3439
3440	/* TM memory operation hashtable helpers. */
3441
3442	struct tm_memop_hasher : free_ptr_hash <tm_memop>
3443	{
3444	static inline hashval_t hash (const tm_memop *);
3445	static inline bool equal (const tm_memop *, const tm_memop *);
3446	};
3447
3448	/* Htab support. Return a hash value for a `tm_memop'. */
3449	inline hashval_t
3450	tm_memop_hasher::hash (const tm_memop *mem)
3451	{
3452	tree addr = mem->addr;
3453	/* We drill down to the SSA_NAME/DECL for the hash, but equality is
3454	actually done with operand_equal_p (see tm_memop_eq). */
3455	if (TREE_CODE (addr) == ADDR_EXPR)
3456	addr = TREE_OPERAND (addr, 0);
3457	return iterative_hash_expr (tree: addr, seed: 0);
3458	}
3459
3460	/* Htab support. Return true if two tm_memop's are the same. */
3461	inline bool
3462	tm_memop_hasher::equal (const tm_memop *mem1, const tm_memop *mem2)
3463	{
3464	return operand_equal_p (mem1->addr, mem2->addr, flags: 0);
3465	}
3466
3467	/* Sets for solving data flow equations in the memory optimization pass. */
3468	struct tm_memopt_bitmaps
3469	{
3470	/* Stores available to this BB upon entry. Basically, stores that
3471	dominate this BB. */
3472	bitmap store_avail_in;
3473	/* Stores available at the end of this BB. */
3474	bitmap store_avail_out;
3475	bitmap store_antic_in;
3476	bitmap store_antic_out;
3477	/* Reads available to this BB upon entry. Basically, reads that
3478	dominate this BB. */
3479	bitmap read_avail_in;
3480	/* Reads available at the end of this BB. */
3481	bitmap read_avail_out;
3482	/* Reads performed in this BB. */
3483	bitmap read_local;
3484	/* Writes performed in this BB. */
3485	bitmap store_local;
3486
3487	/* Temporary storage for pass. */
3488	/* Is the current BB in the worklist? */
3489	bool avail_in_worklist_p;
3490	/* Have we visited this BB? */
3491	bool visited_p;
3492	};
3493
3494	static bitmap_obstack tm_memopt_obstack;
3495
3496	/* Unique counter for TM loads and stores. Loads and stores of the
3497	same address get the same ID. */
3498	static unsigned int tm_memopt_value_id;
3499	static hash_table<tm_memop_hasher> *tm_memopt_value_numbers;
3500
3501	#define STORE_AVAIL_IN(BB) \
3502	((struct tm_memopt_bitmaps *) ((BB)->aux))->store_avail_in
3503	#define STORE_AVAIL_OUT(BB) \
3504	((struct tm_memopt_bitmaps *) ((BB)->aux))->store_avail_out
3505	#define STORE_ANTIC_IN(BB) \
3506	((struct tm_memopt_bitmaps *) ((BB)->aux))->store_antic_in
3507	#define STORE_ANTIC_OUT(BB) \
3508	((struct tm_memopt_bitmaps *) ((BB)->aux))->store_antic_out
3509	#define READ_AVAIL_IN(BB) \
3510	((struct tm_memopt_bitmaps *) ((BB)->aux))->read_avail_in
3511	#define READ_AVAIL_OUT(BB) \
3512	((struct tm_memopt_bitmaps *) ((BB)->aux))->read_avail_out
3513	#define READ_LOCAL(BB) \
3514	((struct tm_memopt_bitmaps *) ((BB)->aux))->read_local
3515	#define STORE_LOCAL(BB) \
3516	((struct tm_memopt_bitmaps *) ((BB)->aux))->store_local
3517	#define AVAIL_IN_WORKLIST_P(BB) \
3518	((struct tm_memopt_bitmaps *) ((BB)->aux))->avail_in_worklist_p
3519	#define BB_VISITED_P(BB) \
3520	((struct tm_memopt_bitmaps *) ((BB)->aux))->visited_p
3521
3522	/* Given a TM load/store in STMT, return the value number for the address
3523	it accesses. */
3524
3525	static unsigned int
3526	tm_memopt_value_number (gimple *stmt, enum insert_option op)
3527	{
3528	struct tm_memop tmpmem, *mem;
3529	tm_memop **slot;
3530
3531	gcc_assert (is_tm_load (stmt) || is_tm_store (stmt));
3532	tmpmem.addr = gimple_call_arg (gs: stmt, index: 0);
3533	slot = tm_memopt_value_numbers->find_slot (value: &tmpmem, insert: op);
3534	if (*slot)
3535	mem = *slot;
3536	else if (op == INSERT)
3537	{
3538	mem = XNEW (struct tm_memop);
3539	*slot = mem;
3540	mem->value_id = tm_memopt_value_id++;
3541	mem->addr = tmpmem.addr;
3542	}
3543	else
3544	gcc_unreachable ();
3545	return mem->value_id;
3546	}
3547
3548	/* Accumulate TM memory operations in BB into STORE_LOCAL and READ_LOCAL. */
3549
3550	static void
3551	tm_memopt_accumulate_memops (basic_block bb)
3552	{
3553	gimple_stmt_iterator gsi;
3554
3555	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
3556	{
3557	gimple *stmt = gsi_stmt (i: gsi);
3558	bitmap bits;
3559	unsigned int loc;
3560
3561	if (is_tm_store (stmt))
3562	bits = STORE_LOCAL (bb);
3563	else if (is_tm_load (stmt))
3564	bits = READ_LOCAL (bb);
3565	else
3566	continue;
3567
3568	loc = tm_memopt_value_number (stmt, op: INSERT);
3569	bitmap_set_bit (bits, loc);
3570	if (dump_file)
3571	{
3572	fprintf (stream: dump_file, format: "TM memopt (%s): value num=%d, BB=%d, addr=",
3573	is_tm_load (stmt) ? "LOAD" : "STORE", loc,
3574	gimple_bb (g: stmt)->index);
3575	print_generic_expr (dump_file, gimple_call_arg (gs: stmt, index: 0));
3576	fprintf (stream: dump_file, format: "\n");
3577	}
3578	}
3579	}
3580
3581	/* Prettily dump one of the memopt sets. BITS is the bitmap to dump. */
3582
3583	static void
3584	dump_tm_memopt_set (const char *set_name, bitmap bits)
3585	{
3586	unsigned i;
3587	bitmap_iterator bi;
3588	const char *comma = "";
3589
3590	fprintf (stream: dump_file, format: "TM memopt: %s: [", set_name);
3591	EXECUTE_IF_SET_IN_BITMAP (bits, 0, i, bi)
3592	{
3593	hash_table<tm_memop_hasher>::iterator hi;
3594	struct tm_memop *mem = NULL;
3595
3596	/* Yeah, yeah, yeah. Whatever. This is just for debugging. */
3597	FOR_EACH_HASH_TABLE_ELEMENT (*tm_memopt_value_numbers, mem, tm_memop_t, hi)
3598	if (mem->value_id == i)
3599	break;
3600	gcc_assert (mem->value_id == i);
3601	fprintf (stream: dump_file, format: "%s", comma);
3602	comma = ", ";
3603	print_generic_expr (dump_file, mem->addr);
3604	}
3605	fprintf (stream: dump_file, format: "]\n");
3606	}
3607
3608	/* Prettily dump all of the memopt sets in BLOCKS. */
3609
3610	static void
3611	dump_tm_memopt_sets (vec<basic_block> blocks)
3612	{
3613	size_t i;
3614	basic_block bb;
3615
3616	for (i = 0; blocks.iterate (ix: i, ptr: &bb); ++i)
3617	{
3618	fprintf (stream: dump_file, format: "------------BB %d---------\n", bb->index);
3619	dump_tm_memopt_set (set_name: "STORE_LOCAL", STORE_LOCAL (bb));
3620	dump_tm_memopt_set (set_name: "READ_LOCAL", READ_LOCAL (bb));
3621	dump_tm_memopt_set (set_name: "STORE_AVAIL_IN", STORE_AVAIL_IN (bb));
3622	dump_tm_memopt_set (set_name: "STORE_AVAIL_OUT", STORE_AVAIL_OUT (bb));
3623	dump_tm_memopt_set (set_name: "READ_AVAIL_IN", READ_AVAIL_IN (bb));
3624	dump_tm_memopt_set (set_name: "READ_AVAIL_OUT", READ_AVAIL_OUT (bb));
3625	}
3626	}
3627
3628	/* Compute {STORE,READ}_AVAIL_IN for the basic block BB. */
3629
3630	static void
3631	tm_memopt_compute_avin (basic_block bb)
3632	{
3633	edge e;
3634	unsigned ix;
3635
3636	/* Seed with the AVOUT of any predecessor. */
3637	for (ix = 0; ix < EDGE_COUNT (bb->preds); ix++)
3638	{
3639	e = EDGE_PRED (bb, ix);
3640	/* Make sure we have already visited this BB, and is thus
3641	initialized.
3642
3643	If e->src->aux is NULL, this predecessor is actually on an
3644	enclosing transaction. We only care about the current
3645	transaction, so ignore it. */
3646	if (e->src->aux && BB_VISITED_P (e->src))
3647	{
3648	bitmap_copy (STORE_AVAIL_IN (bb), STORE_AVAIL_OUT (e->src));
3649	bitmap_copy (READ_AVAIL_IN (bb), READ_AVAIL_OUT (e->src));
3650	break;
3651	}
3652	}
3653
3654	for (; ix < EDGE_COUNT (bb->preds); ix++)
3655	{
3656	e = EDGE_PRED (bb, ix);
3657	if (e->src->aux && BB_VISITED_P (e->src))
3658	{
3659	bitmap_and_into (STORE_AVAIL_IN (bb), STORE_AVAIL_OUT (e->src));
3660	bitmap_and_into (READ_AVAIL_IN (bb), READ_AVAIL_OUT (e->src));
3661	}
3662	}
3663
3664	BB_VISITED_P (bb) = true;
3665	}
3666
3667	/* Compute the STORE_ANTIC_IN for the basic block BB. */
3668
3669	static void
3670	tm_memopt_compute_antin (basic_block bb)
3671	{
3672	edge e;
3673	unsigned ix;
3674
3675	/* Seed with the ANTIC_OUT of any successor. */
3676	for (ix = 0; ix < EDGE_COUNT (bb->succs); ix++)
3677	{
3678	e = EDGE_SUCC (bb, ix);
3679	/* Make sure we have already visited this BB, and is thus
3680	initialized. */
3681	if (BB_VISITED_P (e->dest))
3682	{
3683	bitmap_copy (STORE_ANTIC_IN (bb), STORE_ANTIC_OUT (e->dest));
3684	break;
3685	}
3686	}
3687
3688	for (; ix < EDGE_COUNT (bb->succs); ix++)
3689	{
3690	e = EDGE_SUCC (bb, ix);
3691	if (BB_VISITED_P (e->dest))
3692	bitmap_and_into (STORE_ANTIC_IN (bb), STORE_ANTIC_OUT (e->dest));
3693	}
3694
3695	BB_VISITED_P (bb) = true;
3696	}
3697
3698	/* Compute the AVAIL sets for every basic block in BLOCKS.
3699
3700	We compute {STORE,READ}_AVAIL_{OUT,IN} as follows:
3701
3702	AVAIL_OUT[bb] = union (AVAIL_IN[bb], LOCAL[bb])
3703	AVAIL_IN[bb] = intersect (AVAIL_OUT[predecessors])
3704
3705	This is basically what we do in lcm's compute_available(), but here
3706	we calculate two sets of sets (one for STOREs and one for READs),
3707	and we work on a region instead of the entire CFG.
3708
3709	REGION is the TM region.
3710	BLOCKS are the basic blocks in the region. */
3711
3712	static void
3713	tm_memopt_compute_available (struct tm_region *region,
3714	vec<basic_block> blocks)
3715	{
3716	edge e;
3717	basic_block *worklist, *qin, *qout, *qend, bb;
3718	unsigned int qlen, i;
3719	edge_iterator ei;
3720	bool changed;
3721
3722	/* Allocate a worklist array/queue. Entries are only added to the
3723	list if they were not already on the list. So the size is
3724	bounded by the number of basic blocks in the region. */
3725	gcc_assert (!blocks.is_empty ());
3726	qlen = blocks.length () - 1;
3727	qin = qout = worklist = XNEWVEC (basic_block, qlen);
3728
3729	/* Put every block in the region on the worklist. */
3730	for (i = 0; blocks.iterate (ix: i, ptr: &bb); ++i)
3731	{
3732	/* Seed AVAIL_OUT with the LOCAL set. */
3733	bitmap_ior_into (STORE_AVAIL_OUT (bb), STORE_LOCAL (bb));
3734	bitmap_ior_into (READ_AVAIL_OUT (bb), READ_LOCAL (bb));
3735
3736	AVAIL_IN_WORKLIST_P (bb) = true;
3737	/* No need to insert the entry block, since it has an AVIN of
3738	null, and an AVOUT that has already been seeded in. */
3739	if (bb != region->entry_block)
3740	*qin++ = bb;
3741	}
3742
3743	/* The entry block has been initialized with the local sets. */
3744	BB_VISITED_P (region->entry_block) = true;
3745
3746	qin = worklist;
3747	qend = &worklist[qlen];
3748
3749	/* Iterate until the worklist is empty. */
3750	while (qlen)
3751	{
3752	/* Take the first entry off the worklist. */
3753	bb = *qout++;
3754	qlen--;
3755
3756	if (qout >= qend)
3757	qout = worklist;
3758
3759	/* This block can be added to the worklist again if necessary. */
3760	AVAIL_IN_WORKLIST_P (bb) = false;
3761	tm_memopt_compute_avin (bb);
3762
3763	/* Note: We do not add the LOCAL sets here because we already
3764	seeded the AVAIL_OUT sets with them. */
3765	changed = bitmap_ior_into (STORE_AVAIL_OUT (bb), STORE_AVAIL_IN (bb));
3766	changed |= bitmap_ior_into (READ_AVAIL_OUT (bb), READ_AVAIL_IN (bb));
3767	if (changed
3768	&& (region->exit_blocks == NULL
3769	|| !bitmap_bit_p (region->exit_blocks, bb->index)))
3770	/* If the out state of this block changed, then we need to add
3771	its successors to the worklist if they are not already in. */
3772	FOR_EACH_EDGE (e, ei, bb->succs)
3773	if (!AVAIL_IN_WORKLIST_P (e->dest)
3774	&& e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
3775	{
3776	*qin++ = e->dest;
3777	AVAIL_IN_WORKLIST_P (e->dest) = true;
3778	qlen++;
3779
3780	if (qin >= qend)
3781	qin = worklist;
3782	}
3783	}
3784
3785	free (ptr: worklist);
3786
3787	if (dump_file)
3788	dump_tm_memopt_sets (blocks);
3789	}
3790
3791	/* Compute ANTIC sets for every basic block in BLOCKS.
3792
3793	We compute STORE_ANTIC_OUT as follows:
3794
3795	STORE_ANTIC_OUT[bb] = union(STORE_ANTIC_IN[bb], STORE_LOCAL[bb])
3796	STORE_ANTIC_IN[bb] = intersect(STORE_ANTIC_OUT[successors])
3797
3798	REGION is the TM region.
3799	BLOCKS are the basic blocks in the region. */
3800
3801	static void
3802	tm_memopt_compute_antic (struct tm_region *region,
3803	vec<basic_block> blocks)
3804	{
3805	edge e;
3806	basic_block *worklist, *qin, *qout, *qend, bb;
3807	unsigned int qlen;
3808	int i;
3809	edge_iterator ei;
3810
3811	/* Allocate a worklist array/queue. Entries are only added to the
3812	list if they were not already on the list. So the size is
3813	bounded by the number of basic blocks in the region. */
3814	qin = qout = worklist = XNEWVEC (basic_block, blocks.length ());
3815
3816	for (qlen = 0, i = blocks.length () - 1; i >= 0; --i)
3817	{
3818	bb = blocks[i];
3819
3820	/* Seed ANTIC_OUT with the LOCAL set. */
3821	bitmap_ior_into (STORE_ANTIC_OUT (bb), STORE_LOCAL (bb));
3822
3823	/* Put every block in the region on the worklist. */
3824	AVAIL_IN_WORKLIST_P (bb) = true;
3825	/* No need to insert exit blocks, since their ANTIC_IN is NULL,
3826	and their ANTIC_OUT has already been seeded in. */
3827	if (region->exit_blocks
3828	&& !bitmap_bit_p (region->exit_blocks, bb->index))
3829	{
3830	qlen++;
3831	*qin++ = bb;
3832	}
3833	}
3834
3835	/* The exit blocks have been initialized with the local sets. */
3836	if (region->exit_blocks)
3837	{
3838	unsigned int i;
3839	bitmap_iterator bi;
3840	EXECUTE_IF_SET_IN_BITMAP (region->exit_blocks, 0, i, bi)
3841	BB_VISITED_P (BASIC_BLOCK_FOR_FN (cfun, i)) = true;
3842	}
3843
3844	qin = worklist;
3845	qend = &worklist[qlen];
3846
3847	/* Iterate until the worklist is empty. */
3848	while (qlen)
3849	{
3850	/* Take the first entry off the worklist. */
3851	bb = *qout++;
3852	qlen--;
3853
3854	if (qout >= qend)
3855	qout = worklist;
3856
3857	/* This block can be added to the worklist again if necessary. */
3858	AVAIL_IN_WORKLIST_P (bb) = false;
3859	tm_memopt_compute_antin (bb);
3860
3861	/* Note: We do not add the LOCAL sets here because we already
3862	seeded the ANTIC_OUT sets with them. */
3863	if (bitmap_ior_into (STORE_ANTIC_OUT (bb), STORE_ANTIC_IN (bb))
3864	&& bb != region->entry_block)
3865	/* If the out state of this block changed, then we need to add
3866	its predecessors to the worklist if they are not already in. */
3867	FOR_EACH_EDGE (e, ei, bb->preds)
3868	if (!AVAIL_IN_WORKLIST_P (e->src))
3869	{
3870	*qin++ = e->src;
3871	AVAIL_IN_WORKLIST_P (e->src) = true;
3872	qlen++;
3873
3874	if (qin >= qend)
3875	qin = worklist;
3876	}
3877	}
3878
3879	free (ptr: worklist);
3880
3881	if (dump_file)
3882	dump_tm_memopt_sets (blocks);
3883	}
3884
3885	/* Offsets of load variants from TM_LOAD. For example,
3886	BUILT_IN_TM_LOAD_RAR* is an offset of 1 from BUILT_IN_TM_LOAD*.
3887	See gtm-builtins.def. */
3888	#define TRANSFORM_RAR 1
3889	#define TRANSFORM_RAW 2
3890	#define TRANSFORM_RFW 3
3891	/* Offsets of store variants from TM_STORE. */
3892	#define TRANSFORM_WAR 1
3893	#define TRANSFORM_WAW 2
3894
3895	/* Inform about a load/store optimization. */
3896
3897	static void
3898	dump_tm_memopt_transform (gimple *stmt)
3899	{
3900	if (dump_file)
3901	{
3902	fprintf (stream: dump_file, format: "TM memopt: transforming: ");
3903	print_gimple_stmt (dump_file, stmt, 0);
3904	fprintf (stream: dump_file, format: "\n");
3905	}
3906	}
3907
3908	/* Perform a read/write optimization. Replaces the TM builtin in STMT
3909	by a builtin that is OFFSET entries down in the builtins table in
3910	gtm-builtins.def. */
3911
3912	static void
3913	tm_memopt_transform_stmt (unsigned int offset,
3914	gcall *stmt,
3915	gimple_stmt_iterator *gsi)
3916	{
3917	tree fn = gimple_call_fn (gs: stmt);
3918	gcc_assert (TREE_CODE (fn) == ADDR_EXPR);
3919	TREE_OPERAND (fn, 0)
3920	= builtin_decl_explicit (fncode: (enum built_in_function)
3921	(DECL_FUNCTION_CODE (TREE_OPERAND (fn, 0))
3922	+ offset));
3923	gimple_call_set_fn (gs: stmt, fn);
3924	gsi_replace (gsi, stmt, true);
3925	dump_tm_memopt_transform (stmt);
3926	}
3927
3928	/* Perform the actual TM memory optimization transformations in the
3929	basic blocks in BLOCKS. */
3930
3931	static void
3932	tm_memopt_transform_blocks (vec<basic_block> blocks)
3933	{
3934	size_t i;
3935	basic_block bb;
3936	gimple_stmt_iterator gsi;
3937
3938	for (i = 0; blocks.iterate (ix: i, ptr: &bb); ++i)
3939	{
3940	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
3941	{
3942	gimple *stmt = gsi_stmt (i: gsi);
3943	bitmap read_avail = READ_AVAIL_IN (bb);
3944	bitmap store_avail = STORE_AVAIL_IN (bb);
3945	bitmap store_antic = STORE_ANTIC_OUT (bb);
3946	unsigned int loc;
3947
3948	if (is_tm_simple_load (stmt))
3949	{
3950	gcall *call_stmt = as_a <gcall *> (p: stmt);
3951	loc = tm_memopt_value_number (stmt, op: NO_INSERT);
3952	if (store_avail && bitmap_bit_p (store_avail, loc))
3953	tm_memopt_transform_stmt (TRANSFORM_RAW, stmt: call_stmt, gsi: &gsi);
3954	else if (store_antic && bitmap_bit_p (store_antic, loc))
3955	{
3956	tm_memopt_transform_stmt (TRANSFORM_RFW, stmt: call_stmt, gsi: &gsi);
3957	bitmap_set_bit (store_avail, loc);
3958	}
3959	else if (read_avail && bitmap_bit_p (read_avail, loc))
3960	tm_memopt_transform_stmt (TRANSFORM_RAR, stmt: call_stmt, gsi: &gsi);
3961	else
3962	bitmap_set_bit (read_avail, loc);
3963	}
3964	else if (is_tm_simple_store (stmt))
3965	{
3966	gcall *call_stmt = as_a <gcall *> (p: stmt);
3967	loc = tm_memopt_value_number (stmt, op: NO_INSERT);
3968	if (store_avail && bitmap_bit_p (store_avail, loc))
3969	tm_memopt_transform_stmt (TRANSFORM_WAW, stmt: call_stmt, gsi: &gsi);
3970	else
3971	{
3972	if (read_avail && bitmap_bit_p (read_avail, loc))
3973	tm_memopt_transform_stmt (TRANSFORM_WAR, stmt: call_stmt, gsi: &gsi);
3974	bitmap_set_bit (store_avail, loc);
3975	}
3976	}
3977	}
3978	}
3979	}
3980
3981	/* Return a new set of bitmaps for a BB. */
3982
3983	static struct tm_memopt_bitmaps *
3984	tm_memopt_init_sets (void)
3985	{
3986	struct tm_memopt_bitmaps *b
3987	= XOBNEW (&tm_memopt_obstack.obstack, struct tm_memopt_bitmaps);
3988	b->store_avail_in = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
3989	b->store_avail_out = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
3990	b->store_antic_in = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
3991	b->store_antic_out = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
3992	b->store_avail_out = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
3993	b->read_avail_in = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
3994	b->read_avail_out = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
3995	b->read_local = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
3996	b->store_local = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
3997	return b;
3998	}
3999
4000	/* Free sets computed for each BB. */
4001
4002	static void
4003	tm_memopt_free_sets (vec<basic_block> blocks)
4004	{
4005	size_t i;
4006	basic_block bb;
4007
4008	for (i = 0; blocks.iterate (ix: i, ptr: &bb); ++i)
4009	bb->aux = NULL;
4010	}
4011
4012	/* Clear the visited bit for every basic block in BLOCKS. */
4013
4014	static void
4015	tm_memopt_clear_visited (vec<basic_block> blocks)
4016	{
4017	size_t i;
4018	basic_block bb;
4019
4020	for (i = 0; blocks.iterate (ix: i, ptr: &bb); ++i)
4021	BB_VISITED_P (bb) = false;
4022	}
4023
4024	/* Replace TM load/stores with hints for the runtime. We handle
4025	things like read-after-write, write-after-read, read-after-read,
4026	read-for-write, etc. */
4027
4028	static unsigned int
4029	execute_tm_memopt (void)
4030	{
4031	struct tm_region *region;
4032	vec<basic_block> bbs;
4033
4034	tm_memopt_value_id = 0;
4035	tm_memopt_value_numbers = new hash_table<tm_memop_hasher> (10);
4036
4037	for (region = all_tm_regions; region; region = region->next)
4038	{
4039	/* All the TM stores/loads in the current region. */
4040	size_t i;
4041	basic_block bb;
4042
4043	bitmap_obstack_initialize (&tm_memopt_obstack);
4044
4045	/* Save all BBs for the current region. */
4046	bbs = get_tm_region_blocks (entry_block: region->entry_block,
4047	exit_blocks: region->exit_blocks,
4048	irr_blocks: region->irr_blocks,
4049	NULL,
4050	stop_at_irrevocable_p: false);
4051
4052	/* Collect all the memory operations. */
4053	for (i = 0; bbs.iterate (ix: i, ptr: &bb); ++i)
4054	{
4055	bb->aux = tm_memopt_init_sets ();
4056	tm_memopt_accumulate_memops (bb);
4057	}
4058
4059	/* Solve data flow equations and transform each block accordingly. */
4060	tm_memopt_clear_visited (blocks: bbs);
4061	tm_memopt_compute_available (region, blocks: bbs);
4062	tm_memopt_clear_visited (blocks: bbs);
4063	tm_memopt_compute_antic (region, blocks: bbs);
4064	tm_memopt_transform_blocks (blocks: bbs);
4065
4066	tm_memopt_free_sets (blocks: bbs);
4067	bbs.release ();
4068	bitmap_obstack_release (&tm_memopt_obstack);
4069	tm_memopt_value_numbers->empty ();
4070	}
4071
4072	delete tm_memopt_value_numbers;
4073	tm_memopt_value_numbers = NULL;
4074	return 0;
4075	}
4076
4077	namespace {
4078
4079	const pass_data pass_data_tm_memopt =
4080	{
4081	.type: GIMPLE_PASS, /* type */
4082	.name: "tmmemopt", /* name */
4083	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
4084	.tv_id: TV_TRANS_MEM, /* tv_id */
4085	.properties_required: ( PROP_ssa | PROP_cfg ), /* properties_required */
4086	.properties_provided: 0, /* properties_provided */
4087	.properties_destroyed: 0, /* properties_destroyed */
4088	.todo_flags_start: 0, /* todo_flags_start */
4089	.todo_flags_finish: 0, /* todo_flags_finish */
4090	};
4091
4092	class pass_tm_memopt : public gimple_opt_pass
4093	{
4094	public:
4095	pass_tm_memopt (gcc::context *ctxt)
4096	: gimple_opt_pass (pass_data_tm_memopt, ctxt)
4097	{}
4098
4099	/* opt_pass methods: */
4100	bool gate (function *) final override { return flag_tm && optimize > 0; }
4101	unsigned int execute (function *) final override
4102	{
4103	return execute_tm_memopt ();
4104	}
4105
4106	}; // class pass_tm_memopt
4107
4108	} // anon namespace
4109
4110	gimple_opt_pass *
4111	make_pass_tm_memopt (gcc::context *ctxt)
4112	{
4113	return new pass_tm_memopt (ctxt);
4114	}
4115
4116
4117	/* Interprocedual analysis for the creation of transactional clones.
4118	The aim of this pass is to find which functions are referenced in
4119	a non-irrevocable transaction context, and for those over which
4120	we have control (or user directive), create a version of the
4121	function which uses only the transactional interface to reference
4122	protected memories. This analysis proceeds in several steps:
4123
4124	(1) Collect the set of all possible transactional clones:
4125
4126	(a) For all local public functions marked tm_callable, push
4127	it onto the tm_callee queue.
4128
4129	(b) For all local functions, scan for calls in transaction blocks.
4130	Push the caller and callee onto the tm_caller and tm_callee
4131	queues. Count the number of callers for each callee.
4132
4133	(c) For each local function on the callee list, assume we will
4134	create a transactional clone. Push *all* calls onto the
4135	callee queues; count the number of clone callers separately
4136	to the number of original callers.
4137
4138	(2) Propagate irrevocable status up the dominator tree:
4139
4140	(a) Any external function on the callee list that is not marked
4141	tm_callable is irrevocable. Push all callers of such onto
4142	a worklist.
4143
4144	(b) For each function on the worklist, mark each block that
4145	contains an irrevocable call. Use the AND operator to
4146	propagate that mark up the dominator tree.
4147
4148	(c) If we reach the entry block for a possible transactional
4149	clone, then the transactional clone is irrevocable, and
4150	we should not create the clone after all. Push all
4151	callers onto the worklist.
4152
4153	(d) Place tm_irrevocable calls at the beginning of the relevant
4154	blocks. Special case here is the entry block for the entire
4155	transaction region; there we mark it GTMA_DOES_GO_IRREVOCABLE for
4156	the library to begin the region in serial mode. Decrement
4157	the call count for all callees in the irrevocable region.
4158
4159	(3) Create the transactional clones:
4160
4161	Any tm_callee that still has a non-zero call count is cloned.
4162	*/
4163
4164	/* This structure is stored in the AUX field of each cgraph_node. */
4165	struct tm_ipa_cg_data
4166	{
4167	/* The clone of the function that got created. */
4168	struct cgraph_node *clone;
4169
4170	/* The tm regions in the normal function. */
4171	struct tm_region *all_tm_regions;
4172
4173	/* The blocks of the normal/clone functions that contain irrevocable
4174	calls, or blocks that are post-dominated by irrevocable calls. */
4175	bitmap irrevocable_blocks_normal;
4176	bitmap irrevocable_blocks_clone;
4177
4178	/* The blocks of the normal function that are involved in transactions. */
4179	bitmap transaction_blocks_normal;
4180
4181	/* The number of callers to the transactional clone of this function
4182	from normal and transactional clones respectively. */
4183	unsigned tm_callers_normal;
4184	unsigned tm_callers_clone;
4185
4186	/* True if all calls to this function's transactional clone
4187	are irrevocable. Also automatically true if the function
4188	has no transactional clone. */
4189	bool is_irrevocable;
4190
4191	/* Flags indicating the presence of this function in various queues. */
4192	bool in_callee_queue;
4193	bool in_worklist;
4194
4195	/* Flags indicating the kind of scan desired while in the worklist. */
4196	bool want_irr_scan_normal;
4197	};
4198
4199	typedef vec<cgraph_node *> cgraph_node_queue;
4200
4201	/* Return the ipa data associated with NODE, allocating zeroed memory
4202	if necessary. TRAVERSE_ALIASES is true if we must traverse aliases
4203	and set *NODE accordingly. */
4204
4205	static struct tm_ipa_cg_data *
4206	get_cg_data (struct cgraph_node **node, bool traverse_aliases)
4207	{
4208	struct tm_ipa_cg_data *d;
4209
4210	if (traverse_aliases && (*node)->alias)
4211	*node = (*node)->get_alias_target ();
4212
4213	d = (struct tm_ipa_cg_data *) (*node)->aux;
4214
4215	if (d == NULL)
4216	{
4217	d = (struct tm_ipa_cg_data *)
4218	obstack_alloc (&tm_obstack.obstack, sizeof (*d));
4219	(*node)->aux = (void *) d;
4220	memset (s: d, c: 0, n: sizeof (*d));
4221	}
4222
4223	return d;
4224	}
4225
4226	/* Add NODE to the end of QUEUE, unless IN_QUEUE_P indicates that
4227	it is already present. */
4228
4229	static void
4230	maybe_push_queue (struct cgraph_node *node,
4231	cgraph_node_queue *queue_p, bool *in_queue_p)
4232	{
4233	if (!*in_queue_p)
4234	{
4235	*in_queue_p = true;
4236	queue_p->safe_push (obj: node);
4237	}
4238	}
4239
4240	/* A subroutine of ipa_tm_scan_calls_transaction and ipa_tm_scan_calls_clone.
4241	Queue all callees within block BB. */
4242
4243	static void
4244	ipa_tm_scan_calls_block (cgraph_node_queue *callees_p,
4245	basic_block bb, bool for_clone)
4246	{
4247	gimple_stmt_iterator gsi;
4248
4249	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
4250	{
4251	gimple *stmt = gsi_stmt (i: gsi);
4252	if (is_gimple_call (gs: stmt) && !is_tm_pure_call (call: stmt))
4253	{
4254	tree fndecl = gimple_call_fndecl (gs: stmt);
4255	if (fndecl)
4256	{
4257	struct tm_ipa_cg_data *d;
4258	unsigned *pcallers;
4259	struct cgraph_node *node;
4260
4261	if (is_tm_ending_fndecl (fndecl))
4262	continue;
4263	if (find_tm_replacement_function (fndecl))
4264	continue;
4265
4266	node = cgraph_node::get (decl: fndecl);
4267	gcc_assert (node != NULL);
4268	d = get_cg_data (node: &node, traverse_aliases: true);
4269
4270	pcallers = (for_clone ? &d->tm_callers_clone
4271	: &d->tm_callers_normal);
4272	*pcallers += 1;
4273
4274	maybe_push_queue (node, queue_p: callees_p, in_queue_p: &d->in_callee_queue);
4275	}
4276	}
4277	}
4278	}
4279
4280	/* Scan all calls in NODE that are within a transaction region,
4281	and push the resulting nodes into the callee queue. */
4282
4283	static void
4284	ipa_tm_scan_calls_transaction (struct tm_ipa_cg_data *d,
4285	cgraph_node_queue *callees_p)
4286	{
4287	d->transaction_blocks_normal = BITMAP_ALLOC (obstack: &tm_obstack);
4288	d->all_tm_regions = all_tm_regions;
4289
4290	for (tm_region *r = all_tm_regions; r; r = r->next)
4291	{
4292	vec<basic_block> bbs;
4293	basic_block bb;
4294	unsigned i;
4295
4296	bbs = get_tm_region_blocks (entry_block: r->entry_block, exit_blocks: r->exit_blocks, NULL,
4297	all_region_blocks: d->transaction_blocks_normal, stop_at_irrevocable_p: false, include_uninstrumented_p: false);
4298
4299	FOR_EACH_VEC_ELT (bbs, i, bb)
4300	ipa_tm_scan_calls_block (callees_p, bb, for_clone: false);
4301
4302	bbs.release ();
4303	}
4304	}
4305
4306	/* Scan all calls in NODE as if this is the transactional clone,
4307	and push the destinations into the callee queue. */
4308
4309	static void
4310	ipa_tm_scan_calls_clone (struct cgraph_node *node,
4311	cgraph_node_queue *callees_p)
4312	{
4313	struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
4314	basic_block bb;
4315
4316	FOR_EACH_BB_FN (bb, fn)
4317	ipa_tm_scan_calls_block (callees_p, bb, for_clone: true);
4318	}
4319
4320	/* The function NODE has been detected to be irrevocable. Push all
4321	of its callers onto WORKLIST for the purpose of re-scanning them. */
4322
4323	static void
4324	ipa_tm_note_irrevocable (struct cgraph_node *node,
4325	cgraph_node_queue *worklist_p)
4326	{
4327	struct tm_ipa_cg_data *d = get_cg_data (node: &node, traverse_aliases: true);
4328	struct cgraph_edge *e;
4329
4330	d->is_irrevocable = true;
4331
4332	for (e = node->callers; e ; e = e->next_caller)
4333	{
4334	basic_block bb;
4335	struct cgraph_node *caller;
4336
4337	/* Don't examine recursive calls. */
4338	if (e->caller == node)
4339	continue;
4340	/* Even if we think we can go irrevocable, believe the user
4341	above all. */
4342	if (is_tm_safe_or_pure (x: e->caller->decl))
4343	continue;
4344
4345	caller = e->caller;
4346	d = get_cg_data (node: &caller, traverse_aliases: true);
4347
4348	/* Check if the callee is in a transactional region. If so,
4349	schedule the function for normal re-scan as well. */
4350	bb = gimple_bb (g: e->call_stmt);
4351	gcc_assert (bb != NULL);
4352	if (d->transaction_blocks_normal
4353	&& bitmap_bit_p (d->transaction_blocks_normal, bb->index))
4354	d->want_irr_scan_normal = true;
4355
4356	maybe_push_queue (node: caller, queue_p: worklist_p, in_queue_p: &d->in_worklist);
4357	}
4358	}
4359
4360	/* A subroutine of ipa_tm_scan_irr_blocks; return true iff any statement
4361	within the block is irrevocable. */
4362
4363	static bool
4364	ipa_tm_scan_irr_block (basic_block bb)
4365	{
4366	gimple_stmt_iterator gsi;
4367	tree fn;
4368
4369	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
4370	{
4371	gimple *stmt = gsi_stmt (i: gsi);
4372	switch (gimple_code (g: stmt))
4373	{
4374	case GIMPLE_ASSIGN:
4375	if (gimple_assign_single_p (gs: stmt))
4376	{
4377	tree lhs = gimple_assign_lhs (gs: stmt);
4378	tree rhs = gimple_assign_rhs1 (gs: stmt);
4379	if (volatile_lvalue_p (t: lhs) || volatile_lvalue_p (t: rhs))
4380	return true;
4381	}
4382	break;
4383
4384	case GIMPLE_CALL:
4385	{
4386	tree lhs = gimple_call_lhs (gs: stmt);
4387	if (lhs && volatile_lvalue_p (t: lhs))
4388	return true;
4389
4390	if (is_tm_pure_call (call: stmt))
4391	break;
4392
4393	fn = gimple_call_fn (gs: stmt);
4394
4395	/* Functions with the attribute are by definition irrevocable. */
4396	if (is_tm_irrevocable (x: fn))
4397	return true;
4398
4399	/* For direct function calls, go ahead and check for replacement
4400	functions, or transitive irrevocable functions. For indirect
4401	functions, we'll ask the runtime. */
4402	if (TREE_CODE (fn) == ADDR_EXPR)
4403	{
4404	struct tm_ipa_cg_data *d;
4405	struct cgraph_node *node;
4406
4407	fn = TREE_OPERAND (fn, 0);
4408	if (is_tm_ending_fndecl (fndecl: fn))
4409	break;
4410	if (find_tm_replacement_function (fndecl: fn))
4411	break;
4412
4413	node = cgraph_node::get (decl: fn);
4414	d = get_cg_data (node: &node, traverse_aliases: true);
4415
4416	/* Return true if irrevocable, but above all, believe
4417	the user. */
4418	if (d->is_irrevocable
4419	&& !is_tm_safe_or_pure (x: fn))
4420	return true;
4421	}
4422	break;
4423	}
4424
4425	case GIMPLE_ASM:
4426	/* ??? The Approved Method of indicating that an inline
4427	assembly statement is not relevant to the transaction
4428	is to wrap it in a __tm_waiver block. This is not
4429	yet implemented, so we can't check for it. */
4430	if (is_tm_safe (x: current_function_decl))
4431	error_at (gimple_location (g: stmt),
4432	"%<asm%> not allowed in %<transaction_safe%> function");
4433	return true;
4434
4435	default:
4436	break;
4437	}
4438	}
4439
4440	return false;
4441	}
4442
4443	/* For each of the blocks seeded witin PQUEUE, walk the CFG looking
4444	for new irrevocable blocks, marking them in NEW_IRR. Don't bother
4445	scanning past OLD_IRR or EXIT_BLOCKS. */
4446
4447	static bool
4448	ipa_tm_scan_irr_blocks (vec<basic_block> *pqueue, bitmap new_irr,
4449	bitmap old_irr, bitmap exit_blocks)
4450	{
4451	bool any_new_irr = false;
4452	edge e;
4453	edge_iterator ei;
4454	bitmap visited_blocks = BITMAP_ALLOC (NULL);
4455
4456	do
4457	{
4458	basic_block bb = pqueue->pop ();
4459
4460	/* Don't re-scan blocks we know already are irrevocable. */
4461	if (old_irr && bitmap_bit_p (old_irr, bb->index))
4462	continue;
4463
4464	if (ipa_tm_scan_irr_block (bb))
4465	{
4466	bitmap_set_bit (new_irr, bb->index);
4467	any_new_irr = true;
4468	}
4469	else if (exit_blocks == NULL || !bitmap_bit_p (exit_blocks, bb->index))
4470	{
4471	FOR_EACH_EDGE (e, ei, bb->succs)
4472	if (!bitmap_bit_p (visited_blocks, e->dest->index))
4473	{
4474	bitmap_set_bit (visited_blocks, e->dest->index);
4475	pqueue->safe_push (obj: e->dest);
4476	}
4477	}
4478	}
4479	while (!pqueue->is_empty ());
4480
4481	BITMAP_FREE (visited_blocks);
4482
4483	return any_new_irr;
4484	}
4485
4486	/* Propagate the irrevocable property both up and down the dominator tree.
4487	BB is the current block being scanned; EXIT_BLOCKS are the edges of the
4488	TM regions; OLD_IRR are the results of a previous scan of the dominator
4489	tree which has been fully propagated; NEW_IRR is the set of new blocks
4490	which are gaining the irrevocable property during the current scan. */
4491
4492	static void
4493	ipa_tm_propagate_irr (basic_block entry_block, bitmap new_irr,
4494	bitmap old_irr, bitmap exit_blocks)
4495	{
4496	vec<basic_block> bbs;
4497	bitmap all_region_blocks;
4498
4499	/* If this block is in the old set, no need to rescan. */
4500	if (old_irr && bitmap_bit_p (old_irr, entry_block->index))
4501	return;
4502
4503	all_region_blocks = BITMAP_ALLOC (obstack: &tm_obstack);
4504	bbs = get_tm_region_blocks (entry_block, exit_blocks, NULL,
4505	all_region_blocks, stop_at_irrevocable_p: false);
4506	do
4507	{
4508	basic_block bb = bbs.pop ();
4509	bool this_irr = bitmap_bit_p (new_irr, bb->index);
4510	bool all_son_irr = false;
4511	edge_iterator ei;
4512	edge e;
4513
4514	/* Propagate up. If my children are, I am too, but we must have
4515	at least one child that is. */
4516	if (!this_irr)
4517	{
4518	FOR_EACH_EDGE (e, ei, bb->succs)
4519	{
4520	if (!bitmap_bit_p (new_irr, e->dest->index))
4521	{
4522	all_son_irr = false;
4523	break;
4524	}
4525	else
4526	all_son_irr = true;
4527	}
4528	if (all_son_irr)
4529	{
4530	/* Add block to new_irr if it hasn't already been processed. */
4531	if (!old_irr || !bitmap_bit_p (old_irr, bb->index))
4532	{
4533	bitmap_set_bit (new_irr, bb->index);
4534	this_irr = true;
4535	}
4536	}
4537	}
4538
4539	/* Propagate down to everyone we immediately dominate. */
4540	if (this_irr)
4541	{
4542	basic_block son;
4543	for (son = first_dom_son (CDI_DOMINATORS, bb);
4544	son;
4545	son = next_dom_son (CDI_DOMINATORS, son))
4546	{
4547	/* Make sure block is actually in a TM region, and it
4548	isn't already in old_irr. */
4549	if ((!old_irr || !bitmap_bit_p (old_irr, son->index))
4550	&& bitmap_bit_p (all_region_blocks, son->index))
4551	bitmap_set_bit (new_irr, son->index);
4552	}
4553	}
4554	}
4555	while (!bbs.is_empty ());
4556
4557	BITMAP_FREE (all_region_blocks);
4558	bbs.release ();
4559	}
4560
4561	static void
4562	ipa_tm_decrement_clone_counts (basic_block bb, bool for_clone)
4563	{
4564	gimple_stmt_iterator gsi;
4565
4566	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
4567	{
4568	gimple *stmt = gsi_stmt (i: gsi);
4569	if (is_gimple_call (gs: stmt) && !is_tm_pure_call (call: stmt))
4570	{
4571	tree fndecl = gimple_call_fndecl (gs: stmt);
4572	if (fndecl)
4573	{
4574	struct tm_ipa_cg_data *d;
4575	unsigned *pcallers;
4576	struct cgraph_node *tnode;
4577
4578	if (is_tm_ending_fndecl (fndecl))
4579	continue;
4580	if (find_tm_replacement_function (fndecl))
4581	continue;
4582
4583	tnode = cgraph_node::get (decl: fndecl);
4584	d = get_cg_data (node: &tnode, traverse_aliases: true);
4585
4586	pcallers = (for_clone ? &d->tm_callers_clone
4587	: &d->tm_callers_normal);
4588
4589	gcc_assert (*pcallers > 0);
4590	*pcallers -= 1;
4591	}
4592	}
4593	}
4594	}
4595
4596	/* (Re-)Scan the transaction blocks in NODE for calls to irrevocable functions,
4597	as well as other irrevocable actions such as inline assembly. Mark all
4598	such blocks as irrevocable and decrement the number of calls to
4599	transactional clones. Return true if, for the transactional clone, the
4600	entire function is irrevocable. */
4601
4602	static bool
4603	ipa_tm_scan_irr_function (struct cgraph_node *node, bool for_clone)
4604	{
4605	struct tm_ipa_cg_data *d;
4606	bitmap new_irr, old_irr;
4607	bool ret = false;
4608
4609	/* Builtin operators (operator new, and such). */
4610	if (DECL_STRUCT_FUNCTION (node->decl) == NULL
4611	|| DECL_STRUCT_FUNCTION (node->decl)->cfg == NULL)
4612	return false;
4613
4614	push_cfun (DECL_STRUCT_FUNCTION (node->decl));
4615	calculate_dominance_info (CDI_DOMINATORS);
4616
4617	d = get_cg_data (node: &node, traverse_aliases: true);
4618	auto_vec<basic_block, 10> queue;
4619	new_irr = BITMAP_ALLOC (obstack: &tm_obstack);
4620
4621	/* Scan each tm region, propagating irrevocable status through the tree. */
4622	if (for_clone)
4623	{
4624	old_irr = d->irrevocable_blocks_clone;
4625	queue.quick_push (obj: single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
4626	if (ipa_tm_scan_irr_blocks (pqueue: &queue, new_irr, old_irr, NULL))
4627	{
4628	ipa_tm_propagate_irr (entry_block: single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
4629	new_irr,
4630	old_irr, NULL);
4631	ret = bitmap_bit_p (new_irr,
4632	single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun))->index);
4633	}
4634	}
4635	else
4636	{
4637	struct tm_region *region;
4638
4639	old_irr = d->irrevocable_blocks_normal;
4640	for (region = d->all_tm_regions; region; region = region->next)
4641	{
4642	queue.quick_push (obj: region->entry_block);
4643	if (ipa_tm_scan_irr_blocks (pqueue: &queue, new_irr, old_irr,
4644	exit_blocks: region->exit_blocks))
4645	ipa_tm_propagate_irr (entry_block: region->entry_block, new_irr, old_irr,
4646	exit_blocks: region->exit_blocks);
4647	}
4648	}
4649
4650	/* If we found any new irrevocable blocks, reduce the call count for
4651	transactional clones within the irrevocable blocks. Save the new
4652	set of irrevocable blocks for next time. */
4653	if (!bitmap_empty_p (map: new_irr))
4654	{
4655	bitmap_iterator bmi;
4656	unsigned i;
4657
4658	EXECUTE_IF_SET_IN_BITMAP (new_irr, 0, i, bmi)
4659	ipa_tm_decrement_clone_counts (BASIC_BLOCK_FOR_FN (cfun, i),
4660	for_clone);
4661
4662	if (old_irr)
4663	{
4664	bitmap_ior_into (old_irr, new_irr);
4665	BITMAP_FREE (new_irr);
4666	}
4667	else if (for_clone)
4668	d->irrevocable_blocks_clone = new_irr;
4669	else
4670	d->irrevocable_blocks_normal = new_irr;
4671
4672	if (dump_file && new_irr)
4673	{
4674	const char *dname;
4675	bitmap_iterator bmi;
4676	unsigned i;
4677
4678	dname = lang_hooks.decl_printable_name (current_function_decl, 2);
4679	EXECUTE_IF_SET_IN_BITMAP (new_irr, 0, i, bmi)
4680	fprintf (stream: dump_file, format: "%s: bb %d goes irrevocable\n", dname, i);
4681	}
4682	}
4683	else
4684	BITMAP_FREE (new_irr);
4685
4686	pop_cfun ();
4687
4688	return ret;
4689	}
4690
4691	/* Return true if, for the transactional clone of NODE, any call
4692	may enter irrevocable mode. */
4693
4694	static bool
4695	ipa_tm_mayenterirr_function (struct cgraph_node *node)
4696	{
4697	struct tm_ipa_cg_data *d;
4698	tree decl;
4699	unsigned flags;
4700
4701	d = get_cg_data (node: &node, traverse_aliases: true);
4702	decl = node->decl;
4703	flags = flags_from_decl_or_type (decl);
4704
4705	/* Handle some TM builtins. Ordinarily these aren't actually generated
4706	at this point, but handling these functions when written in by the
4707	user makes it easier to build unit tests. */
4708	if (flags & ECF_TM_BUILTIN)
4709	return false;
4710
4711	/* Filter out all functions that are marked. */
4712	if (flags & ECF_TM_PURE)
4713	return false;
4714	if (is_tm_safe (x: decl))
4715	return false;
4716	if (is_tm_irrevocable (x: decl))
4717	return true;
4718	if (is_tm_callable (x: decl))
4719	return true;
4720	if (find_tm_replacement_function (fndecl: decl))
4721	return true;
4722
4723	/* If we aren't seeing the final version of the function we don't
4724	know what it will contain at runtime. */
4725	if (node->get_availability () < AVAIL_AVAILABLE)
4726	return true;
4727
4728	/* If the function must go irrevocable, then of course true. */
4729	if (d->is_irrevocable)
4730	return true;
4731
4732	/* If there are any blocks marked irrevocable, then the function
4733	as a whole may enter irrevocable. */
4734	if (d->irrevocable_blocks_clone)
4735	return true;
4736
4737	/* We may have previously marked this function as tm_may_enter_irr;
4738	see pass_diagnose_tm_blocks. */
4739	if (node->tm_may_enter_irr)
4740	return true;
4741
4742	/* Recurse on the main body for aliases. In general, this will
4743	result in one of the bits above being set so that we will not
4744	have to recurse next time. */
4745	if (node->alias)
4746	return ipa_tm_mayenterirr_function
4747	(node: cgraph_node::get (decl: thunk_info::get (node)->alias));
4748
4749	/* What remains is unmarked local functions without items that force
4750	the function to go irrevocable. */
4751	return false;
4752	}
4753
4754	/* Diagnose calls from transaction_safe functions to unmarked
4755	functions that are determined to not be safe. */
4756
4757	static void
4758	ipa_tm_diagnose_tm_safe (struct cgraph_node *node)
4759	{
4760	struct cgraph_edge *e;
4761
4762	for (e = node->callees; e ; e = e->next_callee)
4763	if (!is_tm_callable (x: e->callee->decl)
4764	&& e->callee->tm_may_enter_irr)
4765	error_at (gimple_location (g: e->call_stmt),
4766	"unsafe function call %qD within "
4767	"%<transaction_safe%> function", e->callee->decl);
4768	}
4769
4770	/* Diagnose call from atomic transactions to unmarked functions
4771	that are determined to not be safe. */
4772
4773	static void
4774	ipa_tm_diagnose_transaction (struct cgraph_node *node,
4775	struct tm_region *all_tm_regions)
4776	{
4777	struct tm_region *r;
4778
4779	for (r = all_tm_regions; r ; r = r->next)
4780	if (gimple_transaction_subcode (transaction_stmt: r->get_transaction_stmt ())
4781	& GTMA_IS_RELAXED)
4782	{
4783	/* Atomic transactions can be nested inside relaxed. */
4784	if (r->inner)
4785	ipa_tm_diagnose_transaction (node, all_tm_regions: r->inner);
4786	}
4787	else
4788	{
4789	vec<basic_block> bbs;
4790	gimple_stmt_iterator gsi;
4791	basic_block bb;
4792	size_t i;
4793
4794	bbs = get_tm_region_blocks (entry_block: r->entry_block, exit_blocks: r->exit_blocks,
4795	irr_blocks: r->irr_blocks, NULL, stop_at_irrevocable_p: false);
4796
4797	for (i = 0; bbs.iterate (ix: i, ptr: &bb); ++i)
4798	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
4799	{
4800	gimple *stmt = gsi_stmt (i: gsi);
4801	tree fndecl;
4802
4803	if (gimple_code (g: stmt) == GIMPLE_ASM)
4804	{
4805	error_at (gimple_location (g: stmt),
4806	"%<asm%> not allowed in atomic transaction");
4807	continue;
4808	}
4809
4810	if (!is_gimple_call (gs: stmt))
4811	continue;
4812	fndecl = gimple_call_fndecl (gs: stmt);
4813
4814	/* Indirect function calls have been diagnosed already. */
4815	if (!fndecl)
4816	continue;
4817
4818	/* Stop at the end of the transaction. */
4819	if (is_tm_ending_fndecl (fndecl))
4820	{
4821	if (bitmap_bit_p (r->exit_blocks, bb->index))
4822	break;
4823	continue;
4824	}
4825
4826	/* Marked functions have been diagnosed already. */
4827	if (is_tm_pure_call (call: stmt))
4828	continue;
4829	if (is_tm_callable (x: fndecl))
4830	continue;
4831
4832	if (cgraph_node::local_info_node (decl: fndecl)->tm_may_enter_irr)
4833	error_at (gimple_location (g: stmt),
4834	"unsafe function call %qD within "
4835	"atomic transaction", fndecl);
4836	}
4837
4838	bbs.release ();
4839	}
4840	}
4841
4842	/* Return a transactional mangled name for the DECL_ASSEMBLER_NAME in
4843	OLD_DECL. The returned value is a freshly malloced pointer that
4844	should be freed by the caller. */
4845
4846	static tree
4847	tm_mangle (tree old_asm_id)
4848	{
4849	const char *old_asm_name;
4850	char *tm_name;
4851	void *alloc = NULL;
4852	struct demangle_component *dc;
4853	tree new_asm_id;
4854
4855	/* Determine if the symbol is already a valid C++ mangled name. Do this
4856	even for C, which might be interfacing with C++ code via appropriately
4857	ugly identifiers. */
4858	/* ??? We could probably do just as well checking for "_Z" and be done. */
4859	old_asm_name = IDENTIFIER_POINTER (old_asm_id);
4860	dc = cplus_demangle_v3_components (mangled: old_asm_name, DMGL_NO_OPTS, mem: &alloc);
4861
4862	if (dc == NULL)
4863	{
4864	char length[12];
4865
4866	do_unencoded:
4867	sprintf (s: length, format: "%u", IDENTIFIER_LENGTH (old_asm_id));
4868	tm_name = concat ("_ZGTt", length, old_asm_name, NULL);
4869	}
4870	else
4871	{
4872	old_asm_name += 2; /* Skip _Z */
4873
4874	switch (dc->type)
4875	{
4876	case DEMANGLE_COMPONENT_TRANSACTION_CLONE:
4877	case DEMANGLE_COMPONENT_NONTRANSACTION_CLONE:
4878	/* Don't play silly games, you! */
4879	goto do_unencoded;
4880
4881	case DEMANGLE_COMPONENT_HIDDEN_ALIAS:
4882	/* I'd really like to know if we can ever be passed one of
4883	these from the C++ front end. The Logical Thing would
4884	seem that hidden-alias should be outer-most, so that we
4885	get hidden-alias of a transaction-clone and not vice-versa. */
4886	old_asm_name += 2;
4887	break;
4888
4889	default:
4890	break;
4891	}
4892
4893	tm_name = concat ("_ZGTt", old_asm_name, NULL);
4894	}
4895	free (ptr: alloc);
4896
4897	new_asm_id = get_identifier (tm_name);
4898	free (ptr: tm_name);
4899
4900	return new_asm_id;
4901	}
4902
4903	static inline void
4904	ipa_tm_mark_force_output_node (struct cgraph_node *node)
4905	{
4906	node->mark_force_output ();
4907	node->analyzed = true;
4908	}
4909
4910	static inline void
4911	ipa_tm_mark_forced_by_abi_node (struct cgraph_node *node)
4912	{
4913	node->forced_by_abi = true;
4914	node->analyzed = true;
4915	}
4916
4917	/* Callback data for ipa_tm_create_version_alias. */
4918	struct create_version_alias_info
4919	{
4920	struct cgraph_node *old_node;
4921	tree new_decl;
4922	};
4923
4924	/* A subroutine of ipa_tm_create_version, called via
4925	cgraph_for_node_and_aliases. Create new tm clones for each of
4926	the existing aliases. */
4927	static bool
4928	ipa_tm_create_version_alias (struct cgraph_node *node, void *data)
4929	{
4930	struct create_version_alias_info *info
4931	= (struct create_version_alias_info *)data;
4932	tree old_decl, new_decl, tm_name;
4933	struct cgraph_node *new_node;
4934
4935	if (!node->cpp_implicit_alias)
4936	return false;
4937
4938	old_decl = node->decl;
4939	tm_name = tm_mangle (DECL_ASSEMBLER_NAME (old_decl));
4940	new_decl = build_decl (DECL_SOURCE_LOCATION (old_decl),
4941	TREE_CODE (old_decl), tm_name,
4942	TREE_TYPE (old_decl));
4943
4944	SET_DECL_ASSEMBLER_NAME (new_decl, tm_name);
4945	SET_DECL_RTL (new_decl, NULL);
4946
4947	/* Based loosely on C++'s make_alias_for(). */
4948	TREE_PUBLIC (new_decl) = TREE_PUBLIC (old_decl);
4949	DECL_CONTEXT (new_decl) = DECL_CONTEXT (old_decl);
4950	DECL_LANG_SPECIFIC (new_decl) = DECL_LANG_SPECIFIC (old_decl);
4951	TREE_READONLY (new_decl) = TREE_READONLY (old_decl);
4952	DECL_EXTERNAL (new_decl) = 0;
4953	DECL_ARTIFICIAL (new_decl) = 1;
4954	TREE_ADDRESSABLE (new_decl) = 1;
4955	TREE_USED (new_decl) = 1;
4956	TREE_SYMBOL_REFERENCED (tm_name) = 1;
4957
4958	/* Perform the same remapping to the comdat group. */
4959	if (DECL_ONE_ONLY (new_decl))
4960	varpool_node::get (decl: new_decl)->set_comdat_group
4961	(tm_mangle (old_asm_id: decl_comdat_group_id (old_decl)));
4962
4963	new_node = cgraph_node::create_same_body_alias (alias: new_decl, decl: info->new_decl);
4964	new_node->tm_clone = true;
4965	new_node->externally_visible = info->old_node->externally_visible;
4966	new_node->no_reorder = info->old_node->no_reorder;
4967	/* ?? Do not traverse aliases here. */
4968	get_cg_data (node: &node, traverse_aliases: false)->clone = new_node;
4969
4970	record_tm_clone_pair (old_decl, new_decl);
4971
4972	if (info->old_node->force_output
4973	|| info->old_node->ref_list.first_referring ())
4974	ipa_tm_mark_force_output_node (node: new_node);
4975	if (info->old_node->forced_by_abi)
4976	ipa_tm_mark_forced_by_abi_node (node: new_node);
4977	return false;
4978	}
4979
4980	/* Create a copy of the function (possibly declaration only) of OLD_NODE,
4981	appropriate for the transactional clone. */
4982
4983	static void
4984	ipa_tm_create_version (struct cgraph_node *old_node)
4985	{
4986	tree new_decl, old_decl, tm_name;
4987	struct cgraph_node *new_node;
4988
4989	old_decl = old_node->decl;
4990	new_decl = copy_node (old_decl);
4991
4992	/* DECL_ASSEMBLER_NAME needs to be set before we call
4993	cgraph_copy_node_for_versioning below, because cgraph_node will
4994	fill the assembler_name_hash. */
4995	tm_name = tm_mangle (DECL_ASSEMBLER_NAME (old_decl));
4996	SET_DECL_ASSEMBLER_NAME (new_decl, tm_name);
4997	SET_DECL_RTL (new_decl, NULL);
4998	TREE_SYMBOL_REFERENCED (tm_name) = 1;
4999
5000	/* Perform the same remapping to the comdat group. */
5001	if (DECL_ONE_ONLY (new_decl))
5002	varpool_node::get (decl: new_decl)->set_comdat_group
5003	(tm_mangle (DECL_COMDAT_GROUP (old_decl)));
5004
5005	gcc_assert (!old_node->ipa_transforms_to_apply.exists ());
5006	new_node = old_node->create_version_clone (new_decl, redirect_callers: vNULL, NULL);
5007	new_node->local = false;
5008	new_node->externally_visible = old_node->externally_visible;
5009	new_node->lowered = true;
5010	new_node->tm_clone = 1;
5011	if (!old_node->implicit_section)
5012	new_node->set_section (*old_node);
5013	get_cg_data (node: &old_node, traverse_aliases: true)->clone = new_node;
5014
5015	if (old_node->get_availability () >= AVAIL_INTERPOSABLE)
5016	{
5017	/* Remap extern inline to static inline. */
5018	/* ??? Is it worth trying to use make_decl_one_only? */
5019	if (DECL_DECLARED_INLINE_P (new_decl) && DECL_EXTERNAL (new_decl))
5020	{
5021	DECL_EXTERNAL (new_decl) = 0;
5022	TREE_PUBLIC (new_decl) = 0;
5023	DECL_WEAK (new_decl) = 0;
5024	}
5025
5026	tree_function_versioning (old_decl, new_decl,
5027	NULL, NULL, false, NULL, NULL);
5028	}
5029
5030	record_tm_clone_pair (old_decl, new_decl);
5031
5032	symtab->call_cgraph_insertion_hooks (node: new_node);
5033	if (old_node->force_output
5034	|| old_node->ref_list.first_referring ())
5035	ipa_tm_mark_force_output_node (node: new_node);
5036	if (old_node->forced_by_abi)
5037	ipa_tm_mark_forced_by_abi_node (node: new_node);
5038
5039	/* Do the same thing, but for any aliases of the original node. */
5040	{
5041	struct create_version_alias_info data;
5042	data.old_node = old_node;
5043	data.new_decl = new_decl;
5044	old_node->call_for_symbol_thunks_and_aliases (callback: ipa_tm_create_version_alias,
5045	data: &data, include_overwritable: true);
5046	}
5047	}
5048
5049	/* Construct a call to TM_IRREVOCABLE and insert it at the beginning of BB. */
5050
5051	static void
5052	ipa_tm_insert_irr_call (struct cgraph_node *node, struct tm_region *region,
5053	basic_block bb)
5054	{
5055	gimple_stmt_iterator gsi;
5056	gcall *g;
5057
5058	transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
5059
5060	g = gimple_build_call (builtin_decl_explicit (fncode: BUILT_IN_TM_IRREVOCABLE),
5061	1, build_int_cst (NULL_TREE, MODE_SERIALIRREVOCABLE));
5062
5063	split_block_after_labels (bb);
5064	gsi = gsi_after_labels (bb);
5065	gsi_insert_before (&gsi, g, GSI_SAME_STMT);
5066
5067	node->create_edge (callee: cgraph_node::get_create
5068	(builtin_decl_explicit (fncode: BUILT_IN_TM_IRREVOCABLE)),
5069	call_stmt: g, count: gimple_bb (g)->count);
5070	}
5071
5072	/* Construct a call to TM_GETTMCLONE and insert it before GSI. */
5073
5074	static bool
5075	ipa_tm_insert_gettmclone_call (struct cgraph_node *node,
5076	struct tm_region *region,
5077	gimple_stmt_iterator *gsi, gcall *stmt)
5078	{
5079	tree gettm_fn, ret, old_fn, callfn;
5080	gcall *g;
5081	gassign *g2;
5082	bool safe;
5083
5084	old_fn = gimple_call_fn (gs: stmt);
5085
5086	if (TREE_CODE (old_fn) == ADDR_EXPR)
5087	{
5088	tree fndecl = TREE_OPERAND (old_fn, 0);
5089	tree clone = get_tm_clone_pair (fndecl);
5090
5091	/* By transforming the call into a TM_GETTMCLONE, we are
5092	technically taking the address of the original function and
5093	its clone. Explain this so inlining will know this function
5094	is needed. */
5095	cgraph_node::get (decl: fndecl)->mark_address_taken () ;
5096	if (clone)
5097	cgraph_node::get (decl: clone)->mark_address_taken ();
5098	}
5099
5100	safe = is_tm_safe (TREE_TYPE (old_fn));
5101	gettm_fn = builtin_decl_explicit (fncode: safe ? BUILT_IN_TM_GETTMCLONE_SAFE
5102	: BUILT_IN_TM_GETTMCLONE_IRR);
5103	ret = create_tmp_var (ptr_type_node);
5104
5105	if (!safe)
5106	transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
5107
5108	/* Discard OBJ_TYPE_REF, since we weren't able to fold it. */
5109	if (TREE_CODE (old_fn) == OBJ_TYPE_REF)
5110	old_fn = OBJ_TYPE_REF_EXPR (old_fn);
5111
5112	g = gimple_build_call (gettm_fn, 1, old_fn);
5113	ret = make_ssa_name (var: ret, stmt: g);
5114	gimple_call_set_lhs (gs: g, lhs: ret);
5115
5116	gsi_insert_before (gsi, g, GSI_SAME_STMT);
5117
5118	node->create_edge (callee: cgraph_node::get_create (gettm_fn), call_stmt: g, count: gimple_bb (g)->count);
5119
5120	/* Cast return value from tm_gettmclone* into appropriate function
5121	pointer. */
5122	callfn = create_tmp_var (TREE_TYPE (old_fn));
5123	g2 = gimple_build_assign (callfn,
5124	fold_build1 (NOP_EXPR, TREE_TYPE (callfn), ret));
5125	callfn = make_ssa_name (var: callfn, stmt: g2);
5126	gimple_assign_set_lhs (gs: g2, lhs: callfn);
5127	gsi_insert_before (gsi, g2, GSI_SAME_STMT);
5128
5129	/* ??? This is a hack to preserve the NOTHROW bit on the call,
5130	which we would have derived from the decl. Failure to save
5131	this bit means we might have to split the basic block. */
5132	if (gimple_call_nothrow_p (s: stmt))
5133	gimple_call_set_nothrow (s: stmt, nothrow_p: true);
5134
5135	gimple_call_set_fn (gs: stmt, fn: callfn);
5136
5137	/* Discarding OBJ_TYPE_REF above may produce incompatible LHS and RHS
5138	for a call statement. Fix it. */
5139	{
5140	tree lhs = gimple_call_lhs (gs: stmt);
5141	tree rettype = TREE_TYPE (gimple_call_fntype (stmt));
5142	if (lhs
5143	&& !useless_type_conversion_p (TREE_TYPE (lhs), rettype))
5144	{
5145	tree temp;
5146
5147	temp = create_tmp_reg (rettype);
5148	gimple_call_set_lhs (gs: stmt, lhs: temp);
5149
5150	g2 = gimple_build_assign (lhs,
5151	fold_build1 (VIEW_CONVERT_EXPR,
5152	TREE_TYPE (lhs), temp));
5153	gsi_insert_after (gsi, g2, GSI_SAME_STMT);
5154	}
5155	}
5156
5157	update_stmt (s: stmt);
5158	cgraph_edge *e = cgraph_node::get (decl: current_function_decl)->get_edge (call_stmt: stmt);
5159	if (e && e->indirect_info)
5160	e->indirect_info->polymorphic = false;
5161
5162	return true;
5163	}
5164
5165	/* Helper function for ipa_tm_transform_calls*. Given a call
5166	statement in GSI which resides inside transaction REGION, redirect
5167	the call to either its wrapper function, or its clone. */
5168
5169	static void
5170	ipa_tm_transform_calls_redirect (struct cgraph_node *node,
5171	struct tm_region *region,
5172	gimple_stmt_iterator *gsi,
5173	bool *need_ssa_rename_p)
5174	{
5175	gcall *stmt = as_a <gcall *> (p: gsi_stmt (i: *gsi));
5176	struct cgraph_node *new_node;
5177	struct cgraph_edge *e = node->get_edge (call_stmt: stmt);
5178	tree fndecl = gimple_call_fndecl (gs: stmt);
5179
5180	/* For indirect calls, pass the address through the runtime. */
5181	if (fndecl == NULL)
5182	{
5183	*need_ssa_rename_p |=
5184	ipa_tm_insert_gettmclone_call (node, region, gsi, stmt);
5185	return;
5186	}
5187
5188	/* Handle some TM builtins. Ordinarily these aren't actually generated
5189	at this point, but handling these functions when written in by the
5190	user makes it easier to build unit tests. */
5191	if (flags_from_decl_or_type (fndecl) & ECF_TM_BUILTIN)
5192	return;
5193
5194	/* Fixup recursive calls inside clones. */
5195	/* ??? Why did cgraph_copy_node_for_versioning update the call edges
5196	for recursion but not update the call statements themselves? */
5197	if (e->caller == e->callee && decl_is_tm_clone (fndecl: current_function_decl))
5198	{
5199	gimple_call_set_fndecl (gs: stmt, decl: current_function_decl);
5200	return;
5201	}
5202
5203	/* If there is a replacement, use it. */
5204	fndecl = find_tm_replacement_function (fndecl);
5205	if (fndecl)
5206	{
5207	new_node = cgraph_node::get_create (fndecl);
5208
5209	/* ??? Mark all transaction_wrap functions tm_may_enter_irr.
5210
5211	We can't do this earlier in record_tm_replacement because
5212	cgraph_remove_unreachable_nodes is called before we inject
5213	references to the node. Further, we can't do this in some
5214	nice central place in ipa_tm_execute because we don't have
5215	the exact list of wrapper functions that would be used.
5216	Marking more wrappers than necessary results in the creation
5217	of unnecessary cgraph_nodes, which can cause some of the
5218	other IPA passes to crash.
5219
5220	We do need to mark these nodes so that we get the proper
5221	result in expand_call_tm. */
5222	/* ??? This seems broken. How is it that we're marking the
5223	CALLEE as may_enter_irr? Surely we should be marking the
5224	CALLER. Also note that find_tm_replacement_function also
5225	contains mappings into the TM runtime, e.g. memcpy. These
5226	we know won't go irrevocable. */
5227	new_node->tm_may_enter_irr = 1;
5228	}
5229	else
5230	{
5231	struct tm_ipa_cg_data *d;
5232	struct cgraph_node *tnode = e->callee;
5233
5234	d = get_cg_data (node: &tnode, traverse_aliases: true);
5235	new_node = d->clone;
5236
5237	/* As we've already skipped pure calls and appropriate builtins,
5238	and we've already marked irrevocable blocks, if we can't come
5239	up with a static replacement, then ask the runtime. */
5240	if (new_node == NULL)
5241	{
5242	*need_ssa_rename_p |=
5243	ipa_tm_insert_gettmclone_call (node, region, gsi, stmt);
5244	return;
5245	}
5246
5247	fndecl = new_node->decl;
5248	}
5249
5250	e->redirect_callee (n: new_node);
5251	gimple_call_set_fndecl (gs: stmt, decl: fndecl);
5252	}
5253
5254	/* Helper function for ipa_tm_transform_calls. For a given BB,
5255	install calls to tm_irrevocable when IRR_BLOCKS are reached,
5256	redirect other calls to the generated transactional clone. */
5257
5258	static bool
5259	ipa_tm_transform_calls_1 (struct cgraph_node *node, struct tm_region *region,
5260	basic_block bb, bitmap irr_blocks)
5261	{
5262	gimple_stmt_iterator gsi;
5263	bool need_ssa_rename = false;
5264
5265	if (irr_blocks && bitmap_bit_p (irr_blocks, bb->index))
5266	{
5267	ipa_tm_insert_irr_call (node, region, bb);
5268	return true;
5269	}
5270
5271	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
5272	{
5273	gimple *stmt = gsi_stmt (i: gsi);
5274
5275	if (!is_gimple_call (gs: stmt))
5276	continue;
5277	if (is_tm_pure_call (call: stmt))
5278	continue;
5279
5280	/* Redirect edges to the appropriate replacement or clone. */
5281	ipa_tm_transform_calls_redirect (node, region, gsi: &gsi, need_ssa_rename_p: &need_ssa_rename);
5282	}
5283
5284	return need_ssa_rename;
5285	}
5286
5287	/* Walk the CFG for REGION, beginning at BB. Install calls to
5288	tm_irrevocable when IRR_BLOCKS are reached, redirect other calls to
5289	the generated transactional clone. */
5290
5291	static bool
5292	ipa_tm_transform_calls (struct cgraph_node *node, struct tm_region *region,
5293	basic_block bb, bitmap irr_blocks)
5294	{
5295	bool need_ssa_rename = false;
5296	edge e;
5297	edge_iterator ei;
5298	auto_vec<basic_block> queue;
5299	bitmap visited_blocks = BITMAP_ALLOC (NULL);
5300
5301	queue.safe_push (obj: bb);
5302	do
5303	{
5304	bb = queue.pop ();
5305
5306	need_ssa_rename |=
5307	ipa_tm_transform_calls_1 (node, region, bb, irr_blocks);
5308
5309	if (irr_blocks && bitmap_bit_p (irr_blocks, bb->index))
5310	continue;
5311
5312	if (region && bitmap_bit_p (region->exit_blocks, bb->index))
5313	continue;
5314
5315	FOR_EACH_EDGE (e, ei, bb->succs)
5316	if (!bitmap_bit_p (visited_blocks, e->dest->index))
5317	{
5318	bitmap_set_bit (visited_blocks, e->dest->index);
5319	queue.safe_push (obj: e->dest);
5320	}
5321	}
5322	while (!queue.is_empty ());
5323
5324	BITMAP_FREE (visited_blocks);
5325
5326	return need_ssa_rename;
5327	}
5328
5329	/* Transform the calls within the TM regions within NODE. */
5330
5331	static void
5332	ipa_tm_transform_transaction (struct cgraph_node *node)
5333	{
5334	struct tm_ipa_cg_data *d;
5335	struct tm_region *region;
5336	bool need_ssa_rename = false;
5337
5338	d = get_cg_data (node: &node, traverse_aliases: true);
5339
5340	push_cfun (DECL_STRUCT_FUNCTION (node->decl));
5341	calculate_dominance_info (CDI_DOMINATORS);
5342
5343	for (region = d->all_tm_regions; region; region = region->next)
5344	{
5345	/* If we're sure to go irrevocable, don't transform anything. */
5346	if (d->irrevocable_blocks_normal
5347	&& bitmap_bit_p (d->irrevocable_blocks_normal,
5348	region->entry_block->index))
5349	{
5350	transaction_subcode_ior (region, GTMA_DOES_GO_IRREVOCABLE
5351	| GTMA_MAY_ENTER_IRREVOCABLE
5352	| GTMA_HAS_NO_INSTRUMENTATION);
5353	continue;
5354	}
5355
5356	need_ssa_rename |=
5357	ipa_tm_transform_calls (node, region, bb: region->entry_block,
5358	irr_blocks: d->irrevocable_blocks_normal);
5359	}
5360
5361	if (need_ssa_rename)
5362	update_ssa (TODO_update_ssa_only_virtuals);
5363
5364	pop_cfun ();
5365	}
5366
5367	/* Transform the calls within the transactional clone of NODE. */
5368
5369	static void
5370	ipa_tm_transform_clone (struct cgraph_node *node)
5371	{
5372	struct tm_ipa_cg_data *d;
5373	bool need_ssa_rename;
5374
5375	d = get_cg_data (node: &node, traverse_aliases: true);
5376
5377	/* If this function makes no calls and has no irrevocable blocks,
5378	then there's nothing to do. */
5379	/* ??? Remove non-aborting top-level transactions. */
5380	if (!node->callees && !node->indirect_calls && !d->irrevocable_blocks_clone)
5381	return;
5382
5383	push_cfun (DECL_STRUCT_FUNCTION (d->clone->decl));
5384	calculate_dominance_info (CDI_DOMINATORS);
5385
5386	need_ssa_rename =
5387	ipa_tm_transform_calls (node: d->clone, NULL,
5388	bb: single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
5389	irr_blocks: d->irrevocable_blocks_clone);
5390
5391	if (need_ssa_rename)
5392	update_ssa (TODO_update_ssa_only_virtuals);
5393
5394	pop_cfun ();
5395	}
5396
5397	/* Main entry point for the transactional memory IPA pass. */
5398
5399	static unsigned int
5400	ipa_tm_execute (void)
5401	{
5402	cgraph_node_queue tm_callees = cgraph_node_queue ();
5403	/* List of functions that will go irrevocable. */
5404	cgraph_node_queue irr_worklist = cgraph_node_queue ();
5405
5406	struct cgraph_node *node;
5407	struct tm_ipa_cg_data *d;
5408	enum availability a;
5409	unsigned int i;
5410
5411	cgraph_node::checking_verify_cgraph_nodes ();
5412
5413	bitmap_obstack_initialize (&tm_obstack);
5414	initialize_original_copy_tables ();
5415
5416	/* For all local functions marked tm_callable, queue them. */
5417	FOR_EACH_DEFINED_FUNCTION (node)
5418	if (is_tm_callable (x: node->decl)
5419	&& node->get_availability () >= AVAIL_INTERPOSABLE)
5420	{
5421	d = get_cg_data (node: &node, traverse_aliases: true);
5422	maybe_push_queue (node, queue_p: &tm_callees, in_queue_p: &d->in_callee_queue);
5423	}
5424
5425	/* For all local reachable functions... */
5426	FOR_EACH_DEFINED_FUNCTION (node)
5427	if (node->lowered
5428	&& node->get_availability () >= AVAIL_INTERPOSABLE)
5429	{
5430	/* ... marked tm_pure, record that fact for the runtime by
5431	indicating that the pure function is its own tm_callable.
5432	No need to do this if the function's address can't be taken. */
5433	if (is_tm_pure (x: node->decl))
5434	{
5435	if (!node->local)
5436	record_tm_clone_pair (node->decl, node->decl);
5437	continue;
5438	}
5439
5440	push_cfun (DECL_STRUCT_FUNCTION (node->decl));
5441	calculate_dominance_info (CDI_DOMINATORS);
5442
5443	tm_region_init (NULL);
5444	if (all_tm_regions)
5445	{
5446	d = get_cg_data (node: &node, traverse_aliases: true);
5447
5448	/* Scan for calls that are in each transaction, and
5449	generate the uninstrumented code path. */
5450	ipa_tm_scan_calls_transaction (d, callees_p: &tm_callees);
5451
5452	/* Put it in the worklist so we can scan the function
5453	later (ipa_tm_scan_irr_function) and mark the
5454	irrevocable blocks. */
5455	maybe_push_queue (node, queue_p: &irr_worklist, in_queue_p: &d->in_worklist);
5456	d->want_irr_scan_normal = true;
5457	}
5458
5459	pop_cfun ();
5460	}
5461
5462	/* For every local function on the callee list, scan as if we will be
5463	creating a transactional clone, queueing all new functions we find
5464	along the way. */
5465	for (i = 0; i < tm_callees.length (); ++i)
5466	{
5467	node = tm_callees[i];
5468	a = node->get_availability ();
5469	d = get_cg_data (node: &node, traverse_aliases: true);
5470
5471	/* Put it in the worklist so we can scan the function later
5472	(ipa_tm_scan_irr_function) and mark the irrevocable
5473	blocks. */
5474	maybe_push_queue (node, queue_p: &irr_worklist, in_queue_p: &d->in_worklist);
5475
5476	/* Some callees cannot be arbitrarily cloned. These will always be
5477	irrevocable. Mark these now, so that we need not scan them. */
5478	if (is_tm_irrevocable (x: node->decl))
5479	ipa_tm_note_irrevocable (node, worklist_p: &irr_worklist);
5480	else if (a <= AVAIL_NOT_AVAILABLE
5481	&& !is_tm_safe_or_pure (x: node->decl))
5482	ipa_tm_note_irrevocable (node, worklist_p: &irr_worklist);
5483	else if (a >= AVAIL_INTERPOSABLE)
5484	{
5485	if (!tree_versionable_function_p (node->decl))
5486	ipa_tm_note_irrevocable (node, worklist_p: &irr_worklist);
5487	else if (!d->is_irrevocable)
5488	{
5489	/* If this is an alias, make sure its base is queued as well.
5490	we need not scan the callees now, as the base will do. */
5491	if (node->alias)
5492	{
5493	node = cgraph_node::get (decl: thunk_info::get (node)->alias);
5494	d = get_cg_data (node: &node, traverse_aliases: true);
5495	maybe_push_queue (node, queue_p: &tm_callees, in_queue_p: &d->in_callee_queue);
5496	continue;
5497	}
5498
5499	/* Add all nodes called by this function into
5500	tm_callees as well. */
5501	ipa_tm_scan_calls_clone (node, callees_p: &tm_callees);
5502	}
5503	}
5504	}
5505
5506	/* Iterate scans until no more work to be done. Prefer not to use
5507	vec::pop because the worklist tends to follow a breadth-first
5508	search of the callgraph, which should allow convergance with a
5509	minimum number of scans. But we also don't want the worklist
5510	array to grow without bound, so we shift the array up periodically. */
5511	for (i = 0; i < irr_worklist.length (); ++i)
5512	{
5513	if (i > 256 && i == irr_worklist.length () / 8)
5514	{
5515	irr_worklist.block_remove (ix: 0, len: i);
5516	i = 0;
5517	}
5518
5519	node = irr_worklist[i];
5520	d = get_cg_data (node: &node, traverse_aliases: true);
5521	d->in_worklist = false;
5522
5523	if (d->want_irr_scan_normal)
5524	{
5525	d->want_irr_scan_normal = false;
5526	ipa_tm_scan_irr_function (node, for_clone: false);
5527	}
5528	if (d->in_callee_queue && ipa_tm_scan_irr_function (node, for_clone: true))
5529	ipa_tm_note_irrevocable (node, worklist_p: &irr_worklist);
5530	}
5531
5532	/* For every function on the callee list, collect the tm_may_enter_irr
5533	bit on the node. */
5534	irr_worklist.truncate (size: 0);
5535	for (i = 0; i < tm_callees.length (); ++i)
5536	{
5537	node = tm_callees[i];
5538	if (ipa_tm_mayenterirr_function (node))
5539	{
5540	d = get_cg_data (node: &node, traverse_aliases: true);
5541	gcc_assert (d->in_worklist == false);
5542	maybe_push_queue (node, queue_p: &irr_worklist, in_queue_p: &d->in_worklist);
5543	}
5544	}
5545
5546	/* Propagate the tm_may_enter_irr bit to callers until stable. */
5547	for (i = 0; i < irr_worklist.length (); ++i)
5548	{
5549	struct cgraph_node *caller;
5550	struct cgraph_edge *e;
5551	struct ipa_ref *ref;
5552
5553	if (i > 256 && i == irr_worklist.length () / 8)
5554	{
5555	irr_worklist.block_remove (ix: 0, len: i);
5556	i = 0;
5557	}
5558
5559	node = irr_worklist[i];
5560	d = get_cg_data (node: &node, traverse_aliases: true);
5561	d->in_worklist = false;
5562	node->tm_may_enter_irr = true;
5563
5564	/* Propagate back to normal callers. */
5565	for (e = node->callers; e ; e = e->next_caller)
5566	{
5567	caller = e->caller;
5568	if (!is_tm_safe_or_pure (x: caller->decl)
5569	&& !caller->tm_may_enter_irr)
5570	{
5571	d = get_cg_data (node: &caller, traverse_aliases: true);
5572	maybe_push_queue (node: caller, queue_p: &irr_worklist, in_queue_p: &d->in_worklist);
5573	}
5574	}
5575
5576	/* Propagate back to referring aliases as well. */
5577	FOR_EACH_ALIAS (node, ref)
5578	{
5579	caller = dyn_cast<cgraph_node *> (p: ref->referring);
5580	if (!caller->tm_may_enter_irr)
5581	{
5582	/* ?? Do not traverse aliases here. */
5583	d = get_cg_data (node: &caller, traverse_aliases: false);
5584	maybe_push_queue (node: caller, queue_p: &irr_worklist, in_queue_p: &d->in_worklist);
5585	}
5586	}
5587	}
5588
5589	/* Now validate all tm_safe functions, and all atomic regions in
5590	other functions. */
5591	FOR_EACH_DEFINED_FUNCTION (node)
5592	if (node->lowered
5593	&& node->get_availability () >= AVAIL_INTERPOSABLE)
5594	{
5595	d = get_cg_data (node: &node, traverse_aliases: true);
5596	if (is_tm_safe (x: node->decl))
5597	ipa_tm_diagnose_tm_safe (node);
5598	else if (d->all_tm_regions)
5599	ipa_tm_diagnose_transaction (node, all_tm_regions: d->all_tm_regions);
5600	}
5601
5602	/* Create clones. Do those that are not irrevocable and have a
5603	positive call count. Do those publicly visible functions that
5604	the user directed us to clone. */
5605	for (i = 0; i < tm_callees.length (); ++i)
5606	{
5607	bool doit = false;
5608
5609	node = tm_callees[i];
5610	if (node->cpp_implicit_alias)
5611	continue;
5612
5613	a = node->get_availability ();
5614	d = get_cg_data (node: &node, traverse_aliases: true);
5615
5616	if (a <= AVAIL_NOT_AVAILABLE)
5617	doit = is_tm_callable (x: node->decl);
5618	else if (a <= AVAIL_AVAILABLE && is_tm_callable (x: node->decl))
5619	doit = true;
5620	else if (!d->is_irrevocable
5621	&& d->tm_callers_normal + d->tm_callers_clone > 0)
5622	doit = true;
5623
5624	if (doit)
5625	ipa_tm_create_version (old_node: node);
5626	}
5627
5628	/* Redirect calls to the new clones, and insert irrevocable marks. */
5629	for (i = 0; i < tm_callees.length (); ++i)
5630	{
5631	node = tm_callees[i];
5632	if (node->analyzed)
5633	{
5634	d = get_cg_data (node: &node, traverse_aliases: true);
5635	if (d->clone)
5636	ipa_tm_transform_clone (node);
5637	}
5638	}
5639	FOR_EACH_DEFINED_FUNCTION (node)
5640	if (node->lowered
5641	&& node->get_availability () >= AVAIL_INTERPOSABLE)
5642	{
5643	d = get_cg_data (node: &node, traverse_aliases: true);
5644	if (d->all_tm_regions)
5645	ipa_tm_transform_transaction (node);
5646	}
5647
5648	/* Free and clear all data structures. */
5649	tm_callees.release ();
5650	irr_worklist.release ();
5651	bitmap_obstack_release (&tm_obstack);
5652	free_original_copy_tables ();
5653
5654	FOR_EACH_FUNCTION (node)
5655	node->aux = NULL;
5656
5657	cgraph_node::checking_verify_cgraph_nodes ();
5658
5659	return 0;
5660	}
5661
5662	namespace {
5663
5664	const pass_data pass_data_ipa_tm =
5665	{
5666	.type: SIMPLE_IPA_PASS, /* type */
5667	.name: "tmipa", /* name */
5668	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
5669	.tv_id: TV_TRANS_MEM, /* tv_id */
5670	.properties_required: ( PROP_ssa | PROP_cfg ), /* properties_required */
5671	.properties_provided: 0, /* properties_provided */
5672	.properties_destroyed: 0, /* properties_destroyed */
5673	.todo_flags_start: 0, /* todo_flags_start */
5674	.todo_flags_finish: 0, /* todo_flags_finish */
5675	};
5676
5677	class pass_ipa_tm : public simple_ipa_opt_pass
5678	{
5679	public:
5680	pass_ipa_tm (gcc::context *ctxt)
5681	: simple_ipa_opt_pass (pass_data_ipa_tm, ctxt)
5682	{}
5683
5684	/* opt_pass methods: */
5685	bool gate (function *) final override { return flag_tm; }
5686	unsigned int execute (function *) final override { return ipa_tm_execute (); }
5687
5688	}; // class pass_ipa_tm
5689
5690	} // anon namespace
5691
5692	simple_ipa_opt_pass *
5693	make_pass_ipa_tm (gcc::context *ctxt)
5694	{
5695	return new pass_ipa_tm (ctxt);
5696	}
5697
5698	#include "gt-trans-mem.h"
5699