OSDN Git Service

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