/* Optimize jump instructions, for GNU compiler.   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 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, invert_jump, next_real_insn   and prev_real_insn are used from other passes as well.  */#include "config.h"#include "rtl.h"#include "flags.h"#include "regs.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.  */rtx *jump_chain;rtx delete_insn ();void redirect_jump ();void invert_jump ();rtx next_real_insn ();rtx prev_real_insn ();rtx next_label ();static void mark_jump_label ();static void delete_jump ();static void squeeze_block_notes ();void invert_exp ();static void redirect_exp ();static rtx follow_jumps ();static int tension_vector_labels ();static void find_cross_jump ();static void do_cross_jump ();static enum rtx_code reverse_condition ();static int jump_back_p ();int condjump_p ();/* Delete no-op jumps and optimize jumps to jumps   and jumps around jumps.   Delete unused labels and unreachable code.   If CROSS_JUMP is nonzero, detect matching code   before a jump and its destination and unify them.   If NOOP_MOVES is nonzero, also delete no-op move insns.   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)     rtx f;{  register rtx insn;  int changed;  int first = 1;  int max_uid = 0;  rtx last_insn;  /* Initialize LABEL_NUSES and JUMP_LABEL fields.  */  for (insn = f; insn; insn = NEXT_INSN (insn))    {      if (GET_CODE (insn) == CODE_LABEL)	LABEL_NUSES (insn) = 0;      if (GET_CODE (insn) == JUMP_INSN)	JUMP_LABEL (insn) = 0;      if (INSN_UID (insn) > max_uid)	max_uid = INSN_UID (insn);    }  max_uid++;  jump_chain = (rtx *) alloca (max_uid * sizeof (rtx));  bzero (jump_chain, max_uid * sizeof (rtx));  /* 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);    }  /* 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 && ! INSN_DELETED_P (insn))      {	mark_jump_label (PATTERN (insn), insn, cross_jump);	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;	  }      }  /* 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);      }      if (insn && GET_CODE (insn) == NOTE	  && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_END	  && ! INSN_DELETED_P (insn))	{	  extern int current_function_returns_null;	  current_function_returns_null = 1;	}      /* Zero the "deleted" flag of all the "deleted" insns.  */      for (insn = f; insn; insn = NEXT_INSN (insn))	INSN_DELETED_P (insn) = 0;      return;    }  if (noop_moves)    for (insn = f; insn; )      {	register rtx next = NEXT_INSN (insn);	if (GET_CODE (insn) == INSN)	  {	    register rtx body = PATTERN (insn);#if 0 /* Keep these insns, since they are used for conditional branch	 scheduling peepholes on the sparc.  */#endif	    /* Delete insns that existed just to advise flow-analysis.  */	    if (GET_CODE (body) == USE		|| GET_CODE (body) == CLOBBER)	      delete_insn (insn);	    else	    /* Detect and delete no-op move instructions	       resulting from not allocating a parameter in a register.  */	      if (GET_CODE (body) == SET		     && (SET_DEST (body) == SET_SRC (body)			 || (GET_CODE (SET_DEST (body)) == MEM			     && GET_CODE (SET_SRC (body)) == MEM			     && rtx_equal_p (SET_SRC (body), SET_DEST (body))))		     && ! (GET_CODE (SET_DEST (body)) == MEM			   && MEM_VOLATILE_P (SET_DEST (body)))		     && ! (GET_CODE (SET_SRC (body)) == MEM			   && MEM_VOLATILE_P (SET_SRC (body))))	      delete_insn (insn);	    /* Detect and ignore no-op move instructions	       resulting from smart or fortuitous register allocation.  */	    else if (GET_CODE (body) == SET)	      {		int sreg = true_regnum (SET_SRC (body));		int dreg = true_regnum (SET_DEST (body));		if (sreg == dreg && sreg >= 0)		  delete_insn (insn);		else if (sreg >= 0 && dreg >= 0)		  {		    rtx tem = find_equiv_reg (0, insn, 0,					      sreg, 0, dreg,					      GET_MODE (SET_SRC (body)));		    #ifdef PRESERVE_DEATH_INFO_REGNO_P		    /* Deleting insn could lose a death-note for SREG or DREG		       so don't do it if final needs accurate death-notes.  */		    if (! PRESERVE_DEATH_INFO_REGNO_P (sreg)			&& ! PRESERVE_DEATH_INFO_REGNO_P (dreg))#endif		      if (tem != 0			  && GET_MODE (tem) == GET_MODE (SET_DEST (body)))			delete_insn (insn);		  }	      }	  }      insn = next;    }  /* Now iterate optimizing jumps until nothing changes over one pass.  */  changed = 1;  while (changed)    {      register rtx next;      changed = 0;      for (insn = f; insn; insn = next)	{#if 0	  /* If NOT the first iteration, if this is the last jump pass	     (just before final), do the special peephole optimizations.	     Avoiding the first iteration gives ordinary jump opts	     a chance to work before peephole opts.  */	  if (noop_moves && !first && !flag_no_peephole)	    if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)	      peephole (insn);#endif	  /* That could have deleted some insns after INSN, so check now	     what the following insn is.  */	  next = NEXT_INSN (insn);	  /* Tension the labels in dispatch tables.  */	  if (GET_CODE (insn) == JUMP_INSN)	    {	      if (GET_CODE (PATTERN (insn)) == ADDR_VEC)		changed |= tension_vector_labels (PATTERN (insn), 0, noop_moves);	      if (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)		changed |= tension_vector_labels (PATTERN (insn), 1, noop_moves);	    }	  /* Don't allow dropping through into a dispatch table.	     That means the dispatch insn itself was deleted,	     so delete the table too.  */	  if (GET_CODE (insn) == JUMP_INSN)	    {	      /* Note: the corresponding job for ADDR_VEC is done		 in delete_insn.  */	      /* A vector of offsets is unused if its label		 is used only once (i.e., from the vector).  */	      if (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC		  && LABEL_NUSES (XEXP (XEXP (PATTERN (insn), 0), 0)) == 1)		{		  /* So delete both label and vector.  */		  delete_insn (PREV_INSN (insn));		  delete_insn (insn);		  changed = 1;		}	    }	  if (GET_CODE (insn) == JUMP_INSN && JUMP_LABEL (insn))	    {	      register rtx reallabelprev = prev_real_insn (JUMP_LABEL (insn));	      rtx temp;	      /* Detect jump to following insn.  */	      if (reallabelprev == insn && condjump_p (insn))		{		  delete_jump (insn);		  changed = 1;		}	      /* Detect worthless conditional jump.  */	      else if ((temp = next_real_insn (insn))		       && GET_CODE (temp) == JUMP_INSN		       && condjump_p (insn)		       && simplejump_p (temp)		       && JUMP_LABEL (insn) == JUMP_LABEL (temp))		{		  delete_jump (insn);		  changed = 1;		  next = NEXT_INSN (insn);		}	      /* A jump to a return becomes a return.  */	      else if (simplejump_p (insn)		       && (temp = next_real_insn (JUMP_LABEL (insn))) != 0		       && GET_CODE (PATTERN (temp)) == RETURN)		{		  PATTERN (insn) = PATTERN (temp);		  /* Re-recognize this insn.  */		  INSN_CODE (insn) = -1;		}	      /* Detect jumping over an unconditional jump.  */	      else if (reallabelprev != 0		       && GET_CODE (reallabelprev) == JUMP_INSN		       && prev_real_insn (reallabelprev) == insn		       && no_labels_between_p (insn, reallabelprev)		       && simplejump_p (reallabelprev)		       /* Ignore this if INSN is a hairy kind of jump,			  since they may not be invertible.			  This is conservative; could instead construct			  the inverted insn and try recognizing it.  */		       && condjump_p (insn))		{		  /* Delete the original unconditional jump (and barrier).  */		  /* But don't let its destination go with it.  */		  ++LABEL_NUSES (JUMP_LABEL (reallabelprev));		  delete_insn (reallabelprev);		  /* Now change the condition, and make it go to the		     place the deleted jump went to.		     This may cause the label after the deletion to go away.		     But now that the unconditional jump and its barrier		     are gone, that is ok.  */		  invert_jump (insn, JUMP_LABEL (reallabelprev));		  --LABEL_NUSES (JUMP_LABEL (reallabelprev));		  next = insn;		  changed = 1;		}	      else		{		  /* Detect a jump to a jump.  */		  {		    register rtx nlabel		      = follow_jumps (JUMP_LABEL (insn), noop_moves);		    if (nlabel != JUMP_LABEL (insn))		      {			redirect_jump (insn, nlabel);			changed = 1;			next = insn;		      }		  }		  /* Look for   if (foo) bar; else break;  */		  /* The insns look like this:		     insn = condjump label1;		        ...range1 (some insns)...			jump label2;		     label1:		        ...range2 (some insns)...			jump somewhere unconditionally		     label2:  */		  {		    rtx label1 = next_label (insn);		    rtx range1end = label1 ? prev_real_insn (label1) : 0;		    /* Don't do this optimization on the first round, so that		       jump-around-a-jump gets simplified before we ask here		       whether a jump is unconditional.  */		    if (! first			/* Make sure INSN is something we can invert.  */			&& condjump_p (insn)			&& JUMP_LABEL (insn) == label1			&& LABEL_NUSES (label1) == 1			&& GET_CODE (range1end) == JUMP_INSN			&& simplejump_p (range1end))		      {			rtx label2 = next_label (label1);			rtx range2end = label2 ? prev_real_insn (label2) : 0;			if (range1end != range2end			    && JUMP_LABEL (range1end) == label2			    && GET_CODE (range2end) == JUMP_INSN			    && GET_CODE (NEXT_INSN (range2end)) == BARRIER)			  {			    rtx range1beg = next_real_insn (insn);			    rtx range2beg = next_real_insn (label1);			    rtx range1after, range2after;			    rtx range1before, range2before;			    /* Don't move NOTEs for blocks; shift them			       outside the ranges, where they'll stay put.  */			    squeeze_block_notes (range1beg, range1end);			    squeeze_block_notes (range2beg, range2end);			    /* Get current surrounds of the 2 ranges.  */			    range1before = PREV_INSN (range1beg);			    range2before = PREV_INSN (range2beg);			    range1after = NEXT_INSN (range1end);			    range2after = NEXT_INSN (range2end);			    /* Splice range2 where range1 was.  */			    NEXT_INSN (range1before) = range2beg;			    PREV_INSN (range2beg) = range1before;			    NEXT_INSN (range2end) = range1after;			    PREV_INSN (range1after) = range2end;			    /* Splice range1 where range2 was.  */			    NEXT_INSN (range2before) = range1beg;			    PREV_INSN (range1beg) = range2before;			    NEXT_INSN (range1end) = range2after;			    PREV_INSN (range2after) = range1end;			    /* Invert the jump condition, so we			       still execute the same insns in each case.  */			    invert_jump (insn, label1);			    changed = 1;			    continue;			  }		      }		  }		  /* Now that the jump has been tensioned,		     try cross jumping: check for identical code		     before the jump and before its target label. */		  /* First, cross jumping of conditional jumps:  */		  if (cross_jump && condjump_p (insn))		    {		      rtx newjpos, newlpos;		      rtx x = prev_real_insn (JUMP_LABEL (insn));		      /* A conditional jump may be crossjumped			 only if the place it jumps to follows			 an opposing jump that comes back here.  */		      if (x != 0 && ! jump_back_p (x, insn))			/* We have no opposing jump;			   cannot cross jump this insn.  */			x = 0;		      newjpos = 0;		      /* TARGET is nonzero if it is ok to cross jump			 to code before TARGET.  If so, see if matches.  */		      if (x != 0)			find_cross_jump (insn, x, 2,					 &newjpos, &newlpos);		      if (newjpos != 0)			{			  do_cross_jump (insn, newjpos, newlpos);			  /* Make the old conditional jump			     into an unconditional one.  */			  SET_SRC (PATTERN (insn))			    = gen_rtx (LABEL_REF, VOIDmode, JUMP_LABEL (insn));			  emit_barrier_after (insn);			  changed = 1;			  next = insn;			}		    }		  /* Cross jumping of unconditional jumps:		     a few differences.  */		  if (cross_jump && simplejump_p (insn))		    {		      rtx newjpos, newlpos;		      rtx target;