URL
https://opencores.org/ocsvn/openrisc/openrisc/trunk
Subversion Repositories openrisc
[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [config/] [tilepro/] [gen-mul-tables.cc] - Rev 713
Go to most recent revision | Compare with Previous | Blame | View Log
/* 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, -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, 2012\n"); printf (" 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 ("#include \"config.h\"\n"); printf ("#include \"system.h\"\n"); printf ("#include \"coretypes.h\"\n"); printf ("#include \"expr.h\"\n"); printf ("#include \"optabs.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; }
Go to most recent revision | Compare with Previous | Blame | View Log