OSDN Git Service

c5b6e404e3bbdc84de935714482de0484cceff31
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-loop-ivopts.c
1 /* Induction variable optimizations.
2    Copyright (C) 2003 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, 59 Temple Place - Suite 330, Boston, MA
19 02111-1307, 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
92 /* The infinite cost.  */
93 #define INFTY 10000000
94
95 /* The expected number of loop iterations.  TODO -- use profiling instead of
96    this.  */
97 #define AVG_LOOP_NITER(LOOP) 5
98
99 /* Just to shorten the ugly names.  */
100 #define EXEC_BINARY nondestructive_fold_binary_to_constant
101 #define EXEC_UNARY nondestructive_fold_unary_to_constant
102
103 /* Representation of the induction variable.  */
104 struct iv
105 {
106   tree base;            /* Initial value of the iv.  */
107   tree step;            /* Step of the iv (constant only).  */
108   tree ssa_name;        /* The ssa name with the value.  */
109   bool biv_p;           /* Is it a biv?  */
110   bool have_use_for;    /* Do we already have a use for it?  */
111   unsigned use_id;      /* The identifier in the use if it is the case.  */
112 };
113
114 /* Per-ssa version information (induction variable descriptions, etc.).  */
115 struct version_info
116 {
117   tree name;            /* The ssa name.  */
118   struct iv *iv;        /* Induction variable description.  */
119   bool has_nonlin_use;  /* For a loop-level invariant, whether it is used in
120                            an expression that is not an induction variable.  */
121   unsigned inv_id;      /* Id of an invariant.  */
122   bool preserve_biv;    /* For the original biv, whether to preserve it.  */
123 };
124
125 /* Information attached to loop.  */
126 struct loop_data
127 {
128   struct tree_niter_desc niter;
129                         /* Number of iterations.  */
130
131   unsigned regs_used;   /* Number of registers used.  */
132 };
133
134 /* Types of uses.  */
135 enum use_type
136 {
137   USE_NONLINEAR_EXPR,   /* Use in a nonlinear expression.  */
138   USE_OUTER,            /* The induction variable is used outside the loop.  */
139   USE_ADDRESS,          /* Use in an address.  */
140   USE_COMPARE           /* Use is a compare.  */
141 };
142
143 /* The candidate - cost pair.  */
144 struct cost_pair
145 {
146   struct iv_cand *cand; /* The candidate.  */
147   unsigned cost;        /* The cost.  */
148   bitmap depends_on;    /* The list of invariants that have to be
149                            preserved.  */
150 };
151
152 /* Use.  */
153 struct iv_use
154 {
155   unsigned id;          /* The id of the use.  */
156   enum use_type type;   /* Type of the use.  */
157   struct iv *iv;        /* The induction variable it is based on.  */
158   tree stmt;            /* Statement in that it occurs.  */
159   tree *op_p;           /* The place where it occurs.  */
160   bitmap related_cands; /* The set of "related" iv candidates.  */
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 };
195
196 /* The data used by the induction variable optimizations.  */
197
198 struct ivopts_data
199 {
200   /* The currently optimized loop.  */
201   struct loop *current_loop;
202
203   /* The size of version_info array allocated.  */
204   unsigned version_info_size;
205
206   /* The array of information for the ssa names.  */
207   struct version_info *version_info;
208
209   /* The bitmap of indices in version_info whose value was changed.  */
210   bitmap relevant;
211
212   /* The maximum invariant id.  */
213   unsigned max_inv_id;
214
215   /* The uses of induction variables.  */
216   varray_type iv_uses;
217
218   /* The candidates.  */
219   varray_type iv_candidates;
220
221   /* Whether to consider just related and important candidates when replacing a
222      use.  */
223   bool consider_all_candidates;
224 };
225
226 /* Bound on number of candidates below that all candidates are considered.  */
227
228 #define CONSIDER_ALL_CANDIDATES_BOUND \
229   ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
230
231 /* If there are more iv occurrences, we just give up (it is quite unlikely that
232    optimizing such a loop would help, and it would take ages).  */
233
234 #define MAX_CONSIDERED_USES \
235   ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
236
237 /* The list of trees for that the decl_rtl field must be reset is stored
238    here.  */
239
240 static varray_type decl_rtl_to_reset;
241
242 /* Number of uses recorded in DATA.  */
243
244 static inline unsigned
245 n_iv_uses (struct ivopts_data *data)
246 {
247   return VARRAY_ACTIVE_SIZE (data->iv_uses);
248 }
249
250 /* Ith use recorded in DATA.  */
251
252 static inline struct iv_use *
253 iv_use (struct ivopts_data *data, unsigned i)
254 {
255   return VARRAY_GENERIC_PTR_NOGC (data->iv_uses, i);
256 }
257
258 /* Number of candidates recorded in DATA.  */
259
260 static inline unsigned
261 n_iv_cands (struct ivopts_data *data)
262 {
263   return VARRAY_ACTIVE_SIZE (data->iv_candidates);
264 }
265
266 /* Ith candidate recorded in DATA.  */
267
268 static inline struct iv_cand *
269 iv_cand (struct ivopts_data *data, unsigned i)
270 {
271   return VARRAY_GENERIC_PTR_NOGC (data->iv_candidates, i);
272 }
273
274 /* The data for LOOP.  */
275
276 static inline struct loop_data *
277 loop_data (struct loop *loop)
278 {
279   return loop->aux;
280 }
281
282 /* The single loop exit if it dominates the latch, NULL otherwise.  */
283
284 static edge
285 single_dom_exit (struct loop *loop)
286 {
287   edge exit = loop->single_exit;
288
289   if (!exit)
290     return NULL;
291
292   if (!just_once_each_iteration_p (loop, exit->src))
293     return NULL;
294
295   return exit;
296 }
297
298 /* Dumps information about the induction variable IV to FILE.  */
299
300 extern void dump_iv (FILE *, struct iv *);
301 void
302 dump_iv (FILE *file, struct iv *iv)
303 {
304   fprintf (file, "ssa name ");
305   print_generic_expr (file, iv->ssa_name, TDF_SLIM);
306   fprintf (file, "\n");
307
308   if (iv->step)
309     {
310       fprintf (file, "  base ");
311       print_generic_expr (file, iv->base, TDF_SLIM);
312       fprintf (file, "\n");
313
314       fprintf (file, "  step ");
315       print_generic_expr (file, iv->step, TDF_SLIM);
316       fprintf (file, "\n");
317     }
318   else
319     {
320       fprintf (file, "  invariant ");
321       print_generic_expr (file, iv->base, TDF_SLIM);
322       fprintf (file, "\n");
323     }
324
325   if (iv->biv_p)
326     fprintf (file, "  is a biv\n");
327 }
328
329 /* Dumps information about the USE to FILE.  */
330
331 extern void dump_use (FILE *, struct iv_use *);
332 void
333 dump_use (FILE *file, struct iv_use *use)
334 {
335   struct iv *iv = use->iv;
336
337   fprintf (file, "use %d\n", use->id);
338
339   switch (use->type)
340     {
341     case USE_NONLINEAR_EXPR:
342       fprintf (file, "  generic\n");
343       break;
344
345     case USE_OUTER:
346       fprintf (file, "  outside\n");
347       break;
348
349     case USE_ADDRESS:
350       fprintf (file, "  address\n");
351       break;
352
353     case USE_COMPARE:
354       fprintf (file, "  compare\n");
355       break;
356
357     default:
358       abort ();
359     }
360
361    fprintf (file, "  in statement ");
362    print_generic_expr (file, use->stmt, TDF_SLIM);
363    fprintf (file, "\n");
364
365    fprintf (file, "  at position ");
366    if (use->op_p)
367      print_generic_expr (file, *use->op_p, TDF_SLIM);
368    fprintf (file, "\n");
369
370    if (iv->step)
371      {
372        fprintf (file, "  base ");
373        print_generic_expr (file, iv->base, TDF_SLIM);
374        fprintf (file, "\n");
375
376        fprintf (file, "  step ");
377        print_generic_expr (file, iv->step, TDF_SLIM);
378        fprintf (file, "\n");
379      }
380    else
381      {
382        fprintf (file, "  invariant ");
383        print_generic_expr (file, iv->base, TDF_SLIM);
384        fprintf (file, "\n");
385      }
386
387    fprintf (file, "  related candidates ");
388    dump_bitmap (file, use->related_cands);
389 }
390
391 /* Dumps information about the uses to FILE.  */
392
393 extern void dump_uses (FILE *, struct ivopts_data *);
394 void
395 dump_uses (FILE *file, struct ivopts_data *data)
396 {
397   unsigned i;
398   struct iv_use *use;
399
400   for (i = 0; i < n_iv_uses (data); i++)
401     {
402       use = iv_use (data, i);
403
404       dump_use (file, use);
405       fprintf (file, "\n");
406     }
407 }
408
409 /* Dumps information about induction variable candidate CAND to FILE.  */
410
411 extern void dump_cand (FILE *, struct iv_cand *);
412 void
413 dump_cand (FILE *file, struct iv_cand *cand)
414 {
415   struct iv *iv = cand->iv;
416
417   fprintf (file, "candidate %d%s\n",
418            cand->id, cand->important ? " (important)" : "");
419
420   if (!iv)
421     {
422       fprintf (file, "  final value replacement\n");
423       return;
424     }
425
426   switch (cand->pos)
427     {
428     case IP_NORMAL:
429       fprintf (file, "  incremented before exit test\n");
430       break;
431
432     case IP_END:
433       fprintf (file, "  incremented at end\n");
434       break;
435
436     case IP_ORIGINAL:
437       fprintf (file, "  original biv\n");
438       break;
439     }
440
441    if (iv->step)
442      {
443        fprintf (file, "  base ");
444        print_generic_expr (file, iv->base, TDF_SLIM);
445        fprintf (file, "\n");
446
447        fprintf (file, "  step ");
448        print_generic_expr (file, iv->step, TDF_SLIM);
449        fprintf (file, "\n");
450      }
451    else
452      {
453        fprintf (file, "  invariant ");
454        print_generic_expr (file, iv->base, TDF_SLIM);
455        fprintf (file, "\n");
456      }
457 }
458
459 /* Returns the info for ssa version VER.  */
460
461 static inline struct version_info *
462 ver_info (struct ivopts_data *data, unsigned ver)
463 {
464   return data->version_info + ver;
465 }
466
467 /* Returns the info for ssa name NAME.  */
468
469 static inline struct version_info *
470 name_info (struct ivopts_data *data, tree name)
471 {
472   return ver_info (data, SSA_NAME_VERSION (name));
473 }
474
475 /* Checks whether there exists number X such that X * B = A, counting modulo
476    2^BITS.  */
477
478 static bool
479 divide (unsigned bits, unsigned HOST_WIDE_INT a, unsigned HOST_WIDE_INT b,
480         HOST_WIDE_INT *x)
481 {
482   unsigned HOST_WIDE_INT mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
483   unsigned HOST_WIDE_INT inv, ex, val;
484   unsigned i;
485
486   a &= mask;
487   b &= mask;
488
489   /* First divide the whole equation by 2 as long as possible.  */
490   while (!(a & 1) && !(b & 1))
491     {
492       a >>= 1;
493       b >>= 1;
494       bits--;
495       mask >>= 1;
496     }
497
498   if (!(b & 1))
499     {
500       /* If b is still even, a is odd and there is no such x.  */
501       return false;
502     }
503
504   /* Find the inverse of b.  We compute it as
505      b^(2^(bits - 1) - 1) (mod 2^bits).  */
506   inv = 1;
507   ex = b;
508   for (i = 0; i < bits - 1; i++)
509     {
510       inv = (inv * ex) & mask;
511       ex = (ex * ex) & mask;
512     }
513
514   val = (a * inv) & mask;
515
516   if (((val * b) & mask) != a)
517     abort ();
518
519   if ((val >> (bits - 1)) & 1)
520     val |= ~mask;
521
522   *x = val;
523
524   return true;
525 }
526
527 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
528    emitted in LOOP.  */
529
530 static bool
531 stmt_after_ip_normal_pos (struct loop *loop, tree stmt)
532 {
533   basic_block bb = ip_normal_pos (loop), sbb = bb_for_stmt (stmt);
534
535   if (!bb)
536     abort ();
537
538   if (sbb == loop->latch)
539     return true;
540
541   if (sbb != bb)
542     return false;
543
544   return stmt == last_stmt (bb);
545 }
546
547 /* Returns true if STMT if after the place where the original induction
548    variable CAND is incremented.  */
549
550 static bool
551 stmt_after_ip_original_pos (struct iv_cand *cand, tree stmt)
552 {
553   basic_block cand_bb = bb_for_stmt (cand->incremented_at);
554   basic_block stmt_bb = bb_for_stmt (stmt);
555   block_stmt_iterator bsi;
556
557   if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
558     return false;
559
560   if (stmt_bb != cand_bb)
561     return true;
562
563   /* Scan the block from the end, since the original ivs are usually
564      incremented at the end of the loop body.  */
565   for (bsi = bsi_last (stmt_bb); ; bsi_prev (&bsi))
566     {
567       if (bsi_stmt (bsi) == cand->incremented_at)
568         return false;
569       if (bsi_stmt (bsi) == stmt)
570         return true;
571     }
572 }
573
574 /* Returns true if STMT if after the place where the induction variable
575    CAND is incremented in LOOP.  */
576
577 static bool
578 stmt_after_increment (struct loop *loop, struct iv_cand *cand, tree stmt)
579 {
580   switch (cand->pos)
581     {
582     case IP_END:
583       return false;
584
585     case IP_NORMAL:
586       return stmt_after_ip_normal_pos (loop, stmt);
587
588     case IP_ORIGINAL:
589       return stmt_after_ip_original_pos (cand, stmt);
590
591     default:
592       abort ();
593     }
594 }
595
596 /* Initializes data structures used by the iv optimization pass, stored
597    in DATA.  LOOPS is the loop tree.  */
598
599 static void
600 tree_ssa_iv_optimize_init (struct loops *loops, struct ivopts_data *data)
601 {
602   unsigned i;
603
604   data->version_info_size = 2 * num_ssa_names;
605   data->version_info = xcalloc (data->version_info_size,
606                                 sizeof (struct version_info));
607   data->relevant = BITMAP_XMALLOC ();
608   data->max_inv_id = 0;
609
610   for (i = 1; i < loops->num; i++)
611     if (loops->parray[i])
612       loops->parray[i]->aux = xcalloc (1, sizeof (struct loop_data));
613
614   VARRAY_GENERIC_PTR_NOGC_INIT (data->iv_uses, 20, "iv_uses");
615   VARRAY_GENERIC_PTR_NOGC_INIT (data->iv_candidates, 20, "iv_candidates");
616   VARRAY_GENERIC_PTR_NOGC_INIT (decl_rtl_to_reset, 20, "decl_rtl_to_reset");
617 }
618
619 /* Allocates an induction variable with given initial value BASE and step STEP
620    for loop LOOP.  */
621
622 static struct iv *
623 alloc_iv (tree base, tree step)
624 {
625   struct iv *iv = xcalloc (1, sizeof (struct iv));
626
627   if (step && integer_zerop (step))
628     step = NULL_TREE;
629
630   iv->base = base;
631   iv->step = step;
632   iv->biv_p = false;
633   iv->have_use_for = false;
634   iv->use_id = 0;
635   iv->ssa_name = NULL_TREE;
636
637   return iv;
638 }
639
640 /* Sets STEP and BASE for induction variable IV.  */
641
642 static void
643 set_iv (struct ivopts_data *data, tree iv, tree base, tree step)
644 {
645   struct version_info *info = name_info (data, iv);
646
647   if (info->iv)
648     abort ();
649
650   bitmap_set_bit (data->relevant, SSA_NAME_VERSION (iv));
651   info->iv = alloc_iv (base, step);
652   info->iv->ssa_name = iv;
653 }
654
655 /* Finds induction variable declaration for VAR.  */
656
657 static struct iv *
658 get_iv (struct ivopts_data *data, tree var)
659 {
660   basic_block bb;
661   
662   if (!name_info (data, var)->iv)
663     {
664       bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
665
666       if (!bb
667           || !flow_bb_inside_loop_p (data->current_loop, bb))
668         set_iv (data, var, var, NULL_TREE);
669     }
670
671   return name_info (data, var)->iv;
672 }
673
674 /* Determines the step of a biv defined in PHI.  */
675
676 static tree
677 determine_biv_step (tree phi)
678 {
679   struct loop *loop = bb_for_stmt (phi)->loop_father;
680   tree name = PHI_RESULT (phi), base, step;
681   tree type = TREE_TYPE (name);
682
683   if (!is_gimple_reg (name))
684     return NULL_TREE;
685
686   if (!simple_iv (loop, phi, name, &base, &step))
687     return NULL_TREE;
688
689   if (!step)
690     return build_int_cst (type, 0);
691
692   return step;
693 }
694
695 /* Returns false if INDEX is a ssa name that occurs in an
696    abnormal phi node.  Callback for for_each_index.  */
697
698 static bool
699 idx_contains_abnormal_ssa_name_p (tree base ATTRIBUTE_UNUSED, tree *index,
700                                   void *data ATTRIBUTE_UNUSED)
701 {
702   if (TREE_CODE (*index) != SSA_NAME)
703     return true;
704
705   return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (*index) == 0;
706 }
707
708 /* Returns true if EXPR contains a ssa name that occurs in an
709    abnormal phi node.  */
710
711 static bool
712 contains_abnormal_ssa_name_p (tree expr)
713 {
714   enum tree_code code = TREE_CODE (expr);
715   char class = TREE_CODE_CLASS (code);
716     
717   if (code == SSA_NAME)
718     return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
719
720   if (code == INTEGER_CST
721       || is_gimple_min_invariant (expr))
722     return false;
723
724   if (code == ADDR_EXPR)
725     return !for_each_index (&TREE_OPERAND (expr, 1),
726                             idx_contains_abnormal_ssa_name_p,
727                             NULL);
728
729   switch (class)
730     {
731     case '2':
732     case '<':
733       if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1)))
734         return true;
735
736       /* Fallthru.  */
737     case '1':
738       if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0)))
739         return true;
740
741       break;
742
743     default:
744       abort ();
745     }
746
747   return false;
748 }
749
750 /* Finds basic ivs.  */
751
752 static bool
753 find_bivs (struct ivopts_data *data)
754 {
755   tree phi, step, type, base;
756   bool found = false;
757   struct loop *loop = data->current_loop;
758
759   for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
760     {
761       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
762         continue;
763
764       step = determine_biv_step (phi);
765
766       if (!step)
767         continue;
768       if (cst_and_fits_in_hwi (step)
769           && int_cst_value (step) == 0)
770         continue;
771
772       base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
773       if (contains_abnormal_ssa_name_p (base))
774         continue;
775
776       type = TREE_TYPE (PHI_RESULT (phi));
777       base = fold_convert (type, base);
778       step = fold_convert (type, step);
779
780       /* FIXME: We do not handle induction variables whose step does
781          not satisfy cst_and_fits_in_hwi.  */
782       if (!cst_and_fits_in_hwi (step))
783         continue;
784
785       set_iv (data, PHI_RESULT (phi), base, step);
786       found = true;
787     }
788
789   return found;
790 }
791
792 /* Marks basic ivs.  */
793
794 static void
795 mark_bivs (struct ivopts_data *data)
796 {
797   tree phi, var;
798   struct iv *iv, *incr_iv;
799   struct loop *loop = data->current_loop;
800   basic_block incr_bb;
801
802   for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
803     {
804       iv = get_iv (data, PHI_RESULT (phi));
805       if (!iv)
806         continue;
807
808       var = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
809       incr_iv = get_iv (data, var);
810       if (!incr_iv)
811         continue;
812
813       /* If the increment is in the subloop, ignore it.  */
814       incr_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
815       if (incr_bb->loop_father != data->current_loop
816           || (incr_bb->flags & BB_IRREDUCIBLE_LOOP))
817         continue;
818
819       iv->biv_p = true;
820       incr_iv->biv_p = true;
821     }
822 }
823
824 /* Checks whether STMT defines a linear induction variable and stores its
825    parameters to BASE and STEP.  */
826
827 static bool
828 find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt,
829                         tree *base, tree *step)
830 {
831   tree lhs;
832   struct loop *loop = data->current_loop;
833
834   *base = NULL_TREE;
835   *step = NULL_TREE;
836
837   if (TREE_CODE (stmt) != MODIFY_EXPR)
838     return false;
839
840   lhs = TREE_OPERAND (stmt, 0);
841   if (TREE_CODE (lhs) != SSA_NAME)
842     return false;
843
844   if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), base, step))
845     return false;
846
847   /* FIXME: We do not handle induction variables whose step does
848      not satisfy cst_and_fits_in_hwi.  */
849   if (!zero_p (*step)
850       && !cst_and_fits_in_hwi (*step))
851     return false;
852
853   if (contains_abnormal_ssa_name_p (*base))
854     return false;
855
856   return true;
857 }
858
859 /* Finds general ivs in statement STMT.  */
860
861 static void
862 find_givs_in_stmt (struct ivopts_data *data, tree stmt)
863 {
864   tree base, step;
865
866   if (!find_givs_in_stmt_scev (data, stmt, &base, &step))
867     return;
868
869   set_iv (data, TREE_OPERAND (stmt, 0), base, step);
870 }
871
872 /* Finds general ivs in basic block BB.  */
873
874 static void
875 find_givs_in_bb (struct ivopts_data *data, basic_block bb)
876 {
877   block_stmt_iterator bsi;
878
879   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
880     find_givs_in_stmt (data, bsi_stmt (bsi));
881 }
882
883 /* Finds general ivs.  */
884
885 static void
886 find_givs (struct ivopts_data *data)
887 {
888   struct loop *loop = data->current_loop;
889   basic_block *body = get_loop_body_in_dom_order (loop);
890   unsigned i;
891
892   for (i = 0; i < loop->num_nodes; i++)
893     find_givs_in_bb (data, body[i]);
894   free (body);
895 }
896
897 /* Determine the number of iterations of the current loop.  */
898
899 static void
900 determine_number_of_iterations (struct ivopts_data *data)
901 {
902   struct loop *loop = data->current_loop;
903   edge exit = single_dom_exit (loop);
904
905   if (!exit)
906     return;
907
908   number_of_iterations_exit (loop, exit, &loop_data (loop)->niter);
909 }
910
911 /* For each ssa name defined in LOOP determines whether it is an induction
912    variable and if so, its initial value and step.  */
913
914 static bool
915 find_induction_variables (struct ivopts_data *data)
916 {
917   unsigned i;
918   struct loop *loop = data->current_loop;
919
920   if (!find_bivs (data))
921     return false;
922
923   find_givs (data);
924   mark_bivs (data);
925   determine_number_of_iterations (data);
926
927   if (dump_file && (dump_flags & TDF_DETAILS))
928     {
929       if (loop_data (loop)->niter.niter)
930         {
931           fprintf (dump_file, "  number of iterations ");
932           print_generic_expr (dump_file, loop_data (loop)->niter.niter,
933                               TDF_SLIM);
934           fprintf (dump_file, "\n");
935
936           fprintf (dump_file, "  may be zero if ");
937           print_generic_expr (dump_file, loop_data (loop)->niter.may_be_zero,
938                               TDF_SLIM);
939           fprintf (dump_file, "\n");
940
941           fprintf (dump_file, "  bogus unless ");
942           print_generic_expr (dump_file, loop_data (loop)->niter.assumptions,
943                               TDF_SLIM);
944           fprintf (dump_file, "\n");
945           fprintf (dump_file, "\n");
946         };
947  
948       fprintf (dump_file, "Induction variables:\n\n");
949
950       EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i,
951         {
952           if (ver_info (data, i)->iv)
953             dump_iv (dump_file, ver_info (data, i)->iv);
954         });
955     }
956
957   return true;
958 }
959
960 /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV.  */
961
962 static struct iv_use *
963 record_use (struct ivopts_data *data, tree *use_p, struct iv *iv,
964             tree stmt, enum use_type use_type)
965 {
966   struct iv_use *use = xcalloc (1, sizeof (struct iv_use));
967
968   use->id = n_iv_uses (data);
969   use->type = use_type;
970   use->iv = iv;
971   use->stmt = stmt;
972   use->op_p = use_p;
973   use->related_cands = BITMAP_XMALLOC ();
974
975   if (dump_file && (dump_flags & TDF_DETAILS))
976     dump_use (dump_file, use);
977
978   VARRAY_PUSH_GENERIC_PTR_NOGC (data->iv_uses, use);
979
980   return use;
981 }
982
983 /* Checks whether OP is a loop-level invariant and if so, records it.
984    NONLINEAR_USE is true if the invariant is used in a way we do not
985    handle specially.  */
986
987 static void
988 record_invariant (struct ivopts_data *data, tree op, bool nonlinear_use)
989 {
990   basic_block bb;
991   struct version_info *info;
992
993   if (TREE_CODE (op) != SSA_NAME
994       || !is_gimple_reg (op))
995     return;
996
997   bb = bb_for_stmt (SSA_NAME_DEF_STMT (op));
998   if (bb
999       && flow_bb_inside_loop_p (data->current_loop, bb))
1000     return;
1001
1002   info = name_info (data, op);
1003   info->name = op;
1004   info->has_nonlin_use |= nonlinear_use;
1005   if (!info->inv_id)
1006     info->inv_id = ++data->max_inv_id;
1007   bitmap_set_bit (data->relevant, SSA_NAME_VERSION (op));
1008 }
1009
1010 /* Checks whether the use OP is interesting and if so, records it
1011    as TYPE.  */
1012
1013 static struct iv_use *
1014 find_interesting_uses_outer_or_nonlin (struct ivopts_data *data, tree op,
1015                                        enum use_type type)
1016 {
1017   struct iv *iv;
1018   struct iv *civ;
1019   tree stmt;
1020   struct iv_use *use;
1021
1022   if (TREE_CODE (op) != SSA_NAME)
1023     return NULL;
1024
1025   iv = get_iv (data, op);
1026   if (!iv)
1027     return NULL;
1028   
1029   if (iv->have_use_for)
1030     {
1031       use = iv_use (data, iv->use_id);
1032
1033       if (use->type != USE_NONLINEAR_EXPR
1034           && use->type != USE_OUTER)
1035         abort ();
1036
1037       if (type == USE_NONLINEAR_EXPR)
1038         use->type = USE_NONLINEAR_EXPR;
1039       return use;
1040     }
1041
1042   if (zero_p (iv->step))
1043     {
1044       record_invariant (data, op, true);
1045       return NULL;
1046     }
1047   iv->have_use_for = true;
1048
1049   civ = xmalloc (sizeof (struct iv));
1050   *civ = *iv;
1051
1052   stmt = SSA_NAME_DEF_STMT (op);
1053   if (TREE_CODE (stmt) != PHI_NODE
1054       && TREE_CODE (stmt) != MODIFY_EXPR)
1055     abort ();
1056
1057   use = record_use (data, NULL, civ, stmt, type);
1058   iv->use_id = use->id;
1059
1060   return use;
1061 }
1062
1063 /* Checks whether the use OP is interesting and if so, records it.  */
1064
1065 static struct iv_use *
1066 find_interesting_uses_op (struct ivopts_data *data, tree op)
1067 {
1068   return find_interesting_uses_outer_or_nonlin (data, op, USE_NONLINEAR_EXPR);
1069 }
1070
1071 /* Records a definition of induction variable OP that is used outside of the
1072    loop.  */
1073
1074 static struct iv_use *
1075 find_interesting_uses_outer (struct ivopts_data *data, tree op)
1076 {
1077   return find_interesting_uses_outer_or_nonlin (data, op, USE_OUTER);
1078 }
1079
1080 /* Checks whether the condition *COND_P in STMT is interesting
1081    and if so, records it.  */
1082
1083 static void
1084 find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
1085 {
1086   tree *op0_p;
1087   tree *op1_p;
1088   struct iv *iv0 = NULL, *iv1 = NULL, *civ;
1089   struct iv const_iv;
1090   tree zero = integer_zero_node;
1091
1092   const_iv.step = NULL_TREE;
1093
1094   if (integer_zerop (*cond_p)
1095       || integer_nonzerop (*cond_p))
1096     return;
1097
1098   if (TREE_CODE (*cond_p) == SSA_NAME)
1099     {
1100       op0_p = cond_p;
1101       op1_p = &zero;
1102     }
1103   else
1104     {
1105       op0_p = &TREE_OPERAND (*cond_p, 0);
1106       op1_p = &TREE_OPERAND (*cond_p, 1);
1107     }
1108
1109   if (TREE_CODE (*op0_p) == SSA_NAME)
1110     iv0 = get_iv (data, *op0_p);
1111   else
1112     iv0 = &const_iv;
1113
1114   if (TREE_CODE (*op1_p) == SSA_NAME)
1115     iv1 = get_iv (data, *op1_p);
1116   else
1117     iv1 = &const_iv;
1118
1119   if (/* When comparing with non-invariant value, we may not do any senseful
1120          induction variable elimination.  */
1121       (!iv0 || !iv1)
1122       /* Eliminating condition based on two ivs would be nontrivial.
1123          ??? TODO -- it is not really important to handle this case.  */
1124       || (!zero_p (iv0->step) && !zero_p (iv1->step)))
1125     {
1126       find_interesting_uses_op (data, *op0_p);
1127       find_interesting_uses_op (data, *op1_p);
1128       return;
1129     }
1130
1131   if (zero_p (iv0->step) && zero_p (iv1->step))
1132     {
1133       /* If both are invariants, this is a work for unswitching.  */
1134       return;
1135     }
1136
1137   civ = xmalloc (sizeof (struct iv));
1138   *civ = zero_p (iv0->step) ? *iv1: *iv0;
1139   record_use (data, cond_p, civ, stmt, USE_COMPARE);
1140 }
1141
1142 /* Cumulates the steps of indices into DATA and replaces their values with the
1143    initial ones.  Returns false when the value of the index cannot be determined.
1144    Callback for for_each_index.  */
1145
1146 struct ifs_ivopts_data
1147 {
1148   struct ivopts_data *ivopts_data;
1149   tree stmt;
1150   tree *step_p;
1151 };
1152
1153 static bool
1154 idx_find_step (tree base, tree *idx, void *data)
1155 {
1156   struct ifs_ivopts_data *dta = data;
1157   struct iv *iv;
1158   tree step, type, iv_type, iv_step;
1159   
1160   if (TREE_CODE (*idx) != SSA_NAME)
1161     return true;
1162
1163   iv = get_iv (dta->ivopts_data, *idx);
1164   if (!iv)
1165     return false;
1166
1167   *idx = iv->base;
1168
1169   if (!iv->step)
1170     return true;
1171
1172   iv_type = TREE_TYPE (iv->base);
1173   type = build_pointer_type (TREE_TYPE (base));
1174   if (TREE_CODE (base) == ARRAY_REF)
1175     step = array_ref_element_size (base);
1176   else
1177     /* The step for pointer arithmetics already is 1 byte.  */
1178     step = build_int_cst (type, 1);
1179
1180   if (TYPE_PRECISION (iv_type) < TYPE_PRECISION (type))
1181     iv_step = can_count_iv_in_wider_type (dta->ivopts_data->current_loop,
1182                                           type, iv->base, iv->step, dta->stmt);
1183   else
1184     iv_step = fold_convert (iv_type, iv->step);
1185
1186   if (!iv_step)
1187     {
1188       /* The index might wrap.  */
1189       return false;
1190     }
1191
1192   step = EXEC_BINARY (MULT_EXPR, type, step, iv_step);
1193
1194   if (!*dta->step_p)
1195     *dta->step_p = step;
1196   else
1197     *dta->step_p = EXEC_BINARY (PLUS_EXPR, type, *dta->step_p, step);
1198
1199   return true;
1200 }
1201
1202 /* Records use in index IDX.  Callback for for_each_index.  Ivopts data
1203    object is passed to it in DATA.  */
1204
1205 static bool
1206 idx_record_use (tree base ATTRIBUTE_UNUSED, tree *idx,
1207                 void *data)
1208 {
1209   find_interesting_uses_op (data, *idx);
1210   return true;
1211 }
1212
1213 /* Finds addresses in *OP_P inside STMT.  */
1214
1215 static void
1216 find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
1217 {
1218   tree base = unshare_expr (*op_p), step = NULL;
1219   struct iv *civ;
1220   struct ifs_ivopts_data ifs_ivopts_data;
1221
1222   /* Ignore bitfields for now.  Not really something terribly complicated
1223      to handle.  TODO.  */
1224   if (TREE_CODE (base) == COMPONENT_REF
1225       && DECL_NONADDRESSABLE_P (TREE_OPERAND (base, 1)))
1226     goto fail;
1227
1228   ifs_ivopts_data.ivopts_data = data;
1229   ifs_ivopts_data.stmt = stmt;
1230   ifs_ivopts_data.step_p = &step;
1231   if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
1232       || zero_p (step))
1233     goto fail;
1234
1235   if (TREE_CODE (base) == INDIRECT_REF)
1236     base = TREE_OPERAND (base, 0);
1237   else
1238     base = build_addr (base);
1239
1240   civ = alloc_iv (base, step);
1241   record_use (data, op_p, civ, stmt, USE_ADDRESS);
1242   return;
1243
1244 fail:
1245   for_each_index (op_p, idx_record_use, data);
1246 }
1247
1248 /* Finds and records invariants used in STMT.  */
1249
1250 static void
1251 find_invariants_stmt (struct ivopts_data *data, tree stmt)
1252 {
1253   use_optype uses = NULL;
1254   unsigned i, n;
1255   tree op;
1256
1257   if (TREE_CODE (stmt) == PHI_NODE)
1258     n = PHI_NUM_ARGS (stmt);
1259   else
1260     {
1261       get_stmt_operands (stmt);
1262       uses = STMT_USE_OPS (stmt);
1263       n = NUM_USES (uses);
1264     }
1265
1266   for (i = 0; i < n; i++)
1267     {
1268       if (TREE_CODE (stmt) == PHI_NODE)
1269         op = PHI_ARG_DEF (stmt, i);
1270       else
1271         op = USE_OP (uses, i);
1272
1273       record_invariant (data, op, false);
1274     }
1275 }
1276
1277 /* Finds interesting uses of induction variables in the statement STMT.  */
1278
1279 static void
1280 find_interesting_uses_stmt (struct ivopts_data *data, tree stmt)
1281 {
1282   struct iv *iv;
1283   tree op, lhs, rhs;
1284   use_optype uses = NULL;
1285   unsigned i, n;
1286
1287   find_invariants_stmt (data, stmt);
1288
1289   if (TREE_CODE (stmt) == COND_EXPR)
1290     {
1291       find_interesting_uses_cond (data, stmt, &COND_EXPR_COND (stmt));
1292       return;
1293     }
1294
1295   if (TREE_CODE (stmt) == MODIFY_EXPR)
1296     {
1297       lhs = TREE_OPERAND (stmt, 0);
1298       rhs = TREE_OPERAND (stmt, 1);
1299
1300       if (TREE_CODE (lhs) == SSA_NAME)
1301         {
1302           /* If the statement defines an induction variable, the uses are not
1303              interesting by themselves.  */
1304
1305           iv = get_iv (data, lhs);
1306
1307           if (iv && !zero_p (iv->step))
1308             return;
1309         }
1310
1311       switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
1312         {
1313         case '<':
1314           find_interesting_uses_cond (data, stmt, &TREE_OPERAND (stmt, 1));
1315           return;
1316
1317         case 'r':
1318           find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 1));
1319           if (TREE_CODE_CLASS (TREE_CODE (lhs)) == 'r')
1320             find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
1321           return;
1322
1323         default: ;
1324         }
1325
1326       if (TREE_CODE_CLASS (TREE_CODE (lhs)) == 'r')
1327         {
1328           find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
1329           find_interesting_uses_op (data, rhs);
1330           return;
1331         }
1332     }
1333
1334   if (TREE_CODE (stmt) == PHI_NODE
1335       && bb_for_stmt (stmt) == data->current_loop->header)
1336     {
1337       lhs = PHI_RESULT (stmt);
1338       iv = get_iv (data, lhs);
1339
1340       if (iv && !zero_p (iv->step))
1341         return;
1342     }
1343
1344   if (TREE_CODE (stmt) == PHI_NODE)
1345     n = PHI_NUM_ARGS (stmt);
1346   else
1347     {
1348       uses = STMT_USE_OPS (stmt);
1349       n = NUM_USES (uses);
1350     }
1351
1352   for (i = 0; i < n; i++)
1353     {
1354       if (TREE_CODE (stmt) == PHI_NODE)
1355         op = PHI_ARG_DEF (stmt, i);
1356       else
1357         op = USE_OP (uses, i);
1358
1359       if (TREE_CODE (op) != SSA_NAME)
1360         continue;
1361
1362       iv = get_iv (data, op);
1363       if (!iv)
1364         continue;
1365
1366       find_interesting_uses_op (data, op);
1367     }
1368 }
1369
1370 /* Finds interesting uses of induction variables outside of loops
1371    on loop exit edge EXIT.  */
1372
1373 static void
1374 find_interesting_uses_outside (struct ivopts_data *data, edge exit)
1375 {
1376   tree phi, def;
1377
1378   for (phi = phi_nodes (exit->dest); phi; phi = TREE_CHAIN (phi))
1379     {
1380       def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1381       find_interesting_uses_outer (data, def);
1382     }
1383 }
1384
1385 /* Finds uses of the induction variables that are interesting.  */
1386
1387 static void
1388 find_interesting_uses (struct ivopts_data *data)
1389 {
1390   basic_block bb;
1391   block_stmt_iterator bsi;
1392   tree phi;
1393   basic_block *body = get_loop_body (data->current_loop);
1394   unsigned i;
1395   struct version_info *info;
1396   edge e;
1397
1398   if (dump_file && (dump_flags & TDF_DETAILS))
1399     fprintf (dump_file, "Uses:\n\n");
1400
1401   for (i = 0; i < data->current_loop->num_nodes; i++)
1402     {
1403       bb = body[i];
1404
1405       for (e = bb->succ; e; e = e->succ_next)
1406         if (e->dest != EXIT_BLOCK_PTR
1407             && !flow_bb_inside_loop_p (data->current_loop, e->dest))
1408           find_interesting_uses_outside (data, e);
1409
1410       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1411         find_interesting_uses_stmt (data, phi);
1412       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1413         find_interesting_uses_stmt (data, bsi_stmt (bsi));
1414     }
1415
1416   if (dump_file && (dump_flags & TDF_DETAILS))
1417     {
1418       fprintf (dump_file, "\n");
1419
1420       EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i,
1421         {
1422           info = ver_info (data, i);
1423           if (info->inv_id)
1424             {
1425               fprintf (dump_file, "  ");
1426               print_generic_expr (dump_file, info->name, TDF_SLIM);
1427               fprintf (dump_file, " is invariant (%d)%s\n",
1428                        info->inv_id, info->has_nonlin_use ? "" : ", eliminable");
1429             }
1430         });
1431
1432       fprintf (dump_file, "\n");
1433     }
1434
1435   free (body);
1436 }
1437
1438 /* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
1439    position to POS.  If USE is not NULL, the candidate is set as related to
1440    it.  If both BASE and STEP are NULL, we add a pseudocandidate for the
1441    replacement of the final value of the iv by a direct computation.  */
1442
1443 static struct iv_cand *
1444 add_candidate_1 (struct ivopts_data *data,
1445                  tree base, tree step, bool important, enum iv_position pos,
1446                  struct iv_use *use, tree incremented_at)
1447 {
1448   unsigned i;
1449   struct iv_cand *cand = NULL;
1450   tree type;
1451   
1452   if (base)
1453     {
1454       type = TREE_TYPE (base);
1455       if (!TYPE_UNSIGNED (type))
1456         {
1457           type = unsigned_type_for (type);
1458           base = fold_convert (type, base);
1459           if (step)
1460             step = fold_convert (type, step);
1461         }
1462     }
1463
1464   for (i = 0; i < n_iv_cands (data); i++)
1465     {
1466       cand = iv_cand (data, i);
1467
1468       if (cand->pos != pos)
1469         continue;
1470
1471       if (cand->incremented_at != incremented_at)
1472         continue;
1473
1474       if (!cand->iv)
1475         {
1476           if (!base && !step)
1477             break;
1478
1479           continue;
1480         }
1481
1482       if (!base && !step)
1483         continue;
1484
1485       if (!operand_equal_p (base, cand->iv->base, 0))
1486         continue;
1487
1488       if (zero_p (cand->iv->step))
1489         {
1490           if (zero_p (step))
1491             break;
1492         }
1493       else
1494         {
1495           if (step && operand_equal_p (step, cand->iv->step, 0))
1496             break;
1497         }
1498     }
1499
1500   if (i == n_iv_cands (data))
1501     {
1502       cand = xcalloc (1, sizeof (struct iv_cand));
1503       cand->id = i;
1504
1505       if (!base && !step)
1506         cand->iv = NULL;
1507       else
1508         cand->iv = alloc_iv (base, step);
1509
1510       cand->pos = pos;
1511       if (pos != IP_ORIGINAL && cand->iv)
1512         {
1513           cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp");
1514           cand->var_after = cand->var_before;
1515         }
1516       cand->important = important;
1517       cand->incremented_at = incremented_at;
1518       VARRAY_PUSH_GENERIC_PTR_NOGC (data->iv_candidates, cand);
1519
1520       if (dump_file && (dump_flags & TDF_DETAILS))
1521         dump_cand (dump_file, cand);
1522     }
1523
1524   if (important && !cand->important)
1525     {
1526       cand->important = true;
1527       if (dump_file && (dump_flags & TDF_DETAILS))
1528         fprintf (dump_file, "Candidate %d is important\n", cand->id);
1529     }
1530
1531   if (use)
1532     {
1533       bitmap_set_bit (use->related_cands, i);
1534       if (dump_file && (dump_flags & TDF_DETAILS))
1535         fprintf (dump_file, "Candidate %d is related to use %d\n",
1536                  cand->id, use->id);
1537     }
1538
1539   return cand;
1540 }
1541
1542 /* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
1543    position to POS.  If USE is not NULL, the candidate is set as related to
1544    it.  The candidate computation is scheduled on all available positions.  */
1545
1546 static void
1547 add_candidate (struct ivopts_data *data, 
1548                tree base, tree step, bool important, struct iv_use *use)
1549 {
1550   if (ip_normal_pos (data->current_loop))
1551     add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL_TREE);
1552   if (ip_end_pos (data->current_loop))
1553     add_candidate_1 (data, base, step, important, IP_END, use, NULL_TREE);
1554 }
1555
1556 /* Adds standard iv candidates.  */
1557
1558 static void
1559 add_standard_iv_candidates (struct ivopts_data *data)
1560 {
1561   /* Add 0 + 1 * iteration candidate.  */
1562   add_candidate (data,
1563                  build_int_cst (unsigned_intSI_type_node, 0),
1564                  build_int_cst (unsigned_intSI_type_node, 1),
1565                  true, NULL);
1566
1567   /* The same for a long type if it is still fast enought.  */
1568   if (BITS_PER_WORD > 32)
1569     add_candidate (data,
1570                    build_int_cst (unsigned_intDI_type_node, 0),
1571                    build_int_cst (unsigned_intDI_type_node, 1),
1572                    true, NULL);
1573 }
1574
1575
1576 /* Adds candidates bases on the old induction variable IV.  */
1577
1578 static void
1579 add_old_iv_candidates (struct ivopts_data *data, struct iv *iv)
1580 {
1581   tree phi, def;
1582   struct iv_cand *cand;
1583
1584   add_candidate (data, iv->base, iv->step, true, NULL);
1585
1586   /* The same, but with initial value zero.  */
1587   add_candidate (data,
1588                  build_int_cst (TREE_TYPE (iv->base), 0),
1589                  iv->step, true, NULL);
1590
1591   phi = SSA_NAME_DEF_STMT (iv->ssa_name);
1592   if (TREE_CODE (phi) == PHI_NODE)
1593     {
1594       /* Additionally record the possibility of leaving the original iv
1595          untouched.  */
1596       def = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (data->current_loop));
1597       cand = add_candidate_1 (data,
1598                               iv->base, iv->step, true, IP_ORIGINAL, NULL,
1599                               SSA_NAME_DEF_STMT (def));
1600       cand->var_before = iv->ssa_name;
1601       cand->var_after = def;
1602     }
1603 }
1604
1605 /* Adds candidates based on the old induction variables.  */
1606
1607 static void
1608 add_old_ivs_candidates (struct ivopts_data *data)
1609 {
1610   unsigned i;
1611   struct iv *iv;
1612
1613   EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i,
1614     {
1615       iv = ver_info (data, i)->iv;
1616       if (iv && iv->biv_p && !zero_p (iv->step))
1617         add_old_iv_candidates (data, iv);
1618     });
1619 }
1620
1621 /* Adds candidates based on the value of the induction variable IV and USE.  */
1622
1623 static void
1624 add_iv_value_candidates (struct ivopts_data *data,
1625                          struct iv *iv, struct iv_use *use)
1626 {
1627   add_candidate (data, iv->base, iv->step, false, use);
1628
1629   /* The same, but with initial value zero.  */
1630   add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
1631                  iv->step, false, use);
1632 }
1633
1634 /* Adds candidates based on the address IV and USE.  */
1635
1636 static void
1637 add_address_candidates (struct ivopts_data *data,
1638                         struct iv *iv, struct iv_use *use)
1639 {
1640   tree base, abase, tmp, *act;
1641
1642   /* First, the trivial choices.  */
1643   add_iv_value_candidates (data, iv, use);
1644
1645   /* Second, try removing the COMPONENT_REFs.  */
1646   if (TREE_CODE (iv->base) == ADDR_EXPR)
1647     {
1648       base = TREE_OPERAND (iv->base, 0);
1649       while (TREE_CODE (base) == COMPONENT_REF
1650              || (TREE_CODE (base) == ARRAY_REF
1651                  && TREE_CODE (TREE_OPERAND (base, 1)) == INTEGER_CST))
1652         base = TREE_OPERAND (base, 0);
1653
1654       if (base != TREE_OPERAND (iv->base, 0))
1655         { 
1656           if (TREE_CODE (base) == INDIRECT_REF)
1657             base = TREE_OPERAND (base, 0);
1658           else
1659             base = build_addr (base);
1660           add_candidate (data, base, iv->step, false, use);
1661         }
1662     }
1663
1664   /* Third, try removing the constant offset.  */
1665   abase = iv->base;
1666   while (TREE_CODE (abase) == PLUS_EXPR
1667          && TREE_CODE (TREE_OPERAND (abase, 1)) != INTEGER_CST)
1668     abase = TREE_OPERAND (abase, 0);
1669   /* We found the offset, so make the copy of the non-shared part and
1670      remove it.  */
1671   if (TREE_CODE (abase) == PLUS_EXPR)
1672     {
1673       tmp = iv->base;
1674       act = &base;
1675
1676       for (tmp = iv->base; tmp != abase; tmp = TREE_OPERAND (tmp, 0))
1677         {
1678           *act = build2 (PLUS_EXPR, TREE_TYPE (tmp),
1679                          NULL_TREE, TREE_OPERAND (tmp, 1));
1680           act = &TREE_OPERAND (*act, 0);
1681         }
1682       *act = TREE_OPERAND (tmp, 0);
1683
1684       add_candidate (data, base, iv->step, false, use);
1685     }
1686 }
1687
1688 /* Possibly adds pseudocandidate for replacing the final value of USE by
1689    a direct computation.  */
1690
1691 static void
1692 add_iv_outer_candidates (struct ivopts_data *data, struct iv_use *use)
1693 {
1694   struct tree_niter_desc *niter;
1695   struct loop *loop = data->current_loop;
1696
1697   /* We must know where we exit the loop and how many times does it roll.  */
1698   if (!single_dom_exit (loop))
1699     return;
1700
1701   niter = &loop_data (loop)->niter;
1702   if (!niter->niter
1703       || !operand_equal_p (niter->assumptions, boolean_true_node, 0)
1704       || !operand_equal_p (niter->may_be_zero, boolean_false_node, 0))
1705     return;
1706
1707   add_candidate_1 (data, NULL, NULL, false, IP_NORMAL, use, NULL_TREE);
1708 }
1709
1710 /* Adds candidates based on the uses.  */
1711
1712 static void
1713 add_derived_ivs_candidates (struct ivopts_data *data)
1714 {
1715   unsigned i;
1716
1717   for (i = 0; i < n_iv_uses (data); i++)
1718     {
1719       struct iv_use *use = iv_use (data, i);
1720
1721       if (!use)
1722         continue;
1723
1724       switch (use->type)
1725         {
1726         case USE_NONLINEAR_EXPR:
1727         case USE_COMPARE:
1728           /* Just add the ivs based on the value of the iv used here.  */
1729           add_iv_value_candidates (data, use->iv, use);
1730           break;
1731
1732         case USE_OUTER:
1733           add_iv_value_candidates (data, use->iv, use);
1734
1735           /* Additionally, add the pseudocandidate for the possibility to
1736              replace the final value by a direct computation.  */
1737           add_iv_outer_candidates (data, use);
1738           break;
1739
1740         case USE_ADDRESS:
1741           add_address_candidates (data, use->iv, use);
1742           break;
1743
1744         default:
1745           abort ();
1746         }
1747     }
1748 }
1749
1750 /* Finds the candidates for the induction variables.  */
1751
1752 static void
1753 find_iv_candidates (struct ivopts_data *data)
1754 {
1755   /* Add commonly used ivs.  */
1756   add_standard_iv_candidates (data);
1757
1758   /* Add old induction variables.  */
1759   add_old_ivs_candidates (data);
1760
1761   /* Add induction variables derived from uses.  */
1762   add_derived_ivs_candidates (data);
1763 }
1764
1765 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
1766    If consider_all_candidates is true, we use a two-dimensional array, otherwise
1767    we allocate a simple list to every use.  */
1768
1769 static void
1770 alloc_use_cost_map (struct ivopts_data *data)
1771 {
1772   unsigned i, n_imp = 0, size, j;
1773
1774   if (!data->consider_all_candidates)
1775     {
1776       for (i = 0; i < n_iv_cands (data); i++)
1777         {
1778           struct iv_cand *cand = iv_cand (data, i);
1779           if (cand->important)
1780             n_imp++;
1781         }
1782     }
1783
1784   for (i = 0; i < n_iv_uses (data); i++)
1785     {
1786       struct iv_use *use = iv_use (data, i);
1787
1788       if (data->consider_all_candidates)
1789         {
1790           size = n_iv_cands (data);
1791           use->n_map_members = size;
1792         }
1793       else
1794         {
1795           size = n_imp;
1796           EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, size++);
1797           use->n_map_members = 0;
1798         }
1799
1800       use->cost_map = xcalloc (size, sizeof (struct cost_pair));
1801     }
1802 }
1803
1804 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
1805    on invariants DEPENDS_ON.  */
1806
1807 static void
1808 set_use_iv_cost (struct ivopts_data *data,
1809                  struct iv_use *use, struct iv_cand *cand, unsigned cost,
1810                  bitmap depends_on)
1811 {
1812   if (cost == INFTY
1813       && depends_on)
1814     {
1815       BITMAP_XFREE (depends_on);
1816       depends_on = NULL;
1817     }
1818
1819   if (data->consider_all_candidates)
1820     {
1821       use->cost_map[cand->id].cand = cand;
1822       use->cost_map[cand->id].cost = cost;
1823       use->cost_map[cand->id].depends_on = depends_on;
1824       return;
1825     }
1826
1827   if (cost == INFTY)
1828     return;
1829
1830   use->cost_map[use->n_map_members].cand = cand;
1831   use->cost_map[use->n_map_members].cost = cost;
1832   use->cost_map[use->n_map_members].depends_on = depends_on;
1833   use->n_map_members++;
1834 }
1835
1836 /* Gets cost of (USE, CANDIDATE) pair.  Stores the bitmap of dependencies to
1837    DEPENDS_ON.  */
1838
1839 static unsigned
1840 get_use_iv_cost (struct ivopts_data *data,
1841                  struct iv_use *use, struct iv_cand *cand, bitmap *depends_on)
1842 {
1843   unsigned i;
1844
1845   if (!cand)
1846     return INFTY;
1847
1848   if (data->consider_all_candidates)
1849     i = cand->id;
1850   else
1851     {
1852       for (i = 0; i < use->n_map_members; i++)
1853         if (use->cost_map[i].cand == cand)
1854           break;
1855
1856       if (i == use->n_map_members)
1857         return INFTY;
1858     }
1859
1860   if (depends_on)
1861     *depends_on = use->cost_map[i].depends_on;
1862   return use->cost_map[i].cost;
1863 }
1864
1865 /* Returns estimate on cost of computing SEQ.  */
1866
1867 static unsigned
1868 seq_cost (rtx seq)
1869 {
1870   unsigned cost = 0;
1871   rtx set;
1872
1873   for (; seq; seq = NEXT_INSN (seq))
1874     {
1875       set = single_set (seq);
1876       if (set)
1877         cost += rtx_cost (set, SET);
1878       else
1879         cost++;
1880     }
1881
1882   return cost;
1883 }
1884
1885 /* Produce DECL_RTL for object obj so it looks like it is stored in memory.  */
1886 static rtx
1887 produce_memory_decl_rtl (tree obj, int *regno)
1888 {
1889   rtx x;
1890   if (!obj)
1891     abort ();
1892   if (TREE_STATIC (obj) || DECL_EXTERNAL (obj))
1893     {
1894       const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj));
1895       x = gen_rtx_SYMBOL_REF (Pmode, name);
1896     }
1897   else
1898     x = gen_raw_REG (Pmode, (*regno)++);
1899
1900   return gen_rtx_MEM (DECL_MODE (obj), x);
1901 }
1902
1903 /* Prepares decl_rtl for variables referred in *EXPR_P.  Callback for
1904    walk_tree.  DATA contains the actual fake register number.  */
1905
1906 static tree
1907 prepare_decl_rtl (tree *expr_p, int *ws, void *data)
1908 {
1909   tree obj = NULL_TREE;
1910   rtx x = NULL_RTX;
1911   int *regno = data;
1912
1913   switch (TREE_CODE (*expr_p))
1914     {
1915     case ADDR_EXPR:
1916       for (expr_p = &TREE_OPERAND (*expr_p, 0);
1917            (handled_component_p (*expr_p)
1918             || TREE_CODE (*expr_p) == REALPART_EXPR
1919             || TREE_CODE (*expr_p) == IMAGPART_EXPR);
1920            expr_p = &TREE_OPERAND (*expr_p, 0));
1921       obj = *expr_p;
1922       if (DECL_P (obj))
1923         x = produce_memory_decl_rtl (obj, regno);
1924       break;
1925
1926     case SSA_NAME:
1927       *ws = 0;
1928       obj = SSA_NAME_VAR (*expr_p);
1929       if (!DECL_RTL_SET_P (obj))
1930         x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
1931       break;
1932
1933     case VAR_DECL:
1934     case PARM_DECL:
1935     case RESULT_DECL:
1936       *ws = 0;
1937       obj = *expr_p;
1938
1939       if (DECL_RTL_SET_P (obj))
1940         break;
1941
1942       if (DECL_MODE (obj) == BLKmode)
1943         x = produce_memory_decl_rtl (obj, regno);
1944       else
1945         x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
1946
1947       break;
1948
1949     default:
1950       break;
1951     }
1952
1953   if (x)
1954     {
1955       VARRAY_PUSH_GENERIC_PTR_NOGC (decl_rtl_to_reset, obj);
1956       SET_DECL_RTL (obj, x);
1957     }
1958
1959   return NULL_TREE;
1960 }
1961
1962 /* Determines cost of the computation of EXPR.  */
1963
1964 static unsigned
1965 computation_cost (tree expr)
1966 {
1967   rtx seq, rslt;
1968   tree type = TREE_TYPE (expr);
1969   unsigned cost;
1970   int regno = 0;
1971
1972   walk_tree (&expr, prepare_decl_rtl, &regno, NULL);
1973   start_sequence ();
1974   rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL);
1975   seq = get_insns ();
1976   end_sequence ();
1977
1978   cost = seq_cost (seq);
1979   if (GET_CODE (rslt) == MEM)
1980     cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type));
1981
1982   return cost;
1983 }
1984
1985 /* Returns variable containing the value of candidate CAND at statement AT.  */
1986
1987 static tree
1988 var_at_stmt (struct loop *loop, struct iv_cand *cand, tree stmt)
1989 {
1990   if (stmt_after_increment (loop, cand, stmt))
1991     return cand->var_after;
1992   else
1993     return cand->var_before;
1994 }
1995
1996 /* Determines the expression by that USE is expressed from induction variable
1997    CAND at statement AT in LOOP.  */
1998
1999 static tree
2000 get_computation_at (struct loop *loop,
2001                     struct iv_use *use, struct iv_cand *cand, tree at)
2002 {
2003   tree ubase = unsave_expr_now (use->iv->base);
2004   tree ustep = unsave_expr_now (use->iv->step);
2005   tree cbase = unsave_expr_now (cand->iv->base);
2006   tree cstep = unsave_expr_now (cand->iv->step);
2007   tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
2008   tree uutype;
2009   tree expr, delta;
2010   tree ratio;
2011   unsigned HOST_WIDE_INT ustepi, cstepi;
2012   HOST_WIDE_INT ratioi;
2013
2014   if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
2015     {
2016       /* We do not have a precision to express the values of use.  */
2017       return NULL_TREE;
2018     }
2019
2020   expr = var_at_stmt (loop, cand, at);
2021
2022   if (TREE_TYPE (expr) != ctype)
2023     {
2024       /* This may happen with the original ivs.  */
2025       expr = fold_convert (ctype, expr);
2026     }
2027
2028   if (TYPE_UNSIGNED (utype))
2029     uutype = utype;
2030   else
2031     {
2032       uutype = unsigned_type_for (utype);
2033       ubase = fold_convert (uutype, ubase);
2034       ustep = fold_convert (uutype, ustep);
2035     }
2036
2037   if (uutype != ctype)
2038     {
2039       expr = fold_convert (uutype, expr);
2040       cbase = fold_convert (uutype, cbase);
2041       cstep = fold_convert (uutype, cstep);
2042     }
2043
2044   if (!cst_and_fits_in_hwi (cstep)
2045       || !cst_and_fits_in_hwi (ustep))
2046     return NULL_TREE;
2047
2048   ustepi = int_cst_value (ustep);
2049   cstepi = int_cst_value (cstep);
2050
2051   if (!divide (TYPE_PRECISION (uutype), ustepi, cstepi, &ratioi))
2052     {
2053       /* TODO maybe consider case when ustep divides cstep and the ratio is
2054          a power of 2 (so that the division is fast to execute)?  We would
2055          need to be much more careful with overflows etc. then.  */
2056       return NULL_TREE;
2057     }
2058
2059   /* We may need to shift the value if we are after the increment.  */
2060   if (stmt_after_increment (loop, cand, at))
2061     cbase = fold (build2 (PLUS_EXPR, uutype, cbase, cstep));
2062
2063   /* use = ubase + ratio * (var - cbase).  If either cbase is a constant
2064      or |ratio| == 1, it is better to handle this like
2065      
2066      ubase - ratio * cbase + ratio * var.  */
2067
2068   if (ratioi == 1)
2069     {
2070       delta = fold (build2 (MINUS_EXPR, uutype, ubase, cbase));
2071       expr = fold (build2 (PLUS_EXPR, uutype, expr, delta));
2072     }
2073   else if (ratioi == -1)
2074     {
2075       delta = fold (build2 (PLUS_EXPR, uutype, ubase, cbase));
2076       expr = fold (build2 (MINUS_EXPR, uutype, delta, expr));
2077     }
2078   else if (TREE_CODE (cbase) == INTEGER_CST)
2079     {
2080       ratio = build_int_cst_type (uutype, ratioi);
2081       delta = fold (build2 (MULT_EXPR, uutype, ratio, cbase));
2082       delta = fold (build2 (MINUS_EXPR, uutype, ubase, delta));
2083       expr = fold (build2 (MULT_EXPR, uutype, ratio, expr));
2084       expr = fold (build2 (PLUS_EXPR, uutype, delta, expr));
2085     }
2086   else
2087     {
2088       expr = fold (build2 (MINUS_EXPR, uutype, expr, cbase));
2089       ratio = build_int_cst_type (uutype, ratioi);
2090       expr = fold (build2 (MULT_EXPR, uutype, ratio, expr));
2091       expr = fold (build2 (PLUS_EXPR, uutype, ubase, expr));
2092     }
2093
2094   return fold_convert (utype, expr);
2095 }
2096
2097 /* Determines the expression by that USE is expressed from induction variable
2098    CAND in LOOP.  */
2099
2100 static tree
2101 get_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand)
2102 {
2103   return get_computation_at (loop, use, cand, use->stmt);
2104 }
2105
2106 /* Strips constant offsets from EXPR and adds them to OFFSET.  */
2107
2108 static void
2109 strip_offset (tree *expr, unsigned HOST_WIDE_INT *offset)
2110 {
2111   tree op0, op1;
2112   enum tree_code code;
2113   
2114   while (1)
2115     {
2116       if (cst_and_fits_in_hwi (*expr))
2117         {
2118           *offset += int_cst_value (*expr);
2119           *expr = integer_zero_node;
2120           return;
2121         }
2122
2123       code = TREE_CODE (*expr);
2124      
2125       if (code != PLUS_EXPR && code != MINUS_EXPR)
2126         return;
2127
2128       op0 = TREE_OPERAND (*expr, 0);
2129       op1 = TREE_OPERAND (*expr, 1);
2130
2131       if (cst_and_fits_in_hwi (op1))
2132         {
2133           if (code == PLUS_EXPR)
2134             *offset += int_cst_value (op1);
2135           else
2136             *offset -= int_cst_value (op1);
2137
2138           *expr = op0;
2139           continue;
2140         }
2141
2142       if (code != PLUS_EXPR)
2143         return;
2144
2145       if (!cst_and_fits_in_hwi (op0))
2146         return;
2147
2148       *offset += int_cst_value (op0);
2149       *expr = op1;
2150     }
2151 }
2152
2153 /* Returns cost of addition in MODE.  */
2154
2155 static unsigned
2156 add_cost (enum machine_mode mode)
2157 {
2158   static unsigned costs[NUM_MACHINE_MODES];
2159   rtx seq;
2160   unsigned cost;
2161
2162   if (costs[mode])
2163     return costs[mode];
2164
2165   start_sequence ();
2166   force_operand (gen_rtx_fmt_ee (PLUS, mode,
2167                                  gen_raw_REG (mode, FIRST_PSEUDO_REGISTER),
2168                                  gen_raw_REG (mode, FIRST_PSEUDO_REGISTER + 1)),
2169                  NULL_RTX);
2170   seq = get_insns ();
2171   end_sequence ();
2172
2173   cost = seq_cost (seq);
2174   if (!cost)
2175     cost = 1;
2176
2177   costs[mode] = cost;
2178       
2179   if (dump_file && (dump_flags & TDF_DETAILS))
2180     fprintf (dump_file, "Addition in %s costs %d\n",
2181              GET_MODE_NAME (mode), cost);
2182   return cost;
2183 }
2184
2185 /* Entry in a hashtable of already known costs for multiplication.  */
2186 struct mbc_entry
2187 {
2188   HOST_WIDE_INT cst;            /* The constant to multiply by.  */
2189   enum machine_mode mode;       /* In mode.  */
2190   unsigned cost;                /* The cost.  */
2191 };
2192
2193 /* Counts hash value for the ENTRY.  */
2194
2195 static hashval_t
2196 mbc_entry_hash (const void *entry)
2197 {
2198   const struct mbc_entry *e = entry;
2199
2200   return 57 * (hashval_t) e->mode + (hashval_t) (e->cst % 877);
2201 }
2202
2203 /* Compares the hash table entries ENTRY1 and ENTRY2.  */
2204
2205 static int
2206 mbc_entry_eq (const void *entry1, const void *entry2)
2207 {
2208   const struct mbc_entry *e1 = entry1;
2209   const struct mbc_entry *e2 = entry2;
2210
2211   return (e1->mode == e2->mode
2212           && e1->cst == e2->cst);
2213 }
2214
2215 /* Returns cost of multiplication by constant CST in MODE.  */
2216
2217 static unsigned
2218 multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode)
2219 {
2220   static htab_t costs;
2221   struct mbc_entry **cached, act;
2222   rtx seq;
2223   unsigned cost;
2224
2225   if (!costs)
2226     costs = htab_create (100, mbc_entry_hash, mbc_entry_eq, free);
2227
2228   act.mode = mode;
2229   act.cst = cst;
2230   cached = (struct mbc_entry **) htab_find_slot (costs, &act, INSERT);
2231   if (*cached)
2232     return (*cached)->cost;
2233
2234   *cached = xmalloc (sizeof (struct mbc_entry));
2235   (*cached)->mode = mode;
2236   (*cached)->cst = cst;
2237
2238   start_sequence ();
2239   expand_mult (mode, gen_raw_REG (mode, FIRST_PSEUDO_REGISTER), GEN_INT (cst),
2240                NULL_RTX, 0);
2241   seq = get_insns ();
2242   end_sequence ();
2243   
2244   cost = seq_cost (seq);
2245
2246   if (dump_file && (dump_flags & TDF_DETAILS))
2247     fprintf (dump_file, "Multiplication by %d in %s costs %d\n",
2248              (int) cst, GET_MODE_NAME (mode), cost);
2249
2250   (*cached)->cost = cost;
2251
2252   return cost;
2253 }
2254
2255 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
2256    If SYMBOL_PRESENT is false, symbol is omitted.  If VAR_PRESENT is false,
2257    variable is omitted.  The created memory accesses MODE.
2258    
2259    TODO -- there must be some better way.  This all is quite crude.  */
2260
2261 static unsigned
2262 get_address_cost (bool symbol_present, bool var_present,
2263                   unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio)
2264 {
2265 #define MAX_RATIO 128
2266   static sbitmap valid_mult;
2267   static HOST_WIDE_INT rat, off;
2268   static HOST_WIDE_INT min_offset, max_offset;
2269   static unsigned costs[2][2][2][2];
2270   unsigned cost, acost;
2271   rtx seq, addr, base;
2272   bool offset_p, ratio_p;
2273   rtx reg1;
2274   HOST_WIDE_INT s_offset;
2275   unsigned HOST_WIDE_INT mask;
2276   unsigned bits;
2277
2278   if (!valid_mult)
2279     {
2280       HOST_WIDE_INT i;
2281
2282       reg1 = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER);
2283
2284       addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
2285       for (i = 1; i <= 1 << 20; i <<= 1)
2286         {
2287           XEXP (addr, 1) = GEN_INT (i);
2288           if (!memory_address_p (Pmode, addr))
2289             break;
2290         }
2291       max_offset = i >> 1;
2292       off = max_offset;
2293
2294       for (i = 1; i <= 1 << 20; i <<= 1)
2295         {
2296           XEXP (addr, 1) = GEN_INT (-i);
2297           if (!memory_address_p (Pmode, addr))
2298             break;
2299         }
2300       min_offset = -(i >> 1);
2301
2302       if (dump_file && (dump_flags & TDF_DETAILS))
2303         {
2304           fprintf (dump_file, "get_address_cost:\n");
2305           fprintf (dump_file, "  min offset %d\n", (int) min_offset);
2306           fprintf (dump_file, "  max offset %d\n", (int) max_offset);
2307         }
2308
2309       valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1);
2310       sbitmap_zero (valid_mult);
2311       rat = 1;
2312       addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX);
2313       for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
2314         {
2315           XEXP (addr, 1) = GEN_INT (i);
2316           if (memory_address_p (Pmode, addr))
2317             {
2318               SET_BIT (valid_mult, i + MAX_RATIO);
2319               rat = i;
2320             }
2321         }
2322
2323       if (dump_file && (dump_flags & TDF_DETAILS))
2324         {
2325           fprintf (dump_file, "  allowed multipliers:");
2326           for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
2327             if (TEST_BIT (valid_mult, i + MAX_RATIO))
2328               fprintf (dump_file, " %d", (int) i);
2329           fprintf (dump_file, "\n");
2330           fprintf (dump_file, "\n");
2331         }
2332     }
2333
2334   bits = GET_MODE_BITSIZE (Pmode);
2335   mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
2336   offset &= mask;
2337   if ((offset >> (bits - 1) & 1))
2338     offset |= ~mask;
2339   s_offset = offset;
2340
2341   cost = 0;
2342   offset_p = (min_offset <= s_offset && s_offset <= max_offset);
2343   ratio_p = (ratio != 1
2344              && -MAX_RATIO <= ratio && ratio <= MAX_RATIO
2345              && TEST_BIT (valid_mult, ratio + MAX_RATIO));
2346
2347   if (ratio != 1 && !ratio_p)
2348     cost += multiply_by_cost (ratio, Pmode);
2349
2350   if (s_offset && !offset_p && !symbol_present)
2351     {
2352       cost += add_cost (Pmode);
2353       var_present = true;
2354     }
2355
2356   acost = costs[symbol_present][var_present][offset_p][ratio_p];
2357   if (!acost)
2358     {
2359       acost = 0;
2360       
2361       addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER);
2362       reg1 = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 1);
2363       if (ratio_p)
2364         addr = gen_rtx_fmt_ee (MULT, Pmode, addr, GEN_INT (rat));
2365
2366       if (symbol_present)
2367         {
2368           base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
2369           if (offset_p)
2370             base = gen_rtx_fmt_e (CONST, Pmode,
2371                                   gen_rtx_fmt_ee (PLUS, Pmode,
2372                                                   base,
2373                                                   GEN_INT (off)));
2374           if (var_present)
2375             base = gen_rtx_fmt_ee (PLUS, Pmode, reg1, base);
2376         }
2377
2378       else if (var_present)
2379         {
2380           base = reg1;
2381           if (offset_p)
2382             base = gen_rtx_fmt_ee (PLUS, Pmode, base, GEN_INT (off));
2383         }
2384       else if (offset_p)
2385         base = GEN_INT (off);
2386       else
2387         base = NULL_RTX;
2388     
2389       if (base)
2390         addr = gen_rtx_fmt_ee (PLUS, Pmode, base, addr);
2391   
2392       start_sequence ();
2393       addr = memory_address (Pmode, addr);
2394       seq = get_insns ();
2395       end_sequence ();
2396   
2397       acost = seq_cost (seq);
2398       acost += address_cost (addr, Pmode);
2399
2400       if (!acost)
2401         acost = 1;
2402       costs[symbol_present][var_present][offset_p][ratio_p] = acost;
2403     }
2404
2405   return cost + acost;
2406 }
2407
2408 /* Records invariants in *EXPR_P.  Callback for walk_tree.  DATA contains
2409    the bitmap to that we should store it.  */
2410
2411 static struct ivopts_data *fd_ivopts_data;
2412 static tree
2413 find_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
2414 {
2415   bitmap *depends_on = data;
2416   struct version_info *info;
2417
2418   if (TREE_CODE (*expr_p) != SSA_NAME)
2419     return NULL_TREE;
2420   info = name_info (fd_ivopts_data, *expr_p);
2421
2422   if (!info->inv_id || info->has_nonlin_use)
2423     return NULL_TREE;
2424
2425   if (!*depends_on)
2426     *depends_on = BITMAP_XMALLOC ();
2427   bitmap_set_bit (*depends_on, info->inv_id);
2428
2429   return NULL_TREE;
2430 }
2431
2432 /* Estimates cost of forcing EXPR into variable.  DEPENDS_ON is a set of the
2433    invariants the computation depends on.  */
2434
2435 static unsigned
2436 force_var_cost (struct ivopts_data *data,
2437                 tree expr, bitmap *depends_on)
2438 {
2439   static bool costs_initialized = false;
2440   static unsigned integer_cost;
2441   static unsigned symbol_cost;
2442   static unsigned address_cost;
2443
2444   if (!costs_initialized)
2445     {
2446       tree var = create_tmp_var_raw (integer_type_node, "test_var");
2447       rtx x = gen_rtx_MEM (DECL_MODE (var),
2448                            gen_rtx_SYMBOL_REF (Pmode, "test_var"));
2449       tree addr;
2450       tree type = build_pointer_type (integer_type_node);
2451
2452       integer_cost = computation_cost (build_int_cst_type (integer_type_node,
2453                                                            2000));
2454
2455       SET_DECL_RTL (var, x);
2456       TREE_STATIC (var) = 1;
2457       addr = build1 (ADDR_EXPR, type, var);
2458       symbol_cost = computation_cost (addr) + 1;
2459
2460       address_cost
2461         = computation_cost (build2 (PLUS_EXPR, type,
2462                                     addr,
2463                                     build_int_cst_type (type, 2000))) + 1;
2464       if (dump_file && (dump_flags & TDF_DETAILS))
2465         {
2466           fprintf (dump_file, "force_var_cost:\n");
2467           fprintf (dump_file, "  integer %d\n", (int) integer_cost);
2468           fprintf (dump_file, "  symbol %d\n", (int) symbol_cost);
2469           fprintf (dump_file, "  address %d\n", (int) address_cost);
2470           fprintf (dump_file, "  other %d\n", (int) target_spill_cost);
2471           fprintf (dump_file, "\n");
2472         }
2473
2474       costs_initialized = true;
2475     }
2476
2477   if (depends_on)
2478     {
2479       fd_ivopts_data = data;
2480       walk_tree (&expr, find_depends, depends_on, NULL);
2481     }
2482
2483   if (SSA_VAR_P (expr))
2484     return 0;
2485
2486   if (TREE_INVARIANT (expr))
2487     {
2488       if (TREE_CODE (expr) == INTEGER_CST)
2489         return integer_cost;
2490
2491       if (TREE_CODE (expr) == ADDR_EXPR)
2492         {
2493           tree obj = TREE_OPERAND (expr, 0);
2494
2495           if (TREE_CODE (obj) == VAR_DECL
2496               || TREE_CODE (obj) == PARM_DECL
2497               || TREE_CODE (obj) == RESULT_DECL)
2498             return symbol_cost;
2499         }
2500
2501       return address_cost;
2502     }
2503
2504   /* Just an arbitrary value, FIXME.  */
2505   return target_spill_cost;
2506 }
2507
2508 /* Peels a single layer of ADDR.  If DIFF is not NULL, do it only if the
2509    offset is constant and add the offset to DIFF.  */
2510
2511 static tree
2512 peel_address (tree addr, unsigned HOST_WIDE_INT *diff)
2513 {
2514   tree off, size;
2515   HOST_WIDE_INT bit_offset;
2516
2517   switch (TREE_CODE (addr))
2518     {
2519     case SSA_NAME:
2520     case INDIRECT_REF:
2521     case BIT_FIELD_REF:
2522     case VAR_DECL:
2523     case PARM_DECL:
2524     case RESULT_DECL:
2525     case STRING_CST:
2526     case REALPART_EXPR:
2527     case IMAGPART_EXPR:
2528       return NULL_TREE;
2529
2530     case COMPONENT_REF:
2531       off = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (addr, 1));
2532       bit_offset = TREE_INT_CST_LOW (off);
2533
2534       if (bit_offset % BITS_PER_UNIT)
2535         abort ();
2536       
2537       if (diff)
2538         *diff += bit_offset / BITS_PER_UNIT;
2539
2540       return TREE_OPERAND (addr, 0);
2541
2542     case ARRAY_REF:
2543       off = TREE_OPERAND (addr, 1);
2544
2545       if (diff)
2546         {
2547           if (!cst_and_fits_in_hwi (off))
2548             return NULL_TREE;
2549
2550           size = TYPE_SIZE_UNIT (TREE_TYPE (addr));
2551           if (!cst_and_fits_in_hwi (size))
2552             return NULL_TREE;
2553
2554           *diff += TREE_INT_CST_LOW (off) * TREE_INT_CST_LOW (size);
2555         }
2556
2557       return TREE_OPERAND (addr, 0);
2558
2559     default:
2560       abort ();
2561     }
2562 }
2563
2564 /* Checks whether E1 and E2 have constant difference, and if they do,
2565    store it in *DIFF.  */
2566
2567 static bool
2568 ptr_difference_const (tree e1, tree e2, unsigned HOST_WIDE_INT *diff)
2569 {
2570   int d1 = 0, d2 = 0;
2571   tree x;
2572   unsigned HOST_WIDE_INT delta1 = 0, delta2 = 0;
2573
2574   /* Find depths of E1 and E2.  */
2575   for (x = e1; x; x = peel_address (x, NULL))
2576     d1++;
2577   for (x = e2; x; x = peel_address (x, NULL))
2578     d2++;
2579
2580   for (; e1 && d1 > d2; e1 = peel_address (e1, &delta1))
2581     d1--;
2582   for (; e2 && d2 > d1; e2 = peel_address (e2, &delta2))
2583     d2--;
2584
2585   while (e1 && e2 && !operand_equal_p (e1, e2, 0))
2586     {
2587       e1 = peel_address (e1, &delta1);
2588       e2 = peel_address (e2, &delta1);
2589     }
2590
2591   if (!e1 || !e2)
2592     return false;
2593
2594   *diff = delta1 - delta2;
2595   return true;
2596 }
2597
2598 /* Estimates cost of expressing address ADDR  as var + symbol + offset.  The
2599    value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
2600    to false if the corresponding part is missing.  DEPENDS_ON is a set of the
2601    invariants the computation depends on.  */
2602
2603 static unsigned
2604 split_address_cost (struct ivopts_data *data,
2605                     tree addr, bool *symbol_present, bool *var_present,
2606                     unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
2607 {
2608   tree core = addr;
2609
2610   while (core
2611          && TREE_CODE (core) != VAR_DECL)
2612     core = peel_address (core, offset);
2613
2614   if (!core)
2615     {
2616       *symbol_present = false;
2617       *var_present = true;
2618       fd_ivopts_data = data;
2619       walk_tree (&addr, find_depends, depends_on, NULL);
2620       return target_spill_cost;
2621     }  
2622           
2623   if (TREE_STATIC (core)
2624       || DECL_EXTERNAL (core))
2625     {
2626       *symbol_present = true;
2627       *var_present = false;
2628       return 0;
2629     }
2630       
2631   *symbol_present = false;
2632   *var_present = true;
2633   return 0;
2634 }
2635
2636 /* Estimates cost of expressing difference of addresses E1 - E2 as
2637    var + symbol + offset.  The value of offset is added to OFFSET,
2638    SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
2639    part is missing.  DEPENDS_ON is a set of the invariants the computation
2640    depends on.  */
2641
2642 static unsigned
2643 ptr_difference_cost (struct ivopts_data *data,
2644                      tree e1, tree e2, bool *symbol_present, bool *var_present,
2645                      unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
2646 {
2647   unsigned HOST_WIDE_INT diff = 0;
2648   unsigned cost;
2649
2650   if (TREE_CODE (e1) != ADDR_EXPR)
2651     abort ();
2652
2653   if (TREE_CODE (e2) == ADDR_EXPR
2654       && ptr_difference_const (TREE_OPERAND (e1, 0),
2655                                TREE_OPERAND (e2, 0), &diff))
2656     {
2657       *offset += diff;
2658       *symbol_present = false;
2659       *var_present = false;
2660       return 0;
2661     }
2662
2663   if (e2 == integer_zero_node)
2664     return split_address_cost (data, TREE_OPERAND (e1, 0),
2665                                symbol_present, var_present, offset, depends_on);
2666
2667   *symbol_present = false;
2668   *var_present = true;
2669   
2670   cost = force_var_cost (data, e1, depends_on);
2671   cost += force_var_cost (data, e2, depends_on);
2672   cost += add_cost (Pmode);
2673
2674   return cost;
2675 }
2676
2677 /* Estimates cost of expressing difference E1 - E2 as
2678    var + symbol + offset.  The value of offset is added to OFFSET,
2679    SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
2680    part is missing.  DEPENDS_ON is a set of the invariants the computation
2681    depends on.  */
2682
2683 static unsigned
2684 difference_cost (struct ivopts_data *data,
2685                  tree e1, tree e2, bool *symbol_present, bool *var_present,
2686                  unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
2687 {
2688   unsigned cost;
2689   enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
2690
2691   strip_offset (&e1, offset);
2692   *offset = -*offset;
2693   strip_offset (&e2, offset);
2694   *offset = -*offset;
2695
2696   if (TREE_CODE (e1) == ADDR_EXPR)
2697     return ptr_difference_cost (data, e1, e2, symbol_present, var_present, offset,
2698                                 depends_on);
2699   *symbol_present = false;
2700
2701   if (operand_equal_p (e1, e2, 0))
2702     {
2703       *var_present = false;
2704       return 0;
2705     }
2706   *var_present = true;
2707   if (zero_p (e2))
2708     return force_var_cost (data, e1, depends_on);
2709
2710   if (zero_p (e1))
2711     {
2712       cost = force_var_cost (data, e2, depends_on);
2713       cost += multiply_by_cost (-1, mode);
2714
2715       return cost;
2716     }
2717
2718   cost = force_var_cost (data, e1, depends_on);
2719   cost += force_var_cost (data, e2, depends_on);
2720   cost += add_cost (mode);
2721
2722   return cost;
2723 }
2724
2725 /* Determines the cost of the computation by that USE is expressed
2726    from induction variable CAND.  If ADDRESS_P is true, we just need
2727    to create an address from it, otherwise we want to get it into
2728    register.  A set of invariants we depend on is stored in
2729    DEPENDS_ON.  AT is the statement at that the value is computed.  */
2730
2731 static unsigned
2732 get_computation_cost_at (struct ivopts_data *data,
2733                          struct iv_use *use, struct iv_cand *cand,
2734                          bool address_p, bitmap *depends_on, tree at)
2735 {
2736   tree ubase = use->iv->base, ustep = use->iv->step;
2737   tree cbase, cstep;
2738   tree utype = TREE_TYPE (ubase), ctype;
2739   unsigned HOST_WIDE_INT ustepi, cstepi, offset = 0;
2740   HOST_WIDE_INT ratio, aratio;
2741   bool var_present, symbol_present;
2742   unsigned cost = 0, n_sums;
2743
2744   *depends_on = NULL;
2745
2746   /* Only consider real candidates.  */
2747   if (!cand->iv)
2748     return INFTY;
2749
2750   cbase = cand->iv->base;
2751   cstep = cand->iv->step;
2752   ctype = TREE_TYPE (cbase);
2753
2754   if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
2755     {
2756       /* We do not have a precision to express the values of use.  */
2757       return INFTY;
2758     }
2759
2760   if (!cst_and_fits_in_hwi (ustep)
2761       || !cst_and_fits_in_hwi (cstep))
2762     return INFTY;
2763
2764   if (TREE_CODE (ubase) == INTEGER_CST
2765       && !cst_and_fits_in_hwi (ubase))
2766     goto fallback;
2767
2768   if (TREE_CODE (cbase) == INTEGER_CST
2769       && !cst_and_fits_in_hwi (cbase))
2770     goto fallback;
2771     
2772   ustepi = int_cst_value (ustep);
2773   cstepi = int_cst_value (cstep);
2774
2775   if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
2776     {
2777       /* TODO -- add direct handling of this case.  */
2778       goto fallback;
2779     }
2780
2781   if (!divide (TYPE_PRECISION (utype), ustepi, cstepi, &ratio))
2782     return INFTY;
2783
2784   /* use = ubase + ratio * (var - cbase).  If either cbase is a constant
2785      or ratio == 1, it is better to handle this like
2786      
2787      ubase - ratio * cbase + ratio * var
2788      
2789      (also holds in the case ratio == -1, TODO.  */
2790
2791   if (TREE_CODE (cbase) == INTEGER_CST)
2792     {
2793       offset = - ratio * int_cst_value (cbase); 
2794       cost += difference_cost (data,
2795                                ubase, integer_zero_node,
2796                                &symbol_present, &var_present, &offset,
2797                                depends_on);
2798     }
2799   else if (ratio == 1)
2800     {
2801       cost += difference_cost (data,
2802                                ubase, cbase,
2803                                &symbol_present, &var_present, &offset,
2804                                depends_on);
2805     }
2806   else
2807     {
2808       cost += force_var_cost (data, cbase, depends_on);
2809       cost += add_cost (TYPE_MODE (ctype));
2810       cost += difference_cost (data,
2811                                ubase, integer_zero_node,
2812                                &symbol_present, &var_present, &offset,
2813                                depends_on);
2814     }
2815
2816   /* If we are after the increment, the value of the candidate is higher by
2817      one iteration.  */
2818   if (stmt_after_increment (data->current_loop, cand, at))
2819     offset -= ratio * cstepi;
2820
2821   /* Now the computation is in shape symbol + var1 + const + ratio * var2.
2822      (symbol/var/const parts may be omitted).  If we are looking for an address,
2823      find the cost of addressing this.  */
2824   if (address_p)
2825     return get_address_cost (symbol_present, var_present, offset, ratio);
2826
2827   /* Otherwise estimate the costs for computing the expression.  */
2828   aratio = ratio > 0 ? ratio : -ratio;
2829   if (!symbol_present && !var_present && !offset)
2830     {
2831       if (ratio != 1)
2832         cost += multiply_by_cost (ratio, TYPE_MODE (ctype));
2833
2834       return cost;
2835     }
2836
2837   if (aratio != 1)
2838     cost += multiply_by_cost (aratio, TYPE_MODE (ctype));
2839
2840   n_sums = 1;
2841   if (var_present
2842       /* Symbol + offset should be compile-time computable.  */
2843       && (symbol_present || offset))
2844     n_sums++;
2845
2846   return cost + n_sums * add_cost (TYPE_MODE (ctype));
2847
2848 fallback:
2849   {
2850     /* Just get the expression, expand it and measure the cost.  */
2851     tree comp = get_computation_at (data->current_loop, use, cand, at);
2852
2853     if (!comp)
2854       return INFTY;
2855
2856     if (address_p)
2857       comp = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (comp)), comp);
2858
2859     return computation_cost (comp);
2860   }
2861 }
2862
2863 /* Determines the cost of the computation by that USE is expressed
2864    from induction variable CAND.  If ADDRESS_P is true, we just need
2865    to create an address from it, otherwise we want to get it into
2866    register.  A set of invariants we depend on is stored in
2867    DEPENDS_ON.  */
2868
2869 static unsigned
2870 get_computation_cost (struct ivopts_data *data,
2871                       struct iv_use *use, struct iv_cand *cand,
2872                       bool address_p, bitmap *depends_on)
2873 {
2874   return get_computation_cost_at (data,
2875                                   use, cand, address_p, depends_on, use->stmt);
2876 }
2877
2878 /* Determines cost of basing replacement of USE on CAND in a generic
2879    expression.  */
2880
2881 static void
2882 determine_use_iv_cost_generic (struct ivopts_data *data,
2883                                struct iv_use *use, struct iv_cand *cand)
2884 {
2885   bitmap depends_on;
2886   unsigned cost = get_computation_cost (data, use, cand, false, &depends_on);
2887
2888   set_use_iv_cost (data, use, cand, cost, depends_on);
2889 }
2890
2891 /* Determines cost of basing replacement of USE on CAND in an address.  */
2892
2893 static void
2894 determine_use_iv_cost_address (struct ivopts_data *data,
2895                                struct iv_use *use, struct iv_cand *cand)
2896 {
2897   bitmap depends_on;
2898   unsigned cost = get_computation_cost (data, use, cand, true, &depends_on);
2899
2900   set_use_iv_cost (data, use, cand, cost, depends_on);
2901 }
2902
2903 /* Computes value of induction variable IV in iteration NITER.  */
2904
2905 static tree
2906 iv_value (struct iv *iv, tree niter)
2907 {
2908   tree val;
2909   tree type = TREE_TYPE (iv->base);
2910
2911   niter = fold_convert (type, niter);
2912   val = fold (build2 (MULT_EXPR, type, iv->step, unsave_expr_now (niter)));
2913
2914   return fold (build2 (PLUS_EXPR, type, iv->base, val));
2915 }
2916
2917 /* Computes value of candidate CAND at position AT in iteration NITER.  */
2918
2919 static tree
2920 cand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter)
2921 {
2922   tree val = iv_value (cand->iv, niter);
2923   tree type = TREE_TYPE (cand->iv->base);
2924
2925   if (stmt_after_increment (loop, cand, at))
2926     val = fold (build2 (PLUS_EXPR, type, val, cand->iv->step));
2927
2928   return val;
2929 }
2930
2931 /* Check whether it is possible to express the condition in USE by comparison
2932    of candidate CAND.  If so, store the comparison code to COMPARE and the
2933    value compared with to BOUND.  */
2934
2935 static bool
2936 may_eliminate_iv (struct loop *loop,
2937                   struct iv_use *use, struct iv_cand *cand,
2938                   enum tree_code *compare, tree *bound)
2939 {
2940   edge exit;
2941   struct tree_niter_desc *niter, new_niter;
2942   tree wider_type, type, base;
2943
2944   /* For now just very primitive -- we work just for the single exit condition,
2945      and are quite conservative about the possible overflows.  TODO -- both of
2946      these can be improved.  */
2947   exit = single_dom_exit (loop);
2948   if (!exit)
2949     return false;
2950   if (use->stmt != last_stmt (exit->src))
2951     return false;
2952
2953   niter = &loop_data (loop)->niter;
2954   if (!niter->niter
2955       || !integer_nonzerop (niter->assumptions)
2956       || !integer_zerop (niter->may_be_zero))
2957     return false;
2958
2959   if (exit->flags & EDGE_TRUE_VALUE)
2960     *compare = EQ_EXPR;
2961   else
2962     *compare = NE_EXPR;
2963
2964   *bound = cand_value_at (loop, cand, use->stmt, niter->niter);
2965
2966   /* Let us check there is not some problem with overflows, by checking that
2967      the number of iterations is unchanged.  */
2968   base = cand->iv->base;
2969   type = TREE_TYPE (base);
2970   if (stmt_after_increment (loop, cand, use->stmt))
2971     base = fold (build2 (PLUS_EXPR, type, base, cand->iv->step));
2972
2973   new_niter.niter = NULL_TREE;
2974   number_of_iterations_cond (TREE_TYPE (cand->iv->base), base,
2975                              cand->iv->step, NE_EXPR, *bound, NULL_TREE,
2976                              &new_niter);
2977   if (!new_niter.niter
2978       || !integer_nonzerop (new_niter.assumptions)
2979       || !integer_zerop (new_niter.may_be_zero))
2980     return false;
2981
2982   wider_type = TREE_TYPE (new_niter.niter);
2983   if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (TREE_TYPE (niter->niter)))
2984     wider_type = TREE_TYPE (niter->niter);
2985   if (!operand_equal_p (fold_convert (wider_type, niter->niter),
2986                         fold_convert (wider_type, new_niter.niter), 0))
2987     return false;
2988
2989   return true;
2990 }
2991
2992 /* Determines cost of basing replacement of USE on CAND in a condition.  */
2993
2994 static void
2995 determine_use_iv_cost_condition (struct ivopts_data *data,
2996                                  struct iv_use *use, struct iv_cand *cand)
2997 {
2998   tree bound;
2999   enum tree_code compare;
3000
3001   /* Only consider real candidates.  */
3002   if (!cand->iv)
3003     {
3004       set_use_iv_cost (data, use, cand, INFTY, NULL);
3005       return;
3006     }
3007
3008   if (may_eliminate_iv (data->current_loop, use, cand, &compare, &bound))
3009     {
3010       bitmap depends_on = NULL;
3011       unsigned cost = force_var_cost (data, bound, &depends_on);
3012
3013       set_use_iv_cost (data, use, cand, cost, depends_on);
3014       return;
3015     }
3016
3017   /* The induction variable elimination failed; just express the original
3018      giv.  If it is compared with an invariant, note that we cannot get
3019      rid of it.  */
3020   if (TREE_CODE (*use->op_p) == SSA_NAME)
3021     record_invariant (data, *use->op_p, true);
3022   else
3023     {
3024       record_invariant (data, TREE_OPERAND (*use->op_p, 0), true);
3025       record_invariant (data, TREE_OPERAND (*use->op_p, 1), true);
3026     }
3027
3028   determine_use_iv_cost_generic (data, use, cand);
3029 }
3030
3031 /* Checks whether it is possible to replace the final value of USE by
3032    a direct computation.  If so, the formula is stored to *VALUE.  */
3033
3034 static bool
3035 may_replace_final_value (struct loop *loop, struct iv_use *use, tree *value)
3036 {
3037   edge exit;
3038   struct tree_niter_desc *niter;
3039
3040   exit = single_dom_exit (loop);
3041   if (!exit)
3042     return false;
3043
3044   if (!dominated_by_p (CDI_DOMINATORS, exit->src,
3045                        bb_for_stmt (use->stmt)))
3046     abort ();
3047
3048   niter = &loop_data (loop)->niter;
3049   if (!niter->niter
3050       || !operand_equal_p (niter->assumptions, boolean_true_node, 0)
3051       || !operand_equal_p (niter->may_be_zero, boolean_false_node, 0))
3052     return false;
3053
3054   *value = iv_value (use->iv, niter->niter);
3055
3056   return true;
3057 }
3058
3059 /* Determines cost of replacing final value of USE using CAND.  */
3060
3061 static void
3062 determine_use_iv_cost_outer (struct ivopts_data *data,
3063                              struct iv_use *use, struct iv_cand *cand)
3064 {
3065   bitmap depends_on;
3066   unsigned cost;
3067   edge exit;
3068   tree value;
3069   struct loop *loop = data->current_loop;
3070           
3071   if (!cand->iv)
3072     {
3073       if (!may_replace_final_value (loop, use, &value))
3074         {
3075           set_use_iv_cost (data, use, cand, INFTY, NULL);
3076           return;
3077         }
3078
3079       depends_on = NULL;
3080       cost = force_var_cost (data, value, &depends_on);
3081
3082       cost /= AVG_LOOP_NITER (loop);
3083
3084       set_use_iv_cost (data, use, cand, cost, depends_on);
3085       return;
3086     }
3087
3088   exit = single_dom_exit (loop);
3089   if (exit)
3090     {
3091       /* If there is just a single exit, we may use value of the candidate
3092          after we take it to determine the value of use.  */
3093       cost = get_computation_cost_at (data, use, cand, false, &depends_on,
3094                                       last_stmt (exit->src));
3095       if (cost != INFTY)
3096         cost /= AVG_LOOP_NITER (loop);
3097     }
3098   else
3099     {
3100       /* Otherwise we just need to compute the iv.  */
3101       cost = get_computation_cost (data, use, cand, false, &depends_on);
3102     }
3103                                    
3104   set_use_iv_cost (data, use, cand, cost, depends_on);
3105 }
3106
3107 /* Determines cost of basing replacement of USE on CAND.  */
3108
3109 static void
3110 determine_use_iv_cost (struct ivopts_data *data,
3111                        struct iv_use *use, struct iv_cand *cand)
3112 {
3113   switch (use->type)
3114     {
3115     case USE_NONLINEAR_EXPR:
3116       determine_use_iv_cost_generic (data, use, cand);
3117       break;
3118
3119     case USE_OUTER:
3120       determine_use_iv_cost_outer (data, use, cand);
3121       break;
3122
3123     case USE_ADDRESS:
3124       determine_use_iv_cost_address (data, use, cand);
3125       break;
3126
3127     case USE_COMPARE:
3128       determine_use_iv_cost_condition (data, use, cand);
3129       break;
3130
3131     default:
3132       abort ();
3133     }
3134 }
3135
3136 /* Determines costs of basing the use of the iv on an iv candidate.  */
3137
3138 static void
3139 determine_use_iv_costs (struct ivopts_data *data)
3140 {
3141   unsigned i, j;
3142   struct iv_use *use;
3143   struct iv_cand *cand;
3144
3145   data->consider_all_candidates = (n_iv_cands (data)
3146                                    <= CONSIDER_ALL_CANDIDATES_BOUND);
3147
3148   alloc_use_cost_map (data);
3149
3150   if (!data->consider_all_candidates)
3151     {
3152       /* Add the important candidate entries.  */
3153       for (j = 0; j < n_iv_cands (data); j++)
3154         {
3155           cand = iv_cand (data, j);
3156           if (!cand->important)
3157             continue;
3158           for (i = 0; i < n_iv_uses (data); i++)
3159             {
3160               use = iv_use (data, i);
3161               determine_use_iv_cost (data, use, cand);
3162             }
3163         }
3164     }
3165
3166   for (i = 0; i < n_iv_uses (data); i++)
3167     {
3168       use = iv_use (data, i);
3169
3170       if (data->consider_all_candidates)
3171         {
3172           for (j = 0; j < n_iv_cands (data); j++)
3173             {
3174               cand = iv_cand (data, j);
3175               determine_use_iv_cost (data, use, cand);
3176             }
3177         }
3178       else
3179         {
3180           EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j,
3181             {
3182               cand = iv_cand (data, j);
3183               if (!cand->important)
3184                 determine_use_iv_cost (data, use, cand);
3185             });
3186         }
3187     }
3188
3189   if (dump_file && (dump_flags & TDF_DETAILS))
3190     {
3191       fprintf (dump_file, "Use-candidate costs:\n");
3192
3193       for (i = 0; i < n_iv_uses (data); i++)
3194         {
3195           use = iv_use (data, i);
3196
3197           fprintf (dump_file, "Use %d:\n", i);
3198           fprintf (dump_file, "  cand\tcost\tdepends on\n");
3199           for (j = 0; j < use->n_map_members; j++)
3200             {
3201               if (!use->cost_map[j].cand
3202                   || use->cost_map[j].cost == INFTY)
3203                 continue;
3204
3205               fprintf (dump_file, "  %d\t%d\t",
3206                        use->cost_map[j].cand->id,
3207                        use->cost_map[j].cost);
3208               if (use->cost_map[j].depends_on)
3209                 bitmap_print (dump_file,
3210                               use->cost_map[j].depends_on, "","");
3211               fprintf (dump_file, "\n");
3212             }
3213
3214           fprintf (dump_file, "\n");
3215         }
3216       fprintf (dump_file, "\n");
3217     }
3218 }
3219
3220 /* Determines cost of the candidate CAND.  */
3221
3222 static void
3223 determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
3224 {
3225   unsigned cost_base, cost_step;
3226   tree base, last;
3227   basic_block bb;
3228
3229   if (!cand->iv)
3230     {
3231       cand->cost = 0;
3232       return;
3233     }
3234
3235   /* There are two costs associated with the candidate -- its increment
3236      and its initialization.  The second is almost negligible for any loop
3237      that rolls enough, so we take it just very little into account.  */
3238
3239   base = cand->iv->base;
3240   cost_base = force_var_cost (data, base, NULL);
3241   cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
3242
3243   cand->cost = cost_step + cost_base / AVG_LOOP_NITER (current_loop);
3244
3245   /* Prefer the original iv unless we may gain something by replacing it.  */
3246   if (cand->pos == IP_ORIGINAL)
3247     cand->cost--;
3248   
3249   /* Prefer not to insert statements into latch unless there are some
3250      already (so that we do not create unnecessary jumps).  */
3251   if (cand->pos == IP_END)
3252     {
3253       bb = ip_end_pos (data->current_loop);
3254       last = last_stmt (bb);
3255
3256       if (!last
3257           || TREE_CODE (last) == LABEL_EXPR)
3258         cand->cost++;
3259     }
3260 }
3261
3262 /* Determines costs of computation of the candidates.  */
3263
3264 static void
3265 determine_iv_costs (struct ivopts_data *data)
3266 {
3267   unsigned i;
3268
3269   if (dump_file && (dump_flags & TDF_DETAILS))
3270     {
3271       fprintf (dump_file, "Candidate costs:\n");
3272       fprintf (dump_file, "  cand\tcost\n");
3273     }
3274
3275   for (i = 0; i < n_iv_cands (data); i++)
3276     {
3277       struct iv_cand *cand = iv_cand (data, i);
3278
3279       determine_iv_cost (data, cand);
3280
3281       if (dump_file && (dump_flags & TDF_DETAILS))
3282         fprintf (dump_file, "  %d\t%d\n", i, cand->cost);
3283     }
3284   
3285 if (dump_file && (dump_flags & TDF_DETAILS))
3286       fprintf (dump_file, "\n");
3287 }
3288
3289 /* Calculates cost for having SIZE induction variables.  */
3290
3291 static unsigned
3292 ivopts_global_cost_for_size (struct ivopts_data *data, unsigned size)
3293 {
3294   return global_cost_for_size (size,
3295                                loop_data (data->current_loop)->regs_used,
3296                                n_iv_uses (data));
3297 }
3298
3299 /* For each size of the induction variable set determine the penalty.  */
3300
3301 static void
3302 determine_set_costs (struct ivopts_data *data)
3303 {
3304   unsigned j, n;
3305   tree phi, op;
3306   struct loop *loop = data->current_loop;
3307
3308   /* We use the following model (definitely improvable, especially the
3309      cost function -- TODO):
3310
3311      We estimate the number of registers available (using MD data), name it A.
3312
3313      We estimate the number of registers used by the loop, name it U.  This
3314      number is obtained as the number of loop phi nodes (not counting virtual
3315      registers and bivs) + the number of variables from outside of the loop.
3316
3317      We set a reserve R (free regs that are used for temporary computations,
3318      etc.).  For now the reserve is a constant 3.
3319
3320      Let I be the number of induction variables.
3321      
3322      -- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
3323         make a lot of ivs without a reason).
3324      -- if A - R < U + I <= A, the cost is I * PRES_COST
3325      -- if U + I > A, the cost is I * PRES_COST and
3326         number of uses * SPILL_COST * (U + I - A) / (U + I) is added.  */
3327
3328   if (dump_file && (dump_flags & TDF_DETAILS))
3329     {
3330       fprintf (dump_file, "Global costs:\n");
3331       fprintf (dump_file, "  target_avail_regs %d\n", target_avail_regs);
3332       fprintf (dump_file, "  target_small_cost %d\n", target_small_cost);
3333       fprintf (dump_file, "  target_pres_cost %d\n", target_pres_cost);
3334       fprintf (dump_file, "  target_spill_cost %d\n", target_spill_cost);
3335     }
3336
3337   n = 0;
3338   for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
3339     {
3340       op = PHI_RESULT (phi);
3341
3342       if (!is_gimple_reg (op))
3343         continue;
3344
3345       if (get_iv (data, op))
3346         continue;
3347
3348       n++;
3349     }
3350
3351   EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j,
3352     {
3353       struct version_info *info = ver_info (data, j);
3354
3355       if (info->inv_id && info->has_nonlin_use)
3356         n++;
3357     });
3358
3359   loop_data (loop)->regs_used = n;
3360   if (dump_file && (dump_flags & TDF_DETAILS))
3361     fprintf (dump_file, "  regs_used %d\n", n);
3362
3363   if (dump_file && (dump_flags & TDF_DETAILS))
3364     {
3365       fprintf (dump_file, "  cost for size:\n");
3366       fprintf (dump_file, "  ivs\tcost\n");
3367       for (j = 0; j <= 2 * target_avail_regs; j++)
3368         fprintf (dump_file, "  %d\t%d\n", j,
3369                  ivopts_global_cost_for_size (data, j));
3370       fprintf (dump_file, "\n");
3371     }
3372 }
3373
3374 /* Finds a best candidate for USE and stores it to CAND.  The candidates are
3375    taken from the set SOL and they may depend on invariants in the set INV.
3376    The really used candidate and invariants are noted to USED_IVS and
3377    USED_INV.  */
3378
3379 static unsigned
3380 find_best_candidate (struct ivopts_data *data,
3381                      struct iv_use *use, bitmap sol, bitmap inv,
3382                      bitmap used_ivs, bitmap used_inv, struct iv_cand **cand)
3383 {
3384   unsigned c, d;
3385   unsigned best_cost = INFTY, cost;
3386   struct iv_cand *cnd = NULL, *acnd;
3387   bitmap depends_on = NULL, asol;
3388
3389   if (data->consider_all_candidates)
3390     asol = sol;
3391   else
3392     {
3393       asol = BITMAP_XMALLOC ();
3394       bitmap_a_and_b (asol, sol, use->related_cands);
3395     }
3396
3397   EXECUTE_IF_SET_IN_BITMAP (asol, 0, c,
3398     {
3399       acnd = iv_cand (data, c);
3400       cost = get_use_iv_cost (data, use, acnd, &depends_on);
3401
3402       if (cost == INFTY)
3403         goto next_cand;
3404       if (cost > best_cost)
3405         goto next_cand;
3406       if (cost == best_cost)
3407         {
3408           /* Prefer the cheaper iv.  */
3409           if (acnd->cost >= cnd->cost)
3410             goto next_cand;
3411         }
3412
3413       if (depends_on)
3414         {
3415           EXECUTE_IF_AND_COMPL_IN_BITMAP (depends_on, inv, 0, d,
3416                                           goto next_cand);
3417           if (used_inv)
3418             bitmap_a_or_b (used_inv, used_inv, depends_on);
3419         }
3420
3421       cnd = acnd;
3422       best_cost = cost;
3423 next_cand: ;
3424     });
3425
3426   if (cnd && used_ivs)
3427     bitmap_set_bit (used_ivs, cnd->id);
3428
3429   if (cand)
3430     *cand = cnd;
3431
3432   if (!data->consider_all_candidates)
3433     BITMAP_XFREE (asol);
3434
3435   return best_cost;
3436 }
3437
3438 /* Returns cost of set of ivs SOL + invariants INV.  Removes unnecessary
3439    induction variable candidates and invariants from the sets.  Only
3440    uses 0 .. MAX_USE - 1 are taken into account.  */
3441
3442 static unsigned
3443 set_cost_up_to (struct ivopts_data *data, bitmap sol, bitmap inv,
3444                 unsigned max_use)
3445 {
3446   unsigned i;
3447   unsigned cost = 0, size = 0, acost;
3448   struct iv_use *use;
3449   struct iv_cand *cand;
3450   bitmap used_ivs = BITMAP_XMALLOC (), used_inv = BITMAP_XMALLOC ();
3451
3452   for (i = 0; i < max_use; i++)
3453     {
3454       use = iv_use (data, i);
3455       acost = find_best_candidate (data, use, sol, inv,
3456                                    used_ivs, used_inv, NULL);
3457       if (acost == INFTY)
3458         {
3459           BITMAP_XFREE (used_ivs);
3460           BITMAP_XFREE (used_inv);
3461           return INFTY;
3462         }
3463       cost += acost;
3464     }
3465
3466   EXECUTE_IF_SET_IN_BITMAP (used_ivs, 0, i,
3467     {
3468       cand = iv_cand (data, i);
3469
3470       /* Do not count the pseudocandidates.  */
3471       if (cand->iv)
3472         size++;
3473
3474       cost += cand->cost;
3475     });
3476   EXECUTE_IF_SET_IN_BITMAP (used_inv, 0, i, size++);
3477   cost += ivopts_global_cost_for_size (data, size);
3478
3479   bitmap_copy (sol, used_ivs);
3480   bitmap_copy (inv, used_inv);
3481
3482   BITMAP_XFREE (used_ivs);
3483   BITMAP_XFREE (used_inv);
3484
3485   return cost;
3486 }
3487
3488 /* Computes cost of set of ivs SOL + invariants INV.  Removes unnecessary
3489    induction variable candidates and invariants from the sets.  */
3490
3491 static unsigned
3492 set_cost (struct ivopts_data *data, bitmap sol, bitmap inv)
3493 {
3494   return set_cost_up_to (data, sol, inv, n_iv_uses (data));
3495 }
3496
3497 /* Tries to extend the sets IVS and INV in the best possible way in order
3498    to express the USE.  */
3499
3500 static bool
3501 try_add_cand_for (struct ivopts_data *data, bitmap ivs, bitmap inv,
3502                   struct iv_use *use)
3503 {
3504   unsigned best_cost = set_cost_up_to (data, ivs, inv, use->id + 1), act_cost;
3505   bitmap best_ivs = BITMAP_XMALLOC ();
3506   bitmap best_inv = BITMAP_XMALLOC ();
3507   bitmap act_ivs = BITMAP_XMALLOC ();
3508   bitmap act_inv = BITMAP_XMALLOC ();
3509   unsigned i;
3510   struct cost_pair *cp;
3511
3512   bitmap_copy (best_ivs, ivs);
3513   bitmap_copy (best_inv, inv);
3514
3515   for (i = 0; i < use->n_map_members; i++)
3516     {
3517       cp = use->cost_map + i;
3518       if (cp->cost == INFTY)
3519         continue;
3520
3521       bitmap_copy (act_ivs, ivs);
3522       bitmap_set_bit (act_ivs, cp->cand->id);
3523       if (cp->depends_on)
3524         bitmap_a_or_b (act_inv, inv, cp->depends_on);
3525       else
3526         bitmap_copy (act_inv, inv);
3527       act_cost = set_cost_up_to (data, act_ivs, act_inv, use->id + 1);
3528
3529       if (act_cost < best_cost)
3530         {
3531           best_cost = act_cost;
3532           bitmap_copy (best_ivs, act_ivs);
3533           bitmap_copy (best_inv, act_inv);
3534         }
3535     }
3536
3537   bitmap_copy (ivs, best_ivs);
3538   bitmap_copy (inv, best_inv);
3539
3540   BITMAP_XFREE (best_ivs);
3541   BITMAP_XFREE (best_inv);
3542   BITMAP_XFREE (act_ivs);
3543   BITMAP_XFREE (act_inv);
3544
3545   return (best_cost != INFTY);
3546 }
3547
3548 /* Finds an initial set of IVS and invariants INV.  We do this by simply
3549    choosing the best candidate for each use.  */
3550
3551 static unsigned
3552 get_initial_solution (struct ivopts_data *data, bitmap ivs, bitmap inv)
3553 {
3554   unsigned i;
3555
3556   for (i = 0; i < n_iv_uses (data); i++)
3557     if (!try_add_cand_for (data, ivs, inv, iv_use (data, i)))
3558       return INFTY;
3559
3560   return set_cost (data, ivs, inv);
3561 }
3562
3563 /* Tries to improve set of induction variables IVS and invariants INV to get
3564    it better than COST.  */
3565
3566 static bool
3567 try_improve_iv_set (struct ivopts_data *data,
3568                     bitmap ivs, bitmap inv, unsigned *cost)
3569 {
3570   unsigned i, acost;
3571   bitmap new_ivs = BITMAP_XMALLOC (), new_inv = BITMAP_XMALLOC ();
3572   bitmap best_new_ivs = NULL, best_new_inv = NULL;
3573
3574   /* Try altering the set of induction variables by one.  */
3575   for (i = 0; i < n_iv_cands (data); i++)
3576     {
3577       bitmap_copy (new_ivs, ivs);
3578       bitmap_copy (new_inv, inv);
3579
3580       if (bitmap_bit_p (ivs, i))
3581         bitmap_clear_bit (new_ivs, i);
3582       else
3583         bitmap_set_bit (new_ivs, i);
3584
3585       acost = set_cost (data, new_ivs, new_inv);
3586       if (acost >= *cost)
3587         continue;
3588
3589       if (!best_new_ivs)
3590         {
3591           best_new_ivs = BITMAP_XMALLOC ();
3592           best_new_inv = BITMAP_XMALLOC ();
3593         }
3594
3595       *cost = acost;
3596       bitmap_copy (best_new_ivs, new_ivs);
3597       bitmap_copy (best_new_inv, new_inv);
3598     }
3599
3600   /* Ditto for invariants.  */
3601   for (i = 1; i <= data->max_inv_id; i++)
3602     {
3603       if (ver_info (data, i)->has_nonlin_use)
3604         continue;
3605
3606       bitmap_copy (new_ivs, ivs);
3607       bitmap_copy (new_inv, inv);
3608
3609       if (bitmap_bit_p (inv, i))
3610         bitmap_clear_bit (new_inv, i);
3611       else
3612         bitmap_set_bit (new_inv, i);
3613
3614       acost = set_cost (data, new_ivs, new_inv);
3615       if (acost >= *cost)
3616         continue;
3617
3618       if (!best_new_ivs)
3619         {
3620           best_new_ivs = BITMAP_XMALLOC ();
3621           best_new_inv = BITMAP_XMALLOC ();
3622         }
3623
3624       *cost = acost;
3625       bitmap_copy (best_new_ivs, new_ivs);
3626       bitmap_copy (best_new_inv, new_inv);
3627     }
3628
3629   BITMAP_XFREE (new_ivs);
3630   BITMAP_XFREE (new_inv);
3631
3632   if (!best_new_ivs)
3633     return false;
3634
3635   bitmap_copy (ivs, best_new_ivs);
3636   bitmap_copy (inv, best_new_inv);
3637   BITMAP_XFREE (best_new_ivs);
3638   BITMAP_XFREE (best_new_inv);
3639   return true;
3640 }
3641
3642 /* Attempts to find the optimal set of induction variables.  We do simple
3643    greedy heuristic -- we try to replace at most one candidate in the selected
3644    solution and remove the unused ivs while this improves the cost.  */
3645
3646 static bitmap
3647 find_optimal_iv_set (struct ivopts_data *data)
3648 {
3649   unsigned cost, i;
3650   bitmap set = BITMAP_XMALLOC ();
3651   bitmap inv = BITMAP_XMALLOC ();
3652   struct iv_use *use;
3653
3654   /* Set the upper bound.  */
3655   cost = get_initial_solution (data, set, inv);
3656   if (cost == INFTY)
3657     {
3658       if (dump_file && (dump_flags & TDF_DETAILS))
3659         fprintf (dump_file, "Unable to substitute for ivs, failed.\n");
3660       BITMAP_XFREE (inv);
3661       BITMAP_XFREE (set);
3662       return NULL;
3663     }
3664
3665   if (dump_file && (dump_flags & TDF_DETAILS))
3666     {
3667       fprintf (dump_file, "Initial set of candidates (cost %d): ", cost);
3668       bitmap_print (dump_file, set, "", "");
3669       fprintf (dump_file, " invariants ");
3670       bitmap_print (dump_file, inv, "", "");
3671       fprintf (dump_file, "\n");
3672     }
3673
3674   while (try_improve_iv_set (data, set, inv, &cost))
3675     {
3676       if (dump_file && (dump_flags & TDF_DETAILS))
3677         {
3678           fprintf (dump_file, "Improved to (cost %d): ", cost);
3679           bitmap_print (dump_file, set, "", "");
3680           fprintf (dump_file, " invariants ");
3681           bitmap_print (dump_file, inv, "", "");
3682           fprintf (dump_file, "\n");
3683         }
3684     }
3685
3686   if (dump_file && (dump_flags & TDF_DETAILS))
3687     fprintf (dump_file, "Final cost %d\n\n", cost);
3688
3689   for (i = 0; i < n_iv_uses (data); i++)
3690     {
3691       use = iv_use (data, i);
3692       find_best_candidate (data, use, set, inv, NULL, NULL, &use->selected);
3693     }
3694
3695   BITMAP_XFREE (inv);
3696
3697   return set;
3698 }
3699
3700 /* Creates a new induction variable corresponding to CAND.  */
3701
3702 static void
3703 create_new_iv (struct ivopts_data *data, struct iv_cand *cand)
3704 {
3705   block_stmt_iterator incr_pos;
3706   tree base;
3707   bool after = false;
3708
3709   if (!cand->iv)
3710     return;
3711
3712   switch (cand->pos)
3713     {
3714     case IP_NORMAL:
3715       incr_pos = bsi_last (ip_normal_pos (data->current_loop));
3716       break;
3717
3718     case IP_END:
3719       incr_pos = bsi_last (ip_end_pos (data->current_loop));
3720       after = true;
3721       break;
3722
3723     case IP_ORIGINAL:
3724       /* Mark that the iv is preserved.  */
3725       name_info (data, cand->var_before)->preserve_biv = true;
3726       name_info (data, cand->var_after)->preserve_biv = true;
3727
3728       /* Rewrite the increment so that it uses var_before directly.  */
3729       find_interesting_uses_op (data, cand->var_after)->selected = cand;
3730       
3731       return;
3732     }
3733  
3734   gimple_add_tmp_var (cand->var_before);
3735   add_referenced_tmp_var (cand->var_before);
3736
3737   base = unshare_expr (cand->iv->base);
3738
3739   create_iv (base, cand->iv->step, cand->var_before, data->current_loop,
3740              &incr_pos, after, &cand->var_before, &cand->var_after);
3741 }
3742
3743 /* Creates new induction variables described in SET.  */
3744
3745 static void
3746 create_new_ivs (struct ivopts_data *data, bitmap set)
3747 {
3748   unsigned i;
3749   struct iv_cand *cand;
3750
3751   EXECUTE_IF_SET_IN_BITMAP (set, 0, i,
3752     {
3753       cand = iv_cand (data, i);
3754       create_new_iv (data, cand);
3755     });
3756 }
3757
3758 /* Removes statement STMT (real or a phi node).  If INCLUDING_DEFINED_NAME
3759    is true, remove also the ssa name defined by the statement.  */
3760
3761 static void
3762 remove_statement (tree stmt, bool including_defined_name)
3763 {
3764   if (TREE_CODE (stmt) == PHI_NODE)
3765     {
3766       if (!including_defined_name)
3767         {
3768           /* Prevent the ssa name defined by the statement from being removed.  */
3769           SET_PHI_RESULT (stmt, NULL);
3770         }
3771       remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
3772     }
3773   else
3774     {
3775       block_stmt_iterator bsi = stmt_for_bsi (stmt);
3776
3777       bsi_remove (&bsi);
3778     }
3779 }
3780
3781 /* Rewrites USE (definition of iv used in a nonlinear expression)
3782    using candidate CAND.  */
3783
3784 static void
3785 rewrite_use_nonlinear_expr (struct ivopts_data *data,
3786                             struct iv_use *use, struct iv_cand *cand)
3787 {
3788   tree comp = unshare_expr (get_computation (data->current_loop,
3789                                              use, cand));
3790   tree op, stmts, tgt, ass;
3791   block_stmt_iterator bsi, pbsi;
3792  
3793   if (TREE_CODE (use->stmt) == PHI_NODE)
3794     {
3795       tgt = PHI_RESULT (use->stmt);
3796
3797       /* If we should keep the biv, do not replace it.  */
3798       if (name_info (data, tgt)->preserve_biv)
3799         return;
3800
3801       pbsi = bsi = bsi_start (bb_for_stmt (use->stmt));
3802       while (!bsi_end_p (pbsi)
3803              && TREE_CODE (bsi_stmt (pbsi)) == LABEL_EXPR)
3804         {
3805           bsi = pbsi;
3806           bsi_next (&pbsi);
3807         }
3808     }
3809   else if (TREE_CODE (use->stmt) == MODIFY_EXPR)
3810     {
3811       tgt = TREE_OPERAND (use->stmt, 0);
3812       bsi = stmt_for_bsi (use->stmt);
3813     }
3814   else
3815     abort ();
3816
3817   op = force_gimple_operand (comp, &stmts, false, SSA_NAME_VAR (tgt));
3818
3819   if (TREE_CODE (use->stmt) == PHI_NODE)
3820     {
3821       if (stmts)
3822         bsi_insert_after (&bsi, stmts, BSI_CONTINUE_LINKING);
3823       ass = build2 (MODIFY_EXPR, TREE_TYPE (tgt), tgt, op);
3824       bsi_insert_after (&bsi, ass, BSI_NEW_STMT);
3825       remove_statement (use->stmt, false);
3826       SSA_NAME_DEF_STMT (tgt) = ass;
3827     }
3828   else
3829     {
3830       if (stmts)
3831         bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
3832       TREE_OPERAND (use->stmt, 1) = op;
3833     }
3834 }
3835
3836 /* Replaces ssa name in index IDX by its basic variable.  Callback for
3837    for_each_index.  */
3838
3839 static bool
3840 idx_remove_ssa_names (tree base ATTRIBUTE_UNUSED, tree *idx,
3841                       void *data ATTRIBUTE_UNUSED)
3842 {
3843   if (TREE_CODE (*idx) == SSA_NAME)
3844     *idx = SSA_NAME_VAR (*idx);
3845   return true;
3846 }
3847
3848 /* Unshares REF and replaces ssa names inside it by their basic variables.  */
3849
3850 static tree
3851 unshare_and_remove_ssa_names (tree ref)
3852 {
3853   ref = unshare_expr (ref);
3854   for_each_index (&ref, idx_remove_ssa_names, NULL);
3855
3856   return ref;
3857 }
3858
3859 /* Rewrites base of memory access OP with expression WITH in statement
3860    pointed to by BSI.  */
3861
3862 static void
3863 rewrite_address_base (block_stmt_iterator *bsi, tree *op, tree with)
3864 {
3865   tree var = get_base_address (*op), new_var, new_name, copy, name;
3866   tree orig;
3867
3868   if (!var || TREE_CODE (with) != SSA_NAME)
3869     goto do_rewrite;
3870
3871   if (TREE_CODE (var) == INDIRECT_REF)
3872     var = TREE_OPERAND (var, 0);
3873   if (TREE_CODE (var) == SSA_NAME)
3874     {
3875       name = var;
3876       var = SSA_NAME_VAR (var);
3877     }
3878   else if (DECL_P (var))
3879     name = NULL_TREE;
3880   else
3881     goto do_rewrite;
3882     
3883   if (var_ann (var)->type_mem_tag)
3884     var = var_ann (var)->type_mem_tag;
3885
3886   /* We need to add a memory tag for the variable.  But we do not want
3887      to add it to the temporary used for the computations, since this leads
3888      to problems in redundancy elimination when there are common parts
3889      in two computations referring to the different arrays.  So we copy
3890      the variable to a new temporary.  */
3891   copy = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, with);
3892   if (name)
3893     new_name = duplicate_ssa_name (name, copy);
3894   else
3895     {
3896       new_var = create_tmp_var (TREE_TYPE (with), "ruatmp");
3897       add_referenced_tmp_var (new_var);
3898       var_ann (new_var)->type_mem_tag = var;
3899       new_name = make_ssa_name (new_var, copy);
3900     }
3901   TREE_OPERAND (copy, 0) = new_name;
3902   bsi_insert_before (bsi, copy, BSI_SAME_STMT);
3903   with = new_name;
3904
3905 do_rewrite:
3906
3907   orig = NULL_TREE;
3908   if (TREE_CODE (*op) == INDIRECT_REF)
3909     orig = REF_ORIGINAL (*op);
3910   if (!orig)
3911     orig = unshare_and_remove_ssa_names (*op);
3912
3913   *op = build1 (INDIRECT_REF, TREE_TYPE (*op), with);
3914   /* Record the original reference, for purposes of alias analysis.  */
3915   REF_ORIGINAL (*op) = orig;
3916 }
3917
3918 /* Rewrites USE (address that is an iv) using candidate CAND.  */
3919
3920 static void
3921 rewrite_use_address (struct ivopts_data *data,
3922                      struct iv_use *use, struct iv_cand *cand)
3923 {
3924   tree comp = unshare_expr (get_computation (data->current_loop,
3925                                              use, cand));
3926   block_stmt_iterator bsi = stmt_for_bsi (use->stmt);
3927   tree stmts;
3928   tree op = force_gimple_operand (comp, &stmts, true, NULL_TREE);
3929
3930   if (stmts)
3931     bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
3932
3933   rewrite_address_base (&bsi, use->op_p, op);
3934 }
3935
3936 /* Rewrites USE (the condition such that one of the arguments is an iv) using
3937    candidate CAND.  */
3938
3939 static void
3940 rewrite_use_compare (struct ivopts_data *data,
3941                      struct iv_use *use, struct iv_cand *cand)
3942 {
3943   tree comp;
3944   tree *op_p, cond, op, stmts, bound;
3945   block_stmt_iterator bsi = stmt_for_bsi (use->stmt);
3946   enum tree_code compare;
3947   
3948   if (may_eliminate_iv (data->current_loop,
3949                         use, cand, &compare, &bound))
3950     {
3951       op = force_gimple_operand (unshare_expr (bound), &stmts,
3952                                  true, NULL_TREE);
3953
3954       if (stmts)
3955         bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
3956
3957       *use->op_p = build2 (compare, boolean_type_node,
3958                           var_at_stmt (data->current_loop,
3959                                        cand, use->stmt), op);
3960       modify_stmt (use->stmt);
3961       return;
3962     }
3963
3964   /* The induction variable elimination failed; just express the original
3965      giv.  */
3966   comp = unshare_expr (get_computation (data->current_loop, use, cand));
3967
3968   cond = *use->op_p;
3969   op_p = &TREE_OPERAND (cond, 0);
3970   if (TREE_CODE (*op_p) != SSA_NAME
3971       || zero_p (get_iv (data, *op_p)->step))
3972     op_p = &TREE_OPERAND (cond, 1);
3973
3974   op = force_gimple_operand (comp, &stmts, true, SSA_NAME_VAR (*op_p));
3975   if (stmts)
3976     bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
3977
3978   *op_p = op;
3979 }
3980
3981 /* Ensure that operand *OP_P may be used at the end of EXIT without
3982    violating loop closed ssa form.  */
3983
3984 static void
3985 protect_loop_closed_ssa_form_use (edge exit, use_operand_p op_p)
3986 {
3987   basic_block def_bb;
3988   struct loop *def_loop;
3989   tree phi, use;
3990
3991   use = USE_FROM_PTR (op_p);
3992   if (TREE_CODE (use) != SSA_NAME)
3993     return;
3994
3995   def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
3996   if (!def_bb)
3997     return;
3998
3999   def_loop = def_bb->loop_father;
4000   if (flow_bb_inside_loop_p (def_loop, exit->dest))
4001     return;
4002
4003   /* Try finding a phi node that copies the value out of the loop.  */
4004   for (phi = phi_nodes (exit->dest); phi; phi = TREE_CHAIN (phi))
4005     if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == use)
4006       break;
4007
4008   if (!phi)
4009     {
4010       /* Create such a phi node.  */
4011       tree new_name = duplicate_ssa_name (use, NULL);
4012
4013       phi = create_phi_node (new_name, exit->dest);
4014       SSA_NAME_DEF_STMT (new_name) = phi;
4015       add_phi_arg (&phi, use, exit);
4016     }
4017
4018   SET_USE (op_p, PHI_RESULT (phi));
4019 }
4020
4021 /* Ensure that operands of STMT may be used at the end of EXIT without
4022    violating loop closed ssa form.  */
4023
4024 static void
4025 protect_loop_closed_ssa_form (edge exit, tree stmt)
4026 {
4027   use_optype uses;
4028   vuse_optype vuses;
4029   v_may_def_optype v_may_defs;
4030   unsigned i;
4031
4032   get_stmt_operands (stmt);
4033
4034   uses = STMT_USE_OPS (stmt);
4035   for (i = 0; i < NUM_USES (uses); i++)
4036     protect_loop_closed_ssa_form_use (exit, USE_OP_PTR (uses, i));
4037
4038   vuses = STMT_VUSE_OPS (stmt);
4039   for (i = 0; i < NUM_VUSES (vuses); i++)
4040     protect_loop_closed_ssa_form_use (exit, VUSE_OP_PTR (vuses, i));
4041
4042   v_may_defs = STMT_V_MAY_DEF_OPS (stmt);
4043   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
4044     protect_loop_closed_ssa_form_use (exit, V_MAY_DEF_OP_PTR (v_may_defs, i));
4045 }
4046
4047 /* STMTS compute a value of a phi argument OP on EXIT of a loop.  Arrange things
4048    so that they are emitted on the correct place, and so that the loop closed
4049    ssa form is preserved.  */
4050
4051 static void
4052 compute_phi_arg_on_exit (edge exit, tree stmts, tree op)
4053 {
4054   tree_stmt_iterator tsi;
4055   block_stmt_iterator bsi;
4056   tree phi, stmt, def, next;
4057
4058   if (exit->dest->pred->pred_next)
4059     split_loop_exit_edge (exit);
4060
4061   if (TREE_CODE (stmts) == STATEMENT_LIST)
4062     {
4063       for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi))
4064         protect_loop_closed_ssa_form (exit, tsi_stmt (tsi));
4065     }
4066   else
4067     protect_loop_closed_ssa_form (exit, stmts);
4068
4069   /* Ensure there is label in exit->dest, so that we can
4070      insert after it.  */
4071   tree_block_label (exit->dest);
4072   bsi = bsi_after_labels (exit->dest);
4073   bsi_insert_after (&bsi, stmts, BSI_CONTINUE_LINKING);
4074
4075   if (!op)
4076     return;
4077
4078   for (phi = phi_nodes (exit->dest); phi; phi = next)
4079     {
4080       next = TREE_CHAIN (phi);
4081
4082       if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == op)
4083         {
4084           def = PHI_RESULT (phi);
4085           remove_statement (phi, false);
4086           stmt = build2 (MODIFY_EXPR, TREE_TYPE (op),
4087                         def, op);
4088           SSA_NAME_DEF_STMT (def) = stmt;
4089           bsi_insert_after (&bsi, stmt, BSI_CONTINUE_LINKING);
4090         }
4091     }
4092 }
4093
4094 /* Rewrites the final value of USE (that is only needed outside of the loop)
4095    using candidate CAND.  */
4096
4097 static void
4098 rewrite_use_outer (struct ivopts_data *data,
4099                    struct iv_use *use, struct iv_cand *cand)
4100 {
4101   edge exit;
4102   tree value, op, stmts, tgt;
4103   tree phi;
4104
4105   if (TREE_CODE (use->stmt) == PHI_NODE)
4106     tgt = PHI_RESULT (use->stmt);
4107   else if (TREE_CODE (use->stmt) == MODIFY_EXPR)
4108     tgt = TREE_OPERAND (use->stmt, 0);
4109   else
4110     abort ();
4111   exit = single_dom_exit (data->current_loop);
4112
4113   if (exit)
4114     {
4115       if (!cand->iv)
4116         {
4117           if (!may_replace_final_value (data->current_loop, use, &value))
4118             abort ();
4119         }
4120       else
4121         value = get_computation_at (data->current_loop,
4122                                     use, cand, last_stmt (exit->src));
4123
4124       op = force_gimple_operand (value, &stmts, true, SSA_NAME_VAR (tgt));
4125           
4126       /* If we will preserve the iv anyway and we would need to perform
4127          some computation to replace the final value, do nothing.  */
4128       if (stmts && name_info (data, tgt)->preserve_biv)
4129         return;
4130
4131       for (phi = phi_nodes (exit->dest); phi; phi = TREE_CHAIN (phi))
4132         {
4133           use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, exit);
4134
4135           if (USE_FROM_PTR (use_p) == tgt)
4136             SET_USE (use_p, op);
4137         }
4138
4139       if (stmts)
4140         compute_phi_arg_on_exit (exit, stmts, op);
4141
4142       /* Enable removal of the statement.  We cannot remove it directly,
4143          since we may still need the aliasing information attached to the
4144          ssa name defined by it.  */
4145       name_info (data, tgt)->iv->have_use_for = false;
4146       return;
4147     }
4148
4149   /* If the variable is going to be preserved anyway, there is nothing to
4150      do.  */
4151   if (name_info (data, tgt)->preserve_biv)
4152     return;
4153
4154   /* Otherwise we just need to compute the iv.  */
4155   rewrite_use_nonlinear_expr (data, use, cand);
4156 }
4157
4158 /* Rewrites USE using candidate CAND.  */
4159
4160 static void
4161 rewrite_use (struct ivopts_data *data,
4162              struct iv_use *use, struct iv_cand *cand)
4163 {
4164   switch (use->type)
4165     {
4166       case USE_NONLINEAR_EXPR:
4167         rewrite_use_nonlinear_expr (data, use, cand);
4168         break;
4169
4170       case USE_OUTER:
4171         rewrite_use_outer (data, use, cand);
4172         break;
4173
4174       case USE_ADDRESS:
4175         rewrite_use_address (data, use, cand);
4176         break;
4177
4178       case USE_COMPARE:
4179         rewrite_use_compare (data, use, cand);
4180         break;
4181
4182       default:
4183         abort ();
4184     }
4185   modify_stmt (use->stmt);
4186 }
4187
4188 /* Rewrite the uses using the selected induction variables.  */
4189
4190 static void
4191 rewrite_uses (struct ivopts_data *data)
4192 {
4193   unsigned i;
4194   struct iv_cand *cand;
4195   struct iv_use *use;
4196
4197   for (i = 0; i < n_iv_uses (data); i++)
4198     {
4199       use = iv_use (data, i);
4200       cand = use->selected;
4201       if (!cand)
4202         abort ();
4203
4204       rewrite_use (data, use, cand);
4205     }
4206 }
4207
4208 /* Removes the ivs that are not used after rewriting.  */
4209
4210 static void
4211 remove_unused_ivs (struct ivopts_data *data)
4212 {
4213   unsigned j;
4214
4215   EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j,
4216     {
4217       struct version_info *info;
4218
4219       info = ver_info (data, j);
4220       if (info->iv
4221           && !zero_p (info->iv->step)
4222           && !info->inv_id
4223           && !info->iv->have_use_for
4224           && !info->preserve_biv)
4225         remove_statement (SSA_NAME_DEF_STMT (info->iv->ssa_name), true);
4226     });
4227 }
4228
4229 /* Frees data allocated by the optimization of a single loop.  */
4230
4231 static void
4232 free_loop_data (struct ivopts_data *data)
4233 {
4234   unsigned i, j;
4235
4236   EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i,
4237     {
4238       struct version_info *info;
4239
4240       info = ver_info (data, i);
4241       if (info->iv)
4242         free (info->iv);
4243       info->iv = NULL;
4244       info->has_nonlin_use = false;
4245       info->preserve_biv = false;
4246       info->inv_id = 0;
4247     });
4248   bitmap_clear (data->relevant);
4249
4250   for (i = 0; i < n_iv_uses (data); i++)
4251     {
4252       struct iv_use *use = iv_use (data, i);
4253
4254       free (use->iv);
4255       BITMAP_XFREE (use->related_cands);
4256       for (j = 0; j < use->n_map_members; j++)
4257         if (use->cost_map[j].depends_on)