Subversion Repositories openrisc

/* Detection of Static Control Parts (SCoP) for Graphite.

/* Detection of Static Control Parts (SCoP) for Graphite.

   Copyright (C) 2009, 2010 Free Software Foundation, Inc.

   Copyright (C) 2009, 2010 Free Software Foundation, Inc.

   Contributed by Sebastian Pop <sebastian.pop@amd.com> and

   Contributed by Sebastian Pop <sebastian.pop@amd.com> and

   Tobias Grosser <grosser@fim.uni-passau.de>.

   Tobias Grosser <grosser@fim.uni-passau.de>.

This file is part of GCC.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify

GCC is free software; you can redistribute it and/or modify

it under the terms of the GNU General Public License as published by

it under the terms of the GNU General Public License as published by

the Free Software Foundation; either version 3, or (at your option)

the Free Software Foundation; either version 3, or (at your option)

any later version.

any later version.

GCC is distributed in the hope that it will be useful,

GCC is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

GNU General Public License for more details.

GNU General Public License for more details.

You should have received a copy of the GNU General Public License

You should have received a copy of the GNU General Public License

along with GCC; see the file COPYING3.  If not see

along with GCC; see the file COPYING3.  If not see

<http://www.gnu.org/licenses/>.  */

<http://www.gnu.org/licenses/>.  */

#include "config.h"

#include "config.h"

#include "system.h"

#include "system.h"

#include "coretypes.h"

#include "coretypes.h"

#include "tm.h"

#include "tm.h"

#include "ggc.h"

#include "ggc.h"

#include "tree.h"

#include "tree.h"

#include "rtl.h"

#include "rtl.h"

#include "basic-block.h"

#include "basic-block.h"

#include "diagnostic.h"

#include "diagnostic.h"

#include "tree-flow.h"

#include "tree-flow.h"

#include "toplev.h"

#include "toplev.h"

#include "tree-dump.h"

#include "tree-dump.h"

#include "timevar.h"

#include "timevar.h"

#include "cfgloop.h"

#include "cfgloop.h"

#include "tree-chrec.h"

#include "tree-chrec.h"

#include "tree-data-ref.h"

#include "tree-data-ref.h"

#include "tree-scalar-evolution.h"

#include "tree-scalar-evolution.h"

#include "tree-pass.h"

#include "tree-pass.h"

#include "domwalk.h"

#include "domwalk.h"

#include "value-prof.h"

#include "value-prof.h"

#include "pointer-set.h"

#include "pointer-set.h"

#include "gimple.h"

#include "gimple.h"

#include "sese.h"

#include "sese.h"

#ifdef HAVE_cloog

#ifdef HAVE_cloog

#include "cloog/cloog.h"

#include "cloog/cloog.h"

#include "ppl_c.h"

#include "ppl_c.h"

#include "graphite-ppl.h"

#include "graphite-ppl.h"

#include "graphite.h"

#include "graphite.h"

#include "graphite-poly.h"

#include "graphite-poly.h"

#include "graphite-scop-detection.h"

#include "graphite-scop-detection.h"

/* The type of the analyzed basic block.  */

/* The type of the analyzed basic block.  */

typedef enum gbb_type {

typedef enum gbb_type {

  GBB_UNKNOWN,

  GBB_UNKNOWN,

  GBB_LOOP_SING_EXIT_HEADER,

  GBB_LOOP_SING_EXIT_HEADER,

  GBB_LOOP_MULT_EXIT_HEADER,

  GBB_LOOP_MULT_EXIT_HEADER,

  GBB_LOOP_EXIT,

  GBB_LOOP_EXIT,

  GBB_COND_HEADER,

  GBB_COND_HEADER,

  GBB_SIMPLE,

  GBB_SIMPLE,

  GBB_LAST

  GBB_LAST

} gbb_type;

} gbb_type;

/* Detect the type of BB.  Loop headers are only marked, if they are

/* Detect the type of BB.  Loop headers are only marked, if they are

   new.  This means their loop_father is different to LAST_LOOP.

   new.  This means their loop_father is different to LAST_LOOP.

   Otherwise they are treated like any other bb and their type can be

   Otherwise they are treated like any other bb and their type can be

   any other type.  */

   any other type.  */

static gbb_type

static gbb_type

get_bb_type (basic_block bb, struct loop *last_loop)

get_bb_type (basic_block bb, struct loop *last_loop)

{

{

  VEC (basic_block, heap) *dom;

  VEC (basic_block, heap) *dom;

  int nb_dom, nb_suc;

  int nb_dom, nb_suc;

  struct loop *loop = bb->loop_father;

  struct loop *loop = bb->loop_father;

  /* Check, if we entry into a new loop. */

  /* Check, if we entry into a new loop. */

  if (loop != last_loop)

  if (loop != last_loop)

    {

    {

      if (single_exit (loop) != NULL)

      if (single_exit (loop) != NULL)

        return GBB_LOOP_SING_EXIT_HEADER;

        return GBB_LOOP_SING_EXIT_HEADER;

      else if (loop->num != 0)

      else if (loop->num != 0)

        return GBB_LOOP_MULT_EXIT_HEADER;

        return GBB_LOOP_MULT_EXIT_HEADER;

      else

      else

        return GBB_COND_HEADER;

        return GBB_COND_HEADER;

    }

    }

  dom = get_dominated_by (CDI_DOMINATORS, bb);

  dom = get_dominated_by (CDI_DOMINATORS, bb);

  nb_dom = VEC_length (basic_block, dom);

  nb_dom = VEC_length (basic_block, dom);

  VEC_free (basic_block, heap, dom);

  VEC_free (basic_block, heap, dom);

  if (nb_dom == 0)

  if (nb_dom == 0)

    return GBB_LAST;

    return GBB_LAST;

  nb_suc = VEC_length (edge, bb->succs);

  nb_suc = VEC_length (edge, bb->succs);

  if (nb_dom == 1 && nb_suc == 1)

  if (nb_dom == 1 && nb_suc == 1)

    return GBB_SIMPLE;

    return GBB_SIMPLE;

  return GBB_COND_HEADER;

  return GBB_COND_HEADER;

}

}

/* A SCoP detection region, defined using bbs as borders.

/* A SCoP detection region, defined using bbs as borders.

   All control flow touching this region, comes in passing basic_block

   All control flow touching this region, comes in passing basic_block

   ENTRY and leaves passing basic_block EXIT.  By using bbs instead of

   ENTRY and leaves passing basic_block EXIT.  By using bbs instead of

   edges for the borders we are able to represent also regions that do

   edges for the borders we are able to represent also regions that do

   not have a single entry or exit edge.

   not have a single entry or exit edge.

   But as they have a single entry basic_block and a single exit

   But as they have a single entry basic_block and a single exit

   basic_block, we are able to generate for every sd_region a single

   basic_block, we are able to generate for every sd_region a single

   entry and exit edge.

   entry and exit edge.

   1   2

   1   2

    \ /

    \ /

     3  <- entry

     3  <- entry

     |

     |

     4

     4

    / \                 This region contains: {3, 4, 5, 6, 7, 8}

    / \                 This region contains: {3, 4, 5, 6, 7, 8}

   5   6

   5   6

   |   |

   |   |

   7   8

   7   8

    \ /

    \ /

     9  <- exit  */

     9  <- exit  */

typedef struct sd_region_p

typedef struct sd_region_p

{

{

  /* The entry bb dominates all bbs in the sd_region.  It is part of

  /* The entry bb dominates all bbs in the sd_region.  It is part of

     the region.  */

     the region.  */

  basic_block entry;

  basic_block entry;

  /* The exit bb postdominates all bbs in the sd_region, but is not

  /* The exit bb postdominates all bbs in the sd_region, but is not

     part of the region.  */

     part of the region.  */

  basic_block exit;

  basic_block exit;

} sd_region;

} sd_region;

DEF_VEC_O(sd_region);

DEF_VEC_O(sd_region);

DEF_VEC_ALLOC_O(sd_region, heap);

DEF_VEC_ALLOC_O(sd_region, heap);

/* Moves the scops from SOURCE to TARGET and clean up SOURCE.  */

/* Moves the scops from SOURCE to TARGET and clean up SOURCE.  */

static void

static void

move_sd_regions (VEC (sd_region, heap) **source,

move_sd_regions (VEC (sd_region, heap) **source,

                 VEC (sd_region, heap) **target)

                 VEC (sd_region, heap) **target)

{

{

  sd_region *s;

  sd_region *s;

  int i;

  int i;

  for (i = 0; VEC_iterate (sd_region, *source, i, s); i++)

  for (i = 0; VEC_iterate (sd_region, *source, i, s); i++)

    VEC_safe_push (sd_region, heap, *target, s);

    VEC_safe_push (sd_region, heap, *target, s);

  VEC_free (sd_region, heap, *source);

  VEC_free (sd_region, heap, *source);

}

}

/* Something like "n * m" is not allowed.  */

/* Something like "n * m" is not allowed.  */

static bool

static bool

graphite_can_represent_init (tree e)

graphite_can_represent_init (tree e)

{

{

  switch (TREE_CODE (e))

  switch (TREE_CODE (e))

    {

    {

    case POLYNOMIAL_CHREC:

    case POLYNOMIAL_CHREC:

      return graphite_can_represent_init (CHREC_LEFT (e))

      return graphite_can_represent_init (CHREC_LEFT (e))

        && graphite_can_represent_init (CHREC_RIGHT (e));

        && graphite_can_represent_init (CHREC_RIGHT (e));

    case MULT_EXPR:

    case MULT_EXPR:

      if (chrec_contains_symbols (TREE_OPERAND (e, 0)))

      if (chrec_contains_symbols (TREE_OPERAND (e, 0)))

        return graphite_can_represent_init (TREE_OPERAND (e, 0))

        return graphite_can_represent_init (TREE_OPERAND (e, 0))

          && host_integerp (TREE_OPERAND (e, 1), 0);

          && host_integerp (TREE_OPERAND (e, 1), 0);

      else

      else

        return graphite_can_represent_init (TREE_OPERAND (e, 1))

        return graphite_can_represent_init (TREE_OPERAND (e, 1))

          && host_integerp (TREE_OPERAND (e, 0), 0);

          && host_integerp (TREE_OPERAND (e, 0), 0);

    case PLUS_EXPR:

    case PLUS_EXPR:

    case POINTER_PLUS_EXPR:

    case POINTER_PLUS_EXPR:

    case MINUS_EXPR:

    case MINUS_EXPR:

      return graphite_can_represent_init (TREE_OPERAND (e, 0))

      return graphite_can_represent_init (TREE_OPERAND (e, 0))

        && graphite_can_represent_init (TREE_OPERAND (e, 1));

        && graphite_can_represent_init (TREE_OPERAND (e, 1));

    case NEGATE_EXPR:

    case NEGATE_EXPR:

    case BIT_NOT_EXPR:

    case BIT_NOT_EXPR:

    CASE_CONVERT:

    CASE_CONVERT:

    case NON_LVALUE_EXPR:

    case NON_LVALUE_EXPR:

      return graphite_can_represent_init (TREE_OPERAND (e, 0));

      return graphite_can_represent_init (TREE_OPERAND (e, 0));

   default:

   default:

     break;

     break;

    }

    }

  return true;

  return true;

}

}

/* Return true when SCEV can be represented in the polyhedral model.

/* Return true when SCEV can be represented in the polyhedral model.

   An expression can be represented, if it can be expressed as an

   An expression can be represented, if it can be expressed as an

   affine expression.  For loops (i, j) and parameters (m, n) all

   affine expression.  For loops (i, j) and parameters (m, n) all

   affine expressions are of the form:

   affine expressions are of the form:

   x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z

   x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z

   1 i + 20 j + (-2) m + 25

   1 i + 20 j + (-2) m + 25

   Something like "i * n" or "n * m" is not allowed.

   Something like "i * n" or "n * m" is not allowed.

   OUTERMOST_LOOP defines the outermost loop that can variate.  */

   OUTERMOST_LOOP defines the outermost loop that can variate.  */

static bool

static bool

graphite_can_represent_scev (tree scev, int outermost_loop)

graphite_can_represent_scev (tree scev, int outermost_loop)

{

{

  if (chrec_contains_undetermined (scev))

  if (chrec_contains_undetermined (scev))

    return false;

    return false;

  switch (TREE_CODE (scev))

  switch (TREE_CODE (scev))

    {

    {

    case PLUS_EXPR:

    case PLUS_EXPR:

    case MINUS_EXPR:

    case MINUS_EXPR:

      return graphite_can_represent_scev (TREE_OPERAND (scev, 0), outermost_loop)

      return graphite_can_represent_scev (TREE_OPERAND (scev, 0), outermost_loop)

        && graphite_can_represent_scev (TREE_OPERAND (scev, 1), outermost_loop);

        && graphite_can_represent_scev (TREE_OPERAND (scev, 1), outermost_loop);

    case MULT_EXPR:

    case MULT_EXPR:

      return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))

      return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))

        && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))

        && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))

        && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))

        && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))

             && chrec_contains_symbols (TREE_OPERAND (scev, 1)))

             && chrec_contains_symbols (TREE_OPERAND (scev, 1)))

        && graphite_can_represent_init (scev)

        && graphite_can_represent_init (scev)

        && graphite_can_represent_scev (TREE_OPERAND (scev, 0), outermost_loop)

        && graphite_can_represent_scev (TREE_OPERAND (scev, 0), outermost_loop)

        && graphite_can_represent_scev (TREE_OPERAND (scev, 1), outermost_loop);

        && graphite_can_represent_scev (TREE_OPERAND (scev, 1), outermost_loop);

    case POLYNOMIAL_CHREC:

    case POLYNOMIAL_CHREC:

      /* Check for constant strides.  With a non constant stride of

      /* Check for constant strides.  With a non constant stride of

         'n' we would have a value of 'iv * n'.  Also check that the

         'n' we would have a value of 'iv * n'.  Also check that the

         initial value can represented: for example 'n * m' cannot be

         initial value can represented: for example 'n * m' cannot be

         represented.  */

         represented.  */

      if (!evolution_function_right_is_integer_cst (scev)

      if (!evolution_function_right_is_integer_cst (scev)

          || !graphite_can_represent_init (scev))

          || !graphite_can_represent_init (scev))

        return false;

        return false;

    default:

    default:

      break;

      break;

    }

    }

  /* Only affine functions can be represented.  */

  /* Only affine functions can be represented.  */

  if (!scev_is_linear_expression (scev))

  if (!scev_is_linear_expression (scev))

    return false;

    return false;

  return evolution_function_is_invariant_p (scev, outermost_loop)

  return evolution_function_is_invariant_p (scev, outermost_loop)

    || evolution_function_is_affine_multivariate_p (scev, outermost_loop);

    || evolution_function_is_affine_multivariate_p (scev, outermost_loop);

}

}

/* Return true when EXPR can be represented in the polyhedral model.

/* Return true when EXPR can be represented in the polyhedral model.

   This means an expression can be represented, if it is linear with

   This means an expression can be represented, if it is linear with

   respect to the loops and the strides are non parametric.

   respect to the loops and the strides are non parametric.

   LOOP is the place where the expr will be evaluated and OUTERMOST_LOOP

   LOOP is the place where the expr will be evaluated and OUTERMOST_LOOP

   defindes the outermost loop that can variate.  SCOP_ENTRY defines the

   defindes the outermost loop that can variate.  SCOP_ENTRY defines the

   entry of the region we analyse.  */

   entry of the region we analyse.  */

static bool

static bool

graphite_can_represent_expr (basic_block scop_entry, loop_p loop,

graphite_can_represent_expr (basic_block scop_entry, loop_p loop,

                             loop_p outermost_loop, tree expr)

                             loop_p outermost_loop, tree expr)

{

{

  tree scev = analyze_scalar_evolution (loop, expr);

  tree scev = analyze_scalar_evolution (loop, expr);

  scev = instantiate_scev (scop_entry, loop, scev);

  scev = instantiate_scev (scop_entry, loop, scev);

  return graphite_can_represent_scev (scev, outermost_loop->num);

  return graphite_can_represent_scev (scev, outermost_loop->num);

}

}

/* Return true if the data references of STMT can be represented by

/* Return true if the data references of STMT can be represented by

   Graphite.  */

   Graphite.  */

static bool

static bool

stmt_has_simple_data_refs_p (loop_p outermost_loop, gimple stmt)

stmt_has_simple_data_refs_p (loop_p outermost_loop, gimple stmt)

{

{

  data_reference_p dr;

  data_reference_p dr;

  unsigned i;

  unsigned i;

  int j;

  int j;

  bool res = true;

  bool res = true;

  int loop = outermost_loop->num;

  int loop = outermost_loop->num;

  VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);

  VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);

  graphite_find_data_references_in_stmt (outermost_loop, stmt, &drs);

  graphite_find_data_references_in_stmt (outermost_loop, stmt, &drs);

  for (j = 0; VEC_iterate (data_reference_p, drs, j, dr); j++)

  for (j = 0; VEC_iterate (data_reference_p, drs, j, dr); j++)

    for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)

    for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)

      if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i), loop))

      if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i), loop))

        {

        {

          res = false;

          res = false;

          goto done;

          goto done;

        }

        }

 done:

 done:

  free_data_refs (drs);

  free_data_refs (drs);

  return res;

  return res;

}

}

/* Return true only when STMT is simple enough for being handled by

/* Return true only when STMT is simple enough for being handled by

   Graphite.  This depends on SCOP_ENTRY, as the parameters are

   Graphite.  This depends on SCOP_ENTRY, as the parameters are

   initialized relatively to this basic block, the linear functions

   initialized relatively to this basic block, the linear functions

   are initialized to OUTERMOST_LOOP and BB is the place where we try

   are initialized to OUTERMOST_LOOP and BB is the place where we try

   to evaluate the STMT.  */

   to evaluate the STMT.  */

static bool

static bool

stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop,

stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop,

                        gimple stmt, basic_block bb)

                        gimple stmt, basic_block bb)

{

{

  loop_p loop = bb->loop_father;

  loop_p loop = bb->loop_father;

  gcc_assert (scop_entry);

  gcc_assert (scop_entry);

  /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.

  /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.

     Calls have side-effects, except those to const or pure

     Calls have side-effects, except those to const or pure

     functions.  */

     functions.  */

  if (gimple_has_volatile_ops (stmt)

  if (gimple_has_volatile_ops (stmt)

      || (gimple_code (stmt) == GIMPLE_CALL

      || (gimple_code (stmt) == GIMPLE_CALL

          && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))

          && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))

      || (gimple_code (stmt) == GIMPLE_ASM))

      || (gimple_code (stmt) == GIMPLE_ASM))

    return false;

    return false;

  if (is_gimple_debug (stmt))

  if (is_gimple_debug (stmt))

    return true;

    return true;

  if (!stmt_has_simple_data_refs_p (outermost_loop, stmt))

  if (!stmt_has_simple_data_refs_p (outermost_loop, stmt))

    return false;

    return false;

  switch (gimple_code (stmt))

  switch (gimple_code (stmt))

    {

    {

    case GIMPLE_RETURN:

    case GIMPLE_RETURN:

    case GIMPLE_LABEL:

    case GIMPLE_LABEL:

      return true;

      return true;

    case GIMPLE_COND:

    case GIMPLE_COND:

      {

      {

        tree op;

        tree op;

        ssa_op_iter op_iter;

        ssa_op_iter op_iter;

        enum tree_code code = gimple_cond_code (stmt);

        enum tree_code code = gimple_cond_code (stmt);

        /* We can handle all binary comparisons.  Inequalities are

        /* We can handle all binary comparisons.  Inequalities are

           also supported as they can be represented with union of

           also supported as they can be represented with union of

           polyhedra.  */

           polyhedra.  */

        if (!(code == LT_EXPR

        if (!(code == LT_EXPR

              || code == GT_EXPR

              || code == GT_EXPR

              || code == LE_EXPR

              || code == LE_EXPR

              || code == GE_EXPR

              || code == GE_EXPR

              || code == EQ_EXPR

              || code == EQ_EXPR

              || code == NE_EXPR))

              || code == NE_EXPR))

          return false;

          return false;

        FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)

        FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)

          if (!graphite_can_represent_expr (scop_entry, loop, outermost_loop,

          if (!graphite_can_represent_expr (scop_entry, loop, outermost_loop,

                                            op)

                                            op)

              /* We can not handle REAL_TYPE. Failed for pr39260.  */

              /* We can not handle REAL_TYPE. Failed for pr39260.  */

              || TREE_CODE (TREE_TYPE (op)) == REAL_TYPE)

              || TREE_CODE (TREE_TYPE (op)) == REAL_TYPE)

            return false;

            return false;

        return true;

        return true;

      }

      }

    case GIMPLE_ASSIGN:

    case GIMPLE_ASSIGN:

    case GIMPLE_CALL:

    case GIMPLE_CALL:

      return true;

      return true;

    default:

    default:

      /* These nodes cut a new scope.  */

      /* These nodes cut a new scope.  */

      return false;

      return false;

    }

    }

  return false;

  return false;

}

}

/* Returns the statement of BB that contains a harmful operation: that

/* Returns the statement of BB that contains a harmful operation: that

   can be a function call with side effects, the induction variables

   can be a function call with side effects, the induction variables

   are not linear with respect to SCOP_ENTRY, etc.  The current open

   are not linear with respect to SCOP_ENTRY, etc.  The current open

   scop should end before this statement.  The evaluation is limited using

   scop should end before this statement.  The evaluation is limited using

   OUTERMOST_LOOP as outermost loop that may change.  */

   OUTERMOST_LOOP as outermost loop that may change.  */

static gimple

static gimple

harmful_stmt_in_bb (basic_block scop_entry, loop_p outer_loop, basic_block bb)

harmful_stmt_in_bb (basic_block scop_entry, loop_p outer_loop, basic_block bb)

{

{

  gimple_stmt_iterator gsi;

  gimple_stmt_iterator gsi;

  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))

  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))

    if (!stmt_simple_for_scop_p (scop_entry, outer_loop, gsi_stmt (gsi), bb))

    if (!stmt_simple_for_scop_p (scop_entry, outer_loop, gsi_stmt (gsi), bb))

      return gsi_stmt (gsi);

      return gsi_stmt (gsi);

  return NULL;

  return NULL;

}

}

/* Return true when it is not possible to represent LOOP in the

/* Return true when it is not possible to represent LOOP in the

   polyhedral representation.  This is evaluated taking SCOP_ENTRY and

   polyhedral representation.  This is evaluated taking SCOP_ENTRY and

   OUTERMOST_LOOP in mind.  */

   OUTERMOST_LOOP in mind.  */

static bool

static bool

graphite_can_represent_loop (basic_block scop_entry, loop_p outermost_loop,

graphite_can_represent_loop (basic_block scop_entry, loop_p outermost_loop,

                             loop_p loop)

                             loop_p loop)

{

{

  tree niter = number_of_latch_executions (loop);

  tree niter = number_of_latch_executions (loop);

  /* Number of iterations unknown.  */

  /* Number of iterations unknown.  */

  if (chrec_contains_undetermined (niter))

  if (chrec_contains_undetermined (niter))

    return false;

    return false;

  /* Number of iterations not affine.  */

  /* Number of iterations not affine.  */

  if (!graphite_can_represent_expr (scop_entry, loop, outermost_loop, niter))

  if (!graphite_can_represent_expr (scop_entry, loop, outermost_loop, niter))

    return false;

    return false;

  return true;

  return true;

}

}

/* Store information needed by scopdet_* functions.  */

/* Store information needed by scopdet_* functions.  */

struct scopdet_info

struct scopdet_info

{

{

  /* Exit of the open scop would stop if the current BB is harmful.  */

  /* Exit of the open scop would stop if the current BB is harmful.  */

  basic_block exit;

  basic_block exit;

  /* Where the next scop would start if the current BB is harmful.  */

  /* Where the next scop would start if the current BB is harmful.  */

  basic_block next;

  basic_block next;

  /* The bb or one of its children contains open loop exits.  That means

  /* The bb or one of its children contains open loop exits.  That means

     loop exit nodes that are not surrounded by a loop dominated by bb.  */

     loop exit nodes that are not surrounded by a loop dominated by bb.  */

  bool exits;

  bool exits;

  /* The bb or one of its children contains only structures we can handle.  */

  /* The bb or one of its children contains only structures we can handle.  */

  bool difficult;

  bool difficult;

};

};

static struct scopdet_info build_scops_1 (basic_block, loop_p,

static struct scopdet_info build_scops_1 (basic_block, loop_p,

                                          VEC (sd_region, heap) **, loop_p);

                                          VEC (sd_region, heap) **, loop_p);

/* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB

/* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB

   to SCOPS.  TYPE is the gbb_type of BB.  */

   to SCOPS.  TYPE is the gbb_type of BB.  */

static struct scopdet_info

static struct scopdet_info

scopdet_basic_block_info (basic_block bb, loop_p outermost_loop,

scopdet_basic_block_info (basic_block bb, loop_p outermost_loop,

                          VEC (sd_region, heap) **scops, gbb_type type)

                          VEC (sd_region, heap) **scops, gbb_type type)

{

{

  loop_p loop = bb->loop_father;

  loop_p loop = bb->loop_father;

  struct scopdet_info result;

  struct scopdet_info result;

  gimple stmt;

  gimple stmt;

  /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps.  */

  /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps.  */

  basic_block entry_block = ENTRY_BLOCK_PTR;

  basic_block entry_block = ENTRY_BLOCK_PTR;

  stmt = harmful_stmt_in_bb (entry_block, outermost_loop, bb);

  stmt = harmful_stmt_in_bb (entry_block, outermost_loop, bb);

  result.difficult = (stmt != NULL);

  result.difficult = (stmt != NULL);

  result.exit = NULL;

  result.exit = NULL;

  switch (type)

  switch (type)

    {

    {

    case GBB_LAST:

    case GBB_LAST:

      result.next = NULL;

      result.next = NULL;

      result.exits = false;

      result.exits = false;

      /* Mark bbs terminating a SESE region difficult, if they start

      /* Mark bbs terminating a SESE region difficult, if they start

         a condition.  */

         a condition.  */

      if (!single_succ_p (bb))

      if (!single_succ_p (bb))

        result.difficult = true;

        result.difficult = true;

      else

      else

        result.exit = single_succ (bb);

        result.exit = single_succ (bb);

      break;

      break;

    case GBB_SIMPLE:

    case GBB_SIMPLE:

      result.next = single_succ (bb);

      result.next = single_succ (bb);

      result.exits = false;

      result.exits = false;

      result.exit = single_succ (bb);

      result.exit = single_succ (bb);

      break;

      break;

    case GBB_LOOP_SING_EXIT_HEADER:

    case GBB_LOOP_SING_EXIT_HEADER:

      {

      {

        VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);

        VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);

        struct scopdet_info sinfo;

        struct scopdet_info sinfo;

        edge exit_e = single_exit (loop);

        edge exit_e = single_exit (loop);

        sinfo = build_scops_1 (bb, outermost_loop, &regions, loop);

        sinfo = build_scops_1 (bb, outermost_loop, &regions, loop);

        if (!graphite_can_represent_loop (entry_block, outermost_loop, loop))

        if (!graphite_can_represent_loop (entry_block, outermost_loop, loop))

          result.difficult = true;

          result.difficult = true;

        result.difficult |= sinfo.difficult;

        result.difficult |= sinfo.difficult;

        /* Try again with another loop level.  */

        /* Try again with another loop level.  */

        if (result.difficult

        if (result.difficult

            && loop_depth (outermost_loop) + 1 == loop_depth (loop))

            && loop_depth (outermost_loop) + 1 == loop_depth (loop))

          {

          {

            outermost_loop = loop;

            outermost_loop = loop;

            VEC_free (sd_region, heap, regions);

            VEC_free (sd_region, heap, regions);

            regions = VEC_alloc (sd_region, heap, 3);

            regions = VEC_alloc (sd_region, heap, 3);

            sinfo = scopdet_basic_block_info (bb, outermost_loop, scops, type);

            sinfo = scopdet_basic_block_info (bb, outermost_loop, scops, type);

            result = sinfo;

            result = sinfo;

            result.difficult = true;

            result.difficult = true;

            if (sinfo.difficult)

            if (sinfo.difficult)

              move_sd_regions (&regions, scops);

              move_sd_regions (&regions, scops);

            else

            else

              {

              {

                sd_region open_scop;

                sd_region open_scop;

                open_scop.entry = bb;

                open_scop.entry = bb;

                open_scop.exit = exit_e->dest;

                open_scop.exit = exit_e->dest;

                VEC_safe_push (sd_region, heap, *scops, &open_scop);

                VEC_safe_push (sd_region, heap, *scops, &open_scop);

                VEC_free (sd_region, heap, regions);

                VEC_free (sd_region, heap, regions);

              }

              }

          }

          }

        else

        else

          {

          {

            result.exit = exit_e->dest;

            result.exit = exit_e->dest;

            result.next = exit_e->dest;

            result.next = exit_e->dest;

            /* If we do not dominate result.next, remove it.  It's either

            /* If we do not dominate result.next, remove it.  It's either

               the EXIT_BLOCK_PTR, or another bb dominates it and will

               the EXIT_BLOCK_PTR, or another bb dominates it and will

               call the scop detection for this bb.  */

               call the scop detection for this bb.  */

            if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))

            if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))

              result.next = NULL;

              result.next = NULL;

            if (exit_e->src->loop_father != loop)

            if (exit_e->src->loop_father != loop)

              result.next = NULL;

              result.next = NULL;

            result.exits = false;

            result.exits = false;

            if (result.difficult)

            if (result.difficult)

              move_sd_regions (&regions, scops);

              move_sd_regions (&regions, scops);

            else

            else

              VEC_free (sd_region, heap, regions);

              VEC_free (sd_region, heap, regions);

          }

          }

        break;

        break;

      }

      }

    case GBB_LOOP_MULT_EXIT_HEADER:

    case GBB_LOOP_MULT_EXIT_HEADER:

      {

      {

        /* XXX: For now we just do not join loops with multiple exits.  If the

        /* XXX: For now we just do not join loops with multiple exits.  If the

           exits lead to the same bb it may be possible to join the loop.  */

           exits lead to the same bb it may be possible to join the loop.  */

        VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);

        VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);

        VEC (edge, heap) *exits = get_loop_exit_edges (loop);

        VEC (edge, heap) *exits = get_loop_exit_edges (loop);

        edge e;

        edge e;

        int i;

        int i;

        build_scops_1 (bb, loop, &regions, loop);

        build_scops_1 (bb, loop, &regions, loop);

        /* Scan the code dominated by this loop.  This means all bbs, that are

        /* Scan the code dominated by this loop.  This means all bbs, that are

           are dominated by a bb in this loop, but are not part of this loop.

           are dominated by a bb in this loop, but are not part of this loop.

           The easiest case:

           The easiest case:

             - The loop exit destination is dominated by the exit sources.

             - The loop exit destination is dominated by the exit sources.

           TODO: We miss here the more complex cases:

           TODO: We miss here the more complex cases:

                  - The exit destinations are dominated by another bb inside

                  - The exit destinations are dominated by another bb inside

                    the loop.

                    the loop.

                  - The loop dominates bbs, that are not exit destinations.  */

                  - The loop dominates bbs, that are not exit destinations.  */

        for (i = 0; VEC_iterate (edge, exits, i, e); i++)

        for (i = 0; VEC_iterate (edge, exits, i, e); i++)

          if (e->src->loop_father == loop

          if (e->src->loop_father == loop

              && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))

              && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))

            {

            {

              if (loop_outer (outermost_loop))

              if (loop_outer (outermost_loop))

                outermost_loop = loop_outer (outermost_loop);

                outermost_loop = loop_outer (outermost_loop);

              /* Pass loop_outer to recognize e->dest as loop header in

              /* Pass loop_outer to recognize e->dest as loop header in

                 build_scops_1.  */

                 build_scops_1.  */

              if (e->dest->loop_father->header == e->dest)

              if (e->dest->loop_father->header == e->dest)

                build_scops_1 (e->dest, outermost_loop, &regions,

                build_scops_1 (e->dest, outermost_loop, &regions,

                               loop_outer (e->dest->loop_father));

                               loop_outer (e->dest->loop_father));

              else

              else

                build_scops_1 (e->dest, outermost_loop, &regions,

                build_scops_1 (e->dest, outermost_loop, &regions,

                               e->dest->loop_father);

                               e->dest->loop_father);

            }

            }

        result.next = NULL;

        result.next = NULL;

        result.exit = NULL;

        result.exit = NULL;

        result.difficult = true;

        result.difficult = true;

        result.exits = false;

        result.exits = false;

        move_sd_regions (&regions, scops);

        move_sd_regions (&regions, scops);

        VEC_free (edge, heap, exits);

        VEC_free (edge, heap, exits);

        break;

        break;

      }

      }

    case GBB_COND_HEADER:

    case GBB_COND_HEADER:

      {

      {

        VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);

        VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);

        struct scopdet_info sinfo;

        struct scopdet_info sinfo;

        VEC (basic_block, heap) *dominated;

        VEC (basic_block, heap) *dominated;

        int i;

        int i;