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

   1 /*
   2  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Machine dependent Firm optimizations.
  23  * @date    28.9.2004
  24  * @author  Sebastian Hack, Michael Beck
  25  * @version $Id$
  26  */
  27 #ifdef HAVE_CONFIG_H
  28 # include "config.h"
  29 #endif
  30
  31 #ifdef HAVE_STDLIB_H
  32 # include <stdlib.h>
  33 #endif
  34
  35 #include <assert.h>
  36
  37 #include "irnode_t.h"
  38 #include "irgraph_t.h"
  39 #include "irmode_t.h"
  40 #include "iropt_t.h"
  41 #include "ircons_t.h"
  42 #include "irgmod.h"
  43 #include "irvrfy.h"
  44 #include "tv_t.h"
  45 #include "dbginfo_t.h"
  46 #include "iropt_dbg.h"
  47 #include "irflag_t.h"
  48 #include "irhooks.h"
  49 #include "ircons.h"
  50 #include "irarch.h"
  51
  52 #undef DEB
  53
  54 #define MAX_BITSTR 64
  55
  56 /* when we need verifying */
  57 #ifdef NDEBUG
  58 # define IRN_VRFY_IRG(res, irg)
  59 #else
  60 # define IRN_VRFY_IRG(res, irg)  irn_vrfy_irg(res, irg)
  61 #endif
  62
  63 /** The params got from the factory in arch_dep_init(...). */
  64 static const ir_settings_arch_dep_t *params = NULL;
  65
  66 /** The bit mask, which optimizations to apply. */
  67 static arch_dep_opts_t opts;
  68
  69 /* we need this new pseudo op */
  70 static ir_op *op_Mulh = NULL;
  71
  72 /**
  73  * construct a Mulh: Mulh(a,b) = (a * b) >> w, w is the with in bits of a, b
  74  */
  75 static ir_node *
  76 new_rd_Mulh (dbg_info *db, ir_graph *irg, ir_node *block,
  77        ir_node *op1, ir_node *op2, ir_mode *mode) {
  78         ir_node *in[2];
  79         ir_node *res;
  80
  81         in[0] = op1;
  82         in[1] = op2;
  83         res = new_ir_node(db, irg, block, op_Mulh, mode, 2, in);
  84         res = optimize_node(res);
  85         IRN_VRFY_IRG(res, irg);
  86         return res;
  87 }
  88
  89 ir_op *get_op_Mulh(void)  { return op_Mulh; }
  90
  91 void arch_dep_init(arch_dep_params_factory_t factory) {
  92         opts = arch_dep_none;
  93
  94         if (factory != NULL)
  95                 params = factory();
  96
  97         if (! op_Mulh) {
  98                 int mulh_opc = get_next_ir_opcode();
  99
 100                 /* create the Mulh operation */
 101                 op_Mulh = new_ir_op(mulh_opc, "Mulh",  op_pin_state_floats, irop_flag_commutative, oparity_binary, 0, 0, NULL);
 102         }
 103 }
 104
 105 void arch_dep_set_opts(arch_dep_opts_t the_opts) {
 106         opts = the_opts;
 107 }
 108
 109 /** check, whether a mode allows a Mulh instruction. */
 110 static int allow_Mulh(ir_mode *mode) {
 111         if (get_mode_size_bits(mode) > params->max_bits_for_mulh)
 112                 return 0;
 113         return (mode_is_signed(mode) && params->allow_mulhs) || (!mode_is_signed(mode) && params->allow_mulhu);
 114 }
 115
 116 /* Replace Muls with Shifts and Add/Subs. */
 117 ir_node *arch_dep_replace_mul_with_shifts(ir_node *irn) {
 118         ir_node *res = irn;
 119         ir_mode *mode = get_irn_mode(irn);
 120
 121         /* If the architecture dependent optimizations were not initialized
 122            or this optimization was not enabled. */
 123         if (params == NULL || (opts & arch_dep_mul_to_shift) == 0)
 124                 return irn;
 125
 126         if (is_Mul(irn) && mode_is_int(mode)) {
 127                 ir_node *block   = get_nodes_block(irn);
 128                 ir_node *left    = get_binop_left(irn);
 129                 ir_node *right   = get_binop_right(irn);
 130                 tarval *tv       = NULL;
 131                 ir_node *operand = NULL;
 132
 133                 /* Look, if one operand is a constant. */
 134                 if (is_Const(left)) {
 135                         tv = get_Const_tarval(left);
 136                         operand = right;
 137                 } else if (is_Const(right)) {
 138                         tv = get_Const_tarval(right);
 139                         operand = left;
 140                 }
 141
 142                 if (tv != NULL) {
 143                         int maximum_shifts = params->maximum_shifts;
 144                         int also_use_subs = params->also_use_subs;
 145                         int highest_shift_amount = params->highest_shift_amount;
 146
 147                         char *bitstr = get_tarval_bitpattern(tv);
 148                         char *p;
 149                         int i, last = 0;
 150                         int counter = 0;
 151                         int curr_bit;
 152                         int compr_len = 0;
 153                         char compr[MAX_BITSTR];
 154
 155                         int singleton;
 156                         int end_of_group;
 157                         int shift_with_sub[MAX_BITSTR] = { 0 };
 158                         int shift_without_sub[MAX_BITSTR] = { 0 };
 159                         int shift_with_sub_pos = 0;
 160                         int shift_without_sub_pos = 0;
 161
 162 #if DEB
 163                         {
 164                                 long val = get_tarval_long(tv);
 165                                 fprintf(stderr, "Found mul with %ld(%lx) = ", val, val);
 166                                 for(p = bitstr; *p != '\0'; p++)
 167                                         printf("%c", *p);
 168                                 printf("\n");
 169                         }
 170 #endif
 171
 172                         for (p = bitstr; *p != '\0'; p++) {
 173                                 int bit = *p != '0';
 174
 175                                 if (bit != last) {
 176                                         /* The last was 1 we are now at 0 OR
 177                                          * The last was 0 and we are now at 1 */
 178                                         compr[compr_len++] = counter;
 179                                         counter = 1;
 180                                 } else
 181                                         counter++;
 182
 183                                 last = bit;
 184                         }
 185                         compr[compr_len++] = counter;
 186
 187 #ifdef DEB
 188                         {
 189                                 const char *prefix = "";
 190                                 for(i = 0; i < compr_len; i++, prefix = ",")
 191                                         fprintf(stderr, "%s%d", prefix, compr[i]);
 192                                 fprintf("\n");
 193                         }
 194 #endif
 195
 196                         /* Go over all recorded one groups. */
 197                         curr_bit = compr[0];
 198
 199                         for(i = 1; i < compr_len; i = end_of_group + 2) {
 200                                 int j, zeros_in_group, ones_in_group;
 201
 202                                 ones_in_group = compr[i];
 203                                 zeros_in_group = 0;
 204
 205                                 /* Scan for singular 0s in a sequence. */
 206                                 for(j = i + 1; j < compr_len && compr[j] == 1; j += 2) {
 207                                         zeros_in_group += 1;
 208                                         ones_in_group += (j + 1 < compr_len ? compr[j + 1] : 0);
 209                                 }
 210                                 end_of_group = j - 1;
 211
 212                                 if(zeros_in_group >= ones_in_group - 1)
 213                                         end_of_group = i;
 214
 215 #ifdef DEB
 216                                 fprintf(stderr, "  i:%d, eg:%d\n", i, end_of_group);
 217 #endif
 218
 219                                 singleton = compr[i] == 1 && i == end_of_group;
 220                                 for(j = i; j <= end_of_group; j += 2) {
 221                                         int curr_ones = compr[j];
 222                                         int biased_curr_bit = curr_bit + 1;
 223                                         int k;
 224
 225 #ifdef DEB
 226                                         fprintf(stderr, "    j:%d, ones:%d\n", j, curr_ones);
 227 #endif
 228
 229                                         /* If this ones group is a singleton group (it has no
 230                                            singleton zeros inside. */
 231                                         if(singleton)
 232                                                 shift_with_sub[shift_with_sub_pos++] = biased_curr_bit;
 233                                         else if(j == i)
 234                                                 shift_with_sub[shift_with_sub_pos++] = -biased_curr_bit;
 235
 236                                         for(k = 0; k < curr_ones; k++)
 237                                                 shift_without_sub[shift_without_sub_pos++] = biased_curr_bit + k;
 238
 239                                         curr_bit += curr_ones;
 240                                         biased_curr_bit = curr_bit + 1;
 241
 242                                         if(!singleton && j == end_of_group)
 243                                                 shift_with_sub[shift_with_sub_pos++] = biased_curr_bit;
 244                                         else if(j != end_of_group)
 245                                                 shift_with_sub[shift_with_sub_pos++] = -biased_curr_bit;
 246
 247                                         curr_bit += compr[j + 1];
 248                                 }
 249                         }
 250
 251                         {
 252                                 int *shifts = shift_with_sub;
 253                                 int n = shift_with_sub_pos;
 254                                 int highest_shift_wide = 0;
 255                                 int highest_shift_seq = 0;
 256                                 int last_shift = 0;
 257
 258                                 /* If we may not use subs, or we can achieve the same with adds,
 259                                    prefer adds. */
 260                                 if(!also_use_subs || shift_with_sub_pos >= shift_without_sub_pos) {
 261                                         shifts = shift_without_sub;
 262                                         n = shift_without_sub_pos;
 263                                 }
 264
 265                                 /* If the number of needed shifts exceeds the given maximum,
 266                                    use the Mul and exit. */
 267                                 if(n > maximum_shifts) {
 268 #ifdef DEB
 269                                         fprintf(stderr, "Only allowed %d shifts, but %d are needed\n",
 270                                                 maximum_shifts, n);
 271 #endif
 272                                         goto end;
 273                                 }
 274
 275                                 /* Compute the highest shift needed for both, the
 276                                    sequential and wide representations. */
 277                                 for(i = 0; i < n; i++) {
 278                                         int curr = abs(shifts[i]);
 279                                         int curr_seq = curr - last;
 280
 281                                         highest_shift_wide = curr > highest_shift_wide ? curr : highest_shift_wide;
 282                                         highest_shift_seq = curr_seq > highest_shift_seq ? curr_seq : highest_shift_seq;
 283
 284                                         last_shift = curr;
 285                                 }
 286
 287                                 /* If the highest shift amount is greater than the given limit,
 288                                    give back the Mul */
 289                                 if(highest_shift_seq > highest_shift_amount) {
 290 #ifdef DEB
 291                                         fprintf(stderr, "Shift argument %d exceeds maximum %d\n",
 292                                                 highest_shift_seq, highest_shift_amount);
 293 #endif
 294                                         goto end;
 295                                 }
 296
 297                                 /* If we have subs, we cannot do sequential. */
 298                                 if(1 /* also_use_subs */) {
 299                                         if(n > 0) {
 300                                                 ir_node *curr = NULL;
 301
 302                                                 i = n - 1;
 303
 304                                                 do {
 305                                                         int curr_shift = shifts[i];
 306                                                         int sub = curr_shift < 0;
 307                                                         int amount = abs(curr_shift) - 1;
 308                                                         ir_node *aux = operand;
 309
 310                                                         assert(amount >= 0 && "What is a negative shift??");
 311
 312                                                         if (amount != 0) {
 313                                                                 ir_node *cnst = new_r_Const_long(current_ir_graph, block, mode_Iu, amount);
 314                                                                 aux = new_r_Shl(current_ir_graph, block, operand, cnst, mode);
 315                                                         }
 316
 317                                                         if (curr) {
 318                                                                 if (sub)
 319                                                                         curr = new_r_Sub(current_ir_graph, block, curr, aux, mode);
 320                                                                 else
 321                                                                         curr = new_r_Add(current_ir_graph, block, curr, aux, mode);
 322                                                         } else
 323                                                                 curr = aux;
 324
 325                                                 } while(--i >= 0);
 326
 327                                                 res = curr;
 328                                         }
 329                                 }
 330
 331 #ifdef DEB
 332                                 {
 333                                         const char *prefix = "";
 334                                         for (i = 0; i < n; ++i) {
 335                                                 fprintf(stderr, "%s%d", prefix, shifts[i]);
 336                                                 prefix = ", ";
 337                                         }
 338                                         fprintf(stderr, "\n");
 339                                 }
 340 #endif
 341
 342                         }
 343
 344 end:
 345                         if(bitstr)
 346                                 free(bitstr);
 347                 }
 348
 349         }
 350
 351         if (res != irn)
 352                 hook_arch_dep_replace_mul_with_shifts(irn);
 353
 354         return res;
 355 }
 356
 357 /**
 358  * calculated the ld2 of a tarval if tarval is 2^n, else returns -1.
 359  */
 360 static int tv_ld2(tarval *tv, int bits) {
 361         int i, k = 0, num;
 362
 363         for (num = i = 0; i < bits; ++i) {
 364                 unsigned char v = get_tarval_sub_bits(tv, i);
 365
 366                 if (v) {
 367                         int j;
 368
 369                         for (j = 0; j < 8; ++j)
 370                                 if ((1 << j) & v) {
 371                                         ++num;
 372                                         k = 8 * i + j;
 373                                 }
 374                 }
 375         }
 376         if (num == 1)
 377                 return k;
 378         return -1;
 379 }
 380
 381
 382 /* for shorter lines */
 383 #define ABS(a)    tarval_abs(a)
 384 #define NEG(a)    tarval_neg(a)
 385 #define NOT(a)    tarval_not(a)
 386 #define SHL(a, b) tarval_shl(a, b)
 387 #define SHR(a, b) tarval_shr(a, b)
 388 #define ADD(a, b) tarval_add(a, b)
 389 #define SUB(a, b) tarval_sub(a, b)
 390 #define MUL(a, b) tarval_mul(a, b)
 391 #define DIV(a, b) tarval_div(a, b)
 392 #define MOD(a, b) tarval_mod(a, b)
 393 #define CMP(a, b) tarval_cmp(a, b)
 394 #define CNV(a, m) tarval_convert_to(a, m)
 395 #define ONE(m)    get_mode_one(m)
 396 #define ZERO(m)   get_mode_null(m)
 397
 398 /** The result of a the magic() function. */
 399 struct ms {
 400         tarval *M;        /**< magic number */
 401         int s;            /**< shift amount */
 402         int need_add;     /**< an additional add is needed */
 403         int need_sub;     /**< an additional sub is needed */
 404 };
 405
 406 /**
 407  * Signed division by constant d: calculate the Magic multiplier M and the shift amount s
 408  *
 409  * see Hacker's Delight: 10-6 Integer Division by Constants: Incorporation into a Compiler
 410  */
 411 static struct ms magic(tarval *d) {
 412         ir_mode *mode   = get_tarval_mode(d);
 413         ir_mode *u_mode = find_unsigned_mode(mode);
 414         int bits        = get_mode_size_bits(u_mode);
 415         int p;
 416         tarval *ad, *anc, *delta, *q1, *r1, *q2, *r2, *t;     /* unsigned */
 417         pn_Cmp d_cmp, M_cmp;
 418
 419         tarval *bits_minus_1, *two_bits_1;
 420
 421         struct ms mag;
 422
 423         tarval_int_overflow_mode_t rem = tarval_get_integer_overflow_mode();
 424
 425         /* we need overflow mode to work correctly */
 426         tarval_set_integer_overflow_mode(TV_OVERFLOW_WRAP);
 427
 428         /* 2^(bits-1) */
 429         bits_minus_1 = new_tarval_from_long(bits - 1, u_mode);
 430         two_bits_1   = SHL(get_mode_one(u_mode), bits_minus_1);
 431
 432         ad  = CNV(ABS(d), u_mode);
 433         t   = ADD(two_bits_1, SHR(CNV(d, u_mode), bits_minus_1));
 434         anc = SUB(SUB(t, ONE(u_mode)), MOD(t, ad));   /* Absolute value of nc */
 435         p   = bits - 1;                               /* Init: p */
 436         q1  = DIV(two_bits_1, anc);                   /* Init: q1 = 2^p/|nc| */
 437         r1  = SUB(two_bits_1, MUL(q1, anc));          /* Init: r1 = rem(2^p, |nc|) */
 438         q2  = DIV(two_bits_1, ad);                    /* Init: q2 = 2^p/|d| */
 439         r2  = SUB(two_bits_1, MUL(q2, ad));           /* Init: r2 = rem(2^p, |d|) */
 440
 441         do {
 442                 ++p;
 443                 q1 = ADD(q1, q1);                           /* Update q1 = 2^p/|nc| */
 444                 r1 = ADD(r1, r1);                           /* Update r1 = rem(2^p, |nc|) */
 445
 446                 if (CMP(r1, anc) & pn_Cmp_Ge) {
 447                         q1 = ADD(q1, ONE(u_mode));
 448                         r1 = SUB(r1, anc);
 449                 }
 450
 451                 q2 = ADD(q2, q2);                           /* Update q2 = 2^p/|d| */
 452                 r2 = ADD(r2, r2);                           /* Update r2 = rem(2^p, |d|) */
 453
 454                 if (CMP(r2, ad) & pn_Cmp_Ge) {
 455                         q2 = ADD(q2, ONE(u_mode));
 456                         r2 = SUB(r2, ad);
 457                 }
 458
 459                 delta = SUB(ad, r2);
 460         } while (CMP(q1, delta) & pn_Cmp_Lt || (CMP(q1, delta) & pn_Cmp_Eq && CMP(r1, ZERO(u_mode)) & pn_Cmp_Eq));
 461
 462         d_cmp = CMP(d, ZERO(mode));
 463
 464         if (d_cmp & pn_Cmp_Ge)
 465                 mag.M = ADD(CNV(q2, mode), ONE(mode));
 466         else
 467                 mag.M = SUB(ZERO(mode), ADD(CNV(q2, mode), ONE(mode)));
 468
 469         M_cmp = CMP(mag.M, ZERO(mode));
 470
 471         mag.s = p - bits;
 472
 473         /* need an add if d > 0 && M < 0 */
 474         mag.need_add = d_cmp & pn_Cmp_Gt && M_cmp & pn_Cmp_Lt;
 475
 476         /* need a sub if d < 0 && M > 0 */
 477         mag.need_sub = d_cmp & pn_Cmp_Lt && M_cmp & pn_Cmp_Gt;
 478
 479         tarval_set_integer_overflow_mode(rem);
 480
 481         return mag;
 482 }
 483
 484 /** The result of the magicu() function. */
 485 struct mu {
 486         tarval *M;        /**< magic add constant */
 487         int s;            /**< shift amount */
 488         int need_add;     /**< add indicator */
 489 };
 490
 491 /**
 492  * Unsigned division by constant d: calculate the Magic multiplier M and the shift amount s
 493  *
 494  * see Hacker's Delight: 10-10 Integer Division by Constants: Incorporation into a Compiler (Unsigned)
 495  */
 496 static struct mu magicu(tarval *d) {
 497         ir_mode *mode   = get_tarval_mode(d);
 498         int bits        = get_mode_size_bits(mode);
 499         int p;
 500         tarval *nc, *delta, *q1, *r1, *q2, *r2;
 501         tarval *bits_minus_1, *two_bits_1, *seven_ff;
 502
 503         struct mu magu;
 504
 505         tarval_int_overflow_mode_t rem = tarval_get_integer_overflow_mode();
 506
 507         /* we need overflow mode to work correctly */
 508         tarval_set_integer_overflow_mode(TV_OVERFLOW_WRAP);
 509
 510         bits_minus_1 = new_tarval_from_long(bits - 1, mode);
 511         two_bits_1   = SHL(get_mode_one(mode), bits_minus_1);
 512         seven_ff     = SUB(two_bits_1, ONE(mode));
 513
 514         magu.need_add = 0;                            /* initialize the add indicator */
 515         nc = SUB(NEG(ONE(mode)), MOD(NEG(d), d));
 516         p  = bits - 1;                                /* Init: p */
 517         q1 = DIV(two_bits_1, nc);                     /* Init: q1 = 2^p/nc */
 518         r1 = SUB(two_bits_1, MUL(q1, nc));            /* Init: r1 = rem(2^p, nc) */
 519         q2 = DIV(seven_ff, d);                        /* Init: q2 = (2^p - 1)/d */
 520         r2 = SUB(seven_ff, MUL(q2, d));               /* Init: r2 = rem(2^p - 1, d) */
 521
 522         do {
 523                 ++p;
 524                 if (CMP(r1, SUB(nc, r1)) & pn_Cmp_Ge) {
 525                         q1 = ADD(ADD(q1, q1), ONE(mode));
 526                         r1 = SUB(ADD(r1, r1), nc);
 527                 }
 528                 else {
 529                         q1 = ADD(q1, q1);
 530                         r1 = ADD(r1, r1);
 531                 }
 532
 533                 if (CMP(ADD(r2, ONE(mode)), SUB(d, r2)) & pn_Cmp_Ge) {
 534                         if (CMP(q2, seven_ff) & pn_Cmp_Ge)
 535                                 magu.need_add = 1;
 536
 537                         q2 = ADD(ADD(q2, q2), ONE(mode));
 538                         r2 = SUB(ADD(ADD(r2, r2), ONE(mode)), d);
 539                 }
 540                 else {
 541                         if (CMP(q2, two_bits_1) & pn_Cmp_Ge)
 542                                 magu.need_add = 1;
 543
 544                         q2 = ADD(q2, q2);
 545                         r2 = ADD(ADD(r2, r2), ONE(mode));
 546                 }
 547                 delta = SUB(SUB(d, ONE(mode)), r2);
 548         } while (p < 2*bits &&
 549                 (CMP(q1, delta) & pn_Cmp_Lt || (CMP(q1, delta) & pn_Cmp_Eq && CMP(r1, ZERO(mode)) & pn_Cmp_Eq)));
 550
 551         magu.M = ADD(q2, ONE(mode));                       /* Magic number */
 552         magu.s = p - bits;                                 /* and shift amount */
 553
 554         tarval_set_integer_overflow_mode(rem);
 555
 556         return magu;
 557 }
 558
 559 /**
 560  * Build the Mulh replacement code for n / tv.
 561  *
 562  * Note that 'div' might be a mod or DivMod operation as well
 563  */
 564 static ir_node *replace_div_by_mulh(ir_node *div, tarval *tv) {
 565         dbg_info *dbg  = get_irn_dbg_info(div);
 566         ir_node *n     = get_binop_left(div);
 567         ir_node *block = get_irn_n(div, -1);
 568         ir_mode *mode  = get_irn_mode(n);
 569         int bits       = get_mode_size_bits(mode);
 570         ir_node *q, *t, *c;
 571
 572         /* Beware: do not transform bad code */
 573         if (is_Bad(n) || is_Bad(block))
 574                 return div;
 575
 576         if (mode_is_signed(mode)) {
 577                 struct ms mag = magic(tv);
 578
 579                 /* generate the Mulh instruction */
 580                 c = new_r_Const(current_ir_graph, block, mode, mag.M);
 581                 q = new_rd_Mulh(dbg, current_ir_graph, block, n, c, mode);
 582
 583                 /* do we need an Add or Sub */
 584                 if (mag.need_add)
 585                         q = new_rd_Add(dbg, current_ir_graph, block, q, n, mode);
 586                 else if (mag.need_sub)
 587                         q = new_rd_Sub(dbg, current_ir_graph, block, q, n, mode);
 588
 589                 /* Do we need the shift */
 590                 if (mag.s > 0) {
 591                         c = new_r_Const_long(current_ir_graph, block, mode_Iu, mag.s);
 592                         q    = new_rd_Shrs(dbg, current_ir_graph, block, q, c, mode);
 593                 }
 594
 595                 /* final */
 596                 c = new_r_Const_long(current_ir_graph, block, mode_Iu, bits-1);
 597                 t = new_rd_Shr(dbg, current_ir_graph, block, q, c, mode);
 598
 599                 q = new_rd_Add(dbg, current_ir_graph, block, q, t, mode);
 600         } else {
 601                 struct mu mag = magicu(tv);
 602                 ir_node *c;
 603
 604                 /* generate the Mulh instruction */
 605                 c = new_r_Const(current_ir_graph, block, mode, mag.M);
 606                 q    = new_rd_Mulh(dbg, current_ir_graph, block, n, c, mode);
 607
 608                 if (mag.need_add) {
 609                         if (mag.s > 0) {
 610                                 /* use the GM scheme */
 611                                 t = new_rd_Sub(dbg, current_ir_graph, block, n, q, mode);
 612
 613                                 c = new_r_Const(current_ir_graph, block, mode_Iu, get_mode_one(mode_Iu));
 614                                 t = new_rd_Shr(dbg, current_ir_graph, block, t, c, mode);
 615
 616                                 t = new_rd_Add(dbg, current_ir_graph, block, t, q, mode);
 617
 618                                 c = new_r_Const_long(current_ir_graph, block, mode_Iu, mag.s-1);
 619                                 q = new_rd_Shr(dbg, current_ir_graph, block, t, c, mode);
 620                         } else {
 621                                 /* use the default scheme */
 622                                 q = new_rd_Add(dbg, current_ir_graph, block, q, n, mode);
 623                         }
 624                 } else if (mag.s > 0) { /* default scheme, shift needed */
 625                         c = new_r_Const_long(current_ir_graph, block, mode_Iu, mag.s);
 626                         q = new_rd_Shr(dbg, current_ir_graph, block, q, c, mode);
 627                 }
 628         }
 629         return q;
 630 }
 631
 632 /* Replace Divs with Shifts and Add/Subs and Mulh. */
 633 ir_node *arch_dep_replace_div_by_const(ir_node *irn) {
 634         ir_node *res  = irn;
 635
 636         /* If the architecture dependent optimizations were not initialized
 637         or this optimization was not enabled. */
 638         if (params == NULL || (opts & arch_dep_div_by_const) == 0)
 639                 return irn;
 640
 641         if (get_irn_opcode(irn) == iro_Div) {
 642                 ir_node *c = get_Div_right(irn);
 643                 ir_node *block, *left;
 644                 ir_mode *mode;
 645                 tarval *tv, *ntv;
 646                 dbg_info *dbg;
 647                 int n, bits;
 648                 int k, n_flag;
 649
 650                 if (get_irn_op(c) != op_Const)
 651                         return irn;
 652
 653                 tv = get_Const_tarval(c);
 654
 655                 /* check for division by zero */
 656                 if (classify_tarval(tv) == TV_CLASSIFY_NULL)
 657                         return irn;
 658
 659                 left  = get_Div_left(irn);
 660                 mode  = get_irn_mode(left);
 661                 block = get_irn_n(irn, -1);
 662                 dbg   = get_irn_dbg_info(irn);
 663
 664                 bits = get_mode_size_bits(mode);
 665                 n    = (bits + 7) / 8;
 666
 667                 k = -1;
 668                 if (mode_is_signed(mode)) {
 669                         /* for signed divisions, the algorithm works for a / -2^k by negating the result */
 670                         ntv = tarval_neg(tv);
 671                         n_flag = 1;
 672                         k = tv_ld2(ntv, n);
 673                 }
 674
 675                 if (k < 0) {
 676                         n_flag = 0;
 677                         k = tv_ld2(tv, n);
 678                 }
 679
 680                 if (k >= 0) { /* division by 2^k or -2^k */
 681                         if (mode_is_signed(mode)) {
 682                                 ir_node *k_node;
 683                                 ir_node *curr = left;
 684
 685                                 if (k != 1) {
 686                                         k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k - 1);
 687                                         curr   = new_rd_Shrs(dbg, current_ir_graph, block, left, k_node, mode);
 688                                 }
 689
 690                                 k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, bits - k);
 691                                 curr   = new_rd_Shr(dbg, current_ir_graph, block, curr, k_node, mode);
 692
 693                                 curr   = new_rd_Add(dbg, current_ir_graph, block, left, curr, mode);
 694
 695                                 k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k);
 696                                 res    = new_rd_Shrs(dbg, current_ir_graph, block, curr, k_node, mode);
 697
 698                                 if (n_flag) { /* negate the result */
 699                                         ir_node *k_node;
 700
 701                                         k_node = new_r_Const(current_ir_graph, block, mode, get_mode_null(mode));
 702                                         res = new_rd_Sub(dbg, current_ir_graph, block, k_node, res, mode);
 703                                 }
 704                         } else {      /* unsigned case */
 705                                 ir_node *k_node;
 706
 707                                 k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k);
 708                                 res    = new_rd_Shr(dbg, current_ir_graph, block, left, k_node, mode);
 709                         }
 710                 } else {
 711                         /* other constant */
 712                         if (allow_Mulh(mode))
 713                                 res = replace_div_by_mulh(irn, tv);
 714                 }
 715         }
 716
 717         if (res != irn)
 718                 hook_arch_dep_replace_division_by_const(irn);
 719
 720         return res;
 721 }
 722
 723 /* Replace Mods with Shifts and Add/Subs and Mulh. */
 724 ir_node *arch_dep_replace_mod_by_const(ir_node *irn) {
 725         ir_node *res  = irn;
 726
 727         /* If the architecture dependent optimizations were not initialized
 728            or this optimization was not enabled. */
 729         if (params == NULL || (opts & arch_dep_mod_by_const) == 0)
 730                 return irn;
 731
 732         if (get_irn_opcode(irn) == iro_Mod) {
 733                 ir_node *c = get_Mod_right(irn);
 734                 ir_node *block, *left;
 735                 ir_mode *mode;
 736                 tarval *tv, *ntv;
 737                 dbg_info *dbg;
 738                 int n, bits;
 739                 int k;
 740
 741                 if (get_irn_op(c) != op_Const)
 742                         return irn;
 743
 744                 tv = get_Const_tarval(c);
 745
 746                 /* check for division by zero */
 747                 if (classify_tarval(tv) == TV_CLASSIFY_NULL)
 748                         return irn;
 749
 750                 left  = get_Mod_left(irn);
 751                 mode  = get_irn_mode(left);
 752                 block = get_irn_n(irn, -1);
 753                 dbg   = get_irn_dbg_info(irn);
 754                 bits = get_mode_size_bits(mode);
 755                 n    = (bits + 7) / 8;
 756
 757                 k = -1;
 758                 if (mode_is_signed(mode)) {
 759                         /* for signed divisions, the algorithm works for a / -2^k by negating the result */
 760                         ntv = tarval_neg(tv);
 761                         k = tv_ld2(ntv, n);
 762                 }
 763
 764                 if (k < 0) {
 765                         k = tv_ld2(tv, n);
 766                 }
 767
 768                 if (k >= 0) {
 769                         /* division by 2^k or -2^k:
 770                          * we use "modulus" here, so x % y == x % -y that's why is no difference between the case 2^k and -2^k
 771                          */
 772                         if (mode_is_signed(mode)) {
 773                                 ir_node *k_node;
 774                                 ir_node *curr = left;
 775
 776                                 if (k != 1) {
 777                                         k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k - 1);
 778                                         curr   = new_rd_Shrs(dbg, current_ir_graph, block, left, k_node, mode);
 779                                 }
 780
 781                                 k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, bits - k);
 782                                 curr   = new_rd_Shr(dbg, current_ir_graph, block, curr, k_node, mode);
 783
 784                                 curr   = new_rd_Add(dbg, current_ir_graph, block, left, curr, mode);
 785
 786                                 k_node = new_r_Const_long(current_ir_graph, block, mode, (-1) << k);
 787                                 curr   = new_rd_And(dbg, current_ir_graph, block, curr, k_node, mode);
 788
 789                                 res    = new_rd_Sub(dbg, current_ir_graph, block, left, curr, mode);
 790                         } else {      /* unsigned case */
 791                                 ir_node *k_node;
 792
 793                                 k_node = new_r_Const_long(current_ir_graph, block, mode, (1 << k) - 1);
 794                                 res    = new_rd_And(dbg, current_ir_graph, block, left, k_node, mode);
 795                         }
 796                 } else {
 797                         /* other constant */
 798                         if (allow_Mulh(mode)) {
 799                                 res = replace_div_by_mulh(irn, tv);
 800
 801                                 res = new_rd_Mul(dbg, current_ir_graph, block, res, c, mode);
 802
 803                                 /* res = arch_dep_mul_to_shift(res); */
 804
 805                                 res = new_rd_Sub(dbg, current_ir_graph, block, left, res, mode);
 806                         }
 807                 }
 808         }
 809
 810         if (res != irn)
 811                 hook_arch_dep_replace_division_by_const(irn);
 812
 813         return res;
 814 }
 815
 816 /* Replace DivMods with Shifts and Add/Subs and Mulh. */
 817 void arch_dep_replace_divmod_by_const(ir_node **div, ir_node **mod, ir_node *irn) {
 818         *div = *mod = NULL;
 819
 820         /* If the architecture dependent optimizations were not initialized
 821            or this optimization was not enabled. */
 822         if (params == NULL ||
 823                 ((opts & (arch_dep_div_by_const|arch_dep_mod_by_const)) != (arch_dep_div_by_const|arch_dep_mod_by_const)))
 824                 return;
 825
 826         if (get_irn_opcode(irn) == iro_DivMod) {
 827                 ir_node *c = get_DivMod_right(irn);
 828                 ir_node *block, *left;
 829                 ir_mode *mode;
 830                 tarval *tv, *ntv;
 831                 dbg_info *dbg;
 832                 int n, bits;
 833                 int k, n_flag;
 834
 835                 if (get_irn_op(c) != op_Const)
 836                         return;
 837
 838                 tv = get_Const_tarval(c);
 839
 840                 /* check for division by zero */
 841                 if (classify_tarval(tv) == TV_CLASSIFY_NULL)
 842                         return;
 843
 844                 left  = get_DivMod_left(irn);
 845                 mode  = get_irn_mode(left);
 846                 block = get_irn_n(irn, -1);
 847                 dbg   = get_irn_dbg_info(irn);
 848
 849                 bits = get_mode_size_bits(mode);
 850                 n    = (bits + 7) / 8;
 851
 852                 k = -1;
 853                 if (mode_is_signed(mode)) {
 854                         /* for signed divisions, the algorithm works for a / -2^k by negating the result */
 855                         ntv = tarval_neg(tv);
 856                         n_flag = 1;
 857                         k = tv_ld2(ntv, n);
 858                 }
 859
 860                 if (k < 0) {
 861                         n_flag = 0;
 862                         k = tv_ld2(tv, n);
 863                 }
 864
 865                 if (k >= 0) { /* division by 2^k or -2^k */
 866                         if (mode_is_signed(mode)) {
 867                                 ir_node *k_node, *c_k;
 868                                 ir_node *curr = left;
 869
 870                                 if (k != 1) {
 871                                         k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k - 1);
 872                                         curr   = new_rd_Shrs(dbg, current_ir_graph, block, left, k_node, mode);
 873                                 }
 874
 875                                 k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, bits - k);
 876                                 curr   = new_rd_Shr(dbg, current_ir_graph, block, curr, k_node, mode);
 877
 878                                 curr   = new_rd_Add(dbg, current_ir_graph, block, left, curr, mode);
 879
 880                                 c_k    = new_r_Const_long(current_ir_graph, block, mode_Iu, k);
 881
 882                                 *div   = new_rd_Shrs(dbg, current_ir_graph, block, curr, c_k, mode);
 883
 884                                 if (n_flag) { /* negate the div result */
 885                                         ir_node *k_node;
 886
 887                                         k_node = new_r_Const(current_ir_graph, block, mode, get_mode_null(mode));
 888                                         *div = new_rd_Sub(dbg, current_ir_graph, block, k_node, *div, mode);
 889                                 }
 890
 891                                 k_node = new_r_Const_long(current_ir_graph, block, mode, (-1) << k);
 892                                 curr   = new_rd_And(dbg, current_ir_graph, block, curr, k_node, mode);
 893
 894                                 *mod   = new_rd_Sub(dbg, current_ir_graph, block, left, curr, mode);
 895                         } else {      /* unsigned case */
 896                                 ir_node *k_node;
 897
 898                                 k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k);
 899                                 *div   = new_rd_Shr(dbg, current_ir_graph, block, left, k_node, mode);
 900
 901                                 k_node = new_r_Const_long(current_ir_graph, block, mode, (1 << k) - 1);
 902                                 *mod   = new_rd_And(dbg, current_ir_graph, block, left, k_node, mode);
 903                         }
 904                 } else {
 905                         /* other constant */
 906                         if (allow_Mulh(mode)) {
 907                                 ir_node *t;
 908
 909                                 *div = replace_div_by_mulh(irn, tv);
 910
 911                                 t    = new_rd_Mul(dbg, current_ir_graph, block, *div, c, mode);
 912
 913                                 /* t = arch_dep_mul_to_shift(t); */
 914
 915                                 *mod = new_rd_Sub(dbg, current_ir_graph, block, left, t, mode);
 916                         }
 917                 }
 918         }
 919
 920         if (*div)
 921                 hook_arch_dep_replace_division_by_const(irn);
 922 }
 923
 924
 925 static const ir_settings_arch_dep_t default_params = {
 926         1,  /* also use subs */
 927         4,  /* maximum shifts */
 928         31, /* maximum shift amount */
 929
 930         0,  /* allow Mulhs */
 931         0,  /* allow Mulus */
 932         32  /* Mulh allowed up to 32 bit */
 933 };
 934
 935 /* A default parameter factory for testing purposes. */
 936 const ir_settings_arch_dep_t *arch_dep_default_factory(void) {
 937         return &default_params;
 938 }