Merge branch 'vendor/GCC44'
[dragonfly.git] / contrib / gcc-4.4 / gcc / omp-low.c
1 /* Lowering pass for OpenMP directives.  Converts OpenMP directives
2    into explicit calls to the runtime library (libgomp) and data
3    marshalling to implement data sharing and copying clauses.
4    Contributed by Diego Novillo <dnovillo@redhat.com>
5
6    Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
7
8 This file is part of GCC.
9
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
13 version.
14
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
18 for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3.  If not see
22 <http://www.gnu.org/licenses/>.  */
23
24 #include "config.h"
25 #include "system.h"
26 #include "coretypes.h"
27 #include "tm.h"
28 #include "tree.h"
29 #include "rtl.h"
30 #include "gimple.h"
31 #include "tree-iterator.h"
32 #include "tree-inline.h"
33 #include "langhooks.h"
34 #include "diagnostic.h"
35 #include "tree-flow.h"
36 #include "timevar.h"
37 #include "flags.h"
38 #include "function.h"
39 #include "expr.h"
40 #include "toplev.h"
41 #include "tree-pass.h"
42 #include "ggc.h"
43 #include "except.h"
44 #include "splay-tree.h"
45 #include "optabs.h"
46 #include "cfgloop.h"
47
48
49 /* Lowering of OpenMP parallel and workshare constructs proceeds in two 
50    phases.  The first phase scans the function looking for OMP statements
51    and then for variables that must be replaced to satisfy data sharing
52    clauses.  The second phase expands code for the constructs, as well as
53    re-gimplifying things when variables have been replaced with complex
54    expressions.
55
56    Final code generation is done by pass_expand_omp.  The flowgraph is
57    scanned for parallel regions which are then moved to a new
58    function, to be invoked by the thread library.  */
59
60 /* Context structure.  Used to store information about each parallel
61    directive in the code.  */
62
63 typedef struct omp_context
64 {
65   /* This field must be at the beginning, as we do "inheritance": Some
66      callback functions for tree-inline.c (e.g., omp_copy_decl)
67      receive a copy_body_data pointer that is up-casted to an
68      omp_context pointer.  */
69   copy_body_data cb;
70
71   /* The tree of contexts corresponding to the encountered constructs.  */
72   struct omp_context *outer;
73   gimple stmt;
74
75   /* Map variables to fields in a structure that allows communication 
76      between sending and receiving threads.  */
77   splay_tree field_map;
78   tree record_type;
79   tree sender_decl;
80   tree receiver_decl;
81
82   /* These are used just by task contexts, if task firstprivate fn is
83      needed.  srecord_type is used to communicate from the thread
84      that encountered the task construct to task firstprivate fn,
85      record_type is allocated by GOMP_task, initialized by task firstprivate
86      fn and passed to the task body fn.  */
87   splay_tree sfield_map;
88   tree srecord_type;
89
90   /* A chain of variables to add to the top-level block surrounding the
91      construct.  In the case of a parallel, this is in the child function.  */
92   tree block_vars;
93
94   /* What to do with variables with implicitly determined sharing
95      attributes.  */
96   enum omp_clause_default_kind default_kind;
97
98   /* Nesting depth of this context.  Used to beautify error messages re
99      invalid gotos.  The outermost ctx is depth 1, with depth 0 being
100      reserved for the main body of the function.  */
101   int depth;
102
103   /* True if this parallel directive is nested within another.  */
104   bool is_nested;
105 } omp_context;
106
107
108 struct omp_for_data_loop
109 {
110   tree v, n1, n2, step;
111   enum tree_code cond_code;
112 };
113
114 /* A structure describing the main elements of a parallel loop.  */
115
116 struct omp_for_data
117 {
118   struct omp_for_data_loop loop;
119   tree chunk_size;
120   gimple for_stmt;
121   tree pre, iter_type;
122   int collapse;
123   bool have_nowait, have_ordered;
124   enum omp_clause_schedule_kind sched_kind;
125   struct omp_for_data_loop *loops;
126 };
127
128
129 static splay_tree all_contexts;
130 static int taskreg_nesting_level;
131 struct omp_region *root_omp_region;
132 static bitmap task_shared_vars;
133
134 static void scan_omp (gimple_seq, omp_context *);
135 static tree scan_omp_1_op (tree *, int *, void *);
136
137 #define WALK_SUBSTMTS  \
138     case GIMPLE_BIND: \
139     case GIMPLE_TRY: \
140     case GIMPLE_CATCH: \
141     case GIMPLE_EH_FILTER: \
142       /* The sub-statements for these should be walked.  */ \
143       *handled_ops_p = false; \
144       break;
145
146 /* Convenience function for calling scan_omp_1_op on tree operands.  */
147
148 static inline tree
149 scan_omp_op (tree *tp, omp_context *ctx)
150 {
151   struct walk_stmt_info wi;
152
153   memset (&wi, 0, sizeof (wi));
154   wi.info = ctx;
155   wi.want_locations = true;
156
157   return walk_tree (tp, scan_omp_1_op, &wi, NULL);
158 }
159
160 static void lower_omp (gimple_seq, omp_context *);
161 static tree lookup_decl_in_outer_ctx (tree, omp_context *);
162 static tree maybe_lookup_decl_in_outer_ctx (tree, omp_context *);
163
164 /* Find an OpenMP clause of type KIND within CLAUSES.  */
165
166 tree
167 find_omp_clause (tree clauses, enum omp_clause_code kind)
168 {
169   for (; clauses ; clauses = OMP_CLAUSE_CHAIN (clauses))
170     if (OMP_CLAUSE_CODE (clauses) == kind)
171       return clauses;
172
173   return NULL_TREE;
174 }
175
176 /* Return true if CTX is for an omp parallel.  */
177
178 static inline bool
179 is_parallel_ctx (omp_context *ctx)
180 {
181   return gimple_code (ctx->stmt) == GIMPLE_OMP_PARALLEL;
182 }
183
184
185 /* Return true if CTX is for an omp task.  */
186
187 static inline bool
188 is_task_ctx (omp_context *ctx)
189 {
190   return gimple_code (ctx->stmt) == GIMPLE_OMP_TASK;
191 }
192
193
194 /* Return true if CTX is for an omp parallel or omp task.  */
195
196 static inline bool
197 is_taskreg_ctx (omp_context *ctx)
198 {
199   return gimple_code (ctx->stmt) == GIMPLE_OMP_PARALLEL
200          || gimple_code (ctx->stmt) == GIMPLE_OMP_TASK;
201 }
202
203
204 /* Return true if REGION is a combined parallel+workshare region.  */
205
206 static inline bool
207 is_combined_parallel (struct omp_region *region)
208 {
209   return region->is_combined_parallel;
210 }
211
212
213 /* Extract the header elements of parallel loop FOR_STMT and store
214    them into *FD.  */
215
216 static void
217 extract_omp_for_data (gimple for_stmt, struct omp_for_data *fd,
218                       struct omp_for_data_loop *loops)
219 {
220   tree t, var, *collapse_iter, *collapse_count;
221   tree count = NULL_TREE, iter_type = long_integer_type_node;
222   struct omp_for_data_loop *loop;
223   int i;
224   struct omp_for_data_loop dummy_loop;
225
226   fd->for_stmt = for_stmt;
227   fd->pre = NULL;
228   fd->collapse = gimple_omp_for_collapse (for_stmt);
229   if (fd->collapse > 1)
230     fd->loops = loops;
231   else
232     fd->loops = &fd->loop;
233
234   fd->have_nowait = fd->have_ordered = false;
235   fd->sched_kind = OMP_CLAUSE_SCHEDULE_STATIC;
236   fd->chunk_size = NULL_TREE;
237   collapse_iter = NULL;
238   collapse_count = NULL;
239
240   for (t = gimple_omp_for_clauses (for_stmt); t ; t = OMP_CLAUSE_CHAIN (t))
241     switch (OMP_CLAUSE_CODE (t))
242       {
243       case OMP_CLAUSE_NOWAIT:
244         fd->have_nowait = true;
245         break;
246       case OMP_CLAUSE_ORDERED:
247         fd->have_ordered = true;
248         break;
249       case OMP_CLAUSE_SCHEDULE:
250         fd->sched_kind = OMP_CLAUSE_SCHEDULE_KIND (t);
251         fd->chunk_size = OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (t);
252         break;
253       case OMP_CLAUSE_COLLAPSE:
254         if (fd->collapse > 1)
255           {
256             collapse_iter = &OMP_CLAUSE_COLLAPSE_ITERVAR (t);
257             collapse_count = &OMP_CLAUSE_COLLAPSE_COUNT (t);
258           }
259       default:
260         break;
261       }
262
263   /* FIXME: for now map schedule(auto) to schedule(static).
264      There should be analysis to determine whether all iterations
265      are approximately the same amount of work (then schedule(static)
266      is best) or if it varies (then schedule(dynamic,N) is better).  */
267   if (fd->sched_kind == OMP_CLAUSE_SCHEDULE_AUTO)
268     {
269       fd->sched_kind = OMP_CLAUSE_SCHEDULE_STATIC;
270       gcc_assert (fd->chunk_size == NULL);
271     }
272   gcc_assert (fd->collapse == 1 || collapse_iter != NULL);
273   if (fd->sched_kind == OMP_CLAUSE_SCHEDULE_RUNTIME)
274     gcc_assert (fd->chunk_size == NULL);
275   else if (fd->chunk_size == NULL)
276     {
277       /* We only need to compute a default chunk size for ordered
278          static loops and dynamic loops.  */
279       if (fd->sched_kind != OMP_CLAUSE_SCHEDULE_STATIC
280           || fd->have_ordered
281           || fd->collapse > 1)
282         fd->chunk_size = (fd->sched_kind == OMP_CLAUSE_SCHEDULE_STATIC)
283                          ? integer_zero_node : integer_one_node;
284     }
285
286   for (i = 0; i < fd->collapse; i++)
287     {
288       if (fd->collapse == 1)
289         loop = &fd->loop;
290       else if (loops != NULL)
291         loop = loops + i;
292       else
293         loop = &dummy_loop;
294
295       
296       loop->v = gimple_omp_for_index (for_stmt, i);
297       gcc_assert (SSA_VAR_P (loop->v));
298       gcc_assert (TREE_CODE (TREE_TYPE (loop->v)) == INTEGER_TYPE
299                   || TREE_CODE (TREE_TYPE (loop->v)) == POINTER_TYPE);
300       var = TREE_CODE (loop->v) == SSA_NAME ? SSA_NAME_VAR (loop->v) : loop->v;
301       loop->n1 = gimple_omp_for_initial (for_stmt, i);
302
303       loop->cond_code = gimple_omp_for_cond (for_stmt, i);
304       loop->n2 = gimple_omp_for_final (for_stmt, i);
305       switch (loop->cond_code)
306         {
307         case LT_EXPR:
308         case GT_EXPR:
309           break;
310         case LE_EXPR:
311           if (POINTER_TYPE_P (TREE_TYPE (loop->n2)))
312             loop->n2 = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (loop->n2),
313                                     loop->n2, size_one_node);
314           else
315             loop->n2 = fold_build2 (PLUS_EXPR, TREE_TYPE (loop->n2), loop->n2,
316                                     build_int_cst (TREE_TYPE (loop->n2), 1));
317           loop->cond_code = LT_EXPR;
318           break;
319         case GE_EXPR:
320           if (POINTER_TYPE_P (TREE_TYPE (loop->n2)))
321             loop->n2 = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (loop->n2),
322                                     loop->n2, size_int (-1));
323           else
324             loop->n2 = fold_build2 (MINUS_EXPR, TREE_TYPE (loop->n2), loop->n2,
325                                     build_int_cst (TREE_TYPE (loop->n2), 1));
326           loop->cond_code = GT_EXPR;
327           break;
328         default:
329           gcc_unreachable ();
330         }
331
332       t = gimple_omp_for_incr (for_stmt, i);
333       gcc_assert (TREE_OPERAND (t, 0) == var);
334       switch (TREE_CODE (t))
335         {
336         case PLUS_EXPR:
337         case POINTER_PLUS_EXPR:
338           loop->step = TREE_OPERAND (t, 1);
339           break;
340         case MINUS_EXPR:
341           loop->step = TREE_OPERAND (t, 1);
342           loop->step = fold_build1 (NEGATE_EXPR, TREE_TYPE (loop->step),
343                                     loop->step);
344           break;
345         default:
346           gcc_unreachable ();
347         }
348
349       if (iter_type != long_long_unsigned_type_node)
350         {
351           if (POINTER_TYPE_P (TREE_TYPE (loop->v)))
352             iter_type = long_long_unsigned_type_node;
353           else if (TYPE_UNSIGNED (TREE_TYPE (loop->v))
354                    && TYPE_PRECISION (TREE_TYPE (loop->v))
355                       >= TYPE_PRECISION (iter_type))
356             {
357               tree n;
358
359               if (loop->cond_code == LT_EXPR)
360                 n = fold_build2 (PLUS_EXPR, TREE_TYPE (loop->v),
361                                  loop->n2, loop->step);
362               else
363                 n = loop->n1;
364               if (TREE_CODE (n) != INTEGER_CST
365                   || tree_int_cst_lt (TYPE_MAX_VALUE (iter_type), n))
366                 iter_type = long_long_unsigned_type_node;
367             }
368           else if (TYPE_PRECISION (TREE_TYPE (loop->v))
369                    > TYPE_PRECISION (iter_type))
370             {
371               tree n1, n2;
372
373               if (loop->cond_code == LT_EXPR)
374                 {
375                   n1 = loop->n1;
376                   n2 = fold_build2 (PLUS_EXPR, TREE_TYPE (loop->v),
377                                     loop->n2, loop->step);
378                 }
379               else
380                 {
381                   n1 = fold_build2 (MINUS_EXPR, TREE_TYPE (loop->v),
382                                     loop->n2, loop->step);
383                   n2 = loop->n1;
384                 }
385               if (TREE_CODE (n1) != INTEGER_CST
386                   || TREE_CODE (n2) != INTEGER_CST
387                   || !tree_int_cst_lt (TYPE_MIN_VALUE (iter_type), n1)
388                   || !tree_int_cst_lt (n2, TYPE_MAX_VALUE (iter_type)))
389                 iter_type = long_long_unsigned_type_node;
390             }
391         }
392
393       if (collapse_count && *collapse_count == NULL)
394         {
395           if ((i == 0 || count != NULL_TREE)
396               && TREE_CODE (TREE_TYPE (loop->v)) == INTEGER_TYPE
397               && TREE_CONSTANT (loop->n1)
398               && TREE_CONSTANT (loop->n2)
399               && TREE_CODE (loop->step) == INTEGER_CST)
400             {
401               tree itype = TREE_TYPE (loop->v);
402
403               if (POINTER_TYPE_P (itype))
404                 itype
405                   = lang_hooks.types.type_for_size (TYPE_PRECISION (itype), 0);
406               t = build_int_cst (itype, (loop->cond_code == LT_EXPR ? -1 : 1));
407               t = fold_build2 (PLUS_EXPR, itype,
408                                fold_convert (itype, loop->step), t);
409               t = fold_build2 (PLUS_EXPR, itype, t,
410                                fold_convert (itype, loop->n2));
411               t = fold_build2 (MINUS_EXPR, itype, t,
412                                fold_convert (itype, loop->n1));
413               if (TYPE_UNSIGNED (itype) && loop->cond_code == GT_EXPR)
414                 t = fold_build2 (TRUNC_DIV_EXPR, itype,
415                                  fold_build1 (NEGATE_EXPR, itype, t),
416                                  fold_build1 (NEGATE_EXPR, itype,
417                                               fold_convert (itype,
418                                                             loop->step)));
419               else
420                 t = fold_build2 (TRUNC_DIV_EXPR, itype, t,
421                                  fold_convert (itype, loop->step));
422               t = fold_convert (long_long_unsigned_type_node, t);
423               if (count != NULL_TREE)
424                 count = fold_build2 (MULT_EXPR, long_long_unsigned_type_node,
425                                      count, t);
426               else
427                 count = t;
428               if (TREE_CODE (count) != INTEGER_CST)
429                 count = NULL_TREE;
430             }
431           else
432             count = NULL_TREE;
433         }
434     }
435
436   if (count)
437     {
438       if (!tree_int_cst_lt (count, TYPE_MAX_VALUE (long_integer_type_node)))
439         iter_type = long_long_unsigned_type_node;
440       else
441         iter_type = long_integer_type_node;
442     }
443   else if (collapse_iter && *collapse_iter != NULL)
444     iter_type = TREE_TYPE (*collapse_iter);
445   fd->iter_type = iter_type;
446   if (collapse_iter && *collapse_iter == NULL)
447     *collapse_iter = create_tmp_var (iter_type, ".iter");
448   if (collapse_count && *collapse_count == NULL)
449     {
450       if (count)
451         *collapse_count = fold_convert (iter_type, count);
452       else
453         *collapse_count = create_tmp_var (iter_type, ".count");
454     }
455
456   if (fd->collapse > 1)
457     {
458       fd->loop.v = *collapse_iter;
459       fd->loop.n1 = build_int_cst (TREE_TYPE (fd->loop.v), 0);
460       fd->loop.n2 = *collapse_count;
461       fd->loop.step = build_int_cst (TREE_TYPE (fd->loop.v), 1);
462       fd->loop.cond_code = LT_EXPR;
463     }
464 }
465
466
467 /* Given two blocks PAR_ENTRY_BB and WS_ENTRY_BB such that WS_ENTRY_BB
468    is the immediate dominator of PAR_ENTRY_BB, return true if there
469    are no data dependencies that would prevent expanding the parallel
470    directive at PAR_ENTRY_BB as a combined parallel+workshare region.
471
472    When expanding a combined parallel+workshare region, the call to
473    the child function may need additional arguments in the case of
474    GIMPLE_OMP_FOR regions.  In some cases, these arguments are
475    computed out of variables passed in from the parent to the child
476    via 'struct .omp_data_s'.  For instance:
477
478         #pragma omp parallel for schedule (guided, i * 4)
479         for (j ...)
480
481    Is lowered into:
482
483         # BLOCK 2 (PAR_ENTRY_BB)
484         .omp_data_o.i = i;
485         #pragma omp parallel [child fn: bar.omp_fn.0 ( ..., D.1598)
486         
487         # BLOCK 3 (WS_ENTRY_BB)
488         .omp_data_i = &.omp_data_o;
489         D.1667 = .omp_data_i->i;
490         D.1598 = D.1667 * 4;
491         #pragma omp for schedule (guided, D.1598)
492
493    When we outline the parallel region, the call to the child function
494    'bar.omp_fn.0' will need the value D.1598 in its argument list, but
495    that value is computed *after* the call site.  So, in principle we
496    cannot do the transformation.
497
498    To see whether the code in WS_ENTRY_BB blocks the combined
499    parallel+workshare call, we collect all the variables used in the
500    GIMPLE_OMP_FOR header check whether they appear on the LHS of any
501    statement in WS_ENTRY_BB.  If so, then we cannot emit the combined
502    call.
503
504    FIXME.  If we had the SSA form built at this point, we could merely
505    hoist the code in block 3 into block 2 and be done with it.  But at
506    this point we don't have dataflow information and though we could
507    hack something up here, it is really not worth the aggravation.  */
508
509 static bool
510 workshare_safe_to_combine_p (basic_block par_entry_bb, basic_block ws_entry_bb)
511 {
512   struct omp_for_data fd;
513   gimple par_stmt, ws_stmt;
514
515   par_stmt = last_stmt (par_entry_bb);
516   ws_stmt = last_stmt (ws_entry_bb);
517
518   if (gimple_code (ws_stmt) == GIMPLE_OMP_SECTIONS)
519     return true;
520
521   gcc_assert (gimple_code (ws_stmt) == GIMPLE_OMP_FOR);
522
523   extract_omp_for_data (ws_stmt, &fd, NULL);
524
525   if (fd.collapse > 1 && TREE_CODE (fd.loop.n2) != INTEGER_CST)
526     return false;
527   if (fd.iter_type != long_integer_type_node)
528     return false;
529
530   /* FIXME.  We give up too easily here.  If any of these arguments
531      are not constants, they will likely involve variables that have
532      been mapped into fields of .omp_data_s for sharing with the child
533      function.  With appropriate data flow, it would be possible to
534      see through this.  */
535   if (!is_gimple_min_invariant (fd.loop.n1)
536       || !is_gimple_min_invariant (fd.loop.n2)
537       || !is_gimple_min_invariant (fd.loop.step)
538       || (fd.chunk_size && !is_gimple_min_invariant (fd.chunk_size)))
539     return false;
540
541   return true;
542 }
543
544
545 /* Collect additional arguments needed to emit a combined
546    parallel+workshare call.  WS_STMT is the workshare directive being
547    expanded.  */
548
549 static tree
550 get_ws_args_for (gimple ws_stmt)
551 {
552   tree t;
553
554   if (gimple_code (ws_stmt) == GIMPLE_OMP_FOR)
555     {
556       struct omp_for_data fd;
557       tree ws_args;
558
559       extract_omp_for_data (ws_stmt, &fd, NULL);
560
561       ws_args = NULL_TREE;
562       if (fd.chunk_size)
563         {
564           t = fold_convert (long_integer_type_node, fd.chunk_size);
565           ws_args = tree_cons (NULL, t, ws_args);
566         }
567
568       t = fold_convert (long_integer_type_node, fd.loop.step);
569       ws_args = tree_cons (NULL, t, ws_args);
570
571       t = fold_convert (long_integer_type_node, fd.loop.n2);
572       ws_args = tree_cons (NULL, t, ws_args);
573
574       t = fold_convert (long_integer_type_node, fd.loop.n1);
575       ws_args = tree_cons (NULL, t, ws_args);
576
577       return ws_args;
578     }
579   else if (gimple_code (ws_stmt) == GIMPLE_OMP_SECTIONS)
580     {
581       /* Number of sections is equal to the number of edges from the
582          GIMPLE_OMP_SECTIONS_SWITCH statement, except for the one to
583          the exit of the sections region.  */
584       basic_block bb = single_succ (gimple_bb (ws_stmt));
585       t = build_int_cst (unsigned_type_node, EDGE_COUNT (bb->succs) - 1);
586       t = tree_cons (NULL, t, NULL);
587       return t;
588     }
589
590   gcc_unreachable ();
591 }
592
593
594 /* Discover whether REGION is a combined parallel+workshare region.  */
595
596 static void
597 determine_parallel_type (struct omp_region *region)
598 {
599   basic_block par_entry_bb, par_exit_bb;
600   basic_block ws_entry_bb, ws_exit_bb;
601
602   if (region == NULL || region->inner == NULL
603       || region->exit == NULL || region->inner->exit == NULL
604       || region->inner->cont == NULL)
605     return;
606
607   /* We only support parallel+for and parallel+sections.  */
608   if (region->type != GIMPLE_OMP_PARALLEL
609       || (region->inner->type != GIMPLE_OMP_FOR
610           && region->inner->type != GIMPLE_OMP_SECTIONS))
611     return;
612
613   /* Check for perfect nesting PAR_ENTRY_BB -> WS_ENTRY_BB and
614      WS_EXIT_BB -> PAR_EXIT_BB.  */
615   par_entry_bb = region->entry;
616   par_exit_bb = region->exit;
617   ws_entry_bb = region->inner->entry;
618   ws_exit_bb = region->inner->exit;
619
620   if (single_succ (par_entry_bb) == ws_entry_bb
621       && single_succ (ws_exit_bb) == par_exit_bb
622       && workshare_safe_to_combine_p (par_entry_bb, ws_entry_bb)
623       && (gimple_omp_parallel_combined_p (last_stmt (par_entry_bb))
624           || (last_and_only_stmt (ws_entry_bb)
625               && last_and_only_stmt (par_exit_bb))))
626     {
627       gimple ws_stmt = last_stmt (ws_entry_bb);
628
629       if (region->inner->type == GIMPLE_OMP_FOR)
630         {
631           /* If this is a combined parallel loop, we need to determine
632              whether or not to use the combined library calls.  There
633              are two cases where we do not apply the transformation:
634              static loops and any kind of ordered loop.  In the first
635              case, we already open code the loop so there is no need
636              to do anything else.  In the latter case, the combined
637              parallel loop call would still need extra synchronization
638              to implement ordered semantics, so there would not be any
639              gain in using the combined call.  */
640           tree clauses = gimple_omp_for_clauses (ws_stmt);
641           tree c = find_omp_clause (clauses, OMP_CLAUSE_SCHEDULE);
642           if (c == NULL
643               || OMP_CLAUSE_SCHEDULE_KIND (c) == OMP_CLAUSE_SCHEDULE_STATIC
644               || find_omp_clause (clauses, OMP_CLAUSE_ORDERED))
645             {
646               region->is_combined_parallel = false;
647               region->inner->is_combined_parallel = false;
648               return;
649             }
650         }
651
652       region->is_combined_parallel = true;
653       region->inner->is_combined_parallel = true;
654       region->ws_args = get_ws_args_for (ws_stmt);
655     }
656 }
657
658
659 /* Return true if EXPR is variable sized.  */
660
661 static inline bool
662 is_variable_sized (const_tree expr)
663 {
664   return !TREE_CONSTANT (TYPE_SIZE_UNIT (TREE_TYPE (expr)));
665 }
666
667 /* Return true if DECL is a reference type.  */
668
669 static inline bool
670 is_reference (tree decl)
671 {
672   return lang_hooks.decls.omp_privatize_by_reference (decl);
673 }
674
675 /* Lookup variables in the decl or field splay trees.  The "maybe" form
676    allows for the variable form to not have been entered, otherwise we
677    assert that the variable must have been entered.  */
678
679 static inline tree
680 lookup_decl (tree var, omp_context *ctx)
681 {
682   tree *n;
683   n = (tree *) pointer_map_contains (ctx->cb.decl_map, var);
684   return *n;
685 }
686
687 static inline tree
688 maybe_lookup_decl (const_tree var, omp_context *ctx)
689 {
690   tree *n;
691   n = (tree *) pointer_map_contains (ctx->cb.decl_map, var);
692   return n ? *n : NULL_TREE;
693 }
694
695 static inline tree
696 lookup_field (tree var, omp_context *ctx)
697 {
698   splay_tree_node n;
699   n = splay_tree_lookup (ctx->field_map, (splay_tree_key) var);
700   return (tree) n->value;
701 }
702
703 static inline tree
704 lookup_sfield (tree var, omp_context *ctx)
705 {
706   splay_tree_node n;
707   n = splay_tree_lookup (ctx->sfield_map
708                          ? ctx->sfield_map : ctx->field_map,
709                          (splay_tree_key) var);
710   return (tree) n->value;
711 }
712
713 static inline tree
714 maybe_lookup_field (tree var, omp_context *ctx)
715 {
716   splay_tree_node n;
717   n = splay_tree_lookup (ctx->field_map, (splay_tree_key) var);
718   return n ? (tree) n->value : NULL_TREE;
719 }
720
721 /* Return true if DECL should be copied by pointer.  SHARED_CTX is
722    the parallel context if DECL is to be shared.  */
723
724 static bool
725 use_pointer_for_field (tree decl, omp_context *shared_ctx)
726 {
727   if (AGGREGATE_TYPE_P (TREE_TYPE (decl)))
728     return true;
729
730   /* We can only use copy-in/copy-out semantics for shared variables
731      when we know the value is not accessible from an outer scope.  */
732   if (shared_ctx)
733     {
734       /* ??? Trivially accessible from anywhere.  But why would we even
735          be passing an address in this case?  Should we simply assert
736          this to be false, or should we have a cleanup pass that removes
737          these from the list of mappings?  */
738       if (TREE_STATIC (decl) || DECL_EXTERNAL (decl))
739         return true;
740
741       /* For variables with DECL_HAS_VALUE_EXPR_P set, we cannot tell
742          without analyzing the expression whether or not its location
743          is accessible to anyone else.  In the case of nested parallel
744          regions it certainly may be.  */
745       if (TREE_CODE (decl) != RESULT_DECL && DECL_HAS_VALUE_EXPR_P (decl))
746         return true;
747
748       /* Do not use copy-in/copy-out for variables that have their
749          address taken.  */
750       if (TREE_ADDRESSABLE (decl))
751         return true;
752
753       /* Disallow copy-in/out in nested parallel if
754          decl is shared in outer parallel, otherwise
755          each thread could store the shared variable
756          in its own copy-in location, making the
757          variable no longer really shared.  */
758       if (!TREE_READONLY (decl) && shared_ctx->is_nested)
759         {
760           omp_context *up;
761
762           for (up = shared_ctx->outer; up; up = up->outer)
763             if (is_taskreg_ctx (up) && maybe_lookup_decl (decl, up))
764               break;
765
766           if (up)
767             {
768               tree c;
769
770               for (c = gimple_omp_taskreg_clauses (up->stmt);
771                    c; c = OMP_CLAUSE_CHAIN (c))
772                 if (OMP_CLAUSE_CODE (c) == OMP_CLAUSE_SHARED
773                     && OMP_CLAUSE_DECL (c) == decl)
774                   break;
775
776               if (c)
777                 return true;
778             }
779         }
780
781       /* For tasks avoid using copy-in/out, unless they are readonly
782          (in which case just copy-in is used).  As tasks can be
783          deferred or executed in different thread, when GOMP_task
784          returns, the task hasn't necessarily terminated.  */
785       if (!TREE_READONLY (decl) && is_task_ctx (shared_ctx))
786         {
787           tree outer = maybe_lookup_decl_in_outer_ctx (decl, shared_ctx);
788           if (is_gimple_reg (outer))
789             {
790               /* Taking address of OUTER in lower_send_shared_vars
791                  might need regimplification of everything that uses the
792                  variable.  */
793               if (!task_shared_vars)
794                 task_shared_vars = BITMAP_ALLOC (NULL);
795               bitmap_set_bit (task_shared_vars, DECL_UID (outer));
796               TREE_ADDRESSABLE (outer) = 1;
797             }
798           return true;
799         }
800     }
801
802   return false;
803 }
804
805 /* Create a new VAR_DECL and copy information from VAR to it.  */
806
807 tree
808 copy_var_decl (tree var, tree name, tree type)
809 {
810   tree copy = build_decl (VAR_DECL, name, type);
811
812   TREE_ADDRESSABLE (copy) = TREE_ADDRESSABLE (var);
813   TREE_THIS_VOLATILE (copy) = TREE_THIS_VOLATILE (var);
814   DECL_GIMPLE_REG_P (copy) = DECL_GIMPLE_REG_P (var);
815   DECL_NO_TBAA_P (copy) = DECL_NO_TBAA_P (var);
816   DECL_ARTIFICIAL (copy) = DECL_ARTIFICIAL (var);
817   DECL_IGNORED_P (copy) = DECL_IGNORED_P (var);
818   DECL_CONTEXT (copy) = DECL_CONTEXT (var);
819   DECL_SOURCE_LOCATION (copy) = DECL_SOURCE_LOCATION (var);
820   TREE_USED (copy) = 1;
821   DECL_SEEN_IN_BIND_EXPR_P (copy) = 1;
822
823   return copy;
824 }
825
826 /* Construct a new automatic decl similar to VAR.  */
827
828 static tree
829 omp_copy_decl_2 (tree var, tree name, tree type, omp_context *ctx)
830 {
831   tree copy = copy_var_decl (var, name, type);
832
833   DECL_CONTEXT (copy) = current_function_decl;
834   TREE_CHAIN (copy) = ctx->block_vars;
835   ctx->block_vars = copy;
836
837   return copy;
838 }
839
840 static tree
841 omp_copy_decl_1 (tree var, omp_context *ctx)
842 {
843   return omp_copy_decl_2 (var, DECL_NAME (var), TREE_TYPE (var), ctx);
844 }
845
846 /* Build tree nodes to access the field for VAR on the receiver side.  */
847
848 static tree
849 build_receiver_ref (tree var, bool by_ref, omp_context *ctx)
850 {
851   tree x, field = lookup_field (var, ctx);
852
853   /* If the receiver record type was remapped in the child function,
854      remap the field into the new record type.  */
855   x = maybe_lookup_field (field, ctx);
856   if (x != NULL)
857     field = x;
858
859   x = build_fold_indirect_ref (ctx->receiver_decl);
860   x = build3 (COMPONENT_REF, TREE_TYPE (field), x, field, NULL);
861   if (by_ref)
862     x = build_fold_indirect_ref (x);
863
864   return x;
865 }
866
867 /* Build tree nodes to access VAR in the scope outer to CTX.  In the case
868    of a parallel, this is a component reference; for workshare constructs
869    this is some variable.  */
870
871 static tree
872 build_outer_var_ref (tree var, omp_context *ctx)
873 {
874   tree x;
875
876   if (is_global_var (maybe_lookup_decl_in_outer_ctx (var, ctx)))
877     x = var;
878   else if (is_variable_sized (var))
879     {
880       x = TREE_OPERAND (DECL_VALUE_EXPR (var), 0);
881       x = build_outer_var_ref (x, ctx);
882       x = build_fold_indirect_ref (x);
883     }
884   else if (is_taskreg_ctx (ctx))
885     {
886       bool by_ref = use_pointer_for_field (var, NULL);
887       x = build_receiver_ref (var, by_ref, ctx);
888     }
889   else if (ctx->outer)
890     x = lookup_decl (var, ctx->outer);
891   else if (is_reference (var))
892     /* This can happen with orphaned constructs.  If var is reference, it is
893        possible it is shared and as such valid.  */
894     x = var;
895   else
896     gcc_unreachable ();
897
898   if (is_reference (var))
899     x = build_fold_indirect_ref (x);
900
901   return x;
902 }
903
904 /* Build tree nodes to access the field for VAR on the sender side.  */
905
906 static tree
907 build_sender_ref (tree var, omp_context *ctx)
908 {
909   tree field = lookup_sfield (var, ctx);
910   return build3 (COMPONENT_REF, TREE_TYPE (field),
911                  ctx->sender_decl, field, NULL);
912 }
913
914 /* Add a new field for VAR inside the structure CTX->SENDER_DECL.  */
915
916 static void
917 install_var_field (tree var, bool by_ref, int mask, omp_context *ctx)
918 {
919   tree field, type, sfield = NULL_TREE;
920
921   gcc_assert ((mask & 1) == 0
922               || !splay_tree_lookup (ctx->field_map, (splay_tree_key) var));
923   gcc_assert ((mask & 2) == 0 || !ctx->sfield_map
924               || !splay_tree_lookup (ctx->sfield_map, (splay_tree_key) var));
925
926   type = TREE_TYPE (var);
927   if (by_ref)
928     type = build_pointer_type (type);
929   else if ((mask & 3) == 1 && is_reference (var))
930     type = TREE_TYPE (type);
931
932   field = build_decl (FIELD_DECL, DECL_NAME (var), type);
933
934   /* Remember what variable this field was created for.  This does have a
935      side effect of making dwarf2out ignore this member, so for helpful
936      debugging we clear it later in delete_omp_context.  */
937   DECL_ABSTRACT_ORIGIN (field) = var;
938   if (type == TREE_TYPE (var))
939     {
940       DECL_ALIGN (field) = DECL_ALIGN (var);
941       DECL_USER_ALIGN (field) = DECL_USER_ALIGN (var);
942       TREE_THIS_VOLATILE (field) = TREE_THIS_VOLATILE (var);
943     }
944   else
945     DECL_ALIGN (field) = TYPE_ALIGN (type);
946
947   if ((mask & 3) == 3)
948     {
949       insert_field_into_struct (ctx->record_type, field);
950       if (ctx->srecord_type)
951         {
952           sfield = build_decl (FIELD_DECL, DECL_NAME (var), type);
953           DECL_ABSTRACT_ORIGIN (sfield) = var;
954           DECL_ALIGN (sfield) = DECL_ALIGN (field);
955           DECL_USER_ALIGN (sfield) = DECL_USER_ALIGN (field);
956           TREE_THIS_VOLATILE (sfield) = TREE_THIS_VOLATILE (field);
957           insert_field_into_struct (ctx->srecord_type, sfield);
958         }
959     }
960   else
961     {
962       if (ctx->srecord_type == NULL_TREE)
963         {
964           tree t;
965
966           ctx->srecord_type = lang_hooks.types.make_type (RECORD_TYPE);
967           ctx->sfield_map = splay_tree_new (splay_tree_compare_pointers, 0, 0);
968           for (t = TYPE_FIELDS (ctx->record_type); t ; t = TREE_CHAIN (t))
969             {
970               sfield = build_decl (FIELD_DECL, DECL_NAME (t), TREE_TYPE (t));
971               DECL_ABSTRACT_ORIGIN (sfield) = DECL_ABSTRACT_ORIGIN (t);
972               insert_field_into_struct (ctx->srecord_type, sfield);
973               splay_tree_insert (ctx->sfield_map,
974                                  (splay_tree_key) DECL_ABSTRACT_ORIGIN (t),
975                                  (splay_tree_value) sfield);
976             }
977         }
978       sfield = field;
979       insert_field_into_struct ((mask & 1) ? ctx->record_type
980                                 : ctx->srecord_type, field);
981     }
982
983   if (mask & 1)
984     splay_tree_insert (ctx->field_map, (splay_tree_key) var,
985                        (splay_tree_value) field);
986   if ((mask & 2) && ctx->sfield_map)
987     splay_tree_insert (ctx->sfield_map, (splay_tree_key) var,
988                        (splay_tree_value) sfield);
989 }
990
991 static tree
992 install_var_local (tree var, omp_context *ctx)
993 {
994   tree new_var = omp_copy_decl_1 (var, ctx);
995   insert_decl_map (&ctx->cb, var, new_var);
996   return new_var;
997 }
998
999 /* Adjust the replacement for DECL in CTX for the new context.  This means
1000    copying the DECL_VALUE_EXPR, and fixing up the type.  */
1001
1002 static void
1003 fixup_remapped_decl (tree decl, omp_context *ctx, bool private_debug)
1004 {
1005   tree new_decl, size;
1006
1007   new_decl = lookup_decl (decl, ctx);
1008
1009   TREE_TYPE (new_decl) = remap_type (TREE_TYPE (decl), &ctx->cb);
1010
1011   if ((!TREE_CONSTANT (DECL_SIZE (new_decl)) || private_debug)
1012       && DECL_HAS_VALUE_EXPR_P (decl))
1013     {
1014       tree ve = DECL_VALUE_EXPR (decl);
1015       walk_tree (&ve, copy_tree_body_r, &ctx->cb, NULL);
1016       SET_DECL_VALUE_EXPR (new_decl, ve);
1017       DECL_HAS_VALUE_EXPR_P (new_decl) = 1;
1018     }
1019
1020   if (!TREE_CONSTANT (DECL_SIZE (new_decl)))
1021     {
1022       size = remap_decl (DECL_SIZE (decl), &ctx->cb);
1023       if (size == error_mark_node)
1024         size = TYPE_SIZE (TREE_TYPE (new_decl));
1025       DECL_SIZE (new_decl) = size;
1026
1027       size = remap_decl (DECL_SIZE_UNIT (decl), &ctx->cb);
1028       if (size == error_mark_node)
1029         size = TYPE_SIZE_UNIT (TREE_TYPE (new_decl));
1030       DECL_SIZE_UNIT (new_decl) = size;
1031     }
1032 }
1033
1034 /* The callback for remap_decl.  Search all containing contexts for a
1035    mapping of the variable; this avoids having to duplicate the splay
1036    tree ahead of time.  We know a mapping doesn't already exist in the
1037    given context.  Create new mappings to implement default semantics.  */
1038
1039 static tree
1040 omp_copy_decl (tree var, copy_body_data *cb)
1041 {
1042   omp_context *ctx = (omp_context *) cb;
1043   tree new_var;
1044
1045   if (TREE_CODE (var) == LABEL_DECL)
1046     {
1047       new_var = create_artificial_label ();
1048       DECL_CONTEXT (new_var) = current_function_decl;
1049       insert_decl_map (&ctx->cb, var, new_var);
1050       return new_var;
1051     }
1052
1053   while (!is_taskreg_ctx (ctx))
1054     {
1055       ctx = ctx->outer;
1056       if (ctx == NULL)
1057         return var;
1058       new_var = maybe_lookup_decl (var, ctx);
1059       if (new_var)
1060         return new_var;
1061     }
1062
1063   if (is_global_var (var) || decl_function_context (var) != ctx->cb.src_fn)
1064     return var;
1065
1066   return error_mark_node;
1067 }
1068
1069
1070 /* Return the parallel region associated with STMT.  */
1071
1072 /* Debugging dumps for parallel regions.  */
1073 void dump_omp_region (FILE *, struct omp_region *, int);
1074 void debug_omp_region (struct omp_region *);
1075 void debug_all_omp_regions (void);
1076
1077 /* Dump the parallel region tree rooted at REGION.  */
1078
1079 void
1080 dump_omp_region (FILE *file, struct omp_region *region, int indent)
1081 {
1082   fprintf (file, "%*sbb %d: %s\n", indent, "", region->entry->index,
1083            gimple_code_name[region->type]);
1084
1085   if (region->inner)
1086     dump_omp_region (file, region->inner, indent + 4);
1087
1088   if (region->cont)
1089     {
1090       fprintf (file, "%*sbb %d: GIMPLE_OMP_CONTINUE\n", indent, "",
1091                region->cont->index);
1092     }
1093     
1094   if (region->exit)
1095     fprintf (file, "%*sbb %d: GIMPLE_OMP_RETURN\n", indent, "",
1096              region->exit->index);
1097   else
1098     fprintf (file, "%*s[no exit marker]\n", indent, "");
1099
1100   if (region->next)
1101     dump_omp_region (file, region->next, indent);
1102 }
1103
1104 void
1105 debug_omp_region (struct omp_region *region)
1106 {
1107   dump_omp_region (stderr, region, 0);
1108 }
1109
1110 void
1111 debug_all_omp_regions (void)
1112 {
1113   dump_omp_region (stderr, root_omp_region, 0);
1114 }
1115
1116
1117 /* Create a new parallel region starting at STMT inside region PARENT.  */
1118
1119 struct omp_region *
1120 new_omp_region (basic_block bb, enum gimple_code type,
1121                 struct omp_region *parent)
1122 {
1123   struct omp_region *region = XCNEW (struct omp_region);
1124
1125   region->outer = parent;
1126   region->entry = bb;
1127   region->type = type;
1128
1129   if (parent)
1130     {
1131       /* This is a nested region.  Add it to the list of inner
1132          regions in PARENT.  */
1133       region->next = parent->inner;
1134       parent->inner = region;
1135     }
1136   else
1137     {
1138       /* This is a toplevel region.  Add it to the list of toplevel
1139          regions in ROOT_OMP_REGION.  */
1140       region->next = root_omp_region;
1141       root_omp_region = region;
1142     }
1143
1144   return region;
1145 }
1146
1147 /* Release the memory associated with the region tree rooted at REGION.  */
1148
1149 static void
1150 free_omp_region_1 (struct omp_region *region)
1151 {
1152   struct omp_region *i, *n;
1153
1154   for (i = region->inner; i ; i = n)
1155     {
1156       n = i->next;
1157       free_omp_region_1 (i);
1158     }
1159
1160   free (region);
1161 }
1162
1163 /* Release the memory for the entire omp region tree.  */
1164
1165 void
1166 free_omp_regions (void)
1167 {
1168   struct omp_region *r, *n;
1169   for (r = root_omp_region; r ; r = n)
1170     {
1171       n = r->next;
1172       free_omp_region_1 (r);
1173     }
1174   root_omp_region = NULL;
1175 }
1176
1177
1178 /* Create a new context, with OUTER_CTX being the surrounding context.  */
1179
1180 static omp_context *
1181 new_omp_context (gimple stmt, omp_context *outer_ctx)
1182 {
1183   omp_context *ctx = XCNEW (omp_context);
1184
1185   splay_tree_insert (all_contexts, (splay_tree_key) stmt,
1186                      (splay_tree_value) ctx);
1187   ctx->stmt = stmt;
1188
1189   if (outer_ctx)
1190     {
1191       ctx->outer = outer_ctx;
1192       ctx->cb = outer_ctx->cb;
1193       ctx->cb.block = NULL;
1194       ctx->depth = outer_ctx->depth + 1;
1195     }
1196   else
1197     {
1198       ctx->cb.src_fn = current_function_decl;
1199       ctx->cb.dst_fn = current_function_decl;
1200       ctx->cb.src_node = cgraph_node (current_function_decl);
1201       ctx->cb.dst_node = ctx->cb.src_node;
1202       ctx->cb.src_cfun = cfun;
1203       ctx->cb.copy_decl = omp_copy_decl;
1204       ctx->cb.eh_region = -1;
1205       ctx->cb.transform_call_graph_edges = CB_CGE_MOVE;
1206       ctx->depth = 1;
1207     }
1208
1209   ctx->cb.decl_map = pointer_map_create ();
1210
1211   return ctx;
1212 }
1213
1214 static gimple_seq maybe_catch_exception (gimple_seq);
1215
1216 /* Finalize task copyfn.  */
1217
1218 static void
1219 finalize_task_copyfn (gimple task_stmt)
1220 {
1221   struct function *child_cfun;
1222   tree child_fn, old_fn;
1223   gimple_seq seq, new_seq;
1224   gimple bind;
1225
1226   child_fn = gimple_omp_task_copy_fn (task_stmt);
1227   if (child_fn == NULL_TREE)
1228     return;
1229
1230   child_cfun = DECL_STRUCT_FUNCTION (child_fn);
1231
1232   /* Inform the callgraph about the new function.  */
1233   DECL_STRUCT_FUNCTION (child_fn)->curr_properties
1234     = cfun->curr_properties;
1235
1236   old_fn = current_function_decl;
1237   push_cfun (child_cfun);
1238   current_function_decl = child_fn;
1239   bind = gimplify_body (&DECL_SAVED_TREE (child_fn), child_fn, false);
1240   seq = gimple_seq_alloc ();
1241   gimple_seq_add_stmt (&seq, bind);
1242   new_seq = maybe_catch_exception (seq);
1243   if (new_seq != seq)
1244     {
1245       bind = gimple_build_bind (NULL, new_seq, NULL);
1246       seq = gimple_seq_alloc ();
1247       gimple_seq_add_stmt (&seq, bind);
1248     }
1249   gimple_set_body (child_fn, seq);
1250   pop_cfun ();
1251   current_function_decl = old_fn;
1252
1253   cgraph_add_new_function (child_fn, false);
1254 }
1255
1256 /* Destroy a omp_context data structures.  Called through the splay tree
1257    value delete callback.  */
1258
1259 static void
1260 delete_omp_context (splay_tree_value value)
1261 {
1262   omp_context *ctx = (omp_context *) value;
1263
1264   pointer_map_destroy (ctx->cb.decl_map);
1265
1266   if (ctx->field_map)
1267     splay_tree_delete (ctx->field_map);
1268   if (ctx->sfield_map)
1269     splay_tree_delete (ctx->sfield_map);
1270
1271   /* We hijacked DECL_ABSTRACT_ORIGIN earlier.  We need to clear it before
1272      it produces corrupt debug information.  */
1273   if (ctx->record_type)
1274     {
1275       tree t;
1276       for (t = TYPE_FIELDS (ctx->record_type); t ; t = TREE_CHAIN (t))
1277         DECL_ABSTRACT_ORIGIN (t) = NULL;
1278     }
1279   if (ctx->srecord_type)
1280     {
1281       tree t;
1282       for (t = TYPE_FIELDS (ctx->srecord_type); t ; t = TREE_CHAIN (t))
1283         DECL_ABSTRACT_ORIGIN (t) = NULL;
1284     }
1285
1286   if (is_task_ctx (ctx))
1287     finalize_task_copyfn (ctx->stmt);
1288
1289   XDELETE (ctx);
1290 }
1291
1292 /* Fix up RECEIVER_DECL with a type that has been remapped to the child
1293    context.  */
1294
1295 static void
1296 fixup_child_record_type (omp_context *ctx)
1297 {
1298   tree f, type = ctx->record_type;
1299
1300   /* ??? It isn't sufficient to just call remap_type here, because
1301      variably_modified_type_p doesn't work the way we expect for
1302      record types.  Testing each field for whether it needs remapping
1303      and creating a new record by hand works, however.  */
1304   for (f = TYPE_FIELDS (type); f ; f = TREE_CHAIN (f))
1305     if (variably_modified_type_p (TREE_TYPE (f), ctx->cb.src_fn))
1306       break;
1307   if (f)
1308     {
1309       tree name, new_fields = NULL;
1310
1311       type = lang_hooks.types.make_type (RECORD_TYPE);
1312       name = DECL_NAME (TYPE_NAME (ctx->record_type));
1313       name = build_decl (TYPE_DECL, name, type);
1314       TYPE_NAME (type) = name;
1315
1316       for (f = TYPE_FIELDS (ctx->record_type); f ; f = TREE_CHAIN (f))
1317         {
1318           tree new_f = copy_node (f);
1319           DECL_CONTEXT (new_f) = type;
1320           TREE_TYPE (new_f) = remap_type (TREE_TYPE (f), &ctx->cb);
1321           TREE_CHAIN (new_f) = new_fields;
1322           walk_tree (&DECL_SIZE (new_f), copy_tree_body_r, &ctx->cb, NULL);
1323           walk_tree (&DECL_SIZE_UNIT (new_f), copy_tree_body_r,
1324                      &ctx->cb, NULL);
1325           walk_tree (&DECL_FIELD_OFFSET (new_f), copy_tree_body_r,
1326                      &ctx->cb, NULL);
1327           new_fields = new_f;
1328
1329           /* Arrange to be able to look up the receiver field
1330              given the sender field.  */
1331           splay_tree_insert (ctx->field_map, (splay_tree_key) f,
1332                              (splay_tree_value) new_f);
1333         }
1334       TYPE_FIELDS (type) = nreverse (new_fields);
1335       layout_type (type);
1336     }
1337
1338   TREE_TYPE (ctx->receiver_decl) = build_pointer_type (type);
1339 }
1340
1341 /* Instantiate decls as necessary in CTX to satisfy the data sharing
1342    specified by CLAUSES.  */
1343
1344 static void
1345 scan_sharing_clauses (tree clauses, omp_context *ctx)
1346 {
1347   tree c, decl;
1348   bool scan_array_reductions = false;
1349
1350   for (c = clauses; c; c = OMP_CLAUSE_CHAIN (c))
1351     {
1352       bool by_ref;
1353
1354       switch (OMP_CLAUSE_CODE (c))
1355         {
1356         case OMP_CLAUSE_PRIVATE:
1357           decl = OMP_CLAUSE_DECL (c);
1358           if (OMP_CLAUSE_PRIVATE_OUTER_REF (c))
1359             goto do_private;
1360           else if (!is_variable_sized (decl))
1361             install_var_local (decl, ctx);
1362           break;
1363
1364         case OMP_CLAUSE_SHARED:
1365           gcc_assert (is_taskreg_ctx (ctx));
1366           decl = OMP_CLAUSE_DECL (c);
1367           gcc_assert (!COMPLETE_TYPE_P (TREE_TYPE (decl))
1368                       || !is_variable_sized (decl));
1369           /* Global variables don't need to be copied,
1370              the receiver side will use them directly.  */
1371           if (is_global_var (maybe_lookup_decl_in_outer_ctx (decl, ctx)))
1372             break;
1373           by_ref = use_pointer_for_field (decl, ctx);
1374           if (! TREE_READONLY (decl)
1375               || TREE_ADDRESSABLE (decl)
1376               || by_ref
1377               || is_reference (decl))
1378             {
1379               install_var_field (decl, by_ref, 3, ctx);
1380               install_var_local (decl, ctx);
1381               break;
1382             }
1383           /* We don't need to copy const scalar vars back.  */
1384           OMP_CLAUSE_SET_CODE (c, OMP_CLAUSE_FIRSTPRIVATE);
1385           goto do_private;
1386
1387         case OMP_CLAUSE_LASTPRIVATE:
1388           /* Let the corresponding firstprivate clause create
1389              the variable.  */
1390           if (OMP_CLAUSE_LASTPRIVATE_FIRSTPRIVATE (c))
1391             break;
1392           /* FALLTHRU */
1393
1394         case OMP_CLAUSE_FIRSTPRIVATE:
1395         case OMP_CLAUSE_REDUCTION:
1396           decl = OMP_CLAUSE_DECL (c);
1397         do_private:
1398           if (is_variable_sized (decl))
1399             {
1400               if (is_task_ctx (ctx))
1401                 install_var_field (decl, false, 1, ctx);
1402               break;
1403             }
1404           else if (is_taskreg_ctx (ctx))
1405             {
1406               bool global
1407                 = is_global_var (maybe_lookup_decl_in_outer_ctx (decl, ctx));
1408               by_ref = use_pointer_for_field (decl, NULL);
1409
1410               if (is_task_ctx (ctx)
1411                   && (global || by_ref || is_reference (decl)))
1412                 {
1413                   install_var_field (decl, false, 1, ctx);
1414                   if (!global)
1415                     install_var_field (decl, by_ref, 2, ctx);
1416                 }
1417               else if (!global)
1418                 install_var_field (decl, by_ref, 3, ctx);
1419             }
1420           install_var_local (decl, ctx);
1421           break;
1422
1423         case OMP_CLAUSE_COPYPRIVATE:
1424         case OMP_CLAUSE_COPYIN:
1425           decl = OMP_CLAUSE_DECL (c);
1426           by_ref = use_pointer_for_field (decl, NULL);
1427           install_var_field (decl, by_ref, 3, ctx);
1428           break;
1429
1430         case OMP_CLAUSE_DEFAULT:
1431           ctx->default_kind = OMP_CLAUSE_DEFAULT_KIND (c);
1432           break;
1433
1434         case OMP_CLAUSE_IF:
1435         case OMP_CLAUSE_NUM_THREADS:
1436         case OMP_CLAUSE_SCHEDULE:
1437           if (ctx->outer)
1438             scan_omp_op (&OMP_CLAUSE_OPERAND (c, 0), ctx->outer);
1439           break;
1440
1441         case OMP_CLAUSE_NOWAIT:
1442         case OMP_CLAUSE_ORDERED:
1443         case OMP_CLAUSE_COLLAPSE:
1444         case OMP_CLAUSE_UNTIED:
1445           break;
1446
1447         default:
1448           gcc_unreachable ();
1449         }
1450     }
1451
1452   for (c = clauses; c; c = OMP_CLAUSE_CHAIN (c))
1453     {
1454       switch (OMP_CLAUSE_CODE (c))
1455         {
1456         case OMP_CLAUSE_LASTPRIVATE:
1457           /* Let the corresponding firstprivate clause create
1458              the variable.  */
1459           if (OMP_CLAUSE_LASTPRIVATE_GIMPLE_SEQ (c))
1460             scan_array_reductions = true;
1461           if (OMP_CLAUSE_LASTPRIVATE_FIRSTPRIVATE (c))
1462             break;
1463           /* FALLTHRU */
1464
1465         case OMP_CLAUSE_PRIVATE:
1466         case OMP_CLAUSE_FIRSTPRIVATE:
1467         case OMP_CLAUSE_REDUCTION:
1468           decl = OMP_CLAUSE_DECL (c);
1469           if (is_variable_sized (decl))
1470             install_var_local (decl, ctx);
1471           fixup_remapped_decl (decl, ctx,
1472                                OMP_CLAUSE_CODE (c) == OMP_CLAUSE_PRIVATE
1473                                && OMP_CLAUSE_PRIVATE_DEBUG (c));
1474           if (OMP_CLAUSE_CODE (c) == OMP_CLAUSE_REDUCTION
1475               && OMP_CLAUSE_REDUCTION_PLACEHOLDER (c))
1476             scan_array_reductions = true;
1477           break;
1478
1479         case OMP_CLAUSE_SHARED:
1480           decl = OMP_CLAUSE_DECL (c);
1481           if (! is_global_var (maybe_lookup_decl_in_outer_ctx (decl, ctx)))
1482             fixup_remapped_decl (decl, ctx, false);
1483           break;
1484
1485         case OMP_CLAUSE_COPYPRIVATE:
1486         case OMP_CLAUSE_COPYIN:
1487         case OMP_CLAUSE_DEFAULT:
1488         case OMP_CLAUSE_IF:
1489         case OMP_CLAUSE_NUM_THREADS:
1490         case OMP_CLAUSE_SCHEDULE:
1491         case OMP_CLAUSE_NOWAIT:
1492         case OMP_CLAUSE_ORDERED:
1493         case OMP_CLAUSE_COLLAPSE:
1494         case OMP_CLAUSE_UNTIED:
1495           break;
1496
1497         default:
1498           gcc_unreachable ();
1499         }
1500     }
1501
1502   if (scan_array_reductions)
1503     for (c = clauses; c; c = OMP_CLAUSE_CHAIN (c))
1504       if (OMP_CLAUSE_CODE (c) == OMP_CLAUSE_REDUCTION
1505           && OMP_CLAUSE_REDUCTION_PLACEHOLDER (c))
1506         {
1507           scan_omp (OMP_CLAUSE_REDUCTION_GIMPLE_INIT (c), ctx);
1508           scan_omp (OMP_CLAUSE_REDUCTION_GIMPLE_MERGE (c), ctx);
1509         }
1510       else if (OMP_CLAUSE_CODE (c) == OMP_CLAUSE_LASTPRIVATE
1511                && OMP_CLAUSE_LASTPRIVATE_GIMPLE_SEQ (c))
1512         scan_omp (OMP_CLAUSE_LASTPRIVATE_GIMPLE_SEQ (c), ctx);
1513 }
1514
1515 /* Create a new name for omp child function.  Returns an identifier.  */
1516
1517 static GTY(()) unsigned int tmp_ompfn_id_num;
1518
1519 static tree
1520 create_omp_child_function_name (bool task_copy)
1521 {
1522   tree name = DECL_ASSEMBLER_NAME (current_function_decl);
1523   size_t len = IDENTIFIER_LENGTH (name);
1524   char *tmp_name, *prefix;
1525   const char *suffix;
1526
1527   suffix = task_copy ? "_omp_cpyfn" : "_omp_fn";
1528   prefix = XALLOCAVEC (char, len + strlen (suffix) + 1);
1529   memcpy (prefix, IDENTIFIER_POINTER (name), len);
1530   strcpy (prefix + len, suffix);
1531 #ifndef NO_DOT_IN_LABEL
1532   prefix[len] = '.';
1533 #elif !defined NO_DOLLAR_IN_LABEL
1534   prefix[len] = '$';
1535 #endif
1536   ASM_FORMAT_PRIVATE_NAME (tmp_name, prefix, tmp_ompfn_id_num++);
1537   return get_identifier (tmp_name);
1538 }
1539
1540 /* Build a decl for the omp child function.  It'll not contain a body
1541    yet, just the bare decl.  */
1542
1543 static void
1544 create_omp_child_function (omp_context *ctx, bool task_copy)
1545 {
1546   tree decl, type, name, t;
1547
1548   name = create_omp_child_function_name (task_copy);
1549   if (task_copy)
1550     type = build_function_type_list (void_type_node, ptr_type_node,
1551                                      ptr_type_node, NULL_TREE);
1552   else
1553     type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
1554
1555   decl = build_decl (FUNCTION_DECL, name, type);
1556   decl = lang_hooks.decls.pushdecl (decl);
1557
1558   if (!task_copy)
1559     ctx->cb.dst_fn = decl;
1560   else
1561     gimple_omp_task_set_copy_fn (ctx->stmt, decl);
1562
1563   TREE_STATIC (decl) = 1;
1564   TREE_USED (decl) = 1;
1565   DECL_ARTIFICIAL (decl) = 1;
1566   DECL_IGNORED_P (decl) = 0;
1567   TREE_PUBLIC (decl) = 0;
1568   DECL_UNINLINABLE (decl) = 1;
1569   DECL_EXTERNAL (decl) = 0;
1570   DECL_CONTEXT (decl) = NULL_TREE;
1571   DECL_INITIAL (decl) = make_node (BLOCK);
1572
1573   t = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
1574   DECL_ARTIFICIAL (t) = 1;
1575   DECL_IGNORED_P (t) = 1;
1576   DECL_RESULT (decl) = t;
1577
1578   t = build_decl (PARM_DECL, get_identifier (".omp_data_i"), ptr_type_node);
1579   DECL_ARTIFICIAL (t) = 1;
1580   DECL_ARG_TYPE (t) = ptr_type_node;
1581   DECL_CONTEXT (t) = current_function_decl;
1582   TREE_USED (t) = 1;
1583   DECL_ARGUMENTS (decl) = t;
1584   if (!task_copy)
1585     ctx->receiver_decl = t;
1586   else
1587     {
1588       t = build_decl (PARM_DECL, get_identifier (".omp_data_o"),
1589                       ptr_type_node);
1590       DECL_ARTIFICIAL (t) = 1;
1591       DECL_ARG_TYPE (t) = ptr_type_node;
1592       DECL_CONTEXT (t) = current_function_decl;
1593       TREE_USED (t) = 1;
1594       TREE_CHAIN (t) = DECL_ARGUMENTS (decl);
1595       DECL_ARGUMENTS (decl) = t;
1596     }
1597
1598   /* Allocate memory for the function structure.  The call to 
1599      allocate_struct_function clobbers CFUN, so we need to restore
1600      it afterward.  */
1601   push_struct_function (decl);
1602   DECL_SOURCE_LOCATION (decl) = gimple_location (ctx->stmt);
1603   cfun->function_end_locus = gimple_location (ctx->stmt);
1604   pop_cfun ();
1605 }
1606
1607
1608 /* Scan an OpenMP parallel directive.  */
1609
1610 static void
1611 scan_omp_parallel (gimple_stmt_iterator *gsi, omp_context *outer_ctx)
1612 {
1613   omp_context *ctx;
1614   tree name;
1615   gimple stmt = gsi_stmt (*gsi);
1616
1617   /* Ignore parallel directives with empty bodies, unless there
1618      are copyin clauses.  */
1619   if (optimize > 0
1620       && empty_body_p (gimple_omp_body (stmt))
1621       && find_omp_clause (gimple_omp_parallel_clauses (stmt),
1622                           OMP_CLAUSE_COPYIN) == NULL)
1623     {
1624       gsi_replace (gsi, gimple_build_nop (), false);
1625       return;
1626     }
1627
1628   ctx = new_omp_context (stmt, outer_ctx);
1629   if (taskreg_nesting_level > 1)
1630     ctx->is_nested = true;
1631   ctx->field_map = splay_tree_new (splay_tree_compare_pointers, 0, 0);
1632   ctx->default_kind = OMP_CLAUSE_DEFAULT_SHARED;
1633   ctx->record_type = lang_hooks.types.make_type (RECORD_TYPE);
1634   name = create_tmp_var_name (".omp_data_s");
1635   name = build_decl (TYPE_DECL, name, ctx->record_type);
1636   TYPE_NAME (ctx->record_type) = name;
1637   create_omp_child_function (ctx, false);
1638   gimple_omp_parallel_set_child_fn (stmt, ctx->cb.dst_fn);
1639
1640   scan_sharing_clauses (gimple_omp_parallel_clauses (stmt), ctx);
1641   scan_omp (gimple_omp_body (stmt), ctx);
1642
1643   if (TYPE_FIELDS (ctx->record_type) == NULL)
1644     ctx->record_type = ctx->receiver_decl = NULL;
1645   else
1646     {
1647       layout_type (ctx->record_type);
1648       fixup_child_record_type (ctx);
1649     }
1650 }
1651
1652 /* Scan an OpenMP task directive.  */
1653
1654 static void
1655 scan_omp_task (gimple_stmt_iterator *gsi, omp_context *outer_ctx)
1656 {
1657   omp_context *ctx;
1658   tree name, t;
1659   gimple stmt = gsi_stmt (*gsi);
1660
1661   /* Ignore task directives with empty bodies.  */
1662   if (optimize > 0
1663       && empty_body_p (gimple_omp_body (stmt)))
1664     {
1665       gsi_replace (gsi, gimple_build_nop (), false);
1666       return;
1667     }
1668
1669   ctx = new_omp_context (stmt, outer_ctx);
1670   if (taskreg_nesting_level > 1)
1671     ctx->is_nested = true;
1672   ctx->field_map = splay_tree_new (splay_tree_compare_pointers, 0, 0);
1673   ctx->default_kind = OMP_CLAUSE_DEFAULT_SHARED;
1674   ctx->record_type = lang_hooks.types.make_type (RECORD_TYPE);
1675   name = create_tmp_var_name (".omp_data_s");
1676   name = build_decl (TYPE_DECL, name, ctx->record_type);
1677   TYPE_NAME (ctx->record_type) = name;
1678   create_omp_child_function (ctx, false);
1679   gimple_omp_task_set_child_fn (stmt, ctx->cb.dst_fn);
1680
1681   scan_sharing_clauses (gimple_omp_task_clauses (stmt), ctx);
1682
1683   if (ctx->srecord_type)
1684     {
1685       name = create_tmp_var_name (".omp_data_a");
1686       name = build_decl (TYPE_DECL, name, ctx->srecord_type);
1687       TYPE_NAME (ctx->srecord_type) = name;
1688       create_omp_child_function (ctx, true);
1689     }
1690
1691   scan_omp (gimple_omp_body (stmt), ctx);
1692
1693   if (TYPE_FIELDS (ctx->record_type) == NULL)
1694     {
1695       ctx->record_type = ctx->receiver_decl = NULL;
1696       t = build_int_cst (long_integer_type_node, 0);
1697       gimple_omp_task_set_arg_size (stmt, t);
1698       t = build_int_cst (long_integer_type_node, 1);
1699       gimple_omp_task_set_arg_align (stmt, t);
1700     }
1701   else
1702     {
1703       tree *p, vla_fields = NULL_TREE, *q = &vla_fields;
1704       /* Move VLA fields to the end.  */
1705       p = &TYPE_FIELDS (ctx->record_type);
1706       while (*p)
1707         if (!TYPE_SIZE_UNIT (TREE_TYPE (*p))
1708             || ! TREE_CONSTANT (TYPE_SIZE_UNIT (TREE_TYPE (*p))))
1709           {
1710             *q = *p;
1711             *p = TREE_CHAIN (*p);
1712             TREE_CHAIN (*q) = NULL_TREE;
1713             q = &TREE_CHAIN (*q);
1714           }
1715         else
1716           p = &TREE_CHAIN (*p);
1717       *p = vla_fields;
1718       layout_type (ctx->record_type);
1719       fixup_child_record_type (ctx);
1720       if (ctx->srecord_type)
1721         layout_type (ctx->srecord_type);
1722       t = fold_convert (long_integer_type_node,
1723                         TYPE_SIZE_UNIT (ctx->record_type));
1724       gimple_omp_task_set_arg_size (stmt, t);
1725       t = build_int_cst (long_integer_type_node,
1726                          TYPE_ALIGN_UNIT (ctx->record_type));
1727       gimple_omp_task_set_arg_align (stmt, t);
1728     }
1729 }
1730
1731
1732 /* Scan an OpenMP loop directive.  */
1733
1734 static void
1735 scan_omp_for (gimple stmt, omp_context *outer_ctx)
1736 {
1737   omp_context *ctx;
1738   size_t i;
1739
1740   ctx = new_omp_context (stmt, outer_ctx);
1741
1742   scan_sharing_clauses (gimple_omp_for_clauses (stmt), ctx);
1743
1744   scan_omp (gimple_omp_for_pre_body (stmt), ctx);
1745   for (i = 0; i < gimple_omp_for_collapse (stmt); i++)
1746     {
1747       scan_omp_op (gimple_omp_for_index_ptr (stmt, i), ctx);
1748       scan_omp_op (gimple_omp_for_initial_ptr (stmt, i), ctx);
1749       scan_omp_op (gimple_omp_for_final_ptr (stmt, i), ctx);
1750       scan_omp_op (gimple_omp_for_incr_ptr (stmt, i), ctx);
1751     }
1752   scan_omp (gimple_omp_body (stmt), ctx);
1753 }
1754
1755 /* Scan an OpenMP sections directive.  */
1756
1757 static void
1758 scan_omp_sections (gimple stmt, omp_context *outer_ctx)
1759 {
1760   omp_context *ctx;
1761
1762   ctx = new_omp_context (stmt, outer_ctx);
1763   scan_sharing_clauses (gimple_omp_sections_clauses (stmt), ctx);
1764   scan_omp (gimple_omp_body (stmt), ctx);
1765 }
1766
1767 /* Scan an OpenMP single directive.  */
1768
1769 static void
1770 scan_omp_single (gimple stmt, omp_context *outer_ctx)
1771 {
1772   omp_context *ctx;
1773   tree name;
1774
1775   ctx = new_omp_context (stmt, outer_ctx);
1776   ctx->field_map = splay_tree_new (splay_tree_compare_pointers, 0, 0);
1777   ctx->record_type = lang_hooks.types.make_type (RECORD_TYPE);
1778   name = create_tmp_var_name (".omp_copy_s");
1779   name = build_decl (TYPE_DECL, name, ctx->record_type);
1780   TYPE_NAME (ctx->record_type) = name;
1781
1782   scan_sharing_clauses (gimple_omp_single_clauses (stmt), ctx);
1783   scan_omp (gimple_omp_body (stmt), ctx);
1784
1785   if (TYPE_FIELDS (ctx->record_type) == NULL)
1786     ctx->record_type = NULL;
1787   else
1788     layout_type (ctx->record_type);
1789 }
1790
1791
1792 /* Check OpenMP nesting restrictions.  */
1793 static void
1794 check_omp_nesting_restrictions (gimple  stmt, omp_context *ctx)
1795 {
1796   switch (gimple_code (stmt))
1797     {
1798     case GIMPLE_OMP_FOR:
1799     case GIMPLE_OMP_SECTIONS:
1800     case GIMPLE_OMP_SINGLE:
1801     case GIMPLE_CALL:
1802       for (; ctx != NULL; ctx = ctx->outer)
1803         switch (gimple_code (ctx->stmt))
1804           {
1805           case GIMPLE_OMP_FOR:
1806           case GIMPLE_OMP_SECTIONS:
1807           case GIMPLE_OMP_SINGLE:
1808           case GIMPLE_OMP_ORDERED:
1809           case GIMPLE_OMP_MASTER:
1810           case GIMPLE_OMP_TASK:
1811             if (is_gimple_call (stmt))
1812               {
1813                 warning (0, "barrier region may not be closely nested inside "
1814                             "of work-sharing, critical, ordered, master or "
1815                             "explicit task region");
1816                 return;
1817               }
1818             warning (0, "work-sharing region may not be closely nested inside "
1819                         "of work-sharing, critical, ordered, master or explicit "
1820                         "task region");
1821             return;
1822           case GIMPLE_OMP_PARALLEL:
1823             return;
1824           default:
1825             break;
1826           }
1827       break;
1828     case GIMPLE_OMP_MASTER:
1829       for (; ctx != NULL; ctx = ctx->outer)
1830         switch (gimple_code (ctx->stmt))
1831           {
1832           case GIMPLE_OMP_FOR:
1833           case GIMPLE_OMP_SECTIONS:
1834           case GIMPLE_OMP_SINGLE:
1835           case GIMPLE_OMP_TASK:
1836             warning (0, "master region may not be closely nested inside "
1837                         "of work-sharing or explicit task region");
1838             return;
1839           case GIMPLE_OMP_PARALLEL:
1840             return;
1841           default:
1842             break;
1843           }
1844       break;
1845     case GIMPLE_OMP_ORDERED:
1846       for (; ctx != NULL; ctx = ctx->outer)
1847         switch (gimple_code (ctx->stmt))
1848           {
1849           case GIMPLE_OMP_CRITICAL:
1850           case GIMPLE_OMP_TASK:
1851             warning (0, "ordered region may not be closely nested inside "
1852                         "of critical or explicit task region");
1853             return;
1854           case GIMPLE_OMP_FOR:
1855             if (find_omp_clause (gimple_omp_for_clauses (ctx->stmt),
1856                                  OMP_CLAUSE_ORDERED) == NULL)
1857               warning (0, "ordered region must be closely nested inside "
1858                           "a loop region with an ordered clause");
1859             return;
1860           case GIMPLE_OMP_PARALLEL:
1861             return;
1862           default:
1863             break;
1864           }
1865       break;
1866     case GIMPLE_OMP_CRITICAL:
1867       for (; ctx != NULL; ctx = ctx->outer)
1868         if (gimple_code (ctx->stmt) == GIMPLE_OMP_CRITICAL
1869             && (gimple_omp_critical_name (stmt)
1870                 == gimple_omp_critical_name (ctx->stmt)))
1871           {
1872             warning (0, "critical region may not be nested inside a critical "
1873                         "region with the same name");
1874             return;
1875           }
1876       break;
1877     default:
1878       break;
1879     }
1880 }
1881
1882
1883 /* Helper function scan_omp.
1884
1885    Callback for walk_tree or operators in walk_gimple_stmt used to
1886    scan for OpenMP directives in TP.  */
1887
1888 static tree
1889 scan_omp_1_op (tree *tp, int *walk_subtrees, void *data)
1890 {
1891   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
1892   omp_context *ctx = (omp_context *) wi->info;
1893   tree t = *tp;
1894
1895   switch (TREE_CODE (t))
1896     {
1897     case VAR_DECL:
1898     case PARM_DECL:
1899     case LABEL_DECL:
1900     case RESULT_DECL:
1901       if (ctx)
1902         *tp = remap_decl (t, &ctx->cb);
1903       break;
1904
1905     default:
1906       if (ctx && TYPE_P (t))
1907         *tp = remap_type (t, &ctx->cb);
1908       else if (!DECL_P (t))
1909         *walk_subtrees = 1;
1910       break;
1911     }
1912
1913   return NULL_TREE;
1914 }
1915
1916
1917 /* Helper function for scan_omp.
1918
1919    Callback for walk_gimple_stmt used to scan for OpenMP directives in
1920    the current statement in GSI.  */
1921
1922 static tree
1923 scan_omp_1_stmt (gimple_stmt_iterator *gsi, bool *handled_ops_p,
1924                  struct walk_stmt_info *wi)
1925 {
1926   gimple stmt = gsi_stmt (*gsi);
1927   omp_context *ctx = (omp_context *) wi->info;
1928
1929   if (gimple_has_location (stmt))
1930     input_location = gimple_location (stmt);
1931
1932   /* Check the OpenMP nesting restrictions.  */
1933   if (ctx != NULL)
1934     {
1935       if (is_gimple_omp (stmt))
1936         check_omp_nesting_restrictions (stmt, ctx);
1937       else if (is_gimple_call (stmt))
1938         {
1939           tree fndecl = gimple_call_fndecl (stmt);
1940           if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
1941               && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_GOMP_BARRIER)
1942             check_omp_nesting_restrictions (stmt, ctx);
1943         }
1944     }
1945
1946   *handled_ops_p = true;
1947
1948   switch (gimple_code (stmt))
1949     {
1950     case GIMPLE_OMP_PARALLEL:
1951       taskreg_nesting_level++;
1952       scan_omp_parallel (gsi, ctx);
1953       taskreg_nesting_level--;
1954       break;
1955
1956     case GIMPLE_OMP_TASK:
1957       taskreg_nesting_level++;
1958       scan_omp_task (gsi, ctx);
1959       taskreg_nesting_level--;
1960       break;
1961
1962     case GIMPLE_OMP_FOR:
1963       scan_omp_for (stmt, ctx);
1964       break;
1965
1966     case GIMPLE_OMP_SECTIONS:
1967       scan_omp_sections (stmt, ctx);
1968       break;
1969
1970     case GIMPLE_OMP_SINGLE:
1971       scan_omp_single (stmt, ctx);
1972       break;
1973
1974     case GIMPLE_OMP_SECTION:
1975     case GIMPLE_OMP_MASTER:
1976     case GIMPLE_OMP_ORDERED:
1977     case GIMPLE_OMP_CRITICAL:
1978       ctx = new_omp_context (stmt, ctx);
1979       scan_omp (gimple_omp_body (stmt), ctx);
1980       break;
1981
1982     case GIMPLE_BIND:
1983       {
1984         tree var;
1985
1986         *handled_ops_p = false;
1987         if (ctx)
1988           for (var = gimple_bind_vars (stmt); var ; var = TREE_CHAIN (var))
1989             insert_decl_map (&ctx->cb, var, var);
1990       }
1991       break;
1992     default:
1993       *handled_ops_p = false;
1994       break;
1995     }
1996
1997   return NULL_TREE;
1998 }
1999
2000
2001 /* Scan all the statements starting at the current statement.  CTX
2002    contains context information about the OpenMP directives and
2003    clauses found during the scan.  */
2004
2005 static void
2006 scan_omp (gimple_seq body, omp_context *ctx)
2007 {
2008   location_t saved_location;
2009   struct walk_stmt_info wi;
2010
2011   memset (&wi, 0, sizeof (wi));
2012   wi.info = ctx;
2013   wi.want_locations = true;
2014
2015   saved_location = input_location;
2016   walk_gimple_seq (body, scan_omp_1_stmt, scan_omp_1_op, &wi);
2017   input_location = saved_location;
2018 }
2019 \f
2020 /* Re-gimplification and code generation routines.  */
2021
2022 /* Build a call to GOMP_barrier.  */
2023
2024 static tree
2025 build_omp_barrier (void)
2026 {
2027   return build_call_expr (built_in_decls[BUILT_IN_GOMP_BARRIER], 0);
2028 }
2029
2030 /* If a context was created for STMT when it was scanned, return it.  */
2031
2032 static omp_context *
2033 maybe_lookup_ctx (gimple stmt)
2034 {
2035   splay_tree_node n;
2036   n = splay_tree_lookup (all_contexts, (splay_tree_key) stmt);
2037   return n ? (omp_context *) n->value : NULL;
2038 }
2039
2040
2041 /* Find the mapping for DECL in CTX or the immediately enclosing
2042    context that has a mapping for DECL.
2043
2044    If CTX is a nested parallel directive, we may have to use the decl
2045    mappings created in CTX's parent context.  Suppose that we have the
2046    following parallel nesting (variable UIDs showed for clarity):
2047
2048         iD.1562 = 0;
2049         #omp parallel shared(iD.1562)           -> outer parallel
2050           iD.1562 = iD.1562 + 1;
2051
2052           #omp parallel shared (iD.1562)        -> inner parallel
2053              iD.1562 = iD.1562 - 1;
2054
2055    Each parallel structure will create a distinct .omp_data_s structure
2056    for copying iD.1562 in/out of the directive:
2057
2058         outer parallel          .omp_data_s.1.i -> iD.1562
2059         inner parallel          .omp_data_s.2.i -> iD.1562
2060
2061    A shared variable mapping will produce a copy-out operation before
2062    the parallel directive and a copy-in operation after it.  So, in
2063    this case we would have:
2064
2065         iD.1562 = 0;
2066         .omp_data_o.1.i = iD.1562;
2067         #omp parallel shared(iD.1562)           -> outer parallel
2068           .omp_data_i.1 = &.omp_data_o.1
2069           .omp_data_i.1->i = .omp_data_i.1->i + 1;
2070
2071           .omp_data_o.2.i = iD.1562;            -> **
2072           #omp parallel shared(iD.1562)         -> inner parallel
2073             .omp_data_i.2 = &.omp_data_o.2
2074             .omp_data_i.2->i = .omp_data_i.2->i - 1;
2075
2076
2077     ** This is a problem.  The symbol iD.1562 cannot be referenced
2078        inside the body of the outer parallel region.  But since we are
2079        emitting this copy operation while expanding the inner parallel
2080        directive, we need to access the CTX structure of the outer
2081        parallel directive to get the correct mapping:
2082
2083           .omp_data_o.2.i = .omp_data_i.1->i
2084
2085     Since there may be other workshare or parallel directives enclosing
2086     the parallel directive, it may be necessary to walk up the context
2087     parent chain.  This is not a problem in general because nested
2088     parallelism happens only rarely.  */
2089
2090 static tree
2091 lookup_decl_in_outer_ctx (tree decl, omp_context *ctx)
2092 {
2093   tree t;
2094   omp_context *up;
2095
2096   for (up = ctx->outer, t = NULL; up && t == NULL; up = up->outer)
2097     t = maybe_lookup_decl (decl, up);
2098
2099   gcc_assert (!ctx->is_nested || t || is_global_var (decl));
2100
2101   return t ? t : decl;
2102 }
2103
2104
2105 /* Similar to lookup_decl_in_outer_ctx, but return DECL if not found
2106    in outer contexts.  */
2107
2108 static tree
2109 maybe_lookup_decl_in_outer_ctx (tree decl, omp_context *ctx)
2110 {
2111   tree t = NULL;
2112   omp_context *up;
2113
2114   for (up = ctx->outer, t = NULL; up && t == NULL; up = up->outer)
2115     t = maybe_lookup_decl (decl, up);
2116
2117   return t ? t : decl;
2118 }
2119
2120
2121 /* Construct the initialization value for reduction CLAUSE.  */
2122
2123 tree
2124 omp_reduction_init (tree clause, tree type)
2125 {
2126   switch (OMP_CLAUSE_REDUCTION_CODE (clause))
2127     {
2128     case PLUS_EXPR:
2129     case MINUS_EXPR:
2130     case BIT_IOR_EXPR:
2131     case BIT_XOR_EXPR:
2132     case TRUTH_OR_EXPR:
2133     case TRUTH_ORIF_EXPR:
2134     case TRUTH_XOR_EXPR:
2135     case NE_EXPR:
2136       return fold_convert (type, integer_zero_node);
2137
2138     case MULT_EXPR:
2139     case TRUTH_AND_EXPR:
2140     case TRUTH_ANDIF_EXPR:
2141     case EQ_EXPR:
2142       return fold_convert (type, integer_one_node);
2143
2144     case BIT_AND_EXPR:
2145       return fold_convert (type, integer_minus_one_node);
2146
2147     case MAX_EXPR:
2148       if (SCALAR_FLOAT_TYPE_P (type))
2149         {
2150           REAL_VALUE_TYPE max, min;
2151           if (HONOR_INFINITIES (TYPE_MODE (type)))
2152             {
2153               real_inf (&max);
2154               real_arithmetic (&min, NEGATE_EXPR, &max, NULL);
2155             }
2156           else
2157             real_maxval (&min, 1, TYPE_MODE (type));
2158           return build_real (type, min);
2159         }
2160       else
2161         {
2162           gcc_assert (INTEGRAL_TYPE_P (type));
2163           return TYPE_MIN_VALUE (type);
2164         }
2165
2166     case MIN_EXPR:
2167       if (SCALAR_FLOAT_TYPE_P (type))
2168         {
2169           REAL_VALUE_TYPE max;
2170           if (HONOR_INFINITIES (TYPE_MODE (type)))
2171             real_inf (&max);
2172           else
2173             real_maxval (&max, 0, TYPE_MODE (type));
2174           return build_real (type, max);
2175         }
2176       else
2177         {
2178           gcc_assert (INTEGRAL_TYPE_P (type));
2179           return TYPE_MAX_VALUE (type);
2180         }
2181
2182     default:
2183       gcc_unreachable ();
2184     }
2185 }
2186
2187 /* Generate code to implement the input clauses, FIRSTPRIVATE and COPYIN,
2188    from the receiver (aka child) side and initializers for REFERENCE_TYPE
2189    private variables.  Initialization statements go in ILIST, while calls
2190    to destructors go in DLIST.  */
2191
2192 static void
2193 lower_rec_input_clauses (tree clauses, gimple_seq *ilist, gimple_seq *dlist,
2194                          omp_context *ctx)
2195 {
2196   gimple_stmt_iterator diter;
2197   tree c, dtor, copyin_seq, x, ptr;
2198   bool copyin_by_ref = false;
2199   bool lastprivate_firstprivate = false;
2200   int pass;
2201
2202   *dlist = gimple_seq_alloc ();
2203   diter = gsi_start (*dlist);
2204   copyin_seq = NULL;
2205
2206   /* Do all the fixed sized types in the first pass, and the variable sized
2207      types in the second pass.  This makes sure that the scalar arguments to
2208      the variable sized types are processed before we use them in the 
2209      variable sized operations.  */
2210   for (pass = 0; pass < 2; ++pass)
2211     {
2212       for (c = clauses; c ; c = OMP_CLAUSE_CHAIN (c))
2213         {
2214           enum omp_clause_code c_kind = OMP_CLAUSE_CODE (c);
2215           tree var, new_var;
2216           bool by_ref;
2217
2218           switch (c_kind)
2219             {
2220             case OMP_CLAUSE_PRIVATE:
2221               if (OMP_CLAUSE_PRIVATE_DEBUG (c))
2222                 continue;
2223               break;
2224             case OMP_CLAUSE_SHARED:
2225               if (maybe_lookup_decl (OMP_CLAUSE_DECL (c), ctx) == NULL)
2226                 {
2227                   gcc_assert (is_global_var (OMP_CLAUSE_DECL (c)));
2228                   continue;
2229                 }
2230             case OMP_CLAUSE_FIRSTPRIVATE:
2231             case OMP_CLAUSE_COPYIN:
2232             case OMP_CLAUSE_REDUCTION:
2233               break;
2234             case OMP_CLAUSE_LASTPRIVATE:
2235               if (OMP_CLAUSE_LASTPRIVATE_FIRSTPRIVATE (c))
2236                 {
2237                   lastprivate_firstprivate = true;
2238                   if (pass != 0)
2239                     continue;
2240                 }
2241               break;
2242             default:
2243               continue;
2244             }
2245
2246           new_var = var = OMP_CLAUSE_DECL (c);
2247           if (c_kind != OMP_CLAUSE_COPYIN)
2248             new_var = lookup_decl (var, ctx);
2249
2250           if (c_kind == OMP_CLAUSE_SHARED || c_kind == OMP_CLAUSE_COPYIN)
2251             {
2252               if (pass != 0)
2253                 continue;
2254             }
2255           else if (is_variable_sized (var))
2256             {
2257               /* For variable sized types, we need to allocate the
2258                  actual storage here.  Call alloca and store the
2259                  result in the pointer decl that we created elsewhere.  */
2260               if (pass == 0)
2261                 continue;
2262
2263               if (c_kind != OMP_CLAUSE_FIRSTPRIVATE || !is_task_ctx (ctx))
2264                 {
2265                   gimple stmt;
2266                   tree tmp;
2267
2268                   ptr = DECL_VALUE_EXPR (new_var);
2269                   gcc_assert (TREE_CODE (ptr) == INDIRECT_REF);
2270                   ptr = TREE_OPERAND (ptr, 0);
2271                   gcc_assert (DECL_P (ptr));
2272                   x = TYPE_SIZE_UNIT (TREE_TYPE (new_var));
2273
2274                   /* void *tmp = __builtin_alloca */
2275                   stmt
2276                     = gimple_build_call (built_in_decls[BUILT_IN_ALLOCA], 1, x);
2277                   tmp = create_tmp_var_raw (ptr_type_node, NULL);
2278                   gimple_add_tmp_var (tmp);
2279                   gimple_call_set_lhs (stmt, tmp);
2280
2281                   gimple_seq_add_stmt (ilist, stmt);
2282
2283                   x = fold_convert (TREE_TYPE (ptr), tmp);
2284                   gimplify_assign (ptr, x, ilist);
2285                 }
2286             }
2287           else if (is_reference (var))
2288             {
2289               /* For references that are being privatized for Fortran,
2290                  allocate new backing storage for the new pointer
2291                  variable.  This allows us to avoid changing all the
2292                  code that expects a pointer to something that expects
2293                  a direct variable.  Note that this doesn't apply to
2294                  C++, since reference types are disallowed in data
2295                  sharing clauses there, except for NRV optimized
2296                  return values.  */
2297               if (pass == 0)
2298                 continue;
2299
2300               x = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (new_var)));
2301               if (c_kind == OMP_CLAUSE_FIRSTPRIVATE && is_task_ctx (ctx))
2302                 {
2303                   x = build_receiver_ref (var, false, ctx);
2304                   x = build_fold_addr_expr (x);
2305                 }
2306               else if (TREE_CONSTANT (x))
2307                 {
2308                   const char *name = NULL;
2309                   if (DECL_NAME (var))
2310                     name = IDENTIFIER_POINTER (DECL_NAME (new_var));
2311
2312                   x = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (new_var)),
2313                                           name);
2314                   gimple_add_tmp_var (x);
2315                   x = build_fold_addr_expr_with_type (x, TREE_TYPE (new_var));
2316                 }
2317               else
2318                 {
2319                   x = build_call_expr (built_in_decls[BUILT_IN_ALLOCA], 1, x);
2320                   x = fold_convert (TREE_TYPE (new_var), x);
2321                 }
2322
2323               gimplify_assign (new_var, x, ilist);
2324
2325               new_var = build_fold_indirect_ref (new_var);
2326             }
2327           else if (c_kind == OMP_CLAUSE_REDUCTION
2328                    && OMP_CLAUSE_REDUCTION_PLACEHOLDER (c))
2329             {
2330               if (pass == 0)
2331                 continue;
2332             }
2333           else if (pass != 0)
2334             continue;
2335
2336           switch (OMP_CLAUSE_CODE (c))
2337             {
2338             case OMP_CLAUSE_SHARED:
2339               /* Shared global vars are just accessed directly.  */
2340               if (is_global_var (new_var))
2341                 break;
2342               /* Set up the DECL_VALUE_EXPR for shared variables now.  This
2343                  needs to be delayed until after fixup_child_record_type so
2344                  that we get the correct type during the dereference.  */
2345               by_ref = use_pointer_for_field (var, ctx);
2346               x = build_receiver_ref (var, by_ref, ctx);
2347               SET_DECL_VALUE_EXPR (new_var, x);
2348               DECL_HAS_VALUE_EXPR_P (new_var) = 1;
2349
2350               /* ??? If VAR is not passed by reference, and the variable
2351                  hasn't been initialized yet, then we'll get a warning for
2352                  the store into the omp_data_s structure.  Ideally, we'd be
2353                  able to notice this and not store anything at all, but 
2354                  we're generating code too early.  Suppress the warning.  */
2355               if (!by_ref)
2356                 TREE_NO_WARNING (var) = 1;
2357               break;
2358
2359             case OMP_CLAUSE_LASTPRIVATE:
2360               if (OMP_CLAUSE_LASTPRIVATE_FIRSTPRIVATE (c))
2361                 break;
2362               /* FALLTHRU */
2363
2364             case OMP_CLAUSE_PRIVATE:
2365               if (OMP_CLAUSE_CODE (c) != OMP_CLAUSE_PRIVATE)
2366                 x = build_outer_var_ref (var, ctx);
2367               else if (OMP_CLAUSE_PRIVATE_OUTER_REF (c))
2368                 {
2369                   if (is_task_ctx (ctx))
2370                     x = build_receiver_ref (var, false, ctx);
2371                   else
2372                     x = build_outer_var_ref (var, ctx);
2373                 }
2374               else
2375                 x = NULL;
2376               x = lang_hooks.decls.omp_clause_default_ctor (c, new_var, x);
2377               if (x)
2378                 gimplify_and_add (x, ilist);
2379               /* FALLTHRU */
2380
2381             do_dtor:
2382               x = lang_hooks.decls.omp_clause_dtor (c, new_var);
2383               if (x)
2384                 {
2385                   gimple_seq tseq = NULL;
2386
2387                   dtor = x;
2388                   gimplify_stmt (&dtor, &tseq);
2389                   gsi_insert_seq_before (&diter, tseq, GSI_SAME_STMT);
2390                 }
2391               break;
2392
2393             case OMP_CLAUSE_FIRSTPRIVATE:
2394               if (is_task_ctx (ctx))
2395                 {
2396                   if (is_reference (var) || is_variable_sized (var))
2397                     goto do_dtor;
2398                   else if (is_global_var (maybe_lookup_decl_in_outer_ctx (var,
2399                                                                           ctx))
2400                            || use_pointer_for_field (var, NULL))
2401                     {
2402                       x = build_receiver_ref (var, false, ctx);
2403                       SET_DECL_VALUE_EXPR (new_var, x);
2404                       DECL_HAS_VALUE_EXPR_P (new_var) = 1;
2405                       goto do_dtor;
2406                     }
2407                 }
2408               x = build_outer_var_ref (var, ctx);
2409               x = lang_hooks.decls.omp_clause_copy_ctor (c, new_var, x);
2410               gimplify_and_add (x, ilist);
2411               goto do_dtor;
2412               break;
2413
2414             case OMP_CLAUSE_COPYIN:
2415               by_ref = use_pointer_for_field (var, NULL);
2416               x = build_receiver_ref (var, by_ref, ctx);
2417               x = lang_hooks.decls.omp_clause_assign_op (c, new_var, x);
2418               append_to_statement_list (x, &copyin_seq);
2419               copyin_by_ref |= by_ref;
2420               break;
2421
2422             case OMP_CLAUSE_REDUCTION:
2423               if (OMP_CLAUSE_REDUCTION_PLACEHOLDER (c))
2424                 {
2425                   tree placeholder = OMP_CLAUSE_REDUCTION_PLACEHOLDER (c);
2426                   x = build_outer_var_ref (var, ctx);
2427
2428                   if (is_reference (var))
2429                     x = build_fold_addr_expr (x);
2430                   SET_DECL_VALUE_EXPR (placeholder, x);
2431                   DECL_HAS_VALUE_EXPR_P (placeholder) = 1;
2432                   lower_omp (OMP_CLAUSE_REDUCTION_GIMPLE_INIT (c), ctx);
2433                   gimple_seq_add_seq (ilist,
2434                                       OMP_CLAUSE_REDUCTION_GIMPLE_INIT (c));
2435                   OMP_CLAUSE_REDUCTION_GIMPLE_INIT (c) = NULL;
2436                   DECL_HAS_VALUE_EXPR_P (placeholder) = 0;
2437                 }
2438               else
2439                 {
2440                   x = omp_reduction_init (c, TREE_TYPE (new_var));
2441                   gcc_assert (TREE_CODE (TREE_TYPE (new_var)) != ARRAY_TYPE);
2442                   gimplify_assign (new_var, x, ilist);
2443                 }
2444               break;
2445
2446             default:
2447               gcc_unreachable ();
2448             }
2449         }
2450     }
2451
2452   /* The copyin sequence is not to be executed by the main thread, since
2453      that would result in self-copies.  Perhaps not visible to scalars,
2454      but it certainly is to C++ operator=.  */
2455   if (copyin_seq)
2456     {
2457       x = build_call_expr (built_in_decls[BUILT_IN_OMP_GET_THREAD_NUM], 0);
2458       x = build2 (NE_EXPR, boolean_type_node, x,
2459                   build_int_cst (TREE_TYPE (x), 0));
2460       x = build3 (COND_EXPR, void_type_node, x, copyin_seq, NULL);
2461       gimplify_and_add (x, ilist);
2462     }
2463
2464   /* If any copyin variable is passed by reference, we must ensure the
2465      master thread doesn't modify it before it is copied over in all
2466      threads.  Similarly for variables in both firstprivate and
2467      lastprivate clauses we need to ensure the lastprivate copying
2468      happens after firstprivate copying in all threads.  */
2469   if (copyin_by_ref || lastprivate_firstprivate)
2470     gimplify_and_add (build_omp_barrier (), ilist);
2471 }
2472
2473
2474 /* Generate code to implement the LASTPRIVATE clauses.  This is used for
2475    both parallel and workshare constructs.  PREDICATE may be NULL if it's
2476    always true.   */
2477
2478 static void
2479 lower_lastprivate_clauses (tree clauses, tree predicate, gimple_seq *stmt_list,
2480                             omp_context *ctx)
2481 {
2482   tree x, c, label = NULL;
2483   bool par_clauses = false;
2484
2485   /* Early exit if there are no lastprivate clauses.  */
2486   clauses = find_omp_clause (clauses, OMP_CLAUSE_LASTPRIVATE);
2487   if (clauses == NULL)
2488     {
2489       /* If this was a workshare clause, see if it had been combined
2490          with its parallel.  In that case, look for the clauses on the
2491          parallel statement itself.  */
2492       if (is_parallel_ctx (ctx))
2493         return;
2494
2495       ctx = ctx->outer;
2496       if (ctx == NULL || !is_parallel_ctx (ctx))
2497         return;
2498
2499       clauses = find_omp_clause (gimple_omp_parallel_clauses (ctx->stmt),
2500                                  OMP_CLAUSE_LASTPRIVATE);
2501       if (clauses == NULL)
2502         return;
2503       par_clauses = true;
2504     }
2505
2506   if (predicate)
2507     {
2508       gimple stmt;
2509       tree label_true, arm1, arm2;
2510
2511       label = create_artificial_label ();
2512       label_true = create_artificial_label ();
2513       arm1 = TREE_OPERAND (predicate, 0);
2514       arm2 = TREE_OPERAND (predicate, 1);
2515       gimplify_expr (&arm1, stmt_list, NULL, is_gimple_val, fb_rvalue);
2516       gimplify_expr (&arm2, stmt_list, NULL, is_gimple_val, fb_rvalue);
2517       stmt = gimple_build_cond (TREE_CODE (predicate), arm1, arm2,
2518                                 label_true, label);
2519       gimple_seq_add_stmt (stmt_list, stmt);
2520       gimple_seq_add_stmt (stmt_list, gimple_build_label (label_true));
2521     }
2522
2523   for (c = clauses; c ;)
2524     {
2525       tree var, new_var;
2526
2527       if (OMP_CLAUSE_CODE (c) == OMP_CLAUSE_LASTPRIVATE)
2528         {
2529           var = OMP_CLAUSE_DECL (c);
2530           new_var = lookup_decl (var, ctx);
2531
2532           if (OMP_CLAUSE_LASTPRIVATE_GIMPLE_SEQ (c))
2533             {
2534               lower_omp (OMP_CLAUSE_LASTPRIVATE_GIMPLE_SEQ (c), ctx);
2535               gimple_seq_add_seq (stmt_list,
2536                                   OMP_CLAUSE_LASTPRIVATE_GIMPLE_SEQ (c));
2537             }
2538           OMP_CLAUSE_LASTPRIVATE_GIMPLE_SEQ (c) = NULL;
2539
2540           x = build_outer_var_ref (var, ctx);
2541           if (is_reference (var))
2542             new_var = build_fold_indirect_ref (new_var);
2543           x = lang_hooks.decls.omp_clause_assign_op (c, x, new_var);
2544           gimplify_and_add (x, stmt_list);
2545         }
2546       c = OMP_CLAUSE_CHAIN (c);
2547       if (c == NULL && !par_clauses)
2548         {
2549           /* If this was a workshare clause, see if it had been combined
2550              with its parallel.  In that case, continue looking for the
2551              clauses also on the parallel statement itself.  */
2552           if (is_parallel_ctx (ctx))
2553             break;
2554
2555           ctx = ctx->outer;
2556           if (ctx == NULL || !is_parallel_ctx (ctx))
2557             break;
2558
2559           c = find_omp_clause (gimple_omp_parallel_clauses (ctx->stmt),
2560                                OMP_CLAUSE_LASTPRIVATE);
2561           par_clauses = true;
2562         }
2563     }
2564
2565   if (label)
2566     gimple_seq_add_stmt (stmt_list, gimple_build_label (label));
2567 }
2568
2569
2570 /* Generate code to implement the REDUCTION clauses.  */
2571
2572 static void
2573 lower_reduction_clauses (tree clauses, gimple_seq *stmt_seqp, omp_context *ctx)
2574 {
2575   gimple_seq sub_seq = NULL;
2576   gimple stmt;
2577   tree x, c;
2578   int count = 0;
2579
2580   /* First see if there is exactly one reduction clause.  Use OMP_ATOMIC
2581      update in that case, otherwise use a lock.  */
2582   for (c = clauses; c && count < 2; c = OMP_CLAUSE_CHAIN (c))
2583     if (OMP_CLAUSE_CODE (c) == OMP_CLAUSE_REDUCTION)
2584       {
2585         if (OMP_CLAUSE_REDUCTION_PLACEHOLDER (c))
2586           {
2587             /* Never use OMP_ATOMIC for array reductions.  */
2588             count = -1;
2589             break;
2590           }
2591         count++;
2592       }
2593
2594   if (count == 0)
2595     return;
2596
2597   for (c = clauses; c ; c = OMP_CLAUSE_CHAIN (c))
2598     {
2599       tree var, ref, new_var;
2600       enum tree_code code;
2601
2602       if (OMP_CLAUSE_CODE (c) != OMP_CLAUSE_REDUCTION)
2603         continue;
2604
2605       var = OMP_CLAUSE_DECL (c);
2606       new_var = lookup_decl (var, ctx);
2607       if (is_reference (var))
2608         new_var = build_fold_indirect_ref (new_var);
2609       ref = build_outer_var_ref (var, ctx);
2610       code = OMP_CLAUSE_REDUCTION_CODE (c);
2611
2612       /* reduction(-:var) sums up the partial results, so it acts
2613          identically to reduction(+:var).  */
2614       if (code == MINUS_EXPR)
2615         code = PLUS_EXPR;
2616
2617       if (count == 1)
2618         {
2619           tree addr = build_fold_addr_expr (ref);
2620
2621           addr = save_expr (addr);
2622           ref = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (addr)), addr);
2623           x = fold_build2 (code, TREE_TYPE (ref), ref, new_var);
2624           x = build2 (OMP_ATOMIC, void_type_node, addr, x);
2625           gimplify_and_add (x, stmt_seqp);
2626           return;
2627         }
2628
2629       if (OMP_CLAUSE_REDUCTION_PLACEHOLDER (c))
2630         {
2631           tree placeholder = OMP_CLAUSE_REDUCTION_PLACEHOLDER (c);
2632
2633           if (is_reference (var))
2634             ref = build_fold_addr_expr (ref);
2635           SET_DECL_VALUE_EXPR (placeholder, ref);
2636           DECL_HAS_VALUE_EXPR_P (placeholder) = 1;
2637           lower_omp (OMP_CLAUSE_REDUCTION_GIMPLE_MERGE (c), ctx);
2638           gimple_seq_add_seq (&sub_seq, OMP_CLAUSE_REDUCTION_GIMPLE_MERGE (c));
2639           OMP_CLAUSE_REDUCTION_GIMPLE_MERGE (c) = NULL;
2640           OMP_CLAUSE_REDUCTION_PLACEHOLDER (c) = NULL;
2641         }
2642       else
2643         {
2644           x = build2 (code, TREE_TYPE (ref), ref, new_var);
2645           ref = build_outer_var_ref (var, ctx);
2646           gimplify_assign (ref, x, &sub_seq);
2647         }
2648     }
2649
2650   stmt = gimple_build_call (built_in_decls[BUILT_IN_GOMP_ATOMIC_START], 0);
2651   gimple_seq_add_stmt (stmt_seqp, stmt);
2652
2653   gimple_seq_add_seq (stmt_seqp, sub_seq);
2654
2655   stmt = gimple_build_call (built_in_decls[BUILT_IN_GOMP_ATOMIC_END], 0);
2656   gimple_seq_add_stmt (stmt_seqp, stmt);
2657 }
2658
2659
2660 /* Generate code to implement the COPYPRIVATE clauses.  */
2661
2662 static void
2663 lower_copyprivate_clauses (tree clauses, gimple_seq *slist, gimple_seq *rlist,
2664                             omp_context *ctx)
2665 {
2666   tree c;
2667
2668   for (c = clauses; c ; c = OMP_CLAUSE_CHAIN (c))
2669     {
2670       tree var, new_var, ref, x;
2671       bool by_ref;
2672
2673       if (OMP_CLAUSE_CODE (c) != OMP_CLAUSE_COPYPRIVATE)
2674         continue;
2675
2676       var = OMP_CLAUSE_DECL (c);
2677       by_ref = use_pointer_for_field (var, NULL);
2678
2679       ref = build_sender_ref (var, ctx);
2680       x = new_var = lookup_decl_in_outer_ctx (var, ctx);
2681       if (by_ref)
2682         {
2683           x = build_fold_addr_expr (new_var);
2684           x = fold_convert (TREE_TYPE (ref), x);
2685         }
2686       gimplify_assign (ref, x, slist);
2687
2688       ref = build_receiver_ref (var, false, ctx);
2689       if (by_ref)
2690         {
2691           ref = fold_convert (build_pointer_type (TREE_TYPE (new_var)), ref);
2692           ref = build_fold_indirect_ref (ref);
2693         }
2694       if (is_reference (var))
2695         {
2696           ref = fold_convert (TREE_TYPE (new_var), ref);
2697           ref = build_fold_indirect_ref (ref);
2698           new_var = build_fold_indirect_ref (new_var);
2699         }
2700       x = lang_hooks.decls.omp_clause_assign_op (c, new_var, ref);
2701       gimplify_and_add (x, rlist);
2702     }
2703 }
2704
2705
2706 /* Generate code to implement the clauses, FIRSTPRIVATE, COPYIN, LASTPRIVATE,
2707    and REDUCTION from the sender (aka parent) side.  */
2708
2709 static void
2710 lower_send_clauses (tree clauses, gimple_seq *ilist, gimple_seq *olist,
2711                     omp_context *ctx)
2712 {
2713   tree c;
2714
2715   for (c = clauses; c ; c = OMP_CLAUSE_CHAIN (c))
2716     {
2717       tree val, ref, x, var;
2718       bool by_ref, do_in = false, do_out = false;
2719
2720       switch (OMP_CLAUSE_CODE (c))
2721         {
2722         case OMP_CLAUSE_PRIVATE:
2723           if (OMP_CLAUSE_PRIVATE_OUTER_REF (c))
2724             break;
2725           continue;
2726         case OMP_CLAUSE_FIRSTPRIVATE:
2727         case OMP_CLAUSE_COPYIN:
2728         case OMP_CLAUSE_LASTPRIVATE:
2729         case OMP_CLAUSE_REDUCTION:
2730           break;
2731         default:
2732           continue;
2733         }
2734
2735       val = OMP_CLAUSE_DECL (c);
2736       var = lookup_decl_in_outer_ctx (val, ctx);
2737
2738       if (OMP_CLAUSE_CODE (c) != OMP_CLAUSE_COPYIN
2739           && is_global_var (var))
2740         continue;
2741       if (is_variable_sized (val))
2742         continue;
2743       by_ref = use_pointer_for_field (val, NULL);
2744
2745       switch (OMP_CLAUSE_CODE (c))
2746         {
2747         case OMP_CLAUSE_PRIVATE:
2748         case OMP_CLAUSE_FIRSTPRIVATE:
2749         case OMP_CLAUSE_COPYIN:
2750           do_in = true;
2751           break;
2752
2753         case OMP_CLAUSE_LASTPRIVATE:
2754           if (by_ref || is_reference (val))
2755             {
2756               if (OMP_CLAUSE_LASTPRIVATE_FIRSTPRIVATE (c))
2757                 continue;
2758               do_in = true;
2759             }
2760           else
2761             {
2762               do_out = true;
2763               if (lang_hooks.decls.omp_private_outer_ref (val))
2764                 do_in = true;
2765             }
2766           break;
2767
2768         case OMP_CLAUSE_REDUCTION:
2769           do_in = true;
2770           do_out = !(by_ref || is_reference (val));
2771           break;
2772
2773         default:
2774           gcc_unreachable ();
2775         }
2776
2777       if (do_in)
2778         {
2779           ref = build_sender_ref (val, ctx);
2780           x = by_ref ? build_fold_addr_expr (var) : var;
2781           gimplify_assign (ref, x, ilist);
2782           if (is_task_ctx (ctx))
2783             DECL_ABSTRACT_ORIGIN (TREE_OPERAND (ref, 1)) = NULL;
2784         }
2785
2786       if (do_out)
2787         {
2788           ref = build_sender_ref (val, ctx);
2789           gimplify_assign (var, ref, olist);
2790         }
2791     }
2792 }
2793
2794 /* Generate code to implement SHARED from the sender (aka parent)
2795    side.  This is trickier, since GIMPLE_OMP_PARALLEL_CLAUSES doesn't
2796    list things that got automatically shared.  */
2797
2798 static void
2799 lower_send_shared_vars (gimple_seq *ilist, gimple_seq *olist, omp_context *ctx)
2800 {
2801   tree var, ovar, nvar, f, x, record_type;
2802
2803   if (ctx->record_type == NULL)
2804     return;
2805
2806   record_type = ctx->srecord_type ? ctx->srecord_type : ctx->record_type;
2807   for (f = TYPE_FIELDS (record_type); f ; f = TREE_CHAIN (f))
2808     {
2809       ovar = DECL_ABSTRACT_ORIGIN (f);
2810       nvar = maybe_lookup_decl (ovar, ctx);
2811       if (!nvar || !DECL_HAS_VALUE_EXPR_P (nvar))
2812         continue;
2813
2814       /* If CTX is a nested parallel directive.  Find the immediately
2815          enclosing parallel or workshare construct that contains a
2816          mapping for OVAR.  */
2817       var = lookup_decl_in_outer_ctx (ovar, ctx);
2818
2819       if (use_pointer_for_field (ovar, ctx))
2820         {
2821           x = build_sender_ref (ovar, ctx);
2822           var = build_fold_addr_expr (var);
2823           gimplify_assign (x, var, ilist);
2824         }
2825       else
2826         {
2827           x = build_sender_ref (ovar, ctx);
2828           gimplify_assign (x, var, ilist);
2829
2830           if (!TREE_READONLY (var)
2831               /* We don't need to receive a new reference to a result
2832                  or parm decl.  In fact we may not store to it as we will
2833                  invalidate any pending RSO and generate wrong gimple
2834                  during inlining.  */
2835               && !((TREE_CODE (var) == RESULT_DECL
2836                     || TREE_CODE (var) == PARM_DECL)
2837                    && DECL_BY_REFERENCE (var)))
2838             {
2839               x = build_sender_ref (ovar, ctx);
2840               gimplify_assign (var, x, olist);
2841             }
2842         }
2843     }
2844 }
2845
2846
2847 /* A convenience function to build an empty GIMPLE_COND with just the
2848    condition.  */
2849
2850 static gimple
2851 gimple_build_cond_empty (tree cond)
2852 {
2853   enum tree_code pred_code;
2854   tree lhs, rhs;
2855
2856   gimple_cond_get_ops_from_tree (cond, &pred_code, &lhs, &rhs);
2857   return gimple_build_cond (pred_code, lhs, rhs, NULL_TREE, NULL_TREE);
2858 }
2859
2860
2861 /* Build the function calls to GOMP_parallel_start etc to actually 
2862    generate the parallel operation.  REGION is the parallel region
2863    being expanded.  BB is the block where to insert the code.  WS_ARGS
2864    will be set if this is a call to a combined parallel+workshare
2865    construct, it contains the list of additional arguments needed by
2866    the workshare construct.  */
2867
2868 static void
2869 expand_parallel_call (struct omp_region *region, basic_block bb,
2870                       gimple entry_stmt, tree ws_args)
2871 {
2872   tree t, t1, t2, val, cond, c, clauses;
2873   gimple_stmt_iterator gsi;
2874   gimple stmt;
2875   int start_ix;
2876
2877   clauses = gimple_omp_parallel_clauses (entry_stmt);
2878
2879   /* Determine what flavor of GOMP_parallel_start we will be
2880      emitting.  */
2881   start_ix = BUILT_IN_GOMP_PARALLEL_START;
2882   if (is_combined_parallel (region))
2883     {
2884       switch (region->inner->type)
2885         {
2886         case GIMPLE_OMP_FOR:
2887           gcc_assert (region->inner->sched_kind != OMP_CLAUSE_SCHEDULE_AUTO);
2888           start_ix = BUILT_IN_GOMP_PARALLEL_LOOP_STATIC_START
2889                      + (region->inner->sched_kind
2890                         == OMP_CLAUSE_SCHEDULE_RUNTIME
2891                         ? 3 : region->inner->sched_kind);
2892           break;
2893         case GIMPLE_OMP_SECTIONS:
2894           start_ix = BUILT_IN_GOMP_PARALLEL_SECTIONS_START;
2895           break;
2896         default:
2897           gcc_unreachable ();
2898         }
2899     }
2900
2901   /* By default, the value of NUM_THREADS is zero (selected at run time)
2902      and there is no conditional.  */
2903   cond = NULL_TREE;
2904   val = build_int_cst (unsigned_type_node, 0);
2905
2906   c = find_omp_clause (clauses, OMP_CLAUSE_IF);
2907   if (c)
2908     cond = OMP_CLAUSE_IF_EXPR (c);
2909
2910   c = find_omp_clause (clauses, OMP_CLAUSE_NUM_THREADS);
2911   if (c)
2912     val = OMP_CLAUSE_NUM_THREADS_EXPR (c);
2913
2914   /* Ensure 'val' is of the correct type.  */
2915   val = fold_convert (unsigned_type_node, val);
2916
2917   /* If we found the clause 'if (cond)', build either
2918      (cond != 0) or (cond ? val : 1u).  */
2919   if (cond)
2920     {
2921       gimple_stmt_iterator gsi;
2922
2923       cond = gimple_boolify (cond);
2924
2925       if (integer_zerop (val))
2926         val = fold_build2 (EQ_EXPR, unsigned_type_node, cond,
2927                            build_int_cst (TREE_TYPE (cond), 0));
2928       else
2929         {
2930           basic_block cond_bb, then_bb, else_bb;
2931           edge e, e_then, e_else;
2932           tree tmp_then, tmp_else, tmp_join, tmp_var;
2933
2934           tmp_var = create_tmp_var (TREE_TYPE (val), NULL);
2935           if (gimple_in_ssa_p (cfun))
2936             {
2937               tmp_then = make_ssa_name (tmp_var, NULL);
2938               tmp_else = make_ssa_name (tmp_var, NULL);
2939               tmp_join = make_ssa_name (tmp_var, NULL);
2940             }
2941           else
2942             {
2943               tmp_then = tmp_var;
2944               tmp_else = tmp_var;
2945               tmp_join = tmp_var;
2946             }
2947
2948           e = split_block (bb, NULL);
2949           cond_bb = e->src;
2950           bb = e->dest;
2951           remove_edge (e);
2952
2953           then_bb = create_empty_bb (cond_bb);
2954           else_bb = create_empty_bb (then_bb);
2955           set_immediate_dominator (CDI_DOMINATORS, then_bb, cond_bb);
2956           set_immediate_dominator (CDI_DOMINATORS, else_bb, cond_bb);
2957
2958           stmt = gimple_build_cond_empty (cond);
2959           gsi = gsi_start_bb (cond_bb);
2960           gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
2961
2962           gsi = gsi_start_bb (then_bb);
2963           stmt = gimple_build_assign (tmp_then, val);
2964           gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
2965
2966           gsi = gsi_start_bb (else_bb);
2967           stmt = gimple_build_assign
2968                    (tmp_else, build_int_cst (unsigned_type_node, 1));
2969           gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
2970
2971           make_edge (cond_bb, then_bb, EDGE_TRUE_VALUE);
2972           make_edge (cond_bb, else_bb, EDGE_FALSE_VALUE);
2973           e_then = make_edge (then_bb, bb, EDGE_FALLTHRU);
2974           e_else = make_edge (else_bb, bb, EDGE_FALLTHRU);
2975
2976           if (gimple_in_ssa_p (cfun))
2977             {
2978               gimple phi = create_phi_node (tmp_join, bb);
2979               SSA_NAME_DEF_STMT (tmp_join) = phi;
2980               add_phi_arg (phi, tmp_then, e_then);
2981               add_phi_arg (phi, tmp_else, e_else);
2982             }
2983
2984           val = tmp_join;
2985         }
2986
2987       gsi = gsi_start_bb (bb);
2988       val = force_gimple_operand_gsi (&gsi, val, true, NULL_TREE,
2989                                       false, GSI_CONTINUE_LINKING);
2990     }
2991
2992   gsi = gsi_last_bb (bb);
2993   t = gimple_omp_parallel_data_arg (entry_stmt);
2994   if (t == NULL)
2995     t1 = null_pointer_node;
2996   else
2997     t1 = build_fold_addr_expr (t);
2998   t2 = build_fold_addr_expr (gimple_omp_parallel_child_fn (entry_stmt));
2999
3000   if (ws_args)
3001     {
3002       tree args = tree_cons (NULL, t2,
3003                              tree_cons (NULL, t1,
3004                                         tree_cons (NULL, val, ws_args)));
3005       t = build_function_call_expr (built_in_decls[start_ix], args);
3006     }
3007   else
3008     t = build_call_expr (built_in_decls[start_ix], 3, t2, t1, val);
3009
3010   force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
3011                             false, GSI_CONTINUE_LINKING);
3012
3013   t = gimple_omp_parallel_data_arg (entry_stmt);
3014   if (t == NULL)
3015     t = null_pointer_node;
3016   else
3017     t = build_fold_addr_expr (t);
3018   t = build_call_expr (gimple_omp_parallel_child_fn (entry_stmt), 1, t);
3019   force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
3020                             false, GSI_CONTINUE_LINKING);
3021
3022   t = build_call_expr (built_in_decls[BUILT_IN_GOMP_PARALLEL_END], 0);
3023   force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
3024                             false, GSI_CONTINUE_LINKING);
3025 }
3026
3027
3028 /* Build the function call to GOMP_task to actually
3029    generate the task operation.  BB is the block where to insert the code.  */
3030
3031 static void
3032 expand_task_call (basic_block bb, gimple entry_stmt)
3033 {
3034   tree t, t1, t2, t3, flags, cond, c, clauses;
3035   gimple_stmt_iterator gsi;
3036
3037   clauses = gimple_omp_task_clauses (entry_stmt);
3038
3039   c = find_omp_clause (clauses, OMP_CLAUSE_IF);
3040   if (c)
3041     cond = gimple_boolify (OMP_CLAUSE_IF_EXPR (c));
3042   else
3043     cond = boolean_true_node;
3044
3045   c = find_omp_clause (clauses, OMP_CLAUSE_UNTIED);
3046   flags = build_int_cst (unsigned_type_node, (c ? 1 : 0));
3047
3048   gsi = gsi_last_bb (bb);
3049   t = gimple_omp_task_data_arg (entry_stmt);
3050   if (t == NULL)
3051     t2 = null_pointer_node;
3052   else
3053     t2 = build_fold_addr_expr (t);
3054   t1 = build_fold_addr_expr (gimple_omp_task_child_fn (entry_stmt));
3055   t = gimple_omp_task_copy_fn (entry_stmt);
3056   if (t == NULL)
3057     t3 = null_pointer_node;
3058   else
3059     t3 = build_fold_addr_expr (t);
3060
3061   t = build_call_expr (built_in_decls[BUILT_IN_GOMP_TASK], 7, t1, t2, t3,
3062                        gimple_omp_task_arg_size (entry_stmt),
3063                        gimple_omp_task_arg_align (entry_stmt), cond, flags);
3064
3065   force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
3066                             false, GSI_CONTINUE_LINKING);
3067 }
3068
3069
3070 /* If exceptions are enabled, wrap the statements in BODY in a MUST_NOT_THROW
3071    catch handler and return it.  This prevents programs from violating the
3072    structured block semantics with throws.  */
3073
3074 static gimple_seq
3075 maybe_catch_exception (gimple_seq body)
3076 {
3077   gimple f, t;
3078
3079   if (!flag_exceptions)
3080     return body;
3081
3082   if (lang_protect_cleanup_actions)
3083     t = lang_protect_cleanup_actions ();
3084   else
3085     t = gimple_build_call (built_in_decls[BUILT_IN_TRAP], 0);
3086
3087   f = gimple_build_eh_filter (NULL, gimple_seq_alloc_with_stmt (t));
3088   gimple_eh_filter_set_must_not_throw (f, true);
3089
3090   t = gimple_build_try (body, gimple_seq_alloc_with_stmt (f),
3091                         GIMPLE_TRY_CATCH);
3092
3093  return gimple_seq_alloc_with_stmt (t);
3094 }
3095
3096 /* Chain all the DECLs in LIST by their TREE_CHAIN fields.  */
3097
3098 static tree
3099 list2chain (tree list)
3100 {
3101   tree t;
3102
3103   for (t = list; t; t = TREE_CHAIN (t))
3104     {
3105       tree var = TREE_VALUE (t);
3106       if (TREE_CHAIN (t))
3107         TREE_CHAIN (var) = TREE_VALUE (TREE_CHAIN (t));
3108       else
3109         TREE_CHAIN (var) = NULL_TREE;
3110     }
3111
3112   return list ? TREE_VALUE (list) : NULL_TREE;
3113 }
3114
3115
3116 /* Remove barriers in REGION->EXIT's block.  Note that this is only
3117    valid for GIMPLE_OMP_PARALLEL regions.  Since the end of a parallel region
3118    is an implicit barrier, any workshare inside the GIMPLE_OMP_PARALLEL that
3119    left a barrier at the end of the GIMPLE_OMP_PARALLEL region can now be
3120    removed.  */
3121
3122 static void
3123 remove_exit_barrier (struct omp_region *region)
3124 {
3125   gimple_stmt_iterator gsi;
3126   basic_block exit_bb;
3127   edge_iterator ei;
3128   edge e;
3129   gimple stmt;
3130   int any_addressable_vars = -1;
3131
3132   exit_bb = region->exit;
3133
3134   /* If the parallel region doesn't return, we don't have REGION->EXIT
3135      block at all.  */
3136   if (! exit_bb)
3137     return;
3138
3139   /* The last insn in the block will be the parallel's GIMPLE_OMP_RETURN.  The
3140      workshare's GIMPLE_OMP_RETURN will be in a preceding block.  The kinds of
3141      statements that can appear in between are extremely limited -- no
3142      memory operations at all.  Here, we allow nothing at all, so the
3143      only thing we allow to precede this GIMPLE_OMP_RETURN is a label.  */
3144   gsi = gsi_last_bb (exit_bb);
3145   gcc_assert (gimple_code (gsi_stmt (gsi)) == GIMPLE_OMP_RETURN);
3146   gsi_prev (&gsi);
3147   if (!gsi_end_p (gsi) && gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
3148     return;
3149
3150   FOR_EACH_EDGE (e, ei, exit_bb->preds)
3151     {
3152       gsi = gsi_last_bb (e->src);
3153       if (gsi_end_p (gsi))
3154         continue;
3155       stmt = gsi_stmt (gsi);
3156       if (gimple_code (stmt) == GIMPLE_OMP_RETURN
3157           && !gimple_omp_return_nowait_p (stmt))
3158         {
3159           /* OpenMP 3.0 tasks unfortunately prevent this optimization
3160              in many cases.  If there could be tasks queued, the barrier
3161              might be needed to let the tasks run before some local
3162              variable of the parallel that the task uses as shared
3163              runs out of scope.  The task can be spawned either
3164              from within current function (this would be easy to check)
3165              or from some function it calls and gets passed an address
3166              of such a variable.  */
3167           if (any_addressable_vars < 0)
3168             {
3169               gimple parallel_stmt = last_stmt (region->entry);
3170               tree child_fun = gimple_omp_parallel_child_fn (parallel_stmt);
3171               tree local_decls = DECL_STRUCT_FUNCTION (child_fun)->local_decls;
3172               tree block;
3173
3174               any_addressable_vars = 0;
3175               for (; local_decls; local_decls = TREE_CHAIN (local_decls))
3176                 if (TREE_ADDRESSABLE (TREE_VALUE (local_decls)))
3177                   {
3178                     any_addressable_vars = 1;
3179                     break;
3180                   }
3181               for (block = gimple_block (stmt);
3182                    !any_addressable_vars
3183                    && block
3184                    && TREE_CODE (block) == BLOCK;
3185                    block = BLOCK_SUPERCONTEXT (block))
3186                 {
3187                   for (local_decls = BLOCK_VARS (block);
3188                        local_decls;
3189                        local_decls = TREE_CHAIN (local_decls))
3190                     if (TREE_ADDRESSABLE (local_decls))
3191                       {
3192                         any_addressable_vars = 1;
3193                         break;
3194                       }
3195                   if (block == gimple_block (parallel_stmt))
3196                     break;
3197                 }
3198             }
3199           if (!any_addressable_vars)
3200             gimple_omp_return_set_nowait (stmt);
3201         }
3202     }
3203 }
3204
3205 static void
3206 remove_exit_barriers (struct omp_region *region)
3207 {
3208   if (region->type == GIMPLE_OMP_PARALLEL)
3209     remove_exit_barrier (region);
3210
3211   if (region->inner)
3212     {
3213       region = region->inner;
3214       remove_exit_barriers (region);
3215       while (region->next)
3216         {
3217           region = region->next;
3218           remove_exit_barriers (region);
3219         }
3220     }
3221 }
3222
3223 /* Optimize omp_get_thread_num () and omp_get_num_threads ()
3224    calls.  These can't be declared as const functions, but
3225    within one parallel body they are constant, so they can be
3226    transformed there into __builtin_omp_get_{thread_num,num_threads} ()
3227    which are declared const.  Similarly for task body, except
3228    that in untied task omp_get_thread_num () can change at any task
3229    scheduling point.  */
3230
3231 static void
3232 optimize_omp_library_calls (gimple entry_stmt)
3233 {
3234   basic_block bb;
3235   gimple_stmt_iterator gsi;
3236   tree thr_num_id
3237     = DECL_ASSEMBLER_NAME (built_in_decls [BUILT_IN_OMP_GET_THREAD_NUM]);
3238   tree num_thr_id
3239     = DECL_ASSEMBLER_NAME (built_in_decls [BUILT_IN_OMP_GET_NUM_THREADS]);
3240   bool untied_task = (gimple_code (entry_stmt) == GIMPLE_OMP_TASK
3241                       && find_omp_clause (gimple_omp_task_clauses (entry_stmt),
3242                                           OMP_CLAUSE_UNTIED) != NULL);
3243
3244   FOR_EACH_BB (bb)
3245     for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3246       {
3247         gimple call = gsi_stmt (gsi);
3248         tree decl;
3249
3250         if (is_gimple_call (call)
3251             && (decl = gimple_call_fndecl (call))
3252             && DECL_EXTERNAL (decl)
3253             && TREE_PUBLIC (decl)
3254             && DECL_INITIAL (decl) == NULL)
3255           {
3256             tree built_in;
3257
3258             if (DECL_NAME (decl) == thr_num_id)
3259               {
3260                 /* In #pragma omp task untied omp_get_thread_num () can change
3261                    during the execution of the task region.  */
3262                 if (untied_task)
3263                   continue;
3264                 built_in = built_in_decls [BUILT_IN_OMP_GET_THREAD_NUM];
3265               }
3266             else if (DECL_NAME (decl) == num_thr_id)
3267               built_in = built_in_decls [BUILT_IN_OMP_GET_NUM_THREADS];
3268             else
3269               continue;
3270
3271             if (DECL_ASSEMBLER_NAME (decl) != DECL_ASSEMBLER_NAME (built_in)
3272                 || gimple_call_num_args (call) != 0)
3273               continue;
3274
3275             if (flag_exceptions && !TREE_NOTHROW (decl))
3276               continue;
3277
3278             if (TREE_CODE (TREE_TYPE (decl)) != FUNCTION_TYPE
3279                 || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (decl)))
3280                    != TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (built_in))))
3281               continue;
3282
3283             gimple_call_set_fndecl (call, built_in);
3284           }
3285       }
3286 }
3287
3288 /* Expand the OpenMP parallel or task directive starting at REGION.  */
3289
3290 static void
3291 expand_omp_taskreg (struct omp_region *region)
3292 {
3293   basic_block entry_bb, exit_bb, new_bb;
3294   struct function *child_cfun;
3295   tree child_fn, block, t, ws_args, *tp;
3296   gimple_stmt_iterator gsi;
3297   gimple entry_stmt, stmt;
3298   edge e;
3299
3300   entry_stmt = last_stmt (region->entry);
3301   child_fn = gimple_omp_taskreg_child_fn (entry_stmt);
3302   child_cfun = DECL_STRUCT_FUNCTION (child_fn);
3303   /* If this function has been already instrumented, make sure
3304      the child function isn't instrumented again.  */
3305   child_cfun->after_tree_profile = cfun->after_tree_profile;
3306
3307   entry_bb = region->entry;
3308   exit_bb = region->exit;
3309
3310   if (is_combined_parallel (region))
3311     ws_args = region->ws_args;
3312   else
3313     ws_args = NULL_TREE;
3314
3315   if (child_cfun->cfg)
3316     {
3317       /* Due to inlining, it may happen that we have already outlined
3318          the region, in which case all we need to do is make the
3319          sub-graph unreachable and emit the parallel call.  */
3320       edge entry_succ_e, exit_succ_e;
3321       gimple_stmt_iterator gsi;
3322
3323       entry_succ_e = single_succ_edge (entry_bb);
3324
3325       gsi = gsi_last_bb (entry_bb);
3326       gcc_assert (gimple_code (gsi_stmt (gsi)) == GIMPLE_OMP_PARALLEL
3327                   || gimple_code (gsi_stmt (gsi)) == GIMPLE_OMP_TASK);
3328       gsi_remove (&gsi, true);
3329
3330       new_bb = entry_bb;
3331       if (exit_bb)
3332         {
3333           exit_succ_e = single_succ_edge (exit_bb);
3334           make_edge (new_bb, exit_succ_e->dest, EDGE_FALLTHRU);
3335         }
3336       remove_edge_and_dominated_blocks (entry_succ_e);
3337     }
3338   else
3339     {
3340       /* If the parallel region needs data sent from the parent
3341          function, then the very first statement (except possible
3342          tree profile counter updates) of the parallel body
3343          is a copy assignment .OMP_DATA_I = &.OMP_DATA_O.  Since
3344          &.OMP_DATA_O is passed as an argument to the child function,
3345          we need to replace it with the argument as seen by the child
3346          function.
3347
3348          In most cases, this will end up being the identity assignment
3349          .OMP_DATA_I = .OMP_DATA_I.  However, if the parallel body had
3350          a function call that has been inlined, the original PARM_DECL
3351          .OMP_DATA_I may have been converted into a different local
3352          variable.  In which case, we need to keep the assignment.  */
3353       if (gimple_omp_taskreg_data_arg (entry_stmt))
3354         {
3355           basic_block entry_succ_bb = single_succ (entry_bb);
3356           gimple_stmt_iterator gsi;
3357           tree arg, narg;
3358           gimple parcopy_stmt = NULL;
3359
3360           for (gsi = gsi_start_bb (entry_succ_bb); ; gsi_next (&gsi))
3361             {
3362               gimple stmt;
3363
3364               gcc_assert (!gsi_end_p (gsi));
3365               stmt = gsi_stmt (gsi);
3366               if (gimple_code (stmt) != GIMPLE_ASSIGN)
3367                 continue;
3368
3369               if (gimple_num_ops (stmt) == 2)
3370                 {
3371                   tree arg = gimple_assign_rhs1 (stmt);
3372
3373                   /* We're ignore the subcode because we're
3374                      effectively doing a STRIP_NOPS.  */
3375
3376                   if (TREE_CODE (arg) == ADDR_EXPR
3377                       && TREE_OPERAND (arg, 0)
3378                         == gimple_omp_taskreg_data_arg (entry_stmt))
3379                     {
3380                       parcopy_stmt = stmt;
3381                       break;
3382                     }
3383                 }
3384             }
3385
3386           gcc_assert (parcopy_stmt != NULL);
3387           arg = DECL_ARGUMENTS (child_fn);
3388
3389           if (!gimple_in_ssa_p (cfun))
3390             {
3391               if (gimple_assign_lhs (parcopy_stmt) == arg)
3392                 gsi_remove (&gsi, true);
3393               else
3394                 {
3395                   /* ?? Is setting the subcode really necessary ??  */
3396                   gimple_omp_set_subcode (parcopy_stmt, TREE_CODE (arg));
3397                   gimple_assign_set_rhs1 (parcopy_stmt, arg);
3398                 }
3399             }
3400           else
3401             {
3402               /* If we are in ssa form, we must load the value from the default
3403                  definition of the argument.  That should not be defined now,
3404                  since the argument is not used uninitialized.  */
3405               gcc_assert (gimple_default_def (cfun, arg) == NULL);
3406               narg = make_ssa_name (arg, gimple_build_nop ());
3407               set_default_def (arg, narg);
3408               /* ?? Is setting the subcode really necessary ??  */
3409               gimple_omp_set_subcode (parcopy_stmt, TREE_CODE (narg));
3410               gimple_assign_set_rhs1 (parcopy_stmt, narg);
3411               update_stmt (parcopy_stmt);
3412             }
3413         }
3414
3415       /* Declare local variables needed in CHILD_CFUN.  */
3416       block = DECL_INITIAL (child_fn);
3417       BLOCK_VARS (block) = list2chain (child_cfun->local_decls);
3418       /* The gimplifier could record temporaries in parallel/task block
3419          rather than in containing function's local_decls chain,
3420          which would mean cgraph missed finalizing them.  Do it now.  */
3421       for (t = BLOCK_VARS (block); t; t = TREE_CHAIN (t))
3422         if (TREE_CODE (t) == VAR_DECL
3423             && TREE_STATIC (t)
3424             && !DECL_EXTERNAL (t))
3425           varpool_finalize_decl (t);
3426       DECL_SAVED_TREE (child_fn) = NULL;
3427       gimple_set_body (child_fn, bb_seq (single_succ (entry_bb)));
3428       TREE_USED (block) = 1;
3429
3430       /* Reset DECL_CONTEXT on function arguments.  */
3431       for (t = DECL_ARGUMENTS (child_fn); t; t = TREE_CHAIN (t))
3432         DECL_CONTEXT (t) = child_fn;
3433
3434       /* Split ENTRY_BB at GIMPLE_OMP_PARALLEL or GIMPLE_OMP_TASK,
3435          so that it can be moved to the child function.  */
3436       gsi = gsi_last_bb (entry_bb);
3437       stmt = gsi_stmt (gsi);
3438       gcc_assert (stmt && (gimple_code (stmt) == GIMPLE_OMP_PARALLEL
3439                            || gimple_code (stmt) == GIMPLE_OMP_TASK));
3440       gsi_remove (&gsi, true);
3441       e = split_block (entry_bb, stmt);
3442       entry_bb = e->dest;
3443       single_succ_edge (entry_bb)->flags = EDGE_FALLTHRU;
3444
3445       /* Convert GIMPLE_OMP_RETURN into a RETURN_EXPR.  */
3446       if (exit_bb)
3447         {
3448           gsi = gsi_last_bb (exit_bb);
3449           gcc_assert (!gsi_end_p (gsi)
3450                       && gimple_code (gsi_stmt (gsi)) == GIMPLE_OMP_RETURN);
3451           stmt = gimple_build_return (NULL);
3452           gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
3453           gsi_remove (&gsi, true);
3454         }
3455
3456       /* Move the parallel region into CHILD_CFUN.  */
3457  
3458       if (gimple_in_ssa_p (cfun))
3459         {
3460           push_cfun (child_cfun);
3461           init_tree_ssa (child_cfun);
3462           init_ssa_operands ();
3463           cfun->gimple_df->in_ssa_p = true;
3464           pop_cfun ();
3465           block = NULL_TREE;
3466         }
3467       else
3468         block = gimple_block (entry_stmt);
3469
3470       new_bb = move_sese_region_to_fn (child_cfun, entry_bb, exit_bb, block);
3471       if (exit_bb)
3472         single_succ_edge (new_bb)->flags = EDGE_FALLTHRU;
3473
3474       /* Remove non-local VAR_DECLs from child_cfun->local_decls list.  */
3475       for (tp = &child_cfun->local_decls; *tp; )
3476         if (DECL_CONTEXT (TREE_VALUE (*tp)) != cfun->decl)
3477           tp = &TREE_CHAIN (*tp);
3478         else
3479           *tp = TREE_CHAIN (*tp);
3480
3481       /* Inform the callgraph about the new function.  */
3482       DECL_STRUCT_FUNCTION (child_fn)->curr_properties
3483         = cfun->curr_properties;
3484       cgraph_add_new_function (child_fn, true);
3485
3486       /* Fix the callgraph edges for child_cfun.  Those for cfun will be
3487          fixed in a following pass.  */
3488       push_cfun (child_cfun);
3489       if (optimize)
3490         optimize_omp_library_calls (entry_stmt);
3491       rebuild_cgraph_edges ();
3492
3493       /* Some EH regions might become dead, see PR34608.  If
3494          pass_cleanup_cfg isn't the first pass to happen with the
3495          new child, these dead EH edges might cause problems.
3496          Clean them up now.  */
3497       if (flag_exceptions)
3498         {
3499           basic_block bb;
3500           tree save_current = current_function_decl;
3501           bool changed = false;
3502
3503           current_function_decl = child_fn;
3504           FOR_EACH_BB (bb)
3505             changed |= gimple_purge_dead_eh_edges (bb);
3506           if (changed)
3507             cleanup_tree_cfg ();
3508           current_function_decl = save_current;
3509         }
3510       pop_cfun ();
3511     }
3512   
3513   /* Emit a library call to launch the children threads.  */
3514   if (gimple_code (entry_stmt) == GIMPLE_OMP_PARALLEL)
3515     expand_parallel_call (region, new_bb, entry_stmt, ws_args);
3516   else
3517     expand_task_call (new_bb, entry_stmt);
3518   update_ssa (TODO_update_ssa_only_virtuals);
3519 }
3520
3521
3522 /* A subroutine of expand_omp_for.  Generate code for a parallel
3523    loop with any schedule.  Given parameters:
3524
3525         for (V = N1; V cond N2; V += STEP) BODY;
3526
3527    where COND is "<" or ">", we generate pseudocode
3528
3529         more = GOMP_loop_foo_start (N1, N2, STEP, CHUNK, &istart0, &iend0);
3530         if (more) goto L0; else goto L3;
3531     L0:
3532         V = istart0;
3533         iend = iend0;
3534     L1:
3535         BODY;
3536         V += STEP;
3537         if (V cond iend) goto L1; else goto L2;
3538     L2:
3539         if (GOMP_loop_foo_next (&istart0, &iend0)) goto L0; else goto L3;
3540     L3:
3541
3542     If this is a combined omp parallel loop, instead of the call to
3543     GOMP_loop_foo_start, we call GOMP_loop_foo_next.
3544
3545     For collapsed loops, given parameters:
3546       collapse(3)
3547       for (V1 = N11; V1 cond1 N12; V1 += STEP1)
3548         for (V2 = N21; V2 cond2 N22; V2 += STEP2)
3549           for (V3 = N31; V3 cond3 N32; V3 += STEP3)
3550             BODY;
3551
3552     we generate pseudocode
3553
3554         if (cond3 is <)
3555           adj = STEP3 - 1;
3556         else
3557           adj = STEP3 + 1;
3558         count3 = (adj + N32 - N31) / STEP3;
3559         if (cond2 is <)
3560           adj = STEP2 - 1;
3561         else
3562           adj = STEP2 + 1;
3563         count2 = (adj + N22 - N21) / STEP2;
3564         if (cond1 is <)
3565           adj = STEP1 - 1;
3566         else
3567           adj = STEP1 + 1;
3568         count1 = (adj + N12 - N11) / STEP1;
3569         count = count1 * count2 * count3;
3570         more = GOMP_loop_foo_start (0, count, 1, CHUNK, &istart0, &iend0);
3571         if (more) goto L0; else goto L3;
3572     L0:
3573         V = istart0;
3574         T = V;
3575         V3 = N31 + (T % count3) * STEP3;
3576         T = T / count3;
3577         V2 = N21 + (T % count2) * STEP2;
3578         T = T / count2;
3579         V1 = N11 + T * STEP1;
3580         iend = iend0;
3581     L1:
3582         BODY;
3583         V += 1;
3584         if (V < iend) goto L10; else goto L2;
3585     L10:
3586         V3 += STEP3;
3587         if (V3 cond3 N32) goto L1; else goto L11;
3588     L11:
3589         V3 = N31;
3590         V2 += STEP2;
3591         if (V2 cond2 N22) goto L1; else goto L12;
3592     L12:
3593         V2 = N21;
3594         V1 += STEP1;
3595         goto L1;
3596     L2:
3597         if (GOMP_loop_foo_next (&istart0, &iend0)) goto L0; else goto L3;
3598     L3:
3599
3600       */
3601
3602 static void
3603 expand_omp_for_generic (struct omp_region *region,
3604                         struct omp_for_data *fd,
3605                         enum built_in_function start_fn,
3606                         enum built_in_function next_fn)
3607 {
3608   tree type, istart0, iend0, iend;
3609   tree t, vmain, vback, bias = NULL_TREE;
3610   basic_block entry_bb, cont_bb, exit_bb, l0_bb, l1_bb, collapse_bb;
3611   basic_block l2_bb = NULL, l3_bb = NULL;
3612   gimple_stmt_iterator gsi;
3613   gimple stmt;
3614   bool in_combined_parallel = is_combined_parallel (region);
3615   bool broken_loop = region->cont == NULL;
3616   edge e, ne;
3617   tree *counts = NULL;
3618   int i;
3619
3620   gcc_assert (!broken_loop || !in_combined_parallel);
3621   gcc_assert (fd->iter_type == long_integer_type_node
3622               || !in_combined_parallel);
3623
3624   type = TREE_TYPE (fd->loop.v);
3625   istart0 = create_tmp_var (fd->iter_type, ".istart0");
3626   iend0 = create_tmp_var (fd->iter_type, ".iend0");
3627   TREE_ADDRESSABLE (istart0) = 1;
3628   TREE_ADDRESSABLE (iend0) = 1;
3629   if (gimple_in_ssa_p (cfun))
3630     {
3631       add_referenced_var (istart0);
3632       add_referenced_var (iend0);
3633     }
3634
3635   /* See if we need to bias by LLONG_MIN.  */
3636   if (fd->iter_type == long_long_unsigned_type_node
3637       && TREE_CODE (type) == INTEGER_TYPE
3638       && !TYPE_UNSIGNED (type))
3639     {
3640       tree n1, n2;
3641
3642       if (fd->loop.cond_code == LT_EXPR)
3643         {
3644           n1 = fd->loop.n1;
3645           n2 = fold_build2 (PLUS_EXPR, type, fd->loop.n2, fd->loop.step);
3646         }
3647       else
3648         {
3649           n1 = fold_build2 (MINUS_EXPR, type, fd->loop.n2, fd->loop.step);
3650           n2 = fd->loop.n1;
3651         }
3652       if (TREE_CODE (n1) != INTEGER_CST
3653           || TREE_CODE (n2) != INTEGER_CST
3654           || ((tree_int_cst_sgn (n1) < 0) ^ (tree_int_cst_sgn (n2) < 0)))
3655         bias = fold_convert (fd->iter_type, TYPE_MIN_VALUE (type));
3656     }
3657
3658   entry_bb = region->entry;
3659   cont_bb = region->cont;
3660   collapse_bb = NULL;
3661   gcc_assert (EDGE_COUNT (entry_bb->succs) == 2);
3662   gcc_assert (broken_loop
3663               || BRANCH_EDGE (entry_bb)->dest == FALLTHRU_EDGE (cont_bb)->dest);
3664   l0_bb = split_edge (FALLTHRU_EDGE (entry_bb));
3665   l1_bb = single_succ (l0_bb);
3666   if (!broken_loop)
3667     {
3668       l2_bb = create_empty_bb (cont_bb);
3669       gcc_assert (BRANCH_EDGE (cont_bb)->dest == l1_bb);
3670       gcc_assert (EDGE_COUNT (cont_bb->succs) == 2);
3671     }
3672   else
3673     l2_bb = NULL;
3674   l3_bb = BRANCH_EDGE (entry_bb)->dest;
3675   exit_bb = region->exit;
3676
3677   gsi = gsi_last_bb (entry_bb);
3678
3679   gcc_assert (gimple_code (gsi_stmt (gsi)) == GIMPLE_OMP_FOR);
3680   if (fd->collapse > 1)
3681     {
3682       /* collapsed loops need work for expansion in SSA form.  */
3683       gcc_assert (!gimple_in_ssa_p (cfun));
3684       counts = (tree *) alloca (fd->collapse * sizeof (tree));
3685       for (i = 0; i < fd->collapse; i++)
3686         {
3687           tree itype = TREE_TYPE (fd->loops[i].v);
3688
3689           if (POINTER_TYPE_P (itype))
3690             itype = lang_hooks.types.type_for_size (TYPE_PRECISION (itype), 0);
3691           t = build_int_cst (itype, (fd->loops[i].cond_code == LT_EXPR
3692                                      ? -1 : 1));
3693           t = fold_build2 (PLUS_EXPR, itype,
3694                            fold_convert (itype, fd->loops[i].step), t);
3695           t = fold_build2 (PLUS_EXPR, itype, t,
3696                            fold_convert (itype, fd->loops[i].n2));
3697           t = fold_build2 (MINUS_EXPR, itype, t,
3698                            fold_convert (itype, fd->loops[i].n1));
3699           if (TYPE_UNSIGNED (itype) && fd->loops[i].cond_code == GT_EXPR)
3700             t = fold_build2 (TRUNC_DIV_EXPR, itype,
3701                              fold_build1 (NEGATE_EXPR, itype, t),
3702                              fold_build1 (NEGATE_EXPR, itype,
3703                                           fold_convert (itype,
3704                                                         fd->loops[i].step)));
3705           else
3706             t = fold_build2 (TRUNC_DIV_EXPR, itype, t,
3707                              fold_convert (itype, fd->loops[i].step));
3708           t = fold_convert (type, t);
3709           if (TREE_CODE (t) == INTEGER_CST)
3710             counts[i] = t;
3711           else
3712             {
3713               counts[i] = create_tmp_var (type, ".count");
3714               t = force_gimple_operand_gsi (&gsi, t, false, NULL_TREE,
3715                                             true, GSI_SAME_STMT);
3716               stmt = gimple_build_assign (counts[i], t);
3717               gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
3718             }
3719           if (SSA_VAR_P (fd->loop.n2))
3720             {
3721               if (i == 0)
3722                 t = counts[0];
3723               else
3724                 {
3725                   t = fold_build2 (MULT_EXPR, type, fd->loop.n2, counts[i]);
3726                   t = force_gimple_operand_gsi (&gsi, t, false, NULL_TREE,
3727                                                 true, GSI_SAME_STMT);
3728                 }
3729               stmt = gimple_build_assign (fd->loop.n2, t);
3730               gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
3731             }
3732         }
3733     }
3734   if (in_combined_parallel)
3735     {
3736       /* In a combined parallel loop, emit a call to
3737          GOMP_loop_foo_next.  */
3738       t = build_call_expr (built_in_decls[next_fn], 2,
3739                            build_fold_addr_expr (istart0),
3740                            build_fold_addr_expr (iend0));
3741     }
3742   else
3743     {
3744       tree t0, t1, t2, t3, t4;
3745       /* If this is not a combined parallel loop, emit a call to
3746          GOMP_loop_foo_start in ENTRY_BB.  */
3747       t4 = build_fold_addr_expr (iend0);
3748       t3 = build_fold_addr_expr (istart0);
3749       t2 = fold_convert (fd->iter_type, fd->loop.step);
3750       if (POINTER_TYPE_P (type)
3751           && TYPE_PRECISION (type) != TYPE_PRECISION (fd->iter_type))
3752         {
3753           /* Avoid casting pointers to integer of a different size.  */
3754           tree itype
3755             = lang_hooks.types.type_for_size (TYPE_PRECISION (type), 0);
3756           t1 = fold_convert (fd->iter_type, fold_convert (itype, fd->loop.n2));
3757           t0 = fold_convert (fd->iter_type, fold_convert (itype, fd->loop.n1));
3758         }
3759       else
3760         {
3761           t1 = fold_convert (fd->iter_type, fd->loop.n2);
3762           t0 = fold_convert (fd->iter_type, fd->loop.n1);
3763         }
3764       if (bias)
3765         {
3766           t1 = fold_build2 (PLUS_EXPR, fd->iter_type, t1, bias);
3767           t0 = fold_build2 (PLUS_EXPR, fd->iter_type, t0, bias);
3768         }
3769       if (fd->iter_type == long_integer_type_node)
3770         {
3771           if (fd->chunk_size)
3772             {
3773               t = fold_convert (fd->iter_type, fd->chunk_size);
3774               t = build_call_expr (built_in_decls[start_fn], 6,
3775                                    t0, t1, t2, t, t3, t4);
3776             }
3777           else
3778             t = build_call_expr (built_in_decls[start_fn], 5,
3779                                  t0, t1, t2, t3, t4);
3780         }
3781       else
3782         {
3783           tree t5;
3784           tree c_bool_type;
3785
3786           /* The GOMP_loop_ull_*start functions have additional boolean
3787              argument, true for < loops and false for > loops.
3788              In Fortran, the C bool type can be different from
3789              boolean_type_node.  */
3790           c_bool_type = TREE_TYPE (TREE_TYPE (built_in_decls[start_fn]));
3791           t5 = build_int_cst (c_bool_type,
3792                               fd->loop.cond_code == LT_EXPR ? 1 : 0);
3793           if (fd->chunk_size)
3794             {
3795               t = fold_convert (fd->iter_type, fd->chunk_size);
3796               t = build_call_expr (built_in_decls[start_fn], 7,
3797                                    t5, t0, t1, t2, t, t3, t4);
3798             }
3799           else
3800             t = build_call_expr (built_in_decls[start_fn], 6,
3801                                  t5, t0, t1, t2, t3, t4);
3802         }
3803     }
3804   if (TREE_TYPE (t) != boolean_type_node)
3805     t = fold_build2 (NE_EXPR, boolean_type_node,
3806                      t, build_int_cst (TREE_TYPE (t), 0));
3807   t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
3808                                 true, GSI_SAME_STMT);
3809   gsi_insert_after (&gsi, gimple_build_cond_empty (t), GSI_SAME_STMT);
3810
3811   /* Remove the GIMPLE_OMP_FOR statement.  */
3812   gsi_remove (&gsi, true);
3813
3814   /* Iteration setup for sequential loop goes in L0_BB.  */
3815   gsi = gsi_start_bb (l0_bb);
3816   if (bias)
3817     t = fold_convert (type, fold_build2 (MINUS_EXPR, fd->iter_type,
3818                                          istart0, bias));
3819   else
3820     t = fold_convert (type, istart0);
3821   t = force_gimple_operand_gsi (&gsi, t, false, NULL_TREE,
3822                                 false, GSI_CONTINUE_LINKING);
3823   stmt = gimple_build_assign (fd->loop.v, t);
3824   gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
3825
3826   if (bias)
3827     t = fold_convert (type, fold_build2 (MINUS_EXPR, fd->iter_type,
3828                                          iend0, bias));
3829   else
3830     t = fold_convert (type, iend0);
3831   iend = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
3832                                    false, GSI_CONTINUE_LINKING);
3833   if (fd->collapse > 1)
3834     {
3835       tree tem = create_tmp_var (type, ".tem");
3836
3837       stmt = gimple_build_assign (tem, fd->loop.v);
3838       gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
3839       for (i = fd->collapse - 1; i >= 0; i--)
3840         {
3841           tree vtype = TREE_TYPE (fd->loops[i].v), itype;
3842           itype = vtype;
3843           if (POINTER_TYPE_P (vtype))
3844             itype = lang_hooks.types.type_for_size (TYPE_PRECISION (vtype), 0);
3845           t = fold_build2 (TRUNC_MOD_EXPR, type, tem, counts[i]);
3846           t = fold_convert (itype, t);
3847           t = fold_build2 (MULT_EXPR, itype, t, fd->loops[i].step);
3848           if (POINTER_TYPE_P (vtype))
3849             t = fold_build2 (POINTER_PLUS_EXPR, vtype,
3850                              fd->loops[i].n1, fold_convert (sizetype, t));
3851           else
3852             t = fold_build2 (PLUS_EXPR, itype, fd->loops[i].n1, t);
3853           t = force_gimple_operand_gsi (&gsi, t, false, NULL_TREE,
3854                                         false, GSI_CONTINUE_LINKING);
3855           stmt = gimple_build_assign (fd->loops[i].v, t);
3856           gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
3857           if (i != 0)
3858             {
3859               t = fold_build2 (TRUNC_DIV_EXPR, type, tem, counts[i]);
3860               t = force_gimple_operand_gsi (&gsi, t, false, NULL_TREE,
3861                                             false, GSI_CONTINUE_LINKING);
3862               stmt = gimple_build_assign (tem, t);
3863               gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
3864             }
3865         }
3866     }
3867
3868   if (!broken_loop)
3869     {
3870       /* Code to control the increment and predicate for the sequential
3871          loop goes in the CONT_BB.  */
3872       gsi = gsi_last_bb (cont_bb);
3873       stmt = gsi_stmt (gsi);
3874       gcc_assert (gimple_code (stmt) == GIMPLE_OMP_CONTINUE);
3875       vmain = gimple_omp_continue_control_use (stmt);
3876       vback = gimple_omp_continue_control_def (stmt);
3877
3878       if (POINTER_TYPE_P (type))
3879         t = fold_build2 (POINTER_PLUS_EXPR, type, vmain,
3880                          fold_convert (sizetype, fd->loop.step));
3881       else
3882         t = fold_build2 (PLUS_EXPR, type, vmain, fd->loop.step);
3883       t = force_gimple_operand_gsi (&gsi, t, false, NULL_TREE,
3884                                     true, GSI_SAME_STMT);
3885       stmt = gimple_build_assign (vback, t);
3886       gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
3887
3888       t = build2 (fd->loop.cond_code, boolean_type_node, vback, iend);
3889       stmt = gimple_build_cond_empty (t);
3890       gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
3891
3892       /* Remove GIMPLE_OMP_CONTINUE.  */
3893       gsi_remove (&gsi, true);
3894
3895       if (fd->collapse > 1)
3896         {
3897           basic_block last_bb, bb;
3898
3899           last_bb = cont_bb;
3900           for (i = fd->collapse - 1; i >= 0; i--)
3901             {
3902               tree vtype = TREE_TYPE (fd->loops[i].v);
3903
3904               bb = create_empty_bb (last_bb);
3905               gsi = gsi_start_bb (bb);
3906
3907               if (i < fd->collapse - 1)
3908                 {
3909                   e = make_edge (last_bb, bb, EDGE_FALSE_VALUE);
3910                   e->probability = REG_BR_PROB_BASE / 8;
3911
3912                   t = fd->loops[i + 1].n1;
3913                   t = force_gimple_operand_gsi (&gsi, t, false, NULL_TREE,
3914                                                 false, GSI_CONTINUE_LINKING);
3915                   stmt = gimple_build_assign (fd->loops[i + 1].v, t);
3916                   gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
3917                 }
3918               else
3919                 collapse_bb = bb;
3920
3921               set_immediate_dominator (CDI_DOMINATORS, bb, last_bb);
3922
3923               if (POINTER_TYPE_P (vtype))
3924                 t = fold_build2 (POINTER_PLUS_EXPR, vtype,
3925                                  fd->loops[i].v,
3926                                  fold_convert (sizetype, fd->loops[i].step));
3927               else
3928                 t = fold_build2 (PLUS_EXPR, vtype, fd->loops[i].v,
3929                                  fd->loops[i].step);
3930               t = force_gimple_operand_gsi (&gsi, t, false, NULL_TREE,
3931                                             false, GSI_CONTINUE_LINKING);
3932               stmt = gimple_build_assign (fd->loops[i].v, t);
3933               gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
3934
3935               if (i > 0)
3936                 {
3937                   t = fd->loops[i].n2;
3938                   t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
3939                                                 false, GSI_CONTINUE_LINKING);
3940                   t = fold_build2 (fd->loops[i].cond_code, boolean_type_node,
3941                                    fd->loops[i].v, t);
3942                   stmt = gimple_build_cond_empty (t);
3943                   gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
3944                   e = make_edge (bb, l1_bb, EDGE_TRUE_VALUE);
3945                   e->probability = REG_BR_PROB_BASE * 7 / 8;
3946                 }
3947               else
3948                 make_edge (bb, l1_bb, EDGE_FALLTHRU);
3949               last_bb = bb;
3950             }
3951         }
3952
3953       /* Emit code to get the next parallel iteration in L2_BB.  */
3954       gsi = gsi_start_bb (l2_bb);
3955
3956       t = build_call_expr (built_in_decls[next_fn], 2,
3957                            build_fold_addr_expr (istart0),
3958                            build_fold_addr_expr (iend0));
3959       t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
3960                                     false, GSI_CONTINUE_LINKING);
3961       if (TREE_TYPE (t) != boolean_type_node)
3962         t = fold_build2 (NE_EXPR, boolean_type_node,
3963                          t, build_int_cst (TREE_TYPE (t), 0));
3964       stmt = gimple_build_cond_empty (t);
3965       gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
3966     }
3967
3968   /* Add the loop cleanup function.  */
3969   gsi = gsi_last_bb (exit_bb);
3970   if (gimple_omp_return_nowait_p (gsi_stmt (gsi)))
3971     t = built_in_decls[BUILT_IN_GOMP_LOOP_END_NOWAIT];
3972   else
3973     t = built_in_decls[BUILT_IN_GOMP_LOOP_END];
3974   stmt = gimple_build_call (t, 0);
3975   gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
3976   gsi_remove (&gsi, true);
3977
3978   /* Connect the new blocks.  */
3979   find_edge (entry_bb, l0_bb)->flags = EDGE_TRUE_VALUE;
3980   find_edge (entry_bb, l3_bb)->flags = EDGE_FALSE_VALUE;
3981
3982   if (!broken_loop)
3983     {
3984       gimple_seq phis;
3985
3986       e = find_edge (cont_bb, l3_bb);
3987       ne = make_edge (l2_bb, l3_bb, EDGE_FALSE_VALUE);
3988
3989       phis = phi_nodes (l3_bb);
3990       for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
3991         {
3992           gimple phi = gsi_stmt (gsi);
3993           SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, ne),
3994                    PHI_ARG_DEF_FROM_EDGE (phi, e));
3995         }
3996       remove_edge (e);
3997
3998       make_edge (cont_bb, l2_bb, EDGE_FALSE_VALUE);
3999       if (fd->collapse > 1)
4000         {
4001           e = find_edge (cont_bb, l1_bb);
4002           remove_edge (e);
4003           e = make_edge (cont_bb, collapse_bb, EDGE_TRUE_VALUE);
4004         }
4005       else
4006         {
4007           e = find_edge (cont_bb, l1_bb);
4008           e->flags = EDGE_TRUE_VALUE;
4009         }
4010       e->probability = REG_BR_PROB_BASE * 7 / 8;
4011       find_edge (cont_bb, l2_bb)->probability = REG_BR_PROB_BASE / 8;
4012       make_edge (l2_bb, l0_bb, EDGE_TRUE_VALUE);
4013
4014       set_immediate_dominator (CDI_DOMINATORS, l2_bb,
4015                                recompute_dominator (CDI_DOMINATORS, l2_bb));
4016       set_immediate_dominator (CDI_DOMINATORS, l3_bb,
4017                                recompute_dominator (CDI_DOMINATORS, l3_bb));
4018       set_immediate_dominator (CDI_DOMINATORS, l0_bb,
4019                                recompute_dominator (CDI_DOMINATORS, l0_bb));
4020       set_immediate_dominator (CDI_DOMINATORS, l1_bb,
4021                                recompute_dominator (CDI_DOMINATORS, l1_bb));
4022     }
4023 }
4024
4025
4026 /* A subroutine of expand_omp_for.  Generate code for a parallel
4027    loop with static schedule and no specified chunk size.  Given
4028    parameters:
4029
4030         for (V = N1; V cond N2; V += STEP) BODY;
4031
4032    where COND is "<" or ">", we generate pseudocode
4033
4034         if (cond is <)
4035           adj = STEP - 1;
4036         else
4037           adj = STEP + 1;
4038         if ((__typeof (V)) -1 > 0 && cond is >)
4039           n = -(adj + N2 - N1) / -STEP;
4040         else
4041           n = (adj + N2 - N1) / STEP;
4042         q = n / nthreads;
4043         q += (q * nthreads != n);
4044         s0 = q * threadid;
4045         e0 = min(s0 + q, n);
4046         V = s0 * STEP + N1;
4047         if (s0 >= e0) goto L2; else goto L0;
4048     L0:
4049         e = e0 * STEP + N1;
4050     L1:
4051         BODY;
4052         V += STEP;
4053         if (V cond e) goto L1;
4054     L2:
4055 */
4056
4057 static void
4058 expand_omp_for_static_nochunk (struct omp_region *region,
4059                                struct omp_for_data *fd)
4060 {
4061   tree n, q, s0, e0, e, t, nthreads, threadid;
4062   tree type, itype, vmain, vback;
4063   basic_block entry_bb, exit_bb, seq_start_bb, body_bb, cont_bb;
4064   basic_block fin_bb;
4065   gimple_stmt_iterator gsi;
4066   gimple stmt;
4067
4068   itype = type = TREE_TYPE (fd->loop.v);
4069   if (POINTER_TYPE_P (type))
4070     itype = lang_hooks.types.type_for_size (TYPE_PRECISION (type), 0);
4071
4072   entry_bb = region->entry;
4073   cont_bb = region->cont;
4074   gcc_assert (EDGE_COUNT (entry_bb->succs) == 2);
4075   gcc_assert (BRANCH_EDGE (entry_bb)->dest == FALLTHRU_EDGE (cont_bb)->dest);
4076   seq_start_bb = split_edge (FALLTHRU_EDGE (entry_bb));
4077   body_bb = single_succ (seq_start_bb);
4078   gcc_assert (BRANCH_EDGE (cont_bb)->dest == body_bb);
4079   gcc_assert (EDGE_COUNT (cont_bb->succs) == 2);
4080   fin_bb = FALLTHRU_EDGE (cont_bb)->dest;
4081   exit_bb = region->exit;
4082
4083   /* Iteration space partitioning goes in ENTRY_BB.  */
4084   gsi = gsi_last_bb (entry_bb);
4085   gcc_assert (gimple_code (gsi_stmt (gsi)) == GIMPLE_OMP_FOR);
4086
4087   t = build_call_expr (built_in_decls[BUILT_IN_OMP_GET_NUM_THREADS], 0);
4088   t = fold_convert (itype, t);
4089   nthreads = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
4090                                        true, GSI_SAME_STMT);
4091   
4092   t = build_call_expr (built_in_decls[BUILT_IN_OMP_GET_THREAD_NUM], 0);
4093   t = fold_convert (itype, t);
4094   threadid = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
4095                                        true, GSI_SAME_STMT);
4096
4097   fd->loop.n1
4098     = force_gimple_operand_gsi (&gsi, fold_convert (type, fd->loop.n1),
4099                                 true, NULL_TREE, true, GSI_SAME_STMT);
4100   fd->loop.n2
4101     = force_gimple_operand_gsi (&gsi, fold_convert (itype, fd->loop.n2),
4102                                 true, NULL_TREE, true, GSI_SAME_STMT);
4103   fd->loop.step
4104     = force_gimple_operand_gsi (&gsi, fold_convert (itype, fd->loop.step),
4105                                 true, NULL_TREE, true, GSI_SAME_STMT);
4106
4107   t = build_int_cst (itype, (fd->loop.cond_code == LT_EXPR ? -1 : 1));
4108   t = fold_build2 (PLUS_EXPR, itype, fd->loop.step, t);
4109   t = fold_build2 (PLUS_EXPR, itype, t, fd->loop.n2);
4110   t = fold_build2 (MINUS_EXPR, itype, t, fold_convert (itype, fd->loop.n1));
4111   if (TYPE_UNSIGNED (itype) && fd->loop.cond_code == GT_EXPR)
4112     t = fold_build2 (TRUNC_DIV_EXPR, itype,
4113                      fold_build1 (NEGATE_EXPR, itype, t),
4114                      fold_build1 (NEGATE_EXPR, itype, fd->loop.step));
4115   else
4116     t = fold_build2 (TRUNC_DIV_EXPR, itype, t, fd->loop.step);
4117   t = fold_convert (itype, t);
4118   n = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, true, GSI_SAME_STMT);
4119
4120   t = fold_build2 (TRUNC_DIV_EXPR, itype, n, nthreads);
4121   q = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, true, GSI_SAME_STMT);
4122
4123   t = fold_build2 (MULT_EXPR, itype, q, nthreads);
4124   t = fold_build2 (NE_EXPR, itype, t, n);
4125   t = fold_build2 (PLUS_EXPR, itype, q, t);
4126   q = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, true, GSI_SAME_STMT);
4127
4128   t = build2 (MULT_EXPR, itype, q, threadid);
4129   s0 = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, true, GSI_SAME_STMT);
4130
4131   t = fold_build2 (PLUS_EXPR, itype, s0, q);
4132   t = fold_build2 (MIN_EXPR, itype, t, n);
4133   e0 = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, true, GSI_SAME_STMT);
4134
4135   t = build2 (GE_EXPR, boolean_type_node, s0, e0);
4136   gsi_insert_before (&gsi, gimple_build_cond_empty (t), GSI_SAME_STMT);
4137
4138   /* Remove the GIMPLE_OMP_FOR statement.  */
4139   gsi_remove (&gsi, true);
4140
4141   /* Setup code for sequential iteration goes in SEQ_START_BB.  */
4142   gsi = gsi_start_bb (seq_start_bb);
4143
4144   t = fold_convert (itype, s0);
4145   t = fold_build2 (MULT_EXPR, itype, t, fd->loop.step);
4146   if (POINTER_TYPE_P (type))
4147     t = fold_build2 (POINTER_PLUS_EXPR, type, fd->loop.n1,
4148                      fold_convert (sizetype, t));
4149   else
4150     t = fold_build2 (PLUS_EXPR, type, t, fd->loop.n1);
4151   t = force_gimple_operand_gsi (&gsi, t, false, NULL_TREE,
4152                                 false, GSI_CONTINUE_LINKING);
4153   stmt = gimple_build_assign (fd->loop.v, t);
4154   gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
4155  
4156   t = fold_convert (itype, e0);
4157   t = fold_build2 (MULT_EXPR, itype, t, fd->loop.step);
4158   if (POINTER_TYPE_P (type))
4159     t = fold_build2 (POINTER_PLUS_EXPR, type, fd->loop.n1,
4160                      fold_convert (sizetype, t));
4161   else
4162     t = fold_build2 (PLUS_EXPR, type, t, fd->loop.n1);
4163   e = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
4164                                 false, GSI_CONTINUE_LINKING);
4165
4166   /* The code controlling the sequential loop replaces the
4167      GIMPLE_OMP_CONTINUE.  */
4168   gsi = gsi_last_bb (cont_bb);
4169   stmt = gsi_stmt (gsi);
4170   gcc_assert (gimple_code (stmt) == GIMPLE_OMP_CONTINUE);
4171   vmain = gimple_omp_continue_control_use (stmt);
4172   vback = gimple_omp_continue_control_def (stmt);
4173
4174   if (POINTER_TYPE_P (type))
4175