Subversion Repositories openrisc

/* Multiply table generator for tile.

   Copyright (C) 2011, 2012

   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 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,