1 /* Induction variable optimizations.
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
21 /* This pass tries to find the optimal set of induction variables for the loop.
22 It optimizes just the basic linear induction variables (although adding
23 support for other types should not be too hard). It includes the
24 optimizations commonly known as strength reduction, induction variable
25 coalescing and induction variable elimination. It does it in the
28 1) The interesting uses of induction variables are found. This includes
30 -- uses of induction variables in non-linear expressions
31 -- addresses of arrays
32 -- comparisons of induction variables
34 2) Candidates for the induction variables are found. This includes
36 -- old induction variables
37 -- the variables defined by expressions derived from the "interesting
40 3) The optimal (w.r. to a cost function) set of variables is chosen. The
41 cost function assigns a cost to sets of induction variables and consists
44 -- The use costs. Each of the interesting uses chooses the best induction
45 variable in the set and adds its cost to the sum. The cost reflects
46 the time spent on modifying the induction variables value to be usable
47 for the given purpose (adding base and offset for arrays, etc.).
48 -- The variable costs. Each of the variables has a cost assigned that
49 reflects the costs associated with incrementing the value of the
50 variable. The original variables are somewhat preferred.
51 -- The set cost. Depending on the size of the set, extra cost may be
52 added to reflect register pressure.
54 All the costs are defined in a machine-specific way, using the target
55 hooks and machine descriptions to determine them.
57 4) The trees are transformed to use the new variables, the dead code is
60 All of this is done loop by loop. Doing it globally is theoretically
61 possible, it might give a better performance and it might enable us
62 to decide costs more precisely, but getting all the interactions right
63 would be complicated. */
67 #include "coretypes.h"
72 #include "hard-reg-set.h"
73 #include "basic-block.h"
75 #include "diagnostic.h"
76 #include "tree-flow.h"
77 #include "tree-dump.h"
82 #include "tree-pass.h"
84 #include "insn-config.h"
87 #include "tree-chrec.h"
88 #include "tree-scalar-evolution.h"
91 #include "langhooks.h"
93 /* The infinite cost. */
94 #define INFTY 10000000
96 /* The expected number of loop iterations. TODO -- use profiling instead of
98 #define AVG_LOOP_NITER(LOOP) 5
101 /* Representation of the induction variable. */
104 tree base; /* Initial value of the iv. */
105 tree base_object; /* A memory object to that the induction variable points. */
106 tree step; /* Step of the iv (constant only). */
107 tree ssa_name; /* The ssa name with the value. */
108 bool biv_p; /* Is it a biv? */
109 bool have_use_for; /* Do we already have a use for it? */
110 unsigned use_id; /* The identifier in the use if it is the case. */
113 /* Per-ssa version information (induction variable descriptions, etc.). */
116 tree name; /* The ssa name. */
117 struct iv *iv; /* Induction variable description. */
118 bool has_nonlin_use; /* For a loop-level invariant, whether it is used in
119 an expression that is not an induction variable. */
120 unsigned inv_id; /* Id of an invariant. */
121 bool preserve_biv; /* For the original biv, whether to preserve it. */
127 USE_NONLINEAR_EXPR, /* Use in a nonlinear expression. */
128 USE_ADDRESS, /* Use in an address. */
129 USE_COMPARE /* Use is a compare. */
132 /* The candidate - cost pair. */
135 struct iv_cand *cand; /* The candidate. */
136 unsigned cost; /* The cost. */
137 bitmap depends_on; /* The list of invariants that have to be
139 tree value; /* For final value elimination, the expression for
140 the final value of the iv. For iv elimination,
141 the new bound to compare with. */
147 unsigned id; /* The id of the use. */
148 enum use_type type; /* Type of the use. */
149 struct iv *iv; /* The induction variable it is based on. */
150 tree stmt; /* Statement in that it occurs. */
151 tree *op_p; /* The place where it occurs. */
152 bitmap related_cands; /* The set of "related" iv candidates, plus the common
155 unsigned n_map_members; /* Number of candidates in the cost_map list. */
156 struct cost_pair *cost_map;
157 /* The costs wrto the iv candidates. */
159 struct iv_cand *selected;
160 /* The selected candidate. */
163 /* The position where the iv is computed. */
166 IP_NORMAL, /* At the end, just before the exit condition. */
167 IP_END, /* At the end of the latch block. */
168 IP_ORIGINAL /* The original biv. */
171 /* The induction variable candidate. */
174 unsigned id; /* The number of the candidate. */
175 bool important; /* Whether this is an "important" candidate, i.e. such
176 that it should be considered by all uses. */
177 enum iv_position pos; /* Where it is computed. */
178 tree incremented_at; /* For original biv, the statement where it is
180 tree var_before; /* The variable used for it before increment. */
181 tree var_after; /* The variable used for it after increment. */
182 struct iv *iv; /* The value of the candidate. NULL for
183 "pseudocandidate" used to indicate the possibility
184 to replace the final value of an iv by direct
185 computation of the value. */
186 unsigned cost; /* Cost of the candidate. */
187 bitmap depends_on; /* The list of invariants that are used in step of the
191 /* The data used by the induction variable optimizations. */
193 typedef struct iv_use *iv_use_p;
195 DEF_VEC_ALLOC_P(iv_use_p,heap);
197 typedef struct iv_cand *iv_cand_p;
198 DEF_VEC_P(iv_cand_p);
199 DEF_VEC_ALLOC_P(iv_cand_p,heap);
203 /* The currently optimized loop. */
204 struct loop *current_loop;
206 /* Number of registers used in it. */
209 /* Numbers of iterations for all exits of the current loop. */
212 /* The size of version_info array allocated. */
213 unsigned version_info_size;
215 /* The array of information for the ssa names. */
216 struct version_info *version_info;
218 /* The bitmap of indices in version_info whose value was changed. */
221 /* The maximum invariant id. */
224 /* The uses of induction variables. */
225 VEC(iv_use_p,heap) *iv_uses;
227 /* The candidates. */
228 VEC(iv_cand_p,heap) *iv_candidates;
230 /* A bitmap of important candidates. */
231 bitmap important_candidates;
233 /* Whether to consider just related and important candidates when replacing a
235 bool consider_all_candidates;
238 /* An assignment of iv candidates to uses. */
242 /* The number of uses covered by the assignment. */
245 /* Number of uses that cannot be expressed by the candidates in the set. */
248 /* Candidate assigned to a use, together with the related costs. */
249 struct cost_pair **cand_for_use;
251 /* Number of times each candidate is used. */
252 unsigned *n_cand_uses;
254 /* The candidates used. */
257 /* The number of candidates in the set. */
260 /* Total number of registers needed. */
263 /* Total cost of expressing uses. */
264 unsigned cand_use_cost;
266 /* Total cost of candidates. */
269 /* Number of times each invariant is used. */
270 unsigned *n_invariant_uses;
272 /* Total cost of the assignment. */
276 /* Difference of two iv candidate assignments. */
283 /* An old assignment (for rollback purposes). */
284 struct cost_pair *old_cp;
286 /* A new assignment. */
287 struct cost_pair *new_cp;
289 /* Next change in the list. */
290 struct iv_ca_delta *next_change;
293 /* Bound on number of candidates below that all candidates are considered. */
295 #define CONSIDER_ALL_CANDIDATES_BOUND \
296 ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
298 /* If there are more iv occurrences, we just give up (it is quite unlikely that
299 optimizing such a loop would help, and it would take ages). */
301 #define MAX_CONSIDERED_USES \
302 ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
304 /* If there are at most this number of ivs in the set, try removing unnecessary
305 ivs from the set always. */
307 #define ALWAYS_PRUNE_CAND_SET_BOUND \
308 ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
310 /* The list of trees for that the decl_rtl field must be reset is stored
313 static VEC(tree,heap) *decl_rtl_to_reset;
315 /* Number of uses recorded in DATA. */
317 static inline unsigned
318 n_iv_uses (struct ivopts_data *data)
320 return VEC_length (iv_use_p, data->iv_uses);
323 /* Ith use recorded in DATA. */
325 static inline struct iv_use *
326 iv_use (struct ivopts_data *data, unsigned i)
328 return VEC_index (iv_use_p, data->iv_uses, i);
331 /* Number of candidates recorded in DATA. */
333 static inline unsigned
334 n_iv_cands (struct ivopts_data *data)
336 return VEC_length (iv_cand_p, data->iv_candidates);
339 /* Ith candidate recorded in DATA. */
341 static inline struct iv_cand *
342 iv_cand (struct ivopts_data *data, unsigned i)
344 return VEC_index (iv_cand_p, data->iv_candidates, i);
347 /* The single loop exit if it dominates the latch, NULL otherwise. */
350 single_dom_exit (struct loop *loop)
352 edge exit = loop->single_exit;
357 if (!just_once_each_iteration_p (loop, exit->src))
363 /* Dumps information about the induction variable IV to FILE. */
365 extern void dump_iv (FILE *, struct iv *);
367 dump_iv (FILE *file, struct iv *iv)
371 fprintf (file, "ssa name ");
372 print_generic_expr (file, iv->ssa_name, TDF_SLIM);
373 fprintf (file, "\n");
376 fprintf (file, " type ");
377 print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
378 fprintf (file, "\n");
382 fprintf (file, " base ");
383 print_generic_expr (file, iv->base, TDF_SLIM);
384 fprintf (file, "\n");
386 fprintf (file, " step ");
387 print_generic_expr (file, iv->step, TDF_SLIM);
388 fprintf (file, "\n");
392 fprintf (file, " invariant ");
393 print_generic_expr (file, iv->base, TDF_SLIM);
394 fprintf (file, "\n");
399 fprintf (file, " base object ");
400 print_generic_expr (file, iv->base_object, TDF_SLIM);
401 fprintf (file, "\n");
405 fprintf (file, " is a biv\n");
408 /* Dumps information about the USE to FILE. */
410 extern void dump_use (FILE *, struct iv_use *);
412 dump_use (FILE *file, struct iv_use *use)
414 fprintf (file, "use %d\n", use->id);
418 case USE_NONLINEAR_EXPR:
419 fprintf (file, " generic\n");
423 fprintf (file, " address\n");
427 fprintf (file, " compare\n");
434 fprintf (file, " in statement ");
435 print_generic_expr (file, use->stmt, TDF_SLIM);
436 fprintf (file, "\n");
438 fprintf (file, " at position ");
440 print_generic_expr (file, *use->op_p, TDF_SLIM);
441 fprintf (file, "\n");
443 dump_iv (file, use->iv);
445 if (use->related_cands)
447 fprintf (file, " related candidates ");
448 dump_bitmap (file, use->related_cands);
452 /* Dumps information about the uses to FILE. */
454 extern void dump_uses (FILE *, struct ivopts_data *);
456 dump_uses (FILE *file, struct ivopts_data *data)
461 for (i = 0; i < n_iv_uses (data); i++)
463 use = iv_use (data, i);
465 dump_use (file, use);
466 fprintf (file, "\n");
470 /* Dumps information about induction variable candidate CAND to FILE. */
472 extern void dump_cand (FILE *, struct iv_cand *);
474 dump_cand (FILE *file, struct iv_cand *cand)
476 struct iv *iv = cand->iv;
478 fprintf (file, "candidate %d%s\n",
479 cand->id, cand->important ? " (important)" : "");
481 if (cand->depends_on)
483 fprintf (file, " depends on ");
484 dump_bitmap (file, cand->depends_on);
489 fprintf (file, " final value replacement\n");
496 fprintf (file, " incremented before exit test\n");
500 fprintf (file, " incremented at end\n");
504 fprintf (file, " original biv\n");
511 /* Returns the info for ssa version VER. */
513 static inline struct version_info *
514 ver_info (struct ivopts_data *data, unsigned ver)
516 return data->version_info + ver;
519 /* Returns the info for ssa name NAME. */
521 static inline struct version_info *
522 name_info (struct ivopts_data *data, tree name)
524 return ver_info (data, SSA_NAME_VERSION (name));
527 /* Checks whether there exists number X such that X * B = A, counting modulo
531 divide (unsigned bits, unsigned HOST_WIDE_INT a, unsigned HOST_WIDE_INT b,
534 unsigned HOST_WIDE_INT mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
535 unsigned HOST_WIDE_INT inv, ex, val;
541 /* First divide the whole equation by 2 as long as possible. */
542 while (!(a & 1) && !(b & 1))
552 /* If b is still even, a is odd and there is no such x. */
556 /* Find the inverse of b. We compute it as
557 b^(2^(bits - 1) - 1) (mod 2^bits). */
560 for (i = 0; i < bits - 1; i++)
562 inv = (inv * ex) & mask;
563 ex = (ex * ex) & mask;
566 val = (a * inv) & mask;
568 gcc_assert (((val * b) & mask) == a);
570 if ((val >> (bits - 1)) & 1)
578 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
582 stmt_after_ip_normal_pos (struct loop *loop, tree stmt)
584 basic_block bb = ip_normal_pos (loop), sbb = bb_for_stmt (stmt);
588 if (sbb == loop->latch)
594 return stmt == last_stmt (bb);
597 /* Returns true if STMT if after the place where the original induction
598 variable CAND is incremented. */
601 stmt_after_ip_original_pos (struct iv_cand *cand, tree stmt)
603 basic_block cand_bb = bb_for_stmt (cand->incremented_at);
604 basic_block stmt_bb = bb_for_stmt (stmt);
605 block_stmt_iterator bsi;
607 if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
610 if (stmt_bb != cand_bb)
613 /* Scan the block from the end, since the original ivs are usually
614 incremented at the end of the loop body. */
615 for (bsi = bsi_last (stmt_bb); ; bsi_prev (&bsi))
617 if (bsi_stmt (bsi) == cand->incremented_at)
619 if (bsi_stmt (bsi) == stmt)
624 /* Returns true if STMT if after the place where the induction variable
625 CAND is incremented in LOOP. */
628 stmt_after_increment (struct loop *loop, struct iv_cand *cand, tree stmt)
636 return stmt_after_ip_normal_pos (loop, stmt);
639 return stmt_after_ip_original_pos (cand, stmt);
646 /* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
649 abnormal_ssa_name_p (tree exp)
654 if (TREE_CODE (exp) != SSA_NAME)
657 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) != 0;
660 /* Returns false if BASE or INDEX contains a ssa name that occurs in an
661 abnormal phi node. Callback for for_each_index. */
664 idx_contains_abnormal_ssa_name_p (tree base, tree *index,
665 void *data ATTRIBUTE_UNUSED)
667 if (TREE_CODE (base) == ARRAY_REF)
669 if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
671 if (abnormal_ssa_name_p (TREE_OPERAND (base, 3)))
675 return !abnormal_ssa_name_p (*index);
678 /* Returns true if EXPR contains a ssa name that occurs in an
679 abnormal phi node. */
682 contains_abnormal_ssa_name_p (tree expr)
685 enum tree_code_class class;
690 code = TREE_CODE (expr);
691 class = TREE_CODE_CLASS (code);
693 if (code == SSA_NAME)
694 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
696 if (code == INTEGER_CST
697 || is_gimple_min_invariant (expr))
700 if (code == ADDR_EXPR)
701 return !for_each_index (&TREE_OPERAND (expr, 0),
702 idx_contains_abnormal_ssa_name_p,
709 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1)))
714 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0)))
726 /* Element of the table in that we cache the numbers of iterations obtained
727 from exits of the loop. */
731 /* The edge for that the number of iterations is cached. */
734 /* Number of iterations corresponding to this exit, or NULL if it cannot be
739 /* Hash function for nfe_cache_elt E. */
742 nfe_hash (const void *e)
744 const struct nfe_cache_elt *elt = e;
746 return htab_hash_pointer (elt->exit);
749 /* Equality function for nfe_cache_elt E1 and edge E2. */
752 nfe_eq (const void *e1, const void *e2)
754 const struct nfe_cache_elt *elt1 = e1;
756 return elt1->exit == e2;
759 /* Returns tree describing number of iterations determined from
760 EXIT of DATA->current_loop, or NULL if something goes wrong. */
763 niter_for_exit (struct ivopts_data *data, edge exit)
765 struct nfe_cache_elt *nfe_desc;
766 struct tree_niter_desc desc;
769 slot = htab_find_slot_with_hash (data->niters, exit,
770 htab_hash_pointer (exit),
775 nfe_desc = xmalloc (sizeof (struct nfe_cache_elt));
776 nfe_desc->exit = exit;
778 /* Try to determine number of iterations. We must know it
779 unconditionally (i.e., without possibility of # of iterations
780 being zero). Also, we cannot safely work with ssa names that
781 appear in phi nodes on abnormal edges, so that we do not create
782 overlapping life ranges for them (PR 27283). */
783 if (number_of_iterations_exit (data->current_loop,
785 && zero_p (desc.may_be_zero)
786 && !contains_abnormal_ssa_name_p (desc.niter))
787 nfe_desc->niter = desc.niter;
789 nfe_desc->niter = NULL_TREE;
794 return nfe_desc->niter;
797 /* Returns tree describing number of iterations determined from
798 single dominating exit of DATA->current_loop, or NULL if something
802 niter_for_single_dom_exit (struct ivopts_data *data)
804 edge exit = single_dom_exit (data->current_loop);
809 return niter_for_exit (data, exit);
812 /* Initializes data structures used by the iv optimization pass, stored
816 tree_ssa_iv_optimize_init (struct ivopts_data *data)
818 data->version_info_size = 2 * num_ssa_names;
819 data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
820 data->relevant = BITMAP_ALLOC (NULL);
821 data->important_candidates = BITMAP_ALLOC (NULL);
822 data->max_inv_id = 0;
823 data->niters = htab_create (10, nfe_hash, nfe_eq, free);
824 data->iv_uses = VEC_alloc (iv_use_p, heap, 20);
825 data->iv_candidates = VEC_alloc (iv_cand_p, heap, 20);
826 decl_rtl_to_reset = VEC_alloc (tree, heap, 20);
829 /* Returns a memory object to that EXPR points. In case we are able to
830 determine that it does not point to any such object, NULL is returned. */
833 determine_base_object (tree expr)
835 enum tree_code code = TREE_CODE (expr);
836 tree base, obj, op0, op1;
838 if (!POINTER_TYPE_P (TREE_TYPE (expr)))
847 obj = TREE_OPERAND (expr, 0);
848 base = get_base_address (obj);
853 if (TREE_CODE (base) == INDIRECT_REF)
854 return determine_base_object (TREE_OPERAND (base, 0));
856 return fold_convert (ptr_type_node,
857 build_fold_addr_expr (base));
861 op0 = determine_base_object (TREE_OPERAND (expr, 0));
862 op1 = determine_base_object (TREE_OPERAND (expr, 1));
868 return (code == PLUS_EXPR
870 : fold_build1 (NEGATE_EXPR, ptr_type_node, op1));
872 return fold_build2 (code, ptr_type_node, op0, op1);
876 return determine_base_object (TREE_OPERAND (expr, 0));
879 return fold_convert (ptr_type_node, expr);
883 /* Allocates an induction variable with given initial value BASE and step STEP
887 alloc_iv (tree base, tree step)
889 struct iv *iv = XCNEW (struct iv);
891 if (step && integer_zerop (step))
895 iv->base_object = determine_base_object (base);
898 iv->have_use_for = false;
900 iv->ssa_name = NULL_TREE;
905 /* Sets STEP and BASE for induction variable IV. */
908 set_iv (struct ivopts_data *data, tree iv, tree base, tree step)
910 struct version_info *info = name_info (data, iv);
912 gcc_assert (!info->iv);
914 bitmap_set_bit (data->relevant, SSA_NAME_VERSION (iv));
915 info->iv = alloc_iv (base, step);
916 info->iv->ssa_name = iv;
919 /* Finds induction variable declaration for VAR. */
922 get_iv (struct ivopts_data *data, tree var)
926 if (!name_info (data, var)->iv)
928 bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
931 || !flow_bb_inside_loop_p (data->current_loop, bb))
932 set_iv (data, var, var, NULL_TREE);
935 return name_info (data, var)->iv;
938 /* Determines the step of a biv defined in PHI. Returns NULL if PHI does
939 not define a simple affine biv with nonzero step. */
942 determine_biv_step (tree phi)
944 struct loop *loop = bb_for_stmt (phi)->loop_father;
945 tree name = PHI_RESULT (phi);
948 if (!is_gimple_reg (name))
951 if (!simple_iv (loop, phi, name, &iv, true))
954 return (zero_p (iv.step) ? NULL_TREE : iv.step);
957 /* Finds basic ivs. */
960 find_bivs (struct ivopts_data *data)
962 tree phi, step, type, base;
964 struct loop *loop = data->current_loop;
966 for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
968 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
971 step = determine_biv_step (phi);
975 base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
976 base = expand_simple_operations (base);
977 if (contains_abnormal_ssa_name_p (base)
978 || contains_abnormal_ssa_name_p (step))
981 type = TREE_TYPE (PHI_RESULT (phi));
982 base = fold_convert (type, base);
984 step = fold_convert (type, step);
986 set_iv (data, PHI_RESULT (phi), base, step);
993 /* Marks basic ivs. */
996 mark_bivs (struct ivopts_data *data)
999 struct iv *iv, *incr_iv;
1000 struct loop *loop = data->current_loop;
1001 basic_block incr_bb;
1003 for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
1005 iv = get_iv (data, PHI_RESULT (phi));
1009 var = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1010 incr_iv = get_iv (data, var);
1014 /* If the increment is in the subloop, ignore it. */
1015 incr_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
1016 if (incr_bb->loop_father != data->current_loop
1017 || (incr_bb->flags & BB_IRREDUCIBLE_LOOP))
1021 incr_iv->biv_p = true;
1025 /* Checks whether STMT defines a linear induction variable and stores its
1026 parameters to IV. */
1029 find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt, affine_iv *iv)
1032 struct loop *loop = data->current_loop;
1034 iv->base = NULL_TREE;
1035 iv->step = NULL_TREE;
1037 if (TREE_CODE (stmt) != MODIFY_EXPR)
1040 lhs = TREE_OPERAND (stmt, 0);
1041 if (TREE_CODE (lhs) != SSA_NAME)
1044 if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), iv, true))
1046 iv->base = expand_simple_operations (iv->base);
1048 if (contains_abnormal_ssa_name_p (iv->base)
1049 || contains_abnormal_ssa_name_p (iv->step))
1055 /* Finds general ivs in statement STMT. */
1058 find_givs_in_stmt (struct ivopts_data *data, tree stmt)
1062 if (!find_givs_in_stmt_scev (data, stmt, &iv))
1065 set_iv (data, TREE_OPERAND (stmt, 0), iv.base, iv.step);
1068 /* Finds general ivs in basic block BB. */
1071 find_givs_in_bb (struct ivopts_data *data, basic_block bb)
1073 block_stmt_iterator bsi;
1075 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1076 find_givs_in_stmt (data, bsi_stmt (bsi));
1079 /* Finds general ivs. */
1082 find_givs (struct ivopts_data *data)
1084 struct loop *loop = data->current_loop;
1085 basic_block *body = get_loop_body_in_dom_order (loop);
1088 for (i = 0; i < loop->num_nodes; i++)
1089 find_givs_in_bb (data, body[i]);
1093 /* For each ssa name defined in LOOP determines whether it is an induction
1094 variable and if so, its initial value and step. */
1097 find_induction_variables (struct ivopts_data *data)
1102 if (!find_bivs (data))
1108 if (dump_file && (dump_flags & TDF_DETAILS))
1110 tree niter = niter_for_single_dom_exit (data);
1114 fprintf (dump_file, " number of iterations ");
1115 print_generic_expr (dump_file, niter, TDF_SLIM);
1116 fprintf (dump_file, "\n\n");
1119 fprintf (dump_file, "Induction variables:\n\n");
1121 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
1123 if (ver_info (data, i)->iv)
1124 dump_iv (dump_file, ver_info (data, i)->iv);
1131 /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV. */
1133 static struct iv_use *
1134 record_use (struct ivopts_data *data, tree *use_p, struct iv *iv,
1135 tree stmt, enum use_type use_type)
1137 struct iv_use *use = XCNEW (struct iv_use);
1139 use->id = n_iv_uses (data);
1140 use->type = use_type;
1144 use->related_cands = BITMAP_ALLOC (NULL);
1146 /* To avoid showing ssa name in the dumps, if it was not reset by the
1148 iv->ssa_name = NULL_TREE;
1150 if (dump_file && (dump_flags & TDF_DETAILS))
1151 dump_use (dump_file, use);
1153 VEC_safe_push (iv_use_p, heap, data->iv_uses, use);
1158 /* Checks whether OP is a loop-level invariant and if so, records it.
1159 NONLINEAR_USE is true if the invariant is used in a way we do not
1160 handle specially. */
1163 record_invariant (struct ivopts_data *data, tree op, bool nonlinear_use)
1166 struct version_info *info;
1168 if (TREE_CODE (op) != SSA_NAME
1169 || !is_gimple_reg (op))
1172 bb = bb_for_stmt (SSA_NAME_DEF_STMT (op));
1174 && flow_bb_inside_loop_p (data->current_loop, bb))
1177 info = name_info (data, op);
1179 info->has_nonlin_use |= nonlinear_use;
1181 info->inv_id = ++data->max_inv_id;
1182 bitmap_set_bit (data->relevant, SSA_NAME_VERSION (op));
1185 /* Checks whether the use OP is interesting and if so, records it. */
1187 static struct iv_use *
1188 find_interesting_uses_op (struct ivopts_data *data, tree op)
1195 if (TREE_CODE (op) != SSA_NAME)
1198 iv = get_iv (data, op);
1202 if (iv->have_use_for)
1204 use = iv_use (data, iv->use_id);
1206 gcc_assert (use->type == USE_NONLINEAR_EXPR);
1210 if (zero_p (iv->step))
1212 record_invariant (data, op, true);
1215 iv->have_use_for = true;
1217 civ = XNEW (struct iv);
1220 stmt = SSA_NAME_DEF_STMT (op);
1221 gcc_assert (TREE_CODE (stmt) == PHI_NODE
1222 || TREE_CODE (stmt) == MODIFY_EXPR);
1224 use = record_use (data, NULL, civ, stmt, USE_NONLINEAR_EXPR);
1225 iv->use_id = use->id;
1230 /* Checks whether the condition *COND_P in STMT is interesting
1231 and if so, records it. */
1234 find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
1238 struct iv *iv0 = NULL, *iv1 = NULL, *civ;
1240 tree zero = integer_zero_node;
1242 const_iv.step = NULL_TREE;
1244 if (TREE_CODE (*cond_p) != SSA_NAME
1245 && !COMPARISON_CLASS_P (*cond_p))
1248 if (TREE_CODE (*cond_p) == SSA_NAME)
1255 op0_p = &TREE_OPERAND (*cond_p, 0);
1256 op1_p = &TREE_OPERAND (*cond_p, 1);
1259 if (TREE_CODE (*op0_p) == SSA_NAME)
1260 iv0 = get_iv (data, *op0_p);
1264 if (TREE_CODE (*op1_p) == SSA_NAME)
1265 iv1 = get_iv (data, *op1_p);
1269 if (/* When comparing with non-invariant value, we may not do any senseful
1270 induction variable elimination. */
1272 /* Eliminating condition based on two ivs would be nontrivial.
1273 ??? TODO -- it is not really important to handle this case. */
1274 || (!zero_p (iv0->step) && !zero_p (iv1->step)))
1276 find_interesting_uses_op (data, *op0_p);
1277 find_interesting_uses_op (data, *op1_p);
1281 if (zero_p (iv0->step) && zero_p (iv1->step))
1283 /* If both are invariants, this is a work for unswitching. */
1287 civ = XNEW (struct iv);
1288 *civ = zero_p (iv0->step) ? *iv1: *iv0;
1289 record_use (data, cond_p, civ, stmt, USE_COMPARE);
1292 /* Returns true if expression EXPR is obviously invariant in LOOP,
1293 i.e. if all its operands are defined outside of the LOOP. */
1296 expr_invariant_in_loop_p (struct loop *loop, tree expr)
1301 if (is_gimple_min_invariant (expr))
1304 if (TREE_CODE (expr) == SSA_NAME)
1306 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (expr));
1308 && flow_bb_inside_loop_p (loop, def_bb))
1317 len = TREE_CODE_LENGTH (TREE_CODE (expr));
1318 for (i = 0; i < len; i++)
1319 if (!expr_invariant_in_loop_p (loop, TREE_OPERAND (expr, i)))
1325 /* Cumulates the steps of indices into DATA and replaces their values with the
1326 initial ones. Returns false when the value of the index cannot be determined.
1327 Callback for for_each_index. */
1329 struct ifs_ivopts_data
1331 struct ivopts_data *ivopts_data;
1337 idx_find_step (tree base, tree *idx, void *data)
1339 struct ifs_ivopts_data *dta = data;
1341 tree step, iv_base, iv_step, lbound, off;
1342 struct loop *loop = dta->ivopts_data->current_loop;
1344 if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF
1345 || TREE_CODE (base) == ALIGN_INDIRECT_REF)
1348 /* If base is a component ref, require that the offset of the reference
1350 if (TREE_CODE (base) == COMPONENT_REF)
1352 off = component_ref_field_offset (base);
1353 return expr_invariant_in_loop_p (loop, off);
1356 /* If base is array, first check whether we will be able to move the
1357 reference out of the loop (in order to take its address in strength
1358 reduction). In order for this to work we need both lower bound
1359 and step to be loop invariants. */
1360 if (TREE_CODE (base) == ARRAY_REF)
1362 step = array_ref_element_size (base);
1363 lbound = array_ref_low_bound (base);
1365 if (!expr_invariant_in_loop_p (loop, step)
1366 || !expr_invariant_in_loop_p (loop, lbound))
1370 if (TREE_CODE (*idx) != SSA_NAME)
1373 iv = get_iv (dta->ivopts_data, *idx);
1377 /* XXX We produce for a base of *D42 with iv->base being &x[0]
1378 *&x[0], which is not folded and does not trigger the
1379 ARRAY_REF path below. */
1385 if (TREE_CODE (base) == ARRAY_REF)
1387 step = array_ref_element_size (base);
1389 /* We only handle addresses whose step is an integer constant. */
1390 if (TREE_CODE (step) != INTEGER_CST)
1394 /* The step for pointer arithmetics already is 1 byte. */
1395 step = build_int_cst (sizetype, 1);
1399 if (!convert_affine_scev (dta->ivopts_data->current_loop,
1400 sizetype, &iv_base, &iv_step, dta->stmt,
1403 /* The index might wrap. */
1407 step = fold_build2 (MULT_EXPR, sizetype, step, iv_step);
1410 *dta->step_p = step;
1412 *dta->step_p = fold_build2 (PLUS_EXPR, sizetype, *dta->step_p, step);
1417 /* Records use in index IDX. Callback for for_each_index. Ivopts data
1418 object is passed to it in DATA. */
1421 idx_record_use (tree base, tree *idx,
1424 find_interesting_uses_op (data, *idx);
1425 if (TREE_CODE (base) == ARRAY_REF)
1427 find_interesting_uses_op (data, array_ref_element_size (base));
1428 find_interesting_uses_op (data, array_ref_low_bound (base));
1433 /* Returns true if memory reference REF may be unaligned. */
1436 may_be_unaligned_p (tree ref)
1440 HOST_WIDE_INT bitsize;
1441 HOST_WIDE_INT bitpos;
1443 enum machine_mode mode;
1444 int unsignedp, volatilep;
1445 unsigned base_align;
1447 /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
1448 thus they are not misaligned. */
1449 if (TREE_CODE (ref) == TARGET_MEM_REF)
1452 /* The test below is basically copy of what expr.c:normal_inner_ref
1453 does to check whether the object must be loaded by parts when
1454 STRICT_ALIGNMENT is true. */
1455 base = get_inner_reference (ref, &bitsize, &bitpos, &toffset, &mode,
1456 &unsignedp, &volatilep, true);
1457 base_type = TREE_TYPE (base);
1458 base_align = TYPE_ALIGN (base_type);
1461 && (base_align < GET_MODE_ALIGNMENT (mode)
1462 || bitpos % GET_MODE_ALIGNMENT (mode) != 0
1463 || bitpos % BITS_PER_UNIT != 0))
1469 /* Return true if EXPR may be non-addressable. */
1472 may_be_nonaddressable_p (tree expr)
1474 switch (TREE_CODE (expr))
1477 return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr, 1))
1478 || may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
1481 case ARRAY_RANGE_REF:
1482 return may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
1484 case VIEW_CONVERT_EXPR:
1485 /* This kind of view-conversions may wrap non-addressable objects
1486 and make them look addressable. After some processing the
1487 non-addressability may be uncovered again, causing ADDR_EXPRs
1488 of inappropriate objects to be built. */
1489 return AGGREGATE_TYPE_P (TREE_TYPE (expr))
1490 && !AGGREGATE_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)));
1499 /* Finds addresses in *OP_P inside STMT. */
1502 find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
1504 tree base = *op_p, step = NULL;
1506 struct ifs_ivopts_data ifs_ivopts_data;
1508 /* Do not play with volatile memory references. A bit too conservative,
1509 perhaps, but safe. */
1510 if (stmt_ann (stmt)->has_volatile_ops)
1513 /* Ignore bitfields for now. Not really something terribly complicated
1515 if (TREE_CODE (base) == BIT_FIELD_REF)
1518 if (may_be_nonaddressable_p (base))
1521 if (STRICT_ALIGNMENT
1522 && may_be_unaligned_p (base))
1525 base = unshare_expr (base);
1527 if (TREE_CODE (base) == TARGET_MEM_REF)
1529 tree type = build_pointer_type (TREE_TYPE (base));
1533 && TREE_CODE (TMR_BASE (base)) == SSA_NAME)
1535 civ = get_iv (data, TMR_BASE (base));
1539 TMR_BASE (base) = civ->base;
1542 if (TMR_INDEX (base)
1543 && TREE_CODE (TMR_INDEX (base)) == SSA_NAME)
1545 civ = get_iv (data, TMR_INDEX (base));
1549 TMR_INDEX (base) = civ->base;
1554 if (TMR_STEP (base))
1555 astep = fold_build2 (MULT_EXPR, type, TMR_STEP (base), astep);
1558 step = fold_build2 (PLUS_EXPR, type, step, astep);
1566 base = tree_mem_ref_addr (type, base);
1570 ifs_ivopts_data.ivopts_data = data;
1571 ifs_ivopts_data.stmt = stmt;
1572 ifs_ivopts_data.step_p = &step;
1573 if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
1577 gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
1578 gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
1580 base = build_fold_addr_expr (base);
1582 /* Substituting bases of IVs into the base expression might
1583 have caused folding opportunities. */
1584 if (TREE_CODE (base) == ADDR_EXPR)
1586 tree *ref = &TREE_OPERAND (base, 0);
1587 while (handled_component_p (*ref))
1588 ref = &TREE_OPERAND (*ref, 0);
1589 if (TREE_CODE (*ref) == INDIRECT_REF)
1590 *ref = fold_indirect_ref (*ref);
1594 civ = alloc_iv (base, step);
1595 record_use (data, op_p, civ, stmt, USE_ADDRESS);
1599 for_each_index (op_p, idx_record_use, data);
1602 /* Finds and records invariants used in STMT. */
1605 find_invariants_stmt (struct ivopts_data *data, tree stmt)
1608 use_operand_p use_p;
1611 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1613 op = USE_FROM_PTR (use_p);
1614 record_invariant (data, op, false);
1618 /* Finds interesting uses of induction variables in the statement STMT. */
1621 find_interesting_uses_stmt (struct ivopts_data *data, tree stmt)
1626 use_operand_p use_p;
1628 find_invariants_stmt (data, stmt);
1630 if (TREE_CODE (stmt) == COND_EXPR)
1632 find_interesting_uses_cond (data, stmt, &COND_EXPR_COND (stmt));
1636 if (TREE_CODE (stmt) == MODIFY_EXPR)
1638 lhs = TREE_OPERAND (stmt, 0);
1639 rhs = TREE_OPERAND (stmt, 1);
1641 if (TREE_CODE (lhs) == SSA_NAME)
1643 /* If the statement defines an induction variable, the uses are not
1644 interesting by themselves. */
1646 iv = get_iv (data, lhs);
1648 if (iv && !zero_p (iv->step))
1652 switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
1654 case tcc_comparison:
1655 find_interesting_uses_cond (data, stmt, &TREE_OPERAND (stmt, 1));
1659 find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 1));
1660 if (REFERENCE_CLASS_P (lhs))
1661 find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
1667 if (REFERENCE_CLASS_P (lhs)
1668 && is_gimple_val (rhs))
1670 find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
1671 find_interesting_uses_op (data, rhs);
1675 /* TODO -- we should also handle address uses of type
1677 memory = call (whatever);
1684 if (TREE_CODE (stmt) == PHI_NODE
1685 && bb_for_stmt (stmt) == data->current_loop->header)
1687 lhs = PHI_RESULT (stmt);
1688 iv = get_iv (data, lhs);
1690 if (iv && !zero_p (iv->step))
1694 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1696 op = USE_FROM_PTR (use_p);
1698 if (TREE_CODE (op) != SSA_NAME)
1701 iv = get_iv (data, op);
1705 find_interesting_uses_op (data, op);
1709 /* Finds interesting uses of induction variables outside of loops
1710 on loop exit edge EXIT. */
1713 find_interesting_uses_outside (struct ivopts_data *data, edge exit)
1717 for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
1719 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1720 find_interesting_uses_op (data, def);
1724 /* Finds uses of the induction variables that are interesting. */
1727 find_interesting_uses (struct ivopts_data *data)
1730 block_stmt_iterator bsi;
1732 basic_block *body = get_loop_body (data->current_loop);
1734 struct version_info *info;
1737 if (dump_file && (dump_flags & TDF_DETAILS))
1738 fprintf (dump_file, "Uses:\n\n");
1740 for (i = 0; i < data->current_loop->num_nodes; i++)
1745 FOR_EACH_EDGE (e, ei, bb->succs)
1746 if (e->dest != EXIT_BLOCK_PTR
1747 && !flow_bb_inside_loop_p (data->current_loop, e->dest))
1748 find_interesting_uses_outside (data, e);
1750 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1751 find_interesting_uses_stmt (data, phi);
1752 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1753 find_interesting_uses_stmt (data, bsi_stmt (bsi));
1756 if (dump_file && (dump_flags & TDF_DETAILS))
1760 fprintf (dump_file, "\n");
1762 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
1764 info = ver_info (data, i);
1767 fprintf (dump_file, " ");
1768 print_generic_expr (dump_file, info->name, TDF_SLIM);
1769 fprintf (dump_file, " is invariant (%d)%s\n",
1770 info->inv_id, info->has_nonlin_use ? "" : ", eliminable");
1774 fprintf (dump_file, "\n");
1780 /* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
1781 is true, assume we are inside an address. If TOP_COMPREF is true, assume
1782 we are at the top-level of the processed address. */
1785 strip_offset_1 (tree expr, bool inside_addr, bool top_compref,
1786 unsigned HOST_WIDE_INT *offset)
1788 tree op0 = NULL_TREE, op1 = NULL_TREE, tmp, step;
1789 enum tree_code code;
1790 tree type, orig_type = TREE_TYPE (expr);
1791 unsigned HOST_WIDE_INT off0, off1, st;
1792 tree orig_expr = expr;
1796 type = TREE_TYPE (expr);
1797 code = TREE_CODE (expr);
1803 if (!cst_and_fits_in_hwi (expr)
1807 *offset = int_cst_value (expr);
1808 return build_int_cst (orig_type, 0);
1812 op0 = TREE_OPERAND (expr, 0);
1813 op1 = TREE_OPERAND (expr, 1);
1815 op0 = strip_offset_1 (op0, false, false, &off0);
1816 op1 = strip_offset_1 (op1, false, false, &off1);
1818 *offset = (code == PLUS_EXPR ? off0 + off1 : off0 - off1);
1819 if (op0 == TREE_OPERAND (expr, 0)
1820 && op1 == TREE_OPERAND (expr, 1))
1825 else if (zero_p (op0))
1827 if (code == PLUS_EXPR)
1830 expr = fold_build1 (NEGATE_EXPR, type, op1);
1833 expr = fold_build2 (code, type, op0, op1);
1835 return fold_convert (orig_type, expr);
1841 step = array_ref_element_size (expr);
1842 if (!cst_and_fits_in_hwi (step))
1845 st = int_cst_value (step);
1846 op1 = TREE_OPERAND (expr, 1);
1847 op1 = strip_offset_1 (op1, false, false, &off1);
1848 *offset = off1 * st;
1853 /* Strip the component reference completely. */
1854 op0 = TREE_OPERAND (expr, 0);
1855 op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
1865 tmp = component_ref_field_offset (expr);
1867 && cst_and_fits_in_hwi (tmp))
1869 /* Strip the component reference completely. */
1870 op0 = TREE_OPERAND (expr, 0);
1871 op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
1872 *offset = off0 + int_cst_value (tmp);
1878 op0 = TREE_OPERAND (expr, 0);
1879 op0 = strip_offset_1 (op0, true, true, &off0);
1882 if (op0 == TREE_OPERAND (expr, 0))
1885 expr = build_fold_addr_expr (op0);
1886 return fold_convert (orig_type, expr);
1889 inside_addr = false;
1896 /* Default handling of expressions for that we want to recurse into
1897 the first operand. */
1898 op0 = TREE_OPERAND (expr, 0);
1899 op0 = strip_offset_1 (op0, inside_addr, false, &off0);
1902 if (op0 == TREE_OPERAND (expr, 0)
1903 && (!op1 || op1 == TREE_OPERAND (expr, 1)))
1906 expr = copy_node (expr);
1907 TREE_OPERAND (expr, 0) = op0;
1909 TREE_OPERAND (expr, 1) = op1;
1911 /* Inside address, we might strip the top level component references,
1912 thus changing type of the expression. Handling of ADDR_EXPR
1914 expr = fold_convert (orig_type, expr);
1919 /* Strips constant offsets from EXPR and stores them to OFFSET. */
1922 strip_offset (tree expr, unsigned HOST_WIDE_INT *offset)
1924 return strip_offset_1 (expr, false, false, offset);
1927 /* Returns variant of TYPE that can be used as base for different uses.
1928 We return unsigned type with the same precision, which avoids problems
1932 generic_type_for (tree type)
1934 if (POINTER_TYPE_P (type))
1935 return unsigned_type_for (type);
1937 if (TYPE_UNSIGNED (type))
1940 return unsigned_type_for (type);
1943 /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
1944 the bitmap to that we should store it. */
1946 static struct ivopts_data *fd_ivopts_data;
1948 find_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
1950 bitmap *depends_on = data;
1951 struct version_info *info;
1953 if (TREE_CODE (*expr_p) != SSA_NAME)
1955 info = name_info (fd_ivopts_data, *expr_p);
1957 if (!info->inv_id || info->has_nonlin_use)
1961 *depends_on = BITMAP_ALLOC (NULL);
1962 bitmap_set_bit (*depends_on, info->inv_id);
1967 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
1968 position to POS. If USE is not NULL, the candidate is set as related to
1969 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
1970 replacement of the final value of the iv by a direct computation. */
1972 static struct iv_cand *
1973 add_candidate_1 (struct ivopts_data *data,
1974 tree base, tree step, bool important, enum iv_position pos,
1975 struct iv_use *use, tree incremented_at)
1978 struct iv_cand *cand = NULL;
1979 tree type, orig_type;
1983 orig_type = TREE_TYPE (base);
1984 type = generic_type_for (orig_type);
1985 if (type != orig_type)
1987 base = fold_convert (type, base);
1989 step = fold_convert (type, step);
1993 for (i = 0; i < n_iv_cands (data); i++)
1995 cand = iv_cand (data, i);
1997 if (cand->pos != pos)
2000 if (cand->incremented_at != incremented_at)
2014 if (!operand_equal_p (base, cand->iv->base, 0))
2017 if (zero_p (cand->iv->step))
2024 if (step && operand_equal_p (step, cand->iv->step, 0))
2029 if (i == n_iv_cands (data))
2031 cand = XCNEW (struct iv_cand);
2037 cand->iv = alloc_iv (base, step);
2040 if (pos != IP_ORIGINAL && cand->iv)
2042 cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp");
2043 cand->var_after = cand->var_before;
2045 cand->important = important;
2046 cand->incremented_at = incremented_at;
2047 VEC_safe_push (iv_cand_p, heap, data->iv_candidates, cand);
2050 && TREE_CODE (step) != INTEGER_CST)
2052 fd_ivopts_data = data;
2053 walk_tree (&step, find_depends, &cand->depends_on, NULL);
2056 if (dump_file && (dump_flags & TDF_DETAILS))
2057 dump_cand (dump_file, cand);
2060 if (important && !cand->important)
2062 cand->important = true;
2063 if (dump_file && (dump_flags & TDF_DETAILS))
2064 fprintf (dump_file, "Candidate %d is important\n", cand->id);
2069 bitmap_set_bit (use->related_cands, i);
2070 if (dump_file && (dump_flags & TDF_DETAILS))
2071 fprintf (dump_file, "Candidate %d is related to use %d\n",
2078 /* Returns true if incrementing the induction variable at the end of the LOOP
2081 The purpose is to avoid splitting latch edge with a biv increment, thus
2082 creating a jump, possibly confusing other optimization passes and leaving
2083 less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS
2084 is not available (so we do not have a better alternative), or if the latch
2085 edge is already nonempty. */
2088 allow_ip_end_pos_p (struct loop *loop)
2090 if (!ip_normal_pos (loop))
2093 if (!empty_block_p (ip_end_pos (loop)))
2099 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2100 position to POS. If USE is not NULL, the candidate is set as related to
2101 it. The candidate computation is scheduled on all available positions. */
2104 add_candidate (struct ivopts_data *data,
2105 tree base, tree step, bool important, struct iv_use *use)
2107 if (ip_normal_pos (data->current_loop))
2108 add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL_TREE);
2109 if (ip_end_pos (data->current_loop)
2110 && allow_ip_end_pos_p (data->current_loop))
2111 add_candidate_1 (data, base, step, important, IP_END, use, NULL_TREE);
2114 /* Add a standard "0 + 1 * iteration" iv candidate for a
2115 type with SIZE bits. */
2118 add_standard_iv_candidates_for_size (struct ivopts_data *data,
2121 tree type = lang_hooks.types.type_for_size (size, true);
2122 add_candidate (data, build_int_cst (type, 0), build_int_cst (type, 1),
2126 /* Adds standard iv candidates. */
2129 add_standard_iv_candidates (struct ivopts_data *data)
2131 add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE);
2133 /* The same for a double-integer type if it is still fast enough. */
2134 if (BITS_PER_WORD >= INT_TYPE_SIZE * 2)
2135 add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE * 2);
2139 /* Adds candidates bases on the old induction variable IV. */
2142 add_old_iv_candidates (struct ivopts_data *data, struct iv *iv)
2145 struct iv_cand *cand;
2147 add_candidate (data, iv->base, iv->step, true, NULL);
2149 /* The same, but with initial value zero. */
2150 add_candidate (data,
2151 build_int_cst (TREE_TYPE (iv->base), 0),
2152 iv->step, true, NULL);
2154 phi = SSA_NAME_DEF_STMT (iv->ssa_name);
2155 if (TREE_CODE (phi) == PHI_NODE)
2157 /* Additionally record the possibility of leaving the original iv
2159 def = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (data->current_loop));
2160 cand = add_candidate_1 (data,
2161 iv->base, iv->step, true, IP_ORIGINAL, NULL,
2162 SSA_NAME_DEF_STMT (def));
2163 cand->var_before = iv->ssa_name;
2164 cand->var_after = def;
2168 /* Adds candidates based on the old induction variables. */
2171 add_old_ivs_candidates (struct ivopts_data *data)
2177 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
2179 iv = ver_info (data, i)->iv;
2180 if (iv && iv->biv_p && !zero_p (iv->step))
2181 add_old_iv_candidates (data, iv);
2185 /* Adds candidates based on the value of the induction variable IV and USE. */
2188 add_iv_value_candidates (struct ivopts_data *data,
2189 struct iv *iv, struct iv_use *use)
2191 unsigned HOST_WIDE_INT offset;
2194 add_candidate (data, iv->base, iv->step, false, use);
2196 /* The same, but with initial value zero. Make such variable important,
2197 since it is generic enough so that possibly many uses may be based
2199 add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
2200 iv->step, true, use);
2202 /* Third, try removing the constant offset. */
2203 base = strip_offset (iv->base, &offset);
2205 add_candidate (data, base, iv->step, false, use);
2208 /* Adds candidates based on the uses. */
2211 add_derived_ivs_candidates (struct ivopts_data *data)
2215 for (i = 0; i < n_iv_uses (data); i++)
2217 struct iv_use *use = iv_use (data, i);
2224 case USE_NONLINEAR_EXPR:
2227 /* Just add the ivs based on the value of the iv used here. */
2228 add_iv_value_candidates (data, use->iv, use);
2237 /* Record important candidates and add them to related_cands bitmaps
2241 record_important_candidates (struct ivopts_data *data)
2246 for (i = 0; i < n_iv_cands (data); i++)
2248 struct iv_cand *cand = iv_cand (data, i);
2250 if (cand->important)
2251 bitmap_set_bit (data->important_candidates, i);
2254 data->consider_all_candidates = (n_iv_cands (data)
2255 <= CONSIDER_ALL_CANDIDATES_BOUND);
2257 if (data->consider_all_candidates)
2259 /* We will not need "related_cands" bitmaps in this case,
2260 so release them to decrease peak memory consumption. */
2261 for (i = 0; i < n_iv_uses (data); i++)
2263 use = iv_use (data, i);
2264 BITMAP_FREE (use->related_cands);
2269 /* Add important candidates to the related_cands bitmaps. */
2270 for (i = 0; i < n_iv_uses (data); i++)
2271 bitmap_ior_into (iv_use (data, i)->related_cands,
2272 data->important_candidates);
2276 /* Finds the candidates for the induction variables. */
2279 find_iv_candidates (struct ivopts_data *data)
2281 /* Add commonly used ivs. */
2282 add_standard_iv_candidates (data);
2284 /* Add old induction variables. */
2285 add_old_ivs_candidates (data);
2287 /* Add induction variables derived from uses. */
2288 add_derived_ivs_candidates (data);
2290 /* Record the important candidates. */
2291 record_important_candidates (data);
2294 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
2295 If consider_all_candidates is true, we use a two-dimensional array, otherwise
2296 we allocate a simple list to every use. */
2299 alloc_use_cost_map (struct ivopts_data *data)
2301 unsigned i, size, s, j;
2303 for (i = 0; i < n_iv_uses (data); i++)
2305 struct iv_use *use = iv_use (data, i);
2308 if (data->consider_all_candidates)
2309 size = n_iv_cands (data);
2313 EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi)
2318 /* Round up to the power of two, so that moduling by it is fast. */
2319 for (size = 1; size < s; size <<= 1)
2323 use->n_map_members = size;
2324 use->cost_map = XCNEWVEC (struct cost_pair, size);
2328 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
2329 on invariants DEPENDS_ON and that the value used in expressing it
2333 set_use_iv_cost (struct ivopts_data *data,
2334 struct iv_use *use, struct iv_cand *cand, unsigned cost,
2335 bitmap depends_on, tree value)
2341 BITMAP_FREE (depends_on);
2345 if (data->consider_all_candidates)
2347 use->cost_map[cand->id].cand = cand;
2348 use->cost_map[cand->id].cost = cost;
2349 use->cost_map[cand->id].depends_on = depends_on;
2350 use->cost_map[cand->id].value = value;
2354 /* n_map_members is a power of two, so this computes modulo. */
2355 s = cand->id & (use->n_map_members - 1);
2356 for (i = s; i < use->n_map_members; i++)
2357 if (!use->cost_map[i].cand)
2359 for (i = 0; i < s; i++)
2360 if (!use->cost_map[i].cand)
2366 use->cost_map[i].cand = cand;
2367 use->cost_map[i].cost = cost;
2368 use->cost_map[i].depends_on = depends_on;
2369 use->cost_map[i].value = value;
2372 /* Gets cost of (USE, CANDIDATE) pair. */
2374 static struct cost_pair *
2375 get_use_iv_cost (struct ivopts_data *data, struct iv_use *use,
2376 struct iv_cand *cand)
2379 struct cost_pair *ret;
2384 if (data->consider_all_candidates)
2386 ret = use->cost_map + cand->id;
2393 /* n_map_members is a power of two, so this computes modulo. */
2394 s = cand->id & (use->n_map_members - 1);
2395 for (i = s; i < use->n_map_members; i++)
2396 if (use->cost_map[i].cand == cand)
2397 return use->cost_map + i;
2399 for (i = 0; i < s; i++)
2400 if (use->cost_map[i].cand == cand)
2401 return use->cost_map + i;
2406 /* Returns estimate on cost of computing SEQ. */
2414 for (; seq; seq = NEXT_INSN (seq))
2416 set = single_set (seq);
2418 cost += rtx_cost (set, SET);
2426 /* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
2428 produce_memory_decl_rtl (tree obj, int *regno)
2433 if (TREE_STATIC (obj) || DECL_EXTERNAL (obj))
2435 const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj));
2436 x = gen_rtx_SYMBOL_REF (Pmode, name);
2439 x = gen_raw_REG (Pmode, (*regno)++);
2441 return gen_rtx_MEM (DECL_MODE (obj), x);
2444 /* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
2445 walk_tree. DATA contains the actual fake register number. */
2448 prepare_decl_rtl (tree *expr_p, int *ws, void *data)
2450 tree obj = NULL_TREE;
2454 switch (TREE_CODE (*expr_p))
2457 for (expr_p = &TREE_OPERAND (*expr_p, 0);
2458 handled_component_p (*expr_p);
2459 expr_p = &TREE_OPERAND (*expr_p, 0))
2462 if (DECL_P (obj) && !DECL_RTL_SET_P (obj))
2463 x = produce_memory_decl_rtl (obj, regno);
2468 obj = SSA_NAME_VAR (*expr_p);
2469 if (!DECL_RTL_SET_P (obj))
2470 x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
2479 if (DECL_RTL_SET_P (obj))
2482 if (DECL_MODE (obj) == BLKmode)
2483 x = produce_memory_decl_rtl (obj, regno);
2485 x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
2495 VEC_safe_push (tree, heap, decl_rtl_to_reset, obj);
2496 SET_DECL_RTL (obj, x);
2502 /* Determines cost of the computation of EXPR. */
2505 computation_cost (tree expr)
2508 tree type = TREE_TYPE (expr);
2510 /* Avoid using hard regs in ways which may be unsupported. */
2511 int regno = LAST_VIRTUAL_REGISTER + 1;
2513 walk_tree (&expr, prepare_decl_rtl, ®no, NULL);
2515 rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL);
2519 cost = seq_cost (seq);
2521 cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type));
2526 /* Returns variable containing the value of candidate CAND at statement AT. */
2529 var_at_stmt (struct loop *loop, struct iv_cand *cand, tree stmt)
2531 if (stmt_after_increment (loop, cand, stmt))
2532 return cand->var_after;
2534 return cand->var_before;
2537 /* Return the most significant (sign) bit of T. Similar to tree_int_cst_msb,
2538 but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE. */
2541 tree_int_cst_sign_bit (tree t)
2543 unsigned bitno = TYPE_PRECISION (TREE_TYPE (t)) - 1;
2544 unsigned HOST_WIDE_INT w;
2546 if (bitno < HOST_BITS_PER_WIDE_INT)
2547 w = TREE_INT_CST_LOW (t);
2550 w = TREE_INT_CST_HIGH (t);
2551 bitno -= HOST_BITS_PER_WIDE_INT;
2554 return (w >> bitno) & 1;
2557 /* If we can prove that TOP = cst * BOT for some constant cst,
2558 store cst to MUL and return true. Otherwise return false.
2559 The returned value is always sign-extended, regardless of the
2560 signedness of TOP and BOT. */
2563 constant_multiple_of (tree top, tree bot, double_int *mul)
2566 enum tree_code code;
2567 double_int res, p0, p1;
2568 unsigned precision = TYPE_PRECISION (TREE_TYPE (top));
2573 if (operand_equal_p (top, bot, 0))
2575 *mul = double_int_one;
2579 code = TREE_CODE (top);
2583 mby = TREE_OPERAND (top, 1);
2584 if (TREE_CODE (mby) != INTEGER_CST)
2587 if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &res))
2590 *mul = double_int_sext (double_int_mul (res, tree_to_double_int (mby)),
2596 if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &p0)
2597 || !constant_multiple_of (TREE_OPERAND (top, 1), bot, &p1))
2600 if (code == MINUS_EXPR)
2601 p1 = double_int_neg (p1);
2602 *mul = double_int_sext (double_int_add (p0, p1), precision);
2606 if (TREE_CODE (bot) != INTEGER_CST)
2609 p0 = double_int_sext (tree_to_double_int (bot), precision);
2610 p1 = double_int_sext (tree_to_double_int (top), precision);
2611 if (double_int_zero_p (p1))
2613 *mul = double_int_sext (double_int_sdivmod (p0, p1, FLOOR_DIV_EXPR, &res),
2615 return double_int_zero_p (res);
2622 /* Sets COMB to CST. */
2625 aff_combination_const (struct affine_tree_combination *comb, tree type,
2626 unsigned HOST_WIDE_INT cst)
2628 unsigned prec = TYPE_PRECISION (type);
2631 comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
2634 comb->rest = NULL_TREE;
2635 comb->offset = cst & comb->mask;
2638 /* Sets COMB to single element ELT. */
2641 aff_combination_elt (struct affine_tree_combination *comb, tree type, tree elt)
2643 unsigned prec = TYPE_PRECISION (type);
2646 comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
2649 comb->elts[0] = elt;
2651 comb->rest = NULL_TREE;
2655 /* Scales COMB by SCALE. */
2658 aff_combination_scale (struct affine_tree_combination *comb,
2659 unsigned HOST_WIDE_INT scale)
2668 aff_combination_const (comb, comb->type, 0);
2672 comb->offset = (scale * comb->offset) & comb->mask;
2673 for (i = 0, j = 0; i < comb->n; i++)
2675 comb->coefs[j] = (scale * comb->coefs[i]) & comb->mask;
2676 comb->elts[j] = comb->elts[i];
2677 if (comb->coefs[j] != 0)
2684 if (comb->n < MAX_AFF_ELTS)
2686 comb->coefs[comb->n] = scale;
2687 comb->elts[comb->n] = comb->rest;
2688 comb->rest = NULL_TREE;
2692 comb->rest = fold_build2 (MULT_EXPR, comb->type, comb->rest,
2693 build_int_cst_type (comb->type, scale));
2697 /* Adds ELT * SCALE to COMB. */
2700 aff_combination_add_elt (struct affine_tree_combination *comb, tree elt,
2701 unsigned HOST_WIDE_INT scale)
2708 for (i = 0; i < comb->n; i++)
2709 if (operand_equal_p (comb->elts[i], elt, 0))
2711 comb->coefs[i] = (comb->coefs[i] + scale) & comb->mask;
2716 comb->coefs[i] = comb->coefs[comb->n];
2717 comb->elts[i] = comb->elts[comb->n];
2721 gcc_assert (comb->n == MAX_AFF_ELTS - 1);
2722 comb->coefs[comb->n] = 1;
2723 comb->elts[comb->n] = comb->rest;
2724 comb->rest = NULL_TREE;
2729 if (comb->n < MAX_AFF_ELTS)
2731 comb->coefs[comb->n] = scale;
2732 comb->elts[comb->n] = elt;
2738 elt = fold_convert (comb->type, elt);
2740 elt = fold_build2 (MULT_EXPR, comb->type,
2741 fold_convert (comb->type, elt),
2742 build_int_cst_type (comb->type, scale));
2745 comb->rest = fold_build2 (PLUS_EXPR, comb->type, comb->rest, elt);
2750 /* Adds COMB2 to COMB1. */
2753 aff_combination_add (struct affine_tree_combination *comb1,
2754 struct affine_tree_combination *comb2)
2758 comb1->offset = (comb1->offset + comb2->offset) & comb1->mask;
2759 for (i = 0; i < comb2->n; i++)
2760 aff_combination_add_elt (comb1, comb2->elts[i], comb2->coefs[i]);
2762 aff_combination_add_elt (comb1, comb2->rest, 1);
2765 /* Convert COMB to TYPE. */
2768 aff_combination_convert (tree type, struct affine_tree_combination *comb)
2770 unsigned prec = TYPE_PRECISION (type);
2773 /* If the precision of both types is the same, it suffices to change the type
2774 of the whole combination -- the elements are allowed to have another type
2775 equivalent wrto STRIP_NOPS. */
2776 if (prec == TYPE_PRECISION (comb->type))
2782 comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
2783 comb->offset = comb->offset & comb->mask;
2785 /* The type of the elements can be different from comb->type only as
2786 much as what STRIP_NOPS would remove. We can just directly cast
2788 for (i = 0; i < comb->n; i++)
2789 comb->elts[i] = fold_convert (type, comb->elts[i]);
2791 comb->rest = fold_convert (type, comb->rest);
2796 /* Splits EXPR into an affine combination of parts. */
2799 tree_to_aff_combination (tree expr, tree type,
2800 struct affine_tree_combination *comb)
2802 struct affine_tree_combination tmp;
2803 enum tree_code code;
2804 tree cst, core, toffset;
2805 HOST_WIDE_INT bitpos, bitsize;
2806 enum machine_mode mode;
2807 int unsignedp, volatilep;
2811 code = TREE_CODE (expr);
2815 aff_combination_const (comb, type, int_cst_value (expr));
2820 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
2821 tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp);
2822 if (code == MINUS_EXPR)
2823 aff_combination_scale (&tmp, -1);
2824 aff_combination_add (comb, &tmp);
2828 cst = TREE_OPERAND (expr, 1);
2829 if (TREE_CODE (cst) != INTEGER_CST)
2831 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
2832 aff_combination_scale (comb, int_cst_value (cst));
2836 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
2837 aff_combination_scale (comb, -1);
2841 core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
2842 &toffset, &mode, &unsignedp, &volatilep,
2844 if (bitpos % BITS_PER_UNIT != 0)
2846 aff_combination_const (comb, type, bitpos / BITS_PER_UNIT);
2847 core = build_fold_addr_expr (core);
2848 if (TREE_CODE (core) == ADDR_EXPR)
2849 aff_combination_add_elt (comb, core, 1);
2852 tree_to_aff_combination (core, type, &tmp);
2853 aff_combination_add (comb, &tmp);
2857 tree_to_aff_combination (toffset, type, &tmp);
2858 aff_combination_add (comb, &tmp);
2866 aff_combination_elt (comb, type, expr);
2869 /* Creates EXPR + ELT * SCALE in TYPE. MASK is the mask for width of TYPE. */
2872 add_elt_to_tree (tree expr, tree type, tree elt, unsigned HOST_WIDE_INT scale,
2873 unsigned HOST_WIDE_INT mask)
2875 enum tree_code code;
2878 elt = fold_convert (type, elt);
2885 return fold_build2 (PLUS_EXPR, type, expr, elt);
2891 return fold_build1 (NEGATE_EXPR, type, elt);
2893 return fold_build2 (MINUS_EXPR, type, expr, elt);
2897 return fold_build2 (MULT_EXPR, type, elt,
2898 build_int_cst_type (type, scale));
2900 if ((scale | (mask >> 1)) == mask)
2902 /* Scale is negative. */
2904 scale = (-scale) & mask;
2909 elt = fold_build2 (MULT_EXPR, type, elt,
2910 build_int_cst_type (type, scale));
2911 return fold_build2 (code, type, expr, elt);
2914 /* Copies the tree elements of COMB to ensure that they are not shared. */
2917 unshare_aff_combination (struct affine_tree_combination *comb)
2921 for (i = 0; i < comb->n; i++)
2922 comb->elts[i] = unshare_expr (comb->elts[i]);
2924 comb->rest = unshare_expr (comb->rest);
2927 /* Makes tree from the affine combination COMB. */
2930 aff_combination_to_tree (struct affine_tree_combination *comb)
2932 tree type = comb->type;
2933 tree expr = comb->rest;
2935 unsigned HOST_WIDE_INT off, sgn;
2937 if (comb->n == 0 && comb->offset == 0)
2941 /* Handle the special case produced by get_computation_aff when
2942 the type does not fit in HOST_WIDE_INT. */
2943 return fold_convert (type, expr);
2946 return build_int_cst (type, 0);
2949 gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
2951 for (i = 0; i < comb->n; i++)
2952 expr = add_elt_to_tree (expr, type, comb->elts[i], comb->coefs[i],
2955 if ((comb->offset | (comb->mask >> 1)) == comb->mask)
2957 /* Offset is negative. */
2958 off = (-comb->offset) & comb->mask;
2966 return add_elt_to_tree (expr, type, build_int_cst_type (type, off), sgn,
2970 /* Folds EXPR using the affine expressions framework. */
2973 fold_affine_expr (tree expr)
2975 tree type = TREE_TYPE (expr);
2976 struct affine_tree_combination comb;
2978 if (TYPE_PRECISION (type) > HOST_BITS_PER_WIDE_INT)
2981 tree_to_aff_combination (expr, type, &comb);
2982 return aff_combination_to_tree (&comb);
2985 /* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
2986 same precision that is at least as wide as the precision of TYPE, stores
2987 BA to A and BB to B, and returns the type of BA. Otherwise, returns the
2991 determine_common_wider_type (tree *a, tree *b)
2993 tree wider_type = NULL;
2995 tree atype = TREE_TYPE (*a);
2997 if ((TREE_CODE (*a) == NOP_EXPR
2998 || TREE_CODE (*a) == CONVERT_EXPR))
3000 suba = TREE_OPERAND (*a, 0);
3001 wider_type = TREE_TYPE (suba);
3002 if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (atype))
3008 if ((TREE_CODE (*b) == NOP_EXPR
3009 || TREE_CODE (*b) == CONVERT_EXPR))
3011 subb = TREE_OPERAND (*b, 0);
3012 if (TYPE_PRECISION (wider_type) != TYPE_PRECISION (TREE_TYPE (subb)))
3023 /* Determines the expression by that USE is expressed from induction variable
3024 CAND at statement AT in LOOP. The expression is stored in a decomposed
3025 form into AFF. Returns false if USE cannot be expressed using CAND. */
3028 get_computation_aff (struct loop *loop,
3029 struct iv_use *use, struct iv_cand *cand, tree at,
3030 struct affine_tree_combination *aff)
3032 tree ubase = use->iv->base;
3033 tree ustep = use->iv->step;
3034 tree cbase = cand->iv->base;
3035 tree cstep = cand->iv->step;
3036 tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
3041 unsigned HOST_WIDE_INT ustepi, cstepi;
3042 HOST_WIDE_INT ratioi;
3043 struct affine_tree_combination cbase_aff, expr_aff;
3044 tree cstep_orig = cstep, ustep_orig = ustep;
3047 if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
3049 /* We do not have a precision to express the values of use. */
3053 expr = var_at_stmt (loop, cand, at);
3055 if (TREE_TYPE (expr) != ctype)
3057 /* This may happen with the original ivs. */
3058 expr = fold_convert (ctype, expr);
3061 if (TYPE_UNSIGNED (utype))
3065 uutype = unsigned_type_for (utype);
3066 ubase = fold_convert (uutype, ubase);
3067 ustep = fold_convert (uutype, ustep);
3070 if (uutype != ctype)
3072 expr = fold_convert (uutype, expr);
3073 cbase = fold_convert (uutype, cbase);
3074 cstep = fold_convert (uutype, cstep);
3076 /* If the conversion is not noop, we must take it into account when
3077 considering the value of the step. */
3078 if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
3082 if (cst_and_fits_in_hwi (cstep_orig)
3083 && cst_and_fits_in_hwi (ustep_orig))
3085 ustepi = int_cst_value (ustep_orig);
3086 cstepi = int_cst_value (cstep_orig);
3088 if (!divide (TYPE_PRECISION (uutype), ustepi, cstepi, &ratioi))
3090 /* TODO maybe consider case when ustep divides cstep and the ratio is
3091 a power of 2 (so that the division is fast to execute)? We would
3092 need to be much more careful with overflows etc. then. */
3096 ratio = build_int_cst_type (uutype, ratioi);
3100 if (!constant_multiple_of (ustep_orig, cstep_orig, &rat))
3102 ratio = double_int_to_tree (uutype, rat);
3104 /* Ratioi is only used to detect special cases when the multiplicative
3105 factor is 1 or -1, so if rat does not fit to HOST_WIDE_INT, we may
3107 if (double_int_fits_in_shwi_p (rat))
3108 ratioi = double_int_to_shwi (rat);
3113 /* In case both UBASE and CBASE are shortened to UUTYPE from some common
3114 type, we achieve better folding by computing their difference in this
3115 wider type, and cast the result to UUTYPE. We do not need to worry about
3116 overflows, as all the arithmetics will in the end be performed in UUTYPE
3118 common_type = determine_common_wider_type (&ubase, &cbase);
3120 /* We may need to shift the value if we are after the increment. */
3121 if (stmt_after_increment (loop, cand, at))
3123 if (uutype != common_type)
3124 cstep = fold_convert (common_type, cstep);
3125 cbase = fold_build2 (PLUS_EXPR, common_type, cbase, cstep);
3128 /* use = ubase - ratio * cbase + ratio * var.
3130 In general case ubase + ratio * (var - cbase) could be better (one less
3131 multiplication), but often it is possible to eliminate redundant parts
3132 of computations from (ubase - ratio * cbase) term, and if it does not
3133 happen, fold is able to apply the distributive law to obtain this form
3136 if (TYPE_PRECISION (common_type) > HOST_BITS_PER_WIDE_INT)
3138 /* Let's compute in trees and just return the result in AFF. This case
3139 should not be very common, and fold itself is not that bad either,
3140 so making the aff. functions more complicated to handle this case
3141 is not that urgent. */
3144 delta = fold_build2 (MINUS_EXPR, common_type, ubase, cbase);
3145 if (uutype != common_type)
3146 delta = fold_convert (uutype, delta);
3147 expr = fold_build2 (PLUS_EXPR, uutype, expr, delta);
3149 else if (ratioi == -1)
3151 delta = fold_build2 (PLUS_EXPR, common_type, ubase, cbase);
3152 if (uutype != common_type)
3153 delta = fold_convert (uutype, delta);
3154 expr = fold_build2 (MINUS_EXPR, uutype, delta, expr);
3158 delta = fold_build2 (MULT_EXPR, common_type, cbase, ratio);
3159 delta = fold_build2 (MINUS_EXPR, common_type, ubase, delta);
3160 if (uutype != common_type)
3161 delta = fold_convert (uutype, delta);
3162 expr = fold_build2 (MULT_EXPR, uutype, ratio, expr);
3163 expr = fold_build2 (PLUS_EXPR, uutype, delta, expr);
3174 /* If we got here, the types fits in HOST_WIDE_INT, thus it must be
3175 possible to compute ratioi. */
3176 gcc_assert (ratioi);
3178 tree_to_aff_combination (ubase, common_type, aff);
3179 tree_to_aff_combination (cbase, common_type, &cbase_aff);
3180 tree_to_aff_combination (expr, uutype, &expr_aff);
3181 aff_combination_scale (&cbase_aff, -ratioi);
3182 aff_combination_scale (&expr_aff, ratioi);
3183 aff_combination_add (aff, &cbase_aff);
3184 if (common_type != uutype)
3185 aff_combination_convert (uutype, aff);
3186 aff_combination_add (aff, &expr_aff);
3191 /* Determines the expression by that USE is expressed from induction variable
3192 CAND at statement AT in LOOP. The computation is unshared. */
3195 get_computation_at (struct loop *loop,
3196 struct iv_use *use, struct iv_cand *cand, tree at)
3198 struct affine_tree_combination aff;
3199 tree type = TREE_TYPE (use->iv->base);
3201 if (!get_computation_aff (loop, use, cand, at, &aff))
3203 unshare_aff_combination (&aff);
3204 return fold_convert (type, aff_combination_to_tree (&aff));
3207 /* Determines the expression by that USE is expressed from induction variable
3208 CAND in LOOP. The computation is unshared. */
3211 get_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand)
3213 return get_computation_at (loop, use, cand, use->stmt);
3216 /* Returns cost of addition in MODE. */
3219 add_cost (enum machine_mode mode)
3221 static unsigned costs[NUM_MACHINE_MODES];
3229 force_operand (gen_rtx_fmt_ee (PLUS, mode,
3230 gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
3231 gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 2)),
3236 cost = seq_cost (seq);
3242 if (dump_file && (dump_flags & TDF_DETAILS))
3243 fprintf (dump_file, "Addition in %s costs %d\n",
3244 GET_MODE_NAME (mode), cost);
3248 /* Entry in a hashtable of already known costs for multiplication. */
3251 HOST_WIDE_INT cst; /* The constant to multiply by. */
3252 enum machine_mode mode; /* In mode. */
3253 unsigned cost; /* The cost. */
3256 /* Counts hash value for the ENTRY. */
3259 mbc_entry_hash (const void *entry)
3261 const struct mbc_entry *e = entry;
3263 return 57 * (hashval_t) e->mode + (hashval_t) (e->cst % 877);
3266 /* Compares the hash table entries ENTRY1 and ENTRY2. */
3269 mbc_entry_eq (const void *entry1, const void *entry2)
3271 const struct mbc_entry *e1 = entry1;
3272 const struct mbc_entry *e2 = entry2;
3274 return (e1->mode == e2->mode
3275 && e1->cst == e2->cst);
3278 /* Returns cost of multiplication by constant CST in MODE. */
3281 multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode)
3283 static htab_t costs;
3284 struct mbc_entry **cached, act;
3289 costs = htab_create (100, mbc_entry_hash, mbc_entry_eq, free);
3293 cached = (struct mbc_entry **) htab_find_slot (costs, &act, INSERT);
3295 return (*cached)->cost;
3297 *cached = XNEW (struct mbc_entry);
3298 (*cached)->mode = mode;
3299 (*cached)->cst = cst;
3302 expand_mult (mode, gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
3303 gen_int_mode (cst, mode), NULL_RTX, 0);
3307 cost = seq_cost (seq);
3309 if (dump_file && (dump_flags & TDF_DETAILS))
3310 fprintf (dump_file, "Multiplication by %d in %s costs %d\n",
3311 (int) cst, GET_MODE_NAME (mode), cost);
3313 (*cached)->cost = cost;
3318 /* Returns true if multiplying by RATIO is allowed in address. */
3321 multiplier_allowed_in_address_p (HOST_WIDE_INT ratio)
3323 #define MAX_RATIO 128
3324 static sbitmap valid_mult;
3328 rtx reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
3332 valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1);
3333 sbitmap_zero (valid_mult);
3334 addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX);
3335 for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
3337 XEXP (addr, 1) = gen_int_mode (i, Pmode);
3338 if (memory_address_p (Pmode, addr))
3339 SET_BIT (valid_mult, i + MAX_RATIO);
3342 if (dump_file && (dump_flags & TDF_DETAILS))
3344 fprintf (dump_file, " allowed multipliers:");
3345 for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
3346 if (TEST_BIT (valid_mult, i + MAX_RATIO))
3347 fprintf (dump_file, " %d", (int) i);
3348 fprintf (dump_file, "\n");
3349 fprintf (dump_file, "\n");
3353 if (ratio > MAX_RATIO || ratio < -MAX_RATIO)
3356 return TEST_BIT (valid_mult, ratio + MAX_RATIO);
3359 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
3360 If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
3361 variable is omitted. The created memory accesses MODE.
3363 TODO -- there must be some better way. This all is quite crude. */
3366 get_address_cost (bool symbol_present, bool var_present,
3367 unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio)
3369 static bool initialized = false;
3370 static HOST_WIDE_INT rat, off;
3371 static HOST_WIDE_INT min_offset, max_offset;
3372 static unsigned costs[2][2][2][2];
3373 unsigned cost, acost;
3374 rtx seq, addr, base;
3375 bool offset_p, ratio_p;
3377 HOST_WIDE_INT s_offset;
3378 unsigned HOST_WIDE_INT mask;
3386 reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
3388 addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
3389 for (i = 1; i <= 1 << 20; i <<= 1)
3391 XEXP (addr, 1) = gen_int_mode (i, Pmode);
3392 if (!memory_address_p (Pmode, addr))
3395 max_offset = i >> 1;
3398 for (i = 1; i <= 1 << 20; i <<= 1)
3400 XEXP (addr, 1) = gen_int_mode (-i, Pmode);
3401 if (!memory_address_p (Pmode, addr))
3404 min_offset = -(i >> 1);
3406 if (dump_file && (dump_flags & TDF_DETAILS))
3408 fprintf (dump_file, "get_address_cost:\n");
3409 fprintf (dump_file, " min offset %d\n", (int) min_offset);
3410 fprintf (dump_file, " max offset %d\n", (int) max_offset);
3414 for (i = 2; i <= MAX_RATIO; i++)
3415 if (multiplier_allowed_in_address_p (i))
3422 bits = GET_MODE_BITSIZE (Pmode);
3423 mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
3425 if ((offset >> (bits - 1) & 1))
3430 offset_p = (s_offset != 0
3431 && min_offset <= s_offset && s_offset <= max_offset);
3432 ratio_p = (ratio != 1
3433 && multiplier_allowed_in_address_p (ratio));
3435 if (ratio != 1 && !ratio_p)
3436 cost += multiply_by_cost (ratio, Pmode);
3438 if (s_offset && !offset_p && !symbol_present)
3440 cost += add_cost (Pmode);
3444 acost = costs[symbol_present][var_present][offset_p][ratio_p];
3447 int old_cse_not_expected;
3450 addr = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
3451 reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
3453 addr = gen_rtx_fmt_ee (MULT, Pmode, addr, gen_int_mode (rat, Pmode));
3456 addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1);
3460 base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
3462 base = gen_rtx_fmt_e (CONST, Pmode,
3463 gen_rtx_fmt_ee (PLUS, Pmode,
3465 gen_int_mode (off, Pmode)));
3468 base = gen_int_mode (off, Pmode);
3473 addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, base);
3476 /* To avoid splitting addressing modes, pretend that no cse will
3478 old_cse_not_expected = cse_not_expected;
3479 cse_not_expected = true;
3480 addr = memory_address (Pmode, addr);
3481 cse_not_expected = old_cse_not_expected;
3485 acost = seq_cost (seq);
3486 acost += address_cost (addr, Pmode);
3490 costs[symbol_present][var_present][offset_p][ratio_p] = acost;
3493 return cost + acost;
3496 /* Estimates cost of forcing expression EXPR into a variable. */
3499 force_expr_to_var_cost (tree expr)
3501 static bool costs_initialized = false;
3502 static unsigned integer_cost;
3503 static unsigned symbol_cost;
3504 static unsigned address_cost;
3506 unsigned cost0, cost1, cost;
3507 enum machine_mode mode;
3509 if (!costs_initialized)
3511 tree var = create_tmp_var_raw (integer_type_node, "test_var");
3512 rtx x = gen_rtx_MEM (DECL_MODE (var),
3513 gen_rtx_SYMBOL_REF (Pmode, "test_var"));
3515 tree type = build_pointer_type (integer_type_node);
3517 integer_cost = computation_cost (build_int_cst (integer_type_node,
3520 SET_DECL_RTL (var, x);
3521 TREE_STATIC (var) = 1;
3522 addr = build1 (ADDR_EXPR, type, var);
3523 symbol_cost = computation_cost (addr) + 1;
3526 = computation_cost (build2 (PLUS_EXPR, type,
3528 build_int_cst (type, 2000))) + 1;
3529 if (dump_file && (dump_flags & TDF_DETAILS))
3531 fprintf (dump_file, "force_expr_to_var_cost:\n");
3532 fprintf (dump_file, " integer %d\n", (int) integer_cost);
3533 fprintf (dump_file, " symbol %d\n", (int) symbol_cost);
3534 fprintf (dump_file, " address %d\n", (int) address_cost);
3535 fprintf (dump_file, " other %d\n", (int) target_spill_cost);
3536 fprintf (dump_file, "\n");
3539 costs_initialized = true;
3544 if (SSA_VAR_P (expr))
3547 if (TREE_INVARIANT (expr))
3549 if (TREE_CODE (expr) == INTEGER_CST)
3550 return integer_cost;
3552 if (TREE_CODE (expr) == ADDR_EXPR)
3554 tree obj = TREE_OPERAND (expr, 0);
3556 if (TREE_CODE (obj) == VAR_DECL
3557 || TREE_CODE (obj) == PARM_DECL
3558 || TREE_CODE (obj) == RESULT_DECL)
3562 return address_cost;
3565 switch (TREE_CODE (expr))
3570 op0 = TREE_OPERAND (expr, 0);
3571 op1 = TREE_OPERAND (expr, 1);
3575 if (is_gimple_val (op0))
3578 cost0 = force_expr_to_var_cost (op0);
3580 if (is_gimple_val (op1))
3583 cost1 = force_expr_to_var_cost (op1);
3588 /* Just an arbitrary value, FIXME. */
3589 return target_spill_cost;
3592 mode = TYPE_MODE (TREE_TYPE (expr));
3593 switch (TREE_CODE (expr))
3597 cost = add_cost (mode);
3601 if (cst_and_fits_in_hwi (op0))
3602 cost = multiply_by_cost (int_cst_value (op0), mode);
3603 else if (cst_and_fits_in_hwi (op1))
3604 cost = multiply_by_cost (int_cst_value (op1), mode);
3606 return target_spill_cost;
3616 /* Bound the cost by target_spill_cost. The parts of complicated
3617 computations often are either loop invariant or at least can
3618 be shared between several iv uses, so letting this grow without
3619 limits would not give reasonable results. */
3620 return cost < target_spill_cost ? cost : target_spill_cost;
3623 /* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
3624 invariants the computation depends on. */
3627 force_var_cost (struct ivopts_data *data,
3628 tree expr, bitmap *depends_on)
3632 fd_ivopts_data = data;
3633 walk_tree (&expr, find_depends, depends_on, NULL);
3636 return force_expr_to_var_cost (expr);
3639 /* Estimates cost of expressing address ADDR as var + symbol + offset. The
3640 value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
3641 to false if the corresponding part is missing. DEPENDS_ON is a set of the
3642 invariants the computation depends on. */
3645 split_address_cost (struct ivopts_data *data,
3646 tree addr, bool *symbol_present, bool *var_present,
3647 unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
3650 HOST_WIDE_INT bitsize;
3651 HOST_WIDE_INT bitpos;
3653 enum machine_mode mode;
3654 int unsignedp, volatilep;
3656 core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode,
3657 &unsignedp, &volatilep, false);
3660 || bitpos % BITS_PER_UNIT != 0
3661 || TREE_CODE (core) != VAR_DECL)
3663 *symbol_present = false;
3664 *var_present = true;
3665 fd_ivopts_data = data;
3666 walk_tree (&addr, find_depends, depends_on, NULL);
3667 return target_spill_cost;
3670 *offset += bitpos / BITS_PER_UNIT;
3671 if (TREE_STATIC (core)
3672 || DECL_EXTERNAL (core))
3674 *symbol_present = true;
3675 *var_present = false;
3679 *symbol_present = false;
3680 *var_present = true;
3684 /* Estimates cost of expressing difference of addresses E1 - E2 as
3685 var + symbol + offset. The value of offset is added to OFFSET,
3686 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3687 part is missing. DEPENDS_ON is a set of the invariants the computation
3691 ptr_difference_cost (struct ivopts_data *data,
3692 tree e1, tree e2, bool *symbol_present, bool *var_present,
3693 unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
3695 HOST_WIDE_INT diff = 0;
3698 gcc_assert (TREE_CODE (e1) == ADDR_EXPR);
3700 if (ptr_difference_const (e1, e2, &diff))
3703 *symbol_present = false;
3704 *var_present = false;
3708 if (e2 == integer_zero_node)
3709 return split_address_cost (data, TREE_OPERAND (e1, 0),
3710 symbol_present, var_present, offset, depends_on);
3712 *symbol_present = false;
3713 *var_present = true;
3715 cost = force_var_cost (data, e1, depends_on);
3716 cost += force_var_cost (data, e2, depends_on);
3717 cost += add_cost (Pmode);
3722 /* Estimates cost of expressing difference E1 - E2 as
3723 var + symbol + offset. The value of offset is added to OFFSET,
3724 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3725 part is missing. DEPENDS_ON is a set of the invariants the computation
3729 difference_cost (struct ivopts_data *data,
3730 tree e1, tree e2, bool *symbol_present, bool *var_present,
3731 unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
3734 enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
3735 unsigned HOST_WIDE_INT off1, off2;
3737 e1 = strip_offset (e1, &off1);
3738 e2 = strip_offset (e2, &off2);
3739 *offset += off1 - off2;
3744 if (TREE_CODE (e1) == ADDR_EXPR)
3745 return ptr_difference_cost (data, e1, e2, symbol_present, var_present, offset,
3747 *symbol_present = false;
3749 if (operand_equal_p (e1, e2, 0))
3751 *var_present = false;
3754 *var_present = true;
3756 return force_var_cost (data, e1, depends_on);
3760 cost = force_var_cost (data, e2, depends_on);
3761 cost += multiply_by_cost (-1, mode);
3766 cost = force_var_cost (data, e1, depends_on);
3767 cost += force_var_cost (data, e2, depends_on);
3768 cost += add_cost (mode);
3773 /* Determines the cost of the computation by that USE is expressed
3774 from induction variable CAND. If ADDRESS_P is true, we just need
3775 to create an address from it, otherwise we want to get it into
3776 register. A set of invariants we depend on is stored in
3777 DEPENDS_ON. AT is the statement at that the value is computed. */
3780 get_computation_cost_at (struct ivopts_data *data,
3781 struct iv_use *use, struct iv_cand *cand,
3782 bool address_p, bitmap *depends_on, tree at)
3784 tree ubase = use->iv->base, ustep = use->iv->step;
3786 tree utype = TREE_TYPE (ubase), ctype;
3787 unsigned HOST_WIDE_INT ustepi, cstepi, offset = 0;
3788 HOST_WIDE_INT ratio, aratio;
3789 bool var_present, symbol_present;
3790 unsigned cost = 0, n_sums;
3794 /* Only consider real candidates. */
3798 cbase = cand->iv->base;
3799 cstep = cand->iv->step;
3800 ctype = TREE_TYPE (cbase);
3802 if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
3804 /* We do not have a precision to express the values of use. */
3810 /* Do not try to express address of an object with computation based
3811 on address of a different object. This may cause problems in rtl
3812 level alias analysis (that does not expect this to be happening,
3813 as this is illegal in C), and would be unlikely to be useful
3815 if (use->iv->base_object
3816 && cand->iv->base_object
3817 && !operand_equal_p (use->iv->base_object, cand->iv->base_object, 0))
3821 if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
3823 /* TODO -- add direct handling of this case. */
3827 /* CSTEPI is removed from the offset in case statement is after the
3828 increment. If the step is not constant, we use zero instead.
3829 This is a bit imprecise (there is the extra addition), but
3830 redundancy elimination is likely to transform the code so that
3831 it uses value of the variable before increment anyway,
3832 so it is not that much unrealistic. */
3833 if (cst_and_fits_in_hwi (cstep))
3834 cstepi = int_cst_value (cstep);
3838 if (cst_and_fits_in_hwi (ustep)
3839 && cst_and_fits_in_hwi (cstep))
3841 ustepi = int_cst_value (ustep);
3843 if (!divide (TYPE_PRECISION (utype), ustepi, cstepi, &ratio))
3850 if (!constant_multiple_of (ustep, cstep, &rat))
3853 if (double_int_fits_in_shwi_p (rat))
3854 ratio = double_int_to_shwi (rat);
3859 /* use = ubase + ratio * (var - cbase). If either cbase is a constant
3860 or ratio == 1, it is better to handle this like
3862 ubase - ratio * cbase + ratio * var
3864 (also holds in the case ratio == -1, TODO. */
3866 if (cst_and_fits_in_hwi (cbase))
3868 offset = - ratio * int_cst_value (cbase);
3869 cost += difference_cost (data,
3870 ubase, integer_zero_node,
3871 &symbol_present, &var_present, &offset,
3874 else if (ratio == 1)
3876 cost += difference_cost (data,
3878 &symbol_present, &var_present, &offset,
3883 cost += force_var_cost (data, cbase, depends_on);
3884 cost += add_cost (TYPE_MODE (ctype));
3885 cost += difference_cost (data,
3886 ubase, integer_zero_node,
3887 &symbol_present, &var_present, &offset,
3891 /* If we are after the increment, the value of the candidate is higher by
3893 if (stmt_after_increment (data->current_loop, cand, at))
3894 offset -= ratio * cstepi;
3896 /* Now the computation is in shape symbol + var1 + const + ratio * var2.
3897 (symbol/var/const parts may be omitted). If we are looking for an address,
3898 find the cost of addressing this. */
3900 return cost + get_address_cost (symbol_present, var_present, offset, ratio);
3902 /* Otherwise estimate the costs for computing the expression. */
3903 aratio = ratio > 0 ? ratio : -ratio;
3904 if (!symbol_present && !var_present && !offset)
3907 cost += multiply_by_cost (ratio, TYPE_MODE (ctype));
3913 cost += multiply_by_cost (aratio, TYPE_MODE (ctype));
3917 /* Symbol + offset should be compile-time computable. */
3918 && (symbol_present || offset))
3921 return cost + n_sums * add_cost (TYPE_MODE (ctype));
3925 /* Just get the expression, expand it and measure the cost. */
3926 tree comp = get_computation_at (data->current_loop, use, cand, at);
3932 comp = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (comp)), comp);
3934 return computation_cost (comp);
3938 /* Determines the cost of the computation by that USE is expressed
3939 from induction variable CAND. If ADDRESS_P is true, we just need
3940 to create an address from it, otherwise we want to get it into
3941 register. A set of invariants we depend on is stored in
3945 get_computation_cost (struct ivopts_data *data,
3946 struct iv_use *use, struct iv_cand *cand,
3947 bool address_p, bitmap *depends_on)
3949 return get_computation_cost_at (data,
3950 use, cand, address_p, depends_on, use->stmt);
3953 /* Determines cost of basing replacement of USE on CAND in a generic
3957 determine_use_iv_cost_generic (struct ivopts_data *data,
3958 struct iv_use *use, struct iv_cand *cand)
3963 /* The simple case first -- if we need to express value of the preserved
3964 original biv, the cost is 0. This also prevents us from counting the
3965 cost of increment twice -- once at this use and once in the cost of
3967 if (cand->pos == IP_ORIGINAL
3968 && cand->incremented_at == use->stmt)
3970 set_use_iv_cost (data, use, cand, 0, NULL, NULL_TREE);
3974 cost = get_computation_cost (data, use, cand, false, &depends_on);
3975 set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
3977 return cost != INFTY;
3980 /* Determines cost of basing replacement of USE on CAND in an address. */
3983 determine_use_iv_cost_address (struct ivopts_data *data,
3984 struct iv_use *use, struct iv_cand *cand)
3987 unsigned cost = get_computation_cost (data, use, cand, true, &depends_on);
3989 set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
3991 return cost != INFTY;
3994 /* Computes value of induction variable IV in iteration NITER. */
3997 iv_value (struct iv *iv, tree niter)
4000 tree type = TREE_TYPE (iv->base);
4002 niter = fold_convert (type, niter);
4003 val = fold_build2 (MULT_EXPR, type, iv->step, niter);
4005 return fold_build2 (PLUS_EXPR, type, iv->base, val);
4008 /* Computes value of candidate CAND at position AT in iteration NITER. */
4011 cand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter)
4013 tree val = iv_value (cand->iv, niter);
4014 tree type = TREE_TYPE (cand->iv->base);
4016 if (stmt_after_increment (loop, cand, at))
4017 val = fold_build2 (PLUS_EXPR, type, val, cand->iv->step);
4022 /* Returns period of induction variable iv. */
4025 iv_period (struct iv *iv)
4027 tree step = iv->step, period, type;
4030 gcc_assert (step && TREE_CODE (step) == INTEGER_CST);
4032 /* Period of the iv is gcd (step, type range). Since type range is power
4033 of two, it suffices to determine the maximum power of two that divides
4035 pow2div = num_ending_zeros (step);
4036 type = unsigned_type_for (TREE_TYPE (step));
4038 period = build_low_bits_mask (type,
4039 (TYPE_PRECISION (type)
4040 - tree_low_cst (pow2div, 1)));
4045 /* Returns the comparison operator used when eliminating the iv USE. */
4047 static enum tree_code
4048 iv_elimination_compare (struct ivopts_data *data, struct iv_use *use)
4050 struct loop *loop = data->current_loop;
4054 ex_bb = bb_for_stmt (use->stmt);
4055 exit = EDGE_SUCC (ex_bb, 0);
4056 if (flow_bb_inside_loop_p (loop, exit->dest))
4057 exit = EDGE_SUCC (ex_bb, 1);
4059 return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
4062 /* Check whether it is possible to express the condition in USE by comparison
4063 of candidate CAND. If so, store the value compared with to BOUND. */
4066 may_eliminate_iv (struct ivopts_data *data,
4067 struct iv_use *use, struct iv_cand *cand, tree *bound)
4072 tree wider_type, period, per_type;
4073 struct loop *loop = data->current_loop;
4075 if (TREE_CODE (cand->iv->step) != INTEGER_CST)
4078 /* For now works only for exits that dominate the loop latch. TODO -- extend
4079 for other conditions inside loop body. */
4080 ex_bb = bb_for_stmt (use->stmt);
4081 if (use->stmt != last_stmt (ex_bb)
4082 || TREE_CODE (use->stmt) != COND_EXPR)
4084 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, ex_bb))
4087 exit = EDGE_SUCC (ex_bb, 0);
4088 if (flow_bb_inside_loop_p (loop, exit->dest))
4089 exit = EDGE_SUCC (ex_bb, 1);
4090 if (flow_bb_inside_loop_p (loop, exit->dest))
4093 nit = niter_for_exit (data, exit);
4097 nit_type = TREE_TYPE (nit);
4099 /* Determine whether we may use the variable to test whether niter iterations
4100 elapsed. This is the case iff the period of the induction variable is
4101 greater than the number of iterations. */
4102 period = iv_period (cand->iv);
4105 per_type = TREE_TYPE (period);
4107 wider_type = TREE_TYPE (period);
4108 if (TYPE_PRECISION (nit_type) < TYPE_PRECISION (per_type))
4109 wider_type = per_type;
4111 wider_type = nit_type;
4113 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
4114 fold_convert (wider_type, period),
4115 fold_convert (wider_type, nit))))
4118 *bound = fold_affine_expr (cand_value_at (loop, cand, use->stmt, nit));
4122 /* Determines cost of basing replacement of USE on CAND in a condition. */
4125 determine_use_iv_cost_condition (struct ivopts_data *data,
4126 struct iv_use *use, struct iv_cand *cand)
4128 tree bound = NULL_TREE, op, cond;
4129 bitmap depends_on = NULL;
4132 /* Only consider real candidates. */
4135 set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE);
4139 if (may_eliminate_iv (data, use, cand, &bound))
4141 cost = force_var_cost (data, bound, &depends_on);
4143 set_use_iv_cost (data, use, cand, cost, depends_on, bound);
4144 return cost != INFTY;
4147 /* The induction variable elimination failed; just express the original
4148 giv. If it is compared with an invariant, note that we cannot get
4150 cost = get_computation_cost (data, use, cand, false, &depends_on);
4153 if (TREE_CODE (cond) != SSA_NAME)
4155 op = TREE_OPERAND (cond, 0);
4156 if (TREE_CODE (op) == SSA_NAME && !zero_p (get_iv (data, op)->step))
4157 op = TREE_OPERAND (cond, 1);
4158 if (TREE_CODE (op) == SSA_NAME)
4160 op = get_iv (data, op)->base;
4161 fd_ivopts_data = data;
4162 walk_tree (&op, find_depends, &depends_on, NULL);
4166 set_use_iv_cost (data, use, cand, cost, depends_on, NULL);
4167 return cost != INFTY;
4170 /* Determines cost of basing replacement of USE on CAND. Returns false
4171 if USE cannot be based on CAND. */
4174 determine_use_iv_cost (struct ivopts_data *data,
4175 struct iv_use *use, struct iv_cand *cand)
4179 case USE_NONLINEAR_EXPR:
4180 return determine_use_iv_cost_generic (data, use, cand);
4183 return determine_use_iv_cost_address (data, use, cand);
4186 return determine_use_iv_cost_condition (data, use, cand);
4193 /* Determines costs of basing the use of the iv on an iv candidate. */
4196 determine_use_iv_costs (struct ivopts_data *data)
4200 struct iv_cand *cand;
4201 bitmap to_clear = BITMAP_ALLOC (NULL);
4203 alloc_use_cost_map (data);
4205 for (i = 0; i < n_iv_uses (data); i++)
4207 use = iv_use (data, i);
4209 if (data->consider_all_candidates)
4211 for (j = 0; j < n_iv_cands (data); j++)
4213 cand = iv_cand (data, j);
4214 determine_use_iv_cost (data, use, cand);
4221 EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi)
4223 cand = iv_cand (data, j);
4224 if (!determine_use_iv_cost (data, use, cand))
4225 bitmap_set_bit (to_clear, j);
4228 /* Remove the candidates for that the cost is infinite from
4229 the list of related candidates. */
4230 bitmap_and_compl_into (use->related_cands, to_clear);
4231 bitmap_clear (to_clear);
4235 BITMAP_FREE (to_clear);
4237 if (dump_file && (dump_flags & TDF_DETAILS))
4239 fprintf (dump_file, "Use-candidate costs:\n");
4241 for (i = 0; i < n_iv_uses (data); i++)
4243 use = iv_use (data, i);
4245 fprintf (dump_file, "Use %d:\n", i);
4246 fprintf (dump_file, " cand\tcost\tdepends on\n");
4247 for (j = 0; j < use->n_map_members; j++)
4249 if (!use->cost_map[j].cand
4250 || use->cost_map[j].cost == INFTY)
4253 fprintf (dump_file, " %d\t%d\t",
4254 use->cost_map[j].cand->id,
4255 use->cost_map[j].cost);
4256 if (use->cost_map[j].depends_on)
4257 bitmap_print (dump_file,
4258 use->cost_map[j].depends_on, "","");
4259 fprintf (dump_file, "\n");
4262 fprintf (dump_file, "\n");
4264 fprintf (dump_file, "\n");
4268 /* Determines cost of the candidate CAND. */
4271 determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
4273 unsigned cost_base, cost_step;
4282 /* There are two costs associated with the candidate -- its increment
4283 and its initialization. The second is almost negligible for any loop
4284 that rolls enough, so we take it just very little into account. */
4286 base = cand->iv->base;
4287 cost_base = force_var_cost (data, base, NULL);
4288 cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
4290 cand->cost = cost_step + cost_base / AVG_LOOP_NITER (current_loop);
4292 /* Prefer the original iv unless we may gain something by replacing it;
4293 this is not really relevant for artificial ivs created by other
4295 if (cand->pos == IP_ORIGINAL
4296 && !DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
4299 /* Prefer not to insert statements into latch unless there are some
4300 already (so that we do not create unnecessary jumps). */
4301 if (cand->pos == IP_END
4302 && empty_block_p (ip_end_pos (data->current_loop)))
4306 /* Determines costs of computation of the candidates. */
4309 determine_iv_costs (struct ivopts_data *data)
4313 if (dump_file && (dump_flags & TDF_DETAILS))
4315 fprintf (dump_file, "Candidate costs:\n");
4316 fprintf (dump_file, " cand\tcost\n");
4319 for (i = 0; i < n_iv_cands (data); i++)
4321 struct iv_cand *cand = iv_cand (data, i);
4323 determine_iv_cost (data, cand);
4325 if (dump_file && (dump_flags & TDF_DETAILS))
4326 fprintf (dump_file, " %d\t%d\n", i, cand->cost);
4329 if (dump_file && (dump_flags & TDF_DETAILS))
4330 fprintf (dump_file, "\n");
4333 /* Calculates cost for having SIZE induction variables. */
4336 ivopts_global_cost_for_size (struct ivopts_data *data, unsigned size)
4338 return global_cost_for_size (size, data->regs_used, n_iv_uses (data));
4341 /* For each size of the induction variable set determine the penalty. */
4344 determine_set_costs (struct ivopts_data *data)
4348 struct loop *loop = data->current_loop;
4351 /* We use the following model (definitely improvable, especially the
4352 cost function -- TODO):
4354 We estimate the number of registers available (using MD data), name it A.
4356 We estimate the number of registers used by the loop, name it U. This
4357 number is obtained as the number of loop phi nodes (not counting virtual
4358 registers and bivs) + the number of variables from outside of the loop.
4360 We set a reserve R (free regs that are used for temporary computations,
4361 etc.). For now the reserve is a constant 3.
4363 Let I be the number of induction variables.
4365 -- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
4366 make a lot of ivs without a reason).
4367 -- if A - R < U + I <= A, the cost is I * PRES_COST
4368 -- if U + I > A, the cost is I * PRES_COST and
4369 number of uses * SPILL_COST * (U + I - A) / (U + I) is added. */
4371 if (dump_file && (dump_flags & TDF_DETAILS))
4373 fprintf (dump_file, "Global costs:\n");
4374 fprintf (dump_file, " target_avail_regs %d\n", target_avail_regs);
4375 fprintf (dump_file, " target_small_cost %d\n", target_small_cost);
4376 fprintf (dump_file, " target_pres_cost %d\n", target_pres_cost);
4377 fprintf (dump_file, " target_spill_cost %d\n", target_spill_cost);
4381 for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
4383 op = PHI_RESULT (phi);
4385 if (!is_gimple_reg (op))
4388 if (get_iv (data, op))
4394 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
4396 struct version_info *info = ver_info (data, j);
4398 if (info->inv_id && info->has_nonlin_use)
4402 data->regs_used = n;
4403 if (dump_file && (dump_flags & TDF_DETAILS))
4404 fprintf (dump_file, " regs_used %d\n", n);
4406 if (dump_file && (dump_flags & TDF_DETAILS))
4408 fprintf (dump_file, " cost for size:\n");
4409 fprintf (dump_file, " ivs\tcost\n");
4410 for (j = 0; j <= 2 * target_avail_regs; j++)
4411 fprintf (dump_file, " %d\t%d\n", j,
4412 ivopts_global_cost_for_size (data, j));
4413 fprintf (dump_file, "\n");
4417 /* Returns true if A is a cheaper cost pair than B. */
4420 cheaper_cost_pair (struct cost_pair *a, struct cost_pair *b)
4428 if (a->cost < b->cost)
4431 if (a->cost > b->cost)
4434 /* In case the costs are the same, prefer the cheaper candidate. */
4435 if (a->cand->cost < b->cand->cost)
4441 /* Computes the cost field of IVS structure. */
4444 iv_ca_recount_cost (struct ivopts_data *data, struct iv_ca *ivs)
4448 cost += ivs->cand_use_cost;
4449 cost += ivs->cand_cost;
4450 cost += ivopts_global_cost_for_size (data, ivs->n_regs);
4455 /* Remove invariants in set INVS to set IVS. */
4458 iv_ca_set_remove_invariants (struct iv_ca *ivs, bitmap invs)
4466 EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
4468 ivs->n_invariant_uses[iid]--;
4469 if (ivs->n_invariant_uses[iid] == 0)
4474 /* Set USE not to be expressed by any candidate in IVS. */
4477 iv_ca_set_no_cp (struct ivopts_data *data, struct iv_ca *ivs,
4480 unsigned uid = use->id, cid;
4481 struct cost_pair *cp;
4483 cp = ivs->cand_for_use[uid];
4489 ivs->cand_for_use[uid] = NULL;
4490 ivs->n_cand_uses[cid]--;
4492 if (ivs->n_cand_uses[cid] == 0)
4494 bitmap_clear_bit (ivs->cands, cid);
4495 /* Do not count the pseudocandidates. */
4499 ivs->cand_cost -= cp->cand->cost;
4501 iv_ca_set_remove_invariants (ivs, cp->cand->depends_on);
4504 ivs->cand_use_cost -= cp->cost;
4506 iv_ca_set_remove_invariants (ivs, cp->depends_on);
4507 iv_ca_recount_cost (data, ivs);
4510 /* Add invariants in set INVS to set IVS. */
4513 iv_ca_set_add_invariants (struct iv_ca *ivs, bitmap invs)
4521 EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
4523 ivs->n_invariant_uses[iid]++;
4524 if (ivs->n_invariant_uses[iid] == 1)
4529 /* Set cost pair for USE in set IVS to CP. */
4532 iv_ca_set_cp (struct ivopts_data *data, struct iv_ca *ivs,
4533 struct iv_use *use, struct cost_pair *cp)
4535 unsigned uid = use->id, cid;
4537 if (ivs->cand_for_use[uid] == cp)
4540 if (ivs->cand_for_use[uid])
4541 iv_ca_set_no_cp (data, ivs, use);
4548 ivs->cand_for_use[uid] = cp;
4549 ivs->n_cand_uses[cid]++;
4550 if (ivs->n_cand_uses[cid] == 1)
4552 bitmap_set_bit (ivs->cands, cid);
4553 /* Do not count the pseudocandidates. */
4557 ivs->cand_cost += cp->cand->cost;
4559 iv_ca_set_add_invariants (ivs, cp->cand->depends_on);
4562 ivs->cand_use_cost += cp->cost;
4563 iv_ca_set_add_invariants (ivs, cp->depends_on);
4564 iv_ca_recount_cost (data, ivs);
4568 /* Extend set IVS by expressing USE by some of the candidates in it
4572 iv_ca_add_use (struct ivopts_data *data, struct iv_ca *ivs,
4575 struct cost_pair *best_cp = NULL, *cp;
4579 gcc_assert (ivs->upto >= use->id);
4581 if (ivs->upto == use->id)
4587 EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
4589 cp = get_use_iv_cost (data, use, iv_cand (data, i));
4591 if (cheaper_cost_pair (cp, best_cp))
4595 iv_ca_set_cp (data, ivs, use, best_cp);
4598 /* Get cost for assignment IVS. */
4601 iv_ca_cost (struct iv_ca *ivs)
4603 return (ivs->bad_uses ? INFTY : ivs->cost);
4606 /* Returns true if all dependences of CP are among invariants in IVS. */
4609 iv_ca_has_deps (struct iv_ca *ivs, struct cost_pair *cp)
4614 if (!cp->depends_on)
4617 EXECUTE_IF_SET_IN_BITMAP (cp->depends_on, 0, i, bi)
4619 if (ivs->n_invariant_uses[i] == 0)
4626 /* Creates change of expressing USE by NEW_CP instead of OLD_CP and chains
4627 it before NEXT_CHANGE. */
4629 static struct iv_ca_delta *
4630 iv_ca_delta_add (struct iv_use *use, struct cost_pair *old_cp,
4631 struct cost_pair *new_cp, struct iv_ca_delta *next_change)
4633 struct iv_ca_delta *change = XNEW (struct iv_ca_delta);
4636 change->old_cp = old_cp;
4637 change->new_cp = new_cp;
4638 change->next_change = next_change;
4643 /* Joins two lists of changes L1 and L2. Destructive -- old lists
4646 static struct iv_ca_delta *
4647 iv_ca_delta_join (struct iv_ca_delta *l1, struct iv_ca_delta *l2)
4649 struct iv_ca_delta *last;
4657 for (last = l1; last->next_change; last = last->next_change)
4659 last->next_change = l2;
4664 /* Returns candidate by that USE is expressed in IVS. */
4666 static struct cost_pair *
4667 iv_ca_cand_for_use (struct iv_ca *ivs, struct iv_use *use)
4669 return ivs->cand_for_use[use->id];
4672 /* Reverse the list of changes DELTA, forming the inverse to it. */
4674 static struct iv_ca_delta *
4675 iv_ca_delta_reverse (struct iv_ca_delta *delta)
4677 struct iv_ca_delta *act, *next, *prev = NULL;
4678 struct cost_pair *tmp;
4680 for (act = delta; act; act = next)
4682 next = act->next_change;
4683 act->next_change = prev;
4687 act->old_cp = act->new_cp;
4694 /* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
4695 reverted instead. */
4698 iv_ca_delta_commit (struct ivopts_data *data, struct iv_ca *ivs,
4699 struct iv_ca_delta *delta, bool forward)
4701 struct cost_pair *from, *to;
4702 struct iv_ca_delta *act;
4705 delta = iv_ca_delta_reverse (delta);
4707 for (act = delta; act; act = act->next_change)
4711 gcc_assert (iv_ca_cand_for_use (ivs, act->use) == from);
4712 iv_ca_set_cp (data, ivs, act->use, to);
4716 iv_ca_delta_reverse (delta);
4719 /* Returns true if CAND is used in IVS. */
4722 iv_ca_cand_used_p (struct iv_ca *ivs, struct iv_cand *cand)
4724 return ivs->n_cand_uses[cand->id] > 0;
4727 /* Returns number of induction variable candidates in the set IVS. */
4730 iv_ca_n_cands (struct iv_ca *ivs)
4732 return ivs->n_cands;
4735 /* Free the list of changes DELTA. */
4738 iv_ca_delta_free (struct iv_ca_delta **delta)
4740 struct iv_ca_delta *act, *next;
4742 for (act = *delta; act; act = next)
4744 next = act->next_change;
4751 /* Allocates new iv candidates assignment. */
4753 static struct iv_ca *
4754 iv_ca_new (struct ivopts_data *data)
4756 struct iv_ca *nw = XNEW (struct iv_ca);
4760 nw->cand_for_use = XCNEWVEC (struct cost_pair *, n_iv_uses (data));
4761 nw->n_cand_uses = XCNEWVEC (unsigned, n_iv_cands (data));
4762 nw->cands = BITMAP_ALLOC (NULL);
4765 nw->cand_use_cost = 0;
4767 nw->n_invariant_uses = XCNEWVEC (unsigned, data->max_inv_id + 1);
4773 /* Free memory occupied by the set IVS. */
4776 iv_ca_free (struct iv_ca **ivs)
4778 free ((*ivs)->cand_for_use);
4779 free ((*ivs)->n_cand_uses);
4780 BITMAP_FREE ((*ivs)->cands);
4781 free ((*ivs)->n_invariant_uses);
4786 /* Dumps IVS to FILE. */
4789 iv_ca_dump (struct ivopts_data *data, FILE *file, struct iv_ca *ivs)
4791 const char *pref = " invariants ";
4794 fprintf (file, " cost %d\n", iv_ca_cost (ivs));
4795 bitmap_print (file, ivs->cands, " candidates ","\n");
4797 for (i = 1; i <= data->max_inv_id; i++)
4798 if (ivs->n_invariant_uses[i])
4800 fprintf (file, "%s%d", pref, i);
4803 fprintf (file, "\n");
4806 /* Try changing candidate in IVS to CAND for each use. Return cost of the
4807 new set, and store differences in DELTA. Number of induction variables
4808 in the new set is stored to N_IVS. */
4811 iv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs,
4812 struct iv_cand *cand, struct iv_ca_delta **delta,
4817 struct cost_pair *old_cp, *new_cp;
4820 for (i = 0; i < ivs->upto; i++)
4822 use = iv_use (data, i);
4823 old_cp = iv_ca_cand_for_use (ivs, use);
4826 && old_cp->cand == cand)
4829 new_cp = get_use_iv_cost (data, use, cand);
4833 if (!iv_ca_has_deps (ivs, new_cp))
4836 if (!cheaper_cost_pair (new_cp, old_cp))
4839 *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
4842 iv_ca_delta_commit (data, ivs, *delta, true);
4843 cost = iv_ca_cost (ivs);
4845 *n_ivs = iv_ca_n_cands (ivs);
4846 iv_ca_delta_commit (data, ivs, *delta, false);
4851 /* Try narrowing set IVS by removing CAND. Return the cost of
4852 the new set and store the differences in DELTA. */
4855 iv_ca_narrow (struct ivopts_data *data, struct iv_ca *ivs,
4856 struct iv_cand *cand, struct iv_ca_delta **delta)
4860 struct cost_pair *old_cp, *new_cp, *cp;
4862 struct iv_cand *cnd;
4866 for (i = 0; i < n_iv_uses (data); i++)
4868 use = iv_use (data, i);
4870 old_cp = iv_ca_cand_for_use (ivs, use);
4871 if (old_cp->cand != cand)
4876 if (data->consider_all_candidates)
4878 EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, ci, bi)
4883 cnd = iv_cand (data, ci);
4885 cp = get_use_iv_cost (data, use, cnd);
4888 if (!iv_ca_has_deps (ivs, cp))
4891 if (!cheaper_cost_pair (cp, new_cp))
4899 EXECUTE_IF_AND_IN_BITMAP (use->related_cands, ivs->cands, 0, ci, bi)
4904 cnd = iv_cand (data, ci);
4906 cp = get_use_iv_cost (data, use, cnd);
4909 if (!iv_ca_has_deps (ivs, cp))
4912 if (!cheaper_cost_pair (cp, new_cp))
4921 iv_ca_delta_free (delta);
4925 *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
4928 iv_ca_delta_commit (data, ivs, *delta, true);
4929 cost = iv_ca_cost (ivs);
4930 iv_ca_delta_commit (data, ivs, *delta, false);
4935 /* Try optimizing the set of candidates IVS by removing candidates different
4936 from to EXCEPT_CAND from it. Return cost of the new set, and store
4937 differences in DELTA. */
4940 iv_ca_prune (struct ivopts_data *data, struct iv_ca *ivs,
4941 struct iv_cand *except_cand, struct iv_ca_delta **delta)
4944 struct iv_ca_delta *act_delta, *best_delta;
4945 unsigned i, best_cost, acost;
4946 struct iv_cand *cand;
4949 best_cost = iv_ca_cost (ivs);
4951 EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
4953 cand = iv_cand (data, i);
4955 if (cand == except_cand)
4958 acost = iv_ca_narrow (data, ivs, cand, &act_delta);
4960 if (acost < best_cost)
4963 iv_ca_delta_free (&best_delta);
4964 best_delta = act_delta;
4967 iv_ca_delta_free (&act_delta);
4976 /* Recurse to possibly remove other unnecessary ivs. */
4977 iv_ca_delta_commit (data, ivs, best_delta, true);
4978 best_cost = iv_ca_prune (data, ivs, except_cand, delta);
4979 iv_ca_delta_commit (data, ivs, best_delta, false);
4980 *delta = iv_ca_delta_join (best_delta, *delta);
4984 /* Tries to extend the sets IVS in the best possible way in order
4985 to express the USE. */
4988 try_add_cand_for (struct ivopts_data *data, struct iv_ca *ivs,
4991 unsigned best_cost, act_cost;
4994 struct iv_cand *cand;
4995 struct iv_ca_delta *best_delta = NULL, *act_delta;
4996 struct cost_pair *cp;
4998 iv_ca_add_use (data, ivs, use);
4999 best_cost = iv_ca_cost (ivs);
5001 cp = iv_ca_cand_for_use (ivs, use);
5004 best_delta = iv_ca_delta_add (use, NULL, cp, NULL);
5005 iv_ca_set_no_cp (data, ivs, use);
5008 /* First try important candidates. Only if it fails, try the specific ones.
5009 Rationale -- in loops with many variables the best choice often is to use
5010 just one generic biv. If we added here many ivs specific to the uses,
5011 the optimization algorithm later would be likely to get stuck in a local
5012 minimum, thus causing us to create too many ivs. The approach from
5013 few ivs to more seems more likely to be successful -- starting from few
5014 ivs, replacing an expensive use by a specific iv should always be a
5016 EXECUTE_IF_SET_IN_BITMAP (data->important_candidates, 0, i, bi)
5018 cand = iv_cand (data, i);
5020 if (iv_ca_cand_used_p (ivs, cand))
5023 cp = get_use_iv_cost (data, use, cand);
5027 iv_ca_set_cp (data, ivs, use, cp);
5028 act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
5029 iv_ca_set_no_cp (data, ivs, use);
5030 act_delta = iv_ca_delta_add (use, NULL, cp, act_delta);
5032 if (act_cost < best_cost)
5034 best_cost = act_cost;
5036 iv_ca_delta_free (&best_delta);
5037 best_delta = act_delta;
5040 iv_ca_delta_free (&act_delta);
5043 if (best_cost == INFTY)
5045 for (i = 0; i < use->n_map_members; i++)
5047 cp = use->cost_map + i;
5052 /* Already tried this. */
5053 if (cand->important)
5056 if (iv_ca_cand_used_p (ivs, cand))
5060 iv_ca_set_cp (data, ivs, use, cp);
5061 act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
5062 iv_ca_set_no_cp (data, ivs, use);
5063 act_delta = iv_ca_delta_add (use, iv_ca_cand_for_use (ivs, use),
5066 if (act_cost < best_cost)
5068 best_cost = act_cost;
5071 iv_ca_delta_free (&best_delta);
5072 best_delta = act_delta;
5075 iv_ca_delta_free (&act_delta);
5079 iv_ca_delta_commit (data, ivs, best_delta, true);
5080 iv_ca_delta_free (&best_delta);
5082 return (best_cost != INFTY);
5085 /* Finds an initial assignment of candidates to uses. */
5087 static struct iv_ca *
5088 get_initial_solution (struct ivopts_data *data)
5090 struct iv_ca *ivs = iv_ca_new (data);
5093 for (i = 0; i < n_iv_uses (data); i++)
5094 if (!try_add_cand_for (data, ivs, iv_use (data, i)))
5103 /* Tries to improve set of induction variables IVS. */
5106 try_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs)
5108 unsigned i, acost, best_cost = iv_ca_cost (ivs), n_ivs;
5109 struct iv_ca_delta *best_delta = NULL, *act_delta, *tmp_delta;
5110 struct iv_cand *cand;
5112 /* Try extending the set of induction variables by one. */
5113 for (i = 0; i < n_iv_cands (data); i++)
5115 cand = iv_cand (data, i);
5117 if (iv_ca_cand_used_p (ivs, cand))
5120 acost = iv_ca_extend (data, ivs, cand, &act_delta, &n_ivs);
5124 /* If we successfully added the candidate and the set is small enough,
5125 try optimizing it by removing other candidates. */
5126 if (n_ivs <= ALWAYS_PRUNE_CAND_SET_BOUND)
5128 iv_ca_delta_commit (data, ivs, act_delta, true);
5129 acost = iv_ca_prune (data, ivs, cand, &tmp_delta);
5130 iv_ca_delta_commit (data, ivs, act_delta, false);
5131 act_delta = iv_ca_delta_join (act_delta, tmp_delta);
5134 if (acost < best_cost)
5137 iv_ca_delta_free (&best_delta);
5138 best_delta = act_delta;
5141 iv_ca_delta_free (&act_delta);
5146 /* Try removing the candidates from the set instead. */
5147 best_cost = iv_ca_prune (data, ivs, NULL, &best_delta);
5149 /* Nothing more we can do. */
5154 iv_ca_delta_commit (data, ivs, best_delta, true);
5155 gcc_assert (best_cost == iv_ca_cost (ivs));
5156 iv_ca_delta_free (&best_delta);
5160 /* Attempts to find the optimal set of induction variables. We do simple
5161 greedy heuristic -- we try to replace at most one candidate in the selected
5162 solution and remove the unused ivs while this improves the cost. */
5164 static struct iv_ca *
5165 find_optimal_iv_set (struct ivopts_data *data)
5171 /* Get the initial solution. */
5172 set = get_initial_solution (data);
5175 if (dump_file && (dump_flags & TDF_DETAILS))
5176 fprintf (dump_file, "Unable to substitute for ivs, failed.\n");
5180 if (dump_file && (dump_flags & TDF_DETAILS))
5182 fprintf (dump_file, "Initial set of candidates:\n");
5183 iv_ca_dump (data, dump_file, set);
5186 while (try_improve_iv_set (data, set))
5188 if (dump_file && (dump_flags & TDF_DETAILS))
5190 fprintf (dump_file, "Improved to:\n");
5191 iv_ca_dump (data, dump_file, set);
5195 if (dump_file && (dump_flags & TDF_DETAILS))
5196 fprintf (dump_file, "Final cost %d\n\n", iv_ca_cost (set));
5198 for (i = 0; i < n_iv_uses (data); i++)
5200 use = iv_use (data, i);
5201 use->selected = iv_ca_cand_for_use (set, use)->cand;
5207 /* Creates a new induction variable corresponding to CAND. */
5210 create_new_iv (struct ivopts_data *data, struct iv_cand *cand)
5212 block_stmt_iterator incr_pos;
5222 incr_pos = bsi_last (ip_normal_pos (data->current_loop));
5226 incr_pos = bsi_last (ip_end_pos (data->current_loop));
5231 /* Mark that the iv is preserved. */
5232 name_info (data, cand->var_before)->preserve_biv = true;
5233 name_info (data, cand->var_after)->preserve_biv = true;
5235 /* Rewrite the increment so that it uses var_before directly. */
5236 find_interesting_uses_op (data, cand->var_after)->selected = cand;
5241 gimple_add_tmp_var (cand->var_before);
5242 add_referenced_var (cand->var_before);
5244 base = unshare_expr (cand->iv->base);
5246 create_iv (base, unshare_expr (cand->iv->step),
5247 cand->var_before, data->current_loop,
5248 &incr_pos, after, &cand->var_before, &cand->var_after);
5251 /* Creates new induction variables described in SET. */
5254 create_new_ivs (struct ivopts_data *data, struct iv_ca *set)
5257 struct iv_cand *cand;
5260 EXECUTE_IF_SET_IN_BITMAP (set->cands, 0, i, bi)
5262 cand = iv_cand (data, i);
5263 create_new_iv (data, cand);
5267 /* Removes statement STMT (real or a phi node). If INCLUDING_DEFINED_NAME
5268 is true, remove also the ssa name defined by the statement. */
5271 remove_statement (tree stmt, bool including_defined_name)
5273 if (TREE_CODE (stmt) == PHI_NODE)
5275 if (!including_defined_name)
5277 /* Prevent the ssa name defined by the statement from being removed. */
5278 SET_PHI_RESULT (stmt, NULL);
5280 remove_phi_node (stmt, NULL_TREE);
5284 block_stmt_iterator bsi = bsi_for_stmt (stmt);
5286 bsi_remove (&bsi, true);
5290 /* Rewrites USE (definition of iv used in a nonlinear expression)
5291 using candidate CAND. */
5294 rewrite_use_nonlinear_expr (struct ivopts_data *data,
5295 struct iv_use *use, struct iv_cand *cand)
5298 tree op, stmts, tgt, ass;
5299 block_stmt_iterator bsi, pbsi;
5301 /* An important special case -- if we are asked to express value of
5302 the original iv by itself, just exit; there is no need to
5303 introduce a new computation (that might also need casting the
5304 variable to unsigned and back). */
5305 if (cand->pos == IP_ORIGINAL
5306 && cand->incremented_at == use->stmt)
5308 tree step, ctype, utype;
5309 enum tree_code incr_code = PLUS_EXPR;
5311 gcc_assert (TREE_CODE (use->stmt) == MODIFY_EXPR);
5312 gcc_assert (TREE_OPERAND (use->stmt, 0) == cand->var_after);
5314 step = cand->iv->step;
5315 ctype = TREE_TYPE (step);
5316 utype = TREE_TYPE (cand->var_after);
5317 if (TREE_CODE (step) == NEGATE_EXPR)
5319 incr_code = MINUS_EXPR;
5320 step = TREE_OPERAND (step, 0);
5323 /* Check whether we may leave the computation unchanged.
5324 This is the case only if it does not rely on other
5325 computations in the loop -- otherwise, the computation
5326 we rely upon may be removed in remove_unused_ivs,
5327 thus leading to ICE. */
5328 op = TREE_OPERAND (use->stmt, 1);
5329 if (TREE_CODE (op) == PLUS_EXPR
5330 || TREE_CODE (op) == MINUS_EXPR)
5332 if (TREE_OPERAND (op, 0) == cand->var_before)
5333 op = TREE_OPERAND (op, 1);
5334 else if (TREE_CODE (op) == PLUS_EXPR
5335 && TREE_OPERAND (op, 1) == cand->var_before)
5336 op = TREE_OPERAND (op, 0);
5344 && (TREE_CODE (op) == INTEGER_CST
5345 || operand_equal_p (op, step, 0)))
5348 /* Otherwise, add the necessary computations to express
5350 op = fold_convert (ctype, cand->var_before);
5351 comp = fold_convert (utype,
5352 build2 (incr_code, ctype, op,
5353 unshare_expr (step)));
5356 comp = get_computation (data->current_loop, use, cand);
5358 switch (TREE_CODE (use->stmt))
5361 tgt = PHI_RESULT (use->stmt);
5363 /* If we should keep the biv, do not replace it. */
5364 if (name_info (data, tgt)->preserve_biv)
5367 pbsi = bsi = bsi_start (bb_for_stmt (use->stmt));
5368 while (!bsi_end_p (pbsi)
5369 && TREE_CODE (bsi_stmt (pbsi)) == LABEL_EXPR)
5377 tgt = TREE_OPERAND (use->stmt, 0);
5378 bsi = bsi_for_stmt (use->stmt);
5385 op = force_gimple_operand (comp, &stmts, false, SSA_NAME_VAR (tgt));
5387 if (TREE_CODE (use->stmt) == PHI_NODE)
5390 bsi_insert_after (&bsi, stmts, BSI_CONTINUE_LINKING);
5391 ass = build2 (MODIFY_EXPR, TREE_TYPE (tgt), tgt, op);
5392 bsi_insert_after (&bsi, ass, BSI_NEW_STMT);
5393 remove_statement (use->stmt, false);
5394 SSA_NAME_DEF_STMT (tgt) = ass;
5399 bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
5400 TREE_OPERAND (use->stmt, 1) = op;
5404 /* Replaces ssa name in index IDX by its basic variable. Callback for
5408 idx_remove_ssa_names (tree base, tree *idx,
5409 void *data ATTRIBUTE_UNUSED)
5413 if (TREE_CODE (*idx) == SSA_NAME)
5414 *idx = SSA_NAME_VAR (*idx);
5416 if (TREE_CODE (base) == ARRAY_REF)
5418 op = &TREE_OPERAND (base, 2);
5420 && TREE_CODE (*op) == SSA_NAME)
5421 *op = SSA_NAME_VAR (*op);
5422 op = &TREE_OPERAND (base, 3);
5424 && TREE_CODE (*op) == SSA_NAME)
5425 *op = SSA_NAME_VAR (*op);
5431 /* Unshares REF and replaces ssa names inside it by their basic variables. */
5434 unshare_and_remove_ssa_names (tree ref)
5436 ref = unshare_expr (ref);
5437 for_each_index (&ref, idx_remove_ssa_names, NULL);
5442 /* Extract the alias analysis info for the memory reference REF. There are
5443 several ways how this information may be stored and what precisely is
5444 its semantics depending on the type of the reference, but there always is
5445 somewhere hidden one _DECL node that is used to determine the set of
5446 virtual operands for the reference. The code below deciphers this jungle
5447 and extracts this single useful piece of information. */
5450 get_ref_tag (tree ref, tree orig)
5452 tree var = get_base_address (ref);
5453 tree aref = NULL_TREE, tag, sv;
5454 HOST_WIDE_INT offset, size, maxsize;
5456 for (sv = orig; handled_component_p (sv); sv = TREE_OPERAND (sv, 0))
5458 aref = get_ref_base_and_extent (sv, &offset, &size, &maxsize);
5463 if (aref && SSA_VAR_P (aref) && get_subvars_for_var (aref))
5464 return unshare_expr (sv);
5469 if (TREE_CODE (var) == INDIRECT_REF)
5471 /* If the base is a dereference of a pointer, first check its name memory
5472 tag. If it does not have one, use its symbol memory tag. */
5473 var = TREE_OPERAND (var, 0);
5474 if (TREE_CODE (var) != SSA_NAME)
5477 if (SSA_NAME_PTR_INFO (var))
5479 tag = SSA_NAME_PTR_INFO (var)->name_mem_tag;
5484 var = SSA_NAME_VAR (var);
5485 tag = var_ann (var)->symbol_mem_tag;
5486 gcc_assert (tag != NULL_TREE);
5494 tag = var_ann (var)->symbol_mem_tag;
5502 /* Copies the reference information from OLD_REF to NEW_REF. */
5505 copy_ref_info (tree new_ref, tree old_ref)
5507 if (TREE_CODE (old_ref) == TARGET_MEM_REF)
5508 copy_mem_ref_info (new_ref, old_ref);
5511 TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
5512 TMR_TAG (new_ref) = get_ref_tag (old_ref, TMR_ORIGINAL (new_ref));
5516 /* Rewrites USE (address that is an iv) using candidate CAND. */
5519 rewrite_use_address (struct ivopts_data *data,
5520 struct iv_use *use, struct iv_cand *cand)
5522 struct affine_tree_combination aff;
5523 block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
5526 get_computation_aff (data->current_loop, use, cand, use->stmt, &aff);
5527 unshare_aff_combination (&aff);
5529 ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff);
5530 copy_ref_info (ref, *use->op_p);
5534 /* Rewrites USE (the condition such that one of the arguments is an iv) using
5538 rewrite_use_compare (struct ivopts_data *data,
5539 struct iv_use *use, struct iv_cand *cand)
5542 tree *op_p, cond, op, stmts, bound;
5543 block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
5544 enum tree_code compare;
5545 struct cost_pair *cp = get_use_iv_cost (data, use, cand);
5550 tree var = var_at_stmt (data->current_loop, cand, use->stmt);
5551 tree var_type = TREE_TYPE (var);
5553 compare = iv_elimination_compare (data, use);
5554 bound = fold_convert (var_type, bound);
5555 op = force_gimple_operand (unshare_expr (bound), &stmts,
5559 bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
5561 *use->op_p = build2 (compare, boolean_type_node, var, op);
5562 update_stmt (use->stmt);
5566 /* The induction variable elimination failed; just express the original
5568 comp = get_computation (data->current_loop, use, cand);
5571 op_p = &TREE_OPERAND (cond, 0);
5572 if (TREE_CODE (*op_p) != SSA_NAME
5573 || zero_p (get_iv (data, *op_p)->step))
5574 op_p = &TREE_OPERAND (cond, 1);
5576 op = force_gimple_operand (comp, &stmts, true, SSA_NAME_VAR (*op_p));
5578 bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
5583 /* Rewrites USE using candidate CAND. */
5586 rewrite_use (struct ivopts_data *data,
5587 struct iv_use *use, struct iv_cand *cand)
5591 case USE_NONLINEAR_EXPR:
5592 rewrite_use_nonlinear_expr (data, use, cand);
5596 rewrite_use_address (data, use, cand);
5600 rewrite_use_compare (data, use, cand);
5606 mark_new_vars_to_rename (use->stmt);
5609 /* Rewrite the uses using the selected induction variables. */
5612 rewrite_uses (struct ivopts_data *data)
5615 struct iv_cand *cand;
5618 for (i = 0; i < n_iv_uses (data); i++)
5620 use = iv_use (data, i);
5621 cand = use->selected;
5624 rewrite_use (data, use, cand);
5628 /* Removes the ivs that are not used after rewriting. */
5631 remove_unused_ivs (struct ivopts_data *data)
5636 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
5638 struct version_info *info;
5640 info = ver_info (data, j);
5642 && !zero_p (info->iv->step)
5644 && !info->iv->have_use_for
5645 && !info->preserve_biv)
5646 remove_statement (SSA_NAME_DEF_STMT (info->iv->ssa_name), true);
5650 /* Frees data allocated by the optimization of a single loop. */
5653 free_loop_data (struct ivopts_data *data)
5659 htab_empty (data->niters);
5661 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
5663 struct version_info *info;
5665 info = ver_info (data, i);
5669 info->has_nonlin_use = false;
5670 info->preserve_biv = false;
5673 bitmap_clear (data->relevant);
5674 bitmap_clear (data->important_candidates);
5676 for (i = 0; i < n_iv_uses (data); i++)
5678 struct iv_use *use = iv_use (data, i);
5681 BITMAP_FREE (use->related_cands);
5682 for (j = 0; j < use->n_map_members; j++)
5683 if (use->cost_map[j].depends_on)
5684 BITMAP_FREE (use->cost_map[j].depends_on);
5685 free (use->cost_map);
5688 VEC_truncate (iv_use_p, data->iv_uses, 0);
5690 for (i = 0; i < n_iv_cands (data); i++)
5692 struct iv_cand *cand = iv_cand (data, i);
5696 if (cand->depends_on)
5697 BITMAP_FREE (cand->depends_on);
5700 VEC_truncate (iv_cand_p, data->iv_candidates, 0);
5702 if (data->version_info_size < num_ssa_names)
5704 data->version_info_size = 2 * num_ssa_names;
5705 free (data->version_info);
5706 data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
5709 data->max_inv_id = 0;
5711 for (i = 0; VEC_iterate (tree, decl_rtl_to_reset, i, obj); i++)
5712 SET_DECL_RTL (obj, NULL_RTX);
5714 VEC_truncate (tree, decl_rtl_to_reset, 0);
5717 /* Finalizes data structures used by the iv optimization pass. LOOPS is the
5721 tree_ssa_iv_optimize_finalize (struct ivopts_data *data)
5723 free_loop_data (data);
5724 free (data->version_info);
5725 BITMAP_FREE (data->relevant);
5726 BITMAP_FREE (data->important_candidates);
5727 htab_delete (data->niters);
5729 VEC_free (tree, heap, decl_rtl_to_reset);
5730 VEC_free (iv_use_p, heap, data->iv_uses);
5731 VEC_free (iv_cand_p, heap, data->iv_candidates);
5734 /* Optimizes the LOOP. Returns true if anything changed. */
5737 tree_ssa_iv_optimize_loop (struct ivopts_data *data, struct loop *loop)
5739 bool changed = false;
5740 struct iv_ca *iv_ca;
5743 data->current_loop = loop;
5745 if (dump_file && (dump_flags & TDF_DETAILS))
5747 fprintf (dump_file, "Processing loop %d\n", loop->num);
5749 exit = single_dom_exit (loop);
5752 fprintf (dump_file, " single exit %d -> %d, exit condition ",
5753 exit->src->index, exit->dest->index);
5754 print_generic_expr (dump_file, last_stmt (exit->src), TDF_SLIM);
5755 fprintf (dump_file, "\n");
5758 fprintf (dump_file, "\n");
5761 /* For each ssa name determines whether it behaves as an induction variable
5763 if (!find_induction_variables (data))
5766 /* Finds interesting uses (item 1). */
5767 find_interesting_uses (data);
5768 if (n_iv_uses (data) > MAX_CONSIDERED_USES)
5771 /* Finds candidates for the induction variables (item 2). */
5772 find_iv_candidates (data);
5774 /* Calculates the costs (item 3, part 1). */
5775 determine_use_iv_costs (data);
5776 determine_iv_costs (data);
5777 determine_set_costs (data);
5779 /* Find the optimal set of induction variables (item 3, part 2). */
5780 iv_ca = find_optimal_iv_set (data);
5785 /* Create the new induction variables (item 4, part 1). */
5786 create_new_ivs (data, iv_ca);
5787 iv_ca_free (&iv_ca);
5789 /* Rewrite the uses (item 4, part 2). */
5790 rewrite_uses (data);
5792 /* Remove the ivs that are unused after rewriting. */
5793 remove_unused_ivs (data);
5795 /* We have changed the structure of induction variables; it might happen
5796 that definitions in the scev database refer to some of them that were
5801 free_loop_data (data);
5806 /* Main entry point. Optimizes induction variables in LOOPS. */
5809 tree_ssa_iv_optimize (struct loops *loops)
5812 struct ivopts_data data;
5814 tree_ssa_iv_optimize_init (&data);
5816 /* Optimize the loops starting with the innermost ones. */
5817 loop = loops->tree_root;
5821 /* Scan the loops, inner ones first. */
5822 while (loop != loops->tree_root)
5824 if (dump_file && (dump_flags & TDF_DETAILS))
5825 flow_loop_dump (loop, dump_file, NULL, 1);
5827 tree_ssa_iv_optimize_loop (&data, loop);
5839 tree_ssa_iv_optimize_finalize (&data);