aboutsummaryrefslogtreecommitdiff
path: root/gcc/go/go-lang.c
blob: 2797e99620c36152ae48c5888430196950e9830d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
/* go-lang.c -- Go frontend gcc interface.
   Copyright (C) 2009-2015 Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#include "config.h"
#include "system.h"
#include "ansidecl.h"
#include "coretypes.h"
#include "opts.h"
#include "hash-set.h"
#include "machmode.h"
#include "vec.h"
#include "double-int.h"
#include "input.h"
#include "alias.h"
#include "symtab.h"
#include "options.h"
#include "wide-int.h"
#include "inchash.h"
#include "tree.h"
#include "fold-const.h"
#include "tm.h"
#include "hard-reg-set.h"
#include "input.h"
#include "function.h"
#include "gimple-expr.h"
#include "gimplify.h"
#include "stor-layout.h"
#include "toplev.h"
#include "debug.h"
#include "options.h"
#include "flags.h"
#include "convert.h"
#include "diagnostic.h"
#include "langhooks.h"
#include "langhooks-def.h"
#include "target.h"
#include "common/common-target.h"

#include <mpfr.h>

#include "go-c.h"

/* Language-dependent contents of a type.  */

struct GTY(()) lang_type
{
  char dummy;
};

/* Language-dependent contents of a decl.  */

struct GTY(()) lang_decl
{
  char dummy;
};

/* Language-dependent contents of an identifier.  This must include a
   tree_identifier.  */

struct GTY(()) lang_identifier
{
  struct tree_identifier common;
};

/* The resulting tree type.  */

union GTY((desc ("TREE_CODE (&%h.generic) == IDENTIFIER_NODE"),
	   chain_next ("CODE_CONTAINS_STRUCT (TREE_CODE (&%h.generic), TS_COMMON) ? ((union lang_tree_node *) TREE_CHAIN (&%h.generic)) : NULL")))
lang_tree_node
{
  union tree_node GTY((tag ("0"),
		       desc ("tree_node_structure (&%h)"))) generic;
  struct lang_identifier GTY((tag ("1"))) identifier;
};

/* We don't use language_function.  */

struct GTY(()) language_function
{
  int dummy;
};

/* Option information we need to pass to go_create_gogo.  */

static const char *go_pkgpath = NULL;
static const char *go_prefix = NULL;
static const char *go_relative_import_path = NULL;

/* Language hooks.  */

static bool
go_langhook_init (void)
{
  build_common_tree_nodes (false, false);

  /* I don't know why this has to be done explicitly.  */
  void_list_node = build_tree_list (NULL_TREE, void_type_node);

  /* We must create the gogo IR after calling build_common_tree_nodes
     (because Gogo::define_builtin_function_trees refers indirectly
     to, e.g., unsigned_char_type_node) but before calling
     build_common_builtin_nodes (because it calls, indirectly,
     go_type_for_size).  */
  go_create_gogo (INT_TYPE_SIZE, POINTER_SIZE, go_pkgpath, go_prefix,
		  go_relative_import_path, go_check_divide_zero,
		  go_check_divide_overflow);

  build_common_builtin_nodes ();

  /* The default precision for floating point numbers.  This is used
     for floating point constants with abstract type.  This may
     eventually be controllable by a command line option.  */
  mpfr_set_default_prec (256);

  /* Go uses exceptions.  */
  using_eh_for_cleanups ();

  return true;
}

/* The option mask.  */

static unsigned int
go_langhook_option_lang_mask (void)
{
  return CL_Go;
}

/* Initialize the options structure.  */

static void
go_langhook_init_options_struct (struct gcc_options *opts)
{
  /* Go says that signed overflow is precisely defined.  */
  opts->x_flag_wrapv = 1;

  /* We default to using strict aliasing, since Go pointers are safe.
     This is turned off for code that imports the "unsafe" package,
     because using unsafe.pointer violates C style aliasing
     requirements.  */
  opts->x_flag_strict_aliasing = 1;

  /* Default to avoiding range issues for complex multiply and
     divide.  */
  opts->x_flag_complex_method = 2;

  /* The builtin math functions should not set errno.  */
  opts->x_flag_errno_math = 0;
  opts->frontend_set_flag_errno_math = true;

  /* We turn on stack splitting if we can.  */
  if (targetm_common.supports_split_stack (false, opts))
    opts->x_flag_split_stack = 1;

  /* Exceptions are used to handle recovering from panics.  */
  opts->x_flag_exceptions = 1;
  opts->x_flag_non_call_exceptions = 1;
}

/* Infrastructure for a vector of char * pointers.  */

typedef const char *go_char_p;

/* The list of directories to search after all the Go specific
   directories have been searched.  */

static vec<go_char_p> go_search_dirs;

/* Handle Go specific options.  Return 0 if we didn't do anything.  */

static bool
go_langhook_handle_option (
    size_t scode,
    const char *arg,
    int value ATTRIBUTE_UNUSED,
    int kind ATTRIBUTE_UNUSED,
    location_t loc ATTRIBUTE_UNUSED,
    const struct cl_option_handlers *handlers ATTRIBUTE_UNUSED)
{
  enum opt_code code = (enum opt_code) scode;
  bool ret = true;

  switch (code)
    {
    case OPT_I:
      go_add_search_path (arg);
      break;

    case OPT_L:
      /* A -L option is assumed to come from the compiler driver.
	 This is a system directory.  We search the following
	 directories, if they exist, before this one:
	   dir/go/VERSION
	   dir/go/VERSION/MACHINE
	 This is like include/c++.  */
      {
	static const char dir_separator_str[] = { DIR_SEPARATOR, 0 };
	size_t len;
	char *p;
	struct stat st;

	len = strlen (arg);
	p = XALLOCAVEC (char,
			(len + sizeof "go" + sizeof DEFAULT_TARGET_VERSION
			 + sizeof DEFAULT_TARGET_MACHINE + 3));
	strcpy (p, arg);
	if (len > 0 && !IS_DIR_SEPARATOR (p[len - 1]))
	  strcat (p, dir_separator_str);
	strcat (p, "go");
	strcat (p, dir_separator_str);
	strcat (p, DEFAULT_TARGET_VERSION);
	if (stat (p, &st) == 0 && S_ISDIR (st.st_mode))
	  {
	    go_add_search_path (p);
	    strcat (p, dir_separator_str);
	    strcat (p, DEFAULT_TARGET_MACHINE);
	    if (stat (p, &st) == 0 && S_ISDIR (st.st_mode))
	      go_add_search_path (p);
	  }

	/* Search ARG too, but only after we've searched to Go
	   specific directories for all -L arguments.  */
	go_search_dirs.safe_push (arg);
      }
      break;

    case OPT_fgo_dump_:
      ret = go_enable_dump (arg) ? true : false;
      break;

    case OPT_fgo_optimize_:
      ret = go_enable_optimize (arg) ? true : false;
      break;

    case OPT_fgo_pkgpath_:
      go_pkgpath = arg;
      break;

    case OPT_fgo_prefix_:
      go_prefix = arg;
      break;

    case OPT_fgo_relative_import_path_:
      go_relative_import_path = arg;
      break;

    default:
      /* Just return 1 to indicate that the option is valid.  */
      break;
    }

  return ret;
}

/* Run after parsing options.  */

static bool
go_langhook_post_options (const char **pfilename ATTRIBUTE_UNUSED)
{
  unsigned int ix;
  const char *dir;

  gcc_assert (num_in_fnames > 0);

  FOR_EACH_VEC_ELT (go_search_dirs, ix, dir)
    go_add_search_path (dir);
  go_search_dirs.release ();

  if (flag_excess_precision_cmdline == EXCESS_PRECISION_DEFAULT)
    flag_excess_precision_cmdline = EXCESS_PRECISION_STANDARD;

  /* Tail call optimizations can confuse uses of runtime.Callers.  */
  if (!global_options_set.x_flag_optimize_sibling_calls)
    global_options.x_flag_optimize_sibling_calls = 0;

  /* Returning false means that the backend should be used.  */
  return false;
}

static void
go_langhook_parse_file (void)
{
  go_parse_input_files (in_fnames, num_in_fnames, flag_syntax_only,
			go_require_return_statement);
}

static tree
go_langhook_type_for_size (unsigned int bits, int unsignedp)
{
  tree type;
  if (unsignedp)
    {
      if (bits == INT_TYPE_SIZE)
        type = unsigned_type_node;
      else if (bits == CHAR_TYPE_SIZE)
        type = unsigned_char_type_node;
      else if (bits == SHORT_TYPE_SIZE)
        type = short_unsigned_type_node;
      else if (bits == LONG_TYPE_SIZE)
        type = long_unsigned_type_node;
      else if (bits == LONG_LONG_TYPE_SIZE)
        type = long_long_unsigned_type_node;
      else
        type = make_unsigned_type(bits);
    }
  else
    {
      if (bits == INT_TYPE_SIZE)
        type = integer_type_node;
      else if (bits == CHAR_TYPE_SIZE)
        type = signed_char_type_node;
      else if (bits == SHORT_TYPE_SIZE)
        type = short_integer_type_node;
      else if (bits == LONG_TYPE_SIZE)
        type = long_integer_type_node;
      else if (bits == LONG_LONG_TYPE_SIZE)
        type = long_long_integer_type_node;
      else
        type = make_signed_type(bits);
    }
  return type;
}

static tree
go_langhook_type_for_mode (machine_mode mode, int unsignedp)
{
  tree type;
  /* Go has no vector types.  Build them here.  FIXME: It does not
     make sense for the middle-end to ask the frontend for a type
     which the frontend does not support.  However, at least for now
     it is required.  See PR 46805.  */
  if (VECTOR_MODE_P (mode))
    {
      tree inner;

      inner = go_langhook_type_for_mode (GET_MODE_INNER (mode), unsignedp);
      if (inner != NULL_TREE)
	return build_vector_type_for_mode (inner, mode);
      return NULL_TREE;
    }

  // FIXME: This static_cast should be in machmode.h.
  enum mode_class mc = static_cast<enum mode_class>(GET_MODE_CLASS(mode));
  if (mc == MODE_INT)
    return go_langhook_type_for_size(GET_MODE_BITSIZE(mode), unsignedp);
  else if (mc == MODE_FLOAT)
    {
      switch (GET_MODE_BITSIZE (mode))
	{
	case 32:
	  return float_type_node;
	case 64:
	  return double_type_node;
	default:
	  // We have to check for long double in order to support
	  // i386 excess precision.
	  if (mode == TYPE_MODE(long_double_type_node))
	    return long_double_type_node;
	}
    }
  else if (mc == MODE_COMPLEX_FLOAT)
    {
      switch (GET_MODE_BITSIZE (mode))
	{
	case 64:
	  return complex_float_type_node;
	case 128:
	  return complex_double_type_node;
	default:
	  // We have to check for long double in order to support
	  // i386 excess precision.
	  if (mode == TYPE_MODE(complex_long_double_type_node))
	    return complex_long_double_type_node;
	}
    }

#if HOST_BITS_PER_WIDE_INT >= 64
  /* The middle-end and some backends rely on TImode being supported
     for 64-bit HWI.  */
  if (mode == TImode)
    {
      type = build_nonstandard_integer_type (GET_MODE_BITSIZE (TImode),
					     unsignedp);
      if (type && TYPE_MODE (type) == TImode)
	return type;
    }
#endif
  return NULL_TREE;
}

/* Record a builtin function.  We just ignore builtin functions.  */

static tree
go_langhook_builtin_function (tree decl)
{
  return decl;
}

/* Return true if we are in the global binding level.  */

static bool
go_langhook_global_bindings_p (void)
{
  return current_function_decl == NULL_TREE;
}

/* Push a declaration into the current binding level.  We can't
   usefully implement this since we don't want to convert from tree
   back to one of our internal data structures.  I think the only way
   this is used is to record a decl which is to be returned by
   getdecls, and we could implement it for that purpose if
   necessary.  */

static tree
go_langhook_pushdecl (tree decl ATTRIBUTE_UNUSED)
{
  gcc_unreachable ();
}

/* This hook is used to get the current list of declarations as trees.
   We don't support that; instead we use the write_globals hook.  This
   can't simply crash because it is called by -gstabs.  */

static tree
go_langhook_getdecls (void)
{
  return NULL;
}

/* Write out globals.  */

static void
go_langhook_write_globals (void)
{
  go_write_globals ();
}

/* Go specific gimplification.  We need to gimplify
   CALL_EXPR_STATIC_CHAIN, because the gimplifier doesn't handle
   it.  */

static int
go_langhook_gimplify_expr (tree *expr_p, gimple_seq *pre_p, gimple_seq *post_p)
{
  if (TREE_CODE (*expr_p) == CALL_EXPR
      && CALL_EXPR_STATIC_CHAIN (*expr_p) != NULL_TREE)
    gimplify_expr (&CALL_EXPR_STATIC_CHAIN (*expr_p), pre_p, post_p,
		   is_gimple_val, fb_rvalue);
  return GS_UNHANDLED;
}

/* Return a decl for the exception personality function.  The function
   itself is implemented in libgo/runtime/go-unwind.c.  */

static tree
go_langhook_eh_personality (void)
{
  static tree personality_decl;
  if (personality_decl == NULL_TREE)
    {
      personality_decl = build_personality_function ("gccgo");
      go_preserve_from_gc (personality_decl);
    }
  return personality_decl;
}

/* Functions called directly by the generic backend.  */

tree
convert (tree type, tree expr)
{
  if (type == error_mark_node
      || expr == error_mark_node
      || TREE_TYPE (expr) == error_mark_node)
    return error_mark_node;

  if (type == TREE_TYPE (expr))
    return expr;

  if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (TREE_TYPE (expr)))
    return fold_convert (type, expr);

  switch (TREE_CODE (type))
    {
    case VOID_TYPE:
    case BOOLEAN_TYPE:
      return fold_convert (type, expr);
    case INTEGER_TYPE:
      return fold (convert_to_integer (type, expr));
    case POINTER_TYPE:
      return fold (convert_to_pointer (type, expr));
    case REAL_TYPE:
      return fold (convert_to_real (type, expr));
    case COMPLEX_TYPE:
      return fold (convert_to_complex (type, expr));
    default:
      break;
    }

  gcc_unreachable ();
}

/* FIXME: This is a hack to preserve trees that we create from the
   garbage collector.  */

static GTY(()) tree go_gc_root;

void
go_preserve_from_gc (tree t)
{
  go_gc_root = tree_cons (NULL_TREE, t, go_gc_root);
}

/* Convert an identifier for use in an error message.  */

const char *
go_localize_identifier (const char *ident)
{
  return identifier_to_locale (ident);
}

#undef LANG_HOOKS_NAME
#undef LANG_HOOKS_INIT
#undef LANG_HOOKS_OPTION_LANG_MASK
#undef LANG_HOOKS_INIT_OPTIONS_STRUCT
#undef LANG_HOOKS_HANDLE_OPTION
#undef LANG_HOOKS_POST_OPTIONS
#undef LANG_HOOKS_PARSE_FILE
#undef LANG_HOOKS_TYPE_FOR_MODE
#undef LANG_HOOKS_TYPE_FOR_SIZE
#undef LANG_HOOKS_BUILTIN_FUNCTION
#undef LANG_HOOKS_GLOBAL_BINDINGS_P
#undef LANG_HOOKS_PUSHDECL
#undef LANG_HOOKS_GETDECLS
#undef LANG_HOOKS_WRITE_GLOBALS
#undef LANG_HOOKS_GIMPLIFY_EXPR
#undef LANG_HOOKS_EH_PERSONALITY

#define LANG_HOOKS_NAME			"GNU Go"
#define LANG_HOOKS_INIT			go_langhook_init
#define LANG_HOOKS_OPTION_LANG_MASK	go_langhook_option_lang_mask
#define LANG_HOOKS_INIT_OPTIONS_STRUCT	go_langhook_init_options_struct
#define LANG_HOOKS_HANDLE_OPTION	go_langhook_handle_option
#define LANG_HOOKS_POST_OPTIONS		go_langhook_post_options
#define LANG_HOOKS_PARSE_FILE		go_langhook_parse_file
#define LANG_HOOKS_TYPE_FOR_MODE	go_langhook_type_for_mode
#define LANG_HOOKS_TYPE_FOR_SIZE	go_langhook_type_for_size
#define LANG_HOOKS_BUILTIN_FUNCTION	go_langhook_builtin_function
#define LANG_HOOKS_GLOBAL_BINDINGS_P	go_langhook_global_bindings_p
#define LANG_HOOKS_PUSHDECL		go_langhook_pushdecl
#define LANG_HOOKS_GETDECLS		go_langhook_getdecls
#define LANG_HOOKS_WRITE_GLOBALS	go_langhook_write_globals
#define LANG_HOOKS_GIMPLIFY_EXPR	go_langhook_gimplify_expr
#define LANG_HOOKS_EH_PERSONALITY	go_langhook_eh_personality

struct lang_hooks lang_hooks = LANG_HOOKS_INITIALIZER;

#include "gt-go-go-lang.h"
#include "gtype-go.h"
'n1924' href='#n1924'>1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724 2725 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749 2750 2751 2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 2766 2767 2768 2769 2770 2771 2772 2773 2774 2775 2776 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 2793 2794 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 2823 2824 2825 2826 2827 2828 2829 2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841 2842 2843 2844 2845 2846 2847 2848 2849 2850 2851 2852 2853 2854 2855 2856 2857 2858 2859 2860 2861 2862 2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874 2875 2876 2877 2878 2879 2880 2881 2882 2883 2884 2885 2886 2887 2888 2889 2890 2891 2892 2893 2894 2895 2896 2897 2898 2899 2900 2901 2902 2903 2904 2905 2906 2907 2908 2909 2910 2911 2912 2913 2914 2915 2916 2917 2918 2919 2920 2921 2922 2923 2924 2925 2926 2927 2928 2929 2930 2931 2932 2933 2934 2935 2936 2937 2938 2939 2940 2941 2942 2943 2944 2945 2946 2947 2948 2949 2950 2951 2952 2953 2954 2955 2956 2957 2958 2959 2960 2961 2962 2963 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994 2995 2996 2997 2998 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 3039 3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 3050 3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 3115 3116 3117 3118 3119 3120 3121 3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132 3133 3134 3135 3136 3137 3138 3139 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149 3150 3151 3152 3153 3154 3155 3156 3157 3158 3159 3160 3161 3162 3163 3164 3165 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 3180 3181 3182 3183 3184 3185 3186 3187 3188 3189 3190 3191 3192 3193 3194 3195 3196 3197 3198 3199 3200 3201 3202 3203 3204 3205 3206 3207 3208 3209 3210 3211 3212 3213 3214 3215 3216 3217 3218 3219 3220 3221 3222 3223 3224 3225 3226 3227 3228 3229 3230 3231 3232 3233 3234 3235 3236 3237 3238 3239 3240 3241 3242 3243 3244 3245 3246 3247 3248 3249 3250 3251 3252 3253 3254 3255 3256 3257 3258 3259 3260 3261 3262 3263 3264 3265 3266 3267 3268 3269 3270 3271 3272 3273 3274 3275 3276 3277 3278 3279 3280 3281 3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293 3294 3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331 3332 3333 3334 3335 3336 3337 3338 3339 3340 3341 3342 3343 3344 3345 3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365 3366 3367 3368 3369 3370 3371 3372 3373 3374 3375 3376 3377 3378 3379 3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423
/* Loop autoparallelization.
   Copyright (C) 2006-2016 Free Software Foundation, Inc.
   Contributed by Sebastian Pop <pop@cri.ensmp.fr> 
   Zdenek Dvorak <dvorakz@suse.cz> and Razya Ladelsky <razya@il.ibm.com>.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "cfghooks.h"
#include "tree-pass.h"
#include "ssa.h"
#include "cgraph.h"
#include "gimple-pretty-print.h"
#include "fold-const.h"
#include "gimplify.h"
#include "gimple-iterator.h"
#include "gimplify-me.h"
#include "gimple-walk.h"
#include "stor-layout.h"
#include "tree-nested.h"
#include "tree-cfg.h"
#include "tree-ssa-loop-ivopts.h"
#include "tree-ssa-loop-manip.h"
#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop.h"
#include "tree-into-ssa.h"
#include "cfgloop.h"
#include "tree-scalar-evolution.h"
#include "langhooks.h"
#include "tree-vectorizer.h"
#include "tree-hasher.h"
#include "tree-parloops.h"
#include "omp-low.h"
#include "tree-ssa.h"
#include "params.h"
#include "params-enum.h"
#include "tree-ssa-alias.h"
#include "tree-eh.h"
#include "gomp-constants.h"
#include "tree-dfa.h"

/* This pass tries to distribute iterations of loops into several threads.
   The implementation is straightforward -- for each loop we test whether its
   iterations are independent, and if it is the case (and some additional
   conditions regarding profitability and correctness are satisfied), we
   add GIMPLE_OMP_PARALLEL and GIMPLE_OMP_FOR codes and let omp expansion
   machinery do its job.

   The most of the complexity is in bringing the code into shape expected
   by the omp expanders:
   -- for GIMPLE_OMP_FOR, ensuring that the loop has only one induction
      variable and that the exit test is at the start of the loop body
   -- for GIMPLE_OMP_PARALLEL, replacing the references to local addressable
      variables by accesses through pointers, and breaking up ssa chains
      by storing the values incoming to the parallelized loop to a structure
      passed to the new function as an argument (something similar is done
      in omp gimplification, unfortunately only a small part of the code
      can be shared).

   TODO:
   -- if there are several parallelizable loops in a function, it may be
      possible to generate the threads just once (using synchronization to
      ensure that cross-loop dependences are obeyed).
   -- handling of common reduction patterns for outer loops.  
    
   More info can also be found at http://gcc.gnu.org/wiki/AutoParInGCC  */
/*
  Reduction handling:
  currently we use vect_force_simple_reduction() to detect reduction patterns.
  The code transformation will be introduced by an example.


parloop
{
  int sum=1;

  for (i = 0; i < N; i++)
   {
    x[i] = i + 3;
    sum+=x[i];
   }
}

gimple-like code:
header_bb:

  # sum_29 = PHI <sum_11(5), 1(3)>
  # i_28 = PHI <i_12(5), 0(3)>
  D.1795_8 = i_28 + 3;
  x[i_28] = D.1795_8;
  sum_11 = D.1795_8 + sum_29;
  i_12 = i_28 + 1;
  if (N_6(D) > i_12)
    goto header_bb;


exit_bb:

  # sum_21 = PHI <sum_11(4)>
  printf (&"%d"[0], sum_21);


after reduction transformation (only relevant parts):

parloop
{

....


  # Storing the initial value given by the user.  #

  .paral_data_store.32.sum.27 = 1;

  #pragma omp parallel num_threads(4)

  #pragma omp for schedule(static)

  # The neutral element corresponding to the particular
  reduction's operation, e.g. 0 for PLUS_EXPR,
  1 for MULT_EXPR, etc. replaces the user's initial value.  #

  # sum.27_29 = PHI <sum.27_11, 0>

  sum.27_11 = D.1827_8 + sum.27_29;

  GIMPLE_OMP_CONTINUE

  # Adding this reduction phi is done at create_phi_for_local_result() #
  # sum.27_56 = PHI <sum.27_11, 0>
  GIMPLE_OMP_RETURN

  # Creating the atomic operation is done at
  create_call_for_reduction_1()  #

  #pragma omp atomic_load
  D.1839_59 = *&.paral_data_load.33_51->reduction.23;
  D.1840_60 = sum.27_56 + D.1839_59;
  #pragma omp atomic_store (D.1840_60);

  GIMPLE_OMP_RETURN

 # collecting the result after the join of the threads is done at
  create_loads_for_reductions().
  The value computed by the threads is loaded from the
  shared struct.  #


  .paral_data_load.33_52 = &.paral_data_store.32;
  sum_37 =  .paral_data_load.33_52->sum.27;
  sum_43 = D.1795_41 + sum_37;

  exit bb:
  # sum_21 = PHI <sum_43, sum_26>
  printf (&"%d"[0], sum_21);

...

}

*/

/* Minimal number of iterations of a loop that should be executed in each
   thread.  */
#define MIN_PER_THREAD 100

/* Element of the hashtable, representing a
   reduction in the current loop.  */
struct reduction_info
{
  gimple *reduc_stmt;		/* reduction statement.  */
  gimple *reduc_phi;		/* The phi node defining the reduction.  */
  enum tree_code reduction_code;/* code for the reduction operation.  */
  unsigned reduc_version;	/* SSA_NAME_VERSION of original reduc_phi
				   result.  */
  gphi *keep_res;		/* The PHI_RESULT of this phi is the resulting value
				   of the reduction variable when existing the loop. */
  tree initial_value;		/* The initial value of the reduction var before entering the loop.  */
  tree field;			/*  the name of the field in the parloop data structure intended for reduction.  */
  tree reduc_addr;		/* The address of the reduction variable for
				   openacc reductions.  */
  tree init;			/* reduction initialization value.  */
  gphi *new_phi;		/* (helper field) Newly created phi node whose result
				   will be passed to the atomic operation.  Represents
				   the local result each thread computed for the reduction
				   operation.  */
};

/* Reduction info hashtable helpers.  */

struct reduction_hasher : free_ptr_hash <reduction_info>
{
  static inline hashval_t hash (const reduction_info *);
  static inline bool equal (const reduction_info *, const reduction_info *);
};

/* Equality and hash functions for hashtab code.  */

inline bool
reduction_hasher::equal (const reduction_info *a, const reduction_info *b)
{
  return (a->reduc_phi == b->reduc_phi);
}

inline hashval_t
reduction_hasher::hash (const reduction_info *a)
{
  return a->reduc_version;
}

typedef hash_table<reduction_hasher> reduction_info_table_type;


static struct reduction_info *
reduction_phi (reduction_info_table_type *reduction_list, gimple *phi)
{
  struct reduction_info tmpred, *red;

  if (reduction_list->elements () == 0 || phi == NULL)
    return NULL;

  if (gimple_uid (phi) == (unsigned int)-1
      || gimple_uid (phi) == 0)
    return NULL;

  tmpred.reduc_phi = phi;
  tmpred.reduc_version = gimple_uid (phi);
  red = reduction_list->find (&tmpred);
  gcc_assert (red == NULL || red->reduc_phi == phi);

  return red;
}

/* Element of hashtable of names to copy.  */

struct name_to_copy_elt
{
  unsigned version;	/* The version of the name to copy.  */
  tree new_name;	/* The new name used in the copy.  */
  tree field;		/* The field of the structure used to pass the
			   value.  */
};

/* Name copies hashtable helpers.  */

struct name_to_copy_hasher : free_ptr_hash <name_to_copy_elt>
{
  static inline hashval_t hash (const name_to_copy_elt *);
  static inline bool equal (const name_to_copy_elt *, const name_to_copy_elt *);
};

/* Equality and hash functions for hashtab code.  */

inline bool
name_to_copy_hasher::equal (const name_to_copy_elt *a, const name_to_copy_elt *b)
{
  return a->version == b->version;
}

inline hashval_t
name_to_copy_hasher::hash (const name_to_copy_elt *a)
{
  return (hashval_t) a->version;
}

typedef hash_table<name_to_copy_hasher> name_to_copy_table_type;

/* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE
   matrix.  Rather than use floats, we simply keep a single DENOMINATOR that
   represents the denominator for every element in the matrix.  */
typedef struct lambda_trans_matrix_s
{
  lambda_matrix matrix;
  int rowsize;
  int colsize;
  int denominator;
} *lambda_trans_matrix;
#define LTM_MATRIX(T) ((T)->matrix)
#define LTM_ROWSIZE(T) ((T)->rowsize)
#define LTM_COLSIZE(T) ((T)->colsize)
#define LTM_DENOMINATOR(T) ((T)->denominator)

/* Allocate a new transformation matrix.  */

static lambda_trans_matrix
lambda_trans_matrix_new (int colsize, int rowsize,
			 struct obstack * lambda_obstack)
{
  lambda_trans_matrix ret;

  ret = (lambda_trans_matrix)
    obstack_alloc (lambda_obstack, sizeof (struct lambda_trans_matrix_s));
  LTM_MATRIX (ret) = lambda_matrix_new (rowsize, colsize, lambda_obstack);
  LTM_ROWSIZE (ret) = rowsize;
  LTM_COLSIZE (ret) = colsize;
  LTM_DENOMINATOR (ret) = 1;
  return ret;
}

/* Multiply a vector VEC by a matrix MAT.
   MAT is an M*N matrix, and VEC is a vector with length N.  The result
   is stored in DEST which must be a vector of length M.  */

static void
lambda_matrix_vector_mult (lambda_matrix matrix, int m, int n,
			   lambda_vector vec, lambda_vector dest)
{
  int i, j;

  lambda_vector_clear (dest, m);
  for (i = 0; i < m; i++)
    for (j = 0; j < n; j++)
      dest[i] += matrix[i][j] * vec[j];
}

/* Return true if TRANS is a legal transformation matrix that respects
   the dependence vectors in DISTS and DIRS.  The conservative answer
   is false.

   "Wolfe proves that a unimodular transformation represented by the
   matrix T is legal when applied to a loop nest with a set of
   lexicographically non-negative distance vectors RDG if and only if
   for each vector d in RDG, (T.d >= 0) is lexicographically positive.
   i.e.: if and only if it transforms the lexicographically positive
   distance vectors to lexicographically positive vectors.  Note that
   a unimodular matrix must transform the zero vector (and only it) to
   the zero vector." S.Muchnick.  */

static bool
lambda_transform_legal_p (lambda_trans_matrix trans,
			  int nb_loops,
			  vec<ddr_p> dependence_relations)
{
  unsigned int i, j;
  lambda_vector distres;
  struct data_dependence_relation *ddr;

  gcc_assert (LTM_COLSIZE (trans) == nb_loops
	      && LTM_ROWSIZE (trans) == nb_loops);

  /* When there are no dependences, the transformation is correct.  */
  if (dependence_relations.length () == 0)
    return true;

  ddr = dependence_relations[0];
  if (ddr == NULL)
    return true;

  /* When there is an unknown relation in the dependence_relations, we
     know that it is no worth looking at this loop nest: give up.  */
  if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
    return false;

  distres = lambda_vector_new (nb_loops);

  /* For each distance vector in the dependence graph.  */
  FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
    {
      /* Don't care about relations for which we know that there is no
	 dependence, nor about read-read (aka. output-dependences):
	 these data accesses can happen in any order.  */
      if (DDR_ARE_DEPENDENT (ddr) == chrec_known
	  || (DR_IS_READ (DDR_A (ddr)) && DR_IS_READ (DDR_B (ddr))))
	continue;

      /* Conservatively answer: "this transformation is not valid".  */
      if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
	return false;

      /* If the dependence could not be captured by a distance vector,
	 conservatively answer that the transform is not valid.  */
      if (DDR_NUM_DIST_VECTS (ddr) == 0)
	return false;

      /* Compute trans.dist_vect */
      for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
	{
	  lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops,
				     DDR_DIST_VECT (ddr, j), distres);

	  if (!lambda_vector_lexico_pos (distres, nb_loops))
	    return false;
	}
    }
  return true;
}

/* Data dependency analysis. Returns true if the iterations of LOOP
   are independent on each other (that is, if we can execute them
   in parallel).  */

static bool
loop_parallel_p (struct loop *loop, struct obstack * parloop_obstack)
{
  vec<ddr_p> dependence_relations;
  vec<data_reference_p> datarefs;
  lambda_trans_matrix trans;
  bool ret = false;

  if (dump_file && (dump_flags & TDF_DETAILS))
  {
    fprintf (dump_file, "Considering loop %d\n", loop->num);
    if (!loop->inner)
      fprintf (dump_file, "loop is innermost\n");
    else
      fprintf (dump_file, "loop NOT innermost\n");
   }

  /* Check for problems with dependences.  If the loop can be reversed,
     the iterations are independent.  */
  auto_vec<loop_p, 3> loop_nest;
  datarefs.create (10);
  dependence_relations.create (100);
  if (! compute_data_dependences_for_loop (loop, true, &loop_nest, &datarefs,
					   &dependence_relations))
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file, "  FAILED: cannot analyze data dependencies\n");
      ret = false;
      goto end;
    }
  if (dump_file && (dump_flags & TDF_DETAILS))
    dump_data_dependence_relations (dump_file, dependence_relations);

  trans = lambda_trans_matrix_new (1, 1, parloop_obstack);
  LTM_MATRIX (trans)[0][0] = -1;

  if (lambda_transform_legal_p (trans, 1, dependence_relations))
    {
      ret = true;
      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file, "  SUCCESS: may be parallelized\n");
    }
  else if (dump_file && (dump_flags & TDF_DETAILS))
    fprintf (dump_file,
	     "  FAILED: data dependencies exist across iterations\n");

 end:
  free_dependence_relations (dependence_relations);
  free_data_refs (datarefs);

  return ret;
}

/* Return true when LOOP contains basic blocks marked with the
   BB_IRREDUCIBLE_LOOP flag.  */

static inline bool
loop_has_blocks_with_irreducible_flag (struct loop *loop)
{
  unsigned i;
  basic_block *bbs = get_loop_body_in_dom_order (loop);
  bool res = true;

  for (i = 0; i < loop->num_nodes; i++)
    if (bbs[i]->flags & BB_IRREDUCIBLE_LOOP)
      goto end;

  res = false;
 end:
  free (bbs);
  return res;
}

/* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
   The assignment statement is placed on edge ENTRY.  DECL_ADDRESS maps decls
   to their addresses that can be reused.  The address of OBJ is known to
   be invariant in the whole function.  Other needed statements are placed
   right before GSI.  */

static tree
take_address_of (tree obj, tree type, edge entry,
		 int_tree_htab_type *decl_address, gimple_stmt_iterator *gsi)
{
  int uid;
  tree *var_p, name, addr;
  gassign *stmt;
  gimple_seq stmts;

  /* Since the address of OBJ is invariant, the trees may be shared.
     Avoid rewriting unrelated parts of the code.  */
  obj = unshare_expr (obj);
  for (var_p = &obj;
       handled_component_p (*var_p);
       var_p = &TREE_OPERAND (*var_p, 0))
    continue;

  /* Canonicalize the access to base on a MEM_REF.  */
  if (DECL_P (*var_p))
    *var_p = build_simple_mem_ref (build_fold_addr_expr (*var_p));

  /* Assign a canonical SSA name to the address of the base decl used
     in the address and share it for all accesses and addresses based
     on it.  */
  uid = DECL_UID (TREE_OPERAND (TREE_OPERAND (*var_p, 0), 0));
  int_tree_map elt;
  elt.uid = uid;
  int_tree_map *slot = decl_address->find_slot (elt, INSERT);
  if (!slot->to)
    {
      if (gsi == NULL)
	return NULL;
      addr = TREE_OPERAND (*var_p, 0);
      const char *obj_name
	= get_name (TREE_OPERAND (TREE_OPERAND (*var_p, 0), 0));
      if (obj_name)
	name = make_temp_ssa_name (TREE_TYPE (addr), NULL, obj_name);
      else
	name = make_ssa_name (TREE_TYPE (addr));
      stmt = gimple_build_assign (name, addr);
      gsi_insert_on_edge_immediate (entry, stmt);

      slot->uid = uid;
      slot->to = name;
    }
  else
    name = slot->to;

  /* Express the address in terms of the canonical SSA name.  */
  TREE_OPERAND (*var_p, 0) = name;
  if (gsi == NULL)
    return build_fold_addr_expr_with_type (obj, type);

  name = force_gimple_operand (build_addr (obj),
			       &stmts, true, NULL_TREE);
  if (!gimple_seq_empty_p (stmts))
    gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);

  if (!useless_type_conversion_p (type, TREE_TYPE (name)))
    {
      name = force_gimple_operand (fold_convert (type, name), &stmts, true,
				   NULL_TREE);
      if (!gimple_seq_empty_p (stmts))
	gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
    }

  return name;
}

static tree
reduc_stmt_res (gimple *stmt)
{
  return (gimple_code (stmt) == GIMPLE_PHI
	  ? gimple_phi_result (stmt)
	  : gimple_assign_lhs (stmt));
}

/* Callback for htab_traverse.  Create the initialization statement
   for reduction described in SLOT, and place it at the preheader of
   the loop described in DATA.  */

int
initialize_reductions (reduction_info **slot, struct loop *loop)
{
  tree init;
  tree type, arg;
  edge e;

  struct reduction_info *const reduc = *slot;

  /* Create initialization in preheader:
     reduction_variable = initialization value of reduction.  */

  /* In the phi node at the header, replace the argument coming
     from the preheader with the reduction initialization value.  */

  /* Initialize the reduction.  */
  type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
  init = omp_reduction_init_op (gimple_location (reduc->reduc_stmt),
				reduc->reduction_code, type);
  reduc->init = init;

  /* Replace the argument representing the initialization value
     with the initialization value for the reduction (neutral
     element for the particular operation, e.g. 0 for PLUS_EXPR,
     1 for MULT_EXPR, etc).
     Keep the old value in a new variable "reduction_initial",
     that will be taken in consideration after the parallel
     computing is done.  */

  e = loop_preheader_edge (loop);
  arg = PHI_ARG_DEF_FROM_EDGE (reduc->reduc_phi, e);
  /* Create new variable to hold the initial value.  */

  SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
	   (reduc->reduc_phi, loop_preheader_edge (loop)), init);
  reduc->initial_value = arg;
  return 1;
}

struct elv_data
{
  struct walk_stmt_info info;
  edge entry;
  int_tree_htab_type *decl_address;
  gimple_stmt_iterator *gsi;
  bool changed;
  bool reset;
};

/* Eliminates references to local variables in *TP out of the single
   entry single exit region starting at DTA->ENTRY.
   DECL_ADDRESS contains addresses of the references that had their
   address taken already.  If the expression is changed, CHANGED is
   set to true.  Callback for walk_tree.  */

static tree
eliminate_local_variables_1 (tree *tp, int *walk_subtrees, void *data)
{
  struct elv_data *const dta = (struct elv_data *) data;
  tree t = *tp, var, addr, addr_type, type, obj;

  if (DECL_P (t))
    {
      *walk_subtrees = 0;

      if (!SSA_VAR_P (t) || DECL_EXTERNAL (t))
	return NULL_TREE;

      type = TREE_TYPE (t);
      addr_type = build_pointer_type (type);
      addr = take_address_of (t, addr_type, dta->entry, dta->decl_address,
			      dta->gsi);
      if (dta->gsi == NULL && addr == NULL_TREE)
	{
	  dta->reset = true;
	  return NULL_TREE;
	}

      *tp = build_simple_mem_ref (addr);

      dta->changed = true;
      return NULL_TREE;
    }

  if (TREE_CODE (t) == ADDR_EXPR)
    {
      /* ADDR_EXPR may appear in two contexts:
	 -- as a gimple operand, when the address taken is a function invariant
	 -- as gimple rhs, when the resulting address in not a function
	    invariant
	 We do not need to do anything special in the latter case (the base of
	 the memory reference whose address is taken may be replaced in the
	 DECL_P case).  The former case is more complicated, as we need to
	 ensure that the new address is still a gimple operand.  Thus, it
	 is not sufficient to replace just the base of the memory reference --
	 we need to move the whole computation of the address out of the
	 loop.  */
      if (!is_gimple_val (t))
	return NULL_TREE;

      *walk_subtrees = 0;
      obj = TREE_OPERAND (t, 0);
      var = get_base_address (obj);
      if (!var || !SSA_VAR_P (var) || DECL_EXTERNAL (var))
	return NULL_TREE;

      addr_type = TREE_TYPE (t);
      addr = take_address_of (obj, addr_type, dta->entry, dta->decl_address,
			      dta->gsi);
      if (dta->gsi == NULL && addr == NULL_TREE)
	{
	  dta->reset = true;
	  return NULL_TREE;
	}
      *tp = addr;

      dta->changed = true;
      return NULL_TREE;
    }

  if (!EXPR_P (t))
    *walk_subtrees = 0;

  return NULL_TREE;
}

/* Moves the references to local variables in STMT at *GSI out of the single
   entry single exit region starting at ENTRY.  DECL_ADDRESS contains
   addresses of the references that had their address taken
   already.  */

static void
eliminate_local_variables_stmt (edge entry, gimple_stmt_iterator *gsi,
				int_tree_htab_type *decl_address)
{
  struct elv_data dta;
  gimple *stmt = gsi_stmt (*gsi);

  memset (&dta.info, '\0', sizeof (dta.info));
  dta.entry = entry;
  dta.decl_address = decl_address;
  dta.changed = false;
  dta.reset = false;

  if (gimple_debug_bind_p (stmt))
    {
      dta.gsi = NULL;
      walk_tree (gimple_debug_bind_get_value_ptr (stmt),
		 eliminate_local_variables_1, &dta.info, NULL);
      if (dta.reset)
	{
	  gimple_debug_bind_reset_value (stmt);
	  dta.changed = true;
	}
    }
  else if (gimple_clobber_p (stmt))
    {
      unlink_stmt_vdef (stmt);
      stmt = gimple_build_nop ();
      gsi_replace (gsi, stmt, false);
      dta.changed = true;
    }
  else
    {
      dta.gsi = gsi;
      walk_gimple_op (stmt, eliminate_local_variables_1, &dta.info);
    }

  if (dta.changed)
    update_stmt (stmt);
}

/* Eliminates the references to local variables from the single entry
   single exit region between the ENTRY and EXIT edges.

   This includes:
   1) Taking address of a local variable -- these are moved out of the
   region (and temporary variable is created to hold the address if
   necessary).

   2) Dereferencing a local variable -- these are replaced with indirect
   references.  */

static void
eliminate_local_variables (edge entry, edge exit)
{
  basic_block bb;
  auto_vec<basic_block, 3> body;
  unsigned i;
  gimple_stmt_iterator gsi;
  bool has_debug_stmt = false;
  int_tree_htab_type decl_address (10);
  basic_block entry_bb = entry->src;
  basic_block exit_bb = exit->dest;

  gather_blocks_in_sese_region (entry_bb, exit_bb, &body);

  FOR_EACH_VEC_ELT (body, i, bb)
    if (bb != entry_bb && bb != exit_bb)
      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
	if (is_gimple_debug (gsi_stmt (gsi)))
	  {
	    if (gimple_debug_bind_p (gsi_stmt (gsi)))
	      has_debug_stmt = true;
	  }
	else
	  eliminate_local_variables_stmt (entry, &gsi, &decl_address);

  if (has_debug_stmt)
    FOR_EACH_VEC_ELT (body, i, bb)
      if (bb != entry_bb && bb != exit_bb)
	for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
	  if (gimple_debug_bind_p (gsi_stmt (gsi)))
	    eliminate_local_variables_stmt (entry, &gsi, &decl_address);
}

/* Returns true if expression EXPR is not defined between ENTRY and
   EXIT, i.e. if all its operands are defined outside of the region.  */

static bool
expr_invariant_in_region_p (edge entry, edge exit, tree expr)
{
  basic_block entry_bb = entry->src;
  basic_block exit_bb = exit->dest;
  basic_block def_bb;

  if (is_gimple_min_invariant (expr))
    return true;

  if (TREE_CODE (expr) == SSA_NAME)
    {
      def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
      if (def_bb
	  && dominated_by_p (CDI_DOMINATORS, def_bb, entry_bb)
	  && !dominated_by_p (CDI_DOMINATORS, def_bb, exit_bb))
	return false;

      return true;
    }

  return false;
}

/* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
   The copies are stored to NAME_COPIES, if NAME was already duplicated,
   its duplicate stored in NAME_COPIES is returned.

   Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
   duplicated, storing the copies in DECL_COPIES.  */

static tree
separate_decls_in_region_name (tree name, name_to_copy_table_type *name_copies,
			       int_tree_htab_type *decl_copies,
			       bool copy_name_p)
{
  tree copy, var, var_copy;
  unsigned idx, uid, nuid;
  struct int_tree_map ielt;
  struct name_to_copy_elt elt, *nelt;
  name_to_copy_elt **slot;
  int_tree_map *dslot;

  if (TREE_CODE (name) != SSA_NAME)
    return name;

  idx = SSA_NAME_VERSION (name);
  elt.version = idx;
  slot = name_copies->find_slot_with_hash (&elt, idx,
					   copy_name_p ? INSERT : NO_INSERT);
  if (slot && *slot)
    return (*slot)->new_name;

  if (copy_name_p)
    {
      copy = duplicate_ssa_name (name, NULL);
      nelt = XNEW (struct name_to_copy_elt);
      nelt->version = idx;
      nelt->new_name = copy;
      nelt->field = NULL_TREE;
      *slot = nelt;
    }
  else
    {
      gcc_assert (!slot);
      copy = name;
    }

  var = SSA_NAME_VAR (name);
  if (!var)
    return copy;

  uid = DECL_UID (var);
  ielt.uid = uid;
  dslot = decl_copies->find_slot_with_hash (ielt, uid, INSERT);
  if (!dslot->to)
    {
      var_copy = create_tmp_var (TREE_TYPE (var), get_name (var));
      DECL_GIMPLE_REG_P (var_copy) = DECL_GIMPLE_REG_P (var);
      dslot->uid = uid;
      dslot->to = var_copy;

      /* Ensure that when we meet this decl next time, we won't duplicate
         it again.  */
      nuid = DECL_UID (var_copy);
      ielt.uid = nuid;
      dslot = decl_copies->find_slot_with_hash (ielt, nuid, INSERT);
      gcc_assert (!dslot->to);
      dslot->uid = nuid;
      dslot->to = var_copy;
    }
  else
    var_copy = dslot->to;

  replace_ssa_name_symbol (copy, var_copy);
  return copy;
}

/* Finds the ssa names used in STMT that are defined outside the
   region between ENTRY and EXIT and replaces such ssa names with
   their duplicates.  The duplicates are stored to NAME_COPIES.  Base
   decls of all ssa names used in STMT (including those defined in
   LOOP) are replaced with the new temporary variables; the
   replacement decls are stored in DECL_COPIES.  */

static void
separate_decls_in_region_stmt (edge entry, edge exit, gimple *stmt,
			       name_to_copy_table_type *name_copies,
			       int_tree_htab_type *decl_copies)
{
  use_operand_p use;
  def_operand_p def;
  ssa_op_iter oi;
  tree name, copy;
  bool copy_name_p;

  FOR_EACH_PHI_OR_STMT_DEF (def, stmt, oi, SSA_OP_DEF)
  {
    name = DEF_FROM_PTR (def);
    gcc_assert (TREE_CODE (name) == SSA_NAME);
    copy = separate_decls_in_region_name (name, name_copies, decl_copies,
					  false);
    gcc_assert (copy == name);
  }

  FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
  {
    name = USE_FROM_PTR (use);
    if (TREE_CODE (name) != SSA_NAME)
      continue;

    copy_name_p = expr_invariant_in_region_p (entry, exit, name);
    copy = separate_decls_in_region_name (name, name_copies, decl_copies,
					  copy_name_p);
    SET_USE (use, copy);
  }
}

/* Finds the ssa names used in STMT that are defined outside the
   region between ENTRY and EXIT and replaces such ssa names with
   their duplicates.  The duplicates are stored to NAME_COPIES.  Base
   decls of all ssa names used in STMT (including those defined in
   LOOP) are replaced with the new temporary variables; the
   replacement decls are stored in DECL_COPIES.  */

static bool
separate_decls_in_region_debug (gimple *stmt,
				name_to_copy_table_type *name_copies,
				int_tree_htab_type *decl_copies)
{
  use_operand_p use;
  ssa_op_iter oi;
  tree var, name;
  struct int_tree_map ielt;
  struct name_to_copy_elt elt;
  name_to_copy_elt **slot;
  int_tree_map *dslot;

  if (gimple_debug_bind_p (stmt))
    var = gimple_debug_bind_get_var (stmt);
  else if (gimple_debug_source_bind_p (stmt))
    var = gimple_debug_source_bind_get_var (stmt);
  else
    return true;
  if (TREE_CODE (var) == DEBUG_EXPR_DECL || TREE_CODE (var) == LABEL_DECL)
    return true;
  gcc_assert (DECL_P (var) && SSA_VAR_P (var));
  ielt.uid = DECL_UID (var);
  dslot = decl_copies->find_slot_with_hash (ielt, ielt.uid, NO_INSERT);
  if (!dslot)
    return true;
  if (gimple_debug_bind_p (stmt))
    gimple_debug_bind_set_var (stmt, dslot->to);
  else if (gimple_debug_source_bind_p (stmt))
    gimple_debug_source_bind_set_var (stmt, dslot->to);

  FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
  {
    name = USE_FROM_PTR (use);
    if (TREE_CODE (name) != SSA_NAME)
      continue;

    elt.version = SSA_NAME_VERSION (name);
    slot = name_copies->find_slot_with_hash (&elt, elt.version, NO_INSERT);
    if (!slot)
      {
	gimple_debug_bind_reset_value (stmt);
	update_stmt (stmt);
	break;
      }

    SET_USE (use, (*slot)->new_name);
  }

  return false;
}

/* Callback for htab_traverse.  Adds a field corresponding to the reduction
   specified in SLOT. The type is passed in DATA.  */

int
add_field_for_reduction (reduction_info **slot, tree type)
{

  struct reduction_info *const red = *slot;
  tree var = reduc_stmt_res (red->reduc_stmt);
  tree field = build_decl (gimple_location (red->reduc_stmt), FIELD_DECL,
			   SSA_NAME_IDENTIFIER (var), TREE_TYPE (var));

  insert_field_into_struct (type, field);

  red->field = field;

  return 1;
}

/* Callback for htab_traverse.  Adds a field corresponding to a ssa name
   described in SLOT. The type is passed in DATA.  */

int
add_field_for_name (name_to_copy_elt **slot, tree type)
{
  struct name_to_copy_elt *const elt = *slot;
  tree name = ssa_name (elt->version);
  tree field = build_decl (UNKNOWN_LOCATION,
			   FIELD_DECL, SSA_NAME_IDENTIFIER (name),
			   TREE_TYPE (name));

  insert_field_into_struct (type, field);
  elt->field = field;

  return 1;
}

/* Callback for htab_traverse.  A local result is the intermediate result
   computed by a single
   thread, or the initial value in case no iteration was executed.
   This function creates a phi node reflecting these values.
   The phi's result will be stored in NEW_PHI field of the
   reduction's data structure.  */

int
create_phi_for_local_result (reduction_info **slot, struct loop *loop)
{
  struct reduction_info *const reduc = *slot;
  edge e;
  gphi *new_phi;
  basic_block store_bb, continue_bb;
  tree local_res;
  source_location locus;

  /* STORE_BB is the block where the phi
     should be stored.  It is the destination of the loop exit.
     (Find the fallthru edge from GIMPLE_OMP_CONTINUE).  */
  continue_bb = single_pred (loop->latch);
  store_bb = FALLTHRU_EDGE (continue_bb)->dest;

  /* STORE_BB has two predecessors.  One coming from  the loop
     (the reduction's result is computed at the loop),
     and another coming from a block preceding the loop,
     when no iterations
     are executed (the initial value should be taken).  */
  if (EDGE_PRED (store_bb, 0) == FALLTHRU_EDGE (continue_bb))
    e = EDGE_PRED (store_bb, 1);
  else
    e = EDGE_PRED (store_bb, 0);
  tree lhs = reduc_stmt_res (reduc->reduc_stmt);
  local_res = copy_ssa_name (lhs);
  locus = gimple_location (reduc->reduc_stmt);
  new_phi = create_phi_node (local_res, store_bb);
  add_phi_arg (new_phi, reduc->init, e, locus);
  add_phi_arg (new_phi, lhs, FALLTHRU_EDGE (continue_bb), locus);
  reduc->new_phi = new_phi;

  return 1;
}

struct clsn_data
{
  tree store;
  tree load;

  basic_block store_bb;
  basic_block load_bb;
};

/* Callback for htab_traverse.  Create an atomic instruction for the
   reduction described in SLOT.
   DATA annotates the place in memory the atomic operation relates to,
   and the basic block it needs to be generated in.  */

int
create_call_for_reduction_1 (reduction_info **slot, struct clsn_data *clsn_data)
{
  struct reduction_info *const reduc = *slot;
  gimple_stmt_iterator gsi;
  tree type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
  tree load_struct;
  basic_block bb;
  basic_block new_bb;
  edge e;
  tree t, addr, ref, x;
  tree tmp_load, name;
  gimple *load;

  if (reduc->reduc_addr == NULL_TREE)
    {
      load_struct = build_simple_mem_ref (clsn_data->load);
      t = build3 (COMPONENT_REF, type, load_struct, reduc->field, NULL_TREE);

      addr = build_addr (t);
    }
  else
    {
      /* Set the address for the atomic store.  */
      addr = reduc->reduc_addr;

      /* Remove the non-atomic store '*addr = sum'.  */
      tree res = PHI_RESULT (reduc->keep_res);
      use_operand_p use_p;
      gimple *stmt;
      bool single_use_p = single_imm_use (res, &use_p, &stmt);
      gcc_assert (single_use_p);
      replace_uses_by (gimple_vdef (stmt),
		       gimple_vuse (stmt));
      gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
      gsi_remove (&gsi, true);
    }

  /* Create phi node.  */
  bb = clsn_data->load_bb;

  gsi = gsi_last_bb (bb);
  e = split_block (bb, gsi_stmt (gsi));
  new_bb = e->dest;

  tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)));
  tmp_load = make_ssa_name (tmp_load);
  load = gimple_build_omp_atomic_load (tmp_load, addr);
  SSA_NAME_DEF_STMT (tmp_load) = load;
  gsi = gsi_start_bb (new_bb);
  gsi_insert_after (&gsi, load, GSI_NEW_STMT);

  e = split_block (new_bb, load);
  new_bb = e->dest;
  gsi = gsi_start_bb (new_bb);
  ref = tmp_load;
  x = fold_build2 (reduc->reduction_code,
		   TREE_TYPE (PHI_RESULT (reduc->new_phi)), ref,
		   PHI_RESULT (reduc->new_phi));

  name = force_gimple_operand_gsi (&gsi, x, true, NULL_TREE, true,
				   GSI_CONTINUE_LINKING);

  gsi_insert_after (&gsi, gimple_build_omp_atomic_store (name), GSI_NEW_STMT);
  return 1;
}

/* Create the atomic operation at the join point of the threads.
   REDUCTION_LIST describes the reductions in the LOOP.
   LD_ST_DATA describes the shared data structure where
   shared data is stored in and loaded from.  */
static void
create_call_for_reduction (struct loop *loop,
			   reduction_info_table_type *reduction_list,
			   struct clsn_data *ld_st_data)
{
  reduction_list->traverse <struct loop *, create_phi_for_local_result> (loop);
  /* Find the fallthru edge from GIMPLE_OMP_CONTINUE.  */
  basic_block continue_bb = single_pred (loop->latch);
  ld_st_data->load_bb = FALLTHRU_EDGE (continue_bb)->dest;
  reduction_list
    ->traverse <struct clsn_data *, create_call_for_reduction_1> (ld_st_data);
}

/* Callback for htab_traverse.  Loads the final reduction value at the
   join point of all threads, and inserts it in the right place.  */

int
create_loads_for_reductions (reduction_info **slot, struct clsn_data *clsn_data)
{
  struct reduction_info *const red = *slot;
  gimple *stmt;
  gimple_stmt_iterator gsi;
  tree type = TREE_TYPE (reduc_stmt_res (red->reduc_stmt));
  tree load_struct;
  tree name;
  tree x;

  /* If there's no exit phi, the result of the reduction is unused.  */
  if (red->keep_res == NULL)
    return 1;

  gsi = gsi_after_labels (clsn_data->load_bb);
  load_struct = build_simple_mem_ref (clsn_data->load);
  load_struct = build3 (COMPONENT_REF, type, load_struct, red->field,
			NULL_TREE);

  x = load_struct;
  name = PHI_RESULT (red->keep_res);
  stmt = gimple_build_assign (name, x);

  gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);

  for (gsi = gsi_start_phis (gimple_bb (red->keep_res));
       !gsi_end_p (gsi); gsi_next (&gsi))
    if (gsi_stmt (gsi) == red->keep_res)
      {
	remove_phi_node (&gsi, false);
	return 1;
      }
  gcc_unreachable ();
}

/* Load the reduction result that was stored in LD_ST_DATA.
   REDUCTION_LIST describes the list of reductions that the
   loads should be generated for.  */
static void
create_final_loads_for_reduction (reduction_info_table_type *reduction_list,
				  struct clsn_data *ld_st_data)
{
  gimple_stmt_iterator gsi;
  tree t;
  gimple *stmt;

  gsi = gsi_after_labels (ld_st_data->load_bb);
  t = build_fold_addr_expr (ld_st_data->store);
  stmt = gimple_build_assign (ld_st_data->load, t);

  gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);

  reduction_list
    ->traverse <struct clsn_data *, create_loads_for_reductions> (ld_st_data);

}

/* Callback for htab_traverse.  Store the neutral value for the
  particular reduction's operation, e.g. 0 for PLUS_EXPR,
  1 for MULT_EXPR, etc. into the reduction field.
  The reduction is specified in SLOT. The store information is
  passed in DATA.  */

int
create_stores_for_reduction (reduction_info **slot, struct clsn_data *clsn_data)
{
  struct reduction_info *const red = *slot;
  tree t;
  gimple *stmt;
  gimple_stmt_iterator gsi;
  tree type = TREE_TYPE (reduc_stmt_res (red->reduc_stmt));

  gsi = gsi_last_bb (clsn_data->store_bb);
  t = build3 (COMPONENT_REF, type, clsn_data->store, red->field, NULL_TREE);
  stmt = gimple_build_assign (t, red->initial_value);
  gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);

  return 1;
}

/* Callback for htab_traverse.  Creates loads to a field of LOAD in LOAD_BB and
   store to a field of STORE in STORE_BB for the ssa name and its duplicate
   specified in SLOT.  */

int
create_loads_and_stores_for_name (name_to_copy_elt **slot,
				  struct clsn_data *clsn_data)
{
  struct name_to_copy_elt *const elt = *slot;
  tree t;
  gimple *stmt;
  gimple_stmt_iterator gsi;
  tree type = TREE_TYPE (elt->new_name);
  tree load_struct;

  gsi = gsi_last_bb (clsn_data->store_bb);
  t = build3 (COMPONENT_REF, type, clsn_data->store, elt->field, NULL_TREE);
  stmt = gimple_build_assign (t, ssa_name (elt->version));
  gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);

  gsi = gsi_last_bb (clsn_data->load_bb);
  load_struct = build_simple_mem_ref (clsn_data->load);
  t = build3 (COMPONENT_REF, type, load_struct, elt->field, NULL_TREE);
  stmt = gimple_build_assign (elt->new_name, t);
  gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);

  return 1;
}

/* Moves all the variables used in LOOP and defined outside of it (including
   the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
   name) to a structure created for this purpose.  The code

   while (1)
     {
       use (a);
       use (b);
     }

   is transformed this way:

   bb0:
   old.a = a;
   old.b = b;

   bb1:
   a' = new->a;
   b' = new->b;
   while (1)
     {
       use (a');
       use (b');
     }

   `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT.  The
   pointer `new' is intentionally not initialized (the loop will be split to a
   separate function later, and `new' will be initialized from its arguments).
   LD_ST_DATA holds information about the shared data structure used to pass
   information among the threads.  It is initialized here, and
   gen_parallel_loop will pass it to create_call_for_reduction that
   needs this information.  REDUCTION_LIST describes the reductions
   in LOOP.  */

static void
separate_decls_in_region (edge entry, edge exit,
			  reduction_info_table_type *reduction_list,
			  tree *arg_struct, tree *new_arg_struct,
			  struct clsn_data *ld_st_data)

{
  basic_block bb1 = split_edge (entry);
  basic_block bb0 = single_pred (bb1);
  name_to_copy_table_type name_copies (10);
  int_tree_htab_type decl_copies (10);
  unsigned i;
  tree type, type_name, nvar;
  gimple_stmt_iterator gsi;
  struct clsn_data clsn_data;
  auto_vec<basic_block, 3> body;
  basic_block bb;
  basic_block entry_bb = bb1;
  basic_block exit_bb = exit->dest;
  bool has_debug_stmt = false;

  entry = single_succ_edge (entry_bb);
  gather_blocks_in_sese_region (entry_bb, exit_bb, &body);

  FOR_EACH_VEC_ELT (body, i, bb)
    {
      if (bb != entry_bb && bb != exit_bb)
	{
	  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
	    separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
					   &name_copies, &decl_copies);

	  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
	    {
	      gimple *stmt = gsi_stmt (gsi);

	      if (is_gimple_debug (stmt))
		has_debug_stmt = true;
	      else
		separate_decls_in_region_stmt (entry, exit, stmt,
					       &name_copies, &decl_copies);
	    }
	}
    }

  /* Now process debug bind stmts.  We must not create decls while
     processing debug stmts, so we defer their processing so as to
     make sure we will have debug info for as many variables as
     possible (all of those that were dealt with in the loop above),
     and discard those for which we know there's nothing we can
     do.  */
  if (has_debug_stmt)
    FOR_EACH_VEC_ELT (body, i, bb)
      if (bb != entry_bb && bb != exit_bb)
	{
	  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
	    {
	      gimple *stmt = gsi_stmt (gsi);

	      if (is_gimple_debug (stmt))
		{
		  if (separate_decls_in_region_debug (stmt, &name_copies,
						      &decl_copies))
		    {
		      gsi_remove (&gsi, true);
		      continue;
		    }
		}

	      gsi_next (&gsi);
	    }
	}

  if (name_copies.elements () == 0 && reduction_list->elements () == 0)
    {
      /* It may happen that there is nothing to copy (if there are only
         loop carried and external variables in the loop).  */
      *arg_struct = NULL;
      *new_arg_struct = NULL;
    }
  else
    {
      /* Create the type for the structure to store the ssa names to.  */
      type = lang_hooks.types.make_type (RECORD_TYPE);
      type_name = build_decl (UNKNOWN_LOCATION,
			      TYPE_DECL, create_tmp_var_name (".paral_data"),
			      type);
      TYPE_NAME (type) = type_name;

      name_copies.traverse <tree, add_field_for_name> (type);
      if (reduction_list && reduction_list->elements () > 0)
	{
	  /* Create the fields for reductions.  */
	  reduction_list->traverse <tree, add_field_for_reduction> (type);
	}
      layout_type (type);

      /* Create the loads and stores.  */
      *arg_struct = create_tmp_var (type, ".paral_data_store");
      nvar = create_tmp_var (build_pointer_type (type), ".paral_data_load");
      *new_arg_struct = make_ssa_name (nvar);

      ld_st_data->store = *arg_struct;
      ld_st_data->load = *new_arg_struct;
      ld_st_data->store_bb = bb0;
      ld_st_data->load_bb = bb1;

      name_copies
	.traverse <struct clsn_data *, create_loads_and_stores_for_name>
		  (ld_st_data);

      /* Load the calculation from memory (after the join of the threads).  */

      if (reduction_list && reduction_list->elements () > 0)
	{
	  reduction_list
	    ->traverse <struct clsn_data *, create_stores_for_reduction>
	    (ld_st_data);
	  clsn_data.load = make_ssa_name (nvar);
	  clsn_data.load_bb = exit->dest;
	  clsn_data.store = ld_st_data->store;
	  create_final_loads_for_reduction (reduction_list, &clsn_data);
	}
    }
}

/* Returns true if FN was created to run in parallel.  */

bool
parallelized_function_p (tree fndecl)
{
  cgraph_node *node = cgraph_node::get (fndecl);
  gcc_assert (node != NULL);
  return node->parallelized_function;
}

/* Creates and returns an empty function that will receive the body of
   a parallelized loop.  */

static tree
create_loop_fn (location_t loc)
{
  char buf[100];
  char *tname;
  tree decl, type, name, t;
  struct function *act_cfun = cfun;
  static unsigned loopfn_num;

  loc = LOCATION_LOCUS (loc);
  snprintf (buf, 100, "%s.$loopfn", current_function_name ());
  ASM_FORMAT_PRIVATE_NAME (tname, buf, loopfn_num++);
  clean_symbol_name (tname);
  name = get_identifier (tname);
  type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);

  decl = build_decl (loc, FUNCTION_DECL, name, type);
  TREE_STATIC (decl) = 1;
  TREE_USED (decl) = 1;
  DECL_ARTIFICIAL (decl) = 1;
  DECL_IGNORED_P (decl) = 0;
  TREE_PUBLIC (decl) = 0;
  DECL_UNINLINABLE (decl) = 1;
  DECL_EXTERNAL (decl) = 0;
  DECL_CONTEXT (decl) = NULL_TREE;
  DECL_INITIAL (decl) = make_node (BLOCK);

  t = build_decl (loc, RESULT_DECL, NULL_TREE, void_type_node);
  DECL_ARTIFICIAL (t) = 1;
  DECL_IGNORED_P (t) = 1;
  DECL_RESULT (decl) = t;

  t = build_decl (loc, PARM_DECL, get_identifier (".paral_data_param"),
		  ptr_type_node);
  DECL_ARTIFICIAL (t) = 1;
  DECL_ARG_TYPE (t) = ptr_type_node;
  DECL_CONTEXT (t) = decl;
  TREE_USED (t) = 1;
  DECL_ARGUMENTS (decl) = t;

  allocate_struct_function (decl, false);

  /* The call to allocate_struct_function clobbers CFUN, so we need to restore
     it.  */
  set_cfun (act_cfun);

  return decl;
}

/* Replace uses of NAME by VAL in block BB.  */

static void
replace_uses_in_bb_by (tree name, tree val, basic_block bb)
{
  gimple *use_stmt;
  imm_use_iterator imm_iter;

  FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, name)
    {
      if (gimple_bb (use_stmt) != bb)
	continue;

      use_operand_p use_p;
      FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
	SET_USE (use_p, val);
    }
}

/* Do transformation from:

     <bb preheader>:
     ...
     goto <bb header>

     <bb header>:
     ivtmp_a = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
     sum_a = PHI <sum_init (preheader), sum_b (latch)>
     ...
     use (ivtmp_a)
     ...
     sum_b = sum_a + sum_update
     ...
     if (ivtmp_a < n)
       goto <bb latch>;
     else
       goto <bb exit>;

     <bb latch>:
     ivtmp_b = ivtmp_a + 1;
     goto <bb header>

     <bb exit>:
     sum_z = PHI <sum_b (cond[1]), ...>

     [1] Where <bb cond> is single_pred (bb latch); In the simplest case,
	 that's <bb header>.

   to:

     <bb preheader>:
     ...
     goto <bb newheader>

     <bb header>:
     ivtmp_a = PHI <ivtmp_c (latch)>
     sum_a = PHI <sum_c (latch)>
     ...
     use (ivtmp_a)
     ...
     sum_b = sum_a + sum_update
     ...
     goto <bb latch>;

     <bb newheader>:
     ivtmp_c = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
     sum_c = PHI <sum_init (preheader), sum_b (latch)>
     if (ivtmp_c < n + 1)
       goto <bb header>;
     else
       goto <bb newexit>;

     <bb latch>:
     ivtmp_b = ivtmp_a + 1;
     goto <bb newheader>

     <bb newexit>:
     sum_y = PHI <sum_c (newheader)>

     <bb exit>:
     sum_z = PHI <sum_y (newexit), ...>


   In unified diff format:

      <bb preheader>:
      ...
-     goto <bb header>
+     goto <bb newheader>

      <bb header>:
-     ivtmp_a = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
-     sum_a = PHI <sum_init (preheader), sum_b (latch)>
+     ivtmp_a = PHI <ivtmp_c (latch)>
+     sum_a = PHI <sum_c (latch)>
      ...
      use (ivtmp_a)
      ...
      sum_b = sum_a + sum_update
      ...
-     if (ivtmp_a < n)
-       goto <bb latch>;
+     goto <bb latch>;
+
+     <bb newheader>:
+     ivtmp_c = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
+     sum_c = PHI <sum_init (preheader), sum_b (latch)>
+     if (ivtmp_c < n + 1)
+       goto <bb header>;
      else
	goto <bb exit>;

      <bb latch>:
      ivtmp_b = ivtmp_a + 1;
-     goto <bb header>
+     goto <bb newheader>

+    <bb newexit>:
+    sum_y = PHI <sum_c (newheader)>

      <bb exit>:
-     sum_z = PHI <sum_b (cond[1]), ...>
+     sum_z = PHI <sum_y (newexit), ...>

   Note: the example does not show any virtual phis, but these are handled more
   or less as reductions.


   Moves the exit condition of LOOP to the beginning of its header.
   REDUCTION_LIST describes the reductions in LOOP.  BOUND is the new loop
   bound.  */

static void
transform_to_exit_first_loop_alt (struct loop *loop,
				  reduction_info_table_type *reduction_list,
				  tree bound)
{
  basic_block header = loop->header;
  basic_block latch = loop->latch;
  edge exit = single_dom_exit (loop);
  basic_block exit_block = exit->dest;
  gcond *cond_stmt = as_a <gcond *> (last_stmt (exit->src));
  tree control = gimple_cond_lhs (cond_stmt);
  edge e;

  /* Rewriting virtuals into loop-closed ssa normal form makes this
     transformation simpler.  It also ensures that the virtuals are in
     loop-closed ssa normal from after the transformation, which is required by
     create_parallel_loop.  */
  rewrite_virtuals_into_loop_closed_ssa (loop);

  /* Create the new_header block.  */
  basic_block new_header = split_block_before_cond_jump (exit->src);
  edge edge_at_split = single_pred_edge (new_header);

  /* Redirect entry edge to new_header.  */
  edge entry = loop_preheader_edge (loop);
  e = redirect_edge_and_branch (entry, new_header);
  gcc_assert (e == entry);

  /* Redirect post_inc_edge to new_header.  */
  edge post_inc_edge = single_succ_edge (latch);
  e = redirect_edge_and_branch (post_inc_edge, new_header);
  gcc_assert (e == post_inc_edge);

  /* Redirect post_cond_edge to header.  */
  edge post_cond_edge = single_pred_edge (latch);
  e = redirect_edge_and_branch (post_cond_edge, header);
  gcc_assert (e == post_cond_edge);

  /* Redirect edge_at_split to latch.  */
  e = redirect_edge_and_branch (edge_at_split, latch);
  gcc_assert (e == edge_at_split);

  /* Set the new loop bound.  */
  gimple_cond_set_rhs (cond_stmt, bound);
  update_stmt (cond_stmt);

  /* Repair the ssa.  */
  vec<edge_var_map> *v = redirect_edge_var_map_vector (post_inc_edge);
  edge_var_map *vm;
  gphi_iterator gsi;
  int i;
  for (gsi = gsi_start_phis (header), i = 0;
       !gsi_end_p (gsi) && v->iterate (i, &vm);
       gsi_next (&gsi), i++)
    {
      gphi *phi = gsi.phi ();
      tree res_a = PHI_RESULT (phi);

      /* Create new phi.  */
      tree res_c = copy_ssa_name (res_a, phi);
      gphi *nphi = create_phi_node (res_c, new_header);

      /* Replace ivtmp_a with ivtmp_c in condition 'if (ivtmp_a < n)'.  */
      replace_uses_in_bb_by (res_a, res_c, new_header);

      /* Replace ivtmp/sum_b with ivtmp/sum_c in header phi.  */
      add_phi_arg (phi, res_c, post_cond_edge, UNKNOWN_LOCATION);

      /* Replace sum_b with sum_c in exit phi.  */
      tree res_b = redirect_edge_var_map_def (vm);
      replace_uses_in_bb_by (res_b, res_c, exit_block);

      struct reduction_info *red = reduction_phi (reduction_list, phi);
      gcc_assert (virtual_operand_p (res_a)
		  || res_a == control
		  || red != NULL);

      if (red)
	{
	  /* Register the new reduction phi.  */
	  red->reduc_phi = nphi;
	  gimple_set_uid (red->reduc_phi, red->reduc_version);
	}
    }
  gcc_assert (gsi_end_p (gsi) && !v->iterate (i, &vm));

  /* Set the preheader argument of the new phis to ivtmp/sum_init.  */
  flush_pending_stmts (entry);

  /* Set the latch arguments of the new phis to ivtmp/sum_b.  */
  flush_pending_stmts (post_inc_edge);


  basic_block new_exit_block = NULL;
  if (!single_pred_p (exit->dest))
    {
      /* Create a new empty exit block, inbetween the new loop header and the
	 old exit block.  The function separate_decls_in_region needs this block
	 to insert code that is active on loop exit, but not any other path.  */
      new_exit_block = split_edge (exit);
    }

  /* Insert and register the reduction exit phis.  */
  for (gphi_iterator gsi = gsi_start_phis (exit_block);
       !gsi_end_p (gsi);
       gsi_next (&gsi))
    {
      gphi *phi = gsi.phi ();
      gphi *nphi = NULL;
      tree res_z = PHI_RESULT (phi);
      tree res_c;

      if (new_exit_block != NULL)
	{
	  /* Now that we have a new exit block, duplicate the phi of the old
	     exit block in the new exit block to preserve loop-closed ssa.  */
	  edge succ_new_exit_block = single_succ_edge (new_exit_block);
	  edge pred_new_exit_block = single_pred_edge (new_exit_block);
	  tree res_y = copy_ssa_name (res_z, phi);
	  nphi = create_phi_node (res_y, new_exit_block);
	  res_c = PHI_ARG_DEF_FROM_EDGE (phi, succ_new_exit_block);
	  add_phi_arg (nphi, res_c, pred_new_exit_block, UNKNOWN_LOCATION);
	  add_phi_arg (phi, res_y, succ_new_exit_block, UNKNOWN_LOCATION);
	}
      else
	res_c = PHI_ARG_DEF_FROM_EDGE (phi, exit);

      if (virtual_operand_p (res_z))
	continue;

      gimple *reduc_phi = SSA_NAME_DEF_STMT (res_c);
      struct reduction_info *red = reduction_phi (reduction_list, reduc_phi);
      if (red != NULL)
	red->keep_res = (nphi != NULL
			 ? nphi
			 : phi);
    }

  /* We're going to cancel the loop at the end of gen_parallel_loop, but until
     then we're still using some fields, so only bother about fields that are
     still used: header and latch.
     The loop has a new header bb, so we update it.  The latch bb stays the
     same.  */
  loop->header = new_header;

  /* Recalculate dominance info.  */
  free_dominance_info (CDI_DOMINATORS);
  calculate_dominance_info (CDI_DOMINATORS);

  checking_verify_ssa (true, true);
}

/* Tries to moves the exit condition of LOOP to the beginning of its header
   without duplication of the loop body.  NIT is the number of iterations of the
   loop.  REDUCTION_LIST describes the reductions in LOOP.  Return true if
   transformation is successful.  */

static bool
try_transform_to_exit_first_loop_alt (struct loop *loop,
				      reduction_info_table_type *reduction_list,
				      tree nit)
{
  /* Check whether the latch contains a single statement.  */
  if (!gimple_seq_nondebug_singleton_p (bb_seq (loop->latch)))
    return false;

  /* Check whether the latch contains no phis.  */
  if (phi_nodes (loop->latch) != NULL)
    return false;

  /* Check whether the latch contains the loop iv increment.  */
  edge back = single_succ_edge (loop->latch);
  edge exit = single_dom_exit (loop);
  gcond *cond_stmt = as_a <gcond *> (last_stmt (exit->src));
  tree control = gimple_cond_lhs (cond_stmt);
  gphi *phi = as_a <gphi *> (SSA_NAME_DEF_STMT (control));
  tree inc_res = gimple_phi_arg_def (phi, back->dest_idx);
  if (gimple_bb (SSA_NAME_DEF_STMT (inc_res)) != loop->latch)
    return false;

  /* Check whether there's no code between the loop condition and the latch.  */
  if (!single_pred_p (loop->latch)
      || single_pred (loop->latch) != exit->src)
    return false;

  tree alt_bound = NULL_TREE;
  tree nit_type = TREE_TYPE (nit);

  /* Figure out whether nit + 1 overflows.  */
  if (TREE_CODE (nit) == INTEGER_CST)
    {
      if (!tree_int_cst_equal (nit, TYPE_MAXVAL (nit_type)))
	{
	  alt_bound = fold_build2_loc (UNKNOWN_LOCATION, PLUS_EXPR, nit_type,
				       nit, build_one_cst (nit_type));

	  gcc_assert (TREE_CODE (alt_bound) == INTEGER_CST);
	  transform_to_exit_first_loop_alt (loop, reduction_list, alt_bound);
	  return true;
	}
      else
	{
	  /* Todo: Figure out if we can trigger this, if it's worth to handle
	     optimally, and if we can handle it optimally.  */
	  return false;
	}
    }

  gcc_assert (TREE_CODE (nit) == SSA_NAME);

  /* Variable nit is the loop bound as returned by canonicalize_loop_ivs, for an
     iv with base 0 and step 1 that is incremented in the latch, like this:

     <bb header>:
     # iv_1 = PHI <0 (preheader), iv_2 (latch)>
     ...
     if (iv_1 < nit)
       goto <bb latch>;
     else
       goto <bb exit>;

     <bb latch>:
     iv_2 = iv_1 + 1;
     goto <bb header>;

     The range of iv_1 is [0, nit].  The latch edge is taken for
     iv_1 == [0, nit - 1] and the exit edge is taken for iv_1 == nit.  So the
     number of latch executions is equal to nit.

     The function max_loop_iterations gives us the maximum number of latch
     executions, so it gives us the maximum value of nit.  */
  widest_int nit_max;
  if (!max_loop_iterations (loop, &nit_max))
    return false;

  /* Check if nit + 1 overflows.  */
  widest_int type_max = wi::to_widest (TYPE_MAXVAL (nit_type));
  if (!wi::lts_p (nit_max, type_max))
    return false;

  gimple *def = SSA_NAME_DEF_STMT (nit);

  /* Try to find nit + 1, in the form of n in an assignment nit = n - 1.  */
  if (def
      && is_gimple_assign (def)
      && gimple_assign_rhs_code (def) == PLUS_EXPR)
    {
      tree op1 = gimple_assign_rhs1 (def);
      tree op2 = gimple_assign_rhs2 (def);
      if (integer_minus_onep (op1))
	alt_bound = op2;
      else if (integer_minus_onep (op2))
	alt_bound = op1;
    }

  /* If not found, insert nit + 1.  */
  if (alt_bound == NULL_TREE)
    {
      alt_bound = fold_build2 (PLUS_EXPR, nit_type, nit,
			       build_int_cst_type (nit_type, 1));

      gimple_stmt_iterator gsi = gsi_last_bb (loop_preheader_edge (loop)->src);

      alt_bound
	= force_gimple_operand_gsi (&gsi, alt_bound, true, NULL_TREE, false,
				    GSI_CONTINUE_LINKING);
    }

  transform_to_exit_first_loop_alt (loop, reduction_list, alt_bound);
  return true;
}

/* Moves the exit condition of LOOP to the beginning of its header.  NIT is the
   number of iterations of the loop.  REDUCTION_LIST describes the reductions in
   LOOP.  */

static void
transform_to_exit_first_loop (struct loop *loop,
			      reduction_info_table_type *reduction_list,
			      tree nit)
{
  basic_block *bbs, *nbbs, ex_bb, orig_header;
  unsigned n;
  bool ok;
  edge exit = single_dom_exit (loop), hpred;
  tree control, control_name, res, t;
  gphi *phi, *nphi;
  gassign *stmt;
  gcond *cond_stmt, *cond_nit;
  tree nit_1;

  split_block_after_labels (loop->header);
  orig_header = single_succ (loop->header);
  hpred = single_succ_edge (loop->header);

  cond_stmt = as_a <gcond *> (last_stmt (exit->src));
  control = gimple_cond_lhs (cond_stmt);
  gcc_assert (gimple_cond_rhs (cond_stmt) == nit);

  /* Make sure that we have phi nodes on exit for all loop header phis
     (create_parallel_loop requires that).  */
  for (gphi_iterator gsi = gsi_start_phis (loop->header);
       !gsi_end_p (gsi);
       gsi_next (&gsi))
    {
      phi = gsi.phi ();
      res = PHI_RESULT (phi);
      t = copy_ssa_name (res, phi);
      SET_PHI_RESULT (phi, t);
      nphi = create_phi_node (res, orig_header);
      add_phi_arg (nphi, t, hpred, UNKNOWN_LOCATION);

      if (res == control)
	{
	  gimple_cond_set_lhs (cond_stmt, t);
	  update_stmt (cond_stmt);
	  control = t;
	}
    }

  bbs = get_loop_body_in_dom_order (loop);

  for (n = 0; bbs[n] != exit->src; n++)
   continue;
  nbbs = XNEWVEC (basic_block, n);
  ok = gimple_duplicate_sese_tail (single_succ_edge (loop->header), exit,
				   bbs + 1, n, nbbs);
  gcc_assert (ok);
  free (bbs);
  ex_bb = nbbs[0];
  free (nbbs);

  /* Other than reductions, the only gimple reg that should be copied
     out of the loop is the control variable.  */
  exit = single_dom_exit (loop);
  control_name = NULL_TREE;
  for (gphi_iterator gsi = gsi_start_phis (ex_bb);
       !gsi_end_p (gsi); )
    {
      phi = gsi.phi ();
      res = PHI_RESULT (phi);
      if (virtual_operand_p (res))
	{
	  gsi_next (&gsi);
	  continue;
	}

      /* Check if it is a part of reduction.  If it is,
         keep the phi at the reduction's keep_res field.  The
         PHI_RESULT of this phi is the resulting value of the reduction
         variable when exiting the loop.  */

      if (reduction_list->elements () > 0)
	{
	  struct reduction_info *red;

	  tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
	  red = reduction_phi (reduction_list, SSA_NAME_DEF_STMT (val));
	  if (red)
	    {
	      red->keep_res = phi;
	      gsi_next (&gsi);
	      continue;
	    }
	}
      gcc_assert (control_name == NULL_TREE
		  && SSA_NAME_VAR (res) == SSA_NAME_VAR (control));
      control_name = res;
      remove_phi_node (&gsi, false);
    }
  gcc_assert (control_name != NULL_TREE);

  /* Initialize the control variable to number of iterations
     according to the rhs of the exit condition.  */
  gimple_stmt_iterator gsi = gsi_after_labels (ex_bb);
  cond_nit = as_a <gcond *> (last_stmt (exit->src));
  nit_1 =  gimple_cond_rhs (cond_nit);
  nit_1 = force_gimple_operand_gsi (&gsi,
				  fold_convert (TREE_TYPE (control_name), nit_1),
				  false, NULL_TREE, false, GSI_SAME_STMT);
  stmt = gimple_build_assign (control_name, nit_1);
  gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
}

/* Create the parallel constructs for LOOP as described in gen_parallel_loop.
   LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
   NEW_DATA is the variable that should be initialized from the argument
   of LOOP_FN.  N_THREADS is the requested number of threads.  */

static void
create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
		      tree new_data, unsigned n_threads, location_t loc,
		      bool oacc_kernels_p)
{
  gimple_stmt_iterator gsi;
  basic_block for_bb, ex_bb, continue_bb;
  tree t, param;
  gomp_parallel *omp_par_stmt;
  gimple *omp_return_stmt1, *omp_return_stmt2;
  gimple *phi;
  gcond *cond_stmt;
  gomp_for *for_stmt;
  gomp_continue *omp_cont_stmt;
  tree cvar, cvar_init, initvar, cvar_next, cvar_base, type;
  edge exit, nexit, guard, end, e;

  /* Prepare the GIMPLE_OMP_PARALLEL statement.  */
  if (oacc_kernels_p)
    {
      tree clause = build_omp_clause (loc, OMP_CLAUSE_NUM_GANGS);
      OMP_CLAUSE_NUM_GANGS_EXPR (clause)
	= build_int_cst (integer_type_node, n_threads);
      set_oacc_fn_attrib (cfun->decl, clause, true, NULL);
    }
  else
    {
      basic_block bb = loop_preheader_edge (loop)->src;
      basic_block paral_bb = single_pred (bb);
      gsi = gsi_last_bb (paral_bb);

      t = build_omp_clause (loc, OMP_CLAUSE_NUM_THREADS);
      OMP_CLAUSE_NUM_THREADS_EXPR (t)
	= build_int_cst (integer_type_node, n_threads);
      omp_par_stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
      gimple_set_location (omp_par_stmt, loc);

      gsi_insert_after (&gsi, omp_par_stmt, GSI_NEW_STMT);

      /* Initialize NEW_DATA.  */
      if (data)
	{
	  gassign *assign_stmt;

	  gsi = gsi_after_labels (bb);

	  param = make_ssa_name (DECL_ARGUMENTS (loop_fn));
	  assign_stmt = gimple_build_assign (param, build_fold_addr_expr (data));
	  gsi_insert_before (&gsi, assign_stmt, GSI_SAME_STMT);

	  assign_stmt = gimple_build_assign (new_data,
					     fold_convert (TREE_TYPE (new_data), param));
	  gsi_insert_before (&gsi, assign_stmt, GSI_SAME_STMT);
	}

      /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL.  */
      bb = split_loop_exit_edge (single_dom_exit (loop));
      gsi = gsi_last_bb (bb);
      omp_return_stmt1 = gimple_build_omp_return (false);
      gimple_set_location (omp_return_stmt1, loc);
      gsi_insert_after (&gsi, omp_return_stmt1, GSI_NEW_STMT);
    }

  /* Extract data for GIMPLE_OMP_FOR.  */
  gcc_assert (loop->header == single_dom_exit (loop)->src);
  cond_stmt = as_a <gcond *> (last_stmt (loop->header));

  cvar = gimple_cond_lhs (cond_stmt);
  cvar_base = SSA_NAME_VAR (cvar);
  phi = SSA_NAME_DEF_STMT (cvar);
  cvar_init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
  initvar = copy_ssa_name (cvar);
  SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)),
	   initvar);
  cvar_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));

  gsi = gsi_last_nondebug_bb (loop->latch);
  gcc_assert (gsi_stmt (gsi) == SSA_NAME_DEF_STMT (cvar_next));
  gsi_remove (&gsi, true);

  /* Prepare cfg.  */
  for_bb = split_edge (loop_preheader_edge (loop));
  ex_bb = split_loop_exit_edge (single_dom_exit (loop));
  extract_true_false_edges_from_block (loop->header, &nexit, &exit);
  gcc_assert (exit == single_dom_exit (loop));

  guard = make_edge (for_bb, ex_bb, 0);
  /* Split the latch edge, so LOOPS_HAVE_SIMPLE_LATCHES is still valid.  */
  loop->latch = split_edge (single_succ_edge (loop->latch));
  single_pred_edge (loop->latch)->flags = 0;
  end = make_edge (single_pred (loop->latch), ex_bb, EDGE_FALLTHRU);
  rescan_loop_exit (end, true, false);

  for (gphi_iterator gpi = gsi_start_phis (ex_bb);
       !gsi_end_p (gpi); gsi_next (&gpi))
    {
      source_location locus;
      gphi *phi = gpi.phi ();
      tree def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
      gimple *def_stmt = SSA_NAME_DEF_STMT (def);

      /* If the exit phi is not connected to a header phi in the same loop, this
	 value is not modified in the loop, and we're done with this phi.  */
      if (!(gimple_code (def_stmt) == GIMPLE_PHI
	    && gimple_bb (def_stmt) == loop->header))
	{
	  locus = gimple_phi_arg_location_from_edge (phi, exit);
	  add_phi_arg (phi, def, guard, locus);
	  add_phi_arg (phi, def, end, locus);
	  continue;
	}

      gphi *stmt = as_a <gphi *> (def_stmt);
      def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_preheader_edge (loop));
      locus = gimple_phi_arg_location_from_edge (stmt,
						 loop_preheader_edge (loop));
      add_phi_arg (phi, def, guard, locus);

      def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_latch_edge (loop));
      locus = gimple_phi_arg_location_from_edge (stmt, loop_latch_edge (loop));
      add_phi_arg (phi, def, end, locus);
    }
  e = redirect_edge_and_branch (exit, nexit->dest);
  PENDING_STMT (e) = NULL;

  /* Emit GIMPLE_OMP_FOR.  */
  if (oacc_kernels_p)
    /* In combination with the NUM_GANGS on the parallel.  */
    t = build_omp_clause (loc, OMP_CLAUSE_GANG);
  else
    {
      t = build_omp_clause (loc, OMP_CLAUSE_SCHEDULE);
      int chunk_size = PARAM_VALUE (PARAM_PARLOOPS_CHUNK_SIZE);
      enum PARAM_PARLOOPS_SCHEDULE_KIND schedule_type \
	= (enum PARAM_PARLOOPS_SCHEDULE_KIND) PARAM_VALUE (PARAM_PARLOOPS_SCHEDULE);
      switch (schedule_type)
	{
	case PARAM_PARLOOPS_SCHEDULE_KIND_static:
	  OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
	  break;
	case PARAM_PARLOOPS_SCHEDULE_KIND_dynamic:
	  OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_DYNAMIC;
	  break;
	case PARAM_PARLOOPS_SCHEDULE_KIND_guided:
	  OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_GUIDED;
	  break;
	case PARAM_PARLOOPS_SCHEDULE_KIND_auto:
	  OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_AUTO;
	  chunk_size = 0;
	  break;
	case PARAM_PARLOOPS_SCHEDULE_KIND_runtime:
	  OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_RUNTIME;
	  chunk_size = 0;
	  break;
	default:
	  gcc_unreachable ();
	}
      if (chunk_size != 0)
	OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (t)
	  = build_int_cst (integer_type_node, chunk_size);
    }

  for_stmt = gimple_build_omp_for (NULL,
				   (oacc_kernels_p
				    ? GF_OMP_FOR_KIND_OACC_LOOP
				    : GF_OMP_FOR_KIND_FOR),
				   t, 1, NULL);

  gimple_cond_set_lhs (cond_stmt, cvar_base);
  type = TREE_TYPE (cvar);
  gimple_set_location (for_stmt, loc);
  gimple_omp_for_set_index (for_stmt, 0, initvar);
  gimple_omp_for_set_initial (for_stmt, 0, cvar_init);
  gimple_omp_for_set_final (for_stmt, 0, gimple_cond_rhs (cond_stmt));
  gimple_omp_for_set_cond (for_stmt, 0, gimple_cond_code (cond_stmt));
  gimple_omp_for_set_incr (for_stmt, 0, build2 (PLUS_EXPR, type,
						cvar_base,
						build_int_cst (type, 1)));

  gsi = gsi_last_bb (for_bb);
  gsi_insert_after (&gsi, for_stmt, GSI_NEW_STMT);
  SSA_NAME_DEF_STMT (initvar) = for_stmt;

  /* Emit GIMPLE_OMP_CONTINUE.  */
  continue_bb = single_pred (loop->latch);
  gsi = gsi_last_bb (continue_bb);
  omp_cont_stmt = gimple_build_omp_continue (cvar_next, cvar);
  gimple_set_location (omp_cont_stmt, loc);
  gsi_insert_after (&gsi, omp_cont_stmt, GSI_NEW_STMT);
  SSA_NAME_DEF_STMT (cvar_next) = omp_cont_stmt;

  /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR.  */
  gsi = gsi_last_bb (ex_bb);
  omp_return_stmt2 = gimple_build_omp_return (true);
  gimple_set_location (omp_return_stmt2, loc);
  gsi_insert_after (&gsi, omp_return_stmt2, GSI_NEW_STMT);

  /* After the above dom info is hosed.  Re-compute it.  */
  free_dominance_info (CDI_DOMINATORS);
  calculate_dominance_info (CDI_DOMINATORS);
}

/* Generates code to execute the iterations of LOOP in N_THREADS
   threads in parallel.

   NITER describes number of iterations of LOOP.
   REDUCTION_LIST describes the reductions existent in the LOOP.  */

static void
gen_parallel_loop (struct loop *loop,
		   reduction_info_table_type *reduction_list,
		   unsigned n_threads, struct tree_niter_desc *niter,
		   bool oacc_kernels_p)
{
  tree many_iterations_cond, type, nit;
  tree arg_struct, new_arg_struct;
  gimple_seq stmts;
  edge entry, exit;
  struct clsn_data clsn_data;
  unsigned prob;
  location_t loc;
  gimple *cond_stmt;
  unsigned int m_p_thread=2;

  /* From

     ---------------------------------------------------------------------
     loop
       {
	 IV = phi (INIT, IV + STEP)
	 BODY1;
	 if (COND)
	   break;
	 BODY2;
       }
     ---------------------------------------------------------------------

     with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
     we generate the following code:

     ---------------------------------------------------------------------

     if (MAY_BE_ZERO
     || NITER < MIN_PER_THREAD * N_THREADS)
     goto original;

     BODY1;
     store all local loop-invariant variables used in body of the loop to DATA.
     GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
     load the variables from DATA.
     GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
     BODY2;
     BODY1;
     GIMPLE_OMP_CONTINUE;
     GIMPLE_OMP_RETURN         -- GIMPLE_OMP_FOR
     GIMPLE_OMP_RETURN         -- GIMPLE_OMP_PARALLEL
     goto end;

     original:
     loop
       {
	 IV = phi (INIT, IV + STEP)
	 BODY1;
	 if (COND)
	   break;
	 BODY2;
       }

     end:

   */

  /* Create two versions of the loop -- in the old one, we know that the
     number of iterations is large enough, and we will transform it into the
     loop that will be split to loop_fn, the new one will be used for the
     remaining iterations.  */

  /* We should compute a better number-of-iterations value for outer loops.
     That is, if we have
 
    for (i = 0; i < n; ++i)
      for (j = 0; j < m; ++j)
        ...

    we should compute nit = n * m, not nit = n.  
    Also may_be_zero handling would need to be adjusted.  */

  type = TREE_TYPE (niter->niter);
  nit = force_gimple_operand (unshare_expr (niter->niter), &stmts, true,
			      NULL_TREE);
  if (stmts)
    gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);

  if (!oacc_kernels_p)
    {
      if (loop->inner)
	m_p_thread=2;
      else
	m_p_thread=MIN_PER_THREAD;

      many_iterations_cond =
	fold_build2 (GE_EXPR, boolean_type_node,
		     nit, build_int_cst (type, m_p_thread * n_threads));

      many_iterations_cond
	= fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
		       invert_truthvalue (unshare_expr (niter->may_be_zero)),
		       many_iterations_cond);
      many_iterations_cond
	= force_gimple_operand (many_iterations_cond, &stmts, false, NULL_TREE);
      if (stmts)
	gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
      if (!is_gimple_condexpr (many_iterations_cond))
	{
	  many_iterations_cond
	    = force_gimple_operand (many_iterations_cond, &stmts,
				    true, NULL_TREE);
	  if (stmts)
	    gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop),
					      stmts);
	}

      initialize_original_copy_tables ();

      /* We assume that the loop usually iterates a lot.  */
      prob = 4 * REG_BR_PROB_BASE / 5;
      loop_version (loop, many_iterations_cond, NULL,
		    prob, prob, REG_BR_PROB_BASE - prob, true);
      update_ssa (TODO_update_ssa);
      free_original_copy_tables ();
    }

  /* Base all the induction variables in LOOP on a single control one.  */
  canonicalize_loop_ivs (loop, &nit, true);

  /* Ensure that the exit condition is the first statement in the loop.
     The common case is that latch of the loop is empty (apart from the
     increment) and immediately follows the loop exit test.  Attempt to move the
     entry of the loop directly before the exit check and increase the number of
     iterations of the loop by one.  */
  if (try_transform_to_exit_first_loop_alt (loop, reduction_list, nit))
    {
      if (dump_file
	  && (dump_flags & TDF_DETAILS))
	fprintf (dump_file,
		 "alternative exit-first loop transform succeeded"
		 " for loop %d\n", loop->num);
    }
  else
    {
      if (oacc_kernels_p)
	n_threads = 1;

      /* Fall back on the method that handles more cases, but duplicates the
	 loop body: move the exit condition of LOOP to the beginning of its
	 header, and duplicate the part of the last iteration that gets disabled
	 to the exit of the loop.  */
      transform_to_exit_first_loop (loop, reduction_list, nit);
    }

  /* Generate initializations for reductions.  */
  if (reduction_list->elements () > 0)
    reduction_list->traverse <struct loop *, initialize_reductions> (loop);

  /* Eliminate the references to local variables from the loop.  */
  gcc_assert (single_exit (loop));
  entry = loop_preheader_edge (loop);
  exit = single_dom_exit (loop);

  /* This rewrites the body in terms of new variables.  This has already
     been done for oacc_kernels_p in pass_lower_omp/lower_omp ().  */
  if (!oacc_kernels_p)
    {
      eliminate_local_variables (entry, exit);
      /* In the old loop, move all variables non-local to the loop to a
	 structure and back, and create separate decls for the variables used in
	 loop.  */
      separate_decls_in_region (entry, exit, reduction_list, &arg_struct,
				&new_arg_struct, &clsn_data);
    }
  else
    {
      arg_struct = NULL_TREE;
      new_arg_struct = NULL_TREE;
      clsn_data.load = NULL_TREE;
      clsn_data.load_bb = exit->dest;
      clsn_data.store = NULL_TREE;
      clsn_data.store_bb = NULL;
    }

  /* Create the parallel constructs.  */
  loc = UNKNOWN_LOCATION;
  cond_stmt = last_stmt (loop->header);
  if (cond_stmt)
    loc = gimple_location (cond_stmt);
  create_parallel_loop (loop, create_loop_fn (loc), arg_struct, new_arg_struct,
			n_threads, loc, oacc_kernels_p);
  if (reduction_list->elements () > 0)
    create_call_for_reduction (loop, reduction_list, &clsn_data);

  scev_reset ();

  /* Free loop bound estimations that could contain references to
     removed statements.  */
  FOR_EACH_LOOP (loop, 0)
    free_numbers_of_iterations_estimates_loop (loop);
}

/* Returns true when LOOP contains vector phi nodes.  */

static bool
loop_has_vector_phi_nodes (struct loop *loop ATTRIBUTE_UNUSED)
{
  unsigned i;
  basic_block *bbs = get_loop_body_in_dom_order (loop);
  gphi_iterator gsi;
  bool res = true;

  for (i = 0; i < loop->num_nodes; i++)
    for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
      if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi.phi ()))) == VECTOR_TYPE)
	goto end;

  res = false;
 end:
  free (bbs);
  return res;
}

/* Create a reduction_info struct, initialize it with REDUC_STMT
   and PHI, insert it to the REDUCTION_LIST.  */

static void
build_new_reduction (reduction_info_table_type *reduction_list,
		     gimple *reduc_stmt, gphi *phi)
{
  reduction_info **slot;
  struct reduction_info *new_reduction;
  enum tree_code reduction_code;

  gcc_assert (reduc_stmt);

  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      fprintf (dump_file,
	       "Detected reduction. reduction stmt is:\n");
      print_gimple_stmt (dump_file, reduc_stmt, 0, 0);
      fprintf (dump_file, "\n");
    }

  if (gimple_code (reduc_stmt) == GIMPLE_PHI)
    {
      tree op1 = PHI_ARG_DEF (reduc_stmt, 0);
      gimple *def1 = SSA_NAME_DEF_STMT (op1);
      reduction_code = gimple_assign_rhs_code (def1);
    }

  else
    reduction_code = gimple_assign_rhs_code (reduc_stmt);

  new_reduction = XCNEW (struct reduction_info);

  new_reduction->reduc_stmt = reduc_stmt;
  new_reduction->reduc_phi = phi;
  new_reduction->reduc_version = SSA_NAME_VERSION (gimple_phi_result (phi));
  new_reduction->reduction_code = reduction_code;
  slot = reduction_list->find_slot (new_reduction, INSERT);
  *slot = new_reduction;
}

/* Callback for htab_traverse.  Sets gimple_uid of reduc_phi stmts.  */

int
set_reduc_phi_uids (reduction_info **slot, void *data ATTRIBUTE_UNUSED)
{
  struct reduction_info *const red = *slot;
  gimple_set_uid (red->reduc_phi, red->reduc_version);
  return 1;
}

/* Detect all reductions in the LOOP, insert them into REDUCTION_LIST.  */

static void
gather_scalar_reductions (loop_p loop, reduction_info_table_type *reduction_list)
{
  gphi_iterator gsi;
  loop_vec_info simple_loop_info;
  loop_vec_info simple_inner_loop_info = NULL;
  bool allow_double_reduc = true;

  if (!stmt_vec_info_vec.exists ())
    init_stmt_vec_info_vec ();

  simple_loop_info = vect_analyze_loop_form (loop);
  if (simple_loop_info == NULL)
    goto gather_done;

  for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
    {
      gphi *phi = gsi.phi ();
      affine_iv iv;
      tree res = PHI_RESULT (phi);
      bool double_reduc;

      if (virtual_operand_p (res))
	continue;

      if (simple_iv (loop, loop, res, &iv, true))
	continue;

      gimple *reduc_stmt
	= vect_force_simple_reduction (simple_loop_info, phi, true,
				       &double_reduc, true);
      if (!reduc_stmt)
	continue;

      if (double_reduc)
	{
	  if (!allow_double_reduc
	      || loop->inner->inner != NULL)
	    continue;

	  if (!simple_inner_loop_info)
	    {
	      simple_inner_loop_info = vect_analyze_loop_form (loop->inner);
	      if (!simple_inner_loop_info)
		{
		  allow_double_reduc = false;
		  continue;
		}
	    }

	  use_operand_p use_p;
	  gimple *inner_stmt;
	  bool single_use_p = single_imm_use (res, &use_p, &inner_stmt);
	  gcc_assert (single_use_p);
	  if (gimple_code (inner_stmt) != GIMPLE_PHI)
	    continue;
	  gphi *inner_phi = as_a <gphi *> (inner_stmt);
	  if (simple_iv (loop->inner, loop->inner, PHI_RESULT (inner_phi),
			 &iv, true))
	    continue;

	  gimple *inner_reduc_stmt
	    = vect_force_simple_reduction (simple_inner_loop_info, inner_phi,
					   true, &double_reduc, true);
	  gcc_assert (!double_reduc);
	  if (inner_reduc_stmt == NULL)
	    continue;
	}

      build_new_reduction (reduction_list, reduc_stmt, phi);
    }
  destroy_loop_vec_info (simple_loop_info, true);
  destroy_loop_vec_info (simple_inner_loop_info, true);

 gather_done:
  /* Release the claim on gimple_uid.  */
  free_stmt_vec_info_vec ();

  if (reduction_list->elements () == 0)
    return;

  /* As gimple_uid is used by the vectorizer in between vect_analyze_loop_form
     and free_stmt_vec_info_vec, we can set gimple_uid of reduc_phi stmts only
     now.  */
  basic_block bb;
  FOR_EACH_BB_FN (bb, cfun)
    for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
      gimple_set_uid (gsi_stmt (gsi), (unsigned int)-1);
  reduction_list->traverse <void *, set_reduc_phi_uids> (NULL);
}

/* Try to initialize NITER for code generation part.  */

static bool
try_get_loop_niter (loop_p loop, struct tree_niter_desc *niter)
{
  edge exit = single_dom_exit (loop);

  gcc_assert (exit);

  /* We need to know # of iterations, and there should be no uses of values
     defined inside loop outside of it, unless the values are invariants of
     the loop.  */
  if (!number_of_iterations_exit (loop, exit, niter, false))
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file, "  FAILED: number of iterations not known\n");
      return false;
    }

  return true;
}

/* Return the default def of the first function argument.  */

static tree
get_omp_data_i_param (void)
{
  tree decl = DECL_ARGUMENTS (cfun->decl);
  gcc_assert (DECL_CHAIN (decl) == NULL_TREE);
  return ssa_default_def (cfun, decl);
}

/* For PHI in loop header of LOOP, look for pattern:

   <bb preheader>
   .omp_data_i = &.omp_data_arr;
   addr = .omp_data_i->sum;
   sum_a = *addr;

   <bb header>:
   sum_b = PHI <sum_a (preheader), sum_c (latch)>

   and return addr.  Otherwise, return NULL_TREE.  */

static tree
find_reduc_addr (struct loop *loop, gphi *phi)
{
  edge e = loop_preheader_edge (loop);
  tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
  gimple *stmt = SSA_NAME_DEF_STMT (arg);
  if (!gimple_assign_single_p (stmt))
    return NULL_TREE;
  tree memref = gimple_assign_rhs1 (stmt);
  if (TREE_CODE (memref) != MEM_REF)
    return NULL_TREE;
  tree addr = TREE_OPERAND (memref, 0);

  gimple *stmt2 = SSA_NAME_DEF_STMT (addr);
  if (!gimple_assign_single_p (stmt2))
    return NULL_TREE;
  tree compref = gimple_assign_rhs1 (stmt2);
  if (TREE_CODE (compref) != COMPONENT_REF)
    return NULL_TREE;
  tree addr2 = TREE_OPERAND (compref, 0);
  if (TREE_CODE (addr2) != MEM_REF)
    return NULL_TREE;
  addr2 = TREE_OPERAND (addr2, 0);
  if (TREE_CODE (addr2) != SSA_NAME
      || addr2 != get_omp_data_i_param ())
    return NULL_TREE;

  return addr;
}

/* Try to initialize REDUCTION_LIST for code generation part.
   REDUCTION_LIST describes the reductions.  */

static bool
try_create_reduction_list (loop_p loop,
			   reduction_info_table_type *reduction_list,
			   bool oacc_kernels_p)
{
  edge exit = single_dom_exit (loop);
  gphi_iterator gsi;

  gcc_assert (exit);

  /* Try to get rid of exit phis.  */
  final_value_replacement_loop (loop);

  gather_scalar_reductions (loop, reduction_list);


  for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
    {
      gphi *phi = gsi.phi ();
      struct reduction_info *red;
      imm_use_iterator imm_iter;
      use_operand_p use_p;
      gimple *reduc_phi;
      tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);

      if (!virtual_operand_p (val))
	{
	  if (dump_file && (dump_flags & TDF_DETAILS))
	    {
	      fprintf (dump_file, "phi is ");
	      print_gimple_stmt (dump_file, phi, 0, 0);
	      fprintf (dump_file, "arg of phi to exit:   value ");
	      print_generic_expr (dump_file, val, 0);
	      fprintf (dump_file, " used outside loop\n");
	      fprintf (dump_file,
		       "  checking if it is part of reduction pattern:\n");
	    }
	  if (reduction_list->elements () == 0)
	    {
	      if (dump_file && (dump_flags & TDF_DETAILS))
		fprintf (dump_file,
			 "  FAILED: it is not a part of reduction.\n");
	      return false;
	    }
	  reduc_phi = NULL;
	  FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
	    {
	      if (!gimple_debug_bind_p (USE_STMT (use_p))
		  && flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
		{
		  reduc_phi = USE_STMT (use_p);
		  break;
		}
	    }
	  red = reduction_phi (reduction_list, reduc_phi);
	  if (red == NULL)
	    {
	      if (dump_file && (dump_flags & TDF_DETAILS))
		fprintf (dump_file,
			 "  FAILED: it is not a part of reduction.\n");
	      return false;
	    }
	  if (red->keep_res != NULL)
	    {
	      if (dump_file && (dump_flags & TDF_DETAILS))
		fprintf (dump_file,
			 "  FAILED: reduction has multiple exit phis.\n");
	      return false;
	    }
	  red->keep_res = phi;
	  if (dump_file && (dump_flags & TDF_DETAILS))
	    {
	      fprintf (dump_file, "reduction phi is  ");
	      print_gimple_stmt (dump_file, red->reduc_phi, 0, 0);
	      fprintf (dump_file, "reduction stmt is  ");
	      print_gimple_stmt (dump_file, red->reduc_stmt, 0, 0);
	    }
	}
    }

  /* The iterations of the loop may communicate only through bivs whose
     iteration space can be distributed efficiently.  */
  for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
    {
      gphi *phi = gsi.phi ();
      tree def = PHI_RESULT (phi);
      affine_iv iv;

      if (!virtual_operand_p (def) && !simple_iv (loop, loop, def, &iv, true))
	{
	  struct reduction_info *red;

	  red = reduction_phi (reduction_list, phi);
	  if (red == NULL)
	    {
	      if (dump_file && (dump_flags & TDF_DETAILS))
		fprintf (dump_file,
			 "  FAILED: scalar dependency between iterations\n");
	      return false;
	    }
	}
    }

  if (oacc_kernels_p)
    {
      for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi);
	   gsi_next (&gsi))
	{
	  gphi *phi = gsi.phi ();
	  tree def = PHI_RESULT (phi);
	  affine_iv iv;

	  if (!virtual_operand_p (def)
	      && !simple_iv (loop, loop, def, &iv, true))
	    {
	      tree addr = find_reduc_addr (loop, phi);
	      if (addr == NULL_TREE)
		return false;
	      struct reduction_info *red = reduction_phi (reduction_list, phi);
	      red->reduc_addr = addr;
	    }
	}
    }

  return true;
}

/* Return true if LOOP contains phis with ADDR_EXPR in args.  */

static bool
loop_has_phi_with_address_arg (struct loop *loop)
{
  basic_block *bbs = get_loop_body (loop);
  bool res = false;

  unsigned i, j;
  gphi_iterator gsi;
  for (i = 0; i < loop->num_nodes; i++)
    for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
      {
	gphi *phi = gsi.phi ();
	for (j = 0; j < gimple_phi_num_args (phi); j++)
	  {
	    tree arg = gimple_phi_arg_def (phi, j);
	    if (TREE_CODE (arg) == ADDR_EXPR)
	      {
		/* This should be handled by eliminate_local_variables, but that
		   function currently ignores phis.  */
		res = true;
		goto end;
	      }
	  }
      }
 end:
  free (bbs);

  return res;
}

/* Return true if memory ref REF (corresponding to the stmt at GSI in
   REGIONS_BB[I]) conflicts with the statements in REGIONS_BB[I] after gsi,
   or the statements in REGIONS_BB[I + n].  REF_IS_STORE indicates if REF is a
   store.  Ignore conflicts with SKIP_STMT.  */

static bool
ref_conflicts_with_region (gimple_stmt_iterator gsi, ao_ref *ref,
			   bool ref_is_store, vec<basic_block> region_bbs,
			   unsigned int i, gimple *skip_stmt)
{
  basic_block bb = region_bbs[i];
  gsi_next (&gsi);

  while (true)
    {
      for (; !gsi_end_p (gsi);
	   gsi_next (&gsi))
	{
	  gimple *stmt = gsi_stmt (gsi);
	  if (stmt == skip_stmt)
	    {
	      if (dump_file)
		{
		  fprintf (dump_file, "skipping reduction store: ");
		  print_gimple_stmt (dump_file, stmt, 0, 0);
		}
	      continue;
	    }

	  if (!gimple_vdef (stmt)
	      && !gimple_vuse (stmt))
	    continue;

	  if (gimple_code (stmt) == GIMPLE_RETURN)
	    continue;

	  if (ref_is_store)
	    {
	      if (ref_maybe_used_by_stmt_p (stmt, ref))
		{
		  if (dump_file)
		    {
		      fprintf (dump_file, "Stmt ");
		      print_gimple_stmt (dump_file, stmt, 0, 0);
		    }
		  return true;
		}
	    }
	  else
	    {
	      if (stmt_may_clobber_ref_p_1 (stmt, ref))
		{
		  if (dump_file)
		    {
		      fprintf (dump_file, "Stmt ");
		      print_gimple_stmt (dump_file, stmt, 0, 0);
		    }
		  return true;
		}
	    }
	}
      i++;
      if (i == region_bbs.length ())
	break;