/* Multiply table generator for tile.
   Copyright (C) 2011-2017 Free Software Foundation, Inc.
   Contributed by Walter Lee (walt@tilera.com)

   This file is part of GCC.

   GCC 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 3, or (at your
   option) any later version.

   GCC 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 GCC; see the file COPYING3.  If not see
   <http://www.gnu.org/licenses/>.  */

/* This program creates a table used to compile multiply by constant
   efficiently.

   This program should be compiled by a c++ compiler.  If it's
   compiled with -DTILEPRO, it generates the multiply table for
   TILEPro; otherwise it generates the multiply table for TILE-Gx.
   Running the program produces the table in stdout.

   The program works by generating every possible combination of up to
   MAX_INSTRUCTIONS linear operators (such as add, sub, s2a, left
   shift) and computing the multiplier computed by those instructions.
   For example,

   s2a r2,r1,r1
   s2a r3,r2,r2

   multiplies r1 by 25.

   There are usually multiple instruction sequences to multiply by a
   given constant. This program keeps only the cheapest one.
   "Cheapest" is defined first by the minimum theoretical schedule
   length, and if those are equal then by the number of instructions,
   and if those are equal then by which instructions we "prefer"
   (e.g. because we think one might take infinitesimally less power
   than another, or simply because we arbitrarily pick one to be more
   canonical).

   Once this program has determined the best instruction sequence for
   each multiplier, it emits them in a table sorted by the multiplier
   so the user can binary-search it to look for a match.  The table is
   pruned based on various criteria to keep its sizes reasonable.  */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#define __STDC_LIMIT_MACROS
#include <stdint.h>

#include <map>

#ifdef TILEPRO

/* The string representing the architecture.  */
#define ARCH "tilepro"

/* The type for the multiplication.  */
typedef int MUL_TYPE;

#else

/* The string representing the architecture.  */
#define ARCH "tilegx"

/* The type for the multiplication.  */
typedef long long MUL_TYPE;

#endif

/* Longest instruction sequence this will produce. With the current
   stupid algorithm runtime grows very quickly with this number.  */
#define MAX_INSTRUCTIONS 4

/* Maximum number of subexpressions in the expression DAG being
   generated.  This is the same as the number of instructions, except
   that zero and the original register we'd like to multiply by a
   constant are also thrown into the mix.  */
#define MAX_SUBEXPRS (2 + MAX_INSTRUCTIONS)

#define MIN(x, y)  ((x) <= (y) ? (x) : (y))
#define MAX(x, y)  ((x) >= (y) ? (x) : (y))

/* For this program a unary op is one which has only one nonconstant
   operand.  So shift left by 5 is considered unary.  */
typedef MUL_TYPE (*unary_op_func) (MUL_TYPE);
typedef MUL_TYPE (*binary_op_func) (MUL_TYPE, MUL_TYPE);

/* This describes an operation like 'add two registers' or 'left-shift
   by 7'.

   We call something a 'unary' operator if it only takes in one
   register as input, even though it might have an implicit second
   constant operand.  Currently this is used for left-shift by
   constant.  */
class Operator
{
public:
  /* Construct for a binary operator.  */
  Operator (const char *pattern, const char *name, binary_op_func func,
	    int cost)
    : m_pattern (pattern), m_name (name), m_top_index (-1),
      m_unary_func (0), m_binary_func (func), m_cost (cost),
      m_rhs_if_unary (0)
  {
  }

  /* Construct for a unary operator.  */
  Operator (const char *pattern, const char *name, unary_op_func func,
	    int rhs_if_unary, int cost)
    : m_pattern (pattern), m_name (name), m_top_index (-1),
      m_unary_func (func), m_binary_func (0), m_cost (cost),
      m_rhs_if_unary (rhs_if_unary)
  {
  }

  bool is_unary () const
  {
    return m_binary_func == NULL;
  }

  /* Name of the pattern for this operation, e.g. CODE_FOR_addsi3.  */
  const char *m_pattern;

  /* Name of the opcode for this operation, e.g. add.  */
  const char *m_name;

  /* We don't have enough bits in our output representation to store
     the original insn_code value, so we store a compressed form
     instead.  These values are decoded back into insn_code via the
     machine-generated multiply_insn_seq_decode_opcode lookup
     table.  */
  int m_top_index;

  /* Unary operator to apply, or NULL if this is a binary operator.  */
  unary_op_func m_unary_func;

  /* Binary operator to apply, or NULL if this is a unary operator.  */
  binary_op_func m_binary_func;

  /* Function of how expensive we consider this operator. Higher is
     worse.  */
  int m_cost;

  /* the RHS value to write into the C file if unary; used for shift
     count.  */
  int m_rhs_if_unary;
};


/* An entry in an expression DAG.  */
class Expr
{
public:
  Expr () : m_op (NULL), m_lhs (0), m_rhs (0), m_produced_val (0),
    m_critical_path_length (0)
  {
  }

  /* The operator being applied to the operands.  */
  const Operator *m_op;

  /* The index of the left-hand operand in the array of subexpressions
     already computed.  */
  int m_lhs;

  /* For binary ops ,this is the index of the left-hand operand in the
     array of subexpressions already computed. For unary ops, it is
     specific to the op (e.g. it might hold a constant shift
     count).  */
  int m_rhs;

  /* The multiplier produced by this expression tree. For example, for
     the tree ((x << 5) + x), the value would be 33.  */
  MUL_TYPE m_produced_val;

  /* How far is this expression from the root, i.e. how many cycles
     minimum will it take to compute this?  */
  int m_critical_path_length;
};


/* Make function pointers for the various linear operators we can
   apply to compute a multiplicative value.  */

static MUL_TYPE
add (MUL_TYPE n1, MUL_TYPE n2)
{
  return n1 + n2;
}

static MUL_TYPE
sub (MUL_TYPE n1, MUL_TYPE n2)
{
  return n1 - n2;
}

static MUL_TYPE
s1a (MUL_TYPE n1, MUL_TYPE n2)
{
  return n1 * 2 + n2;
}

static MUL_TYPE
s2a (MUL_TYPE n1, MUL_TYPE n2)
{
  return n1 * 4 + n2;
}

static MUL_TYPE
s3a (MUL_TYPE n1, MUL_TYPE n2)
{
  return n1 * 8 + n2;
}

#define SHIFT(count)                            \
static MUL_TYPE                                 \
shift##count(MUL_TYPE n)                        \
{                                               \
  return n << (count);                          \
}

SHIFT (1);
SHIFT (2);
SHIFT (3);
SHIFT (4);
SHIFT (5);
SHIFT (6);
SHIFT (7);
SHIFT (8);
SHIFT (9);
SHIFT (10);
SHIFT (11);
SHIFT (12);
SHIFT (13);
SHIFT (14);
SHIFT (15);
SHIFT (16);
SHIFT (17);
SHIFT (18);
SHIFT (19);
SHIFT (20);
SHIFT (21);
SHIFT (22);
SHIFT (23);
SHIFT (24);
SHIFT (25);
SHIFT (26);
SHIFT (27);
SHIFT (28);
SHIFT (29);
SHIFT (30);
SHIFT (31);
#ifndef TILEPRO
SHIFT (32);
SHIFT (33);
SHIFT (34);
SHIFT (35);
SHIFT (36);
SHIFT (37);
SHIFT (38);
SHIFT (39);
SHIFT (40);
SHIFT (41);
SHIFT (42);
SHIFT (43);
SHIFT (44);
SHIFT (45);
SHIFT (46);
SHIFT (47);
SHIFT (48);
SHIFT (49);
SHIFT (50);
SHIFT (51);
SHIFT (52);
SHIFT (53);
SHIFT (54);
SHIFT (55);
SHIFT (56);
SHIFT (57);
SHIFT (58);
SHIFT (59);
SHIFT (60);
SHIFT (61);
SHIFT (62);
SHIFT (63);
#endif

#ifdef TILEPRO
static Operator ops[] = {
  Operator ("CODE_FOR_addsi3", "add", add, 1040),
  Operator ("CODE_FOR_subsi3", "sub", sub, 1041),
  Operator ("CODE_FOR_insn_s1a", "s1a", s1a, 1042),
  Operator ("CODE_FOR_insn_s2a", "s2a", s2a, 1043),
  Operator ("CODE_FOR_insn_s3a", "s3a", s3a, 1044),
  /* Note: shl by 1 is not necessary, since adding a value to itself
     produces the same result. But the architecture team thinks
     left-shift may use slightly less power, so we might as well
     prefer it.  */
  Operator ("CODE_FOR_ashlsi3", "shli", shift1, 1, 1001),
  Operator ("CODE_FOR_ashlsi3", "shli", shift2, 2, 1002),
  Operator ("CODE_FOR_ashlsi3", "shli", shift3, 3, 1003),
  Operator ("CODE_FOR_ashlsi3", "shli", shift4, 4, 1004),
  Operator ("CODE_FOR_ashlsi3", "shli", shift5, 5, 1005),
  Operator ("CODE_FOR_ashlsi3", "shli", shift6, 6, 1006),
  Operator ("CODE_FOR_ashlsi3", "shli", shift7, 7, 1007),
  Operator ("CODE_FOR_ashlsi3", "shli", shift8, 8, 1008),
  Operator ("CODE_FOR_ashlsi3", "shli", shift9, 9, 1009),
  Operator ("CODE_FOR_ashlsi3", "shli", shift10, 10, 1010),
  Operator ("CODE_FOR_ashlsi3", "shli", shift11, 11, 1011),
  Operator ("CODE_FOR_ashlsi3", "shli", shift12, 12, 1012),
  Operator ("CODE_FOR_ashlsi3", "shli", shift13, 13, 1013),
  Operator ("CODE_FOR_ashlsi3", "shli", shift14, 14, 1014),
  Operator ("CODE_FOR_ashlsi3", "shli", shift15, 15, 1015),
  Operator ("CODE_FOR_ashlsi3", "shli", shift16, 16, 1016),
  Operator ("CODE_FOR_ashlsi3", "shli", shift17, 17, 1017),
  Operator ("CODE_FOR_ashlsi3", "shli", shift18, 18, 1018),
  Operator ("CODE_FOR_ashlsi3", "shli", shift19, 19, 1019),
  Operator ("CODE_FOR_ashlsi3", "shli", shift20, 20, 1020),
  Operator ("CODE_FOR_ashlsi3", "shli", shift21, 21, 1021),
  Operator ("CODE_FOR_ashlsi3", "shli", shift22, 22, 1022),
  Operator ("CODE_FOR_ashlsi3", "shli", shift23, 23, 1023),
  Operator ("CODE_FOR_ashlsi3", "shli", shift24, 24, 1024),
  Operator ("CODE_FOR_ashlsi3", "shli", shift25, 25, 1025),
  Operator ("CODE_FOR_ashlsi3", "shli", shift26, 26, 1026),
  Operator ("CODE_FOR_ashlsi3", "shli", shift27, 27, 1027),
  Operator ("CODE_FOR_ashlsi3", "shli", shift28, 28, 1028),
  Operator ("CODE_FOR_ashlsi3", "shli", shift29, 29, 1029),
  Operator ("CODE_FOR_ashlsi3", "shli", shift30, 30, 1030),
  Operator ("CODE_FOR_ashlsi3", "shli", shift31, 31, 1031)
};
#else
static Operator ops[] = {
  Operator ("CODE_FOR_adddi3", "add", add, 1070),
  Operator ("CODE_FOR_subdi3", "sub", sub, 1071),
  Operator ("CODE_FOR_insn_shl1add", "shl1add", s1a, 1072),
  Operator ("CODE_FOR_insn_shl2add", "shl2add", s2a, 1073),
  Operator ("CODE_FOR_insn_shl3add", "shl3add", s3a, 1074),
  // Note: shl by 1 is not necessary, since adding a value to itself
  // produces the same result. But the architecture team thinks left-shift
  // may use slightly less power, so we might as well prefer it.
  Operator ("CODE_FOR_ashldi3", "shli", shift1, 1, 1001),
  Operator ("CODE_FOR_ashldi3", "shli", shift2, 2, 1002),
  Operator ("CODE_FOR_ashldi3", "shli", shift3, 3, 1003),
  Operator ("CODE_FOR_ashldi3", "shli", shift4, 4, 1004),
  Operator ("CODE_FOR_ashldi3", "shli", shift5, 5, 1005),
  Operator ("CODE_FOR_ashldi3", "shli", shift6, 6, 1006),
  Operator ("CODE_FOR_ashldi3", "shli", shift7, 7, 1007),
  Operator ("CODE_FOR_ashldi3", "shli", shift8, 8, 1008),
  Operator ("CODE_FOR_ashldi3", "shli", shift9, 9, 1009),
  Operator ("CODE_FOR_ashldi3", "shli", shift10, 10, 1010),
  Operator ("CODE_FOR_ashldi3", "shli", shift11, 11, 1011),
  Operator ("CODE_FOR_ashldi3", "shli", shift12, 12, 1012),
  Operator ("CODE_FOR_ashldi3", "shli", shift13, 13, 1013),
  Operator ("CODE_FOR_ashldi3", "shli", shift14, 14, 1014),
  Operator ("CODE_FOR_ashldi3", "shli", shift15, 15, 1015),
  Operator ("CODE_FOR_ashldi3", "shli", shift16, 16, 1016),
  Operator ("CODE_FOR_ashldi3", "shli", shift17, 17, 1017),
  Operator ("CODE_FOR_ashldi3", "shli", shift18, 18, 1018),
  Operator ("CODE_FOR_ashldi3", "shli", shift19, 19, 1019),
  Operator ("CODE_FOR_ashldi3", "shli", shift20, 20, 1020),
  Operator ("CODE_FOR_ashldi3", "shli", shift21, 21, 1021),
  Operator ("CODE_FOR_ashldi3", "shli", shift22, 22, 1022),
  Operator ("CODE_FOR_ashldi3", "shli", shift23, 23, 1023),
  Operator ("CODE_FOR_ashldi3", "shli", shift24, 24, 1024),
  Operator ("CODE_FOR_ashldi3", "shli", shift25, 25, 1025),
  Operator ("CODE_FOR_ashldi3", "shli", shift26, 26, 1026),
  Operator ("CODE_FOR_ashldi3", "shli", shift27, 27, 1027),
  Operator ("CODE_FOR_ashldi3", "shli", shift28, 28, 1028),
  Operator ("CODE_FOR_ashldi3", "shli", shift29, 29, 1029),
  Operator ("CODE_FOR_ashldi3", "shli", shift30, 30, 1030),
  Operator ("CODE_FOR_ashldi3", "shli", shift31, 31, 1031),
  Operator ("CODE_FOR_ashldi3", "shli", shift32, 32, 1032),
  Operator ("CODE_FOR_ashldi3", "shli", shift33, 33, 1033),
  Operator ("CODE_FOR_ashldi3", "shli", shift34, 34, 1034),
  Operator ("CODE_FOR_ashldi3", "shli", shift35, 35, 1035),
  Operator ("CODE_FOR_ashldi3", "shli", shift36, 36, 1036),
  Operator ("CODE_FOR_ashldi3", "shli", shift37, 37, 1037),
  Operator ("CODE_FOR_ashldi3", "shli", shift38, 38, 1038),
  Operator ("CODE_FOR_ashldi3", "shli", shift39, 39, 1039),
  Operator ("CODE_FOR_ashldi3", "shli", shift40, 40, 1040),
  Operator ("CODE_FOR_ashldi3", "shli", shift41, 41, 1041),
  Operator ("CODE_FOR_ashldi3", "shli", shift42, 42, 1042),
  Operator ("CODE_FOR_ashldi3", "shli", shift43, 43, 1043),
  Operator ("CODE_FOR_ashldi3", "shli", shift44, 44, 1044),
  Operator ("CODE_FOR_ashldi3", "shli", shift45, 45, 1045),
  Operator ("CODE_FOR_ashldi3", "shli", shift46, 46, 1046),
  Operator ("CODE_FOR_ashldi3", "shli", shift47, 47, 1047),
  Operator ("CODE_FOR_ashldi3", "shli", shift48, 48, 1048),
  Operator ("CODE_FOR_ashldi3", "shli", shift49, 49, 1049),
  Operator ("CODE_FOR_ashldi3", "shli", shift50, 50, 1050),
  Operator ("CODE_FOR_ashldi3", "shli", shift51, 51, 1051),
  Operator ("CODE_FOR_ashldi3", "shli", shift52, 52, 1052),
  Operator ("CODE_FOR_ashldi3", "shli", shift53, 53, 1053),
  Operator ("CODE_FOR_ashldi3", "shli", shift54, 54, 1054),
  Operator ("CODE_FOR_ashldi3", "shli", shift55, 55, 1055),
  Operator ("CODE_FOR_ashldi3", "shli", shift56, 56, 1056),
  Operator ("CODE_FOR_ashldi3", "shli", shift57, 57, 1057),
  Operator ("CODE_FOR_ashldi3", "shli", shift58, 58, 1058),
  Operator ("CODE_FOR_ashldi3", "shli", shift59, 59, 1059),
  Operator ("CODE_FOR_ashldi3", "shli", shift60, 60, 1060),
  Operator ("CODE_FOR_ashldi3", "shli", shift61, 61, 1061),
  Operator ("CODE_FOR_ashldi3", "shli", shift62, 62, 1062),
  Operator ("CODE_FOR_ashldi3", "shli", shift63, 63, 1063)
};
#endif

/* An ExpressionTree is an expression DAG.  */
class ExpressionTree
{
public:
  ExpressionTree () : m_num_vals (2)
  {
    m_exprs[0].m_produced_val = 0;
    m_exprs[1].m_produced_val = 1;
  }

  void copy_technique_from (ExpressionTree * other)
  {
    /* TODO: write this; other can compute the same products with less
       cost.  We update this ExpressionTree object because some int is
       already mapped to it.  */
  }

  int m_num_vals;
  Expr m_exprs[MAX_SUBEXPRS];

  int cost () const
  {
    int cost = 0;
    for (int j = 2; j < m_num_vals; j++)
        cost += m_exprs[j].m_op->m_cost;
      return cost + m_exprs[m_num_vals - 1].m_critical_path_length * 1000000;
  }
};


typedef std::map<MUL_TYPE, ExpressionTree *> ExpressionTreeMap;


static void
find_sequences (ExpressionTree &s, ExpressionTreeMap &best_solution)
{
  /* Don't look more if we can't add any new values to the expression
     tree.  */
  const int num_vals = s.m_num_vals;
  if (num_vals == MAX_SUBEXPRS)
    return;

  /* Grow array to make room for new values added as we loop.  */
  s.m_num_vals = num_vals + 1;

  const Operator *const prev_op = s.m_exprs[num_vals - 1].m_op;
  const int prev_top_index = (prev_op != NULL) ? prev_op->m_top_index : -1;

  for (size_t f = 0; f < sizeof ops / sizeof ops[0]; f++)
    {
      const Operator *const op = &ops[f];

      for (int i = 0; i < num_vals; i++)
	{
	  /* Only allow zero as the first operand to sub, otherwise
	     it is useless.  */
	  if (i == 0 && op->m_binary_func != sub)
	    continue;

	  /* Unary ops don't actually use the second operand, so as a
	     big hack we trick it into only looping once in the inner
	     loop.  */
	  const int j_end = op->is_unary () ? 2 : num_vals;

	  /* We never allow zero as the second operand, as it is
	     always useless.  */
	  for (int j = 1; j < j_end; j++)
	    {
	      /* Does this expression use the immediately previous
		 expression?  */
	      const bool uses_prev_value =
		(i == num_vals - 1
		 || (!op->is_unary () && j == num_vals - 1));

	      if (!uses_prev_value)
		{
		  /* For search efficiency, prune redundant
		     instruction orderings.

		     This op does not take the immediately preceding
		     value as input, which means we could have done it
		     in the previous slot. If its opcode is less than
		     the previous instruction's, we'll declare this
		     instruction order non-canonical and not pursue
		     this branch of the search.  */
		  if (op->m_top_index < prev_top_index)
		    continue;
		}

	      MUL_TYPE n;
	      if (op->is_unary ())
		{
		  n = op->m_unary_func (s.m_exprs[i].m_produced_val);
		}
	      else
		{
		  n = op->m_binary_func (s.m_exprs[i].m_produced_val,
					 s.m_exprs[j].m_produced_val);
		}

	      bool duplicate = false;
	      for (int k = 0; k < num_vals; k++)
		if (n == s.m_exprs[j].m_produced_val)
		  {
		    duplicate = true;
		    break;
		  }

	      if (duplicate)
		continue;

	      /* See if we found the best solution for n.  */
	      Expr *e = &s.m_exprs[num_vals];
	      e->m_op = op;
	      e->m_lhs = i;
	      e->m_rhs = op->is_unary () ? op->m_rhs_if_unary : j;
	      e->m_produced_val = n;
	      e->m_critical_path_length =
		1 + MAX (s.m_exprs[i].m_critical_path_length,
			 s.m_exprs[j].m_critical_path_length);

	      ExpressionTreeMap::iterator best (best_solution.find (n));
	      if (best == best_solution.end ()
		  || (*best).second->cost () > s.cost ())
		best_solution[n] = new ExpressionTree (s);

	      /* Recurse and find more.  */
	      find_sequences (s, best_solution);
	    }
	}
    }

  /* Restore old size.  */
  s.m_num_vals = num_vals;
}


/* For each insn_code used by an operator, choose a compact number so
   it takes less space in the output data structure. This prints out a
   lookup table used to map the compactified number back to an
   insn_code.  */
static void
create_insn_code_compression_table ()
{
  int next_index = 1;

  /* Entry 0 must hold CODE_FOR_nothing to mean "end of array".  */
  printf ("const enum insn_code %s_multiply_insn_seq_decode_opcode[] = {\n"
	  "  CODE_FOR_nothing /* must be first */ ", ARCH);

  for (size_t i = 0; i < sizeof ops / sizeof ops[0]; i++)
    {
      Operator *op = &ops[i];
      int index = -1;

      /* See if some previous Operator was using the same insn_code.
	 If so, reuse its table entry.  */
      for (size_t j = 0; j < i; j++)
	{
	  Operator *old = &ops[j];
	  if (strcmp (old->m_pattern, op->m_pattern) == 0)
	    {
	      index = old->m_top_index;
	      break;
	    }
	}

      if (index == -1)
	{
	  /* We need to make a new entry in the table.  */
	  printf (",\n  %s", op->m_pattern);
	  index = next_index++;
	}

      op->m_top_index = index;
    }

  printf ("\n};\n\n");
}


/* These are constants we've seen in code, that we want to keep table
   entries for.  */
static int multiply_constants_used[] = {
  -11796480,
  -27439,
  -25148,
  -22820,
  -21709,
  -20995,
  -20284,
  -20239,
  -19595,
  -19447,
  -19183,
  -19165,
  -18730,
  -17828,
  -17799,
  -17237,
  -17036,
  -16549,
  -16423,
  -16294,
  -16244,
  -16069,
  -15137,
  -15083,
  -15038,
  -14924,
  -14905,
  -14752,
  -14731,
  -14529,
  -14273,
  -14090,
  -14084,
  -14043,
  -13850,
  -13802,
  -13631,
  -13455,
  -13275,
  -12879,
  -12700,
  -12534,
  -12399,
  -12131,
  -12112,
  -12054,
  -12019,
  -11759,
  -11585,
  -11467,
  -11395,
  -11295,
  -11248,
  -11148,
  -11116,
  -11086,
  -11059,
  -11018,
  -10811,
  -10538,
  -10258,
  -10217,
  -10033,
  -9766,
  -9754,
  -9534,
  -9527,
  -9467,
  -9262,
  -9232,
  -9222,
  -9198,
  -9191,
  -9113,
  -8825,
  -8756,
  -8697,
  -8693,
  -8565,
  -8342,
  -8208,
  -8200,
  -8170,
  -8102,
  -7770,
  -7678,
  -7562,
  -7376,
  -7373,
  -7221,
  -7121,
  -6835,
  -6810,
  -6626,
  -6581,
  -6461,
  -6278,
  -6263,
  -6163,
  -6029,
  -5816,
  -5540,
  -5461,
  -5384,
  -5329,
  -4985,
  -4926,
  -4815,
  -4788,
  -4758,
  -4433,
  -4229,
  -4209,
  -4176,
  -4104,
  -4095,
  -4078,
  -3941,
  -3818,
  -3600,
  -3474,
  -3314,
  -3264,
  -3196,
  -3072,
  -2912,
  -2836,
  -2773,
  -2269,
  -2184,
  -2100,
  -1730,
  -1512,
  -1500,
  -1396,
  -1344,
  -1312,
  -1297,
  -1059,
  -1058,
  1027,
  1049,
  1059,
  1100,
  1104,
  1108,
  1136,
  1200,
  1204,
  1242,
  1292,
  1304,
  1312,
  1320,
  1336,
  1344,
  1348,
  1360,
  1364,
  1395,
  1448,
  1460,
  1461,
  1472,
  1488,
  1500,
  1512,
  1568,
  1576,
  1649,
  1664,
  1684,
  1696,
  1744,
  1812,
  1822,
  1884,
  1963,
  1978,
  2000,
  2012,
  2014,
  2037,
  2039,
  2100,
  2139,
  2144,
  2184,
  2237,
  2260,
  2320,
  2408,
  2446,
  2447,
  2499,
  2531,
  2578,
  2592,
  2611,
  2633,
  2704,
  2730,
  2773,
  2880,
  2896,
  2998,
  3000,
  3001,
  3021,
  3079,
  3112,
  3150,
  3179,
  3192,
  3240,
  3264,
  3271,
  3283,
  3328,
  3363,
  3367,
  3453,
  3529,
  3570,
  3580,
  3600,
  3624,
  3707,
  3783,
  3826,
  3897,
  3941,
  3962,
  3989,
  4000,
  4025,
  4073,
  4093,
  4099,
  4108,
  4184,
  4209,
  4369,
  4376,
  4416,
  4433,
  4434,
  4482,
  4582,
  4712,
  4717,
  4813,
  4815,
  4864,
  5000,
  5027,
  5040,
  5091,
  5195,
  5243,
  5260,
  5285,
  5329,
  5331,
  5350,
  5361,
  5387,
  5461,
  5492,
  5529,
  5573,
  5793,
  5819,
  5915,
  5946,
  5992,
  6000,
  6164,
  6205,
  6262,
  6263,
  6269,
  6270,
  6387,
  6400,
  6406,
  6476,
  6541,
  6565,
  6568,
  6626,
  6656,
  6732,
  6810,
  6817,
  6859,
  7040,
  7053,
  7141,
  7169,
  7221,
  7223,
  7274,
  7282,
  7350,
  7369,
  7373,
  7442,
  7447,
  7471,
  7518,
  7542,
  7566,
  7587,
  7663,
  7678,
  7682,
  7748,
  7752,
  7791,
  8000,
  8026,
  8048,
  8170,
  8203,
  8204,
  8290,
  8368,
  8520,
  8640,
  8666,
  8672,
  8697,
  8716,
  8728,
  8756,
  8820,
  8875,
  8918,
  8956,
  9058,
  9154,
  9175,
  9191,
  9217,
  9262,
  9321,
  9373,
  9434,
  9465,
  9514,
  9534,
  9633,
  9746,
  9810,
  9850,
  9947,
  9973,
  10000,
  10009,
  10033,
  10055,
  10217,
  10248,
  10298,
  10310,
  10323,
  10368,
  10438,
  10456,
  10486,
  10538,
  10664,
  10695,
  10700,
  10703,
  10832,
  10887,
  10935,
  10958,
  11018,
  11059,
  11061,
  11086,
  11116,
  11148,
  11190,
  11249,
  11314,
  11332,
  11363,
  11409,
  11415,
  11443,
  11467,
  11512,
  11522,
  11529,
  11585,
  11759,
  11768,
  11795,
  11893,
  11997,
  12131,
  12299,
  12536,
  12543,
  12893,
  12945,
  12998,
  13109,
  13213,
  13685,
  13930,
  14023,
  14024,
  14271,
  14564,
  14647,
  15326,
  15850,
  15855,
  15929,
  16000,
  16154,
  16496,
  16807,
  16819,
  16984,
  17203,
  17223,
  17333,
  17760,
  17799,
  17837,
  18029,
  18068,
  18336,
  18515,
  19595,
  20017,
  20131,
  20862,
  20995,
  21709,
  22554,
  25000,
  25172,
  25600,
  25733,
  27439,
  38470,
  46802,
  50000,
  11796480,
  16843009,
  23592960,
};


const int num_mult_constants_used =
  (int)(sizeof multiply_constants_used
	/ sizeof multiply_constants_used[0]);


#define XSIZE (sizeof multiply_constants_used / \
	       sizeof multiply_constants_used[0] + 32) / 32
unsigned multiply_constants_avail[XSIZE];
#undef XSIZE


/* bsearch helper function.  */
static int
compare_constants (const void *key, const void *t)
{
  return (*(int*)key) - *((int*)t);
}


static int *
find_mult_constants_used (int multiplier)
{
  return (int *) bsearch (&multiplier, multiply_constants_used,
			  num_mult_constants_used,
			  sizeof multiply_constants_used[0],
			  compare_constants);
}


int num_ops (ExpressionTree *s)
{
  int n = 0;
  for (int i = 0; i < s->m_num_vals; i++)
    {
      Expr *e = &s->m_exprs[i];
      if (e->m_op != NULL)
	n++;
    }
  return n;
}


#ifdef TILEPRO
bool
tilepro_emit (int multiplier, int num_ops)
{
  int abs_multiplier = (multiplier >= 0) ? multiplier : -multiplier;

  /* Keep constants in range [-1024, 1024].  */
  if (abs_multiplier <= 1024)
    return true;

  /* Keep constants near powers of two.  */
  int prev_pow2 = 1 << (31 - __builtin_clz (abs_multiplier));
  int next_pow2 = prev_pow2 << 1;

  if ((abs_multiplier - prev_pow2 <= 10)
      || (next_pow2 - abs_multiplier <= 10))
    return true;

  /* Keep constants near powers of ten.  */
  {
    long long j = 1;
    long long prev_pow10;
    long long next_pow10;

    while (((j * 10) < abs_multiplier)
	   && (j < (j * 10)))
      j = j * 10;

    prev_pow10 = j;
    next_pow10 = j * 10;

    if ((abs_multiplier - prev_pow10 <= 10)
	|| (next_pow10 - abs_multiplier <= 10))
      return true;
  }

  /* Keep short sequences that have two or fewer ops.  */
  if (num_ops <= 2)
    return true;

  /* Keep constants that are mostly 0's or mostly 1's.  */
  if (__builtin_popcount (multiplier) <= 2 ||
      __builtin_popcount (multiplier) >= 30)
    return true;

  /* Keep constants seen in actual code.  */
  if ((find_mult_constants_used (multiplier)))
    return true;

  return false;
}
#else
bool
tilegx_emit (long long multiplier, int num_ops)
{
  long long abs_multiplier = (multiplier >= 0) ? multiplier : - multiplier;

  /* Keep constants in range [-1024, 1024].  */
  if (abs_multiplier <= 1024)
    return true;

  /* Otherwise exclude sequences with four ops.  */
  if (num_ops > 3)
    return false;

  /* Keep constants near powers of two.  */
  {
    unsigned long long prev_pow2 =
      1LL << (63 - __builtin_clzll (abs_multiplier));
    unsigned long long next_pow2 = prev_pow2 << 1;

    /* handle overflow case. */
    if (next_pow2 == 0)
      {
	if (prev_pow2 - abs_multiplier <= 10)
	  return true;
      }
    else if ((abs_multiplier - prev_pow2 <= 10)
	     || (next_pow2 - abs_multiplier <= 10))
      return true;
  }

  /* Keep constants near powers of ten.  */
  {
    long long j = 1;
    long long prev_pow10;
    long long next_pow10;

    while (((j * 10) < abs_multiplier)
	   && (j < (INTMAX_MAX / 10)))
      j = j * 10;

    prev_pow10 = j;
    next_pow10 = (j > (INTMAX_MAX / 10)) ? 0 : j * 10;

    if ((abs_multiplier - prev_pow10 <= 100)
	|| (next_pow10
	    && (next_pow10 - abs_multiplier <= 100)))
      return true;
  }

  if (num_ops <= 2)
    return true;

  /* Keep constants that are mostly 0's or mostly 1's.  */
  if (__builtin_popcountll (multiplier) <= 2 ||
      __builtin_popcountll (multiplier) >= 62)
    return true;

  /* Keep constants seen in actual code.  */
  if (find_mult_constants_used (multiplier))
    return true;

  return false;
}
#endif


int
main ()
{
  ExpressionTreeMap best_solution;
  ExpressionTree s;

#ifdef TILEPRO
  printf ("/* Constant multiply table for TILEPro.\n");
#else
  printf ("/* Constant multiply table for TILE-Gx.\n");
#endif
  printf ("   Copyright (C) 2011-2017 Free Software Foundation, Inc.\n");
  printf ("   Contributed by Walter Lee (walt@tilera.com)\n");
  printf ("\n");
  printf ("   This file is part of GCC.\n");
  printf ("\n");
  printf ("   GCC is free software; you can redistribute it and/or modify it\n");
  printf ("   under the terms of the GNU General Public License as published\n");
  printf ("   by the Free Software Foundation; either version 3, or (at your\n");
  printf ("   option) any later version.\n");
  printf ("\n");
  printf ("   GCC is distributed in the hope that it will be useful, but WITHOUT\n");
  printf ("   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY\n");
  printf ("   or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public\n");
  printf ("   License for more details.\n");
  printf ("\n");
  printf ("   You should have received a copy of the GNU General Public License\n");
  printf ("   along with GCC; see the file COPYING3.  If not see\n");
  printf ("   <http://www.gnu.org/licenses/>.  */\n");
  printf ("\n");
  printf ("/* Note this file is auto-generated from gen-mul-tables.cc.\n");
  printf ("   Make any required changes there.  */\n");
  printf ("\n");
  printf ("#include \"config.h\"\n");
  printf ("#include \"system.h\"\n");
  printf ("#include \"coretypes.h\"\n");
  printf ("#include \"backend.h\"\n");
  printf ("#include \"rtl.h\"\n");
  printf ("#include \"expmed.h\"\n");
  printf ("#include \"%s-multiply.h\"\n\n", ARCH);
  create_insn_code_compression_table ();

  /* Try all combinations of operators and see what constants we
     produce.  For each possible constant, record the most efficient
     way to generate it.  */
  find_sequences (s, best_solution);

  printf ("const struct %s_multiply_insn_seq "
	  "%s_multiply_insn_seq_table[] = {\n",
	  ARCH, ARCH);

  const char *comma_separator = "";

  ExpressionTreeMap::iterator i (best_solution.begin ());
  for (; i != best_solution.end (); ++i)
    {
      ExpressionTree *s = (*i).second;
      const MUL_TYPE n = (*i).first;

      if (n == 0 || n == 1)
	{
	  /* Both of these require zero operations, so these entries
	     are bogus and should never be used.  */
	  continue;
	}

      /* Prune the list of entries to keep the table to a reasonable
	 size.  */
#ifdef TILEPRO
      if (!tilepro_emit (n, num_ops (s)))
	continue;
#else
      if (!tilegx_emit (n, num_ops (s)))
	continue;
#endif

      printf ("%s", comma_separator);

#ifdef TILEPRO
      const MUL_TYPE int_min = INT32_MIN;
#else
      const MUL_TYPE int_min = INT64_MIN;
#endif
      if (n == int_min)
	{
	  /* Handle C's woeful lack of unary negation. Without this,
	     printing out INT_MIN in decimal will yield an unsigned
	     int which could generate a compiler warning.  */
#ifdef TILEPRO
	  printf ("  {%d - 1 /* 0x%x */ ,\n   {", n + 1,
		  (unsigned) n);
#else
	  printf ("  {%lldll - 1 /* 0x%llx */ ,\n   {", n + 1,
		  (unsigned MUL_TYPE) n);
#endif
	}
      else
	{
#ifdef TILEPRO
	  printf ("  {%d /* 0x%x */ ,\n   {", n, (unsigned) n);
#else
	  printf ("  {%lldll /* 0x%llx */ ,\n   {", n, (unsigned MUL_TYPE) n);
#endif
	}

      bool first = true;
      for (int j = 0; j < s->m_num_vals; j++)
	{
	  Expr *e = &s->m_exprs[j];

	  const Operator *op = e->m_op;
	  if (op == NULL)
	    continue;

	  char buf[1024];
	  snprintf (buf, sizeof buf, "%s{%d, %d, %d}%s",
		    first ? "" : "    ",
		    op->m_top_index,
		    e->m_lhs, e->m_rhs, (j + 1) == s->m_num_vals ? "}" : ",");

	  char opnd0[10];
	  if (e->m_lhs)
	    snprintf (opnd0, sizeof opnd0, "r%d", e->m_lhs);
	  else
	    snprintf (opnd0, sizeof opnd0, "zero");

	  printf ("%s\t\t\t/* %s r%d, %s, %s%d */\n",
		  buf, op->m_name, j, opnd0,
		  op->is_unary () ? "" : "r", e->m_rhs);

	  first = false;
	}
      printf ("   }");
      comma_separator = ",\n";
    }

  printf ("\n};\n\n");
  printf ("const int %s_multiply_insn_seq_table_size =\n"
	  "  (int) (sizeof %s_multiply_insn_seq_table\n"
	  "         / sizeof %s_multiply_insn_seq_table[0]);\n",
	  ARCH, ARCH, ARCH);

  return EXIT_SUCCESS;
}