Subversion Repositories openrisc_2011-10-31

/* Loop autoparallelization.

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

   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 "tm.h"

#include "tree.h"

#include "rtl.h"

#include "tree-flow.h"

#include "cfgloop.h"

#include "ggc.h"

#include "tree-data-ref.h"

#include "diagnostic.h"

#include "tree-pass.h"

#include "tree-scalar-evolution.h"

#include "hashtab.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_is_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.  */

  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 htab_hash_pointer (a->reduc_phi);

}

static struct reduction_info *

reduction_phi (htab_t reduction_list, gimple phi)

{

  struct reduction_info tmpred, *red;

  if (htab_elements (reduction_list) == 0)

    return NULL;

  tmpred.reduc_phi = 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;

}

/* 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)

{

  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);

  compute_data_dependences_for_loop (loop, true, &datarefs,

                                     &dependence_relations);

  if (dump_file && (dump_flags & TDF_DETAILS))

    dump_data_dependence_relations (dump_file, dependence_relations);

  trans = lambda_trans_matrix_new (1, 1);

  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");

  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.  */

static tree

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

{

  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;

  uid = DECL_UID (*var_p);

  ielt.uid = uid;

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

  if (!*dslot)

    {

      addr = build_addr (*var_p, current_function_decl);

      bvar = create_tmp_var (TREE_TYPE (addr), get_name (*var_p));

      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;

  if (var_p != &obj)

    {

      *var_p = build1 (INDIRECT_REF, TREE_TYPE (*var_p), name);

      name = force_gimple_operand (build_addr (obj, current_function_decl),

                                   &stmts, true, NULL_TREE);

      if (!gimple_seq_empty_p (stmts))

        gsi_insert_seq_on_edge_immediate (entry, stmts);

    }

  if (TREE_TYPE (name) != type)

    {

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

                                   NULL_TREE);

      if (!gimple_seq_empty_p (stmts))

        gsi_insert_seq_on_edge_immediate (entry, stmts);

    }

  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;

  bool changed;

};

/* 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);

      *tp = build1 (INDIRECT_REF, TREE_TYPE (*tp), 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);

      *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 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,

                                htab_t decl_address)

{

  struct elv_data dta;

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

  dta.entry = entry;

  dta.decl_address = decl_address;

  dta.changed = false;

  if (gimple_debug_bind_p (stmt))

    walk_tree (gimple_debug_bind_get_value_ptr (stmt),

               eliminate_local_variables_1, &dta.info, NULL);

  else

    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;

  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 (i = 0; VEC_iterate (basic_block, body, i, bb); i++)

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

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

        eliminate_local_variables_stmt (entry, gsi_stmt (gsi),

                                        decl_address);

  htab_delete (decl_address);

  VEC_free (basic_block, heap, body);

}

/* Returns true if expression EXPR is not defined between ENTRY and

   EXIT, i.e. if all its operands are defined outside of the region.  */

static bool

expr_invariant_in_region_p (edge entry, edge exit, tree expr)

{

  basic_block entry_bb = entry->src;

  basic_block exit_bb = exit->dest;

  basic_block def_bb;

  if (is_gimple_min_invariant (expr))

    return true;

  if (TREE_CODE (expr) == SSA_NAME)

    {

      def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));

      if (def_bb

          && dominated_by_p (CDI_DOMINATORS, def_bb, entry_bb)

          && !dominated_by_p (CDI_DOMINATORS, def_bb, exit_bb))

        return false;

      return true;

    }

  return false;

}

/* If COPY_NAME_P is true, creates and returns a duplicate of NAME.

   The copies are stored to NAME_COPIES, if NAME was already duplicated,

   its duplicate stored in NAME_COPIES is returned.

   Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also

   duplicated, storing the copies in DECL_COPIES.  */

static tree

separate_decls_in_region_name (tree name,

                               htab_t name_copies, htab_t decl_copies,

                               bool copy_name_p)

{

  tree copy, var, var_copy;

  unsigned idx, uid, nuid;

  struct int_tree_map ielt, *nielt;

  struct name_to_copy_elt elt, *nelt;

  void **slot, **dslot;

  if (TREE_CODE (name) != SSA_NAME)

    return name;

  idx = SSA_NAME_VERSION (name);

  elt.version = idx;

  slot = htab_find_slot_with_hash (name_copies, &elt, idx,

                                   copy_name_p ? INSERT : NO_INSERT);

  if (slot && *slot)

    return ((struct name_to_copy_elt *) *slot)->new_name;

  var = SSA_NAME_VAR (name);

  uid = DECL_UID (var);

  ielt.uid = uid;

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

  if (!*dslot)

    {

      var_copy = create_tmp_var (TREE_TYPE (var), get_name (var));

      DECL_GIMPLE_REG_P (var_copy) = DECL_GIMPLE_REG_P (var);

      add_referenced_var (var_copy);

      nielt = XNEW (struct int_tree_map);

      nielt->uid = uid;

      nielt->to = var_copy;

      *dslot = nielt;

      /* Ensure that when we meet this decl next time, we won't duplicate

         it again.  */

      nuid = DECL_UID (var_copy);

      ielt.uid = nuid;

      dslot = htab_find_slot_with_hash (decl_copies, &ielt, nuid, INSERT);

      gcc_assert (!*dslot);

      nielt = XNEW (struct int_tree_map);

      nielt->uid = nuid;

      nielt->to = var_copy;

      *dslot = nielt;

    }

  else

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

  if (copy_name_p)

    {

      copy = duplicate_ssa_name (name, NULL);

      nelt = XNEW (struct name_to_copy_elt);

      nelt->version = idx;

      nelt->new_name = copy;

      nelt->field = NULL_TREE;

      *slot = nelt;

    }

  else

    {

      gcc_assert (!slot);

      copy = name;

    }

  SSA_NAME_VAR (copy) = var_copy;

  return copy;

}

/* Finds the ssa names used in STMT that are defined outside the

   region between ENTRY and EXIT and replaces such ssa names with

   their duplicates.  The duplicates are stored to NAME_COPIES.  Base

   decls of all ssa names used in STMT (including those defined in

   LOOP) are replaced with the new temporary variables; the

   replacement decls are stored in DECL_COPIES.  */

static void

separate_decls_in_region_stmt (edge entry, edge exit, gimple stmt,

                               htab_t name_copies, htab_t decl_copies)

{

  use_operand_p use;

  def_operand_p def;

  ssa_op_iter oi;

  tree name, copy;

  bool copy_name_p;

  mark_virtual_ops_for_renaming (stmt);

  FOR_EACH_PHI_OR_STMT_DEF (def, stmt, oi, SSA_OP_DEF)

  {

    name = DEF_FROM_PTR (def);

    gcc_assert (TREE_CODE (name) == SSA_NAME);

    copy = separate_decls_in_region_name (name, name_copies, decl_copies,

                                          false);

    gcc_assert (copy == name);

  }

  FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)

  {

    name = USE_FROM_PTR (use);

    if (TREE_CODE (name) != SSA_NAME)

      continue;

    copy_name_p = expr_invariant_in_region_p (entry, exit, name);

    copy = separate_decls_in_region_name (name, name_copies, decl_copies,

                                          copy_name_p);

    SET_USE (use, copy);

  }

}

/* Finds the ssa names used in STMT that are defined outside the

   region between ENTRY and EXIT and replaces such ssa names with

   their duplicates.  The duplicates are stored to NAME_COPIES.  Base

   decls of all ssa names used in STMT (including those defined in

   LOOP) are replaced with the new temporary variables; the

   replacement decls are stored in DECL_COPIES.  */

static bool

separate_decls_in_region_debug_bind (gimple stmt,

                                     htab_t name_copies, htab_t decl_copies)

{

  use_operand_p use;

  ssa_op_iter oi;

  tree var, name;

  struct int_tree_map ielt;

  struct name_to_copy_elt elt;

  void **slot, **dslot;

  var = gimple_debug_bind_get_var (stmt);

  if (TREE_CODE (var) == DEBUG_EXPR_DECL)

    return true;

  gcc_assert (DECL_P (var) && SSA_VAR_P (var));

  ielt.uid = DECL_UID (var);