/* Move constant computations out of loops.   Copyright (C) 1987, 1988, 1989 Free Software Foundation, Inc.This file is part of GNU CC.GNU CC is free software; you can redistribute it and/or modifyit under the terms of the GNU General Public License as published bythe Free Software Foundation; either version 1, or (at your option)any later version.GNU CC is distributed in the hope that it will be useful,but WITHOUT ANY WARRANTY; without even the implied warranty ofMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See theGNU General Public License for more details.You should have received a copy of the GNU General Public Licensealong with GNU CC; see the file COPYING.  If not, write tothe Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  *//* This is the loop optimization pass of the compiler.   It finds invariant computations within loops and moves them   to the beginning of the loop.  Then it identifies basic and    general induction variables.  Strength reduction is applied to the general   induction variables, and induction variable elimination is applied to   the basic induction variables.   It also finds cases where   a register is set within the loop by zero-extending a narrower value   and changes these to zero the entire register once before the loop   and merely copy the low part within the loop.   Most of the complexity is in heuristics to decide when it is worth   while to do these things.  *//* ??? verify_loop would run faster if we made one table   of the minimum and maximum luids from which each label is reached.   Also, it would be faster if loop_store_addrs were a hash table.  */#include "config.h"#include "rtl.h"#include "expr.h"#include "insn-config.h"#include "regs.h"#include "hard-reg-set.h"#include "recog.h"#include "flags.h"#include <stdio.h>/* Vector mapping INSN_UIDs to luids.   The luids are like uids but increase monononically always.   We use them to see whether a jump comes from outside a given loop.  */static int *uid_luid;/* Get the luid of an insn.  */#define INSN_LUID(INSN) (uid_luid[INSN_UID (INSN)])/* 1 + largest uid of any insn.  */static int max_uid;/* 1 + luid of last insn.  */static int max_luid;/* Nonzero if somewhere in the current loop   there is either a subroutine call,   or a store into a memory address that is not fixed,   or a store in a BLKmode memory operand,   or too many different fixed addresses stored in   to record them all in `loop_store_addrs'.   In any of these cases, no memory location can be regarded   as invariant.  */static int unknown_address_altered;/* Nonzero if somewhere in the current loop there is a store   into a memory address that is not fixed but is known to be   part of an aggregate.   In this case, no memory reference in an aggregate may be   considered invariant.  */static int unknown_aggregate_altered;/* Nonzero if somewhere in the current loop there is a store   into a memory address other than a fixed address not in an aggregate.   In this case, no memory reference in an aggregate at a varying address   may be considered invariant.  */static int fixed_aggregate_altered;/* Nonzero if there is a subroutine call in the current loop.   (unknown_address_altered is also nonzero in this case.)  */static int loop_has_call;/* Nonzero if there is a volatile memory reference in the current   loop.  */static int loop_has_volatile;/* Added loop_continue which is the NOTE_INSN_LOOP_CONT of the   current loop.  A continue statement will generate a branch to   NEXT_INSN (loop_continue).  */static rtx loop_continue;/* Indexed by register number, contains the number of times the reg   is set during the loop being scanned.   During code motion, -1 indicates a reg that has been made a candidate.   After code motion, regs moved have 0 (which is accurate now)   while the failed candidates have the original number of times set.   Therefore, at all times, 0 indicates an invariant register;   -1 a conditionally invariant one.  */static short *n_times_set;/* Original value of n_times_set; same except that this value   is not set to -1 for a reg whose sets have been made candidates   and not set to 0 for a reg that is moved.  */static short *n_times_used;/* Index by register number, 1 indicates that the register   cannot be moved or strength reduced.  */static char *may_not_optimize;/* Nonzero means reg N has already been moved out of one loop.   This reduces the desire to move it out of another.  */static char *moved_once;/* Array of fixed memory addresses that are stored in this loop.   If there are too many to fit here,   we just turn on unknown_address_altered.  */#define NUM_STORES 10static rtx loop_store_addrs[NUM_STORES];static int loop_store_widths[NUM_STORES];/* Index of first available slot in above array.  */static int loop_store_addrs_idx;/* Count of movable (i.e. invariant) instructions discovered in the loop.  */static int num_movables;/* Count of memory write instructions discovered in the loop.  */static int num_mem_sets;/* Number of loops contained within the current one, including itself.  */static int loops_enclosed;/* Bound on pseudo register number before loop optimization.   A pseudo has valid regscan info if its number is < old_max_reg.  */static int old_max_reg;/* During the analysis of a loop, a chain of `struct movable's   is made to record all the movable insns found.   Then the entire chain can be scanned to decide which to move.  */struct movable{  rtx insn;			/* A movable insn */  rtx set_src;                  /* The expression this reg is set from.				   Either SET_SRC (body) or a REG_EQUAL.  */  int consec;			/* Number of consecutive following insns 				   that must be moved with this one.  */  int regno;			/* The register it sets */  short lifetime;		/* lifetime of that register;				   may be adjusted when matching movables				   that load the same value are found.  */  short savings;		/* Number of insns we can move for this reg,				   including other movables that force this				   or match this one.  */  unsigned int cond : 1;	/* 1 if only conditionally movable */  unsigned int force : 1;	/* 1 means MUST move this insn */  unsigned int global : 1;	/* 1 means reg is live outside this loop */		/* If PARTIAL is 1, GLOBAL means something different:		   that the reg is live outside the range from where it is set		   to the following label.  */  unsigned int done : 1;	/* 1 inhibits further processing of this */  /* 1 in PARTIAL means this reg is used for zero-extending.     In particular, moving it does not make it invariant.  */  unsigned int partial : 1;  enum machine_mode savemode;   /* Nonzero means it is a mode for a low part				   that we should avoid changing when clearing				   the rest of the reg.  */  struct movable *match;	/* First entry for same value */  struct movable *forces;	/* An insn that must be moved if this is */  struct movable *next;};static FILE *loop_dump_stream;/* Forward declarations.  */struct induction;struct iv_class;static rtx loop_find_reg_equal ();static int reg_in_basic_block_p ();static rtx verify_loop ();static int invariant_p ();static int consec_sets_invariant_p ();static int can_jump_into_range_p ();static int labels_in_range_p ();static void count_loop_regs_set ();static void note_addr_stored ();static int loop_reg_used_before_p ();static void constant_high_bytes ();static void scan_loop ();static rtx replace_regs ();static void replace_call_address ();static rtx skip_consec_insns ();static void ignore_some_movables ();static void force_movables ();static void combine_movables ();static int rtx_equal_for_loop_p ();static void move_movables ();static void strength_reduce ();static void find_mem_givs ();static void record_giv ();static void delete_insn_forces ();static int basic_induction_var ();static int general_induction_var ();static int consec_sets_giv ();static int check_dbra_loop ();static void emit_iv_init_code ();static int product_cheap_p ();static void emit_iv_inc ();static void check_eliminate_biv ();static int can_eliminate_biv_p ();static void eliminate_biv ();static rtx final_biv_value ();static int last_use_this_basic_block ();/* Entry point of this file.  Perform loop optimization   on the current function.  F is the first insn of the function   and DUMPFILE is a stream for output of a trace of actions taken   (or 0 if none should be output).  */voidloop_optimize (f, dumpfile)     /* f is the first instruction of a chain of insns for one function */     rtx f;     FILE *dumpfile;{  register rtx insn;  register int i;  rtx end;  rtx last_insn;  loop_dump_stream = dumpfile;  init_recog ();  old_max_reg = max_reg_num ();  moved_once = (char *) alloca (old_max_reg);  bzero (moved_once, old_max_reg);  /* First find the last real insn, and count the number of insns,     and assign insns their luids.  */  for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))    if (INSN_UID (insn) > i)      i = INSN_UID (insn);  max_uid = i + 1;  uid_luid = (int *) alloca ((i + 1) * sizeof (int));  bzero (uid_luid, (i + 1) * sizeof (int));  /* Compute the mapping from uids to luids.     LUIDs are numbers assigned to insns, like uids,     except that luids increase monotonically through the code.     Don't assign luids to line-number NOTEs, so that the distance in luids     between two insns is not affected by -g.  */  for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))    {      last_insn = insn;      if (GET_CODE (insn) != NOTE	  || NOTE_LINE_NUMBER (insn) < 0)	INSN_LUID (insn) = ++i;      else	/* Give a line number note the same luid as preceding insn.  */	INSN_LUID (insn) = i;    }  max_luid = i;  /* Don't leave gaps in uid_luid for insns that have been     deleted.  It is possible that the first or last insn     using some register has been deleted by cross-jumping.     Make sure that uid_luid for that former insn's uid     points to the general area where that insn used to be.  */  for (i = 0; i < max_uid; i++)    {      uid_luid[0] = uid_luid[i];      if (uid_luid[0] != 0)	break;    }  for (i = 0; i < max_uid; i++)    if (uid_luid[i] == 0)      uid_luid[i] = uid_luid[i - 1];  /* Find and process each loop.     We scan from the end, and process each loop when its start is seen,     so we process innermost loops first.  */  for (insn = last_insn; insn; insn = PREV_INSN (insn))    if (GET_CODE (insn) == NOTE	&& NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)      {	/* Make sure it really is a loop -- no jumps in from outside.  */	end = verify_loop (f, insn);	if (end != 0)	  /* If so, optimize this loop.  */	  scan_loop (insn, end, max_reg_num ());	else if (loop_dump_stream)	  fprintf (loop_dump_stream,		   "\nLoop at %d ignored due to multiple entry points.\n",		   INSN_UID (insn));      }}/* Optimize one loop whose start is LOOP_START and end is END.   LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching   NOTE_INSN_LOOP_END.  *//* ??? can also move memory writes out of loop if destination   address is invariant? */static voidscan_loop (loop_start, end, nregs)     rtx loop_start, end;     int nregs;{  register int i;  register rtx p = NEXT_INSN (loop_start);  /* 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;  /* For a rotated loop that is entered near the bottom,     this is the label at the top.  Otherwise it is zero.  */  rtx loop_top = 0;  /* Jump insn that enters the loop, or 0 if control drops in.  */  rtx loop_entry_jump = 0;  /* Place in the loop where control enters.  */  rtx scan_start;  /* Number of insns in the loop.  */  int insn_count;  int tem;  rtx temp;  /* 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 = loop_has_call ? 15 : 30;  /* Nonzero if the insn that jumps into the real loop     is not the very first thing after the loop-beginning note.  */  int something_before_entry_jump = 0;  n_times_set = (short *) alloca (nregs * sizeof (short));  n_times_used = (short *) alloca (nregs * sizeof (short));  may_not_optimize = (char *) alloca (nregs);  /* Determine whether this loop starts with a jump down     to a test at the end.  */  while (p != end	 && GET_CODE (p) != CODE_LABEL && GET_CODE (p) != JUMP_INSN)    {      if (GET_CODE (p) == CALL_INSN || GET_CODE (p) == INSN)	something_before_entry_jump = 1;      p = NEXT_INSN (p);    }  /* "Loop" contains neither jumps nor labels;     it must have been a dummy.  Think no more about it.  */  if (p == end)    return;  scan_start = p;  /* If loop has a jump before the first label,     the true entry is the target of that jump.     Start scan from there.     But record in LOOP_TOP the place where the end-test jumps     back to so we can scan that after the end of the loop.  */  if (GET_CODE (p) == JUMP_INSN)    {      loop_entry_jump = p;      loop_top = NEXT_INSN (p);      /* Loop entry will never be a conditional jump.	 If we see one, this must not be a real loop.	 Also, a return-insn isn't a jump to enter the loop.  */      if (GET_CODE (loop_top) != BARRIER	  || GET_CODE (PATTERN (p)) != SET)	return;      /* Get the label at which the loop is entered.  */      p = XEXP (SET_SRC (PATTERN (p)), 0);      /* Check to see whether the jump actually	 jumps out of the loop (meaning it's no loop).	 This case can happen for things like	 do {..} while (0).  */      if (p == 0	  || INSN_LUID (p) < INSN_LUID (loop_start)	  || INSN_LUID (p) >= INSN_LUID (end))	{	  if (loop_dump_stream)	    fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",		     INSN_UID (loop_start), INSN_UID (end));	  return;	}      /* Find the first label after the entry-jump.  */      while (GET_CODE (loop_top) != CODE_LABEL)	{	  loop_top = NEXT_INSN (loop_top);	  if (loop_top == 0)	    abort ();	}      /* Maybe rearrange the loop to drop straight in	 with a new test to jump around it entirely.	 (The latter is considered outside the loop.)	 If this is done, we no longer enter with a jump.  */      if (! something_before_entry_jump	  && loop_skip_over (loop_start, end, loop_entry_jump))