irarch.c 27.1 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

Michael Beck's avatar
Michael Beck committed
20
21
22
/**
 * @file irarch.c
 * @date 28.9.2004
Michael Beck's avatar
Michael Beck committed
23
 * @author Sebastian Hack, Michael Beck
24
 * @brief Machine dependent Firm optimizations.
Michael Beck's avatar
Michael Beck committed
25
26
27
 *
 * $Id$
 */
Michael Beck's avatar
Michael Beck committed
28
29
30
31
32
33
34
35
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif

#ifdef HAVE_STDLIB_H
# include <stdlib.h>
#endif

36
37
38
39
40
41
42
43
44
#include <assert.h>

#include "irnode_t.h"
#include "irgraph_t.h"
#include "irmode_t.h"
#include "iropt_t.h"
#include "ircons_t.h"
#include "irgmod.h"
#include "irvrfy.h"
Michael Beck's avatar
Michael Beck committed
45
#include "tv_t.h"
46
47
48
#include "dbginfo_t.h"
#include "iropt_dbg.h"
#include "irflag_t.h"
49
#include "irhooks.h"
50
51
#include "ircons.h"
#include "irarch.h"
Daniel Grund's avatar
Daniel Grund committed
52
#include "irreflect.h"
53
54
55
56
57

#undef DEB

#define MAX_BITSTR 64

58
59
60
61
62
63
64
/* when we need verifying */
#ifdef NDEBUG
# define IRN_VRFY_IRG(res, irg)
#else
# define IRN_VRFY_IRG(res, irg)  irn_vrfy_irg(res, irg)
#endif

65
/** The params got from the factory in arch_dep_init(...). */
66
67
68
69
70
static const arch_dep_params_t *params = NULL;

/** The bit mask, which optimizations to apply. */
static arch_dep_opts_t opts;

71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/* we need this new pseudo op */
static ir_op *op_Mulh = NULL;

/**
 * construct a Mulh: Mulh(a,b) = (a * b) >> w, w is the with in bits of a, b
 */
static ir_node *
new_rd_Mulh (dbg_info *db, ir_graph *irg, ir_node *block,
       ir_node *op1, ir_node *op2, ir_mode *mode)
{
  ir_node *in[2];
  ir_node *res;

  in[0] = op1;
  in[1] = op2;
  res = new_ir_node(db, irg, block, op_Mulh, mode, 2, in);
  res = optimize_node(res);
  IRN_VRFY_IRG(res, irg);
  return res;
}

ir_op *get_op_Mulh(void)  { return op_Mulh; }

94
95
void arch_dep_init(arch_dep_params_factory_t factory)
{
Michael Beck's avatar
Michael Beck committed
96
  opts = arch_dep_none;
97

98
  if (factory != NULL)
Michael Beck's avatar
Michael Beck committed
99
    params = factory();
100

101
102
103
104
105
106
107
108
109
110
111
112
  if (! op_Mulh) {
    rflct_sig_t *sig;
    int mulh_opc = get_next_ir_opcode();

    /* create the Mulh operation */
    op_Mulh = new_ir_op(mulh_opc, "Mulh",  op_pin_state_floats, irop_flag_commutative, oparity_binary, 0, 0, NULL);
    sig = rflct_signature_allocate(1, 3);
    rflct_signature_set_arg(sig, 0, 0, "Res", RFLCT_MC(Int), 0, 0);
    rflct_signature_set_arg(sig, 1, 0, "Block", RFLCT_MC(BB), 0, 0);
    rflct_signature_set_arg(sig, 1, 1, "Op 0", RFLCT_MC(Int), 0, 0);
    rflct_signature_set_arg(sig, 1, 2, "Op 1", RFLCT_MC(Int), 0, 0);

113
    rflct_new_opcode(mulh_opc, "Mulh", 0);
114
    rflct_opcode_add_signature(mulh_opc, sig);
115
  }
116
117
118
}

void arch_dep_set_opts(arch_dep_opts_t the_opts) {
Michael Beck's avatar
Michael Beck committed
119
  opts = the_opts;
120
121
}

122
/** check, whether a mode allows a Mulh instruction. */
123
124
125
126
127
128
129
static int allow_Mulh(ir_mode *mode)
{
  if (get_mode_size_bits(mode) > params->max_bits_for_mulh)
    return 0;
  return (mode_is_signed(mode) && params->allow_mulhs) || (!mode_is_signed(mode) && params->allow_mulhu);
}

130
/* Replace Muls with Shifts and Add/Subs. */
131
132
ir_node *arch_dep_replace_mul_with_shifts(ir_node *irn)
{
Michael Beck's avatar
Michael Beck committed
133
134
135
136
137
  ir_node *res = irn;
  ir_mode *mode = get_irn_mode(irn);

  /* If the architecture dependent optimizations were not initialized
     or this optimization was not enabled. */
Michael Beck's avatar
Michael Beck committed
138
  if (params == NULL || (opts & arch_dep_mul_to_shift) == 0)
Michael Beck's avatar
Michael Beck committed
139
140
    return irn;

Michael Beck's avatar
Michael Beck committed
141
142
  if (get_irn_op(irn) == op_Mul && mode_is_int(mode)) {
    ir_node *block   = get_irn_n(irn, -1);
Michael Beck's avatar
Michael Beck committed
143
144
145
146
147
148
    ir_node *left    = get_binop_left(irn);
    ir_node *right   = get_binop_right(irn);
    tarval *tv       = NULL;
    ir_node *operand = NULL;

    /* Look, if one operand is a constant. */
Michael Beck's avatar
Michael Beck committed
149
    if (get_irn_opcode(left) == iro_Const) {
Michael Beck's avatar
Michael Beck committed
150
151
152
153
154
155
156
      tv = get_Const_tarval(left);
      operand = right;
    } else if(get_irn_opcode(right) == iro_Const) {
      tv = get_Const_tarval(right);
      operand = left;
    }

Michael Beck's avatar
Michael Beck committed
157
    if (tv != NULL) {
Michael Beck's avatar
Michael Beck committed
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
      int maximum_shifts = params->maximum_shifts;
      int also_use_subs = params->also_use_subs;
      int highest_shift_amount = params->highest_shift_amount;

      char *bitstr = get_tarval_bitpattern(tv);
      char *p;
      int i, last = 0;
      int counter = 0;
      int curr_bit;
      int compr_len = 0;
      char compr[MAX_BITSTR];

      int singleton;
      int end_of_group;
      int shift_with_sub[MAX_BITSTR] = { 0 };
      int shift_without_sub[MAX_BITSTR] = { 0 };
      int shift_with_sub_pos = 0;
      int shift_without_sub_pos = 0;
176
177

#if DEB
Michael Beck's avatar
Michael Beck committed
178
179
180
181
182
183
184
      {
        long val = get_tarval_long(tv);
        fprintf(stderr, "Found mul with %ld(%lx) = ", val, val);
        for(p = bitstr; *p != '\0'; p++)
          printf("%c", *p);
        printf("\n");
      }
185
186
#endif

Michael Beck's avatar
Michael Beck committed
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
      for(p = bitstr; *p != '\0'; p++) {
        int bit = *p != '0';

        if (bit != last) {
          /* The last was 1 we are now at 0 OR
           * The last was 0 and we are now at 1 */
          compr[compr_len++] = counter;
          counter = 1;
        }
        else
          counter++;

        last = bit;
      }
      compr[compr_len++] = counter;


#ifdef DEB
      {
        const char *prefix = "";
        for(i = 0; i < compr_len; i++, prefix = ",")
          fprintf(stderr, "%s%d", prefix, compr[i]);
        fprintf("\n");
      }
211
212
#endif

213
      /* Go over all recorded one groups. */
Michael Beck's avatar
Michael Beck committed
214
      curr_bit = compr[0];
215

Michael Beck's avatar
Michael Beck committed
216
217
      for(i = 1; i < compr_len; i = end_of_group + 2) {
        int j, zeros_in_group, ones_in_group;
218

Michael Beck's avatar
Michael Beck committed
219
220
        ones_in_group = compr[i];
        zeros_in_group = 0;
221

222
        /* Scan for singular 0s in a sequence. */
Michael Beck's avatar
Michael Beck committed
223
224
225
226
227
        for(j = i + 1; j < compr_len && compr[j] == 1; j += 2) {
          zeros_in_group += 1;
          ones_in_group += (j + 1 < compr_len ? compr[j + 1] : 0);
        }
        end_of_group = j - 1;
228

Michael Beck's avatar
Michael Beck committed
229
230
        if(zeros_in_group >= ones_in_group - 1)
          end_of_group = i;
231
232

#ifdef DEB
Michael Beck's avatar
Michael Beck committed
233
        fprintf(stderr, "  i:%d, eg:%d\n", i, end_of_group);
234
235
#endif

Michael Beck's avatar
Michael Beck committed
236
237
238
239
240
        singleton = compr[i] == 1 && i == end_of_group;
        for(j = i; j <= end_of_group; j += 2) {
          int curr_ones = compr[j];
          int biased_curr_bit = curr_bit + 1;
          int k;
241
242

#ifdef DEB
Michael Beck's avatar
Michael Beck committed
243
          fprintf(stderr, "    j:%d, ones:%d\n", j, curr_ones);
244
245
#endif

246
247
          /* If this ones group is a singleton group (it has no
             singleton zeros inside. */
Michael Beck's avatar
Michael Beck committed
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
          if(singleton)
            shift_with_sub[shift_with_sub_pos++] = biased_curr_bit;
          else if(j == i)
            shift_with_sub[shift_with_sub_pos++] = -biased_curr_bit;

          for(k = 0; k < curr_ones; k++)
            shift_without_sub[shift_without_sub_pos++] = biased_curr_bit + k;

          curr_bit += curr_ones;
          biased_curr_bit = curr_bit + 1;

          if(!singleton && j == end_of_group)
            shift_with_sub[shift_with_sub_pos++] = biased_curr_bit;
          else if(j != end_of_group)
            shift_with_sub[shift_with_sub_pos++] = -biased_curr_bit;

          curr_bit += compr[j + 1];
        }

      }

      {
        int *shifts = shift_with_sub;
        int n = shift_with_sub_pos;
        int highest_shift_wide = 0;
        int highest_shift_seq = 0;
        int last_shift = 0;

        /* If we may not use subs, or we can achive the same with adds,
           prefer adds. */
        if(!also_use_subs || shift_with_sub_pos >= shift_without_sub_pos) {
          shifts = shift_without_sub;
          n = shift_without_sub_pos;
        }

        /* If the number of needed shifts exceeds the given maximum,
           use the Mul and exit. */
        if(n > maximum_shifts) {
286
#ifdef DEB
Michael Beck's avatar
Michael Beck committed
287
288
          fprintf(stderr, "Only allowed %d shifts, but %d are needed\n",
              maximum_shifts, n);
289
#endif
Michael Beck's avatar
Michael Beck committed
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
          return irn;
        }

        /* Compute the highest shift needed for both, the
           sequential and wide representations. */
        for(i = 0; i < n; i++) {
          int curr = abs(shifts[i]);
          int curr_seq = curr - last;

          highest_shift_wide = curr > highest_shift_wide ? curr
            : highest_shift_wide;
          highest_shift_seq = curr_seq > highest_shift_seq ? curr_seq
            : highest_shift_seq;

          last_shift = curr;
        }

        /* If the highest shift amount is greater than the given limit,
           give back the Mul */
        if(highest_shift_seq > highest_shift_amount) {
310
#ifdef DEB
Michael Beck's avatar
Michael Beck committed
311
312
          fprintf(stderr, "Shift argument %d exceeds maximum %d\n",
              highest_shift_seq, highest_shift_amount);
313
#endif
Michael Beck's avatar
Michael Beck committed
314
315
          return irn;
        }
316

Michael Beck's avatar
Michael Beck committed
317
318
319
320
        /* If we have subs, we cannot do sequential. */
        if(1 /* also_use_subs */) {
          if(n > 0) {
            ir_node *curr = NULL;
321

Michael Beck's avatar
Michael Beck committed
322
            i = n - 1;
323

Michael Beck's avatar
Michael Beck committed
324
325
326
327
328
            do {
              int curr_shift = shifts[i];
              int sub = curr_shift < 0;
              int amount = abs(curr_shift) - 1;
              ir_node *aux = operand;
329

Michael Beck's avatar
Michael Beck committed
330
              assert(amount >= 0 && "What is a negative shift??");
331

Michael Beck's avatar
Michael Beck committed
332
              if (amount != 0) {
333
                ir_node *cnst = new_r_Const_long(current_ir_graph, block, mode_Iu, amount);
Michael Beck's avatar
Michael Beck committed
334
335
                aux = new_r_Shl(current_ir_graph, block, operand, cnst, mode);
              }
336

Michael Beck's avatar
Michael Beck committed
337
338
              if (curr) {
                if (sub)
Michael Beck's avatar
Michael Beck committed
339
340
341
342
343
                  curr = new_r_Sub(current_ir_graph, block, curr, aux, mode);
                else
                  curr = new_r_Add(current_ir_graph, block, curr, aux, mode);
              } else
                curr = aux;
344

Michael Beck's avatar
Michael Beck committed
345
            } while(--i >= 0);
346

Michael Beck's avatar
Michael Beck committed
347
348
349
            res = curr;
          }
        }
350
351

#ifdef DEB
Michael Beck's avatar
Michael Beck committed
352
353
        {
          const char *prefix = "";
Michael Beck's avatar
Michael Beck committed
354
          for (i = 0; i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
355
356
357
358
359
            fprintf(stderr, "%s%d", prefix, shifts[i]);
            prefix = ", ";
          }
          fprintf(stderr, "\n");
        }
360
361
#endif

Michael Beck's avatar
Michael Beck committed
362
363
364
365
366
      }

      if(bitstr)
        free(bitstr);
    }
367

Michael Beck's avatar
Michael Beck committed
368
  }
369

Michael Beck's avatar
Michael Beck committed
370
  if (res != irn)
371
    hook_arch_dep_replace_mul_with_shifts(irn);
372

Michael Beck's avatar
Michael Beck committed
373
374
  return res;
}
375

376
377
378
379
380
/**
 * calculated the ld2 of a tarval if tarval is 2^n, else returns -1.
 */
static int tv_ld2(tarval *tv, int bits)
{
Matthias Braun's avatar
Matthias Braun committed
381
  int i, k = 0, num;
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417

  for (num = i = 0; i < bits; ++i) {
    unsigned char v = get_tarval_sub_bits(tv, i);

    if (v) {
      int j;

      for (j = 0; j < 8; ++j)
        if ((1 << j) & v) {
          ++num;
          k = 8 * i + j;
        }
    }
  }
  if (num == 1)
    return k;
  return -1;
}


/* for shorter lines */
#define ABS(a)    tarval_abs(a)
#define NEG(a)    tarval_neg(a)
#define NOT(a)    tarval_not(a)
#define SHL(a, b) tarval_shl(a, b)
#define SHR(a, b) tarval_shr(a, b)
#define ADD(a, b) tarval_add(a, b)
#define SUB(a, b) tarval_sub(a, b)
#define MUL(a, b) tarval_mul(a, b)
#define DIV(a, b) tarval_div(a, b)
#define MOD(a, b) tarval_mod(a, b)
#define CMP(a, b) tarval_cmp(a, b)
#define CNV(a, m) tarval_convert_to(a, m)
#define ONE(m)    get_mode_one(m)
#define ZERO(m)   get_mode_null(m)

418
/** The result of a the magic() function. */
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
struct ms {
  tarval *M;        /**< magic number */
  int s;            /**< shift amount */
  int need_add;     /**< an additional add is needed */
  int need_sub;     /**< an additional sub is needed */
};

/**
 * Signed division by constant d: calculate the Magic multiplier M and the shift amount s
 *
 * see Hacker's Delight: 10-6 Integer Division by Constants: Incorporation into a Compiler
 */
static struct ms magic(tarval *d)
{
  ir_mode *mode   = get_tarval_mode(d);
  ir_mode *u_mode = find_unsigned_mode(mode);
  int bits        = get_mode_size_bits(u_mode);
  int p;
  tarval *ad, *anc, *delta, *q1, *r1, *q2, *r2, *t;     /* unsigned */
438
  pn_Cmp d_cmp, M_cmp;
439

440
441
  tarval *bits_minus_1, *two_bits_1;

442
443
  struct ms mag;

444
445
446
447
448
  tarval_int_overflow_mode_t rem = tarval_get_integer_overflow_mode();

  /* we need overflow mode to work correctly */
  tarval_set_integer_overflow_mode(TV_OVERFLOW_WRAP);

449
  /* 2^(bits-1) */
450
451
  bits_minus_1 = new_tarval_from_long(bits - 1, u_mode);
  two_bits_1   = SHL(get_mode_one(u_mode), bits_minus_1);
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466

  ad  = CNV(ABS(d), u_mode);
  t   = ADD(two_bits_1, SHR(CNV(d, u_mode), bits_minus_1));
  anc = SUB(SUB(t, ONE(u_mode)), MOD(t, ad));   /* Absolute value of nc */
  p   = bits - 1;                               /* Init: p */
  q1  = DIV(two_bits_1, anc);                   /* Init: q1 = 2^p/|nc| */
  r1  = SUB(two_bits_1, MUL(q1, anc));          /* Init: r1 = rem(2^p, |nc|) */
  q2  = DIV(two_bits_1, ad);                    /* Init: q2 = 2^p/|d| */
  r2  = SUB(two_bits_1, MUL(q2, ad));           /* Init: r2 = rem(2^p, |d|) */

  do {
    ++p;
    q1 = ADD(q1, q1);                           /* Update q1 = 2^p/|nc| */
    r1 = ADD(r1, r1);                           /* Update r1 = rem(2^p, |nc|) */

467
    if (CMP(r1, anc) & pn_Cmp_Ge) {
468
469
470
471
472
473
474
      q1 = ADD(q1, ONE(u_mode));
      r1 = SUB(r1, anc);
    }

    q2 = ADD(q2, q2);                           /* Update q2 = 2^p/|d| */
    r2 = ADD(r2, r2);                           /* Update r2 = rem(2^p, |d|) */

475
    if (CMP(r2, ad) & pn_Cmp_Ge) {
476
477
478
479
480
      q2 = ADD(q2, ONE(u_mode));
      r2 = SUB(r2, ad);
    }

    delta = SUB(ad, r2);
481
  } while (CMP(q1, delta) & pn_Cmp_Lt || (CMP(q1, delta) & pn_Cmp_Eq && CMP(r1, ZERO(u_mode)) & pn_Cmp_Eq));
482
483
484

  d_cmp = CMP(d, ZERO(mode));

485
  if (d_cmp & pn_Cmp_Ge)
486
487
488
489
490
491
492
493
494
    mag.M = ADD(CNV(q2, mode), ONE(mode));
  else
    mag.M = SUB(ZERO(mode), ADD(CNV(q2, mode), ONE(mode)));

  M_cmp = CMP(mag.M, ZERO(mode));

  mag.s = p - bits;

  /* need an add if d > 0 && M < 0 */
495
  mag.need_add = d_cmp & pn_Cmp_Gt && M_cmp & pn_Cmp_Lt;
496
497

  /* need a sub if d < 0 && M > 0 */
498
  mag.need_sub = d_cmp & pn_Cmp_Lt && M_cmp & pn_Cmp_Gt;
499

500
501
  tarval_set_integer_overflow_mode(rem);

502
503
504
  return mag;
}

505
/** The result of the magicu() function. */
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
struct mu {
  tarval *M;        /**< magic add constant */
  int s;            /**< shift amount */
  int need_add;     /**< add indicator */
};

/**
 * Unsigned division by constant d: calculate the Magic multiplier M and the shift amount s
 *
 * see Hacker's Delight: 10-10 Integer Division by Constants: Incorporation into a Compiler (Unsigned)
 */
static struct mu magicu(tarval *d)
{
  ir_mode *mode   = get_tarval_mode(d);
  int bits        = get_mode_size_bits(mode);
  int p;
  tarval *nc, *delta, *q1, *r1, *q2, *r2;
523
  tarval *bits_minus_1, *two_bits_1, *seven_ff;
524
525
526

  struct mu magu;

527
528
529
530
531
532
533
534
  tarval_int_overflow_mode_t rem = tarval_get_integer_overflow_mode();

  /* we need overflow mode to work correctly */
  tarval_set_integer_overflow_mode(TV_OVERFLOW_WRAP);

  bits_minus_1 = new_tarval_from_long(bits - 1, mode);
  two_bits_1   = SHL(get_mode_one(mode), bits_minus_1);
  seven_ff     = SUB(two_bits_1, ONE(mode));
535
536
537
538
539
540
541
542
543
544
545

  magu.need_add = 0;                            /* initialize the add indicator */
  nc = SUB(NEG(ONE(mode)), MOD(NEG(d), d));
  p  = bits - 1;                                /* Init: p */
  q1 = DIV(two_bits_1, nc);                     /* Init: q1 = 2^p/nc */
  r1 = SUB(two_bits_1, MUL(q1, nc));            /* Init: r1 = rem(2^p, nc) */
  q2 = DIV(seven_ff, d);                        /* Init: q2 = (2^p - 1)/d */
  r2 = SUB(seven_ff, MUL(q2, d));               /* Init: r2 = rem(2^p - 1, d) */

  do {
    ++p;
546
    if (CMP(r1, SUB(nc, r1)) & pn_Cmp_Ge) {
547
548
549
550
551
552
553
554
      q1 = ADD(ADD(q1, q1), ONE(mode));
      r1 = SUB(ADD(r1, r1), nc);
    }
    else {
      q1 = ADD(q1, q1);
      r1 = ADD(r1, r1);
    }

555
556
    if (CMP(ADD(r2, ONE(mode)), SUB(d, r2)) & pn_Cmp_Ge) {
      if (CMP(q2, seven_ff) & pn_Cmp_Ge)
557
558
559
560
561
562
        magu.need_add = 1;

      q2 = ADD(ADD(q2, q2), ONE(mode));
      r2 = SUB(ADD(ADD(r2, r2), ONE(mode)), d);
    }
    else {
563
      if (CMP(q2, two_bits_1) & pn_Cmp_Ge)
564
565
566
567
568
569
570
        magu.need_add = 1;

      q2 = ADD(q2, q2);
      r2 = ADD(ADD(r2, r2), ONE(mode));
    }
    delta = SUB(SUB(d, ONE(mode)), r2);
  } while (p < 2*bits &&
571
          (CMP(q1, delta) & pn_Cmp_Lt || (CMP(q1, delta) & pn_Cmp_Eq && CMP(r1, ZERO(mode)) & pn_Cmp_Eq)));
572
573
574
575

  magu.M = ADD(q2, ONE(mode));                       /* Magic number */
  magu.s = p - bits;                                 /* and shift amount */

576
577
  tarval_set_integer_overflow_mode(rem);

578
579
580
581
  return magu;
}

/**
582
 * Build the Mulh replacement code for n / tv.
583
 *
Michael Beck's avatar
Michael Beck committed
584
 * Note that 'div' might be a mod or DivMod operation as well
585
586
587
588
589
 */
static ir_node *replace_div_by_mulh(ir_node *div, tarval *tv)
{
  dbg_info *dbg  = get_irn_dbg_info(div);
  ir_node *n     = get_binop_left(div);
Michael Beck's avatar
Michael Beck committed
590
  ir_node *block = get_irn_n(div, -1);
591
592
593
594
  ir_mode *mode  = get_irn_mode(n);
  int bits       = get_mode_size_bits(mode);
  ir_node *q, *t, *c;

595
596
597
598
  /* Beware: do not transform bad code */
  if (is_Bad(n) || is_Bad(block))
    return div;

599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
  if (mode_is_signed(mode)) {
    struct ms mag = magic(tv);

    /* generate the Mulh instruction */
    c = new_r_Const(current_ir_graph, block, mode, mag.M);
    q = new_rd_Mulh(dbg, current_ir_graph, block, n, c, mode);

    /* do we need an Add or Sub */
    if (mag.need_add)
      q = new_rd_Add(dbg, current_ir_graph, block, q, n, mode);
    else if (mag.need_sub)
      q = new_rd_Sub(dbg, current_ir_graph, block, q, n, mode);

    /* Do we need the shift */
    if (mag.s > 0) {
614
      c = new_r_Const_long(current_ir_graph, block, mode_Iu, mag.s);
615
616
617
618
      q    = new_rd_Shrs(dbg, current_ir_graph, block, q, c, mode);
    }

    /* final */
619
    c = new_r_Const_long(current_ir_graph, block, mode_Iu, bits-1);
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
    t = new_rd_Shr(dbg, current_ir_graph, block, q, c, mode);

    q = new_rd_Add(dbg, current_ir_graph, block, q, t, mode);
  }
  else {
    struct mu mag = magicu(tv);
    ir_node *c;

    /* generate the Mulh instruction */
    c = new_r_Const(current_ir_graph, block, mode, mag.M);
    q    = new_rd_Mulh(dbg, current_ir_graph, block, n, c, mode);

    if (mag.need_add) {
      if (mag.s > 0) {
        /* use the GM scheme */
        t = new_rd_Sub(dbg, current_ir_graph, block, n, q, mode);

        c = new_r_Const(current_ir_graph, block, mode_Iu, get_mode_one(mode_Iu));
        t = new_rd_Shr(dbg, current_ir_graph, block, t, c, mode);

        t = new_rd_Add(dbg, current_ir_graph, block, t, q, mode);

642
        c = new_r_Const_long(current_ir_graph, block, mode_Iu, mag.s-1);
643
644
645
646
647
648
649
650
        q = new_rd_Shr(dbg, current_ir_graph, block, t, c, mode);
      }
      else {
        /* use the default scheme */
        q = new_rd_Add(dbg, current_ir_graph, block, q, n, mode);
      }
    }
    else if (mag.s > 0) { /* default scheme, shift needed */
651
      c = new_r_Const_long(current_ir_graph, block, mode_Iu, mag.s);
652
653
654
655
656
657
      q = new_rd_Shr(dbg, current_ir_graph, block, q, c, mode);
    }
  }
  return q;
}

658
/* Replace Divs with Shifts and Add/Subs and Mulh. */
659
ir_node *arch_dep_replace_div_by_const(ir_node *irn)
Michael Beck's avatar
Michael Beck committed
660
661
662
663
664
{
  ir_node *res  = irn;

  /* If the architecture dependent optimizations were not initialized
     or this optimization was not enabled. */
665
  if (params == NULL || (opts & arch_dep_div_by_const) == 0)
Michael Beck's avatar
Michael Beck committed
666
667
668
669
670
671
    return irn;

  if (get_irn_opcode(irn) == iro_Div) {
    ir_node *c = get_Div_right(irn);
    ir_node *block, *left;
    ir_mode *mode;
672
    tarval *tv, *ntv;
Michael Beck's avatar
Michael Beck committed
673
674
    dbg_info *dbg;
    int n, bits;
675
    int k, n_flag;
Michael Beck's avatar
Michael Beck committed
676
677
678
679

    if (get_irn_op(c) != op_Const)
      return irn;

680
681
682
683
684
685
    tv = get_Const_tarval(c);

    /* check for division by zero */
    if (classify_tarval(tv) == TV_CLASSIFY_NULL)
      return irn;

Michael Beck's avatar
Michael Beck committed
686
687
    left  = get_Div_left(irn);
    mode  = get_irn_mode(left);
Michael Beck's avatar
Michael Beck committed
688
    block = get_irn_n(irn, -1);
Michael Beck's avatar
Michael Beck committed
689
690
691
692
693
    dbg   = get_irn_dbg_info(irn);

    bits = get_mode_size_bits(mode);
    n    = (bits + 7) / 8;

694
695
696
697
698
699
    k = -1;
    if (mode_is_signed(mode)) {
      /* for signed divisions, the algorithm works for a / -2^k by negating the result */
      ntv = tarval_neg(tv);
      n_flag = 1;
      k = tv_ld2(ntv, n);
Michael Beck's avatar
Michael Beck committed
700
701
    }

702
703
704
705
    if (k < 0) {
      n_flag = 0;
      k = tv_ld2(tv, n);
    }
Michael Beck's avatar
Michael Beck committed
706

707
    if (k >= 0) { /* division by 2^k or -2^k */
Michael Beck's avatar
Michael Beck committed
708
709
710
711
712
      if (mode_is_signed(mode)) {
        ir_node *k_node;
        ir_node *curr = left;

        if (k != 1) {
713
          k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k - 1);
Michael Beck's avatar
Michael Beck committed
714
715
716
          curr   = new_rd_Shrs(dbg, current_ir_graph, block, left, k_node, mode);
        }

717
        k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, bits - k);
Michael Beck's avatar
Michael Beck committed
718
719
720
721
        curr   = new_rd_Shr(dbg, current_ir_graph, block, curr, k_node, mode);

        curr   = new_rd_Add(dbg, current_ir_graph, block, left, curr, mode);

722
        k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k);
Michael Beck's avatar
Michael Beck committed
723
        res    = new_rd_Shrs(dbg, current_ir_graph, block, curr, k_node, mode);
724
725
726
727
728
729
730

        if (n_flag) { /* negate the result */
          ir_node *k_node;

          k_node = new_r_Const(current_ir_graph, block, mode, get_mode_null(mode));
          res = new_rd_Sub(dbg, current_ir_graph, block, k_node, res, mode);
        }
Michael Beck's avatar
Michael Beck committed
731
732
733
734
      }
      else {      /* unsigned case */
        ir_node *k_node;

735
        k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k);
736
        res    = new_rd_Shr(dbg, current_ir_graph, block, left, k_node, mode);
Michael Beck's avatar
Michael Beck committed
737
738
      }
    }
739
740
    else {
      /* other constant */
741
      if (allow_Mulh(mode))
742
743
        res = replace_div_by_mulh(irn, tv);
    }
Michael Beck's avatar
Michael Beck committed
744
745
746
  }

  if (res != irn)
Michael Beck's avatar
Michael Beck committed
747
    hook_arch_dep_replace_division_by_const(irn);
Michael Beck's avatar
Michael Beck committed
748
749

  return res;
750
751
}

752
/* Replace Mods with Shifts and Add/Subs and Mulh. */
753
ir_node *arch_dep_replace_mod_by_const(ir_node *irn)
Michael Beck's avatar
Michael Beck committed
754
755
756
757
758
{
  ir_node *res  = irn;

  /* If the architecture dependent optimizations were not initialized
     or this optimization was not enabled. */
759
  if (params == NULL || (opts & arch_dep_mod_by_const) == 0)
Michael Beck's avatar
Michael Beck committed
760
761
762
763
764
765
    return irn;

  if (get_irn_opcode(irn) == iro_Mod) {
    ir_node *c = get_Mod_right(irn);
    ir_node *block, *left;
    ir_mode *mode;
766
    tarval *tv, *ntv;
Michael Beck's avatar
Michael Beck committed
767
768
    dbg_info *dbg;
    int n, bits;
769
    int k;
Michael Beck's avatar
Michael Beck committed
770
771
772
773

    if (get_irn_op(c) != op_Const)
      return irn;

774
775
776
777
778
779
    tv = get_Const_tarval(c);

    /* check for division by zero */
    if (classify_tarval(tv) == TV_CLASSIFY_NULL)
      return irn;

Michael Beck's avatar
Michael Beck committed
780
781
    left  = get_Mod_left(irn);
    mode  = get_irn_mode(left);
Michael Beck's avatar
Michael Beck committed
782
    block = get_irn_n(irn, -1);
Michael Beck's avatar
Michael Beck committed
783
784
785
786
    dbg   = get_irn_dbg_info(irn);
    bits = get_mode_size_bits(mode);
    n    = (bits + 7) / 8;

787
788
789
790
791
    k = -1;
    if (mode_is_signed(mode)) {
      /* for signed divisions, the algorithm works for a / -2^k by negating the result */
      ntv = tarval_neg(tv);
      k = tv_ld2(ntv, n);
Michael Beck's avatar
Michael Beck committed
792
793
    }

794
795
796
    if (k < 0) {
      k = tv_ld2(tv, n);
    }
Michael Beck's avatar
Michael Beck committed
797

798
799
800
801
    if (k >= 0) {
      /* division by 2^k or -2^k:
       * we use "modulus" here, so x % y == x % -y that's why is no difference between the case 2^k and -2^k
       */
Michael Beck's avatar
Michael Beck committed
802
803
804
805
806
      if (mode_is_signed(mode)) {
        ir_node *k_node;
        ir_node *curr = left;

        if (k != 1) {
807
          k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k - 1);
Michael Beck's avatar
Michael Beck committed
808
809
810
          curr   = new_rd_Shrs(dbg, current_ir_graph, block, left, k_node, mode);
        }

811
        k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, bits - k);
Michael Beck's avatar
Michael Beck committed
812
813
814
815
        curr   = new_rd_Shr(dbg, current_ir_graph, block, curr, k_node, mode);

        curr   = new_rd_Add(dbg, current_ir_graph, block, left, curr, mode);

816
        k_node = new_r_Const_long(current_ir_graph, block, mode, (-1) << k);
Michael Beck's avatar
Michael Beck committed
817
818
819
820
821
822
823
        curr   = new_rd_And(dbg, current_ir_graph, block, curr, k_node, mode);

        res    = new_rd_Sub(dbg, current_ir_graph, block, left, curr, mode);
      }
      else {      /* unsigned case */
        ir_node *k_node;

824
        k_node = new_r_Const_long(current_ir_graph, block, mode, (1 << k) - 1);
Michael Beck's avatar
Michael Beck committed
825
826
827
        res    = new_rd_And(dbg, current_ir_graph, block, left, k_node, mode);
      }
    }
828
829
    else {
      /* other constant */
830
      if (allow_Mulh(mode)) {
831
832
833
834
835
836
837
838
839
        res = replace_div_by_mulh(irn, tv);

        res = new_rd_Mul(dbg, current_ir_graph, block, res, c, mode);

        /* res = arch_dep_mul_to_shift(res); */

        res = new_rd_Sub(dbg, current_ir_graph, block, left, res, mode);
      }
    }
Michael Beck's avatar
Michael Beck committed
840
841
842
  }

  if (res != irn)
Michael Beck's avatar
Michael Beck committed
843
    hook_arch_dep_replace_division_by_const(irn);
Michael Beck's avatar
Michael Beck committed
844
845
846
847

  return res;
}

848
/* Replace DivMods with Shifts and Add/Subs and Mulh. */
849
void arch_dep_replace_divmod_by_const(ir_node **div, ir_node **mod, ir_node *irn)
Michael Beck's avatar
Michael Beck committed
850
851
852
853
854
{
  *div = *mod = NULL;

  /* If the architecture dependent optimizations were not initialized
     or this optimization was not enabled. */
Michael Beck's avatar
Michael Beck committed
855
  if (params == NULL ||
856
      ((opts & (arch_dep_div_by_const|arch_dep_mod_by_const)) != (arch_dep_div_by_const|arch_dep_mod_by_const)))
Michael Beck's avatar
Michael Beck committed
857
858
859
860
861
862
    return;

  if (get_irn_opcode(irn) == iro_DivMod) {
    ir_node *c = get_DivMod_right(irn);
    ir_node *block, *left;
    ir_mode *mode;
863
    tarval *tv, *ntv;
Michael Beck's avatar
Michael Beck committed
864
865
    dbg_info *dbg;
    int n, bits;
866
    int k, n_flag;
Michael Beck's avatar
Michael Beck committed
867
868
869
870

    if (get_irn_op(c) != op_Const)
      return;

871
872
873
874
875
876
    tv = get_Const_tarval(c);

    /* check for division by zero */
    if (classify_tarval(tv) == TV_CLASSIFY_NULL)
      return;

Michael Beck's avatar
Michael Beck committed
877
878
    left  = get_DivMod_left(irn);
    mode  = get_irn_mode(left);
Michael Beck's avatar
Michael Beck committed
879
    block = get_irn_n(irn, -1);
Michael Beck's avatar
Michael Beck committed
880
881
882
883
884
    dbg   = get_irn_dbg_info(irn);

    bits = get_mode_size_bits(mode);
    n    = (bits + 7) / 8;

885
886
887
888
889
890
    k = -1;
    if (mode_is_signed(mode)) {
      /* for signed divisions, the algorithm works for a / -2^k by negating the result */
      ntv = tarval_neg(tv);
      n_flag = 1;
      k = tv_ld2(ntv, n);
Michael Beck's avatar
Michael Beck committed
891
892
    }

893
894
895
896
    if (k < 0) {
      n_flag = 0;
      k = tv_ld2(tv, n);
    }
Michael Beck's avatar
Michael Beck committed
897

898
    if (k >= 0) { /* division by 2^k or -2^k */
Michael Beck's avatar
Michael Beck committed
899
      if (mode_is_signed(mode)) {
900
        ir_node *k_node, *c_k;
Michael Beck's avatar
Michael Beck committed
901
902
903
        ir_node *curr = left;

        if (k != 1) {
904
          k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k - 1);
Michael Beck's avatar
Michael Beck committed
905
906
907
          curr   = new_rd_Shrs(dbg, current_ir_graph, block, left, k_node, mode);
        }

908
        k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, bits - k);
Michael Beck's avatar
Michael Beck committed
909
910
911
912
        curr   = new_rd_Shr(dbg, current_ir_graph, block, curr, k_node, mode);

        curr   = new_rd_Add(dbg, current_ir_graph, block, left, curr, mode);

913
        c_k    = new_r_Const_long(current_ir_graph, block, mode_Iu, k);
914
915
916
917
918
919
920
921
922

        *div   = new_rd_Shrs(dbg, current_ir_graph, block, curr, c_k, mode);

        if (n_flag) { /* negate the div result */
          ir_node *k_node;

          k_node = new_r_Const(current_ir_graph, block, mode, get_mode_null(mode));
          *div = new_rd_Sub(dbg, current_ir_graph, block, k_node, *div, mode);
        }
Michael Beck's avatar
Michael Beck committed
923

924
        k_node = new_r_Const_long(current_ir_graph, block, mode, (-1) << k);
Michael Beck's avatar
Michael Beck committed
925
926
927
928
929
930
931
        curr   = new_rd_And(dbg, current_ir_graph, block, curr, k_node, mode);

        *mod   = new_rd_Sub(dbg, current_ir_graph, block, left, curr, mode);
      }
      else {      /* unsigned case */
        ir_node *k_node;

932
        k_node = new_r_Const_long(current_ir_graph, block, mode_Iu, k);
933
        *div   = new_rd_Shr(dbg, current_ir_graph, block, left, k_node, mode);
Michael Beck's avatar
Michael Beck committed
934

935
        k_node = new_r_Const_long(current_ir_graph, block, mode, (1 << k) - 1);
Michael Beck's avatar
Michael Beck committed
936
937
938
        *mod   = new_rd_And(dbg, current_ir_graph, block, left, k_node, mode);
      }
    }
939
940
    else {
      /* other constant */
941
      if (allow_Mulh(mode)) {
942
943
944
945
946
947
948
949
950
951
952
        ir_node *t;

        *div = replace_div_by_mulh(irn, tv);

        t    = new_rd_Mul(dbg, current_ir_graph, block, *div, c, mode);

        /* t = arch_dep_mul_to_shift(t); */

        *mod = new_rd_Sub(dbg, current_ir_graph, block, left, t, mode);
      }
    }
Michael Beck's avatar
Michael Beck committed
953
954
955
  }

  if (*div)
Michael Beck's avatar
Michael Beck committed
956
    hook_arch_dep_replace_division_by_const(irn);
Michael Beck's avatar
Michael Beck committed
957
958
}

959
960

static const arch_dep_params_t default_params = {
961
962
963
964
965
966
967
  1,  /* also use subs */
  4,  /* maximum shifts */
  31, /* maximum shift amount */

  0,  /* allow Mulhs */
  0,  /* allow Mulus */
  32  /* Mulh allowed up to 32 bit */
968
969
};

970
/* A default parameter factory for testing purposes. */
971
const arch_dep_params_t *arch_dep_default_factory(void) {
Michael Beck's avatar
Michael Beck committed
972
  return &default_params;
973
}