Subversion Repositories openrisc

/* Instruction scheduling pass.

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

   1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007

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

/* This pass implements list scheduling within basic blocks.  It is

   run twice: (1) after flow analysis, but before register allocation,

   and (2) after register allocation.

   The first run performs interblock scheduling, moving insns between

   different blocks in the same "region", and the second runs only

   basic block scheduling.

   Interblock motions performed are useful motions and speculative

   motions, including speculative loads.  Motions requiring code

   duplication are not supported.  The identification of motion type

   and the check for validity of speculative motions requires

   construction and analysis of the function's control flow graph.

   The main entry point for this pass is schedule_insns(), called for

   each function.  The work of the scheduler is organized in three

   levels: (1) function level: insns are subject to splitting,

   control-flow-graph is constructed, regions are computed (after

   reload, each region is of one block), (2) region level: control

   flow graph attributes required for interblock scheduling are

   computed (dominators, reachability, etc.), data dependences and

   priorities are computed, and (3) block level: insns in the block

   are actually scheduled.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "toplev.h"

#include "rtl.h"

#include "tm_p.h"

#include "hard-reg-set.h"

#include "regs.h"

#include "function.h"

#include "flags.h"

#include "insn-config.h"

#include "insn-attr.h"

#include "except.h"

#include "toplev.h"

#include "recog.h"

#include "cfglayout.h"

#include "params.h"

#include "sched-int.h"

#include "target.h"

#include "timevar.h"

#include "tree-pass.h"

/* Define when we want to do count REG_DEAD notes before and after scheduling

   for sanity checking.  We can't do that when conditional execution is used,

   as REG_DEAD exist only for unconditional deaths.  */

#if !defined (HAVE_conditional_execution) && defined (ENABLE_CHECKING)

#define CHECK_DEAD_NOTES 1

#else

#define CHECK_DEAD_NOTES 0

#endif

#ifdef INSN_SCHEDULING

/* Some accessor macros for h_i_d members only used within this file.  */

#define INSN_REF_COUNT(INSN)    (h_i_d[INSN_UID (INSN)].ref_count)

#define FED_BY_SPEC_LOAD(insn)  (h_i_d[INSN_UID (insn)].fed_by_spec_load)

#define IS_LOAD_INSN(insn)      (h_i_d[INSN_UID (insn)].is_load_insn)

/* nr_inter/spec counts interblock/speculative motion for the function.  */

static int nr_inter, nr_spec;

static int is_cfg_nonregular (void);

static bool sched_is_disabled_for_current_region_p (void);

/* A region is the main entity for interblock scheduling: insns

   are allowed to move between blocks in the same region, along

   control flow graph edges, in the 'up' direction.  */

typedef struct

{

  /* Number of extended basic blocks in region.  */

  int rgn_nr_blocks;

  /* cblocks in the region (actually index in rgn_bb_table).  */

  int rgn_blocks;

  /* Dependencies for this region are already computed.  Basically, indicates,

     that this is a recovery block.  */

  unsigned int dont_calc_deps : 1;

  /* This region has at least one non-trivial ebb.  */

  unsigned int has_real_ebb : 1;

}

region;

/* Number of regions in the procedure.  */

static int nr_regions;

/* Table of region descriptions.  */

static region *rgn_table;

/* Array of lists of regions' blocks.  */

static int *rgn_bb_table;

/* Topological order of blocks in the region (if b2 is reachable from

   b1, block_to_bb[b2] > block_to_bb[b1]).  Note: A basic block is

   always referred to by either block or b, while its topological

   order name (in the region) is referred to by bb.  */

static int *block_to_bb;

/* The number of the region containing a block.  */

static int *containing_rgn;

/* The minimum probability of reaching a source block so that it will be

   considered for speculative scheduling.  */

static int min_spec_prob;

#define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)

#define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)

#define RGN_DONT_CALC_DEPS(rgn) (rgn_table[rgn].dont_calc_deps)

#define RGN_HAS_REAL_EBB(rgn) (rgn_table[rgn].has_real_ebb)

#define BLOCK_TO_BB(block) (block_to_bb[block])

#define CONTAINING_RGN(block) (containing_rgn[block])

void debug_regions (void);

static void find_single_block_region (void);

static void find_rgns (void);

static void extend_rgns (int *, int *, sbitmap, int *);

static bool too_large (int, int *, int *);

extern void debug_live (int, int);

/* Blocks of the current region being scheduled.  */

static int current_nr_blocks;

static int current_blocks;

static int rgn_n_insns;

/* The mapping from ebb to block.  */

/* ebb_head [i] - is index in rgn_bb_table, while

   EBB_HEAD (i) - is basic block index.

   BASIC_BLOCK (EBB_HEAD (i)) - head of ebb.  */

#define BB_TO_BLOCK(ebb) (rgn_bb_table[ebb_head[ebb]])

#define EBB_FIRST_BB(ebb) BASIC_BLOCK (BB_TO_BLOCK (ebb))

#define EBB_LAST_BB(ebb) BASIC_BLOCK (rgn_bb_table[ebb_head[ebb + 1] - 1])

/* Target info declarations.

   The block currently being scheduled is referred to as the "target" block,

   while other blocks in the region from which insns can be moved to the

   target are called "source" blocks.  The candidate structure holds info

   about such sources: are they valid?  Speculative?  Etc.  */

typedef struct

{

  basic_block *first_member;

  int nr_members;

}

bblst;

typedef struct

{

  char is_valid;

  char is_speculative;

  int src_prob;

  bblst split_bbs;

  bblst update_bbs;

}

candidate;

static candidate *candidate_table;

/* A speculative motion requires checking live information on the path

   from 'source' to 'target'.  The split blocks are those to be checked.

   After a speculative motion, live information should be modified in

   the 'update' blocks.

   Lists of split and update blocks for each candidate of the current

   target are in array bblst_table.  */

static basic_block *bblst_table;

static int bblst_size, bblst_last;

#define IS_VALID(src) ( candidate_table[src].is_valid )

#define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )

#define SRC_PROB(src) ( candidate_table[src].src_prob )

/* The bb being currently scheduled.  */

static int target_bb;

/* List of edges.  */

typedef struct

{

  edge *first_member;

  int nr_members;

}

edgelst;

static edge *edgelst_table;

static int edgelst_last;

static void extract_edgelst (sbitmap, edgelst *);

/* Target info functions.  */

static void split_edges (int, int, edgelst *);

static void compute_trg_info (int);

void debug_candidate (int);

void debug_candidates (int);

/* Dominators array: dom[i] contains the sbitmap of dominators of

   bb i in the region.  */

static sbitmap *dom;

/* bb 0 is the only region entry.  */

#define IS_RGN_ENTRY(bb) (!bb)

/* Is bb_src dominated by bb_trg.  */

#define IS_DOMINATED(bb_src, bb_trg)                                 \

( TEST_BIT (dom[bb_src], bb_trg) )

/* Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is

   the probability of bb i relative to the region entry.  */

static int *prob;

/* Bit-set of edges, where bit i stands for edge i.  */

typedef sbitmap edgeset;

/* Number of edges in the region.  */

static int rgn_nr_edges;

/* Array of size rgn_nr_edges.  */

static edge *rgn_edges;

/* Mapping from each edge in the graph to its number in the rgn.  */

#define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux)

#define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr))

/* The split edges of a source bb is different for each target

   bb.  In order to compute this efficiently, the 'potential-split edges'

   are computed for each bb prior to scheduling a region.  This is actually

   the split edges of each bb relative to the region entry.

   pot_split[bb] is the set of potential split edges of bb.  */

static edgeset *pot_split;

/* For every bb, a set of its ancestor edges.  */

static edgeset *ancestor_edges;

/* Array of EBBs sizes.  Currently we can get a ebb only through

   splitting of currently scheduling block, therefore, we don't need

   ebb_head array for every region, its sufficient to hold it only

   for current one.  */

static int *ebb_head;

static void compute_dom_prob_ps (int);

#define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))

#define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))

#define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))

/* Speculative scheduling functions.  */

static int check_live_1 (int, rtx);

static void update_live_1 (int, rtx);

static int check_live (rtx, int);

static void update_live (rtx, int);

static void set_spec_fed (rtx);

static int is_pfree (rtx, int, int);

static int find_conditional_protection (rtx, int);

static int is_conditionally_protected (rtx, int, int);

static int is_prisky (rtx, int, int);

static int is_exception_free (rtx, int, int);

static bool sets_likely_spilled (rtx);

static void sets_likely_spilled_1 (rtx, rtx, void *);

static void add_branch_dependences (rtx, rtx);

static void compute_block_backward_dependences (int);

void debug_dependencies (void);

static void init_regions (void);

static void schedule_region (int);

static rtx concat_INSN_LIST (rtx, rtx);

static void concat_insn_mem_list (rtx, rtx, rtx *, rtx *);

static void propagate_deps (int, struct deps *);

static void free_pending_lists (void);

/* Functions for construction of the control flow graph.  */

/* Return 1 if control flow graph should not be constructed, 0 otherwise.

   We decide not to build the control flow graph if there is possibly more

   than one entry to the function, if computed branches exist, if we

   have nonlocal gotos, or if we have an unreachable loop.  */

static int

is_cfg_nonregular (void)

{

  basic_block b;

  rtx insn;

  /* If we have a label that could be the target of a nonlocal goto, then

     the cfg is not well structured.  */

  if (nonlocal_goto_handler_labels)

    return 1;

  /* If we have any forced labels, then the cfg is not well structured.  */

  if (forced_labels)

    return 1;

  /* If we have exception handlers, then we consider the cfg not well

     structured.  ?!?  We should be able to handle this now that flow.c

     computes an accurate cfg for EH.  */

  if (current_function_has_exception_handlers ())

    return 1;

  /* If we have non-jumping insns which refer to labels, then we consider

     the cfg not well structured.  */

  FOR_EACH_BB (b)

    FOR_BB_INSNS (b, insn)

      {

        /* Check for labels referred by non-jump insns.  */

        if (NONJUMP_INSN_P (insn) || CALL_P (insn))

          {

            rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);

            if (note

                && ! (JUMP_P (NEXT_INSN (insn))

                      && find_reg_note (NEXT_INSN (insn), REG_LABEL,

                                        XEXP (note, 0))))

              return 1;

          }

        /* If this function has a computed jump, then we consider the cfg

           not well structured.  */

        else if (JUMP_P (insn) && computed_jump_p (insn))

          return 1;

      }

  /* Unreachable loops with more than one basic block are detected

     during the DFS traversal in find_rgns.

     Unreachable loops with a single block are detected here.  This

     test is redundant with the one in find_rgns, but it's much

     cheaper to go ahead and catch the trivial case here.  */

  FOR_EACH_BB (b)

    {

      if (EDGE_COUNT (b->preds) == 0

          || (single_pred_p (b)

              && single_pred (b) == b))

        return 1;

    }

  /* All the tests passed.  Consider the cfg well structured.  */

  return 0;

}

/* Extract list of edges from a bitmap containing EDGE_TO_BIT bits.  */

static void

extract_edgelst (sbitmap set, edgelst *el)

{

  unsigned int i = 0;

  sbitmap_iterator sbi;

  /* edgelst table space is reused in each call to extract_edgelst.  */

  edgelst_last = 0;

  el->first_member = &edgelst_table[edgelst_last];

  el->nr_members = 0;

  /* Iterate over each word in the bitset.  */

  EXECUTE_IF_SET_IN_SBITMAP (set, 0, i, sbi)

    {

      edgelst_table[edgelst_last++] = rgn_edges[i];

      el->nr_members++;

    }

}

/* Functions for the construction of regions.  */

/* Print the regions, for debugging purposes.  Callable from debugger.  */

void

debug_regions (void)

{

  int rgn, bb;

  fprintf (sched_dump, "\n;;   ------------ REGIONS ----------\n\n");

  for (rgn = 0; rgn < nr_regions; rgn++)

    {

      fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn,

               rgn_table[rgn].rgn_nr_blocks);

      fprintf (sched_dump, ";;\tbb/block: ");

      /* We don't have ebb_head initialized yet, so we can't use

         BB_TO_BLOCK ().  */

      current_blocks = RGN_BLOCKS (rgn);

      for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)

        fprintf (sched_dump, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);

      fprintf (sched_dump, "\n\n");

    }

}

/* Build a single block region for each basic block in the function.

   This allows for using the same code for interblock and basic block

   scheduling.  */

static void

find_single_block_region (void)

{

  basic_block bb;

  nr_regions = 0;

  FOR_EACH_BB (bb)

    {

      rgn_bb_table[nr_regions] = bb->index;

      RGN_NR_BLOCKS (nr_regions) = 1;

      RGN_BLOCKS (nr_regions) = nr_regions;

      RGN_DONT_CALC_DEPS (nr_regions) = 0;

      RGN_HAS_REAL_EBB (nr_regions) = 0;

      CONTAINING_RGN (bb->index) = nr_regions;

      BLOCK_TO_BB (bb->index) = 0;

      nr_regions++;

    }

}

/* Update number of blocks and the estimate for number of insns

   in the region.  Return true if the region is "too large" for interblock

   scheduling (compile time considerations).  */

static bool

too_large (int block, int *num_bbs, int *num_insns)

{

  (*num_bbs)++;

  (*num_insns) += (INSN_LUID (BB_END (BASIC_BLOCK (block)))

                   - INSN_LUID (BB_HEAD (BASIC_BLOCK (block))));

  return ((*num_bbs > PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS))

          || (*num_insns > PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS)));

}

/* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]

   is still an inner loop.  Put in max_hdr[blk] the header of the most inner

   loop containing blk.  */

#define UPDATE_LOOP_RELATIONS(blk, hdr)         \

{                                               \

  if (max_hdr[blk] == -1)                       \

    max_hdr[blk] = hdr;                         \

  else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr])  \

    RESET_BIT (inner, hdr);                     \

  else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr])  \

    {                                           \

      RESET_BIT (inner,max_hdr[blk]);           \

      max_hdr[blk] = hdr;                       \

    }                                           \

}

/* Find regions for interblock scheduling.

   A region for scheduling can be:

     * A loop-free procedure, or

     * A reducible inner loop, or

     * A basic block not contained in any other region.

   ?!? In theory we could build other regions based on extended basic

   blocks or reverse extended basic blocks.  Is it worth the trouble?

   Loop blocks that form a region are put into the region's block list

   in topological order.

   This procedure stores its results into the following global (ick) variables

     * rgn_nr

     * rgn_table

     * rgn_bb_table

     * block_to_bb

     * containing region

   We use dominator relationships to avoid making regions out of non-reducible

   loops.

   This procedure needs to be converted to work on pred/succ lists instead

   of edge tables.  That would simplify it somewhat.  */

static void

find_rgns (void)

{

  int *max_hdr, *dfs_nr, *degree;

  char no_loops = 1;

  int node, child, loop_head, i, head, tail;

  int count = 0, sp, idx = 0;

  edge_iterator current_edge;

  edge_iterator *stack;

  int num_bbs, num_insns, unreachable;

  int too_large_failure;

  basic_block bb;

  /* Note if a block is a natural loop header.  */

  sbitmap header;

  /* Note if a block is a natural inner loop header.  */

  sbitmap inner;

  /* Note if a block is in the block queue.  */

  sbitmap in_queue;

  /* Note if a block is in the block queue.  */

  sbitmap in_stack;

  /* Perform a DFS traversal of the cfg.  Identify loop headers, inner loops

     and a mapping from block to its loop header (if the block is contained

     in a loop, else -1).

     Store results in HEADER, INNER, and MAX_HDR respectively, these will

     be used as inputs to the second traversal.

     STACK, SP and DFS_NR are only used during the first traversal.  */

  /* Allocate and initialize variables for the first traversal.  */

  max_hdr = XNEWVEC (int, last_basic_block);

  dfs_nr = XCNEWVEC (int, last_basic_block);

  stack = XNEWVEC (edge_iterator, n_edges);

  inner = sbitmap_alloc (last_basic_block);

  sbitmap_ones (inner);

  header = sbitmap_alloc (last_basic_block);

  sbitmap_zero (header);

  in_queue = sbitmap_alloc (last_basic_block);

  sbitmap_zero (in_queue);

  in_stack = sbitmap_alloc (last_basic_block);

  sbitmap_zero (in_stack);

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

    max_hdr[i] = -1;

  #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux)

  #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E)))

  /* DFS traversal to find inner loops in the cfg.  */

  current_edge = ei_start (single_succ (ENTRY_BLOCK_PTR)->succs);

  sp = -1;

  while (1)

    {

      if (EDGE_PASSED (current_edge))

        {

          /* We have reached a leaf node or a node that was already

             processed.  Pop edges off the stack until we find

             an edge that has not yet been processed.  */

          while (sp >= 0 && EDGE_PASSED (current_edge))

            {

              /* Pop entry off the stack.  */

              current_edge = stack[sp--];

              node = ei_edge (current_edge)->src->index;

              gcc_assert (node != ENTRY_BLOCK);

              child = ei_edge (current_edge)->dest->index;

              gcc_assert (child != EXIT_BLOCK);

              RESET_BIT (in_stack, child);

              if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))

                UPDATE_LOOP_RELATIONS (node, max_hdr[child]);

              ei_next (&current_edge);

            }

          /* See if have finished the DFS tree traversal.  */

          if (sp < 0 && EDGE_PASSED (current_edge))

            break;

          /* Nope, continue the traversal with the popped node.  */

          continue;

        }

      /* Process a node.  */

      node = ei_edge (current_edge)->src->index;

      gcc_assert (node != ENTRY_BLOCK);

      SET_BIT (in_stack, node);

      dfs_nr[node] = ++count;

      /* We don't traverse to the exit block.  */

      child = ei_edge (current_edge)->dest->index;

      if (child == EXIT_BLOCK)

        {

          SET_EDGE_PASSED (current_edge);

          ei_next (&current_edge);

          continue;

        }

      /* If the successor is in the stack, then we've found a loop.

         Mark the loop, if it is not a natural loop, then it will

         be rejected during the second traversal.  */

      if (TEST_BIT (in_stack, child))

        {

          no_loops = 0;

          SET_BIT (header, child);

          UPDATE_LOOP_RELATIONS (node, child);

          SET_EDGE_PASSED (current_edge);

          ei_next (&current_edge);

          continue;

        }

      /* If the child was already visited, then there is no need to visit

         it again.  Just update the loop relationships and restart

         with a new edge.  */

      if (dfs_nr[child])

        {

          if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))

            UPDATE_LOOP_RELATIONS (node, max_hdr[child]);

          SET_EDGE_PASSED (current_edge);

          ei_next (&current_edge);

          continue;

        }

      /* Push an entry on the stack and continue DFS traversal.  */

      stack[++sp] = current_edge;

      SET_EDGE_PASSED (current_edge);

      current_edge = ei_start (ei_edge (current_edge)->dest->succs);

    }

  /* Reset ->aux field used by EDGE_PASSED.  */

  FOR_ALL_BB (bb)

    {

      edge_iterator ei;

      edge e;

      FOR_EACH_EDGE (e, ei, bb->succs)

        e->aux = NULL;

    }

  /* Another check for unreachable blocks.  The earlier test in

     is_cfg_nonregular only finds unreachable blocks that do not

     form a loop.

     The DFS traversal will mark every block that is reachable from

     the entry node by placing a nonzero value in dfs_nr.  Thus if

     dfs_nr is zero for any block, then it must be unreachable.  */

  unreachable = 0;

  FOR_EACH_BB (bb)

    if (dfs_nr[bb->index] == 0)

      {

        unreachable = 1;

        break;

      }

  /* Gross.  To avoid wasting memory, the second pass uses the dfs_nr array

     to hold degree counts.  */

  degree = dfs_nr;

  FOR_EACH_BB (bb)

    degree[bb->index] = EDGE_COUNT (bb->preds);

  /* Do not perform region scheduling if there are any unreachable

     blocks.  */

  if (!unreachable)

    {

      int *queue, *degree1 = NULL;

      /* We use EXTENDED_RGN_HEADER as an addition to HEADER and put

         there basic blocks, which are forced to be region heads.

         This is done to try to assemble few smaller regions

         from a too_large region.  */

      sbitmap extended_rgn_header = NULL;

      bool extend_regions_p;

      if (no_loops)

        SET_BIT (header, 0);

      /* Second traversal:find reducible inner loops and topologically sort

         block of each region.  */

      queue = XNEWVEC (int, n_basic_blocks);

      extend_regions_p = PARAM_VALUE (PARAM_MAX_SCHED_EXTEND_REGIONS_ITERS) > 0;

      if (extend_regions_p)

        {

          degree1 = xmalloc (last_basic_block * sizeof (int));

          extended_rgn_header = sbitmap_alloc (last_basic_block);

          sbitmap_zero (extended_rgn_header);

        }

      /* Find blocks which are inner loop headers.  We still have non-reducible

         loops to consider at this point.  */

      FOR_EACH_BB (bb)

        {

          if (TEST_BIT (header, bb->index) && TEST_BIT (inner, bb->index))

            {

              edge e;

              edge_iterator ei;

              basic_block jbb;

              /* Now check that the loop is reducible.  We do this separate

                 from finding inner loops so that we do not find a reducible

                 loop which contains an inner non-reducible loop.

                 A simple way to find reducible/natural loops is to verify

                 that each block in the loop is dominated by the loop

                 header.

                 If there exists a block that is not dominated by the loop

                 header, then the block is reachable from outside the loop

                 and thus the loop is not a natural loop.  */

              FOR_EACH_BB (jbb)

                {

                  /* First identify blocks in the loop, except for the loop

                     entry block.  */

                  if (bb->index == max_hdr[jbb->index] && bb != jbb)

                    {

                      /* Now verify that the block is dominated by the loop

                         header.  */

                      if (!dominated_by_p (CDI_DOMINATORS, jbb, bb))

                        break;

                    }

                }

              /* If we exited the loop early, then I is the header of

                 a non-reducible loop and we should quit processing it

                 now.  */

              if (jbb != EXIT_BLOCK_PTR)

                continue;

              /* I is a header of an inner loop, or block 0 in a subroutine

                 with no loops at all.  */

              head = tail = -1;