nsz Git - libfirm/blob - ir/ir/irarch.c

   1         /**
   2          * @file irarch.c
   3          * @date 28.9.2004
   4          * @author Sebastian Hack
   5          * @brief Machine dependent firm optimizations.
   6          *
   7          * $Id$
   8          */
   9
  10 #include <stdlib.h>
  11 #include <assert.h>
  12
  13 #include "irnode_t.h"
  14 #include "irgraph_t.h"
  15 #include "irmode_t.h"
  16 #include "iropt_t.h"
  17 #include "ircons_t.h"
  18 #include "irgmod.h"
  19 #include "irvrfy.h"
  20 #include "tv.h"
  21 #include "dbginfo_t.h"
  22 #include "iropt_dbg.h"
  23 #include "irflag_t.h"
  24 #include "firmstat.h"
  25 #include "ircons.h"
  26 #include "irarch.h"
  27 #include "firmstat.h"
  28
  29 #undef DEB
  30
  31 #define MAX_BITSTR 64
  32
  33 /** The params got from the factory in arch_dep_init(...). */
  34 static const arch_dep_params_t *params = NULL;
  35
  36 /** The bit mask, which optimizations to apply. */
  37 static arch_dep_opts_t opts;
  38
  39 void arch_dep_init(arch_dep_params_factory_t factory)
  40 {
  41         opts = arch_dep_none;
  42
  43         if(factory != NULL)
  44                 params = factory();
  45 }
  46
  47 void arch_dep_set_opts(arch_dep_opts_t the_opts) {
  48         opts = the_opts;
  49 }
  50
  51 ir_node *arch_dep_replace_mul_with_shifts(ir_node *irn)
  52 {
  53         ir_node *block = get_nodes_block(irn);
  54         ir_node *res = irn;
  55         ir_node *operand = NULL;
  56         ir_node *left, *right;
  57         ir_mode *mode = get_irn_mode(irn);
  58         tarval *tv = NULL;
  59
  60         /* If the architecture dependent optimizations were not initialized
  61                  or this optimization was not enabled. */
  62         if(params == NULL || (opts & arch_dep_mul_to_shift) == 0)
  63                 return irn;
  64
  65         if(is_ir_node(irn)
  66                         && get_irn_opcode(irn) == iro_Mul
  67                         && mode_is_int(mode)) {
  68
  69                 left = get_binop_left(irn);
  70                 right = get_binop_right(irn);
  71
  72                 /* Look, if one operand is a constant. */
  73                 if(get_irn_opcode(left) == iro_Const) {
  74                         tv = get_Const_tarval(left);
  75                         operand = right;
  76                 } else if(get_irn_opcode(right) == iro_Const) {
  77                         tv = get_Const_tarval(right);
  78                         operand = left;
  79                 }
  80
  81                 if(tv != NULL) {
  82                         int maximum_shifts = params->maximum_shifts;
  83                         int also_use_subs = params->also_use_subs;
  84                         int highest_shift_amount = params->highest_shift_amount;
  85
  86                         char *bitstr = get_tarval_bitpattern(tv);
  87                         char *p;
  88                         int i, last = 0;
  89                         int counter = 0;
  90                         int curr_bit;
  91                         int compr_len = 0;
  92                         char compr[MAX_BITSTR];
  93
  94                         int singleton;
  95                         int end_of_group;
  96                         int shift_with_sub[MAX_BITSTR] = { 0 };
  97                         int shift_without_sub[MAX_BITSTR] = { 0 };
  98                         int shift_with_sub_pos = 0;
  99                         int shift_without_sub_pos = 0;
 100
 101 #if DEB
 102                         {
 103                                 int val = (int) get_tarval_long(tv);
 104                                 fprintf(stderr, "Found mul with %d(%x) = ", val, val);
 105                                 for(p = bitstr; *p != '\0'; p++)
 106                                         printf("%c", *p);
 107                                 printf("\n");
 108                         }
 109 #endif
 110
 111                         for(p = bitstr; *p != '\0'; p++) {
 112                                 int bit = *p != '0';
 113
 114                                 switch(bit - last) {
 115                                         case -1:          // The last was 1 we are now at 0
 116                                         case 1:           // The last was 0 and we are now at 1
 117                                                 compr[compr_len++] = counter;
 118                                                 counter = 1;
 119                                                 break;
 120                                         default:
 121                                                 counter++;
 122                                 }
 123
 124                                 last = bit;
 125                         }
 126                         compr[compr_len++] = counter;
 127
 128
 129 #ifdef DEF
 130                         {
 131                                 const char *prefix = "";
 132                                 for(i = 0; i < compr_len; i++, prefix = ",")
 133                                         fprintf(stderr, "%s%d", prefix, compr[i]);
 134                                 fprintf("\n");
 135                         }
 136 #endif
 137
 138                         // Go over all recorded one groups.
 139                         curr_bit = compr[0];
 140
 141                         for(i = 1; i < compr_len; i = end_of_group + 2) {
 142                                 int j, zeros_in_group, ones_in_group;
 143
 144                                 ones_in_group = compr[i];
 145                                 zeros_in_group = 0;
 146
 147                                 // Scan for singular 0s in a sequence
 148                                 for(j = i + 1; j < compr_len && compr[j] == 1; j += 2) {
 149                                         zeros_in_group += 1;
 150                                         ones_in_group += (j + 1 < compr_len ? compr[j + 1] : 0);
 151                                 }
 152                                 end_of_group = j - 1;
 153
 154                                 if(zeros_in_group >= ones_in_group - 1)
 155                                         end_of_group = i;
 156
 157 #ifdef DEB
 158                                 fprintf(stderr, "  i:%d, eg:%d\n", i, end_of_group);
 159 #endif
 160
 161                                 singleton = compr[i] == 1 && i == end_of_group;
 162                                 for(j = i; j <= end_of_group; j += 2) {
 163                                         int curr_ones = compr[j];
 164                                         int biased_curr_bit = curr_bit + 1;
 165                                         int k;
 166
 167 #ifdef DEB
 168                                         fprintf(stderr, "    j:%d, ones:%d\n", j, curr_ones);
 169 #endif
 170
 171                                         // If this ones group is a singleton group (it has no
 172                                         // singleton zeros inside
 173                                         if(singleton)
 174                                                 shift_with_sub[shift_with_sub_pos++] = biased_curr_bit;
 175                                         else if(j == i)
 176                                                 shift_with_sub[shift_with_sub_pos++] = -biased_curr_bit;
 177
 178                                         for(k = 0; k < curr_ones; k++)
 179                                                 shift_without_sub[shift_without_sub_pos++] = biased_curr_bit + k;
 180
 181                                         curr_bit += curr_ones;
 182                                         biased_curr_bit = curr_bit + 1;
 183
 184                                         if(!singleton && j == end_of_group)
 185                                                 shift_with_sub[shift_with_sub_pos++] = biased_curr_bit;
 186                                         else if(j != end_of_group)
 187                                                 shift_with_sub[shift_with_sub_pos++] = -biased_curr_bit;
 188
 189                                         curr_bit += compr[j + 1];
 190                                 }
 191
 192                         }
 193
 194                         {
 195                                 int *shifts = shift_with_sub;
 196                                 int n = shift_with_sub_pos;
 197                                 int highest_shift_wide = 0;
 198                                 int highest_shift_seq = 0;
 199                                 int last_shift = 0;
 200
 201                                 /* If we may not use subs, or we can achive the same with adds,
 202                                          prefer adds. */
 203                                 if(!also_use_subs || shift_with_sub_pos >= shift_without_sub_pos) {
 204                                         shifts = shift_without_sub;
 205                                         n = shift_without_sub_pos;
 206                                 }
 207
 208                                 /* If the number of needed shifts exceeds the given maximum,
 209                                          use the Mul and exit. */
 210                                 if(n > maximum_shifts) {
 211 #ifdef DEB
 212                                         fprintf(stderr, "Only allowed %d shifts, but %d are needed\n",
 213                                                         maximum_shifts, n);
 214 #endif
 215                                         return irn;
 216                                 }
 217
 218                                 /* Compute the highest shift needed for both, the
 219                                          sequential and wide representations. */
 220                                 for(i = 0; i < n; i++) {
 221                                         int curr = abs(shifts[i]);
 222                                         int curr_seq = curr - last;
 223
 224                                         highest_shift_wide = curr > highest_shift_wide ? curr
 225                                                 : highest_shift_wide;
 226                                         highest_shift_seq = curr_seq > highest_shift_seq ? curr_seq
 227                                                 : highest_shift_seq;
 228
 229                                         last_shift = curr;
 230                                 }
 231
 232                                 /* If the highest shift amount is greater than the given limit,
 233                                          give back the Mul */
 234                                 if(highest_shift_seq > highest_shift_amount) {
 235 #ifdef DEB
 236                                         fprintf(stderr, "Shift argument %d exceeds maximum %d\n",
 237                                                         highest_shift_seq, highest_shift_amount);
 238 #endif
 239                                         return irn;
 240                                 }
 241
 242                                 /* If we have subs, we cannot do sequential. */
 243                                 if(1 /* also_use_subs */) {
 244                                         if(n > 0) {
 245                                                 ir_node *curr = NULL;
 246
 247                                                 i = n - 1;
 248
 249                                                 do {
 250                                                         int curr_shift = shifts[i];
 251                                                         int sub = curr_shift < 0;
 252                                                         int amount = abs(curr_shift) - 1;
 253                                                         ir_node *aux = operand;
 254
 255
 256                                                         assert(amount >= 0 && "What is a negative shift??");
 257
 258                                                         if(amount != 0) {
 259                                                                 tarval *shift_amount = new_tarval_from_long(amount, mode_Iu);
 260                                                                 ir_node *cnst = new_r_Const(current_ir_graph, block, mode_Iu, shift_amount);
 261                                                                 aux = new_r_Shl(current_ir_graph, block, operand, cnst, mode);
 262                                                         }
 263
 264                                                         if(curr) {
 265                                                                 if(sub)
 266                                                                         curr = new_r_Sub(current_ir_graph, block, curr, aux, mode);
 267                                                                 else
 268                                                                         curr = new_r_Add(current_ir_graph, block, curr, aux, mode);
 269                                                         } else
 270                                                                 curr = aux;
 271
 272                                                 } while(--i >= 0);
 273
 274                                                 res = curr;
 275                                         }
 276                                 }
 277
 278 #ifdef DEB
 279                                 {
 280                                         const char *prefix = "";
 281                                         for(i = 0; i < n; i++) {
 282                                                 fprintf(stderr, "%s%d", prefix, shifts[i]);
 283                                                 prefix = ", ";
 284                                         }
 285                                         fprintf(stderr, "\n");
 286                                 }
 287 #endif
 288
 289                         }
 290
 291                         if(bitstr)
 292                                 free(bitstr);
 293                 }
 294
 295         }
 296
 297         if (res != irn)
 298           stat_arch_dep_replace_mul_with_shifts(irn);
 299
 300         return res;
 301 }
 302
 303
 304 static const arch_dep_params_t default_params = {
 305         1, /* also use subs */
 306         4, /* maximum shifts */
 307         31 /* maximum shift amount */
 308 };
 309
 310 const arch_dep_params_t *arch_dep_default_factory(void) {
 311         return &default_params;
 312 }