1 /* Induction variable optimizations.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 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 3, 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 COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This pass tries to find the optimal set of induction variables for the loop.
21 It optimizes just the basic linear induction variables (although adding
22 support for other types should not be too hard). It includes the
23 optimizations commonly known as strength reduction, induction variable
24 coalescing and induction variable elimination. It does it in the
27 1) The interesting uses of induction variables are found. This includes
29 -- uses of induction variables in non-linear expressions
30 -- addresses of arrays
31 -- comparisons of induction variables
33 2) Candidates for the induction variables are found. This includes
35 -- old induction variables
36 -- the variables defined by expressions derived from the "interesting
39 3) The optimal (w.r. to a cost function) set of variables is chosen. The
40 cost function assigns a cost to sets of induction variables and consists
43 -- The use costs. Each of the interesting uses chooses the best induction
44 variable in the set and adds its cost to the sum. The cost reflects
45 the time spent on modifying the induction variables value to be usable
46 for the given purpose (adding base and offset for arrays, etc.).
47 -- The variable costs. Each of the variables has a cost assigned that
48 reflects the costs associated with incrementing the value of the
49 variable. The original variables are somewhat preferred.
50 -- The set cost. Depending on the size of the set, extra cost may be
51 added to reflect register pressure.
53 All the costs are defined in a machine-specific way, using the target
54 hooks and machine descriptions to determine them.
56 4) The trees are transformed to use the new variables, the dead code is
59 All of this is done loop by loop. Doing it globally is theoretically
60 possible, it might give a better performance and it might enable us
61 to decide costs more precisely, but getting all the interactions right
62 would be complicated. */
66 #include "coretypes.h"
71 #include "hard-reg-set.h"
72 #include "basic-block.h"
74 #include "diagnostic.h"
75 #include "tree-flow.h"
76 #include "tree-dump.h"
81 #include "tree-pass.h"
83 #include "insn-config.h"
85 #include "pointer-set.h"
87 #include "tree-chrec.h"
88 #include "tree-scalar-evolution.h"
91 #include "langhooks.h"
92 #include "tree-affine.h"
95 /* The infinite cost. */
96 #define INFTY 10000000
98 /* The expected number of loop iterations. TODO -- use profiling instead of
100 #define AVG_LOOP_NITER(LOOP) 5
103 /* Representation of the induction variable. */
106 tree base; /* Initial value of the iv. */
107 tree base_object; /* A memory object to that the induction variable points. */
108 tree step; /* Step of the iv (constant only). */
109 tree ssa_name; /* The ssa name with the value. */
110 bool biv_p; /* Is it a biv? */
111 bool have_use_for; /* Do we already have a use for it? */
112 unsigned use_id; /* The identifier in the use if it is the case. */
115 /* Per-ssa version information (induction variable descriptions, etc.). */
118 tree name; /* The ssa name. */
119 struct iv *iv; /* Induction variable description. */
120 bool has_nonlin_use; /* For a loop-level invariant, whether it is used in
121 an expression that is not an induction variable. */
122 unsigned inv_id; /* Id of an invariant. */
123 bool preserve_biv; /* For the original biv, whether to preserve it. */
129 USE_NONLINEAR_EXPR, /* Use in a nonlinear expression. */
130 USE_ADDRESS, /* Use in an address. */
131 USE_COMPARE /* Use is a compare. */
134 /* Cost of a computation. */
137 unsigned cost; /* The runtime cost. */
138 unsigned complexity; /* The estimate of the complexity of the code for
139 the computation (in no concrete units --
140 complexity field should be larger for more
141 complex expressions and addressing modes). */
144 static const comp_cost zero_cost = {0, 0};
145 static const comp_cost infinite_cost = {INFTY, INFTY};
147 /* The candidate - cost pair. */
150 struct iv_cand *cand; /* The candidate. */
151 comp_cost cost; /* The cost. */
152 bitmap depends_on; /* The list of invariants that have to be
154 tree value; /* For final value elimination, the expression for
155 the final value of the iv. For iv elimination,
156 the new bound to compare with. */
162 unsigned id; /* The id of the use. */
163 enum use_type type; /* Type of the use. */
164 struct iv *iv; /* The induction variable it is based on. */
165 tree stmt; /* Statement in that it occurs. */
166 tree *op_p; /* The place where it occurs. */
167 bitmap related_cands; /* The set of "related" iv candidates, plus the common
170 unsigned n_map_members; /* Number of candidates in the cost_map list. */
171 struct cost_pair *cost_map;
172 /* The costs wrto the iv candidates. */
174 struct iv_cand *selected;
175 /* The selected candidate. */
178 /* The position where the iv is computed. */
181 IP_NORMAL, /* At the end, just before the exit condition. */
182 IP_END, /* At the end of the latch block. */
183 IP_ORIGINAL /* The original biv. */
186 /* The induction variable candidate. */
189 unsigned id; /* The number of the candidate. */
190 bool important; /* Whether this is an "important" candidate, i.e. such
191 that it should be considered by all uses. */
192 enum iv_position pos; /* Where it is computed. */
193 tree incremented_at; /* For original biv, the statement where it is
195 tree var_before; /* The variable used for it before increment. */
196 tree var_after; /* The variable used for it after increment. */
197 struct iv *iv; /* The value of the candidate. NULL for
198 "pseudocandidate" used to indicate the possibility
199 to replace the final value of an iv by direct
200 computation of the value. */
201 unsigned cost; /* Cost of the candidate. */
202 bitmap depends_on; /* The list of invariants that are used in step of the
206 /* The data used by the induction variable optimizations. */
208 typedef struct iv_use *iv_use_p;
210 DEF_VEC_ALLOC_P(iv_use_p,heap);
212 typedef struct iv_cand *iv_cand_p;
213 DEF_VEC_P(iv_cand_p);
214 DEF_VEC_ALLOC_P(iv_cand_p,heap);
218 /* The currently optimized loop. */
219 struct loop *current_loop;
221 /* Number of registers used in it. */
224 /* Numbers of iterations for all exits of the current loop. */
225 struct pointer_map_t *niters;
227 /* The size of version_info array allocated. */
228 unsigned version_info_size;
230 /* The array of information for the ssa names. */
231 struct version_info *version_info;
233 /* The bitmap of indices in version_info whose value was changed. */
236 /* The maximum invariant id. */
239 /* The uses of induction variables. */
240 VEC(iv_use_p,heap) *iv_uses;
242 /* The candidates. */
243 VEC(iv_cand_p,heap) *iv_candidates;
245 /* A bitmap of important candidates. */
246 bitmap important_candidates;
248 /* Whether to consider just related and important candidates when replacing a
250 bool consider_all_candidates;
253 /* An assignment of iv candidates to uses. */
257 /* The number of uses covered by the assignment. */
260 /* Number of uses that cannot be expressed by the candidates in the set. */
263 /* Candidate assigned to a use, together with the related costs. */
264 struct cost_pair **cand_for_use;
266 /* Number of times each candidate is used. */
267 unsigned *n_cand_uses;
269 /* The candidates used. */
272 /* The number of candidates in the set. */
275 /* Total number of registers needed. */
278 /* Total cost of expressing uses. */
279 comp_cost cand_use_cost;
281 /* Total cost of candidates. */
284 /* Number of times each invariant is used. */
285 unsigned *n_invariant_uses;
287 /* Total cost of the assignment. */
291 /* Difference of two iv candidate assignments. */
298 /* An old assignment (for rollback purposes). */
299 struct cost_pair *old_cp;
301 /* A new assignment. */
302 struct cost_pair *new_cp;
304 /* Next change in the list. */
305 struct iv_ca_delta *next_change;
308 /* Bound on number of candidates below that all candidates are considered. */
310 #define CONSIDER_ALL_CANDIDATES_BOUND \
311 ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
313 /* If there are more iv occurrences, we just give up (it is quite unlikely that
314 optimizing such a loop would help, and it would take ages). */
316 #define MAX_CONSIDERED_USES \
317 ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
319 /* If there are at most this number of ivs in the set, try removing unnecessary
320 ivs from the set always. */
322 #define ALWAYS_PRUNE_CAND_SET_BOUND \
323 ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
325 /* The list of trees for that the decl_rtl field must be reset is stored
328 static VEC(tree,heap) *decl_rtl_to_reset;
330 /* Number of uses recorded in DATA. */
332 static inline unsigned
333 n_iv_uses (struct ivopts_data *data)
335 return VEC_length (iv_use_p, data->iv_uses);
338 /* Ith use recorded in DATA. */
340 static inline struct iv_use *
341 iv_use (struct ivopts_data *data, unsigned i)
343 return VEC_index (iv_use_p, data->iv_uses, i);
346 /* Number of candidates recorded in DATA. */
348 static inline unsigned
349 n_iv_cands (struct ivopts_data *data)
351 return VEC_length (iv_cand_p, data->iv_candidates);
354 /* Ith candidate recorded in DATA. */
356 static inline struct iv_cand *
357 iv_cand (struct ivopts_data *data, unsigned i)
359 return VEC_index (iv_cand_p, data->iv_candidates, i);
362 /* The single loop exit if it dominates the latch, NULL otherwise. */
365 single_dom_exit (struct loop *loop)
367 edge exit = single_exit (loop);
372 if (!just_once_each_iteration_p (loop, exit->src))
378 /* Dumps information about the induction variable IV to FILE. */
380 extern void dump_iv (FILE *, struct iv *);
382 dump_iv (FILE *file, struct iv *iv)
386 fprintf (file, "ssa name ");
387 print_generic_expr (file, iv->ssa_name, TDF_SLIM);
388 fprintf (file, "\n");
391 fprintf (file, " type ");
392 print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
393 fprintf (file, "\n");
397 fprintf (file, " base ");
398 print_generic_expr (file, iv->base, TDF_SLIM);
399 fprintf (file, "\n");
401 fprintf (file, " step ");
402 print_generic_expr (file, iv->step, TDF_SLIM);
403 fprintf (file, "\n");
407 fprintf (file, " invariant ");
408 print_generic_expr (file, iv->base, TDF_SLIM);
409 fprintf (file, "\n");
414 fprintf (file, " base object ");
415 print_generic_expr (file, iv->base_object, TDF_SLIM);
416 fprintf (file, "\n");
420 fprintf (file, " is a biv\n");
423 /* Dumps information about the USE to FILE. */
425 extern void dump_use (FILE *, struct iv_use *);
427 dump_use (FILE *file, struct iv_use *use)
429 fprintf (file, "use %d\n", use->id);
433 case USE_NONLINEAR_EXPR:
434 fprintf (file, " generic\n");
438 fprintf (file, " address\n");
442 fprintf (file, " compare\n");
449 fprintf (file, " in statement ");
450 print_generic_expr (file, use->stmt, TDF_SLIM);
451 fprintf (file, "\n");
453 fprintf (file, " at position ");
455 print_generic_expr (file, *use->op_p, TDF_SLIM);
456 fprintf (file, "\n");
458 dump_iv (file, use->iv);
460 if (use->related_cands)
462 fprintf (file, " related candidates ");
463 dump_bitmap (file, use->related_cands);
467 /* Dumps information about the uses to FILE. */
469 extern void dump_uses (FILE *, struct ivopts_data *);
471 dump_uses (FILE *file, struct ivopts_data *data)
476 for (i = 0; i < n_iv_uses (data); i++)
478 use = iv_use (data, i);
480 dump_use (file, use);
481 fprintf (file, "\n");
485 /* Dumps information about induction variable candidate CAND to FILE. */
487 extern void dump_cand (FILE *, struct iv_cand *);
489 dump_cand (FILE *file, struct iv_cand *cand)
491 struct iv *iv = cand->iv;
493 fprintf (file, "candidate %d%s\n",
494 cand->id, cand->important ? " (important)" : "");
496 if (cand->depends_on)
498 fprintf (file, " depends on ");
499 dump_bitmap (file, cand->depends_on);
504 fprintf (file, " final value replacement\n");
511 fprintf (file, " incremented before exit test\n");
515 fprintf (file, " incremented at end\n");
519 fprintf (file, " original biv\n");
526 /* Returns the info for ssa version VER. */
528 static inline struct version_info *
529 ver_info (struct ivopts_data *data, unsigned ver)
531 return data->version_info + ver;
534 /* Returns the info for ssa name NAME. */
536 static inline struct version_info *
537 name_info (struct ivopts_data *data, tree name)
539 return ver_info (data, SSA_NAME_VERSION (name));
542 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
546 stmt_after_ip_normal_pos (struct loop *loop, tree stmt)
548 basic_block bb = ip_normal_pos (loop), sbb = bb_for_stmt (stmt);
552 if (sbb == loop->latch)
558 return stmt == last_stmt (bb);
561 /* Returns true if STMT if after the place where the original induction
562 variable CAND is incremented. */
565 stmt_after_ip_original_pos (struct iv_cand *cand, tree stmt)
567 basic_block cand_bb = bb_for_stmt (cand->incremented_at);
568 basic_block stmt_bb = bb_for_stmt (stmt);
569 block_stmt_iterator bsi;
571 if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
574 if (stmt_bb != cand_bb)
577 /* Scan the block from the end, since the original ivs are usually
578 incremented at the end of the loop body. */
579 for (bsi = bsi_last (stmt_bb); ; bsi_prev (&bsi))
581 if (bsi_stmt (bsi) == cand->incremented_at)
583 if (bsi_stmt (bsi) == stmt)
588 /* Returns true if STMT if after the place where the induction variable
589 CAND is incremented in LOOP. */
592 stmt_after_increment (struct loop *loop, struct iv_cand *cand, tree stmt)
600 return stmt_after_ip_normal_pos (loop, stmt);
603 return stmt_after_ip_original_pos (cand, stmt);
610 /* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
613 abnormal_ssa_name_p (tree exp)
618 if (TREE_CODE (exp) != SSA_NAME)
621 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) != 0;
624 /* Returns false if BASE or INDEX contains a ssa name that occurs in an
625 abnormal phi node. Callback for for_each_index. */
628 idx_contains_abnormal_ssa_name_p (tree base, tree *index,
629 void *data ATTRIBUTE_UNUSED)
631 if (TREE_CODE (base) == ARRAY_REF)
633 if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
635 if (abnormal_ssa_name_p (TREE_OPERAND (base, 3)))
639 return !abnormal_ssa_name_p (*index);
642 /* Returns true if EXPR contains a ssa name that occurs in an
643 abnormal phi node. */
646 contains_abnormal_ssa_name_p (tree expr)
649 enum tree_code_class codeclass;
654 code = TREE_CODE (expr);
655 codeclass = TREE_CODE_CLASS (code);
657 if (code == SSA_NAME)
658 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
660 if (code == INTEGER_CST
661 || is_gimple_min_invariant (expr))
664 if (code == ADDR_EXPR)
665 return !for_each_index (&TREE_OPERAND (expr, 0),
666 idx_contains_abnormal_ssa_name_p,
673 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1)))
678 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0)))
690 /* Returns tree describing number of iterations determined from
691 EXIT of DATA->current_loop, or NULL if something goes wrong. */
694 niter_for_exit (struct ivopts_data *data, edge exit)
696 struct tree_niter_desc desc;
702 data->niters = pointer_map_create ();
706 slot = pointer_map_contains (data->niters, exit);
710 /* Try to determine number of iterations. We must know it
711 unconditionally (i.e., without possibility of # of iterations
712 being zero). Also, we cannot safely work with ssa names that
713 appear in phi nodes on abnormal edges, so that we do not create
714 overlapping life ranges for them (PR 27283). */
715 if (number_of_iterations_exit (data->current_loop,
717 && integer_zerop (desc.may_be_zero)
718 && !contains_abnormal_ssa_name_p (desc.niter))
723 *pointer_map_insert (data->niters, exit) = niter;
726 niter = (tree) *slot;
731 /* Returns tree describing number of iterations determined from
732 single dominating exit of DATA->current_loop, or NULL if something
736 niter_for_single_dom_exit (struct ivopts_data *data)
738 edge exit = single_dom_exit (data->current_loop);
743 return niter_for_exit (data, exit);
746 /* Initializes data structures used by the iv optimization pass, stored
750 tree_ssa_iv_optimize_init (struct ivopts_data *data)
752 data->version_info_size = 2 * num_ssa_names;
753 data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
754 data->relevant = BITMAP_ALLOC (NULL);
755 data->important_candidates = BITMAP_ALLOC (NULL);
756 data->max_inv_id = 0;
758 data->iv_uses = VEC_alloc (iv_use_p, heap, 20);
759 data->iv_candidates = VEC_alloc (iv_cand_p, heap, 20);
760 decl_rtl_to_reset = VEC_alloc (tree, heap, 20);
763 /* Returns a memory object to that EXPR points. In case we are able to
764 determine that it does not point to any such object, NULL is returned. */
767 determine_base_object (tree expr)
769 enum tree_code code = TREE_CODE (expr);
772 /* If this is a pointer casted to any type, we need to determine
773 the base object for the pointer; so handle conversions before
774 throwing away non-pointer expressions. */
775 if (TREE_CODE (expr) == NOP_EXPR
776 || TREE_CODE (expr) == CONVERT_EXPR)
777 return determine_base_object (TREE_OPERAND (expr, 0));
779 if (!POINTER_TYPE_P (TREE_TYPE (expr)))
788 obj = TREE_OPERAND (expr, 0);
789 base = get_base_address (obj);
794 if (TREE_CODE (base) == INDIRECT_REF)
795 return determine_base_object (TREE_OPERAND (base, 0));
797 return fold_convert (ptr_type_node,
798 build_fold_addr_expr (base));
800 case POINTER_PLUS_EXPR:
801 return determine_base_object (TREE_OPERAND (expr, 0));
805 /* Pointer addition is done solely using POINTER_PLUS_EXPR. */
809 return fold_convert (ptr_type_node, expr);
813 /* Allocates an induction variable with given initial value BASE and step STEP
817 alloc_iv (tree base, tree step)
819 struct iv *iv = XCNEW (struct iv);
820 gcc_assert (step != NULL_TREE);
823 iv->base_object = determine_base_object (base);
826 iv->have_use_for = false;
828 iv->ssa_name = NULL_TREE;
833 /* Sets STEP and BASE for induction variable IV. */
836 set_iv (struct ivopts_data *data, tree iv, tree base, tree step)
838 struct version_info *info = name_info (data, iv);
840 gcc_assert (!info->iv);
842 bitmap_set_bit (data->relevant, SSA_NAME_VERSION (iv));
843 info->iv = alloc_iv (base, step);
844 info->iv->ssa_name = iv;
847 /* Finds induction variable declaration for VAR. */
850 get_iv (struct ivopts_data *data, tree var)
853 tree type = TREE_TYPE (var);
855 if (!POINTER_TYPE_P (type)
856 && !INTEGRAL_TYPE_P (type))
859 if (!name_info (data, var)->iv)
861 bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
864 || !flow_bb_inside_loop_p (data->current_loop, bb))
865 set_iv (data, var, var, build_int_cst (type, 0));
868 return name_info (data, var)->iv;
871 /* Determines the step of a biv defined in PHI. Returns NULL if PHI does
872 not define a simple affine biv with nonzero step. */
875 determine_biv_step (tree phi)
877 struct loop *loop = bb_for_stmt (phi)->loop_father;
878 tree name = PHI_RESULT (phi);
881 if (!is_gimple_reg (name))
884 if (!simple_iv (loop, phi, name, &iv, true))
887 return integer_zerop (iv.step) ? NULL_TREE : iv.step;
890 /* Finds basic ivs. */
893 find_bivs (struct ivopts_data *data)
895 tree phi, step, type, base;
897 struct loop *loop = data->current_loop;
899 for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
901 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
904 step = determine_biv_step (phi);
908 base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
909 base = expand_simple_operations (base);
910 if (contains_abnormal_ssa_name_p (base)
911 || contains_abnormal_ssa_name_p (step))
914 type = TREE_TYPE (PHI_RESULT (phi));
915 base = fold_convert (type, base);
917 step = fold_convert (type, step);
919 set_iv (data, PHI_RESULT (phi), base, step);
926 /* Marks basic ivs. */
929 mark_bivs (struct ivopts_data *data)
932 struct iv *iv, *incr_iv;
933 struct loop *loop = data->current_loop;
936 for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
938 iv = get_iv (data, PHI_RESULT (phi));
942 var = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
943 incr_iv = get_iv (data, var);
947 /* If the increment is in the subloop, ignore it. */
948 incr_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
949 if (incr_bb->loop_father != data->current_loop
950 || (incr_bb->flags & BB_IRREDUCIBLE_LOOP))
954 incr_iv->biv_p = true;
958 /* Checks whether STMT defines a linear induction variable and stores its
962 find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt, affine_iv *iv)
965 struct loop *loop = data->current_loop;
967 iv->base = NULL_TREE;
968 iv->step = NULL_TREE;
970 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
973 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
974 if (TREE_CODE (lhs) != SSA_NAME)
977 if (!simple_iv (loop, stmt, GIMPLE_STMT_OPERAND (stmt, 1), iv, true))
979 iv->base = expand_simple_operations (iv->base);
981 if (contains_abnormal_ssa_name_p (iv->base)
982 || contains_abnormal_ssa_name_p (iv->step))
988 /* Finds general ivs in statement STMT. */
991 find_givs_in_stmt (struct ivopts_data *data, tree stmt)
995 if (!find_givs_in_stmt_scev (data, stmt, &iv))
998 set_iv (data, GIMPLE_STMT_OPERAND (stmt, 0), iv.base, iv.step);
1001 /* Finds general ivs in basic block BB. */
1004 find_givs_in_bb (struct ivopts_data *data, basic_block bb)
1006 block_stmt_iterator bsi;
1008 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1009 find_givs_in_stmt (data, bsi_stmt (bsi));
1012 /* Finds general ivs. */
1015 find_givs (struct ivopts_data *data)
1017 struct loop *loop = data->current_loop;
1018 basic_block *body = get_loop_body_in_dom_order (loop);
1021 for (i = 0; i < loop->num_nodes; i++)
1022 find_givs_in_bb (data, body[i]);
1026 /* For each ssa name defined in LOOP determines whether it is an induction
1027 variable and if so, its initial value and step. */
1030 find_induction_variables (struct ivopts_data *data)
1035 if (!find_bivs (data))
1041 if (dump_file && (dump_flags & TDF_DETAILS))
1043 tree niter = niter_for_single_dom_exit (data);
1047 fprintf (dump_file, " number of iterations ");
1048 print_generic_expr (dump_file, niter, TDF_SLIM);
1049 fprintf (dump_file, "\n\n");
1052 fprintf (dump_file, "Induction variables:\n\n");
1054 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
1056 if (ver_info (data, i)->iv)
1057 dump_iv (dump_file, ver_info (data, i)->iv);
1064 /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV. */
1066 static struct iv_use *
1067 record_use (struct ivopts_data *data, tree *use_p, struct iv *iv,
1068 tree stmt, enum use_type use_type)
1070 struct iv_use *use = XCNEW (struct iv_use);
1072 use->id = n_iv_uses (data);
1073 use->type = use_type;
1077 use->related_cands = BITMAP_ALLOC (NULL);
1079 /* To avoid showing ssa name in the dumps, if it was not reset by the
1081 iv->ssa_name = NULL_TREE;
1083 if (dump_file && (dump_flags & TDF_DETAILS))
1084 dump_use (dump_file, use);
1086 VEC_safe_push (iv_use_p, heap, data->iv_uses, use);
1091 /* Checks whether OP is a loop-level invariant and if so, records it.
1092 NONLINEAR_USE is true if the invariant is used in a way we do not
1093 handle specially. */
1096 record_invariant (struct ivopts_data *data, tree op, bool nonlinear_use)
1099 struct version_info *info;
1101 if (TREE_CODE (op) != SSA_NAME
1102 || !is_gimple_reg (op))
1105 bb = bb_for_stmt (SSA_NAME_DEF_STMT (op));
1107 && flow_bb_inside_loop_p (data->current_loop, bb))
1110 info = name_info (data, op);
1112 info->has_nonlin_use |= nonlinear_use;
1114 info->inv_id = ++data->max_inv_id;
1115 bitmap_set_bit (data->relevant, SSA_NAME_VERSION (op));
1118 /* Checks whether the use OP is interesting and if so, records it. */
1120 static struct iv_use *
1121 find_interesting_uses_op (struct ivopts_data *data, tree op)
1128 if (TREE_CODE (op) != SSA_NAME)
1131 iv = get_iv (data, op);
1135 if (iv->have_use_for)
1137 use = iv_use (data, iv->use_id);
1139 gcc_assert (use->type == USE_NONLINEAR_EXPR);
1143 if (integer_zerop (iv->step))
1145 record_invariant (data, op, true);
1148 iv->have_use_for = true;
1150 civ = XNEW (struct iv);
1153 stmt = SSA_NAME_DEF_STMT (op);
1154 gcc_assert (TREE_CODE (stmt) == PHI_NODE
1155 || TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
1157 use = record_use (data, NULL, civ, stmt, USE_NONLINEAR_EXPR);
1158 iv->use_id = use->id;
1163 /* Given a condition *COND_P, checks whether it is a compare of an induction
1164 variable and an invariant. If this is the case, CONTROL_VAR is set
1165 to location of the iv, BOUND to the location of the invariant,
1166 IV_VAR and IV_BOUND are set to the corresponding induction variable
1167 descriptions, and true is returned. If this is not the case,
1168 CONTROL_VAR and BOUND are set to the arguments of the condition and
1169 false is returned. */
1172 extract_cond_operands (struct ivopts_data *data, tree *cond_p,
1173 tree **control_var, tree **bound,
1174 struct iv **iv_var, struct iv **iv_bound)
1176 /* The nodes returned when COND has just one operand. Note that you should
1177 not modify anything in BOUND or IV_BOUND because of this. */
1178 static struct iv const_iv;
1180 tree cond = *cond_p;
1181 tree *op0 = &zero, *op1 = &zero, *tmp_op;
1182 struct iv *iv0 = &const_iv, *iv1 = &const_iv, *tmp_iv;
1185 zero = integer_zero_node;
1186 const_iv.step = integer_zero_node;
1188 if (TREE_CODE (cond) == SSA_NAME)
1191 iv0 = get_iv (data, cond);
1192 ret = (iv0 && !integer_zerop (iv0->step));
1196 if (!COMPARISON_CLASS_P (cond))
1202 op0 = &TREE_OPERAND (cond, 0);
1203 op1 = &TREE_OPERAND (cond, 1);
1204 if (TREE_CODE (*op0) == SSA_NAME)
1205 iv0 = get_iv (data, *op0);
1206 if (TREE_CODE (*op1) == SSA_NAME)
1207 iv1 = get_iv (data, *op1);
1209 /* Exactly one of the compared values must be an iv, and the other one must
1214 if (integer_zerop (iv0->step))
1216 /* Control variable may be on the other side. */
1217 tmp_op = op0; op0 = op1; op1 = tmp_op;
1218 tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
1220 ret = !integer_zerop (iv0->step) && integer_zerop (iv1->step);
1224 *control_var = op0;;
1235 /* Checks whether the condition *COND_P in STMT is interesting
1236 and if so, records it. */
1239 find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
1241 tree *var_p, *bound_p;
1242 struct iv *var_iv, *civ;
1244 if (!extract_cond_operands (data, cond_p, &var_p, &bound_p, &var_iv, NULL))
1246 find_interesting_uses_op (data, *var_p);
1247 find_interesting_uses_op (data, *bound_p);
1251 civ = XNEW (struct iv);
1253 record_use (data, cond_p, civ, stmt, USE_COMPARE);
1256 /* Returns true if expression EXPR is obviously invariant in LOOP,
1257 i.e. if all its operands are defined outside of the LOOP. */
1260 expr_invariant_in_loop_p (struct loop *loop, tree expr)
1265 if (is_gimple_min_invariant (expr))
1268 if (TREE_CODE (expr) == SSA_NAME)
1270 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (expr));
1272 && flow_bb_inside_loop_p (loop, def_bb))
1278 if (!EXPR_P (expr) && !GIMPLE_STMT_P (expr))
1281 len = TREE_OPERAND_LENGTH (expr);
1282 for (i = 0; i < len; i++)
1283 if (!expr_invariant_in_loop_p (loop, TREE_OPERAND (expr, i)))
1289 /* Cumulates the steps of indices into DATA and replaces their values with the
1290 initial ones. Returns false when the value of the index cannot be determined.
1291 Callback for for_each_index. */
1293 struct ifs_ivopts_data
1295 struct ivopts_data *ivopts_data;
1301 idx_find_step (tree base, tree *idx, void *data)
1303 struct ifs_ivopts_data *dta = (struct ifs_ivopts_data *) data;
1305 tree step, iv_base, iv_step, lbound, off;
1306 struct loop *loop = dta->ivopts_data->current_loop;
1308 if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF
1309 || TREE_CODE (base) == ALIGN_INDIRECT_REF)
1312 /* If base is a component ref, require that the offset of the reference
1314 if (TREE_CODE (base) == COMPONENT_REF)
1316 off = component_ref_field_offset (base);
1317 return expr_invariant_in_loop_p (loop, off);
1320 /* If base is array, first check whether we will be able to move the
1321 reference out of the loop (in order to take its address in strength
1322 reduction). In order for this to work we need both lower bound
1323 and step to be loop invariants. */
1324 if (TREE_CODE (base) == ARRAY_REF)
1326 step = array_ref_element_size (base);
1327 lbound = array_ref_low_bound (base);
1329 if (!expr_invariant_in_loop_p (loop, step)
1330 || !expr_invariant_in_loop_p (loop, lbound))
1334 if (TREE_CODE (*idx) != SSA_NAME)
1337 iv = get_iv (dta->ivopts_data, *idx);
1341 /* XXX We produce for a base of *D42 with iv->base being &x[0]
1342 *&x[0], which is not folded and does not trigger the
1343 ARRAY_REF path below. */
1346 if (integer_zerop (iv->step))
1349 if (TREE_CODE (base) == ARRAY_REF)
1351 step = array_ref_element_size (base);
1353 /* We only handle addresses whose step is an integer constant. */
1354 if (TREE_CODE (step) != INTEGER_CST)
1358 /* The step for pointer arithmetics already is 1 byte. */
1359 step = build_int_cst (sizetype, 1);
1363 if (!convert_affine_scev (dta->ivopts_data->current_loop,
1364 sizetype, &iv_base, &iv_step, dta->stmt,
1367 /* The index might wrap. */
1371 step = fold_build2 (MULT_EXPR, sizetype, step, iv_step);
1372 dta->step = fold_build2 (PLUS_EXPR, sizetype, dta->step, step);
1377 /* Records use in index IDX. Callback for for_each_index. Ivopts data
1378 object is passed to it in DATA. */
1381 idx_record_use (tree base, tree *idx,
1384 struct ivopts_data *data = (struct ivopts_data *) vdata;
1385 find_interesting_uses_op (data, *idx);
1386 if (TREE_CODE (base) == ARRAY_REF)
1388 find_interesting_uses_op (data, array_ref_element_size (base));
1389 find_interesting_uses_op (data, array_ref_low_bound (base));
1394 /* Returns true if memory reference REF may be unaligned. */
1397 may_be_unaligned_p (tree ref)
1401 HOST_WIDE_INT bitsize;
1402 HOST_WIDE_INT bitpos;
1404 enum machine_mode mode;
1405 int unsignedp, volatilep;
1406 unsigned base_align;
1408 /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
1409 thus they are not misaligned. */
1410 if (TREE_CODE (ref) == TARGET_MEM_REF)
1413 /* The test below is basically copy of what expr.c:normal_inner_ref
1414 does to check whether the object must be loaded by parts when
1415 STRICT_ALIGNMENT is true. */
1416 base = get_inner_reference (ref, &bitsize, &bitpos, &toffset, &mode,
1417 &unsignedp, &volatilep, true);
1418 base_type = TREE_TYPE (base);
1419 base_align = TYPE_ALIGN (base_type);
1422 && (base_align < GET_MODE_ALIGNMENT (mode)
1423 || bitpos % GET_MODE_ALIGNMENT (mode) != 0
1424 || bitpos % BITS_PER_UNIT != 0))
1430 /* Return true if EXPR may be non-addressable. */
1433 may_be_nonaddressable_p (tree expr)
1435 switch (TREE_CODE (expr))
1437 case TARGET_MEM_REF:
1438 /* TARGET_MEM_REFs are translated directly to valid MEMs on the
1439 target, thus they are always addressable. */
1443 return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr, 1))
1444 || may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
1446 case VIEW_CONVERT_EXPR:
1447 /* This kind of view-conversions may wrap non-addressable objects
1448 and make them look addressable. After some processing the
1449 non-addressability may be uncovered again, causing ADDR_EXPRs
1450 of inappropriate objects to be built. */
1451 if (AGGREGATE_TYPE_P (TREE_TYPE (expr))
1452 && !AGGREGATE_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))))
1455 /* ... fall through ... */
1458 case ARRAY_RANGE_REF:
1459 return may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
1462 case NON_LVALUE_EXPR:
1473 /* Finds addresses in *OP_P inside STMT. */
1476 find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
1478 tree base = *op_p, step = build_int_cst (sizetype, 0);
1480 struct ifs_ivopts_data ifs_ivopts_data;
1482 /* Do not play with volatile memory references. A bit too conservative,
1483 perhaps, but safe. */
1484 if (stmt_ann (stmt)->has_volatile_ops)
1487 /* Ignore bitfields for now. Not really something terribly complicated
1489 if (TREE_CODE (base) == BIT_FIELD_REF)
1492 base = unshare_expr (base);
1494 if (TREE_CODE (base) == TARGET_MEM_REF)
1496 tree type = build_pointer_type (TREE_TYPE (base));
1500 && TREE_CODE (TMR_BASE (base)) == SSA_NAME)
1502 civ = get_iv (data, TMR_BASE (base));
1506 TMR_BASE (base) = civ->base;
1509 if (TMR_INDEX (base)
1510 && TREE_CODE (TMR_INDEX (base)) == SSA_NAME)
1512 civ = get_iv (data, TMR_INDEX (base));
1516 TMR_INDEX (base) = civ->base;
1521 if (TMR_STEP (base))
1522 astep = fold_build2 (MULT_EXPR, type, TMR_STEP (base), astep);
1524 step = fold_build2 (PLUS_EXPR, type, step, astep);
1528 if (integer_zerop (step))
1530 base = tree_mem_ref_addr (type, base);
1534 ifs_ivopts_data.ivopts_data = data;
1535 ifs_ivopts_data.stmt = stmt;
1536 ifs_ivopts_data.step = build_int_cst (sizetype, 0);
1537 if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
1538 || integer_zerop (ifs_ivopts_data.step))
1540 step = ifs_ivopts_data.step;
1542 gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
1543 gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
1545 /* Check that the base expression is addressable. This needs
1546 to be done after substituting bases of IVs into it. */
1547 if (may_be_nonaddressable_p (base))
1550 /* Moreover, on strict alignment platforms, check that it is
1551 sufficiently aligned. */
1552 if (STRICT_ALIGNMENT && may_be_unaligned_p (base))
1555 base = build_fold_addr_expr (base);
1557 /* Substituting bases of IVs into the base expression might
1558 have caused folding opportunities. */
1559 if (TREE_CODE (base) == ADDR_EXPR)
1561 tree *ref = &TREE_OPERAND (base, 0);
1562 while (handled_component_p (*ref))
1563 ref = &TREE_OPERAND (*ref, 0);
1564 if (TREE_CODE (*ref) == INDIRECT_REF)
1565 *ref = fold_indirect_ref (*ref);
1569 civ = alloc_iv (base, step);
1570 record_use (data, op_p, civ, stmt, USE_ADDRESS);
1574 for_each_index (op_p, idx_record_use, data);
1577 /* Finds and records invariants used in STMT. */
1580 find_invariants_stmt (struct ivopts_data *data, tree stmt)
1583 use_operand_p use_p;
1586 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1588 op = USE_FROM_PTR (use_p);
1589 record_invariant (data, op, false);
1593 /* Finds interesting uses of induction variables in the statement STMT. */
1596 find_interesting_uses_stmt (struct ivopts_data *data, tree stmt)
1601 use_operand_p use_p;
1603 find_invariants_stmt (data, stmt);
1605 if (TREE_CODE (stmt) == COND_EXPR)
1607 find_interesting_uses_cond (data, stmt, &COND_EXPR_COND (stmt));
1611 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1613 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1614 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1616 if (TREE_CODE (lhs) == SSA_NAME)
1618 /* If the statement defines an induction variable, the uses are not
1619 interesting by themselves. */
1621 iv = get_iv (data, lhs);
1623 if (iv && !integer_zerop (iv->step))
1627 switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
1629 case tcc_comparison:
1630 find_interesting_uses_cond (data, stmt,
1631 &GIMPLE_STMT_OPERAND (stmt, 1));
1635 find_interesting_uses_address (data, stmt,
1636 &GIMPLE_STMT_OPERAND (stmt, 1));
1637 if (REFERENCE_CLASS_P (lhs))
1638 find_interesting_uses_address (data, stmt,
1639 &GIMPLE_STMT_OPERAND (stmt, 0));
1645 if (REFERENCE_CLASS_P (lhs)
1646 && is_gimple_val (rhs))
1648 find_interesting_uses_address (data, stmt,
1649 &GIMPLE_STMT_OPERAND (stmt, 0));
1650 find_interesting_uses_op (data, rhs);
1654 /* TODO -- we should also handle address uses of type
1656 memory = call (whatever);
1663 if (TREE_CODE (stmt) == PHI_NODE
1664 && bb_for_stmt (stmt) == data->current_loop->header)
1666 lhs = PHI_RESULT (stmt);
1667 iv = get_iv (data, lhs);
1669 if (iv && !integer_zerop (iv->step))
1673 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1675 op = USE_FROM_PTR (use_p);
1677 if (TREE_CODE (op) != SSA_NAME)
1680 iv = get_iv (data, op);
1684 find_interesting_uses_op (data, op);
1688 /* Finds interesting uses of induction variables outside of loops
1689 on loop exit edge EXIT. */
1692 find_interesting_uses_outside (struct ivopts_data *data, edge exit)
1696 for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
1698 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1699 if (is_gimple_reg (def))
1700 find_interesting_uses_op (data, def);
1704 /* Finds uses of the induction variables that are interesting. */
1707 find_interesting_uses (struct ivopts_data *data)
1710 block_stmt_iterator bsi;
1712 basic_block *body = get_loop_body (data->current_loop);
1714 struct version_info *info;
1717 if (dump_file && (dump_flags & TDF_DETAILS))
1718 fprintf (dump_file, "Uses:\n\n");
1720 for (i = 0; i < data->current_loop->num_nodes; i++)
1725 FOR_EACH_EDGE (e, ei, bb->succs)
1726 if (e->dest != EXIT_BLOCK_PTR
1727 && !flow_bb_inside_loop_p (data->current_loop, e->dest))
1728 find_interesting_uses_outside (data, e);
1730 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1731 find_interesting_uses_stmt (data, phi);
1732 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1733 find_interesting_uses_stmt (data, bsi_stmt (bsi));
1736 if (dump_file && (dump_flags & TDF_DETAILS))
1740 fprintf (dump_file, "\n");
1742 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
1744 info = ver_info (data, i);
1747 fprintf (dump_file, " ");
1748 print_generic_expr (dump_file, info->name, TDF_SLIM);
1749 fprintf (dump_file, " is invariant (%d)%s\n",
1750 info->inv_id, info->has_nonlin_use ? "" : ", eliminable");
1754 fprintf (dump_file, "\n");
1760 /* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
1761 is true, assume we are inside an address. If TOP_COMPREF is true, assume
1762 we are at the top-level of the processed address. */
1765 strip_offset_1 (tree expr, bool inside_addr, bool top_compref,
1766 unsigned HOST_WIDE_INT *offset)
1768 tree op0 = NULL_TREE, op1 = NULL_TREE, tmp, step;
1769 enum tree_code code;
1770 tree type, orig_type = TREE_TYPE (expr);
1771 unsigned HOST_WIDE_INT off0, off1, st;
1772 tree orig_expr = expr;
1776 type = TREE_TYPE (expr);
1777 code = TREE_CODE (expr);
1783 if (!cst_and_fits_in_hwi (expr)
1784 || integer_zerop (expr))
1787 *offset = int_cst_value (expr);
1788 return build_int_cst (orig_type, 0);
1790 case POINTER_PLUS_EXPR:
1793 op0 = TREE_OPERAND (expr, 0);
1794 op1 = TREE_OPERAND (expr, 1);
1796 op0 = strip_offset_1 (op0, false, false, &off0);
1797 op1 = strip_offset_1 (op1, false, false, &off1);
1799 *offset = (code == MINUS_EXPR ? off0 - off1 : off0 + off1);
1800 if (op0 == TREE_OPERAND (expr, 0)
1801 && op1 == TREE_OPERAND (expr, 1))
1804 if (integer_zerop (op1))
1806 else if (integer_zerop (op0))
1808 if (code == MINUS_EXPR)
1809 expr = fold_build1 (NEGATE_EXPR, type, op1);
1814 expr = fold_build2 (code, type, op0, op1);
1816 return fold_convert (orig_type, expr);
1822 step = array_ref_element_size (expr);
1823 if (!cst_and_fits_in_hwi (step))
1826 st = int_cst_value (step);
1827 op1 = TREE_OPERAND (expr, 1);
1828 op1 = strip_offset_1 (op1, false, false, &off1);
1829 *offset = off1 * st;
1832 && integer_zerop (op1))
1834 /* Strip the component reference completely. */
1835 op0 = TREE_OPERAND (expr, 0);
1836 op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
1846 tmp = component_ref_field_offset (expr);
1848 && cst_and_fits_in_hwi (tmp))
1850 /* Strip the component reference completely. */
1851 op0 = TREE_OPERAND (expr, 0);
1852 op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
1853 *offset = off0 + int_cst_value (tmp);
1859 op0 = TREE_OPERAND (expr, 0);
1860 op0 = strip_offset_1 (op0, true, true, &off0);
1863 if (op0 == TREE_OPERAND (expr, 0))
1866 expr = build_fold_addr_expr (op0);
1867 return fold_convert (orig_type, expr);
1870 inside_addr = false;
1877 /* Default handling of expressions for that we want to recurse into
1878 the first operand. */
1879 op0 = TREE_OPERAND (expr, 0);
1880 op0 = strip_offset_1 (op0, inside_addr, false, &off0);
1883 if (op0 == TREE_OPERAND (expr, 0)
1884 && (!op1 || op1 == TREE_OPERAND (expr, 1)))
1887 expr = copy_node (expr);
1888 TREE_OPERAND (expr, 0) = op0;
1890 TREE_OPERAND (expr, 1) = op1;
1892 /* Inside address, we might strip the top level component references,
1893 thus changing type of the expression. Handling of ADDR_EXPR
1895 expr = fold_convert (orig_type, expr);
1900 /* Strips constant offsets from EXPR and stores them to OFFSET. */
1903 strip_offset (tree expr, unsigned HOST_WIDE_INT *offset)
1905 return strip_offset_1 (expr, false, false, offset);
1908 /* Returns variant of TYPE that can be used as base for different uses.
1909 We return unsigned type with the same precision, which avoids problems
1913 generic_type_for (tree type)
1915 if (POINTER_TYPE_P (type))
1916 return unsigned_type_for (type);
1918 if (TYPE_UNSIGNED (type))
1921 return unsigned_type_for (type);
1924 /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
1925 the bitmap to that we should store it. */
1927 static struct ivopts_data *fd_ivopts_data;
1929 find_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
1931 bitmap *depends_on = (bitmap *) data;
1932 struct version_info *info;
1934 if (TREE_CODE (*expr_p) != SSA_NAME)
1936 info = name_info (fd_ivopts_data, *expr_p);
1938 if (!info->inv_id || info->has_nonlin_use)
1942 *depends_on = BITMAP_ALLOC (NULL);
1943 bitmap_set_bit (*depends_on, info->inv_id);
1948 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
1949 position to POS. If USE is not NULL, the candidate is set as related to
1950 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
1951 replacement of the final value of the iv by a direct computation. */
1953 static struct iv_cand *
1954 add_candidate_1 (struct ivopts_data *data,
1955 tree base, tree step, bool important, enum iv_position pos,
1956 struct iv_use *use, tree incremented_at)
1959 struct iv_cand *cand = NULL;
1960 tree type, orig_type;
1964 orig_type = TREE_TYPE (base);
1965 type = generic_type_for (orig_type);
1966 if (type != orig_type)
1968 base = fold_convert (type, base);
1969 step = fold_convert (type, step);
1973 for (i = 0; i < n_iv_cands (data); i++)
1975 cand = iv_cand (data, i);
1977 if (cand->pos != pos)
1980 if (cand->incremented_at != incremented_at)
1994 if (operand_equal_p (base, cand->iv->base, 0)
1995 && operand_equal_p (step, cand->iv->step, 0))
1999 if (i == n_iv_cands (data))
2001 cand = XCNEW (struct iv_cand);
2007 cand->iv = alloc_iv (base, step);
2010 if (pos != IP_ORIGINAL && cand->iv)
2012 cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp");
2013 cand->var_after = cand->var_before;
2015 cand->important = important;
2016 cand->incremented_at = incremented_at;
2017 VEC_safe_push (iv_cand_p, heap, data->iv_candidates, cand);
2020 && TREE_CODE (step) != INTEGER_CST)
2022 fd_ivopts_data = data;
2023 walk_tree (&step, find_depends, &cand->depends_on, NULL);
2026 if (dump_file && (dump_flags & TDF_DETAILS))
2027 dump_cand (dump_file, cand);
2030 if (important && !cand->important)
2032 cand->important = true;
2033 if (dump_file && (dump_flags & TDF_DETAILS))
2034 fprintf (dump_file, "Candidate %d is important\n", cand->id);
2039 bitmap_set_bit (use->related_cands, i);
2040 if (dump_file && (dump_flags & TDF_DETAILS))
2041 fprintf (dump_file, "Candidate %d is related to use %d\n",
2048 /* Returns true if incrementing the induction variable at the end of the LOOP
2051 The purpose is to avoid splitting latch edge with a biv increment, thus
2052 creating a jump, possibly confusing other optimization passes and leaving
2053 less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS
2054 is not available (so we do not have a better alternative), or if the latch
2055 edge is already nonempty. */
2058 allow_ip_end_pos_p (struct loop *loop)
2060 if (!ip_normal_pos (loop))
2063 if (!empty_block_p (ip_end_pos (loop)))
2069 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2070 position to POS. If USE is not NULL, the candidate is set as related to
2071 it. The candidate computation is scheduled on all available positions. */
2074 add_candidate (struct ivopts_data *data,
2075 tree base, tree step, bool important, struct iv_use *use)
2077 if (ip_normal_pos (data->current_loop))
2078 add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL_TREE);
2079 if (ip_end_pos (data->current_loop)
2080 && allow_ip_end_pos_p (data->current_loop))
2081 add_candidate_1 (data, base, step, important, IP_END, use, NULL_TREE);
2084 /* Add a standard "0 + 1 * iteration" iv candidate for a
2085 type with SIZE bits. */
2088 add_standard_iv_candidates_for_size (struct ivopts_data *data,
2091 tree type = lang_hooks.types.type_for_size (size, true);
2092 add_candidate (data, build_int_cst (type, 0), build_int_cst (type, 1),
2096 /* Adds standard iv candidates. */
2099 add_standard_iv_candidates (struct ivopts_data *data)
2101 add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE);
2103 /* The same for a double-integer type if it is still fast enough. */
2104 if (BITS_PER_WORD >= INT_TYPE_SIZE * 2)
2105 add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE * 2);
2109 /* Adds candidates bases on the old induction variable IV. */
2112 add_old_iv_candidates (struct ivopts_data *data, struct iv *iv)
2115 struct iv_cand *cand;
2117 add_candidate (data, iv->base, iv->step, true, NULL);
2119 /* The same, but with initial value zero. */
2120 add_candidate (data,
2121 build_int_cst (TREE_TYPE (iv->base), 0),
2122 iv->step, true, NULL);
2124 phi = SSA_NAME_DEF_STMT (iv->ssa_name);
2125 if (TREE_CODE (phi) == PHI_NODE)
2127 /* Additionally record the possibility of leaving the original iv
2129 def = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (data->current_loop));
2130 cand = add_candidate_1 (data,
2131 iv->base, iv->step, true, IP_ORIGINAL, NULL,
2132 SSA_NAME_DEF_STMT (def));
2133 cand->var_before = iv->ssa_name;
2134 cand->var_after = def;
2138 /* Adds candidates based on the old induction variables. */
2141 add_old_ivs_candidates (struct ivopts_data *data)
2147 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
2149 iv = ver_info (data, i)->iv;
2150 if (iv && iv->biv_p && !integer_zerop (iv->step))
2151 add_old_iv_candidates (data, iv);
2155 /* Adds candidates based on the value of the induction variable IV and USE. */
2158 add_iv_value_candidates (struct ivopts_data *data,
2159 struct iv *iv, struct iv_use *use)
2161 unsigned HOST_WIDE_INT offset;
2164 add_candidate (data, iv->base, iv->step, false, use);
2166 /* The same, but with initial value zero. Make such variable important,
2167 since it is generic enough so that possibly many uses may be based
2169 add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
2170 iv->step, true, use);
2172 /* Third, try removing the constant offset. */
2173 base = strip_offset (iv->base, &offset);
2175 add_candidate (data, base, iv->step, false, use);
2178 /* Adds candidates based on the uses. */
2181 add_derived_ivs_candidates (struct ivopts_data *data)
2185 for (i = 0; i < n_iv_uses (data); i++)
2187 struct iv_use *use = iv_use (data, i);
2194 case USE_NONLINEAR_EXPR:
2197 /* Just add the ivs based on the value of the iv used here. */
2198 add_iv_value_candidates (data, use->iv, use);
2207 /* Record important candidates and add them to related_cands bitmaps
2211 record_important_candidates (struct ivopts_data *data)
2216 for (i = 0; i < n_iv_cands (data); i++)
2218 struct iv_cand *cand = iv_cand (data, i);
2220 if (cand->important)
2221 bitmap_set_bit (data->important_candidates, i);
2224 data->consider_all_candidates = (n_iv_cands (data)
2225 <= CONSIDER_ALL_CANDIDATES_BOUND);
2227 if (data->consider_all_candidates)
2229 /* We will not need "related_cands" bitmaps in this case,
2230 so release them to decrease peak memory consumption. */
2231 for (i = 0; i < n_iv_uses (data); i++)
2233 use = iv_use (data, i);
2234 BITMAP_FREE (use->related_cands);
2239 /* Add important candidates to the related_cands bitmaps. */
2240 for (i = 0; i < n_iv_uses (data); i++)
2241 bitmap_ior_into (iv_use (data, i)->related_cands,
2242 data->important_candidates);
2246 /* Finds the candidates for the induction variables. */
2249 find_iv_candidates (struct ivopts_data *data)
2251 /* Add commonly used ivs. */
2252 add_standard_iv_candidates (data);
2254 /* Add old induction variables. */
2255 add_old_ivs_candidates (data);
2257 /* Add induction variables derived from uses. */
2258 add_derived_ivs_candidates (data);
2260 /* Record the important candidates. */
2261 record_important_candidates (data);
2264 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
2265 If consider_all_candidates is true, we use a two-dimensional array, otherwise
2266 we allocate a simple list to every use. */
2269 alloc_use_cost_map (struct ivopts_data *data)
2271 unsigned i, size, s, j;
2273 for (i = 0; i < n_iv_uses (data); i++)
2275 struct iv_use *use = iv_use (data, i);
2278 if (data->consider_all_candidates)
2279 size = n_iv_cands (data);
2283 EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi)
2288 /* Round up to the power of two, so that moduling by it is fast. */
2289 for (size = 1; size < s; size <<= 1)
2293 use->n_map_members = size;
2294 use->cost_map = XCNEWVEC (struct cost_pair, size);
2298 /* Returns description of computation cost of expression whose runtime
2299 cost is RUNTIME and complexity corresponds to COMPLEXITY. */
2302 new_cost (unsigned runtime, unsigned complexity)
2306 cost.cost = runtime;
2307 cost.complexity = complexity;
2312 /* Adds costs COST1 and COST2. */
2315 add_costs (comp_cost cost1, comp_cost cost2)
2317 cost1.cost += cost2.cost;
2318 cost1.complexity += cost2.complexity;
2322 /* Subtracts costs COST1 and COST2. */
2325 sub_costs (comp_cost cost1, comp_cost cost2)
2327 cost1.cost -= cost2.cost;
2328 cost1.complexity -= cost2.complexity;
2333 /* Returns a negative number if COST1 < COST2, a positive number if
2334 COST1 > COST2, and 0 if COST1 = COST2. */
2337 compare_costs (comp_cost cost1, comp_cost cost2)
2339 if (cost1.cost == cost2.cost)
2340 return cost1.complexity - cost2.complexity;
2342 return cost1.cost - cost2.cost;
2345 /* Returns true if COST is infinite. */
2348 infinite_cost_p (comp_cost cost)
2350 return cost.cost == INFTY;
2353 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
2354 on invariants DEPENDS_ON and that the value used in expressing it
2358 set_use_iv_cost (struct ivopts_data *data,
2359 struct iv_use *use, struct iv_cand *cand,
2360 comp_cost cost, bitmap depends_on, tree value)
2364 if (infinite_cost_p (cost))
2366 BITMAP_FREE (depends_on);
2370 if (data->consider_all_candidates)
2372 use->cost_map[cand->id].cand = cand;
2373 use->cost_map[cand->id].cost = cost;
2374 use->cost_map[cand->id].depends_on = depends_on;
2375 use->cost_map[cand->id].value = value;
2379 /* n_map_members is a power of two, so this computes modulo. */
2380 s = cand->id & (use->n_map_members - 1);
2381 for (i = s; i < use->n_map_members; i++)
2382 if (!use->cost_map[i].cand)
2384 for (i = 0; i < s; i++)
2385 if (!use->cost_map[i].cand)
2391 use->cost_map[i].cand = cand;
2392 use->cost_map[i].cost = cost;
2393 use->cost_map[i].depends_on = depends_on;
2394 use->cost_map[i].value = value;
2397 /* Gets cost of (USE, CANDIDATE) pair. */
2399 static struct cost_pair *
2400 get_use_iv_cost (struct ivopts_data *data, struct iv_use *use,
2401 struct iv_cand *cand)
2404 struct cost_pair *ret;
2409 if (data->consider_all_candidates)
2411 ret = use->cost_map + cand->id;
2418 /* n_map_members is a power of two, so this computes modulo. */
2419 s = cand->id & (use->n_map_members - 1);
2420 for (i = s; i < use->n_map_members; i++)
2421 if (use->cost_map[i].cand == cand)
2422 return use->cost_map + i;
2424 for (i = 0; i < s; i++)
2425 if (use->cost_map[i].cand == cand)
2426 return use->cost_map + i;
2431 /* Returns estimate on cost of computing SEQ. */
2439 for (; seq; seq = NEXT_INSN (seq))
2441 set = single_set (seq);
2443 cost += rtx_cost (set, SET);
2451 /* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
2453 produce_memory_decl_rtl (tree obj, int *regno)
2458 if (TREE_STATIC (obj) || DECL_EXTERNAL (obj))
2460 const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj));
2461 x = gen_rtx_SYMBOL_REF (Pmode, name);
2462 SET_SYMBOL_REF_DECL (x, obj);
2463 x = gen_rtx_MEM (DECL_MODE (obj), x);
2464 targetm.encode_section_info (obj, x, true);
2468 x = gen_raw_REG (Pmode, (*regno)++);
2469 x = gen_rtx_MEM (DECL_MODE (obj), x);
2475 /* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
2476 walk_tree. DATA contains the actual fake register number. */
2479 prepare_decl_rtl (tree *expr_p, int *ws, void *data)
2481 tree obj = NULL_TREE;
2483 int *regno = (int *) data;
2485 switch (TREE_CODE (*expr_p))
2488 for (expr_p = &TREE_OPERAND (*expr_p, 0);
2489 handled_component_p (*expr_p);
2490 expr_p = &TREE_OPERAND (*expr_p, 0))
2493 if (DECL_P (obj) && !DECL_RTL_SET_P (obj))
2494 x = produce_memory_decl_rtl (obj, regno);
2499 obj = SSA_NAME_VAR (*expr_p);
2500 if (!DECL_RTL_SET_P (obj))
2501 x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
2510 if (DECL_RTL_SET_P (obj))
2513 if (DECL_MODE (obj) == BLKmode)
2514 x = produce_memory_decl_rtl (obj, regno);
2516 x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
2526 VEC_safe_push (tree, heap, decl_rtl_to_reset, obj);
2527 SET_DECL_RTL (obj, x);
2533 /* Determines cost of the computation of EXPR. */
2536 computation_cost (tree expr)
2539 tree type = TREE_TYPE (expr);
2541 /* Avoid using hard regs in ways which may be unsupported. */
2542 int regno = LAST_VIRTUAL_REGISTER + 1;
2544 walk_tree (&expr, prepare_decl_rtl, ®no, NULL);
2546 rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL);
2550 cost = seq_cost (seq);
2552 cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type));
2557 /* Returns variable containing the value of candidate CAND at statement AT. */
2560 var_at_stmt (struct loop *loop, struct iv_cand *cand, tree stmt)
2562 if (stmt_after_increment (loop, cand, stmt))
2563 return cand->var_after;
2565 return cand->var_before;
2568 /* Return the most significant (sign) bit of T. Similar to tree_int_cst_msb,
2569 but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE. */
2572 tree_int_cst_sign_bit (const_tree t)
2574 unsigned bitno = TYPE_PRECISION (TREE_TYPE (t)) - 1;
2575 unsigned HOST_WIDE_INT w;
2577 if (bitno < HOST_BITS_PER_WIDE_INT)
2578 w = TREE_INT_CST_LOW (t);
2581 w = TREE_INT_CST_HIGH (t);
2582 bitno -= HOST_BITS_PER_WIDE_INT;
2585 return (w >> bitno) & 1;
2588 /* If we can prove that TOP = cst * BOT for some constant cst,
2589 store cst to MUL and return true. Otherwise return false.
2590 The returned value is always sign-extended, regardless of the
2591 signedness of TOP and BOT. */
2594 constant_multiple_of (tree top, tree bot, double_int *mul)
2597 enum tree_code code;
2598 double_int res, p0, p1;
2599 unsigned precision = TYPE_PRECISION (TREE_TYPE (top));
2604 if (operand_equal_p (top, bot, 0))
2606 *mul = double_int_one;
2610 code = TREE_CODE (top);
2614 mby = TREE_OPERAND (top, 1);
2615 if (TREE_CODE (mby) != INTEGER_CST)
2618 if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &res))
2621 *mul = double_int_sext (double_int_mul (res, tree_to_double_int (mby)),
2627 if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &p0)
2628 || !constant_multiple_of (TREE_OPERAND (top, 1), bot, &p1))
2631 if (code == MINUS_EXPR)
2632 p1 = double_int_neg (p1);
2633 *mul = double_int_sext (double_int_add (p0, p1), precision);
2637 if (TREE_CODE (bot) != INTEGER_CST)
2640 p0 = double_int_sext (tree_to_double_int (top), precision);
2641 p1 = double_int_sext (tree_to_double_int (bot), precision);
2642 if (double_int_zero_p (p1))
2644 *mul = double_int_sext (double_int_sdivmod (p0, p1, FLOOR_DIV_EXPR, &res),
2646 return double_int_zero_p (res);
2653 /* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
2654 same precision that is at least as wide as the precision of TYPE, stores
2655 BA to A and BB to B, and returns the type of BA. Otherwise, returns the
2659 determine_common_wider_type (tree *a, tree *b)
2661 tree wider_type = NULL;
2663 tree atype = TREE_TYPE (*a);
2665 if ((TREE_CODE (*a) == NOP_EXPR
2666 || TREE_CODE (*a) == CONVERT_EXPR))
2668 suba = TREE_OPERAND (*a, 0);
2669 wider_type = TREE_TYPE (suba);
2670 if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (atype))
2676 if ((TREE_CODE (*b) == NOP_EXPR
2677 || TREE_CODE (*b) == CONVERT_EXPR))
2679 subb = TREE_OPERAND (*b, 0);
2680 if (TYPE_PRECISION (wider_type) != TYPE_PRECISION (TREE_TYPE (subb)))
2691 /* Determines the expression by that USE is expressed from induction variable
2692 CAND at statement AT in LOOP. The expression is stored in a decomposed
2693 form into AFF. Returns false if USE cannot be expressed using CAND. */
2696 get_computation_aff (struct loop *loop,
2697 struct iv_use *use, struct iv_cand *cand, tree at,
2698 struct affine_tree_combination *aff)
2700 tree ubase = use->iv->base;
2701 tree ustep = use->iv->step;
2702 tree cbase = cand->iv->base;
2703 tree cstep = cand->iv->step, cstep_common;
2704 tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
2705 tree common_type, var;
2707 aff_tree cbase_aff, var_aff;
2710 if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
2712 /* We do not have a precision to express the values of use. */
2716 var = var_at_stmt (loop, cand, at);
2717 uutype = unsigned_type_for (utype);
2719 /* If the conversion is not noop, perform it. */
2720 if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
2722 cstep = fold_convert (uutype, cstep);
2723 cbase = fold_convert (uutype, cbase);
2724 var = fold_convert (uutype, var);
2727 if (!constant_multiple_of (ustep, cstep, &rat))
2730 /* In case both UBASE and CBASE are shortened to UUTYPE from some common
2731 type, we achieve better folding by computing their difference in this
2732 wider type, and cast the result to UUTYPE. We do not need to worry about
2733 overflows, as all the arithmetics will in the end be performed in UUTYPE
2735 common_type = determine_common_wider_type (&ubase, &cbase);
2737 /* use = ubase - ratio * cbase + ratio * var. */
2738 tree_to_aff_combination (ubase, common_type, aff);
2739 tree_to_aff_combination (cbase, common_type, &cbase_aff);
2740 tree_to_aff_combination (var, uutype, &var_aff);
2742 /* We need to shift the value if we are after the increment. */
2743 if (stmt_after_increment (loop, cand, at))
2747 if (common_type != uutype)
2748 cstep_common = fold_convert (common_type, cstep);
2750 cstep_common = cstep;
2752 tree_to_aff_combination (cstep_common, common_type, &cstep_aff);
2753 aff_combination_add (&cbase_aff, &cstep_aff);
2756 aff_combination_scale (&cbase_aff, double_int_neg (rat));
2757 aff_combination_add (aff, &cbase_aff);
2758 if (common_type != uutype)
2759 aff_combination_convert (aff, uutype);
2761 aff_combination_scale (&var_aff, rat);
2762 aff_combination_add (aff, &var_aff);
2767 /* Determines the expression by that USE is expressed from induction variable
2768 CAND at statement AT in LOOP. The computation is unshared. */
2771 get_computation_at (struct loop *loop,
2772 struct iv_use *use, struct iv_cand *cand, tree at)
2775 tree type = TREE_TYPE (use->iv->base);
2777 if (!get_computation_aff (loop, use, cand, at, &aff))
2779 unshare_aff_combination (&aff);
2780 return fold_convert (type, aff_combination_to_tree (&aff));
2783 /* Determines the expression by that USE is expressed from induction variable
2784 CAND in LOOP. The computation is unshared. */
2787 get_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand)
2789 return get_computation_at (loop, use, cand, use->stmt);
2792 /* Returns cost of addition in MODE. */
2795 add_cost (enum machine_mode mode)
2797 static unsigned costs[NUM_MACHINE_MODES];
2805 force_operand (gen_rtx_fmt_ee (PLUS, mode,
2806 gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
2807 gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 2)),
2812 cost = seq_cost (seq);
2818 if (dump_file && (dump_flags & TDF_DETAILS))
2819 fprintf (dump_file, "Addition in %s costs %d\n",
2820 GET_MODE_NAME (mode), cost);
2824 /* Entry in a hashtable of already known costs for multiplication. */
2827 HOST_WIDE_INT cst; /* The constant to multiply by. */
2828 enum machine_mode mode; /* In mode. */
2829 unsigned cost; /* The cost. */
2832 /* Counts hash value for the ENTRY. */
2835 mbc_entry_hash (const void *entry)
2837 const struct mbc_entry *e = (const struct mbc_entry *) entry;
2839 return 57 * (hashval_t) e->mode + (hashval_t) (e->cst % 877);
2842 /* Compares the hash table entries ENTRY1 and ENTRY2. */
2845 mbc_entry_eq (const void *entry1, const void *entry2)
2847 const struct mbc_entry *e1 = (const struct mbc_entry *) entry1;
2848 const struct mbc_entry *e2 = (const struct mbc_entry *) entry2;
2850 return (e1->mode == e2->mode
2851 && e1->cst == e2->cst);
2854 /* Returns cost of multiplication by constant CST in MODE. */
2857 multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode)
2859 static htab_t costs;
2860 struct mbc_entry **cached, act;
2865 costs = htab_create (100, mbc_entry_hash, mbc_entry_eq, free);
2869 cached = (struct mbc_entry **) htab_find_slot (costs, &act, INSERT);
2871 return (*cached)->cost;
2873 *cached = XNEW (struct mbc_entry);
2874 (*cached)->mode = mode;
2875 (*cached)->cst = cst;
2878 expand_mult (mode, gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
2879 gen_int_mode (cst, mode), NULL_RTX, 0);
2883 cost = seq_cost (seq);
2885 if (dump_file && (dump_flags & TDF_DETAILS))
2886 fprintf (dump_file, "Multiplication by %d in %s costs %d\n",
2887 (int) cst, GET_MODE_NAME (mode), cost);
2889 (*cached)->cost = cost;
2894 /* Returns true if multiplying by RATIO is allowed in an address. Test the
2895 validity for a memory reference accessing memory of mode MODE. */
2898 multiplier_allowed_in_address_p (HOST_WIDE_INT ratio, enum machine_mode mode)
2900 #define MAX_RATIO 128
2901 static sbitmap valid_mult[MAX_MACHINE_MODE];
2903 if (!valid_mult[mode])
2905 rtx reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
2909 valid_mult[mode] = sbitmap_alloc (2 * MAX_RATIO + 1);
2910 sbitmap_zero (valid_mult[mode]);
2911 addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX);
2912 for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
2914 XEXP (addr, 1) = gen_int_mode (i, Pmode);
2915 if (memory_address_p (mode, addr))
2916 SET_BIT (valid_mult[mode], i + MAX_RATIO);
2919 if (dump_file && (dump_flags & TDF_DETAILS))
2921 fprintf (dump_file, " allowed multipliers:");
2922 for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
2923 if (TEST_BIT (valid_mult[mode], i + MAX_RATIO))
2924 fprintf (dump_file, " %d", (int) i);
2925 fprintf (dump_file, "\n");
2926 fprintf (dump_file, "\n");
2930 if (ratio > MAX_RATIO || ratio < -MAX_RATIO)
2933 return TEST_BIT (valid_mult[mode], ratio + MAX_RATIO);
2936 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
2937 If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
2938 variable is omitted. Compute the cost for a memory reference that accesses
2939 a memory location of mode MEM_MODE.
2941 TODO -- there must be some better way. This all is quite crude. */
2944 get_address_cost (bool symbol_present, bool var_present,
2945 unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio,
2946 enum machine_mode mem_mode)
2948 static bool initialized[MAX_MACHINE_MODE];
2949 static HOST_WIDE_INT rat[MAX_MACHINE_MODE], off[MAX_MACHINE_MODE];
2950 static HOST_WIDE_INT min_offset[MAX_MACHINE_MODE], max_offset[MAX_MACHINE_MODE];
2951 static unsigned costs[MAX_MACHINE_MODE][2][2][2][2];
2952 unsigned cost, acost, complexity;
2953 bool offset_p, ratio_p;
2954 HOST_WIDE_INT s_offset;
2955 unsigned HOST_WIDE_INT mask;
2958 if (!initialized[mem_mode])
2961 HOST_WIDE_INT start = BIGGEST_ALIGNMENT / BITS_PER_UNIT;
2962 int old_cse_not_expected;
2963 unsigned sym_p, var_p, off_p, rat_p, add_c;
2964 rtx seq, addr, base;
2967 initialized[mem_mode] = true;
2969 reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
2971 addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
2972 for (i = start; i <= 1 << 20; i <<= 1)
2974 XEXP (addr, 1) = gen_int_mode (i, Pmode);
2975 if (!memory_address_p (mem_mode, addr))
2978 max_offset[mem_mode] = i == start ? 0 : i >> 1;
2979 off[mem_mode] = max_offset[mem_mode];
2981 for (i = start; i <= 1 << 20; i <<= 1)
2983 XEXP (addr, 1) = gen_int_mode (-i, Pmode);
2984 if (!memory_address_p (mem_mode, addr))
2987 min_offset[mem_mode] = i == start ? 0 : -(i >> 1);
2989 if (dump_file && (dump_flags & TDF_DETAILS))
2991 fprintf (dump_file, "get_address_cost:\n");
2992 fprintf (dump_file, " min offset %s %d\n",
2993 GET_MODE_NAME (mem_mode),
2994 (int) min_offset[mem_mode]);
2995 fprintf (dump_file, " max offset %s %d\n",
2996 GET_MODE_NAME (mem_mode),
2997 (int) max_offset[mem_mode]);
3001 for (i = 2; i <= MAX_RATIO; i++)
3002 if (multiplier_allowed_in_address_p (i, mem_mode))
3008 /* Compute the cost of various addressing modes. */
3010 reg0 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
3011 reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
3013 for (i = 0; i < 16; i++)
3016 var_p = (i >> 1) & 1;
3017 off_p = (i >> 2) & 1;
3018 rat_p = (i >> 3) & 1;
3022 addr = gen_rtx_fmt_ee (MULT, Pmode, addr,
3023 gen_int_mode (rat[mem_mode], Pmode));
3026 addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1);
3030 base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
3031 /* ??? We can run into trouble with some backends by presenting
3032 it with symbols which havn't been properly passed through
3033 targetm.encode_section_info. By setting the local bit, we
3034 enhance the probability of things working. */
3035 SYMBOL_REF_FLAGS (base) = SYMBOL_FLAG_LOCAL;
3038 base = gen_rtx_fmt_e (CONST, Pmode,
3039 gen_rtx_fmt_ee (PLUS, Pmode,
3041 gen_int_mode (off[mem_mode],
3045 base = gen_int_mode (off[mem_mode], Pmode);
3050 addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, base);
3053 /* To avoid splitting addressing modes, pretend that no cse will
3055 old_cse_not_expected = cse_not_expected;
3056 cse_not_expected = true;
3057 addr = memory_address (mem_mode, addr);
3058 cse_not_expected = old_cse_not_expected;
3062 acost = seq_cost (seq);
3063 acost += address_cost (addr, mem_mode);
3067 costs[mem_mode][sym_p][var_p][off_p][rat_p] = acost;
3070 /* On some targets, it is quite expensive to load symbol to a register,
3071 which makes addresses that contain symbols look much more expensive.
3072 However, the symbol will have to be loaded in any case before the
3073 loop (and quite likely we have it in register already), so it does not
3074 make much sense to penalize them too heavily. So make some final
3075 tweaks for the SYMBOL_PRESENT modes:
3077 If VAR_PRESENT is false, and the mode obtained by changing symbol to
3078 var is cheaper, use this mode with small penalty.
3079 If VAR_PRESENT is true, try whether the mode with
3080 SYMBOL_PRESENT = false is cheaper even with cost of addition, and
3081 if this is the case, use it. */
3082 add_c = add_cost (Pmode);
3083 for (i = 0; i < 8; i++)
3086 off_p = (i >> 1) & 1;
3087 rat_p = (i >> 2) & 1;
3089 acost = costs[mem_mode][0][1][off_p][rat_p] + 1;
3093 if (acost < costs[mem_mode][1][var_p][off_p][rat_p])
3094 costs[mem_mode][1][var_p][off_p][rat_p] = acost;
3097 if (dump_file && (dump_flags & TDF_DETAILS))
3099 fprintf (dump_file, "Address costs:\n");
3101 for (i = 0; i < 16; i++)
3104 var_p = (i >> 1) & 1;
3105 off_p = (i >> 2) & 1;
3106 rat_p = (i >> 3) & 1;
3108 fprintf (dump_file, " ");
3110 fprintf (dump_file, "sym + ");
3112 fprintf (dump_file, "var + ");
3114 fprintf (dump_file, "cst + ");
3116 fprintf (dump_file, "rat * ");
3118 acost = costs[mem_mode][sym_p][var_p][off_p][rat_p];
3119 fprintf (dump_file, "index costs %d\n", acost);
3121 fprintf (dump_file, "\n");
3125 bits = GET_MODE_BITSIZE (Pmode);
3126 mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
3128 if ((offset >> (bits - 1) & 1))
3133 offset_p = (s_offset != 0
3134 && min_offset[mem_mode] <= s_offset
3135 && s_offset <= max_offset[mem_mode]);
3136 ratio_p = (ratio != 1
3137 && multiplier_allowed_in_address_p (ratio, mem_mode));
3139 if (ratio != 1 && !ratio_p)
3140 cost += multiply_by_cost (ratio, Pmode);
3142 if (s_offset && !offset_p && !symbol_present)
3143 cost += add_cost (Pmode);
3145 acost = costs[mem_mode][symbol_present][var_present][offset_p][ratio_p];
3146 complexity = (symbol_present != 0) + (var_present != 0) + offset_p + ratio_p;
3147 return new_cost (cost + acost, complexity);
3150 /* Estimates cost of forcing expression EXPR into a variable. */
3153 force_expr_to_var_cost (tree expr)
3155 static bool costs_initialized = false;
3156 static unsigned integer_cost;
3157 static unsigned symbol_cost;
3158 static unsigned address_cost;
3160 comp_cost cost0, cost1, cost;
3161 enum machine_mode mode;
3163 if (!costs_initialized)
3165 tree type = build_pointer_type (integer_type_node);
3169 var = create_tmp_var_raw (integer_type_node, "test_var");
3170 TREE_STATIC (var) = 1;
3171 x = produce_memory_decl_rtl (var, NULL);
3172 SET_DECL_RTL (var, x);
3174 integer_cost = computation_cost (build_int_cst (integer_type_node,
3177 addr = build1 (ADDR_EXPR, type, var);
3178 symbol_cost = computation_cost (addr) + 1;
3181 = computation_cost (build2 (POINTER_PLUS_EXPR, type,
3183 build_int_cst (sizetype, 2000))) + 1;
3184 if (dump_file && (dump_flags & TDF_DETAILS))
3186 fprintf (dump_file, "force_expr_to_var_cost:\n");
3187 fprintf (dump_file, " integer %d\n", (int) integer_cost);
3188 fprintf (dump_file, " symbol %d\n", (int) symbol_cost);
3189 fprintf (dump_file, " address %d\n", (int) address_cost);
3190 fprintf (dump_file, " other %d\n", (int) target_spill_cost);
3191 fprintf (dump_file, "\n");
3194 costs_initialized = true;
3199 if (SSA_VAR_P (expr))
3202 if (TREE_INVARIANT (expr))
3204 if (TREE_CODE (expr) == INTEGER_CST)
3205 return new_cost (integer_cost, 0);
3207 if (TREE_CODE (expr) == ADDR_EXPR)
3209 tree obj = TREE_OPERAND (expr, 0);
3211 if (TREE_CODE (obj) == VAR_DECL
3212 || TREE_CODE (obj) == PARM_DECL
3213 || TREE_CODE (obj) == RESULT_DECL)
3214 return new_cost (symbol_cost, 0);
3217 return new_cost (address_cost, 0);
3220 switch (TREE_CODE (expr))
3222 case POINTER_PLUS_EXPR:
3226 op0 = TREE_OPERAND (expr, 0);
3227 op1 = TREE_OPERAND (expr, 1);
3231 if (is_gimple_val (op0))
3234 cost0 = force_expr_to_var_cost (op0);
3236 if (is_gimple_val (op1))
3239 cost1 = force_expr_to_var_cost (op1);
3244 /* Just an arbitrary value, FIXME. */
3245 return new_cost (target_spill_cost, 0);
3248 mode = TYPE_MODE (TREE_TYPE (expr));
3249 switch (TREE_CODE (expr))
3251 case POINTER_PLUS_EXPR:
3254 cost = new_cost (add_cost (mode), 0);
3258 if (cst_and_fits_in_hwi (op0))
3259 cost = new_cost (multiply_by_cost (int_cst_value (op0), mode), 0);
3260 else if (cst_and_fits_in_hwi (op1))
3261 cost = new_cost (multiply_by_cost (int_cst_value (op1), mode), 0);
3263 return new_cost (target_spill_cost, 0);
3270 cost = add_costs (cost, cost0);
3271 cost = add_costs (cost, cost1);
3273 /* Bound the cost by target_spill_cost. The parts of complicated
3274 computations often are either loop invariant or at least can
3275 be shared between several iv uses, so letting this grow without
3276 limits would not give reasonable results. */
3277 if (cost.cost > target_spill_cost)
3278 cost.cost = target_spill_cost;
3283 /* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
3284 invariants the computation depends on. */
3287 force_var_cost (struct ivopts_data *data,
3288 tree expr, bitmap *depends_on)
3292 fd_ivopts_data = data;
3293 walk_tree (&expr, find_depends, depends_on, NULL);
3296 return force_expr_to_var_cost (expr);
3299 /* Estimates cost of expressing address ADDR as var + symbol + offset. The
3300 value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
3301 to false if the corresponding part is missing. DEPENDS_ON is a set of the
3302 invariants the computation depends on. */
3305 split_address_cost (struct ivopts_data *data,
3306 tree addr, bool *symbol_present, bool *var_present,
3307 unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
3310 HOST_WIDE_INT bitsize;
3311 HOST_WIDE_INT bitpos;
3313 enum machine_mode mode;
3314 int unsignedp, volatilep;
3316 core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode,
3317 &unsignedp, &volatilep, false);
3320 || bitpos % BITS_PER_UNIT != 0
3321 || TREE_CODE (core) != VAR_DECL)
3323 *symbol_present = false;
3324 *var_present = true;
3325 fd_ivopts_data = data;
3326 walk_tree (&addr, find_depends, depends_on, NULL);
3327 return new_cost (target_spill_cost, 0);
3330 *offset += bitpos / BITS_PER_UNIT;
3331 if (TREE_STATIC (core)
3332 || DECL_EXTERNAL (core))
3334 *symbol_present = true;
3335 *var_present = false;
3339 *symbol_present = false;
3340 *var_present = true;
3344 /* Estimates cost of expressing difference of addresses E1 - E2 as
3345 var + symbol + offset. The value of offset is added to OFFSET,
3346 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3347 part is missing. DEPENDS_ON is a set of the invariants the computation
3351 ptr_difference_cost (struct ivopts_data *data,
3352 tree e1, tree e2, bool *symbol_present, bool *var_present,
3353 unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
3355 HOST_WIDE_INT diff = 0;
3358 gcc_assert (TREE_CODE (e1) == ADDR_EXPR);
3360 if (ptr_difference_const (e1, e2, &diff))
3363 *symbol_present = false;
3364 *var_present = false;
3368 if (integer_zerop (e2))
3369 return split_address_cost (data, TREE_OPERAND (e1, 0),
3370 symbol_present, var_present, offset, depends_on);
3372 *symbol_present = false;
3373 *var_present = true;
3375 cost = force_var_cost (data, e1, depends_on);
3376 cost = add_costs (cost, force_var_cost (data, e2, depends_on));
3377 cost.cost += add_cost (Pmode);
3382 /* Estimates cost of expressing difference E1 - E2 as
3383 var + symbol + offset. The value of offset is added to OFFSET,
3384 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3385 part is missing. DEPENDS_ON is a set of the invariants the computation
3389 difference_cost (struct ivopts_data *data,
3390 tree e1, tree e2, bool *symbol_present, bool *var_present,
3391 unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
3394 enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
3395 unsigned HOST_WIDE_INT off1, off2;
3397 e1 = strip_offset (e1, &off1);
3398 e2 = strip_offset (e2, &off2);
3399 *offset += off1 - off2;
3404 if (TREE_CODE (e1) == ADDR_EXPR)
3405 return ptr_difference_cost (data, e1, e2, symbol_present, var_present, offset,
3407 *symbol_present = false;
3409 if (operand_equal_p (e1, e2, 0))
3411 *var_present = false;
3414 *var_present = true;
3415 if (integer_zerop (e2))
3416 return force_var_cost (data, e1, depends_on);
3418 if (integer_zerop (e1))
3420 cost = force_var_cost (data, e2, depends_on);
3421 cost.cost += multiply_by_cost (-1, mode);
3426 cost = force_var_cost (data, e1, depends_on);
3427 cost = add_costs (cost, force_var_cost (data, e2, depends_on));
3428 cost.cost += add_cost (mode);
3433 /* Determines the cost of the computation by that USE is expressed
3434 from induction variable CAND. If ADDRESS_P is true, we just need
3435 to create an address from it, otherwise we want to get it into
3436 register. A set of invariants we depend on is stored in
3437 DEPENDS_ON. AT is the statement at that the value is computed. */
3440 get_computation_cost_at (struct ivopts_data *data,
3441 struct iv_use *use, struct iv_cand *cand,
3442 bool address_p, bitmap *depends_on, tree at)
3444 tree ubase = use->iv->base, ustep = use->iv->step;
3446 tree utype = TREE_TYPE (ubase), ctype;
3447 unsigned HOST_WIDE_INT cstepi, offset = 0;
3448 HOST_WIDE_INT ratio, aratio;
3449 bool var_present, symbol_present;
3456 /* Only consider real candidates. */
3458 return infinite_cost;
3460 cbase = cand->iv->base;
3461 cstep = cand->iv->step;
3462 ctype = TREE_TYPE (cbase);
3464 if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
3466 /* We do not have a precision to express the values of use. */
3467 return infinite_cost;
3472 /* Do not try to express address of an object with computation based
3473 on address of a different object. This may cause problems in rtl
3474 level alias analysis (that does not expect this to be happening,
3475 as this is illegal in C), and would be unlikely to be useful
3477 if (use->iv->base_object
3478 && cand->iv->base_object
3479 && !operand_equal_p (use->iv->base_object, cand->iv->base_object, 0))
3480 return infinite_cost;
3483 if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
3485 /* TODO -- add direct handling of this case. */
3489 /* CSTEPI is removed from the offset in case statement is after the
3490 increment. If the step is not constant, we use zero instead.
3491 This is a bit imprecise (there is the extra addition), but
3492 redundancy elimination is likely to transform the code so that
3493 it uses value of the variable before increment anyway,
3494 so it is not that much unrealistic. */
3495 if (cst_and_fits_in_hwi (cstep))
3496 cstepi = int_cst_value (cstep);
3500 if (!constant_multiple_of (ustep, cstep, &rat))
3501 return infinite_cost;
3503 if (double_int_fits_in_shwi_p (rat))
3504 ratio = double_int_to_shwi (rat);
3506 return infinite_cost;
3508 /* use = ubase + ratio * (var - cbase). If either cbase is a constant
3509 or ratio == 1, it is better to handle this like
3511 ubase - ratio * cbase + ratio * var
3513 (also holds in the case ratio == -1, TODO. */
3515 if (cst_and_fits_in_hwi (cbase))
3517 offset = - ratio * int_cst_value (cbase);
3518 cost = difference_cost (data,
3519 ubase, build_int_cst (utype, 0),
3520 &symbol_present, &var_present, &offset,
3523 else if (ratio == 1)
3525 cost = difference_cost (data,
3527 &symbol_present, &var_present, &offset,
3532 cost = force_var_cost (data, cbase, depends_on);
3533 cost.cost += add_cost (TYPE_MODE (ctype));
3534 cost = add_costs (cost,
3535 difference_cost (data,
3536 ubase, build_int_cst (utype, 0),
3537 &symbol_present, &var_present,
3538 &offset, depends_on));
3541 /* If we are after the increment, the value of the candidate is higher by
3543 if (stmt_after_increment (data->current_loop, cand, at))
3544 offset -= ratio * cstepi;
3546 /* Now the computation is in shape symbol + var1 + const + ratio * var2.
3547 (symbol/var/const parts may be omitted). If we are looking for an address,
3548 find the cost of addressing this. */
3550 return add_costs (cost, get_address_cost (symbol_present, var_present,
3552 TYPE_MODE (TREE_TYPE (*use->op_p))));
3554 /* Otherwise estimate the costs for computing the expression. */
3555 aratio = ratio > 0 ? ratio : -ratio;
3556 if (!symbol_present && !var_present && !offset)
3559 cost.cost += multiply_by_cost (ratio, TYPE_MODE (ctype));
3565 cost.cost += multiply_by_cost (aratio, TYPE_MODE (ctype));
3569 /* Symbol + offset should be compile-time computable. */
3570 && (symbol_present || offset))
3573 /* Having offset does not affect runtime cost in case it is added to
3574 symbol, but it increases complexity. */
3578 cost.cost += n_sums * add_cost (TYPE_MODE (ctype));
3583 /* Just get the expression, expand it and measure the cost. */
3584 tree comp = get_computation_at (data->current_loop, use, cand, at);
3587 return infinite_cost;
3590 comp = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (comp)), comp);
3592 return new_cost (computation_cost (comp), 0);
3596 /* Determines the cost of the computation by that USE is expressed
3597 from induction variable CAND. If ADDRESS_P is true, we just need
3598 to create an address from it, otherwise we want to get it into
3599 register. A set of invariants we depend on is stored in
3603 get_computation_cost (struct ivopts_data *data,
3604 struct iv_use *use, struct iv_cand *cand,
3605 bool address_p, bitmap *depends_on)
3607 return get_computation_cost_at (data,
3608 use, cand, address_p, depends_on, use->stmt);
3611 /* Determines cost of basing replacement of USE on CAND in a generic
3615 determine_use_iv_cost_generic (struct ivopts_data *data,
3616 struct iv_use *use, struct iv_cand *cand)
3621 /* The simple case first -- if we need to express value of the preserved
3622 original biv, the cost is 0. This also prevents us from counting the
3623 cost of increment twice -- once at this use and once in the cost of
3625 if (cand->pos == IP_ORIGINAL
3626 && cand->incremented_at == use->stmt)
3628 set_use_iv_cost (data, use, cand, zero_cost, NULL, NULL_TREE);
3632 cost = get_computation_cost (data, use, cand, false, &depends_on);
3633 set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
3635 return !infinite_cost_p (cost);
3638 /* Determines cost of basing replacement of USE on CAND in an address. */
3641 determine_use_iv_cost_address (struct ivopts_data *data,
3642 struct iv_use *use, struct iv_cand *cand)
3645 comp_cost cost = get_computation_cost (data, use, cand, true, &depends_on);
3647 set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
3649 return !infinite_cost_p (cost);
3652 /* Computes value of candidate CAND at position AT in iteration NITER, and
3653 stores it to VAL. */
3656 cand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter,
3659 aff_tree step, delta, nit;
3660 struct iv *iv = cand->iv;
3661 tree type = TREE_TYPE (iv->base);
3663 tree_to_aff_combination (iv->step, type, &step);
3664 tree_to_aff_combination (niter, TREE_TYPE (niter), &nit);
3665 aff_combination_convert (&nit, type);
3666 aff_combination_mult (&nit, &step, &delta);
3667 if (stmt_after_increment (loop, cand, at))
3668 aff_combination_add (&delta, &step);
3670 tree_to_aff_combination (iv->base, type, val);
3671 aff_combination_add (val, &delta);
3674 /* Returns period of induction variable iv. */
3677 iv_period (struct iv *iv)
3679 tree step = iv->step, period, type;
3682 gcc_assert (step && TREE_CODE (step) == INTEGER_CST);
3684 /* Period of the iv is gcd (step, type range). Since type range is power
3685 of two, it suffices to determine the maximum power of two that divides
3687 pow2div = num_ending_zeros (step);
3688 type = unsigned_type_for (TREE_TYPE (step));
3690 period = build_low_bits_mask (type,
3691 (TYPE_PRECISION (type)
3692 - tree_low_cst (pow2div, 1)));
3697 /* Returns the comparison operator used when eliminating the iv USE. */
3699 static enum tree_code
3700 iv_elimination_compare (struct ivopts_data *data, struct iv_use *use)
3702 struct loop *loop = data->current_loop;
3706 ex_bb = bb_for_stmt (use->stmt);
3707 exit = EDGE_SUCC (ex_bb, 0);
3708 if (flow_bb_inside_loop_p (loop, exit->dest))
3709 exit = EDGE_SUCC (ex_bb, 1);
3711 return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
3714 /* Check whether it is possible to express the condition in USE by comparison
3715 of candidate CAND. If so, store the value compared with to BOUND. */
3718 may_eliminate_iv (struct ivopts_data *data,
3719 struct iv_use *use, struct iv_cand *cand, tree *bound)
3724 struct loop *loop = data->current_loop;
3726 double_int period_value, max_niter;
3728 if (TREE_CODE (cand->iv->step) != INTEGER_CST)
3731 /* For now works only for exits that dominate the loop latch. TODO -- extend
3732 for other conditions inside loop body. */
3733 ex_bb = bb_for_stmt (use->stmt);
3734 if (use->stmt != last_stmt (ex_bb)
3735 || TREE_CODE (use->stmt) != COND_EXPR)
3737 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, ex_bb))
3740 exit = EDGE_SUCC (ex_bb, 0);
3741 if (flow_bb_inside_loop_p (loop, exit->dest))
3742 exit = EDGE_SUCC (ex_bb, 1);
3743 if (flow_bb_inside_loop_p (loop, exit->dest))
3746 nit = niter_for_exit (data, exit);
3750 /* Determine whether we may use the variable to test whether niter iterations
3751 elapsed. This is the case iff the period of the induction variable is
3752 greater than the number of iterations. */
3753 period = iv_period (cand->iv);
3757 /* Compare the period with the estimate on the number of iterations of the
3759 if (!estimated_loop_iterations (loop, true, &max_niter))
3761 period_value = tree_to_double_int (period);
3762 if (double_int_ucmp (period_value, max_niter) <= 0)
3765 cand_value_at (loop, cand, use->stmt, nit, &bnd);
3766 *bound = aff_combination_to_tree (&bnd);
3770 /* Determines cost of basing replacement of USE on CAND in a condition. */
3773 determine_use_iv_cost_condition (struct ivopts_data *data,
3774 struct iv_use *use, struct iv_cand *cand)
3776 tree bound = NULL_TREE;
3778 bitmap depends_on_elim = NULL, depends_on_express = NULL, depends_on;
3779 comp_cost elim_cost, express_cost, cost;
3782 /* Only consider real candidates. */
3785 set_use_iv_cost (data, use, cand, infinite_cost, NULL, NULL_TREE);
3789 /* Try iv elimination. */
3790 if (may_eliminate_iv (data, use, cand, &bound))
3792 elim_cost = force_var_cost (data, bound, &depends_on_elim);
3793 /* The bound is a loop invariant, so it will be only computed
3795 elim_cost.cost /= AVG_LOOP_NITER (data->current_loop);
3798 elim_cost = infinite_cost;
3800 /* Try expressing the original giv. If it is compared with an invariant,
3801 note that we cannot get rid of it. */
3802 ok = extract_cond_operands (data, use->op_p, NULL, NULL, NULL, &cmp_iv);
3805 express_cost = get_computation_cost (data, use, cand, false,
3806 &depends_on_express);
3807 fd_ivopts_data = data;
3808 walk_tree (&cmp_iv->base, find_depends, &depends_on_express, NULL);
3810 /* Choose the better approach. */
3811 if (compare_costs (elim_cost, express_cost) < 0)
3814 depends_on = depends_on_elim;
3815 depends_on_elim = NULL;
3819 cost = express_cost;
3820 depends_on = depends_on_express;
3821 depends_on_express = NULL;
3825 set_use_iv_cost (data, use, cand, cost, depends_on, bound);
3827 if (depends_on_elim)
3828 BITMAP_FREE (depends_on_elim);
3829 if (depends_on_express)
3830 BITMAP_FREE (depends_on_express);
3832 return !infinite_cost_p (cost);
3835 /* Determines cost of basing replacement of USE on CAND. Returns false
3836 if USE cannot be based on CAND. */
3839 determine_use_iv_cost (struct ivopts_data *data,
3840 struct iv_use *use, struct iv_cand *cand)
3844 case USE_NONLINEAR_EXPR:
3845 return determine_use_iv_cost_generic (data, use, cand);
3848 return determine_use_iv_cost_address (data, use, cand);
3851 return determine_use_iv_cost_condition (data, use, cand);
3858 /* Determines costs of basing the use of the iv on an iv candidate. */
3861 determine_use_iv_costs (struct ivopts_data *data)
3865 struct iv_cand *cand;
3866 bitmap to_clear = BITMAP_ALLOC (NULL);
3868 alloc_use_cost_map (data);
3870 for (i = 0; i < n_iv_uses (data); i++)
3872 use = iv_use (data, i);
3874 if (data->consider_all_candidates)
3876 for (j = 0; j < n_iv_cands (data); j++)
3878 cand = iv_cand (data, j);
3879 determine_use_iv_cost (data, use, cand);
3886 EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi)
3888 cand = iv_cand (data, j);
3889 if (!determine_use_iv_cost (data, use, cand))
3890 bitmap_set_bit (to_clear, j);
3893 /* Remove the candidates for that the cost is infinite from
3894 the list of related candidates. */
3895 bitmap_and_compl_into (use->related_cands, to_clear);
3896 bitmap_clear (to_clear);
3900 BITMAP_FREE (to_clear);
3902 if (dump_file && (dump_flags & TDF_DETAILS))
3904 fprintf (dump_file, "Use-candidate costs:\n");
3906 for (i = 0; i < n_iv_uses (data); i++)
3908 use = iv_use (data, i);
3910 fprintf (dump_file, "Use %d:\n", i);
3911 fprintf (dump_file, " cand\tcost\tcompl.\tdepends on\n");
3912 for (j = 0; j < use->n_map_members; j++)
3914 if (!use->cost_map[j].cand
3915 || infinite_cost_p (use->cost_map[j].cost))
3918 fprintf (dump_file, " %d\t%d\t%d\t",
3919 use->cost_map[j].cand->id,
3920 use->cost_map[j].cost.cost,
3921 use->cost_map[j].cost.complexity);
3922 if (use->cost_map[j].depends_on)
3923 bitmap_print (dump_file,
3924 use->cost_map[j].depends_on, "","");
3925 fprintf (dump_file, "\n");
3928 fprintf (dump_file, "\n");
3930 fprintf (dump_file, "\n");
3934 /* Determines cost of the candidate CAND. */
3937 determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
3939 comp_cost cost_base;
3940 unsigned cost, cost_step;
3949 /* There are two costs associated with the candidate -- its increment
3950 and its initialization. The second is almost negligible for any loop
3951 that rolls enough, so we take it just very little into account. */
3953 base = cand->iv->base;
3954 cost_base = force_var_cost (data, base, NULL);
3955 cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
3957 cost = cost_step + cost_base.cost / AVG_LOOP_NITER (current_loop);
3959 /* Prefer the original ivs unless we may gain something by replacing it.
3960 The reason is to makee debugging simpler; so this is not relevant for
3961 artificial ivs created by other optimization passes. */
3962 if (cand->pos != IP_ORIGINAL
3963 || DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
3966 /* Prefer not to insert statements into latch unless there are some
3967 already (so that we do not create unnecessary jumps). */
3968 if (cand->pos == IP_END
3969 && empty_block_p (ip_end_pos (data->current_loop)))
3975 /* Determines costs of computation of the candidates. */
3978 determine_iv_costs (struct ivopts_data *data)
3982 if (dump_file && (dump_flags & TDF_DETAILS))
3984 fprintf (dump_file, "Candidate costs:\n");
3985 fprintf (dump_file, " cand\tcost\n");
3988 for (i = 0; i < n_iv_cands (data); i++)
3990 struct iv_cand *cand = iv_cand (data, i);
3992 determine_iv_cost (data, cand);
3994 if (dump_file && (dump_flags & TDF_DETAILS))
3995 fprintf (dump_file, " %d\t%d\n", i, cand->cost);
3998 if (dump_file && (dump_flags & TDF_DETAILS))
3999 fprintf (dump_file, "\n");
4002 /* Calculates cost for having SIZE induction variables. */
4005 ivopts_global_cost_for_size (struct ivopts_data *data, unsigned size)
4007 /* We add size to the cost, so that we prefer eliminating ivs
4009 return size + estimate_reg_pressure_cost (size, data->regs_used);
4012 /* For each size of the induction variable set determine the penalty. */
4015 determine_set_costs (struct ivopts_data *data)
4019 struct loop *loop = data->current_loop;
4022 /* We use the following model (definitely improvable, especially the
4023 cost function -- TODO):
4025 We estimate the number of registers available (using MD data), name it A.
4027 We estimate the number of registers used by the loop, name it U. This
4028 number is obtained as the number of loop phi nodes (not counting virtual
4029 registers and bivs) + the number of variables from outside of the loop.
4031 We set a reserve R (free regs that are used for temporary computations,
4032 etc.). For now the reserve is a constant 3.
4034 Let I be the number of induction variables.
4036 -- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
4037 make a lot of ivs without a reason).
4038 -- if A - R < U + I <= A, the cost is I * PRES_COST
4039 -- if U + I > A, the cost is I * PRES_COST and
4040 number of uses * SPILL_COST * (U + I - A) / (U + I) is added. */
4042 if (dump_file && (dump_flags & TDF_DETAILS))
4044 fprintf (dump_file, "Global costs:\n");
4045 fprintf (dump_file, " target_avail_regs %d\n", target_avail_regs);
4046 fprintf (dump_file, " target_reg_cost %d\n", target_reg_cost);
4047 fprintf (dump_file, " target_spill_cost %d\n", target_spill_cost);
4051 for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
4053 op = PHI_RESULT (phi);
4055 if (!is_gimple_reg (op))
4058 if (get_iv (data, op))
4064 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
4066 struct version_info *info = ver_info (data, j);
4068 if (info->inv_id && info->has_nonlin_use)
4072 data->regs_used = n;
4073 if (dump_file && (dump_flags & TDF_DETAILS))
4074 fprintf (dump_file, " regs_used %d\n", n);
4076 if (dump_file && (dump_flags & TDF_DETAILS))
4078 fprintf (dump_file, " cost for size:\n");
4079 fprintf (dump_file, " ivs\tcost\n");
4080 for (j = 0; j <= 2 * target_avail_regs; j++)
4081 fprintf (dump_file, " %d\t%d\n", j,
4082 ivopts_global_cost_for_size (data, j));
4083 fprintf (dump_file, "\n");
4087 /* Returns true if A is a cheaper cost pair than B. */
4090 cheaper_cost_pair (struct cost_pair *a, struct cost_pair *b)
4100 cmp = compare_costs (a->cost, b->cost);
4107 /* In case the costs are the same, prefer the cheaper candidate. */
4108 if (a->cand->cost < b->cand->cost)
4114 /* Computes the cost field of IVS structure. */
4117 iv_ca_recount_cost (struct ivopts_data *data, struct iv_ca *ivs)
4119 comp_cost cost = ivs->cand_use_cost;
4120 cost.cost += ivs->cand_cost;
4121 cost.cost += ivopts_global_cost_for_size (data, ivs->n_regs);
4126 /* Remove invariants in set INVS to set IVS. */
4129 iv_ca_set_remove_invariants (struct iv_ca *ivs, bitmap invs)
4137 EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
4139 ivs->n_invariant_uses[iid]--;
4140 if (ivs->n_invariant_uses[iid] == 0)
4145 /* Set USE not to be expressed by any candidate in IVS. */
4148 iv_ca_set_no_cp (struct ivopts_data *data, struct iv_ca *ivs,
4151 unsigned uid = use->id, cid;
4152 struct cost_pair *cp;
4154 cp = ivs->cand_for_use[uid];
4160 ivs->cand_for_use[uid] = NULL;
4161 ivs->n_cand_uses[cid]--;
4163 if (ivs->n_cand_uses[cid] == 0)
4165 bitmap_clear_bit (ivs->cands, cid);
4166 /* Do not count the pseudocandidates. */
4170 ivs->cand_cost -= cp->cand->cost;
4172 iv_ca_set_remove_invariants (ivs, cp->cand->depends_on);
4175 ivs->cand_use_cost = sub_costs (ivs->cand_use_cost, cp->cost);
4177 iv_ca_set_remove_invariants (ivs, cp->depends_on);
4178 iv_ca_recount_cost (data, ivs);
4181 /* Add invariants in set INVS to set IVS. */
4184 iv_ca_set_add_invariants (struct iv_ca *ivs, bitmap invs)
4192 EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
4194 ivs->n_invariant_uses[iid]++;
4195 if (ivs->n_invariant_uses[iid] == 1)
4200 /* Set cost pair for USE in set IVS to CP. */
4203 iv_ca_set_cp (struct ivopts_data *data, struct iv_ca *ivs,
4204 struct iv_use *use, struct cost_pair *cp)
4206 unsigned uid = use->id, cid;
4208 if (ivs->cand_for_use[uid] == cp)
4211 if (ivs->cand_for_use[uid])
4212 iv_ca_set_no_cp (data, ivs, use);
4219 ivs->cand_for_use[uid] = cp;
4220 ivs->n_cand_uses[cid]++;
4221 if (ivs->n_cand_uses[cid] == 1)
4223 bitmap_set_bit (ivs->cands, cid);
4224 /* Do not count the pseudocandidates. */
4228 ivs->cand_cost += cp->cand->cost;
4230 iv_ca_set_add_invariants (ivs, cp->cand->depends_on);
4233 ivs->cand_use_cost = add_costs (ivs->cand_use_cost, cp->cost);
4234 iv_ca_set_add_invariants (ivs, cp->depends_on);
4235 iv_ca_recount_cost (data, ivs);
4239 /* Extend set IVS by expressing USE by some of the candidates in it
4243 iv_ca_add_use (struct ivopts_data *data, struct iv_ca *ivs,
4246 struct cost_pair *best_cp = NULL, *cp;
4250 gcc_assert (ivs->upto >= use->id);
4252 if (ivs->upto == use->id)
4258 EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
4260 cp = get_use_iv_cost (data, use, iv_cand (data, i));
4262 if (cheaper_cost_pair (cp, best_cp))
4266 iv_ca_set_cp (data, ivs, use, best_cp);
4269 /* Get cost for assignment IVS. */
4272 iv_ca_cost (struct iv_ca *ivs)
4274 return (ivs->bad_uses ? infinite_cost : ivs->cost);
4277 /* Returns true if all dependences of CP are among invariants in IVS. */
4280 iv_ca_has_deps (struct iv_ca *ivs, struct cost_pair *cp)
4285 if (!cp->depends_on)
4288 EXECUTE_IF_SET_IN_BITMAP (cp->depends_on, 0, i, bi)
4290 if (ivs->n_invariant_uses[i] == 0)
4297 /* Creates change of expressing USE by NEW_CP instead of OLD_CP and chains
4298 it before NEXT_CHANGE. */
4300 static struct iv_ca_delta *
4301 iv_ca_delta_add (struct iv_use *use, struct cost_pair *old_cp,
4302 struct cost_pair *new_cp, struct iv_ca_delta *next_change)
4304 struct iv_ca_delta *change = XNEW (struct iv_ca_delta);
4307 change->old_cp = old_cp;
4308 change->new_cp = new_cp;
4309 change->next_change = next_change;
4314 /* Joins two lists of changes L1 and L2. Destructive -- old lists
4317 static struct iv_ca_delta *
4318 iv_ca_delta_join (struct iv_ca_delta *l1, struct iv_ca_delta *l2)
4320 struct iv_ca_delta *last;
4328 for (last = l1; last->next_change; last = last->next_change)
4330 last->next_change = l2;
4335 /* Returns candidate by that USE is expressed in IVS. */
4337 static struct cost_pair *
4338 iv_ca_cand_for_use (struct iv_ca *ivs, struct iv_use *use)
4340 return ivs->cand_for_use[use->id];
4343 /* Reverse the list of changes DELTA, forming the inverse to it. */
4345 static struct iv_ca_delta *
4346 iv_ca_delta_reverse (struct iv_ca_delta *delta)
4348 struct iv_ca_delta *act, *next, *prev = NULL;
4349 struct cost_pair *tmp;
4351 for (act = delta; act; act = next)
4353 next = act->next_change;
4354 act->next_change = prev;
4358 act->old_cp = act->new_cp;
4365 /* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
4366 reverted instead. */
4369 iv_ca_delta_commit (struct ivopts_data *data, struct iv_ca *ivs,
4370 struct iv_ca_delta *delta, bool forward)
4372 struct cost_pair *from, *to;
4373 struct iv_ca_delta *act;
4376 delta = iv_ca_delta_reverse (delta);
4378 for (act = delta; act; act = act->next_change)
4382 gcc_assert (iv_ca_cand_for_use (ivs, act->use) == from);
4383 iv_ca_set_cp (data, ivs, act->use, to);
4387 iv_ca_delta_reverse (delta);
4390 /* Returns true if CAND is used in IVS. */
4393 iv_ca_cand_used_p (struct iv_ca *ivs, struct iv_cand *cand)
4395 return ivs->n_cand_uses[cand->id] > 0;
4398 /* Returns number of induction variable candidates in the set IVS. */
4401 iv_ca_n_cands (struct iv_ca *ivs)
4403 return ivs->n_cands;
4406 /* Free the list of changes DELTA. */
4409 iv_ca_delta_free (struct iv_ca_delta **delta)
4411 struct iv_ca_delta *act, *next;
4413 for (act = *delta; act; act = next)
4415 next = act->next_change;
4422 /* Allocates new iv candidates assignment. */
4424 static struct iv_ca *
4425 iv_ca_new (struct ivopts_data *data)
4427 struct iv_ca *nw = XNEW (struct iv_ca);
4431 nw->cand_for_use = XCNEWVEC (struct cost_pair *, n_iv_uses (data));
4432 nw->n_cand_uses = XCNEWVEC (unsigned, n_iv_cands (data));
4433 nw->cands = BITMAP_ALLOC (NULL);
4436 nw->cand_use_cost = zero_cost;
4438 nw->n_invariant_uses = XCNEWVEC (unsigned, data->max_inv_id + 1);
4439 nw->cost = zero_cost;
4444 /* Free memory occupied by the set IVS. */
4447 iv_ca_free (struct iv_ca **ivs)
4449 free ((*ivs)->cand_for_use);
4450 free ((*ivs)->n_cand_uses);
4451 BITMAP_FREE ((*ivs)->cands);
4452 free ((*ivs)->n_invariant_uses);
4457 /* Dumps IVS to FILE. */
4460 iv_ca_dump (struct ivopts_data *data, FILE *file, struct iv_ca *ivs)
4462 const char *pref = " invariants ";
4464 comp_cost cost = iv_ca_cost (ivs);
4466 fprintf (file, " cost %d (complexity %d)\n", cost.cost, cost.complexity);
4467 bitmap_print (file, ivs->cands, " candidates ","\n");
4469 for (i = 1; i <= data->max_inv_id; i++)
4470 if (ivs->n_invariant_uses[i])
4472 fprintf (file, "%s%d", pref, i);
4475 fprintf (file, "\n");
4478 /* Try changing candidate in IVS to CAND for each use. Return cost of the
4479 new set, and store differences in DELTA. Number of induction variables
4480 in the new set is stored to N_IVS. */
4483 iv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs,
4484 struct iv_cand *cand, struct iv_ca_delta **delta,
4490 struct cost_pair *old_cp, *new_cp;
4493 for (i = 0; i < ivs->upto; i++)
4495 use = iv_use (data, i);
4496 old_cp = iv_ca_cand_for_use (ivs, use);
4499 && old_cp->cand == cand)
4502 new_cp = get_use_iv_cost (data, use, cand);
4506 if (!iv_ca_has_deps (ivs, new_cp))
4509 if (!cheaper_cost_pair (new_cp, old_cp))
4512 *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
4515 iv_ca_delta_commit (data, ivs, *delta, true);
4516 cost = iv_ca_cost (ivs);
4518 *n_ivs = iv_ca_n_cands (ivs);
4519 iv_ca_delta_commit (data, ivs, *delta, false);
4524 /* Try narrowing set IVS by removing CAND. Return the cost of
4525 the new set and store the differences in DELTA. */
4528 iv_ca_narrow (struct ivopts_data *data, struct iv_ca *ivs,
4529 struct iv_cand *cand, struct iv_ca_delta **delta)
4533 struct cost_pair *old_cp, *new_cp, *cp;
4535 struct iv_cand *cnd;
4539 for (i = 0; i < n_iv_uses (data); i++)
4541 use = iv_use (data, i);
4543 old_cp = iv_ca_cand_for_use (ivs, use);
4544 if (old_cp->cand != cand)
4549 if (data->consider_all_candidates)
4551 EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, ci, bi)
4556 cnd = iv_cand (data, ci);
4558 cp = get_use_iv_cost (data, use, cnd);
4561 if (!iv_ca_has_deps (ivs, cp))
4564 if (!cheaper_cost_pair (cp, new_cp))
4572 EXECUTE_IF_AND_IN_BITMAP (use->related_cands, ivs->cands, 0, ci, bi)
4577 cnd = iv_cand (data, ci);
4579 cp = get_use_iv_cost (data, use, cnd);
4582 if (!iv_ca_has_deps (ivs, cp))
4585 if (!cheaper_cost_pair (cp, new_cp))
4594 iv_ca_delta_free (delta);
4595 return infinite_cost;
4598 *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
4601 iv_ca_delta_commit (data, ivs, *delta, true);
4602 cost = iv_ca_cost (ivs);
4603 iv_ca_delta_commit (data, ivs, *delta, false);
4608 /* Try optimizing the set of candidates IVS by removing candidates different
4609 from to EXCEPT_CAND from it. Return cost of the new set, and store
4610 differences in DELTA. */
4613 iv_ca_prune (struct ivopts_data *data, struct iv_ca *ivs,
4614 struct iv_cand *except_cand, struct iv_ca_delta **delta)
4617 struct iv_ca_delta *act_delta, *best_delta;
4619 comp_cost best_cost, acost;
4620 struct iv_cand *cand;
4623 best_cost = iv_ca_cost (ivs);
4625 EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
4627 cand = iv_cand (data, i);
4629 if (cand == except_cand)
4632 acost = iv_ca_narrow (data, ivs, cand, &act_delta);
4634 if (compare_costs (acost, best_cost) < 0)
4637 iv_ca_delta_free (&best_delta);
4638 best_delta = act_delta;
4641 iv_ca_delta_free (&act_delta);
4650 /* Recurse to possibly remove other unnecessary ivs. */
4651 iv_ca_delta_commit (data, ivs, best_delta, true);
4652 best_cost = iv_ca_prune (data, ivs, except_cand, delta);
4653 iv_ca_delta_commit (data, ivs, best_delta, false);
4654 *delta = iv_ca_delta_join (best_delta, *delta);
4658 /* Tries to extend the sets IVS in the best possible way in order
4659 to express the USE. */
4662 try_add_cand_for (struct ivopts_data *data, struct iv_ca *ivs,
4665 comp_cost best_cost, act_cost;
4668 struct iv_cand *cand;
4669 struct iv_ca_delta *best_delta = NULL, *act_delta;
4670 struct cost_pair *cp;
4672 iv_ca_add_use (data, ivs, use);
4673 best_cost = iv_ca_cost (ivs);
4675 cp = iv_ca_cand_for_use (ivs, use);
4678 best_delta = iv_ca_delta_add (use, NULL, cp, NULL);
4679 iv_ca_set_no_cp (data, ivs, use);
4682 /* First try important candidates not based on any memory object. Only if
4683 this fails, try the specific ones. Rationale -- in loops with many
4684 variables the best choice often is to use just one generic biv. If we
4685 added here many ivs specific to the uses, the optimization algorithm later
4686 would be likely to get stuck in a local minimum, thus causing us to create
4687 too many ivs. The approach from few ivs to more seems more likely to be
4688 successful -- starting from few ivs, replacing an expensive use by a
4689 specific iv should always be a win. */
4690 EXECUTE_IF_SET_IN_BITMAP (data->important_candidates, 0, i, bi)
4692 cand = iv_cand (data, i);
4694 if (cand->iv->base_object != NULL_TREE)
4697 if (iv_ca_cand_used_p (ivs, cand))
4700 cp = get_use_iv_cost (data, use, cand);
4704 iv_ca_set_cp (data, ivs, use, cp);
4705 act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
4706 iv_ca_set_no_cp (data, ivs, use);
4707 act_delta = iv_ca_delta_add (use, NULL, cp, act_delta);
4709 if (compare_costs (act_cost, best_cost) < 0)
4711 best_cost = act_cost;
4713 iv_ca_delta_free (&best_delta);
4714 best_delta = act_delta;
4717 iv_ca_delta_free (&act_delta);
4720 if (infinite_cost_p (best_cost))
4722 for (i = 0; i < use->n_map_members; i++)
4724 cp = use->cost_map + i;
4729 /* Already tried this. */
4730 if (cand->important && cand->iv->base_object == NULL_TREE)
4733 if (iv_ca_cand_used_p (ivs, cand))
4737 iv_ca_set_cp (data, ivs, use, cp);
4738 act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
4739 iv_ca_set_no_cp (data, ivs, use);
4740 act_delta = iv_ca_delta_add (use, iv_ca_cand_for_use (ivs, use),
4743 if (compare_costs (act_cost, best_cost) < 0)
4745 best_cost = act_cost;
4748 iv_ca_delta_free (&best_delta);
4749 best_delta = act_delta;
4752 iv_ca_delta_free (&act_delta);
4756 iv_ca_delta_commit (data, ivs, best_delta, true);
4757 iv_ca_delta_free (&best_delta);
4759 return !infinite_cost_p (best_cost);
4762 /* Finds an initial assignment of candidates to uses. */
4764 static struct iv_ca *
4765 get_initial_solution (struct ivopts_data *data)
4767 struct iv_ca *ivs = iv_ca_new (data);
4770 for (i = 0; i < n_iv_uses (data); i++)
4771 if (!try_add_cand_for (data, ivs, iv_use (data, i)))
4780 /* Tries to improve set of induction variables IVS. */
4783 try_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs)
4786 comp_cost acost, best_cost = iv_ca_cost (ivs);
4787 struct iv_ca_delta *best_delta = NULL, *act_delta, *tmp_delta;
4788 struct iv_cand *cand;
4790 /* Try extending the set of induction variables by one. */
4791 for (i = 0; i < n_iv_cands (data); i++)
4793 cand = iv_cand (data, i);
4795 if (iv_ca_cand_used_p (ivs, cand))
4798 acost = iv_ca_extend (data, ivs, cand, &act_delta, &n_ivs);
4802 /* If we successfully added the candidate and the set is small enough,
4803 try optimizing it by removing other candidates. */
4804 if (n_ivs <= ALWAYS_PRUNE_CAND_SET_BOUND)
4806 iv_ca_delta_commit (data, ivs, act_delta, true);
4807 acost = iv_ca_prune (data, ivs, cand, &tmp_delta);
4808 iv_ca_delta_commit (data, ivs, act_delta, false);
4809 act_delta = iv_ca_delta_join (act_delta, tmp_delta);
4812 if (compare_costs (acost, best_cost) < 0)
4815 iv_ca_delta_free (&best_delta);
4816 best_delta = act_delta;
4819 iv_ca_delta_free (&act_delta);
4824 /* Try removing the candidates from the set instead. */
4825 best_cost = iv_ca_prune (data, ivs, NULL, &best_delta);
4827 /* Nothing more we can do. */
4832 iv_ca_delta_commit (data, ivs, best_delta, true);
4833 gcc_assert (compare_costs (best_cost, iv_ca_cost (ivs)) == 0);
4834 iv_ca_delta_free (&best_delta);
4838 /* Attempts to find the optimal set of induction variables. We do simple
4839 greedy heuristic -- we try to replace at most one candidate in the selected
4840 solution and remove the unused ivs while this improves the cost. */
4842 static struct iv_ca *
4843 find_optimal_iv_set (struct ivopts_data *data)
4849 /* Get the initial solution. */
4850 set = get_initial_solution (data);
4853 if (dump_file && (dump_flags & TDF_DETAILS))
4854 fprintf (dump_file, "Unable to substitute for ivs, failed.\n");
4858 if (dump_file && (dump_flags & TDF_DETAILS))
4860 fprintf (dump_file, "Initial set of candidates:\n");
4861 iv_ca_dump (data, dump_file, set);
4864 while (try_improve_iv_set (data, set))
4866 if (dump_file && (dump_flags & TDF_DETAILS))
4868 fprintf (dump_file, "Improved to:\n");
4869 iv_ca_dump (data, dump_file, set);
4873 if (dump_file && (dump_flags & TDF_DETAILS))
4875 comp_cost cost = iv_ca_cost (set);
4876 fprintf (dump_file, "Final cost %d (complexity %d)\n\n", cost.cost, cost.complexity);
4879 for (i = 0; i < n_iv_uses (data); i++)
4881 use = iv_use (data, i);
4882 use->selected = iv_ca_cand_for_use (set, use)->cand;
4888 /* Creates a new induction variable corresponding to CAND. */
4891 create_new_iv (struct ivopts_data *data, struct iv_cand *cand)
4893 block_stmt_iterator incr_pos;
4903 incr_pos = bsi_last (ip_normal_pos (data->current_loop));
4907 incr_pos = bsi_last (ip_end_pos (data->current_loop));
4912 /* Mark that the iv is preserved. */
4913 name_info (data, cand->var_before)->preserve_biv = true;
4914 name_info (data, cand->var_after)->preserve_biv = true;
4916 /* Rewrite the increment so that it uses var_before directly. */
4917 find_interesting_uses_op (data, cand->var_after)->selected = cand;
4922 gimple_add_tmp_var (cand->var_before);
4923 add_referenced_var (cand->var_before);
4925 base = unshare_expr (cand->iv->base);
4927 create_iv (base, unshare_expr (cand->iv->step),
4928 cand->var_before, data->current_loop,
4929 &incr_pos, after, &cand->var_before, &cand->var_after);
4932 /* Creates new induction variables described in SET. */
4935 create_new_ivs (struct ivopts_data *data, struct iv_ca *set)
4938 struct iv_cand *cand;
4941 EXECUTE_IF_SET_IN_BITMAP (set->cands, 0, i, bi)
4943 cand = iv_cand (data, i);
4944 create_new_iv (data, cand);
4948 /* Removes statement STMT (real or a phi node). If INCLUDING_DEFINED_NAME
4949 is true, remove also the ssa name defined by the statement. */
4952 remove_statement (tree stmt, bool including_defined_name)
4954 if (TREE_CODE (stmt) == PHI_NODE)
4956 remove_phi_node (stmt, NULL_TREE, including_defined_name);
4960 block_stmt_iterator bsi = bsi_for_stmt (stmt);
4962 bsi_remove (&bsi, true);
4963 release_defs (stmt);
4967 /* Rewrites USE (definition of iv used in a nonlinear expression)
4968 using candidate CAND. */
4971 rewrite_use_nonlinear_expr (struct ivopts_data *data,
4972 struct iv_use *use, struct iv_cand *cand)
4976 block_stmt_iterator bsi;
4978 /* An important special case -- if we are asked to express value of
4979 the original iv by itself, just exit; there is no need to
4980 introduce a new computation (that might also need casting the
4981 variable to unsigned and back). */
4982 if (cand->pos == IP_ORIGINAL
4983 && cand->incremented_at == use->stmt)
4985 tree step, ctype, utype;
4986 enum tree_code incr_code = PLUS_EXPR;
4988 gcc_assert (TREE_CODE (use->stmt) == GIMPLE_MODIFY_STMT);
4989 gcc_assert (GIMPLE_STMT_OPERAND (use->stmt, 0) == cand->var_after);
4991 step = cand->iv->step;
4992 ctype = TREE_TYPE (step);
4993 utype = TREE_TYPE (cand->var_after);
4994 if (TREE_CODE (step) == NEGATE_EXPR)
4996 incr_code = MINUS_EXPR;
4997 step = TREE_OPERAND (step, 0);
5000 /* Check whether we may leave the computation unchanged.
5001 This is the case only if it does not rely on other
5002 computations in the loop -- otherwise, the computation
5003 we rely upon may be removed in remove_unused_ivs,
5004 thus leading to ICE. */
5005 op = GIMPLE_STMT_OPERAND (use->stmt, 1);
5006 if (TREE_CODE (op) == PLUS_EXPR
5007 || TREE_CODE (op) == MINUS_EXPR
5008 || TREE_CODE (op) == POINTER_PLUS_EXPR)
5010 if (TREE_OPERAND (op, 0) == cand->var_before)
5011 op = TREE_OPERAND (op, 1);
5012 else if (TREE_CODE (op) != MINUS_EXPR
5013 && TREE_OPERAND (op, 1) == cand->var_before)
5014 op = TREE_OPERAND (op, 0);
5022 && (TREE_CODE (op) == INTEGER_CST
5023 || operand_equal_p (op, step, 0)))
5026 /* Otherwise, add the necessary computations to express
5028 op = fold_convert (ctype, cand->var_before);
5029 comp = fold_convert (utype,
5030 build2 (incr_code, ctype, op,
5031 unshare_expr (step)));
5035 comp = get_computation (data->current_loop, use, cand);
5036 gcc_assert (comp != NULL_TREE);
5039 switch (TREE_CODE (use->stmt))
5042 tgt = PHI_RESULT (use->stmt);
5044 /* If we should keep the biv, do not replace it. */
5045 if (name_info (data, tgt)->preserve_biv)
5048 bsi = bsi_after_labels (bb_for_stmt (use->stmt));
5051 case GIMPLE_MODIFY_STMT:
5052 tgt = GIMPLE_STMT_OPERAND (use->stmt, 0);
5053 bsi = bsi_for_stmt (use->stmt);
5060 op = force_gimple_operand_bsi (&bsi, comp, false, SSA_NAME_VAR (tgt),
5061 true, BSI_SAME_STMT);
5063 if (TREE_CODE (use->stmt) == PHI_NODE)
5065 ass = build_gimple_modify_stmt (tgt, op);
5066 bsi_insert_before (&bsi, ass, BSI_SAME_STMT);
5067 remove_statement (use->stmt, false);
5068 SSA_NAME_DEF_STMT (tgt) = ass;
5071 GIMPLE_STMT_OPERAND (use->stmt, 1) = op;
5074 /* Replaces ssa name in index IDX by its basic variable. Callback for
5078 idx_remove_ssa_names (tree base, tree *idx,
5079 void *data ATTRIBUTE_UNUSED)
5083 if (TREE_CODE (*idx) == SSA_NAME)
5084 *idx = SSA_NAME_VAR (*idx);
5086 if (TREE_CODE (base) == ARRAY_REF)
5088 op = &TREE_OPERAND (base, 2);
5090 && TREE_CODE (*op) == SSA_NAME)
5091 *op = SSA_NAME_VAR (*op);
5092 op = &TREE_OPERAND (base, 3);
5094 && TREE_CODE (*op) == SSA_NAME)
5095 *op = SSA_NAME_VAR (*op);
5101 /* Unshares REF and replaces ssa names inside it by their basic variables. */
5104 unshare_and_remove_ssa_names (tree ref)
5106 ref = unshare_expr (ref);
5107 for_each_index (&ref, idx_remove_ssa_names, NULL);
5112 /* Extract the alias analysis info for the memory reference REF. There are
5113 several ways how this information may be stored and what precisely is
5114 its semantics depending on the type of the reference, but there always is
5115 somewhere hidden one _DECL node that is used to determine the set of
5116 virtual operands for the reference. The code below deciphers this jungle
5117 and extracts this single useful piece of information. */
5120 get_ref_tag (tree ref, tree orig)
5122 tree var = get_base_address (ref);
5123 tree aref = NULL_TREE, tag, sv;
5124 HOST_WIDE_INT offset, size, maxsize;
5126 for (sv = orig; handled_component_p (sv); sv = TREE_OPERAND (sv, 0))
5128 aref = get_ref_base_and_extent (sv, &offset, &size, &maxsize);
5133 if (aref && SSA_VAR_P (aref) && get_subvars_for_var (aref))
5139 if (TREE_CODE (var) == INDIRECT_REF)
5141 /* If the base is a dereference of a pointer, first check its name memory
5142 tag. If it does not have one, use its symbol memory tag. */
5143 var = TREE_OPERAND (var, 0);
5144 if (TREE_CODE (var) != SSA_NAME)
5147 if (SSA_NAME_PTR_INFO (var))
5149 tag = SSA_NAME_PTR_INFO (var)->name_mem_tag;
5154 var = SSA_NAME_VAR (var);
5155 tag = symbol_mem_tag (var);
5156 gcc_assert (tag != NULL_TREE);
5164 tag = symbol_mem_tag (var);
5172 /* Copies the reference information from OLD_REF to NEW_REF. */
5175 copy_ref_info (tree new_ref, tree old_ref)
5177 if (TREE_CODE (old_ref) == TARGET_MEM_REF)
5178 copy_mem_ref_info (new_ref, old_ref);
5181 TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
5182 TMR_TAG (new_ref) = get_ref_tag (old_ref, TMR_ORIGINAL (new_ref));
5186 /* Rewrites USE (address that is an iv) using candidate CAND. */
5189 rewrite_use_address (struct ivopts_data *data,
5190 struct iv_use *use, struct iv_cand *cand)
5193 block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
5197 ok = get_computation_aff (data->current_loop, use, cand, use->stmt, &aff);
5199 unshare_aff_combination (&aff);
5201 ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff);
5202 copy_ref_info (ref, *use->op_p);
5206 /* Rewrites USE (the condition such that one of the arguments is an iv) using
5210 rewrite_use_compare (struct ivopts_data *data,
5211 struct iv_use *use, struct iv_cand *cand)
5213 tree comp, *var_p, op, bound;
5214 block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
5215 enum tree_code compare;
5216 struct cost_pair *cp = get_use_iv_cost (data, use, cand);
5222 tree var = var_at_stmt (data->current_loop, cand, use->stmt);
5223 tree var_type = TREE_TYPE (var);
5225 compare = iv_elimination_compare (data, use);
5226 bound = unshare_expr (fold_convert (var_type, bound));
5227 op = force_gimple_operand_bsi (&bsi, bound, true, NULL_TREE,
5228 true, BSI_SAME_STMT);
5230 *use->op_p = build2 (compare, boolean_type_node, var, op);
5234 /* The induction variable elimination failed; just express the original
5236 comp = get_computation (data->current_loop, use, cand);
5237 gcc_assert (comp != NULL_TREE);
5239 ok = extract_cond_operands (data, use->op_p, &var_p, NULL, NULL, NULL);
5242 *var_p = force_gimple_operand_bsi (&bsi, comp, true, SSA_NAME_VAR (*var_p),
5243 true, BSI_SAME_STMT);
5246 /* Rewrites USE using candidate CAND. */
5249 rewrite_use (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
5251 push_stmt_changes (&use->stmt);
5255 case USE_NONLINEAR_EXPR:
5256 rewrite_use_nonlinear_expr (data, use, cand);
5260 rewrite_use_address (data, use, cand);
5264 rewrite_use_compare (data, use, cand);
5271 pop_stmt_changes (&use->stmt);
5274 /* Rewrite the uses using the selected induction variables. */
5277 rewrite_uses (struct ivopts_data *data)
5280 struct iv_cand *cand;
5283 for (i = 0; i < n_iv_uses (data); i++)
5285 use = iv_use (data, i);
5286 cand = use->selected;
5289 rewrite_use (data, use, cand);
5293 /* Removes the ivs that are not used after rewriting. */
5296 remove_unused_ivs (struct ivopts_data *data)
5301 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
5303 struct version_info *info;
5305 info = ver_info (data, j);
5307 && !integer_zerop (info->iv->step)
5309 && !info->iv->have_use_for
5310 && !info->preserve_biv)
5311 remove_statement (SSA_NAME_DEF_STMT (info->iv->ssa_name), true);
5315 /* Frees data allocated by the optimization of a single loop. */
5318 free_loop_data (struct ivopts_data *data)
5326 pointer_map_destroy (data->niters);
5327 data->niters = NULL;
5330 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
5332 struct version_info *info;
5334 info = ver_info (data, i);
5338 info->has_nonlin_use = false;
5339 info->preserve_biv = false;
5342 bitmap_clear (data->relevant);
5343 bitmap_clear (data->important_candidates);
5345 for (i = 0; i < n_iv_uses (data); i++)
5347 struct iv_use *use = iv_use (data, i);
5350 BITMAP_FREE (use->related_cands);
5351 for (j = 0; j < use->n_map_members; j++)
5352 if (use->cost_map[j].depends_on)
5353 BITMAP_FREE (use->cost_map[j].depends_on);
5354 free (use->cost_map);
5357 VEC_truncate (iv_use_p, data->iv_uses, 0);
5359 for (i = 0; i < n_iv_cands (data); i++)
5361 struct iv_cand *cand = iv_cand (data, i);
5365 if (cand->depends_on)
5366 BITMAP_FREE (cand->depends_on);
5369 VEC_truncate (iv_cand_p, data->iv_candidates, 0);
5371 if (data->version_info_size < num_ssa_names)
5373 data->version_info_size = 2 * num_ssa_names;
5374 free (data->version_info);
5375 data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
5378 data->max_inv_id = 0;
5380 for (i = 0; VEC_iterate (tree, decl_rtl_to_reset, i, obj); i++)
5381 SET_DECL_RTL (obj, NULL_RTX);
5383 VEC_truncate (tree, decl_rtl_to_reset, 0);
5386 /* Finalizes data structures used by the iv optimization pass. LOOPS is the
5390 tree_ssa_iv_optimize_finalize (struct ivopts_data *data)
5392 free_loop_data (data);
5393 free (data->version_info);
5394 BITMAP_FREE (data->relevant);
5395 BITMAP_FREE (data->important_candidates);
5397 VEC_free (tree, heap, decl_rtl_to_reset);
5398 VEC_free (iv_use_p, heap, data->iv_uses);
5399 VEC_free (iv_cand_p, heap, data->iv_candidates);
5402 /* Optimizes the LOOP. Returns true if anything changed. */
5405 tree_ssa_iv_optimize_loop (struct ivopts_data *data, struct loop *loop)
5407 bool changed = false;
5408 struct iv_ca *iv_ca;
5411 gcc_assert (!data->niters);
5412 data->current_loop = loop;
5414 if (dump_file && (dump_flags & TDF_DETAILS))
5416 fprintf (dump_file, "Processing loop %d\n", loop->num);
5418 exit = single_dom_exit (loop);
5421 fprintf (dump_file, " single exit %d -> %d, exit condition ",
5422 exit->src->index, exit->dest->index);
5423 print_generic_expr (dump_file, last_stmt (exit->src), TDF_SLIM);
5424 fprintf (dump_file, "\n");
5427 fprintf (dump_file, "\n");
5430 /* For each ssa name determines whether it behaves as an induction variable
5432 if (!find_induction_variables (data))
5435 /* Finds interesting uses (item 1). */
5436 find_interesting_uses (data);
5437 if (n_iv_uses (data) > MAX_CONSIDERED_USES)
5440 /* Finds candidates for the induction variables (item 2). */
5441 find_iv_candidates (data);
5443 /* Calculates the costs (item 3, part 1). */
5444 determine_use_iv_costs (data);
5445 determine_iv_costs (data);
5446 determine_set_costs (data);
5448 /* Find the optimal set of induction variables (item 3, part 2). */
5449 iv_ca = find_optimal_iv_set (data);
5454 /* Create the new induction variables (item 4, part 1). */
5455 create_new_ivs (data, iv_ca);
5456 iv_ca_free (&iv_ca);
5458 /* Rewrite the uses (item 4, part 2). */
5459 rewrite_uses (data);
5461 /* Remove the ivs that are unused after rewriting. */
5462 remove_unused_ivs (data);
5464 /* We have changed the structure of induction variables; it might happen
5465 that definitions in the scev database refer to some of them that were
5470 free_loop_data (data);
5475 /* Main entry point. Optimizes induction variables in loops. */
5478 tree_ssa_iv_optimize (void)
5481 struct ivopts_data data;
5484 tree_ssa_iv_optimize_init (&data);
5486 /* Optimize the loops starting with the innermost ones. */
5487 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
5489 if (dump_file && (dump_flags & TDF_DETAILS))
5490 flow_loop_dump (loop, dump_file, NULL, 1);
5492 tree_ssa_iv_optimize_loop (&data, loop);
5495 tree_ssa_iv_optimize_finalize (&data);