OSDN Git Service

PR tree-optimization/22236
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-loop-ivopts.c
1 /* Induction variable optimizations.
2    Copyright (C) 2003, 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 pass tries to find the optimal set of induction variables for the loop.
22    It optimizes just the basic linear induction variables (although adding
23    support for other types should not be too hard).  It includes the
24    optimizations commonly known as strength reduction, induction variable
25    coalescing and induction variable elimination.  It does it in the
26    following steps:
27
28    1) The interesting uses of induction variables are found.  This includes
29
30       -- uses of induction variables in non-linear expressions
31       -- addresses of arrays
32       -- comparisons of induction variables
33
34    2) Candidates for the induction variables are found.  This includes
35
36       -- old induction variables
37       -- the variables defined by expressions derived from the "interesting
38          uses" above
39
40    3) The optimal (w.r. to a cost function) set of variables is chosen.  The
41       cost function assigns a cost to sets of induction variables and consists
42       of three parts:
43
44       -- The use costs.  Each of the interesting uses chooses the best induction
45          variable in the set and adds its cost to the sum.  The cost reflects
46          the time spent on modifying the induction variables value to be usable
47          for the given purpose (adding base and offset for arrays, etc.).
48       -- The variable costs.  Each of the variables has a cost assigned that
49          reflects the costs associated with incrementing the value of the
50          variable.  The original variables are somewhat preferred.
51       -- The set cost.  Depending on the size of the set, extra cost may be
52          added to reflect register pressure.
53
54       All the costs are defined in a machine-specific way, using the target
55       hooks and machine descriptions to determine them.
56
57    4) The trees are transformed to use the new variables, the dead code is
58       removed.
59    
60    All of this is done loop by loop.  Doing it globally is theoretically
61    possible, it might give a better performance and it might enable us
62    to decide costs more precisely, but getting all the interactions right
63    would be complicated.  */
64
65 #include "config.h"
66 #include "system.h"
67 #include "coretypes.h"
68 #include "tm.h"
69 #include "tree.h"
70 #include "rtl.h"
71 #include "tm_p.h"
72 #include "hard-reg-set.h"
73 #include "basic-block.h"
74 #include "output.h"
75 #include "diagnostic.h"
76 #include "tree-flow.h"
77 #include "tree-dump.h"
78 #include "timevar.h"
79 #include "cfgloop.h"
80 #include "varray.h"
81 #include "expr.h"
82 #include "tree-pass.h"
83 #include "ggc.h"
84 #include "insn-config.h"
85 #include "recog.h"
86 #include "hashtab.h"
87 #include "tree-chrec.h"
88 #include "tree-scalar-evolution.h"
89 #include "cfgloop.h"
90 #include "params.h"
91 #include "langhooks.h"
92
93 /* The infinite cost.  */
94 #define INFTY 10000000
95
96 /* The expected number of loop iterations.  TODO -- use profiling instead of
97    this.  */
98 #define AVG_LOOP_NITER(LOOP) 5
99
100
101 /* Representation of the induction variable.  */
102 struct iv
103 {
104   tree base;            /* Initial value of the iv.  */
105   tree base_object;     /* A memory object to that the induction variable points.  */
106   tree step;            /* Step of the iv (constant only).  */
107   tree ssa_name;        /* The ssa name with the value.  */
108   bool biv_p;           /* Is it a biv?  */
109   bool have_use_for;    /* Do we already have a use for it?  */
110   unsigned use_id;      /* The identifier in the use if it is the case.  */
111 };
112
113 /* Per-ssa version information (induction variable descriptions, etc.).  */
114 struct version_info
115 {
116   tree name;            /* The ssa name.  */
117   struct iv *iv;        /* Induction variable description.  */
118   bool has_nonlin_use;  /* For a loop-level invariant, whether it is used in
119                            an expression that is not an induction variable.  */
120   unsigned inv_id;      /* Id of an invariant.  */
121   bool preserve_biv;    /* For the original biv, whether to preserve it.  */
122 };
123
124 /* Information attached to loop.  */
125 struct loop_data
126 {
127   unsigned regs_used;   /* Number of registers used.  */
128 };
129
130 /* Types of uses.  */
131 enum use_type
132 {
133   USE_NONLINEAR_EXPR,   /* Use in a nonlinear expression.  */
134   USE_OUTER,            /* The induction variable is used outside the loop.  */
135   USE_ADDRESS,          /* Use in an address.  */
136   USE_COMPARE           /* Use is a compare.  */
137 };
138
139 /* The candidate - cost pair.  */
140 struct cost_pair
141 {
142   struct iv_cand *cand; /* The candidate.  */
143   unsigned cost;        /* The cost.  */
144   bitmap depends_on;    /* The list of invariants that have to be
145                            preserved.  */
146   tree value;           /* For final value elimination, the expression for
147                            the final value of the iv.  For iv elimination,
148                            the new bound to compare with.  */
149 };
150
151 /* Use.  */
152 struct iv_use
153 {
154   unsigned id;          /* The id of the use.  */
155   enum use_type type;   /* Type of the use.  */
156   struct iv *iv;        /* The induction variable it is based on.  */
157   tree stmt;            /* Statement in that it occurs.  */
158   tree *op_p;           /* The place where it occurs.  */
159   bitmap related_cands; /* The set of "related" iv candidates, plus the common
160                            important ones.  */
161
162   unsigned n_map_members; /* Number of candidates in the cost_map list.  */
163   struct cost_pair *cost_map;
164                         /* The costs wrto the iv candidates.  */
165
166   struct iv_cand *selected;
167                         /* The selected candidate.  */
168 };
169
170 /* The position where the iv is computed.  */
171 enum iv_position
172 {
173   IP_NORMAL,            /* At the end, just before the exit condition.  */
174   IP_END,               /* At the end of the latch block.  */
175   IP_ORIGINAL           /* The original biv.  */
176 };
177
178 /* The induction variable candidate.  */
179 struct iv_cand
180 {
181   unsigned id;          /* The number of the candidate.  */
182   bool important;       /* Whether this is an "important" candidate, i.e. such
183                            that it should be considered by all uses.  */
184   enum iv_position pos; /* Where it is computed.  */
185   tree incremented_at;  /* For original biv, the statement where it is
186                            incremented.  */
187   tree var_before;      /* The variable used for it before increment.  */
188   tree var_after;       /* The variable used for it after increment.  */
189   struct iv *iv;        /* The value of the candidate.  NULL for
190                            "pseudocandidate" used to indicate the possibility
191                            to replace the final value of an iv by direct
192                            computation of the value.  */
193   unsigned cost;        /* Cost of the candidate.  */
194   bitmap depends_on;    /* The list of invariants that are used in step of the
195                            biv.  */
196 };
197
198 /* The data used by the induction variable optimizations.  */
199
200 typedef struct iv_use *iv_use_p;
201 DEF_VEC_P(iv_use_p);
202 DEF_VEC_ALLOC_P(iv_use_p,heap);
203
204 typedef struct iv_cand *iv_cand_p;
205 DEF_VEC_P(iv_cand_p);
206 DEF_VEC_ALLOC_P(iv_cand_p,heap);
207
208 struct ivopts_data
209 {
210   /* The currently optimized loop.  */
211   struct loop *current_loop;
212
213   /* Numbers of iterations for all exits of the current loop.  */
214   htab_t niters;
215
216   /* The size of version_info array allocated.  */
217   unsigned version_info_size;
218
219   /* The array of information for the ssa names.  */
220   struct version_info *version_info;
221
222   /* The bitmap of indices in version_info whose value was changed.  */
223   bitmap relevant;
224
225   /* The maximum invariant id.  */
226   unsigned max_inv_id;
227
228   /* The uses of induction variables.  */
229   VEC(iv_use_p,heap) *iv_uses;
230
231   /* The candidates.  */
232   VEC(iv_cand_p,heap) *iv_candidates;
233
234   /* A bitmap of important candidates.  */
235   bitmap important_candidates;
236
237   /* Whether to consider just related and important candidates when replacing a
238      use.  */
239   bool consider_all_candidates;
240 };
241
242 /* An assignment of iv candidates to uses.  */
243
244 struct iv_ca
245 {
246   /* The number of uses covered by the assignment.  */
247   unsigned upto;
248
249   /* Number of uses that cannot be expressed by the candidates in the set.  */
250   unsigned bad_uses;
251
252   /* Candidate assigned to a use, together with the related costs.  */
253   struct cost_pair **cand_for_use;
254
255   /* Number of times each candidate is used.  */
256   unsigned *n_cand_uses;
257
258   /* The candidates used.  */
259   bitmap cands;
260
261   /* The number of candidates in the set.  */
262   unsigned n_cands;
263
264   /* Total number of registers needed.  */
265   unsigned n_regs;
266
267   /* Total cost of expressing uses.  */
268   unsigned cand_use_cost;
269
270   /* Total cost of candidates.  */
271   unsigned cand_cost;
272
273   /* Number of times each invariant is used.  */
274   unsigned *n_invariant_uses;
275
276   /* Total cost of the assignment.  */
277   unsigned cost;
278 };
279
280 /* Difference of two iv candidate assignments.  */
281
282 struct iv_ca_delta
283 {
284   /* Changed use.  */
285   struct iv_use *use;
286
287   /* An old assignment (for rollback purposes).  */
288   struct cost_pair *old_cp;
289
290   /* A new assignment.  */
291   struct cost_pair *new_cp;
292
293   /* Next change in the list.  */
294   struct iv_ca_delta *next_change;
295 };
296
297 /* Bound on number of candidates below that all candidates are considered.  */
298
299 #define CONSIDER_ALL_CANDIDATES_BOUND \
300   ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
301
302 /* If there are more iv occurrences, we just give up (it is quite unlikely that
303    optimizing such a loop would help, and it would take ages).  */
304
305 #define MAX_CONSIDERED_USES \
306   ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
307
308 /* If there are at most this number of ivs in the set, try removing unnecessary
309    ivs from the set always.  */
310
311 #define ALWAYS_PRUNE_CAND_SET_BOUND \
312   ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
313
314 /* The list of trees for that the decl_rtl field must be reset is stored
315    here.  */
316
317 static VEC(tree,heap) *decl_rtl_to_reset;
318
319 /* Number of uses recorded in DATA.  */
320
321 static inline unsigned
322 n_iv_uses (struct ivopts_data *data)
323 {
324   return VEC_length (iv_use_p, data->iv_uses);
325 }
326
327 /* Ith use recorded in DATA.  */
328
329 static inline struct iv_use *
330 iv_use (struct ivopts_data *data, unsigned i)
331 {
332   return VEC_index (iv_use_p, data->iv_uses, i);
333 }
334
335 /* Number of candidates recorded in DATA.  */
336
337 static inline unsigned
338 n_iv_cands (struct ivopts_data *data)
339 {
340   return VEC_length (iv_cand_p, data->iv_candidates);
341 }
342
343 /* Ith candidate recorded in DATA.  */
344
345 static inline struct iv_cand *
346 iv_cand (struct ivopts_data *data, unsigned i)
347 {
348   return VEC_index (iv_cand_p, data->iv_candidates, i);
349 }
350
351 /* The data for LOOP.  */
352
353 static inline struct loop_data *
354 loop_data (struct loop *loop)
355 {
356   return loop->aux;
357 }
358
359 /* The single loop exit if it dominates the latch, NULL otherwise.  */
360
361 edge
362 single_dom_exit (struct loop *loop)
363 {
364   edge exit = loop->single_exit;
365
366   if (!exit)
367     return NULL;
368
369   if (!just_once_each_iteration_p (loop, exit->src))
370     return NULL;
371
372   return exit;
373 }
374
375 /* Dumps information about the induction variable IV to FILE.  */
376
377 extern void dump_iv (FILE *, struct iv *);
378 void
379 dump_iv (FILE *file, struct iv *iv)
380 {
381   if (iv->ssa_name)
382     {
383       fprintf (file, "ssa name ");
384       print_generic_expr (file, iv->ssa_name, TDF_SLIM);
385       fprintf (file, "\n");
386     }
387
388   fprintf (file, "  type ");
389   print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
390   fprintf (file, "\n");
391
392   if (iv->step)
393     {
394       fprintf (file, "  base ");
395       print_generic_expr (file, iv->base, TDF_SLIM);
396       fprintf (file, "\n");
397
398       fprintf (file, "  step ");
399       print_generic_expr (file, iv->step, TDF_SLIM);
400       fprintf (file, "\n");
401     }
402   else
403     {
404       fprintf (file, "  invariant ");
405       print_generic_expr (file, iv->base, TDF_SLIM);
406       fprintf (file, "\n");
407     }
408
409   if (iv->base_object)
410     {
411       fprintf (file, "  base object ");
412       print_generic_expr (file, iv->base_object, TDF_SLIM);
413       fprintf (file, "\n");
414     }
415
416   if (iv->biv_p)
417     fprintf (file, "  is a biv\n");
418 }
419
420 /* Dumps information about the USE to FILE.  */
421
422 extern void dump_use (FILE *, struct iv_use *);
423 void
424 dump_use (FILE *file, struct iv_use *use)
425 {
426   fprintf (file, "use %d\n", use->id);
427
428   switch (use->type)
429     {
430     case USE_NONLINEAR_EXPR:
431       fprintf (file, "  generic\n");
432       break;
433
434     case USE_OUTER:
435       fprintf (file, "  outside\n");
436       break;
437
438     case USE_ADDRESS:
439       fprintf (file, "  address\n");
440       break;
441
442     case USE_COMPARE:
443       fprintf (file, "  compare\n");
444       break;
445
446     default:
447       gcc_unreachable ();
448     }
449
450   fprintf (file, "  in statement ");
451   print_generic_expr (file, use->stmt, TDF_SLIM);
452   fprintf (file, "\n");
453
454   fprintf (file, "  at position ");
455   if (use->op_p)
456     print_generic_expr (file, *use->op_p, TDF_SLIM);
457   fprintf (file, "\n");
458
459   dump_iv (file, use->iv);
460
461   if (use->related_cands)
462     {
463       fprintf (file, "  related candidates ");
464       dump_bitmap (file, use->related_cands);
465     }
466 }
467
468 /* Dumps information about the uses to FILE.  */
469
470 extern void dump_uses (FILE *, struct ivopts_data *);
471 void
472 dump_uses (FILE *file, struct ivopts_data *data)
473 {
474   unsigned i;
475   struct iv_use *use;
476
477   for (i = 0; i < n_iv_uses (data); i++)
478     {
479       use = iv_use (data, i);
480
481       dump_use (file, use);
482       fprintf (file, "\n");
483     }
484 }
485
486 /* Dumps information about induction variable candidate CAND to FILE.  */
487
488 extern void dump_cand (FILE *, struct iv_cand *);
489 void
490 dump_cand (FILE *file, struct iv_cand *cand)
491 {
492   struct iv *iv = cand->iv;
493
494   fprintf (file, "candidate %d%s\n",
495            cand->id, cand->important ? " (important)" : "");
496
497   if (cand->depends_on)
498     {
499       fprintf (file, "  depends on ");
500       dump_bitmap (file, cand->depends_on);
501     }
502
503   if (!iv)
504     {
505       fprintf (file, "  final value replacement\n");
506       return;
507     }
508
509   switch (cand->pos)
510     {
511     case IP_NORMAL:
512       fprintf (file, "  incremented before exit test\n");
513       break;
514
515     case IP_END:
516       fprintf (file, "  incremented at end\n");
517       break;
518
519     case IP_ORIGINAL:
520       fprintf (file, "  original biv\n");
521       break;
522     }
523
524   dump_iv (file, iv);
525 }
526
527 /* Returns the info for ssa version VER.  */
528
529 static inline struct version_info *
530 ver_info (struct ivopts_data *data, unsigned ver)
531 {
532   return data->version_info + ver;
533 }
534
535 /* Returns the info for ssa name NAME.  */
536
537 static inline struct version_info *
538 name_info (struct ivopts_data *data, tree name)
539 {
540   return ver_info (data, SSA_NAME_VERSION (name));
541 }
542
543 /* Checks whether there exists number X such that X * B = A, counting modulo
544    2^BITS.  */
545
546 static bool
547 divide (unsigned bits, unsigned HOST_WIDE_INT a, unsigned HOST_WIDE_INT b,
548         HOST_WIDE_INT *x)
549 {
550   unsigned HOST_WIDE_INT mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
551   unsigned HOST_WIDE_INT inv, ex, val;
552   unsigned i;
553
554   a &= mask;
555   b &= mask;
556
557   /* First divide the whole equation by 2 as long as possible.  */
558   while (!(a & 1) && !(b & 1))
559     {
560       a >>= 1;
561       b >>= 1;
562       bits--;
563       mask >>= 1;
564     }
565
566   if (!(b & 1))
567     {
568       /* If b is still even, a is odd and there is no such x.  */
569       return false;
570     }
571
572   /* Find the inverse of b.  We compute it as
573      b^(2^(bits - 1) - 1) (mod 2^bits).  */
574   inv = 1;
575   ex = b;
576   for (i = 0; i < bits - 1; i++)
577     {
578       inv = (inv * ex) & mask;
579       ex = (ex * ex) & mask;
580     }
581
582   val = (a * inv) & mask;
583
584   gcc_assert (((val * b) & mask) == a);
585
586   if ((val >> (bits - 1)) & 1)
587     val |= ~mask;
588
589   *x = val;
590
591   return true;
592 }
593
594 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
595    emitted in LOOP.  */
596
597 static bool
598 stmt_after_ip_normal_pos (struct loop *loop, tree stmt)
599 {
600   basic_block bb = ip_normal_pos (loop), sbb = bb_for_stmt (stmt);
601
602   gcc_assert (bb);
603
604   if (sbb == loop->latch)
605     return true;
606
607   if (sbb != bb)
608     return false;
609
610   return stmt == last_stmt (bb);
611 }
612
613 /* Returns true if STMT if after the place where the original induction
614    variable CAND is incremented.  */
615
616 static bool
617 stmt_after_ip_original_pos (struct iv_cand *cand, tree stmt)
618 {
619   basic_block cand_bb = bb_for_stmt (cand->incremented_at);
620   basic_block stmt_bb = bb_for_stmt (stmt);
621   block_stmt_iterator bsi;
622
623   if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
624     return false;
625
626   if (stmt_bb != cand_bb)
627     return true;
628
629   /* Scan the block from the end, since the original ivs are usually
630      incremented at the end of the loop body.  */
631   for (bsi = bsi_last (stmt_bb); ; bsi_prev (&bsi))
632     {
633       if (bsi_stmt (bsi) == cand->incremented_at)
634         return false;
635       if (bsi_stmt (bsi) == stmt)
636         return true;
637     }
638 }
639
640 /* Returns true if STMT if after the place where the induction variable
641    CAND is incremented in LOOP.  */
642
643 static bool
644 stmt_after_increment (struct loop *loop, struct iv_cand *cand, tree stmt)
645 {
646   switch (cand->pos)
647     {
648     case IP_END:
649       return false;
650
651     case IP_NORMAL:
652       return stmt_after_ip_normal_pos (loop, stmt);
653
654     case IP_ORIGINAL:
655       return stmt_after_ip_original_pos (cand, stmt);
656
657     default:
658       gcc_unreachable ();
659     }
660 }
661
662 /* Element of the table in that we cache the numbers of iterations obtained
663    from exits of the loop.  */
664
665 struct nfe_cache_elt
666 {
667   /* The edge for that the number of iterations is cached.  */
668   edge exit;
669
670   /* True if the # of iterations was successfully determined.  */
671   bool valid_p;
672
673   /* Description of # of iterations.  */
674   struct tree_niter_desc niter;
675 };
676
677 /* Hash function for nfe_cache_elt E.  */
678
679 static hashval_t
680 nfe_hash (const void *e)
681 {
682   const struct nfe_cache_elt *elt = e;
683
684   return htab_hash_pointer (elt->exit);
685 }
686
687 /* Equality function for nfe_cache_elt E1 and edge E2.  */
688
689 static int
690 nfe_eq (const void *e1, const void *e2)
691 {
692   const struct nfe_cache_elt *elt1 = e1;
693
694   return elt1->exit == e2;
695 }
696
697 /*  Returns structure describing number of iterations determined from
698     EXIT of DATA->current_loop, or NULL if something goes wrong.  */
699
700 static struct tree_niter_desc *
701 niter_for_exit (struct ivopts_data *data, edge exit)
702 {
703   struct nfe_cache_elt *nfe_desc;
704   PTR *slot;
705
706   slot = htab_find_slot_with_hash (data->niters, exit,
707                                    htab_hash_pointer (exit),
708                                    INSERT);
709
710   if (!*slot)
711     {
712       nfe_desc = xmalloc (sizeof (struct nfe_cache_elt));
713       nfe_desc->exit = exit;
714       nfe_desc->valid_p = number_of_iterations_exit (data->current_loop,
715                                                      exit, &nfe_desc->niter,
716                                                      true);
717       *slot = nfe_desc;
718     }
719   else
720     nfe_desc = *slot;
721
722   if (!nfe_desc->valid_p)
723     return NULL;
724
725   return &nfe_desc->niter;
726 }
727
728 /* Returns structure describing number of iterations determined from
729    single dominating exit of DATA->current_loop, or NULL if something
730    goes wrong.  */
731
732 static struct tree_niter_desc *
733 niter_for_single_dom_exit (struct ivopts_data *data)
734 {
735   edge exit = single_dom_exit (data->current_loop);
736
737   if (!exit)
738     return NULL;
739
740   return niter_for_exit (data, exit);
741 }
742
743 /* Initializes data structures used by the iv optimization pass, stored
744    in DATA.  LOOPS is the loop tree.  */
745
746 static void
747 tree_ssa_iv_optimize_init (struct loops *loops, struct ivopts_data *data)
748 {
749   unsigned i;
750
751   data->version_info_size = 2 * num_ssa_names;
752   data->version_info = xcalloc (data->version_info_size,
753                                 sizeof (struct version_info));
754   data->relevant = BITMAP_ALLOC (NULL);
755   data->important_candidates = BITMAP_ALLOC (NULL);
756   data->max_inv_id = 0;
757   data->niters = htab_create (10, nfe_hash, nfe_eq, free);
758
759   for (i = 1; i < loops->num; i++)
760     if (loops->parray[i])
761       loops->parray[i]->aux = xcalloc (1, sizeof (struct loop_data));
762
763   data->iv_uses = VEC_alloc (iv_use_p, heap, 20);
764   data->iv_candidates = VEC_alloc (iv_cand_p, heap, 20);
765   decl_rtl_to_reset = VEC_alloc (tree, heap, 20);
766 }
767
768 /* Returns a memory object to that EXPR points.  In case we are able to
769    determine that it does not point to any such object, NULL is returned.  */
770
771 static tree
772 determine_base_object (tree expr)
773 {
774   enum tree_code code = TREE_CODE (expr);
775   tree base, obj, op0, op1;
776
777   if (!POINTER_TYPE_P (TREE_TYPE (expr)))
778     return NULL_TREE;
779
780   switch (code)
781     {
782     case INTEGER_CST:
783       return NULL_TREE;
784
785     case ADDR_EXPR:
786       obj = TREE_OPERAND (expr, 0);
787       base = get_base_address (obj);
788
789       if (!base)
790         return expr;
791
792       if (TREE_CODE (base) == INDIRECT_REF)
793         return determine_base_object (TREE_OPERAND (base, 0));
794
795       return fold_convert (ptr_type_node,
796                            build_fold_addr_expr (base));
797
798     case PLUS_EXPR:
799     case MINUS_EXPR:
800       op0 = determine_base_object (TREE_OPERAND (expr, 0));
801       op1 = determine_base_object (TREE_OPERAND (expr, 1));
802       
803       if (!op1)
804         return op0;
805
806       if (!op0)
807         return (code == PLUS_EXPR
808                 ? op1
809                 : fold_build1 (NEGATE_EXPR, ptr_type_node, op1));
810
811       return fold_build2 (code, ptr_type_node, op0, op1);
812
813     case NOP_EXPR:
814     case CONVERT_EXPR:
815       return determine_base_object (TREE_OPERAND (expr, 0));
816
817     default:
818       return fold_convert (ptr_type_node, expr);
819     }
820 }
821
822 /* Allocates an induction variable with given initial value BASE and step STEP
823    for loop LOOP.  */
824
825 static struct iv *
826 alloc_iv (tree base, tree step)
827 {
828   struct iv *iv = xcalloc (1, sizeof (struct iv));
829
830   if (step && integer_zerop (step))
831     step = NULL_TREE;
832
833   iv->base = base;
834   iv->base_object = determine_base_object (base);
835   iv->step = step;
836   iv->biv_p = false;
837   iv->have_use_for = false;
838   iv->use_id = 0;
839   iv->ssa_name = NULL_TREE;
840
841   return iv;
842 }
843
844 /* Sets STEP and BASE for induction variable IV.  */
845
846 static void
847 set_iv (struct ivopts_data *data, tree iv, tree base, tree step)
848 {
849   struct version_info *info = name_info (data, iv);
850
851   gcc_assert (!info->iv);
852
853   bitmap_set_bit (data->relevant, SSA_NAME_VERSION (iv));
854   info->iv = alloc_iv (base, step);
855   info->iv->ssa_name = iv;
856 }
857
858 /* Finds induction variable declaration for VAR.  */
859
860 static struct iv *
861 get_iv (struct ivopts_data *data, tree var)
862 {
863   basic_block bb;
864   
865   if (!name_info (data, var)->iv)
866     {
867       bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
868
869       if (!bb
870           || !flow_bb_inside_loop_p (data->current_loop, bb))
871         set_iv (data, var, var, NULL_TREE);
872     }
873
874   return name_info (data, var)->iv;
875 }
876
877 /* Determines the step of a biv defined in PHI.  Returns NULL if PHI does
878    not define a simple affine biv with nonzero step.  */
879
880 static tree
881 determine_biv_step (tree phi)
882 {
883   struct loop *loop = bb_for_stmt (phi)->loop_father;
884   tree name = PHI_RESULT (phi), base, step;
885
886   if (!is_gimple_reg (name))
887     return NULL_TREE;
888
889   if (!simple_iv (loop, phi, name, &base, &step, true))
890     return NULL_TREE;
891
892   if (zero_p (step))
893     return NULL_TREE;
894
895   return step;
896 }
897
898 /* Returns true if EXP is a ssa name that occurs in an abnormal phi node.  */
899
900 static bool
901 abnormal_ssa_name_p (tree exp)
902 {
903   if (!exp)
904     return false;
905
906   if (TREE_CODE (exp) != SSA_NAME)
907     return false;
908
909   return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) != 0;
910 }
911
912 /* Returns false if BASE or INDEX contains a ssa name that occurs in an
913    abnormal phi node.  Callback for for_each_index.  */
914
915 static bool
916 idx_contains_abnormal_ssa_name_p (tree base, tree *index,
917                                   void *data ATTRIBUTE_UNUSED)
918 {
919   if (TREE_CODE (base) == ARRAY_REF)
920     {
921       if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
922         return false;
923       if (abnormal_ssa_name_p (TREE_OPERAND (base, 3)))
924         return false;
925     }
926
927   return !abnormal_ssa_name_p (*index);
928 }
929
930 /* Returns true if EXPR contains a ssa name that occurs in an
931    abnormal phi node.  */
932
933 static bool
934 contains_abnormal_ssa_name_p (tree expr)
935 {
936   enum tree_code code;
937   enum tree_code_class class;
938
939   if (!expr)
940     return false;
941
942   code = TREE_CODE (expr);
943   class = TREE_CODE_CLASS (code);
944
945   if (code == SSA_NAME)
946     return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
947
948   if (code == INTEGER_CST
949       || is_gimple_min_invariant (expr))
950     return false;
951
952   if (code == ADDR_EXPR)
953     return !for_each_index (&TREE_OPERAND (expr, 0),
954                             idx_contains_abnormal_ssa_name_p,
955                             NULL);
956
957   switch (class)
958     {
959     case tcc_binary:
960     case tcc_comparison:
961       if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1)))
962         return true;
963
964       /* Fallthru.  */
965     case tcc_unary:
966       if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0)))
967         return true;
968
969       break;
970
971     default:
972       gcc_unreachable ();
973     }
974
975   return false;
976 }
977
978 /* Finds basic ivs.  */
979
980 static bool
981 find_bivs (struct ivopts_data *data)
982 {
983   tree phi, step, type, base;
984   bool found = false;
985   struct loop *loop = data->current_loop;
986
987   for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
988     {
989       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
990         continue;
991
992       step = determine_biv_step (phi);
993       if (!step)
994         continue;
995
996       base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
997       base = expand_simple_operations (base);
998       if (contains_abnormal_ssa_name_p (base)
999           || contains_abnormal_ssa_name_p (step))
1000         continue;
1001
1002       type = TREE_TYPE (PHI_RESULT (phi));
1003       base = fold_convert (type, base);
1004       if (step)
1005         step = fold_convert (type, step);
1006
1007       set_iv (data, PHI_RESULT (phi), base, step);
1008       found = true;
1009     }
1010
1011   return found;
1012 }
1013
1014 /* Marks basic ivs.  */
1015
1016 static void
1017 mark_bivs (struct ivopts_data *data)
1018 {
1019   tree phi, var;
1020   struct iv *iv, *incr_iv;
1021   struct loop *loop = data->current_loop;
1022   basic_block incr_bb;
1023
1024   for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
1025     {
1026       iv = get_iv (data, PHI_RESULT (phi));
1027       if (!iv)
1028         continue;
1029
1030       var = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1031       incr_iv = get_iv (data, var);
1032       if (!incr_iv)
1033         continue;
1034
1035       /* If the increment is in the subloop, ignore it.  */
1036       incr_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
1037       if (incr_bb->loop_father != data->current_loop
1038           || (incr_bb->flags & BB_IRREDUCIBLE_LOOP))
1039         continue;
1040
1041       iv->biv_p = true;
1042       incr_iv->biv_p = true;
1043     }
1044 }
1045
1046 /* Checks whether STMT defines a linear induction variable and stores its
1047    parameters to BASE and STEP.  */
1048
1049 static bool
1050 find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt,
1051                         tree *base, tree *step)
1052 {
1053   tree lhs;
1054   struct loop *loop = data->current_loop;
1055
1056   *base = NULL_TREE;
1057   *step = NULL_TREE;
1058
1059   if (TREE_CODE (stmt) != MODIFY_EXPR)
1060     return false;
1061
1062   lhs = TREE_OPERAND (stmt, 0);
1063   if (TREE_CODE (lhs) != SSA_NAME)
1064     return false;
1065
1066   if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), base, step, true))
1067     return false;
1068   *base = expand_simple_operations (*base);
1069
1070   if (contains_abnormal_ssa_name_p (*base)
1071       || contains_abnormal_ssa_name_p (*step))
1072     return false;
1073
1074   return true;
1075 }
1076
1077 /* Finds general ivs in statement STMT.  */
1078
1079 static void
1080 find_givs_in_stmt (struct ivopts_data *data, tree stmt)
1081 {
1082   tree base, step;
1083
1084   if (!find_givs_in_stmt_scev (data, stmt, &base, &step))
1085     return;
1086
1087   set_iv (data, TREE_OPERAND (stmt, 0), base, step);
1088 }
1089
1090 /* Finds general ivs in basic block BB.  */
1091
1092 static void
1093 find_givs_in_bb (struct ivopts_data *data, basic_block bb)
1094 {
1095   block_stmt_iterator bsi;
1096
1097   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1098     find_givs_in_stmt (data, bsi_stmt (bsi));
1099 }
1100
1101 /* Finds general ivs.  */
1102
1103 static void
1104 find_givs (struct ivopts_data *data)
1105 {
1106   struct loop *loop = data->current_loop;
1107   basic_block *body = get_loop_body_in_dom_order (loop);
1108   unsigned i;
1109
1110   for (i = 0; i < loop->num_nodes; i++)
1111     find_givs_in_bb (data, body[i]);
1112   free (body);
1113 }
1114
1115 /* For each ssa name defined in LOOP determines whether it is an induction
1116    variable and if so, its initial value and step.  */
1117
1118 static bool
1119 find_induction_variables (struct ivopts_data *data)
1120 {
1121   unsigned i;
1122   bitmap_iterator bi;
1123
1124   if (!find_bivs (data))
1125     return false;
1126
1127   find_givs (data);
1128   mark_bivs (data);
1129
1130   if (dump_file && (dump_flags & TDF_DETAILS))
1131     {
1132       struct tree_niter_desc *niter;
1133
1134       niter = niter_for_single_dom_exit (data);
1135
1136       if (niter)
1137         {
1138           fprintf (dump_file, "  number of iterations ");
1139           print_generic_expr (dump_file, niter->niter, TDF_SLIM);
1140           fprintf (dump_file, "\n");
1141
1142           fprintf (dump_file, "  may be zero if ");
1143           print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
1144           fprintf (dump_file, "\n");
1145           fprintf (dump_file, "\n");
1146         };
1147  
1148       fprintf (dump_file, "Induction variables:\n\n");
1149
1150       EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
1151         {
1152           if (ver_info (data, i)->iv)
1153             dump_iv (dump_file, ver_info (data, i)->iv);
1154         }
1155     }
1156
1157   return true;
1158 }
1159
1160 /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV.  */
1161
1162 static struct iv_use *
1163 record_use (struct ivopts_data *data, tree *use_p, struct iv *iv,
1164             tree stmt, enum use_type use_type)
1165 {
1166   struct iv_use *use = xcalloc (1, sizeof (struct iv_use));
1167
1168   use->id = n_iv_uses (data);
1169   use->type = use_type;
1170   use->iv = iv;
1171   use->stmt = stmt;
1172   use->op_p = use_p;
1173   use->related_cands = BITMAP_ALLOC (NULL);
1174
1175   /* To avoid showing ssa name in the dumps, if it was not reset by the
1176      caller.  */
1177   iv->ssa_name = NULL_TREE;
1178
1179   if (dump_file && (dump_flags & TDF_DETAILS))
1180     dump_use (dump_file, use);
1181
1182   VEC_safe_push (iv_use_p, heap, data->iv_uses, use);
1183
1184   return use;
1185 }
1186
1187 /* Checks whether OP is a loop-level invariant and if so, records it.
1188    NONLINEAR_USE is true if the invariant is used in a way we do not
1189    handle specially.  */
1190
1191 static void
1192 record_invariant (struct ivopts_data *data, tree op, bool nonlinear_use)
1193 {
1194   basic_block bb;
1195   struct version_info *info;
1196
1197   if (TREE_CODE (op) != SSA_NAME
1198       || !is_gimple_reg (op))
1199     return;
1200
1201   bb = bb_for_stmt (SSA_NAME_DEF_STMT (op));
1202   if (bb
1203       && flow_bb_inside_loop_p (data->current_loop, bb))
1204     return;
1205
1206   info = name_info (data, op);
1207   info->name = op;
1208   info->has_nonlin_use |= nonlinear_use;
1209   if (!info->inv_id)
1210     info->inv_id = ++data->max_inv_id;
1211   bitmap_set_bit (data->relevant, SSA_NAME_VERSION (op));
1212 }
1213
1214 /* Checks whether the use OP is interesting and if so, records it
1215    as TYPE.  */
1216
1217 static struct iv_use *
1218 find_interesting_uses_outer_or_nonlin (struct ivopts_data *data, tree op,
1219                                        enum use_type type)
1220 {
1221   struct iv *iv;
1222   struct iv *civ;
1223   tree stmt;
1224   struct iv_use *use;
1225
1226   if (TREE_CODE (op) != SSA_NAME)
1227     return NULL;
1228
1229   iv = get_iv (data, op);
1230   if (!iv)
1231     return NULL;
1232   
1233   if (iv->have_use_for)
1234     {
1235       use = iv_use (data, iv->use_id);
1236
1237       gcc_assert (use->type == USE_NONLINEAR_EXPR
1238                   || use->type == USE_OUTER);
1239
1240       if (type == USE_NONLINEAR_EXPR)
1241         use->type = USE_NONLINEAR_EXPR;
1242       return use;
1243     }
1244
1245   if (zero_p (iv->step))
1246     {
1247       record_invariant (data, op, true);
1248       return NULL;
1249     }
1250   iv->have_use_for = true;
1251
1252   civ = xmalloc (sizeof (struct iv));
1253   *civ = *iv;
1254
1255   stmt = SSA_NAME_DEF_STMT (op);
1256   gcc_assert (TREE_CODE (stmt) == PHI_NODE
1257               || TREE_CODE (stmt) == MODIFY_EXPR);
1258
1259   use = record_use (data, NULL, civ, stmt, type);
1260   iv->use_id = use->id;
1261
1262   return use;
1263 }
1264
1265 /* Checks whether the use OP is interesting and if so, records it.  */
1266
1267 static struct iv_use *
1268 find_interesting_uses_op (struct ivopts_data *data, tree op)
1269 {
1270   return find_interesting_uses_outer_or_nonlin (data, op, USE_NONLINEAR_EXPR);
1271 }
1272
1273 /* Records a definition of induction variable OP that is used outside of the
1274    loop.  */
1275
1276 static struct iv_use *
1277 find_interesting_uses_outer (struct ivopts_data *data, tree op)
1278 {
1279   return find_interesting_uses_outer_or_nonlin (data, op, USE_OUTER);
1280 }
1281
1282 /* Checks whether the condition *COND_P in STMT is interesting
1283    and if so, records it.  */
1284
1285 static void
1286 find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
1287 {
1288   tree *op0_p;
1289   tree *op1_p;
1290   struct iv *iv0 = NULL, *iv1 = NULL, *civ;
1291   struct iv const_iv;
1292   tree zero = integer_zero_node;
1293
1294   const_iv.step = NULL_TREE;
1295
1296   if (TREE_CODE (*cond_p) != SSA_NAME
1297       && !COMPARISON_CLASS_P (*cond_p))
1298     return;
1299
1300   if (TREE_CODE (*cond_p) == SSA_NAME)
1301     {
1302       op0_p = cond_p;
1303       op1_p = &zero;
1304     }
1305   else
1306     {
1307       op0_p = &TREE_OPERAND (*cond_p, 0);
1308       op1_p = &TREE_OPERAND (*cond_p, 1);
1309     }
1310
1311   if (TREE_CODE (*op0_p) == SSA_NAME)
1312     iv0 = get_iv (data, *op0_p);
1313   else
1314     iv0 = &const_iv;
1315
1316   if (TREE_CODE (*op1_p) == SSA_NAME)
1317     iv1 = get_iv (data, *op1_p);
1318   else
1319     iv1 = &const_iv;
1320
1321   if (/* When comparing with non-invariant value, we may not do any senseful
1322          induction variable elimination.  */
1323       (!iv0 || !iv1)
1324       /* Eliminating condition based on two ivs would be nontrivial.
1325          ??? TODO -- it is not really important to handle this case.  */
1326       || (!zero_p (iv0->step) && !zero_p (iv1->step)))
1327     {
1328       find_interesting_uses_op (data, *op0_p);
1329       find_interesting_uses_op (data, *op1_p);
1330       return;
1331     }
1332
1333   if (zero_p (iv0->step) && zero_p (iv1->step))
1334     {
1335       /* If both are invariants, this is a work for unswitching.  */
1336       return;
1337     }
1338
1339   civ = xmalloc (sizeof (struct iv));
1340   *civ = zero_p (iv0->step) ? *iv1: *iv0;
1341   record_use (data, cond_p, civ, stmt, USE_COMPARE);
1342 }
1343
1344 /* Returns true if expression EXPR is obviously invariant in LOOP,
1345    i.e. if all its operands are defined outside of the LOOP.  */
1346
1347 bool
1348 expr_invariant_in_loop_p (struct loop *loop, tree expr)
1349 {
1350   basic_block def_bb;
1351   unsigned i, len;
1352
1353   if (is_gimple_min_invariant (expr))
1354     return true;
1355
1356   if (TREE_CODE (expr) == SSA_NAME)
1357     {
1358       def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (expr));
1359       if (def_bb
1360           && flow_bb_inside_loop_p (loop, def_bb))
1361         return false;
1362
1363       return true;
1364     }
1365
1366   if (!EXPR_P (expr))
1367     return false;
1368
1369   len = TREE_CODE_LENGTH (TREE_CODE (expr));
1370   for (i = 0; i < len; i++)
1371     if (!expr_invariant_in_loop_p (loop, TREE_OPERAND (expr, i)))
1372       return false;
1373
1374   return true;
1375 }
1376
1377 /* Cumulates the steps of indices into DATA and replaces their values with the
1378    initial ones.  Returns false when the value of the index cannot be determined.
1379    Callback for for_each_index.  */
1380
1381 struct ifs_ivopts_data
1382 {
1383   struct ivopts_data *ivopts_data;
1384   tree stmt;
1385   tree *step_p;
1386 };
1387
1388 static bool
1389 idx_find_step (tree base, tree *idx, void *data)
1390 {
1391   struct ifs_ivopts_data *dta = data;
1392   struct iv *iv;
1393   tree step, iv_step, lbound, off;
1394   struct loop *loop = dta->ivopts_data->current_loop;
1395
1396   if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF
1397       || TREE_CODE (base) == ALIGN_INDIRECT_REF)
1398     return false;
1399
1400   /* If base is a component ref, require that the offset of the reference
1401      be invariant.  */
1402   if (TREE_CODE (base) == COMPONENT_REF)
1403     {
1404       off = component_ref_field_offset (base);
1405       return expr_invariant_in_loop_p (loop, off);
1406     }
1407
1408   /* If base is array, first check whether we will be able to move the
1409      reference out of the loop (in order to take its address in strength
1410      reduction).  In order for this to work we need both lower bound
1411      and step to be loop invariants.  */
1412   if (TREE_CODE (base) == ARRAY_REF)
1413     {
1414       step = array_ref_element_size (base);
1415       lbound = array_ref_low_bound (base);
1416
1417       if (!expr_invariant_in_loop_p (loop, step)
1418           || !expr_invariant_in_loop_p (loop, lbound))
1419         return false;
1420     }
1421
1422   if (TREE_CODE (*idx) != SSA_NAME)
1423     return true;
1424
1425   iv = get_iv (dta->ivopts_data, *idx);
1426   if (!iv)
1427     return false;
1428
1429   *idx = iv->base;
1430
1431   if (!iv->step)
1432     return true;
1433
1434   if (TREE_CODE (base) == ARRAY_REF)
1435     {
1436       step = array_ref_element_size (base);
1437
1438       /* We only handle addresses whose step is an integer constant.  */
1439       if (TREE_CODE (step) != INTEGER_CST)
1440         return false;
1441     }
1442   else
1443     /* The step for pointer arithmetics already is 1 byte.  */
1444     step = build_int_cst (sizetype, 1);
1445
1446   /* FIXME: convert_step should not be used outside chrec_convert: fix
1447      this by calling chrec_convert.  */
1448   iv_step = convert_step (dta->ivopts_data->current_loop,
1449                           sizetype, iv->base, iv->step, dta->stmt);
1450
1451   if (!iv_step)
1452     {
1453       /* The index might wrap.  */
1454       return false;
1455     }
1456
1457   step = fold_build2 (MULT_EXPR, sizetype, step, iv_step);
1458
1459   if (!*dta->step_p)
1460     *dta->step_p = step;
1461   else
1462     *dta->step_p = fold_build2 (PLUS_EXPR, sizetype, *dta->step_p, step);
1463
1464   return true;
1465 }
1466
1467 /* Records use in index IDX.  Callback for for_each_index.  Ivopts data
1468    object is passed to it in DATA.  */
1469
1470 static bool
1471 idx_record_use (tree base, tree *idx,
1472                 void *data)
1473 {
1474   find_interesting_uses_op (data, *idx);
1475   if (TREE_CODE (base) == ARRAY_REF)
1476     {
1477       find_interesting_uses_op (data, array_ref_element_size (base));
1478       find_interesting_uses_op (data, array_ref_low_bound (base));
1479     }
1480   return true;
1481 }
1482
1483 /* Returns true if memory reference REF may be unaligned.  */
1484
1485 static bool
1486 may_be_unaligned_p (tree ref)
1487 {
1488   tree base;
1489   tree base_type;
1490   HOST_WIDE_INT bitsize;
1491   HOST_WIDE_INT bitpos;
1492   tree toffset;
1493   enum machine_mode mode;
1494   int unsignedp, volatilep;
1495   unsigned base_align;
1496
1497   /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
1498      thus they are not misaligned.  */
1499   if (TREE_CODE (ref) == TARGET_MEM_REF)
1500     return false;
1501
1502   /* The test below is basically copy of what expr.c:normal_inner_ref
1503      does to check whether the object must be loaded by parts when
1504      STRICT_ALIGNMENT is true.  */
1505   base = get_inner_reference (ref, &bitsize, &bitpos, &toffset, &mode,
1506                               &unsignedp, &volatilep, true);
1507   base_type = TREE_TYPE (base);
1508   base_align = TYPE_ALIGN (base_type);
1509
1510   if (mode != BLKmode
1511       && (base_align < GET_MODE_ALIGNMENT (mode)
1512           || bitpos % GET_MODE_ALIGNMENT (mode) != 0
1513           || bitpos % BITS_PER_UNIT != 0))
1514     return true;
1515
1516   return false;
1517 }
1518
1519 /* Finds addresses in *OP_P inside STMT.  */
1520
1521 static void
1522 find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
1523 {
1524   tree base = *op_p, step = NULL;
1525   struct iv *civ;
1526   struct ifs_ivopts_data ifs_ivopts_data;
1527
1528   /* Do not play with volatile memory references.  A bit too conservative,
1529      perhaps, but safe.  */
1530   if (stmt_ann (stmt)->has_volatile_ops)
1531     goto fail;
1532
1533   /* Ignore bitfields for now.  Not really something terribly complicated
1534      to handle.  TODO.  */
1535   if (TREE_CODE (base) == COMPONENT_REF
1536       && DECL_NONADDRESSABLE_P (TREE_OPERAND (base, 1)))
1537     goto fail;
1538
1539   if (STRICT_ALIGNMENT
1540       && may_be_unaligned_p (base))
1541     goto fail;
1542
1543   base = unshare_expr (base);
1544
1545   if (TREE_CODE (base) == TARGET_MEM_REF)
1546     {
1547       tree type = build_pointer_type (TREE_TYPE (base));
1548       tree astep;
1549
1550       if (TMR_BASE (base)
1551           && TREE_CODE (TMR_BASE (base)) == SSA_NAME)
1552         {
1553           civ = get_iv (data, TMR_BASE (base));
1554           if (!civ)
1555             goto fail;
1556
1557           TMR_BASE (base) = civ->base;
1558           step = civ->step;
1559         }
1560       if (TMR_INDEX (base)
1561           && TREE_CODE (TMR_INDEX (base)) == SSA_NAME)
1562         {
1563           civ = get_iv (data, TMR_INDEX (base));
1564           if (!civ)
1565             goto fail;
1566
1567           TMR_INDEX (base) = civ->base;
1568           astep = civ->step;
1569
1570           if (astep)
1571             {
1572               if (TMR_STEP (base))
1573                 astep = fold_build2 (MULT_EXPR, type, TMR_STEP (base), astep);
1574
1575               if (step)
1576                 step = fold_build2 (PLUS_EXPR, type, step, astep);
1577               else
1578                 step = astep;
1579             }
1580         }
1581
1582       if (zero_p (step))
1583         goto fail;
1584       base = tree_mem_ref_addr (type, base);
1585     }
1586   else
1587     {
1588       ifs_ivopts_data.ivopts_data = data;
1589       ifs_ivopts_data.stmt = stmt;
1590       ifs_ivopts_data.step_p = &step;
1591       if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
1592           || zero_p (step))
1593         goto fail;
1594
1595       gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
1596       gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
1597
1598       base = build_fold_addr_expr (base);
1599     }
1600
1601   civ = alloc_iv (base, step);
1602   record_use (data, op_p, civ, stmt, USE_ADDRESS);
1603   return;
1604
1605 fail:
1606   for_each_index (op_p, idx_record_use, data);
1607 }
1608
1609 /* Finds and records invariants used in STMT.  */
1610
1611 static void
1612 find_invariants_stmt (struct ivopts_data *data, tree stmt)
1613 {
1614   ssa_op_iter iter;
1615   use_operand_p use_p;
1616   tree op;
1617
1618   FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1619     {
1620       op = USE_FROM_PTR (use_p);
1621       record_invariant (data, op, false);
1622     }
1623 }
1624
1625 /* Finds interesting uses of induction variables in the statement STMT.  */
1626
1627 static void
1628 find_interesting_uses_stmt (struct ivopts_data *data, tree stmt)
1629 {
1630   struct iv *iv;
1631   tree op, lhs, rhs;
1632   ssa_op_iter iter;
1633   use_operand_p use_p;
1634
1635   find_invariants_stmt (data, stmt);
1636
1637   if (TREE_CODE (stmt) == COND_EXPR)
1638     {
1639       find_interesting_uses_cond (data, stmt, &COND_EXPR_COND (stmt));
1640       return;
1641     }
1642
1643   if (TREE_CODE (stmt) == MODIFY_EXPR)
1644     {
1645       lhs = TREE_OPERAND (stmt, 0);
1646       rhs = TREE_OPERAND (stmt, 1);
1647
1648       if (TREE_CODE (lhs) == SSA_NAME)
1649         {
1650           /* If the statement defines an induction variable, the uses are not
1651              interesting by themselves.  */
1652
1653           iv = get_iv (data, lhs);
1654
1655           if (iv && !zero_p (iv->step))
1656             return;
1657         }
1658
1659       switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
1660         {
1661         case tcc_comparison:
1662           find_interesting_uses_cond (data, stmt, &TREE_OPERAND (stmt, 1));
1663           return;
1664
1665         case tcc_reference:
1666           find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 1));
1667           if (REFERENCE_CLASS_P (lhs))
1668             find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
1669           return;
1670
1671         default: ;
1672         }
1673
1674       if (REFERENCE_CLASS_P (lhs)
1675           && is_gimple_val (rhs))
1676         {
1677           find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
1678           find_interesting_uses_op (data, rhs);
1679           return;
1680         }
1681
1682       /* TODO -- we should also handle address uses of type
1683
1684          memory = call (whatever);
1685
1686          and
1687
1688          call (memory).  */
1689     }
1690
1691   if (TREE_CODE (stmt) == PHI_NODE
1692       && bb_for_stmt (stmt) == data->current_loop->header)
1693     {
1694       lhs = PHI_RESULT (stmt);
1695       iv = get_iv (data, lhs);
1696
1697       if (iv && !zero_p (iv->step))
1698         return;
1699     }
1700
1701   FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1702     {
1703       op = USE_FROM_PTR (use_p);
1704
1705       if (TREE_CODE (op) != SSA_NAME)
1706         continue;
1707
1708       iv = get_iv (data, op);
1709       if (!iv)
1710         continue;
1711
1712       find_interesting_uses_op (data, op);
1713     }
1714 }
1715
1716 /* Finds interesting uses of induction variables outside of loops
1717    on loop exit edge EXIT.  */
1718
1719 static void
1720 find_interesting_uses_outside (struct ivopts_data *data, edge exit)
1721 {
1722   tree phi, def;
1723
1724   for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
1725     {
1726       def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1727       find_interesting_uses_outer (data, def);
1728     }
1729 }
1730
1731 /* Finds uses of the induction variables that are interesting.  */
1732
1733 static void
1734 find_interesting_uses (struct ivopts_data *data)
1735 {
1736   basic_block bb;
1737   block_stmt_iterator bsi;
1738   tree phi;
1739   basic_block *body = get_loop_body (data->current_loop);
1740   unsigned i;
1741   struct version_info *info;
1742   edge e;
1743
1744   if (dump_file && (dump_flags & TDF_DETAILS))
1745     fprintf (dump_file, "Uses:\n\n");
1746
1747   for (i = 0; i < data->current_loop->num_nodes; i++)
1748     {
1749       edge_iterator ei;
1750       bb = body[i];
1751
1752       FOR_EACH_EDGE (e, ei, bb->succs)
1753         if (e->dest != EXIT_BLOCK_PTR
1754             && !flow_bb_inside_loop_p (data->current_loop, e->dest))
1755           find_interesting_uses_outside (data, e);
1756
1757       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1758         find_interesting_uses_stmt (data, phi);
1759       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1760         find_interesting_uses_stmt (data, bsi_stmt (bsi));
1761     }
1762
1763   if (dump_file && (dump_flags & TDF_DETAILS))
1764     {
1765       bitmap_iterator bi;
1766
1767       fprintf (dump_file, "\n");
1768
1769       EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
1770         {
1771           info = ver_info (data, i);
1772           if (info->inv_id)
1773             {
1774               fprintf (dump_file, "  ");
1775               print_generic_expr (dump_file, info->name, TDF_SLIM);
1776               fprintf (dump_file, " is invariant (%d)%s\n",
1777                        info->inv_id, info->has_nonlin_use ? "" : ", eliminable");
1778             }
1779         }
1780
1781       fprintf (dump_file, "\n");
1782     }
1783
1784   free (body);
1785 }
1786
1787 /* Strips constant offsets from EXPR and stores them to OFFSET.  If INSIDE_ADDR
1788    is true, assume we are inside an address.  If TOP_COMPREF is true, assume
1789    we are at the top-level of the processed address.  */
1790
1791 static tree
1792 strip_offset_1 (tree expr, bool inside_addr, bool top_compref,
1793                 unsigned HOST_WIDE_INT *offset)
1794 {
1795   tree op0 = NULL_TREE, op1 = NULL_TREE, tmp, step;
1796   enum tree_code code;
1797   tree type, orig_type = TREE_TYPE (expr);
1798   unsigned HOST_WIDE_INT off0, off1, st;
1799   tree orig_expr = expr;
1800
1801   STRIP_NOPS (expr);
1802
1803   type = TREE_TYPE (expr);
1804   code = TREE_CODE (expr);
1805   *offset = 0;
1806
1807   switch (code)
1808     {
1809     case INTEGER_CST:
1810       if (!cst_and_fits_in_hwi (expr)
1811           || zero_p (expr))
1812         return orig_expr;
1813
1814       *offset = int_cst_value (expr);
1815       return build_int_cst_type (orig_type, 0);
1816
1817     case PLUS_EXPR:
1818     case MINUS_EXPR:
1819       op0 = TREE_OPERAND (expr, 0);
1820       op1 = TREE_OPERAND (expr, 1);
1821
1822       op0 = strip_offset_1 (op0, false, false, &off0);
1823       op1 = strip_offset_1 (op1, false, false, &off1);
1824
1825       *offset = (code == PLUS_EXPR ? off0 + off1 : off0 - off1);
1826       if (op0 == TREE_OPERAND (expr, 0)
1827           && op1 == TREE_OPERAND (expr, 1))
1828         return orig_expr;
1829
1830       if (zero_p (op1))
1831         expr = op0;
1832       else if (zero_p (op0))
1833         {
1834           if (code == PLUS_EXPR)
1835             expr = op1;
1836           else
1837             expr = fold_build1 (NEGATE_EXPR, type, op1);
1838         }
1839       else
1840         expr = fold_build2 (code, type, op0, op1);
1841
1842       return fold_convert (orig_type, expr);
1843
1844     case ARRAY_REF:
1845       if (!inside_addr)
1846         return orig_expr;
1847
1848       step = array_ref_element_size (expr);
1849       if (!cst_and_fits_in_hwi (step))
1850         break;
1851
1852       st = int_cst_value (step);
1853       op1 = TREE_OPERAND (expr, 1);
1854       op1 = strip_offset_1 (op1, false, false, &off1);
1855       *offset = off1 * st;
1856
1857       if (top_compref
1858           && zero_p (op1))
1859         {
1860           /* Strip the component reference completely.  */
1861           op0 = TREE_OPERAND (expr, 0);
1862           op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
1863           *offset += off0;
1864           return op0;
1865         }
1866       break;
1867
1868     case COMPONENT_REF:
1869       if (!inside_addr)
1870         return orig_expr;
1871
1872       tmp = component_ref_field_offset (expr);
1873       if (top_compref
1874           && cst_and_fits_in_hwi (tmp))
1875         {
1876           /* Strip the component reference completely.  */
1877           op0 = TREE_OPERAND (expr, 0);
1878           op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
1879           *offset = off0 + int_cst_value (tmp);
1880           return op0;
1881         }
1882       break;
1883
1884     case ADDR_EXPR:
1885       op0 = TREE_OPERAND (expr, 0);
1886       op0 = strip_offset_1 (op0, true, true, &off0);
1887       *offset += off0;
1888
1889       if (op0 == TREE_OPERAND (expr, 0))
1890         return orig_expr;
1891
1892       expr = build_fold_addr_expr (op0);
1893       return fold_convert (orig_type, expr);
1894
1895     case INDIRECT_REF:
1896       inside_addr = false;
1897       break;
1898
1899     default:
1900       return orig_expr;
1901     }
1902
1903   /* Default handling of expressions for that we want to recurse into
1904      the first operand.  */
1905   op0 = TREE_OPERAND (expr, 0);
1906   op0 = strip_offset_1 (op0, inside_addr, false, &off0);
1907   *offset += off0;
1908
1909   if (op0 == TREE_OPERAND (expr, 0)
1910       && (!op1 || op1 == TREE_OPERAND (expr, 1)))
1911     return orig_expr;
1912
1913   expr = copy_node (expr);
1914   TREE_OPERAND (expr, 0) = op0;
1915   if (op1)
1916     TREE_OPERAND (expr, 1) = op1;
1917
1918   /* Inside address, we might strip the top level component references,
1919      thus changing type of the expression.  Handling of ADDR_EXPR
1920      will fix that.  */
1921   expr = fold_convert (orig_type, expr);
1922
1923   return expr;
1924 }
1925
1926 /* Strips constant offsets from EXPR and stores them to OFFSET.  */
1927
1928 static tree
1929 strip_offset (tree expr, unsigned HOST_WIDE_INT *offset)
1930 {
1931   return strip_offset_1 (expr, false, false, offset);
1932 }
1933
1934 /* Returns variant of TYPE that can be used as base for different uses.
1935    For integer types, we return unsigned variant of the type, which
1936    avoids problems with overflows.  For pointer types, we return void *.  */
1937
1938 static tree
1939 generic_type_for (tree type)
1940 {
1941   if (POINTER_TYPE_P (type))
1942     return ptr_type_node;
1943
1944   if (TYPE_UNSIGNED (type))
1945     return type;
1946
1947   return unsigned_type_for (type);
1948 }
1949
1950 /* Records invariants in *EXPR_P.  Callback for walk_tree.  DATA contains
1951    the bitmap to that we should store it.  */
1952
1953 static struct ivopts_data *fd_ivopts_data;
1954 static tree
1955 find_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
1956 {
1957   bitmap *depends_on = data;
1958   struct version_info *info;
1959
1960   if (TREE_CODE (*expr_p) != SSA_NAME)
1961     return NULL_TREE;
1962   info = name_info (fd_ivopts_data, *expr_p);
1963
1964   if (!info->inv_id || info->has_nonlin_use)
1965     return NULL_TREE;
1966
1967   if (!*depends_on)
1968     *depends_on = BITMAP_ALLOC (NULL);
1969   bitmap_set_bit (*depends_on, info->inv_id);
1970
1971   return NULL_TREE;
1972 }
1973
1974 /* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
1975    position to POS.  If USE is not NULL, the candidate is set as related to
1976    it.  If both BASE and STEP are NULL, we add a pseudocandidate for the
1977    replacement of the final value of the iv by a direct computation.  */
1978
1979 static struct iv_cand *
1980 add_candidate_1 (struct ivopts_data *data,
1981                  tree base, tree step, bool important, enum iv_position pos,
1982                  struct iv_use *use, tree incremented_at)
1983 {
1984   unsigned i;
1985   struct iv_cand *cand = NULL;
1986   tree type, orig_type;
1987   
1988   if (base)
1989     {
1990       orig_type = TREE_TYPE (base);
1991       type = generic_type_for (orig_type);
1992       if (type != orig_type)
1993         {
1994           base = fold_convert (type, base);
1995           if (step)
1996             step = fold_convert (type, step);
1997         }
1998     }
1999
2000   for (i = 0; i < n_iv_cands (data); i++)
2001     {
2002       cand = iv_cand (data, i);
2003
2004       if (cand->pos != pos)
2005         continue;
2006
2007       if (cand->incremented_at != incremented_at)
2008         continue;
2009
2010       if (!cand->iv)
2011         {
2012           if (!base && !step)
2013             break;
2014
2015           continue;
2016         }
2017
2018       if (!base && !step)
2019         continue;
2020
2021       if (!operand_equal_p (base, cand->iv->base, 0))
2022         continue;
2023
2024       if (zero_p (cand->iv->step))
2025         {
2026           if (zero_p (step))
2027             break;
2028         }
2029       else
2030         {
2031           if (step && operand_equal_p (step, cand->iv->step, 0))
2032             break;
2033         }
2034     }
2035
2036   if (i == n_iv_cands (data))
2037     {
2038       cand = xcalloc (1, sizeof (struct iv_cand));
2039       cand->id = i;
2040
2041       if (!base && !step)
2042         cand->iv = NULL;
2043       else
2044         cand->iv = alloc_iv (base, step);
2045
2046       cand->pos = pos;
2047       if (pos != IP_ORIGINAL && cand->iv)
2048         {
2049           cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp");
2050           cand->var_after = cand->var_before;
2051         }
2052       cand->important = important;
2053       cand->incremented_at = incremented_at;
2054       VEC_safe_push (iv_cand_p, heap, data->iv_candidates, cand);
2055
2056       if (step
2057           && TREE_CODE (step) != INTEGER_CST)
2058         {
2059           fd_ivopts_data = data;
2060           walk_tree (&step, find_depends, &cand->depends_on, NULL);
2061         }
2062
2063       if (dump_file && (dump_flags & TDF_DETAILS))
2064         dump_cand (dump_file, cand);
2065     }
2066
2067   if (important && !cand->important)
2068     {
2069       cand->important = true;
2070       if (dump_file && (dump_flags & TDF_DETAILS))
2071         fprintf (dump_file, "Candidate %d is important\n", cand->id);
2072     }
2073
2074   if (use)
2075     {
2076       bitmap_set_bit (use->related_cands, i);
2077       if (dump_file && (dump_flags & TDF_DETAILS))
2078         fprintf (dump_file, "Candidate %d is related to use %d\n",
2079                  cand->id, use->id);
2080     }
2081
2082   return cand;
2083 }
2084
2085 /* Returns true if incrementing the induction variable at the end of the LOOP
2086    is allowed.
2087
2088    The purpose is to avoid splitting latch edge with a biv increment, thus
2089    creating a jump, possibly confusing other optimization passes and leaving
2090    less freedom to scheduler.  So we allow IP_END_POS only if IP_NORMAL_POS
2091    is not available (so we do not have a better alternative), or if the latch
2092    edge is already nonempty.  */
2093
2094 static bool
2095 allow_ip_end_pos_p (struct loop *loop)
2096 {
2097   if (!ip_normal_pos (loop))
2098     return true;
2099
2100   if (!empty_block_p (ip_end_pos (loop)))
2101     return true;
2102
2103   return false;
2104 }
2105
2106 /* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
2107    position to POS.  If USE is not NULL, the candidate is set as related to
2108    it.  The candidate computation is scheduled on all available positions.  */
2109
2110 static void
2111 add_candidate (struct ivopts_data *data, 
2112                tree base, tree step, bool important, struct iv_use *use)
2113 {
2114   if (ip_normal_pos (data->current_loop))
2115     add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL_TREE);
2116   if (ip_end_pos (data->current_loop)
2117       && allow_ip_end_pos_p (data->current_loop))
2118     add_candidate_1 (data, base, step, important, IP_END, use, NULL_TREE);
2119 }
2120
2121 /* Add a standard "0 + 1 * iteration" iv candidate for a
2122    type with SIZE bits.  */
2123
2124 static void
2125 add_standard_iv_candidates_for_size (struct ivopts_data *data,
2126                                      unsigned int size)
2127 {
2128   tree type = lang_hooks.types.type_for_size (size, true);
2129   add_candidate (data, build_int_cst (type, 0), build_int_cst (type, 1),
2130                  true, NULL);
2131 }
2132
2133 /* Adds standard iv candidates.  */
2134
2135 static void
2136 add_standard_iv_candidates (struct ivopts_data *data)
2137 {
2138   add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE);
2139
2140   /* The same for a double-integer type if it is still fast enough.  */
2141   if (BITS_PER_WORD >= INT_TYPE_SIZE * 2)
2142     add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE * 2);
2143 }
2144
2145
2146 /* Adds candidates bases on the old induction variable IV.  */
2147
2148 static void
2149 add_old_iv_candidates (struct ivopts_data *data, struct iv *iv)
2150 {
2151   tree phi, def;
2152   struct iv_cand *cand;
2153
2154   add_candidate (data, iv->base, iv->step, true, NULL);
2155
2156   /* The same, but with initial value zero.  */
2157   add_candidate (data,
2158                  build_int_cst (TREE_TYPE (iv->base), 0),
2159                  iv->step, true, NULL);
2160
2161   phi = SSA_NAME_DEF_STMT (iv->ssa_name);
2162   if (TREE_CODE (phi) == PHI_NODE)
2163     {
2164       /* Additionally record the possibility of leaving the original iv
2165          untouched.  */
2166       def = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (data->current_loop));
2167       cand = add_candidate_1 (data,
2168                               iv->base, iv->step, true, IP_ORIGINAL, NULL,
2169                               SSA_NAME_DEF_STMT (def));
2170       cand->var_before = iv->ssa_name;
2171       cand->var_after = def;
2172     }
2173 }
2174
2175 /* Adds candidates based on the old induction variables.  */
2176
2177 static void
2178 add_old_ivs_candidates (struct ivopts_data *data)
2179 {
2180   unsigned i;
2181   struct iv *iv;
2182   bitmap_iterator bi;
2183
2184   EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
2185     {
2186       iv = ver_info (data, i)->iv;
2187       if (iv && iv->biv_p && !zero_p (iv->step))
2188         add_old_iv_candidates (data, iv);
2189     }
2190 }
2191
2192 /* Adds candidates based on the value of the induction variable IV and USE.  */
2193
2194 static void
2195 add_iv_value_candidates (struct ivopts_data *data,
2196                          struct iv *iv, struct iv_use *use)
2197 {
2198   unsigned HOST_WIDE_INT offset;
2199   tree base;
2200
2201   add_candidate (data, iv->base, iv->step, false, use);
2202
2203   /* The same, but with initial value zero.  Make such variable important,
2204      since it is generic enough so that possibly many uses may be based
2205      on it.  */
2206   add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
2207                  iv->step, true, use);
2208
2209   /* Third, try removing the constant offset.  */
2210   base = strip_offset (iv->base, &offset);
2211   if (offset)
2212     add_candidate (data, base, iv->step, false, use);
2213 }
2214
2215 /* Possibly adds pseudocandidate for replacing the final value of USE by
2216    a direct computation.  */
2217
2218 static void
2219 add_iv_outer_candidates (struct ivopts_data *data, struct iv_use *use)
2220 {
2221   struct tree_niter_desc *niter;
2222
2223   /* We must know where we exit the loop and how many times does it roll.  */
2224   niter = niter_for_single_dom_exit (data);
2225   if (!niter
2226       || !zero_p (niter->may_be_zero))
2227     return;
2228
2229   add_candidate_1 (data, NULL, NULL, false, IP_NORMAL, use, NULL_TREE);
2230 }
2231
2232 /* Adds candidates based on the uses.  */
2233
2234 static void
2235 add_derived_ivs_candidates (struct ivopts_data *data)
2236 {
2237   unsigned i;
2238
2239   for (i = 0; i < n_iv_uses (data); i++)
2240     {
2241       struct iv_use *use = iv_use (data, i);
2242
2243       if (!use)
2244         continue;
2245
2246       switch (use->type)
2247         {
2248         case USE_NONLINEAR_EXPR:
2249         case USE_COMPARE:
2250         case USE_ADDRESS:
2251           /* Just add the ivs based on the value of the iv used here.  */
2252           add_iv_value_candidates (data, use->iv, use);
2253           break;
2254
2255         case USE_OUTER:
2256           add_iv_value_candidates (data, use->iv, use);
2257
2258           /* Additionally, add the pseudocandidate for the possibility to
2259              replace the final value by a direct computation.  */
2260           add_iv_outer_candidates (data, use);
2261           break;
2262
2263         default:
2264           gcc_unreachable ();
2265         }
2266     }
2267 }
2268
2269 /* Record important candidates and add them to related_cands bitmaps
2270    if needed.  */
2271
2272 static void
2273 record_important_candidates (struct ivopts_data *data)
2274 {
2275   unsigned i;
2276   struct iv_use *use;
2277
2278   for (i = 0; i < n_iv_cands (data); i++)
2279     {
2280       struct iv_cand *cand = iv_cand (data, i);
2281
2282       if (cand->important)
2283         bitmap_set_bit (data->important_candidates, i);
2284     }
2285
2286   data->consider_all_candidates = (n_iv_cands (data)
2287                                    <= CONSIDER_ALL_CANDIDATES_BOUND);
2288
2289   if (data->consider_all_candidates)
2290     {
2291       /* We will not need "related_cands" bitmaps in this case,
2292          so release them to decrease peak memory consumption.  */
2293       for (i = 0; i < n_iv_uses (data); i++)
2294         {
2295           use = iv_use (data, i);
2296           BITMAP_FREE (use->related_cands);
2297         }
2298     }
2299   else
2300     {
2301       /* Add important candidates to the related_cands bitmaps.  */
2302       for (i = 0; i < n_iv_uses (data); i++)
2303         bitmap_ior_into (iv_use (data, i)->related_cands,
2304                          data->important_candidates);
2305     }
2306 }
2307
2308 /* Finds the candidates for the induction variables.  */
2309
2310 static void
2311 find_iv_candidates (struct ivopts_data *data)
2312 {
2313   /* Add commonly used ivs.  */
2314   add_standard_iv_candidates (data);
2315
2316   /* Add old induction variables.  */
2317   add_old_ivs_candidates (data);
2318
2319   /* Add induction variables derived from uses.  */
2320   add_derived_ivs_candidates (data);
2321
2322   /* Record the important candidates.  */
2323   record_important_candidates (data);
2324 }
2325
2326 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
2327    If consider_all_candidates is true, we use a two-dimensional array, otherwise
2328    we allocate a simple list to every use.  */
2329
2330 static void
2331 alloc_use_cost_map (struct ivopts_data *data)
2332 {
2333   unsigned i, size, s, j;
2334
2335   for (i = 0; i < n_iv_uses (data); i++)
2336     {
2337       struct iv_use *use = iv_use (data, i);
2338       bitmap_iterator bi;
2339
2340       if (data->consider_all_candidates)
2341         size = n_iv_cands (data);
2342       else
2343         {
2344           s = 0;
2345           EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi)
2346             {
2347               s++;
2348             }
2349
2350           /* Round up to the power of two, so that moduling by it is fast.  */
2351           for (size = 1; size < s; size <<= 1)
2352             continue;
2353         }
2354
2355       use->n_map_members = size;
2356       use->cost_map = xcalloc (size, sizeof (struct cost_pair));
2357     }
2358 }
2359
2360 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
2361    on invariants DEPENDS_ON and that the value used in expressing it
2362    is VALUE.*/
2363
2364 static void
2365 set_use_iv_cost (struct ivopts_data *data,
2366                  struct iv_use *use, struct iv_cand *cand, unsigned cost,
2367                  bitmap depends_on, tree value)
2368 {
2369   unsigned i, s;
2370
2371   if (cost == INFTY)
2372     {
2373       BITMAP_FREE (depends_on);
2374       return;
2375     }
2376
2377   if (data->consider_all_candidates)
2378     {
2379       use->cost_map[cand->id].cand = cand;
2380       use->cost_map[cand->id].cost = cost;
2381       use->cost_map[cand->id].depends_on = depends_on;
2382       use->cost_map[cand->id].value = value;
2383       return;
2384     }
2385
2386   /* n_map_members is a power of two, so this computes modulo.  */
2387   s = cand->id & (use->n_map_members - 1);
2388   for (i = s; i < use->n_map_members; i++)
2389     if (!use->cost_map[i].cand)
2390       goto found;
2391   for (i = 0; i < s; i++)
2392     if (!use->cost_map[i].cand)
2393       goto found;
2394
2395   gcc_unreachable ();
2396
2397 found:
2398   use->cost_map[i].cand = cand;
2399   use->cost_map[i].cost = cost;
2400   use->cost_map[i].depends_on = depends_on;
2401   use->cost_map[i].value = value;
2402 }
2403
2404 /* Gets cost of (USE, CANDIDATE) pair.  */
2405
2406 static struct cost_pair *
2407 get_use_iv_cost (struct ivopts_data *data, struct iv_use *use,
2408                  struct iv_cand *cand)
2409 {
2410   unsigned i, s;
2411   struct cost_pair *ret;
2412
2413   if (!cand)
2414     return NULL;
2415
2416   if (data->consider_all_candidates)
2417     {
2418       ret = use->cost_map + cand->id;
2419       if (!ret->cand)
2420         return NULL;
2421
2422       return ret;
2423     }
2424       
2425   /* n_map_members is a power of two, so this computes modulo.  */
2426   s = cand->id & (use->n_map_members - 1);
2427   for (i = s; i < use->n_map_members; i++)
2428     if (use->cost_map[i].cand == cand)
2429       return use->cost_map + i;
2430
2431   for (i = 0; i < s; i++)
2432     if (use->cost_map[i].cand == cand)
2433       return use->cost_map + i;
2434
2435   return NULL;
2436 }
2437
2438 /* Returns estimate on cost of computing SEQ.  */
2439
2440 static unsigned
2441 seq_cost (rtx seq)
2442 {
2443   unsigned cost = 0;
2444   rtx set;
2445
2446   for (; seq; seq = NEXT_INSN (seq))
2447     {
2448       set = single_set (seq);
2449       if (set)
2450         cost += rtx_cost (set, SET);
2451       else
2452         cost++;
2453     }
2454
2455   return cost;
2456 }
2457
2458 /* Produce DECL_RTL for object obj so it looks like it is stored in memory.  */
2459 static rtx
2460 produce_memory_decl_rtl (tree obj, int *regno)
2461 {
2462   rtx x;
2463   
2464   gcc_assert (obj);
2465   if (TREE_STATIC (obj) || DECL_EXTERNAL (obj))
2466     {
2467       const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj));
2468       x = gen_rtx_SYMBOL_REF (Pmode, name);
2469     }
2470   else
2471     x = gen_raw_REG (Pmode, (*regno)++);
2472
2473   return gen_rtx_MEM (DECL_MODE (obj), x);
2474 }
2475
2476 /* Prepares decl_rtl for variables referred in *EXPR_P.  Callback for
2477    walk_tree.  DATA contains the actual fake register number.  */
2478
2479 static tree
2480 prepare_decl_rtl (tree *expr_p, int *ws, void *data)
2481 {
2482   tree obj = NULL_TREE;
2483   rtx x = NULL_RTX;
2484   int *regno = data;
2485
2486   switch (TREE_CODE (*expr_p))
2487     {
2488     case ADDR_EXPR:
2489       for (expr_p = &TREE_OPERAND (*expr_p, 0);
2490            handled_component_p (*expr_p);
2491            expr_p = &TREE_OPERAND (*expr_p, 0))
2492         continue;
2493       obj = *expr_p;
2494       if (DECL_P (obj))
2495         x = produce_memory_decl_rtl (obj, regno);
2496       break;
2497
2498     case SSA_NAME:
2499       *ws = 0;
2500       obj = SSA_NAME_VAR (*expr_p);
2501       if (!DECL_RTL_SET_P (obj))
2502         x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
2503       break;
2504
2505     case VAR_DECL:
2506     case PARM_DECL:
2507     case RESULT_DECL:
2508       *ws = 0;
2509       obj = *expr_p;
2510
2511       if (DECL_RTL_SET_P (obj))
2512         break;
2513
2514       if (DECL_MODE (obj) == BLKmode)
2515         x = produce_memory_decl_rtl (obj, regno);
2516       else
2517         x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
2518
2519       break;
2520
2521     default:
2522       break;
2523     }
2524
2525   if (x)
2526     {
2527       VEC_safe_push (tree, heap, decl_rtl_to_reset, obj);
2528       SET_DECL_RTL (obj, x);
2529     }
2530
2531   return NULL_TREE;
2532 }
2533
2534 /* Determines cost of the computation of EXPR.  */
2535
2536 static unsigned
2537 computation_cost (tree expr)
2538 {
2539   rtx seq, rslt;
2540   tree type = TREE_TYPE (expr);
2541   unsigned cost;
2542   /* Avoid using hard regs in ways which may be unsupported.  */
2543   int regno = LAST_VIRTUAL_REGISTER + 1;
2544
2545   walk_tree (&expr, prepare_decl_rtl, &regno, NULL);
2546   start_sequence ();
2547   rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL);
2548   seq = get_insns ();
2549   end_sequence ();
2550
2551   cost = seq_cost (seq);
2552   if (MEM_P (rslt))
2553     cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type));
2554
2555   return cost;
2556 }
2557
2558 /* Returns variable containing the value of candidate CAND at statement AT.  */
2559
2560 static tree
2561 var_at_stmt (struct loop *loop, struct iv_cand *cand, tree stmt)
2562 {
2563   if (stmt_after_increment (loop, cand, stmt))
2564     return cand->var_after;
2565   else
2566     return cand->var_before;
2567 }
2568
2569 /* Return the most significant (sign) bit of T.  Similar to tree_int_cst_msb,
2570    but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE.  */
2571
2572 int
2573 tree_int_cst_sign_bit (tree t)
2574 {
2575   unsigned bitno = TYPE_PRECISION (TREE_TYPE (t)) - 1;
2576   unsigned HOST_WIDE_INT w;
2577
2578   if (bitno < HOST_BITS_PER_WIDE_INT)
2579     w = TREE_INT_CST_LOW (t);
2580   else
2581     {
2582       w = TREE_INT_CST_HIGH (t);
2583       bitno -= HOST_BITS_PER_WIDE_INT;
2584     }
2585
2586   return (w >> bitno) & 1;
2587 }
2588
2589 /* If we can prove that TOP = cst * BOT for some constant cst in TYPE,
2590    return cst.  Otherwise return NULL_TREE.  */
2591
2592 static tree
2593 constant_multiple_of (tree type, tree top, tree bot)
2594 {
2595   tree res, mby, p0, p1;
2596   enum tree_code code;
2597   bool negate;
2598
2599   STRIP_NOPS (top);
2600   STRIP_NOPS (bot);
2601
2602   if (operand_equal_p (top, bot, 0))
2603     return build_int_cst (type, 1);
2604
2605   code = TREE_CODE (top);
2606   switch (code)
2607     {
2608     case MULT_EXPR:
2609       mby = TREE_OPERAND (top, 1);
2610       if (TREE_CODE (mby) != INTEGER_CST)
2611         return NULL_TREE;
2612
2613       res = constant_multiple_of (type, TREE_OPERAND (top, 0), bot);
2614       if (!res)
2615         return NULL_TREE;
2616
2617       return fold_binary_to_constant (MULT_EXPR, type, res,
2618                                       fold_convert (type, mby));
2619
2620     case PLUS_EXPR:
2621     case MINUS_EXPR:
2622       p0 = constant_multiple_of (type, TREE_OPERAND (top, 0), bot);
2623       if (!p0)
2624         return NULL_TREE;
2625       p1 = constant_multiple_of (type, TREE_OPERAND (top, 1), bot);
2626       if (!p1)
2627         return NULL_TREE;
2628
2629       return fold_binary_to_constant (code, type, p0, p1);
2630
2631     case INTEGER_CST:
2632       if (TREE_CODE (bot) != INTEGER_CST)
2633         return NULL_TREE;
2634
2635       bot = fold_convert (type, bot);
2636       top = fold_convert (type, top);
2637
2638       /* If BOT seems to be negative, try dividing by -BOT instead, and negate
2639          the result afterwards.  */
2640       if (tree_int_cst_sign_bit (bot))
2641         {
2642           negate = true;
2643           bot = fold_unary_to_constant (NEGATE_EXPR, type, bot);
2644         }
2645       else
2646         negate = false;
2647
2648       /* Ditto for TOP.  */
2649       if (tree_int_cst_sign_bit (top))
2650         {
2651           negate = !negate;
2652           top = fold_unary_to_constant (NEGATE_EXPR, type, top);
2653         }
2654
2655       if (!zero_p (fold_binary_to_constant (TRUNC_MOD_EXPR, type, top, bot)))
2656         return NULL_TREE;
2657
2658       res = fold_binary_to_constant (EXACT_DIV_EXPR, type, top, bot);
2659       if (negate)
2660         res = fold_unary_to_constant (NEGATE_EXPR, type, res);
2661       return res;
2662
2663     default:
2664       return NULL_TREE;
2665     }
2666 }
2667
2668 /* Sets COMB to CST.  */
2669
2670 static void
2671 aff_combination_const (struct affine_tree_combination *comb, tree type,
2672                        unsigned HOST_WIDE_INT cst)
2673 {
2674   unsigned prec = TYPE_PRECISION (type);
2675
2676   comb->type = type;
2677   comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
2678
2679   comb->n = 0;
2680   comb->rest = NULL_TREE;
2681   comb->offset = cst & comb->mask;
2682 }
2683
2684 /* Sets COMB to single element ELT.  */
2685
2686 static void
2687 aff_combination_elt (struct affine_tree_combination *comb, tree type, tree elt)
2688 {
2689   unsigned prec = TYPE_PRECISION (type);
2690
2691   comb->type = type;
2692   comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
2693
2694   comb->n = 1;
2695   comb->elts[0] = elt;
2696   comb->coefs[0] = 1;
2697   comb->rest = NULL_TREE;
2698   comb->offset = 0;
2699 }
2700
2701 /* Scales COMB by SCALE.  */
2702
2703 static void
2704 aff_combination_scale (struct affine_tree_combination *comb,
2705                        unsigned HOST_WIDE_INT scale)
2706 {
2707   unsigned i, j;
2708
2709   if (scale == 1)
2710     return;
2711
2712   if (scale == 0)
2713     {
2714       aff_combination_const (comb, comb->type, 0);
2715       return;
2716     }
2717
2718   comb->offset = (scale * comb->offset) & comb->mask;
2719   for (i = 0, j = 0; i < comb->n; i++)
2720     {
2721       comb->coefs[j] = (scale * comb->coefs[i]) & comb->mask;
2722       comb->elts[j] = comb->elts[i];
2723       if (comb->coefs[j] != 0)
2724         j++;
2725     }
2726   comb->n = j;
2727
2728   if (comb->rest)
2729     {
2730       if (comb->n < MAX_AFF_ELTS)
2731         {
2732           comb->coefs[comb->n] = scale;
2733           comb->elts[comb->n] = comb->rest;
2734           comb->rest = NULL_TREE;
2735           comb->n++;
2736         }
2737       else
2738         comb->rest = fold_build2 (MULT_EXPR, comb->type, comb->rest,
2739                                   build_int_cst_type (comb->type, scale));
2740     }
2741 }
2742
2743 /* Adds ELT * SCALE to COMB.  */
2744
2745 static void
2746 aff_combination_add_elt (struct affine_tree_combination *comb, tree elt,
2747                          unsigned HOST_WIDE_INT scale)
2748 {
2749   unsigned i;
2750
2751   if (scale == 0)
2752     return;
2753
2754   for (i = 0; i < comb->n; i++)
2755     if (operand_equal_p (comb->elts[i], elt, 0))
2756       {
2757         comb->coefs[i] = (comb->coefs[i] + scale) & comb->mask;
2758         if (comb->coefs[i])
2759           return;
2760
2761         comb->n--;
2762         comb->coefs[i] = comb->coefs[comb->n];
2763         comb->elts[i] = comb->elts[comb->n];
2764         return;
2765       }
2766   if (comb->n < MAX_AFF_ELTS)
2767     {
2768       comb->coefs[comb->n] = scale;
2769       comb->elts[comb->n] = elt;
2770       comb->n++;
2771       return;
2772     }
2773
2774   if (scale == 1)
2775     elt = fold_convert (comb->type, elt);
2776   else
2777     elt = fold_build2 (MULT_EXPR, comb->type,
2778                        fold_convert (comb->type, elt),
2779                        build_int_cst_type (comb->type, scale)); 
2780
2781   if (comb->rest)
2782     comb->rest = fold_build2 (PLUS_EXPR, comb->type, comb->rest, elt);
2783   else
2784     comb->rest = elt;
2785 }
2786
2787 /* Adds COMB2 to COMB1.  */
2788
2789 static void
2790 aff_combination_add (struct affine_tree_combination *comb1,
2791                      struct affine_tree_combination *comb2)
2792 {
2793   unsigned i;
2794
2795   comb1->offset = (comb1->offset + comb2->offset) & comb1->mask;
2796   for (i = 0; i < comb2-> n; i++)
2797     aff_combination_add_elt (comb1, comb2->elts[i], comb2->coefs[i]);
2798   if (comb2->rest)
2799     aff_combination_add_elt (comb1, comb2->rest, 1);
2800 }
2801
2802 /* Splits EXPR into an affine combination of parts.  */
2803
2804 static void
2805 tree_to_aff_combination (tree expr, tree type,
2806                          struct affine_tree_combination *comb)
2807 {
2808   struct affine_tree_combination tmp;
2809   enum tree_code code;
2810   tree cst, core, toffset;
2811   HOST_WIDE_INT bitpos, bitsize;
2812   enum machine_mode mode;
2813   int unsignedp, volatilep;
2814
2815   STRIP_NOPS (expr);
2816
2817   code = TREE_CODE (expr);
2818   switch (code)
2819     {
2820     case INTEGER_CST:
2821       aff_combination_const (comb, type, int_cst_value (expr));
2822       return;
2823
2824     case PLUS_EXPR:
2825     case MINUS_EXPR:
2826       tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
2827       tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp);
2828       if (code == MINUS_EXPR)
2829         aff_combination_scale (&tmp, -1);
2830       aff_combination_add (comb, &tmp);
2831       return;
2832
2833     case MULT_EXPR:
2834       cst = TREE_OPERAND (expr, 1);
2835       if (TREE_CODE (cst) != INTEGER_CST)
2836         break;
2837       tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
2838       aff_combination_scale (comb, int_cst_value (cst));
2839       return;
2840
2841     case NEGATE_EXPR:
2842       tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
2843       aff_combination_scale (comb, -1);
2844       return;
2845
2846     case ADDR_EXPR:
2847       core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
2848                                   &toffset, &mode, &unsignedp, &volatilep,
2849                                   false);
2850       if (bitpos % BITS_PER_UNIT != 0)
2851         break;
2852       aff_combination_const (comb, type, bitpos / BITS_PER_UNIT);
2853       core = build_fold_addr_expr (core);
2854       if (TREE_CODE (core) == ADDR_EXPR)
2855         aff_combination_add_elt (comb, core, 1);
2856       else
2857         {
2858           tree_to_aff_combination (core, type, &tmp);
2859           aff_combination_add (comb, &tmp);
2860         }
2861       if (toffset)
2862         {
2863           tree_to_aff_combination (toffset, type, &tmp);
2864           aff_combination_add (comb, &tmp);
2865         }
2866       return;
2867
2868     default:
2869       break;
2870     }
2871
2872   aff_combination_elt (comb, type, expr);
2873 }
2874
2875 /* Creates EXPR + ELT * SCALE in TYPE.  MASK is the mask for width of TYPE.  */
2876
2877 static tree
2878 add_elt_to_tree (tree expr, tree type, tree elt, unsigned HOST_WIDE_INT scale,
2879                  unsigned HOST_WIDE_INT mask)
2880 {
2881   enum tree_code code;
2882
2883   scale &= mask;
2884   elt = fold_convert (type, elt);
2885
2886   if (scale == 1)
2887     {
2888       if (!expr)
2889         return elt;
2890
2891       return fold_build2 (PLUS_EXPR, type, expr, elt);
2892     }
2893
2894   if (scale == mask)
2895     {
2896       if (!expr)
2897         return fold_build1 (NEGATE_EXPR, type, elt);
2898
2899       return fold_build2 (MINUS_EXPR, type, expr, elt);
2900     }
2901
2902   if (!expr)
2903     return fold_build2 (MULT_EXPR, type, elt,
2904                         build_int_cst_type (type, scale));
2905
2906   if ((scale | (mask >> 1)) == mask)
2907     {
2908       /* Scale is negative.  */
2909       code = MINUS_EXPR;
2910       scale = (-scale) & mask;
2911     }
2912   else
2913     code = PLUS_EXPR;
2914
2915   elt = fold_build2 (MULT_EXPR, type, elt,
2916                      build_int_cst_type (type, scale));
2917   return fold_build2 (code, type, expr, elt);
2918 }
2919
2920 /* Copies the tree elements of COMB to ensure that they are not shared.  */
2921
2922 static void
2923 unshare_aff_combination (struct affine_tree_combination *comb)
2924 {
2925   unsigned i;
2926
2927   for (i = 0; i < comb->n; i++)
2928     comb->elts[i] = unshare_expr (comb->elts[i]);
2929   if (comb->rest)
2930     comb->rest = unshare_expr (comb->rest);
2931 }
2932
2933 /* Makes tree from the affine combination COMB.  */
2934
2935 static tree
2936 aff_combination_to_tree (struct affine_tree_combination *comb)
2937 {
2938   tree type = comb->type;
2939   tree expr = comb->rest;
2940   unsigned i;
2941   unsigned HOST_WIDE_INT off, sgn;
2942
2943   /* Handle the special case produced by get_computation_aff when
2944      the type does not fit in HOST_WIDE_INT.  */
2945   if (comb->n == 0 && comb->offset == 0)
2946     return fold_convert (type, expr);
2947
2948   gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
2949
2950   for (i = 0; i < comb->n; i++)
2951     expr = add_elt_to_tree (expr, type, comb->elts[i], comb->coefs[i],
2952                             comb->mask);
2953
2954   if ((comb->offset | (comb->mask >> 1)) == comb->mask)
2955     {
2956       /* Offset is negative.  */
2957       off = (-comb->offset) & comb->mask;
2958       sgn = comb->mask;
2959     }
2960   else
2961     {
2962       off = comb->offset;
2963       sgn = 1;
2964     }
2965   return add_elt_to_tree (expr, type, build_int_cst_type (type, off), sgn,
2966                           comb->mask);
2967 }
2968
2969 /* Determines the expression by that USE is expressed from induction variable
2970    CAND at statement AT in LOOP.  The expression is stored in a decomposed
2971    form into AFF.  Returns false if USE cannot be expressed using CAND.  */
2972
2973 static bool
2974 get_computation_aff (struct loop *loop,
2975                      struct iv_use *use, struct iv_cand *cand, tree at,
2976                      struct affine_tree_combination *aff)
2977 {
2978   tree ubase = use->iv->base;
2979   tree ustep = use->iv->step;
2980   tree cbase = cand->iv->base;
2981   tree cstep = cand->iv->step;
2982   tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
2983   tree uutype;
2984   tree expr, delta;
2985   tree ratio;
2986   unsigned HOST_WIDE_INT ustepi, cstepi;
2987   HOST_WIDE_INT ratioi;
2988   struct affine_tree_combination cbase_aff, expr_aff;
2989   tree cstep_orig = cstep, ustep_orig = ustep;
2990
2991   if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
2992     {
2993       /* We do not have a precision to express the values of use.  */
2994       return false;
2995     }
2996
2997   expr = var_at_stmt (loop, cand, at);
2998
2999   if (TREE_TYPE (expr) != ctype)
3000     {
3001       /* This may happen with the original ivs.  */
3002       expr = fold_convert (ctype, expr);
3003     }
3004
3005   if (TYPE_UNSIGNED (utype))
3006     uutype = utype;
3007   else
3008     {
3009       uutype = unsigned_type_for (utype);
3010       ubase = fold_convert (uutype, ubase);
3011       ustep = fold_convert (uutype, ustep);
3012     }
3013
3014   if (uutype != ctype)
3015     {
3016       expr = fold_convert (uutype, expr);
3017       cbase = fold_convert (uutype, cbase);
3018       cstep = fold_convert (uutype, cstep);
3019
3020       /* If the conversion is not noop, we must take it into account when
3021          considering the value of the step.  */
3022       if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
3023         cstep_orig = cstep;
3024     }
3025
3026   if (cst_and_fits_in_hwi (cstep_orig)
3027       && cst_and_fits_in_hwi (ustep_orig))
3028     {
3029       ustepi = int_cst_value (ustep_orig);
3030       cstepi = int_cst_value (cstep_orig);
3031
3032       if (!divide (TYPE_PRECISION (uutype), ustepi, cstepi, &ratioi))
3033         {
3034           /* TODO maybe consider case when ustep divides cstep and the ratio is
3035              a power of 2 (so that the division is fast to execute)?  We would
3036              need to be much more careful with overflows etc. then.  */
3037           return false;
3038         }
3039
3040       ratio = build_int_cst_type (uutype, ratioi);
3041     }
3042   else
3043     {
3044       ratio = constant_multiple_of (uutype, ustep_orig, cstep_orig);
3045       if (!ratio)
3046         return false;
3047
3048       /* Ratioi is only used to detect special cases when the multiplicative
3049          factor is 1 or -1, so if we cannot convert ratio to HOST_WIDE_INT,
3050          we may set it to 0.  We prefer cst_and_fits_in_hwi/int_cst_value
3051          to integer_onep/integer_all_onesp, since the former ignores
3052          TREE_OVERFLOW.  */
3053       if (cst_and_fits_in_hwi (ratio))
3054         ratioi = int_cst_value (ratio);
3055       else if (integer_onep (ratio))
3056         ratioi = 1;
3057       else if (integer_all_onesp (ratio))
3058         ratioi = -1;
3059       else
3060         ratioi = 0;
3061     }
3062
3063   /* We may need to shift the value if we are after the increment.  */
3064   if (stmt_after_increment (loop, cand, at))
3065     cbase = fold_build2 (PLUS_EXPR, uutype, cbase, cstep);
3066
3067   /* use = ubase - ratio * cbase + ratio * var.
3068
3069      In general case ubase + ratio * (var - cbase) could be better (one less
3070      multiplication), but often it is possible to eliminate redundant parts
3071      of computations from (ubase - ratio * cbase) term, and if it does not
3072      happen, fold is able to apply the distributive law to obtain this form
3073      anyway.  */
3074
3075   if (TYPE_PRECISION (uutype) > HOST_BITS_PER_WIDE_INT)
3076     {
3077       /* Let's compute in trees and just return the result in AFF.  This case
3078          should not be very common, and fold itself is not that bad either,
3079          so making the aff. functions more complicated to handle this case
3080          is not that urgent.  */
3081       if (ratioi == 1)
3082         {
3083           delta = fold_build2 (MINUS_EXPR, uutype, ubase, cbase);
3084           expr = fold_build2 (PLUS_EXPR, uutype, expr, delta);
3085         }
3086       else if (ratioi == -1)
3087         {
3088           delta = fold_build2 (PLUS_EXPR, uutype, ubase, cbase);
3089           expr = fold_build2 (MINUS_EXPR, uutype, delta, expr);
3090         }
3091       else
3092         {
3093           delta = fold_build2 (MULT_EXPR, uutype, cbase, ratio);
3094           delta = fold_build2 (MINUS_EXPR, uutype, ubase, delta);
3095           expr = fold_build2 (MULT_EXPR, uutype, ratio, expr);
3096           expr = fold_build2 (PLUS_EXPR, uutype, delta, expr);
3097         }
3098
3099       aff->type = uutype;
3100       aff->n = 0;
3101       aff->offset = 0;
3102       aff->mask = 0;
3103       aff->rest = expr;
3104       return true;
3105     }
3106
3107   /* If we got here, the types fits in HOST_WIDE_INT, thus it must be
3108      possible to compute ratioi.  */
3109   gcc_assert (ratioi);
3110
3111   tree_to_aff_combination (ubase, uutype, aff);
3112   tree_to_aff_combination (cbase, uutype, &cbase_aff);
3113   tree_to_aff_combination (expr, uutype, &expr_aff);
3114   aff_combination_scale (&cbase_aff, -ratioi);
3115   aff_combination_scale (&expr_aff, ratioi);
3116   aff_combination_add (aff, &cbase_aff);
3117   aff_combination_add (aff, &expr_aff);
3118
3119   return true;
3120 }
3121
3122 /* Determines the expression by that USE is expressed from induction variable
3123    CAND at statement AT in LOOP.  The computation is unshared.  */
3124
3125 static tree
3126 get_computation_at (struct loop *loop,
3127                     struct iv_use *use, struct iv_cand *cand, tree at)
3128 {
3129   struct affine_tree_combination aff;
3130   tree type = TREE_TYPE (use->iv->base);
3131
3132   if (!get_computation_aff (loop, use, cand, at, &aff))
3133     return NULL_TREE;
3134   unshare_aff_combination (&aff);
3135   return fold_convert (type, aff_combination_to_tree (&aff));
3136 }
3137
3138 /* Determines the expression by that USE is expressed from induction variable
3139    CAND in LOOP.  The computation is unshared.  */
3140
3141 static tree
3142 get_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand)
3143 {
3144   return get_computation_at (loop, use, cand, use->stmt);
3145 }
3146
3147 /* Returns cost of addition in MODE.  */
3148
3149 static unsigned
3150 add_cost (enum machine_mode mode)
3151 {
3152   static unsigned costs[NUM_MACHINE_MODES];
3153   rtx seq;
3154   unsigned cost;
3155
3156   if (costs[mode])
3157     return costs[mode];
3158
3159   start_sequence ();
3160   force_operand (gen_rtx_fmt_ee (PLUS, mode,
3161                                  gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
3162                                  gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 2)),
3163                  NULL_RTX);
3164   seq = get_insns ();
3165   end_sequence ();
3166
3167   cost = seq_cost (seq);
3168   if (!cost)
3169     cost = 1;
3170
3171   costs[mode] = cost;
3172       
3173   if (dump_file && (dump_flags & TDF_DETAILS))
3174     fprintf (dump_file, "Addition in %s costs %d\n",
3175              GET_MODE_NAME (mode), cost);
3176   return cost;
3177 }
3178
3179 /* Entry in a hashtable of already known costs for multiplication.  */
3180 struct mbc_entry
3181 {
3182   HOST_WIDE_INT cst;            /* The constant to multiply by.  */
3183   enum machine_mode mode;       /* In mode.  */
3184   unsigned cost;                /* The cost.  */
3185 };
3186
3187 /* Counts hash value for the ENTRY.  */
3188
3189 static hashval_t
3190 mbc_entry_hash (const void *entry)
3191 {
3192   const struct mbc_entry *e = entry;
3193
3194   return 57 * (hashval_t) e->mode + (hashval_t) (e->cst % 877);
3195 }
3196
3197 /* Compares the hash table entries ENTRY1 and ENTRY2.  */
3198
3199 static int
3200 mbc_entry_eq (const void *entry1, const void *entry2)
3201 {
3202   const struct mbc_entry *e1 = entry1;
3203   const struct mbc_entry *e2 = entry2;
3204
3205   return (e1->mode == e2->mode
3206           && e1->cst == e2->cst);
3207 }
3208
3209 /* Returns cost of multiplication by constant CST in MODE.  */
3210
3211 unsigned
3212 multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode)
3213 {
3214   static htab_t costs;
3215   struct mbc_entry **cached, act;
3216   rtx seq;
3217   unsigned cost;
3218
3219   if (!costs)
3220     costs = htab_create (100, mbc_entry_hash, mbc_entry_eq, free);
3221
3222   act.mode = mode;
3223   act.cst = cst;
3224   cached = (struct mbc_entry **) htab_find_slot (costs, &act, INSERT);
3225   if (*cached)
3226     return (*cached)->cost;
3227
3228   *cached = xmalloc (sizeof (struct mbc_entry));
3229   (*cached)->mode = mode;
3230   (*cached)->cst = cst;
3231
3232   start_sequence ();
3233   expand_mult (mode, gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
3234                gen_int_mode (cst, mode), NULL_RTX, 0);
3235   seq = get_insns ();
3236   end_sequence ();
3237   
3238   cost = seq_cost (seq);
3239
3240   if (dump_file && (dump_flags & TDF_DETAILS))
3241     fprintf (dump_file, "Multiplication by %d in %s costs %d\n",
3242              (int) cst, GET_MODE_NAME (mode), cost);
3243
3244   (*cached)->cost = cost;
3245
3246   return cost;
3247 }
3248
3249 /* Returns true if multiplying by RATIO is allowed in address.  */
3250
3251 bool
3252 multiplier_allowed_in_address_p (HOST_WIDE_INT ratio)
3253 {
3254 #define MAX_RATIO 128
3255   static sbitmap valid_mult;
3256   
3257   if (!valid_mult)
3258     {
3259       rtx reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
3260       rtx addr;
3261       HOST_WIDE_INT i;
3262
3263       valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1);
3264       sbitmap_zero (valid_mult);
3265       addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX);
3266       for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
3267         {
3268           XEXP (addr, 1) = gen_int_mode (i, Pmode);
3269           if (memory_address_p (Pmode, addr))
3270             SET_BIT (valid_mult, i + MAX_RATIO);
3271         }
3272
3273       if (dump_file && (dump_flags & TDF_DETAILS))
3274         {
3275           fprintf (dump_file, "  allowed multipliers:");
3276           for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
3277             if (TEST_BIT (valid_mult, i + MAX_RATIO))
3278               fprintf (dump_file, " %d", (int) i);
3279           fprintf (dump_file, "\n");
3280           fprintf (dump_file, "\n");
3281         }
3282     }
3283
3284   if (ratio > MAX_RATIO || ratio < -MAX_RATIO)
3285     return false;
3286
3287   return TEST_BIT (valid_mult, ratio + MAX_RATIO);
3288 }
3289
3290 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
3291    If SYMBOL_PRESENT is false, symbol is omitted.  If VAR_PRESENT is false,
3292    variable is omitted.  The created memory accesses MODE.
3293    
3294    TODO -- there must be some better way.  This all is quite crude.  */
3295
3296 static unsigned
3297 get_address_cost (bool symbol_present, bool var_present,
3298                   unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio)
3299 {
3300   static bool initialized = false;
3301   static HOST_WIDE_INT rat, off;
3302   static HOST_WIDE_INT min_offset, max_offset;
3303   static unsigned costs[2][2][2][2];
3304   unsigned cost, acost;
3305   rtx seq, addr, base;
3306   bool offset_p, ratio_p;
3307   rtx reg1;
3308   HOST_WIDE_INT s_offset;
3309   unsigned HOST_WIDE_INT mask;
3310   unsigned bits;
3311
3312   if (!initialized)
3313     {
3314       HOST_WIDE_INT i;
3315       initialized = true;
3316
3317       reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
3318
3319       addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
3320       for (i = 1; i <= 1 << 20; i <<= 1)
3321         {
3322           XEXP (addr, 1) = gen_int_mode (i, Pmode);
3323           if (!memory_address_p (Pmode, addr))
3324             break;
3325         }
3326       max_offset = i >> 1;
3327       off = max_offset;
3328
3329       for (i = 1; i <= 1 << 20; i <<= 1)
3330         {
3331           XEXP (addr, 1) = gen_int_mode (-i, Pmode);
3332           if (!memory_address_p (Pmode, addr))
3333             break;
3334         }
3335       min_offset = -(i >> 1);
3336
3337       if (dump_file && (dump_flags & TDF_DETAILS))
3338         {
3339           fprintf (dump_file, "get_address_cost:\n");
3340           fprintf (dump_file, "  min offset %d\n", (int) min_offset);
3341           fprintf (dump_file, "  max offset %d\n", (int) max_offset);
3342         }
3343
3344       rat = 1;
3345       for (i = 2; i <= MAX_RATIO; i++)
3346         if (multiplier_allowed_in_address_p (i))
3347           {
3348             rat = i;
3349             break;
3350           }
3351     }
3352
3353   bits = GET_MODE_BITSIZE (Pmode);
3354   mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
3355   offset &= mask;
3356   if ((offset >> (bits - 1) & 1))
3357     offset |= ~mask;
3358   s_offset = offset;
3359
3360   cost = 0;
3361   offset_p = (s_offset != 0
3362               && min_offset <= s_offset && s_offset <= max_offset);
3363   ratio_p = (ratio != 1
3364              && multiplier_allowed_in_address_p (ratio));
3365
3366   if (ratio != 1 && !ratio_p)
3367     cost += multiply_by_cost (ratio, Pmode);
3368
3369   if (s_offset && !offset_p && !symbol_present)
3370     {
3371       cost += add_cost (Pmode);
3372       var_present = true;
3373     }
3374
3375   acost = costs[symbol_present][var_present][offset_p][ratio_p];
3376   if (!acost)
3377     {
3378       acost = 0;
3379       
3380       addr = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
3381       reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
3382       if (ratio_p)
3383         addr = gen_rtx_fmt_ee (MULT, Pmode, addr, gen_int_mode (rat, Pmode));
3384
3385       if (var_present)
3386         addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1);
3387
3388       if (symbol_present)
3389         {
3390           base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
3391           if (offset_p)
3392             base = gen_rtx_fmt_e (CONST, Pmode,
3393                                   gen_rtx_fmt_ee (PLUS, Pmode,
3394                                                   base,
3395                                                   gen_int_mode (off, Pmode)));
3396         }
3397       else if (offset_p)
3398         base = gen_int_mode (off, Pmode);
3399       else
3400         base = NULL_RTX;
3401     
3402       if (base)
3403         addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, base);
3404   
3405       start_sequence ();
3406       addr = memory_address (Pmode, addr);
3407       seq = get_insns ();
3408       end_sequence ();
3409   
3410       acost = seq_cost (seq);
3411       acost += address_cost (addr, Pmode);
3412
3413       if (!acost)
3414         acost = 1;
3415       costs[symbol_present][var_present][offset_p][ratio_p] = acost;
3416     }
3417
3418   return cost + acost;
3419 }
3420
3421 /* Estimates cost of forcing expression EXPR into a variable.  */
3422
3423 unsigned
3424 force_expr_to_var_cost (tree expr)
3425 {
3426   static bool costs_initialized = false;
3427   static unsigned integer_cost;
3428   static unsigned symbol_cost;
3429   static unsigned address_cost;
3430   tree op0, op1;
3431   unsigned cost0, cost1, cost;
3432   enum machine_mode mode;
3433
3434   if (!costs_initialized)
3435     {
3436       tree var = create_tmp_var_raw (integer_type_node, "test_var");
3437       rtx x = gen_rtx_MEM (DECL_MODE (var),
3438                            gen_rtx_SYMBOL_REF (Pmode, "test_var"));
3439       tree addr;
3440       tree type = build_pointer_type (integer_type_node);
3441
3442       integer_cost = computation_cost (build_int_cst_type (integer_type_node,
3443                                                            2000));
3444
3445       SET_DECL_RTL (var, x);
3446       TREE_STATIC (var) = 1;
3447       addr = build1 (ADDR_EXPR, type, var);
3448       symbol_cost = computation_cost (addr) + 1;
3449
3450       address_cost
3451         = computation_cost (build2 (PLUS_EXPR, type,
3452                                     addr,
3453                                     build_int_cst_type (type, 2000))) + 1;
3454       if (dump_file && (dump_flags & TDF_DETAILS))
3455         {
3456           fprintf (dump_file, "force_expr_to_var_cost:\n");
3457           fprintf (dump_file, "  integer %d\n", (int) integer_cost);
3458           fprintf (dump_file, "  symbol %d\n", (int) symbol_cost);
3459           fprintf (dump_file, "  address %d\n", (int) address_cost);
3460           fprintf (dump_file, "  other %d\n", (int) target_spill_cost);
3461           fprintf (dump_file, "\n");
3462         }
3463
3464       costs_initialized = true;
3465     }
3466
3467   STRIP_NOPS (expr);
3468
3469   if (SSA_VAR_P (expr))
3470     return 0;
3471
3472   if (TREE_INVARIANT (expr))
3473     {
3474       if (TREE_CODE (expr) == INTEGER_CST)
3475         return integer_cost;
3476
3477       if (TREE_CODE (expr) == ADDR_EXPR)
3478         {
3479           tree obj = TREE_OPERAND (expr, 0);
3480
3481           if (TREE_CODE (obj) == VAR_DECL
3482               || TREE_CODE (obj) == PARM_DECL
3483               || TREE_CODE (obj) == RESULT_DECL)
3484             return symbol_cost;
3485         }
3486
3487       return address_cost;
3488     }
3489
3490   switch (TREE_CODE (expr))
3491     {
3492     case PLUS_EXPR:
3493     case MINUS_EXPR:
3494     case MULT_EXPR:
3495       op0 = TREE_OPERAND (expr, 0);
3496       op1 = TREE_OPERAND (expr, 1);
3497       STRIP_NOPS (op0);
3498       STRIP_NOPS (op1);
3499
3500       if (is_gimple_val (op0))
3501         cost0 = 0;
3502       else
3503         cost0 = force_expr_to_var_cost (op0);
3504
3505       if (is_gimple_val (op1))
3506         cost1 = 0;
3507       else
3508         cost1 = force_expr_to_var_cost (op1);
3509
3510       break;
3511
3512     default:
3513       /* Just an arbitrary value, FIXME.  */
3514       return target_spill_cost;
3515     }
3516
3517   mode = TYPE_MODE (TREE_TYPE (expr));
3518   switch (TREE_CODE (expr))
3519     {
3520     case PLUS_EXPR:
3521     case MINUS_EXPR:
3522       cost = add_cost (mode);
3523       break;
3524
3525     case MULT_EXPR:
3526       if (cst_and_fits_in_hwi (op0))
3527         cost = multiply_by_cost (int_cst_value (op0), mode);
3528       else if (cst_and_fits_in_hwi (op1))
3529         cost = multiply_by_cost (int_cst_value (op1), mode);
3530       else
3531         return target_spill_cost;
3532       break;
3533
3534     default:
3535       gcc_unreachable ();
3536     }
3537
3538   cost += cost0;
3539   cost += cost1;
3540
3541   /* Bound the cost by target_spill_cost.  The parts of complicated
3542      computations often are either loop invariant or at least can
3543      be shared between several iv uses, so letting this grow without
3544      limits would not give reasonable results.  */
3545   return cost < target_spill_cost ? cost : target_spill_cost;
3546 }
3547
3548 /* Estimates cost of forcing EXPR into a variable.  DEPENDS_ON is a set of the
3549    invariants the computation depends on.  */
3550
3551 static unsigned
3552 force_var_cost (struct ivopts_data *data,
3553                 tree expr, bitmap *depends_on)
3554 {
3555   if (depends_on)
3556     {
3557       fd_ivopts_data = data;
3558       walk_tree (&expr, find_depends, depends_on, NULL);
3559     }
3560
3561   return force_expr_to_var_cost (expr);
3562 }
3563
3564 /* Estimates cost of expressing address ADDR  as var + symbol + offset.  The
3565    value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
3566    to false if the corresponding part is missing.  DEPENDS_ON is a set of the
3567    invariants the computation depends on.  */
3568
3569 static unsigned
3570 split_address_cost (struct ivopts_data *data,
3571                     tree addr, bool *symbol_present, bool *var_present,
3572                     unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
3573 {
3574   tree core;
3575   HOST_WIDE_INT bitsize;
3576   HOST_WIDE_INT bitpos;
3577   tree toffset;
3578   enum machine_mode mode;
3579   int unsignedp, volatilep;
3580   
3581   core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode,
3582                               &unsignedp, &volatilep, false);
3583
3584   if (toffset != 0
3585       || bitpos % BITS_PER_UNIT != 0
3586       || TREE_CODE (core) != VAR_DECL)
3587     {
3588       *symbol_present = false;
3589       *var_present = true;
3590       fd_ivopts_data = data;
3591       walk_tree (&addr, find_depends, depends_on, NULL);
3592       return target_spill_cost;
3593     }
3594
3595   *offset += bitpos / BITS_PER_UNIT;
3596   if (TREE_STATIC (core)
3597       || DECL_EXTERNAL (core))
3598     {
3599       *symbol_present = true;
3600       *var_present = false;
3601       return 0;
3602     }
3603       
3604   *symbol_present = false;
3605   *var_present = true;
3606   return 0;
3607 }
3608
3609 /* Estimates cost of expressing difference of addresses E1 - E2 as
3610    var + symbol + offset.  The value of offset is added to OFFSET,
3611    SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3612    part is missing.  DEPENDS_ON is a set of the invariants the computation
3613    depends on.  */
3614
3615 static unsigned
3616 ptr_difference_cost (struct ivopts_data *data,
3617                      tree e1, tree e2, bool *symbol_present, bool *var_present,
3618                      unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
3619 {
3620   HOST_WIDE_INT diff = 0;
3621   unsigned cost;
3622
3623   gcc_assert (TREE_CODE (e1) == ADDR_EXPR);