[GSoC] How to get started with the isl code generation

[Tobias Grosser]

On 01/06/2014 01:21, Roman Gareev wrote:
> Hi Tobias,
>
>> Allright. It seems you understood the tree traversel. For the actual
>> patch that we want to commit, let's leave it out for now.  Instead,
>> let's try to get a minimal patch that only adds the flag and the new
>> file for the isl_ast stuff. In case the isl is choosen as code
>> generation option, the cloog pass is disabled (they would otherwise get
>> into their way later) and we dump the ast. We also need a simple test case
>> that checks that the dump is generated.
>
> What do you mean by simple test case that checks that the dump is
> generated? Is it checking of the dump_flags?

I mean that we verify that the dump that is created contains a printed
AST that matches the one we expect.

for (int c1 = 0; c1 < n - 1; c1 += 1)
   for (int c3 = 0; c3 < n; c3 += 1)
     S_5(c1, c3);

>> Instead of adding this functionality to gloog() I would create a
>> semilar function that provides the functionality gloog has for the isl
>> codegen counterpart. -fgraphite-code-generator switches then between
>> these two functions. To start with the isl counterpart is almost empty.
>> It just contains the parts of this patch needed for printing. When we
>> add more functionality and we encounter reuse opportunities, we can move
>> parts of graphite-clast-to-gimple.c into a generic codegen file.
>>
>> What do you think?
>
> I think that it's good. It would help to begin removing of CLooG
> dependency and make the file with generation of ISL AST easier to
> maintain. I implemented it in the patch, which can be found below. You
> can also find my post about my second task of the proposal at the
> following link http://romangareev.blogspot.com/2014/05/gsoc-report-ii.html

Nice post.

> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
> index e74bb67..39cb7bd 100644
> --- a/gcc/Makefile.in
> +++ b/gcc/Makefile.in
> @@ -1250,6 +1250,7 @@ OBJS = \
>  	graphite.o \
>  	graphite-blocking.o \
>  	graphite-clast-to-gimple.o \
> +	graphite-isl-ast-to-gimple.o \
>  	graphite-dependences.o \
>  	graphite-interchange.o \
>  	graphite-optimize-isl.o \
> diff --git a/gcc/common.opt b/gcc/common.opt
> index 5c3f834..731aaf5 100644
> --- a/gcc/common.opt
> +++ b/gcc/common.opt
> @@ -1250,6 +1250,19 @@ fgraphite-identity
>  Common Report Var(flag_graphite_identity) Optimization
>  Enable Graphite Identity transformation
>
> +fgraphite-code-generator=
> +Common Report RejectNegative Joined Optimization Enum(fgraphite_generator) Var(flag_graphite_code_gen) Init(FGRAPHITE_CODE_GEN_CLOOG)
> +Choose code generator of Graphite
> +
> +Enum
> +Name(fgraphite_generator) Type(enum fgraphite_generator) UnknownError(unknown code generator of graphite %qs)
> +
> +EnumValue
> +Enum(fgraphite_generator) String(isl) Value(FGRAPHITE_CODE_GEN_ISL)
> +
> +EnumValue
> +Enum(fgraphite_generator) String(cloog) Value(FGRAPHITE_CODE_GEN_CLOOG)

Nice.

> +#include "config.h"
> +
> +#include <isl/set.h>
> +#include <isl/map.h>
> +#include <isl/union_map.h>
> +#include <isl/list.h>
> +#include <isl/constraint.h>
> +#include <isl/ilp.h>
> +#include <isl/aff.h>
> +#include <isl/ast_build.h>
> +
> +#include "system.h"
> +#include "coretypes.h"
> +#include "diagnostic-core.h"
> +#include "tree.h"
> +#include "basic-block.h"
> +#include "tree-ssa-alias.h"
> +#include "internal-fn.h"
> +#include "gimple-expr.h"
> +#include "is-a.h"
> +#include "gimple.h"
> +#include "gimple-iterator.h"
> +#include "gimplify-me.h"
> +#include "gimple-ssa.h"
> +#include "tree-ssa-loop-manip.h"
> +#include "tree-ssa-loop.h"
> +#include "tree-into-ssa.h"
> +#include "tree-pass.h"
> +#include "cfgloop.h"
> +#include "tree-chrec.h"
> +#include "tree-data-ref.h"
> +#include "tree-scalar-evolution.h"
> +#include "sese.h"
> +
> +#include "graphite-poly.h"
> +#include "graphite-isl-ast-to-gimple.h"
> +#include "graphite-htab.h"

Are these the minimal includes necessary?

> +
> +/* This flag is set when an error occurred during the translation of
> +   ISL AST to Gimple.  */
> +
> +static bool isl_gloog_error;
> +
> +/* Prints NODE to FILE.  */
> +
> +void
> +print_isl_ast_node (FILE *file, __isl_keep isl_ast_node *node,
> +		    __isl_keep isl_ctx *ctx)
> +{
> +  isl_printer *prn = isl_printer_to_file (ctx, file);
> +  prn = isl_printer_set_output_format (prn, ISL_FORMAT_C);
> +  prn = isl_printer_print_ast_node (prn, node);
> +  prn = isl_printer_print_str (prn, "\n");
> +  isl_printer_free (prn);
> +}
> +
> +/* Generates a build, which specifies the constraints on the parameters. */
> +
> +static isl_ast_build *
> +generate_isl_context (scop_p scop)
> +{
> +  isl_set * context_isl = isl_set_params (isl_set_copy (scop->context));
> +  return isl_ast_build_from_context (context_isl);
> +}
> +
> +/* Generates a schedule, which specifies an order used to
> +   visit elements in a domain. */
> +
> +static isl_union_map *
> +generate_isl_schedule (scop_p scop)
> +{
> +  int i;
> +  poly_bb_p pbb;
> +  isl_union_map *schedule_isl =
> +    isl_union_map_empty (isl_set_get_space (scop->context));
> +
> +  FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
> +    {
> +      /* Dead code elimination: when the domain of a PBB is empty,
> +	 don't generate code for the PBB.  */
> +      if (isl_set_is_empty (pbb->domain))
> +	continue;
> +
> +      isl_map *bb_schedule = isl_map_copy (pbb->transformed);
> +      bb_schedule = isl_map_intersect_domain (bb_schedule,
> +					      isl_set_copy (pbb->domain));
> +      schedule_isl =
> +        isl_union_map_union (schedule_isl,
> +			     isl_union_map_from_map (bb_schedule));
> +    }
> +  return schedule_isl;
> +}
> +
> +static isl_ast_node *
> +scop_to_isl_ast (scop_p scop)
> +{
> +  isl_union_map *schedule_isl = generate_isl_schedule (scop);
> +  isl_ast_build *context_isl = generate_isl_context (scop);
> +  isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
> +							   schedule_isl);
> +  isl_ast_build_free (context_isl);
> +  return ast_isl;
> +}
> +
> +
> +/* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
> +   the given SCOP.  Return true if code generation succeeded.
> +   BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.

You do not yet pass a BB_PBB_MAPPING. Please remove it from the comment.

> +*/
> +
> +bool
> +gloog_isl (scop_p scop)
> +{
> +  timevar_push (TV_GRAPHITE_CODE_GEN);
> +  isl_gloog_error = false;
> +  isl_ast_node *root_node = scop_to_isl_ast (scop);
> +  if (dump_file && (dump_flags & TDF_DETAILS))
> +    {
> +      fprintf (dump_file, "\nISL AST generated by ISL: \n");
> +      print_isl_ast_node (dump_file, root_node, scop->ctx);
> +    }
> +  isl_ast_node_free (root_node);
> +  timevar_pop (TV_GRAPHITE_CODE_GEN);
> +  return !isl_gloog_error;
> +}
> diff --git a/gcc/graphite-isl-ast-to-gimple.h b/gcc/graphite-isl-ast-to-gimple.h
> new file mode 100644
> index 0000000..c7d924e
> --- /dev/null
> +++ b/gcc/graphite-isl-ast-to-gimple.h
> @@ -0,0 +1,24 @@
> +/* Translation of ISL AST to Gimple.
> +   Copyright (C) 2014 Free Software Foundation, Inc.
> +   Contributed by Roman Gareev <gareevroman@gmail.com>.
> +
> +This file is part of GCC.
> +
> +GCC is free software; you can redistribute it and/or modify
> +it under the terms of the GNU General Public License as published by
> +the Free Software Foundation; either version 3, or (at your option)
> +any later version.
> +
> +GCC is distributed in the hope that it will be useful,
> +but WITHOUT ANY WARRANTY; without even the implied warranty of
> +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> +GNU General Public License for more details.
> +
> +You should have received a copy of the GNU General Public License
> +along with GCC; see the file COPYING3.  If not see
> +<http://www.gnu.org/licenses/>.  */
> +
> +#ifndef GCC_GRAPHITE_ISL_AST_TO_GIMPLE_H
> +#define GCC_GRAPHITE_ISL_AST_TO_GIMPLE_H

This file is empty. It seems to be the perfect place for gloog_isl,
maybe give it a more descriptive name. E.g.,

graphite_regenerate_ast_isl()

We could then rename gloog, to graphite_regenerate_ast_cloog().

gloog comes from graphite + cloog and does not make sense in the context
of isl.

> +#endif
> diff --git a/gcc/graphite.c b/gcc/graphite.c
> index 2e1f439..c384ca7 100644
> --- a/gcc/graphite.c
> +++ b/gcc/graphite.c
> @@ -73,6 +73,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "graphite-poly.h"
>  #include "graphite-scop-detection.h"
>  #include "graphite-clast-to-gimple.h"
> +#include "graphite-isl-ast-to-gimple.h"
>  #include "graphite-sese-to-poly.h"
>  #include "graphite-htab.h"
>
> @@ -301,7 +302,10 @@ graphite_transform_loops (void)
>
>  	if (POLY_SCOP_P (scop)
>  	    && apply_poly_transforms (scop)
> -	    && gloog (scop, bb_pbb_mapping))
> +	    && (((flag_graphite_code_gen == FGRAPHITE_CODE_GEN_ISL)
> +	    && gloog_isl (scop))
> +	    || ((flag_graphite_code_gen == FGRAPHITE_CODE_GEN_CLOOG)
> +	    && gloog (scop, bb_pbb_mapping))))
>  	  need_cfg_cleanup_p = true;

Good.

Overall, this patch is wonderful. Small, self-contained, clean,
easy-to-review. A perfect patch.

Please address the comments mentioned above, add the test case and
repost for review. We should get this committed soon.

Tobias