OSDN Git Service

c32aee6d338be4b930a778b9c51ca8f610fdae6b
[pf3gnuchains/gcc-fork.git] / gcc / trans-mem.c
1 /* Passes for transactional memory support.
2    Copyright (C) 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
3
4    This file is part of GCC.
5
6    GCC is free software; you can redistribute it and/or modify it under
7    the terms of the GNU General Public License as published by the Free
8    Software Foundation; either version 3, or (at your option) any later
9    version.
10
11    GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12    WARRANTY; without even the implied warranty of MERCHANTABILITY or
13    FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14    for more details.
15
16    You should have received a copy of the GNU General Public License
17    along with GCC; see the file COPYING3.  If not see
18    <http://www.gnu.org/licenses/>.  */
19
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tree.h"
24 #include "gimple.h"
25 #include "tree-flow.h"
26 #include "tree-pass.h"
27 #include "tree-inline.h"
28 #include "diagnostic-core.h"
29 #include "demangle.h"
30 #include "output.h"
31 #include "trans-mem.h"
32 #include "params.h"
33 #include "target.h"
34 #include "langhooks.h"
35 #include "tree-pretty-print.h"
36 #include "gimple-pretty-print.h"
37
38
39 #define PROB_VERY_UNLIKELY      (REG_BR_PROB_BASE / 2000 - 1)
40 #define PROB_ALWAYS             (REG_BR_PROB_BASE)
41
42 #define A_RUNINSTRUMENTEDCODE   0x0001
43 #define A_RUNUNINSTRUMENTEDCODE 0x0002
44 #define A_SAVELIVEVARIABLES     0x0004
45 #define A_RESTORELIVEVARIABLES  0x0008
46 #define A_ABORTTRANSACTION      0x0010
47
48 #define AR_USERABORT            0x0001
49 #define AR_USERRETRY            0x0002
50 #define AR_TMCONFLICT           0x0004
51 #define AR_EXCEPTIONBLOCKABORT  0x0008
52 #define AR_OUTERABORT           0x0010
53
54 #define MODE_SERIALIRREVOCABLE  0x0000
55
56
57 /* The representation of a transaction changes several times during the
58    lowering process.  In the beginning, in the front-end we have the
59    GENERIC tree TRANSACTION_EXPR.  For example,
60
61         __transaction {
62           local++;
63           if (++global == 10)
64             __tm_abort;
65         }
66
67   During initial gimplification (gimplify.c) the TRANSACTION_EXPR node is
68   trivially replaced with a GIMPLE_TRANSACTION node.
69
70   During pass_lower_tm, we examine the body of transactions looking
71   for aborts.  Transactions that do not contain an abort may be
72   merged into an outer transaction.  We also add a TRY-FINALLY node
73   to arrange for the transaction to be committed on any exit.
74
75   [??? Think about how this arrangement affects throw-with-commit
76   and throw-with-abort operations.  In this case we want the TRY to
77   handle gotos, but not to catch any exceptions because the transaction
78   will already be closed.]
79
80         GIMPLE_TRANSACTION [label=NULL] {
81           try {
82             local = local + 1;
83             t0 = global;
84             t1 = t0 + 1;
85             global = t1;
86             if (t1 == 10)
87               __builtin___tm_abort ();
88           } finally {
89             __builtin___tm_commit ();
90           }
91         }
92
93   During pass_lower_eh, we create EH regions for the transactions,
94   intermixed with the regular EH stuff.  This gives us a nice persistent
95   mapping (all the way through rtl) from transactional memory operation
96   back to the transaction, which allows us to get the abnormal edges
97   correct to model transaction aborts and restarts:
98
99         GIMPLE_TRANSACTION [label=over]
100         local = local + 1;
101         t0 = global;
102         t1 = t0 + 1;
103         global = t1;
104         if (t1 == 10)
105           __builtin___tm_abort ();
106         __builtin___tm_commit ();
107         over:
108
109   This is the end of all_lowering_passes, and so is what is present
110   during the IPA passes, and through all of the optimization passes.
111
112   During pass_ipa_tm, we examine all GIMPLE_TRANSACTION blocks in all
113   functions and mark functions for cloning.
114
115   At the end of gimple optimization, before exiting SSA form,
116   pass_tm_edges replaces statements that perform transactional
117   memory operations with the appropriate TM builtins, and swap
118   out function calls with their transactional clones.  At this
119   point we introduce the abnormal transaction restart edges and
120   complete lowering of the GIMPLE_TRANSACTION node.
121
122         x = __builtin___tm_start (MAY_ABORT);
123         eh_label:
124         if (x & abort_transaction)
125           goto over;
126         local = local + 1;
127         t0 = __builtin___tm_load (global);
128         t1 = t0 + 1;
129         __builtin___tm_store (&global, t1);
130         if (t1 == 10)
131           __builtin___tm_abort ();
132         __builtin___tm_commit ();
133         over:
134 */
135
136 \f
137 /* Return the attributes we want to examine for X, or NULL if it's not
138    something we examine.  We look at function types, but allow pointers
139    to function types and function decls and peek through.  */
140
141 static tree
142 get_attrs_for (const_tree x)
143 {
144   switch (TREE_CODE (x))
145     {
146     case FUNCTION_DECL:
147       return TYPE_ATTRIBUTES (TREE_TYPE (x));
148       break;
149
150     default:
151       if (TYPE_P (x))
152         return NULL;
153       x = TREE_TYPE (x);
154       if (TREE_CODE (x) != POINTER_TYPE)
155         return NULL;
156       /* FALLTHRU */
157
158     case POINTER_TYPE:
159       x = TREE_TYPE (x);
160       if (TREE_CODE (x) != FUNCTION_TYPE && TREE_CODE (x) != METHOD_TYPE)
161         return NULL;
162       /* FALLTHRU */
163
164     case FUNCTION_TYPE:
165     case METHOD_TYPE:
166       return TYPE_ATTRIBUTES (x);
167     }
168 }
169
170 /* Return true if X has been marked TM_PURE.  */
171
172 bool
173 is_tm_pure (const_tree x)
174 {
175   unsigned flags;
176
177   switch (TREE_CODE (x))
178     {
179     case FUNCTION_DECL:
180     case FUNCTION_TYPE:
181     case METHOD_TYPE:
182       break;
183
184     default:
185       if (TYPE_P (x))
186         return false;
187       x = TREE_TYPE (x);
188       if (TREE_CODE (x) != POINTER_TYPE)
189         return false;
190       /* FALLTHRU */
191
192     case POINTER_TYPE:
193       x = TREE_TYPE (x);
194       if (TREE_CODE (x) != FUNCTION_TYPE && TREE_CODE (x) != METHOD_TYPE)
195         return false;
196       break;
197     }
198
199   flags = flags_from_decl_or_type (x);
200   return (flags & ECF_TM_PURE) != 0;
201 }
202
203 /* Return true if X has been marked TM_IRREVOCABLE.  */
204
205 static bool
206 is_tm_irrevocable (tree x)
207 {
208   tree attrs = get_attrs_for (x);
209
210   if (attrs && lookup_attribute ("transaction_unsafe", attrs))
211     return true;
212
213   /* A call to the irrevocable builtin is by definition,
214      irrevocable.  */
215   if (TREE_CODE (x) == ADDR_EXPR)
216     x = TREE_OPERAND (x, 0);
217   if (TREE_CODE (x) == FUNCTION_DECL
218       && DECL_BUILT_IN_CLASS (x) == BUILT_IN_NORMAL
219       && DECL_FUNCTION_CODE (x) == BUILT_IN_TM_IRREVOCABLE)
220     return true;
221
222   return false;
223 }
224
225 /* Return true if X has been marked TM_SAFE.  */
226
227 bool
228 is_tm_safe (const_tree x)
229 {
230   if (flag_tm)
231     {
232       tree attrs = get_attrs_for (x);
233       if (attrs)
234         {
235           if (lookup_attribute ("transaction_safe", attrs))
236             return true;
237           if (lookup_attribute ("transaction_may_cancel_outer", attrs))
238             return true;
239         }
240     }
241   return false;
242 }
243
244 /* Return true if CALL is const, or tm_pure.  */
245
246 static bool
247 is_tm_pure_call (gimple call)
248 {
249   tree fn = gimple_call_fn (call);
250
251   if (TREE_CODE (fn) == ADDR_EXPR)
252     {
253       fn = TREE_OPERAND (fn, 0);
254       gcc_assert (TREE_CODE (fn) == FUNCTION_DECL);
255     }
256   else
257     fn = TREE_TYPE (fn);
258
259   return is_tm_pure (fn);
260 }
261
262 /* Return true if X has been marked TM_CALLABLE.  */
263
264 static bool
265 is_tm_callable (tree x)
266 {
267   tree attrs = get_attrs_for (x);
268   if (attrs)
269     {
270       if (lookup_attribute ("transaction_callable", attrs))
271         return true;
272       if (lookup_attribute ("transaction_safe", attrs))
273         return true;
274       if (lookup_attribute ("transaction_may_cancel_outer", attrs))
275         return true;
276     }
277   return false;
278 }
279
280 /* Return true if X has been marked TRANSACTION_MAY_CANCEL_OUTER.  */
281
282 bool
283 is_tm_may_cancel_outer (tree x)
284 {
285   tree attrs = get_attrs_for (x);
286   if (attrs)
287     return lookup_attribute ("transaction_may_cancel_outer", attrs) != NULL;
288   return false;
289 }
290
291 /* Return true for built in functions that "end" a transaction.   */
292
293 bool
294 is_tm_ending_fndecl (tree fndecl)
295 {
296   if (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
297     switch (DECL_FUNCTION_CODE (fndecl))
298       {
299       case BUILT_IN_TM_COMMIT:
300       case BUILT_IN_TM_COMMIT_EH:
301       case BUILT_IN_TM_ABORT:
302       case BUILT_IN_TM_IRREVOCABLE:
303         return true;
304       default:
305         break;
306       }
307
308   return false;
309 }
310
311 /* Return true if STMT is a TM load.  */
312
313 static bool
314 is_tm_load (gimple stmt)
315 {
316   tree fndecl;
317
318   if (gimple_code (stmt) != GIMPLE_CALL)
319     return false;
320
321   fndecl = gimple_call_fndecl (stmt);
322   return (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
323           && BUILTIN_TM_LOAD_P (DECL_FUNCTION_CODE (fndecl)));
324 }
325
326 /* Same as above, but for simple TM loads, that is, not the
327    after-write, after-read, etc optimized variants.  */
328
329 static bool
330 is_tm_simple_load (gimple stmt)
331 {
332   tree fndecl;
333
334   if (gimple_code (stmt) != GIMPLE_CALL)
335     return false;
336
337   fndecl = gimple_call_fndecl (stmt);
338   if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
339     {
340       enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl);
341       return (fcode == BUILT_IN_TM_LOAD_1
342               || fcode == BUILT_IN_TM_LOAD_2
343               || fcode == BUILT_IN_TM_LOAD_4
344               || fcode == BUILT_IN_TM_LOAD_8
345               || fcode == BUILT_IN_TM_LOAD_FLOAT
346               || fcode == BUILT_IN_TM_LOAD_DOUBLE
347               || fcode == BUILT_IN_TM_LOAD_LDOUBLE
348               || fcode == BUILT_IN_TM_LOAD_M64
349               || fcode == BUILT_IN_TM_LOAD_M128
350               || fcode == BUILT_IN_TM_LOAD_M256);
351     }
352   return false;
353 }
354
355 /* Return true if STMT is a TM store.  */
356
357 static bool
358 is_tm_store (gimple stmt)
359 {
360   tree fndecl;
361
362   if (gimple_code (stmt) != GIMPLE_CALL)
363     return false;
364
365   fndecl = gimple_call_fndecl (stmt);
366   return (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
367           && BUILTIN_TM_STORE_P (DECL_FUNCTION_CODE (fndecl)));
368 }
369
370 /* Same as above, but for simple TM stores, that is, not the
371    after-write, after-read, etc optimized variants.  */
372
373 static bool
374 is_tm_simple_store (gimple stmt)
375 {
376   tree fndecl;
377
378   if (gimple_code (stmt) != GIMPLE_CALL)
379     return false;
380
381   fndecl = gimple_call_fndecl (stmt);
382   if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
383     {
384       enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl);
385       return (fcode == BUILT_IN_TM_STORE_1
386               || fcode == BUILT_IN_TM_STORE_2
387               || fcode == BUILT_IN_TM_STORE_4
388               || fcode == BUILT_IN_TM_STORE_8
389               || fcode == BUILT_IN_TM_STORE_FLOAT
390               || fcode == BUILT_IN_TM_STORE_DOUBLE
391               || fcode == BUILT_IN_TM_STORE_LDOUBLE
392               || fcode == BUILT_IN_TM_STORE_M64
393               || fcode == BUILT_IN_TM_STORE_M128
394               || fcode == BUILT_IN_TM_STORE_M256);
395     }
396   return false;
397 }
398
399 /* Return true if FNDECL is BUILT_IN_TM_ABORT.  */
400
401 static bool
402 is_tm_abort (tree fndecl)
403 {
404   return (fndecl
405           && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
406           && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_TM_ABORT);
407 }
408
409 /* Build a GENERIC tree for a user abort.  This is called by front ends
410    while transforming the __tm_abort statement.  */
411
412 tree
413 build_tm_abort_call (location_t loc, bool is_outer)
414 {
415   return build_call_expr_loc (loc, builtin_decl_explicit (BUILT_IN_TM_ABORT), 1,
416                               build_int_cst (integer_type_node,
417                                              AR_USERABORT
418                                              | (is_outer ? AR_OUTERABORT : 0)));
419 }
420
421 /* Common gateing function for several of the TM passes.  */
422
423 static bool
424 gate_tm (void)
425 {
426   return flag_tm;
427 }
428 \f
429 /* Map for aribtrary function replacement under TM, as created
430    by the tm_wrap attribute.  */
431
432 static GTY((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
433      htab_t tm_wrap_map;
434
435 void
436 record_tm_replacement (tree from, tree to)
437 {
438   struct tree_map **slot, *h;
439
440   /* Do not inline wrapper functions that will get replaced in the TM
441      pass.
442
443      Suppose you have foo() that will get replaced into tmfoo().  Make
444      sure the inliner doesn't try to outsmart us and inline foo()
445      before we get a chance to do the TM replacement.  */
446   DECL_UNINLINABLE (from) = 1;
447
448   if (tm_wrap_map == NULL)
449     tm_wrap_map = htab_create_ggc (32, tree_map_hash, tree_map_eq, 0);
450
451   h = ggc_alloc_tree_map ();
452   h->hash = htab_hash_pointer (from);
453   h->base.from = from;
454   h->to = to;
455
456   slot = (struct tree_map **)
457     htab_find_slot_with_hash (tm_wrap_map, h, h->hash, INSERT);
458   *slot = h;
459 }
460
461 /* Return a TM-aware replacement function for DECL.  */
462
463 static tree
464 find_tm_replacement_function (tree fndecl)
465 {
466   if (tm_wrap_map)
467     {
468       struct tree_map *h, in;
469
470       in.base.from = fndecl;
471       in.hash = htab_hash_pointer (fndecl);
472       h = (struct tree_map *) htab_find_with_hash (tm_wrap_map, &in, in.hash);
473       if (h)
474         return h->to;
475     }
476
477   /* ??? We may well want TM versions of most of the common <string.h>
478      functions.  For now, we've already these two defined.  */
479   /* Adjust expand_call_tm() attributes as necessary for the cases
480      handled here:  */
481   if (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
482     switch (DECL_FUNCTION_CODE (fndecl))
483       {
484       case BUILT_IN_MEMCPY:
485         return builtin_decl_explicit (BUILT_IN_TM_MEMCPY);
486       case BUILT_IN_MEMMOVE:
487         return builtin_decl_explicit (BUILT_IN_TM_MEMMOVE);
488       case BUILT_IN_MEMSET:
489         return builtin_decl_explicit (BUILT_IN_TM_MEMSET);
490       default:
491         return NULL;
492       }
493
494   return NULL;
495 }
496
497 /* When appropriate, record TM replacement for memory allocation functions.
498
499    FROM is the FNDECL to wrap.  */
500 void
501 tm_malloc_replacement (tree from)
502 {
503   const char *str;
504   tree to;
505
506   if (TREE_CODE (from) != FUNCTION_DECL)
507     return;
508
509   /* If we have a previous replacement, the user must be explicitly
510      wrapping malloc/calloc/free.  They better know what they're
511      doing... */
512   if (find_tm_replacement_function (from))
513     return;
514
515   str = IDENTIFIER_POINTER (DECL_NAME (from));
516
517   if (!strcmp (str, "malloc"))
518     to = builtin_decl_explicit (BUILT_IN_TM_MALLOC);
519   else if (!strcmp (str, "calloc"))
520     to = builtin_decl_explicit (BUILT_IN_TM_CALLOC);
521   else if (!strcmp (str, "free"))
522     to = builtin_decl_explicit (BUILT_IN_TM_FREE);
523   else
524     return;
525
526   TREE_NOTHROW (to) = 0;
527
528   record_tm_replacement (from, to);
529 }
530 \f
531 /* Diagnostics for tm_safe functions/regions.  Called by the front end
532    once we've lowered the function to high-gimple.  */
533
534 /* Subroutine of diagnose_tm_safe_errors, called through walk_gimple_seq.
535    Process exactly one statement.  WI->INFO is set to non-null when in
536    the context of a tm_safe function, and null for a __transaction block.  */
537
538 #define DIAG_TM_OUTER           1
539 #define DIAG_TM_SAFE            2
540 #define DIAG_TM_RELAXED         4
541
542 struct diagnose_tm
543 {
544   unsigned int summary_flags : 8;
545   unsigned int block_flags : 8;
546   unsigned int func_flags : 8;
547   unsigned int saw_unsafe : 1;
548   unsigned int saw_volatile : 1;
549   gimple stmt;
550 };
551
552 /* Tree callback function for diagnose_tm pass.  */
553
554 static tree
555 diagnose_tm_1_op (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
556                   void *data)
557 {
558   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
559   struct diagnose_tm *d = (struct diagnose_tm *) wi->info;
560   enum tree_code code = TREE_CODE (*tp);
561
562   if ((code == VAR_DECL
563        || code == RESULT_DECL
564        || code == PARM_DECL)
565       && d->block_flags & (DIAG_TM_SAFE | DIAG_TM_RELAXED)
566       && TREE_THIS_VOLATILE (TREE_TYPE (*tp))
567       && !d->saw_volatile)
568     {
569       d->saw_volatile = 1;
570       error_at (gimple_location (d->stmt),
571                 "invalid volatile use of %qD inside transaction",
572                 *tp);
573     }
574
575   return NULL_TREE;
576 }
577
578 static tree
579 diagnose_tm_1 (gimple_stmt_iterator *gsi, bool *handled_ops_p,
580                     struct walk_stmt_info *wi)
581 {
582   gimple stmt = gsi_stmt (*gsi);
583   struct diagnose_tm *d = (struct diagnose_tm *) wi->info;
584
585   /* Save stmt for use in leaf analysis.  */
586   d->stmt = stmt;
587
588   switch (gimple_code (stmt))
589     {
590     case GIMPLE_CALL:
591       {
592         tree fn = gimple_call_fn (stmt);
593
594         if ((d->summary_flags & DIAG_TM_OUTER) == 0
595             && is_tm_may_cancel_outer (fn))
596           error_at (gimple_location (stmt),
597                     "%<transaction_may_cancel_outer%> function call not within"
598                     " outer transaction or %<transaction_may_cancel_outer%>");
599
600         if (d->summary_flags & DIAG_TM_SAFE)
601           {
602             bool is_safe, direct_call_p;
603             tree replacement;
604
605             if (TREE_CODE (fn) == ADDR_EXPR
606                 && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL)
607               {
608                 direct_call_p = true;
609                 replacement = TREE_OPERAND (fn, 0);
610                 replacement = find_tm_replacement_function (replacement);
611                 if (replacement)
612                   fn = replacement;
613               }
614             else
615               {
616                 direct_call_p = false;
617                 replacement = NULL_TREE;
618               }
619
620             if (is_tm_safe_or_pure (fn))
621               is_safe = true;
622             else if (is_tm_callable (fn) || is_tm_irrevocable (fn))
623               {
624                 /* A function explicitly marked transaction_callable as
625                    opposed to transaction_safe is being defined to be
626                    unsafe as part of its ABI, regardless of its contents.  */
627                 is_safe = false;
628               }
629             else if (direct_call_p)
630               {
631                 if (flags_from_decl_or_type (fn) & ECF_TM_BUILTIN)
632                   is_safe = true;
633                 else if (replacement)
634                   {
635                     /* ??? At present we've been considering replacements
636                        merely transaction_callable, and therefore might
637                        enter irrevocable.  The tm_wrap attribute has not
638                        yet made it into the new language spec.  */
639                     is_safe = false;
640                   }
641                 else
642                   {
643                     /* ??? Diagnostics for unmarked direct calls moved into
644                        the IPA pass.  Section 3.2 of the spec details how
645                        functions not marked should be considered "implicitly
646                        safe" based on having examined the function body.  */
647                     is_safe = true;
648                   }
649               }
650             else
651               {
652                 /* An unmarked indirect call.  Consider it unsafe even
653                    though optimization may yet figure out how to inline.  */
654                 is_safe = false;
655               }
656
657             if (!is_safe)
658               {
659                 if (TREE_CODE (fn) == ADDR_EXPR)
660                   fn = TREE_OPERAND (fn, 0);
661                 if (d->block_flags & DIAG_TM_SAFE)
662                   {
663                     if (direct_call_p)
664                       error_at (gimple_location (stmt),
665                                 "unsafe function call %qD within "
666                                 "atomic transaction", fn);
667                     else
668                       error_at (gimple_location (stmt),
669                                 "unsafe function call %qE within "
670                                 "atomic transaction", fn);
671                   }
672                 else
673                   {
674                     if (direct_call_p)
675                       error_at (gimple_location (stmt),
676                                 "unsafe function call %qD within "
677                                 "%<transaction_safe%> function", fn);
678                     else
679                       error_at (gimple_location (stmt),
680                                 "unsafe function call %qE within "
681                                 "%<transaction_safe%> function", fn);
682                   }
683               }
684           }
685       }
686       break;
687
688     case GIMPLE_ASM:
689       /* ??? We ought to come up with a way to add attributes to
690          asm statements, and then add "transaction_safe" to it.
691          Either that or get the language spec to resurrect __tm_waiver.  */
692       if (d->block_flags & DIAG_TM_SAFE)
693         error_at (gimple_location (stmt),
694                   "asm not allowed in atomic transaction");
695       else if (d->func_flags & DIAG_TM_SAFE)
696         error_at (gimple_location (stmt),
697                   "asm not allowed in %<transaction_safe%> function");
698       else
699         d->saw_unsafe = true;
700       break;
701
702     case GIMPLE_TRANSACTION:
703       {
704         unsigned char inner_flags = DIAG_TM_SAFE;
705
706         if (gimple_transaction_subcode (stmt) & GTMA_IS_RELAXED)
707           {
708             if (d->block_flags & DIAG_TM_SAFE)
709               error_at (gimple_location (stmt),
710                         "relaxed transaction in atomic transaction");
711             else if (d->func_flags & DIAG_TM_SAFE)
712               error_at (gimple_location (stmt),
713                         "relaxed transaction in %<transaction_safe%> function");
714             else
715               d->saw_unsafe = true;
716             inner_flags = DIAG_TM_RELAXED;
717           }
718         else if (gimple_transaction_subcode (stmt) & GTMA_IS_OUTER)
719           {
720             if (d->block_flags)
721               error_at (gimple_location (stmt),
722                         "outer transaction in transaction");
723             else if (d->func_flags & DIAG_TM_OUTER)
724               error_at (gimple_location (stmt),
725                         "outer transaction in "
726                         "%<transaction_may_cancel_outer%> function");
727             else if (d->func_flags & DIAG_TM_SAFE)
728               error_at (gimple_location (stmt),
729                         "outer transaction in %<transaction_safe%> function");
730             else
731               d->saw_unsafe = true;
732             inner_flags |= DIAG_TM_OUTER;
733           }
734
735         *handled_ops_p = true;
736         if (gimple_transaction_body (stmt))
737           {
738             struct walk_stmt_info wi_inner;
739             struct diagnose_tm d_inner;
740
741             memset (&d_inner, 0, sizeof (d_inner));
742             d_inner.func_flags = d->func_flags;
743             d_inner.block_flags = d->block_flags | inner_flags;
744             d_inner.summary_flags = d_inner.func_flags | d_inner.block_flags;
745
746             memset (&wi_inner, 0, sizeof (wi_inner));
747             wi_inner.info = &d_inner;
748
749             walk_gimple_seq (gimple_transaction_body (stmt),
750                              diagnose_tm_1, diagnose_tm_1_op, &wi_inner);
751
752             d->saw_unsafe |= d_inner.saw_unsafe;
753           }
754       }
755       break;
756
757     default:
758       break;
759     }
760
761   return NULL_TREE;
762 }
763
764 static unsigned int
765 diagnose_tm_blocks (void)
766 {
767   struct walk_stmt_info wi;
768   struct diagnose_tm d;
769
770   memset (&d, 0, sizeof (d));
771   if (is_tm_may_cancel_outer (current_function_decl))
772     d.func_flags = DIAG_TM_OUTER | DIAG_TM_SAFE;
773   else if (is_tm_safe (current_function_decl))
774     d.func_flags = DIAG_TM_SAFE;
775   d.summary_flags = d.func_flags;
776
777   memset (&wi, 0, sizeof (wi));
778   wi.info = &d;
779
780   walk_gimple_seq (gimple_body (current_function_decl),
781                    diagnose_tm_1, diagnose_tm_1_op, &wi);
782
783   /* If we saw something other than a call that makes this function
784      unsafe, remember it so that the IPA pass only needs to scan calls.  */
785   if (d.saw_unsafe && !is_tm_safe_or_pure (current_function_decl))
786     cgraph_local_info (current_function_decl)->tm_may_enter_irr = 1;
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_var (TREE_TYPE (lp->addr), "tm_save");
1021           add_referenced_var (lp->save_var);
1022           lp->stmts = NULL;
1023           lp->entry_block = entry_block;
1024           /* Save addresses separately in dominator order so we don't
1025              get confused by overlapping addresses in the save/restore
1026              sequence.  */
1027           VEC_safe_push (tree, heap, tm_log_save_addresses, lp->addr);
1028         }
1029       else
1030         {
1031           /* Use the logging functions.  */
1032           lp->stmts = VEC_alloc (gimple, heap, 5);
1033           VEC_quick_push (gimple, lp->stmts, stmt);
1034           lp->save_var = NULL;
1035         }
1036     }
1037   else
1038     {
1039       size_t i;
1040       gimple oldstmt;
1041
1042       lp = (struct tm_log_entry *) *slot;
1043
1044       /* If we're generating a save/restore sequence, we don't care
1045          about statements.  */
1046       if (lp->save_var)
1047         return;
1048
1049       for (i = 0; VEC_iterate (gimple, lp->stmts, i, oldstmt); ++i)
1050         {
1051           if (stmt == oldstmt)
1052             return;
1053           /* We already have a store to the same address, higher up the
1054              dominator tree.  Nothing to do.  */
1055           if (dominated_by_p (CDI_DOMINATORS,
1056                               gimple_bb (stmt), gimple_bb (oldstmt)))
1057             return;
1058           /* We should be processing blocks in dominator tree order.  */
1059           gcc_assert (!dominated_by_p (CDI_DOMINATORS,
1060                                        gimple_bb (oldstmt), gimple_bb (stmt)));
1061         }
1062       /* Store is on a different code path.  */
1063       VEC_safe_push (gimple, heap, lp->stmts, stmt);
1064     }
1065 }
1066
1067 /* Gimplify the address of a TARGET_MEM_REF.  Return the SSA_NAME
1068    result, insert the new statements before GSI.  */
1069
1070 static tree
1071 gimplify_addr (gimple_stmt_iterator *gsi, tree x)
1072 {
1073   if (TREE_CODE (x) == TARGET_MEM_REF)
1074     x = tree_mem_ref_addr (build_pointer_type (TREE_TYPE (x)), x);
1075   else
1076     x = build_fold_addr_expr (x);
1077   return force_gimple_operand_gsi (gsi, x, true, NULL, true, GSI_SAME_STMT);
1078 }
1079
1080 /* Instrument one address with the logging functions.
1081    ADDR is the address to save.
1082    STMT is the statement before which to place it.  */
1083 static void
1084 tm_log_emit_stmt (tree addr, gimple stmt)
1085 {
1086   tree type = TREE_TYPE (addr);
1087   tree size = TYPE_SIZE_UNIT (type);
1088   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1089   gimple log;
1090   enum built_in_function code = BUILT_IN_TM_LOG;
1091
1092   if (type == float_type_node)
1093     code = BUILT_IN_TM_LOG_FLOAT;
1094   else if (type == double_type_node)
1095     code = BUILT_IN_TM_LOG_DOUBLE;
1096   else if (type == long_double_type_node)
1097     code = BUILT_IN_TM_LOG_LDOUBLE;
1098   else if (host_integerp (size, 1))
1099     {
1100       unsigned int n = tree_low_cst (size, 1);
1101       switch (n)
1102         {
1103         case 1:
1104           code = BUILT_IN_TM_LOG_1;
1105           break;
1106         case 2:
1107           code = BUILT_IN_TM_LOG_2;
1108           break;
1109         case 4:
1110           code = BUILT_IN_TM_LOG_4;
1111           break;
1112         case 8:
1113           code = BUILT_IN_TM_LOG_8;
1114           break;
1115         default:
1116           code = BUILT_IN_TM_LOG;
1117           if (TREE_CODE (type) == VECTOR_TYPE)
1118             {
1119               if (n == 8 && builtin_decl_explicit (BUILT_IN_TM_LOG_M64))
1120                 code = BUILT_IN_TM_LOG_M64;
1121               else if (n == 16 && builtin_decl_explicit (BUILT_IN_TM_LOG_M128))
1122                 code = BUILT_IN_TM_LOG_M128;
1123               else if (n == 32 && builtin_decl_explicit (BUILT_IN_TM_LOG_M256))
1124                 code = BUILT_IN_TM_LOG_M256;
1125             }
1126           break;
1127         }
1128     }
1129
1130   addr = gimplify_addr (&gsi, addr);
1131   if (code == BUILT_IN_TM_LOG)
1132     log = gimple_build_call (builtin_decl_explicit (code), 2, addr,  size);
1133   else
1134     log = gimple_build_call (builtin_decl_explicit (code), 1, addr);
1135   gsi_insert_before (&gsi, log, GSI_SAME_STMT);
1136 }
1137
1138 /* Go through the log and instrument address that must be instrumented
1139    with the logging functions.  Leave the save/restore addresses for
1140    later.  */
1141 static void
1142 tm_log_emit (void)
1143 {
1144   htab_iterator hi;
1145   struct tm_log_entry *lp;
1146
1147   FOR_EACH_HTAB_ELEMENT (tm_log, lp, tm_log_entry_t, hi)
1148     {
1149       size_t i;
1150       gimple stmt;
1151
1152       if (dump_file)
1153         {
1154           fprintf (dump_file, "TM thread private mem logging: ");
1155           print_generic_expr (dump_file, lp->addr, 0);
1156           fprintf (dump_file, "\n");
1157         }
1158
1159       if (lp->save_var)
1160         {
1161           if (dump_file)
1162             fprintf (dump_file, "DUMPING to variable\n");
1163           continue;
1164         }
1165       else
1166         {
1167           if (dump_file)
1168             fprintf (dump_file, "DUMPING with logging functions\n");
1169           for (i = 0; VEC_iterate (gimple, lp->stmts, i, stmt); ++i)
1170             tm_log_emit_stmt (lp->addr, stmt);
1171         }
1172     }
1173 }
1174
1175 /* Emit the save sequence for the corresponding addresses in the log.
1176    ENTRY_BLOCK is the entry block for the transaction.
1177    BB is the basic block to insert the code in.  */
1178 static void
1179 tm_log_emit_saves (basic_block entry_block, basic_block bb)
1180 {
1181   size_t i;
1182   gimple_stmt_iterator gsi = gsi_last_bb (bb);
1183   gimple stmt;
1184   struct tm_log_entry l, *lp;
1185
1186   for (i = 0; i < VEC_length (tree, tm_log_save_addresses); ++i)
1187     {
1188       l.addr = VEC_index (tree, tm_log_save_addresses, i);
1189       lp = (struct tm_log_entry *) *htab_find_slot (tm_log, &l, NO_INSERT);
1190       gcc_assert (lp->save_var != NULL);
1191
1192       /* We only care about variables in the current transaction.  */
1193       if (lp->entry_block != entry_block)
1194         continue;
1195
1196       stmt = gimple_build_assign (lp->save_var, unshare_expr (lp->addr));
1197
1198       /* Make sure we can create an SSA_NAME for this type.  For
1199          instance, aggregates aren't allowed, in which case the system
1200          will create a VOP for us and everything will just work.  */
1201       if (is_gimple_reg_type (TREE_TYPE (lp->save_var)))
1202         {
1203           lp->save_var = make_ssa_name (lp->save_var, stmt);
1204           gimple_assign_set_lhs (stmt, lp->save_var);
1205         }
1206
1207       gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1208     }
1209 }
1210
1211 /* Emit the restore sequence for the corresponding addresses in the log.
1212    ENTRY_BLOCK is the entry block for the transaction.
1213    BB is the basic block to insert the code in.  */
1214 static void
1215 tm_log_emit_restores (basic_block entry_block, basic_block bb)
1216 {
1217   int i;
1218   struct tm_log_entry l, *lp;
1219   gimple_stmt_iterator gsi;
1220   gimple stmt;
1221
1222   for (i = VEC_length (tree, tm_log_save_addresses) - 1; i >= 0; i--)
1223     {
1224       l.addr = VEC_index (tree, tm_log_save_addresses, i);
1225       lp = (struct tm_log_entry *) *htab_find_slot (tm_log, &l, NO_INSERT);
1226       gcc_assert (lp->save_var != NULL);
1227
1228       /* We only care about variables in the current transaction.  */
1229       if (lp->entry_block != entry_block)
1230         continue;
1231
1232       /* Restores are in LIFO order from the saves in case we have
1233          overlaps.  */
1234       gsi = gsi_start_bb (bb);
1235
1236       stmt = gimple_build_assign (unshare_expr (lp->addr), lp->save_var);
1237       gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
1238     }
1239 }
1240
1241 /* Emit the checks for performing either a save or a restore sequence.
1242
1243    TRXN_PROP is either A_SAVELIVEVARIABLES or A_RESTORELIVEVARIABLES.
1244
1245    The code sequence is inserted in a new basic block created in
1246    END_BB which is inserted between BEFORE_BB and the destination of
1247    FALLTHRU_EDGE.
1248
1249    STATUS is the return value from _ITM_beginTransaction.
1250    ENTRY_BLOCK is the entry block for the transaction.
1251    EMITF is a callback to emit the actual save/restore code.
1252
1253    The basic block containing the conditional checking for TRXN_PROP
1254    is returned.  */
1255 static basic_block
1256 tm_log_emit_save_or_restores (basic_block entry_block,
1257                               unsigned trxn_prop,
1258                               tree status,
1259                               void (*emitf)(basic_block, basic_block),
1260                               basic_block before_bb,
1261                               edge fallthru_edge,
1262                               basic_block *end_bb)
1263 {
1264   basic_block cond_bb, code_bb;
1265   gimple cond_stmt, stmt;
1266   gimple_stmt_iterator gsi;
1267   tree t1, t2;
1268   int old_flags = fallthru_edge->flags;
1269
1270   cond_bb = create_empty_bb (before_bb);
1271   code_bb = create_empty_bb (cond_bb);
1272   *end_bb = create_empty_bb (code_bb);
1273   redirect_edge_pred (fallthru_edge, *end_bb);
1274   fallthru_edge->flags = EDGE_FALLTHRU;
1275   make_edge (before_bb, cond_bb, old_flags);
1276
1277   set_immediate_dominator (CDI_DOMINATORS, cond_bb, before_bb);
1278   set_immediate_dominator (CDI_DOMINATORS, code_bb, cond_bb);
1279
1280   gsi = gsi_last_bb (cond_bb);
1281
1282   /* t1 = status & A_{property}.  */
1283   t1 = make_rename_temp (TREE_TYPE (status), NULL);
1284   t2 = build_int_cst (TREE_TYPE (status), trxn_prop);
1285   stmt = gimple_build_assign_with_ops (BIT_AND_EXPR, t1, status, t2);
1286   gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
1287
1288   /* if (t1).  */
1289   t2 = build_int_cst (TREE_TYPE (status), 0);
1290   cond_stmt = gimple_build_cond (NE_EXPR, t1, t2, NULL, NULL);
1291   gsi_insert_after (&gsi, cond_stmt, GSI_CONTINUE_LINKING);
1292
1293   emitf (entry_block, code_bb);
1294
1295   make_edge (cond_bb, code_bb, EDGE_TRUE_VALUE);
1296   make_edge (cond_bb, *end_bb, EDGE_FALSE_VALUE);
1297   make_edge (code_bb, *end_bb, EDGE_FALLTHRU);
1298
1299   return cond_bb;
1300 }
1301 \f
1302 static tree lower_sequence_tm (gimple_stmt_iterator *, bool *,
1303                                struct walk_stmt_info *);
1304 static tree lower_sequence_no_tm (gimple_stmt_iterator *, bool *,
1305                                   struct walk_stmt_info *);
1306
1307 /* Evaluate an address X being dereferenced and determine if it
1308    originally points to a non aliased new chunk of memory (malloc,
1309    alloca, etc).
1310
1311    Return MEM_THREAD_LOCAL if it points to a thread-local address.
1312    Return MEM_TRANSACTION_LOCAL if it points to a transaction-local address.
1313    Return MEM_NON_LOCAL otherwise.
1314
1315    ENTRY_BLOCK is the entry block to the transaction containing the
1316    dereference of X.  */
1317 static enum thread_memory_type
1318 thread_private_new_memory (basic_block entry_block, tree x)
1319 {
1320   gimple stmt = NULL;
1321   enum tree_code code;
1322   void **slot;
1323   tm_new_mem_map_t elt, *elt_p;
1324   tree val = x;
1325   enum thread_memory_type retval = mem_transaction_local;
1326
1327   if (!entry_block
1328       || TREE_CODE (x) != SSA_NAME
1329       /* Possible uninitialized use, or a function argument.  In
1330          either case, we don't care.  */
1331       || SSA_NAME_IS_DEFAULT_DEF (x))
1332     return mem_non_local;
1333
1334   /* Look in cache first.  */
1335   elt.val = x;
1336   slot = htab_find_slot (tm_new_mem_hash, &elt, INSERT);
1337   elt_p = (tm_new_mem_map_t *) *slot;
1338   if (elt_p)
1339     return elt_p->local_new_memory;
1340
1341   /* Optimistically assume the memory is transaction local during
1342      processing.  This catches recursion into this variable.  */
1343   *slot = elt_p = XNEW (tm_new_mem_map_t);
1344   elt_p->val = val;
1345   elt_p->local_new_memory = mem_transaction_local;
1346
1347   /* Search DEF chain to find the original definition of this address.  */
1348   do
1349     {
1350       if (ptr_deref_may_alias_global_p (x))
1351         {
1352           /* Address escapes.  This is not thread-private.  */
1353           retval = mem_non_local;
1354           goto new_memory_ret;
1355         }
1356
1357       stmt = SSA_NAME_DEF_STMT (x);
1358
1359       /* If the malloc call is outside the transaction, this is
1360          thread-local.  */
1361       if (retval != mem_thread_local
1362           && !dominated_by_p (CDI_DOMINATORS, gimple_bb (stmt), entry_block))
1363         retval = mem_thread_local;
1364
1365       if (is_gimple_assign (stmt))
1366         {
1367           code = gimple_assign_rhs_code (stmt);
1368           /* x = foo ==> foo */
1369           if (code == SSA_NAME)
1370             x = gimple_assign_rhs1 (stmt);
1371           /* x = foo + n ==> foo */
1372           else if (code == POINTER_PLUS_EXPR)
1373             x = gimple_assign_rhs1 (stmt);
1374           /* x = (cast*) foo ==> foo */
1375           else if (code == VIEW_CONVERT_EXPR || code == NOP_EXPR)
1376             x = gimple_assign_rhs1 (stmt);
1377           else
1378             {
1379               retval = mem_non_local;
1380               goto new_memory_ret;
1381             }
1382         }
1383       else
1384         {
1385           if (gimple_code (stmt) == GIMPLE_PHI)
1386             {
1387               unsigned int i;
1388               enum thread_memory_type mem;
1389               tree phi_result = gimple_phi_result (stmt);
1390
1391               /* If any of the ancestors are non-local, we are sure to
1392                  be non-local.  Otherwise we can avoid doing anything
1393                  and inherit what has already been generated.  */
1394               retval = mem_max;
1395               for (i = 0; i < gimple_phi_num_args (stmt); ++i)
1396                 {
1397                   tree op = PHI_ARG_DEF (stmt, i);
1398
1399                   /* Exclude self-assignment.  */
1400                   if (phi_result == op)
1401                     continue;
1402
1403                   mem = thread_private_new_memory (entry_block, op);
1404                   if (mem == mem_non_local)
1405                     {
1406                       retval = mem;
1407                       goto new_memory_ret;
1408                     }
1409                   retval = MIN (retval, mem);
1410                 }
1411               goto new_memory_ret;
1412             }
1413           break;
1414         }
1415     }
1416   while (TREE_CODE (x) == SSA_NAME);
1417
1418   if (stmt && is_gimple_call (stmt) && gimple_call_flags (stmt) & ECF_MALLOC)
1419     /* Thread-local or transaction-local.  */
1420     ;
1421   else
1422     retval = mem_non_local;
1423
1424  new_memory_ret:
1425   elt_p->local_new_memory = retval;
1426   return retval;
1427 }
1428
1429 /* Determine whether X has to be instrumented using a read
1430    or write barrier.
1431
1432    ENTRY_BLOCK is the entry block for the region where stmt resides
1433    in.  NULL if unknown.
1434
1435    STMT is the statement in which X occurs in.  It is used for thread
1436    private memory instrumentation.  If no TPM instrumentation is
1437    desired, STMT should be null.  */
1438 static bool
1439 requires_barrier (basic_block entry_block, tree x, gimple stmt)
1440 {
1441   tree orig = x;
1442   while (handled_component_p (x))
1443     x = TREE_OPERAND (x, 0);
1444
1445   switch (TREE_CODE (x))
1446     {
1447     case INDIRECT_REF:
1448     case MEM_REF:
1449       {
1450         enum thread_memory_type ret;
1451
1452         ret = thread_private_new_memory (entry_block, TREE_OPERAND (x, 0));
1453         if (ret == mem_non_local)
1454           return true;
1455         if (stmt && ret == mem_thread_local)
1456           /* ?? Should we pass `orig', or the INDIRECT_REF X.  ?? */
1457           tm_log_add (entry_block, orig, stmt);
1458
1459         /* Transaction-locals require nothing at all.  For malloc, a
1460            transaction restart frees the memory and we reallocate.
1461            For alloca, the stack pointer gets reset by the retry and
1462            we reallocate.  */
1463         return false;
1464       }
1465
1466     case TARGET_MEM_REF:
1467       if (TREE_CODE (TMR_BASE (x)) != ADDR_EXPR)
1468         return true;
1469       x = TREE_OPERAND (TMR_BASE (x), 0);
1470       if (TREE_CODE (x) == PARM_DECL)
1471         return false;
1472       gcc_assert (TREE_CODE (x) == VAR_DECL);
1473       /* FALLTHRU */
1474
1475     case PARM_DECL:
1476     case RESULT_DECL:
1477     case VAR_DECL:
1478       if (DECL_BY_REFERENCE (x))
1479         {
1480           /* ??? This value is a pointer, but aggregate_value_p has been
1481              jigged to return true which confuses needs_to_live_in_memory.
1482              This ought to be cleaned up generically.
1483
1484              FIXME: Verify this still happens after the next mainline
1485              merge.  Testcase ie g++.dg/tm/pr47554.C.
1486           */
1487           return false;
1488         }
1489
1490       if (is_global_var (x))
1491         return !TREE_READONLY (x);
1492       if (/* FIXME: This condition should actually go below in the
1493              tm_log_add() call, however is_call_clobbered() depends on
1494              aliasing info which is not available during
1495              gimplification.  Since requires_barrier() gets called
1496              during lower_sequence_tm/gimplification, leave the call
1497              to needs_to_live_in_memory until we eliminate
1498              lower_sequence_tm altogether.  */
1499           needs_to_live_in_memory (x)
1500           /* X escapes.  */
1501           || ptr_deref_may_alias_global_p (x))
1502         return true;
1503       else
1504         {
1505           /* For local memory that doesn't escape (aka thread private
1506              memory), we can either save the value at the beginning of
1507              the transaction and restore on restart, or call a tm
1508              function to dynamically save and restore on restart
1509              (ITM_L*).  */
1510           if (stmt)
1511             tm_log_add (entry_block, orig, stmt);
1512           return false;
1513         }
1514
1515     default:
1516       return false;
1517     }
1518 }
1519
1520 /* Mark the GIMPLE_ASSIGN statement as appropriate for being inside
1521    a transaction region.  */
1522
1523 static void
1524 examine_assign_tm (unsigned *state, gimple_stmt_iterator *gsi)
1525 {
1526   gimple stmt = gsi_stmt (*gsi);
1527
1528   if (requires_barrier (/*entry_block=*/NULL, gimple_assign_rhs1 (stmt), NULL))
1529     *state |= GTMA_HAVE_LOAD;
1530   if (requires_barrier (/*entry_block=*/NULL, gimple_assign_lhs (stmt), NULL))
1531     *state |= GTMA_HAVE_STORE;
1532 }
1533
1534 /* Mark a GIMPLE_CALL as appropriate for being inside a transaction.  */
1535
1536 static void
1537 examine_call_tm (unsigned *state, gimple_stmt_iterator *gsi)
1538 {
1539   gimple stmt = gsi_stmt (*gsi);
1540   tree fn;
1541
1542   if (is_tm_pure_call (stmt))
1543     return;
1544
1545   /* Check if this call is a transaction abort.  */
1546   fn = gimple_call_fndecl (stmt);
1547   if (is_tm_abort (fn))
1548     *state |= GTMA_HAVE_ABORT;
1549
1550   /* Note that something may happen.  */
1551   *state |= GTMA_HAVE_LOAD | GTMA_HAVE_STORE;
1552 }
1553
1554 /* Lower a GIMPLE_TRANSACTION statement.  */
1555
1556 static void
1557 lower_transaction (gimple_stmt_iterator *gsi, struct walk_stmt_info *wi)
1558 {
1559   gimple g, stmt = gsi_stmt (*gsi);
1560   unsigned int *outer_state = (unsigned int *) wi->info;
1561   unsigned int this_state = 0;
1562   struct walk_stmt_info this_wi;
1563
1564   /* First, lower the body.  The scanning that we do inside gives
1565      us some idea of what we're dealing with.  */
1566   memset (&this_wi, 0, sizeof (this_wi));
1567   this_wi.info = (void *) &this_state;
1568   walk_gimple_seq (gimple_transaction_body (stmt),
1569                    lower_sequence_tm, NULL, &this_wi);
1570
1571   /* If there was absolutely nothing transaction related inside the
1572      transaction, we may elide it.  Likewise if this is a nested
1573      transaction and does not contain an abort.  */
1574   if (this_state == 0
1575       || (!(this_state & GTMA_HAVE_ABORT) && outer_state != NULL))
1576     {
1577       if (outer_state)
1578         *outer_state |= this_state;
1579
1580       gsi_insert_seq_before (gsi, gimple_transaction_body (stmt),
1581                              GSI_SAME_STMT);
1582       gimple_transaction_set_body (stmt, NULL);
1583
1584       gsi_remove (gsi, true);
1585       wi->removed_stmt = true;
1586       return;
1587     }
1588
1589   /* Wrap the body of the transaction in a try-finally node so that
1590      the commit call is always properly called.  */
1591   g = gimple_build_call (builtin_decl_explicit (BUILT_IN_TM_COMMIT), 0);
1592   if (flag_exceptions)
1593     {
1594       tree ptr;
1595       gimple_seq n_seq, e_seq;
1596
1597       n_seq = gimple_seq_alloc_with_stmt (g);
1598       e_seq = gimple_seq_alloc ();
1599
1600       g = gimple_build_call (builtin_decl_explicit (BUILT_IN_EH_POINTER),
1601                              1, integer_zero_node);
1602       ptr = create_tmp_var (ptr_type_node, NULL);
1603       gimple_call_set_lhs (g, ptr);
1604       gimple_seq_add_stmt (&e_seq, g);
1605
1606       g = gimple_build_call (builtin_decl_explicit (BUILT_IN_TM_COMMIT_EH),
1607                              1, ptr);
1608       gimple_seq_add_stmt (&e_seq, g);
1609
1610       g = gimple_build_eh_else (n_seq, e_seq);
1611     }
1612
1613   g = gimple_build_try (gimple_transaction_body (stmt),
1614                         gimple_seq_alloc_with_stmt (g), GIMPLE_TRY_FINALLY);
1615   gsi_insert_after (gsi, g, GSI_CONTINUE_LINKING);
1616
1617   gimple_transaction_set_body (stmt, NULL);
1618
1619   /* If the transaction calls abort or if this is an outer transaction,
1620      add an "over" label afterwards.  */
1621   if ((this_state & (GTMA_HAVE_ABORT))
1622       || (gimple_transaction_subcode(stmt) & GTMA_IS_OUTER))
1623     {
1624       tree label = create_artificial_label (UNKNOWN_LOCATION);
1625       gimple_transaction_set_label (stmt, label);
1626       gsi_insert_after (gsi, gimple_build_label (label), GSI_CONTINUE_LINKING);
1627     }
1628
1629   /* Record the set of operations found for use later.  */
1630   this_state |= gimple_transaction_subcode (stmt) & GTMA_DECLARATION_MASK;
1631   gimple_transaction_set_subcode (stmt, this_state);
1632 }
1633
1634 /* Iterate through the statements in the sequence, lowering them all
1635    as appropriate for being in a transaction.  */
1636
1637 static tree
1638 lower_sequence_tm (gimple_stmt_iterator *gsi, bool *handled_ops_p,
1639                    struct walk_stmt_info *wi)
1640 {
1641   unsigned int *state = (unsigned int *) wi->info;
1642   gimple stmt = gsi_stmt (*gsi);
1643
1644   *handled_ops_p = true;
1645   switch (gimple_code (stmt))
1646     {
1647     case GIMPLE_ASSIGN:
1648       /* Only memory reads/writes need to be instrumented.  */
1649       if (gimple_assign_single_p (stmt))
1650         examine_assign_tm (state, gsi);
1651       break;
1652
1653     case GIMPLE_CALL:
1654       examine_call_tm (state, gsi);
1655       break;
1656
1657     case GIMPLE_ASM:
1658       *state |= GTMA_MAY_ENTER_IRREVOCABLE;
1659       break;
1660
1661     case GIMPLE_TRANSACTION:
1662       lower_transaction (gsi, wi);
1663       break;
1664
1665     default:
1666       *handled_ops_p = !gimple_has_substatements (stmt);
1667       break;
1668     }
1669
1670   return NULL_TREE;
1671 }
1672
1673 /* Iterate through the statements in the sequence, lowering them all
1674    as appropriate for being outside of a transaction.  */
1675
1676 static tree
1677 lower_sequence_no_tm (gimple_stmt_iterator *gsi, bool *handled_ops_p,
1678                       struct walk_stmt_info * wi)
1679 {
1680   gimple stmt = gsi_stmt (*gsi);
1681
1682   if (gimple_code (stmt) == GIMPLE_TRANSACTION)
1683     {
1684       *handled_ops_p = true;
1685       lower_transaction (gsi, wi);
1686     }
1687   else
1688     *handled_ops_p = !gimple_has_substatements (stmt);
1689
1690   return NULL_TREE;
1691 }
1692
1693 /* Main entry point for flattening GIMPLE_TRANSACTION constructs.  After
1694    this, GIMPLE_TRANSACTION nodes still exist, but the nested body has
1695    been moved out, and all the data required for constructing a proper
1696    CFG has been recorded.  */
1697
1698 static unsigned int
1699 execute_lower_tm (void)
1700 {
1701   struct walk_stmt_info wi;
1702
1703   /* Transactional clones aren't created until a later pass.  */
1704   gcc_assert (!decl_is_tm_clone (current_function_decl));
1705
1706   memset (&wi, 0, sizeof (wi));
1707   walk_gimple_seq (gimple_body (current_function_decl),
1708                    lower_sequence_no_tm, NULL, &wi);
1709
1710   return 0;
1711 }
1712
1713 struct gimple_opt_pass pass_lower_tm =
1714 {
1715  {
1716   GIMPLE_PASS,
1717   "tmlower",                            /* name */
1718   gate_tm,                              /* gate */
1719   execute_lower_tm,                     /* execute */
1720   NULL,                                 /* sub */
1721   NULL,                                 /* next */
1722   0,                                    /* static_pass_number */
1723   TV_TRANS_MEM,                         /* tv_id */
1724   PROP_gimple_lcf,                      /* properties_required */
1725   0,                                    /* properties_provided */
1726   0,                                    /* properties_destroyed */
1727   0,                                    /* todo_flags_start */
1728   TODO_dump_func                        /* todo_flags_finish */
1729  }
1730 };
1731 \f
1732 /* Collect region information for each transaction.  */
1733
1734 struct tm_region
1735 {
1736   /* Link to the next unnested transaction.  */
1737   struct tm_region *next;
1738
1739   /* Link to the next inner transaction.  */
1740   struct tm_region *inner;
1741
1742   /* Link to the next outer transaction.  */
1743   struct tm_region *outer;
1744
1745   /* The GIMPLE_TRANSACTION statement beginning this transaction.  */
1746   gimple transaction_stmt;
1747
1748   /* The entry block to this region.  */
1749   basic_block entry_block;
1750
1751   /* The set of all blocks that end the region; NULL if only EXIT_BLOCK.
1752      These blocks are still a part of the region (i.e., the border is
1753      inclusive). Note that this set is only complete for paths in the CFG
1754      starting at ENTRY_BLOCK, and that there is no exit block recorded for
1755      the edge to the "over" label.  */
1756   bitmap exit_blocks;
1757
1758   /* The set of all blocks that have an TM_IRREVOCABLE call.  */
1759   bitmap irr_blocks;
1760 };
1761
1762 /* True if there are pending edge statements to be committed for the
1763    current function being scanned in the tmmark pass.  */
1764 bool pending_edge_inserts_p;
1765
1766 static struct tm_region *all_tm_regions;
1767 static bitmap_obstack tm_obstack;
1768
1769
1770 /* A subroutine of tm_region_init.  Record the existance of the
1771    GIMPLE_TRANSACTION statement in a tree of tm_region elements.  */
1772
1773 static struct tm_region *
1774 tm_region_init_0 (struct tm_region *outer, basic_block bb, gimple stmt)
1775 {
1776   struct tm_region *region;
1777
1778   region = (struct tm_region *)
1779     obstack_alloc (&tm_obstack.obstack, sizeof (struct tm_region));
1780
1781   if (outer)
1782     {
1783       region->next = outer->inner;
1784       outer->inner = region;
1785     }
1786   else
1787     {
1788       region->next = all_tm_regions;
1789       all_tm_regions = region;
1790     }
1791   region->inner = NULL;
1792   region->outer = outer;
1793
1794   region->transaction_stmt = stmt;
1795
1796   /* There are either one or two edges out of the block containing
1797      the GIMPLE_TRANSACTION, one to the actual region and one to the
1798      "over" label if the region contains an abort.  The former will
1799      always be the one marked FALLTHRU.  */
1800   region->entry_block = FALLTHRU_EDGE (bb)->dest;
1801
1802   region->exit_blocks = BITMAP_ALLOC (&tm_obstack);
1803   region->irr_blocks = BITMAP_ALLOC (&tm_obstack);
1804
1805   return region;
1806 }
1807
1808 /* A subroutine of tm_region_init.  Record all the exit and
1809    irrevocable blocks in BB into the region's exit_blocks and
1810    irr_blocks bitmaps.  Returns the new region being scanned.  */
1811
1812 static struct tm_region *
1813 tm_region_init_1 (struct tm_region *region, basic_block bb)
1814 {
1815   gimple_stmt_iterator gsi;
1816   gimple g;
1817
1818   if (!region
1819       || (!region->irr_blocks && !region->exit_blocks))
1820     return region;
1821
1822   /* Check to see if this is the end of a region by seeing if it
1823      contains a call to __builtin_tm_commit{,_eh}.  Note that the
1824      outermost region for DECL_IS_TM_CLONE need not collect this.  */
1825   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
1826     {
1827       g = gsi_stmt (gsi);
1828       if (gimple_code (g) == GIMPLE_CALL)
1829         {
1830           tree fn = gimple_call_fndecl (g);
1831           if (fn && DECL_BUILT_IN_CLASS (fn) == BUILT_IN_NORMAL)
1832             {
1833               if ((DECL_FUNCTION_CODE (fn) == BUILT_IN_TM_COMMIT
1834                    || DECL_FUNCTION_CODE (fn) == BUILT_IN_TM_COMMIT_EH)
1835                   && region->exit_blocks)
1836                 {
1837                   bitmap_set_bit (region->exit_blocks, bb->index);
1838                   region = region->outer;
1839                   break;
1840                 }
1841               if (DECL_FUNCTION_CODE (fn) == BUILT_IN_TM_IRREVOCABLE)
1842                 bitmap_set_bit (region->irr_blocks, bb->index);
1843             }
1844         }
1845     }
1846   return region;
1847 }
1848
1849 /* Collect all of the transaction regions within the current function
1850    and record them in ALL_TM_REGIONS.  The REGION parameter may specify
1851    an "outermost" region for use by tm clones.  */
1852
1853 static void
1854 tm_region_init (struct tm_region *region)
1855 {
1856   gimple g;
1857   edge_iterator ei;
1858   edge e;
1859   basic_block bb;
1860   VEC(basic_block, heap) *queue = NULL;
1861   bitmap visited_blocks = BITMAP_ALLOC (NULL);
1862   struct tm_region *old_region;
1863
1864   all_tm_regions = region;
1865   bb = single_succ (ENTRY_BLOCK_PTR);
1866
1867   VEC_safe_push (basic_block, heap, queue, bb);
1868   gcc_assert (!bb->aux);        /* FIXME: Remove me.  */
1869   bb->aux = region;
1870   do
1871     {
1872       bb = VEC_pop (basic_block, queue);
1873       region = (struct tm_region *)bb->aux;
1874       bb->aux = NULL;
1875
1876       /* Record exit and irrevocable blocks.  */
1877       region = tm_region_init_1 (region, bb);
1878
1879       /* Check for the last statement in the block beginning a new region.  */
1880       g = last_stmt (bb);
1881       old_region = region;
1882       if (g && gimple_code (g) == GIMPLE_TRANSACTION)
1883         region = tm_region_init_0 (region, bb, g);
1884
1885       /* Process subsequent blocks.  */
1886       FOR_EACH_EDGE (e, ei, bb->succs)
1887         if (!bitmap_bit_p (visited_blocks, e->dest->index))
1888           {
1889             bitmap_set_bit (visited_blocks, e->dest->index);
1890             VEC_safe_push (basic_block, heap, queue, e->dest);
1891             gcc_assert (!e->dest->aux); /* FIXME: Remove me.  */
1892
1893             /* If the current block started a new region, make sure that only
1894                the entry block of the new region is associated with this region.
1895                Other successors are still part of the old region.  */
1896             if (old_region != region && e->dest != region->entry_block)
1897               e->dest->aux = old_region;
1898             else
1899               e->dest->aux = region;
1900           }
1901     }
1902   while (!VEC_empty (basic_block, queue));
1903   VEC_free (basic_block, heap, queue);
1904   BITMAP_FREE (visited_blocks);
1905 }
1906
1907 /* The "gate" function for all transactional memory expansion and optimization
1908    passes.  We collect region information for each top-level transaction, and
1909    if we don't find any, we skip all of the TM passes.  Each region will have
1910    all of the exit blocks recorded, and the originating statement.  */
1911
1912 static bool
1913 gate_tm_init (void)
1914 {
1915   if (!flag_tm)
1916     return false;
1917
1918   calculate_dominance_info (CDI_DOMINATORS);
1919   bitmap_obstack_initialize (&tm_obstack);
1920
1921   /* If the function is a TM_CLONE, then the entire function is the region.  */
1922   if (decl_is_tm_clone (current_function_decl))
1923     {
1924       struct tm_region *region = (struct tm_region *)
1925         obstack_alloc (&tm_obstack.obstack, sizeof (struct tm_region));
1926       memset (region, 0, sizeof (*region));
1927       region->entry_block = single_succ (ENTRY_BLOCK_PTR);
1928       /* For a clone, the entire function is the region.  But even if
1929          we don't need to record any exit blocks, we may need to
1930          record irrevocable blocks.  */
1931       region->irr_blocks = BITMAP_ALLOC (&tm_obstack);
1932
1933       tm_region_init (region);
1934     }
1935   else
1936     {
1937       tm_region_init (NULL);
1938
1939       /* If we didn't find any regions, cleanup and skip the whole tree
1940          of tm-related optimizations.  */
1941       if (all_tm_regions == NULL)
1942         {
1943           bitmap_obstack_release (&tm_obstack);
1944           return false;
1945         }
1946     }
1947
1948   return true;
1949 }
1950
1951 struct gimple_opt_pass pass_tm_init =
1952 {
1953  {
1954   GIMPLE_PASS,
1955   "*tminit",                            /* name */
1956   gate_tm_init,                         /* gate */
1957   NULL,                                 /* execute */
1958   NULL,                                 /* sub */
1959   NULL,                                 /* next */
1960   0,                                    /* static_pass_number */
1961   TV_TRANS_MEM,                         /* tv_id */
1962   PROP_ssa | PROP_cfg,                  /* properties_required */
1963   0,                                    /* properties_provided */
1964   0,                                    /* properties_destroyed */
1965   0,                                    /* todo_flags_start */
1966   0,                                    /* todo_flags_finish */
1967  }
1968 };
1969 \f
1970 /* Add FLAGS to the GIMPLE_TRANSACTION subcode for the transaction region
1971    represented by STATE.  */
1972
1973 static inline void
1974 transaction_subcode_ior (struct tm_region *region, unsigned flags)
1975 {
1976   if (region && region->transaction_stmt)
1977     {
1978       flags |= gimple_transaction_subcode (region->transaction_stmt);
1979       gimple_transaction_set_subcode (region->transaction_stmt, flags);
1980     }
1981 }
1982
1983 /* Construct a memory load in a transactional context.  Return the
1984    gimple statement performing the load, or NULL if there is no
1985    TM_LOAD builtin of the appropriate size to do the load.
1986
1987    LOC is the location to use for the new statement(s).  */
1988
1989 static gimple
1990 build_tm_load (location_t loc, tree lhs, tree rhs, gimple_stmt_iterator *gsi)
1991 {
1992   enum built_in_function code = END_BUILTINS;
1993   tree t, type = TREE_TYPE (rhs), decl;
1994   gimple gcall;
1995
1996   if (type == float_type_node)
1997     code = BUILT_IN_TM_LOAD_FLOAT;
1998   else if (type == double_type_node)
1999     code = BUILT_IN_TM_LOAD_DOUBLE;
2000   else if (type == long_double_type_node)
2001     code = BUILT_IN_TM_LOAD_LDOUBLE;
2002   else if (TYPE_SIZE_UNIT (type) != NULL
2003            && host_integerp (TYPE_SIZE_UNIT (type), 1))
2004     {
2005       switch (tree_low_cst (TYPE_SIZE_UNIT (type), 1))
2006         {
2007         case 1:
2008           code = BUILT_IN_TM_LOAD_1;
2009           break;
2010         case 2:
2011           code = BUILT_IN_TM_LOAD_2;
2012           break;
2013         case 4:
2014           code = BUILT_IN_TM_LOAD_4;
2015           break;
2016         case 8:
2017           code = BUILT_IN_TM_LOAD_8;
2018           break;
2019         }
2020     }
2021
2022   if (code == END_BUILTINS)
2023     {
2024       decl = targetm.vectorize.builtin_tm_load (type);
2025       if (!decl)
2026         return NULL;
2027     }
2028   else
2029     decl = builtin_decl_explicit (code);
2030
2031   t = gimplify_addr (gsi, rhs);
2032   gcall = gimple_build_call (decl, 1, t);
2033   gimple_set_location (gcall, loc);
2034
2035   t = TREE_TYPE (TREE_TYPE (decl));
2036   if (useless_type_conversion_p (type, t))
2037     {
2038       gimple_call_set_lhs (gcall, lhs);
2039       gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2040     }
2041   else
2042     {
2043       gimple g;
2044       tree temp;
2045
2046       temp = make_rename_temp (t, NULL);
2047       gimple_call_set_lhs (gcall, temp);
2048       gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2049
2050       t = fold_build1 (VIEW_CONVERT_EXPR, type, temp);
2051       g = gimple_build_assign (lhs, t);
2052       gsi_insert_before (gsi, g, GSI_SAME_STMT);
2053     }
2054
2055   return gcall;
2056 }
2057
2058
2059 /* Similarly for storing TYPE in a transactional context.  */
2060
2061 static gimple
2062 build_tm_store (location_t loc, tree lhs, tree rhs, gimple_stmt_iterator *gsi)
2063 {
2064   enum built_in_function code = END_BUILTINS;
2065   tree t, fn, type = TREE_TYPE (rhs), simple_type;
2066   gimple gcall;
2067
2068   if (type == float_type_node)
2069     code = BUILT_IN_TM_STORE_FLOAT;
2070   else if (type == double_type_node)
2071     code = BUILT_IN_TM_STORE_DOUBLE;
2072   else if (type == long_double_type_node)
2073     code = BUILT_IN_TM_STORE_LDOUBLE;
2074   else if (TYPE_SIZE_UNIT (type) != NULL
2075            && host_integerp (TYPE_SIZE_UNIT (type), 1))
2076     {
2077       switch (tree_low_cst (TYPE_SIZE_UNIT (type), 1))
2078         {
2079         case 1:
2080           code = BUILT_IN_TM_STORE_1;
2081           break;
2082         case 2:
2083           code = BUILT_IN_TM_STORE_2;
2084           break;
2085         case 4:
2086           code = BUILT_IN_TM_STORE_4;
2087           break;
2088         case 8:
2089           code = BUILT_IN_TM_STORE_8;
2090           break;
2091         }
2092     }
2093
2094   if (code == END_BUILTINS)
2095     {
2096       fn = targetm.vectorize.builtin_tm_store (type);
2097       if (!fn)
2098         return NULL;
2099     }
2100   else
2101     fn = builtin_decl_explicit (code);
2102
2103   simple_type = TREE_VALUE (TREE_CHAIN (TYPE_ARG_TYPES (TREE_TYPE (fn))));
2104
2105   if (TREE_CODE (rhs) == CONSTRUCTOR)
2106     {
2107       /* Handle the easy initialization to zero.  */
2108       if (CONSTRUCTOR_ELTS (rhs) == 0)
2109         rhs = build_int_cst (simple_type, 0);
2110       else
2111         {
2112           /* ...otherwise punt to the caller and probably use
2113             BUILT_IN_TM_MEMMOVE, because we can't wrap a
2114             VIEW_CONVERT_EXPR around a CONSTRUCTOR (below) and produce
2115             valid gimple.  */
2116           return NULL;
2117         }
2118     }
2119   else if (!useless_type_conversion_p (simple_type, type))
2120     {
2121       gimple g;
2122       tree temp;
2123
2124       temp = make_rename_temp (simple_type, NULL);
2125       t = fold_build1 (VIEW_CONVERT_EXPR, simple_type, rhs);
2126       g = gimple_build_assign (temp, t);
2127       gimple_set_location (g, loc);
2128       gsi_insert_before (gsi, g, GSI_SAME_STMT);
2129
2130       rhs = temp;
2131     }
2132
2133   t = gimplify_addr (gsi, lhs);
2134   gcall = gimple_build_call (fn, 2, t, rhs);
2135   gimple_set_location (gcall, loc);
2136   gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2137
2138   return gcall;
2139 }
2140
2141
2142 /* Expand an assignment statement into transactional builtins.  */
2143
2144 static void
2145 expand_assign_tm (struct tm_region *region, gimple_stmt_iterator *gsi)
2146 {
2147   gimple stmt = gsi_stmt (*gsi);
2148   location_t loc = gimple_location (stmt);
2149   tree lhs = gimple_assign_lhs (stmt);
2150   tree rhs = gimple_assign_rhs1 (stmt);
2151   bool store_p = requires_barrier (region->entry_block, lhs, NULL);
2152   bool load_p = requires_barrier (region->entry_block, rhs, NULL);
2153   gimple gcall = NULL;
2154
2155   if (!load_p && !store_p)
2156     {
2157       /* Add thread private addresses to log if applicable.  */
2158       requires_barrier (region->entry_block, lhs, stmt);
2159       gsi_next (gsi);
2160       return;
2161     }
2162
2163   gsi_remove (gsi, true);
2164
2165   if (load_p && !store_p)
2166     {
2167       transaction_subcode_ior (region, GTMA_HAVE_LOAD);
2168       gcall = build_tm_load (loc, lhs, rhs, gsi);
2169     }
2170   else if (store_p && !load_p)
2171     {
2172       transaction_subcode_ior (region, GTMA_HAVE_STORE);
2173       gcall = build_tm_store (loc, lhs, rhs, gsi);
2174     }
2175   if (!gcall)
2176     {
2177       tree lhs_addr, rhs_addr;
2178
2179       if (load_p)
2180         transaction_subcode_ior (region, GTMA_HAVE_LOAD);
2181       if (store_p)
2182         transaction_subcode_ior (region, GTMA_HAVE_STORE);
2183
2184       /* ??? Figure out if there's any possible overlap between the LHS
2185          and the RHS and if not, use MEMCPY.  */
2186       lhs_addr = gimplify_addr (gsi, lhs);
2187       rhs_addr = gimplify_addr (gsi, rhs);
2188       gcall = gimple_build_call (builtin_decl_explicit (BUILT_IN_TM_MEMMOVE),
2189                                  3, lhs_addr, rhs_addr,
2190                                  TYPE_SIZE_UNIT (TREE_TYPE (lhs)));
2191       gimple_set_location (gcall, loc);
2192       gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2193     }
2194
2195   /* Now that we have the load/store in its instrumented form, add
2196      thread private addresses to the log if applicable.  */
2197   if (!store_p)
2198     requires_barrier (region->entry_block, lhs, gcall);
2199
2200   /* add_stmt_to_tm_region  (region, gcall); */
2201 }
2202
2203
2204 /* Expand a call statement as appropriate for a transaction.  That is,
2205    either verify that the call does not affect the transaction, or
2206    redirect the call to a clone that handles transactions, or change
2207    the transaction state to IRREVOCABLE.  Return true if the call is
2208    one of the builtins that end a transaction.  */
2209
2210 static bool
2211 expand_call_tm (struct tm_region *region,
2212                 gimple_stmt_iterator *gsi)
2213 {
2214   gimple stmt = gsi_stmt (*gsi);
2215   tree lhs = gimple_call_lhs (stmt);
2216   tree fn_decl;
2217   struct cgraph_node *node;
2218   bool retval = false;
2219
2220   fn_decl = gimple_call_fndecl (stmt);
2221
2222   if (fn_decl == builtin_decl_explicit (BUILT_IN_TM_MEMCPY)
2223       || fn_decl == builtin_decl_explicit (BUILT_IN_TM_MEMMOVE))
2224     transaction_subcode_ior (region, GTMA_HAVE_STORE | GTMA_HAVE_LOAD);
2225   if (fn_decl == builtin_decl_explicit (BUILT_IN_TM_MEMSET))
2226     transaction_subcode_ior (region, GTMA_HAVE_STORE);
2227
2228   if (is_tm_pure_call (stmt))
2229     return false;
2230
2231   if (fn_decl)
2232     retval = is_tm_ending_fndecl (fn_decl);
2233   if (!retval)
2234     {
2235       /* Assume all non-const/pure calls write to memory, except
2236          transaction ending builtins.  */
2237       transaction_subcode_ior (region, GTMA_HAVE_STORE);
2238     }
2239
2240   /* For indirect calls, we already generated a call into the runtime.  */
2241   if (!fn_decl)
2242     {
2243       tree fn = gimple_call_fn (stmt);
2244
2245       /* We are guaranteed never to go irrevocable on a safe or pure
2246          call, and the pure call was handled above.  */
2247       if (is_tm_safe (fn))
2248         return false;
2249       else
2250         transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
2251
2252       return false;
2253     }
2254
2255   node = cgraph_get_node (fn_decl);
2256   if (node->local.tm_may_enter_irr)
2257     transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
2258
2259   if (is_tm_abort (fn_decl))
2260     {
2261       transaction_subcode_ior (region, GTMA_HAVE_ABORT);
2262       return true;
2263     }
2264
2265   /* Instrument the store if needed.
2266
2267      If the assignment happens inside the function call (return slot
2268      optimization), there is no instrumentation to be done, since
2269      the callee should have done the right thing.  */
2270   if (lhs && requires_barrier (region->entry_block, lhs, stmt)
2271       && !gimple_call_return_slot_opt_p (stmt))
2272     {
2273       tree tmp = make_rename_temp (TREE_TYPE (lhs), NULL);
2274       location_t loc = gimple_location (stmt);
2275       edge fallthru_edge = NULL;
2276
2277       /* Remember if the call was going to throw.  */
2278       if (stmt_can_throw_internal (stmt))
2279         {
2280           edge_iterator ei;
2281           edge e;
2282           basic_block bb = gimple_bb (stmt);
2283
2284           FOR_EACH_EDGE (e, ei, bb->succs)
2285             if (e->flags & EDGE_FALLTHRU)
2286               {
2287                 fallthru_edge = e;
2288                 break;
2289               }
2290         }
2291
2292       gimple_call_set_lhs (stmt, tmp);
2293       update_stmt (stmt);
2294       stmt = gimple_build_assign (lhs, tmp);
2295       gimple_set_location (stmt, loc);
2296
2297       /* We cannot throw in the middle of a BB.  If the call was going
2298          to throw, place the instrumentation on the fallthru edge, so
2299          the call remains the last statement in the block.  */
2300       if (fallthru_edge)
2301         {
2302           gimple_seq fallthru_seq = gimple_seq_alloc_with_stmt (stmt);
2303           gimple_stmt_iterator fallthru_gsi = gsi_start (fallthru_seq);
2304           expand_assign_tm (region, &fallthru_gsi);
2305           gsi_insert_seq_on_edge (fallthru_edge, fallthru_seq);
2306           pending_edge_inserts_p = true;
2307         }
2308       else
2309         {
2310           gsi_insert_after (gsi, stmt, GSI_CONTINUE_LINKING);
2311           expand_assign_tm (region, gsi);
2312         }
2313
2314       transaction_subcode_ior (region, GTMA_HAVE_STORE);
2315     }
2316
2317   return retval;
2318 }
2319
2320
2321 /* Expand all statements in BB as appropriate for being inside
2322    a transaction.  */
2323
2324 static void
2325 expand_block_tm (struct tm_region *region, basic_block bb)
2326 {
2327   gimple_stmt_iterator gsi;
2328
2329   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2330     {
2331       gimple stmt = gsi_stmt (gsi);
2332       switch (gimple_code (stmt))
2333         {
2334         case GIMPLE_ASSIGN:
2335           /* Only memory reads/writes need to be instrumented.  */
2336           if (gimple_assign_single_p (stmt)
2337               && !gimple_clobber_p (stmt))
2338             {
2339               expand_assign_tm (region, &gsi);
2340               continue;
2341             }
2342           break;
2343
2344         case GIMPLE_CALL:
2345           if (expand_call_tm (region, &gsi))
2346             return;
2347           break;
2348
2349         case GIMPLE_ASM:
2350           gcc_unreachable ();
2351
2352         default:
2353           break;
2354         }
2355       if (!gsi_end_p (gsi))
2356         gsi_next (&gsi);
2357     }
2358 }
2359
2360 /* Return the list of basic-blocks in REGION.
2361
2362    STOP_AT_IRREVOCABLE_P is true if caller is uninterested in blocks
2363    following a TM_IRREVOCABLE call.  */
2364
2365 static VEC (basic_block, heap) *
2366 get_tm_region_blocks (basic_block entry_block,
2367                       bitmap exit_blocks,
2368                       bitmap irr_blocks,
2369                       bitmap all_region_blocks,
2370                       bool stop_at_irrevocable_p)
2371 {
2372   VEC(basic_block, heap) *bbs = NULL;
2373   unsigned i;
2374   edge e;
2375   edge_iterator ei;
2376   bitmap visited_blocks = BITMAP_ALLOC (NULL);
2377
2378   i = 0;
2379   VEC_safe_push (basic_block, heap, bbs, entry_block);
2380   bitmap_set_bit (visited_blocks, entry_block->index);
2381
2382   do
2383     {
2384       basic_block bb = VEC_index (basic_block, bbs, i++);
2385
2386       if (exit_blocks &&
2387           bitmap_bit_p (exit_blocks, bb->index))
2388         continue;
2389
2390       if (stop_at_irrevocable_p
2391           && irr_blocks
2392           && bitmap_bit_p (irr_blocks, bb->index))
2393         continue;
2394
2395       FOR_EACH_EDGE (e, ei, bb->succs)
2396         if (!bitmap_bit_p (visited_blocks, e->dest->index))
2397           {
2398             bitmap_set_bit (visited_blocks, e->dest->index);
2399             VEC_safe_push (basic_block, heap, bbs, e->dest);
2400           }
2401     }
2402   while (i < VEC_length (basic_block, bbs));
2403
2404   if (all_region_blocks)
2405     bitmap_ior_into (all_region_blocks, visited_blocks);
2406
2407   BITMAP_FREE (visited_blocks);
2408   return bbs;
2409 }
2410
2411 /* Entry point to the MARK phase of TM expansion.  Here we replace
2412    transactional memory statements with calls to builtins, and function
2413    calls with their transactional clones (if available).  But we don't
2414    yet lower GIMPLE_TRANSACTION or add the transaction restart back-edges.  */
2415
2416 static unsigned int
2417 execute_tm_mark (void)
2418 {
2419   struct tm_region *region;
2420   basic_block bb;
2421   VEC (basic_block, heap) *queue;
2422   size_t i;
2423
2424   queue = VEC_alloc (basic_block, heap, 10);
2425   pending_edge_inserts_p = false;
2426
2427   for (region = all_tm_regions; region ; region = region->next)
2428     {
2429       tm_log_init ();
2430       /* If we have a transaction...  */
2431       if (region->exit_blocks)
2432         {
2433           unsigned int subcode
2434             = gimple_transaction_subcode (region->transaction_stmt);
2435
2436           /* Collect a new SUBCODE set, now that optimizations are done...  */
2437           if (subcode & GTMA_DOES_GO_IRREVOCABLE)
2438             subcode &= (GTMA_DECLARATION_MASK | GTMA_DOES_GO_IRREVOCABLE
2439                         | GTMA_MAY_ENTER_IRREVOCABLE);
2440           else
2441             subcode &= GTMA_DECLARATION_MASK;
2442           gimple_transaction_set_subcode (region->transaction_stmt, subcode);
2443         }
2444
2445       queue = get_tm_region_blocks (region->entry_block,
2446                                     region->exit_blocks,
2447                                     region->irr_blocks,
2448                                     NULL,
2449                                     /*stop_at_irr_p=*/true);
2450       for (i = 0; VEC_iterate (basic_block, queue, i, bb); ++i)
2451         expand_block_tm (region, bb);
2452       VEC_free (basic_block, heap, queue);
2453
2454       tm_log_emit ();
2455     }
2456
2457   if (pending_edge_inserts_p)
2458     gsi_commit_edge_inserts ();
2459   return 0;
2460 }
2461
2462 struct gimple_opt_pass pass_tm_mark =
2463 {
2464  {
2465   GIMPLE_PASS,
2466   "tmmark",                             /* name */
2467   NULL,                                 /* gate */
2468   execute_tm_mark,                      /* execute */
2469   NULL,                                 /* sub */
2470   NULL,                                 /* next */
2471   0,                                    /* static_pass_number */
2472   TV_TRANS_MEM,                         /* tv_id */
2473   PROP_ssa | PROP_cfg,                  /* properties_required */
2474   0,                                    /* properties_provided */
2475   0,                                    /* properties_destroyed */
2476   0,                                    /* todo_flags_start */
2477   TODO_update_ssa
2478   | TODO_verify_ssa
2479   | TODO_dump_func,                     /* todo_flags_finish */
2480  }
2481 };
2482 \f
2483 /* Create an abnormal call edge from BB to the first block of the region
2484    represented by STATE.  Also record the edge in the TM_RESTART map.  */
2485
2486 static inline void
2487 make_tm_edge (gimple stmt, basic_block bb, struct tm_region *region)
2488 {
2489   void **slot;
2490   struct tm_restart_node *n, dummy;
2491
2492   if (cfun->gimple_df->tm_restart == NULL)
2493     cfun->gimple_df->tm_restart = htab_create_ggc (31, struct_ptr_hash,
2494                                                    struct_ptr_eq, ggc_free);
2495
2496   dummy.stmt = stmt;
2497   dummy.label_or_list = gimple_block_label (region->entry_block);
2498   slot = htab_find_slot (cfun->gimple_df->tm_restart, &dummy, INSERT);
2499   n = (struct tm_restart_node *) *slot;
2500   if (n == NULL)
2501     {
2502       n = ggc_alloc_tm_restart_node ();
2503       *n = dummy;
2504     }
2505   else
2506     {
2507       tree old = n->label_or_list;
2508       if (TREE_CODE (old) == LABEL_DECL)
2509         old = tree_cons (NULL, old, NULL);
2510       n->label_or_list = tree_cons (NULL, dummy.label_or_list, old);
2511     }
2512
2513   make_edge (bb, region->entry_block, EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
2514 }
2515
2516
2517 /* Split block BB as necessary for every builtin function we added, and
2518    wire up the abnormal back edges implied by the transaction restart.  */
2519
2520 static void
2521 expand_block_edges (struct tm_region *region, basic_block bb)
2522 {
2523   gimple_stmt_iterator gsi;
2524
2525   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2526     {
2527       gimple stmt = gsi_stmt (gsi);
2528
2529       /* ??? TM_COMMIT (and any other tm builtin function) in a nested
2530          transaction has an abnormal edge back to the outer-most transaction
2531          (there are no nested retries), while a TM_ABORT also has an abnormal
2532          backedge to the inner-most transaction.  We haven't actually saved
2533          the inner-most transaction here.  We should be able to get to it
2534          via the region_nr saved on STMT, and read the transaction_stmt from
2535          that, and find the first region block from there.  */
2536       /* ??? Shouldn't we split for any non-pure, non-irrevocable function?  */
2537       if (gimple_code (stmt) == GIMPLE_CALL
2538           && (gimple_call_flags (stmt) & ECF_TM_BUILTIN) != 0)
2539         {
2540           if (gsi_one_before_end_p (gsi))
2541             make_tm_edge (stmt, bb, region);
2542           else
2543             {
2544               edge e = split_block (bb, stmt);
2545               make_tm_edge (stmt, bb, region);
2546               bb = e->dest;
2547               gsi = gsi_start_bb (bb);
2548             }
2549
2550           /* Delete any tail-call annotation that may have been added.
2551              The tail-call pass may have mis-identified the commit as being
2552              a candidate because we had not yet added this restart edge.  */
2553           gimple_call_set_tail (stmt, false);
2554         }
2555
2556       gsi_next (&gsi);
2557     }
2558 }
2559
2560 /* Expand the GIMPLE_TRANSACTION statement into the STM library call.  */
2561
2562 static void
2563 expand_transaction (struct tm_region *region)
2564 {
2565   tree status, tm_start;
2566   basic_block atomic_bb, slice_bb;
2567   gimple_stmt_iterator gsi;
2568   tree t1, t2;
2569   gimple g;
2570   int flags, subcode;
2571
2572   tm_start = builtin_decl_explicit (BUILT_IN_TM_START);
2573   status = make_rename_temp (TREE_TYPE (TREE_TYPE (tm_start)), "tm_state");
2574
2575   /* ??? There are plenty of bits here we're not computing.  */
2576   subcode = gimple_transaction_subcode (region->transaction_stmt);
2577   if (subcode & GTMA_DOES_GO_IRREVOCABLE)
2578     flags = PR_DOESGOIRREVOCABLE | PR_UNINSTRUMENTEDCODE;
2579   else
2580     flags = PR_INSTRUMENTEDCODE;
2581   if ((subcode & GTMA_MAY_ENTER_IRREVOCABLE) == 0)
2582     flags |= PR_HASNOIRREVOCABLE;
2583   /* If the transaction does not have an abort in lexical scope and is not
2584      marked as an outer transaction, then it will never abort.  */
2585   if ((subcode & GTMA_HAVE_ABORT) == 0
2586       && (subcode & GTMA_IS_OUTER) == 0)
2587     flags |= PR_HASNOABORT;
2588   if ((subcode & GTMA_HAVE_STORE) == 0)
2589     flags |= PR_READONLY;
2590   t2 = build_int_cst (TREE_TYPE (status), flags);
2591   g = gimple_build_call (tm_start, 1, t2);
2592   gimple_call_set_lhs (g, status);
2593   gimple_set_location (g, gimple_location (region->transaction_stmt));
2594
2595   atomic_bb = gimple_bb (region->transaction_stmt);
2596
2597   if (!VEC_empty (tree, tm_log_save_addresses))
2598     tm_log_emit_saves (region->entry_block, atomic_bb);
2599
2600   gsi = gsi_last_bb (atomic_bb);
2601   gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2602   gsi_remove (&gsi, true);
2603
2604   if (!VEC_empty (tree, tm_log_save_addresses))
2605     region->entry_block =
2606       tm_log_emit_save_or_restores (region->entry_block,
2607                                     A_RESTORELIVEVARIABLES,
2608                                     status,
2609                                     tm_log_emit_restores,
2610                                     atomic_bb,
2611                                     FALLTHRU_EDGE (atomic_bb),
2612                                     &slice_bb);
2613   else
2614     slice_bb = atomic_bb;
2615
2616   /* If we have an ABORT statement, create a test following the start
2617      call to perform the abort.  */
2618   if (gimple_transaction_label (region->transaction_stmt))
2619     {
2620       edge e;
2621       basic_block test_bb;
2622
2623       test_bb = create_empty_bb (slice_bb);
2624       if (VEC_empty (tree, tm_log_save_addresses))
2625         region->entry_block = test_bb;
2626       gsi = gsi_last_bb (test_bb);
2627
2628       t1 = make_rename_temp (TREE_TYPE (status), NULL);
2629       t2 = build_int_cst (TREE_TYPE (status), A_ABORTTRANSACTION);
2630       g = gimple_build_assign_with_ops (BIT_AND_EXPR, t1, status, t2);
2631       gsi_insert_after (&gsi, g, GSI_CONTINUE_LINKING);
2632
2633       t2 = build_int_cst (TREE_TYPE (status), 0);
2634       g = gimple_build_cond (NE_EXPR, t1, t2, NULL, NULL);
2635       gsi_insert_after (&gsi, g, GSI_CONTINUE_LINKING);
2636
2637       e = FALLTHRU_EDGE (slice_bb);
2638       redirect_edge_pred (e, test_bb);
2639       e->flags = EDGE_FALSE_VALUE;
2640       e->probability = PROB_ALWAYS - PROB_VERY_UNLIKELY;
2641
2642       e = BRANCH_EDGE (atomic_bb);
2643       redirect_edge_pred (e, test_bb);
2644       e->flags = EDGE_TRUE_VALUE;
2645       e->probability = PROB_VERY_UNLIKELY;
2646
2647       e = make_edge (slice_bb, test_bb, EDGE_FALLTHRU);
2648     }
2649
2650   /* If we've no abort, but we do have PHIs at the beginning of the atomic
2651      region, that means we've a loop at the beginning of the atomic region
2652      that shares the first block.  This can cause problems with the abnormal
2653      edges we're about to add for the transaction restart.  Solve this by
2654      adding a new empty block to receive the abnormal edges.  */
2655   else if (phi_nodes (region->entry_block))
2656     {
2657       edge e;
2658       basic_block empty_bb;
2659
2660       region->entry_block = empty_bb = create_empty_bb (atomic_bb);
2661
2662       e = FALLTHRU_EDGE (atomic_bb);
2663       redirect_edge_pred (e, empty_bb);
2664
2665       e = make_edge (atomic_bb, empty_bb, EDGE_FALLTHRU);
2666     }
2667
2668   /* The GIMPLE_TRANSACTION statement no longer exists.  */
2669   region->transaction_stmt = NULL;
2670 }
2671
2672 static void expand_regions (struct tm_region *);
2673
2674 /* Helper function for expand_regions.  Expand REGION and recurse to
2675    the inner region.  */
2676
2677 static void
2678 expand_regions_1 (struct tm_region *region)
2679 {
2680   if (region->exit_blocks)
2681     {
2682       unsigned int i;
2683       basic_block bb;
2684       VEC (basic_block, heap) *queue;
2685
2686       /* Collect the set of blocks in this region.  Do this before
2687          splitting edges, so that we don't have to play with the
2688          dominator tree in the middle.  */
2689       queue = get_tm_region_blocks (region->entry_block,
2690                                     region->exit_blocks,
2691                                     region->irr_blocks,
2692                                     NULL,
2693                                     /*stop_at_irr_p=*/false);
2694       expand_transaction (region);
2695       for (i = 0; VEC_iterate (basic_block, queue, i, bb); ++i)
2696         expand_block_edges (region, bb);
2697       VEC_free (basic_block, heap, queue);
2698     }
2699   if (region->inner)
2700     expand_regions (region->inner);
2701 }
2702
2703 /* Expand regions starting at REGION.  */
2704
2705 static void
2706 expand_regions (struct tm_region *region)
2707 {
2708   while (region)
2709     {
2710       expand_regions_1 (region);
2711       region = region->next;
2712     }
2713 }
2714
2715 /* Entry point to the final expansion of transactional nodes. */
2716
2717 static unsigned int
2718 execute_tm_edges (void)
2719 {
2720   expand_regions (all_tm_regions);
2721   tm_log_delete ();
2722
2723   /* We've got to release the dominance info now, to indicate that it
2724      must be rebuilt completely.  Otherwise we'll crash trying to update
2725      the SSA web in the TODO section following this pass.  */
2726   free_dominance_info (CDI_DOMINATORS);
2727   bitmap_obstack_release (&tm_obstack);
2728   all_tm_regions = NULL;
2729
2730   return 0;
2731 }
2732
2733 struct gimple_opt_pass pass_tm_edges =
2734 {
2735  {
2736   GIMPLE_PASS,
2737   "tmedge",                             /* name */
2738   NULL,                                 /* gate */
2739   execute_tm_edges,                     /* execute */
2740   NULL,                                 /* sub */
2741   NULL,                                 /* next */
2742   0,                                    /* static_pass_number */
2743   TV_TRANS_MEM,                         /* tv_id */
2744   PROP_ssa | PROP_cfg,                  /* properties_required */
2745   0,                                    /* properties_provided */
2746   0,                                    /* properties_destroyed */
2747   0,                                    /* todo_flags_start */
2748   TODO_update_ssa
2749   | TODO_verify_ssa
2750   | TODO_dump_func,                     /* todo_flags_finish */
2751  }
2752 };
2753 \f
2754 /* A unique TM memory operation.  */
2755 typedef struct tm_memop
2756 {
2757   /* Unique ID that all memory operations to the same location have.  */
2758   unsigned int value_id;
2759   /* Address of load/store.  */
2760   tree addr;
2761 } *tm_memop_t;
2762
2763 /* Sets for solving data flow equations in the memory optimization pass.  */
2764 struct tm_memopt_bitmaps
2765 {
2766   /* Stores available to this BB upon entry.  Basically, stores that
2767      dominate this BB.  */
2768   bitmap store_avail_in;
2769   /* Stores available at the end of this BB.  */
2770   bitmap store_avail_out;
2771   bitmap store_antic_in;
2772   bitmap store_antic_out;
2773   /* Reads available to this BB upon entry.  Basically, reads that
2774      dominate this BB.  */
2775   bitmap read_avail_in;
2776   /* Reads available at the end of this BB.  */
2777   bitmap read_avail_out;
2778   /* Reads performed in this BB.  */
2779   bitmap read_local;
2780   /* Writes performed in this BB.  */
2781   bitmap store_local;
2782
2783   /* Temporary storage for pass.  */
2784   /* Is the current BB in the worklist?  */
2785   bool avail_in_worklist_p;
2786   /* Have we visited this BB?  */
2787   bool visited_p;
2788 };
2789
2790 static bitmap_obstack tm_memopt_obstack;
2791
2792 /* Unique counter for TM loads and stores. Loads and stores of the
2793    same address get the same ID.  */
2794 static unsigned int tm_memopt_value_id;
2795 static htab_t tm_memopt_value_numbers;
2796
2797 #define STORE_AVAIL_IN(BB) \
2798   ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_avail_in
2799 #define STORE_AVAIL_OUT(BB) \
2800   ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_avail_out
2801 #define STORE_ANTIC_IN(BB) \
2802   ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_antic_in
2803 #define STORE_ANTIC_OUT(BB) \
2804   ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_antic_out
2805 #define READ_AVAIL_IN(BB) \
2806   ((struct tm_memopt_bitmaps *) ((BB)->aux))->read_avail_in
2807 #define READ_AVAIL_OUT(BB) \
2808   ((struct tm_memopt_bitmaps *) ((BB)->aux))->read_avail_out
2809 #define READ_LOCAL(BB) \
2810   ((struct tm_memopt_bitmaps *) ((BB)->aux))->read_local
2811 #define STORE_LOCAL(BB) \
2812   ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_local
2813 #define AVAIL_IN_WORKLIST_P(BB) \
2814   ((struct tm_memopt_bitmaps *) ((BB)->aux))->avail_in_worklist_p
2815 #define BB_VISITED_P(BB) \
2816   ((struct tm_memopt_bitmaps *) ((BB)->aux))->visited_p
2817
2818 /* Htab support.  Return a hash value for a `tm_memop'.  */
2819 static hashval_t
2820 tm_memop_hash (const void *p)
2821 {
2822   const struct tm_memop *mem = (const struct tm_memop *) p;
2823   tree addr = mem->addr;
2824   /* We drill down to the SSA_NAME/DECL for the hash, but equality is
2825      actually done with operand_equal_p (see tm_memop_eq).  */
2826   if (TREE_CODE (addr) == ADDR_EXPR)
2827     addr = TREE_OPERAND (addr, 0);
2828   return iterative_hash_expr (addr, 0);
2829 }
2830
2831 /* Htab support.  Return true if two tm_memop's are the same.  */
2832 static int
2833 tm_memop_eq (const void *p1, const void *p2)
2834 {
2835   const struct tm_memop *mem1 = (const struct tm_memop *) p1;
2836   const struct tm_memop *mem2 = (const struct tm_memop *) p2;
2837
2838   return operand_equal_p (mem1->addr, mem2->addr, 0);
2839 }
2840
2841 /* Given a TM load/store in STMT, return the value number for the address
2842    it accesses.  */
2843
2844 static unsigned int
2845 tm_memopt_value_number (gimple stmt, enum insert_option op)
2846 {
2847   struct tm_memop tmpmem, *mem;
2848   void **slot;
2849
2850   gcc_assert (is_tm_load (stmt) || is_tm_store (stmt));
2851   tmpmem.addr = gimple_call_arg (stmt, 0);
2852   slot = htab_find_slot (tm_memopt_value_numbers, &tmpmem, op);
2853   if (*slot)
2854     mem = (struct tm_memop *) *slot;
2855   else if (op == INSERT)
2856     {
2857       mem = XNEW (struct tm_memop);
2858       *slot = mem;
2859       mem->value_id = tm_memopt_value_id++;
2860       mem->addr = tmpmem.addr;
2861     }
2862   else
2863     gcc_unreachable ();
2864   return mem->value_id;
2865 }
2866
2867 /* Accumulate TM memory operations in BB into STORE_LOCAL and READ_LOCAL.  */
2868
2869 static void
2870 tm_memopt_accumulate_memops (basic_block bb)
2871 {
2872   gimple_stmt_iterator gsi;
2873
2874   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2875     {
2876       gimple stmt = gsi_stmt (gsi);
2877       bitmap bits;
2878       unsigned int loc;
2879
2880       if (is_tm_store (stmt))
2881         bits = STORE_LOCAL (bb);
2882       else if (is_tm_load (stmt))
2883         bits = READ_LOCAL (bb);
2884       else
2885         continue;
2886
2887       loc = tm_memopt_value_number (stmt, INSERT);
2888       bitmap_set_bit (bits, loc);
2889       if (dump_file)
2890         {
2891           fprintf (dump_file, "TM memopt (%s): value num=%d, BB=%d, addr=",
2892                    is_tm_load (stmt) ? "LOAD" : "STORE", loc,
2893                    gimple_bb (stmt)->index);
2894           print_generic_expr (dump_file, gimple_call_arg (stmt, 0), 0);
2895           fprintf (dump_file, "\n");
2896         }
2897     }
2898 }
2899
2900 /* Prettily dump one of the memopt sets.  BITS is the bitmap to dump.  */
2901
2902 static void
2903 dump_tm_memopt_set (const char *set_name, bitmap bits)
2904 {
2905   unsigned i;
2906   bitmap_iterator bi;
2907   const char *comma = "";
2908
2909   fprintf (dump_file, "TM memopt: %s: [", set_name);
2910   EXECUTE_IF_SET_IN_BITMAP (bits, 0, i, bi)
2911     {
2912       htab_iterator hi;
2913       struct tm_memop *mem;
2914
2915       /* Yeah, yeah, yeah.  Whatever.  This is just for debugging.  */
2916       FOR_EACH_HTAB_ELEMENT (tm_memopt_value_numbers, mem, tm_memop_t, hi)
2917         if (mem->value_id == i)
2918           break;
2919       gcc_assert (mem->value_id == i);
2920       fprintf (dump_file, "%s", comma);
2921       comma = ", ";
2922       print_generic_expr (dump_file, mem->addr, 0);
2923     }
2924   fprintf (dump_file, "]\n");
2925 }
2926
2927 /* Prettily dump all of the memopt sets in BLOCKS.  */
2928
2929 static void
2930 dump_tm_memopt_sets (VEC (basic_block, heap) *blocks)
2931 {
2932   size_t i;
2933   basic_block bb;
2934
2935   for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
2936     {
2937       fprintf (dump_file, "------------BB %d---------\n", bb->index);
2938       dump_tm_memopt_set ("STORE_LOCAL", STORE_LOCAL (bb));
2939       dump_tm_memopt_set ("READ_LOCAL", READ_LOCAL (bb));
2940       dump_tm_memopt_set ("STORE_AVAIL_IN", STORE_AVAIL_IN (bb));
2941       dump_tm_memopt_set ("STORE_AVAIL_OUT", STORE_AVAIL_OUT (bb));
2942       dump_tm_memopt_set ("READ_AVAIL_IN", READ_AVAIL_IN (bb));
2943       dump_tm_memopt_set ("READ_AVAIL_OUT", READ_AVAIL_OUT (bb));
2944     }
2945 }
2946
2947 /* Compute {STORE,READ}_AVAIL_IN for the basic block BB.  */
2948
2949 static void
2950 tm_memopt_compute_avin (basic_block bb)
2951 {
2952   edge e;
2953   unsigned ix;
2954
2955   /* Seed with the AVOUT of any predecessor.  */
2956   for (ix = 0; ix < EDGE_COUNT (bb->preds); ix++)
2957     {
2958       e = EDGE_PRED (bb, ix);
2959       /* Make sure we have already visited this BB, and is thus
2960          initialized.
2961
2962           If e->src->aux is NULL, this predecessor is actually on an
2963           enclosing transaction.  We only care about the current
2964           transaction, so ignore it.  */
2965       if (e->src->aux && BB_VISITED_P (e->src))
2966         {
2967           bitmap_copy (STORE_AVAIL_IN (bb), STORE_AVAIL_OUT (e->src));
2968           bitmap_copy (READ_AVAIL_IN (bb), READ_AVAIL_OUT (e->src));
2969           break;
2970         }
2971     }
2972
2973   for (; ix < EDGE_COUNT (bb->preds); ix++)
2974     {
2975       e = EDGE_PRED (bb, ix);
2976       if (e->src->aux && BB_VISITED_P (e->src))
2977         {
2978           bitmap_and_into (STORE_AVAIL_IN (bb), STORE_AVAIL_OUT (e->src));
2979           bitmap_and_into (READ_AVAIL_IN (bb), READ_AVAIL_OUT (e->src));
2980         }
2981     }
2982
2983   BB_VISITED_P (bb) = true;
2984 }
2985
2986 /* Compute the STORE_ANTIC_IN for the basic block BB.  */
2987
2988 static void
2989 tm_memopt_compute_antin (basic_block bb)
2990 {
2991   edge e;
2992   unsigned ix;
2993
2994   /* Seed with the ANTIC_OUT of any successor.  */
2995   for (ix = 0; ix < EDGE_COUNT (bb->succs); ix++)
2996     {
2997       e = EDGE_SUCC (bb, ix);
2998       /* Make sure we have already visited this BB, and is thus
2999          initialized.  */
3000       if (BB_VISITED_P (e->dest))
3001         {
3002           bitmap_copy (STORE_ANTIC_IN (bb), STORE_ANTIC_OUT (e->dest));
3003           break;
3004         }
3005     }
3006
3007   for (; ix < EDGE_COUNT (bb->succs); ix++)
3008     {
3009       e = EDGE_SUCC (bb, ix);
3010       if (BB_VISITED_P  (e->dest))
3011         bitmap_and_into (STORE_ANTIC_IN (bb), STORE_ANTIC_OUT (e->dest));
3012     }
3013
3014   BB_VISITED_P (bb) = true;
3015 }
3016
3017 /* Compute the AVAIL sets for every basic block in BLOCKS.
3018
3019    We compute {STORE,READ}_AVAIL_{OUT,IN} as follows:
3020
3021      AVAIL_OUT[bb] = union (AVAIL_IN[bb], LOCAL[bb])
3022      AVAIL_IN[bb]  = intersect (AVAIL_OUT[predecessors])
3023
3024    This is basically what we do in lcm's compute_available(), but here
3025    we calculate two sets of sets (one for STOREs and one for READs),
3026    and we work on a region instead of the entire CFG.
3027
3028    REGION is the TM region.
3029    BLOCKS are the basic blocks in the region.  */
3030
3031 static void
3032 tm_memopt_compute_available (struct tm_region *region,
3033                              VEC (basic_block, heap) *blocks)
3034 {
3035   edge e;
3036   basic_block *worklist, *qin, *qout, *qend, bb;
3037   unsigned int qlen, i;
3038   edge_iterator ei;
3039   bool changed;
3040
3041   /* Allocate a worklist array/queue.  Entries are only added to the
3042      list if they were not already on the list.  So the size is
3043      bounded by the number of basic blocks in the region.  */
3044   qlen = VEC_length (basic_block, blocks) - 1;
3045   qin = qout = worklist =
3046     XNEWVEC (basic_block, qlen);
3047
3048   /* Put every block in the region on the worklist.  */
3049   for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
3050     {
3051       /* Seed AVAIL_OUT with the LOCAL set.  */
3052       bitmap_ior_into (STORE_AVAIL_OUT (bb), STORE_LOCAL (bb));
3053       bitmap_ior_into (READ_AVAIL_OUT (bb), READ_LOCAL (bb));
3054
3055       AVAIL_IN_WORKLIST_P (bb) = true;
3056       /* No need to insert the entry block, since it has an AVIN of
3057          null, and an AVOUT that has already been seeded in.  */
3058       if (bb != region->entry_block)
3059         *qin++ = bb;
3060     }
3061
3062   /* The entry block has been initialized with the local sets.  */
3063   BB_VISITED_P (region->entry_block) = true;
3064
3065   qin = worklist;
3066   qend = &worklist[qlen];
3067
3068   /* Iterate until the worklist is empty.  */
3069   while (qlen)
3070     {
3071       /* Take the first entry off the worklist.  */
3072       bb = *qout++;
3073       qlen--;
3074
3075       if (qout >= qend)
3076         qout = worklist;
3077
3078       /* This block can be added to the worklist again if necessary.  */
3079       AVAIL_IN_WORKLIST_P (bb) = false;
3080       tm_memopt_compute_avin (bb);
3081
3082       /* Note: We do not add the LOCAL sets here because we already
3083          seeded the AVAIL_OUT sets with them.  */
3084       changed  = bitmap_ior_into (STORE_AVAIL_OUT (bb), STORE_AVAIL_IN (bb));
3085       changed |= bitmap_ior_into (READ_AVAIL_OUT (bb), READ_AVAIL_IN (bb));
3086       if (changed
3087           && (region->exit_blocks == NULL
3088               || !bitmap_bit_p (region->exit_blocks, bb->index)))
3089         /* If the out state of this block changed, then we need to add
3090            its successors to the worklist if they are not already in.  */
3091         FOR_EACH_EDGE (e, ei, bb->succs)
3092           if (!AVAIL_IN_WORKLIST_P (e->dest) && e->dest != EXIT_BLOCK_PTR)
3093             {
3094               *qin++ = e->dest;
3095               AVAIL_IN_WORKLIST_P (e->dest) = true;
3096               qlen++;
3097
3098               if (qin >= qend)
3099                 qin = worklist;
3100             }
3101     }
3102
3103   free (worklist);
3104
3105   if (dump_file)
3106     dump_tm_memopt_sets (blocks);
3107 }
3108
3109 /* Compute ANTIC sets for every basic block in BLOCKS.
3110
3111    We compute STORE_ANTIC_OUT as follows:
3112
3113         STORE_ANTIC_OUT[bb] = union(STORE_ANTIC_IN[bb], STORE_LOCAL[bb])
3114         STORE_ANTIC_IN[bb]  = intersect(STORE_ANTIC_OUT[successors])
3115
3116    REGION is the TM region.
3117    BLOCKS are the basic blocks in the region.  */
3118
3119 static void
3120 tm_memopt_compute_antic (struct tm_region *region,
3121                          VEC (basic_block, heap) *blocks)
3122 {
3123   edge e;
3124   basic_block *worklist, *qin, *qout, *qend, bb;
3125   unsigned int qlen;
3126   int i;
3127   edge_iterator ei;
3128
3129   /* Allocate a worklist array/queue.  Entries are only added to the
3130      list if they were not already on the list.  So the size is
3131      bounded by the number of basic blocks in the region.  */
3132   qin = qout = worklist =
3133     XNEWVEC (basic_block, VEC_length (basic_block, blocks));
3134
3135   for (qlen = 0, i = VEC_length (basic_block, blocks) - 1; i >= 0; --i)
3136     {
3137       bb = VEC_index (basic_block, blocks, i);
3138
3139       /* Seed ANTIC_OUT with the LOCAL set.  */
3140       bitmap_ior_into (STORE_ANTIC_OUT (bb), STORE_LOCAL (bb));
3141
3142       /* Put every block in the region on the worklist.  */
3143       AVAIL_IN_WORKLIST_P (bb) = true;
3144       /* No need to insert exit blocks, since their ANTIC_IN is NULL,
3145          and their ANTIC_OUT has already been seeded in.  */
3146       if (region->exit_blocks
3147           && !bitmap_bit_p (region->exit_blocks, bb->index))
3148         {
3149           qlen++;
3150           *qin++ = bb;
3151         }
3152     }
3153
3154   /* The exit blocks have been initialized with the local sets.  */
3155   if (region->exit_blocks)
3156     {
3157       unsigned int i;
3158       bitmap_iterator bi;
3159       EXECUTE_IF_SET_IN_BITMAP (region->exit_blocks, 0, i, bi)
3160         BB_VISITED_P (BASIC_BLOCK (i)) = true;
3161     }
3162
3163   qin = worklist;
3164   qend = &worklist[qlen];
3165
3166   /* Iterate until the worklist is empty.  */
3167   while (qlen)
3168     {
3169       /* Take the first entry off the worklist.  */
3170       bb = *qout++;
3171       qlen--;
3172
3173       if (qout >= qend)
3174         qout = worklist;
3175
3176       /* This block can be added to the worklist again if necessary.  */
3177       AVAIL_IN_WORKLIST_P (bb) = false;
3178       tm_memopt_compute_antin (bb);
3179
3180       /* Note: We do not add the LOCAL sets here because we already
3181          seeded the ANTIC_OUT sets with them.  */
3182       if (bitmap_ior_into (STORE_ANTIC_OUT (bb), STORE_ANTIC_IN (bb))
3183           && bb != region->entry_block)
3184         /* If the out state of this block changed, then we need to add
3185            its predecessors to the worklist if they are not already in.  */
3186         FOR_EACH_EDGE (e, ei, bb->preds)
3187           if (!AVAIL_IN_WORKLIST_P (e->src))
3188             {
3189               *qin++ = e->src;
3190               AVAIL_IN_WORKLIST_P (e->src) = true;
3191               qlen++;
3192
3193               if (qin >= qend)
3194                 qin = worklist;
3195             }
3196     }
3197
3198   free (worklist);
3199
3200   if (dump_file)
3201     dump_tm_memopt_sets (blocks);
3202 }
3203
3204 /* Offsets of load variants from TM_LOAD.  For example,
3205    BUILT_IN_TM_LOAD_RAR* is an offset of 1 from BUILT_IN_TM_LOAD*.
3206    See gtm-builtins.def.  */
3207 #define TRANSFORM_RAR 1
3208 #define TRANSFORM_RAW 2
3209 #define TRANSFORM_RFW 3
3210 /* Offsets of store variants from TM_STORE.  */
3211 #define TRANSFORM_WAR 1
3212 #define TRANSFORM_WAW 2
3213
3214 /* Inform about a load/store optimization.  */
3215
3216 static void
3217 dump_tm_memopt_transform (gimple stmt)
3218 {
3219   if (dump_file)
3220     {
3221       fprintf (dump_file, "TM memopt: transforming: ");
3222       print_gimple_stmt (dump_file, stmt, 0, 0);
3223       fprintf (dump_file, "\n");
3224     }
3225 }
3226
3227 /* Perform a read/write optimization.  Replaces the TM builtin in STMT
3228    by a builtin that is OFFSET entries down in the builtins table in
3229    gtm-builtins.def.  */
3230
3231 static void
3232 tm_memopt_transform_stmt (unsigned int offset,
3233                           gimple stmt,
3234                           gimple_stmt_iterator *gsi)
3235 {
3236   tree fn = gimple_call_fn (stmt);
3237   gcc_assert (TREE_CODE (fn) == ADDR_EXPR);
3238   TREE_OPERAND (fn, 0)
3239     = builtin_decl_explicit ((enum built_in_function)
3240                              (DECL_FUNCTION_CODE (TREE_OPERAND (fn, 0))
3241                               + offset));
3242   gimple_call_set_fn (stmt, fn);
3243   gsi_replace (gsi, stmt, true);
3244   dump_tm_memopt_transform (stmt);
3245 }
3246
3247 /* Perform the actual TM memory optimization transformations in the
3248    basic blocks in BLOCKS.  */
3249
3250 static void
3251 tm_memopt_transform_blocks (VEC (basic_block, heap) *blocks)
3252 {
3253   size_t i;
3254   basic_block bb;
3255   gimple_stmt_iterator gsi;
3256
3257   for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
3258     {
3259       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3260         {
3261           gimple stmt = gsi_stmt (gsi);
3262           bitmap read_avail = READ_AVAIL_IN (bb);
3263           bitmap store_avail = STORE_AVAIL_IN (bb);
3264           bitmap store_antic = STORE_ANTIC_OUT (bb);
3265           unsigned int loc;
3266
3267           if (is_tm_simple_load (stmt))
3268             {
3269               loc = tm_memopt_value_number (stmt, NO_INSERT);
3270               if (store_avail && bitmap_bit_p (store_avail, loc))
3271                 tm_memopt_transform_stmt (TRANSFORM_RAW, stmt, &gsi);
3272               else if (store_antic && bitmap_bit_p (store_antic, loc))
3273                 {
3274                   tm_memopt_transform_stmt (TRANSFORM_RFW, stmt, &gsi);
3275                   bitmap_set_bit (store_avail, loc);
3276                 }
3277               else if (read_avail && bitmap_bit_p (read_avail, loc))
3278                 tm_memopt_transform_stmt (TRANSFORM_RAR, stmt, &gsi);
3279               else
3280                 bitmap_set_bit (read_avail, loc);
3281             }
3282           else if (is_tm_simple_store (stmt))
3283             {
3284               loc = tm_memopt_value_number (stmt, NO_INSERT);
3285               if (store_avail && bitmap_bit_p (store_avail, loc))
3286                 tm_memopt_transform_stmt (TRANSFORM_WAW, stmt, &gsi);
3287               else
3288                 {
3289                   if (read_avail && bitmap_bit_p (read_avail, loc))
3290                     tm_memopt_transform_stmt (TRANSFORM_WAR, stmt, &gsi);
3291                   bitmap_set_bit (store_avail, loc);
3292                 }
3293             }
3294         }
3295     }
3296 }
3297
3298 /* Return a new set of bitmaps for a BB.  */
3299
3300 static struct tm_memopt_bitmaps *
3301 tm_memopt_init_sets (void)
3302 {
3303   struct tm_memopt_bitmaps *b
3304     = XOBNEW (&tm_memopt_obstack.obstack, struct tm_memopt_bitmaps);
3305   b->store_avail_in = BITMAP_ALLOC (&tm_memopt_obstack);
3306   b->store_avail_out = BITMAP_ALLOC (&tm_memopt_obstack);
3307   b->store_antic_in = BITMAP_ALLOC (&tm_memopt_obstack);
3308   b->store_antic_out = BITMAP_ALLOC (&tm_memopt_obstack);
3309   b->store_avail_out = BITMAP_ALLOC (&tm_memopt_obstack);
3310   b->read_avail_in = BITMAP_ALLOC (&tm_memopt_obstack);
3311   b->read_avail_out = BITMAP_ALLOC (&tm_memopt_obstack);
3312   b->read_local = BITMAP_ALLOC (&tm_memopt_obstack);
3313   b->store_local = BITMAP_ALLOC (&tm_memopt_obstack);
3314   return b;
3315 }
3316
3317 /* Free sets computed for each BB.  */
3318
3319 static void
3320 tm_memopt_free_sets (VEC (basic_block, heap) *blocks)
3321 {
3322   size_t i;
3323   basic_block bb;
3324
3325   for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
3326     bb->aux = NULL;
3327 }
3328
3329 /* Clear the visited bit for every basic block in BLOCKS.  */
3330
3331 static void
3332 tm_memopt_clear_visited (VEC (basic_block, heap) *blocks)
3333 {
3334   size_t i;
3335   basic_block bb;
3336
3337   for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
3338     BB_VISITED_P (bb) = false;
3339 }
3340
3341 /* Replace TM load/stores with hints for the runtime.  We handle
3342    things like read-after-write, write-after-read, read-after-read,
3343    read-for-write, etc.  */
3344
3345 static unsigned int
3346 execute_tm_memopt (void)
3347 {
3348   struct tm_region *region;
3349   VEC (basic_block, heap) *bbs;
3350
3351   tm_memopt_value_id = 0;
3352   tm_memopt_value_numbers = htab_create (10, tm_memop_hash, tm_memop_eq, free);
3353
3354   for (region = all_tm_regions; region; region = region->next)
3355     {
3356       /* All the TM stores/loads in the current region.  */
3357       size_t i;
3358       basic_block bb;
3359
3360       bitmap_obstack_initialize (&tm_memopt_obstack);
3361
3362       /* Save all BBs for the current region.  */
3363       bbs = get_tm_region_blocks (region->entry_block,
3364                                   region->exit_blocks,
3365                                   region->irr_blocks,
3366                                   NULL,
3367                                   false);
3368
3369       /* Collect all the memory operations.  */
3370       for (i = 0; VEC_iterate (basic_block, bbs, i, bb); ++i)
3371         {
3372           bb->aux = tm_memopt_init_sets ();
3373           tm_memopt_accumulate_memops (bb);
3374         }
3375
3376       /* Solve data flow equations and transform each block accordingly.  */
3377       tm_memopt_clear_visited (bbs);
3378       tm_memopt_compute_available (region, bbs);
3379       tm_memopt_clear_visited (bbs);
3380       tm_memopt_compute_antic (region, bbs);
3381       tm_memopt_transform_blocks (bbs);
3382
3383       tm_memopt_free_sets (bbs);
3384       VEC_free (basic_block, heap, bbs);
3385       bitmap_obstack_release (&tm_memopt_obstack);
3386       htab_empty (tm_memopt_value_numbers);
3387     }
3388
3389   htab_delete (tm_memopt_value_numbers);
3390   return 0;
3391 }
3392
3393 static bool
3394 gate_tm_memopt (void)
3395 {
3396   return flag_tm && optimize > 0;
3397 }
3398
3399 struct gimple_opt_pass pass_tm_memopt =
3400 {
3401  {
3402   GIMPLE_PASS,
3403   "tmmemopt",                           /* name */
3404   gate_tm_memopt,                       /* gate */
3405   execute_tm_memopt,                    /* execute */
3406   NULL,                                 /* sub */
3407   NULL,                                 /* next */
3408   0,                                    /* static_pass_number */
3409   TV_TRANS_MEM,                         /* tv_id */
3410   PROP_ssa | PROP_cfg,                  /* properties_required */
3411   0,                                    /* properties_provided */
3412   0,                                    /* properties_destroyed */
3413   0,                                    /* todo_flags_start */
3414   TODO_dump_func,                       /* todo_flags_finish */
3415  }
3416 };
3417
3418 \f
3419 /* Interprocedual analysis for the creation of transactional clones.
3420    The aim of this pass is to find which functions are referenced in
3421    a non-irrevocable transaction context, and for those over which
3422    we have control (or user directive), create a version of the
3423    function which uses only the transactional interface to reference
3424    protected memories.  This analysis proceeds in several steps:
3425
3426      (1) Collect the set of all possible transactional clones:
3427
3428         (a) For all local public functions marked tm_callable, push
3429             it onto the tm_callee queue.
3430
3431         (b) For all local functions, scan for calls in transaction blocks.
3432             Push the caller and callee onto the tm_caller and tm_callee
3433             queues.  Count the number of callers for each callee.
3434
3435         (c) For each local function on the callee list, assume we will
3436             create a transactional clone.  Push *all* calls onto the
3437             callee queues; count the number of clone callers separately
3438             to the number of original callers.
3439
3440      (2) Propagate irrevocable status up the dominator tree:
3441
3442         (a) Any external function on the callee list that is not marked
3443             tm_callable is irrevocable.  Push all callers of such onto
3444             a worklist.
3445
3446         (b) For each function on the worklist, mark each block that
3447             contains an irrevocable call.  Use the AND operator to
3448             propagate that mark up the dominator tree.
3449
3450         (c) If we reach the entry block for a possible transactional
3451             clone, then the transactional clone is irrevocable, and
3452             we should not create the clone after all.  Push all
3453             callers onto the worklist.
3454
3455         (d) Place tm_irrevocable calls at the beginning of the relevant
3456             blocks.  Special case here is the entry block for the entire
3457             transaction region; there we mark it GTMA_DOES_GO_IRREVOCABLE for
3458             the library to begin the region in serial mode.  Decrement
3459             the call count for all callees in the irrevocable region.
3460
3461      (3) Create the transactional clones:
3462
3463         Any tm_callee that still has a non-zero call count is cloned.
3464 */
3465
3466 /* This structure is stored in the AUX field of each cgraph_node.  */
3467 struct tm_ipa_cg_data
3468 {
3469   /* The clone of the function that got created.  */
3470   struct cgraph_node *clone;
3471
3472   /* The tm regions in the normal function.  */
3473   struct tm_region *all_tm_regions;
3474
3475   /* The blocks of the normal/clone functions that contain irrevocable
3476      calls, or blocks that are post-dominated by irrevocable calls.  */
3477   bitmap irrevocable_blocks_normal;
3478   bitmap irrevocable_blocks_clone;
3479
3480   /* The blocks of the normal function that are involved in transactions.  */
3481   bitmap transaction_blocks_normal;
3482
3483   /* The number of callers to the transactional clone of this function
3484      from normal and transactional clones respectively.  */
3485   unsigned tm_callers_normal;
3486   unsigned tm_callers_clone;
3487
3488   /* True if all calls to this function's transactional clone
3489      are irrevocable.  Also automatically true if the function
3490      has no transactional clone.  */
3491   bool is_irrevocable;
3492
3493   /* Flags indicating the presence of this function in various queues.  */
3494   bool in_callee_queue;
3495   bool in_worklist;
3496
3497   /* Flags indicating the kind of scan desired while in the worklist.  */
3498   bool want_irr_scan_normal;
3499 };
3500
3501 typedef struct cgraph_node *cgraph_node_p;
3502
3503 DEF_VEC_P (cgraph_node_p);
3504 DEF_VEC_ALLOC_P (cgraph_node_p, heap);
3505
3506 typedef VEC (cgraph_node_p, heap) *cgraph_node_queue;
3507
3508 /* Return the ipa data associated with NODE, allocating zeroed memory
3509    if necessary.  */
3510
3511 static struct tm_ipa_cg_data *
3512 get_cg_data (struct cgraph_node *node)
3513 {
3514   struct tm_ipa_cg_data *d = (struct tm_ipa_cg_data *) node->aux;
3515
3516   if (d == NULL)
3517     {
3518       d = (struct tm_ipa_cg_data *)
3519         obstack_alloc (&tm_obstack.obstack, sizeof (*d));
3520       node->aux = (void *) d;
3521       memset (d, 0, sizeof (*d));
3522     }
3523
3524   return d;
3525 }
3526
3527 /* Add NODE to the end of QUEUE, unless IN_QUEUE_P indicates that
3528    it is already present.  */
3529
3530 static void
3531 maybe_push_queue (struct cgraph_node *node,
3532                   cgraph_node_queue *queue_p, bool *in_queue_p)
3533 {
3534   if (!*in_queue_p)
3535     {
3536       *in_queue_p = true;
3537       VEC_safe_push (cgraph_node_p, heap, *queue_p, node);
3538     }
3539 }
3540
3541 /* A subroutine of ipa_tm_scan_calls_transaction and ipa_tm_scan_calls_clone.
3542    Queue all callees within block BB.  */
3543
3544 static void
3545 ipa_tm_scan_calls_block (cgraph_node_queue *callees_p,
3546                          basic_block bb, bool for_clone)
3547 {
3548   gimple_stmt_iterator gsi;
3549
3550   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3551     {
3552       gimple stmt = gsi_stmt (gsi);
3553       if (is_gimple_call (stmt) && !is_tm_pure_call (stmt))
3554         {
3555           tree fndecl = gimple_call_fndecl (stmt);
3556           if (fndecl)
3557             {
3558               struct tm_ipa_cg_data *d;
3559               unsigned *pcallers;
3560               struct cgraph_node *node;
3561
3562               if (is_tm_ending_fndecl (fndecl))
3563                 continue;
3564               if (find_tm_replacement_function (fndecl))
3565                 continue;
3566
3567               node = cgraph_get_node (fndecl);
3568               gcc_assert (node != NULL);
3569               d = get_cg_data (node);
3570
3571               pcallers = (for_clone ? &d->tm_callers_clone
3572                           : &d->tm_callers_normal);
3573               *pcallers += 1;
3574
3575               maybe_push_queue (node, callees_p, &d->in_callee_queue);
3576             }
3577         }
3578     }
3579 }
3580
3581 /* Scan all calls in NODE that are within a transaction region,
3582    and push the resulting nodes into the callee queue.  */
3583
3584 static void