OSDN Git Service

de7a913be66bf63e5c634995aaee4e87dcd2add4
[pf3gnuchains/gcc-fork.git] / gcc / trans-mem.c
1 /* Passes for transactional memory support.
2    Copyright (C) 2008, 2009, 2010, 2011 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 \f
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
424 gate_tm (void)
425 {
426   return flag_tm;
427 }
428 \f
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
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
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
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 \f
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
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
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
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 \f
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.  */
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
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
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
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
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
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
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
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
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
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
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
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
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
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 \f
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
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
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
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
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
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
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
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
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 \f
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 /* True if there are pending edge statements to be committed for the
1761    current function being scanned in the tmmark pass.  */
1762 bool pending_edge_inserts_p;
1763
1764 static struct tm_region *all_tm_regions;
1765 static bitmap_obstack tm_obstack;
1766
1767
1768 /* A subroutine of tm_region_init.  Record the existance of the
1769    GIMPLE_TRANSACTION statement in a tree of tm_region elements.  */
1770
1771 static struct tm_region *
1772 tm_region_init_0 (struct tm_region *outer, basic_block bb, gimple stmt)
1773 {
1774   struct tm_region *region;
1775
1776   region = (struct tm_region *)
1777     obstack_alloc (&tm_obstack.obstack, sizeof (struct tm_region));
1778
1779   if (outer)
1780     {
1781       region->next = outer->inner;
1782       outer->inner = region;
1783     }
1784   else
1785     {
1786       region->next = all_tm_regions;
1787       all_tm_regions = region;
1788     }
1789   region->inner = NULL;
1790   region->outer = outer;
1791
1792   region->transaction_stmt = stmt;
1793
1794   /* There are either one or two edges out of the block containing
1795      the GIMPLE_TRANSACTION, one to the actual region and one to the
1796      "over" label if the region contains an abort.  The former will
1797      always be the one marked FALLTHRU.  */
1798   region->entry_block = FALLTHRU_EDGE (bb)->dest;
1799
1800   region->exit_blocks = BITMAP_ALLOC (&tm_obstack);
1801   region->irr_blocks = BITMAP_ALLOC (&tm_obstack);
1802
1803   return region;
1804 }
1805
1806 /* A subroutine of tm_region_init.  Record all the exit and
1807    irrevocable blocks in BB into the region's exit_blocks and
1808    irr_blocks bitmaps.  Returns the new region being scanned.  */
1809
1810 static struct tm_region *
1811 tm_region_init_1 (struct tm_region *region, basic_block bb)
1812 {
1813   gimple_stmt_iterator gsi;
1814   gimple g;
1815
1816   if (!region
1817       || (!region->irr_blocks && !region->exit_blocks))
1818     return region;
1819
1820   /* Check to see if this is the end of a region by seeing if it
1821      contains a call to __builtin_tm_commit{,_eh}.  Note that the
1822      outermost region for DECL_IS_TM_CLONE need not collect this.  */
1823   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
1824     {
1825       g = gsi_stmt (gsi);
1826       if (gimple_code (g) == GIMPLE_CALL)
1827         {
1828           tree fn = gimple_call_fndecl (g);
1829           if (fn && DECL_BUILT_IN_CLASS (fn) == BUILT_IN_NORMAL)
1830             {
1831               if ((DECL_FUNCTION_CODE (fn) == BUILT_IN_TM_COMMIT
1832                    || DECL_FUNCTION_CODE (fn) == BUILT_IN_TM_COMMIT_EH)
1833                   && region->exit_blocks)
1834                 {
1835                   bitmap_set_bit (region->exit_blocks, bb->index);
1836                   region = region->outer;
1837                   break;
1838                 }
1839               if (DECL_FUNCTION_CODE (fn) == BUILT_IN_TM_IRREVOCABLE)
1840                 bitmap_set_bit (region->irr_blocks, bb->index);
1841             }
1842         }
1843     }
1844   return region;
1845 }
1846
1847 /* Collect all of the transaction regions within the current function
1848    and record them in ALL_TM_REGIONS.  The REGION parameter may specify
1849    an "outermost" region for use by tm clones.  */
1850
1851 static void
1852 tm_region_init (struct tm_region *region)
1853 {
1854   gimple g;
1855   edge_iterator ei;
1856   edge e;
1857   basic_block bb;
1858   VEC(basic_block, heap) *queue = NULL;
1859   bitmap visited_blocks = BITMAP_ALLOC (NULL);
1860   struct tm_region *old_region;
1861
1862   all_tm_regions = region;
1863   bb = single_succ (ENTRY_BLOCK_PTR);
1864
1865   VEC_safe_push (basic_block, heap, queue, bb);
1866   gcc_assert (!bb->aux);        /* FIXME: Remove me.  */
1867   bb->aux = region;
1868   do
1869     {
1870       bb = VEC_pop (basic_block, queue);
1871       region = (struct tm_region *)bb->aux;
1872       bb->aux = NULL;
1873
1874       /* Record exit and irrevocable blocks.  */
1875       region = tm_region_init_1 (region, bb);
1876
1877       /* Check for the last statement in the block beginning a new region.  */
1878       g = last_stmt (bb);
1879       old_region = region;
1880       if (g && gimple_code (g) == GIMPLE_TRANSACTION)
1881         region = tm_region_init_0 (region, bb, g);
1882
1883       /* Process subsequent blocks.  */
1884       FOR_EACH_EDGE (e, ei, bb->succs)
1885         if (!bitmap_bit_p (visited_blocks, e->dest->index))
1886           {
1887             bitmap_set_bit (visited_blocks, e->dest->index);
1888             VEC_safe_push (basic_block, heap, queue, e->dest);
1889             gcc_assert (!e->dest->aux); /* FIXME: Remove me.  */
1890
1891             /* If the current block started a new region, make sure that only
1892                the entry block of the new region is associated with this region.
1893                Other successors are still part of the old region.  */
1894             if (old_region != region && e->dest != region->entry_block)
1895               e->dest->aux = old_region;
1896             else
1897               e->dest->aux = region;
1898           }
1899     }
1900   while (!VEC_empty (basic_block, queue));
1901   VEC_free (basic_block, heap, queue);
1902   BITMAP_FREE (visited_blocks);
1903 }
1904
1905 /* The "gate" function for all transactional memory expansion and optimization
1906    passes.  We collect region information for each top-level transaction, and
1907    if we don't find any, we skip all of the TM passes.  Each region will have
1908    all of the exit blocks recorded, and the originating statement.  */
1909
1910 static bool
1911 gate_tm_init (void)
1912 {
1913   if (!flag_tm)
1914     return false;
1915
1916   calculate_dominance_info (CDI_DOMINATORS);
1917   bitmap_obstack_initialize (&tm_obstack);
1918
1919   /* If the function is a TM_CLONE, then the entire function is the region.  */
1920   if (decl_is_tm_clone (current_function_decl))
1921     {
1922       struct tm_region *region = (struct tm_region *)
1923         obstack_alloc (&tm_obstack.obstack, sizeof (struct tm_region));
1924       memset (region, 0, sizeof (*region));
1925       region->entry_block = single_succ (ENTRY_BLOCK_PTR);
1926       /* For a clone, the entire function is the region.  But even if
1927          we don't need to record any exit blocks, we may need to
1928          record irrevocable blocks.  */
1929       region->irr_blocks = BITMAP_ALLOC (&tm_obstack);
1930
1931       tm_region_init (region);
1932     }
1933   else
1934     {
1935       tm_region_init (NULL);
1936
1937       /* If we didn't find any regions, cleanup and skip the whole tree
1938          of tm-related optimizations.  */
1939       if (all_tm_regions == NULL)
1940         {
1941           bitmap_obstack_release (&tm_obstack);
1942           return false;
1943         }
1944     }
1945
1946   return true;
1947 }
1948
1949 struct gimple_opt_pass pass_tm_init =
1950 {
1951  {
1952   GIMPLE_PASS,
1953   "*tminit",                            /* name */
1954   gate_tm_init,                         /* gate */
1955   NULL,                                 /* execute */
1956   NULL,                                 /* sub */
1957   NULL,                                 /* next */
1958   0,                                    /* static_pass_number */
1959   TV_TRANS_MEM,                         /* tv_id */
1960   PROP_ssa | PROP_cfg,                  /* properties_required */
1961   0,                                    /* properties_provided */
1962   0,                                    /* properties_destroyed */
1963   0,                                    /* todo_flags_start */
1964   0,                                    /* todo_flags_finish */
1965  }
1966 };
1967 \f
1968 /* Add FLAGS to the GIMPLE_TRANSACTION subcode for the transaction region
1969    represented by STATE.  */
1970
1971 static inline void
1972 transaction_subcode_ior (struct tm_region *region, unsigned flags)
1973 {
1974   if (region && region->transaction_stmt)
1975     {
1976       flags |= gimple_transaction_subcode (region->transaction_stmt);
1977       gimple_transaction_set_subcode (region->transaction_stmt, flags);
1978     }
1979 }
1980
1981 /* Construct a memory load in a transactional context.  Return the
1982    gimple statement performing the load, or NULL if there is no
1983    TM_LOAD builtin of the appropriate size to do the load.
1984
1985    LOC is the location to use for the new statement(s).  */
1986
1987 static gimple
1988 build_tm_load (location_t loc, tree lhs, tree rhs, gimple_stmt_iterator *gsi)
1989 {
1990   enum built_in_function code = END_BUILTINS;
1991   tree t, type = TREE_TYPE (rhs), decl;
1992   gimple gcall;
1993
1994   if (type == float_type_node)
1995     code = BUILT_IN_TM_LOAD_FLOAT;
1996   else if (type == double_type_node)
1997     code = BUILT_IN_TM_LOAD_DOUBLE;
1998   else if (type == long_double_type_node)
1999     code = BUILT_IN_TM_LOAD_LDOUBLE;
2000   else if (TYPE_SIZE_UNIT (type) != NULL
2001            && host_integerp (TYPE_SIZE_UNIT (type), 1))
2002     {
2003       switch (tree_low_cst (TYPE_SIZE_UNIT (type), 1))
2004         {
2005         case 1:
2006           code = BUILT_IN_TM_LOAD_1;
2007           break;
2008         case 2:
2009           code = BUILT_IN_TM_LOAD_2;
2010           break;
2011         case 4:
2012           code = BUILT_IN_TM_LOAD_4;
2013           break;
2014         case 8:
2015           code = BUILT_IN_TM_LOAD_8;
2016           break;
2017         }
2018     }
2019
2020   if (code == END_BUILTINS)
2021     {
2022       decl = targetm.vectorize.builtin_tm_load (type);
2023       if (!decl)
2024         return NULL;
2025     }
2026   else
2027     decl = builtin_decl_explicit (code);
2028
2029   t = gimplify_addr (gsi, rhs);
2030   gcall = gimple_build_call (decl, 1, t);
2031   gimple_set_location (gcall, loc);
2032
2033   t = TREE_TYPE (TREE_TYPE (decl));
2034   if (useless_type_conversion_p (type, t))
2035     {
2036       gimple_call_set_lhs (gcall, lhs);
2037       gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2038     }
2039   else
2040     {
2041       gimple g;
2042       tree temp;
2043
2044       temp = make_rename_temp (t, NULL);
2045       gimple_call_set_lhs (gcall, temp);
2046       gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2047
2048       t = fold_build1 (VIEW_CONVERT_EXPR, type, temp);
2049       g = gimple_build_assign (lhs, t);
2050       gsi_insert_before (gsi, g, GSI_SAME_STMT);
2051     }
2052
2053   return gcall;
2054 }
2055
2056
2057 /* Similarly for storing TYPE in a transactional context.  */
2058
2059 static gimple
2060 build_tm_store (location_t loc, tree lhs, tree rhs, gimple_stmt_iterator *gsi)
2061 {
2062   enum built_in_function code = END_BUILTINS;
2063   tree t, fn, type = TREE_TYPE (rhs), simple_type;
2064   gimple gcall;
2065
2066   if (type == float_type_node)
2067     code = BUILT_IN_TM_STORE_FLOAT;
2068   else if (type == double_type_node)
2069     code = BUILT_IN_TM_STORE_DOUBLE;
2070   else if (type == long_double_type_node)
2071     code = BUILT_IN_TM_STORE_LDOUBLE;
2072   else if (TYPE_SIZE_UNIT (type) != NULL
2073            && host_integerp (TYPE_SIZE_UNIT (type), 1))
2074     {
2075       switch (tree_low_cst (TYPE_SIZE_UNIT (type), 1))
2076         {
2077         case 1:
2078           code = BUILT_IN_TM_STORE_1;
2079           break;
2080         case 2:
2081           code = BUILT_IN_TM_STORE_2;
2082           break;
2083         case 4:
2084           code = BUILT_IN_TM_STORE_4;
2085           break;
2086         case 8:
2087           code = BUILT_IN_TM_STORE_8;
2088           break;
2089         }
2090     }
2091
2092   if (code == END_BUILTINS)
2093     {
2094       fn = targetm.vectorize.builtin_tm_store (type);
2095       if (!fn)
2096         return NULL;
2097     }
2098   else
2099     fn = builtin_decl_explicit (code);
2100
2101   simple_type = TREE_VALUE (TREE_CHAIN (TYPE_ARG_TYPES (TREE_TYPE (fn))));
2102
2103   if (TREE_CODE (rhs) == CONSTRUCTOR)
2104     {
2105       /* Handle the easy initialization to zero.  */
2106       if (CONSTRUCTOR_ELTS (rhs) == 0)
2107         rhs = build_int_cst (simple_type, 0);
2108       else
2109         {
2110           /* ...otherwise punt to the caller and probably use
2111             BUILT_IN_TM_MEMMOVE, because we can't wrap a
2112             VIEW_CONVERT_EXPR around a CONSTRUCTOR (below) and produce
2113             valid gimple.  */
2114           return NULL;
2115         }
2116     }
2117   else if (!useless_type_conversion_p (simple_type, type))
2118     {
2119       gimple g;
2120       tree temp;
2121
2122       temp = make_rename_temp (simple_type, NULL);
2123       t = fold_build1 (VIEW_CONVERT_EXPR, simple_type, rhs);
2124       g = gimple_build_assign (temp, t);
2125       gimple_set_location (g, loc);
2126       gsi_insert_before (gsi, g, GSI_SAME_STMT);
2127
2128       rhs = temp;
2129     }
2130
2131   t = gimplify_addr (gsi, lhs);
2132   gcall = gimple_build_call (fn, 2, t, rhs);
2133   gimple_set_location (gcall, loc);
2134   gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2135
2136   return gcall;
2137 }
2138
2139
2140 /* Expand an assignment statement into transactional builtins.  */
2141
2142 static void
2143 expand_assign_tm (struct tm_region *region, gimple_stmt_iterator *gsi)
2144 {
2145   gimple stmt = gsi_stmt (*gsi);
2146   location_t loc = gimple_location (stmt);
2147   tree lhs = gimple_assign_lhs (stmt);
2148   tree rhs = gimple_assign_rhs1 (stmt);
2149   bool store_p = requires_barrier (region->entry_block, lhs, NULL);
2150   bool load_p = requires_barrier (region->entry_block, rhs, NULL);
2151   gimple gcall = NULL;
2152
2153   if (!load_p && !store_p)
2154     {
2155       /* Add thread private addresses to log if applicable.  */
2156       requires_barrier (region->entry_block, lhs, stmt);
2157       gsi_next (gsi);
2158       return;
2159     }
2160
2161   gsi_remove (gsi, true);
2162
2163   if (load_p && !store_p)
2164     {
2165       transaction_subcode_ior (region, GTMA_HAVE_LOAD);
2166       gcall = build_tm_load (loc, lhs, rhs, gsi);
2167     }
2168   else if (store_p && !load_p)
2169     {
2170       transaction_subcode_ior (region, GTMA_HAVE_STORE);
2171       gcall = build_tm_store (loc, lhs, rhs, gsi);
2172     }
2173   if (!gcall)
2174     {
2175       tree lhs_addr, rhs_addr, tmp;
2176
2177       if (load_p)
2178         transaction_subcode_ior (region, GTMA_HAVE_LOAD);
2179       if (store_p)
2180         transaction_subcode_ior (region, GTMA_HAVE_STORE);
2181
2182       /* ??? Figure out if there's any possible overlap between the LHS
2183          and the RHS and if not, use MEMCPY.  */
2184
2185       if (load_p && is_gimple_reg (lhs))
2186         {
2187           tmp = create_tmp_var (TREE_TYPE (lhs), NULL);
2188           lhs_addr = build_fold_addr_expr (tmp);
2189         }
2190       else
2191         {
2192           tmp = NULL_TREE;
2193           lhs_addr = gimplify_addr (gsi, lhs);
2194         }
2195       rhs_addr = gimplify_addr (gsi, rhs);
2196       gcall = gimple_build_call (builtin_decl_explicit (BUILT_IN_TM_MEMMOVE),
2197                                  3, lhs_addr, rhs_addr,
2198                                  TYPE_SIZE_UNIT (TREE_TYPE (lhs)));
2199       gimple_set_location (gcall, loc);
2200       gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2201
2202       if (tmp)
2203         {
2204           gcall = gimple_build_assign (lhs, tmp);
2205           gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2206         }
2207     }
2208
2209   /* Now that we have the load/store in its instrumented form, add
2210      thread private addresses to the log if applicable.  */
2211   if (!store_p)
2212     requires_barrier (region->entry_block, lhs, gcall);
2213
2214   /* add_stmt_to_tm_region  (region, gcall); */
2215 }
2216
2217
2218 /* Expand a call statement as appropriate for a transaction.  That is,
2219    either verify that the call does not affect the transaction, or
2220    redirect the call to a clone that handles transactions, or change
2221    the transaction state to IRREVOCABLE.  Return true if the call is
2222    one of the builtins that end a transaction.  */
2223
2224 static bool
2225 expand_call_tm (struct tm_region *region,
2226                 gimple_stmt_iterator *gsi)
2227 {
2228   gimple stmt = gsi_stmt (*gsi);
2229   tree lhs = gimple_call_lhs (stmt);
2230   tree fn_decl;
2231   struct cgraph_node *node;
2232   bool retval = false;
2233
2234   fn_decl = gimple_call_fndecl (stmt);
2235
2236   if (fn_decl == builtin_decl_explicit (BUILT_IN_TM_MEMCPY)
2237       || fn_decl == builtin_decl_explicit (BUILT_IN_TM_MEMMOVE))
2238     transaction_subcode_ior (region, GTMA_HAVE_STORE | GTMA_HAVE_LOAD);
2239   if (fn_decl == builtin_decl_explicit (BUILT_IN_TM_MEMSET))
2240     transaction_subcode_ior (region, GTMA_HAVE_STORE);
2241
2242   if (is_tm_pure_call (stmt))
2243     return false;
2244
2245   if (fn_decl)
2246     retval = is_tm_ending_fndecl (fn_decl);
2247   if (!retval)
2248     {
2249       /* Assume all non-const/pure calls write to memory, except
2250          transaction ending builtins.  */
2251       transaction_subcode_ior (region, GTMA_HAVE_STORE);
2252     }
2253
2254   /* For indirect calls, we already generated a call into the runtime.  */
2255   if (!fn_decl)
2256     {
2257       tree fn = gimple_call_fn (stmt);
2258
2259       /* We are guaranteed never to go irrevocable on a safe or pure
2260          call, and the pure call was handled above.  */
2261       if (is_tm_safe (fn))
2262         return false;
2263       else
2264         transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
2265
2266       return false;
2267     }
2268
2269   node = cgraph_get_node (fn_decl);
2270   if (node->local.tm_may_enter_irr)
2271     transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
2272
2273   if (is_tm_abort (fn_decl))
2274     {
2275       transaction_subcode_ior (region, GTMA_HAVE_ABORT);
2276       return true;
2277     }
2278
2279   /* Instrument the store if needed.
2280
2281      If the assignment happens inside the function call (return slot
2282      optimization), there is no instrumentation to be done, since
2283      the callee should have done the right thing.  */
2284   if (lhs && requires_barrier (region->entry_block, lhs, stmt)
2285       && !gimple_call_return_slot_opt_p (stmt))
2286     {
2287       tree tmp = make_rename_temp (TREE_TYPE (lhs), NULL);
2288       location_t loc = gimple_location (stmt);
2289       edge fallthru_edge = NULL;
2290
2291       /* Remember if the call was going to throw.  */
2292       if (stmt_can_throw_internal (stmt))
2293         {
2294           edge_iterator ei;
2295           edge e;
2296           basic_block bb = gimple_bb (stmt);
2297
2298           FOR_EACH_EDGE (e, ei, bb->succs)
2299             if (e->flags & EDGE_FALLTHRU)
2300               {
2301                 fallthru_edge = e;
2302                 break;
2303               }
2304         }
2305
2306       gimple_call_set_lhs (stmt, tmp);
2307       update_stmt (stmt);
2308       stmt = gimple_build_assign (lhs, tmp);
2309       gimple_set_location (stmt, loc);
2310
2311       /* We cannot throw in the middle of a BB.  If the call was going
2312          to throw, place the instrumentation on the fallthru edge, so
2313          the call remains the last statement in the block.  */
2314       if (fallthru_edge)
2315         {
2316           gimple_seq fallthru_seq = gimple_seq_alloc_with_stmt (stmt);
2317           gimple_stmt_iterator fallthru_gsi = gsi_start (fallthru_seq);
2318           expand_assign_tm (region, &fallthru_gsi);
2319           gsi_insert_seq_on_edge (fallthru_edge, fallthru_seq);
2320           pending_edge_inserts_p = true;
2321         }
2322       else
2323         {
2324           gsi_insert_after (gsi, stmt, GSI_CONTINUE_LINKING);
2325           expand_assign_tm (region, gsi);
2326         }
2327
2328       transaction_subcode_ior (region, GTMA_HAVE_STORE);
2329     }
2330
2331   return retval;
2332 }
2333
2334
2335 /* Expand all statements in BB as appropriate for being inside
2336    a transaction.  */
2337
2338 static void
2339 expand_block_tm (struct tm_region *region, basic_block bb)
2340 {
2341   gimple_stmt_iterator gsi;
2342
2343   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2344     {
2345       gimple stmt = gsi_stmt (gsi);
2346       switch (gimple_code (stmt))
2347         {
2348         case GIMPLE_ASSIGN:
2349           /* Only memory reads/writes need to be instrumented.  */
2350           if (gimple_assign_single_p (stmt)
2351               && !gimple_clobber_p (stmt))
2352             {
2353               expand_assign_tm (region, &gsi);
2354               continue;
2355             }
2356           break;
2357
2358         case GIMPLE_CALL:
2359           if (expand_call_tm (region, &gsi))
2360             return;
2361           break;
2362
2363         case GIMPLE_ASM:
2364           gcc_unreachable ();
2365
2366         default:
2367           break;
2368         }
2369       if (!gsi_end_p (gsi))
2370         gsi_next (&gsi);
2371     }
2372 }
2373
2374 /* Return the list of basic-blocks in REGION.
2375
2376    STOP_AT_IRREVOCABLE_P is true if caller is uninterested in blocks
2377    following a TM_IRREVOCABLE call.  */
2378
2379 static VEC (basic_block, heap) *
2380 get_tm_region_blocks (basic_block entry_block,
2381                       bitmap exit_blocks,
2382                       bitmap irr_blocks,
2383                       bitmap all_region_blocks,
2384                       bool stop_at_irrevocable_p)
2385 {
2386   VEC(basic_block, heap) *bbs = NULL;
2387   unsigned i;
2388   edge e;
2389   edge_iterator ei;
2390   bitmap visited_blocks = BITMAP_ALLOC (NULL);
2391
2392   i = 0;
2393   VEC_safe_push (basic_block, heap, bbs, entry_block);
2394   bitmap_set_bit (visited_blocks, entry_block->index);
2395
2396   do
2397     {
2398       basic_block bb = VEC_index (basic_block, bbs, i++);
2399
2400       if (exit_blocks &&
2401           bitmap_bit_p (exit_blocks, bb->index))
2402         continue;
2403
2404       if (stop_at_irrevocable_p
2405           && irr_blocks
2406           && bitmap_bit_p (irr_blocks, bb->index))
2407         continue;
2408
2409       FOR_EACH_EDGE (e, ei, bb->succs)
2410         if (!bitmap_bit_p (visited_blocks, e->dest->index))
2411           {
2412             bitmap_set_bit (visited_blocks, e->dest->index);
2413             VEC_safe_push (basic_block, heap, bbs, e->dest);
2414           }
2415     }
2416   while (i < VEC_length (basic_block, bbs));
2417
2418   if (all_region_blocks)
2419     bitmap_ior_into (all_region_blocks, visited_blocks);
2420
2421   BITMAP_FREE (visited_blocks);
2422   return bbs;
2423 }
2424
2425 /* Entry point to the MARK phase of TM expansion.  Here we replace
2426    transactional memory statements with calls to builtins, and function
2427    calls with their transactional clones (if available).  But we don't
2428    yet lower GIMPLE_TRANSACTION or add the transaction restart back-edges.  */
2429
2430 static unsigned int
2431 execute_tm_mark (void)
2432 {
2433   struct tm_region *region;
2434   basic_block bb;
2435   VEC (basic_block, heap) *queue;
2436   size_t i;
2437
2438   queue = VEC_alloc (basic_block, heap, 10);
2439   pending_edge_inserts_p = false;
2440
2441   for (region = all_tm_regions; region ; region = region->next)
2442     {
2443       tm_log_init ();
2444       /* If we have a transaction...  */
2445       if (region->exit_blocks)
2446         {
2447           unsigned int subcode
2448             = gimple_transaction_subcode (region->transaction_stmt);
2449
2450           /* Collect a new SUBCODE set, now that optimizations are done...  */
2451           if (subcode & GTMA_DOES_GO_IRREVOCABLE)
2452             subcode &= (GTMA_DECLARATION_MASK | GTMA_DOES_GO_IRREVOCABLE
2453                         | GTMA_MAY_ENTER_IRREVOCABLE);
2454           else
2455             subcode &= GTMA_DECLARATION_MASK;
2456           gimple_transaction_set_subcode (region->transaction_stmt, subcode);
2457         }
2458
2459       queue = get_tm_region_blocks (region->entry_block,
2460                                     region->exit_blocks,
2461                                     region->irr_blocks,
2462                                     NULL,
2463                                     /*stop_at_irr_p=*/true);
2464       for (i = 0; VEC_iterate (basic_block, queue, i, bb); ++i)
2465         expand_block_tm (region, bb);
2466       VEC_free (basic_block, heap, queue);
2467
2468       tm_log_emit ();
2469     }
2470
2471   if (pending_edge_inserts_p)
2472     gsi_commit_edge_inserts ();
2473   return 0;
2474 }
2475
2476 struct gimple_opt_pass pass_tm_mark =
2477 {
2478  {
2479   GIMPLE_PASS,
2480   "tmmark",                             /* name */
2481   NULL,                                 /* gate */
2482   execute_tm_mark,                      /* execute */
2483   NULL,                                 /* sub */
2484   NULL,                                 /* next */
2485   0,                                    /* static_pass_number */
2486   TV_TRANS_MEM,                         /* tv_id */
2487   PROP_ssa | PROP_cfg,                  /* properties_required */
2488   0,                                    /* properties_provided */
2489   0,                                    /* properties_destroyed */
2490   0,                                    /* todo_flags_start */
2491   TODO_update_ssa
2492   | TODO_verify_ssa
2493   | TODO_dump_func,                     /* todo_flags_finish */
2494  }
2495 };
2496 \f
2497 /* Create an abnormal call edge from BB to the first block of the region
2498    represented by STATE.  Also record the edge in the TM_RESTART map.  */
2499
2500 static inline void
2501 make_tm_edge (gimple stmt, basic_block bb, struct tm_region *region)
2502 {
2503   void **slot;
2504   struct tm_restart_node *n, dummy;
2505
2506   if (cfun->gimple_df->tm_restart == NULL)
2507     cfun->gimple_df->tm_restart = htab_create_ggc (31, struct_ptr_hash,
2508                                                    struct_ptr_eq, ggc_free);
2509
2510   dummy.stmt = stmt;
2511   dummy.label_or_list = gimple_block_label (region->entry_block);
2512   slot = htab_find_slot (cfun->gimple_df->tm_restart, &dummy, INSERT);
2513   n = (struct tm_restart_node *) *slot;
2514   if (n == NULL)
2515     {
2516       n = ggc_alloc_tm_restart_node ();
2517       *n = dummy;
2518     }
2519   else
2520     {
2521       tree old = n->label_or_list;
2522       if (TREE_CODE (old) == LABEL_DECL)
2523         old = tree_cons (NULL, old, NULL);
2524       n->label_or_list = tree_cons (NULL, dummy.label_or_list, old);
2525     }
2526
2527   make_edge (bb, region->entry_block, EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
2528 }
2529
2530
2531 /* Split block BB as necessary for every builtin function we added, and
2532    wire up the abnormal back edges implied by the transaction restart.  */
2533
2534 static void
2535 expand_block_edges (struct tm_region *region, basic_block bb)
2536 {
2537   gimple_stmt_iterator gsi;
2538
2539   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2540     {
2541       gimple stmt = gsi_stmt (gsi);
2542
2543       /* ??? TM_COMMIT (and any other tm builtin function) in a nested
2544          transaction has an abnormal edge back to the outer-most transaction
2545          (there are no nested retries), while a TM_ABORT also has an abnormal
2546          backedge to the inner-most transaction.  We haven't actually saved
2547          the inner-most transaction here.  We should be able to get to it
2548          via the region_nr saved on STMT, and read the transaction_stmt from
2549          that, and find the first region block from there.  */
2550       /* ??? Shouldn't we split for any non-pure, non-irrevocable function?  */
2551       if (gimple_code (stmt) == GIMPLE_CALL
2552           && (gimple_call_flags (stmt) & ECF_TM_BUILTIN) != 0)
2553         {
2554           if (gsi_one_before_end_p (gsi))
2555             make_tm_edge (stmt, bb, region);
2556           else
2557             {
2558               edge e = split_block (bb, stmt);
2559               make_tm_edge (stmt, bb, region);
2560               bb = e->dest;
2561               gsi = gsi_start_bb (bb);
2562             }
2563
2564           /* Delete any tail-call annotation that may have been added.
2565              The tail-call pass may have mis-identified the commit as being
2566              a candidate because we had not yet added this restart edge.  */
2567           gimple_call_set_tail (stmt, false);
2568         }
2569
2570       gsi_next (&gsi);
2571     }
2572 }
2573
2574 /* Expand the GIMPLE_TRANSACTION statement into the STM library call.  */
2575
2576 static void
2577 expand_transaction (struct tm_region *region)
2578 {
2579   tree status, tm_start;
2580   basic_block atomic_bb, slice_bb;
2581   gimple_stmt_iterator gsi;
2582   tree t1, t2;
2583   gimple g;
2584   int flags, subcode;
2585
2586   tm_start = builtin_decl_explicit (BUILT_IN_TM_START);
2587   status = make_rename_temp (TREE_TYPE (TREE_TYPE (tm_start)), "tm_state");
2588
2589   /* ??? There are plenty of bits here we're not computing.  */
2590   subcode = gimple_transaction_subcode (region->transaction_stmt);
2591   if (subcode & GTMA_DOES_GO_IRREVOCABLE)
2592     flags = PR_DOESGOIRREVOCABLE | PR_UNINSTRUMENTEDCODE;
2593   else
2594     flags = PR_INSTRUMENTEDCODE;
2595   if ((subcode & GTMA_MAY_ENTER_IRREVOCABLE) == 0)
2596     flags |= PR_HASNOIRREVOCABLE;
2597   /* If the transaction does not have an abort in lexical scope and is not
2598      marked as an outer transaction, then it will never abort.  */
2599   if ((subcode & GTMA_HAVE_ABORT) == 0
2600       && (subcode & GTMA_IS_OUTER) == 0)
2601     flags |= PR_HASNOABORT;
2602   if ((subcode & GTMA_HAVE_STORE) == 0)
2603     flags |= PR_READONLY;
2604   t2 = build_int_cst (TREE_TYPE (status), flags);
2605   g = gimple_build_call (tm_start, 1, t2);
2606   gimple_call_set_lhs (g, status);
2607   gimple_set_location (g, gimple_location (region->transaction_stmt));
2608
2609   atomic_bb = gimple_bb (region->transaction_stmt);
2610
2611   if (!VEC_empty (tree, tm_log_save_addresses))
2612     tm_log_emit_saves (region->entry_block, atomic_bb);
2613
2614   gsi = gsi_last_bb (atomic_bb);
2615   gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2616   gsi_remove (&gsi, true);
2617
2618   if (!VEC_empty (tree, tm_log_save_addresses))
2619     region->entry_block =
2620       tm_log_emit_save_or_restores (region->entry_block,
2621                                     A_RESTORELIVEVARIABLES,
2622                                     status,
2623                                     tm_log_emit_restores,
2624                                     atomic_bb,
2625                                     FALLTHRU_EDGE (atomic_bb),
2626                                     &slice_bb);
2627   else
2628     slice_bb = atomic_bb;
2629
2630   /* If we have an ABORT statement, create a test following the start
2631      call to perform the abort.  */
2632   if (gimple_transaction_label (region->transaction_stmt))
2633     {
2634       edge e;
2635       basic_block test_bb;
2636
2637       test_bb = create_empty_bb (slice_bb);
2638       if (VEC_empty (tree, tm_log_save_addresses))
2639         region->entry_block = test_bb;
2640       gsi = gsi_last_bb (test_bb);
2641
2642       t1 = make_rename_temp (TREE_TYPE (status), NULL);
2643       t2 = build_int_cst (TREE_TYPE (status), A_ABORTTRANSACTION);
2644       g = gimple_build_assign_with_ops (BIT_AND_EXPR, t1, status, t2);
2645       gsi_insert_after (&gsi, g, GSI_CONTINUE_LINKING);
2646
2647       t2 = build_int_cst (TREE_TYPE (status), 0);
2648       g = gimple_build_cond (NE_EXPR, t1, t2, NULL, NULL);
2649       gsi_insert_after (&gsi, g, GSI_CONTINUE_LINKING);
2650
2651       e = FALLTHRU_EDGE (slice_bb);
2652       redirect_edge_pred (e, test_bb);
2653       e->flags = EDGE_FALSE_VALUE;
2654       e->probability = PROB_ALWAYS - PROB_VERY_UNLIKELY;
2655
2656       e = BRANCH_EDGE (atomic_bb);
2657       redirect_edge_pred (e, test_bb);
2658       e->flags = EDGE_TRUE_VALUE;
2659       e->probability = PROB_VERY_UNLIKELY;
2660
2661       e = make_edge (slice_bb, test_bb, EDGE_FALLTHRU);
2662     }
2663
2664   /* If we've no abort, but we do have PHIs at the beginning of the atomic
2665      region, that means we've a loop at the beginning of the atomic region
2666      that shares the first block.  This can cause problems with the abnormal
2667      edges we're about to add for the transaction restart.  Solve this by
2668      adding a new empty block to receive the abnormal edges.  */
2669   else if (phi_nodes (region->entry_block))
2670     {
2671       edge e;
2672       basic_block empty_bb;
2673
2674       region->entry_block = empty_bb = create_empty_bb (atomic_bb);
2675
2676       e = FALLTHRU_EDGE (atomic_bb);
2677       redirect_edge_pred (e, empty_bb);
2678
2679       e = make_edge (atomic_bb, empty_bb, EDGE_FALLTHRU);
2680     }
2681
2682   /* The GIMPLE_TRANSACTION statement no longer exists.  */
2683   region->transaction_stmt = NULL;
2684 }
2685
2686 static void expand_regions (struct tm_region *);
2687
2688 /* Helper function for expand_regions.  Expand REGION and recurse to
2689    the inner region.  */
2690
2691 static void
2692 expand_regions_1 (struct tm_region *region)
2693 {
2694   if (region->exit_blocks)
2695     {
2696       unsigned int i;
2697       basic_block bb;
2698       VEC (basic_block, heap) *queue;
2699
2700       /* Collect the set of blocks in this region.  Do this before
2701          splitting edges, so that we don't have to play with the
2702          dominator tree in the middle.  */
2703       queue = get_tm_region_blocks (region->entry_block,
2704                                     region->exit_blocks,
2705                                     region->irr_blocks,
2706                                     NULL,
2707                                     /*stop_at_irr_p=*/false);
2708       expand_transaction (region);
2709       for (i = 0; VEC_iterate (basic_block, queue, i, bb); ++i)
2710         expand_block_edges (region, bb);
2711       VEC_free (basic_block, heap, queue);
2712     }
2713   if (region->inner)
2714     expand_regions (region->inner);
2715 }
2716
2717 /* Expand regions starting at REGION.  */
2718
2719 static void
2720 expand_regions (struct tm_region *region)
2721 {
2722   while (region)
2723     {
2724       expand_regions_1 (region);
2725       region = region->next;
2726     }
2727 }
2728
2729 /* Entry point to the final expansion of transactional nodes. */
2730
2731 static unsigned int
2732 execute_tm_edges (void)
2733 {
2734   expand_regions (all_tm_regions);
2735   tm_log_delete ();
2736
2737   /* We've got to release the dominance info now, to indicate that it
2738      must be rebuilt completely.  Otherwise we'll crash trying to update
2739      the SSA web in the TODO section following this pass.  */
2740   free_dominance_info (CDI_DOMINATORS);
2741   bitmap_obstack_release (&tm_obstack);
2742   all_tm_regions = NULL;
2743
2744   return 0;
2745 }
2746
2747 struct gimple_opt_pass pass_tm_edges =
2748 {
2749  {
2750   GIMPLE_PASS,
2751   "tmedge",                             /* name */
2752   NULL,                                 /* gate */
2753   execute_tm_edges,                     /* execute */
2754   NULL,                                 /* sub */
2755   NULL,                                 /* next */
2756   0,                                    /* static_pass_number */
2757   TV_TRANS_MEM,                         /* tv_id */
2758   PROP_ssa | PROP_cfg,                  /* properties_required */
2759   0,                                    /* properties_provided */
2760   0,                                    /* properties_destroyed */
2761   0,                                    /* todo_flags_start */
2762   TODO_update_ssa
2763   | TODO_verify_ssa
2764   | TODO_dump_func,                     /* todo_flags_finish */
2765  }
2766 };
2767 \f
2768 /* A unique TM memory operation.  */
2769 typedef struct tm_memop
2770 {
2771   /* Unique ID that all memory operations to the same location have.  */
2772   unsigned int value_id;
2773   /* Address of load/store.  */
2774   tree addr;
2775 } *tm_memop_t;
2776
2777 /* Sets for solving data flow equations in the memory optimization pass.  */
2778 struct tm_memopt_bitmaps
2779 {
2780   /* Stores available to this BB upon entry.  Basically, stores that
2781      dominate this BB.  */
2782   bitmap store_avail_in;
2783   /* Stores available at the end of this BB.  */
2784   bitmap store_avail_out;
2785   bitmap store_antic_in;
2786   bitmap store_antic_out;
2787   /* Reads available to this BB upon entry.  Basically, reads that
2788      dominate this BB.  */
2789   bitmap read_avail_in;
2790   /* Reads available at the end of this BB.  */
2791   bitmap read_avail_out;
2792   /* Reads performed in this BB.  */
2793   bitmap read_local;
2794   /* Writes performed in this BB.  */
2795   bitmap store_local;
2796
2797   /* Temporary storage for pass.  */
2798   /* Is the current BB in the worklist?  */
2799   bool avail_in_worklist_p;
2800   /* Have we visited this BB?  */
2801   bool visited_p;
2802 };
2803
2804 static bitmap_obstack tm_memopt_obstack;
2805
2806 /* Unique counter for TM loads and stores. Loads and stores of the
2807    same address get the same ID.  */
2808 static unsigned int tm_memopt_value_id;
2809 static htab_t tm_memopt_value_numbers;
2810
2811 #define STORE_AVAIL_IN(BB) \
2812   ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_avail_in
2813 #define STORE_AVAIL_OUT(BB) \
2814   ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_avail_out
2815 #define STORE_ANTIC_IN(BB) \
2816   ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_antic_in
2817 #define STORE_ANTIC_OUT(BB) \
2818   ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_antic_out
2819 #define READ_AVAIL_IN(BB) \
2820   ((struct tm_memopt_bitmaps *) ((BB)->aux))->read_avail_in
2821 #define READ_AVAIL_OUT(BB) \
2822   ((struct tm_memopt_bitmaps *) ((BB)->aux))->read_avail_out
2823 #define READ_LOCAL(BB) \
2824   ((struct tm_memopt_bitmaps *) ((BB)->aux))->read_local
2825 #define STORE_LOCAL(BB) \
2826   ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_local
2827 #define AVAIL_IN_WORKLIST_P(BB) \
2828   ((struct tm_memopt_bitmaps *) ((BB)->aux))->avail_in_worklist_p
2829 #define BB_VISITED_P(BB) \
2830   ((struct tm_memopt_bitmaps *) ((BB)->aux))->visited_p
2831
2832 /* Htab support.  Return a hash value for a `tm_memop'.  */
2833 static hashval_t
2834 tm_memop_hash (const void *p)
2835 {
2836   const struct tm_memop *mem = (const struct tm_memop *) p;
2837   tree addr = mem->addr;
2838   /* We drill down to the SSA_NAME/DECL for the hash, but equality is
2839      actually done with operand_equal_p (see tm_memop_eq).  */
2840   if (TREE_CODE (addr) == ADDR_EXPR)
2841     addr = TREE_OPERAND (addr, 0);
2842   return iterative_hash_expr (addr, 0);
2843 }
2844
2845 /* Htab support.  Return true if two tm_memop's are the same.  */
2846 static int
2847 tm_memop_eq (const void *p1, const void *p2)
2848 {
2849   const struct tm_memop *mem1 = (const struct tm_memop *) p1;
2850   const struct tm_memop *mem2 = (const struct tm_memop *) p2;
2851
2852   return operand_equal_p (mem1->addr, mem2->addr, 0);
2853 }
2854
2855 /* Given a TM load/store in STMT, return the value number for the address
2856    it accesses.  */
2857
2858 static unsigned int
2859 tm_memopt_value_number (gimple stmt, enum insert_option op)
2860 {
2861   struct tm_memop tmpmem, *mem;
2862   void **slot;
2863
2864   gcc_assert (is_tm_load (stmt) || is_tm_store (stmt));
2865   tmpmem.addr = gimple_call_arg (stmt, 0);
2866   slot = htab_find_slot (tm_memopt_value_numbers, &tmpmem, op);
2867   if (*slot)
2868     mem = (struct tm_memop *) *slot;
2869   else if (op == INSERT)
2870     {
2871       mem = XNEW (struct tm_memop);
2872       *slot = mem;
2873       mem->value_id = tm_memopt_value_id++;
2874       mem->addr = tmpmem.addr;
2875     }
2876   else
2877     gcc_unreachable ();
2878   return mem->value_id;
2879 }
2880
2881 /* Accumulate TM memory operations in BB into STORE_LOCAL and READ_LOCAL.  */
2882
2883 static void
2884 tm_memopt_accumulate_memops (basic_block bb)
2885 {
2886   gimple_stmt_iterator gsi;
2887
2888   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2889     {
2890       gimple stmt = gsi_stmt (gsi);
2891       bitmap bits;
2892       unsigned int loc;
2893
2894       if (is_tm_store (stmt))
2895         bits = STORE_LOCAL (bb);
2896       else if (is_tm_load (stmt))
2897         bits = READ_LOCAL (bb);
2898       else
2899         continue;
2900
2901       loc = tm_memopt_value_number (stmt, INSERT);
2902       bitmap_set_bit (bits, loc);
2903       if (dump_file)
2904         {
2905           fprintf (dump_file, "TM memopt (%s): value num=%d, BB=%d, addr=",
2906                    is_tm_load (stmt) ? "LOAD" : "STORE", loc,
2907                    gimple_bb (stmt)->index);
2908           print_generic_expr (dump_file, gimple_call_arg (stmt, 0), 0);
2909           fprintf (dump_file, "\n");
2910         }
2911     }
2912 }
2913
2914 /* Prettily dump one of the memopt sets.  BITS is the bitmap to dump.  */
2915
2916 static void
2917 dump_tm_memopt_set (const char *set_name, bitmap bits)
2918 {
2919   unsigned i;
2920   bitmap_iterator bi;
2921   const char *comma = "";
2922
2923   fprintf (dump_file, "TM memopt: %s: [", set_name);
2924   EXECUTE_IF_SET_IN_BITMAP (bits, 0, i, bi)
2925     {
2926       htab_iterator hi;
2927       struct tm_memop *mem;
2928
2929       /* Yeah, yeah, yeah.  Whatever.  This is just for debugging.  */
2930       FOR_EACH_HTAB_ELEMENT (tm_memopt_value_numbers, mem, tm_memop_t, hi)
2931         if (mem->value_id == i)
2932           break;
2933       gcc_assert (mem->value_id == i);
2934       fprintf (dump_file, "%s", comma);
2935       comma = ", ";
2936       print_generic_expr (dump_file, mem->addr, 0);
2937     }
2938   fprintf (dump_file, "]\n");
2939 }
2940
2941 /* Prettily dump all of the memopt sets in BLOCKS.  */
2942
2943 static void
2944 dump_tm_memopt_sets (VEC (basic_block, heap) *blocks)
2945 {
2946   size_t i;
2947   basic_block bb;
2948
2949   for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
2950     {
2951       fprintf (dump_file, "------------BB %d---------\n", bb->index);
2952       dump_tm_memopt_set ("STORE_LOCAL", STORE_LOCAL (bb));
2953       dump_tm_memopt_set ("READ_LOCAL", READ_LOCAL (bb));
2954       dump_tm_memopt_set ("STORE_AVAIL_IN", STORE_AVAIL_IN (bb));
2955       dump_tm_memopt_set ("STORE_AVAIL_OUT", STORE_AVAIL_OUT (bb));
2956       dump_tm_memopt_set ("READ_AVAIL_IN", READ_AVAIL_IN (bb));
2957       dump_tm_memopt_set ("READ_AVAIL_OUT", READ_AVAIL_OUT (bb));
2958     }
2959 }
2960
2961 /* Compute {STORE,READ}_AVAIL_IN for the basic block BB.  */
2962
2963 static void
2964 tm_memopt_compute_avin (basic_block bb)
2965 {
2966   edge e;
2967   unsigned ix;
2968
2969   /* Seed with the AVOUT of any predecessor.  */
2970   for (ix = 0; ix < EDGE_COUNT (bb->preds); ix++)
2971     {
2972       e = EDGE_PRED (bb, ix);
2973       /* Make sure we have already visited this BB, and is thus
2974          initialized.
2975
2976           If e->src->aux is NULL, this predecessor is actually on an
2977           enclosing transaction.  We only care about the current
2978           transaction, so ignore it.  */
2979       if (e->src->aux && BB_VISITED_P (e->src))
2980         {
2981           bitmap_copy (STORE_AVAIL_IN (bb), STORE_AVAIL_OUT (e->src));
2982           bitmap_copy (READ_AVAIL_IN (bb), READ_AVAIL_OUT (e->src));
2983           break;
2984         }
2985     }
2986
2987   for (; ix < EDGE_COUNT (bb->preds); ix++)
2988     {
2989       e = EDGE_PRED (bb, ix);
2990       if (e->src->aux && BB_VISITED_P (e->src))
2991         {
2992           bitmap_and_into (STORE_AVAIL_IN (bb), STORE_AVAIL_OUT (e->src));
2993           bitmap_and_into (READ_AVAIL_IN (bb), READ_AVAIL_OUT (e->src));
2994         }
2995     }
2996
2997   BB_VISITED_P (bb) = true;
2998 }
2999
3000 /* Compute the STORE_ANTIC_IN for the basic block BB.  */
3001
3002 static void
3003 tm_memopt_compute_antin (basic_block bb)
3004 {
3005   edge e;
3006   unsigned ix;
3007
3008   /* Seed with the ANTIC_OUT of any successor.  */
3009   for (ix = 0; ix < EDGE_COUNT (bb->succs); ix++)
3010     {
3011       e = EDGE_SUCC (bb, ix);
3012       /* Make sure we have already visited this BB, and is thus
3013          initialized.  */
3014       if (BB_VISITED_P (e->dest))
3015         {
3016           bitmap_copy (STORE_ANTIC_IN (bb), STORE_ANTIC_OUT (e->dest));
3017           break;
3018         }
3019     }
3020
3021   for (; ix < EDGE_COUNT (bb->succs); ix++)
3022     {
3023       e = EDGE_SUCC (bb, ix);
3024       if (BB_VISITED_P  (e->dest))
3025         bitmap_and_into (STORE_ANTIC_IN (bb), STORE_ANTIC_OUT (e->dest));
3026     }
3027
3028   BB_VISITED_P (bb) = true;
3029 }
3030
3031 /* Compute the AVAIL sets for every basic block in BLOCKS.
3032
3033    We compute {STORE,READ}_AVAIL_{OUT,IN} as follows:
3034
3035      AVAIL_OUT[bb] = union (AVAIL_IN[bb], LOCAL[bb])
3036      AVAIL_IN[bb]  = intersect (AVAIL_OUT[predecessors])
3037
3038    This is basically what we do in lcm's compute_available(), but here
3039    we calculate two sets of sets (one for STOREs and one for READs),
3040    and we work on a region instead of the entire CFG.
3041
3042    REGION is the TM region.
3043    BLOCKS are the basic blocks in the region.  */
3044
3045 static void
3046 tm_memopt_compute_available (struct tm_region *region,
3047                              VEC (basic_block, heap) *blocks)
3048 {
3049   edge e;
3050   basic_block *worklist, *qin, *qout, *qend, bb;
3051   unsigned int qlen, i;
3052   edge_iterator ei;
3053   bool changed;
3054
3055   /* Allocate a worklist array/queue.  Entries are only added to the
3056      list if they were not already on the list.  So the size is
3057      bounded by the number of basic blocks in the region.  */
3058   qlen = VEC_length (basic_block, blocks) - 1;
3059   qin = qout = worklist =
3060     XNEWVEC (basic_block, qlen);
3061
3062   /* Put every block in the region on the worklist.  */
3063   for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
3064     {
3065       /* Seed AVAIL_OUT with the LOCAL set.  */
3066       bitmap_ior_into (STORE_AVAIL_OUT (bb), STORE_LOCAL (bb));
3067       bitmap_ior_into (READ_AVAIL_OUT (bb), READ_LOCAL (bb));
3068
3069       AVAIL_IN_WORKLIST_P (bb) = true;
3070       /* No need to insert the entry block, since it has an AVIN of
3071          null, and an AVOUT that has already been seeded in.  */
3072       if (bb != region->entry_block)
3073         *qin++ = bb;
3074     }
3075
3076   /* The entry block has been initialized with the local sets.  */
3077   BB_VISITED_P (region->entry_block) = true;
3078
3079   qin = worklist;
3080   qend = &worklist[qlen];
3081
3082   /* Iterate until the worklist is empty.  */
3083   while (qlen)
3084     {
3085       /* Take the first entry off the worklist.  */
3086       bb = *qout++;
3087       qlen--;
3088
3089       if (qout >= qend)
3090         qout = worklist;
3091
3092       /* This block can be added to the worklist again if necessary.  */
3093       AVAIL_IN_WORKLIST_P (bb) = false;
3094       tm_memopt_compute_avin (bb);
3095
3096       /* Note: We do not add the LOCAL sets here because we already
3097          seeded the AVAIL_OUT sets with them.  */
3098       changed  = bitmap_ior_into (STORE_AVAIL_OUT (bb), STORE_AVAIL_IN (bb));
3099       changed |= bitmap_ior_into (READ_AVAIL_OUT (bb), READ_AVAIL_IN (bb));
3100       if (changed
3101           && (region->exit_blocks == NULL
3102               || !bitmap_bit_p (region->exit_blocks, bb->index)))
3103         /* If the out state of this block changed, then we need to add
3104            its successors to the worklist if they are not already in.  */
3105         FOR_EACH_EDGE (e, ei, bb->succs)
3106           if (!AVAIL_IN_WORKLIST_P (e->dest) && e->dest != EXIT_BLOCK_PTR)
3107             {
3108               *qin++ = e->dest;
3109               AVAIL_IN_WORKLIST_P (e->dest) = true;
3110               qlen++;
3111
3112               if (qin >= qend)
3113                 qin = worklist;
3114             }
3115     }
3116
3117   free (worklist);
3118
3119   if (dump_file)
3120     dump_tm_memopt_sets (blocks);
3121 }
3122
3123 /* Compute ANTIC sets for every basic block in BLOCKS.
3124
3125    We compute STORE_ANTIC_OUT as follows:
3126
3127         STORE_ANTIC_OUT[bb] = union(STORE_ANTIC_IN[bb], STORE_LOCAL[bb])
3128         STORE_ANTIC_IN[bb]  = intersect(STORE_ANTIC_OUT[successors])
3129
3130    REGION is the TM region.
3131    BLOCKS are the basic blocks in the region.  */
3132
3133 static void
3134 tm_memopt_compute_antic (struct tm_region *region,
3135                          VEC (basic_block, heap) *blocks)
3136 {
3137   edge e;
3138   basic_block *worklist, *qin, *qout, *qend, bb;
3139   unsigned int qlen;
3140   int i;
3141   edge_iterator ei;
3142
3143   /* Allocate a worklist array/queue.  Entries are only added to the
3144      list if they were not already on the list.  So the size is
3145      bounded by the number of basic blocks in the region.  */
3146   qin = qout = worklist =
3147     XNEWVEC (basic_block, VEC_length (basic_block, blocks));
3148
3149   for (qlen = 0, i = VEC_length (basic_block, blocks) - 1; i >= 0; --i)
3150     {
3151       bb = VEC_index (basic_block, blocks, i);
3152
3153       /* Seed ANTIC_OUT with the LOCAL set.  */
3154       bitmap_ior_into (STORE_ANTIC_OUT (bb), STORE_LOCAL (bb));
3155
3156       /* Put every block in the region on the worklist.  */
3157       AVAIL_IN_WORKLIST_P (bb) = true;
3158       /* No need to insert exit blocks, since their ANTIC_IN is NULL,
3159          and their ANTIC_OUT has already been seeded in.  */
3160       if (region->exit_blocks
3161           && !bitmap_bit_p (region->exit_blocks, bb->index))
3162         {
3163           qlen++;
3164           *qin++ = bb;
3165         }
3166     }
3167
3168   /* The exit blocks have been initialized with the local sets.  */
3169   if (region->exit_blocks)
3170     {
3171       unsigned int i;
3172       bitmap_iterator bi;
3173       EXECUTE_IF_SET_IN_BITMAP (region->exit_blocks, 0, i, bi)
3174         BB_VISITED_P (BASIC_BLOCK (i)) = true;
3175     }
3176
3177   qin = worklist;
3178   qend = &worklist[qlen];
3179
3180   /* Iterate until the worklist is empty.  */
3181   while (qlen)
3182     {
3183       /* Take the first entry off the worklist.  */
3184       bb = *qout++;
3185       qlen--;
3186
3187       if (qout >= qend)
3188         qout = worklist;
3189
3190       /* This block can be added to the worklist again if necessary.  */
3191       AVAIL_IN_WORKLIST_P (bb) = false;
3192       tm_memopt_compute_antin (bb);
3193
3194       /* Note: We do not add the LOCAL sets here because we already
3195          seeded the ANTIC_OUT sets with them.  */
3196       if (bitmap_ior_into (STORE_ANTIC_OUT (bb), STORE_ANTIC_IN (bb))
3197           && bb != region->entry_block)
3198         /* If the out state of this block changed, then we need to add
3199            its predecessors to the worklist if they are not already in.  */
3200         FOR_EACH_EDGE (e, ei, bb->preds)
3201           if (!AVAIL_IN_WORKLIST_P (e->src))
3202             {
3203               *qin++ = e->src;
3204               AVAIL_IN_WORKLIST_P (e->src) = true;
3205               qlen++;
3206
3207               if (qin >= qend)
3208                 qin = worklist;
3209             }
3210     }
3211
3212   free (worklist);
3213
3214   if (dump_file)
3215     dump_tm_memopt_sets (blocks);
3216 }
3217
3218 /* Offsets of load variants from TM_LOAD.  For example,
3219    BUILT_IN_TM_LOAD_RAR* is an offset of 1 from BUILT_IN_TM_LOAD*.
3220    See gtm-builtins.def.  */
3221 #define TRANSFORM_RAR 1
3222 #define TRANSFORM_RAW 2
3223 #define TRANSFORM_RFW 3
3224 /* Offsets of store variants from TM_STORE.  */
3225 #define TRANSFORM_WAR 1
3226 #define TRANSFORM_WAW 2
3227
3228 /* Inform about a load/store optimization.  */
3229
3230 static void
3231 dump_tm_memopt_transform (gimple stmt)
3232 {
3233   if (dump_file)
3234     {
3235       fprintf (dump_file, "TM memopt: transforming: ");
3236       print_gimple_stmt (dump_file, stmt, 0, 0);
3237       fprintf (dump_file, "\n");
3238     }
3239 }
3240
3241 /* Perform a read/write optimization.  Replaces the TM builtin in STMT
3242    by a builtin that is OFFSET entries down in the builtins table in
3243    gtm-builtins.def.  */
3244
3245 static void
3246 tm_memopt_transform_stmt (unsigned int offset,
3247                           gimple stmt,
3248                           gimple_stmt_iterator *gsi)
3249 {
3250   tree fn = gimple_call_fn (stmt);
3251   gcc_assert (TREE_CODE (fn) == ADDR_EXPR);
3252   TREE_OPERAND (fn, 0)
3253     = builtin_decl_explicit ((enum built_in_function)
3254                              (DECL_FUNCTION_CODE (TREE_OPERAND (fn, 0))
3255                               + offset));
3256   gimple_call_set_fn (stmt, fn);
3257   gsi_replace (gsi, stmt, true);
3258   dump_tm_memopt_transform (stmt);
3259 }
3260
3261 /* Perform the actual TM memory optimization transformations in the
3262    basic blocks in BLOCKS.  */
3263
3264 static void
3265 tm_memopt_transform_blocks (VEC (basic_block, heap) *blocks)
3266 {
3267   size_t i;
3268   basic_block bb;
3269   gimple_stmt_iterator gsi;
3270
3271   for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
3272     {
3273       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3274         {
3275           gimple stmt = gsi_stmt (gsi);
3276           bitmap read_avail = READ_AVAIL_IN (bb);
3277           bitmap store_avail = STORE_AVAIL_IN (bb);
3278           bitmap store_antic = STORE_ANTIC_OUT (bb);
3279           unsigned int loc;
3280
3281           if (is_tm_simple_load (stmt))
3282             {
3283               loc = tm_memopt_value_number (stmt, NO_INSERT);
3284               if (store_avail && bitmap_bit_p (store_avail, loc))
3285                 tm_memopt_transform_stmt (TRANSFORM_RAW, stmt, &gsi);
3286               else if (store_antic && bitmap_bit_p (store_antic, loc))
3287                 {
3288                   tm_memopt_transform_stmt (TRANSFORM_RFW, stmt, &gsi);
3289                   bitmap_set_bit (store_avail, loc);
3290                 }
3291               else if (read_avail && bitmap_bit_p (read_avail, loc))
3292                 tm_memopt_transform_stmt (TRANSFORM_RAR, stmt, &gsi);
3293               else
3294                 bitmap_set_bit (read_avail, loc);
3295             }
3296           else if (is_tm_simple_store (stmt))
3297             {
3298               loc = tm_memopt_value_number (stmt, NO_INSERT);
3299               if (store_avail && bitmap_bit_p (store_avail, loc))
3300                 tm_memopt_transform_stmt (TRANSFORM_WAW, stmt, &gsi);
3301               else
3302                 {
3303                   if (read_avail && bitmap_bit_p (read_avail, loc))
3304                     tm_memopt_transform_stmt (TRANSFORM_WAR, stmt, &gsi);
3305                   bitmap_set_bit (store_avail, loc);
3306                 }
3307             }
3308         }
3309     }
3310 }
3311
3312 /* Return a new set of bitmaps for a BB.  */
3313
3314 static struct tm_memopt_bitmaps *
3315 tm_memopt_init_sets (void)
3316 {
3317   struct tm_memopt_bitmaps *b
3318     = XOBNEW (&tm_memopt_obstack.obstack, struct tm_memopt_bitmaps);
3319   b->store_avail_in = BITMAP_ALLOC (&tm_memopt_obstack);
3320   b->store_avail_out = BITMAP_ALLOC (&tm_memopt_obstack);
3321   b->store_antic_in = BITMAP_ALLOC (&tm_memopt_obstack);
3322   b->store_antic_out = BITMAP_ALLOC (&tm_memopt_obstack);
3323   b->store_avail_out = BITMAP_ALLOC (&tm_memopt_obstack);
3324   b->read_avail_in = BITMAP_ALLOC (&tm_memopt_obstack);
3325   b->read_avail_out = BITMAP_ALLOC (&tm_memopt_obstack);
3326   b->read_local = BITMAP_ALLOC (&tm_memopt_obstack);
3327   b->store_local = BITMAP_ALLOC (&tm_memopt_obstack);
3328   return b;
3329 }
3330
3331 /* Free sets computed for each BB.  */
3332
3333 static void
3334 tm_memopt_free_sets (VEC (basic_block, heap) *blocks)
3335 {
3336   size_t i;
3337   basic_block bb;
3338
3339   for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
3340     bb->aux = NULL;
3341 }
3342
3343 /* Clear the visited bit for every basic block in BLOCKS.  */
3344
3345 static void
3346 tm_memopt_clear_visited (VEC (basic_block, heap) *blocks)
3347 {
3348   size_t i;
3349   basic_block bb;
3350
3351   for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
3352     BB_VISITED_P (bb) = false;
3353 }
3354
3355 /* Replace TM load/stores with hints for the runtime.  We handle
3356    things like read-after-write, write-after-read, read-after-read,
3357    read-for-write, etc.  */
3358
3359 static unsigned int
3360 execute_tm_memopt (void)
3361 {
3362   struct tm_region *region;
3363   VEC (basic_block, heap) *bbs;
3364
3365   tm_memopt_value_id = 0;
3366   tm_memopt_value_numbers = htab_create (10, tm_memop_hash, tm_memop_eq, free);
3367
3368   for (region = all_tm_regions; region; region = region->next)
3369     {
3370       /* All the TM stores/loads in the current region.  */
3371       size_t i;
3372       basic_block bb;
3373
3374       bitmap_obstack_initialize (&tm_memopt_obstack);
3375
3376       /* Save all BBs for the current region.  */
3377       bbs = get_tm_region_blocks (region->entry_block,
3378                                   region->exit_blocks,
3379                                   region->irr_blocks,
3380                                   NULL,
3381                                   false);
3382
3383       /* Collect all the memory operations.  */
3384       for (i = 0; VEC_iterate (basic_block, bbs, i, bb); ++i)
3385         {
3386           bb->aux = tm_memopt_init_sets ();
3387           tm_memopt_accumulate_memops (bb);
3388         }
3389
3390       /* Solve data flow equations and transform each block accordingly.  */
3391       tm_memopt_clear_visited (bbs);
3392       tm_memopt_compute_available (region, bbs);
3393       tm_memopt_clear_visited (bbs);
3394       tm_memopt_compute_antic (region, bbs);
3395       tm_memopt_transform_blocks (bbs);
3396
3397       tm_memopt_free_sets (bbs);
3398       VEC_free (basic_block, heap, bbs);
3399       bitmap_obstack_release (&tm_memopt_obstack);
3400       htab_empty (tm_memopt_value_numbers);
3401     }
3402
3403   htab_delete (tm_memopt_value_numbers);
3404   return 0;
3405 }
3406
3407 static bool
3408 gate_tm_memopt (void)
3409 {
3410   return flag_tm && optimize > 0;
3411 }
3412
3413 struct gimple_opt_pass pass_tm_memopt =
3414 {
3415  {
3416   GIMPLE_PASS,
3417   "tmmemopt",                           /* name */
3418   gate_tm_memopt,                       /* gate */
3419   execute_tm_memopt,                    /* execute */
3420   NULL,                                 /* sub */
3421   NULL,                                 /* next */
3422   0,                                    /* static_pass_number */
3423   TV_TRANS_MEM,                         /* tv_id */
3424   PROP_ssa | PROP_cfg,                  /* properties_required */
3425   0,                                    /* properties_provided */
3426   0,                                    /* properties_destroyed */
3427   0,                                    /* todo_flags_start */
3428   TODO_dump_func,                       /* todo_flags_finish */
3429  }
3430 };
3431
3432 \f
3433 /* Interprocedual analysis for the creation of transactional clones.
3434    The aim of this pass is to find which functions are referenced in
3435    a non-irrevocable transaction context, and for those over which
3436    we have control (or user directive), create a version of the
3437    function which uses only the transactional interface to reference
3438    protected memories.  This analysis proceeds in several steps:
3439
3440      (1) Collect the set of all possible transactional clones:
3441
3442         (a) For all local public functions marked tm_callable, push
3443             it onto the tm_callee queue.
3444
3445         (b) For all local functions, scan for calls in transaction blocks.
3446             Push the caller and callee onto the tm_caller and tm_callee
3447             queues.  Count the number of callers for each callee.
3448
3449         (c) For each local function on the callee list, assume we will
3450             create a transactional clone.  Push *all* calls onto the
3451             callee queues; count the number of clone callers separately
3452             to the number of original callers.
3453
3454      (2) Propagate irrevocable status up the dominator tree:
3455
3456         (a) Any external function on the callee list that is not marked
3457             tm_callable is irrevocable.  Push all callers of such onto
3458             a worklist.
3459
3460         (b) For each function on the worklist, mark each block that
3461             contains an irrevocable call.  Use the AND operator to
3462             propagate that mark up the dominator tree.
3463
3464         (c) If we reach the entry block for a possible transactional
3465             clone, then the transactional clone is irrevocable, and
3466             we should not create the clone after all.  Push all
3467             callers onto the worklist.
3468
3469         (d) Place tm_irrevocable calls at the beginning of the relevant
3470             blocks.  Special case here is the entry block for the entire
3471             transaction region; there we mark it GTMA_DOES_GO_IRREVOCABLE for
3472             the library to begin the region in serial mode.  Decrement
3473             the call count for all callees in the irrevocable region.
3474
3475      (3) Create the transactional clones:
3476
3477         Any tm_callee that still has a non-zero call count is cloned.
3478 */
3479
3480 /* This structure is stored in the AUX field of each cgraph_node.  */
3481 struct tm_ipa_cg_data
3482 {
3483   /* The clone of the function that got created.  */
3484   struct cgraph_node *clone;
3485
3486   /* The tm regions in the normal function.  */
3487   struct tm_region *all_tm_regions;
3488
3489   /* The blocks of the normal/clone functions that contain irrevocable
3490      calls, or blocks that are post-dominated by irrevocable calls.  */
3491   bitmap irrevocable_blocks_normal;
3492   bitmap irrevocable_blocks_clone;
3493
3494   /* The blocks of the normal function that are involved in transactions.  */
3495   bitmap transaction_blocks_normal;
3496
3497   /* The number of callers to the transactional clone of this function
3498      from normal and transactional clones respectively.  */
3499   unsigned tm_callers_normal;
3500   unsigned tm_callers_clone;
3501
3502   /* True if all calls to this function's transactional clone
3503      are irrevocable.  Also automatically true if the function
3504      has no transactional clone.  */
3505   bool is_irrevocable;
3506
3507   /* Flags indicating the presence of this function in various queues.  */
3508   bool in_callee_queue;
3509   bool in_worklist;
3510
3511   /* Flags indicating the kind of scan desired while in the worklist.  */
3512   bool want_irr_scan_normal;
3513 };
3514
3515 typedef struct cgraph_node *cgraph_node_p;
3516
3517 DEF_VEC_P (cgraph_node_p);
3518 DEF_VEC_ALLOC_P (cgraph_node_p, heap);
3519
3520 typedef VEC (cgraph_node_p, heap) *cgraph_node_queue;
3521
3522 /* Return the ipa data associated with NODE, allocating zeroed memory
3523    if necessary.  TRAVERSE_ALIASES is true if we must traverse aliases
3524    and set *NODE accordingly.  */
3525
3526 static struct tm_ipa_cg_data *
3527 get_cg_data (struct cgraph_node **node, bool traverse_aliases)
3528 {
3529   struct tm_ipa_cg_data *d;
3530
3531   if (traverse_aliases && (*node)->alias)
3532     *node = cgraph_get_node ((*node)->thunk.alias);
3533
3534   d = (struct tm_ipa_cg_data *) (*node)->aux;
3535
3536   if (d == NULL)
3537     {
3538       d = (struct tm_ipa_cg_data *)
3539         obstack_alloc (&tm_obstack.obstack, sizeof (*d));
3540       (*node)->aux = (void *) d;
3541       memset (d, 0, sizeof (*d));
3542     }
3543
3544   return d;
3545 }
3546
3547 /* Add NODE to the end of QUEUE, unless IN_QUEUE_P indicates that
3548    it is already present.  */
3549
3550 static void
3551 maybe_push_queue (struct cgraph_node *node,
3552                   cgraph_node_queue *queue_p, bool *in_queue_p)
3553 {
3554   if (!*in_queue_p)
3555     {
3556       *in_queue_p = true;
3557       VEC_safe_push (cgraph_node_p, heap, *queue_p, node);
3558     }
3559 }
3560
3561 /* A subroutine of ipa_tm_scan_calls_transaction and ipa_tm_scan_calls_clone.
3562    Queue all callees within block BB.  */
3563
3564 static void
3565 ipa_tm_scan_calls_block (cgraph_node_queue *callees_p,
3566                          basic_block bb, bool for_clone)
3567 {
3568   gimple_stmt_iterator gsi;
3569
3570   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3571     {
3572       gimple stmt = gsi_stmt (gsi);
3573       if (is_gimple_call (stmt) && !is_tm_pure_call (stmt))
3574         {
3575           tree fndecl = gimple_call_fndecl (stmt);
3576           if (fndecl)
3577             {
3578               struct tm_ipa_cg_data *d;
3579               unsigned *pcallers;
3580               struct cgraph_node *node;
3581
3582               if (is_tm_ending_fndecl (fndecl))
3583                 continue;
3584               if (find_tm_replacement_function (fndecl))
3585                 continue;
3586
3587               node = cgraph_get_node (fndecl);
3588               gcc_assert (node != NULL);
3589               d = get_cg_data (&node, true);
3590
3591               pcallers = (for_clone ? &d->tm_callers_clone
3592                           : &d->tm_callers_normal);
3593               *pcallers += 1;
3594
3595               maybe_push_queue (node, callees_p, &d->in_callee_queue);
3596             }
3597         }
3598     }
3599 }
3600
3601 /* Scan all calls in NODE that are within a transaction region,
3602    and push the resulting nodes into the callee queue.  */
3603
3604 static void
3605 ipa_tm_scan_calls_transaction (struct tm_ipa_cg_data *d,
3606                                cgraph_node_queue *callees_p)
3607 {
3608   struct tm_region *r;
3609
3610   d->transaction_blocks_normal = BITMAP_ALLOC (&tm_obstack);
3611   d->all_tm_regions = all_tm_regions;
3612
3613   for (r = all_tm_regions; r; r = r->next)
3614     {
3615       VEC (basic_block, heap) *bbs;
3616       basic_block bb;
3617       unsigned i;
3618
3619       bbs = get_tm_region_blocks (r->entry_block, r->exit_blocks, NULL,
3620                                   d->transaction_blocks_normal, false);
3621
3622       FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
3623         ipa_tm_scan_calls_block (callees_p, bb, false);
3624
3625       VEC_free (basic_block, heap, bbs);
3626     }
3627 }
3628
3629 /* Scan all calls in NODE as if this is the transactional clone,
3630    and push the destinations into the callee queue.  */
3631
3632 static void
3633 ipa_tm_scan_calls_clone (struct cgraph_node *node,
3634                          cgraph_node_queue *callees_p)
3635 {
3636   struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3637   basic_block bb;
3638
3639   FOR_EACH_BB_FN (bb, fn)
3640     ipa_tm_scan_calls_block (callees_p, bb, true);
3641 }
3642
3643 /* The function NODE has been detected to be irrevocable.  Push all
3644    of its callers onto WORKLIST for the purpose of re-scanning them.  */
3645
3646 static void
3647 ipa_tm_note_irrevocable (struct cgraph_node *node,
3648                          cgraph_node_queue *worklist_p)
3649 {
3650   struct tm_ipa_cg_data *d = get_cg_data (&node, true);
3651   struct cgraph_edge *e;
3652
3653   d->is_irrevocable = true;
3654
3655   for (e = node->callers; e ; e = e->next_caller)
3656     {
3657       basic_block bb;
3658       struct cgraph_node *caller;
3659
3660       /* Don't examine recursive calls.  */
3661       if (e->caller == node)
3662         continue;
3663       /* Even if we think we can go irrevocable, believe the user
3664          above all.  */
3665       if (is_tm_safe_or_pure (e->caller->decl))
3666         continue;
3667
3668       caller = e->caller;
3669       d = get_cg_data (&caller, true);
3670
3671       /* Check if the callee is in a transactional region.  If so,
3672          schedule the function for normal re-scan as well.  */
3673       bb = gimple_bb (e->call_stmt);
3674       gcc_assert (bb != NULL);
3675       if (d->transaction_blocks_normal
3676           && bitmap_bit_p (d->transaction_blocks_normal, bb->index))
3677         d->want_irr_scan_normal = true;
3678
3679       maybe_push_queue (caller, worklist_p, &d->in_worklist);
3680     }
3681 }
3682
3683 /* A subroutine of ipa_tm_scan_irr_blocks; return true iff any statement
3684    within the block is irrevocable.  */
3685
3686 static bool
3687 ipa_tm_scan_irr_block (basic_block bb)
3688 {
3689   gimple_stmt_iterator gsi;
3690   tree fn;
3691
3692   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3693     {
3694       gimple stmt = gsi_stmt (gsi);
3695       switch (gimple_code (stmt))
3696         {
3697         case GIMPLE_CALL:
3698           if (is_tm_pure_call (stmt))
3699             break;
3700
3701           fn = gimple_call_fn (stmt);
3702
3703           /* Functions with the attribute are by definition irrevocable.  */
3704           if (is_tm_irrevocable (fn))
3705             return true;
3706
3707           /* For direct function calls, go ahead and check for replacement
3708              functions, or transitive irrevocable functions.  For indirect
3709              functions, we'll ask the runtime.  */
3710           if (TREE_CODE (fn) == ADDR_EXPR)
3711             {
3712               struct tm_ipa_cg_data *d;
3713               struct cgraph_node *node;
3714
3715               fn = TREE_OPERAND (fn, 0);
3716               if (is_tm_ending_fndecl (fn))
3717                 break;
3718               if (find_tm_replacement_function (fn))
3719                 break;
3720
3721               node = cgraph_get_node(fn);
3722               d = get_cg_data (&node, true);
3723
3724               /* Return true if irrevocable, but above all, believe
3725                  the user.  */
3726               if (d->is_irrevocable
3727                   && !is_tm_safe_or_pure (fn))
3728                 return true;
3729             }
3730           break;
3731
3732         case GIMPLE_ASM:
3733           /* ??? The Approved Method of indicating that an inline
3734              assembly statement is not relevant to the transaction
3735              is to wrap it in a __tm_waiver block.  This is not
3736              yet implemented, so we can't check for it.  */
3737           return true;
3738
3739         default:
3740           break;
3741         }
3742     }
3743
3744   return false;
3745 }
3746
3747 /* For each of the blocks seeded witin PQUEUE, walk the CFG looking
3748    for new irrevocable blocks, marking them in NEW_IRR.  Don't bother
3749    scanning past OLD_IRR or EXIT_BLOCKS.  */
3750
3751 static bool
3752 ipa_tm_scan_irr_blocks (VEC (basic_block, heap) **pqueue, bitmap new_irr,
3753                         bitmap old_irr, bitmap exit_blocks)
3754 {
3755   bool any_new_irr = false;
3756   edge e;
3757   edge_iterator ei;
3758   bitmap visited_blocks = BITMAP_ALLOC (NULL);
3759
3760   do
3761     {
3762       basic_block bb = VEC_pop (basic_block, *pqueue);
3763
3764       /* Don't re-scan blocks we know already are irrevocable.  */
3765       if (old_irr && bitmap_bit_p (old_irr, bb->index))
3766         continue;
3767
3768       if (ipa_tm_scan_irr_block (bb))
3769         {
3770           bitmap_set_bit (new_irr, bb->index);
3771           any_new_irr = true;
3772         }
3773       else if (exit_blocks == NULL || !bitmap_bit_p (exit_blocks, bb->index))
3774         {
3775           FOR_EACH_EDGE (e, ei, bb->succs)
3776             if (!bitmap_bit_p (visited_blocks, e->dest->index))
3777               {
3778                 bitmap_set_bit (visited_blocks, e->dest->index);
3779                 VEC_safe_push (basic_block, heap, *pqueue, e->dest);
3780               }
3781         }
3782     }
3783   while (!VEC_empty (basic_block, *pqueue));
3784
3785   BITMAP_FREE (visited_blocks);
3786
3787   return any_new_irr;
3788 }
3789
3790 /* Propagate the irrevocable property both up and down the dominator tree.
3791    BB is the current block being scanned; EXIT_BLOCKS are the edges of the
3792    TM regions; OLD_IRR are the results of a previous scan of the dominator
3793    tree which has been fully propagated; NEW_IRR is the set of new blocks
3794    which are gaining the irrevocable property during the current scan.  */
3795
3796 static void
3797 ipa_tm_propagate_irr (basic_block entry_block, bitmap new_irr,
3798                       bitmap old_irr, bitmap exit_blocks)
3799 {
3800   VEC (basic_block, heap) *bbs;
3801   bitmap all_region_blocks;
3802
3803   /* If this block is in the old set, no need to rescan.  */
3804   if (old_irr && bitmap_bit_p (old_irr, entry_block->index))
3805     return;
3806
3807   all_region_blocks = BITMAP_ALLOC (&tm_obstack);
3808   bbs = get_tm_region_blocks (entry_block, exit_blocks, NULL,
3809                               all_region_blocks, false);
3810   do
3811     {
3812       basic_block bb = VEC_pop (basic_block, bbs);
3813       bool this_irr = bitmap_bit_p (new_irr, bb->index);
3814       bool all_son_irr = false;
3815       edge_iterator ei;
3816       edge e;
3817
3818       /* Propagate up.  If my children are, I am too, but we must have
3819          at least one child that is.  */
3820       if (!this_irr)
3821         {
3822           FOR_EACH_EDGE (e, ei, bb->succs)
3823             {
3824               if (!bitmap_bit_p (new_irr, e->dest->index))
3825                 {
3826                   all_son_irr = false;
3827                   break;
3828                 }
3829               else
3830                 all_son_irr = true;
3831             }
3832           if (all_son_irr)
3833             {
3834               /* Add block to new_irr if it hasn't already been processed. */
3835               if (!old_irr || !bitmap_bit_p (old_irr, bb->index))
3836                 {
3837                   bitmap_set_bit (new_irr, bb->index);
3838                   this_irr = true;
3839                 }
3840             }
3841         }
3842
3843       /* Propagate down to everyone we immediately dominate.  */
3844       if (this_irr)
3845         {
3846           basic_block son;
3847           for (son = first_dom_son (CDI_DOMINATORS, bb);
3848                son;
3849                son = next_dom_son (CDI_DOMINATORS, son))
3850             {
3851               /* Make sure block is actually in a TM region, and it
3852                  isn't already in old_irr.  */
3853               if ((!old_irr || !bitmap_bit_p (old_irr, son->index))
3854                   && bitmap_bit_p (all_region_blocks, son->index))
3855                 bitmap_set_bit (new_irr, son->index);
3856             }
3857         }
3858     }
3859   while (!VEC_empty (basic_block, bbs));
3860
3861   BITMAP_FREE (all_region_blocks);
3862   VEC_free (basic_block, heap, bbs);
3863 }
3864
3865 static void
3866 ipa_tm_decrement_clone_counts (basic_block bb, bool for_clone)
3867 {
3868   gimple_stmt_iterator gsi;
3869
3870   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3871     {
3872       gimple stmt = gsi_stmt (gsi);
3873       if (is_gimple_call (stmt) && !is_tm_pure_call (stmt))
3874         {
3875           tree fndecl = gimple_call_fndecl (stmt);
3876           if (fndecl)
3877             {
3878               struct tm_ipa_cg_data *d;
3879               unsigned *pcallers;
3880               struct cgraph_node *tnode;
3881
3882               if (is_tm_ending_fndecl (fndecl))
3883                 continue;
3884               if (find_tm_replacement_function (fndecl))
3885                 continue;
3886
3887               tnode = cgraph_get_node (fndecl);
3888               d = get_cg_data (&tnode, true);
3889
3890               pcallers = (for_clone ? &d->tm_callers_clone
3891                           : &d->tm_callers_normal);
3892
3893               gcc_assert (*pcallers > 0);
3894               *pcallers -= 1;
3895             }
3896         }
3897     }
3898 }
3899
3900 /* (Re-)Scan the transaction blocks in NODE for calls to irrevocable functions,
3901    as well as other irrevocable actions such as inline assembly.  Mark all
3902    such blocks as irrevocable and decrement the number of calls to
3903    transactional clones.  Return true if, for the transactional clone, the
3904    entire function is irrevocable.  */
3905
3906 static bool
3907 ipa_tm_scan_irr_function (struct cgraph_node *node, bool for_clone)
3908 {
3909   struct tm_ipa_cg_data *d;
3910   bitmap new_irr, old_irr;
3911   VEC (basic_block, heap) *queue;
3912   bool ret = false;
3913
3914   /* Builtin operators (operator new, and such).  */
3915   if (DECL_STRUCT_FUNCTION (node->decl) == NULL
3916       || DECL_STRUCT_FUNCTION (node->decl)->cfg == NULL)
3917     return false;
3918
3919   current_function_decl = node->decl;
3920   push_cfun (DECL_STRUCT_FUNCTION (node->decl));
3921   calculate_dominance_info (CDI_DOMINATORS);
3922
3923   d = get_cg_data (&node, true);
3924   queue = VEC_alloc (basic_block, heap, 10);
3925   new_irr = BITMAP_ALLOC (&tm_obstack);
3926
3927   /* Scan each tm region, propagating irrevocable status through the tree.  */
3928   if (for_clone)
3929     {
3930       old_irr = d->irrevocable_blocks_clone;
3931       VEC_quick_push (basic_block, queue, single_succ (ENTRY_BLOCK_PTR));
3932       if (ipa_tm_scan_irr_blocks (&queue, new_irr, old_irr, NULL))
3933         {
3934           ipa_tm_propagate_irr (single_succ (ENTRY_BLOCK_PTR), new_irr,
3935                                 old_irr, NULL);
3936           ret = bitmap_bit_p (new_irr, single_succ (ENTRY_BLOCK_PTR)->index);
3937         }
3938     }
3939   else
3940     {
3941       struct tm_region *region;
3942
3943       old_irr = d->irrevocable_blocks_normal;
3944       for (region = d->all_tm_regions; region; region = region->next)
3945         {
3946           VEC_quick_push (basic_block, queue, region->entry_block);
3947           if (ipa_tm_scan_irr_blocks (&queue, new_irr, old_irr,
3948                                       region->exit_blocks))
3949             ipa_tm_propagate_irr (region->entry_block, new_irr, old_irr,
3950                                   region->exit_blocks);
3951         }
3952     }
3953
3954   /* If we found any new irrevocable blocks, reduce the call count for
3955      transactional clones within the irrevocable blocks.  Save the new
3956      set of irrevocable blocks for next time.  */
3957   if (!bitmap_empty_p (new_irr))
3958     {
3959       bitmap_iterator bmi;
3960       unsigned i;
3961
3962       EXECUTE_IF_SET_IN_BITMAP (new_irr, 0, i, bmi)
3963         ipa_tm_decrement_clone_counts (BASIC_BLOCK (i), for_clone);
3964
3965       if (old_irr)
3966         {
3967           bitmap_ior_into (old_irr, new_irr);
3968           BITMAP_FREE (new_irr);
3969         }
3970       else if (for_clone)
3971         d->irrevocable_blocks_clone = new_irr;
3972       else
3973         d->irrevocable_blocks_normal = new_irr;
3974
3975       if (dump_file && new_irr)
3976         {
3977           const char *dname;
3978           bitmap_iterator bmi;
3979           unsigned i;
3980
3981           dname = lang_hooks.decl_printable_name (current_function_decl, 2);
3982           EXECUTE_IF_SET_IN_BITMAP (new_irr, 0, i, bmi)
3983             fprintf (dump_file, "%s: bb %d goes irrevocable\n", dname, i);
3984         }
3985     }
3986   else
3987     BITMAP_FREE (new_irr);
3988
3989   VEC_free (basic_block, heap, queue);
3990   pop_cfun ();
3991   current_function_decl = NULL;
3992
3993   return ret;
3994 }
3995
3996 /* Return true if, for the transactional clone of NODE, any call
3997    may enter irrevocable mode.  */
3998
3999 static bool
4000 ipa_tm_mayenterirr_function (struct cgraph_node *node)
4001 {
4002   struct tm_ipa_cg_data *d;
4003   tree decl;
4004   unsigned flags;
4005
4006   d = get_cg_data (&node, true);
4007   decl = node->decl;
4008   flags = flags_from_decl_or_type (decl);
4009
4010   /* Handle some TM builtins.  Ordinarily these aren't actually generated
4011      at this point, but handling these functions when written in by the
4012      user makes it easier to build unit tests.  */
4013   if (flags & ECF_TM_BUILTIN)
4014     return false;
4015
4016   /* Filter out all functions that are marked.  */
4017   if (flags & ECF_TM_PURE)
4018     return false;
4019   if (is_tm_safe (decl))
4020     return false;
4021   if (is_tm_irrevocable (decl))
4022     return true;
4023   if (is_tm_callable (decl))
4024     return true;
4025   if (find_tm_replacement_function (decl))
4026     return true;
4027
4028   /* If we aren't seeing the final version of the function we don't
4029      know what it will contain at runtime.  */
4030   if (cgraph_function_body_availability (node) < AVAIL_AVAILABLE)
4031     return true;
4032
4033   /* If the function must go irrevocable, then of course true.  */
4034   if (d->is_irrevocable)
4035     return true;
4036
4037   /* If there are any blocks marked irrevocable, then the function
4038      as a whole may enter irrevocable.  */
4039   if (d->irrevocable_blocks_clone)
4040     return true;
4041
4042   /* We may have previously marked this function as tm_may_enter_irr;
4043      see pass_diagnose_tm_blocks.  */
4044   if (node->local.tm_may_enter_irr)
4045     return true;
4046
4047   /* Recurse on the main body for aliases.  In general, this will
4048      result in one of the bits above being set so that we will not
4049      have to recurse next time.  */
4050   if (node->alias)
4051     return ipa_tm_mayenterirr_function (cgraph_get_node (node->thunk.alias));
4052
4053   /* What remains is unmarked local functions without items that force
4054      the function to go irrevocable.  */
4055   return false;
4056 }
4057
4058 /* Diagnose calls from transaction_safe functions to unmarked
4059    functions that are determined to not be safe.  */
4060
4061 static void
4062 ipa_tm_diagnose_tm_safe (struct cgraph_node *node)
4063 {
4064   struct cgraph_edge *e;
4065
4066   for (e = node->callees; e ; e = e->next_callee)
4067     if (!is_tm_callable (e->callee->decl)
4068         && e->callee->local.tm_may_enter_irr)
4069       error_at (gimple_location (e->call_stmt),
4070                 "unsafe function call %qD within "
4071                 "%<transaction_safe%> function", e->callee->decl);
4072 }
4073
4074 /* Diagnose call from atomic transactions to unmarked functions
4075    that are determined to not be safe.  */
4076
4077 static void
4078 ipa_tm_diagnose_transaction (struct cgraph_node *node,
4079                            struct tm_region *all_tm_regions)
4080 {
4081   struct tm_region *r;
4082
4083   for (r = all_tm_regions; r ; r = r->next)
4084     if (gimple_transaction_subcode (r->transaction_stmt) & GTMA_IS_RELAXED)
4085       {
4086         /* Atomic transactions can be nested inside relaxed.  */
4087         if (r->inner)
4088           ipa_tm_diagnose_transaction (node, r->inner);
4089       }
4090     else
4091       {
4092         VEC (basic_block, heap) *bbs;
4093         gimple_stmt_iterator gsi;
4094         basic_block bb;
4095         size_t i;
4096
4097         bbs = get_tm_region_blocks (r->entry_block, r->exit_blocks,
4098                                     r->irr_blocks, NULL, false);
4099
4100         for (i = 0; VEC_iterate (basic_block, bbs, i, bb); ++i)
4101           for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4102             {
4103               gimple stmt = gsi_stmt (gsi);
4104               tree fndecl;
4105
4106               if (gimple_code (stmt) == GIMPLE_ASM)
4107                 {
4108                   error_at (gimple_location (stmt),
4109                             "asm not allowed in atomic transaction");
4110                   continue;
4111                 }
4112
4113               if (!is_gimple_call (stmt))
4114                 continue;
4115               fndecl = gimple_call_fndecl (stmt);
4116
4117               /* Indirect function calls have been diagnosed already.  */
4118               if (!fndecl)
4119                 continue;
4120
4121               /* Stop at the end of the transaction.  */
4122               if (is_tm_ending_fndecl (fndecl))
4123                 {
4124                   if (bitmap_bit_p (r->exit_blocks, bb->index))
4125                     break;
4126                   continue;
4127                 }
4128
4129               /* Marked functions have been diagnosed already.  */
4130               if (is_tm_pure_call (stmt))
4131                 continue;
4132               if (is_tm_callable (fndecl))
4133                 continue;
4134
4135               if (cgraph_local_info (fndecl)->tm_may_enter_irr)
4136                 error_at (gimple_location (stmt),
4137                           "unsafe function call %qD within "
4138                           "atomic transaction", fndecl);
4139             }
4140
4141         VEC_free (basic_block, heap, bbs);
4142       }
4143 }
4144
4145 /* Return a transactional mangled name for the DECL_ASSEMBLER_NAME in
4146    OLD_DECL.  The returned value is a freshly malloced pointer that
4147    should be freed by the caller.  */
4148
4149 static tree
4150 tm_mangle (tree old_asm_id)
4151 {
4152   const char *old_asm_name;
4153   char *tm_name;
4154   void *alloc = NULL;
4155   struct demangle_component *dc;
4156   tree new_asm_id;
4157
4158   /* Determine if the symbol is already a valid C++ mangled name.  Do this
4159      even for C, which might be interfacing with C++ code via appropriately
4160      ugly identifiers.  */
4161   /* ??? We could probably do just as well checking for "_Z" and be done.  */
4162   old_asm_name = IDENTIFIER_POINTER (old_asm_id);
4163   dc = cplus_demangle_v3_components (old_asm_name, DMGL_NO_OPTS, &alloc);
4164
4165   if (dc == NULL)
4166     {
4167       char length[8];
4168
4169     do_unencoded:
4170       sprintf (length, "%u", IDENTIFIER_LENGTH (old_asm_id));
4171       tm_name = concat ("_ZGTt", length, old_asm_name, NULL);
4172     }
4173   else
4174     {
4175       old_asm_name += 2;        /* Skip _Z */
4176
4177       switch (dc->type)
4178         {
4179         case DEMANGLE_COMPONENT_TRANSACTION_CLONE:
4180         case DEMANGLE_COMPONENT_NONTRANSACTION_CLONE:
4181           /* Don't play silly games, you!  */
4182           goto do_unencoded;
4183
4184         case DEMANGLE_COMPONENT_HIDDEN_ALIAS:
4185           /* I'd really like to know if we can ever be passed one of
4186              these from the C++ front end.  The Logical Thing would
4187              seem that hidden-alias should be outer-most, so that we
4188              get hidden-alias of a transaction-clone and not vice-versa.  */
4189           old_asm_name += 2;
4190           break;
4191
4192         default:
4193           break;
4194         }
4195
4196       tm_name = concat ("_ZGTt", old_asm_name, NULL);
4197     }
4198   free (alloc);
4199
4200   new_asm_id = get_identifier (tm_name);
4201   free (tm_name);
4202
4203   return new_asm_id;
4204 }
4205
4206 static inline void
4207 ipa_tm_mark_needed_node (struct cgraph_node *node)
4208 {
4209   cgraph_mark_needed_node (node);