gcc/expmed.h

   1 /* Target-dependent costs for expmed.c.
   2    Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
   4    Free Software Foundation, Inc.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option; any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #ifndef EXPMED_H
  23 #define EXPMED_H 1
  24
  25 enum alg_code {
  26   alg_unknown,
  27   alg_zero,
  28   alg_m, alg_shift,
  29   alg_add_t_m2,
  30   alg_sub_t_m2,
  31   alg_add_factor,
  32   alg_sub_factor,
  33   alg_add_t2_m,
  34   alg_sub_t2_m,
  35   alg_impossible
  36 };
  37
  38 /* This structure holds the "cost" of a multiply sequence.  The
  39    "cost" field holds the total rtx_cost of every operator in the
  40    synthetic multiplication sequence, hence cost(a op b) is defined
  41    as rtx_cost(op) + cost(a) + cost(b), where cost(leaf) is zero.
  42    The "latency" field holds the minimum possible latency of the
  43    synthetic multiply, on a hypothetical infinitely parallel CPU.
  44    This is the critical path, or the maximum height, of the expression
  45    tree which is the sum of rtx_costs on the most expensive path from
  46    any leaf to the root.  Hence latency(a op b) is defined as zero for
  47    leaves and rtx_cost(op) + max(latency(a), latency(b)) otherwise.  */
  48
  49 struct mult_cost {
  50   short cost;     /* Total rtx_cost of the multiplication sequence.  */
  51   short latency;  /* The latency of the multiplication sequence.  */
  52 };
  53
  54 /* This macro is used to compare a pointer to a mult_cost against an
  55    single integer "rtx_cost" value.  This is equivalent to the macro
  56    CHEAPER_MULT_COST(X,Z) where Z = {Y,Y}.  */
  57 #define MULT_COST_LESS(X,Y) ((X)->cost < (Y)    \
  58                              || ((X)->cost == (Y) && (X)->latency < (Y)))
  59
  60 /* This macro is used to compare two pointers to mult_costs against
  61    each other.  The macro returns true if X is cheaper than Y.
  62    Currently, the cheaper of two mult_costs is the one with the
  63    lower "cost".  If "cost"s are tied, the lower latency is cheaper.  */
  64 #define CHEAPER_MULT_COST(X,Y)  ((X)->cost < (Y)->cost          \
  65                                  || ((X)->cost == (Y)->cost     \
  66                                      && (X)->latency < (Y)->latency))
  67
  68 /* This structure records a sequence of operations.
  69    `ops' is the number of operations recorded.
  70    `cost' is their total cost.
  71    The operations are stored in `op' and the corresponding
  72    logarithms of the integer coefficients in `log'.
  73
  74    These are the operations:
  75    alg_zero             total := 0;
  76    alg_m                total := multiplicand;
  77    alg_shift            total := total * coeff
  78    alg_add_t_m2         total := total + multiplicand * coeff;
  79    alg_sub_t_m2         total := total - multiplicand * coeff;
  80    alg_add_factor       total := total * coeff + total;
  81    alg_sub_factor       total := total * coeff - total;
  82    alg_add_t2_m         total := total * coeff + multiplicand;
  83    alg_sub_t2_m         total := total * coeff - multiplicand;
  84
  85    The first operand must be either alg_zero or alg_m.  */
  86
  87 struct algorithm
  88 {
  89   struct mult_cost cost;
  90   short ops;
  91   /* The size of the OP and LOG fields are not directly related to the
  92      word size, but the worst-case algorithms will be if we have few
  93      consecutive ones or zeros, i.e., a multiplicand like 10101010101...
  94      In that case we will generate shift-by-2, add, shift-by-2, add,...,
  95      in total wordsize operations.  */
  96   enum alg_code op[MAX_BITS_PER_WORD];
  97   char log[MAX_BITS_PER_WORD];
  98 };
  99
 100 /* The entry for our multiplication cache/hash table.  */
 101 struct alg_hash_entry {
 102   /* The number we are multiplying by.  */
 103   unsigned HOST_WIDE_INT t;
 104
 105   /* The mode in which we are multiplying something by T.  */
 106   enum machine_mode mode;
 107
 108   /* The best multiplication algorithm for t.  */
 109   enum alg_code alg;
 110
 111   /* The cost of multiplication if ALG_CODE is not alg_impossible.
 112      Otherwise, the cost within which multiplication by T is
 113      impossible.  */
 114   struct mult_cost cost;
 115
 116   /* Optimized for speed? */
 117   bool speed;
 118 };
 119
 120 /* The number of cache/hash entries.  */
 121 #if HOST_BITS_PER_WIDE_INT == 64
 122 #define NUM_ALG_HASH_ENTRIES 1031
 123 #else
 124 #define NUM_ALG_HASH_ENTRIES 307
 125 #endif
 126
 127 #define NUM_MODE_INT (MAX_MODE_INT - MIN_MODE_INT + 1)
 128
 129 /* Target-dependent globals.  */
 130 struct target_expmed {
 131   /* Each entry of ALG_HASH caches alg_code for some integer.  This is
 132      actually a hash table.  If we have a collision, that the older
 133      entry is kicked out.  */
 134   struct alg_hash_entry x_alg_hash[NUM_ALG_HASH_ENTRIES];
 135
 136   /* True if x_alg_hash might already have been used.  */
 137   bool x_alg_hash_used_p;
 138
 139   /* Nonzero means divides or modulus operations are relatively cheap for
 140      powers of two, so don't use branches; emit the operation instead.
 141      Usually, this will mean that the MD file will emit non-branch
 142      sequences.  */
 143   bool x_sdiv_pow2_cheap[2][NUM_MACHINE_MODES];
 144   bool x_smod_pow2_cheap[2][NUM_MACHINE_MODES];
 145
 146   /* Cost of various pieces of RTL.  Note that some of these are indexed by
 147      shift count and some by mode.  */
 148   int x_zero_cost[2];
 149   int x_add_cost[2][NUM_MACHINE_MODES];
 150   int x_neg_cost[2][NUM_MACHINE_MODES];
 151   int x_shift_cost[2][NUM_MACHINE_MODES][MAX_BITS_PER_WORD];
 152   int x_shiftadd_cost[2][NUM_MACHINE_MODES][MAX_BITS_PER_WORD];
 153   int x_shiftsub0_cost[2][NUM_MACHINE_MODES][MAX_BITS_PER_WORD];
 154   int x_shiftsub1_cost[2][NUM_MACHINE_MODES][MAX_BITS_PER_WORD];
 155   int x_mul_cost[2][NUM_MACHINE_MODES];
 156   int x_sdiv_cost[2][NUM_MACHINE_MODES];
 157   int x_udiv_cost[2][NUM_MACHINE_MODES];
 158   int x_mul_widen_cost[2][NUM_MACHINE_MODES];
 159   int x_mul_highpart_cost[2][NUM_MACHINE_MODES];
 160
 161   /* Conversion costs are only defined between two scalar integer modes
 162      of different sizes.  The first machine mode is the destination mode,
 163      and the second is the source mode.  */
 164   int x_convert_cost[2][NUM_MODE_INT][NUM_MODE_INT];
 165 };
 166
 167 extern struct target_expmed default_target_expmed;
 168 #if SWITCHABLE_TARGET
 169 extern struct target_expmed *this_target_expmed;
 170 #else
 171 #define this_target_expmed (&default_target_expmed)
 172 #endif
 173
 174 #define alg_hash \
 175   (this_target_expmed->x_alg_hash)
 176 #define alg_hash_used_p \
 177   (this_target_expmed->x_alg_hash_used_p)
 178 #define sdiv_pow2_cheap \
 179   (this_target_expmed->x_sdiv_pow2_cheap)
 180 #define smod_pow2_cheap \
 181   (this_target_expmed->x_smod_pow2_cheap)
 182 #define zero_cost \
 183   (this_target_expmed->x_zero_cost)
 184 #define add_cost \
 185   (this_target_expmed->x_add_cost)
 186 #define neg_cost \
 187   (this_target_expmed->x_neg_cost)
 188 #define shift_cost \
 189   (this_target_expmed->x_shift_cost)
 190 #define shiftadd_cost \
 191   (this_target_expmed->x_shiftadd_cost)
 192 #define shiftsub0_cost \
 193   (this_target_expmed->x_shiftsub0_cost)
 194 #define shiftsub1_cost \
 195   (this_target_expmed->x_shiftsub1_cost)
 196 #define mul_cost \
 197   (this_target_expmed->x_mul_cost)
 198 #define sdiv_cost \
 199   (this_target_expmed->x_sdiv_cost)
 200 #define udiv_cost \
 201   (this_target_expmed->x_udiv_cost)
 202 #define mul_widen_cost \
 203   (this_target_expmed->x_mul_widen_cost)
 204 #define mul_highpart_cost \
 205   (this_target_expmed->x_mul_highpart_cost)
 206
 207 /* Set the COST for converting from FROM_MODE to TO_MODE when optimizing
 208    for SPEED.  */
 209
 210 static inline void
 211 set_convert_cost (enum machine_mode to_mode, enum machine_mode from_mode,
 212                   bool speed, int cost)
 213 {
 214   int to_idx, from_idx;
 215
 216   gcc_assert (to_mode >= MIN_MODE_INT
 217               && to_mode <= MAX_MODE_INT
 218               && from_mode >= MIN_MODE_INT
 219               && from_mode <= MAX_MODE_INT);
 220
 221   to_idx = to_mode - MIN_MODE_INT;
 222   from_idx = from_mode - MIN_MODE_INT;
 223   this_target_expmed->x_convert_cost[speed][to_idx][from_idx] = cost;
 224 }
 225
 226 /* Return the cost for converting from FROM_MODE to TO_MODE when optimizing
 227    for SPEED.  */
 228
 229 static inline int
 230 convert_cost (enum machine_mode to_mode, enum machine_mode from_mode,
 231               bool speed)
 232 {
 233   int to_idx, from_idx;
 234
 235   gcc_assert (to_mode >= MIN_MODE_INT
 236               && to_mode <= MAX_MODE_INT
 237               && from_mode >= MIN_MODE_INT
 238               && from_mode <= MAX_MODE_INT);
 239
 240   to_idx = to_mode - MIN_MODE_INT;
 241   from_idx = from_mode - MIN_MODE_INT;
 242   return this_target_expmed->x_convert_cost[speed][to_idx][from_idx];
 243 }
 244
 245 extern int mult_by_coeff_cost (HOST_WIDE_INT, enum machine_mode, bool);
 246 #endif