1	/* Passes for transactional memory support.
2	Copyright (C) 2008-2025 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 if (TREE_CODE (rhs) == CONSTRUCTOR
2445	&& CONSTRUCTOR_NELTS (rhs) == 0)
2446	{
2447	/* Don't take address of an empty CONSTRUCTOR, it might not
2448	work for C++ non-POD constructors at all and otherwise
2449	would be inefficient. Use tm memset to clear lhs. */
2450	gcc_assert (!load_p && store_p);
2451	rhs_addr = integer_zero_node;
2452	}
2453	else
2454	rhs_addr = gimplify_addr (gsi, x: rhs);
2455
2456	// Choose the appropriate memory transfer function.
2457	if (store_p
2458	&& TREE_CODE (rhs) == CONSTRUCTOR
2459	&& CONSTRUCTOR_NELTS (rhs) == 0)
2460	copy_fn = builtin_decl_explicit (fncode: BUILT_IN_TM_MEMSET);
2461	else if (load_p && store_p)
2462	// ??? Figure out if there's any possible overlap between
2463	// the LHS and the RHS and if not, use MEMCPY.
2464	copy_fn = builtin_decl_explicit (fncode: BUILT_IN_TM_MEMMOVE);
2465	else if (load_p)
2466	// Note that the store is non-transactional and cannot overlap.
2467	copy_fn = builtin_decl_explicit (fncode: BUILT_IN_TM_MEMCPY_RTWN);
2468	else
2469	// Note that the load is non-transactional and cannot overlap.
2470	copy_fn = builtin_decl_explicit (fncode: BUILT_IN_TM_MEMCPY_RNWT);
2471
2472	gcall = gimple_build_call (copy_fn, 3, lhs_addr, rhs_addr,
2473	TYPE_SIZE_UNIT (TREE_TYPE (lhs)));
2474	gimple_set_location (g: gcall, location: loc);
2475	gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2476
2477	if (ltmp)
2478	{
2479	gcall = gimple_build_assign (lhs, ltmp);
2480	gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2481	}
2482	}
2483
2484	// Now that we have the load/store in its instrumented form, add
2485	// thread private addresses to the log if applicable.
2486	if (!store_p)
2487	requires_barrier (entry_block: region->entry_block, x: lhs, stmt: gcall);
2488	}
2489
2490
2491	/* Expand a call statement as appropriate for a transaction. That is,
2492	either verify that the call does not affect the transaction, or
2493	redirect the call to a clone that handles transactions, or change
2494	the transaction state to IRREVOCABLE. Return true if the call is
2495	one of the builtins that end a transaction. */
2496
2497	static bool
2498	expand_call_tm (struct tm_region *region,
2499	gimple_stmt_iterator *gsi)
2500	{
2501	gcall *stmt = as_a <gcall *> (p: gsi_stmt (i: *gsi));
2502	tree lhs = gimple_call_lhs (gs: stmt);
2503	tree fn_decl;
2504	struct cgraph_node *node;
2505	bool retval = false;
2506
2507	fn_decl = gimple_call_fndecl (gs: stmt);
2508
2509	if (fn_decl == builtin_decl_explicit (fncode: BUILT_IN_TM_MEMCPY)
2510	|| fn_decl == builtin_decl_explicit (fncode: BUILT_IN_TM_MEMMOVE))
2511	transaction_subcode_ior (region, GTMA_HAVE_STORE | GTMA_HAVE_LOAD);
2512	if (fn_decl == builtin_decl_explicit (fncode: BUILT_IN_TM_MEMSET))
2513	transaction_subcode_ior (region, GTMA_HAVE_STORE);
2514
2515	if (is_tm_pure_call (call: stmt))
2516	return false;
2517
2518	if (fn_decl)
2519	retval = is_tm_ending_fndecl (fndecl: fn_decl);
2520	if (!retval)
2521	{
2522	/* Assume all non-const/pure calls write to memory, except
2523	transaction ending builtins. */
2524	transaction_subcode_ior (region, GTMA_HAVE_STORE);
2525	}
2526
2527	/* For indirect calls, we already generated a call into the runtime. */
2528	if (!fn_decl)
2529	{
2530	tree fn = gimple_call_fn (gs: stmt);
2531
2532	/* We are guaranteed never to go irrevocable on a safe or pure
2533	call, and the pure call was handled above. */
2534	if (is_tm_safe (x: fn))
2535	return false;
2536	else
2537	transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
2538
2539	return false;
2540	}
2541
2542	node = cgraph_node::get (decl: fn_decl);
2543	/* All calls should have cgraph here. */
2544	if (!node)
2545	{
2546	/* We can have a nodeless call here if some pass after IPA-tm
2547	added uninstrumented calls. For example, loop distribution
2548	can transform certain loop constructs into __builtin_mem*
2549	calls. In this case, see if we have a suitable TM
2550	replacement and fill in the gaps. */
2551	gcc_assert (DECL_BUILT_IN_CLASS (fn_decl) == BUILT_IN_NORMAL);
2552	enum built_in_function code = DECL_FUNCTION_CODE (decl: fn_decl);
2553	gcc_assert (code == BUILT_IN_MEMCPY
2554	|| code == BUILT_IN_MEMMOVE
2555	|| code == BUILT_IN_MEMSET);
2556
2557	tree repl = find_tm_replacement_function (fndecl: fn_decl);
2558	if (repl)
2559	{
2560	gimple_call_set_fndecl (gs: stmt, decl: repl);
2561	update_stmt (s: stmt);
2562	node = cgraph_node::create (decl: repl);
2563	node->tm_may_enter_irr = false;
2564	return expand_call_tm (region, gsi);
2565	}
2566	gcc_unreachable ();
2567	}
2568	if (node->tm_may_enter_irr)
2569	transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
2570
2571	if (is_tm_abort (fndecl: fn_decl))
2572	{
2573	transaction_subcode_ior (region, GTMA_HAVE_ABORT);
2574	return true;
2575	}
2576
2577	/* Instrument the store if needed.
2578
2579	If the assignment happens inside the function call (return slot
2580	optimization), there is no instrumentation to be done, since
2581	the callee should have done the right thing. */
2582	if (lhs && requires_barrier (entry_block: region->entry_block, x: lhs, stmt)
2583	&& !gimple_call_return_slot_opt_p (s: stmt))
2584	{
2585	tree tmp = create_tmp_reg (TREE_TYPE (lhs));
2586	location_t loc = gimple_location (g: stmt);
2587	edge fallthru_edge = NULL;
2588	gassign *assign_stmt;
2589
2590	/* Remember if the call was going to throw. */
2591	if (stmt_can_throw_internal (cfun, stmt))
2592	{
2593	edge_iterator ei;
2594	edge e;
2595	basic_block bb = gimple_bb (g: stmt);
2596
2597	FOR_EACH_EDGE (e, ei, bb->succs)
2598	if (e->flags & EDGE_FALLTHRU)
2599	{
2600	fallthru_edge = e;
2601	break;
2602	}
2603	}
2604
2605	gimple_call_set_lhs (gs: stmt, lhs: tmp);
2606	update_stmt (s: stmt);
2607	assign_stmt = gimple_build_assign (lhs, tmp);
2608	gimple_set_location (g: assign_stmt, location: loc);
2609
2610	/* We cannot throw in the middle of a BB. If the call was going
2611	to throw, place the instrumentation on the fallthru edge, so
2612	the call remains the last statement in the block. */
2613	if (fallthru_edge)
2614	{
2615	gimple_seq fallthru_seq = gimple_seq_alloc_with_stmt (stmt: assign_stmt);
2616	gimple_stmt_iterator fallthru_gsi = gsi_start (seq&: fallthru_seq);
2617	expand_assign_tm (region, gsi: &fallthru_gsi);
2618	gsi_insert_seq_on_edge (fallthru_edge, fallthru_seq);
2619	pending_edge_inserts_p = true;
2620	}
2621	else
2622	{
2623	gsi_insert_after (gsi, assign_stmt, GSI_CONTINUE_LINKING);
2624	expand_assign_tm (region, gsi);
2625	}
2626
2627	transaction_subcode_ior (region, GTMA_HAVE_STORE);
2628	}
2629
2630	return retval;
2631	}
2632
2633
2634	/* Expand all statements in BB as appropriate for being inside
2635	a transaction. */
2636
2637	static void
2638	expand_block_tm (struct tm_region *region, basic_block bb)
2639	{
2640	gimple_stmt_iterator gsi;
2641
2642	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); )
2643	{
2644	gimple *stmt = gsi_stmt (i: gsi);
2645	switch (gimple_code (g: stmt))
2646	{
2647	case GIMPLE_ASSIGN:
2648	/* Only memory reads/writes need to be instrumented. */
2649	if (gimple_assign_single_p (gs: stmt)
2650	&& !gimple_clobber_p (s: stmt))
2651	{
2652	expand_assign_tm (region, gsi: &gsi);
2653	continue;
2654	}
2655	break;
2656
2657	case GIMPLE_CALL:
2658	if (expand_call_tm (region, gsi: &gsi))
2659	return;
2660	break;
2661
2662	case GIMPLE_ASM:
2663	gcc_unreachable ();
2664
2665	default:
2666	break;
2667	}
2668	if (!gsi_end_p (i: gsi))
2669	gsi_next (i: &gsi);
2670	}
2671	}
2672
2673	/* Return the list of basic-blocks in REGION.
2674
2675	STOP_AT_IRREVOCABLE_P is true if caller is uninterested in blocks
2676	following a TM_IRREVOCABLE call.
2677
2678	INCLUDE_UNINSTRUMENTED_P is TRUE if we should include the
2679	uninstrumented code path blocks in the list of basic blocks
2680	returned, false otherwise. */
2681
2682	static vec<basic_block>
2683	get_tm_region_blocks (basic_block entry_block,
2684	bitmap exit_blocks,
2685	bitmap irr_blocks,
2686	bitmap all_region_blocks,
2687	bool stop_at_irrevocable_p,
2688	bool include_uninstrumented_p = true)
2689	{
2690	vec<basic_block> bbs = vNULL;
2691	unsigned i;
2692	edge e;
2693	edge_iterator ei;
2694	bitmap visited_blocks = BITMAP_ALLOC (NULL);
2695
2696	i = 0;
2697	bbs.safe_push (obj: entry_block);
2698	bitmap_set_bit (visited_blocks, entry_block->index);
2699
2700	do
2701	{
2702	basic_block bb = bbs[i++];
2703
2704	if (exit_blocks &&
2705	bitmap_bit_p (exit_blocks, bb->index))
2706	continue;
2707
2708	if (stop_at_irrevocable_p
2709	&& irr_blocks
2710	&& bitmap_bit_p (irr_blocks, bb->index))
2711	continue;
2712
2713	FOR_EACH_EDGE (e, ei, bb->succs)
2714	if ((include_uninstrumented_p
2715	|| !(e->flags & EDGE_TM_UNINSTRUMENTED))
2716	&& !bitmap_bit_p (visited_blocks, e->dest->index))
2717	{
2718	bitmap_set_bit (visited_blocks, e->dest->index);
2719	bbs.safe_push (obj: e->dest);
2720	}
2721	}
2722	while (i < bbs.length ());
2723
2724	if (all_region_blocks)
2725	bitmap_ior_into (all_region_blocks, visited_blocks);
2726
2727	BITMAP_FREE (visited_blocks);
2728	return bbs;
2729	}
2730
2731	// Callback data for collect_bb2reg.
2732	struct bb2reg_stuff
2733	{
2734	vec<tm_region *> *bb2reg;
2735	bool include_uninstrumented_p;
2736	};
2737
2738	// Callback for expand_regions, collect innermost region data for each bb.
2739	static void *
2740	collect_bb2reg (struct tm_region *region, void *data)
2741	{
2742	struct bb2reg_stuff *stuff = (struct bb2reg_stuff *)data;
2743	vec<tm_region *> *bb2reg = stuff->bb2reg;
2744	vec<basic_block> queue;
2745	unsigned int i;
2746	basic_block bb;
2747
2748	queue = get_tm_region_blocks (entry_block: region->entry_block,
2749	exit_blocks: region->exit_blocks,
2750	irr_blocks: region->irr_blocks,
2751	NULL,
2752	/*stop_at_irr_p=*/stop_at_irrevocable_p: true,
2753	include_uninstrumented_p: stuff->include_uninstrumented_p);
2754
2755	// We expect expand_region to perform a post-order traversal of the region
2756	// tree. Therefore the last region seen for any bb is the innermost.
2757	FOR_EACH_VEC_ELT (queue, i, bb)
2758	(*bb2reg)[bb->index] = region;
2759
2760	queue.release ();
2761	return NULL;
2762	}
2763
2764	// Returns a vector, indexed by BB->INDEX, of the innermost tm_region to
2765	// which a basic block belongs. Note that we only consider the instrumented
2766	// code paths for the region; the uninstrumented code paths are ignored if
2767	// INCLUDE_UNINSTRUMENTED_P is false.
2768	//
2769	// ??? This data is very similar to the bb_regions array that is collected
2770	// during tm_region_init. Or, rather, this data is similar to what could
2771	// be used within tm_region_init. The actual computation in tm_region_init
2772	// begins and ends with bb_regions entirely full of NULL pointers, due to
2773	// the way in which pointers are swapped in and out of the array.
2774	//
2775	// ??? Our callers expect that blocks are not shared between transactions.
2776	// When the optimizers get too smart, and blocks are shared, then during
2777	// the tm_mark phase we'll add log entries to only one of the two transactions,
2778	// and in the tm_edge phase we'll add edges to the CFG that create invalid
2779	// cycles. The symptom being SSA defs that do not dominate their uses.
2780	// Note that the optimizers were locally correct with their transformation,
2781	// as we have no info within the program that suggests that the blocks cannot
2782	// be shared.
2783	//
2784	// ??? There is currently a hack inside tree-ssa-pre.cc to work around the
2785	// only known instance of this block sharing.
2786
2787	static vec<tm_region *>
2788	get_bb_regions_instrumented (bool traverse_clones,
2789	bool include_uninstrumented_p)
2790	{
2791	unsigned n = last_basic_block_for_fn (cfun);
2792	struct bb2reg_stuff stuff;
2793	vec<tm_region *> ret;
2794
2795	ret.create (nelems: n);
2796	ret.safe_grow_cleared (len: n, exact: true);
2797	stuff.bb2reg = &ret;
2798	stuff.include_uninstrumented_p = include_uninstrumented_p;
2799	expand_regions (all_tm_regions, callback: collect_bb2reg, &stuff, traverse_clones);
2800
2801	return ret;
2802	}
2803
2804	/* Set the IN_TRANSACTION for all gimple statements that appear in a
2805	transaction. */
2806
2807	void
2808	compute_transaction_bits (void)
2809	{
2810	struct tm_region *region;
2811	vec<basic_block> queue;
2812	unsigned int i;
2813	basic_block bb;
2814
2815	/* ?? Perhaps we need to abstract gate_tm_init further, because we
2816	certainly don't need it to calculate CDI_DOMINATOR info. */
2817	gate_tm_init ();
2818
2819	FOR_EACH_BB_FN (bb, cfun)
2820	bb->flags &= ~BB_IN_TRANSACTION;
2821
2822	for (region = all_tm_regions; region; region = region->next)
2823	{
2824	queue = get_tm_region_blocks (entry_block: region->entry_block,
2825	exit_blocks: region->exit_blocks,
2826	irr_blocks: region->irr_blocks,
2827	NULL,
2828	/*stop_at_irr_p=*/stop_at_irrevocable_p: true);
2829	for (i = 0; queue.iterate (ix: i, ptr: &bb); ++i)
2830	bb->flags |= BB_IN_TRANSACTION;
2831	queue.release ();
2832	}
2833
2834	if (all_tm_regions)
2835	bitmap_obstack_release (&tm_obstack);
2836	}
2837
2838	/* Replace the GIMPLE_TRANSACTION in this region with the corresponding
2839	call to BUILT_IN_TM_START. */
2840
2841	static void *
2842	expand_transaction (struct tm_region *region, void *data ATTRIBUTE_UNUSED)
2843	{
2844	tree tm_start = builtin_decl_explicit (fncode: BUILT_IN_TM_START);
2845	basic_block transaction_bb = gimple_bb (g: region->transaction_stmt);
2846	tree tm_state = region->tm_state;
2847	tree tm_state_type = TREE_TYPE (tm_state);
2848	edge abort_edge = NULL;
2849	edge inst_edge = NULL;
2850	edge uninst_edge = NULL;
2851	edge fallthru_edge = NULL;
2852
2853	// Identify the various successors of the transaction start.
2854	{
2855	edge_iterator i;
2856	edge e;
2857	FOR_EACH_EDGE (e, i, transaction_bb->succs)
2858	{
2859	if (e->flags & EDGE_TM_ABORT)
2860	abort_edge = e;
2861	else if (e->flags & EDGE_TM_UNINSTRUMENTED)
2862	uninst_edge = e;
2863	else
2864	inst_edge = e;
2865	if (e->flags & EDGE_FALLTHRU)
2866	fallthru_edge = e;
2867	}
2868	}
2869
2870	/* ??? There are plenty of bits here we're not computing. */
2871	{
2872	int subcode = gimple_transaction_subcode (transaction_stmt: region->get_transaction_stmt ());
2873	int flags = 0;
2874	if (subcode & GTMA_DOES_GO_IRREVOCABLE)
2875	flags |= PR_DOESGOIRREVOCABLE;
2876	if ((subcode & GTMA_MAY_ENTER_IRREVOCABLE) == 0)
2877	flags |= PR_HASNOIRREVOCABLE;
2878	/* If the transaction does not have an abort in lexical scope and is not
2879	marked as an outer transaction, then it will never abort. */
2880	if ((subcode & GTMA_HAVE_ABORT) == 0 && (subcode & GTMA_IS_OUTER) == 0)
2881	flags |= PR_HASNOABORT;
2882	if ((subcode & GTMA_HAVE_STORE) == 0)
2883	flags |= PR_READONLY;
2884	if (inst_edge && !(subcode & GTMA_HAS_NO_INSTRUMENTATION))
2885	flags |= PR_INSTRUMENTEDCODE;
2886	if (uninst_edge)
2887	flags |= PR_UNINSTRUMENTEDCODE;
2888	if (subcode & GTMA_IS_OUTER)
2889	region->original_transaction_was_outer = true;
2890	tree t = build_int_cst (tm_state_type, flags);
2891	gcall *call = gimple_build_call (tm_start, 1, t);
2892	gimple_call_set_lhs (gs: call, lhs: tm_state);
2893	gimple_set_location (g: call, location: gimple_location (g: region->transaction_stmt));
2894
2895	// Replace the GIMPLE_TRANSACTION with the call to BUILT_IN_TM_START.
2896	gimple_stmt_iterator gsi = gsi_last_bb (bb: transaction_bb);
2897	gcc_assert (gsi_stmt (gsi) == region->transaction_stmt);
2898	gsi_insert_before (&gsi, call, GSI_SAME_STMT);
2899	gsi_remove (&gsi, true);
2900	region->transaction_stmt = call;
2901	}
2902
2903	// Generate log saves.
2904	if (!tm_log_save_addresses.is_empty ())
2905	tm_log_emit_saves (entry_block: region->entry_block, bb: transaction_bb);
2906
2907	// In the beginning, we've no tests to perform on transaction restart.
2908	// Note that after this point, transaction_bb becomes the "most recent
2909	// block containing tests for the transaction".
2910	region->restart_block = region->entry_block;
2911
2912	// Generate log restores.
2913	if (!tm_log_save_addresses.is_empty ())
2914	{
2915	basic_block test_bb = create_empty_bb (transaction_bb);
2916	basic_block code_bb = create_empty_bb (test_bb);
2917	basic_block join_bb = create_empty_bb (code_bb);
2918	add_bb_to_loop (test_bb, transaction_bb->loop_father);
2919	add_bb_to_loop (code_bb, transaction_bb->loop_father);
2920	add_bb_to_loop (join_bb, transaction_bb->loop_father);
2921	if (region->restart_block == region->entry_block)
2922	region->restart_block = test_bb;
2923
2924	tree t1 = create_tmp_reg (tm_state_type);
2925	tree t2 = build_int_cst (tm_state_type, A_RESTORELIVEVARIABLES);
2926	gimple *stmt = gimple_build_assign (t1, BIT_AND_EXPR, tm_state, t2);
2927	gimple_stmt_iterator gsi = gsi_last_bb (bb: test_bb);
2928	gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
2929
2930	t2 = build_int_cst (tm_state_type, 0);
2931	stmt = gimple_build_cond (NE_EXPR, t1, t2, NULL, NULL);
2932	gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
2933
2934	tm_log_emit_restores (entry_block: region->entry_block, bb: code_bb);
2935
2936	edge ei = make_edge (transaction_bb, test_bb, EDGE_FALLTHRU);
2937	edge et = make_edge (test_bb, code_bb, EDGE_TRUE_VALUE);
2938	edge ef = make_edge (test_bb, join_bb, EDGE_FALSE_VALUE);
2939	redirect_edge_pred (fallthru_edge, join_bb);
2940
2941	join_bb->count = test_bb->count = transaction_bb->count;
2942
2943	ei->probability = profile_probability::always ();
2944	et->probability = profile_probability::likely ();
2945	ef->probability = profile_probability::unlikely ();
2946
2947	code_bb->count = et->count ();
2948
2949	transaction_bb = join_bb;
2950	}
2951
2952	// If we have an ABORT edge, create a test to perform the abort.
2953	if (abort_edge)
2954	{
2955	basic_block test_bb = create_empty_bb (transaction_bb);
2956	add_bb_to_loop (test_bb, transaction_bb->loop_father);
2957	if (region->restart_block == region->entry_block)
2958	region->restart_block = test_bb;
2959
2960	tree t1 = create_tmp_reg (tm_state_type);
2961	tree t2 = build_int_cst (tm_state_type, A_ABORTTRANSACTION);
2962	gimple *stmt = gimple_build_assign (t1, BIT_AND_EXPR, tm_state, t2);
2963	gimple_stmt_iterator gsi = gsi_last_bb (bb: test_bb);
2964	gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
2965
2966	t2 = build_int_cst (tm_state_type, 0);
2967	stmt = gimple_build_cond (NE_EXPR, t1, t2, NULL, NULL);
2968	gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
2969
2970	edge ei = make_edge (transaction_bb, test_bb, EDGE_FALLTHRU);
2971	test_bb->count = transaction_bb->count;
2972	ei->probability = profile_probability::always ();
2973
2974	// Not abort edge. If both are live, chose one at random as we'll
2975	// we'll be fixing that up below.
2976	redirect_edge_pred (fallthru_edge, test_bb);
2977	fallthru_edge->flags = EDGE_FALSE_VALUE;
2978	fallthru_edge->probability = profile_probability::very_likely ();
2979
2980	// Abort/over edge.
2981	redirect_edge_pred (abort_edge, test_bb);
2982	abort_edge->flags = EDGE_TRUE_VALUE;
2983	abort_edge->probability = profile_probability::unlikely ();
2984
2985	transaction_bb = test_bb;
2986	}
2987
2988	// If we have both instrumented and uninstrumented code paths, select one.
2989	if (inst_edge && uninst_edge)
2990	{
2991	basic_block test_bb = create_empty_bb (transaction_bb);
2992	add_bb_to_loop (test_bb, transaction_bb->loop_father);
2993	if (region->restart_block == region->entry_block)
2994	region->restart_block = test_bb;
2995
2996	tree t1 = create_tmp_reg (tm_state_type);
2997	tree t2 = build_int_cst (tm_state_type, A_RUNUNINSTRUMENTEDCODE);
2998
2999	gimple *stmt = gimple_build_assign (t1, BIT_AND_EXPR, tm_state, t2);
3000	gimple_stmt_iterator gsi = gsi_last_bb (bb: test_bb);
3001	gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
3002
3003	t2 = build_int_cst (tm_state_type, 0);
3004	stmt = gimple_build_cond (NE_EXPR, t1, t2, NULL, NULL);
3005	gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
3006
3007	// Create the edge into test_bb first, as we want to copy values
3008	// out of the fallthru edge.
3009	edge e = make_edge (transaction_bb, test_bb, fallthru_edge->flags);
3010	e->probability = fallthru_edge->probability;
3011	test_bb->count = fallthru_edge->count ();
3012
3013	// Now update the edges to the inst/uninist implementations.
3014	// For now assume that the paths are equally likely. When using HTM,
3015	// we'll try the uninst path first and fallback to inst path if htm
3016	// buffers are exceeded. Without HTM we start with the inst path and
3017	// use the uninst path when falling back to serial mode.
3018	redirect_edge_pred (inst_edge, test_bb);
3019	inst_edge->flags = EDGE_FALSE_VALUE;
3020	inst_edge->probability = profile_probability::even ();
3021
3022	redirect_edge_pred (uninst_edge, test_bb);
3023	uninst_edge->flags = EDGE_TRUE_VALUE;
3024	uninst_edge->probability = profile_probability::even ();
3025	}
3026
3027	// If we have no previous special cases, and we have PHIs at the beginning
3028	// of the atomic region, this means we have a loop at the beginning of the
3029	// atomic region that shares the first block. This can cause problems with
3030	// the transaction restart abnormal edges to be added in the tm_edges pass.
3031	// Solve this by adding a new empty block to receive the abnormal edges.
3032	if (region->restart_block == region->entry_block
3033	&& phi_nodes (bb: region->entry_block))
3034	{
3035	basic_block empty_bb = create_empty_bb (transaction_bb);
3036	region->restart_block = empty_bb;
3037	add_bb_to_loop (empty_bb, transaction_bb->loop_father);
3038
3039	redirect_edge_pred (fallthru_edge, empty_bb);
3040	make_edge (transaction_bb, empty_bb, EDGE_FALLTHRU);
3041	}
3042
3043	return NULL;
3044	}
3045
3046	/* Generate the temporary to be used for the return value of
3047	BUILT_IN_TM_START. */
3048
3049	static void *
3050	generate_tm_state (struct tm_region *region, void *data ATTRIBUTE_UNUSED)
3051	{
3052	tree tm_start = builtin_decl_explicit (fncode: BUILT_IN_TM_START);
3053	region->tm_state =
3054	create_tmp_reg (TREE_TYPE (TREE_TYPE (tm_start)), "tm_state");
3055
3056	// Reset the subcode, post optimizations. We'll fill this in
3057	// again as we process blocks.
3058	if (region->exit_blocks)
3059	{
3060	gtransaction *transaction_stmt = region->get_transaction_stmt ();
3061	unsigned int subcode = gimple_transaction_subcode (transaction_stmt);
3062
3063	if (subcode & GTMA_DOES_GO_IRREVOCABLE)
3064	subcode &= (GTMA_DECLARATION_MASK | GTMA_DOES_GO_IRREVOCABLE
3065	| GTMA_MAY_ENTER_IRREVOCABLE
3066	| GTMA_HAS_NO_INSTRUMENTATION);
3067	else
3068	subcode &= GTMA_DECLARATION_MASK;
3069	gimple_transaction_set_subcode (transaction_stmt, subcode);
3070	}
3071
3072	return NULL;
3073	}
3074
3075	// Propagate flags from inner transactions outwards.
3076	static void
3077	propagate_tm_flags_out (struct tm_region *region)
3078	{
3079	if (region == NULL)
3080	return;
3081	propagate_tm_flags_out (region: region->inner);
3082
3083	if (region->outer && region->outer->transaction_stmt)
3084	{
3085	unsigned s
3086	= gimple_transaction_subcode (transaction_stmt: region->get_transaction_stmt ());
3087	s &= (GTMA_HAVE_ABORT | GTMA_HAVE_LOAD | GTMA_HAVE_STORE
3088	| GTMA_MAY_ENTER_IRREVOCABLE);
3089	s |= gimple_transaction_subcode (transaction_stmt: region->outer->get_transaction_stmt ());
3090	gimple_transaction_set_subcode (transaction_stmt: region->outer->get_transaction_stmt (),
3091	subcode: s);
3092	}
3093
3094	propagate_tm_flags_out (region: region->next);
3095	}
3096
3097	/* Entry point to the MARK phase of TM expansion. Here we replace
3098	transactional memory statements with calls to builtins, and function
3099	calls with their transactional clones (if available). But we don't
3100	yet lower GIMPLE_TRANSACTION or add the transaction restart back-edges. */
3101
3102	static unsigned int
3103	execute_tm_mark (void)
3104	{
3105	pending_edge_inserts_p = false;
3106
3107	expand_regions (all_tm_regions, callback: generate_tm_state, NULL,
3108	/*traverse_clones=*/true);
3109
3110	tm_log_init ();
3111
3112	vec<tm_region *> bb_regions
3113	= get_bb_regions_instrumented (/*traverse_clones=*/true,
3114	/*include_uninstrumented_p=*/false);
3115	struct tm_region *r;
3116	unsigned i;
3117
3118	// Expand memory operations into calls into the runtime.
3119	// This collects log entries as well.
3120	FOR_EACH_VEC_ELT (bb_regions, i, r)
3121	{
3122	if (r != NULL)
3123	{
3124	if (r->transaction_stmt)
3125	{
3126	unsigned sub
3127	= gimple_transaction_subcode (transaction_stmt: r->get_transaction_stmt ());
3128
3129	/* If we're sure to go irrevocable, there won't be
3130	anything to expand, since the run-time will go
3131	irrevocable right away. */
3132	if (sub & GTMA_DOES_GO_IRREVOCABLE
3133	&& sub & GTMA_MAY_ENTER_IRREVOCABLE)
3134	continue;
3135	}
3136	expand_block_tm (region: r, BASIC_BLOCK_FOR_FN (cfun, i));
3137	}
3138	}
3139
3140	bb_regions.release ();
3141
3142	// Propagate flags from inner transactions outwards.
3143	propagate_tm_flags_out (region: all_tm_regions);
3144
3145	// Expand GIMPLE_TRANSACTIONs into calls into the runtime.
3146	expand_regions (all_tm_regions, callback: expand_transaction, NULL,
3147	/*traverse_clones=*/false);
3148
3149	tm_log_emit ();
3150	tm_log_delete ();
3151
3152	if (pending_edge_inserts_p)
3153	gsi_commit_edge_inserts ();
3154	free_dominance_info (CDI_DOMINATORS);
3155	return 0;
3156	}
3157
3158	namespace {
3159
3160	const pass_data pass_data_tm_mark =
3161	{
3162	.type: GIMPLE_PASS, /* type */
3163	.name: "tmmark", /* name */
3164	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
3165	.tv_id: TV_TRANS_MEM, /* tv_id */
3166	.properties_required: ( PROP_ssa | PROP_cfg ), /* properties_required */
3167	.properties_provided: 0, /* properties_provided */
3168	.properties_destroyed: 0, /* properties_destroyed */
3169	.todo_flags_start: 0, /* todo_flags_start */
3170	TODO_update_ssa, /* todo_flags_finish */
3171	};
3172
3173	class pass_tm_mark : public gimple_opt_pass
3174	{
3175	public:
3176	pass_tm_mark (gcc::context *ctxt)
3177	: gimple_opt_pass (pass_data_tm_mark, ctxt)
3178	{}
3179
3180	/* opt_pass methods: */
3181	unsigned int execute (function *) final override
3182	{
3183	return execute_tm_mark ();
3184	}
3185
3186	}; // class pass_tm_mark
3187
3188	} // anon namespace
3189
3190	gimple_opt_pass *
3191	make_pass_tm_mark (gcc::context *ctxt)
3192	{
3193	return new pass_tm_mark (ctxt);
3194	}
3195
3196
3197	/* Create an abnormal edge from STMT at iter, splitting the block
3198	as necessary. Adjust *PNEXT as needed for the split block. */
3199
3200	static inline void
3201	split_bb_make_tm_edge (gimple *stmt, basic_block dest_bb,
3202	gimple_stmt_iterator iter, gimple_stmt_iterator *pnext)
3203	{
3204	basic_block bb = gimple_bb (g: stmt);
3205	if (!gsi_one_before_end_p (i: iter))
3206	{
3207	edge e = split_block (bb, stmt);
3208	*pnext = gsi_start_bb (bb: e->dest);
3209	}
3210	edge e = make_edge (bb, dest_bb, EDGE_ABNORMAL);
3211	if (e)
3212	e->probability = profile_probability::guessed_never ();
3213
3214	// Record the need for the edge for the benefit of the rtl passes.
3215	if (cfun->gimple_df->tm_restart == NULL)
3216	cfun->gimple_df->tm_restart
3217	= hash_table<tm_restart_hasher>::create_ggc (n: 31);
3218
3219	struct tm_restart_node dummy;
3220	dummy.stmt = stmt;
3221	dummy.label_or_list = gimple_block_label (dest_bb);
3222
3223	tm_restart_node **slot = cfun->gimple_df->tm_restart->find_slot (value: &dummy,
3224	insert: INSERT);
3225	struct tm_restart_node *n = *slot;
3226	if (n == NULL)
3227	{
3228	*slot = n = ggc_alloc<tm_restart_node> ();
3229	*n = dummy;
3230	}
3231	else
3232	{
3233	tree old = n->label_or_list;
3234	if (TREE_CODE (old) == LABEL_DECL)
3235	old = tree_cons (NULL, old, NULL);
3236	n->label_or_list = tree_cons (NULL, dummy.label_or_list, old);
3237	}
3238	}
3239
3240	/* Split block BB as necessary for every builtin function we added, and
3241	wire up the abnormal back edges implied by the transaction restart. */
3242
3243	static void
3244	expand_block_edges (struct tm_region *const region, basic_block bb)
3245	{
3246	gimple_stmt_iterator gsi, next_gsi;
3247
3248	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi = next_gsi)
3249	{
3250	gimple *stmt = gsi_stmt (i: gsi);
3251	gcall *call_stmt;
3252
3253	next_gsi = gsi;
3254	gsi_next (i: &next_gsi);
3255
3256	// ??? Shouldn't we split for any non-pure, non-irrevocable function?
3257	call_stmt = dyn_cast <gcall *> (p: stmt);
3258	if ((!call_stmt)
3259	|| (gimple_call_flags (call_stmt) & ECF_TM_BUILTIN) == 0)
3260	continue;
3261
3262	if (gimple_call_builtin_p (call_stmt, BUILT_IN_TM_ABORT))
3263	{
3264	// If we have a ``_transaction_cancel [[outer]]'', there is only
3265	// one abnormal edge: to the transaction marked OUTER.
3266	// All compiler-generated instances of BUILT_IN_TM_ABORT have a
3267	// constant argument, which we can examine here. Users invoking
3268	// TM_ABORT directly get what they deserve.
3269	tree arg = gimple_call_arg (gs: call_stmt, index: 0);
3270	if (TREE_CODE (arg) == INTEGER_CST
3271	&& (TREE_INT_CST_LOW (arg) & AR_OUTERABORT) != 0
3272	&& !decl_is_tm_clone (fndecl: current_function_decl))
3273	{
3274	// Find the GTMA_IS_OUTER transaction.
3275	for (struct tm_region *o = region; o; o = o->outer)
3276	if (o->original_transaction_was_outer)
3277	{
3278	split_bb_make_tm_edge (stmt: call_stmt, dest_bb: o->restart_block,
3279	iter: gsi, pnext: &next_gsi);
3280	break;
3281	}
3282
3283	// Otherwise, the front-end should have semantically checked
3284	// outer aborts, but in either case the target region is not
3285	// within this function.
3286	continue;
3287	}
3288
3289	// Non-outer, TM aborts have an abnormal edge to the inner-most
3290	// transaction, the one being aborted;
3291	split_bb_make_tm_edge (stmt: call_stmt, dest_bb: region->restart_block, iter: gsi,
3292	pnext: &next_gsi);
3293	}
3294
3295	// All TM builtins have an abnormal edge to the outer-most transaction.
3296	// We never restart inner transactions. For tm clones, we know a-priori
3297	// that the outer-most transaction is outside the function.
3298	if (decl_is_tm_clone (fndecl: current_function_decl))
3299	continue;
3300
3301	if (cfun->gimple_df->tm_restart == NULL)
3302	cfun->gimple_df->tm_restart
3303	= hash_table<tm_restart_hasher>::create_ggc (n: 31);
3304
3305	// All TM builtins have an abnormal edge to the outer-most transaction.
3306	// We never restart inner transactions.
3307	for (struct tm_region *o = region; o; o = o->outer)
3308	if (!o->outer)
3309	{
3310	split_bb_make_tm_edge (stmt: call_stmt, dest_bb: o->restart_block, iter: gsi, pnext: &next_gsi);
3311	break;
3312	}
3313
3314	// Delete any tail-call annotation that may have been added.
3315	// The tail-call pass may have mis-identified the commit as being
3316	// a candidate because we had not yet added this restart edge.
3317	gimple_call_set_tail (s: call_stmt, tail_p: false);
3318	}
3319	}
3320
3321	/* Entry point to the final expansion of transactional nodes. */
3322
3323	namespace {
3324
3325	const pass_data pass_data_tm_edges =
3326	{
3327	.type: GIMPLE_PASS, /* type */
3328	.name: "tmedge", /* name */
3329	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
3330	.tv_id: TV_TRANS_MEM, /* tv_id */
3331	.properties_required: ( PROP_ssa | PROP_cfg ), /* properties_required */
3332	.properties_provided: 0, /* properties_provided */
3333	.properties_destroyed: 0, /* properties_destroyed */
3334	.todo_flags_start: 0, /* todo_flags_start */
3335	TODO_update_ssa, /* todo_flags_finish */
3336	};
3337
3338	class pass_tm_edges : public gimple_opt_pass
3339	{
3340	public:
3341	pass_tm_edges (gcc::context *ctxt)
3342	: gimple_opt_pass (pass_data_tm_edges, ctxt)
3343	{}
3344
3345	/* opt_pass methods: */
3346	unsigned int execute (function *) final override;
3347
3348	}; // class pass_tm_edges
3349
3350	unsigned int
3351	pass_tm_edges::execute (function *fun)
3352	{
3353	vec<tm_region *> bb_regions
3354	= get_bb_regions_instrumented (/*traverse_clones=*/false,
3355	/*include_uninstrumented_p=*/true);
3356	struct tm_region *r;
3357	unsigned i;
3358
3359	FOR_EACH_VEC_ELT (bb_regions, i, r)
3360	if (r != NULL)
3361	expand_block_edges (region: r, BASIC_BLOCK_FOR_FN (fun, i));
3362
3363	bb_regions.release ();
3364
3365	/* We've got to release the dominance info now, to indicate that it
3366	must be rebuilt completely. Otherwise we'll crash trying to update
3367	the SSA web in the TODO section following this pass. */
3368	free_dominance_info (CDI_DOMINATORS);
3369	/* We'ge also wrecked loops badly with inserting of abnormal edges. */
3370	loops_state_set (flags: LOOPS_NEED_FIXUP);
3371	bitmap_obstack_release (&tm_obstack);
3372	all_tm_regions = NULL;
3373
3374	return 0;
3375	}
3376
3377	} // anon namespace
3378
3379	gimple_opt_pass *
3380	make_pass_tm_edges (gcc::context *ctxt)
3381	{
3382	return new pass_tm_edges (ctxt);
3383	}
3384
3385	/* Helper function for expand_regions. Expand REGION and recurse to
3386	the inner region. Call CALLBACK on each region. CALLBACK returns
3387	NULL to continue the traversal, otherwise a non-null value which
3388	this function will return as well. TRAVERSE_CLONES is true if we
3389	should traverse transactional clones. */
3390
3391	static void *
3392	expand_regions_1 (struct tm_region *region,
3393	void *(*callback)(struct tm_region *, void *),
3394	void *data,
3395	bool traverse_clones)
3396	{
3397	void *retval = NULL;
3398	if (region->exit_blocks
3399	|| (traverse_clones && decl_is_tm_clone (fndecl: current_function_decl)))
3400	{
3401	retval = callback (region, data);
3402	if (retval)
3403	return retval;
3404	}
3405	if (region->inner)
3406	{
3407	retval = expand_regions (region->inner, callback, data, traverse_clones);
3408	if (retval)
3409	return retval;
3410	}
3411	return retval;
3412	}
3413
3414	/* Traverse the regions enclosed and including REGION. Execute
3415	CALLBACK for each region, passing DATA. CALLBACK returns NULL to
3416	continue the traversal, otherwise a non-null value which this
3417	function will return as well. TRAVERSE_CLONES is true if we should
3418	traverse transactional clones. */
3419
3420	static void *
3421	expand_regions (struct tm_region *region,
3422	void *(*callback)(struct tm_region *, void *),
3423	void *data,
3424	bool traverse_clones)
3425	{
3426	void *retval = NULL;
3427	while (region)
3428	{
3429	retval = expand_regions_1 (region, callback, data, traverse_clones);
3430	if (retval)
3431	return retval;
3432	region = region->next;
3433	}
3434	return retval;
3435	}
3436
3437
3438	/* A unique TM memory operation. */
3439	struct tm_memop
3440	{
3441	/* Unique ID that all memory operations to the same location have. */
3442	unsigned int value_id;
3443	/* Address of load/store. */
3444	tree addr;
3445	};
3446
3447	/* TM memory operation hashtable helpers. */
3448
3449	struct tm_memop_hasher : free_ptr_hash <tm_memop>
3450	{
3451	static inline hashval_t hash (const tm_memop *);
3452	static inline bool equal (const tm_memop *, const tm_memop *);
3453	};
3454
3455	/* Htab support. Return a hash value for a `tm_memop'. */
3456	inline hashval_t
3457	tm_memop_hasher::hash (const tm_memop *mem)
3458	{
3459	tree addr = mem->addr;
3460	/* We drill down to the SSA_NAME/DECL for the hash, but equality is
3461	actually done with operand_equal_p (see tm_memop_eq). */
3462	if (TREE_CODE (addr) == ADDR_EXPR)
3463	addr = TREE_OPERAND (addr, 0);
3464	return iterative_hash_expr (tree: addr, seed: 0);
3465	}
3466
3467	/* Htab support. Return true if two tm_memop's are the same. */
3468	inline bool
3469	tm_memop_hasher::equal (const tm_memop *mem1, const tm_memop *mem2)
3470	{
3471	return operand_equal_p (mem1->addr, mem2->addr, flags: 0);
3472	}
3473
3474	/* Sets for solving data flow equations in the memory optimization pass. */
3475	struct tm_memopt_bitmaps
3476	{
3477	/* Stores available to this BB upon entry. Basically, stores that
3478	dominate this BB. */
3479	bitmap store_avail_in;
3480	/* Stores available at the end of this BB. */
3481	bitmap store_avail_out;
3482	bitmap store_antic_in;
3483	bitmap store_antic_out;
3484	/* Reads available to this BB upon entry. Basically, reads that
3485	dominate this BB. */
3486	bitmap read_avail_in;
3487	/* Reads available at the end of this BB. */
3488	bitmap read_avail_out;
3489	/* Reads performed in this BB. */
3490	bitmap read_local;
3491	/* Writes performed in this BB. */
3492	bitmap store_local;
3493
3494	/* Temporary storage for pass. */
3495	/* Is the current BB in the worklist? */
3496	bool avail_in_worklist_p;
3497	/* Have we visited this BB? */
3498	bool visited_p;
3499	};
3500
3501	static bitmap_obstack tm_memopt_obstack;
3502
3503	/* Unique counter for TM loads and stores. Loads and stores of the
3504	same address get the same ID. */
3505	static unsigned int tm_memopt_value_id;
3506	static hash_table<tm_memop_hasher> *tm_memopt_value_numbers;
3507
3508	#define STORE_AVAIL_IN(BB) \
3509	((struct tm_memopt_bitmaps *) ((BB)->aux))->store_avail_in
3510	#define STORE_AVAIL_OUT(BB) \
3511	((struct tm_memopt_bitmaps *) ((BB)->aux))->store_avail_out
3512	#define STORE_ANTIC_IN(BB) \
3513	((struct tm_memopt_bitmaps *) ((BB)->aux))->store_antic_in
3514	#define STORE_ANTIC_OUT(BB) \
3515	((struct tm_memopt_bitmaps *) ((BB)->aux))->store_antic_out
3516	#define READ_AVAIL_IN(BB) \
3517	((struct tm_memopt_bitmaps *) ((BB)->aux))->read_avail_in
3518	#define READ_AVAIL_OUT(BB) \
3519	((struct tm_memopt_bitmaps *) ((BB)->aux))->read_avail_out
3520	#define READ_LOCAL(BB) \
3521	((struct tm_memopt_bitmaps *) ((BB)->aux))->read_local
3522	#define STORE_LOCAL(BB) \
3523	((struct tm_memopt_bitmaps *) ((BB)->aux))->store_local
3524	#define AVAIL_IN_WORKLIST_P(BB) \
3525	((struct tm_memopt_bitmaps *) ((BB)->aux))->avail_in_worklist_p
3526	#define BB_VISITED_P(BB) \
3527	((struct tm_memopt_bitmaps *) ((BB)->aux))->visited_p
3528
3529	/* Given a TM load/store in STMT, return the value number for the address
3530	it accesses. */
3531
3532	static unsigned int
3533	tm_memopt_value_number (gimple *stmt, enum insert_option op)
3534	{
3535	struct tm_memop tmpmem, *mem;
3536	tm_memop **slot;
3537
3538	gcc_assert (is_tm_load (stmt) || is_tm_store (stmt));
3539	tmpmem.addr = gimple_call_arg (gs: stmt, index: 0);
3540	slot = tm_memopt_value_numbers->find_slot (value: &tmpmem, insert: op);
3541	if (*slot)
3542	mem = *slot;
3543	else if (op == INSERT)
3544	{
3545	mem = XNEW (struct tm_memop);
3546	*slot = mem;
3547	mem->value_id = tm_memopt_value_id++;
3548	mem->addr = tmpmem.addr;
3549	}
3550	else
3551	gcc_unreachable ();
3552	return mem->value_id;
3553	}
3554
3555	/* Accumulate TM memory operations in BB into STORE_LOCAL and READ_LOCAL. */
3556
3557	static void
3558	tm_memopt_accumulate_memops (basic_block bb)
3559	{
3560	gimple_stmt_iterator gsi;
3561
3562	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
3563	{
3564	gimple *stmt = gsi_stmt (i: gsi);
3565	bitmap bits;
3566	unsigned int loc;
3567
3568	if (is_tm_store (stmt))
3569	bits = STORE_LOCAL (bb);
3570	else if (is_tm_load (stmt))
3571	bits = READ_LOCAL (bb);
3572	else
3573	continue;
3574
3575	loc = tm_memopt_value_number (stmt, op: INSERT);
3576	bitmap_set_bit (bits, loc);
3577	if (dump_file)
3578	{
3579	fprintf (stream: dump_file, format: "TM memopt (%s): value num=%d, BB=%d, addr=",
3580	is_tm_load (stmt) ? "LOAD" : "STORE", loc,
3581	gimple_bb (g: stmt)->index);
3582	print_generic_expr (dump_file, gimple_call_arg (gs: stmt, index: 0));
3583	fprintf (stream: dump_file, format: "\n");
3584	}
3585	}
3586	}
3587
3588	/* Prettily dump one of the memopt sets. BITS is the bitmap to dump. */
3589
3590	static void
3591	dump_tm_memopt_set (const char *set_name, bitmap bits)
3592	{
3593	unsigned i;
3594	bitmap_iterator bi;
3595	const char *comma = "";
3596
3597	fprintf (stream: dump_file, format: "TM memopt: %s: [", set_name);
3598	EXECUTE_IF_SET_IN_BITMAP (bits, 0, i, bi)
3599	{
3600	hash_table<tm_memop_hasher>::iterator hi;
3601	struct tm_memop *mem = NULL;
3602
3603	/* Yeah, yeah, yeah. Whatever. This is just for debugging. */
3604	FOR_EACH_HASH_TABLE_ELEMENT (*tm_memopt_value_numbers, mem, tm_memop_t, hi)
3605	if (mem->value_id == i)
3606	break;
3607	gcc_assert (mem->value_id == i);
3608	fprintf (stream: dump_file, format: "%s", comma);
3609	comma = ", ";
3610	print_generic_expr (dump_file, mem->addr);
3611	}
3612	fprintf (stream: dump_file, format: "]\n");
3613	}
3614
3615	/* Prettily dump all of the memopt sets in BLOCKS. */
3616
3617	static void
3618	dump_tm_memopt_sets (vec<basic_block> blocks)
3619	{
3620	size_t i;
3621	basic_block bb;
3622
3623	for (i = 0; blocks.iterate (ix: i, ptr: &bb); ++i)
3624	{
3625	fprintf (stream: dump_file, format: "------------BB %d---------\n", bb->index);
3626	dump_tm_memopt_set (set_name: "STORE_LOCAL", STORE_LOCAL (bb));
3627	dump_tm_memopt_set (set_name: "READ_LOCAL", READ_LOCAL (bb));
3628	dump_tm_memopt_set (set_name: "STORE_AVAIL_IN", STORE_AVAIL_IN (bb));
3629	dump_tm_memopt_set (set_name: "STORE_AVAIL_OUT", STORE_AVAIL_OUT (bb));
3630	dump_tm_memopt_set (set_name: "READ_AVAIL_IN", READ_AVAIL_IN (bb));
3631	dump_tm_memopt_set (set_name: "READ_AVAIL_OUT", READ_AVAIL_OUT (bb));
3632	}
3633	}
3634
3635	/* Compute {STORE,READ}_AVAIL_IN for the basic block BB. */
3636
3637	static void
3638	tm_memopt_compute_avin (basic_block bb)
3639	{
3640	edge e;
3641	unsigned ix;
3642
3643	/* Seed with the AVOUT of any predecessor. */
3644	for (ix = 0; ix < EDGE_COUNT (bb->preds); ix++)
3645	{
3646	e = EDGE_PRED (bb, ix);
3647	/* Make sure we have already visited this BB, and is thus
3648	initialized.
3649
3650	If e->src->aux is NULL, this predecessor is actually on an
3651	enclosing transaction. We only care about the current
3652	transaction, so ignore it. */
3653	if (e->src->aux && BB_VISITED_P (e->src))
3654	{
3655	bitmap_copy (STORE_AVAIL_IN (bb), STORE_AVAIL_OUT (e->src));
3656	bitmap_copy (READ_AVAIL_IN (bb), READ_AVAIL_OUT (e->src));
3657	break;
3658	}
3659	}
3660
3661	for (; ix < EDGE_COUNT (bb->preds); ix++)
3662	{
3663	e = EDGE_PRED (bb, ix);
3664	if (e->src->aux && BB_VISITED_P (e->src))
3665	{
3666	bitmap_and_into (STORE_AVAIL_IN (bb), STORE_AVAIL_OUT (e->src));
3667	bitmap_and_into (READ_AVAIL_IN (bb), READ_AVAIL_OUT (e->src));
3668	}
3669	}
3670
3671	BB_VISITED_P (bb) = true;
3672	}
3673
3674	/* Compute the STORE_ANTIC_IN for the basic block BB. */
3675
3676	static void
3677	tm_memopt_compute_antin (basic_block bb)
3678	{
3679	edge e;
3680	unsigned ix;
3681
3682	/* Seed with the ANTIC_OUT of any successor. */
3683	for (ix = 0; ix < EDGE_COUNT (bb->succs); ix++)
3684	{
3685	e = EDGE_SUCC (bb, ix);
3686	/* Make sure we have already visited this BB, and is thus
3687	initialized. */
3688	if (BB_VISITED_P (e->dest))
3689	{
3690	bitmap_copy (STORE_ANTIC_IN (bb), STORE_ANTIC_OUT (e->dest));
3691	break;
3692	}
3693	}
3694
3695	for (; ix < EDGE_COUNT (bb->succs); ix++)
3696	{
3697	e = EDGE_SUCC (bb, ix);
3698	if (BB_VISITED_P (e->dest))
3699	bitmap_and_into (STORE_ANTIC_IN (bb), STORE_ANTIC_OUT (e->dest));
3700	}
3701
3702	BB_VISITED_P (bb) = true;
3703	}
3704
3705	/* Compute the AVAIL sets for every basic block in BLOCKS.
3706
3707	We compute {STORE,READ}_AVAIL_{OUT,IN} as follows:
3708
3709	AVAIL_OUT[bb] = union (AVAIL_IN[bb], LOCAL[bb])
3710	AVAIL_IN[bb] = intersect (AVAIL_OUT[predecessors])
3711
3712	This is basically what we do in lcm's compute_available(), but here
3713	we calculate two sets of sets (one for STOREs and one for READs),
3714	and we work on a region instead of the entire CFG.
3715
3716	REGION is the TM region.
3717	BLOCKS are the basic blocks in the region. */
3718
3719	static void
3720	tm_memopt_compute_available (struct tm_region *region,
3721	vec<basic_block> blocks)
3722	{
3723	edge e;
3724	basic_block *worklist, *qin, *qout, *qend, bb;
3725	unsigned int qlen, i;
3726	edge_iterator ei;
3727	bool changed;
3728
3729	/* Allocate a worklist array/queue. Entries are only added to the
3730	list if they were not already on the list. So the size is
3731	bounded by the number of basic blocks in the region. */
3732	gcc_assert (!blocks.is_empty ());
3733	qlen = blocks.length () - 1;
3734	qin = qout = worklist = XNEWVEC (basic_block, qlen);
3735
3736	/* Put every block in the region on the worklist. */
3737	for (i = 0; blocks.iterate (ix: i, ptr: &bb); ++i)
3738	{
3739	/* Seed AVAIL_OUT with the LOCAL set. */
3740	bitmap_ior_into (STORE_AVAIL_OUT (bb), STORE_LOCAL (bb));
3741	bitmap_ior_into (READ_AVAIL_OUT (bb), READ_LOCAL (bb));
3742
3743	AVAIL_IN_WORKLIST_P (bb) = true;
3744	/* No need to insert the entry block, since it has an AVIN of
3745	null, and an AVOUT that has already been seeded in. */
3746	if (bb != region->entry_block)
3747	*qin++ = bb;
3748	}
3749
3750	/* The entry block has been initialized with the local sets. */
3751	BB_VISITED_P (region->entry_block) = true;
3752
3753	qin = worklist;
3754	qend = &worklist[qlen];
3755
3756	/* Iterate until the worklist is empty. */
3757	while (qlen)
3758	{
3759	/* Take the first entry off the worklist. */
3760	bb = *qout++;
3761	qlen--;
3762
3763	if (qout >= qend)
3764	qout = worklist;
3765
3766	/* This block can be added to the worklist again if necessary. */
3767	AVAIL_IN_WORKLIST_P (bb) = false;
3768	tm_memopt_compute_avin (bb);
3769
3770	/* Note: We do not add the LOCAL sets here because we already
3771	seeded the AVAIL_OUT sets with them. */
3772	changed = bitmap_ior_into (STORE_AVAIL_OUT (bb), STORE_AVAIL_IN (bb));
3773	changed |= bitmap_ior_into (READ_AVAIL_OUT (bb), READ_AVAIL_IN (bb));
3774	if (changed
3775	&& (region->exit_blocks == NULL
3776	|| !bitmap_bit_p (region->exit_blocks, bb->index)))
3777	/* If the out state of this block changed, then we need to add
3778	its successors to the worklist if they are not already in. */
3779	FOR_EACH_EDGE (e, ei, bb->succs)
3780	if (!AVAIL_IN_WORKLIST_P (e->dest)
3781	&& e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
3782	{
3783	*qin++ = e->dest;
3784	AVAIL_IN_WORKLIST_P (e->dest) = true;
3785	qlen++;
3786
3787	if (qin >= qend)
3788	qin = worklist;
3789	}
3790	}
3791
3792	free (ptr: worklist);
3793
3794	if (dump_file)
3795	dump_tm_memopt_sets (blocks);
3796	}
3797
3798	/* Compute ANTIC sets for every basic block in BLOCKS.
3799
3800	We compute STORE_ANTIC_OUT as follows:
3801
3802	STORE_ANTIC_OUT[bb] = union(STORE_ANTIC_IN[bb], STORE_LOCAL[bb])
3803	STORE_ANTIC_IN[bb] = intersect(STORE_ANTIC_OUT[successors])
3804
3805	REGION is the TM region.
3806	BLOCKS are the basic blocks in the region. */
3807
3808	static void
3809	tm_memopt_compute_antic (struct tm_region *region,
3810	vec<basic_block> blocks)
3811	{
3812	edge e;
3813	basic_block *worklist, *qin, *qout, *qend, bb;
3814	unsigned int qlen;
3815	int i;
3816	edge_iterator ei;
3817
3818	/* Allocate a worklist array/queue. Entries are only added to the
3819	list if they were not already on the list. So the size is
3820	bounded by the number of basic blocks in the region. */
3821	qin = qout = worklist = XNEWVEC (basic_block, blocks.length ());
3822
3823	for (qlen = 0, i = blocks.length () - 1; i >= 0; --i)
3824	{
3825	bb = blocks[i];
3826
3827	/* Seed ANTIC_OUT with the LOCAL set. */
3828	bitmap_ior_into (STORE_ANTIC_OUT (bb), STORE_LOCAL (bb));
3829
3830	/* Put every block in the region on the worklist. */
3831	AVAIL_IN_WORKLIST_P (bb) = true;
3832	/* No need to insert exit blocks, since their ANTIC_IN is NULL,
3833	and their ANTIC_OUT has already been seeded in. */
3834	if (region->exit_blocks
3835	&& !bitmap_bit_p (region->exit_blocks, bb->index))
3836	{
3837	qlen++;
3838	*qin++ = bb;
3839	}
3840	}
3841
3842	/* The exit blocks have been initialized with the local sets. */
3843	if (region->exit_blocks)
3844	{
3845	unsigned int i;
3846	bitmap_iterator bi;
3847	EXECUTE_IF_SET_IN_BITMAP (region->exit_blocks, 0, i, bi)
3848	BB_VISITED_P (BASIC_BLOCK_FOR_FN (cfun, i)) = true;
3849	}
3850
3851	qin = worklist;
3852	qend = &worklist[qlen];
3853
3854	/* Iterate until the worklist is empty. */
3855	while (qlen)
3856	{
3857	/* Take the first entry off the worklist. */
3858	bb = *qout++;
3859	qlen--;
3860
3861	if (qout >= qend)
3862	qout = worklist;
3863
3864	/* This block can be added to the worklist again if necessary. */
3865	AVAIL_IN_WORKLIST_P (bb) = false;
3866	tm_memopt_compute_antin (bb);
3867
3868	/* Note: We do not add the LOCAL sets here because we already
3869	seeded the ANTIC_OUT sets with them. */
3870	if (bitmap_ior_into (STORE_ANTIC_OUT (bb), STORE_ANTIC_IN (bb))
3871	&& bb != region->entry_block)
3872	/* If the out state of this block changed, then we need to add
3873	its predecessors to the worklist if they are not already in. */
3874	FOR_EACH_EDGE (e, ei, bb->preds)
3875	if (!AVAIL_IN_WORKLIST_P (e->src))
3876	{
3877	*qin++ = e->src;
3878	AVAIL_IN_WORKLIST_P (e->src) = true;
3879	qlen++;
3880
3881	if (qin >= qend)
3882	qin = worklist;
3883	}
3884	}
3885
3886	free (ptr: worklist);
3887
3888	if (dump_file)
3889	dump_tm_memopt_sets (blocks);
3890	}
3891
3892	/* Offsets of load variants from TM_LOAD. For example,
3893	BUILT_IN_TM_LOAD_RAR* is an offset of 1 from BUILT_IN_TM_LOAD*.
3894	See gtm-builtins.def. */
3895	#define TRANSFORM_RAR 1
3896	#define TRANSFORM_RAW 2
3897	#define TRANSFORM_RFW 3
3898	/* Offsets of store variants from TM_STORE. */
3899	#define TRANSFORM_WAR 1
3900	#define TRANSFORM_WAW 2
3901
3902	/* Inform about a load/store optimization. */
3903
3904	static void
3905	dump_tm_memopt_transform (gimple *stmt)
3906	{
3907	if (dump_file)
3908	{
3909	fprintf (stream: dump_file, format: "TM memopt: transforming: ");
3910	print_gimple_stmt (dump_file, stmt, 0);
3911	fprintf (stream: dump_file, format: "\n");
3912	}
3913	}
3914
3915	/* Perform a read/write optimization. Replaces the TM builtin in STMT
3916	by a builtin that is OFFSET entries down in the builtins table in
3917	gtm-builtins.def. */
3918
3919	static void
3920	tm_memopt_transform_stmt (unsigned int offset,
3921	gcall *stmt,
3922	gimple_stmt_iterator *gsi)
3923	{
3924	tree fn = gimple_call_fn (gs: stmt);
3925	gcc_assert (TREE_CODE (fn) == ADDR_EXPR);
3926	TREE_OPERAND (fn, 0)
3927	= builtin_decl_explicit (fncode: (enum built_in_function)
3928	(DECL_FUNCTION_CODE (TREE_OPERAND (fn, 0))
3929	+ offset));
3930	gimple_call_set_fn (gs: stmt, fn);
3931	gsi_replace (gsi, stmt, true);
3932	dump_tm_memopt_transform (stmt);
3933	}
3934
3935	/* Perform the actual TM memory optimization transformations in the
3936	basic blocks in BLOCKS. */
3937
3938	static void
3939	tm_memopt_transform_blocks (vec<basic_block> blocks)
3940	{
3941	size_t i;
3942	basic_block bb;
3943	gimple_stmt_iterator gsi;
3944
3945	for (i = 0; blocks.iterate (ix: i, ptr: &bb); ++i)
3946	{
3947	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
3948	{
3949	gimple *stmt = gsi_stmt (i: gsi);
3950	bitmap read_avail = READ_AVAIL_IN (bb);
3951	bitmap store_avail = STORE_AVAIL_IN (bb);
3952	bitmap store_antic = STORE_ANTIC_OUT (bb);
3953	unsigned int loc;
3954
3955	if (is_tm_simple_load (stmt))
3956	{
3957	gcall *call_stmt = as_a <gcall *> (p: stmt);
3958	loc = tm_memopt_value_number (stmt, op: NO_INSERT);
3959	if (store_avail && bitmap_bit_p (store_avail, loc))
3960	tm_memopt_transform_stmt (TRANSFORM_RAW, stmt: call_stmt, gsi: &gsi);
3961	else if (store_antic && bitmap_bit_p (store_antic, loc))
3962	{
3963	tm_memopt_transform_stmt (TRANSFORM_RFW, stmt: call_stmt, gsi: &gsi);
3964	bitmap_set_bit (store_avail, loc);
3965	}
3966	else if (read_avail && bitmap_bit_p (read_avail, loc))
3967	tm_memopt_transform_stmt (TRANSFORM_RAR, stmt: call_stmt, gsi: &gsi);
3968	else
3969	bitmap_set_bit (read_avail, loc);
3970	}
3971	else if (is_tm_simple_store (stmt))
3972	{
3973	gcall *call_stmt = as_a <gcall *> (p: stmt);
3974	loc = tm_memopt_value_number (stmt, op: NO_INSERT);
3975	if (store_avail && bitmap_bit_p (store_avail, loc))
3976	tm_memopt_transform_stmt (TRANSFORM_WAW, stmt: call_stmt, gsi: &gsi);
3977	else
3978	{
3979	if (read_avail && bitmap_bit_p (read_avail, loc))
3980	tm_memopt_transform_stmt (TRANSFORM_WAR, stmt: call_stmt, gsi: &gsi);
3981	bitmap_set_bit (store_avail, loc);
3982	}
3983	}
3984	}
3985	}
3986	}
3987
3988	/* Return a new set of bitmaps for a BB. */
3989
3990	static struct tm_memopt_bitmaps *
3991	tm_memopt_init_sets (void)
3992	{
3993	struct tm_memopt_bitmaps *b
3994	= XOBNEW (&tm_memopt_obstack.obstack, struct tm_memopt_bitmaps);
3995	b->store_avail_in = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
3996	b->store_avail_out = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
3997	b->store_antic_in = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
3998	b->store_antic_out = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
3999	b->store_avail_out = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
4000	b->read_avail_in = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
4001	b->read_avail_out = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
4002	b->read_local = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
4003	b->store_local = BITMAP_ALLOC (obstack: &tm_memopt_obstack);
4004	return b;
4005	}
4006
4007	/* Free sets computed for each BB. */
4008
4009	static void
4010	tm_memopt_free_sets (vec<basic_block> blocks)
4011	{
4012	size_t i;
4013	basic_block bb;
4014
4015	for (i = 0; blocks.iterate (ix: i, ptr: &bb); ++i)
4016	bb->aux = NULL;
4017	}
4018
4019	/* Clear the visited bit for every basic block in BLOCKS. */
4020
4021	static void
4022	tm_memopt_clear_visited (vec<basic_block> blocks)
4023	{
4024	size_t i;
4025	basic_block bb;
4026
4027	for (i = 0; blocks.iterate (ix: i, ptr: &bb); ++i)
4028	BB_VISITED_P (bb) = false;
4029	}
4030
4031	/* Replace TM load/stores with hints for the runtime. We handle
4032	things like read-after-write, write-after-read, read-after-read,
4033	read-for-write, etc. */
4034
4035	static unsigned int
4036	execute_tm_memopt (void)
4037	{
4038	struct tm_region *region;
4039	vec<basic_block> bbs;
4040
4041	tm_memopt_value_id = 0;
4042	tm_memopt_value_numbers = new hash_table<tm_memop_hasher> (10);
4043
4044	for (region = all_tm_regions; region; region = region->next)
4045	{
4046	/* All the TM stores/loads in the current region. */
4047	size_t i;
4048	basic_block bb;
4049
4050	bitmap_obstack_initialize (&tm_memopt_obstack);
4051
4052	/* Save all BBs for the current region. */
4053	bbs = get_tm_region_blocks (entry_block: region->entry_block,
4054	exit_blocks: region->exit_blocks,
4055	irr_blocks: region->irr_blocks,
4056	NULL,
4057	stop_at_irrevocable_p: false);
4058
4059	/* Collect all the memory operations. */
4060	for (i = 0; bbs.iterate (ix: i, ptr: &bb); ++i)
4061	{
4062	bb->aux = tm_memopt_init_sets ();
4063	tm_memopt_accumulate_memops (bb);
4064	}
4065
4066	/* Solve data flow equations and transform each block accordingly. */
4067	tm_memopt_clear_visited (blocks: bbs);
4068	tm_memopt_compute_available (region, blocks: bbs);
4069	tm_memopt_clear_visited (blocks: bbs);
4070	tm_memopt_compute_antic (region, blocks: bbs);
4071	tm_memopt_transform_blocks (blocks: bbs);
4072
4073	tm_memopt_free_sets (blocks: bbs);
4074	bbs.release ();
4075	bitmap_obstack_release (&tm_memopt_obstack);
4076	tm_memopt_value_numbers->empty ();
4077	}
4078
4079	delete tm_memopt_value_numbers;
4080	tm_memopt_value_numbers = NULL;
4081	return 0;
4082	}
4083
4084	namespace {
4085
4086	const pass_data pass_data_tm_memopt =
4087	{
4088	.type: GIMPLE_PASS, /* type */
4089	.name: "tmmemopt", /* name */
4090	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
4091	.tv_id: TV_TRANS_MEM, /* tv_id */
4092	.properties_required: ( PROP_ssa | PROP_cfg ), /* properties_required */
4093	.properties_provided: 0, /* properties_provided */
4094	.properties_destroyed: 0, /* properties_destroyed */
4095	.todo_flags_start: 0, /* todo_flags_start */
4096	.todo_flags_finish: 0, /* todo_flags_finish */
4097	};
4098
4099	class pass_tm_memopt : public gimple_opt_pass
4100	{
4101	public:
4102	pass_tm_memopt (gcc::context *ctxt)
4103	: gimple_opt_pass (pass_data_tm_memopt, ctxt)
4104	{}
4105
4106	/* opt_pass methods: */
4107	bool gate (function *) final override { return flag_tm && optimize > 0; }
4108	unsigned int execute (function *) final override
4109	{
4110	return execute_tm_memopt ();
4111	}
4112
4113	}; // class pass_tm_memopt
4114
4115	} // anon namespace
4116
4117	gimple_opt_pass *
4118	make_pass_tm_memopt (gcc::context *ctxt)
4119	{
4120	return new pass_tm_memopt (ctxt);
4121	}
4122
4123
4124	/* Interprocedual analysis for the creation of transactional clones.
4125	The aim of this pass is to find which functions are referenced in
4126	a non-irrevocable transaction context, and for those over which
4127	we have control (or user directive), create a version of the
4128	function which uses only the transactional interface to reference
4129	protected memories. This analysis proceeds in several steps:
4130
4131	(1) Collect the set of all possible transactional clones:
4132
4133	(a) For all local public functions marked tm_callable, push
4134	it onto the tm_callee queue.
4135
4136	(b) For all local functions, scan for calls in transaction blocks.
4137	Push the caller and callee onto the tm_caller and tm_callee
4138	queues. Count the number of callers for each callee.
4139
4140	(c) For each local function on the callee list, assume we will
4141	create a transactional clone. Push *all* calls onto the
4142	callee queues; count the number of clone callers separately
4143	to the number of original callers.
4144
4145	(2) Propagate irrevocable status up the dominator tree:
4146
4147	(a) Any external function on the callee list that is not marked
4148	tm_callable is irrevocable. Push all callers of such onto
4149	a worklist.
4150
4151	(b) For each function on the worklist, mark each block that
4152	contains an irrevocable call. Use the AND operator to
4153	propagate that mark up the dominator tree.
4154
4155	(c) If we reach the entry block for a possible transactional
4156	clone, then the transactional clone is irrevocable, and
4157	we should not create the clone after all. Push all
4158	callers onto the worklist.
4159
4160	(d) Place tm_irrevocable calls at the beginning of the relevant
4161	blocks. Special case here is the entry block for the entire
4162	transaction region; there we mark it GTMA_DOES_GO_IRREVOCABLE for
4163	the library to begin the region in serial mode. Decrement
4164	the call count for all callees in the irrevocable region.
4165
4166	(3) Create the transactional clones:
4167
4168	Any tm_callee that still has a non-zero call count is cloned.
4169	*/
4170
4171	/* This structure is stored in the AUX field of each cgraph_node. */
4172	struct tm_ipa_cg_data
4173	{
4174	/* The clone of the function that got created. */
4175	struct cgraph_node *clone;
4176
4177	/* The tm regions in the normal function. */
4178	struct tm_region *all_tm_regions;
4179
4180	/* The blocks of the normal/clone functions that contain irrevocable
4181	calls, or blocks that are post-dominated by irrevocable calls. */
4182	bitmap irrevocable_blocks_normal;
4183	bitmap irrevocable_blocks_clone;
4184
4185	/* The blocks of the normal function that are involved in transactions. */
4186	bitmap transaction_blocks_normal;
4187
4188	/* The number of callers to the transactional clone of this function
4189	from normal and transactional clones respectively. */
4190	unsigned tm_callers_normal;
4191	unsigned tm_callers_clone;
4192
4193	/* True if all calls to this function's transactional clone
4194	are irrevocable. Also automatically true if the function
4195	has no transactional clone. */
4196	bool is_irrevocable;
4197
4198	/* Flags indicating the presence of this function in various queues. */
4199	bool in_callee_queue;
4200	bool in_worklist;
4201
4202	/* Flags indicating the kind of scan desired while in the worklist. */
4203	bool want_irr_scan_normal;
4204	};
4205
4206	typedef vec<cgraph_node *> cgraph_node_queue;
4207
4208	/* Return the ipa data associated with NODE, allocating zeroed memory
4209	if necessary. TRAVERSE_ALIASES is true if we must traverse aliases
4210	and set *NODE accordingly. */
4211
4212	static struct tm_ipa_cg_data *
4213	get_cg_data (struct cgraph_node **node, bool traverse_aliases)
4214	{
4215	struct tm_ipa_cg_data *d;
4216
4217	if (traverse_aliases && (*node)->alias)
4218	*node = (*node)->get_alias_target ();
4219
4220	d = (struct tm_ipa_cg_data *) (*node)->aux;
4221
4222	if (d == NULL)
4223	{
4224	d = (struct tm_ipa_cg_data *)
4225	obstack_alloc (&tm_obstack.obstack, sizeof (*d));
4226	(*node)->aux = (void *) d;
4227	memset (s: d, c: 0, n: sizeof (*d));
4228	}
4229
4230	return d;
4231	}
4232
4233	/* Add NODE to the end of QUEUE, unless IN_QUEUE_P indicates that
4234	it is already present. */
4235
4236	static void
4237	maybe_push_queue (struct cgraph_node *node,
4238	cgraph_node_queue *queue_p, bool *in_queue_p)
4239	{
4240	if (!*in_queue_p)
4241	{
4242	*in_queue_p = true;
4243	queue_p->safe_push (obj: node);
4244	}
4245	}
4246
4247	/* A subroutine of ipa_tm_scan_calls_transaction and ipa_tm_scan_calls_clone.
4248	Queue all callees within block BB. */
4249
4250	static void
4251	ipa_tm_scan_calls_block (cgraph_node_queue *callees_p,
4252	basic_block bb, bool for_clone)
4253	{
4254	gimple_stmt_iterator gsi;
4255
4256	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
4257	{
4258	gimple *stmt = gsi_stmt (i: gsi);
4259	if (is_gimple_call (gs: stmt) && !is_tm_pure_call (call: stmt))
4260	{
4261	tree fndecl = gimple_call_fndecl (gs: stmt);
4262	if (fndecl)
4263	{
4264	struct tm_ipa_cg_data *d;
4265	unsigned *pcallers;
4266	struct cgraph_node *node;
4267
4268	if (is_tm_ending_fndecl (fndecl))
4269	continue;
4270	if (find_tm_replacement_function (fndecl))
4271	continue;
4272
4273	node = cgraph_node::get (decl: fndecl);
4274	gcc_assert (node != NULL);
4275	d = get_cg_data (node: &node, traverse_aliases: true);
4276
4277	pcallers = (for_clone ? &d->tm_callers_clone
4278	: &d->tm_callers_normal);
4279	*pcallers += 1;
4280
4281	maybe_push_queue (node, queue_p: callees_p, in_queue_p: &d->in_callee_queue);
4282	}
4283	}
4284	}
4285	}
4286
4287	/* Scan all calls in NODE that are within a transaction region,
4288	and push the resulting nodes into the callee queue. */
4289
4290	static void
4291	ipa_tm_scan_calls_transaction (struct tm_ipa_cg_data *d,
4292	cgraph_node_queue *callees_p)
4293	{
4294	d->transaction_blocks_normal = BITMAP_ALLOC (obstack: &tm_obstack);
4295	d->all_tm_regions = all_tm_regions;
4296
4297	for (tm_region *r = all_tm_regions; r; r = r->next)
4298	{
4299	vec<basic_block> bbs;
4300	basic_block bb;
4301	unsigned i;
4302
4303	bbs = get_tm_region_blocks (entry_block: r->entry_block, exit_blocks: r->exit_blocks, NULL,
4304	all_region_blocks: d->transaction_blocks_normal, stop_at_irrevocable_p: false, include_uninstrumented_p: false);
4305
4306	FOR_EACH_VEC_ELT (bbs, i, bb)
4307	ipa_tm_scan_calls_block (callees_p, bb, for_clone: false);
4308
4309	bbs.release ();
4310	}
4311	}
4312
4313	/* Scan all calls in NODE as if this is the transactional clone,
4314	and push the destinations into the callee queue. */
4315
4316	static void
4317	ipa_tm_scan_calls_clone (struct cgraph_node *node,
4318	cgraph_node_queue *callees_p)
4319	{
4320	struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
4321	basic_block bb;
4322
4323	FOR_EACH_BB_FN (bb, fn)
4324	ipa_tm_scan_calls_block (callees_p, bb, for_clone: true);
4325	}
4326
4327	/* The function NODE has been detected to be irrevocable. Push all
4328	of its callers onto WORKLIST for the purpose of re-scanning them. */
4329
4330	static void
4331	ipa_tm_note_irrevocable (struct cgraph_node *node,
4332	cgraph_node_queue *worklist_p)
4333	{
4334	struct tm_ipa_cg_data *d = get_cg_data (node: &node, traverse_aliases: true);
4335	struct cgraph_edge *e;
4336
4337	d->is_irrevocable = true;
4338
4339	for (e = node->callers; e ; e = e->next_caller)
4340	{
4341	basic_block bb;
4342	struct cgraph_node *caller;
4343
4344	/* Don't examine recursive calls. */
4345	if (e->caller == node)
4346	continue;
4347	/* Even if we think we can go irrevocable, believe the user
4348	above all. */
4349	if (is_tm_safe_or_pure (x: e->caller->decl))
4350	continue;
4351
4352	caller = e->caller;
4353	d = get_cg_data (node: &caller, traverse_aliases: true);
4354
4355	/* Check if the callee is in a transactional region. If so,
4356	schedule the function for normal re-scan as well. */
4357	bb = gimple_bb (g: e->call_stmt);
4358	gcc_assert (bb != NULL);
4359	if (d->transaction_blocks_normal
4360	&& bitmap_bit_p (d->transaction_blocks_normal, bb->index))
4361	d->want_irr_scan_normal = true;
4362
4363	maybe_push_queue (node: caller, queue_p: worklist_p, in_queue_p: &d->in_worklist);
4364	}
4365	}
4366
4367	/* A subroutine of ipa_tm_scan_irr_blocks; return true iff any statement
4368	within the block is irrevocable. */
4369
4370	static bool
4371	ipa_tm_scan_irr_block (basic_block bb)
4372	{
4373	gimple_stmt_iterator gsi;
4374	tree fn;
4375
4376	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
4377	{
4378	gimple *stmt = gsi_stmt (i: gsi);
4379	switch (gimple_code (g: stmt))
4380	{
4381	case GIMPLE_ASSIGN:
4382	if (gimple_assign_single_p (gs: stmt))
4383	{
4384	tree lhs = gimple_assign_lhs (gs: stmt);
4385	tree rhs = gimple_assign_rhs1 (gs: stmt);
4386	if (volatile_lvalue_p (t: lhs) || volatile_lvalue_p (t: rhs))
4387	return true;
4388	}
4389	break;
4390
4391	case GIMPLE_CALL:
4392	{
4393	tree lhs = gimple_call_lhs (gs: stmt);
4394	if (lhs && volatile_lvalue_p (t: lhs))
4395	return true;
4396
4397	if (is_tm_pure_call (call: stmt))
4398	break;
4399
4400	fn = gimple_call_fn (gs: stmt);
4401
4402	/* Functions with the attribute are by definition irrevocable. */
4403	if (is_tm_irrevocable (x: fn))
4404	return true;
4405
4406	/* For direct function calls, go ahead and check for replacement
4407	functions, or transitive irrevocable functions. For indirect
4408	functions, we'll ask the runtime. */
4409	if (TREE_CODE (fn) == ADDR_EXPR)
4410	{
4411	struct tm_ipa_cg_data *d;
4412	struct cgraph_node *node;
4413
4414	fn = TREE_OPERAND (fn, 0);
4415	if (is_tm_ending_fndecl (fndecl: fn))
4416	break;
4417	if (find_tm_replacement_function (fndecl: fn))
4418	break;
4419
4420	node = cgraph_node::get (decl: fn);
4421	d = get_cg_data (node: &node, traverse_aliases: true);
4422
4423	/* Return true if irrevocable, but above all, believe
4424	the user. */
4425	if (d->is_irrevocable
4426	&& !is_tm_safe_or_pure (x: fn))
4427	return true;
4428	}
4429	break;
4430	}
4431
4432	case GIMPLE_ASM:
4433	/* ??? The Approved Method of indicating that an inline
4434	assembly statement is not relevant to the transaction
4435	is to wrap it in a __tm_waiver block. This is not
4436	yet implemented, so we can't check for it. */
4437	if (is_tm_safe (x: current_function_decl))
4438	error_at (gimple_location (g: stmt),
4439	"%<asm%> not allowed in %<transaction_safe%> function");
4440	return true;
4441
4442	default:
4443	break;
4444	}
4445	}
4446
4447	return false;
4448	}
4449
4450	/* For each of the blocks seeded witin PQUEUE, walk the CFG looking
4451	for new irrevocable blocks, marking them in NEW_IRR. Don't bother
4452	scanning past OLD_IRR or EXIT_BLOCKS. */
4453
4454	static bool
4455	ipa_tm_scan_irr_blocks (vec<basic_block> *pqueue, bitmap new_irr,
4456	bitmap old_irr, bitmap exit_blocks)
4457	{
4458	bool any_new_irr = false;
4459	edge e;
4460	edge_iterator ei;
4461	bitmap visited_blocks = BITMAP_ALLOC (NULL);
4462
4463	do
4464	{
4465	basic_block bb = pqueue->pop ();
4466
4467	/* Don't re-scan blocks we know already are irrevocable. */
4468	if (old_irr && bitmap_bit_p (old_irr, bb->index))
4469	continue;
4470
4471	if (ipa_tm_scan_irr_block (bb))
4472	{
4473	bitmap_set_bit (new_irr, bb->index);
4474	any_new_irr = true;
4475	}
4476	else if (exit_blocks == NULL || !bitmap_bit_p (exit_blocks, bb->index))
4477	{
4478	FOR_EACH_EDGE (e, ei, bb->succs)
4479	if (!bitmap_bit_p (visited_blocks, e->dest->index))
4480	{
4481	bitmap_set_bit (visited_blocks, e->dest->index);
4482	pqueue->safe_push (obj: e->dest);
4483	}
4484	}
4485	}
4486	while (!pqueue->is_empty ());
4487
4488	BITMAP_FREE (visited_blocks);
4489
4490	return any_new_irr;
4491	}
4492
4493	/* Propagate the irrevocable property both up and down the dominator tree.
4494	BB is the current block being scanned; EXIT_BLOCKS are the edges of the
4495	TM regions; OLD_IRR are the results of a previous scan of the dominator
4496	tree which has been fully propagated; NEW_IRR is the set of new blocks
4497	which are gaining the irrevocable property during the current scan. */
4498
4499	static void
4500	ipa_tm_propagate_irr (basic_block entry_block, bitmap new_irr,
4501	bitmap old_irr, bitmap exit_blocks)
4502	{
4503	vec<basic_block> bbs;
4504	bitmap all_region_blocks;
4505
4506	/* If this block is in the old set, no need to rescan. */
4507	if (old_irr && bitmap_bit_p (old_irr, entry_block->index))
4508	return;
4509
4510	all_region_blocks = BITMAP_ALLOC (obstack: &tm_obstack);
4511	bbs = get_tm_region_blocks (entry_block, exit_blocks, NULL,
4512	all_region_blocks, stop_at_irrevocable_p: false);
4513	do
4514	{
4515	basic_block bb = bbs.pop ();
4516	bool this_irr = bitmap_bit_p (new_irr, bb->index);
4517	bool all_son_irr = false;
4518	edge_iterator ei;
4519	edge e;
4520
4521	/* Propagate up. If my children are, I am too, but we must have
4522	at least one child that is. */
4523	if (!this_irr)
4524	{
4525	FOR_EACH_EDGE (e, ei, bb->succs)
4526	{
4527	if (!bitmap_bit_p (new_irr, e->dest->index))
4528	{
4529	all_son_irr = false;
4530	break;
4531	}
4532	else
4533	all_son_irr = true;
4534	}
4535	if (all_son_irr)
4536	{
4537	/* Add block to new_irr if it hasn't already been processed. */
4538	if (!old_irr || !bitmap_bit_p (old_irr, bb->index))
4539	{
4540	bitmap_set_bit (new_irr, bb->index);
4541	this_irr = true;
4542	}
4543	}
4544	}
4545
4546	/* Propagate down to everyone we immediately dominate. */
4547	if (this_irr)
4548	{
4549	basic_block son;
4550	for (son = first_dom_son (CDI_DOMINATORS, bb);
4551	son;
4552	son = next_dom_son (CDI_DOMINATORS, son))
4553	{
4554	/* Make sure block is actually in a TM region, and it
4555	isn't already in old_irr. */
4556	if ((!old_irr || !bitmap_bit_p (old_irr, son->index))
4557	&& bitmap_bit_p (all_region_blocks, son->index))
4558	bitmap_set_bit (new_irr, son->index);
4559	}
4560	}
4561	}
4562	while (!bbs.is_empty ());
4563
4564	BITMAP_FREE (all_region_blocks);
4565	bbs.release ();
4566	}
4567
4568	static void
4569	ipa_tm_decrement_clone_counts (basic_block bb, bool for_clone)
4570	{
4571	gimple_stmt_iterator gsi;
4572
4573	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
4574	{
4575	gimple *stmt = gsi_stmt (i: gsi);
4576	if (is_gimple_call (gs: stmt) && !is_tm_pure_call (call: stmt))
4577	{
4578	tree fndecl = gimple_call_fndecl (gs: stmt);
4579	if (fndecl)
4580	{
4581	struct tm_ipa_cg_data *d;
4582	unsigned *pcallers;
4583	struct cgraph_node *tnode;
4584
4585	if (is_tm_ending_fndecl (fndecl))
4586	continue;
4587	if (find_tm_replacement_function (fndecl))
4588	continue;
4589
4590	tnode = cgraph_node::get (decl: fndecl);
4591	d = get_cg_data (node: &tnode, traverse_aliases: true);
4592
4593	pcallers = (for_clone ? &d->tm_callers_clone
4594	: &d->tm_callers_normal);
4595
4596	gcc_assert (*pcallers > 0);
4597	*pcallers -= 1;
4598	}
4599	}
4600	}
4601	}
4602
4603	/* (Re-)Scan the transaction blocks in NODE for calls to irrevocable functions,
4604	as well as other irrevocable actions such as inline assembly. Mark all
4605	such blocks as irrevocable and decrement the number of calls to
4606	transactional clones. Return true if, for the transactional clone, the
4607	entire function is irrevocable. */
4608
4609	static bool
4610	ipa_tm_scan_irr_function (struct cgraph_node *node, bool for_clone)
4611	{
4612	struct tm_ipa_cg_data *d;
4613	bitmap new_irr, old_irr;
4614	bool ret = false;
4615
4616	/* Builtin operators (operator new, and such). */
4617	if (DECL_STRUCT_FUNCTION (node->decl) == NULL
4618	|| DECL_STRUCT_FUNCTION (node->decl)->cfg == NULL)
4619	return false;
4620
4621	push_cfun (DECL_STRUCT_FUNCTION (node->decl));
4622	calculate_dominance_info (CDI_DOMINATORS);
4623
4624	d = get_cg_data (node: &node, traverse_aliases: true);
4625	auto_vec<basic_block, 10> queue;
4626	new_irr = BITMAP_ALLOC (obstack: &tm_obstack);
4627
4628	/* Scan each tm region, propagating irrevocable status through the tree. */
4629	if (for_clone)
4630	{
4631	old_irr = d->irrevocable_blocks_clone;
4632	queue.quick_push (obj: single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
4633	if (ipa_tm_scan_irr_blocks (pqueue: &queue, new_irr, old_irr, NULL))
4634	{
4635	ipa_tm_propagate_irr (entry_block: single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
4636	new_irr,
4637	old_irr, NULL);
4638	ret = bitmap_bit_p (new_irr,
4639	single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun))->index);
4640	}
4641	}
4642	else
4643	{
4644	struct tm_region *region;
4645
4646	old_irr = d->irrevocable_blocks_normal;
4647	for (region = d->all_tm_regions; region; region = region->next)
4648	{
4649	queue.quick_push (obj: region->entry_block);
4650	if (ipa_tm_scan_irr_blocks (pqueue: &queue, new_irr, old_irr,
4651	exit_blocks: region->exit_blocks))
4652	ipa_tm_propagate_irr (entry_block: region->entry_block, new_irr, old_irr,
4653	exit_blocks: region->exit_blocks);
4654	}
4655	}
4656
4657	/* If we found any new irrevocable blocks, reduce the call count for
4658	transactional clones within the irrevocable blocks. Save the new
4659	set of irrevocable blocks for next time. */
4660	if (!bitmap_empty_p (map: new_irr))
4661	{
4662	bitmap_iterator bmi;
4663	unsigned i;
4664
4665	EXECUTE_IF_SET_IN_BITMAP (new_irr, 0, i, bmi)
4666	ipa_tm_decrement_clone_counts (BASIC_BLOCK_FOR_FN (cfun, i),
4667	for_clone);
4668
4669	if (old_irr)
4670	{
4671	bitmap_ior_into (old_irr, new_irr);
4672	BITMAP_FREE (new_irr);
4673	}
4674	else if (for_clone)
4675	d->irrevocable_blocks_clone = new_irr;
4676	else
4677	d->irrevocable_blocks_normal = new_irr;
4678
4679	if (dump_file && new_irr)
4680	{
4681	const char *dname;
4682	bitmap_iterator bmi;
4683	unsigned i;
4684
4685	dname = lang_hooks.decl_printable_name (current_function_decl, 2);
4686	EXECUTE_IF_SET_IN_BITMAP (new_irr, 0, i, bmi)
4687	fprintf (stream: dump_file, format: "%s: bb %d goes irrevocable\n", dname, i);
4688	}
4689	}
4690	else
4691	BITMAP_FREE (new_irr);
4692
4693	pop_cfun ();
4694
4695	return ret;
4696	}
4697
4698	/* Return true if, for the transactional clone of NODE, any call
4699	may enter irrevocable mode. */
4700
4701	static bool
4702	ipa_tm_mayenterirr_function (struct cgraph_node *node)
4703	{
4704	struct tm_ipa_cg_data *d;
4705	tree decl;
4706	unsigned flags;
4707
4708	d = get_cg_data (node: &node, traverse_aliases: true);
4709	decl = node->decl;
4710	flags = flags_from_decl_or_type (decl);
4711
4712	/* Handle some TM builtins. Ordinarily these aren't actually generated
4713	at this point, but handling these functions when written in by the
4714	user makes it easier to build unit tests. */
4715	if (flags & ECF_TM_BUILTIN)
4716	return false;
4717
4718	/* Filter out all functions that are marked. */
4719	if (flags & ECF_TM_PURE)
4720	return false;
4721	if (is_tm_safe (x: decl))
4722	return false;
4723	if (is_tm_irrevocable (x: decl))
4724	return true;
4725	if (is_tm_callable (x: decl))
4726	return true;
4727	if (find_tm_replacement_function (fndecl: decl))
4728	return true;
4729
4730	/* If we aren't seeing the final version of the function we don't
4731	know what it will contain at runtime. */
4732	if (node->get_availability () < AVAIL_AVAILABLE)
4733	return true;
4734
4735	/* If the function must go irrevocable, then of course true. */
4736	if (d->is_irrevocable)
4737	return true;
4738
4739	/* If there are any blocks marked irrevocable, then the function
4740	as a whole may enter irrevocable. */
4741	if (d->irrevocable_blocks_clone)
4742	return true;
4743
4744	/* We may have previously marked this function as tm_may_enter_irr;
4745	see pass_diagnose_tm_blocks. */
4746	if (node->tm_may_enter_irr)
4747	return true;
4748
4749	/* Recurse on the main body for aliases. In general, this will
4750	result in one of the bits above being set so that we will not
4751	have to recurse next time. */
4752	if (node->alias)
4753	return ipa_tm_mayenterirr_function
4754	(node: cgraph_node::get (decl: thunk_info::get (node)->alias));
4755
4756	/* What remains is unmarked local functions without items that force
4757	the function to go irrevocable. */
4758	return false;
4759	}
4760
4761	/* Diagnose calls from transaction_safe functions to unmarked
4762	functions that are determined to not be safe. */
4763
4764	static void
4765	ipa_tm_diagnose_tm_safe (struct cgraph_node *node)
4766	{
4767	struct cgraph_edge *e;
4768
4769	for (e = node->callees; e ; e = e->next_callee)
4770	if (!is_tm_callable (x: e->callee->decl)
4771	&& e->callee->tm_may_enter_irr)
4772	error_at (gimple_location (g: e->call_stmt),
4773	"unsafe function call %qD within "
4774	"%<transaction_safe%> function", e->callee->decl);
4775	}
4776
4777	/* Diagnose call from atomic transactions to unmarked functions
4778	that are determined to not be safe. */
4779
4780	static void
4781	ipa_tm_diagnose_transaction (struct cgraph_node *node,
4782	struct tm_region *all_tm_regions)
4783	{
4784	struct tm_region *r;
4785
4786	for (r = all_tm_regions; r ; r = r->next)
4787	if (gimple_transaction_subcode (transaction_stmt: r->get_transaction_stmt ())
4788	& GTMA_IS_RELAXED)
4789	{
4790	/* Atomic transactions can be nested inside relaxed. */
4791	if (r->inner)
4792	ipa_tm_diagnose_transaction (node, all_tm_regions: r->inner);
4793	}
4794	else
4795	{
4796	vec<basic_block> bbs;
4797	gimple_stmt_iterator gsi;
4798	basic_block bb;
4799	size_t i;
4800
4801	bbs = get_tm_region_blocks (entry_block: r->entry_block, exit_blocks: r->exit_blocks,
4802	irr_blocks: r->irr_blocks, NULL, stop_at_irrevocable_p: false);
4803
4804	for (i = 0; bbs.iterate (ix: i, ptr: &bb); ++i)
4805	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
4806	{
4807	gimple *stmt = gsi_stmt (i: gsi);
4808	tree fndecl;
4809
4810	if (gimple_code (g: stmt) == GIMPLE_ASM)
4811	{
4812	error_at (gimple_location (g: stmt),
4813	"%<asm%> not allowed in atomic transaction");
4814	continue;
4815	}
4816
4817	if (!is_gimple_call (gs: stmt))
4818	continue;
4819	fndecl = gimple_call_fndecl (gs: stmt);
4820
4821	/* Indirect function calls have been diagnosed already. */
4822	if (!fndecl)
4823	continue;
4824
4825	/* Stop at the end of the transaction. */
4826	if (is_tm_ending_fndecl (fndecl))
4827	{
4828	if (bitmap_bit_p (r->exit_blocks, bb->index))
4829	break;
4830	continue;
4831	}
4832
4833	/* Marked functions have been diagnosed already. */
4834	if (is_tm_pure_call (call: stmt))
4835	continue;
4836	if (is_tm_callable (x: fndecl))
4837	continue;
4838
4839	if (cgraph_node::local_info_node (decl: fndecl)->tm_may_enter_irr)
4840	error_at (gimple_location (g: stmt),
4841	"unsafe function call %qD within "
4842	"atomic transaction", fndecl);
4843	}
4844
4845	bbs.release ();
4846	}
4847	}
4848
4849	/* Return a transactional mangled name for the DECL_ASSEMBLER_NAME in
4850	OLD_DECL. The returned value is a freshly malloced pointer that
4851	should be freed by the caller. */
4852
4853	static tree
4854	tm_mangle (tree old_asm_id)
4855	{
4856	const char *old_asm_name;
4857	char *tm_name;
4858	void *alloc = NULL;
4859	struct demangle_component *dc;
4860	tree new_asm_id;
4861
4862	/* Determine if the symbol is already a valid C++ mangled name. Do this
4863	even for C, which might be interfacing with C++ code via appropriately
4864	ugly identifiers. */
4865	/* ??? We could probably do just as well checking for "_Z" and be done. */
4866	old_asm_name = IDENTIFIER_POINTER (old_asm_id);
4867	dc = cplus_demangle_v3_components (mangled: old_asm_name, DMGL_NO_OPTS, mem: &alloc);
4868
4869	if (dc == NULL)
4870	{
4871	char length[12];
4872
4873	do_unencoded:
4874	sprintf (s: length, format: "%u", IDENTIFIER_LENGTH (old_asm_id));
4875	tm_name = concat ("_ZGTt", length, old_asm_name, NULL);
4876	}
4877	else
4878	{
4879	old_asm_name += 2; /* Skip _Z */
4880
4881	switch (dc->type)
4882	{
4883	case DEMANGLE_COMPONENT_TRANSACTION_CLONE:
4884	case DEMANGLE_COMPONENT_NONTRANSACTION_CLONE:
4885	/* Don't play silly games, you! */
4886	goto do_unencoded;
4887
4888	case DEMANGLE_COMPONENT_HIDDEN_ALIAS:
4889	/* I'd really like to know if we can ever be passed one of
4890	these from the C++ front end. The Logical Thing would
4891	seem that hidden-alias should be outer-most, so that we
4892	get hidden-alias of a transaction-clone and not vice-versa. */
4893	old_asm_name += 2;
4894	break;
4895
4896	default:
4897	break;
4898	}
4899
4900	tm_name = concat ("_ZGTt", old_asm_name, NULL);
4901	}
4902	free (ptr: alloc);
4903
4904	new_asm_id = get_identifier (tm_name);
4905	free (ptr: tm_name);
4906
4907	return new_asm_id;
4908	}
4909
4910	static inline void
4911	ipa_tm_mark_force_output_node (struct cgraph_node *node)
4912	{
4913	node->mark_force_output ();
4914	node->analyzed = true;
4915	}
4916
4917	static inline void
4918	ipa_tm_mark_forced_by_abi_node (struct cgraph_node *node)
4919	{
4920	node->forced_by_abi = true;
4921	node->analyzed = true;
4922	}
4923
4924	/* Callback data for ipa_tm_create_version_alias. */
4925	struct create_version_alias_info
4926	{
4927	struct cgraph_node *old_node;
4928	tree new_decl;
4929	};
4930
4931	/* A subroutine of ipa_tm_create_version, called via
4932	cgraph_for_node_and_aliases. Create new tm clones for each of
4933	the existing aliases. */
4934	static bool
4935	ipa_tm_create_version_alias (struct cgraph_node *node, void *data)
4936	{
4937	struct create_version_alias_info *info
4938	= (struct create_version_alias_info *)data;
4939	tree old_decl, new_decl, tm_name;
4940	struct cgraph_node *new_node;
4941
4942	if (!node->cpp_implicit_alias)
4943	return false;
4944
4945	old_decl = node->decl;
4946	tm_name = tm_mangle (DECL_ASSEMBLER_NAME (old_decl));
4947	new_decl = build_decl (DECL_SOURCE_LOCATION (old_decl),
4948	TREE_CODE (old_decl), tm_name,
4949	TREE_TYPE (old_decl));
4950
4951	SET_DECL_ASSEMBLER_NAME (new_decl, tm_name);
4952	SET_DECL_RTL (new_decl, NULL);
4953
4954	/* Based loosely on C++'s make_alias_for(). */
4955	TREE_PUBLIC (new_decl) = TREE_PUBLIC (old_decl);
4956	DECL_CONTEXT (new_decl) = DECL_CONTEXT (old_decl);
4957	DECL_LANG_SPECIFIC (new_decl) = DECL_LANG_SPECIFIC (old_decl);
4958	TREE_READONLY (new_decl) = TREE_READONLY (old_decl);
4959	DECL_EXTERNAL (new_decl) = 0;
4960	DECL_ARTIFICIAL (new_decl) = 1;
4961	TREE_ADDRESSABLE (new_decl) = 1;
4962	TREE_USED (new_decl) = 1;
4963	TREE_SYMBOL_REFERENCED (tm_name) = 1;
4964
4965	/* Perform the same remapping to the comdat group. */
4966	if (DECL_ONE_ONLY (new_decl))
4967	varpool_node::get (decl: new_decl)->set_comdat_group
4968	(tm_mangle (old_asm_id: decl_comdat_group_id (old_decl)));
4969
4970	new_node = cgraph_node::create_same_body_alias (alias: new_decl, decl: info->new_decl);
4971	new_node->tm_clone = true;
4972	new_node->externally_visible = info->old_node->externally_visible;
4973	new_node->no_reorder = info->old_node->no_reorder;
4974	/* ?? Do not traverse aliases here. */
4975	get_cg_data (node: &node, traverse_aliases: false)->clone = new_node;
4976
4977	record_tm_clone_pair (old_decl, new_decl);
4978
4979	if (info->old_node->force_output
4980	|| info->old_node->ref_list.first_referring ())
4981	ipa_tm_mark_force_output_node (node: new_node);
4982	if (info->old_node->forced_by_abi)
4983	ipa_tm_mark_forced_by_abi_node (node: new_node);
4984	return false;
4985	}
4986
4987	/* Create a copy of the function (possibly declaration only) of OLD_NODE,
4988	appropriate for the transactional clone. */
4989
4990	static void
4991	ipa_tm_create_version (struct cgraph_node *old_node)
4992	{
4993	tree new_decl, old_decl, tm_name;
4994	struct cgraph_node *new_node;
4995
4996	old_decl = old_node->decl;
4997	new_decl = copy_node (old_decl);
4998
4999	/* DECL_ASSEMBLER_NAME needs to be set before we call
5000	cgraph_copy_node_for_versioning below, because cgraph_node will
5001	fill the assembler_name_hash. */
5002	tm_name = tm_mangle (DECL_ASSEMBLER_NAME (old_decl));
5003	SET_DECL_ASSEMBLER_NAME (new_decl, tm_name);
5004	SET_DECL_RTL (new_decl, NULL);
5005	TREE_SYMBOL_REFERENCED (tm_name) = 1;
5006
5007	/* Perform the same remapping to the comdat group. */
5008	if (DECL_ONE_ONLY (new_decl))
5009	varpool_node::get (decl: new_decl)->set_comdat_group
5010	(tm_mangle (DECL_COMDAT_GROUP (old_decl)));
5011
5012	gcc_assert (!old_node->ipa_transforms_to_apply.exists ());
5013	new_node = old_node->create_version_clone (new_decl, redirect_callers: vNULL, NULL);
5014	new_node->local = false;
5015	new_node->externally_visible = old_node->externally_visible;
5016	new_node->lowered = true;
5017	new_node->tm_clone = 1;
5018	if (!old_node->implicit_section)
5019	new_node->set_section (*old_node);
5020	get_cg_data (node: &old_node, traverse_aliases: true)->clone = new_node;
5021
5022	if (old_node->get_availability () >= AVAIL_INTERPOSABLE)
5023	{
5024	/* Remap extern inline to static inline. */
5025	/* ??? Is it worth trying to use make_decl_one_only? */
5026	if (DECL_DECLARED_INLINE_P (new_decl) && DECL_EXTERNAL (new_decl))
5027	{
5028	DECL_EXTERNAL (new_decl) = 0;
5029	TREE_PUBLIC (new_decl) = 0;
5030	DECL_WEAK (new_decl) = 0;
5031	}
5032
5033	tree_function_versioning (old_decl, new_decl,
5034	NULL, NULL, false, NULL, NULL);
5035	}
5036
5037	record_tm_clone_pair (old_decl, new_decl);
5038
5039	symtab->call_cgraph_insertion_hooks (node: new_node);
5040	if (old_node->force_output
5041	|| old_node->ref_list.first_referring ())
5042	ipa_tm_mark_force_output_node (node: new_node);
5043	if (old_node->forced_by_abi)
5044	ipa_tm_mark_forced_by_abi_node (node: new_node);
5045
5046	/* Do the same thing, but for any aliases of the original node. */
5047	{
5048	struct create_version_alias_info data;
5049	data.old_node = old_node;
5050	data.new_decl = new_decl;
5051	old_node->call_for_symbol_thunks_and_aliases (callback: ipa_tm_create_version_alias,
5052	data: &data, include_overwritable: true);
5053	}
5054	}
5055
5056	/* Construct a call to TM_IRREVOCABLE and insert it at the beginning of BB. */
5057
5058	static void
5059	ipa_tm_insert_irr_call (struct cgraph_node *node, struct tm_region *region,
5060	basic_block bb)
5061	{
5062	gimple_stmt_iterator gsi;
5063	gcall *g;
5064
5065	transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
5066
5067	g = gimple_build_call (builtin_decl_explicit (fncode: BUILT_IN_TM_IRREVOCABLE),
5068	1, build_int_cst (NULL_TREE, MODE_SERIALIRREVOCABLE));
5069
5070	split_block_after_labels (bb);
5071	gsi = gsi_after_labels (bb);
5072	gsi_insert_before (&gsi, g, GSI_SAME_STMT);
5073
5074	node->create_edge (callee: cgraph_node::get_create
5075	(builtin_decl_explicit (fncode: BUILT_IN_TM_IRREVOCABLE)),
5076	call_stmt: g, count: gimple_bb (g)->count);
5077	}
5078
5079	/* Construct a call to TM_GETTMCLONE and insert it before GSI. */
5080
5081	static bool
5082	ipa_tm_insert_gettmclone_call (struct cgraph_node *node,
5083	struct tm_region *region,
5084	gimple_stmt_iterator *gsi, gcall *stmt)
5085	{
5086	tree gettm_fn, ret, old_fn, callfn;
5087	gcall *g;
5088	gassign *g2;
5089	bool safe;
5090
5091	old_fn = gimple_call_fn (gs: stmt);
5092
5093	if (TREE_CODE (old_fn) == ADDR_EXPR)
5094	{
5095	tree fndecl = TREE_OPERAND (old_fn, 0);
5096	tree clone = get_tm_clone_pair (fndecl);
5097
5098	/* By transforming the call into a TM_GETTMCLONE, we are
5099	technically taking the address of the original function and
5100	its clone. Explain this so inlining will know this function
5101	is needed. */
5102	cgraph_node::get (decl: fndecl)->mark_address_taken () ;
5103	if (clone)
5104	cgraph_node::get (decl: clone)->mark_address_taken ();
5105	}
5106
5107	safe = is_tm_safe (TREE_TYPE (old_fn));
5108	gettm_fn = builtin_decl_explicit (fncode: safe ? BUILT_IN_TM_GETTMCLONE_SAFE
5109	: BUILT_IN_TM_GETTMCLONE_IRR);
5110	ret = create_tmp_var (ptr_type_node);
5111
5112	if (!safe)
5113	transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
5114
5115	/* Discard OBJ_TYPE_REF, since we weren't able to fold it. */
5116	if (TREE_CODE (old_fn) == OBJ_TYPE_REF)
5117	old_fn = OBJ_TYPE_REF_EXPR (old_fn);
5118
5119	g = gimple_build_call (gettm_fn, 1, old_fn);
5120	ret = make_ssa_name (var: ret, stmt: g);
5121	gimple_call_set_lhs (gs: g, lhs: ret);
5122
5123	gsi_insert_before (gsi, g, GSI_SAME_STMT);
5124
5125	node->create_edge (callee: cgraph_node::get_create (gettm_fn), call_stmt: g, count: gimple_bb (g)->count);
5126
5127	/* Cast return value from tm_gettmclone* into appropriate function
5128	pointer. */
5129	callfn = create_tmp_var (TREE_TYPE (old_fn));
5130	g2 = gimple_build_assign (callfn,
5131	fold_build1 (NOP_EXPR, TREE_TYPE (callfn), ret));
5132	callfn = make_ssa_name (var: callfn, stmt: g2);
5133	gimple_assign_set_lhs (gs: g2, lhs: callfn);
5134	gsi_insert_before (gsi, g2, GSI_SAME_STMT);
5135
5136	/* ??? This is a hack to preserve the NOTHROW bit on the call,
5137	which we would have derived from the decl. Failure to save
5138	this bit means we might have to split the basic block. */
5139	if (gimple_call_nothrow_p (s: stmt))
5140	gimple_call_set_nothrow (s: stmt, nothrow_p: true);
5141
5142	gimple_call_set_fn (gs: stmt, fn: callfn);
5143
5144	/* Discarding OBJ_TYPE_REF above may produce incompatible LHS and RHS
5145	for a call statement. Fix it. */
5146	{
5147	tree lhs = gimple_call_lhs (gs: stmt);
5148	tree rettype = TREE_TYPE (gimple_call_fntype (stmt));
5149	if (lhs
5150	&& !useless_type_conversion_p (TREE_TYPE (lhs), rettype))
5151	{
5152	tree temp;
5153
5154	temp = create_tmp_reg (rettype);
5155	gimple_call_set_lhs (gs: stmt, lhs: temp);
5156
5157	g2 = gimple_build_assign (lhs,
5158	fold_build1 (VIEW_CONVERT_EXPR,
5159	TREE_TYPE (lhs), temp));
5160	gsi_insert_after (gsi, g2, GSI_SAME_STMT);
5161	}
5162	}
5163
5164	update_stmt (s: stmt);
5165	cgraph_edge *e = cgraph_node::get (decl: current_function_decl)->get_edge (call_stmt: stmt);
5166	if (e && e->indirect_info)
5167	e->indirect_info->polymorphic = false;
5168
5169	return true;
5170	}
5171
5172	/* Helper function for ipa_tm_transform_calls*. Given a call
5173	statement in GSI which resides inside transaction REGION, redirect
5174	the call to either its wrapper function, or its clone. */
5175
5176	static void
5177	ipa_tm_transform_calls_redirect (struct cgraph_node *node,
5178	struct tm_region *region,
5179	gimple_stmt_iterator *gsi,
5180	bool *need_ssa_rename_p)
5181	{
5182	gcall *stmt = as_a <gcall *> (p: gsi_stmt (i: *gsi));
5183	struct cgraph_node *new_node;
5184	struct cgraph_edge *e = node->get_edge (call_stmt: stmt);
5185	tree fndecl = gimple_call_fndecl (gs: stmt);
5186
5187	/* For indirect calls, pass the address through the runtime. */
5188	if (fndecl == NULL)
5189	{
5190	*need_ssa_rename_p |=
5191	ipa_tm_insert_gettmclone_call (node, region, gsi, stmt);
5192	return;
5193	}
5194
5195	/* Handle some TM builtins. Ordinarily these aren't actually generated
5196	at this point, but handling these functions when written in by the
5197	user makes it easier to build unit tests. */
5198	if (flags_from_decl_or_type (fndecl) & ECF_TM_BUILTIN)
5199	return;
5200
5201	/* Fixup recursive calls inside clones. */
5202	/* ??? Why did cgraph_copy_node_for_versioning update the call edges
5203	for recursion but not update the call statements themselves? */
5204	if (e->caller == e->callee && decl_is_tm_clone (fndecl: current_function_decl))
5205	{
5206	gimple_call_set_fndecl (gs: stmt, decl: current_function_decl);
5207	return;
5208	}
5209
5210	/* If there is a replacement, use it. */
5211	fndecl = find_tm_replacement_function (fndecl);
5212	if (fndecl)
5213	{
5214	new_node = cgraph_node::get_create (fndecl);
5215
5216	/* ??? Mark all transaction_wrap functions tm_may_enter_irr.
5217
5218	We can't do this earlier in record_tm_replacement because
5219	cgraph_remove_unreachable_nodes is called before we inject
5220	references to the node. Further, we can't do this in some
5221	nice central place in ipa_tm_execute because we don't have
5222	the exact list of wrapper functions that would be used.
5223	Marking more wrappers than necessary results in the creation
5224	of unnecessary cgraph_nodes, which can cause some of the
5225	other IPA passes to crash.
5226
5227	We do need to mark these nodes so that we get the proper
5228	result in expand_call_tm. */
5229	/* ??? This seems broken. How is it that we're marking the
5230	CALLEE as may_enter_irr? Surely we should be marking the
5231	CALLER. Also note that find_tm_replacement_function also
5232	contains mappings into the TM runtime, e.g. memcpy. These
5233	we know won't go irrevocable. */
5234	new_node->tm_may_enter_irr = 1;
5235	}
5236	else
5237	{
5238	struct tm_ipa_cg_data *d;
5239	struct cgraph_node *tnode = e->callee;
5240
5241	d = get_cg_data (node: &tnode, traverse_aliases: true);
5242	new_node = d->clone;
5243
5244	/* As we've already skipped pure calls and appropriate builtins,
5245	and we've already marked irrevocable blocks, if we can't come
5246	up with a static replacement, then ask the runtime. */
5247	if (new_node == NULL)
5248	{
5249	*need_ssa_rename_p |=
5250	ipa_tm_insert_gettmclone_call (node, region, gsi, stmt);
5251	return;
5252	}
5253
5254	fndecl = new_node->decl;
5255	}
5256
5257	e->redirect_callee (n: new_node);
5258	gimple_call_set_fndecl (gs: stmt, decl: fndecl);
5259	}
5260
5261	/* Helper function for ipa_tm_transform_calls. For a given BB,
5262	install calls to tm_irrevocable when IRR_BLOCKS are reached,
5263	redirect other calls to the generated transactional clone. */
5264
5265	static bool
5266	ipa_tm_transform_calls_1 (struct cgraph_node *node, struct tm_region *region,
5267	basic_block bb, bitmap irr_blocks)
5268	{
5269	gimple_stmt_iterator gsi;
5270	bool need_ssa_rename = false;
5271
5272	if (irr_blocks && bitmap_bit_p (irr_blocks, bb->index))
5273	{
5274	ipa_tm_insert_irr_call (node, region, bb);
5275	return true;
5276	}
5277
5278	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
5279	{
5280	gimple *stmt = gsi_stmt (i: gsi);
5281
5282	if (!is_gimple_call (gs: stmt))
5283	continue;
5284	if (is_tm_pure_call (call: stmt))
5285	continue;
5286
5287	/* Redirect edges to the appropriate replacement or clone. */
5288	ipa_tm_transform_calls_redirect (node, region, gsi: &gsi, need_ssa_rename_p: &need_ssa_rename);
5289	}
5290
5291	return need_ssa_rename;
5292	}
5293
5294	/* Walk the CFG for REGION, beginning at BB. Install calls to
5295	tm_irrevocable when IRR_BLOCKS are reached, redirect other calls to
5296	the generated transactional clone. */
5297
5298	static bool
5299	ipa_tm_transform_calls (struct cgraph_node *node, struct tm_region *region,
5300	basic_block bb, bitmap irr_blocks)
5301	{
5302	bool need_ssa_rename = false;
5303	edge e;
5304	edge_iterator ei;
5305	auto_vec<basic_block> queue;
5306	bitmap visited_blocks = BITMAP_ALLOC (NULL);
5307
5308	queue.safe_push (obj: bb);
5309	do
5310	{
5311	bb = queue.pop ();
5312
5313	need_ssa_rename |=
5314	ipa_tm_transform_calls_1 (node, region, bb, irr_blocks);
5315
5316	if (irr_blocks && bitmap_bit_p (irr_blocks, bb->index))
5317	continue;
5318
5319	if (region && bitmap_bit_p (region->exit_blocks, bb->index))
5320	continue;
5321
5322	FOR_EACH_EDGE (e, ei, bb->succs)
5323	if (!bitmap_bit_p (visited_blocks, e->dest->index))
5324	{
5325	bitmap_set_bit (visited_blocks, e->dest->index);
5326	queue.safe_push (obj: e->dest);
5327	}
5328	}
5329	while (!queue.is_empty ());
5330
5331	BITMAP_FREE (visited_blocks);
5332
5333	return need_ssa_rename;
5334	}
5335
5336	/* Transform the calls within the TM regions within NODE. */
5337
5338	static void
5339	ipa_tm_transform_transaction (struct cgraph_node *node)
5340	{
5341	struct tm_ipa_cg_data *d;
5342	struct tm_region *region;
5343	bool need_ssa_rename = false;
5344
5345	d = get_cg_data (node: &node, traverse_aliases: true);
5346
5347	push_cfun (DECL_STRUCT_FUNCTION (node->decl));
5348	calculate_dominance_info (CDI_DOMINATORS);
5349
5350	for (region = d->all_tm_regions; region; region = region->next)
5351	{
5352	/* If we're sure to go irrevocable, don't transform anything. */
5353	if (d->irrevocable_blocks_normal
5354	&& bitmap_bit_p (d->irrevocable_blocks_normal,
5355	region->entry_block->index))
5356	{
5357	transaction_subcode_ior (region, GTMA_DOES_GO_IRREVOCABLE
5358	| GTMA_MAY_ENTER_IRREVOCABLE
5359	| GTMA_HAS_NO_INSTRUMENTATION);
5360	continue;
5361	}
5362
5363	need_ssa_rename |=
5364	ipa_tm_transform_calls (node, region, bb: region->entry_block,
5365	irr_blocks: d->irrevocable_blocks_normal);
5366	}
5367
5368	if (need_ssa_rename)
5369	update_ssa (TODO_update_ssa_only_virtuals);
5370
5371	pop_cfun ();
5372	}
5373
5374	/* Transform the calls within the transactional clone of NODE. */
5375
5376	static void
5377	ipa_tm_transform_clone (struct cgraph_node *node)
5378	{
5379	struct tm_ipa_cg_data *d;
5380	bool need_ssa_rename;
5381
5382	d = get_cg_data (node: &node, traverse_aliases: true);
5383
5384	/* If this function makes no calls and has no irrevocable blocks,
5385	then there's nothing to do. */
5386	/* ??? Remove non-aborting top-level transactions. */
5387	if (!node->callees && !node->indirect_calls && !d->irrevocable_blocks_clone)
5388	return;
5389
5390	push_cfun (DECL_STRUCT_FUNCTION (d->clone->decl));
5391	calculate_dominance_info (CDI_DOMINATORS);
5392
5393	need_ssa_rename =
5394	ipa_tm_transform_calls (node: d->clone, NULL,
5395	bb: single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
5396	irr_blocks: d->irrevocable_blocks_clone);
5397
5398	if (need_ssa_rename)
5399	update_ssa (TODO_update_ssa_only_virtuals);
5400
5401	pop_cfun ();
5402	}
5403
5404	/* Main entry point for the transactional memory IPA pass. */
5405
5406	static unsigned int
5407	ipa_tm_execute (void)
5408	{
5409	cgraph_node_queue tm_callees = cgraph_node_queue ();
5410	/* List of functions that will go irrevocable. */
5411	cgraph_node_queue irr_worklist = cgraph_node_queue ();
5412
5413	struct cgraph_node *node;
5414	struct tm_ipa_cg_data *d;
5415	enum availability a;
5416	unsigned int i;
5417
5418	cgraph_node::checking_verify_cgraph_nodes ();
5419
5420	bitmap_obstack_initialize (&tm_obstack);
5421	initialize_original_copy_tables ();
5422
5423	/* For all local functions marked tm_callable, queue them. */
5424	FOR_EACH_DEFINED_FUNCTION (node)
5425	if (is_tm_callable (x: node->decl)
5426	&& node->get_availability () >= AVAIL_INTERPOSABLE)
5427	{
5428	d = get_cg_data (node: &node, traverse_aliases: true);
5429	maybe_push_queue (node, queue_p: &tm_callees, in_queue_p: &d->in_callee_queue);
5430	}
5431
5432	/* For all local reachable functions... */
5433	FOR_EACH_DEFINED_FUNCTION (node)
5434	if (node->lowered
5435	&& node->get_availability () >= AVAIL_INTERPOSABLE)
5436	{
5437	/* ... marked tm_pure, record that fact for the runtime by
5438	indicating that the pure function is its own tm_callable.
5439	No need to do this if the function's address can't be taken. */
5440	if (is_tm_pure (x: node->decl))
5441	{
5442	if (!node->local)
5443	record_tm_clone_pair (node->decl, node->decl);
5444	continue;
5445	}
5446
5447	push_cfun (DECL_STRUCT_FUNCTION (node->decl));
5448	calculate_dominance_info (CDI_DOMINATORS);
5449
5450	tm_region_init (NULL);
5451	if (all_tm_regions)
5452	{
5453	d = get_cg_data (node: &node, traverse_aliases: true);
5454
5455	/* Scan for calls that are in each transaction, and
5456	generate the uninstrumented code path. */
5457	ipa_tm_scan_calls_transaction (d, callees_p: &tm_callees);
5458
5459	/* Put it in the worklist so we can scan the function
5460	later (ipa_tm_scan_irr_function) and mark the
5461	irrevocable blocks. */
5462	maybe_push_queue (node, queue_p: &irr_worklist, in_queue_p: &d->in_worklist);
5463	d->want_irr_scan_normal = true;
5464	}
5465
5466	pop_cfun ();
5467	}
5468
5469	/* For every local function on the callee list, scan as if we will be
5470	creating a transactional clone, queueing all new functions we find
5471	along the way. */
5472	for (i = 0; i < tm_callees.length (); ++i)
5473	{
5474	node = tm_callees[i];
5475	a = node->get_availability ();
5476	d = get_cg_data (node: &node, traverse_aliases: true);
5477
5478	/* Put it in the worklist so we can scan the function later
5479	(ipa_tm_scan_irr_function) and mark the irrevocable
5480	blocks. */
5481	maybe_push_queue (node, queue_p: &irr_worklist, in_queue_p: &d->in_worklist);
5482
5483	/* Some callees cannot be arbitrarily cloned. These will always be
5484	irrevocable. Mark these now, so that we need not scan them. */
5485	if (is_tm_irrevocable (x: node->decl))
5486	ipa_tm_note_irrevocable (node, worklist_p: &irr_worklist);
5487	else if (a <= AVAIL_NOT_AVAILABLE
5488	&& !is_tm_safe_or_pure (x: node->decl))
5489	ipa_tm_note_irrevocable (node, worklist_p: &irr_worklist);
5490	else if (a >= AVAIL_INTERPOSABLE)
5491	{
5492	if (!tree_versionable_function_p (node->decl))
5493	ipa_tm_note_irrevocable (node, worklist_p: &irr_worklist);
5494	else if (!d->is_irrevocable)
5495	{
5496	/* If this is an alias, make sure its base is queued as well.
5497	we need not scan the callees now, as the base will do. */
5498	if (node->alias)
5499	{
5500	node = cgraph_node::get (decl: thunk_info::get (node)->alias);
5501	d = get_cg_data (node: &node, traverse_aliases: true);
5502	maybe_push_queue (node, queue_p: &tm_callees, in_queue_p: &d->in_callee_queue);
5503	continue;
5504	}
5505
5506	/* Add all nodes called by this function into
5507	tm_callees as well. */
5508	ipa_tm_scan_calls_clone (node, callees_p: &tm_callees);
5509	}
5510	}
5511	}
5512
5513	/* Iterate scans until no more work to be done. Prefer not to use
5514	vec::pop because the worklist tends to follow a breadth-first
5515	search of the callgraph, which should allow convergance with a
5516	minimum number of scans. But we also don't want the worklist
5517	array to grow without bound, so we shift the array up periodically. */
5518	for (i = 0; i < irr_worklist.length (); ++i)
5519	{
5520	if (i > 256 && i == irr_worklist.length () / 8)
5521	{
5522	irr_worklist.block_remove (ix: 0, len: i);
5523	i = 0;
5524	}
5525
5526	node = irr_worklist[i];
5527	d = get_cg_data (node: &node, traverse_aliases: true);
5528	d->in_worklist = false;
5529
5530	if (d->want_irr_scan_normal)
5531	{
5532	d->want_irr_scan_normal = false;
5533	ipa_tm_scan_irr_function (node, for_clone: false);
5534	}
5535	if (d->in_callee_queue && ipa_tm_scan_irr_function (node, for_clone: true))
5536	ipa_tm_note_irrevocable (node, worklist_p: &irr_worklist);
5537	}
5538
5539	/* For every function on the callee list, collect the tm_may_enter_irr
5540	bit on the node. */
5541	irr_worklist.truncate (size: 0);
5542	for (i = 0; i < tm_callees.length (); ++i)
5543	{
5544	node = tm_callees[i];
5545	if (ipa_tm_mayenterirr_function (node))
5546	{
5547	d = get_cg_data (node: &node, traverse_aliases: true);
5548	gcc_assert (d->in_worklist == false);
5549	maybe_push_queue (node, queue_p: &irr_worklist, in_queue_p: &d->in_worklist);
5550	}
5551	}
5552
5553	/* Propagate the tm_may_enter_irr bit to callers until stable. */
5554	for (i = 0; i < irr_worklist.length (); ++i)
5555	{
5556	struct cgraph_node *caller;
5557	struct cgraph_edge *e;
5558	struct ipa_ref *ref;
5559
5560	if (i > 256 && i == irr_worklist.length () / 8)
5561	{
5562	irr_worklist.block_remove (ix: 0, len: i);
5563	i = 0;
5564	}
5565
5566	node = irr_worklist[i];
5567	d = get_cg_data (node: &node, traverse_aliases: true);
5568	d->in_worklist = false;
5569	node->tm_may_enter_irr = true;
5570
5571	/* Propagate back to normal callers. */
5572	for (e = node->callers; e ; e = e->next_caller)
5573	{
5574	caller = e->caller;
5575	if (!is_tm_safe_or_pure (x: caller->decl)
5576	&& !caller->tm_may_enter_irr)
5577	{
5578	d = get_cg_data (node: &caller, traverse_aliases: true);
5579	maybe_push_queue (node: caller, queue_p: &irr_worklist, in_queue_p: &d->in_worklist);
5580	}
5581	}
5582
5583	/* Propagate back to referring aliases as well. */
5584	FOR_EACH_ALIAS (node, ref)
5585	{
5586	caller = dyn_cast<cgraph_node *> (p: ref->referring);
5587	if (!caller->tm_may_enter_irr)
5588	{
5589	/* ?? Do not traverse aliases here. */
5590	d = get_cg_data (node: &caller, traverse_aliases: false);
5591	maybe_push_queue (node: caller, queue_p: &irr_worklist, in_queue_p: &d->in_worklist);
5592	}
5593	}
5594	}
5595
5596	/* Now validate all tm_safe functions, and all atomic regions in
5597	other functions. */
5598	FOR_EACH_DEFINED_FUNCTION (node)
5599	if (node->lowered
5600	&& node->get_availability () >= AVAIL_INTERPOSABLE)
5601	{
5602	d = get_cg_data (node: &node, traverse_aliases: true);
5603	if (is_tm_safe (x: node->decl))
5604	ipa_tm_diagnose_tm_safe (node);
5605	else if (d->all_tm_regions)
5606	ipa_tm_diagnose_transaction (node, all_tm_regions: d->all_tm_regions);
5607	}
5608
5609	/* Create clones. Do those that are not irrevocable and have a
5610	positive call count. Do those publicly visible functions that
5611	the user directed us to clone. */
5612	for (i = 0; i < tm_callees.length (); ++i)
5613	{
5614	bool doit = false;
5615
5616	node = tm_callees[i];
5617	if (node->cpp_implicit_alias)
5618	continue;
5619
5620	a = node->get_availability ();
5621	d = get_cg_data (node: &node, traverse_aliases: true);
5622
5623	if (a <= AVAIL_NOT_AVAILABLE)
5624	doit = is_tm_callable (x: node->decl);
5625	else if (a <= AVAIL_AVAILABLE && is_tm_callable (x: node->decl))
5626	doit = true;
5627	else if (!d->is_irrevocable
5628	&& d->tm_callers_normal + d->tm_callers_clone > 0)
5629	doit = true;
5630
5631	if (doit)
5632	ipa_tm_create_version (old_node: node);
5633	}
5634
5635	/* Redirect calls to the new clones, and insert irrevocable marks. */
5636	for (i = 0; i < tm_callees.length (); ++i)
5637	{
5638	node = tm_callees[i];
5639	if (node->analyzed)
5640	{
5641	d = get_cg_data (node: &node, traverse_aliases: true);
5642	if (d->clone)
5643	ipa_tm_transform_clone (node);
5644	}
5645	}
5646	FOR_EACH_DEFINED_FUNCTION (node)
5647	if (node->lowered
5648	&& node->get_availability () >= AVAIL_INTERPOSABLE)
5649	{
5650	d = get_cg_data (node: &node, traverse_aliases: true);
5651	if (d->all_tm_regions)
5652	ipa_tm_transform_transaction (node);
5653	}
5654
5655	/* Free and clear all data structures. */
5656	tm_callees.release ();
5657	irr_worklist.release ();
5658	bitmap_obstack_release (&tm_obstack);
5659	free_original_copy_tables ();
5660
5661	FOR_EACH_FUNCTION (node)
5662	node->aux = NULL;
5663
5664	cgraph_node::checking_verify_cgraph_nodes ();
5665
5666	return 0;
5667	}
5668
5669	namespace {
5670
5671	const pass_data pass_data_ipa_tm =
5672	{
5673	.type: SIMPLE_IPA_PASS, /* type */
5674	.name: "tmipa", /* name */
5675	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
5676	.tv_id: TV_TRANS_MEM, /* tv_id */
5677	.properties_required: ( PROP_ssa | PROP_cfg ), /* properties_required */
5678	.properties_provided: 0, /* properties_provided */
5679	.properties_destroyed: 0, /* properties_destroyed */
5680	.todo_flags_start: 0, /* todo_flags_start */
5681	.todo_flags_finish: 0, /* todo_flags_finish */
5682	};
5683
5684	class pass_ipa_tm : public simple_ipa_opt_pass
5685	{
5686	public:
5687	pass_ipa_tm (gcc::context *ctxt)
5688	: simple_ipa_opt_pass (pass_data_ipa_tm, ctxt)
5689	{}
5690
5691	/* opt_pass methods: */
5692	bool gate (function *) final override { return flag_tm; }
5693	unsigned int execute (function *) final override { return ipa_tm_execute (); }
5694
5695	}; // class pass_ipa_tm
5696
5697	} // anon namespace
5698
5699	simple_ipa_opt_pass *
5700	make_pass_ipa_tm (gcc::context *ctxt)
5701	{
5702	return new pass_ipa_tm (ctxt);
5703	}
5704
5705	#include "gt-trans-mem.h"
5706