Subversion Repositories openrisc

/* RTL factoring (sequence abstraction).

   Copyright (C) 2004, 2005, 2006, 2007 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/>.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "rtl.h"

#include "obstack.h"

#include "basic-block.h"

#include "resource.h"

#include "flags.h"

#include "ggc.h"

#include "regs.h"

#include "params.h"

#include "expr.h"

#include "tm_p.h"

#include "tree-pass.h"

#include "tree-flow.h"

#include "timevar.h"

#include "output.h"

#include "addresses.h"

/* Sequence abstraction:

   It is a size optimization method. The main idea of this technique is to

   find identical sequences of code, which can be turned into procedures and

   then replace all occurrences with calls to the newly created subroutine.

   It is kind of an opposite of function inlining.

   There are four major parts of this file:

   sequence fingerprint

     In order to avoid the comparison of every insn with every other, hash

     value will be designed for every insn by COMPUTE_HASH.

     These hash values are used for grouping the sequence candidates. So

     we only need to compare every insn with every other in same hash group.

     FILL_HASH_BUCKET creates all hash values and stores into HASH_BUCKETS.

     The result is used by COLLECT_PATTERN_SEQS.

   code matching

     In code matching the algorithm compares every two possible sequence

     candidates which last insns are in the same hash group. If these

     sequences are identical they will be stored and do further searches for

     finding more sequences which are identical with the first one.

     COLLECT_PATTERN_SEQS does the code matching and stores the results into

     PATTERN_SEQS.

   gain computation

     This part computes the gain of abstraction which could be archived when

     turning the pattern sequence into a pseudo-function and its matching

     sequences into pseudo-calls. After it the most effective sequences will

     be marked for abstraction.

     RECOMPUTE_GAIN does the gain computation. The sequences with the maximum

     gain is on the top of PATTERN_SEQS.

   abstract code

     This part turns the pattern sequence into a pseudo-function and its

     matching sequences into pseudo-calls.

     ABSTRACT_BEST_SEQ does the code merging.

   C code example:

   // Original source            // After sequence abstraction

   {                             {

                                   void *jump_label;

     ...                           ...

                                   jump_label = &&exit_0;

                                 entry_0:

     I0;                           I0;

     I1;                           I1;

     I2;                           I2;

     I3;                           I3;

                                   goto *jump_label;

                                 exit_0:

     ...                           ...

                                   jump_label = &&exit_1;

                                 goto entry_0;

     I0;

     I1;

     I2;

     I3;

                                 exit_1:

     ...                           ...

                                   jump_label = &&exit_2;

                                   goto entry_0;

     I0;

     I1;

     I2;

     I3;

                                 exit_2:

     ...                           ...

                                   jump_label = &&exit_3;

                                   goto entry_0;

     I0;

     I1;

     I2;

     I3;

                                exit_3:

     ...                           ...

   }                             }

   TODO:

   - Use REG_ALLOC_ORDER when choosing link register.

   - Handle JUMP_INSNs. Also handle volatile function calls (handle them

     similar to unconditional jumps.)

   - Test command line option -fpic.

*/

/* Predicate yielding nonzero iff X is an abstractable insn.  Non-jump insns are

   abstractable.  */

#define ABSTRACTABLE_INSN_P(X) (INSN_P (X) && !JUMP_P (X))

/* First parameter of the htab_create function call.  */

#define HASH_INIT 1023

/* Multiplier for cost of sequence call to avoid abstracting short

   sequences.  */

#ifndef SEQ_CALL_COST_MULTIPLIER

#define SEQ_CALL_COST_MULTIPLIER 2

#endif

/* Recomputes the cost of MSEQ pattern/matching sequence.  */

#define RECOMPUTE_COST(SEQ)                                 \

{                                                           \

  int l;                                                    \

  rtx x = SEQ->insn;                                        \

  SEQ->cost = 0;                                            \

  for (l = 0; l < SEQ->abstracted_length; l++)              \

    {                                                       \

      SEQ->cost += compute_rtx_cost (x);                    \

      x = prev_insn_in_block (x);                           \

    }                                                       \

}

/* A sequence matching a pattern sequence.  */

typedef struct matching_seq_def

{

  /* The last insn in the matching sequence.  */

  rtx insn;

  /* Index of INSN instruction.  */

  unsigned long idx;

  /* The number of insns matching in this sequence and the pattern sequence.

   */

  int matching_length;

  /* The number of insns selected to abstract from this sequence. Less than

     or equal to MATCHING_LENGTH.  */

  int abstracted_length;

  /* The cost of the sequence.  */

  int cost;

  /* The next sequence in the chain matching the same pattern.  */

  struct matching_seq_def *next_matching_seq;

} *matching_seq;

/* A pattern instruction sequence.  */

typedef struct pattern_seq_def

{

  /* The last insn in the pattern sequence.  */

  rtx insn;

  /* Index of INSN instruction.  */

  unsigned long idx;

  /* The gain of transforming the pattern sequence into a pseudo-function and

     the matching sequences into pseudo-calls.  */

  int gain;

  /* The maximum of the ABSTRACTED_LENGTH of the matching sequences.  */

  int abstracted_length;

  /* The cost of the sequence.  */

  int cost;

  /* The register used to hold the return address during the pseudo-call.  */

  rtx link_reg;

  /* The sequences matching this pattern.  */

  matching_seq matching_seqs;

  /* The next pattern sequence in the chain.  */

  struct pattern_seq_def *next_pattern_seq;

} *pattern_seq;

/* A block of a pattern sequence.  */

typedef struct seq_block_def

{

  /* The number of insns in the block.  */

  int length;

  /* The code_label of the block.  */

  rtx label;

  /* The sequences entering the pattern sequence at LABEL.  */

  matching_seq matching_seqs;

  /* The next block in the chain. The blocks are sorted by LENGTH in

     ascending order.  */

  struct seq_block_def *next_seq_block;

} *seq_block;

/* Contains same sequence candidates for further searching.  */

typedef struct hash_bucket_def

{

  /* The hash value of the group.  */

  unsigned int hash;

  /* List of sequence candidates.  */

  htab_t seq_candidates;

} *p_hash_bucket;

/* Contains the last insn of the sequence, and its index value.  */

typedef struct hash_elem_def

{

  /* Unique index; ordered by FILL_HASH_BUCKET.  */

  unsigned long idx;

  /* The last insn in the sequence.  */

  rtx insn;

  /* The cached length of the insn.  */

  int length;

} *p_hash_elem;

/* The list of same sequence candidates.  */

static htab_t hash_buckets;

/* The pattern sequences collected from the current functions.  */

static pattern_seq pattern_seqs;

/* The blocks of the current pattern sequence.  */

static seq_block seq_blocks;

/* Cost of calling sequence.  */

static int seq_call_cost;

/* Cost of jump.  */

static int seq_jump_cost;

/* Cost of returning.  */

static int seq_return_cost;

/* Returns the first insn preceding INSN for which INSN_P is true and belongs to

   the same basic block. Returns NULL_RTX if no such insn can be found.  */

static rtx

prev_insn_in_block (rtx insn)

{

  basic_block bb = BLOCK_FOR_INSN (insn);

  if (!bb)

    return NULL_RTX;

  while (insn != BB_HEAD (bb))

    {

      insn = PREV_INSN (insn);

      if (INSN_P (insn))

        return insn;

    }

  return NULL_RTX;

}

/* Returns the hash value of INSN.  */

static unsigned int

compute_hash (rtx insn)

{

  unsigned int hash = 0;

  rtx prev;

  hash = INSN_CODE (insn) * 100;

  prev = prev_insn_in_block (insn);

  if (prev)

    hash += INSN_CODE (prev);

  return hash;

}

/* Compute the cost of INSN rtx for abstraction.  */

static int

compute_rtx_cost (rtx insn)

{

  struct hash_bucket_def tmp_bucket;

  p_hash_bucket bucket;

  struct hash_elem_def tmp_elem;

  p_hash_elem elem = NULL;

  int cost = -1;

  /* Compute hash value for INSN.  */

  tmp_bucket.hash = compute_hash (insn);

  /* Select the hash group.  */

  bucket = htab_find (hash_buckets, &tmp_bucket);

  if (bucket)

  {

    tmp_elem.insn = insn;

    /* Select the insn.  */

    elem = htab_find (bucket->seq_candidates, &tmp_elem);

    /* If INSN is parsed the cost will be the cached length.  */

    if (elem)

      cost = elem->length;

  }

  /* If we can't parse the INSN cost will be the instruction length.  */

  if (cost == -1)

  {

    cost = get_attr_length (insn);

    /* Cache the length.  */

    if (elem)

      elem->length = cost;

  }

  /* If we can't get an accurate estimate for a complex instruction,

     assume that it has the same cost as a single fast instruction.  */

  return cost != 0 ? cost : COSTS_N_INSNS (1);

}

/* Determines the number of common insns in the sequences ending in INSN1 and

   INSN2. Returns with LEN number of common insns and COST cost of sequence.

*/

static void

matching_length (rtx insn1, rtx insn2, int* len, int* cost)

{

  rtx x1;

  rtx x2;

  x1 = insn1;

  x2 = insn2;

  *len = 0;

  *cost = 0;

  while (x1 && x2 && (x1 != insn2) && (x2 != insn1)

         && rtx_equal_p (PATTERN (x1), PATTERN (x2)))

    {

      (*len)++;

      (*cost) += compute_rtx_cost (x1);

      x1 = prev_insn_in_block (x1);

      x2 = prev_insn_in_block (x2);

    }

}

/* Adds E0 as a pattern sequence to PATTERN_SEQS with E1 as a matching

   sequence.  */

static void

match_seqs (p_hash_elem e0, p_hash_elem e1)

{

  int len;

  int cost;

  matching_seq mseq, p_prev, p_next;

  /* Determines the cost of the sequence and return without doing anything

     if it is too small to produce any gain.  */

  matching_length (e0->insn, e1->insn, &len, &cost);

  if (cost <= seq_call_cost)

    return;

  /* Prepend a new PATTERN_SEQ to PATTERN_SEQS if the last pattern sequence

     does not end in E0->INSN. This assumes that once the E0->INSN changes

     the old value will never appear again.  */

  if (!pattern_seqs || pattern_seqs->insn != e0->insn)

    {

      pattern_seq pseq =

        (pattern_seq) xmalloc (sizeof (struct pattern_seq_def));

      pseq->insn = e0->insn;

      pseq->idx = e0->idx;

      pseq->gain = 0;                 /* Set to zero to force recomputing.  */

      pseq->abstracted_length = 0;

      pseq->cost = 0;

      pseq->link_reg = NULL_RTX;

      pseq->matching_seqs = NULL;

      pseq->next_pattern_seq = pattern_seqs;

      pattern_seqs = pseq;

    }

  /* Find the position of E1 in the matching sequences list.  */

  p_prev = NULL;

  p_next = pattern_seqs->matching_seqs;

  while (p_next && p_next->idx < e1->idx)

    {

      p_prev = p_next;

      p_next = p_next->next_matching_seq;

    }

  /* Add a new E1 matching sequence to the pattern sequence. We know that

     it ends in E0->INSN.  */

  mseq = (matching_seq) xmalloc (sizeof (struct matching_seq_def));

  mseq->insn = e1->insn;

  mseq->idx = e1->idx;

  mseq->matching_length = len;

  mseq->abstracted_length = 0;

  mseq->cost = cost;

  if (p_prev == NULL)

    pattern_seqs->matching_seqs = mseq;

  else

    p_prev->next_matching_seq = mseq;

  mseq->next_matching_seq = p_next;

}

/* Collects all pattern sequences and their matching sequences and puts them

   into PATTERN_SEQS.  */

static void

collect_pattern_seqs (void)

{

  htab_iterator hti0, hti1, hti2;

  p_hash_bucket hash_bucket;

  p_hash_elem e0, e1;

#ifdef STACK_REGS

  basic_block bb;

  bitmap_head stack_reg_live;

  /* Extra initialization step to ensure that no stack registers (if present)

     are live across abnormal edges. Set a flag in STACK_REG_LIVE for an insn

     if a stack register is live after the insn.  */

  bitmap_initialize (&stack_reg_live, NULL);

  FOR_EACH_BB (bb)

  {

    regset_head live;

    struct propagate_block_info *pbi;

    rtx insn;

    /* Initialize liveness propagation.  */

    INIT_REG_SET (&live);

    COPY_REG_SET (&live, bb->il.rtl->global_live_at_end);

    pbi = init_propagate_block_info (bb, &live, NULL, NULL, 0);

    /* Propagate liveness info and mark insns where a stack reg is live.  */

    insn = BB_END (bb);

    while (1)

      {

        int reg;

        for (reg = FIRST_STACK_REG; reg <= LAST_STACK_REG; reg++)

          {

            if (REGNO_REG_SET_P (&live, reg))

              {

                bitmap_set_bit (&stack_reg_live, INSN_UID (insn));

                break;

              }

          }

        if (insn == BB_HEAD (bb))

          break;

        insn = propagate_one_insn (pbi, insn);

      }

    /* Free unused data.  */

    CLEAR_REG_SET (&live);

    free_propagate_block_info (pbi);

  }

#endif

  /* Initialize PATTERN_SEQS to empty.  */

  pattern_seqs = 0;

  /* Try to match every abstractable insn with every other insn in the same

     HASH_BUCKET.  */

  FOR_EACH_HTAB_ELEMENT (hash_buckets, hash_bucket, p_hash_bucket, hti0)

    if (htab_elements (hash_bucket->seq_candidates) > 1)

      FOR_EACH_HTAB_ELEMENT (hash_bucket->seq_candidates, e0, p_hash_elem, hti1)

        FOR_EACH_HTAB_ELEMENT (hash_bucket->seq_candidates, e1, p_hash_elem,

                               hti2)

          if (e0 != e1

#ifdef STACK_REGS

              && !bitmap_bit_p (&stack_reg_live, INSN_UID (e0->insn))

              && !bitmap_bit_p (&stack_reg_live, INSN_UID (e1->insn))

#endif

             )

            match_seqs (e0, e1);

#ifdef STACK_REGS

  /* Free unused data.  */

  bitmap_clear (&stack_reg_live);

#endif

}

/* Transforms a regset to a HARD_REG_SET. Every hard register in REGS is added

   to hregs. Additionally, the hard counterpart of every renumbered pseudo

   register is also added.  */

static void

renumbered_reg_set_to_hard_reg_set (HARD_REG_SET * hregs, regset regs)

{

  int r;

  REG_SET_TO_HARD_REG_SET (*hregs, regs);

  for (r = FIRST_PSEUDO_REGISTER; r < max_regno; r++)

    if (REGNO_REG_SET_P (regs, r) && reg_renumber[r] >= 0)

      SET_HARD_REG_BIT (*hregs, reg_renumber[r]);

}

/* Clears the bits in REGS for all registers, which are live in the sequence

   give by its last INSN and its LENGTH.  */

static void

clear_regs_live_in_seq (HARD_REG_SET * regs, rtx insn, int length)

{

  basic_block bb;

  regset_head live;

  HARD_REG_SET hlive;

  struct propagate_block_info *pbi;

  rtx x;

  int i;

  /* Initialize liveness propagation.  */

  bb = BLOCK_FOR_INSN (insn);

  INIT_REG_SET (&live);

  COPY_REG_SET (&live, bb->il.rtl->global_live_at_end);

  pbi = init_propagate_block_info (bb, &live, NULL, NULL, 0);

  /* Propagate until INSN if found.  */

  for (x = BB_END (bb); x != insn;)

    x = propagate_one_insn (pbi, x);

  /* Clear registers live after INSN.  */

  renumbered_reg_set_to_hard_reg_set (&hlive, &live);

  AND_COMPL_HARD_REG_SET (*regs, hlive);

  /* Clear registers live in and before the sequence.  */

  for (i = 0; i < length;)

    {

      rtx prev = propagate_one_insn (pbi, x);

      if (INSN_P (x))

        {

          renumbered_reg_set_to_hard_reg_set (&hlive, &live);

          AND_COMPL_HARD_REG_SET (*regs, hlive);

          i++;

        }

      x = prev;

    }

  /* Free unused data.  */

  free_propagate_block_info (pbi);

  CLEAR_REG_SET (&live);

}

/* Computes the gain of turning PSEQ into a pseudo-function and its matching

   sequences into pseudo-calls. Also computes and caches the number of insns to

   abstract from  the matching sequences.  */

static void

recompute_gain_for_pattern_seq (pattern_seq pseq)

{

  matching_seq mseq;

  rtx x;

  int i;

  int hascall;

  HARD_REG_SET linkregs;

  /* Initialize data.  */

  SET_HARD_REG_SET (linkregs);

  pseq->link_reg = NULL_RTX;

  pseq->abstracted_length = 0;

  pseq->gain = -(seq_call_cost - seq_jump_cost + seq_return_cost);

  /* Determine ABSTRACTED_LENGTH and COST for matching sequences of PSEQ.

     ABSTRACTED_LENGTH may be less than MATCHING_LENGTH if sequences in the

     same block overlap. */

  for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)

    {

      /* Determine ABSTRACTED_LENGTH.  */

      if (mseq->next_matching_seq)

        mseq->abstracted_length = (int)(mseq->next_matching_seq->idx -

                                        mseq->idx);

      else

        mseq->abstracted_length = mseq->matching_length;

      if (mseq->abstracted_length > mseq->matching_length)

        mseq->abstracted_length = mseq->matching_length;

      /* Compute the cost of sequence.  */

      RECOMPUTE_COST (mseq);

      /* If COST is big enough registers live in this matching sequence

         should not be used as a link register. Also set ABSTRACTED_LENGTH

         of PSEQ.  */

      if (mseq->cost > seq_call_cost)

        {

          clear_regs_live_in_seq (&linkregs, mseq->insn,

                                  mseq->abstracted_length);

          if (mseq->abstracted_length > pseq->abstracted_length)

            pseq->abstracted_length = mseq->abstracted_length;

        }

    }

  /* Modify ABSTRACTED_LENGTH of PSEQ if pattern sequence overlaps with one

     of the matching sequences.  */

  for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)

    {

      x = pseq->insn;

      for (i = 0; (i < pseq->abstracted_length) && (x != mseq->insn); i++)

        x = prev_insn_in_block (x);

      pseq->abstracted_length = i;

    }

  /* Compute the cost of pattern sequence.  */

  RECOMPUTE_COST (pseq);

  /* No gain if COST is too small.  */

  if (pseq->cost <= seq_call_cost)

  {

    pseq->gain = -1;

    return;

  }

  /* Ensure that no matching sequence is longer than the pattern sequence.  */

  for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)

    {

      if (mseq->abstracted_length > pseq->abstracted_length)

        {

          mseq->abstracted_length = pseq->abstracted_length;

          RECOMPUTE_COST (mseq);

        }

      /* Once the length is stabilizing the gain can be calculated.  */

      if (mseq->cost > seq_call_cost)

        pseq->gain += mseq->cost - seq_call_cost;

    }

  /* No need to do further work if there is no gain.  */

  if (pseq->gain <= 0)

    return;

  /* Should not use registers live in the pattern sequence as link register.

   */

  clear_regs_live_in_seq (&linkregs, pseq->insn, pseq->abstracted_length);

  /* Determine whether pattern sequence contains a call_insn.  */

  hascall = 0;

  x = pseq->insn;

  for (i = 0; i < pseq->abstracted_length; i++)

    {

      if (CALL_P (x))

        {

          hascall = 1;

          break;

        }

      x = prev_insn_in_block (x);

    }

  /* Should not use a register as a link register if - it is a fixed

     register, or - the sequence contains a call insn and the register is a

     call used register, or - the register needs to be saved if used in a

     function but was not used before (since saving it can invalidate already

     computed frame pointer offsets), or - the register cannot be used as a

     base register.  */

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

    if (fixed_regs[i]

#ifdef REGNO_OK_FOR_INDIRECT_JUMP_P

        || (!REGNO_OK_FOR_INDIRECT_JUMP_P (i, Pmode))

#else

        || (!ok_for_base_p_1 (i, Pmode, MEM, SCRATCH))

        || (!reg_class_subset_p (REGNO_REG_CLASS (i),

                                 base_reg_class (VOIDmode, MEM, SCRATCH)))

#endif

        || (hascall && call_used_regs[i])

        || (!call_used_regs[i] && !regs_ever_live[i]))

      CLEAR_HARD_REG_BIT (linkregs, i);

  /* Find an appropriate register to be used as the link register.  */

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

    if (TEST_HARD_REG_BIT (linkregs, i))

      {

        pseq->link_reg = gen_rtx_REG (Pmode, i);

        break;

      }

  /* Abstraction is not possible if no link register is available, so set

     gain to 0.  */

  if (!pseq->link_reg)

    pseq->gain = 0;

}

/* Deallocates memory occupied by PSEQ and its matching seqs.  */

static void

free_pattern_seq (pattern_seq pseq)

{

  while (pseq->matching_seqs)

    {

      matching_seq mseq = pseq->matching_seqs;

      pseq->matching_seqs = mseq->next_matching_seq;

      free (mseq);

    }

  free (pseq);

}

/* Computes the gain for pattern sequences. Pattern sequences producing no gain

   are deleted. The pattern sequence with the biggest gain is moved to the first

   place of PATTERN_SEQS.  */

static void

recompute_gain (void)

{

  pattern_seq *pseq;

  int maxgain;

  maxgain = 0;

  for (pseq = &pattern_seqs; *pseq;)

    {

      if ((*pseq)->gain <= 0)

        recompute_gain_for_pattern_seq (*pseq);

      if ((*pseq)->gain > 0)

        {

          if ((*pseq)->gain > maxgain)