1169689Skan/* Induction variable optimizations.
2169689Skan   Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3169689Skan
4169689SkanThis file is part of GCC.
5169689Skan
6169689SkanGCC is free software; you can redistribute it and/or modify it
7169689Skanunder the terms of the GNU General Public License as published by the
8169689SkanFree Software Foundation; either version 2, or (at your option) any
9169689Skanlater version.
10169689Skan
11169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT
12169689SkanANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13169689SkanFITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14169689Skanfor more details.
15169689Skan
16169689SkanYou should have received a copy of the GNU General Public License
17169689Skanalong with GCC; see the file COPYING.  If not, write to the Free
18169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
19169689Skan02110-1301, USA.  */
20169689Skan
21169689Skan/* This pass tries to find the optimal set of induction variables for the loop.
22169689Skan   It optimizes just the basic linear induction variables (although adding
23169689Skan   support for other types should not be too hard).  It includes the
24169689Skan   optimizations commonly known as strength reduction, induction variable
25169689Skan   coalescing and induction variable elimination.  It does it in the
26169689Skan   following steps:
27169689Skan
28169689Skan   1) The interesting uses of induction variables are found.  This includes
29169689Skan
30169689Skan      -- uses of induction variables in non-linear expressions
31169689Skan      -- addresses of arrays
32169689Skan      -- comparisons of induction variables
33169689Skan
34169689Skan   2) Candidates for the induction variables are found.  This includes
35169689Skan
36169689Skan      -- old induction variables
37169689Skan      -- the variables defined by expressions derived from the "interesting
38169689Skan	 uses" above
39169689Skan
40169689Skan   3) The optimal (w.r. to a cost function) set of variables is chosen.  The
41169689Skan      cost function assigns a cost to sets of induction variables and consists
42169689Skan      of three parts:
43169689Skan
44169689Skan      -- The use costs.  Each of the interesting uses chooses the best induction
45169689Skan	 variable in the set and adds its cost to the sum.  The cost reflects
46169689Skan	 the time spent on modifying the induction variables value to be usable
47169689Skan	 for the given purpose (adding base and offset for arrays, etc.).
48169689Skan      -- The variable costs.  Each of the variables has a cost assigned that
49169689Skan	 reflects the costs associated with incrementing the value of the
50169689Skan	 variable.  The original variables are somewhat preferred.
51169689Skan      -- The set cost.  Depending on the size of the set, extra cost may be
52169689Skan	 added to reflect register pressure.
53169689Skan
54169689Skan      All the costs are defined in a machine-specific way, using the target
55169689Skan      hooks and machine descriptions to determine them.
56169689Skan
57169689Skan   4) The trees are transformed to use the new variables, the dead code is
58169689Skan      removed.
59169689Skan
60169689Skan   All of this is done loop by loop.  Doing it globally is theoretically
61169689Skan   possible, it might give a better performance and it might enable us
62169689Skan   to decide costs more precisely, but getting all the interactions right
63169689Skan   would be complicated.  */
64169689Skan
65169689Skan#include "config.h"
66169689Skan#include "system.h"
67169689Skan#include "coretypes.h"
68169689Skan#include "tm.h"
69169689Skan#include "tree.h"
70169689Skan#include "rtl.h"
71169689Skan#include "tm_p.h"
72169689Skan#include "hard-reg-set.h"
73169689Skan#include "basic-block.h"
74169689Skan#include "output.h"
75169689Skan#include "diagnostic.h"
76169689Skan#include "tree-flow.h"
77169689Skan#include "tree-dump.h"
78169689Skan#include "timevar.h"
79169689Skan#include "cfgloop.h"
80169689Skan#include "varray.h"
81169689Skan#include "expr.h"
82169689Skan#include "tree-pass.h"
83169689Skan#include "ggc.h"
84169689Skan#include "insn-config.h"
85169689Skan#include "recog.h"
86169689Skan#include "hashtab.h"
87169689Skan#include "tree-chrec.h"
88169689Skan#include "tree-scalar-evolution.h"
89169689Skan#include "cfgloop.h"
90169689Skan#include "params.h"
91169689Skan#include "langhooks.h"
92169689Skan
93169689Skan/* The infinite cost.  */
94169689Skan#define INFTY 10000000
95169689Skan
96169689Skan/* The expected number of loop iterations.  TODO -- use profiling instead of
97169689Skan   this.  */
98169689Skan#define AVG_LOOP_NITER(LOOP) 5
99169689Skan
100169689Skan
101169689Skan/* Representation of the induction variable.  */
102169689Skanstruct iv
103169689Skan{
104169689Skan  tree base;		/* Initial value of the iv.  */
105169689Skan  tree base_object;	/* A memory object to that the induction variable points.  */
106169689Skan  tree step;		/* Step of the iv (constant only).  */
107169689Skan  tree ssa_name;	/* The ssa name with the value.  */
108169689Skan  bool biv_p;		/* Is it a biv?  */
109169689Skan  bool have_use_for;	/* Do we already have a use for it?  */
110169689Skan  unsigned use_id;	/* The identifier in the use if it is the case.  */
111169689Skan};
112169689Skan
113169689Skan/* Per-ssa version information (induction variable descriptions, etc.).  */
114169689Skanstruct version_info
115169689Skan{
116169689Skan  tree name;		/* The ssa name.  */
117169689Skan  struct iv *iv;	/* Induction variable description.  */
118169689Skan  bool has_nonlin_use;	/* For a loop-level invariant, whether it is used in
119169689Skan			   an expression that is not an induction variable.  */
120169689Skan  unsigned inv_id;	/* Id of an invariant.  */
121169689Skan  bool preserve_biv;	/* For the original biv, whether to preserve it.  */
122169689Skan};
123169689Skan
124169689Skan/* Types of uses.  */
125169689Skanenum use_type
126169689Skan{
127169689Skan  USE_NONLINEAR_EXPR,	/* Use in a nonlinear expression.  */
128169689Skan  USE_ADDRESS,		/* Use in an address.  */
129169689Skan  USE_COMPARE		/* Use is a compare.  */
130169689Skan};
131169689Skan
132169689Skan/* The candidate - cost pair.  */
133169689Skanstruct cost_pair
134169689Skan{
135169689Skan  struct iv_cand *cand;	/* The candidate.  */
136169689Skan  unsigned cost;	/* The cost.  */
137169689Skan  bitmap depends_on;	/* The list of invariants that have to be
138169689Skan			   preserved.  */
139169689Skan  tree value;		/* For final value elimination, the expression for
140169689Skan			   the final value of the iv.  For iv elimination,
141169689Skan			   the new bound to compare with.  */
142169689Skan};
143169689Skan
144169689Skan/* Use.  */
145169689Skanstruct iv_use
146169689Skan{
147169689Skan  unsigned id;		/* The id of the use.  */
148169689Skan  enum use_type type;	/* Type of the use.  */
149169689Skan  struct iv *iv;	/* The induction variable it is based on.  */
150169689Skan  tree stmt;		/* Statement in that it occurs.  */
151169689Skan  tree *op_p;		/* The place where it occurs.  */
152169689Skan  bitmap related_cands;	/* The set of "related" iv candidates, plus the common
153169689Skan			   important ones.  */
154169689Skan
155169689Skan  unsigned n_map_members; /* Number of candidates in the cost_map list.  */
156169689Skan  struct cost_pair *cost_map;
157169689Skan			/* The costs wrto the iv candidates.  */
158169689Skan
159169689Skan  struct iv_cand *selected;
160169689Skan			/* The selected candidate.  */
161169689Skan};
162169689Skan
163169689Skan/* The position where the iv is computed.  */
164169689Skanenum iv_position
165169689Skan{
166169689Skan  IP_NORMAL,		/* At the end, just before the exit condition.  */
167169689Skan  IP_END,		/* At the end of the latch block.  */
168169689Skan  IP_ORIGINAL		/* The original biv.  */
169169689Skan};
170169689Skan
171169689Skan/* The induction variable candidate.  */
172169689Skanstruct iv_cand
173169689Skan{
174169689Skan  unsigned id;		/* The number of the candidate.  */
175169689Skan  bool important;	/* Whether this is an "important" candidate, i.e. such
176169689Skan			   that it should be considered by all uses.  */
177169689Skan  enum iv_position pos;	/* Where it is computed.  */
178169689Skan  tree incremented_at;	/* For original biv, the statement where it is
179169689Skan			   incremented.  */
180169689Skan  tree var_before;	/* The variable used for it before increment.  */
181169689Skan  tree var_after;	/* The variable used for it after increment.  */
182169689Skan  struct iv *iv;	/* The value of the candidate.  NULL for
183169689Skan			   "pseudocandidate" used to indicate the possibility
184169689Skan			   to replace the final value of an iv by direct
185169689Skan			   computation of the value.  */
186169689Skan  unsigned cost;	/* Cost of the candidate.  */
187169689Skan  bitmap depends_on;	/* The list of invariants that are used in step of the
188169689Skan			   biv.  */
189169689Skan};
190169689Skan
191169689Skan/* The data used by the induction variable optimizations.  */
192169689Skan
193169689Skantypedef struct iv_use *iv_use_p;
194169689SkanDEF_VEC_P(iv_use_p);
195169689SkanDEF_VEC_ALLOC_P(iv_use_p,heap);
196169689Skan
197169689Skantypedef struct iv_cand *iv_cand_p;
198169689SkanDEF_VEC_P(iv_cand_p);
199169689SkanDEF_VEC_ALLOC_P(iv_cand_p,heap);
200169689Skan
201169689Skanstruct ivopts_data
202169689Skan{
203169689Skan  /* The currently optimized loop.  */
204169689Skan  struct loop *current_loop;
205169689Skan
206169689Skan  /* Number of registers used in it.  */
207169689Skan  unsigned regs_used;
208169689Skan
209169689Skan  /* Numbers of iterations for all exits of the current loop.  */
210169689Skan  htab_t niters;
211169689Skan
212169689Skan  /* The size of version_info array allocated.  */
213169689Skan  unsigned version_info_size;
214169689Skan
215169689Skan  /* The array of information for the ssa names.  */
216169689Skan  struct version_info *version_info;
217169689Skan
218169689Skan  /* The bitmap of indices in version_info whose value was changed.  */
219169689Skan  bitmap relevant;
220169689Skan
221169689Skan  /* The maximum invariant id.  */
222169689Skan  unsigned max_inv_id;
223169689Skan
224169689Skan  /* The uses of induction variables.  */
225169689Skan  VEC(iv_use_p,heap) *iv_uses;
226169689Skan
227169689Skan  /* The candidates.  */
228169689Skan  VEC(iv_cand_p,heap) *iv_candidates;
229169689Skan
230169689Skan  /* A bitmap of important candidates.  */
231169689Skan  bitmap important_candidates;
232169689Skan
233169689Skan  /* Whether to consider just related and important candidates when replacing a
234169689Skan     use.  */
235169689Skan  bool consider_all_candidates;
236169689Skan};
237169689Skan
238169689Skan/* An assignment of iv candidates to uses.  */
239169689Skan
240169689Skanstruct iv_ca
241169689Skan{
242169689Skan  /* The number of uses covered by the assignment.  */
243169689Skan  unsigned upto;
244169689Skan
245169689Skan  /* Number of uses that cannot be expressed by the candidates in the set.  */
246169689Skan  unsigned bad_uses;
247169689Skan
248169689Skan  /* Candidate assigned to a use, together with the related costs.  */
249169689Skan  struct cost_pair **cand_for_use;
250169689Skan
251169689Skan  /* Number of times each candidate is used.  */
252169689Skan  unsigned *n_cand_uses;
253169689Skan
254169689Skan  /* The candidates used.  */
255169689Skan  bitmap cands;
256169689Skan
257169689Skan  /* The number of candidates in the set.  */
258169689Skan  unsigned n_cands;
259169689Skan
260169689Skan  /* Total number of registers needed.  */
261169689Skan  unsigned n_regs;
262169689Skan
263169689Skan  /* Total cost of expressing uses.  */
264169689Skan  unsigned cand_use_cost;
265169689Skan
266169689Skan  /* Total cost of candidates.  */
267169689Skan  unsigned cand_cost;
268169689Skan
269169689Skan  /* Number of times each invariant is used.  */
270169689Skan  unsigned *n_invariant_uses;
271169689Skan
272169689Skan  /* Total cost of the assignment.  */
273169689Skan  unsigned cost;
274169689Skan};
275169689Skan
276169689Skan/* Difference of two iv candidate assignments.  */
277169689Skan
278169689Skanstruct iv_ca_delta
279169689Skan{
280169689Skan  /* Changed use.  */
281169689Skan  struct iv_use *use;
282169689Skan
283169689Skan  /* An old assignment (for rollback purposes).  */
284169689Skan  struct cost_pair *old_cp;
285169689Skan
286169689Skan  /* A new assignment.  */
287169689Skan  struct cost_pair *new_cp;
288169689Skan
289169689Skan  /* Next change in the list.  */
290169689Skan  struct iv_ca_delta *next_change;
291169689Skan};
292169689Skan
293169689Skan/* Bound on number of candidates below that all candidates are considered.  */
294169689Skan
295169689Skan#define CONSIDER_ALL_CANDIDATES_BOUND \
296169689Skan  ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
297169689Skan
298169689Skan/* If there are more iv occurrences, we just give up (it is quite unlikely that
299169689Skan   optimizing such a loop would help, and it would take ages).  */
300169689Skan
301169689Skan#define MAX_CONSIDERED_USES \
302169689Skan  ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
303169689Skan
304169689Skan/* If there are at most this number of ivs in the set, try removing unnecessary
305169689Skan   ivs from the set always.  */
306169689Skan
307169689Skan#define ALWAYS_PRUNE_CAND_SET_BOUND \
308169689Skan  ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
309169689Skan
310169689Skan/* The list of trees for that the decl_rtl field must be reset is stored
311169689Skan   here.  */
312169689Skan
313169689Skanstatic VEC(tree,heap) *decl_rtl_to_reset;
314169689Skan
315169689Skan/* Number of uses recorded in DATA.  */
316169689Skan
317169689Skanstatic inline unsigned
318169689Skann_iv_uses (struct ivopts_data *data)
319169689Skan{
320169689Skan  return VEC_length (iv_use_p, data->iv_uses);
321169689Skan}
322169689Skan
323169689Skan/* Ith use recorded in DATA.  */
324169689Skan
325169689Skanstatic inline struct iv_use *
326169689Skaniv_use (struct ivopts_data *data, unsigned i)
327169689Skan{
328169689Skan  return VEC_index (iv_use_p, data->iv_uses, i);
329169689Skan}
330169689Skan
331169689Skan/* Number of candidates recorded in DATA.  */
332169689Skan
333169689Skanstatic inline unsigned
334169689Skann_iv_cands (struct ivopts_data *data)
335169689Skan{
336169689Skan  return VEC_length (iv_cand_p, data->iv_candidates);
337169689Skan}
338169689Skan
339169689Skan/* Ith candidate recorded in DATA.  */
340169689Skan
341169689Skanstatic inline struct iv_cand *
342169689Skaniv_cand (struct ivopts_data *data, unsigned i)
343169689Skan{
344169689Skan  return VEC_index (iv_cand_p, data->iv_candidates, i);
345169689Skan}
346169689Skan
347169689Skan/* The single loop exit if it dominates the latch, NULL otherwise.  */
348169689Skan
349169689Skanedge
350169689Skansingle_dom_exit (struct loop *loop)
351169689Skan{
352169689Skan  edge exit = loop->single_exit;
353169689Skan
354169689Skan  if (!exit)
355169689Skan    return NULL;
356169689Skan
357169689Skan  if (!just_once_each_iteration_p (loop, exit->src))
358169689Skan    return NULL;
359169689Skan
360169689Skan  return exit;
361169689Skan}
362169689Skan
363169689Skan/* Dumps information about the induction variable IV to FILE.  */
364169689Skan
365169689Skanextern void dump_iv (FILE *, struct iv *);
366169689Skanvoid
367169689Skandump_iv (FILE *file, struct iv *iv)
368169689Skan{
369169689Skan  if (iv->ssa_name)
370169689Skan    {
371169689Skan      fprintf (file, "ssa name ");
372169689Skan      print_generic_expr (file, iv->ssa_name, TDF_SLIM);
373169689Skan      fprintf (file, "\n");
374169689Skan    }
375169689Skan
376169689Skan  fprintf (file, "  type ");
377169689Skan  print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
378169689Skan  fprintf (file, "\n");
379169689Skan
380169689Skan  if (iv->step)
381169689Skan    {
382169689Skan      fprintf (file, "  base ");
383169689Skan      print_generic_expr (file, iv->base, TDF_SLIM);
384169689Skan      fprintf (file, "\n");
385169689Skan
386169689Skan      fprintf (file, "  step ");
387169689Skan      print_generic_expr (file, iv->step, TDF_SLIM);
388169689Skan      fprintf (file, "\n");
389169689Skan    }
390169689Skan  else
391169689Skan    {
392169689Skan      fprintf (file, "  invariant ");
393169689Skan      print_generic_expr (file, iv->base, TDF_SLIM);
394169689Skan      fprintf (file, "\n");
395169689Skan    }
396169689Skan
397169689Skan  if (iv->base_object)
398169689Skan    {
399169689Skan      fprintf (file, "  base object ");
400169689Skan      print_generic_expr (file, iv->base_object, TDF_SLIM);
401169689Skan      fprintf (file, "\n");
402169689Skan    }
403169689Skan
404169689Skan  if (iv->biv_p)
405169689Skan    fprintf (file, "  is a biv\n");
406169689Skan}
407169689Skan
408169689Skan/* Dumps information about the USE to FILE.  */
409169689Skan
410169689Skanextern void dump_use (FILE *, struct iv_use *);
411169689Skanvoid
412169689Skandump_use (FILE *file, struct iv_use *use)
413169689Skan{
414169689Skan  fprintf (file, "use %d\n", use->id);
415169689Skan
416169689Skan  switch (use->type)
417169689Skan    {
418169689Skan    case USE_NONLINEAR_EXPR:
419169689Skan      fprintf (file, "  generic\n");
420169689Skan      break;
421169689Skan
422169689Skan    case USE_ADDRESS:
423169689Skan      fprintf (file, "  address\n");
424169689Skan      break;
425169689Skan
426169689Skan    case USE_COMPARE:
427169689Skan      fprintf (file, "  compare\n");
428169689Skan      break;
429169689Skan
430169689Skan    default:
431169689Skan      gcc_unreachable ();
432169689Skan    }
433169689Skan
434169689Skan  fprintf (file, "  in statement ");
435169689Skan  print_generic_expr (file, use->stmt, TDF_SLIM);
436169689Skan  fprintf (file, "\n");
437169689Skan
438169689Skan  fprintf (file, "  at position ");
439169689Skan  if (use->op_p)
440169689Skan    print_generic_expr (file, *use->op_p, TDF_SLIM);
441169689Skan  fprintf (file, "\n");
442169689Skan
443169689Skan  dump_iv (file, use->iv);
444169689Skan
445169689Skan  if (use->related_cands)
446169689Skan    {
447169689Skan      fprintf (file, "  related candidates ");
448169689Skan      dump_bitmap (file, use->related_cands);
449169689Skan    }
450169689Skan}
451169689Skan
452169689Skan/* Dumps information about the uses to FILE.  */
453169689Skan
454169689Skanextern void dump_uses (FILE *, struct ivopts_data *);
455169689Skanvoid
456169689Skandump_uses (FILE *file, struct ivopts_data *data)
457169689Skan{
458169689Skan  unsigned i;
459169689Skan  struct iv_use *use;
460169689Skan
461169689Skan  for (i = 0; i < n_iv_uses (data); i++)
462169689Skan    {
463169689Skan      use = iv_use (data, i);
464169689Skan
465169689Skan      dump_use (file, use);
466169689Skan      fprintf (file, "\n");
467169689Skan    }
468169689Skan}
469169689Skan
470169689Skan/* Dumps information about induction variable candidate CAND to FILE.  */
471169689Skan
472169689Skanextern void dump_cand (FILE *, struct iv_cand *);
473169689Skanvoid
474169689Skandump_cand (FILE *file, struct iv_cand *cand)
475169689Skan{
476169689Skan  struct iv *iv = cand->iv;
477169689Skan
478169689Skan  fprintf (file, "candidate %d%s\n",
479169689Skan	   cand->id, cand->important ? " (important)" : "");
480169689Skan
481169689Skan  if (cand->depends_on)
482169689Skan    {
483169689Skan      fprintf (file, "  depends on ");
484169689Skan      dump_bitmap (file, cand->depends_on);
485169689Skan    }
486169689Skan
487169689Skan  if (!iv)
488169689Skan    {
489169689Skan      fprintf (file, "  final value replacement\n");
490169689Skan      return;
491169689Skan    }
492169689Skan
493169689Skan  switch (cand->pos)
494169689Skan    {
495169689Skan    case IP_NORMAL:
496169689Skan      fprintf (file, "  incremented before exit test\n");
497169689Skan      break;
498169689Skan
499169689Skan    case IP_END:
500169689Skan      fprintf (file, "  incremented at end\n");
501169689Skan      break;
502169689Skan
503169689Skan    case IP_ORIGINAL:
504169689Skan      fprintf (file, "  original biv\n");
505169689Skan      break;
506169689Skan    }
507169689Skan
508169689Skan  dump_iv (file, iv);
509169689Skan}
510169689Skan
511169689Skan/* Returns the info for ssa version VER.  */
512169689Skan
513169689Skanstatic inline struct version_info *
514169689Skanver_info (struct ivopts_data *data, unsigned ver)
515169689Skan{
516169689Skan  return data->version_info + ver;
517169689Skan}
518169689Skan
519169689Skan/* Returns the info for ssa name NAME.  */
520169689Skan
521169689Skanstatic inline struct version_info *
522169689Skanname_info (struct ivopts_data *data, tree name)
523169689Skan{
524169689Skan  return ver_info (data, SSA_NAME_VERSION (name));
525169689Skan}
526169689Skan
527169689Skan/* Checks whether there exists number X such that X * B = A, counting modulo
528169689Skan   2^BITS.  */
529169689Skan
530169689Skanstatic bool
531169689Skandivide (unsigned bits, unsigned HOST_WIDE_INT a, unsigned HOST_WIDE_INT b,
532169689Skan	HOST_WIDE_INT *x)
533169689Skan{
534169689Skan  unsigned HOST_WIDE_INT mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
535169689Skan  unsigned HOST_WIDE_INT inv, ex, val;
536169689Skan  unsigned i;
537169689Skan
538169689Skan  a &= mask;
539169689Skan  b &= mask;
540169689Skan
541169689Skan  /* First divide the whole equation by 2 as long as possible.  */
542169689Skan  while (!(a & 1) && !(b & 1))
543169689Skan    {
544169689Skan      a >>= 1;
545169689Skan      b >>= 1;
546169689Skan      bits--;
547169689Skan      mask >>= 1;
548169689Skan    }
549169689Skan
550169689Skan  if (!(b & 1))
551169689Skan    {
552169689Skan      /* If b is still even, a is odd and there is no such x.  */
553169689Skan      return false;
554169689Skan    }
555169689Skan
556169689Skan  /* Find the inverse of b.  We compute it as
557169689Skan     b^(2^(bits - 1) - 1) (mod 2^bits).  */
558169689Skan  inv = 1;
559169689Skan  ex = b;
560169689Skan  for (i = 0; i < bits - 1; i++)
561169689Skan    {
562169689Skan      inv = (inv * ex) & mask;
563169689Skan      ex = (ex * ex) & mask;
564169689Skan    }
565169689Skan
566169689Skan  val = (a * inv) & mask;
567169689Skan
568169689Skan  gcc_assert (((val * b) & mask) == a);
569169689Skan
570169689Skan  if ((val >> (bits - 1)) & 1)
571169689Skan    val |= ~mask;
572169689Skan
573169689Skan  *x = val;
574169689Skan
575169689Skan  return true;
576169689Skan}
577169689Skan
578169689Skan/* Returns true if STMT is after the place where the IP_NORMAL ivs will be
579169689Skan   emitted in LOOP.  */
580169689Skan
581169689Skanstatic bool
582169689Skanstmt_after_ip_normal_pos (struct loop *loop, tree stmt)
583169689Skan{
584169689Skan  basic_block bb = ip_normal_pos (loop), sbb = bb_for_stmt (stmt);
585169689Skan
586169689Skan  gcc_assert (bb);
587169689Skan
588169689Skan  if (sbb == loop->latch)
589169689Skan    return true;
590169689Skan
591169689Skan  if (sbb != bb)
592169689Skan    return false;
593169689Skan
594169689Skan  return stmt == last_stmt (bb);
595169689Skan}
596169689Skan
597169689Skan/* Returns true if STMT if after the place where the original induction
598169689Skan   variable CAND is incremented.  */
599169689Skan
600169689Skanstatic bool
601169689Skanstmt_after_ip_original_pos (struct iv_cand *cand, tree stmt)
602169689Skan{
603169689Skan  basic_block cand_bb = bb_for_stmt (cand->incremented_at);
604169689Skan  basic_block stmt_bb = bb_for_stmt (stmt);
605169689Skan  block_stmt_iterator bsi;
606169689Skan
607169689Skan  if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
608169689Skan    return false;
609169689Skan
610169689Skan  if (stmt_bb != cand_bb)
611169689Skan    return true;
612169689Skan
613169689Skan  /* Scan the block from the end, since the original ivs are usually
614169689Skan     incremented at the end of the loop body.  */
615169689Skan  for (bsi = bsi_last (stmt_bb); ; bsi_prev (&bsi))
616169689Skan    {
617169689Skan      if (bsi_stmt (bsi) == cand->incremented_at)
618169689Skan	return false;
619169689Skan      if (bsi_stmt (bsi) == stmt)
620169689Skan	return true;
621169689Skan    }
622169689Skan}
623169689Skan
624169689Skan/* Returns true if STMT if after the place where the induction variable
625169689Skan   CAND is incremented in LOOP.  */
626169689Skan
627169689Skanstatic bool
628169689Skanstmt_after_increment (struct loop *loop, struct iv_cand *cand, tree stmt)
629169689Skan{
630169689Skan  switch (cand->pos)
631169689Skan    {
632169689Skan    case IP_END:
633169689Skan      return false;
634169689Skan
635169689Skan    case IP_NORMAL:
636169689Skan      return stmt_after_ip_normal_pos (loop, stmt);
637169689Skan
638169689Skan    case IP_ORIGINAL:
639169689Skan      return stmt_after_ip_original_pos (cand, stmt);
640169689Skan
641169689Skan    default:
642169689Skan      gcc_unreachable ();
643169689Skan    }
644169689Skan}
645169689Skan
646169689Skan/* Returns true if EXP is a ssa name that occurs in an abnormal phi node.  */
647169689Skan
648169689Skanstatic bool
649169689Skanabnormal_ssa_name_p (tree exp)
650169689Skan{
651169689Skan  if (!exp)
652169689Skan    return false;
653169689Skan
654169689Skan  if (TREE_CODE (exp) != SSA_NAME)
655169689Skan    return false;
656169689Skan
657169689Skan  return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) != 0;
658169689Skan}
659169689Skan
660169689Skan/* Returns false if BASE or INDEX contains a ssa name that occurs in an
661169689Skan   abnormal phi node.  Callback for for_each_index.  */
662169689Skan
663169689Skanstatic bool
664169689Skanidx_contains_abnormal_ssa_name_p (tree base, tree *index,
665169689Skan				  void *data ATTRIBUTE_UNUSED)
666169689Skan{
667169689Skan  if (TREE_CODE (base) == ARRAY_REF)
668169689Skan    {
669169689Skan      if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
670169689Skan	return false;
671169689Skan      if (abnormal_ssa_name_p (TREE_OPERAND (base, 3)))
672169689Skan	return false;
673169689Skan    }
674169689Skan
675169689Skan  return !abnormal_ssa_name_p (*index);
676169689Skan}
677169689Skan
678169689Skan/* Returns true if EXPR contains a ssa name that occurs in an
679169689Skan   abnormal phi node.  */
680169689Skan
681169689Skanbool
682169689Skancontains_abnormal_ssa_name_p (tree expr)
683169689Skan{
684169689Skan  enum tree_code code;
685169689Skan  enum tree_code_class class;
686169689Skan
687169689Skan  if (!expr)
688169689Skan    return false;
689169689Skan
690169689Skan  code = TREE_CODE (expr);
691169689Skan  class = TREE_CODE_CLASS (code);
692169689Skan
693169689Skan  if (code == SSA_NAME)
694169689Skan    return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
695169689Skan
696169689Skan  if (code == INTEGER_CST
697169689Skan      || is_gimple_min_invariant (expr))
698169689Skan    return false;
699169689Skan
700169689Skan  if (code == ADDR_EXPR)
701169689Skan    return !for_each_index (&TREE_OPERAND (expr, 0),
702169689Skan			    idx_contains_abnormal_ssa_name_p,
703169689Skan			    NULL);
704169689Skan
705169689Skan  switch (class)
706169689Skan    {
707169689Skan    case tcc_binary:
708169689Skan    case tcc_comparison:
709169689Skan      if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1)))
710169689Skan	return true;
711169689Skan
712169689Skan      /* Fallthru.  */
713169689Skan    case tcc_unary:
714169689Skan      if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0)))
715169689Skan	return true;
716169689Skan
717169689Skan      break;
718169689Skan
719169689Skan    default:
720169689Skan      gcc_unreachable ();
721169689Skan    }
722169689Skan
723169689Skan  return false;
724169689Skan}
725169689Skan
726169689Skan/* Element of the table in that we cache the numbers of iterations obtained
727169689Skan   from exits of the loop.  */
728169689Skan
729169689Skanstruct nfe_cache_elt
730169689Skan{
731169689Skan  /* The edge for that the number of iterations is cached.  */
732169689Skan  edge exit;
733169689Skan
734169689Skan  /* Number of iterations corresponding to this exit, or NULL if it cannot be
735169689Skan     determined.  */
736169689Skan  tree niter;
737169689Skan};
738169689Skan
739169689Skan/* Hash function for nfe_cache_elt E.  */
740169689Skan
741169689Skanstatic hashval_t
742169689Skannfe_hash (const void *e)
743169689Skan{
744169689Skan  const struct nfe_cache_elt *elt = e;
745169689Skan
746169689Skan  return htab_hash_pointer (elt->exit);
747169689Skan}
748169689Skan
749169689Skan/* Equality function for nfe_cache_elt E1 and edge E2.  */
750169689Skan
751169689Skanstatic int
752169689Skannfe_eq (const void *e1, const void *e2)
753169689Skan{
754169689Skan  const struct nfe_cache_elt *elt1 = e1;
755169689Skan
756169689Skan  return elt1->exit == e2;
757169689Skan}
758169689Skan
759169689Skan/*  Returns tree describing number of iterations determined from
760169689Skan    EXIT of DATA->current_loop, or NULL if something goes wrong.  */
761169689Skan
762169689Skanstatic tree
763169689Skanniter_for_exit (struct ivopts_data *data, edge exit)
764169689Skan{
765169689Skan  struct nfe_cache_elt *nfe_desc;
766169689Skan  struct tree_niter_desc desc;
767169689Skan  PTR *slot;
768169689Skan
769169689Skan  slot = htab_find_slot_with_hash (data->niters, exit,
770169689Skan				   htab_hash_pointer (exit),
771169689Skan				   INSERT);
772169689Skan
773169689Skan  if (!*slot)
774169689Skan    {
775169689Skan      nfe_desc = xmalloc (sizeof (struct nfe_cache_elt));
776169689Skan      nfe_desc->exit = exit;
777169689Skan
778169689Skan      /* Try to determine number of iterations.  We must know it
779169689Skan	 unconditionally (i.e., without possibility of # of iterations
780169689Skan	 being zero).  Also, we cannot safely work with ssa names that
781169689Skan	 appear in phi nodes on abnormal edges, so that we do not create
782169689Skan	 overlapping life ranges for them (PR 27283).  */
783169689Skan      if (number_of_iterations_exit (data->current_loop,
784169689Skan				     exit, &desc, true)
785169689Skan	  && zero_p (desc.may_be_zero)
786169689Skan     	  && !contains_abnormal_ssa_name_p (desc.niter))
787169689Skan	nfe_desc->niter = desc.niter;
788169689Skan      else
789169689Skan	nfe_desc->niter = NULL_TREE;
790169689Skan    }
791169689Skan  else
792169689Skan    nfe_desc = *slot;
793169689Skan
794169689Skan  return nfe_desc->niter;
795169689Skan}
796169689Skan
797169689Skan/* Returns tree describing number of iterations determined from
798169689Skan   single dominating exit of DATA->current_loop, or NULL if something
799169689Skan   goes wrong.  */
800169689Skan
801169689Skanstatic tree
802169689Skanniter_for_single_dom_exit (struct ivopts_data *data)
803169689Skan{
804169689Skan  edge exit = single_dom_exit (data->current_loop);
805169689Skan
806169689Skan  if (!exit)
807169689Skan    return NULL;
808169689Skan
809169689Skan  return niter_for_exit (data, exit);
810169689Skan}
811169689Skan
812169689Skan/* Initializes data structures used by the iv optimization pass, stored
813169689Skan   in DATA.  */
814169689Skan
815169689Skanstatic void
816169689Skantree_ssa_iv_optimize_init (struct ivopts_data *data)
817169689Skan{
818169689Skan  data->version_info_size = 2 * num_ssa_names;
819169689Skan  data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
820169689Skan  data->relevant = BITMAP_ALLOC (NULL);
821169689Skan  data->important_candidates = BITMAP_ALLOC (NULL);
822169689Skan  data->max_inv_id = 0;
823169689Skan  data->niters = htab_create (10, nfe_hash, nfe_eq, free);
824169689Skan  data->iv_uses = VEC_alloc (iv_use_p, heap, 20);
825169689Skan  data->iv_candidates = VEC_alloc (iv_cand_p, heap, 20);
826169689Skan  decl_rtl_to_reset = VEC_alloc (tree, heap, 20);
827169689Skan}
828169689Skan
829169689Skan/* Returns a memory object to that EXPR points.  In case we are able to
830169689Skan   determine that it does not point to any such object, NULL is returned.  */
831169689Skan
832169689Skanstatic tree
833169689Skandetermine_base_object (tree expr)
834169689Skan{
835169689Skan  enum tree_code code = TREE_CODE (expr);
836169689Skan  tree base, obj, op0, op1;
837169689Skan
838169689Skan  /* If this is a pointer casted to any type, we need to determine
839169689Skan     the base object for the pointer; so handle conversions before
840169689Skan     throwing away non-pointer expressions.  */
841169689Skan  if (TREE_CODE (expr) == NOP_EXPR
842169689Skan      || TREE_CODE (expr) == CONVERT_EXPR)
843169689Skan    return determine_base_object (TREE_OPERAND (expr, 0));
844169689Skan
845169689Skan  if (!POINTER_TYPE_P (TREE_TYPE (expr)))
846169689Skan    return NULL_TREE;
847169689Skan
848169689Skan  switch (code)
849169689Skan    {
850169689Skan    case INTEGER_CST:
851169689Skan      return NULL_TREE;
852169689Skan
853169689Skan    case ADDR_EXPR:
854169689Skan      obj = TREE_OPERAND (expr, 0);
855169689Skan      base = get_base_address (obj);
856169689Skan
857169689Skan      if (!base)
858169689Skan	return expr;
859169689Skan
860169689Skan      if (TREE_CODE (base) == INDIRECT_REF)
861169689Skan	return determine_base_object (TREE_OPERAND (base, 0));
862169689Skan
863169689Skan      return fold_convert (ptr_type_node,
864169689Skan		           build_fold_addr_expr (base));
865169689Skan
866169689Skan    case PLUS_EXPR:
867169689Skan    case MINUS_EXPR:
868169689Skan      op0 = determine_base_object (TREE_OPERAND (expr, 0));
869169689Skan      op1 = determine_base_object (TREE_OPERAND (expr, 1));
870169689Skan
871169689Skan      if (!op1)
872169689Skan	return op0;
873169689Skan
874169689Skan      if (!op0)
875169689Skan	return (code == PLUS_EXPR
876169689Skan		? op1
877169689Skan		: fold_build1 (NEGATE_EXPR, ptr_type_node, op1));
878169689Skan
879169689Skan      return fold_build2 (code, ptr_type_node, op0, op1);
880169689Skan
881169689Skan    default:
882169689Skan      return fold_convert (ptr_type_node, expr);
883169689Skan    }
884169689Skan}
885169689Skan
886169689Skan/* Allocates an induction variable with given initial value BASE and step STEP
887169689Skan   for loop LOOP.  */
888169689Skan
889169689Skanstatic struct iv *
890169689Skanalloc_iv (tree base, tree step)
891169689Skan{
892169689Skan  struct iv *iv = XCNEW (struct iv);
893169689Skan
894169689Skan  if (step && integer_zerop (step))
895169689Skan    step = NULL_TREE;
896169689Skan
897169689Skan  iv->base = base;
898169689Skan  iv->base_object = determine_base_object (base);
899169689Skan  iv->step = step;
900169689Skan  iv->biv_p = false;
901169689Skan  iv->have_use_for = false;
902169689Skan  iv->use_id = 0;
903169689Skan  iv->ssa_name = NULL_TREE;
904169689Skan
905169689Skan  return iv;
906169689Skan}
907169689Skan
908169689Skan/* Sets STEP and BASE for induction variable IV.  */
909169689Skan
910169689Skanstatic void
911169689Skanset_iv (struct ivopts_data *data, tree iv, tree base, tree step)
912169689Skan{
913169689Skan  struct version_info *info = name_info (data, iv);
914169689Skan
915169689Skan  gcc_assert (!info->iv);
916169689Skan
917169689Skan  bitmap_set_bit (data->relevant, SSA_NAME_VERSION (iv));
918169689Skan  info->iv = alloc_iv (base, step);
919169689Skan  info->iv->ssa_name = iv;
920169689Skan}
921169689Skan
922169689Skan/* Finds induction variable declaration for VAR.  */
923169689Skan
924169689Skanstatic struct iv *
925169689Skanget_iv (struct ivopts_data *data, tree var)
926169689Skan{
927169689Skan  basic_block bb;
928169689Skan
929169689Skan  if (!name_info (data, var)->iv)
930169689Skan    {
931169689Skan      bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
932169689Skan
933169689Skan      if (!bb
934169689Skan	  || !flow_bb_inside_loop_p (data->current_loop, bb))
935169689Skan	set_iv (data, var, var, NULL_TREE);
936169689Skan    }
937169689Skan
938169689Skan  return name_info (data, var)->iv;
939169689Skan}
940169689Skan
941169689Skan/* Determines the step of a biv defined in PHI.  Returns NULL if PHI does
942169689Skan   not define a simple affine biv with nonzero step.  */
943169689Skan
944169689Skanstatic tree
945169689Skandetermine_biv_step (tree phi)
946169689Skan{
947169689Skan  struct loop *loop = bb_for_stmt (phi)->loop_father;
948169689Skan  tree name = PHI_RESULT (phi);
949169689Skan  affine_iv iv;
950169689Skan
951169689Skan  if (!is_gimple_reg (name))
952169689Skan    return NULL_TREE;
953169689Skan
954169689Skan  if (!simple_iv (loop, phi, name, &iv, true))
955169689Skan    return NULL_TREE;
956169689Skan
957169689Skan  return (zero_p (iv.step) ? NULL_TREE : iv.step);
958169689Skan}
959169689Skan
960169689Skan/* Finds basic ivs.  */
961169689Skan
962169689Skanstatic bool
963169689Skanfind_bivs (struct ivopts_data *data)
964169689Skan{
965169689Skan  tree phi, step, type, base;
966169689Skan  bool found = false;
967169689Skan  struct loop *loop = data->current_loop;
968169689Skan
969169689Skan  for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
970169689Skan    {
971169689Skan      if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
972169689Skan	continue;
973169689Skan
974169689Skan      step = determine_biv_step (phi);
975169689Skan      if (!step)
976169689Skan	continue;
977169689Skan
978169689Skan      base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
979169689Skan      base = expand_simple_operations (base);
980169689Skan      if (contains_abnormal_ssa_name_p (base)
981169689Skan	  || contains_abnormal_ssa_name_p (step))
982169689Skan	continue;
983169689Skan
984169689Skan      type = TREE_TYPE (PHI_RESULT (phi));
985169689Skan      base = fold_convert (type, base);
986169689Skan      if (step)
987169689Skan	step = fold_convert (type, step);
988169689Skan
989169689Skan      set_iv (data, PHI_RESULT (phi), base, step);
990169689Skan      found = true;
991169689Skan    }
992169689Skan
993169689Skan  return found;
994169689Skan}
995169689Skan
996169689Skan/* Marks basic ivs.  */
997169689Skan
998169689Skanstatic void
999169689Skanmark_bivs (struct ivopts_data *data)
1000169689Skan{
1001169689Skan  tree phi, var;
1002169689Skan  struct iv *iv, *incr_iv;
1003169689Skan  struct loop *loop = data->current_loop;
1004169689Skan  basic_block incr_bb;
1005169689Skan
1006169689Skan  for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
1007169689Skan    {
1008169689Skan      iv = get_iv (data, PHI_RESULT (phi));
1009169689Skan      if (!iv)
1010169689Skan	continue;
1011169689Skan
1012169689Skan      var = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1013169689Skan      incr_iv = get_iv (data, var);
1014169689Skan      if (!incr_iv)
1015169689Skan	continue;
1016169689Skan
1017169689Skan      /* If the increment is in the subloop, ignore it.  */
1018169689Skan      incr_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
1019169689Skan      if (incr_bb->loop_father != data->current_loop
1020169689Skan	  || (incr_bb->flags & BB_IRREDUCIBLE_LOOP))
1021169689Skan	continue;
1022169689Skan
1023169689Skan      iv->biv_p = true;
1024169689Skan      incr_iv->biv_p = true;
1025169689Skan    }
1026169689Skan}
1027169689Skan
1028169689Skan/* Checks whether STMT defines a linear induction variable and stores its
1029169689Skan   parameters to IV.  */
1030169689Skan
1031169689Skanstatic bool
1032169689Skanfind_givs_in_stmt_scev (struct ivopts_data *data, tree stmt, affine_iv *iv)
1033169689Skan{
1034169689Skan  tree lhs;
1035169689Skan  struct loop *loop = data->current_loop;
1036169689Skan
1037169689Skan  iv->base = NULL_TREE;
1038169689Skan  iv->step = NULL_TREE;
1039169689Skan
1040169689Skan  if (TREE_CODE (stmt) != MODIFY_EXPR)
1041169689Skan    return false;
1042169689Skan
1043169689Skan  lhs = TREE_OPERAND (stmt, 0);
1044169689Skan  if (TREE_CODE (lhs) != SSA_NAME)
1045169689Skan    return false;
1046169689Skan
1047169689Skan  if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), iv, true))
1048169689Skan    return false;
1049169689Skan  iv->base = expand_simple_operations (iv->base);
1050169689Skan
1051169689Skan  if (contains_abnormal_ssa_name_p (iv->base)
1052169689Skan      || contains_abnormal_ssa_name_p (iv->step))
1053169689Skan    return false;
1054169689Skan
1055169689Skan  return true;
1056169689Skan}
1057169689Skan
1058169689Skan/* Finds general ivs in statement STMT.  */
1059169689Skan
1060169689Skanstatic void
1061169689Skanfind_givs_in_stmt (struct ivopts_data *data, tree stmt)
1062169689Skan{
1063169689Skan  affine_iv iv;
1064169689Skan
1065169689Skan  if (!find_givs_in_stmt_scev (data, stmt, &iv))
1066169689Skan    return;
1067169689Skan
1068169689Skan  set_iv (data, TREE_OPERAND (stmt, 0), iv.base, iv.step);
1069169689Skan}
1070169689Skan
1071169689Skan/* Finds general ivs in basic block BB.  */
1072169689Skan
1073169689Skanstatic void
1074169689Skanfind_givs_in_bb (struct ivopts_data *data, basic_block bb)
1075169689Skan{
1076169689Skan  block_stmt_iterator bsi;
1077169689Skan
1078169689Skan  for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1079169689Skan    find_givs_in_stmt (data, bsi_stmt (bsi));
1080169689Skan}
1081169689Skan
1082169689Skan/* Finds general ivs.  */
1083169689Skan
1084169689Skanstatic void
1085169689Skanfind_givs (struct ivopts_data *data)
1086169689Skan{
1087169689Skan  struct loop *loop = data->current_loop;
1088169689Skan  basic_block *body = get_loop_body_in_dom_order (loop);
1089169689Skan  unsigned i;
1090169689Skan
1091169689Skan  for (i = 0; i < loop->num_nodes; i++)
1092169689Skan    find_givs_in_bb (data, body[i]);
1093169689Skan  free (body);
1094169689Skan}
1095169689Skan
1096169689Skan/* For each ssa name defined in LOOP determines whether it is an induction
1097169689Skan   variable and if so, its initial value and step.  */
1098169689Skan
1099169689Skanstatic bool
1100169689Skanfind_induction_variables (struct ivopts_data *data)
1101169689Skan{
1102169689Skan  unsigned i;
1103169689Skan  bitmap_iterator bi;
1104169689Skan
1105169689Skan  if (!find_bivs (data))
1106169689Skan    return false;
1107169689Skan
1108169689Skan  find_givs (data);
1109169689Skan  mark_bivs (data);
1110169689Skan
1111169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
1112169689Skan    {
1113169689Skan      tree niter = niter_for_single_dom_exit (data);
1114169689Skan
1115169689Skan      if (niter)
1116169689Skan	{
1117169689Skan	  fprintf (dump_file, "  number of iterations ");
1118169689Skan	  print_generic_expr (dump_file, niter, TDF_SLIM);
1119169689Skan	  fprintf (dump_file, "\n\n");
1120169689Skan    	};
1121169689Skan
1122169689Skan      fprintf (dump_file, "Induction variables:\n\n");
1123169689Skan
1124169689Skan      EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
1125169689Skan	{
1126169689Skan	  if (ver_info (data, i)->iv)
1127169689Skan	    dump_iv (dump_file, ver_info (data, i)->iv);
1128169689Skan	}
1129169689Skan    }
1130169689Skan
1131169689Skan  return true;
1132169689Skan}
1133169689Skan
1134169689Skan/* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV.  */
1135169689Skan
1136169689Skanstatic struct iv_use *
1137169689Skanrecord_use (struct ivopts_data *data, tree *use_p, struct iv *iv,
1138169689Skan	    tree stmt, enum use_type use_type)
1139169689Skan{
1140169689Skan  struct iv_use *use = XCNEW (struct iv_use);
1141169689Skan
1142169689Skan  use->id = n_iv_uses (data);
1143169689Skan  use->type = use_type;
1144169689Skan  use->iv = iv;
1145169689Skan  use->stmt = stmt;
1146169689Skan  use->op_p = use_p;
1147169689Skan  use->related_cands = BITMAP_ALLOC (NULL);
1148169689Skan
1149169689Skan  /* To avoid showing ssa name in the dumps, if it was not reset by the
1150169689Skan     caller.  */
1151169689Skan  iv->ssa_name = NULL_TREE;
1152169689Skan
1153169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
1154169689Skan    dump_use (dump_file, use);
1155169689Skan
1156169689Skan  VEC_safe_push (iv_use_p, heap, data->iv_uses, use);
1157169689Skan
1158169689Skan  return use;
1159169689Skan}
1160169689Skan
1161169689Skan/* Checks whether OP is a loop-level invariant and if so, records it.
1162169689Skan   NONLINEAR_USE is true if the invariant is used in a way we do not
1163169689Skan   handle specially.  */
1164169689Skan
1165169689Skanstatic void
1166169689Skanrecord_invariant (struct ivopts_data *data, tree op, bool nonlinear_use)
1167169689Skan{
1168169689Skan  basic_block bb;
1169169689Skan  struct version_info *info;
1170169689Skan
1171169689Skan  if (TREE_CODE (op) != SSA_NAME
1172169689Skan      || !is_gimple_reg (op))
1173169689Skan    return;
1174169689Skan
1175169689Skan  bb = bb_for_stmt (SSA_NAME_DEF_STMT (op));
1176169689Skan  if (bb
1177169689Skan      && flow_bb_inside_loop_p (data->current_loop, bb))
1178169689Skan    return;
1179169689Skan
1180169689Skan  info = name_info (data, op);
1181169689Skan  info->name = op;
1182169689Skan  info->has_nonlin_use |= nonlinear_use;
1183169689Skan  if (!info->inv_id)
1184169689Skan    info->inv_id = ++data->max_inv_id;
1185169689Skan  bitmap_set_bit (data->relevant, SSA_NAME_VERSION (op));
1186169689Skan}
1187169689Skan
1188169689Skan/* Checks whether the use OP is interesting and if so, records it.  */
1189169689Skan
1190169689Skanstatic struct iv_use *
1191169689Skanfind_interesting_uses_op (struct ivopts_data *data, tree op)
1192169689Skan{
1193169689Skan  struct iv *iv;
1194169689Skan  struct iv *civ;
1195169689Skan  tree stmt;
1196169689Skan  struct iv_use *use;
1197169689Skan
1198169689Skan  if (TREE_CODE (op) != SSA_NAME)
1199169689Skan    return NULL;
1200169689Skan
1201169689Skan  iv = get_iv (data, op);
1202169689Skan  if (!iv)
1203169689Skan    return NULL;
1204169689Skan
1205169689Skan  if (iv->have_use_for)
1206169689Skan    {
1207169689Skan      use = iv_use (data, iv->use_id);
1208169689Skan
1209169689Skan      gcc_assert (use->type == USE_NONLINEAR_EXPR);
1210169689Skan      return use;
1211169689Skan    }
1212169689Skan
1213169689Skan  if (zero_p (iv->step))
1214169689Skan    {
1215169689Skan      record_invariant (data, op, true);
1216169689Skan      return NULL;
1217169689Skan    }
1218169689Skan  iv->have_use_for = true;
1219169689Skan
1220169689Skan  civ = XNEW (struct iv);
1221169689Skan  *civ = *iv;
1222169689Skan
1223169689Skan  stmt = SSA_NAME_DEF_STMT (op);
1224169689Skan  gcc_assert (TREE_CODE (stmt) == PHI_NODE
1225169689Skan	      || TREE_CODE (stmt) == MODIFY_EXPR);
1226169689Skan
1227169689Skan  use = record_use (data, NULL, civ, stmt, USE_NONLINEAR_EXPR);
1228169689Skan  iv->use_id = use->id;
1229169689Skan
1230169689Skan  return use;
1231169689Skan}
1232169689Skan
1233169689Skan/* Checks whether the condition *COND_P in STMT is interesting
1234169689Skan   and if so, records it.  */
1235169689Skan
1236169689Skanstatic void
1237169689Skanfind_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
1238169689Skan{
1239169689Skan  tree *op0_p;
1240169689Skan  tree *op1_p;
1241169689Skan  struct iv *iv0 = NULL, *iv1 = NULL, *civ;
1242169689Skan  struct iv const_iv;
1243169689Skan  tree zero = integer_zero_node;
1244169689Skan
1245169689Skan  const_iv.step = NULL_TREE;
1246169689Skan
1247169689Skan  if (TREE_CODE (*cond_p) != SSA_NAME
1248169689Skan      && !COMPARISON_CLASS_P (*cond_p))
1249169689Skan    return;
1250169689Skan
1251169689Skan  if (TREE_CODE (*cond_p) == SSA_NAME)
1252169689Skan    {
1253169689Skan      op0_p = cond_p;
1254169689Skan      op1_p = &zero;
1255169689Skan    }
1256169689Skan  else
1257169689Skan    {
1258169689Skan      op0_p = &TREE_OPERAND (*cond_p, 0);
1259169689Skan      op1_p = &TREE_OPERAND (*cond_p, 1);
1260169689Skan    }
1261169689Skan
1262169689Skan  if (TREE_CODE (*op0_p) == SSA_NAME)
1263169689Skan    iv0 = get_iv (data, *op0_p);
1264169689Skan  else
1265169689Skan    iv0 = &const_iv;
1266169689Skan
1267169689Skan  if (TREE_CODE (*op1_p) == SSA_NAME)
1268169689Skan    iv1 = get_iv (data, *op1_p);
1269169689Skan  else
1270169689Skan    iv1 = &const_iv;
1271169689Skan
1272169689Skan  if (/* When comparing with non-invariant value, we may not do any senseful
1273169689Skan	 induction variable elimination.  */
1274169689Skan      (!iv0 || !iv1)
1275169689Skan      /* Eliminating condition based on two ivs would be nontrivial.
1276169689Skan	 ??? TODO -- it is not really important to handle this case.  */
1277169689Skan      || (!zero_p (iv0->step) && !zero_p (iv1->step)))
1278169689Skan    {
1279169689Skan      find_interesting_uses_op (data, *op0_p);
1280169689Skan      find_interesting_uses_op (data, *op1_p);
1281169689Skan      return;
1282169689Skan    }
1283169689Skan
1284169689Skan  if (zero_p (iv0->step) && zero_p (iv1->step))
1285169689Skan    {
1286169689Skan      /* If both are invariants, this is a work for unswitching.  */
1287169689Skan      return;
1288169689Skan    }
1289169689Skan
1290169689Skan  civ = XNEW (struct iv);
1291169689Skan  *civ = zero_p (iv0->step) ? *iv1: *iv0;
1292169689Skan  record_use (data, cond_p, civ, stmt, USE_COMPARE);
1293169689Skan}
1294169689Skan
1295169689Skan/* Returns true if expression EXPR is obviously invariant in LOOP,
1296169689Skan   i.e. if all its operands are defined outside of the LOOP.  */
1297169689Skan
1298169689Skanbool
1299169689Skanexpr_invariant_in_loop_p (struct loop *loop, tree expr)
1300169689Skan{
1301169689Skan  basic_block def_bb;
1302169689Skan  unsigned i, len;
1303169689Skan
1304169689Skan  if (is_gimple_min_invariant (expr))
1305169689Skan    return true;
1306169689Skan
1307169689Skan  if (TREE_CODE (expr) == SSA_NAME)
1308169689Skan    {
1309169689Skan      def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (expr));
1310169689Skan      if (def_bb
1311169689Skan	  && flow_bb_inside_loop_p (loop, def_bb))
1312169689Skan	return false;
1313169689Skan
1314169689Skan      return true;
1315169689Skan    }
1316169689Skan
1317169689Skan  if (!EXPR_P (expr))
1318169689Skan    return false;
1319169689Skan
1320169689Skan  len = TREE_CODE_LENGTH (TREE_CODE (expr));
1321169689Skan  for (i = 0; i < len; i++)
1322169689Skan    if (!expr_invariant_in_loop_p (loop, TREE_OPERAND (expr, i)))
1323169689Skan      return false;
1324169689Skan
1325169689Skan  return true;
1326169689Skan}
1327169689Skan
1328169689Skan/* Cumulates the steps of indices into DATA and replaces their values with the
1329169689Skan   initial ones.  Returns false when the value of the index cannot be determined.
1330169689Skan   Callback for for_each_index.  */
1331169689Skan
1332169689Skanstruct ifs_ivopts_data
1333169689Skan{
1334169689Skan  struct ivopts_data *ivopts_data;
1335169689Skan  tree stmt;
1336169689Skan  tree *step_p;
1337169689Skan};
1338169689Skan
1339169689Skanstatic bool
1340169689Skanidx_find_step (tree base, tree *idx, void *data)
1341169689Skan{
1342169689Skan  struct ifs_ivopts_data *dta = data;
1343169689Skan  struct iv *iv;
1344169689Skan  tree step, iv_base, iv_step, lbound, off;
1345169689Skan  struct loop *loop = dta->ivopts_data->current_loop;
1346169689Skan
1347169689Skan  if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF
1348169689Skan      || TREE_CODE (base) == ALIGN_INDIRECT_REF)
1349169689Skan    return false;
1350169689Skan
1351169689Skan  /* If base is a component ref, require that the offset of the reference
1352169689Skan     be invariant.  */
1353169689Skan  if (TREE_CODE (base) == COMPONENT_REF)
1354169689Skan    {
1355169689Skan      off = component_ref_field_offset (base);
1356169689Skan      return expr_invariant_in_loop_p (loop, off);
1357169689Skan    }
1358169689Skan
1359169689Skan  /* If base is array, first check whether we will be able to move the
1360169689Skan     reference out of the loop (in order to take its address in strength
1361169689Skan     reduction).  In order for this to work we need both lower bound
1362169689Skan     and step to be loop invariants.  */
1363169689Skan  if (TREE_CODE (base) == ARRAY_REF)
1364169689Skan    {
1365169689Skan      step = array_ref_element_size (base);
1366169689Skan      lbound = array_ref_low_bound (base);
1367169689Skan
1368169689Skan      if (!expr_invariant_in_loop_p (loop, step)
1369169689Skan	  || !expr_invariant_in_loop_p (loop, lbound))
1370169689Skan	return false;
1371169689Skan    }
1372169689Skan
1373169689Skan  if (TREE_CODE (*idx) != SSA_NAME)
1374169689Skan    return true;
1375169689Skan
1376169689Skan  iv = get_iv (dta->ivopts_data, *idx);
1377169689Skan  if (!iv)
1378169689Skan    return false;
1379169689Skan
1380169689Skan  /* XXX  We produce for a base of *D42 with iv->base being &x[0]
1381169689Skan	  *&x[0], which is not folded and does not trigger the
1382169689Skan	  ARRAY_REF path below.  */
1383169689Skan  *idx = iv->base;
1384169689Skan
1385169689Skan  if (!iv->step)
1386169689Skan    return true;
1387169689Skan
1388169689Skan  if (TREE_CODE (base) == ARRAY_REF)
1389169689Skan    {
1390169689Skan      step = array_ref_element_size (base);
1391169689Skan
1392169689Skan      /* We only handle addresses whose step is an integer constant.  */
1393169689Skan      if (TREE_CODE (step) != INTEGER_CST)
1394169689Skan	return false;
1395169689Skan    }
1396169689Skan  else
1397169689Skan    /* The step for pointer arithmetics already is 1 byte.  */
1398169689Skan    step = build_int_cst (sizetype, 1);
1399169689Skan
1400169689Skan  iv_base = iv->base;
1401169689Skan  iv_step = iv->step;
1402169689Skan  if (!convert_affine_scev (dta->ivopts_data->current_loop,
1403169689Skan			    sizetype, &iv_base, &iv_step, dta->stmt,
1404169689Skan			    false))
1405169689Skan    {
1406169689Skan      /* The index might wrap.  */
1407169689Skan      return false;
1408169689Skan    }
1409169689Skan
1410169689Skan  step = fold_build2 (MULT_EXPR, sizetype, step, iv_step);
1411169689Skan
1412169689Skan  if (!*dta->step_p)
1413169689Skan    *dta->step_p = step;
1414169689Skan  else
1415169689Skan    *dta->step_p = fold_build2 (PLUS_EXPR, sizetype, *dta->step_p, step);
1416169689Skan
1417169689Skan  return true;
1418169689Skan}
1419169689Skan
1420169689Skan/* Records use in index IDX.  Callback for for_each_index.  Ivopts data
1421169689Skan   object is passed to it in DATA.  */
1422169689Skan
1423169689Skanstatic bool
1424169689Skanidx_record_use (tree base, tree *idx,
1425169689Skan		void *data)
1426169689Skan{
1427169689Skan  find_interesting_uses_op (data, *idx);
1428169689Skan  if (TREE_CODE (base) == ARRAY_REF)
1429169689Skan    {
1430169689Skan      find_interesting_uses_op (data, array_ref_element_size (base));
1431169689Skan      find_interesting_uses_op (data, array_ref_low_bound (base));
1432169689Skan    }
1433169689Skan  return true;
1434169689Skan}
1435169689Skan
1436169689Skan/* Returns true if memory reference REF may be unaligned.  */
1437169689Skan
1438169689Skanstatic bool
1439169689Skanmay_be_unaligned_p (tree ref)
1440169689Skan{
1441169689Skan  tree base;
1442169689Skan  tree base_type;
1443169689Skan  HOST_WIDE_INT bitsize;
1444169689Skan  HOST_WIDE_INT bitpos;
1445169689Skan  tree toffset;
1446169689Skan  enum machine_mode mode;
1447169689Skan  int unsignedp, volatilep;
1448169689Skan  unsigned base_align;
1449169689Skan
1450169689Skan  /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
1451169689Skan     thus they are not misaligned.  */
1452169689Skan  if (TREE_CODE (ref) == TARGET_MEM_REF)
1453169689Skan    return false;
1454169689Skan
1455169689Skan  /* The test below is basically copy of what expr.c:normal_inner_ref
1456169689Skan     does to check whether the object must be loaded by parts when
1457169689Skan     STRICT_ALIGNMENT is true.  */
1458169689Skan  base = get_inner_reference (ref, &bitsize, &bitpos, &toffset, &mode,
1459169689Skan			      &unsignedp, &volatilep, true);
1460169689Skan  base_type = TREE_TYPE (base);
1461169689Skan  base_align = TYPE_ALIGN (base_type);
1462169689Skan
1463169689Skan  if (mode != BLKmode
1464169689Skan      && (base_align < GET_MODE_ALIGNMENT (mode)
1465169689Skan	  || bitpos % GET_MODE_ALIGNMENT (mode) != 0
1466169689Skan	  || bitpos % BITS_PER_UNIT != 0))
1467169689Skan    return true;
1468169689Skan
1469169689Skan  return false;
1470169689Skan}
1471169689Skan
1472169689Skan/* Return true if EXPR may be non-addressable.   */
1473169689Skan
1474169689Skanstatic bool
1475169689Skanmay_be_nonaddressable_p (tree expr)
1476169689Skan{
1477169689Skan  switch (TREE_CODE (expr))
1478169689Skan    {
1479169689Skan    case COMPONENT_REF:
1480169689Skan      return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr, 1))
1481169689Skan	     || may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
1482169689Skan
1483169689Skan    case ARRAY_REF:
1484169689Skan    case ARRAY_RANGE_REF:
1485169689Skan      return may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
1486169689Skan
1487169689Skan    case VIEW_CONVERT_EXPR:
1488169689Skan      /* This kind of view-conversions may wrap non-addressable objects
1489169689Skan	 and make them look addressable.  After some processing the
1490169689Skan	 non-addressability may be uncovered again, causing ADDR_EXPRs
1491169689Skan	 of inappropriate objects to be built.  */
1492169689Skan      return AGGREGATE_TYPE_P (TREE_TYPE (expr))
1493169689Skan	     && !AGGREGATE_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)));
1494169689Skan
1495169689Skan    default:
1496169689Skan      break;
1497169689Skan    }
1498169689Skan
1499169689Skan  return false;
1500169689Skan}
1501169689Skan
1502169689Skan/* Finds addresses in *OP_P inside STMT.  */
1503169689Skan
1504169689Skanstatic void
1505169689Skanfind_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
1506169689Skan{
1507169689Skan  tree base = *op_p, step = NULL;
1508169689Skan  struct iv *civ;
1509169689Skan  struct ifs_ivopts_data ifs_ivopts_data;
1510169689Skan
1511169689Skan  /* Do not play with volatile memory references.  A bit too conservative,
1512169689Skan     perhaps, but safe.  */
1513169689Skan  if (stmt_ann (stmt)->has_volatile_ops)
1514169689Skan    goto fail;
1515169689Skan
1516169689Skan  /* Ignore bitfields for now.  Not really something terribly complicated
1517169689Skan     to handle.  TODO.  */
1518169689Skan  if (TREE_CODE (base) == BIT_FIELD_REF)
1519169689Skan    goto fail;
1520169689Skan
1521169689Skan  if (may_be_nonaddressable_p (base))
1522169689Skan    goto fail;
1523169689Skan
1524169689Skan  if (STRICT_ALIGNMENT
1525169689Skan      && may_be_unaligned_p (base))
1526169689Skan    goto fail;
1527169689Skan
1528169689Skan  base = unshare_expr (base);
1529169689Skan
1530169689Skan  if (TREE_CODE (base) == TARGET_MEM_REF)
1531169689Skan    {
1532169689Skan      tree type = build_pointer_type (TREE_TYPE (base));
1533169689Skan      tree astep;
1534169689Skan
1535169689Skan      if (TMR_BASE (base)
1536169689Skan	  && TREE_CODE (TMR_BASE (base)) == SSA_NAME)
1537169689Skan	{
1538169689Skan	  civ = get_iv (data, TMR_BASE (base));
1539169689Skan	  if (!civ)
1540169689Skan	    goto fail;
1541169689Skan
1542169689Skan	  TMR_BASE (base) = civ->base;
1543169689Skan	  step = civ->step;
1544169689Skan	}
1545169689Skan      if (TMR_INDEX (base)
1546169689Skan	  && TREE_CODE (TMR_INDEX (base)) == SSA_NAME)
1547169689Skan	{
1548169689Skan	  civ = get_iv (data, TMR_INDEX (base));
1549169689Skan	  if (!civ)
1550169689Skan	    goto fail;
1551169689Skan
1552169689Skan	  TMR_INDEX (base) = civ->base;
1553169689Skan	  astep = civ->step;
1554169689Skan
1555169689Skan	  if (astep)
1556169689Skan	    {
1557169689Skan	      if (TMR_STEP (base))
1558169689Skan		astep = fold_build2 (MULT_EXPR, type, TMR_STEP (base), astep);
1559169689Skan
1560169689Skan	      if (step)
1561169689Skan		step = fold_build2 (PLUS_EXPR, type, step, astep);
1562169689Skan	      else
1563169689Skan		step = astep;
1564169689Skan	    }
1565169689Skan	}
1566169689Skan
1567169689Skan      if (zero_p (step))
1568169689Skan	goto fail;
1569169689Skan      base = tree_mem_ref_addr (type, base);
1570169689Skan    }
1571169689Skan  else
1572169689Skan    {
1573169689Skan      ifs_ivopts_data.ivopts_data = data;
1574169689Skan      ifs_ivopts_data.stmt = stmt;
1575169689Skan      ifs_ivopts_data.step_p = &step;
1576169689Skan      if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
1577169689Skan	  || zero_p (step))
1578169689Skan	goto fail;
1579169689Skan
1580169689Skan      gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
1581169689Skan      gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
1582169689Skan
1583169689Skan      base = build_fold_addr_expr (base);
1584169689Skan
1585169689Skan      /* Substituting bases of IVs into the base expression might
1586169689Skan	 have caused folding opportunities.  */
1587169689Skan      if (TREE_CODE (base) == ADDR_EXPR)
1588169689Skan	{
1589169689Skan	  tree *ref = &TREE_OPERAND (base, 0);
1590169689Skan	  while (handled_component_p (*ref))
1591169689Skan	    ref = &TREE_OPERAND (*ref, 0);
1592169689Skan	  if (TREE_CODE (*ref) == INDIRECT_REF)
1593169689Skan	    *ref = fold_indirect_ref (*ref);
1594169689Skan	}
1595169689Skan    }
1596169689Skan
1597169689Skan  civ = alloc_iv (base, step);
1598169689Skan  record_use (data, op_p, civ, stmt, USE_ADDRESS);
1599169689Skan  return;
1600169689Skan
1601169689Skanfail:
1602169689Skan  for_each_index (op_p, idx_record_use, data);
1603169689Skan}
1604169689Skan
1605169689Skan/* Finds and records invariants used in STMT.  */
1606169689Skan
1607169689Skanstatic void
1608169689Skanfind_invariants_stmt (struct ivopts_data *data, tree stmt)
1609169689Skan{
1610169689Skan  ssa_op_iter iter;
1611169689Skan  use_operand_p use_p;
1612169689Skan  tree op;
1613169689Skan
1614169689Skan  FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1615169689Skan    {
1616169689Skan      op = USE_FROM_PTR (use_p);
1617169689Skan      record_invariant (data, op, false);
1618169689Skan    }
1619169689Skan}
1620169689Skan
1621169689Skan/* Finds interesting uses of induction variables in the statement STMT.  */
1622169689Skan
1623169689Skanstatic void
1624169689Skanfind_interesting_uses_stmt (struct ivopts_data *data, tree stmt)
1625169689Skan{
1626169689Skan  struct iv *iv;
1627169689Skan  tree op, lhs, rhs;
1628169689Skan  ssa_op_iter iter;
1629169689Skan  use_operand_p use_p;
1630169689Skan
1631169689Skan  find_invariants_stmt (data, stmt);
1632169689Skan
1633169689Skan  if (TREE_CODE (stmt) == COND_EXPR)
1634169689Skan    {
1635169689Skan      find_interesting_uses_cond (data, stmt, &COND_EXPR_COND (stmt));
1636169689Skan      return;
1637169689Skan    }
1638169689Skan
1639169689Skan  if (TREE_CODE (stmt) == MODIFY_EXPR)
1640169689Skan    {
1641169689Skan      lhs = TREE_OPERAND (stmt, 0);
1642169689Skan      rhs = TREE_OPERAND (stmt, 1);
1643169689Skan
1644169689Skan      if (TREE_CODE (lhs) == SSA_NAME)
1645169689Skan	{
1646169689Skan	  /* If the statement defines an induction variable, the uses are not
1647169689Skan	     interesting by themselves.  */
1648169689Skan
1649169689Skan	  iv = get_iv (data, lhs);
1650169689Skan
1651169689Skan	  if (iv && !zero_p (iv->step))
1652169689Skan	    return;
1653169689Skan	}
1654169689Skan
1655169689Skan      switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
1656169689Skan	{
1657169689Skan	case tcc_comparison:
1658169689Skan	  find_interesting_uses_cond (data, stmt, &TREE_OPERAND (stmt, 1));
1659169689Skan	  return;
1660169689Skan
1661169689Skan	case tcc_reference:
1662169689Skan	  find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 1));
1663169689Skan	  if (REFERENCE_CLASS_P (lhs))
1664169689Skan	    find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
1665169689Skan	  return;
1666169689Skan
1667169689Skan	default: ;
1668169689Skan	}
1669169689Skan
1670169689Skan      if (REFERENCE_CLASS_P (lhs)
1671169689Skan	  && is_gimple_val (rhs))
1672169689Skan	{
1673169689Skan	  find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
1674169689Skan	  find_interesting_uses_op (data, rhs);
1675169689Skan	  return;
1676169689Skan	}
1677169689Skan
1678169689Skan      /* TODO -- we should also handle address uses of type
1679169689Skan
1680169689Skan	 memory = call (whatever);
1681169689Skan
1682169689Skan	 and
1683169689Skan
1684169689Skan	 call (memory).  */
1685169689Skan    }
1686169689Skan
1687169689Skan  if (TREE_CODE (stmt) == PHI_NODE
1688169689Skan      && bb_for_stmt (stmt) == data->current_loop->header)
1689169689Skan    {
1690169689Skan      lhs = PHI_RESULT (stmt);
1691169689Skan      iv = get_iv (data, lhs);
1692169689Skan
1693169689Skan      if (iv && !zero_p (iv->step))
1694169689Skan	return;
1695169689Skan    }
1696169689Skan
1697169689Skan  FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1698169689Skan    {
1699169689Skan      op = USE_FROM_PTR (use_p);
1700169689Skan
1701169689Skan      if (TREE_CODE (op) != SSA_NAME)
1702169689Skan	continue;
1703169689Skan
1704169689Skan      iv = get_iv (data, op);
1705169689Skan      if (!iv)
1706169689Skan	continue;
1707169689Skan
1708169689Skan      find_interesting_uses_op (data, op);
1709169689Skan    }
1710169689Skan}
1711169689Skan
1712169689Skan/* Finds interesting uses of induction variables outside of loops
1713169689Skan   on loop exit edge EXIT.  */
1714169689Skan
1715169689Skanstatic void
1716169689Skanfind_interesting_uses_outside (struct ivopts_data *data, edge exit)
1717169689Skan{
1718169689Skan  tree phi, def;
1719169689Skan
1720169689Skan  for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
1721169689Skan    {
1722169689Skan      def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1723169689Skan      find_interesting_uses_op (data, def);
1724169689Skan    }
1725169689Skan}
1726169689Skan
1727169689Skan/* Finds uses of the induction variables that are interesting.  */
1728169689Skan
1729169689Skanstatic void
1730169689Skanfind_interesting_uses (struct ivopts_data *data)
1731169689Skan{
1732169689Skan  basic_block bb;
1733169689Skan  block_stmt_iterator bsi;
1734169689Skan  tree phi;
1735169689Skan  basic_block *body = get_loop_body (data->current_loop);
1736169689Skan  unsigned i;
1737169689Skan  struct version_info *info;
1738169689Skan  edge e;
1739169689Skan
1740169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
1741169689Skan    fprintf (dump_file, "Uses:\n\n");
1742169689Skan
1743169689Skan  for (i = 0; i < data->current_loop->num_nodes; i++)
1744169689Skan    {
1745169689Skan      edge_iterator ei;
1746169689Skan      bb = body[i];
1747169689Skan
1748169689Skan      FOR_EACH_EDGE (e, ei, bb->succs)
1749169689Skan	if (e->dest != EXIT_BLOCK_PTR
1750169689Skan	    && !flow_bb_inside_loop_p (data->current_loop, e->dest))
1751169689Skan	  find_interesting_uses_outside (data, e);
1752169689Skan
1753169689Skan      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1754169689Skan	find_interesting_uses_stmt (data, phi);
1755169689Skan      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1756169689Skan	find_interesting_uses_stmt (data, bsi_stmt (bsi));
1757169689Skan    }
1758169689Skan
1759169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
1760169689Skan    {
1761169689Skan      bitmap_iterator bi;
1762169689Skan
1763169689Skan      fprintf (dump_file, "\n");
1764169689Skan
1765169689Skan      EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
1766169689Skan	{
1767169689Skan	  info = ver_info (data, i);
1768169689Skan	  if (info->inv_id)
1769169689Skan	    {
1770169689Skan	      fprintf (dump_file, "  ");
1771169689Skan	      print_generic_expr (dump_file, info->name, TDF_SLIM);
1772169689Skan	      fprintf (dump_file, " is invariant (%d)%s\n",
1773169689Skan		       info->inv_id, info->has_nonlin_use ? "" : ", eliminable");
1774169689Skan	    }
1775169689Skan	}
1776169689Skan
1777169689Skan      fprintf (dump_file, "\n");
1778169689Skan    }
1779169689Skan
1780169689Skan  free (body);
1781169689Skan}
1782169689Skan
1783169689Skan/* Strips constant offsets from EXPR and stores them to OFFSET.  If INSIDE_ADDR
1784169689Skan   is true, assume we are inside an address.  If TOP_COMPREF is true, assume
1785169689Skan   we are at the top-level of the processed address.  */
1786169689Skan
1787169689Skanstatic tree
1788169689Skanstrip_offset_1 (tree expr, bool inside_addr, bool top_compref,
1789169689Skan		unsigned HOST_WIDE_INT *offset)
1790169689Skan{
1791169689Skan  tree op0 = NULL_TREE, op1 = NULL_TREE, tmp, step;
1792169689Skan  enum tree_code code;
1793169689Skan  tree type, orig_type = TREE_TYPE (expr);
1794169689Skan  unsigned HOST_WIDE_INT off0, off1, st;
1795169689Skan  tree orig_expr = expr;
1796169689Skan
1797169689Skan  STRIP_NOPS (expr);
1798169689Skan
1799169689Skan  type = TREE_TYPE (expr);
1800169689Skan  code = TREE_CODE (expr);
1801169689Skan  *offset = 0;
1802169689Skan
1803169689Skan  switch (code)
1804169689Skan    {
1805169689Skan    case INTEGER_CST:
1806169689Skan      if (!cst_and_fits_in_hwi (expr)
1807169689Skan	  || zero_p (expr))
1808169689Skan	return orig_expr;
1809169689Skan
1810169689Skan      *offset = int_cst_value (expr);
1811169689Skan      return build_int_cst (orig_type, 0);
1812169689Skan
1813169689Skan    case PLUS_EXPR:
1814169689Skan    case MINUS_EXPR:
1815169689Skan      op0 = TREE_OPERAND (expr, 0);
1816169689Skan      op1 = TREE_OPERAND (expr, 1);
1817169689Skan
1818169689Skan      op0 = strip_offset_1 (op0, false, false, &off0);
1819169689Skan      op1 = strip_offset_1 (op1, false, false, &off1);
1820169689Skan
1821169689Skan      *offset = (code == PLUS_EXPR ? off0 + off1 : off0 - off1);
1822169689Skan      if (op0 == TREE_OPERAND (expr, 0)
1823169689Skan	  && op1 == TREE_OPERAND (expr, 1))
1824169689Skan	return orig_expr;
1825169689Skan
1826169689Skan      if (zero_p (op1))
1827169689Skan	expr = op0;
1828169689Skan      else if (zero_p (op0))
1829169689Skan	{
1830169689Skan	  if (code == PLUS_EXPR)
1831169689Skan	    expr = op1;
1832169689Skan	  else
1833169689Skan	    expr = fold_build1 (NEGATE_EXPR, type, op1);
1834169689Skan	}
1835169689Skan      else
1836169689Skan	expr = fold_build2 (code, type, op0, op1);
1837169689Skan
1838169689Skan      return fold_convert (orig_type, expr);
1839169689Skan
1840169689Skan    case ARRAY_REF:
1841169689Skan      if (!inside_addr)
1842169689Skan	return orig_expr;
1843169689Skan
1844169689Skan      step = array_ref_element_size (expr);
1845169689Skan      if (!cst_and_fits_in_hwi (step))
1846169689Skan	break;
1847169689Skan
1848169689Skan      st = int_cst_value (step);
1849169689Skan      op1 = TREE_OPERAND (expr, 1);
1850169689Skan      op1 = strip_offset_1 (op1, false, false, &off1);
1851169689Skan      *offset = off1 * st;
1852169689Skan
1853169689Skan      if (top_compref
1854169689Skan	  && zero_p (op1))
1855169689Skan	{
1856169689Skan	  /* Strip the component reference completely.  */
1857169689Skan	  op0 = TREE_OPERAND (expr, 0);
1858169689Skan	  op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
1859169689Skan	  *offset += off0;
1860169689Skan	  return op0;
1861169689Skan	}
1862169689Skan      break;
1863169689Skan
1864169689Skan    case COMPONENT_REF:
1865169689Skan      if (!inside_addr)
1866169689Skan	return orig_expr;
1867169689Skan
1868169689Skan      tmp = component_ref_field_offset (expr);
1869169689Skan      if (top_compref
1870169689Skan	  && cst_and_fits_in_hwi (tmp))
1871169689Skan	{
1872169689Skan	  /* Strip the component reference completely.  */
1873169689Skan	  op0 = TREE_OPERAND (expr, 0);
1874169689Skan	  op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
1875169689Skan	  *offset = off0 + int_cst_value (tmp);
1876169689Skan	  return op0;
1877169689Skan	}
1878169689Skan      break;
1879169689Skan
1880169689Skan    case ADDR_EXPR:
1881169689Skan      op0 = TREE_OPERAND (expr, 0);
1882169689Skan      op0 = strip_offset_1 (op0, true, true, &off0);
1883169689Skan      *offset += off0;
1884169689Skan
1885169689Skan      if (op0 == TREE_OPERAND (expr, 0))
1886169689Skan	return orig_expr;
1887169689Skan
1888169689Skan      expr = build_fold_addr_expr (op0);
1889169689Skan      return fold_convert (orig_type, expr);
1890169689Skan
1891169689Skan    case INDIRECT_REF:
1892169689Skan      inside_addr = false;
1893169689Skan      break;
1894169689Skan
1895169689Skan    default:
1896169689Skan      return orig_expr;
1897169689Skan    }
1898169689Skan
1899169689Skan  /* Default handling of expressions for that we want to recurse into
1900169689Skan     the first operand.  */
1901169689Skan  op0 = TREE_OPERAND (expr, 0);
1902169689Skan  op0 = strip_offset_1 (op0, inside_addr, false, &off0);
1903169689Skan  *offset += off0;
1904169689Skan
1905169689Skan  if (op0 == TREE_OPERAND (expr, 0)
1906169689Skan      && (!op1 || op1 == TREE_OPERAND (expr, 1)))
1907169689Skan    return orig_expr;
1908169689Skan
1909169689Skan  expr = copy_node (expr);
1910169689Skan  TREE_OPERAND (expr, 0) = op0;
1911169689Skan  if (op1)
1912169689Skan    TREE_OPERAND (expr, 1) = op1;
1913169689Skan
1914169689Skan  /* Inside address, we might strip the top level component references,
1915169689Skan     thus changing type of the expression.  Handling of ADDR_EXPR
1916169689Skan     will fix that.  */
1917169689Skan  expr = fold_convert (orig_type, expr);
1918169689Skan
1919169689Skan  return expr;
1920169689Skan}
1921169689Skan
1922169689Skan/* Strips constant offsets from EXPR and stores them to OFFSET.  */
1923169689Skan
1924169689Skanstatic tree
1925169689Skanstrip_offset (tree expr, unsigned HOST_WIDE_INT *offset)
1926169689Skan{
1927169689Skan  return strip_offset_1 (expr, false, false, offset);
1928169689Skan}
1929169689Skan
1930169689Skan/* Returns variant of TYPE that can be used as base for different uses.
1931169689Skan   We return unsigned type with the same precision, which avoids problems
1932169689Skan   with overflows.  */
1933169689Skan
1934169689Skanstatic tree
1935169689Skangeneric_type_for (tree type)
1936169689Skan{
1937169689Skan  if (POINTER_TYPE_P (type))
1938169689Skan    return unsigned_type_for (type);
1939169689Skan
1940169689Skan  if (TYPE_UNSIGNED (type))
1941169689Skan    return type;
1942169689Skan
1943169689Skan  return unsigned_type_for (type);
1944169689Skan}
1945169689Skan
1946169689Skan/* Records invariants in *EXPR_P.  Callback for walk_tree.  DATA contains
1947169689Skan   the bitmap to that we should store it.  */
1948169689Skan
1949169689Skanstatic struct ivopts_data *fd_ivopts_data;
1950169689Skanstatic tree
1951169689Skanfind_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
1952169689Skan{
1953169689Skan  bitmap *depends_on = data;
1954169689Skan  struct version_info *info;
1955169689Skan
1956169689Skan  if (TREE_CODE (*expr_p) != SSA_NAME)
1957169689Skan    return NULL_TREE;
1958169689Skan  info = name_info (fd_ivopts_data, *expr_p);
1959169689Skan
1960169689Skan  if (!info->inv_id || info->has_nonlin_use)
1961169689Skan    return NULL_TREE;
1962169689Skan
1963169689Skan  if (!*depends_on)
1964169689Skan    *depends_on = BITMAP_ALLOC (NULL);
1965169689Skan  bitmap_set_bit (*depends_on, info->inv_id);
1966169689Skan
1967169689Skan  return NULL_TREE;
1968169689Skan}
1969169689Skan
1970169689Skan/* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
1971169689Skan   position to POS.  If USE is not NULL, the candidate is set as related to
1972169689Skan   it.  If both BASE and STEP are NULL, we add a pseudocandidate for the
1973169689Skan   replacement of the final value of the iv by a direct computation.  */
1974169689Skan
1975169689Skanstatic struct iv_cand *
1976169689Skanadd_candidate_1 (struct ivopts_data *data,
1977169689Skan		 tree base, tree step, bool important, enum iv_position pos,
1978169689Skan		 struct iv_use *use, tree incremented_at)
1979169689Skan{
1980169689Skan  unsigned i;
1981169689Skan  struct iv_cand *cand = NULL;
1982169689Skan  tree type, orig_type;
1983169689Skan
1984169689Skan  if (base)
1985169689Skan    {
1986169689Skan      orig_type = TREE_TYPE (base);
1987169689Skan      type = generic_type_for (orig_type);
1988169689Skan      if (type != orig_type)
1989169689Skan	{
1990169689Skan	  base = fold_convert (type, base);
1991169689Skan	  if (step)
1992169689Skan	    step = fold_convert (type, step);
1993169689Skan	}
1994169689Skan    }
1995169689Skan
1996169689Skan  for (i = 0; i < n_iv_cands (data); i++)
1997169689Skan    {
1998169689Skan      cand = iv_cand (data, i);
1999169689Skan
2000169689Skan      if (cand->pos != pos)
2001169689Skan	continue;
2002169689Skan
2003169689Skan      if (cand->incremented_at != incremented_at)
2004169689Skan	continue;
2005169689Skan
2006169689Skan      if (!cand->iv)
2007169689Skan	{
2008169689Skan	  if (!base && !step)
2009169689Skan	    break;
2010169689Skan
2011169689Skan	  continue;
2012169689Skan	}
2013169689Skan
2014169689Skan      if (!base && !step)
2015169689Skan	continue;
2016169689Skan
2017169689Skan      if (!operand_equal_p (base, cand->iv->base, 0))
2018169689Skan	continue;
2019169689Skan
2020169689Skan      if (zero_p (cand->iv->step))
2021169689Skan	{
2022169689Skan	  if (zero_p (step))
2023169689Skan	    break;
2024169689Skan	}
2025169689Skan      else
2026169689Skan	{
2027169689Skan	  if (step && operand_equal_p (step, cand->iv->step, 0))
2028169689Skan	    break;
2029169689Skan	}
2030169689Skan    }
2031169689Skan
2032169689Skan  if (i == n_iv_cands (data))
2033169689Skan    {
2034169689Skan      cand = XCNEW (struct iv_cand);
2035169689Skan      cand->id = i;
2036169689Skan
2037169689Skan      if (!base && !step)
2038169689Skan	cand->iv = NULL;
2039169689Skan      else
2040169689Skan	cand->iv = alloc_iv (base, step);
2041169689Skan
2042169689Skan      cand->pos = pos;
2043169689Skan      if (pos != IP_ORIGINAL && cand->iv)
2044169689Skan	{
2045169689Skan	  cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp");
2046169689Skan	  cand->var_after = cand->var_before;
2047169689Skan	}
2048169689Skan      cand->important = important;
2049169689Skan      cand->incremented_at = incremented_at;
2050169689Skan      VEC_safe_push (iv_cand_p, heap, data->iv_candidates, cand);
2051169689Skan
2052169689Skan      if (step
2053169689Skan	  && TREE_CODE (step) != INTEGER_CST)
2054169689Skan	{
2055169689Skan	  fd_ivopts_data = data;
2056169689Skan	  walk_tree (&step, find_depends, &cand->depends_on, NULL);
2057169689Skan	}
2058169689Skan
2059169689Skan      if (dump_file && (dump_flags & TDF_DETAILS))
2060169689Skan	dump_cand (dump_file, cand);
2061169689Skan    }
2062169689Skan
2063169689Skan  if (important && !cand->important)
2064169689Skan    {
2065169689Skan      cand->important = true;
2066169689Skan      if (dump_file && (dump_flags & TDF_DETAILS))
2067169689Skan	fprintf (dump_file, "Candidate %d is important\n", cand->id);
2068169689Skan    }
2069169689Skan
2070169689Skan  if (use)
2071169689Skan    {
2072169689Skan      bitmap_set_bit (use->related_cands, i);
2073169689Skan      if (dump_file && (dump_flags & TDF_DETAILS))
2074169689Skan	fprintf (dump_file, "Candidate %d is related to use %d\n",
2075169689Skan		 cand->id, use->id);
2076169689Skan    }
2077169689Skan
2078169689Skan  return cand;
2079169689Skan}
2080169689Skan
2081169689Skan/* Returns true if incrementing the induction variable at the end of the LOOP
2082169689Skan   is allowed.
2083169689Skan
2084169689Skan   The purpose is to avoid splitting latch edge with a biv increment, thus
2085169689Skan   creating a jump, possibly confusing other optimization passes and leaving
2086169689Skan   less freedom to scheduler.  So we allow IP_END_POS only if IP_NORMAL_POS
2087169689Skan   is not available (so we do not have a better alternative), or if the latch
2088169689Skan   edge is already nonempty.  */
2089169689Skan
2090169689Skanstatic bool
2091169689Skanallow_ip_end_pos_p (struct loop *loop)
2092169689Skan{
2093169689Skan  if (!ip_normal_pos (loop))
2094169689Skan    return true;
2095169689Skan
2096169689Skan  if (!empty_block_p (ip_end_pos (loop)))
2097169689Skan    return true;
2098169689Skan
2099169689Skan  return false;
2100169689Skan}
2101169689Skan
2102169689Skan/* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
2103169689Skan   position to POS.  If USE is not NULL, the candidate is set as related to
2104169689Skan   it.  The candidate computation is scheduled on all available positions.  */
2105169689Skan
2106169689Skanstatic void
2107169689Skanadd_candidate (struct ivopts_data *data,
2108169689Skan	       tree base, tree step, bool important, struct iv_use *use)
2109169689Skan{
2110169689Skan  if (ip_normal_pos (data->current_loop))
2111169689Skan    add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL_TREE);
2112169689Skan  if (ip_end_pos (data->current_loop)
2113169689Skan      && allow_ip_end_pos_p (data->current_loop))
2114169689Skan    add_candidate_1 (data, base, step, important, IP_END, use, NULL_TREE);
2115169689Skan}
2116169689Skan
2117169689Skan/* Add a standard "0 + 1 * iteration" iv candidate for a
2118169689Skan   type with SIZE bits.  */
2119169689Skan
2120169689Skanstatic void
2121169689Skanadd_standard_iv_candidates_for_size (struct ivopts_data *data,
2122169689Skan				     unsigned int size)
2123169689Skan{
2124169689Skan  tree type = lang_hooks.types.type_for_size (size, true);
2125169689Skan  add_candidate (data, build_int_cst (type, 0), build_int_cst (type, 1),
2126169689Skan		 true, NULL);
2127169689Skan}
2128169689Skan
2129169689Skan/* Adds standard iv candidates.  */
2130169689Skan
2131169689Skanstatic void
2132169689Skanadd_standard_iv_candidates (struct ivopts_data *data)
2133169689Skan{
2134169689Skan  add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE);
2135169689Skan
2136169689Skan  /* The same for a double-integer type if it is still fast enough.  */
2137169689Skan  if (BITS_PER_WORD >= INT_TYPE_SIZE * 2)
2138169689Skan    add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE * 2);
2139169689Skan}
2140169689Skan
2141169689Skan
2142169689Skan/* Adds candidates bases on the old induction variable IV.  */
2143169689Skan
2144169689Skanstatic void
2145169689Skanadd_old_iv_candidates (struct ivopts_data *data, struct iv *iv)
2146169689Skan{
2147169689Skan  tree phi, def;
2148169689Skan  struct iv_cand *cand;
2149169689Skan
2150169689Skan  add_candidate (data, iv->base, iv->step, true, NULL);
2151169689Skan
2152169689Skan  /* The same, but with initial value zero.  */
2153169689Skan  add_candidate (data,
2154169689Skan		 build_int_cst (TREE_TYPE (iv->base), 0),
2155169689Skan		 iv->step, true, NULL);
2156169689Skan
2157169689Skan  phi = SSA_NAME_DEF_STMT (iv->ssa_name);
2158169689Skan  if (TREE_CODE (phi) == PHI_NODE)
2159169689Skan    {
2160169689Skan      /* Additionally record the possibility of leaving the original iv
2161169689Skan	 untouched.  */
2162169689Skan      def = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (data->current_loop));
2163169689Skan      cand = add_candidate_1 (data,
2164169689Skan			      iv->base, iv->step, true, IP_ORIGINAL, NULL,
2165169689Skan			      SSA_NAME_DEF_STMT (def));
2166169689Skan      cand->var_before = iv->ssa_name;
2167169689Skan      cand->var_after = def;
2168169689Skan    }
2169169689Skan}
2170169689Skan
2171169689Skan/* Adds candidates based on the old induction variables.  */
2172169689Skan
2173169689Skanstatic void
2174169689Skanadd_old_ivs_candidates (struct ivopts_data *data)
2175169689Skan{
2176169689Skan  unsigned i;
2177169689Skan  struct iv *iv;
2178169689Skan  bitmap_iterator bi;
2179169689Skan
2180169689Skan  EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
2181169689Skan    {
2182169689Skan      iv = ver_info (data, i)->iv;
2183169689Skan      if (iv && iv->biv_p && !zero_p (iv->step))
2184169689Skan	add_old_iv_candidates (data, iv);
2185169689Skan    }
2186169689Skan}
2187169689Skan
2188169689Skan/* Adds candidates based on the value of the induction variable IV and USE.  */
2189169689Skan
2190169689Skanstatic void
2191169689Skanadd_iv_value_candidates (struct ivopts_data *data,
2192169689Skan			 struct iv *iv, struct iv_use *use)
2193169689Skan{
2194169689Skan  unsigned HOST_WIDE_INT offset;
2195169689Skan  tree base;
2196169689Skan
2197169689Skan  add_candidate (data, iv->base, iv->step, false, use);
2198169689Skan
2199169689Skan  /* The same, but with initial value zero.  Make such variable important,
2200169689Skan     since it is generic enough so that possibly many uses may be based
2201169689Skan     on it.  */
2202169689Skan  add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
2203169689Skan		 iv->step, true, use);
2204169689Skan
2205169689Skan  /* Third, try removing the constant offset.  */
2206169689Skan  base = strip_offset (iv->base, &offset);
2207169689Skan  if (offset)
2208169689Skan    add_candidate (data, base, iv->step, false, use);
2209169689Skan}
2210169689Skan
2211169689Skan/* Adds candidates based on the uses.  */
2212169689Skan
2213169689Skanstatic void
2214169689Skanadd_derived_ivs_candidates (struct ivopts_data *data)
2215169689Skan{
2216169689Skan  unsigned i;
2217169689Skan
2218169689Skan  for (i = 0; i < n_iv_uses (data); i++)
2219169689Skan    {
2220169689Skan      struct iv_use *use = iv_use (data, i);
2221169689Skan
2222169689Skan      if (!use)
2223169689Skan	continue;
2224169689Skan
2225169689Skan      switch (use->type)
2226169689Skan	{
2227169689Skan	case USE_NONLINEAR_EXPR:
2228169689Skan	case USE_COMPARE:
2229169689Skan	case USE_ADDRESS:
2230169689Skan	  /* Just add the ivs based on the value of the iv used here.  */
2231169689Skan	  add_iv_value_candidates (data, use->iv, use);
2232169689Skan	  break;
2233169689Skan
2234169689Skan	default:
2235169689Skan	  gcc_unreachable ();
2236169689Skan	}
2237169689Skan    }
2238169689Skan}
2239169689Skan
2240169689Skan/* Record important candidates and add them to related_cands bitmaps
2241169689Skan   if needed.  */
2242169689Skan
2243169689Skanstatic void
2244169689Skanrecord_important_candidates (struct ivopts_data *data)
2245169689Skan{
2246169689Skan  unsigned i;
2247169689Skan  struct iv_use *use;
2248169689Skan
2249169689Skan  for (i = 0; i < n_iv_cands (data); i++)
2250169689Skan    {
2251169689Skan      struct iv_cand *cand = iv_cand (data, i);
2252169689Skan
2253169689Skan      if (cand->important)
2254169689Skan	bitmap_set_bit (data->important_candidates, i);
2255169689Skan    }
2256169689Skan
2257169689Skan  data->consider_all_candidates = (n_iv_cands (data)
2258169689Skan				   <= CONSIDER_ALL_CANDIDATES_BOUND);
2259169689Skan
2260169689Skan  if (data->consider_all_candidates)
2261169689Skan    {
2262169689Skan      /* We will not need "related_cands" bitmaps in this case,
2263169689Skan	 so release them to decrease peak memory consumption.  */
2264169689Skan      for (i = 0; i < n_iv_uses (data); i++)
2265169689Skan	{
2266169689Skan	  use = iv_use (data, i);
2267169689Skan	  BITMAP_FREE (use->related_cands);
2268169689Skan	}
2269169689Skan    }
2270169689Skan  else
2271169689Skan    {
2272169689Skan      /* Add important candidates to the related_cands bitmaps.  */
2273169689Skan      for (i = 0; i < n_iv_uses (data); i++)
2274169689Skan	bitmap_ior_into (iv_use (data, i)->related_cands,
2275169689Skan			 data->important_candidates);
2276169689Skan    }
2277169689Skan}
2278169689Skan
2279169689Skan/* Finds the candidates for the induction variables.  */
2280169689Skan
2281169689Skanstatic void
2282169689Skanfind_iv_candidates (struct ivopts_data *data)
2283169689Skan{
2284169689Skan  /* Add commonly used ivs.  */
2285169689Skan  add_standard_iv_candidates (data);
2286169689Skan
2287169689Skan  /* Add old induction variables.  */
2288169689Skan  add_old_ivs_candidates (data);
2289169689Skan
2290169689Skan  /* Add induction variables derived from uses.  */
2291169689Skan  add_derived_ivs_candidates (data);
2292169689Skan
2293169689Skan  /* Record the important candidates.  */
2294169689Skan  record_important_candidates (data);
2295169689Skan}
2296169689Skan
2297169689Skan/* Allocates the data structure mapping the (use, candidate) pairs to costs.
2298169689Skan   If consider_all_candidates is true, we use a two-dimensional array, otherwise
2299169689Skan   we allocate a simple list to every use.  */
2300169689Skan
2301169689Skanstatic void
2302169689Skanalloc_use_cost_map (struct ivopts_data *data)
2303169689Skan{
2304169689Skan  unsigned i, size, s, j;
2305169689Skan
2306169689Skan  for (i = 0; i < n_iv_uses (data); i++)
2307169689Skan    {
2308169689Skan      struct iv_use *use = iv_use (data, i);
2309169689Skan      bitmap_iterator bi;
2310169689Skan
2311169689Skan      if (data->consider_all_candidates)
2312169689Skan	size = n_iv_cands (data);
2313169689Skan      else
2314169689Skan	{
2315169689Skan	  s = 0;
2316169689Skan	  EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi)
2317169689Skan	    {
2318169689Skan	      s++;
2319169689Skan	    }
2320169689Skan
2321169689Skan	  /* Round up to the power of two, so that moduling by it is fast.  */
2322169689Skan	  for (size = 1; size < s; size <<= 1)
2323169689Skan	    continue;
2324169689Skan	}
2325169689Skan
2326169689Skan      use->n_map_members = size;
2327169689Skan      use->cost_map = XCNEWVEC (struct cost_pair, size);
2328169689Skan    }
2329169689Skan}
2330169689Skan
2331169689Skan/* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
2332169689Skan   on invariants DEPENDS_ON and that the value used in expressing it
2333169689Skan   is VALUE.*/
2334169689Skan
2335169689Skanstatic void
2336169689Skanset_use_iv_cost (struct ivopts_data *data,
2337169689Skan		 struct iv_use *use, struct iv_cand *cand, unsigned cost,
2338169689Skan		 bitmap depends_on, tree value)
2339169689Skan{
2340169689Skan  unsigned i, s;
2341169689Skan
2342169689Skan  if (cost == INFTY)
2343169689Skan    {
2344169689Skan      BITMAP_FREE (depends_on);
2345169689Skan      return;
2346169689Skan    }
2347169689Skan
2348169689Skan  if (data->consider_all_candidates)
2349169689Skan    {
2350169689Skan      use->cost_map[cand->id].cand = cand;
2351169689Skan      use->cost_map[cand->id].cost = cost;
2352169689Skan      use->cost_map[cand->id].depends_on = depends_on;
2353169689Skan      use->cost_map[cand->id].value = value;
2354169689Skan      return;
2355169689Skan    }
2356169689Skan
2357169689Skan  /* n_map_members is a power of two, so this computes modulo.  */
2358169689Skan  s = cand->id & (use->n_map_members - 1);
2359169689Skan  for (i = s; i < use->n_map_members; i++)
2360169689Skan    if (!use->cost_map[i].cand)
2361169689Skan      goto found;
2362169689Skan  for (i = 0; i < s; i++)
2363169689Skan    if (!use->cost_map[i].cand)
2364169689Skan      goto found;
2365169689Skan
2366169689Skan  gcc_unreachable ();
2367169689Skan
2368169689Skanfound:
2369169689Skan  use->cost_map[i].cand = cand;
2370169689Skan  use->cost_map[i].cost = cost;
2371169689Skan  use->cost_map[i].depends_on = depends_on;
2372169689Skan  use->cost_map[i].value = value;
2373169689Skan}
2374169689Skan
2375169689Skan/* Gets cost of (USE, CANDIDATE) pair.  */
2376169689Skan
2377169689Skanstatic struct cost_pair *
2378169689Skanget_use_iv_cost (struct ivopts_data *data, struct iv_use *use,
2379169689Skan		 struct iv_cand *cand)
2380169689Skan{
2381169689Skan  unsigned i, s;
2382169689Skan  struct cost_pair *ret;
2383169689Skan
2384169689Skan  if (!cand)
2385169689Skan    return NULL;
2386169689Skan
2387169689Skan  if (data->consider_all_candidates)
2388169689Skan    {
2389169689Skan      ret = use->cost_map + cand->id;
2390169689Skan      if (!ret->cand)
2391169689Skan	return NULL;
2392169689Skan
2393169689Skan      return ret;
2394169689Skan    }
2395169689Skan
2396169689Skan  /* n_map_members is a power of two, so this computes modulo.  */
2397169689Skan  s = cand->id & (use->n_map_members - 1);
2398169689Skan  for (i = s; i < use->n_map_members; i++)
2399169689Skan    if (use->cost_map[i].cand == cand)
2400169689Skan      return use->cost_map + i;
2401169689Skan
2402169689Skan  for (i = 0; i < s; i++)
2403169689Skan    if (use->cost_map[i].cand == cand)
2404169689Skan      return use->cost_map + i;
2405169689Skan
2406169689Skan  return NULL;
2407169689Skan}
2408169689Skan
2409169689Skan/* Returns estimate on cost of computing SEQ.  */
2410169689Skan
2411169689Skanstatic unsigned
2412169689Skanseq_cost (rtx seq)
2413169689Skan{
2414169689Skan  unsigned cost = 0;
2415169689Skan  rtx set;
2416169689Skan
2417169689Skan  for (; seq; seq = NEXT_INSN (seq))
2418169689Skan    {
2419169689Skan      set = single_set (seq);
2420169689Skan      if (set)
2421169689Skan	cost += rtx_cost (set, SET);
2422169689Skan      else
2423169689Skan	cost++;
2424169689Skan    }
2425169689Skan
2426169689Skan  return cost;
2427169689Skan}
2428169689Skan
2429169689Skan/* Produce DECL_RTL for object obj so it looks like it is stored in memory.  */
2430169689Skanstatic rtx
2431169689Skanproduce_memory_decl_rtl (tree obj, int *regno)
2432169689Skan{
2433169689Skan  rtx x;
2434169689Skan
2435169689Skan  gcc_assert (obj);
2436169689Skan  if (TREE_STATIC (obj) || DECL_EXTERNAL (obj))
2437169689Skan    {
2438169689Skan      const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj));
2439169689Skan      x = gen_rtx_SYMBOL_REF (Pmode, name);
2440169689Skan    }
2441169689Skan  else
2442169689Skan    x = gen_raw_REG (Pmode, (*regno)++);
2443169689Skan
2444169689Skan  return gen_rtx_MEM (DECL_MODE (obj), x);
2445169689Skan}
2446169689Skan
2447169689Skan/* Prepares decl_rtl for variables referred in *EXPR_P.  Callback for
2448169689Skan   walk_tree.  DATA contains the actual fake register number.  */
2449169689Skan
2450169689Skanstatic tree
2451169689Skanprepare_decl_rtl (tree *expr_p, int *ws, void *data)
2452169689Skan{
2453169689Skan  tree obj = NULL_TREE;
2454169689Skan  rtx x = NULL_RTX;
2455169689Skan  int *regno = data;
2456169689Skan
2457169689Skan  switch (TREE_CODE (*expr_p))
2458169689Skan    {
2459169689Skan    case ADDR_EXPR:
2460169689Skan      for (expr_p = &TREE_OPERAND (*expr_p, 0);
2461169689Skan	   handled_component_p (*expr_p);
2462169689Skan	   expr_p = &TREE_OPERAND (*expr_p, 0))
2463169689Skan	continue;
2464169689Skan      obj = *expr_p;
2465169689Skan      if (DECL_P (obj) && !DECL_RTL_SET_P (obj))
2466169689Skan        x = produce_memory_decl_rtl (obj, regno);
2467169689Skan      break;
2468169689Skan
2469169689Skan    case SSA_NAME:
2470169689Skan      *ws = 0;
2471169689Skan      obj = SSA_NAME_VAR (*expr_p);
2472169689Skan      if (!DECL_RTL_SET_P (obj))
2473169689Skan	x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
2474169689Skan      break;
2475169689Skan
2476169689Skan    case VAR_DECL:
2477169689Skan    case PARM_DECL:
2478169689Skan    case RESULT_DECL:
2479169689Skan      *ws = 0;
2480169689Skan      obj = *expr_p;
2481169689Skan
2482169689Skan      if (DECL_RTL_SET_P (obj))
2483169689Skan	break;
2484169689Skan
2485169689Skan      if (DECL_MODE (obj) == BLKmode)
2486169689Skan	x = produce_memory_decl_rtl (obj, regno);
2487169689Skan      else
2488169689Skan	x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
2489169689Skan
2490169689Skan      break;
2491169689Skan
2492169689Skan    default:
2493169689Skan      break;
2494169689Skan    }
2495169689Skan
2496169689Skan  if (x)
2497169689Skan    {
2498169689Skan      VEC_safe_push (tree, heap, decl_rtl_to_reset, obj);
2499169689Skan      SET_DECL_RTL (obj, x);
2500169689Skan    }
2501169689Skan
2502169689Skan  return NULL_TREE;
2503169689Skan}
2504169689Skan
2505169689Skan/* Determines cost of the computation of EXPR.  */
2506169689Skan
2507169689Skanstatic unsigned
2508169689Skancomputation_cost (tree expr)
2509169689Skan{
2510169689Skan  rtx seq, rslt;
2511169689Skan  tree type = TREE_TYPE (expr);
2512169689Skan  unsigned cost;
2513169689Skan  /* Avoid using hard regs in ways which may be unsupported.  */
2514169689Skan  int regno = LAST_VIRTUAL_REGISTER + 1;
2515169689Skan
2516169689Skan  walk_tree (&expr, prepare_decl_rtl, &regno, NULL);
2517169689Skan  start_sequence ();
2518169689Skan  rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL);
2519169689Skan  seq = get_insns ();
2520169689Skan  end_sequence ();
2521169689Skan
2522169689Skan  cost = seq_cost (seq);
2523169689Skan  if (MEM_P (rslt))
2524169689Skan    cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type));
2525169689Skan
2526169689Skan  return cost;
2527169689Skan}
2528169689Skan
2529169689Skan/* Returns variable containing the value of candidate CAND at statement AT.  */
2530169689Skan
2531169689Skanstatic tree
2532169689Skanvar_at_stmt (struct loop *loop, struct iv_cand *cand, tree stmt)
2533169689Skan{
2534169689Skan  if (stmt_after_increment (loop, cand, stmt))
2535169689Skan    return cand->var_after;
2536169689Skan  else
2537169689Skan    return cand->var_before;
2538169689Skan}
2539169689Skan
2540169689Skan/* Return the most significant (sign) bit of T.  Similar to tree_int_cst_msb,
2541169689Skan   but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE.  */
2542169689Skan
2543169689Skanint
2544169689Skantree_int_cst_sign_bit (tree t)
2545169689Skan{
2546169689Skan  unsigned bitno = TYPE_PRECISION (TREE_TYPE (t)) - 1;
2547169689Skan  unsigned HOST_WIDE_INT w;
2548169689Skan
2549169689Skan  if (bitno < HOST_BITS_PER_WIDE_INT)
2550169689Skan    w = TREE_INT_CST_LOW (t);
2551169689Skan  else
2552169689Skan    {
2553169689Skan      w = TREE_INT_CST_HIGH (t);
2554169689Skan      bitno -= HOST_BITS_PER_WIDE_INT;
2555169689Skan    }
2556169689Skan
2557169689Skan  return (w >> bitno) & 1;
2558169689Skan}
2559169689Skan
2560169689Skan/* If we can prove that TOP = cst * BOT for some constant cst,
2561169689Skan   store cst to MUL and return true.  Otherwise return false.
2562169689Skan   The returned value is always sign-extended, regardless of the
2563169689Skan   signedness of TOP and BOT.  */
2564169689Skan
2565169689Skanstatic bool
2566169689Skanconstant_multiple_of (tree top, tree bot, double_int *mul)
2567169689Skan{
2568169689Skan  tree mby;
2569169689Skan  enum tree_code code;
2570169689Skan  double_int res, p0, p1;
2571169689Skan  unsigned precision = TYPE_PRECISION (TREE_TYPE (top));
2572169689Skan
2573169689Skan  STRIP_NOPS (top);
2574169689Skan  STRIP_NOPS (bot);
2575169689Skan
2576169689Skan  if (operand_equal_p (top, bot, 0))
2577169689Skan    {
2578169689Skan      *mul = double_int_one;
2579169689Skan      return true;
2580169689Skan    }
2581169689Skan
2582169689Skan  code = TREE_CODE (top);
2583169689Skan  switch (code)
2584169689Skan    {
2585169689Skan    case MULT_EXPR:
2586169689Skan      mby = TREE_OPERAND (top, 1);
2587169689Skan      if (TREE_CODE (mby) != INTEGER_CST)
2588169689Skan	return false;
2589169689Skan
2590169689Skan      if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &res))
2591169689Skan	return false;
2592169689Skan
2593169689Skan      *mul = double_int_sext (double_int_mul (res, tree_to_double_int (mby)),
2594169689Skan			      precision);
2595169689Skan      return true;
2596169689Skan
2597169689Skan    case PLUS_EXPR:
2598169689Skan    case MINUS_EXPR:
2599169689Skan      if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &p0)
2600169689Skan	  || !constant_multiple_of (TREE_OPERAND (top, 1), bot, &p1))
2601169689Skan	return false;
2602169689Skan
2603169689Skan      if (code == MINUS_EXPR)
2604169689Skan	p1 = double_int_neg (p1);
2605169689Skan      *mul = double_int_sext (double_int_add (p0, p1), precision);
2606169689Skan      return true;
2607169689Skan
2608169689Skan    case INTEGER_CST:
2609169689Skan      if (TREE_CODE (bot) != INTEGER_CST)
2610169689Skan	return false;
2611169689Skan
2612169689Skan      p0 = double_int_sext (tree_to_double_int (bot), precision);
2613169689Skan      p1 = double_int_sext (tree_to_double_int (top), precision);
2614169689Skan      if (double_int_zero_p (p1))
2615169689Skan	return false;
2616169689Skan      *mul = double_int_sext (double_int_sdivmod (p0, p1, FLOOR_DIV_EXPR, &res),
2617169689Skan			      precision);
2618169689Skan      return double_int_zero_p (res);
2619169689Skan
2620169689Skan    default:
2621169689Skan      return false;
2622169689Skan    }
2623169689Skan}
2624169689Skan
2625169689Skan/* Sets COMB to CST.  */
2626169689Skan
2627169689Skanstatic void
2628169689Skanaff_combination_const (struct affine_tree_combination *comb, tree type,
2629169689Skan		       unsigned HOST_WIDE_INT cst)
2630169689Skan{
2631169689Skan  unsigned prec = TYPE_PRECISION (type);
2632169689Skan
2633169689Skan  comb->type = type;
2634169689Skan  comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
2635169689Skan
2636169689Skan  comb->n = 0;
2637169689Skan  comb->rest = NULL_TREE;
2638169689Skan  comb->offset = cst & comb->mask;
2639169689Skan}
2640169689Skan
2641169689Skan/* Sets COMB to single element ELT.  */
2642169689Skan
2643169689Skanstatic void
2644169689Skanaff_combination_elt (struct affine_tree_combination *comb, tree type, tree elt)
2645169689Skan{
2646169689Skan  unsigned prec = TYPE_PRECISION (type);
2647169689Skan
2648169689Skan  comb->type = type;
2649169689Skan  comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
2650169689Skan
2651169689Skan  comb->n = 1;
2652169689Skan  comb->elts[0] = elt;
2653169689Skan  comb->coefs[0] = 1;
2654169689Skan  comb->rest = NULL_TREE;
2655169689Skan  comb->offset = 0;
2656169689Skan}
2657169689Skan
2658169689Skan/* Scales COMB by SCALE.  */
2659169689Skan
2660169689Skanstatic void
2661169689Skanaff_combination_scale (struct affine_tree_combination *comb,
2662169689Skan		       unsigned HOST_WIDE_INT scale)
2663169689Skan{
2664169689Skan  unsigned i, j;
2665169689Skan
2666169689Skan  if (scale == 1)
2667169689Skan    return;
2668169689Skan
2669169689Skan  if (scale == 0)
2670169689Skan    {
2671169689Skan      aff_combination_const (comb, comb->type, 0);
2672169689Skan      return;
2673169689Skan    }
2674169689Skan
2675169689Skan  comb->offset = (scale * comb->offset) & comb->mask;
2676169689Skan  for (i = 0, j = 0; i < comb->n; i++)
2677169689Skan    {
2678169689Skan      comb->coefs[j] = (scale * comb->coefs[i]) & comb->mask;
2679169689Skan      comb->elts[j] = comb->elts[i];
2680169689Skan      if (comb->coefs[j] != 0)
2681169689Skan	j++;
2682169689Skan    }
2683169689Skan  comb->n = j;
2684169689Skan
2685169689Skan  if (comb->rest)
2686169689Skan    {
2687169689Skan      if (comb->n < MAX_AFF_ELTS)
2688169689Skan	{
2689169689Skan	  comb->coefs[comb->n] = scale;
2690169689Skan	  comb->elts[comb->n] = comb->rest;
2691169689Skan	  comb->rest = NULL_TREE;
2692169689Skan	  comb->n++;
2693169689Skan	}
2694169689Skan      else
2695169689Skan	comb->rest = fold_build2 (MULT_EXPR, comb->type, comb->rest,
2696169689Skan				  build_int_cst_type (comb->type, scale));
2697169689Skan    }
2698169689Skan}
2699169689Skan
2700169689Skan/* Adds ELT * SCALE to COMB.  */
2701169689Skan
2702169689Skanstatic void
2703169689Skanaff_combination_add_elt (struct affine_tree_combination *comb, tree elt,
2704169689Skan			 unsigned HOST_WIDE_INT scale)
2705169689Skan{
2706169689Skan  unsigned i;
2707169689Skan
2708169689Skan  if (scale == 0)
2709169689Skan    return;
2710169689Skan
2711169689Skan  for (i = 0; i < comb->n; i++)
2712169689Skan    if (operand_equal_p (comb->elts[i], elt, 0))
2713169689Skan      {
2714169689Skan	comb->coefs[i] = (comb->coefs[i] + scale) & comb->mask;
2715169689Skan	if (comb->coefs[i])
2716169689Skan	  return;
2717169689Skan
2718169689Skan	comb->n--;
2719169689Skan	comb->coefs[i] = comb->coefs[comb->n];
2720169689Skan	comb->elts[i] = comb->elts[comb->n];
2721169689Skan
2722169689Skan	if (comb->rest)
2723169689Skan	  {
2724169689Skan	    gcc_assert (comb->n == MAX_AFF_ELTS - 1);
2725169689Skan	    comb->coefs[comb->n] = 1;
2726169689Skan	    comb->elts[comb->n] = comb->rest;
2727169689Skan	    comb->rest = NULL_TREE;
2728169689Skan	    comb->n++;
2729169689Skan	  }
2730169689Skan	return;
2731169689Skan      }
2732169689Skan  if (comb->n < MAX_AFF_ELTS)
2733169689Skan    {
2734169689Skan      comb->coefs[comb->n] = scale;
2735169689Skan      comb->elts[comb->n] = elt;
2736169689Skan      comb->n++;
2737169689Skan      return;
2738169689Skan    }
2739169689Skan
2740169689Skan  if (scale == 1)
2741169689Skan    elt = fold_convert (comb->type, elt);
2742169689Skan  else
2743169689Skan    elt = fold_build2 (MULT_EXPR, comb->type,
2744169689Skan		       fold_convert (comb->type, elt),
2745169689Skan		       build_int_cst_type (comb->type, scale));
2746169689Skan
2747169689Skan  if (comb->rest)
2748169689Skan    comb->rest = fold_build2 (PLUS_EXPR, comb->type, comb->rest, elt);
2749169689Skan  else
2750169689Skan    comb->rest = elt;
2751169689Skan}
2752169689Skan
2753169689Skan/* Adds COMB2 to COMB1.  */
2754169689Skan
2755169689Skanstatic void
2756169689Skanaff_combination_add (struct affine_tree_combination *comb1,
2757169689Skan		     struct affine_tree_combination *comb2)
2758169689Skan{
2759169689Skan  unsigned i;
2760169689Skan
2761169689Skan  comb1->offset = (comb1->offset + comb2->offset) & comb1->mask;
2762169689Skan  for (i = 0; i < comb2->n; i++)
2763169689Skan    aff_combination_add_elt (comb1, comb2->elts[i], comb2->coefs[i]);
2764169689Skan  if (comb2->rest)
2765169689Skan    aff_combination_add_elt (comb1, comb2->rest, 1);
2766169689Skan}
2767169689Skan
2768169689Skan/* Convert COMB to TYPE.  */
2769169689Skan
2770169689Skanstatic void
2771169689Skanaff_combination_convert (tree type, struct affine_tree_combination *comb)
2772169689Skan{
2773169689Skan  unsigned prec = TYPE_PRECISION (type);
2774169689Skan  unsigned i;
2775169689Skan
2776169689Skan  /* If the precision of both types is the same, it suffices to change the type
2777169689Skan     of the whole combination -- the elements are allowed to have another type
2778169689Skan     equivalent wrto STRIP_NOPS.  */
2779169689Skan  if (prec == TYPE_PRECISION (comb->type))
2780169689Skan    {
2781169689Skan      comb->type = type;
2782169689Skan      return;
2783169689Skan    }
2784169689Skan
2785169689Skan  comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
2786169689Skan  comb->offset = comb->offset & comb->mask;
2787169689Skan
2788169689Skan  /* The type of the elements can be different from comb->type only as
2789169689Skan     much as what STRIP_NOPS would remove.  We can just directly cast
2790169689Skan     to TYPE.  */
2791169689Skan  for (i = 0; i < comb->n; i++)
2792169689Skan    comb->elts[i] = fold_convert (type, comb->elts[i]);
2793169689Skan  if (comb->rest)
2794169689Skan    comb->rest = fold_convert (type, comb->rest);
2795169689Skan
2796169689Skan  comb->type = type;
2797169689Skan}
2798169689Skan
2799169689Skan/* Splits EXPR into an affine combination of parts.  */
2800169689Skan
2801169689Skanstatic void
2802169689Skantree_to_aff_combination (tree expr, tree type,
2803169689Skan			 struct affine_tree_combination *comb)
2804169689Skan{
2805169689Skan  struct affine_tree_combination tmp;
2806169689Skan  enum tree_code code;
2807169689Skan  tree cst, core, toffset;
2808169689Skan  HOST_WIDE_INT bitpos, bitsize;
2809169689Skan  enum machine_mode mode;
2810169689Skan  int unsignedp, volatilep;
2811169689Skan
2812169689Skan  STRIP_NOPS (expr);
2813169689Skan
2814169689Skan  code = TREE_CODE (expr);
2815169689Skan  switch (code)
2816169689Skan    {
2817169689Skan    case INTEGER_CST:
2818169689Skan      aff_combination_const (comb, type, int_cst_value (expr));
2819169689Skan      return;
2820169689Skan
2821169689Skan    case PLUS_EXPR:
2822169689Skan    case MINUS_EXPR:
2823169689Skan      tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
2824169689Skan      tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp);
2825169689Skan      if (code == MINUS_EXPR)
2826169689Skan	aff_combination_scale (&tmp, -1);
2827169689Skan      aff_combination_add (comb, &tmp);
2828169689Skan      return;
2829169689Skan
2830169689Skan    case MULT_EXPR:
2831169689Skan      cst = TREE_OPERAND (expr, 1);
2832169689Skan      if (TREE_CODE (cst) != INTEGER_CST)
2833169689Skan	break;
2834169689Skan      tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
2835169689Skan      aff_combination_scale (comb, int_cst_value (cst));
2836169689Skan      return;
2837169689Skan
2838169689Skan    case NEGATE_EXPR:
2839169689Skan      tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
2840169689Skan      aff_combination_scale (comb, -1);
2841169689Skan      return;
2842169689Skan
2843169689Skan    case ADDR_EXPR:
2844169689Skan      core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
2845169689Skan				  &toffset, &mode, &unsignedp, &volatilep,
2846169689Skan				  false);
2847169689Skan      if (bitpos % BITS_PER_UNIT != 0)
2848169689Skan	break;
2849169689Skan      aff_combination_const (comb, type, bitpos / BITS_PER_UNIT);
2850169689Skan      core = build_fold_addr_expr (core);
2851169689Skan      if (TREE_CODE (core) == ADDR_EXPR)
2852169689Skan	aff_combination_add_elt (comb, core, 1);
2853169689Skan      else
2854169689Skan	{
2855169689Skan	  tree_to_aff_combination (core, type, &tmp);
2856169689Skan	  aff_combination_add (comb, &tmp);
2857169689Skan	}
2858169689Skan      if (toffset)
2859169689Skan	{
2860169689Skan	  tree_to_aff_combination (toffset, type, &tmp);
2861169689Skan	  aff_combination_add (comb, &tmp);
2862169689Skan	}
2863169689Skan      return;
2864169689Skan
2865169689Skan    default:
2866169689Skan      break;
2867169689Skan    }
2868169689Skan
2869169689Skan  aff_combination_elt (comb, type, expr);
2870169689Skan}
2871169689Skan
2872169689Skan/* Creates EXPR + ELT * SCALE in TYPE.  MASK is the mask for width of TYPE.  */
2873169689Skan
2874169689Skanstatic tree
2875169689Skanadd_elt_to_tree (tree expr, tree type, tree elt, unsigned HOST_WIDE_INT scale,
2876169689Skan		 unsigned HOST_WIDE_INT mask)
2877169689Skan{
2878169689Skan  enum tree_code code;
2879169689Skan
2880169689Skan  scale &= mask;
2881169689Skan  elt = fold_convert (type, elt);
2882169689Skan
2883169689Skan  if (scale == 1)
2884169689Skan    {
2885169689Skan      if (!expr)
2886169689Skan	return elt;
2887169689Skan
2888169689Skan      return fold_build2 (PLUS_EXPR, type, expr, elt);
2889169689Skan    }
2890169689Skan
2891169689Skan  if (scale == mask)
2892169689Skan    {
2893169689Skan      if (!expr)
2894169689Skan	return fold_build1 (NEGATE_EXPR, type, elt);
2895169689Skan
2896169689Skan      return fold_build2 (MINUS_EXPR, type, expr, elt);
2897169689Skan    }
2898169689Skan
2899169689Skan  if (!expr)
2900169689Skan    return fold_build2 (MULT_EXPR, type, elt,
2901169689Skan			build_int_cst_type (type, scale));
2902169689Skan
2903169689Skan  if ((scale | (mask >> 1)) == mask)
2904169689Skan    {
2905169689Skan      /* Scale is negative.  */
2906169689Skan      code = MINUS_EXPR;
2907169689Skan      scale = (-scale) & mask;
2908169689Skan    }
2909169689Skan  else
2910169689Skan    code = PLUS_EXPR;
2911169689Skan
2912169689Skan  elt = fold_build2 (MULT_EXPR, type, elt,
2913169689Skan		     build_int_cst_type (type, scale));
2914169689Skan  return fold_build2 (code, type, expr, elt);
2915169689Skan}
2916169689Skan
2917169689Skan/* Copies the tree elements of COMB to ensure that they are not shared.  */
2918169689Skan
2919169689Skanstatic void
2920169689Skanunshare_aff_combination (struct affine_tree_combination *comb)
2921169689Skan{
2922169689Skan  unsigned i;
2923169689Skan
2924169689Skan  for (i = 0; i < comb->n; i++)
2925169689Skan    comb->elts[i] = unshare_expr (comb->elts[i]);
2926169689Skan  if (comb->rest)
2927169689Skan    comb->rest = unshare_expr (comb->rest);
2928169689Skan}
2929169689Skan
2930169689Skan/* Makes tree from the affine combination COMB.  */
2931169689Skan
2932169689Skanstatic tree
2933169689Skanaff_combination_to_tree (struct affine_tree_combination *comb)
2934169689Skan{
2935169689Skan  tree type = comb->type;
2936169689Skan  tree expr = comb->rest;
2937169689Skan  unsigned i;
2938169689Skan  unsigned HOST_WIDE_INT off, sgn;
2939169689Skan
2940169689Skan  if (comb->n == 0 && comb->offset == 0)
2941169689Skan    {
2942169689Skan      if (expr)
2943169689Skan	{
2944169689Skan	  /* Handle the special case produced by get_computation_aff when
2945169689Skan	     the type does not fit in HOST_WIDE_INT.  */
2946169689Skan	  return fold_convert (type, expr);
2947169689Skan	}
2948169689Skan      else
2949169689Skan	return build_int_cst (type, 0);
2950169689Skan    }
2951169689Skan
2952169689Skan  gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
2953169689Skan
2954169689Skan  for (i = 0; i < comb->n; i++)
2955169689Skan    expr = add_elt_to_tree (expr, type, comb->elts[i], comb->coefs[i],
2956169689Skan			    comb->mask);
2957169689Skan
2958169689Skan  if ((comb->offset | (comb->mask >> 1)) == comb->mask)
2959169689Skan    {
2960169689Skan      /* Offset is negative.  */
2961169689Skan      off = (-comb->offset) & comb->mask;
2962169689Skan      sgn = comb->mask;
2963169689Skan    }
2964169689Skan  else
2965169689Skan    {
2966169689Skan      off = comb->offset;
2967169689Skan      sgn = 1;
2968169689Skan    }
2969169689Skan  return add_elt_to_tree (expr, type, build_int_cst_type (type, off), sgn,
2970169689Skan			  comb->mask);
2971169689Skan}
2972169689Skan
2973169689Skan/* Folds EXPR using the affine expressions framework.  */
2974169689Skan
2975169689Skanstatic tree
2976169689Skanfold_affine_expr (tree expr)
2977169689Skan{
2978169689Skan  tree type = TREE_TYPE (expr);
2979169689Skan  struct affine_tree_combination comb;
2980169689Skan
2981169689Skan  if (TYPE_PRECISION (type) > HOST_BITS_PER_WIDE_INT)
2982169689Skan    return expr;
2983169689Skan
2984169689Skan  tree_to_aff_combination (expr, type, &comb);
2985169689Skan  return aff_combination_to_tree (&comb);
2986169689Skan}
2987169689Skan
2988169689Skan/* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
2989169689Skan   same precision that is at least as wide as the precision of TYPE, stores
2990169689Skan   BA to A and BB to B, and returns the type of BA.  Otherwise, returns the
2991169689Skan   type of A and B.  */
2992169689Skan
2993169689Skanstatic tree
2994169689Skandetermine_common_wider_type (tree *a, tree *b)
2995169689Skan{
2996169689Skan  tree wider_type = NULL;
2997169689Skan  tree suba, subb;
2998169689Skan  tree atype = TREE_TYPE (*a);
2999169689Skan
3000169689Skan  if ((TREE_CODE (*a) == NOP_EXPR
3001169689Skan       || TREE_CODE (*a) == CONVERT_EXPR))
3002169689Skan    {
3003169689Skan      suba = TREE_OPERAND (*a, 0);
3004169689Skan      wider_type = TREE_TYPE (suba);
3005169689Skan      if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (atype))
3006169689Skan	return atype;
3007169689Skan    }
3008169689Skan  else
3009169689Skan    return atype;
3010169689Skan
3011169689Skan  if ((TREE_CODE (*b) == NOP_EXPR
3012169689Skan       || TREE_CODE (*b) == CONVERT_EXPR))
3013169689Skan    {
3014169689Skan      subb = TREE_OPERAND (*b, 0);
3015169689Skan      if (TYPE_PRECISION (wider_type) != TYPE_PRECISION (TREE_TYPE (subb)))
3016169689Skan	return atype;
3017169689Skan    }
3018169689Skan  else
3019169689Skan    return atype;
3020169689Skan
3021169689Skan  *a = suba;
3022169689Skan  *b = subb;
3023169689Skan  return wider_type;
3024169689Skan}
3025169689Skan
3026169689Skan/* Determines the expression by that USE is expressed from induction variable
3027169689Skan   CAND at statement AT in LOOP.  The expression is stored in a decomposed
3028169689Skan   form into AFF.  Returns false if USE cannot be expressed using CAND.  */
3029169689Skan
3030169689Skanstatic bool
3031169689Skanget_computation_aff (struct loop *loop,
3032169689Skan		     struct iv_use *use, struct iv_cand *cand, tree at,
3033169689Skan		     struct affine_tree_combination *aff)
3034169689Skan{
3035169689Skan  tree ubase = use->iv->base;
3036169689Skan  tree ustep = use->iv->step;
3037169689Skan  tree cbase = cand->iv->base;
3038169689Skan  tree cstep = cand->iv->step;
3039169689Skan  tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
3040169689Skan  tree common_type;
3041169689Skan  tree uutype;
3042169689Skan  tree expr, delta;
3043169689Skan  tree ratio;
3044169689Skan  unsigned HOST_WIDE_INT ustepi, cstepi;
3045169689Skan  HOST_WIDE_INT ratioi;
3046169689Skan  struct affine_tree_combination cbase_aff, expr_aff;
3047169689Skan  tree cstep_orig = cstep, ustep_orig = ustep;
3048169689Skan  double_int rat;
3049169689Skan
3050169689Skan  if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
3051169689Skan    {
3052169689Skan      /* We do not have a precision to express the values of use.  */
3053169689Skan      return false;
3054169689Skan    }
3055169689Skan
3056169689Skan  expr = var_at_stmt (loop, cand, at);
3057169689Skan
3058169689Skan  if (TREE_TYPE (expr) != ctype)
3059169689Skan    {
3060169689Skan      /* This may happen with the original ivs.  */
3061169689Skan      expr = fold_convert (ctype, expr);
3062169689Skan    }
3063169689Skan
3064169689Skan  if (TYPE_UNSIGNED (utype))
3065169689Skan    uutype = utype;
3066169689Skan  else
3067169689Skan    {
3068169689Skan      uutype = unsigned_type_for (utype);
3069169689Skan      ubase = fold_convert (uutype, ubase);
3070169689Skan      ustep = fold_convert (uutype, ustep);
3071169689Skan    }
3072169689Skan
3073169689Skan  if (uutype != ctype)
3074169689Skan    {
3075169689Skan      expr = fold_convert (uutype, expr);
3076169689Skan      cbase = fold_convert (uutype, cbase);
3077169689Skan      cstep = fold_convert (uutype, cstep);
3078169689Skan
3079169689Skan      /* If the conversion is not noop, we must take it into account when
3080169689Skan	 considering the value of the step.  */
3081169689Skan      if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
3082169689Skan	cstep_orig = cstep;
3083169689Skan    }
3084169689Skan
3085169689Skan  if (cst_and_fits_in_hwi (cstep_orig)
3086169689Skan      && cst_and_fits_in_hwi (ustep_orig))
3087169689Skan    {
3088169689Skan      ustepi = int_cst_value (ustep_orig);
3089169689Skan      cstepi = int_cst_value (cstep_orig);
3090169689Skan
3091169689Skan      if (!divide (TYPE_PRECISION (uutype), ustepi, cstepi, &ratioi))
3092169689Skan	{
3093169689Skan	  /* TODO maybe consider case when ustep divides cstep and the ratio is
3094169689Skan	     a power of 2 (so that the division is fast to execute)?  We would
3095169689Skan	     need to be much more careful with overflows etc. then.  */
3096169689Skan	  return false;
3097169689Skan	}
3098169689Skan
3099169689Skan      ratio = build_int_cst_type (uutype, ratioi);
3100169689Skan    }
3101169689Skan  else
3102169689Skan    {
3103169689Skan      if (!constant_multiple_of (ustep_orig, cstep_orig, &rat))
3104169689Skan	return false;
3105169689Skan      ratio = double_int_to_tree (uutype, rat);
3106169689Skan
3107169689Skan      /* Ratioi is only used to detect special cases when the multiplicative
3108169689Skan	 factor is 1 or -1, so if rat does not fit to HOST_WIDE_INT, we may
3109169689Skan	 set it to 0.  */
3110169689Skan      if (double_int_fits_in_shwi_p (rat))
3111169689Skan	ratioi = double_int_to_shwi (rat);
3112169689Skan      else
3113169689Skan	ratioi = 0;
3114169689Skan    }
3115169689Skan
3116169689Skan  /* In case both UBASE and CBASE are shortened to UUTYPE from some common
3117169689Skan     type, we achieve better folding by computing their difference in this
3118169689Skan     wider type, and cast the result to UUTYPE.  We do not need to worry about
3119169689Skan     overflows, as all the arithmetics will in the end be performed in UUTYPE
3120169689Skan     anyway.  */
3121169689Skan  common_type = determine_common_wider_type (&ubase, &cbase);
3122169689Skan
3123169689Skan  /* We may need to shift the value if we are after the increment.  */
3124169689Skan  if (stmt_after_increment (loop, cand, at))
3125169689Skan    {
3126169689Skan      if (uutype != common_type)
3127169689Skan	cstep = fold_convert (common_type, cstep);
3128169689Skan      cbase = fold_build2 (PLUS_EXPR, common_type, cbase, cstep);
3129169689Skan    }
3130169689Skan
3131169689Skan  /* use = ubase - ratio * cbase + ratio * var.
3132169689Skan
3133169689Skan     In general case ubase + ratio * (var - cbase) could be better (one less
3134169689Skan     multiplication), but often it is possible to eliminate redundant parts
3135169689Skan     of computations from (ubase - ratio * cbase) term, and if it does not
3136169689Skan     happen, fold is able to apply the distributive law to obtain this form
3137169689Skan     anyway.  */
3138169689Skan
3139169689Skan  if (TYPE_PRECISION (common_type) > HOST_BITS_PER_WIDE_INT)
3140169689Skan    {
3141169689Skan      /* Let's compute in trees and just return the result in AFF.  This case
3142169689Skan	 should not be very common, and fold itself is not that bad either,
3143169689Skan	 so making the aff. functions more complicated to handle this case
3144169689Skan	 is not that urgent.  */
3145169689Skan      if (ratioi == 1)
3146169689Skan	{
3147169689Skan	  delta = fold_build2 (MINUS_EXPR, common_type, ubase, cbase);
3148169689Skan	  if (uutype != common_type)
3149169689Skan	    delta = fold_convert (uutype, delta);
3150169689Skan	  expr = fold_build2 (PLUS_EXPR, uutype, expr, delta);
3151169689Skan	}
3152169689Skan      else if (ratioi == -1)
3153169689Skan	{
3154169689Skan	  delta = fold_build2 (PLUS_EXPR, common_type, ubase, cbase);
3155169689Skan	  if (uutype != common_type)
3156169689Skan	    delta = fold_convert (uutype, delta);
3157169689Skan	  expr = fold_build2 (MINUS_EXPR, uutype, delta, expr);
3158169689Skan	}
3159169689Skan      else
3160169689Skan	{
3161169689Skan	  delta = fold_build2 (MULT_EXPR, common_type, cbase, ratio);
3162169689Skan	  delta = fold_build2 (MINUS_EXPR, common_type, ubase, delta);
3163169689Skan	  if (uutype != common_type)
3164169689Skan	    delta = fold_convert (uutype, delta);
3165169689Skan	  expr = fold_build2 (MULT_EXPR, uutype, ratio, expr);
3166169689Skan	  expr = fold_build2 (PLUS_EXPR, uutype, delta, expr);
3167169689Skan	}
3168169689Skan
3169169689Skan      aff->type = uutype;
3170169689Skan      aff->n = 0;
3171169689Skan      aff->offset = 0;
3172169689Skan      aff->mask = 0;
3173169689Skan      aff->rest = expr;
3174169689Skan      return true;
3175169689Skan    }
3176169689Skan
3177169689Skan  /* If we got here, the types fits in HOST_WIDE_INT, thus it must be
3178169689Skan     possible to compute ratioi.  */
3179169689Skan  gcc_assert (ratioi);
3180169689Skan
3181169689Skan  tree_to_aff_combination (ubase, common_type, aff);
3182169689Skan  tree_to_aff_combination (cbase, common_type, &cbase_aff);
3183169689Skan  tree_to_aff_combination (expr, uutype, &expr_aff);
3184169689Skan  aff_combination_scale (&cbase_aff, -ratioi);
3185169689Skan  aff_combination_scale (&expr_aff, ratioi);
3186169689Skan  aff_combination_add (aff, &cbase_aff);
3187169689Skan  if (common_type != uutype)
3188169689Skan    aff_combination_convert (uutype, aff);
3189169689Skan  aff_combination_add (aff, &expr_aff);
3190169689Skan
3191169689Skan  return true;
3192169689Skan}
3193169689Skan
3194169689Skan/* Determines the expression by that USE is expressed from induction variable
3195169689Skan   CAND at statement AT in LOOP.  The computation is unshared.  */
3196169689Skan
3197169689Skanstatic tree
3198169689Skanget_computation_at (struct loop *loop,
3199169689Skan		    struct iv_use *use, struct iv_cand *cand, tree at)
3200169689Skan{
3201169689Skan  struct affine_tree_combination aff;
3202169689Skan  tree type = TREE_TYPE (use->iv->base);
3203169689Skan
3204169689Skan  if (!get_computation_aff (loop, use, cand, at, &aff))
3205169689Skan    return NULL_TREE;
3206169689Skan  unshare_aff_combination (&aff);
3207169689Skan  return fold_convert (type, aff_combination_to_tree (&aff));
3208169689Skan}
3209169689Skan
3210169689Skan/* Determines the expression by that USE is expressed from induction variable
3211169689Skan   CAND in LOOP.  The computation is unshared.  */
3212169689Skan
3213169689Skanstatic tree
3214169689Skanget_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand)
3215169689Skan{
3216169689Skan  return get_computation_at (loop, use, cand, use->stmt);
3217169689Skan}
3218169689Skan
3219169689Skan/* Returns cost of addition in MODE.  */
3220169689Skan
3221169689Skanstatic unsigned
3222169689Skanadd_cost (enum machine_mode mode)
3223169689Skan{
3224169689Skan  static unsigned costs[NUM_MACHINE_MODES];
3225169689Skan  rtx seq;
3226169689Skan  unsigned cost;
3227169689Skan
3228169689Skan  if (costs[mode])
3229169689Skan    return costs[mode];
3230169689Skan
3231169689Skan  start_sequence ();
3232169689Skan  force_operand (gen_rtx_fmt_ee (PLUS, mode,
3233169689Skan				 gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
3234169689Skan				 gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 2)),
3235169689Skan		 NULL_RTX);
3236169689Skan  seq = get_insns ();
3237169689Skan  end_sequence ();
3238169689Skan
3239169689Skan  cost = seq_cost (seq);
3240169689Skan  if (!cost)
3241169689Skan    cost = 1;
3242169689Skan
3243169689Skan  costs[mode] = cost;
3244169689Skan
3245169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
3246169689Skan    fprintf (dump_file, "Addition in %s costs %d\n",
3247169689Skan	     GET_MODE_NAME (mode), cost);
3248169689Skan  return cost;
3249169689Skan}
3250169689Skan
3251169689Skan/* Entry in a hashtable of already known costs for multiplication.  */
3252169689Skanstruct mbc_entry
3253169689Skan{
3254169689Skan  HOST_WIDE_INT cst;		/* The constant to multiply by.  */
3255169689Skan  enum machine_mode mode;	/* In mode.  */
3256169689Skan  unsigned cost;		/* The cost.  */
3257169689Skan};
3258169689Skan
3259169689Skan/* Counts hash value for the ENTRY.  */
3260169689Skan
3261169689Skanstatic hashval_t
3262169689Skanmbc_entry_hash (const void *entry)
3263169689Skan{
3264169689Skan  const struct mbc_entry *e = entry;
3265169689Skan
3266169689Skan  return 57 * (hashval_t) e->mode + (hashval_t) (e->cst % 877);
3267169689Skan}
3268169689Skan
3269169689Skan/* Compares the hash table entries ENTRY1 and ENTRY2.  */
3270169689Skan
3271169689Skanstatic int
3272169689Skanmbc_entry_eq (const void *entry1, const void *entry2)
3273169689Skan{
3274169689Skan  const struct mbc_entry *e1 = entry1;
3275169689Skan  const struct mbc_entry *e2 = entry2;
3276169689Skan
3277169689Skan  return (e1->mode == e2->mode
3278169689Skan	  && e1->cst == e2->cst);
3279169689Skan}
3280169689Skan
3281169689Skan/* Returns cost of multiplication by constant CST in MODE.  */
3282169689Skan
3283169689Skanunsigned
3284169689Skanmultiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode)
3285169689Skan{
3286169689Skan  static htab_t costs;
3287169689Skan  struct mbc_entry **cached, act;
3288169689Skan  rtx seq;
3289169689Skan  unsigned cost;
3290169689Skan
3291169689Skan  if (!costs)
3292169689Skan    costs = htab_create (100, mbc_entry_hash, mbc_entry_eq, free);
3293169689Skan
3294169689Skan  act.mode = mode;
3295169689Skan  act.cst = cst;
3296169689Skan  cached = (struct mbc_entry **) htab_find_slot (costs, &act, INSERT);
3297169689Skan  if (*cached)
3298169689Skan    return (*cached)->cost;
3299169689Skan
3300169689Skan  *cached = XNEW (struct mbc_entry);
3301169689Skan  (*cached)->mode = mode;
3302169689Skan  (*cached)->cst = cst;
3303169689Skan
3304169689Skan  start_sequence ();
3305169689Skan  expand_mult (mode, gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
3306169689Skan	       gen_int_mode (cst, mode), NULL_RTX, 0);
3307169689Skan  seq = get_insns ();
3308169689Skan  end_sequence ();
3309169689Skan
3310169689Skan  cost = seq_cost (seq);
3311169689Skan
3312169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
3313169689Skan    fprintf (dump_file, "Multiplication by %d in %s costs %d\n",
3314169689Skan	     (int) cst, GET_MODE_NAME (mode), cost);
3315169689Skan
3316169689Skan  (*cached)->cost = cost;
3317169689Skan
3318169689Skan  return cost;
3319169689Skan}
3320169689Skan
3321169689Skan/* Returns true if multiplying by RATIO is allowed in address.  */
3322169689Skan
3323169689Skanbool
3324169689Skanmultiplier_allowed_in_address_p (HOST_WIDE_INT ratio)
3325169689Skan{
3326169689Skan#define MAX_RATIO 128
3327169689Skan  static sbitmap valid_mult;
3328169689Skan
3329169689Skan  if (!valid_mult)
3330169689Skan    {
3331169689Skan      rtx reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
3332169689Skan      rtx addr;
3333169689Skan      HOST_WIDE_INT i;
3334169689Skan
3335169689Skan      valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1);
3336169689Skan      sbitmap_zero (valid_mult);
3337169689Skan      addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX);
3338169689Skan      for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
3339169689Skan	{
3340169689Skan	  XEXP (addr, 1) = gen_int_mode (i, Pmode);
3341169689Skan	  if (memory_address_p (Pmode, addr))
3342169689Skan	    SET_BIT (valid_mult, i + MAX_RATIO);
3343169689Skan	}
3344169689Skan
3345169689Skan      if (dump_file && (dump_flags & TDF_DETAILS))
3346169689Skan	{
3347169689Skan	  fprintf (dump_file, "  allowed multipliers:");
3348169689Skan	  for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
3349169689Skan	    if (TEST_BIT (valid_mult, i + MAX_RATIO))
3350169689Skan	      fprintf (dump_file, " %d", (int) i);
3351169689Skan	  fprintf (dump_file, "\n");
3352169689Skan	  fprintf (dump_file, "\n");
3353169689Skan	}
3354169689Skan    }
3355169689Skan
3356169689Skan  if (ratio > MAX_RATIO || ratio < -MAX_RATIO)
3357169689Skan    return false;
3358169689Skan
3359169689Skan  return TEST_BIT (valid_mult, ratio + MAX_RATIO);
3360169689Skan}
3361169689Skan
3362169689Skan/* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
3363169689Skan   If SYMBOL_PRESENT is false, symbol is omitted.  If VAR_PRESENT is false,
3364169689Skan   variable is omitted.  The created memory accesses MODE.
3365169689Skan
3366169689Skan   TODO -- there must be some better way.  This all is quite crude.  */
3367169689Skan
3368169689Skanstatic unsigned
3369169689Skanget_address_cost (bool symbol_present, bool var_present,
3370169689Skan		  unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio)
3371169689Skan{
3372169689Skan  static bool initialized = false;
3373169689Skan  static HOST_WIDE_INT rat, off;
3374169689Skan  static HOST_WIDE_INT min_offset, max_offset;
3375169689Skan  static unsigned costs[2][2][2][2];
3376169689Skan  unsigned cost, acost;
3377169689Skan  bool offset_p, ratio_p;
3378169689Skan  HOST_WIDE_INT s_offset;
3379169689Skan  unsigned HOST_WIDE_INT mask;
3380169689Skan  unsigned bits;
3381169689Skan
3382169689Skan  if (!initialized)
3383169689Skan    {
3384169689Skan      HOST_WIDE_INT i;
3385169689Skan      int old_cse_not_expected;
3386169689Skan      unsigned sym_p, var_p, off_p, rat_p, add_c;
3387169689Skan      rtx seq, addr, base;
3388169689Skan      rtx reg0, reg1;
3389169689Skan
3390169689Skan      initialized = true;
3391169689Skan
3392169689Skan      reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
3393169689Skan
3394169689Skan      addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
3395169689Skan      for (i = 1; i <= 1 << 20; i <<= 1)
3396169689Skan	{
3397169689Skan	  XEXP (addr, 1) = gen_int_mode (i, Pmode);
3398169689Skan	  if (!memory_address_p (Pmode, addr))
3399169689Skan	    break;
3400169689Skan	}
3401169689Skan      max_offset = i >> 1;
3402169689Skan      off = max_offset;
3403169689Skan
3404169689Skan      for (i = 1; i <= 1 << 20; i <<= 1)
3405169689Skan	{
3406169689Skan	  XEXP (addr, 1) = gen_int_mode (-i, Pmode);
3407169689Skan	  if (!memory_address_p (Pmode, addr))
3408169689Skan	    break;
3409169689Skan	}
3410169689Skan      min_offset = -(i >> 1);
3411169689Skan
3412169689Skan      if (dump_file && (dump_flags & TDF_DETAILS))
3413169689Skan	{
3414169689Skan	  fprintf (dump_file, "get_address_cost:\n");
3415169689Skan	  fprintf (dump_file, "  min offset %d\n", (int) min_offset);
3416169689Skan	  fprintf (dump_file, "  max offset %d\n", (int) max_offset);
3417169689Skan	}
3418169689Skan
3419169689Skan      rat = 1;
3420169689Skan      for (i = 2; i <= MAX_RATIO; i++)
3421169689Skan	if (multiplier_allowed_in_address_p (i))
3422169689Skan	  {
3423169689Skan	    rat = i;
3424169689Skan	    break;
3425169689Skan	  }
3426169689Skan
3427169689Skan      /* Compute the cost of various addressing modes.  */
3428169689Skan      acost = 0;
3429169689Skan      reg0 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
3430169689Skan      reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
3431169689Skan
3432169689Skan      for (i = 0; i < 16; i++)
3433169689Skan	{
3434169689Skan	  sym_p = i & 1;
3435169689Skan	  var_p = (i >> 1) & 1;
3436169689Skan	  off_p = (i >> 2) & 1;
3437169689Skan	  rat_p = (i >> 3) & 1;
3438169689Skan
3439169689Skan	  addr = reg0;
3440169689Skan	  if (rat_p)
3441169689Skan	    addr = gen_rtx_fmt_ee (MULT, Pmode, addr, gen_int_mode (rat, Pmode));
3442169689Skan
3443169689Skan	  if (var_p)
3444169689Skan	    addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1);
3445169689Skan
3446169689Skan	  if (sym_p)
3447169689Skan	    {
3448169689Skan	      base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
3449169689Skan	      if (off_p)
3450169689Skan		base = gen_rtx_fmt_e (CONST, Pmode,
3451169689Skan				      gen_rtx_fmt_ee (PLUS, Pmode,
3452169689Skan						      base,
3453169689Skan						      gen_int_mode (off, Pmode)));
3454169689Skan	    }
3455169689Skan	  else if (off_p)
3456169689Skan	    base = gen_int_mode (off, Pmode);
3457169689Skan	  else
3458169689Skan	    base = NULL_RTX;
3459169689Skan
3460169689Skan	  if (base)
3461169689Skan	    addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, base);
3462169689Skan
3463169689Skan	  start_sequence ();
3464169689Skan	  /* To avoid splitting addressing modes, pretend that no cse will
3465169689Skan	     follow.  */
3466169689Skan	  old_cse_not_expected = cse_not_expected;
3467169689Skan	  cse_not_expected = true;
3468169689Skan	  addr = memory_address (Pmode, addr);
3469169689Skan	  cse_not_expected = old_cse_not_expected;
3470169689Skan	  seq = get_insns ();
3471169689Skan	  end_sequence ();
3472169689Skan
3473169689Skan	  acost = seq_cost (seq);
3474169689Skan	  acost += address_cost (addr, Pmode);
3475169689Skan
3476169689Skan	  if (!acost)
3477169689Skan	    acost = 1;
3478169689Skan	  costs[sym_p][var_p][off_p][rat_p] = acost;
3479169689Skan	}
3480169689Skan
3481169689Skan      /* On some targets, it is quite expensive to load symbol to a register,
3482169689Skan	 which makes addresses that contain symbols look much more expensive.
3483169689Skan	 However, the symbol will have to be loaded in any case before the
3484169689Skan	 loop (and quite likely we have it in register already), so it does not
3485169689Skan	 make much sense to penalize them too heavily.  So make some final
3486169689Skan         tweaks for the SYMBOL_PRESENT modes:
3487169689Skan
3488169689Skan         If VAR_PRESENT is false, and the mode obtained by changing symbol to
3489169689Skan	 var is cheaper, use this mode with small penalty.
3490169689Skan	 If VAR_PRESENT is true, try whether the mode with
3491169689Skan	 SYMBOL_PRESENT = false is cheaper even with cost of addition, and
3492169689Skan	 if this is the case, use it.  */
3493169689Skan      add_c = add_cost (Pmode);
3494169689Skan      for (i = 0; i < 8; i++)
3495169689Skan	{
3496169689Skan	  var_p = i & 1;
3497169689Skan	  off_p = (i >> 1) & 1;
3498169689Skan	  rat_p = (i >> 2) & 1;
3499169689Skan
3500169689Skan	  acost = costs[0][1][off_p][rat_p] + 1;
3501169689Skan	  if (var_p)
3502169689Skan	    acost += add_c;
3503169689Skan
3504169689Skan	  if (acost < costs[1][var_p][off_p][rat_p])
3505169689Skan	    costs[1][var_p][off_p][rat_p] = acost;
3506169689Skan	}
3507169689Skan
3508169689Skan      if (dump_file && (dump_flags & TDF_DETAILS))
3509169689Skan	{
3510169689Skan	  fprintf (dump_file, "Address costs:\n");
3511169689Skan
3512169689Skan	  for (i = 0; i < 16; i++)
3513169689Skan	    {
3514169689Skan	      sym_p = i & 1;
3515169689Skan	      var_p = (i >> 1) & 1;
3516169689Skan	      off_p = (i >> 2) & 1;
3517169689Skan	      rat_p = (i >> 3) & 1;
3518169689Skan
3519169689Skan	      fprintf (dump_file, "  ");
3520169689Skan	      if (sym_p)
3521169689Skan		fprintf (dump_file, "sym + ");
3522169689Skan	      if (var_p)
3523169689Skan		fprintf (dump_file, "var + ");
3524169689Skan	      if (off_p)
3525169689Skan		fprintf (dump_file, "cst + ");
3526169689Skan	      if (rat_p)
3527169689Skan		fprintf (dump_file, "rat * ");
3528169689Skan
3529169689Skan	      acost = costs[sym_p][var_p][off_p][rat_p];
3530169689Skan	      fprintf (dump_file, "index costs %d\n", acost);
3531169689Skan	    }
3532169689Skan	  fprintf (dump_file, "\n");
3533169689Skan	}
3534169689Skan    }
3535169689Skan
3536169689Skan  bits = GET_MODE_BITSIZE (Pmode);
3537169689Skan  mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
3538169689Skan  offset &= mask;
3539169689Skan  if ((offset >> (bits - 1) & 1))
3540169689Skan    offset |= ~mask;
3541169689Skan  s_offset = offset;
3542169689Skan
3543169689Skan  cost = 0;
3544169689Skan  offset_p = (s_offset != 0
3545169689Skan	      && min_offset <= s_offset && s_offset <= max_offset);
3546169689Skan  ratio_p = (ratio != 1
3547169689Skan	     && multiplier_allowed_in_address_p (ratio));
3548169689Skan
3549169689Skan  if (ratio != 1 && !ratio_p)
3550169689Skan    cost += multiply_by_cost (ratio, Pmode);
3551169689Skan
3552169689Skan  if (s_offset && !offset_p && !symbol_present)
3553169689Skan    {
3554169689Skan      cost += add_cost (Pmode);
3555169689Skan      var_present = true;
3556169689Skan    }
3557169689Skan
3558169689Skan  acost = costs[symbol_present][var_present][offset_p][ratio_p];
3559169689Skan  return cost + acost;
3560169689Skan}
3561169689Skan
3562169689Skan/* Estimates cost of forcing expression EXPR into a variable.  */
3563169689Skan
3564169689Skanunsigned
3565169689Skanforce_expr_to_var_cost (tree expr)
3566169689Skan{
3567169689Skan  static bool costs_initialized = false;
3568169689Skan  static unsigned integer_cost;
3569169689Skan  static unsigned symbol_cost;
3570169689Skan  static unsigned address_cost;
3571169689Skan  tree op0, op1;
3572169689Skan  unsigned cost0, cost1, cost;
3573169689Skan  enum machine_mode mode;
3574169689Skan
3575169689Skan  if (!costs_initialized)
3576169689Skan    {
3577169689Skan      tree var = create_tmp_var_raw (integer_type_node, "test_var");
3578169689Skan      rtx x = gen_rtx_MEM (DECL_MODE (var),
3579169689Skan			   gen_rtx_SYMBOL_REF (Pmode, "test_var"));
3580169689Skan      tree addr;
3581169689Skan      tree type = build_pointer_type (integer_type_node);
3582169689Skan
3583169689Skan      integer_cost = computation_cost (build_int_cst (integer_type_node,
3584169689Skan						      2000));
3585169689Skan
3586169689Skan      SET_DECL_RTL (var, x);
3587169689Skan      TREE_STATIC (var) = 1;
3588169689Skan      addr = build1 (ADDR_EXPR, type, var);
3589169689Skan      symbol_cost = computation_cost (addr) + 1;
3590169689Skan
3591169689Skan      address_cost
3592169689Skan	= computation_cost (build2 (PLUS_EXPR, type,
3593169689Skan				    addr,
3594169689Skan				    build_int_cst (type, 2000))) + 1;
3595169689Skan      if (dump_file && (dump_flags & TDF_DETAILS))
3596169689Skan	{
3597169689Skan	  fprintf (dump_file, "force_expr_to_var_cost:\n");
3598169689Skan	  fprintf (dump_file, "  integer %d\n", (int) integer_cost);
3599169689Skan	  fprintf (dump_file, "  symbol %d\n", (int) symbol_cost);
3600169689Skan	  fprintf (dump_file, "  address %d\n", (int) address_cost);
3601169689Skan	  fprintf (dump_file, "  other %d\n", (int) target_spill_cost);
3602169689Skan	  fprintf (dump_file, "\n");
3603169689Skan	}
3604169689Skan
3605169689Skan      costs_initialized = true;
3606169689Skan    }
3607169689Skan
3608169689Skan  STRIP_NOPS (expr);
3609169689Skan
3610169689Skan  if (SSA_VAR_P (expr))
3611169689Skan    return 0;
3612169689Skan
3613169689Skan  if (TREE_INVARIANT (expr))
3614169689Skan    {
3615169689Skan      if (TREE_CODE (expr) == INTEGER_CST)
3616169689Skan	return integer_cost;
3617169689Skan
3618169689Skan      if (TREE_CODE (expr) == ADDR_EXPR)
3619169689Skan	{
3620169689Skan	  tree obj = TREE_OPERAND (expr, 0);
3621169689Skan
3622169689Skan	  if (TREE_CODE (obj) == VAR_DECL
3623169689Skan	      || TREE_CODE (obj) == PARM_DECL
3624169689Skan	      || TREE_CODE (obj) == RESULT_DECL)
3625169689Skan	    return symbol_cost;
3626169689Skan	}
3627169689Skan
3628169689Skan      return address_cost;
3629169689Skan    }
3630169689Skan
3631169689Skan  switch (TREE_CODE (expr))
3632169689Skan    {
3633169689Skan    case PLUS_EXPR:
3634169689Skan    case MINUS_EXPR:
3635169689Skan    case MULT_EXPR:
3636169689Skan      op0 = TREE_OPERAND (expr, 0);
3637169689Skan      op1 = TREE_OPERAND (expr, 1);
3638169689Skan      STRIP_NOPS (op0);
3639169689Skan      STRIP_NOPS (op1);
3640169689Skan
3641169689Skan      if (is_gimple_val (op0))
3642169689Skan	cost0 = 0;
3643169689Skan      else
3644169689Skan	cost0 = force_expr_to_var_cost (op0);
3645169689Skan
3646169689Skan      if (is_gimple_val (op1))
3647169689Skan	cost1 = 0;
3648169689Skan      else
3649169689Skan	cost1 = force_expr_to_var_cost (op1);
3650169689Skan
3651169689Skan      break;
3652169689Skan
3653169689Skan    default:
3654169689Skan      /* Just an arbitrary value, FIXME.  */
3655169689Skan      return target_spill_cost;
3656169689Skan    }
3657169689Skan
3658169689Skan  mode = TYPE_MODE (TREE_TYPE (expr));
3659169689Skan  switch (TREE_CODE (expr))
3660169689Skan    {
3661169689Skan    case PLUS_EXPR:
3662169689Skan    case MINUS_EXPR:
3663169689Skan      cost = add_cost (mode);
3664169689Skan      break;
3665169689Skan
3666169689Skan    case MULT_EXPR:
3667169689Skan      if (cst_and_fits_in_hwi (op0))
3668169689Skan	cost = multiply_by_cost (int_cst_value (op0), mode);
3669169689Skan      else if (cst_and_fits_in_hwi (op1))
3670169689Skan	cost = multiply_by_cost (int_cst_value (op1), mode);
3671169689Skan      else
3672169689Skan	return target_spill_cost;
3673169689Skan      break;
3674169689Skan
3675169689Skan    default:
3676169689Skan      gcc_unreachable ();
3677169689Skan    }
3678169689Skan
3679169689Skan  cost += cost0;
3680169689Skan  cost += cost1;
3681169689Skan
3682169689Skan  /* Bound the cost by target_spill_cost.  The parts of complicated
3683169689Skan     computations often are either loop invariant or at least can
3684169689Skan     be shared between several iv uses, so letting this grow without
3685169689Skan     limits would not give reasonable results.  */
3686169689Skan  return cost < target_spill_cost ? cost : target_spill_cost;
3687169689Skan}
3688169689Skan
3689169689Skan/* Estimates cost of forcing EXPR into a variable.  DEPENDS_ON is a set of the
3690169689Skan   invariants the computation depends on.  */
3691169689Skan
3692169689Skanstatic unsigned
3693169689Skanforce_var_cost (struct ivopts_data *data,
3694169689Skan		tree expr, bitmap *depends_on)
3695169689Skan{
3696169689Skan  if (depends_on)
3697169689Skan    {
3698169689Skan      fd_ivopts_data = data;
3699169689Skan      walk_tree (&expr, find_depends, depends_on, NULL);
3700169689Skan    }
3701169689Skan
3702169689Skan  return force_expr_to_var_cost (expr);
3703169689Skan}
3704169689Skan
3705169689Skan/* Estimates cost of expressing address ADDR  as var + symbol + offset.  The
3706169689Skan   value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
3707169689Skan   to false if the corresponding part is missing.  DEPENDS_ON is a set of the
3708169689Skan   invariants the computation depends on.  */
3709169689Skan
3710169689Skanstatic unsigned
3711169689Skansplit_address_cost (struct ivopts_data *data,
3712169689Skan		    tree addr, bool *symbol_present, bool *var_present,
3713169689Skan		    unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
3714169689Skan{
3715169689Skan  tree core;
3716169689Skan  HOST_WIDE_INT bitsize;
3717169689Skan  HOST_WIDE_INT bitpos;
3718169689Skan  tree toffset;
3719169689Skan  enum machine_mode mode;
3720169689Skan  int unsignedp, volatilep;
3721169689Skan
3722169689Skan  core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode,
3723169689Skan			      &unsignedp, &volatilep, false);
3724169689Skan
3725169689Skan  if (toffset != 0
3726169689Skan      || bitpos % BITS_PER_UNIT != 0
3727169689Skan      || TREE_CODE (core) != VAR_DECL)
3728169689Skan    {
3729169689Skan      *symbol_present = false;
3730169689Skan      *var_present = true;
3731169689Skan      fd_ivopts_data = data;
3732169689Skan      walk_tree (&addr, find_depends, depends_on, NULL);
3733169689Skan      return target_spill_cost;
3734169689Skan    }
3735169689Skan
3736169689Skan  *offset += bitpos / BITS_PER_UNIT;
3737169689Skan  if (TREE_STATIC (core)
3738169689Skan      || DECL_EXTERNAL (core))
3739169689Skan    {
3740169689Skan      *symbol_present = true;
3741169689Skan      *var_present = false;
3742169689Skan      return 0;
3743169689Skan    }
3744169689Skan
3745169689Skan  *symbol_present = false;
3746169689Skan  *var_present = true;
3747169689Skan  return 0;
3748169689Skan}
3749169689Skan
3750169689Skan/* Estimates cost of expressing difference of addresses E1 - E2 as
3751169689Skan   var + symbol + offset.  The value of offset is added to OFFSET,
3752169689Skan   SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3753169689Skan   part is missing.  DEPENDS_ON is a set of the invariants the computation
3754169689Skan   depends on.  */
3755169689Skan
3756169689Skanstatic unsigned
3757169689Skanptr_difference_cost (struct ivopts_data *data,
3758169689Skan		     tree e1, tree e2, bool *symbol_present, bool *var_present,
3759169689Skan		     unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
3760169689Skan{
3761169689Skan  HOST_WIDE_INT diff = 0;
3762169689Skan  unsigned cost;
3763169689Skan
3764169689Skan  gcc_assert (TREE_CODE (e1) == ADDR_EXPR);
3765169689Skan
3766169689Skan  if (ptr_difference_const (e1, e2, &diff))
3767169689Skan    {
3768169689Skan      *offset += diff;
3769169689Skan      *symbol_present = false;
3770169689Skan      *var_present = false;
3771169689Skan      return 0;
3772169689Skan    }
3773169689Skan
3774169689Skan  if (e2 == integer_zero_node)
3775169689Skan    return split_address_cost (data, TREE_OPERAND (e1, 0),
3776169689Skan			       symbol_present, var_present, offset, depends_on);
3777169689Skan
3778169689Skan  *symbol_present = false;
3779169689Skan  *var_present = true;
3780169689Skan
3781169689Skan  cost = force_var_cost (data, e1, depends_on);
3782169689Skan  cost += force_var_cost (data, e2, depends_on);
3783169689Skan  cost += add_cost (Pmode);
3784169689Skan
3785169689Skan  return cost;
3786169689Skan}
3787169689Skan
3788169689Skan/* Estimates cost of expressing difference E1 - E2 as
3789169689Skan   var + symbol + offset.  The value of offset is added to OFFSET,
3790169689Skan   SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3791169689Skan   part is missing.  DEPENDS_ON is a set of the invariants the computation
3792169689Skan   depends on.  */
3793169689Skan
3794169689Skanstatic unsigned
3795169689Skandifference_cost (struct ivopts_data *data,
3796169689Skan		 tree e1, tree e2, bool *symbol_present, bool *var_present,
3797169689Skan		 unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
3798169689Skan{
3799169689Skan  unsigned cost;
3800169689Skan  enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
3801169689Skan  unsigned HOST_WIDE_INT off1, off2;
3802169689Skan
3803169689Skan  e1 = strip_offset (e1, &off1);
3804169689Skan  e2 = strip_offset (e2, &off2);
3805169689Skan  *offset += off1 - off2;
3806169689Skan
3807169689Skan  STRIP_NOPS (e1);
3808169689Skan  STRIP_NOPS (e2);
3809169689Skan
3810169689Skan  if (TREE_CODE (e1) == ADDR_EXPR)
3811169689Skan    return ptr_difference_cost (data, e1, e2, symbol_present, var_present, offset,
3812169689Skan				depends_on);
3813169689Skan  *symbol_present = false;
3814169689Skan
3815169689Skan  if (operand_equal_p (e1, e2, 0))
3816169689Skan    {
3817169689Skan      *var_present = false;
3818169689Skan      return 0;
3819169689Skan    }
3820169689Skan  *var_present = true;
3821169689Skan  if (zero_p (e2))
3822169689Skan    return force_var_cost (data, e1, depends_on);
3823169689Skan
3824169689Skan  if (zero_p (e1))
3825169689Skan    {
3826169689Skan      cost = force_var_cost (data, e2, depends_on);
3827169689Skan      cost += multiply_by_cost (-1, mode);
3828169689Skan
3829169689Skan      return cost;
3830169689Skan    }
3831169689Skan
3832169689Skan  cost = force_var_cost (data, e1, depends_on);
3833169689Skan  cost += force_var_cost (data, e2, depends_on);
3834169689Skan  cost += add_cost (mode);
3835169689Skan
3836169689Skan  return cost;
3837169689Skan}
3838169689Skan
3839169689Skan/* Determines the cost of the computation by that USE is expressed
3840169689Skan   from induction variable CAND.  If ADDRESS_P is true, we just need
3841169689Skan   to create an address from it, otherwise we want to get it into
3842169689Skan   register.  A set of invariants we depend on is stored in
3843169689Skan   DEPENDS_ON.  AT is the statement at that the value is computed.  */
3844169689Skan
3845169689Skanstatic unsigned
3846169689Skanget_computation_cost_at (struct ivopts_data *data,
3847169689Skan			 struct iv_use *use, struct iv_cand *cand,
3848169689Skan			 bool address_p, bitmap *depends_on, tree at)
3849169689Skan{
3850169689Skan  tree ubase = use->iv->base, ustep = use->iv->step;
3851169689Skan  tree cbase, cstep;
3852169689Skan  tree utype = TREE_TYPE (ubase), ctype;
3853169689Skan  unsigned HOST_WIDE_INT ustepi, cstepi, offset = 0;
3854169689Skan  HOST_WIDE_INT ratio, aratio;
3855169689Skan  bool var_present, symbol_present;
3856169689Skan  unsigned cost = 0, n_sums;
3857169689Skan
3858169689Skan  *depends_on = NULL;
3859169689Skan
3860169689Skan  /* Only consider real candidates.  */
3861169689Skan  if (!cand->iv)
3862169689Skan    return INFTY;
3863169689Skan
3864169689Skan  cbase = cand->iv->base;
3865169689Skan  cstep = cand->iv->step;
3866169689Skan  ctype = TREE_TYPE (cbase);
3867169689Skan
3868169689Skan  if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
3869169689Skan    {
3870169689Skan      /* We do not have a precision to express the values of use.  */
3871169689Skan      return INFTY;
3872169689Skan    }
3873169689Skan
3874169689Skan  if (address_p)
3875169689Skan    {
3876169689Skan      /* Do not try to express address of an object with computation based
3877169689Skan	 on address of a different object.  This may cause problems in rtl
3878169689Skan	 level alias analysis (that does not expect this to be happening,
3879169689Skan	 as this is illegal in C), and would be unlikely to be useful
3880169689Skan	 anyway.  */
3881169689Skan      if (use->iv->base_object
3882169689Skan	  && cand->iv->base_object
3883169689Skan	  && !operand_equal_p (use->iv->base_object, cand->iv->base_object, 0))
3884169689Skan	return INFTY;
3885169689Skan    }
3886169689Skan
3887169689Skan  if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
3888169689Skan    {
3889169689Skan      /* TODO -- add direct handling of this case.  */
3890169689Skan      goto fallback;
3891169689Skan    }
3892169689Skan
3893169689Skan  /* CSTEPI is removed from the offset in case statement is after the
3894169689Skan     increment.  If the step is not constant, we use zero instead.
3895169689Skan     This is a bit imprecise (there is the extra addition), but
3896169689Skan     redundancy elimination is likely to transform the code so that
3897169689Skan     it uses value of the variable before increment anyway,
3898169689Skan     so it is not that much unrealistic.  */
3899169689Skan  if (cst_and_fits_in_hwi (cstep))
3900169689Skan    cstepi = int_cst_value (cstep);
3901169689Skan  else
3902169689Skan    cstepi = 0;
3903169689Skan
3904169689Skan  if (cst_and_fits_in_hwi (ustep)
3905169689Skan      && cst_and_fits_in_hwi (cstep))
3906169689Skan    {
3907169689Skan      ustepi = int_cst_value (ustep);
3908169689Skan
3909169689Skan      if (!divide (TYPE_PRECISION (utype), ustepi, cstepi, &ratio))
3910169689Skan	return INFTY;
3911169689Skan    }
3912169689Skan  else
3913169689Skan    {
3914169689Skan      double_int rat;
3915169689Skan
3916169689Skan      if (!constant_multiple_of (ustep, cstep, &rat))
3917169689Skan	return INFTY;
3918169689Skan
3919169689Skan      if (double_int_fits_in_shwi_p (rat))
3920169689Skan	ratio = double_int_to_shwi (rat);
3921169689Skan      else
3922169689Skan	return INFTY;
3923169689Skan    }
3924169689Skan
3925169689Skan  /* use = ubase + ratio * (var - cbase).  If either cbase is a constant
3926169689Skan     or ratio == 1, it is better to handle this like
3927169689Skan
3928169689Skan     ubase - ratio * cbase + ratio * var
3929169689Skan
3930169689Skan     (also holds in the case ratio == -1, TODO.  */
3931169689Skan
3932169689Skan  if (cst_and_fits_in_hwi (cbase))
3933169689Skan    {
3934169689Skan      offset = - ratio * int_cst_value (cbase);
3935169689Skan      cost += difference_cost (data,
3936169689Skan			       ubase, integer_zero_node,
3937169689Skan			       &symbol_present, &var_present, &offset,
3938169689Skan			       depends_on);
3939169689Skan    }
3940169689Skan  else if (ratio == 1)
3941169689Skan    {
3942169689Skan      cost += difference_cost (data,
3943169689Skan			       ubase, cbase,
3944169689Skan			       &symbol_present, &var_present, &offset,
3945169689Skan			       depends_on);
3946169689Skan    }
3947169689Skan  else
3948169689Skan    {
3949169689Skan      cost += force_var_cost (data, cbase, depends_on);
3950169689Skan      cost += add_cost (TYPE_MODE (ctype));
3951169689Skan      cost += difference_cost (data,
3952169689Skan			       ubase, integer_zero_node,
3953169689Skan			       &symbol_present, &var_present, &offset,
3954169689Skan			       depends_on);
3955169689Skan    }
3956169689Skan
3957169689Skan  /* If we are after the increment, the value of the candidate is higher by
3958169689Skan     one iteration.  */
3959169689Skan  if (stmt_after_increment (data->current_loop, cand, at))
3960169689Skan    offset -= ratio * cstepi;
3961169689Skan
3962169689Skan  /* Now the computation is in shape symbol + var1 + const + ratio * var2.
3963169689Skan     (symbol/var/const parts may be omitted).  If we are looking for an address,
3964169689Skan     find the cost of addressing this.  */
3965169689Skan  if (address_p)
3966169689Skan    return cost + get_address_cost (symbol_present, var_present, offset, ratio);
3967169689Skan
3968169689Skan  /* Otherwise estimate the costs for computing the expression.  */
3969169689Skan  aratio = ratio > 0 ? ratio : -ratio;
3970169689Skan  if (!symbol_present && !var_present && !offset)
3971169689Skan    {
3972169689Skan      if (ratio != 1)
3973169689Skan	cost += multiply_by_cost (ratio, TYPE_MODE (ctype));
3974169689Skan
3975169689Skan      return cost;
3976169689Skan    }
3977169689Skan
3978169689Skan  if (aratio != 1)
3979169689Skan    cost += multiply_by_cost (aratio, TYPE_MODE (ctype));
3980169689Skan
3981169689Skan  n_sums = 1;
3982169689Skan  if (var_present
3983169689Skan      /* Symbol + offset should be compile-time computable.  */
3984169689Skan      && (symbol_present || offset))
3985169689Skan    n_sums++;
3986169689Skan
3987169689Skan  return cost + n_sums * add_cost (TYPE_MODE (ctype));
3988169689Skan
3989169689Skanfallback:
3990169689Skan  {
3991169689Skan    /* Just get the expression, expand it and measure the cost.  */
3992169689Skan    tree comp = get_computation_at (data->current_loop, use, cand, at);
3993169689Skan
3994169689Skan    if (!comp)
3995169689Skan      return INFTY;
3996169689Skan
3997169689Skan    if (address_p)
3998169689Skan      comp = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (comp)), comp);
3999169689Skan
4000169689Skan    return computation_cost (comp);
4001169689Skan  }
4002169689Skan}
4003169689Skan
4004169689Skan/* Determines the cost of the computation by that USE is expressed
4005169689Skan   from induction variable CAND.  If ADDRESS_P is true, we just need
4006169689Skan   to create an address from it, otherwise we want to get it into
4007169689Skan   register.  A set of invariants we depend on is stored in
4008169689Skan   DEPENDS_ON.  */
4009169689Skan
4010169689Skanstatic unsigned
4011169689Skanget_computation_cost (struct ivopts_data *data,
4012169689Skan		      struct iv_use *use, struct iv_cand *cand,
4013169689Skan		      bool address_p, bitmap *depends_on)
4014169689Skan{
4015169689Skan  return get_computation_cost_at (data,
4016169689Skan				  use, cand, address_p, depends_on, use->stmt);
4017169689Skan}
4018169689Skan
4019169689Skan/* Determines cost of basing replacement of USE on CAND in a generic
4020169689Skan   expression.  */
4021169689Skan
4022169689Skanstatic bool
4023169689Skandetermine_use_iv_cost_generic (struct ivopts_data *data,
4024169689Skan			       struct iv_use *use, struct iv_cand *cand)
4025169689Skan{
4026169689Skan  bitmap depends_on;
4027169689Skan  unsigned cost;
4028169689Skan
4029169689Skan  /* The simple case first -- if we need to express value of the preserved
4030169689Skan     original biv, the cost is 0.  This also prevents us from counting the
4031169689Skan     cost of increment twice -- once at this use and once in the cost of
4032169689Skan     the candidate.  */
4033169689Skan  if (cand->pos == IP_ORIGINAL
4034169689Skan      && cand->incremented_at == use->stmt)
4035169689Skan    {
4036169689Skan      set_use_iv_cost (data, use, cand, 0, NULL, NULL_TREE);
4037169689Skan      return true;
4038169689Skan    }
4039169689Skan
4040169689Skan  cost = get_computation_cost (data, use, cand, false, &depends_on);
4041169689Skan  set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
4042169689Skan
4043169689Skan  return cost != INFTY;
4044169689Skan}
4045169689Skan
4046169689Skan/* Determines cost of basing replacement of USE on CAND in an address.  */
4047169689Skan
4048169689Skanstatic bool
4049169689Skandetermine_use_iv_cost_address (struct ivopts_data *data,
4050169689Skan			       struct iv_use *use, struct iv_cand *cand)
4051169689Skan{
4052169689Skan  bitmap depends_on;
4053169689Skan  unsigned cost = get_computation_cost (data, use, cand, true, &depends_on);
4054169689Skan
4055169689Skan  set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
4056169689Skan
4057169689Skan  return cost != INFTY;
4058169689Skan}
4059169689Skan
4060169689Skan/* Computes value of induction variable IV in iteration NITER.  */
4061169689Skan
4062169689Skanstatic tree
4063169689Skaniv_value (struct iv *iv, tree niter)
4064169689Skan{
4065169689Skan  tree val;
4066169689Skan  tree type = TREE_TYPE (iv->base);
4067169689Skan
4068169689Skan  niter = fold_convert (type, niter);
4069169689Skan  val = fold_build2 (MULT_EXPR, type, iv->step, niter);
4070169689Skan
4071169689Skan  return fold_build2 (PLUS_EXPR, type, iv->base, val);
4072169689Skan}
4073169689Skan
4074169689Skan/* Computes value of candidate CAND at position AT in iteration NITER.  */
4075169689Skan
4076169689Skanstatic tree
4077169689Skancand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter)
4078169689Skan{
4079169689Skan  tree val = iv_value (cand->iv, niter);
4080169689Skan  tree type = TREE_TYPE (cand->iv->base);
4081169689Skan
4082169689Skan  if (stmt_after_increment (loop, cand, at))
4083169689Skan    val = fold_build2 (PLUS_EXPR, type, val, cand->iv->step);
4084169689Skan
4085169689Skan  return val;
4086169689Skan}
4087169689Skan
4088169689Skan/* Returns period of induction variable iv.  */
4089169689Skan
4090169689Skanstatic tree
4091169689Skaniv_period (struct iv *iv)
4092169689Skan{
4093169689Skan  tree step = iv->step, period, type;
4094169689Skan  tree pow2div;
4095169689Skan
4096169689Skan  gcc_assert (step && TREE_CODE (step) == INTEGER_CST);
4097169689Skan
4098169689Skan  /* Period of the iv is gcd (step, type range).  Since type range is power
4099169689Skan     of two, it suffices to determine the maximum power of two that divides
4100169689Skan     step.  */
4101169689Skan  pow2div = num_ending_zeros (step);
4102169689Skan  type = unsigned_type_for (TREE_TYPE (step));
4103169689Skan
4104169689Skan  period = build_low_bits_mask (type,
4105169689Skan				(TYPE_PRECISION (type)
4106169689Skan				 - tree_low_cst (pow2div, 1)));
4107169689Skan
4108169689Skan  return period;
4109169689Skan}
4110169689Skan
4111169689Skan/* Returns the comparison operator used when eliminating the iv USE.  */
4112169689Skan
4113169689Skanstatic enum tree_code
4114169689Skaniv_elimination_compare (struct ivopts_data *data, struct iv_use *use)
4115169689Skan{
4116169689Skan  struct loop *loop = data->current_loop;
4117169689Skan  basic_block ex_bb;
4118169689Skan  edge exit;
4119169689Skan
4120169689Skan  ex_bb = bb_for_stmt (use->stmt);
4121169689Skan  exit = EDGE_SUCC (ex_bb, 0);
4122169689Skan  if (flow_bb_inside_loop_p (loop, exit->dest))
4123169689Skan    exit = EDGE_SUCC (ex_bb, 1);
4124169689Skan
4125169689Skan  return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
4126169689Skan}
4127169689Skan
4128169689Skan/* Check whether it is possible to express the condition in USE by comparison
4129169689Skan   of candidate CAND.  If so, store the value compared with to BOUND.  */
4130169689Skan
4131169689Skanstatic bool
4132169689Skanmay_eliminate_iv (struct ivopts_data *data,
4133169689Skan		  struct iv_use *use, struct iv_cand *cand, tree *bound)
4134169689Skan{
4135169689Skan  basic_block ex_bb;
4136169689Skan  edge exit;
4137169689Skan  tree nit, nit_type;
4138169689Skan  tree wider_type, period, per_type;
4139169689Skan  struct loop *loop = data->current_loop;
4140169689Skan
4141169689Skan  if (TREE_CODE (cand->iv->step) != INTEGER_CST)
4142169689Skan    return false;
4143169689Skan
4144169689Skan  /* For now works only for exits that dominate the loop latch.  TODO -- extend
4145169689Skan     for other conditions inside loop body.  */
4146169689Skan  ex_bb = bb_for_stmt (use->stmt);
4147169689Skan  if (use->stmt != last_stmt (ex_bb)
4148169689Skan      || TREE_CODE (use->stmt) != COND_EXPR)
4149169689Skan    return false;
4150169689Skan  if (!dominated_by_p (CDI_DOMINATORS, loop->latch, ex_bb))
4151169689Skan    return false;
4152169689Skan
4153169689Skan  exit = EDGE_SUCC (ex_bb, 0);
4154169689Skan  if (flow_bb_inside_loop_p (loop, exit->dest))
4155169689Skan    exit = EDGE_SUCC (ex_bb, 1);
4156169689Skan  if (flow_bb_inside_loop_p (loop, exit->dest))
4157169689Skan    return false;
4158169689Skan
4159169689Skan  nit = niter_for_exit (data, exit);
4160169689Skan  if (!nit)
4161169689Skan    return false;
4162169689Skan
4163169689Skan  nit_type = TREE_TYPE (nit);
4164169689Skan
4165169689Skan  /* Determine whether we may use the variable to test whether niter iterations
4166169689Skan     elapsed.  This is the case iff the period of the induction variable is
4167169689Skan     greater than the number of iterations.  */
4168169689Skan  period = iv_period (cand->iv);
4169169689Skan  if (!period)
4170169689Skan    return false;
4171169689Skan  per_type = TREE_TYPE (period);
4172169689Skan
4173169689Skan  wider_type = TREE_TYPE (period);
4174169689Skan  if (TYPE_PRECISION (nit_type) < TYPE_PRECISION (per_type))
4175169689Skan    wider_type = per_type;
4176169689Skan  else
4177169689Skan    wider_type = nit_type;
4178169689Skan
4179169689Skan  if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
4180169689Skan				      fold_convert (wider_type, period),
4181169689Skan				      fold_convert (wider_type, nit))))
4182169689Skan    return false;
4183169689Skan
4184169689Skan  *bound = fold_affine_expr (cand_value_at (loop, cand, use->stmt, nit));
4185169689Skan  return true;
4186169689Skan}
4187169689Skan
4188169689Skan/* Determines cost of basing replacement of USE on CAND in a condition.  */
4189169689Skan
4190169689Skanstatic bool
4191169689Skandetermine_use_iv_cost_condition (struct ivopts_data *data,
4192169689Skan				 struct iv_use *use, struct iv_cand *cand)
4193169689Skan{
4194169689Skan  tree bound = NULL_TREE, op, cond;
4195169689Skan  bitmap depends_on = NULL;
4196169689Skan  unsigned cost;
4197169689Skan
4198169689Skan  /* Only consider real candidates.  */
4199169689Skan  if (!cand->iv)
4200169689Skan    {
4201169689Skan      set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE);
4202169689Skan      return false;
4203169689Skan    }
4204169689Skan
4205169689Skan  if (may_eliminate_iv (data, use, cand, &bound))
4206169689Skan    {
4207169689Skan      cost = force_var_cost (data, bound, &depends_on);
4208169689Skan
4209169689Skan      set_use_iv_cost (data, use, cand, cost, depends_on, bound);
4210169689Skan      return cost != INFTY;
4211169689Skan    }
4212169689Skan
4213169689Skan  /* The induction variable elimination failed; just express the original
4214169689Skan     giv.  If it is compared with an invariant, note that we cannot get
4215169689Skan     rid of it.  */
4216169689Skan  cost = get_computation_cost (data, use, cand, false, &depends_on);
4217169689Skan
4218169689Skan  cond = *use->op_p;
4219169689Skan  if (TREE_CODE (cond) != SSA_NAME)
4220169689Skan    {
4221169689Skan      op = TREE_OPERAND (cond, 0);
4222169689Skan      if (TREE_CODE (op) == SSA_NAME && !zero_p (get_iv (data, op)->step))
4223169689Skan	op = TREE_OPERAND (cond, 1);
4224169689Skan      if (TREE_CODE (op) == SSA_NAME)
4225169689Skan	{
4226169689Skan	  op = get_iv (data, op)->base;
4227169689Skan	  fd_ivopts_data = data;
4228169689Skan	  walk_tree (&op, find_depends, &depends_on, NULL);
4229169689Skan	}
4230169689Skan    }
4231169689Skan
4232169689Skan  set_use_iv_cost (data, use, cand, cost, depends_on, NULL);
4233169689Skan  return cost != INFTY;
4234169689Skan}
4235169689Skan
4236169689Skan/* Determines cost of basing replacement of USE on CAND.  Returns false
4237169689Skan   if USE cannot be based on CAND.  */
4238169689Skan
4239169689Skanstatic bool
4240169689Skandetermine_use_iv_cost (struct ivopts_data *data,
4241169689Skan		       struct iv_use *use, struct iv_cand *cand)
4242169689Skan{
4243169689Skan  switch (use->type)
4244169689Skan    {
4245169689Skan    case USE_NONLINEAR_EXPR:
4246169689Skan      return determine_use_iv_cost_generic (data, use, cand);
4247169689Skan
4248169689Skan    case USE_ADDRESS:
4249169689Skan      return determine_use_iv_cost_address (data, use, cand);
4250169689Skan
4251169689Skan    case USE_COMPARE:
4252169689Skan      return determine_use_iv_cost_condition (data, use, cand);
4253169689Skan
4254169689Skan    default:
4255169689Skan      gcc_unreachable ();
4256169689Skan    }
4257169689Skan}
4258169689Skan
4259169689Skan/* Determines costs of basing the use of the iv on an iv candidate.  */
4260169689Skan
4261169689Skanstatic void
4262169689Skandetermine_use_iv_costs (struct ivopts_data *data)
4263169689Skan{
4264169689Skan  unsigned i, j;
4265169689Skan  struct iv_use *use;
4266169689Skan  struct iv_cand *cand;
4267169689Skan  bitmap to_clear = BITMAP_ALLOC (NULL);
4268169689Skan
4269169689Skan  alloc_use_cost_map (data);
4270169689Skan
4271169689Skan  for (i = 0; i < n_iv_uses (data); i++)
4272169689Skan    {
4273169689Skan      use = iv_use (data, i);
4274169689Skan
4275169689Skan      if (data->consider_all_candidates)
4276169689Skan	{
4277169689Skan	  for (j = 0; j < n_iv_cands (data); j++)
4278169689Skan	    {
4279169689Skan	      cand = iv_cand (data, j);
4280169689Skan	      determine_use_iv_cost (data, use, cand);
4281169689Skan	    }
4282169689Skan	}
4283169689Skan      else
4284169689Skan	{
4285169689Skan	  bitmap_iterator bi;
4286169689Skan
4287169689Skan	  EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi)
4288169689Skan	    {
4289169689Skan	      cand = iv_cand (data, j);
4290169689Skan	      if (!determine_use_iv_cost (data, use, cand))
4291169689Skan		bitmap_set_bit (to_clear, j);
4292169689Skan	    }
4293169689Skan
4294169689Skan	  /* Remove the candidates for that the cost is infinite from
4295169689Skan	     the list of related candidates.  */
4296169689Skan	  bitmap_and_compl_into (use->related_cands, to_clear);
4297169689Skan	  bitmap_clear (to_clear);
4298169689Skan	}
4299169689Skan    }
4300169689Skan
4301169689Skan  BITMAP_FREE (to_clear);
4302169689Skan
4303169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
4304169689Skan    {
4305169689Skan      fprintf (dump_file, "Use-candidate costs:\n");
4306169689Skan
4307169689Skan      for (i = 0; i < n_iv_uses (data); i++)
4308169689Skan	{
4309169689Skan	  use = iv_use (data, i);
4310169689Skan
4311169689Skan	  fprintf (dump_file, "Use %d:\n", i);
4312169689Skan	  fprintf (dump_file, "  cand\tcost\tdepends on\n");
4313169689Skan	  for (j = 0; j < use->n_map_members; j++)
4314169689Skan	    {
4315169689Skan	      if (!use->cost_map[j].cand
4316169689Skan		  || use->cost_map[j].cost == INFTY)
4317169689Skan		continue;
4318169689Skan
4319169689Skan	      fprintf (dump_file, "  %d\t%d\t",
4320169689Skan		       use->cost_map[j].cand->id,
4321169689Skan		       use->cost_map[j].cost);
4322169689Skan	      if (use->cost_map[j].depends_on)
4323169689Skan		bitmap_print (dump_file,
4324169689Skan			      use->cost_map[j].depends_on, "","");
4325169689Skan	      fprintf (dump_file, "\n");
4326169689Skan	    }
4327169689Skan
4328169689Skan	  fprintf (dump_file, "\n");
4329169689Skan	}
4330169689Skan      fprintf (dump_file, "\n");
4331169689Skan    }
4332169689Skan}
4333169689Skan
4334169689Skan/* Determines cost of the candidate CAND.  */
4335169689Skan
4336169689Skanstatic void
4337169689Skandetermine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
4338169689Skan{
4339169689Skan  unsigned cost_base, cost_step;
4340169689Skan  tree base;
4341169689Skan
4342169689Skan  if (!cand->iv)
4343169689Skan    {
4344169689Skan      cand->cost = 0;
4345169689Skan      return;
4346169689Skan    }
4347169689Skan
4348169689Skan  /* There are two costs associated with the candidate -- its increment
4349169689Skan     and its initialization.  The second is almost negligible for any loop
4350169689Skan     that rolls enough, so we take it just very little into account.  */
4351169689Skan
4352169689Skan  base = cand->iv->base;
4353169689Skan  cost_base = force_var_cost (data, base, NULL);
4354169689Skan  cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
4355169689Skan
4356169689Skan  cand->cost = cost_step + cost_base / AVG_LOOP_NITER (current_loop);
4357169689Skan
4358169689Skan  /* Prefer the original iv unless we may gain something by replacing it;
4359169689Skan     this is not really relevant for artificial ivs created by other
4360169689Skan     passes.  */
4361169689Skan  if (cand->pos == IP_ORIGINAL
4362169689Skan      && !DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
4363169689Skan    cand->cost--;
4364169689Skan
4365169689Skan  /* Prefer not to insert statements into latch unless there are some
4366169689Skan     already (so that we do not create unnecessary jumps).  */
4367169689Skan  if (cand->pos == IP_END
4368169689Skan      && empty_block_p (ip_end_pos (data->current_loop)))
4369169689Skan    cand->cost++;
4370169689Skan}
4371169689Skan
4372169689Skan/* Determines costs of computation of the candidates.  */
4373169689Skan
4374169689Skanstatic void
4375169689Skandetermine_iv_costs (struct ivopts_data *data)
4376169689Skan{
4377169689Skan  unsigned i;
4378169689Skan
4379169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
4380169689Skan    {
4381169689Skan      fprintf (dump_file, "Candidate costs:\n");
4382169689Skan      fprintf (dump_file, "  cand\tcost\n");
4383169689Skan    }
4384169689Skan
4385169689Skan  for (i = 0; i < n_iv_cands (data); i++)
4386169689Skan    {
4387169689Skan      struct iv_cand *cand = iv_cand (data, i);
4388169689Skan
4389169689Skan      determine_iv_cost (data, cand);
4390169689Skan
4391169689Skan      if (dump_file && (dump_flags & TDF_DETAILS))
4392169689Skan	fprintf (dump_file, "  %d\t%d\n", i, cand->cost);
4393169689Skan    }
4394169689Skan
4395169689Skanif (dump_file && (dump_flags & TDF_DETAILS))
4396169689Skan      fprintf (dump_file, "\n");
4397169689Skan}
4398169689Skan
4399169689Skan/* Calculates cost for having SIZE induction variables.  */
4400169689Skan
4401169689Skanstatic unsigned
4402169689Skanivopts_global_cost_for_size (struct ivopts_data *data, unsigned size)
4403169689Skan{
4404169689Skan  return global_cost_for_size (size, data->regs_used, n_iv_uses (data));
4405169689Skan}
4406169689Skan
4407169689Skan/* For each size of the induction variable set determine the penalty.  */
4408169689Skan
4409169689Skanstatic void
4410169689Skandetermine_set_costs (struct ivopts_data *data)
4411169689Skan{
4412169689Skan  unsigned j, n;
4413169689Skan  tree phi, op;
4414169689Skan  struct loop *loop = data->current_loop;
4415169689Skan  bitmap_iterator bi;
4416169689Skan
4417169689Skan  /* We use the following model (definitely improvable, especially the
4418169689Skan     cost function -- TODO):
4419169689Skan
4420169689Skan     We estimate the number of registers available (using MD data), name it A.
4421169689Skan
4422169689Skan     We estimate the number of registers used by the loop, name it U.  This
4423169689Skan     number is obtained as the number of loop phi nodes (not counting virtual
4424169689Skan     registers and bivs) + the number of variables from outside of the loop.
4425169689Skan
4426169689Skan     We set a reserve R (free regs that are used for temporary computations,
4427169689Skan     etc.).  For now the reserve is a constant 3.
4428169689Skan
4429169689Skan     Let I be the number of induction variables.
4430169689Skan
4431169689Skan     -- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
4432169689Skan	make a lot of ivs without a reason).
4433169689Skan     -- if A - R < U + I <= A, the cost is I * PRES_COST
4434169689Skan     -- if U + I > A, the cost is I * PRES_COST and
4435169689Skan        number of uses * SPILL_COST * (U + I - A) / (U + I) is added.  */
4436169689Skan
4437169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
4438169689Skan    {
4439169689Skan      fprintf (dump_file, "Global costs:\n");
4440169689Skan      fprintf (dump_file, "  target_avail_regs %d\n", target_avail_regs);
4441169689Skan      fprintf (dump_file, "  target_small_cost %d\n", target_small_cost);
4442169689Skan      fprintf (dump_file, "  target_pres_cost %d\n", target_pres_cost);
4443169689Skan      fprintf (dump_file, "  target_spill_cost %d\n", target_spill_cost);
4444169689Skan    }
4445169689Skan
4446169689Skan  n = 0;
4447169689Skan  for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
4448169689Skan    {
4449169689Skan      op = PHI_RESULT (phi);
4450169689Skan
4451169689Skan      if (!is_gimple_reg (op))
4452169689Skan	continue;
4453169689Skan
4454169689Skan      if (get_iv (data, op))
4455169689Skan	continue;
4456169689Skan
4457169689Skan      n++;
4458169689Skan    }
4459169689Skan
4460169689Skan  EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
4461169689Skan    {
4462169689Skan      struct version_info *info = ver_info (data, j);
4463169689Skan
4464169689Skan      if (info->inv_id && info->has_nonlin_use)
4465169689Skan	n++;
4466169689Skan    }
4467169689Skan
4468169689Skan  data->regs_used = n;
4469169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
4470169689Skan    fprintf (dump_file, "  regs_used %d\n", n);
4471169689Skan
4472169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
4473169689Skan    {
4474169689Skan      fprintf (dump_file, "  cost for size:\n");
4475169689Skan      fprintf (dump_file, "  ivs\tcost\n");
4476169689Skan      for (j = 0; j <= 2 * target_avail_regs; j++)
4477169689Skan	fprintf (dump_file, "  %d\t%d\n", j,
4478169689Skan		 ivopts_global_cost_for_size (data, j));
4479169689Skan      fprintf (dump_file, "\n");
4480169689Skan    }
4481169689Skan}
4482169689Skan
4483169689Skan/* Returns true if A is a cheaper cost pair than B.  */
4484169689Skan
4485169689Skanstatic bool
4486169689Skancheaper_cost_pair (struct cost_pair *a, struct cost_pair *b)
4487169689Skan{
4488169689Skan  if (!a)
4489169689Skan    return false;
4490169689Skan
4491169689Skan  if (!b)
4492169689Skan    return true;
4493169689Skan
4494169689Skan  if (a->cost < b->cost)
4495169689Skan    return true;
4496169689Skan
4497169689Skan  if (a->cost > b->cost)
4498169689Skan    return false;
4499169689Skan
4500169689Skan  /* In case the costs are the same, prefer the cheaper candidate.  */
4501169689Skan  if (a->cand->cost < b->cand->cost)
4502169689Skan    return true;
4503169689Skan
4504169689Skan  return false;
4505169689Skan}
4506169689Skan
4507169689Skan/* Computes the cost field of IVS structure.  */
4508169689Skan
4509169689Skanstatic void
4510169689Skaniv_ca_recount_cost (struct ivopts_data *data, struct iv_ca *ivs)
4511169689Skan{
4512169689Skan  unsigned cost = 0;
4513169689Skan
4514169689Skan  cost += ivs->cand_use_cost;
4515169689Skan  cost += ivs->cand_cost;
4516169689Skan  cost += ivopts_global_cost_for_size (data, ivs->n_regs);
4517169689Skan
4518169689Skan  ivs->cost = cost;
4519169689Skan}
4520169689Skan
4521169689Skan/* Remove invariants in set INVS to set IVS.  */
4522169689Skan
4523169689Skanstatic void
4524169689Skaniv_ca_set_remove_invariants (struct iv_ca *ivs, bitmap invs)
4525169689Skan{
4526169689Skan  bitmap_iterator bi;
4527169689Skan  unsigned iid;
4528169689Skan
4529169689Skan  if (!invs)
4530169689Skan    return;
4531169689Skan
4532169689Skan  EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
4533169689Skan    {
4534169689Skan      ivs->n_invariant_uses[iid]--;
4535169689Skan      if (ivs->n_invariant_uses[iid] == 0)
4536169689Skan	ivs->n_regs--;
4537169689Skan    }
4538169689Skan}
4539169689Skan
4540169689Skan/* Set USE not to be expressed by any candidate in IVS.  */
4541169689Skan
4542169689Skanstatic void
4543169689Skaniv_ca_set_no_cp (struct ivopts_data *data, struct iv_ca *ivs,
4544169689Skan		 struct iv_use *use)
4545169689Skan{
4546169689Skan  unsigned uid = use->id, cid;
4547169689Skan  struct cost_pair *cp;
4548169689Skan
4549169689Skan  cp = ivs->cand_for_use[uid];
4550169689Skan  if (!cp)
4551169689Skan    return;
4552169689Skan  cid = cp->cand->id;
4553169689Skan
4554169689Skan  ivs->bad_uses++;
4555169689Skan  ivs->cand_for_use[uid] = NULL;
4556169689Skan  ivs->n_cand_uses[cid]--;
4557169689Skan
4558169689Skan  if (ivs->n_cand_uses[cid] == 0)
4559169689Skan    {
4560169689Skan      bitmap_clear_bit (ivs->cands, cid);
4561169689Skan      /* Do not count the pseudocandidates.  */
4562169689Skan      if (cp->cand->iv)
4563169689Skan	ivs->n_regs--;
4564169689Skan      ivs->n_cands--;
4565169689Skan      ivs->cand_cost -= cp->cand->cost;
4566169689Skan
4567169689Skan      iv_ca_set_remove_invariants (ivs, cp->cand->depends_on);
4568169689Skan    }
4569169689Skan
4570169689Skan  ivs->cand_use_cost -= cp->cost;
4571169689Skan
4572169689Skan  iv_ca_set_remove_invariants (ivs, cp->depends_on);
4573169689Skan  iv_ca_recount_cost (data, ivs);
4574169689Skan}
4575169689Skan
4576169689Skan/* Add invariants in set INVS to set IVS.  */
4577169689Skan
4578169689Skanstatic void
4579169689Skaniv_ca_set_add_invariants (struct iv_ca *ivs, bitmap invs)
4580169689Skan{
4581169689Skan  bitmap_iterator bi;
4582169689Skan  unsigned iid;
4583169689Skan
4584169689Skan  if (!invs)
4585169689Skan    return;
4586169689Skan
4587169689Skan  EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
4588169689Skan    {
4589169689Skan      ivs->n_invariant_uses[iid]++;
4590169689Skan      if (ivs->n_invariant_uses[iid] == 1)
4591169689Skan	ivs->n_regs++;
4592169689Skan    }
4593169689Skan}
4594169689Skan
4595169689Skan/* Set cost pair for USE in set IVS to CP.  */
4596169689Skan
4597169689Skanstatic void
4598169689Skaniv_ca_set_cp (struct ivopts_data *data, struct iv_ca *ivs,
4599169689Skan	      struct iv_use *use, struct cost_pair *cp)
4600169689Skan{
4601169689Skan  unsigned uid = use->id, cid;
4602169689Skan
4603169689Skan  if (ivs->cand_for_use[uid] == cp)
4604169689Skan    return;
4605169689Skan
4606169689Skan  if (ivs->cand_for_use[uid])
4607169689Skan    iv_ca_set_no_cp (data, ivs, use);
4608169689Skan
4609169689Skan  if (cp)
4610169689Skan    {
4611169689Skan      cid = cp->cand->id;
4612169689Skan
4613169689Skan      ivs->bad_uses--;
4614169689Skan      ivs->cand_for_use[uid] = cp;
4615169689Skan      ivs->n_cand_uses[cid]++;
4616169689Skan      if (ivs->n_cand_uses[cid] == 1)
4617169689Skan	{
4618169689Skan	  bitmap_set_bit (ivs->cands, cid);
4619169689Skan	  /* Do not count the pseudocandidates.  */
4620169689Skan	  if (cp->cand->iv)
4621169689Skan	    ivs->n_regs++;
4622169689Skan	  ivs->n_cands++;
4623169689Skan	  ivs->cand_cost += cp->cand->cost;
4624169689Skan
4625169689Skan	  iv_ca_set_add_invariants (ivs, cp->cand->depends_on);
4626169689Skan	}
4627169689Skan
4628169689Skan      ivs->cand_use_cost += cp->cost;
4629169689Skan      iv_ca_set_add_invariants (ivs, cp->depends_on);
4630169689Skan      iv_ca_recount_cost (data, ivs);
4631169689Skan    }
4632169689Skan}
4633169689Skan
4634169689Skan/* Extend set IVS by expressing USE by some of the candidates in it
4635169689Skan   if possible.  */
4636169689Skan
4637169689Skanstatic void
4638169689Skaniv_ca_add_use (struct ivopts_data *data, struct iv_ca *ivs,
4639169689Skan	       struct iv_use *use)
4640169689Skan{
4641169689Skan  struct cost_pair *best_cp = NULL, *cp;
4642169689Skan  bitmap_iterator bi;
4643169689Skan  unsigned i;
4644169689Skan
4645169689Skan  gcc_assert (ivs->upto >= use->id);
4646169689Skan
4647169689Skan  if (ivs->upto == use->id)
4648169689Skan    {
4649169689Skan      ivs->upto++;
4650169689Skan      ivs->bad_uses++;
4651169689Skan    }
4652169689Skan
4653169689Skan  EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
4654169689Skan    {
4655169689Skan      cp = get_use_iv_cost (data, use, iv_cand (data, i));
4656169689Skan
4657169689Skan      if (cheaper_cost_pair (cp, best_cp))
4658169689Skan	best_cp = cp;
4659169689Skan    }
4660169689Skan
4661169689Skan  iv_ca_set_cp (data, ivs, use, best_cp);
4662169689Skan}
4663169689Skan
4664169689Skan/* Get cost for assignment IVS.  */
4665169689Skan
4666169689Skanstatic unsigned
4667169689Skaniv_ca_cost (struct iv_ca *ivs)
4668169689Skan{
4669169689Skan  return (ivs->bad_uses ? INFTY : ivs->cost);
4670169689Skan}
4671169689Skan
4672169689Skan/* Returns true if all dependences of CP are among invariants in IVS.  */
4673169689Skan
4674169689Skanstatic bool
4675169689Skaniv_ca_has_deps (struct iv_ca *ivs, struct cost_pair *cp)
4676169689Skan{
4677169689Skan  unsigned i;
4678169689Skan  bitmap_iterator bi;
4679169689Skan
4680169689Skan  if (!cp->depends_on)
4681169689Skan    return true;
4682169689Skan
4683169689Skan  EXECUTE_IF_SET_IN_BITMAP (cp->depends_on, 0, i, bi)
4684169689Skan    {
4685169689Skan      if (ivs->n_invariant_uses[i] == 0)
4686169689Skan	return false;
4687169689Skan    }
4688169689Skan
4689169689Skan  return true;
4690169689Skan}
4691169689Skan
4692169689Skan/* Creates change of expressing USE by NEW_CP instead of OLD_CP and chains
4693169689Skan   it before NEXT_CHANGE.  */
4694169689Skan
4695169689Skanstatic struct iv_ca_delta *
4696169689Skaniv_ca_delta_add (struct iv_use *use, struct cost_pair *old_cp,
4697169689Skan		 struct cost_pair *new_cp, struct iv_ca_delta *next_change)
4698169689Skan{
4699169689Skan  struct iv_ca_delta *change = XNEW (struct iv_ca_delta);
4700169689Skan
4701169689Skan  change->use = use;
4702169689Skan  change->old_cp = old_cp;
4703169689Skan  change->new_cp = new_cp;
4704169689Skan  change->next_change = next_change;
4705169689Skan
4706169689Skan  return change;
4707169689Skan}
4708169689Skan
4709169689Skan/* Joins two lists of changes L1 and L2.  Destructive -- old lists
4710169689Skan   are rewritten.  */
4711169689Skan
4712169689Skanstatic struct iv_ca_delta *
4713169689Skaniv_ca_delta_join (struct iv_ca_delta *l1, struct iv_ca_delta *l2)
4714169689Skan{
4715169689Skan  struct iv_ca_delta *last;
4716169689Skan
4717169689Skan  if (!l2)
4718169689Skan    return l1;
4719169689Skan
4720169689Skan  if (!l1)
4721169689Skan    return l2;
4722169689Skan
4723169689Skan  for (last = l1; last->next_change; last = last->next_change)
4724169689Skan    continue;
4725169689Skan  last->next_change = l2;
4726169689Skan
4727169689Skan  return l1;
4728169689Skan}
4729169689Skan
4730169689Skan/* Returns candidate by that USE is expressed in IVS.  */
4731169689Skan
4732169689Skanstatic struct cost_pair *
4733169689Skaniv_ca_cand_for_use (struct iv_ca *ivs, struct iv_use *use)
4734169689Skan{
4735169689Skan  return ivs->cand_for_use[use->id];
4736169689Skan}
4737169689Skan
4738169689Skan/* Reverse the list of changes DELTA, forming the inverse to it.  */
4739169689Skan
4740169689Skanstatic struct iv_ca_delta *
4741169689Skaniv_ca_delta_reverse (struct iv_ca_delta *delta)
4742169689Skan{
4743169689Skan  struct iv_ca_delta *act, *next, *prev = NULL;
4744169689Skan  struct cost_pair *tmp;
4745169689Skan
4746169689Skan  for (act = delta; act; act = next)
4747169689Skan    {
4748169689Skan      next = act->next_change;
4749169689Skan      act->next_change = prev;
4750169689Skan      prev = act;
4751169689Skan
4752169689Skan      tmp = act->old_cp;
4753169689Skan      act->old_cp = act->new_cp;
4754169689Skan      act->new_cp = tmp;
4755169689Skan    }
4756169689Skan
4757169689Skan  return prev;
4758169689Skan}
4759169689Skan
4760169689Skan/* Commit changes in DELTA to IVS.  If FORWARD is false, the changes are
4761169689Skan   reverted instead.  */
4762169689Skan
4763169689Skanstatic void
4764169689Skaniv_ca_delta_commit (struct ivopts_data *data, struct iv_ca *ivs,
4765169689Skan		    struct iv_ca_delta *delta, bool forward)
4766169689Skan{
4767169689Skan  struct cost_pair *from, *to;
4768169689Skan  struct iv_ca_delta *act;
4769169689Skan
4770169689Skan  if (!forward)
4771169689Skan    delta = iv_ca_delta_reverse (delta);
4772169689Skan
4773169689Skan  for (act = delta; act; act = act->next_change)
4774169689Skan    {
4775169689Skan      from = act->old_cp;
4776169689Skan      to = act->new_cp;
4777169689Skan      gcc_assert (iv_ca_cand_for_use (ivs, act->use) == from);
4778169689Skan      iv_ca_set_cp (data, ivs, act->use, to);
4779169689Skan    }
4780169689Skan
4781169689Skan  if (!forward)
4782169689Skan    iv_ca_delta_reverse (delta);
4783169689Skan}
4784169689Skan
4785169689Skan/* Returns true if CAND is used in IVS.  */
4786169689Skan
4787169689Skanstatic bool
4788169689Skaniv_ca_cand_used_p (struct iv_ca *ivs, struct iv_cand *cand)
4789169689Skan{
4790169689Skan  return ivs->n_cand_uses[cand->id] > 0;
4791169689Skan}
4792169689Skan
4793169689Skan/* Returns number of induction variable candidates in the set IVS.  */
4794169689Skan
4795169689Skanstatic unsigned
4796169689Skaniv_ca_n_cands (struct iv_ca *ivs)
4797169689Skan{
4798169689Skan  return ivs->n_cands;
4799169689Skan}
4800169689Skan
4801169689Skan/* Free the list of changes DELTA.  */
4802169689Skan
4803169689Skanstatic void
4804169689Skaniv_ca_delta_free (struct iv_ca_delta **delta)
4805169689Skan{
4806169689Skan  struct iv_ca_delta *act, *next;
4807169689Skan
4808169689Skan  for (act = *delta; act; act = next)
4809169689Skan    {
4810169689Skan      next = act->next_change;
4811169689Skan      free (act);
4812169689Skan    }
4813169689Skan
4814169689Skan  *delta = NULL;
4815169689Skan}
4816169689Skan
4817169689Skan/* Allocates new iv candidates assignment.  */
4818169689Skan
4819169689Skanstatic struct iv_ca *
4820169689Skaniv_ca_new (struct ivopts_data *data)
4821169689Skan{
4822169689Skan  struct iv_ca *nw = XNEW (struct iv_ca);
4823169689Skan
4824169689Skan  nw->upto = 0;
4825169689Skan  nw->bad_uses = 0;
4826169689Skan  nw->cand_for_use = XCNEWVEC (struct cost_pair *, n_iv_uses (data));
4827169689Skan  nw->n_cand_uses = XCNEWVEC (unsigned, n_iv_cands (data));
4828169689Skan  nw->cands = BITMAP_ALLOC (NULL);
4829169689Skan  nw->n_cands = 0;
4830169689Skan  nw->n_regs = 0;
4831169689Skan  nw->cand_use_cost = 0;
4832169689Skan  nw->cand_cost = 0;
4833169689Skan  nw->n_invariant_uses = XCNEWVEC (unsigned, data->max_inv_id + 1);
4834169689Skan  nw->cost = 0;
4835169689Skan
4836169689Skan  return nw;
4837169689Skan}
4838169689Skan
4839169689Skan/* Free memory occupied by the set IVS.  */
4840169689Skan
4841169689Skanstatic void
4842169689Skaniv_ca_free (struct iv_ca **ivs)
4843169689Skan{
4844169689Skan  free ((*ivs)->cand_for_use);
4845169689Skan  free ((*ivs)->n_cand_uses);
4846169689Skan  BITMAP_FREE ((*ivs)->cands);
4847169689Skan  free ((*ivs)->n_invariant_uses);
4848169689Skan  free (*ivs);
4849169689Skan  *ivs = NULL;
4850169689Skan}
4851169689Skan
4852169689Skan/* Dumps IVS to FILE.  */
4853169689Skan
4854169689Skanstatic void
4855169689Skaniv_ca_dump (struct ivopts_data *data, FILE *file, struct iv_ca *ivs)
4856169689Skan{
4857169689Skan  const char *pref = "  invariants ";
4858169689Skan  unsigned i;
4859169689Skan
4860169689Skan  fprintf (file, "  cost %d\n", iv_ca_cost (ivs));
4861169689Skan  bitmap_print (file, ivs->cands, "  candidates ","\n");
4862169689Skan
4863169689Skan  for (i = 1; i <= data->max_inv_id; i++)
4864169689Skan    if (ivs->n_invariant_uses[i])
4865169689Skan      {
4866169689Skan	fprintf (file, "%s%d", pref, i);
4867169689Skan	pref = ", ";
4868169689Skan      }
4869169689Skan  fprintf (file, "\n");
4870169689Skan}
4871169689Skan
4872169689Skan/* Try changing candidate in IVS to CAND for each use.  Return cost of the
4873169689Skan   new set, and store differences in DELTA.  Number of induction variables
4874169689Skan   in the new set is stored to N_IVS.  */
4875169689Skan
4876169689Skanstatic unsigned
4877169689Skaniv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs,
4878169689Skan	      struct iv_cand *cand, struct iv_ca_delta **delta,
4879169689Skan	      unsigned *n_ivs)
4880169689Skan{
4881169689Skan  unsigned i, cost;
4882169689Skan  struct iv_use *use;
4883169689Skan  struct cost_pair *old_cp, *new_cp;
4884169689Skan
4885169689Skan  *delta = NULL;
4886169689Skan  for (i = 0; i < ivs->upto; i++)
4887169689Skan    {
4888169689Skan      use = iv_use (data, i);
4889169689Skan      old_cp = iv_ca_cand_for_use (ivs, use);
4890169689Skan
4891169689Skan      if (old_cp
4892169689Skan	  && old_cp->cand == cand)
4893169689Skan	continue;
4894169689Skan
4895169689Skan      new_cp = get_use_iv_cost (data, use, cand);
4896169689Skan      if (!new_cp)
4897169689Skan	continue;
4898169689Skan
4899169689Skan      if (!iv_ca_has_deps (ivs, new_cp))
4900169689Skan	continue;
4901169689Skan
4902169689Skan      if (!cheaper_cost_pair (new_cp, old_cp))
4903169689Skan	continue;
4904169689Skan
4905169689Skan      *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
4906169689Skan    }
4907169689Skan
4908169689Skan  iv_ca_delta_commit (data, ivs, *delta, true);
4909169689Skan  cost = iv_ca_cost (ivs);
4910169689Skan  if (n_ivs)
4911169689Skan    *n_ivs = iv_ca_n_cands (ivs);
4912169689Skan  iv_ca_delta_commit (data, ivs, *delta, false);
4913169689Skan
4914169689Skan  return cost;
4915169689Skan}
4916169689Skan
4917169689Skan/* Try narrowing set IVS by removing CAND.  Return the cost of
4918169689Skan   the new set and store the differences in DELTA.  */
4919169689Skan
4920169689Skanstatic unsigned
4921169689Skaniv_ca_narrow (struct ivopts_data *data, struct iv_ca *ivs,
4922169689Skan	      struct iv_cand *cand, struct iv_ca_delta **delta)
4923169689Skan{
4924169689Skan  unsigned i, ci;
4925169689Skan  struct iv_use *use;
4926169689Skan  struct cost_pair *old_cp, *new_cp, *cp;
4927169689Skan  bitmap_iterator bi;
4928169689Skan  struct iv_cand *cnd;
4929169689Skan  unsigned cost;
4930169689Skan
4931169689Skan  *delta = NULL;
4932169689Skan  for (i = 0; i < n_iv_uses (data); i++)
4933169689Skan    {
4934169689Skan      use = iv_use (data, i);
4935169689Skan
4936169689Skan      old_cp = iv_ca_cand_for_use (ivs, use);
4937169689Skan      if (old_cp->cand != cand)
4938169689Skan	continue;
4939169689Skan
4940169689Skan      new_cp = NULL;
4941169689Skan
4942169689Skan      if (data->consider_all_candidates)
4943169689Skan	{
4944169689Skan	  EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, ci, bi)
4945169689Skan	    {
4946169689Skan	      if (ci == cand->id)
4947169689Skan		continue;
4948169689Skan
4949169689Skan	      cnd = iv_cand (data, ci);
4950169689Skan
4951169689Skan	      cp = get_use_iv_cost (data, use, cnd);
4952169689Skan	      if (!cp)
4953169689Skan		continue;
4954169689Skan	      if (!iv_ca_has_deps (ivs, cp))
4955169689Skan		continue;
4956169689Skan
4957169689Skan	      if (!cheaper_cost_pair (cp, new_cp))
4958169689Skan		continue;
4959169689Skan
4960169689Skan	      new_cp = cp;
4961169689Skan	    }
4962169689Skan	}
4963169689Skan      else
4964169689Skan	{
4965169689Skan	  EXECUTE_IF_AND_IN_BITMAP (use->related_cands, ivs->cands, 0, ci, bi)
4966169689Skan	    {
4967169689Skan	      if (ci == cand->id)
4968169689Skan		continue;
4969169689Skan
4970169689Skan	      cnd = iv_cand (data, ci);
4971169689Skan
4972169689Skan	      cp = get_use_iv_cost (data, use, cnd);
4973169689Skan	      if (!cp)
4974169689Skan		continue;
4975169689Skan	      if (!iv_ca_has_deps (ivs, cp))
4976169689Skan		continue;
4977169689Skan
4978169689Skan	      if (!cheaper_cost_pair (cp, new_cp))
4979169689Skan		continue;
4980169689Skan
4981169689Skan	      new_cp = cp;
4982169689Skan	    }
4983169689Skan	}
4984169689Skan
4985169689Skan      if (!new_cp)
4986169689Skan	{
4987169689Skan	  iv_ca_delta_free (delta);
4988169689Skan	  return INFTY;
4989169689Skan	}
4990169689Skan
4991169689Skan      *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
4992169689Skan    }
4993169689Skan
4994169689Skan  iv_ca_delta_commit (data, ivs, *delta, true);
4995169689Skan  cost = iv_ca_cost (ivs);
4996169689Skan  iv_ca_delta_commit (data, ivs, *delta, false);
4997169689Skan
4998169689Skan  return cost;
4999169689Skan}
5000169689Skan
5001169689Skan/* Try optimizing the set of candidates IVS by removing candidates different
5002169689Skan   from to EXCEPT_CAND from it.  Return cost of the new set, and store
5003169689Skan   differences in DELTA.  */
5004169689Skan
5005169689Skanstatic unsigned
5006169689Skaniv_ca_prune (struct ivopts_data *data, struct iv_ca *ivs,
5007169689Skan	     struct iv_cand *except_cand, struct iv_ca_delta **delta)
5008169689Skan{
5009169689Skan  bitmap_iterator bi;
5010169689Skan  struct iv_ca_delta *act_delta, *best_delta;
5011169689Skan  unsigned i, best_cost, acost;
5012169689Skan  struct iv_cand *cand;
5013169689Skan
5014169689Skan  best_delta = NULL;
5015169689Skan  best_cost = iv_ca_cost (ivs);
5016169689Skan
5017169689Skan  EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
5018169689Skan    {
5019169689Skan      cand = iv_cand (data, i);
5020169689Skan
5021169689Skan      if (cand == except_cand)
5022169689Skan	continue;
5023169689Skan
5024169689Skan      acost = iv_ca_narrow (data, ivs, cand, &act_delta);
5025169689Skan
5026169689Skan      if (acost < best_cost)
5027169689Skan	{
5028169689Skan	  best_cost = acost;
5029169689Skan	  iv_ca_delta_free (&best_delta);
5030169689Skan	  best_delta = act_delta;
5031169689Skan	}
5032169689Skan      else
5033169689Skan	iv_ca_delta_free (&act_delta);
5034169689Skan    }
5035169689Skan
5036169689Skan  if (!best_delta)
5037169689Skan    {
5038169689Skan      *delta = NULL;
5039169689Skan      return best_cost;
5040169689Skan    }
5041169689Skan
5042169689Skan  /* Recurse to possibly remove other unnecessary ivs.  */
5043169689Skan  iv_ca_delta_commit (data, ivs, best_delta, true);
5044169689Skan  best_cost = iv_ca_prune (data, ivs, except_cand, delta);
5045169689Skan  iv_ca_delta_commit (data, ivs, best_delta, false);
5046169689Skan  *delta = iv_ca_delta_join (best_delta, *delta);
5047169689Skan  return best_cost;
5048169689Skan}
5049169689Skan
5050169689Skan/* Tries to extend the sets IVS in the best possible way in order
5051169689Skan   to express the USE.  */
5052169689Skan
5053169689Skanstatic bool
5054169689Skantry_add_cand_for (struct ivopts_data *data, struct iv_ca *ivs,
5055169689Skan		  struct iv_use *use)
5056169689Skan{
5057169689Skan  unsigned best_cost, act_cost;
5058169689Skan  unsigned i;
5059169689Skan  bitmap_iterator bi;
5060169689Skan  struct iv_cand *cand;
5061169689Skan  struct iv_ca_delta *best_delta = NULL, *act_delta;
5062169689Skan  struct cost_pair *cp;
5063169689Skan
5064169689Skan  iv_ca_add_use (data, ivs, use);
5065169689Skan  best_cost = iv_ca_cost (ivs);
5066169689Skan
5067169689Skan  cp = iv_ca_cand_for_use (ivs, use);
5068169689Skan  if (cp)
5069169689Skan    {
5070169689Skan      best_delta = iv_ca_delta_add (use, NULL, cp, NULL);
5071169689Skan      iv_ca_set_no_cp (data, ivs, use);
5072169689Skan    }
5073169689Skan
5074169689Skan  /* First try important candidates.  Only if it fails, try the specific ones.
5075169689Skan     Rationale -- in loops with many variables the best choice often is to use
5076169689Skan     just one generic biv.  If we added here many ivs specific to the uses,
5077169689Skan     the optimization algorithm later would be likely to get stuck in a local
5078169689Skan     minimum, thus causing us to create too many ivs.  The approach from
5079169689Skan     few ivs to more seems more likely to be successful -- starting from few
5080169689Skan     ivs, replacing an expensive use by a specific iv should always be a
5081169689Skan     win.  */
5082169689Skan  EXECUTE_IF_SET_IN_BITMAP (data->important_candidates, 0, i, bi)
5083169689Skan    {
5084169689Skan      cand = iv_cand (data, i);
5085169689Skan
5086169689Skan      if (iv_ca_cand_used_p (ivs, cand))
5087169689Skan	continue;
5088169689Skan
5089169689Skan      cp = get_use_iv_cost (data, use, cand);
5090169689Skan      if (!cp)
5091169689Skan	continue;
5092169689Skan
5093169689Skan      iv_ca_set_cp (data, ivs, use, cp);
5094169689Skan      act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
5095169689Skan      iv_ca_set_no_cp (data, ivs, use);
5096169689Skan      act_delta = iv_ca_delta_add (use, NULL, cp, act_delta);
5097169689Skan
5098169689Skan      if (act_cost < best_cost)
5099169689Skan	{
5100169689Skan	  best_cost = act_cost;
5101169689Skan
5102169689Skan	  iv_ca_delta_free (&best_delta);
5103169689Skan	  best_delta = act_delta;
5104169689Skan	}
5105169689Skan      else
5106169689Skan	iv_ca_delta_free (&act_delta);
5107169689Skan    }
5108169689Skan
5109169689Skan  if (best_cost == INFTY)
5110169689Skan    {
5111169689Skan      for (i = 0; i < use->n_map_members; i++)
5112169689Skan	{
5113169689Skan	  cp = use->cost_map + i;
5114169689Skan	  cand = cp->cand;
5115169689Skan	  if (!cand)
5116169689Skan	    continue;
5117169689Skan
5118169689Skan	  /* Already tried this.  */
5119169689Skan	  if (cand->important)
5120169689Skan	    continue;
5121169689Skan
5122169689Skan	  if (iv_ca_cand_used_p (ivs, cand))
5123169689Skan	    continue;
5124169689Skan
5125169689Skan	  act_delta = NULL;
5126169689Skan	  iv_ca_set_cp (data, ivs, use, cp);
5127169689Skan	  act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
5128169689Skan	  iv_ca_set_no_cp (data, ivs, use);
5129169689Skan	  act_delta = iv_ca_delta_add (use, iv_ca_cand_for_use (ivs, use),
5130169689Skan				       cp, act_delta);
5131169689Skan
5132169689Skan	  if (act_cost < best_cost)
5133169689Skan	    {
5134169689Skan	      best_cost = act_cost;
5135169689Skan
5136169689Skan	      if (best_delta)
5137169689Skan		iv_ca_delta_free (&best_delta);
5138169689Skan	      best_delta = act_delta;
5139169689Skan	    }
5140169689Skan	  else
5141169689Skan	    iv_ca_delta_free (&act_delta);
5142169689Skan	}
5143169689Skan    }
5144169689Skan
5145169689Skan  iv_ca_delta_commit (data, ivs, best_delta, true);
5146169689Skan  iv_ca_delta_free (&best_delta);
5147169689Skan
5148169689Skan  return (best_cost != INFTY);
5149169689Skan}
5150169689Skan
5151169689Skan/* Finds an initial assignment of candidates to uses.  */
5152169689Skan
5153169689Skanstatic struct iv_ca *
5154169689Skanget_initial_solution (struct ivopts_data *data)
5155169689Skan{
5156169689Skan  struct iv_ca *ivs = iv_ca_new (data);
5157169689Skan  unsigned i;
5158169689Skan
5159169689Skan  for (i = 0; i < n_iv_uses (data); i++)
5160169689Skan    if (!try_add_cand_for (data, ivs, iv_use (data, i)))
5161169689Skan      {
5162169689Skan	iv_ca_free (&ivs);
5163169689Skan	return NULL;
5164169689Skan      }
5165169689Skan
5166169689Skan  return ivs;
5167169689Skan}
5168169689Skan
5169169689Skan/* Tries to improve set of induction variables IVS.  */
5170169689Skan
5171169689Skanstatic bool
5172169689Skantry_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs)
5173169689Skan{
5174169689Skan  unsigned i, acost, best_cost = iv_ca_cost (ivs), n_ivs;
5175169689Skan  struct iv_ca_delta *best_delta = NULL, *act_delta, *tmp_delta;
5176169689Skan  struct iv_cand *cand;
5177169689Skan
5178169689Skan  /* Try extending the set of induction variables by one.  */
5179169689Skan  for (i = 0; i < n_iv_cands (data); i++)
5180169689Skan    {
5181169689Skan      cand = iv_cand (data, i);
5182169689Skan
5183169689Skan      if (iv_ca_cand_used_p (ivs, cand))
5184169689Skan	continue;
5185169689Skan
5186169689Skan      acost = iv_ca_extend (data, ivs, cand, &act_delta, &n_ivs);
5187169689Skan      if (!act_delta)
5188169689Skan	continue;
5189169689Skan
5190169689Skan      /* If we successfully added the candidate and the set is small enough,
5191169689Skan	 try optimizing it by removing other candidates.  */
5192169689Skan      if (n_ivs <= ALWAYS_PRUNE_CAND_SET_BOUND)
5193169689Skan      	{
5194169689Skan	  iv_ca_delta_commit (data, ivs, act_delta, true);
5195169689Skan	  acost = iv_ca_prune (data, ivs, cand, &tmp_delta);
5196169689Skan	  iv_ca_delta_commit (data, ivs, act_delta, false);
5197169689Skan	  act_delta = iv_ca_delta_join (act_delta, tmp_delta);
5198169689Skan	}
5199169689Skan
5200169689Skan      if (acost < best_cost)
5201169689Skan	{
5202169689Skan	  best_cost = acost;
5203169689Skan	  iv_ca_delta_free (&best_delta);
5204169689Skan	  best_delta = act_delta;
5205169689Skan	}
5206169689Skan      else
5207169689Skan	iv_ca_delta_free (&act_delta);
5208169689Skan    }
5209169689Skan
5210169689Skan  if (!best_delta)
5211169689Skan    {
5212169689Skan      /* Try removing the candidates from the set instead.  */
5213169689Skan      best_cost = iv_ca_prune (data, ivs, NULL, &best_delta);
5214169689Skan
5215169689Skan      /* Nothing more we can do.  */
5216169689Skan      if (!best_delta)
5217169689Skan	return false;
5218169689Skan    }
5219169689Skan
5220169689Skan  iv_ca_delta_commit (data, ivs, best_delta, true);
5221169689Skan  gcc_assert (best_cost == iv_ca_cost (ivs));
5222169689Skan  iv_ca_delta_free (&best_delta);
5223169689Skan  return true;
5224169689Skan}
5225169689Skan
5226169689Skan/* Attempts to find the optimal set of induction variables.  We do simple
5227169689Skan   greedy heuristic -- we try to replace at most one candidate in the selected
5228169689Skan   solution and remove the unused ivs while this improves the cost.  */
5229169689Skan
5230169689Skanstatic struct iv_ca *
5231169689Skanfind_optimal_iv_set (struct ivopts_data *data)
5232169689Skan{
5233169689Skan  unsigned i;
5234169689Skan  struct iv_ca *set;
5235169689Skan  struct iv_use *use;
5236169689Skan
5237169689Skan  /* Get the initial solution.  */
5238169689Skan  set = get_initial_solution (data);
5239169689Skan  if (!set)
5240169689Skan    {
5241169689Skan      if (dump_file && (dump_flags & TDF_DETAILS))
5242169689Skan	fprintf (dump_file, "Unable to substitute for ivs, failed.\n");
5243169689Skan      return NULL;
5244169689Skan    }
5245169689Skan
5246169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
5247169689Skan    {
5248169689Skan      fprintf (dump_file, "Initial set of candidates:\n");
5249169689Skan      iv_ca_dump (data, dump_file, set);
5250169689Skan    }
5251169689Skan
5252169689Skan  while (try_improve_iv_set (data, set))
5253169689Skan    {
5254169689Skan      if (dump_file && (dump_flags & TDF_DETAILS))
5255169689Skan	{
5256169689Skan	  fprintf (dump_file, "Improved to:\n");
5257169689Skan	  iv_ca_dump (data, dump_file, set);
5258169689Skan	}
5259169689Skan    }
5260169689Skan
5261169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
5262169689Skan    fprintf (dump_file, "Final cost %d\n\n", iv_ca_cost (set));
5263169689Skan
5264169689Skan  for (i = 0; i < n_iv_uses (data); i++)
5265169689Skan    {
5266169689Skan      use = iv_use (data, i);
5267169689Skan      use->selected = iv_ca_cand_for_use (set, use)->cand;
5268169689Skan    }
5269169689Skan
5270169689Skan  return set;
5271169689Skan}
5272169689Skan
5273169689Skan/* Creates a new induction variable corresponding to CAND.  */
5274169689Skan
5275169689Skanstatic void
5276169689Skancreate_new_iv (struct ivopts_data *data, struct iv_cand *cand)
5277169689Skan{
5278169689Skan  block_stmt_iterator incr_pos;
5279169689Skan  tree base;
5280169689Skan  bool after = false;
5281169689Skan
5282169689Skan  if (!cand->iv)
5283169689Skan    return;
5284169689Skan
5285169689Skan  switch (cand->pos)
5286169689Skan    {
5287169689Skan    case IP_NORMAL:
5288169689Skan      incr_pos = bsi_last (ip_normal_pos (data->current_loop));
5289169689Skan      break;
5290169689Skan
5291169689Skan    case IP_END:
5292169689Skan      incr_pos = bsi_last (ip_end_pos (data->current_loop));
5293169689Skan      after = true;
5294169689Skan      break;
5295169689Skan
5296169689Skan    case IP_ORIGINAL:
5297169689Skan      /* Mark that the iv is preserved.  */
5298169689Skan      name_info (data, cand->var_before)->preserve_biv = true;
5299169689Skan      name_info (data, cand->var_after)->preserve_biv = true;
5300169689Skan
5301169689Skan      /* Rewrite the increment so that it uses var_before directly.  */
5302169689Skan      find_interesting_uses_op (data, cand->var_after)->selected = cand;
5303169689Skan
5304169689Skan      return;
5305169689Skan    }
5306169689Skan
5307169689Skan  gimple_add_tmp_var (cand->var_before);
5308169689Skan  add_referenced_var (cand->var_before);
5309169689Skan
5310169689Skan  base = unshare_expr (cand->iv->base);
5311169689Skan
5312169689Skan  create_iv (base, unshare_expr (cand->iv->step),
5313169689Skan	     cand->var_before, data->current_loop,
5314169689Skan	     &incr_pos, after, &cand->var_before, &cand->var_after);
5315169689Skan}
5316169689Skan
5317169689Skan/* Creates new induction variables described in SET.  */
5318169689Skan
5319169689Skanstatic void
5320169689Skancreate_new_ivs (struct ivopts_data *data, struct iv_ca *set)
5321169689Skan{
5322169689Skan  unsigned i;
5323169689Skan  struct iv_cand *cand;
5324169689Skan  bitmap_iterator bi;
5325169689Skan
5326169689Skan  EXECUTE_IF_SET_IN_BITMAP (set->cands, 0, i, bi)
5327169689Skan    {
5328169689Skan      cand = iv_cand (data, i);
5329169689Skan      create_new_iv (data, cand);
5330169689Skan    }
5331169689Skan}
5332169689Skan
5333169689Skan/* Removes statement STMT (real or a phi node).  If INCLUDING_DEFINED_NAME
5334169689Skan   is true, remove also the ssa name defined by the statement.  */
5335169689Skan
5336169689Skanstatic void
5337169689Skanremove_statement (tree stmt, bool including_defined_name)
5338169689Skan{
5339169689Skan  if (TREE_CODE (stmt) == PHI_NODE)
5340169689Skan    {
5341169689Skan      if (!including_defined_name)
5342169689Skan	{
5343169689Skan	  /* Prevent the ssa name defined by the statement from being removed.  */
5344169689Skan	  SET_PHI_RESULT (stmt, NULL);
5345169689Skan	}
5346169689Skan      remove_phi_node (stmt, NULL_TREE);
5347169689Skan    }
5348169689Skan  else
5349169689Skan    {
5350169689Skan      block_stmt_iterator bsi = bsi_for_stmt (stmt);
5351169689Skan
5352169689Skan      bsi_remove (&bsi, true);
5353169689Skan    }
5354169689Skan}
5355169689Skan
5356169689Skan/* Rewrites USE (definition of iv used in a nonlinear expression)
5357169689Skan   using candidate CAND.  */
5358169689Skan
5359169689Skanstatic void
5360169689Skanrewrite_use_nonlinear_expr (struct ivopts_data *data,
5361169689Skan			    struct iv_use *use, struct iv_cand *cand)
5362169689Skan{
5363169689Skan  tree comp;
5364169689Skan  tree op, stmts, tgt, ass;
5365169689Skan  block_stmt_iterator bsi, pbsi;
5366169689Skan
5367169689Skan  /* An important special case -- if we are asked to express value of
5368169689Skan     the original iv by itself, just exit; there is no need to
5369169689Skan     introduce a new computation (that might also need casting the
5370169689Skan     variable to unsigned and back).  */
5371169689Skan  if (cand->pos == IP_ORIGINAL
5372169689Skan      && cand->incremented_at == use->stmt)
5373169689Skan    {
5374169689Skan      tree step, ctype, utype;
5375169689Skan      enum tree_code incr_code = PLUS_EXPR;
5376169689Skan
5377169689Skan      gcc_assert (TREE_CODE (use->stmt) == MODIFY_EXPR);
5378169689Skan      gcc_assert (TREE_OPERAND (use->stmt, 0) == cand->var_after);
5379169689Skan
5380169689Skan      step = cand->iv->step;
5381169689Skan      ctype = TREE_TYPE (step);
5382169689Skan      utype = TREE_TYPE (cand->var_after);
5383169689Skan      if (TREE_CODE (step) == NEGATE_EXPR)
5384169689Skan	{
5385169689Skan	  incr_code = MINUS_EXPR;
5386169689Skan	  step = TREE_OPERAND (step, 0);
5387169689Skan	}
5388169689Skan
5389169689Skan      /* Check whether we may leave the computation unchanged.
5390169689Skan	 This is the case only if it does not rely on other
5391169689Skan	 computations in the loop -- otherwise, the computation
5392169689Skan	 we rely upon may be removed in remove_unused_ivs,
5393169689Skan	 thus leading to ICE.  */
5394169689Skan      op = TREE_OPERAND (use->stmt, 1);
5395169689Skan      if (TREE_CODE (op) == PLUS_EXPR
5396169689Skan	  || TREE_CODE (op) == MINUS_EXPR)
5397169689Skan	{
5398169689Skan	  if (TREE_OPERAND (op, 0) == cand->var_before)
5399169689Skan	    op = TREE_OPERAND (op, 1);
5400169689Skan	  else if (TREE_CODE (op) == PLUS_EXPR
5401169689Skan		   && TREE_OPERAND (op, 1) == cand->var_before)
5402169689Skan	    op = TREE_OPERAND (op, 0);
5403169689Skan	  else
5404169689Skan	    op = NULL_TREE;
5405169689Skan	}
5406169689Skan      else
5407169689Skan	op = NULL_TREE;
5408169689Skan
5409169689Skan      if (op
5410169689Skan	  && (TREE_CODE (op) == INTEGER_CST
5411169689Skan	      || operand_equal_p (op, step, 0)))
5412169689Skan	return;
5413169689Skan
5414169689Skan      /* Otherwise, add the necessary computations to express
5415169689Skan	 the iv.  */
5416169689Skan      op = fold_convert (ctype, cand->var_before);
5417169689Skan      comp = fold_convert (utype,
5418169689Skan			   build2 (incr_code, ctype, op,
5419169689Skan				   unshare_expr (step)));
5420169689Skan    }
5421169689Skan  else
5422169689Skan    comp = get_computation (data->current_loop, use, cand);
5423169689Skan
5424169689Skan  switch (TREE_CODE (use->stmt))
5425169689Skan    {
5426169689Skan    case PHI_NODE:
5427169689Skan      tgt = PHI_RESULT (use->stmt);
5428169689Skan
5429169689Skan      /* If we should keep the biv, do not replace it.  */
5430169689Skan      if (name_info (data, tgt)->preserve_biv)
5431169689Skan	return;
5432169689Skan
5433169689Skan      pbsi = bsi = bsi_start (bb_for_stmt (use->stmt));
5434169689Skan      while (!bsi_end_p (pbsi)
5435169689Skan	     && TREE_CODE (bsi_stmt (pbsi)) == LABEL_EXPR)
5436169689Skan	{
5437169689Skan	  bsi = pbsi;
5438169689Skan	  bsi_next (&pbsi);
5439169689Skan	}
5440169689Skan      break;
5441169689Skan
5442169689Skan    case MODIFY_EXPR:
5443169689Skan      tgt = TREE_OPERAND (use->stmt, 0);
5444169689Skan      bsi = bsi_for_stmt (use->stmt);
5445169689Skan      break;
5446169689Skan
5447169689Skan    default:
5448169689Skan      gcc_unreachable ();
5449169689Skan    }
5450169689Skan
5451169689Skan  op = force_gimple_operand (comp, &stmts, false, SSA_NAME_VAR (tgt));
5452169689Skan
5453169689Skan  if (TREE_CODE (use->stmt) == PHI_NODE)
5454169689Skan    {
5455169689Skan      if (stmts)
5456169689Skan	bsi_insert_after (&bsi, stmts, BSI_CONTINUE_LINKING);
5457169689Skan      ass = build2 (MODIFY_EXPR, TREE_TYPE (tgt), tgt, op);
5458169689Skan      bsi_insert_after (&bsi, ass, BSI_NEW_STMT);
5459169689Skan      remove_statement (use->stmt, false);
5460169689Skan      SSA_NAME_DEF_STMT (tgt) = ass;
5461169689Skan    }
5462169689Skan  else
5463169689Skan    {
5464169689Skan      if (stmts)
5465169689Skan	bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
5466169689Skan      TREE_OPERAND (use->stmt, 1) = op;
5467169689Skan    }
5468169689Skan}
5469169689Skan
5470169689Skan/* Replaces ssa name in index IDX by its basic variable.  Callback for
5471169689Skan   for_each_index.  */
5472169689Skan
5473169689Skanstatic bool
5474169689Skanidx_remove_ssa_names (tree base, tree *idx,
5475169689Skan		      void *data ATTRIBUTE_UNUSED)
5476169689Skan{
5477169689Skan  tree *op;
5478169689Skan
5479169689Skan  if (TREE_CODE (*idx) == SSA_NAME)
5480169689Skan    *idx = SSA_NAME_VAR (*idx);
5481169689Skan
5482169689Skan  if (TREE_CODE (base) == ARRAY_REF)
5483169689Skan    {
5484169689Skan      op = &TREE_OPERAND (base, 2);
5485169689Skan      if (*op
5486169689Skan	  && TREE_CODE (*op) == SSA_NAME)
5487169689Skan	*op = SSA_NAME_VAR (*op);
5488169689Skan      op = &TREE_OPERAND (base, 3);
5489169689Skan      if (*op
5490169689Skan	  && TREE_CODE (*op) == SSA_NAME)
5491169689Skan	*op = SSA_NAME_VAR (*op);
5492169689Skan    }
5493169689Skan
5494169689Skan  return true;
5495169689Skan}
5496169689Skan
5497169689Skan/* Unshares REF and replaces ssa names inside it by their basic variables.  */
5498169689Skan
5499169689Skanstatic tree
5500169689Skanunshare_and_remove_ssa_names (tree ref)
5501169689Skan{
5502169689Skan  ref = unshare_expr (ref);
5503169689Skan  for_each_index (&ref, idx_remove_ssa_names, NULL);
5504169689Skan
5505169689Skan  return ref;
5506169689Skan}
5507169689Skan
5508169689Skan/* Extract the alias analysis info for the memory reference REF.  There are
5509169689Skan   several ways how this information may be stored and what precisely is
5510169689Skan   its semantics depending on the type of the reference, but there always is
5511169689Skan   somewhere hidden one _DECL node that is used to determine the set of
5512169689Skan   virtual operands for the reference.  The code below deciphers this jungle
5513169689Skan   and extracts this single useful piece of information.  */
5514169689Skan
5515169689Skanstatic tree
5516169689Skanget_ref_tag (tree ref, tree orig)
5517169689Skan{
5518169689Skan  tree var = get_base_address (ref);
5519169689Skan  tree aref = NULL_TREE, tag, sv;
5520169689Skan  HOST_WIDE_INT offset, size, maxsize;
5521169689Skan
5522169689Skan  for (sv = orig; handled_component_p (sv); sv = TREE_OPERAND (sv, 0))
5523169689Skan    {
5524169689Skan      aref = get_ref_base_and_extent (sv, &offset, &size, &maxsize);
5525169689Skan      if (ref)
5526169689Skan	break;
5527169689Skan    }
5528169689Skan
5529169689Skan  if (aref && SSA_VAR_P (aref) && get_subvars_for_var (aref))
5530169689Skan    return unshare_expr (sv);
5531169689Skan
5532169689Skan  if (!var)
5533169689Skan    return NULL_TREE;
5534169689Skan
5535169689Skan  if (TREE_CODE (var) == INDIRECT_REF)
5536169689Skan    {
5537169689Skan      /* If the base is a dereference of a pointer, first check its name memory
5538169689Skan	 tag.  If it does not have one, use its symbol memory tag.  */
5539169689Skan      var = TREE_OPERAND (var, 0);
5540169689Skan      if (TREE_CODE (var) != SSA_NAME)
5541169689Skan	return NULL_TREE;
5542169689Skan
5543169689Skan      if (SSA_NAME_PTR_INFO (var))
5544169689Skan	{
5545169689Skan	  tag = SSA_NAME_PTR_INFO (var)->name_mem_tag;
5546169689Skan	  if (tag)
5547169689Skan	    return tag;
5548169689Skan	}
5549169689Skan
5550169689Skan      var = SSA_NAME_VAR (var);
5551169689Skan      tag = var_ann (var)->symbol_mem_tag;
5552169689Skan      gcc_assert (tag != NULL_TREE);
5553169689Skan      return tag;
5554169689Skan    }
5555169689Skan  else
5556169689Skan    {
5557169689Skan      if (!DECL_P (var))
5558169689Skan	return NULL_TREE;
5559169689Skan
5560169689Skan      tag = var_ann (var)->symbol_mem_tag;
5561169689Skan      if (tag)
5562169689Skan	return tag;
5563169689Skan
5564169689Skan      return var;
5565169689Skan    }
5566169689Skan}
5567169689Skan
5568169689Skan/* Copies the reference information from OLD_REF to NEW_REF.  */
5569169689Skan
5570169689Skanstatic void
5571169689Skancopy_ref_info (tree new_ref, tree old_ref)
5572169689Skan{
5573169689Skan  if (TREE_CODE (old_ref) == TARGET_MEM_REF)
5574169689Skan    copy_mem_ref_info (new_ref, old_ref);
5575169689Skan  else
5576169689Skan    {
5577169689Skan      TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
5578169689Skan      TMR_TAG (new_ref) = get_ref_tag (old_ref, TMR_ORIGINAL (new_ref));
5579169689Skan    }
5580169689Skan}
5581169689Skan
5582169689Skan/* Rewrites USE (address that is an iv) using candidate CAND.  */
5583169689Skan
5584169689Skanstatic void
5585169689Skanrewrite_use_address (struct ivopts_data *data,
5586169689Skan		     struct iv_use *use, struct iv_cand *cand)
5587169689Skan{
5588169689Skan  struct affine_tree_combination aff;
5589169689Skan  block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
5590169689Skan  tree ref;
5591169689Skan
5592169689Skan  get_computation_aff (data->current_loop, use, cand, use->stmt, &aff);
5593169689Skan  unshare_aff_combination (&aff);
5594169689Skan
5595169689Skan  ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff);
5596169689Skan  copy_ref_info (ref, *use->op_p);
5597169689Skan  *use->op_p = ref;
5598169689Skan}
5599169689Skan
5600169689Skan/* Rewrites USE (the condition such that one of the arguments is an iv) using
5601169689Skan   candidate CAND.  */
5602169689Skan
5603169689Skanstatic void
5604169689Skanrewrite_use_compare (struct ivopts_data *data,
5605169689Skan		     struct iv_use *use, struct iv_cand *cand)
5606169689Skan{
5607169689Skan  tree comp;
5608169689Skan  tree *op_p, cond, op, stmts, bound;
5609169689Skan  block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
5610169689Skan  enum tree_code compare;
5611169689Skan  struct cost_pair *cp = get_use_iv_cost (data, use, cand);
5612169689Skan
5613169689Skan  bound = cp->value;
5614169689Skan  if (bound)
5615169689Skan    {
5616169689Skan      tree var = var_at_stmt (data->current_loop, cand, use->stmt);
5617169689Skan      tree var_type = TREE_TYPE (var);
5618169689Skan
5619169689Skan      compare = iv_elimination_compare (data, use);
5620169689Skan      bound = fold_convert (var_type, bound);
5621169689Skan      op = force_gimple_operand (unshare_expr (bound), &stmts,
5622169689Skan				 true, NULL_TREE);
5623169689Skan
5624169689Skan      if (stmts)
5625169689Skan	bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
5626169689Skan
5627169689Skan      *use->op_p = build2 (compare, boolean_type_node, var, op);
5628169689Skan      update_stmt (use->stmt);
5629169689Skan      return;
5630169689Skan    }
5631169689Skan
5632169689Skan  /* The induction variable elimination failed; just express the original
5633169689Skan     giv.  */
5634169689Skan  comp = get_computation (data->current_loop, use, cand);
5635169689Skan
5636169689Skan  cond = *use->op_p;
5637169689Skan  op_p = &TREE_OPERAND (cond, 0);
5638169689Skan  if (TREE_CODE (*op_p) != SSA_NAME
5639169689Skan      || zero_p (get_iv (data, *op_p)->step))
5640169689Skan    op_p = &TREE_OPERAND (cond, 1);
5641169689Skan
5642169689Skan  op = force_gimple_operand (comp, &stmts, true, SSA_NAME_VAR (*op_p));
5643169689Skan  if (stmts)
5644169689Skan    bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
5645169689Skan
5646169689Skan  *op_p = op;
5647169689Skan}
5648169689Skan
5649169689Skan/* Rewrites USE using candidate CAND.  */
5650169689Skan
5651169689Skanstatic void
5652169689Skanrewrite_use (struct ivopts_data *data,
5653169689Skan	     struct iv_use *use, struct iv_cand *cand)
5654169689Skan{
5655169689Skan  switch (use->type)
5656169689Skan    {
5657169689Skan      case USE_NONLINEAR_EXPR:
5658169689Skan	rewrite_use_nonlinear_expr (data, use, cand);
5659169689Skan	break;
5660169689Skan
5661169689Skan      case USE_ADDRESS:
5662169689Skan	rewrite_use_address (data, use, cand);
5663169689Skan	break;
5664169689Skan
5665169689Skan      case USE_COMPARE:
5666169689Skan	rewrite_use_compare (data, use, cand);
5667169689Skan	break;
5668169689Skan
5669169689Skan      default:
5670169689Skan	gcc_unreachable ();
5671169689Skan    }
5672169689Skan  mark_new_vars_to_rename (use->stmt);
5673169689Skan}
5674169689Skan
5675169689Skan/* Rewrite the uses using the selected induction variables.  */
5676169689Skan
5677169689Skanstatic void
5678169689Skanrewrite_uses (struct ivopts_data *data)
5679169689Skan{
5680169689Skan  unsigned i;
5681169689Skan  struct iv_cand *cand;
5682169689Skan  struct iv_use *use;
5683169689Skan
5684169689Skan  for (i = 0; i < n_iv_uses (data); i++)
5685169689Skan    {
5686169689Skan      use = iv_use (data, i);
5687169689Skan      cand = use->selected;
5688169689Skan      gcc_assert (cand);
5689169689Skan
5690169689Skan      rewrite_use (data, use, cand);
5691169689Skan    }
5692169689Skan}
5693169689Skan
5694169689Skan/* Removes the ivs that are not used after rewriting.  */
5695169689Skan
5696169689Skanstatic void
5697169689Skanremove_unused_ivs (struct ivopts_data *data)
5698169689Skan{
5699169689Skan  unsigned j;
5700169689Skan  bitmap_iterator bi;
5701169689Skan
5702169689Skan  EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
5703169689Skan    {
5704169689Skan      struct version_info *info;
5705169689Skan
5706169689Skan      info = ver_info (data, j);
5707169689Skan      if (info->iv
5708169689Skan	  && !zero_p (info->iv->step)
5709169689Skan	  && !info->inv_id
5710169689Skan	  && !info->iv->have_use_for
5711169689Skan	  && !info->preserve_biv)
5712169689Skan	remove_statement (SSA_NAME_DEF_STMT (info->iv->ssa_name), true);
5713169689Skan    }
5714169689Skan}
5715169689Skan
5716169689Skan/* Frees data allocated by the optimization of a single loop.  */
5717169689Skan
5718169689Skanstatic void
5719169689Skanfree_loop_data (struct ivopts_data *data)
5720169689Skan{
5721169689Skan  unsigned i, j;
5722169689Skan  bitmap_iterator bi;
5723169689Skan  tree obj;
5724169689Skan
5725169689Skan  htab_empty (data->niters);
5726169689Skan
5727169689Skan  EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
5728169689Skan    {
5729169689Skan      struct version_info *info;
5730169689Skan
5731169689Skan      info = ver_info (data, i);
5732169689Skan      if (info->iv)
5733169689Skan	free (info->iv);
5734169689Skan      info->iv = NULL;
5735169689Skan      info->has_nonlin_use = false;
5736169689Skan      info->preserve_biv = false;
5737169689Skan      info->inv_id = 0;
5738169689Skan    }
5739169689Skan  bitmap_clear (data->relevant);
5740169689Skan  bitmap_clear (data->important_candidates);
5741169689Skan
5742169689Skan  for (i = 0; i < n_iv_uses (data); i++)
5743169689Skan    {
5744169689Skan      struct iv_use *use = iv_use (data, i);
5745169689Skan
5746169689Skan      free (use->iv);
5747169689Skan      BITMAP_FREE (use->related_cands);
5748169689Skan      for (j = 0; j < use->n_map_members; j++)
5749169689Skan	if (use->cost_map[j].depends_on)
5750169689Skan	  BITMAP_FREE (use->cost_map[j].depends_on);
5751169689Skan      free (use->cost_map);
5752169689Skan      free (use);
5753169689Skan    }
5754169689Skan  VEC_truncate (iv_use_p, data->iv_uses, 0);
5755169689Skan
5756169689Skan  for (i = 0; i < n_iv_cands (data); i++)
5757169689Skan    {
5758169689Skan      struct iv_cand *cand = iv_cand (data, i);
5759169689Skan
5760169689Skan      if (cand->iv)
5761169689Skan	free (cand->iv);
5762169689Skan      if (cand->depends_on)
5763169689Skan	BITMAP_FREE (cand->depends_on);
5764169689Skan      free (cand);
5765169689Skan    }
5766169689Skan  VEC_truncate (iv_cand_p, data->iv_candidates, 0);
5767169689Skan
5768169689Skan  if (data->version_info_size < num_ssa_names)
5769169689Skan    {
5770169689Skan      data->version_info_size = 2 * num_ssa_names;
5771169689Skan      free (data->version_info);
5772169689Skan      data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
5773169689Skan    }
5774169689Skan
5775169689Skan  data->max_inv_id = 0;
5776169689Skan
5777169689Skan  for (i = 0; VEC_iterate (tree, decl_rtl_to_reset, i, obj); i++)
5778169689Skan    SET_DECL_RTL (obj, NULL_RTX);
5779169689Skan
5780169689Skan  VEC_truncate (tree, decl_rtl_to_reset, 0);
5781169689Skan}
5782169689Skan
5783169689Skan/* Finalizes data structures used by the iv optimization pass.  LOOPS is the
5784169689Skan   loop tree.  */
5785169689Skan
5786169689Skanstatic void
5787169689Skantree_ssa_iv_optimize_finalize (struct ivopts_data *data)
5788169689Skan{
5789169689Skan  free_loop_data (data);
5790169689Skan  free (data->version_info);
5791169689Skan  BITMAP_FREE (data->relevant);
5792169689Skan  BITMAP_FREE (data->important_candidates);
5793169689Skan  htab_delete (data->niters);
5794169689Skan
5795169689Skan  VEC_free (tree, heap, decl_rtl_to_reset);
5796169689Skan  VEC_free (iv_use_p, heap, data->iv_uses);
5797169689Skan  VEC_free (iv_cand_p, heap, data->iv_candidates);
5798169689Skan}
5799169689Skan
5800169689Skan/* Optimizes the LOOP.  Returns true if anything changed.  */
5801169689Skan
5802169689Skanstatic bool
5803169689Skantree_ssa_iv_optimize_loop (struct ivopts_data *data, struct loop *loop)
5804169689Skan{
5805169689Skan  bool changed = false;
5806169689Skan  struct iv_ca *iv_ca;
5807169689Skan  edge exit;
5808169689Skan
5809169689Skan  data->current_loop = loop;
5810169689Skan
5811169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
5812169689Skan    {
5813169689Skan      fprintf (dump_file, "Processing loop %d\n", loop->num);
5814169689Skan
5815169689Skan      exit = single_dom_exit (loop);
5816169689Skan      if (exit)
5817169689Skan	{
5818169689Skan	  fprintf (dump_file, "  single exit %d -> %d, exit condition ",
5819169689Skan		   exit->src->index, exit->dest->index);
5820169689Skan	  print_generic_expr (dump_file, last_stmt (exit->src), TDF_SLIM);
5821169689Skan	  fprintf (dump_file, "\n");
5822169689Skan	}
5823169689Skan
5824169689Skan      fprintf (dump_file, "\n");
5825169689Skan    }
5826169689Skan
5827169689Skan  /* For each ssa name determines whether it behaves as an induction variable
5828169689Skan     in some loop.  */
5829169689Skan  if (!find_induction_variables (data))
5830169689Skan    goto finish;
5831169689Skan
5832169689Skan  /* Finds interesting uses (item 1).  */
5833169689Skan  find_interesting_uses (data);
5834169689Skan  if (n_iv_uses (data) > MAX_CONSIDERED_USES)
5835169689Skan    goto finish;
5836169689Skan
5837169689Skan  /* Finds candidates for the induction variables (item 2).  */
5838169689Skan  find_iv_candidates (data);
5839169689Skan
5840169689Skan  /* Calculates the costs (item 3, part 1).  */
5841169689Skan  determine_use_iv_costs (data);
5842169689Skan  determine_iv_costs (data);
5843169689Skan  determine_set_costs (data);
5844169689Skan
5845169689Skan  /* Find the optimal set of induction variables (item 3, part 2).  */
5846169689Skan  iv_ca = find_optimal_iv_set (data);
5847169689Skan  if (!iv_ca)
5848169689Skan    goto finish;
5849169689Skan  changed = true;
5850169689Skan
5851169689Skan  /* Create the new induction variables (item 4, part 1).  */
5852169689Skan  create_new_ivs (data, iv_ca);
5853169689Skan  iv_ca_free (&iv_ca);
5854169689Skan
5855169689Skan  /* Rewrite the uses (item 4, part 2).  */
5856169689Skan  rewrite_uses (data);
5857169689Skan
5858169689Skan  /* Remove the ivs that are unused after rewriting.  */
5859169689Skan  remove_unused_ivs (data);
5860169689Skan
5861169689Skan  /* We have changed the structure of induction variables; it might happen
5862169689Skan     that definitions in the scev database refer to some of them that were
5863169689Skan     eliminated.  */
5864169689Skan  scev_reset ();
5865169689Skan
5866169689Skanfinish:
5867169689Skan  free_loop_data (data);
5868169689Skan
5869169689Skan  return changed;
5870169689Skan}
5871169689Skan
5872169689Skan/* Main entry point.  Optimizes induction variables in LOOPS.  */
5873169689Skan
5874169689Skanvoid
5875169689Skantree_ssa_iv_optimize (struct loops *loops)
5876169689Skan{
5877169689Skan  struct loop *loop;
5878169689Skan  struct ivopts_data data;
5879169689Skan
5880169689Skan  tree_ssa_iv_optimize_init (&data);
5881169689Skan
5882169689Skan  /* Optimize the loops starting with the innermost ones.  */
5883169689Skan  loop = loops->tree_root;
5884169689Skan  while (loop->inner)
5885169689Skan    loop = loop->inner;
5886169689Skan
5887169689Skan  /* Scan the loops, inner ones first.  */
5888169689Skan  while (loop != loops->tree_root)
5889169689Skan    {
5890169689Skan      if (dump_file && (dump_flags & TDF_DETAILS))
5891169689Skan	flow_loop_dump (loop, dump_file, NULL, 1);
5892169689Skan
5893169689Skan      tree_ssa_iv_optimize_loop (&data, loop);
5894169689Skan
5895169689Skan      if (loop->next)
5896169689Skan	{
5897169689Skan	  loop = loop->next;
5898169689Skan	  while (loop->inner)
5899169689Skan	    loop = loop->inner;
5900169689Skan	}
5901169689Skan      else
5902169689Skan	loop = loop->outer;
5903169689Skan    }
5904169689Skan
5905169689Skan  tree_ssa_iv_optimize_finalize (&data);
5906169689Skan}
5907