This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH,RFC] CSE path following on basic blocks


Hi,

This is the patch as it looks right now to make CSE path following
work on a trace of basic blocks isntead of on a list of insns.  I
need to clean it up a bit more and write a ChangeLog, but I'm looking
for early comments now.  So start shooting... :-)

Gr.
Steven

Index: cse.c
===================================================================
*** cse.c	(revision 119209)
--- cse.c	(working copy)
*************** Software Foundation, 51 Franklin Street,
*** 29,34 ****
--- 29,35 ----
  #include "hard-reg-set.h"
  #include "regs.h"
  #include "basic-block.h"
+ #include "cfglayout.h"
  #include "flags.h"
  #include "real.h"
  #include "insn-config.h"
*************** static unsigned int cse_reg_info_table_s
*** 336,346 ****
  static unsigned int cse_reg_info_table_first_uninitialized;
  
  /* The timestamp at the beginning of the current run of
!    cse_basic_block.  We increment this variable at the beginning of
!    the current run of cse_basic_block.  The timestamp field of a
     cse_reg_info entry matches the value of this variable if and only
     if the entry has been initialized during the current run of
!    cse_basic_block.  */
  static unsigned int cse_reg_info_timestamp;
  
  /* A HARD_REG_SET containing all the hard registers for which there is
--- 337,347 ----
  static unsigned int cse_reg_info_table_first_uninitialized;
  
  /* The timestamp at the beginning of the current run of
!    cse_extended_basic_block.  We increment this variable at the beginning of
!    the current run of cse_extended_basic_block.  The timestamp field of a
     cse_reg_info entry matches the value of this variable if and only
     if the entry has been initialized during the current run of
!    cse_extended_basic_block.  */
  static unsigned int cse_reg_info_timestamp;
  
  /* A HARD_REG_SET containing all the hard registers for which there is
*************** static struct table_elt *free_element_ch
*** 536,542 ****
  static int constant_pool_entries_cost;
  static int constant_pool_entries_regcost;
  
! /* This data describes a block that will be processed by cse_basic_block.  */
  
  struct cse_basic_block_data
  {
--- 537,544 ----
  static int constant_pool_entries_cost;
  static int constant_pool_entries_regcost;
  
! /* This data describes a block that will be processed by
!    cse_extended_basic_block.  */
  
  struct cse_basic_block_data
  {
*************** struct cse_basic_block_data
*** 546,565 ****
    int high_cuid;
    /* Total number of SETs in block.  */
    int nsets;
-   /* Last insn in the block.  */
-   rtx last;
    /* Size of current branch path, if any.  */
    int path_size;
!   /* Current branch path, indicating which branches will be taken.  */
    struct branch_path
      {
!       /* The branch insn.  */
!       rtx branch;
!       /* Whether it should be taken or not.  */
!       enum taken {PATH_TAKEN, PATH_NOT_TAKEN} status;
      } *path;
  };
  
  static bool fixed_base_plus_p (rtx x);
  static int notreg_cost (rtx, enum rtx_code);
  static int approx_reg_cost_1 (rtx *, void *);
--- 548,567 ----
    int high_cuid;
    /* Total number of SETs in block.  */
    int nsets;
    /* Size of current branch path, if any.  */
    int path_size;
!   /* Current path, indicating which basic_blocks will be processed.  */
    struct branch_path
      {
!       /* The basic block for this path entry.  */
!       basic_block bb;
      } *path;
  };
  
+ /* A simple bitmap to track which basic blocks have been visited
+    already as part of an already processed extended basic block.  */
+ sbitmap cse_visited_basic_blocks;
+ 
  static bool fixed_base_plus_p (rtx x);
  static int notreg_cost (rtx, enum rtx_code);
  static int approx_reg_cost_1 (rtx *, void *);
*************** static void record_jump_equiv (rtx, bool
*** 602,612 ****
  static void record_jump_cond (enum rtx_code, enum machine_mode, rtx, rtx,
  			      int);
  static void cse_insn (rtx, rtx);
! static void cse_end_of_basic_block (rtx, struct cse_basic_block_data *,
! 				    int);
  static void invalidate_from_clobbers (rtx);
  static rtx cse_process_notes (rtx, rtx);
! static rtx cse_basic_block (rtx, rtx, struct branch_path *);
  static void count_reg_usage (rtx, int *, rtx, int);
  static int check_for_label_ref (rtx *, void *);
  extern void dump_class (struct table_elt*);
--- 604,613 ----
  static void record_jump_cond (enum rtx_code, enum machine_mode, rtx, rtx,
  			      int);
  static void cse_insn (rtx, rtx);
! static void cse_prescan_path (struct cse_basic_block_data *);
  static void invalidate_from_clobbers (rtx);
  static rtx cse_process_notes (rtx, rtx);
! static void cse_extended_basic_block (struct cse_basic_block_data *);
  static void count_reg_usage (rtx, int *, rtx, int);
  static int check_for_label_ref (rtx *, void *);
  extern void dump_class (struct table_elt*);
*************** cse_insn (rtx insn, rtx libcall_insn)
*** 5317,5322 ****
--- 5318,5332 ----
        && MEM_VOLATILE_P (PATTERN (insn)))
      flush_hash_table ();
  
+   /* Don't cse over a call to setjmp; on some machines (eg VAX)
+      the regs restored by the longjmp come from a later time
+      than the setjmp.  */
+   if (CALL_P (insn) && find_reg_note (insn, REG_SETJMP, NULL))
+     {
+       flush_hash_table ();
+       goto done;
+     }
+ 
    /* Make sure registers mentioned in destinations
       are safe for use in an expression to be inserted.
       This removes from the hash table
*************** cse_insn (rtx insn, rtx libcall_insn)
*** 5578,5592 ****
        if ((src_ent->first_reg == REGNO (SET_DEST (sets[0].rtl)))
  	  && ! find_reg_note (insn, REG_RETVAL, NULL_RTX))
  	{
- 	  rtx prev = insn;
  	  /* Scan for the previous nonnote insn, but stop at a basic
  	     block boundary.  */
  	  do
  	    {
  	      prev = PREV_INSN (prev);
  	    }
! 	  while (prev && NOTE_P (prev)
! 		 && NOTE_LINE_NUMBER (prev) != NOTE_INSN_BASIC_BLOCK);
  
  	  /* Do not swap the registers around if the previous instruction
  	     attaches a REG_EQUIV note to REG1.
--- 5588,5602 ----
        if ((src_ent->first_reg == REGNO (SET_DEST (sets[0].rtl)))
  	  && ! find_reg_note (insn, REG_RETVAL, NULL_RTX))
  	{
  	  /* Scan for the previous nonnote insn, but stop at a basic
  	     block boundary.  */
+ 	  rtx prev = insn;
+ 	  rtx bb_head = BB_HEAD (BLOCK_FOR_INSN (insn));
  	  do
  	    {
  	      prev = PREV_INSN (prev);
  	    }
! 	  while (prev != bb_head);
  
  	  /* Do not swap the registers around if the previous instruction
  	     attaches a REG_EQUIV note to REG1.
*************** cse_insn (rtx insn, rtx libcall_insn)
*** 5599,5606 ****
  	     This section previously turned the REG_EQUIV into a REG_EQUAL
  	     note.  We cannot do that because REG_EQUIV may provide an
  	     uninitialized stack slot when REG_PARM_STACK_SPACE is used.  */
! 
! 	  if (prev != 0 && NONJUMP_INSN_P (prev)
  	      && GET_CODE (PATTERN (prev)) == SET
  	      && SET_DEST (PATTERN (prev)) == SET_SRC (sets[0].rtl)
  	      && ! find_reg_note (prev, REG_EQUIV, NULL_RTX))
--- 5609,5616 ----
  	     This section previously turned the REG_EQUIV into a REG_EQUAL
  	     note.  We cannot do that because REG_EQUIV may provide an
  	     uninitialized stack slot when REG_PARM_STACK_SPACE is used.  */
! 	  gcc_assert (prev);
! 	  if (NONJUMP_INSN_P (prev)
  	      && GET_CODE (PATTERN (prev)) == SET
  	      && SET_DEST (PATTERN (prev)) == SET_SRC (sets[0].rtl)
  	      && ! find_reg_note (prev, REG_EQUIV, NULL_RTX))
*************** cse_insn (rtx insn, rtx libcall_insn)
*** 5627,5638 ****
  	}
      }
  
!   /* If this is a conditional jump insn, record any known equivalences due to
!      the condition being tested.  */
! 
!   if (n_sets == 1 && any_condjump_p (insn))
!     record_jump_equiv (insn, false);
! 
  #ifdef HAVE_cc0
    /* If the previous insn set CC0 and this insn no longer references CC0,
       delete the previous insn.  Here we use the fact that nothing expects CC0
--- 5637,5643 ----
  	}
      }
  
! done:
  #ifdef HAVE_cc0
    /* If the previous insn set CC0 and this insn no longer references CC0,
       delete the previous insn.  Here we use the fact that nothing expects CC0
*************** cse_insn (rtx insn, rtx libcall_insn)
*** 5647,5652 ****
--- 5652,5659 ----
    prev_insn_cc0_mode = this_insn_cc0_mode;
    prev_insn = insn;
  #endif
+ 
+   return;
  }
  
  /* Remove from the hash table all expressions that reference memory.  */
*************** cse_process_notes (rtx x, rtx object)
*** 5796,6218 ****
    return x;
  }
  
! /* Find the end of INSN's basic block and return its range,
!    the total number of SETs in all the insns of the block, the last insn of the
!    block, and the branch path.
! 
!    The branch path indicates which branches should be followed.  If a nonzero
!    path size is specified, the block should be rescanned and a different set
!    of branches will be taken.  The branch path is only used if
!    FLAG_CSE_FOLLOW_JUMPS is nonzero.
! 
!    DATA is a pointer to a struct cse_basic_block_data, defined below, that is
!    used to describe the block.  It is filled in with the information about
!    the current block.  The incoming structure's branch path, if any, is used
!    to construct the output branch path.  */
  
! static void
! cse_end_of_basic_block (rtx insn, struct cse_basic_block_data *data,
! 			int follow_jumps)
! {
!   rtx p = insn, q;
!   int nsets = 0;
!   int low_cuid = INSN_CUID (insn), high_cuid = INSN_CUID (insn);
!   rtx next = INSN_P (insn) ? insn : next_real_insn (insn);
!   int path_size = data->path_size;
!   int path_entry = 0;
!   int i;
  
!   /* Update the previous branch path, if any.  If the last branch was
!      previously PATH_TAKEN, mark it PATH_NOT_TAKEN.
!      If it was previously PATH_NOT_TAKEN,
!      shorten the path by one and look at the previous branch.  We know that
!      at least one branch must have been taken if PATH_SIZE is nonzero.  */
!   while (path_size > 0)
!     {
!       if (data->path[path_size - 1].status != PATH_NOT_TAKEN)
! 	{
! 	  data->path[path_size - 1].status = PATH_NOT_TAKEN;
! 	  break;
! 	}
!       else
! 	path_size--;
!     }
  
!   /* If the first instruction is marked with QImode, that means we've
!      already processed this block.  Our caller will look at DATA->LAST
!      to figure out where to go next.  We want to return the next block
!      in the instruction stream, not some branched-to block somewhere
!      else.  We accomplish this by pretending our called forbid us to
!      follow jumps.  */
!   if (GET_MODE (insn) == QImode)
!     follow_jumps = 0;
! 
!   /* Scan to end of this basic block.  */
!   while (p && !LABEL_P (p))
!     {
!       /* Don't cse over a call to setjmp; on some machines (eg VAX)
! 	 the regs restored by the longjmp come from
! 	 a later time than the setjmp.  */
!       if (PREV_INSN (p) && CALL_P (PREV_INSN (p))
! 	  && find_reg_note (PREV_INSN (p), REG_SETJMP, NULL))
! 	break;
  
!       /* A PARALLEL can have lots of SETs in it,
! 	 especially if it is really an ASM_OPERANDS.  */
!       if (INSN_P (p) && GET_CODE (PATTERN (p)) == PARALLEL)
! 	nsets += XVECLEN (PATTERN (p), 0);
!       else if (!NOTE_P (p))
! 	nsets += 1;
  
!       /* Ignore insns made by CSE; they cannot affect the boundaries of
! 	 the basic block.  */
  
!       if (INSN_UID (p) <= max_uid && INSN_CUID (p) > high_cuid)
! 	high_cuid = INSN_CUID (p);
!       if (INSN_UID (p) <= max_uid && INSN_CUID (p) < low_cuid)
! 	low_cuid = INSN_CUID (p);
! 
!       /* See if this insn is in our branch path.  If it is and we are to
! 	 take it, do so.  */
!       if (path_entry < path_size && data->path[path_entry].branch == p)
! 	{
! 	  if (data->path[path_entry].status != PATH_NOT_TAKEN)
! 	    p = JUMP_LABEL (p);
! 
! 	  /* Point to next entry in path, if any.  */
! 	  path_entry++;
! 	}
! 
!       /* If this is a conditional jump, we can follow it if -fcse-follow-jumps
! 	 was specified, we haven't reached our maximum path length, there are
! 	 insns following the target of the jump, this is the only use of the
! 	 jump label, and the target label is preceded by a BARRIER.  */
!       else if (follow_jumps
! 	       && path_size < PARAM_VALUE (PARAM_MAX_CSE_PATH_LENGTH) - 1
! 	       && JUMP_P (p)
! 	       && GET_CODE (PATTERN (p)) == SET
! 	       && GET_CODE (SET_SRC (PATTERN (p))) == IF_THEN_ELSE
! 	       && JUMP_LABEL (p) != 0
! 	       && LABEL_NUSES (JUMP_LABEL (p)) == 1
! 	       && NEXT_INSN (JUMP_LABEL (p)) != 0)
! 	{
! 	  for (q = PREV_INSN (JUMP_LABEL (p)); q; q = PREV_INSN (q))
! 	    if ((!NOTE_P (q)
! 		 || (PREV_INSN (q) && CALL_P (PREV_INSN (q))
! 		     && find_reg_note (PREV_INSN (q), REG_SETJMP, NULL)))
! 		&& (!LABEL_P (q) || LABEL_NUSES (q) != 0))
! 	      break;
  
! 	  /* If we ran into a BARRIER, this code is an extension of the
! 	     basic block when the branch is taken.  */
! 	  if (follow_jumps && q != 0 && BARRIER_P (q))
! 	    {
! 	      /* Don't allow ourself to keep walking around an
! 		 always-executed loop.  */
! 	      if (next_real_insn (q) == next)
  		{
! 		  p = NEXT_INSN (p);
! 		  continue;
  		}
  
! 	      /* Similarly, don't put a branch in our path more than once.  */
! 	      for (i = 0; i < path_entry; i++)
! 		if (data->path[i].branch == p)
! 		  break;
  
! 	      if (i != path_entry)
! 		break;
  
! 	      data->path[path_entry].branch = p;
! 	      data->path[path_entry++].status = PATH_TAKEN;
  
! 	      /* This branch now ends our path.  It was possible that we
! 		 didn't see this branch the last time around (when the
! 		 insn in front of the target was a JUMP_INSN that was
! 		 turned into a no-op).  */
! 	      path_size = path_entry;
  
! 	      p = JUMP_LABEL (p);
! 	      /* Mark block so we won't scan it again later.  */
! 	      PUT_MODE (NEXT_INSN (p), QImode);
  	    }
  	}
-       p = NEXT_INSN (p);
      }
  
!   data->low_cuid = low_cuid;
!   data->high_cuid = high_cuid;
!   data->nsets = nsets;
!   data->last = p;
! 
!   /* If all jumps in the path are not taken, set our path length to zero
!      so a rescan won't be done.  */
!   for (i = path_size - 1; i >= 0; i--)
!     if (data->path[i].status != PATH_NOT_TAKEN)
!       break;
! 
!   if (i == -1)
!     data->path_size = 0;
!   else
!     data->path_size = path_size;
! 
!   /* End the current branch path.  */
!   data->path[path_size].branch = 0;
  }
  
! /* Perform cse on the instructions of a function.
!    F is the first instruction.
!    NREGS is one plus the highest pseudo-reg number used in the instruction.
  
!    Returns 1 if jump_optimize should be redone due to simplifications
!    in conditional jump instructions.  */
! 
! int
! cse_main (rtx f, int nregs)
  {
!   struct cse_basic_block_data val;
!   rtx insn = f;
!   int i;
! 
!   init_cse_reg_info (nregs);
! 
!   val.path = XNEWVEC (struct branch_path, PARAM_VALUE (PARAM_MAX_CSE_PATH_LENGTH));
! 
!   cse_jumps_altered = 0;
!   recorded_label_ref = 0;
!   constant_pool_entries_cost = 0;
!   constant_pool_entries_regcost = 0;
!   val.path_size = 0;
!   rtl_hooks = cse_rtl_hooks;
! 
!   init_recog ();
!   init_alias_analysis ();
  
!   reg_eqv_table = XNEWVEC (struct reg_eqv_elem, nregs);
! 
!   /* Find the largest uid.  */
  
!   max_uid = get_max_uid ();
!   uid_cuid = XCNEWVEC (int, max_uid + 1);
  
!   /* Compute the mapping from uids to cuids.
!      CUIDs are numbers assigned to insns, like uids,
!      except that cuids increase monotonically through the code.  */
  
!   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
!     INSN_CUID (insn) = ++i;
  
!   /* Loop over basic blocks.
!      Compute the maximum number of qty's needed for each basic block
!      (which is 2 for each SET).  */
!   insn = f;
!   while (insn)
!     {
!       cse_end_of_basic_block (insn, &val, flag_cse_follow_jumps);
! 
!       /* If this basic block was already processed or has no sets, skip it.  */
!       if (val.nsets == 0 || GET_MODE (insn) == QImode)
! 	{
! 	  PUT_MODE (insn, VOIDmode);
! 	  insn = (val.last ? NEXT_INSN (val.last) : 0);
! 	  val.path_size = 0;
! 	  continue;
! 	}
  
!       cse_basic_block_start = val.low_cuid;
!       cse_basic_block_end = val.high_cuid;
!       max_qty = val.nsets * 2;
! 
!       if (dump_file)
! 	fprintf (dump_file, ";; Processing block from %d to %d, %d sets.\n",
! 		 INSN_UID (insn), val.last ? INSN_UID (val.last) : 0,
! 		 val.nsets);
! 
!       /* Make MAX_QTY bigger to give us room to optimize
! 	 past the end of this basic block, if that should prove useful.  */
!       if (max_qty < 500)
! 	max_qty = 500;
! 
!       /* If this basic block is being extended by following certain jumps,
!          (see `cse_end_of_basic_block'), we reprocess the code from the start.
!          Otherwise, we start after this basic block.  */
!       if (val.path_size > 0)
! 	cse_basic_block (insn, val.last, val.path);
!       else
  	{
! 	  int old_cse_jumps_altered = cse_jumps_altered;
! 	  rtx temp;
  
! 	  /* When cse changes a conditional jump to an unconditional
! 	     jump, we want to reprocess the block, since it will give
! 	     us a new branch path to investigate.  */
! 	  cse_jumps_altered = 0;
! 	  temp = cse_basic_block (insn, val.last, val.path);
! 	  if (cse_jumps_altered == 0 || flag_cse_follow_jumps)
! 	    insn = temp;
  
! 	  cse_jumps_altered |= old_cse_jumps_altered;
  	}
      }
  
!   /* Clean up.  */
!   end_alias_analysis ();
!   free (uid_cuid);
!   free (reg_eqv_table);
!   free (val.path);
!   rtl_hooks = general_rtl_hooks;
! 
!   return cse_jumps_altered || recorded_label_ref;
  }
  
! /* Process a single basic block.  FROM and TO and the limits of the basic
!    block.  NEXT_BRANCH points to the branch path when following jumps or
!    a null path when not following jumps.  */
! 
! static rtx
! cse_basic_block (rtx from, rtx to, struct branch_path *next_branch)
  {
!   rtx insn;
!   int to_usage = 0;
!   rtx libcall_insn = NULL_RTX;
    int num_insns = 0;
-   int no_conflict = 0;
  
    /* Allocate the space needed by qty_table.  */
    qty_table = XNEWVEC (struct qty_table_elem, max_qty);
  
    new_basic_block ();
  
!   /* TO might be a label.  If so, protect it from being deleted.  */
!   if (to != 0 && LABEL_P (to))
!     ++LABEL_NUSES (to);
  
!   for (insn = from; insn != to; insn = NEXT_INSN (insn))
!     {
!       enum rtx_code code = GET_CODE (insn);
  
!       /* If we have processed 1,000 insns, flush the hash table to
! 	 avoid extreme quadratic behavior.  We must not include NOTEs
! 	 in the count since there may be more of them when generating
! 	 debugging information.  If we clear the table at different
! 	 times, code generated with -g -O might be different than code
! 	 generated with -O but not -g.
  
! 	 ??? This is a real kludge and needs to be done some other way.
! 	 Perhaps for 2.9.  */
!       if (code != NOTE && num_insns++ > PARAM_VALUE (PARAM_MAX_CSE_INSNS))
! 	{
! 	  flush_hash_table ();
! 	  num_insns = 0;
  	}
  
!       /* See if this is a branch that is part of the path.  If so, and it is
! 	 to be taken, do so.  */
!       if (next_branch->branch == insn)
! 	{
! 	  enum taken status = next_branch++->status;
! 	  if (status != PATH_NOT_TAKEN)
! 	    {
! 	      gcc_assert (status == PATH_TAKEN);
! 	      if (any_condjump_p (insn))
! 		record_jump_equiv (insn, true);
  
- 	      /* Set the last insn as the jump insn; it doesn't affect cc0.
- 		 Then follow this branch.  */
  #ifdef HAVE_cc0
! 	      prev_insn_cc0 = 0;
! 	      prev_insn = insn;
  #endif
! 	      insn = JUMP_LABEL (insn);
! 	      continue;
  	    }
  	}
  
!       if (GET_MODE (insn) == QImode)
! 	PUT_MODE (insn, VOIDmode);
  
!       if (GET_RTX_CLASS (code) == RTX_INSN)
! 	{
! 	  rtx p;
  
! 	  /* Process notes first so we have all notes in canonical forms when
! 	     looking for duplicate operations.  */
  
! 	  if (REG_NOTES (insn))
! 	    REG_NOTES (insn) = cse_process_notes (REG_NOTES (insn), NULL_RTX);
  
! 	  /* Track when we are inside in LIBCALL block.  Inside such a block,
! 	     we do not want to record destinations.  The last insn of a
! 	     LIBCALL block is not considered to be part of the block, since
! 	     its destination is the result of the block and hence should be
! 	     recorded.  */
  
! 	  if (REG_NOTES (insn) != 0)
! 	    {
! 	      if ((p = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
! 		libcall_insn = XEXP (p, 0);
! 	      else if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
! 		{
! 		  /* Keep libcall_insn for the last SET insn of a no-conflict
! 		     block to prevent changing the destination.  */
! 		  if (! no_conflict)
! 		    libcall_insn = 0;
! 		  else
! 		    no_conflict = -1;
! 		}
! 	      else if (find_reg_note (insn, REG_NO_CONFLICT, NULL_RTX))
! 		no_conflict = 1;
! 	    }
  
! 	  cse_insn (insn, libcall_insn);
  
! 	  if (no_conflict == -1)
! 	    {
! 	      libcall_insn = 0;
! 	      no_conflict = 0;
! 	    }
! 	    
! 	  /* If we haven't already found an insn where we added a LABEL_REF,
! 	     check this one.  */
! 	  if (NONJUMP_INSN_P (insn) && ! recorded_label_ref
! 	      && for_each_rtx (&PATTERN (insn), check_for_label_ref,
! 			       (void *) insn))
! 	    recorded_label_ref = 1;
! 	}
  
!       /* If INSN is now an unconditional jump, skip to the end of our
! 	 basic block by pretending that we just did the last insn in the
! 	 basic block.  If we are jumping to the end of our block, show
! 	 that we can have one usage of TO.  */
  
!       if (any_uncondjump_p (insn))
  	{
! 	  if (to == 0)
! 	    {
! 	      free (qty_table);
! 	      return 0;
! 	    }
  
! 	  if (JUMP_LABEL (insn) == to)
! 	    to_usage = 1;
  
! 	  /* Maybe TO was deleted because the jump is unconditional.
! 	     If so, there is nothing left in this basic block.  */
! 	  /* ??? Perhaps it would be smarter to set TO
! 	     to whatever follows this insn,
! 	     and pretend the basic block had always ended here.  */
! 	  if (INSN_DELETED_P (to))
! 	    break;
  
! 	  insn = PREV_INSN (to);
  	}
      }
  
!   gcc_assert (next_qty <= max_qty);
! 
!   free (qty_table);
  
!   return to ? NEXT_INSN (to) : 0;
  }
  
  /* Called via for_each_rtx to see if an insn is using a LABEL_REF for which
--- 5803,6257 ----
    return x;
  }
  
! /* Find a path in the CFG, starting with FIRST_BB to perform CSE on.
  
!    DATA is a pointer to a struct cse_basic_blockb_data, that is used to
!    describe the path.
!    It is filled with a queue of basic blocks, starting with FIRST_BB
!    and following a trace through the CFG.
!   
!    If all paths starting at FIRST_BB have been followed, or no new path
!    starting at FIRST_BB can be constructed, this function returns FALSE.
!    Otherwise, DATA->path is filled and the function returns TRUE indicating
!    that a path to follow was found.
  
!    If FOLLOW_JUMPS is false, the maximum path lenghth is 1 and the only
!    block in the path will be FIRST_BB.  */
  
! static bool
! cse_find_path (basic_block first_bb, struct cse_basic_block_data *data,
! 	       int follow_jumps)
! {
!   basic_block bb;
!   edge e;
!   int path_size;
!  
!   SET_BIT (cse_visited_basic_blocks, first_bb->index);
  
!   /* See if there is a previous path.  */
!   path_size = data->path_size;
  
!   /* There is a previous path.  Make sure it started with FIRST_BB.  */
!   if (path_size)
!     gcc_assert (data->path[0].bb = first_bb);
  
!   /* There was only one basic block in the last path.  Clear the path and
!      return, so that paths starting at another basic block can be tried.  */
!   if (path_size == 1)
!     {
!       data->path[--path_size].bb = NULL;
!       goto done;
!     }
  
!   /* If the path was empty from the beginning, construct a new path.  */
!   if (path_size == 0)
!     data->path[path_size++].bb = first_bb;
!   else
!     {
!       /* Otherwise, path_size must be equal to or greater than 2, because
! 	 a previous path exists that is at least two basic blocks long.  */
!       gcc_assert (path_size >= 2);
! 
!       /* Update the previous branch path, if any.  If the last branch was
! 	 previously along the branch edge, take the fallthrough edge now.  */
!       while (path_size >= 2)
! 	{
! 	  basic_block last_bb_in_path, previous_bb_in_path;
! 	  edge e;
! 
! 	  --path_size;
! 	  last_bb_in_path = data->path[path_size].bb;
! 	  previous_bb_in_path = data->path[path_size - 1].bb;
! 
! 	  /* If we previously followed a path along the branch edge, try
! 	     the falltrhu edge now.  */
! 	  if (EDGE_COUNT (previous_bb_in_path->succs) == 2
! 	      && any_condjump_p (BB_END (previous_bb_in_path))
! 	      && (e = find_edge (previous_bb_in_path, last_bb_in_path))
! 	      && e == BRANCH_EDGE (previous_bb_in_path))
! 	    {
! 	      bb = FALLTHRU_EDGE (previous_bb_in_path)->dest;
! 	      if (bb != EXIT_BLOCK_PTR
! 		  && single_pred_p (bb))
  		{
! #if ENABLE_CHECKING
! 		  /* We should only see blocks here that we have not
! 		     visited yet.  */
! 		  gcc_assert (!TEST_BIT (cse_visited_basic_blocks, bb->index));
! #endif
! 		  SET_BIT (cse_visited_basic_blocks, bb->index);
! 		  data->path[path_size++].bb = bb;
! 		  break;
  		}
+ 	    }
  
! 	  data->path[path_size].bb = NULL;
! 	}
  
!       /* If only one block remains in the path, bail.  */
!       if (path_size == 1)
! 	{
! 	  data->path[--path_size].bb = NULL;
! 	  goto done;
! 	}
!     }
  
!   /* Extend the path if possible.  */
!   if (follow_jumps)
!     {
!       bb = data->path[path_size - 1].bb;
!       while (bb && path_size < PARAM_VALUE (PARAM_MAX_CSE_PATH_LENGTH))
! 	{
! 	  if (single_succ_p (bb))
! 	    e = single_succ_edge (bb);
! 	  else if (EDGE_COUNT (bb->succs) == 2
! 		   && any_condjump_p (BB_END (bb)))
! 	    {
! 	      /* First try to follow the branch.  If that doesn't lead
! 		 to a useful path, follow the fallthru edge.  */
! 	      e = BRANCH_EDGE (bb);
! 	      if (!single_pred_p (e->dest))
! 		e = FALLTHRU_EDGE (bb);
! 	    }
! 	  else
! 	    e = NULL;
  
! 	  if (e && e->dest != EXIT_BLOCK_PTR
! 	      && single_pred_p (e->dest))
! 	    {
! 	      basic_block bb2 = e->dest;
  
! #if ENABLE_CHECKING
! 	      /* We should only see blocks here that we have not
! 		 visited yet.  */
! 	      gcc_assert (!TEST_BIT (cse_visited_basic_blocks, bb2->index));
! #endif
! 	      SET_BIT (cse_visited_basic_blocks, bb2->index);
! 	      data->path[path_size++].bb = bb2;
! 	      bb = bb2;
  	    }
+ 	  else
+ 	    bb = NULL;
  	}
      }
  
! done:
!   data->path_size = path_size;
!   return path_size != 0;
  }
  
! /* Dump the path in DATA to file F.  NSETS is the number of sets
!    in the path.  */
  
! static void
! cse_dump_path (struct cse_basic_block_data *data, int nsets, FILE *f)
  {
!   int path_entry;
  
!   fprintf (f, ";; Following path with %d sets: ", nsets);
!   for (path_entry = 0; path_entry < data->path_size; path_entry++)
!     fprintf (f, "%d ", (data->path[path_entry].bb)->index);
!   fputc ('\n', dump_file);
!   fflush (f);
! }
  
! 
! /* Scan to the end of the path described by DATA.  Return an estimate of
!    the total number of SETs, and the lowest and highest insn CUID, of all
!    insns in the path.  */
  
! static void
! cse_prescan_path (struct cse_basic_block_data *data)
! {
!   int nsets = 0;
!   int low_cuid = -1, high_cuid = -1; /* FIXME low_cuid not computed correctly */
!   int path_size = data->path_size;
!   int path_entry;
  
!   /* Scan to end of each basic block in the path.  */
!   for (path_entry = 0; path_entry < path_size; path_entry++) 
!     {
!       basic_block bb;
!       rtx insn;
  
!       bb = data->path[path_entry].bb;
  
!       FOR_BB_INSNS (bb, insn)
  	{
! 	  if (!INSN_P (insn))
! 	    continue;
  
! 	  /* A PARALLEL can have lots of SETs in it,
! 	     especially if it is really an ASM_OPERANDS.  */
! 	  if (GET_CODE (PATTERN (insn)) == PARALLEL)
! 	    nsets += XVECLEN (PATTERN (insn), 0);
! 	  else
! 	    nsets += 1;
  
! 	  /* Ignore insns made by CSE in a previous traversal of this
! 	     basic block.  They cannot affect the boundaries of the
! 	     basic block.
! 	     FIXME: When we only visit each basic block at most once,
! 		    this can go away.  */
! 	  if (INSN_UID (insn) <= max_uid && INSN_CUID (insn) > high_cuid)
! 	    high_cuid = INSN_CUID (insn);
! 	  if (INSN_UID (insn) <= max_uid && INSN_CUID (insn) < low_cuid)
! 	    low_cuid = INSN_CUID (insn);
  	}
      }
  
!   data->low_cuid = low_cuid;
!   data->high_cuid = high_cuid;
!   data->nsets = nsets;
  }
+ 
+ /* Process a single extended basic block described by EBB_DATA.  */
  
! static void
! cse_extended_basic_block (struct cse_basic_block_data *ebb_data)
  {
!   int path_size = ebb_data->path_size;
!   int path_entry;
    int num_insns = 0;
  
    /* Allocate the space needed by qty_table.  */
    qty_table = XNEWVEC (struct qty_table_elem, max_qty);
  
    new_basic_block ();
+   for (path_entry = 0; path_entry < path_size; path_entry++)
+     {
+       basic_block bb;
+       rtx insn;
+       rtx libcall_insn = NULL_RTX;
+       int no_conflict = 0;
  
!       bb = ebb_data->path[path_entry].bb;
!       FOR_BB_INSNS (bb, insn)
! 	{
! 	  /* If we have processed 1,000 insns, flush the hash table to
! 	     avoid extreme quadratic behavior.  We must not include NOTEs
! 	     in the count since there may be more of them when generating
! 	     debugging information.  If we clear the table at different
! 	     times, code generated with -g -O might be different than code
! 	     generated with -O but not -g.
! 
! 	     FIXME: This is a real kludge and needs to be done some other
! 		    way.  */
! 	  if (!INSN_P (insn)
! 	      && num_insns++ > PARAM_VALUE (PARAM_MAX_CSE_INSNS))
! 	    {
! 	      flush_hash_table ();
! 	      num_insns = 0;
! 	    }
! 
! 	  if (INSN_P (insn))
! 	    {
! 	      /* Process notes first so we have all notes in canonical forms
! 		 when looking for duplicate operations.  */
! 	      if (REG_NOTES (insn))
! 		REG_NOTES (insn) = cse_process_notes (REG_NOTES (insn),
! 						      NULL_RTX);
! 
! 	      /* Track when we are inside in LIBCALL block.  Inside such
! 		 a block we do not want to record destinations.  The last
! 		 insn of a LIBCALL block is not considered to be part of
! 		 the block, since its destination is the result of the
! 		 block and hence should be recorded.  */
! 	      if (REG_NOTES (insn) != 0)
! 		{
! 		  rtx p;
  
! 		  if ((p = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
! 		    libcall_insn = XEXP (p, 0);
! 		  else if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
! 		    {
! 		      /* Keep libcall_insn for the last SET insn of
! 			 a no-conflict block to prevent changing the
! 			 destination.  */
! 		      if (!no_conflict)
! 			libcall_insn = NULL_RTX;
! 		      else
! 			no_conflict = -1;
! 		    }
! 		  else if (find_reg_note (insn, REG_NO_CONFLICT, NULL_RTX))
! 		    no_conflict = 1;
! 		}
  
! 	      cse_insn (insn, libcall_insn);
  
! 	      /* If we kept libcall_insn for a no-conflict bock,
! 		 clear it here.  */
! 	      if (no_conflict == -1)
! 		{
! 		  libcall_insn = NULL_RTX;
! 		  no_conflict = 0;
! 		}
! 	    
! 	      /* If we haven't already found an insn where we added a LABEL_REF,
! 		 check this one.  */
! 	      if (NONJUMP_INSN_P (insn) && ! recorded_label_ref
! 		  && for_each_rtx (&PATTERN (insn), check_for_label_ref,
! 				   (void *) insn))
! 		recorded_label_ref = 1;
! 	    }
  	}
  
!       /* Make sure that libcalls don't span multiple basic blocks.  */
!       gcc_assert (libcall_insn == NULL_RTX);
  
  #ifdef HAVE_cc0
!       /* Clear the CC0-tracking related insns, they can't provide
! 	 useful information across basic block boundaries.  */
!       prev_insn_cc0 = 0;
!       prev_insn = 0;
  #endif
! 
!       /* If we changed a conditional jump, we may have terminated
! 	 the path we are following.  Check that by verifying that
! 	 the edge we would take still exists.  If the edge does
! 	 not exist anymore, purge the remainder of the path.
! 	 Note that this will cause us to return to the caller.  */
!       if (path_entry < path_size - 1)
! 	{
! 	  basic_block next_bb = ebb_data->path[path_entry + 1].bb;
! 	  if (!find_edge (bb, next_bb))
! 	    {
! 	      do
! 		{
! 		  ebb_data->path[--path_size].bb = NULL;
! 		}
! 	      while (ebb_data->path[path_size - 1].bb != bb);
! 	      ebb_data->path_size = path_size;
  	    }
  	}
  
!       /* If this is a conditional jump insn, record any known
! 	 equivalences due to the condition being tested.  */
!       insn = BB_END (bb);
!       if (JUMP_P (insn)
! 	  && single_set (insn)
! 	  && any_condjump_p (insn)
! 	  && path_entry < path_size - 1)
! 	{
! 	  basic_block next_bb = ebb_data->path[path_entry + 1].bb;
! 	  bool taken = (next_bb == BRANCH_EDGE (bb)->dest);
! 	  record_jump_equiv (insn, taken);
! 	}
!     }
  
!   gcc_assert (next_qty <= max_qty);
  
!   free (qty_table);
! }
! 
! /* Perform cse on the instructions of a function.
!    F is the first instruction.
!    NREGS is one plus the highest pseudo-reg number used in the instruction.
  
!    Returns 1 if jump_optimize should be redone due to simplifications
!    in conditional jump instructions.  */
  
! int
! cse_main (rtx f ATTRIBUTE_UNUSED, int nregs)
! {
!   struct cse_basic_block_data ebb_data;
!   basic_block bb;
!   int *dfs_order = XNEWVEC (int, last_basic_block);
!   int i, n_blocks;
  
!   init_cse_reg_info (nregs);
  
!   ebb_data.path = XNEWVEC (struct branch_path, PARAM_VALUE (PARAM_MAX_CSE_PATH_LENGTH));
  
!   cse_jumps_altered = 0;
!   recorded_label_ref = 0;
!   constant_pool_entries_cost = 0;
!   constant_pool_entries_regcost = 0;
!   ebb_data.path_size = 0;
!   ebb_data.nsets = 0;
!   rtl_hooks = cse_rtl_hooks;
! 
!   init_recog ();
!   init_alias_analysis ();
! 
!   reg_eqv_table = XNEWVEC (struct reg_eqv_elem, nregs);
  
!   /* Set up the table of already visited basic blocks.  */
!   cse_visited_basic_blocks = sbitmap_alloc (last_basic_block);
!   sbitmap_zero (cse_visited_basic_blocks);
  
!   /* Compute the mapping from uids to cuids.
!      CUIDs are numbers assigned to insns, like uids, except that
!      that cuids increase monotonically through the code.  */
!   max_uid = get_max_uid ();
!   uid_cuid = XCNEWVEC (int, max_uid + 1);
!   i = 0;
!   FOR_EACH_BB (bb)
!     {
!       rtx insn;
!       FOR_BB_INSNS (bb, insn)
! 	INSN_CUID (insn) = ++i;
!     }
! 
!   /* Loop over basic blocks in DFS order,
!      excluding the ENTRY and EXIT blocks.  */
!   n_blocks = pre_and_rev_post_order_compute (dfs_order, NULL, false);
!   i = 0;
!   while (i < n_blocks)
!     {
!       /* Find the first block in the DFS queue that we have not yet
! 	 processed before.  */
!       do
  	{
! 	  bb = BASIC_BLOCK (dfs_order[i++]);
! 	}
!       while (TEST_BIT (cse_visited_basic_blocks, bb->index)
! 	     && i < n_blocks);
! 
!       /* Find all paths starting with BB, and process them.  */
!       while (cse_find_path (bb, &ebb_data, flag_cse_follow_jumps))
! 	{
! 	  /* Pre-scan the path.  */
! 	  cse_prescan_path (&ebb_data);
  
! 	  /* If this basic block was already processed or has no sets,
! 	     skip it.  */
! 	  if (ebb_data.nsets == 0)
! 	    continue;
  
! 	  /* Get a reasonable extimate for the maximum number of qty's
! 	     needed for this path.  For this, we take the number of sets
! 	     and multiply that by MAX_RECOG_OPERANDS.
! 	     The old CSE path following code would use MIN(2*nsets,500)
! 	     but now that we know exactly how many insns (and hence sets)
! 	     we will see in the path, it seemed like a good idea to just
! 	     use max_qty = 2 * nsets.  Interestingly, we end up writing
! 	     past the end of qty_table with that value for max_qty.  In
! 	     other words, this was a latent bug in cse.c present since 
! 	     at least 1992.
! 	     Oh well, we just take a bigger max_qty now to play safe.  */
! 	  max_qty = ebb_data.nsets * MAX_RECOG_OPERANDS;
! 	  cse_basic_block_start = ebb_data.low_cuid;
! 	  cse_basic_block_end = ebb_data.high_cuid;
! 
! 	  /* Dump the path we're about to process.  */
! 	  if (dump_file)
! 	    cse_dump_path (&ebb_data, ebb_data.nsets, dump_file);
  
! 	  cse_extended_basic_block (&ebb_data);
  	}
      }
  
!   /* Clean up.  */
!   end_alias_analysis ();
!   free (uid_cuid);
!   free (reg_eqv_table);
!   free (ebb_data.path);
!   sbitmap_free (cse_visited_basic_blocks);
!   free (dfs_order);
!   rtl_hooks = general_rtl_hooks;
  
!   return cse_jumps_altered || recorded_label_ref;
  }
  
  /* Called via for_each_rtx to see if an insn is using a LABEL_REF for which
*************** static unsigned int
*** 6930,6935 ****
--- 6969,6978 ----
  rest_of_handle_cse (void)
  {
    int tem;
+   basic_block bb;
+ 
+   /* Initialize structures for layout changes.  */
+   cfg_layout_initialize (0);
  
    if (dump_file)
      dump_flow_info (dump_file, dump_flags);
*************** rest_of_handle_cse (void)
*** 6937,6958 ****
    reg_scan (get_insns (), max_reg_num ());
  
    tem = cse_main (get_insns (), max_reg_num ());
-   if (tem)
-     rebuild_jump_labels (get_insns ());
-   if (purge_all_dead_edges ())
-     delete_unreachable_blocks ();
- 
-   delete_trivially_dead_insns (get_insns (), max_reg_num ());
  
    /* If we are not running more CSE passes, then we are no longer
       expecting CSE to be run.  But always rerun it in a cheap mode.  */
    cse_not_expected = !flag_rerun_cse_after_loop && !flag_gcse;
  
    if (tem)
!     delete_dead_jumptables ();
  
    if (tem || optimize > 1)
!     cleanup_cfg (CLEANUP_EXPENSIVE);
    return 0;
  }
  
--- 6980,7007 ----
    reg_scan (get_insns (), max_reg_num ());
  
    tem = cse_main (get_insns (), max_reg_num ());
  
    /* If we are not running more CSE passes, then we are no longer
       expecting CSE to be run.  But always rerun it in a cheap mode.  */
    cse_not_expected = !flag_rerun_cse_after_loop && !flag_gcse;
  
+ #ifdef ENABLE_CHECKING
+   if (purge_all_dead_edges ())
+     gcc_unreachable ();
+ #endif
+ 
    if (tem)
!     rebuild_jump_labels (get_insns ());
  
    if (tem || optimize > 1)
!     cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_CFGLAYOUT);
! 
!   /* Finalize layout changes.  */
!   FOR_EACH_BB (bb)
!     if (bb->next_bb != EXIT_BLOCK_PTR)
!       bb->aux = bb->next_bb;
!   cfg_layout_finalize ();
! 
    return 0;
  }
  
*************** struct tree_opt_pass pass_cse =
*** 6970,6976 ****
    0,                                    /* properties_destroyed */
    0,                                    /* todo_flags_start */
    TODO_dump_func |
!   TODO_ggc_collect,                     /* todo_flags_finish */
    's'                                   /* letter */
  };
  
--- 7019,7026 ----
    0,                                    /* properties_destroyed */
    0,                                    /* todo_flags_start */
    TODO_dump_func |
!   TODO_ggc_collect |
!   TODO_verify_flow,                     /* todo_flags_finish */
    's'                                   /* letter */
  };
  
*************** rest_of_handle_cse2 (void)
*** 6998,7004 ****
       bypassed safely.  */
    cse_condition_code_reg ();
  
!   purge_all_dead_edges ();
    delete_trivially_dead_insns (get_insns (), max_reg_num ());
  
    if (tem)
--- 7048,7058 ----
       bypassed safely.  */
    cse_condition_code_reg ();
  
! #ifdef ENABLE_CHECKING
!   if (purge_all_dead_edges ())
!     gcc_unreachable ();
! #endif
! 
    delete_trivially_dead_insns (get_insns (), max_reg_num ());
  
    if (tem)
*************** struct tree_opt_pass pass_cse2 =
*** 7029,7035 ****
    0,                                    /* properties_destroyed */
    0,                                    /* todo_flags_start */
    TODO_dump_func |
!   TODO_ggc_collect,                     /* todo_flags_finish */
    't'                                   /* letter */
  };
  
--- 7083,7090 ----
    0,                                    /* properties_destroyed */
    0,                                    /* todo_flags_start */
    TODO_dump_func |
!   TODO_ggc_collect |
!   TODO_verify_flow,                     /* todo_flags_finish */
    't'                                   /* letter */
  };
  


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]