OSDN Git Service

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