/* Perform various loop optimizations, including strength reduction.   Copyright (C) 1987, 88, 89, 91-4, 1995 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 2, 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, 59 Temple Place - Suite 330,Boston, MA 02111-1307, 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.  */#include <stdio.h>#include "config.h"#include "rtl.h"#include "obstack.h"#include "expr.h"#include "insn-config.h"#include "insn-flags.h"#include "regs.h"#include "hard-reg-set.h"#include "recog.h"#include "flags.h"#include "real.h"#include "loop.h"/* Vector mapping INSN_UIDs to luids.   The luids are like uids but increase monotonically always.   We use them to see whether a jump comes from outside a given loop.  */int *uid_luid;/* Indexed by INSN_UID, contains the ordinal giving the (innermost) loop   number the insn is contained in.  */int *uid_loop_num;/* 1 + largest uid of any insn.  */int max_uid_for_loop;/* 1 + luid of last insn.  */static int max_luid;/* Number of loops detected in current function.  Used as index to the   next few tables.  */static int max_loop_num;/* Indexed by loop number, contains the first and last insn of each loop.  */static rtx *loop_number_loop_starts, *loop_number_loop_ends;/* For each loop, gives the containing loop number, -1 if none.  */int *loop_outer_loop;/* Indexed by loop number, contains a nonzero value if the "loop" isn't   really a loop (an insn outside the loop branches into it).  */static char *loop_invalid;/* Indexed by loop number, links together all LABEL_REFs which refer to   code labels outside the loop.  Used by routines that need to know all   loop exits, such as final_biv_value and final_giv_value.   This does not include loop exits due to return instructions.  This is   because all bivs and givs are pseudos, and hence must be dead after a   return, so the presense of a return does not affect any of the   optimizations that use this info.  It is simpler to just not include return   instructions on this list.  */rtx *loop_number_exit_labels;/* Indexed by loop number, counts the number of LABEL_REFs on   loop_number_exit_labels for this loop and all loops nested inside it.  */int *loop_number_exit_count;/* Holds the number of loop iterations.  It is zero if the number could not be   calculated.  Must be unsigned since the number of iterations can   be as high as 2^wordsize-1.  For loops with a wider iterator, this number   will will be zero if the number of loop iterations is too large for an   unsigned integer to hold.  */unsigned HOST_WIDE_INT loop_n_iterations;/* 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, a negative value indicates a reg that has been   made a candidate; in particular -2 means that it is an candidate that   we know is equal to a constant and -1 means that it is an candidate   not known equal to a constant.   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;   < 0 a conditionally invariant one.  */static short *n_times_set;/* Original value of n_times_set; same except that this value   is not set negative 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 MEMs that are stored in this loop. If there are too many to fit   here, we just turn on unknown_address_altered.  */#define NUM_STORES 20static rtx loop_store_mems[NUM_STORES];/* Index of first available slot in above array.  */static int loop_store_mems_idx;/* Nonzero if we don't know what MEMs were changed in the current loop.   This happens if the loop contains a call (in which case `loop_has_call'   will also be set) or if we store into more than NUM_STORES MEMs.  */static int unknown_address_altered;/* 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 < max_reg_before_loop.  */int max_reg_before_loop;/* This obstack is used in product_cheap_p to allocate its rtl.  It   may call gen_reg_rtx which, in turn, may reallocate regno_reg_rtx.   If we used the same obstack that it did, we would be deallocating   that array.  */static struct obstack temp_obstack;/* This is where the pointer to the obstack being used for RTL is stored.  */extern struct obstack *rtl_obstack;#define obstack_chunk_alloc xmalloc#define obstack_chunk_free freeextern char *oballoc ();/* 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. */  rtx set_dest;			/* The destination of this SET. */  rtx dependencies;		/* When INSN is libcall, this is an EXPR_LIST				   of any registers used within the LIBCALL. */  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 */    unsigned int partial : 1;	/* 1 means this reg is used for zero-extending.				   In particular, moving it does not make it				   invariant.  */  unsigned int move_insn : 1;	/* 1 means that we call emit_move_insn to				   load SRC, rather than copying INSN.  */  unsigned int is_equiv : 1;	/* 1 means a REG_EQUIV is present on INSN. */  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;};FILE *loop_dump_stream;/* Forward declarations.  */static void find_and_verify_loops ();static void mark_loop_jump ();static void prescan_loop ();static int reg_in_basic_block_p ();static int consec_sets_invariant_p ();static rtx libcall_other_reg ();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 scan_loop ();static void replace_call_address ();static rtx skip_consec_insns ();static int libcall_benefit ();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 int valid_initial_value_p ();static void find_mem_givs ();static void record_biv ();static void check_final_value ();static void record_giv ();static void update_giv_derive ();static int basic_induction_var ();static rtx simplify_giv_expr ();static int general_induction_var ();static int consec_sets_giv ();static int check_dbra_loop ();static rtx express_from ();static int combine_givs_p ();static void combine_givs ();static int product_cheap_p ();static int maybe_eliminate_biv ();static int maybe_eliminate_biv_1 ();static int last_use_this_basic_block ();static void record_initial ();static void update_reg_last_use ();/* Relative gain of eliminating various kinds of operations.  */int add_cost;#if 0int shift_cost;int mult_cost;#endif/* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to   copy the value of the strength reduced giv to its original register.  */int copy_cost;voidinit_loop (){  char *free_point = (char *) oballoc (1);  rtx reg = gen_rtx (REG, word_mode, 0);  add_cost = rtx_cost (gen_rtx (PLUS, word_mode, reg, reg), SET);  /* We multiply by 2 to reconcile the difference in scale between     these two ways of computing costs.  Otherwise the cost of a copy     will be far less than the cost of an add.  */  copy_cost = 2 * 2;  /* Free the objects we just allocated.  */  obfree (free_point);  /* Initialize the obstack used for rtl in product_cheap_p.  */  gcc_obstack_init (&temp_obstack);}/* 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 last_insn;  loop_dump_stream = dumpfile;  init_recog_no_volatile ();  init_alias_analysis ();  max_reg_before_loop = max_reg_num ();  moved_once = (char *) alloca (max_reg_before_loop);  bzero (moved_once, max_reg_before_loop);  regs_may_share = 0;  /* Count the number of loops. */  max_loop_num = 0;  for (insn = f; insn; insn = NEXT_INSN (insn))    {      if (GET_CODE (insn) == NOTE	  && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)	max_loop_num++;    }  /* Don't waste time if no loops.  */  if (max_loop_num == 0)    return;  /* Get size to use for tables indexed by uids.     Leave some space for labels allocated by find_and_verify_loops.  */  max_uid_for_loop = get_max_uid () + 1 + max_loop_num * 32;  uid_luid = (int *) alloca (max_uid_for_loop * sizeof (int));  uid_loop_num = (int *) alloca (max_uid_for_loop * sizeof (int));  bzero ((char *) uid_luid, max_uid_for_loop * sizeof (int));  bzero ((char *) uid_loop_num, max_uid_for_loop * sizeof (int));  /* Allocate tables for recording each loop.  We set each entry, so they need     not be zeroed.  */  loop_number_loop_starts = (rtx *) alloca (max_loop_num * sizeof (rtx));  loop_number_loop_ends = (rtx *) alloca (max_loop_num * sizeof (rtx));  loop_outer_loop = (int *) alloca (max_loop_num * sizeof (int));  loop_invalid = (char *) alloca (max_loop_num * sizeof (char));  loop_number_exit_labels = (rtx *) alloca (max_loop_num * sizeof (rtx));  loop_number_exit_count = (int *) alloca (max_loop_num * sizeof (int));  /* Find and process each loop.     First, find them, and record them in order of their beginnings.  */  find_and_verify_loops (f);  /* Now find all register lifetimes.  This must be done after     find_and_verify_loops, because it might reorder the insns in the     function.  */  reg_scan (f, max_reg_num (), 1);  /* See if we went too far.  */  if (get_max_uid () > max_uid_for_loop)    abort ();  /* 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)	uid_luid[INSN_UID (insn)] = ++i;      else	/* Give a line number note the same luid as preceding insn.  */	uid_luid[INSN_UID (insn)] = i;