/* Superoptimizer.  Finds the shortest instruction sequences for an
   arbitrary function f(x,y) where x and y are integers.  The algorithm is
   based on exhaustive search with backtracking and iterative deepening.

   Copyright (C) 1991, 1992 Free Software Foundation, Inc.

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 2, or (at your option) any
   later version.

   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License along
   with this program; see the file COPYING.  If not, write to the Free
   Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */

#include <stdio.h>

#include "superopt.h"
#include "run_program.def"
#include "version.h"

int goal_function_arity;
enum goal_func goal_function;
word (*eval_goal_function) (const word *);

int flag_output_assembler = 0;
int flag_use_carry = 1;

/* Counts the number of solutions found.  Flags to top loop that it should
   not go deeper.  */
int success;

#ifdef TIMING
#ifndef USG
#include <sys/time.h>
#include <sys/resource.h>

unsigned long
cputime ()
{
    struct rusage rus;

    getrusage (0, &rus);
    return rus.ru_utime.tv_sec * 1000 + rus.ru_utime.tv_usec / 1000;
}
#else
#include <time.h>

unsigned long
cputime ()
{
  return clock () / 1000;
}
#endif
int timings[100];
#endif

#ifdef STATISTICS
unsigned int heuristic_reject_count = 0;
unsigned int heuristic_accept_count = 0;
#endif

char *insn_name[] =
{
#undef	DEF_INSN
#define DEF_INSN(SYM,CLASS,NAME) NAME,
#include "insn.def"
};

char insn_class[] =
{
#undef	DEF_INSN
#define DEF_INSN(SYM,CLASS,NAME) CLASS,
#include "insn.def"
};

/* Initialize the "immediate" values in the top registers.  */
void
init_immediates(word *values)
{
  int i;
  for (i = -1; i < BITS_PER_WORD; i++)
    values[0x20 + i] = i;

  values[0x20 - 2] = VALUE_MIN_SIGNED;
  values[0x20 - 3] = VALUE_MAX_SIGNED;
}

inline word
random_word(void)
{
#ifdef __hpux
  return mrand48();
#else
  /* random returns 31 bits.  We need 32.  */
  return random() ^ (random() << 1);
#endif
}

char *
xrealloc (ptr, size)
     char *ptr;
     unsigned size;
{
  char *result = (char *) realloc (ptr, size);
  if (!result)
    abort ();
  return result;
}

char *
xmalloc (size)
     unsigned size;
{
  register char *val = (char *) malloc (size);

  if (val == 0)
    abort ();
  return val;
}

#define RECURSE(opcode, s1, s2, prune_hint) \
  recurse(opcode, n_values, s1, s2, v, 1, sequence, n_insns, values,	\
	  n_values + 1, goal_value, allowed_cost, co, prune_hint)
#define CRECURSE_2OP(opcode, d, s1, s2, cost, prune_hint) \
  recurse(opcode, d, s1, s2, v, cost, sequence, n_insns, values,	\
	  n_values, goal_value, allowed_cost, co, prune_hint)
#define CRECURSE_NEW(opcode, d, s1, s2, cost, prune_hint) \
  recurse(opcode, d, s1, s2, v, cost, sequence, n_insns, values,	\
	  n_values + 1, goal_value, allowed_cost, co, prune_hint)

/* Save the last generated instruction and recursively call `synth', if we
   are not at a leaf node.  Otherwise test the computed value and
   back-track.  This function is extremely critical for the performance!

   OPCODE is the opcode of the insn that was just generated.

   D is the destination register.

   S1 is the left source register or immediate reference.  It is an
   immediate reference if IMMEDIATE_P(S1) is true.

   S2 is the right source register or immediate reference.  It is an
   immediate reference if IMMEDIATE_P(S2) is true.

   V is the computed result from "rD = rS1 OPCODE rS2".

   COST is the cost of OPCODE with the the actual operands.

   SEQUENCE is the insn sequence so far, excluding the just generated insn.

   N_INSNS is the number of insns in SEQUENCE.

   VALUES contains the values in register 0..N_VALUES.

   N_VALUES is the number of registers that have been assigned values by
   the insns so far.

   GOAL_VALUE is the value we aim at, when the sequence is ready.

   ALLOWED_COST is the maximum allowed cost of the remaining sequence.

   CY is the carry flag.  It is negative if it has an undefined value (this
   for pruning the search tree), and otherwise takes the values 0 or 1
   according to the conventions of the current target.

   PRUNE_HINT contains flags to assist pruning of the search tree.  */

static inline void
recurse(opcode_t opcode,
	int d,
	int s1,
	int s2,
	word v,
	int cost,
	insn_t *sequence,
	int n_insns,
	word *values,
	int n_values,
	const word goal_value,
	int allowed_cost,
	int cy,
	int prune_flags)
{
  insn_t insn;

  /* Update the remaining allowed cost with the cost of the last
     instruction.  */
  allowed_cost -= cost;

  if (allowed_cost > 0)
    {
      /* ALLOWED_COST is still positive, meaning we can generate more
	 instructions.  */
      word old_d;

      old_d = values[d];	/* Remember old value of dest. reg.  */
      values[d] = v;

#if __GNUC__
      sequence[n_insns] = (insn_t) {opcode, s1, s2, d};
#else
      insn.opcode = opcode;
      insn.s1 = s1;
      insn.s2 = s2;
      insn.d = d;
      sequence[n_insns] = insn;
#endif

      synth(sequence, n_insns + 1, values, n_values,
	    goal_value, allowed_cost, cy, prune_flags);

      values[d] = old_d;	/* Restore value of dest. reg. */
    }
  else if (goal_value == v)
    {
      /* We are at a leaf node and got the right answer for the
	 random value operands.  However, we probably have an
	 incorrect sequence.  Call test_sequence to find out.  */

#if __GNUC__
      sequence[n_insns] = (insn_t) {opcode, s1, s2, d};
#else
      insn.opcode = opcode;
      insn.s1 = s1;
      insn.s2 = s2;
      insn.d = d;
      sequence[n_insns] = insn;
#endif
      test_sequence(sequence, n_insns + 1);

#ifdef STATISTICS
  heuristic_accept_count++;
#endif

    }
#ifdef STATISTICS
  else
    heuristic_reject_count++;
#endif
}

#define NAME(op) operand_names[op]
static char *operand_names[256]=
{
#if SPARC
  "%i0", "%i1", "%i2", "%i3", "%i4", "%i5", "%i6", "%i7",
#elif RS6000
  "r3", "r4", "r5", "r6", "r7", "r8", "r9", "r10",
#elif M88000
  "r2", "r3", "r4", "r5", "r6", "r7", "r8", "r9",
#elif AM29K
  "lr2", "lr3", "lr4", "lr5", "lr6", "lr7", "lr8", "lr9",
#elif M68000
  "d0", "d1", "d2", "d3", "d4", "d5", "d6", "d7",
#elif I386
  "%eax", "%edx", "%ecx", "%ebx", "%esi", "%edi", "%noooo!", "%crash!!!",
#elif PYR
  "pr0", "pr1", "pr2", "pr3", "pr4", "pr5", "pr6", "pr7",
#elif ALPHA
  "r0", "r1", "r2", "r3", "r4", "r5", "r6", "r7",
#else
#error no register names for this CPU
#endif
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
#if SPARC
  "???%hi(0x7fffffff)","%hi(0x80000000)","-1","%g0","1","2","3","4","5","6",
  "7","8","9","10","11","12","13","14","15","16","17","18","19",
  "20","21","22","23","24","25","26","27","28","29","30","31",
#elif RS6000
  "0x7fff","0x8000","-1","0","1","2","3","4","5","6",
  "7","8","9","10","11","12","13","14","15","16","17","18","19",
  "20","21","22","23","24","25","26","27","28","29","30","31",
#elif M88000
  "hi16(0x7fffffff)","hi16(0x80000000)","-1","r0","1","2","3","4","5","6",
  "7","8","9","10","11","12","13","14","15","16","17","18","19",
  "20","21","22","23","24","25","26","27","28","29","30","31",
#elif AM29K
  "0x7fff","0x8000","-1","0","1","2","3","4","5","6",
  "7","8","9","10","11","12","13","14","15","16","17","18","19",
  "20","21","22","23","24","25","26","27","28","29","30","31",
#elif M68000
  "#0x7fffffff","#0x80000000","#-1","#0","#1","#2","#3","#4","#5","#6",
  "#7","#8","#9","#10","#11","#12","#13","#14","#15","#16","#17","#18","#19",
  "#20","#21","#22","#23","#24","#25","#26","#27","#28","#29","#30","#31",
#elif I386
  "$0x7fffffff","$0x80000000","$-1","$0","$1","$2","$3","$4","$5","$6",
  "$7","$8","$9","$10","$11","$12","$13","$14","$15","$16","$17","$18","$19",
  "$20","$21","$22","$23","$24","$25","$26","$27","$28","$29","$30","$31",
#elif PYR
  "$0x7fffffff","$0x80000000","$-1","$0","$1","$2","$3","$4","$5","$6",
  "$7","$8","$9","$10","$11","$12","$13","$14","$15","$16","$17","$18","$19",
  "$20","$21","$22","$23","$24","$25","$26","$27","$28","$29","$30","$31",
#elif ALPHA
  "0x7fff","0x8000","-1","$31","1","2","3","4","5","6",
  "7","8","9","10","11","12","13","14","15","16","17","18","19",
  "20","21","22","23","24","25","26","27","28","29","30","31",
  "32","33","34","35","36","37","38","39","40","41","42","43",
  "44","45","46","47","48","49","50","51","52","53","54","55",
  "56","57","58","59","60","61","62","63",
#else
#error no constant syntax for this CPU
#endif
};

/* Output INSN in assembler mnemonic format on stdout.  */

void
output_assembler(insn_t insn)
{
  int d, s1, s2;

  d = insn.d;
  s1 = insn.s1;
  s2 = insn.s2;

  printf("\t");
  switch (insn.opcode)
    {
#if SPARC
    case COPY:
      if (IMMEDIATE_P(s1) && (IMMEDIATE_VAL(s1) & 0x1fff) == 0)
	printf("sethi	%s,%s",NAME(s1),NAME(d));
      else
	printf("mov	%s,%s",NAME(s1),NAME(d));
      break;
    case ADD:	printf("add	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case ADD_CI:printf("addx	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case ADD_CO:printf("addcc	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case ADD_CIO:printf("addxcc	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case SUB:
      if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == -1)
	printf("xnor	%%g0,%s,%s",NAME(s2),NAME(d));
      else
	printf("sub	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));
      break;
    case SUB_CI:printf("subx	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case SUB_CO:printf("subcc	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case SUB_CIO:printf("subxcc	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case AND:	printf("and	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case IOR:	printf("or	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case XOR:	printf("xor	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case ANDC:	printf("andn	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case IORC:	printf("orn	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case EQV:	printf("xnor	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case LSHIFTR:printf("srl	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case ASHIFTR:printf("sra	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case SHIFTL:printf("sll	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
#elif RS6000
    case COPY:
      if (IMMEDIATE_P(s1))
	{
	  if (IMMEDIATE_VAL(s1) >= 0 && IMMEDIATE_VAL(s1) < 0x8000)
	    printf("lil	%s,0x%x",NAME(d),IMMEDIATE_VAL(s1));
	  else
	    printf("liu	%s,%s",NAME(d),NAME(s1));
	}
      else
	printf("oril	%s,%s,0",NAME(d),NAME(s1));
      break;
    case ADD:
      if (IMMEDIATE_P(s2))
	{
	  if (IMMEDIATE_VAL(s2) + 0x4000 < 0x8000)
	    printf("cal	%s,%d(%s)",NAME(d),IMMEDIATE_VAL(s2),NAME(s1));
	  else if ((IMMEDIATE_VAL(s2) & 0xffff) == 0)
	    printf("cau	%s,%s,0x%x",NAME(d),NAME(s1),IMMEDIATE_VAL(s2) >> 16);
	  else
	    abort ();
	}
      else
	printf("cax     %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;
    case ADD_CO:
      if (IMMEDIATE_P(s2))
	printf("ai	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      else
	printf("a	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;
    case ADD_CIO:
      if (IMMEDIATE_P(s2))
	{
	  if (IMMEDIATE_VAL(s2) == -1)
	    printf("ame	%s,%s",NAME(d),NAME(s1));
	  else if (IMMEDIATE_VAL(s2) == 0)
	    printf("aze	%s,%s",NAME(d),NAME(s1));
	}
      else
	printf("ae	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;
    case SUB:
      if (IMMEDIATE_P(s1))
	{
	  if (IMMEDIATE_VAL(s1) == 0)
	    printf("neg	%s,%s",NAME(d),NAME(s2));
	  else if (IMMEDIATE_VAL(s1) == -1)
	    printf("nand	%s,%s,%s",NAME(d),NAME(s2),NAME(s2));
	}
      else abort();
      break;
    case ADC_CO:
      if (IMMEDIATE_P(s1))
	printf("sfi	%s,%s,%s",NAME(d),NAME(s2),NAME(s1));
      else
	printf("sf	%s,%s,%s",NAME(d),NAME(s2),NAME(s1));
      break;
    case ADC_CIO:
      if (IMMEDIATE_P(s1))
	{
	  if (IMMEDIATE_VAL(s1) == -1)
	    printf("sfme	%s,%s",NAME(d),NAME(s2));
	  else if (IMMEDIATE_VAL(s1) == 0)
	    printf("sfze	%s,%s",NAME(d),NAME(s2));
	  else abort();
	}
      else
	printf("sfe	%s,%s,%s",NAME(d),NAME(s2),NAME(s1));
      break;
    case AND:
      if (IMMEDIATE_P(s2))
	{
	  if (IMMEDIATE_VAL(s2) == 0x80000000)
	    printf("rlinm	%s,%s,0,0,0",NAME(d),NAME(s1));
	  else if (IMMEDIATE_VAL(s2) == 0x7fffffff)
	    printf("rlinm	%s,%s,0,1,31",NAME(d),NAME(s1));
	  else if (IMMEDIATE_VAL(s2) == 1)
	    printf("rlinm	%s,%s,0,31,31",NAME(d),NAME(s1));
	  else abort();
	}
      else
	printf("and	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;
    case IOR:
      if (IMMEDIATE_P(s2))
	{
	  if (IMMEDIATE_VAL(s2) == 0x80000000)
	    printf("oriu	%s,%s,0x8000",NAME(d),NAME(s1));
	  else abort();
	}
      else
	printf("or	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;
    case XOR:
      if (IMMEDIATE_P(s2))
	{
	  if (IMMEDIATE_VAL(s2) == 1)
	    printf("xoril\t%s,%s,1",NAME(d),NAME(s1));
	  else if (IMMEDIATE_VAL(s2) == 0x80000000)
	    printf("xoriu\t%s,%s,0x8000",NAME(d),NAME(s1));
	  else abort();
	}
      else
	printf("xor	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;
    case ANDC:	printf("andc	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case IORC:	printf("orc	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case EQV:	printf("eqv	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case NAND:	printf("nand	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case NOR:	printf("nor	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case LSHIFTR:
      if (IMMEDIATE_P(s2))
	printf("sri	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      else
	printf("sre	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;
    case ASHIFTR_CON:
      if (IMMEDIATE_P(s2))
	printf("srai	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      else
	printf("srea	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;
    case SHIFTL:
      if (IMMEDIATE_P(s2))
	printf("sli	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      else
	printf("sle	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;
    case ROTATEL:
      if (IMMEDIATE_P(s2))
	printf("rlinm	%s,%s,%s,0,31",NAME(d),NAME(s1),NAME(s2));
      else
	printf("rlnm	%s,%s,%s,0,31",NAME(d),NAME(s1),NAME(s2));
      break;
    case ABSVAL:printf("abs	%s,%s",NAME(d),NAME(s1));break;
    case NABSVAL:printf("nabs	%s,%s",NAME(d),NAME(s1));break;
    case DOZ:
      if (IMMEDIATE_P(s1))
	printf("dozi	%s,%s,%s",NAME(d),NAME(s2),NAME(s1));
      else
	printf("doz	%s,%s,%s",NAME(d),NAME(s2),NAME(s1));
      break;
    case MUL:
      if (IMMEDIATE_P(s1))
	printf("muli	%s,%s,%s",NAME(d),NAME(s2),NAME(s1));
      else
	printf("muls	%s,%s,%s",NAME(d),NAME(s2),NAME(s1));
      break;
    case CLZ:
      printf("cntlz	%s,%s",NAME(d),NAME(s1));break;
      
#elif M88000
    case COPY:
      if (IMMEDIATE_P(s1))
	{
	  if ((IMMEDIATE_VAL(s1) & 0xffff) == 0)
	    printf("or.u	%s,r0,0x%x",NAME(d),IMMEDIATE_VAL(s1));
	  else if ((IMMEDIATE_VAL(s1) & 0xffff0000) == 0)
	    printf("or	%s,r0,0x%x",NAME(d),IMMEDIATE_VAL(s1));
	  else if ((IMMEDIATE_VAL(s1) & 0xffff0000) == 0xffff0000)
	    printf("subu	%s,r0,0x%x",NAME(d),-IMMEDIATE_VAL(s1));
	  else
	    {
	      word x = IMMEDIATE_VAL(s1);
	      int i, j;
	      for (i = 31; i > 0; i--)
		if ((x & (1 << i)) != 0)
		  break;
	      for (j = i; j >= 0; j--)
		if ((x & (1 << j)) == 0)
		  break;
	      printf("set	%s,r0,%d<%d>",NAME(d), i - j, j + 1);
	    }
	}
      else
	printf("or	%s,%s",NAME(d),NAME(s1));
      break;
    case ADD:	printf("addu	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case ADD_CI:printf("addu.ci	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case ADD_CO:printf("addu.co	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case ADD_CIO:
      if (IMMEDIATE_P(s2))
	{
	  if (IMMEDIATE_VAL(s2) == -1)
	    {
	      printf("subu.cio %s,%s,r0",NAME(d),NAME(s1));
	      break;
	    }
	  if (IMMEDIATE_VAL(s2) != 0)
	    abort();
	}
      printf("addu.cio %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;      
    case SUB:
      if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == -1)
	printf("xor.c	%s,%s,r0",NAME(d),NAME(s2));
      else
	printf("subu	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;
    case ADC_CI:printf("subu.ci	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case ADC_CO:printf("subu.co	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case ADC_CIO:printf("subu.cio %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case AND:
      if (IMMEDIATE_P(s2))
	{
	  if (IMMEDIATE_VAL(s2) == 0x80000000)
	    printf("mask.u	%s,%s,0x8000",NAME(d),NAME(s1));
	  else if (IMMEDIATE_VAL(s2) == 0x7fffffff)
	    printf("and.u	%s,%s,0x7fff",NAME(d),NAME(s1));
	  else if (IMMEDIATE_VAL(s2) == 1)
	    printf("mask	%s,%s,1",NAME(d),NAME(s1));
	  else abort();
	}
      else
	printf("and	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;
    case IOR:
      if (IMMEDIATE_P(s2))
	{
	  if ((IMMEDIATE_VAL(s2) & 0xffff) == 0)
	    printf("or.u	%s,%s,0x%x",NAME(d),NAME(s1),
		   IMMEDIATE_VAL(s2)>>16);
	  else if (IMMEDIATE_VAL(s2) < 0x10000)
	    printf("or	%s,%s,0x%x",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
	  else abort();
	}
      else
	printf("or	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;
    case XOR:
      if (IMMEDIATE_P(s2))
	{
	  if ((IMMEDIATE_VAL(s2) & 0xffff) == 0)
	    printf("xor.u	%s,%s,0x%x",NAME(d),NAME(s1),
		   IMMEDIATE_VAL(s2)>>16);
	  else if (IMMEDIATE_VAL(s2) < 0x10000)
	    printf("xor	%s,%s,0x%x",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
	  else abort();
	}
      else
	printf("xor	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;
    case ANDC:	printf("and.c	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case IORC:	printf("or.c	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case EQV:	printf("xor.c	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case LSHIFTR:printf("extu	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case ASHIFTR:printf("ext	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case SHIFTL:printf("mak	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case ROTATEL:
      printf("rot	%s,%s,%d",NAME(d),NAME(s1),32-IMMEDIATE_VAL(s2));
      break;
    case FF1:
      printf("ff1	%s,%s",NAME(d),NAME(s1)); break;
    case FF0:
      printf("ff0	%s,%s",NAME(d),NAME(s1)); break;
    case CMPPAR:
      if (IMMEDIATE_P(s2))
	printf("cmp	%s,%s,0x%x",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
      else if (IMMEDIATE_P(s1))
	printf("cmp	%s,r0,%s",NAME(d),NAME(s2));
      else
	printf("cmp	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;
    case EXTS1:
      printf("ext	%s,%s,1<%d>",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
      break;      
    case EXTS2:
      printf("ext	%s,%s,2<%d>",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
      break;      
    case EXTU1:
      printf("extu	%s,%s,1<%d>",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
      break;      
    case EXTU2:
      printf("extu	%s,%s,2<%d>",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
      break;      
    case MUL:
      printf("mul	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;      
#elif AM29K
    case COPY:
      if (IMMEDIATE_P(s1))
	{
	  if (IMMEDIATE_VAL(s1) < 0x10000)
	    printf("const	%s,0x%x",NAME(d),IMMEDIATE_VAL(s1));
	  else if (-IMMEDIATE_VAL(s1) < 0x10000)
	    printf("constn	%s,-0x%x",NAME(d),-IMMEDIATE_VAL(s1));
	  else if (IMMEDIATE_VAL(s1) == 0x80000000)
	    printf("cpeq	%s,gr1,gr1",NAME(d));
	  else abort();
	}
      else
	printf("or	%s,%s,0",NAME(d),NAME(s1));
      break;
    case ADD_CO:
      if (IMMEDIATE_P(s2) && (signed_word) IMMEDIATE_VAL(s2) < 0)
	printf("sub	%s,%s,0x%x",NAME(d),NAME(s1),-IMMEDIATE_VAL(s2));
      else
	printf("add	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;
    case ADD_CIO:
      if (IMMEDIATE_P(s2) && (signed_word) IMMEDIATE_VAL(s2) < 0)
	printf("subc	%s,%s,0x%x",NAME(d),NAME(s1),-IMMEDIATE_VAL(s2));
      else
	printf("addc	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;
    case SUB:
      if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == -1)
	printf("nor	%s,%s,0",NAME(d),NAME(s2));
      else abort();
      break;
    case ADC_CO:printf("sub	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case ADC_CIO:printf("subc	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case AND:	printf("and	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case IOR:	printf("or	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case XOR:	printf("xor	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case ANDC:	printf("andn	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case EQV:	printf("xnor	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case NAND:	printf("nand	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case NOR:	printf("nor	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case LSHIFTR:printf("srl	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case ASHIFTR:printf("sra	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case SHIFTL:printf("sll	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case CPEQ:	printf("cpeq	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case CPGE:	printf("cpge	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case CPGEU:	printf("cpgeu	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case CPGT:	printf("cpgt	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case CPGTU:	printf("cpgtu	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case CPLE:	printf("cple	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case CPLEU:	printf("cpleu	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case CPLT:	printf("cplt	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case CPLTU:	printf("cpltu	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case CPNEQ:	printf("cpneq	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
    case MUL:
      printf("multiply	%s,%s,%s",NAME(d),NAME(s1),NAME(s2));
      break;      
    case CLZ:
      printf("clz	%s,%s",NAME(d),NAME(s1));break;
#elif M68000
    case COPY:
      if (IMMEDIATE_P(s1))
	{
	  if ((signed_word) IMMEDIATE_VAL(s1) >= -128
	      && (signed_word) IMMEDIATE_VAL(s1) < 128)
	    {
	      printf("moveq	#%ld,%s", IMMEDIATE_VAL(s1),NAME(d));
	      break;
	    }
	}
      printf("movel	%s,%s",NAME(s1),NAME(d));
      break;
    case EXCHANGE:
      printf("exgl	%s,%s",NAME(s2),NAME(d));break;
    case ADD_CO:
      if (IMMEDIATE_P(s2)
	  && IMMEDIATE_VAL(s2) >= 1 && IMMEDIATE_VAL(s2) <= 8)
	printf("addql	%s,%s",NAME(s2),NAME(d));
      else
	printf("addl	%s,%s",NAME(s2),NAME(d));
      break;
    case ADD_CIO:
      printf("addxl	%s,%s",NAME(s2),NAME(d));break;
    case SUB:
      if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == -1)
	printf("notl	%s",NAME(d));
      else abort();
      break;
    case SUB_CO:
      if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == 0)
	printf("negl	%s",NAME(d));
      else if (IMMEDIATE_P(s2)
	       && IMMEDIATE_VAL(s2) >= 1 && IMMEDIATE_VAL(s2) <= 8)
	printf("subql	%s,%s",NAME(s2),NAME(d));
      else
	printf("subl	%s,%s",NAME(s2),NAME(d));
      break;
    case SUB_CIO:
      if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == 0)
	printf("negxl	%s",NAME(d));
      else
	printf("subxl	%s,%s",NAME(s2),NAME(d));
      break;
    case AND:
      if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) + 0x8000 < 0x10000)
	printf("andw	%s,%s",NAME(s2),NAME(d));
      else
	printf("andl	%s,%s",NAME(s2),NAME(d));
      break;
    case IOR:
      if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) + 0x8000 < 0x10000)
	printf("orw	%s,%s",NAME(s2),NAME(d));
      else
	printf("orl	%s,%s",NAME(s2),NAME(d));
      break;
    case XOR:
      if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) + 0x8000 < 0x10000)
	printf("eorw	%s,%s",NAME(s2),NAME(d));
      else
	printf("eorl	%s,%s",NAME(s2),NAME(d));
      break;
    case LSHIFTR_CO:
      printf("lsrl	%s,%s",NAME(s2),NAME(d));break;
    case ASHIFTR_CO:
      printf("asrl	%s,%s",NAME(s2),NAME(d));break;
    case SHIFTL_CO:
      printf("lsll	%s,%s",NAME(s2),NAME(d));break;
    case ROTATEL_CO:
      printf("roll	%s,%s",NAME(s2),NAME(d));break;
    case ROTATEXL_CIO:
      printf("roxll	%s,%s",NAME(s2),NAME(d));break;
    case MUL:
      printf("mulsl	%s,%s",NAME(s2),NAME(d));break;      
#elif I386
    case COPY:
      printf("movl	%s,%s",NAME(s1),NAME(d));break;
    case EXCHANGE:
      printf("xchgl	%s,%s",NAME(s2),NAME(d));break;
    case ADD:
      if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) == 1)
	printf("incl	%s",NAME(d));
      else abort();
      break;
    case ADD_CO:
      printf("addl	%s,%s",NAME(s2),NAME(d));break;
    case ADD_CIO:
      printf("adcl	%s,%s",NAME(s2),NAME(d));break;
    case SUB:
      if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) == 1)
	printf("decl	%s",NAME(d));
      else if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == -1)
	printf("notl	%s",NAME(d));
      else abort();
      break;
    case SUB_CO:
      if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == 0)
	printf("negl	%s",NAME(d));
      else
	printf("subl	%s,%s",NAME(s2),NAME(d));
      break;
    case SUB_CIO:
      printf("sbbl	%s,%s",NAME(s2),NAME(d));break;
    case CMP:
      printf("cmpl	%s,%s",NAME(s2),NAME(s1));break;
    case AND_RC:
      if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) + 0x80 < 0x100)
	printf("andb	$%d,%s",IMMEDIATE_VAL(s2),NAME(d));
      else
	printf("andl	%s,%s",NAME(s2),NAME(d));
      break;
    case IOR_RC:
      if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) + 0x80 < 0x100)
	printf("orb	$%d,%s",IMMEDIATE_VAL(s2),NAME(d));
      else
	printf("orl	%s,%s",NAME(s2),NAME(d));
      break;
    case XOR_RC:
      if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) + 0x80 < 0x100)
	printf("xorb	$%d,%s",IMMEDIATE_VAL(s2),NAME(d));
      else
	printf("xorl	%s,%s",NAME(s2),NAME(d));
      break;
    case LSHIFTR_CO:
      printf("shrl	%s,%s",NAME(s2),NAME(d));break;
    case ASHIFTR_CO:
      printf("sarl	%s,%s",NAME(s2),NAME(d));break;
    case SHIFTL_CO:
      printf("shll	%s,%s",NAME(s2),NAME(d));break;
    case ROTATEL_CO:
      printf("roll	%s,%s",NAME(s2),NAME(d));break;
    case ROTATEXL_CIO:
      printf("rlcl	%s,%s",NAME(s2),NAME(d));break;
    case COMCY:
      printf("cmc");break;
    case MUL:
      printf("imull	%s,%s",NAME(s2),NAME(d));break;      
#elif PYR
    case COPY:
      printf("movw	%s,%s",NAME(s1),NAME(d));break;
    case EXCHANGE:
      printf("xchw	%s,%s",NAME(s2),NAME(d));break;
    case ADD:
      printf("mova	0x%x(%s),%s",IMMEDIATE_VAL(s2),NAME(s1),NAME(d));
      break;
    case ADD_CO:
      printf("addw	%s,%s",NAME(s2),NAME(d));break;
    case ADD_CIO:
      printf("addwc	%s,%s",NAME(s2),NAME(d));break;
    case ADC_CO:
      printf("subw	%s,%s",NAME(s2),NAME(d));break;
    case ADC_CIO:
      printf("subwb	%s,%s",NAME(s2),NAME(d));break;
    case AND_CC:
      printf("andw	%s,%s",NAME(s2),NAME(d));break;
    case IOR_CC:
      printf("orw	%s,%s",NAME(s2),NAME(d));break;
    case XOR_CC:
      printf("xorw	%s,%s",NAME(s2),NAME(d)); break;
    case ANDC_CC:
      printf("bicw	%s,%s",NAME(s2),NAME(d)); break;
    case LSHIFTR_CO:
      printf("lshrw	%s,%s",NAME(s2),NAME(d));break;
    case ASHIFTR_CO:
      printf("ashrw	%s,%s",NAME(s2),NAME(d));break;
    case SHIFTL_CO:
      printf("lshlw	%s,%s",NAME(s2),NAME(d));break;
    case MUL:
      printf("mulw	%s,%s",NAME(s2),NAME(d));break;      
#elif ALPHA
    case ADD:	printf("addq	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case SUB:
      if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == -1)
	printf("ornot	$31,%s,%s",NAME(s2),NAME(d));
      else
	printf("subq	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));
      break;
    case AND:	printf("and	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case IOR:	printf("bis	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case XOR:	printf("xor	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case ANDC:	printf("bic	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case IORC:	printf("ornot	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case EQV:	printf("eqv	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case LSHIFTR:printf("srl	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case ASHIFTR:printf("sra	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case SHIFTL:printf("sll	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case CMPEQ:	printf("cmpeq	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case CMPLE:	printf("cmple	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case CMPLEU:printf("cmpleu	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case CMPLT:	printf("cmplt	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case CMPLTU:printf("cmpltu	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case CMOVEQ:printf("cmoveq	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case CMOVNE:printf("cmovne	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case CMOVLT:printf("cmovlt	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case CMOVGE:printf("cmovge	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case CMOVLE:printf("cmovle	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
    case CMOVGT:printf("cmovgt	%s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
#else
#error no assembler output code for this CPU
#endif
    default:abort();
    }
  printf("\n");
}

word tvalues[0x100];

/* TEST_SETS contains sets of input values and corresponding goal value used
   to test the correctness of a sequence.  N_TEST_SETS says how many sets
   are defined.  */
word *test_sets;
int n_test_sets;

word test_operands[] =
{
  0,
  1,
  -1,
  -2,
  VALUE_MIN_SIGNED,
  VALUE_MAX_SIGNED,
  VALUE_MIN_SIGNED + 1,
  VALUE_MAX_SIGNED - 1,
};
#define N_TEST_OPERANDS (sizeof(test_operands)/sizeof(test_operands[0]))

void
init_test_sets()
{
  unsigned int loop_vars[8];
  int pc, i, j;
  word *test_set;
  const int arity = goal_function_arity;
  word (*eval) (const word *) = eval_goal_function;

  if (sizeof (loop_vars) / sizeof (loop_vars[0]) <= arity)
    abort ();

  /* Allocate enough space in TEST_SETS for all combinations of TEST_OPERANDS
     and an additional 10,000 random test sets.  */
  {
    static int n_words;

    j = 1 + arity;
    for (i = arity - 1; i >= 0; i--)
      j *= N_TEST_OPERANDS;

    j += (1 + arity) * 10000;

    if (n_words < j)
      {
	test_sets = (n_words == 0
		     ? (word *) xmalloc (sizeof (word) * j)
		     : (word *) xrealloc (test_sets, sizeof (word) * j));
	n_words = j;
      }
  }

  test_set = test_sets;
  j = 0;

  /* Start with all combinations of operands from TEST_OPERANDS.  */
  for (i = arity - 1; i >= 0; i--)
    loop_vars[i] = 0;
  for (;;)
    {
      for (i = arity - 1; i >= 0; i--)
	tvalues[i] = *test_set++ = test_operands[loop_vars[i]];

      /* Get the desired value for the current operand values.  */
      *test_set++ = (*eval)(tvalues);
      j++;

      /* General loop control.  This implements ARITY loops using induction
	 variables in loop_vars[0] through loop_vars[ARITY - 1].  */
      i = 0;
      loop_vars[i] = (loop_vars[i] + 1) % N_TEST_OPERANDS;
      while (loop_vars[i] == 0)
	{
	  i++;
	  if (i >= arity)
	    goto random;
	  loop_vars[i] = (loop_vars[i] + 1) % N_TEST_OPERANDS;
	}
    }

  /* Now add the additional random test sets.  */
 random:  
  for (i = 9999; i >= 0; i--)
    {
      for (pc = arity - 1; pc >= 0; pc--)
	tvalues[pc] = *test_set++ = random_word();

      *test_set++ = (*eval)(tvalues);
      j++;
    }

  n_test_sets = j;
}

/* Test the correctness of a sequence in SEQUENCE[0] through
   SEQUENCE[N_INSNS - 1].  */

void
test_sequence(insn_t *sequence, int n_insns)
{
  int pc;
  int i, j;
  word *test_set = test_sets;
  const int arity = goal_function_arity;

  /* Test each of the precomputed values.  */
  for (j = n_test_sets; j > 0; j--)
    {
      /* Update the tvalues array in each iteration, as execution of the
	 sequence might clobber the values.  (On 2-operand machines.)  */
      for (i = arity - 1; i >= 0; i--)
	tvalues[i] = *test_set++;

      /* Execute the synthesised sequence for the current operand
	 values.  */
      run_program (sequence, n_insns, tvalues);
      if (tvalues[sequence[n_insns - 1].d] != *test_set++)
	{
	  /* Adaptively rearrange the order of the tests.  This set of test
	     values is better than all that preceed it.  The optimal
	     ordering changes with the search space.  */
	  if ((j = n_test_sets - j) != 0)
	    {
	      int k = j >> 1;
	      j *= (arity + 1);
	      k *= (arity + 1);
	      for (i = 0; i <= arity; i++)
		{
		  word t = test_sets[j + i];
		  test_sets[j + i] = test_sets[k + i];
		  test_sets[k + i] = t;
		}
	    }
	  return;
	}
    }

  /* The tests passed.  Print the instruction sequence.  */
  if (success == 0)
    printf("\n");
  success++;

  printf("%d:", success);
  for (pc = 0; pc < n_insns; pc++)
    {
      insn_t insn;

      insn = sequence[pc];
      if (flag_output_assembler)
	output_assembler(insn);
      else
	{
	  if (insn.opcode == CMP)
	    printf("\t%s(", GET_INSN_NAME(insn.opcode));
	  else
	    printf("\tr%u:=%s(", insn.d, GET_INSN_NAME(insn.opcode));
	  if (IMMEDIATE_P(insn.s1))
	    {
	      if ((signed_word) IMMEDIATE_VAL(insn.s1) >= 10
		  || (signed_word) IMMEDIATE_VAL(insn.s1) <= -10)
		printf("0x%lx", IMMEDIATE_VAL(insn.s1));
	      else
		printf("%ld", IMMEDIATE_VAL(insn.s1));
	    }
	  else
	    printf("r%u", insn.s1);

	  if (!UNARY_OPERATION(insn))
	    {
	      if (IMMEDIATE_P(insn.s2))
		{
		  if ((signed_word) IMMEDIATE_VAL(insn.s2) >= 10
		      || (signed_word) IMMEDIATE_VAL(insn.s2) <= -10)
		    printf(",0x%lx", IMMEDIATE_VAL(insn.s2));
		  else
		    printf(",%ld", IMMEDIATE_VAL(insn.s2));
		}
	      else
		printf(",r%u", insn.s2);
	    }
	  printf(")\n");
	}
    }
  fflush(stdout);
}


/* Recursively investigate all possible instruction sequences for the
   current target.

   SEQUENCE contains the instructions defined so far.

   N_INSNS is the number of instructions, including the one we will
   generate this time, in SEQUENCE.

   VALUES contains the values in register 0..N_VALUES.

   N_VALUES is the number of registers that have been assigned values by
   the insns so far.

   GOAL_VALUE is the value we aim at, when the sequence is ready.

   ALLOWED_COST is the maximum allowed cost of the remaining sequence.

   CY_IN is the carry flag.  It is negative if no instruction has yet
   defined it (this to pruning the search tree), and otherwise takes the
   values 0 or 1 according to the conventions of the current target.

   PRUNE_HINT contains flags to assist pruning of the search tree.  */

#if SPARC || RS6000 || M88000 || AM29K || ALPHA
void
synth(insn_t *sequence,
      int n_insns,
      word *values,
      int n_values,
      word goal_value,
      int allowed_cost,
      int ci,
      int prune_hint)
{
  int s1, s2;
  word v, r1, r2;
  int co;
  int last_dest;

#ifdef TIMING
  int time_start = cputime();
#endif

  if (n_insns > 0)
    last_dest = sequence[n_insns - 1].d;
  else
    last_dest = -1;

  /* Binary operations with carry-in.  */
  if (ci >= 0 && flag_use_carry)
    {
      for (s1 = n_values - 1; s1 >= 0; s1--)
	{
	  r1 = values[s1];
	  for (s2 = s1 - 1; s2 >= 0; s2--)
	    {
	      r2 = values[s2];

	      if (allowed_cost <= 1 && (prune_hint & CY_JUST_SET) == 0)
		{
		  /* We are in a leaf node.  CY was not set (to 0, 1 or to
		     a data dependent value) by the previous insn.

		     So one of the input operands has to be the result
		     operand of the previous insn for that insn to be
		     meaningful.  */
		  if (last_dest >= 0 && s1 != last_dest && s2 != last_dest)
		    continue;
		}

#if SPARC || RS6000 || M88000 || AM29K
	      /* sparc:		addxcc
		 rs6000:	ae
		 m88000:	addu.cio
		 am29k:		addc */
	      PERFORM_ADD_CIO(v, co, r1, r2, ci);
	      RECURSE(ADD_CIO, s1, s2, CY_JUST_SET);
#endif
#if SPARC || M88000
	      /* sparc:		addx
		 m88000:	addu.ci */
	      PERFORM_ADD_CI(v, co, r1, r2, ci);
	      RECURSE(ADD_CI, s1, s2, prune_hint & ~CY_JUST_SET);
#endif
#if SPARC
	      /* sparc:		subxcc */
	      PERFORM_SUB_CIO(v, co, r1, r2, ci);
	      RECURSE(SUB_CIO, s1, s2, CY_JUST_SET);
	      PERFORM_SUB_CIO(v, co, r2, r1, ci);
	      RECURSE(SUB_CIO, s2, s1, CY_JUST_SET);
#endif
#if SPARC
	      /* sparc:		subx */
	      PERFORM_SUB_CI(v, co, r1, r2, ci);
	      RECURSE(SUB_CI, s1, s2, prune_hint & ~CY_JUST_SET);
	      PERFORM_SUB_CI(v, co, r2, r1, ci);
	      RECURSE(SUB_CI, s2, s1, prune_hint & ~CY_JUST_SET);
#endif
#if RS6000 || M88000 || AM29K
	      /* rs6000:	sfe
		 m88000:	subu.cio
		 am29k:		subc */
	      PERFORM_ADC_CIO(v, co, r1, r2, ci);
	      RECURSE(ADC_CIO, s1, s2, CY_JUST_SET);
	      PERFORM_ADC_CIO(v, co, r2, r1, ci);
	      RECURSE(ADC_CIO, s2, s1, CY_JUST_SET);
#endif
#if M88000
	      /* m88000:	subu.ci */
	      PERFORM_ADC_CI(v, co, r1, r2, ci);
	      RECURSE(ADC_CI, s1, s2, prune_hint & ~CY_JUST_SET);
	      PERFORM_ADC_CI(v, co, r2, r1, ci);
	      RECURSE(ADC_CI, s2, s1, prune_hint & ~CY_JUST_SET);
#endif
	    }
	}
    }

  /* Binary operations without carry-in.  */
  for (s1 = n_values - 1; s1 >= 0; s1--)
    {
      r1 = values[s1];
      for (s2 = s1 - 1; s2 >= 0; s2--)
	{
	  r2 = values[s2];

	  if (allowed_cost <= 1)
	    {
	      /* We are in a leaf node.

		 So one of the input operands has to be the result operand
		 of the previous insn for that insn to be meaningful.  */
	      if (last_dest >= 0 && s1 != last_dest && s2 != last_dest)
		continue;
	    }

#ifdef DM
	  PERFORM_UMULWIDEN_HI(v, co, r1, r2, ci);
	  RECURSE(UMULWIDEN_HI, s1, s2, prune_hint & ~CY_JUST_SET);
#endif
#if defined (DM) || defined (MM)
	  PERFORM_MUL(v, co, r1, r2, ci);
	  RECURSE(MUL, s1, s2, prune_hint & ~CY_JUST_SET);
#endif
#ifdef UDIV_WITH_SDIV
	  PERFORM_SDIV (v, co, r1, r2, ci);
	  RECURSE(SDIV, s1, s2, prune_hint & ~CY_JUST_SET);
#endif
#if SPARC || RS6000 || M88000 || AM29K
	  /* sparc:	addcc
	     rs6000:	a
	     m88000:	addu.co
	     am29k:	add */
	  PERFORM_ADD_CO(v, co, r1, r2, ci);
	  RECURSE(ADD_CO, s1, s2, CY_JUST_SET);
#endif
#if SPARC || RS6000 || M88000 || ALPHA
	  /* sparc:	add
	     rs6000:	cax
	     m88000:	addu
	     alpha:	addq */
	  PERFORM_ADD(v, co, r1, r2, ci);
	  RECURSE(ADD, s1, s2, prune_hint & ~CY_JUST_SET);
#endif
#if SPARC
	  /* sparc:	subcc */
	  PERFORM_SUB_CO(v, co, r1, r2, ci);
	  RECURSE(SUB_CO, s1, s2, CY_JUST_SET);
	  PERFORM_SUB_CO(v, co, r2, r1, ci);
	  RECURSE(SUB_CO, s2, s1, CY_JUST_SET);
#endif
#if SPARC || M88000 || ALPHA
	  /* sparc:	sub
	     m88000:	subu
	     alpha:	subq */
	  PERFORM_SUB(v, co, r1, r2, ci);
	  RECURSE(SUB, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_SUB(v, co, r2, r1, ci);
	  RECURSE(SUB, s2, s1, prune_hint & ~CY_JUST_SET);
#endif
#if RS6000 || M88000 || AM29K
	  /* rs6000:	sf
	     m88000:	subu.co
	     am29k:	sub */
	  PERFORM_ADC_CO(v, co, r1, r2, ci);
	  RECURSE(ADC_CO, s1, s2, CY_JUST_SET);
	  PERFORM_ADC_CO(v, co, r2, r1, ci);
	  RECURSE(ADC_CO, s2, s1, CY_JUST_SET);
#endif
#if SPARC || RS6000 || M88000 || AM29K || ALPHA
	  PERFORM_AND(v, co, r1, r2, ci);
	  RECURSE(AND, s1, s2, prune_hint & ~CY_JUST_SET);

	  PERFORM_IOR(v, co, r1, r2, ci);
	  RECURSE(IOR, s1, s2, prune_hint & ~CY_JUST_SET);

	  PERFORM_XOR(v, co, r1, r2, ci);
	  RECURSE(XOR, s1, s2, prune_hint & ~CY_JUST_SET);

	  PERFORM_ANDC(v, co, r1, r2, ci);
	  RECURSE(ANDC, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_ANDC(v, co, r2, r1, ci);
	  RECURSE(ANDC, s2, s1, prune_hint & ~CY_JUST_SET);
#endif
#if SPARC || RS6000 || M88000 || ALPHA
	  PERFORM_IORC(v, co, r1, r2, ci);
	  RECURSE(IORC, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_IORC(v, co, r2, r1, ci);
	  RECURSE(IORC, s2, s1, prune_hint & ~CY_JUST_SET);
#endif
#if SPARC || RS6000 || M88000 || AM29K || ALPHA
	  PERFORM_EQV(v, co, r1, r2, ci);
	  RECURSE(EQV, s1, s2, prune_hint & ~CY_JUST_SET);
#endif
#if RS6000 || AM29K
	  PERFORM_NAND(v, co, r1, r2, ci);
	  RECURSE(NAND, s1, s2, prune_hint & ~CY_JUST_SET);

	  PERFORM_NOR(v, co, r1, r2, ci);
	  RECURSE(NOR, s1, s2, prune_hint & ~CY_JUST_SET);
#endif
#if RS6000 && !defined (AVOID_DOZ)
	  PERFORM_DOZ(v, co, r1, r2, ci);
	  RECURSE(DOZ, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_DOZ(v, co, r2, r1, ci);
	  RECURSE(DOZ, s2, s1, prune_hint & ~CY_JUST_SET);
#endif
#if AM29K
	  PERFORM_CPEQ(v, co, r1, r2, ci);
	  RECURSE(CPEQ, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_CPGE(v, co, r1, r2, ci);
	  RECURSE(CPGE, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_CPGEU(v, co, r1, r2, ci);
	  RECURSE(CPGEU, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_CPGT(v, co, r1, r2, ci);
	  RECURSE(CPGT, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_CPGTU(v, co, r1, r2, ci);
	  RECURSE(CPGTU, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_CPLE(v, co, r1, r2, ci);
	  RECURSE(CPLE, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_CPLEU(v, co, r1, r2, ci);
	  RECURSE(CPLEU, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_CPLT(v, co, r1, r2, ci);
	  RECURSE(CPLT, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_CPLTU(v, co, r1, r2, ci);
	  RECURSE(CPLTU, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_CPNEQ(v, co, r1, r2, ci);
	  RECURSE(CPNEQ, s1, s2, prune_hint & ~CY_JUST_SET);
#endif
#if ALPHA
	  PERFORM_CMPEQ(v, co, r1, r2, ci);
	  RECURSE(CMPEQ, s1, s2, prune_hint & ~CY_JUST_SET);

	  PERFORM_CMPLE(v, co, r1, r2, ci);
	  RECURSE(CMPLE, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_CMPLE(v, co, r2, r1, ci);
	  RECURSE(CMPLE, s2, s1, prune_hint & ~CY_JUST_SET);

	  PERFORM_CMPLEU(v, co, r1, r2, ci);
	  RECURSE(CMPLEU, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_CMPLEU(v, co, r2, r1, ci);
	  RECURSE(CMPLEU, s2, s1, prune_hint & ~CY_JUST_SET);

	  PERFORM_CMPLT(v, co, r1, r2, ci);
	  RECURSE(CMPLT, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_CMPLT(v, co, r2, r1, ci);
	  RECURSE(CMPLT, s2, s1, prune_hint & ~CY_JUST_SET);

	  PERFORM_CMPLTU(v, co, r1, r2, ci);
	  RECURSE(CMPLTU, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_CMPLTU(v, co, r2, r1, ci);
	  RECURSE(CMPLTU, s2, s1, prune_hint & ~CY_JUST_SET);
#endif
#if M88000
	  PERFORM_CMPPAR (v, co, r1, r2, ci);
	  RECURSE(CMPPAR, s1, s2, prune_hint & ~CY_JUST_SET);
	  PERFORM_CMPPAR (v, co, r2, r1, ci);
	  RECURSE(CMPPAR, s2, s1, prune_hint & ~CY_JUST_SET);
#endif
	}
    }

  /* Unary operations with carry-in.  */
  if (ci >= 0 && flag_use_carry)
    {
      for (s1 = n_values - 1; s1 >= 0; s1--)
	{
	  r1 = values[s1];

	  if (allowed_cost <= 1 && (prune_hint & CY_JUST_SET) == 0)
	    {
	      /* We are in a leaf node and CY was not set (to 1 or to a
		 data dependent value) by the previous insn.

		 The input operand has to be the result operand of the
		 previous insn for that insn to be meaningful.  */
	      if (last_dest >= 0 && s1 != last_dest)
		continue;
	    }

#if SPARC || RS6000 || M88000 || AM29K
	  /* d,cy = 2*r1 + cy
	     sparc:	addxcc	s1,s1,d
	     rs6000:	ae	d,s1,s1
	     m88000:	addu.cio d,s1,s1
	     am29k:		addc	d,s1,s1 */
	  PERFORM_ADD_CIO(v, co, r1, r1, ci);
	  RECURSE(ADD_CIO, s1, s1, CY_JUST_SET);
#endif
#if SPARC || M88000 
	  /* d = 2*r1 + cy
	     sparc:	addx	s1,s1,d
	     m88000:	addu.ci	d,s1,s1  */
	  PERFORM_ADD_CI(v, co, r1, r1, ci);
	  RECURSE(ADD_CI, s1, s1, prune_hint & ~CY_JUST_SET);
#endif
#if SPARC || RS6000 || M88000 || AM29K
	  /* d,cy = r1 + cy - 1
	     sparc:	addxcc	s1,-1,d
	     rs6000:	ame	d,s1
	     m88000:	subu.cio d,s1,r0
	     am29k:	subc	d,s1,0 */
	  PERFORM_ADD_CIO(v, co, r1, VALUE(-1), ci);
	  RECURSE(ADD_CIO, s1, CNST(-1), CY_JUST_SET);
#endif
#if SPARC || RS6000 || M88000 || AM29K
	  /* d,cy = r1 + cy
	     sparc:	addxcc	s1,0,d
	     rs6000:	aze	d,s1
	     m88000:	addu.cio d,s1,r0
	     am29k:	addc	d,s1,0 */
	  PERFORM_ADD_CIO(v, co, r1, VALUE(0), ci);
	  RECURSE(ADD_CIO, s1, CNST(0), CY_JUST_SET);
#endif
#if SPARC
	  /* d,cy = 0 - r1 - cy
	     sparc:	 subxcc	%g0,s1,d */
	  PERFORM_SUB_CIO(v, co, VALUE(0), r1, ci);
	  RECURSE(SUB_CIO, CNST(0), s1, CY_JUST_SET);
#endif
#if SPARC
	  /* d = r1 + 1 - cy
	     sparc:	 subx	s1,-1,d */
	  PERFORM_SUB_CI(v, co, r1, VALUE(-1), ci);
	  RECURSE(SUB_CI, s1, CNST(-1), prune_hint & ~CY_JUST_SET);
#endif
#if SPARC
	  /* d,cy = r1 + 1 - cy
	     sparc:	 subxcc	s1,-1,d */
	  PERFORM_SUB_CIO(v, co, r1, VALUE(-1), ci);
	  RECURSE(SUB_CIO, s1, CNST(-1), CY_JUST_SET);
#endif
#if RS6000
	  /* d,cy = -1 + ~r1 + cy
	     rs6000:	sfme	d,s1 */
	  PERFORM_ADC_CIO(v, co, VALUE(-1), r1, ci);
	  RECURSE(ADC_CIO, CNST(-1), s1, CY_JUST_SET);
#endif
#if RS6000 || M88000 || AM29K
	  /* d,cy = ~r1 + cy
	     m88000:	subu.cio d,r0,s1
	     rs6000:	sfze	d,s1
	     am29k:	subrc	d,s1,0 */
	  PERFORM_ADC_CIO(v, co, VALUE(0), r1, ci);
	  RECURSE(ADC_CIO, CNST(0), s1, CY_JUST_SET);
#endif
	}
    }

  /* Unary operations without carry-in.  */
  for (s1 = n_values - 1; s1 >= 0; s1--)
    {
      r1 = values[s1];

      if (allowed_cost <= 1)
	{
	  /* We are in a leaf node.

	     The input operand has to be the result operand of the
	     previous insns for that insn to be meaningful.  */
	  if (last_dest >= 0 && s1 != last_dest)
	    continue;
	}

#ifdef DM
      PERFORM_INVDIV(v, co, r1, ci);
      RECURSE(INVDIV, s1, 0, prune_hint & ~CY_JUST_SET);

      PERFORM_INVMOD(v, co, r1, ci);
      RECURSE(INVMOD, s1, 0, prune_hint & ~CY_JUST_SET);
#endif
#if SPARC || RS6000 || M88000 || AM29K
      /* d,cy = 2*r1
	 sparc:		addcc	s1,s1,d
	 rs6000:	a	d,s1,s1
	 m88000:	addu.co	d,s1,s1
	 am29k:		add	d,s1,s1 */
      PERFORM_ADD_CO(v, co, r1, r1, ci);
      RECURSE(ADD_CO, s1, s1, CY_JUST_SET);
#endif
#if SPARC || RS6000 || M88000 || AM29K || ALPHA
      /* d = r1 & 1
	 sparc:		and	s1,1,d
	 rs6000:	rlinm	d,s1,0,31,31
	 m88000:	mask	d,s1,1
	 am29k:		and	d,s1,1
	 alpha:		and	s1,1,d */
      PERFORM_AND(v, co, r1, VALUE(1), ci);
      RECURSE(AND, s1, CNST(1), prune_hint & ~CY_JUST_SET);
#endif
#if RS6000 || M88000
      /* d = r1 & 0x80000000
	 rs6000:	rlinm	d,s1,0,0,0
	 m88000:	mask.u	d,s1,0x8000 */
      PERFORM_AND(v, co, r1, VALUE_MIN_SIGNED, ci);
      RECURSE(AND, s1, CNST_0x80000000, prune_hint & ~CY_JUST_SET);

      /* d = r1 & 0x7fffffff
	 rs6000:	rlinm	d,s1,0,1,31
	 m88000:	and.u	d,s1,0x7fff */
      PERFORM_AND(v, co, r1, VALUE_MAX_SIGNED, ci);
      RECURSE(AND, s1, CNST_0x7FFFFFFF, prune_hint & ~CY_JUST_SET);
#endif
#if RS6000 || M88000
      PERFORM_XOR(v, co, r1, VALUE_MIN_SIGNED, ci);
      RECURSE(XOR, s1, CNST_0x80000000, prune_hint & ~CY_JUST_SET);

      PERFORM_IOR(v, co, r1, VALUE_MIN_SIGNED, ci);
      RECURSE(IOR, s1, CNST_0x80000000, prune_hint & ~CY_JUST_SET);
#endif
#if SPARC || RS6000 || M88000 || AM29K || ALPHA
      /* d = r1 ^ 1
	 sparc:		xor	s1,1,d
	 rs6000:	xoril	d,s1,1
	 m88000:	xor	d,s1,1
	 am29k:		xor	d,s1,1
	 alpha:		xor	s1,1,d */
      PERFORM_XOR(v, co, r1, VALUE(1), ci);
      RECURSE(XOR, s1, CNST(1), prune_hint & ~CY_JUST_SET);
#endif
#if SPARC || RS6000 || M88000 || AM29K || ALPHA
      /* d = ~r1
	 sparc:		xnor	%g0,s1,d
	 rs6000:	nand	d,s1,s1
	 m88000:	xor.c	d,s1,r0
	 am29k:		nand	d,s1,s1
	 alpha:		ornot	$31,s1,d */
      PERFORM_SUB(v, co, VALUE(-1), r1, ci);
      RECURSE(SUB, CNST(-1), s1, prune_hint & ~CY_JUST_SET);
#endif
#if RS6000
      /* d,cy = -1 + ~r1 (i.e. one's complement and set carry.)
	 rs6000:	sfi	d,s1,-1 */
      PERFORM_ADC_CO(v, co, VALUE(-1), r1, ci);
      RECURSE(ADC_CO, CNST(-1), s1, CY_JUST_SET | CY_1);
#endif
#if SPARC || RS6000 || AM29K
      /* d,cy = r1 + 1
	 sparc:		addcc	s1,1,d
	 rs6000:	ai	d,s1,1
	 am29k:		add	d,s1,1 */
      PERFORM_ADD_CO(v, co, r1, VALUE(1), ci);
      RECURSE(ADD_CO, s1, CNST(1), CY_JUST_SET);
#endif
#if SPARC || RS6000 || M88000 || ALPHA
      /* d = r1 + 1
	 sparc:		add	s1,1,d
	 rs6000:	cal	d,1(s1)
	 m88000:	addu	d,s1,1
	 alpha:		addq	s1,1,d */
      PERFORM_ADD(v, co, r1, VALUE(1), ci);
      RECURSE(ADD, s1, CNST(1), prune_hint & ~CY_JUST_SET);
#endif
#if 0 && RS6000 /* This has the same effect as a "xoriu". */
      /* d = r1 + 0x80000000
	 rs6000:	cau	d,s1,0x8000 */
      PERFORM_ADD(v, co, r1, VALUE_MIN_SIGNED, ci);
      RECURSE(ADD, s1, CNST_0x80000000, CY_JUST_SET);
#endif
#if SPARC || RS6000 || AM29K /* not M88000 */
      /* d,cy = r1 + -1
	 sparc:		addcc	s1,-1,d
	 rs6000:	ai	d,s1,-1
	 am29k:		sub	d,s1,1 */
      PERFORM_ADD_CO(v, co, r1, VALUE(-1), ci);
      RECURSE(ADD_CO, s1, CNST(-1), CY_JUST_SET);
#endif
#if SPARC
      /* d,cy = r1 - 1. [This isn't redundant, in spite we add -1 above.]
	 sparc:		subcc	s1,1,d */
      PERFORM_SUB_CO(v, co, r1, VALUE(1), ci);
      RECURSE(SUB_CO, s1, CNST(1), CY_JUST_SET);
#endif
#if SPARC
      /* d,cy = -r1
	 sparc:		subcc	%g0,s1,d */
      PERFORM_SUB_CO(v, co, VALUE(0), r1, ci);
      RECURSE(SUB_CO, CNST(0), s1, CY_JUST_SET);
#endif
#if SPARC || RS6000 || M88000 || ALPHA
      /* d = -r1
	 sparc:		sub	%g0,s1,d
	 rs6000:	neg	d,s1
	 m88000:	subu	d,r0,s1
	 alpha:		subq	$31,s1,d */
      PERFORM_SUB(v, co, VALUE(0), r1, ci);
      RECURSE(SUB, CNST(0), s1, prune_hint & ~CY_JUST_SET);
#endif
#if RS6000 || M88000 || AM29K
      /* d,cy = -r1
	 rs6000:	sf	d,s1,0
	 m88000:	subu.co	d,r0,s1
	 am29k:		subr	d,s1,0 */
      PERFORM_ADC_CO(v, co, VALUE(0), r1, ci);
      RECURSE(ADC_CO, CNST(0), s1, CY_JUST_SET);
#endif
#if RS6000
      /* d = abs(r1)
	 rs6000:	abs	d,s1 */
      PERFORM_ABSVAL(v, co, r1, ci);
      RECURSE(ABSVAL, s1, 0, prune_hint & ~CY_JUST_SET);

      /* d = -abs(r1)
	 rs6000:	nabs	d,s1 */
      PERFORM_NABSVAL(v, co, r1, ci);
      RECURSE(NABSVAL, s1, 0, prune_hint & ~CY_JUST_SET);
#endif
#if RS6000 && !defined (AVOID_DOZ)
      PERFORM_DOZ(v, co, VALUE(0), r1, ci);
      RECURSE(DOZ, CNST(0), s1, prune_hint & ~CY_JUST_SET);
      PERFORM_DOZ(v, co, VALUE(-1), r1, ci);
      RECURSE(DOZ, CNST(-1), s1, prune_hint & ~CY_JUST_SET);
#endif
#if SHIFTS
      {
	int cnt;
	for (cnt = 1; cnt < BITS_PER_WORD; cnt++)
	  {
#if SPARC || RS6000 || M88000 || AM29K || ALPHA
	    PERFORM_LSHIFTR(v, co, r1, VALUE(cnt), ci);
	    RECURSE(LSHIFTR, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
#endif
#if SPARC || M88000 || AM29K || ALPHA
	    PERFORM_ASHIFTR(v, co, r1, VALUE(cnt), ci);
	    RECURSE(ASHIFTR, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
#endif
#if RS6000
	    PERFORM_ASHIFTR_CON(v, co, r1, VALUE(cnt), ci);
	    RECURSE(ASHIFTR_CON, s1, CNST(cnt), CY_JUST_SET);
#endif
#if SPARC || RS6000 || M88000 || AM29K || ALPHA
	    PERFORM_SHIFTL(v, co, r1, VALUE(cnt), ci);
	    RECURSE(SHIFTL, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
#endif
#if RS6000 || M88000
	    PERFORM_ROTATEL(v, co, r1, VALUE(cnt), ci);
	    RECURSE(ROTATEL, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
#endif
	  }
      }
#else
#if SPARC || RS6000 || M88000 || AM29K || ALPHA
      PERFORM_LSHIFTR(v, co, r1, VALUE(1), ci);
      RECURSE(LSHIFTR, s1, CNST(1), prune_hint & ~CY_JUST_SET);
#endif
#if SPARC || M88000 || AM29K || ALPHA
      PERFORM_ASHIFTR(v, co, r1, VALUE(1), ci);
      RECURSE(ASHIFTR, s1, CNST(1), prune_hint & ~CY_JUST_SET);
#endif
#if RS6000
      PERFORM_ASHIFTR_CON(v, co, r1, VALUE(1), ci);
      RECURSE(ASHIFTR_CON, s1, CNST(1), CY_JUST_SET);
#endif
#if SPARC || RS6000 || M88000 || AM29K || ALPHA
      PERFORM_SHIFTL(v, co, r1, VALUE(1), ci);
      RECURSE(SHIFTL, s1, CNST(1), prune_hint & ~CY_JUST_SET);
#endif
#if RS6000 || M88000
      PERFORM_ROTATEL(v, co, r1, VALUE(1), ci);
      RECURSE(ROTATEL, s1, CNST(1), prune_hint & ~CY_JUST_SET);
#endif
#if SPARC || RS6000 || M88000 || AM29K || ALPHA
      PERFORM_LSHIFTR(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
      RECURSE(LSHIFTR, s1, CNST(BITS_PER_WORD-1), prune_hint & ~CY_JUST_SET);
#endif
#if SPARC || M88000 || AM29K || ALPHA
      PERFORM_ASHIFTR(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
      RECURSE(ASHIFTR, s1, CNST(BITS_PER_WORD-1), prune_hint & ~CY_JUST_SET);
#endif
#if RS6000
      PERFORM_ASHIFTR_CON(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
      RECURSE(ASHIFTR_CON, s1, CNST(BITS_PER_WORD-1), CY_JUST_SET);
#endif
#if SHIFT16
#if SPARC || RS6000 || M88000 || AM29K || ALPHA
      PERFORM_LSHIFTR(v, co, r1, VALUE(16), ci);
      RECURSE(LSHIFTR, s1, CNST(16), prune_hint & ~CY_JUST_SET);
#endif
#if SPARC || M88000 || AM29K || ALPHA
      PERFORM_ASHIFTR(v, co, r1, VALUE(16), ci);
      RECURSE(ASHIFTR, s1, CNST(16), prune_hint & ~CY_JUST_SET);
#endif
#if RS6000
      PERFORM_ASHIFTR_CON(v, co, r1, VALUE(16), ci);
      RECURSE(ASHIFTR_CON, s1, CNST(16), CY_JUST_SET);
#endif
#if SPARC || RS6000 || M88000 || AM29K || ALPHA
      PERFORM_SHIFTL(v, co, r1, VALUE(16), ci);
      RECURSE(SHIFTL, s1, CNST(16), prune_hint & ~CY_JUST_SET);
#endif
#if RS6000 || M88000
      PERFORM_ROTATEL(v, co, r1, VALUE(16), ci);
      RECURSE(ROTATEL, s1, CNST(16), prune_hint & ~CY_JUST_SET);
#endif
#endif /* SHIFT16 */
#endif /* SHIFTS */
#if EXTRACTS
      {
	int cnt;
	for (cnt = 1; cnt < BITS_PER_WORD; cnt++)
	  {
#if M88000
	    PERFORM_EXTS1(v, co, r1, VALUE(cnt), ci);
	    RECURSE(EXTS1, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
	    PERFORM_EXTU1(v, co, r1, VALUE(cnt), ci);
	    RECURSE(EXTU1, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
	    PERFORM_EXTS2(v, co, r1, VALUE(cnt), ci);
	    RECURSE(EXTS2, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
	    PERFORM_EXTU2(v, co, r1, VALUE(cnt), ci);
	    RECURSE(EXTU2, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
#endif
	  }
      }
#endif
#if AM29K
      PERFORM_CPEQ(v, co, r1, VALUE(0), ci);
      RECURSE(CPEQ, s1, CNST(0), prune_hint & ~CY_JUST_SET);
      PERFORM_CPGE(v, co, r1, VALUE(0), ci);
      RECURSE(CPGE, s1, CNST(0), prune_hint & ~CY_JUST_SET);
      PERFORM_CPGEU(v, co, r1, VALUE(0), ci);
      RECURSE(CPGEU, s1, CNST(0), prune_hint & ~CY_JUST_SET);
      PERFORM_CPGT(v, co, r1, VALUE(0), ci);
      RECURSE(CPGT, s1, CNST(0), prune_hint & ~CY_JUST_SET);
      PERFORM_CPGTU(v, co, r1, VALUE(0), ci);
      RECURSE(CPGTU, s1, CNST(0), prune_hint & ~CY_JUST_SET);
      PERFORM_CPLE(v, co, r1, VALUE(0), ci);
      RECURSE(CPLE, s1, CNST(0), prune_hint & ~CY_JUST_SET);
      PERFORM_CPLEU(v, co, r1, VALUE(0), ci);
      RECURSE(CPLEU, s1, CNST(0), prune_hint & ~CY_JUST_SET);
      PERFORM_CPLT(v, co, r1, VALUE(0), ci);
      RECURSE(CPLT, s1, CNST(0), prune_hint & ~CY_JUST_SET);
      PERFORM_CPLTU(v, co, r1, VALUE(0), ci);
      RECURSE(CPLTU, s1, CNST(0), prune_hint & ~CY_JUST_SET);
      PERFORM_CPNEQ(v, co, r1, VALUE(0), ci);
      RECURSE(CPNEQ, s1, CNST(0), prune_hint & ~CY_JUST_SET);
#endif
#if ALPHA
      PERFORM_CMPEQ(v, co, r1, VALUE(0), ci);
      RECURSE(CMPEQ, s1, CNST(0), prune_hint & ~CY_JUST_SET);

      PERFORM_CMPLE(v, co, r1, VALUE(0), ci);
      RECURSE(CMPLE, s1, CNST(0), prune_hint & ~CY_JUST_SET);
      PERFORM_CMPLE(v, co, VALUE(0), r1, ci);
      RECURSE(CMPLE, CNST(0), s1, prune_hint & ~CY_JUST_SET);

      PERFORM_CMPLEU(v, co, r1, VALUE(0), ci);
      RECURSE(CMPLEU, s1, CNST(0), prune_hint & ~CY_JUST_SET);
      PERFORM_CMPLEU(v, co, VALUE(0), r1, ci);
      RECURSE(CMPLEU, CNST(0), s1, prune_hint & ~CY_JUST_SET);

      PERFORM_CMPLT(v, co, r1, VALUE(0), ci);
      RECURSE(CMPLT, s1, CNST(0), prune_hint & ~CY_JUST_SET);
      PERFORM_CMPLT(v, co, VALUE(0), r1, ci);
      RECURSE(CMPLT, CNST(0), s1, prune_hint & ~CY_JUST_SET);

      PERFORM_CMPLTU(v, co, r1, VALUE(0), ci);
      RECURSE(CMPLTU, s1, CNST(0), prune_hint & ~CY_JUST_SET);
      PERFORM_CMPLTU(v, co, VALUE(0), r1, ci);
      RECURSE(CMPLTU, CNST(0), s1, prune_hint & ~CY_JUST_SET);
#endif
#if RS6000 || AM29K
      PERFORM_CLZ(v, co, r1, ci);
      RECURSE(CLZ, s1, 0, prune_hint & ~CY_JUST_SET);
#endif
#if M88000
      PERFORM_FF1(v, co, r1, ci);
      RECURSE(FF1, s1, 0, prune_hint & ~CY_JUST_SET);
#endif
#if M88000
      PERFORM_CMPPAR (v, co, r1, VALUE(0), ci);
      RECURSE(CMPPAR, s1, CNST(0), prune_hint & ~CY_JUST_SET);
      PERFORM_CMPPAR (v, co, VALUE(0), r1, ci);
      RECURSE(CMPPAR, CNST(0), s1, prune_hint & ~CY_JUST_SET);
#endif
    }

#if ALPHA
  /* Alpha Conditional move instructions need special treatment.  We let all
     other instructions assign the next higher-numbered register, but we
     can't do that here since cmov insns leave the register undefined if the
     instruction condition is not satisfied.  Instead we let the cmov
     instructions non-deterministically overwrite all already-defined
     registers.  */
  for (s1 = n_values - 1; s1 >= 0; s1--)
    {
      r1 = values[s1];
      for (s2 = s1 - 1; s2 >= 0; s2--)
	{
	  int dr;
	  r2 = values[s2];

	  if (allowed_cost <= 1)
	    {
	      /* We are in a leaf node.  */

	      /* One of the input operands has to be the result operand
		 of the previous insn for that insn to be meaningful.  */
	      if (last_dest >= 0 && s1 != last_dest && s2 != last_dest)
		continue;
	    }

	  for (dr = n_values - 1; dr >= 0; dr--)
	    {
	      v = values[dr];

	      PERFORM_CMOVEQ (v, co, r1, r2, ci);
	      CRECURSE_2OP(CMOVEQ, dr, s1, s2, 1, prune_hint & ~CY_JUST_SET);
	      PERFORM_CMOVEQ (v, co, r2, r1, ci);
	      CRECURSE_2OP(CMOVEQ, dr, s2, s1, 1, prune_hint & ~CY_JUST_SET);

	      PERFORM_CMOVNE (v, co, r1, r2, ci);
	      CRECURSE_2OP(CMOVNE, dr, s1, s2, 1, prune_hint & ~CY_JUST_SET);
	      PERFORM_CMOVNE (v, co, r2, r1, ci);
	      CRECURSE_2OP(CMOVNE, dr, s2, s1, 1, prune_hint & ~CY_JUST_SET);

	      PERFORM_CMOVLT (v, co, r1, r2, ci);
	      CRECURSE_2OP(CMOVLT, dr, s1, s2, 1, prune_hint & ~CY_JUST_SET);
	      PERFORM_CMOVLT (v, co, r2, r1, ci);
	      CRECURSE_2OP(CMOVLT, dr, s2, s1, 1, prune_hint & ~CY_JUST_SET);

	      PERFORM_CMOVGE (v, co, r1, r2, ci);
	      CRECURSE_2OP(CMOVGE, dr, s1, s2, 1, prune_hint & ~CY_JUST_SET);
	      PERFORM_CMOVGE (v, co, r2, r1, ci);
	      CRECURSE_2OP(CMOVGE, dr, s2, s1, 1, prune_hint & ~CY_JUST_SET);

	      PERFORM_CMOVLE (v, co, r1, r2, ci);
	      CRECURSE_2OP(CMOVLE, dr, s1, s2, 1, prune_hint & ~CY_JUST_SET);
	      PERFORM_CMOVLE (v, co, r2, r1, ci);
	      CRECURSE_2OP(CMOVLE, dr, s2, s1, 1, prune_hint & ~CY_JUST_SET);

	      PERFORM_CMOVGT (v, co, r1, r2, ci);
	      CRECURSE_2OP(CMOVGT, dr, s1, s2, 1, prune_hint & ~CY_JUST_SET);
	      PERFORM_CMOVGT (v, co, r2, r1, ci);
	      CRECURSE_2OP(CMOVGT, dr, s2, s1, 1, prune_hint & ~CY_JUST_SET);
	    }
	}
    }

  for (s1 = n_values - 1; s1 >= 0; s1--)
    {
      int dr;
      r1 = values[s1];

      if (allowed_cost <= 1)
	{
	  /* We are in a leaf node.

	     The input operand has to be the result operand of the
	     previous insns for that insn to be meaningful.  */
	  if (last_dest >= 0 && s1 != last_dest)
	    continue;
	}

      for (dr = n_values - 1; dr >= 0; dr--)
	{
	  v = values[dr];

	  PERFORM_CMOVEQ (v, co, r1, VALUE(0), ci);
	  CRECURSE_2OP(CMOVEQ, dr, s1, CNST(0), 1, prune_hint & ~CY_JUST_SET);
	  PERFORM_CMOVEQ (v, co, VALUE(0), r1, ci);
	  CRECURSE_2OP(CMOVEQ, dr, CNST(0), s1, 1, prune_hint & ~CY_JUST_SET);

	  PERFORM_CMOVNE (v, co, r1, VALUE(0), ci);
	  CRECURSE_2OP(CMOVNE, dr, s1, CNST(0), 1, prune_hint & ~CY_JUST_SET);
	  PERFORM_CMOVNE (v, co, VALUE(0), r1, ci);
	  CRECURSE_2OP(CMOVNE, dr, CNST(0), s1, 1, prune_hint & ~CY_JUST_SET);

	  PERFORM_CMOVLT (v, co, r1, VALUE(0), ci);
	  CRECURSE_2OP(CMOVLT, dr, s1, CNST(0), 1, prune_hint & ~CY_JUST_SET);
	  PERFORM_CMOVLT (v, co, VALUE(0), r1, ci);
	  CRECURSE_2OP(CMOVLT, dr, CNST(0), s1, 1, prune_hint & ~CY_JUST_SET);

	  PERFORM_CMOVGE (v, co, r1, VALUE(0), ci);
	  CRECURSE_2OP(CMOVGE, dr, s1, CNST(0), 1, prune_hint & ~CY_JUST_SET);
	  PERFORM_CMOVGE (v, co, VALUE(0), r1, ci);
	  CRECURSE_2OP(CMOVGE, dr, CNST(0), s1, 1, prune_hint & ~CY_JUST_SET);

	  PERFORM_CMOVLE (v, co, r1, VALUE(0), ci);
	  CRECURSE_2OP(CMOVLE, dr, s1, CNST(0), 1, prune_hint & ~CY_JUST_SET);
	  PERFORM_CMOVLE (v, co, VALUE(0), r1, ci);
	  CRECURSE_2OP(CMOVLE, dr, CNST(0), s1, 1, prune_hint & ~CY_JUST_SET);

	  PERFORM_CMOVGT (v, co, r1, VALUE(0), ci);
	  CRECURSE_2OP(CMOVGT, dr, s1, CNST(0), 1, prune_hint & ~CY_JUST_SET);
	  PERFORM_CMOVGT (v, co, VALUE(0), r1, ci);
	  CRECURSE_2OP(CMOVGT, dr, CNST(0), s1, 1, prune_hint & ~CY_JUST_SET);
	}
    }
#endif /* ALPHA */

  /* 0-ary instructions, just dependent on carry.  */
  if (ci >= 0 && flag_use_carry
      && (allowed_cost <= 1 ? ((prune_hint & CY_JUST_SET) != 0) : 1))
    {
      /* We don't do "0 - 1 - cy" or "0 + 1 + cy" here.  It would
	 probably give very few new sequences. */
#if SPARC || M88000
      /* d = cy.
	 sparc:		addx	%g0,0,d
	 m88000:	addu.ci d,r0,r0 */
      PERFORM_ADD_CI(v, co, VALUE(0), VALUE(0), ci);
      RECURSE(ADD_CI, CNST(0), CNST(0), prune_hint & ~CY_JUST_SET);
#endif
#if SPARC || M88000
      /* d = cy, cy = 0.
	 sparc:		addxcc	%g0,0,d
	 m88000:	addu.cio d,r0,r0 */
      PERFORM_ADD_CIO(v, co, VALUE(0), VALUE(0), ci);
      RECURSE(ADD_CIO, CNST(0), CNST(0), CY_JUST_SET | CY_0);
#endif
#if SPARC
      /* Using SUB_CIO instead would make no difference.
	 It'd just set carry to it's old value.  */
      /* d = -cy.
	 sparc:		subx	%g0,0,d */
      PERFORM_SUB_CI(v, co, VALUE(0), VALUE(0), ci);
      RECURSE(SUB_CI, CNST(0), CNST(0), prune_hint & ~CY_JUST_SET);
#endif
#if SPARC
      /* d = 1 - cy.
	 sparc:		subx	%g0,-1,d */
      PERFORM_SUB_CI(v, co, VALUE(0), VALUE(-1), ci);
      RECURSE(SUB_CI, CNST(0), CNST(-1), CY_JUST_SET | CY_1);
#endif
#if SPARC
      /* d = 1 - cy, cy = 1.
	 sparc:		subxcc	%g0,-1,d */
      PERFORM_SUB_CIO(v, co, VALUE(0), VALUE(-1), ci);
      RECURSE(SUB_CIO, CNST(0), CNST(-1), CY_JUST_SET | CY_1);
#endif
#if SPARC
      /* Using ADD_CIO instead would make no difference.
	 It'd just set carry to it's old value.  */
      /* d = -1 + cy.
	 sparc:		addx	%g0,-1,d */
      PERFORM_ADD_CI(v, co, VALUE(0), VALUE(-1), ci);
      RECURSE(ADD_CI, CNST(0), CNST(-1), prune_hint & ~CY_JUST_SET);
#endif
#if RS6000 || AM29K /* Use subu.ci on 88k instead with same result */
      /* d = -1 + cy, cy = cy
	 rs6000:	sfe	d,d,d
	 am29k:		subc	d,d,d */
      PERFORM_ADC_CIO(v, co, VALUE(0), VALUE(0), ci);
      RECURSE(ADC_CIO, n_values, n_values, prune_hint & ~CY_JUST_SET);
#endif
#if M88000
      /* d = -1 + cy
	 m88000:	subu.ci	d,r0,r0 */
      PERFORM_ADC_CI(v, co, VALUE(0), VALUE(0), ci);
      RECURSE(ADC_CI, CNST(0), CNST(0), prune_hint & ~CY_JUST_SET);
#endif
    }

  /* Move instructions.
     Don't do this if we are just permitted to do one more instruction.  */
  if (allowed_cost > 1)
    {
#if SPARC || RS6000 || M88000 || AM29K
      /* d = 0x80000000
	 sparc:		sethi	%hi(0x80000000),d
	 rs6000:	liu	d,0x8000
	 m88000:	or.u	d,r0,0x8000
	 am29k:		cpeq	d,gr1,gr1 */
      PERFORM_COPY(v, co, VALUE_MIN_SIGNED, ci);
      RECURSE(COPY, CNST_0x80000000, 0, prune_hint & ~CY_JUST_SET);
      /* d = -1
	 sparc:		mov	-1,d
	 rs6000:	lil	d,-1
	 m88000:	subu	d,r0,1
	 am29k:		constn	d,1 */
      PERFORM_COPY(v, co, VALUE(-1), ci);
      RECURSE(COPY, CNST(-1), 0, prune_hint & ~CY_JUST_SET);
      /* d = 1
	 sparc:		mov	1,d
	 rs6000:	lil	d,1
	 m88000:	addu	d,r0,1
	 am29k:		const	d,1 */
      PERFORM_COPY(v, co, VALUE(1), ci);
      RECURSE(COPY, CNST(1), 0, prune_hint & ~CY_JUST_SET);
#endif
#if RS6000 || AM29K	/* sparc and 88k should not need this. */
      /* d = 0
	 sparc:		mov	0,d
	 rs6000:	lil	d,0
	 m88000:	or	d,r0,0
	 am29k:		const	d,0 */
      PERFORM_COPY(v, co, VALUE(0), ci);
      RECURSE(COPY, CNST(0), 0, prune_hint & ~CY_JUST_SET);
#endif
#if M88000
      /* d = 0x7fffffff
	 m88000:	set	d,r0,31<0> */
      PERFORM_COPY(v, co, VALUE_MAX_SIGNED, ci);
      RECURSE(COPY, CNST_0x7FFFFFFF, 0, prune_hint & ~CY_JUST_SET);
#endif
    }

#ifdef TIMING
  timings[allowed_cost] += cputime() - time_start;
#endif
}
#endif

/* This function is commented above, before the previous function.  */

#if M68000 || I386 || PYR
void
synth(insn_t *sequence,
      int n_insns,
      word *values,
      int n_values,
      word goal_value,
      int allowed_cost,
      int ci,
      int prune_hint)
{
  int s1, s2;
  word v, r1, r2;
  int co;
  int last_dest;

  if (n_insns > 0)
    last_dest = sequence[n_insns - 1].d;
  else
    last_dest = -1;

  /* Binary operations with carry-in.  */
  if (ci >= 0 && (prune_hint & CY_0) == 0 && flag_use_carry)
    {
      for (s1 = n_values - 1; s1 >= 0; s1--)
	{
	  r1 = values[s1];
	  for (s2 = n_values - 1; s2 >= 0; s2--)
	    {
	      r2 = values[s2];

	      if (allowed_cost <= 1 && (prune_hint & CY_JUST_SET) == 0)
		{
		  /* We are in a leaf node.  CY was not set (to 1 or to a
		     data dependent value) by the previous insn.

		     So one of the input operands has to be the result
		     operand of the previous insn for that insn to be
		     meaningful.  */
		  if (last_dest >= 0 && s1 != last_dest && s2 != last_dest)
		    continue;
		}

#if M68000 || I386 || PYR
	      /* m68000:	addx
		 i80386:	adc
		 pyramid:	addwc */
	      PERFORM_ADD_CIO(v, co, r1, r2, ci);
	      CRECURSE_2OP(ADD_CIO, s1, s1, s2, 1, CY_JUST_SET);
#endif
#if M68000 || I386
	      if (s1 != s2)
		{
		  /* m68000:	subx
		     i80386:	sbb */
		  PERFORM_SUB_CIO(v, co, r1, r2, ci);
		  CRECURSE_2OP(SUB_CIO, s1, s1, s2, 1, CY_JUST_SET);
		}
#endif
#if PYR
	      if (s1 != s2)
		{
		  /* pyramid:	subwb */
		  PERFORM_ADC_CIO(v, co, r1, r2, ci);
		  CRECURSE_2OP(ADC_CIO, s1, s1, s2, 1, CY_JUST_SET);
		}
#endif
	    }
	}
    }

  /* Binary operations without carry-in.  */
  for (s1 = n_values - 1; s1 >= 0; s1--)
    {
      r1 = values[s1];
      for (s2 = n_values - 1; s2 >= 0; s2--)
	{
	  r2 = values[s2];

	  if (allowed_cost <= 1)
	    {
	      /* We are in a leaf node.

		 So one of the input operands has to be the result operand
		 of the previous insn for that insn to be meaningful.  */
	      if (last_dest >= 0 && s1 != last_dest && s2 != last_dest)
		continue;
	    }

#if M68000 || I386 || PYR
	  /* m68000:	add
	     i80386:	add
	     pyramid:	addw */
	  PERFORM_ADD_CO(v, co, r1, r2, ci);
	  CRECURSE_2OP(ADD_CO, s1, s1, s2, 1, CY_JUST_SET);
#endif
	  if (s1 != s2)
	    {
#if M68000 || I386
	      /* m68000:	sub
		 i80386:	sub */
	      PERFORM_SUB_CO(v, co, r1, r2, ci);
	      CRECURSE_2OP(SUB_CO, s1, s1, s2, 1, CY_JUST_SET);
#endif
#if PYR
	      /* pyramid:	subw */
	      PERFORM_ADC_CO(v, co, r1, r2, ci);
	      CRECURSE_2OP(ADC_CO, s1, s1, s2, 1, CY_JUST_SET);
#endif
#if M68000
	      PERFORM_AND(v, co, r1, r2, ci);
	      CRECURSE_2OP(AND, s1, s1, s2, 1, prune_hint & ~CY_JUST_SET);

	      PERFORM_IOR(v, co, r1, r2, ci);
	      CRECURSE_2OP(IOR, s1, s1, s2, 1, prune_hint & ~CY_JUST_SET);

	      PERFORM_XOR(v, co, r1, r2, ci);
	      CRECURSE_2OP(XOR, s1, s1, s2, 1, prune_hint & ~CY_JUST_SET);
#endif
#if I386
	      PERFORM_AND_RC(v, co, r1, r2, ci);
	      CRECURSE_2OP(AND_RC, s1, s1, s2, 1, CY_JUST_SET | CY_0);

	      PERFORM_IOR_RC(v, co, r1, r2, ci);
	      CRECURSE_2OP(IOR_RC, s1, s1, s2, 1, CY_JUST_SET | CY_0);

	      PERFORM_XOR_RC(v, co, r1, r2, ci);
	      CRECURSE_2OP(XOR_RC, s1, s1, s2, 1, CY_JUST_SET | CY_0);
#endif
#if PYR
	      PERFORM_AND_CC(v, co, r1, r2, ci);
	      CRECURSE_2OP(AND_CC, s1, s1, s2, 1, 0);

	      PERFORM_ANDC_CC(v, co, r1, r2, ci);
	      CRECURSE_2OP(ANDC_CC, s1, s1, s2, 1, 0);

	      PERFORM_IOR_CC(v, co, r1, r2, ci);
	      CRECURSE_2OP(IOR_CC, s1, s1, s2, 1, 0);

	      PERFORM_XOR_CC(v, co, r1, r2, ci);
	      CRECURSE_2OP(XOR_CC, s1, s1, s2, 1, 0);
#endif
#if I386
	      PERFORM_CMP(v, co, r1, r2, ci);
	      /* kludge: lie that the result is written to
		 register <n_values>. */
	      CRECURSE_2OP(CMP, n_values, s1, s2, 1, CY_JUST_SET);
#endif
	    }
#if M68000 || I386 || PYR
	  /* Exchange registers.  An ugly kludge.  */
	  if (s1 < s2)
	    {
	      values[s2] = r1;
	      /* Assign r2 to v to make `recurse' and rely on `recurse'
		 to handle the writing of it to the values array.  */
	      v = r2;
	      CRECURSE_2OP(EXCHANGE, s1, s1, s2, 1,
			   prune_hint & ~CY_JUST_SET);
	      values[s2] = r2;
	    }
#endif
	}
    }

  /* Unary operations with carry-in.  */
  if (ci >= 0 && (prune_hint & CY_0) == 0 && flag_use_carry)
    {
      for (s1 = n_values - 1; s1 >= 0; s1--)
	{
	  r1 = values[s1];

	  if (allowed_cost <= 1 && (prune_hint & CY_JUST_SET) == 0)
	    {
	      /* We are in a leaf node.  CY was not set (to 1 or to a
		 data dependent value) by the previous insn.

		 The input operand has to be the result operand of the
		 previous insn for that insn to be meaningful.  */
	      if (last_dest >= 0 && s1 != last_dest)
		continue;
	    }

#if I386 || PYR
	  /* d,cy = r1 + 1 + cy
	     i80386:	adc	1,d
	     pyramid:	addwc	$1,d */
	  PERFORM_ADD_CIO(v, co, r1, VALUE(1), ci);
	  CRECURSE_2OP(ADD_CIO, s1, s1, CNST(1), 1, CY_JUST_SET);
#endif
#if I386
	  /* d,cy = r1 - 1 - cy
	     i80386:	sbb	1,d */
	  PERFORM_SUB_CIO(v, co, r1, VALUE(1), ci);
	  CRECURSE_2OP(SUB_CIO, s1, s1, CNST(1), 1, CY_JUST_SET);
#endif
#if PYR
	  /* d,cy = r1 + (-2) + cy
	     pyramid:	subwb	$1,d */
	  PERFORM_ADC_CIO(v, co, r1, VALUE(1), ci);
	  CRECURSE_2OP(ADC_CIO, s1, s1, CNST(1), 1, CY_JUST_SET);
#endif
#if I386 || PYR
	  /* d,cy = r1 + (-1) + cy
	     i80386:	adc	-1,d
	     pyramid:	addwc	$-1,d */
	  PERFORM_ADD_CIO(v, co, r1, VALUE(-1), ci);
	  CRECURSE_2OP(ADD_CIO, s1, s1, CNST(-1), 1, CY_JUST_SET);
#endif
#if I386
	  /* d,cy = r1 - -1 - cy
	     i80386:	sbb	-1,d */
	  PERFORM_SUB_CIO(v, co, r1, VALUE(-1), ci);
	  CRECURSE_2OP(SUB_CIO, s1, s1, CNST(-1), 1, CY_JUST_SET);
#endif
#if PYR
	  /* d,cy = r1 + cy          [or if you prefer, r1 + 0 + cy]
	     pyramid:	subwb	$-1,d */
	  PERFORM_ADC_CIO(v, co, r1, VALUE(-1), ci);
	  CRECURSE_2OP(ADC_CIO, s1, s1, CNST(-1), 1, CY_JUST_SET);
#endif
#if I386 || PYR
	  /* d,cy = r1 + cy
	     i80386:	adc	0,d
	     pyramid:	addwc	$0,d */
	  PERFORM_ADD_CIO(v, co, r1, VALUE(0), ci);
	  CRECURSE_2OP(ADD_CIO, s1, s1, CNST(0), 1, CY_JUST_SET);
#endif
#if I386
	  /* d,cy = r1 - cy
	     i80386:	sbb	0,d */
	  PERFORM_SUB_CIO(v, co, r1, VALUE(0), ci);
	  CRECURSE_2OP(SUB_CIO, s1, s1, CNST(0), 1, CY_JUST_SET);
#endif
#if PYR
	  /* d,cy = r1 + (-1) + cy
	     pyramid:	subwb	$0,d */
	  PERFORM_ADC_CIO(v, co, r1, VALUE(0), ci);
	  CRECURSE_2OP(ADC_CIO, s1, s1, CNST(0), 1, CY_JUST_SET);
#endif
#if M68000
	  /* d,cy = 0 - r1 - cy
	     m68000:	 negx	d */
	  PERFORM_SUB_CIO(v, co, VALUE(0), r1, ci);
	  CRECURSE_2OP(SUB_CIO, s1, CNST(0), s1, 1, CY_JUST_SET);
#endif
#if M68000
	  /* d,cy = circular rotate left thru carry
	     m68000:	roxll	#1,d */
      PERFORM_ROTATEXL_CIO(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(ROTATEXL_CIO, s1, s1, CNST(1), SHIFT_COST(1), CY_JUST_SET);
#endif
#if I386
      PERFORM_ROTATEXL_CIO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
      CRECURSE_2OP(ROTATEXL_CIO, s1, s1, CNST(BITS_PER_WORD-1), 2, CY_JUST_SET);

      PERFORM_ROTATEXL_CIO(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(ROTATEXL_CIO, s1, s1, CNST(1), 2, CY_JUST_SET);
#endif
	}
    }

  /* Unary operations without carry-in.  */
  for (s1 = n_values - 1; s1 >= 0; s1--)
    {
      r1 = values[s1];

      if (allowed_cost <= 1)
	{
	  /* We are in a leaf node.

	     The input operand has to be the result operand of the
	     previous insns for that insn to be meaningful.  */
	  if (last_dest >= 0 && s1 != last_dest)
	    continue;
	}
      else
	{
	  /* Certain instructions should not terminate a sequence.  So we
	     only generate them in non-leaf nodes.  */
#if M68000 || I386 || PYR
	  /* d = r1
	     m68000:	move	s1,d
	     i80386:	move	s1,d
	     pyramid:	movw	s1,d */
	  PERFORM_COPY(v, co, r1, ci);
	  CRECURSE_NEW(COPY, n_values, s1, CNST(0), 1,
		       prune_hint & ~CY_JUST_SET);
#endif
#if I386
	  /* cmp kludge: lie that the result is written to register
	     <n_values>. */

	  /* i80386:	cmp	-1,s1 */
	  PERFORM_CMP(v, co, r1, VALUE(-1), ci);
	  CRECURSE_2OP(CMP, n_values, s1, CNST(-1), 1, CY_JUST_SET);

	  /* i80386:	cmp	1,s1 */
	  PERFORM_CMP(v, co, r1, VALUE(1), ci);
	  CRECURSE_2OP(CMP, n_values, s1, CNST(1), 1, CY_JUST_SET);

	  /* i80386:	cmp	0x7fffffff,s1 */
	  PERFORM_CMP(v, co, r1, VALUE_MAX_SIGNED, ci);
	  CRECURSE_2OP(CMP, n_values, s1, CNST_0x7FFFFFFF, 2, CY_JUST_SET);

	  /* i80386:	cmp	0x80000000,s1 */
	  PERFORM_CMP(v, co, r1, VALUE_MIN_SIGNED, ci);
	  CRECURSE_2OP(CMP, n_values, s1, CNST_0x80000000, 2, CY_JUST_SET);
#endif
	}

#if M68000 || PYR
      PERFORM_LSHIFTR_CO(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(LSHIFTR_CO, s1, s1, CNST(1), SHIFT_COST(1), CY_JUST_SET);

      PERFORM_ASHIFTR_CO(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(ASHIFTR_CO, s1, s1, CNST(1), SHIFT_COST(1), CY_JUST_SET);

      PERFORM_SHIFTL_CO(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(SHIFTL_CO, s1, s1, CNST(1), SHIFT_COST(1), CY_JUST_SET);

      /* Pyramids's rotlw and rotrw clobber cy */
#endif
#if M68000
      PERFORM_ROTATEL_CO(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(ROTATEL_CO, s1, s1, CNST(1), SHIFT_COST(1), CY_JUST_SET);
#endif
#if PYR
      PERFORM_LSHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
      CRECURSE_2OP(LSHIFTR_CO, s1, s1, CNST(BITS_PER_WORD-1), 1, CY_JUST_SET);

      PERFORM_ASHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
      CRECURSE_2OP(ASHIFTR_CO, s1, s1, CNST(BITS_PER_WORD-1), 1, CY_JUST_SET);

      PERFORM_SHIFTL_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
      CRECURSE_2OP(SHIFTL_CO, s1, s1, CNST(BITS_PER_WORD-1), 1, CY_JUST_SET);

      /* Pyramids's rotlw and rotrw clobber cy */
#endif
#if I386
      PERFORM_LSHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
      CRECURSE_2OP(LSHIFTR_CO, s1, s1, CNST(BITS_PER_WORD-1), 2, CY_JUST_SET);

      PERFORM_ASHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
      CRECURSE_2OP(ASHIFTR_CO, s1, s1, CNST(BITS_PER_WORD-1), 2, CY_JUST_SET);

      PERFORM_SHIFTL_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
      CRECURSE_2OP(SHIFTL_CO, s1, s1, CNST(BITS_PER_WORD-1), 2, CY_JUST_SET);

      PERFORM_ROTATEL_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
      CRECURSE_2OP(ROTATEL_CO, s1, s1, CNST(BITS_PER_WORD-1), 2, CY_JUST_SET);

      PERFORM_LSHIFTR_CO(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(LSHIFTR_CO, s1, s1, CNST(1), 2, CY_JUST_SET);

      PERFORM_ASHIFTR_CO(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(ASHIFTR_CO, s1, s1, CNST(1), 2, CY_JUST_SET);

      PERFORM_SHIFTL_CO(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(SHIFTL_CO, s1, s1, CNST(1), 2, CY_JUST_SET);

      PERFORM_ROTATEL_CO(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(ROTATEL_CO, s1, s1, CNST(1), 2, CY_JUST_SET);
#endif
#if M68000
      /* m68000:	andw	$1,d */
      PERFORM_AND(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(AND, s1, s1, CNST(1), 1, prune_hint & ~CY_JUST_SET);

      PERFORM_AND(v, co, r1, VALUE_MIN_SIGNED, ci);
      CRECURSE_2OP(AND, s1, s1, CNST_0x80000000, 2, prune_hint & ~CY_JUST_SET);

      PERFORM_IOR(v, co, r1, VALUE_MIN_SIGNED, ci);
      CRECURSE_2OP(IOR, s1, s1, CNST_0x80000000, 2, prune_hint & ~CY_JUST_SET);

      /* d = r1 ^ 1
	 m68000:	eorw	#1,d */
      PERFORM_XOR(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(XOR, s1, s1, CNST(1), 1, prune_hint & ~CY_JUST_SET);

      PERFORM_XOR(v, co, r1, VALUE_MIN_SIGNED, ci);
      CRECURSE_2OP(XOR, s1, s1, CNST_0x80000000, 2, prune_hint & ~CY_JUST_SET);
#endif
#if I386
      /* i80386:	andb	$1,d */
      PERFORM_AND_RC(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(AND_RC, s1, s1, CNST(1), 1, CY_JUST_SET | CY_0);

      PERFORM_AND_RC(v, co, r1, VALUE_MIN_SIGNED, ci);
      CRECURSE_2OP(AND_RC, s1, s1, CNST_0x80000000, 2, CY_JUST_SET | CY_0);

      PERFORM_IOR_RC(v, co, r1, VALUE_MIN_SIGNED, ci);
      CRECURSE_2OP(IOR_RC, s1, s1, CNST_0x80000000, 2, CY_JUST_SET | CY_0);

      /* d = r1 ^ 1
	 i80386:	xorb	$1,d */
      PERFORM_XOR_RC(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(XOR_RC, s1, s1, CNST(1), 1, CY_JUST_SET | CY_0);

      PERFORM_XOR_RC(v, co, r1, VALUE_MIN_SIGNED, ci);
      CRECURSE_2OP(XOR_RC, s1, s1, CNST_0x80000000, 2, CY_JUST_SET | CY_0);
#endif
#if PYR
      PERFORM_AND_CC(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(AND_CC, s1, s1, CNST(1), 1, 0);

      PERFORM_AND_CC(v, co, r1, VALUE_MIN_SIGNED, ci);
      CRECURSE_2OP(AND_CC, s1, s1, CNST_0x80000000, 2, 0);

      PERFORM_IOR_CC(v, co, r1, VALUE_MIN_SIGNED, ci);
      CRECURSE_2OP(IOR_CC, s1, s1, CNST_0x80000000, 2, 0);

      /* d = r1 ^ 1
	 pyramid:	xorw	$1,d */
      PERFORM_XOR_CC(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(XOR_CC, s1, s1, CNST(1), 1, 0);

      PERFORM_XOR_CC(v, co, r1, VALUE_MIN_SIGNED, ci);
      CRECURSE_2OP(XOR_CC, s1, s1, CNST_0x80000000, 2, 0);
#endif
#if M68000 || I386
      /* d = ~r1
	 m68000:	not	d
	 i80386:	not	d */
      PERFORM_SUB(v, co, VALUE(-1), r1, ci);
      CRECURSE_2OP(SUB, s1, CNST(-1), s1, 1, prune_hint & ~CY_JUST_SET);
#endif
#if PYR
      /* d = ~r1
	 pyramid:	mcomw	s1,d */
      /* We need a new insn: SUB_CC, for Subtract and Clobber Carry  */
#endif
#if I386
      /* d = r1 + 1
	 i80386:	inc	d */
      PERFORM_ADD(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(ADD, s1, s1, CNST(1), 2, prune_hint & ~CY_JUST_SET);
#endif
#if PYR
      /* d = r1 + 1
	 pyramid:	mova	1(s1),d */
      PERFORM_ADD(v, co, r1, VALUE(1), ci);
      RECURSE(ADD, s1, CNST(1), prune_hint & ~CY_JUST_SET);
#endif
#if I386
      /* d = r1 - 1
	 i80386:	dec	d */
      PERFORM_SUB(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(SUB, s1, s1, CNST(1), 1, prune_hint & ~CY_JUST_SET);
#endif
#if PYR
      /* d = r1 - 1
	 pyramid:	mova	-1(s1),d */
      PERFORM_ADD(v, co, r1, VALUE(-1), ci);
      RECURSE(ADD, s1, CNST(-1), prune_hint & ~CY_JUST_SET);
#endif
#if M68000 || I386 || PYR
      /* d,cy = r1 + 1
	 m68000:	addq	1,d
	 i80386:	add	1,d [short immediate form]
	 pyramid:	addw	$1,d */
      PERFORM_ADD_CO(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(ADD_CO, s1, s1, CNST(1), 1, CY_JUST_SET);
#endif
#if M68000 || I386
      /* d,cy = r1 - 1
	 m68000:	subq	1,d
	 i80386:	sub	1,d [short immediate form] */
      PERFORM_SUB_CO(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(SUB_CO, s1, s1, CNST(1), 1, CY_JUST_SET);
#endif
#if PYR && 0			/* same effect as addw $-1,d */
      /* d,cy = r1 + (-1)
	 pyramid:	subw	1,d */
      PERFORM_ADC_CO(v, co, r1, VALUE(1), ci);
      CRECURSE_2OP(ADC_CO, s1, s1, CNST(1), 1, CY_JUST_SET);
#endif
#if M68000
      /* d,cy = r1 + (-1)
	 m68000:	add	-1,d */
      PERFORM_ADD_CO(v, co, r1, VALUE(-1), ci);
      CRECURSE_2OP(ADD_CO, s1, s1, CNST(-1), 2, CY_JUST_SET);
#endif
#if I386 || PYR
      /* d,cy = r1 + (-1)
	 i80386:	add	-1,d
	 pyramid:	addw	$-1,d */
      PERFORM_ADD_CO(v, co, r1, VALUE(-1), ci);
      CRECURSE_2OP(ADD_CO, s1, s1, CNST(-1), 1, CY_JUST_SET);
#endif
#if M68000
      /* d,cy = r1 - (-1)
	 m68000:	sub	-1,d */
      PERFORM_SUB_CO(v, co, r1, VALUE(-1), ci);
      CRECURSE_2OP(SUB_CO, s1, s1, CNST(-1), 2, CY_JUST_SET);
#endif
#if I386
      /* d,cy = r1 - (-1)
	 i80386:	sub	-1,d */
      PERFORM_SUB_CO(v, co, r1, VALUE(-1), ci);
      CRECURSE_2OP(SUB_CO, s1, s1, CNST(-1), 1, CY_JUST_SET);
#endif
#if M68000 || I386
      /* d,cy = -r1
	 m68000:	neg	d
	 i80386:	neg	d */
      PERFORM_SUB_CO(v, co, VALUE(0), r1, ci);
      CRECURSE_2OP(SUB_CO, s1, CNST(0), s1, 1, CY_JUST_SET);
#endif
#if PYR
      /* d,cy = 0 + (-r1)
	 pyramid:	rsubw	$0,d */
      PERFORM_ADC_CO(v, co, VALUE(0), r1, ci);
      CRECURSE_2OP(ADC_CO, s1, CNST(0), s1, 1, CY_JUST_SET);
#endif
    }

#if M68020 && !M68000		/* don't do this for plain 68000 */
  /* kludge for immediate shift on 68k */
  if (last_dest >= 0 && last_dest == n_values - 1
      && values[last_dest] == VALUE(BITS_PER_WORD-1)
      && sequence[n_insns - 1].opcode == COPY)
    {
      for (s1 = n_values - 2; s1 >= 0; s1--)
	{
	  r1 = values[s1];

	  PERFORM_LSHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
	  CRECURSE_2OP(LSHIFTR_CO, s1, s1, last_dest, 1, CY_JUST_SET);

	  PERFORM_ASHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
	  CRECURSE_2OP(ASHIFTR_CO, s1, s1, last_dest, 1, CY_JUST_SET);

	  PERFORM_SHIFTL_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
	  CRECURSE_2OP(SHIFTL_CO, s1, s1, last_dest, 1, CY_JUST_SET);

	  PERFORM_ROTATEL_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
	  CRECURSE_2OP(ROTATEL_CO, s1, s1, last_dest, 1, CY_JUST_SET);

	  if (ci >= 0)
	    {
	      PERFORM_ROTATEXL_CIO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
	      CRECURSE_2OP(ROTATEXL_CIO, s1, s1, last_dest, 1, CY_JUST_SET);
	    }
	}
    }
#endif

  if (ci >= 0 && (prune_hint & CY_0) == 0 && flag_use_carry
      && (allowed_cost <= 1 ? ((prune_hint & CY_JUST_SET) != 0) : 1))
    {
#if M68000 || I386
      /* d = -cy, cy = cy
	 m68000:	subx	d,d
	 i80386:	sbb	d,d */
      PERFORM_SUB_CIO(v, co, VALUE(0), VALUE(0), ci);
      CRECURSE_NEW(SUB_CIO, n_values, n_values, n_values, 1,
		   prune_hint & ~CY_JUST_SET); /* cy not really affected */
#endif
#if PYR
      /* d = -cy, cy = cy
	 pyramid:	subwb	d,d */
      PERFORM_ADC_CIO(v, co, VALUE(0), VALUE(0), ci);
      CRECURSE_NEW(ADC_CIO, n_values, n_values, n_values, 1,
		   prune_hint & ~CY_JUST_SET); /* cy not really affected */
#endif
#if I386 /* slow on m68000 */
      /* i80386:	cmc */
      co = ci ^ 1;
      CRECURSE_2OP(COMCY, n_values, n_values, n_values, 1, CY_JUST_SET);
#endif
    }

  /* Move instructions.
     Don't do this if we are just permitted to do one more instruction.  */
  if (allowed_cost > 1)
    {
#if M68000 || PYR
      /* d = 0
	 m68000:	moveq	0,d
	 pyramid:	movw	0,d */
      PERFORM_COPY(v, co, VALUE(0), ci);
      CRECURSE_NEW(COPY, n_values, CNST(0), CNST(0), 1,
		   prune_hint & ~CY_JUST_SET);
#endif
#if M68000 || I386
      /* d = 0, cy = 0
	 m68000:	sub	d,d
	 i80386:	sub	d,d */
      PERFORM_SUB_CO(v, co, r1, r1, ci);
      CRECURSE_NEW(SUB_CO, n_values, n_values, n_values, 1, CY_JUST_SET | CY_0);
#endif
#if PYR
      /* d = 0, cy = 0
	 pyramid:	subw	d,d */
      PERFORM_ADC_CO(v, co, r1, r1, ci);
      CRECURSE_NEW(ADC_CO, n_values, n_values, n_values, 1, CY_JUST_SET | CY_0);
#endif
#if M68000
      /* d = 31
	 m68000:	moveq	31,d */
      PERFORM_COPY(v, co, VALUE(BITS_PER_WORD-1), ci);
      CRECURSE_NEW(COPY, n_values, CNST(BITS_PER_WORD-1), CNST(0), 1,
		   prune_hint & ~CY_JUST_SET);
#endif
#if M68000 || PYR
      /* d = 1
	 m68000:	moveq	1,d
	 pyramid:	movw	$1,d */
      PERFORM_COPY(v, co, VALUE(1), ci);
      CRECURSE_NEW(COPY, n_values, CNST(1), CNST(0), 1,
		   prune_hint & ~CY_JUST_SET);
      /* d = -1
	 m68000:	moveq	-1,d
	 pyramid:	movw	$-1,d  */
      PERFORM_COPY(v, co, VALUE(-1), ci);
      CRECURSE_NEW(COPY, n_values, CNST(-1), CNST(0), 1,
		   prune_hint & ~CY_JUST_SET);
#endif
#if M68000 || I386 || PYR	/* these cost 2 cost units */
      /* d = 0x80000000 */
      PERFORM_COPY(v, co, VALUE_MIN_SIGNED, ci);
      CRECURSE_NEW(COPY, n_values, CNST_0x80000000, CNST(0), 2,
		   prune_hint & ~CY_JUST_SET);

      /* d = 0x7fffffff */
      PERFORM_COPY(v, co, VALUE_MAX_SIGNED, ci);
      CRECURSE_NEW(COPY, n_values, CNST_0x7FFFFFFF, CNST(0), 2,
		   prune_hint & ~CY_JUST_SET);
#endif
    }
}
#endif

/* Call `synth' allowing deeper and deeper searches for each call.
   This way we achieve iterative deepening search.

   MAXMAX_COST is the maximum cost for any sequence we will accept.  */
void
main_synth(int maxmax_cost, int allowed_extra_cost)
{
  int max_cost;
  word values[0x100];
  insn_t sequence[0x100];
  int i, ii;

  init_immediates(tvalues);
  init_immediates(values);
  init_test_sets();

  /* Speed hack: Try to find random values that makes the goal function
     take a value != 0.  Many false sequences give 0 for all input,
     and this hack achieve quick reject of these sequences.  */
  for (i = 0; i < 50; i++)
    {
      for (ii = 0; ii < goal_function_arity; ii++)
	values[ii] = random_word();
      if ((*eval_goal_function)(values) != 0)
	break;
    }

  ii = 0;
#if KNOW_START
  switch (goal_function)
    {
    case FFS:
#if M88000
      /* Best ffs starting place.  */
      sequence[ii++] = (insn_t) { ADC_CO, CNST(0), 0, 1 };
      sequence[ii++] = (insn_t) { AND, 0, 1, 2 };
#endif
      break;

    case ZDEPI_FOR_MOVSI:
#if SPARC
      sequence[ii++] = (insn_t) { SUB, CNST(0), 0, 1 };
      sequence[ii++] = (insn_t) { AND, 0, 1, 2 };
#endif
      break;
    default: break;
    }
#endif

  fprintf(stderr, "Superoptimizing at cost");
  success = 0;
  for (max_cost = 1; max_cost <= maxmax_cost; max_cost++)
    {
#if TIMING
      for (i = 0; i <= max_cost; i++)
	timings[i] = 0;
#endif

      if (success)
	fprintf (stderr, "[cost %d]\n", max_cost + ii);
      else
	fprintf(stderr, " %d", max_cost + ii);
      fflush(stderr);

      i = run_program (sequence, ii, values);

      /* Don't pass CY_JUST_SET ever, since we don't know which of the
	 predefined insn above set cy.  */
      synth(sequence, ii, values, goal_function_arity+ii,
	    (*eval_goal_function)(values),
	    max_cost, i, NO_PRUNE);

#ifdef STATISTICS
      if (isatty(fileno(stdout)) == isatty(fileno(stderr)))
	printf("\n");
      printf("heuristic accept count:%u\n", heuristic_accept_count);
      printf("heuristic reject count:%u\n", heuristic_reject_count);
#endif
#if TIMING
      for (i = 1; i <= max_cost; i++)
	printf ("time %d: %d\n", i, timings[i] - timings[i - 1]);
#endif

      if (success)
	{
	  allowed_extra_cost--;
	  if (allowed_extra_cost < 0)
	    {
	      static char *s[] = {"", "s"};
	      fprintf(stderr, " [%d sequence%s found]\n", success,
		      s[success != 1]);
	      return;
	    }
	}
    }
  fprintf(stderr, " failure.\n");
}

/* Create a function for each DEF_GOAL.  When optimized, these are very
   efficient.  */
#undef	DEF_GOAL
#ifdef __STDC__
#define DEF_GOAL(SYM,ARITY,NAME,CODE)	 	\
word SYM ## _func (const word *v)		\
GOAL_FUNCTION (ARITY, CODE)
#else
#define DEF_GOAL(SYM,ARITY,NAME,CODE)	 	\
word SYM/**/_func (v) word *v;			\
GOAL_FUNCTION (ARITY, CODE)
#endif
#define GOAL_FUNCTION(ARITY,CODE)		\
{						\
  word r, v0, v1, v2, v3;			\
  switch (ARITY)				\
    {						\
    default:					\
      abort ();					\
    case 4: v3 = v[3];				\
    case 3: v2 = v[2];				\
    case 2: v1 = v[1];				\
    case 1: v0 = v[0];				\
    }						\
  CODE;						\
  return r;					\
}
#undef	DEF_SYNONYM
#define DEF_SYNONYM(SYM,NAME)
#include "goal.def"

struct
{
  char *fname;
  enum goal_func fcode;
  int arity;
  char *c_code;
  word (*function)(const word*);
} goal_table[] =
{
/* Start off with entries so that goal_names[i].fcode == i.  */
#undef	DEF_GOAL
#ifdef __STDC__
#define DEF_GOAL(SYM,ARITY,NAME,CODE) {NAME, SYM, ARITY, #CODE, SYM ## _func},
#else
#define DEF_GOAL(SYM,ARITY,NAME,CODE) {NAME, SYM, ARITY, "CODE", SYM/**/_func},
#endif
#undef	DEF_SYNONYM
#define DEF_SYNONYM(SYM,NAME)
#include "goal.def"

/* Now add the synonyms.  */
#undef	DEF_GOAL
#define DEF_GOAL(SYM,ARITY,NAME,CODE)
#undef	DEF_SYNONYM
#define DEF_SYNONYM(SYM,NAME) {NAME, SYM, 0, 0},
#include "goal.def"
};

#define GET_GOAL_NAME(X) (goal_table[X].fname)
#define GET_GOAL_ARITY(X) (goal_table[X].arity)
#define GET_GOAL_C_CODE(X) (goal_table[X].c_code)
#define GET_GOAL_FUNCTION(X) (goal_table[X].function)

int
main(int argc, char **argv)
{
  int maxmax_cost = 5;
  int allowed_extra_cost = 0;
  int flag_all = 0;

  goal_function = LAST_AND_UNUSED_GOAL_CODE;

  argv++;
  argc--;

  while (argc > 0)
    {
      char *arg = argv[0];
      int arglen = strlen(arg);

      if (arglen < 2)
	arglen = 2;

      if (!strncmp(arg, "-version", arglen))
	{
	  printf ("GSO version %s\n", version_string);
	  if (argc == 1)
	    exit (0);
	}
      else if (!strncmp(arg, "-assembler", arglen))
	flag_output_assembler = 1;
      else if (!strncmp(arg, "-no-carry-insns", arglen))
	flag_use_carry = 0;
      else if (!strncmp(arg, "-all", arglen))
	flag_all = 1;
      else if (!strncmp(arg, "-max-cost", arglen))
	{
	  argv++;
	  argc--;
	  if (argc == 0)
	    {
	      fprintf(stderr, "superoptimizer: argument to `-max-cost' expected\n");
	      exit(-1);
	    }
	  maxmax_cost = atoi(argv[0]);
	}
      else if (!strncmp(arg, "-extra-cost", arglen))
	{
	  argv++;
	  argc--;
	  if (argc == 0)
	    {
	      fprintf(stderr, "superoptimizer: argument `-extra-cost' expected\n");
	      exit(-1);
	    }
	  allowed_extra_cost = atoi(argv[0]);
	}
      else if (!strncmp(arg, "-f", 2))
	{
	  int i;
	  for (i = 0; i < sizeof(goal_table) / sizeof(goal_table[0]); i++)
	    {
	      if (!strcmp(arg + 2, goal_table[i].fname))
		{
		  goal_function = goal_table[i].fcode;
		  goal_function_arity = GET_GOAL_ARITY(goal_function);
		  eval_goal_function = GET_GOAL_FUNCTION(goal_function);
		  break;
		}
	    }
	  if (goal_function == LAST_AND_UNUSED_GOAL_CODE)
	    {
	      fprintf(stderr,
		      "superoptimizer: unknown goal function\n");
	      exit(-1);
	    }
	}
      else
	{
	  fprintf(stderr, "superoptimizer: syntax error at command line\n");
	  exit(-1);
	}

      argv++;
      argc--;
    }

  if (flag_all)
    {
      for (goal_function = 0; goal_function < LAST_AND_UNUSED_GOAL_CODE;
	   goal_function++)
	{
	  fprintf(stderr, "Searching for goal %s\n",
		  GET_GOAL_NAME (goal_function));

	  goal_function_arity = GET_GOAL_ARITY(goal_function);
	  eval_goal_function = GET_GOAL_FUNCTION(goal_function);
	  main_synth(maxmax_cost, allowed_extra_cost);
	  if (success)
	    fprintf(stderr, "%s\n", GET_GOAL_C_CODE(goal_function));
	}
      return 0;
    }
      
  if (goal_function == LAST_AND_UNUSED_GOAL_CODE)
    {
      fprintf(stderr, "superoptimizer: missing goal function definition\n");
      exit(-1);
    }

  fprintf(stderr, "Searching for %s\n", GET_GOAL_C_CODE(goal_function));
  main_synth(maxmax_cost, allowed_extra_cost);
  return !success;
}

/* Aux stuff that should go into a separate file.  */

int
ffs_internal(x)
     word x;
{
  int co, ci;
  word d;
  PERFORM_FFS(d, co, x, ci);
  return d;
}

const char clz_tab[] =
{
  32,31,30,30,29,29,29,29,28,28,28,28,28,28,28,28,
  27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,
  26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,
  26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,
  25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,
  25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,
  25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,
  25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,
  24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
};

const char ctz_tab[] =
{
  8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
};

const char ff1_tab[] =
{
  32,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,
  4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
  5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
  5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
  6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
};