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 #include <stdlib.h>
  10 #include <assert.h>
  11
  12 #include "irnode_t.h"
  13 #include "irgraph_t.h"
  14 #include "irmode_t.h"
  15 #include "iropt_t.h"
  16 #include "ircons_t.h"
  17 #include "irgmod.h"
  18 #include "irvrfy.h"
  19 #include "tv.h"
  20 #include "dbginfo_t.h"
  21 #include "iropt_dbg.h"
  22 #include "irflag_t.h"
  23 #include "firmstat.h"
  24 #include "ircons.h"
  25 #include "irarch.h"
  26 #include "firmstat.h"
  27
  28 #undef DEB
  29
  30 #define MAX_BITSTR 64
  31
  32 /** The params got from the factory in arch_dep_init(...). */
  33 static const arch_dep_params_t *params = NULL;
  34
  35 /** The bit mask, which optimizations to apply. */
  36 static arch_dep_opts_t opts;
  37
  38 void arch_dep_init(arch_dep_params_factory_t factory)
  39 {
  40   opts = arch_dep_none;
  41
  42   if(factory != NULL)
  43     params = factory();
  44 }
  45
  46 void arch_dep_set_opts(arch_dep_opts_t the_opts) {
  47   opts = the_opts;
  48 }
  49
  50 ir_node *arch_dep_replace_mul_with_shifts(ir_node *irn)
  51 {
  52   ir_node *res = irn;
  53   ir_mode *mode = get_irn_mode(irn);
  54
  55   /* If the architecture dependent optimizations were not initialized
  56      or this optimization was not enabled. */
  57   if(params == NULL || (opts & arch_dep_mul_to_shift) == 0)
  58     return irn;
  59
  60   if(get_irn_opcode(irn) == iro_Mul && mode_is_int(mode)) {
  61     ir_node *block   = get_nodes_block(irn);
  62     ir_node *left    = get_binop_left(irn);
  63     ir_node *right   = get_binop_right(irn);
  64     tarval *tv       = NULL;
  65     ir_node *operand = NULL;
  66
  67     /* Look, if one operand is a constant. */
  68     if(get_irn_opcode(left) == iro_Const) {
  69       tv = get_Const_tarval(left);
  70       operand = right;
  71     } else if(get_irn_opcode(right) == iro_Const) {
  72       tv = get_Const_tarval(right);
  73       operand = left;
  74     }
  75
  76     if(tv != NULL) {
  77       int maximum_shifts = params->maximum_shifts;
  78       int also_use_subs = params->also_use_subs;
  79       int highest_shift_amount = params->highest_shift_amount;
  80
  81       char *bitstr = get_tarval_bitpattern(tv);
  82       char *p;
  83       int i, last = 0;
  84       int counter = 0;
  85       int curr_bit;
  86       int compr_len = 0;
  87       char compr[MAX_BITSTR];
  88
  89       int singleton;
  90       int end_of_group;
  91       int shift_with_sub[MAX_BITSTR] = { 0 };
  92       int shift_without_sub[MAX_BITSTR] = { 0 };
  93       int shift_with_sub_pos = 0;
  94       int shift_without_sub_pos = 0;
  95
  96 #if DEB
  97       {
  98         long val = get_tarval_long(tv);
  99         fprintf(stderr, "Found mul with %ld(%lx) = ", val, val);
 100         for(p = bitstr; *p != '\0'; p++)
 101           printf("%c", *p);
 102         printf("\n");
 103       }
 104 #endif
 105
 106       for(p = bitstr; *p != '\0'; p++) {
 107         int bit = *p != '0';
 108
 109         if (bit != last) {
 110           /* The last was 1 we are now at 0 OR
 111            * The last was 0 and we are now at 1 */
 112           compr[compr_len++] = counter;
 113           counter = 1;
 114         }
 115         else
 116           counter++;
 117
 118         last = bit;
 119       }
 120       compr[compr_len++] = counter;
 121
 122
 123 #ifdef DEB
 124       {
 125         const char *prefix = "";
 126         for(i = 0; i < compr_len; i++, prefix = ",")
 127           fprintf(stderr, "%s%d", prefix, compr[i]);
 128         fprintf("\n");
 129       }
 130 #endif
 131
 132       // Go over all recorded one groups.
 133       curr_bit = compr[0];
 134
 135       for(i = 1; i < compr_len; i = end_of_group + 2) {
 136         int j, zeros_in_group, ones_in_group;
 137
 138         ones_in_group = compr[i];
 139         zeros_in_group = 0;
 140
 141         // Scan for singular 0s in a sequence
 142         for(j = i + 1; j < compr_len && compr[j] == 1; j += 2) {
 143           zeros_in_group += 1;
 144           ones_in_group += (j + 1 < compr_len ? compr[j + 1] : 0);
 145         }
 146         end_of_group = j - 1;
 147
 148         if(zeros_in_group >= ones_in_group - 1)
 149           end_of_group = i;
 150
 151 #ifdef DEB
 152         fprintf(stderr, "  i:%d, eg:%d\n", i, end_of_group);
 153 #endif
 154
 155         singleton = compr[i] == 1 && i == end_of_group;
 156         for(j = i; j <= end_of_group; j += 2) {
 157           int curr_ones = compr[j];
 158           int biased_curr_bit = curr_bit + 1;
 159           int k;
 160
 161 #ifdef DEB
 162           fprintf(stderr, "    j:%d, ones:%d\n", j, curr_ones);
 163 #endif
 164
 165           // If this ones group is a singleton group (it has no
 166           // singleton zeros inside
 167           if(singleton)
 168             shift_with_sub[shift_with_sub_pos++] = biased_curr_bit;
 169           else if(j == i)
 170             shift_with_sub[shift_with_sub_pos++] = -biased_curr_bit;
 171
 172           for(k = 0; k < curr_ones; k++)
 173             shift_without_sub[shift_without_sub_pos++] = biased_curr_bit + k;
 174
 175           curr_bit += curr_ones;
 176           biased_curr_bit = curr_bit + 1;
 177
 178           if(!singleton && j == end_of_group)
 179             shift_with_sub[shift_with_sub_pos++] = biased_curr_bit;
 180           else if(j != end_of_group)
 181             shift_with_sub[shift_with_sub_pos++] = -biased_curr_bit;
 182
 183           curr_bit += compr[j + 1];
 184         }
 185
 186       }
 187
 188       {
 189         int *shifts = shift_with_sub;
 190         int n = shift_with_sub_pos;
 191         int highest_shift_wide = 0;
 192         int highest_shift_seq = 0;
 193         int last_shift = 0;
 194
 195         /* If we may not use subs, or we can achive the same with adds,
 196            prefer adds. */
 197         if(!also_use_subs || shift_with_sub_pos >= shift_without_sub_pos) {
 198           shifts = shift_without_sub;
 199           n = shift_without_sub_pos;
 200         }
 201
 202         /* If the number of needed shifts exceeds the given maximum,
 203            use the Mul and exit. */
 204         if(n > maximum_shifts) {
 205 #ifdef DEB
 206           fprintf(stderr, "Only allowed %d shifts, but %d are needed\n",
 207               maximum_shifts, n);
 208 #endif
 209           return irn;
 210         }
 211
 212         /* Compute the highest shift needed for both, the
 213            sequential and wide representations. */
 214         for(i = 0; i < n; i++) {
 215           int curr = abs(shifts[i]);
 216           int curr_seq = curr - last;
 217
 218           highest_shift_wide = curr > highest_shift_wide ? curr
 219             : highest_shift_wide;
 220           highest_shift_seq = curr_seq > highest_shift_seq ? curr_seq
 221             : highest_shift_seq;
 222
 223           last_shift = curr;
 224         }
 225
 226         /* If the highest shift amount is greater than the given limit,
 227            give back the Mul */
 228         if(highest_shift_seq > highest_shift_amount) {
 229 #ifdef DEB
 230           fprintf(stderr, "Shift argument %d exceeds maximum %d\n",
 231               highest_shift_seq, highest_shift_amount);
 232 #endif
 233           return irn;
 234         }
 235
 236         /* If we have subs, we cannot do sequential. */
 237         if(1 /* also_use_subs */) {
 238           if(n > 0) {
 239             ir_node *curr = NULL;
 240
 241             i = n - 1;
 242
 243             do {
 244               int curr_shift = shifts[i];
 245               int sub = curr_shift < 0;
 246               int amount = abs(curr_shift) - 1;
 247               ir_node *aux = operand;
 248
 249
 250               assert(amount >= 0 && "What is a negative shift??");
 251
 252               if(amount != 0) {
 253                 tarval *shift_amount = new_tarval_from_long(amount, mode_Iu);
 254                 ir_node *cnst = new_r_Const(current_ir_graph, block, mode_Iu, shift_amount);
 255                 aux = new_r_Shl(current_ir_graph, block, operand, cnst, mode);
 256               }
 257
 258               if(curr) {
 259                 if(sub)
 260                   curr = new_r_Sub(current_ir_graph, block, curr, aux, mode);
 261                 else
 262                   curr = new_r_Add(current_ir_graph, block, curr, aux, mode);
 263               } else
 264                 curr = aux;
 265
 266             } while(--i >= 0);
 267
 268             res = curr;
 269           }
 270         }
 271
 272 #ifdef DEB
 273         {
 274           const char *prefix = "";
 275           for(i = 0; i < n; i++) {
 276             fprintf(stderr, "%s%d", prefix, shifts[i]);
 277             prefix = ", ";
 278           }
 279           fprintf(stderr, "\n");
 280         }
 281 #endif
 282
 283       }
 284
 285       if(bitstr)
 286         free(bitstr);
 287     }
 288
 289   }
 290
 291   if (res != irn)
 292     stat_arch_dep_replace_mul_with_shifts(irn);
 293
 294   return res;
 295 }
 296
 297 ir_node *arch_dep_replace_div_with_shifts(ir_node *irn)
 298 {
 299   ir_node *res  = irn;
 300
 301   /* If the architecture dependent optimizations were not initialized
 302      or this optimization was not enabled. */
 303   if (params == NULL || (opts & arch_dep_div_to_shift) == 0)
 304     return irn;
 305
 306   if (get_irn_opcode(irn) == iro_Div) {
 307     ir_node *c = get_Div_right(irn);
 308     ir_node *block, *left;
 309     ir_mode *mode;
 310     tarval *tv;
 311     dbg_info *dbg;
 312     int n, bits;
 313     int i, k, num;
 314
 315     if (get_irn_op(c) != op_Const)
 316       return irn;
 317
 318     left  = get_Div_left(irn);
 319     mode  = get_irn_mode(left);
 320     block = get_nodes_block(irn);
 321     dbg   = get_irn_dbg_info(irn);
 322     tv    = get_Const_tarval(c);
 323
 324     bits = get_mode_size_bits(mode);
 325     n    = (bits + 7) / 8;
 326
 327     for (num = i = 0; i < n; ++i) {
 328       unsigned char v = get_tarval_sub_bits(tv, i);
 329
 330       if (v) {
 331         int j;
 332
 333         for (j = 0; j < 8; ++j)
 334           if ((1 << j) & v) {
 335             ++num;
 336             k = 8 * i + j;
 337           }
 338       }
 339     }
 340
 341     if (num == 1) { /* division by 2^k */
 342
 343       if (mode_is_signed(mode)) {
 344         ir_node *k_node;
 345         ir_node *curr = left;
 346
 347         if (k != 1) {
 348           k_node = new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(k - 1, mode_Iu));
 349           curr   = new_rd_Shrs(dbg, current_ir_graph, block, left, k_node, mode);
 350         }
 351
 352         k_node = new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(bits - k, mode_Iu));
 353         curr   = new_rd_Shr(dbg, current_ir_graph, block, curr, k_node, mode);
 354
 355         curr   = new_rd_Add(dbg, current_ir_graph, block, left, curr, mode);
 356
 357         k_node = new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(k, mode_Iu));
 358         res    = new_rd_Shrs(dbg, current_ir_graph, block, curr, k_node, mode);
 359       }
 360       else {      /* unsigned case */
 361         ir_node *k_node;
 362
 363         k_node = new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(k, mode_Iu));
 364         res    = new_rd_Shl(dbg, current_ir_graph, block, left, k_node, mode);
 365       }
 366     }
 367   }
 368
 369   if (res != irn)
 370     stat_arch_dep_replace_div_with_shifts(irn);
 371
 372   return res;
 373 }
 374
 375 ir_node *arch_dep_replace_mod_with_shifts(ir_node *irn)
 376 {
 377   ir_node *res  = irn;
 378
 379   /* If the architecture dependent optimizations were not initialized
 380      or this optimization was not enabled. */
 381   if (params == NULL || (opts & arch_dep_mod_to_shift) == 0)
 382     return irn;
 383
 384   if (get_irn_opcode(irn) == iro_Mod) {
 385     ir_node *c = get_Mod_right(irn);
 386     ir_node *block, *left;
 387     ir_mode *mode;
 388     tarval *tv;
 389     dbg_info *dbg;
 390     int n, bits;
 391     int i, k, num;
 392
 393     if (get_irn_op(c) != op_Const)
 394       return irn;
 395
 396     left  = get_Mod_left(irn);
 397     mode  = get_irn_mode(left);
 398     block = get_nodes_block(irn);
 399     dbg   = get_irn_dbg_info(irn);
 400     tv    = get_Const_tarval(c);
 401
 402     bits = get_mode_size_bits(mode);
 403     n    = (bits + 7) / 8;
 404
 405     for (num = i = 0; i < n; ++i) {
 406       unsigned char v = get_tarval_sub_bits(tv, i);
 407
 408       if (v) {
 409         int j;
 410
 411         for (j = 0; j < 8; ++j)
 412           if ((1 << j) & v) {
 413             ++num;
 414             k = 8 * i + j;
 415           }
 416       }
 417     }
 418
 419     if (num == 1) { /* remainder by 2^k */
 420
 421       if (mode_is_signed(mode)) {
 422         ir_node *k_node;
 423         ir_node *curr = left;
 424
 425         if (k != 1) {
 426           k_node = new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(k - 1, mode_Iu));
 427           curr   = new_rd_Shrs(dbg, current_ir_graph, block, left, k_node, mode);
 428         }
 429
 430         k_node = new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(bits - k, mode_Iu));
 431         curr   = new_rd_Shr(dbg, current_ir_graph, block, curr, k_node, mode);
 432
 433         curr   = new_rd_Add(dbg, current_ir_graph, block, left, curr, mode);
 434
 435         k_node = new_r_Const(current_ir_graph, block, mode, new_tarval_from_long((-1) << k, mode));
 436         curr   = new_rd_And(dbg, current_ir_graph, block, curr, k_node, mode);
 437
 438         res    = new_rd_Sub(dbg, current_ir_graph, block, left, curr, mode);
 439       }
 440       else {      /* unsigned case */
 441         ir_node *k_node;
 442
 443         k_node = new_r_Const(current_ir_graph, block, mode, new_tarval_from_long((1 << k) - 1, mode));
 444         res    = new_rd_And(dbg, current_ir_graph, block, left, k_node, mode);
 445       }
 446     }
 447   }
 448
 449   if (res != irn)
 450     stat_arch_dep_replace_mod_with_shifts(irn);
 451
 452   return res;
 453 }
 454
 455 void arch_dep_replace_divmod_with_shifts(ir_node **div, ir_node **mod, ir_node *irn)
 456 {
 457   *div = *mod = NULL;
 458
 459   /* If the architecture dependent optimizations were not initialized
 460      or this optimization was not enabled. */
 461   if (params == NULL ||
 462      (opts & (arch_dep_div_to_shift|arch_dep_mod_to_shift) != (arch_dep_div_to_shift|arch_dep_mod_to_shift)))
 463     return;
 464
 465   if (get_irn_opcode(irn) == iro_DivMod) {
 466     ir_node *c = get_DivMod_right(irn);
 467     ir_node *block, *left;
 468     ir_mode *mode;
 469     tarval *tv;
 470     dbg_info *dbg;
 471     int n, bits;
 472     int i, k, num;
 473
 474     if (get_irn_op(c) != op_Const)
 475       return;
 476
 477     left  = get_DivMod_left(irn);
 478     mode  = get_irn_mode(left);
 479     block = get_nodes_block(irn);
 480     dbg   = get_irn_dbg_info(irn);
 481     tv    = get_Const_tarval(c);
 482
 483     bits = get_mode_size_bits(mode);
 484     n    = (bits + 7) / 8;
 485
 486     for (num = i = 0; i < n; ++i) {
 487       unsigned char v = get_tarval_sub_bits(tv, i);
 488
 489       if (v) {
 490         int j;
 491
 492         for (j = 0; j < 8; ++j)
 493           if ((1 << j) & v) {
 494             ++num;
 495             k = 8 * i + j;
 496           }
 497       }
 498     }
 499
 500     if (num == 1) { /* division & remainder by 2^k */
 501
 502       if (mode_is_signed(mode)) {
 503         ir_node *k_node;
 504         ir_node *curr = left;
 505
 506         if (k != 1) {
 507           k_node = new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(k - 1, mode_Iu));
 508           curr   = new_rd_Shrs(dbg, current_ir_graph, block, left, k_node, mode);
 509         }
 510
 511         k_node = new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(bits - k, mode_Iu));
 512         curr   = new_rd_Shr(dbg, current_ir_graph, block, curr, k_node, mode);
 513
 514         curr   = new_rd_Add(dbg, current_ir_graph, block, left, curr, mode);
 515
 516         k_node = new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(k, mode_Iu));
 517         *div   = new_rd_Shrs(dbg, current_ir_graph, block, curr, k_node, mode);
 518
 519         k_node = new_r_Const(current_ir_graph, block, mode, new_tarval_from_long((-1) << k, mode));
 520         curr   = new_rd_And(dbg, current_ir_graph, block, curr, k_node, mode);
 521
 522         *mod   = new_rd_Sub(dbg, current_ir_graph, block, left, curr, mode);
 523       }
 524       else {      /* unsigned case */
 525         ir_node *k_node;
 526
 527         k_node = new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(k, mode_Iu));
 528         *div   = new_rd_Shl(dbg, current_ir_graph, block, left, k_node, mode);
 529
 530         k_node = new_r_Const(current_ir_graph, block, mode, new_tarval_from_long((1 << k) - 1, mode));
 531         *mod   = new_rd_And(dbg, current_ir_graph, block, left, k_node, mode);
 532       }
 533     }
 534   }
 535
 536   if (*div)
 537     stat_arch_dep_replace_DivMod_with_shifts(irn);
 538 }
 539
 540
 541 static const arch_dep_params_t default_params = {
 542   1, /* also use subs */
 543   4, /* maximum shifts */
 544   31 /* maximum shift amount */
 545 };
 546
 547 const arch_dep_params_t *arch_dep_default_factory(void) {
 548   return &default_params;
 549 }