[patch] Store motion rewrite

Zdenek Dvorak rakdver@atrey.karlin.mff.cuni.cz
Wed Mar 5 21:55:00 GMT 2003


Hello,

> > no, its much simpler; just
> > (insn 177 176 374 33 0x2a98de5b40 (set (mem/s:SI (plus:DI (reg/v/f:DI 59 [ this ])
> >                 (const_int 40 [0x28])) [17 <variable>.pos+0 S4 A64])
> >         (reg:SI 121)) -1 (nil)
> >     (expr_list:REG_EH_REGION (const_int 1 [0x1])
> >         (nil)))
> > 
> > is converted into
> > 
> > (insn 431 176 374 33 (nil) (set (reg:SI 169)
> >         (reg:SI 121)) -1 (nil)
> >     (nil))
> > by store motion.
> > 
> > Unfortunately probably the only correct fix is to disable the
> > transformation in this case at all; which is unpleasant considering that
> > we will miss most of the opportunities :-(
> 
> Yep.  There's no helping the fact that you can't perform
> load or store motion on trapping memories when they matter.

here is the updated patch. It just tests for possibility to trap when
we do exception handling, as otherwise it does not matter whether we
crash now or sometime later.

Zdenek

Index: gcse.c
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/gcse.c,v
retrieving revision 1.238
diff -c -3 -p -r1.238 gcse.c
*** gcse.c	25 Feb 2003 22:56:27 -0000	1.238
--- gcse.c	5 Mar 2003 21:45:58 -0000
*************** struct ls_expr
*** 470,475 ****
--- 470,476 ----
  {
    struct expr * expr;		/* Gcse expression reference for LM.  */
    rtx pattern;			/* Pattern of this mem.  */
+   rtx pattern_regs;		/* List of registers mentioned by the mem.  */
    rtx loads;			/* INSN list of loads seen.  */
    rtx stores;			/* INSN list of stores seen.  */
    struct ls_expr * next;	/* Next in the list.  */
*************** static void compute_ld_motion_mems	PARAM
*** 686,699 ****
  static void trim_ld_motion_mems		PARAMS ((void));
  static void update_ld_motion_stores	PARAMS ((struct expr *));
  static void reg_set_info		PARAMS ((rtx, rtx, void *));
! static int store_ops_ok			PARAMS ((rtx, basic_block));
! static void find_moveable_store		PARAMS ((rtx));
  static int compute_store_table		PARAMS ((void));
! static int load_kills_store		PARAMS ((rtx, rtx));
! static int find_loads			PARAMS ((rtx, rtx));
! static int store_killed_in_insn		PARAMS ((rtx, rtx));
! static int store_killed_after		PARAMS ((rtx, rtx, basic_block));
! static int store_killed_before		PARAMS ((rtx, rtx, basic_block));
  static void build_store_vectors		PARAMS ((void));
  static void insert_insn_start_bb	PARAMS ((rtx, basic_block));
  static int insert_store			PARAMS ((struct ls_expr *, edge));
--- 687,704 ----
  static void trim_ld_motion_mems		PARAMS ((void));
  static void update_ld_motion_stores	PARAMS ((struct expr *));
  static void reg_set_info		PARAMS ((rtx, rtx, void *));
! static bool store_ops_ok		PARAMS ((rtx, int *));
! static rtx extract_mentioned_regs	PARAMS ((rtx));
! static rtx extract_mentioned_regs_helper PARAMS ((rtx, rtx));
! static void find_moveable_store		PARAMS ((rtx, int *, int *));
  static int compute_store_table		PARAMS ((void));
! static bool load_kills_store		PARAMS ((rtx, rtx));
! static bool find_loads			PARAMS ((rtx, rtx));
! static bool store_killed_in_insn	PARAMS ((rtx, rtx));
! static bool store_killed_after		PARAMS ((rtx, rtx, rtx, basic_block,
! 						 int *, rtx *));
! static bool store_killed_before		PARAMS ((rtx, rtx, rtx, basic_block,
! 						 int *));
  static void build_store_vectors		PARAMS ((void));
  static void insert_insn_start_bb	PARAMS ((rtx, basic_block));
  static int insert_store			PARAMS ((struct ls_expr *, edge));
*************** gcse_main (f, file)
*** 909,917 ****
    end_alias_analysis ();
    allocate_reg_info (max_reg_num (), FALSE, FALSE);
  
!   /* Store motion disabled until it is fixed.  */
!   if (0 && !optimize_size && flag_gcse_sm)
      store_motion ();
    /* Record where pseudo-registers are set.  */
    return run_jump_opt_after_gcse;
  }
--- 914,922 ----
    end_alias_analysis ();
    allocate_reg_info (max_reg_num (), FALSE, FALSE);
  
!   if (!optimize_size && flag_gcse_sm)
      store_motion ();
+ 
    /* Record where pseudo-registers are set.  */
    return run_jump_opt_after_gcse;
  }
*************** mems_conflict_for_gcse_p (dest, setter, 
*** 1463,1469 ****
    /* If we are setting a MEM in our list of specially recognized MEMs,
       don't mark as killed this time.  */
  
!   if (dest == gcse_mem_operand && pre_ldst_mems != NULL)
      {
        if (!find_rtx_in_ldst (dest))
  	gcse_mems_conflict_p = 1;
--- 1468,1474 ----
    /* If we are setting a MEM in our list of specially recognized MEMs,
       don't mark as killed this time.  */
  
!   if (expr_equiv_p (dest, gcse_mem_operand) && pre_ldst_mems != NULL)
      {
        if (!find_rtx_in_ldst (dest))
  	gcse_mems_conflict_p = 1;
*************** pre_insert_copy_insn (expr, insn)
*** 5403,5409 ****
    if (!set)
      abort ();
  
!   new_insn = emit_insn_after (gen_move_insn (reg, SET_DEST (set)), insn);
  
    /* Keep register set table up to date.  */
    record_one_set (regno, new_insn);
--- 5408,5414 ----
    if (!set)
      abort ();
  
!   new_insn = emit_insn_after (gen_move_insn (reg, copy_rtx (SET_DEST (set))), insn);
  
    /* Keep register set table up to date.  */
    record_one_set (regno, new_insn);
*************** ldst_entry (x)
*** 6480,6485 ****
--- 6485,6491 ----
        ptr->next         = pre_ldst_mems;
        ptr->expr         = NULL;
        ptr->pattern      = x;
+       ptr->pattern_regs	= NULL_RTX;
        ptr->loads        = NULL_RTX;
        ptr->stores       = NULL_RTX;
        ptr->reaching_reg = NULL_RTX;
*************** simple_mem (x)
*** 6622,6631 ****
    if (GET_MODE (x) == BLKmode)
      return 0;
  
!   if (!rtx_varies_p (XEXP (x, 0), 0))
!     return 1;
  
!   return 0;
  }
  
  /* Make sure there isn't a buried reference in this pattern anywhere.
--- 6628,6647 ----
    if (GET_MODE (x) == BLKmode)
      return 0;
  
!   /* If we are handling exceptions, we must be careful with memory references
!      that may trap. If we are not, the behavior is undefined, so we may just
!      continue.  */
!   if (flag_exceptions && may_trap_p (x))
!     return 0;
  
!   if (side_effects_p (x))
!     return 0;
! 
!   /* Do not consider function arguments passed on stack.  */
!   if (reg_mentioned_p (stack_pointer_rtx, x))
!     return 0;
! 
!   return 1;
  }
  
  /* Make sure there isn't a buried reference in this pattern anywhere.
*************** update_ld_motion_stores (expr)
*** 6838,6844 ****
  	      fprintf (gcse_file, "\n");
  	    }
  
! 	  copy = gen_move_insn ( reg, SET_SRC (pat));
  	  new = emit_insn_before (copy, insn);
  	  record_one_set (REGNO (reg), new);
  	  SET_SRC (pat) = reg;
--- 6854,6860 ----
  	      fprintf (gcse_file, "\n");
  	    }
  
! 	  copy = gen_move_insn ( reg, copy_rtx (SET_SRC (pat)));
  	  new = emit_insn_before (copy, insn);
  	  record_one_set (REGNO (reg), new);
  	  SET_SRC (pat) = reg;
*************** update_ld_motion_stores (expr)
*** 6852,6860 ****
  
  /* Store motion code.  */
  
  /* This is used to communicate the target bitvector we want to use in the
     reg_set_info routine when called via the note_stores mechanism.  */
! static sbitmap * regvec;
  
  /* Used in computing the reverse edge graph bit vectors.  */
  static sbitmap * st_antloc;
--- 6868,6883 ----
  
  /* Store motion code.  */
  
+ #define ANTIC_STORE_LIST(x)		((x)->loads)
+ #define AVAIL_STORE_LIST(x)		((x)->stores)
+ #define LAST_AVAIL_CHECK_FAILURE(x)	((x)->reaching_reg)
+ 
  /* This is used to communicate the target bitvector we want to use in the
     reg_set_info routine when called via the note_stores mechanism.  */
! static int * regvec;
! 
! /* And current insn, for the same routine.  */
! static rtx compute_store_table_current_insn;
  
  /* Used in computing the reverse edge graph bit vectors.  */
  static sbitmap * st_antloc;
*************** reg_set_info (dest, setter, data)
*** 6873,6888 ****
      dest = SUBREG_REG (dest);
  
    if (GET_CODE (dest) == REG)
!     SET_BIT (*regvec, REGNO (dest));
  }
  
! /* Return nonzero if the register operands of expression X are killed
!    anywhere in basic block BB.  */
  
! static int
! store_ops_ok (x, bb)
       rtx x;
!      basic_block bb;
  {
    int i;
    enum rtx_code code;
--- 6896,6938 ----
      dest = SUBREG_REG (dest);
  
    if (GET_CODE (dest) == REG)
!     regvec[REGNO (dest)] = INSN_UID (compute_store_table_current_insn);
  }
  
! /* Return zero if some of the registers in list X are killed
!    due to set of registers in bitmap REGS_SET.  */
!   
! static bool
! store_ops_ok (x, regs_set)
!      rtx x;
!      int *regs_set;
! {
!   rtx reg;
  
!   for (; x; x = XEXP (x, 1))
!     {
!       reg = XEXP (x, 0);
!       if (regs_set[REGNO(reg)])
! 	return false; 
!     }
! 
!   return true;
! }
! 
! /* Returns a list of registers mentioned in X.  */
! static rtx
! extract_mentioned_regs (x)
       rtx x;
! {
!   return extract_mentioned_regs_helper (x, NULL_RTX);
! }
! 
! /* Helper for extract_mentioned_regs; ACCUM is used to accumulate used
!    registers.  */
! static rtx
! extract_mentioned_regs_helper (x, accum)
!      rtx x;
!      rtx accum;
  {
    int i;
    enum rtx_code code;
*************** store_ops_ok (x, bb)
*** 6892,6906 ****
   repeat:
  
    if (x == 0)
!     return 1;
  
    code = GET_CODE (x);
    switch (code)
      {
      case REG:
! 	/* If a reg has changed after us in this
! 	   block, the operand has been killed.  */
! 	return TEST_BIT (reg_set_in_block[bb->index], REGNO (x));
  
      case MEM:
        x = XEXP (x, 0);
--- 6942,6954 ----
   repeat:
  
    if (x == 0)
!     return accum;
  
    code = GET_CODE (x);
    switch (code)
      {
      case REG:
!       return alloc_EXPR_LIST (0, x, accum);
  
      case MEM:
        x = XEXP (x, 0);
*************** store_ops_ok (x, bb)
*** 6910,6916 ****
      case PRE_INC:
      case POST_DEC:
      case POST_INC:
!       return 0;
  
      case PC:
      case CC0: /*FIXME*/
--- 6958,6965 ----
      case PRE_INC:
      case POST_DEC:
      case POST_INC:
!       /* We do not run this function with arguments having side effects.  */
!       abort ();
  
      case PC:
      case CC0: /*FIXME*/
*************** store_ops_ok (x, bb)
*** 6922,6928 ****
      case LABEL_REF:
      case ADDR_VEC:
      case ADDR_DIFF_VEC:
!       return 1;
  
      default:
        break;
--- 6971,6977 ----
      case LABEL_REF:
      case ADDR_VEC:
      case ADDR_DIFF_VEC:
!       return accum;
  
      default:
        break;
*************** store_ops_ok (x, bb)
*** 6938,7000 ****
  	  rtx tem = XEXP (x, i);
  
  	  /* If we are about to do the last recursive call
! 	     needed at this level, change it into iteration.
! 	     This function is called enough to be worth it.  */
  	  if (i == 0)
  	    {
  	      x = tem;
  	      goto repeat;
  	    }
  
! 	  if (! store_ops_ok (tem, bb))
! 	    return 0;
  	}
        else if (fmt[i] == 'E')
  	{
  	  int j;
  
  	  for (j = 0; j < XVECLEN (x, i); j++)
! 	    {
! 	      if (! store_ops_ok (XVECEXP (x, i, j), bb))
! 		return 0;
! 	    }
  	}
      }
  
!   return 1;
  }
  
! /* Determine whether insn is MEM store pattern that we will consider moving.  */
  
  static void
! find_moveable_store (insn)
       rtx insn;
  {
    struct ls_expr * ptr;
!   rtx dest = PATTERN (insn);
  
!   if (GET_CODE (dest) != SET
!       || GET_CODE (SET_SRC (dest)) == ASM_OPERANDS)
      return;
  
!   dest = SET_DEST (dest);
  
    if (GET_CODE (dest) != MEM || MEM_VOLATILE_P (dest)
        || GET_MODE (dest) == BLKmode)
      return;
  
!   if (GET_CODE (XEXP (dest, 0)) != SYMBOL_REF)
!       return;
  
!   if (rtx_varies_p (XEXP (dest, 0), 0))
      return;
  
    ptr = ldst_entry (dest);
!   ptr->stores = alloc_INSN_LIST (insn, ptr->stores);
! }
  
! /* Perform store motion. Much like gcse, except we move expressions the
!    other way by looking at the flowgraph in reverse.  */
  
  static int
  compute_store_table ()
--- 6987,7132 ----
  	  rtx tem = XEXP (x, i);
  
  	  /* If we are about to do the last recursive call
! 	     needed at this level, change it into iteration.  */
  	  if (i == 0)
  	    {
  	      x = tem;
  	      goto repeat;
  	    }
  
! 	  accum = extract_mentioned_regs_helper (tem, accum);
  	}
        else if (fmt[i] == 'E')
  	{
  	  int j;
  
  	  for (j = 0; j < XVECLEN (x, i); j++)
! 	    accum = extract_mentioned_regs_helper (XVECEXP (x, i, j), accum);
  	}
      }
  
!   return accum;
  }
  
! /* Determine whether INSN is MEM store pattern that we will consider moving.
!    REGS_SET_BEFORE is bitmap of registers set before (and including) the
!    current insn, REGS_SET_AFTER is bitmap of registers set after (and
!    including) the insn in this basic block.  We must be passing through BB from
!    head to end, as we are using this fact to speed things up.
!    
!    The results are stored this way:
! 
!    -- the first anticipatable expression is added into ANTIC_STORE_LIST
!    -- if the processed expression is not anticipatable, NULL_RTX is added
!       there instead, so that we can use it as indicator that no further
!       expression of this type may be anticipatable
!    -- if the expression is available, it is added as head of AVAIL_STORE_LIST;
!       consequently, all of them but this head are dead and may be deleted.
!    -- if the expression is not available, the insn due to that it fails to be
!       available is stored in reaching_reg.
! 
!    The things are complicated a bit by fact that there already may be stores
!    to the same MEM from other blocks; also caller must take care of the
!    neccessary cleanup of the temporary markers after end of the basic block.
!    */
  
  static void
! find_moveable_store (insn, regs_set_before, regs_set_after)
       rtx insn;
+      int *regs_set_before;
+      int *regs_set_after;
  {
    struct ls_expr * ptr;
!   rtx dest, set, tmp;
!   int check_anticipatable, check_available;
!   basic_block bb = BLOCK_FOR_INSN (insn);
  
!   set = single_set (insn);
!   if (!set)
      return;
  
!   dest = SET_DEST (set);
  
    if (GET_CODE (dest) != MEM || MEM_VOLATILE_P (dest)
        || GET_MODE (dest) == BLKmode)
      return;
  
!   if (side_effects_p (dest))
!     return;
  
!   /* If we are handling exceptions, we must be careful with memory references
!      that may trap. If we are not, the behavior is undefined, so we may just
!      continue.  */
!   if (flag_exceptions && may_trap_p (dest))
!     return;
!     
!   /* Do not consider MEMs that mention stack pointer; in the following
!      we rely on that constant functions do not read memory, which of course
!      does not include their arguments if passed on stack.  */
!   if (reg_mentioned_p (stack_pointer_rtx, dest))
      return;
  
    ptr = ldst_entry (dest);
!   if (!ptr->pattern_regs)
!     ptr->pattern_regs = extract_mentioned_regs (dest);
  
!   /* Do not check for anticipatability if we either found one anticipatable
!      store already, or tested for one and found out that it was killed.  */
!   check_anticipatable = 0;
!   if (!ANTIC_STORE_LIST (ptr))
!     check_anticipatable = 1;
!   else
!     {
!       tmp = XEXP (ANTIC_STORE_LIST (ptr), 0);
!       if (tmp != NULL_RTX
! 	  && BLOCK_FOR_INSN (tmp) != bb)
! 	check_anticipatable = 1;
!     }
!   if (check_anticipatable)
!     {
!       if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before))
! 	tmp = NULL_RTX;
!       else
! 	tmp = insn;
!       ANTIC_STORE_LIST (ptr) = alloc_INSN_LIST (tmp,
! 						ANTIC_STORE_LIST (ptr));
!     }
! 
!   /* It is not neccessary to check whether store is available if we did
!      it successfully before; if we failed before, do not bother to check
!      until we reach the insn that caused us to fail.  */
!   check_available = 0;
!   if (!AVAIL_STORE_LIST (ptr))
!     check_available = 1;
!   else
!     {
!       tmp = XEXP (AVAIL_STORE_LIST (ptr), 0);
!       if (BLOCK_FOR_INSN (tmp) != bb)
! 	check_available = 1;
!     }
!   if (check_available)
!     {
!       /* Check that we have already reached the insn at that the check
! 	 failed last time.  */
!       if (LAST_AVAIL_CHECK_FAILURE (ptr))
! 	{
! 	  for (tmp = bb->end;
! 	       tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr);
! 	       tmp = PREV_INSN (tmp))
! 	    continue;
! 	  if (tmp == insn)
! 	    check_available = 0;
! 	}
!       else
! 	check_available = store_killed_after (dest, ptr->pattern_regs, insn,
! 					      bb, regs_set_after,
! 					      &LAST_AVAIL_CHECK_FAILURE (ptr));
!     }
!   if (!check_available)
!     AVAIL_STORE_LIST (ptr) = alloc_INSN_LIST (insn, AVAIL_STORE_LIST (ptr));
! }
!   
! /* Find available and anticipatable stores.  */
  
  static int
  compute_store_table ()
*************** compute_store_table ()
*** 7002,7008 ****
    int ret;
    basic_block bb;
    unsigned regno;
!   rtx insn, pat;
  
    max_gcse_regno = max_reg_num ();
  
--- 7134,7142 ----
    int ret;
    basic_block bb;
    unsigned regno;
!   rtx insn, pat, tmp;
!   int *last_set_in, *already_set;
!   struct ls_expr * ptr, **prev_next_ptr_ptr;
  
    max_gcse_regno = max_reg_num ();
  
*************** compute_store_table ()
*** 7010,7025 ****
  						       max_gcse_regno);
    sbitmap_vector_zero (reg_set_in_block, last_basic_block);
    pre_ldst_mems = 0;
  
    /* Find all the stores we care about.  */
    FOR_EACH_BB (bb)
      {
!       regvec = & (reg_set_in_block[bb->index]);
!       for (insn = bb->end;
! 	   insn && insn != PREV_INSN (bb->end);
! 	   insn = PREV_INSN (insn))
  	{
- 	  /* Ignore anything that is not a normal insn.  */
  	  if (! INSN_P (insn))
  	    continue;
  
--- 7144,7163 ----
  						       max_gcse_regno);
    sbitmap_vector_zero (reg_set_in_block, last_basic_block);
    pre_ldst_mems = 0;
+   last_set_in = xmalloc (sizeof (int) * max_gcse_regno);
+   already_set = xmalloc (sizeof (int) * max_gcse_regno);
  
    /* Find all the stores we care about.  */
    FOR_EACH_BB (bb)
      {
!       /* First compute the registers set in this block.  */
!       memset (last_set_in, 0, sizeof (int) * max_gcse_regno);
!       regvec = last_set_in;
! 
!       for (insn = bb->head;
! 	   insn != NEXT_INSN (bb->end);
! 	   insn = NEXT_INSN (insn))
  	{
  	  if (! INSN_P (insn))
  	    continue;
  
*************** compute_store_table ()
*** 7035,7087 ****
  	      for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
  		if (clobbers_all
  		    || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
! 		  SET_BIT (reg_set_in_block[bb->index], regno);
  	    }
  
  	  pat = PATTERN (insn);
  	  note_stores (pat, reg_set_info, NULL);
  
  	  /* Now that we've marked regs, look for stores.  */
! 	  if (GET_CODE (pat) == SET)
! 	    find_moveable_store (insn);
  	}
      }
  
    ret = enumerate_ldsts ();
  
    if (gcse_file)
      {
!       fprintf (gcse_file, "Store Motion Expressions.\n");
        print_ldst_list (gcse_file);
      }
  
    return ret;
  }
  
  /* Check to see if the load X is aliased with STORE_PATTERN.  */
  
! static int
  load_kills_store (x, store_pattern)
       rtx x, store_pattern;
  {
    if (true_dependence (x, GET_MODE (x), store_pattern, rtx_addr_varies_p))
!     return 1;
!   return 0;
  }
  
  /* Go through the entire insn X, looking for any loads which might alias
!    STORE_PATTERN.  Return 1 if found.  */
  
! static int
  find_loads (x, store_pattern)
       rtx x, store_pattern;
  {
    const char * fmt;
    int i, j;
!   int ret = 0;
  
    if (!x)
!     return 0;
  
    if (GET_CODE (x) == SET)
      x = SET_SRC (x);
--- 7173,7290 ----
  	      for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
  		if (clobbers_all
  		    || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
! 		  last_set_in[regno] = INSN_UID (insn);
! 	    }
! 
! 	  pat = PATTERN (insn);
! 	  compute_store_table_current_insn = insn;
! 	  note_stores (pat, reg_set_info, NULL);
! 	}
! 
!       /* Record the set registers.  */
!       for (regno = 0; regno < max_gcse_regno; regno++)
! 	if (last_set_in[regno])
! 	  SET_BIT (reg_set_in_block[bb->index], regno);
! 
!       /* Now find the stores.  */
!       memset (already_set, 0, sizeof (int) * max_gcse_regno);
!       regvec = already_set;
!       for (insn = bb->head;
! 	   insn != NEXT_INSN (bb->end);
! 	   insn = NEXT_INSN (insn))
! 	{
! 	  if (! INSN_P (insn))
! 	    continue;
! 
! 	  if (GET_CODE (insn) == CALL_INSN)
! 	    {
! 	      bool clobbers_all = false;
! #ifdef NON_SAVING_SETJMP
! 	      if (NON_SAVING_SETJMP
! 		  && find_reg_note (insn, REG_SETJMP, NULL_RTX))
! 		clobbers_all = true;
! #endif
! 
! 	      for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
! 		if (clobbers_all
! 		    || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
! 		  already_set[regno] = 1;
  	    }
  
  	  pat = PATTERN (insn);
  	  note_stores (pat, reg_set_info, NULL);
  
  	  /* Now that we've marked regs, look for stores.  */
! 	  find_moveable_store (insn, already_set, last_set_in);
! 
! 	  /* Unmark regs that are no longer set.  */
! 	  for (regno = 0; regno < max_gcse_regno; regno++)
! 	    if (last_set_in[regno] == INSN_UID (insn))
! 	      last_set_in[regno] = 0;
! 	}
! 
!       /* Clear temporary marks.  */
!       for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
! 	{
! 	  LAST_AVAIL_CHECK_FAILURE(ptr) = NULL_RTX;
! 	  if (ANTIC_STORE_LIST (ptr)
! 	      && (tmp = XEXP (ANTIC_STORE_LIST (ptr), 0)) == NULL_RTX)
! 	    ANTIC_STORE_LIST (ptr) = XEXP (ANTIC_STORE_LIST (ptr), 1);
! 	}
!     }
! 
!   /* Remove the stores that are not available anywhere, as there will
!      be no opportunity to optimize them.  */
!   for (ptr = pre_ldst_mems, prev_next_ptr_ptr = &pre_ldst_mems;
!        ptr != NULL;
!        ptr = *prev_next_ptr_ptr)
!     {
!       if (!AVAIL_STORE_LIST (ptr))
! 	{
! 	  *prev_next_ptr_ptr = ptr->next;
! 	  free_ldst_entry (ptr);
  	}
+       else
+ 	prev_next_ptr_ptr = &ptr->next;
      }
  
    ret = enumerate_ldsts ();
  
    if (gcse_file)
      {
!       fprintf (gcse_file, "ST_avail and ST_antic (shown under loads..)\n");
        print_ldst_list (gcse_file);
      }
  
+   free (last_set_in);
+   free (already_set);
    return ret;
  }
  
  /* Check to see if the load X is aliased with STORE_PATTERN.  */
  
! static bool
  load_kills_store (x, store_pattern)
       rtx x, store_pattern;
  {
    if (true_dependence (x, GET_MODE (x), store_pattern, rtx_addr_varies_p))
!     return true;
!   return false;
  }
  
  /* Go through the entire insn X, looking for any loads which might alias
!    STORE_PATTERN.  Return true if found.  */
  
! static bool
  find_loads (x, store_pattern)
       rtx x, store_pattern;
  {
    const char * fmt;
    int i, j;
!   int ret = false;
  
    if (!x)
!     return false;
  
    if (GET_CODE (x) == SET)
      x = SET_SRC (x);
*************** find_loads (x, store_pattern)
*** 7089,7095 ****
    if (GET_CODE (x) == MEM)
      {
        if (load_kills_store (x, store_pattern))
! 	return 1;
      }
  
    /* Recursively process the insn.  */
--- 7292,7298 ----
    if (GET_CODE (x) == MEM)
      {
        if (load_kills_store (x, store_pattern))
! 	return true;
      }
  
    /* Recursively process the insn.  */
*************** find_loads (x, store_pattern)
*** 7107,7120 ****
  }
  
  /* Check if INSN kills the store pattern X (is aliased with it).
!    Return 1 if it it does.  */
  
! static int
  store_killed_in_insn (x, insn)
       rtx x, insn;
  {
    if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
!     return 0;
  
    if (GET_CODE (insn) == CALL_INSN)
      {
--- 7310,7323 ----
  }
  
  /* Check if INSN kills the store pattern X (is aliased with it).
!    Return true if it it does.  */
  
! static bool
  store_killed_in_insn (x, insn)
       rtx x, insn;
  {
    if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
!     return false;
  
    if (GET_CODE (insn) == CALL_INSN)
      {
*************** store_killed_in_insn (x, insn)
*** 7130,7209 ****
        if (GET_CODE (SET_DEST (pat)) == MEM && !expr_equiv_p (SET_DEST (pat), x))
  	/* pretend its a load and check for aliasing.  */
  	if (find_loads (SET_DEST (pat), x))
! 	  return 1;
        return find_loads (SET_SRC (pat), x);
      }
    else
      return find_loads (PATTERN (insn), x);
  }
  
! /* Returns 1 if the expression X is loaded or clobbered on or after INSN
!    within basic block BB.  */
  
! static int
! store_killed_after (x, insn, bb)
!      rtx x, insn;
       basic_block bb;
  {
!   rtx last = bb->end;
! 
!   if (insn == last)
!     return 0;
  
!   /* Check if the register operands of the store are OK in this block.
!      Note that if registers are changed ANYWHERE in the block, we'll
!      decide we can't move it, regardless of whether it changed above
!      or below the store. This could be improved by checking the register
!      operands while looking for aliasing in each insn.  */
!   if (!store_ops_ok (XEXP (x, 0), bb))
!     return 1;
! 
!   for ( ; insn && insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
!     if (store_killed_in_insn (x, insn))
!       return 1;
  
!   return 0;
  }
! 
! /* Returns 1 if the expression X is loaded or clobbered on or before INSN
!    within basic block BB.  */
! static int
! store_killed_before (x, insn, bb)
!      rtx x, insn;
       basic_block bb;
  {
    rtx first = bb->head;
  
!   if (insn == first)
!     return store_killed_in_insn (x, insn);
! 
!   /* Check if the register operands of the store are OK in this block.
!      Note that if registers are changed ANYWHERE in the block, we'll
!      decide we can't move it, regardless of whether it changed above
!      or below the store. This could be improved by checking the register
!      operands while looking for aliasing in each insn.  */
!   if (!store_ops_ok (XEXP (x, 0), bb))
!     return 1;
  
!   for ( ; insn && insn != PREV_INSN (first); insn = PREV_INSN (insn))
      if (store_killed_in_insn (x, insn))
!       return 1;
  
!   return 0;
  }
! 
! #define ANTIC_STORE_LIST(x)	((x)->loads)
! #define AVAIL_STORE_LIST(x)	((x)->stores)
! 
! /* Given the table of available store insns at the end of blocks,
!    determine which ones are not killed by aliasing, and generate
!    the appropriate vectors for gen and killed.  */
  static void
  build_store_vectors ()
  {
!   basic_block bb, b;
    rtx insn, st;
    struct ls_expr * ptr;
  
    /* Build the gen_vector. This is any store in the table which is not killed
       by aliasing later in its block.  */
--- 7333,7410 ----
        if (GET_CODE (SET_DEST (pat)) == MEM && !expr_equiv_p (SET_DEST (pat), x))
  	/* pretend its a load and check for aliasing.  */
  	if (find_loads (SET_DEST (pat), x))
! 	  return true;
        return find_loads (SET_SRC (pat), x);
      }
    else
      return find_loads (PATTERN (insn), x);
  }
  
! /* Returns true if the expression X is loaded or clobbered on or after INSN
!    within basic block BB.  REGS_SET_AFTER is bitmap of registers set in
!    or after the insn.  X_REGS is list of registers mentioned in X. If the store
!    is killed, return the last insn in that it occurs in FAIL_INSN.  */
  
! static bool
! store_killed_after (x, x_regs, insn, bb, regs_set_after, fail_insn)
!      rtx x, x_regs, insn;
       basic_block bb;
+      int *regs_set_after;
+      rtx *fail_insn;
  {
!   rtx last = bb->end, act;
  
!   if (!store_ops_ok (x_regs, regs_set_after))
!     { 
!       /* We do not know where it will happen.  */
!       if (fail_insn)
! 	*fail_insn = NULL_RTX;
!       return true;
!     }
! 
!   /* Scan from the end, so that fail_insn is determined correctly.  */
!   for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act))
!     if (store_killed_in_insn (x, act))
!       {
! 	if (fail_insn)
! 	  *fail_insn = act;
! 	return true;
!       }
  
!   return false;
  }
!   
! /* Returns true if the expression X is loaded or clobbered on or before INSN
!    within basic block BB. X_REGS is list of registers mentioned in X.
!    REGS_SET_BEFORE is bitmap of registers set before or in this insn.  */
! static bool
! store_killed_before (x, x_regs, insn, bb, regs_set_before)
!      rtx x, x_regs, insn;
       basic_block bb;
+      int *regs_set_before;
  {
    rtx first = bb->head;
  
!   if (!store_ops_ok (x_regs, regs_set_before))
!     return true;
  
!   for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
      if (store_killed_in_insn (x, insn))
!       return true;
  
!   return false;
  }
!   
! /* Fill in available, anticipatable, transparent and kill vectors in
!    STORE_DATA, based on lists of available and anticipatable stores.  */
  static void
  build_store_vectors ()
  {
!   basic_block bb;
!   int *regs_set_in_block;
    rtx insn, st;
    struct ls_expr * ptr;
+   unsigned regno;
  
    /* Build the gen_vector. This is any store in the table which is not killed
       by aliasing later in its block.  */
*************** build_store_vectors ()
*** 7215,7269 ****
  
    for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
      {
!       /* Put all the stores into either the antic list, or the avail list,
! 	 or both.  */
!       rtx store_list = ptr->stores;
!       ptr->stores = NULL_RTX;
! 
!       for (st = store_list; st != NULL; st = XEXP (st, 1))
  	{
  	  insn = XEXP (st, 0);
  	  bb = BLOCK_FOR_INSN (insn);
  
! 	  if (!store_killed_after (ptr->pattern, insn, bb))
  	    {
! 	      /* If we've already seen an available expression in this block,
! 		 we can delete the one we saw already (It occurs earlier in
! 		 the block), and replace it with this one). We'll copy the
! 		 old SRC expression to an unused register in case there
! 		 are any side effects.  */
! 	      if (TEST_BIT (ae_gen[bb->index], ptr->index))
! 		{
! 		  /* Find previous store.  */
! 		  rtx st;
! 		  for (st = AVAIL_STORE_LIST (ptr); st ; st = XEXP (st, 1))
! 		    if (BLOCK_FOR_INSN (XEXP (st, 0)) == bb)
! 		      break;
! 		  if (st)
! 		    {
! 		      rtx r = gen_reg_rtx (GET_MODE (ptr->pattern));
! 		      if (gcse_file)
! 			fprintf (gcse_file, "Removing redundant store:\n");
! 		      replace_store_insn (r, XEXP (st, 0), bb);
! 		      XEXP (st, 0) = insn;
! 		      continue;
! 		    }
! 		}
! 	      SET_BIT (ae_gen[bb->index], ptr->index);
! 	      AVAIL_STORE_LIST (ptr) = alloc_INSN_LIST (insn,
! 							AVAIL_STORE_LIST (ptr));
! 	    }
! 
! 	  if (!store_killed_before (ptr->pattern, insn, bb))
! 	    {
! 	      SET_BIT (st_antloc[BLOCK_NUM (insn)], ptr->index);
! 	      ANTIC_STORE_LIST (ptr) = alloc_INSN_LIST (insn,
! 							ANTIC_STORE_LIST (ptr));
  	    }
  	}
  
!       /* Free the original list of store insns.  */
!       free_INSN_LIST_list (&store_list);
      }
  
    ae_kill = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
--- 7416,7447 ----
  
    for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
      {
!       for (st = AVAIL_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1))
  	{
  	  insn = XEXP (st, 0);
  	  bb = BLOCK_FOR_INSN (insn);
  
! 	  /* If we've already seen an available expression in this block,
! 	     we can delete this one (It occurs earlier in the block). We'll
! 	     copy the SRC expression to an unused register in case there
! 	     are any side effects.  */
! 	  if (TEST_BIT (ae_gen[bb->index], ptr->index))
  	    {
! 	      rtx r = gen_reg_rtx (GET_MODE (ptr->pattern));
! 	      if (gcse_file)
! 		fprintf (gcse_file, "Removing redundant store:\n");
! 	      replace_store_insn (r, XEXP (st, 0), bb);
! 	      continue;
  	    }
+ 	  SET_BIT (ae_gen[bb->index], ptr->index);
  	}
  
!       for (st = ANTIC_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1))
! 	{
! 	  insn = XEXP (st, 0);
! 	  bb = BLOCK_FOR_INSN (insn);
! 	  SET_BIT (st_antloc[bb->index], ptr->index);
! 	}
      }
  
    ae_kill = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
*************** build_store_vectors ()
*** 7271,7312 ****
  
    transp = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
    sbitmap_vector_zero (transp, last_basic_block);
  
!   for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
!     FOR_EACH_BB (b)
!       {
! 	if (store_killed_after (ptr->pattern, b->head, b))
! 	  {
! 	    /* The anticipatable expression is not killed if it's gen'd.  */
! 	    /*
! 	      We leave this check out for now. If we have a code sequence
! 	      in a block which looks like:
! 			ST MEMa = x
! 			L     y = MEMa
! 			ST MEMa = z
! 	      We should flag this as having an ANTIC expression, NOT
! 	      transparent, NOT killed, and AVAIL.
! 	      Unfortunately, since we haven't re-written all loads to
! 	      use the reaching reg, we'll end up doing an incorrect
! 	      Load in the middle here if we push the store down. It happens in
! 		    gcc.c-torture/execute/960311-1.c with -O3
! 	      If we always kill it in this case, we'll sometimes do
! 	      unnecessary work, but it shouldn't actually hurt anything.
! 	    if (!TEST_BIT (ae_gen[b], ptr->index)).  */
! 	    SET_BIT (ae_kill[b->index], ptr->index);
! 	  }
! 	else
! 	  SET_BIT (transp[b->index], ptr->index);
!       }
  
-   /* Any block with no exits calls some non-returning function, so
-      we better mark the store killed here, or we might not store to
-      it at all.  If we knew it was abort, we wouldn't have to store,
-      but we don't know that for sure.  */
    if (gcse_file)
      {
-       fprintf (gcse_file, "ST_avail and ST_antic (shown under loads..)\n");
-       print_ldst_list (gcse_file);
        dump_sbitmap_vector (gcse_file, "st_antloc", "", st_antloc, last_basic_block);
        dump_sbitmap_vector (gcse_file, "st_kill", "", ae_kill, last_basic_block);
        dump_sbitmap_vector (gcse_file, "Transpt", "", transp, last_basic_block);
--- 7449,7481 ----
  
    transp = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
    sbitmap_vector_zero (transp, last_basic_block);
+   regs_set_in_block = xmalloc (sizeof (int) * max_gcse_regno);
  
!   FOR_EACH_BB (bb)
!     {
!       for (regno = 0; regno < max_gcse_regno; regno++)
! 	regs_set_in_block[regno] = TEST_BIT (reg_set_in_block[bb->index], regno);
! 
!       for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
! 	{
! 	  if (store_killed_after (ptr->pattern, ptr->pattern_regs, bb->head,
! 				  bb, regs_set_in_block, NULL))
! 	    {
! 	      /* It should not be neccessary to consider the expression
! 		 killed if it is both anticipatable and available.  */
! 	      if (!TEST_BIT (st_antloc[bb->index], ptr->index)
! 		  || !TEST_BIT (ae_gen[bb->index], ptr->index))
! 		SET_BIT (ae_kill[bb->index], ptr->index);
!   	    }
!   	  else
!   	    SET_BIT (transp[bb->index], ptr->index);
!        	}
!     }
! 
!   free (regs_set_in_block);
  
    if (gcse_file)
      {
        dump_sbitmap_vector (gcse_file, "st_antloc", "", st_antloc, last_basic_block);
        dump_sbitmap_vector (gcse_file, "st_kill", "", ae_kill, last_basic_block);
        dump_sbitmap_vector (gcse_file, "Transpt", "", transp, last_basic_block);
*************** insert_store (expr, e)
*** 7367,7373 ****
      return 0;
  
    reg = expr->reaching_reg;
!   insn = gen_move_insn (expr->pattern, reg);
  
    /* If we are inserting this expression on ALL predecessor edges of a BB,
       insert it at the start of the BB, and reset the insert bits on the other
--- 7536,7542 ----
      return 0;
  
    reg = expr->reaching_reg;
!   insn = gen_move_insn (copy_rtx (expr->pattern), reg);
  
    /* If we are inserting this expression on ALL predecessor edges of a BB,
       insert it at the start of the BB, and reset the insert bits on the other
*************** delete_store (expr, bb)
*** 7455,7463 ****
    if (expr->reaching_reg == NULL_RTX)
      expr->reaching_reg = gen_reg_rtx (GET_MODE (expr->pattern));
  
- 
-   /* If there is more than 1 store, the earlier ones will be dead,
-      but it doesn't hurt to replace them here.  */
    reg = expr->reaching_reg;
  
    for (i = AVAIL_STORE_LIST (expr); i; i = XEXP (i, 1))
--- 7624,7629 ----
*************** store_motion ()
*** 7519,7525 ****
  
    init_alias_analysis ();
  
!   /* Find all the stores that are live to the end of their block.  */
    num_stores = compute_store_table ();
    if (num_stores == 0)
      {
--- 7685,7691 ----
  
    init_alias_analysis ();
  
!   /* Find all the available and anticipatable stores.  */
    num_stores = compute_store_table ();
    if (num_stores == 0)
      {
*************** store_motion ()
*** 7528,7536 ****
        return;
      }
  
!   /* Now compute whats actually available to move.  */
!   add_noreturn_fake_exit_edges ();
    build_store_vectors ();
  
    edge_list = pre_edge_rev_lcm (gcse_file, num_stores, transp, ae_gen,
  				st_antloc, ae_kill, &pre_insert_map,
--- 7694,7702 ----
        return;
      }
  
!   /* Now compute kill & transp vectors.  */
    build_store_vectors ();
+   add_noreturn_fake_exit_edges ();
  
    edge_list = pre_edge_rev_lcm (gcse_file, num_stores, transp, ae_gen,
  				st_antloc, ae_kill, &pre_insert_map,



More information about the Gcc-patches mailing list