/* Optimize jump instructions, for GNU compiler.   Copyright (C) 1987, 1988, 1989, 1991, 1992 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, 675 Mass Ave, Cambridge, MA 02139, USA.  *//* This is the jump-optimization pass of the compiler.   It is run two or three times: once before cse, sometimes once after cse,   and once after reload (before final).   jump_optimize deletes unreachable code and labels that are not used.   It also deletes jumps that jump to the following insn,   and simplifies jumps around unconditional jumps and jumps   to unconditional jumps.   Each CODE_LABEL has a count of the times it is used   stored in the LABEL_NUSES internal field, and each JUMP_INSN   has one label that it refers to stored in the   JUMP_LABEL internal field.  With this we can detect labels that   become unused because of the deletion of all the jumps that   formerly used them.  The JUMP_LABEL info is sometimes looked   at by later passes.   Optionally, cross-jumping can be done.  Currently it is done   only the last time (when after reload and before final).   In fact, the code for cross-jumping now assumes that register   allocation has been done, since it uses `rtx_renumbered_equal_p'.   Jump optimization is done after cse when cse's constant-propagation   causes jumps to become unconditional or to be deleted.   Unreachable loops are not detected here, because the labels   have references and the insns appear reachable from the labels.   find_basic_blocks in flow.c finds and deletes such loops.   The subroutines delete_insn, redirect_jump, and invert_jump are used   from other passes as well.  */#include "config.h"#include "rtl.h"#include "flags.h"#include "hard-reg-set.h"#include "regs.h"#include "expr.h"#include "insn-config.h"#include "insn-flags.h"#include "real.h"/* ??? Eventually must record somehow the labels used by jumps   from nested functions.  *//* Pre-record the next or previous real insn for each label?   No, this pass is very fast anyway.  *//* Condense consecutive labels?   This would make life analysis faster, maybe.  *//* Optimize jump y; x: ... y: jumpif... x?   Don't know if it is worth bothering with.  *//* Optimize two cases of conditional jump to conditional jump?   This can never delete any instruction or make anything dead,   or even change what is live at any point.   So perhaps let combiner do it.  *//* Vector indexed by uid.   For each CODE_LABEL, index by its uid to get first unconditional jump   that jumps to the label.   For each JUMP_INSN, index by its uid to get the next unconditional jump   that jumps to the same label.   Element 0 is the start of a chain of all return insns.   (It is safe to use element 0 because insn uid 0 is not used.  */static rtx *jump_chain;/* List of labels referred to from initializers.   These can never be deleted.  */rtx forced_labels;/* Maximum index in jump_chain.  */static int max_jump_chain;/* Set nonzero by jump_optimize if control can fall through   to the end of the function.  */int can_reach_end;/* Indicates whether death notes are significant in cross jump analysis.   Normally they are not significant, because of A and B jump to C,   and R dies in A, it must die in B.  But this might not be true after   stack register conversion, and we must compare death notes in that   case. */static int cross_jump_death_matters = 0;static int duplicate_loop_exit_test ();void redirect_tablejump ();static int delete_labelref_insn ();static void mark_jump_label ();void delete_jump ();void delete_computation ();static void delete_from_jump_chain ();static int tension_vector_labels ();static void find_cross_jump ();static void do_cross_jump ();static int jump_back_p ();extern rtx gen_jump ();/* Delete no-op jumps and optimize jumps to jumps   and jumps around jumps.   Delete unused labels and unreachable code.   If CROSS_JUMP is 1, detect matching code   before a jump and its destination and unify them.   If CROSS_JUMP is 2, do cross-jumping, but pay attention to death notes.   If NOOP_MOVES is nonzero, delete no-op move insns.   If AFTER_REGSCAN is nonzero, then this jump pass is being run immediately   after regscan, and it is safe to use regno_first_uid and regno_last_uid.   If `optimize' is zero, don't change any code,   just determine whether control drops off the end of the function.   This case occurs when we have -W and not -O.   It works because `delete_insn' checks the value of `optimize'   and refrains from actually deleting when that is 0.  */voidjump_optimize (f, cross_jump, noop_moves, after_regscan)     rtx f;     int cross_jump;     int noop_moves;     int after_regscan;{  register rtx insn, next;  int changed;  int first = 1;  int max_uid = 0;  rtx last_insn;  cross_jump_death_matters = (cross_jump == 2);  /* Initialize LABEL_NUSES and JUMP_LABEL fields.  */  for (insn = f; insn; insn = NEXT_INSN (insn))    {      if (GET_CODE (insn) == CODE_LABEL)	LABEL_NUSES (insn) = (LABEL_PRESERVE_P (insn) != 0);      else if (GET_CODE (insn) == JUMP_INSN)	JUMP_LABEL (insn) = 0;      if (INSN_UID (insn) > max_uid)	max_uid = INSN_UID (insn);    }  max_uid++;  /* Delete insns following barriers, up to next label.  */  for (insn = f; insn;)    {      if (GET_CODE (insn) == BARRIER)	{	  insn = NEXT_INSN (insn);	  while (insn != 0 && GET_CODE (insn) != CODE_LABEL)	    {	      if (GET_CODE (insn) == NOTE		  && NOTE_LINE_NUMBER (insn) != NOTE_INSN_FUNCTION_END)		insn = NEXT_INSN (insn);	      else		insn = delete_insn (insn);	    }	  /* INSN is now the code_label.  */	}      else	insn = NEXT_INSN (insn);    }  /* Leave some extra room for labels and duplicate exit test insns     we make.  */  max_jump_chain = max_uid * 14 / 10;  jump_chain = (rtx *) alloca (max_jump_chain * sizeof (rtx));  bzero (jump_chain, max_jump_chain * sizeof (rtx));  /* Mark the label each jump jumps to.     Combine consecutive labels, and count uses of labels.     For each label, make a chain (using `jump_chain')     of all the *unconditional* jumps that jump to it;     also make a chain of all returns.  */  for (insn = f; insn; insn = NEXT_INSN (insn))    if ((GET_CODE (insn) == JUMP_INSN || GET_CODE (insn) == INSN	 || GET_CODE (insn) == CALL_INSN)	&& ! INSN_DELETED_P (insn))      {	mark_jump_label (PATTERN (insn), insn, cross_jump);	if (GET_CODE (insn) == JUMP_INSN)	  {	    if (JUMP_LABEL (insn) != 0 && simplejump_p (insn))	      {		jump_chain[INSN_UID (insn)]		  = jump_chain[INSN_UID (JUMP_LABEL (insn))];		jump_chain[INSN_UID (JUMP_LABEL (insn))] = insn;	      }	    if (GET_CODE (PATTERN (insn)) == RETURN)	      {		jump_chain[INSN_UID (insn)] = jump_chain[0];		jump_chain[0] = insn;	      }	  }      }  /* Keep track of labels used from static data;     they cannot ever be deleted.  */  for (insn = forced_labels; insn; insn = XEXP (insn, 1))    LABEL_NUSES (XEXP (insn, 0))++;  /* Delete all labels already not referenced.     Also find the last insn.  */  last_insn = 0;  for (insn = f; insn; )    {      if (GET_CODE (insn) == CODE_LABEL && LABEL_NUSES (insn) == 0)	insn = delete_insn (insn);      else	{	  last_insn = insn;	  insn = NEXT_INSN (insn);	}    }  if (!optimize)    {      /* See if there is still a NOTE_INSN_FUNCTION_END in this function.	 If so record that this function can drop off the end.  */      insn = last_insn;      {	int n_labels = 1;	while (insn	       /* One label can follow the end-note: the return label.  */	       && ((GET_CODE (insn) == CODE_LABEL && n_labels-- > 0)		   /* Ordinary insns can follow it if returning a structure.  */		   || GET_CODE (insn) == INSN		   /* If machine uses explicit RETURN insns, no epilogue,		      then one of them follows the note.  */		   || (GET_CODE (insn) == JUMP_INSN		       && GET_CODE (PATTERN (insn)) == RETURN)		   /* Other kinds of notes can follow also.  */		   || (GET_CODE (insn) == NOTE		       && NOTE_LINE_NUMBER (insn) != NOTE_INSN_FUNCTION_END)))	  insn = PREV_INSN (insn);      }      /* Report if control can fall through at the end of the function.  */      if (insn && GET_CODE (insn) == NOTE	  && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_END	  && ! INSN_DELETED_P (insn))	can_reach_end = 1;      /* Zero the "deleted" flag of all the "deleted" insns.  */      for (insn = f; insn; insn = NEXT_INSN (insn))	INSN_DELETED_P (insn) = 0;      return;    }#ifdef HAVE_return  if (HAVE_return)    {      /* If we fall through to the epilogue, see if we can insert a RETURN insn	 in front of it.  If the machine allows it at this point (we might be	 after reload for a leaf routine), it will improve optimization for it	 to be there.  */      insn = get_last_insn ();      while (insn && GET_CODE (insn) == NOTE)	insn = PREV_INSN (insn);      if (insn && GET_CODE (insn) != BARRIER)	{	  emit_jump_insn (gen_return ());	  emit_barrier ();	}    }#endif  if (noop_moves)    for (insn = f; insn; )      {	next = NEXT_INSN (insn);	if (GET_CODE (insn) == INSN)	  {	    register rtx body = PATTERN (insn);/* Combine stack_adjusts with following push_insns.  */#ifdef PUSH_ROUNDING	    if (GET_CODE (body) == SET		&& SET_DEST (body) == stack_pointer_rtx		&& GET_CODE (SET_SRC (body)) == PLUS		&& XEXP (SET_SRC (body), 0) == stack_pointer_rtx		&& GET_CODE (XEXP (SET_SRC (body), 1)) == CONST_INT		&& INTVAL (XEXP (SET_SRC (body), 1)) > 0)	      {		rtx p;		rtx stack_adjust_insn = insn;		int stack_adjust_amount = INTVAL (XEXP (SET_SRC (body), 1));		int total_pushed = 0;		int pushes = 0;		/* Find all successive push insns.  */		p = insn;		/* Don't convert more than three pushes;		   that starts adding too many displaced addresses		   and the whole thing starts becoming a losing		   proposition.  */		while (pushes < 3)		  {		    rtx pbody, dest;		    p = next_nonnote_insn (p);		    if (p == 0 || GET_CODE (p) != INSN)		      break;		    pbody = PATTERN (p);		    if (GET_CODE (pbody) != SET)		      break;		    dest = SET_DEST (pbody);		    /* Allow a no-op move between the adjust and the push.  */		    if (GET_CODE (dest) == REG			&& GET_CODE (SET_SRC (pbody)) == REG			&& REGNO (dest) == REGNO (SET_SRC (pbody)))		      continue;		    if (! (GET_CODE (dest) == MEM			   && GET_CODE (XEXP (dest, 0)) == POST_INC			   && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx))		      break;		    pushes++;		    if (total_pushed + GET_MODE_SIZE (SET_DEST (pbody))			> stack_adjust_amount)		      break;		    total_pushed += GET_MODE_SIZE (SET_DEST (pbody));		  }		/* Discard the amount pushed from the stack adjust;		   maybe eliminate it entirely.  */		if (total_pushed >= stack_adjust_amount)		  {		    delete_insn (stack_adjust_insn);		    total_pushed = stack_adjust_amount;		  }		else		  XEXP (SET_SRC (PATTERN (stack_adjust_insn)), 1)		    = GEN_INT (stack_adjust_amount - total_pushed);		/* Change the appropriate push insns to ordinary stores.  */		p = insn;		while (total_pushed > 0)		  {		    rtx pbody, dest;		    p = next_nonnote_insn (p);		    if (GET_CODE (p) != INSN)		      break;		    pbody = PATTERN (p);		    if (GET_CODE (pbody) == SET)		      break;		    dest = SET_DEST (pbody);		    if (! (GET_CODE (dest) == MEM			   && GET_CODE (XEXP (dest, 0)) == POST_INC			   && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx))		      break;		    total_pushed -= GET_MODE_SIZE (SET_DEST (pbody));		    /* If this push doesn't fully fit in the space		       of the stack adjust that we deleted,		       make another stack adjust here for what we		       didn't use up.  There should be peepholes		       to recognize the resulting sequence of insns.  */