On Thu, Nov 12, 2020 at 11:11 AM Frederik Harwath
<frede...@codesourcery.com> wrote:
>
>
> This patch enables the use of Graphite for the analysis of OpenACC
> "auto" loops. The goal is to decide if a loop may be parallelized
> (i.e. converted to an "independent" loop) or not. Graphite and the
> functionality on which it relies (scalar evolution, data references) are
> extended to interpret the internal representation of OpenACC loop
> constructs that is encoded (e.g. through calls to OpenACC-specific
> internal functions) in the OpenACC outlined functions (".omp_fn") and to
> ignore some artifacts of the outlining process that are not relevant for
> the analysis the original loops (e.g. pointers introduced for the
> purpose of offloading are irrelevant to the question whether the
> original loops can be parallelized or not). This is done in a way that
> does not impact code which does not use OpenACC. Furthermore, Graphite
> is extended by functionality that extends its applicability to
> real-world code (e.g. runtime alias checking). The OpenACC lowering is
> extended to use the result of Graphite's analysis to assign
> "independent" clauses to loops.
I wonder if this can be split into a refactoring of graphite and adding
runtime alias capability and a part doing the OpenACC pieces.
Richard.
> ---
> gcc/common.opt | 8 +
> gcc/graphite-dependences.c | 12 +-
> gcc/graphite-isl-ast-to-gimple.c | 77 +-
> gcc/graphite-oacc.h | 90 ++
> gcc/graphite-scop-detection.c | 828 ++++++++++++++----
> gcc/graphite-sese-to-poly.c | 26 +-
> gcc/graphite.c | 403 ++++++++-
> gcc/graphite.h | 11 +-
> gcc/internal-fn.h | 7 +-
> gcc/omp-expand.c | 26 +-
> gcc/omp-offload.c | 173 +++-
> gcc/predict.c | 2 +-
> .../graphite/alias-0-no-runtime-check.c | 20 +
> .../gcc.dg/graphite/alias-0-runtime-check.c | 21 +
> gcc/testsuite/gcc.dg/graphite/alias-1.c | 22 +
> gcc/tree-chrec-oacc.h | 45 +
> gcc/tree-chrec.c | 16 +-
> gcc/tree-data-ref.c | 112 ++-
> gcc/tree-data-ref.h | 8 +-
> gcc/tree-loop-distribution.c | 17 +-
> gcc/tree-scalar-evolution.c | 257 +++++-
> gcc/tree-ssa-loop-ivcanon.c | 9 +-
> gcc/tree-ssa-loop-niter.c | 13 +
> 23 files changed, 1870 insertions(+), 333 deletions(-)
> create mode 100644 gcc/graphite-oacc.h
> create mode 100644 gcc/testsuite/gcc.dg/graphite/alias-0-no-runtime-check.c
> create mode 100644 gcc/testsuite/gcc.dg/graphite/alias-0-runtime-check.c
> create mode 100644 gcc/testsuite/gcc.dg/graphite/alias-1.c
> create mode 100644 gcc/tree-chrec-oacc.h
>
> diff --git a/gcc/common.opt b/gcc/common.opt
> index dfed6ec76ba..caaeaa1aa6f 100644
> --- a/gcc/common.opt
> +++ b/gcc/common.opt
> @@ -1600,6 +1600,14 @@ fgraphite-identity
> Common Report Var(flag_graphite_identity) Optimization
> Enable Graphite Identity transformation.
>
> +fgraphite-non-affine-accesses
> +Common Report Var(flag_graphite_non_affine_accesses) Init(0)
> +Allow Graphite to handle non-affine data accesses.
> +
> +fgraphite-runtime-alias-checks
> +Common Report Var(flag_graphite_runtime_alias_checks) Optimization Init(1)
> +Allow Graphite to add runtime alias checks to loops if aliasing cannot be
> resolved statically.
> +
> fhoist-adjacent-loads
> Common Report Var(flag_hoist_adjacent_loads) Optimization
> Enable hoisting adjacent loads to encourage generating conditional move
> diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
> index 7078c949800..76ba027cdf3 100644
> --- a/gcc/graphite-dependences.c
> +++ b/gcc/graphite-dependences.c
> @@ -82,7 +82,7 @@ scop_get_reads_and_writes (scop_p scop, isl_union_map
> *&reads,
> {
> if (dump_file)
> {
> - fprintf (dump_file, "Adding read to depedence graph: ");
> + fprintf (dump_file, "Adding read to dependence graph: ");
> print_pdr (dump_file, pdr);
> }
> isl_union_map *um
> @@ -90,7 +90,7 @@ scop_get_reads_and_writes (scop_p scop, isl_union_map
> *&reads,
> reads = isl_union_map_union (reads, um);
> if (dump_file)
> {
> - fprintf (dump_file, "Reads depedence graph: ");
> + fprintf (dump_file, "Reads dependence graph: ");
> print_isl_union_map (dump_file, reads);
> }
> }
> @@ -98,7 +98,7 @@ scop_get_reads_and_writes (scop_p scop, isl_union_map
> *&reads,
> {
> if (dump_file)
> {
> - fprintf (dump_file, "Adding must write to depedence graph: ");
> + fprintf (dump_file, "Adding must write to dependence graph:
> ");
> print_pdr (dump_file, pdr);
> }
> isl_union_map *um
> @@ -106,7 +106,7 @@ scop_get_reads_and_writes (scop_p scop, isl_union_map
> *&reads,
> must_writes = isl_union_map_union (must_writes, um);
> if (dump_file)
> {
> - fprintf (dump_file, "Must writes depedence graph: ");
> + fprintf (dump_file, "Must writes dependence graph: ");
> print_isl_union_map (dump_file, must_writes);
> }
> }
> @@ -114,7 +114,7 @@ scop_get_reads_and_writes (scop_p scop, isl_union_map
> *&reads,
> {
> if (dump_file)
> {
> - fprintf (dump_file, "Adding may write to depedence graph: ");
> + fprintf (dump_file, "Adding may write to dependence graph: ");
> print_pdr (dump_file, pdr);
> }
> isl_union_map *um
> @@ -122,7 +122,7 @@ scop_get_reads_and_writes (scop_p scop, isl_union_map
> *&reads,
> may_writes = isl_union_map_union (may_writes, um);
> if (dump_file)
> {
> - fprintf (dump_file, "May writes depedence graph: ");
> + fprintf (dump_file, "May writes dependence graph: ");
> print_isl_union_map (dump_file, may_writes);
> }
> }
> diff --git a/gcc/graphite-isl-ast-to-gimple.c
> b/gcc/graphite-isl-ast-to-gimple.c
> index ef93fda2233..98c61ff864e 100644
> --- a/gcc/graphite-isl-ast-to-gimple.c
> +++ b/gcc/graphite-isl-ast-to-gimple.c
> @@ -57,6 +57,7 @@ along with GCC; see the file COPYING3. If not see
> #include "tree-ssa.h"
> #include "tree-vectorizer.h"
> #include "graphite.h"
> +#include "graphite-oacc.h"
>
> struct ast_build_info
> {
> @@ -635,12 +636,18 @@ translate_isl_ast_for_loop (loop_p context_loop,
> redirect_edge_succ_nodup (next_e, after);
> set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
>
> - if (flag_loop_parallelize_all)
> + if (flag_loop_parallelize_all || oacc_function_p (cfun))
> {
> isl_id *id = isl_ast_node_get_annotation (node_for);
> gcc_assert (id);
> ast_build_info *for_info = (ast_build_info *) isl_id_get_user (id);
> loop->can_be_parallel = for_info->is_parallelizable;
> + if (dump_file && (dump_flags & TDF_DETAILS))
> + {
> + dump_user_location_t loc = find_loop_location (loop);
> + dump_printf_loc (MSG_NOTE, loc, "loop can be parallel: %d \n",
> + loop->can_be_parallel);
> + }
> free (for_info);
> isl_id_free (id);
> }
> @@ -1027,7 +1034,7 @@ gsi_insert_earliest (gimple_seq seq)
> basic_block begin_bb = get_entry_bb (codegen_region);
>
> /* Inserting the gimple statements in a vector because gimple_seq behave
> - in strage ways when inserting the stmts from it into different basic
> + in strange ways when inserting the stmts from it into different basic
> blocks one at a time. */
> auto_vec<gimple *, 3> stmts;
> for (gimple_stmt_iterator gsi = gsi_start (seq); !gsi_end_p (gsi);
> @@ -1397,7 +1404,7 @@ scop_to_isl_ast (scop_p scop)
> (isl_schedule_copy (scop->transformed_schedule), set_separate_option,
> NULL);
> isl_ast_build *context_isl = generate_isl_context (scop);
>
> - if (flag_loop_parallelize_all)
> + if (flag_loop_parallelize_all || oacc_function_p (cfun))
> {
> scop_get_dependences (scop);
> context_isl =
> @@ -1464,6 +1471,42 @@ generate_entry_out_of_ssa_copies (edge false_entry,
> }
> }
>
> +/* Defined in tree-loop-distribution.c */
> +/* TODO Move this function to tree-data-ref.c? */
> +
> +void
> +compute_alias_check_pairs (class loop *loop, vec<ddr_p> *alias_ddrs,
> + vec<dr_with_seg_len_pair_t> *comp_alias_pairs);
> +
> +
> +/* Create a condition that evaluates to TRUE if some ALIAS_DDRS
> + do alias. */
> +
> +static tree
> +generate_alias_cond (vec<ddr_p>& alias_ddrs, loop_p context_loop)
> +{
> + gcc_checking_assert (flag_graphite_runtime_alias_checks
> + && alias_ddrs.length () > 0);
> + gcc_checking_assert (context_loop);
> +
> + auto_vec<dr_with_seg_len_pair_t> check_pairs;
> + compute_alias_check_pairs (context_loop, &alias_ddrs, &check_pairs);
> + gcc_checking_assert (check_pairs.length () > 0);
> +
> + tree alias_cond = NULL_TREE;
> + create_runtime_alias_checks (context_loop, &check_pairs, &alias_cond);
> + gcc_checking_assert (alias_cond);
> +
> + if (dump_file && (dump_flags & TDF_DETAILS))
> + {
> + fprintf (dump_file, "Generated runtime alias check: ");
> + print_generic_expr (dump_file, alias_cond, dump_flags);
> + fprintf (dump_file, "\n");
> + }
> +
> + return alias_cond;
> +}
> +
> /* GIMPLE Loop Generator: generates loops in GIMPLE form for the given SCOP.
> Return true if code generation succeeded. */
>
> @@ -1504,12 +1547,38 @@ graphite_regenerate_ast_isl (scop_p scop)
> region->if_region = if_region;
>
> loop_p context_loop = region->region.entry->src->loop_father;
> + gcc_checking_assert (context_loop);
> edge e = single_succ_edge (if_region->true_region->region.entry->dest);
> basic_block bb = split_edge (e);
>
> /* Update the true_region exit edge. */
> region->if_region->true_region->region.exit = single_succ_edge (bb);
>
> + if (flag_graphite_runtime_alias_checks
> + && scop->unhandled_alias_ddrs.length () > 0)
> + {
> + /* SCoP detection has failed to handle the aliasing between some
> + data-references of the SCoP statically. Generate an alias
> + check that selects the newly generated version of the SCoP
> + (in the true-branch of the conditional) if aliasing can be
> + ruled out at runtime and the original version of the SCoP,
> + otherwise. */
> +
> + loop_p loop
> + = find_common_loop (scop->scop_info->region.entry->dest->loop_father,
> + scop->scop_info->region.exit->src->loop_father);
> +
> + tree cond = generate_alias_cond (scop->unhandled_alias_ddrs, loop);
> + tree non_alias_cond = build1 (TRUTH_NOT_EXPR, boolean_type_node, cond);
> + set_ifsese_condition (region->if_region, non_alias_cond);
> + /* The loop nest is shared by all DDRs, cf. build_alias_set. */
> + DDR_LOOP_NEST (scop->unhandled_alias_ddrs[0]).release ();
> + free_dependence_relations (scop->unhandled_alias_ddrs);
> + }
> +
> + if (dump_file)
> + fprintf (dump_file, "[codegen] isl AST to Gimple succeeded.\n");
> +
> t.translate_isl_ast (context_loop, root_node, e, ip);
> if (! t.codegen_error_p ())
> {
> @@ -1520,8 +1589,6 @@ graphite_regenerate_ast_isl (scop_p scop)
> if_region->region->region.exit->src,
> if_region->false_region->region.exit,
> if_region->true_region->region.exit);
> - if (dump_file)
> - fprintf (dump_file, "[codegen] isl AST to Gimple succeeded.\n");
> }
>
> if (t.codegen_error_p ())
> diff --git a/gcc/graphite-oacc.h b/gcc/graphite-oacc.h
> new file mode 100644
> index 00000000000..5978f428974
> --- /dev/null
> +++ b/gcc/graphite-oacc.h
> @@ -0,0 +1,90 @@
> +/* Graphite OpenACC helpers
> + Copyright (C) 2006-2020 Free Software Foundation, Inc.
> + Contributed by Sebastian Pop <sebastian....@inria.fr>.
> +
> +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/>. */
> +
> +/* This pass converts GIMPLE to GRAPHITE, performs some loop
> + transformations and then converts the resulting representation back
> + to GIMPLE.
> +
> + An early description of this pass can be found in the GCC Summit'06
> + paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC".
> + The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to
> + the related work. */
> +
> +#include "omp-general.h"
> +#include "attribs.h"
> +
> +static inline bool oacc_function_p (function *fun)
> +{
> + return oacc_get_fn_attrib (fun->decl);
> +}
> +
> +/* Represents a field of the ".omp_data_i" argument of
> + an outlined OpenACC function. Each such field
> + is used to pass a unique variable from the function
> + that originally contained the loop to the outlined
> + function. */
> +
> +struct oacc_data_field {
> + /* The variable of the source function that
> + gets passed through this field. */
> + tree src_var;
> +
> + /* The variable that holds the dereferenced value of the
> + field. This might be left NULL for reduction variables. */
> + // TODO-kernels Should we also set this for reduction variables?
> + // This seems to be unnecessary since we do not create data-refs
> + // for reduction variables.
> +
> + tree tgt_var;
> +};
> +
> +class oacc_omp_data
> +{
> +private:
> + hash_map<tree, oacc_data_field> field_map;
> +
> + void gather_assignments (struct function *fn);
> + tree get_accessed_field (tree t);
> +public:
> + tree src_fn_arg;
> + tree tgt_fn_arg;
> + gimple* src_fn_def;
> + // TODO-kernels This belongs into the oacc_context
> + loop_p loop;
> + static oacc_omp_data construct (struct function* fn);
> + tree redirect_data_ref (tree ref);
> +};
> +
> +class oacc_context {
> +public:
> + oacc_omp_data omp_data;
> +
> +private:
> + bool valid;
> + oacc_context () : omp_data (), valid (false) {}
> + oacc_context (oacc_omp_data omp_data) :
> + omp_data (omp_data),
> + valid (true) {}
> +public:
> + static oacc_context build_context ();
> + static oacc_context invalid_context () { return oacc_context (); }
> +
> + bool is_valid () { return valid; }
> +};
> diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
> index 75f81227f8a..ccdf3aa4d5b 100644
> --- a/gcc/graphite-scop-detection.c
> +++ b/gcc/graphite-scop-detection.c
> @@ -42,6 +42,7 @@ along with GCC; see the file COPYING3. If not see
> #include "tree-into-ssa.h"
> #include "tree-ssa.h"
> #include "cfgloop.h"
> +#include "tree-chrec-oacc.h"
> #include "tree-data-ref.h"
> #include "tree-scalar-evolution.h"
> #include "tree-pass.h"
> @@ -49,6 +50,9 @@ along with GCC; see the file COPYING3. If not see
> #include "gimple-pretty-print.h"
> #include "cfganal.h"
> #include "graphite.h"
> +#include "omp-general.h"
> +#include "graphite-oacc.h"
> +#include "print-tree.h"
>
> class debug_printer
> {
> @@ -69,12 +73,27 @@ public:
> fprintf (output.dump_file, "%d", i);
> return output;
> }
> +
> friend debug_printer &
> operator<< (debug_printer &output, const char *s)
> {
> fprintf (output.dump_file, "%s", s);
> return output;
> }
> +
> + friend debug_printer &
> + operator<< (debug_printer &output, gimple* stmt)
> + {
> + print_gimple_stmt (output.dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS);
> + return output;
> + }
> +
> + friend debug_printer &
> + operator<< (debug_printer &output, tree t)
> + {
> + print_generic_expr (output.dump_file, t, TDF_SLIM);
> + return output;
> + }
> } dp;
>
> #define DEBUG_PRINT(args) do \
> @@ -286,7 +305,8 @@ namespace
> class scop_detection
> {
> public:
> - scop_detection () : scops (vNULL) {}
> + scop_detection (oacc_context *oacc_ctx)
> + : scops (vNULL), oacc_ctx (oacc_ctx) {}
>
> ~scop_detection ()
> {
> @@ -354,24 +374,6 @@ public:
> bool stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
> basic_block bb) const;
>
> - /* Something like "n * m" is not allowed. */
> -
> - static bool graphite_can_represent_init (tree e);
> -
> - /* Return true when SCEV can be represented in the polyhedral model.
> -
> - An expression can be represented, if it can be expressed as an
> - affine expression. For loops (i, j) and parameters (m, n) all
> - affine expressions are of the form:
> -
> - x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
> -
> - 1 i + 20 j + (-2) m + 25
> -
> - Something like "i * n" or "n * m" is not allowed. */
> -
> - static bool graphite_can_represent_scev (sese_l scop, tree scev);
> -
> /* Return true when EXPR can be represented in the polyhedral model.
>
> This means an expression can be represented, if it is linear with
> respect
> @@ -382,9 +384,9 @@ public:
> tree expr);
>
> /* Return true if the data references of STMT can be represented by
> Graphite.
> - We try to analyze the data references in a loop contained in the SCOP.
> */
> + We try to analyze the data references in a loop contained in the SCOP.
> */
>
> - static bool stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt);
> + static bool stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt,
> oacc_context *oacc_ctx);
>
> /* Remove the close phi node at GSI and replace its rhs with the rhs
> of PHI. */
> @@ -403,6 +405,7 @@ public:
>
> private:
> vec<sese_l> scops;
> + oacc_context *oacc_ctx;
> };
>
> sese_l scop_detection::invalid_sese (NULL, NULL);
> @@ -560,14 +563,58 @@ scop_detection::can_represent_loop (loop_p loop, sese_l
> scop)
> || !single_pred_p (loop->latch)
> || exit->src != single_pred (loop->latch)
> || !empty_block_p (loop->latch))
> - return false;
> + {
> + DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop shape invalid.\n");
> + return false;
> +
> + }
> +
> + bool edge_irreducible = loop_preheader_edge (loop)->flags &
> EDGE_IRREDUCIBLE_LOOP;
> + if (edge_irreducible)
> + {
> + DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop is not a natural
> loop.\n");
> + return false;
> + }
> +
> + bool niter_is_unconditional =
> + number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false);
> + if (!niter_is_unconditional)
> + {
> + DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop niter not
> unconditional.\n");
> + return false;
> + }
> +
> + if (!niter_desc.control.no_overflow)
> + {
> + DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop niter can
> overflow.\n");
> + return false;
> + }
> +
> + niter = number_of_latch_executions (loop);
> + if (!niter)
> + {
> + DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop niter unknown.\n");
> + return false;
> + }
> +
> + bool undetermined_coefficients = chrec_contains_undetermined (niter);
> + if (undetermined_coefficients)
> + {
> + DEBUG_PRINT (dp << "[can_represent_loop-fail] "
> + << "Loop niter chrec contains undetermined
> coefficients.\n");
> + return false;
> + }
>
> - return !(loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
> - && number_of_iterations_exit (loop, single_exit (loop), &niter_desc,
> false)
> - && niter_desc.control.no_overflow
> - && (niter = number_of_latch_executions (loop))
> - && !chrec_contains_undetermined (niter)
> - && graphite_can_represent_expr (scop, loop, niter);
> + bool can_represent_expr = graphite_can_represent_expr (scop, loop, niter);
> + if (!can_represent_expr)
> + {
> + DEBUG_PRINT (dp << "[can_represent_loop-fail] "
> + << "Loop niter expression cannot be represented: "
> + << niter << "\n");
> + return false;
> + }
> +
> + return true;
> }
>
> /* Return true when BEGIN is the preheader edge of a loop with a single exit
> @@ -615,13 +662,12 @@ scop_detection::add_scop (sese_l s)
> s.exit = single_succ_edge (s.exit->dest);
> }
>
> - /* Do not add scops with only one loop. */
> - if (region_has_one_loop (s))
> - {
> - DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP: ";
> - print_sese (dump_file, s));
> - return;
> - }
> + if (!oacc_function_p (cfun) && region_has_one_loop (s))
> + {
> + DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP: ";
> + print_sese (dump_file, s));
> + return;
> + }
>
> if (get_exit_bb (s) == EXIT_BLOCK_PTR_FOR_FN (cfun))
> {
> @@ -805,140 +851,87 @@ scop_detection::remove_intersecting_scops (sese_l s1)
> }
> }
>
> -/* Something like "n * m" is not allowed. */
> +/* Return true when EXPR can be represented in the polyhedral model.
> +
> + This means an expression can be represented, if it is linear with respect
> to
> + the loops and the strides are non parametric. LOOP is the place where the
> + expr will be evaluated. SCOP defines the region we analyse. */
>
> bool
> -scop_detection::graphite_can_represent_init (tree e)
> +scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop,
> + tree expr)
> {
> - switch (TREE_CODE (e))
> + if (TREE_CODE (expr) == SSA_NAME)
> {
> - case POLYNOMIAL_CHREC:
> - return graphite_can_represent_init (CHREC_LEFT (e))
> - && graphite_can_represent_init (CHREC_RIGHT (e));
> -
> - case MULT_EXPR:
> - if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
> - return graphite_can_represent_init (TREE_OPERAND (e, 0))
> - && tree_fits_shwi_p (TREE_OPERAND (e, 1));
> - else
> - return graphite_can_represent_init (TREE_OPERAND (e, 1))
> - && tree_fits_shwi_p (TREE_OPERAND (e, 0));
> + tree name = SSA_NAME_IDENTIFIER (expr);
>
> - case PLUS_EXPR:
> - case POINTER_PLUS_EXPR:
> - case MINUS_EXPR:
> - return graphite_can_represent_init (TREE_OPERAND (e, 0))
> - && graphite_can_represent_init (TREE_OPERAND (e, 1));
> -
> - case NEGATE_EXPR:
> - case BIT_NOT_EXPR:
> - CASE_CONVERT:
> - case NON_LVALUE_EXPR:
> - return graphite_can_represent_init (TREE_OPERAND (e, 0));
> -
> - default:
> - break;
> + if (name)
> + {
> + const char* id = IDENTIFIER_POINTER (name);
> + if (strncmp (id, ".bound", 6) == 0
> + || strncmp (id, ".offset", 7) == 0
> + || strncmp (id, ".chunk_max", 11) == 0
> + || strncmp (id, ".chunk_no", 10) == 0
> + || strncmp (id, ".step", 5) == 0)
> + return true;
> + }
> }
> + tree scev = cached_scalar_evolution_in_region (scop, loop, expr);
> + bool can_represent = graphite_can_represent_scev (scop, scev);
>
> - return true;
> -}
> -
> -/* Return true when SCEV can be represented in the polyhedral model.
> -
> - An expression can be represented, if it can be expressed as an
> - affine expression. For loops (i, j) and parameters (m, n) all
> - affine expressions are of the form:
> -
> - x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
> -
> - 1 i + 20 j + (-2) m + 25
> -
> - Something like "i * n" or "n * m" is not allowed. */
> -
> -bool
> -scop_detection::graphite_can_represent_scev (sese_l scop, tree scev)
> -{
> - if (chrec_contains_undetermined (scev))
> - return false;
> -
> - switch (TREE_CODE (scev))
> + if (!can_represent)
> {
> - case NEGATE_EXPR:
> - case BIT_NOT_EXPR:
> - CASE_CONVERT:
> - case NON_LVALUE_EXPR:
> - return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0));
> -
> - case PLUS_EXPR:
> - case POINTER_PLUS_EXPR:
> - case MINUS_EXPR:
> - return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
> - && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
> -
> - case MULT_EXPR:
> - return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
> - && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
> - && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
> - && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
> - && graphite_can_represent_init (scev)
> - && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
> - && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
> -
> - case POLYNOMIAL_CHREC:
> - /* Check for constant strides. With a non constant stride of
> - 'n' we would have a value of 'iv * n'. Also check that the
> - initial value can represented: for example 'n * m' cannot be
> - represented. */
> - gcc_assert (loop_in_sese_p (get_loop (cfun,
> - CHREC_VARIABLE (scev)), scop));
> - if (!evolution_function_right_is_integer_cst (scev)
> - || !graphite_can_represent_init (scev))
> - return false;
> - return graphite_can_represent_scev (scop, CHREC_LEFT (scev));
> -
> - case ADDR_EXPR:
> - /* We cannot encode addresses for ISL. */
> - return false;
> -
> - default:
> - break;
> + if (dump_file)
> + {
> + fprintf (dump_file, "[graphite_can_represent_expr] Cannot represent
> scev ");
> + print_generic_expr (dump_file, scev, TDF_SLIM);
> + fprintf (dump_file, " of expression ");
> + print_generic_expr (dump_file, expr, TDF_SLIM);
> + fprintf (dump_file, "\n");
> + }
> }
> -
> - /* Only affine functions can be represented. */
> - if (tree_contains_chrecs (scev, NULL) || !scev_is_linear_expression (scev))
> - return false;
> -
> - return true;
> + return can_represent;
> }
>
> -/* Return true when EXPR can be represented in the polyhedral model.
> -
> - This means an expression can be represented, if it is linear with respect
> to
> - the loops and the strides are non parametric. LOOP is the place where the
> - expr will be evaluated. SCOP defines the region we analyse. */
> +/* Check if STMT is a internal OpenACC function call that should be
> + ignored when Graphite checks side effects and data references. */
>
> -bool
> -scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop,
> - tree expr)
> -{
> - tree scev = cached_scalar_evolution_in_region (scop, loop, expr);
> - return graphite_can_represent_scev (scop, scev);
> +static inline bool
> +oacc_ignore_internal_stmt (gimple *stmt) {
> + return is_gimple_call (stmt) &&
> + (gimple_call_internal_p (stmt, IFN_UNIQUE)
> + || gimple_call_internal_p (stmt, IFN_GOACC_REDUCTION));
> }
>
> /* Return true if the data references of STMT can be represented by Graphite.
> We try to analyze the data references in a loop contained in the SCOP. */
>
> bool
> -scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt)
> +scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt,
> oacc_context *oacc_ctx)
> {
> + if (oacc_ignore_internal_stmt (stmt))
> + return true;
> +
> edge nest = scop.entry;
> loop_p loop = loop_containing_stmt (stmt);
> if (!loop_in_sese_p (loop, scop))
> loop = NULL;
>
> + bool allow_non_affine_base = flag_graphite_non_affine_accesses;
> auto_vec<data_reference_p> drs;
> - if (! graphite_find_data_references_in_stmt (nest, loop, stmt, &drs))
> - return false;
> + if (! graphite_find_data_references_in_stmt (nest, loop, stmt, &drs,
> + oacc_ctx,
> allow_non_affine_base))
> + {
> + DEBUG_PRINT (dp << "[stmt_has_simple_data_refs_p] Unanalyzable
> statement.\n");
> + return false;
> + }
> +
> + /* This flag means that we allow Graphite to overapproximate the
> + range of data references. Consequently, we do not need to check
> + if Graphite can actually represent the access functions'
> + SCEVs. */
> + if (flag_graphite_non_affine_accesses)
> + return true;
>
> int j;
> data_reference_p dr;
> @@ -946,7 +939,10 @@ scop_detection::stmt_has_simple_data_refs_p (sese_l
> scop, gimple *stmt)
> {
> for (unsigned i = 0; i < DR_NUM_DIMENSIONS (dr); ++i)
> if (! graphite_can_represent_scev (scop, DR_ACCESS_FN (dr, i)))
> - return false;
> + {
> + DEBUG_PRINT (dp << "[stmt_has_simple_data_refs_p] Cannot
> represent access function SCEV: " << DR_ACCESS_FN (dr, i) << "\n");
> + return false;
> + }
> }
>
> return true;
> @@ -959,6 +955,9 @@ scop_detection::stmt_has_simple_data_refs_p (sese_l scop,
> gimple *stmt)
> static bool
> stmt_has_side_effects (gimple *stmt)
> {
> + if (oacc_ignore_internal_stmt (stmt))
> + return false;
> +
> if (gimple_has_volatile_ops (stmt)
> || (gimple_code (stmt) == GIMPLE_CALL
> && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
> @@ -990,11 +989,16 @@ scop_detection::stmt_simple_for_scop_p (sese_l scop,
> gimple *stmt,
> if (stmt_has_side_effects (stmt))
> return false;
>
> - if (!stmt_has_simple_data_refs_p (scop, stmt))
> + if (!stmt_has_simple_data_refs_p (scop, stmt, oacc_ctx))
> {
> - DEBUG_PRINT (dp << "[scop-detection-fail] "
> - << "Graphite cannot handle data-refs in stmt:\n";
> - print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS););
> + DEBUG_PRINT (dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt,
> + "[scop-detection-fail] Graphite cannot "
> + "handle data-refs-in-stmt: ");
> + print_gimple_stmt (dump_file, stmt, 0,
> + TDF_VOPS | TDF_MEMSYMS);
> + fprintf (dump_file, "\n");
> +
> + );
> return false;
> }
>
> @@ -1027,14 +1031,22 @@ scop_detection::stmt_simple_for_scop_p (sese_l scop,
> gimple *stmt,
> for (unsigned i = 0; i < 2; ++i)
> {
> tree op = gimple_op (stmt, i);
> - if (!graphite_can_represent_expr (scop, loop, op)
> - /* We can only constrain on integer type. */
> - || ! INTEGRAL_TYPE_P (TREE_TYPE (op)))
> + if (!graphite_can_represent_expr (scop, loop, op))
> + {
> + DEBUG_PRINT (dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt,
> + "[scop-detection-fail] "
> + "Graphite cannot represent cond
> "
> + "stmt operator expression.\n"));
> + return false;
> + }
> +
> + if (! INTEGRAL_TYPE_P (TREE_TYPE (op)))
> {
> - DEBUG_PRINT (dp << "[scop-detection-fail] "
> - << "Graphite cannot represent stmt:\n";
> - print_gimple_stmt (dump_file, stmt, 0,
> - TDF_VOPS | TDF_MEMSYMS));
> + DEBUG_PRINT (dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt,
> + "[scop-detection-fail] "
> + "Graphite cannot represent cond
> "
> + "statement operator. "
> + "Type must be integral.\n"));
> return false;
> }
> }
> @@ -1151,6 +1163,7 @@ scan_tree_for_params (sese_info_p s, tree e)
> break;
>
> case SSA_NAME:
> + //TODO-kernels Stop treating some OpenACC ifn calls as parameters
> (reductions?)
> assign_parameter_index_in_region (e, s);
> break;
>
> @@ -1288,11 +1301,99 @@ build_cross_bb_scalars_use (scop_p scop, tree use,
> gimple *use_stmt,
> add_read (reads, use, use_stmt);
> }
>
> +/* This class keeps track of the variables that occur in active
> + OpenACC reductions while walking a function's basic blocks during
> + SCoP detection. The UPDATE method processes calls to the OpenACC
> + internal functions which mark the beginning and the end of the use
> + of a reduction variable. It adjusts an internal reference count
> + that is maintained for each such variable accordingly (i.e. number
> + of reductions using a SSA_NAME with the variable name). */
> +
> +class oacc_reductions {
> + public:
> + bool is_reduction_var (const tree var);
> + void update (const gimple* oacc_reduction_call);
> + void update (const basic_block);
> + private:
> + hash_map<tree, unsigned> reductions;
> +};
> +
> +/* Check if the DEF is a SSA_NAME for a variable that occurs in an
> + active reduction. */
> +
> +bool oacc_reductions::is_reduction_var (const tree def) {
> + if (TREE_CODE (def) != SSA_NAME)
> + return false;
> +
> + tree var = SSA_NAME_VAR (def);
> + if (var == NULL_TREE)
> + return false;
> +
> + return reductions.get (var);
> +}
> +
> +/* Update the internal reference count for the variable used by the
> + OACC_REDUCTION_CALL if it starts or ends a reduction. */
> +
> +void oacc_reductions::update (const gimple* oacc_reduction_call)
> +{
> + const gcall* call = GIMPLE_CHECK2<const gcall *> (oacc_reduction_call);
> + unsigned code = (unsigned)TREE_INT_CST_LOW (gimple_call_arg (call, 0));
> +
> + if (!gimple_has_lhs (call))
> + return;
> +
> + tree var = SSA_NAME_VAR (gimple_call_lhs (call));
> +
> + if (var == NULL)
> + return;
> +
> + switch (code)
> + {
> + case IFN_GOACC_REDUCTION_SETUP:
> + {
> + unsigned& ref_count = reductions.get_or_insert (var);
> + ref_count++;
> +
> + break;
> + }
> + case IFN_GOACC_REDUCTION_FINI:
> + {
> + unsigned* ref_count = reductions.get (var);
> + gcc_checking_assert (ref_count != NULL && *ref_count > 0);
> + ref_count--;
> +
> + if (ref_count == 0)
> + reductions.remove (var);
> +
> + break;
> + }
> +
> + default:
> + break;
> + }
> +}
> +
> +void oacc_reductions::update (const basic_block bb)
> +{
> + for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
> + gsi_next (&gsi))
> + {
> + gimple *stmt = gsi_stmt (gsi);
> + if (gimple_call_internal_p (stmt, IFN_GOACC_REDUCTION))
> + update (stmt);
> + }
> +}
> +
> +
> +
> /* Generates a polyhedral black box only if the bb contains interesting
> information. */
>
> static gimple_poly_bb_p
> -try_generate_gimple_bb (scop_p scop, basic_block bb)
> +try_generate_gimple_bb (scop_p scop, basic_block bb,
> + oacc_reductions& oacc_reductions,
> + __attribute__ ((unused)) oacc_context* oacc_ctx)
> {
> vec<data_reference_p> drs = vNULL;
> vec<tree> writes = vNULL;
> @@ -1304,6 +1405,7 @@ try_generate_gimple_bb (scop_p scop, basic_block bb)
> if (!loop_in_sese_p (loop, region))
> loop = NULL;
>
> + bool allow_non_affine_base = flag_graphite_non_affine_accesses;
> for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
> gsi_next (&gsi))
> {
> @@ -1311,16 +1413,27 @@ try_generate_gimple_bb (scop_p scop, basic_block bb)
> if (is_gimple_debug (stmt))
> continue;
>
> - graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
> + graphite_find_data_references_in_stmt (nest, loop, stmt, &drs,
> + oacc_ctx, allow_non_affine_base);
>
> tree def = gimple_get_lhs (stmt);
> - if (def)
> + if (def
> + /* When analyzing the outlined function for an OpenACC
> + region, no dependencies on reduction variables should be
> + generated. Those variables must be ignored when deciding
> + if a loop can be parallel. */
> + && !oacc_reductions.is_reduction_var (def))
> build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), &writes);
>
> ssa_op_iter iter;
> tree use;
> FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
> - build_cross_bb_scalars_use (scop, use, stmt, &reads);
> + {
> + if (oacc_reductions.is_reduction_var (use))
> + continue;
> +
> + build_cross_bb_scalars_use (scop, use, stmt, &reads);
> + }
> }
>
> /* Handle defs and uses in PHIs. Those need special treatment given
> @@ -1332,7 +1445,8 @@ try_generate_gimple_bb (scop_p scop, basic_block bb)
> gphi *phi = psi.phi ();
> tree res = gimple_phi_result (phi);
> if (virtual_operand_p (res)
> - || scev_analyzable_p (res, scop->scop_info->region))
> + || scev_analyzable_p (res, scop->scop_info->region)
> + || oacc_reductions.is_reduction_var (res))
> continue;
> /* To simulate out-of-SSA the block containing the PHI node has
> reads of the PHI destination. And to preserve SSA dependences
> @@ -1362,13 +1476,15 @@ try_generate_gimple_bb (scop_p scop, basic_block bb)
> continue;
> /* To simulate out-of-SSA the predecessor of edges into PHI
> nodes
> has a copy from the PHI argument to the PHI destination. */
> - if (! scev_analyzable_p (res, scop->scop_info->region))
> + if (! scev_analyzable_p (res, scop->scop_info->region)
> + && ! oacc_reductions.is_reduction_var (res))
> add_write (&writes, res);
> tree use = PHI_ARG_DEF_FROM_EDGE (phi, e);
> if (TREE_CODE (use) == SSA_NAME
> && ! SSA_NAME_IS_DEFAULT_DEF (use)
> && gimple_bb (SSA_NAME_DEF_STMT (use)) != bb_for_succs
> - && ! scev_analyzable_p (use, scop->scop_info->region))
> + && ! scev_analyzable_p (use, scop->scop_info->region)
> + && ! oacc_reductions.is_reduction_var (use))
> add_read (&reads, use, phi);
> }
> if (e->dest == bb_for_succs->loop_father->latch
> @@ -1402,40 +1518,316 @@ try_generate_gimple_bb (scop_p scop, basic_block bb)
> return new_gimple_poly_bb (bb, drs, reads, writes);
> }
>
> +bool oacc_is_omp_data_use (oacc_context *ctx, data_reference_p dr)
> +{
> + tree t;
> +
> + switch (TREE_CODE (dr->ref))
> + {
> + case COMPONENT_REF:
> + {
> + tree referenced = TREE_OPERAND (dr->ref, 0);
> + tree target = TREE_OPERAND (referenced, 0);
> +
> + if (TREE_CODE(target) != SSA_NAME ||
> + SSA_NAME_VAR(target) == NULL_TREE)
> + return false;
> +
> + if (SSA_NAME_VAR (target) == ctx->omp_data.tgt_fn_arg)
> + return true;
> + }
> +
> + default:
> + return false;
> + }
> +
> + return false;
> +}
> +
> +/* Aliasing involving the pointers contained in the ".omp_data_i"
> + struct can be safely ignored. We are analysing the behavior of a
> + loop nest with respect to the original function and those pointers
> + are artifacts of the outlining process. */
> +
> +bool oacc_ignore_alias (oacc_context *ctx, data_reference_p dr1,
> data_reference_p dr2)
> +{
> + if (oacc_is_omp_data_use (ctx, dr1)
> + || oacc_is_omp_data_use (ctx, dr2))
> + return true;
> +
> + return false;
> +}
> +
> +/* Returns true if expression EXPR is defined between ENTRY and
> + EXIT. */
> +
> +static bool
> +def_in_region_p (edge entry, edge exit, tree expr)
> +{
> + basic_block entry_bb = entry->dest;
> + basic_block exit_bb = exit->dest;
> + basic_block def_bb;
> +
> + if (! expr)
> + return false;
> +
> + if (is_gimple_min_invariant (expr))
> + return false;
> +
> + if (TREE_CODE (expr) == SSA_NAME)
> + {
> + def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
> + if (!def_bb)
> + return false;
> +
> + if (dominated_by_p (CDI_DOMINATORS, def_bb, entry_bb)
> + && !dominated_by_p (CDI_DOMINATORS, def_bb, exit_bb))
> + return true;
> +
> + return false;
> + }
> + else {
> + for (unsigned i = 0; i < TREE_OPERAND_LENGTH (expr); i++)
> + if (def_in_region_p (entry, exit, TREE_OPERAND (expr, i)))
> + return true;
> + }
> +
> + return false;
> +}
> +
> +static bool
> +scev_defs_outside_region_p (edge entry, edge exit, tree scev)
> +{
> + if (chrec_contains_undetermined (scev))
> + return false;
> +
> + switch (TREE_CODE (scev))
> + {
> + case NEGATE_EXPR:
> + case BIT_NOT_EXPR:
> + case NON_LVALUE_EXPR:
> + case ADDR_EXPR:
> + return scev_defs_outside_region_p (entry, exit, TREE_OPERAND (scev,
> 0));
> +
> + case PLUS_EXPR:
> + case POINTER_PLUS_EXPR:
> + case MINUS_EXPR:
> + case MULT_EXPR:
> + case POLYNOMIAL_CHREC:
> + return scev_defs_outside_region_p (entry, exit, TREE_OPERAND (scev, 0))
> + && scev_defs_outside_region_p (entry, exit, TREE_OPERAND (scev, 1));
> +
> + default:
> + break;
> + }
> +
> + return ! def_in_region_p (entry, exit, scev);
> +}
> +
> +/* Checks if all parts of the DRI are defined outside of the region
> + surrounded by the given edges which allows an alias check involving
> + DRI to be placed before the region. */
> +
> +static bool
> +dr_defs_outside_region (edge entry, edge exit, dr_info *dri)
> +{
> + data_reference_p dr = dri->dr;
> + tree base = DR_BASE_OBJECT (dr);
> + if (def_in_region_p (entry, exit, base))
> + {
> + DEBUG_PRINT(dp << "base defined inside SCoP.\n");
> + return false;
> + }
> +
> + tree step = DR_STEP (dr);
> + if (def_in_region_p (entry, exit, step))
> + {
> + DEBUG_PRINT(dp << "step defined inside SCoP.\n");
> + return false;
> + }
> +
> + tree base_addr = DR_BASE_ADDRESS (dr);
> + if (def_in_region_p (entry, exit, base_addr))
> + {
> + DEBUG_PRINT(dp << "base address defined inside SCoP.\n");
> + return false;
> + }
> +
> + for (unsigned i = 0; i < DR_NUM_DIMENSIONS(dr); ++i)
> + {
> + tree access = DR_ACCESS_FN (dr, i);
> + if (! scev_defs_outside_region_p (entry, exit, access))
> + {
> + DEBUG_PRINT(fprintf (dump_file, "%d-th access function uses
> definitions from SCoP.\n", i);
> + print_generic_expr (dump_file, access, dump_flags);
> + fprintf (dump_file, "\n"););
> + return false;
> + }
> + }
> +
> + return true;
> +}
> +
> +
> +
> +/* Return TRUE if a runtime alias check to resolve the aliasing
> + between the DDRs DR1 and DR2 which belong to the LOOP in the region
> + delineated by SCOP_ENTRY and SCOP_EXIT may be created and placed
> + before that region. */
> +
> +static opt_result
> +graphite_runtime_alias_check_p (dr_info* dr1, dr_info* dr2, class loop *loop,
> + edge scop_entry, edge scop_exit)
> +{
> + gcc_checking_assert (loop);
> + gcc_checking_assert (dr1);
> + gcc_checking_assert (dr2);
> +
> + if (dump_enabled_p ())
> + dump_printf (MSG_NOTE,
> + "consider run-time aliasing test between %T and %T\n",
> + DR_REF (dr1->dr), DR_REF (dr2->dr));
> +
> +
> + if (! optimize_loop_for_speed_p (loop))
> + return opt_result::failure_at (DR_STMT (dr1->dr),
> + "runtime alias check not supported when"
> + " optimizing for size.\n");
> +
> +
> + /* Verify that we have enough information about the data-references
> + and context loop to construct a runtime alias check with
> + "compute_alias_check_pairs". */
> +
> + if (loop->num != 0) {
> + tree niters = number_of_latch_executions (loop);
> + if (niters == NULL_TREE || niters == chrec_dont_know)
> + return opt_result::failure_at (DR_STMT (dr1->dr),
> + "could not determine number of
> iterations "
> + "of the SCoP's context loop. "
> + "Aborting runtime alias checks.\n");
> + }
> +
> + /* The runtime alias check selects between the optimized and the
> + original version of a SCoP. Hence, it must be placed before the
> + SCoP which is not possible if some of the data reference's fields
> + refer to definitions inside of the SCoP. */
> +
> + if (! dr_defs_outside_region (scop_entry, scop_exit, dr1)
> + || ! dr_defs_outside_region (scop_entry, scop_exit, dr2))
> + return opt_result::failure_at (DR_STMT (dr1->dr),
> + "data-references use definitions inside
> of "
> + "SCoP. "
> + "Aborting runtime alias checks.\n");
> +
> +
> + return opt_result::success ();
> +}
> +
> /* Compute alias-sets for all data references in DRS. */
>
> -static bool
> -build_alias_set (scop_p scop)
> +static bool
> +build_alias_set (scop_p scop, oacc_context *oacc_ctx)
> {
> int num_vertices = scop->drs.length ();
> struct graph *g = new_graph (num_vertices);
> dr_info *dr1, *dr2;
> int i, j;
> int *all_vertices;
> + edge scop_entry = scop->scop_info->region.entry;
> + edge scop_exit = scop->scop_info->region.exit;
>
> struct loop *nest
> - = find_common_loop (scop->scop_info->region.entry->dest->loop_father,
> - scop->scop_info->region.exit->src->loop_father);
> + = find_common_loop (scop_entry->dest->loop_father,
> + scop_exit->src->loop_father);
> +
> + gcc_checking_assert (nest);
> +
> + DEBUG_PRINT(dp << "[build_alias_set]: Data references:\n";
> + dr_info *dr;
> + FOR_EACH_VEC_ELT (scop->drs, i, dr)
> + {
> + dump_data_reference (dump_file, dr->dr);
> + }
> + );
> +
> + auto_vec<loop_p, 1> nest_vec;
> + if (flag_graphite_runtime_alias_checks)
> + {
> + scop->unhandled_alias_ddrs.create (1);
> + nest_vec.safe_push (nest);
> + }
>
> FOR_EACH_VEC_ELT (scop->drs, i, dr1)
> for (j = i+1; scop->drs.iterate (j, &dr2); j++)
> - if (dr_may_alias_p (dr1->dr, dr2->dr, nest))
> + if (! (DR_IS_READ (dr1->dr) && DR_IS_READ (dr2->dr))
> + && dr_may_alias_p (dr1->dr, dr2->dr, nest))
> {
> - /* Dependences in the same alias set need to be handled
> - by just looking at DR_ACCESS_FNs. */
> - if (DR_NUM_DIMENSIONS (dr1->dr) == 0
> - || DR_NUM_DIMENSIONS (dr1->dr) != DR_NUM_DIMENSIONS (dr2->dr)
> - || ! operand_equal_p (DR_BASE_OBJECT (dr1->dr),
> - DR_BASE_OBJECT (dr2->dr),
> - OEP_ADDRESS_OF)
> - || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1->dr)),
> - TREE_TYPE (DR_BASE_OBJECT (dr2->dr))))
> + if (! oacc_ignore_alias (oacc_ctx, dr1->dr, dr2->dr))
> {
> - free_graph (g);
> - return false;
> + /* Dependences in the same alias set need to be handled
> + by just looking at DR_ACCESS_FNs. */
> + bool dimension_zero = DR_NUM_DIMENSIONS (dr1->dr) == 0;
> + if (dimension_zero)
> + DEBUG_PRINT(dp << "[build_alias_set] DR1 has dimension
> 0\n");
> +
> + bool different_dimensions =
> + DR_NUM_DIMENSIONS (dr1->dr) != DR_NUM_DIMENSIONS (dr2->dr);
> + if (different_dimensions)
> + DEBUG_PRINT (dp << "[build_alias_set] "
> + "DRs have different dimensions\n");
> +
> + bool different_base_objects =
> + ! operand_equal_p (DR_BASE_OBJECT (dr1->dr),
> + DR_BASE_OBJECT (dr2->dr), OEP_ADDRESS_OF);
> + if (different_base_objects)
> + DEBUG_PRINT (dp << "[build_alias_set] "
> + "DRs access different objects\n");
> +
> + bool incompatible_types =
> + ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1->dr)),
> + TREE_TYPE (DR_BASE_OBJECT (dr2->dr)));
> + if (incompatible_types)
> + DEBUG_PRINT (dp << "[build_alias_set] "
> + "DRs with incompatible base object types");
> +
> + if (dimension_zero || different_dimensions
> + || different_base_objects || incompatible_types)
> + {
> + if (! flag_graphite_runtime_alias_checks)
> + goto FAIL;
> +
> + if (! graphite_runtime_alias_check_p (dr1, dr2, nest,
> + scop_entry,
> scop_exit))
> + goto FAIL;
> +
> + ddr_p ddr = initialize_data_dependence_relation
> + (dr1->dr, dr2->dr, nest_vec);
> + scop->unhandled_alias_ddrs.safe_push(ddr);
> + }
> }
> add_edge (g, i, j);
> add_edge (g, j, i);
> + continue;
> +
> + FAIL:
> + DEBUG_PRINT (dp <<
> + "[build_alias_set] "
> + "Cannot handle dependency between data references: \n";
> + print_gimple_stmt (dump_file, dr1->dr->stmt, 2,
> TDF_DETAILS);
> + print_gimple_stmt (dump_file, dr2->dr->stmt, 2,
> TDF_DETAILS);
> + dp << "\n");
> +
> + if (flag_graphite_runtime_alias_checks)
> + {
> + if (scop->unhandled_alias_ddrs.length () > 0)
> + /* The loop-nest vec is shared by all DDRs. */
> + DDR_LOOP_NEST (scop->unhandled_alias_ddrs[0]).release ();
> + free_dependence_relations (scop->unhandled_alias_ddrs);
> + }
> +
> + free_graph (g);
> + return false;
> }
>
> all_vertices = XNEWVEC (int, num_vertices);
> @@ -1457,7 +1849,7 @@ build_alias_set (scop_p scop)
> class gather_bbs : public dom_walker
> {
> public:
> - gather_bbs (cdi_direction, scop_p, int *);
> + gather_bbs (cdi_direction, scop_p, int *, oacc_reductions&, oacc_context*);
>
> virtual edge before_dom_children (basic_block);
> virtual void after_dom_children (basic_block);
> @@ -1465,12 +1857,18 @@ public:
> private:
> auto_vec<gimple *, 3> conditions, cases;
> scop_p scop;
> + oacc_reductions &reductions;
> + oacc_context *oacc_ctx;
> };
> -}
> -gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo)
> - : dom_walker (direction, ALL_BLOCKS, bb_to_rpo), scop (scop)
> -{
> -}
> +
> +gather_bbs::gather_bbs
> +(cdi_direction direction, scop_p scop, int *bb_to_rpo,
> + oacc_reductions& reductions, oacc_context *oacc_ctx)
> +: dom_walker (direction, ALL_BLOCKS, bb_to_rpo)
> + , scop (scop)
> + , reductions (reductions)
> + , oacc_ctx (oacc_ctx)
> +{}
>
> /* Call-back for dom_walk executed before visiting the dominated
> blocks. */
> @@ -1478,6 +1876,8 @@ gather_bbs::gather_bbs (cdi_direction direction, scop_p
> scop, int *bb_to_rpo)
> edge
> gather_bbs::before_dom_children (basic_block bb)
> {
> + reductions.update (bb);
> +
> sese_info_p region = scop->scop_info;
> if (!bb_in_sese_p (bb, region->region))
> return dom_walker::STOP;
> @@ -1514,7 +1914,8 @@ gather_bbs::before_dom_children (basic_block bb)
>
> scop->scop_info->bbs.safe_push (bb);
>
> - gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
> + gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb, reductions,
> oacc_ctx);
> +
> if (!gbb)
> return NULL;
>
> @@ -1563,6 +1964,44 @@ gather_bbs::after_dom_children (basic_block bb)
> }
> }
>
> +/* Update the OpenACC reductions information for all basic blocks
> + encountered by the dom_walker. This is used to adjust the
> + reduction information for the basic blocks between the SCoPs (which
> + are processed by GATHER_BBS) in the BUILD_SCOPS function. */
> +
> +class oacc_reduction_walker : public dom_walker
> +{
> +public:
> + oacc_reduction_walker (oacc_reductions& reductions, edge end, int *);
> +
> + virtual edge before_dom_children (basic_block);
> +
> +private:
> + auto_vec<gimple *, 3> conditions, cases;
> + oacc_reductions& reductions;
> + edge end;
> +};
> +
> +oacc_reduction_walker::oacc_reduction_walker
> +(oacc_reductions& reductions, edge end, int *bb_to_rpo)
> +: dom_walker (CDI_DOMINATORS, ALL_BLOCKS, bb_to_rpo),
> + reductions (reductions),
> + end (end)
> +{
> +}
> +
> +edge
> +oacc_reduction_walker::before_dom_children (basic_block bb)
> +{
> + reductions.update (bb);
> +
> + if (bb == end->src)
> + return dom_walker::STOP;
> + else
> + return NULL;
> +}
> +
> +}
>
> /* Compute sth like an execution order, dominator order with first executing
> edges that stay inside the current loop, delaying processing exit edges.
> */
> @@ -1590,12 +2029,12 @@ cmp_pbbs (const void *pa, const void *pb)
> them to SCOPS. */
>
> void
> -build_scops (vec<scop_p> *scops)
> +build_scops (vec<scop_p> *scops, oacc_context *oacc_ctx)
> {
> if (dump_file)
> dp.set_dump_file (dump_file);
>
> - scop_detection sb;
> + scop_detection sb (oacc_ctx);
> sb.build_scop_depth (current_loops->tree_root);
>
> /* Now create scops from the lightweight SESEs. */
> @@ -1611,17 +2050,26 @@ build_scops (vec<scop_p> *scops)
>
> int i;
> sese_l *s;
> + basic_block reduction_walk_start = ENTRY_BLOCK_PTR_FOR_FN (cfun);
> + oacc_reductions reductions;
> +
> FOR_EACH_VEC_ELT (scops_l, i, s)
> {
> scop_p scop = new_scop (s->entry, s->exit);
>
> + edge reduction_walk_end = s->entry;
> + oacc_reduction_walker (reductions, reduction_walk_end, bb_to_rpo)
> + .walk (reduction_walk_start);
> + reduction_walk_start = s->exit->dest;
> +
> /* Record all basic blocks and their conditions in REGION. */
> - gather_bbs (CDI_DOMINATORS, scop, bb_to_rpo).walk (s->entry->dest);
> + gather_bbs (CDI_DOMINATORS, scop, bb_to_rpo, reductions, oacc_ctx)
> + .walk (s->entry->dest);
>
> /* Sort pbbs after execution order for initial schedule generation. */
> scop->pbbs.qsort (cmp_pbbs);
>
> - if (! build_alias_set (scop))
> + if (! build_alias_set (scop, oacc_ctx))
> {
> DEBUG_PRINT (dp << "[scop-detection-fail] cannot handle
> dependences\n");
> free_scop (scop);
> diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
> index c42415e0554..c6f07ea9a99 100644
> --- a/gcc/graphite-sese-to-poly.c
> +++ b/gcc/graphite-sese-to-poly.c
> @@ -36,6 +36,7 @@ along with GCC; see the file COPYING3. If not see
> #include "gimplify.h"
> #include "gimplify-me.h"
> #include "tree-cfg.h"
> +#include "tree-chrec-oacc.h"
> #include "tree-ssa-loop-manip.h"
> #include "tree-ssa-loop-niter.h"
> #include "tree-ssa-loop.h"
> @@ -209,6 +210,8 @@ parameter_index_in_region (tree name, sese_info_p region)
> return -1;
> }
>
> +tree oacc_ifn_call_extract (gimple*);
> +
> /* Extract an affine expression from the tree E in the scop S. */
>
> static isl_pw_aff *
> @@ -275,6 +278,13 @@ extract_affine (scop_p s, tree e, __isl_take isl_space
> *space)
> case SSA_NAME:
> {
> gcc_assert (! defined_in_sese_p (e, s->scop_info->region));
> + if (is_oacc_loop_ifn_call_def (e))
> + {
> + gimple* stmt = SSA_NAME_DEF_STMT (e);
> + return extract_affine (s, oacc_ifn_call_extract (stmt), space);
> +
> + }
> +
> int dim = parameter_index_in_region (e, s->scop_info);
> gcc_assert (dim != -1);
> /* No need to wrap a parameter. */
> @@ -643,8 +653,20 @@ build_poly_dr (dr_info &dri)
> subscript_sizes = pdr_add_data_dimensions (subscript_sizes, scop, dr);
> }
>
> - new_poly_dr (pbb, DR_STMT (dr), DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
> - acc, subscript_sizes);
> + bool representable = true;
> + for (unsigned i = 0; i < DR_NUM_DIMENSIONS (dr); ++i)
> + if (! graphite_can_represent_scev
> + (scop->scop_info->region, DR_ACCESS_FN (dr, i)))
> + representable = false;
> +
> + /* If non-affine access functions are not enabled, the DR should
> + have been rejected during SCoP detection. */
> + gcc_checking_assert (representable || flag_graphite_non_affine_accesses);
> +
> + poly_dr_type write_type = representable ? PDR_WRITE : PDR_MAY_WRITE;
> + poly_dr_type type = DR_IS_READ (dr) ? PDR_READ : write_type;
> +
> + new_poly_dr (pbb, DR_STMT (dr), type, acc, subscript_sizes);
> }
>
> static void
> diff --git a/gcc/graphite.c b/gcc/graphite.c
> index 27f1e486e1f..3661d92e601 100644
> --- a/gcc/graphite.c
> +++ b/gcc/graphite.c
> @@ -43,6 +43,8 @@ along with GCC; see the file COPYING3. If not see
> #include "cfghooks.h"
> #include "tree.h"
> #include "gimple.h"
> +#include "gimple-iterator.h"
> +#include "gimplify-me.h"
> #include "ssa.h"
> #include "fold-const.h"
> #include "gimple-iterator.h"
> @@ -58,6 +60,18 @@ along with GCC; see the file COPYING3. If not see
> #include "tree-ssa.h"
> #include "tree-into-ssa.h"
> #include "graphite.h"
> +#include "graphite-oacc.h"
> +#include "cgraph.h"
> +#include "gimple-pretty-print.h"
> +#include "print-tree.h"
> +
> +static bool have_isl = true;
> +
> +#ifdef ACCEL_COMPILER
> +static bool accel_compiler = true;
> +#else
> +static bool accel_compiler = false;
> +#endif
>
> /* Print global statistics to FILE. */
>
> @@ -348,6 +362,220 @@ canonicalize_loop_closed_ssa (loop_p loop, edge e)
> }
> }
>
> +struct goacc_parallel_info {
> + gcall* call;
> + loop_p loop;
> +};
> +
> +/* Find the first call to BUILT_IN_GOACC_PARALLEL in the given
> + function where the type of the ".omp_data_arr" argument matches the
> + given type. The type of that argument is sufficient to find the
> + call to the right outlined function, i.e. we don't need to check
> + the function name. Return this call or a NULL_TREE if there is no
> + such call in the function. */
> +
> +static goacc_parallel_info find_goacc_parallel_call (struct function* fn)
> +{
> + goacc_parallel_info result;
> +
> + basic_block bb;
> + FOR_EACH_BB_FN (bb, fn)
> + {
> + for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
> + gsi_next (&gsi))
> + {
> + gimple *call = gsi_stmt (gsi);
> + if (! is_gimple_call (call)
> + || ! gimple_call_builtin_p (call, BUILT_IN_NORMAL))
> + continue;
> +
> + built_in_function code =
> + DECL_FUNCTION_CODE (gimple_call_fndecl (call));
> + if (code != BUILT_IN_GOACC_PARALLEL)
> + continue;
> +
> + tree called_fn_addr = gimple_call_arg (call, 1);
> + gcc_checking_assert (TREE_CODE (called_fn_addr) == ADDR_EXPR);
> + tree called_fn = TREE_OPERAND (called_fn_addr, 0);
> +
> + if (called_fn != cfun->decl)
> + continue;
> +
> + result.call = (gcall*)call;
> + result.loop = bb->loop_father;
> + }
> + }
> +
> + return result;
> +}
> +
> +static tree
> +get_goacc_parallel_omp_data_arg (gimple* call)
> +{
> + gcc_checking_assert (is_gimple_call (call)
> + && gimple_call_builtin_p (call, BUILT_IN_NORMAL)
> + && DECL_FUNCTION_CODE (gimple_call_fndecl (call))
> + == BUILT_IN_GOACC_PARALLEL);
> + tree omp_data_ptr = gimple_call_arg (call, 3);
> + tree omp_data = TREE_OPERAND (omp_data_ptr, 0);
> +
> + return omp_data;
> +}
> +
> +/* TODO-kernels This was meant as a way to allow to peak into the
> + original function from an outlined function to see, for instance,
> + if some values are known to be constant since constant propagation
> + fails to propagate values into the outlined function. Currently
> + unused and can be removed. *
> +
> +/* Gather direct assignments to STRUCT in FN in MAP. Each field of
> + STRUCT that gets assigned to in FN is mapped to the corresponding
> + rhs of the last encountered assignment. */
> +
> +void
> +oacc_omp_data::gather_assignments (struct function *fn)
> +{
> + if (!fn)
> + return;
> +
> + basic_block bb;
> + FOR_EACH_BB_FN (bb, fn)
> + {
> + for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
> + gsi_next (&gsi))
> + {
> + gimple *assign = gsi_stmt (gsi);
> +
> + if (! is_gimple_assign (assign))
> + continue;
> +
> + tree lhs = gimple_assign_lhs (assign);
> + if (TREE_CODE (lhs) != COMPONENT_REF
> + || TREE_OPERAND (lhs, 0) != src_fn_arg)
> + continue;
> +
> + tree field = DECL_NAME (TREE_OPERAND (lhs, 1));
> +
> + oacc_data_field& value = field_map.get_or_insert (field);
> + value.src_var = gimple_assign_rhs1 (assign);
> + }
> + }
> +
> + unsigned i;
> + tree var;
> + FOR_EACH_VEC_SAFE_ELT (cfun->local_decls, i, var)
> + {
> + oacc_data_field* value = field_map.get (DECL_NAME (var));
> + if (value)
> + value->tgt_var = var;
> + }
> +}
> +
> +/* TODO-kernels This will have to be adapted to work with the
> +"exploded arguments" patch because the mapping of names from the
> +outlined function to the original function relies on the omp_data
> +arguments to the outlined function which don't exist after "exploding"
> +the arguments. */
> +
> +oacc_omp_data
> +oacc_omp_data::construct (struct function* fn)
> +{
> + tree omp_data_arr_arg = NULL_TREE;
> + loop_p call_loop = NULL;
> +
> + if (fn)
> + {
> + goacc_parallel_info info = find_goacc_parallel_call (fn);
> + gcall *parallel_call = info.call;
> + call_loop = info.loop;
> + gcc_checking_assert (parallel_call);
> + gcc_checking_assert (call_loop);
> +
> + omp_data_arr_arg = get_goacc_parallel_omp_data_arg (parallel_call);
> + gcc_checking_assert (omp_data_arr_arg);
> + }
> + tree omp_data_i_arg = DECL_ARGUMENTS (cfun->decl);
> +
> + oacc_omp_data omp_data;
> + omp_data.src_fn_arg = omp_data_arr_arg;
> + omp_data.tgt_fn_arg = omp_data_i_arg;
> + omp_data.loop = call_loop;
> +
> + omp_data.gather_assignments (fn);
> +
> + return omp_data;
> +}
> +
> +/* TODO-kernels How to implement this in a stable way? The name of the
> + original function may change (constprop?) which causes the search
> + to fail. */
> +
> +/* Return the function from which the OpenACC OUTLINED_FN
> + has been outlined. */
> +
> +static function*
> +find_oacc_src_fn (function* outlined_fn)
> +{
> + gcc_assert (! accel_compiler);
> + gcc_assert (oacc_function_p (outlined_fn));
> +
> + tree name = DECL_ASSEMBLER_NAME (outlined_fn->decl);
> + const char* id = IDENTIFIER_POINTER (name);
> + const unsigned len = IDENTIFIER_LENGTH (name);
> +
> + /* id is the name of the function from which the current
> + function has been outlined, followed by a suffix that starts
> + with ".omp_fn" */
> + unsigned i = 0;
> + for (; i < len; ++i)
> + if (id[i] == '.')
> + break;
> +
> + gcc_checking_assert (id[i] == '.');
> +
> + const char* src_id = ggc_alloc_string (id, i);
> + /* fprintf (stderr, "[%s] Looking for source function '%s'\n. ",
> __FUNCTION__, src_id); */
> + tree id_node = get_identifier (src_id);
> +
> + cgraph_node* n = cgraph_node::get_for_asmname (id_node);
> +
> + return n ? n->get_fun () : NULL;
> +
> + /* cgraph_node* node; */
> + /* FOR_EACH_FUNCTION (node) */
> + /* { */
> + /* tree node_name = DECL_ASSEMBLER_NAME (node->decl); */
> + /* const char* node_id = IDENTIFIER_POINTER (node_name); */
> +
> + /* fprintf (stderr, "[%s] Function '%s'\n. ", __FUNCTION__, node_id);
> */
> +
> + /* if (strcmp (src_id, node_id) == 0) */
> + /* return node->get_fun (); */
> + /* } */
> + /* return NULL; */
> +}
> +
> +oacc_context
> +oacc_context::build_context () {
> + if (! oacc_function_p (cfun))
> + return oacc_context::invalid_context ();
> +
> + struct function* src_fn (find_oacc_src_fn (cfun));
> + if (! src_fn)
> + {
> + if (dump_file)
> + fprintf (dump_file,
> + "Source function for outlined function %s not found.\n",
> + IDENTIFIER_POINTER (DECL_NAME (cfun->decl)));
> + /* return oacc_context::invalid_context (); */
> + }
> +
> + oacc_context context (oacc_omp_data::construct (src_fn));
> +
> + context.valid = true;
> + return context;
> +}
> +
> /* Converts the current loop closed SSA form to a canonical form
> expected by the Graphite code generation.
>
> @@ -405,6 +633,8 @@ canonicalize_loop_form (void)
>
> isl_ctx *the_isl_ctx;
>
> +extern void oacc_set_arg_evolutions ();
> +
> /* Perform a set of linear transforms on the loops of the current
> function. */
>
> @@ -417,10 +647,34 @@ graphite_transform_loops (void)
> vec<scop_p> scops = vNULL;
> isl_ctx *ctx;
>
> + bool is_oacc_function = oacc_function_p (cfun);
> +
> + oacc_context oacc_ctx(oacc_context::build_context ());
> + // TODO-kernels Clean this up
> + /* if (is_oacc_function && ! oacc_ctx.is_valid ()) */
> + /* { */
> + /* if (dump_file) */
> + /* fprintf (dump_file, "Could not build OpenACC context for function %s.
> " */
> + /* "Aborting Graphite.\n", current_function_name ()); */
> + /* return; */
> + /* } */
> +
> + if (dump_file && (dump_flags & TDF_DETAILS))
> + fprintf (dump_file, "\nTransforming Function: %s\n",
> + current_function_name ());
> +
> /* If a function is parallel it was most probably already run through
> graphite
> once. No need to run again. */
> - if (parallelized_function_p (cfun->decl))
> - return;
> +
> + /* TODO-kernels Stop marking kernels regions that should be
> + processed here as "parallelized". */
> + if (parallelized_function_p (cfun->decl) && ! is_oacc_function)
> + {
> +
> + if (dump_file)
> + fprintf (dump_file, "\nAlready parallelized function.\n");
> + return;
> + }
>
> calculate_dominance_info (CDI_DOMINATORS);
>
> @@ -445,7 +699,9 @@ graphite_transform_loops (void)
> seir_cache = new hash_map<sese_scev_hash, tree>;
>
> calculate_dominance_info (CDI_POST_DOMINATORS);
> - build_scops (&scops);
> +
> + oacc_set_arg_evolutions ();
> + build_scops (&scops, oacc_ctx.is_valid () ? &oacc_ctx : NULL);
> free_dominance_info (CDI_POST_DOMINATORS);
>
> /* Remove the fake exits before transform given they are not reflected
> @@ -520,6 +776,8 @@ graphite_transform_loops (void)
>
> #else /* If isl is not available: #ifndef HAVE_isl. */
>
> +static bool have_isl = false;
> +
> static void
> graphite_transform_loops (void)
> {
> @@ -532,7 +790,9 @@ graphite_transform_loops (void)
> static unsigned int
> graphite_transforms (struct function *fun)
> {
> - if (number_of_loops (fun) <= 1)
> + unsigned num_loops = number_of_loops (fun);
> + if (num_loops == 0
> + || (num_loops == 1 && !oacc_function_p (cfun)))
> return 0;
>
> graphite_transform_loops ();
> @@ -540,9 +800,34 @@ graphite_transforms (struct function *fun)
> return 0;
> }
>
> +
> +/* Return true if fun is an OpenACC outlined function that should be
> +handled by Graphite. */
> +
> +static inline bool oacc_enable_graphite_p (function *fun)
> +{
> + return !accel_compiler && flag_openacc && oacc_get_fn_attrib (fun->decl);
> +}
> +
> +
> static bool
> -gate_graphite_transforms (void)
> +gate_graphite_transforms (function *fun)
> {
> + bool oacc_enabled_graphite = oacc_enable_graphite_p (fun);
> + bool optimizing = global_options.x_optimize <= 0;
> +
> + /* Enabling Graphite if isl is not available aborts compilation.
> + Prefer to skip Graphite if compiling without optimisations,
> + but emit a warning. */
> + if (have_isl || optimizing)
> + flag_graphite_identity |= oacc_enabled_graphite;
> + else {
> + if (oacc_enabled_graphite)
> + warning (OPT_Wall, "Unable to enable Graphite on OpenACC regions,"
> + "because isl is not available");
> + }
> +
> +
> /* Enable -fgraphite pass if any one of the graphite optimization flags
> is turned on. */
> if (flag_graphite_identity
> @@ -576,7 +861,7 @@ public:
> {}
>
> /* opt_pass methods: */
> - virtual bool gate (function *) { return gate_graphite_transforms (); }
> + virtual bool gate (function *fun) { return gate_graphite_transforms (fun);
> }
>
> }; // class pass_graphite
>
> @@ -611,7 +896,7 @@ public:
> {}
>
> /* opt_pass methods: */
> - virtual bool gate (function *) { return gate_graphite_transforms (); }
> + virtual bool gate (function *fun) { return gate_graphite_transforms (fun);
> }
> virtual unsigned int execute (function *fun) { return graphite_transforms
> (fun); }
>
> }; // class pass_graphite_transforms
> @@ -624,4 +909,108 @@ make_pass_graphite_transforms (gcc::context *ctxt)
> return new pass_graphite_transforms (ctxt);
> }
>
> +/* Something like "n * m" is not allowed. */
> +
> +static bool
> +graphite_can_represent_init (tree e)
> +{
> + switch (TREE_CODE (e))
> + {
> + case POLYNOMIAL_CHREC:
> + return graphite_can_represent_init (CHREC_LEFT (e))
> + && graphite_can_represent_init (CHREC_RIGHT (e));
> +
> + case MULT_EXPR:
> + if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
> + return graphite_can_represent_init (TREE_OPERAND (e, 0))
> + && tree_fits_shwi_p (TREE_OPERAND (e, 1));
> + else
> + return graphite_can_represent_init (TREE_OPERAND (e, 1))
> + && tree_fits_shwi_p (TREE_OPERAND (e, 0));
> +
> + case PLUS_EXPR:
> + case POINTER_PLUS_EXPR:
> + case MINUS_EXPR:
> + return graphite_can_represent_init (TREE_OPERAND (e, 0))
> + && graphite_can_represent_init (TREE_OPERAND (e, 1));
> +
> + case NEGATE_EXPR:
> + case BIT_NOT_EXPR:
> + CASE_CONVERT:
> + case NON_LVALUE_EXPR:
> + return graphite_can_represent_init (TREE_OPERAND (e, 0));
> +
> + default:
> + break;
> + }
> +
> + return true;
> +}
> +
> +/* Return true when SCEV can be represented in the polyhedral model.
> +
> + An expression can be represented, if it can be expressed as an
> + affine expression. For loops (i, j) and parameters (m, n) all
> + affine expressions are of the form:
> +
> + x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
> +
> + 1 i + 20 j + (-2) m + 25
> +
> + Something like "i * n" or "n * m" is not allowed. */
>
> +bool
> +graphite_can_represent_scev (sese_l scop, tree scev)
> +{
> + if (chrec_contains_undetermined (scev))
> + return false;
> +
> + switch (TREE_CODE (scev))
> + {
> + case NEGATE_EXPR:
> + case BIT_NOT_EXPR:
> + CASE_CONVERT:
> + case NON_LVALUE_EXPR:
> + return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0));
> +
> + case PLUS_EXPR:
> + case POINTER_PLUS_EXPR:
> + case MINUS_EXPR:
> + return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
> + && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
> +
> + case MULT_EXPR:
> + return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
> + && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
> + && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
> + && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
> + && graphite_can_represent_init (scev)
> + && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
> + && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
> +
> + case POLYNOMIAL_CHREC:
> + /* Check for constant strides. With a non constant stride of
> + 'n' we would have a value of 'iv * n'. Also check that the
> + initial value can represented: for example 'n * m' cannot be
> + represented. */
> + gcc_assert (loop_in_sese_p (get_loop (cfun,
> + CHREC_VARIABLE (scev)), scop));
> + if (!evolution_function_right_is_integer_cst (scev)
> + || !graphite_can_represent_init (scev))
> + return false;
> + return graphite_can_represent_scev (scop, CHREC_LEFT (scev));
> +
> + case ADDR_EXPR:
> + /* We cannot encode addresses for ISL. */
> + return false;
> +
> + default:
> + break;
> + }
> +
> + /* Only affine functions can be represented. */
> + if (tree_contains_chrecs (scev, NULL) || !scev_is_linear_expression (scev))
> + return false;
> +
> + return true;
> +}
> diff --git a/gcc/graphite.h b/gcc/graphite.h
> index 3fe1345cf96..1e0ccd2de7b 100644
> --- a/gcc/graphite.h
> +++ b/gcc/graphite.h
> @@ -384,6 +384,10 @@ struct scop
> /* The maximum alias set as assigned to drs by build_alias_sets. */
> unsigned max_alias_set;
>
> + /* The set of dependent ddrs that were rejected by build_alias_set
> + and that must be handled by other means (runtime checking). */
> + auto_vec<ddr_p> unhandled_alias_ddrs;
> +
> /* All the basic blocks in this scop that contain memory references
> and that will be represented as statements in the polyhedral
> representation. */
> @@ -459,10 +463,15 @@ carries_deps (__isl_keep isl_union_map *schedule,
>
> extern bool build_poly_scop (scop_p);
> extern bool graphite_regenerate_ast_isl (scop_p);
> -extern void build_scops (vec<scop_p> *);
> +
> +class oacc_context;
> +extern void build_scops (vec<scop_p> *, oacc_context*);
> +
> extern tree cached_scalar_evolution_in_region (const sese_l &, loop_p, tree);
> extern void dot_all_sese (FILE *, vec<sese_l> &);
> extern void dot_sese (sese_l &);
> extern void dot_cfg ();
>
> +extern bool graphite_can_represent_scev (sese_l, tree);
> +
> #endif
> diff --git a/gcc/internal-fn.h b/gcc/internal-fn.h
> index 2ec3c504cd6..73c0e7d1880 100644
> --- a/gcc/internal-fn.h
> +++ b/gcc/internal-fn.h
> @@ -52,10 +52,13 @@ enum ifn_unique_kind {
>
> CHUNK_MAX = LOOP (CODE_CHUNKS, DIR, RANGE, STEP, CHUNK_SIZE, MASK)
> STEP = LOOP (CODE_STEP, DIR, RANGE, STEP, CHUNK_SIZE, MASK)
> - OFFSET = LOOP (CODE_OFFSET, DIR, RANGE, STEP, CHUNK_SIZE, MASK,
> CHUNK_NO)
> - BOUND = LOOP (CODE_BOUND, DIR, RANGE, STEP, CHUNK_SIZE, MASK, OFFSET)
> + OFFSET = LOOP (CODE_OFFSET, DIR, RANGE, STEP, CHUNK_SIZE, MASK, BASE,
> CHUNK_NO)
> + BOUND = LOOP (CODE_BOUND, DIR, RANGE, STEP, CHUNK_SIZE, MASK, END,
> OFFSET)
>
> DIR - +1 for up loop, -1 for down loop
> + BASE - Initial value of the loop's iteration variable.
> + END - Last value of the loop's iteration variable +1 or -1, depending
> on the
> + direction of the iteration.
> RANGE - Range of loop (END - BASE)
> STEP - iteration step size
> CHUNKING - size of chunking, (constant zero for no chunking)
> diff --git a/gcc/omp-expand.c b/gcc/omp-expand.c
> index 08afaceb87e..b3d21c1181d 100644
> --- a/gcc/omp-expand.c
> +++ b/gcc/omp-expand.c
> @@ -6015,8 +6015,8 @@ expand_omp_taskloop_for_inner (struct omp_region
> *region,
> T step = GOACC_LOOP_STEP (dir, range, S, CHUNK_SIZE, GWV);
>
> <head_bb> [created by splitting end of entry_bb]
> - T offset = GOACC_LOOP_OFFSET (dir, range, S, CHUNK_SIZE, GWV, chunk_no);
> - T bound = GOACC_LOOP_BOUND (dir, range, S, CHUNK_SIZE, GWV, offset);
> + T offset = GOACC_LOOP_OFFSET (dir, range, S, CHUNK_SIZE, GWV, b,
> chunk_no);
> + T bound = GOACC_LOOP_BOUND (dir, range, S, CHUNK_SIZE, GWV, e, offset);
> if (!(offset LTGT bound)) goto bottom_bb;
>
> <body_bb> [incoming]
> @@ -6270,20 +6270,22 @@ expand_oacc_for (struct omp_region *region, struct
> omp_for_data *fd)
> /* Loop offset & bound go into head_bb. */
> gsi = gsi_start_bb (head_bb);
>
> - call = gimple_build_call_internal (IFN_GOACC_LOOP, 7,
> + tree begin = force_gimple_operand_gsi (&gsi, unshare_expr (fd->loop.n1),
> true, NULL_TREE, true, GSI_SAME_STMT);
> + call = gimple_build_call_internal (IFN_GOACC_LOOP, 8,
> build_int_cst (integer_type_node,
> IFN_GOACC_LOOP_OFFSET),
> dir, range, s,
> - chunk_size, gwv, chunk_no);
> + chunk_size, gwv, begin, chunk_no);
> gimple_call_set_lhs (call, offset_init);
> gimple_set_location (call, loc);
> gsi_insert_after (&gsi, call, GSI_CONTINUE_LINKING);
>
> - call = gimple_build_call_internal (IFN_GOACC_LOOP, 7,
> + tree end = force_gimple_operand_gsi (&gsi, unshare_expr (fd->loop.n2),
> true, NULL_TREE, true, GSI_SAME_STMT);
> + call = gimple_build_call_internal (IFN_GOACC_LOOP, 8,
> build_int_cst (integer_type_node,
> IFN_GOACC_LOOP_BOUND),
> dir, range, s,
> - chunk_size, gwv, offset_init);
> + chunk_size, gwv, end, offset_init);
> gimple_call_set_lhs (call, bound);
> gimple_set_location (call, loc);
> gsi_insert_after (&gsi, call, GSI_CONTINUE_LINKING);
> @@ -6332,16 +6334,20 @@ expand_oacc_for (struct omp_region *region, struct
> omp_for_data *fd)
> tree t, e_gwv = integer_minus_one_node;
> tree chunk = build_int_cst (diff_type, 0); /* Never chunked. */
>
> + tree begin = force_gimple_operand_gsi (&gsi, unshare_expr
> (fd->loop.n1),
> + true, NULL_TREE, true,
> GSI_SAME_STMT);
> t = build_int_cst (integer_type_node, IFN_GOACC_LOOP_OFFSET);
> - call = gimple_build_call_internal (IFN_GOACC_LOOP, 7, t, dir,
> e_range,
> - element_s, chunk, e_gwv, chunk);
> + call = gimple_build_call_internal (IFN_GOACC_LOOP, 8, t, dir,
> e_range,
> + element_s, chunk, e_gwv, begin,
> chunk);
> gimple_call_set_lhs (call, e_offset);
> gimple_set_location (call, loc);
> gsi_insert_before (&gsi, call, GSI_SAME_STMT);
>
> + tree end = force_gimple_operand_gsi (&gsi, unshare_expr
> (fd->loop.n2),
> + true, NULL_TREE, true,
> GSI_SAME_STMT);
> t = build_int_cst (integer_type_node, IFN_GOACC_LOOP_BOUND);
> - call = gimple_build_call_internal (IFN_GOACC_LOOP, 7, t, dir,
> e_range,
> - element_s, chunk, e_gwv,
> e_offset);
> + call = gimple_build_call_internal (IFN_GOACC_LOOP, 8, t, dir,
> e_range,
> + element_s, chunk, e_gwv, end,
> e_offset);
> gimple_call_set_lhs (call, e_bound);
> gimple_set_location (call, loc);
> gsi_insert_before (&gsi, call, GSI_SAME_STMT);
> diff --git a/gcc/omp-offload.c b/gcc/omp-offload.c
> index a73b73fb41a..3e81e878cf9 100644
> --- a/gcc/omp-offload.c
> +++ b/gcc/omp-offload.c
> @@ -83,6 +83,8 @@ struct oacc_loop
> vec<gcall *> ifns; /* Contained loop abstraction functions. */
> tree chunk_size; /* Chunk size. */
> gcall *head_end; /* Final marker of head sequence. */
> +
> + bool can_be_parallel; /* Can the loop be parallelized?. */
> };
>
> /* Holds offload tables with decls. */
> @@ -657,7 +659,7 @@ oacc_xform_loop (gcall *call)
>
> if (chunking)
> {
> - tree chunk = fold_convert (diff_type, gimple_call_arg (call,
> 6));
> + tree chunk = fold_convert (diff_type, gimple_call_arg (call,
> 7));
> tree per
> = fold_build2 (MULT_EXPR, diff_type, volume, chunk_size);
> per = build2 (MULT_EXPR, diff_type, per, chunk);
> @@ -697,7 +699,7 @@ oacc_xform_loop (gcall *call)
>
> r = fold_build2 (MULT_EXPR, diff_type, span, step);
>
> - tree offset = gimple_call_arg (call, 6);
> + tree offset = gimple_call_arg (call, 7);
> r = build2 (PLUS_EXPR, diff_type, r,
> fold_convert (diff_type, offset));
> r = build2 (integer_onep (dir) ? MIN_EXPR : MAX_EXPR,
> @@ -911,7 +913,8 @@ oacc_validate_dims (tree fn, tree attrs, int *dims, int
> level, unsigned used)
> check = false;
> #endif
> if (check
> - && !lookup_attribute ("oacc kernels", DECL_ATTRIBUTES (fn)))
> + && !lookup_attribute ("oacc kernels", DECL_ATTRIBUTES (fn))
> + && !lookup_attribute ("oacc parallel_kernels_graphite",
> DECL_ATTRIBUTES (fn)))
> {
> static char const *const axes[] =
> /* Must be kept in sync with GOMP_DIM enumeration. */
> @@ -1015,6 +1018,11 @@ new_oacc_loop (oacc_loop *parent, gcall *marker)
> flags. */
>
> loop->flags = TREE_INT_CST_LOW (gimple_call_arg (marker, 3));
> + if (dump_file && (dump_flags & TDF_DETAILS))
> + dump_printf_loc (MSG_NOTE,
> + dump_user_location_t::from_location_t (loop->loc),
> + "[new_oacc_loop] Found loop %s 'auto' directive.\n",
> + loop->flags & OLF_AUTO ? "with" : "without");
>
> tree chunk_size = integer_zero_node;
> if (loop->flags & OLF_GANG_STATIC)
> @@ -1217,45 +1225,62 @@ oacc_loop_discover_walk (oacc_loop *loop, basic_block
> bb)
> break;
>
> case IFN_UNIQUE:
> - enum ifn_unique_kind kind
> - = (enum ifn_unique_kind) (TREE_INT_CST_LOW
> - (gimple_call_arg (call, 0)));
> - if (kind == IFN_UNIQUE_OACC_HEAD_MARK
> - || kind == IFN_UNIQUE_OACC_TAIL_MARK)
> - {
> - if (gimple_call_num_args (call) == 2)
> - {
> - gcc_assert (marker && !remaining);
> - marker = 0;
> - if (kind == IFN_UNIQUE_OACC_TAIL_MARK)
> - loop = finish_oacc_loop (loop);
> - else
> - loop->head_end = call;
> - }
> - else
> - {
> - int count = TREE_INT_CST_LOW (gimple_call_arg (call, 2));
> + {
> + enum ifn_unique_kind kind
> + = (enum ifn_unique_kind) (TREE_INT_CST_LOW
> + (gimple_call_arg (call, 0)));
> + if (kind == IFN_UNIQUE_OACC_HEAD_MARK
> + || kind == IFN_UNIQUE_OACC_TAIL_MARK)
> + {
> + if (gimple_call_num_args (call) == 2)
> + {
> + gcc_assert (marker && !remaining);
> + marker = 0;
> + if (kind == IFN_UNIQUE_OACC_TAIL_MARK)
> + loop = finish_oacc_loop (loop);
> + else
> + loop->head_end = call;
> + }
> + else
> + {
> + int count = TREE_INT_CST_LOW (gimple_call_arg (call, 2));
>
> - if (!marker)
> - {
> - if (kind == IFN_UNIQUE_OACC_HEAD_MARK)
> - loop = new_oacc_loop (loop, call);
> - remaining = count;
> - }
> - gcc_assert (count == remaining);
> - if (remaining)
> - {
> - remaining--;
> - if (kind == IFN_UNIQUE_OACC_HEAD_MARK)
> - loop->heads[marker] = call;
> - else
> - loop->tails[remaining] = call;
> - }
> - marker++;
> - }
> - }
> + if (!marker)
> + {
> + if (kind == IFN_UNIQUE_OACC_HEAD_MARK)
> + loop = new_oacc_loop (loop, call);
> +
> + remaining = count;
> + }
> + gcc_assert (count == remaining);
> + if (remaining)
> + {
> + remaining--;
> + if (kind == IFN_UNIQUE_OACC_HEAD_MARK)
> + loop->heads[marker] = call;
> + else
> + loop->tails[remaining] = call;
> + }
> + marker++;
> + }
> + }
> + break;
> + }
> +
> + case IFN_GOACC_REDUCTION:
> + break;
> }
> }
> +
> + if (bb->loop_father->can_be_parallel)
> + {
> + loop->can_be_parallel = true;
> + const dump_user_location_t loc
> + = dump_user_location_t::from_location_t (loop->loc);
> + if (dump_file)
> + dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc, "Detected
> parallelizable loop.");
> + }
> +
> if (remaining || marker)
> {
> bb = single_succ (bb);
> @@ -1411,12 +1436,61 @@ oacc_loop_process (oacc_loop *loop)
> oacc_loop_process (loop->sibling);
> }
>
> -/* Walk the OpenACC loop heirarchy checking and assigning the
> +/* Interpret the "can_be_parallel" flag of the LOOP to decide
> + if it can be made "independent" */
> +
> +static bool oacc_loop_parallelize (oacc_loop *loop) {
> + if (loop->routine)
> + return false;
> +
> + if (!(loop->flags & OLF_AUTO))
> + {
> + if (dump_file && (dump_flags & TDF_DETAILS))
> + dump_printf_loc (MSG_NOTE,
> + dump_user_location_t::from_location_t (loop->loc),
> + "[oacc_loop_parallelize] Not an 'auto' loop.\n");
> +
> +
> + return false;
> + }
> +
> + if (!loop->can_be_parallel)
> + {
> + if (dump_file && (dump_flags & TDF_DETAILS))
> + dump_printf_loc (MSG_MISSED_OPTIMIZATION,
> + dump_user_location_t::from_location_t (loop->loc),
> + "'auto' loop cannot be parallel.\n");
> + return false;
> + }
> +
> + if (dump_file && (dump_flags & TDF_DETAILS))
> + dump_printf_loc (MSG_OPTIMIZED_LOCATIONS,
> + dump_user_location_t::from_location_t (loop->loc),
> + "'auto' loop can be parallel.\n");
> +
> + loop->flags |= OLF_INDEPENDENT;
> +
> + if (dump_file && (dump_flags & TDF_DETAILS))
> + fprintf (dump_file, "[oacc_loop_parallelize] %s:%u Transformed 'auto'
> into 'independent'.\n",
> + LOCATION_FILE (loop->loc), LOCATION_LINE (loop->loc));
> +
> + // loop->flags &= ~OLF_AUTO;
> + /* TODO-kernels Right now we need to keep the OLF_AUTO flag for
> + further processing in oacc_loop_fixed_partitions and
> + oacc_loop_auto_partitions. We should remove it here and use
> + another flag to indicate that the partitioning must be
> + assigned. */
> +
> + return true;
> +}
> +
> +/* Walk the OpenACC loop hierarchy checking and assigning the
> programmer-specified partitionings. OUTER_MASK is the partitioning
> this loop is contained within. Return mask of partitioning
> encountered. If any auto loops are discovered, set GOMP_DIM_MAX
> bit. */
>
> +
> static unsigned
> oacc_loop_fixed_partitions (oacc_loop *loop, unsigned outer_mask)
> {
> @@ -1446,14 +1520,18 @@ oacc_loop_fixed_partitions (oacc_loop *loop, unsigned
> outer_mask)
>
> if ((this_mask != 0) + auto_par + seq_par > 1)
> {
> - if (noisy)
> - error_at (loop->loc,
> - seq_par
> - ? G_("%<seq%> overrides other OpenACC loop specifiers")
> - : G_("%<auto%> conflicts with other OpenACC loop "
> - "specifiers"));
> + if (seq_par && noisy)
> + error_at (loop->loc, G_("%<seq%> overrides other OpenACC loop
> specifiers"));
> maybe_auto = false;
> +
> + if (dump_file && (dump_flags & TDF_DETAILS))
> + dump_printf_loc (MSG_NOTE,
> + dump_user_location_t::from_location_t
> (loop->loc),
> + "[oacc_loop_fixed_partitions] Removed
> 'auto'.\n");
> +
> +
> loop->flags &= ~OLF_AUTO;
> +
> if (seq_par)
> {
> loop->flags
> @@ -1467,6 +1545,9 @@ oacc_loop_fixed_partitions (oacc_loop *loop, unsigned
> outer_mask)
> loop->flags |= OLF_AUTO;
> mask_all |= GOMP_DIM_MASK (GOMP_DIM_MAX);
> }
> +
> + if (oacc_loop_parallelize (loop))
> + mask_all |= GOMP_DIM_MASK (GOMP_DIM_MAX);
> }
>
> if (this_mask & outer_mask)
> diff --git a/gcc/predict.c b/gcc/predict.c
> index a7ae977c866..c44aac58f28 100644
> --- a/gcc/predict.c
> +++ b/gcc/predict.c
> @@ -4035,7 +4035,7 @@ pass_profile::execute (function *fun)
> class loop *loop;
> FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
> if (loop->header->count.initialized_p ())
> - fprintf (dump_file, "Loop got predicted %d to iterate %i times.\n",
> + fprintf (dump_file, "Loop %d got predicted to iterate %i times.\n",
> loop->num,
> (int)expected_loop_iterations_unbounded (loop));
> }
> diff --git a/gcc/testsuite/gcc.dg/graphite/alias-0-no-runtime-check.c
> b/gcc/testsuite/gcc.dg/graphite/alias-0-no-runtime-check.c
> new file mode 100644
> index 00000000000..7228fb09818
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/graphite/alias-0-no-runtime-check.c
> @@ -0,0 +1,20 @@
> +/* This test demonstrates a loop nest that Graphite cannot handle
> + because of aliasing. But the loop nest can be handled with enabled
> + runtime alias checking. */
> +
> +/* { dg-options "-O2 -fgraphite-identity -fno-graphite-runtime-alias-checks
> -fdump-tree-graphite-details" } */
> +
> +void sum(int *x, int *y, unsigned *sum)
> +{
> + unsigned i,j;
> + *sum = 0;
> +
> + for (i = 0; i < 10000; i=i+1)
> + {
> + int xi = x[i];
> + for (j = 0; j < 22222; j=j+1)
> + *sum += xi + y[j];
> + }
> +}
> +
> +/* { dg-final { scan-tree-dump "number of SCoPs: 0" "graphite"} } */
> diff --git a/gcc/testsuite/gcc.dg/graphite/alias-0-runtime-check.c
> b/gcc/testsuite/gcc.dg/graphite/alias-0-runtime-check.c
> new file mode 100644
> index 00000000000..a9f9ef99908
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/graphite/alias-0-runtime-check.c
> @@ -0,0 +1,21 @@
> +/* This test demonstrates a loop nest that Graphite cannot handle
> + because of aliasing. But the loop nest can be handled with enabled
> + runtime alias checking. */
> +
> +/* { dg-options "-O2 -fgraphite-identity -fgraphite-runtime-alias-checks
> -fdump-tree-graphite-details" } */
> +
> +void sum(int *x, int *y, unsigned *sum)
> +{
> + unsigned i,j;
> + *sum = 0;
> +
> + for (i = 0; i < 10000; i=i+1)
> + {
> + int xi = x[i];
> + for (j = 0; j < 22222; j=j+1)
> + *sum += xi + y[j];
> + }
> +}
> +
> +/* { dg-final { scan-tree-dump "number of SCoPs: 1" "graphite"} } */
> +/* { dg-final { scan-tree-dump "Generated runtime alias
> check.*?sum_.*?x_.*?y_.*?\n" "graphite"} } */
> diff --git a/gcc/testsuite/gcc.dg/graphite/alias-1.c
> b/gcc/testsuite/gcc.dg/graphite/alias-1.c
> new file mode 100644
> index 00000000000..ee80dae1df3
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/graphite/alias-1.c
> @@ -0,0 +1,22 @@
> +/* This test demonstrates a loop nest that Graphite cannot handle
> + because of aliasing. It should be possible to handle this loop nest
> + by creating a runtime alias check like in the very similar test
> + alias-0-runtime-check.c. However Graphite analyses the data
> + reference with respect to the innermost loop that contains the data
> + reference, the variable "i" remains uninstantiated (in contrast to
> + "j"), and consequently the alias check cannot be placed outside of
> + the SCoP since "i" is not defined there. */
> +
> +/* { dg-options "-O2 -fgraphite-identity -fgraphite-runtime-alias-checks
> -fdump-tree-graphite-details" } */
> +
> +void sum(int *x, int *y, unsigned *sum)
> +{
> + unsigned i,j;
> + *sum = 0;
> +
> + for (i = 0; i < 10000; i=i+1)
> + for (j = 0; j < 22222; j=j+1)
> + *sum += x[i] + y[j];
> +}
> +
> +/* { dg-final { scan-tree-dump "number of SCoPs: 1" "graphite" { xfail *-*-*
> } } } */
> diff --git a/gcc/tree-chrec-oacc.h b/gcc/tree-chrec-oacc.h
> new file mode 100644
> index 00000000000..bcbb1e03657
> --- /dev/null
> +++ b/gcc/tree-chrec-oacc.h
> @@ -0,0 +1,45 @@
> +/* OpenACC helpers for Chains of recurrences.
> + Copyright (C) 2003-2020 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/>. */
> +
> +#ifndef GCC_TREE_CHREC_OACC_H
> +#define GCC_TREE_CHREC_OACC_H
> +
> +#include <gimple.h>
> +#include <internal-fn.h>
> +
> +/* Check if the tree is an SSA_NAME whose defining statement
> + is a call to a IFN_GOACC_LOOP function. */
> +static inline bool
> +is_oacc_loop_ifn_call_def (tree t) {
> + tree_code code = TREE_CODE (t);
> + return (code == SSA_NAME
> + && gimple_call_internal_p (SSA_NAME_DEF_STMT (t), IFN_GOACC_LOOP));
> +}
> +
> +/* Check if the tree is an SSA_NAME whose defining statement
> + is a call to a IFN_GOACC_LOOP function. */
> +static inline bool
> +is_oacc_ifn_call_def (tree t) {
> + if (TREE_CODE (t) != SSA_NAME)
> + return false;
> +
> + return (gimple_call_internal_p (SSA_NAME_DEF_STMT (t), IFN_GOACC_LOOP)
> + || gimple_call_internal_p (SSA_NAME_DEF_STMT (t),
> IFN_GOACC_REDUCTION));
> +}
> +#endif /* GCC_TREE_CHREC_OACC_H */
> diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c
> index a8848067040..f536d6001ce 100644
> --- a/gcc/tree-chrec.c
> +++ b/gcc/tree-chrec.c
> @@ -1744,8 +1744,17 @@ scev_is_linear_expression (tree scev)
> }
> }
>
> -/* Determines whether the expression CHREC contains only interger consts
> - in the right parts. */
> +static bool
> +is_oacc_loop_call (tree chrec) {
> + return TREE_CODE (chrec) == SSA_NAME
> + && gimple_call_internal_p (SSA_NAME_DEF_STMT (chrec),
> + IFN_GOACC_LOOP);
> +
> +}
> +
> +/* Determines whether the expression CHREC contains only integer
> + consts in the right parts. OpenACC internal function calls
> + which encode integer constants are also admitted. */
>
> bool
> evolution_function_right_is_integer_cst (const_tree chrec)
> @@ -1759,7 +1768,8 @@ evolution_function_right_is_integer_cst (const_tree
> chrec)
> return true;
>
> case POLYNOMIAL_CHREC:
> - return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
> + return (TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
> + || is_oacc_loop_call (CHREC_RIGHT (chrec)))
> && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
> || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
>
> diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
> index 5505ba46778..9094b2ac45d 100644
> --- a/gcc/tree-data-ref.c
> +++ b/gcc/tree-data-ref.c
> @@ -85,6 +85,7 @@ along with GCC; see the file COPYING3. If not see
> #include "fold-const.h"
> #include "expr.h"
> #include "gimple-iterator.h"
> +#include "tree-chrec-oacc.h"
> #include "tree-ssa-loop-niter.h"
> #include "tree-ssa-loop.h"
> #include "tree-ssa.h"
> @@ -97,6 +98,8 @@ along with GCC; see the file COPYING3. If not see
> #include "tree-eh.h"
> #include "ssa.h"
> #include "internal-fn.h"
> +#include "print-tree.h"
> +#include "graphite-oacc.h"
>
> static struct datadep_stats
> {
> @@ -884,18 +887,23 @@ canonicalize_base_object_address (tree addr)
> dummy outermost loop. In other cases perform loop analysis.
>
> Return true if the analysis succeeded and store the results in DRB if so.
> - BB analysis can only fail for bitfield or reversed-storage accesses. */
> + BB analysis can only fail for bitfield or reversed-storage accesses.
> +
> + If ALLOW_NON_AFFINE_BASE is true, the function will not return false if
> + the base is non-affine. */
>
> opt_result
> dr_analyze_innermost (innermost_loop_behavior *drb, tree ref,
> - class loop *loop, const gimple *stmt)
> + class loop *loop, const gimple *stmt,
> + // TODO-kernels Rename (also allows non affine offset)
> + bool allow_non_affine_base)
> {
> poly_int64 pbitsize, pbitpos;
> tree base, poffset;
> machine_mode pmode;
> int punsignedp, preversep, pvolatilep;
> affine_iv base_iv, offset_iv;
> - tree init, dinit, step;
> + tree init, dinit;
> bool in_loop = (loop && loop->num);
>
> if (dump_file && (dump_flags & TDF_DETAILS))
> @@ -945,17 +953,20 @@ dr_analyze_innermost (innermost_loop_behavior *drb,
> tree ref,
> else
> base = build_fold_addr_expr (base);
>
> + bool affine_base = true;
> if (in_loop)
> {
> - if (!simple_iv (loop, loop, base, &base_iv, true))
> + affine_base = simple_iv (loop, loop, base, &base_iv, true);
> + if (!affine_base && !allow_non_affine_base)
> return opt_result::failure_at
> (stmt, "failed: evolution of base is not affine.\n");
> }
> - else
> +
> + if (!in_loop || !affine_base)
> {
> base_iv.base = base;
> base_iv.step = ssize_int (0);
> - base_iv.no_overflow = true;
> + base_iv.no_overflow = affine_base ? false : true;
> }
>
> if (!poffset)
> @@ -965,14 +976,18 @@ dr_analyze_innermost (innermost_loop_behavior *drb,
> tree ref,
> }
> else
> {
> - if (!in_loop)
> - {
> - offset_iv.base = poffset;
> - offset_iv.step = ssize_int (0);
> - }
> - else if (!simple_iv (loop, loop, poffset, &offset_iv, true))
> - return opt_result::failure_at
> - (stmt, "failed: evolution of offset is not affine.\n");
> + offset_iv.base = poffset;
> + offset_iv.step = ssize_int (0);
> +
> + if (in_loop && ! simple_iv (loop, loop, poffset, &offset_iv, true)) {
> + if (!allow_non_affine_base)
> + return opt_result::failure_at
> + (stmt, "failed: evolution of offset is not affine.\n");
> + offset_iv.base = poffset;
> + offset_iv.step = ssize_int (0);
> +
> +
> + }
> }
>
> init = ssize_int (pbytepos);
> @@ -983,14 +998,8 @@ dr_analyze_innermost (innermost_loop_behavior *drb, tree
> ref,
> init = size_binop (PLUS_EXPR, init, dinit);
> base_misalignment -= TREE_INT_CST_LOW (dinit);
>
> - split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
> - init = size_binop (PLUS_EXPR, init, dinit);
> -
> - step = size_binop (PLUS_EXPR,
> - fold_convert (ssizetype, base_iv.step),
> - fold_convert (ssizetype, offset_iv.step));
> -
> base = canonicalize_base_object_address (base_iv.base);
> + split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
>
> /* See if get_pointer_alignment can guarantee a higher alignment than
> the one we calculated above. */
> @@ -1013,7 +1022,10 @@ dr_analyze_innermost (innermost_loop_behavior *drb,
> tree ref,
> drb->base_address = base;
> drb->offset = fold_convert (ssizetype, offset_iv.base);
> drb->init = init;
> - drb->step = step;
> + drb->step = size_binop (PLUS_EXPR,
> + fold_convert (ssizetype, base_iv.step),
> + fold_convert (ssizetype, offset_iv.step));
> +
> if (known_misalignment (base_misalignment, base_alignment,
> &drb->base_misalignment))
> drb->base_alignment = base_alignment;
> @@ -1023,7 +1035,7 @@ dr_analyze_innermost (innermost_loop_behavior *drb,
> tree ref,
> drb->base_misalignment = 0;
> }
> drb->offset_alignment = highest_pow2_factor (offset_iv.base);
> - drb->step_alignment = highest_pow2_factor (step);
> + drb->step_alignment = highest_pow2_factor (drb->step);
>
> if (dump_file && (dump_flags & TDF_DETAILS))
> fprintf (dump_file, "success.\n");
> @@ -1096,7 +1108,9 @@ dr_analyze_indices (struct data_reference *dr, edge
> nest, loop_p loop)
> {
> op = TREE_OPERAND (ref, 1);
> access_fn = analyze_scalar_evolution (loop, op);
> - access_fn = instantiate_scev (nest, loop, access_fn);
> + tree instantiated_fn = instantiate_scev (nest, loop, access_fn);
> + if (instantiated_fn)
> + access_fn = instantiated_fn;
> access_fns.safe_push (access_fn);
> }
> else if (TREE_CODE (ref) == COMPONENT_REF
> @@ -1128,7 +1142,9 @@ dr_analyze_indices (struct data_reference *dr, edge
> nest, loop_p loop)
> {
> op = TREE_OPERAND (ref, 0);
> access_fn = analyze_scalar_evolution (loop, op);
> - access_fn = instantiate_scev (nest, loop, access_fn);
> + tree instantiated_fn = instantiate_scev (nest, loop, access_fn);
> + if (instantiated_fn)
> + access_fn = instantiated_fn;
> if (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
> {
> tree orig_type;
> @@ -1230,11 +1246,15 @@ free_data_ref (data_reference_p dr)
>
> Return the data_reference description of MEMREF. NEST is the outermost
> loop in which the reference should be instantiated, LOOP is the loop
> - in which the data reference should be analyzed. */
> + in which the data reference should be analyzed.
> +
> + If ALLOW_NON_AFFINE_BASE is true, the function will not fail if the
> + base is non-affine. */
>
> struct data_reference *
> create_data_ref (edge nest, loop_p loop, tree memref, gimple *stmt,
> - bool is_read, bool is_conditional_in_stmt)
> + bool is_read, bool is_conditional_in_stmt,
> + bool allow_non_affine_base)
> {
> struct data_reference *dr;
>
> @@ -1252,7 +1272,8 @@ create_data_ref (edge nest, loop_p loop, tree memref,
> gimple *stmt,
> DR_IS_CONDITIONAL_IN_STMT (dr) = is_conditional_in_stmt;
>
> dr_analyze_innermost (&DR_INNERMOST (dr), memref,
> - nest != NULL ? loop : NULL, stmt);
> + nest != NULL ? loop : NULL, stmt,
> + allow_non_affine_base);
> dr_analyze_indices (dr, nest, loop);
> dr_analyze_alias (dr);
>
> @@ -5422,6 +5443,7 @@ struct data_ref_loc
> bool is_conditional_in_stmt;
> };
>
> +tree oacc_ifn_call_extract (gimple *call);
>
> /* Stores the locations of memory references in STMT to REFERENCES. Returns
> true if STMT clobbers memory, false otherwise. */
> @@ -5444,6 +5466,10 @@ get_references_in_stmt (gimple *stmt,
> vec<data_ref_loc, va_heap> *references)
> if (gimple_call_internal_p (stmt))
> switch (gimple_call_internal_fn (stmt))
> {
> + case IFN_GOACC_REDUCTION:
> + case IFN_UNIQUE:
> + case IFN_GOACC_LOOP:
> + break;
> case IFN_GOMP_SIMD_LANE:
> {
> class loop *loop = gimple_bb (stmt)->loop_father;
> @@ -5519,6 +5545,25 @@ get_references_in_stmt (gimple *stmt,
> vec<data_ref_loc, va_heap> *references)
> ptr);
> references->safe_push (ref);
> return false;
> + case IFN_GOACC_LOOP:
> + /* Treat this like a reference to the data from the
> + original loop (offset, bound etc.) that has been
> + replaced by the internal function call in
> + omp-expand.c. */
> +
> + op0 = gimple_call_lhs (stmt);
> + op1 = oacc_ifn_call_extract (stmt);
> +
> + if (DECL_P (op1)
> + || (REFERENCE_CLASS_P (op1) && get_base_address (op1)))
> + {
> + ref.ref = op1;
> + ref.is_read = true;
> + ref.is_conditional_in_stmt = false;
> + references->safe_push (ref);
> + }
> + return false;
> +
> default:
> break;
> }
> @@ -5616,11 +5661,15 @@ find_data_references_in_stmt (class loop *nest,
> gimple *stmt,
> unanalyzable reference, returns false, otherwise returns true.
> NEST is the outermost loop of the loop nest in which the references
> should be instantiated, LOOP is the loop in which the references
> - should be analyzed. */
> + should be analyzed.
> + If ALLOW_NON_AFFINE_BASE is true, the data references are allowed
> + to have a non-affine base. */
>
> bool
> graphite_find_data_references_in_stmt (edge nest, loop_p loop, gimple *stmt,
> - vec<data_reference_p> *datarefs)
> + vec<data_reference_p> *datarefs,
> + oacc_context *oacc_ctx,
> + bool allow_non_affine_base)
> {
> unsigned i;
> auto_vec<data_ref_loc, 2> references;
> @@ -5634,7 +5683,8 @@ graphite_find_data_references_in_stmt (edge nest,
> loop_p loop, gimple *stmt,
> FOR_EACH_VEC_ELT (references, i, ref)
> {
> dr = create_data_ref (nest, loop, ref->ref, stmt, ref->is_read,
> - ref->is_conditional_in_stmt);
> + ref->is_conditional_in_stmt,
> + allow_non_affine_base);
> gcc_assert (dr != NULL);
> datarefs->safe_push (dr);
> }
> diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h
> index 771d20fbbc3..2d82e0ad923 100644
> --- a/gcc/tree-data-ref.h
> +++ b/gcc/tree-data-ref.h
> @@ -515,7 +515,7 @@ typedef struct data_dependence_relation *ddr_p;
>
>
> opt_result dr_analyze_innermost (innermost_loop_behavior *, tree,
> - class loop *, const gimple *);
> + class loop *, const gimple *, bool = false);
> extern bool compute_data_dependences_for_loop (class loop *, bool,
> vec<loop_p> *,
> vec<data_reference_p> *,
> @@ -539,12 +539,14 @@ extern void free_data_ref (data_reference_p);
> extern void free_data_refs (vec<data_reference_p> );
> extern opt_result find_data_references_in_stmt (class loop *, gimple *,
> vec<data_reference_p> *);
> +class oacc_context;
> extern bool graphite_find_data_references_in_stmt (edge, loop_p, gimple *,
> - vec<data_reference_p> *);
> + vec<data_reference_p> *,
> + oacc_context *, bool);
> tree find_data_references_in_loop (class loop *, vec<data_reference_p> *);
> bool loop_nest_has_data_refs (loop_p loop);
> struct data_reference *create_data_ref (edge, loop_p, tree, gimple *, bool,
> - bool);
> + bool, bool = false);
> extern bool find_loop_nest (class loop *, vec<loop_p> *);
> extern struct data_dependence_relation *initialize_data_dependence_relation
> (struct data_reference *, struct data_reference *, vec<loop_p>);
> diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c
> index 888af48946f..1ac27569a03 100644
> --- a/gcc/tree-loop-distribution.c
> +++ b/gcc/tree-loop-distribution.c
> @@ -2572,15 +2572,24 @@ latch_dominated_by_data_ref (class loop *loop,
> data_reference *dr)
> /* Compute alias check pairs and store them in COMP_ALIAS_PAIRS for LOOP's
> data dependence relations ALIAS_DDRS. */
>
> -static void
> +void
> compute_alias_check_pairs (class loop *loop, vec<ddr_p> *alias_ddrs,
> vec<dr_with_seg_len_pair_t> *comp_alias_pairs)
> {
> unsigned int i;
> unsigned HOST_WIDE_INT factor = 1;
> - tree niters_plus_one, niters = number_of_latch_executions (loop);
> + tree niters_plus_one, niters;
>
> + if (loop->num == 0)
> + {
> + /* Loop 0 is not at real loop and hence it has no niter information.
> + It executes once. */
> + niters = build_int_cst (integer_type_node, 1);
> + }
> + else
> + niters = number_of_latch_executions (loop);
> gcc_assert (niters != NULL_TREE && niters != chrec_dont_know);
> +
> niters = fold_convert (sizetype, niters);
> niters_plus_one = size_binop (PLUS_EXPR, niters, size_one_node);
>
> @@ -2595,12 +2604,12 @@ compute_alias_check_pairs (class loop *loop,
> vec<ddr_p> *alias_ddrs,
> struct data_reference *dr_b = DDR_B (ddr);
> tree seg_length_a, seg_length_b;
>
> - if (latch_dominated_by_data_ref (loop, dr_a))
> + if (loop->num != 0 && latch_dominated_by_data_ref (loop, dr_a))
> seg_length_a = data_ref_segment_size (dr_a, niters_plus_one);
> else
> seg_length_a = data_ref_segment_size (dr_a, niters);
>
> - if (latch_dominated_by_data_ref (loop, dr_b))
> + if (loop->num != 0 && latch_dominated_by_data_ref (loop, dr_b))
> seg_length_b = data_ref_segment_size (dr_b, niters_plus_one);
> else
> seg_length_b = data_ref_segment_size (dr_b, niters);
> diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
> index edab778277b..466aa65d899 100644
> --- a/gcc/tree-scalar-evolution.c
> +++ b/gcc/tree-scalar-evolution.c
> @@ -264,6 +264,8 @@ along with GCC; see the file COPYING3. If not see
> #include "gimple.h"
> #include "ssa.h"
> #include "gimple-pretty-print.h"
> +#include "tree-pretty-print.h"
> +#include "print-tree.h"
> #include "fold-const.h"
> #include "gimplify.h"
> #include "gimple-iterator.h"
> @@ -276,6 +278,7 @@ along with GCC; see the file COPYING3. If not see
> #include "tree-ssa.h"
> #include "cfgloop.h"
> #include "tree-chrec.h"
> +#include "tree-chrec-oacc.h"
> #include "tree-affine.h"
> #include "tree-scalar-evolution.h"
> #include "dumpfile.h"
> @@ -284,6 +287,8 @@ along with GCC; see the file COPYING3. If not see
> #include "tree-into-ssa.h"
> #include "builtins.h"
> #include "case-cfn-macros.h"
> +#include "omp-offload.h"
> +#include "internal-fn.h"
>
> static tree analyze_scalar_evolution_1 (class loop *, tree);
> static tree analyze_scalar_evolution_for_address_of (class loop *loop,
> @@ -550,11 +555,32 @@ get_scalar_evolution (basic_block instantiated_below,
> tree scalar)
> switch (TREE_CODE (scalar))
> {
> case SSA_NAME:
> + {
> if (SSA_NAME_IS_DEFAULT_DEF (scalar))
> res = scalar;
> else
> - res = *find_var_scev_info (instantiated_below, scalar);
> + {
> + // TODO-kernels Should no longer be necessary, cf.
> oacc_set_arg_evolutions
> + res = *find_var_scev_info (instantiated_below, scalar);
> + if (res)
> + break;
> +
> + tree name = SSA_NAME_IDENTIFIER (scalar);
> +
> + if (name)
> + {
> + const char* id = IDENTIFIER_POINTER (name);
> + if (strncmp (id, ".bound", 6) == 0
> + || strncmp (id, ".offset", 7) == 0
> + || strncmp (id, ".chunk_max", 11) == 0
> + || strncmp (id, ".chunk_no", 10) == 0
> + || strncmp (id, ".step", 5) == 0)
> + res = scalar;
> + }
> +
> + }
> break;
> + }
>
> case REAL_CST:
> case FIXED_CST:
> @@ -1115,6 +1141,7 @@ follow_ssa_edge_inner_loop_phi (class loop *outer_loop,
> return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi,
> evolution_of_loop, limit);
> }
> +tree interpret_gimple_call (class loop *loop, gimple *call);
>
> /* Follow the ssa edge into the expression EXPR.
> Return true if the strongly connected component has been found. */
> @@ -1125,7 +1152,9 @@ follow_ssa_edge_expr (class loop *loop, gimple
> *at_stmt, tree expr,
> int limit)
> {
> enum tree_code code;
> - tree type, rhs0, rhs1 = NULL_TREE;
> + tree type = NULL_TREE;
> + tree rhs0 = NULL_TREE;
> + tree rhs1 = NULL_TREE;
>
> /* The EXPR is one of the following cases:
> - an SSA_NAME,
> @@ -1189,26 +1218,36 @@ tail_recurse:
>
> /* At this level of abstraction, the program is just a set
> of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
> - other def to be handled. */
> - if (!is_gimple_assign (def))
> - return t_false;
> -
> - code = gimple_assign_rhs_code (def);
> - switch (get_gimple_rhs_class (code))
> + other def to be handled except for OpenACC internal function calls.
> + */
> + if (is_gimple_assign (def)) {
> + code = gimple_assign_rhs_code (def);
> + switch (get_gimple_rhs_class (code))
> + {
> + case GIMPLE_BINARY_RHS:
> + rhs0 = gimple_assign_rhs1 (def);
> + rhs1 = gimple_assign_rhs2 (def);
> + break;
> + case GIMPLE_UNARY_RHS:
> + case GIMPLE_SINGLE_RHS:
> + rhs0 = gimple_assign_rhs1 (def);
> + break;
> + default:
> + return t_false;
> + }
> + type = TREE_TYPE (gimple_assign_lhs (def));
> + at_stmt = def;
> + }
> + else if (is_oacc_ifn_call_def (expr)) {
> + rhs0 = interpret_gimple_call (loop, def);
> + type = TREE_TYPE (gimple_call_lhs (def));
> + at_stmt = def;
> + }
> + else
> {
> - case GIMPLE_BINARY_RHS:
> - rhs0 = gimple_assign_rhs1 (def);
> - rhs1 = gimple_assign_rhs2 (def);
> - break;
> - case GIMPLE_UNARY_RHS:
> - case GIMPLE_SINGLE_RHS:
> - rhs0 = gimple_assign_rhs1 (def);
> - break;
> - default:
> return t_false;
> }
> - type = TREE_TYPE (gimple_assign_lhs (def));
> - at_stmt = def;
> +
> }
> else
> {
> @@ -1920,7 +1959,75 @@ interpret_gimple_assign (class loop *loop, gimple
> *stmt)
> gimple_assign_rhs2 (stmt));
> }
>
> -
> +/* Extract loop information from a OpenACC internal function call. */
> +tree
> +oacc_ifn_call_extract (gimple *call) {
> + gcc_assert (gimple_call_internal_p (call, IFN_GOACC_LOOP));
> +
> + enum ifn_goacc_loop_kind code
> + = (enum ifn_goacc_loop_kind) TREE_INT_CST_LOW (gimple_call_arg (call,
> 0));
> +
> + tree expr;
> + switch (code)
> + {
> + case IFN_GOACC_LOOP_STEP:
> + {
> + expr = gimple_call_arg (call, 3);
> + break;
> + }
> + case IFN_GOACC_LOOP_CHUNKS:
> + {
> + expr = gimple_call_arg (call, 4);
> + break;
> + }
> + case IFN_GOACC_LOOP_OFFSET:
> + {
> + expr = gimple_call_arg (call, 6);
> + break;
> + }
> + case IFN_GOACC_LOOP_BOUND:
> + {
> + expr = gimple_call_arg (call, 2);
> + break;
> + }
> + default:
> + gcc_unreachable();
> + }
> +
> + gcc_assert (scev_is_linear_expression (expr));
> + return expr;
> +}
> +
> +/* Interpret a gimple call statement. */
> +tree
> +interpret_gimple_call (class loop *loop, gimple *call)
> +{
> + /* Only IFN_GOACC_LOOP calls are handled here.
> + SCEV computation for those calls is only really relevant
> + for Graphite's execution on OpenACC functions in the host
> + compiler. */
> +
> +#ifndef ACCEL_COMPILER
> + if (!gimple_call_internal_p (call, IFN_GOACC_LOOP))
> + return chrec_dont_know;
> +#else
> + return chrec_dont_know;
> +#endif
> +
> + /* Information about OpenACC loops is encoded in internal function calls.
> + Extract loop information from those calls, but ignore other calls. */
> + if (!gimple_call_internal_p (call, IFN_GOACC_LOOP))
> + return chrec_dont_know;
> +
> + tree expr = oacc_ifn_call_extract (call);
> + tree analyzed = analyze_scalar_evolution (loop, expr);
> + gcc_checking_assert (expr == analyzed);
> +
> + tree lhs = gimple_call_lhs (call);
> + gcc_assert (lhs);
> +
> + return chrec_convert (TREE_TYPE (lhs), analyzed, call);
> +}
>
> /* This section contains all the entry points:
> - number_of_iterations_in_loop,
> @@ -1969,6 +2076,10 @@ analyze_scalar_evolution_1 (class loop *loop, tree var)
> res = interpret_gimple_assign (loop, def);
> break;
>
> + case GIMPLE_CALL:
> + res = interpret_gimple_call (loop, def);
> + break;
> +
> case GIMPLE_PHI:
> if (loop_phi_node_p (def))
> res = interpret_loop_phi (loop, as_a <gphi *> (def));
> @@ -2049,6 +2160,91 @@ analyze_scalar_evolution (class loop *loop, tree var)
> return res;
> }
>
> +/* Check if VAR represents a parameter of an OpenACC region in an
> + offloaded function. That is, check that VAR's defining statement
> + has the shape:
> +
> + VAR2 = *.omp_data_i(D).field
> + VAR = *_VAR2
> + */
> +static bool
> +is_oacc_arg (tree var)
> +{
> + gimple* def = SSA_NAME_DEF_STMT (var);
> +
> + if (!def || !is_gimple_assign (def))
> + return false;
> +
> + tree rhs = gimple_assign_rhs1 (def);
> +
> + if (TREE_CODE (rhs) != MEM_REF)
> + return false;
> +
> + tree ref = TREE_OPERAND (rhs, 0);
> +
> + if (TREE_CODE (ref) != SSA_NAME)
> + return false;
> +
> + gimple* ref_def = SSA_NAME_DEF_STMT (ref);
> +
> + if (!ref_def || !is_gimple_assign (ref_def))
> + return false;
> +
> + rhs = gimple_assign_rhs1 (ref_def);
> + if (TREE_CODE (rhs) != COMPONENT_REF)
> + return false;
> +
> + tree base_ref = TREE_OPERAND (rhs, 0);
> +
> + if (TREE_CODE (base_ref) != MEM_REF)
> + return false;
> +
> + tree base = TREE_OPERAND (base_ref, 0);
> +
> + if (!SSA_NAME_IDENTIFIER (base))
> + return false;
> +
> + char* base_id =
> + const_cast<char*>(IDENTIFIER_POINTER (SSA_NAME_IDENTIFIER (base)));
> +
> + if (strncmp (base_id, ".omp_data_i", 11))
> + return false;
> +
> + return true;
> +}
> +
> +/* Search for SSA_NAMEs which represent parameters of an offloaded
> + OpenACC region and set their SCEV values to a parametric chrec
> + containing the variable itself.
> +
> + We do not have a way to perform scalar evolution on the function
> + from which an OpenACC outlined function was extracted while
> + executing on the outlined function. Analysing those SSA_NAMEs
> + would lead to chrec_dont_know because of the pointer indirection
> + introduced by the outlining. We are better of treating the
> + names as parameters. */
> +
> +/* TODO Come up with a way to determine the scalar evolution
> + in the original function */
> +
> +void
> +oacc_set_arg_evolutions () {
> + unsigned i;
> + tree var;
> +
> + FOR_EACH_SSA_NAME (i, var, cfun)
> + {
> + if (! is_oacc_arg (var))
> + continue;
> +
> + basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (var));
> +
> + tree *chrec = find_var_scev_info (bb, var);
> + *chrec = var;
> + }
> +
> +}
> +
> /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
>
> static tree
> @@ -2261,6 +2457,15 @@ instantiate_scev_name (edge instantiate_below,
> class loop *def_loop;
> basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
>
> + /* Do not instantiate names which dereference ".omp_data_i" field.
> + Cf. oacc_set_arg_evolutions. */
> + if (is_oacc_arg (chrec))
> + return chrec;
> +
> + if (is_oacc_loop_ifn_call_def (chrec))
> + return interpret_gimple_call (evolution_loop, SSA_NAME_DEF_STMT (chrec));
> +
> +
> /* A parameter, nothing to do. */
> if (!def_bb
> || !dominated_by_p (CDI_DOMINATORS, def_bb, instantiate_below->dest))
> @@ -3221,10 +3426,14 @@ simple_iv_with_niters (class loop *wrto_loop, class
> loop *use_loop,
> || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
> return false;
>
> + tree ev_type = TREE_TYPE (ev);
> + if (is_oacc_loop_ifn_call_def (ev))
> + type = integer_type_node;
> +
> if (tree_does_not_contain_chrecs (ev))
> {
> iv->base = ev;
> - iv->step = build_int_cst (TREE_TYPE (ev), 0);
> + iv->step = build_int_cst (ev_type, 0);
> iv->no_overflow = true;
> return true;
> }
> @@ -3240,6 +3449,9 @@ simple_iv_with_niters (class loop *wrto_loop, class
> loop *use_loop,
> return false;
>
> iv->step = CHREC_RIGHT (ev);
> + if (is_oacc_loop_ifn_call_def (iv->step))
> + iv->step = interpret_gimple_call (use_loop, SSA_NAME_DEF_STMT
> (iv->step));
> +
> if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
> || tree_contains_chrecs (iv->step, NULL))
> return false;
> @@ -3385,6 +3597,9 @@ expression_expensive_p (tree expr, hash_map<tree,
> uint64_t> &cache,
> return true;
> }
>
> + if (is_oacc_ifn_call_def (expr))
> + return false;
> +
> bool visited_p;
> uint64_t &local_cost = cache.get_or_insert (expr, &visited_p);
> if (visited_p)
> diff --git a/gcc/tree-ssa-loop-ivcanon.c b/gcc/tree-ssa-loop-ivcanon.c
> index 6c1268e84ad..0f3d7ce3e76 100644
> --- a/gcc/tree-ssa-loop-ivcanon.c
> +++ b/gcc/tree-ssa-loop-ivcanon.c
> @@ -64,6 +64,7 @@ along with GCC; see the file COPYING3. If not see
> #include "builtins.h"
> #include "tree-ssa-sccvn.h"
> #include "dbgcnt.h"
> +#include "omp-general.h"
>
> /* Specifies types of loops that may be unrolled. */
>
> @@ -1256,7 +1257,13 @@ canonicalize_loop_induction_variables (class loop
> *loop,
> populates the loop bounds. */
> modified |= remove_redundant_iv_tests (loop);
>
> - if (try_unroll_loop_completely (loop, exit, niter, may_be_zero, ul,
> + /* Skip unrolling on OpenACC outlined functions. Those functions
> + contain loops (e.g. the top loop for a region) that never iterate
> + and that should not be removed. */
> +
> + bool skip_unrolling = oacc_get_fn_attrib (cfun->decl);
> + if (!skip_unrolling &&
> + try_unroll_loop_completely (loop, exit, niter, may_be_zero, ul,
> maxiter, locus, allow_peel))
> return true;
>
> diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
> index 7d61ef080eb..c54a0277670 100644
> --- a/gcc/tree-ssa-loop-niter.c
> +++ b/gcc/tree-ssa-loop-niter.c
> @@ -40,6 +40,7 @@ along with GCC; see the file COPYING3. If not see
> #include "tree-ssa-loop.h"
> #include "cfgloop.h"
> #include "tree-chrec.h"
> +#include "tree-chrec-oacc.h"
> #include "tree-scalar-evolution.h"
> #include "tree-dfa.h"
>
> @@ -1980,6 +1981,9 @@ simplify_replace_tree (tree expr, tree old, tree
> new_tree,
> return (ret ? (do_fold ? fold (ret) : ret) : expr);
> }
>
> +tree oacc_ifn_call_extract (gimple*);
> +tree interpret_gimple_call (class loop *loop, gimple *call);
> +
> /* Expand definitions of ssa names in EXPR as long as they are simple
> enough, and return the new expression. If STOP is specified, stop
> expanding if EXPR equals to it. */
> @@ -1995,6 +1999,12 @@ expand_simple_operations (tree expr, tree stop,
> hash_map<tree, tree> &cache)
> if (expr == NULL_TREE)
> return expr;
>
> + if (is_oacc_ifn_call_def (expr))
> + {
> + //expr = oacc_ifn_call_extract (SSA_NAME_DEF_STMT (expr));
> + expr = interpret_gimple_call (NULL, SSA_NAME_DEF_STMT (expr));
> + }
> +
> if (is_gimple_min_invariant (expr))
> return expr;
>
> @@ -2465,6 +2475,9 @@ number_of_iterations_exit_assumptions (class loop
> *loop, edge exit,
> if (iv0_niters && iv1_niters)
> return false;
>
> + type = TREE_TYPE (iv0.step);
> +
> +
> /* We don't want to see undefined signed overflow warnings while
> computing the number of iterations. */
> fold_defer_overflow_warnings ();
> --
> 2.17.1
>
> -----------------
> Mentor Graphics (Deutschland) GmbH, Arnulfstraße 201, 80634 München / Germany
> Registergericht München HRB 106955, Geschäftsführer: Thomas Heurung,
> Alexander Walter
