OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.2.2/] [gcc/] [loop-iv.c] - Blame information for rev 304

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* Rtl-level induction variable analysis.
2
   Copyright (C) 2004, 2005, 2007 Free Software Foundation, Inc.
3
 
4
This file is part of GCC.
5
 
6
GCC is free software; you can redistribute it and/or modify it
7
under the terms of the GNU General Public License as published by the
8
Free Software Foundation; either version 3, or (at your option) any
9
later version.
10
 
11
GCC is distributed in the hope that it will be useful, but WITHOUT
12
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14
for more details.
15
 
16
You should have received a copy of the GNU General Public License
17
along with GCC; see the file COPYING3.  If not see
18
<http://www.gnu.org/licenses/>.  */
19
 
20
/* This is a simple analysis of induction variables of the loop.  The major use
21
   is for determining the number of iterations of a loop for loop unrolling,
22
   doloop optimization and branch prediction.  The iv information is computed
23
   on demand.
24
 
25
   Induction variable is analyzed by walking the use-def chains.  When a biv
26
   is found, it is cached in the bivs hash table.  When register is proved
27
   to be a giv, its description is stored to DF_REF_DATA of the def reference.
28
 
29
   The analysis works always with one loop -- you must call
30
   iv_analysis_loop_init (loop) for it.  All the other functions then work with
31
   this loop.   When you need to work with another loop, just call
32
   iv_analysis_loop_init for it.  When you no longer need iv analysis, call
33
   iv_analysis_done () to clean up the memory.
34
 
35
   The available functions are:
36
 
37
   iv_analyze (insn, reg, iv): Stores the description of the induction variable
38
     corresponding to the use of register REG in INSN to IV.  Returns true if
39
     REG is an induction variable in INSN. false otherwise.
40
     If use of REG is not found in INSN, following insns are scanned (so that
41
     we may call this function on insn returned by get_condition).
42
   iv_analyze_result (insn, def, iv):  Stores to IV the description of the iv
43
     corresponding to DEF, which is a register defined in INSN.
44
   iv_analyze_expr (insn, rhs, mode, iv):  Stores to IV the description of iv
45
     corresponding to expression EXPR evaluated at INSN.  All registers used bu
46
     EXPR must also be used in INSN.
47
   iv_current_loop_df (): Returns the dataflow object for the current loop used
48
     by iv analysis.  */
49
 
50
#include "config.h"
51
#include "system.h"
52
#include "coretypes.h"
53
#include "tm.h"
54
#include "rtl.h"
55
#include "hard-reg-set.h"
56
#include "obstack.h"
57
#include "basic-block.h"
58
#include "cfgloop.h"
59
#include "expr.h"
60
#include "intl.h"
61
#include "output.h"
62
#include "toplev.h"
63
#include "df.h"
64
#include "hashtab.h"
65
 
66
/* Possible return values of iv_get_reaching_def.  */
67
 
68
enum iv_grd_result
69
{
70
  /* More than one reaching def, or reaching def that does not
71
     dominate the use.  */
72
  GRD_INVALID,
73
 
74
  /* The use is trivial invariant of the loop, i.e. is not changed
75
     inside the loop.  */
76
  GRD_INVARIANT,
77
 
78
  /* The use is reached by initial value and a value from the
79
     previous iteration.  */
80
  GRD_MAYBE_BIV,
81
 
82
  /* The use has single dominating def.  */
83
  GRD_SINGLE_DOM
84
};
85
 
86
/* Information about a biv.  */
87
 
88
struct biv_entry
89
{
90
  unsigned regno;       /* The register of the biv.  */
91
  struct rtx_iv iv;     /* Value of the biv.  */
92
};
93
 
94
/* Induction variable stored at the reference.  */
95
#define DF_REF_IV(REF) ((struct rtx_iv *) DF_REF_DATA (REF))
96
#define DF_REF_IV_SET(REF, IV) DF_REF_DATA (REF) = (IV)
97
 
98
/* The current loop.  */
99
 
100
static struct loop *current_loop;
101
 
102
/* Dataflow information for the current loop.  */
103
 
104
static struct df *df = NULL;
105
 
106
/* Bivs of the current loop.  */
107
 
108
static htab_t bivs;
109
 
110
/* Return the dataflow object for the current loop.  */
111
struct df *
112
iv_current_loop_df (void)
113
{
114
  return df;
115
}
116
 
117
static bool iv_analyze_op (rtx, rtx, struct rtx_iv *);
118
 
119
/* Dumps information about IV to FILE.  */
120
 
121
extern void dump_iv_info (FILE *, struct rtx_iv *);
122
void
123
dump_iv_info (FILE *file, struct rtx_iv *iv)
124
{
125
  if (!iv->base)
126
    {
127
      fprintf (file, "not simple");
128
      return;
129
    }
130
 
131
  if (iv->step == const0_rtx
132
      && !iv->first_special)
133
    fprintf (file, "invariant ");
134
 
135
  print_rtl (file, iv->base);
136
  if (iv->step != const0_rtx)
137
    {
138
      fprintf (file, " + ");
139
      print_rtl (file, iv->step);
140
      fprintf (file, " * iteration");
141
    }
142
  fprintf (file, " (in %s)", GET_MODE_NAME (iv->mode));
143
 
144
  if (iv->mode != iv->extend_mode)
145
    fprintf (file, " %s to %s",
146
             rtx_name[iv->extend],
147
             GET_MODE_NAME (iv->extend_mode));
148
 
149
  if (iv->mult != const1_rtx)
150
    {
151
      fprintf (file, " * ");
152
      print_rtl (file, iv->mult);
153
    }
154
  if (iv->delta != const0_rtx)
155
    {
156
      fprintf (file, " + ");
157
      print_rtl (file, iv->delta);
158
    }
159
  if (iv->first_special)
160
    fprintf (file, " (first special)");
161
}
162
 
163
/* Generates a subreg to get the least significant part of EXPR (in mode
164
   INNER_MODE) to OUTER_MODE.  */
165
 
166
rtx
167
lowpart_subreg (enum machine_mode outer_mode, rtx expr,
168
                enum machine_mode inner_mode)
169
{
170
  return simplify_gen_subreg (outer_mode, expr, inner_mode,
171
                              subreg_lowpart_offset (outer_mode, inner_mode));
172
}
173
 
174
/* Checks whether REG is a well-behaved register.  */
175
 
176
static bool
177
simple_reg_p (rtx reg)
178
{
179
  unsigned r;
180
 
181
  if (GET_CODE (reg) == SUBREG)
182
    {
183
      if (!subreg_lowpart_p (reg))
184
        return false;
185
      reg = SUBREG_REG (reg);
186
    }
187
 
188
  if (!REG_P (reg))
189
    return false;
190
 
191
  r = REGNO (reg);
192
  if (HARD_REGISTER_NUM_P (r))
193
    return false;
194
 
195
  if (GET_MODE_CLASS (GET_MODE (reg)) != MODE_INT)
196
    return false;
197
 
198
  return true;
199
}
200
 
201
/* Clears the information about ivs stored in df.  */
202
 
203
static void
204
clear_iv_info (void)
205
{
206
  unsigned i, n_defs = DF_DEFS_SIZE (df);
207
  struct rtx_iv *iv;
208
  struct df_ref *def;
209
 
210
  for (i = 0; i < n_defs; i++)
211
    {
212
      def = DF_DEFS_GET (df, i);
213
      iv = DF_REF_IV (def);
214
      if (!iv)
215
        continue;
216
      free (iv);
217
      DF_REF_IV_SET (def, NULL);
218
    }
219
 
220
  htab_empty (bivs);
221
}
222
 
223
/* Returns hash value for biv B.  */
224
 
225
static hashval_t
226
biv_hash (const void *b)
227
{
228
  return ((const struct biv_entry *) b)->regno;
229
}
230
 
231
/* Compares biv B and register R.  */
232
 
233
static int
234
biv_eq (const void *b, const void *r)
235
{
236
  return ((const struct biv_entry *) b)->regno == REGNO ((rtx) r);
237
}
238
 
239
/* Prepare the data for an induction variable analysis of a LOOP.  */
240
 
241
void
242
iv_analysis_loop_init (struct loop *loop)
243
{
244
  basic_block *body = get_loop_body_in_dom_order (loop), bb;
245
  bitmap blocks = BITMAP_ALLOC (NULL);
246
  unsigned i;
247
  bool first_time = (df == NULL);
248
 
249
  current_loop = loop;
250
 
251
  /* Clear the information from the analysis of the previous loop.  */
252
  if (first_time)
253
    {
254
      df = df_init (DF_HARD_REGS | DF_EQUIV_NOTES);
255
      df_chain_add_problem (df, DF_UD_CHAIN);
256
      bivs = htab_create (10, biv_hash, biv_eq, free);
257
    }
258
  else
259
    clear_iv_info ();
260
 
261
  for (i = 0; i < loop->num_nodes; i++)
262
    {
263
      bb = body[i];
264
      bitmap_set_bit (blocks, bb->index);
265
    }
266
  df_set_blocks (df, blocks);
267
  df_analyze (df);
268
  BITMAP_FREE (blocks);
269
  free (body);
270
}
271
 
272
/* Finds the definition of REG that dominates loop latch and stores
273
   it to DEF.  Returns false if there is not a single definition
274
   dominating the latch.  If REG has no definition in loop, DEF
275
   is set to NULL and true is returned.  */
276
 
277
static bool
278
latch_dominating_def (rtx reg, struct df_ref **def)
279
{
280
  struct df_ref *single_rd = NULL, *adef;
281
  unsigned regno = REGNO (reg);
282
  struct df_reg_info *reg_info = DF_REG_DEF_GET (df, regno);
283
  struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (df, current_loop->latch);
284
 
285
  for (adef = reg_info->reg_chain; adef; adef = adef->next_reg)
286
    {
287
      if (!bitmap_bit_p (bb_info->out, DF_REF_ID (adef)))
288
        continue;
289
 
290
      /* More than one reaching definition.  */
291
      if (single_rd)
292
        return false;
293
 
294
      if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef)))
295
        return false;
296
 
297
      single_rd = adef;
298
    }
299
 
300
  *def = single_rd;
301
  return true;
302
}
303
 
304
/* Gets definition of REG reaching its use in INSN and stores it to DEF.  */
305
 
306
static enum iv_grd_result
307
iv_get_reaching_def (rtx insn, rtx reg, struct df_ref **def)
308
{
309
  struct df_ref *use, *adef;
310
  basic_block def_bb, use_bb;
311
  rtx def_insn;
312
  bool dom_p;
313
 
314
  *def = NULL;
315
  if (!simple_reg_p (reg))
316
    return GRD_INVALID;
317
  if (GET_CODE (reg) == SUBREG)
318
    reg = SUBREG_REG (reg);
319
  gcc_assert (REG_P (reg));
320
 
321
  use = df_find_use (df, insn, reg);
322
  gcc_assert (use != NULL);
323
 
324
  if (!DF_REF_CHAIN (use))
325
    return GRD_INVARIANT;
326
 
327
  /* More than one reaching def.  */
328
  if (DF_REF_CHAIN (use)->next)
329
    return GRD_INVALID;
330
 
331
  adef = DF_REF_CHAIN (use)->ref;
332
  def_insn = DF_REF_INSN (adef);
333
  def_bb = DF_REF_BB (adef);
334
  use_bb = BLOCK_FOR_INSN (insn);
335
 
336
  if (use_bb == def_bb)
337
    dom_p = (DF_INSN_LUID (df, def_insn) < DF_INSN_LUID (df, insn));
338
  else
339
    dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb);
340
 
341
  if (dom_p)
342
    {
343
      *def = adef;
344
      return GRD_SINGLE_DOM;
345
    }
346
 
347
  /* The definition does not dominate the use.  This is still OK if
348
     this may be a use of a biv, i.e. if the def_bb dominates loop
349
     latch.  */
350
  if (just_once_each_iteration_p (current_loop, def_bb))
351
    return GRD_MAYBE_BIV;
352
 
353
  return GRD_INVALID;
354
}
355
 
356
/* Sets IV to invariant CST in MODE.  Always returns true (just for
357
   consistency with other iv manipulation functions that may fail).  */
358
 
359
static bool
360
iv_constant (struct rtx_iv *iv, rtx cst, enum machine_mode mode)
361
{
362
  if (mode == VOIDmode)
363
    mode = GET_MODE (cst);
364
 
365
  iv->mode = mode;
366
  iv->base = cst;
367
  iv->step = const0_rtx;
368
  iv->first_special = false;
369
  iv->extend = UNKNOWN;
370
  iv->extend_mode = iv->mode;
371
  iv->delta = const0_rtx;
372
  iv->mult = const1_rtx;
373
 
374
  return true;
375
}
376
 
377
/* Evaluates application of subreg to MODE on IV.  */
378
 
379
static bool
380
iv_subreg (struct rtx_iv *iv, enum machine_mode mode)
381
{
382
  /* If iv is invariant, just calculate the new value.  */
383
  if (iv->step == const0_rtx
384
      && !iv->first_special)
385
    {
386
      rtx val = get_iv_value (iv, const0_rtx);
387
      val = lowpart_subreg (mode, val, iv->extend_mode);
388
 
389
      iv->base = val;
390
      iv->extend = UNKNOWN;
391
      iv->mode = iv->extend_mode = mode;
392
      iv->delta = const0_rtx;
393
      iv->mult = const1_rtx;
394
      return true;
395
    }
396
 
397
  if (iv->extend_mode == mode)
398
    return true;
399
 
400
  if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (iv->mode))
401
    return false;
402
 
403
  iv->extend = UNKNOWN;
404
  iv->mode = mode;
405
 
406
  iv->base = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
407
                                  simplify_gen_binary (MULT, iv->extend_mode,
408
                                                       iv->base, iv->mult));
409
  iv->step = simplify_gen_binary (MULT, iv->extend_mode, iv->step, iv->mult);
410
  iv->mult = const1_rtx;
411
  iv->delta = const0_rtx;
412
  iv->first_special = false;
413
 
414
  return true;
415
}
416
 
417
/* Evaluates application of EXTEND to MODE on IV.  */
418
 
419
static bool
420
iv_extend (struct rtx_iv *iv, enum rtx_code extend, enum machine_mode mode)
421
{
422
  /* If iv is invariant, just calculate the new value.  */
423
  if (iv->step == const0_rtx
424
      && !iv->first_special)
425
    {
426
      rtx val = get_iv_value (iv, const0_rtx);
427
      val = simplify_gen_unary (extend, mode, val, iv->extend_mode);
428
 
429
      iv->base = val;
430
      iv->extend = UNKNOWN;
431
      iv->mode = iv->extend_mode = mode;
432
      iv->delta = const0_rtx;
433
      iv->mult = const1_rtx;
434
      return true;
435
    }
436
 
437
  if (mode != iv->extend_mode)
438
    return false;
439
 
440
  if (iv->extend != UNKNOWN
441
      && iv->extend != extend)
442
    return false;
443
 
444
  iv->extend = extend;
445
 
446
  return true;
447
}
448
 
449
/* Evaluates negation of IV.  */
450
 
451
static bool
452
iv_neg (struct rtx_iv *iv)
453
{
454
  if (iv->extend == UNKNOWN)
455
    {
456
      iv->base = simplify_gen_unary (NEG, iv->extend_mode,
457
                                     iv->base, iv->extend_mode);
458
      iv->step = simplify_gen_unary (NEG, iv->extend_mode,
459
                                     iv->step, iv->extend_mode);
460
    }
461
  else
462
    {
463
      iv->delta = simplify_gen_unary (NEG, iv->extend_mode,
464
                                      iv->delta, iv->extend_mode);
465
      iv->mult = simplify_gen_unary (NEG, iv->extend_mode,
466
                                     iv->mult, iv->extend_mode);
467
    }
468
 
469
  return true;
470
}
471
 
472
/* Evaluates addition or subtraction (according to OP) of IV1 to IV0.  */
473
 
474
static bool
475
iv_add (struct rtx_iv *iv0, struct rtx_iv *iv1, enum rtx_code op)
476
{
477
  enum machine_mode mode;
478
  rtx arg;
479
 
480
  /* Extend the constant to extend_mode of the other operand if necessary.  */
481
  if (iv0->extend == UNKNOWN
482
      && iv0->mode == iv0->extend_mode
483
      && iv0->step == const0_rtx
484
      && GET_MODE_SIZE (iv0->extend_mode) < GET_MODE_SIZE (iv1->extend_mode))
485
    {
486
      iv0->extend_mode = iv1->extend_mode;
487
      iv0->base = simplify_gen_unary (ZERO_EXTEND, iv0->extend_mode,
488
                                      iv0->base, iv0->mode);
489
    }
490
  if (iv1->extend == UNKNOWN
491
      && iv1->mode == iv1->extend_mode
492
      && iv1->step == const0_rtx
493
      && GET_MODE_SIZE (iv1->extend_mode) < GET_MODE_SIZE (iv0->extend_mode))
494
    {
495
      iv1->extend_mode = iv0->extend_mode;
496
      iv1->base = simplify_gen_unary (ZERO_EXTEND, iv1->extend_mode,
497
                                      iv1->base, iv1->mode);
498
    }
499
 
500
  mode = iv0->extend_mode;
501
  if (mode != iv1->extend_mode)
502
    return false;
503
 
504
  if (iv0->extend == UNKNOWN && iv1->extend == UNKNOWN)
505
    {
506
      if (iv0->mode != iv1->mode)
507
        return false;
508
 
509
      iv0->base = simplify_gen_binary (op, mode, iv0->base, iv1->base);
510
      iv0->step = simplify_gen_binary (op, mode, iv0->step, iv1->step);
511
 
512
      return true;
513
    }
514
 
515
  /* Handle addition of constant.  */
516
  if (iv1->extend == UNKNOWN
517
      && iv1->mode == mode
518
      && iv1->step == const0_rtx)
519
    {
520
      iv0->delta = simplify_gen_binary (op, mode, iv0->delta, iv1->base);
521
      return true;
522
    }
523
 
524
  if (iv0->extend == UNKNOWN
525
      && iv0->mode == mode
526
      && iv0->step == const0_rtx)
527
    {
528
      arg = iv0->base;
529
      *iv0 = *iv1;
530
      if (op == MINUS
531
          && !iv_neg (iv0))
532
        return false;
533
 
534
      iv0->delta = simplify_gen_binary (PLUS, mode, iv0->delta, arg);
535
      return true;
536
    }
537
 
538
  return false;
539
}
540
 
541
/* Evaluates multiplication of IV by constant CST.  */
542
 
543
static bool
544
iv_mult (struct rtx_iv *iv, rtx mby)
545
{
546
  enum machine_mode mode = iv->extend_mode;
547
 
548
  if (GET_MODE (mby) != VOIDmode
549
      && GET_MODE (mby) != mode)
550
    return false;
551
 
552
  if (iv->extend == UNKNOWN)
553
    {
554
      iv->base = simplify_gen_binary (MULT, mode, iv->base, mby);
555
      iv->step = simplify_gen_binary (MULT, mode, iv->step, mby);
556
    }
557
  else
558
    {
559
      iv->delta = simplify_gen_binary (MULT, mode, iv->delta, mby);
560
      iv->mult = simplify_gen_binary (MULT, mode, iv->mult, mby);
561
    }
562
 
563
  return true;
564
}
565
 
566
/* Evaluates shift of IV by constant CST.  */
567
 
568
static bool
569
iv_shift (struct rtx_iv *iv, rtx mby)
570
{
571
  enum machine_mode mode = iv->extend_mode;
572
 
573
  if (GET_MODE (mby) != VOIDmode
574
      && GET_MODE (mby) != mode)
575
    return false;
576
 
577
  if (iv->extend == UNKNOWN)
578
    {
579
      iv->base = simplify_gen_binary (ASHIFT, mode, iv->base, mby);
580
      iv->step = simplify_gen_binary (ASHIFT, mode, iv->step, mby);
581
    }
582
  else
583
    {
584
      iv->delta = simplify_gen_binary (ASHIFT, mode, iv->delta, mby);
585
      iv->mult = simplify_gen_binary (ASHIFT, mode, iv->mult, mby);
586
    }
587
 
588
  return true;
589
}
590
 
591
/* The recursive part of get_biv_step.  Gets the value of the single value
592
   defined by DEF wrto initial value of REG inside loop, in shape described
593
   at get_biv_step.  */
594
 
595
static bool
596
get_biv_step_1 (struct df_ref *def, rtx reg,
597
                rtx *inner_step, enum machine_mode *inner_mode,
598
                enum rtx_code *extend, enum machine_mode outer_mode,
599
                rtx *outer_step)
600
{
601
  rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
602
  rtx next, nextr, tmp;
603
  enum rtx_code code;
604
  rtx insn = DF_REF_INSN (def);
605
  struct df_ref *next_def;
606
  enum iv_grd_result res;
607
 
608
  set = single_set (insn);
609
  if (!set)
610
    return false;
611
 
612
  rhs = find_reg_equal_equiv_note (insn);
613
  if (rhs)
614
    rhs = XEXP (rhs, 0);
615
  else
616
    rhs = SET_SRC (set);
617
 
618
  code = GET_CODE (rhs);
619
  switch (code)
620
    {
621
    case SUBREG:
622
    case REG:
623
      next = rhs;
624
      break;
625
 
626
    case PLUS:
627
    case MINUS:
628
      op0 = XEXP (rhs, 0);
629
      op1 = XEXP (rhs, 1);
630
 
631
      if (code == PLUS && CONSTANT_P (op0))
632
        {
633
          tmp = op0; op0 = op1; op1 = tmp;
634
        }
635
 
636
      if (!simple_reg_p (op0)
637
          || !CONSTANT_P (op1))
638
        return false;
639
 
640
      if (GET_MODE (rhs) != outer_mode)
641
        {
642
          /* ppc64 uses expressions like
643
 
644
             (set x:SI (plus:SI (subreg:SI y:DI) 1)).
645
 
646
             this is equivalent to
647
 
648
             (set x':DI (plus:DI y:DI 1))
649
             (set x:SI (subreg:SI (x':DI)).  */
650
          if (GET_CODE (op0) != SUBREG)
651
            return false;
652
          if (GET_MODE (SUBREG_REG (op0)) != outer_mode)
653
            return false;
654
        }
655
 
656
      next = op0;
657
      break;
658
 
659
    case SIGN_EXTEND:
660
    case ZERO_EXTEND:
661
      if (GET_MODE (rhs) != outer_mode)
662
        return false;
663
 
664
      op0 = XEXP (rhs, 0);
665
      if (!simple_reg_p (op0))
666
        return false;
667
 
668
      next = op0;
669
      break;
670
 
671
    default:
672
      return false;
673
    }
674
 
675
  if (GET_CODE (next) == SUBREG)
676
    {
677
      if (!subreg_lowpart_p (next))
678
        return false;
679
 
680
      nextr = SUBREG_REG (next);
681
      if (GET_MODE (nextr) != outer_mode)
682
        return false;
683
    }
684
  else
685
    nextr = next;
686
 
687
  res = iv_get_reaching_def (insn, nextr, &next_def);
688
 
689
  if (res == GRD_INVALID || res == GRD_INVARIANT)
690
    return false;
691
 
692
  if (res == GRD_MAYBE_BIV)
693
    {
694
      if (!rtx_equal_p (nextr, reg))
695
        return false;
696
 
697
      *inner_step = const0_rtx;
698
      *extend = UNKNOWN;
699
      *inner_mode = outer_mode;
700
      *outer_step = const0_rtx;
701
    }
702
  else if (!get_biv_step_1 (next_def, reg,
703
                            inner_step, inner_mode, extend, outer_mode,
704
                            outer_step))
705
    return false;
706
 
707
  if (GET_CODE (next) == SUBREG)
708
    {
709
      enum machine_mode amode = GET_MODE (next);
710
 
711
      if (GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode))
712
        return false;
713
 
714
      *inner_mode = amode;
715
      *inner_step = simplify_gen_binary (PLUS, outer_mode,
716
                                         *inner_step, *outer_step);
717
      *outer_step = const0_rtx;
718
      *extend = UNKNOWN;
719
    }
720
 
721
  switch (code)
722
    {
723
    case REG:
724
    case SUBREG:
725
      break;
726
 
727
    case PLUS:
728
    case MINUS:
729
      if (*inner_mode == outer_mode
730
          /* See comment in previous switch.  */
731
          || GET_MODE (rhs) != outer_mode)
732
        *inner_step = simplify_gen_binary (code, outer_mode,
733
                                           *inner_step, op1);
734
      else
735
        *outer_step = simplify_gen_binary (code, outer_mode,
736
                                           *outer_step, op1);
737
      break;
738
 
739
    case SIGN_EXTEND:
740
    case ZERO_EXTEND:
741
      gcc_assert (GET_MODE (op0) == *inner_mode
742
                  && *extend == UNKNOWN
743
                  && *outer_step == const0_rtx);
744
 
745
      *extend = code;
746
      break;
747
 
748
    default:
749
      return false;
750
    }
751
 
752
  return true;
753
}
754
 
755
/* Gets the operation on register REG inside loop, in shape
756
 
757
   OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
758
 
759
   If the operation cannot be described in this shape, return false.
760
   LAST_DEF is the definition of REG that dominates loop latch.  */
761
 
762
static bool
763
get_biv_step (struct df_ref *last_def, rtx reg, rtx *inner_step,
764
              enum machine_mode *inner_mode, enum rtx_code *extend,
765
              enum machine_mode *outer_mode, rtx *outer_step)
766
{
767
  *outer_mode = GET_MODE (reg);
768
 
769
  if (!get_biv_step_1 (last_def, reg,
770
                       inner_step, inner_mode, extend, *outer_mode,
771
                       outer_step))
772
    return false;
773
 
774
  gcc_assert ((*inner_mode == *outer_mode) != (*extend != UNKNOWN));
775
  gcc_assert (*inner_mode != *outer_mode || *outer_step == const0_rtx);
776
 
777
  return true;
778
}
779
 
780
/* Records information that DEF is induction variable IV.  */
781
 
782
static void
783
record_iv (struct df_ref *def, struct rtx_iv *iv)
784
{
785
  struct rtx_iv *recorded_iv = XNEW (struct rtx_iv);
786
 
787
  *recorded_iv = *iv;
788
  DF_REF_IV_SET (def, recorded_iv);
789
}
790
 
791
/* If DEF was already analyzed for bivness, store the description of the biv to
792
   IV and return true.  Otherwise return false.  */
793
 
794
static bool
795
analyzed_for_bivness_p (rtx def, struct rtx_iv *iv)
796
{
797
  struct biv_entry *biv = htab_find_with_hash (bivs, def, REGNO (def));
798
 
799
  if (!biv)
800
    return false;
801
 
802
  *iv = biv->iv;
803
  return true;
804
}
805
 
806
static void
807
record_biv (rtx def, struct rtx_iv *iv)
808
{
809
  struct biv_entry *biv = XNEW (struct biv_entry);
810
  void **slot = htab_find_slot_with_hash (bivs, def, REGNO (def), INSERT);
811
 
812
  biv->regno = REGNO (def);
813
  biv->iv = *iv;
814
  gcc_assert (!*slot);
815
  *slot = biv;
816
}
817
 
818
/* Determines whether DEF is a biv and if so, stores its description
819
   to *IV.  */
820
 
821
static bool
822
iv_analyze_biv (rtx def, struct rtx_iv *iv)
823
{
824
  rtx inner_step, outer_step;
825
  enum machine_mode inner_mode, outer_mode;
826
  enum rtx_code extend;
827
  struct df_ref *last_def;
828
 
829
  if (dump_file)
830
    {
831
      fprintf (dump_file, "Analyzing ");
832
      print_rtl (dump_file, def);
833
      fprintf (dump_file, " for bivness.\n");
834
    }
835
 
836
  if (!REG_P (def))
837
    {
838
      if (!CONSTANT_P (def))
839
        return false;
840
 
841
      return iv_constant (iv, def, VOIDmode);
842
    }
843
 
844
  if (!latch_dominating_def (def, &last_def))
845
    {
846
      if (dump_file)
847
        fprintf (dump_file, "  not simple.\n");
848
      return false;
849
    }
850
 
851
  if (!last_def)
852
    return iv_constant (iv, def, VOIDmode);
853
 
854
  if (analyzed_for_bivness_p (def, iv))
855
    {
856
      if (dump_file)
857
        fprintf (dump_file, "  already analysed.\n");
858
      return iv->base != NULL_RTX;
859
    }
860
 
861
  if (!get_biv_step (last_def, def, &inner_step, &inner_mode, &extend,
862
                     &outer_mode, &outer_step))
863
    {
864
      iv->base = NULL_RTX;
865
      goto end;
866
    }
867
 
868
  /* Loop transforms base to es (base + inner_step) + outer_step,
869
     where es means extend of subreg between inner_mode and outer_mode.
870
     The corresponding induction variable is
871
 
872
     es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step  */
873
 
874
  iv->base = simplify_gen_binary (MINUS, outer_mode, def, outer_step);
875
  iv->step = simplify_gen_binary (PLUS, outer_mode, inner_step, outer_step);
876
  iv->mode = inner_mode;
877
  iv->extend_mode = outer_mode;
878
  iv->extend = extend;
879
  iv->mult = const1_rtx;
880
  iv->delta = outer_step;
881
  iv->first_special = inner_mode != outer_mode;
882
 
883
 end:
884
  if (dump_file)
885
    {
886
      fprintf (dump_file, "  ");
887
      dump_iv_info (dump_file, iv);
888
      fprintf (dump_file, "\n");
889
    }
890
 
891
  record_biv (def, iv);
892
  return iv->base != NULL_RTX;
893
}
894
 
895
/* Analyzes expression RHS used at INSN and stores the result to *IV.
896
   The mode of the induction variable is MODE.  */
897
 
898
bool
899
iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv)
900
{
901
  rtx mby = NULL_RTX, tmp;
902
  rtx op0 = NULL_RTX, op1 = NULL_RTX;
903
  struct rtx_iv iv0, iv1;
904
  enum rtx_code code = GET_CODE (rhs);
905
  enum machine_mode omode = mode;
906
 
907
  iv->mode = VOIDmode;
908
  iv->base = NULL_RTX;
909
  iv->step = NULL_RTX;
910
 
911
  gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode);
912
 
913
  if (CONSTANT_P (rhs)
914
      || REG_P (rhs)
915
      || code == SUBREG)
916
    {
917
      if (!iv_analyze_op (insn, rhs, iv))
918
        return false;
919
 
920
      if (iv->mode == VOIDmode)
921
        {
922
          iv->mode = mode;
923
          iv->extend_mode = mode;
924
        }
925
 
926
      return true;
927
    }
928
 
929
  switch (code)
930
    {
931
    case REG:
932
      op0 = rhs;
933
      break;
934
 
935
    case SIGN_EXTEND:
936
    case ZERO_EXTEND:
937
    case NEG:
938
      op0 = XEXP (rhs, 0);
939
      omode = GET_MODE (op0);
940
      break;
941
 
942
    case PLUS:
943
    case MINUS:
944
      op0 = XEXP (rhs, 0);
945
      op1 = XEXP (rhs, 1);
946
      break;
947
 
948
    case MULT:
949
      op0 = XEXP (rhs, 0);
950
      mby = XEXP (rhs, 1);
951
      if (!CONSTANT_P (mby))
952
        {
953
          tmp = op0;
954
          op0 = mby;
955
          mby = tmp;
956
        }
957
      if (!CONSTANT_P (mby))
958
        return false;
959
      break;
960
 
961
    case ASHIFT:
962
      op0 = XEXP (rhs, 0);
963
      mby = XEXP (rhs, 1);
964
      if (!CONSTANT_P (mby))
965
        return false;
966
      break;
967
 
968
    default:
969
      return false;
970
    }
971
 
972
  if (op0
973
      && !iv_analyze_expr (insn, op0, omode, &iv0))
974
    return false;
975
 
976
  if (op1
977
      && !iv_analyze_expr (insn, op1, omode, &iv1))
978
    return false;
979
 
980
  switch (code)
981
    {
982
    case SIGN_EXTEND:
983
    case ZERO_EXTEND:
984
      if (!iv_extend (&iv0, code, mode))
985
        return false;
986
      break;
987
 
988
    case NEG:
989
      if (!iv_neg (&iv0))
990
        return false;
991
      break;
992
 
993
    case PLUS:
994
    case MINUS:
995
      if (!iv_add (&iv0, &iv1, code))
996
        return false;
997
      break;
998
 
999
    case MULT:
1000
      if (!iv_mult (&iv0, mby))
1001
        return false;
1002
      break;
1003
 
1004
    case ASHIFT:
1005
      if (!iv_shift (&iv0, mby))
1006
        return false;
1007
      break;
1008
 
1009
    default:
1010
      break;
1011
    }
1012
 
1013
  *iv = iv0;
1014
  return iv->base != NULL_RTX;
1015
}
1016
 
1017
/* Analyzes iv DEF and stores the result to *IV.  */
1018
 
1019
static bool
1020
iv_analyze_def (struct df_ref *def, struct rtx_iv *iv)
1021
{
1022
  rtx insn = DF_REF_INSN (def);
1023
  rtx reg = DF_REF_REG (def);
1024
  rtx set, rhs;
1025
 
1026
  if (dump_file)
1027
    {
1028
      fprintf (dump_file, "Analysing def of ");
1029
      print_rtl (dump_file, reg);
1030
      fprintf (dump_file, " in insn ");
1031
      print_rtl_single (dump_file, insn);
1032
    }
1033
 
1034
  if (DF_REF_IV (def))
1035
    {
1036
      if (dump_file)
1037
        fprintf (dump_file, "  already analysed.\n");
1038
      *iv = *DF_REF_IV (def);
1039
      return iv->base != NULL_RTX;
1040
    }
1041
 
1042
  iv->mode = VOIDmode;
1043
  iv->base = NULL_RTX;
1044
  iv->step = NULL_RTX;
1045
 
1046
  set = single_set (insn);
1047
  if (!set || SET_DEST (set) != reg)
1048
    return false;
1049
 
1050
  rhs = find_reg_equal_equiv_note (insn);
1051
  if (rhs)
1052
    rhs = XEXP (rhs, 0);
1053
  else
1054
    rhs = SET_SRC (set);
1055
 
1056
  iv_analyze_expr (insn, rhs, GET_MODE (reg), iv);
1057
  record_iv (def, iv);
1058
 
1059
  if (dump_file)
1060
    {
1061
      print_rtl (dump_file, reg);
1062
      fprintf (dump_file, " in insn ");
1063
      print_rtl_single (dump_file, insn);
1064
      fprintf (dump_file, "  is ");
1065
      dump_iv_info (dump_file, iv);
1066
      fprintf (dump_file, "\n");
1067
    }
1068
 
1069
  return iv->base != NULL_RTX;
1070
}
1071
 
1072
/* Analyzes operand OP of INSN and stores the result to *IV.  */
1073
 
1074
static bool
1075
iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv)
1076
{
1077
  struct df_ref *def = NULL;
1078
  enum iv_grd_result res;
1079
 
1080
  if (dump_file)
1081
    {
1082
      fprintf (dump_file, "Analysing operand ");
1083
      print_rtl (dump_file, op);
1084
      fprintf (dump_file, " of insn ");
1085
      print_rtl_single (dump_file, insn);
1086
    }
1087
 
1088
  if (CONSTANT_P (op))
1089
    res = GRD_INVARIANT;
1090
  else if (GET_CODE (op) == SUBREG)
1091
    {
1092
      if (!subreg_lowpart_p (op))
1093
        return false;
1094
 
1095
      if (!iv_analyze_op (insn, SUBREG_REG (op), iv))
1096
        return false;
1097
 
1098
      return iv_subreg (iv, GET_MODE (op));
1099
    }
1100
  else
1101
    {
1102
      res = iv_get_reaching_def (insn, op, &def);
1103
      if (res == GRD_INVALID)
1104
        {
1105
          if (dump_file)
1106
            fprintf (dump_file, "  not simple.\n");
1107
          return false;
1108
        }
1109
    }
1110
 
1111
  if (res == GRD_INVARIANT)
1112
    {
1113
      iv_constant (iv, op, VOIDmode);
1114
 
1115
      if (dump_file)
1116
        {
1117
          fprintf (dump_file, "  ");
1118
          dump_iv_info (dump_file, iv);
1119
          fprintf (dump_file, "\n");
1120
        }
1121
      return true;
1122
    }
1123
 
1124
  if (res == GRD_MAYBE_BIV)
1125
    return iv_analyze_biv (op, iv);
1126
 
1127
  return iv_analyze_def (def, iv);
1128
}
1129
 
1130
/* Analyzes value VAL at INSN and stores the result to *IV.  */
1131
 
1132
bool
1133
iv_analyze (rtx insn, rtx val, struct rtx_iv *iv)
1134
{
1135
  rtx reg;
1136
 
1137
  /* We must find the insn in that val is used, so that we get to UD chains.
1138
     Since the function is sometimes called on result of get_condition,
1139
     this does not necessarily have to be directly INSN; scan also the
1140
     following insns.  */
1141
  if (simple_reg_p (val))
1142
    {
1143
      if (GET_CODE (val) == SUBREG)
1144
        reg = SUBREG_REG (val);
1145
      else
1146
        reg = val;
1147
 
1148
      while (!df_find_use (df, insn, reg))
1149
        insn = NEXT_INSN (insn);
1150
    }
1151
 
1152
  return iv_analyze_op (insn, val, iv);
1153
}
1154
 
1155
/* Analyzes definition of DEF in INSN and stores the result to IV.  */
1156
 
1157
bool
1158
iv_analyze_result (rtx insn, rtx def, struct rtx_iv *iv)
1159
{
1160
  struct df_ref *adef;
1161
 
1162
  adef = df_find_def (df, insn, def);
1163
  if (!adef)
1164
    return false;
1165
 
1166
  return iv_analyze_def (adef, iv);
1167
}
1168
 
1169
/* Checks whether definition of register REG in INSN is a basic induction
1170
   variable.  IV analysis must have been initialized (via a call to
1171
   iv_analysis_loop_init) for this function to produce a result.  */
1172
 
1173
bool
1174
biv_p (rtx insn, rtx reg)
1175
{
1176
  struct rtx_iv iv;
1177
  struct df_ref *def, *last_def;
1178
 
1179
  if (!simple_reg_p (reg))
1180
    return false;
1181
 
1182
  def = df_find_def (df, insn, reg);
1183
  gcc_assert (def != NULL);
1184
  if (!latch_dominating_def (reg, &last_def))
1185
    return false;
1186
  if (last_def != def)
1187
    return false;
1188
 
1189
  if (!iv_analyze_biv (reg, &iv))
1190
    return false;
1191
 
1192
  return iv.step != const0_rtx;
1193
}
1194
 
1195
/* Calculates value of IV at ITERATION-th iteration.  */
1196
 
1197
rtx
1198
get_iv_value (struct rtx_iv *iv, rtx iteration)
1199
{
1200
  rtx val;
1201
 
1202
  /* We would need to generate some if_then_else patterns, and so far
1203
     it is not needed anywhere.  */
1204
  gcc_assert (!iv->first_special);
1205
 
1206
  if (iv->step != const0_rtx && iteration != const0_rtx)
1207
    val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base,
1208
                               simplify_gen_binary (MULT, iv->extend_mode,
1209
                                                    iv->step, iteration));
1210
  else
1211
    val = iv->base;
1212
 
1213
  if (iv->extend_mode == iv->mode)
1214
    return val;
1215
 
1216
  val = lowpart_subreg (iv->mode, val, iv->extend_mode);
1217
 
1218
  if (iv->extend == UNKNOWN)
1219
    return val;
1220
 
1221
  val = simplify_gen_unary (iv->extend, iv->extend_mode, val, iv->mode);
1222
  val = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
1223
                             simplify_gen_binary (MULT, iv->extend_mode,
1224
                                                  iv->mult, val));
1225
 
1226
  return val;
1227
}
1228
 
1229
/* Free the data for an induction variable analysis.  */
1230
 
1231
void
1232
iv_analysis_done (void)
1233
{
1234
  if (df)
1235
    {
1236
      clear_iv_info ();
1237
      df_finish (df);
1238
      df = NULL;
1239
      htab_delete (bivs);
1240
      bivs = NULL;
1241
    }
1242
}
1243
 
1244
/* Computes inverse to X modulo (1 << MOD).  */
1245
 
1246
static unsigned HOST_WIDEST_INT
1247
inverse (unsigned HOST_WIDEST_INT x, int mod)
1248
{
1249
  unsigned HOST_WIDEST_INT mask =
1250
          ((unsigned HOST_WIDEST_INT) 1 << (mod - 1) << 1) - 1;
1251
  unsigned HOST_WIDEST_INT rslt = 1;
1252
  int i;
1253
 
1254
  for (i = 0; i < mod - 1; i++)
1255
    {
1256
      rslt = (rslt * x) & mask;
1257
      x = (x * x) & mask;
1258
    }
1259
 
1260
  return rslt;
1261
}
1262
 
1263
/* Tries to estimate the maximum number of iterations.  */
1264
 
1265
static unsigned HOST_WIDEST_INT
1266
determine_max_iter (struct niter_desc *desc)
1267
{
1268
  rtx niter = desc->niter_expr;
1269
  rtx mmin, mmax, left, right;
1270
  unsigned HOST_WIDEST_INT nmax, inc;
1271
 
1272
  if (GET_CODE (niter) == AND
1273
      && GET_CODE (XEXP (niter, 0)) == CONST_INT)
1274
    {
1275
      nmax = INTVAL (XEXP (niter, 0));
1276
      if (!(nmax & (nmax + 1)))
1277
        {
1278
          desc->niter_max = nmax;
1279
          return nmax;
1280
        }
1281
    }
1282
 
1283
  get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
1284
  nmax = INTVAL (mmax) - INTVAL (mmin);
1285
 
1286
  if (GET_CODE (niter) == UDIV)
1287
    {
1288
      if (GET_CODE (XEXP (niter, 1)) != CONST_INT)
1289
        {
1290
          desc->niter_max = nmax;
1291
          return nmax;
1292
        }
1293
      inc = INTVAL (XEXP (niter, 1));
1294
      niter = XEXP (niter, 0);
1295
    }
1296
  else
1297
    inc = 1;
1298
 
1299
  if (GET_CODE (niter) == PLUS)
1300
    {
1301
      left = XEXP (niter, 0);
1302
      right = XEXP (niter, 0);
1303
 
1304
      if (GET_CODE (right) == CONST_INT)
1305
        right = GEN_INT (-INTVAL (right));
1306
    }
1307
  else if (GET_CODE (niter) == MINUS)
1308
    {
1309
      left = XEXP (niter, 0);
1310
      right = XEXP (niter, 0);
1311
    }
1312
  else
1313
    {
1314
      left = niter;
1315
      right = mmin;
1316
    }
1317
 
1318
  if (GET_CODE (left) == CONST_INT)
1319
    mmax = left;
1320
  if (GET_CODE (right) == CONST_INT)
1321
    mmin = right;
1322
  nmax = INTVAL (mmax) - INTVAL (mmin);
1323
 
1324
  desc->niter_max = nmax / inc;
1325
  return nmax / inc;
1326
}
1327
 
1328
/* Checks whether register *REG is in set ALT.  Callback for for_each_rtx.  */
1329
 
1330
static int
1331
altered_reg_used (rtx *reg, void *alt)
1332
{
1333
  if (!REG_P (*reg))
1334
    return 0;
1335
 
1336
  return REGNO_REG_SET_P (alt, REGNO (*reg));
1337
}
1338
 
1339
/* Marks registers altered by EXPR in set ALT.  */
1340
 
1341
static void
1342
mark_altered (rtx expr, rtx by ATTRIBUTE_UNUSED, void *alt)
1343
{
1344
  if (GET_CODE (expr) == SUBREG)
1345
    expr = SUBREG_REG (expr);
1346
  if (!REG_P (expr))
1347
    return;
1348
 
1349
  SET_REGNO_REG_SET (alt, REGNO (expr));
1350
}
1351
 
1352
/* Checks whether RHS is simple enough to process.  */
1353
 
1354
static bool
1355
simple_rhs_p (rtx rhs)
1356
{
1357
  rtx op0, op1;
1358
 
1359
  if (CONSTANT_P (rhs)
1360
      || REG_P (rhs))
1361
    return true;
1362
 
1363
  switch (GET_CODE (rhs))
1364
    {
1365
    case PLUS:
1366
    case MINUS:
1367
      op0 = XEXP (rhs, 0);
1368
      op1 = XEXP (rhs, 1);
1369
      /* Allow reg + const sets only.  */
1370
      if (REG_P (op0) && CONSTANT_P (op1))
1371
        return true;
1372
      if (REG_P (op1) && CONSTANT_P (op0))
1373
        return true;
1374
 
1375
      return false;
1376
 
1377
    default:
1378
      return false;
1379
    }
1380
}
1381
 
1382
/* Simplifies *EXPR using assignment in INSN.  ALTERED is the set of registers
1383
   altered so far.  */
1384
 
1385
static void
1386
simplify_using_assignment (rtx insn, rtx *expr, regset altered)
1387
{
1388
  rtx set = single_set (insn);
1389
  rtx lhs = NULL_RTX, rhs;
1390
  bool ret = false;
1391
 
1392
  if (set)
1393
    {
1394
      lhs = SET_DEST (set);
1395
      if (!REG_P (lhs)
1396
          || altered_reg_used (&lhs, altered))
1397
        ret = true;
1398
    }
1399
  else
1400
    ret = true;
1401
 
1402
  note_stores (PATTERN (insn), mark_altered, altered);
1403
  if (CALL_P (insn))
1404
    {
1405
      int i;
1406
 
1407
      /* Kill all call clobbered registers.  */
1408
      for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1409
        if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1410
          SET_REGNO_REG_SET (altered, i);
1411
    }
1412
 
1413
  if (ret)
1414
    return;
1415
 
1416
  rhs = find_reg_equal_equiv_note (insn);
1417
  if (rhs)
1418
    rhs = XEXP (rhs, 0);
1419
  else
1420
    rhs = SET_SRC (set);
1421
 
1422
  if (!simple_rhs_p (rhs))
1423
    return;
1424
 
1425
  if (for_each_rtx (&rhs, altered_reg_used, altered))
1426
    return;
1427
 
1428
  *expr = simplify_replace_rtx (*expr, lhs, rhs);
1429
}
1430
 
1431
/* Checks whether A implies B.  */
1432
 
1433
static bool
1434
implies_p (rtx a, rtx b)
1435
{
1436
  rtx op0, op1, opb0, opb1, r;
1437
  enum machine_mode mode;
1438
 
1439
  if (GET_CODE (a) == EQ)
1440
    {
1441
      op0 = XEXP (a, 0);
1442
      op1 = XEXP (a, 1);
1443
 
1444
      if (REG_P (op0))
1445
        {
1446
          r = simplify_replace_rtx (b, op0, op1);
1447
          if (r == const_true_rtx)
1448
            return true;
1449
        }
1450
 
1451
      if (REG_P (op1))
1452
        {
1453
          r = simplify_replace_rtx (b, op1, op0);
1454
          if (r == const_true_rtx)
1455
            return true;
1456
        }
1457
    }
1458
 
1459
  /* A < B implies A + 1 <= B.  */
1460
  if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
1461
      && (GET_CODE (b) == GE || GET_CODE (b) == LE))
1462
    {
1463
      op0 = XEXP (a, 0);
1464
      op1 = XEXP (a, 1);
1465
      opb0 = XEXP (b, 0);
1466
      opb1 = XEXP (b, 1);
1467
 
1468
      if (GET_CODE (a) == GT)
1469
        {
1470
          r = op0;
1471
          op0 = op1;
1472
          op1 = r;
1473
        }
1474
 
1475
      if (GET_CODE (b) == GE)
1476
        {
1477
          r = opb0;
1478
          opb0 = opb1;
1479
          opb1 = r;
1480
        }
1481
 
1482
      mode = GET_MODE (op0);
1483
      if (mode != GET_MODE (opb0))
1484
        mode = VOIDmode;
1485
      else if (mode == VOIDmode)
1486
        {
1487
          mode = GET_MODE (op1);
1488
          if (mode != GET_MODE (opb1))
1489
            mode = VOIDmode;
1490
        }
1491
 
1492
      if (SCALAR_INT_MODE_P (mode)
1493
          && rtx_equal_p (op1, opb1)
1494
          && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
1495
        return true;
1496
    }
1497
 
1498
  return false;
1499
}
1500
 
1501
/* Canonicalizes COND so that
1502
 
1503
   (1) Ensure that operands are ordered according to
1504
       swap_commutative_operands_p.
1505
   (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1506
       for GE, GEU, and LEU.  */
1507
 
1508
rtx
1509
canon_condition (rtx cond)
1510
{
1511
  rtx tem;
1512
  rtx op0, op1;
1513
  enum rtx_code code;
1514
  enum machine_mode mode;
1515
 
1516
  code = GET_CODE (cond);
1517
  op0 = XEXP (cond, 0);
1518
  op1 = XEXP (cond, 1);
1519
 
1520
  if (swap_commutative_operands_p (op0, op1))
1521
    {
1522
      code = swap_condition (code);
1523
      tem = op0;
1524
      op0 = op1;
1525
      op1 = tem;
1526
    }
1527
 
1528
  mode = GET_MODE (op0);
1529
  if (mode == VOIDmode)
1530
    mode = GET_MODE (op1);
1531
  gcc_assert (mode != VOIDmode);
1532
 
1533
  if (GET_CODE (op1) == CONST_INT
1534
      && GET_MODE_CLASS (mode) != MODE_CC
1535
      && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
1536
    {
1537
      HOST_WIDE_INT const_val = INTVAL (op1);
1538
      unsigned HOST_WIDE_INT uconst_val = const_val;
1539
      unsigned HOST_WIDE_INT max_val
1540
        = (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode);
1541
 
1542
      switch (code)
1543
        {
1544
        case LE:
1545
          if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
1546
            code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0));
1547
          break;
1548
 
1549
        /* When cross-compiling, const_val might be sign-extended from
1550
           BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1551
        case GE:
1552
          if ((HOST_WIDE_INT) (const_val & max_val)
1553
              != (((HOST_WIDE_INT) 1
1554
                   << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
1555
            code = GT, op1 = gen_int_mode (const_val - 1, mode);
1556
          break;
1557
 
1558
        case LEU:
1559
          if (uconst_val < max_val)
1560
            code = LTU, op1 = gen_int_mode (uconst_val + 1, mode);
1561
          break;
1562
 
1563
        case GEU:
1564
          if (uconst_val != 0)
1565
            code = GTU, op1 = gen_int_mode (uconst_val - 1, mode);
1566
          break;
1567
 
1568
        default:
1569
          break;
1570
        }
1571
    }
1572
 
1573
  if (op0 != XEXP (cond, 0)
1574
      || op1 != XEXP (cond, 1)
1575
      || code != GET_CODE (cond)
1576
      || GET_MODE (cond) != SImode)
1577
    cond = gen_rtx_fmt_ee (code, SImode, op0, op1);
1578
 
1579
  return cond;
1580
}
1581
 
1582
/* Tries to use the fact that COND holds to simplify EXPR.  ALTERED is the
1583
   set of altered regs.  */
1584
 
1585
void
1586
simplify_using_condition (rtx cond, rtx *expr, regset altered)
1587
{
1588
  rtx rev, reve, exp = *expr;
1589
 
1590
  if (!COMPARISON_P (exp))
1591
    return;
1592
 
1593
  /* If some register gets altered later, we do not really speak about its
1594
     value at the time of comparison.  */
1595
  if (altered
1596
      && for_each_rtx (&cond, altered_reg_used, altered))
1597
    return;
1598
 
1599
  rev = reversed_condition (cond);
1600
  reve = reversed_condition (exp);
1601
 
1602
  cond = canon_condition (cond);
1603
  exp = canon_condition (exp);
1604
  if (rev)
1605
    rev = canon_condition (rev);
1606
  if (reve)
1607
    reve = canon_condition (reve);
1608
 
1609
  if (rtx_equal_p (exp, cond))
1610
    {
1611
      *expr = const_true_rtx;
1612
      return;
1613
    }
1614
 
1615
 
1616
  if (rev && rtx_equal_p (exp, rev))
1617
    {
1618
      *expr = const0_rtx;
1619
      return;
1620
    }
1621
 
1622
  if (implies_p (cond, exp))
1623
    {
1624
      *expr = const_true_rtx;
1625
      return;
1626
    }
1627
 
1628
  if (reve && implies_p (cond, reve))
1629
    {
1630
      *expr = const0_rtx;
1631
      return;
1632
    }
1633
 
1634
  /* A proof by contradiction.  If *EXPR implies (not cond), *EXPR must
1635
     be false.  */
1636
  if (rev && implies_p (exp, rev))
1637
    {
1638
      *expr = const0_rtx;
1639
      return;
1640
    }
1641
 
1642
  /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true.  */
1643
  if (rev && reve && implies_p (reve, rev))
1644
    {
1645
      *expr = const_true_rtx;
1646
      return;
1647
    }
1648
 
1649
  /* We would like to have some other tests here.  TODO.  */
1650
 
1651
  return;
1652
}
1653
 
1654
/* Use relationship between A and *B to eventually eliminate *B.
1655
   OP is the operation we consider.  */
1656
 
1657
static void
1658
eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
1659
{
1660
  switch (op)
1661
    {
1662
    case AND:
1663
      /* If A implies *B, we may replace *B by true.  */
1664
      if (implies_p (a, *b))
1665
        *b = const_true_rtx;
1666
      break;
1667
 
1668
    case IOR:
1669
      /* If *B implies A, we may replace *B by false.  */
1670
      if (implies_p (*b, a))
1671
        *b = const0_rtx;
1672
      break;
1673
 
1674
    default:
1675
      gcc_unreachable ();
1676
    }
1677
}
1678
 
1679
/* Eliminates the conditions in TAIL that are implied by HEAD.  OP is the
1680
   operation we consider.  */
1681
 
1682
static void
1683
eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
1684
{
1685
  rtx elt;
1686
 
1687
  for (elt = tail; elt; elt = XEXP (elt, 1))
1688
    eliminate_implied_condition (op, *head, &XEXP (elt, 0));
1689
  for (elt = tail; elt; elt = XEXP (elt, 1))
1690
    eliminate_implied_condition (op, XEXP (elt, 0), head);
1691
}
1692
 
1693
/* Simplifies *EXPR using initial values at the start of the LOOP.  If *EXPR
1694
   is a list, its elements are assumed to be combined using OP.  */
1695
 
1696
static void
1697
simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
1698
{
1699
  rtx head, tail, insn;
1700
  rtx neutral, aggr;
1701
  regset altered;
1702
  edge e;
1703
 
1704
  if (!*expr)
1705
    return;
1706
 
1707
  if (CONSTANT_P (*expr))
1708
    return;
1709
 
1710
  if (GET_CODE (*expr) == EXPR_LIST)
1711
    {
1712
      head = XEXP (*expr, 0);
1713
      tail = XEXP (*expr, 1);
1714
 
1715
      eliminate_implied_conditions (op, &head, tail);
1716
 
1717
      switch (op)
1718
        {
1719
        case AND:
1720
          neutral = const_true_rtx;
1721
          aggr = const0_rtx;
1722
          break;
1723
 
1724
        case IOR:
1725
          neutral = const0_rtx;
1726
          aggr = const_true_rtx;
1727
          break;
1728
 
1729
        default:
1730
          gcc_unreachable ();
1731
        }
1732
 
1733
      simplify_using_initial_values (loop, UNKNOWN, &head);
1734
      if (head == aggr)
1735
        {
1736
          XEXP (*expr, 0) = aggr;
1737
          XEXP (*expr, 1) = NULL_RTX;
1738
          return;
1739
        }
1740
      else if (head == neutral)
1741
        {
1742
          *expr = tail;
1743
          simplify_using_initial_values (loop, op, expr);
1744
          return;
1745
        }
1746
      simplify_using_initial_values (loop, op, &tail);
1747
 
1748
      if (tail && XEXP (tail, 0) == aggr)
1749
        {
1750
          *expr = tail;
1751
          return;
1752
        }
1753
 
1754
      XEXP (*expr, 0) = head;
1755
      XEXP (*expr, 1) = tail;
1756
      return;
1757
    }
1758
 
1759
  gcc_assert (op == UNKNOWN);
1760
 
1761
  e = loop_preheader_edge (loop);
1762
  if (e->src == ENTRY_BLOCK_PTR)
1763
    return;
1764
 
1765
  altered = ALLOC_REG_SET (&reg_obstack);
1766
 
1767
  while (1)
1768
    {
1769
      insn = BB_END (e->src);
1770
      if (any_condjump_p (insn))
1771
        {
1772
          rtx cond = get_condition (BB_END (e->src), NULL, false, true);
1773
 
1774
          if (cond && (e->flags & EDGE_FALLTHRU))
1775
            cond = reversed_condition (cond);
1776
          if (cond)
1777
            {
1778
              simplify_using_condition (cond, expr, altered);
1779
              if (CONSTANT_P (*expr))
1780
                {
1781
                  FREE_REG_SET (altered);
1782
                  return;
1783
                }
1784
            }
1785
        }
1786
 
1787
      FOR_BB_INSNS_REVERSE (e->src, insn)
1788
        {
1789
          if (!INSN_P (insn))
1790
            continue;
1791
 
1792
          simplify_using_assignment (insn, expr, altered);
1793
          if (CONSTANT_P (*expr))
1794
            {
1795
              FREE_REG_SET (altered);
1796
              return;
1797
            }
1798
        }
1799
 
1800
      if (!single_pred_p (e->src)
1801
          || single_pred (e->src) == ENTRY_BLOCK_PTR)
1802
        break;
1803
      e = single_pred_edge (e->src);
1804
    }
1805
 
1806
  FREE_REG_SET (altered);
1807
}
1808
 
1809
/* Transforms invariant IV into MODE.  Adds assumptions based on the fact
1810
   that IV occurs as left operands of comparison COND and its signedness
1811
   is SIGNED_P to DESC.  */
1812
 
1813
static void
1814
shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode,
1815
                   enum rtx_code cond, bool signed_p, struct niter_desc *desc)
1816
{
1817
  rtx mmin, mmax, cond_over, cond_under;
1818
 
1819
  get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
1820
  cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
1821
                                        iv->base, mmin);
1822
  cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
1823
                                       iv->base, mmax);
1824
 
1825
  switch (cond)
1826
    {
1827
      case LE:
1828
      case LT:
1829
      case LEU:
1830
      case LTU:
1831
        if (cond_under != const0_rtx)
1832
          desc->infinite =
1833
                  alloc_EXPR_LIST (0, cond_under, desc->infinite);
1834
        if (cond_over != const0_rtx)
1835
          desc->noloop_assumptions =
1836
                  alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions);
1837
        break;
1838
 
1839
      case GE:
1840
      case GT:
1841
      case GEU:
1842
      case GTU:
1843
        if (cond_over != const0_rtx)
1844
          desc->infinite =
1845
                  alloc_EXPR_LIST (0, cond_over, desc->infinite);
1846
        if (cond_under != const0_rtx)
1847
          desc->noloop_assumptions =
1848
                  alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions);
1849
        break;
1850
 
1851
      case NE:
1852
        if (cond_over != const0_rtx)
1853
          desc->infinite =
1854
                  alloc_EXPR_LIST (0, cond_over, desc->infinite);
1855
        if (cond_under != const0_rtx)
1856
          desc->infinite =
1857
                  alloc_EXPR_LIST (0, cond_under, desc->infinite);
1858
        break;
1859
 
1860
      default:
1861
        gcc_unreachable ();
1862
    }
1863
 
1864
  iv->mode = mode;
1865
  iv->extend = signed_p ? SIGN_EXTEND : ZERO_EXTEND;
1866
}
1867
 
1868
/* Transforms IV0 and IV1 compared by COND so that they are both compared as
1869
   subregs of the same mode if possible (sometimes it is necessary to add
1870
   some assumptions to DESC).  */
1871
 
1872
static bool
1873
canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
1874
                         enum rtx_code cond, struct niter_desc *desc)
1875
{
1876
  enum machine_mode comp_mode;
1877
  bool signed_p;
1878
 
1879
  /* If the ivs behave specially in the first iteration, or are
1880
     added/multiplied after extending, we ignore them.  */
1881
  if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx)
1882
    return false;
1883
  if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx)
1884
    return false;
1885
 
1886
  /* If there is some extend, it must match signedness of the comparison.  */
1887
  switch (cond)
1888
    {
1889
      case LE:
1890
      case LT:
1891
        if (iv0->extend == ZERO_EXTEND
1892
            || iv1->extend == ZERO_EXTEND)
1893
          return false;
1894
        signed_p = true;
1895
        break;
1896
 
1897
      case LEU:
1898
      case LTU:
1899
        if (iv0->extend == SIGN_EXTEND
1900
            || iv1->extend == SIGN_EXTEND)
1901
          return false;
1902
        signed_p = false;
1903
        break;
1904
 
1905
      case NE:
1906
        if (iv0->extend != UNKNOWN
1907
            && iv1->extend != UNKNOWN
1908
            && iv0->extend != iv1->extend)
1909
          return false;
1910
 
1911
        signed_p = false;
1912
        if (iv0->extend != UNKNOWN)
1913
          signed_p = iv0->extend == SIGN_EXTEND;
1914
        if (iv1->extend != UNKNOWN)
1915
          signed_p = iv1->extend == SIGN_EXTEND;
1916
        break;
1917
 
1918
      default:
1919
        gcc_unreachable ();
1920
    }
1921
 
1922
  /* Values of both variables should be computed in the same mode.  These
1923
     might indeed be different, if we have comparison like
1924
 
1925
     (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
1926
 
1927
     and iv0 and iv1 are both ivs iterating in SI mode, but calculated
1928
     in different modes.  This does not seem impossible to handle, but
1929
     it hardly ever occurs in practice.
1930
 
1931
     The only exception is the case when one of operands is invariant.
1932
     For example pentium 3 generates comparisons like
1933
     (lt (subreg:HI (reg:SI)) 100).  Here we assign HImode to 100, but we
1934
     definitely do not want this prevent the optimization.  */
1935
  comp_mode = iv0->extend_mode;
1936
  if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode))
1937
    comp_mode = iv1->extend_mode;
1938
 
1939
  if (iv0->extend_mode != comp_mode)
1940
    {
1941
      if (iv0->mode != iv0->extend_mode
1942
          || iv0->step != const0_rtx)
1943
        return false;
1944
 
1945
      iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
1946
                                      comp_mode, iv0->base, iv0->mode);
1947
      iv0->extend_mode = comp_mode;
1948
    }
1949
 
1950
  if (iv1->extend_mode != comp_mode)
1951
    {
1952
      if (iv1->mode != iv1->extend_mode
1953
          || iv1->step != const0_rtx)
1954
        return false;
1955
 
1956
      iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
1957
                                      comp_mode, iv1->base, iv1->mode);
1958
      iv1->extend_mode = comp_mode;
1959
    }
1960
 
1961
  /* Check that both ivs belong to a range of a single mode.  If one of the
1962
     operands is an invariant, we may need to shorten it into the common
1963
     mode.  */
1964
  if (iv0->mode == iv0->extend_mode
1965
      && iv0->step == const0_rtx
1966
      && iv0->mode != iv1->mode)
1967
    shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc);
1968
 
1969
  if (iv1->mode == iv1->extend_mode
1970
      && iv1->step == const0_rtx
1971
      && iv0->mode != iv1->mode)
1972
    shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc);
1973
 
1974
  if (iv0->mode != iv1->mode)
1975
    return false;
1976
 
1977
  desc->mode = iv0->mode;
1978
  desc->signed_p = signed_p;
1979
 
1980
  return true;
1981
}
1982
 
1983
/* Computes number of iterations of the CONDITION in INSN in LOOP and stores
1984
   the result into DESC.  Very similar to determine_number_of_iterations
1985
   (basically its rtl version), complicated by things like subregs.  */
1986
 
1987
static void
1988
iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
1989
                         struct niter_desc *desc)
1990
{
1991
  rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;
1992
  struct rtx_iv iv0, iv1, tmp_iv;
1993
  rtx assumption, may_not_xform;
1994
  enum rtx_code cond;
1995
  enum machine_mode mode, comp_mode;
1996
  rtx mmin, mmax, mode_mmin, mode_mmax;
1997
  unsigned HOST_WIDEST_INT s, size, d, inv;
1998
  HOST_WIDEST_INT up, down, inc, step_val;
1999
  int was_sharp = false;
2000
  rtx old_niter;
2001
  bool step_is_pow2;
2002
 
2003
  /* The meaning of these assumptions is this:
2004
     if !assumptions
2005
       then the rest of information does not have to be valid
2006
     if noloop_assumptions then the loop does not roll
2007
     if infinite then this exit is never used */
2008
 
2009
  desc->assumptions = NULL_RTX;
2010
  desc->noloop_assumptions = NULL_RTX;
2011
  desc->infinite = NULL_RTX;
2012
  desc->simple_p = true;
2013
 
2014
  desc->const_iter = false;
2015
  desc->niter_expr = NULL_RTX;
2016
  desc->niter_max = 0;
2017
 
2018
  cond = GET_CODE (condition);
2019
  gcc_assert (COMPARISON_P (condition));
2020
 
2021
  mode = GET_MODE (XEXP (condition, 0));
2022
  if (mode == VOIDmode)
2023
    mode = GET_MODE (XEXP (condition, 1));
2024
  /* The constant comparisons should be folded.  */
2025
  gcc_assert (mode != VOIDmode);
2026
 
2027
  /* We only handle integers or pointers.  */
2028
  if (GET_MODE_CLASS (mode) != MODE_INT
2029
      && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
2030
    goto fail;
2031
 
2032
  op0 = XEXP (condition, 0);
2033
  if (!iv_analyze (insn, op0, &iv0))
2034
    goto fail;
2035
  if (iv0.extend_mode == VOIDmode)
2036
    iv0.mode = iv0.extend_mode = mode;
2037
 
2038
  op1 = XEXP (condition, 1);
2039
  if (!iv_analyze (insn, op1, &iv1))
2040
    goto fail;
2041
  if (iv1.extend_mode == VOIDmode)
2042
    iv1.mode = iv1.extend_mode = mode;
2043
 
2044
  if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
2045
      || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
2046
    goto fail;
2047
 
2048
  /* Check condition and normalize it.  */
2049
 
2050
  switch (cond)
2051
    {
2052
      case GE:
2053
      case GT:
2054
      case GEU:
2055
      case GTU:
2056
        tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
2057
        cond = swap_condition (cond);
2058
        break;
2059
      case NE:
2060
      case LE:
2061
      case LEU:
2062
      case LT:
2063
      case LTU:
2064
        break;
2065
      default:
2066
        goto fail;
2067
    }
2068
 
2069
  /* Handle extends.  This is relatively nontrivial, so we only try in some
2070
     easy cases, when we can canonicalize the ivs (possibly by adding some
2071
     assumptions) to shape subreg (base + i * step).  This function also fills
2072
     in desc->mode and desc->signed_p.  */
2073
 
2074
  if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
2075
    goto fail;
2076
 
2077
  comp_mode = iv0.extend_mode;
2078
  mode = iv0.mode;
2079
  size = GET_MODE_BITSIZE (mode);
2080
  get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
2081
  mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
2082
  mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
2083
 
2084
  if (GET_CODE (iv0.step) != CONST_INT || GET_CODE (iv1.step) != CONST_INT)
2085
    goto fail;
2086
 
2087
  /* We can take care of the case of two induction variables chasing each other
2088
     if the test is NE. I have never seen a loop using it, but still it is
2089
     cool.  */
2090
  if (iv0.step != const0_rtx && iv1.step != const0_rtx)
2091
    {
2092
      if (cond != NE)
2093
        goto fail;
2094
 
2095
      iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2096
      iv1.step = const0_rtx;
2097
    }
2098
 
2099
  /* This is either infinite loop or the one that ends immediately, depending
2100
     on initial values.  Unswitching should remove this kind of conditions.  */
2101
  if (iv0.step == const0_rtx && iv1.step == const0_rtx)
2102
    goto fail;
2103
 
2104
  if (cond != NE)
2105
    {
2106
      if (iv0.step == const0_rtx)
2107
        step_val = -INTVAL (iv1.step);
2108
      else
2109
        step_val = INTVAL (iv0.step);
2110
 
2111
      /* Ignore loops of while (i-- < 10) type.  */
2112
      if (step_val < 0)
2113
        goto fail;
2114
 
2115
      step_is_pow2 = !(step_val & (step_val - 1));
2116
    }
2117
  else
2118
    {
2119
      /* We do not care about whether the step is power of two in this
2120
         case.  */
2121
      step_is_pow2 = false;
2122
      step_val = 0;
2123
    }
2124
 
2125
  /* Some more condition normalization.  We must record some assumptions
2126
     due to overflows.  */
2127
  switch (cond)
2128
    {
2129
      case LT:
2130
      case LTU:
2131
        /* We want to take care only of non-sharp relationals; this is easy,
2132
           as in cases the overflow would make the transformation unsafe
2133
           the loop does not roll.  Seemingly it would make more sense to want
2134
           to take care of sharp relationals instead, as NE is more similar to
2135
           them, but the problem is that here the transformation would be more
2136
           difficult due to possibly infinite loops.  */
2137
        if (iv0.step == const0_rtx)
2138
          {
2139
            tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2140
            assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2141
                                                  mode_mmax);
2142
            if (assumption == const_true_rtx)
2143
              goto zero_iter_simplify;
2144
            iv0.base = simplify_gen_binary (PLUS, comp_mode,
2145
                                            iv0.base, const1_rtx);
2146
          }
2147
        else
2148
          {
2149
            tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2150
            assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2151
                                                  mode_mmin);
2152
            if (assumption == const_true_rtx)
2153
              goto zero_iter_simplify;
2154
            iv1.base = simplify_gen_binary (PLUS, comp_mode,
2155
                                            iv1.base, constm1_rtx);
2156
          }
2157
 
2158
        if (assumption != const0_rtx)
2159
          desc->noloop_assumptions =
2160
                  alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2161
        cond = (cond == LT) ? LE : LEU;
2162
 
2163
        /* It will be useful to be able to tell the difference once more in
2164
           LE -> NE reduction.  */
2165
        was_sharp = true;
2166
        break;
2167
      default: ;
2168
    }
2169
 
2170
  /* Take care of trivially infinite loops.  */
2171
  if (cond != NE)
2172
    {
2173
      if (iv0.step == const0_rtx)
2174
        {
2175
          tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2176
          if (rtx_equal_p (tmp, mode_mmin))
2177
            {
2178
              desc->infinite =
2179
                      alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2180
              /* Fill in the remaining fields somehow.  */
2181
              goto zero_iter_simplify;
2182
            }
2183
        }
2184
      else
2185
        {
2186
          tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2187
          if (rtx_equal_p (tmp, mode_mmax))
2188
            {
2189
              desc->infinite =
2190
                      alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2191
              /* Fill in the remaining fields somehow.  */
2192
              goto zero_iter_simplify;
2193
            }
2194
        }
2195
    }
2196
 
2197
  /* If we can we want to take care of NE conditions instead of size
2198
     comparisons, as they are much more friendly (most importantly
2199
     this takes care of special handling of loops with step 1).  We can
2200
     do it if we first check that upper bound is greater or equal to
2201
     lower bound, their difference is constant c modulo step and that
2202
     there is not an overflow.  */
2203
  if (cond != NE)
2204
    {
2205
      if (iv0.step == const0_rtx)
2206
        step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
2207
      else
2208
        step = iv0.step;
2209
      delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2210
      delta = lowpart_subreg (mode, delta, comp_mode);
2211
      delta = simplify_gen_binary (UMOD, mode, delta, step);
2212
      may_xform = const0_rtx;
2213
      may_not_xform = const_true_rtx;
2214
 
2215
      if (GET_CODE (delta) == CONST_INT)
2216
        {
2217
          if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
2218
            {
2219
              /* A special case.  We have transformed condition of type
2220
                 for (i = 0; i < 4; i += 4)
2221
                 into
2222
                 for (i = 0; i <= 3; i += 4)
2223
                 obviously if the test for overflow during that transformation
2224
                 passed, we cannot overflow here.  Most importantly any
2225
                 loop with sharp end condition and step 1 falls into this
2226
                 category, so handling this case specially is definitely
2227
                 worth the troubles.  */
2228
              may_xform = const_true_rtx;
2229
            }
2230
          else if (iv0.step == const0_rtx)
2231
            {
2232
              bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
2233
              bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
2234
              bound = lowpart_subreg (mode, bound, comp_mode);
2235
              tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2236
              may_xform = simplify_gen_relational (cond, SImode, mode,
2237
                                                   bound, tmp);
2238
              may_not_xform = simplify_gen_relational (reverse_condition (cond),
2239
                                                       SImode, mode,
2240
                                                       bound, tmp);
2241
            }
2242
          else
2243
            {
2244
              bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
2245
              bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
2246
              bound = lowpart_subreg (mode, bound, comp_mode);
2247
              tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2248
              may_xform = simplify_gen_relational (cond, SImode, mode,
2249
                                                   tmp, bound);
2250
              may_not_xform = simplify_gen_relational (reverse_condition (cond),
2251
                                                       SImode, mode,
2252
                                                       tmp, bound);
2253
            }
2254
        }
2255
 
2256
      if (may_xform != const0_rtx)
2257
        {
2258
          /* We perform the transformation always provided that it is not
2259
             completely senseless.  This is OK, as we would need this assumption
2260
             to determine the number of iterations anyway.  */
2261
          if (may_xform != const_true_rtx)
2262
            {
2263
              /* If the step is a power of two and the final value we have
2264
                 computed overflows, the cycle is infinite.  Otherwise it
2265
                 is nontrivial to compute the number of iterations.  */
2266
              if (step_is_pow2)
2267
                desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
2268
                                                  desc->infinite);
2269
              else
2270
                desc->assumptions = alloc_EXPR_LIST (0, may_xform,
2271
                                                     desc->assumptions);
2272
            }
2273
 
2274
          /* We are going to lose some information about upper bound on
2275
             number of iterations in this step, so record the information
2276
             here.  */
2277
          inc = INTVAL (iv0.step) - INTVAL (iv1.step);
2278
          if (GET_CODE (iv1.base) == CONST_INT)
2279
            up = INTVAL (iv1.base);
2280
          else
2281
            up = INTVAL (mode_mmax) - inc;
2282
          down = INTVAL (GET_CODE (iv0.base) == CONST_INT
2283
                         ? iv0.base
2284
                         : mode_mmin);
2285
          desc->niter_max = (up - down) / inc + 1;
2286
 
2287
          if (iv0.step == const0_rtx)
2288
            {
2289
              iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
2290
              iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
2291
            }
2292
          else
2293
            {
2294
              iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
2295
              iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
2296
            }
2297
 
2298
          tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2299
          tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2300
          assumption = simplify_gen_relational (reverse_condition (cond),
2301
                                                SImode, mode, tmp0, tmp1);
2302
          if (assumption == const_true_rtx)
2303
            goto zero_iter_simplify;
2304
          else if (assumption != const0_rtx)
2305
            desc->noloop_assumptions =
2306
                    alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2307
          cond = NE;
2308
        }
2309
    }
2310
 
2311
  /* Count the number of iterations.  */
2312
  if (cond == NE)
2313
    {
2314
      /* Everything we do here is just arithmetics modulo size of mode.  This
2315
         makes us able to do more involved computations of number of iterations
2316
         than in other cases.  First transform the condition into shape
2317
         s * i <> c, with s positive.  */
2318
      iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2319
      iv0.base = const0_rtx;
2320
      iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2321
      iv1.step = const0_rtx;
2322
      if (INTVAL (iv0.step) < 0)
2323
        {
2324
          iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, mode);
2325
          iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, mode);
2326
        }
2327
      iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2328
 
2329
      /* Let nsd (s, size of mode) = d.  If d does not divide c, the loop
2330
         is infinite.  Otherwise, the number of iterations is
2331
         (inverse(s/d) * (c/d)) mod (size of mode/d).  */
2332
      s = INTVAL (iv0.step); d = 1;
2333
      while (s % 2 != 1)
2334
        {
2335
          s /= 2;
2336
          d *= 2;
2337
          size--;
2338
        }
2339
      bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
2340
 
2341
      tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2342
      tmp = simplify_gen_binary (UMOD, mode, tmp1, GEN_INT (d));
2343
      assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
2344
      desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
2345
 
2346
      tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
2347
      inv = inverse (s, size);
2348
      tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
2349
      desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
2350
    }
2351
  else
2352
    {
2353
      if (iv1.step == const0_rtx)
2354
        /* Condition in shape a + s * i <= b
2355
           We must know that b + s does not overflow and a <= b + s and then we
2356
           can compute number of iterations as (b + s - a) / s.  (It might
2357
           seem that we in fact could be more clever about testing the b + s
2358
           overflow condition using some information about b - a mod s,
2359
           but it was already taken into account during LE -> NE transform).  */
2360
        {
2361
          step = iv0.step;
2362
          tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2363
          tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2364
 
2365
          bound = simplify_gen_binary (MINUS, mode, mode_mmax,
2366
                                       lowpart_subreg (mode, step,
2367
                                                       comp_mode));
2368
          if (step_is_pow2)
2369
            {
2370
              rtx t0, t1;
2371
 
2372
              /* If s is power of 2, we know that the loop is infinite if
2373
                 a % s <= b % s and b + s overflows.  */
2374
              assumption = simplify_gen_relational (reverse_condition (cond),
2375
                                                    SImode, mode,
2376
                                                    tmp1, bound);
2377
 
2378
              t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2379
              t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2380
              tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2381
              assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2382
              desc->infinite =
2383
                      alloc_EXPR_LIST (0, assumption, desc->infinite);
2384
            }
2385
          else
2386
            {
2387
              assumption = simplify_gen_relational (cond, SImode, mode,
2388
                                                    tmp1, bound);
2389
              desc->assumptions =
2390
                      alloc_EXPR_LIST (0, assumption, desc->assumptions);
2391
            }
2392
 
2393
          tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
2394
          tmp = lowpart_subreg (mode, tmp, comp_mode);
2395
          assumption = simplify_gen_relational (reverse_condition (cond),
2396
                                                SImode, mode, tmp0, tmp);
2397
 
2398
          delta = simplify_gen_binary (PLUS, mode, tmp1, step);
2399
          delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
2400
        }
2401
      else
2402
        {
2403
          /* Condition in shape a <= b - s * i
2404
             We must know that a - s does not overflow and a - s <= b and then
2405
             we can again compute number of iterations as (b - (a - s)) / s.  */
2406
          step = simplify_gen_unary (NEG, mode, iv1.step, mode);
2407
          tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2408
          tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2409
 
2410
          bound = simplify_gen_binary (PLUS, mode, mode_mmin,
2411
                                       lowpart_subreg (mode, step, comp_mode));
2412
          if (step_is_pow2)
2413
            {
2414
              rtx t0, t1;
2415
 
2416
              /* If s is power of 2, we know that the loop is infinite if
2417
                 a % s <= b % s and a - s overflows.  */
2418
              assumption = simplify_gen_relational (reverse_condition (cond),
2419
                                                    SImode, mode,
2420
                                                    bound, tmp0);
2421
 
2422
              t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2423
              t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2424
              tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2425
              assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2426
              desc->infinite =
2427
                      alloc_EXPR_LIST (0, assumption, desc->infinite);
2428
            }
2429
          else
2430
            {
2431
              assumption = simplify_gen_relational (cond, SImode, mode,
2432
                                                    bound, tmp0);
2433
              desc->assumptions =
2434
                      alloc_EXPR_LIST (0, assumption, desc->assumptions);
2435
            }
2436
 
2437
          tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
2438
          tmp = lowpart_subreg (mode, tmp, comp_mode);
2439
          assumption = simplify_gen_relational (reverse_condition (cond),
2440
                                                SImode, mode,
2441
                                                tmp, tmp1);
2442
          delta = simplify_gen_binary (MINUS, mode, tmp0, step);
2443
          delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
2444
        }
2445
      if (assumption == const_true_rtx)
2446
        goto zero_iter_simplify;
2447
      else if (assumption != const0_rtx)
2448
        desc->noloop_assumptions =
2449
                alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2450
      delta = simplify_gen_binary (UDIV, mode, delta, step);
2451
      desc->niter_expr = delta;
2452
    }
2453
 
2454
  old_niter = desc->niter_expr;
2455
 
2456
  simplify_using_initial_values (loop, AND, &desc->assumptions);
2457
  if (desc->assumptions
2458
      && XEXP (desc->assumptions, 0) == const0_rtx)
2459
    goto fail;
2460
  simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2461
  simplify_using_initial_values (loop, IOR, &desc->infinite);
2462
  simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2463
 
2464
  /* Rerun the simplification.  Consider code (created by copying loop headers)
2465
 
2466
     i = 0;
2467
 
2468
     if (0 < n)
2469
       {
2470
         do
2471
           {
2472
             i++;
2473
           } while (i < n);
2474
       }
2475
 
2476
    The first pass determines that i = 0, the second pass uses it to eliminate
2477
    noloop assumption.  */
2478
 
2479
  simplify_using_initial_values (loop, AND, &desc->assumptions);
2480
  if (desc->assumptions
2481
      && XEXP (desc->assumptions, 0) == const0_rtx)
2482
    goto fail;
2483
  simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2484
  simplify_using_initial_values (loop, IOR, &desc->infinite);
2485
  simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2486
 
2487
  if (desc->noloop_assumptions
2488
      && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
2489
    goto zero_iter;
2490
 
2491
  if (GET_CODE (desc->niter_expr) == CONST_INT)
2492
    {
2493
      unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
2494
 
2495
      desc->const_iter = true;
2496
      desc->niter_max = desc->niter = val & GET_MODE_MASK (desc->mode);
2497
    }
2498
  else
2499
    {
2500
      if (!desc->niter_max)
2501
        desc->niter_max = determine_max_iter (desc);
2502
 
2503
      /* simplify_using_initial_values does a copy propagation on the registers
2504
         in the expression for the number of iterations.  This prolongs life
2505
         ranges of registers and increases register pressure, and usually
2506
         brings no gain (and if it happens to do, the cse pass will take care
2507
         of it anyway).  So prevent this behavior, unless it enabled us to
2508
         derive that the number of iterations is a constant.  */
2509
      desc->niter_expr = old_niter;
2510
    }
2511
 
2512
  return;
2513
 
2514
zero_iter_simplify:
2515
  /* Simplify the assumptions.  */
2516
  simplify_using_initial_values (loop, AND, &desc->assumptions);
2517
  if (desc->assumptions
2518
      && XEXP (desc->assumptions, 0) == const0_rtx)
2519
    goto fail;
2520
  simplify_using_initial_values (loop, IOR, &desc->infinite);
2521
 
2522
  /* Fallthru.  */
2523
zero_iter:
2524
  desc->const_iter = true;
2525
  desc->niter = 0;
2526
  desc->niter_max = 0;
2527
  desc->noloop_assumptions = NULL_RTX;
2528
  desc->niter_expr = const0_rtx;
2529
  return;
2530
 
2531
fail:
2532
  desc->simple_p = false;
2533
  return;
2534
}
2535
 
2536
/* Checks whether E is a simple exit from LOOP and stores its description
2537
   into DESC.  */
2538
 
2539
static void
2540
check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
2541
{
2542
  basic_block exit_bb;
2543
  rtx condition, at;
2544
  edge ein;
2545
 
2546
  exit_bb = e->src;
2547
  desc->simple_p = false;
2548
 
2549
  /* It must belong directly to the loop.  */
2550
  if (exit_bb->loop_father != loop)
2551
    return;
2552
 
2553
  /* It must be tested (at least) once during any iteration.  */
2554
  if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
2555
    return;
2556
 
2557
  /* It must end in a simple conditional jump.  */
2558
  if (!any_condjump_p (BB_END (exit_bb)))
2559
    return;
2560
 
2561
  ein = EDGE_SUCC (exit_bb, 0);
2562
  if (ein == e)
2563
    ein = EDGE_SUCC (exit_bb, 1);
2564
 
2565
  desc->out_edge = e;
2566
  desc->in_edge = ein;
2567
 
2568
  /* Test whether the condition is suitable.  */
2569
  if (!(condition = get_condition (BB_END (ein->src), &at, false, false)))
2570
    return;
2571
 
2572
  if (ein->flags & EDGE_FALLTHRU)
2573
    {
2574
      condition = reversed_condition (condition);
2575
      if (!condition)
2576
        return;
2577
    }
2578
 
2579
  /* Check that we are able to determine number of iterations and fill
2580
     in information about it.  */
2581
  iv_number_of_iterations (loop, at, condition, desc);
2582
}
2583
 
2584
/* Finds a simple exit of LOOP and stores its description into DESC.  */
2585
 
2586
void
2587
find_simple_exit (struct loop *loop, struct niter_desc *desc)
2588
{
2589
  unsigned i;
2590
  basic_block *body;
2591
  edge e;
2592
  struct niter_desc act;
2593
  bool any = false;
2594
  edge_iterator ei;
2595
 
2596
  desc->simple_p = false;
2597
  body = get_loop_body (loop);
2598
 
2599
  for (i = 0; i < loop->num_nodes; i++)
2600
    {
2601
      FOR_EACH_EDGE (e, ei, body[i]->succs)
2602
        {
2603
          if (flow_bb_inside_loop_p (loop, e->dest))
2604
            continue;
2605
 
2606
          check_simple_exit (loop, e, &act);
2607
          if (!act.simple_p)
2608
            continue;
2609
 
2610
          if (!any)
2611
            any = true;
2612
          else
2613
            {
2614
              /* Prefer constant iterations; the less the better.  */
2615
              if (!act.const_iter
2616
                  || (desc->const_iter && act.niter >= desc->niter))
2617
                continue;
2618
 
2619
              /* Also if the actual exit may be infinite, while the old one
2620
                 not, prefer the old one.  */
2621
              if (act.infinite && !desc->infinite)
2622
                continue;
2623
            }
2624
 
2625
          *desc = act;
2626
        }
2627
    }
2628
 
2629
  if (dump_file)
2630
    {
2631
      if (desc->simple_p)
2632
        {
2633
          fprintf (dump_file, "Loop %d is simple:\n", loop->num);
2634
          fprintf (dump_file, "  simple exit %d -> %d\n",
2635
                   desc->out_edge->src->index,
2636
                   desc->out_edge->dest->index);
2637
          if (desc->assumptions)
2638
            {
2639
              fprintf (dump_file, "  assumptions: ");
2640
              print_rtl (dump_file, desc->assumptions);
2641
              fprintf (dump_file, "\n");
2642
            }
2643
          if (desc->noloop_assumptions)
2644
            {
2645
              fprintf (dump_file, "  does not roll if: ");
2646
              print_rtl (dump_file, desc->noloop_assumptions);
2647
              fprintf (dump_file, "\n");
2648
            }
2649
          if (desc->infinite)
2650
            {
2651
              fprintf (dump_file, "  infinite if: ");
2652
              print_rtl (dump_file, desc->infinite);
2653
              fprintf (dump_file, "\n");
2654
            }
2655
 
2656
          fprintf (dump_file, "  number of iterations: ");
2657
          print_rtl (dump_file, desc->niter_expr);
2658
          fprintf (dump_file, "\n");
2659
 
2660
          fprintf (dump_file, "  upper bound: ");
2661
          fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter_max);
2662
          fprintf (dump_file, "\n");
2663
        }
2664
      else
2665
        fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
2666
    }
2667
 
2668
  free (body);
2669
}
2670
 
2671
/* Creates a simple loop description of LOOP if it was not computed
2672
   already.  */
2673
 
2674
struct niter_desc *
2675
get_simple_loop_desc (struct loop *loop)
2676
{
2677
  struct niter_desc *desc = simple_loop_desc (loop);
2678
 
2679
  if (desc)
2680
    return desc;
2681
 
2682
  desc = XNEW (struct niter_desc);
2683
  iv_analysis_loop_init (loop);
2684
  find_simple_exit (loop, desc);
2685
  loop->aux = desc;
2686
 
2687
  if (desc->simple_p && (desc->assumptions || desc->infinite))
2688
    {
2689
      const char *wording;
2690
 
2691
      /* Assume that no overflow happens and that the loop is finite.
2692
         We already warned at the tree level if we ran optimizations there.  */
2693
      if (!flag_tree_loop_optimize && warn_unsafe_loop_optimizations)
2694
        {
2695
          if (desc->infinite)
2696
            {
2697
              wording =
2698
                flag_unsafe_loop_optimizations
2699
                ? N_("assuming that the loop is not infinite")
2700
                : N_("cannot optimize possibly infinite loops");
2701
              warning (OPT_Wunsafe_loop_optimizations, "%s",
2702
                       gettext (wording));
2703
            }
2704
          if (desc->assumptions)
2705
            {
2706
              wording =
2707
                flag_unsafe_loop_optimizations
2708
                ? N_("assuming that the loop counter does not overflow")
2709
                : N_("cannot optimize loop, the loop counter may overflow");
2710
              warning (OPT_Wunsafe_loop_optimizations, "%s",
2711
                       gettext (wording));
2712
            }
2713
        }
2714
 
2715
      if (flag_unsafe_loop_optimizations)
2716
        {
2717
          desc->assumptions = NULL_RTX;
2718
          desc->infinite = NULL_RTX;
2719
        }
2720
    }
2721
 
2722
  return desc;
2723
}
2724
 
2725
/* Releases simple loop description for LOOP.  */
2726
 
2727
void
2728
free_simple_loop_desc (struct loop *loop)
2729
{
2730
  struct niter_desc *desc = simple_loop_desc (loop);
2731
 
2732
  if (!desc)
2733
    return;
2734
 
2735
  free (desc);
2736
  loop->aux = NULL;
2737
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.