strength_red.c 23 KB
Newer Older
1
2
/**
 *
Beyhan's avatar
Beyhan committed
3
 * @file strength_red.c
4
5
6
7
8
9
 *
 * Project:     libFIRM
 * File name:   ir/opt/strength_red.c
 * Purpose:     Make strength reduction .
 * Author:      Beyhan Veliev
 * Modified by:
Beyhan's avatar
Beyhan committed
10
 * Created:     22.8.2004
11
 * CVS-ID:      $Id$
Beyhan's avatar
Beyhan committed
12
 * Copyright:   (c) 2004 Universität Karlsruhe
13
14
15
16
17
 * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
 */

# include "strength_red.h"

Beyhan's avatar
Beyhan committed
18
# include "irouts.h"
19
20
21
22
23
# include "irnode_t.h"
# include "irgwalk.h"
# include "irloop_t.h"
# include "ircons.h"
# include "irgmod.h"
Michael Beck's avatar
Michael Beck committed
24
# include "irdump_t.h"
25
# include "firmstat.h"
26
27


Götz Lindenmaier's avatar
Götz Lindenmaier committed
28
29
/** Counter for verbose information about optimization. */
static int n_reduced_expressions;
Beyhan's avatar
Beyhan committed
30
static int n_made_new_phis;
Michael Beck's avatar
Michael Beck committed
31

32
33
/** Detect basic iteration variables.
 *
Michael Beck's avatar
Michael Beck committed
34
35
 * The variable is represented by a subgraph as this:
 * @verbatim
36
37
38
39
 *
 *       init
 *       /|\
 *        |
Michael Beck's avatar
Michael Beck committed
40
 *   +-- Phi
41
42
 *   |   /|\
 *   |    |
Michael Beck's avatar
Michael Beck committed
43
 *   +-->op
44
 *
Michael Beck's avatar
Michael Beck committed
45
46
47
48
49
50
51
52
 * @endverbatim
 *
 * Where op is a Add or Sub node and init is loop invariant.
 *
 * @note
 * So far we only accept Phi nodes with two predecessors.
 * We could expand this to Phi nodes where all predecessors
 * are either op or loop invariant.
53
 *
54
 * @param info  After call contains the induction variable information.
Michael Beck's avatar
Michael Beck committed
55
56
57
 *
 * @return
 *   The info structure.
58
 */
Michael Beck's avatar
Michael Beck committed
59
induct_var_info *is_induction_variable(induct_var_info *info) {
60

Michael Beck's avatar
Michael Beck committed
61
  int i, q, r;
Michael Beck's avatar
Michael Beck committed
62
  int op_pred, Store_in_op, Store_in_phi;
Michael Beck's avatar
Michael Beck committed
63
64
  ir_node *cmp_pred_bl, *cond_succ_0, *cond_succ_1, *cmp_const;
  ir_node *loop_head;
Michael Beck's avatar
Michael Beck committed
65
  ir_node *cmp_const_block;
66

67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
  info->operation_code   = NULL; /* The opcode of "op". */
  info->increment        = NULL; /* The value which increase or decrease the iteration variable. */
  info->init             = NULL; /* The start value of the iteration variable. */
  info->op               = NULL; /* The operation which increase or decrease the iteration variable. */
  info->l_itervar_phi    = NULL; /* The iteration variable. */
  info->new_phi          = NULL; /* The new iteration variable. */
  info->new_increment    = NULL; /* The new increment which replace the old one.*/
  info->new_init         = NULL; /* The new init value of the iteration variable. */
  info->new_op           = NULL; /* The new operation that we need after replace. */
  info->new_cmp          = NULL; /* The new Cmp which replaces the old one. */
  info->cmp              = NULL; /* The Cmp which breaks the loop and compares the iteration variable with a constant. */
  info->cmp_const        = NULL; /* The other operand of Cmp. */
  info->cmp_init_block   = NULL; /* The initial block of the Cmp. */
  info->reducible_node   = NULL; /* The reducible nodes are save here. */
  info->is_reducible     = 0;    /* To save information if anything is reducible. */
  info->phi_pred         = 0;    /* To save the value of iteration variable predecessors. */
  info->init_pred_pos    = -1;   /* To save the position of iteration variable start value. */
  info->op_pred_pos      = -1;   /* To save the backedge of iteration variable. */
  info->l_itervar_phi    = NULL; /* Information about loop of itervar_phi. */
Beyhan's avatar
Beyhan committed
86
87

  assert(get_irn_op(info->itervar_phi) == op_Phi);
88

Michael Beck's avatar
Michael Beck committed
89
90
91
92
  /*
   * The necessary conditions for the phi node:
   * We can handle currently Phi's with 2 predecessors, one must be a backedge.
   */
Michael Beck's avatar
Michael Beck committed
93
  if (get_irn_arity(info->itervar_phi) != 2 || !has_backedges(get_nodes_block(info->itervar_phi)))
94
95
    return NULL;

Michael Beck's avatar
Michael Beck committed
96
  for (i = 0; i < 2; ++i) {
Michael Beck's avatar
Michael Beck committed
97
    ir_node *pred = get_Phi_pred(info->itervar_phi, i);
Michael Beck's avatar
Michael Beck committed
98
99
    ir_op *op = get_irn_op(pred);

Michael Beck's avatar
Michael Beck committed
100
    /* Compute if the induction variable is added or subtracted with a constant. */
Michael Beck's avatar
Michael Beck committed
101
102
103
104
    if (op == op_Add || op == op_Sub) {
      ir_node *n_l = get_binop_left(pred);
      ir_node *n_r = get_binop_right(pred);

Michael Beck's avatar
Michael Beck committed
105
      if (n_l == info->itervar_phi) {
Michael Beck's avatar
Michael Beck committed
106
107
108
109
110
111
        info->operation_code = op;
        info->increment      = n_r;
        info->op_pred_pos    = i;
        info->init_pred_pos  = i ^ 1;
        break;
      }
Michael Beck's avatar
Michael Beck committed
112
      else if (n_r == info->itervar_phi) {
Michael Beck's avatar
Michael Beck committed
113
114
115
116
117
118
119
120
121
122
        info->operation_code = op;
        info->increment      = n_l;
        info->op_pred_pos    = i;
        info->init_pred_pos  = i ^ 1;
        break;
      }
    }
  }
  /* check if we found something */
  if (! info->operation_code)
123
124
    return NULL;

Michael Beck's avatar
Michael Beck committed
125
  /* Compute the position of the backedge. */
Michael Beck's avatar
Michael Beck committed
126
127
128
  if (is_backedge(get_nodes_block(info->itervar_phi), info->op_pred_pos)) {
    info->op   = get_Phi_pred(info->itervar_phi, info->op_pred_pos);
    info->init = get_Phi_pred(info->itervar_phi, info->init_pred_pos);
Michael Beck's avatar
Michael Beck committed
129
130
131
132
  }
  else {
    /* irregular control flow detected. */
    return NULL;
133
134
  }

Michael Beck's avatar
Michael Beck committed
135
136
137
138
  /*
   * the block of the init code should dominate the loop, else
   * we have an irregular control flow
   */
Beyhan's avatar
Beyhan committed
139
  if (get_Block_dom_depth(get_nodes_block(info->init))  >=
Beyhan's avatar
Beyhan committed
140
      get_Block_dom_depth(get_nodes_block(info->itervar_phi))) {
Beyhan's avatar
Beyhan committed
141
142
    return NULL;
  }
143

Michael Beck's avatar
Michael Beck committed
144
145
146
  op_pred      = get_irn_n_outs(info->op);
  Store_in_op  = 0;
  Store_in_phi = 0;
Beyhan's avatar
Beyhan committed
147

Michael Beck's avatar
Michael Beck committed
148
  /* Information about loop of itervar_phi. */
Beyhan's avatar
Beyhan committed
149
150
  info->l_itervar_phi = get_irn_loop(get_nodes_block(info->itervar_phi));

Beyhan's avatar
Beyhan committed
151
152
153
154

  info->phi_pred = get_irn_n_outs(info->itervar_phi);
  loop_head = get_nodes_block(info->itervar_phi);

Michael Beck's avatar
Michael Beck committed
155
  /*
Michael Beck's avatar
Michael Beck committed
156
   * This "for" searches for the Cmp successor of the
Michael Beck's avatar
Michael Beck committed
157
158
159
160
   * iter_var to reduce and marks if the iter_var have a Store
   * successor or a successor out of loop.
   */
  for (i = 0; i < info->phi_pred; i++) {
Michael Beck's avatar
Michael Beck committed
161
    ir_node *out = get_irn_out(info->itervar_phi, i);
Beyhan's avatar
Beyhan committed
162
    ir_op   *out_op = get_irn_op(out);
163

Michael Beck's avatar
Michael Beck committed
164
    if (out_op == op_Store)
Beyhan's avatar
Beyhan committed
165
      Store_in_phi++;
Michael Beck's avatar
Michael Beck committed
166
    else if (out_op == op_Cmp && !is_loop_invariant(out, loop_head)) {
167
      /* a Cmp can have more than one successor therefore we need this loop.*/
Michael Beck's avatar
Michael Beck committed
168
169
170
171
      for (q = get_irn_n_outs(out) - 1; q >= 0; --q) {
        ir_node *proj = get_irn_out(out, q);

        for (r = get_irn_n_outs(proj) -1; r >= 0; --r) {
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
          cmp_pred_bl = get_irn_out(proj, r);

          /* The wanted Cmp must be followed by a Cond successor
             not by a Mux. */
          if (get_irn_op(cmp_pred_bl) != op_Cond)
            continue;

          /* the binary Cond should have two successors */
          if (get_irn_n_outs(cmp_pred_bl) != 2)
            continue;

          cond_succ_0 = get_irn_out(cmp_pred_bl, 0);
          cond_succ_1 = get_irn_out(cmp_pred_bl, 1);

          if (is_loop_invariant(get_irn_out(cond_succ_1, 0), loop_head) ||
            is_loop_invariant(get_irn_out(cond_succ_0, 0), loop_head)) {
            if (get_Cmp_left(out) == info->itervar_phi)
              cmp_const = get_Cmp_right(out);
            else
              cmp_const = get_Cmp_left(out);
          } else
            continue;
          if (info->cmp == NULL) {
            /* A cmp is found.*/
            info->cmp       = out;
            info->cmp_const = cmp_const;
          }
          else {
            /* We have more then one cmp with our requests, that mean cmp isn't found */
            info->cmp = NULL;
            return NULL;
          }
Michael Beck's avatar
Michael Beck committed
204
        }
Michael Beck's avatar
Michael Beck committed
205
      }
Beyhan's avatar
Beyhan committed
206
207
    }
  }
Michael Beck's avatar
Michael Beck committed
208

Michael Beck's avatar
Michael Beck committed
209
210
211
  for (i = 0; i < op_pred; ++i) {
    ir_node *out  = get_irn_out(info->op, i);
    ir_op *out_op = get_irn_op(out);
Michael Beck's avatar
Michael Beck committed
212

Michael Beck's avatar
Michael Beck committed
213
214
    if (out_op == op_Store)
      Store_in_op++;
Michael Beck's avatar
Michael Beck committed
215
    else if (out_op == op_Cmp && !is_loop_invariant(out, loop_head)) {
216
217
      /* a Cmp can have more as one successor therefore
         I need this for loop. */
Michael Beck's avatar
Michael Beck committed
218
219
220
221
      for (q = get_irn_n_outs(out) - 1; q >= 0; --q) {
        ir_node *proj = get_irn_out(out, q);

        for (r = get_irn_n_outs(proj) -1; r >= 0; --r) {
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
          cmp_pred_bl = get_irn_out(proj, r);

          /* The wanted Cmp must be followed by a Cond successor. */
          if (get_irn_op(cmp_pred_bl) != op_Cond)
            continue;

          cond_succ_0 = get_irn_out(cmp_pred_bl, 0);
          cond_succ_1 = get_irn_out(cmp_pred_bl, 1);

          if (is_loop_invariant(get_irn_out(cond_succ_0, 0), loop_head) ||
            is_loop_invariant(get_irn_out(cond_succ_1, 0), loop_head)) {
            if (get_Cmp_left(out) == info->op)
              cmp_const = get_Cmp_right(out);
            else
              cmp_const = get_Cmp_left(out);
          } else
            continue;
          if (info->cmp == NULL) {
            /* A cmp is found*/
            info->cmp = out;
            info->cmp_const = cmp_const;
          }
          else {
            /* We have more then one cmp with our requests, that mean cmp isn't found*/
            info->cmp = NULL;
            return NULL;
          }
Michael Beck's avatar
Michael Beck committed
249
250
251
252
        }
      }
    }
  }
Beyhan's avatar
Beyhan committed
253

Michael Beck's avatar
Michael Beck committed
254
255
256
  if ((info->phi_pred == 3 && op_pred == 1 && Store_in_phi == 0 && info->cmp != NULL)  ||
      (info->phi_pred == 2 && op_pred == 2 && Store_in_op == 0 && info->cmp != NULL )  ||
      (info->phi_pred == 1 && Store_in_op == 0))
257
    info->is_reducible = 1;
258

Beyhan's avatar
Beyhan committed
259
  /* Search for loop invariant of Cmp.*/
Michael Beck's avatar
Michael Beck committed
260
  if (info->cmp != NULL) {
261
262
    cmp_const_block = get_nodes_block(info->cmp_const);
    if (get_Block_dom_depth(get_nodes_block(info->init)) >=
Michael Beck's avatar
Michael Beck committed
263
	      get_Block_dom_depth(cmp_const_block))
264
265
266
267
268
      info->cmp_init_block = get_nodes_block(info->init);
    else
      info->cmp_init_block = cmp_const_block;
  }
  return info;
269
270
}

Michael Beck's avatar
Michael Beck committed
271
/**
272
 * Creates a new Add node with the correct mode from its two operands.
Michael Beck's avatar
Michael Beck committed
273
 */
Beyhan's avatar
Beyhan committed
274
static INLINE ir_node *
Michael Beck's avatar
Michael Beck committed
275
my_new_r_Add(ir_graph *irg, ir_node *b, ir_node *op1, ir_node *op2) {
Michael Beck's avatar
Michael Beck committed
276
277
278
279
280
  ir_mode *m  = get_irn_mode(op1);
  ir_mode *m2 = get_irn_mode(op2);

  if (mode_is_reference(m2))
    m = m2;
Beyhan's avatar
Beyhan committed
281

Beyhan's avatar
Beyhan committed
282
283
  return new_r_Add(irg, b, op1, op2, m);
}
284

Michael Beck's avatar
Michael Beck committed
285
/**
286
 * Creates a new Sub node with the correct mode from its two operands.
Michael Beck's avatar
Michael Beck committed
287
 */
Beyhan's avatar
Beyhan committed
288
static INLINE ir_node *
Michael Beck's avatar
Michael Beck committed
289
my_new_r_Sub(ir_graph *irg, ir_node *b, ir_node *op1, ir_node *op2) {
Michael Beck's avatar
Michael Beck committed
290
291
292
293
294
295
296
  ir_mode *m  = get_irn_mode(op1);
  ir_mode *m2 = get_irn_mode(op2);

  if (mode_is_reference(m) && mode_is_reference(m2))
    m = mode_Is;        /* FIXME: may be other mode! */
  else if (mode_is_reference(m2))
    m = m2;
Beyhan's avatar
Beyhan committed
297
298
  return new_r_Sub(irg, b, op1, op2, m);
}
299

300
301
/**
 * Reduce an Add, Sub or Mul node
Beyhan's avatar
Beyhan committed
302
303
304
305
 *
 * @param *reduce_var  The node to reduce.
 * @param *ivi         Contains the induction variable information.
 */
Michael Beck's avatar
Michael Beck committed
306
307
static int reduce(ir_node *reduce_var, induct_var_info *ivi)
{
Michael Beck's avatar
Michael Beck committed
308
309
  ir_node *iter_varblk, *init_block, *irg_startblk, *block_init;

310
  /* Essential conditions for a reducible node. */
Michael Beck's avatar
Michael Beck committed
311
312
  if (get_irn_loop(get_nodes_block(reduce_var)) != ivi->l_itervar_phi)
    return 0;
313

Michael Beck's avatar
Michael Beck committed
314
315
316
317
  iter_varblk  = get_nodes_block(ivi->itervar_phi);
  init_block   = get_nodes_block(ivi->init);
  irg_startblk = get_irg_start_block(current_ir_graph);

318
  /* The "new_init" and the "new_cmp_const" must not be in the start block.*/
Michael Beck's avatar
Michael Beck committed
319
320
321
322
323
324
  if (get_Block_dom_depth(init_block) > get_Block_dom_depth(irg_startblk) &&
      init_block != iter_varblk)
    block_init = init_block;
  else
    block_init = get_nodes_block(get_Block_cfgpred(iter_varblk, ivi->init_pred_pos));

325
  /* To avoid that cmp is placed in the start block.*/
Michael Beck's avatar
Michael Beck committed
326
327
328
  if (ivi->cmp_init_block == irg_startblk)
    ivi->cmp_init_block = iter_varblk;

Michael Beck's avatar
Michael Beck committed
329
  if (get_irn_op(reduce_var) == op_Mul) {
Beyhan's avatar
Beyhan committed
330
331
    ir_node *mul_init  = NULL;
    ir_node *mul_const = NULL;
Michael Beck's avatar
Michael Beck committed
332

333
    /* Search for constant and init of strong. */
Beyhan's avatar
Beyhan committed
334
335
336
337
    ir_node  *mul_right = get_Mul_right(reduce_var);
    ir_node  *mul_left  = get_Mul_left(reduce_var);
    ir_op *mul_right_op = get_irn_op(mul_right);
    ir_op  *mul_left_op = get_irn_op(mul_left);
338

Michael Beck's avatar
Michael Beck committed
339
    ir_node *in[2];
Michael Beck's avatar
Michael Beck committed
340
341
342
343
344
345
346
    ir_node *block_inc;

    ir_node *increment_block;
    ir_node *c_block;

    n_reduced_expressions++;

Michael Beck's avatar
Michael Beck committed
347
    if (mul_right_op == op_Const) {
Beyhan's avatar
Beyhan committed
348
      mul_const = mul_right;
Michael Beck's avatar
Michael Beck committed
349
350
351
      mul_init  = mul_left;
    }
    else if (mul_left_op == op_Const) {
Beyhan's avatar
Beyhan committed
352
      mul_const = mul_left;
Michael Beck's avatar
Michael Beck committed
353
354
      mul_init  = mul_right;
    }
355

Michael Beck's avatar
Michael Beck committed
356
357
    if (mul_const == NULL || mul_init == NULL)
      return 0;
Beyhan's avatar
Beyhan committed
358

Michael Beck's avatar
Michael Beck committed
359
360
    increment_block = get_nodes_block(ivi->increment);
    c_block         = get_nodes_block(mul_const);
361
362
363
364
365
366

    if (get_Block_dom_depth(increment_block) >= get_Block_dom_depth(c_block))
      block_inc = increment_block;
    else
      block_inc = c_block;

367
    if (! ivi->is_reducible){
Michael Beck's avatar
Michael Beck committed
368
369
      int reduce_var_pred;

370
      /* Essential condition for the constant of strong. */
Beyhan's avatar
Beyhan committed
371
      if (get_Block_dom_depth(get_nodes_block(mul_const))  >=
Michael Beck's avatar
Michael Beck committed
372
373
374
          get_Block_dom_depth(get_nodes_block(ivi->itervar_phi)))
        return 0;

Beyhan's avatar
Beyhan committed
375
376
      n_made_new_phis++;
      if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
Michael Beck's avatar
Michael Beck committed
377
378
379
        printf("The new Phi node is : "); DDMN(ivi->itervar_phi);
        printf("reducing operation is : "); DDMN(reduce_var);
        printf("in graph : "); DDMG(current_ir_graph);
Beyhan's avatar
Beyhan committed
380
      }
381

Michael Beck's avatar
Michael Beck committed
382
383
      ivi->new_increment  = new_r_Mul (current_ir_graph, block_inc, ivi->increment, mul_const,
                                       get_irn_mode(mul_const));
Beyhan's avatar
Beyhan committed
384
      if (!(get_irn_op(mul_init) == op_Phi)){
Michael Beck's avatar
Michael Beck committed
385
386
387
388
389
390
391
        ivi->new_init = new_r_Mul (current_ir_graph, block_init, ivi->init, mul_const,
                                   get_irn_mode(mul_const));
        ivi->new_init = my_new_r_Add(current_ir_graph, block_init, ivi->new_init,
                                    ivi->new_increment);
      } else
        ivi->new_init = new_r_Mul (current_ir_graph, block_init, ivi->init, mul_const,
                                   get_irn_mode(mul_const));
Beyhan's avatar
Beyhan committed
392

Beyhan's avatar
Beyhan committed
393
      /* Generate a new basic induction variable. Break the data flow loop
Michael Beck's avatar
Michael Beck committed
394
         initially by using an Unknown node. */
Beyhan's avatar
Beyhan committed
395
396
397
398
399

      in[ivi->op_pred_pos]   = new_Unknown(get_irn_mode(ivi->new_init));

      in[ivi->init_pred_pos] = ivi->new_init;
      ivi->new_phi = new_r_Phi(current_ir_graph, get_nodes_block(ivi->itervar_phi), 2, in,
Michael Beck's avatar
Michael Beck committed
400
                               get_irn_mode(mul_const));
Beyhan's avatar
Beyhan committed
401
402
403
      mark_irn_visited(ivi->new_phi);

      if (ivi->operation_code == op_Add)
Michael Beck's avatar
Michael Beck committed
404
405
        ivi->new_op = my_new_r_Add(current_ir_graph, get_nodes_block(ivi->op),
                                  ivi->new_increment,ivi-> new_phi);
Beyhan's avatar
Beyhan committed
406
      else if (ivi->operation_code == op_Sub)
Michael Beck's avatar
Michael Beck committed
407
408
        ivi->new_op = my_new_r_Sub(current_ir_graph, get_nodes_block(ivi->op),ivi-> new_phi,
                                   ivi->new_increment);
Beyhan's avatar
Beyhan committed
409
410

      set_Phi_pred(ivi->new_phi, ivi->op_pred_pos, ivi->new_op);
Beyhan's avatar
Beyhan committed
411

Beyhan's avatar
Beyhan committed
412
      // This for search for a reducible successor of reduc_var.
Michael Beck's avatar
Michael Beck committed
413
414
      reduce_var_pred =  get_irn_n_outs(reduce_var);
      if (reduce_var_pred == 1) {
Michael Beck's avatar
Michael Beck committed
415
416
417
        ir_node *old_ind =get_irn_out(reduce_var, 0);
        if(get_irn_op(old_ind) == op_Add || get_irn_op(old_ind) == op_Sub ||
           get_irn_op(old_ind) == op_Mul){
418
          ivi->is_reducible = 1;
Michael Beck's avatar
Michael Beck committed
419
420
          ivi->reducible_node = old_ind;
        }
Beyhan's avatar
Beyhan committed
421
422
423
424
      }
      /* Replace the use of the strength reduced value. */
      exchange(reduce_var, ivi->new_phi);
      return 1;
Michael Beck's avatar
Michael Beck committed
425
    }
426
427
    else { /* ivi->is_reducible */
      if (ivi->new_phi == NULL) {
Michael Beck's avatar
Michael Beck committed
428
        ivi->init = new_r_Mul (current_ir_graph, block_init,
Michael Beck's avatar
Michael Beck committed
429
430
431
                               mul_const, ivi->init,
                               get_irn_mode(mul_const));
        if(ivi->cmp != NULL)
Michael Beck's avatar
Michael Beck committed
432
433
434
435
          ivi->cmp_const = new_r_Mul (current_ir_graph, ivi->cmp_init_block,
                                      ivi->cmp_const, mul_const, get_irn_mode(mul_const));
        ivi->increment = new_r_Mul (current_ir_graph, block_inc,
                                    ivi->increment, mul_const, get_irn_mode(mul_const));
436
437
      }
      else {
Michael Beck's avatar
Michael Beck committed
438
439
440
441
442
443
        ivi->new_init = new_r_Mul (current_ir_graph, block_init,
                                   mul_const, ivi->new_init,
                                   get_irn_mode(mul_const));
        ivi->new_increment = new_r_Mul (current_ir_graph, block_inc,
                                        ivi->new_increment, mul_const,
                                        get_irn_mode(mul_const));
Beyhan's avatar
Beyhan committed
444
445
      }
      if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
Michael Beck's avatar
Michael Beck committed
446
447
        printf("\nReducing operation is : "); DDMN(reduce_var);
        printf("in graph : "); DDMG(current_ir_graph);
Beyhan's avatar
Beyhan committed
448
449
450
      }
      return 1;
    }
Michael Beck's avatar
Michael Beck committed
451
452
  }
  else if (get_irn_op (reduce_var) == op_Add){
Beyhan's avatar
Beyhan committed
453
454
455
    ir_node *add_init  = NULL;
    ir_node *add_const = NULL;

456
    /* Search for constant of add. */
Beyhan's avatar
Beyhan committed
457
458
459
460
    ir_node  *add_right = get_Add_right(reduce_var);
    ir_node  *add_left  = get_Add_left(reduce_var);
    ir_op *add_right_op = get_irn_op(add_right);
    ir_op  *add_left_op = get_irn_op(add_left);
Michael Beck's avatar
Michael Beck committed
461

462
    ++n_reduced_expressions;
Michael Beck's avatar
Michael Beck committed
463
464

    if (add_right_op != op_Const)
Beyhan's avatar
Beyhan committed
465
      add_init = add_right;
Michael Beck's avatar
Michael Beck committed
466
    else if (add_left_op != op_Const)
Beyhan's avatar
Beyhan committed
467
      add_init = add_left;
Michael Beck's avatar
Michael Beck committed
468
    if (add_right_op == op_Const || add_right_op == op_SymConst)
Beyhan's avatar
Beyhan committed
469
      add_const = add_right;
Michael Beck's avatar
Michael Beck committed
470
    else if (add_left_op == op_Const || add_left_op == op_SymConst)
Beyhan's avatar
Beyhan committed
471
      add_const = add_left;
472
473
474
    if (add_const == NULL)
      return 0;
    if (ivi->new_phi == NULL) {
Michael Beck's avatar
Michael Beck committed
475
      ivi->init = my_new_r_Add(current_ir_graph, block_init,
Michael Beck's avatar
Michael Beck committed
476
477
478
479
                               add_const, ivi->init);
      if (ivi->cmp != NULL)
        ivi->cmp_const = my_new_r_Add(current_ir_graph, ivi->cmp_init_block,
                                      add_const, ivi->cmp_const);
480
481
    }
    else {
Michael Beck's avatar
Michael Beck committed
482
      ivi->new_init = my_new_r_Add(current_ir_graph, block_init,
Michael Beck's avatar
Michael Beck committed
483
                                   add_const, ivi->new_init);
Beyhan's avatar
Beyhan committed
484
485
486
487
488
489
    }
    if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
      printf("\nReducing operation is : "); DDMN(reduce_var);
      printf("in graph : "); DDMG(current_ir_graph);
    }
    return 1;
Michael Beck's avatar
Michael Beck committed
490
491
  }
  else if (get_irn_op(reduce_var) == op_Sub) {
Beyhan's avatar
Beyhan committed
492
493
494
495
496
497
    ir_node *sub_init  = NULL;
    ir_node *sub_const = NULL;
    ir_node  *sub_right = get_Sub_right(reduce_var);
    ir_node  *sub_left  = get_Sub_left(reduce_var);
    ir_op *sub_right_op = get_irn_op(sub_right);
    ir_op  *sub_left_op = get_irn_op(sub_left);
Michael Beck's avatar
Michael Beck committed
498

499
    ++n_reduced_expressions;
Michael Beck's avatar
Michael Beck committed
500

Michael Beck's avatar
Michael Beck committed
501
    /* Search for constant of Sub. */
Michael Beck's avatar
Michael Beck committed
502
    if (sub_right_op != op_Const)
Beyhan's avatar
Beyhan committed
503
      sub_init = sub_right;
Michael Beck's avatar
Michael Beck committed
504
    else if (sub_left_op != op_Const)
Beyhan's avatar
Beyhan committed
505
      sub_init = sub_left;
Michael Beck's avatar
Michael Beck committed
506
    if (sub_right_op == op_Const)
Beyhan's avatar
Beyhan committed
507
      sub_const = sub_right;
Michael Beck's avatar
Michael Beck committed
508
    else if (sub_left_op == op_Const)
Beyhan's avatar
Beyhan committed
509
510
      sub_const = sub_left;

Michael Beck's avatar
Michael Beck committed
511
512
    if (sub_const == NULL)
      return 0;
Beyhan's avatar
Beyhan committed
513

Michael Beck's avatar
Michael Beck committed
514
    if (ivi->new_phi == NULL) {
Michael Beck's avatar
Michael Beck committed
515
      ivi->init = my_new_r_Sub(current_ir_graph,  block_init,
Michael Beck's avatar
Michael Beck committed
516
                               ivi->init, sub_const);
Michael Beck's avatar
Michael Beck committed
517
      if (ivi->cmp != NULL)
Michael Beck's avatar
Michael Beck committed
518
        ivi->cmp_const = my_new_r_Sub(current_ir_graph, ivi->cmp_init_block,
Michael Beck's avatar
Michael Beck committed
519
520
                                      ivi->cmp_const,sub_const);
    } else
Michael Beck's avatar
Michael Beck committed
521
      ivi->new_init = my_new_r_Sub (current_ir_graph, block_init,
Michael Beck's avatar
Michael Beck committed
522
                                    ivi->new_init, sub_const);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
523
    if (get_opt_strength_red_verbose() && get_firm_verbosity() > 1) {
Beyhan's avatar
Beyhan committed
524
525
      printf("\nReducing operation is : "); DDMN(reduce_var);
      printf("in graph : "); DDMG(current_ir_graph);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
526
    }
Beyhan's avatar
Beyhan committed
527
    return 1;
Michael Beck's avatar
Michael Beck committed
528
529
  }
  return 0;
Beyhan's avatar
Beyhan committed
530
}
Beyhan's avatar
Beyhan committed
531

Michael Beck's avatar
Michael Beck committed
532
/**
Beyhan's avatar
Beyhan committed
533
534
535
536
537
538
 * Search for reducible successor of iteration variable.
 * If such successor is found it will be reduced and returned,
 * else return NULL.
 *
 * @param ivi   Contains information about the induction variable.
 * @param out   A successor of iteration variable.
Michael Beck's avatar
Michael Beck committed
539
 */
Michael Beck's avatar
Michael Beck committed
540
541
static ir_node *reducible(ir_node *out, induct_var_info *ivi)
{
Beyhan's avatar
Beyhan committed
542
  ir_node *reduced = NULL;
Michael Beck's avatar
Michael Beck committed
543
  int pred;
Beyhan's avatar
Beyhan committed
544

Michael Beck's avatar
Michael Beck committed
545
546
547
548
549
550
  for (pred = 1; pred == 1; pred = get_irn_n_outs(out)) {
    if (reduce(out, ivi))
      reduced = out;
    else
      return reduced;
    out = get_irn_out(out, 0);
Beyhan's avatar
Beyhan committed
551
552
553
  }
  return reduced;
}
Michael Beck's avatar
Michael Beck committed
554

Beyhan's avatar
Beyhan committed
555
/**
Michael Beck's avatar
Michael Beck committed
556
557
 * Post walker: Find a Phi node that is a iteration variable and
 * try to reduce it.
Beyhan's avatar
Beyhan committed
558
 *
Michael Beck's avatar
Michael Beck committed
559
560
 * @param itervar_phi   The iteration variable of a loop.
 * @param env           Free environment pointer.
Beyhan's avatar
Beyhan committed
561
 */
Michael Beck's avatar
Michael Beck committed
562
563
static void reduce_itervar(ir_node *itervar_phi, void *env)
{
Beyhan's avatar
Beyhan committed
564
  induct_var_info ivi;
Beyhan's avatar
Beyhan committed
565
566
  /* check if a iteration variable be reduced.*/
  int reduced = 0;
Beyhan's avatar
Beyhan committed
567

Michael Beck's avatar
Michael Beck committed
568
569
  if (get_irn_op(itervar_phi) != op_Phi)
    return;
Beyhan's avatar
Beyhan committed
570
  /* A candidate is found.*/
Beyhan's avatar
Beyhan committed
571
  ivi.itervar_phi = itervar_phi;
Beyhan's avatar
Beyhan committed
572

Beyhan's avatar
Beyhan committed
573
  /* It musss be a induction variable.*/
Michael Beck's avatar
Michael Beck committed
574
575
576
577
578
  if (is_induction_variable(&ivi)) {
    int i, op_out;

    for (i = 0; i < ivi.phi_pred; i++) {
      ir_node *out = get_irn_out(ivi.itervar_phi, i);
Beyhan's avatar
Beyhan committed
579
      ir_op   *out_op = get_irn_op(out);
Beyhan's avatar
Beyhan committed
580
      /* Reduce a induction variable.*/
581
      if (ivi.is_reducible) {
Michael Beck's avatar
Michael Beck committed
582
        if (ivi.phi_pred == 3 && out != ivi.op && out != ivi.cmp) {
Beyhan's avatar
Beyhan committed
583
584
          ir_node *irn_reduced = reducible(out, &ivi);
          if (irn_reduced != NULL){
585
586
587
588
            reduced = 1;
            exchange(irn_reduced, ivi.itervar_phi);
          }
        }
Michael Beck's avatar
Michael Beck committed
589
      }
Beyhan's avatar
Beyhan committed
590
      /* Reduce a multiplication*/
Michael Beck's avatar
Michael Beck committed
591
      else if (out_op == op_Mul)
592
        if (reduce(out, &ivi) && ivi.is_reducible) {
Michael Beck's avatar
Michael Beck committed
593
          ir_node *reduced = reducible(ivi.reducible_node, &ivi);
Michael Beck's avatar
Michael Beck committed
594
595

          if (reduced != NULL)
Michael Beck's avatar
Michael Beck committed
596
            exchange(reduced, ivi.new_phi);
Michael Beck's avatar
Michael Beck committed
597

598
          ivi.is_reducible = 0;
Michael Beck's avatar
Michael Beck committed
599
600
601
602
          set_Phi_pred(ivi.new_phi, ivi.init_pred_pos, ivi.new_init);
          set_irn_mode(ivi.new_phi,get_irn_mode(ivi.new_init));
          set_irn_mode(ivi.new_op,get_irn_mode(ivi.new_phi));
        }
Beyhan's avatar
Beyhan committed
603
    }
Michael Beck's avatar
Michael Beck committed
604
605
606
607

    op_out = get_irn_n_outs(ivi.op);
    for (i = 0; i < op_out; i++){
      ir_node *out = get_irn_out(ivi.op, i);
Beyhan's avatar
Beyhan committed
608
      ir_op   *out_op = get_irn_op(out);
Beyhan's avatar
Beyhan committed
609
      /* Try to reduce the second successor of the "ivi.op"*/
Michael Beck's avatar
Michael Beck committed
610
      if (op_out == 2 && out != ivi.itervar_phi){
Michael Beck's avatar
Michael Beck committed
611
612
613
        ir_node *reduced = reducible(out, &ivi);
        if(reduced != NULL)
          exchange( reduced, ivi.op);
Michael Beck's avatar
Michael Beck committed
614
      }
Beyhan's avatar
Beyhan committed
615
      /* Try to reduce a multiplication, that is successor of "ivi.op".*/
Michael Beck's avatar
Michael Beck committed
616
      else if (out_op == op_Mul)
617
        if (reduce(out, &ivi) && ivi.is_reducible){
Michael Beck's avatar
Michael Beck committed
618
619
620
          ir_node *reduced = reducible(ivi.reducible_node, &ivi);
          if(reduced != NULL)
            exchange(reduced, ivi.new_phi);
621
          ivi.is_reducible = 0;
Michael Beck's avatar
Michael Beck committed
622
623
624
625
          set_Phi_pred(ivi.new_phi, ivi.init_pred_pos, ivi.new_init);
          set_irn_mode(ivi.new_phi,get_irn_mode(ivi.new_init));
          set_irn_mode(ivi.new_op,get_irn_mode(ivi.new_phi));
        }
Beyhan's avatar
Beyhan committed
626
    }
Beyhan's avatar
Beyhan committed
627
    /* Set some predecessors and modes after reduce.*/
628
    if (ivi.is_reducible && reduced) {
Beyhan's avatar
Beyhan committed
629
      if(get_irn_op(ivi.op) == op_Add)
Michael Beck's avatar
Michael Beck committed
630
631
632
633
        if(get_Add_left(ivi.op) == ivi.itervar_phi)
          set_Add_right(ivi.op, ivi.increment);
        else
          set_Add_left(ivi.op, ivi.increment);
Beyhan's avatar
Beyhan committed
634
      else if(get_Sub_left(ivi.op) == ivi.itervar_phi)
Michael Beck's avatar
Michael Beck committed
635
        set_Sub_right(ivi.op, ivi.increment);
Beyhan's avatar
Beyhan committed
636
      else
Michael Beck's avatar
Michael Beck committed
637
        set_Sub_right(ivi.op, ivi.increment);
Beyhan's avatar
Beyhan committed
638
639
640
641
      set_Phi_pred(ivi.itervar_phi, ivi.init_pred_pos, ivi.init);
      set_irn_mode(ivi.itervar_phi, get_irn_mode(ivi.init));
      set_irn_mode(ivi.op, get_irn_mode(ivi.itervar_phi));
      if (ivi.cmp != NULL){
Michael Beck's avatar
Michael Beck committed
642
643
644
645
646
        set_irn_mode(ivi.cmp_const, get_irn_mode(ivi.itervar_phi));
        if(get_Cmp_left(ivi.cmp) == ivi.itervar_phi)
          set_Cmp_right(ivi.cmp, ivi.cmp_const);
        else
          set_Cmp_left(ivi.cmp, ivi.cmp_const);
Beyhan's avatar
Beyhan committed
647
648
      }
    }
Michael Beck's avatar
Michael Beck committed
649
  }
650
651
652
653
}

/* Performs strength reduction for the passed graph. */
void reduce_strength(ir_graph *irg) {
Beyhan's avatar
Beyhan committed
654
  ir_graph *rem = current_ir_graph;
Michael Beck's avatar
Michael Beck committed
655
  int modifiyed = 1;
656

Beyhan's avatar
Beyhan committed
657
  if (!get_optimize() || !get_opt_strength_red()) return;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
658

Michael Beck's avatar
Michael Beck committed
659
660
  current_ir_graph = irg;

Götz Lindenmaier's avatar
Götz Lindenmaier committed
661
  n_reduced_expressions = 0;
Beyhan's avatar
Beyhan committed
662
  n_made_new_phis = 0;
663
664
665
666
  /* -- Precompute some information -- */
  /* Call algorithm that computes the backedges */
  construct_cf_backedges(irg);
  /* Call algorithm that computes the dominator trees. */
Michael Beck's avatar
Michael Beck committed
667
  assure_doms(irg);
Beyhan's avatar
Beyhan committed
668
  /* Call algorithm that computes the out edges */
Michael Beck's avatar
Michael Beck committed
669
  assure_irg_outs(irg);
Michael Beck's avatar
Michael Beck committed
670

671
  /* -- Search expressions that can be optimized -- */
Beyhan's avatar
Beyhan committed
672
  irg_walk_graph(irg, NULL, reduce_itervar, NULL);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
673

Götz Lindenmaier's avatar
Götz Lindenmaier committed
674
  if (get_opt_strength_red_verbose()) {
Beyhan's avatar
Beyhan committed
675
676
677
    printf ("\n %d made new_phis und  ", n_made_new_phis);
    printf("reduced %d iteration variables "
           "in \n graph %s.%s.\n", n_reduced_expressions,
Florian Liekweg's avatar
\!C99    
Florian Liekweg committed
678
679
       get_type_name(get_entity_owner(get_irg_entity(irg))),
       get_entity_name(get_irg_entity(irg)));
Götz Lindenmaier's avatar
Götz Lindenmaier committed
680
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
681

Michael Beck's avatar
Michael Beck committed
682
683
684
685
686
  if (modifiyed) {
    set_irg_outs_inconsistent(irg);
    set_irg_loopinfo_inconsistent(irg);
  }

Götz Lindenmaier's avatar
Götz Lindenmaier committed
687
  current_ir_graph = rem;
688
}