OSDN Git Service

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