Subversion Repositories openrisc

/* Predictive commoning.

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

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

/* This file implements the predictive commoning optimization.  Predictive

   commoning can be viewed as CSE around a loop, and with some improvements,

   as generalized strength reduction-- i.e., reusing values computed in

   earlier iterations of a loop in the later ones.  So far, the pass only

   handles the most useful case, that is, reusing values of memory references.

   If you think this is all just a special case of PRE, you are sort of right;

   however, concentrating on loops is simpler, and makes it possible to

   incorporate data dependence analysis to detect the opportunities, perform

   loop unrolling to avoid copies together with renaming immediately,

   and if needed, we could also take register pressure into account.

   Let us demonstrate what is done on an example:

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

     {

       a[i+2] = a[i] + a[i+1];

       b[10] = b[10] + i;

       c[i] = c[99 - i];

       d[i] = d[i + 1];

     }

   1) We find data references in the loop, and split them to mutually

      independent groups (i.e., we find components of a data dependence

      graph).  We ignore read-read dependences whose distance is not constant.

      (TODO -- we could also ignore antidependences).  In this example, we

      find the following groups:

      a[i]{read}, a[i+1]{read}, a[i+2]{write}

      b[10]{read}, b[10]{write}

      c[99 - i]{read}, c[i]{write}

      d[i + 1]{read}, d[i]{write}

   2) Inside each of the group, we verify several conditions:

      a) all the references must differ in indices only, and the indices

         must all have the same step

      b) the references must dominate loop latch (and thus, they must be

         ordered by dominance relation).

      c) the distance of the indices must be a small multiple of the step

      We are then able to compute the difference of the references (# of

      iterations before they point to the same place as the first of them).

      Also, in case there are writes in the loop, we split the groups into

      chains whose head is the write whose values are used by the reads in

      the same chain.  The chains are then processed independently,

      making the further transformations simpler.  Also, the shorter chains

      need the same number of registers, but may require lower unrolling

      factor in order to get rid of the copies on the loop latch.

      In our example, we get the following chains (the chain for c is invalid).

      a[i]{read,+0}, a[i+1]{read,-1}, a[i+2]{write,-2}

      b[10]{read,+0}, b[10]{write,+0}

      d[i + 1]{read,+0}, d[i]{write,+1}

   3) For each read, we determine the read or write whose value it reuses,

      together with the distance of this reuse.  I.e. we take the last

      reference before it with distance 0, or the last of the references

      with the smallest positive distance to the read.  Then, we remove

      the references that are not used in any of these chains, discard the

      empty groups, and propagate all the links so that they point to the

      single root reference of the chain (adjusting their distance

      appropriately).  Some extra care needs to be taken for references with

      step 0.  In our example (the numbers indicate the distance of the

      reuse),

      a[i] --> (*) 2, a[i+1] --> (*) 1, a[i+2] (*)

      b[10] --> (*) 1, b[10] (*)

   4) The chains are combined together if possible.  If the corresponding

      elements of two chains are always combined together with the same

      operator, we remember just the result of this combination, instead

      of remembering the values separately.  We may need to perform

      reassociation to enable combining, for example

      e[i] + f[i+1] + e[i+1] + f[i]

      can be reassociated as

      (e[i] + f[i]) + (e[i+1] + f[i+1])

      and we can combine the chains for e and f into one chain.

   5) For each root reference (end of the chain) R, let N be maximum distance

      of a reference reusing its value.  Variables R0 upto RN are created,

      together with phi nodes that transfer values from R1 .. RN to

      R0 .. R(N-1).

      Initial values are loaded to R0..R(N-1) (in case not all references

      must necessarily be accessed and they may trap, we may fail here;

      TODO sometimes, the loads could be guarded by a check for the number

      of iterations).  Values loaded/stored in roots are also copied to

      RN.  Other reads are replaced with the appropriate variable Ri.

      Everything is put to SSA form.

      As a small improvement, if R0 is dead after the root (i.e., all uses of

      the value with the maximum distance dominate the root), we can avoid

      creating RN and use R0 instead of it.

      In our example, we get (only the parts concerning a and b are shown):

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

        {

          f = phi (a[0], s);

          s = phi (a[1], f);

          x = phi (b[10], x);

          f = f + s;

          a[i+2] = f;

          x = x + i;

          b[10] = x;

        }

   6) Factor F for unrolling is determined as the smallest common multiple of

      (N + 1) for each root reference (N for references for that we avoided

      creating RN).  If F and the loop is small enough, loop is unrolled F

      times.  The stores to RN (R0) in the copies of the loop body are

      periodically replaced with R0, R1, ... (R1, R2, ...), so that they can

      be coalesced and the copies can be eliminated.

      TODO -- copy propagation and other optimizations may change the live

      ranges of the temporary registers and prevent them from being coalesced;

      this may increase the register pressure.

      In our case, F = 2 and the (main loop of the) result is

      for (i = 0; i < ...; i += 2)

        {

          f = phi (a[0], f);

          s = phi (a[1], s);

          x = phi (b[10], x);

          f = f + s;

          a[i+2] = f;

          x = x + i;

          b[10] = x;

          s = s + f;

          a[i+3] = s;

          x = x + i;

          b[10] = x;

       }

   TODO -- stores killing other stores can be taken into account, e.g.,

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

     {

       a[i] = 1;

       a[i+2] = 2;

     }

   can be replaced with

   t0 = a[0];

   t1 = a[1];

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

     {

       a[i] = 1;

       t2 = 2;

       t0 = t1;

       t1 = t2;

     }

   a[n] = t0;

   a[n+1] = t1;

   The interesting part is that this would generalize store motion; still, since

   sm is performed elsewhere, it does not seem that important.

   Predictive commoning can be generalized for arbitrary computations (not

   just memory loads), and also nontrivial transfer functions (e.g., replacing

   i * i with ii_last + 2 * i + 1), to generalize strength reduction.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "tree.h"

#include "tm_p.h"

#include "cfgloop.h"

#include "tree-flow.h"

#include "ggc.h"

#include "tree-data-ref.h"

#include "tree-scalar-evolution.h"

#include "tree-chrec.h"

#include "params.h"

#include "diagnostic.h"

#include "tree-pass.h"

#include "tree-affine.h"

#include "tree-inline.h"

/* The maximum number of iterations between the considered memory

   references.  */

#define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)

/* Data references (or phi nodes that carry data reference values across

   loop iterations).  */

typedef struct dref_d

{

  /* The reference itself.  */

  struct data_reference *ref;

  /* The statement in that the reference appears.  */

  gimple stmt;

  /* In case that STMT is a phi node, this field is set to the SSA name

     defined by it in replace_phis_by_defined_names (in order to avoid

     pointing to phi node that got reallocated in the meantime).  */

  tree name_defined_by_phi;

  /* Distance of the reference from the root of the chain (in number of

     iterations of the loop).  */

  unsigned distance;

  /* Number of iterations offset from the first reference in the component.  */

  double_int offset;

  /* Number of the reference in a component, in dominance ordering.  */

  unsigned pos;

  /* True if the memory reference is always accessed when the loop is

     entered.  */

  unsigned always_accessed : 1;

} *dref;

DEF_VEC_P (dref);

DEF_VEC_ALLOC_P (dref, heap);

/* Type of the chain of the references.  */

enum chain_type

{

  /* The addresses of the references in the chain are constant.  */

  CT_INVARIANT,

  /* There are only loads in the chain.  */

  CT_LOAD,

  /* Root of the chain is store, the rest are loads.  */

  CT_STORE_LOAD,

  /* A combination of two chains.  */

  CT_COMBINATION

};

/* Chains of data references.  */

typedef struct chain

{

  /* Type of the chain.  */

  enum chain_type type;

  /* For combination chains, the operator and the two chains that are

     combined, and the type of the result.  */

  enum tree_code op;

  tree rslt_type;

  struct chain *ch1, *ch2;

  /* The references in the chain.  */

  VEC(dref,heap) *refs;

  /* The maximum distance of the reference in the chain from the root.  */

  unsigned length;

  /* The variables used to copy the value throughout iterations.  */

  VEC(tree,heap) *vars;

  /* Initializers for the variables.  */

  VEC(tree,heap) *inits;

  /* True if there is a use of a variable with the maximal distance

     that comes after the root in the loop.  */

  unsigned has_max_use_after : 1;

  /* True if all the memory references in the chain are always accessed.  */

  unsigned all_always_accessed : 1;

  /* True if this chain was combined together with some other chain.  */

  unsigned combined : 1;

} *chain_p;

DEF_VEC_P (chain_p);

DEF_VEC_ALLOC_P (chain_p, heap);

/* Describes the knowledge about the step of the memory references in

   the component.  */

enum ref_step_type

{

  /* The step is zero.  */

  RS_INVARIANT,

  /* The step is nonzero.  */

  RS_NONZERO,

  /* The step may or may not be nonzero.  */

  RS_ANY

};

/* Components of the data dependence graph.  */

struct component

{

  /* The references in the component.  */

  VEC(dref,heap) *refs;

  /* What we know about the step of the references in the component.  */

  enum ref_step_type comp_step;

  /* Next component in the list.  */

  struct component *next;

};

/* Bitmap of ssa names defined by looparound phi nodes covered by chains.  */

static bitmap looparound_phis;

/* Cache used by tree_to_aff_combination_expand.  */

static struct pointer_map_t *name_expansions;

/* Dumps data reference REF to FILE.  */

extern void dump_dref (FILE *, dref);

void

dump_dref (FILE *file, dref ref)

{

  if (ref->ref)

    {

      fprintf (file, "    ");

      print_generic_expr (file, DR_REF (ref->ref), TDF_SLIM);

      fprintf (file, " (id %u%s)\n", ref->pos,

               DR_IS_READ (ref->ref) ? "" : ", write");

      fprintf (file, "      offset ");

      dump_double_int (file, ref->offset, false);

      fprintf (file, "\n");

      fprintf (file, "      distance %u\n", ref->distance);

    }

  else

    {

      if (gimple_code (ref->stmt) == GIMPLE_PHI)

        fprintf (file, "    looparound ref\n");

      else

        fprintf (file, "    combination ref\n");

      fprintf (file, "      in statement ");

      print_gimple_stmt (file, ref->stmt, 0, TDF_SLIM);

      fprintf (file, "\n");

      fprintf (file, "      distance %u\n", ref->distance);

    }

}

/* Dumps CHAIN to FILE.  */

extern void dump_chain (FILE *, chain_p);

void

dump_chain (FILE *file, chain_p chain)

{

  dref a;

  const char *chain_type;

  unsigned i;

  tree var;

  switch (chain->type)

    {

    case CT_INVARIANT:

      chain_type = "Load motion";

      break;

    case CT_LOAD:

      chain_type = "Loads-only";

      break;

    case CT_STORE_LOAD:

      chain_type = "Store-loads";

      break;

    case CT_COMBINATION:

      chain_type = "Combination";

      break;

    default:

      gcc_unreachable ();

    }

  fprintf (file, "%s chain %p%s\n", chain_type, (void *) chain,

           chain->combined ? " (combined)" : "");

  if (chain->type != CT_INVARIANT)

    fprintf (file, "  max distance %u%s\n", chain->length,

             chain->has_max_use_after ? "" : ", may reuse first");

  if (chain->type == CT_COMBINATION)

    {

      fprintf (file, "  equal to %p %s %p in type ",

               (void *) chain->ch1, op_symbol_code (chain->op),

               (void *) chain->ch2);

      print_generic_expr (file, chain->rslt_type, TDF_SLIM);

      fprintf (file, "\n");

    }

  if (chain->vars)

    {

      fprintf (file, "  vars");

      for (i = 0; VEC_iterate (tree, chain->vars, i, var); i++)

        {

          fprintf (file, " ");

          print_generic_expr (file, var, TDF_SLIM);

        }

      fprintf (file, "\n");

    }

  if (chain->inits)

    {

      fprintf (file, "  inits");

      for (i = 0; VEC_iterate (tree, chain->inits, i, var); i++)

        {

          fprintf (file, " ");

          print_generic_expr (file, var, TDF_SLIM);

        }

      fprintf (file, "\n");

    }

  fprintf (file, "  references:\n");

  for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++)

    dump_dref (file, a);

  fprintf (file, "\n");

}

/* Dumps CHAINS to FILE.  */

extern void dump_chains (FILE *, VEC (chain_p, heap) *);

void

dump_chains (FILE *file, VEC (chain_p, heap) *chains)

{

  chain_p chain;

  unsigned i;

  for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)

    dump_chain (file, chain);

}

/* Dumps COMP to FILE.  */

extern void dump_component (FILE *, struct component *);

void

dump_component (FILE *file, struct component *comp)

{

  dref a;

  unsigned i;

  fprintf (file, "Component%s:\n",

           comp->comp_step == RS_INVARIANT ? " (invariant)" : "");

  for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++)

    dump_dref (file, a);

  fprintf (file, "\n");

}

/* Dumps COMPS to FILE.  */

extern void dump_components (FILE *, struct component *);

void

dump_components (FILE *file, struct component *comps)

{

  struct component *comp;

  for (comp = comps; comp; comp = comp->next)

    dump_component (file, comp);

}

/* Frees a chain CHAIN.  */

static void

release_chain (chain_p chain)

{

  dref ref;

  unsigned i;

  if (chain == NULL)

    return;

  for (i = 0; VEC_iterate (dref, chain->refs, i, ref); i++)

    free (ref);

  VEC_free (dref, heap, chain->refs);

  VEC_free (tree, heap, chain->vars);

  VEC_free (tree, heap, chain->inits);

  free (chain);

}

/* Frees CHAINS.  */

static void

release_chains (VEC (chain_p, heap) *chains)

{

  unsigned i;

  chain_p chain;

  for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)

    release_chain (chain);

  VEC_free (chain_p, heap, chains);

}

/* Frees a component COMP.  */

static void

release_component (struct component *comp)

{

  VEC_free (dref, heap, comp->refs);

  free (comp);

}

/* Frees list of components COMPS.  */

static void

release_components (struct component *comps)

{

  struct component *act, *next;

  for (act = comps; act; act = next)

    {

      next = act->next;

      release_component (act);

    }

}

/* Finds a root of tree given by FATHERS containing A, and performs path

   shortening.  */

static unsigned

component_of (unsigned fathers[], unsigned a)

{

  unsigned root, n;

  for (root = a; root != fathers[root]; root = fathers[root])

    continue;

  for (; a != root; a = n)

    {

      n = fathers[a];

      fathers[a] = root;

    }

  return root;

}

/* Join operation for DFU.  FATHERS gives the tree, SIZES are sizes of the

   components, A and B are components to merge.  */

static void

merge_comps (unsigned fathers[], unsigned sizes[], unsigned a, unsigned b)

{

  unsigned ca = component_of (fathers, a);

  unsigned cb = component_of (fathers, b);

  if (ca == cb)

    return;

  if (sizes[ca] < sizes[cb])

    {

      sizes[cb] += sizes[ca];

      fathers[ca] = cb;

    }

  else

    {

      sizes[ca] += sizes[cb];

      fathers[cb] = ca;

    }

}

/* Returns true if A is a reference that is suitable for predictive commoning

   in the innermost loop that contains it.  REF_STEP is set according to the

   step of the reference A.  */

static bool

suitable_reference_p (struct data_reference *a, enum ref_step_type *ref_step)

{

  tree ref = DR_REF (a), step = DR_STEP (a);

  if (!step

      || !is_gimple_reg_type (TREE_TYPE (ref))

      || tree_could_throw_p (ref))

    return false;

  if (integer_zerop (step))

    *ref_step = RS_INVARIANT;

  else if (integer_nonzerop (step))

    *ref_step = RS_NONZERO;

  else

    *ref_step = RS_ANY;

  return true;

}

/* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET.  */

static void

aff_combination_dr_offset (struct data_reference *dr, aff_tree *offset)

{

  aff_tree delta;

  tree_to_aff_combination_expand (DR_OFFSET (dr), sizetype, offset,

                                  &name_expansions);

  aff_combination_const (&delta, sizetype, tree_to_double_int (DR_INIT (dr)));

  aff_combination_add (offset, &delta);

}

/* Determines number of iterations of the innermost enclosing loop before B

   refers to exactly the same location as A and stores it to OFF.  If A and

   B do not have the same step, they never meet, or anything else fails,

   returns false, otherwise returns true.  Both A and B are assumed to

   satisfy suitable_reference_p.  */

static bool

determine_offset (struct data_reference *a, struct data_reference *b,

                  double_int *off)

{

  aff_tree diff, baseb, step;

  tree typea, typeb;

  /* Check that both the references access the location in the same type.  */

  typea = TREE_TYPE (DR_REF (a));

  typeb = TREE_TYPE (DR_REF (b));

  if (!useless_type_conversion_p (typeb, typea))

    return false;

  /* Check whether the base address and the step of both references is the

     same.  */

  if (!operand_equal_p (DR_STEP (a), DR_STEP (b), 0)

      || !operand_equal_p (DR_BASE_ADDRESS (a), DR_BASE_ADDRESS (b), 0))

    return false;

  if (integer_zerop (DR_STEP (a)))

    {

      /* If the references have loop invariant address, check that they access

         exactly the same location.  */

      *off = double_int_zero;

      return (operand_equal_p (DR_OFFSET (a), DR_OFFSET (b), 0)

              && operand_equal_p (DR_INIT (a), DR_INIT (b), 0));

    }

  /* Compare the offsets of the addresses, and check whether the difference

     is a multiple of step.  */

  aff_combination_dr_offset (a, &diff);

  aff_combination_dr_offset (b, &baseb);

  aff_combination_scale (&baseb, double_int_minus_one);

  aff_combination_add (&diff, &baseb);

  tree_to_aff_combination_expand (DR_STEP (a), sizetype,

                                  &step, &name_expansions);

  return aff_combination_constant_multiple_p (&diff, &step, off);

}

/* Returns the last basic block in LOOP for that we are sure that

   it is executed whenever the loop is entered.  */

static basic_block

last_always_executed_block (struct loop *loop)

{

  unsigned i;

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

  edge ex;

  basic_block last = loop->latch;

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

    last = nearest_common_dominator (CDI_DOMINATORS, last, ex->src);

  VEC_free (edge, heap, exits);

  return last;

}

/* Splits dependence graph on DATAREFS described by DEPENDS to components.  */

static struct component *

split_data_refs_to_components (struct loop *loop,

                               VEC (data_reference_p, heap) *datarefs,

                               VEC (ddr_p, heap) *depends)

{

  unsigned i, n = VEC_length (data_reference_p, datarefs);

  unsigned ca, ia, ib, bad;

  unsigned *comp_father = XNEWVEC (unsigned, n + 1);

  unsigned *comp_size = XNEWVEC (unsigned, n + 1);

  struct component **comps;

  struct data_reference *dr, *dra, *drb;

  struct data_dependence_relation *ddr;

  struct component *comp_list = NULL, *comp;

  dref dataref;

  basic_block last_always_executed = last_always_executed_block (loop);

  for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)

    {

      if (!DR_REF (dr))

        {

          /* A fake reference for call or asm_expr that may clobber memory;

             just fail.  */

          goto end;

        }

      dr->aux = (void *) (size_t) i;

      comp_father[i] = i;

      comp_size[i] = 1;

    }

  /* A component reserved for the "bad" data references.  */

  comp_father[n] = n;

  comp_size[n] = 1;

  for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)

    {

      enum ref_step_type dummy;

      if (!suitable_reference_p (dr, &dummy))

        {

          ia = (unsigned) (size_t) dr->aux;

          merge_comps (comp_father, comp_size, n, ia);

        }

    }

  for (i = 0; VEC_iterate (ddr_p, depends, i, ddr); i++)

    {

      double_int dummy_off;