OSDN Git Service

* loop-iv.c (implies_p): Detect additional cases where A implies B.
[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 /* Checks whether register *REG is in set ALT.  Callback for for_each_rtx.  */
1265
1266 static int
1267 altered_reg_used (rtx *reg, void *alt)
1268 {
1269   if (!REG_P (*reg))
1270     return 0;
1271
1272   return REGNO_REG_SET_P (alt, REGNO (*reg));
1273 }
1274
1275 /* Marks registers altered by EXPR in set ALT.  */
1276
1277 static void
1278 mark_altered (rtx expr, rtx by ATTRIBUTE_UNUSED, void *alt)
1279 {
1280   if (GET_CODE (expr) == SUBREG)
1281     expr = SUBREG_REG (expr);
1282   if (!REG_P (expr))
1283     return;
1284
1285   SET_REGNO_REG_SET (alt, REGNO (expr));
1286 }
1287
1288 /* Checks whether RHS is simple enough to process.  */
1289
1290 static bool
1291 simple_rhs_p (rtx rhs)
1292 {
1293   rtx op0, op1;
1294
1295   if (CONSTANT_P (rhs)
1296       || REG_P (rhs))
1297     return true;
1298
1299   switch (GET_CODE (rhs))
1300     {
1301     case PLUS:
1302     case MINUS:
1303       op0 = XEXP (rhs, 0);
1304       op1 = XEXP (rhs, 1);
1305       /* Allow reg + const sets only.  */
1306       if (REG_P (op0) && CONSTANT_P (op1))
1307         return true;
1308       if (REG_P (op1) && CONSTANT_P (op0))
1309         return true;
1310
1311       return false;
1312
1313     default:
1314       return false;
1315     }
1316 }
1317
1318 /* Simplifies *EXPR using assignment in INSN.  ALTERED is the set of registers
1319    altered so far.  */
1320
1321 static void
1322 simplify_using_assignment (rtx insn, rtx *expr, regset altered)
1323 {
1324   rtx set = single_set (insn);
1325   rtx lhs = NULL_RTX, rhs;
1326   bool ret = false;
1327
1328   if (set)
1329     {
1330       lhs = SET_DEST (set);
1331       if (!REG_P (lhs)
1332           || altered_reg_used (&lhs, altered))
1333         ret = true;
1334     }
1335   else
1336     ret = true;
1337
1338   note_stores (PATTERN (insn), mark_altered, altered);
1339   if (CALL_P (insn))
1340     {
1341       int i;
1342
1343       /* Kill all call clobbered registers.  */
1344       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1345         if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1346           SET_REGNO_REG_SET (altered, i);
1347     }
1348
1349   if (ret)
1350     return;
1351
1352   rhs = find_reg_equal_equiv_note (insn);
1353   if (rhs)
1354     rhs = XEXP (rhs, 0);
1355   else
1356     rhs = SET_SRC (set);
1357
1358   if (!simple_rhs_p (rhs))
1359     return;
1360
1361   if (for_each_rtx (&rhs, altered_reg_used, altered))
1362     return;
1363
1364   *expr = simplify_replace_rtx (*expr, lhs, rhs);
1365 }
1366
1367 /* Checks whether A implies B.  */
1368
1369 static bool
1370 implies_p (rtx a, rtx b)
1371 {
1372   rtx op0, op1, opb0, opb1, r;
1373   enum machine_mode mode;
1374
1375   if (GET_CODE (a) == EQ)
1376     {
1377       op0 = XEXP (a, 0);
1378       op1 = XEXP (a, 1);
1379
1380       if (REG_P (op0))
1381         {
1382           r = simplify_replace_rtx (b, op0, op1);
1383           if (r == const_true_rtx)
1384             return true;
1385         }
1386
1387       if (REG_P (op1))
1388         {
1389           r = simplify_replace_rtx (b, op1, op0);
1390           if (r == const_true_rtx)
1391             return true;
1392         }
1393     }
1394
1395   if (b == const_true_rtx)
1396     return true;
1397
1398   if ((GET_RTX_CLASS (GET_CODE (a)) != RTX_COMM_COMPARE
1399        && GET_RTX_CLASS (GET_CODE (a)) != RTX_COMPARE)
1400       || (GET_RTX_CLASS (GET_CODE (b)) != RTX_COMM_COMPARE
1401           && GET_RTX_CLASS (GET_CODE (b)) != RTX_COMPARE))
1402     return false;
1403
1404   op0 = XEXP (a, 0);
1405   op1 = XEXP (a, 1);
1406   opb0 = XEXP (b, 0);
1407   opb1 = XEXP (b, 1);
1408
1409   mode = GET_MODE (op0);
1410   if (mode != GET_MODE (opb0))
1411     mode = VOIDmode;
1412   else if (mode == VOIDmode)
1413     {
1414       mode = GET_MODE (op1);
1415       if (mode != GET_MODE (opb1))
1416         mode = VOIDmode;
1417     }
1418
1419   /* A < B implies A + 1 <= B.  */
1420   if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
1421       && (GET_CODE (b) == GE || GET_CODE (b) == LE))
1422     {
1423
1424       if (GET_CODE (a) == GT)
1425         {
1426           r = op0;
1427           op0 = op1;
1428           op1 = r;
1429         }
1430
1431       if (GET_CODE (b) == GE)
1432         {
1433           r = opb0;
1434           opb0 = opb1;
1435           opb1 = r;
1436         }
1437
1438       if (SCALAR_INT_MODE_P (mode)
1439           && rtx_equal_p (op1, opb1)
1440           && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
1441         return true;
1442       return false;
1443     }
1444
1445   /* A < B or A > B imply A != B.  TODO: Likewise
1446      A + n < B implies A != B + n if neither wraps.  */
1447   if (GET_CODE (b) == NE
1448       && (GET_CODE (a) == GT || GET_CODE (a) == GTU
1449           || GET_CODE (a) == LT || GET_CODE (a) == LTU))
1450     {
1451       if (rtx_equal_p (op0, opb0)
1452           && rtx_equal_p (op1, opb1))
1453         return true;
1454     }
1455
1456   /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1.  */
1457   if (GET_CODE (a) == NE
1458       && op1 == const0_rtx)
1459     {
1460       if ((GET_CODE (b) == GTU
1461            && opb1 == const0_rtx)
1462           || (GET_CODE (b) == GEU
1463               && opb1 == const1_rtx))
1464         return rtx_equal_p (op0, opb0);
1465     }
1466
1467   /* A != N is equivalent to A - (N + 1) <u -1.  */
1468   if (GET_CODE (a) == NE
1469       && GET_CODE (op1) == CONST_INT
1470       && GET_CODE (b) == LTU
1471       && opb1 == constm1_rtx
1472       && GET_CODE (opb0) == PLUS
1473       && GET_CODE (XEXP (opb0, 1)) == CONST_INT
1474       /* Avoid overflows.  */
1475       && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1476           != ((unsigned HOST_WIDE_INT)1
1477               << (HOST_BITS_PER_WIDE_INT - 1)) - 1)
1478       && INTVAL (XEXP (opb0, 1)) + 1 == -INTVAL (op1))
1479     return rtx_equal_p (op0, XEXP (opb0, 0));
1480
1481   /* Likewise, A != N implies A - N > 0.  */
1482   if (GET_CODE (a) == NE
1483       && GET_CODE (op1) == CONST_INT)
1484     {
1485       if (GET_CODE (b) == GTU
1486           && GET_CODE (opb0) == PLUS
1487           && opb1 == const0_rtx
1488           && GET_CODE (XEXP (opb0, 1)) == CONST_INT
1489           /* Avoid overflows.  */
1490           && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1491               != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
1492           && rtx_equal_p (XEXP (opb0, 0), op0))
1493         return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1494       if (GET_CODE (b) == GEU
1495           && GET_CODE (opb0) == PLUS
1496           && opb1 == const1_rtx
1497           && GET_CODE (XEXP (opb0, 1)) == CONST_INT
1498           /* Avoid overflows.  */
1499           && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1500               != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
1501           && rtx_equal_p (XEXP (opb0, 0), op0))
1502         return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1503     }
1504
1505   /* A >s X, where X is positive, implies A <u Y, if Y is negative.  */
1506   if ((GET_CODE (a) == GT || GET_CODE (a) == GE)
1507       && GET_CODE (op1) == CONST_INT
1508       && ((GET_CODE (a) == GT && op1 == constm1_rtx)
1509           || INTVAL (op1) >= 0)
1510       && GET_CODE (b) == LTU
1511       && GET_CODE (opb1) == CONST_INT)
1512     return INTVAL (opb1) < 0;
1513
1514   return false;
1515 }
1516
1517 /* Canonicalizes COND so that
1518
1519    (1) Ensure that operands are ordered according to
1520        swap_commutative_operands_p.
1521    (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1522        for GE, GEU, and LEU.  */
1523
1524 rtx
1525 canon_condition (rtx cond)
1526 {
1527   rtx tem;
1528   rtx op0, op1;
1529   enum rtx_code code;
1530   enum machine_mode mode;
1531
1532   code = GET_CODE (cond);
1533   op0 = XEXP (cond, 0);
1534   op1 = XEXP (cond, 1);
1535
1536   if (swap_commutative_operands_p (op0, op1))
1537     {
1538       code = swap_condition (code);
1539       tem = op0;
1540       op0 = op1;
1541       op1 = tem;
1542     }
1543
1544   mode = GET_MODE (op0);
1545   if (mode == VOIDmode)
1546     mode = GET_MODE (op1);
1547   gcc_assert (mode != VOIDmode);
1548
1549   if (GET_CODE (op1) == CONST_INT
1550       && GET_MODE_CLASS (mode) != MODE_CC
1551       && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
1552     {
1553       HOST_WIDE_INT const_val = INTVAL (op1);
1554       unsigned HOST_WIDE_INT uconst_val = const_val;
1555       unsigned HOST_WIDE_INT max_val
1556         = (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode);
1557
1558       switch (code)
1559         {
1560         case LE:
1561           if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
1562             code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0));
1563           break;
1564
1565         /* When cross-compiling, const_val might be sign-extended from
1566            BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1567         case GE:
1568           if ((HOST_WIDE_INT) (const_val & max_val)
1569               != (((HOST_WIDE_INT) 1
1570                    << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
1571             code = GT, op1 = gen_int_mode (const_val - 1, mode);
1572           break;
1573
1574         case LEU:
1575           if (uconst_val < max_val)
1576             code = LTU, op1 = gen_int_mode (uconst_val + 1, mode);
1577           break;
1578
1579         case GEU:
1580           if (uconst_val != 0)
1581             code = GTU, op1 = gen_int_mode (uconst_val - 1, mode);
1582           break;
1583
1584         default:
1585           break;
1586         }
1587     }
1588
1589   if (op0 != XEXP (cond, 0)
1590       || op1 != XEXP (cond, 1)
1591       || code != GET_CODE (cond)
1592       || GET_MODE (cond) != SImode)
1593     cond = gen_rtx_fmt_ee (code, SImode, op0, op1);
1594
1595   return cond;
1596 }
1597
1598 /* Tries to use the fact that COND holds to simplify EXPR.  ALTERED is the
1599    set of altered regs.  */
1600
1601 void
1602 simplify_using_condition (rtx cond, rtx *expr, regset altered)
1603 {
1604   rtx rev, reve, exp = *expr;
1605
1606   if (!COMPARISON_P (exp))
1607     return;
1608
1609   /* If some register gets altered later, we do not really speak about its
1610      value at the time of comparison.  */
1611   if (altered
1612       && for_each_rtx (&cond, altered_reg_used, altered))
1613     return;
1614
1615   rev = reversed_condition (cond);
1616   reve = reversed_condition (exp);
1617
1618   cond = canon_condition (cond);
1619   exp = canon_condition (exp);
1620   if (rev)
1621     rev = canon_condition (rev);
1622   if (reve)
1623     reve = canon_condition (reve);
1624
1625   if (rtx_equal_p (exp, cond))
1626     {
1627       *expr = const_true_rtx;
1628       return;
1629     }
1630
1631
1632   if (rev && rtx_equal_p (exp, rev))
1633     {
1634       *expr = const0_rtx;
1635       return;
1636     }
1637
1638   if (implies_p (cond, exp))
1639     {
1640       *expr = const_true_rtx;
1641       return;
1642     }
1643   
1644   if (reve && implies_p (cond, reve))
1645     {
1646       *expr = const0_rtx;
1647       return;
1648     }
1649
1650   /* A proof by contradiction.  If *EXPR implies (not cond), *EXPR must
1651      be false.  */
1652   if (rev && implies_p (exp, rev))
1653     {
1654       *expr = const0_rtx;
1655       return;
1656     }
1657
1658   /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true.  */
1659   if (rev && reve && implies_p (reve, rev))
1660     {
1661       *expr = const_true_rtx;
1662       return;
1663     }
1664
1665   /* We would like to have some other tests here.  TODO.  */
1666
1667   return;
1668 }
1669
1670 /* Use relationship between A and *B to eventually eliminate *B.
1671    OP is the operation we consider.  */
1672
1673 static void
1674 eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
1675 {
1676   switch (op)
1677     {
1678     case AND:
1679       /* If A implies *B, we may replace *B by true.  */
1680       if (implies_p (a, *b))
1681         *b = const_true_rtx;
1682       break;
1683
1684     case IOR:
1685       /* If *B implies A, we may replace *B by false.  */
1686       if (implies_p (*b, a))
1687         *b = const0_rtx;
1688       break;
1689
1690     default:
1691       gcc_unreachable ();
1692     }
1693 }
1694
1695 /* Eliminates the conditions in TAIL that are implied by HEAD.  OP is the
1696    operation we consider.  */
1697
1698 static void
1699 eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
1700 {
1701   rtx elt;
1702
1703   for (elt = tail; elt; elt = XEXP (elt, 1))
1704     eliminate_implied_condition (op, *head, &XEXP (elt, 0));
1705   for (elt = tail; elt; elt = XEXP (elt, 1))
1706     eliminate_implied_condition (op, XEXP (elt, 0), head);
1707 }
1708
1709 /* Simplifies *EXPR using initial values at the start of the LOOP.  If *EXPR
1710    is a list, its elements are assumed to be combined using OP.  */
1711
1712 static void
1713 simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
1714 {
1715   rtx head, tail, insn;
1716   rtx neutral, aggr;
1717   regset altered;
1718   edge e;
1719
1720   if (!*expr)
1721     return;
1722
1723   if (CONSTANT_P (*expr))
1724     return;
1725
1726   if (GET_CODE (*expr) == EXPR_LIST)
1727     {
1728       head = XEXP (*expr, 0);
1729       tail = XEXP (*expr, 1);
1730
1731       eliminate_implied_conditions (op, &head, tail);
1732
1733       switch (op)
1734         {
1735         case AND:
1736           neutral = const_true_rtx;
1737           aggr = const0_rtx;
1738           break;
1739
1740         case IOR:
1741           neutral = const0_rtx;
1742           aggr = const_true_rtx;
1743           break;
1744
1745         default:
1746           gcc_unreachable ();
1747         }
1748       
1749       simplify_using_initial_values (loop, UNKNOWN, &head);
1750       if (head == aggr)
1751         {
1752           XEXP (*expr, 0) = aggr;
1753           XEXP (*expr, 1) = NULL_RTX;
1754           return;
1755         }
1756       else if (head == neutral)
1757         {
1758           *expr = tail;
1759           simplify_using_initial_values (loop, op, expr);
1760           return;
1761         }
1762       simplify_using_initial_values (loop, op, &tail);
1763
1764       if (tail && XEXP (tail, 0) == aggr)
1765         {
1766           *expr = tail;
1767           return;
1768         }
1769   
1770       XEXP (*expr, 0) = head;
1771       XEXP (*expr, 1) = tail;
1772       return;
1773     }
1774
1775   gcc_assert (op == UNKNOWN);
1776
1777   e = loop_preheader_edge (loop);
1778   if (e->src == ENTRY_BLOCK_PTR)
1779     return;
1780
1781   altered = ALLOC_REG_SET (&reg_obstack);
1782
1783   while (1)
1784     {
1785       insn = BB_END (e->src);
1786       if (any_condjump_p (insn))
1787         {
1788           rtx cond = get_condition (BB_END (e->src), NULL, false, true);
1789       
1790           if (cond && (e->flags & EDGE_FALLTHRU))
1791             cond = reversed_condition (cond);
1792           if (cond)
1793             {
1794               simplify_using_condition (cond, expr, altered);
1795               if (CONSTANT_P (*expr))
1796                 {
1797                   FREE_REG_SET (altered);
1798                   return;
1799                 }
1800             }
1801         }
1802
1803       FOR_BB_INSNS_REVERSE (e->src, insn)
1804         {
1805           if (!INSN_P (insn))
1806             continue;
1807             
1808           simplify_using_assignment (insn, expr, altered);
1809           if (CONSTANT_P (*expr))
1810             {
1811               FREE_REG_SET (altered);
1812               return;
1813             }
1814         }
1815
1816       if (!single_pred_p (e->src)
1817           || single_pred (e->src) == ENTRY_BLOCK_PTR)
1818         break;
1819       e = single_pred_edge (e->src);
1820     }
1821
1822   FREE_REG_SET (altered);
1823 }
1824
1825 /* Transforms invariant IV into MODE.  Adds assumptions based on the fact
1826    that IV occurs as left operands of comparison COND and its signedness
1827    is SIGNED_P to DESC.  */
1828
1829 static void
1830 shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode,
1831                    enum rtx_code cond, bool signed_p, struct niter_desc *desc)
1832 {
1833   rtx mmin, mmax, cond_over, cond_under;
1834
1835   get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
1836   cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
1837                                         iv->base, mmin);
1838   cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
1839                                        iv->base, mmax);
1840
1841   switch (cond)
1842     {
1843       case LE:
1844       case LT:
1845       case LEU:
1846       case LTU:
1847         if (cond_under != const0_rtx)
1848           desc->infinite =
1849                   alloc_EXPR_LIST (0, cond_under, desc->infinite);
1850         if (cond_over != const0_rtx)
1851           desc->noloop_assumptions =
1852                   alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions);
1853         break;
1854
1855       case GE:
1856       case GT:
1857       case GEU:
1858       case GTU:
1859         if (cond_over != const0_rtx)
1860           desc->infinite =
1861                   alloc_EXPR_LIST (0, cond_over, desc->infinite);
1862         if (cond_under != const0_rtx)
1863           desc->noloop_assumptions =
1864                   alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions);
1865         break;
1866
1867       case NE:
1868         if (cond_over != const0_rtx)
1869           desc->infinite =
1870                   alloc_EXPR_LIST (0, cond_over, desc->infinite);
1871         if (cond_under != const0_rtx)
1872           desc->infinite =
1873                   alloc_EXPR_LIST (0, cond_under, desc->infinite);
1874         break;
1875
1876       default:
1877         gcc_unreachable ();
1878     }
1879
1880   iv->mode = mode;
1881   iv->extend = signed_p ? SIGN_EXTEND : ZERO_EXTEND;
1882 }
1883
1884 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
1885    subregs of the same mode if possible (sometimes it is necessary to add
1886    some assumptions to DESC).  */
1887
1888 static bool
1889 canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
1890                          enum rtx_code cond, struct niter_desc *desc)
1891 {
1892   enum machine_mode comp_mode;
1893   bool signed_p;
1894
1895   /* If the ivs behave specially in the first iteration, or are
1896      added/multiplied after extending, we ignore them.  */
1897   if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx)
1898     return false;
1899   if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx)
1900     return false;
1901
1902   /* If there is some extend, it must match signedness of the comparison.  */
1903   switch (cond)
1904     {
1905       case LE:
1906       case LT:
1907         if (iv0->extend == ZERO_EXTEND
1908             || iv1->extend == ZERO_EXTEND)
1909           return false;
1910         signed_p = true;
1911         break;
1912
1913       case LEU:
1914       case LTU:
1915         if (iv0->extend == SIGN_EXTEND
1916             || iv1->extend == SIGN_EXTEND)
1917           return false;
1918         signed_p = false;
1919         break;
1920
1921       case NE:
1922         if (iv0->extend != UNKNOWN
1923             && iv1->extend != UNKNOWN
1924             && iv0->extend != iv1->extend)
1925           return false;
1926
1927         signed_p = false;
1928         if (iv0->extend != UNKNOWN)
1929           signed_p = iv0->extend == SIGN_EXTEND;
1930         if (iv1->extend != UNKNOWN)
1931           signed_p = iv1->extend == SIGN_EXTEND;
1932         break;
1933
1934       default:
1935         gcc_unreachable ();
1936     }
1937
1938   /* Values of both variables should be computed in the same mode.  These
1939      might indeed be different, if we have comparison like
1940
1941      (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
1942
1943      and iv0 and iv1 are both ivs iterating in SI mode, but calculated
1944      in different modes.  This does not seem impossible to handle, but
1945      it hardly ever occurs in practice.
1946      
1947      The only exception is the case when one of operands is invariant.
1948      For example pentium 3 generates comparisons like
1949      (lt (subreg:HI (reg:SI)) 100).  Here we assign HImode to 100, but we
1950      definitely do not want this prevent the optimization.  */
1951   comp_mode = iv0->extend_mode;
1952   if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode))
1953     comp_mode = iv1->extend_mode;
1954
1955   if (iv0->extend_mode != comp_mode)
1956     {
1957       if (iv0->mode != iv0->extend_mode
1958           || iv0->step != const0_rtx)
1959         return false;
1960
1961       iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
1962                                       comp_mode, iv0->base, iv0->mode);
1963       iv0->extend_mode = comp_mode;
1964     }
1965
1966   if (iv1->extend_mode != comp_mode)
1967     {
1968       if (iv1->mode != iv1->extend_mode
1969           || iv1->step != const0_rtx)
1970         return false;
1971
1972       iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
1973                                       comp_mode, iv1->base, iv1->mode);
1974       iv1->extend_mode = comp_mode;
1975     }
1976
1977   /* Check that both ivs belong to a range of a single mode.  If one of the
1978      operands is an invariant, we may need to shorten it into the common
1979      mode.  */
1980   if (iv0->mode == iv0->extend_mode
1981       && iv0->step == const0_rtx
1982       && iv0->mode != iv1->mode)
1983     shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc);
1984
1985   if (iv1->mode == iv1->extend_mode
1986       && iv1->step == const0_rtx
1987       && iv0->mode != iv1->mode)
1988     shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc);
1989
1990   if (iv0->mode != iv1->mode)
1991     return false;
1992
1993   desc->mode = iv0->mode;
1994   desc->signed_p = signed_p;
1995
1996   return true;
1997 }
1998
1999 /* Tries to estimate the maximum number of iterations.  */
2000
2001 static unsigned HOST_WIDEST_INT
2002 determine_max_iter (struct loop *loop, struct niter_desc *desc)
2003 {
2004   rtx niter = desc->niter_expr;
2005   rtx mmin, mmax, cmp;
2006   unsigned HOST_WIDEST_INT nmax, inc;
2007
2008   if (GET_CODE (niter) == AND
2009       && GET_CODE (XEXP (niter, 0)) == CONST_INT)
2010     {
2011       nmax = INTVAL (XEXP (niter, 0));
2012       if (!(nmax & (nmax + 1)))
2013         {
2014           desc->niter_max = nmax;
2015           return nmax;
2016         }
2017     }
2018
2019   get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
2020   nmax = INTVAL (mmax) - INTVAL (mmin);
2021
2022   if (GET_CODE (niter) == UDIV)
2023     {
2024       if (GET_CODE (XEXP (niter, 1)) != CONST_INT)
2025         {
2026           desc->niter_max = nmax;
2027           return nmax;
2028         }
2029       inc = INTVAL (XEXP (niter, 1));
2030       niter = XEXP (niter, 0);
2031     }
2032   else
2033     inc = 1;
2034
2035   /* We could use a binary search here, but for now improving the upper
2036      bound by just one eliminates one important corner case.  */
2037   cmp = gen_rtx_fmt_ee (desc->signed_p ? LT : LTU, VOIDmode, niter, mmax);
2038   simplify_using_initial_values (loop, UNKNOWN, &cmp);
2039   if (cmp == const_true_rtx)
2040     {
2041       nmax--;
2042
2043       if (dump_file)
2044         fprintf (dump_file, ";; improved upper bound by one.\n");
2045     }
2046   desc->niter_max = nmax / inc;
2047   return nmax / inc;
2048 }
2049
2050 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2051    the result into DESC.  Very similar to determine_number_of_iterations
2052    (basically its rtl version), complicated by things like subregs.  */
2053
2054 static void
2055 iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
2056                          struct niter_desc *desc)
2057 {
2058   rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;
2059   struct rtx_iv iv0, iv1, tmp_iv;
2060   rtx assumption, may_not_xform;
2061   enum rtx_code cond;
2062   enum machine_mode mode, comp_mode;
2063   rtx mmin, mmax, mode_mmin, mode_mmax;
2064   unsigned HOST_WIDEST_INT s, size, d, inv;
2065   HOST_WIDEST_INT up, down, inc, step_val;
2066   int was_sharp = false;
2067   rtx old_niter;
2068   bool step_is_pow2;
2069
2070   /* The meaning of these assumptions is this:
2071      if !assumptions
2072        then the rest of information does not have to be valid
2073      if noloop_assumptions then the loop does not roll
2074      if infinite then this exit is never used */
2075
2076   desc->assumptions = NULL_RTX;
2077   desc->noloop_assumptions = NULL_RTX;
2078   desc->infinite = NULL_RTX;
2079   desc->simple_p = true;
2080
2081   desc->const_iter = false;
2082   desc->niter_expr = NULL_RTX;
2083   desc->niter_max = 0;
2084
2085   cond = GET_CODE (condition);
2086   gcc_assert (COMPARISON_P (condition));
2087
2088   mode = GET_MODE (XEXP (condition, 0));
2089   if (mode == VOIDmode)
2090     mode = GET_MODE (XEXP (condition, 1));
2091   /* The constant comparisons should be folded.  */
2092   gcc_assert (mode != VOIDmode);
2093
2094   /* We only handle integers or pointers.  */
2095   if (GET_MODE_CLASS (mode) != MODE_INT
2096       && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
2097     goto fail;
2098
2099   op0 = XEXP (condition, 0);
2100   if (!iv_analyze (insn, op0, &iv0))
2101     goto fail;
2102   if (iv0.extend_mode == VOIDmode)
2103     iv0.mode = iv0.extend_mode = mode;
2104   
2105   op1 = XEXP (condition, 1);
2106   if (!iv_analyze (insn, op1, &iv1))
2107     goto fail;
2108   if (iv1.extend_mode == VOIDmode)
2109     iv1.mode = iv1.extend_mode = mode;
2110
2111   if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
2112       || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
2113     goto fail;
2114
2115   /* Check condition and normalize it.  */
2116
2117   switch (cond)
2118     {
2119       case GE:
2120       case GT:
2121       case GEU:
2122       case GTU:
2123         tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
2124         cond = swap_condition (cond);
2125         break;
2126       case NE:
2127       case LE:
2128       case LEU:
2129       case LT:
2130       case LTU:
2131         break;
2132       default:
2133         goto fail;
2134     }
2135
2136   /* Handle extends.  This is relatively nontrivial, so we only try in some
2137      easy cases, when we can canonicalize the ivs (possibly by adding some
2138      assumptions) to shape subreg (base + i * step).  This function also fills
2139      in desc->mode and desc->signed_p.  */
2140
2141   if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
2142     goto fail;
2143
2144   comp_mode = iv0.extend_mode;
2145   mode = iv0.mode;
2146   size = GET_MODE_BITSIZE (mode);
2147   get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
2148   mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
2149   mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
2150
2151   if (GET_CODE (iv0.step) != CONST_INT || GET_CODE (iv1.step) != CONST_INT)
2152     goto fail;
2153
2154   /* We can take care of the case of two induction variables chasing each other
2155      if the test is NE. I have never seen a loop using it, but still it is
2156      cool.  */
2157   if (iv0.step != const0_rtx && iv1.step != const0_rtx)
2158     {
2159       if (cond != NE)
2160         goto fail;
2161
2162       iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2163       iv1.step = const0_rtx;
2164     }
2165
2166   /* This is either infinite loop or the one that ends immediately, depending
2167      on initial values.  Unswitching should remove this kind of conditions.  */
2168   if (iv0.step == const0_rtx && iv1.step == const0_rtx)
2169     goto fail;
2170
2171   if (cond != NE)
2172     {
2173       if (iv0.step == const0_rtx)
2174         step_val = -INTVAL (iv1.step);
2175       else
2176         step_val = INTVAL (iv0.step);
2177
2178       /* Ignore loops of while (i-- < 10) type.  */
2179       if (step_val < 0)
2180         goto fail;
2181
2182       step_is_pow2 = !(step_val & (step_val - 1));
2183     }
2184   else
2185     {
2186       /* We do not care about whether the step is power of two in this
2187          case.  */
2188       step_is_pow2 = false;
2189       step_val = 0;
2190     }
2191
2192   /* Some more condition normalization.  We must record some assumptions
2193      due to overflows.  */
2194   switch (cond)
2195     {
2196       case LT:
2197       case LTU:
2198         /* We want to take care only of non-sharp relationals; this is easy,
2199            as in cases the overflow would make the transformation unsafe
2200            the loop does not roll.  Seemingly it would make more sense to want
2201            to take care of sharp relationals instead, as NE is more similar to
2202            them, but the problem is that here the transformation would be more
2203            difficult due to possibly infinite loops.  */
2204         if (iv0.step == const0_rtx)
2205           {
2206             tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2207             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2208                                                   mode_mmax);
2209             if (assumption == const_true_rtx)
2210               goto zero_iter_simplify;
2211             iv0.base = simplify_gen_binary (PLUS, comp_mode,
2212                                             iv0.base, const1_rtx);
2213           }
2214         else
2215           {
2216             tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2217             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2218                                                   mode_mmin);
2219             if (assumption == const_true_rtx)
2220               goto zero_iter_simplify;
2221             iv1.base = simplify_gen_binary (PLUS, comp_mode,
2222                                             iv1.base, constm1_rtx);
2223           }
2224
2225         if (assumption != const0_rtx)
2226           desc->noloop_assumptions =
2227                   alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2228         cond = (cond == LT) ? LE : LEU;
2229
2230         /* It will be useful to be able to tell the difference once more in
2231            LE -> NE reduction.  */
2232         was_sharp = true;
2233         break;
2234       default: ;
2235     }
2236
2237   /* Take care of trivially infinite loops.  */
2238   if (cond != NE)
2239     {
2240       if (iv0.step == const0_rtx)
2241         {
2242           tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2243           if (rtx_equal_p (tmp, mode_mmin))
2244             {
2245               desc->infinite =
2246                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2247               /* Fill in the remaining fields somehow.  */
2248               goto zero_iter_simplify;
2249             }
2250         }
2251       else
2252         {
2253           tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2254           if (rtx_equal_p (tmp, mode_mmax))
2255             {
2256               desc->infinite =
2257                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2258               /* Fill in the remaining fields somehow.  */
2259               goto zero_iter_simplify;
2260             }
2261         }
2262     }
2263
2264   /* If we can we want to take care of NE conditions instead of size
2265      comparisons, as they are much more friendly (most importantly
2266      this takes care of special handling of loops with step 1).  We can
2267      do it if we first check that upper bound is greater or equal to
2268      lower bound, their difference is constant c modulo step and that
2269      there is not an overflow.  */
2270   if (cond != NE)
2271     {
2272       if (iv0.step == const0_rtx)
2273         step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
2274       else
2275         step = iv0.step;
2276       delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2277       delta = lowpart_subreg (mode, delta, comp_mode);
2278       delta = simplify_gen_binary (UMOD, mode, delta, step);
2279       may_xform = const0_rtx;
2280       may_not_xform = const_true_rtx;
2281
2282       if (GET_CODE (delta) == CONST_INT)
2283         {
2284           if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
2285             {
2286               /* A special case.  We have transformed condition of type
2287                  for (i = 0; i < 4; i += 4)
2288                  into
2289                  for (i = 0; i <= 3; i += 4)
2290                  obviously if the test for overflow during that transformation
2291                  passed, we cannot overflow here.  Most importantly any
2292                  loop with sharp end condition and step 1 falls into this
2293                  category, so handling this case specially is definitely
2294                  worth the troubles.  */
2295               may_xform = const_true_rtx;
2296             }
2297           else if (iv0.step == const0_rtx)
2298             {
2299               bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
2300               bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
2301               bound = lowpart_subreg (mode, bound, comp_mode);
2302               tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2303               may_xform = simplify_gen_relational (cond, SImode, mode,
2304                                                    bound, tmp);
2305               may_not_xform = simplify_gen_relational (reverse_condition (cond),
2306                                                        SImode, mode,
2307                                                        bound, tmp);
2308             }
2309           else
2310             {
2311               bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
2312               bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
2313               bound = lowpart_subreg (mode, bound, comp_mode);
2314               tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2315               may_xform = simplify_gen_relational (cond, SImode, mode,
2316                                                    tmp, bound);
2317               may_not_xform = simplify_gen_relational (reverse_condition (cond),
2318                                                        SImode, mode,
2319                                                        tmp, bound);
2320             }
2321         }
2322
2323       if (may_xform != const0_rtx)
2324         {
2325           /* We perform the transformation always provided that it is not
2326              completely senseless.  This is OK, as we would need this assumption
2327              to determine the number of iterations anyway.  */
2328           if (may_xform != const_true_rtx)
2329             {
2330               /* If the step is a power of two and the final value we have
2331                  computed overflows, the cycle is infinite.  Otherwise it
2332                  is nontrivial to compute the number of iterations.  */
2333               if (step_is_pow2)
2334                 desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
2335                                                   desc->infinite);
2336               else
2337                 desc->assumptions = alloc_EXPR_LIST (0, may_xform,
2338                                                      desc->assumptions);
2339             }
2340
2341           /* We are going to lose some information about upper bound on
2342              number of iterations in this step, so record the information
2343              here.  */
2344           inc = INTVAL (iv0.step) - INTVAL (iv1.step);
2345           if (GET_CODE (iv1.base) == CONST_INT)
2346             up = INTVAL (iv1.base);
2347           else
2348             up = INTVAL (mode_mmax) - inc;
2349           down = INTVAL (GET_CODE (iv0.base) == CONST_INT
2350                          ? iv0.base
2351                          : mode_mmin);
2352           desc->niter_max = (up - down) / inc + 1;
2353
2354           if (iv0.step == const0_rtx)
2355             {
2356               iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
2357               iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
2358             }
2359           else
2360             {
2361               iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
2362               iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
2363             }
2364
2365           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2366           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2367           assumption = simplify_gen_relational (reverse_condition (cond),
2368                                                 SImode, mode, tmp0, tmp1);
2369           if (assumption == const_true_rtx)
2370             goto zero_iter_simplify;
2371           else if (assumption != const0_rtx)
2372             desc->noloop_assumptions =
2373                     alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2374           cond = NE;
2375         }
2376     }
2377
2378   /* Count the number of iterations.  */
2379   if (cond == NE)
2380     {
2381       /* Everything we do here is just arithmetics modulo size of mode.  This
2382          makes us able to do more involved computations of number of iterations
2383          than in other cases.  First transform the condition into shape
2384          s * i <> c, with s positive.  */
2385       iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2386       iv0.base = const0_rtx;
2387       iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2388       iv1.step = const0_rtx;
2389       if (INTVAL (iv0.step) < 0)
2390         {
2391           iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, mode);
2392           iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, mode);
2393         }
2394       iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2395
2396       /* Let nsd (s, size of mode) = d.  If d does not divide c, the loop
2397          is infinite.  Otherwise, the number of iterations is
2398          (inverse(s/d) * (c/d)) mod (size of mode/d).  */
2399       s = INTVAL (iv0.step); d = 1;
2400       while (s % 2 != 1)
2401         {
2402           s /= 2;
2403           d *= 2;
2404           size--;
2405         }
2406       bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
2407
2408       tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2409       tmp = simplify_gen_binary (UMOD, mode, tmp1, GEN_INT (d));
2410       assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
2411       desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
2412
2413       tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
2414       inv = inverse (s, size);
2415       tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
2416       desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
2417     }
2418   else
2419     {
2420       if (iv1.step == const0_rtx)
2421         /* Condition in shape a + s * i <= b
2422            We must know that b + s does not overflow and a <= b + s and then we
2423            can compute number of iterations as (b + s - a) / s.  (It might
2424            seem that we in fact could be more clever about testing the b + s
2425            overflow condition using some information about b - a mod s,
2426            but it was already taken into account during LE -> NE transform).  */
2427         {
2428           step = iv0.step;
2429           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2430           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2431
2432           bound = simplify_gen_binary (MINUS, mode, mode_mmax,
2433                                        lowpart_subreg (mode, step,
2434                                                        comp_mode));
2435           if (step_is_pow2)
2436             {
2437               rtx t0, t1;
2438
2439               /* If s is power of 2, we know that the loop is infinite if
2440                  a % s <= b % s and b + s overflows.  */
2441               assumption = simplify_gen_relational (reverse_condition (cond),
2442                                                     SImode, mode,
2443                                                     tmp1, bound);
2444
2445               t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2446               t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2447               tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2448               assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2449               desc->infinite =
2450                       alloc_EXPR_LIST (0, assumption, desc->infinite);
2451             }
2452           else
2453             {
2454               assumption = simplify_gen_relational (cond, SImode, mode,
2455                                                     tmp1, bound);
2456               desc->assumptions =
2457                       alloc_EXPR_LIST (0, assumption, desc->assumptions);
2458             }
2459
2460           tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
2461           tmp = lowpart_subreg (mode, tmp, comp_mode);
2462           assumption = simplify_gen_relational (reverse_condition (cond),
2463                                                 SImode, mode, tmp0, tmp);
2464
2465           delta = simplify_gen_binary (PLUS, mode, tmp1, step);
2466           delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
2467         }
2468       else
2469         {
2470           /* Condition in shape a <= b - s * i
2471              We must know that a - s does not overflow and a - s <= b and then
2472              we can again compute number of iterations as (b - (a - s)) / s.  */
2473           step = simplify_gen_unary (NEG, mode, iv1.step, mode);
2474           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2475           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2476
2477           bound = simplify_gen_binary (PLUS, mode, mode_mmin,
2478                                        lowpart_subreg (mode, step, comp_mode));
2479           if (step_is_pow2)
2480             {
2481               rtx t0, t1;
2482
2483               /* If s is power of 2, we know that the loop is infinite if
2484                  a % s <= b % s and a - s overflows.  */
2485               assumption = simplify_gen_relational (reverse_condition (cond),
2486                                                     SImode, mode,
2487                                                     bound, tmp0);
2488
2489               t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2490               t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2491               tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2492               assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2493               desc->infinite =
2494                       alloc_EXPR_LIST (0, assumption, desc->infinite);
2495             }
2496           else
2497             {
2498               assumption = simplify_gen_relational (cond, SImode, mode,
2499                                                     bound, tmp0);
2500               desc->assumptions =
2501                       alloc_EXPR_LIST (0, assumption, desc->assumptions);
2502             }
2503
2504           tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
2505           tmp = lowpart_subreg (mode, tmp, comp_mode);
2506           assumption = simplify_gen_relational (reverse_condition (cond),
2507                                                 SImode, mode,
2508                                                 tmp, tmp1);
2509           delta = simplify_gen_binary (MINUS, mode, tmp0, step);
2510           delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
2511         }
2512       if (assumption == const_true_rtx)
2513         goto zero_iter_simplify;
2514       else if (assumption != const0_rtx)
2515         desc->noloop_assumptions =
2516                 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2517       delta = simplify_gen_binary (UDIV, mode, delta, step);
2518       desc->niter_expr = delta;
2519     }
2520
2521   old_niter = desc->niter_expr;
2522
2523   simplify_using_initial_values (loop, AND, &desc->assumptions);
2524   if (desc->assumptions
2525       && XEXP (desc->assumptions, 0) == const0_rtx)
2526     goto fail;
2527   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2528   simplify_using_initial_values (loop, IOR, &desc->infinite);
2529   simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2530
2531   /* Rerun the simplification.  Consider code (created by copying loop headers)
2532
2533      i = 0;
2534
2535      if (0 < n)
2536        {
2537          do
2538            {
2539              i++;
2540            } while (i < n);
2541        }
2542
2543     The first pass determines that i = 0, the second pass uses it to eliminate
2544     noloop assumption.  */
2545
2546   simplify_using_initial_values (loop, AND, &desc->assumptions);
2547   if (desc->assumptions
2548       && XEXP (desc->assumptions, 0) == const0_rtx)
2549     goto fail;
2550   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2551   simplify_using_initial_values (loop, IOR, &desc->infinite);
2552   simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2553
2554   if (desc->noloop_assumptions
2555       && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
2556     goto zero_iter;
2557
2558   if (GET_CODE (desc->niter_expr) == CONST_INT)
2559     {
2560       unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
2561
2562       desc->const_iter = true;
2563       desc->niter_max = desc->niter = val & GET_MODE_MASK (desc->mode);
2564     }
2565   else
2566     {
2567       if (!desc->niter_max)
2568         desc->niter_max = determine_max_iter (loop, desc);
2569
2570       /* simplify_using_initial_values does a copy propagation on the registers
2571          in the expression for the number of iterations.  This prolongs life
2572          ranges of registers and increases register pressure, and usually
2573          brings no gain (and if it happens to do, the cse pass will take care
2574          of it anyway).  So prevent this behavior, unless it enabled us to
2575          derive that the number of iterations is a constant.  */
2576       desc->niter_expr = old_niter;
2577     }
2578
2579   return;
2580
2581 zero_iter_simplify:
2582   /* Simplify the assumptions.  */
2583   simplify_using_initial_values (loop, AND, &desc->assumptions);
2584   if (desc->assumptions
2585       && XEXP (desc->assumptions, 0) == const0_rtx)
2586     goto fail;
2587   simplify_using_initial_values (loop, IOR, &desc->infinite);
2588
2589   /* Fallthru.  */
2590 zero_iter:
2591   desc->const_iter = true;
2592   desc->niter = 0;
2593   desc->niter_max = 0;
2594   desc->noloop_assumptions = NULL_RTX;
2595   desc->niter_expr = const0_rtx;
2596   return;
2597
2598 fail:
2599   desc->simple_p = false;
2600   return;
2601 }
2602
2603 /* Checks whether E is a simple exit from LOOP and stores its description
2604    into DESC.  */
2605
2606 static void
2607 check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
2608 {
2609   basic_block exit_bb;
2610   rtx condition, at;
2611   edge ein;
2612
2613   exit_bb = e->src;
2614   desc->simple_p = false;
2615
2616   /* It must belong directly to the loop.  */
2617   if (exit_bb->loop_father != loop)
2618     return;
2619
2620   /* It must be tested (at least) once during any iteration.  */
2621   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
2622     return;
2623
2624   /* It must end in a simple conditional jump.  */
2625   if (!any_condjump_p (BB_END (exit_bb)))
2626     return;
2627
2628   ein = EDGE_SUCC (exit_bb, 0);
2629   if (ein == e)
2630     ein = EDGE_SUCC (exit_bb, 1);
2631
2632   desc->out_edge = e;
2633   desc->in_edge = ein;
2634
2635   /* Test whether the condition is suitable.  */
2636   if (!(condition = get_condition (BB_END (ein->src), &at, false, false)))
2637     return;
2638
2639   if (ein->flags & EDGE_FALLTHRU)
2640     {
2641       condition = reversed_condition (condition);
2642       if (!condition)
2643         return;
2644     }
2645
2646   /* Check that we are able to determine number of iterations and fill
2647      in information about it.  */
2648   iv_number_of_iterations (loop, at, condition, desc);
2649 }
2650
2651 /* Finds a simple exit of LOOP and stores its description into DESC.  */
2652
2653 void
2654 find_simple_exit (struct loop *loop, struct niter_desc *desc)
2655 {
2656   unsigned i;
2657   basic_block *body;
2658   edge e;
2659   struct niter_desc act;
2660   bool any = false;
2661   edge_iterator ei;
2662
2663   desc->simple_p = false;
2664   body = get_loop_body (loop);
2665
2666   for (i = 0; i < loop->num_nodes; i++)
2667     {
2668       FOR_EACH_EDGE (e, ei, body[i]->succs)
2669         {
2670           if (flow_bb_inside_loop_p (loop, e->dest))
2671             continue;
2672           
2673           check_simple_exit (loop, e, &act);
2674           if (!act.simple_p)
2675             continue;
2676
2677           if (!any)
2678             any = true;
2679           else
2680             {
2681               /* Prefer constant iterations; the less the better.  */
2682               if (!act.const_iter
2683                   || (desc->const_iter && act.niter >= desc->niter))
2684                 continue;
2685
2686               /* Also if the actual exit may be infinite, while the old one
2687                  not, prefer the old one.  */
2688               if (act.infinite && !desc->infinite)
2689                 continue;
2690             }
2691           
2692           *desc = act;
2693         }
2694     }
2695
2696   if (dump_file)
2697     {
2698       if (desc->simple_p)
2699         {
2700           fprintf (dump_file, "Loop %d is simple:\n", loop->num);
2701           fprintf (dump_file, "  simple exit %d -> %d\n",
2702                    desc->out_edge->src->index,
2703                    desc->out_edge->dest->index);
2704           if (desc->assumptions)
2705             {
2706               fprintf (dump_file, "  assumptions: ");
2707               print_rtl (dump_file, desc->assumptions);
2708               fprintf (dump_file, "\n");
2709             }
2710           if (desc->noloop_assumptions)
2711             {
2712               fprintf (dump_file, "  does not roll if: ");
2713               print_rtl (dump_file, desc->noloop_assumptions);
2714               fprintf (dump_file, "\n");
2715             }
2716           if (desc->infinite)
2717             {
2718               fprintf (dump_file, "  infinite if: ");
2719               print_rtl (dump_file, desc->infinite);
2720               fprintf (dump_file, "\n");
2721             }
2722
2723           fprintf (dump_file, "  number of iterations: ");
2724           print_rtl (dump_file, desc->niter_expr);
2725           fprintf (dump_file, "\n");
2726
2727           fprintf (dump_file, "  upper bound: ");
2728           fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter_max);
2729           fprintf (dump_file, "\n");
2730         }
2731       else
2732         fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
2733     }
2734
2735   free (body);
2736 }
2737
2738 /* Creates a simple loop description of LOOP if it was not computed
2739    already.  */
2740
2741 struct niter_desc *
2742 get_simple_loop_desc (struct loop *loop)
2743 {
2744   struct niter_desc *desc = simple_loop_desc (loop);
2745
2746   if (desc)
2747     return desc;
2748
2749   desc = XNEW (struct niter_desc);
2750   iv_analysis_loop_init (loop);
2751   find_simple_exit (loop, desc);
2752   loop->aux = desc;
2753
2754   if (desc->simple_p && (desc->assumptions || desc->infinite))
2755     {
2756       const char *wording; 
2757
2758       /* Assume that no overflow happens and that the loop is finite.  
2759          We already warned at the tree level if we ran optimizations there.  */
2760       if (!flag_tree_loop_optimize && warn_unsafe_loop_optimizations)
2761         {
2762           if (desc->infinite)
2763             {
2764               wording = 
2765                 flag_unsafe_loop_optimizations
2766                 ? N_("assuming that the loop is not infinite")
2767                 : N_("cannot optimize possibly infinite loops");
2768               warning (OPT_Wunsafe_loop_optimizations, "%s",
2769                        gettext (wording));
2770             }
2771           if (desc->assumptions)
2772             {
2773               wording = 
2774                 flag_unsafe_loop_optimizations
2775                 ? N_("assuming that the loop counter does not overflow")
2776                 : N_("cannot optimize loop, the loop counter may overflow");
2777               warning (OPT_Wunsafe_loop_optimizations, "%s",
2778                        gettext (wording));
2779             }
2780         }
2781
2782       if (flag_unsafe_loop_optimizations)
2783         {
2784           desc->assumptions = NULL_RTX;
2785           desc->infinite = NULL_RTX;
2786         }
2787     }
2788
2789   return desc;
2790 }
2791
2792 /* Releases simple loop description for LOOP.  */
2793
2794 void
2795 free_simple_loop_desc (struct loop *loop)
2796 {
2797   struct niter_desc *desc = simple_loop_desc (loop);
2798
2799   if (!desc)
2800     return;
2801
2802   free (desc);
2803   loop->aux = NULL;
2804 }