[PATCH] PR 9974: Insns on edges in bypass

[Roger Sayle <roger at www dot eyesopen dot com>]

The following patch fixes PR fortran/9974, an ICE building check0.f on
mips-sgi-irix6.5.  The source of the problem isn't in the g77 front-end
at all, but a very rare problem in GCSE's jump bypassing pass.  This
bug causes ffeexpr_finished_ in f/expr.c to be miscompiled on MIPS,
which eventually results in an ICE in g77.f-torture/noncompile/check0.f

On most architectures conditional jumps are actually two consecutive
instructions, one to perform the comparison setting a condition code
and the second to perform the conditional branch.  However, on non-cc0
targets the condition code may still be live after the branch, so
the jump bypassing optimization after redirecting an edge, places a
copy of the ccsetting instruction on that edge.  These temporary
instructions on edges are placed in the main instruction stream at
the end of the pass, splitting edges if necessary.

Occassionally, on targets such as MIPS where conditional branches are
just a single instruction, we treat the immediately preceding set of
a register as a cc-setter.  This is almost always harmless except in
cases such as the PR where the instruction placed on the edge invalidates
the data flow analysis for a later jump bypassing attempt.

[I originally tried explaining the precise sequence of events leading
to the failure, but its actually incredibly convoluted.  The details
are available upon request.]

The solution is to make jump bypassing aware that instructions may
already have been placed on edges.  We disable the jump bypassing
transformation if (i) any instruction on the incoming edge invalidates
the incoming constant substitution or (ii) the outgoing edge contains
any instructions that would need to be executed.


The following patch has been tested on both mips-sgi-irix6.5 and
i686-pc-linux-gnu, with a complete "make bootstrap", all languages
except Ada and treelang, and a top-level "make -k check" with no
new regressions.  Many thanks to David Billinghurst for confirming
that this patch bootstraps without regressions and fixes the problem
on MIPS IRIX.

Ok for mainline?


2003-03-24  Roger Sayle  <roger at eyesopen dot com>

	PR fortran/9974
	* gcse.c (reg_killed_on_egde): New function to test whether the
	given regno is overwritten by any instruction queued on an edge.
	(bypass_block): Ignore substitutions killed on incoming edges.
	Don't bypass outgoing edges that have queued instructions.

	* gcc.c-torture/execute/20030324-1.c: New test case.


Index: gcse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gcse.c,v
retrieving revision 1.239
diff -c -3 -p -r1.239 gcse.c
*** gcse.c	8 Mar 2003 09:47:28 -0000	1.239
--- gcse.c	23 Mar 2003 22:04:31 -0000
*************** static void find_implicit_sets	PARAMS ((
*** 622,627 ****
--- 622,628 ----
  static int one_cprop_pass	PARAMS ((int, int, int));
  static bool constprop_register	PARAMS ((rtx, rtx, rtx, int));
  static struct expr *find_bypass_set PARAMS ((int, int));
+ static bool reg_killed_on_edge	    PARAMS ((unsigned int, edge));
  static int bypass_block		    PARAMS ((basic_block, rtx, rtx));
  static int bypass_conditional_jumps PARAMS ((void));
  static void alloc_pre_mem	PARAMS ((int, int));
*************** find_bypass_set (regno, bb)
*** 4745,4750 ****
--- 4746,4774 ----
  }


+ /* Subroutine of bypass_block that checks whether a pseudo is killed by
+    any of the instructions inserted on an edge.  Jump bypassing places
+    condition code setters on CFG edges using insert_insn_on_edge.  This
+    function is required to check that our data flow analysis is still
+    valid prior to comit_edge_insertions.  */
+
+ static bool
+ reg_killed_on_edge (regno, e)
+      unsigned int regno;
+      edge e;
+ {
+   rtx insn, set;
+
+   for (insn = e->insns; insn; insn = NEXT_INSN (insn))
+     if (INSN_P (insn)
+ 	&& (set = single_set (insn)) != NULL_RTX
+ 	&& GET_CODE (SET_DEST (set)) == REG
+ 	&& REGNO (SET_DEST (set)) == regno)
+       return true;
+
+   return false;
+ }
+
  /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
     basic block BB which has more than one predecessor.  If not NULL, SETCC
     is the first instruction of BB, which is immediately followed by JUMP_INSN
*************** bypass_block (bb, setcc, jump)
*** 4757,4763 ****
       rtx setcc, jump;
  {
    rtx insn, note;
!   edge e, enext;
    int i, change;
    int may_be_loop_header;

--- 4781,4787 ----
       rtx setcc, jump;
  {
    rtx insn, note;
!   edge e, enext, edest;
    int i, change;
    int may_be_loop_header;

*************** bypass_block (bb, setcc, jump)
*** 4812,4817 ****
--- 4836,4845 ----
  	  if (! set)
  	    continue;

+ 	  /* Check the data flow is valid after edge insertions.  */
+ 	  if (reg_killed_on_edge (regno, e))
+ 	    continue;
+
  	  src = SET_SRC (pc_set (jump));

  	  if (setcc != NULL)
*************** bypass_block (bb, setcc, jump)
*** 4823,4831 ****
  				      SET_SRC (set->expr));

  	  if (new == pc_rtx)
! 	    dest = FALLTHRU_EDGE (bb)->dest;
  	  else if (GET_CODE (new) == LABEL_REF)
! 	    dest = BLOCK_FOR_INSN (XEXP (new, 0));
  	  else
  	    dest = NULL;

--- 4851,4871 ----
  				      SET_SRC (set->expr));

  	  if (new == pc_rtx)
! 	    {
! 	      edest = FALLTHRU_EDGE (bb);
! 	      dest = edest->insns ? NULL : edest->dest;
! 	    }
  	  else if (GET_CODE (new) == LABEL_REF)
! 	    {
! 	      dest = BLOCK_FOR_INSN (XEXP (new, 0));
! 	      /* Don't bypass edges containing instructions.  */
! 	      for (edest = bb->succ; edest; edest = edest->succ_next)
! 		if (edest->dest == dest && edest->insns)
! 		  {
! 		    dest = NULL;
! 		    break;
! 		  }
! 	    }
  	  else
  	    dest = NULL;


/* Testcase for PR fortran/9974.  This was a miscompilation of the g77
   front-end caused by the jump bypassing optimizations not handling
   instructions inserted on CFG edges.  */

extern void abort ();

int bar ()
{
  return 1;
}

void foo (int x)
{
  unsigned char error = 0;

  if (! (error = ((x == 0) || bar ())))
    bar ();
  if (! error)
    abort ();
}

int main()
{
  foo (1);
  return 0;
}


Roger
--
Roger Sayle,                         E-mail: roger at eyesopen dot com
OpenEye Scientific Software,         WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road,     Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507.         Fax: (+1) 505-473-0833