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