OSDN Git Service

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