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 /* Target-dependent globals. */ 128 struct target_expmed { 129 /* Each entry of ALG_HASH caches alg_code for some integer. This is 130 actually a hash table. If we have a collision, that the older 131 entry is kicked out. */ 132 struct alg_hash_entry x_alg_hash[NUM_ALG_HASH_ENTRIES]; 133 134 /* True if x_alg_hash might already have been used. */ 135 bool x_alg_hash_used_p; 136 137 /* Nonzero means divides or modulus operations are relatively cheap for 138 powers of two, so don't use branches; emit the operation instead. 139 Usually, this will mean that the MD file will emit non-branch 140 sequences. */ 141 bool x_sdiv_pow2_cheap[2][NUM_MACHINE_MODES]; 142 bool x_smod_pow2_cheap[2][NUM_MACHINE_MODES]; 143 144 /* Cost of various pieces of RTL. Note that some of these are indexed by 145 shift count and some by mode. */ 146 int x_zero_cost[2]; 147 int x_add_cost[2][NUM_MACHINE_MODES]; 148 int x_neg_cost[2][NUM_MACHINE_MODES]; 149 int x_shift_cost[2][NUM_MACHINE_MODES][MAX_BITS_PER_WORD]; 150 int x_shiftadd_cost[2][NUM_MACHINE_MODES][MAX_BITS_PER_WORD]; 151 int x_shiftsub0_cost[2][NUM_MACHINE_MODES][MAX_BITS_PER_WORD]; 152 int x_shiftsub1_cost[2][NUM_MACHINE_MODES][MAX_BITS_PER_WORD]; 153 int x_mul_cost[2][NUM_MACHINE_MODES]; 154 int x_sdiv_cost[2][NUM_MACHINE_MODES]; 155 int x_udiv_cost[2][NUM_MACHINE_MODES]; 156 int x_mul_widen_cost[2][NUM_MACHINE_MODES]; 157 int x_mul_highpart_cost[2][NUM_MACHINE_MODES]; 158 }; 159 160 extern struct target_expmed default_target_expmed; 161 #if SWITCHABLE_TARGET 162 extern struct target_expmed *this_target_expmed; 163 #else 164 #define this_target_expmed (&default_target_expmed) 165 #endif 166 167 #define alg_hash \ 168 (this_target_expmed->x_alg_hash) 169 #define alg_hash_used_p \ 170 (this_target_expmed->x_alg_hash_used_p) 171 #define sdiv_pow2_cheap \ 172 (this_target_expmed->x_sdiv_pow2_cheap) 173 #define smod_pow2_cheap \ 174 (this_target_expmed->x_smod_pow2_cheap) 175 #define zero_cost \ 176 (this_target_expmed->x_zero_cost) 177 #define add_cost \ 178 (this_target_expmed->x_add_cost) 179 #define neg_cost \ 180 (this_target_expmed->x_neg_cost) 181 #define shift_cost \ 182 (this_target_expmed->x_shift_cost) 183 #define shiftadd_cost \ 184 (this_target_expmed->x_shiftadd_cost) 185 #define shiftsub0_cost \ 186 (this_target_expmed->x_shiftsub0_cost) 187 #define shiftsub1_cost \ 188 (this_target_expmed->x_shiftsub1_cost) 189 #define mul_cost \ 190 (this_target_expmed->x_mul_cost) 191 #define sdiv_cost \ 192 (this_target_expmed->x_sdiv_cost) 193 #define udiv_cost \ 194 (this_target_expmed->x_udiv_cost) 195 #define mul_widen_cost \ 196 (this_target_expmed->x_mul_widen_cost) 197 #define mul_highpart_cost \ 198 (this_target_expmed->x_mul_highpart_cost) 199 200 #endif 201