Subversion Repositories openrisc

/* Loop autoparallelization.

   Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011, 2012

   Free Software Foundation, Inc.

   Contributed by Sebastian Pop <pop@cri.ensmp.fr> and

   Zdenek Dvorak <dvorakz@suse.cz>.

This file is part of GCC.

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

the terms of the GNU General Public License as published by the Free

Software Foundation; either version 3, or (at your option) any later

version.

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

WARRANTY; without even the implied warranty of MERCHANTABILITY or

FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

for more details.

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

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

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

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tree-flow.h"

#include "cfgloop.h"

#include "tree-data-ref.h"

#include "tree-scalar-evolution.h"

#include "gimple-pretty-print.h"

#include "tree-pass.h"

#include "langhooks.h"

#include "tree-vectorizer.h"

/* This pass tries to distribute iterations of loops into several threads.

   The implementation is straightforward -- for each loop we test whether its

   iterations are independent, and if it is the case (and some additional

   conditions regarding profitability and correctness are satisfied), we

   add GIMPLE_OMP_PARALLEL and GIMPLE_OMP_FOR codes and let omp expansion

   machinery do its job.

   The most of the complexity is in bringing the code into shape expected

   by the omp expanders:

   -- for GIMPLE_OMP_FOR, ensuring that the loop has only one induction

      variable and that the exit test is at the start of the loop body

   -- for GIMPLE_OMP_PARALLEL, replacing the references to local addressable

      variables by accesses through pointers, and breaking up ssa chains

      by storing the values incoming to the parallelized loop to a structure

      passed to the new function as an argument (something similar is done

      in omp gimplification, unfortunately only a small part of the code

      can be shared).

   TODO:

   -- if there are several parallelizable loops in a function, it may be

      possible to generate the threads just once (using synchronization to

      ensure that cross-loop dependences are obeyed).

   -- handling of common scalar dependence patterns (accumulation, ...)

   -- handling of non-innermost loops  */

/*

  Reduction handling:

  currently we use vect_force_simple_reduction() to detect reduction patterns.

  The code transformation will be introduced by an example.

parloop

{

  int sum=1;

  for (i = 0; i < N; i++)

   {

    x[i] = i + 3;

    sum+=x[i];

   }

}

gimple-like code:

header_bb:

  # sum_29 = PHI <sum_11(5), 1(3)>

  # i_28 = PHI <i_12(5), 0(3)>

  D.1795_8 = i_28 + 3;

  x[i_28] = D.1795_8;

  sum_11 = D.1795_8 + sum_29;

  i_12 = i_28 + 1;

  if (N_6(D) > i_12)

    goto header_bb;

exit_bb:

  # sum_21 = PHI <sum_11(4)>

  printf (&"%d"[0], sum_21);

after reduction transformation (only relevant parts):

parloop

{

....

  # Storing the initial value given by the user.  #

  .paral_data_store.32.sum.27 = 1;

  #pragma omp parallel num_threads(4)

  #pragma omp for schedule(static)

  # The neutral element corresponding to the particular

  reduction's operation, e.g. 0 for PLUS_EXPR,

  1 for MULT_EXPR, etc. replaces the user's initial value.  #

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

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

  GIMPLE_OMP_CONTINUE

  # Adding this reduction phi is done at create_phi_for_local_result() #

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

  GIMPLE_OMP_RETURN

  # Creating the atomic operation is done at

  create_call_for_reduction_1()  #

  #pragma omp atomic_load

  D.1839_59 = *&.paral_data_load.33_51->reduction.23;

  D.1840_60 = sum.27_56 + D.1839_59;

  #pragma omp atomic_store (D.1840_60);

  GIMPLE_OMP_RETURN

 # collecting the result after the join of the threads is done at

  create_loads_for_reductions().

  The value computed by the threads is loaded from the

  shared struct.  #

  .paral_data_load.33_52 = &.paral_data_store.32;

  sum_37 =  .paral_data_load.33_52->sum.27;

  sum_43 = D.1795_41 + sum_37;

  exit bb:

  # sum_21 = PHI <sum_43, sum_26>

  printf (&"%d"[0], sum_21);

...

}

*/

/* Minimal number of iterations of a loop that should be executed in each

   thread.  */

#define MIN_PER_THREAD 100

/* Element of the hashtable, representing a

   reduction in the current loop.  */

struct reduction_info

{

  gimple reduc_stmt;            /* reduction statement.  */

  gimple reduc_phi;             /* The phi node defining the reduction.  */

  enum tree_code reduction_code;/* code for the reduction operation.  */

  unsigned reduc_version;       /* SSA_NAME_VERSION of original reduc_phi

                                   result.  */

  gimple keep_res;              /* The PHI_RESULT of this phi is the resulting value

                                   of the reduction variable when existing the loop. */

  tree initial_value;           /* The initial value of the reduction var before entering the loop.  */

  tree field;                   /*  the name of the field in the parloop data structure intended for reduction.  */

  tree init;                    /* reduction initialization value.  */

  gimple new_phi;               /* (helper field) Newly created phi node whose result

                                   will be passed to the atomic operation.  Represents

                                   the local result each thread computed for the reduction

                                   operation.  */

};

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

static int

reduction_info_eq (const void *aa, const void *bb)

{

  const struct reduction_info *a = (const struct reduction_info *) aa;

  const struct reduction_info *b = (const struct reduction_info *) bb;

  return (a->reduc_phi == b->reduc_phi);

}

static hashval_t

reduction_info_hash (const void *aa)

{

  const struct reduction_info *a = (const struct reduction_info *) aa;

  return a->reduc_version;

}

static struct reduction_info *

reduction_phi (htab_t reduction_list, gimple phi)

{

  struct reduction_info tmpred, *red;

  if (htab_elements (reduction_list) == 0 || phi == NULL)

    return NULL;

  tmpred.reduc_phi = phi;

  tmpred.reduc_version = gimple_uid (phi);

  red = (struct reduction_info *) htab_find (reduction_list, &tmpred);

  return red;

}

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

struct name_to_copy_elt

{

  unsigned version;     /* The version of the name to copy.  */

  tree new_name;        /* The new name used in the copy.  */

  tree field;           /* The field of the structure used to pass the

                           value.  */

};

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

static int

name_to_copy_elt_eq (const void *aa, const void *bb)

{

  const struct name_to_copy_elt *a = (const struct name_to_copy_elt *) aa;

  const struct name_to_copy_elt *b = (const struct name_to_copy_elt *) bb;

  return a->version == b->version;

}

static hashval_t

name_to_copy_elt_hash (const void *aa)

{

  const struct name_to_copy_elt *a = (const struct name_to_copy_elt *) aa;

  return (hashval_t) a->version;

}

/* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE

   matrix.  Rather than use floats, we simply keep a single DENOMINATOR that

   represents the denominator for every element in the matrix.  */

typedef struct lambda_trans_matrix_s

{

  lambda_matrix matrix;

  int rowsize;

  int colsize;

  int denominator;

} *lambda_trans_matrix;

#define LTM_MATRIX(T) ((T)->matrix)

#define LTM_ROWSIZE(T) ((T)->rowsize)

#define LTM_COLSIZE(T) ((T)->colsize)

#define LTM_DENOMINATOR(T) ((T)->denominator)

/* Allocate a new transformation matrix.  */

static lambda_trans_matrix

lambda_trans_matrix_new (int colsize, int rowsize,

                         struct obstack * lambda_obstack)

{

  lambda_trans_matrix ret;

  ret = (lambda_trans_matrix)

    obstack_alloc (lambda_obstack, sizeof (struct lambda_trans_matrix_s));

  LTM_MATRIX (ret) = lambda_matrix_new (rowsize, colsize, lambda_obstack);

  LTM_ROWSIZE (ret) = rowsize;

  LTM_COLSIZE (ret) = colsize;

  LTM_DENOMINATOR (ret) = 1;

  return ret;

}

/* Multiply a vector VEC by a matrix MAT.

   MAT is an M*N matrix, and VEC is a vector with length N.  The result

   is stored in DEST which must be a vector of length M.  */

static void

lambda_matrix_vector_mult (lambda_matrix matrix, int m, int n,

                           lambda_vector vec, lambda_vector dest)

{

  int i, j;

  lambda_vector_clear (dest, m);

  for (i = 0; i < m; i++)

    for (j = 0; j < n; j++)

      dest[i] += matrix[i][j] * vec[j];

}

/* Return true if TRANS is a legal transformation matrix that respects

   the dependence vectors in DISTS and DIRS.  The conservative answer

   is false.

   "Wolfe proves that a unimodular transformation represented by the

   matrix T is legal when applied to a loop nest with a set of

   lexicographically non-negative distance vectors RDG if and only if

   for each vector d in RDG, (T.d >= 0) is lexicographically positive.

   i.e.: if and only if it transforms the lexicographically positive

   distance vectors to lexicographically positive vectors.  Note that

   a unimodular matrix must transform the zero vector (and only it) to

   the zero vector." S.Muchnick.  */

static bool

lambda_transform_legal_p (lambda_trans_matrix trans,

                          int nb_loops,

                          VEC (ddr_p, heap) *dependence_relations)

{

  unsigned int i, j;

  lambda_vector distres;

  struct data_dependence_relation *ddr;

  gcc_assert (LTM_COLSIZE (trans) == nb_loops

              && LTM_ROWSIZE (trans) == nb_loops);

  /* When there are no dependences, the transformation is correct.  */

  if (VEC_length (ddr_p, dependence_relations) == 0)

    return true;

  ddr = VEC_index (ddr_p, dependence_relations, 0);

  if (ddr == NULL)

    return true;

  /* When there is an unknown relation in the dependence_relations, we

     know that it is no worth looking at this loop nest: give up.  */

  if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)

    return false;

  distres = lambda_vector_new (nb_loops);

  /* For each distance vector in the dependence graph.  */

  FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)

    {

      /* Don't care about relations for which we know that there is no

         dependence, nor about read-read (aka. output-dependences):

         these data accesses can happen in any order.  */

      if (DDR_ARE_DEPENDENT (ddr) == chrec_known

          || (DR_IS_READ (DDR_A (ddr)) && DR_IS_READ (DDR_B (ddr))))

        continue;

      /* Conservatively answer: "this transformation is not valid".  */

      if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)

        return false;

      /* If the dependence could not be captured by a distance vector,

         conservatively answer that the transform is not valid.  */

      if (DDR_NUM_DIST_VECTS (ddr) == 0)

        return false;

      /* Compute trans.dist_vect */

      for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)

        {

          lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops,

                                     DDR_DIST_VECT (ddr, j), distres);

          if (!lambda_vector_lexico_pos (distres, nb_loops))

            return false;

        }

    }

  return true;

}

/* Data dependency analysis. Returns true if the iterations of LOOP

   are independent on each other (that is, if we can execute them

   in parallel).  */

static bool

loop_parallel_p (struct loop *loop, struct obstack * parloop_obstack)

{

  VEC (loop_p, heap) *loop_nest;

  VEC (ddr_p, heap) *dependence_relations;

  VEC (data_reference_p, heap) *datarefs;

  lambda_trans_matrix trans;

  bool ret = false;

  if (dump_file && (dump_flags & TDF_DETAILS))

  {

    fprintf (dump_file, "Considering loop %d\n", loop->num);

    if (!loop->inner)

      fprintf (dump_file, "loop is innermost\n");

    else

      fprintf (dump_file, "loop NOT innermost\n");

   }

  /* Check for problems with dependences.  If the loop can be reversed,

     the iterations are independent.  */

  datarefs = VEC_alloc (data_reference_p, heap, 10);

  dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);

  loop_nest = VEC_alloc (loop_p, heap, 3);

  if (! compute_data_dependences_for_loop (loop, true, &loop_nest, &datarefs,

                                           &dependence_relations))

    {

      if (dump_file && (dump_flags & TDF_DETAILS))

        fprintf (dump_file, "  FAILED: cannot analyze data dependencies\n");

      ret = false;

      goto end;

    }

  if (dump_file && (dump_flags & TDF_DETAILS))

    dump_data_dependence_relations (dump_file, dependence_relations);

  trans = lambda_trans_matrix_new (1, 1, parloop_obstack);

  LTM_MATRIX (trans)[0][0] = -1;

  if (lambda_transform_legal_p (trans, 1, dependence_relations))

    {

      ret = true;

      if (dump_file && (dump_flags & TDF_DETAILS))

        fprintf (dump_file, "  SUCCESS: may be parallelized\n");

    }

  else if (dump_file && (dump_flags & TDF_DETAILS))

    fprintf (dump_file,

             "  FAILED: data dependencies exist across iterations\n");

 end:

  VEC_free (loop_p, heap, loop_nest);

  free_dependence_relations (dependence_relations);

  free_data_refs (datarefs);

  return ret;

}

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

   BB_IRREDUCIBLE_LOOP flag.  */

static inline bool

loop_has_blocks_with_irreducible_flag (struct loop *loop)

{

  unsigned i;

  basic_block *bbs = get_loop_body_in_dom_order (loop);

  bool res = true;

  for (i = 0; i < loop->num_nodes; i++)

    if (bbs[i]->flags & BB_IRREDUCIBLE_LOOP)

      goto end;

  res = false;

 end:

  free (bbs);

  return res;

}

/* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.

   The assignment statement is placed on edge ENTRY.  DECL_ADDRESS maps decls

   to their addresses that can be reused.  The address of OBJ is known to

   be invariant in the whole function.  Other needed statements are placed

   right before GSI.  */

static tree

take_address_of (tree obj, tree type, edge entry, htab_t decl_address,

                 gimple_stmt_iterator *gsi)

{

  int uid;

  void **dslot;

  struct int_tree_map ielt, *nielt;

  tree *var_p, name, bvar, addr;

  gimple stmt;

  gimple_seq stmts;

  /* Since the address of OBJ is invariant, the trees may be shared.

     Avoid rewriting unrelated parts of the code.  */

  obj = unshare_expr (obj);

  for (var_p = &obj;

       handled_component_p (*var_p);

       var_p = &TREE_OPERAND (*var_p, 0))

    continue;

  /* Canonicalize the access to base on a MEM_REF.  */

  if (DECL_P (*var_p))

    *var_p = build_simple_mem_ref (build_fold_addr_expr (*var_p));

  /* Assign a canonical SSA name to the address of the base decl used

     in the address and share it for all accesses and addresses based

     on it.  */

  uid = DECL_UID (TREE_OPERAND (TREE_OPERAND (*var_p, 0), 0));

  ielt.uid = uid;

  dslot = htab_find_slot_with_hash (decl_address, &ielt, uid, INSERT);

  if (!*dslot)

    {

      if (gsi == NULL)

        return NULL;

      addr = TREE_OPERAND (*var_p, 0);

      bvar = create_tmp_var (TREE_TYPE (addr),

                             get_name (TREE_OPERAND

                                         (TREE_OPERAND (*var_p, 0), 0)));

      add_referenced_var (bvar);

      stmt = gimple_build_assign (bvar, addr);

      name = make_ssa_name (bvar, stmt);

      gimple_assign_set_lhs (stmt, name);

      gsi_insert_on_edge_immediate (entry, stmt);

      nielt = XNEW (struct int_tree_map);

      nielt->uid = uid;

      nielt->to = name;

      *dslot = nielt;

    }

  else

    name = ((struct int_tree_map *) *dslot)->to;

  /* Express the address in terms of the canonical SSA name.  */

  TREE_OPERAND (*var_p, 0) = name;

  if (gsi == NULL)

    return build_fold_addr_expr_with_type (obj, type);

  name = force_gimple_operand (build_addr (obj, current_function_decl),

                               &stmts, true, NULL_TREE);

  if (!gimple_seq_empty_p (stmts))

    gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);

  if (!useless_type_conversion_p (type, TREE_TYPE (name)))

    {

      name = force_gimple_operand (fold_convert (type, name), &stmts, true,

                                   NULL_TREE);

      if (!gimple_seq_empty_p (stmts))

        gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);

    }

  return name;

}

/* Callback for htab_traverse.  Create the initialization statement

   for reduction described in SLOT, and place it at the preheader of

   the loop described in DATA.  */

static int

initialize_reductions (void **slot, void *data)

{

  tree init, c;

  tree bvar, type, arg;

  edge e;

  struct reduction_info *const reduc = (struct reduction_info *) *slot;

  struct loop *loop = (struct loop *) data;

  /* Create initialization in preheader:

     reduction_variable = initialization value of reduction.  */

  /* In the phi node at the header, replace the argument coming

     from the preheader with the reduction initialization value.  */

  /* Create a new variable to initialize the reduction.  */

  type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));

  bvar = create_tmp_var (type, "reduction");

  add_referenced_var (bvar);

  c = build_omp_clause (gimple_location (reduc->reduc_stmt),

                        OMP_CLAUSE_REDUCTION);

  OMP_CLAUSE_REDUCTION_CODE (c) = reduc->reduction_code;

  OMP_CLAUSE_DECL (c) = SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt));

  init = omp_reduction_init (c, TREE_TYPE (bvar));

  reduc->init = init;

  /* Replace the argument representing the initialization value

     with the initialization value for the reduction (neutral

     element for the particular operation, e.g. 0 for PLUS_EXPR,

     1 for MULT_EXPR, etc).

     Keep the old value in a new variable "reduction_initial",

     that will be taken in consideration after the parallel

     computing is done.  */

  e = loop_preheader_edge (loop);

  arg = PHI_ARG_DEF_FROM_EDGE (reduc->reduc_phi, e);

  /* Create new variable to hold the initial value.  */

  SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE

           (reduc->reduc_phi, loop_preheader_edge (loop)), init);

  reduc->initial_value = arg;

  return 1;

}

struct elv_data

{

  struct walk_stmt_info info;

  edge entry;

  htab_t decl_address;

  gimple_stmt_iterator *gsi;

  bool changed;

  bool reset;

};

/* Eliminates references to local variables in *TP out of the single

   entry single exit region starting at DTA->ENTRY.

   DECL_ADDRESS contains addresses of the references that had their

   address taken already.  If the expression is changed, CHANGED is

   set to true.  Callback for walk_tree.  */

static tree

eliminate_local_variables_1 (tree *tp, int *walk_subtrees, void *data)

{

  struct elv_data *const dta = (struct elv_data *) data;

  tree t = *tp, var, addr, addr_type, type, obj;

  if (DECL_P (t))

    {

      *walk_subtrees = 0;

      if (!SSA_VAR_P (t) || DECL_EXTERNAL (t))

        return NULL_TREE;

      type = TREE_TYPE (t);

      addr_type = build_pointer_type (type);

      addr = take_address_of (t, addr_type, dta->entry, dta->decl_address,

                              dta->gsi);

      if (dta->gsi == NULL && addr == NULL_TREE)

        {

          dta->reset = true;

          return NULL_TREE;

        }

      *tp = build_simple_mem_ref (addr);

      dta->changed = true;

      return NULL_TREE;

    }

  if (TREE_CODE (t) == ADDR_EXPR)

    {

      /* ADDR_EXPR may appear in two contexts:

         -- as a gimple operand, when the address taken is a function invariant

         -- as gimple rhs, when the resulting address in not a function

            invariant

         We do not need to do anything special in the latter case (the base of

         the memory reference whose address is taken may be replaced in the

         DECL_P case).  The former case is more complicated, as we need to

         ensure that the new address is still a gimple operand.  Thus, it

         is not sufficient to replace just the base of the memory reference --

         we need to move the whole computation of the address out of the

         loop.  */

      if (!is_gimple_val (t))

        return NULL_TREE;

      *walk_subtrees = 0;

      obj = TREE_OPERAND (t, 0);

      var = get_base_address (obj);

      if (!var || !SSA_VAR_P (var) || DECL_EXTERNAL (var))

        return NULL_TREE;

      addr_type = TREE_TYPE (t);

      addr = take_address_of (obj, addr_type, dta->entry, dta->decl_address,

                              dta->gsi);

      if (dta->gsi == NULL && addr == NULL_TREE)

        {

          dta->reset = true;

          return NULL_TREE;

        }

      *tp = addr;

      dta->changed = true;

      return NULL_TREE;

    }

  if (!EXPR_P (t))

    *walk_subtrees = 0;

  return NULL_TREE;

}

/* Moves the references to local variables in STMT at *GSI out of the single

   entry single exit region starting at ENTRY.  DECL_ADDRESS contains

   addresses of the references that had their address taken

   already.  */

static void

eliminate_local_variables_stmt (edge entry, gimple_stmt_iterator *gsi,

                                htab_t decl_address)

{

  struct elv_data dta;

  gimple stmt = gsi_stmt (*gsi);

  memset (&dta.info, '\0', sizeof (dta.info));

  dta.entry = entry;

  dta.decl_address = decl_address;

  dta.changed = false;

  dta.reset = false;

  if (gimple_debug_bind_p (stmt))

    {

      dta.gsi = NULL;

      walk_tree (gimple_debug_bind_get_value_ptr (stmt),

                 eliminate_local_variables_1, &dta.info, NULL);

      if (dta.reset)

        {

          gimple_debug_bind_reset_value (stmt);

          dta.changed = true;

        }

    }

  else

    {

      dta.gsi = gsi;

      walk_gimple_op (stmt, eliminate_local_variables_1, &dta.info);

    }

  if (dta.changed)

    update_stmt (stmt);

}

/* Eliminates the references to local variables from the single entry

   single exit region between the ENTRY and EXIT edges.

   This includes:

   1) Taking address of a local variable -- these are moved out of the

   region (and temporary variable is created to hold the address if

   necessary).

   2) Dereferencing a local variable -- these are replaced with indirect

   references.  */

static void

eliminate_local_variables (edge entry, edge exit)

{

  basic_block bb;

  VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);

  unsigned i;

  gimple_stmt_iterator gsi;

  bool has_debug_stmt = false;

  htab_t decl_address = htab_create (10, int_tree_map_hash, int_tree_map_eq,

                                     free);

  basic_block entry_bb = entry->src;

  basic_block exit_bb = exit->dest;

  gather_blocks_in_sese_region (entry_bb, exit_bb, &body);

  FOR_EACH_VEC_ELT (basic_block, body, i, bb)

    if (bb != entry_bb && bb != exit_bb)

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