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