genrecog.c

GUN开源阻止下的编译器GCC

      new = add_to_sequence (SET_DEST (pattern), &new->success, newpos);
      this->success.first->enforce_mode = 1;
      newpos[depth] = '1';
      new = add_to_sequence (SET_SRC (pattern), &new->success, newpos);

      /* If set are setting CC0 from anything other than a COMPARE, we
	 must enforce the mode so that we do not produce ambiguous insns.  */
      if (GET_CODE (SET_DEST (pattern)) == CC0
	  && GET_CODE (SET_SRC (pattern)) != COMPARE)
	this->success.first->enforce_mode = 1;
      return new;

    case SIGN_EXTEND:
    case ZERO_EXTEND:
    case STRICT_LOW_PART:
      newpos[depth] = '0';
      new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos);
      this->success.first->enforce_mode = 1;
      return new;

    case SUBREG:
      this->test_elt_one_int = 1;
      this->elt_one_int = XINT (pattern, 1);
      newpos[depth] = '0';
      new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos);
      this->success.first->enforce_mode = 1;
      return new;

    case ZERO_EXTRACT:
    case SIGN_EXTRACT:
      newpos[depth] = '0';
      new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos);
      this->success.first->enforce_mode = 1;
      newpos[depth] = '1';
      new = add_to_sequence (XEXP (pattern, 1), &new->success, newpos);
      newpos[depth] = '2';
      new = add_to_sequence (XEXP (pattern, 2), &new->success, newpos);
      return new;

    case EQ:   case NE:   case LE:   case LT:   case GE:  case GT:
    case LEU:  case LTU:  case GEU:  case GTU:
      /* If the first operand is (cc0), we don't have to do anything
	 special.  */
      if (GET_CODE (XEXP (pattern, 0)) == CC0)
	break;

      /* ... fall through ... */
      
    case COMPARE:
      /* Enforce the mode on the first operand to avoid ambiguous insns.  */
      newpos[depth] = '0';
      new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos);
      this->success.first->enforce_mode = 1;
      newpos[depth] = '1';
      new = add_to_sequence (XEXP (pattern, 1), &new->success, newpos);
      return new;
    }

  fmt = GET_RTX_FORMAT (code);
  len = GET_RTX_LENGTH (code);
  for (i = 0; i < len; i++)
    {
      newpos[depth] = '0' + i;
      if (fmt[i] == 'e' || fmt[i] == 'u')
	new = add_to_sequence (XEXP (pattern, i), &new->success, newpos);
      else if (fmt[i] == 'i' && i == 0)
	{
	  this->test_elt_zero_int = 1;
	  this->elt_zero_int = XINT (pattern, i);
	}
      else if (fmt[i] == 'i' && i == 1)
	{
	  this->test_elt_one_int = 1;
	  this->elt_one_int = XINT (pattern, i);
	}
      else if (fmt[i] == 'w' && i == 0)
	{
	  this->test_elt_zero_wide = 1;
	  this->elt_zero_wide = XWINT (pattern, i);
	}
      else if (fmt[i] == 'E')
	{
	  register int j;
	  /* We do not handle a vector appearing as other than
	     the first item, just because nothing uses them
	     and by handling only the special case
	     we can use one element in newpos for either
	     the item number of a subexpression
	     or the element number in a vector.  */
	  if (i != 0)
	    abort ();
	  this->veclen = XVECLEN (pattern, i);
	  for (j = 0; j < XVECLEN (pattern, i); j++)
	    {
	      newpos[depth] = 'a' + j;
	      new = add_to_sequence (XVECEXP (pattern, i, j),
				     &new->success, newpos);
	    }
	}
      else if (fmt[i] != '0')
	abort ();
    }
  return new;
}

/* Return 1 if we can prove that there is no RTL that can match both
   D1 and D2.  Otherwise, return 0 (it may be that there is an RTL that
   can match both or just that we couldn't prove there wasn't such an RTL).

   TOPLEVEL is non-zero if we are to only look at the top level and not
   recursively descend.  */

static int
not_both_true (d1, d2, toplevel)
     struct decision *d1, *d2;
     int toplevel;
{
  struct decision *p1, *p2;

  /* If they are both to test modes and the modes are different, they aren't
     both true.  Similarly for codes, integer elements, and vector lengths. */

  if ((d1->enforce_mode && d2->enforce_mode
       && d1->mode != VOIDmode && d2->mode != VOIDmode && d1->mode != d2->mode)
      || (d1->code != UNKNOWN && d2->code != UNKNOWN && d1->code != d2->code)
      || (d1->test_elt_zero_int && d2->test_elt_zero_int
	  && d1->elt_zero_int != d2->elt_zero_int)
      || (d1->test_elt_one_int && d2->test_elt_one_int
	  && d1->elt_one_int != d2->elt_one_int)
      || (d1->test_elt_zero_wide && d2->test_elt_zero_wide
	  && d1->elt_zero_wide != d2->elt_zero_wide)
      || (d1->veclen && d2->veclen && d1->veclen != d2->veclen))
    return 1;

  /* If either is a wild-card MATCH_OPERAND without a predicate, it can match
     absolutely anything, so we can't say that no intersection is possible.
     This case is detected by having a zero TESTS field with a code of
     UNKNOWN.  */

  if ((d1->tests == 0 && d1->code == UNKNOWN)
      || (d2->tests == 0 && d2->code == UNKNOWN))
    return 0;

  /* If either has a predicate that we know something about, set things up so
     that D1 is the one that always has a known predicate.  Then see if they
     have any codes in common.  */

  if (d1->pred >= 0 || d2->pred >= 0)
    {
      int i, j;

      if (d2->pred >= 0)
	p1 = d1, d1 = d2, d2 = p1;

      /* If D2 tests an explicit code, see if it is in the list of valid codes
	 for D1's predicate.  */
      if (d2->code != UNKNOWN)
	{
	  for (i = 0; i < NUM_RTX_CODE && preds[d1->pred].codes[i] != 0; i++)
	    if (preds[d1->pred].codes[i] == d2->code)
	      break;

	  if (preds[d1->pred].codes[i] == 0)
	    return 1;
	}

      /* Otherwise see if the predicates have any codes in common.  */

      else if (d2->pred >= 0)
	{
	  for (i = 0; i < NUM_RTX_CODE && preds[d1->pred].codes[i] != 0; i++)
	    {
	      for (j = 0; j < NUM_RTX_CODE; j++)
		if (preds[d2->pred].codes[j] == 0
		    || preds[d2->pred].codes[j] == preds[d1->pred].codes[i])
		  break;

	      if (preds[d2->pred].codes[j] != 0)
		break;
	    }

	  if (preds[d1->pred].codes[i] == 0)
	    return 1;
	}
    }

  /* If we got here, we can't prove that D1 and D2 cannot both be true.
     If we are only to check the top level, return 0.  Otherwise, see if
     we can prove that all choices in both successors are mutually
     exclusive.  If either does not have any successors, we can't prove
     they can't both be true.  */

  if (toplevel || d1->success.first == 0 || d2->success.first == 0)
    return 0;

  for (p1 = d1->success.first; p1; p1 = p1->next)
    for (p2 = d2->success.first; p2; p2 = p2->next)
      if (! not_both_true (p1, p2, 0))
	return 0;

  return 1;
}

/* Assuming that we can reorder all the alternatives at a specific point in
   the tree (see discussion in merge_trees), we would prefer an ordering of
   nodes where groups of consecutive nodes test the same mode and, within each
   mode, groups of nodes test the same code.  With this order, we can
   construct nested switch statements, the inner one to test the code and
   the outer one to test the mode.

   We would like to list nodes testing for specific codes before those
   that test predicates to avoid unnecessary function calls.  Similarly,
   tests for specific modes should precede nodes that allow any mode.

   This function returns the merit (with 0 being the best) of inserting
   a test involving the specified MODE and CODE after node P.  If P is
   zero, we are to determine the merit of inserting the test at the front
   of the list.  */

static int
position_merit (p, mode, code)
     struct decision *p;
     enum machine_mode mode;
     enum rtx_code code;
{
  enum machine_mode p_mode;

  /* The only time the front of the list is anything other than the worst
     position is if we are testing a mode that isn't VOIDmode.  */
  if (p == 0)
    return mode == VOIDmode ? 3 : 2;

  p_mode = p->enforce_mode ? p->mode : VOIDmode;

  /* The best case is if the codes and modes both match.  */
  if (p_mode == mode && p->code== code)
    return 0;

  /* If the codes don't match, the next best case is if the modes match.
     In that case, the best position for this node depends on whether
     we are testing for a specific code or not.  If we are, the best place
     is after some other test for an explicit code and our mode or after
     the last test in the previous mode if every test in our mode is for
     an unknown code.

     If we are testing for UNKNOWN, then the next best case is at the end of
     our mode.  */

  if ((code != UNKNOWN
       && ((p_mode == mode && p->code != UNKNOWN)
	   || (p_mode != mode && p->next
	       && (p->next->enforce_mode ? p->next->mode : VOIDmode) == mode
	       && (p->next->code == UNKNOWN))))
      || (code == UNKNOWN && p_mode == mode
	  && (p->next == 0
	      || (p->next->enforce_mode ? p->next->mode : VOIDmode) != mode)))
    return 1;

  /* The third best case occurs when nothing is testing MODE.  If MODE
     is not VOIDmode, then the third best case is after something of any
     mode that is not VOIDmode.  If we are testing VOIDmode, the third best
     place is the end of the list.  */

  if (p_mode != mode
      && ((mode != VOIDmode && p_mode != VOIDmode)
	  || (mode == VOIDmode && p->next == 0)))
    return 2;

  /* Otherwise, we have the worst case.  */
  return 3;
}

/* Merge two decision tree listheads OLDH and ADDH,
   modifying OLDH destructively, and return the merged tree.  */

static struct decision_head
merge_trees (oldh, addh)
     register struct decision_head oldh, addh;
{
  struct decision *add, *next;

  if (oldh.first == 0)
    return addh;

  if (addh.first == 0)
    return oldh;

  /* If we are adding things at different positions, something is wrong.  */
  if (strcmp (oldh.first->position, addh.first->position))
    abort ();

  for (add = addh.first; add; add = next)
    {
      enum machine_mode add_mode = add->enforce_mode ? add->mode : VOIDmode;
      struct decision *best_position = 0;
      int best_merit = 4;
      struct decision *old;

      next = add->next;

      /* The semantics of pattern matching state that the tests are done in
	 the order given in the MD file so that if an insn matches two
	 patterns, the first one will be used.  However, in practice, most,
	 if not all, patterns are unambiguous so that their order is 
	 independent.  In that case, we can merge identical tests and
	 group all similar modes and codes together.

	 Scan starting from the end of OLDH until we reach a point
	 where we reach the head of the list or where we pass a pattern
	 that could also be true if NEW is true.  If we find an identical
	 pattern, we can merge them.  Also, record the last node that tests
	 the same code and mode and the last one that tests just the same mode.

	 If we have no match, place NEW after the closest match we found.  */
	 
      for (old = oldh.last; old; old = old->prev)
	{
	  int our_merit;

	  /* If we don't have anything to test except an additional test,
	     do not consider the two nodes equal.  If we did, the test below
	     would cause an infinite recursion.  */
	  if (old->tests == 0 && old->test_elt_zero_int == 0
	      && old->test_elt_one_int == 0 && old->veclen == 0
	      && old->test_elt_zero_wide == 0
	      && old->dupno == -1 && old->mode == VOIDmode
	      && old->code == UNKNOWN
	      && (old->c_test != 0 || add->c_test != 0))
	    ;

	  else if ((old->tests == add->tests
		    || (old->pred >= 0 && old->pred == add->pred)
		    || (old->tests && add->tests
			&& !strcmp (old->tests, add->tests)))
		   && old->test_elt_zero_int == add->test_elt_zero_int
		   && old->elt_zero_int == add->elt_zero_int
		   && old->test_elt_one_int == add->test_elt_one_int
		   && old->elt_one_int == add->elt_one_int
		   && old->test_elt_zero_wide == add->test_elt_zero_wide
		   && old->elt_zero_wide == add->elt_zero_wide
		   && old->veclen == add->veclen
		   && old->dupno == add->dupno
		   && old->opno == add->opno
		   && old->code == add->code
		   && old->enforce_mode == add->enforce_mode
		   && old->mode == add->mode)
	    {
	      /* If the additional test is not the same, split both nodes
		 into nodes that just contain all things tested before the
		 additional test and nodes that contain the additional test
		 and actions when it is true.  This optimization is important
		 because of the case where we have almost identical patterns
		 with different tests on target flags.  */

	      if (old->c_test != add->c_test
		  && ! (old->c_test && add->c_test
			&& !strcmp (old->c_test, add->c_test)))
		{
		  if (old->insn_code_number >= 0 || old->opno >= 0)
		    {
		      struct decision *split
			= (struct decision *) xmalloc (sizeof (struct decision));

		      mybcopy ((char *) old, (char *) split,
			       sizeof (struct decision));

		      old->success.first = old->success.last = split;
		      old->c_test = 0;
		      old->opno = -1;
		      old->insn_code_number = -1;
		      old->num_clobbers_to_add = 0;

		      split->number = next_number++;
		      split->next = split->prev = 0;
		      split->mode = VOIDmode;
		      split->code = UNKNOWN;
		      split->veclen = 0;
		      split->test_elt_zero_int = 0;
		      split->test_elt_one_int = 0;
		      split->test_elt_zero_wide = 0;
		      split->tests = 0;
		      split->pred = -1;
		      split->dupno = -1;
		    }

		  if (add->insn_code_number >= 0 || add->opno >= 0)
		    {
		      struct decision *split
			= (struct decision *) xmalloc (sizeof (struct decision));

		      mybcopy ((char *) add, (char *) split,
			       sizeof (struct decision));

		      add->success.first = add->success.last = split;
		      add->c_test = 0;
		      add->opno = -1;
		      add->insn_code_number = -1;
		      add->num_clobbers_to_add = 0;

		      split->number = next_number++;
		      split->next = split->prev = 0;
		      split->mode = VOIDmode;
		      split->code = UNKNOWN;
		      split->veclen = 0;
		      split->test_elt_zero_int = 0;
		      split->test_elt_one_int = 0;
		      split->test_elt_zero_wide = 0;
		      split->tests = 0;
		      split->pred = -1;
		      split->dupno = -1;
		    }
		}

	      if (old->insn_code_number >= 0 && add->insn_code_number >= 0)
		{
		  /* If one node is for a normal insn and the second is
		     for the base insn with clobbers stripped off, the
		     second node should be ignored.  */

		  if (old->num_clobbers_to_add == 0
		      && add->num_clobbers_to_add > 0)
		    /* Nothing to do here.  */
		    ;
		  else if (old->num_clobbers_to_add > 0
			   && add->num_clobbers_to_add == 0)
		    {
		      /* In this case, replace OLD with ADD.  */
		      old->insn_code_number = add->insn_code_number;
		      old->num_clobbers_to_add = 0;
		    }
		  else
		    fatal ("Two actions at one point in tree");
		}

	      if (old->insn_code_number == -1)
		old->insn_code_number = add->insn_code_number;
	      old->success = merge_trees (old->success, add->success);
	      add = 0;
	      break;
	    }

	  /* Unless we have already found the best possible insert point,
	     see if this position is better.  If so, record it.  */

	  if (best_merit != 0
	      && ((our_merit = position_merit (old, add_mode, add->code))
		  < best_merit))
	    best_merit = our_merit, best_position = old;

	  if (! not_both_true (old, add, 0))
	    break;
	}

      /* If ADD was duplicate, we are done.  */