Subversion Repositories openrisc

/* Instruction scheduling pass.

   Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,

   2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012

   Free Software Foundation, Inc.

   Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,

   and currently maintained by, Jim Wilson (wilson@cygnus.com)

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

/* Instruction scheduling pass.  This file, along with sched-deps.c,

   contains the generic parts.  The actual entry point is found for

   the normal instruction scheduling pass is found in sched-rgn.c.

   We compute insn priorities based on data dependencies.  Flow

   analysis only creates a fraction of the data-dependencies we must

   observe: namely, only those dependencies which the combiner can be

   expected to use.  For this pass, we must therefore create the

   remaining dependencies we need to observe: register dependencies,

   memory dependencies, dependencies to keep function calls in order,

   and the dependence between a conditional branch and the setting of

   condition codes are all dealt with here.

   The scheduler first traverses the data flow graph, starting with

   the last instruction, and proceeding to the first, assigning values

   to insn_priority as it goes.  This sorts the instructions

   topologically by data dependence.

   Once priorities have been established, we order the insns using

   list scheduling.  This works as follows: starting with a list of

   all the ready insns, and sorted according to priority number, we

   schedule the insn from the end of the list by placing its

   predecessors in the list according to their priority order.  We

   consider this insn scheduled by setting the pointer to the "end" of

   the list to point to the previous insn.  When an insn has no

   predecessors, we either queue it until sufficient time has elapsed

   or add it to the ready list.  As the instructions are scheduled or

   when stalls are introduced, the queue advances and dumps insns into

   the ready list.  When all insns down to the lowest priority have

   been scheduled, the critical path of the basic block has been made

   as short as possible.  The remaining insns are then scheduled in

   remaining slots.

   The following list shows the order in which we want to break ties

   among insns in the ready list:

   1.  choose insn with the longest path to end of bb, ties

   broken by

   2.  choose insn with least contribution to register pressure,

   ties broken by

   3.  prefer in-block upon interblock motion, ties broken by

   4.  prefer useful upon speculative motion, ties broken by

   5.  choose insn with largest control flow probability, ties

   broken by

   6.  choose insn with the least dependences upon the previously

   scheduled insn, or finally

   7   choose the insn which has the most insns dependent on it.

   8.  choose insn with lowest UID.

   Memory references complicate matters.  Only if we can be certain

   that memory references are not part of the data dependency graph

   (via true, anti, or output dependence), can we move operations past

   memory references.  To first approximation, reads can be done

   independently, while writes introduce dependencies.  Better

   approximations will yield fewer dependencies.

   Before reload, an extended analysis of interblock data dependences

   is required for interblock scheduling.  This is performed in

   compute_block_backward_dependences ().

   Dependencies set up by memory references are treated in exactly the

   same way as other dependencies, by using insn backward dependences

   INSN_BACK_DEPS.  INSN_BACK_DEPS are translated into forward dependences

   INSN_FORW_DEPS the purpose of forward list scheduling.

   Having optimized the critical path, we may have also unduly

   extended the lifetimes of some registers.  If an operation requires

   that constants be loaded into registers, it is certainly desirable

   to load those constants as early as necessary, but no earlier.

   I.e., it will not do to load up a bunch of registers at the

   beginning of a basic block only to use them at the end, if they

   could be loaded later, since this may result in excessive register

   utilization.

   Note that since branches are never in basic blocks, but only end

   basic blocks, this pass will not move branches.  But that is ok,

   since we can use GNU's delayed branch scheduling pass to take care

   of this case.

   Also note that no further optimizations based on algebraic

   identities are performed, so this pass would be a good one to

   perform instruction splitting, such as breaking up a multiply

   instruction into shifts and adds where that is profitable.

   Given the memory aliasing analysis that this pass should perform,

   it should be possible to remove redundant stores to memory, and to

   load values from registers instead of hitting memory.

   Before reload, speculative insns are moved only if a 'proof' exists

   that no exception will be caused by this, and if no live registers

   exist that inhibit the motion (live registers constraints are not

   represented by data dependence edges).

   This pass must update information that subsequent passes expect to

   be correct.  Namely: reg_n_refs, reg_n_sets, reg_n_deaths,

   reg_n_calls_crossed, and reg_live_length.  Also, BB_HEAD, BB_END.

   The information in the line number notes is carefully retained by

   this pass.  Notes that refer to the starting and ending of

   exception regions are also carefully retained by this pass.  All

   other NOTE insns are grouped in their same relative order at the

   beginning of basic blocks and regions that have been scheduled.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "diagnostic-core.h"

#include "hard-reg-set.h"

#include "rtl.h"

#include "tm_p.h"

#include "regs.h"

#include "function.h"

#include "flags.h"

#include "insn-config.h"

#include "insn-attr.h"

#include "except.h"

#include "recog.h"

#include "sched-int.h"

#include "target.h"

#include "common/common-target.h"

#include "output.h"

#include "params.h"

#include "vecprim.h"

#include "dbgcnt.h"

#include "cfgloop.h"

#include "ira.h"

#include "emit-rtl.h"  /* FIXME: Can go away once crtl is moved to rtl.h.  */

#include "hashtab.h"

#ifdef INSN_SCHEDULING

/* issue_rate is the number of insns that can be scheduled in the same

   machine cycle.  It can be defined in the config/mach/mach.h file,

   otherwise we set it to 1.  */

int issue_rate;

/* This can be set to true by a backend if the scheduler should not

   enable a DCE pass.  */

bool sched_no_dce;

/* The current initiation interval used when modulo scheduling.  */

static int modulo_ii;

/* The maximum number of stages we are prepared to handle.  */

static int modulo_max_stages;

/* The number of insns that exist in each iteration of the loop.  We use this

   to detect when we've scheduled all insns from the first iteration.  */

static int modulo_n_insns;

/* The current count of insns in the first iteration of the loop that have

   already been scheduled.  */

static int modulo_insns_scheduled;

/* The maximum uid of insns from the first iteration of the loop.  */

static int modulo_iter0_max_uid;

/* The number of times we should attempt to backtrack when modulo scheduling.

   Decreased each time we have to backtrack.  */

static int modulo_backtracks_left;

/* The stage in which the last insn from the original loop was

   scheduled.  */

static int modulo_last_stage;

/* sched-verbose controls the amount of debugging output the

   scheduler prints.  It is controlled by -fsched-verbose=N:

   N>0 and no -DSR : the output is directed to stderr.

   N>=10 will direct the printouts to stderr (regardless of -dSR).

   N=1: same as -dSR.

   N=2: bb's probabilities, detailed ready list info, unit/insn info.

   N=3: rtl at abort point, control-flow, regions info.

   N=5: dependences info.  */

int sched_verbose = 0;

/* Debugging file.  All printouts are sent to dump, which is always set,

   either to stderr, or to the dump listing file (-dRS).  */

FILE *sched_dump = 0;

/* This is a placeholder for the scheduler parameters common

   to all schedulers.  */

struct common_sched_info_def *common_sched_info;

#define INSN_TICK(INSN) (HID (INSN)->tick)

#define INSN_EXACT_TICK(INSN) (HID (INSN)->exact_tick)

#define INSN_TICK_ESTIMATE(INSN) (HID (INSN)->tick_estimate)

#define INTER_TICK(INSN) (HID (INSN)->inter_tick)

#define FEEDS_BACKTRACK_INSN(INSN) (HID (INSN)->feeds_backtrack_insn)

#define SHADOW_P(INSN) (HID (INSN)->shadow_p)

#define MUST_RECOMPUTE_SPEC_P(INSN) (HID (INSN)->must_recompute_spec)

/* If INSN_TICK of an instruction is equal to INVALID_TICK,

   then it should be recalculated from scratch.  */

#define INVALID_TICK (-(max_insn_queue_index + 1))

/* The minimal value of the INSN_TICK of an instruction.  */

#define MIN_TICK (-max_insn_queue_index)

/* List of important notes we must keep around.  This is a pointer to the

   last element in the list.  */

rtx note_list;

static struct spec_info_def spec_info_var;

/* Description of the speculative part of the scheduling.

   If NULL - no speculation.  */

spec_info_t spec_info = NULL;

/* True, if recovery block was added during scheduling of current block.

   Used to determine, if we need to fix INSN_TICKs.  */

static bool haifa_recovery_bb_recently_added_p;

/* True, if recovery block was added during this scheduling pass.

   Used to determine if we should have empty memory pools of dependencies

   after finishing current region.  */

bool haifa_recovery_bb_ever_added_p;

/* Counters of different types of speculative instructions.  */

static int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control;

/* Array used in {unlink, restore}_bb_notes.  */

static rtx *bb_header = 0;

/* Basic block after which recovery blocks will be created.  */

static basic_block before_recovery;

/* Basic block just before the EXIT_BLOCK and after recovery, if we have

   created it.  */

basic_block after_recovery;

/* FALSE if we add bb to another region, so we don't need to initialize it.  */

bool adding_bb_to_current_region_p = true;

/* Queues, etc.  */

/* An instruction is ready to be scheduled when all insns preceding it

   have already been scheduled.  It is important to ensure that all

   insns which use its result will not be executed until its result

   has been computed.  An insn is maintained in one of four structures:

   (P) the "Pending" set of insns which cannot be scheduled until

   their dependencies have been satisfied.

   (Q) the "Queued" set of insns that can be scheduled when sufficient

   time has passed.

   (R) the "Ready" list of unscheduled, uncommitted insns.

   (S) the "Scheduled" list of insns.

   Initially, all insns are either "Pending" or "Ready" depending on

   whether their dependencies are satisfied.

   Insns move from the "Ready" list to the "Scheduled" list as they

   are committed to the schedule.  As this occurs, the insns in the

   "Pending" list have their dependencies satisfied and move to either

   the "Ready" list or the "Queued" set depending on whether

   sufficient time has passed to make them ready.  As time passes,

   insns move from the "Queued" set to the "Ready" list.

   The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the

   unscheduled insns, i.e., those that are ready, queued, and pending.

   The "Queued" set (Q) is implemented by the variable `insn_queue'.

   The "Ready" list (R) is implemented by the variables `ready' and

   `n_ready'.

   The "Scheduled" list (S) is the new insn chain built by this pass.

   The transition (R->S) is implemented in the scheduling loop in

   `schedule_block' when the best insn to schedule is chosen.

   The transitions (P->R and P->Q) are implemented in `schedule_insn' as

   insns move from the ready list to the scheduled list.

   The transition (Q->R) is implemented in 'queue_to_insn' as time

   passes or stalls are introduced.  */

/* Implement a circular buffer to delay instructions until sufficient

   time has passed.  For the new pipeline description interface,

   MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less

   than maximal time of instruction execution computed by genattr.c on

   the base maximal time of functional unit reservations and getting a

   result.  This is the longest time an insn may be queued.  */

static rtx *insn_queue;

static int q_ptr = 0;

static int q_size = 0;

#define NEXT_Q(X) (((X)+1) & max_insn_queue_index)

#define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)

#define QUEUE_SCHEDULED (-3)

#define QUEUE_NOWHERE   (-2)

#define QUEUE_READY     (-1)

/* QUEUE_SCHEDULED - INSN is scheduled.

   QUEUE_NOWHERE   - INSN isn't scheduled yet and is neither in

   queue or ready list.

   QUEUE_READY     - INSN is in ready list.

   N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles.  */

#define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)

/* The following variable value refers for all current and future

   reservations of the processor units.  */

state_t curr_state;

/* The following variable value is size of memory representing all

   current and future reservations of the processor units.  */

size_t dfa_state_size;

/* The following array is used to find the best insn from ready when

   the automaton pipeline interface is used.  */

char *ready_try = NULL;

/* The ready list.  */

struct ready_list ready = {NULL, 0, 0, 0, 0};

/* The pointer to the ready list (to be removed).  */

static struct ready_list *readyp = &ready;

/* Scheduling clock.  */

static int clock_var;

/* Clock at which the previous instruction was issued.  */

static int last_clock_var;

/* Set to true if, when queuing a shadow insn, we discover that it would be

   scheduled too late.  */

static bool must_backtrack;

/* The following variable value is number of essential insns issued on

   the current cycle.  An insn is essential one if it changes the

   processors state.  */

int cycle_issued_insns;

/* This records the actual schedule.  It is built up during the main phase

   of schedule_block, and afterwards used to reorder the insns in the RTL.  */

static VEC(rtx, heap) *scheduled_insns;

static int may_trap_exp (const_rtx, int);

/* Nonzero iff the address is comprised from at most 1 register.  */

#define CONST_BASED_ADDRESS_P(x)                        \

  (REG_P (x)                                    \

   || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS   \

        || (GET_CODE (x) == LO_SUM))                    \

       && (CONSTANT_P (XEXP (x, 0))                      \

           || CONSTANT_P (XEXP (x, 1)))))

/* Returns a class that insn with GET_DEST(insn)=x may belong to,

   as found by analyzing insn's expression.  */

static int haifa_luid_for_non_insn (rtx x);

/* Haifa version of sched_info hooks common to all headers.  */

const struct common_sched_info_def haifa_common_sched_info =

  {

    NULL, /* fix_recovery_cfg */

    NULL, /* add_block */

    NULL, /* estimate_number_of_insns */

    haifa_luid_for_non_insn, /* luid_for_non_insn */

    SCHED_PASS_UNKNOWN /* sched_pass_id */

  };

/* Mapping from instruction UID to its Logical UID.  */

VEC (int, heap) *sched_luids = NULL;

/* Next LUID to assign to an instruction.  */

int sched_max_luid = 1;

/* Haifa Instruction Data.  */

VEC (haifa_insn_data_def, heap) *h_i_d = NULL;

void (* sched_init_only_bb) (basic_block, basic_block);

/* Split block function.  Different schedulers might use different functions

   to handle their internal data consistent.  */

basic_block (* sched_split_block) (basic_block, rtx);

/* Create empty basic block after the specified block.  */

basic_block (* sched_create_empty_bb) (basic_block);

static int

may_trap_exp (const_rtx x, int is_store)

{

  enum rtx_code code;

  if (x == 0)

    return TRAP_FREE;

  code = GET_CODE (x);

  if (is_store)

    {

      if (code == MEM && may_trap_p (x))

        return TRAP_RISKY;

      else

        return TRAP_FREE;

    }

  if (code == MEM)

    {

      /* The insn uses memory:  a volatile load.  */

      if (MEM_VOLATILE_P (x))

        return IRISKY;

      /* An exception-free load.  */

      if (!may_trap_p (x))

        return IFREE;

      /* A load with 1 base register, to be further checked.  */

      if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))

        return PFREE_CANDIDATE;

      /* No info on the load, to be further checked.  */

      return PRISKY_CANDIDATE;

    }

  else

    {

      const char *fmt;

      int i, insn_class = TRAP_FREE;

      /* Neither store nor load, check if it may cause a trap.  */

      if (may_trap_p (x))

        return TRAP_RISKY;

      /* Recursive step: walk the insn...  */

      fmt = GET_RTX_FORMAT (code);

      for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)

        {

          if (fmt[i] == 'e')

            {

              int tmp_class = may_trap_exp (XEXP (x, i), is_store);

              insn_class = WORST_CLASS (insn_class, tmp_class);

            }

          else if (fmt[i] == 'E')

            {

              int j;

              for (j = 0; j < XVECLEN (x, i); j++)

                {

                  int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);

                  insn_class = WORST_CLASS (insn_class, tmp_class);

                  if (insn_class == TRAP_RISKY || insn_class == IRISKY)

                    break;

                }

            }

          if (insn_class == TRAP_RISKY || insn_class == IRISKY)

            break;

        }

      return insn_class;

    }

}

/* Classifies rtx X of an insn for the purpose of verifying that X can be

   executed speculatively (and consequently the insn can be moved

   speculatively), by examining X, returning:

   TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).

   TRAP_FREE: non-load insn.

   IFREE: load from a globally safe location.

   IRISKY: volatile load.

   PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for

   being either PFREE or PRISKY.  */

static int

haifa_classify_rtx (const_rtx x)

{

  int tmp_class = TRAP_FREE;

  int insn_class = TRAP_FREE;

  enum rtx_code code;

  if (GET_CODE (x) == PARALLEL)

    {

      int i, len = XVECLEN (x, 0);

      for (i = len - 1; i >= 0; i--)

        {

          tmp_class = haifa_classify_rtx (XVECEXP (x, 0, i));

          insn_class = WORST_CLASS (insn_class, tmp_class);

          if (insn_class == TRAP_RISKY || insn_class == IRISKY)

            break;

        }

    }

  else

    {

      code = GET_CODE (x);

      switch (code)

        {

        case CLOBBER:

          /* Test if it is a 'store'.  */

          tmp_class = may_trap_exp (XEXP (x, 0), 1);

          break;

        case SET:

          /* Test if it is a store.  */

          tmp_class = may_trap_exp (SET_DEST (x), 1);

          if (tmp_class == TRAP_RISKY)

            break;

          /* Test if it is a load.  */

          tmp_class =

            WORST_CLASS (tmp_class,

                         may_trap_exp (SET_SRC (x), 0));

          break;

        case COND_EXEC:

          tmp_class = haifa_classify_rtx (COND_EXEC_CODE (x));

          if (tmp_class == TRAP_RISKY)

            break;

          tmp_class = WORST_CLASS (tmp_class,

                                   may_trap_exp (COND_EXEC_TEST (x), 0));

          break;

        case TRAP_IF:

          tmp_class = TRAP_RISKY;

          break;

        default:;

        }

      insn_class = tmp_class;

    }

  return insn_class;

}

int

haifa_classify_insn (const_rtx insn)

{

  return haifa_classify_rtx (PATTERN (insn));

}

/* After the scheduler initialization function has been called, this function

   can be called to enable modulo scheduling.  II is the initiation interval

   we should use, it affects the delays for delay_pairs that were recorded as

   separated by a given number of stages.

   MAX_STAGES provides us with a limit

   after which we give up scheduling; the caller must have unrolled at least

   as many copies of the loop body and recorded delay_pairs for them.

   INSNS is the number of real (non-debug) insns in one iteration of

   the loop.  MAX_UID can be used to test whether an insn belongs to

   the first iteration of the loop; all of them have a uid lower than

   MAX_UID.  */

void

set_modulo_params (int ii, int max_stages, int insns, int max_uid)

{

  modulo_ii = ii;

  modulo_max_stages = max_stages;

  modulo_n_insns = insns;

  modulo_iter0_max_uid = max_uid;

  modulo_backtracks_left = PARAM_VALUE (PARAM_MAX_MODULO_BACKTRACK_ATTEMPTS);

}

/* A structure to record a pair of insns where the first one is a real

   insn that has delay slots, and the second is its delayed shadow.

   I1 is scheduled normally and will emit an assembly instruction,

   while I2 describes the side effect that takes place at the

   transition between cycles CYCLES and (CYCLES + 1) after I1.  */

struct delay_pair

{

  struct delay_pair *next_same_i1;

  rtx i1, i2;

  int cycles;

  /* When doing modulo scheduling, we a delay_pair can also be used to

     show that I1 and I2 are the same insn in a different stage.  If that

     is the case, STAGES will be nonzero.  */

  int stages;

};

/* Two hash tables to record delay_pairs, one indexed by I1 and the other

   indexed by I2.  */

static htab_t delay_htab;

static htab_t delay_htab_i2;

/* Called through htab_traverse.  Walk the hashtable using I2 as

   index, and delete all elements involving an UID higher than

   that pointed to by *DATA.  */

static int

htab_i2_traverse (void **slot, void *data)

{

  int maxuid = *(int *)data;

  struct delay_pair *p = *(struct delay_pair **)slot;

  if (INSN_UID (p->i2) >= maxuid || INSN_UID (p->i1) >= maxuid)

    {

      htab_clear_slot (delay_htab_i2, slot);

    }

  return 1;

}

/* Called through htab_traverse.  Walk the hashtable using I2 as

   index, and delete all elements involving an UID higher than

   that pointed to by *DATA.  */

static int

htab_i1_traverse (void **slot, void *data)

{

  int maxuid = *(int *)data;

  struct delay_pair **pslot = (struct delay_pair **)slot;

  struct delay_pair *p, *first, **pprev;

  if (INSN_UID ((*pslot)->i1) >= maxuid)

    {

      htab_clear_slot (delay_htab, slot);

      return 1;

    }

  pprev = &first;

  for (p = *pslot; p; p = p->next_same_i1)

    {

      if (INSN_UID (p->i2) < maxuid)

        {

          *pprev = p;

          pprev = &p->next_same_i1;

        }

    }

  *pprev = NULL;

  if (first == NULL)

    htab_clear_slot (delay_htab, slot);

  else

    *pslot = first;

  return 1;

}

/* Discard all delay pairs which involve an insn with an UID higher

   than MAX_UID.  */

void

discard_delay_pairs_above (int max_uid)

{

  htab_traverse (delay_htab, htab_i1_traverse, &max_uid);

  htab_traverse (delay_htab_i2, htab_i2_traverse, &max_uid);

}

/* Returns a hash value for X (which really is a delay_pair), based on

   hashing just I1.  */

static hashval_t

delay_hash_i1 (const void *x)

{

  return htab_hash_pointer (((const struct delay_pair *) x)->i1);

}

/* Returns a hash value for X (which really is a delay_pair), based on

   hashing just I2.  */

static hashval_t

delay_hash_i2 (const void *x)

{

  return htab_hash_pointer (((const struct delay_pair *) x)->i2);

}

/* Return nonzero if I1 of pair X is the same as that of pair Y.  */

static int

delay_i1_eq (const void *x, const void *y)

{

  return ((const struct delay_pair *) x)->i1 == y;

}

/* Return nonzero if I2 of pair X is the same as that of pair Y.  */

static int

delay_i2_eq (const void *x, const void *y)

{

  return ((const struct delay_pair *) x)->i2 == y;

}

/* This function can be called by a port just before it starts the final

   scheduling pass.  It records the fact that an instruction with delay

   slots has been split into two insns, I1 and I2.  The first one will be

   scheduled normally and initiates the operation.  The second one is a

   shadow which must follow a specific number of cycles after I1; its only

   purpose is to show the side effect that occurs at that cycle in the RTL.

   If a JUMP_INSN or a CALL_INSN has been split, I1 should be a normal INSN,

   while I2 retains the original insn type.

   There are two ways in which the number of cycles can be specified,

   involving the CYCLES and STAGES arguments to this function.  If STAGES

   is zero, we just use the value of CYCLES.  Otherwise, STAGES is a factor

   which is multiplied by MODULO_II to give the number of cycles.  This is

   only useful if the caller also calls set_modulo_params to enable modulo

   scheduling.  */

void

record_delay_slot_pair (rtx i1, rtx i2, int cycles, int stages)

{

  struct delay_pair *p = XNEW (struct delay_pair);

  struct delay_pair **slot;

  p->i1 = i1;

  p->i2 = i2;

  p->cycles = cycles;

  p->stages = stages;

  if (!delay_htab)

    {

      delay_htab = htab_create (10, delay_hash_i1, delay_i1_eq, NULL);

      delay_htab_i2 = htab_create (10, delay_hash_i2, delay_i2_eq, free);

    }

  slot = ((struct delay_pair **)

          htab_find_slot_with_hash (delay_htab, i1, htab_hash_pointer (i1),

                                    INSERT));

  p->next_same_i1 = *slot;

  *slot = p;

  slot = ((struct delay_pair **)

          htab_find_slot_with_hash (delay_htab_i2, i2, htab_hash_pointer (i2),

                                    INSERT));

  *slot = p;

}

/* Examine the delay pair hashtable to see if INSN is a shadow for another,

   and return the other insn if so.  Return NULL otherwise.  */

rtx

real_insn_for_shadow (rtx insn)

{

  struct delay_pair *pair;

  if (delay_htab == NULL)

    return NULL_RTX;

  pair

    = (struct delay_pair *)htab_find_with_hash (delay_htab_i2, insn,

                                                htab_hash_pointer (insn));

  if (!pair || pair->stages > 0)

    return NULL_RTX;

  return pair->i1;

}

/* For a pair P of insns, return the fixed distance in cycles from the first

   insn after which the second must be scheduled.  */

static int

pair_delay (struct delay_pair *p)

{

  if (p->stages == 0)

    return p->cycles;

  else

    return p->stages * modulo_ii;

}

/* Given an insn INSN, add a dependence on its delayed shadow if it

   has one.  Also try to find situations where shadows depend on each other

   and add dependencies to the real insns to limit the amount of backtracking

   needed.  */

void

add_delay_dependencies (rtx insn)

{

  struct delay_pair *pair;

  sd_iterator_def sd_it;

  dep_t dep;

  if (!delay_htab)

    return;

  pair

    = (struct delay_pair *)htab_find_with_hash (delay_htab_i2, insn,

                                                htab_hash_pointer (insn));

  if (!pair)

    return;

  add_dependence (insn, pair->i1, REG_DEP_ANTI);

  if (pair->stages)

    return;

  FOR_EACH_DEP (pair->i2, SD_LIST_BACK, sd_it, dep)

    {

      rtx pro = DEP_PRO (dep);

      struct delay_pair *other_pair