1 /* Induction variable optimizations.
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
21 /* This pass tries to find the optimal set of induction variables for the loop.
22 It optimizes just the basic linear induction variables (although adding
23 support for other types should not be too hard). It includes the
24 optimizations commonly known as strength reduction, induction variable
25 coalescing and induction variable elimination. It does it in the
28 1) The interesting uses of induction variables are found. This includes
30 -- uses of induction variables in non-linear expressions
31 -- addresses of arrays
32 -- comparisons of induction variables
34 2) Candidates for the induction variables are found. This includes
36 -- old induction variables
37 -- the variables defined by expressions derived from the "interesting
40 3) The optimal (w.r. to a cost function) set of variables is chosen. The
41 cost function assigns a cost to sets of induction variables and consists
44 -- The use costs. Each of the interesting uses chooses the best induction
45 variable in the set and adds its cost to the sum. The cost reflects
46 the time spent on modifying the induction variables value to be usable
47 for the given purpose (adding base and offset for arrays, etc.).
48 -- The variable costs. Each of the variables has a cost assigned that
49 reflects the costs associated with incrementing the value of the
50 variable. The original variables are somewhat preferred.
51 -- The set cost. Depending on the size of the set, extra cost may be
52 added to reflect register pressure.
54 All the costs are defined in a machine-specific way, using the target
55 hooks and machine descriptions to determine them.
57 4) The trees are transformed to use the new variables, the dead code is
60 All of this is done loop by loop. Doing it globally is theoretically
61 possible, it might give a better performance and it might enable us
62 to decide costs more precisely, but getting all the interactions right
63 would be complicated. */
67 #include "coretypes.h"
72 #include "hard-reg-set.h"
73 #include "basic-block.h"
75 #include "diagnostic.h"
76 #include "tree-flow.h"
77 #include "tree-dump.h"
82 #include "tree-pass.h"
84 #include "insn-config.h"
87 #include "tree-chrec.h"
88 #include "tree-scalar-evolution.h"
91 #include "langhooks.h"
92 #include "tree-affine.h"
94 /* The infinite cost. */
95 #define INFTY 10000000
97 /* The expected number of loop iterations. TODO -- use profiling instead of
99 #define AVG_LOOP_NITER(LOOP) 5
102 /* Representation of the induction variable. */
105 tree base; /* Initial value of the iv. */
106 tree base_object; /* A memory object to that the induction variable points. */
107 tree step; /* Step of the iv (constant only). */
108 tree ssa_name; /* The ssa name with the value. */
109 bool biv_p; /* Is it a biv? */
110 bool have_use_for; /* Do we already have a use for it? */
111 unsigned use_id; /* The identifier in the use if it is the case. */
114 /* Per-ssa version information (induction variable descriptions, etc.). */
117 tree name; /* The ssa name. */
118 struct iv *iv; /* Induction variable description. */
119 bool has_nonlin_use; /* For a loop-level invariant, whether it is used in
120 an expression that is not an induction variable. */
121 unsigned inv_id; /* Id of an invariant. */
122 bool preserve_biv; /* For the original biv, whether to preserve it. */
128 USE_NONLINEAR_EXPR, /* Use in a nonlinear expression. */
129 USE_ADDRESS, /* Use in an address. */
130 USE_COMPARE /* Use is a compare. */
133 /* The candidate - cost pair. */
136 struct iv_cand *cand; /* The candidate. */
137 unsigned cost; /* The cost. */
138 bitmap depends_on; /* The list of invariants that have to be
140 tree value; /* For final value elimination, the expression for
141 the final value of the iv. For iv elimination,
142 the new bound to compare with. */
148 unsigned id; /* The id of the use. */
149 enum use_type type; /* Type of the use. */
150 struct iv *iv; /* The induction variable it is based on. */
151 tree stmt; /* Statement in that it occurs. */
152 tree *op_p; /* The place where it occurs. */
153 bitmap related_cands; /* The set of "related" iv candidates, plus the common
156 unsigned n_map_members; /* Number of candidates in the cost_map list. */
157 struct cost_pair *cost_map;
158 /* The costs wrto the iv candidates. */
160 struct iv_cand *selected;
161 /* The selected candidate. */
164 /* The position where the iv is computed. */
167 IP_NORMAL, /* At the end, just before the exit condition. */
168 IP_END, /* At the end of the latch block. */
169 IP_ORIGINAL /* The original biv. */
172 /* The induction variable candidate. */
175 unsigned id; /* The number of the candidate. */
176 bool important; /* Whether this is an "important" candidate, i.e. such
177 that it should be considered by all uses. */
178 enum iv_position pos; /* Where it is computed. */
179 tree incremented_at; /* For original biv, the statement where it is
181 tree var_before; /* The variable used for it before increment. */
182 tree var_after; /* The variable used for it after increment. */
183 struct iv *iv; /* The value of the candidate. NULL for
184 "pseudocandidate" used to indicate the possibility
185 to replace the final value of an iv by direct
186 computation of the value. */
187 unsigned cost; /* Cost of the candidate. */
188 bitmap depends_on; /* The list of invariants that are used in step of the
192 /* The data used by the induction variable optimizations. */
194 typedef struct iv_use *iv_use_p;
196 DEF_VEC_ALLOC_P(iv_use_p,heap);
198 typedef struct iv_cand *iv_cand_p;
199 DEF_VEC_P(iv_cand_p);
200 DEF_VEC_ALLOC_P(iv_cand_p,heap);
204 /* The currently optimized loop. */
205 struct loop *current_loop;
207 /* Number of registers used in it. */
210 /* Numbers of iterations for all exits of the current loop. */
213 /* The size of version_info array allocated. */
214 unsigned version_info_size;
216 /* The array of information for the ssa names. */
217 struct version_info *version_info;
219 /* The bitmap of indices in version_info whose value was changed. */
222 /* The maximum invariant id. */
225 /* The uses of induction variables. */
226 VEC(iv_use_p,heap) *iv_uses;
228 /* The candidates. */
229 VEC(iv_cand_p,heap) *iv_candidates;
231 /* A bitmap of important candidates. */
232 bitmap important_candidates;
234 /* Whether to consider just related and important candidates when replacing a
236 bool consider_all_candidates;
239 /* An assignment of iv candidates to uses. */
243 /* The number of uses covered by the assignment. */
246 /* Number of uses that cannot be expressed by the candidates in the set. */
249 /* Candidate assigned to a use, together with the related costs. */
250 struct cost_pair **cand_for_use;
252 /* Number of times each candidate is used. */
253 unsigned *n_cand_uses;
255 /* The candidates used. */
258 /* The number of candidates in the set. */
261 /* Total number of registers needed. */
264 /* Total cost of expressing uses. */
265 unsigned cand_use_cost;
267 /* Total cost of candidates. */
270 /* Number of times each invariant is used. */
271 unsigned *n_invariant_uses;
273 /* Total cost of the assignment. */
277 /* Difference of two iv candidate assignments. */
284 /* An old assignment (for rollback purposes). */
285 struct cost_pair *old_cp;
287 /* A new assignment. */
288 struct cost_pair *new_cp;
290 /* Next change in the list. */
291 struct iv_ca_delta *next_change;
294 /* Bound on number of candidates below that all candidates are considered. */
296 #define CONSIDER_ALL_CANDIDATES_BOUND \
297 ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
299 /* If there are more iv occurrences, we just give up (it is quite unlikely that
300 optimizing such a loop would help, and it would take ages). */
302 #define MAX_CONSIDERED_USES \
303 ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
305 /* If there are at most this number of ivs in the set, try removing unnecessary
306 ivs from the set always. */
308 #define ALWAYS_PRUNE_CAND_SET_BOUND \
309 ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
311 /* The list of trees for that the decl_rtl field must be reset is stored
314 static VEC(tree,heap) *decl_rtl_to_reset;
316 /* Number of uses recorded in DATA. */
318 static inline unsigned
319 n_iv_uses (struct ivopts_data *data)
321 return VEC_length (iv_use_p, data->iv_uses);
324 /* Ith use recorded in DATA. */
326 static inline struct iv_use *
327 iv_use (struct ivopts_data *data, unsigned i)
329 return VEC_index (iv_use_p, data->iv_uses, i);
332 /* Number of candidates recorded in DATA. */
334 static inline unsigned
335 n_iv_cands (struct ivopts_data *data)
337 return VEC_length (iv_cand_p, data->iv_candidates);
340 /* Ith candidate recorded in DATA. */
342 static inline struct iv_cand *
343 iv_cand (struct ivopts_data *data, unsigned i)
345 return VEC_index (iv_cand_p, data->iv_candidates, i);
348 /* The single loop exit if it dominates the latch, NULL otherwise. */
351 single_dom_exit (struct loop *loop)
353 edge exit = single_exit (loop);
358 if (!just_once_each_iteration_p (loop, exit->src))
364 /* Dumps information about the induction variable IV to FILE. */
366 extern void dump_iv (FILE *, struct iv *);
368 dump_iv (FILE *file, struct iv *iv)
372 fprintf (file, "ssa name ");
373 print_generic_expr (file, iv->ssa_name, TDF_SLIM);
374 fprintf (file, "\n");
377 fprintf (file, " type ");
378 print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
379 fprintf (file, "\n");
383 fprintf (file, " base ");
384 print_generic_expr (file, iv->base, TDF_SLIM);
385 fprintf (file, "\n");
387 fprintf (file, " step ");
388 print_generic_expr (file, iv->step, TDF_SLIM);
389 fprintf (file, "\n");
393 fprintf (file, " invariant ");
394 print_generic_expr (file, iv->base, TDF_SLIM);
395 fprintf (file, "\n");
400 fprintf (file, " base object ");
401 print_generic_expr (file, iv->base_object, TDF_SLIM);
402 fprintf (file, "\n");
406 fprintf (file, " is a biv\n");
409 /* Dumps information about the USE to FILE. */
411 extern void dump_use (FILE *, struct iv_use *);
413 dump_use (FILE *file, struct iv_use *use)
415 fprintf (file, "use %d\n", use->id);
419 case USE_NONLINEAR_EXPR:
420 fprintf (file, " generic\n");
424 fprintf (file, " address\n");
428 fprintf (file, " compare\n");
435 fprintf (file, " in statement ");
436 print_generic_expr (file, use->stmt, TDF_SLIM);
437 fprintf (file, "\n");
439 fprintf (file, " at position ");
441 print_generic_expr (file, *use->op_p, TDF_SLIM);
442 fprintf (file, "\n");
444 dump_iv (file, use->iv);
446 if (use->related_cands)
448 fprintf (file, " related candidates ");
449 dump_bitmap (file, use->related_cands);
453 /* Dumps information about the uses to FILE. */
455 extern void dump_uses (FILE *, struct ivopts_data *);
457 dump_uses (FILE *file, struct ivopts_data *data)
462 for (i = 0; i < n_iv_uses (data); i++)
464 use = iv_use (data, i);
466 dump_use (file, use);
467 fprintf (file, "\n");
471 /* Dumps information about induction variable candidate CAND to FILE. */
473 extern void dump_cand (FILE *, struct iv_cand *);
475 dump_cand (FILE *file, struct iv_cand *cand)
477 struct iv *iv = cand->iv;
479 fprintf (file, "candidate %d%s\n",
480 cand->id, cand->important ? " (important)" : "");
482 if (cand->depends_on)
484 fprintf (file, " depends on ");
485 dump_bitmap (file, cand->depends_on);
490 fprintf (file, " final value replacement\n");
497 fprintf (file, " incremented before exit test\n");
501 fprintf (file, " incremented at end\n");
505 fprintf (file, " original biv\n");
512 /* Returns the info for ssa version VER. */
514 static inline struct version_info *
515 ver_info (struct ivopts_data *data, unsigned ver)
517 return data->version_info + ver;
520 /* Returns the info for ssa name NAME. */
522 static inline struct version_info *
523 name_info (struct ivopts_data *data, tree name)
525 return ver_info (data, SSA_NAME_VERSION (name));
528 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
532 stmt_after_ip_normal_pos (struct loop *loop, tree stmt)
534 basic_block bb = ip_normal_pos (loop), sbb = bb_for_stmt (stmt);
538 if (sbb == loop->latch)
544 return stmt == last_stmt (bb);
547 /* Returns true if STMT if after the place where the original induction
548 variable CAND is incremented. */
551 stmt_after_ip_original_pos (struct iv_cand *cand, tree stmt)
553 basic_block cand_bb = bb_for_stmt (cand->incremented_at);
554 basic_block stmt_bb = bb_for_stmt (stmt);
555 block_stmt_iterator bsi;
557 if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
560 if (stmt_bb != cand_bb)
563 /* Scan the block from the end, since the original ivs are usually
564 incremented at the end of the loop body. */
565 for (bsi = bsi_last (stmt_bb); ; bsi_prev (&bsi))
567 if (bsi_stmt (bsi) == cand->incremented_at)
569 if (bsi_stmt (bsi) == stmt)
574 /* Returns true if STMT if after the place where the induction variable
575 CAND is incremented in LOOP. */
578 stmt_after_increment (struct loop *loop, struct iv_cand *cand, tree stmt)
586 return stmt_after_ip_normal_pos (loop, stmt);
589 return stmt_after_ip_original_pos (cand, stmt);
596 /* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
599 abnormal_ssa_name_p (tree exp)
604 if (TREE_CODE (exp) != SSA_NAME)
607 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) != 0;
610 /* Returns false if BASE or INDEX contains a ssa name that occurs in an
611 abnormal phi node. Callback for for_each_index. */
614 idx_contains_abnormal_ssa_name_p (tree base, tree *index,
615 void *data ATTRIBUTE_UNUSED)
617 if (TREE_CODE (base) == ARRAY_REF)
619 if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
621 if (abnormal_ssa_name_p (TREE_OPERAND (base, 3)))
625 return !abnormal_ssa_name_p (*index);
628 /* Returns true if EXPR contains a ssa name that occurs in an
629 abnormal phi node. */
632 contains_abnormal_ssa_name_p (tree expr)
635 enum tree_code_class class;
640 code = TREE_CODE (expr);
641 class = TREE_CODE_CLASS (code);
643 if (code == SSA_NAME)
644 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
646 if (code == INTEGER_CST
647 || is_gimple_min_invariant (expr))
650 if (code == ADDR_EXPR)
651 return !for_each_index (&TREE_OPERAND (expr, 0),
652 idx_contains_abnormal_ssa_name_p,
659 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1)))
664 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0)))
676 /* Element of the table in that we cache the numbers of iterations obtained
677 from exits of the loop. */
681 /* The edge for that the number of iterations is cached. */
684 /* Number of iterations corresponding to this exit, or NULL if it cannot be
689 /* Hash function for nfe_cache_elt E. */
692 nfe_hash (const void *e)
694 const struct nfe_cache_elt *elt = e;
696 return htab_hash_pointer (elt->exit);
699 /* Equality function for nfe_cache_elt E1 and edge E2. */
702 nfe_eq (const void *e1, const void *e2)
704 const struct nfe_cache_elt *elt1 = e1;
706 return elt1->exit == e2;
709 /* Returns tree describing number of iterations determined from
710 EXIT of DATA->current_loop, or NULL if something goes wrong. */
713 niter_for_exit (struct ivopts_data *data, edge exit)
715 struct nfe_cache_elt *nfe_desc;
716 struct tree_niter_desc desc;
719 slot = htab_find_slot_with_hash (data->niters, exit,
720 htab_hash_pointer (exit),
725 nfe_desc = xmalloc (sizeof (struct nfe_cache_elt));
726 nfe_desc->exit = exit;
728 /* Try to determine number of iterations. We must know it
729 unconditionally (i.e., without possibility of # of iterations
730 being zero). Also, we cannot safely work with ssa names that
731 appear in phi nodes on abnormal edges, so that we do not create
732 overlapping life ranges for them (PR 27283). */
733 if (number_of_iterations_exit (data->current_loop,
735 && integer_zerop (desc.may_be_zero)
736 && !contains_abnormal_ssa_name_p (desc.niter))
737 nfe_desc->niter = desc.niter;
739 nfe_desc->niter = NULL_TREE;
744 return nfe_desc->niter;
747 /* Returns tree describing number of iterations determined from
748 single dominating exit of DATA->current_loop, or NULL if something
752 niter_for_single_dom_exit (struct ivopts_data *data)
754 edge exit = single_dom_exit (data->current_loop);
759 return niter_for_exit (data, exit);
762 /* Initializes data structures used by the iv optimization pass, stored
766 tree_ssa_iv_optimize_init (struct ivopts_data *data)
768 data->version_info_size = 2 * num_ssa_names;
769 data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
770 data->relevant = BITMAP_ALLOC (NULL);
771 data->important_candidates = BITMAP_ALLOC (NULL);
772 data->max_inv_id = 0;
773 data->niters = htab_create (10, nfe_hash, nfe_eq, free);
774 data->iv_uses = VEC_alloc (iv_use_p, heap, 20);
775 data->iv_candidates = VEC_alloc (iv_cand_p, heap, 20);
776 decl_rtl_to_reset = VEC_alloc (tree, heap, 20);
779 /* Returns a memory object to that EXPR points. In case we are able to
780 determine that it does not point to any such object, NULL is returned. */
783 determine_base_object (tree expr)
785 enum tree_code code = TREE_CODE (expr);
786 tree base, obj, op0, op1;
788 /* If this is a pointer casted to any type, we need to determine
789 the base object for the pointer; so handle conversions before
790 throwing away non-pointer expressions. */
791 if (TREE_CODE (expr) == NOP_EXPR
792 || TREE_CODE (expr) == CONVERT_EXPR)
793 return determine_base_object (TREE_OPERAND (expr, 0));
795 if (!POINTER_TYPE_P (TREE_TYPE (expr)))
804 obj = TREE_OPERAND (expr, 0);
805 base = get_base_address (obj);
810 if (TREE_CODE (base) == INDIRECT_REF)
811 return determine_base_object (TREE_OPERAND (base, 0));
813 return fold_convert (ptr_type_node,
814 build_fold_addr_expr (base));
818 op0 = determine_base_object (TREE_OPERAND (expr, 0));
819 op1 = determine_base_object (TREE_OPERAND (expr, 1));
825 return (code == PLUS_EXPR
827 : fold_build1 (NEGATE_EXPR, ptr_type_node, op1));
829 return fold_build2 (code, ptr_type_node, op0, op1);
832 return fold_convert (ptr_type_node, expr);
836 /* Allocates an induction variable with given initial value BASE and step STEP
840 alloc_iv (tree base, tree step)
842 struct iv *iv = XCNEW (struct iv);
844 if (step && integer_zerop (step))
848 iv->base_object = determine_base_object (base);
851 iv->have_use_for = false;
853 iv->ssa_name = NULL_TREE;
858 /* Sets STEP and BASE for induction variable IV. */
861 set_iv (struct ivopts_data *data, tree iv, tree base, tree step)
863 struct version_info *info = name_info (data, iv);
865 gcc_assert (!info->iv);
867 bitmap_set_bit (data->relevant, SSA_NAME_VERSION (iv));
868 info->iv = alloc_iv (base, step);
869 info->iv->ssa_name = iv;
872 /* Finds induction variable declaration for VAR. */
875 get_iv (struct ivopts_data *data, tree var)
879 if (!name_info (data, var)->iv)
881 bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
884 || !flow_bb_inside_loop_p (data->current_loop, bb))
885 set_iv (data, var, var, NULL_TREE);
888 return name_info (data, var)->iv;
891 /* Determines the step of a biv defined in PHI. Returns NULL if PHI does
892 not define a simple affine biv with nonzero step. */
895 determine_biv_step (tree phi)
897 struct loop *loop = bb_for_stmt (phi)->loop_father;
898 tree name = PHI_RESULT (phi);
901 if (!is_gimple_reg (name))
904 if (!simple_iv (loop, phi, name, &iv, true))
907 return (null_or_integer_zerop (iv.step) ? NULL_TREE : iv.step);
910 /* Finds basic ivs. */
913 find_bivs (struct ivopts_data *data)
915 tree phi, step, type, base;
917 struct loop *loop = data->current_loop;
919 for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
921 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
924 step = determine_biv_step (phi);
928 base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
929 base = expand_simple_operations (base);
930 if (contains_abnormal_ssa_name_p (base)
931 || contains_abnormal_ssa_name_p (step))
934 type = TREE_TYPE (PHI_RESULT (phi));
935 base = fold_convert (type, base);
937 step = fold_convert (type, step);
939 set_iv (data, PHI_RESULT (phi), base, step);
946 /* Marks basic ivs. */
949 mark_bivs (struct ivopts_data *data)
952 struct iv *iv, *incr_iv;
953 struct loop *loop = data->current_loop;
956 for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
958 iv = get_iv (data, PHI_RESULT (phi));
962 var = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
963 incr_iv = get_iv (data, var);
967 /* If the increment is in the subloop, ignore it. */
968 incr_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
969 if (incr_bb->loop_father != data->current_loop
970 || (incr_bb->flags & BB_IRREDUCIBLE_LOOP))
974 incr_iv->biv_p = true;
978 /* Checks whether STMT defines a linear induction variable and stores its
982 find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt, affine_iv *iv)
985 struct loop *loop = data->current_loop;
987 iv->base = NULL_TREE;
988 iv->step = NULL_TREE;
990 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
993 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
994 if (TREE_CODE (lhs) != SSA_NAME)
997 if (!simple_iv (loop, stmt, GIMPLE_STMT_OPERAND (stmt, 1), iv, true))
999 iv->base = expand_simple_operations (iv->base);
1001 if (contains_abnormal_ssa_name_p (iv->base)
1002 || contains_abnormal_ssa_name_p (iv->step))
1008 /* Finds general ivs in statement STMT. */
1011 find_givs_in_stmt (struct ivopts_data *data, tree stmt)
1015 if (!find_givs_in_stmt_scev (data, stmt, &iv))
1018 set_iv (data, GIMPLE_STMT_OPERAND (stmt, 0), iv.base, iv.step);
1021 /* Finds general ivs in basic block BB. */
1024 find_givs_in_bb (struct ivopts_data *data, basic_block bb)
1026 block_stmt_iterator bsi;
1028 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1029 find_givs_in_stmt (data, bsi_stmt (bsi));
1032 /* Finds general ivs. */
1035 find_givs (struct ivopts_data *data)
1037 struct loop *loop = data->current_loop;
1038 basic_block *body = get_loop_body_in_dom_order (loop);
1041 for (i = 0; i < loop->num_nodes; i++)
1042 find_givs_in_bb (data, body[i]);
1046 /* For each ssa name defined in LOOP determines whether it is an induction
1047 variable and if so, its initial value and step. */
1050 find_induction_variables (struct ivopts_data *data)
1055 if (!find_bivs (data))
1061 if (dump_file && (dump_flags & TDF_DETAILS))
1063 tree niter = niter_for_single_dom_exit (data);
1067 fprintf (dump_file, " number of iterations ");
1068 print_generic_expr (dump_file, niter, TDF_SLIM);
1069 fprintf (dump_file, "\n\n");
1072 fprintf (dump_file, "Induction variables:\n\n");
1074 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
1076 if (ver_info (data, i)->iv)
1077 dump_iv (dump_file, ver_info (data, i)->iv);
1084 /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV. */
1086 static struct iv_use *
1087 record_use (struct ivopts_data *data, tree *use_p, struct iv *iv,
1088 tree stmt, enum use_type use_type)
1090 struct iv_use *use = XCNEW (struct iv_use);
1092 use->id = n_iv_uses (data);
1093 use->type = use_type;
1097 use->related_cands = BITMAP_ALLOC (NULL);
1099 /* To avoid showing ssa name in the dumps, if it was not reset by the
1101 iv->ssa_name = NULL_TREE;
1103 if (dump_file && (dump_flags & TDF_DETAILS))
1104 dump_use (dump_file, use);
1106 VEC_safe_push (iv_use_p, heap, data->iv_uses, use);
1111 /* Checks whether OP is a loop-level invariant and if so, records it.
1112 NONLINEAR_USE is true if the invariant is used in a way we do not
1113 handle specially. */
1116 record_invariant (struct ivopts_data *data, tree op, bool nonlinear_use)
1119 struct version_info *info;
1121 if (TREE_CODE (op) != SSA_NAME
1122 || !is_gimple_reg (op))
1125 bb = bb_for_stmt (SSA_NAME_DEF_STMT (op));
1127 && flow_bb_inside_loop_p (data->current_loop, bb))
1130 info = name_info (data, op);
1132 info->has_nonlin_use |= nonlinear_use;
1134 info->inv_id = ++data->max_inv_id;
1135 bitmap_set_bit (data->relevant, SSA_NAME_VERSION (op));
1138 /* Checks whether the use OP is interesting and if so, records it. */
1140 static struct iv_use *
1141 find_interesting_uses_op (struct ivopts_data *data, tree op)
1148 if (TREE_CODE (op) != SSA_NAME)
1151 iv = get_iv (data, op);
1155 if (iv->have_use_for)
1157 use = iv_use (data, iv->use_id);
1159 gcc_assert (use->type == USE_NONLINEAR_EXPR);
1163 if (null_or_integer_zerop (iv->step))
1165 record_invariant (data, op, true);
1168 iv->have_use_for = true;
1170 civ = XNEW (struct iv);
1173 stmt = SSA_NAME_DEF_STMT (op);
1174 gcc_assert (TREE_CODE (stmt) == PHI_NODE
1175 || TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
1177 use = record_use (data, NULL, civ, stmt, USE_NONLINEAR_EXPR);
1178 iv->use_id = use->id;
1183 /* Checks whether the condition *COND_P in STMT is interesting
1184 and if so, records it. */
1187 find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
1191 struct iv *iv0 = NULL, *iv1 = NULL, *civ;
1193 tree zero = integer_zero_node;
1195 const_iv.step = NULL_TREE;
1197 if (TREE_CODE (*cond_p) != SSA_NAME
1198 && !COMPARISON_CLASS_P (*cond_p))
1201 if (TREE_CODE (*cond_p) == SSA_NAME)
1208 op0_p = &TREE_OPERAND (*cond_p, 0);
1209 op1_p = &TREE_OPERAND (*cond_p, 1);
1212 if (TREE_CODE (*op0_p) == SSA_NAME)
1213 iv0 = get_iv (data, *op0_p);
1217 if (TREE_CODE (*op1_p) == SSA_NAME)
1218 iv1 = get_iv (data, *op1_p);
1222 if (/* When comparing with non-invariant value, we may not do any senseful
1223 induction variable elimination. */
1225 /* Eliminating condition based on two ivs would be nontrivial.
1226 ??? TODO -- it is not really important to handle this case. */
1227 || (!null_or_integer_zerop (iv0->step)
1228 && !null_or_integer_zerop (iv1->step)))
1230 find_interesting_uses_op (data, *op0_p);
1231 find_interesting_uses_op (data, *op1_p);
1235 if (null_or_integer_zerop (iv0->step)
1236 && null_or_integer_zerop (iv1->step))
1238 /* If both are invariants, this is a work for unswitching. */
1242 civ = XNEW (struct iv);
1243 *civ = null_or_integer_zerop (iv0->step) ? *iv1: *iv0;
1244 record_use (data, cond_p, civ, stmt, USE_COMPARE);
1247 /* Returns true if expression EXPR is obviously invariant in LOOP,
1248 i.e. if all its operands are defined outside of the LOOP. */
1251 expr_invariant_in_loop_p (struct loop *loop, tree expr)
1256 if (is_gimple_min_invariant (expr))
1259 if (TREE_CODE (expr) == SSA_NAME)
1261 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (expr));
1263 && flow_bb_inside_loop_p (loop, def_bb))
1269 if (!EXPR_P (expr) && !GIMPLE_STMT_P (expr))
1272 len = TREE_CODE_LENGTH (TREE_CODE (expr));
1273 for (i = 0; i < len; i++)
1274 if (!expr_invariant_in_loop_p (loop, TREE_OPERAND (expr, i)))
1280 /* Cumulates the steps of indices into DATA and replaces their values with the
1281 initial ones. Returns false when the value of the index cannot be determined.
1282 Callback for for_each_index. */
1284 struct ifs_ivopts_data
1286 struct ivopts_data *ivopts_data;
1292 idx_find_step (tree base, tree *idx, void *data)
1294 struct ifs_ivopts_data *dta = data;
1296 tree step, iv_base, iv_step, lbound, off;
1297 struct loop *loop = dta->ivopts_data->current_loop;
1299 if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF
1300 || TREE_CODE (base) == ALIGN_INDIRECT_REF)
1303 /* If base is a component ref, require that the offset of the reference
1305 if (TREE_CODE (base) == COMPONENT_REF)
1307 off = component_ref_field_offset (base);
1308 return expr_invariant_in_loop_p (loop, off);
1311 /* If base is array, first check whether we will be able to move the
1312 reference out of the loop (in order to take its address in strength
1313 reduction). In order for this to work we need both lower bound
1314 and step to be loop invariants. */
1315 if (TREE_CODE (base) == ARRAY_REF)
1317 step = array_ref_element_size (base);
1318 lbound = array_ref_low_bound (base);
1320 if (!expr_invariant_in_loop_p (loop, step)
1321 || !expr_invariant_in_loop_p (loop, lbound))
1325 if (TREE_CODE (*idx) != SSA_NAME)
1328 iv = get_iv (dta->ivopts_data, *idx);
1332 /* XXX We produce for a base of *D42 with iv->base being &x[0]
1333 *&x[0], which is not folded and does not trigger the
1334 ARRAY_REF path below. */
1340 if (TREE_CODE (base) == ARRAY_REF)
1342 step = array_ref_element_size (base);
1344 /* We only handle addresses whose step is an integer constant. */
1345 if (TREE_CODE (step) != INTEGER_CST)
1349 /* The step for pointer arithmetics already is 1 byte. */
1350 step = build_int_cst (sizetype, 1);
1354 if (!convert_affine_scev (dta->ivopts_data->current_loop,
1355 sizetype, &iv_base, &iv_step, dta->stmt,
1358 /* The index might wrap. */
1362 step = fold_build2 (MULT_EXPR, sizetype, step, iv_step);
1365 *dta->step_p = step;
1367 *dta->step_p = fold_build2 (PLUS_EXPR, sizetype, *dta->step_p, step);
1372 /* Records use in index IDX. Callback for for_each_index. Ivopts data
1373 object is passed to it in DATA. */
1376 idx_record_use (tree base, tree *idx,
1379 find_interesting_uses_op (data, *idx);
1380 if (TREE_CODE (base) == ARRAY_REF)
1382 find_interesting_uses_op (data, array_ref_element_size (base));
1383 find_interesting_uses_op (data, array_ref_low_bound (base));
1388 /* Returns true if memory reference REF may be unaligned. */
1391 may_be_unaligned_p (tree ref)
1395 HOST_WIDE_INT bitsize;
1396 HOST_WIDE_INT bitpos;
1398 enum machine_mode mode;
1399 int unsignedp, volatilep;
1400 unsigned base_align;
1402 /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
1403 thus they are not misaligned. */
1404 if (TREE_CODE (ref) == TARGET_MEM_REF)
1407 /* The test below is basically copy of what expr.c:normal_inner_ref
1408 does to check whether the object must be loaded by parts when
1409 STRICT_ALIGNMENT is true. */
1410 base = get_inner_reference (ref, &bitsize, &bitpos, &toffset, &mode,
1411 &unsignedp, &volatilep, true);
1412 base_type = TREE_TYPE (base);
1413 base_align = TYPE_ALIGN (base_type);
1416 && (base_align < GET_MODE_ALIGNMENT (mode)
1417 || bitpos % GET_MODE_ALIGNMENT (mode) != 0
1418 || bitpos % BITS_PER_UNIT != 0))
1424 /* Return true if EXPR may be non-addressable. */
1427 may_be_nonaddressable_p (tree expr)
1429 switch (TREE_CODE (expr))
1432 return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr, 1))
1433 || may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
1436 case ARRAY_RANGE_REF:
1437 return may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
1439 case VIEW_CONVERT_EXPR:
1440 /* This kind of view-conversions may wrap non-addressable objects
1441 and make them look addressable. After some processing the
1442 non-addressability may be uncovered again, causing ADDR_EXPRs
1443 of inappropriate objects to be built. */
1444 return AGGREGATE_TYPE_P (TREE_TYPE (expr))
1445 && !AGGREGATE_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)));
1454 /* Finds addresses in *OP_P inside STMT. */
1457 find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
1459 tree base = *op_p, step = NULL;
1461 struct ifs_ivopts_data ifs_ivopts_data;
1463 /* Do not play with volatile memory references. A bit too conservative,
1464 perhaps, but safe. */
1465 if (stmt_ann (stmt)->has_volatile_ops)
1468 /* Ignore bitfields for now. Not really something terribly complicated
1470 if (TREE_CODE (base) == BIT_FIELD_REF)
1473 if (may_be_nonaddressable_p (base))
1476 if (STRICT_ALIGNMENT
1477 && may_be_unaligned_p (base))
1480 base = unshare_expr (base);
1482 if (TREE_CODE (base) == TARGET_MEM_REF)
1484 tree type = build_pointer_type (TREE_TYPE (base));
1488 && TREE_CODE (TMR_BASE (base)) == SSA_NAME)
1490 civ = get_iv (data, TMR_BASE (base));
1494 TMR_BASE (base) = civ->base;
1497 if (TMR_INDEX (base)
1498 && TREE_CODE (TMR_INDEX (base)) == SSA_NAME)
1500 civ = get_iv (data, TMR_INDEX (base));
1504 TMR_INDEX (base) = civ->base;
1509 if (TMR_STEP (base))
1510 astep = fold_build2 (MULT_EXPR, type, TMR_STEP (base), astep);
1513 step = fold_build2 (PLUS_EXPR, type, step, astep);
1519 if (null_or_integer_zerop (step))
1521 base = tree_mem_ref_addr (type, base);
1525 ifs_ivopts_data.ivopts_data = data;
1526 ifs_ivopts_data.stmt = stmt;
1527 ifs_ivopts_data.step_p = &step;
1528 if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
1529 || null_or_integer_zerop (step))
1532 gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
1533 gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
1535 base = build_fold_addr_expr (base);
1537 /* Substituting bases of IVs into the base expression might
1538 have caused folding opportunities. */
1539 if (TREE_CODE (base) == ADDR_EXPR)
1541 tree *ref = &TREE_OPERAND (base, 0);
1542 while (handled_component_p (*ref))
1543 ref = &TREE_OPERAND (*ref, 0);
1544 if (TREE_CODE (*ref) == INDIRECT_REF)
1545 *ref = fold_indirect_ref (*ref);
1549 civ = alloc_iv (base, step);
1550 record_use (data, op_p, civ, stmt, USE_ADDRESS);
1554 for_each_index (op_p, idx_record_use, data);
1557 /* Finds and records invariants used in STMT. */
1560 find_invariants_stmt (struct ivopts_data *data, tree stmt)
1563 use_operand_p use_p;
1566 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1568 op = USE_FROM_PTR (use_p);
1569 record_invariant (data, op, false);
1573 /* Finds interesting uses of induction variables in the statement STMT. */
1576 find_interesting_uses_stmt (struct ivopts_data *data, tree stmt)
1581 use_operand_p use_p;
1583 find_invariants_stmt (data, stmt);
1585 if (TREE_CODE (stmt) == COND_EXPR)
1587 find_interesting_uses_cond (data, stmt, &COND_EXPR_COND (stmt));
1591 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1593 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1594 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1596 if (TREE_CODE (lhs) == SSA_NAME)
1598 /* If the statement defines an induction variable, the uses are not
1599 interesting by themselves. */
1601 iv = get_iv (data, lhs);
1603 if (iv && !null_or_integer_zerop (iv->step))
1607 switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
1609 case tcc_comparison:
1610 find_interesting_uses_cond (data, stmt,
1611 &GIMPLE_STMT_OPERAND (stmt, 1));
1615 find_interesting_uses_address (data, stmt,
1616 &GIMPLE_STMT_OPERAND (stmt, 1));
1617 if (REFERENCE_CLASS_P (lhs))
1618 find_interesting_uses_address (data, stmt,
1619 &GIMPLE_STMT_OPERAND (stmt, 0));
1625 if (REFERENCE_CLASS_P (lhs)
1626 && is_gimple_val (rhs))
1628 find_interesting_uses_address (data, stmt,
1629 &GIMPLE_STMT_OPERAND (stmt, 0));
1630 find_interesting_uses_op (data, rhs);
1634 /* TODO -- we should also handle address uses of type
1636 memory = call (whatever);
1643 if (TREE_CODE (stmt) == PHI_NODE
1644 && bb_for_stmt (stmt) == data->current_loop->header)
1646 lhs = PHI_RESULT (stmt);
1647 iv = get_iv (data, lhs);
1649 if (iv && !null_or_integer_zerop (iv->step))
1653 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1655 op = USE_FROM_PTR (use_p);
1657 if (TREE_CODE (op) != SSA_NAME)
1660 iv = get_iv (data, op);
1664 find_interesting_uses_op (data, op);
1668 /* Finds interesting uses of induction variables outside of loops
1669 on loop exit edge EXIT. */
1672 find_interesting_uses_outside (struct ivopts_data *data, edge exit)
1676 for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
1678 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1679 find_interesting_uses_op (data, def);
1683 /* Finds uses of the induction variables that are interesting. */
1686 find_interesting_uses (struct ivopts_data *data)
1689 block_stmt_iterator bsi;
1691 basic_block *body = get_loop_body (data->current_loop);
1693 struct version_info *info;
1696 if (dump_file && (dump_flags & TDF_DETAILS))
1697 fprintf (dump_file, "Uses:\n\n");
1699 for (i = 0; i < data->current_loop->num_nodes; i++)
1704 FOR_EACH_EDGE (e, ei, bb->succs)
1705 if (e->dest != EXIT_BLOCK_PTR
1706 && !flow_bb_inside_loop_p (data->current_loop, e->dest))
1707 find_interesting_uses_outside (data, e);
1709 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1710 find_interesting_uses_stmt (data, phi);
1711 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1712 find_interesting_uses_stmt (data, bsi_stmt (bsi));
1715 if (dump_file && (dump_flags & TDF_DETAILS))
1719 fprintf (dump_file, "\n");
1721 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
1723 info = ver_info (data, i);
1726 fprintf (dump_file, " ");
1727 print_generic_expr (dump_file, info->name, TDF_SLIM);
1728 fprintf (dump_file, " is invariant (%d)%s\n",
1729 info->inv_id, info->has_nonlin_use ? "" : ", eliminable");
1733 fprintf (dump_file, "\n");
1739 /* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
1740 is true, assume we are inside an address. If TOP_COMPREF is true, assume
1741 we are at the top-level of the processed address. */
1744 strip_offset_1 (tree expr, bool inside_addr, bool top_compref,
1745 unsigned HOST_WIDE_INT *offset)
1747 tree op0 = NULL_TREE, op1 = NULL_TREE, tmp, step;
1748 enum tree_code code;
1749 tree type, orig_type = TREE_TYPE (expr);
1750 unsigned HOST_WIDE_INT off0, off1, st;
1751 tree orig_expr = expr;
1755 type = TREE_TYPE (expr);
1756 code = TREE_CODE (expr);
1762 if (!cst_and_fits_in_hwi (expr)
1763 || integer_zerop (expr))
1766 *offset = int_cst_value (expr);
1767 return build_int_cst (orig_type, 0);
1771 op0 = TREE_OPERAND (expr, 0);
1772 op1 = TREE_OPERAND (expr, 1);
1774 op0 = strip_offset_1 (op0, false, false, &off0);
1775 op1 = strip_offset_1 (op1, false, false, &off1);
1777 *offset = (code == PLUS_EXPR ? off0 + off1 : off0 - off1);
1778 if (op0 == TREE_OPERAND (expr, 0)
1779 && op1 == TREE_OPERAND (expr, 1))
1782 if (integer_zerop (op1))
1784 else if (integer_zerop (op0))
1786 if (code == PLUS_EXPR)
1789 expr = fold_build1 (NEGATE_EXPR, type, op1);
1792 expr = fold_build2 (code, type, op0, op1);
1794 return fold_convert (orig_type, expr);
1800 step = array_ref_element_size (expr);
1801 if (!cst_and_fits_in_hwi (step))
1804 st = int_cst_value (step);
1805 op1 = TREE_OPERAND (expr, 1);
1806 op1 = strip_offset_1 (op1, false, false, &off1);
1807 *offset = off1 * st;
1810 && integer_zerop (op1))
1812 /* Strip the component reference completely. */
1813 op0 = TREE_OPERAND (expr, 0);
1814 op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
1824 tmp = component_ref_field_offset (expr);
1826 && cst_and_fits_in_hwi (tmp))
1828 /* Strip the component reference completely. */
1829 op0 = TREE_OPERAND (expr, 0);
1830 op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
1831 *offset = off0 + int_cst_value (tmp);
1837 op0 = TREE_OPERAND (expr, 0);
1838 op0 = strip_offset_1 (op0, true, true, &off0);
1841 if (op0 == TREE_OPERAND (expr, 0))
1844 expr = build_fold_addr_expr (op0);
1845 return fold_convert (orig_type, expr);
1848 inside_addr = false;
1855 /* Default handling of expressions for that we want to recurse into
1856 the first operand. */
1857 op0 = TREE_OPERAND (expr, 0);
1858 op0 = strip_offset_1 (op0, inside_addr, false, &off0);
1861 if (op0 == TREE_OPERAND (expr, 0)
1862 && (!op1 || op1 == TREE_OPERAND (expr, 1)))
1865 expr = copy_node (expr);
1866 TREE_OPERAND (expr, 0) = op0;
1868 TREE_OPERAND (expr, 1) = op1;
1870 /* Inside address, we might strip the top level component references,
1871 thus changing type of the expression. Handling of ADDR_EXPR
1873 expr = fold_convert (orig_type, expr);
1878 /* Strips constant offsets from EXPR and stores them to OFFSET. */
1881 strip_offset (tree expr, unsigned HOST_WIDE_INT *offset)
1883 return strip_offset_1 (expr, false, false, offset);
1886 /* Returns variant of TYPE that can be used as base for different uses.
1887 We return unsigned type with the same precision, which avoids problems
1891 generic_type_for (tree type)
1893 if (POINTER_TYPE_P (type))
1894 return unsigned_type_for (type);
1896 if (TYPE_UNSIGNED (type))
1899 return unsigned_type_for (type);
1902 /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
1903 the bitmap to that we should store it. */
1905 static struct ivopts_data *fd_ivopts_data;
1907 find_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
1909 bitmap *depends_on = data;
1910 struct version_info *info;
1912 if (TREE_CODE (*expr_p) != SSA_NAME)
1914 info = name_info (fd_ivopts_data, *expr_p);
1916 if (!info->inv_id || info->has_nonlin_use)
1920 *depends_on = BITMAP_ALLOC (NULL);
1921 bitmap_set_bit (*depends_on, info->inv_id);
1926 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
1927 position to POS. If USE is not NULL, the candidate is set as related to
1928 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
1929 replacement of the final value of the iv by a direct computation. */
1931 static struct iv_cand *
1932 add_candidate_1 (struct ivopts_data *data,
1933 tree base, tree step, bool important, enum iv_position pos,
1934 struct iv_use *use, tree incremented_at)
1937 struct iv_cand *cand = NULL;
1938 tree type, orig_type;
1942 orig_type = TREE_TYPE (base);
1943 type = generic_type_for (orig_type);
1944 if (type != orig_type)
1946 base = fold_convert (type, base);
1948 step = fold_convert (type, step);
1952 for (i = 0; i < n_iv_cands (data); i++)
1954 cand = iv_cand (data, i);
1956 if (cand->pos != pos)
1959 if (cand->incremented_at != incremented_at)
1973 if (!operand_equal_p (base, cand->iv->base, 0))
1976 if (null_or_integer_zerop (cand->iv->step))
1978 if (null_or_integer_zerop (step))
1983 if (step && operand_equal_p (step, cand->iv->step, 0))
1988 if (i == n_iv_cands (data))
1990 cand = XCNEW (struct iv_cand);
1996 cand->iv = alloc_iv (base, step);
1999 if (pos != IP_ORIGINAL && cand->iv)
2001 cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp");
2002 cand->var_after = cand->var_before;
2004 cand->important = important;
2005 cand->incremented_at = incremented_at;
2006 VEC_safe_push (iv_cand_p, heap, data->iv_candidates, cand);
2009 && TREE_CODE (step) != INTEGER_CST)
2011 fd_ivopts_data = data;
2012 walk_tree (&step, find_depends, &cand->depends_on, NULL);
2015 if (dump_file && (dump_flags & TDF_DETAILS))
2016 dump_cand (dump_file, cand);
2019 if (important && !cand->important)
2021 cand->important = true;
2022 if (dump_file && (dump_flags & TDF_DETAILS))
2023 fprintf (dump_file, "Candidate %d is important\n", cand->id);
2028 bitmap_set_bit (use->related_cands, i);
2029 if (dump_file && (dump_flags & TDF_DETAILS))
2030 fprintf (dump_file, "Candidate %d is related to use %d\n",
2037 /* Returns true if incrementing the induction variable at the end of the LOOP
2040 The purpose is to avoid splitting latch edge with a biv increment, thus
2041 creating a jump, possibly confusing other optimization passes and leaving
2042 less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS
2043 is not available (so we do not have a better alternative), or if the latch
2044 edge is already nonempty. */
2047 allow_ip_end_pos_p (struct loop *loop)
2049 if (!ip_normal_pos (loop))
2052 if (!empty_block_p (ip_end_pos (loop)))
2058 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2059 position to POS. If USE is not NULL, the candidate is set as related to
2060 it. The candidate computation is scheduled on all available positions. */
2063 add_candidate (struct ivopts_data *data,
2064 tree base, tree step, bool important, struct iv_use *use)
2066 if (ip_normal_pos (data->current_loop))
2067 add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL_TREE);
2068 if (ip_end_pos (data->current_loop)
2069 && allow_ip_end_pos_p (data->current_loop))
2070 add_candidate_1 (data, base, step, important, IP_END, use, NULL_TREE);
2073 /* Add a standard "0 + 1 * iteration" iv candidate for a
2074 type with SIZE bits. */
2077 add_standard_iv_candidates_for_size (struct ivopts_data *data,
2080 tree type = lang_hooks.types.type_for_size (size, true);
2081 add_candidate (data, build_int_cst (type, 0), build_int_cst (type, 1),
2085 /* Adds standard iv candidates. */
2088 add_standard_iv_candidates (struct ivopts_data *data)
2090 add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE);
2092 /* The same for a double-integer type if it is still fast enough. */
2093 if (BITS_PER_WORD >= INT_TYPE_SIZE * 2)
2094 add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE * 2);
2098 /* Adds candidates bases on the old induction variable IV. */
2101 add_old_iv_candidates (struct ivopts_data *data, struct iv *iv)
2104 struct iv_cand *cand;
2106 add_candidate (data, iv->base, iv->step, true, NULL);
2108 /* The same, but with initial value zero. */
2109 add_candidate (data,
2110 build_int_cst (TREE_TYPE (iv->base), 0),
2111 iv->step, true, NULL);
2113 phi = SSA_NAME_DEF_STMT (iv->ssa_name);
2114 if (TREE_CODE (phi) == PHI_NODE)
2116 /* Additionally record the possibility of leaving the original iv
2118 def = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (data->current_loop));
2119 cand = add_candidate_1 (data,
2120 iv->base, iv->step, true, IP_ORIGINAL, NULL,
2121 SSA_NAME_DEF_STMT (def));
2122 cand->var_before = iv->ssa_name;
2123 cand->var_after = def;
2127 /* Adds candidates based on the old induction variables. */
2130 add_old_ivs_candidates (struct ivopts_data *data)
2136 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
2138 iv = ver_info (data, i)->iv;
2139 if (iv && iv->biv_p && !null_or_integer_zerop (iv->step))
2140 add_old_iv_candidates (data, iv);
2144 /* Adds candidates based on the value of the induction variable IV and USE. */
2147 add_iv_value_candidates (struct ivopts_data *data,
2148 struct iv *iv, struct iv_use *use)
2150 unsigned HOST_WIDE_INT offset;
2153 add_candidate (data, iv->base, iv->step, false, use);
2155 /* The same, but with initial value zero. Make such variable important,
2156 since it is generic enough so that possibly many uses may be based
2158 add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
2159 iv->step, true, use);
2161 /* Third, try removing the constant offset. */
2162 base = strip_offset (iv->base, &offset);
2164 add_candidate (data, base, iv->step, false, use);
2167 /* Adds candidates based on the uses. */
2170 add_derived_ivs_candidates (struct ivopts_data *data)
2174 for (i = 0; i < n_iv_uses (data); i++)
2176 struct iv_use *use = iv_use (data, i);
2183 case USE_NONLINEAR_EXPR:
2186 /* Just add the ivs based on the value of the iv used here. */
2187 add_iv_value_candidates (data, use->iv, use);
2196 /* Record important candidates and add them to related_cands bitmaps
2200 record_important_candidates (struct ivopts_data *data)
2205 for (i = 0; i < n_iv_cands (data); i++)
2207 struct iv_cand *cand = iv_cand (data, i);
2209 if (cand->important)
2210 bitmap_set_bit (data->important_candidates, i);
2213 data->consider_all_candidates = (n_iv_cands (data)
2214 <= CONSIDER_ALL_CANDIDATES_BOUND);
2216 if (data->consider_all_candidates)
2218 /* We will not need "related_cands" bitmaps in this case,
2219 so release them to decrease peak memory consumption. */
2220 for (i = 0; i < n_iv_uses (data); i++)
2222 use = iv_use (data, i);
2223 BITMAP_FREE (use->related_cands);
2228 /* Add important candidates to the related_cands bitmaps. */
2229 for (i = 0; i < n_iv_uses (data); i++)
2230 bitmap_ior_into (iv_use (data, i)->related_cands,
2231 data->important_candidates);
2235 /* Finds the candidates for the induction variables. */
2238 find_iv_candidates (struct ivopts_data *data)
2240 /* Add commonly used ivs. */
2241 add_standard_iv_candidates (data);
2243 /* Add old induction variables. */
2244 add_old_ivs_candidates (data);
2246 /* Add induction variables derived from uses. */
2247 add_derived_ivs_candidates (data);
2249 /* Record the important candidates. */
2250 record_important_candidates (data);
2253 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
2254 If consider_all_candidates is true, we use a two-dimensional array, otherwise
2255 we allocate a simple list to every use. */
2258 alloc_use_cost_map (struct ivopts_data *data)
2260 unsigned i, size, s, j;
2262 for (i = 0; i < n_iv_uses (data); i++)
2264 struct iv_use *use = iv_use (data, i);
2267 if (data->consider_all_candidates)
2268 size = n_iv_cands (data);
2272 EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi)
2277 /* Round up to the power of two, so that moduling by it is fast. */
2278 for (size = 1; size < s; size <<= 1)
2282 use->n_map_members = size;
2283 use->cost_map = XCNEWVEC (struct cost_pair, size);
2287 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
2288 on invariants DEPENDS_ON and that the value used in expressing it
2292 set_use_iv_cost (struct ivopts_data *data,
2293 struct iv_use *use, struct iv_cand *cand, unsigned cost,
2294 bitmap depends_on, tree value)
2300 BITMAP_FREE (depends_on);
2304 if (data->consider_all_candidates)
2306 use->cost_map[cand->id].cand = cand;
2307 use->cost_map[cand->id].cost = cost;
2308 use->cost_map[cand->id].depends_on = depends_on;
2309 use->cost_map[cand->id].value = value;
2313 /* n_map_members is a power of two, so this computes modulo. */
2314 s = cand->id & (use->n_map_members - 1);
2315 for (i = s; i < use->n_map_members; i++)
2316 if (!use->cost_map[i].cand)
2318 for (i = 0; i < s; i++)
2319 if (!use->cost_map[i].cand)
2325 use->cost_map[i].cand = cand;
2326 use->cost_map[i].cost = cost;
2327 use->cost_map[i].depends_on = depends_on;
2328 use->cost_map[i].value = value;
2331 /* Gets cost of (USE, CANDIDATE) pair. */
2333 static struct cost_pair *
2334 get_use_iv_cost (struct ivopts_data *data, struct iv_use *use,
2335 struct iv_cand *cand)
2338 struct cost_pair *ret;
2343 if (data->consider_all_candidates)
2345 ret = use->cost_map + cand->id;
2352 /* n_map_members is a power of two, so this computes modulo. */
2353 s = cand->id & (use->n_map_members - 1);
2354 for (i = s; i < use->n_map_members; i++)
2355 if (use->cost_map[i].cand == cand)
2356 return use->cost_map + i;
2358 for (i = 0; i < s; i++)
2359 if (use->cost_map[i].cand == cand)
2360 return use->cost_map + i;
2365 /* Returns estimate on cost of computing SEQ. */
2373 for (; seq; seq = NEXT_INSN (seq))
2375 set = single_set (seq);
2377 cost += rtx_cost (set, SET);
2385 /* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
2387 produce_memory_decl_rtl (tree obj, int *regno)
2392 if (TREE_STATIC (obj) || DECL_EXTERNAL (obj))
2394 const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj));
2395 x = gen_rtx_SYMBOL_REF (Pmode, name);
2398 x = gen_raw_REG (Pmode, (*regno)++);
2400 return gen_rtx_MEM (DECL_MODE (obj), x);
2403 /* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
2404 walk_tree. DATA contains the actual fake register number. */
2407 prepare_decl_rtl (tree *expr_p, int *ws, void *data)
2409 tree obj = NULL_TREE;
2413 switch (TREE_CODE (*expr_p))
2416 for (expr_p = &TREE_OPERAND (*expr_p, 0);
2417 handled_component_p (*expr_p);
2418 expr_p = &TREE_OPERAND (*expr_p, 0))
2421 if (DECL_P (obj) && !DECL_RTL_SET_P (obj))
2422 x = produce_memory_decl_rtl (obj, regno);
2427 obj = SSA_NAME_VAR (*expr_p);
2428 if (!DECL_RTL_SET_P (obj))
2429 x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
2438 if (DECL_RTL_SET_P (obj))
2441 if (DECL_MODE (obj) == BLKmode)
2442 x = produce_memory_decl_rtl (obj, regno);
2444 x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
2454 VEC_safe_push (tree, heap, decl_rtl_to_reset, obj);
2455 SET_DECL_RTL (obj, x);
2461 /* Determines cost of the computation of EXPR. */
2464 computation_cost (tree expr)
2467 tree type = TREE_TYPE (expr);
2469 /* Avoid using hard regs in ways which may be unsupported. */
2470 int regno = LAST_VIRTUAL_REGISTER + 1;
2472 walk_tree (&expr, prepare_decl_rtl, ®no, NULL);
2474 rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL);
2478 cost = seq_cost (seq);
2480 cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type));
2485 /* Returns variable containing the value of candidate CAND at statement AT. */
2488 var_at_stmt (struct loop *loop, struct iv_cand *cand, tree stmt)
2490 if (stmt_after_increment (loop, cand, stmt))
2491 return cand->var_after;
2493 return cand->var_before;
2496 /* Return the most significant (sign) bit of T. Similar to tree_int_cst_msb,
2497 but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE. */
2500 tree_int_cst_sign_bit (tree t)
2502 unsigned bitno = TYPE_PRECISION (TREE_TYPE (t)) - 1;
2503 unsigned HOST_WIDE_INT w;
2505 if (bitno < HOST_BITS_PER_WIDE_INT)
2506 w = TREE_INT_CST_LOW (t);
2509 w = TREE_INT_CST_HIGH (t);
2510 bitno -= HOST_BITS_PER_WIDE_INT;
2513 return (w >> bitno) & 1;
2516 /* If we can prove that TOP = cst * BOT for some constant cst,
2517 store cst to MUL and return true. Otherwise return false.
2518 The returned value is always sign-extended, regardless of the
2519 signedness of TOP and BOT. */
2522 constant_multiple_of (tree top, tree bot, double_int *mul)
2525 enum tree_code code;
2526 double_int res, p0, p1;
2527 unsigned precision = TYPE_PRECISION (TREE_TYPE (top));
2532 if (operand_equal_p (top, bot, 0))
2534 *mul = double_int_one;
2538 code = TREE_CODE (top);
2542 mby = TREE_OPERAND (top, 1);
2543 if (TREE_CODE (mby) != INTEGER_CST)
2546 if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &res))
2549 *mul = double_int_sext (double_int_mul (res, tree_to_double_int (mby)),
2555 if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &p0)
2556 || !constant_multiple_of (TREE_OPERAND (top, 1), bot, &p1))
2559 if (code == MINUS_EXPR)
2560 p1 = double_int_neg (p1);
2561 *mul = double_int_sext (double_int_add (p0, p1), precision);
2565 if (TREE_CODE (bot) != INTEGER_CST)
2568 p0 = double_int_sext (tree_to_double_int (top), precision);
2569 p1 = double_int_sext (tree_to_double_int (bot), precision);
2570 if (double_int_zero_p (p1))
2572 *mul = double_int_sext (double_int_sdivmod (p0, p1, FLOOR_DIV_EXPR, &res),
2574 return double_int_zero_p (res);
2581 /* Folds EXPR using the affine expressions framework. */
2584 fold_affine_expr (tree expr)
2586 tree type = TREE_TYPE (expr);
2587 struct affine_tree_combination comb;
2589 if (TYPE_PRECISION (type) > HOST_BITS_PER_WIDE_INT)
2592 tree_to_aff_combination (expr, type, &comb);
2593 return aff_combination_to_tree (&comb);
2596 /* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
2597 same precision that is at least as wide as the precision of TYPE, stores
2598 BA to A and BB to B, and returns the type of BA. Otherwise, returns the
2602 determine_common_wider_type (tree *a, tree *b)
2604 tree wider_type = NULL;
2606 tree atype = TREE_TYPE (*a);
2608 if ((TREE_CODE (*a) == NOP_EXPR
2609 || TREE_CODE (*a) == CONVERT_EXPR))
2611 suba = TREE_OPERAND (*a, 0);
2612 wider_type = TREE_TYPE (suba);
2613 if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (atype))
2619 if ((TREE_CODE (*b) == NOP_EXPR
2620 || TREE_CODE (*b) == CONVERT_EXPR))
2622 subb = TREE_OPERAND (*b, 0);
2623 if (TYPE_PRECISION (wider_type) != TYPE_PRECISION (TREE_TYPE (subb)))
2634 /* Determines the expression by that USE is expressed from induction variable
2635 CAND at statement AT in LOOP. The expression is stored in a decomposed
2636 form into AFF. Returns false if USE cannot be expressed using CAND. */
2639 get_computation_aff (struct loop *loop,
2640 struct iv_use *use, struct iv_cand *cand, tree at,
2641 struct affine_tree_combination *aff)
2643 tree ubase = use->iv->base;
2644 tree ustep = use->iv->step;
2645 tree cbase = cand->iv->base;
2646 tree cstep = cand->iv->step, cstep_common;
2647 tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
2648 tree common_type, var;
2650 aff_tree cbase_aff, var_aff;
2653 if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
2655 /* We do not have a precision to express the values of use. */
2659 var = var_at_stmt (loop, cand, at);
2660 uutype = unsigned_type_for (utype);
2662 /* If the conversion is not noop, perform it. */
2663 if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
2665 cstep = fold_convert (uutype, cstep);
2666 cbase = fold_convert (uutype, cbase);
2667 var = fold_convert (uutype, var);
2670 if (!constant_multiple_of (ustep, cstep, &rat))
2673 /* In case both UBASE and CBASE are shortened to UUTYPE from some common
2674 type, we achieve better folding by computing their difference in this
2675 wider type, and cast the result to UUTYPE. We do not need to worry about
2676 overflows, as all the arithmetics will in the end be performed in UUTYPE
2678 common_type = determine_common_wider_type (&ubase, &cbase);
2680 /* use = ubase - ratio * cbase + ratio * var. */
2681 tree_to_aff_combination (ubase, common_type, aff);
2682 tree_to_aff_combination (cbase, common_type, &cbase_aff);
2683 tree_to_aff_combination (var, uutype, &var_aff);
2685 /* We need to shift the value if we are after the increment. */
2686 if (stmt_after_increment (loop, cand, at))
2690 if (common_type != uutype)
2691 cstep_common = fold_convert (common_type, cstep);
2693 cstep_common = cstep;
2695 tree_to_aff_combination (cstep_common, common_type, &cstep_aff);
2696 aff_combination_add (&cbase_aff, &cstep_aff);
2699 aff_combination_scale (&cbase_aff, double_int_neg (rat));
2700 aff_combination_add (aff, &cbase_aff);
2701 if (common_type != uutype)
2702 aff_combination_convert (aff, uutype);
2704 aff_combination_scale (&var_aff, rat);
2705 aff_combination_add (aff, &var_aff);
2710 /* Determines the expression by that USE is expressed from induction variable
2711 CAND at statement AT in LOOP. The computation is unshared. */
2714 get_computation_at (struct loop *loop,
2715 struct iv_use *use, struct iv_cand *cand, tree at)
2718 tree type = TREE_TYPE (use->iv->base);
2720 if (!get_computation_aff (loop, use, cand, at, &aff))
2722 unshare_aff_combination (&aff);
2723 return fold_convert (type, aff_combination_to_tree (&aff));
2726 /* Determines the expression by that USE is expressed from induction variable
2727 CAND in LOOP. The computation is unshared. */
2730 get_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand)
2732 return get_computation_at (loop, use, cand, use->stmt);
2735 /* Returns cost of addition in MODE. */
2738 add_cost (enum machine_mode mode)
2740 static unsigned costs[NUM_MACHINE_MODES];
2748 force_operand (gen_rtx_fmt_ee (PLUS, mode,
2749 gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
2750 gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 2)),
2755 cost = seq_cost (seq);
2761 if (dump_file && (dump_flags & TDF_DETAILS))
2762 fprintf (dump_file, "Addition in %s costs %d\n",
2763 GET_MODE_NAME (mode), cost);
2767 /* Entry in a hashtable of already known costs for multiplication. */
2770 HOST_WIDE_INT cst; /* The constant to multiply by. */
2771 enum machine_mode mode; /* In mode. */
2772 unsigned cost; /* The cost. */
2775 /* Counts hash value for the ENTRY. */
2778 mbc_entry_hash (const void *entry)
2780 const struct mbc_entry *e = entry;
2782 return 57 * (hashval_t) e->mode + (hashval_t) (e->cst % 877);
2785 /* Compares the hash table entries ENTRY1 and ENTRY2. */
2788 mbc_entry_eq (const void *entry1, const void *entry2)
2790 const struct mbc_entry *e1 = entry1;
2791 const struct mbc_entry *e2 = entry2;
2793 return (e1->mode == e2->mode
2794 && e1->cst == e2->cst);
2797 /* Returns cost of multiplication by constant CST in MODE. */
2800 multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode)
2802 static htab_t costs;
2803 struct mbc_entry **cached, act;
2808 costs = htab_create (100, mbc_entry_hash, mbc_entry_eq, free);
2812 cached = (struct mbc_entry **) htab_find_slot (costs, &act, INSERT);
2814 return (*cached)->cost;
2816 *cached = XNEW (struct mbc_entry);
2817 (*cached)->mode = mode;
2818 (*cached)->cst = cst;
2821 expand_mult (mode, gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
2822 gen_int_mode (cst, mode), NULL_RTX, 0);
2826 cost = seq_cost (seq);
2828 if (dump_file && (dump_flags & TDF_DETAILS))
2829 fprintf (dump_file, "Multiplication by %d in %s costs %d\n",
2830 (int) cst, GET_MODE_NAME (mode), cost);
2832 (*cached)->cost = cost;
2837 /* Returns true if multiplying by RATIO is allowed in an address. Test the
2838 validity for a memory reference accessing memory of mode MODE. */
2841 multiplier_allowed_in_address_p (HOST_WIDE_INT ratio, enum machine_mode mode)
2843 #define MAX_RATIO 128
2844 static sbitmap valid_mult[MAX_MACHINE_MODE];
2846 if (!valid_mult[mode])
2848 rtx reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
2852 valid_mult[mode] = sbitmap_alloc (2 * MAX_RATIO + 1);
2853 sbitmap_zero (valid_mult[mode]);
2854 addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX);
2855 for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
2857 XEXP (addr, 1) = gen_int_mode (i, Pmode);
2858 if (memory_address_p (mode, addr))
2859 SET_BIT (valid_mult[mode], i + MAX_RATIO);
2862 if (dump_file && (dump_flags & TDF_DETAILS))
2864 fprintf (dump_file, " allowed multipliers:");
2865 for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
2866 if (TEST_BIT (valid_mult[mode], i + MAX_RATIO))
2867 fprintf (dump_file, " %d", (int) i);
2868 fprintf (dump_file, "\n");
2869 fprintf (dump_file, "\n");
2873 if (ratio > MAX_RATIO || ratio < -MAX_RATIO)
2876 return TEST_BIT (valid_mult[mode], ratio + MAX_RATIO);
2879 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
2880 If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
2881 variable is omitted. Compute the cost for a memory reference that accesses
2882 a memory location of mode MEM_MODE.
2884 TODO -- there must be some better way. This all is quite crude. */
2887 get_address_cost (bool symbol_present, bool var_present,
2888 unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio,
2889 enum machine_mode mem_mode)
2891 static bool initialized[MAX_MACHINE_MODE];
2892 static HOST_WIDE_INT rat[MAX_MACHINE_MODE], off[MAX_MACHINE_MODE];
2893 static HOST_WIDE_INT min_offset[MAX_MACHINE_MODE], max_offset[MAX_MACHINE_MODE];
2894 static unsigned costs[MAX_MACHINE_MODE][2][2][2][2];
2895 unsigned cost, acost;
2896 bool offset_p, ratio_p;
2897 HOST_WIDE_INT s_offset;
2898 unsigned HOST_WIDE_INT mask;
2901 if (!initialized[mem_mode])
2904 HOST_WIDE_INT start = BIGGEST_ALIGNMENT / BITS_PER_UNIT;
2905 int old_cse_not_expected;
2906 unsigned sym_p, var_p, off_p, rat_p, add_c;
2907 rtx seq, addr, base;
2910 initialized[mem_mode] = true;
2912 reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
2914 addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
2915 for (i = start; i <= 1 << 20; i <<= 1)
2917 XEXP (addr, 1) = gen_int_mode (i, Pmode);
2918 if (!memory_address_p (mem_mode, addr))
2921 max_offset[mem_mode] = i == start ? 0 : i >> 1;
2922 off[mem_mode] = max_offset[mem_mode];
2924 for (i = start; i <= 1 << 20; i <<= 1)
2926 XEXP (addr, 1) = gen_int_mode (-i, Pmode);
2927 if (!memory_address_p (mem_mode, addr))
2930 min_offset[mem_mode] = i == start ? 0 : -(i >> 1);
2932 if (dump_file && (dump_flags & TDF_DETAILS))
2934 fprintf (dump_file, "get_address_cost:\n");
2935 fprintf (dump_file, " min offset %s %d\n",
2936 GET_MODE_NAME (mem_mode),
2937 (int) min_offset[mem_mode]);
2938 fprintf (dump_file, " max offset %s %d\n",
2939 GET_MODE_NAME (mem_mode),
2940 (int) max_offset[mem_mode]);
2944 for (i = 2; i <= MAX_RATIO; i++)
2945 if (multiplier_allowed_in_address_p (i, mem_mode))
2951 /* Compute the cost of various addressing modes. */
2953 reg0 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
2954 reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
2956 for (i = 0; i < 16; i++)
2959 var_p = (i >> 1) & 1;
2960 off_p = (i >> 2) & 1;
2961 rat_p = (i >> 3) & 1;
2965 addr = gen_rtx_fmt_ee (MULT, Pmode, addr,
2966 gen_int_mode (rat[mem_mode], Pmode));
2969 addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1);
2973 base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
2975 base = gen_rtx_fmt_e (CONST, Pmode,
2976 gen_rtx_fmt_ee (PLUS, Pmode,
2978 gen_int_mode (off[mem_mode],
2982 base = gen_int_mode (off[mem_mode], Pmode);
2987 addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, base);
2990 /* To avoid splitting addressing modes, pretend that no cse will
2992 old_cse_not_expected = cse_not_expected;
2993 cse_not_expected = true;
2994 addr = memory_address (mem_mode, addr);
2995 cse_not_expected = old_cse_not_expected;
2999 acost = seq_cost (seq);
3000 acost += address_cost (addr, mem_mode);
3004 costs[mem_mode][sym_p][var_p][off_p][rat_p] = acost;
3007 /* On some targets, it is quite expensive to load symbol to a register,
3008 which makes addresses that contain symbols look much more expensive.
3009 However, the symbol will have to be loaded in any case before the
3010 loop (and quite likely we have it in register already), so it does not
3011 make much sense to penalize them too heavily. So make some final
3012 tweaks for the SYMBOL_PRESENT modes:
3014 If VAR_PRESENT is false, and the mode obtained by changing symbol to
3015 var is cheaper, use this mode with small penalty.
3016 If VAR_PRESENT is true, try whether the mode with
3017 SYMBOL_PRESENT = false is cheaper even with cost of addition, and
3018 if this is the case, use it. */
3019 add_c = add_cost (Pmode);
3020 for (i = 0; i < 8; i++)
3023 off_p = (i >> 1) & 1;
3024 rat_p = (i >> 2) & 1;
3026 acost = costs[mem_mode][0][1][off_p][rat_p] + 1;
3030 if (acost < costs[mem_mode][1][var_p][off_p][rat_p])
3031 costs[mem_mode][1][var_p][off_p][rat_p] = acost;
3034 if (dump_file && (dump_flags & TDF_DETAILS))
3036 fprintf (dump_file, "Address costs:\n");
3038 for (i = 0; i < 16; i++)
3041 var_p = (i >> 1) & 1;
3042 off_p = (i >> 2) & 1;
3043 rat_p = (i >> 3) & 1;
3045 fprintf (dump_file, " ");
3047 fprintf (dump_file, "sym + ");
3049 fprintf (dump_file, "var + ");
3051 fprintf (dump_file, "cst + ");
3053 fprintf (dump_file, "rat * ");
3055 acost = costs[mem_mode][sym_p][var_p][off_p][rat_p];
3056 fprintf (dump_file, "index costs %d\n", acost);
3058 fprintf (dump_file, "\n");
3062 bits = GET_MODE_BITSIZE (Pmode);
3063 mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
3065 if ((offset >> (bits - 1) & 1))
3070 offset_p = (s_offset != 0
3071 && min_offset[mem_mode] <= s_offset
3072 && s_offset <= max_offset[mem_mode]);
3073 ratio_p = (ratio != 1
3074 && multiplier_allowed_in_address_p (ratio, mem_mode));
3076 if (ratio != 1 && !ratio_p)
3077 cost += multiply_by_cost (ratio, Pmode);
3079 if (s_offset && !offset_p && !symbol_present)
3080 cost += add_cost (Pmode);
3082 acost = costs[mem_mode][symbol_present][var_present][offset_p][ratio_p];
3083 return cost + acost;
3086 /* Estimates cost of forcing expression EXPR into a variable. */
3089 force_expr_to_var_cost (tree expr)
3091 static bool costs_initialized = false;
3092 static unsigned integer_cost;
3093 static unsigned symbol_cost;
3094 static unsigned address_cost;
3096 unsigned cost0, cost1, cost;
3097 enum machine_mode mode;
3099 if (!costs_initialized)
3101 tree var = create_tmp_var_raw (integer_type_node, "test_var");
3102 rtx x = gen_rtx_MEM (DECL_MODE (var),
3103 gen_rtx_SYMBOL_REF (Pmode, "test_var"));
3105 tree type = build_pointer_type (integer_type_node);
3107 integer_cost = computation_cost (build_int_cst (integer_type_node,
3110 SET_DECL_RTL (var, x);
3111 TREE_STATIC (var) = 1;
3112 addr = build1 (ADDR_EXPR, type, var);
3113 symbol_cost = computation_cost (addr) + 1;
3116 = computation_cost (build2 (PLUS_EXPR, type,
3118 build_int_cst (type, 2000))) + 1;
3119 if (dump_file && (dump_flags & TDF_DETAILS))
3121 fprintf (dump_file, "force_expr_to_var_cost:\n");
3122 fprintf (dump_file, " integer %d\n", (int) integer_cost);
3123 fprintf (dump_file, " symbol %d\n", (int) symbol_cost);
3124 fprintf (dump_file, " address %d\n", (int) address_cost);
3125 fprintf (dump_file, " other %d\n", (int) target_spill_cost);
3126 fprintf (dump_file, "\n");
3129 costs_initialized = true;
3134 if (SSA_VAR_P (expr))
3137 if (TREE_INVARIANT (expr))
3139 if (TREE_CODE (expr) == INTEGER_CST)
3140 return integer_cost;
3142 if (TREE_CODE (expr) == ADDR_EXPR)
3144 tree obj = TREE_OPERAND (expr, 0);
3146 if (TREE_CODE (obj) == VAR_DECL
3147 || TREE_CODE (obj) == PARM_DECL
3148 || TREE_CODE (obj) == RESULT_DECL)
3152 return address_cost;
3155 switch (TREE_CODE (expr))
3160 op0 = TREE_OPERAND (expr, 0);
3161 op1 = TREE_OPERAND (expr, 1);
3165 if (is_gimple_val (op0))
3168 cost0 = force_expr_to_var_cost (op0);
3170 if (is_gimple_val (op1))
3173 cost1 = force_expr_to_var_cost (op1);
3178 /* Just an arbitrary value, FIXME. */
3179 return target_spill_cost;
3182 mode = TYPE_MODE (TREE_TYPE (expr));
3183 switch (TREE_CODE (expr))
3187 cost = add_cost (mode);
3191 if (cst_and_fits_in_hwi (op0))
3192 cost = multiply_by_cost (int_cst_value (op0), mode);
3193 else if (cst_and_fits_in_hwi (op1))
3194 cost = multiply_by_cost (int_cst_value (op1), mode);
3196 return target_spill_cost;
3206 /* Bound the cost by target_spill_cost. The parts of complicated
3207 computations often are either loop invariant or at least can
3208 be shared between several iv uses, so letting this grow without
3209 limits would not give reasonable results. */
3210 return cost < target_spill_cost ? cost : target_spill_cost;
3213 /* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
3214 invariants the computation depends on. */
3217 force_var_cost (struct ivopts_data *data,
3218 tree expr, bitmap *depends_on)
3222 fd_ivopts_data = data;
3223 walk_tree (&expr, find_depends, depends_on, NULL);
3226 return force_expr_to_var_cost (expr);
3229 /* Estimates cost of expressing address ADDR as var + symbol + offset. The
3230 value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
3231 to false if the corresponding part is missing. DEPENDS_ON is a set of the
3232 invariants the computation depends on. */
3235 split_address_cost (struct ivopts_data *data,
3236 tree addr, bool *symbol_present, bool *var_present,
3237 unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
3240 HOST_WIDE_INT bitsize;
3241 HOST_WIDE_INT bitpos;
3243 enum machine_mode mode;
3244 int unsignedp, volatilep;
3246 core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode,
3247 &unsignedp, &volatilep, false);
3250 || bitpos % BITS_PER_UNIT != 0
3251 || TREE_CODE (core) != VAR_DECL)
3253 *symbol_present = false;
3254 *var_present = true;
3255 fd_ivopts_data = data;
3256 walk_tree (&addr, find_depends, depends_on, NULL);
3257 return target_spill_cost;
3260 *offset += bitpos / BITS_PER_UNIT;
3261 if (TREE_STATIC (core)
3262 || DECL_EXTERNAL (core))
3264 *symbol_present = true;
3265 *var_present = false;
3269 *symbol_present = false;
3270 *var_present = true;
3274 /* Estimates cost of expressing difference of addresses E1 - E2 as
3275 var + symbol + offset. The value of offset is added to OFFSET,
3276 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3277 part is missing. DEPENDS_ON is a set of the invariants the computation
3281 ptr_difference_cost (struct ivopts_data *data,
3282 tree e1, tree e2, bool *symbol_present, bool *var_present,
3283 unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
3285 HOST_WIDE_INT diff = 0;
3288 gcc_assert (TREE_CODE (e1) == ADDR_EXPR);
3290 if (ptr_difference_const (e1, e2, &diff))
3293 *symbol_present = false;
3294 *var_present = false;
3298 if (e2 == integer_zero_node)
3299 return split_address_cost (data, TREE_OPERAND (e1, 0),
3300 symbol_present, var_present, offset, depends_on);
3302 *symbol_present = false;
3303 *var_present = true;
3305 cost = force_var_cost (data, e1, depends_on);
3306 cost += force_var_cost (data, e2, depends_on);
3307 cost += add_cost (Pmode);
3312 /* Estimates cost of expressing difference E1 - E2 as
3313 var + symbol + offset. The value of offset is added to OFFSET,
3314 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3315 part is missing. DEPENDS_ON is a set of the invariants the computation
3319 difference_cost (struct ivopts_data *data,
3320 tree e1, tree e2, bool *symbol_present, bool *var_present,
3321 unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
3324 enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
3325 unsigned HOST_WIDE_INT off1, off2;
3327 e1 = strip_offset (e1, &off1);
3328 e2 = strip_offset (e2, &off2);
3329 *offset += off1 - off2;
3334 if (TREE_CODE (e1) == ADDR_EXPR)
3335 return ptr_difference_cost (data, e1, e2, symbol_present, var_present, offset,
3337 *symbol_present = false;
3339 if (operand_equal_p (e1, e2, 0))
3341 *var_present = false;
3344 *var_present = true;
3345 if (integer_zerop (e2))
3346 return force_var_cost (data, e1, depends_on);
3348 if (integer_zerop (e1))
3350 cost = force_var_cost (data, e2, depends_on);
3351 cost += multiply_by_cost (-1, mode);
3356 cost = force_var_cost (data, e1, depends_on);
3357 cost += force_var_cost (data, e2, depends_on);
3358 cost += add_cost (mode);
3363 /* Determines the cost of the computation by that USE is expressed
3364 from induction variable CAND. If ADDRESS_P is true, we just need
3365 to create an address from it, otherwise we want to get it into
3366 register. A set of invariants we depend on is stored in
3367 DEPENDS_ON. AT is the statement at that the value is computed. */
3370 get_computation_cost_at (struct ivopts_data *data,
3371 struct iv_use *use, struct iv_cand *cand,
3372 bool address_p, bitmap *depends_on, tree at)
3374 tree ubase = use->iv->base, ustep = use->iv->step;
3376 tree utype = TREE_TYPE (ubase), ctype;
3377 unsigned HOST_WIDE_INT cstepi, offset = 0;
3378 HOST_WIDE_INT ratio, aratio;
3379 bool var_present, symbol_present;
3380 unsigned cost = 0, n_sums;
3385 /* Only consider real candidates. */
3389 cbase = cand->iv->base;
3390 cstep = cand->iv->step;
3391 ctype = TREE_TYPE (cbase);
3393 if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
3395 /* We do not have a precision to express the values of use. */
3401 /* Do not try to express address of an object with computation based
3402 on address of a different object. This may cause problems in rtl
3403 level alias analysis (that does not expect this to be happening,
3404 as this is illegal in C), and would be unlikely to be useful
3406 if (use->iv->base_object
3407 && cand->iv->base_object
3408 && !operand_equal_p (use->iv->base_object, cand->iv->base_object, 0))
3412 if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
3414 /* TODO -- add direct handling of this case. */
3418 /* CSTEPI is removed from the offset in case statement is after the
3419 increment. If the step is not constant, we use zero instead.
3420 This is a bit imprecise (there is the extra addition), but
3421 redundancy elimination is likely to transform the code so that
3422 it uses value of the variable before increment anyway,
3423 so it is not that much unrealistic. */
3424 if (cst_and_fits_in_hwi (cstep))
3425 cstepi = int_cst_value (cstep);
3429 if (!constant_multiple_of (ustep, cstep, &rat))
3432 if (double_int_fits_in_shwi_p (rat))
3433 ratio = double_int_to_shwi (rat);
3437 /* use = ubase + ratio * (var - cbase). If either cbase is a constant
3438 or ratio == 1, it is better to handle this like
3440 ubase - ratio * cbase + ratio * var
3442 (also holds in the case ratio == -1, TODO. */
3444 if (cst_and_fits_in_hwi (cbase))
3446 offset = - ratio * int_cst_value (cbase);
3447 cost += difference_cost (data,
3448 ubase, integer_zero_node,
3449 &symbol_present, &var_present, &offset,
3452 else if (ratio == 1)
3454 cost += difference_cost (data,
3456 &symbol_present, &var_present, &offset,
3461 cost += force_var_cost (data, cbase, depends_on);
3462 cost += add_cost (TYPE_MODE (ctype));
3463 cost += difference_cost (data,
3464 ubase, integer_zero_node,
3465 &symbol_present, &var_present, &offset,
3469 /* If we are after the increment, the value of the candidate is higher by
3471 if (stmt_after_increment (data->current_loop, cand, at))
3472 offset -= ratio * cstepi;
3474 /* Now the computation is in shape symbol + var1 + const + ratio * var2.
3475 (symbol/var/const parts may be omitted). If we are looking for an address,
3476 find the cost of addressing this. */
3478 return cost + get_address_cost (symbol_present, var_present, offset, ratio,
3479 TYPE_MODE (TREE_TYPE (*use->op_p)));
3481 /* Otherwise estimate the costs for computing the expression. */
3482 aratio = ratio > 0 ? ratio : -ratio;
3483 if (!symbol_present && !var_present && !offset)
3486 cost += multiply_by_cost (ratio, TYPE_MODE (ctype));
3492 cost += multiply_by_cost (aratio, TYPE_MODE (ctype));
3496 /* Symbol + offset should be compile-time computable. */
3497 && (symbol_present || offset))
3500 return cost + n_sums * add_cost (TYPE_MODE (ctype));
3504 /* Just get the expression, expand it and measure the cost. */
3505 tree comp = get_computation_at (data->current_loop, use, cand, at);
3511 comp = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (comp)), comp);
3513 return computation_cost (comp);
3517 /* Determines the cost of the computation by that USE is expressed
3518 from induction variable CAND. If ADDRESS_P is true, we just need
3519 to create an address from it, otherwise we want to get it into
3520 register. A set of invariants we depend on is stored in
3524 get_computation_cost (struct ivopts_data *data,
3525 struct iv_use *use, struct iv_cand *cand,
3526 bool address_p, bitmap *depends_on)
3528 return get_computation_cost_at (data,
3529 use, cand, address_p, depends_on, use->stmt);
3532 /* Determines cost of basing replacement of USE on CAND in a generic
3536 determine_use_iv_cost_generic (struct ivopts_data *data,
3537 struct iv_use *use, struct iv_cand *cand)
3542 /* The simple case first -- if we need to express value of the preserved
3543 original biv, the cost is 0. This also prevents us from counting the
3544 cost of increment twice -- once at this use and once in the cost of
3546 if (cand->pos == IP_ORIGINAL
3547 && cand->incremented_at == use->stmt)
3549 set_use_iv_cost (data, use, cand, 0, NULL, NULL_TREE);
3553 cost = get_computation_cost (data, use, cand, false, &depends_on);
3554 set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
3556 return cost != INFTY;
3559 /* Determines cost of basing replacement of USE on CAND in an address. */
3562 determine_use_iv_cost_address (struct ivopts_data *data,
3563 struct iv_use *use, struct iv_cand *cand)
3566 unsigned cost = get_computation_cost (data, use, cand, true, &depends_on);
3568 set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
3570 return cost != INFTY;
3573 /* Computes value of induction variable IV in iteration NITER. */
3576 iv_value (struct iv *iv, tree niter)
3579 tree type = TREE_TYPE (iv->base);
3581 niter = fold_convert (type, niter);
3582 val = fold_build2 (MULT_EXPR, type, iv->step, niter);
3584 return fold_build2 (PLUS_EXPR, type, iv->base, val);
3587 /* Computes value of candidate CAND at position AT in iteration NITER. */
3590 cand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter)
3592 tree val = iv_value (cand->iv, niter);
3593 tree type = TREE_TYPE (cand->iv->base);
3595 if (stmt_after_increment (loop, cand, at))
3596 val = fold_build2 (PLUS_EXPR, type, val, cand->iv->step);
3601 /* Returns period of induction variable iv. */
3604 iv_period (struct iv *iv)
3606 tree step = iv->step, period, type;
3609 gcc_assert (step && TREE_CODE (step) == INTEGER_CST);
3611 /* Period of the iv is gcd (step, type range). Since type range is power
3612 of two, it suffices to determine the maximum power of two that divides
3614 pow2div = num_ending_zeros (step);
3615 type = unsigned_type_for (TREE_TYPE (step));
3617 period = build_low_bits_mask (type,
3618 (TYPE_PRECISION (type)
3619 - tree_low_cst (pow2div, 1)));
3624 /* Returns the comparison operator used when eliminating the iv USE. */
3626 static enum tree_code
3627 iv_elimination_compare (struct ivopts_data *data, struct iv_use *use)
3629 struct loop *loop = data->current_loop;
3633 ex_bb = bb_for_stmt (use->stmt);
3634 exit = EDGE_SUCC (ex_bb, 0);
3635 if (flow_bb_inside_loop_p (loop, exit->dest))
3636 exit = EDGE_SUCC (ex_bb, 1);
3638 return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
3641 /* Check whether it is possible to express the condition in USE by comparison
3642 of candidate CAND. If so, store the value compared with to BOUND. */
3645 may_eliminate_iv (struct ivopts_data *data,
3646 struct iv_use *use, struct iv_cand *cand, tree *bound)
3651 tree wider_type, period, per_type;
3652 struct loop *loop = data->current_loop;
3654 if (TREE_CODE (cand->iv->step) != INTEGER_CST)
3657 /* For now works only for exits that dominate the loop latch. TODO -- extend
3658 for other conditions inside loop body. */
3659 ex_bb = bb_for_stmt (use->stmt);
3660 if (use->stmt != last_stmt (ex_bb)
3661 || TREE_CODE (use->stmt) != COND_EXPR)
3663 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, ex_bb))
3666 exit = EDGE_SUCC (ex_bb, 0);
3667 if (flow_bb_inside_loop_p (loop, exit->dest))
3668 exit = EDGE_SUCC (ex_bb, 1);
3669 if (flow_bb_inside_loop_p (loop, exit->dest))
3672 nit = niter_for_exit (data, exit);
3676 nit_type = TREE_TYPE (nit);
3678 /* Determine whether we may use the variable to test whether niter iterations
3679 elapsed. This is the case iff the period of the induction variable is
3680 greater than the number of iterations. */
3681 period = iv_period (cand->iv);
3684 per_type = TREE_TYPE (period);
3686 wider_type = TREE_TYPE (period);
3687 if (TYPE_PRECISION (nit_type) < TYPE_PRECISION (per_type))
3688 wider_type = per_type;
3690 wider_type = nit_type;
3692 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
3693 fold_convert (wider_type, period),
3694 fold_convert (wider_type, nit))))
3697 *bound = fold_affine_expr (cand_value_at (loop, cand, use->stmt, nit));
3701 /* Determines cost of basing replacement of USE on CAND in a condition. */
3704 determine_use_iv_cost_condition (struct ivopts_data *data,
3705 struct iv_use *use, struct iv_cand *cand)
3707 tree bound = NULL_TREE, op, cond;
3708 bitmap depends_on = NULL;
3711 /* Only consider real candidates. */
3714 set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE);
3718 if (may_eliminate_iv (data, use, cand, &bound))
3720 cost = force_var_cost (data, bound, &depends_on);
3722 set_use_iv_cost (data, use, cand, cost, depends_on, bound);
3723 return cost != INFTY;
3726 /* The induction variable elimination failed; just express the original
3727 giv. If it is compared with an invariant, note that we cannot get
3729 cost = get_computation_cost (data, use, cand, false, &depends_on);
3732 if (TREE_CODE (cond) != SSA_NAME)
3734 op = TREE_OPERAND (cond, 0);
3735 if (TREE_CODE (op) == SSA_NAME
3736 && !null_or_integer_zerop (get_iv (data, op)->step))
3737 op = TREE_OPERAND (cond, 1);
3738 if (TREE_CODE (op) == SSA_NAME)
3740 op = get_iv (data, op)->base;
3741 fd_ivopts_data = data;
3742 walk_tree (&op, find_depends, &depends_on, NULL);
3746 set_use_iv_cost (data, use, cand, cost, depends_on, NULL);
3747 return cost != INFTY;
3750 /* Determines cost of basing replacement of USE on CAND. Returns false
3751 if USE cannot be based on CAND. */
3754 determine_use_iv_cost (struct ivopts_data *data,
3755 struct iv_use *use, struct iv_cand *cand)
3759 case USE_NONLINEAR_EXPR:
3760 return determine_use_iv_cost_generic (data, use, cand);
3763 return determine_use_iv_cost_address (data, use, cand);
3766 return determine_use_iv_cost_condition (data, use, cand);
3773 /* Determines costs of basing the use of the iv on an iv candidate. */
3776 determine_use_iv_costs (struct ivopts_data *data)
3780 struct iv_cand *cand;
3781 bitmap to_clear = BITMAP_ALLOC (NULL);
3783 alloc_use_cost_map (data);
3785 for (i = 0; i < n_iv_uses (data); i++)
3787 use = iv_use (data, i);
3789 if (data->consider_all_candidates)
3791 for (j = 0; j < n_iv_cands (data); j++)
3793 cand = iv_cand (data, j);
3794 determine_use_iv_cost (data, use, cand);
3801 EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi)
3803 cand = iv_cand (data, j);
3804 if (!determine_use_iv_cost (data, use, cand))
3805 bitmap_set_bit (to_clear, j);
3808 /* Remove the candidates for that the cost is infinite from
3809 the list of related candidates. */
3810 bitmap_and_compl_into (use->related_cands, to_clear);
3811 bitmap_clear (to_clear);
3815 BITMAP_FREE (to_clear);
3817 if (dump_file && (dump_flags & TDF_DETAILS))
3819 fprintf (dump_file, "Use-candidate costs:\n");
3821 for (i = 0; i < n_iv_uses (data); i++)
3823 use = iv_use (data, i);
3825 fprintf (dump_file, "Use %d:\n", i);
3826 fprintf (dump_file, " cand\tcost\tdepends on\n");
3827 for (j = 0; j < use->n_map_members; j++)
3829 if (!use->cost_map[j].cand
3830 || use->cost_map[j].cost == INFTY)
3833 fprintf (dump_file, " %d\t%d\t",
3834 use->cost_map[j].cand->id,
3835 use->cost_map[j].cost);
3836 if (use->cost_map[j].depends_on)
3837 bitmap_print (dump_file,
3838 use->cost_map[j].depends_on, "","");
3839 fprintf (dump_file, "\n");
3842 fprintf (dump_file, "\n");
3844 fprintf (dump_file, "\n");
3848 /* Determines cost of the candidate CAND. */
3851 determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
3853 unsigned cost_base, cost_step;
3862 /* There are two costs associated with the candidate -- its increment
3863 and its initialization. The second is almost negligible for any loop
3864 that rolls enough, so we take it just very little into account. */
3866 base = cand->iv->base;
3867 cost_base = force_var_cost (data, base, NULL);
3868 cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
3870 cand->cost = cost_step + cost_base / AVG_LOOP_NITER (current_loop);
3872 /* Prefer the original iv unless we may gain something by replacing it;
3873 this is not really relevant for artificial ivs created by other
3875 if (cand->pos == IP_ORIGINAL
3876 && !DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
3879 /* Prefer not to insert statements into latch unless there are some
3880 already (so that we do not create unnecessary jumps). */
3881 if (cand->pos == IP_END
3882 && empty_block_p (ip_end_pos (data->current_loop)))
3886 /* Determines costs of computation of the candidates. */
3889 determine_iv_costs (struct ivopts_data *data)
3893 if (dump_file && (dump_flags & TDF_DETAILS))
3895 fprintf (dump_file, "Candidate costs:\n");
3896 fprintf (dump_file, " cand\tcost\n");
3899 for (i = 0; i < n_iv_cands (data); i++)
3901 struct iv_cand *cand = iv_cand (data, i);
3903 determine_iv_cost (data, cand);
3905 if (dump_file && (dump_flags & TDF_DETAILS))
3906 fprintf (dump_file, " %d\t%d\n", i, cand->cost);
3909 if (dump_file && (dump_flags & TDF_DETAILS))
3910 fprintf (dump_file, "\n");
3913 /* Calculates cost for having SIZE induction variables. */
3916 ivopts_global_cost_for_size (struct ivopts_data *data, unsigned size)
3918 return global_cost_for_size (size, data->regs_used, n_iv_uses (data));
3921 /* For each size of the induction variable set determine the penalty. */
3924 determine_set_costs (struct ivopts_data *data)
3928 struct loop *loop = data->current_loop;
3931 /* We use the following model (definitely improvable, especially the
3932 cost function -- TODO):
3934 We estimate the number of registers available (using MD data), name it A.
3936 We estimate the number of registers used by the loop, name it U. This
3937 number is obtained as the number of loop phi nodes (not counting virtual
3938 registers and bivs) + the number of variables from outside of the loop.
3940 We set a reserve R (free regs that are used for temporary computations,
3941 etc.). For now the reserve is a constant 3.
3943 Let I be the number of induction variables.
3945 -- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
3946 make a lot of ivs without a reason).
3947 -- if A - R < U + I <= A, the cost is I * PRES_COST
3948 -- if U + I > A, the cost is I * PRES_COST and
3949 number of uses * SPILL_COST * (U + I - A) / (U + I) is added. */
3951 if (dump_file && (dump_flags & TDF_DETAILS))
3953 fprintf (dump_file, "Global costs:\n");
3954 fprintf (dump_file, " target_avail_regs %d\n", target_avail_regs);
3955 fprintf (dump_file, " target_small_cost %d\n", target_small_cost);
3956 fprintf (dump_file, " target_pres_cost %d\n", target_pres_cost);
3957 fprintf (dump_file, " target_spill_cost %d\n", target_spill_cost);
3961 for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
3963 op = PHI_RESULT (phi);
3965 if (!is_gimple_reg (op))
3968 if (get_iv (data, op))
3974 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
3976 struct version_info *info = ver_info (data, j);
3978 if (info->inv_id && info->has_nonlin_use)
3982 data->regs_used = n;
3983 if (dump_file && (dump_flags & TDF_DETAILS))
3984 fprintf (dump_file, " regs_used %d\n", n);
3986 if (dump_file && (dump_flags & TDF_DETAILS))
3988 fprintf (dump_file, " cost for size:\n");
3989 fprintf (dump_file, " ivs\tcost\n");
3990 for (j = 0; j <= 2 * target_avail_regs; j++)
3991 fprintf (dump_file, " %d\t%d\n", j,
3992 ivopts_global_cost_for_size (data, j));
3993 fprintf (dump_file, "\n");
3997 /* Returns true if A is a cheaper cost pair than B. */
4000 cheaper_cost_pair (struct cost_pair *a, struct cost_pair *b)
4008 if (a->cost < b->cost)
4011 if (a->cost > b->cost)
4014 /* In case the costs are the same, prefer the cheaper candidate. */
4015 if (a->cand->cost < b->cand->cost)
4021 /* Computes the cost field of IVS structure. */
4024 iv_ca_recount_cost (struct ivopts_data *data, struct iv_ca *ivs)
4028 cost += ivs->cand_use_cost;
4029 cost += ivs->cand_cost;
4030 cost += ivopts_global_cost_for_size (data, ivs->n_regs);
4035 /* Remove invariants in set INVS to set IVS. */
4038 iv_ca_set_remove_invariants (struct iv_ca *ivs, bitmap invs)
4046 EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
4048 ivs->n_invariant_uses[iid]--;
4049 if (ivs->n_invariant_uses[iid] == 0)
4054 /* Set USE not to be expressed by any candidate in IVS. */
4057 iv_ca_set_no_cp (struct ivopts_data *data, struct iv_ca *ivs,
4060 unsigned uid = use->id, cid;
4061 struct cost_pair *cp;
4063 cp = ivs->cand_for_use[uid];
4069 ivs->cand_for_use[uid] = NULL;
4070 ivs->n_cand_uses[cid]--;
4072 if (ivs->n_cand_uses[cid] == 0)
4074 bitmap_clear_bit (ivs->cands, cid);
4075 /* Do not count the pseudocandidates. */
4079 ivs->cand_cost -= cp->cand->cost;
4081 iv_ca_set_remove_invariants (ivs, cp->cand->depends_on);
4084 ivs->cand_use_cost -= cp->cost;
4086 iv_ca_set_remove_invariants (ivs, cp->depends_on);
4087 iv_ca_recount_cost (data, ivs);
4090 /* Add invariants in set INVS to set IVS. */
4093 iv_ca_set_add_invariants (struct iv_ca *ivs, bitmap invs)
4101 EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
4103 ivs->n_invariant_uses[iid]++;
4104 if (ivs->n_invariant_uses[iid] == 1)
4109 /* Set cost pair for USE in set IVS to CP. */
4112 iv_ca_set_cp (struct ivopts_data *data, struct iv_ca *ivs,
4113 struct iv_use *use, struct cost_pair *cp)
4115 unsigned uid = use->id, cid;
4117 if (ivs->cand_for_use[uid] == cp)
4120 if (ivs->cand_for_use[uid])
4121 iv_ca_set_no_cp (data, ivs, use);
4128 ivs->cand_for_use[uid] = cp;
4129 ivs->n_cand_uses[cid]++;
4130 if (ivs->n_cand_uses[cid] == 1)
4132 bitmap_set_bit (ivs->cands, cid);
4133 /* Do not count the pseudocandidates. */
4137 ivs->cand_cost += cp->cand->cost;
4139 iv_ca_set_add_invariants (ivs, cp->cand->depends_on);
4142 ivs->cand_use_cost += cp->cost;
4143 iv_ca_set_add_invariants (ivs, cp->depends_on);
4144 iv_ca_recount_cost (data, ivs);
4148 /* Extend set IVS by expressing USE by some of the candidates in it
4152 iv_ca_add_use (struct ivopts_data *data, struct iv_ca *ivs,
4155 struct cost_pair *best_cp = NULL, *cp;
4159 gcc_assert (ivs->upto >= use->id);
4161 if (ivs->upto == use->id)
4167 EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
4169 cp = get_use_iv_cost (data, use, iv_cand (data, i));
4171 if (cheaper_cost_pair (cp, best_cp))
4175 iv_ca_set_cp (data, ivs, use, best_cp);
4178 /* Get cost for assignment IVS. */
4181 iv_ca_cost (struct iv_ca *ivs)
4183 return (ivs->bad_uses ? INFTY : ivs->cost);
4186 /* Returns true if all dependences of CP are among invariants in IVS. */
4189 iv_ca_has_deps (struct iv_ca *ivs, struct cost_pair *cp)
4194 if (!cp->depends_on)
4197 EXECUTE_IF_SET_IN_BITMAP (cp->depends_on, 0, i, bi)
4199 if (ivs->n_invariant_uses[i] == 0)
4206 /* Creates change of expressing USE by NEW_CP instead of OLD_CP and chains
4207 it before NEXT_CHANGE. */
4209 static struct iv_ca_delta *
4210 iv_ca_delta_add (struct iv_use *use, struct cost_pair *old_cp,
4211 struct cost_pair *new_cp, struct iv_ca_delta *next_change)
4213 struct iv_ca_delta *change = XNEW (struct iv_ca_delta);
4216 change->old_cp = old_cp;
4217 change->new_cp = new_cp;
4218 change->next_change = next_change;
4223 /* Joins two lists of changes L1 and L2. Destructive -- old lists
4226 static struct iv_ca_delta *
4227 iv_ca_delta_join (struct iv_ca_delta *l1, struct iv_ca_delta *l2)
4229 struct iv_ca_delta *last;
4237 for (last = l1; last->next_change; last = last->next_change)
4239 last->next_change = l2;
4244 /* Returns candidate by that USE is expressed in IVS. */
4246 static struct cost_pair *
4247 iv_ca_cand_for_use (struct iv_ca *ivs, struct iv_use *use)
4249 return ivs->cand_for_use[use->id];
4252 /* Reverse the list of changes DELTA, forming the inverse to it. */
4254 static struct iv_ca_delta *
4255 iv_ca_delta_reverse (struct iv_ca_delta *delta)
4257 struct iv_ca_delta *act, *next, *prev = NULL;
4258 struct cost_pair *tmp;
4260 for (act = delta; act; act = next)
4262 next = act->next_change;
4263 act->next_change = prev;
4267 act->old_cp = act->new_cp;
4274 /* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
4275 reverted instead. */
4278 iv_ca_delta_commit (struct ivopts_data *data, struct iv_ca *ivs,
4279 struct iv_ca_delta *delta, bool forward)
4281 struct cost_pair *from, *to;
4282 struct iv_ca_delta *act;
4285 delta = iv_ca_delta_reverse (delta);
4287 for (act = delta; act; act = act->next_change)
4291 gcc_assert (iv_ca_cand_for_use (ivs, act->use) == from);
4292 iv_ca_set_cp (data, ivs, act->use, to);
4296 iv_ca_delta_reverse (delta);
4299 /* Returns true if CAND is used in IVS. */
4302 iv_ca_cand_used_p (struct iv_ca *ivs, struct iv_cand *cand)
4304 return ivs->n_cand_uses[cand->id] > 0;
4307 /* Returns number of induction variable candidates in the set IVS. */
4310 iv_ca_n_cands (struct iv_ca *ivs)
4312 return ivs->n_cands;
4315 /* Free the list of changes DELTA. */
4318 iv_ca_delta_free (struct iv_ca_delta **delta)
4320 struct iv_ca_delta *act, *next;
4322 for (act = *delta; act; act = next)
4324 next = act->next_change;
4331 /* Allocates new iv candidates assignment. */
4333 static struct iv_ca *
4334 iv_ca_new (struct ivopts_data *data)
4336 struct iv_ca *nw = XNEW (struct iv_ca);
4340 nw->cand_for_use = XCNEWVEC (struct cost_pair *, n_iv_uses (data));
4341 nw->n_cand_uses = XCNEWVEC (unsigned, n_iv_cands (data));
4342 nw->cands = BITMAP_ALLOC (NULL);
4345 nw->cand_use_cost = 0;
4347 nw->n_invariant_uses = XCNEWVEC (unsigned, data->max_inv_id + 1);
4353 /* Free memory occupied by the set IVS. */
4356 iv_ca_free (struct iv_ca **ivs)
4358 free ((*ivs)->cand_for_use);
4359 free ((*ivs)->n_cand_uses);
4360 BITMAP_FREE ((*ivs)->cands);
4361 free ((*ivs)->n_invariant_uses);
4366 /* Dumps IVS to FILE. */
4369 iv_ca_dump (struct ivopts_data *data, FILE *file, struct iv_ca *ivs)
4371 const char *pref = " invariants ";
4374 fprintf (file, " cost %d\n", iv_ca_cost (ivs));
4375 bitmap_print (file, ivs->cands, " candidates ","\n");
4377 for (i = 1; i <= data->max_inv_id; i++)
4378 if (ivs->n_invariant_uses[i])
4380 fprintf (file, "%s%d", pref, i);
4383 fprintf (file, "\n");
4386 /* Try changing candidate in IVS to CAND for each use. Return cost of the
4387 new set, and store differences in DELTA. Number of induction variables
4388 in the new set is stored to N_IVS. */
4391 iv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs,
4392 struct iv_cand *cand, struct iv_ca_delta **delta,
4397 struct cost_pair *old_cp, *new_cp;
4400 for (i = 0; i < ivs->upto; i++)
4402 use = iv_use (data, i);
4403 old_cp = iv_ca_cand_for_use (ivs, use);
4406 && old_cp->cand == cand)
4409 new_cp = get_use_iv_cost (data, use, cand);
4413 if (!iv_ca_has_deps (ivs, new_cp))
4416 if (!cheaper_cost_pair (new_cp, old_cp))
4419 *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
4422 iv_ca_delta_commit (data, ivs, *delta, true);
4423 cost = iv_ca_cost (ivs);
4425 *n_ivs = iv_ca_n_cands (ivs);
4426 iv_ca_delta_commit (data, ivs, *delta, false);
4431 /* Try narrowing set IVS by removing CAND. Return the cost of
4432 the new set and store the differences in DELTA. */
4435 iv_ca_narrow (struct ivopts_data *data, struct iv_ca *ivs,
4436 struct iv_cand *cand, struct iv_ca_delta **delta)
4440 struct cost_pair *old_cp, *new_cp, *cp;
4442 struct iv_cand *cnd;
4446 for (i = 0; i < n_iv_uses (data); i++)
4448 use = iv_use (data, i);
4450 old_cp = iv_ca_cand_for_use (ivs, use);
4451 if (old_cp->cand != cand)
4456 if (data->consider_all_candidates)
4458 EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, ci, bi)
4463 cnd = iv_cand (data, ci);
4465 cp = get_use_iv_cost (data, use, cnd);
4468 if (!iv_ca_has_deps (ivs, cp))
4471 if (!cheaper_cost_pair (cp, new_cp))
4479 EXECUTE_IF_AND_IN_BITMAP (use->related_cands, ivs->cands, 0, ci, bi)
4484 cnd = iv_cand (data, ci);
4486 cp = get_use_iv_cost (data, use, cnd);
4489 if (!iv_ca_has_deps (ivs, cp))
4492 if (!cheaper_cost_pair (cp, new_cp))
4501 iv_ca_delta_free (delta);
4505 *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
4508 iv_ca_delta_commit (data, ivs, *delta, true);
4509 cost = iv_ca_cost (ivs);
4510 iv_ca_delta_commit (data, ivs, *delta, false);
4515 /* Try optimizing the set of candidates IVS by removing candidates different
4516 from to EXCEPT_CAND from it. Return cost of the new set, and store
4517 differences in DELTA. */
4520 iv_ca_prune (struct ivopts_data *data, struct iv_ca *ivs,
4521 struct iv_cand *except_cand, struct iv_ca_delta **delta)
4524 struct iv_ca_delta *act_delta, *best_delta;
4525 unsigned i, best_cost, acost;
4526 struct iv_cand *cand;
4529 best_cost = iv_ca_cost (ivs);
4531 EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
4533 cand = iv_cand (data, i);
4535 if (cand == except_cand)
4538 acost = iv_ca_narrow (data, ivs, cand, &act_delta);
4540 if (acost < best_cost)
4543 iv_ca_delta_free (&best_delta);
4544 best_delta = act_delta;
4547 iv_ca_delta_free (&act_delta);
4556 /* Recurse to possibly remove other unnecessary ivs. */
4557 iv_ca_delta_commit (data, ivs, best_delta, true);
4558 best_cost = iv_ca_prune (data, ivs, except_cand, delta);
4559 iv_ca_delta_commit (data, ivs, best_delta, false);
4560 *delta = iv_ca_delta_join (best_delta, *delta);
4564 /* Tries to extend the sets IVS in the best possible way in order
4565 to express the USE. */
4568 try_add_cand_for (struct ivopts_data *data, struct iv_ca *ivs,
4571 unsigned best_cost, act_cost;
4574 struct iv_cand *cand;
4575 struct iv_ca_delta *best_delta = NULL, *act_delta;
4576 struct cost_pair *cp;
4578 iv_ca_add_use (data, ivs, use);
4579 best_cost = iv_ca_cost (ivs);
4581 cp = iv_ca_cand_for_use (ivs, use);
4584 best_delta = iv_ca_delta_add (use, NULL, cp, NULL);
4585 iv_ca_set_no_cp (data, ivs, use);
4588 /* First try important candidates. Only if it fails, try the specific ones.
4589 Rationale -- in loops with many variables the best choice often is to use
4590 just one generic biv. If we added here many ivs specific to the uses,
4591 the optimization algorithm later would be likely to get stuck in a local
4592 minimum, thus causing us to create too many ivs. The approach from
4593 few ivs to more seems more likely to be successful -- starting from few
4594 ivs, replacing an expensive use by a specific iv should always be a
4596 EXECUTE_IF_SET_IN_BITMAP (data->important_candidates, 0, i, bi)
4598 cand = iv_cand (data, i);
4600 if (iv_ca_cand_used_p (ivs, cand))
4603 cp = get_use_iv_cost (data, use, cand);
4607 iv_ca_set_cp (data, ivs, use, cp);
4608 act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
4609 iv_ca_set_no_cp (data, ivs, use);
4610 act_delta = iv_ca_delta_add (use, NULL, cp, act_delta);
4612 if (act_cost < best_cost)
4614 best_cost = act_cost;
4616 iv_ca_delta_free (&best_delta);
4617 best_delta = act_delta;
4620 iv_ca_delta_free (&act_delta);
4623 if (best_cost == INFTY)
4625 for (i = 0; i < use->n_map_members; i++)
4627 cp = use->cost_map + i;
4632 /* Already tried this. */
4633 if (cand->important)
4636 if (iv_ca_cand_used_p (ivs, cand))
4640 iv_ca_set_cp (data, ivs, use, cp);
4641 act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
4642 iv_ca_set_no_cp (data, ivs, use);
4643 act_delta = iv_ca_delta_add (use, iv_ca_cand_for_use (ivs, use),
4646 if (act_cost < best_cost)
4648 best_cost = act_cost;
4651 iv_ca_delta_free (&best_delta);
4652 best_delta = act_delta;
4655 iv_ca_delta_free (&act_delta);
4659 iv_ca_delta_commit (data, ivs, best_delta, true);
4660 iv_ca_delta_free (&best_delta);
4662 return (best_cost != INFTY);
4665 /* Finds an initial assignment of candidates to uses. */
4667 static struct iv_ca *
4668 get_initial_solution (struct ivopts_data *data)
4670 struct iv_ca *ivs = iv_ca_new (data);
4673 for (i = 0; i < n_iv_uses (data); i++)
4674 if (!try_add_cand_for (data, ivs, iv_use (data, i)))
4683 /* Tries to improve set of induction variables IVS. */
4686 try_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs)
4688 unsigned i, acost, best_cost = iv_ca_cost (ivs), n_ivs;
4689 struct iv_ca_delta *best_delta = NULL, *act_delta, *tmp_delta;
4690 struct iv_cand *cand;
4692 /* Try extending the set of induction variables by one. */
4693 for (i = 0; i < n_iv_cands (data); i++)
4695 cand = iv_cand (data, i);
4697 if (iv_ca_cand_used_p (ivs, cand))
4700 acost = iv_ca_extend (data, ivs, cand, &act_delta, &n_ivs);
4704 /* If we successfully added the candidate and the set is small enough,
4705 try optimizing it by removing other candidates. */
4706 if (n_ivs <= ALWAYS_PRUNE_CAND_SET_BOUND)
4708 iv_ca_delta_commit (data, ivs, act_delta, true);
4709 acost = iv_ca_prune (data, ivs, cand, &tmp_delta);
4710 iv_ca_delta_commit (data, ivs, act_delta, false);
4711 act_delta = iv_ca_delta_join (act_delta, tmp_delta);
4714 if (acost < best_cost)
4717 iv_ca_delta_free (&best_delta);
4718 best_delta = act_delta;
4721 iv_ca_delta_free (&act_delta);
4726 /* Try removing the candidates from the set instead. */
4727 best_cost = iv_ca_prune (data, ivs, NULL, &best_delta);
4729 /* Nothing more we can do. */
4734 iv_ca_delta_commit (data, ivs, best_delta, true);
4735 gcc_assert (best_cost == iv_ca_cost (ivs));
4736 iv_ca_delta_free (&best_delta);
4740 /* Attempts to find the optimal set of induction variables. We do simple
4741 greedy heuristic -- we try to replace at most one candidate in the selected
4742 solution and remove the unused ivs while this improves the cost. */
4744 static struct iv_ca *
4745 find_optimal_iv_set (struct ivopts_data *data)
4751 /* Get the initial solution. */
4752 set = get_initial_solution (data);
4755 if (dump_file && (dump_flags & TDF_DETAILS))
4756 fprintf (dump_file, "Unable to substitute for ivs, failed.\n");
4760 if (dump_file && (dump_flags & TDF_DETAILS))
4762 fprintf (dump_file, "Initial set of candidates:\n");
4763 iv_ca_dump (data, dump_file, set);
4766 while (try_improve_iv_set (data, set))
4768 if (dump_file && (dump_flags & TDF_DETAILS))
4770 fprintf (dump_file, "Improved to:\n");
4771 iv_ca_dump (data, dump_file, set);
4775 if (dump_file && (dump_flags & TDF_DETAILS))
4776 fprintf (dump_file, "Final cost %d\n\n", iv_ca_cost (set));
4778 for (i = 0; i < n_iv_uses (data); i++)
4780 use = iv_use (data, i);
4781 use->selected = iv_ca_cand_for_use (set, use)->cand;
4787 /* Creates a new induction variable corresponding to CAND. */
4790 create_new_iv (struct ivopts_data *data, struct iv_cand *cand)
4792 block_stmt_iterator incr_pos;
4802 incr_pos = bsi_last (ip_normal_pos (data->current_loop));
4806 incr_pos = bsi_last (ip_end_pos (data->current_loop));
4811 /* Mark that the iv is preserved. */
4812 name_info (data, cand->var_before)->preserve_biv = true;
4813 name_info (data, cand->var_after)->preserve_biv = true;
4815 /* Rewrite the increment so that it uses var_before directly. */
4816 find_interesting_uses_op (data, cand->var_after)->selected = cand;
4821 gimple_add_tmp_var (cand->var_before);
4822 add_referenced_var (cand->var_before);
4824 base = unshare_expr (cand->iv->base);
4826 create_iv (base, unshare_expr (cand->iv->step),
4827 cand->var_before, data->current_loop,
4828 &incr_pos, after, &cand->var_before, &cand->var_after);
4831 /* Creates new induction variables described in SET. */
4834 create_new_ivs (struct ivopts_data *data, struct iv_ca *set)
4837 struct iv_cand *cand;
4840 EXECUTE_IF_SET_IN_BITMAP (set->cands, 0, i, bi)
4842 cand = iv_cand (data, i);
4843 create_new_iv (data, cand);
4847 /* Removes statement STMT (real or a phi node). If INCLUDING_DEFINED_NAME
4848 is true, remove also the ssa name defined by the statement. */
4851 remove_statement (tree stmt, bool including_defined_name)
4853 if (TREE_CODE (stmt) == PHI_NODE)
4855 remove_phi_node (stmt, NULL_TREE, including_defined_name);
4859 block_stmt_iterator bsi = bsi_for_stmt (stmt);
4861 bsi_remove (&bsi, true);
4865 /* Rewrites USE (definition of iv used in a nonlinear expression)
4866 using candidate CAND. */
4869 rewrite_use_nonlinear_expr (struct ivopts_data *data,
4870 struct iv_use *use, struct iv_cand *cand)
4873 tree op, stmts, tgt, ass;
4874 block_stmt_iterator bsi, pbsi;
4876 /* An important special case -- if we are asked to express value of
4877 the original iv by itself, just exit; there is no need to
4878 introduce a new computation (that might also need casting the
4879 variable to unsigned and back). */
4880 if (cand->pos == IP_ORIGINAL
4881 && cand->incremented_at == use->stmt)
4883 tree step, ctype, utype;
4884 enum tree_code incr_code = PLUS_EXPR;
4886 gcc_assert (TREE_CODE (use->stmt) == GIMPLE_MODIFY_STMT);
4887 gcc_assert (GIMPLE_STMT_OPERAND (use->stmt, 0) == cand->var_after);
4889 step = cand->iv->step;
4890 ctype = TREE_TYPE (step);
4891 utype = TREE_TYPE (cand->var_after);
4892 if (TREE_CODE (step) == NEGATE_EXPR)
4894 incr_code = MINUS_EXPR;
4895 step = TREE_OPERAND (step, 0);
4898 /* Check whether we may leave the computation unchanged.
4899 This is the case only if it does not rely on other
4900 computations in the loop -- otherwise, the computation
4901 we rely upon may be removed in remove_unused_ivs,
4902 thus leading to ICE. */
4903 op = GIMPLE_STMT_OPERAND (use->stmt, 1);
4904 if (TREE_CODE (op) == PLUS_EXPR
4905 || TREE_CODE (op) == MINUS_EXPR)
4907 if (TREE_OPERAND (op, 0) == cand->var_before)
4908 op = TREE_OPERAND (op, 1);
4909 else if (TREE_CODE (op) == PLUS_EXPR
4910 && TREE_OPERAND (op, 1) == cand->var_before)
4911 op = TREE_OPERAND (op, 0);
4919 && (TREE_CODE (op) == INTEGER_CST
4920 || operand_equal_p (op, step, 0)))
4923 /* Otherwise, add the necessary computations to express
4925 op = fold_convert (ctype, cand->var_before);
4926 comp = fold_convert (utype,
4927 build2 (incr_code, ctype, op,
4928 unshare_expr (step)));
4932 comp = get_computation (data->current_loop, use, cand);
4933 gcc_assert (comp != NULL_TREE);
4936 switch (TREE_CODE (use->stmt))
4939 tgt = PHI_RESULT (use->stmt);
4941 /* If we should keep the biv, do not replace it. */
4942 if (name_info (data, tgt)->preserve_biv)
4945 pbsi = bsi = bsi_start (bb_for_stmt (use->stmt));
4946 while (!bsi_end_p (pbsi)
4947 && TREE_CODE (bsi_stmt (pbsi)) == LABEL_EXPR)
4954 case GIMPLE_MODIFY_STMT:
4955 tgt = GIMPLE_STMT_OPERAND (use->stmt, 0);
4956 bsi = bsi_for_stmt (use->stmt);
4963 op = force_gimple_operand (comp, &stmts, false, SSA_NAME_VAR (tgt));
4965 if (TREE_CODE (use->stmt) == PHI_NODE)
4968 bsi_insert_after (&bsi, stmts, BSI_CONTINUE_LINKING);
4969 ass = build2_gimple (GIMPLE_MODIFY_STMT, tgt, op);
4970 bsi_insert_after (&bsi, ass, BSI_NEW_STMT);
4971 remove_statement (use->stmt, false);
4972 SSA_NAME_DEF_STMT (tgt) = ass;
4977 bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
4978 GIMPLE_STMT_OPERAND (use->stmt, 1) = op;
4982 /* Replaces ssa name in index IDX by its basic variable. Callback for
4986 idx_remove_ssa_names (tree base, tree *idx,
4987 void *data ATTRIBUTE_UNUSED)
4991 if (TREE_CODE (*idx) == SSA_NAME)
4992 *idx = SSA_NAME_VAR (*idx);
4994 if (TREE_CODE (base) == ARRAY_REF)
4996 op = &TREE_OPERAND (base, 2);
4998 && TREE_CODE (*op) == SSA_NAME)
4999 *op = SSA_NAME_VAR (*op);
5000 op = &TREE_OPERAND (base, 3);
5002 && TREE_CODE (*op) == SSA_NAME)
5003 *op = SSA_NAME_VAR (*op);
5009 /* Unshares REF and replaces ssa names inside it by their basic variables. */
5012 unshare_and_remove_ssa_names (tree ref)
5014 ref = unshare_expr (ref);
5015 for_each_index (&ref, idx_remove_ssa_names, NULL);
5020 /* Extract the alias analysis info for the memory reference REF. There are
5021 several ways how this information may be stored and what precisely is
5022 its semantics depending on the type of the reference, but there always is
5023 somewhere hidden one _DECL node that is used to determine the set of
5024 virtual operands for the reference. The code below deciphers this jungle
5025 and extracts this single useful piece of information. */
5028 get_ref_tag (tree ref, tree orig)
5030 tree var = get_base_address (ref);
5031 tree aref = NULL_TREE, tag, sv;
5032 HOST_WIDE_INT offset, size, maxsize;
5034 for (sv = orig; handled_component_p (sv); sv = TREE_OPERAND (sv, 0))
5036 aref = get_ref_base_and_extent (sv, &offset, &size, &maxsize);
5041 if (aref && SSA_VAR_P (aref) && get_subvars_for_var (aref))
5042 return unshare_expr (sv);
5047 if (TREE_CODE (var) == INDIRECT_REF)
5049 /* If the base is a dereference of a pointer, first check its name memory
5050 tag. If it does not have one, use its symbol memory tag. */
5051 var = TREE_OPERAND (var, 0);
5052 if (TREE_CODE (var) != SSA_NAME)
5055 if (SSA_NAME_PTR_INFO (var))
5057 tag = SSA_NAME_PTR_INFO (var)->name_mem_tag;
5062 var = SSA_NAME_VAR (var);
5063 tag = symbol_mem_tag (var);
5064 gcc_assert (tag != NULL_TREE);
5072 tag = symbol_mem_tag (var);
5080 /* Copies the reference information from OLD_REF to NEW_REF. */
5083 copy_ref_info (tree new_ref, tree old_ref)
5085 if (TREE_CODE (old_ref) == TARGET_MEM_REF)
5086 copy_mem_ref_info (new_ref, old_ref);
5089 TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
5090 TMR_TAG (new_ref) = get_ref_tag (old_ref, TMR_ORIGINAL (new_ref));
5094 /* Rewrites USE (address that is an iv) using candidate CAND. */
5097 rewrite_use_address (struct ivopts_data *data,
5098 struct iv_use *use, struct iv_cand *cand)
5101 block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
5105 ok = get_computation_aff (data->current_loop, use, cand, use->stmt, &aff);
5107 unshare_aff_combination (&aff);
5109 ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff);
5110 copy_ref_info (ref, *use->op_p);
5114 /* Rewrites USE (the condition such that one of the arguments is an iv) using
5118 rewrite_use_compare (struct ivopts_data *data,
5119 struct iv_use *use, struct iv_cand *cand)
5122 tree *op_p, cond, op, stmts, bound;
5123 block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
5124 enum tree_code compare;
5125 struct cost_pair *cp = get_use_iv_cost (data, use, cand);
5130 tree var = var_at_stmt (data->current_loop, cand, use->stmt);
5131 tree var_type = TREE_TYPE (var);
5133 compare = iv_elimination_compare (data, use);
5134 bound = fold_convert (var_type, bound);
5135 op = force_gimple_operand (unshare_expr (bound), &stmts,
5139 bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
5141 *use->op_p = build2 (compare, boolean_type_node, var, op);
5142 update_stmt (use->stmt);
5146 /* The induction variable elimination failed; just express the original
5148 comp = get_computation (data->current_loop, use, cand);
5149 gcc_assert (comp != NULL_TREE);
5152 op_p = &TREE_OPERAND (cond, 0);
5153 if (TREE_CODE (*op_p) != SSA_NAME
5154 || null_or_integer_zerop (get_iv (data, *op_p)->step))
5155 op_p = &TREE_OPERAND (cond, 1);
5157 op = force_gimple_operand (comp, &stmts, true, SSA_NAME_VAR (*op_p));
5159 bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
5164 /* Rewrites USE using candidate CAND. */
5167 rewrite_use (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
5169 push_stmt_changes (&use->stmt);
5173 case USE_NONLINEAR_EXPR:
5174 rewrite_use_nonlinear_expr (data, use, cand);
5178 rewrite_use_address (data, use, cand);
5182 rewrite_use_compare (data, use, cand);
5189 pop_stmt_changes (&use->stmt);
5192 /* Rewrite the uses using the selected induction variables. */
5195 rewrite_uses (struct ivopts_data *data)
5198 struct iv_cand *cand;
5201 for (i = 0; i < n_iv_uses (data); i++)
5203 use = iv_use (data, i);
5204 cand = use->selected;
5207 rewrite_use (data, use, cand);
5211 /* Removes the ivs that are not used after rewriting. */
5214 remove_unused_ivs (struct ivopts_data *data)
5219 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
5221 struct version_info *info;
5223 info = ver_info (data, j);
5225 && !null_or_integer_zerop (info->iv->step)
5227 && !info->iv->have_use_for
5228 && !info->preserve_biv)
5229 remove_statement (SSA_NAME_DEF_STMT (info->iv->ssa_name), true);
5233 /* Frees data allocated by the optimization of a single loop. */
5236 free_loop_data (struct ivopts_data *data)
5242 htab_empty (data->niters);
5244 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
5246 struct version_info *info;
5248 info = ver_info (data, i);
5252 info->has_nonlin_use = false;
5253 info->preserve_biv = false;
5256 bitmap_clear (data->relevant);
5257 bitmap_clear (data->important_candidates);
5259 for (i = 0; i < n_iv_uses (data); i++)
5261 struct iv_use *use = iv_use (data, i);
5264 BITMAP_FREE (use->related_cands);
5265 for (j = 0; j < use->n_map_members; j++)
5266 if (use->cost_map[j].depends_on)
5267 BITMAP_FREE (use->cost_map[j].depends_on);
5268 free (use->cost_map);
5271 VEC_truncate (iv_use_p, data->iv_uses, 0);
5273 for (i = 0; i < n_iv_cands (data); i++)
5275 struct iv_cand *cand = iv_cand (data, i);
5279 if (cand->depends_on)
5280 BITMAP_FREE (cand->depends_on);
5283 VEC_truncate (iv_cand_p, data->iv_candidates, 0);
5285 if (data->version_info_size < num_ssa_names)
5287 data->version_info_size = 2 * num_ssa_names;
5288 free (data->version_info);
5289 data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
5292 data->max_inv_id = 0;
5294 for (i = 0; VEC_iterate (tree, decl_rtl_to_reset, i, obj); i++)
5295 SET_DECL_RTL (obj, NULL_RTX);
5297 VEC_truncate (tree, decl_rtl_to_reset, 0);
5300 /* Finalizes data structures used by the iv optimization pass. LOOPS is the
5304 tree_ssa_iv_optimize_finalize (struct ivopts_data *data)
5306 free_loop_data (data);
5307 free (data->version_info);
5308 BITMAP_FREE (data->relevant);
5309 BITMAP_FREE (data->important_candidates);
5310 htab_delete (data->niters);
5312 VEC_free (tree, heap, decl_rtl_to_reset);
5313 VEC_free (iv_use_p, heap, data->iv_uses);
5314 VEC_free (iv_cand_p, heap, data->iv_candidates);
5317 /* Optimizes the LOOP. Returns true if anything changed. */
5320 tree_ssa_iv_optimize_loop (struct ivopts_data *data, struct loop *loop)
5322 bool changed = false;
5323 struct iv_ca *iv_ca;
5326 data->current_loop = loop;
5328 if (dump_file && (dump_flags & TDF_DETAILS))
5330 fprintf (dump_file, "Processing loop %d\n", loop->num);
5332 exit = single_dom_exit (loop);
5335 fprintf (dump_file, " single exit %d -> %d, exit condition ",
5336 exit->src->index, exit->dest->index);
5337 print_generic_expr (dump_file, last_stmt (exit->src), TDF_SLIM);
5338 fprintf (dump_file, "\n");
5341 fprintf (dump_file, "\n");
5344 /* For each ssa name determines whether it behaves as an induction variable
5346 if (!find_induction_variables (data))
5349 /* Finds interesting uses (item 1). */
5350 find_interesting_uses (data);
5351 if (n_iv_uses (data) > MAX_CONSIDERED_USES)
5354 /* Finds candidates for the induction variables (item 2). */
5355 find_iv_candidates (data);
5357 /* Calculates the costs (item 3, part 1). */
5358 determine_use_iv_costs (data);
5359 determine_iv_costs (data);
5360 determine_set_costs (data);
5362 /* Find the optimal set of induction variables (item 3, part 2). */
5363 iv_ca = find_optimal_iv_set (data);
5368 /* Create the new induction variables (item 4, part 1). */
5369 create_new_ivs (data, iv_ca);
5370 iv_ca_free (&iv_ca);
5372 /* Rewrite the uses (item 4, part 2). */
5373 rewrite_uses (data);
5375 /* Remove the ivs that are unused after rewriting. */
5376 remove_unused_ivs (data);
5378 /* We have changed the structure of induction variables; it might happen
5379 that definitions in the scev database refer to some of them that were
5384 free_loop_data (data);
5389 /* Main entry point. Optimizes induction variables in loops. */
5392 tree_ssa_iv_optimize (void)
5395 struct ivopts_data data;
5398 tree_ssa_iv_optimize_init (&data);
5400 /* Optimize the loops starting with the innermost ones. */
5401 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
5403 if (dump_file && (dump_flags & TDF_DETAILS))
5404 flow_loop_dump (loop, dump_file, NULL, 1);
5406 tree_ssa_iv_optimize_loop (&data, loop);
5409 tree_ssa_iv_optimize_finalize (&data);