More loop cleanups

Jan Hubicka hubicka@atrey.karlin.mff.cuni.cz
Tue Apr 25 07:53:00 GMT 2000


Hi
This patch reorganizes loop somewhat in order to make more use of
for_each_insn_in_loop infrastructure bit.  I've found that scan_loop contains
very related code to calculate MAYBE_NEVER flag for the insn, this code is
partially copied into load_mems code, where it is quite over-conservative and
partly broken.

So I've extended for_each_insn_in_loop to pass those information as well and
created new LIF flags.  I am using them now in the hoisting code and in the
strength reduction. As the side effect, the loop hoisting code is now much less
strict about jumps inside loop and is able to hoist more memory references than
originally.  The patch is actually quite long, but basically is just moves code
around.

Honza

Tue Apr 18 12:00:14 CEST 2000  Jan Hubicka  <jh@suse.cz>
	* loop.h (LIF_MAYBE_NEVER, LIF_CALL_PASSED, LIF_NOT_EVERY_ITERATION,
	LIF_MAYBE_MULTIPLE): New macro.
	(loop_insn_callback): Accept flags and custom data arguments.
	(for_each_insn_in_loop): New parameter data.
	* loop.c (last_movable): New global variable.
	(load_mems_and_recount_loop_regs_set): Parameter loop is no longer
	const.
	(load_mems): Likewise.
	(check_insn_for_givs, check_insn_for_bivs): Update for new
	loop_insn_callback.
	(check_insn_for_loop_mems): New.
	(scan_insn): Break out from ...
	(scan_loop): ... here; Use the_movables everywhere instead of movables;
	do not caluclate unused loop_entry_jump; call check_insn_for_loop_mems
	(prescan_loop): Do not call insert_loop_mem.
	(for_each_insn_in_loop): New parameter data; calculate flags MAYBE_NEVER
	and CALL_PASSED.
	(insert_loop_mem): Get lif information from the data, don't set optimize
	for MAYBE_NEVER or CALL_PASSED flags.
	(replace_mem_references): Break out from ...
	(load_mems): ... here; don't take care for maybe_never flag.

*** /potvora/d/LOOP/LOOP.H	Tue Apr 24 09:55:20 2001
--- loop.h	Tue Apr 18 11:42:45 2000
*************** Boston, MA 02111-1307, USA.  */
*** 21,26 ****
--- 21,32 ----
  #include "varray.h"
  #include "basic-block.h"
  
+ /* Loop's insn flags set by for_each_insn_in_loop.  */
+ #define LIF_MAYBE_NEVER 1
+ #define LIF_CALL_PASSED 2
+ #define LIF_NOT_EVERY_ITERATION 4
+ #define LIF_MAYBE_MULTIPLE 8
+ 
  /* Get the loop info pointer of a loop.  */
  #define LOOP_INFO(LOOP) ((struct loop_info *) (LOOP)->aux) 
  
*************** void emit_unrolled_add PARAMS ((rtx, rtx
*** 247,252 ****
  int back_branch_in_range_p PARAMS ((const struct loop *, rtx));
  
  int loop_insn_first_p PARAMS ((rtx, rtx));
! typedef rtx (*loop_insn_callback ) PARAMS ((struct loop *, rtx, int, int));
! void for_each_insn_in_loop PARAMS ((struct loop *, loop_insn_callback));
  
--- 253,258 ----
  int back_branch_in_range_p PARAMS ((const struct loop *, rtx));
  
  int loop_insn_first_p PARAMS ((rtx, rtx));
! typedef rtx (*loop_insn_callback ) PARAMS ((struct loop *, rtx, int, void *));
! void for_each_insn_in_loop PARAMS ((struct loop *, loop_insn_callback, void *));
  
*** /potvora/d/LOOP/LOOP.C	Tue Apr 24 09:55:18 2001
--- loop.c	Tue Apr 18 12:02:54 2000
*************** struct movable
*** 226,231 ****
--- 226,233 ----
  };
  
  static struct movable *the_movables;
+ /* Last element in `the_movables' -- so we can add elements at the end.  */
+ static struct movable *last_movable = 0;
  
  FILE *loop_dump_stream;
  
*************** static int last_use_this_basic_block PAR
*** 299,315 ****
  static void record_initial PARAMS ((rtx, rtx, void *));
  static void update_reg_last_use PARAMS ((rtx, rtx));
  static rtx next_insn_in_loop PARAMS ((const struct loop *, rtx));
! static void load_mems_and_recount_loop_regs_set PARAMS ((const struct loop*,
  							 int *));
! static void load_mems PARAMS ((const struct loop *));
  static int insert_loop_mem PARAMS ((rtx *, void *));
  static int replace_loop_mem PARAMS ((rtx *, void *));
  static int replace_loop_reg PARAMS ((rtx *, void *));
  static void note_reg_stored PARAMS ((rtx, rtx, void *));
  static void try_copy_prop PARAMS ((const struct loop *, rtx, unsigned int));
  static int replace_label PARAMS ((rtx *, void *));
! static rtx check_insn_for_givs PARAMS((struct loop *, rtx, int, int));
! static rtx check_insn_for_bivs PARAMS((struct loop *, rtx, int, int));
  
  typedef struct rtx_and_int {
    rtx r;
--- 301,319 ----
  static void record_initial PARAMS ((rtx, rtx, void *));
  static void update_reg_last_use PARAMS ((rtx, rtx));
  static rtx next_insn_in_loop PARAMS ((const struct loop *, rtx));
! static void load_mems_and_recount_loop_regs_set PARAMS ((struct loop*,
  							 int *));
! static void load_mems PARAMS ((struct loop *));
  static int insert_loop_mem PARAMS ((rtx *, void *));
  static int replace_loop_mem PARAMS ((rtx *, void *));
  static int replace_loop_reg PARAMS ((rtx *, void *));
  static void note_reg_stored PARAMS ((rtx, rtx, void *));
  static void try_copy_prop PARAMS ((const struct loop *, rtx, unsigned int));
  static int replace_label PARAMS ((rtx *, void *));
! static rtx check_insn_for_givs PARAMS((struct loop *, rtx, int, void *));
! static rtx check_insn_for_bivs PARAMS((struct loop *, rtx, int, void *));
! static rtx check_insn_for_loop_mems PARAMS((struct loop *, rtx, int, void *));
! static rtx scan_insn PARAMS((struct loop *, rtx, int, void *));
  
  typedef struct rtx_and_int {
    rtx r;
*************** next_insn_in_loop (loop, insn)
*** 580,585 ****
--- 584,904 ----
  
    return insn;
  }
+ 
+   /* Find insns that are safe to move.  Set set_in_loop negative for
+      the reg being set, so that this reg will be considered invariant
+      for subsequent insns.  We consider whether subsequent insns use
+      the reg in deciding whether it is worth actually moving.
+ 
+      LIF_MAYBE_NEVER is set if we have passed a conditional jump insn
+      and therefore it is possible that the insns we are scanning
+      would never be executed.  At such times, we must make sure
+      that it is safe to execute the insn once instead of zero times.
+      When LIF_MAYBE_NEVER is not set, all insns will be executed at least
+      once so that is not a problem.  */
+ rtx
+ scan_insn (loop, p, lif, data)
+      struct loop *loop;
+      rtx p;
+      int lif;
+      void *data ATTRIBUTE_UNUSED;
+ {
+   rtx set, set1;
+   rtx temp;
+   int tem;
+   /* Additional information about the current loop being processed
+      that is used to compute the number of loop iterations for loop
+      unrolling and doloop optimization.  */
+   struct loop_info *loop_info = LOOP_INFO (loop);
+ 
+   if (GET_CODE (p) == INSN
+       && (set = single_set (p))
+       && GET_CODE (SET_DEST (set)) == REG
+       && ! VARRAY_CHAR (may_not_optimize, REGNO (SET_DEST (set))))
+     {
+       int tem1 = 0;
+       int tem2 = 0;
+       int move_insn = 0;
+       rtx src = SET_SRC (set);
+       rtx dependencies = 0;
+ 
+       /* Figure out what to use as a source of this insn.  If a REG_EQUIV
+ 	 note is given or if a REG_EQUAL note with a constant operand is
+ 	 specified, use it as the source and mark that we should move
+ 	 this insn by calling emit_move_insn rather that duplicating the
+ 	 insn.
+ 
+ 	 Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
+ 	 is present.  */
+       temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
+       if (temp)
+ 	src = XEXP (temp, 0), move_insn = 1;
+       else 
+ 	{
+ 	  temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
+ 	  if (temp && CONSTANT_P (XEXP (temp, 0)))
+ 	    src = XEXP (temp, 0), move_insn = 1;
+ 	  if (temp && find_reg_note (p, REG_RETVAL, NULL_RTX))
+ 	    {
+ 	      src = XEXP (temp, 0);
+ 	      /* A libcall block can use regs that don't appear in
+ 		 the equivalent expression.  To move the libcall,
+ 		 we must move those regs too.  */
+ 	      dependencies = libcall_other_reg (p, src);
+ 	    }
+ 	}
+ 
+       /* Don't try to optimize a register that was made
+ 	 by loop-optimization for an inner loop.
+ 	 We don't know its life-span, so we can't compute the benefit.  */
+       if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
+ 	;
+       else if (/* The register is used in basic blocks other
+ 		  than the one where it is set (meaning that
+ 		  something after this point in the loop might
+ 		  depend on its value before the set).  */
+ 	       ! reg_in_basic_block_p (p, SET_DEST (set))
+ 	       /* And the set is not guaranteed to be executed one
+ 		  the loop starts, or the value before the set is
+ 		  needed before the set occurs... 
+ 
+ 		  ??? Note we have quadratic behaviour here, mitigated
+ 		  by the fact that the previous test will often fail for
+ 		  large loops.  Rather than re-scanning the entire loop
+ 		  each time for register usage, we should build tables
+ 		  of the register usage and use them here instead.  */
+ 	       && ((lif & LIF_MAYBE_NEVER)
+ 		   || loop_reg_used_before_p (loop, set, p)))
+ 	/* It is unsafe to move the set.  
+ 
+ 	   This code used to consider it OK to move a set of a variable
+ 	   which was not created by the user and not used in an exit test.
+ 	   That behavior is incorrect and was removed.  */
+ 	;
+       else if ((tem = loop_invariant_p (loop, src))
+ 	       && (dependencies == 0
+ 		   || (tem2 = loop_invariant_p (loop, dependencies)) != 0)
+ 	       && (VARRAY_INT (set_in_loop, 
+ 			       REGNO (SET_DEST (set))) == 1
+ 		   || (tem1
+ 		       = consec_sets_invariant_p 
+ 		       (loop, SET_DEST (set),
+ 			VARRAY_INT (set_in_loop, REGNO (SET_DEST (set))),
+ 			p)))
+ 	       /* If the insn can cause a trap (such as divide by zero),
+ 		  can't move it unless it's guaranteed to be executed
+ 		  once loop is entered.  Even a function call might
+ 		  prevent the trap insn from being reached
+ 		  (since it might exit!)  */
+ 	       && ! ((lif & (LIF_MAYBE_NEVER | LIF_CALL_PASSED))
+ 		     && may_trap_p (src)))
+ 	{
+ 	  register struct movable *m;
+ 	  register int regno = REGNO (SET_DEST (set));
+ 
+ 	  /* A potential lossage is where we have a case where two insns
+ 	     can be combined as long as they are both in the loop, but
+ 	     we move one of them outside the loop.  For large loops,
+ 	     this can lose.  The most common case of this is the address
+ 	     of a function being called.  
+ 
+ 	     Therefore, if this register is marked as being used exactly
+ 	     once if we are in a loop with calls (a "large loop"), see if
+ 	     we can replace the usage of this register with the source
+ 	     of this SET.  If we can, delete this insn. 
+ 
+ 	     Don't do this if P has a REG_RETVAL note or if we have
+ 	     SMALL_REGISTER_CLASSES and SET_SRC is a hard register.  */
+ 
+ 	  if (loop_info->has_call
+ 	      && VARRAY_RTX (reg_single_usage, regno) != 0
+ 	      && VARRAY_RTX (reg_single_usage, regno) != const0_rtx
+ 	      && REGNO_FIRST_UID (regno) == INSN_UID (p)
+ 	      && (REGNO_LAST_UID (regno)
+ 		  == INSN_UID (VARRAY_RTX (reg_single_usage, regno)))
+ 	      && VARRAY_INT (set_in_loop, regno) == 1
+ 	      && ! side_effects_p (SET_SRC (set))
+ 	      && ! find_reg_note (p, REG_RETVAL, NULL_RTX)
+ 	      && (! SMALL_REGISTER_CLASSES
+ 		  || (! (GET_CODE (SET_SRC (set)) == REG
+ 			 && REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)))
+ 	      /* This test is not redundant; SET_SRC (set) might be
+ 		 a call-clobbered register and the life of REGNO
+ 		 might span a call.  */
+ 	      && ! modified_between_p (SET_SRC (set), p,
+ 				       VARRAY_RTX
+ 				       (reg_single_usage, regno)) 
+ 	      && no_labels_between_p (p, VARRAY_RTX (reg_single_usage, regno))
+ 	      && validate_replace_rtx (SET_DEST (set), SET_SRC (set),
+ 				       VARRAY_RTX
+ 				       (reg_single_usage, regno))) 
+ 	    {
+ 	      /* Replace any usage in a REG_EQUAL note.  Must copy the
+ 		 new source, so that we don't get rtx sharing between the
+ 		 SET_SOURCE and REG_NOTES of insn p.  */
+ 	      REG_NOTES (VARRAY_RTX (reg_single_usage, regno))
+ 		= replace_rtx (REG_NOTES (VARRAY_RTX
+ 					  (reg_single_usage, regno)), 
+ 			       SET_DEST (set), copy_rtx (SET_SRC (set)));
+ 			       
+ 	      PUT_CODE (p, NOTE);
+ 	      NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
+ 	      NOTE_SOURCE_FILE (p) = 0;
+ 	      VARRAY_INT (set_in_loop, regno) = 0;
+ 	      return p;
+ 	    }
+ 
+ 	  m = (struct movable *) oballoc (sizeof (struct movable));
+ 	  m->next = 0;
+ 	  m->insn = p;
+ 	  m->set_src = src;
+ 	  m->dependencies = dependencies;
+ 	  m->set_dest = SET_DEST (set);
+ 	  m->force = 0;
+ 	  m->consec = VARRAY_INT (set_in_loop, 
+ 				  REGNO (SET_DEST (set))) - 1;
+ 	  m->done = 0;
+ 	  m->forces = 0;
+ 	  m->partial = 0;
+ 	  m->move_insn = move_insn;
+ 	  m->move_insn_first = 0;
+ 	  m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
+ 	  m->savemode = VOIDmode;
+ 	  m->regno = regno;
+ 	  /* Set M->cond if either loop_invariant_p
+ 	     or consec_sets_invariant_p returned 2
+ 	     (only conditionally invariant).  */
+ 	  m->cond = ((tem | tem1 | tem2) > 1);
+ 	  m->global = (uid_luid[REGNO_LAST_UID (regno)] 
+ 		       > INSN_LUID (loop->end)
+ 		       || uid_luid[REGNO_FIRST_UID (regno)] < INSN_LUID (loop->start));
+ 	  m->match = 0;
+ 	  m->lifetime = (uid_luid[REGNO_LAST_UID (regno)]
+ 			 - uid_luid[REGNO_FIRST_UID (regno)]);
+ 	  m->savings = VARRAY_INT (n_times_set, regno);
+ 	  if (find_reg_note (p, REG_RETVAL, NULL_RTX))
+ 	    m->savings += libcall_benefit (p);
+ 	  VARRAY_INT (set_in_loop, regno) = move_insn ? -2 : -1;
+ 	  /* Add M to the end of the chain MOVABLES.  */
+ 	  if (the_movables == 0)
+ 	    the_movables = m;
+ 	  else
+ 	    last_movable->next = m;
+ 	  last_movable = m;
+ 
+ 	  if (m->consec > 0)
+ 	    {
+ 	      /* It is possible for the first instruction to have a
+ 		 REG_EQUAL note but a non-invariant SET_SRC, so we must
+ 		 remember the status of the first instruction in case
+ 		 the last instruction doesn't have a REG_EQUAL note.  */
+ 	      m->move_insn_first = m->move_insn;
+ 
+ 	      /* Skip this insn, not checking REG_LIBCALL notes.  */
+ 	      p = next_nonnote_insn (p);
+ 	      /* Skip the consecutive insns, if there are any.  */
+ 	      p = skip_consec_insns (p, m->consec);
+ 	      /* Back up to the last insn of the consecutive group.  */
+ 	      p = prev_nonnote_insn (p);
+ 
+ 	      /* We must now reset m->move_insn, m->is_equiv, and possibly
+ 		 m->set_src to correspond to the effects of all the
+ 		 insns.  */
+ 	      temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
+ 	      if (temp)
+ 		m->set_src = XEXP (temp, 0), m->move_insn = 1;
+ 	      else
+ 		{
+ 		  temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
+ 		  if (temp && CONSTANT_P (XEXP (temp, 0)))
+ 		    m->set_src = XEXP (temp, 0), m->move_insn = 1;
+ 		  else
+ 		    m->move_insn = 0;
+ 
+ 		}
+ 	      m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
+ 	    }
+ 	}
+       /* If this register is always set within a STRICT_LOW_PART
+ 	 or set to zero, then its high bytes are constant.
+ 	 So clear them outside the loop and within the loop
+ 	 just load the low bytes.
+ 	 We must check that the machine has an instruction to do so.
+ 	 Also, if the value loaded into the register
+ 	 depends on the same register, this cannot be done.  */
+       else if (SET_SRC (set) == const0_rtx
+ 	       && GET_CODE (NEXT_INSN (p)) == INSN
+ 	       && (set1 = single_set (NEXT_INSN (p)))
+ 	       && GET_CODE (set1) == SET
+ 	       && (GET_CODE (SET_DEST (set1)) == STRICT_LOW_PART)
+ 	       && (GET_CODE (XEXP (SET_DEST (set1), 0)) == SUBREG)
+ 	       && (SUBREG_REG (XEXP (SET_DEST (set1), 0))
+ 		   == SET_DEST (set))
+ 	       && !reg_mentioned_p (SET_DEST (set), SET_SRC (set1)))
+ 	{
+ 	  register int regno = REGNO (SET_DEST (set));
+ 	  if (VARRAY_INT (set_in_loop, regno) == 2)
+ 	    {
+ 	      register struct movable *m;
+ 	      m = (struct movable *) alloca (sizeof (struct movable));
+ 	      m->next = 0;
+ 	      m->insn = p;
+ 	      m->set_dest = SET_DEST (set);
+ 	      m->dependencies = 0;
+ 	      m->force = 0;
+ 	      m->consec = 0;
+ 	      m->done = 0;
+ 	      m->forces = 0;
+ 	      m->move_insn = 0;
+ 	      m->move_insn_first = 0;
+ 	      m->partial = 1;
+ 	      /* If the insn may not be executed on some cycles,
+ 		 we can't clear the whole reg; clear just high part.
+ 		 Not even if the reg is used only within this loop.
+ 		 Consider this:
+ 		 while (1)
+ 		   while (s != t) {
+ 		     if (foo ()) x = *s;
+ 		     use (x);
+ 		   }
+ 		 Clearing x before the inner loop could clobber a value
+ 		 being saved from the last time around the outer loop.
+ 		 However, if the reg is not used outside this loop
+ 		 and all uses of the register are in the same
+ 		 basic block as the store, there is no problem.
+ 
+ 		 If this insn was made by loop, we don't know its
+ 		 INSN_LUID and hence must make a conservative
+ 		 assumption.  */
+ 	      m->global = (INSN_UID (p) >= max_uid_for_loop
+ 			   || (uid_luid[REGNO_LAST_UID (regno)]
+ 			       > INSN_LUID (loop->end))
+ 			   || (uid_luid[REGNO_FIRST_UID (regno)]
+ 			       < INSN_LUID (p))
+ 			   || (labels_in_range_p
+ 			       (p, uid_luid[REGNO_FIRST_UID (regno)])));
+ 	      if ((lif & LIF_MAYBE_NEVER) && m->global)
+ 		m->savemode = GET_MODE (SET_SRC (set1));
+ 	      else
+ 		m->savemode = VOIDmode;
+ 	      m->regno = regno;
+ 	      m->cond = 0;
+ 	      m->match = 0;
+ 	      m->lifetime = (uid_luid[REGNO_LAST_UID (regno)]
+ 			     - uid_luid[REGNO_FIRST_UID (regno)]);
+ 	      m->savings = 1;
+ 	      VARRAY_INT (set_in_loop, regno) = -1;
+ 	      /* Add M to the end of the chain MOVABLES.  */
+ 	      if (the_movables == 0)
+ 		the_movables = m;
+ 	      else
+ 		last_movable->next = m;
+ 	      last_movable = m;
+ 	    }
+ 	}
+     }
+   return p;
+ }
  
  /* Optimize one loop described by LOOP.  */
  
*************** scan_loop (loop, unroll_p, bct_p)
*** 602,635 ****
       unrolling and doloop optimization.  */
    struct loop_info *loop_info = LOOP_INFO (loop);
    rtx p;
-   /* 1 if we are scanning insns that could be executed zero times.  */
-   int maybe_never = 0;
-   /* 1 if we are scanning insns that might never be executed
-      due to a subroutine call which might exit before they are reached.  */
-   int call_passed = 0;
-   /* Jump insn that enters the loop, or 0 if control drops in.  */
-   rtx loop_entry_jump = 0;
    /* Number of insns in the loop.  */
    int insn_count;
!   int in_libcall = 0;
!   int tem;
!   rtx temp, update_start, update_end;
!   /* The SET from an insn, if it is the only SET in the insn.  */
!   rtx set, set1;
!   /* Chain describing insns movable in current loop.  */
!   struct movable *movables = 0;
!   /* Last element in `movables' -- so we can add elements at the end.  */
!   struct movable *last_movable = 0;
    /* Ratio of extra register life span we can justify
       for saving an instruction.  More if loop doesn't call subroutines
       since in that case saving an insn makes more difference
       and more registers are available.  */
    int threshold;
-   /* Nonzero if we are scanning instructions in a sub-loop.  */
-   int loop_depth = 0;
    int nregs;
  
    loop->top = 0;
  
    /* Determine whether this loop starts with a jump down to a test at
       the end.  This will occur for a small number of loops with a test
--- 921,938 ----
       unrolling and doloop optimization.  */
    struct loop_info *loop_info = LOOP_INFO (loop);
    rtx p;
    /* Number of insns in the loop.  */
    int insn_count;
!   rtx update_start, update_end;
    /* Ratio of extra register life span we can justify
       for saving an instruction.  More if loop doesn't call subroutines
       since in that case saving an insn makes more difference
       and more registers are available.  */
    int threshold;
    int nregs;
  
    loop->top = 0;
+   the_movables = 0;
  
    /* Determine whether this loop starts with a jump down to a test at
       the end.  This will occur for a small number of loops with a test
*************** scan_loop (loop, unroll_p, bct_p)
*** 669,676 ****
       back to so we can scan that after the end of the loop.  */
    if (GET_CODE (p) == JUMP_INSN)
      {
-       loop_entry_jump = p;
- 
        /* Loop entry must be unconditional jump (and not a RETURN)  */
        if (simplejump_p (p)
  	  && JUMP_LABEL (p) != 0
--- 972,977 ----
*************** scan_loop (loop, unroll_p, bct_p)
*** 748,1116 ****
  		 INSN_UID (loop->cont));
      }
  
!   /* Scan through the loop finding insns that are safe to move.
!      Set set_in_loop negative for the reg being set, so that
!      this reg will be considered invariant for subsequent insns.
!      We consider whether subsequent insns use the reg
!      in deciding whether it is worth actually moving.
! 
!      MAYBE_NEVER is nonzero if we have passed a conditional jump insn
!      and therefore it is possible that the insns we are scanning
!      would never be executed.  At such times, we must make sure
!      that it is safe to execute the insn once instead of zero times.
!      When MAYBE_NEVER is 0, all insns will be executed at least once
!      so that is not a problem.  */
! 
!   for (p = next_insn_in_loop (loop, loop->scan_start); 
!        p != NULL_RTX;
!        p = next_insn_in_loop (loop, p))
!     {
!       if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
! 	  && find_reg_note (p, REG_LIBCALL, NULL_RTX))
! 	in_libcall = 1;
!       else if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
! 	       && find_reg_note (p, REG_RETVAL, NULL_RTX))
! 	in_libcall = 0;
! 
!       if (GET_CODE (p) == INSN
! 	  && (set = single_set (p))
! 	  && GET_CODE (SET_DEST (set)) == REG
! 	  && ! VARRAY_CHAR (may_not_optimize, REGNO (SET_DEST (set))))
! 	{
! 	  int tem1 = 0;
! 	  int tem2 = 0;
! 	  int move_insn = 0;
! 	  rtx src = SET_SRC (set);
! 	  rtx dependencies = 0;
! 
! 	  /* Figure out what to use as a source of this insn.  If a REG_EQUIV
! 	     note is given or if a REG_EQUAL note with a constant operand is
! 	     specified, use it as the source and mark that we should move
! 	     this insn by calling emit_move_insn rather that duplicating the
! 	     insn.
! 
! 	     Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
! 	     is present.  */
! 	  temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
! 	  if (temp)
! 	    src = XEXP (temp, 0), move_insn = 1;
! 	  else 
! 	    {
! 	      temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
! 	      if (temp && CONSTANT_P (XEXP (temp, 0)))
! 		src = XEXP (temp, 0), move_insn = 1;
! 	      if (temp && find_reg_note (p, REG_RETVAL, NULL_RTX))
! 		{
! 		  src = XEXP (temp, 0);
! 		  /* A libcall block can use regs that don't appear in
! 		     the equivalent expression.  To move the libcall,
! 		     we must move those regs too.  */
! 		  dependencies = libcall_other_reg (p, src);
! 		}
! 	    }
! 
! 	  /* Don't try to optimize a register that was made
! 	     by loop-optimization for an inner loop.
! 	     We don't know its life-span, so we can't compute the benefit.  */
! 	  if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
! 	    ;
! 	  else if (/* The register is used in basic blocks other
! 		      than the one where it is set (meaning that
! 		      something after this point in the loop might
! 		      depend on its value before the set).  */
! 		   ! reg_in_basic_block_p (p, SET_DEST (set))
! 		   /* And the set is not guaranteed to be executed one
! 		      the loop starts, or the value before the set is
! 		      needed before the set occurs... 
! 
! 		      ??? Note we have quadratic behaviour here, mitigated
! 		      by the fact that the previous test will often fail for
! 		      large loops.  Rather than re-scanning the entire loop
! 		      each time for register usage, we should build tables
! 		      of the register usage and use them here instead.  */
! 		   && (maybe_never
! 		       || loop_reg_used_before_p (loop, set, p)))
! 	    /* It is unsafe to move the set.  
! 
! 	       This code used to consider it OK to move a set of a variable
! 	       which was not created by the user and not used in an exit test.
! 	       That behavior is incorrect and was removed.  */
! 	    ;
! 	  else if ((tem = loop_invariant_p (loop, src))
! 		   && (dependencies == 0
! 		       || (tem2 = loop_invariant_p (loop, dependencies)) != 0)
! 		   && (VARRAY_INT (set_in_loop, 
! 				   REGNO (SET_DEST (set))) == 1
! 		       || (tem1
! 			   = consec_sets_invariant_p 
! 			   (loop, SET_DEST (set),
! 			    VARRAY_INT (set_in_loop, REGNO (SET_DEST (set))),
! 			    p)))
! 		   /* If the insn can cause a trap (such as divide by zero),
! 		      can't move it unless it's guaranteed to be executed
! 		      once loop is entered.  Even a function call might
! 		      prevent the trap insn from being reached
! 		      (since it might exit!)  */
! 		   && ! ((maybe_never || call_passed)
! 			 && may_trap_p (src)))
! 	    {
! 	      register struct movable *m;
! 	      register int regno = REGNO (SET_DEST (set));
! 
! 	      /* A potential lossage is where we have a case where two insns
! 		 can be combined as long as they are both in the loop, but
! 		 we move one of them outside the loop.  For large loops,
! 		 this can lose.  The most common case of this is the address
! 		 of a function being called.  
! 
! 		 Therefore, if this register is marked as being used exactly
! 		 once if we are in a loop with calls (a "large loop"), see if
! 		 we can replace the usage of this register with the source
! 		 of this SET.  If we can, delete this insn. 
! 
! 		 Don't do this if P has a REG_RETVAL note or if we have
! 		 SMALL_REGISTER_CLASSES and SET_SRC is a hard register.  */
! 
! 	      if (loop_info->has_call
! 		  && VARRAY_RTX (reg_single_usage, regno) != 0
! 		  && VARRAY_RTX (reg_single_usage, regno) != const0_rtx
! 		  && REGNO_FIRST_UID (regno) == INSN_UID (p)
! 		  && (REGNO_LAST_UID (regno)
! 		      == INSN_UID (VARRAY_RTX (reg_single_usage, regno)))
! 		  && VARRAY_INT (set_in_loop, regno) == 1
! 		  && ! side_effects_p (SET_SRC (set))
! 		  && ! find_reg_note (p, REG_RETVAL, NULL_RTX)
! 		  && (! SMALL_REGISTER_CLASSES
! 		      || (! (GET_CODE (SET_SRC (set)) == REG
! 			     && REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)))
! 		  /* This test is not redundant; SET_SRC (set) might be
! 		     a call-clobbered register and the life of REGNO
! 		     might span a call.  */
! 		  && ! modified_between_p (SET_SRC (set), p,
! 					   VARRAY_RTX
! 					   (reg_single_usage, regno)) 
! 		  && no_labels_between_p (p, VARRAY_RTX (reg_single_usage, regno))
! 		  && validate_replace_rtx (SET_DEST (set), SET_SRC (set),
! 					   VARRAY_RTX
! 					   (reg_single_usage, regno))) 
! 		{
! 		  /* Replace any usage in a REG_EQUAL note.  Must copy the
! 		     new source, so that we don't get rtx sharing between the
! 		     SET_SOURCE and REG_NOTES of insn p.  */
! 		  REG_NOTES (VARRAY_RTX (reg_single_usage, regno))
! 		    = replace_rtx (REG_NOTES (VARRAY_RTX
! 					      (reg_single_usage, regno)), 
! 				   SET_DEST (set), copy_rtx (SET_SRC (set)));
! 				   
! 		  PUT_CODE (p, NOTE);
! 		  NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
! 		  NOTE_SOURCE_FILE (p) = 0;
! 		  VARRAY_INT (set_in_loop, regno) = 0;
! 		  continue;
! 		}
! 
! 	      m = (struct movable *) alloca (sizeof (struct movable));
! 	      m->next = 0;
! 	      m->insn = p;
! 	      m->set_src = src;
! 	      m->dependencies = dependencies;
! 	      m->set_dest = SET_DEST (set);
! 	      m->force = 0;
! 	      m->consec = VARRAY_INT (set_in_loop, 
! 				      REGNO (SET_DEST (set))) - 1;
! 	      m->done = 0;
! 	      m->forces = 0;
! 	      m->partial = 0;
! 	      m->move_insn = move_insn;
! 	      m->move_insn_first = 0;
! 	      m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
! 	      m->savemode = VOIDmode;
! 	      m->regno = regno;
! 	      /* Set M->cond if either loop_invariant_p
! 		 or consec_sets_invariant_p returned 2
! 		 (only conditionally invariant).  */
! 	      m->cond = ((tem | tem1 | tem2) > 1);
! 	      m->global = (uid_luid[REGNO_LAST_UID (regno)] 
! 			   > INSN_LUID (loop_end)
! 			   || uid_luid[REGNO_FIRST_UID (regno)] < INSN_LUID (loop_start));
! 	      m->match = 0;
! 	      m->lifetime = (uid_luid[REGNO_LAST_UID (regno)]
! 			     - uid_luid[REGNO_FIRST_UID (regno)]);
! 	      m->savings = VARRAY_INT (n_times_set, regno);
! 	      if (find_reg_note (p, REG_RETVAL, NULL_RTX))
! 		m->savings += libcall_benefit (p);
! 	      VARRAY_INT (set_in_loop, regno) = move_insn ? -2 : -1;
! 	      /* Add M to the end of the chain MOVABLES.  */
! 	      if (movables == 0)
! 		movables = m;
! 	      else
! 		last_movable->next = m;
! 	      last_movable = m;
! 
! 	      if (m->consec > 0)
! 		{
! 		  /* It is possible for the first instruction to have a
! 		     REG_EQUAL note but a non-invariant SET_SRC, so we must
! 		     remember the status of the first instruction in case
! 		     the last instruction doesn't have a REG_EQUAL note.  */
! 		  m->move_insn_first = m->move_insn;
! 
! 		  /* Skip this insn, not checking REG_LIBCALL notes.  */
! 		  p = next_nonnote_insn (p);
! 		  /* Skip the consecutive insns, if there are any.  */
! 		  p = skip_consec_insns (p, m->consec);
! 		  /* Back up to the last insn of the consecutive group.  */
! 		  p = prev_nonnote_insn (p);
! 
! 		  /* We must now reset m->move_insn, m->is_equiv, and possibly
! 		     m->set_src to correspond to the effects of all the
! 		     insns.  */
! 		  temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
! 		  if (temp)
! 		    m->set_src = XEXP (temp, 0), m->move_insn = 1;
! 		  else
! 		    {
! 		      temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
! 		      if (temp && CONSTANT_P (XEXP (temp, 0)))
! 			m->set_src = XEXP (temp, 0), m->move_insn = 1;
! 		      else
! 			m->move_insn = 0;
  
! 		    }
! 		  m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
! 		}
! 	    }
! 	  /* If this register is always set within a STRICT_LOW_PART
! 	     or set to zero, then its high bytes are constant.
! 	     So clear them outside the loop and within the loop
! 	     just load the low bytes.
! 	     We must check that the machine has an instruction to do so.
! 	     Also, if the value loaded into the register
! 	     depends on the same register, this cannot be done.  */
! 	  else if (SET_SRC (set) == const0_rtx
! 		   && GET_CODE (NEXT_INSN (p)) == INSN
! 		   && (set1 = single_set (NEXT_INSN (p)))
! 		   && GET_CODE (set1) == SET
! 		   && (GET_CODE (SET_DEST (set1)) == STRICT_LOW_PART)
! 		   && (GET_CODE (XEXP (SET_DEST (set1), 0)) == SUBREG)
! 		   && (SUBREG_REG (XEXP (SET_DEST (set1), 0))
! 		       == SET_DEST (set))
! 		   && !reg_mentioned_p (SET_DEST (set), SET_SRC (set1)))
! 	    {
! 	      register int regno = REGNO (SET_DEST (set));
! 	      if (VARRAY_INT (set_in_loop, regno) == 2)
! 		{
! 		  register struct movable *m;
! 		  m = (struct movable *) alloca (sizeof (struct movable));
! 		  m->next = 0;
! 		  m->insn = p;
! 		  m->set_dest = SET_DEST (set);
! 		  m->dependencies = 0;
! 		  m->force = 0;
! 		  m->consec = 0;
! 		  m->done = 0;
! 		  m->forces = 0;
! 		  m->move_insn = 0;
! 		  m->move_insn_first = 0;
! 		  m->partial = 1;
! 		  /* If the insn may not be executed on some cycles,
! 		     we can't clear the whole reg; clear just high part.
! 		     Not even if the reg is used only within this loop.
! 		     Consider this:
! 		     while (1)
! 		       while (s != t) {
! 		         if (foo ()) x = *s;
! 			 use (x);
! 		       }
! 		     Clearing x before the inner loop could clobber a value
! 		     being saved from the last time around the outer loop.
! 		     However, if the reg is not used outside this loop
! 		     and all uses of the register are in the same
! 		     basic block as the store, there is no problem.
! 
! 		     If this insn was made by loop, we don't know its
! 		     INSN_LUID and hence must make a conservative
! 		     assumption.  */
! 		  m->global = (INSN_UID (p) >= max_uid_for_loop
! 			       || (uid_luid[REGNO_LAST_UID (regno)]
! 				   > INSN_LUID (loop_end))
! 			       || (uid_luid[REGNO_FIRST_UID (regno)]
! 				   < INSN_LUID (p))
! 			       || (labels_in_range_p
! 				   (p, uid_luid[REGNO_FIRST_UID (regno)])));
! 		  if (maybe_never && m->global)
! 		    m->savemode = GET_MODE (SET_SRC (set1));
! 		  else
! 		    m->savemode = VOIDmode;
! 		  m->regno = regno;
! 		  m->cond = 0;
! 		  m->match = 0;
! 		  m->lifetime = (uid_luid[REGNO_LAST_UID (regno)]
! 				 - uid_luid[REGNO_FIRST_UID (regno)]);
! 		  m->savings = 1;
! 		  VARRAY_INT (set_in_loop, regno) = -1;
! 		  /* Add M to the end of the chain MOVABLES.  */
! 		  if (movables == 0)
! 		    movables = m;
! 		  else
! 		    last_movable->next = m;
! 		  last_movable = m;
! 		}
! 	    }
! 	}
!       /* Past a call insn, we get to insns which might not be executed
! 	 because the call might exit.  This matters for insns that trap.
! 	 Call insns inside a REG_LIBCALL/REG_RETVAL block always return,
! 	 so they don't count.  */
!       else if (GET_CODE (p) == CALL_INSN && ! in_libcall)
! 	call_passed = 1;
!       /* Past a label or a jump, we get to insns for which we
! 	 can't count on whether or how many times they will be
! 	 executed during each iteration.  Therefore, we can
! 	 only move out sets of trivial variables
! 	 (those not used after the loop).  */
!       /* Similar code appears twice in strength_reduce.  */
!       else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
! 	       /* If we enter the loop in the middle, and scan around to the
! 		  beginning, don't set maybe_never for that.  This must be an
! 		  unconditional jump, otherwise the code at the top of the
! 		  loop might never be executed.  Unconditional jumps are
! 		  followed a by barrier then loop end.  */
!                && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop->top
! 		     && NEXT_INSN (NEXT_INSN (p)) == loop_end
! 		     && simplejump_p (p)))
! 	maybe_never = 1;
!       else if (GET_CODE (p) == NOTE)
! 	{
! 	  /* At the virtual top of a converted loop, insns are again known to
! 	     be executed: logically, the loop begins here even though the exit
! 	     code has been duplicated.  */
! 	  if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP && loop_depth == 0)
! 	    maybe_never = call_passed = 0;
! 	  else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
! 	    loop_depth++;
! 	  else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
! 	    loop_depth--;
! 	}
!     }
  
    /* If one movable subsumes another, ignore that other.  */
  
!   ignore_some_movables (movables);
  
    /* For each movable insn, see if the reg that it loads
       leads when it dies right into another conditionally movable insn.
       If so, record that the second insn "forces" the first one,
       since the second can be moved only if the first is.  */
  
!   force_movables (movables);
  
    /* See if there are multiple movable insns that load the same value.
       If there are, make all but the first point at the first one
       through the `match' field, and add the priorities of them
       all together as the priority of the first.  */
  
!   combine_movables (movables, nregs);
  	
    /* Now consider each movable insn to decide whether it is worth moving.
       Store 0 in set_in_loop for each reg that is moved.
--- 1049,1085 ----
  		 INSN_UID (loop->cont));
      }
  
!   if (/* We can't tell what MEMs are aliased by what.  */
!       ! unknown_address_altered
!       /* We don't want loads for MEMs moved to a location before the
! 	 one at which their stack memory becomes allocated.  (Note
! 	 that this is not a problem for malloc, etc., since those
! 	 require actual function calls).  */
!       && ! current_function_calls_alloca
!       /* There are ways to leave the loop other than falling off the
! 	 end.  */
!       && ! loop_info->has_multiple_exit_targets)
!     for_each_insn_in_loop (loop, check_insn_for_loop_mems, NULL);
  
!   for_each_insn_in_loop (loop, scan_insn, NULL);
  
    /* If one movable subsumes another, ignore that other.  */
  
!   ignore_some_movables (the_movables);
  
    /* For each movable insn, see if the reg that it loads
       leads when it dies right into another conditionally movable insn.
       If so, record that the second insn "forces" the first one,
       since the second can be moved only if the first is.  */
  
!   force_movables (the_movables);
  
    /* See if there are multiple movable insns that load the same value.
       If there are, make all but the first point at the first one
       through the `match' field, and add the priorities of them
       all together as the priority of the first.  */
  
!   combine_movables (the_movables, nregs);
  	
    /* Now consider each movable insn to decide whether it is worth moving.
       Store 0 in set_in_loop for each reg that is moved.
*************** scan_loop (loop, unroll_p, bct_p)
*** 1119,1125 ****
       optimizing for code size.  */
  
    if (! optimize_size)
!     move_movables (loop, movables, threshold, insn_count, nregs);
  
    /* Now candidates that still are negative are those not moved.
       Change set_in_loop to indicate that those are not actually invariant.  */
--- 1088,1094 ----
       optimizing for code size.  */
  
    if (! optimize_size)
!     move_movables (loop, the_movables, threshold, insn_count, nregs);
  
    /* Now candidates that still are negative are those not moved.
       Change set_in_loop to indicate that those are not actually invariant.  */
*************** scan_loop (loop, unroll_p, bct_p)
*** 1143,1149 ****
  
    if (flag_strength_reduce)
      {
-       the_movables = movables;
        strength_reduce (loop, insn_count, unroll_p, bct_p);
  
        reg_scan_update (update_start, update_end, loop_max_reg);
--- 1112,1117 ----
*************** prescan_loop (loop)
*** 2517,2540 ****
        else if (GET_CODE (insn) == RETURN)
  	loop_info->has_multiple_exit_targets = 1;
      }
- 
-   /* Now, rescan the loop, setting up the LOOP_MEMS array.  */
-   if (/* We can't tell what MEMs are aliased by what.  */
-       ! unknown_address_altered 
-       /* An exception thrown by a called function might land us
- 	 anywhere.  */
-       && ! loop_info->has_call
-       /* We don't want loads for MEMs moved to a location before the
- 	 one at which their stack memory becomes allocated.  (Note
- 	 that this is not a problem for malloc, etc., since those
- 	 require actual function calls.  */
-       && ! current_function_calls_alloca
-       /* There are ways to leave the loop other than falling off the
- 	 end.  */
-       && ! loop_info->has_multiple_exit_targets)
-     for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
- 	 insn = NEXT_INSN (insn))
-       for_each_rtx (&insn, insert_loop_mem, 0);
  }
  
  /* LOOP->CONT_DOMINATOR is now the last label between the loop start
--- 2485,2490 ----
*************** static rtx addr_placeholder;
*** 3697,3736 ****
     Also, some of the optimizations could be a little less conservative.  */
  
  /* Scan the loop body and call FNCALL for each insn.  In the addition to the
!    LOOP and INSN parameters pass MAYBE_MULTIPLE and NOT_EVERY_ITERATION to the
!    callback.
   
!    NOT_EVERY_ITERATION if current insn is not executed at least once for every
     loop iteration except for the last one.
  
!    MAYBE_MULTIPLE is 1 if current insn may be executed more than once for every
     loop iteration.
   */
  void
! for_each_insn_in_loop (loop, fncall)
       struct loop *loop;
       loop_insn_callback fncall;
  {
!   /* This is 1 if current insn is not executed at least once for every loop
!      iteration.  */
!   int not_every_iteration = 0;
!   int maybe_multiple = 0;
!   int past_loop_latch = 0;
    int loop_depth = 0;
    rtx p;
  
    /* If loop_scan_start points to the loop exit test, we have to be wary of
       subversive use of gotos inside expression statements.  */
!   if (prev_nonnote_insn (loop->scan_start) != prev_nonnote_insn (loop->start))
!     maybe_multiple = back_branch_in_range_p (loop, loop->scan_start);
! 
!   /* Scan through loop to find all possible bivs.  */
  
    for (p = next_insn_in_loop (loop, loop->scan_start);
         p != NULL_RTX;
         p = next_insn_in_loop (loop, p))
      {
!       p = fncall (loop, p, not_every_iteration, maybe_multiple);
  
        /* Past CODE_LABEL, we get to insns that may be executed multiple
           times.  The only way we can be sure that they can't is if every
--- 3647,3703 ----
     Also, some of the optimizations could be a little less conservative.  */
  
  /* Scan the loop body and call FNCALL for each insn.  In the addition to the
!    LOOP and INSN parameters pass FLAGS to the callback.  Flags is bitmask of
!    following values:
   
!    LIF_NOT_EVERY_ITERATION if current insn is not executed at least once for every
     loop iteration except for the last one.
  
!    LIF_MAYBE_MULTIPLE is 1 if current insn may be executed more than once for every
     loop iteration.
+ 
+    LIF_MAYBE_NEVER is 1 if current insn could be executed zero times.
+ 
+    LIF_CALL_PASSED is 1 if current insn might never be executed
+    due to a subroutine call which might exit before they are reached.  
+  
+    The callback function returns insn where we continue scanning, so some insns
+    may be skipped, also it may return NULL to terminate the search.
   */
  void
! for_each_insn_in_loop (loop, fncall, data)
       struct loop *loop;
       loop_insn_callback fncall;
+      void *data;
  {
!   int flags = 0;
    int loop_depth = 0;
+   int in_libcall = 0;
+   int past_loop_latch = 0;
    rtx p;
  
    /* If loop_scan_start points to the loop exit test, we have to be wary of
       subversive use of gotos inside expression statements.  */
!   if (prev_nonnote_insn (loop->scan_start) != prev_nonnote_insn (loop->start)
!       && back_branch_in_range_p (loop, loop->scan_start))
!     flags |= LIF_MAYBE_MULTIPLE;
! 
!   /* Scan through loop and collect the variables we are looking for.
!      In the future we may want to rewrite all this uglyness to the basic block
!      dominator operations.  */
  
    for (p = next_insn_in_loop (loop, loop->scan_start);
         p != NULL_RTX;
         p = next_insn_in_loop (loop, p))
      {
!       p = fncall (loop, p, flags, data);
!       if (!p)
! 	return;
! 
!       if (INSN_P (p) && find_reg_note (p, REG_LIBCALL, NULL_RTX))
! 	in_libcall = 1;
!       else if (INSN_P (p) && find_reg_note (p, REG_RETVAL, NULL_RTX))
! 	in_libcall = 0;
  
        /* Past CODE_LABEL, we get to insns that may be executed multiple
           times.  The only way we can be sure that they can't is if every
*************** for_each_insn_in_loop (loop, fncall)
*** 3742,3748 ****
  	{
  	  rtx insn = p;
  
! 	  maybe_multiple = 0;
  
  	  while (1)
  	    {
--- 3709,3715 ----
  	{
  	  rtx insn = p;
  
! 	  flags &= ~LIF_MAYBE_MULTIPLE;
  
  	  while (1)
  	    {
*************** for_each_insn_in_loop (loop, fncall)
*** 3766,3789 ****
  			  && JUMP_LABEL (insn) != loop->scan_start
  			  && !loop_insn_first_p (p, JUMP_LABEL (insn)))))
  		{
! 		  maybe_multiple = 1;
  		  break;
  		}
  	    }
  	}
  
        /* Past a jump, we get to insns for which we can't count
           on whether they will be executed during each iteration.  */
-       /* This code appears twice in strength_reduce.  There is also similar
-          code in scan_loop.  */
        if (GET_CODE (p) == JUMP_INSN
        /* If we enter the loop in the middle, and scan around to the
           beginning, don't set not_every_iteration for that.
           This can be any kind of jump, since we want to know if insns
           will be executed if the loop is executed.  */
  	  && !(JUMP_LABEL (p) == loop->top
! 	     && ((NEXT_INSN (NEXT_INSN (p)) == loop->end && simplejump_p (p))
! 		 || (NEXT_INSN (p) == loop->end && condjump_p (p)))))
  	{
  	  rtx label = 0;
  
--- 3733,3772 ----
  			  && JUMP_LABEL (insn) != loop->scan_start
  			  && !loop_insn_first_p (p, JUMP_LABEL (insn)))))
  		{
! 		  flags |= LIF_MAYBE_MULTIPLE;
  		  break;
  		}
  	    }
  	}
  
+       /* Past a call insn, we get to insns which might not be executed
+ 	 because the call might exit.  This matters for insns that trap.
+ 	 Call insns inside a REG_LIBCALL/REG_RETVAL block always return,
+ 	 so they don't count.  */
+       if (GET_CODE (p) == CALL_INSN && ! in_libcall)
+ 	flags |= LIF_CALL_PASSED;
+ 
+       if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
+ 	       /* If we enter the loop in the middle, and scan around to the
+ 		  beginning, don't set maybe_never for that.  This must be an
+ 		  unconditional jump, otherwise the code at the top of the
+ 		  loop might never be executed.  Unconditional jumps are
+ 		  followed a by barrier then loop end.  */
+                && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop->top
+ 		     && NEXT_INSN (NEXT_INSN (p)) == loop->end
+ 		     && simplejump_p (p)))
+ 	flags |= LIF_MAYBE_NEVER;
+ 
        /* Past a jump, we get to insns for which we can't count
           on whether they will be executed during each iteration.  */
        if (GET_CODE (p) == JUMP_INSN
        /* If we enter the loop in the middle, and scan around to the
           beginning, don't set not_every_iteration for that.
           This can be any kind of jump, since we want to know if insns
           will be executed if the loop is executed.  */
  	  && !(JUMP_LABEL (p) == loop->top
! 	       && ((NEXT_INSN (NEXT_INSN (p)) == loop->end && simplejump_p (p))
! 		   || (NEXT_INSN (p) == loop->end && condjump_p (p)))))
  	{
  	  rtx label = 0;
  
*************** for_each_insn_in_loop (loop, fncall)
*** 3796,3802 ****
  	      break;
  
  	  if (!label)
! 	    not_every_iteration = 1;
  	}
  
        else if (GET_CODE (p) == NOTE)
--- 3779,3785 ----
  	      break;
  
  	  if (!label)
! 	    flags |= LIF_NOT_EVERY_ITERATION;
  	}
  
        else if (GET_CODE (p) == NOTE)
*************** for_each_insn_in_loop (loop, fncall)
*** 3810,3816 ****
  	  if ((NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP
  	       || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_CONT)
  	      && loop_depth == 0)
! 	    not_every_iteration = 0;
  	  else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
  	    loop_depth++;
  	  else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
--- 3793,3802 ----
  	  if ((NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP
  	       || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_CONT)
  	      && loop_depth == 0)
! 	    flags &= ~LIF_NOT_EVERY_ITERATION;
! 	  if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP
! 	      && loop_depth == 0)
! 	    flags &= ~(LIF_CALL_PASSED | LIF_MAYBE_NEVER);
  	  else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
  	    loop_depth++;
  	  else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
*************** for_each_insn_in_loop (loop, fncall)
*** 3839,3850 ****
           a jump to the top of the loop, then we know these insns will be
           executed each iteration.  */
  
!       if (not_every_iteration
  	  && !past_loop_latch
  	  && GET_CODE (p) == CODE_LABEL
  	  && no_labels_between_p (p, loop->end)
  	  && loop_insn_first_p (p, loop->cont))
! 	not_every_iteration = 0;
      }
  }
  
--- 3825,3836 ----
           a jump to the top of the loop, then we know these insns will be
           executed each iteration.  */
  
!       if ((flags & LIF_NOT_EVERY_ITERATION)
  	  && !past_loop_latch
  	  && GET_CODE (p) == CODE_LABEL
  	  && no_labels_between_p (p, loop->end)
  	  && loop_insn_first_p (p, loop->cont))
! 	flags &= ~LIF_NOT_EVERY_ITERATION;
      }
  }
  
*************** strength_reduce (loop, insn_count, unrol
*** 3904,3910 ****
    else
      end_insert_before = emit_note_after (NOTE_INSN_DELETED, loop_end);
  
!   for_each_insn_in_loop (loop, check_insn_for_bivs);
  
    /* Scan loop_iv_list to remove all regs that proved not to be bivs.
       Make a sanity check against n_times_set.  */
--- 3890,3896 ----
    else
      end_insert_before = emit_note_after (NOTE_INSN_DELETED, loop_end);
  
!   for_each_insn_in_loop (loop, check_insn_for_bivs, NULL);
  
    /* Scan loop_iv_list to remove all regs that proved not to be bivs.
       Make a sanity check against n_times_set.  */
*************** strength_reduce (loop, insn_count, unrol
*** 4398,4404 ****
  
    /* Search the loop for general induction variables.  */
  
!   for_each_insn_in_loop (loop, check_insn_for_givs);
  
    /* Try to calculate and save the number of loop iterations.  This is
       set to zero if the actual number can not be calculated.  This must
--- 4384,4390 ----
  
    /* Search the loop for general induction variables.  */
  
!   for_each_insn_in_loop (loop, check_insn_for_givs, NULL);
  
    /* Try to calculate and save the number of loop iterations.  This is
       set to zero if the actual number can not be calculated.  This must
*************** egress:
*** 5056,5066 ****
  
  /*Record all basic induction variables calculated in the insn.  */
  static rtx
! check_insn_for_bivs (loop, p, not_every_iteration, maybe_multiple)
       struct loop *loop;
       rtx p;
!      int not_every_iteration;
!      int maybe_multiple;
  {
    rtx set;
    rtx dest_reg;
--- 5042,5052 ----
  
  /*Record all basic induction variables calculated in the insn.  */
  static rtx
! check_insn_for_bivs (loop, p, lif, data)
       struct loop *loop;
       rtx p;
!      int lif;
!      void *data ATTRIBUTE_UNUSED;
  {
    rtx set;
    rtx dest_reg;
*************** check_insn_for_bivs (loop, p, not_every_
*** 5091,5097 ****
  	      = (struct induction *) oballoc (sizeof (struct induction));
  
  	      record_biv (v, p, dest_reg, inc_val, mult_val, location,
! 			  not_every_iteration, maybe_multiple,
  			  multi_insn_incr);
  	      REG_IV_TYPE (REGNO (dest_reg)) = BASIC_INDUCT;
  	    }
--- 5077,5084 ----
  	      = (struct induction *) oballoc (sizeof (struct induction));
  
  	      record_biv (v, p, dest_reg, inc_val, mult_val, location,
! 			  (lif & LIF_NOT_EVERY_ITERATION) != 0,
! 			  (lif & LIF_MAYBE_MULTIPLE) != 0,
  			  multi_insn_incr);
  	      REG_IV_TYPE (REGNO (dest_reg)) = BASIC_INDUCT;
  	    }
*************** check_insn_for_bivs (loop, p, not_every_
*** 5106,5116 ****
     A register is a giv if: it is only set once, it is a function of a
     biv and a constant (or invariant), and it is not a biv.  */
  static rtx
! check_insn_for_givs (loop, p, not_every_iteration, maybe_multiple)
       struct loop *loop;
       rtx p;
!      int not_every_iteration;
!      int maybe_multiple;
  {
    rtx set;
    /* Look for a general induction variable in a register.  */
--- 5093,5103 ----
     A register is a giv if: it is only set once, it is a function of a
     biv and a constant (or invariant), and it is not a biv.  */
  static rtx
! check_insn_for_givs (loop, p, lif, data)
       struct loop *loop;
       rtx p;
!      int lif;
!      void *data ATTRIBUTE_UNUSED;
  {
    rtx set;
    /* Look for a general induction variable in a register.  */
*************** check_insn_for_givs (loop, p, not_every_
*** 5164,5171 ****
  	    p = last_consec_insn;
  
  	  record_giv (loop, v, p, src_reg, dest_reg, mult_val, add_val,
! 		      benefit, DEST_REG, not_every_iteration,
! 		      maybe_multiple, NULL_PTR);
  
  	}
      }
--- 5151,5160 ----
  	    p = last_consec_insn;
  
  	  record_giv (loop, v, p, src_reg, dest_reg, mult_val, add_val,
! 		      benefit, DEST_REG,
! 		      (lif & LIF_NOT_EVERY_ITERATION) != 0,
! 		      (lif & LIF_MAYBE_MULTIPLE) != 0,
! 		      NULL_PTR);
  
  	}
      }
*************** check_insn_for_givs (loop, p, not_every_
*** 5175,5182 ****
    /* This resulted in worse code on a VAX 8600.  I wonder if it
       still does.  */
    if (GET_CODE (p) == INSN)
!     find_mem_givs (loop, PATTERN (p), p, not_every_iteration,
! 		   maybe_multiple);
  #endif
  
    /* Update the status of whether giv can derive other givs.  This can
--- 5164,5172 ----
    /* This resulted in worse code on a VAX 8600.  I wonder if it
       still does.  */
    if (GET_CODE (p) == INSN)
!     find_mem_givs (loop, PATTERN (p), p,
! 		   (lif & LIF_NOT_EVERY_ITERATION) != 0,
! 		   (lif & LIF_MAYBE_MULTIPLE) != 0);
  #endif
  
    /* Update the status of whether giv can derive other givs.  This can
*************** indirect_jump_in_function_p (start)
*** 9558,9565 ****
  static int
  insert_loop_mem (mem, data)
       rtx *mem;
!      void *data ATTRIBUTE_UNUSED;
  {
    int i;
    rtx m = *mem;
  
--- 9607,9615 ----
  static int
  insert_loop_mem (mem, data)
       rtx *mem;
!      void *data;
  {
+   int lif = *(int *)data;
    int i;
    rtx m = *mem;
  
*************** insert_loop_mem (mem, data)
*** 9623,9640 ****
       non-BLK mode, we'll not think we can optimize it at that point.  */
    loop_mems[loop_mems_idx].optimize = (GET_MODE (m) != BLKmode);
    loop_mems[loop_mems_idx].reg = NULL_RTX;
    ++loop_mems_idx;
  
    return 0;
  }
  
  /* Like load_mems, but also ensures that SET_IN_LOOP,
     MAY_NOT_OPTIMIZE, REG_SINGLE_USAGE, and INSN_COUNT have the correct
     values after load_mems.  */
  
  static void
  load_mems_and_recount_loop_regs_set (loop, insn_count)
!      const struct loop *loop;
       int *insn_count;
  {
    int nregs = max_reg_num ();
--- 9673,9708 ----
       non-BLK mode, we'll not think we can optimize it at that point.  */
    loop_mems[loop_mems_idx].optimize = (GET_MODE (m) != BLKmode);
    loop_mems[loop_mems_idx].reg = NULL_RTX;
+   /* We can't hoist this MEM when it may not be executed and it may
+      trap.  */
+   if ((lif & (LIF_MAYBE_NEVER | LIF_CALL_PASSED))
+       && may_trap_p (loop_mems[loop_mems_idx].mem))
+     loop_mems[loop_mems_idx].optimize = 0;
    ++loop_mems_idx;
  
    return 0;
  }
  
+ /* Called via for_each_loop_insn in prescan_loop.  */
+ rtx
+ check_insn_for_loop_mems (loop, p, lif, data)
+      struct loop *loop ATTRIBUTE_UNUSED;
+      rtx p;
+      int lif;
+      void *data ATTRIBUTE_UNUSED;
+ {
+   if (INSN_P (p))
+     for_each_rtx (&PATTERN (p), insert_loop_mem, (void *) &lif);
+   return p;
+ }
+ 
  /* Like load_mems, but also ensures that SET_IN_LOOP,
     MAY_NOT_OPTIMIZE, REG_SINGLE_USAGE, and INSN_COUNT have the correct
     values after load_mems.  */
  
  static void
  load_mems_and_recount_loop_regs_set (loop, insn_count)
!      struct loop *loop;
       int *insn_count;
  {
    int nregs = max_reg_num ();
*************** load_mems_and_recount_loop_regs_set (loo
*** 9689,9707 ****
      }
  }
  
  /* Move MEMs into registers for the duration of the loop.  */
  
  static void
  load_mems (loop)
!      const struct loop *loop;
  {
-   int maybe_never = 0;
    int i;
    rtx p;
    rtx label = NULL_RTX;
    rtx end_label = NULL_RTX;
-   /* Nonzero if the next instruction may never be executed.  */
-   int next_maybe_never = 0;
    int last_max_reg = max_reg_num ();
  
    if (loop_mems_idx == 0)
--- 9757,9817 ----
      }
  }
  
+ /* Data required by the following function.  */
+ struct replace_mem_references_data
+ {
+   int i;
+   int last_max_reg;
+   regset_head *copies;
+ };
+ 
+ /* Used by load_mems to replace all references to the MEM with the corresponding
+    pesudos.  */
+ static rtx
+ replace_mem_references (loop, p, lif, data)
+      struct loop *loop ATTRIBUTE_UNUSED;
+      rtx p;
+      int lif;
+      void *data;
+ {
+   rtx_and_int ri;
+   rtx set;
+   struct replace_mem_references_data *r = (struct replace_mem_references_data *) data;
+ 
+   if (INSN_P (p))
+     {
+       /* See if this copies the mem into a register that isn't
+          modified afterwards.  We'll try to do copy propagation
+          a little further on.  */
+       set = single_set (p);
+       if (set
+       /* @@@ This test is _way_ too conservative.
+          ??? Was this note about the maybe_never, that is calculated
+          propertly, or about the whole test?  */
+ 	  && !(lif & LIF_MAYBE_NEVER)
+ 	  && GET_CODE (SET_DEST (set)) == REG
+ 	  && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
+ 	  && REGNO (SET_DEST (set)) < r->last_max_reg
+ 	  && VARRAY_INT (n_times_set, REGNO (SET_DEST (set))) == 1
+ 	  && rtx_equal_p (SET_SRC (set), loop_mems[r->i].mem))
+ 	SET_REGNO_REG_SET (r->copies, REGNO (SET_DEST (set)));
+       ri.r = p;
+       ri.i = r->i;
+       for_each_rtx (&p, replace_loop_mem, &ri);
+     }
+   return p;
+ }
+ 
  /* Move MEMs into registers for the duration of the loop.  */
  
  static void
  load_mems (loop)
!      struct loop *loop;
  {
    int i;
    rtx p;
    rtx label = NULL_RTX;
    rtx end_label = NULL_RTX;
    int last_max_reg = max_reg_num ();
  
    if (loop_mems_idx == 0)
*************** load_mems (loop)
*** 9720,9757 ****
    for (; p != loop->start; p = NEXT_INSN (p))
      cselib_process_insn (p);
  
-   /* Check to see if it's possible that some instructions in the
-      loop are never executed.  */
-   for (p = next_insn_in_loop (loop, loop->scan_start); 
-        p != NULL_RTX && ! maybe_never; 
-        p = next_insn_in_loop (loop, p))
-     {
-       if (GET_CODE (p) == CODE_LABEL)
- 	maybe_never = 1;
-       else if (GET_CODE (p) == JUMP_INSN
- 	       /* If we enter the loop in the middle, and scan
- 		  around to the beginning, don't set maybe_never
- 		  for that.  This must be an unconditional jump,
- 		  otherwise the code at the top of the loop might
- 		  never be executed.  Unconditional jumps are
- 		  followed a by barrier then loop end.  */
- 	       && ! (GET_CODE (p) == JUMP_INSN 
- 		     && JUMP_LABEL (p) == loop->top
- 		     && NEXT_INSN (NEXT_INSN (p)) == loop->end
- 		     && simplejump_p (p)))
- 	{
- 	  if (!condjump_p (p))
- 	    /* Something complicated.  */
- 	    maybe_never = 1;
- 	  else
- 	    /* If there are any more instructions in the loop, they
- 	       might not be reached.  */
- 	    next_maybe_never = 1; 
- 	} 
-       else if (next_maybe_never)
- 	maybe_never = 1;
-     }
- 
    /* Actually move the MEMs.  */
    for (i = 0; i < loop_mems_idx; ++i) 
      {
--- 9830,9835 ----
*************** load_mems (loop)
*** 9760,9765 ****
--- 9838,9844 ----
        rtx reg;
        rtx mem = loop_mems[i].mem;
        rtx mem_list_entry;
+       struct replace_mem_references_data rd;
  
        if (MEM_VOLATILE_P (mem) 
  	  || loop_invariant_p (loop, XEXP (mem, 0)) != 1)
*************** load_mems (loop)
*** 9811,9821 ****
  	    }
  	}
  
-       if (maybe_never && may_trap_p (mem))
- 	/* We can't access the MEM outside the loop; it might
- 	   cause a trap that wouldn't have happened otherwise.  */
- 	loop_mems[i].optimize = 0;
- 	  
        if (!loop_mems[i].optimize)
  	/* We thought we were going to lift this MEM out of the
  	   loop, but later discovered that we could not.  */
--- 9890,9895 ----
*************** load_mems (loop)
*** 9833,9870 ****
  
        /* Now, replace all references to the MEM with the
  	 corresponding pesudos.  */
!       maybe_never = 0;
!       for (p = next_insn_in_loop (loop, loop->scan_start);
! 	   p != NULL_RTX;
! 	   p = next_insn_in_loop (loop, p))
! 	{
! 	  rtx_and_int ri;
! 	  rtx set;
! 
! 	  if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
! 	    {
! 	      /* See if this copies the mem into a register that isn't
! 		 modified afterwards.  We'll try to do copy propagation
! 		 a little further on.  */
! 	      set = single_set (p);
! 	      if (set
! 		  /* @@@ This test is _way_ too conservative.  */
! 		  && ! maybe_never
! 		  && GET_CODE (SET_DEST (set)) == REG
! 		  && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
! 		  && REGNO (SET_DEST (set)) < last_max_reg
! 		  && VARRAY_INT (n_times_set, REGNO (SET_DEST (set))) == 1
! 		  && rtx_equal_p (SET_SRC (set), loop_mems[i].mem))
! 		SET_REGNO_REG_SET (&copies, REGNO (SET_DEST (set)));
! 	      ri.r = p;
! 	      ri.i = i;
! 	      for_each_rtx (&p, replace_loop_mem, &ri);
! 	    }
! 
! 	  if (GET_CODE (p) == CODE_LABEL
! 	      || GET_CODE (p) == JUMP_INSN)
! 	    maybe_never = 1;
! 	}
  
        if (! apply_change_group ())
  	/* We couldn't replace all occurrences of the MEM.  */
--- 9907,9917 ----
  
        /* Now, replace all references to the MEM with the
  	 corresponding pesudos.  */
! 
!       rd.i = i;
!       rd.last_max_reg = last_max_reg;
!       rd.copies = &copies;
!       for_each_insn_in_loop (loop, replace_mem_references, &rd);
  
        if (! apply_change_group ())
  	/* We couldn't replace all occurrences of the MEM.  */


More information about the Gcc-patches mailing list