OSDN Git Service

* targhooks.c (default_unwind_emit, default_scalar_mode_supported_p):
[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       gcc_unreachable ();
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   gcc_assert (((val * b) & mask) == a);
517
518   if ((val >> (bits - 1)) & 1)
519     val |= ~mask;
520
521   *x = val;
522
523   return true;
524 }
525
526 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
527    emitted in LOOP.  */
528
529 static bool
530 stmt_after_ip_normal_pos (struct loop *loop, tree stmt)
531 {
532   basic_block bb = ip_normal_pos (loop), sbb = bb_for_stmt (stmt);
533
534   gcc_assert (bb);
535
536   if (sbb == loop->latch)
537     return true;
538
539   if (sbb != bb)
540     return false;
541
542   return stmt == last_stmt (bb);
543 }
544
545 /* Returns true if STMT if after the place where the original induction
546    variable CAND is incremented.  */
547
548 static bool
549 stmt_after_ip_original_pos (struct iv_cand *cand, tree stmt)
550 {
551   basic_block cand_bb = bb_for_stmt (cand->incremented_at);
552   basic_block stmt_bb = bb_for_stmt (stmt);
553   block_stmt_iterator bsi;
554
555   if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
556     return false;
557
558   if (stmt_bb != cand_bb)
559     return true;
560
561   /* Scan the block from the end, since the original ivs are usually
562      incremented at the end of the loop body.  */
563   for (bsi = bsi_last (stmt_bb); ; bsi_prev (&bsi))
564     {
565       if (bsi_stmt (bsi) == cand->incremented_at)
566         return false;
567       if (bsi_stmt (bsi) == stmt)
568         return true;
569     }
570 }
571
572 /* Returns true if STMT if after the place where the induction variable
573    CAND is incremented in LOOP.  */
574
575 static bool
576 stmt_after_increment (struct loop *loop, struct iv_cand *cand, tree stmt)
577 {
578   switch (cand->pos)
579     {
580     case IP_END:
581       return false;
582
583     case IP_NORMAL:
584       return stmt_after_ip_normal_pos (loop, stmt);
585
586     case IP_ORIGINAL:
587       return stmt_after_ip_original_pos (cand, stmt);
588
589     default:
590       gcc_unreachable ();
591     }
592 }
593
594 /* Initializes data structures used by the iv optimization pass, stored
595    in DATA.  LOOPS is the loop tree.  */
596
597 static void
598 tree_ssa_iv_optimize_init (struct loops *loops, struct ivopts_data *data)
599 {
600   unsigned i;
601
602   data->version_info_size = 2 * num_ssa_names;
603   data->version_info = xcalloc (data->version_info_size,
604                                 sizeof (struct version_info));
605   data->relevant = BITMAP_XMALLOC ();
606   data->max_inv_id = 0;
607
608   for (i = 1; i < loops->num; i++)
609     if (loops->parray[i])
610       loops->parray[i]->aux = xcalloc (1, sizeof (struct loop_data));
611
612   VARRAY_GENERIC_PTR_NOGC_INIT (data->iv_uses, 20, "iv_uses");
613   VARRAY_GENERIC_PTR_NOGC_INIT (data->iv_candidates, 20, "iv_candidates");
614   VARRAY_GENERIC_PTR_NOGC_INIT (decl_rtl_to_reset, 20, "decl_rtl_to_reset");
615 }
616
617 /* Allocates an induction variable with given initial value BASE and step STEP
618    for loop LOOP.  */
619
620 static struct iv *
621 alloc_iv (tree base, tree step)
622 {
623   struct iv *iv = xcalloc (1, sizeof (struct iv));
624
625   if (step && integer_zerop (step))
626     step = NULL_TREE;
627
628   iv->base = base;
629   iv->step = step;
630   iv->biv_p = false;
631   iv->have_use_for = false;
632   iv->use_id = 0;
633   iv->ssa_name = NULL_TREE;
634
635   return iv;
636 }
637
638 /* Sets STEP and BASE for induction variable IV.  */
639
640 static void
641 set_iv (struct ivopts_data *data, tree iv, tree base, tree step)
642 {
643   struct version_info *info = name_info (data, iv);
644
645   gcc_assert (!info->iv);
646
647   bitmap_set_bit (data->relevant, SSA_NAME_VERSION (iv));
648   info->iv = alloc_iv (base, step);
649   info->iv->ssa_name = iv;
650 }
651
652 /* Finds induction variable declaration for VAR.  */
653
654 static struct iv *
655 get_iv (struct ivopts_data *data, tree var)
656 {
657   basic_block bb;
658   
659   if (!name_info (data, var)->iv)
660     {
661       bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
662
663       if (!bb
664           || !flow_bb_inside_loop_p (data->current_loop, bb))
665         set_iv (data, var, var, NULL_TREE);
666     }
667
668   return name_info (data, var)->iv;
669 }
670
671 /* Determines the step of a biv defined in PHI.  */
672
673 static tree
674 determine_biv_step (tree phi)
675 {
676   struct loop *loop = bb_for_stmt (phi)->loop_father;
677   tree name = PHI_RESULT (phi), base, step;
678   tree type = TREE_TYPE (name);
679
680   if (!is_gimple_reg (name))
681     return NULL_TREE;
682
683   if (!simple_iv (loop, phi, name, &base, &step))
684     return NULL_TREE;
685
686   if (!step)
687     return build_int_cst (type, 0);
688
689   return step;
690 }
691
692 /* Returns false if INDEX is a ssa name that occurs in an
693    abnormal phi node.  Callback for for_each_index.  */
694
695 static bool
696 idx_contains_abnormal_ssa_name_p (tree base ATTRIBUTE_UNUSED, tree *index,
697                                   void *data ATTRIBUTE_UNUSED)
698 {
699   if (TREE_CODE (*index) != SSA_NAME)
700     return true;
701
702   return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (*index) == 0;
703 }
704
705 /* Returns true if EXPR contains a ssa name that occurs in an
706    abnormal phi node.  */
707
708 static bool
709 contains_abnormal_ssa_name_p (tree expr)
710 {
711   enum tree_code code = TREE_CODE (expr);
712   char class = TREE_CODE_CLASS (code);
713     
714   if (code == SSA_NAME)
715     return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
716
717   if (code == INTEGER_CST
718       || is_gimple_min_invariant (expr))
719     return false;
720
721   if (code == ADDR_EXPR)
722     return !for_each_index (&TREE_OPERAND (expr, 1),
723                             idx_contains_abnormal_ssa_name_p,
724                             NULL);
725
726   switch (class)
727     {
728     case '2':
729     case '<':
730       if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1)))
731         return true;
732
733       /* Fallthru.  */
734     case '1':
735       if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0)))
736         return true;
737
738       break;
739
740     default:
741       gcc_unreachable ();
742     }
743
744   return false;
745 }
746
747 /* Finds basic ivs.  */
748
749 static bool
750 find_bivs (struct ivopts_data *data)
751 {
752   tree phi, step, type, base;
753   bool found = false;
754   struct loop *loop = data->current_loop;
755
756   for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
757     {
758       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
759         continue;
760
761       step = determine_biv_step (phi);
762
763       if (!step)
764         continue;
765       if (cst_and_fits_in_hwi (step)
766           && int_cst_value (step) == 0)
767         continue;
768
769       base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
770       if (contains_abnormal_ssa_name_p (base))
771         continue;
772
773       type = TREE_TYPE (PHI_RESULT (phi));
774       base = fold_convert (type, base);
775       step = fold_convert (type, step);
776
777       /* FIXME: We do not handle induction variables whose step does
778          not satisfy cst_and_fits_in_hwi.  */
779       if (!cst_and_fits_in_hwi (step))
780         continue;
781
782       set_iv (data, PHI_RESULT (phi), base, step);
783       found = true;
784     }
785
786   return found;
787 }
788
789 /* Marks basic ivs.  */
790
791 static void
792 mark_bivs (struct ivopts_data *data)
793 {
794   tree phi, var;
795   struct iv *iv, *incr_iv;
796   struct loop *loop = data->current_loop;
797   basic_block incr_bb;
798
799   for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
800     {
801       iv = get_iv (data, PHI_RESULT (phi));
802       if (!iv)
803         continue;
804
805       var = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
806       incr_iv = get_iv (data, var);
807       if (!incr_iv)
808         continue;
809
810       /* If the increment is in the subloop, ignore it.  */
811       incr_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
812       if (incr_bb->loop_father != data->current_loop
813           || (incr_bb->flags & BB_IRREDUCIBLE_LOOP))
814         continue;
815
816       iv->biv_p = true;
817       incr_iv->biv_p = true;
818     }
819 }
820
821 /* Checks whether STMT defines a linear induction variable and stores its
822    parameters to BASE and STEP.  */
823
824 static bool
825 find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt,
826                         tree *base, tree *step)
827 {
828   tree lhs;
829   struct loop *loop = data->current_loop;
830
831   *base = NULL_TREE;
832   *step = NULL_TREE;
833
834   if (TREE_CODE (stmt) != MODIFY_EXPR)
835     return false;
836
837   lhs = TREE_OPERAND (stmt, 0);
838   if (TREE_CODE (lhs) != SSA_NAME)
839     return false;
840
841   if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), base, step))
842     return false;
843
844   /* FIXME: We do not handle induction variables whose step does
845      not satisfy cst_and_fits_in_hwi.  */
846   if (!zero_p (*step)
847       && !cst_and_fits_in_hwi (*step))
848     return false;
849
850   if (contains_abnormal_ssa_name_p (*base))
851     return false;
852
853   return true;
854 }
855
856 /* Finds general ivs in statement STMT.  */
857
858 static void
859 find_givs_in_stmt (struct ivopts_data *data, tree stmt)
860 {
861   tree base, step;
862
863   if (!find_givs_in_stmt_scev (data, stmt, &base, &step))
864     return;
865
866   set_iv (data, TREE_OPERAND (stmt, 0), base, step);
867 }
868
869 /* Finds general ivs in basic block BB.  */
870
871 static void
872 find_givs_in_bb (struct ivopts_data *data, basic_block bb)
873 {
874   block_stmt_iterator bsi;
875
876   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
877     find_givs_in_stmt (data, bsi_stmt (bsi));
878 }
879
880 /* Finds general ivs.  */
881
882 static void
883 find_givs (struct ivopts_data *data)
884 {
885   struct loop *loop = data->current_loop;
886   basic_block *body = get_loop_body_in_dom_order (loop);
887   unsigned i;
888
889   for (i = 0; i < loop->num_nodes; i++)
890     find_givs_in_bb (data, body[i]);
891   free (body);
892 }
893
894 /* Determine the number of iterations of the current loop.  */
895
896 static void
897 determine_number_of_iterations (struct ivopts_data *data)
898 {
899   struct loop *loop = data->current_loop;
900   edge exit = single_dom_exit (loop);
901
902   if (!exit)
903     return;
904
905   number_of_iterations_exit (loop, exit, &loop_data (loop)->niter);
906 }
907
908 /* For each ssa name defined in LOOP determines whether it is an induction
909    variable and if so, its initial value and step.  */
910
911 static bool
912 find_induction_variables (struct ivopts_data *data)
913 {
914   unsigned i;
915   struct loop *loop = data->current_loop;
916
917   if (!find_bivs (data))
918     return false;
919
920   find_givs (data);
921   mark_bivs (data);
922   determine_number_of_iterations (data);
923
924   if (dump_file && (dump_flags & TDF_DETAILS))
925     {
926       if (loop_data (loop)->niter.niter)
927         {
928           fprintf (dump_file, "  number of iterations ");
929           print_generic_expr (dump_file, loop_data (loop)->niter.niter,
930                               TDF_SLIM);
931           fprintf (dump_file, "\n");
932
933           fprintf (dump_file, "  may be zero if ");
934           print_generic_expr (dump_file, loop_data (loop)->niter.may_be_zero,
935                               TDF_SLIM);
936           fprintf (dump_file, "\n");
937
938           fprintf (dump_file, "  bogus unless ");
939           print_generic_expr (dump_file, loop_data (loop)->niter.assumptions,
940                               TDF_SLIM);
941           fprintf (dump_file, "\n");
942           fprintf (dump_file, "\n");
943         };
944  
945       fprintf (dump_file, "Induction variables:\n\n");
946
947       EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i,
948         {
949           if (ver_info (data, i)->iv)
950             dump_iv (dump_file, ver_info (data, i)->iv);
951         });
952     }
953
954   return true;
955 }
956
957 /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV.  */
958
959 static struct iv_use *
960 record_use (struct ivopts_data *data, tree *use_p, struct iv *iv,
961             tree stmt, enum use_type use_type)
962 {
963   struct iv_use *use = xcalloc (1, sizeof (struct iv_use));
964
965   use->id = n_iv_uses (data);
966   use->type = use_type;
967   use->iv = iv;
968   use->stmt = stmt;
969   use->op_p = use_p;
970   use->related_cands = BITMAP_XMALLOC ();
971
972   if (dump_file && (dump_flags & TDF_DETAILS))
973     dump_use (dump_file, use);
974
975   VARRAY_PUSH_GENERIC_PTR_NOGC (data->iv_uses, use);
976
977   return use;
978 }
979
980 /* Checks whether OP is a loop-level invariant and if so, records it.
981    NONLINEAR_USE is true if the invariant is used in a way we do not
982    handle specially.  */
983
984 static void
985 record_invariant (struct ivopts_data *data, tree op, bool nonlinear_use)
986 {
987   basic_block bb;
988   struct version_info *info;
989
990   if (TREE_CODE (op) != SSA_NAME
991       || !is_gimple_reg (op))
992     return;
993
994   bb = bb_for_stmt (SSA_NAME_DEF_STMT (op));
995   if (bb
996       && flow_bb_inside_loop_p (data->current_loop, bb))
997     return;
998
999   info = name_info (data, op);
1000   info->name = op;
1001   info->has_nonlin_use |= nonlinear_use;
1002   if (!info->inv_id)
1003     info->inv_id = ++data->max_inv_id;
1004   bitmap_set_bit (data->relevant, SSA_NAME_VERSION (op));
1005 }
1006
1007 /* Checks whether the use OP is interesting and if so, records it
1008    as TYPE.  */
1009
1010 static struct iv_use *
1011 find_interesting_uses_outer_or_nonlin (struct ivopts_data *data, tree op,
1012                                        enum use_type type)
1013 {
1014   struct iv *iv;
1015   struct iv *civ;
1016   tree stmt;
1017   struct iv_use *use;
1018
1019   if (TREE_CODE (op) != SSA_NAME)
1020     return NULL;
1021
1022   iv = get_iv (data, op);
1023   if (!iv)
1024     return NULL;
1025   
1026   if (iv->have_use_for)
1027     {
1028       use = iv_use (data, iv->use_id);
1029
1030       gcc_assert (use->type == USE_NONLINEAR_EXPR
1031                   || use->type == USE_OUTER);
1032
1033       if (type == USE_NONLINEAR_EXPR)
1034         use->type = USE_NONLINEAR_EXPR;
1035       return use;
1036     }
1037
1038   if (zero_p (iv->step))
1039     {
1040       record_invariant (data, op, true);
1041       return NULL;
1042     }
1043   iv->have_use_for = true;
1044
1045   civ = xmalloc (sizeof (struct iv));
1046   *civ = *iv;
1047
1048   stmt = SSA_NAME_DEF_STMT (op);
1049   gcc_assert (TREE_CODE (stmt) == PHI_NODE
1050               || TREE_CODE (stmt) == MODIFY_EXPR);
1051
1052   use = record_use (data, NULL, civ, stmt, type);
1053   iv->use_id = use->id;
1054
1055   return use;
1056 }
1057
1058 /* Checks whether the use OP is interesting and if so, records it.  */
1059
1060 static struct iv_use *
1061 find_interesting_uses_op (struct ivopts_data *data, tree op)
1062 {
1063   return find_interesting_uses_outer_or_nonlin (data, op, USE_NONLINEAR_EXPR);
1064 }
1065
1066 /* Records a definition of induction variable OP that is used outside of the
1067    loop.  */
1068
1069 static struct iv_use *
1070 find_interesting_uses_outer (struct ivopts_data *data, tree op)
1071 {
1072   return find_interesting_uses_outer_or_nonlin (data, op, USE_OUTER);
1073 }
1074
1075 /* Checks whether the condition *COND_P in STMT is interesting
1076    and if so, records it.  */
1077
1078 static void
1079 find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
1080 {
1081   tree *op0_p;
1082   tree *op1_p;
1083   struct iv *iv0 = NULL, *iv1 = NULL, *civ;
1084   struct iv const_iv;
1085   tree zero = integer_zero_node;
1086
1087   const_iv.step = NULL_TREE;
1088
1089   if (integer_zerop (*cond_p)
1090       || integer_nonzerop (*cond_p))
1091     return;
1092
1093   if (TREE_CODE (*cond_p) == SSA_NAME)
1094     {
1095       op0_p = cond_p;
1096       op1_p = &zero;
1097     }
1098   else
1099     {
1100       op0_p = &TREE_OPERAND (*cond_p, 0);
1101       op1_p = &TREE_OPERAND (*cond_p, 1);
1102     }
1103
1104   if (TREE_CODE (*op0_p) == SSA_NAME)
1105     iv0 = get_iv (data, *op0_p);
1106   else
1107     iv0 = &const_iv;
1108
1109   if (TREE_CODE (*op1_p) == SSA_NAME)
1110     iv1 = get_iv (data, *op1_p);
1111   else
1112     iv1 = &const_iv;
1113
1114   if (/* When comparing with non-invariant value, we may not do any senseful
1115          induction variable elimination.  */
1116       (!iv0 || !iv1)
1117       /* Eliminating condition based on two ivs would be nontrivial.
1118          ??? TODO -- it is not really important to handle this case.  */
1119       || (!zero_p (iv0->step) && !zero_p (iv1->step)))
1120     {
1121       find_interesting_uses_op (data, *op0_p);
1122       find_interesting_uses_op (data, *op1_p);
1123       return;
1124     }
1125
1126   if (zero_p (iv0->step) && zero_p (iv1->step))
1127     {
1128       /* If both are invariants, this is a work for unswitching.  */
1129       return;
1130     }
1131
1132   civ = xmalloc (sizeof (struct iv));
1133   *civ = zero_p (iv0->step) ? *iv1: *iv0;
1134   record_use (data, cond_p, civ, stmt, USE_COMPARE);
1135 }
1136
1137 /* Cumulates the steps of indices into DATA and replaces their values with the
1138    initial ones.  Returns false when the value of the index cannot be determined.
1139    Callback for for_each_index.  */
1140
1141 struct ifs_ivopts_data
1142 {
1143   struct ivopts_data *ivopts_data;
1144   tree stmt;
1145   tree *step_p;
1146 };
1147
1148 static bool
1149 idx_find_step (tree base, tree *idx, void *data)
1150 {
1151   struct ifs_ivopts_data *dta = data;
1152   struct iv *iv;
1153   tree step, type, iv_type, iv_step;
1154   
1155   if (TREE_CODE (*idx) != SSA_NAME)
1156     return true;
1157
1158   iv = get_iv (dta->ivopts_data, *idx);
1159   if (!iv)
1160     return false;
1161
1162   *idx = iv->base;
1163
1164   if (!iv->step)
1165     return true;
1166
1167   iv_type = TREE_TYPE (iv->base);
1168   type = build_pointer_type (TREE_TYPE (base));
1169   if (TREE_CODE (base) == ARRAY_REF)
1170     step = array_ref_element_size (base);
1171   else
1172     /* The step for pointer arithmetics already is 1 byte.  */
1173     step = build_int_cst (type, 1);
1174
1175   if (TYPE_PRECISION (iv_type) < TYPE_PRECISION (type))
1176     iv_step = can_count_iv_in_wider_type (dta->ivopts_data->current_loop,
1177                                           type, iv->base, iv->step, dta->stmt);
1178   else
1179     iv_step = fold_convert (iv_type, iv->step);
1180
1181   if (!iv_step)
1182     {
1183       /* The index might wrap.  */
1184       return false;
1185     }
1186
1187   step = EXEC_BINARY (MULT_EXPR, type, step, iv_step);
1188
1189   if (!*dta->step_p)
1190     *dta->step_p = step;
1191   else
1192     *dta->step_p = EXEC_BINARY (PLUS_EXPR, type, *dta->step_p, step);
1193
1194   return true;
1195 }
1196
1197 /* Records use in index IDX.  Callback for for_each_index.  Ivopts data
1198    object is passed to it in DATA.  */
1199
1200 static bool
1201 idx_record_use (tree base ATTRIBUTE_UNUSED, tree *idx,
1202                 void *data)
1203 {
1204   find_interesting_uses_op (data, *idx);
1205   return true;
1206 }
1207
1208 /* Finds addresses in *OP_P inside STMT.  */
1209
1210 static void
1211 find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
1212 {
1213   tree base = unshare_expr (*op_p), step = NULL;
1214   struct iv *civ;
1215   struct ifs_ivopts_data ifs_ivopts_data;
1216
1217   /* Ignore bitfields for now.  Not really something terribly complicated
1218      to handle.  TODO.  */
1219   if (TREE_CODE (base) == COMPONENT_REF
1220       && DECL_NONADDRESSABLE_P (TREE_OPERAND (base, 1)))
1221     goto fail;
1222
1223   ifs_ivopts_data.ivopts_data = data;
1224   ifs_ivopts_data.stmt = stmt;
1225   ifs_ivopts_data.step_p = &step;
1226   if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
1227       || zero_p (step))
1228     goto fail;
1229
1230   if (TREE_CODE (base) == INDIRECT_REF)
1231     base = TREE_OPERAND (base, 0);
1232   else
1233     base = build_addr (base);
1234
1235   civ = alloc_iv (base, step);
1236   record_use (data, op_p, civ, stmt, USE_ADDRESS);
1237   return;
1238
1239 fail:
1240   for_each_index (op_p, idx_record_use, data);
1241 }
1242
1243 /* Finds and records invariants used in STMT.  */
1244
1245 static void
1246 find_invariants_stmt (struct ivopts_data *data, tree stmt)
1247 {
1248   use_optype uses = NULL;
1249   unsigned i, n;
1250   tree op;
1251
1252   if (TREE_CODE (stmt) == PHI_NODE)
1253     n = PHI_NUM_ARGS (stmt);
1254   else
1255     {
1256       get_stmt_operands (stmt);
1257       uses = STMT_USE_OPS (stmt);
1258       n = NUM_USES (uses);
1259     }
1260
1261   for (i = 0; i < n; i++)
1262     {
1263       if (TREE_CODE (stmt) == PHI_NODE)
1264         op = PHI_ARG_DEF (stmt, i);
1265       else
1266         op = USE_OP (uses, i);
1267
1268       record_invariant (data, op, false);
1269     }
1270 }
1271
1272 /* Finds interesting uses of induction variables in the statement STMT.  */
1273
1274 static void
1275 find_interesting_uses_stmt (struct ivopts_data *data, tree stmt)
1276 {
1277   struct iv *iv;
1278   tree op, lhs, rhs;
1279   use_optype uses = NULL;
1280   unsigned i, n;
1281
1282   find_invariants_stmt (data, stmt);
1283
1284   if (TREE_CODE (stmt) == COND_EXPR)
1285     {
1286       find_interesting_uses_cond (data, stmt, &COND_EXPR_COND (stmt));
1287       return;
1288     }
1289
1290   if (TREE_CODE (stmt) == MODIFY_EXPR)
1291     {
1292       lhs = TREE_OPERAND (stmt, 0);
1293       rhs = TREE_OPERAND (stmt, 1);
1294
1295       if (TREE_CODE (lhs) == SSA_NAME)
1296         {
1297           /* If the statement defines an induction variable, the uses are not
1298              interesting by themselves.  */
1299
1300           iv = get_iv (data, lhs);
1301
1302           if (iv && !zero_p (iv->step))
1303             return;
1304         }
1305
1306       switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
1307         {
1308         case '<':
1309           find_interesting_uses_cond (data, stmt, &TREE_OPERAND (stmt, 1));
1310           return;
1311
1312         case 'r':
1313           find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 1));
1314           if (TREE_CODE_CLASS (TREE_CODE (lhs)) == 'r')
1315             find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
1316           return;
1317
1318         default: ;
1319         }
1320
1321       if (TREE_CODE_CLASS (TREE_CODE (lhs)) == 'r')
1322         {
1323           find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
1324           find_interesting_uses_op (data, rhs);
1325           return;
1326         }
1327     }
1328
1329   if (TREE_CODE (stmt) == PHI_NODE
1330       && bb_for_stmt (stmt) == data->current_loop->header)
1331     {
1332       lhs = PHI_RESULT (stmt);
1333       iv = get_iv (data, lhs);
1334
1335       if (iv && !zero_p (iv->step))
1336         return;
1337     }
1338
1339   if (TREE_CODE (stmt) == PHI_NODE)
1340     n = PHI_NUM_ARGS (stmt);
1341   else
1342     {
1343       uses = STMT_USE_OPS (stmt);
1344       n = NUM_USES (uses);
1345     }
1346
1347   for (i = 0; i < n; i++)
1348     {
1349       if (TREE_CODE (stmt) == PHI_NODE)
1350         op = PHI_ARG_DEF (stmt, i);
1351       else
1352         op = USE_OP (uses, i);
1353
1354       if (TREE_CODE (op) != SSA_NAME)
1355         continue;
1356
1357       iv = get_iv (data, op);
1358       if (!iv)
1359         continue;
1360
1361       find_interesting_uses_op (data, op);
1362     }
1363 }
1364
1365 /* Finds interesting uses of induction variables outside of loops
1366    on loop exit edge EXIT.  */
1367
1368 static void
1369 find_interesting_uses_outside (struct ivopts_data *data, edge exit)
1370 {
1371   tree phi, def;
1372
1373   for (phi = phi_nodes (exit->dest); phi; phi = TREE_CHAIN (phi))
1374     {
1375       def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1376       find_interesting_uses_outer (data, def);
1377     }
1378 }
1379
1380 /* Finds uses of the induction variables that are interesting.  */
1381
1382 static void
1383 find_interesting_uses (struct ivopts_data *data)
1384 {
1385   basic_block bb;
1386   block_stmt_iterator bsi;
1387   tree phi;
1388   basic_block *body = get_loop_body (data->current_loop);
1389   unsigned i;
1390   struct version_info *info;
1391   edge e;
1392
1393   if (dump_file && (dump_flags & TDF_DETAILS))
1394     fprintf (dump_file, "Uses:\n\n");
1395
1396   for (i = 0; i < data->current_loop->num_nodes; i++)
1397     {
1398       bb = body[i];
1399
1400       for (e = bb->succ; e; e = e->succ_next)
1401         if (e->dest != EXIT_BLOCK_PTR
1402             && !flow_bb_inside_loop_p (data->current_loop, e->dest))
1403           find_interesting_uses_outside (data, e);
1404
1405       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1406         find_interesting_uses_stmt (data, phi);
1407       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1408         find_interesting_uses_stmt (data, bsi_stmt (bsi));
1409     }
1410
1411   if (dump_file && (dump_flags & TDF_DETAILS))
1412     {
1413       fprintf (dump_file, "\n");
1414
1415       EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i,
1416         {
1417           info = ver_info (data, i);
1418           if (info->inv_id)
1419             {
1420               fprintf (dump_file, "  ");
1421               print_generic_expr (dump_file, info->name, TDF_SLIM);
1422               fprintf (dump_file, " is invariant (%d)%s\n",
1423                        info->inv_id, info->has_nonlin_use ? "" : ", eliminable");
1424             }
1425         });
1426
1427       fprintf (dump_file, "\n");
1428     }
1429
1430   free (body);
1431 }
1432
1433 /* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
1434    position to POS.  If USE is not NULL, the candidate is set as related to
1435    it.  If both BASE and STEP are NULL, we add a pseudocandidate for the
1436    replacement of the final value of the iv by a direct computation.  */
1437
1438 static struct iv_cand *
1439 add_candidate_1 (struct ivopts_data *data,
1440                  tree base, tree step, bool important, enum iv_position pos,
1441                  struct iv_use *use, tree incremented_at)
1442 {
1443   unsigned i;
1444   struct iv_cand *cand = NULL;
1445   tree type;
1446   
1447   if (base)
1448     {
1449       type = TREE_TYPE (base);
1450       if (!TYPE_UNSIGNED (type))
1451         {
1452           type = unsigned_type_for (type);
1453           base = fold_convert (type, base);
1454           if (step)
1455             step = fold_convert (type, step);
1456         }
1457     }
1458
1459   for (i = 0; i < n_iv_cands (data); i++)
1460     {
1461       cand = iv_cand (data, i);
1462
1463       if (cand->pos != pos)
1464         continue;
1465
1466       if (cand->incremented_at != incremented_at)
1467         continue;
1468
1469       if (!cand->iv)
1470         {
1471           if (!base && !step)
1472             break;
1473
1474           continue;
1475         }
1476
1477       if (!base && !step)
1478         continue;
1479
1480       if (!operand_equal_p (base, cand->iv->base, 0))
1481         continue;
1482
1483       if (zero_p (cand->iv->step))
1484         {
1485           if (zero_p (step))
1486             break;
1487         }
1488       else
1489         {
1490           if (step && operand_equal_p (step, cand->iv->step, 0))
1491             break;
1492         }
1493     }
1494
1495   if (i == n_iv_cands (data))
1496     {
1497       cand = xcalloc (1, sizeof (struct iv_cand));
1498       cand->id = i;
1499
1500       if (!base && !step)
1501         cand->iv = NULL;
1502       else
1503         cand->iv = alloc_iv (base, step);
1504
1505       cand->pos = pos;
1506       if (pos != IP_ORIGINAL && cand->iv)
1507         {
1508           cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp");
1509           cand->var_after = cand->var_before;
1510         }
1511       cand->important = important;
1512       cand->incremented_at = incremented_at;
1513       VARRAY_PUSH_GENERIC_PTR_NOGC (data->iv_candidates, cand);
1514
1515       if (dump_file && (dump_flags & TDF_DETAILS))
1516         dump_cand (dump_file, cand);
1517     }
1518
1519   if (important && !cand->important)
1520     {
1521       cand->important = true;
1522       if (dump_file && (dump_flags & TDF_DETAILS))
1523         fprintf (dump_file, "Candidate %d is important\n", cand->id);
1524     }
1525
1526   if (use)
1527     {
1528       bitmap_set_bit (use->related_cands, i);
1529       if (dump_file && (dump_flags & TDF_DETAILS))
1530         fprintf (dump_file, "Candidate %d is related to use %d\n",
1531                  cand->id, use->id);
1532     }
1533
1534   return cand;
1535 }
1536
1537 /* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
1538    position to POS.  If USE is not NULL, the candidate is set as related to
1539    it.  The candidate computation is scheduled on all available positions.  */
1540
1541 static void
1542 add_candidate (struct ivopts_data *data, 
1543                tree base, tree step, bool important, struct iv_use *use)
1544 {
1545   if (ip_normal_pos (data->current_loop))
1546     add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL_TREE);
1547   if (ip_end_pos (data->current_loop))
1548     add_candidate_1 (data, base, step, important, IP_END, use, NULL_TREE);
1549 }
1550
1551 /* Adds standard iv candidates.  */
1552
1553 static void
1554 add_standard_iv_candidates (struct ivopts_data *data)
1555 {
1556   /* Add 0 + 1 * iteration candidate.  */
1557   add_candidate (data,
1558                  build_int_cst (unsigned_intSI_type_node, 0),
1559                  build_int_cst (unsigned_intSI_type_node, 1),
1560                  true, NULL);
1561
1562   /* The same for a long type if it is still fast enought.  */
1563   if (BITS_PER_WORD > 32)
1564     add_candidate (data,
1565                    build_int_cst (unsigned_intDI_type_node, 0),
1566                    build_int_cst (unsigned_intDI_type_node, 1),
1567                    true, NULL);
1568 }
1569
1570
1571 /* Adds candidates bases on the old induction variable IV.  */
1572
1573 static void
1574 add_old_iv_candidates (struct ivopts_data *data, struct iv *iv)
1575 {
1576   tree phi, def;
1577   struct iv_cand *cand;
1578
1579   add_candidate (data, iv->base, iv->step, true, NULL);
1580
1581   /* The same, but with initial value zero.  */
1582   add_candidate (data,
1583                  build_int_cst (TREE_TYPE (iv->base), 0),
1584                  iv->step, true, NULL);
1585
1586   phi = SSA_NAME_DEF_STMT (iv->ssa_name);
1587   if (TREE_CODE (phi) == PHI_NODE)
1588     {
1589       /* Additionally record the possibility of leaving the original iv
1590          untouched.  */
1591       def = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (data->current_loop));
1592       cand = add_candidate_1 (data,
1593                               iv->base, iv->step, true, IP_ORIGINAL, NULL,
1594                               SSA_NAME_DEF_STMT (def));
1595       cand->var_before = iv->ssa_name;
1596       cand->var_after = def;
1597     }
1598 }
1599
1600 /* Adds candidates based on the old induction variables.  */
1601
1602 static void
1603 add_old_ivs_candidates (struct ivopts_data *data)
1604 {
1605   unsigned i;
1606   struct iv *iv;
1607
1608   EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i,
1609     {
1610       iv = ver_info (data, i)->iv;
1611       if (iv && iv->biv_p && !zero_p (iv->step))
1612         add_old_iv_candidates (data, iv);
1613     });
1614 }
1615
1616 /* Adds candidates based on the value of the induction variable IV and USE.  */
1617
1618 static void
1619 add_iv_value_candidates (struct ivopts_data *data,
1620                          struct iv *iv, struct iv_use *use)
1621 {
1622   add_candidate (data, iv->base, iv->step, false, use);
1623
1624   /* The same, but with initial value zero.  */
1625   add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
1626                  iv->step, false, use);
1627 }
1628
1629 /* Adds candidates based on the address IV and USE.  */
1630
1631 static void
1632 add_address_candidates (struct ivopts_data *data,
1633                         struct iv *iv, struct iv_use *use)
1634 {
1635   tree base, abase, tmp, *act;
1636
1637   /* First, the trivial choices.  */
1638   add_iv_value_candidates (data, iv, use);
1639
1640   /* Second, try removing the COMPONENT_REFs.  */
1641   if (TREE_CODE (iv->base) == ADDR_EXPR)
1642     {
1643       base = TREE_OPERAND (iv->base, 0);
1644       while (TREE_CODE (base) == COMPONENT_REF
1645              || (TREE_CODE (base) == ARRAY_REF
1646                  && TREE_CODE (TREE_OPERAND (base, 1)) == INTEGER_CST))
1647         base = TREE_OPERAND (base, 0);
1648
1649       if (base != TREE_OPERAND (iv->base, 0))
1650         { 
1651           if (TREE_CODE (base) == INDIRECT_REF)
1652             base = TREE_OPERAND (base, 0);
1653           else
1654             base = build_addr (base);
1655           add_candidate (data, base, iv->step, false, use);
1656         }
1657     }
1658
1659   /* Third, try removing the constant offset.  */
1660   abase = iv->base;
1661   while (TREE_CODE (abase) == PLUS_EXPR
1662          && TREE_CODE (TREE_OPERAND (abase, 1)) != INTEGER_CST)
1663     abase = TREE_OPERAND (abase, 0);
1664   /* We found the offset, so make the copy of the non-shared part and
1665      remove it.  */
1666   if (TREE_CODE (abase) == PLUS_EXPR)
1667     {
1668       tmp = iv->base;
1669       act = &base;
1670
1671       for (tmp = iv->base; tmp != abase; tmp = TREE_OPERAND (tmp, 0))
1672         {
1673           *act = build2 (PLUS_EXPR, TREE_TYPE (tmp),
1674                          NULL_TREE, TREE_OPERAND (tmp, 1));
1675           act = &TREE_OPERAND (*act, 0);
1676         }
1677       *act = TREE_OPERAND (tmp, 0);
1678
1679       add_candidate (data, base, iv->step, false, use);
1680     }
1681 }
1682
1683 /* Possibly adds pseudocandidate for replacing the final value of USE by
1684    a direct computation.  */
1685
1686 static void
1687 add_iv_outer_candidates (struct ivopts_data *data, struct iv_use *use)
1688 {
1689   struct tree_niter_desc *niter;
1690   struct loop *loop = data->current_loop;
1691
1692   /* We must know where we exit the loop and how many times does it roll.  */
1693   if (!single_dom_exit (loop))
1694     return;
1695
1696   niter = &loop_data (loop)->niter;
1697   if (!niter->niter
1698       || !operand_equal_p (niter->assumptions, boolean_true_node, 0)
1699       || !operand_equal_p (niter->may_be_zero, boolean_false_node, 0))
1700     return;
1701
1702   add_candidate_1 (data, NULL, NULL, false, IP_NORMAL, use, NULL_TREE);
1703 }
1704
1705 /* Adds candidates based on the uses.  */
1706
1707 static void
1708 add_derived_ivs_candidates (struct ivopts_data *data)
1709 {
1710   unsigned i;
1711
1712   for (i = 0; i < n_iv_uses (data); i++)
1713     {
1714       struct iv_use *use = iv_use (data, i);
1715
1716       if (!use)
1717         continue;
1718
1719       switch (use->type)
1720         {
1721         case USE_NONLINEAR_EXPR:
1722         case USE_COMPARE:
1723           /* Just add the ivs based on the value of the iv used here.  */
1724           add_iv_value_candidates (data, use->iv, use);
1725           break;
1726
1727         case USE_OUTER:
1728           add_iv_value_candidates (data, use->iv, use);
1729
1730           /* Additionally, add the pseudocandidate for the possibility to
1731              replace the final value by a direct computation.  */
1732           add_iv_outer_candidates (data, use);
1733           break;
1734
1735         case USE_ADDRESS:
1736           add_address_candidates (data, use->iv, use);
1737           break;
1738
1739         default:
1740           gcc_unreachable ();
1741         }
1742     }
1743 }
1744
1745 /* Finds the candidates for the induction variables.  */
1746
1747 static void
1748 find_iv_candidates (struct ivopts_data *data)
1749 {
1750   /* Add commonly used ivs.  */
1751   add_standard_iv_candidates (data);
1752
1753   /* Add old induction variables.  */
1754   add_old_ivs_candidates (data);
1755
1756   /* Add induction variables derived from uses.  */
1757   add_derived_ivs_candidates (data);
1758 }
1759
1760 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
1761    If consider_all_candidates is true, we use a two-dimensional array, otherwise
1762    we allocate a simple list to every use.  */
1763
1764 static void
1765 alloc_use_cost_map (struct ivopts_data *data)
1766 {
1767   unsigned i, n_imp = 0, size, j;
1768
1769   if (!data->consider_all_candidates)
1770     {
1771       for (i = 0; i < n_iv_cands (data); i++)
1772         {
1773           struct iv_cand *cand = iv_cand (data, i);
1774           if (cand->important)
1775             n_imp++;
1776         }
1777     }
1778
1779   for (i = 0; i < n_iv_uses (data); i++)
1780     {
1781       struct iv_use *use = iv_use (data, i);
1782
1783       if (data->consider_all_candidates)
1784         {
1785           size = n_iv_cands (data);
1786           use->n_map_members = size;
1787         }
1788       else
1789         {
1790           size = n_imp;
1791           EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, size++);
1792           use->n_map_members = 0;
1793         }
1794
1795       use->cost_map = xcalloc (size, sizeof (struct cost_pair));
1796     }
1797 }
1798
1799 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
1800    on invariants DEPENDS_ON.  */
1801
1802 static void
1803 set_use_iv_cost (struct ivopts_data *data,
1804                  struct iv_use *use, struct iv_cand *cand, unsigned cost,
1805                  bitmap depends_on)
1806 {
1807   if (cost == INFTY
1808       && depends_on)
1809     {
1810       BITMAP_XFREE (depends_on);
1811       depends_on = NULL;
1812     }
1813
1814   if (data->consider_all_candidates)
1815     {
1816       use->cost_map[cand->id].cand = cand;
1817       use->cost_map[cand->id].cost = cost;
1818       use->cost_map[cand->id].depends_on = depends_on;
1819       return;
1820     }
1821
1822   if (cost == INFTY)
1823     return;
1824
1825   use->cost_map[use->n_map_members].cand = cand;
1826   use->cost_map[use->n_map_members].cost = cost;
1827   use->cost_map[use->n_map_members].depends_on = depends_on;
1828   use->n_map_members++;
1829 }
1830
1831 /* Gets cost of (USE, CANDIDATE) pair.  Stores the bitmap of dependencies to
1832    DEPENDS_ON.  */
1833
1834 static unsigned
1835 get_use_iv_cost (struct ivopts_data *data,
1836                  struct iv_use *use, struct iv_cand *cand, bitmap *depends_on)
1837 {
1838   unsigned i;
1839
1840   if (!cand)
1841     return INFTY;
1842
1843   if (data->consider_all_candidates)
1844     i = cand->id;
1845   else
1846     {
1847       for (i = 0; i < use->n_map_members; i++)
1848         if (use->cost_map[i].cand == cand)
1849           break;
1850
1851       if (i == use->n_map_members)
1852         return INFTY;
1853     }
1854
1855   if (depends_on)
1856     *depends_on = use->cost_map[i].depends_on;
1857   return use->cost_map[i].cost;
1858 }
1859
1860 /* Returns estimate on cost of computing SEQ.  */
1861
1862 static unsigned
1863 seq_cost (rtx seq)
1864 {
1865   unsigned cost = 0;
1866   rtx set;
1867
1868   for (; seq; seq = NEXT_INSN (seq))
1869     {
1870       set = single_set (seq);
1871       if (set)
1872         cost += rtx_cost (set, SET);
1873       else
1874         cost++;
1875     }
1876
1877   return cost;
1878 }
1879
1880 /* Produce DECL_RTL for object obj so it looks like it is stored in memory.  */
1881 static rtx
1882 produce_memory_decl_rtl (tree obj, int *regno)
1883 {
1884   rtx x;
1885   if (!obj)
1886     abort ();
1887   if (TREE_STATIC (obj) || DECL_EXTERNAL (obj))
1888     {
1889       const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj));
1890       x = gen_rtx_SYMBOL_REF (Pmode, name);
1891     }
1892   else
1893     x = gen_raw_REG (Pmode, (*regno)++);
1894
1895   return gen_rtx_MEM (DECL_MODE (obj), x);
1896 }
1897
1898 /* Prepares decl_rtl for variables referred in *EXPR_P.  Callback for
1899    walk_tree.  DATA contains the actual fake register number.  */
1900
1901 static tree
1902 prepare_decl_rtl (tree *expr_p, int *ws, void *data)
1903 {
1904   tree obj = NULL_TREE;
1905   rtx x = NULL_RTX;
1906   int *regno = data;
1907
1908   switch (TREE_CODE (*expr_p))
1909     {
1910     case ADDR_EXPR:
1911       for (expr_p = &TREE_OPERAND (*expr_p, 0);
1912            (handled_component_p (*expr_p)
1913             || TREE_CODE (*expr_p) == REALPART_EXPR
1914             || TREE_CODE (*expr_p) == IMAGPART_EXPR);
1915            expr_p = &TREE_OPERAND (*expr_p, 0));
1916       obj = *expr_p;
1917       if (DECL_P (obj))
1918         x = produce_memory_decl_rtl (obj, regno);
1919       break;
1920
1921     case SSA_NAME:
1922       *ws = 0;
1923       obj = SSA_NAME_VAR (*expr_p);
1924       if (!DECL_RTL_SET_P (obj))
1925         x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
1926       break;
1927
1928     case VAR_DECL:
1929     case PARM_DECL:
1930     case RESULT_DECL:
1931       *ws = 0;
1932       obj = *expr_p;
1933
1934       if (DECL_RTL_SET_P (obj))
1935         break;
1936
1937       if (DECL_MODE (obj) == BLKmode)
1938         x = produce_memory_decl_rtl (obj, regno);
1939       else
1940         x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
1941
1942       break;
1943
1944     default:
1945       break;
1946     }
1947
1948   if (x)
1949     {
1950       VARRAY_PUSH_GENERIC_PTR_NOGC (decl_rtl_to_reset, obj);
1951       SET_DECL_RTL (obj, x);
1952     }
1953
1954   return NULL_TREE;
1955 }
1956
1957 /* Determines cost of the computation of EXPR.  */
1958
1959 static unsigned
1960 computation_cost (tree expr)
1961 {
1962   rtx seq, rslt;
1963   tree type = TREE_TYPE (expr);
1964   unsigned cost;
1965   int regno = 0;
1966
1967   walk_tree (&expr, prepare_decl_rtl, &regno, NULL);
1968   start_sequence ();
1969   rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL);
1970   seq = get_insns ();
1971   end_sequence ();
1972
1973   cost = seq_cost (seq);
1974   if (GET_CODE (rslt) == MEM)
1975     cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type));
1976
1977   return cost;
1978 }
1979
1980 /* Returns variable containing the value of candidate CAND at statement AT.  */
1981
1982 static tree
1983 var_at_stmt (struct loop *loop, struct iv_cand *cand, tree stmt)
1984 {
1985   if (stmt_after_increment (loop, cand, stmt))
1986     return cand->var_after;
1987   else
1988     return cand->var_before;
1989 }
1990
1991 /* Determines the expression by that USE is expressed from induction variable
1992    CAND at statement AT in LOOP.  */
1993
1994 static tree
1995 get_computation_at (struct loop *loop,
1996                     struct iv_use *use, struct iv_cand *cand, tree at)
1997 {
1998   tree ubase = unsave_expr_now (use->iv->base);
1999   tree ustep = unsave_expr_now (use->iv->step);
2000   tree cbase = unsave_expr_now (cand->iv->base);
2001   tree cstep = unsave_expr_now (cand->iv->step);
2002   tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
2003   tree uutype;
2004   tree expr, delta;
2005   tree ratio;
2006   unsigned HOST_WIDE_INT ustepi, cstepi;
2007   HOST_WIDE_INT ratioi;
2008
2009   if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
2010     {
2011       /* We do not have a precision to express the values of use.  */
2012       return NULL_TREE;
2013     }
2014
2015   expr = var_at_stmt (loop, cand, at);
2016
2017   if (TREE_TYPE (expr) != ctype)
2018     {
2019       /* This may happen with the original ivs.  */
2020       expr = fold_convert (ctype, expr);
2021     }
2022
2023   if (TYPE_UNSIGNED (utype))
2024     uutype = utype;
2025   else
2026     {
2027       uutype = unsigned_type_for (utype);
2028       ubase = fold_convert (uutype, ubase);
2029       ustep = fold_convert (uutype, ustep);
2030     }
2031
2032   if (uutype != ctype)
2033     {
2034       expr = fold_convert (uutype, expr);
2035       cbase = fold_convert (uutype, cbase);
2036       cstep = fold_convert (uutype, cstep);
2037     }
2038
2039   if (!cst_and_fits_in_hwi (cstep)
2040       || !cst_and_fits_in_hwi (ustep))
2041     return NULL_TREE;
2042
2043   ustepi = int_cst_value (ustep);
2044   cstepi = int_cst_value (cstep);
2045
2046   if (!divide (TYPE_PRECISION (uutype), ustepi, cstepi, &ratioi))
2047     {
2048       /* TODO maybe consider case when ustep divides cstep and the ratio is
2049          a power of 2 (so that the division is fast to execute)?  We would
2050          need to be much more careful with overflows etc. then.  */
2051       return NULL_TREE;
2052     }
2053
2054   /* We may need to shift the value if we are after the increment.  */
2055   if (stmt_after_increment (loop, cand, at))
2056     cbase = fold (build2 (PLUS_EXPR, uutype, cbase, cstep));
2057
2058   /* use = ubase + ratio * (var - cbase).  If either cbase is a constant
2059      or |ratio| == 1, it is better to handle this like
2060      
2061      ubase - ratio * cbase + ratio * var.  */
2062
2063   if (ratioi == 1)
2064     {
2065       delta = fold (build2 (MINUS_EXPR, uutype, ubase, cbase));
2066       expr = fold (build2 (PLUS_EXPR, uutype, expr, delta));
2067     }
2068   else if (ratioi == -1)
2069     {
2070       delta = fold (build2 (PLUS_EXPR, uutype, ubase, cbase));
2071       expr = fold (build2 (MINUS_EXPR, uutype, delta, expr));
2072     }
2073   else if (TREE_CODE (cbase) == INTEGER_CST)
2074     {
2075       ratio = build_int_cst_type (uutype, ratioi);
2076       delta = fold (build2 (MULT_EXPR, uutype, ratio, cbase));
2077       delta = fold (build2 (MINUS_EXPR, uutype, ubase, delta));
2078       expr = fold (build2 (MULT_EXPR, uutype, ratio, expr));
2079       expr = fold (build2 (PLUS_EXPR, uutype, delta, expr));
2080     }
2081   else
2082     {
2083       expr = fold (build2 (MINUS_EXPR, uutype, expr, cbase));
2084       ratio = build_int_cst_type (uutype, ratioi);
2085       expr = fold (build2 (MULT_EXPR, uutype, ratio, expr));
2086       expr = fold (build2 (PLUS_EXPR, uutype, ubase, expr));
2087     }
2088
2089   return fold_convert (utype, expr);
2090 }
2091
2092 /* Determines the expression by that USE is expressed from induction variable
2093    CAND in LOOP.  */
2094
2095 static tree
2096 get_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand)
2097 {
2098   return get_computation_at (loop, use, cand, use->stmt);
2099 }
2100
2101 /* Strips constant offsets from EXPR and adds them to OFFSET.  */
2102
2103 static void
2104 strip_offset (tree *expr, unsigned HOST_WIDE_INT *offset)
2105 {
2106   tree op0, op1;
2107   enum tree_code code;
2108   
2109   while (1)
2110     {
2111       if (cst_and_fits_in_hwi (*expr))
2112         {
2113           *offset += int_cst_value (*expr);
2114           *expr = integer_zero_node;
2115           return;
2116         }
2117
2118       code = TREE_CODE (*expr);
2119      
2120       if (code != PLUS_EXPR && code != MINUS_EXPR)
2121         return;
2122
2123       op0 = TREE_OPERAND (*expr, 0);
2124       op1 = TREE_OPERAND (*expr, 1);
2125
2126       if (cst_and_fits_in_hwi (op1))
2127         {
2128           if (code == PLUS_EXPR)
2129             *offset += int_cst_value (op1);
2130           else
2131             *offset -= int_cst_value (op1);
2132
2133           *expr = op0;
2134           continue;
2135         }
2136
2137       if (code != PLUS_EXPR)
2138         return;
2139
2140       if (!cst_and_fits_in_hwi (op0))
2141         return;
2142
2143       *offset += int_cst_value (op0);
2144       *expr = op1;
2145     }
2146 }
2147
2148 /* Returns cost of addition in MODE.  */
2149
2150 static unsigned
2151 add_cost (enum machine_mode mode)
2152 {
2153   static unsigned costs[NUM_MACHINE_MODES];
2154   rtx seq;
2155   unsigned cost;
2156
2157   if (costs[mode])
2158     return costs[mode];
2159
2160   start_sequence ();
2161   force_operand (gen_rtx_fmt_ee (PLUS, mode,
2162                                  gen_raw_REG (mode, FIRST_PSEUDO_REGISTER),
2163                                  gen_raw_REG (mode, FIRST_PSEUDO_REGISTER + 1)),
2164                  NULL_RTX);
2165   seq = get_insns ();
2166   end_sequence ();
2167
2168   cost = seq_cost (seq);
2169   if (!cost)
2170     cost = 1;
2171
2172   costs[mode] = cost;
2173       
2174   if (dump_file && (dump_flags & TDF_DETAILS))
2175     fprintf (dump_file, "Addition in %s costs %d\n",
2176              GET_MODE_NAME (mode), cost);
2177   return cost;
2178 }
2179
2180 /* Entry in a hashtable of already known costs for multiplication.  */
2181 struct mbc_entry
2182 {
2183   HOST_WIDE_INT cst;            /* The constant to multiply by.  */
2184   enum machine_mode mode;       /* In mode.  */
2185   unsigned cost;                /* The cost.  */
2186 };
2187
2188 /* Counts hash value for the ENTRY.  */
2189
2190 static hashval_t
2191 mbc_entry_hash (const void *entry)
2192 {
2193   const struct mbc_entry *e = entry;
2194
2195   return 57 * (hashval_t) e->mode + (hashval_t) (e->cst % 877);
2196 }
2197
2198 /* Compares the hash table entries ENTRY1 and ENTRY2.  */
2199
2200 static int
2201 mbc_entry_eq (const void *entry1, const void *entry2)
2202 {
2203   const struct mbc_entry *e1 = entry1;
2204   const struct mbc_entry *e2 = entry2;
2205
2206   return (e1->mode == e2->mode
2207           && e1->cst == e2->cst);
2208 }
2209
2210 /* Returns cost of multiplication by constant CST in MODE.  */
2211
2212 static unsigned
2213 multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode)
2214 {
2215   static htab_t costs;
2216   struct mbc_entry **cached, act;
2217   rtx seq;
2218   unsigned cost;
2219
2220   if (!costs)
2221     costs = htab_create (100, mbc_entry_hash, mbc_entry_eq, free);
2222
2223   act.mode = mode;
2224   act.cst = cst;
2225   cached = (struct mbc_entry **) htab_find_slot (costs, &act, INSERT);
2226   if (*cached)
2227     return (*cached)->cost;
2228
2229   *cached = xmalloc (sizeof (struct mbc_entry));
2230   (*cached)->mode = mode;
2231   (*cached)->cst = cst;
2232
2233   start_sequence ();
2234   expand_mult (mode, gen_raw_REG (mode, FIRST_PSEUDO_REGISTER), GEN_INT (cst),
2235                NULL_RTX, 0);
2236   seq = get_insns ();
2237   end_sequence ();
2238   
2239   cost = seq_cost (seq);
2240
2241   if (dump_file && (dump_flags & TDF_DETAILS))
2242     fprintf (dump_file, "Multiplication by %d in %s costs %d\n",
2243              (int) cst, GET_MODE_NAME (mode), cost);
2244
2245   (*cached)->cost = cost;
2246
2247   return cost;
2248 }
2249
2250 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
2251    If SYMBOL_PRESENT is false, symbol is omitted.  If VAR_PRESENT is false,
2252    variable is omitted.  The created memory accesses MODE.
2253    
2254    TODO -- there must be some better way.  This all is quite crude.  */
2255
2256 static unsigned
2257 get_address_cost (bool symbol_present, bool var_present,
2258                   unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio)
2259 {
2260 #define MAX_RATIO 128
2261   static sbitmap valid_mult;
2262   static HOST_WIDE_INT rat, off;
2263   static HOST_WIDE_INT min_offset, max_offset;
2264   static unsigned costs[2][2][2][2];
2265   unsigned cost, acost;
2266   rtx seq, addr, base;
2267   bool offset_p, ratio_p;
2268   rtx reg1;
2269   HOST_WIDE_INT s_offset;
2270   unsigned HOST_WIDE_INT mask;
2271   unsigned bits;
2272
2273   if (!valid_mult)
2274     {
2275       HOST_WIDE_INT i;
2276
2277       reg1 = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER);
2278
2279       addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
2280       for (i = 1; i <= 1 << 20; i <<= 1)
2281         {
2282           XEXP (addr, 1) = GEN_INT (i);
2283           if (!memory_address_p (Pmode, addr))
2284             break;
2285         }
2286       max_offset = i >> 1;
2287       off = max_offset;
2288
2289       for (i = 1; i <= 1 << 20; i <<= 1)
2290         {
2291           XEXP (addr, 1) = GEN_INT (-i);
2292           if (!memory_address_p (Pmode, addr))
2293             break;
2294         }
2295       min_offset = -(i >> 1);
2296
2297       if (dump_file && (dump_flags & TDF_DETAILS))
2298         {
2299           fprintf (dump_file, "get_address_cost:\n");
2300           fprintf (dump_file, "  min offset %d\n", (int) min_offset);
2301           fprintf (dump_file, "  max offset %d\n", (int) max_offset);
2302         }
2303
2304       valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1);
2305       sbitmap_zero (valid_mult);
2306       rat = 1;
2307       addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX);
2308       for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
2309         {
2310           XEXP (addr, 1) = GEN_INT (i);
2311           if (memory_address_p (Pmode, addr))
2312             {
2313               SET_BIT (valid_mult, i + MAX_RATIO);
2314               rat = i;
2315             }
2316         }
2317
2318       if (dump_file && (dump_flags & TDF_DETAILS))
2319         {
2320           fprintf (dump_file, "  allowed multipliers:");
2321           for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
2322             if (TEST_BIT (valid_mult, i + MAX_RATIO))
2323               fprintf (dump_file, " %d", (int) i);
2324           fprintf (dump_file, "\n");
2325           fprintf (dump_file, "\n");
2326         }
2327     }
2328
2329   bits = GET_MODE_BITSIZE (Pmode);
2330   mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
2331   offset &= mask;
2332   if ((offset >> (bits - 1) & 1))
2333     offset |= ~mask;
2334   s_offset = offset;
2335
2336   cost = 0;
2337   offset_p = (min_offset <= s_offset && s_offset <= max_offset);
2338   ratio_p = (ratio != 1
2339              && -MAX_RATIO <= ratio && ratio <= MAX_RATIO
2340              && TEST_BIT (valid_mult, ratio + MAX_RATIO));
2341
2342   if (ratio != 1 && !ratio_p)
2343     cost += multiply_by_cost (ratio, Pmode);
2344
2345   if (s_offset && !offset_p && !symbol_present)
2346     {
2347       cost += add_cost (Pmode);
2348       var_present = true;
2349     }
2350
2351   acost = costs[symbol_present][var_present][offset_p][ratio_p];
2352   if (!acost)
2353     {
2354       acost = 0;
2355       
2356       addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER);
2357       reg1 = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 1);
2358       if (ratio_p)
2359         addr = gen_rtx_fmt_ee (MULT, Pmode, addr, GEN_INT (rat));
2360
2361       if (symbol_present)
2362         {
2363           base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
2364           if (offset_p)
2365             base = gen_rtx_fmt_e (CONST, Pmode,
2366                                   gen_rtx_fmt_ee (PLUS, Pmode,
2367                                                   base,
2368                                                   GEN_INT (off)));
2369           if (var_present)
2370             base = gen_rtx_fmt_ee (PLUS, Pmode, reg1, base);
2371         }
2372
2373       else if (var_present)
2374         {
2375           base = reg1;
2376           if (offset_p)
2377             base = gen_rtx_fmt_ee (PLUS, Pmode, base, GEN_INT (off));
2378         }
2379       else if (offset_p)
2380         base = GEN_INT (off);
2381       else
2382         base = NULL_RTX;
2383     
2384       if (base)
2385         addr = gen_rtx_fmt_ee (PLUS, Pmode, base, addr);
2386   
2387       start_sequence ();
2388       addr = memory_address (Pmode, addr);
2389       seq = get_insns ();
2390       end_sequence ();
2391   
2392       acost = seq_cost (seq);
2393       acost += address_cost (addr, Pmode);
2394
2395       if (!acost)
2396         acost = 1;
2397       costs[symbol_present][var_present][offset_p][ratio_p] = acost;
2398     }
2399
2400   return cost + acost;
2401 }
2402
2403 /* Records invariants in *EXPR_P.  Callback for walk_tree.  DATA contains
2404    the bitmap to that we should store it.  */
2405
2406 static struct ivopts_data *fd_ivopts_data;
2407 static tree
2408 find_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
2409 {
2410   bitmap *depends_on = data;
2411   struct version_info *info;
2412
2413   if (TREE_CODE (*expr_p) != SSA_NAME)
2414     return NULL_TREE;
2415   info = name_info (fd_ivopts_data, *expr_p);
2416
2417   if (!info->inv_id || info->has_nonlin_use)
2418     return NULL_TREE;
2419
2420   if (!*depends_on)
2421     *depends_on = BITMAP_XMALLOC ();
2422   bitmap_set_bit (*depends_on, info->inv_id);
2423
2424   return NULL_TREE;
2425 }
2426
2427 /* Estimates cost of forcing EXPR into variable.  DEPENDS_ON is a set of the
2428    invariants the computation depends on.  */
2429
2430 static unsigned
2431 force_var_cost (struct ivopts_data *data,
2432                 tree expr, bitmap *depends_on)
2433 {
2434   static bool costs_initialized = false;
2435   static unsigned integer_cost;
2436   static unsigned symbol_cost;
2437   static unsigned address_cost;
2438
2439   if (!costs_initialized)
2440     {
2441       tree var = create_tmp_var_raw (integer_type_node, "test_var");
2442       rtx x = gen_rtx_MEM (DECL_MODE (var),
2443                            gen_rtx_SYMBOL_REF (Pmode, "test_var"));
2444       tree addr;
2445       tree type = build_pointer_type (integer_type_node);
2446
2447       integer_cost = computation_cost (build_int_cst_type (integer_type_node,
2448                                                            2000));
2449
2450       SET_DECL_RTL (var, x);
2451       TREE_STATIC (var) = 1;
2452       addr = build1 (ADDR_EXPR, type, var);
2453       symbol_cost = computation_cost (addr) + 1;
2454
2455       address_cost
2456         = computation_cost (build2 (PLUS_EXPR, type,
2457                                     addr,
2458                                     build_int_cst_type (type, 2000))) + 1;
2459       if (dump_file && (dump_flags & TDF_DETAILS))
2460         {
2461           fprintf (dump_file, "force_var_cost:\n");
2462           fprintf (dump_file, "  integer %d\n", (int) integer_cost);
2463           fprintf (dump_file, "  symbol %d\n", (int) symbol_cost);
2464           fprintf (dump_file, "  address %d\n", (int) address_cost);
2465           fprintf (dump_file, "  other %d\n", (int) target_spill_cost);
2466           fprintf (dump_file, "\n");
2467         }
2468
2469       costs_initialized = true;
2470     }
2471
2472   if (depends_on)
2473     {
2474       fd_ivopts_data = data;
2475       walk_tree (&expr, find_depends, depends_on, NULL);
2476     }
2477
2478   if (SSA_VAR_P (expr))
2479     return 0;
2480
2481   if (TREE_INVARIANT (expr))
2482     {
2483       if (TREE_CODE (expr) == INTEGER_CST)
2484         return integer_cost;
2485
2486       if (TREE_CODE (expr) == ADDR_EXPR)
2487         {
2488           tree obj = TREE_OPERAND (expr, 0);
2489
2490           if (TREE_CODE (obj) == VAR_DECL
2491               || TREE_CODE (obj) == PARM_DECL
2492               || TREE_CODE (obj) == RESULT_DECL)
2493             return symbol_cost;
2494         }
2495
2496       return address_cost;
2497     }
2498
2499   /* Just an arbitrary value, FIXME.  */
2500   return target_spill_cost;
2501 }
2502
2503 /* Peels a single layer of ADDR.  If DIFF is not NULL, do it only if the
2504    offset is constant and add the offset to DIFF.  */
2505
2506 static tree
2507 peel_address (tree addr, unsigned HOST_WIDE_INT *diff)
2508 {
2509   tree off, size;
2510   HOST_WIDE_INT bit_offset;
2511
2512   switch (TREE_CODE (addr))
2513     {
2514     case SSA_NAME:
2515     case INDIRECT_REF:
2516     case BIT_FIELD_REF:
2517     case VAR_DECL:
2518     case PARM_DECL:
2519     case RESULT_DECL:
2520     case STRING_CST:
2521     case REALPART_EXPR:
2522     case IMAGPART_EXPR:
2523       return NULL_TREE;
2524
2525     case COMPONENT_REF:
2526       off = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (addr, 1));
2527       bit_offset = TREE_INT_CST_LOW (off);
2528
2529       gcc_assert ((bit_offset % BITS_PER_UNIT) == 0);
2530       
2531       if (diff)
2532         *diff += bit_offset / BITS_PER_UNIT;
2533
2534       return TREE_OPERAND (addr, 0);
2535
2536     case ARRAY_REF:
2537       off = TREE_OPERAND (addr, 1);
2538
2539       if (diff)
2540         {
2541           if (!cst_and_fits_in_hwi (off))
2542             return NULL_TREE;
2543
2544           size = TYPE_SIZE_UNIT (TREE_TYPE (addr));
2545           if (!cst_and_fits_in_hwi (size))
2546             return NULL_TREE;
2547
2548           *diff += TREE_INT_CST_LOW (off) * TREE_INT_CST_LOW (size);
2549         }
2550
2551       return TREE_OPERAND (addr, 0);
2552
2553     default:
2554       gcc_unreachable ();
2555     }
2556 }
2557
2558 /* Checks whether E1 and E2 have constant difference, and if they do,
2559    store it in *DIFF.  */
2560
2561 static bool
2562 ptr_difference_const (tree e1, tree e2, unsigned HOST_WIDE_INT *diff)
2563 {
2564   int d1 = 0, d2 = 0;
2565   tree x;
2566   unsigned HOST_WIDE_INT delta1 = 0, delta2 = 0;
2567
2568   /* Find depths of E1 and E2.  */
2569   for (x = e1; x; x = peel_address (x, NULL))
2570     d1++;
2571   for (x = e2; x; x = peel_address (x, NULL))
2572     d2++;
2573
2574   for (; e1 && d1 > d2; e1 = peel_address (e1, &delta1))
2575     d1--;
2576   for (; e2 && d2 > d1; e2 = peel_address (e2, &delta2))
2577     d2--;
2578
2579   while (e1 && e2 && !operand_equal_p (e1, e2, 0))
2580     {
2581       e1 = peel_address (e1, &delta1);
2582       e2 = peel_address (e2, &delta1);
2583     }
2584
2585   if (!e1 || !e2)
2586     return false;
2587
2588   *diff = delta1 - delta2;
2589   return true;
2590 }
2591
2592 /* Estimates cost of expressing address ADDR  as var + symbol + offset.  The
2593    value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
2594    to false if the corresponding part is missing.  DEPENDS_ON is a set of the
2595    invariants the computation depends on.  */
2596
2597 static unsigned
2598 split_address_cost (struct ivopts_data *data,
2599                     tree addr, bool *symbol_present, bool *var_present,
2600                     unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
2601 {
2602   tree core = addr;
2603
2604   while (core
2605          && TREE_CODE (core) != VAR_DECL)
2606     core = peel_address (core, offset);
2607
2608   if (!core)
2609     {
2610       *symbol_present = false;
2611       *var_present = true;
2612       fd_ivopts_data = data;
2613       walk_tree (&addr, find_depends, depends_on, NULL);
2614       return target_spill_cost;
2615     }  
2616           
2617   if (TREE_STATIC (core)
2618       || DECL_EXTERNAL (core))
2619     {
2620       *symbol_present = true;
2621       *var_present = false;
2622       return 0;
2623     }
2624       
2625   *symbol_present = false;
2626   *var_present = true;
2627   return 0;
2628 }
2629
2630 /* Estimates cost of expressing difference of addresses E1 - E2 as
2631    var + symbol + offset.  The value of offset is added to OFFSET,
2632    SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
2633    part is missing.  DEPENDS_ON is a set of the invariants the computation
2634    depends on.  */
2635
2636 static unsigned
2637 ptr_difference_cost (struct ivopts_data *data,
2638                      tree e1, tree e2, bool *symbol_present, bool *var_present,
2639                      unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
2640 {
2641   unsigned HOST_WIDE_INT diff = 0;
2642   unsigned cost;
2643
2644   gcc_assert (TREE_CODE (e1) == ADDR_EXPR);
2645
2646   if (TREE_CODE (e2) == ADDR_EXPR
2647       && ptr_difference_const (TREE_OPERAND (e1, 0),
2648                                TREE_OPERAND (e2, 0), &diff))
2649     {
2650       *offset += diff;
2651       *symbol_present = false;
2652       *var_present = false;
2653       return 0;
2654     }
2655
2656   if (e2 == integer_zero_node)
2657     return split_address_cost (data, TREE_OPERAND (e1, 0),
2658                                symbol_present, var_present, offset, depends_on);
2659
2660   *symbol_present = false;
2661   *var_present = true;
2662   
2663   cost = force_var_cost (data, e1, depends_on);
2664   cost += force_var_cost (data, e2, depends_on);
2665   cost += add_cost (Pmode);
2666
2667   return cost;
2668 }
2669
2670 /* Estimates cost of expressing difference E1 - E2 as
2671    var + symbol + offset.  The value of offset is added to OFFSET,
2672    SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
2673    part is missing.  DEPENDS_ON is a set of the invariants the computation
2674    depends on.  */
2675
2676 static unsigned
2677 difference_cost (struct ivopts_data *data,
2678                  tree e1, tree e2, bool *symbol_present, bool *var_present,
2679                  unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
2680 {
2681   unsigned cost;
2682   enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
2683
2684   strip_offset (&e1, offset);
2685   *offset = -*offset;
2686   strip_offset (&e2, offset);
2687   *offset = -*offset;
2688
2689   if (TREE_CODE (e1) == ADDR_EXPR)
2690     return ptr_difference_cost (data, e1, e2, symbol_present, var_present, offset,
2691                                 depends_on);
2692   *symbol_present = false;
2693
2694   if (operand_equal_p (e1, e2, 0))
2695     {
2696       *var_present = false;
2697       return 0;
2698     }
2699   *var_present = true;
2700   if (zero_p (e2))
2701     return force_var_cost (data, e1, depends_on);
2702
2703   if (zero_p (e1))
2704     {
2705       cost = force_var_cost (data, e2, depends_on);
2706       cost += multiply_by_cost (-1, mode);
2707
2708       return cost;
2709     }
2710
2711   cost = force_var_cost (data, e1, depends_on);
2712   cost += force_var_cost (data, e2, depends_on);
2713   cost += add_cost (mode);
2714
2715   return cost;
2716 }
2717
2718 /* Determines the cost of the computation by that USE is expressed
2719    from induction variable CAND.  If ADDRESS_P is true, we just need
2720    to create an address from it, otherwise we want to get it into
2721    register.  A set of invariants we depend on is stored in
2722    DEPENDS_ON.  AT is the statement at that the value is computed.  */
2723
2724 static unsigned
2725 get_computation_cost_at (struct ivopts_data *data,
2726                          struct iv_use *use, struct iv_cand *cand,
2727                          bool address_p, bitmap *depends_on, tree at)
2728 {
2729   tree ubase = use->iv->base, ustep = use->iv->step;
2730   tree cbase, cstep;
2731   tree utype = TREE_TYPE (ubase), ctype;
2732   unsigned HOST_WIDE_INT ustepi, cstepi, offset = 0;
2733   HOST_WIDE_INT ratio, aratio;
2734   bool var_present, symbol_present;
2735   unsigned cost = 0, n_sums;
2736
2737   *depends_on = NULL;
2738
2739   /* Only consider real candidates.  */
2740   if (!cand->iv)
2741     return INFTY;
2742
2743   cbase = cand->iv->base;
2744   cstep = cand->iv->step;
2745   ctype = TREE_TYPE (cbase);
2746
2747   if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
2748     {
2749       /* We do not have a precision to express the values of use.  */
2750       return INFTY;
2751     }
2752
2753   if (!cst_and_fits_in_hwi (ustep)
2754       || !cst_and_fits_in_hwi (cstep))
2755     return INFTY;
2756
2757   if (TREE_CODE (ubase) == INTEGER_CST
2758       && !cst_and_fits_in_hwi (ubase))
2759     goto fallback;
2760
2761   if (TREE_CODE (cbase) == INTEGER_CST
2762       && !cst_and_fits_in_hwi (cbase))
2763     goto fallback;
2764     
2765   ustepi = int_cst_value (ustep);
2766   cstepi = int_cst_value (cstep);
2767
2768   if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
2769     {
2770       /* TODO -- add direct handling of this case.  */
2771       goto fallback;
2772     }
2773
2774   if (!divide (TYPE_PRECISION (utype), ustepi, cstepi, &ratio))
2775     return INFTY;
2776
2777   /* use = ubase + ratio * (var - cbase).  If either cbase is a constant
2778      or ratio == 1, it is better to handle this like
2779      
2780      ubase - ratio * cbase + ratio * var
2781      
2782      (also holds in the case ratio == -1, TODO.  */
2783
2784   if (TREE_CODE (cbase) == INTEGER_CST)
2785     {
2786       offset = - ratio * int_cst_value (cbase); 
2787       cost += difference_cost (data,
2788                                ubase, integer_zero_node,
2789                                &symbol_present, &var_present, &offset,
2790                                depends_on);
2791     }
2792   else if (ratio == 1)
2793     {
2794       cost += difference_cost (data,
2795                                ubase, cbase,
2796                                &symbol_present, &var_present, &offset,
2797                                depends_on);
2798     }
2799   else
2800     {
2801       cost += force_var_cost (data, cbase, depends_on);
2802       cost += add_cost (TYPE_MODE (ctype));
2803       cost += difference_cost (data,
2804                                ubase, integer_zero_node,
2805                                &symbol_present, &var_present, &offset,
2806                                depends_on);
2807     }
2808
2809   /* If we are after the increment, the value of the candidate is higher by
2810      one iteration.  */
2811   if (stmt_after_increment (data->current_loop, cand, at))
2812     offset -= ratio * cstepi;
2813
2814   /* Now the computation is in shape symbol + var1 + const + ratio * var2.
2815      (symbol/var/const parts may be omitted).  If we are looking for an address,
2816      find the cost of addressing this.  */
2817   if (address_p)
2818     return get_address_cost (symbol_present, var_present, offset, ratio);
2819
2820   /* Otherwise estimate the costs for computing the expression.  */
2821   aratio = ratio > 0 ? ratio : -ratio;
2822   if (!symbol_present && !var_present && !offset)
2823     {
2824       if (ratio != 1)
2825         cost += multiply_by_cost (ratio, TYPE_MODE (ctype));
2826
2827       return cost;
2828     }
2829
2830   if (aratio != 1)
2831     cost += multiply_by_cost (aratio, TYPE_MODE (ctype));
2832
2833   n_sums = 1;
2834   if (var_present
2835       /* Symbol + offset should be compile-time computable.  */
2836       && (symbol_present || offset))
2837     n_sums++;
2838
2839   return cost + n_sums * add_cost (TYPE_MODE (ctype));
2840
2841 fallback:
2842   {
2843     /* Just get the expression, expand it and measure the cost.  */
2844     tree comp = get_computation_at (data->current_loop, use, cand, at);
2845
2846     if (!comp)
2847       return INFTY;
2848
2849     if (address_p)
2850       comp = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (comp)), comp);
2851
2852     return computation_cost (comp);
2853   }
2854 }
2855
2856 /* Determines the cost of the computation by that USE is expressed
2857    from induction variable CAND.  If ADDRESS_P is true, we just need
2858    to create an address from it, otherwise we want to get it into
2859    register.  A set of invariants we depend on is stored in
2860    DEPENDS_ON.  */
2861
2862 static unsigned
2863 get_computation_cost (struct ivopts_data *data,
2864                       struct iv_use *use, struct iv_cand *cand,
2865                       bool address_p, bitmap *depends_on)
2866 {
2867   return get_computation_cost_at (data,
2868                                   use, cand, address_p, depends_on, use->stmt);
2869 }
2870
2871 /* Determines cost of basing replacement of USE on CAND in a generic
2872    expression.  */
2873
2874 static void
2875 determine_use_iv_cost_generic (struct ivopts_data *data,
2876                                struct iv_use *use, struct iv_cand *cand)
2877 {
2878   bitmap depends_on;
2879   unsigned cost = get_computation_cost (data, use, cand, false, &depends_on);
2880
2881   set_use_iv_cost (data, use, cand, cost, depends_on);
2882 }
2883
2884 /* Determines cost of basing replacement of USE on CAND in an address.  */
2885
2886 static void
2887 determine_use_iv_cost_address (struct ivopts_data *data,
2888                                struct iv_use *use, struct iv_cand *cand)
2889 {
2890   bitmap depends_on;
2891   unsigned cost = get_computation_cost (data, use, cand, true, &depends_on);
2892
2893   set_use_iv_cost (data, use, cand, cost, depends_on);
2894 }
2895
2896 /* Computes value of induction variable IV in iteration NITER.  */
2897
2898 static tree
2899 iv_value (struct iv *iv, tree niter)
2900 {
2901   tree val;
2902   tree type = TREE_TYPE (iv->base);
2903
2904   niter = fold_convert (type, niter);
2905   val = fold (build2 (MULT_EXPR, type, iv->step, unsave_expr_now (niter)));
2906
2907   return fold (build2 (PLUS_EXPR, type, iv->base, val));
2908 }
2909
2910 /* Computes value of candidate CAND at position AT in iteration NITER.  */
2911
2912 static tree
2913 cand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter)
2914 {
2915   tree val = iv_value (cand->iv, niter);
2916   tree type = TREE_TYPE (cand->iv->base);
2917
2918   if (stmt_after_increment (loop, cand, at))
2919     val = fold (build2 (PLUS_EXPR, type, val, cand->iv->step));
2920
2921   return val;
2922 }
2923
2924 /* Check whether it is possible to express the condition in USE by comparison
2925    of candidate CAND.  If so, store the comparison code to COMPARE and the
2926    value compared with to BOUND.  */
2927
2928 static bool
2929 may_eliminate_iv (struct loop *loop,
2930                   struct iv_use *use, struct iv_cand *cand,
2931                   enum tree_code *compare, tree *bound)
2932 {
2933   edge exit;
2934   struct tree_niter_desc *niter, new_niter;
2935   tree wider_type, type, base;
2936
2937   /* For now just very primitive -- we work just for the single exit condition,
2938      and are quite conservative about the possible overflows.  TODO -- both of
2939      these can be improved.  */
2940   exit = single_dom_exit (loop);
2941   if (!exit)
2942     return false;
2943   if (use->stmt != last_stmt (exit->src))
2944     return false;
2945
2946   niter = &loop_data (loop)->niter;
2947   if (!niter->niter
2948       || !integer_nonzerop (niter->assumptions)
2949       || !integer_zerop (niter->may_be_zero))
2950     return false;
2951
2952   if (exit->flags & EDGE_TRUE_VALUE)
2953     *compare = EQ_EXPR;
2954   else
2955     *compare = NE_EXPR;
2956
2957   *bound = cand_value_at (loop, cand, use->stmt, niter->niter);
2958
2959   /* Let us check there is not some problem with overflows, by checking that
2960      the number of iterations is unchanged.  */
2961   base = cand->iv->base;
2962   type = TREE_TYPE (base);
2963   if (stmt_after_increment (loop, cand, use->stmt))
2964     base = fold (build2 (PLUS_EXPR, type, base, cand->iv->step));
2965
2966   new_niter.niter = NULL_TREE;
2967   number_of_iterations_cond (TREE_TYPE (cand->iv->base), base,
2968                              cand->iv->step, NE_EXPR, *bound, NULL_TREE,
2969                              &new_niter);
2970   if (!new_niter.niter
2971       || !integer_nonzerop (new_niter.assumptions)
2972       || !integer_zerop (new_niter.may_be_zero))
2973     return false;
2974
2975   wider_type = TREE_TYPE (new_niter.niter);
2976   if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (TREE_TYPE (niter->niter)))
2977     wider_type = TREE_TYPE (niter->niter);
2978   if (!operand_equal_p (fold_convert (wider_type, niter->niter),
2979                         fold_convert (wider_type, new_niter.niter), 0))
2980     return false;
2981
2982   return true;
2983 }
2984
2985 /* Determines cost of basing replacement of USE on CAND in a condition.  */
2986
2987 static void
2988 determine_use_iv_cost_condition (struct ivopts_data *data,
2989                                  struct iv_use *use, struct iv_cand *cand)
2990 {
2991   tree bound;
2992   enum tree_code compare;
2993
2994   /* Only consider real candidates.  */
2995   if (!cand->iv)
2996     {
2997       set_use_iv_cost (data, use, cand, INFTY, NULL);
2998       return;
2999     }
3000
3001   if (may_eliminate_iv (data->current_loop, use, cand, &compare, &bound))
3002     {
3003       bitmap depends_on = NULL;
3004       unsigned cost = force_var_cost (data, bound, &depends_on);
3005
3006       set_use_iv_cost (data, use, cand, cost, depends_on);
3007       return;
3008     }
3009
3010   /* The induction variable elimination failed; just express the original
3011      giv.  If it is compared with an invariant, note that we cannot get
3012      rid of it.  */
3013   if (TREE_CODE (*use->op_p) == SSA_NAME)
3014     record_invariant (data, *use->op_p, true);
3015   else
3016     {
3017       record_invariant (data, TREE_OPERAND (*use->op_p, 0), true);
3018       record_invariant (data, TREE_OPERAND (*use->op_p, 1), true);
3019     }
3020
3021   determine_use_iv_cost_generic (data, use, cand);
3022 }
3023
3024 /* Checks whether it is possible to replace the final value of USE by
3025    a direct computation.  If so, the formula is stored to *VALUE.  */
3026
3027 static bool
3028 may_replace_final_value (struct loop *loop, struct iv_use *use, tree *value)
3029 {
3030   edge exit;
3031   struct tree_niter_desc *niter;
3032
3033   exit = single_dom_exit (loop);
3034   if (!exit)
3035     return false;
3036
3037   gcc_assert (dominated_by_p (CDI_DOMINATORS, exit->src,
3038                               bb_for_stmt (use->stmt)));
3039
3040   niter = &loop_data (loop)->niter;
3041   if (!niter->niter
3042       || !operand_equal_p (niter->assumptions, boolean_true_node, 0)
3043       || !operand_equal_p (niter->may_be_zero, boolean_false_node, 0))
3044     return false;
3045
3046   *value = iv_value (use->iv, niter->niter);
3047
3048   return true;
3049 }
3050
3051 /* Determines cost of replacing final value of USE using CAND.  */
3052
3053 static void
3054 determine_use_iv_cost_outer (struct ivopts_data *data,
3055                              struct iv_use *use, struct iv_cand *cand)
3056 {
3057   bitmap depends_on;
3058   unsigned cost;
3059   edge exit;
3060   tree value;
3061   struct loop *loop = data->current_loop;
3062           
3063   if (!cand->iv)
3064     {
3065       if (!may_replace_final_value (loop, use, &value))
3066         {
3067           set_use_iv_cost (data, use, cand, INFTY, NULL);
3068           return;
3069         }
3070
3071       depends_on = NULL;
3072       cost = force_var_cost (data, value, &depends_on);
3073
3074       cost /= AVG_LOOP_NITER (loop);
3075
3076       set_use_iv_cost (data, use, cand, cost, depends_on);
3077       return;
3078     }
3079
3080   exit = single_dom_exit (loop);
3081   if (exit)
3082     {
3083       /* If there is just a single exit, we may use value of the candidate
3084          after we take it to determine the value of use.  */
3085       cost = get_computation_cost_at (data, use, cand, false, &depends_on,
3086                                       last_stmt (exit->src));
3087       if (cost != INFTY)
3088         cost /= AVG_LOOP_NITER (loop);
3089     }
3090   else
3091     {
3092       /* Otherwise we just need to compute the iv.  */
3093       cost = get_computation_cost (data, use, cand, false, &depends_on);
3094     }
3095                                    
3096   set_use_iv_cost (data, use, cand, cost, depends_on);
3097 }
3098
3099 /* Determines cost of basing replacement of USE on CAND.  */
3100
3101 static void
3102 determine_use_iv_cost (struct ivopts_data *data,
3103                        struct iv_use *use, struct iv_cand *cand)
3104 {
3105   switch (use->type)
3106     {
3107     case USE_NONLINEAR_EXPR:
3108       determine_use_iv_cost_generic (data, use, cand);
3109       break;
3110
3111     case USE_OUTER:
3112       determine_use_iv_cost_outer (data, use, cand);
3113       break;
3114
3115     case USE_ADDRESS:
3116       determine_use_iv_cost_address (data, use, cand);
3117       break;
3118
3119     case USE_COMPARE:
3120       determine_use_iv_cost_condition (data, use, cand);
3121       break;
3122
3123     default:
3124       gcc_unreachable ();
3125     }
3126 }
3127
3128 /* Determines costs of basing the use of the iv on an iv candidate.  */
3129
3130 static void
3131 determine_use_iv_costs (struct ivopts_data *data)
3132 {
3133   unsigned i, j;
3134   struct iv_use *use;
3135   struct iv_cand *cand;
3136
3137   data->consider_all_candidates = (n_iv_cands (data)
3138                                    <= CONSIDER_ALL_CANDIDATES_BOUND);
3139
3140   alloc_use_cost_map (data);
3141
3142   if (!data->consider_all_candidates)
3143     {
3144       /* Add the important candidate entries.  */
3145       for (j = 0; j < n_iv_cands (data); j++)
3146         {
3147           cand = iv_cand (data, j);
3148           if (!cand->important)
3149             continue;
3150           for (i = 0; i < n_iv_uses (data); i++)
3151             {
3152               use = iv_use (data, i);
3153               determine_use_iv_cost (data, use, cand);
3154             }
3155         }
3156     }
3157
3158   for (i = 0; i < n_iv_uses (data); i++)
3159     {
3160       use = iv_use (data, i);
3161
3162       if (data->consider_all_candidates)
3163         {
3164           for (j = 0; j < n_iv_cands (data); j++)
3165             {
3166               cand = iv_cand (data, j);
3167               determine_use_iv_cost (data, use, cand);
3168             }
3169         }
3170       else
3171         {
3172           EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j,
3173             {
3174               cand = iv_cand (data, j);
3175               if (!cand->important)
3176                 determine_use_iv_cost (data, use, cand);
3177             });
3178         }
3179     }
3180
3181   if (dump_file && (dump_flags & TDF_DETAILS))
3182     {
3183       fprintf (dump_file, "Use-candidate costs:\n");
3184
3185       for (i = 0; i < n_iv_uses (data); i++)
3186         {
3187           use = iv_use (data, i);
3188
3189           fprintf (dump_file, "Use %d:\n", i);
3190           fprintf (dump_file, "  cand\tcost\tdepends on\n");
3191           for (j = 0; j < use->n_map_members; j++)
3192             {
3193               if (!use->cost_map[j].cand
3194                   || use->cost_map[j].cost == INFTY)
3195                 continue;
3196
3197               fprintf (dump_file, "  %d\t%d\t",
3198                        use->cost_map[j].cand->id,
3199                        use->cost_map[j].cost);
3200               if (use->cost_map[j].depends_on)
3201                 bitmap_print (dump_file,
3202                               use->cost_map[j].depends_on, "","");
3203               fprintf (dump_file, "\n");
3204             }
3205
3206           fprintf (dump_file, "\n");
3207         }
3208       fprintf (dump_file, "\n");
3209     }
3210 }
3211
3212 /* Determines cost of the candidate CAND.  */
3213
3214 static void
3215 determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
3216 {
3217   unsigned cost_base, cost_step;
3218   tree base, last;
3219   basic_block bb;
3220
3221   if (!cand->iv)
3222     {
3223       cand->cost = 0;
3224       return;
3225     }
3226
3227   /* There are two costs associated with the candidate -- its increment
3228      and its initialization.  The second is almost negligible for any loop
3229      that rolls enough, so we take it just very little into account.  */
3230
3231   base = cand->iv->base;
3232   cost_base = force_var_cost (data, base, NULL);
3233   cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
3234
3235   cand->cost = cost_step + cost_base / AVG_LOOP_NITER (current_loop);
3236
3237   /* Prefer the original iv unless we may gain something by replacing it.  */
3238   if (cand->pos == IP_ORIGINAL)
3239     cand->cost--;
3240   
3241   /* Prefer not to insert statements into latch unless there are some
3242      already (so that we do not create unnecessary jumps).  */
3243   if (cand->pos == IP_END)
3244     {
3245       bb = ip_end_pos (data->current_loop);
3246       last = last_stmt (bb);
3247
3248       if (!last
3249           || TREE_CODE (last) == LABEL_EXPR)
3250         cand->cost++;
3251     }
3252 }
3253
3254 /* Determines costs of computation of the candidates.  */
3255
3256 static void
3257 determine_iv_costs (struct ivopts_data *data)
3258 {
3259   unsigned i;
3260
3261   if (dump_file && (dump_flags & TDF_DETAILS))
3262     {
3263       fprintf (dump_file, "Candidate costs:\n");
3264       fprintf (dump_file, "  cand\tcost\n");
3265     }
3266
3267   for (i = 0; i < n_iv_cands (data); i++)
3268     {
3269       struct iv_cand *cand = iv_cand (data, i);
3270
3271       determine_iv_cost (data, cand);
3272
3273       if (dump_file && (dump_flags & TDF_DETAILS))
3274         fprintf (dump_file, "  %d\t%d\n", i, cand->cost);
3275     }
3276   
3277 if (dump_file && (dump_flags & TDF_DETAILS))
3278       fprintf (dump_file, "\n");
3279 }
3280
3281 /* Calculates cost for having SIZE induction variables.  */
3282
3283 static unsigned
3284 ivopts_global_cost_for_size (struct ivopts_data *data, unsigned size)
3285 {
3286   return global_cost_for_size (size,
3287                                loop_data (data->current_loop)->regs_used,
3288                                n_iv_uses (data));
3289 }
3290
3291 /* For each size of the induction variable set determine the penalty.  */
3292
3293 static void
3294 determine_set_costs (struct ivopts_data *data)
3295 {
3296   unsigned j, n;
3297   tree phi, op;
3298   struct loop *loop = data->current_loop;
3299
3300   /* We use the following model (definitely improvable, especially the
3301      cost function -- TODO):
3302
3303      We estimate the number of registers available (using MD data), name it A.
3304
3305      We estimate the number of registers used by the loop, name it U.  This
3306      number is obtained as the number of loop phi nodes (not counting virtual
3307      registers and bivs) + the number of variables from outside of the loop.
3308
3309      We set a reserve R (free regs that are used for temporary computations,
3310      etc.).  For now the reserve is a constant 3.
3311
3312      Let I be the number of induction variables.
3313      
3314      -- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
3315         make a lot of ivs without a reason).
3316      -- if A - R < U + I <= A, the cost is I * PRES_COST
3317      -- if U + I > A, the cost is I * PRES_COST and
3318         number of uses * SPILL_COST * (U + I - A) / (U + I) is added.  */
3319
3320   if (dump_file && (dump_flags & TDF_DETAILS))
3321     {
3322       fprintf (dump_file, "Global costs:\n");
3323       fprintf (dump_file, "  target_avail_regs %d\n", target_avail_regs);
3324       fprintf (dump_file, "  target_small_cost %d\n", target_small_cost);
3325       fprintf (dump_file, "  target_pres_cost %d\n", target_pres_cost);
3326       fprintf (dump_file, "  target_spill_cost %d\n", target_spill_cost);
3327     }
3328
3329   n = 0;
3330   for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
3331     {
3332       op = PHI_RESULT (phi);
3333
3334       if (!is_gimple_reg (op))
3335         continue;
3336
3337       if (get_iv (data, op))
3338         continue;
3339
3340       n++;
3341     }
3342
3343   EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j,
3344     {
3345       struct version_info *info = ver_info (data, j);
3346
3347       if (info->inv_id && info->has_nonlin_use)
3348         n++;
3349     });
3350
3351   loop_data (loop)->regs_used = n;
3352   if (dump_file && (dump_flags & TDF_DETAILS))
3353     fprintf (dump_file, "  regs_used %d\n", n);
3354
3355   if (dump_file && (dump_flags & TDF_DETAILS))
3356     {
3357       fprintf (dump_file, "  cost for size:\n");
3358       fprintf (dump_file, "  ivs\tcost\n");
3359       for (j = 0; j <= 2 * target_avail_regs; j++)
3360         fprintf (dump_file, "  %d\t%d\n", j,
3361                  ivopts_global_cost_for_size (data, j));
3362       fprintf (dump_file, "\n");
3363     }
3364 }
3365
3366 /* Finds a best candidate for USE and stores it to CAND.  The candidates are
3367    taken from the set SOL and they may depend on invariants in the set INV.
3368    The really used candidate and invariants are noted to USED_IVS and
3369    USED_INV.  */
3370
3371 static unsigned
3372 find_best_candidate (struct ivopts_data *data,
3373                      struct iv_use *use, bitmap sol, bitmap inv,
3374                      bitmap used_ivs, bitmap used_inv, struct iv_cand **cand)
3375 {
3376   unsigned c, d;
3377   unsigned best_cost = INFTY, cost;
3378   struct iv_cand *cnd = NULL, *acnd;
3379   bitmap depends_on = NULL, asol;
3380
3381   if (data->consider_all_candidates)
3382     asol = sol;
3383   else
3384     {
3385       asol = BITMAP_XMALLOC ();
3386       bitmap_a_and_b (asol, sol, use->related_cands);
3387     }
3388
3389   EXECUTE_IF_SET_IN_BITMAP (asol, 0, c,
3390     {
3391       acnd = iv_cand (data, c);
3392       cost = get_use_iv_cost (data, use, acnd, &depends_on);
3393
3394       if (cost == INFTY)
3395         goto next_cand;
3396       if (cost > best_cost)
3397         goto next_cand;
3398       if (cost == best_cost)
3399         {
3400           /* Prefer the cheaper iv.  */
3401           if (acnd->cost >= cnd->cost)
3402             goto next_cand;
3403         }
3404
3405       if (depends_on)
3406         {
3407           EXECUTE_IF_AND_COMPL_IN_BITMAP (depends_on, inv, 0, d,
3408                                           goto next_cand);
3409           if (used_inv)
3410             bitmap_a_or_b (used_inv, used_inv, depends_on);
3411         }
3412
3413       cnd = acnd;
3414       best_cost = cost;
3415 next_cand: ;
3416     });
3417
3418   if (cnd && used_ivs)
3419     bitmap_set_bit (used_ivs, cnd->id);
3420
3421   if (cand)
3422     *cand = cnd;
3423
3424   if (!data->consider_all_candidates)
3425     BITMAP_XFREE (asol);
3426
3427   return best_cost;
3428 }
3429
3430 /* Returns cost of set of ivs SOL + invariants INV.  Removes unnecessary
3431    induction variable candidates and invariants from the sets.  Only
3432    uses 0 .. MAX_USE - 1 are taken into account.  */
3433
3434 static unsigned
3435 set_cost_up_to (struct ivopts_data *data, bitmap sol, bitmap inv,
3436                 unsigned max_use)
3437 {
3438   unsigned i;
3439   unsigned cost = 0, size = 0, acost;
3440   struct iv_use *use;
3441   struct iv_cand *cand;
3442   bitmap used_ivs = BITMAP_XMALLOC (), used_inv = BITMAP_XMALLOC ();
3443
3444   for (i = 0; i < max_use; i++)
3445     {
3446       use = iv_use (data, i);
3447       acost = find_best_candidate (data, use, sol, inv,
3448                                    used_ivs, used_inv, NULL);
3449       if (acost == INFTY)
3450         {
3451           BITMAP_XFREE (used_ivs);
3452           BITMAP_XFREE (used_inv);
3453           return INFTY;
3454         }
3455       cost += acost;
3456     }
3457
3458   EXECUTE_IF_SET_IN_BITMAP (used_ivs, 0, i,
3459     {
3460       cand = iv_cand (data, i);
3461
3462       /* Do not count the pseudocandidates.  */
3463       if (cand->iv)
3464         size++;
3465
3466       cost += cand->cost;
3467     });
3468   EXECUTE_IF_SET_IN_BITMAP (used_inv, 0, i, size++);
3469   cost += ivopts_global_cost_for_size (data, size);
3470
3471   bitmap_copy (sol, used_ivs);
3472   bitmap_copy (inv, used_inv);
3473
3474   BITMAP_XFREE (used_ivs);
3475   BITMAP_XFREE (used_inv);
3476
3477   return cost;
3478 }
3479
3480 /* Computes cost of set of ivs SOL + invariants INV.  Removes unnecessary
3481    induction variable candidates and invariants from the sets.  */
3482
3483 static unsigned
3484 set_cost (struct ivopts_data *data, bitmap sol, bitmap inv)
3485 {
3486   return set_cost_up_to (data, sol, inv, n_iv_uses (data));
3487 }
3488
3489 /* Tries to extend the sets IVS and INV in the best possible way in order
3490    to express the USE.  */
3491
3492 static bool
3493 try_add_cand_for (struct ivopts_data *data, bitmap ivs, bitmap inv,
3494                   struct iv_use *use)
3495 {
3496   unsigned best_cost = set_cost_up_to (data, ivs, inv, use->id + 1), act_cost;
3497   bitmap best_ivs = BITMAP_XMALLOC ();
3498   bitmap best_inv = BITMAP_XMALLOC ();
3499   bitmap act_ivs = BITMAP_XMALLOC ();
3500   bitmap act_inv = BITMAP_XMALLOC ();
3501   unsigned i;
3502   struct cost_pair *cp;
3503
3504   bitmap_copy (best_ivs, ivs);
3505   bitmap_copy (best_inv, inv);
3506
3507   for (i = 0; i < use->n_map_members; i++)
3508     {
3509       cp = use->cost_map + i;
3510       if (cp->cost == INFTY)
3511         continue;
3512
3513       bitmap_copy (act_ivs, ivs);
3514       bitmap_set_bit (act_ivs, cp->cand->id);
3515       if (cp->depends_on)
3516         bitmap_a_or_b (act_inv, inv, cp->depends_on);
3517       else
3518         bitmap_copy (act_inv, inv);
3519       act_cost = set_cost_up_to (data, act_ivs, act_inv, use->id + 1);
3520
3521       if (act_cost < best_cost)
3522         {
3523           best_cost = act_cost;
3524           bitmap_copy (best_ivs, act_ivs);
3525           bitmap_copy (best_inv, act_inv);
3526         }
3527     }
3528
3529   bitmap_copy (ivs, best_ivs);
3530   bitmap_copy (inv, best_inv);
3531
3532   BITMAP_XFREE (best_ivs);
3533   BITMAP_XFREE (best_inv);
3534   BITMAP_XFREE (act_ivs);
3535   BITMAP_XFREE (act_inv);
3536
3537   return (best_cost != INFTY);
3538 }
3539
3540 /* Finds an initial set of IVS and invariants INV.  We do this by simply
3541    choosing the best candidate for each use.  */
3542
3543 static unsigned
3544 get_initial_solution (struct ivopts_data *data, bitmap ivs, bitmap inv)
3545 {
3546   unsigned i;
3547
3548   for (i = 0; i < n_iv_uses (data); i++)
3549     if (!try_add_cand_for (data, ivs, inv, iv_use (data, i)))
3550       return INFTY;
3551
3552   return set_cost (data, ivs, inv);
3553 }
3554
3555 /* Tries to improve set of induction variables IVS and invariants INV to get
3556    it better than COST.  */
3557
3558 static bool
3559 try_improve_iv_set (struct ivopts_data *data,
3560                     bitmap ivs, bitmap inv, unsigned *cost)
3561 {
3562   unsigned i, acost;
3563   bitmap new_ivs = BITMAP_XMALLOC (), new_inv = BITMAP_XMALLOC ();
3564   bitmap best_new_ivs = NULL, best_new_inv = NULL;
3565
3566   /* Try altering the set of induction variables by one.  */
3567   for (i = 0; i < n_iv_cands (data); i++)
3568     {
3569       bitmap_copy (new_ivs, ivs);
3570       bitmap_copy (new_inv, inv);
3571
3572       if (bitmap_bit_p (ivs, i))
3573         bitmap_clear_bit (new_ivs, i);
3574       else
3575         bitmap_set_bit (new_ivs, i);
3576
3577       acost = set_cost (data, new_ivs, new_inv);
3578       if (acost >= *cost)
3579         continue;
3580
3581       if (!best_new_ivs)
3582         {
3583           best_new_ivs = BITMAP_XMALLOC ();
3584           best_new_inv = BITMAP_XMALLOC ();
3585         }
3586
3587       *cost = acost;
3588       bitmap_copy (best_new_ivs, new_ivs);
3589       bitmap_copy (best_new_inv, new_inv);
3590     }
3591
3592   /* Ditto for invariants.  */
3593   for (i = 1; i <= data->max_inv_id; i++)
3594     {
3595       if (ver_info (data, i)->has_nonlin_use)
3596         continue;
3597
3598       bitmap_copy (new_ivs, ivs);
3599       bitmap_copy (new_inv, inv);
3600
3601       if (bitmap_bit_p (inv, i))
3602         bitmap_clear_bit (new_inv, i);
3603       else