RFC/A: canonicalize_condition() cleanups

[Richard Sandiford <rsandifo at redhat dot com>]

This started with a bug report against an uncontributed port.  The exact
circumstances are hard to reproduce in current sources, and I'd normally
be reticent about submitting a bug fix for something that has no known
testcase.  I hope this particular patch can go in anyway because:

    (a) it's easy to see that there is a theoretical bug
    (b) it cleans up some code in gcse.c and ifcvt.c
    (c) it gets rid of a FIXME in loop-iv.c

The problem is in the use of canonicalize_condition().  This function looks
at a branch insn and tries to work out what the original comparison was.
It has a parameter, EARLIEST, in which it records the first insn to be
involved in the comparison.

The idea is that the condition returned by canonicalize_condition() is
valid immediately before *EARLIEST, but not necessarily at the original
branch instruction.  This has led to functions like fis_get_condition()
and noce_get_condition(), both of which check whether the condition is
also valid at the branch.

Unfortunately, unroll.c:loop_iterations() just uses get_condition_for_loop(),
which in turn uses get_condition(), which doesn't check this property.
loop_iterations() nevertheless assumes that the condition is still valid
at the branch.

In the testcase against the internal port, we had a loop of the form:

    start:
    ...
    cond = i < num
    i = i + 1
    if cond goto start

and loop_iterations thought that the final value of "i" was "num",
not "num + 1".

A simple fix would be to use fis_get_condition().  However,
fis_get_condition() is itself a bit of mess.  If the condition
returned by canonicalize_condition() doesn't survive to the branch,
fis_get_condition() will call canonicalize_condition() again, but this
time stopping it from looking as far:

    /* Use canonicalize_condition to do the dirty work of manipulating
       MODE_CC values and COMPARE rtx codes.  */
    tmp = canonicalize_condition (jump, cond, reverse, &earliest, NULL_RTX,
                                  false);
    if (!tmp)
      return NULL_RTX;

    /* Verify that the given condition is valid at JUMP by virtue of not
       having been modified since EARLIEST.  */
    for (insn = earliest; insn != jump; insn = NEXT_INSN (insn))
      if (INSN_P (insn) && modified_in_p (tmp, insn))
        break;
    if (insn == jump)
      return tmp;

    /* The condition was modified.  See if we can get a partial result
       that doesn't follow all the reversals.  Perhaps combine can fold
       them together later.  */
    tmp = XEXP (tmp, 0);
    if (!REG_P (tmp) || GET_MODE_CLASS (GET_MODE (tmp)) != MODE_INT)
      return NULL_RTX;
    tmp = canonicalize_condition (jump, cond, reverse, &earliest, tmp,
                                  false);
    if (!tmp)
      return NULL_RTX;

    /* For sanity's sake, re-validate the new result.  */
    for (insn = earliest; insn != jump; insn = NEXT_INSN (insn))
      if (INSN_P (insn) && modified_in_p (tmp, insn))
        return NULL_RTX;

    return tmp;

noce_get_condition() has the same cut-&-paste construct.  I think it
would be much easier to check this in canonicalize_condition(), where we
can stop looking as soon as we know that a particular condition will not
be valid at INSN.

I wondered whether canonicalize_condition() should always ensure that
the condition is valid at the branch.  That might be less confusing
than what we have now.  However, it looks like some pieces of code do
correctly handle the case where it isn't valid, so I thought that might
be seen as a pessimisation.

Instead, the patch adds a new parameter to canonicalize_condition() to
say whether the condition must be valid at both *EARLIEST and INSN.
This allows us to get rid of the code above, and also forces every
user of canonicalize_condition() or get_condition() to say what
assumptions they're making.  It also means we can get rid of the
following FIXME in loop-iv.c:

    /* FIXME -- slightly wrong -- what if compared register
       gets altered between start of the condition and insn?  */
    rtx cond = get_condition (BB_END (e->src), NULL, false);

This change needed an audit of all calls to the affected functions:

    - gcse.c:fis_get_condition() gets simplified as described above.

    - ifcvt.c:noce_get_condition() also gets simplified.

    - ifcvt.c:noce_get_alt_condition() assumes that the condition is
      valid at the branch, so the new argument should be "true".
      (This is a bit defensive, since the function also checks
      the definition and use of A, B and X.)

    - loop-iv.c:simplify_using_initial_values() also assumes the
      condition is valid at the branch, as per the FIXME above.

    - loop-iv.c:check_simple_exit() and loop-unswitch.c:may_unswitch_on()
      seem to cope with situations where the condition isn't valid
      at the branch, so the new argument is "false".

    - loop.c:check_dbra_loop() also wants the condition to be valid at
      the branch, so the new argument should be "true".  (This is again
      a bit defensive, since the function only copes with cases where
      *EARLIEST immediately precedes the branch.  However, it's technically
      possible for *EARLIEST to modify one of the source registers,
      so it seems better to be on the safe side.)

    - loop.c:get_condition_for_loop() has users which assume the condition
      is valid at the branch, so the new argument is "true".

    - predict.c doesn't seem to care where the condition is valid,
      just which registers it uses.  The new argument is therefore "false".

Well, as "cleanups" go, that was very verbose, and the code's still
far from pretty.  Even so...

...bootstrapped & regression tested on i686-pc-linux-gnu.  OK for mainline?

Richard


	* expr.h (canonicalize_condition, get_condition): Add an int argument.
	* gcse.c (fis_get_condition): Reimplement using get_condition, leaving
	it to check whether the condition is still valid at the jump insn.
	* ifcvt.c (noce_get_condition): Likewise.
	(noce_get_alt_condition): Update call to canonicalize_condition.
	* loop-iv.c (simplify_using_initial_values): Update call to
	get_condition.  Remove FIXME.
	(check_simple_exit): Update call to get_condition.
	* loop-unswitch.c (may_unswitch_on): Likewise.
	* loop.c (check_dbra_loop): Likewise.
	(canonicalize_condition, get_condition): Add an argument to say whether
	the condition must still be valid at INSN.
	(get_condition_for_loop): Update call to get_condition.  Require that
	the condition be valid at INSN.
	* predict.c (estimate_probability): Update call to get_condition.
	Remove unused earliest parameter.
	(expected_value_to_br_prob): Update call to canonicalize_condition.

Index: expr.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/expr.h,v
retrieving revision 1.167
diff -u -p -F^\([(a-zA-Z0-9_]\|#define\) -r1.167 expr.h
--- expr.h	16 Jul 2004 23:25:38 -0000	1.167
+++ expr.h	23 Jul 2004 15:23:04 -0000
@@ -338,11 +338,11 @@ extern rtx emit_store_flag_force (rtx, e
 
 /* Given an insn and condition, return a canonical description of
    the test being made.  */
-extern rtx canonicalize_condition (rtx, rtx, int, rtx *, rtx, int);
+extern rtx canonicalize_condition (rtx, rtx, int, rtx *, rtx, int, int);
 
 /* Given a JUMP_INSN, return a canonical description of the test
    being made.  */
-extern rtx get_condition (rtx, rtx *, int);
+extern rtx get_condition (rtx, rtx *, int, int);
 
 /* Generate a conditional trap instruction.  */
 extern rtx gen_cond_trap (enum rtx_code, rtx, rtx, rtx);
Index: gcse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gcse.c,v
retrieving revision 1.307
diff -u -p -F^\([(a-zA-Z0-9_]\|#define\) -r1.307 gcse.c
--- gcse.c	16 Jul 2004 22:28:28 -0000	1.307
+++ gcse.c	23 Jul 2004 15:23:11 -0000
@@ -3687,52 +3687,7 @@ cprop (int alter_jumps)
 rtx
 fis_get_condition (rtx jump)
 {
-  rtx cond, set, tmp, insn, earliest;
-  bool reverse;
-
-  if (! any_condjump_p (jump))
-    return NULL_RTX;
-
-  set = pc_set (jump);
-  cond = XEXP (SET_SRC (set), 0);
-
-  /* If this branches to JUMP_LABEL when the condition is false,
-     reverse the condition.  */
-  reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
-	     && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump));
-
-  /* Use canonicalize_condition to do the dirty work of manipulating
-     MODE_CC values and COMPARE rtx codes.  */
-  tmp = canonicalize_condition (jump, cond, reverse, &earliest, NULL_RTX,
-				false);
-  if (!tmp)
-    return NULL_RTX;
-
-  /* Verify that the given condition is valid at JUMP by virtue of not
-     having been modified since EARLIEST.  */
-  for (insn = earliest; insn != jump; insn = NEXT_INSN (insn))
-    if (INSN_P (insn) && modified_in_p (tmp, insn))
-      break;
-  if (insn == jump)
-    return tmp;
-
-  /* The condition was modified.  See if we can get a partial result
-     that doesn't follow all the reversals.  Perhaps combine can fold
-     them together later.  */
-  tmp = XEXP (tmp, 0);
-  if (!REG_P (tmp) || GET_MODE_CLASS (GET_MODE (tmp)) != MODE_INT)
-    return NULL_RTX;
-  tmp = canonicalize_condition (jump, cond, reverse, &earliest, tmp,
-				false);
-  if (!tmp)
-    return NULL_RTX;
-
-  /* For sanity's sake, re-validate the new result.  */
-  for (insn = earliest; insn != jump; insn = NEXT_INSN (insn))
-    if (INSN_P (insn) && modified_in_p (tmp, insn))
-      return NULL_RTX;
-
-  return tmp;
+  return get_condition (jump, NULL, false, true);
 }
 
 /* Check the comparison COND to see if we can safely form an implicit set from
Index: ifcvt.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ifcvt.c,v
retrieving revision 1.158
diff -u -p -F^\([(a-zA-Z0-9_]\|#define\) -r1.158 ifcvt.c
--- ifcvt.c	11 Jul 2004 14:37:57 -0000	1.158
+++ ifcvt.c	23 Jul 2004 15:23:14 -0000
@@ -1489,7 +1489,7 @@ noce_get_alt_condition (struct noce_if_i
     }
 
   cond = canonicalize_condition (if_info->jump, cond, reverse,
-				 earliest, target, false);
+				 earliest, target, false, true);
   if (! cond || ! reg_mentioned_p (target, cond))
     return NULL;
 
@@ -1800,7 +1800,7 @@ noce_try_sign_mask (struct noce_if_info 
 static rtx
 noce_get_condition (rtx jump, rtx *earliest)
 {
-  rtx cond, set, tmp, insn;
+  rtx cond, set, tmp;
   bool reverse;
 
   if (! any_condjump_p (jump))
@@ -1829,38 +1829,8 @@ noce_get_condition (rtx jump, rtx *earli
 
   /* Otherwise, fall back on canonicalize_condition to do the dirty
      work of manipulating MODE_CC values and COMPARE rtx codes.  */
-
-  tmp = canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX,
-				false);
-  if (!tmp)
-    return NULL_RTX;
-
-  /* We are going to insert code before JUMP, not before EARLIEST.
-     We must therefore be certain that the given condition is valid
-     at JUMP by virtue of not having been modified since.  */
-  for (insn = *earliest; insn != jump; insn = NEXT_INSN (insn))
-    if (INSN_P (insn) && modified_in_p (tmp, insn))
-      break;
-  if (insn == jump)
-    return tmp;
-
-  /* The condition was modified.  See if we can get a partial result
-     that doesn't follow all the reversals.  Perhaps combine can fold
-     them together later.  */
-  tmp = XEXP (tmp, 0);
-  if (!REG_P (tmp) || GET_MODE_CLASS (GET_MODE (tmp)) != MODE_INT)
-    return NULL_RTX;
-  tmp = canonicalize_condition (jump, cond, reverse, earliest, tmp,
-				false);
-  if (!tmp)
-    return NULL_RTX;
-
-  /* For sanity's sake, re-validate the new result.  */
-  for (insn = *earliest; insn != jump; insn = NEXT_INSN (insn))
-    if (INSN_P (insn) && modified_in_p (tmp, insn))
-      return NULL_RTX;
-
-  return tmp;
+  return canonicalize_condition (jump, cond, reverse, earliest,
+				 NULL_RTX, false, true);
 }
 
 /* Return true if OP is ok for if-then-else processing.  */
Index: loop-iv.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop-iv.c,v
retrieving revision 2.12
diff -u -p -F^\([(a-zA-Z0-9_]\|#define\) -r2.12 loop-iv.c
--- loop-iv.c	11 Jul 2004 02:52:54 -0000	2.12
+++ loop-iv.c	23 Jul 2004 15:23:16 -0000
@@ -1737,9 +1737,7 @@ simplify_using_initial_values (struct lo
       insn = BB_END (e->src);
       if (any_condjump_p (insn))
 	{
-	  /* FIXME -- slightly wrong -- what if compared register
-	     gets altered between start of the condition and insn?  */
-	  rtx cond = get_condition (BB_END (e->src), NULL, false);
+	  rtx cond = get_condition (BB_END (e->src), NULL, false, true);
       
 	  if (cond && (e->flags & EDGE_FALLTHRU))
 	    cond = reversed_condition (cond);
@@ -2472,7 +2470,7 @@ check_simple_exit (struct loop *loop, ed
   desc->in_edge = ei;
 
   /* Test whether the condition is suitable.  */
-  if (!(condition = get_condition (BB_END (ei->src), &at, false)))
+  if (!(condition = get_condition (BB_END (ei->src), &at, false, false)))
     return;
 
   if (ei->flags & EDGE_FALLTHRU)
Index: loop-unswitch.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop-unswitch.c,v
retrieving revision 1.18
diff -u -p -F^\([(a-zA-Z0-9_]\|#define\) -r1.18 loop-unswitch.c
--- loop-unswitch.c	19 May 2004 17:53:45 -0000	1.18
+++ loop-unswitch.c	23 Jul 2004 15:23:16 -0000
@@ -196,7 +196,7 @@ may_unswitch_on (basic_block bb, struct 
     return NULL_RTX;
 
   /* Condition must be invariant.  */
-  test = get_condition (BB_END (bb), &at, true);
+  test = get_condition (BB_END (bb), &at, true, false);
   if (!test)
     return NULL_RTX;
 
Index: loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.504
diff -u -p -F^\([(a-zA-Z0-9_]\|#define\) -r1.504 loop.c
--- loop.c	15 Jul 2004 14:55:15 -0000	1.504
+++ loop.c	23 Jul 2004 15:23:27 -0000
@@ -8001,7 +8001,7 @@ check_dbra_loop (struct loop *loop, int 
 
   /* Try to compute whether the compare/branch at the loop end is one or
      two instructions.  */
-  get_condition (jump, &first_compare, false);
+  get_condition (jump, &first_compare, false, true);
   if (first_compare == jump)
     compare_and_branch = 1;
   else if (first_compare == prev_nonnote_insn (jump))
@@ -9195,11 +9195,14 @@ update_reg_last_use (rtx x, rtx insn)
    If WANT_REG is nonzero, we wish the condition to be relative to that
    register, if possible.  Therefore, do not canonicalize the condition
    further.  If ALLOW_CC_MODE is nonzero, allow the condition returned 
-   to be a compare to a CC mode register.  */
+   to be a compare to a CC mode register.
+
+   If VALID_AT_INSN_P, the condition must be valid at both *EARLIEST
+   and at INSN.  */
 
 rtx
 canonicalize_condition (rtx insn, rtx cond, int reverse, rtx *earliest,
-			rtx want_reg, int allow_cc_mode)
+			rtx want_reg, int allow_cc_mode, int valid_at_insn_p)
 {
   enum rtx_code code;
   rtx prev = insn;
@@ -9357,6 +9360,11 @@ canonicalize_condition (rtx insn, rtx co
 
       if (x)
 	{
+	  /* If the caller is expecting the condition to be valid at INSN,
+	     make sure X doesn't change before INSN.  */
+	  if (valid_at_insn_p)
+	    if (modified_in_p (x, prev) || modified_between_p (x, prev, insn))
+	      break;
 	  if (COMPARISON_P (x))
 	    code = GET_CODE (x);
 	  if (reverse_code)
@@ -9443,13 +9451,16 @@ canonicalize_condition (rtx insn, rtx co
    If EARLIEST is nonzero, it is a pointer to a place where the earliest
    insn used in locating the condition was found.  If a replacement test
    of the condition is desired, it should be placed in front of that
-   insn and we will be sure that the inputs are still valid.  
+   insn and we will be sure that the inputs are still valid.  If EARLIEST
+   is null, the returned condition will be valid at INSN.
 
    If ALLOW_CC_MODE is nonzero, allow the condition returned to be a
-   compare CC mode register.  */
+   compare CC mode register.
+
+   VALID_AT_INSN_P is the same as for canonicalize_condition.  */
 
 rtx
-get_condition (rtx jump, rtx *earliest, int allow_cc_mode)
+get_condition (rtx jump, rtx *earliest, int allow_cc_mode, int valid_at_insn_p)
 {
   rtx cond;
   int reverse;
@@ -9470,7 +9481,7 @@ get_condition (rtx jump, rtx *earliest, 
       && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump);
 
   return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX,
-				 allow_cc_mode);
+				 allow_cc_mode, valid_at_insn_p);
 }
 
 /* Similar to above routine, except that we also put an invariant last
@@ -9479,7 +9490,7 @@ get_condition (rtx jump, rtx *earliest, 
 rtx
 get_condition_for_loop (const struct loop *loop, rtx x)
 {
-  rtx comparison = get_condition (x, (rtx*) 0, false);
+  rtx comparison = get_condition (x, (rtx*) 0, false, true);
 
   if (comparison == 0
       || ! loop_invariant_p (loop, XEXP (comparison, 0))
Index: predict.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/predict.c,v
retrieving revision 1.107
diff -u -p -F^\([(a-zA-Z0-9_]\|#define\) -r1.107 predict.c
--- predict.c	16 Jul 2004 22:28:28 -0000	1.107
+++ predict.c	23 Jul 2004 15:23:29 -0000
@@ -638,7 +638,7 @@ estimate_probability (struct loops *loop
   FOR_EACH_BB (bb)
     {
       rtx last_insn = BB_END (bb);
-      rtx cond, earliest;
+      rtx cond;
       edge e;
 
       if (! can_predict_insn_p (last_insn))
@@ -683,7 +683,7 @@ estimate_probability (struct loops *loop
 	    }
 	}
 
-      cond = get_condition (last_insn, &earliest, false);
+      cond = get_condition (last_insn, NULL, false, false);
       if (! cond)
 	continue;
 
@@ -1045,7 +1045,8 @@ expected_value_to_br_prob (void)
 		(lt r70, r71)
 	 Could use cselib to try and reduce this further.  */
       cond = XEXP (SET_SRC (pc_set (insn)), 0);
-      cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg, false);
+      cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg,
+				     false, false);
       if (! cond || XEXP (cond, 0) != ev_reg
 	  || GET_CODE (XEXP (cond, 1)) != CONST_INT)
 	continue;