1 /* Passes for transactional memory support.
2 Copyright (C) 2008, 2009, 2010, 2011, 2012 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
19
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tree.h"
24 #include "gimple.h"
25 #include "tree-flow.h"
26 #include "tree-pass.h"
27 #include "tree-inline.h"
28 #include "diagnostic-core.h"
29 #include "demangle.h"
30 #include "output.h"
31 #include "trans-mem.h"
32 #include "params.h"
33 #include "target.h"
34 #include "langhooks.h"
35 #include "tree-pretty-print.h"
36 #include "gimple-pretty-print.h"
37
38
39 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 2000 - 1)
40 #define PROB_ALWAYS (REG_BR_PROB_BASE)
41
42 #define A_RUNINSTRUMENTEDCODE 0x0001
43 #define A_RUNUNINSTRUMENTEDCODE 0x0002
44 #define A_SAVELIVEVARIABLES 0x0004
45 #define A_RESTORELIVEVARIABLES 0x0008
46 #define A_ABORTTRANSACTION 0x0010
47
48 #define AR_USERABORT 0x0001
49 #define AR_USERRETRY 0x0002
50 #define AR_TMCONFLICT 0x0004
51 #define AR_EXCEPTIONBLOCKABORT 0x0008
52 #define AR_OUTERABORT 0x0010
53
54 #define MODE_SERIALIRREVOCABLE 0x0000
55
56
57 /* The representation of a transaction changes several times during the
58 lowering process. In the beginning, in the front-end we have the
59 GENERIC tree TRANSACTION_EXPR. For example,
60
61 __transaction {
62 local++;
63 if (++global == 10)
64 __tm_abort;
65 }
66
67 During initial gimplification (gimplify.c) the TRANSACTION_EXPR node is
68 trivially replaced with a GIMPLE_TRANSACTION node.
69
70 During pass_lower_tm, we examine the body of transactions looking
71 for aborts. Transactions that do not contain an abort may be
72 merged into an outer transaction. We also add a TRY-FINALLY node
73 to arrange for the transaction to be committed on any exit.
74
75 [??? Think about how this arrangement affects throw-with-commit
76 and throw-with-abort operations. In this case we want the TRY to
77 handle gotos, but not to catch any exceptions because the transaction
78 will already be closed.]
79
80 GIMPLE_TRANSACTION [label=NULL] {
81 try {
82 local = local + 1;
83 t0 = global;
84 t1 = t0 + 1;
85 global = t1;
86 if (t1 == 10)
87 __builtin___tm_abort ();
88 } finally {
89 __builtin___tm_commit ();
90 }
91 }
92
93 During pass_lower_eh, we create EH regions for the transactions,
94 intermixed with the regular EH stuff. This gives us a nice persistent
95 mapping (all the way through rtl) from transactional memory operation
96 back to the transaction, which allows us to get the abnormal edges
97 correct to model transaction aborts and restarts:
98
99 GIMPLE_TRANSACTION [label=over]
100 local = local + 1;
101 t0 = global;
102 t1 = t0 + 1;
103 global = t1;
104 if (t1 == 10)
105 __builtin___tm_abort ();
106 __builtin___tm_commit ();
107 over:
108
109 This is the end of all_lowering_passes, and so is what is present
110 during the IPA passes, and through all of the optimization passes.
111
112 During pass_ipa_tm, we examine all GIMPLE_TRANSACTION blocks in all
113 functions and mark functions for cloning.
114
115 At the end of gimple optimization, before exiting SSA form,
116 pass_tm_edges replaces statements that perform transactional
117 memory operations with the appropriate TM builtins, and swap
118 out function calls with their transactional clones. At this
119 point we introduce the abnormal transaction restart edges and
120 complete lowering of the GIMPLE_TRANSACTION node.
121
122 x = __builtin___tm_start (MAY_ABORT);
123 eh_label:
124 if (x & abort_transaction)
125 goto over;
126 local = local + 1;
127 t0 = __builtin___tm_load (global);
128 t1 = t0 + 1;
129 __builtin___tm_store (&global, t1);
130 if (t1 == 10)
131 __builtin___tm_abort ();
132 __builtin___tm_commit ();
133 over:
134 */
135
136
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
get_attrs_for(const_tree x)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
is_tm_pure(const_tree x)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
is_tm_irrevocable(tree x)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
is_tm_safe(const_tree x)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
is_tm_pure_call(gimple call)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
is_tm_callable(tree x)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
is_tm_may_cancel_outer(tree x)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
is_tm_ending_fndecl(tree fndecl)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
is_tm_load(gimple stmt)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
is_tm_simple_load(gimple stmt)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
is_tm_store(gimple stmt)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
is_tm_simple_store(gimple stmt)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
is_tm_abort(tree fndecl)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
build_tm_abort_call(location_t loc,bool is_outer)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
gate_tm(void)424 gate_tm (void)
425 {
426 return flag_tm;
427 }
428
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
record_tm_replacement(tree from,tree to)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
find_tm_replacement_function(tree fndecl)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
tm_malloc_replacement(tree from)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
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
diagnose_tm_1_op(tree * tp,int * walk_subtrees ATTRIBUTE_UNUSED,void * data)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
diagnose_tm_1(gimple_stmt_iterator * gsi,bool * handled_ops_p,struct walk_stmt_info * wi)578 diagnose_tm_1 (gimple_stmt_iterator *gsi, bool *handled_ops_p,
579 struct walk_stmt_info *wi)
580 {
581 gimple stmt = gsi_stmt (*gsi);
582 struct diagnose_tm *d = (struct diagnose_tm *) wi->info;
583
584 /* Save stmt for use in leaf analysis. */
585 d->stmt = stmt;
586
587 switch (gimple_code (stmt))
588 {
589 case GIMPLE_CALL:
590 {
591 tree fn = gimple_call_fn (stmt);
592
593 if ((d->summary_flags & DIAG_TM_OUTER) == 0
594 && is_tm_may_cancel_outer (fn))
595 error_at (gimple_location (stmt),
596 "%<transaction_may_cancel_outer%> function call not within"
597 " outer transaction or %<transaction_may_cancel_outer%>");
598
599 if (d->summary_flags & DIAG_TM_SAFE)
600 {
601 bool is_safe, direct_call_p;
602 tree replacement;
603
604 if (TREE_CODE (fn) == ADDR_EXPR
605 && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL)
606 {
607 direct_call_p = true;
608 replacement = TREE_OPERAND (fn, 0);
609 replacement = find_tm_replacement_function (replacement);
610 if (replacement)
611 fn = replacement;
612 }
613 else
614 {
615 direct_call_p = false;
616 replacement = NULL_TREE;
617 }
618
619 if (is_tm_safe_or_pure (fn))
620 is_safe = true;
621 else if (is_tm_callable (fn) || is_tm_irrevocable (fn))
622 {
623 /* A function explicitly marked transaction_callable as
624 opposed to transaction_safe is being defined to be
625 unsafe as part of its ABI, regardless of its contents. */
626 is_safe = false;
627 }
628 else if (direct_call_p)
629 {
630 if (flags_from_decl_or_type (fn) & ECF_TM_BUILTIN)
631 is_safe = true;
632 else if (replacement)
633 {
634 /* ??? At present we've been considering replacements
635 merely transaction_callable, and therefore might
636 enter irrevocable. The tm_wrap attribute has not
637 yet made it into the new language spec. */
638 is_safe = false;
639 }
640 else
641 {
642 /* ??? Diagnostics for unmarked direct calls moved into
643 the IPA pass. Section 3.2 of the spec details how
644 functions not marked should be considered "implicitly
645 safe" based on having examined the function body. */
646 is_safe = true;
647 }
648 }
649 else
650 {
651 /* An unmarked indirect call. Consider it unsafe even
652 though optimization may yet figure out how to inline. */
653 is_safe = false;
654 }
655
656 if (!is_safe)
657 {
658 if (TREE_CODE (fn) == ADDR_EXPR)
659 fn = TREE_OPERAND (fn, 0);
660 if (d->block_flags & DIAG_TM_SAFE)
661 {
662 if (direct_call_p)
663 error_at (gimple_location (stmt),
664 "unsafe function call %qD within "
665 "atomic transaction", fn);
666 else
667 {
668 if (!DECL_P (fn) || DECL_NAME (fn))
669 error_at (gimple_location (stmt),
670 "unsafe function call %qE within "
671 "atomic transaction", fn);
672 else
673 error_at (gimple_location (stmt),
674 "unsafe indirect function call within "
675 "atomic transaction");
676 }
677 }
678 else
679 {
680 if (direct_call_p)
681 error_at (gimple_location (stmt),
682 "unsafe function call %qD within "
683 "%<transaction_safe%> function", fn);
684 else
685 {
686 if (!DECL_P (fn) || DECL_NAME (fn))
687 error_at (gimple_location (stmt),
688 "unsafe function call %qE within "
689 "%<transaction_safe%> function", fn);
690 else
691 error_at (gimple_location (stmt),
692 "unsafe indirect function call within "
693 "%<transaction_safe%> function");
694 }
695 }
696 }
697 }
698 }
699 break;
700
701 case GIMPLE_ASM:
702 /* ??? We ought to come up with a way to add attributes to
703 asm statements, and then add "transaction_safe" to it.
704 Either that or get the language spec to resurrect __tm_waiver. */
705 if (d->block_flags & DIAG_TM_SAFE)
706 error_at (gimple_location (stmt),
707 "asm not allowed in atomic transaction");
708 else if (d->func_flags & DIAG_TM_SAFE)
709 error_at (gimple_location (stmt),
710 "asm not allowed in %<transaction_safe%> function");
711 break;
712
713 case GIMPLE_TRANSACTION:
714 {
715 unsigned char inner_flags = DIAG_TM_SAFE;
716
717 if (gimple_transaction_subcode (stmt) & GTMA_IS_RELAXED)
718 {
719 if (d->block_flags & DIAG_TM_SAFE)
720 error_at (gimple_location (stmt),
721 "relaxed transaction in atomic transaction");
722 else if (d->func_flags & DIAG_TM_SAFE)
723 error_at (gimple_location (stmt),
724 "relaxed transaction in %<transaction_safe%> function");
725 inner_flags = DIAG_TM_RELAXED;
726 }
727 else if (gimple_transaction_subcode (stmt) & GTMA_IS_OUTER)
728 {
729 if (d->block_flags)
730 error_at (gimple_location (stmt),
731 "outer transaction in transaction");
732 else if (d->func_flags & DIAG_TM_OUTER)
733 error_at (gimple_location (stmt),
734 "outer transaction in "
735 "%<transaction_may_cancel_outer%> function");
736 else if (d->func_flags & DIAG_TM_SAFE)
737 error_at (gimple_location (stmt),
738 "outer transaction in %<transaction_safe%> function");
739 inner_flags |= DIAG_TM_OUTER;
740 }
741
742 *handled_ops_p = true;
743 if (gimple_transaction_body (stmt))
744 {
745 struct walk_stmt_info wi_inner;
746 struct diagnose_tm d_inner;
747
748 memset (&d_inner, 0, sizeof (d_inner));
749 d_inner.func_flags = d->func_flags;
750 d_inner.block_flags = d->block_flags | inner_flags;
751 d_inner.summary_flags = d_inner.func_flags | d_inner.block_flags;
752
753 memset (&wi_inner, 0, sizeof (wi_inner));
754 wi_inner.info = &d_inner;
755
756 walk_gimple_seq (gimple_transaction_body (stmt),
757 diagnose_tm_1, diagnose_tm_1_op, &wi_inner);
758 }
759 }
760 break;
761
762 default:
763 break;
764 }
765
766 return NULL_TREE;
767 }
768
769 static unsigned int
diagnose_tm_blocks(void)770 diagnose_tm_blocks (void)
771 {
772 struct walk_stmt_info wi;
773 struct diagnose_tm d;
774
775 memset (&d, 0, sizeof (d));
776 if (is_tm_may_cancel_outer (current_function_decl))
777 d.func_flags = DIAG_TM_OUTER | DIAG_TM_SAFE;
778 else if (is_tm_safe (current_function_decl))
779 d.func_flags = DIAG_TM_SAFE;
780 d.summary_flags = d.func_flags;
781
782 memset (&wi, 0, sizeof (wi));
783 wi.info = &d;
784
785 walk_gimple_seq (gimple_body (current_function_decl),
786 diagnose_tm_1, diagnose_tm_1_op, &wi);
787
788 return 0;
789 }
790
791 struct gimple_opt_pass pass_diagnose_tm_blocks =
792 {
793 {
794 GIMPLE_PASS,
795 "*diagnose_tm_blocks", /* name */
796 gate_tm, /* gate */
797 diagnose_tm_blocks, /* execute */
798 NULL, /* sub */
799 NULL, /* next */
800 0, /* static_pass_number */
801 TV_TRANS_MEM, /* tv_id */
802 PROP_gimple_any, /* properties_required */
803 0, /* properties_provided */
804 0, /* properties_destroyed */
805 0, /* todo_flags_start */
806 0, /* todo_flags_finish */
807 }
808 };
809
810 /* Instead of instrumenting thread private memory, we save the
811 addresses in a log which we later use to save/restore the addresses
812 upon transaction start/restart.
813
814 The log is keyed by address, where each element contains individual
815 statements among different code paths that perform the store.
816
817 This log is later used to generate either plain save/restore of the
818 addresses upon transaction start/restart, or calls to the ITM_L*
819 logging functions.
820
821 So for something like:
822
823 struct large { int x[1000]; };
824 struct large lala = { 0 };
825 __transaction {
826 lala.x[i] = 123;
827 ...
828 }
829
830 We can either save/restore:
831
832 lala = { 0 };
833 trxn = _ITM_startTransaction ();
834 if (trxn & a_saveLiveVariables)
835 tmp_lala1 = lala.x[i];
836 else if (a & a_restoreLiveVariables)
837 lala.x[i] = tmp_lala1;
838
839 or use the logging functions:
840
841 lala = { 0 };
842 trxn = _ITM_startTransaction ();
843 _ITM_LU4 (&lala.x[i]);
844
845 Obviously, if we use _ITM_L* to log, we prefer to call _ITM_L* as
846 far up the dominator tree to shadow all of the writes to a given
847 location (thus reducing the total number of logging calls), but not
848 so high as to be called on a path that does not perform a
849 write. */
850
851 /* One individual log entry. We may have multiple statements for the
852 same location if neither dominate each other (on different
853 execution paths). */
854 typedef struct tm_log_entry
855 {
856 /* Address to save. */
857 tree addr;
858 /* Entry block for the transaction this address occurs in. */
859 basic_block entry_block;
860 /* Dominating statements the store occurs in. */
861 gimple_vec stmts;
862 /* Initially, while we are building the log, we place a nonzero
863 value here to mean that this address *will* be saved with a
864 save/restore sequence. Later, when generating the save sequence
865 we place the SSA temp generated here. */
866 tree save_var;
867 } *tm_log_entry_t;
868
869 /* The actual log. */
870 static htab_t tm_log;
871
872 /* Addresses to log with a save/restore sequence. These should be in
873 dominator order. */
VEC(tree,heap)874 static VEC(tree,heap) *tm_log_save_addresses;
875
876 /* Map for an SSA_NAME originally pointing to a non aliased new piece
877 of memory (malloc, alloc, etc). */
878 static htab_t tm_new_mem_hash;
879
880 enum thread_memory_type
881 {
882 mem_non_local = 0,
883 mem_thread_local,
884 mem_transaction_local,
885 mem_max
886 };
887
888 typedef struct tm_new_mem_map
889 {
890 /* SSA_NAME being dereferenced. */
891 tree val;
892 enum thread_memory_type local_new_memory;
893 } tm_new_mem_map_t;
894
895 /* Htab support. Return hash value for a `tm_log_entry'. */
896 static hashval_t
tm_log_hash(const void * p)897 tm_log_hash (const void *p)
898 {
899 const struct tm_log_entry *log = (const struct tm_log_entry *) p;
900 return iterative_hash_expr (log->addr, 0);
901 }
902
903 /* Htab support. Return true if two log entries are the same. */
904 static int
tm_log_eq(const void * p1,const void * p2)905 tm_log_eq (const void *p1, const void *p2)
906 {
907 const struct tm_log_entry *log1 = (const struct tm_log_entry *) p1;
908 const struct tm_log_entry *log2 = (const struct tm_log_entry *) p2;
909
910 /* FIXME:
911
912 rth: I suggest that we get rid of the component refs etc.
913 I.e. resolve the reference to base + offset.
914
915 We may need to actually finish a merge with mainline for this,
916 since we'd like to be presented with Richi's MEM_REF_EXPRs more
917 often than not. But in the meantime your tm_log_entry could save
918 the results of get_inner_reference.
919
920 See: g++.dg/tm/pr46653.C
921 */
922
923 /* Special case plain equality because operand_equal_p() below will
924 return FALSE if the addresses are equal but they have
925 side-effects (e.g. a volatile address). */
926 if (log1->addr == log2->addr)
927 return true;
928
929 return operand_equal_p (log1->addr, log2->addr, 0);
930 }
931
932 /* Htab support. Free one tm_log_entry. */
933 static void
tm_log_free(void * p)934 tm_log_free (void *p)
935 {
936 struct tm_log_entry *lp = (struct tm_log_entry *) p;
937 VEC_free (gimple, heap, lp->stmts);
938 free (lp);
939 }
940
941 /* Initialize logging data structures. */
942 static void
tm_log_init(void)943 tm_log_init (void)
944 {
945 tm_log = htab_create (10, tm_log_hash, tm_log_eq, tm_log_free);
946 tm_new_mem_hash = htab_create (5, struct_ptr_hash, struct_ptr_eq, free);
947 tm_log_save_addresses = VEC_alloc (tree, heap, 5);
948 }
949
950 /* Free logging data structures. */
951 static void
tm_log_delete(void)952 tm_log_delete (void)
953 {
954 htab_delete (tm_log);
955 htab_delete (tm_new_mem_hash);
956 VEC_free (tree, heap, tm_log_save_addresses);
957 }
958
959 /* Return true if MEM is a transaction invariant memory for the TM
960 region starting at REGION_ENTRY_BLOCK. */
961 static bool
transaction_invariant_address_p(const_tree mem,basic_block region_entry_block)962 transaction_invariant_address_p (const_tree mem, basic_block region_entry_block)
963 {
964 if ((TREE_CODE (mem) == INDIRECT_REF || TREE_CODE (mem) == MEM_REF)
965 && TREE_CODE (TREE_OPERAND (mem, 0)) == SSA_NAME)
966 {
967 basic_block def_bb;
968
969 def_bb = gimple_bb (SSA_NAME_DEF_STMT (TREE_OPERAND (mem, 0)));
970 return def_bb != region_entry_block
971 && dominated_by_p (CDI_DOMINATORS, region_entry_block, def_bb);
972 }
973
974 mem = strip_invariant_refs (mem);
975 return mem && (CONSTANT_CLASS_P (mem) || decl_address_invariant_p (mem));
976 }
977
978 /* Given an address ADDR in STMT, find it in the memory log or add it,
979 making sure to keep only the addresses highest in the dominator
980 tree.
981
982 ENTRY_BLOCK is the entry_block for the transaction.
983
984 If we find the address in the log, make sure it's either the same
985 address, or an equivalent one that dominates ADDR.
986
987 If we find the address, but neither ADDR dominates the found
988 address, nor the found one dominates ADDR, we're on different
989 execution paths. Add it.
990
991 If known, ENTRY_BLOCK is the entry block for the region, otherwise
992 NULL. */
993 static void
tm_log_add(basic_block entry_block,tree addr,gimple stmt)994 tm_log_add (basic_block entry_block, tree addr, gimple stmt)
995 {
996 void **slot;
997 struct tm_log_entry l, *lp;
998
999 l.addr = addr;
1000 slot = htab_find_slot (tm_log, &l, INSERT);
1001 if (!*slot)
1002 {
1003 tree type = TREE_TYPE (addr);
1004
1005 lp = XNEW (struct tm_log_entry);
1006 lp->addr = addr;
1007 *slot = lp;
1008
1009 /* Small invariant addresses can be handled as save/restores. */
1010 if (entry_block
1011 && transaction_invariant_address_p (lp->addr, entry_block)
1012 && TYPE_SIZE_UNIT (type) != NULL
1013 && host_integerp (TYPE_SIZE_UNIT (type), 1)
1014 && (tree_low_cst (TYPE_SIZE_UNIT (type), 1)
1015 < PARAM_VALUE (PARAM_TM_MAX_AGGREGATE_SIZE))
1016 /* We must be able to copy this type normally. I.e., no
1017 special constructors and the like. */
1018 && !TREE_ADDRESSABLE (type))
1019 {
1020 lp->save_var = create_tmp_reg (TREE_TYPE (lp->addr), "tm_save");
1021 add_referenced_var (lp->save_var);
1022 lp->stmts = NULL;
1023 lp->entry_block = entry_block;
1024 /* Save addresses separately in dominator order so we don't
1025 get confused by overlapping addresses in the save/restore
1026 sequence. */
1027 VEC_safe_push (tree, heap, tm_log_save_addresses, lp->addr);
1028 }
1029 else
1030 {
1031 /* Use the logging functions. */
1032 lp->stmts = VEC_alloc (gimple, heap, 5);
1033 VEC_quick_push (gimple, lp->stmts, stmt);
1034 lp->save_var = NULL;
1035 }
1036 }
1037 else
1038 {
1039 size_t i;
1040 gimple oldstmt;
1041
1042 lp = (struct tm_log_entry *) *slot;
1043
1044 /* If we're generating a save/restore sequence, we don't care
1045 about statements. */
1046 if (lp->save_var)
1047 return;
1048
1049 for (i = 0; VEC_iterate (gimple, lp->stmts, i, oldstmt); ++i)
1050 {
1051 if (stmt == oldstmt)
1052 return;
1053 /* We already have a store to the same address, higher up the
1054 dominator tree. Nothing to do. */
1055 if (dominated_by_p (CDI_DOMINATORS,
1056 gimple_bb (stmt), gimple_bb (oldstmt)))
1057 return;
1058 /* We should be processing blocks in dominator tree order. */
1059 gcc_assert (!dominated_by_p (CDI_DOMINATORS,
1060 gimple_bb (oldstmt), gimple_bb (stmt)));
1061 }
1062 /* Store is on a different code path. */
1063 VEC_safe_push (gimple, heap, lp->stmts, stmt);
1064 }
1065 }
1066
1067 /* Gimplify the address of a TARGET_MEM_REF. Return the SSA_NAME
1068 result, insert the new statements before GSI. */
1069
1070 static tree
gimplify_addr(gimple_stmt_iterator * gsi,tree x)1071 gimplify_addr (gimple_stmt_iterator *gsi, tree x)
1072 {
1073 if (TREE_CODE (x) == TARGET_MEM_REF)
1074 x = tree_mem_ref_addr (build_pointer_type (TREE_TYPE (x)), x);
1075 else
1076 x = build_fold_addr_expr (x);
1077 return force_gimple_operand_gsi (gsi, x, true, NULL, true, GSI_SAME_STMT);
1078 }
1079
1080 /* Instrument one address with the logging functions.
1081 ADDR is the address to save.
1082 STMT is the statement before which to place it. */
1083 static void
tm_log_emit_stmt(tree addr,gimple stmt)1084 tm_log_emit_stmt (tree addr, gimple stmt)
1085 {
1086 tree type = TREE_TYPE (addr);
1087 tree size = TYPE_SIZE_UNIT (type);
1088 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1089 gimple log;
1090 enum built_in_function code = BUILT_IN_TM_LOG;
1091
1092 if (type == float_type_node)
1093 code = BUILT_IN_TM_LOG_FLOAT;
1094 else if (type == double_type_node)
1095 code = BUILT_IN_TM_LOG_DOUBLE;
1096 else if (type == long_double_type_node)
1097 code = BUILT_IN_TM_LOG_LDOUBLE;
1098 else if (host_integerp (size, 1))
1099 {
1100 unsigned int n = tree_low_cst (size, 1);
1101 switch (n)
1102 {
1103 case 1:
1104 code = BUILT_IN_TM_LOG_1;
1105 break;
1106 case 2:
1107 code = BUILT_IN_TM_LOG_2;
1108 break;
1109 case 4:
1110 code = BUILT_IN_TM_LOG_4;
1111 break;
1112 case 8:
1113 code = BUILT_IN_TM_LOG_8;
1114 break;
1115 default:
1116 code = BUILT_IN_TM_LOG;
1117 if (TREE_CODE (type) == VECTOR_TYPE)
1118 {
1119 if (n == 8 && builtin_decl_explicit (BUILT_IN_TM_LOG_M64))
1120 code = BUILT_IN_TM_LOG_M64;
1121 else if (n == 16 && builtin_decl_explicit (BUILT_IN_TM_LOG_M128))
1122 code = BUILT_IN_TM_LOG_M128;
1123 else if (n == 32 && builtin_decl_explicit (BUILT_IN_TM_LOG_M256))
1124 code = BUILT_IN_TM_LOG_M256;
1125 }
1126 break;
1127 }
1128 }
1129
1130 addr = gimplify_addr (&gsi, addr);
1131 if (code == BUILT_IN_TM_LOG)
1132 log = gimple_build_call (builtin_decl_explicit (code), 2, addr, size);
1133 else
1134 log = gimple_build_call (builtin_decl_explicit (code), 1, addr);
1135 gsi_insert_before (&gsi, log, GSI_SAME_STMT);
1136 }
1137
1138 /* Go through the log and instrument address that must be instrumented
1139 with the logging functions. Leave the save/restore addresses for
1140 later. */
1141 static void
tm_log_emit(void)1142 tm_log_emit (void)
1143 {
1144 htab_iterator hi;
1145 struct tm_log_entry *lp;
1146
1147 FOR_EACH_HTAB_ELEMENT (tm_log, lp, tm_log_entry_t, hi)
1148 {
1149 size_t i;
1150 gimple stmt;
1151
1152 if (dump_file)
1153 {
1154 fprintf (dump_file, "TM thread private mem logging: ");
1155 print_generic_expr (dump_file, lp->addr, 0);
1156 fprintf (dump_file, "\n");
1157 }
1158
1159 if (lp->save_var)
1160 {
1161 if (dump_file)
1162 fprintf (dump_file, "DUMPING to variable\n");
1163 continue;
1164 }
1165 else
1166 {
1167 if (dump_file)
1168 fprintf (dump_file, "DUMPING with logging functions\n");
1169 for (i = 0; VEC_iterate (gimple, lp->stmts, i, stmt); ++i)
1170 tm_log_emit_stmt (lp->addr, stmt);
1171 }
1172 }
1173 }
1174
1175 /* Emit the save sequence for the corresponding addresses in the log.
1176 ENTRY_BLOCK is the entry block for the transaction.
1177 BB is the basic block to insert the code in. */
1178 static void
tm_log_emit_saves(basic_block entry_block,basic_block bb)1179 tm_log_emit_saves (basic_block entry_block, basic_block bb)
1180 {
1181 size_t i;
1182 gimple_stmt_iterator gsi = gsi_last_bb (bb);
1183 gimple stmt;
1184 struct tm_log_entry l, *lp;
1185
1186 for (i = 0; i < VEC_length (tree, tm_log_save_addresses); ++i)
1187 {
1188 l.addr = VEC_index (tree, tm_log_save_addresses, i);
1189 lp = (struct tm_log_entry *) *htab_find_slot (tm_log, &l, NO_INSERT);
1190 gcc_assert (lp->save_var != NULL);
1191
1192 /* We only care about variables in the current transaction. */
1193 if (lp->entry_block != entry_block)
1194 continue;
1195
1196 stmt = gimple_build_assign (lp->save_var, unshare_expr (lp->addr));
1197
1198 /* Make sure we can create an SSA_NAME for this type. For
1199 instance, aggregates aren't allowed, in which case the system
1200 will create a VOP for us and everything will just work. */
1201 if (is_gimple_reg_type (TREE_TYPE (lp->save_var)))
1202 {
1203 lp->save_var = make_ssa_name (lp->save_var, stmt);
1204 gimple_assign_set_lhs (stmt, lp->save_var);
1205 }
1206
1207 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1208 }
1209 }
1210
1211 /* Emit the restore sequence for the corresponding addresses in the log.
1212 ENTRY_BLOCK is the entry block for the transaction.
1213 BB is the basic block to insert the code in. */
1214 static void
tm_log_emit_restores(basic_block entry_block,basic_block bb)1215 tm_log_emit_restores (basic_block entry_block, basic_block bb)
1216 {
1217 int i;
1218 struct tm_log_entry l, *lp;
1219 gimple_stmt_iterator gsi;
1220 gimple stmt;
1221
1222 for (i = VEC_length (tree, tm_log_save_addresses) - 1; i >= 0; i--)
1223 {
1224 l.addr = VEC_index (tree, tm_log_save_addresses, i);
1225 lp = (struct tm_log_entry *) *htab_find_slot (tm_log, &l, NO_INSERT);
1226 gcc_assert (lp->save_var != NULL);
1227
1228 /* We only care about variables in the current transaction. */
1229 if (lp->entry_block != entry_block)
1230 continue;
1231
1232 /* Restores are in LIFO order from the saves in case we have
1233 overlaps. */
1234 gsi = gsi_start_bb (bb);
1235
1236 stmt = gimple_build_assign (unshare_expr (lp->addr), lp->save_var);
1237 gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
1238 }
1239 }
1240
1241 /* Emit the checks for performing either a save or a restore sequence.
1242
1243 TRXN_PROP is either A_SAVELIVEVARIABLES or A_RESTORELIVEVARIABLES.
1244
1245 The code sequence is inserted in a new basic block created in
1246 END_BB which is inserted between BEFORE_BB and the destination of
1247 FALLTHRU_EDGE.
1248
1249 STATUS is the return value from _ITM_beginTransaction.
1250 ENTRY_BLOCK is the entry block for the transaction.
1251 EMITF is a callback to emit the actual save/restore code.
1252
1253 The basic block containing the conditional checking for TRXN_PROP
1254 is returned. */
1255 static basic_block
tm_log_emit_save_or_restores(basic_block entry_block,unsigned trxn_prop,tree status,void (* emitf)(basic_block,basic_block),basic_block before_bb,edge fallthru_edge,basic_block * end_bb)1256 tm_log_emit_save_or_restores (basic_block entry_block,
1257 unsigned trxn_prop,
1258 tree status,
1259 void (*emitf)(basic_block, basic_block),
1260 basic_block before_bb,
1261 edge fallthru_edge,
1262 basic_block *end_bb)
1263 {
1264 basic_block cond_bb, code_bb;
1265 gimple cond_stmt, stmt;
1266 gimple_stmt_iterator gsi;
1267 tree t1, t2;
1268 int old_flags = fallthru_edge->flags;
1269
1270 cond_bb = create_empty_bb (before_bb);
1271 code_bb = create_empty_bb (cond_bb);
1272 *end_bb = create_empty_bb (code_bb);
1273 redirect_edge_pred (fallthru_edge, *end_bb);
1274 fallthru_edge->flags = EDGE_FALLTHRU;
1275 make_edge (before_bb, cond_bb, old_flags);
1276
1277 set_immediate_dominator (CDI_DOMINATORS, cond_bb, before_bb);
1278 set_immediate_dominator (CDI_DOMINATORS, code_bb, cond_bb);
1279
1280 gsi = gsi_last_bb (cond_bb);
1281
1282 /* t1 = status & A_{property}. */
1283 t1 = make_rename_temp (TREE_TYPE (status), NULL);
1284 t2 = build_int_cst (TREE_TYPE (status), trxn_prop);
1285 stmt = gimple_build_assign_with_ops (BIT_AND_EXPR, t1, status, t2);
1286 gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
1287
1288 /* if (t1). */
1289 t2 = build_int_cst (TREE_TYPE (status), 0);
1290 cond_stmt = gimple_build_cond (NE_EXPR, t1, t2, NULL, NULL);
1291 gsi_insert_after (&gsi, cond_stmt, GSI_CONTINUE_LINKING);
1292
1293 emitf (entry_block, code_bb);
1294
1295 make_edge (cond_bb, code_bb, EDGE_TRUE_VALUE);
1296 make_edge (cond_bb, *end_bb, EDGE_FALSE_VALUE);
1297 make_edge (code_bb, *end_bb, EDGE_FALLTHRU);
1298
1299 return cond_bb;
1300 }
1301
1302 static tree lower_sequence_tm (gimple_stmt_iterator *, bool *,
1303 struct walk_stmt_info *);
1304 static tree lower_sequence_no_tm (gimple_stmt_iterator *, bool *,
1305 struct walk_stmt_info *);
1306
1307 /* Evaluate an address X being dereferenced and determine if it
1308 originally points to a non aliased new chunk of memory (malloc,
1309 alloca, etc).
1310
1311 Return MEM_THREAD_LOCAL if it points to a thread-local address.
1312 Return MEM_TRANSACTION_LOCAL if it points to a transaction-local address.
1313 Return MEM_NON_LOCAL otherwise.
1314
1315 ENTRY_BLOCK is the entry block to the transaction containing the
1316 dereference of X. */
1317 static enum thread_memory_type
thread_private_new_memory(basic_block entry_block,tree x)1318 thread_private_new_memory (basic_block entry_block, tree x)
1319 {
1320 gimple stmt = NULL;
1321 enum tree_code code;
1322 void **slot;
1323 tm_new_mem_map_t elt, *elt_p;
1324 tree val = x;
1325 enum thread_memory_type retval = mem_transaction_local;
1326
1327 if (!entry_block
1328 || TREE_CODE (x) != SSA_NAME
1329 /* Possible uninitialized use, or a function argument. In
1330 either case, we don't care. */
1331 || SSA_NAME_IS_DEFAULT_DEF (x))
1332 return mem_non_local;
1333
1334 /* Look in cache first. */
1335 elt.val = x;
1336 slot = htab_find_slot (tm_new_mem_hash, &elt, INSERT);
1337 elt_p = (tm_new_mem_map_t *) *slot;
1338 if (elt_p)
1339 return elt_p->local_new_memory;
1340
1341 /* Optimistically assume the memory is transaction local during
1342 processing. This catches recursion into this variable. */
1343 *slot = elt_p = XNEW (tm_new_mem_map_t);
1344 elt_p->val = val;
1345 elt_p->local_new_memory = mem_transaction_local;
1346
1347 /* Search DEF chain to find the original definition of this address. */
1348 do
1349 {
1350 if (ptr_deref_may_alias_global_p (x))
1351 {
1352 /* Address escapes. This is not thread-private. */
1353 retval = mem_non_local;
1354 goto new_memory_ret;
1355 }
1356
1357 stmt = SSA_NAME_DEF_STMT (x);
1358
1359 /* If the malloc call is outside the transaction, this is
1360 thread-local. */
1361 if (retval != mem_thread_local
1362 && !dominated_by_p (CDI_DOMINATORS, gimple_bb (stmt), entry_block))
1363 retval = mem_thread_local;
1364
1365 if (is_gimple_assign (stmt))
1366 {
1367 code = gimple_assign_rhs_code (stmt);
1368 /* x = foo ==> foo */
1369 if (code == SSA_NAME)
1370 x = gimple_assign_rhs1 (stmt);
1371 /* x = foo + n ==> foo */
1372 else if (code == POINTER_PLUS_EXPR)
1373 x = gimple_assign_rhs1 (stmt);
1374 /* x = (cast*) foo ==> foo */
1375 else if (code == VIEW_CONVERT_EXPR || code == NOP_EXPR)
1376 x = gimple_assign_rhs1 (stmt);
1377 else
1378 {
1379 retval = mem_non_local;
1380 goto new_memory_ret;
1381 }
1382 }
1383 else
1384 {
1385 if (gimple_code (stmt) == GIMPLE_PHI)
1386 {
1387 unsigned int i;
1388 enum thread_memory_type mem;
1389 tree phi_result = gimple_phi_result (stmt);
1390
1391 /* If any of the ancestors are non-local, we are sure to
1392 be non-local. Otherwise we can avoid doing anything
1393 and inherit what has already been generated. */
1394 retval = mem_max;
1395 for (i = 0; i < gimple_phi_num_args (stmt); ++i)
1396 {
1397 tree op = PHI_ARG_DEF (stmt, i);
1398
1399 /* Exclude self-assignment. */
1400 if (phi_result == op)
1401 continue;
1402
1403 mem = thread_private_new_memory (entry_block, op);
1404 if (mem == mem_non_local)
1405 {
1406 retval = mem;
1407 goto new_memory_ret;
1408 }
1409 retval = MIN (retval, mem);
1410 }
1411 goto new_memory_ret;
1412 }
1413 break;
1414 }
1415 }
1416 while (TREE_CODE (x) == SSA_NAME);
1417
1418 if (stmt && is_gimple_call (stmt) && gimple_call_flags (stmt) & ECF_MALLOC)
1419 /* Thread-local or transaction-local. */
1420 ;
1421 else
1422 retval = mem_non_local;
1423
1424 new_memory_ret:
1425 elt_p->local_new_memory = retval;
1426 return retval;
1427 }
1428
1429 /* Determine whether X has to be instrumented using a read
1430 or write barrier.
1431
1432 ENTRY_BLOCK is the entry block for the region where stmt resides
1433 in. NULL if unknown.
1434
1435 STMT is the statement in which X occurs in. It is used for thread
1436 private memory instrumentation. If no TPM instrumentation is
1437 desired, STMT should be null. */
1438 static bool
requires_barrier(basic_block entry_block,tree x,gimple stmt)1439 requires_barrier (basic_block entry_block, tree x, gimple stmt)
1440 {
1441 tree orig = x;
1442 while (handled_component_p (x))
1443 x = TREE_OPERAND (x, 0);
1444
1445 switch (TREE_CODE (x))
1446 {
1447 case INDIRECT_REF:
1448 case MEM_REF:
1449 {
1450 enum thread_memory_type ret;
1451
1452 ret = thread_private_new_memory (entry_block, TREE_OPERAND (x, 0));
1453 if (ret == mem_non_local)
1454 return true;
1455 if (stmt && ret == mem_thread_local)
1456 /* ?? Should we pass `orig', or the INDIRECT_REF X. ?? */
1457 tm_log_add (entry_block, orig, stmt);
1458
1459 /* Transaction-locals require nothing at all. For malloc, a
1460 transaction restart frees the memory and we reallocate.
1461 For alloca, the stack pointer gets reset by the retry and
1462 we reallocate. */
1463 return false;
1464 }
1465
1466 case TARGET_MEM_REF:
1467 if (TREE_CODE (TMR_BASE (x)) != ADDR_EXPR)
1468 return true;
1469 x = TREE_OPERAND (TMR_BASE (x), 0);
1470 if (TREE_CODE (x) == PARM_DECL)
1471 return false;
1472 gcc_assert (TREE_CODE (x) == VAR_DECL);
1473 /* FALLTHRU */
1474
1475 case PARM_DECL:
1476 case RESULT_DECL:
1477 case VAR_DECL:
1478 if (DECL_BY_REFERENCE (x))
1479 {
1480 /* ??? This value is a pointer, but aggregate_value_p has been
1481 jigged to return true which confuses needs_to_live_in_memory.
1482 This ought to be cleaned up generically.
1483
1484 FIXME: Verify this still happens after the next mainline
1485 merge. Testcase ie g++.dg/tm/pr47554.C.
1486 */
1487 return false;
1488 }
1489
1490 if (is_global_var (x))
1491 return !TREE_READONLY (x);
1492 if (/* FIXME: This condition should actually go below in the
1493 tm_log_add() call, however is_call_clobbered() depends on
1494 aliasing info which is not available during
1495 gimplification. Since requires_barrier() gets called
1496 during lower_sequence_tm/gimplification, leave the call
1497 to needs_to_live_in_memory until we eliminate
1498 lower_sequence_tm altogether. */
1499 needs_to_live_in_memory (x))
1500 return true;
1501 else
1502 {
1503 /* For local memory that doesn't escape (aka thread private
1504 memory), we can either save the value at the beginning of
1505 the transaction and restore on restart, or call a tm
1506 function to dynamically save and restore on restart
1507 (ITM_L*). */
1508 if (stmt)
1509 tm_log_add (entry_block, orig, stmt);
1510 return false;
1511 }
1512
1513 default:
1514 return false;
1515 }
1516 }
1517
1518 /* Mark the GIMPLE_ASSIGN statement as appropriate for being inside
1519 a transaction region. */
1520
1521 static void
examine_assign_tm(unsigned * state,gimple_stmt_iterator * gsi)1522 examine_assign_tm (unsigned *state, gimple_stmt_iterator *gsi)
1523 {
1524 gimple stmt = gsi_stmt (*gsi);
1525
1526 if (requires_barrier (/*entry_block=*/NULL, gimple_assign_rhs1 (stmt), NULL))
1527 *state |= GTMA_HAVE_LOAD;
1528 if (requires_barrier (/*entry_block=*/NULL, gimple_assign_lhs (stmt), NULL))
1529 *state |= GTMA_HAVE_STORE;
1530 }
1531
1532 /* Mark a GIMPLE_CALL as appropriate for being inside a transaction. */
1533
1534 static void
examine_call_tm(unsigned * state,gimple_stmt_iterator * gsi)1535 examine_call_tm (unsigned *state, gimple_stmt_iterator *gsi)
1536 {
1537 gimple stmt = gsi_stmt (*gsi);
1538 tree fn;
1539
1540 if (is_tm_pure_call (stmt))
1541 return;
1542
1543 /* Check if this call is a transaction abort. */
1544 fn = gimple_call_fndecl (stmt);
1545 if (is_tm_abort (fn))
1546 *state |= GTMA_HAVE_ABORT;
1547
1548 /* Note that something may happen. */
1549 *state |= GTMA_HAVE_LOAD | GTMA_HAVE_STORE;
1550 }
1551
1552 /* Lower a GIMPLE_TRANSACTION statement. */
1553
1554 static void
lower_transaction(gimple_stmt_iterator * gsi,struct walk_stmt_info * wi)1555 lower_transaction (gimple_stmt_iterator *gsi, struct walk_stmt_info *wi)
1556 {
1557 gimple g, stmt = gsi_stmt (*gsi);
1558 unsigned int *outer_state = (unsigned int *) wi->info;
1559 unsigned int this_state = 0;
1560 struct walk_stmt_info this_wi;
1561
1562 /* First, lower the body. The scanning that we do inside gives
1563 us some idea of what we're dealing with. */
1564 memset (&this_wi, 0, sizeof (this_wi));
1565 this_wi.info = (void *) &this_state;
1566 walk_gimple_seq (gimple_transaction_body (stmt),
1567 lower_sequence_tm, NULL, &this_wi);
1568
1569 /* If there was absolutely nothing transaction related inside the
1570 transaction, we may elide it. Likewise if this is a nested
1571 transaction and does not contain an abort. */
1572 if (this_state == 0
1573 || (!(this_state & GTMA_HAVE_ABORT) && outer_state != NULL))
1574 {
1575 if (outer_state)
1576 *outer_state |= this_state;
1577
1578 gsi_insert_seq_before (gsi, gimple_transaction_body (stmt),
1579 GSI_SAME_STMT);
1580 gimple_transaction_set_body (stmt, NULL);
1581
1582 gsi_remove (gsi, true);
1583 wi->removed_stmt = true;
1584 return;
1585 }
1586
1587 /* Wrap the body of the transaction in a try-finally node so that
1588 the commit call is always properly called. */
1589 g = gimple_build_call (builtin_decl_explicit (BUILT_IN_TM_COMMIT), 0);
1590 if (flag_exceptions)
1591 {
1592 tree ptr;
1593 gimple_seq n_seq, e_seq;
1594
1595 n_seq = gimple_seq_alloc_with_stmt (g);
1596 e_seq = gimple_seq_alloc ();
1597
1598 g = gimple_build_call (builtin_decl_explicit (BUILT_IN_EH_POINTER),
1599 1, integer_zero_node);
1600 ptr = create_tmp_var (ptr_type_node, NULL);
1601 gimple_call_set_lhs (g, ptr);
1602 gimple_seq_add_stmt (&e_seq, g);
1603
1604 g = gimple_build_call (builtin_decl_explicit (BUILT_IN_TM_COMMIT_EH),
1605 1, ptr);
1606 gimple_seq_add_stmt (&e_seq, g);
1607
1608 g = gimple_build_eh_else (n_seq, e_seq);
1609 }
1610
1611 g = gimple_build_try (gimple_transaction_body (stmt),
1612 gimple_seq_alloc_with_stmt (g), GIMPLE_TRY_FINALLY);
1613 gsi_insert_after (gsi, g, GSI_CONTINUE_LINKING);
1614
1615 gimple_transaction_set_body (stmt, NULL);
1616
1617 /* If the transaction calls abort or if this is an outer transaction,
1618 add an "over" label afterwards. */
1619 if ((this_state & (GTMA_HAVE_ABORT))
1620 || (gimple_transaction_subcode(stmt) & GTMA_IS_OUTER))
1621 {
1622 tree label = create_artificial_label (UNKNOWN_LOCATION);
1623 gimple_transaction_set_label (stmt, label);
1624 gsi_insert_after (gsi, gimple_build_label (label), GSI_CONTINUE_LINKING);
1625 }
1626
1627 /* Record the set of operations found for use later. */
1628 this_state |= gimple_transaction_subcode (stmt) & GTMA_DECLARATION_MASK;
1629 gimple_transaction_set_subcode (stmt, this_state);
1630 }
1631
1632 /* Iterate through the statements in the sequence, lowering them all
1633 as appropriate for being in a transaction. */
1634
1635 static tree
lower_sequence_tm(gimple_stmt_iterator * gsi,bool * handled_ops_p,struct walk_stmt_info * wi)1636 lower_sequence_tm (gimple_stmt_iterator *gsi, bool *handled_ops_p,
1637 struct walk_stmt_info *wi)
1638 {
1639 unsigned int *state = (unsigned int *) wi->info;
1640 gimple stmt = gsi_stmt (*gsi);
1641
1642 *handled_ops_p = true;
1643 switch (gimple_code (stmt))
1644 {
1645 case GIMPLE_ASSIGN:
1646 /* Only memory reads/writes need to be instrumented. */
1647 if (gimple_assign_single_p (stmt))
1648 examine_assign_tm (state, gsi);
1649 break;
1650
1651 case GIMPLE_CALL:
1652 examine_call_tm (state, gsi);
1653 break;
1654
1655 case GIMPLE_ASM:
1656 *state |= GTMA_MAY_ENTER_IRREVOCABLE;
1657 break;
1658
1659 case GIMPLE_TRANSACTION:
1660 lower_transaction (gsi, wi);
1661 break;
1662
1663 default:
1664 *handled_ops_p = !gimple_has_substatements (stmt);
1665 break;
1666 }
1667
1668 return NULL_TREE;
1669 }
1670
1671 /* Iterate through the statements in the sequence, lowering them all
1672 as appropriate for being outside of a transaction. */
1673
1674 static tree
lower_sequence_no_tm(gimple_stmt_iterator * gsi,bool * handled_ops_p,struct walk_stmt_info * wi)1675 lower_sequence_no_tm (gimple_stmt_iterator *gsi, bool *handled_ops_p,
1676 struct walk_stmt_info * wi)
1677 {
1678 gimple stmt = gsi_stmt (*gsi);
1679
1680 if (gimple_code (stmt) == GIMPLE_TRANSACTION)
1681 {
1682 *handled_ops_p = true;
1683 lower_transaction (gsi, wi);
1684 }
1685 else
1686 *handled_ops_p = !gimple_has_substatements (stmt);
1687
1688 return NULL_TREE;
1689 }
1690
1691 /* Main entry point for flattening GIMPLE_TRANSACTION constructs. After
1692 this, GIMPLE_TRANSACTION nodes still exist, but the nested body has
1693 been moved out, and all the data required for constructing a proper
1694 CFG has been recorded. */
1695
1696 static unsigned int
execute_lower_tm(void)1697 execute_lower_tm (void)
1698 {
1699 struct walk_stmt_info wi;
1700
1701 /* Transactional clones aren't created until a later pass. */
1702 gcc_assert (!decl_is_tm_clone (current_function_decl));
1703
1704 memset (&wi, 0, sizeof (wi));
1705 walk_gimple_seq (gimple_body (current_function_decl),
1706 lower_sequence_no_tm, NULL, &wi);
1707
1708 return 0;
1709 }
1710
1711 struct gimple_opt_pass pass_lower_tm =
1712 {
1713 {
1714 GIMPLE_PASS,
1715 "tmlower", /* name */
1716 gate_tm, /* gate */
1717 execute_lower_tm, /* execute */
1718 NULL, /* sub */
1719 NULL, /* next */
1720 0, /* static_pass_number */
1721 TV_TRANS_MEM, /* tv_id */
1722 PROP_gimple_lcf, /* properties_required */
1723 0, /* properties_provided */
1724 0, /* properties_destroyed */
1725 0, /* todo_flags_start */
1726 TODO_dump_func /* todo_flags_finish */
1727 }
1728 };
1729
1730 /* Collect region information for each transaction. */
1731
1732 struct tm_region
1733 {
1734 /* Link to the next unnested transaction. */
1735 struct tm_region *next;
1736
1737 /* Link to the next inner transaction. */
1738 struct tm_region *inner;
1739
1740 /* Link to the next outer transaction. */
1741 struct tm_region *outer;
1742
1743 /* The GIMPLE_TRANSACTION statement beginning this transaction. */
1744 gimple transaction_stmt;
1745
1746 /* The entry block to this region. */
1747 basic_block entry_block;
1748
1749 /* The set of all blocks that end the region; NULL if only EXIT_BLOCK.
1750 These blocks are still a part of the region (i.e., the border is
1751 inclusive). Note that this set is only complete for paths in the CFG
1752 starting at ENTRY_BLOCK, and that there is no exit block recorded for
1753 the edge to the "over" label. */
1754 bitmap exit_blocks;
1755
1756 /* The set of all blocks that have an TM_IRREVOCABLE call. */
1757 bitmap irr_blocks;
1758 };
1759
1760 typedef struct tm_region *tm_region_p;
1761 DEF_VEC_P (tm_region_p);
1762 DEF_VEC_ALLOC_P (tm_region_p, heap);
1763
1764 /* True if there are pending edge statements to be committed for the
1765 current function being scanned in the tmmark pass. */
1766 bool pending_edge_inserts_p;
1767
1768 static struct tm_region *all_tm_regions;
1769 static bitmap_obstack tm_obstack;
1770
1771
1772 /* A subroutine of tm_region_init. Record the existance of the
1773 GIMPLE_TRANSACTION statement in a tree of tm_region elements. */
1774
1775 static struct tm_region *
tm_region_init_0(struct tm_region * outer,basic_block bb,gimple stmt)1776 tm_region_init_0 (struct tm_region *outer, basic_block bb, gimple stmt)
1777 {
1778 struct tm_region *region;
1779
1780 region = (struct tm_region *)
1781 obstack_alloc (&tm_obstack.obstack, sizeof (struct tm_region));
1782
1783 if (outer)
1784 {
1785 region->next = outer->inner;
1786 outer->inner = region;
1787 }
1788 else
1789 {
1790 region->next = all_tm_regions;
1791 all_tm_regions = region;
1792 }
1793 region->inner = NULL;
1794 region->outer = outer;
1795
1796 region->transaction_stmt = stmt;
1797
1798 /* There are either one or two edges out of the block containing
1799 the GIMPLE_TRANSACTION, one to the actual region and one to the
1800 "over" label if the region contains an abort. The former will
1801 always be the one marked FALLTHRU. */
1802 region->entry_block = FALLTHRU_EDGE (bb)->dest;
1803
1804 region->exit_blocks = BITMAP_ALLOC (&tm_obstack);
1805 region->irr_blocks = BITMAP_ALLOC (&tm_obstack);
1806
1807 return region;
1808 }
1809
1810 /* A subroutine of tm_region_init. Record all the exit and
1811 irrevocable blocks in BB into the region's exit_blocks and
1812 irr_blocks bitmaps. Returns the new region being scanned. */
1813
1814 static struct tm_region *
tm_region_init_1(struct tm_region * region,basic_block bb)1815 tm_region_init_1 (struct tm_region *region, basic_block bb)
1816 {
1817 gimple_stmt_iterator gsi;
1818 gimple g;
1819
1820 if (!region
1821 || (!region->irr_blocks && !region->exit_blocks))
1822 return region;
1823
1824 /* Check to see if this is the end of a region by seeing if it
1825 contains a call to __builtin_tm_commit{,_eh}. Note that the
1826 outermost region for DECL_IS_TM_CLONE need not collect this. */
1827 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
1828 {
1829 g = gsi_stmt (gsi);
1830 if (gimple_code (g) == GIMPLE_CALL)
1831 {
1832 tree fn = gimple_call_fndecl (g);
1833 if (fn && DECL_BUILT_IN_CLASS (fn) == BUILT_IN_NORMAL)
1834 {
1835 if ((DECL_FUNCTION_CODE (fn) == BUILT_IN_TM_COMMIT
1836 || DECL_FUNCTION_CODE (fn) == BUILT_IN_TM_COMMIT_EH)
1837 && region->exit_blocks)
1838 {
1839 bitmap_set_bit (region->exit_blocks, bb->index);
1840 region = region->outer;
1841 break;
1842 }
1843 if (DECL_FUNCTION_CODE (fn) == BUILT_IN_TM_IRREVOCABLE)
1844 bitmap_set_bit (region->irr_blocks, bb->index);
1845 }
1846 }
1847 }
1848 return region;
1849 }
1850
1851 /* Collect all of the transaction regions within the current function
1852 and record them in ALL_TM_REGIONS. The REGION parameter may specify
1853 an "outermost" region for use by tm clones. */
1854
1855 static void
tm_region_init(struct tm_region * region)1856 tm_region_init (struct tm_region *region)
1857 {
1858 gimple g;
1859 edge_iterator ei;
1860 edge e;
1861 basic_block bb;
1862 VEC(basic_block, heap) *queue = NULL;
1863 bitmap visited_blocks = BITMAP_ALLOC (NULL);
1864 struct tm_region *old_region;
1865 VEC(tm_region_p, heap) *bb_regions = NULL;
1866
1867 all_tm_regions = region;
1868 bb = single_succ (ENTRY_BLOCK_PTR);
1869
1870 /* We could store this information in bb->aux, but we may get called
1871 through get_all_tm_blocks() from another pass that may be already
1872 using bb->aux. */
1873 VEC_safe_grow_cleared (tm_region_p, heap, bb_regions, last_basic_block);
1874
1875 VEC_safe_push (basic_block, heap, queue, bb);
1876 VEC_replace (tm_region_p, bb_regions, bb->index, region);
1877 do
1878 {
1879 bb = VEC_pop (basic_block, queue);
1880 region = VEC_index (tm_region_p, bb_regions, bb->index);
1881 VEC_replace (tm_region_p, bb_regions, bb->index, NULL);
1882
1883 /* Record exit and irrevocable blocks. */
1884 region = tm_region_init_1 (region, bb);
1885
1886 /* Check for the last statement in the block beginning a new region. */
1887 g = last_stmt (bb);
1888 old_region = region;
1889 if (g && gimple_code (g) == GIMPLE_TRANSACTION)
1890 region = tm_region_init_0 (region, bb, g);
1891
1892 /* Process subsequent blocks. */
1893 FOR_EACH_EDGE (e, ei, bb->succs)
1894 if (!bitmap_bit_p (visited_blocks, e->dest->index))
1895 {
1896 bitmap_set_bit (visited_blocks, e->dest->index);
1897 VEC_safe_push (basic_block, heap, queue, e->dest);
1898
1899 /* If the current block started a new region, make sure that only
1900 the entry block of the new region is associated with this region.
1901 Other successors are still part of the old region. */
1902 if (old_region != region && e->dest != region->entry_block)
1903 VEC_replace (tm_region_p, bb_regions, e->dest->index, old_region);
1904 else
1905 VEC_replace (tm_region_p, bb_regions, e->dest->index, region);
1906 }
1907 }
1908 while (!VEC_empty (basic_block, queue));
1909 VEC_free (basic_block, heap, queue);
1910 BITMAP_FREE (visited_blocks);
1911 VEC_free (tm_region_p, heap, bb_regions);
1912 }
1913
1914 /* The "gate" function for all transactional memory expansion and optimization
1915 passes. We collect region information for each top-level transaction, and
1916 if we don't find any, we skip all of the TM passes. Each region will have
1917 all of the exit blocks recorded, and the originating statement. */
1918
1919 static bool
gate_tm_init(void)1920 gate_tm_init (void)
1921 {
1922 if (!flag_tm)
1923 return false;
1924
1925 calculate_dominance_info (CDI_DOMINATORS);
1926 bitmap_obstack_initialize (&tm_obstack);
1927
1928 /* If the function is a TM_CLONE, then the entire function is the region. */
1929 if (decl_is_tm_clone (current_function_decl))
1930 {
1931 struct tm_region *region = (struct tm_region *)
1932 obstack_alloc (&tm_obstack.obstack, sizeof (struct tm_region));
1933 memset (region, 0, sizeof (*region));
1934 region->entry_block = single_succ (ENTRY_BLOCK_PTR);
1935 /* For a clone, the entire function is the region. But even if
1936 we don't need to record any exit blocks, we may need to
1937 record irrevocable blocks. */
1938 region->irr_blocks = BITMAP_ALLOC (&tm_obstack);
1939
1940 tm_region_init (region);
1941 }
1942 else
1943 {
1944 tm_region_init (NULL);
1945
1946 /* If we didn't find any regions, cleanup and skip the whole tree
1947 of tm-related optimizations. */
1948 if (all_tm_regions == NULL)
1949 {
1950 bitmap_obstack_release (&tm_obstack);
1951 return false;
1952 }
1953 }
1954
1955 return true;
1956 }
1957
1958 struct gimple_opt_pass pass_tm_init =
1959 {
1960 {
1961 GIMPLE_PASS,
1962 "*tminit", /* name */
1963 gate_tm_init, /* gate */
1964 NULL, /* execute */
1965 NULL, /* sub */
1966 NULL, /* next */
1967 0, /* static_pass_number */
1968 TV_TRANS_MEM, /* tv_id */
1969 PROP_ssa | PROP_cfg, /* properties_required */
1970 0, /* properties_provided */
1971 0, /* properties_destroyed */
1972 0, /* todo_flags_start */
1973 0, /* todo_flags_finish */
1974 }
1975 };
1976
1977 /* Add FLAGS to the GIMPLE_TRANSACTION subcode for the transaction region
1978 represented by STATE. */
1979
1980 static inline void
transaction_subcode_ior(struct tm_region * region,unsigned flags)1981 transaction_subcode_ior (struct tm_region *region, unsigned flags)
1982 {
1983 if (region && region->transaction_stmt)
1984 {
1985 flags |= gimple_transaction_subcode (region->transaction_stmt);
1986 gimple_transaction_set_subcode (region->transaction_stmt, flags);
1987 }
1988 }
1989
1990 /* Construct a memory load in a transactional context. Return the
1991 gimple statement performing the load, or NULL if there is no
1992 TM_LOAD builtin of the appropriate size to do the load.
1993
1994 LOC is the location to use for the new statement(s). */
1995
1996 static gimple
build_tm_load(location_t loc,tree lhs,tree rhs,gimple_stmt_iterator * gsi)1997 build_tm_load (location_t loc, tree lhs, tree rhs, gimple_stmt_iterator *gsi)
1998 {
1999 enum built_in_function code = END_BUILTINS;
2000 tree t, type = TREE_TYPE (rhs), decl;
2001 gimple gcall;
2002
2003 if (type == float_type_node)
2004 code = BUILT_IN_TM_LOAD_FLOAT;
2005 else if (type == double_type_node)
2006 code = BUILT_IN_TM_LOAD_DOUBLE;
2007 else if (type == long_double_type_node)
2008 code = BUILT_IN_TM_LOAD_LDOUBLE;
2009 else if (TYPE_SIZE_UNIT (type) != NULL
2010 && host_integerp (TYPE_SIZE_UNIT (type), 1))
2011 {
2012 switch (tree_low_cst (TYPE_SIZE_UNIT (type), 1))
2013 {
2014 case 1:
2015 code = BUILT_IN_TM_LOAD_1;
2016 break;
2017 case 2:
2018 code = BUILT_IN_TM_LOAD_2;
2019 break;
2020 case 4:
2021 code = BUILT_IN_TM_LOAD_4;
2022 break;
2023 case 8:
2024 code = BUILT_IN_TM_LOAD_8;
2025 break;
2026 }
2027 }
2028
2029 if (code == END_BUILTINS)
2030 {
2031 decl = targetm.vectorize.builtin_tm_load (type);
2032 if (!decl)
2033 return NULL;
2034 }
2035 else
2036 decl = builtin_decl_explicit (code);
2037
2038 t = gimplify_addr (gsi, rhs);
2039 gcall = gimple_build_call (decl, 1, t);
2040 gimple_set_location (gcall, loc);
2041
2042 t = TREE_TYPE (TREE_TYPE (decl));
2043 if (useless_type_conversion_p (type, t))
2044 {
2045 gimple_call_set_lhs (gcall, lhs);
2046 gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2047 }
2048 else
2049 {
2050 gimple g;
2051 tree temp;
2052
2053 temp = make_rename_temp (t, NULL);
2054 gimple_call_set_lhs (gcall, temp);
2055 gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2056
2057 t = fold_build1 (VIEW_CONVERT_EXPR, type, temp);
2058 g = gimple_build_assign (lhs, t);
2059 gsi_insert_before (gsi, g, GSI_SAME_STMT);
2060 }
2061
2062 return gcall;
2063 }
2064
2065
2066 /* Similarly for storing TYPE in a transactional context. */
2067
2068 static gimple
build_tm_store(location_t loc,tree lhs,tree rhs,gimple_stmt_iterator * gsi)2069 build_tm_store (location_t loc, tree lhs, tree rhs, gimple_stmt_iterator *gsi)
2070 {
2071 enum built_in_function code = END_BUILTINS;
2072 tree t, fn, type = TREE_TYPE (rhs), simple_type;
2073 gimple gcall;
2074
2075 if (type == float_type_node)
2076 code = BUILT_IN_TM_STORE_FLOAT;
2077 else if (type == double_type_node)
2078 code = BUILT_IN_TM_STORE_DOUBLE;
2079 else if (type == long_double_type_node)
2080 code = BUILT_IN_TM_STORE_LDOUBLE;
2081 else if (TYPE_SIZE_UNIT (type) != NULL
2082 && host_integerp (TYPE_SIZE_UNIT (type), 1))
2083 {
2084 switch (tree_low_cst (TYPE_SIZE_UNIT (type), 1))
2085 {
2086 case 1:
2087 code = BUILT_IN_TM_STORE_1;
2088 break;
2089 case 2:
2090 code = BUILT_IN_TM_STORE_2;
2091 break;
2092 case 4:
2093 code = BUILT_IN_TM_STORE_4;
2094 break;
2095 case 8:
2096 code = BUILT_IN_TM_STORE_8;
2097 break;
2098 }
2099 }
2100
2101 if (code == END_BUILTINS)
2102 {
2103 fn = targetm.vectorize.builtin_tm_store (type);
2104 if (!fn)
2105 return NULL;
2106 }
2107 else
2108 fn = builtin_decl_explicit (code);
2109
2110 simple_type = TREE_VALUE (TREE_CHAIN (TYPE_ARG_TYPES (TREE_TYPE (fn))));
2111
2112 if (TREE_CODE (rhs) == CONSTRUCTOR)
2113 {
2114 /* Handle the easy initialization to zero. */
2115 if (CONSTRUCTOR_ELTS (rhs) == 0)
2116 rhs = build_int_cst (simple_type, 0);
2117 else
2118 {
2119 /* ...otherwise punt to the caller and probably use
2120 BUILT_IN_TM_MEMMOVE, because we can't wrap a
2121 VIEW_CONVERT_EXPR around a CONSTRUCTOR (below) and produce
2122 valid gimple. */
2123 return NULL;
2124 }
2125 }
2126 else if (!useless_type_conversion_p (simple_type, type))
2127 {
2128 gimple g;
2129 tree temp;
2130
2131 temp = make_rename_temp (simple_type, NULL);
2132 t = fold_build1 (VIEW_CONVERT_EXPR, simple_type, rhs);
2133 g = gimple_build_assign (temp, t);
2134 gimple_set_location (g, loc);
2135 gsi_insert_before (gsi, g, GSI_SAME_STMT);
2136
2137 rhs = temp;
2138 }
2139
2140 t = gimplify_addr (gsi, lhs);
2141 gcall = gimple_build_call (fn, 2, t, rhs);
2142 gimple_set_location (gcall, loc);
2143 gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2144
2145 return gcall;
2146 }
2147
2148
2149 /* Expand an assignment statement into transactional builtins. */
2150
2151 static void
expand_assign_tm(struct tm_region * region,gimple_stmt_iterator * gsi)2152 expand_assign_tm (struct tm_region *region, gimple_stmt_iterator *gsi)
2153 {
2154 gimple stmt = gsi_stmt (*gsi);
2155 location_t loc = gimple_location (stmt);
2156 tree lhs = gimple_assign_lhs (stmt);
2157 tree rhs = gimple_assign_rhs1 (stmt);
2158 bool store_p = requires_barrier (region->entry_block, lhs, NULL);
2159 bool load_p = requires_barrier (region->entry_block, rhs, NULL);
2160 gimple gcall = NULL;
2161
2162 if (!load_p && !store_p)
2163 {
2164 /* Add thread private addresses to log if applicable. */
2165 requires_barrier (region->entry_block, lhs, stmt);
2166 gsi_next (gsi);
2167 return;
2168 }
2169
2170 gsi_remove (gsi, true);
2171
2172 if (load_p && !store_p)
2173 {
2174 transaction_subcode_ior (region, GTMA_HAVE_LOAD);
2175 gcall = build_tm_load (loc, lhs, rhs, gsi);
2176 }
2177 else if (store_p && !load_p)
2178 {
2179 transaction_subcode_ior (region, GTMA_HAVE_STORE);
2180 gcall = build_tm_store (loc, lhs, rhs, gsi);
2181 }
2182 if (!gcall)
2183 {
2184 tree lhs_addr, rhs_addr, tmp;
2185
2186 if (load_p)
2187 transaction_subcode_ior (region, GTMA_HAVE_LOAD);
2188 if (store_p)
2189 transaction_subcode_ior (region, GTMA_HAVE_STORE);
2190
2191 /* ??? Figure out if there's any possible overlap between the LHS
2192 and the RHS and if not, use MEMCPY. */
2193
2194 if (load_p && is_gimple_reg (lhs))
2195 {
2196 tmp = create_tmp_var (TREE_TYPE (lhs), NULL);
2197 lhs_addr = build_fold_addr_expr (tmp);
2198 }
2199 else
2200 {
2201 tmp = NULL_TREE;
2202 lhs_addr = gimplify_addr (gsi, lhs);
2203 }
2204 rhs_addr = gimplify_addr (gsi, rhs);
2205 gcall = gimple_build_call (builtin_decl_explicit (BUILT_IN_TM_MEMMOVE),
2206 3, lhs_addr, rhs_addr,
2207 TYPE_SIZE_UNIT (TREE_TYPE (lhs)));
2208 gimple_set_location (gcall, loc);
2209 gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2210
2211 if (tmp)
2212 {
2213 gcall = gimple_build_assign (lhs, tmp);
2214 gsi_insert_before (gsi, gcall, GSI_SAME_STMT);
2215 }
2216 }
2217
2218 /* Now that we have the load/store in its instrumented form, add
2219 thread private addresses to the log if applicable. */
2220 if (!store_p)
2221 requires_barrier (region->entry_block, lhs, gcall);
2222
2223 /* add_stmt_to_tm_region (region, gcall); */
2224 }
2225
2226
2227 /* Expand a call statement as appropriate for a transaction. That is,
2228 either verify that the call does not affect the transaction, or
2229 redirect the call to a clone that handles transactions, or change
2230 the transaction state to IRREVOCABLE. Return true if the call is
2231 one of the builtins that end a transaction. */
2232
2233 static bool
expand_call_tm(struct tm_region * region,gimple_stmt_iterator * gsi)2234 expand_call_tm (struct tm_region *region,
2235 gimple_stmt_iterator *gsi)
2236 {
2237 gimple stmt = gsi_stmt (*gsi);
2238 tree lhs = gimple_call_lhs (stmt);
2239 tree fn_decl;
2240 struct cgraph_node *node;
2241 bool retval = false;
2242
2243 fn_decl = gimple_call_fndecl (stmt);
2244
2245 if (fn_decl == builtin_decl_explicit (BUILT_IN_TM_MEMCPY)
2246 || fn_decl == builtin_decl_explicit (BUILT_IN_TM_MEMMOVE))
2247 transaction_subcode_ior (region, GTMA_HAVE_STORE | GTMA_HAVE_LOAD);
2248 if (fn_decl == builtin_decl_explicit (BUILT_IN_TM_MEMSET))
2249 transaction_subcode_ior (region, GTMA_HAVE_STORE);
2250
2251 if (is_tm_pure_call (stmt))
2252 return false;
2253
2254 if (fn_decl)
2255 retval = is_tm_ending_fndecl (fn_decl);
2256 if (!retval)
2257 {
2258 /* Assume all non-const/pure calls write to memory, except
2259 transaction ending builtins. */
2260 transaction_subcode_ior (region, GTMA_HAVE_STORE);
2261 }
2262
2263 /* For indirect calls, we already generated a call into the runtime. */
2264 if (!fn_decl)
2265 {
2266 tree fn = gimple_call_fn (stmt);
2267
2268 /* We are guaranteed never to go irrevocable on a safe or pure
2269 call, and the pure call was handled above. */
2270 if (is_tm_safe (fn))
2271 return false;
2272 else
2273 transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
2274
2275 return false;
2276 }
2277
2278 node = cgraph_get_node (fn_decl);
2279 /* All calls should have cgraph here. */
2280 gcc_assert (node);
2281 if (node->local.tm_may_enter_irr)
2282 transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
2283
2284 if (is_tm_abort (fn_decl))
2285 {
2286 transaction_subcode_ior (region, GTMA_HAVE_ABORT);
2287 return true;
2288 }
2289
2290 /* Instrument the store if needed.
2291
2292 If the assignment happens inside the function call (return slot
2293 optimization), there is no instrumentation to be done, since
2294 the callee should have done the right thing. */
2295 if (lhs && requires_barrier (region->entry_block, lhs, stmt)
2296 && !gimple_call_return_slot_opt_p (stmt))
2297 {
2298 tree tmp = make_rename_temp (TREE_TYPE (lhs), NULL);
2299 location_t loc = gimple_location (stmt);
2300 edge fallthru_edge = NULL;
2301
2302 /* Remember if the call was going to throw. */
2303 if (stmt_can_throw_internal (stmt))
2304 {
2305 edge_iterator ei;
2306 edge e;
2307 basic_block bb = gimple_bb (stmt);
2308
2309 FOR_EACH_EDGE (e, ei, bb->succs)
2310 if (e->flags & EDGE_FALLTHRU)
2311 {
2312 fallthru_edge = e;
2313 break;
2314 }
2315 }
2316
2317 gimple_call_set_lhs (stmt, tmp);
2318 update_stmt (stmt);
2319 stmt = gimple_build_assign (lhs, tmp);
2320 gimple_set_location (stmt, loc);
2321
2322 /* We cannot throw in the middle of a BB. If the call was going
2323 to throw, place the instrumentation on the fallthru edge, so
2324 the call remains the last statement in the block. */
2325 if (fallthru_edge)
2326 {
2327 gimple_seq fallthru_seq = gimple_seq_alloc_with_stmt (stmt);
2328 gimple_stmt_iterator fallthru_gsi = gsi_start (fallthru_seq);
2329 expand_assign_tm (region, &fallthru_gsi);
2330 gsi_insert_seq_on_edge (fallthru_edge, fallthru_seq);
2331 pending_edge_inserts_p = true;
2332 }
2333 else
2334 {
2335 gsi_insert_after (gsi, stmt, GSI_CONTINUE_LINKING);
2336 expand_assign_tm (region, gsi);
2337 }
2338
2339 transaction_subcode_ior (region, GTMA_HAVE_STORE);
2340 }
2341
2342 return retval;
2343 }
2344
2345
2346 /* Expand all statements in BB as appropriate for being inside
2347 a transaction. */
2348
2349 static void
expand_block_tm(struct tm_region * region,basic_block bb)2350 expand_block_tm (struct tm_region *region, basic_block bb)
2351 {
2352 gimple_stmt_iterator gsi;
2353
2354 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2355 {
2356 gimple stmt = gsi_stmt (gsi);
2357 switch (gimple_code (stmt))
2358 {
2359 case GIMPLE_ASSIGN:
2360 /* Only memory reads/writes need to be instrumented. */
2361 if (gimple_assign_single_p (stmt)
2362 && !gimple_clobber_p (stmt))
2363 {
2364 expand_assign_tm (region, &gsi);
2365 continue;
2366 }
2367 break;
2368
2369 case GIMPLE_CALL:
2370 if (expand_call_tm (region, &gsi))
2371 return;
2372 break;
2373
2374 case GIMPLE_ASM:
2375 gcc_unreachable ();
2376
2377 default:
2378 break;
2379 }
2380 if (!gsi_end_p (gsi))
2381 gsi_next (&gsi);
2382 }
2383 }
2384
2385 /* Return the list of basic-blocks in REGION.
2386
2387 STOP_AT_IRREVOCABLE_P is true if caller is uninterested in blocks
2388 following a TM_IRREVOCABLE call. */
2389
VEC(basic_block,heap)2390 static VEC (basic_block, heap) *
2391 get_tm_region_blocks (basic_block entry_block,
2392 bitmap exit_blocks,
2393 bitmap irr_blocks,
2394 bitmap all_region_blocks,
2395 bool stop_at_irrevocable_p)
2396 {
2397 VEC(basic_block, heap) *bbs = NULL;
2398 unsigned i;
2399 edge e;
2400 edge_iterator ei;
2401 bitmap visited_blocks = BITMAP_ALLOC (NULL);
2402
2403 i = 0;
2404 VEC_safe_push (basic_block, heap, bbs, entry_block);
2405 bitmap_set_bit (visited_blocks, entry_block->index);
2406
2407 do
2408 {
2409 basic_block bb = VEC_index (basic_block, bbs, i++);
2410
2411 if (exit_blocks &&
2412 bitmap_bit_p (exit_blocks, bb->index))
2413 continue;
2414
2415 if (stop_at_irrevocable_p
2416 && irr_blocks
2417 && bitmap_bit_p (irr_blocks, bb->index))
2418 continue;
2419
2420 FOR_EACH_EDGE (e, ei, bb->succs)
2421 if (!bitmap_bit_p (visited_blocks, e->dest->index))
2422 {
2423 bitmap_set_bit (visited_blocks, e->dest->index);
2424 VEC_safe_push (basic_block, heap, bbs, e->dest);
2425 }
2426 }
2427 while (i < VEC_length (basic_block, bbs));
2428
2429 if (all_region_blocks)
2430 bitmap_ior_into (all_region_blocks, visited_blocks);
2431
2432 BITMAP_FREE (visited_blocks);
2433 return bbs;
2434 }
2435
2436 /* Set the IN_TRANSACTION for all gimple statements that appear in a
2437 transaction. */
2438
2439 void
compute_transaction_bits(void)2440 compute_transaction_bits (void)
2441 {
2442 struct tm_region *region;
2443 VEC (basic_block, heap) *queue;
2444 unsigned int i;
2445 basic_block bb;
2446
2447 /* ?? Perhaps we need to abstract gate_tm_init further, because we
2448 certainly don't need it to calculate CDI_DOMINATOR info. */
2449 gate_tm_init ();
2450
2451 FOR_EACH_BB (bb)
2452 bb->flags &= ~BB_IN_TRANSACTION;
2453
2454 for (region = all_tm_regions; region; region = region->next)
2455 {
2456 queue = get_tm_region_blocks (region->entry_block,
2457 region->exit_blocks,
2458 region->irr_blocks,
2459 NULL,
2460 /*stop_at_irr_p=*/true);
2461 for (i = 0; VEC_iterate (basic_block, queue, i, bb); ++i)
2462 bb->flags |= BB_IN_TRANSACTION;
2463 VEC_free (basic_block, heap, queue);
2464 }
2465
2466 if (all_tm_regions)
2467 bitmap_obstack_release (&tm_obstack);
2468 }
2469
2470 /* Entry point to the MARK phase of TM expansion. Here we replace
2471 transactional memory statements with calls to builtins, and function
2472 calls with their transactional clones (if available). But we don't
2473 yet lower GIMPLE_TRANSACTION or add the transaction restart back-edges. */
2474
2475 static unsigned int
execute_tm_mark(void)2476 execute_tm_mark (void)
2477 {
2478 struct tm_region *region;
2479 basic_block bb;
2480 VEC (basic_block, heap) *queue;
2481 size_t i;
2482
2483 queue = VEC_alloc (basic_block, heap, 10);
2484 pending_edge_inserts_p = false;
2485
2486 for (region = all_tm_regions; region ; region = region->next)
2487 {
2488 tm_log_init ();
2489 /* If we have a transaction... */
2490 if (region->exit_blocks)
2491 {
2492 unsigned int subcode
2493 = gimple_transaction_subcode (region->transaction_stmt);
2494
2495 /* Collect a new SUBCODE set, now that optimizations are done... */
2496 if (subcode & GTMA_DOES_GO_IRREVOCABLE)
2497 subcode &= (GTMA_DECLARATION_MASK | GTMA_DOES_GO_IRREVOCABLE
2498 | GTMA_MAY_ENTER_IRREVOCABLE);
2499 else
2500 subcode &= GTMA_DECLARATION_MASK;
2501 gimple_transaction_set_subcode (region->transaction_stmt, subcode);
2502 }
2503
2504 queue = get_tm_region_blocks (region->entry_block,
2505 region->exit_blocks,
2506 region->irr_blocks,
2507 NULL,
2508 /*stop_at_irr_p=*/true);
2509 for (i = 0; VEC_iterate (basic_block, queue, i, bb); ++i)
2510 expand_block_tm (region, bb);
2511 VEC_free (basic_block, heap, queue);
2512
2513 tm_log_emit ();
2514 }
2515
2516 if (pending_edge_inserts_p)
2517 gsi_commit_edge_inserts ();
2518 return 0;
2519 }
2520
2521 struct gimple_opt_pass pass_tm_mark =
2522 {
2523 {
2524 GIMPLE_PASS,
2525 "tmmark", /* name */
2526 NULL, /* gate */
2527 execute_tm_mark, /* execute */
2528 NULL, /* sub */
2529 NULL, /* next */
2530 0, /* static_pass_number */
2531 TV_TRANS_MEM, /* tv_id */
2532 PROP_ssa | PROP_cfg, /* properties_required */
2533 0, /* properties_provided */
2534 0, /* properties_destroyed */
2535 0, /* todo_flags_start */
2536 TODO_update_ssa
2537 | TODO_verify_ssa
2538 | TODO_dump_func, /* todo_flags_finish */
2539 }
2540 };
2541
2542 /* Create an abnormal call edge from BB to the first block of the region
2543 represented by STATE. Also record the edge in the TM_RESTART map. */
2544
2545 static inline void
make_tm_edge(gimple stmt,basic_block bb,struct tm_region * region)2546 make_tm_edge (gimple stmt, basic_block bb, struct tm_region *region)
2547 {
2548 void **slot;
2549 struct tm_restart_node *n, dummy;
2550
2551 if (cfun->gimple_df->tm_restart == NULL)
2552 cfun->gimple_df->tm_restart = htab_create_ggc (31, struct_ptr_hash,
2553 struct_ptr_eq, ggc_free);
2554
2555 dummy.stmt = stmt;
2556 dummy.label_or_list = gimple_block_label (region->entry_block);
2557 slot = htab_find_slot (cfun->gimple_df->tm_restart, &dummy, INSERT);
2558 n = (struct tm_restart_node *) *slot;
2559 if (n == NULL)
2560 {
2561 n = ggc_alloc_tm_restart_node ();
2562 *n = dummy;
2563 }
2564 else
2565 {
2566 tree old = n->label_or_list;
2567 if (TREE_CODE (old) == LABEL_DECL)
2568 old = tree_cons (NULL, old, NULL);
2569 n->label_or_list = tree_cons (NULL, dummy.label_or_list, old);
2570 }
2571
2572 make_edge (bb, region->entry_block, EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
2573 }
2574
2575
2576 /* Split block BB as necessary for every builtin function we added, and
2577 wire up the abnormal back edges implied by the transaction restart. */
2578
2579 static void
expand_block_edges(struct tm_region * region,basic_block bb)2580 expand_block_edges (struct tm_region *region, basic_block bb)
2581 {
2582 gimple_stmt_iterator gsi;
2583
2584 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2585 {
2586 bool do_next = true;
2587 gimple stmt = gsi_stmt (gsi);
2588
2589 /* ??? TM_COMMIT (and any other tm builtin function) in a nested
2590 transaction has an abnormal edge back to the outer-most transaction
2591 (there are no nested retries), while a TM_ABORT also has an abnormal
2592 backedge to the inner-most transaction. We haven't actually saved
2593 the inner-most transaction here. We should be able to get to it
2594 via the region_nr saved on STMT, and read the transaction_stmt from
2595 that, and find the first region block from there. */
2596 /* ??? Shouldn't we split for any non-pure, non-irrevocable function? */
2597 if (gimple_code (stmt) == GIMPLE_CALL
2598 && (gimple_call_flags (stmt) & ECF_TM_BUILTIN) != 0)
2599 {
2600 if (gsi_one_before_end_p (gsi))
2601 make_tm_edge (stmt, bb, region);
2602 else
2603 {
2604 edge e = split_block (bb, stmt);
2605 make_tm_edge (stmt, bb, region);
2606 bb = e->dest;
2607 gsi = gsi_start_bb (bb);
2608 do_next = false;
2609 }
2610
2611 /* Delete any tail-call annotation that may have been added.
2612 The tail-call pass may have mis-identified the commit as being
2613 a candidate because we had not yet added this restart edge. */
2614 gimple_call_set_tail (stmt, false);
2615 }
2616
2617 if (do_next)
2618 gsi_next (&gsi);
2619 }
2620 }
2621
2622 /* Expand the GIMPLE_TRANSACTION statement into the STM library call. */
2623
2624 static void
expand_transaction(struct tm_region * region)2625 expand_transaction (struct tm_region *region)
2626 {
2627 tree status, tm_start;
2628 basic_block atomic_bb, slice_bb;
2629 gimple_stmt_iterator gsi;
2630 tree t1, t2;
2631 gimple g;
2632 int flags, subcode;
2633
2634 tm_start = builtin_decl_explicit (BUILT_IN_TM_START);
2635 status = make_rename_temp (TREE_TYPE (TREE_TYPE (tm_start)), "tm_state");
2636
2637 /* ??? There are plenty of bits here we're not computing. */
2638 subcode = gimple_transaction_subcode (region->transaction_stmt);
2639 if (subcode & GTMA_DOES_GO_IRREVOCABLE)
2640 flags = PR_DOESGOIRREVOCABLE | PR_UNINSTRUMENTEDCODE;
2641 else
2642 flags = PR_INSTRUMENTEDCODE;
2643 if ((subcode & GTMA_MAY_ENTER_IRREVOCABLE) == 0)
2644 flags |= PR_HASNOIRREVOCABLE;
2645 /* If the transaction does not have an abort in lexical scope and is not
2646 marked as an outer transaction, then it will never abort. */
2647 if ((subcode & GTMA_HAVE_ABORT) == 0
2648 && (subcode & GTMA_IS_OUTER) == 0)
2649 flags |= PR_HASNOABORT;
2650 if ((subcode & GTMA_HAVE_STORE) == 0)
2651 flags |= PR_READONLY;
2652 t2 = build_int_cst (TREE_TYPE (status), flags);
2653 g = gimple_build_call (tm_start, 1, t2);
2654 gimple_call_set_lhs (g, status);
2655 gimple_set_location (g, gimple_location (region->transaction_stmt));
2656
2657 atomic_bb = gimple_bb (region->transaction_stmt);
2658
2659 if (!VEC_empty (tree, tm_log_save_addresses))
2660 tm_log_emit_saves (region->entry_block, atomic_bb);
2661
2662 gsi = gsi_last_bb (atomic_bb);
2663 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2664 gsi_remove (&gsi, true);
2665
2666 if (!VEC_empty (tree, tm_log_save_addresses))
2667 region->entry_block =
2668 tm_log_emit_save_or_restores (region->entry_block,
2669 A_RESTORELIVEVARIABLES,
2670 status,
2671 tm_log_emit_restores,
2672 atomic_bb,
2673 FALLTHRU_EDGE (atomic_bb),
2674 &slice_bb);
2675 else
2676 slice_bb = atomic_bb;
2677
2678 /* If we have an ABORT statement, create a test following the start
2679 call to perform the abort. */
2680 if (gimple_transaction_label (region->transaction_stmt))
2681 {
2682 edge e;
2683 basic_block test_bb;
2684
2685 test_bb = create_empty_bb (slice_bb);
2686 if (VEC_empty (tree, tm_log_save_addresses))
2687 region->entry_block = test_bb;
2688 gsi = gsi_last_bb (test_bb);
2689
2690 t1 = make_rename_temp (TREE_TYPE (status), NULL);
2691 t2 = build_int_cst (TREE_TYPE (status), A_ABORTTRANSACTION);
2692 g = gimple_build_assign_with_ops (BIT_AND_EXPR, t1, status, t2);
2693 gsi_insert_after (&gsi, g, GSI_CONTINUE_LINKING);
2694
2695 t2 = build_int_cst (TREE_TYPE (status), 0);
2696 g = gimple_build_cond (NE_EXPR, t1, t2, NULL, NULL);
2697 gsi_insert_after (&gsi, g, GSI_CONTINUE_LINKING);
2698
2699 e = FALLTHRU_EDGE (slice_bb);
2700 redirect_edge_pred (e, test_bb);
2701 e->flags = EDGE_FALSE_VALUE;
2702 e->probability = PROB_ALWAYS - PROB_VERY_UNLIKELY;
2703
2704 e = BRANCH_EDGE (atomic_bb);
2705 redirect_edge_pred (e, test_bb);
2706 e->flags = EDGE_TRUE_VALUE;
2707 e->probability = PROB_VERY_UNLIKELY;
2708
2709 e = make_edge (slice_bb, test_bb, EDGE_FALLTHRU);
2710 }
2711
2712 /* If we've no abort, but we do have PHIs at the beginning of the atomic
2713 region, that means we've a loop at the beginning of the atomic region
2714 that shares the first block. This can cause problems with the abnormal
2715 edges we're about to add for the transaction restart. Solve this by
2716 adding a new empty block to receive the abnormal edges. */
2717 else if (phi_nodes (region->entry_block))
2718 {
2719 edge e;
2720 basic_block empty_bb;
2721
2722 region->entry_block = empty_bb = create_empty_bb (atomic_bb);
2723
2724 e = FALLTHRU_EDGE (atomic_bb);
2725 redirect_edge_pred (e, empty_bb);
2726
2727 e = make_edge (atomic_bb, empty_bb, EDGE_FALLTHRU);
2728 }
2729
2730 /* The GIMPLE_TRANSACTION statement no longer exists. */
2731 region->transaction_stmt = NULL;
2732 }
2733
2734 static void expand_regions (struct tm_region *);
2735
2736 /* Helper function for expand_regions. Expand REGION and recurse to
2737 the inner region. */
2738
2739 static void
expand_regions_1(struct tm_region * region)2740 expand_regions_1 (struct tm_region *region)
2741 {
2742 if (region->exit_blocks)
2743 {
2744 unsigned int i;
2745 basic_block bb;
2746 VEC (basic_block, heap) *queue;
2747
2748 /* Collect the set of blocks in this region. Do this before
2749 splitting edges, so that we don't have to play with the
2750 dominator tree in the middle. */
2751 queue = get_tm_region_blocks (region->entry_block,
2752 region->exit_blocks,
2753 region->irr_blocks,
2754 NULL,
2755 /*stop_at_irr_p=*/false);
2756 expand_transaction (region);
2757 for (i = 0; VEC_iterate (basic_block, queue, i, bb); ++i)
2758 expand_block_edges (region, bb);
2759 VEC_free (basic_block, heap, queue);
2760 }
2761 if (region->inner)
2762 expand_regions (region->inner);
2763 }
2764
2765 /* Expand regions starting at REGION. */
2766
2767 static void
expand_regions(struct tm_region * region)2768 expand_regions (struct tm_region *region)
2769 {
2770 while (region)
2771 {
2772 expand_regions_1 (region);
2773 region = region->next;
2774 }
2775 }
2776
2777 /* Entry point to the final expansion of transactional nodes. */
2778
2779 static unsigned int
execute_tm_edges(void)2780 execute_tm_edges (void)
2781 {
2782 expand_regions (all_tm_regions);
2783 tm_log_delete ();
2784
2785 /* We've got to release the dominance info now, to indicate that it
2786 must be rebuilt completely. Otherwise we'll crash trying to update
2787 the SSA web in the TODO section following this pass. */
2788 free_dominance_info (CDI_DOMINATORS);
2789 bitmap_obstack_release (&tm_obstack);
2790 all_tm_regions = NULL;
2791
2792 return 0;
2793 }
2794
2795 struct gimple_opt_pass pass_tm_edges =
2796 {
2797 {
2798 GIMPLE_PASS,
2799 "tmedge", /* name */
2800 NULL, /* gate */
2801 execute_tm_edges, /* execute */
2802 NULL, /* sub */
2803 NULL, /* next */
2804 0, /* static_pass_number */
2805 TV_TRANS_MEM, /* tv_id */
2806 PROP_ssa | PROP_cfg, /* properties_required */
2807 0, /* properties_provided */
2808 0, /* properties_destroyed */
2809 0, /* todo_flags_start */
2810 TODO_update_ssa
2811 | TODO_verify_ssa
2812 | TODO_dump_func, /* todo_flags_finish */
2813 }
2814 };
2815
2816 /* A unique TM memory operation. */
2817 typedef struct tm_memop
2818 {
2819 /* Unique ID that all memory operations to the same location have. */
2820 unsigned int value_id;
2821 /* Address of load/store. */
2822 tree addr;
2823 } *tm_memop_t;
2824
2825 /* Sets for solving data flow equations in the memory optimization pass. */
2826 struct tm_memopt_bitmaps
2827 {
2828 /* Stores available to this BB upon entry. Basically, stores that
2829 dominate this BB. */
2830 bitmap store_avail_in;
2831 /* Stores available at the end of this BB. */
2832 bitmap store_avail_out;
2833 bitmap store_antic_in;
2834 bitmap store_antic_out;
2835 /* Reads available to this BB upon entry. Basically, reads that
2836 dominate this BB. */
2837 bitmap read_avail_in;
2838 /* Reads available at the end of this BB. */
2839 bitmap read_avail_out;
2840 /* Reads performed in this BB. */
2841 bitmap read_local;
2842 /* Writes performed in this BB. */
2843 bitmap store_local;
2844
2845 /* Temporary storage for pass. */
2846 /* Is the current BB in the worklist? */
2847 bool avail_in_worklist_p;
2848 /* Have we visited this BB? */
2849 bool visited_p;
2850 };
2851
2852 static bitmap_obstack tm_memopt_obstack;
2853
2854 /* Unique counter for TM loads and stores. Loads and stores of the
2855 same address get the same ID. */
2856 static unsigned int tm_memopt_value_id;
2857 static htab_t tm_memopt_value_numbers;
2858
2859 #define STORE_AVAIL_IN(BB) \
2860 ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_avail_in
2861 #define STORE_AVAIL_OUT(BB) \
2862 ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_avail_out
2863 #define STORE_ANTIC_IN(BB) \
2864 ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_antic_in
2865 #define STORE_ANTIC_OUT(BB) \
2866 ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_antic_out
2867 #define READ_AVAIL_IN(BB) \
2868 ((struct tm_memopt_bitmaps *) ((BB)->aux))->read_avail_in
2869 #define READ_AVAIL_OUT(BB) \
2870 ((struct tm_memopt_bitmaps *) ((BB)->aux))->read_avail_out
2871 #define READ_LOCAL(BB) \
2872 ((struct tm_memopt_bitmaps *) ((BB)->aux))->read_local
2873 #define STORE_LOCAL(BB) \
2874 ((struct tm_memopt_bitmaps *) ((BB)->aux))->store_local
2875 #define AVAIL_IN_WORKLIST_P(BB) \
2876 ((struct tm_memopt_bitmaps *) ((BB)->aux))->avail_in_worklist_p
2877 #define BB_VISITED_P(BB) \
2878 ((struct tm_memopt_bitmaps *) ((BB)->aux))->visited_p
2879
2880 /* Htab support. Return a hash value for a `tm_memop'. */
2881 static hashval_t
tm_memop_hash(const void * p)2882 tm_memop_hash (const void *p)
2883 {
2884 const struct tm_memop *mem = (const struct tm_memop *) p;
2885 tree addr = mem->addr;
2886 /* We drill down to the SSA_NAME/DECL for the hash, but equality is
2887 actually done with operand_equal_p (see tm_memop_eq). */
2888 if (TREE_CODE (addr) == ADDR_EXPR)
2889 addr = TREE_OPERAND (addr, 0);
2890 return iterative_hash_expr (addr, 0);
2891 }
2892
2893 /* Htab support. Return true if two tm_memop's are the same. */
2894 static int
tm_memop_eq(const void * p1,const void * p2)2895 tm_memop_eq (const void *p1, const void *p2)
2896 {
2897 const struct tm_memop *mem1 = (const struct tm_memop *) p1;
2898 const struct tm_memop *mem2 = (const struct tm_memop *) p2;
2899
2900 return operand_equal_p (mem1->addr, mem2->addr, 0);
2901 }
2902
2903 /* Given a TM load/store in STMT, return the value number for the address
2904 it accesses. */
2905
2906 static unsigned int
tm_memopt_value_number(gimple stmt,enum insert_option op)2907 tm_memopt_value_number (gimple stmt, enum insert_option op)
2908 {
2909 struct tm_memop tmpmem, *mem;
2910 void **slot;
2911
2912 gcc_assert (is_tm_load (stmt) || is_tm_store (stmt));
2913 tmpmem.addr = gimple_call_arg (stmt, 0);
2914 slot = htab_find_slot (tm_memopt_value_numbers, &tmpmem, op);
2915 if (*slot)
2916 mem = (struct tm_memop *) *slot;
2917 else if (op == INSERT)
2918 {
2919 mem = XNEW (struct tm_memop);
2920 *slot = mem;
2921 mem->value_id = tm_memopt_value_id++;
2922 mem->addr = tmpmem.addr;
2923 }
2924 else
2925 gcc_unreachable ();
2926 return mem->value_id;
2927 }
2928
2929 /* Accumulate TM memory operations in BB into STORE_LOCAL and READ_LOCAL. */
2930
2931 static void
tm_memopt_accumulate_memops(basic_block bb)2932 tm_memopt_accumulate_memops (basic_block bb)
2933 {
2934 gimple_stmt_iterator gsi;
2935
2936 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2937 {
2938 gimple stmt = gsi_stmt (gsi);
2939 bitmap bits;
2940 unsigned int loc;
2941
2942 if (is_tm_store (stmt))
2943 bits = STORE_LOCAL (bb);
2944 else if (is_tm_load (stmt))
2945 bits = READ_LOCAL (bb);
2946 else
2947 continue;
2948
2949 loc = tm_memopt_value_number (stmt, INSERT);
2950 bitmap_set_bit (bits, loc);
2951 if (dump_file)
2952 {
2953 fprintf (dump_file, "TM memopt (%s): value num=%d, BB=%d, addr=",
2954 is_tm_load (stmt) ? "LOAD" : "STORE", loc,
2955 gimple_bb (stmt)->index);
2956 print_generic_expr (dump_file, gimple_call_arg (stmt, 0), 0);
2957 fprintf (dump_file, "\n");
2958 }
2959 }
2960 }
2961
2962 /* Prettily dump one of the memopt sets. BITS is the bitmap to dump. */
2963
2964 static void
dump_tm_memopt_set(const char * set_name,bitmap bits)2965 dump_tm_memopt_set (const char *set_name, bitmap bits)
2966 {
2967 unsigned i;
2968 bitmap_iterator bi;
2969 const char *comma = "";
2970
2971 fprintf (dump_file, "TM memopt: %s: [", set_name);
2972 EXECUTE_IF_SET_IN_BITMAP (bits, 0, i, bi)
2973 {
2974 htab_iterator hi;
2975 struct tm_memop *mem;
2976
2977 /* Yeah, yeah, yeah. Whatever. This is just for debugging. */
2978 FOR_EACH_HTAB_ELEMENT (tm_memopt_value_numbers, mem, tm_memop_t, hi)
2979 if (mem->value_id == i)
2980 break;
2981 gcc_assert (mem->value_id == i);
2982 fprintf (dump_file, "%s", comma);
2983 comma = ", ";
2984 print_generic_expr (dump_file, mem->addr, 0);
2985 }
2986 fprintf (dump_file, "]\n");
2987 }
2988
2989 /* Prettily dump all of the memopt sets in BLOCKS. */
2990
2991 static void
dump_tm_memopt_sets(VEC (basic_block,heap)* blocks)2992 dump_tm_memopt_sets (VEC (basic_block, heap) *blocks)
2993 {
2994 size_t i;
2995 basic_block bb;
2996
2997 for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
2998 {
2999 fprintf (dump_file, "------------BB %d---------\n", bb->index);
3000 dump_tm_memopt_set ("STORE_LOCAL", STORE_LOCAL (bb));
3001 dump_tm_memopt_set ("READ_LOCAL", READ_LOCAL (bb));
3002 dump_tm_memopt_set ("STORE_AVAIL_IN", STORE_AVAIL_IN (bb));
3003 dump_tm_memopt_set ("STORE_AVAIL_OUT", STORE_AVAIL_OUT (bb));
3004 dump_tm_memopt_set ("READ_AVAIL_IN", READ_AVAIL_IN (bb));
3005 dump_tm_memopt_set ("READ_AVAIL_OUT", READ_AVAIL_OUT (bb));
3006 }
3007 }
3008
3009 /* Compute {STORE,READ}_AVAIL_IN for the basic block BB. */
3010
3011 static void
tm_memopt_compute_avin(basic_block bb)3012 tm_memopt_compute_avin (basic_block bb)
3013 {
3014 edge e;
3015 unsigned ix;
3016
3017 /* Seed with the AVOUT of any predecessor. */
3018 for (ix = 0; ix < EDGE_COUNT (bb->preds); ix++)
3019 {
3020 e = EDGE_PRED (bb, ix);
3021 /* Make sure we have already visited this BB, and is thus
3022 initialized.
3023
3024 If e->src->aux is NULL, this predecessor is actually on an
3025 enclosing transaction. We only care about the current
3026 transaction, so ignore it. */
3027 if (e->src->aux && BB_VISITED_P (e->src))
3028 {
3029 bitmap_copy (STORE_AVAIL_IN (bb), STORE_AVAIL_OUT (e->src));
3030 bitmap_copy (READ_AVAIL_IN (bb), READ_AVAIL_OUT (e->src));
3031 break;
3032 }
3033 }
3034
3035 for (; ix < EDGE_COUNT (bb->preds); ix++)
3036 {
3037 e = EDGE_PRED (bb, ix);
3038 if (e->src->aux && BB_VISITED_P (e->src))
3039 {
3040 bitmap_and_into (STORE_AVAIL_IN (bb), STORE_AVAIL_OUT (e->src));
3041 bitmap_and_into (READ_AVAIL_IN (bb), READ_AVAIL_OUT (e->src));
3042 }
3043 }
3044
3045 BB_VISITED_P (bb) = true;
3046 }
3047
3048 /* Compute the STORE_ANTIC_IN for the basic block BB. */
3049
3050 static void
tm_memopt_compute_antin(basic_block bb)3051 tm_memopt_compute_antin (basic_block bb)
3052 {
3053 edge e;
3054 unsigned ix;
3055
3056 /* Seed with the ANTIC_OUT of any successor. */
3057 for (ix = 0; ix < EDGE_COUNT (bb->succs); ix++)
3058 {
3059 e = EDGE_SUCC (bb, ix);
3060 /* Make sure we have already visited this BB, and is thus
3061 initialized. */
3062 if (BB_VISITED_P (e->dest))
3063 {
3064 bitmap_copy (STORE_ANTIC_IN (bb), STORE_ANTIC_OUT (e->dest));
3065 break;
3066 }
3067 }
3068
3069 for (; ix < EDGE_COUNT (bb->succs); ix++)
3070 {
3071 e = EDGE_SUCC (bb, ix);
3072 if (BB_VISITED_P (e->dest))
3073 bitmap_and_into (STORE_ANTIC_IN (bb), STORE_ANTIC_OUT (e->dest));
3074 }
3075
3076 BB_VISITED_P (bb) = true;
3077 }
3078
3079 /* Compute the AVAIL sets for every basic block in BLOCKS.
3080
3081 We compute {STORE,READ}_AVAIL_{OUT,IN} as follows:
3082
3083 AVAIL_OUT[bb] = union (AVAIL_IN[bb], LOCAL[bb])
3084 AVAIL_IN[bb] = intersect (AVAIL_OUT[predecessors])
3085
3086 This is basically what we do in lcm's compute_available(), but here
3087 we calculate two sets of sets (one for STOREs and one for READs),
3088 and we work on a region instead of the entire CFG.
3089
3090 REGION is the TM region.
3091 BLOCKS are the basic blocks in the region. */
3092
3093 static void
tm_memopt_compute_available(struct tm_region * region,VEC (basic_block,heap)* blocks)3094 tm_memopt_compute_available (struct tm_region *region,
3095 VEC (basic_block, heap) *blocks)
3096 {
3097 edge e;
3098 basic_block *worklist, *qin, *qout, *qend, bb;
3099 unsigned int qlen, i;
3100 edge_iterator ei;
3101 bool changed;
3102
3103 /* Allocate a worklist array/queue. Entries are only added to the
3104 list if they were not already on the list. So the size is
3105 bounded by the number of basic blocks in the region. */
3106 qlen = VEC_length (basic_block, blocks) - 1;
3107 qin = qout = worklist =
3108 XNEWVEC (basic_block, qlen);
3109
3110 /* Put every block in the region on the worklist. */
3111 for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
3112 {
3113 /* Seed AVAIL_OUT with the LOCAL set. */
3114 bitmap_ior_into (STORE_AVAIL_OUT (bb), STORE_LOCAL (bb));
3115 bitmap_ior_into (READ_AVAIL_OUT (bb), READ_LOCAL (bb));
3116
3117 AVAIL_IN_WORKLIST_P (bb) = true;
3118 /* No need to insert the entry block, since it has an AVIN of
3119 null, and an AVOUT that has already been seeded in. */
3120 if (bb != region->entry_block)
3121 *qin++ = bb;
3122 }
3123
3124 /* The entry block has been initialized with the local sets. */
3125 BB_VISITED_P (region->entry_block) = true;
3126
3127 qin = worklist;
3128 qend = &worklist[qlen];
3129
3130 /* Iterate until the worklist is empty. */
3131 while (qlen)
3132 {
3133 /* Take the first entry off the worklist. */
3134 bb = *qout++;
3135 qlen--;
3136
3137 if (qout >= qend)
3138 qout = worklist;
3139
3140 /* This block can be added to the worklist again if necessary. */
3141 AVAIL_IN_WORKLIST_P (bb) = false;
3142 tm_memopt_compute_avin (bb);
3143
3144 /* Note: We do not add the LOCAL sets here because we already
3145 seeded the AVAIL_OUT sets with them. */
3146 changed = bitmap_ior_into (STORE_AVAIL_OUT (bb), STORE_AVAIL_IN (bb));
3147 changed |= bitmap_ior_into (READ_AVAIL_OUT (bb), READ_AVAIL_IN (bb));
3148 if (changed
3149 && (region->exit_blocks == NULL
3150 || !bitmap_bit_p (region->exit_blocks, bb->index)))
3151 /* If the out state of this block changed, then we need to add
3152 its successors to the worklist if they are not already in. */
3153 FOR_EACH_EDGE (e, ei, bb->succs)
3154 if (!AVAIL_IN_WORKLIST_P (e->dest) && e->dest != EXIT_BLOCK_PTR)
3155 {
3156 *qin++ = e->dest;
3157 AVAIL_IN_WORKLIST_P (e->dest) = true;
3158 qlen++;
3159
3160 if (qin >= qend)
3161 qin = worklist;
3162 }
3163 }
3164
3165 free (worklist);
3166
3167 if (dump_file)
3168 dump_tm_memopt_sets (blocks);
3169 }
3170
3171 /* Compute ANTIC sets for every basic block in BLOCKS.
3172
3173 We compute STORE_ANTIC_OUT as follows:
3174
3175 STORE_ANTIC_OUT[bb] = union(STORE_ANTIC_IN[bb], STORE_LOCAL[bb])
3176 STORE_ANTIC_IN[bb] = intersect(STORE_ANTIC_OUT[successors])
3177
3178 REGION is the TM region.
3179 BLOCKS are the basic blocks in the region. */
3180
3181 static void
tm_memopt_compute_antic(struct tm_region * region,VEC (basic_block,heap)* blocks)3182 tm_memopt_compute_antic (struct tm_region *region,
3183 VEC (basic_block, heap) *blocks)
3184 {
3185 edge e;
3186 basic_block *worklist, *qin, *qout, *qend, bb;
3187 unsigned int qlen;
3188 int i;
3189 edge_iterator ei;
3190
3191 /* Allocate a worklist array/queue. Entries are only added to the
3192 list if they were not already on the list. So the size is
3193 bounded by the number of basic blocks in the region. */
3194 qin = qout = worklist =
3195 XNEWVEC (basic_block, VEC_length (basic_block, blocks));
3196
3197 for (qlen = 0, i = VEC_length (basic_block, blocks) - 1; i >= 0; --i)
3198 {
3199 bb = VEC_index (basic_block, blocks, i);
3200
3201 /* Seed ANTIC_OUT with the LOCAL set. */
3202 bitmap_ior_into (STORE_ANTIC_OUT (bb), STORE_LOCAL (bb));
3203
3204 /* Put every block in the region on the worklist. */
3205 AVAIL_IN_WORKLIST_P (bb) = true;
3206 /* No need to insert exit blocks, since their ANTIC_IN is NULL,
3207 and their ANTIC_OUT has already been seeded in. */
3208 if (region->exit_blocks
3209 && !bitmap_bit_p (region->exit_blocks, bb->index))
3210 {
3211 qlen++;
3212 *qin++ = bb;
3213 }
3214 }
3215
3216 /* The exit blocks have been initialized with the local sets. */
3217 if (region->exit_blocks)
3218 {
3219 unsigned int i;
3220 bitmap_iterator bi;
3221 EXECUTE_IF_SET_IN_BITMAP (region->exit_blocks, 0, i, bi)
3222 BB_VISITED_P (BASIC_BLOCK (i)) = true;
3223 }
3224
3225 qin = worklist;
3226 qend = &worklist[qlen];
3227
3228 /* Iterate until the worklist is empty. */
3229 while (qlen)
3230 {
3231 /* Take the first entry off the worklist. */
3232 bb = *qout++;
3233 qlen--;
3234
3235 if (qout >= qend)
3236 qout = worklist;
3237
3238 /* This block can be added to the worklist again if necessary. */
3239 AVAIL_IN_WORKLIST_P (bb) = false;
3240 tm_memopt_compute_antin (bb);
3241
3242 /* Note: We do not add the LOCAL sets here because we already
3243 seeded the ANTIC_OUT sets with them. */
3244 if (bitmap_ior_into (STORE_ANTIC_OUT (bb), STORE_ANTIC_IN (bb))
3245 && bb != region->entry_block)
3246 /* If the out state of this block changed, then we need to add
3247 its predecessors to the worklist if they are not already in. */
3248 FOR_EACH_EDGE (e, ei, bb->preds)
3249 if (!AVAIL_IN_WORKLIST_P (e->src))
3250 {
3251 *qin++ = e->src;
3252 AVAIL_IN_WORKLIST_P (e->src) = true;
3253 qlen++;
3254
3255 if (qin >= qend)
3256 qin = worklist;
3257 }
3258 }
3259
3260 free (worklist);
3261
3262 if (dump_file)
3263 dump_tm_memopt_sets (blocks);
3264 }
3265
3266 /* Offsets of load variants from TM_LOAD. For example,
3267 BUILT_IN_TM_LOAD_RAR* is an offset of 1 from BUILT_IN_TM_LOAD*.
3268 See gtm-builtins.def. */
3269 #define TRANSFORM_RAR 1
3270 #define TRANSFORM_RAW 2
3271 #define TRANSFORM_RFW 3
3272 /* Offsets of store variants from TM_STORE. */
3273 #define TRANSFORM_WAR 1
3274 #define TRANSFORM_WAW 2
3275
3276 /* Inform about a load/store optimization. */
3277
3278 static void
dump_tm_memopt_transform(gimple stmt)3279 dump_tm_memopt_transform (gimple stmt)
3280 {
3281 if (dump_file)
3282 {
3283 fprintf (dump_file, "TM memopt: transforming: ");
3284 print_gimple_stmt (dump_file, stmt, 0, 0);
3285 fprintf (dump_file, "\n");
3286 }
3287 }
3288
3289 /* Perform a read/write optimization. Replaces the TM builtin in STMT
3290 by a builtin that is OFFSET entries down in the builtins table in
3291 gtm-builtins.def. */
3292
3293 static void
tm_memopt_transform_stmt(unsigned int offset,gimple stmt,gimple_stmt_iterator * gsi)3294 tm_memopt_transform_stmt (unsigned int offset,
3295 gimple stmt,
3296 gimple_stmt_iterator *gsi)
3297 {
3298 tree fn = gimple_call_fn (stmt);
3299 gcc_assert (TREE_CODE (fn) == ADDR_EXPR);
3300 TREE_OPERAND (fn, 0)
3301 = builtin_decl_explicit ((enum built_in_function)
3302 (DECL_FUNCTION_CODE (TREE_OPERAND (fn, 0))
3303 + offset));
3304 gimple_call_set_fn (stmt, fn);
3305 gsi_replace (gsi, stmt, true);
3306 dump_tm_memopt_transform (stmt);
3307 }
3308
3309 /* Perform the actual TM memory optimization transformations in the
3310 basic blocks in BLOCKS. */
3311
3312 static void
tm_memopt_transform_blocks(VEC (basic_block,heap)* blocks)3313 tm_memopt_transform_blocks (VEC (basic_block, heap) *blocks)
3314 {
3315 size_t i;
3316 basic_block bb;
3317 gimple_stmt_iterator gsi;
3318
3319 for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
3320 {
3321 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3322 {
3323 gimple stmt = gsi_stmt (gsi);
3324 bitmap read_avail = READ_AVAIL_IN (bb);
3325 bitmap store_avail = STORE_AVAIL_IN (bb);
3326 bitmap store_antic = STORE_ANTIC_OUT (bb);
3327 unsigned int loc;
3328
3329 if (is_tm_simple_load (stmt))
3330 {
3331 loc = tm_memopt_value_number (stmt, NO_INSERT);
3332 if (store_avail && bitmap_bit_p (store_avail, loc))
3333 tm_memopt_transform_stmt (TRANSFORM_RAW, stmt, &gsi);
3334 else if (store_antic && bitmap_bit_p (store_antic, loc))
3335 {
3336 tm_memopt_transform_stmt (TRANSFORM_RFW, stmt, &gsi);
3337 bitmap_set_bit (store_avail, loc);
3338 }
3339 else if (read_avail && bitmap_bit_p (read_avail, loc))
3340 tm_memopt_transform_stmt (TRANSFORM_RAR, stmt, &gsi);
3341 else
3342 bitmap_set_bit (read_avail, loc);
3343 }
3344 else if (is_tm_simple_store (stmt))
3345 {
3346 loc = tm_memopt_value_number (stmt, NO_INSERT);
3347 if (store_avail && bitmap_bit_p (store_avail, loc))
3348 tm_memopt_transform_stmt (TRANSFORM_WAW, stmt, &gsi);
3349 else
3350 {
3351 if (read_avail && bitmap_bit_p (read_avail, loc))
3352 tm_memopt_transform_stmt (TRANSFORM_WAR, stmt, &gsi);
3353 bitmap_set_bit (store_avail, loc);
3354 }
3355 }
3356 }
3357 }
3358 }
3359
3360 /* Return a new set of bitmaps for a BB. */
3361
3362 static struct tm_memopt_bitmaps *
tm_memopt_init_sets(void)3363 tm_memopt_init_sets (void)
3364 {
3365 struct tm_memopt_bitmaps *b
3366 = XOBNEW (&tm_memopt_obstack.obstack, struct tm_memopt_bitmaps);
3367 b->store_avail_in = BITMAP_ALLOC (&tm_memopt_obstack);
3368 b->store_avail_out = BITMAP_ALLOC (&tm_memopt_obstack);
3369 b->store_antic_in = BITMAP_ALLOC (&tm_memopt_obstack);
3370 b->store_antic_out = BITMAP_ALLOC (&tm_memopt_obstack);
3371 b->store_avail_out = BITMAP_ALLOC (&tm_memopt_obstack);
3372 b->read_avail_in = BITMAP_ALLOC (&tm_memopt_obstack);
3373 b->read_avail_out = BITMAP_ALLOC (&tm_memopt_obstack);
3374 b->read_local = BITMAP_ALLOC (&tm_memopt_obstack);
3375 b->store_local = BITMAP_ALLOC (&tm_memopt_obstack);
3376 return b;
3377 }
3378
3379 /* Free sets computed for each BB. */
3380
3381 static void
tm_memopt_free_sets(VEC (basic_block,heap)* blocks)3382 tm_memopt_free_sets (VEC (basic_block, heap) *blocks)
3383 {
3384 size_t i;
3385 basic_block bb;
3386
3387 for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
3388 bb->aux = NULL;
3389 }
3390
3391 /* Clear the visited bit for every basic block in BLOCKS. */
3392
3393 static void
tm_memopt_clear_visited(VEC (basic_block,heap)* blocks)3394 tm_memopt_clear_visited (VEC (basic_block, heap) *blocks)
3395 {
3396 size_t i;
3397 basic_block bb;
3398
3399 for (i = 0; VEC_iterate (basic_block, blocks, i, bb); ++i)
3400 BB_VISITED_P (bb) = false;
3401 }
3402
3403 /* Replace TM load/stores with hints for the runtime. We handle
3404 things like read-after-write, write-after-read, read-after-read,
3405 read-for-write, etc. */
3406
3407 static unsigned int
execute_tm_memopt(void)3408 execute_tm_memopt (void)
3409 {
3410 struct tm_region *region;
3411 VEC (basic_block, heap) *bbs;
3412
3413 tm_memopt_value_id = 0;
3414 tm_memopt_value_numbers = htab_create (10, tm_memop_hash, tm_memop_eq, free);
3415
3416 for (region = all_tm_regions; region; region = region->next)
3417 {
3418 /* All the TM stores/loads in the current region. */
3419 size_t i;
3420 basic_block bb;
3421
3422 bitmap_obstack_initialize (&tm_memopt_obstack);
3423
3424 /* Save all BBs for the current region. */
3425 bbs = get_tm_region_blocks (region->entry_block,
3426 region->exit_blocks,
3427 region->irr_blocks,
3428 NULL,
3429 false);
3430
3431 /* Collect all the memory operations. */
3432 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); ++i)
3433 {
3434 bb->aux = tm_memopt_init_sets ();
3435 tm_memopt_accumulate_memops (bb);
3436 }
3437
3438 /* Solve data flow equations and transform each block accordingly. */
3439 tm_memopt_clear_visited (bbs);
3440 tm_memopt_compute_available (region, bbs);
3441 tm_memopt_clear_visited (bbs);
3442 tm_memopt_compute_antic (region, bbs);
3443 tm_memopt_transform_blocks (bbs);
3444
3445 tm_memopt_free_sets (bbs);
3446 VEC_free (basic_block, heap, bbs);
3447 bitmap_obstack_release (&tm_memopt_obstack);
3448 htab_empty (tm_memopt_value_numbers);
3449 }
3450
3451 htab_delete (tm_memopt_value_numbers);
3452 return 0;
3453 }
3454
3455 static bool
gate_tm_memopt(void)3456 gate_tm_memopt (void)
3457 {
3458 return flag_tm && optimize > 0;
3459 }
3460
3461 struct gimple_opt_pass pass_tm_memopt =
3462 {
3463 {
3464 GIMPLE_PASS,
3465 "tmmemopt", /* name */
3466 gate_tm_memopt, /* gate */
3467 execute_tm_memopt, /* execute */
3468 NULL, /* sub */
3469 NULL, /* next */
3470 0, /* static_pass_number */
3471 TV_TRANS_MEM, /* tv_id */
3472 PROP_ssa | PROP_cfg, /* properties_required */
3473 0, /* properties_provided */
3474 0, /* properties_destroyed */
3475 0, /* todo_flags_start */
3476 TODO_dump_func, /* todo_flags_finish */
3477 }
3478 };
3479
3480
3481 /* Interprocedual analysis for the creation of transactional clones.
3482 The aim of this pass is to find which functions are referenced in
3483 a non-irrevocable transaction context, and for those over which
3484 we have control (or user directive), create a version of the
3485 function which uses only the transactional interface to reference
3486 protected memories. This analysis proceeds in several steps:
3487
3488 (1) Collect the set of all possible transactional clones:
3489
3490 (a) For all local public functions marked tm_callable, push
3491 it onto the tm_callee queue.
3492
3493 (b) For all local functions, scan for calls in transaction blocks.
3494 Push the caller and callee onto the tm_caller and tm_callee
3495 queues. Count the number of callers for each callee.
3496
3497 (c) For each local function on the callee list, assume we will
3498 create a transactional clone. Push *all* calls onto the
3499 callee queues; count the number of clone callers separately
3500 to the number of original callers.
3501
3502 (2) Propagate irrevocable status up the dominator tree:
3503
3504 (a) Any external function on the callee list that is not marked
3505 tm_callable is irrevocable. Push all callers of such onto
3506 a worklist.
3507
3508 (b) For each function on the worklist, mark each block that
3509 contains an irrevocable call. Use the AND operator to
3510 propagate that mark up the dominator tree.
3511
3512 (c) If we reach the entry block for a possible transactional
3513 clone, then the transactional clone is irrevocable, and
3514 we should not create the clone after all. Push all
3515 callers onto the worklist.
3516
3517 (d) Place tm_irrevocable calls at the beginning of the relevant
3518 blocks. Special case here is the entry block for the entire
3519 transaction region; there we mark it GTMA_DOES_GO_IRREVOCABLE for
3520 the library to begin the region in serial mode. Decrement
3521 the call count for all callees in the irrevocable region.
3522
3523 (3) Create the transactional clones:
3524
3525 Any tm_callee that still has a non-zero call count is cloned.
3526 */
3527
3528 /* This structure is stored in the AUX field of each cgraph_node. */
3529 struct tm_ipa_cg_data
3530 {
3531 /* The clone of the function that got created. */
3532 struct cgraph_node *clone;
3533
3534 /* The tm regions in the normal function. */
3535 struct tm_region *all_tm_regions;
3536
3537 /* The blocks of the normal/clone functions that contain irrevocable
3538 calls, or blocks that are post-dominated by irrevocable calls. */
3539 bitmap irrevocable_blocks_normal;
3540 bitmap irrevocable_blocks_clone;
3541
3542 /* The blocks of the normal function that are involved in transactions. */
3543 bitmap transaction_blocks_normal;
3544
3545 /* The number of callers to the transactional clone of this function
3546 from normal and transactional clones respectively. */
3547 unsigned tm_callers_normal;
3548 unsigned tm_callers_clone;
3549
3550 /* True if all calls to this function's transactional clone
3551 are irrevocable. Also automatically true if the function
3552 has no transactional clone. */
3553 bool is_irrevocable;
3554
3555 /* Flags indicating the presence of this function in various queues. */
3556 bool in_callee_queue;
3557 bool in_worklist;
3558
3559 /* Flags indicating the kind of scan desired while in the worklist. */
3560 bool want_irr_scan_normal;
3561 };
3562
3563 typedef struct cgraph_node *cgraph_node_p;
3564
3565 DEF_VEC_P (cgraph_node_p);
3566 DEF_VEC_ALLOC_P (cgraph_node_p, heap);
3567
3568 typedef VEC (cgraph_node_p, heap) *cgraph_node_queue;
3569
3570 /* Return the ipa data associated with NODE, allocating zeroed memory
3571 if necessary. TRAVERSE_ALIASES is true if we must traverse aliases
3572 and set *NODE accordingly. */
3573
3574 static struct tm_ipa_cg_data *
get_cg_data(struct cgraph_node ** node,bool traverse_aliases)3575 get_cg_data (struct cgraph_node **node, bool traverse_aliases)
3576 {
3577 struct tm_ipa_cg_data *d;
3578
3579 if (traverse_aliases && (*node)->alias)
3580 *node = cgraph_get_node ((*node)->thunk.alias);
3581
3582 d = (struct tm_ipa_cg_data *) (*node)->aux;
3583
3584 if (d == NULL)
3585 {
3586 d = (struct tm_ipa_cg_data *)
3587 obstack_alloc (&tm_obstack.obstack, sizeof (*d));
3588 (*node)->aux = (void *) d;
3589 memset (d, 0, sizeof (*d));
3590 }
3591
3592 return d;
3593 }
3594
3595 /* Add NODE to the end of QUEUE, unless IN_QUEUE_P indicates that
3596 it is already present. */
3597
3598 static void
maybe_push_queue(struct cgraph_node * node,cgraph_node_queue * queue_p,bool * in_queue_p)3599 maybe_push_queue (struct cgraph_node *node,
3600 cgraph_node_queue *queue_p, bool *in_queue_p)
3601 {
3602 if (!*in_queue_p)
3603 {
3604 *in_queue_p = true;
3605 VEC_safe_push (cgraph_node_p, heap, *queue_p, node);
3606 }
3607 }
3608
3609 /* A subroutine of ipa_tm_scan_calls_transaction and ipa_tm_scan_calls_clone.
3610 Queue all callees within block BB. */
3611
3612 static void
ipa_tm_scan_calls_block(cgraph_node_queue * callees_p,basic_block bb,bool for_clone)3613 ipa_tm_scan_calls_block (cgraph_node_queue *callees_p,
3614 basic_block bb, bool for_clone)
3615 {
3616 gimple_stmt_iterator gsi;
3617
3618 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3619 {
3620 gimple stmt = gsi_stmt (gsi);
3621 if (is_gimple_call (stmt) && !is_tm_pure_call (stmt))
3622 {
3623 tree fndecl = gimple_call_fndecl (stmt);
3624 if (fndecl)
3625 {
3626 struct tm_ipa_cg_data *d;
3627 unsigned *pcallers;
3628 struct cgraph_node *node;
3629
3630 if (is_tm_ending_fndecl (fndecl))
3631 continue;
3632 if (find_tm_replacement_function (fndecl))
3633 continue;
3634
3635 node = cgraph_get_node (fndecl);
3636 gcc_assert (node != NULL);
3637 d = get_cg_data (&node, true);
3638
3639 pcallers = (for_clone ? &d->tm_callers_clone
3640 : &d->tm_callers_normal);
3641 *pcallers += 1;
3642
3643 maybe_push_queue (node, callees_p, &d->in_callee_queue);
3644 }
3645 }
3646 }
3647 }
3648
3649 /* Scan all calls in NODE that are within a transaction region,
3650 and push the resulting nodes into the callee queue. */
3651
3652 static void
ipa_tm_scan_calls_transaction(struct tm_ipa_cg_data * d,cgraph_node_queue * callees_p)3653 ipa_tm_scan_calls_transaction (struct tm_ipa_cg_data *d,
3654 cgraph_node_queue *callees_p)
3655 {
3656 struct tm_region *r;
3657
3658 d->transaction_blocks_normal = BITMAP_ALLOC (&tm_obstack);
3659 d->all_tm_regions = all_tm_regions;
3660
3661 for (r = all_tm_regions; r; r = r->next)
3662 {
3663 VEC (basic_block, heap) *bbs;
3664 basic_block bb;
3665 unsigned i;
3666
3667 bbs = get_tm_region_blocks (r->entry_block, r->exit_blocks, NULL,
3668 d->transaction_blocks_normal, false);
3669
3670 FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
3671 ipa_tm_scan_calls_block (callees_p, bb, false);
3672
3673 VEC_free (basic_block, heap, bbs);
3674 }
3675 }
3676
3677 /* Scan all calls in NODE as if this is the transactional clone,
3678 and push the destinations into the callee queue. */
3679
3680 static void
ipa_tm_scan_calls_clone(struct cgraph_node * node,cgraph_node_queue * callees_p)3681 ipa_tm_scan_calls_clone (struct cgraph_node *node,
3682 cgraph_node_queue *callees_p)
3683 {
3684 struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3685 basic_block bb;
3686
3687 FOR_EACH_BB_FN (bb, fn)
3688 ipa_tm_scan_calls_block (callees_p, bb, true);
3689 }
3690
3691 /* The function NODE has been detected to be irrevocable. Push all
3692 of its callers onto WORKLIST for the purpose of re-scanning them. */
3693
3694 static void
ipa_tm_note_irrevocable(struct cgraph_node * node,cgraph_node_queue * worklist_p)3695 ipa_tm_note_irrevocable (struct cgraph_node *node,
3696 cgraph_node_queue *worklist_p)
3697 {
3698 struct tm_ipa_cg_data *d = get_cg_data (&node, true);
3699 struct cgraph_edge *e;
3700
3701 d->is_irrevocable = true;
3702
3703 for (e = node->callers; e ; e = e->next_caller)
3704 {
3705 basic_block bb;
3706 struct cgraph_node *caller;
3707
3708 /* Don't examine recursive calls. */
3709 if (e->caller == node)
3710 continue;
3711 /* Even if we think we can go irrevocable, believe the user
3712 above all. */
3713 if (is_tm_safe_or_pure (e->caller->decl))
3714 continue;
3715
3716 caller = e->caller;
3717 d = get_cg_data (&caller, true);
3718
3719 /* Check if the callee is in a transactional region. If so,
3720 schedule the function for normal re-scan as well. */
3721 bb = gimple_bb (e->call_stmt);
3722 gcc_assert (bb != NULL);
3723 if (d->transaction_blocks_normal
3724 && bitmap_bit_p (d->transaction_blocks_normal, bb->index))
3725 d->want_irr_scan_normal = true;
3726
3727 maybe_push_queue (caller, worklist_p, &d->in_worklist);
3728 }
3729 }
3730
3731 /* A subroutine of ipa_tm_scan_irr_blocks; return true iff any statement
3732 within the block is irrevocable. */
3733
3734 static bool
ipa_tm_scan_irr_block(basic_block bb)3735 ipa_tm_scan_irr_block (basic_block bb)
3736 {
3737 gimple_stmt_iterator gsi;
3738 tree fn;
3739
3740 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3741 {
3742 gimple stmt = gsi_stmt (gsi);
3743 switch (gimple_code (stmt))
3744 {
3745 case GIMPLE_CALL:
3746 if (is_tm_pure_call (stmt))
3747 break;
3748
3749 fn = gimple_call_fn (stmt);
3750
3751 /* Functions with the attribute are by definition irrevocable. */
3752 if (is_tm_irrevocable (fn))
3753 return true;
3754
3755 /* For direct function calls, go ahead and check for replacement
3756 functions, or transitive irrevocable functions. For indirect
3757 functions, we'll ask the runtime. */
3758 if (TREE_CODE (fn) == ADDR_EXPR)
3759 {
3760 struct tm_ipa_cg_data *d;
3761 struct cgraph_node *node;
3762
3763 fn = TREE_OPERAND (fn, 0);
3764 if (is_tm_ending_fndecl (fn))
3765 break;
3766 if (find_tm_replacement_function (fn))
3767 break;
3768
3769 node = cgraph_get_node(fn);
3770 d = get_cg_data (&node, true);
3771
3772 /* Return true if irrevocable, but above all, believe
3773 the user. */
3774 if (d->is_irrevocable
3775 && !is_tm_safe_or_pure (fn))
3776 return true;
3777 }
3778 break;
3779
3780 case GIMPLE_ASM:
3781 /* ??? The Approved Method of indicating that an inline
3782 assembly statement is not relevant to the transaction
3783 is to wrap it in a __tm_waiver block. This is not
3784 yet implemented, so we can't check for it. */
3785 if (is_tm_safe (current_function_decl))
3786 {
3787 tree t = build1 (NOP_EXPR, void_type_node, size_zero_node);
3788 SET_EXPR_LOCATION (t, gimple_location (stmt));
3789 TREE_BLOCK (t) = gimple_block (stmt);
3790 error ("%Kasm not allowed in %<transaction_safe%> function", t);
3791 }
3792 return true;
3793
3794 default:
3795 break;
3796 }
3797 }
3798
3799 return false;
3800 }
3801
3802 /* For each of the blocks seeded witin PQUEUE, walk the CFG looking
3803 for new irrevocable blocks, marking them in NEW_IRR. Don't bother
3804 scanning past OLD_IRR or EXIT_BLOCKS. */
3805
3806 static bool
ipa_tm_scan_irr_blocks(VEC (basic_block,heap)** pqueue,bitmap new_irr,bitmap old_irr,bitmap exit_blocks)3807 ipa_tm_scan_irr_blocks (VEC (basic_block, heap) **pqueue, bitmap new_irr,
3808 bitmap old_irr, bitmap exit_blocks)
3809 {
3810 bool any_new_irr = false;
3811 edge e;
3812 edge_iterator ei;
3813 bitmap visited_blocks = BITMAP_ALLOC (NULL);
3814
3815 do
3816 {
3817 basic_block bb = VEC_pop (basic_block, *pqueue);
3818
3819 /* Don't re-scan blocks we know already are irrevocable. */
3820 if (old_irr && bitmap_bit_p (old_irr, bb->index))
3821 continue;
3822
3823 if (ipa_tm_scan_irr_block (bb))
3824 {
3825 bitmap_set_bit (new_irr, bb->index);
3826 any_new_irr = true;
3827 }
3828 else if (exit_blocks == NULL || !bitmap_bit_p (exit_blocks, bb->index))
3829 {
3830 FOR_EACH_EDGE (e, ei, bb->succs)
3831 if (!bitmap_bit_p (visited_blocks, e->dest->index))
3832 {
3833 bitmap_set_bit (visited_blocks, e->dest->index);
3834 VEC_safe_push (basic_block, heap, *pqueue, e->dest);
3835 }
3836 }
3837 }
3838 while (!VEC_empty (basic_block, *pqueue));
3839
3840 BITMAP_FREE (visited_blocks);
3841
3842 return any_new_irr;
3843 }
3844
3845 /* Propagate the irrevocable property both up and down the dominator tree.
3846 BB is the current block being scanned; EXIT_BLOCKS are the edges of the
3847 TM regions; OLD_IRR are the results of a previous scan of the dominator
3848 tree which has been fully propagated; NEW_IRR is the set of new blocks
3849 which are gaining the irrevocable property during the current scan. */
3850
3851 static void
ipa_tm_propagate_irr(basic_block entry_block,bitmap new_irr,bitmap old_irr,bitmap exit_blocks)3852 ipa_tm_propagate_irr (basic_block entry_block, bitmap new_irr,
3853 bitmap old_irr, bitmap exit_blocks)
3854 {
3855 VEC (basic_block, heap) *bbs;
3856 bitmap all_region_blocks;
3857
3858 /* If this block is in the old set, no need to rescan. */
3859 if (old_irr && bitmap_bit_p (old_irr, entry_block->index))
3860 return;
3861
3862 all_region_blocks = BITMAP_ALLOC (&tm_obstack);
3863 bbs = get_tm_region_blocks (entry_block, exit_blocks, NULL,
3864 all_region_blocks, false);
3865 do
3866 {
3867 basic_block bb = VEC_pop (basic_block, bbs);
3868 bool this_irr = bitmap_bit_p (new_irr, bb->index);
3869 bool all_son_irr = false;
3870 edge_iterator ei;
3871 edge e;
3872
3873 /* Propagate up. If my children are, I am too, but we must have
3874 at least one child that is. */
3875 if (!this_irr)
3876 {
3877 FOR_EACH_EDGE (e, ei, bb->succs)
3878 {
3879 if (!bitmap_bit_p (new_irr, e->dest->index))
3880 {
3881 all_son_irr = false;
3882 break;
3883 }
3884 else
3885 all_son_irr = true;
3886 }
3887 if (all_son_irr)
3888 {
3889 /* Add block to new_irr if it hasn't already been processed. */
3890 if (!old_irr || !bitmap_bit_p (old_irr, bb->index))
3891 {
3892 bitmap_set_bit (new_irr, bb->index);
3893 this_irr = true;
3894 }
3895 }
3896 }
3897
3898 /* Propagate down to everyone we immediately dominate. */
3899 if (this_irr)
3900 {
3901 basic_block son;
3902 for (son = first_dom_son (CDI_DOMINATORS, bb);
3903 son;
3904 son = next_dom_son (CDI_DOMINATORS, son))
3905 {
3906 /* Make sure block is actually in a TM region, and it
3907 isn't already in old_irr. */
3908 if ((!old_irr || !bitmap_bit_p (old_irr, son->index))
3909 && bitmap_bit_p (all_region_blocks, son->index))
3910 bitmap_set_bit (new_irr, son->index);
3911 }
3912 }
3913 }
3914 while (!VEC_empty (basic_block, bbs));
3915
3916 BITMAP_FREE (all_region_blocks);
3917 VEC_free (basic_block, heap, bbs);
3918 }
3919
3920 static void
ipa_tm_decrement_clone_counts(basic_block bb,bool for_clone)3921 ipa_tm_decrement_clone_counts (basic_block bb, bool for_clone)
3922 {
3923 gimple_stmt_iterator gsi;
3924
3925 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3926 {
3927 gimple stmt = gsi_stmt (gsi);
3928 if (is_gimple_call (stmt) && !is_tm_pure_call (stmt))
3929 {
3930 tree fndecl = gimple_call_fndecl (stmt);
3931 if (fndecl)
3932 {
3933 struct tm_ipa_cg_data *d;
3934 unsigned *pcallers;
3935 struct cgraph_node *tnode;
3936
3937 if (is_tm_ending_fndecl (fndecl))
3938 continue;
3939 if (find_tm_replacement_function (fndecl))
3940 continue;
3941
3942 tnode = cgraph_get_node (fndecl);
3943 d = get_cg_data (&tnode, true);
3944
3945 pcallers = (for_clone ? &d->tm_callers_clone
3946 : &d->tm_callers_normal);
3947
3948 gcc_assert (*pcallers > 0);
3949 *pcallers -= 1;
3950 }
3951 }
3952 }
3953 }
3954
3955 /* (Re-)Scan the transaction blocks in NODE for calls to irrevocable functions,
3956 as well as other irrevocable actions such as inline assembly. Mark all
3957 such blocks as irrevocable and decrement the number of calls to
3958 transactional clones. Return true if, for the transactional clone, the
3959 entire function is irrevocable. */
3960
3961 static bool
ipa_tm_scan_irr_function(struct cgraph_node * node,bool for_clone)3962 ipa_tm_scan_irr_function (struct cgraph_node *node, bool for_clone)
3963 {
3964 struct tm_ipa_cg_data *d;
3965 bitmap new_irr, old_irr;
3966 VEC (basic_block, heap) *queue;
3967 bool ret = false;
3968
3969 /* Builtin operators (operator new, and such). */
3970 if (DECL_STRUCT_FUNCTION (node->decl) == NULL
3971 || DECL_STRUCT_FUNCTION (node->decl)->cfg == NULL)
3972 return false;
3973
3974 current_function_decl = node->decl;
3975 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
3976 calculate_dominance_info (CDI_DOMINATORS);
3977
3978 d = get_cg_data (&node, true);
3979 queue = VEC_alloc (basic_block, heap, 10);
3980 new_irr = BITMAP_ALLOC (&tm_obstack);
3981
3982 /* Scan each tm region, propagating irrevocable status through the tree. */
3983 if (for_clone)
3984 {
3985 old_irr = d->irrevocable_blocks_clone;
3986 VEC_quick_push (basic_block, queue, single_succ (ENTRY_BLOCK_PTR));
3987 if (ipa_tm_scan_irr_blocks (&queue, new_irr, old_irr, NULL))
3988 {
3989 ipa_tm_propagate_irr (single_succ (ENTRY_BLOCK_PTR), new_irr,
3990 old_irr, NULL);
3991 ret = bitmap_bit_p (new_irr, single_succ (ENTRY_BLOCK_PTR)->index);
3992 }
3993 }
3994 else
3995 {
3996 struct tm_region *region;
3997
3998 old_irr = d->irrevocable_blocks_normal;
3999 for (region = d->all_tm_regions; region; region = region->next)
4000 {
4001 VEC_quick_push (basic_block, queue, region->entry_block);
4002 if (ipa_tm_scan_irr_blocks (&queue, new_irr, old_irr,
4003 region->exit_blocks))
4004 ipa_tm_propagate_irr (region->entry_block, new_irr, old_irr,
4005 region->exit_blocks);
4006 }
4007 }
4008
4009 /* If we found any new irrevocable blocks, reduce the call count for
4010 transactional clones within the irrevocable blocks. Save the new
4011 set of irrevocable blocks for next time. */
4012 if (!bitmap_empty_p (new_irr))
4013 {
4014 bitmap_iterator bmi;
4015 unsigned i;
4016
4017 EXECUTE_IF_SET_IN_BITMAP (new_irr, 0, i, bmi)
4018 ipa_tm_decrement_clone_counts (BASIC_BLOCK (i), for_clone);
4019
4020 if (old_irr)
4021 {
4022 bitmap_ior_into (old_irr, new_irr);
4023 BITMAP_FREE (new_irr);
4024 }
4025 else if (for_clone)
4026 d->irrevocable_blocks_clone = new_irr;
4027 else
4028 d->irrevocable_blocks_normal = new_irr;
4029
4030 if (dump_file && new_irr)
4031 {
4032 const char *dname;
4033 bitmap_iterator bmi;
4034 unsigned i;
4035
4036 dname = lang_hooks.decl_printable_name (current_function_decl, 2);
4037 EXECUTE_IF_SET_IN_BITMAP (new_irr, 0, i, bmi)
4038 fprintf (dump_file, "%s: bb %d goes irrevocable\n", dname, i);
4039 }
4040 }
4041 else
4042 BITMAP_FREE (new_irr);
4043
4044 VEC_free (basic_block, heap, queue);
4045 pop_cfun ();
4046 current_function_decl = NULL;
4047
4048 return ret;
4049 }
4050
4051 /* Return true if, for the transactional clone of NODE, any call
4052 may enter irrevocable mode. */
4053
4054 static bool
ipa_tm_mayenterirr_function(struct cgraph_node * node)4055 ipa_tm_mayenterirr_function (struct cgraph_node *node)
4056 {
4057 struct tm_ipa_cg_data *d;
4058 tree decl;
4059 unsigned flags;
4060
4061 d = get_cg_data (&node, true);
4062 decl = node->decl;
4063 flags = flags_from_decl_or_type (decl);
4064
4065 /* Handle some TM builtins. Ordinarily these aren't actually generated
4066 at this point, but handling these functions when written in by the
4067 user makes it easier to build unit tests. */
4068 if (flags & ECF_TM_BUILTIN)
4069 return false;
4070
4071 /* Filter out all functions that are marked. */
4072 if (flags & ECF_TM_PURE)
4073 return false;
4074 if (is_tm_safe (decl))
4075 return false;
4076 if (is_tm_irrevocable (decl))
4077 return true;
4078 if (is_tm_callable (decl))
4079 return true;
4080 if (find_tm_replacement_function (decl))
4081 return true;
4082
4083 /* If we aren't seeing the final version of the function we don't
4084 know what it will contain at runtime. */
4085 if (cgraph_function_body_availability (node) < AVAIL_AVAILABLE)
4086 return true;
4087
4088 /* If the function must go irrevocable, then of course true. */
4089 if (d->is_irrevocable)
4090 return true;
4091
4092 /* If there are any blocks marked irrevocable, then the function
4093 as a whole may enter irrevocable. */
4094 if (d->irrevocable_blocks_clone)
4095 return true;
4096
4097 /* We may have previously marked this function as tm_may_enter_irr;
4098 see pass_diagnose_tm_blocks. */
4099 if (node->local.tm_may_enter_irr)
4100 return true;
4101
4102 /* Recurse on the main body for aliases. In general, this will
4103 result in one of the bits above being set so that we will not
4104 have to recurse next time. */
4105 if (node->alias)
4106 return ipa_tm_mayenterirr_function (cgraph_get_node (node->thunk.alias));
4107
4108 /* What remains is unmarked local functions without items that force
4109 the function to go irrevocable. */
4110 return false;
4111 }
4112
4113 /* Diagnose calls from transaction_safe functions to unmarked
4114 functions that are determined to not be safe. */
4115
4116 static void
ipa_tm_diagnose_tm_safe(struct cgraph_node * node)4117 ipa_tm_diagnose_tm_safe (struct cgraph_node *node)
4118 {
4119 struct cgraph_edge *e;
4120
4121 for (e = node->callees; e ; e = e->next_callee)
4122 if (!is_tm_callable (e->callee->decl)
4123 && e->callee->local.tm_may_enter_irr)
4124 error_at (gimple_location (e->call_stmt),
4125 "unsafe function call %qD within "
4126 "%<transaction_safe%> function", e->callee->decl);
4127 }
4128
4129 /* Diagnose call from atomic transactions to unmarked functions
4130 that are determined to not be safe. */
4131
4132 static void
ipa_tm_diagnose_transaction(struct cgraph_node * node,struct tm_region * all_tm_regions)4133 ipa_tm_diagnose_transaction (struct cgraph_node *node,
4134 struct tm_region *all_tm_regions)
4135 {
4136 struct tm_region *r;
4137
4138 for (r = all_tm_regions; r ; r = r->next)
4139 if (gimple_transaction_subcode (r->transaction_stmt) & GTMA_IS_RELAXED)
4140 {
4141 /* Atomic transactions can be nested inside relaxed. */
4142 if (r->inner)
4143 ipa_tm_diagnose_transaction (node, r->inner);
4144 }
4145 else
4146 {
4147 VEC (basic_block, heap) *bbs;
4148 gimple_stmt_iterator gsi;
4149 basic_block bb;
4150 size_t i;
4151
4152 bbs = get_tm_region_blocks (r->entry_block, r->exit_blocks,
4153 r->irr_blocks, NULL, false);
4154
4155 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); ++i)
4156 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4157 {
4158 gimple stmt = gsi_stmt (gsi);
4159 tree fndecl;
4160
4161 if (gimple_code (stmt) == GIMPLE_ASM)
4162 {
4163 error_at (gimple_location (stmt),
4164 "asm not allowed in atomic transaction");
4165 continue;
4166 }
4167
4168 if (!is_gimple_call (stmt))
4169 continue;
4170 fndecl = gimple_call_fndecl (stmt);
4171
4172 /* Indirect function calls have been diagnosed already. */
4173 if (!fndecl)
4174 continue;
4175
4176 /* Stop at the end of the transaction. */
4177 if (is_tm_ending_fndecl (fndecl))
4178 {
4179 if (bitmap_bit_p (r->exit_blocks, bb->index))
4180 break;
4181 continue;
4182 }
4183
4184 /* Marked functions have been diagnosed already. */
4185 if (is_tm_pure_call (stmt))
4186 continue;
4187 if (is_tm_callable (fndecl))
4188 continue;
4189
4190 if (cgraph_local_info (fndecl)->tm_may_enter_irr)
4191 error_at (gimple_location (stmt),
4192 "unsafe function call %qD within "
4193 "atomic transaction", fndecl);
4194 }
4195
4196 VEC_free (basic_block, heap, bbs);
4197 }
4198 }
4199
4200 /* Return a transactional mangled name for the DECL_ASSEMBLER_NAME in
4201 OLD_DECL. The returned value is a freshly malloced pointer that
4202 should be freed by the caller. */
4203
4204 static tree
tm_mangle(tree old_asm_id)4205 tm_mangle (tree old_asm_id)
4206 {
4207 const char *old_asm_name;
4208 char *tm_name;
4209 void *alloc = NULL;
4210 struct demangle_component *dc;
4211 tree new_asm_id;
4212
4213 /* Determine if the symbol is already a valid C++ mangled name. Do this
4214 even for C, which might be interfacing with C++ code via appropriately
4215 ugly identifiers. */
4216 /* ??? We could probably do just as well checking for "_Z" and be done. */
4217 old_asm_name = IDENTIFIER_POINTER (old_asm_id);
4218 dc = cplus_demangle_v3_components (old_asm_name, DMGL_NO_OPTS, &alloc);
4219
4220 if (dc == NULL)
4221 {
4222 char length[8];
4223
4224 do_unencoded:
4225 sprintf (length, "%u", IDENTIFIER_LENGTH (old_asm_id));
4226 tm_name = concat ("_ZGTt", length, old_asm_name, NULL);
4227 }
4228 else
4229 {
4230 old_asm_name += 2; /* Skip _Z */
4231
4232 switch (dc->type)
4233 {
4234 case DEMANGLE_COMPONENT_TRANSACTION_CLONE:
4235 case DEMANGLE_COMPONENT_NONTRANSACTION_CLONE:
4236 /* Don't play silly games, you! */
4237 goto do_unencoded;
4238
4239 case DEMANGLE_COMPONENT_HIDDEN_ALIAS:
4240 /* I'd really like to know if we can ever be passed one of
4241 these from the C++ front end. The Logical Thing would
4242 seem that hidden-alias should be outer-most, so that we
4243 get hidden-alias of a transaction-clone and not vice-versa. */
4244 old_asm_name += 2;
4245 break;
4246
4247 default:
4248 break;
4249 }
4250
4251 tm_name = concat ("_ZGTt", old_asm_name, NULL);
4252 }
4253 free (alloc);
4254
4255 new_asm_id = get_identifier (tm_name);
4256 free (tm_name);
4257
4258 return new_asm_id;
4259 }
4260
4261 static inline void
ipa_tm_mark_needed_node(struct cgraph_node * node)4262 ipa_tm_mark_needed_node (struct cgraph_node *node)
4263 {
4264 cgraph_mark_needed_node (node);
4265 /* ??? function_and_variable_visibility will reset
4266 the needed bit, without actually checking. */
4267 node->analyzed = 1;
4268 }
4269
4270 /* Callback data for ipa_tm_create_version_alias. */
4271 struct create_version_alias_info
4272 {
4273 struct cgraph_node *old_node;
4274 tree new_decl;
4275 };
4276
4277 /* A subroutine of ipa_tm_create_version, called via
4278 cgraph_for_node_and_aliases. Create new tm clones for each of
4279 the existing aliases. */
4280 static bool
ipa_tm_create_version_alias(struct cgraph_node * node,void * data)4281 ipa_tm_create_version_alias (struct cgraph_node *node, void *data)
4282 {
4283 struct create_version_alias_info *info
4284 = (struct create_version_alias_info *)data;
4285 tree old_decl, new_decl, tm_name;
4286 struct cgraph_node *new_node;
4287
4288 if (!node->same_body_alias)
4289 return false;
4290
4291 old_decl = node->decl;
4292 tm_name = tm_mangle (DECL_ASSEMBLER_NAME (old_decl));
4293 new_decl = build_decl (DECL_SOURCE_LOCATION (old_decl),
4294 TREE_CODE (old_decl), tm_name,
4295 TREE_TYPE (old_decl));
4296
4297 SET_DECL_ASSEMBLER_NAME (new_decl, tm_name);
4298 SET_DECL_RTL (new_decl, NULL);
4299
4300 /* Based loosely on C++'s make_alias_for(). */
4301 TREE_PUBLIC (new_decl) = TREE_PUBLIC (old_decl);
4302 DECL_CONTEXT (new_decl) = DECL_CONTEXT (old_decl);
4303 DECL_LANG_SPECIFIC (new_decl) = DECL_LANG_SPECIFIC (old_decl);
4304 TREE_READONLY (new_decl) = TREE_READONLY (old_decl);
4305 DECL_EXTERNAL (new_decl) = 0;
4306 DECL_ARTIFICIAL (new_decl) = 1;
4307 TREE_ADDRESSABLE (new_decl) = 1;
4308 TREE_USED (new_decl) = 1;
4309 TREE_SYMBOL_REFERENCED (tm_name) = 1;
4310
4311 /* Perform the same remapping to the comdat group. */
4312 if (DECL_ONE_ONLY (new_decl))
4313 DECL_COMDAT_GROUP (new_decl) = tm_mangle (DECL_COMDAT_GROUP (old_decl));
4314
4315 new_node = cgraph_same_body_alias (NULL, new_decl, info->new_decl);
4316 new_node->tm_clone = true;
4317 new_node->local.externally_visible = info->old_node->local.externally_visible;
4318 /* ?? Do not traverse aliases here. */
4319 get_cg_data (&node, false)->clone = new_node;
4320
4321 record_tm_clone_pair (old_decl, new_decl);
4322
4323 if (info->old_node->needed
4324 || ipa_ref_list_first_refering (&info->old_node->ref_list))
4325 ipa_tm_mark_needed_node (new_node);
4326 return false;
4327 }
4328
4329 /* Create a copy of the function (possibly declaration only) of OLD_NODE,
4330 appropriate for the transactional clone. */
4331
4332 static void
ipa_tm_create_version(struct cgraph_node * old_node)4333 ipa_tm_create_version (struct cgraph_node *old_node)
4334 {
4335 tree new_decl, old_decl, tm_name;
4336 struct cgraph_node *new_node;
4337
4338 old_decl = old_node->decl;
4339 new_decl = copy_node (old_decl);
4340
4341 /* DECL_ASSEMBLER_NAME needs to be set before we call
4342 cgraph_copy_node_for_versioning below, because cgraph_node will
4343 fill the assembler_name_hash. */
4344 tm_name = tm_mangle (DECL_ASSEMBLER_NAME (old_decl));
4345 SET_DECL_ASSEMBLER_NAME (new_decl, tm_name);
4346 SET_DECL_RTL (new_decl, NULL);
4347 TREE_SYMBOL_REFERENCED (tm_name) = 1;
4348
4349 /* Perform the same remapping to the comdat group. */
4350 if (DECL_ONE_ONLY (new_decl))
4351 DECL_COMDAT_GROUP (new_decl) = tm_mangle (DECL_COMDAT_GROUP (old_decl));
4352
4353 new_node = cgraph_copy_node_for_versioning (old_node, new_decl, NULL, NULL);
4354 new_node->local.externally_visible = old_node->local.externally_visible;
4355 new_node->lowered = true;
4356 new_node->tm_clone = 1;
4357 get_cg_data (&old_node, true)->clone = new_node;
4358
4359 if (cgraph_function_body_availability (old_node) >= AVAIL_OVERWRITABLE)
4360 {
4361 /* Remap extern inline to static inline. */
4362 /* ??? Is it worth trying to use make_decl_one_only? */
4363 if (DECL_DECLARED_INLINE_P (new_decl) && DECL_EXTERNAL (new_decl))
4364 {
4365 DECL_EXTERNAL (new_decl) = 0;
4366 TREE_PUBLIC (new_decl) = 0;
4367 DECL_WEAK (new_decl) = 0;
4368 }
4369
4370 tree_function_versioning (old_decl, new_decl, NULL, false, NULL, false,
4371 NULL, NULL);
4372 }
4373
4374 record_tm_clone_pair (old_decl, new_decl);
4375
4376 cgraph_call_function_insertion_hooks (new_node);
4377 if (old_node->needed
4378 || ipa_ref_list_first_refering (&old_node->ref_list))
4379 ipa_tm_mark_needed_node (new_node);
4380
4381 /* Do the same thing, but for any aliases of the original node. */
4382 {
4383 struct create_version_alias_info data;
4384 data.old_node = old_node;
4385 data.new_decl = new_decl;
4386 cgraph_for_node_and_aliases (old_node, ipa_tm_create_version_alias,
4387 &data, true);
4388 }
4389 }
4390
4391 /* Construct a call to TM_IRREVOCABLE and insert it at the beginning of BB. */
4392
4393 static void
ipa_tm_insert_irr_call(struct cgraph_node * node,struct tm_region * region,basic_block bb)4394 ipa_tm_insert_irr_call (struct cgraph_node *node, struct tm_region *region,
4395 basic_block bb)
4396 {
4397 gimple_stmt_iterator gsi;
4398 gimple g;
4399
4400 transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
4401
4402 g = gimple_build_call (builtin_decl_explicit (BUILT_IN_TM_IRREVOCABLE),
4403 1, build_int_cst (NULL_TREE, MODE_SERIALIRREVOCABLE));
4404
4405 split_block_after_labels (bb);
4406 gsi = gsi_after_labels (bb);
4407 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
4408
4409 cgraph_create_edge (node,
4410 cgraph_get_create_node
4411 (builtin_decl_explicit (BUILT_IN_TM_IRREVOCABLE)),
4412 g, 0,
4413 compute_call_stmt_bb_frequency (node->decl,
4414 gimple_bb (g)));
4415 }
4416
4417 /* Construct a call to TM_GETTMCLONE and insert it before GSI. */
4418
4419 static bool
ipa_tm_insert_gettmclone_call(struct cgraph_node * node,struct tm_region * region,gimple_stmt_iterator * gsi,gimple stmt)4420 ipa_tm_insert_gettmclone_call (struct cgraph_node *node,
4421 struct tm_region *region,
4422 gimple_stmt_iterator *gsi, gimple stmt)
4423 {
4424 tree gettm_fn, ret, old_fn, callfn;
4425 gimple g, g2;
4426 bool safe;
4427
4428 old_fn = gimple_call_fn (stmt);
4429
4430 if (TREE_CODE (old_fn) == ADDR_EXPR)
4431 {
4432 tree fndecl = TREE_OPERAND (old_fn, 0);
4433 tree clone = get_tm_clone_pair (fndecl);
4434
4435 /* By transforming the call into a TM_GETTMCLONE, we are
4436 technically taking the address of the original function and
4437 its clone. Explain this so inlining will know this function
4438 is needed. */
4439 cgraph_mark_address_taken_node (cgraph_get_node (fndecl));
4440 if (clone)
4441 cgraph_mark_address_taken_node (cgraph_get_node (clone));
4442 }
4443
4444 safe = is_tm_safe (TREE_TYPE (old_fn));
4445 gettm_fn = builtin_decl_explicit (safe ? BUILT_IN_TM_GETTMCLONE_SAFE
4446 : BUILT_IN_TM_GETTMCLONE_IRR);
4447 ret = create_tmp_var (ptr_type_node, NULL);
4448 add_referenced_var (ret);
4449
4450 if (!safe)
4451 transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
4452
4453 /* Discard OBJ_TYPE_REF, since we weren't able to fold it. */
4454 if (TREE_CODE (old_fn) == OBJ_TYPE_REF)
4455 old_fn = OBJ_TYPE_REF_EXPR (old_fn);
4456
4457 g = gimple_build_call (gettm_fn, 1, old_fn);
4458 ret = make_ssa_name (ret, g);
4459 gimple_call_set_lhs (g, ret);
4460
4461 gsi_insert_before (gsi, g, GSI_SAME_STMT);
4462
4463 cgraph_create_edge (node, cgraph_get_create_node (gettm_fn), g, 0,
4464 compute_call_stmt_bb_frequency (node->decl,
4465 gimple_bb(g)));
4466
4467 /* Cast return value from tm_gettmclone* into appropriate function
4468 pointer. */
4469 callfn = create_tmp_var (TREE_TYPE (old_fn), NULL);
4470 add_referenced_var (callfn);
4471 g2 = gimple_build_assign (callfn,
4472 fold_build1 (NOP_EXPR, TREE_TYPE (callfn), ret));
4473 callfn = make_ssa_name (callfn, g2);
4474 gimple_assign_set_lhs (g2, callfn);
4475 gsi_insert_before (gsi, g2, GSI_SAME_STMT);
4476
4477 /* ??? This is a hack to preserve the NOTHROW bit on the call,
4478 which we would have derived from the decl. Failure to save
4479 this bit means we might have to split the basic block. */
4480 if (gimple_call_nothrow_p (stmt))
4481 gimple_call_set_nothrow (stmt, true);
4482
4483 gimple_call_set_fn (stmt, callfn);
4484
4485 /* Discarding OBJ_TYPE_REF above may produce incompatible LHS and RHS
4486 for a call statement. Fix it. */
4487 {
4488 tree lhs = gimple_call_lhs (stmt);
4489 tree rettype = TREE_TYPE (gimple_call_fntype (stmt));
4490 if (lhs
4491 && !useless_type_conversion_p (TREE_TYPE (lhs), rettype))
4492 {
4493 tree temp;
4494
4495 temp = make_rename_temp (rettype, 0);
4496 gimple_call_set_lhs (stmt, temp);
4497
4498 g2 = gimple_build_assign (lhs,
4499 fold_build1 (VIEW_CONVERT_EXPR,
4500 TREE_TYPE (lhs), temp));
4501 gsi_insert_after (gsi, g2, GSI_SAME_STMT);
4502 }
4503 }
4504
4505 update_stmt (stmt);
4506
4507 return true;
4508 }
4509
4510 /* Helper function for ipa_tm_transform_calls*. Given a call
4511 statement in GSI which resides inside transaction REGION, redirect
4512 the call to either its wrapper function, or its clone. */
4513
4514 static void
ipa_tm_transform_calls_redirect(struct cgraph_node * node,struct tm_region * region,gimple_stmt_iterator * gsi,bool * need_ssa_rename_p)4515 ipa_tm_transform_calls_redirect (struct cgraph_node *node,
4516 struct tm_region *region,
4517 gimple_stmt_iterator *gsi,
4518 bool *need_ssa_rename_p)
4519 {
4520 gimple stmt = gsi_stmt (*gsi);
4521 struct cgraph_node *new_node;
4522 struct cgraph_edge *e = cgraph_edge (node, stmt);
4523 tree fndecl = gimple_call_fndecl (stmt);
4524
4525 /* For indirect calls, pass the address through the runtime. */
4526 if (fndecl == NULL)
4527 {
4528 *need_ssa_rename_p |=
4529 ipa_tm_insert_gettmclone_call (node, region, gsi, stmt);
4530 return;
4531 }
4532
4533 /* Handle some TM builtins. Ordinarily these aren't actually generated
4534 at this point, but handling these functions when written in by the
4535 user makes it easier to build unit tests. */
4536 if (flags_from_decl_or_type (fndecl) & ECF_TM_BUILTIN)
4537 return;
4538
4539 /* Fixup recursive calls inside clones. */
4540 /* ??? Why did cgraph_copy_node_for_versioning update the call edges
4541 for recursion but not update the call statements themselves? */
4542 if (e->caller == e->callee && decl_is_tm_clone (current_function_decl))
4543 {
4544 gimple_call_set_fndecl (stmt, current_function_decl);
4545 return;
4546 }
4547
4548 /* If there is a replacement, use it. */
4549 fndecl = find_tm_replacement_function (fndecl);
4550 if (fndecl)
4551 {
4552 new_node = cgraph_get_create_node (fndecl);
4553
4554 /* ??? Mark all transaction_wrap functions tm_may_enter_irr.
4555
4556 We can't do this earlier in record_tm_replacement because
4557 cgraph_remove_unreachable_nodes is called before we inject
4558 references to the node. Further, we can't do this in some
4559 nice central place in ipa_tm_execute because we don't have
4560 the exact list of wrapper functions that would be used.
4561 Marking more wrappers than necessary results in the creation
4562 of unnecessary cgraph_nodes, which can cause some of the
4563 other IPA passes to crash.
4564
4565 We do need to mark these nodes so that we get the proper
4566 result in expand_call_tm. */
4567 /* ??? This seems broken. How is it that we're marking the
4568 CALLEE as may_enter_irr? Surely we should be marking the
4569 CALLER. Also note that find_tm_replacement_function also
4570 contains mappings into the TM runtime, e.g. memcpy. These
4571 we know won't go irrevocable. */
4572 new_node->local.tm_may_enter_irr = 1;
4573 }
4574 else
4575 {
4576 struct tm_ipa_cg_data *d;
4577 struct cgraph_node *tnode = e->callee;
4578
4579 d = get_cg_data (&tnode, true);
4580 new_node = d->clone;
4581
4582 /* As we've already skipped pure calls and appropriate builtins,
4583 and we've already marked irrevocable blocks, if we can't come
4584 up with a static replacement, then ask the runtime. */
4585 if (new_node == NULL)
4586 {
4587 *need_ssa_rename_p |=
4588 ipa_tm_insert_gettmclone_call (node, region, gsi, stmt);
4589 return;
4590 }
4591
4592 fndecl = new_node->decl;
4593 }
4594
4595 cgraph_redirect_edge_callee (e, new_node);
4596 gimple_call_set_fndecl (stmt, fndecl);
4597 }
4598
4599 /* Helper function for ipa_tm_transform_calls. For a given BB,
4600 install calls to tm_irrevocable when IRR_BLOCKS are reached,
4601 redirect other calls to the generated transactional clone. */
4602
4603 static bool
ipa_tm_transform_calls_1(struct cgraph_node * node,struct tm_region * region,basic_block bb,bitmap irr_blocks)4604 ipa_tm_transform_calls_1 (struct cgraph_node *node, struct tm_region *region,
4605 basic_block bb, bitmap irr_blocks)
4606 {
4607 gimple_stmt_iterator gsi;
4608 bool need_ssa_rename = false;
4609
4610 if (irr_blocks && bitmap_bit_p (irr_blocks, bb->index))
4611 {
4612 ipa_tm_insert_irr_call (node, region, bb);
4613 return true;
4614 }
4615
4616 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4617 {
4618 gimple stmt = gsi_stmt (gsi);
4619
4620 if (!is_gimple_call (stmt))
4621 continue;
4622 if (is_tm_pure_call (stmt))
4623 continue;
4624
4625 /* Redirect edges to the appropriate replacement or clone. */
4626 ipa_tm_transform_calls_redirect (node, region, &gsi, &need_ssa_rename);
4627 }
4628
4629 return need_ssa_rename;
4630 }
4631
4632 /* Walk the CFG for REGION, beginning at BB. Install calls to
4633 tm_irrevocable when IRR_BLOCKS are reached, redirect other calls to
4634 the generated transactional clone. */
4635
4636 static bool
ipa_tm_transform_calls(struct cgraph_node * node,struct tm_region * region,basic_block bb,bitmap irr_blocks)4637 ipa_tm_transform_calls (struct cgraph_node *node, struct tm_region *region,
4638 basic_block bb, bitmap irr_blocks)
4639 {
4640 bool need_ssa_rename = false;
4641 edge e;
4642 edge_iterator ei;
4643 VEC(basic_block, heap) *queue = NULL;
4644 bitmap visited_blocks = BITMAP_ALLOC (NULL);
4645
4646 VEC_safe_push (basic_block, heap, queue, bb);
4647 do
4648 {
4649 bb = VEC_pop (basic_block, queue);
4650
4651 need_ssa_rename |=
4652 ipa_tm_transform_calls_1 (node, region, bb, irr_blocks);
4653
4654 if (irr_blocks && bitmap_bit_p (irr_blocks, bb->index))
4655 continue;
4656
4657 if (region && bitmap_bit_p (region->exit_blocks, bb->index))
4658 continue;
4659
4660 FOR_EACH_EDGE (e, ei, bb->succs)
4661 if (!bitmap_bit_p (visited_blocks, e->dest->index))
4662 {
4663 bitmap_set_bit (visited_blocks, e->dest->index);
4664 VEC_safe_push (basic_block, heap, queue, e->dest);
4665 }
4666 }
4667 while (!VEC_empty (basic_block, queue));
4668
4669 VEC_free (basic_block, heap, queue);
4670 BITMAP_FREE (visited_blocks);
4671
4672 return need_ssa_rename;
4673 }
4674
4675 /* Transform the calls within the TM regions within NODE. */
4676
4677 static void
ipa_tm_transform_transaction(struct cgraph_node * node)4678 ipa_tm_transform_transaction (struct cgraph_node *node)
4679 {
4680 struct tm_ipa_cg_data *d;
4681 struct tm_region *region;
4682 bool need_ssa_rename = false;
4683
4684 d = get_cg_data (&node, true);
4685
4686 current_function_decl = node->decl;
4687 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
4688 calculate_dominance_info (CDI_DOMINATORS);
4689
4690 for (region = d->all_tm_regions; region; region = region->next)
4691 {
4692 /* If we're sure to go irrevocable, don't transform anything. */
4693 if (d->irrevocable_blocks_normal
4694 && bitmap_bit_p (d->irrevocable_blocks_normal,
4695 region->entry_block->index))
4696 {
4697 transaction_subcode_ior (region, GTMA_DOES_GO_IRREVOCABLE);
4698 transaction_subcode_ior (region, GTMA_MAY_ENTER_IRREVOCABLE);
4699 continue;
4700 }
4701
4702 need_ssa_rename |=
4703 ipa_tm_transform_calls (node, region, region->entry_block,
4704 d->irrevocable_blocks_normal);
4705 }
4706
4707 if (need_ssa_rename)
4708 update_ssa (TODO_update_ssa_only_virtuals);
4709
4710 pop_cfun ();
4711 current_function_decl = NULL;
4712 }
4713
4714 /* Transform the calls within the transactional clone of NODE. */
4715
4716 static void
ipa_tm_transform_clone(struct cgraph_node * node)4717 ipa_tm_transform_clone (struct cgraph_node *node)
4718 {
4719 struct tm_ipa_cg_data *d;
4720 bool need_ssa_rename;
4721
4722 d = get_cg_data (&node, true);
4723
4724 /* If this function makes no calls and has no irrevocable blocks,
4725 then there's nothing to do. */
4726 /* ??? Remove non-aborting top-level transactions. */
4727 if (!node->callees && !node->indirect_calls && !d->irrevocable_blocks_clone)
4728 return;
4729
4730 current_function_decl = d->clone->decl;
4731 push_cfun (DECL_STRUCT_FUNCTION (current_function_decl));
4732 calculate_dominance_info (CDI_DOMINATORS);
4733
4734 need_ssa_rename =
4735 ipa_tm_transform_calls (d->clone, NULL, single_succ (ENTRY_BLOCK_PTR),
4736 d->irrevocable_blocks_clone);
4737
4738 if (need_ssa_rename)
4739 update_ssa (TODO_update_ssa_only_virtuals);
4740
4741 pop_cfun ();
4742 current_function_decl = NULL;
4743 }
4744
4745 /* Main entry point for the transactional memory IPA pass. */
4746
4747 static unsigned int
ipa_tm_execute(void)4748 ipa_tm_execute (void)
4749 {
4750 cgraph_node_queue tm_callees = NULL;
4751 /* List of functions that will go irrevocable. */
4752 cgraph_node_queue irr_worklist = NULL;
4753
4754 struct cgraph_node *node;
4755 struct tm_ipa_cg_data *d;
4756 enum availability a;
4757 unsigned int i;
4758
4759 #ifdef ENABLE_CHECKING
4760 verify_cgraph ();
4761 #endif
4762
4763 bitmap_obstack_initialize (&tm_obstack);
4764
4765 /* For all local functions marked tm_callable, queue them. */
4766 for (node = cgraph_nodes; node; node = node->next)
4767 if (is_tm_callable (node->decl)
4768 && cgraph_function_body_availability (node) >= AVAIL_OVERWRITABLE)
4769 {
4770 d = get_cg_data (&node, true);
4771 maybe_push_queue (node, &tm_callees, &d->in_callee_queue);
4772 }
4773
4774 /* For all local reachable functions... */
4775 for (node = cgraph_nodes; node; node = node->next)
4776 if (node->reachable && node->lowered
4777 && cgraph_function_body_availability (node) >= AVAIL_OVERWRITABLE)
4778 {
4779 /* ... marked tm_pure, record that fact for the runtime by
4780 indicating that the pure function is its own tm_callable.
4781 No need to do this if the function's address can't be taken. */
4782 if (is_tm_pure (node->decl))
4783 {
4784 if (!node->local.local)
4785 record_tm_clone_pair (node->decl, node->decl);
4786 continue;
4787 }
4788
4789 current_function_decl = node->decl;
4790 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
4791 calculate_dominance_info (CDI_DOMINATORS);
4792
4793 tm_region_init (NULL);
4794 if (all_tm_regions)
4795 {
4796 d = get_cg_data (&node, true);
4797
4798 /* Scan for calls that are in each transaction. */
4799 ipa_tm_scan_calls_transaction (d, &tm_callees);
4800
4801 /* Put it in the worklist so we can scan the function
4802 later (ipa_tm_scan_irr_function) and mark the
4803 irrevocable blocks. */
4804 maybe_push_queue (node, &irr_worklist, &d->in_worklist);
4805 d->want_irr_scan_normal = true;
4806 }
4807
4808 pop_cfun ();
4809 current_function_decl = NULL;
4810 }
4811
4812 /* For every local function on the callee list, scan as if we will be
4813 creating a transactional clone, queueing all new functions we find
4814 along the way. */
4815 for (i = 0; i < VEC_length (cgraph_node_p, tm_callees); ++i)
4816 {
4817 node = VEC_index (cgraph_node_p, tm_callees, i);
4818 a = cgraph_function_body_availability (node);
4819 d = get_cg_data (&node, true);
4820
4821 /* Put it in the worklist so we can scan the function later
4822 (ipa_tm_scan_irr_function) and mark the irrevocable
4823 blocks. */
4824 maybe_push_queue (node, &irr_worklist, &d->in_worklist);
4825
4826 /* Some callees cannot be arbitrarily cloned. These will always be
4827 irrevocable. Mark these now, so that we need not scan them. */
4828 if (is_tm_irrevocable (node->decl))
4829 ipa_tm_note_irrevocable (node, &irr_worklist);
4830 else if (a <= AVAIL_NOT_AVAILABLE
4831 && !is_tm_safe_or_pure (node->decl))
4832 ipa_tm_note_irrevocable (node, &irr_worklist);
4833 else if (a >= AVAIL_OVERWRITABLE)
4834 {
4835 if (!tree_versionable_function_p (node->decl))
4836 ipa_tm_note_irrevocable (node, &irr_worklist);
4837 else if (!d->is_irrevocable)
4838 {
4839 /* If this is an alias, make sure its base is queued as well.
4840 we need not scan the callees now, as the base will do. */
4841 if (node->alias)
4842 {
4843 node = cgraph_get_node (node->thunk.alias);
4844 d = get_cg_data (&node, true);
4845 maybe_push_queue (node, &tm_callees, &d->in_callee_queue);
4846 continue;
4847 }
4848
4849 /* Add all nodes called by this function into
4850 tm_callees as well. */
4851 ipa_tm_scan_calls_clone (node, &tm_callees);
4852 }
4853 }
4854 }
4855
4856 /* Iterate scans until no more work to be done. Prefer not to use
4857 VEC_pop because the worklist tends to follow a breadth-first
4858 search of the callgraph, which should allow convergance with a
4859 minimum number of scans. But we also don't want the worklist
4860 array to grow without bound, so we shift the array up periodically. */
4861 for (i = 0; i < VEC_length (cgraph_node_p, irr_worklist); ++i)
4862 {
4863 if (i > 256 && i == VEC_length (cgraph_node_p, irr_worklist) / 8)
4864 {
4865 VEC_block_remove (cgraph_node_p, irr_worklist, 0, i);
4866 i = 0;
4867 }
4868
4869 node = VEC_index (cgraph_node_p, irr_worklist, i);
4870 d = get_cg_data (&node, true);
4871 d->in_worklist = false;
4872
4873 if (d->want_irr_scan_normal)
4874 {
4875 d->want_irr_scan_normal = false;
4876 ipa_tm_scan_irr_function (node, false);
4877 }
4878 if (d->in_callee_queue && ipa_tm_scan_irr_function (node, true))
4879 ipa_tm_note_irrevocable (node, &irr_worklist);
4880 }
4881
4882 /* For every function on the callee list, collect the tm_may_enter_irr
4883 bit on the node. */
4884 VEC_truncate (cgraph_node_p, irr_worklist, 0);
4885 for (i = 0; i < VEC_length (cgraph_node_p, tm_callees); ++i)
4886 {
4887 node = VEC_index (cgraph_node_p, tm_callees, i);
4888 if (ipa_tm_mayenterirr_function (node))
4889 {
4890 d = get_cg_data (&node, true);
4891 gcc_assert (d->in_worklist == false);
4892 maybe_push_queue (node, &irr_worklist, &d->in_worklist);
4893 }
4894 }
4895
4896 /* Propagate the tm_may_enter_irr bit to callers until stable. */
4897 for (i = 0; i < VEC_length (cgraph_node_p, irr_worklist); ++i)
4898 {
4899 struct cgraph_node *caller;
4900 struct cgraph_edge *e;
4901 struct ipa_ref *ref;
4902 unsigned j;
4903
4904 if (i > 256 && i == VEC_length (cgraph_node_p, irr_worklist) / 8)
4905 {
4906 VEC_block_remove (cgraph_node_p, irr_worklist, 0, i);
4907 i = 0;
4908 }
4909
4910 node = VEC_index (cgraph_node_p, irr_worklist, i);
4911 d = get_cg_data (&node, true);
4912 d->in_worklist = false;
4913 node->local.tm_may_enter_irr = true;
4914
4915 /* Propagate back to normal callers. */
4916 for (e = node->callers; e ; e = e->next_caller)
4917 {
4918 caller = e->caller;
4919 if (!is_tm_safe_or_pure (caller->decl)
4920 && !caller->local.tm_may_enter_irr)
4921 {
4922 d = get_cg_data (&caller, true);
4923 maybe_push_queue (caller, &irr_worklist, &d->in_worklist);
4924 }
4925 }
4926
4927 /* Propagate back to referring aliases as well. */
4928 for (j = 0; ipa_ref_list_refering_iterate (&node->ref_list, j, ref); j++)
4929 {
4930 caller = ref->refering.cgraph_node;
4931 if (ref->use == IPA_REF_ALIAS
4932 && !caller->local.tm_may_enter_irr)
4933 {
4934 /* ?? Do not traverse aliases here. */
4935 d = get_cg_data (&caller, false);
4936 maybe_push_queue (caller, &irr_worklist, &d->in_worklist);
4937 }
4938 }
4939 }
4940
4941 /* Now validate all tm_safe functions, and all atomic regions in
4942 other functions. */
4943 for (node = cgraph_nodes; node; node = node->next)
4944 if (node->reachable && node->lowered
4945 && cgraph_function_body_availability (node) >= AVAIL_OVERWRITABLE)
4946 {
4947 d = get_cg_data (&node, true);
4948 if (is_tm_safe (node->decl))
4949 ipa_tm_diagnose_tm_safe (node);
4950 else if (d->all_tm_regions)
4951 ipa_tm_diagnose_transaction (node, d->all_tm_regions);
4952 }
4953
4954 /* Create clones. Do those that are not irrevocable and have a
4955 positive call count. Do those publicly visible functions that
4956 the user directed us to clone. */
4957 for (i = 0; i < VEC_length (cgraph_node_p, tm_callees); ++i)
4958 {
4959 bool doit = false;
4960
4961 node = VEC_index (cgraph_node_p, tm_callees, i);
4962 if (node->same_body_alias)
4963 continue;
4964
4965 a = cgraph_function_body_availability (node);
4966 d = get_cg_data (&node, true);
4967
4968 if (a <= AVAIL_NOT_AVAILABLE)
4969 doit = is_tm_callable (node->decl);
4970 else if (a <= AVAIL_AVAILABLE && is_tm_callable (node->decl))
4971 doit = true;
4972 else if (!d->is_irrevocable
4973 && d->tm_callers_normal + d->tm_callers_clone > 0)
4974 doit = true;
4975
4976 if (doit)
4977 ipa_tm_create_version (node);
4978 }
4979
4980 /* Redirect calls to the new clones, and insert irrevocable marks. */
4981 for (i = 0; i < VEC_length (cgraph_node_p, tm_callees); ++i)
4982 {
4983 node = VEC_index (cgraph_node_p, tm_callees, i);
4984 if (node->analyzed)
4985 {
4986 d = get_cg_data (&node, true);
4987 if (d->clone)
4988 ipa_tm_transform_clone (node);
4989 }
4990 }
4991 for (node = cgraph_nodes; node; node = node->next)
4992 if (node->reachable && node->lowered
4993 && cgraph_function_body_availability (node) >= AVAIL_OVERWRITABLE)
4994 {
4995 d = get_cg_data (&node, true);
4996 if (d->all_tm_regions)
4997 ipa_tm_transform_transaction (node);
4998 }
4999
5000 /* Free and clear all data structures. */
5001 VEC_free (cgraph_node_p, heap, tm_callees);
5002 VEC_free (cgraph_node_p, heap, irr_worklist);
5003 bitmap_obstack_release (&tm_obstack);
5004
5005 for (node = cgraph_nodes; node; node = node->next)
5006 node->aux = NULL;
5007
5008 #ifdef ENABLE_CHECKING
5009 verify_cgraph ();
5010 #endif
5011
5012 return 0;
5013 }
5014
5015 struct simple_ipa_opt_pass pass_ipa_tm =
5016 {
5017 {
5018 SIMPLE_IPA_PASS,
5019 "tmipa", /* name */
5020 gate_tm, /* gate */
5021 ipa_tm_execute, /* execute */
5022 NULL, /* sub */
5023 NULL, /* next */
5024 0, /* static_pass_number */
5025 TV_TRANS_MEM, /* tv_id */
5026 PROP_ssa | PROP_cfg, /* properties_required */
5027 0, /* properties_provided */
5028 0, /* properties_destroyed */
5029 0, /* todo_flags_start */
5030 TODO_dump_func, /* todo_flags_finish */
5031 },
5032 };
5033
5034 #include "gt-trans-mem.h"
5035