OSDN Git Service

bd4ce3933e63a3f458c1b7d3590a788f87c59610
[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           /* X escapes.  */
1501           || ptr_deref_may_alias_global_p (x))
1502         return true;
1503       else
1504         {
1505           /* For local memory that doesn't escape (aka thread private
1506              memory), we can either save the value at the beginning of
1507              the transaction and restore on restart, or call a tm
1508              function to dynamically save and restore on restart
1509              (ITM_L*).  */
1510           if (stmt)
1511             tm_log_add (entry_block, orig, stmt);
1512           return false;
1513         }
1514
1515     default:
1516       return false;
1517     }
1518 }
1519
1520 /* Mark the GIMPLE_ASSIGN statement as appropriate for being inside
1521    a transaction region.  */
1522
1523 static void
1524 examine_assign_tm (unsigned *state, gimple_stmt_iterator *gsi)
1525 {
1526   gimple stmt = gsi_stmt (*gsi);
1527
1528   if (requires_barrier (/*entry_block=*/NULL, gimple_assign_rhs1 (stmt), NULL))
1529     *state |= GTMA_HAVE_LOAD;
1530   if (requires_barrier (/*entry_block=*/NULL, gimple_assign_lhs (stmt), NULL))
1531     *state |= GTMA_HAVE_STORE;
1532 }
1533
1534 /* Mark a GIMPLE_CALL as appropriate for being inside a transaction.  */
1535
1536 static void
1537 examine_call_tm (unsigned *state, gimple_stmt_iterator *gsi)
1538 {
1539   gimple stmt = gsi_stmt (*gsi);
1540   tree fn;
1541
1542   if (is_tm_pure_call (stmt))
1543     return;
1544
1545   /* Check if this call is a transaction abort.  */
1546   fn = gimple_call_fndecl (stmt);
1547   if (is_tm_abort (fn))
1548     *state |= GTMA_HAVE_ABORT;
1549
1550   /* Note that something may happen.  */
1551   *state |= GTMA_HAVE_LOAD | GTMA_HAVE_STORE;
1552 }
1553
1554 /* Lower a GIMPLE_TRANSACTION statement.  */
1555
1556 static void
1557 lower_transaction (gimple_stmt_iterator *gsi, struct walk_stmt_info *wi)
1558 {
1559   gimple g, stmt = gsi_stmt (*gsi);
1560   unsigned int *outer_state = (unsigned int *) wi->info;
1561   unsigned int this_state = 0;
1562   struct walk_stmt_info this_wi;
1563
1564   /* First, lower the body.  The scanning that we do inside gives
1565      us some idea of what we're dealing with.  */
1566   memset (&this_wi, 0, sizeof (this_wi));
1567   this_wi.info = (void *) &this_state;
1568   walk_gimple_seq (gimple_transaction_body (stmt),
1569                    lower_sequence_tm, NULL, &this_wi);
1570
1571   /* If there was absolutely nothing transaction related inside the
1572      transaction, we may elide it.  Likewise if this is a nested
1573      transaction and does not contain an abort.  */
1574   if (this_state == 0
1575       || (!(this_state & GTMA_HAVE_ABORT) && outer_state != NULL))
1576     {
1577       if (outer_state)
1578         *outer_state |= this_state;
1579
1580       gsi_insert_seq_before (gsi, gimple_transaction_body (stmt),
1581                              GSI_SAME_STMT);
1582       gimple_transaction_set_body (stmt, NULL);
1583
1584       gsi_remove (gsi, true);
1585       wi->removed_stmt = true;
1586       return;
1587     }
1588
1589   /* Wrap the body of the transaction in a try-finally node so that
1590      the commit call is always properly called.  */
1591   g = gimple_build_call (builtin_decl_explicit (BUILT_IN_TM_COMMIT), 0);
1592   if (flag_exceptions)
1593     {
1594       tree ptr;
1595       gimple_seq n_seq, e_seq;
1596
1597       n_seq = gimple_seq_alloc_with_stmt (g);
1598       e_seq = gimple_seq_alloc ();
1599
1600       g = gimple_build_call (builtin_decl_explicit (BUILT_IN_EH_POINTER),
1601                              1, integer_zero_node);
1602       ptr = create_tmp_var (ptr_type_node, NULL);
1603       gimple_call_set_lhs (g, ptr);
1604       gimple_seq_add_stmt (&e_seq, g);
1605
1606       g = gimple_build_call (builtin_decl_explicit (BUILT_IN_TM_COMMIT_EH),
1607                              1, ptr);
1608       gimple_seq_add_stmt (&e_seq, g);
1609
1610       g = gimple_build_eh_else (n_seq, e_seq);
1611     }
1612
1613   g = gimple_build_try (gimple_transaction_body (stmt),
1614                         gimple_seq_alloc_with_stmt (g), GIMPLE_TRY_FINALLY);
1615   gsi_insert_after (gsi, g, GSI_CONTINUE_LINKING);
1616
1617   gimple_transaction_set_body (stmt, NULL);
1618
1619   /* If the transaction calls abort or if this is an outer transaction,
1620      add an "over" label afterwards.  */
1621   if ((this_state & (GTMA_HAVE_ABORT))
1622       || (gimple_transaction_subcode(stmt) & GTMA_IS_OUTER))
1623     {
1624       tree label = create_artificial_label (UNKNOWN_LOCATION);
1625       gimple_transaction_set_label (stmt, label);
1626       gsi_insert_after (gsi, gimple_build_label (label), GSI_CONTINUE_LINKING);
1627     }
1628
1629   /* Record the set of operations found for use later.  */
1630   this_state |= gimple_transaction_subcode (stmt) & GTMA_DECLARATION_MASK;
1631   gimple_transaction_set_subcode (stmt, this_state);
1632 }
1633
1634 /* Iterate through the statements in the sequence, lowering them all
1635    as appropriate for being in a transaction.  */
1636
1637 static tree
1638 lower_sequence_tm (gimple_stmt_iterator *gsi, bool *handled_ops_p,
1639                    struct walk_stmt_info *wi)
1640 {
1641   unsigned int *state = (unsigned int *) wi->info;
1642   gimple stmt = gsi_stmt (*gsi);
1643
1644   *handled_ops_p = true;
1645   switch (gimple_code (stmt))
1646     {
1647     case GIMPLE_ASSIGN:
1648       /* Only memory reads/writes need to be instrumented.  */
1649       if (gimple_assign_single_p (stmt))
1650         examine_assign_tm (state, gsi);
1651       break;
1652
1653     case GIMPLE_CALL:
1654       examine_call_tm (state, gsi);
1655       break;
1656
1657     case GIMPLE_ASM:
1658       *state |= GTMA_MAY_ENTER_IRREVOCABLE;
1659       break;
1660
1661     case GIMPLE_TRANSACTION:
1662       lower_transaction (gsi, wi);
1663       break;
1664
1665     default:
1666       *handled_ops_p = !gimple_has_substatements (stmt);
1667       break;
1668     }
1669
1670   return NULL_TREE;
1671 }
1672
1673 /* Iterate through the statements in the sequence, lowering them all
1674    as appropriate for being outside of a transaction.  */
1675
1676 static tree
1677 lower_sequence_no_tm (gimple_stmt_iterator *gsi, bool *handled_ops_p,
1678                       struct walk_stmt_info * wi)
1679 {
1680   gimple stmt = gsi_stmt (*gsi);
1681
1682   if (gimple_code (stmt) == GIMPLE_TRANSACTION)
1683     {
1684       *handled_ops_p = true;
1685       lower_transaction (gsi, wi);
1686     }
1687   else
1688     *handled_ops_p = !gimple_has_substatements (stmt);
1689
1690   return NULL_TREE;
1691 }
1692
1693 /* Main entry point for flattening GIMPLE_TRANSACTION constructs.  After
1694    this, GIMPLE_TRANSACTION nodes still exist, but the nested body has
1695    been moved out, and all the data required for constructing a proper
1696    CFG has been recorded.  */
1697
1698 static unsigned int
1699 execute_lower_tm (void)
1700 {
1701   struct walk_stmt_info wi;
1702
1703   /* Transactional clones aren't created until a later pass.  */
1704   gcc_assert (!decl_is_tm_clone (current_function_decl));
1705
1706   memset (&wi, 0, sizeof (wi));
1707   walk_gimple_seq (gimple_body (current_function_decl),
1708                    lower_sequence_no_tm, NULL, &wi);
1709
1710   return 0;
1711 }
1712
1713 struct gimple_opt_pass pass_lower_tm =
1714 {
1715  {
1716   GIMPLE_PASS,
1717   "tmlower",                            /* name */
1718   gate_tm,                              /* gate */
1719   execute_lower_tm,                     /* execute */
1720   NULL,                                 /* sub */
1721   NULL,                                 /* next */
1722   0,                                    /* static_pass_number */
1723   TV_TRANS_MEM,                         /* tv_id */
1724   PROP_gimple_lcf,                      /* properties_required */
1725   0,                                    /* properties_provided */
1726   0,                                    /* properties_destroyed */
1727   0,                                    /* todo_flags_start */
1728   TODO_dump_func                        /* todo_flags_finish */
1729  }
1730 };
1731 \f
1732 /* Collect region information for each transaction.  */
1733
1734 struct tm_region
1735 {
1736   /* Link to the next unnested transaction.  */
1737   struct tm_region *next;
1738
1739   /* Link to the next inner transaction.  */
1740   struct tm_region *inner;
1741
1742   /* Link to the next outer transaction.  */
1743   struct tm_region *outer;
1744
1745   /* The GIMPLE_TRANSACTION statement beginning this transaction.  */
1746   gimple transaction_stmt;
1747
1748   /* The entry block to this region.  */
1749   basic_block entry_block;
1750
1751   /* The set of all blocks that end the region; NULL if only EXIT_BLOCK.
1752      These blocks are still a part of the region (i.e., the border is
1753      inclusive). Note that this set is only complete for paths in the CFG
1754      starting at ENTRY_BLOCK, and that there is no exit block recorded for
1755      the edge to the "over" label.  */
1756   bitmap exit_blocks;
1757
1758   /* The set of all blocks that have an TM_IRREVOCABLE call.  */
1759   bitmap irr_blocks;
1760 };
1761
1762 /* True if there are pending edge statements to be committed for the
1763    current function being scanned in the tmmark pass.  */
1764 bool pending_edge_inserts_p;
1765
1766 static struct tm_region *all_tm_regions;
1767 static bitmap_obstack tm_obstack;
1768
1769
1770 /* A subroutine of tm_region_init.  Record the existance of the
1771    GIMPLE_TRANSACTION statement in a tree of tm_region elements.  */
1772
1773 static struct tm_region *
1774 tm_region_init_0 (struct tm_region *outer, basic_block bb, gimple stmt)
1775 {
1776   struct tm_region *region;
1777
1778   region = (struct tm_region *)
1779     obstack_alloc (&tm_obstack.obstack, sizeof (struct tm_region));
1780
1781   if (outer)
1782     {
1783       region->next = outer->inner;
1784       outer->inner = region;
1785     }
1786   else
1787     {
1788       region->next = all_tm_regions;
1789       all_tm_regions = region;
1790     }
1791   region->inner = NULL;
1792   region->outer = outer;
1793
1794   region->transaction_stmt = stmt;
1795
1796   /* There are either one or two edges out of the block containing
1797      the GIMPLE_TRANSACTION, one to the actual region and one to the
1798      "over" label if the region contains an abort.  The former will
1799      always be the one marked FALLTHRU.  */
1800   region->entry_block = FALLTHRU_EDGE (bb)->dest;
1801
1802   region->exit_blocks = BITMAP_ALLOC (&tm_obstack);
1803   region->irr_blocks = BITMAP_ALLOC (&tm_obstack);
1804
1805   return region;
1806 }
1807
1808 /* A subroutine of tm_region_init.  Record all the exit and
1809    irrevocable blocks in BB into the region's exit_blocks and
1810    irr_blocks bitmaps.  Returns the new region being scanned.  */
1811
1812 static struct tm_region *
1813 tm_region_init_1 (struct tm_region *region, basic_block bb)
1814 {
1815   gimple_stmt_iterator gsi;
1816   gimple g;
1817
1818   if (!region
1819       || (!region->irr_blocks && !region->exit_blocks))
1820     return region;
1821
1822   /* Check to see if this is the end of a region by seeing if it
1823      contains a call to __builtin_tm_commit{,_eh}.  Note that the
1824      outermost region for DECL_IS_TM_CLONE need not collect this.  */
1825   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
1826     {
1827       g = gsi_stmt (gsi);
1828       if (gimple_code (g) == GIMPLE_CALL)
1829         {
1830           tree fn = gimple_call_fndecl (g);
1831           if (fn && DECL_BUILT_IN_CLASS (fn) == BUILT_IN_NORMAL)
1832             {
1833               if ((DECL_FUNCTION_CODE (fn) == BUILT_IN_TM_COMMIT
1834                    || DECL_FUNCTION_CODE (fn) == BUILT_IN_TM_COMMIT_EH)
1835                   && region->exit_blocks)
1836                 {
1837                   bitmap_set_bit (region->exit_blocks, bb->index);
1838                   region = region->outer;
1839                   break;
1840                 }
1841               if (DECL_FUNCTION_CODE (fn) == BUILT_IN_TM_IRREVOCABLE)
1842                 bitmap_set_bit (region->irr_blocks, bb->index);
1843             }
1844         }
1845     }
1846   return region;
1847 }
1848
1849 /* Collect all of the transaction regions within the current function
1850    and record them in ALL_TM_REGIONS.  The REGION parameter may specify
1851    an "outermost" region for use by tm clones.  */
1852
1853 static void
1854 tm_region_init (struct tm_region *region)
1855 {
1856   gimple g;
1857   edge_iterator ei;
1858   edge e;
1859   basic_block bb;
1860   VEC(basic_block, heap) *queue = NULL;
1861   bitmap visited_blocks = BITMAP_ALLOC (NULL);
1862   struct tm_region *old_region;
1863
1864   all_tm_regions = region;
1865   bb = single_succ (ENTRY_BLOCK_PTR);
1866
1867   VEC_safe_push (basic_block, heap, queue, bb);
1868   gcc_assert (!bb->aux);        /* FIXME: Remove me.  */
1869   bb->aux = region;
1870   do
1871     {
1872       bb = VEC_pop (basic_block, queue);
1873       region = (struct tm_region *)bb->aux;
1874       bb->aux = NULL;
1875
1876       /* Record exit and irrevocable blocks.  */
1877       region = tm_region_init_1 (region, bb);
1878
1879       /* Check for the last statement in the block beginning a new region.  */
1880       g = last_stmt (bb);
1881       old_region = region;
1882       if (g && gimple_code (g) == GIMPLE_TRANSACTION)
1883         region = tm_region_init_0 (region, bb, g);
1884
1885       /* Process subsequent blocks.  */
1886       FOR_EACH_EDGE (e, ei, bb->succs)
1887         if (!bitmap_bit_p (visited_blocks, e->dest->index))
1888           {
1889             bitmap_set_bit (visited_blocks, e->dest->index);
1890             VEC_safe_push (basic_block, heap, queue, e->dest);
1891             gcc_assert (!e->dest->aux); /* FIXME: Remove me.  */
1892
1893             /* If the current block started a new region, make sure that only
1894                the entry block of the new region is associated with this region.
1895                Other successors are still part of the old region.  */
1896             if (old_region != region && e->dest != region->entry_block)
1897               e->dest->aux = old_region;
1898             else
1899               e->dest->aux = region;
1900           }
1901     }
1902   while (!VEC_empty (basic_block, queue));
1903   VEC_free (basic_block, heap, queue);
1904   BITMAP_FREE (visited_blocks);
1905 }
1906
1907 /* The "gate" function for all transactional memory expansion and optimization
1908    passes.  We collect region information for each top-level transaction, and
1909    if we don't find any, we skip all of the TM passes.  Each region will have
1910    all of the exit blocks recorded, and the originating statement.  */
1911
1912 static bool
1913 gate_tm_init (void)
1914 {
1915   if (!flag_tm)
1916     return false;
1917
1918   calculate_dominance_info (CDI_DOMINATORS);
1919   bitmap_obstack_initialize (&tm_obstack);
1920
1921   /* If the function is a TM_CLONE, then the entire function is the region.  */
1922   if (decl_is_tm_clone (current_function_decl))
1923     {
1924       struct tm_region *region = (struct tm_region *)
1925         obstack_alloc (&tm_obstack.obstack, sizeof (struct tm_region));
1926       memset (region, 0, sizeof (*region));
1927       region->entry_block = single_succ (ENTRY_BLOCK_PTR);
1928       /* For a clone, the entire function is the region.  But even if
1929          we don't need to record any exit blocks, we may need to
1930          record irrevocable blocks.  */
1931       region->irr_blocks = BITMAP_ALLOC (&tm_obstack);
1932
1933       tm_region_init (region);
1934     }
1935   else
1936     {
1937       tm_region_init (NULL);
1938
1939       /* If we didn't find any regions, cleanup and skip the whole tree
1940          of tm-related optimizations.  */
1941       if (all_tm_regions == NULL)
1942         {
1943           bitmap_obstack_release (&tm_obstack);
1944           return false;
1945         }
1946     }
1947
1948   return true;
1949 }
1950
1951 struct gimple_opt_pass pass_tm_init =
1952 {
1953  {
1954   GIMPLE_PASS,
1955   "*tminit",                            /* name */
1956   gate_tm_init,                         /* gate */
1957   NULL,                                 /* execute */
1958   NULL,                                 /* sub */
1959   NULL,                                 /* next */
1960   0,                                    /* static_pass_number */
1961   TV_TRANS_MEM,                         /* tv_id */
1962   PROP_ssa | PROP_cfg,                  /* properties_required */
1963   0,                                    /* properties_provided */
1964   0,                                    /* properties_destroyed */
1965   0,                                    /* todo_flags_start */
1966   0,                                    /* todo_flags_finish */
1967  }
1968 };
1969 \f
1970 /* Add FLAGS to the GIMPLE_TRANSACTION subcode for the transaction region
1971    represented by STATE.  */
1972
1973 static inline void
1974 transaction_subcode_ior (struct tm_region *region, unsigned flags)
1975 {
1976   if (region && region->transaction_stmt)
1977     {
1978       flags |= gimple_transaction_subcode (region->transaction_stmt);
1979       gimple_transaction_set_subcode (region->transaction_stmt, flags);
1980     }
1981 }
1982
1983 /* Construct a memory load in a transactional context.  Return the
1984    gimple statement performing the load, or NULL if there is no
1985    TM_LOAD builtin of the appropriate size to do the load.
1986
1987    LOC is the location to use for the new statement(s).  */
1988
1989 static gimple
1990 build_tm_load (location_t loc, tree lhs, tree rhs, gimple_stmt_iterator *gsi)
1991 {
1992   enum built_in_function code = END_BUILTINS;
1993   tree t, type = TREE_TYPE (rhs), decl;
1994   gimple gcall;
1995
1996   if (type == float_type_node)
1997     code = BUILT_IN_TM_LOAD_FLOAT;
1998   else if (type == double_type_node)
1999     code = BUILT_IN_TM_LOAD_DOUBLE;
2000   else if (type == long_double_type_node)
2001     code = BUILT_IN_TM_LOAD_LDOUBLE;
2002   else if (TYPE_SIZE_UNIT (type) != NULL
2003            && host_integerp (TYPE_SIZE_UNIT (type), 1))
2004     {
2005       switch (tree_low_cst (TYPE_SIZE_UNIT (type), 1))
2006         {
2007         case 1:
2008           code = BUILT_IN_TM_LOAD_1;
2009           break;
2010         case 2:
2011           code = BUILT_IN_TM_LOAD_2;
2012           break;
2013         case 4:
2014           code = BUILT_IN_TM_LOAD_4;
2015           break;
2016         case 8:
2017           code = BUILT_IN_TM_LOAD_8;
2018           break;
2019         }
2020     }
2021
2022   if (code == END_BUILTINS)
2023     {
2024       decl = targetm.vectorize.builtin_tm_load (type);
2025       if (!decl)
2026         return NULL;
2027     }
2028   else
2029     decl = builtin_decl_explicit (code);
2030
2031   t = gimplify_addr (gsi, rhs);
2032   gcall = gimple_build_call (decl, 1, t);
2033   gimple_set_location (gcall, loc);
2034
2035   t = TREE_TYPE (TREE_TYPE (decl));
2036   if (useless_type_conversion_p (type, t))
2037     {
2038       gimple_call_set_lhs (gcall, lhs);
2039       gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2040     }
2041   else
2042     {
2043       gimple g;
2044       tree temp;
2045
2046       temp = make_rename_temp (t, NULL);
2047       gimple_call_set_lhs (gcall, temp);
2048       gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2049
2050       t = fold_build1 (VIEW_CONVERT_EXPR, type, temp);
2051       g = gimple_build_assign (lhs, t);
2052       gsi_insert_before (gsi, g, GSI_SAME_STMT);
2053     }
2054
2055   return gcall;
2056 }
2057
2058
2059 /* Similarly for storing TYPE in a transactional context.  */
2060
2061 static gimple
2062 build_tm_store (location_t loc, tree lhs, tree rhs, gimple_stmt_iterator *gsi)
2063 {
2064   enum built_in_function code = END_BUILTINS;
2065   tree t, fn, type = TREE_TYPE (rhs), simple_type;
2066   gimple gcall;
2067
2068   if (type == float_type_node)
2069     code = BUILT_IN_TM_STORE_FLOAT;
2070   else if (type == double_type_node)
2071     code = BUILT_IN_TM_STORE_DOUBLE;
2072   else if (type == long_double_type_node)
2073     code = BUILT_IN_TM_STORE_LDOUBLE;
2074   else if (TYPE_SIZE_UNIT (type) != NULL
2075            && host_integerp (TYPE_SIZE_UNIT (type), 1))
2076     {
2077       switch (tree_low_cst (TYPE_SIZE_UNIT (type), 1))
2078         {
2079         case 1:
2080           code = BUILT_IN_TM_STORE_1;
2081           break;
2082         case 2:
2083           code = BUILT_IN_TM_STORE_2;
2084           break;
2085         case 4:
2086           code = BUILT_IN_TM_STORE_4;
2087           break;
2088         case 8:
2089           code = BUILT_IN_TM_STORE_8;
2090           break;
2091         }
2092     }
2093
2094   if (code == END_BUILTINS)
2095     {
2096       fn = targetm.vectorize.builtin_tm_store (type);
2097       if (!fn)
2098         return NULL;
2099     }
2100   else
2101     fn = builtin_decl_explicit (code);
2102
2103   simple_type = TREE_VALUE (TREE_CHAIN (TYPE_ARG_TYPES (TREE_TYPE (fn))));
2104
2105   if (TREE_CODE (rhs) == CONSTRUCTOR)
2106     {
2107       /* Handle the easy initialization to zero.  */
2108       if (CONSTRUCTOR_ELTS (rhs) == 0)
2109         rhs = build_int_cst (simple_type, 0);
2110       else
2111         {
2112           /* ...otherwise punt to the caller and probably use
2113             BUILT_IN_TM_MEMMOVE, because we can't wrap a
2114             VIEW_CONVERT_EXPR around a CONSTRUCTOR (below) and produce
2115             valid gimple.  */
2116           return NULL;
2117         }
2118     }
2119   else if (!useless_type_conversion_p (simple_type, type))
2120     {
2121       gimple g;
2122       tree temp;
2123
2124       temp = make_rename_temp (simple_type, NULL);
2125       t = fold_build1 (VIEW_CONVERT_EXPR, simple_type, rhs);
2126       g = gimple_build_assign (temp, t);
2127       gimple_set_location (g, loc);
2128       gsi_insert_before (gsi, g, GSI_SAME_STMT);
2129
2130       rhs = temp;
2131     }
2132
2133   t = gimplify_addr (gsi, lhs);
2134   gcall = gimple_build_call (fn, 2, t, rhs);
2135   gimple_set_location (gcall, loc);
2136   gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2137
2138   return gcall;
2139 }
2140
2141
2142 /* Expand an assignment statement into transactional builtins.  */
2143
2144 static void
2145 expand_assign_tm (struct tm_region *region, gimple_stmt_iterator *gsi)
2146 {
2147   gimple stmt = gsi_stmt (*gsi);
2148   location_t loc = gimple_location (stmt);
2149   tree lhs = gimple_assign_lhs (stmt);
2150   tree rhs = gimple_assign_rhs1 (stmt);
2151   bool store_p = requires_barrier (region->entry_block, lhs, NULL);
2152   bool load_p = requires_barrier (region->entry_block, rhs, NULL);
2153   gimple gcall = NULL;
2154
2155   if (!load_p && !store_p)
2156     {
2157       /* Add thread private addresses to log if applicable.  */
2158       requires_barrier (region->entry_block, lhs, stmt);
2159       gsi_next (gsi);
2160       return;
2161     }
2162
2163   gsi_remove (gsi, true);
2164
2165   if (load_p && !store_p)
2166     {
2167       transaction_subcode_ior (region, GTMA_HAVE_LOAD);
2168       gcall = build_tm_load (loc, lhs, rhs, gsi);
2169     }
2170   else if (store_p && !load_p)
2171     {
2172       transaction_subcode_ior (region, GTMA_HAVE_STORE);
2173       gcall = build_tm_store (loc, lhs, rhs, gsi);
2174     }
2175   if (!gcall)
2176     {
2177       tree lhs_addr, rhs_addr, tmp;
2178
2179       if (load_p)
2180         transaction_subcode_ior (region, GTMA_HAVE_LOAD);
2181       if (store_p)
2182         transaction_subcode_ior (region, GTMA_HAVE_STORE);
2183
2184       /* ??? Figure out if there's any possible overlap between the LHS
2185          and the RHS and if not, use MEMCPY.  */
2186
2187       if (load_p && is_gimple_reg (lhs))
2188         {
2189           tmp = create_tmp_var (TREE_TYPE (lhs), NULL);
2190           lhs_addr = build_fold_addr_expr (tmp);
2191         }
2192       else
2193         {
2194           tmp = NULL_TREE;
2195           lhs_addr = gimplify_addr (gsi, lhs);
2196         }
2197       rhs_addr = gimplify_addr (gsi, rhs);
2198       gcall = gimple_build_call (builtin_decl_explicit (BUILT_IN_TM_MEMMOVE),
2199                                  3, lhs_addr, rhs_addr,
2200                                  TYPE_SIZE_UNIT (TREE_TYPE (lhs)));
2201       gimple_set_location (gcall, loc);
2202       gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2203
2204       if (tmp)
2205         {
2206           gcall = gimple_build_assign (lhs, tmp);
2207           gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2208         }
2209     }
2210
2211   /* Now that we have the load/store in its instrumented form, add
2212      thread private addresses to the log if applicable.  */
2213   if (!store_p)
2214     requires_barrier (region->entry_block, lhs, gcall);
2215
2216   /* add_stmt_to_tm_region  (region, gcall); */
2217 }
2218
2219
2220 /* Expand a call statement as appropriate for a transaction.  That is,
2221    either verify that the call does not affect the transaction, or
2222    redirect the call to a clone that handles transactions, or change
2223    the transaction state to IRREVOCABLE.  Return true if the call is
2224    one of the builtins that end a transaction.  */
2225
2226 static bool
2227 expand_call_tm (struct tm_region *region,
2228                 gimple_stmt_iterator *gsi)
2229 {
2230   gimple stmt = gsi_stmt (*gsi);
2231   tree lhs = gimple_call_lhs (stmt);
2232   tree fn_decl;
2233   struct cgraph_node *node;
2234   bool retval = false;
2235
2236   fn_decl = gimple_call_fndecl (stmt);
2237
2238   if (fn_decl == builtin_decl_explicit (BUILT_IN_TM_MEMCPY)
2239       || fn_decl == builtin_decl_explicit (BUILT_IN_TM_MEMMOVE))
2240     transaction_subcode_ior (region, GTMA_HAVE_STORE | GTMA_HAVE_LOAD);
2241   if (fn_decl == builtin_decl_explicit (BUILT_IN_TM_MEMSET))
2242     transaction_subcode_ior (region, GTMA_HAVE_STORE);
2243
2244   if (is_tm_pure_call (stmt))
2245     return false;
2246
2247   if (fn_decl)
2248     retval = is_tm_ending_fndecl (fn_decl);
2249   if (!retval)
2250     {
2251       /* Assume all non-const/pure calls write to memory, except
2252          transaction ending builtins.  */
2253       transaction_subcode_ior (region, GTMA_HAVE_STORE);
2254     }
2255
2256   /* For indirect calls, we already generated a call into the runtime.  */
2257   if (!fn_decl)
2258     {
2259       tree fn = gimple_call_fn (stmt);
2260
2261       /* We are guaranteed never to go irrevocable on a safe or pure
2262          call, and the pure call was handled above.  */
2263       if (is_tm_safe (fn))
2264         return false;
2265       else
2266         transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
2267
2268       return false;
2269     }
2270
2271   node = cgraph_get_node (fn_decl);
2272   if (node->local.tm_may_enter_irr)
2273     transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
2274
2275   if (is_tm_abort (fn_decl))
2276     {
2277       transaction_subcode_ior (region, GTMA_HAVE_ABORT);
2278       return true;
2279     }
2280
2281   /* Instrument the store if needed.
2282
2283      If the assignment happens inside the function call (return slot
2284      optimization), there is no instrumentation to be done, since
2285      the callee should have done the right thing.  */
2286   if (lhs && requires_barrier (region->entry_block, lhs, stmt)
2287       && !gimple_call_return_slot_opt_p (stmt))
2288     {
2289       tree tmp = make_rename_temp (TREE_TYPE (lhs), NULL);
2290       location_t loc = gimple_location (stmt);
2291       edge fallthru_edge = NULL;
2292
2293       /* Remember if the call was going to throw.  */
2294       if (stmt_can_throw_internal (stmt))
2295         {
2296           edge_iterator ei;
2297           edge e;
2298           basic_block bb = gimple_bb (stmt);
2299
2300           FOR_EACH_EDGE (e, ei, bb->succs)
2301             if (e->flags & EDGE_FALLTHRU)
2302               {
2303                 fallthru_edge = e;
2304                 break;
2305               }
2306         }
2307
2308       gimple_call_set_lhs (stmt, tmp);
2309       update_stmt (stmt);
2310       stmt = gimple_build_assign (lhs, tmp);
2311       gimple_set_location (stmt, loc);
2312
2313       /* We cannot throw in the middle of a BB.  If the call was going
2314          to throw, place the instrumentation on the fallthru edge, so
2315          the call remains the last statement in the block.  */
2316       if (fallthru_edge)
2317         {
2318           gimple_seq fallthru_seq = gimple_seq_alloc_with_stmt (stmt);
2319           gimple_stmt_iterator fallthru_gsi = gsi_start (fallthru_seq);
2320           expand_assign_tm (region, &fallthru_gsi);
2321           gsi_insert_seq_on_edge (fallthru_edge, fallthru_seq);
2322           pending_edge_inserts_p = true;
2323         }
2324       else
2325         {
2326           gsi_insert_after (gsi, stmt, GSI_CONTINUE_LINKING);
2327           expand_assign_tm (region, gsi);
2328         }
2329
2330       transaction_subcode_ior (region, GTMA_HAVE_STORE);
2331     }
2332
2333   return retval;
2334 }
2335
2336
2337 /* Expand all statements in BB as appropriate for being inside
2338    a transaction.  */
2339
2340 static void
2341 expand_block_tm (struct tm_region *region, basic_block bb)
2342 {
2343   gimple_stmt_iterator gsi;
2344
2345   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2346     {
2347       gimple stmt = gsi_stmt (gsi);
2348       switch (gimple_code (stmt))
2349         {
2350         case GIMPLE_ASSIGN:
2351           /* Only memory reads/writes need to be instrumented.  */
2352           if (gimple_assign_single_p (stmt)
2353               && !gimple_clobber_p (stmt))
2354             {
2355               expand_assign_tm (region, &gsi);
2356               continue;
2357             }
2358           break;
2359
2360         case GIMPLE_CALL:
2361           if (expand_call_tm (region, &gsi))
2362             return;
2363           break;
2364
2365         case GIMPLE_ASM:
2366           gcc_unreachable ();
2367
2368         default:
2369           break;
2370         }
2371       if (!gsi_end_p (gsi))
2372         gsi_next (&gsi);
2373     }
2374 }
2375
2376 /* Return the list of basic-blocks in REGION.
2377
2378    STOP_AT_IRREVOCABLE_P is true if caller is uninterested in blocks
2379    following a TM_IRREVOCABLE call.  */
2380
2381 static VEC (basic_block, heap) *
2382 get_tm_region_blocks (basic_block entry_block,
2383                       bitmap exit_blocks,
2384                       bitmap irr_blocks,
2385                       bitmap all_region_blocks,
2386                       bool stop_at_irrevocable_p)
2387 {
2388   VEC(basic_block, heap) *bbs = NULL;
2389   unsigned i;
2390   edge e;
2391   edge_iterator ei;
2392   bitmap visited_blocks = BITMAP_ALLOC (NULL);
2393
2394   i = 0;
2395   VEC_safe_push (basic_block, heap, bbs, entry_block);
2396   bitmap_set_bit (visited_blocks, entry_block->index);
2397
2398   do
2399     {
2400       basic_block bb = VEC_index (basic_block, bbs, i++);
2401
2402       if (exit_blocks &&
2403           bitmap_bit_p (exit_blocks, bb->index))
2404         continue;
2405
2406       if (stop_at_irrevocable_p
2407           && irr_blocks
2408           && bitmap_bit_p (irr_blocks, bb->index))
2409         continue;
2410
2411       FOR_EACH_EDGE (e, ei, bb->succs)
2412         if (!bitmap_bit_p (visited_blocks, e->dest->index))
2413           {
2414             bitmap_set_bit (visited_blocks, e->dest->index);
2415             VEC_safe_push (basic_block, heap, bbs, e->dest);
2416           }
2417     }
2418   while (i < VEC_length (basic_block, bbs));
2419
2420   if (all_region_blocks)
2421     bitmap_ior_into (all_region_blocks, visited_blocks);
2422
2423   BITMAP_FREE (visited_blocks);
2424   return bbs;
2425 }
2426
2427 /* Entry point to the MARK phase of TM expansion.  Here we replace
2428    transactional memory statements with calls to builtins, and function
2429    calls with their transactional clones (if available).  But we don't
2430    yet lower GIMPLE_TRANSACTION or add the transaction restart back-edges.  */
2431
2432 static unsigned int
2433 execute_tm_mark (void)
2434 {
2435   struct tm_region *region;
2436   basic_block bb;
2437   VEC (basic_block, heap) *queue;
2438   size_t i;
2439
2440   queue = VEC_alloc (basic_block, heap, 10);
2441   pending_edge_inserts_p = false;
2442
2443   for (region = all_tm_regions; region ; region = region->next)
2444     {
2445       tm_log_init ();
2446       /* If we have a transaction...  */
2447       if (region->exit_blocks)
2448         {
2449           unsigned int subcode
2450             = gimple_transaction_subcode (region->transaction_stmt);
2451
2452           /* Collect a new SUBCODE set, now that optimizations are done...  */
2453           if (subcode & GTMA_DOES_GO_IRREVOCABLE)
2454             subcode &= (GTMA_DECLARATION_MASK | GTMA_DOES_GO_IRREVOCABLE
2455                         | GTMA_MAY_ENTER_IRREVOCABLE);
2456           else
2457             subcode &= GTMA_DECLARATION_MASK;
2458           gimple_transaction_set_subcode (region->transaction_stmt, subcode);
2459         }
2460
2461       queue = get_tm_region_blocks (region->entry_block,
2462                                     region->exit_blocks,
2463                                     region->irr_blocks,
2464                                     NULL,
2465                                     /*stop_at_irr_p=*/true);
2466       for (i = 0; VEC_iterate (basic_block, queue, i, bb); ++i)
2467         expand_block_tm (region, bb);
2468       VEC_free (basic_block, heap, queue);
2469
2470       tm_log_emit ();
2471     }
2472
2473   if (pending_edge_inserts_p)
2474     gsi_commit_edge_inserts ();
2475   return 0;
2476 }
2477
2478 struct gimple_opt_pass pass_tm_mark =
2479 {
2480  {
2481   GIMPLE_PASS,
2482   "tmmark",                             /* name */
2483   NULL,                                 /* gate */
2484   execute_tm_mark,                      /* execute */
2485   NULL,                                 /* sub */
2486   NULL,                                 /* next */
2487   0,                                    /* static_pass_number */
2488   TV_TRANS_MEM,                         /* tv_id */
2489   PROP_ssa | PROP_cfg,                  /* properties_required */
2490   0,                                    /* properties_provided */
2491   0,                                    /* properties_destroyed */
2492   0,                                    /* todo_flags_start */
2493   TODO_update_ssa
2494   | TODO_verify_ssa
2495   | TODO_dump_func,                     /* todo_flags_finish */
2496  }
2497 };
2498 \f
2499 /* Create an abnormal call edge from BB to the first block of the region
2500    represented by STATE.  Also record the edge in the TM_RESTART map.  */
2501
2502 static inline void
2503 make_tm_edge (gimple stmt, basic_block bb, struct tm_region *region)
2504 {
2505   void **slot;
2506   struct tm_restart_node *n, dummy;
2507
2508   if (cfun->gimple_df->tm_restart == NULL)
2509     cfun->gimple_df->tm_restart = htab_create_ggc (31, struct_ptr_hash,
2510                                                    struct_ptr_eq, ggc_free);
2511
2512   dummy.stmt = stmt;
2513   dummy.label_or_list = gimple_block_label (region->entry_block);
2514   slot = htab_find_slot (cfun->gimple_df->tm_restart, &dummy, INSERT);
2515   n = (struct tm_restart_node *) *slot;
2516   if (n == NULL)
2517     {
2518       n = ggc_alloc_tm_restart_node ();
2519       *n = dummy;
2520     }
2521   else
2522     {
2523       tree old = n->label_or_list;
2524       if (TREE_CODE (old) == LABEL_DECL)
2525         old = tree_cons (NULL, old, NULL);
2526       n->label_or_list = tree_cons (NULL, dummy.label_or_list, old);
2527     }
2528
2529   make_edge (bb, region->entry_block, EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
2530 }
2531
2532
2533 /* Split block BB as necessary for every builtin function we added, and
2534    wire up the abnormal back edges implied by the transaction restart.  */
2535
2536 static void
2537 expand_block_edges (struct tm_region *region, basic_block bb)
2538 {
2539   gimple_stmt_iterator gsi;
2540
2541   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2542     {
2543       gimple stmt = gsi_stmt (gsi);
2544
2545       /* ??? TM_COMMIT (and any other tm builtin function) in a nested
2546          transaction has an abnormal edge back to the outer-most transaction
2547          (there are no nested retries), while a TM_ABORT also has an abnormal
2548          backedge to the inner-most transaction.  We haven't actually saved
2549          the inner-most transaction here.  We should be able to get to it
2550          via the region_nr saved on STMT, and read the transaction_stmt from
2551          that, and find the first region block from there.  */
2552       /* ??? Shouldn't we split for any non-pure, non-irrevocable function?  */
2553       if (gimple_code (stmt) == GIMPLE_CALL
2554           && (gimple_call_flags (stmt) & ECF_TM_BUILTIN) != 0)
2555         {
2556           if (gsi_one_before_end_p (gsi))
2557             make_tm_edge (stmt, bb, region);
2558           else
2559             {
2560               edge e = split_block (bb, stmt);
2561               make_tm_edge (stmt, bb, region);
2562               bb = e->dest;
2563               gsi = gsi_start_bb (bb);
2564             }
2565
2566           /* Delete any tail-call annotation that may have been added.
2567              The tail-call pass may have mis-identified the commit as being
2568              a candidate because we had not yet added this restart edge.  */
2569           gimple_call_set_tail (stmt, false);
2570         }
2571
2572       gsi_next (&gsi);
2573     }
2574 }
2575
2576 /* Expand the GIMPLE_TRANSACTION statement into the STM library call.  */
2577
2578 static void
2579 expand_transaction (struct tm_region *region)
2580 {
2581   tree status, tm_start;
2582   basic_block atomic_bb, slice_bb;
2583   gimple_stmt_iterator gsi;
2584   tree t1, t2;
2585   gimple g;
2586   int flags, subcode;
2587
2588   tm_start = builtin_decl_explicit (BUILT_IN_TM_START);
2589   status = make_rename_temp (TREE_TYPE (TREE_TYPE (tm_start)), "tm_state");
2590
2591   /* ??? There are plenty of bits here we're not computing.  */
2592   subcode = gimple_transaction_subcode (region->transaction_stmt);
2593   if (subcode & GTMA_DOES_GO_IRREVOCABLE)
2594     flags = PR_DOESGOIRREVOCABLE | PR_UNINSTRUMENTEDCODE;
2595   else
2596     flags = PR_INSTRUMENTEDCODE;
2597   if ((subcode & GTMA_MAY_ENTER_IRREVOCABLE) == 0)
2598     flags |= PR_HASNOIRREVOCABLE;
2599   /* If the transaction does not have an abort in lexical scope and is not
2600      marked as an outer transaction, then it will never abort.  */
2601   if ((subcode & GTMA_HAVE_ABORT) == 0
2602       && (subcode & GTMA_IS_OUTER) == 0)
2603     flags |= PR_HASNOABORT;
2604   if ((subcode & GTMA_HAVE_STORE) == 0)
2605     flags |= PR_READONLY;
2606   t2 = build_int_cst (TREE_TYPE (status), flags);
2607   g = gimple_build_call (tm_start, 1, t2);
2608   gimple_call_set_lhs (g, status);
2609   gimple_set_location (g, gimple_location (region->transaction_stmt));
2610
2611   atomic_bb = gimple_bb (region->transaction_stmt);
2612
2613   if (!VEC_empty (tree, tm_log_save_addresses))
2614     tm_log_emit_saves (region->entry_block, atomic_bb);
2615
2616   gsi = gsi_last_bb (atomic_bb);
2617   gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2618   gsi_remove (&gsi, true);
2619
2620   if (!VEC_empty (tree, tm_log_save_addresses))
2621     region->entry_block =
2622       tm_log_emit_save_or_restores (region->entry_block,
2623                                     A_RESTORELIVEVARIABLES,
2624                                     status,
2625                                     tm_log_emit_restores,
2626                                     atomic_bb,
2627                                     FALLTHRU_EDGE (atomic_bb),
2628                                     &slice_bb);
2629   else
2630     slice_bb = atomic_bb;
2631
2632   /* If we have an ABORT statement, create a test following the start
2633      call to perform the abort.  */
2634   if (gimple_transaction_label (region->transaction_stmt))
2635     {
2636       edge e;
2637       basic_block test_bb;
2638
2639       test_bb = create_empty_bb (slice_bb);
2640       if (VEC_empty (tree, tm_log_save_addresses))
2641         region->entry_block = test_bb;
2642       gsi = gsi_last_bb (test_bb);
2643
2644       t1 = make_rename_temp (TREE_TYPE (status), NULL);
2645       t2 = build_int_cst (TREE_TYPE (status), A_ABORTTRANSACTION);
2646       g = gimple_build_assign_with_ops (BIT_AND_EXPR, t1, status, t2);
2647       gsi_insert_after (&gsi, g, GSI_CONTINUE_LINKING);
2648
2649       t2 = build_int_cst (TREE_TYPE (status), 0);
2650       g = gimple_build_cond (NE_EXPR, t1, t2, NULL, NULL);
2651       gsi_insert_after (&gsi, g, GSI_CONTINUE_LINKING);
2652
2653       e = FALLTHRU_EDGE (slice_bb);
2654       redirect_edge_pred (e, test_bb);
2655       e->flags = EDGE_FALSE_VALUE;
2656       e->probability = PROB_ALWAYS - PROB_VERY_UNLIKELY;
2657
2658       e = BRANCH_EDGE (atomic_bb);
2659       redirect_edge_pred (e, test_bb);
2660       e->flags = EDGE_TRUE_VALUE;
2661       e->probability = PROB_VERY_UNLIKELY;
2662
2663       e = make_edge (slice_bb, test_bb, EDGE_FALLTHRU);
2664     }
2665
2666   /* If we've no abort, but we do have PHIs at the beginning of the atomic
2667      region, that means we've a loop at the beginning of the atomic region
2668      that shares the first block.  This can cause problems with the abnormal
2669      edges we're about to add for the transaction restart.  Solve this by
2670      adding a new empty block to receive the abnormal edges.  */
2671   else if (phi_nodes (region->entry_block))
2672     {
2673       edge e;
2674       basic_block empty_bb;
2675
2676       region->entry_block = empty_bb = create_empty_bb (atomic_bb);
2677
2678       e = FALLTHRU_EDGE (atomic_bb);
2679       redirect_edge_pred (e, empty_bb);
2680
2681       e = make_edge (atomic_bb, empty_bb, EDGE_FALLTHRU);
2682     }
2683
2684   /* The GIMPLE_TRANSACTION statement no longer exists.  */
2685   region->transaction_stmt = NULL;
2686 }
2687
2688 static void expand_regions (struct tm_region *);
2689
2690 /* Helper function for expand_regions.  Expand REGION and recurse to
2691    the inner region.  */
2692
2693 static void
2694 expand_regions_1 (struct tm_region *region)
2695 {
2696   if (region->exit_blocks)
2697     {
2698       unsigned int i;
2699       basic_block bb;
2700       VEC (basic_block, heap) *queue;
2701
2702       /* Collect the set of blocks in this region.  Do this before
2703          splitting edges, so that we don't have to play with the
2704          dominator tree in the middle.  */
2705       queue = get_tm_region_blocks (region->entry_block,
2706                                     region->exit_blocks,
2707                                     region->irr_blocks,
2708                                     NULL,
2709                                     /*stop_at_irr_p=*/false);
2710       expand_transaction (region);
2711       for (i = 0; VEC_iterate (basic_block, queue, i, bb); ++i)
2712         expand_block_edges (region, bb);
2713       VEC_free (basic_block, heap, queue);
2714     }
2715   if (region->inner)
2716     expand_regions (region->inner);
2717 }
2718
2719 /* Expand regions starting at REGION.  */
2720
2721 static void
2722 expand_regions (struct tm_region *region)
2723 {
2724   while (region)
2725     {
2726       expand_regions_1 (region);
2727       region = region->next;
2728     }
2729 }
2730
2731 /* Entry point to the final expansion of transactional nodes. */
2732
2733 static unsigned int
2734 execute_tm_edges (void)
2735 {
2736   expand_regions (all_tm_regions);
2737   tm_log_delete ();
2738
2739   /* We've got to release the dominance info now, to indicate that it
2740      must be rebuilt completely.  Otherwise we'll crash trying to update
2741      the SSA web in the TODO section following this pass.  */
2742   free_dominance_info (CDI_DOMINATORS);
2743   bitmap_obstack_release (&tm_obstack);
2744   all_tm_regions = NULL;
2745
2746   return 0;
2747 }
2748
2749 struct gimple_opt_pass pass_tm_edges =
2750 {
2751  {
2752   GIMPLE_PASS,
2753   "tmedge",                             /* name */
2754   NULL,                                 /* gate */
2755   execute_tm_edges,                     /* execute */
2756   NULL,                                 /* sub */
2757   NULL,                                 /* next */
2758   0,                                    /* static_pass_number */
2759   TV_TRANS_MEM,                         /* tv_id */
2760   PROP_ssa | PROP_cfg,                  /* properties_required */
2761   0,                                    /* properties_provided */
2762   0,                                    /* properties_destroyed */
2763   0,                                    /* todo_flags_start */
2764   TODO_update_ssa
2765   | TODO_verify_ssa
2766   | TODO_dump_func,                     /* todo_flags_finish */
2767  }
2768 };
2769 \f
2770 /* A unique TM memory operation.  */
2771 typedef struct tm_memop
2772 {
2773   /* Unique ID that all memory operations to the same location have.  */
2774   unsigned int value_id;
2775   /* Address of load/store.  */
2776   tree addr;
2777 } *tm_memop_t;
2778
2779 /* Sets for solving data flow equations in the memory optimization pass.  */
2780 struct tm_memopt_bitmaps
2781 {
2782   /* Stores available to this BB upon entry.  Basically, stores that
2783      dominate this BB.  */
2784   bitmap store_avail_in;
2785   /* Stores available at the end of this BB.  */
2786   bitmap store_avail_out;
2787   bitmap store_antic_in;
2788   bitmap store_antic_out;
2789   /* Reads available to this BB upon entry.  Basically, reads that
2790      dominate this BB.  */
2791   bitmap read_avail_in;
2792   /* Reads available at the end of this BB.  */
2793   bitmap read_avail_out;
2794   /* Reads performed in this BB.  */
2795   bitmap read_local;
2796   /* Writes performed in this BB.  */
2797   bitmap store_local;
2798
2799   /* Temporary storage for pass.  */
2800   /* Is the current BB in the worklist?  */
2801   bool avail_in_worklist_p;
2802   /* Have we visited this BB?  */
2803   bool visited_p;
2804 };
2805
2806 static bitmap_obstack tm_memopt_obstack;
2807
2808 /* Unique counter for TM loads and stores. Loads and stores of the
2809    same address get the same ID.  */
2810 static unsigned int tm_memopt_value_id;
2811 static htab_t tm_memopt_value_numbers;
2812
2813 #define STORE_AVAIL_IN(BB) \
2814   ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_avail_in
2815 #define STORE_AVAIL_OUT(BB) \
2816   ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_avail_out
2817 #define STORE_ANTIC_IN(BB) \
2818   ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_antic_in
2819 #define STORE_ANTIC_OUT(BB) \
2820   ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_antic_out
2821 #define READ_AVAIL_IN(BB) \
2822   ((struct tm_memopt_bitmaps *) ((BB)->aux))->read_avail_in
2823 #define READ_AVAIL_OUT(BB) \
2824   ((struct tm_memopt_bitmaps *) ((BB)->aux))->read_avail_out
2825 #define READ_LOCAL(BB) \
2826   ((struct tm_memopt_bitmaps *) ((BB)->aux))->read_local
2827 #define STORE_LOCAL(BB) \
2828   ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_local
2829 #define AVAIL_IN_WORKLIST_P(BB) \
2830   ((struct tm_memopt_bitmaps *) ((BB)->aux))->avail_in_worklist_p
2831 #define BB_VISITED_P(BB) \
2832   ((struct tm_memopt_bitmaps *) ((BB)->aux))->visited_p
2833
2834 /* Htab support.  Return a hash value for a `tm_memop'.  */
2835 static hashval_t
2836 tm_memop_hash (const void *p)
2837 {
2838   const struct tm_memop *mem = (const struct tm_memop *) p;
2839   tree addr = mem->addr;
2840   /* We drill down to the SSA_NAME/DECL for the hash, but equality is
2841      actually done with operand_equal_p (see tm_memop_eq).  */
2842   if (TREE_CODE (addr) == ADDR_EXPR)
2843     addr = TREE_OPERAND (addr, 0);
2844   return iterative_hash_expr (addr, 0);
2845 }
2846
2847 /* Htab support.  Return true if two tm_memop's are the same.  */
2848 static int
2849 tm_memop_eq (const void *p1, const void *p2)
2850 {
2851   const struct tm_memop *mem1 = (const struct tm_memop *) p1;
2852   const struct tm_memop *mem2 = (const struct tm_memop *) p2;
2853
2854   return operand_equal_p (mem1->addr, mem2->addr, 0);
2855 }
2856
2857 /* Given a TM load/store in STMT, return the value number for the address
2858    it accesses.  */
2859
2860 static unsigned int
2861 tm_memopt_value_number (gimple stmt, enum insert_option op)
2862 {
2863   struct tm_memop tmpmem, *mem;
2864   void **slot;
2865
2866   gcc_assert (is_tm_load (stmt) || is_tm_store (stmt));
2867   tmpmem.addr = gimple_call_arg (stmt, 0);
2868   slot = htab_find_slot (tm_memopt_value_numbers, &tmpmem, op);
2869   if (*slot)
2870     mem = (struct tm_memop *) *slot;
2871   else if (op == INSERT)
2872     {
2873       mem = XNEW (struct tm_memop);
2874       *slot = mem;
2875       mem->value_id = tm_memopt_value_id++;
2876       mem->addr = tmpmem.addr;
2877     }
2878   else
2879     gcc_unreachable ();
2880   return mem->value_id;
2881 }
2882
2883 /* Accumulate TM memory operations in BB into STORE_LOCAL and READ_LOCAL.  */
2884
2885 static void
2886 tm_memopt_accumulate_memops (basic_block bb)
2887 {
2888   gimple_stmt_iterator gsi;
2889
2890   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2891     {
2892       gimple stmt = gsi_stmt (gsi);
2893       bitmap bits;
2894       unsigned int loc;
2895
2896       if (is_tm_store (stmt))
2897         bits = STORE_LOCAL (bb);
2898       else if (is_tm_load (stmt))
2899         bits = READ_LOCAL (bb);
2900       else
2901         continue;
2902
2903       loc = tm_memopt_value_number (stmt, INSERT);
2904       bitmap_set_bit (bits, loc);
2905       if (dump_file)
2906         {
2907           fprintf (dump_file, "TM memopt (%s): value num=%d, BB=%d, addr=",
2908                    is_tm_load (stmt) ? "LOAD" : "STORE", loc,
2909                    gimple_bb (stmt)->index);
2910           print_generic_expr (dump_file, gimple_call_arg (stmt, 0), 0);
2911           fprintf (dump_file, "\n");
2912         }
2913     }
2914 }
2915
2916 /* Prettily dump one of the memopt sets.  BITS is the bitmap to dump.  */
2917
2918 static void
2919 dump_tm_memopt_set (const char *set_name, bitmap bits)
2920 {
2921   unsigned i;
2922   bitmap_iterator bi;
2923   const char *comma = "";
2924
2925   fprintf (dump_file, "TM memopt: %s: [", set_name);
2926   EXECUTE_IF_SET_IN_BITMAP (bits, 0, i, bi)
2927     {
2928       htab_iterator hi;
2929       struct tm_memop *mem;
2930
2931       /* Yeah, yeah, yeah.  Whatever.  This is just for debugging.  */
2932       FOR_EACH_HTAB_ELEMENT (tm_memopt_value_numbers, mem, tm_memop_t, hi)
2933         if (mem->value_id == i)
2934           break;
2935       gcc_assert (mem->value_id == i);
2936       fprintf (dump_file, "%s", comma);
2937       comma = ", ";
2938       print_generic_expr (dump_file, mem->addr, 0);
2939     }
2940   fprintf (dump_file, "]\n");
2941 }
2942
2943 /* Prettily dump all of the memopt sets in BLOCKS.  */
2944
2945 static void
2946 dump_tm_memopt_sets (VEC (basic_block, heap) *blocks)
2947 {
2948   size_t i;
2949   basic_block bb;
2950
2951   for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
2952     {
2953       fprintf (dump_file, "------------BB %d---------\n", bb->index);
2954       dump_tm_memopt_set ("STORE_LOCAL", STORE_LOCAL (bb));
2955       dump_tm_memopt_set ("READ_LOCAL", READ_LOCAL (bb));
2956       dump_tm_memopt_set ("STORE_AVAIL_IN", STORE_AVAIL_IN (bb));
2957       dump_tm_memopt_set ("STORE_AVAIL_OUT", STORE_AVAIL_OUT (bb));
2958       dump_tm_memopt_set ("READ_AVAIL_IN", READ_AVAIL_IN (bb));
2959       dump_tm_memopt_set ("READ_AVAIL_OUT", READ_AVAIL_OUT (bb));
2960     }
2961 }
2962
2963 /* Compute {STORE,READ}_AVAIL_IN for the basic block BB.  */
2964
2965 static void
2966 tm_memopt_compute_avin (basic_block bb)
2967 {
2968   edge e;
2969   unsigned ix;
2970
2971   /* Seed with the AVOUT of any predecessor.  */
2972   for (ix = 0; ix < EDGE_COUNT (bb->preds); ix++)
2973     {
2974       e = EDGE_PRED (bb, ix);
2975       /* Make sure we have already visited this BB, and is thus
2976          initialized.
2977
2978           If e->src->aux is NULL, this predecessor is actually on an
2979           enclosing transaction.  We only care about the current
2980           transaction, so ignore it.  */
2981       if (e->src->aux && BB_VISITED_P (e->src))
2982         {
2983           bitmap_copy (STORE_AVAIL_IN (bb), STORE_AVAIL_OUT (e->src));
2984           bitmap_copy (READ_AVAIL_IN (bb), READ_AVAIL_OUT (e->src));
2985           break;
2986         }
2987     }
2988
2989   for (; ix < EDGE_COUNT (bb->preds); ix++)
2990     {
2991       e = EDGE_PRED (bb, ix);
2992       if (e->src->aux && BB_VISITED_P (e->src))
2993         {
2994           bitmap_and_into (STORE_AVAIL_IN (bb), STORE_AVAIL_OUT (e->src));
2995           bitmap_and_into (READ_AVAIL_IN (bb), READ_AVAIL_OUT (e->src));
2996         }
2997     }
2998
2999   BB_VISITED_P (bb) = true;
3000 }
3001
3002 /* Compute the STORE_ANTIC_IN for the basic block BB.  */
3003
3004 static void
3005 tm_memopt_compute_antin (basic_block bb)
3006 {
3007   edge e;
3008   unsigned ix;
3009
3010   /* Seed with the ANTIC_OUT of any successor.  */
3011   for (ix = 0; ix < EDGE_COUNT (bb->succs); ix++)
3012     {
3013       e = EDGE_SUCC (bb, ix);
3014       /* Make sure we have already visited this BB, and is thus
3015          initialized.  */
3016       if (BB_VISITED_P (e->dest))
3017         {
3018           bitmap_copy (STORE_ANTIC_IN (bb), STORE_ANTIC_OUT (e->dest));
3019           break;
3020         }
3021     }
3022
3023   for (; ix < EDGE_COUNT (bb->succs); ix++)
3024     {
3025       e = EDGE_SUCC (bb, ix);
3026       if (BB_VISITED_P  (e->dest))
3027         bitmap_and_into (STORE_ANTIC_IN (bb), STORE_ANTIC_OUT (e->dest));
3028     }
3029
3030   BB_VISITED_P (bb) = true;
3031 }
3032
3033 /* Compute the AVAIL sets for every basic block in BLOCKS.
3034
3035    We compute {STORE,READ}_AVAIL_{OUT,IN} as follows:
3036
3037      AVAIL_OUT[bb] = union (AVAIL_IN[bb], LOCAL[bb])
3038      AVAIL_IN[bb]  = intersect (AVAIL_OUT[predecessors])
3039
3040    This is basically what we do in lcm's compute_available(), but here
3041    we calculate two sets of sets (one for STOREs and one for READs),
3042    and we work on a region instead of the entire CFG.
3043
3044    REGION is the TM region.
3045    BLOCKS are the basic blocks in the region.  */
3046
3047 static void
3048 tm_memopt_compute_available (struct tm_region *region,
3049                              VEC (basic_block, heap) *blocks)
3050 {
3051   edge e;
3052   basic_block *worklist, *qin, *qout, *qend, bb;
3053   unsigned int qlen, i;
3054   edge_iterator ei;
3055   bool changed;
3056
3057   /* Allocate a worklist array/queue.  Entries are only added to the
3058      list if they were not already on the list.  So the size is
3059      bounded by the number of basic blocks in the region.  */
3060   qlen = VEC_length (basic_block, blocks) - 1;
3061   qin = qout = worklist =
3062     XNEWVEC (basic_block, qlen);
3063
3064   /* Put every block in the region on the worklist.  */
3065   for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
3066     {
3067       /* Seed AVAIL_OUT with the LOCAL set.  */
3068       bitmap_ior_into (STORE_AVAIL_OUT (bb), STORE_LOCAL (bb));
3069       bitmap_ior_into (READ_AVAIL_OUT (bb), READ_LOCAL (bb));
3070
3071       AVAIL_IN_WORKLIST_P (bb) = true;
3072       /* No need to insert the entry block, since it has an AVIN of
3073          null, and an AVOUT that has already been seeded in.  */
3074       if (bb != region->entry_block)
3075         *qin++ = bb;
3076     }
3077
3078   /* The entry block has been initialized with the local sets.  */
3079   BB_VISITED_P (region->entry_block) = true;
3080
3081   qin = worklist;
3082   qend = &worklist[qlen];
3083
3084   /* Iterate until the worklist is empty.  */
3085   while (qlen)
3086     {
3087       /* Take the first entry off the worklist.  */
3088       bb = *qout++;
3089       qlen--;
3090
3091       if (qout >= qend)
3092         qout = worklist;
3093
3094       /* This block can be added to the worklist again if necessary.  */
3095       AVAIL_IN_WORKLIST_P (bb) = false;
3096       tm_memopt_compute_avin (bb);
3097
3098       /* Note: We do not add the LOCAL sets here because we already
3099          seeded the AVAIL_OUT sets with them.  */
3100       changed  = bitmap_ior_into (STORE_AVAIL_OUT (bb), STORE_AVAIL_IN (bb));
3101       changed |= bitmap_ior_into (READ_AVAIL_OUT (bb), READ_AVAIL_IN (bb));
3102       if (changed
3103           && (region->exit_blocks == NULL
3104               || !bitmap_bit_p (region->exit_blocks, bb->index)))
3105         /* If the out state of this block changed, then we need to add
3106            its successors to the worklist if they are not already in.  */
3107         FOR_EACH_EDGE (e, ei, bb->succs)
3108           if (!AVAIL_IN_WORKLIST_P (e->dest) && e->dest != EXIT_BLOCK_PTR)
3109             {
3110               *qin++ = e->dest;
3111               AVAIL_IN_WORKLIST_P (e->dest) = true;
3112               qlen++;
3113
3114               if (qin >= qend)
3115                 qin = worklist;
3116             }
3117     }
3118
3119   free (worklist);
3120
3121   if (dump_file)
3122     dump_tm_memopt_sets (blocks);
3123 }
3124
3125 /* Compute ANTIC sets for every basic block in BLOCKS.
3126
3127    We compute STORE_ANTIC_OUT as follows:
3128
3129         STORE_ANTIC_OUT[bb] = union(STORE_ANTIC_IN[bb], STORE_LOCAL[bb])
3130         STORE_ANTIC_IN[bb]  = intersect(STORE_ANTIC_OUT[successors])
3131
3132    REGION is the TM region.
3133    BLOCKS are the basic blocks in the region.  */
3134
3135 static void
3136 tm_memopt_compute_antic (struct tm_region *region,
3137                          VEC (basic_block, heap) *blocks)
3138 {
3139   edge e;
3140   basic_block *worklist, *qin, *qout, *qend, bb;
3141   unsigned int qlen;
3142   int i;
3143   edge_iterator ei;
3144
3145   /* Allocate a worklist array/queue.  Entries are only added to the
3146      list if they were not already on the list.  So the size is
3147      bounded by the number of basic blocks in the region.  */
3148   qin = qout = worklist =
3149     XNEWVEC (basic_block, VEC_length (basic_block, blocks));
3150
3151   for (qlen = 0, i = VEC_length (basic_block, blocks) - 1; i >= 0; --i)
3152     {
3153       bb = VEC_index (basic_block, blocks, i);
3154
3155       /* Seed ANTIC_OUT with the LOCAL set.  */
3156       bitmap_ior_into (STORE_ANTIC_OUT (bb), STORE_LOCAL (bb));
3157
3158       /* Put every block in the region on the worklist.  */
3159       AVAIL_IN_WORKLIST_P (bb) = true;
3160       /* No need to insert exit blocks, since their ANTIC_IN is NULL,
3161          and their ANTIC_OUT has already been seeded in.  */
3162       if (region->exit_blocks
3163           && !bitmap_bit_p (region->exit_blocks, bb->index))
3164         {
3165           qlen++;
3166           *qin++ = bb;
3167         }
3168     }
3169
3170   /* The exit blocks have been initialized with the local sets.  */
3171   if (region->exit_blocks)
3172     {
3173       unsigned int i;
3174       bitmap_iterator bi;
3175       EXECUTE_IF_SET_IN_BITMAP (region->exit_blocks, 0, i, bi)
3176         BB_VISITED_P (BASIC_BLOCK (i)) = true;
3177     }
3178
3179   qin = worklist;
3180   qend = &worklist[qlen];
3181
3182   /* Iterate until the worklist is empty.  */
3183   while (qlen)
3184     {
3185       /* Take the first entry off the worklist.  */
3186       bb = *qout++;
3187       qlen--;
3188
3189       if (qout >= qend)
3190         qout = worklist;
3191
3192       /* This block can be added to the worklist again if necessary.  */
3193       AVAIL_IN_WORKLIST_P (bb) = false;
3194       tm_memopt_compute_antin (bb);
3195
3196       /* Note: We do not add the LOCAL sets here because we already
3197          seeded the ANTIC_OUT sets with them.  */
3198       if (bitmap_ior_into (STORE_ANTIC_OUT (bb), STORE_ANTIC_IN (bb))
3199           && bb != region->entry_block)
3200         /* If the out state of this block changed, then we need to add
3201            its predecessors to the worklist if they are not already in.  */
3202         FOR_EACH_EDGE (e, ei, bb->preds)
3203           if (!AVAIL_IN_WORKLIST_P (e->src))
3204             {
3205               *qin++ = e->src;
3206               AVAIL_IN_WORKLIST_P (e->src) = true;
3207               qlen++;
3208
3209               if (qin >= qend)
3210                 qin = worklist;
3211             }
3212     }
3213
3214   free (worklist);
3215
3216   if (dump_file)
3217     dump_tm_memopt_sets (blocks);
3218 }
3219
3220 /* Offsets of load variants from TM_LOAD.  For example,
3221    BUILT_IN_TM_LOAD_RAR* is an offset of 1 from BUILT_IN_TM_LOAD*.
3222    See gtm-builtins.def.  */
3223 #define TRANSFORM_RAR 1
3224 #define TRANSFORM_RAW 2
3225 #define TRANSFORM_RFW 3
3226 /* Offsets of store variants from TM_STORE.  */
3227 #define TRANSFORM_WAR 1
3228 #define TRANSFORM_WAW 2
3229
3230 /* Inform about a load/store optimization.  */
3231
3232 static void
3233 dump_tm_memopt_transform (gimple stmt)
3234 {
3235   if (dump_file)
3236     {
3237       fprintf (dump_file, "TM memopt: transforming: ");
3238       print_gimple_stmt (dump_file, stmt, 0, 0);
3239       fprintf (dump_file, "\n");
3240     }
3241 }
3242
3243 /* Perform a read/write optimization.  Replaces the TM builtin in STMT
3244    by a builtin that is OFFSET entries down in the builtins table in
3245    gtm-builtins.def.  */
3246
3247 static void
3248 tm_memopt_transform_stmt (unsigned int offset,
3249                           gimple stmt,
3250                           gimple_stmt_iterator *gsi)
3251 {
3252   tree fn = gimple_call_fn (stmt);
3253   gcc_assert (TREE_CODE (fn) == ADDR_EXPR);
3254   TREE_OPERAND (fn, 0)
3255     = builtin_decl_explicit ((enum built_in_function)
3256                              (DECL_FUNCTION_CODE (TREE_OPERAND (fn, 0))
3257                               + offset));
3258   gimple_call_set_fn (stmt, fn);
3259   gsi_replace (gsi, stmt, true);
3260   dump_tm_memopt_transform (stmt);
3261 }
3262
3263 /* Perform the actual TM memory optimization transformations in the
3264    basic blocks in BLOCKS.  */
3265
3266 static void
3267 tm_memopt_transform_blocks (VEC (basic_block, heap) *blocks)
3268 {
3269   size_t i;
3270   basic_block bb;
3271   gimple_stmt_iterator gsi;
3272
3273   for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
3274     {
3275       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3276         {
3277           gimple stmt = gsi_stmt (gsi);
3278           bitmap read_avail = READ_AVAIL_IN (bb);
3279           bitmap store_avail = STORE_AVAIL_IN (bb);
3280           bitmap store_antic = STORE_ANTIC_OUT (bb);
3281           unsigned int loc;
3282
3283           if (is_tm_simple_load (stmt))
3284             {
3285               loc = tm_memopt_value_number (stmt, NO_INSERT);
3286               if (store_avail && bitmap_bit_p (store_avail, loc))
3287                 tm_memopt_transform_stmt (TRANSFORM_RAW, stmt, &gsi);
3288               else if (store_antic && bitmap_bit_p (store_antic, loc))
3289                 {
3290                   tm_memopt_transform_stmt (TRANSFORM_RFW, stmt, &gsi);
3291                   bitmap_set_bit (store_avail, loc);
3292                 }
3293               else if (read_avail && bitmap_bit_p (read_avail, loc))
3294                 tm_memopt_transform_stmt (TRANSFORM_RAR, stmt, &gsi);
3295               else
3296                 bitmap_set_bit (read_avail, loc);
3297             }
3298           else if (is_tm_simple_store (stmt))
3299             {
3300               loc = tm_memopt_value_number (stmt, NO_INSERT);
3301               if (store_avail && bitmap_bit_p (store_avail, loc))
3302                 tm_memopt_transform_stmt (TRANSFORM_WAW, stmt, &gsi);
3303               else
3304                 {
3305                   if (read_avail && bitmap_bit_p (read_avail, loc))
3306                     tm_memopt_transform_stmt (TRANSFORM_WAR, stmt, &gsi);
3307                   bitmap_set_bit (store_avail, loc);
3308                 }
3309             }
3310         }
3311     }
3312 }
3313
3314 /* Return a new set of bitmaps for a BB.  */
3315
3316 static struct tm_memopt_bitmaps *
3317 tm_memopt_init_sets (void)
3318 {
3319   struct tm_memopt_bitmaps *b
3320     = XOBNEW (&tm_memopt_obstack.obstack, struct tm_memopt_bitmaps);
3321   b->store_avail_in = BITMAP_ALLOC (&tm_memopt_obstack);
3322   b->store_avail_out = BITMAP_ALLOC (&tm_memopt_obstack);
3323   b->store_antic_in = BITMAP_ALLOC (&tm_memopt_obstack);
3324   b->store_antic_out = BITMAP_ALLOC (&tm_memopt_obstack);
3325   b->store_avail_out = BITMAP_ALLOC (&tm_memopt_obstack);
3326   b->read_avail_in = BITMAP_ALLOC (&tm_memopt_obstack);
3327   b->read_avail_out = BITMAP_ALLOC (&tm_memopt_obstack);
3328   b->read_local = BITMAP_ALLOC (&tm_memopt_obstack);
3329   b->store_local = BITMAP_ALLOC (&tm_memopt_obstack);
3330   return b;
3331 }
3332
3333 /* Free sets computed for each BB.  */
3334
3335 static void
3336 tm_memopt_free_sets (VEC (basic_block, heap) *blocks)
3337 {
3338   size_t i;
3339   basic_block bb;
3340
3341   for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
3342     bb->aux = NULL;
3343 }
3344
3345 /* Clear the visited bit for every basic block in BLOCKS.  */
3346
3347 static void
3348 tm_memopt_clear_visited (VEC (basic_block, heap) *blocks)
3349 {
3350   size_t i;
3351   basic_block bb;
3352
3353   for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
3354     BB_VISITED_P (bb) = false;
3355 }
3356
3357 /* Replace TM load/stores with hints for the runtime.  We handle
3358    things like read-after-write, write-after-read, read-after-read,
3359    read-for-write, etc.  */
3360
3361 static unsigned int
3362 execute_tm_memopt (void)
3363 {
3364   struct tm_region *region;
3365   VEC (basic_block, heap) *bbs;
3366
3367   tm_memopt_value_id = 0;
3368   tm_memopt_value_numbers = htab_create (10, tm_memop_hash, tm_memop_eq, free);
3369
3370   for (region = all_tm_regions; region; region = region->next)
3371     {
3372       /* All the TM stores/loads in the current region.  */
3373       size_t i;
3374       basic_block bb;
3375
3376       bitmap_obstack_initialize (&tm_memopt_obstack);
3377
3378       /* Save all BBs for the current region.  */
3379       bbs = get_tm_region_blocks (region->entry_block,
3380                                   region->exit_blocks,
3381                                   region->irr_blocks,
3382                                   NULL,
3383                                   false);
3384
3385       /* Collect all the memory operations.  */
3386       for (i = 0; VEC_iterate (basic_block, bbs, i, bb); ++i)
3387         {
3388           bb->aux = tm_memopt_init_sets ();
3389           tm_memopt_accumulate_memops (bb);
3390         }
3391
3392       /* Solve data flow equations and transform each block accordingly.  */
3393       tm_memopt_clear_visited (bbs);
3394       tm_memopt_compute_available (region, bbs);
3395       tm_memopt_clear_visited (bbs);
3396       tm_memopt_compute_antic (region, bbs);
3397       tm_memopt_transform_blocks (bbs);
3398
3399       tm_memopt_free_sets (bbs);
3400       VEC_free (basic_block, heap, bbs);
3401       bitmap_obstack_release (&tm_memopt_obstack);
3402       htab_empty (tm_memopt_value_numbers);
3403     }
3404
3405   htab_delete (tm_memopt_value_numbers);
3406   return 0;
3407 }
3408
3409 static bool
3410 gate_tm_memopt (void)
3411 {
3412   return flag_tm && optimize > 0;
3413 }
3414
3415 struct gimple_opt_pass pass_tm_memopt =
3416 {
3417  {
3418   GIMPLE_PASS,
3419   "tmmemopt",                           /* name */
3420   gate_tm_memopt,                       /* gate */
3421   execute_tm_memopt,                    /* execute */
3422   NULL,                                 /* sub */
3423   NULL,                                 /* next */
3424   0,                                    /* static_pass_number */
3425   TV_TRANS_MEM,                         /* tv_id */
3426   PROP_ssa | PROP_cfg,                  /* properties_required */
3427   0,                                    /* properties_provided */
3428   0,                                    /* properties_destroyed */
3429   0,                                    /* todo_flags_start */
3430   TODO_dump_func,                       /* todo_flags_finish */
3431  }
3432 };
3433
3434 \f
3435 /* Interprocedual analysis for the creation of transactional clones.
3436    The aim of this pass is to find which functions are referenced in
3437    a non-irrevocable transaction context, and for those over which
3438    we have control (or user directive), create a version of the
3439    function which uses only the transactional interface to reference
3440    protected memories.  This analysis proceeds in several steps:
3441
3442      (1) Collect the set of all possible transactional clones:
3443
3444         (a) For all local public functions marked tm_callable, push
3445             it onto the tm_callee queue.
3446
3447         (b) For all local functions, scan for calls in transaction blocks.
3448             Push the caller and callee onto the tm_caller and tm_callee
3449             queues.  Count the number of callers for each callee.
3450
3451         (c) For each local function on the callee list, assume we will
3452             create a transactional clone.  Push *all* calls onto the
3453             callee queues; count the number of clone callers separately
3454             to the number of original callers.
3455
3456      (2) Propagate irrevocable status up the dominator tree:
3457
3458         (a) Any external function on the callee list that is not marked
3459             tm_callable is irrevocable.  Push all callers of such onto
3460             a worklist.
3461
3462         (b) For each function on the worklist, mark each block that
3463             contains an irrevocable call.  Use the AND operator to
3464             propagate that mark up the dominator tree.
3465
3466         (c) If we reach the entry block for a possible transactional
3467             clone, then the transactional clone is irrevocable, and
3468             we should not create the clone after all.  Push all
3469             callers onto the worklist.
3470
3471         (d) Place tm_irrevocable calls at the beginning of the relevant
3472             blocks.  Special case here is the entry block for the entire
3473             transaction region; there we mark it GTMA_DOES_GO_IRREVOCABLE for
3474             the library to begin the region in serial mode.  Decrement
3475             the call count for all callees in the irrevocable region.
3476
3477      (3) Create the transactional clones:
3478
3479         Any tm_callee that still has a non-zero call count is cloned.
3480 */
3481
3482 /* This structure is stored in the AUX field of each cgraph_node.  */
3483 struct tm_ipa_cg_data
3484 {
3485   /* The clone of the function that got created.  */
3486   struct cgraph_node *clone;
3487
3488   /* The tm regions in the normal function.  */
3489   struct tm_region *all_tm_regions;
3490
3491   /* The blocks of the normal/clone functions that contain irrevocable
3492      calls, or blocks that are post-dominated by irrevocable calls.  */
3493   bitmap irrevocable_blocks_normal;
3494   bitmap irrevocable_blocks_clone;
3495
3496   /* The blocks of the normal function that are involved in transactions.  */
3497   bitmap transaction_blocks_normal;
3498
3499   /* The number of callers to the transactional clone of this function
3500      from normal and transactional clones respectively.  */
3501   unsigned tm_callers_normal;
3502   unsigned tm_callers_clone;
3503
3504   /* True if all calls to this function's transactional clone
3505      are irrevocable.  Also automatically true if the function
3506      has no transactional clone.  */
3507   bool is_irrevocable;
3508
3509   /* Flags indicating the presence of this function in various queues.  */
3510   bool in_callee_queue;
3511   bool in_worklist;
3512
3513   /* Flags indicating the kind of scan desired while in the worklist.  */
3514   bool want_irr_scan_normal;
3515 };
3516
3517 typedef struct cgraph_node *cgraph_node_p;
3518
3519 DEF_VEC_P (cgraph_node_p);
3520 DEF_VEC_ALLOC_P (cgraph_node_p, heap);
3521
3522 typedef VEC (cgraph_node_p, heap) *cgraph_node_queue;
3523
3524 /* Return the ipa data associated with NODE, allocating zeroed memory
3525    if necessary.  */
3526
3527 static struct tm_ipa_cg_data *
3528 get_cg_data (struct cgraph_node *node)
3529 {
3530   struct tm_ipa_cg_data *d = (struct tm_ipa_cg_data *) node->aux;
3531
3532   if (d == NULL)
3533     {
3534       d = (struct tm_ipa_cg_data *)
3535         obstack_alloc (&tm_obstack.obstack, sizeof (*d));
3536       node->aux = (void *) d;
3537       memset (d, 0, sizeof (*d));
3538     }
3539
3540   return d;
3541 }
3542
3543 /* Add NODE to the end of QUEUE, unless IN_QUEUE_P indicates that
3544    it is already present.  */
3545
3546 static void
3547 maybe_push_queue (struct cgraph_node *node,
3548                   cgraph_node_queue *queue_p, bool *in_queue_p)
3549 {
3550   if (!*in_queue_p)
3551     {
3552       *in_queue_p = true;
3553       VEC_safe_push (cgraph_node_p, heap, *queue_p, node);
3554     }
3555 }
3556
3557 /* A subroutine of ipa_tm_scan_calls_transaction and ipa_tm_scan_calls_clone.
3558    Queue all callees within block BB.  */
3559
3560 static void
3561 ipa_tm_scan_calls_block (cgraph_node_queue *callees_p,
3562                          basic_block bb, bool for_clone)
3563 {
3564   gimple_stmt_iterator gsi;
3565
3566   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3567     {
3568       gimple stmt = gsi_stmt (gsi);
3569       if (is_gimple_call (stmt) && !is_tm_pure_call (stmt))
3570         {
3571           tree fndecl = gimple_call_fndecl (stmt);
3572           if (fndecl)
3573             {
3574               struct tm_ipa_cg_data *d;
3575               unsigned *pcallers;
3576               struct cgraph_node *node;
3577
3578               if (is_tm_ending_fndecl (fndecl))
3579                 continue;