1 /* Induction variable optimizations.
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
21 /* This pass tries to find the optimal set of induction variables for the loop.
22 It optimizes just the basic linear induction variables (although adding
23 support for other types should not be too hard). It includes the
24 optimizations commonly known as strength reduction, induction variable
25 coalescing and induction variable elimination. It does it in the
28 1) The interesting uses of induction variables are found. This includes
30 -- uses of induction variables in non-linear expressions
31 -- addresses of arrays
32 -- comparisons of induction variables
34 2) Candidates for the induction variables are found. This includes
36 -- old induction variables
37 -- the variables defined by expressions derived from the "interesting
40 3) The optimal (w.r. to a cost function) set of variables is chosen. The
41 cost function assigns a cost to sets of induction variables and consists
44 -- The use costs. Each of the interesting uses chooses the best induction
45 variable in the set and adds its cost to the sum. The cost reflects
46 the time spent on modifying the induction variables value to be usable
47 for the given purpose (adding base and offset for arrays, etc.).
48 -- The variable costs. Each of the variables has a cost assigned that
49 reflects the costs associated with incrementing the value of the
50 variable. The original variables are somewhat preferred.
51 -- The set cost. Depending on the size of the set, extra cost may be
52 added to reflect register pressure.
54 All the costs are defined in a machine-specific way, using the target
55 hooks and machine descriptions to determine them.
57 4) The trees are transformed to use the new variables, the dead code is
60 All of this is done loop by loop. Doing it globally is theoretically
61 possible, it might give a better performance and it might enable us
62 to decide costs more precisely, but getting all the interactions right
63 would be complicated. */
67 #include "coretypes.h"
72 #include "hard-reg-set.h"
73 #include "basic-block.h"
75 #include "diagnostic.h"
76 #include "tree-flow.h"
77 #include "tree-dump.h"
82 #include "tree-pass.h"
84 #include "insn-config.h"
87 #include "tree-chrec.h"
88 #include "tree-scalar-evolution.h"
91 #include "langhooks.h"
93 /* The infinite cost. */
94 #define INFTY 10000000
96 /* The expected number of loop iterations. TODO -- use profiling instead of
98 #define AVG_LOOP_NITER(LOOP) 5
101 /* Representation of the induction variable. */
104 tree base; /* Initial value of the iv. */
105 tree base_object; /* A memory object to that the induction variable points. */
106 tree step; /* Step of the iv (constant only). */
107 tree ssa_name; /* The ssa name with the value. */
108 bool biv_p; /* Is it a biv? */
109 bool have_use_for; /* Do we already have a use for it? */
110 unsigned use_id; /* The identifier in the use if it is the case. */
113 /* Per-ssa version information (induction variable descriptions, etc.). */
116 tree name; /* The ssa name. */
117 struct iv *iv; /* Induction variable description. */
118 bool has_nonlin_use; /* For a loop-level invariant, whether it is used in
119 an expression that is not an induction variable. */
120 unsigned inv_id; /* Id of an invariant. */
121 bool preserve_biv; /* For the original biv, whether to preserve it. */
124 /* Information attached to loop. */
127 unsigned regs_used; /* Number of registers used. */
133 USE_NONLINEAR_EXPR, /* Use in a nonlinear expression. */
134 USE_OUTER, /* The induction variable is used outside the loop. */
135 USE_ADDRESS, /* Use in an address. */
136 USE_COMPARE /* Use is a compare. */
139 /* The candidate - cost pair. */
142 struct iv_cand *cand; /* The candidate. */
143 unsigned cost; /* The cost. */
144 bitmap depends_on; /* The list of invariants that have to be
146 tree value; /* For final value elimination, the expression for
147 the final value of the iv. For iv elimination,
148 the new bound to compare with. */
154 unsigned id; /* The id of the use. */
155 enum use_type type; /* Type of the use. */
156 struct iv *iv; /* The induction variable it is based on. */
157 tree stmt; /* Statement in that it occurs. */
158 tree *op_p; /* The place where it occurs. */
159 bitmap related_cands; /* The set of "related" iv candidates, plus the common
162 unsigned n_map_members; /* Number of candidates in the cost_map list. */
163 struct cost_pair *cost_map;
164 /* The costs wrto the iv candidates. */
166 struct iv_cand *selected;
167 /* The selected candidate. */
170 /* The position where the iv is computed. */
173 IP_NORMAL, /* At the end, just before the exit condition. */
174 IP_END, /* At the end of the latch block. */
175 IP_ORIGINAL /* The original biv. */
178 /* The induction variable candidate. */
181 unsigned id; /* The number of the candidate. */
182 bool important; /* Whether this is an "important" candidate, i.e. such
183 that it should be considered by all uses. */
184 enum iv_position pos; /* Where it is computed. */
185 tree incremented_at; /* For original biv, the statement where it is
187 tree var_before; /* The variable used for it before increment. */
188 tree var_after; /* The variable used for it after increment. */
189 struct iv *iv; /* The value of the candidate. NULL for
190 "pseudocandidate" used to indicate the possibility
191 to replace the final value of an iv by direct
192 computation of the value. */
193 unsigned cost; /* Cost of the candidate. */
194 bitmap depends_on; /* The list of invariants that are used in step of the
198 /* The data used by the induction variable optimizations. */
200 typedef struct iv_use *iv_use_p;
202 DEF_VEC_ALLOC_P(iv_use_p,heap);
204 typedef struct iv_cand *iv_cand_p;
205 DEF_VEC_P(iv_cand_p);
206 DEF_VEC_ALLOC_P(iv_cand_p,heap);
210 /* The currently optimized loop. */
211 struct loop *current_loop;
213 /* Numbers of iterations for all exits of the current loop. */
216 /* The size of version_info array allocated. */
217 unsigned version_info_size;
219 /* The array of information for the ssa names. */
220 struct version_info *version_info;
222 /* The bitmap of indices in version_info whose value was changed. */
225 /* The maximum invariant id. */
228 /* The uses of induction variables. */
229 VEC(iv_use_p,heap) *iv_uses;
231 /* The candidates. */
232 VEC(iv_cand_p,heap) *iv_candidates;
234 /* A bitmap of important candidates. */
235 bitmap important_candidates;
237 /* Whether to consider just related and important candidates when replacing a
239 bool consider_all_candidates;
242 /* An assignment of iv candidates to uses. */
246 /* The number of uses covered by the assignment. */
249 /* Number of uses that cannot be expressed by the candidates in the set. */
252 /* Candidate assigned to a use, together with the related costs. */
253 struct cost_pair **cand_for_use;
255 /* Number of times each candidate is used. */
256 unsigned *n_cand_uses;
258 /* The candidates used. */
261 /* The number of candidates in the set. */
264 /* Total number of registers needed. */
267 /* Total cost of expressing uses. */
268 unsigned cand_use_cost;
270 /* Total cost of candidates. */
273 /* Number of times each invariant is used. */
274 unsigned *n_invariant_uses;
276 /* Total cost of the assignment. */
280 /* Difference of two iv candidate assignments. */
287 /* An old assignment (for rollback purposes). */
288 struct cost_pair *old_cp;
290 /* A new assignment. */
291 struct cost_pair *new_cp;
293 /* Next change in the list. */
294 struct iv_ca_delta *next_change;
297 /* Bound on number of candidates below that all candidates are considered. */
299 #define CONSIDER_ALL_CANDIDATES_BOUND \
300 ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
302 /* If there are more iv occurrences, we just give up (it is quite unlikely that
303 optimizing such a loop would help, and it would take ages). */
305 #define MAX_CONSIDERED_USES \
306 ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
308 /* If there are at most this number of ivs in the set, try removing unnecessary
309 ivs from the set always. */
311 #define ALWAYS_PRUNE_CAND_SET_BOUND \
312 ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
314 /* The list of trees for that the decl_rtl field must be reset is stored
317 static VEC(tree,heap) *decl_rtl_to_reset;
319 /* Number of uses recorded in DATA. */
321 static inline unsigned
322 n_iv_uses (struct ivopts_data *data)
324 return VEC_length (iv_use_p, data->iv_uses);
327 /* Ith use recorded in DATA. */
329 static inline struct iv_use *
330 iv_use (struct ivopts_data *data, unsigned i)
332 return VEC_index (iv_use_p, data->iv_uses, i);
335 /* Number of candidates recorded in DATA. */
337 static inline unsigned
338 n_iv_cands (struct ivopts_data *data)
340 return VEC_length (iv_cand_p, data->iv_candidates);
343 /* Ith candidate recorded in DATA. */
345 static inline struct iv_cand *
346 iv_cand (struct ivopts_data *data, unsigned i)
348 return VEC_index (iv_cand_p, data->iv_candidates, i);
351 /* The data for LOOP. */
353 static inline struct loop_data *
354 loop_data (struct loop *loop)
359 /* The single loop exit if it dominates the latch, NULL otherwise. */
362 single_dom_exit (struct loop *loop)
364 edge exit = loop->single_exit;
369 if (!just_once_each_iteration_p (loop, exit->src))
375 /* Dumps information about the induction variable IV to FILE. */
377 extern void dump_iv (FILE *, struct iv *);
379 dump_iv (FILE *file, struct iv *iv)
383 fprintf (file, "ssa name ");
384 print_generic_expr (file, iv->ssa_name, TDF_SLIM);
385 fprintf (file, "\n");
388 fprintf (file, " type ");
389 print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
390 fprintf (file, "\n");
394 fprintf (file, " base ");
395 print_generic_expr (file, iv->base, TDF_SLIM);
396 fprintf (file, "\n");
398 fprintf (file, " step ");
399 print_generic_expr (file, iv->step, TDF_SLIM);
400 fprintf (file, "\n");
404 fprintf (file, " invariant ");
405 print_generic_expr (file, iv->base, TDF_SLIM);
406 fprintf (file, "\n");
411 fprintf (file, " base object ");
412 print_generic_expr (file, iv->base_object, TDF_SLIM);
413 fprintf (file, "\n");
417 fprintf (file, " is a biv\n");
420 /* Dumps information about the USE to FILE. */
422 extern void dump_use (FILE *, struct iv_use *);
424 dump_use (FILE *file, struct iv_use *use)
426 fprintf (file, "use %d\n", use->id);
430 case USE_NONLINEAR_EXPR:
431 fprintf (file, " generic\n");
435 fprintf (file, " outside\n");
439 fprintf (file, " address\n");
443 fprintf (file, " compare\n");
450 fprintf (file, " in statement ");
451 print_generic_expr (file, use->stmt, TDF_SLIM);
452 fprintf (file, "\n");
454 fprintf (file, " at position ");
456 print_generic_expr (file, *use->op_p, TDF_SLIM);
457 fprintf (file, "\n");
459 dump_iv (file, use->iv);
461 if (use->related_cands)
463 fprintf (file, " related candidates ");
464 dump_bitmap (file, use->related_cands);
468 /* Dumps information about the uses to FILE. */
470 extern void dump_uses (FILE *, struct ivopts_data *);
472 dump_uses (FILE *file, struct ivopts_data *data)
477 for (i = 0; i < n_iv_uses (data); i++)
479 use = iv_use (data, i);
481 dump_use (file, use);
482 fprintf (file, "\n");
486 /* Dumps information about induction variable candidate CAND to FILE. */
488 extern void dump_cand (FILE *, struct iv_cand *);
490 dump_cand (FILE *file, struct iv_cand *cand)
492 struct iv *iv = cand->iv;
494 fprintf (file, "candidate %d%s\n",
495 cand->id, cand->important ? " (important)" : "");
497 if (cand->depends_on)
499 fprintf (file, " depends on ");
500 dump_bitmap (file, cand->depends_on);
505 fprintf (file, " final value replacement\n");
512 fprintf (file, " incremented before exit test\n");
516 fprintf (file, " incremented at end\n");
520 fprintf (file, " original biv\n");
527 /* Returns the info for ssa version VER. */
529 static inline struct version_info *
530 ver_info (struct ivopts_data *data, unsigned ver)
532 return data->version_info + ver;
535 /* Returns the info for ssa name NAME. */
537 static inline struct version_info *
538 name_info (struct ivopts_data *data, tree name)
540 return ver_info (data, SSA_NAME_VERSION (name));
543 /* Checks whether there exists number X such that X * B = A, counting modulo
547 divide (unsigned bits, unsigned HOST_WIDE_INT a, unsigned HOST_WIDE_INT b,
550 unsigned HOST_WIDE_INT mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
551 unsigned HOST_WIDE_INT inv, ex, val;
557 /* First divide the whole equation by 2 as long as possible. */
558 while (!(a & 1) && !(b & 1))
568 /* If b is still even, a is odd and there is no such x. */
572 /* Find the inverse of b. We compute it as
573 b^(2^(bits - 1) - 1) (mod 2^bits). */
576 for (i = 0; i < bits - 1; i++)
578 inv = (inv * ex) & mask;
579 ex = (ex * ex) & mask;
582 val = (a * inv) & mask;
584 gcc_assert (((val * b) & mask) == a);
586 if ((val >> (bits - 1)) & 1)
594 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
598 stmt_after_ip_normal_pos (struct loop *loop, tree stmt)
600 basic_block bb = ip_normal_pos (loop), sbb = bb_for_stmt (stmt);
604 if (sbb == loop->latch)
610 return stmt == last_stmt (bb);
613 /* Returns true if STMT if after the place where the original induction
614 variable CAND is incremented. */
617 stmt_after_ip_original_pos (struct iv_cand *cand, tree stmt)
619 basic_block cand_bb = bb_for_stmt (cand->incremented_at);
620 basic_block stmt_bb = bb_for_stmt (stmt);
621 block_stmt_iterator bsi;
623 if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
626 if (stmt_bb != cand_bb)
629 /* Scan the block from the end, since the original ivs are usually
630 incremented at the end of the loop body. */
631 for (bsi = bsi_last (stmt_bb); ; bsi_prev (&bsi))
633 if (bsi_stmt (bsi) == cand->incremented_at)
635 if (bsi_stmt (bsi) == stmt)
640 /* Returns true if STMT if after the place where the induction variable
641 CAND is incremented in LOOP. */
644 stmt_after_increment (struct loop *loop, struct iv_cand *cand, tree stmt)
652 return stmt_after_ip_normal_pos (loop, stmt);
655 return stmt_after_ip_original_pos (cand, stmt);
662 /* Element of the table in that we cache the numbers of iterations obtained
663 from exits of the loop. */
667 /* The edge for that the number of iterations is cached. */
670 /* True if the # of iterations was successfully determined. */
673 /* Description of # of iterations. */
674 struct tree_niter_desc niter;
677 /* Hash function for nfe_cache_elt E. */
680 nfe_hash (const void *e)
682 const struct nfe_cache_elt *elt = e;
684 return htab_hash_pointer (elt->exit);
687 /* Equality function for nfe_cache_elt E1 and edge E2. */
690 nfe_eq (const void *e1, const void *e2)
692 const struct nfe_cache_elt *elt1 = e1;
694 return elt1->exit == e2;
697 /* Returns structure describing number of iterations determined from
698 EXIT of DATA->current_loop, or NULL if something goes wrong. */
700 static struct tree_niter_desc *
701 niter_for_exit (struct ivopts_data *data, edge exit)
703 struct nfe_cache_elt *nfe_desc;
706 slot = htab_find_slot_with_hash (data->niters, exit,
707 htab_hash_pointer (exit),
712 nfe_desc = xmalloc (sizeof (struct nfe_cache_elt));
713 nfe_desc->exit = exit;
714 nfe_desc->valid_p = number_of_iterations_exit (data->current_loop,
715 exit, &nfe_desc->niter,
722 if (!nfe_desc->valid_p)
725 return &nfe_desc->niter;
728 /* Returns structure describing number of iterations determined from
729 single dominating exit of DATA->current_loop, or NULL if something
732 static struct tree_niter_desc *
733 niter_for_single_dom_exit (struct ivopts_data *data)
735 edge exit = single_dom_exit (data->current_loop);
740 return niter_for_exit (data, exit);
743 /* Initializes data structures used by the iv optimization pass, stored
744 in DATA. LOOPS is the loop tree. */
747 tree_ssa_iv_optimize_init (struct loops *loops, struct ivopts_data *data)
751 data->version_info_size = 2 * num_ssa_names;
752 data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
753 data->relevant = BITMAP_ALLOC (NULL);
754 data->important_candidates = BITMAP_ALLOC (NULL);
755 data->max_inv_id = 0;
756 data->niters = htab_create (10, nfe_hash, nfe_eq, free);
758 for (i = 1; i < loops->num; i++)
759 if (loops->parray[i])
760 loops->parray[i]->aux = xcalloc (1, sizeof (struct loop_data));
762 data->iv_uses = VEC_alloc (iv_use_p, heap, 20);
763 data->iv_candidates = VEC_alloc (iv_cand_p, heap, 20);
764 decl_rtl_to_reset = VEC_alloc (tree, heap, 20);
767 /* Returns a memory object to that EXPR points. In case we are able to
768 determine that it does not point to any such object, NULL is returned. */
771 determine_base_object (tree expr)
773 enum tree_code code = TREE_CODE (expr);
774 tree base, obj, op0, op1;
776 if (!POINTER_TYPE_P (TREE_TYPE (expr)))
785 obj = TREE_OPERAND (expr, 0);
786 base = get_base_address (obj);
791 if (TREE_CODE (base) == INDIRECT_REF)
792 return determine_base_object (TREE_OPERAND (base, 0));
794 return fold_convert (ptr_type_node,
795 build_fold_addr_expr (base));
799 op0 = determine_base_object (TREE_OPERAND (expr, 0));
800 op1 = determine_base_object (TREE_OPERAND (expr, 1));
806 return (code == PLUS_EXPR
808 : fold_build1 (NEGATE_EXPR, ptr_type_node, op1));
810 return fold_build2 (code, ptr_type_node, op0, op1);
814 return determine_base_object (TREE_OPERAND (expr, 0));
817 return fold_convert (ptr_type_node, expr);
821 /* Allocates an induction variable with given initial value BASE and step STEP
825 alloc_iv (tree base, tree step)
827 struct iv *iv = XCNEW (struct iv);
829 if (step && integer_zerop (step))
833 iv->base_object = determine_base_object (base);
836 iv->have_use_for = false;
838 iv->ssa_name = NULL_TREE;
843 /* Sets STEP and BASE for induction variable IV. */
846 set_iv (struct ivopts_data *data, tree iv, tree base, tree step)
848 struct version_info *info = name_info (data, iv);
850 gcc_assert (!info->iv);
852 bitmap_set_bit (data->relevant, SSA_NAME_VERSION (iv));
853 info->iv = alloc_iv (base, step);
854 info->iv->ssa_name = iv;
857 /* Finds induction variable declaration for VAR. */
860 get_iv (struct ivopts_data *data, tree var)
864 if (!name_info (data, var)->iv)
866 bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
869 || !flow_bb_inside_loop_p (data->current_loop, bb))
870 set_iv (data, var, var, NULL_TREE);
873 return name_info (data, var)->iv;
876 /* Determines the step of a biv defined in PHI. Returns NULL if PHI does
877 not define a simple affine biv with nonzero step. */
880 determine_biv_step (tree phi)
882 struct loop *loop = bb_for_stmt (phi)->loop_father;
883 tree name = PHI_RESULT (phi);
886 if (!is_gimple_reg (name))
889 if (!simple_iv (loop, phi, name, &iv, true))
892 return (zero_p (iv.step) ? NULL_TREE : iv.step);
895 /* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
898 abnormal_ssa_name_p (tree exp)
903 if (TREE_CODE (exp) != SSA_NAME)
906 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) != 0;
909 /* Returns false if BASE or INDEX contains a ssa name that occurs in an
910 abnormal phi node. Callback for for_each_index. */
913 idx_contains_abnormal_ssa_name_p (tree base, tree *index,
914 void *data ATTRIBUTE_UNUSED)
916 if (TREE_CODE (base) == ARRAY_REF)
918 if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
920 if (abnormal_ssa_name_p (TREE_OPERAND (base, 3)))
924 return !abnormal_ssa_name_p (*index);
927 /* Returns true if EXPR contains a ssa name that occurs in an
928 abnormal phi node. */
931 contains_abnormal_ssa_name_p (tree expr)
934 enum tree_code_class class;
939 code = TREE_CODE (expr);
940 class = TREE_CODE_CLASS (code);
942 if (code == SSA_NAME)
943 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
945 if (code == INTEGER_CST
946 || is_gimple_min_invariant (expr))
949 if (code == ADDR_EXPR)
950 return !for_each_index (&TREE_OPERAND (expr, 0),
951 idx_contains_abnormal_ssa_name_p,
958 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1)))
963 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0)))
975 /* Finds basic ivs. */
978 find_bivs (struct ivopts_data *data)
980 tree phi, step, type, base;
982 struct loop *loop = data->current_loop;
984 for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
986 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
989 step = determine_biv_step (phi);
993 base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
994 base = expand_simple_operations (base);
995 if (contains_abnormal_ssa_name_p (base)
996 || contains_abnormal_ssa_name_p (step))
999 type = TREE_TYPE (PHI_RESULT (phi));
1000 base = fold_convert (type, base);
1002 step = fold_convert (type, step);
1004 set_iv (data, PHI_RESULT (phi), base, step);
1011 /* Marks basic ivs. */
1014 mark_bivs (struct ivopts_data *data)
1017 struct iv *iv, *incr_iv;
1018 struct loop *loop = data->current_loop;
1019 basic_block incr_bb;
1021 for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
1023 iv = get_iv (data, PHI_RESULT (phi));
1027 var = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1028 incr_iv = get_iv (data, var);
1032 /* If the increment is in the subloop, ignore it. */
1033 incr_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
1034 if (incr_bb->loop_father != data->current_loop
1035 || (incr_bb->flags & BB_IRREDUCIBLE_LOOP))
1039 incr_iv->biv_p = true;
1043 /* Checks whether STMT defines a linear induction variable and stores its
1044 parameters to IV. */
1047 find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt, affine_iv *iv)
1050 struct loop *loop = data->current_loop;
1052 iv->base = NULL_TREE;
1053 iv->step = NULL_TREE;
1055 if (TREE_CODE (stmt) != MODIFY_EXPR)
1058 lhs = TREE_OPERAND (stmt, 0);
1059 if (TREE_CODE (lhs) != SSA_NAME)
1062 if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), iv, true))
1064 iv->base = expand_simple_operations (iv->base);
1066 if (contains_abnormal_ssa_name_p (iv->base)
1067 || contains_abnormal_ssa_name_p (iv->step))
1073 /* Finds general ivs in statement STMT. */
1076 find_givs_in_stmt (struct ivopts_data *data, tree stmt)
1080 if (!find_givs_in_stmt_scev (data, stmt, &iv))
1083 set_iv (data, TREE_OPERAND (stmt, 0), iv.base, iv.step);
1086 /* Finds general ivs in basic block BB. */
1089 find_givs_in_bb (struct ivopts_data *data, basic_block bb)
1091 block_stmt_iterator bsi;
1093 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1094 find_givs_in_stmt (data, bsi_stmt (bsi));
1097 /* Finds general ivs. */
1100 find_givs (struct ivopts_data *data)
1102 struct loop *loop = data->current_loop;
1103 basic_block *body = get_loop_body_in_dom_order (loop);
1106 for (i = 0; i < loop->num_nodes; i++)
1107 find_givs_in_bb (data, body[i]);
1111 /* For each ssa name defined in LOOP determines whether it is an induction
1112 variable and if so, its initial value and step. */
1115 find_induction_variables (struct ivopts_data *data)
1120 if (!find_bivs (data))
1126 if (dump_file && (dump_flags & TDF_DETAILS))
1128 struct tree_niter_desc *niter;
1130 niter = niter_for_single_dom_exit (data);
1134 fprintf (dump_file, " number of iterations ");
1135 print_generic_expr (dump_file, niter->niter, TDF_SLIM);
1136 fprintf (dump_file, "\n");
1138 fprintf (dump_file, " may be zero if ");
1139 print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
1140 fprintf (dump_file, "\n");
1141 fprintf (dump_file, "\n");
1144 fprintf (dump_file, "Induction variables:\n\n");
1146 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
1148 if (ver_info (data, i)->iv)
1149 dump_iv (dump_file, ver_info (data, i)->iv);
1156 /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV. */
1158 static struct iv_use *
1159 record_use (struct ivopts_data *data, tree *use_p, struct iv *iv,
1160 tree stmt, enum use_type use_type)
1162 struct iv_use *use = XCNEW (struct iv_use);
1164 use->id = n_iv_uses (data);
1165 use->type = use_type;
1169 use->related_cands = BITMAP_ALLOC (NULL);
1171 /* To avoid showing ssa name in the dumps, if it was not reset by the
1173 iv->ssa_name = NULL_TREE;
1175 if (dump_file && (dump_flags & TDF_DETAILS))
1176 dump_use (dump_file, use);
1178 VEC_safe_push (iv_use_p, heap, data->iv_uses, use);
1183 /* Checks whether OP is a loop-level invariant and if so, records it.
1184 NONLINEAR_USE is true if the invariant is used in a way we do not
1185 handle specially. */
1188 record_invariant (struct ivopts_data *data, tree op, bool nonlinear_use)
1191 struct version_info *info;
1193 if (TREE_CODE (op) != SSA_NAME
1194 || !is_gimple_reg (op))
1197 bb = bb_for_stmt (SSA_NAME_DEF_STMT (op));
1199 && flow_bb_inside_loop_p (data->current_loop, bb))
1202 info = name_info (data, op);
1204 info->has_nonlin_use |= nonlinear_use;
1206 info->inv_id = ++data->max_inv_id;
1207 bitmap_set_bit (data->relevant, SSA_NAME_VERSION (op));
1210 /* Checks whether the use OP is interesting and if so, records it
1213 static struct iv_use *
1214 find_interesting_uses_outer_or_nonlin (struct ivopts_data *data, tree op,
1222 if (TREE_CODE (op) != SSA_NAME)
1225 iv = get_iv (data, op);
1229 if (iv->have_use_for)
1231 use = iv_use (data, iv->use_id);
1233 gcc_assert (use->type == USE_NONLINEAR_EXPR
1234 || use->type == USE_OUTER);
1236 if (type == USE_NONLINEAR_EXPR)
1237 use->type = USE_NONLINEAR_EXPR;
1241 if (zero_p (iv->step))
1243 record_invariant (data, op, true);
1246 iv->have_use_for = true;
1248 civ = XNEW (struct iv);
1251 stmt = SSA_NAME_DEF_STMT (op);
1252 gcc_assert (TREE_CODE (stmt) == PHI_NODE
1253 || TREE_CODE (stmt) == MODIFY_EXPR);
1255 use = record_use (data, NULL, civ, stmt, type);
1256 iv->use_id = use->id;
1261 /* Checks whether the use OP is interesting and if so, records it. */
1263 static struct iv_use *
1264 find_interesting_uses_op (struct ivopts_data *data, tree op)
1266 return find_interesting_uses_outer_or_nonlin (data, op, USE_NONLINEAR_EXPR);
1269 /* Records a definition of induction variable OP that is used outside of the
1272 static struct iv_use *
1273 find_interesting_uses_outer (struct ivopts_data *data, tree op)
1275 return find_interesting_uses_outer_or_nonlin (data, op, USE_OUTER);
1278 /* Checks whether the condition *COND_P in STMT is interesting
1279 and if so, records it. */
1282 find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
1286 struct iv *iv0 = NULL, *iv1 = NULL, *civ;
1288 tree zero = integer_zero_node;
1290 const_iv.step = NULL_TREE;
1292 if (TREE_CODE (*cond_p) != SSA_NAME
1293 && !COMPARISON_CLASS_P (*cond_p))
1296 if (TREE_CODE (*cond_p) == SSA_NAME)
1303 op0_p = &TREE_OPERAND (*cond_p, 0);
1304 op1_p = &TREE_OPERAND (*cond_p, 1);
1307 if (TREE_CODE (*op0_p) == SSA_NAME)
1308 iv0 = get_iv (data, *op0_p);
1312 if (TREE_CODE (*op1_p) == SSA_NAME)
1313 iv1 = get_iv (data, *op1_p);
1317 if (/* When comparing with non-invariant value, we may not do any senseful
1318 induction variable elimination. */
1320 /* Eliminating condition based on two ivs would be nontrivial.
1321 ??? TODO -- it is not really important to handle this case. */
1322 || (!zero_p (iv0->step) && !zero_p (iv1->step)))
1324 find_interesting_uses_op (data, *op0_p);
1325 find_interesting_uses_op (data, *op1_p);
1329 if (zero_p (iv0->step) && zero_p (iv1->step))
1331 /* If both are invariants, this is a work for unswitching. */
1335 civ = XNEW (struct iv);
1336 *civ = zero_p (iv0->step) ? *iv1: *iv0;
1337 record_use (data, cond_p, civ, stmt, USE_COMPARE);
1340 /* Returns true if expression EXPR is obviously invariant in LOOP,
1341 i.e. if all its operands are defined outside of the LOOP. */
1344 expr_invariant_in_loop_p (struct loop *loop, tree expr)
1349 if (is_gimple_min_invariant (expr))
1352 if (TREE_CODE (expr) == SSA_NAME)
1354 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (expr));
1356 && flow_bb_inside_loop_p (loop, def_bb))
1365 len = TREE_CODE_LENGTH (TREE_CODE (expr));
1366 for (i = 0; i < len; i++)
1367 if (!expr_invariant_in_loop_p (loop, TREE_OPERAND (expr, i)))
1373 /* Cumulates the steps of indices into DATA and replaces their values with the
1374 initial ones. Returns false when the value of the index cannot be determined.
1375 Callback for for_each_index. */
1377 struct ifs_ivopts_data
1379 struct ivopts_data *ivopts_data;
1385 idx_find_step (tree base, tree *idx, void *data)
1387 struct ifs_ivopts_data *dta = data;
1389 tree step, iv_step, lbound, off;
1390 struct loop *loop = dta->ivopts_data->current_loop;
1392 if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF
1393 || TREE_CODE (base) == ALIGN_INDIRECT_REF)
1396 /* If base is a component ref, require that the offset of the reference
1398 if (TREE_CODE (base) == COMPONENT_REF)
1400 off = component_ref_field_offset (base);
1401 return expr_invariant_in_loop_p (loop, off);
1404 /* If base is array, first check whether we will be able to move the
1405 reference out of the loop (in order to take its address in strength
1406 reduction). In order for this to work we need both lower bound
1407 and step to be loop invariants. */
1408 if (TREE_CODE (base) == ARRAY_REF)
1410 step = array_ref_element_size (base);
1411 lbound = array_ref_low_bound (base);
1413 if (!expr_invariant_in_loop_p (loop, step)
1414 || !expr_invariant_in_loop_p (loop, lbound))
1418 if (TREE_CODE (*idx) != SSA_NAME)
1421 iv = get_iv (dta->ivopts_data, *idx);
1430 if (TREE_CODE (base) == ARRAY_REF)
1432 step = array_ref_element_size (base);
1434 /* We only handle addresses whose step is an integer constant. */
1435 if (TREE_CODE (step) != INTEGER_CST)
1439 /* The step for pointer arithmetics already is 1 byte. */
1440 step = build_int_cst (sizetype, 1);
1442 /* FIXME: convert_step should not be used outside chrec_convert: fix
1443 this by calling chrec_convert. */
1444 iv_step = convert_step (dta->ivopts_data->current_loop,
1445 sizetype, iv->base, iv->step, dta->stmt);
1449 /* The index might wrap. */
1453 step = fold_build2 (MULT_EXPR, sizetype, step, iv_step);
1456 *dta->step_p = step;
1458 *dta->step_p = fold_build2 (PLUS_EXPR, sizetype, *dta->step_p, step);
1463 /* Records use in index IDX. Callback for for_each_index. Ivopts data
1464 object is passed to it in DATA. */
1467 idx_record_use (tree base, tree *idx,
1470 find_interesting_uses_op (data, *idx);
1471 if (TREE_CODE (base) == ARRAY_REF)
1473 find_interesting_uses_op (data, array_ref_element_size (base));
1474 find_interesting_uses_op (data, array_ref_low_bound (base));
1479 /* Returns true if memory reference REF may be unaligned. */
1482 may_be_unaligned_p (tree ref)
1486 HOST_WIDE_INT bitsize;
1487 HOST_WIDE_INT bitpos;
1489 enum machine_mode mode;
1490 int unsignedp, volatilep;
1491 unsigned base_align;
1493 /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
1494 thus they are not misaligned. */
1495 if (TREE_CODE (ref) == TARGET_MEM_REF)
1498 /* The test below is basically copy of what expr.c:normal_inner_ref
1499 does to check whether the object must be loaded by parts when
1500 STRICT_ALIGNMENT is true. */
1501 base = get_inner_reference (ref, &bitsize, &bitpos, &toffset, &mode,
1502 &unsignedp, &volatilep, true);
1503 base_type = TREE_TYPE (base);
1504 base_align = TYPE_ALIGN (base_type);
1507 && (base_align < GET_MODE_ALIGNMENT (mode)
1508 || bitpos % GET_MODE_ALIGNMENT (mode) != 0
1509 || bitpos % BITS_PER_UNIT != 0))
1515 /* Finds addresses in *OP_P inside STMT. */
1518 find_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p)
1520 tree base = *op_p, step = NULL;
1522 struct ifs_ivopts_data ifs_ivopts_data;
1524 /* Do not play with volatile memory references. A bit too conservative,
1525 perhaps, but safe. */
1526 if (stmt_ann (stmt)->has_volatile_ops)
1529 /* Ignore bitfields for now. Not really something terribly complicated
1531 if (TREE_CODE (base) == COMPONENT_REF
1532 && DECL_NONADDRESSABLE_P (TREE_OPERAND (base, 1)))
1535 if (STRICT_ALIGNMENT
1536 && may_be_unaligned_p (base))
1539 base = unshare_expr (base);
1541 if (TREE_CODE (base) == TARGET_MEM_REF)
1543 tree type = build_pointer_type (TREE_TYPE (base));
1547 && TREE_CODE (TMR_BASE (base)) == SSA_NAME)
1549 civ = get_iv (data, TMR_BASE (base));
1553 TMR_BASE (base) = civ->base;
1556 if (TMR_INDEX (base)
1557 && TREE_CODE (TMR_INDEX (base)) == SSA_NAME)
1559 civ = get_iv (data, TMR_INDEX (base));
1563 TMR_INDEX (base) = civ->base;
1568 if (TMR_STEP (base))
1569 astep = fold_build2 (MULT_EXPR, type, TMR_STEP (base), astep);
1572 step = fold_build2 (PLUS_EXPR, type, step, astep);
1580 base = tree_mem_ref_addr (type, base);
1584 ifs_ivopts_data.ivopts_data = data;
1585 ifs_ivopts_data.stmt = stmt;
1586 ifs_ivopts_data.step_p = &step;
1587 if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
1591 gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF);
1592 gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF);
1594 base = build_fold_addr_expr (base);
1597 civ = alloc_iv (base, step);
1598 record_use (data, op_p, civ, stmt, USE_ADDRESS);
1602 for_each_index (op_p, idx_record_use, data);
1605 /* Finds and records invariants used in STMT. */
1608 find_invariants_stmt (struct ivopts_data *data, tree stmt)
1611 use_operand_p use_p;
1614 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1616 op = USE_FROM_PTR (use_p);
1617 record_invariant (data, op, false);
1621 /* Finds interesting uses of induction variables in the statement STMT. */
1624 find_interesting_uses_stmt (struct ivopts_data *data, tree stmt)
1629 use_operand_p use_p;
1631 find_invariants_stmt (data, stmt);
1633 if (TREE_CODE (stmt) == COND_EXPR)
1635 find_interesting_uses_cond (data, stmt, &COND_EXPR_COND (stmt));
1639 if (TREE_CODE (stmt) == MODIFY_EXPR)
1641 lhs = TREE_OPERAND (stmt, 0);
1642 rhs = TREE_OPERAND (stmt, 1);
1644 if (TREE_CODE (lhs) == SSA_NAME)
1646 /* If the statement defines an induction variable, the uses are not
1647 interesting by themselves. */
1649 iv = get_iv (data, lhs);
1651 if (iv && !zero_p (iv->step))
1655 switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
1657 case tcc_comparison:
1658 find_interesting_uses_cond (data, stmt, &TREE_OPERAND (stmt, 1));
1662 find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 1));
1663 if (REFERENCE_CLASS_P (lhs))
1664 find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
1670 if (REFERENCE_CLASS_P (lhs)
1671 && is_gimple_val (rhs))
1673 find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
1674 find_interesting_uses_op (data, rhs);
1678 /* TODO -- we should also handle address uses of type
1680 memory = call (whatever);
1687 if (TREE_CODE (stmt) == PHI_NODE
1688 && bb_for_stmt (stmt) == data->current_loop->header)
1690 lhs = PHI_RESULT (stmt);
1691 iv = get_iv (data, lhs);
1693 if (iv && !zero_p (iv->step))
1697 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1699 op = USE_FROM_PTR (use_p);
1701 if (TREE_CODE (op) != SSA_NAME)
1704 iv = get_iv (data, op);
1708 find_interesting_uses_op (data, op);
1712 /* Finds interesting uses of induction variables outside of loops
1713 on loop exit edge EXIT. */
1716 find_interesting_uses_outside (struct ivopts_data *data, edge exit)
1720 for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
1722 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1723 find_interesting_uses_outer (data, def);
1727 /* Finds uses of the induction variables that are interesting. */
1730 find_interesting_uses (struct ivopts_data *data)
1733 block_stmt_iterator bsi;
1735 basic_block *body = get_loop_body (data->current_loop);
1737 struct version_info *info;
1740 if (dump_file && (dump_flags & TDF_DETAILS))
1741 fprintf (dump_file, "Uses:\n\n");
1743 for (i = 0; i < data->current_loop->num_nodes; i++)
1748 FOR_EACH_EDGE (e, ei, bb->succs)
1749 if (e->dest != EXIT_BLOCK_PTR
1750 && !flow_bb_inside_loop_p (data->current_loop, e->dest))
1751 find_interesting_uses_outside (data, e);
1753 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1754 find_interesting_uses_stmt (data, phi);
1755 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1756 find_interesting_uses_stmt (data, bsi_stmt (bsi));
1759 if (dump_file && (dump_flags & TDF_DETAILS))
1763 fprintf (dump_file, "\n");
1765 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
1767 info = ver_info (data, i);
1770 fprintf (dump_file, " ");
1771 print_generic_expr (dump_file, info->name, TDF_SLIM);
1772 fprintf (dump_file, " is invariant (%d)%s\n",
1773 info->inv_id, info->has_nonlin_use ? "" : ", eliminable");
1777 fprintf (dump_file, "\n");
1783 /* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
1784 is true, assume we are inside an address. If TOP_COMPREF is true, assume
1785 we are at the top-level of the processed address. */
1788 strip_offset_1 (tree expr, bool inside_addr, bool top_compref,
1789 unsigned HOST_WIDE_INT *offset)
1791 tree op0 = NULL_TREE, op1 = NULL_TREE, tmp, step;
1792 enum tree_code code;
1793 tree type, orig_type = TREE_TYPE (expr);
1794 unsigned HOST_WIDE_INT off0, off1, st;
1795 tree orig_expr = expr;
1799 type = TREE_TYPE (expr);
1800 code = TREE_CODE (expr);
1806 if (!cst_and_fits_in_hwi (expr)
1810 *offset = int_cst_value (expr);
1811 return build_int_cst_type (orig_type, 0);
1815 op0 = TREE_OPERAND (expr, 0);
1816 op1 = TREE_OPERAND (expr, 1);
1818 op0 = strip_offset_1 (op0, false, false, &off0);
1819 op1 = strip_offset_1 (op1, false, false, &off1);
1821 *offset = (code == PLUS_EXPR ? off0 + off1 : off0 - off1);
1822 if (op0 == TREE_OPERAND (expr, 0)
1823 && op1 == TREE_OPERAND (expr, 1))
1828 else if (zero_p (op0))
1830 if (code == PLUS_EXPR)
1833 expr = fold_build1 (NEGATE_EXPR, type, op1);
1836 expr = fold_build2 (code, type, op0, op1);
1838 return fold_convert (orig_type, expr);
1844 step = array_ref_element_size (expr);
1845 if (!cst_and_fits_in_hwi (step))
1848 st = int_cst_value (step);
1849 op1 = TREE_OPERAND (expr, 1);
1850 op1 = strip_offset_1 (op1, false, false, &off1);
1851 *offset = off1 * st;
1856 /* Strip the component reference completely. */
1857 op0 = TREE_OPERAND (expr, 0);
1858 op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
1868 tmp = component_ref_field_offset (expr);
1870 && cst_and_fits_in_hwi (tmp))
1872 /* Strip the component reference completely. */
1873 op0 = TREE_OPERAND (expr, 0);
1874 op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
1875 *offset = off0 + int_cst_value (tmp);
1881 op0 = TREE_OPERAND (expr, 0);
1882 op0 = strip_offset_1 (op0, true, true, &off0);
1885 if (op0 == TREE_OPERAND (expr, 0))
1888 expr = build_fold_addr_expr (op0);
1889 return fold_convert (orig_type, expr);
1892 inside_addr = false;
1899 /* Default handling of expressions for that we want to recurse into
1900 the first operand. */
1901 op0 = TREE_OPERAND (expr, 0);
1902 op0 = strip_offset_1 (op0, inside_addr, false, &off0);
1905 if (op0 == TREE_OPERAND (expr, 0)
1906 && (!op1 || op1 == TREE_OPERAND (expr, 1)))
1909 expr = copy_node (expr);
1910 TREE_OPERAND (expr, 0) = op0;
1912 TREE_OPERAND (expr, 1) = op1;
1914 /* Inside address, we might strip the top level component references,
1915 thus changing type of the expression. Handling of ADDR_EXPR
1917 expr = fold_convert (orig_type, expr);
1922 /* Strips constant offsets from EXPR and stores them to OFFSET. */
1925 strip_offset (tree expr, unsigned HOST_WIDE_INT *offset)
1927 return strip_offset_1 (expr, false, false, offset);
1930 /* Returns variant of TYPE that can be used as base for different uses.
1931 For integer types, we return unsigned variant of the type, which
1932 avoids problems with overflows. For pointer types, we return void *. */
1935 generic_type_for (tree type)
1937 if (POINTER_TYPE_P (type))
1938 return ptr_type_node;
1940 if (TYPE_UNSIGNED (type))
1943 return unsigned_type_for (type);
1946 /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
1947 the bitmap to that we should store it. */
1949 static struct ivopts_data *fd_ivopts_data;
1951 find_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
1953 bitmap *depends_on = data;
1954 struct version_info *info;
1956 if (TREE_CODE (*expr_p) != SSA_NAME)
1958 info = name_info (fd_ivopts_data, *expr_p);
1960 if (!info->inv_id || info->has_nonlin_use)
1964 *depends_on = BITMAP_ALLOC (NULL);
1965 bitmap_set_bit (*depends_on, info->inv_id);
1970 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
1971 position to POS. If USE is not NULL, the candidate is set as related to
1972 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
1973 replacement of the final value of the iv by a direct computation. */
1975 static struct iv_cand *
1976 add_candidate_1 (struct ivopts_data *data,
1977 tree base, tree step, bool important, enum iv_position pos,
1978 struct iv_use *use, tree incremented_at)
1981 struct iv_cand *cand = NULL;
1982 tree type, orig_type;
1986 orig_type = TREE_TYPE (base);
1987 type = generic_type_for (orig_type);
1988 if (type != orig_type)
1990 base = fold_convert (type, base);
1992 step = fold_convert (type, step);
1996 for (i = 0; i < n_iv_cands (data); i++)
1998 cand = iv_cand (data, i);
2000 if (cand->pos != pos)
2003 if (cand->incremented_at != incremented_at)
2017 if (!operand_equal_p (base, cand->iv->base, 0))
2020 if (zero_p (cand->iv->step))
2027 if (step && operand_equal_p (step, cand->iv->step, 0))
2032 if (i == n_iv_cands (data))
2034 cand = XCNEW (struct iv_cand);
2040 cand->iv = alloc_iv (base, step);
2043 if (pos != IP_ORIGINAL && cand->iv)
2045 cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp");
2046 cand->var_after = cand->var_before;
2048 cand->important = important;
2049 cand->incremented_at = incremented_at;
2050 VEC_safe_push (iv_cand_p, heap, data->iv_candidates, cand);
2053 && TREE_CODE (step) != INTEGER_CST)
2055 fd_ivopts_data = data;
2056 walk_tree (&step, find_depends, &cand->depends_on, NULL);
2059 if (dump_file && (dump_flags & TDF_DETAILS))
2060 dump_cand (dump_file, cand);
2063 if (important && !cand->important)
2065 cand->important = true;
2066 if (dump_file && (dump_flags & TDF_DETAILS))
2067 fprintf (dump_file, "Candidate %d is important\n", cand->id);
2072 bitmap_set_bit (use->related_cands, i);
2073 if (dump_file && (dump_flags & TDF_DETAILS))
2074 fprintf (dump_file, "Candidate %d is related to use %d\n",
2081 /* Returns true if incrementing the induction variable at the end of the LOOP
2084 The purpose is to avoid splitting latch edge with a biv increment, thus
2085 creating a jump, possibly confusing other optimization passes and leaving
2086 less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS
2087 is not available (so we do not have a better alternative), or if the latch
2088 edge is already nonempty. */
2091 allow_ip_end_pos_p (struct loop *loop)
2093 if (!ip_normal_pos (loop))
2096 if (!empty_block_p (ip_end_pos (loop)))
2102 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2103 position to POS. If USE is not NULL, the candidate is set as related to
2104 it. The candidate computation is scheduled on all available positions. */
2107 add_candidate (struct ivopts_data *data,
2108 tree base, tree step, bool important, struct iv_use *use)
2110 if (ip_normal_pos (data->current_loop))
2111 add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL_TREE);
2112 if (ip_end_pos (data->current_loop)
2113 && allow_ip_end_pos_p (data->current_loop))
2114 add_candidate_1 (data, base, step, important, IP_END, use, NULL_TREE);
2117 /* Add a standard "0 + 1 * iteration" iv candidate for a
2118 type with SIZE bits. */
2121 add_standard_iv_candidates_for_size (struct ivopts_data *data,
2124 tree type = lang_hooks.types.type_for_size (size, true);
2125 add_candidate (data, build_int_cst (type, 0), build_int_cst (type, 1),
2129 /* Adds standard iv candidates. */
2132 add_standard_iv_candidates (struct ivopts_data *data)
2134 add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE);
2136 /* The same for a double-integer type if it is still fast enough. */
2137 if (BITS_PER_WORD >= INT_TYPE_SIZE * 2)
2138 add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE * 2);
2142 /* Adds candidates bases on the old induction variable IV. */
2145 add_old_iv_candidates (struct ivopts_data *data, struct iv *iv)
2148 struct iv_cand *cand;
2150 add_candidate (data, iv->base, iv->step, true, NULL);
2152 /* The same, but with initial value zero. */
2153 add_candidate (data,
2154 build_int_cst (TREE_TYPE (iv->base), 0),
2155 iv->step, true, NULL);
2157 phi = SSA_NAME_DEF_STMT (iv->ssa_name);
2158 if (TREE_CODE (phi) == PHI_NODE)
2160 /* Additionally record the possibility of leaving the original iv
2162 def = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (data->current_loop));
2163 cand = add_candidate_1 (data,
2164 iv->base, iv->step, true, IP_ORIGINAL, NULL,
2165 SSA_NAME_DEF_STMT (def));
2166 cand->var_before = iv->ssa_name;
2167 cand->var_after = def;
2171 /* Adds candidates based on the old induction variables. */
2174 add_old_ivs_candidates (struct ivopts_data *data)
2180 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
2182 iv = ver_info (data, i)->iv;
2183 if (iv && iv->biv_p && !zero_p (iv->step))
2184 add_old_iv_candidates (data, iv);
2188 /* Adds candidates based on the value of the induction variable IV and USE. */
2191 add_iv_value_candidates (struct ivopts_data *data,
2192 struct iv *iv, struct iv_use *use)
2194 unsigned HOST_WIDE_INT offset;
2197 add_candidate (data, iv->base, iv->step, false, use);
2199 /* The same, but with initial value zero. Make such variable important,
2200 since it is generic enough so that possibly many uses may be based
2202 add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
2203 iv->step, true, use);
2205 /* Third, try removing the constant offset. */
2206 base = strip_offset (iv->base, &offset);
2208 add_candidate (data, base, iv->step, false, use);
2211 /* Possibly adds pseudocandidate for replacing the final value of USE by
2212 a direct computation. */
2215 add_iv_outer_candidates (struct ivopts_data *data, struct iv_use *use)
2217 struct tree_niter_desc *niter;
2219 /* We must know where we exit the loop and how many times does it roll. */
2220 niter = niter_for_single_dom_exit (data);
2222 || !zero_p (niter->may_be_zero))
2225 add_candidate_1 (data, NULL, NULL, false, IP_NORMAL, use, NULL_TREE);
2228 /* Adds candidates based on the uses. */
2231 add_derived_ivs_candidates (struct ivopts_data *data)
2235 for (i = 0; i < n_iv_uses (data); i++)
2237 struct iv_use *use = iv_use (data, i);
2244 case USE_NONLINEAR_EXPR:
2247 /* Just add the ivs based on the value of the iv used here. */
2248 add_iv_value_candidates (data, use->iv, use);
2252 add_iv_value_candidates (data, use->iv, use);
2254 /* Additionally, add the pseudocandidate for the possibility to
2255 replace the final value by a direct computation. */
2256 add_iv_outer_candidates (data, use);
2265 /* Record important candidates and add them to related_cands bitmaps
2269 record_important_candidates (struct ivopts_data *data)
2274 for (i = 0; i < n_iv_cands (data); i++)
2276 struct iv_cand *cand = iv_cand (data, i);
2278 if (cand->important)
2279 bitmap_set_bit (data->important_candidates, i);
2282 data->consider_all_candidates = (n_iv_cands (data)
2283 <= CONSIDER_ALL_CANDIDATES_BOUND);
2285 if (data->consider_all_candidates)
2287 /* We will not need "related_cands" bitmaps in this case,
2288 so release them to decrease peak memory consumption. */
2289 for (i = 0; i < n_iv_uses (data); i++)
2291 use = iv_use (data, i);
2292 BITMAP_FREE (use->related_cands);
2297 /* Add important candidates to the related_cands bitmaps. */
2298 for (i = 0; i < n_iv_uses (data); i++)
2299 bitmap_ior_into (iv_use (data, i)->related_cands,
2300 data->important_candidates);
2304 /* Finds the candidates for the induction variables. */
2307 find_iv_candidates (struct ivopts_data *data)
2309 /* Add commonly used ivs. */
2310 add_standard_iv_candidates (data);
2312 /* Add old induction variables. */
2313 add_old_ivs_candidates (data);
2315 /* Add induction variables derived from uses. */
2316 add_derived_ivs_candidates (data);
2318 /* Record the important candidates. */
2319 record_important_candidates (data);
2322 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
2323 If consider_all_candidates is true, we use a two-dimensional array, otherwise
2324 we allocate a simple list to every use. */
2327 alloc_use_cost_map (struct ivopts_data *data)
2329 unsigned i, size, s, j;
2331 for (i = 0; i < n_iv_uses (data); i++)
2333 struct iv_use *use = iv_use (data, i);
2336 if (data->consider_all_candidates)
2337 size = n_iv_cands (data);
2341 EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi)
2346 /* Round up to the power of two, so that moduling by it is fast. */
2347 for (size = 1; size < s; size <<= 1)
2351 use->n_map_members = size;
2352 use->cost_map = XCNEWVEC (struct cost_pair, size);
2356 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
2357 on invariants DEPENDS_ON and that the value used in expressing it
2361 set_use_iv_cost (struct ivopts_data *data,
2362 struct iv_use *use, struct iv_cand *cand, unsigned cost,
2363 bitmap depends_on, tree value)
2369 BITMAP_FREE (depends_on);
2373 if (data->consider_all_candidates)
2375 use->cost_map[cand->id].cand = cand;
2376 use->cost_map[cand->id].cost = cost;
2377 use->cost_map[cand->id].depends_on = depends_on;
2378 use->cost_map[cand->id].value = value;
2382 /* n_map_members is a power of two, so this computes modulo. */
2383 s = cand->id & (use->n_map_members - 1);
2384 for (i = s; i < use->n_map_members; i++)
2385 if (!use->cost_map[i].cand)
2387 for (i = 0; i < s; i++)
2388 if (!use->cost_map[i].cand)
2394 use->cost_map[i].cand = cand;
2395 use->cost_map[i].cost = cost;
2396 use->cost_map[i].depends_on = depends_on;
2397 use->cost_map[i].value = value;
2400 /* Gets cost of (USE, CANDIDATE) pair. */
2402 static struct cost_pair *
2403 get_use_iv_cost (struct ivopts_data *data, struct iv_use *use,
2404 struct iv_cand *cand)
2407 struct cost_pair *ret;
2412 if (data->consider_all_candidates)
2414 ret = use->cost_map + cand->id;
2421 /* n_map_members is a power of two, so this computes modulo. */
2422 s = cand->id & (use->n_map_members - 1);
2423 for (i = s; i < use->n_map_members; i++)
2424 if (use->cost_map[i].cand == cand)
2425 return use->cost_map + i;
2427 for (i = 0; i < s; i++)
2428 if (use->cost_map[i].cand == cand)
2429 return use->cost_map + i;
2434 /* Returns estimate on cost of computing SEQ. */
2442 for (; seq; seq = NEXT_INSN (seq))
2444 set = single_set (seq);
2446 cost += rtx_cost (set, SET);
2454 /* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
2456 produce_memory_decl_rtl (tree obj, int *regno)
2461 if (TREE_STATIC (obj) || DECL_EXTERNAL (obj))
2463 const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj));
2464 x = gen_rtx_SYMBOL_REF (Pmode, name);
2467 x = gen_raw_REG (Pmode, (*regno)++);
2469 return gen_rtx_MEM (DECL_MODE (obj), x);
2472 /* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
2473 walk_tree. DATA contains the actual fake register number. */
2476 prepare_decl_rtl (tree *expr_p, int *ws, void *data)
2478 tree obj = NULL_TREE;
2482 switch (TREE_CODE (*expr_p))
2485 for (expr_p = &TREE_OPERAND (*expr_p, 0);
2486 handled_component_p (*expr_p);
2487 expr_p = &TREE_OPERAND (*expr_p, 0))
2491 x = produce_memory_decl_rtl (obj, regno);
2496 obj = SSA_NAME_VAR (*expr_p);
2497 if (!DECL_RTL_SET_P (obj))
2498 x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
2507 if (DECL_RTL_SET_P (obj))
2510 if (DECL_MODE (obj) == BLKmode)
2511 x = produce_memory_decl_rtl (obj, regno);
2513 x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
2523 VEC_safe_push (tree, heap, decl_rtl_to_reset, obj);
2524 SET_DECL_RTL (obj, x);
2530 /* Determines cost of the computation of EXPR. */
2533 computation_cost (tree expr)
2536 tree type = TREE_TYPE (expr);
2538 /* Avoid using hard regs in ways which may be unsupported. */
2539 int regno = LAST_VIRTUAL_REGISTER + 1;
2541 walk_tree (&expr, prepare_decl_rtl, ®no, NULL);
2543 rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL);
2547 cost = seq_cost (seq);
2549 cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type));
2554 /* Returns variable containing the value of candidate CAND at statement AT. */
2557 var_at_stmt (struct loop *loop, struct iv_cand *cand, tree stmt)
2559 if (stmt_after_increment (loop, cand, stmt))
2560 return cand->var_after;
2562 return cand->var_before;
2565 /* Return the most significant (sign) bit of T. Similar to tree_int_cst_msb,
2566 but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE. */
2569 tree_int_cst_sign_bit (tree t)
2571 unsigned bitno = TYPE_PRECISION (TREE_TYPE (t)) - 1;
2572 unsigned HOST_WIDE_INT w;
2574 if (bitno < HOST_BITS_PER_WIDE_INT)
2575 w = TREE_INT_CST_LOW (t);
2578 w = TREE_INT_CST_HIGH (t);
2579 bitno -= HOST_BITS_PER_WIDE_INT;
2582 return (w >> bitno) & 1;
2585 /* If we can prove that TOP = cst * BOT for some constant cst in TYPE,
2586 return cst. Otherwise return NULL_TREE. */
2589 constant_multiple_of (tree type, tree top, tree bot)
2591 tree res, mby, p0, p1;
2592 enum tree_code code;
2598 if (operand_equal_p (top, bot, 0))
2599 return build_int_cst (type, 1);
2601 code = TREE_CODE (top);
2605 mby = TREE_OPERAND (top, 1);
2606 if (TREE_CODE (mby) != INTEGER_CST)
2609 res = constant_multiple_of (type, TREE_OPERAND (top, 0), bot);
2613 return fold_binary_to_constant (MULT_EXPR, type, res,
2614 fold_convert (type, mby));
2618 p0 = constant_multiple_of (type, TREE_OPERAND (top, 0), bot);
2621 p1 = constant_multiple_of (type, TREE_OPERAND (top, 1), bot);
2625 return fold_binary_to_constant (code, type, p0, p1);
2628 if (TREE_CODE (bot) != INTEGER_CST)
2631 bot = fold_convert (type, bot);
2632 top = fold_convert (type, top);
2634 /* If BOT seems to be negative, try dividing by -BOT instead, and negate
2635 the result afterwards. */
2636 if (tree_int_cst_sign_bit (bot))
2639 bot = fold_unary_to_constant (NEGATE_EXPR, type, bot);
2644 /* Ditto for TOP. */
2645 if (tree_int_cst_sign_bit (top))
2648 top = fold_unary_to_constant (NEGATE_EXPR, type, top);
2651 if (!zero_p (fold_binary_to_constant (TRUNC_MOD_EXPR, type, top, bot)))
2654 res = fold_binary_to_constant (EXACT_DIV_EXPR, type, top, bot);
2656 res = fold_unary_to_constant (NEGATE_EXPR, type, res);
2664 /* Sets COMB to CST. */
2667 aff_combination_const (struct affine_tree_combination *comb, tree type,
2668 unsigned HOST_WIDE_INT cst)
2670 unsigned prec = TYPE_PRECISION (type);
2673 comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
2676 comb->rest = NULL_TREE;
2677 comb->offset = cst & comb->mask;
2680 /* Sets COMB to single element ELT. */
2683 aff_combination_elt (struct affine_tree_combination *comb, tree type, tree elt)
2685 unsigned prec = TYPE_PRECISION (type);
2688 comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
2691 comb->elts[0] = elt;
2693 comb->rest = NULL_TREE;
2697 /* Scales COMB by SCALE. */
2700 aff_combination_scale (struct affine_tree_combination *comb,
2701 unsigned HOST_WIDE_INT scale)
2710 aff_combination_const (comb, comb->type, 0);
2714 comb->offset = (scale * comb->offset) & comb->mask;
2715 for (i = 0, j = 0; i < comb->n; i++)
2717 comb->coefs[j] = (scale * comb->coefs[i]) & comb->mask;
2718 comb->elts[j] = comb->elts[i];
2719 if (comb->coefs[j] != 0)
2726 if (comb->n < MAX_AFF_ELTS)
2728 comb->coefs[comb->n] = scale;
2729 comb->elts[comb->n] = comb->rest;
2730 comb->rest = NULL_TREE;
2734 comb->rest = fold_build2 (MULT_EXPR, comb->type, comb->rest,
2735 build_int_cst_type (comb->type, scale));
2739 /* Adds ELT * SCALE to COMB. */
2742 aff_combination_add_elt (struct affine_tree_combination *comb, tree elt,
2743 unsigned HOST_WIDE_INT scale)
2750 for (i = 0; i < comb->n; i++)
2751 if (operand_equal_p (comb->elts[i], elt, 0))
2753 comb->coefs[i] = (comb->coefs[i] + scale) & comb->mask;
2758 comb->coefs[i] = comb->coefs[comb->n];
2759 comb->elts[i] = comb->elts[comb->n];
2763 gcc_assert (comb->n == MAX_AFF_ELTS - 1);
2764 comb->coefs[comb->n] = 1;
2765 comb->elts[comb->n] = comb->rest;
2766 comb->rest = NULL_TREE;
2771 if (comb->n < MAX_AFF_ELTS)
2773 comb->coefs[comb->n] = scale;
2774 comb->elts[comb->n] = elt;
2780 elt = fold_convert (comb->type, elt);
2782 elt = fold_build2 (MULT_EXPR, comb->type,
2783 fold_convert (comb->type, elt),
2784 build_int_cst_type (comb->type, scale));
2787 comb->rest = fold_build2 (PLUS_EXPR, comb->type, comb->rest, elt);
2792 /* Adds COMB2 to COMB1. */
2795 aff_combination_add (struct affine_tree_combination *comb1,
2796 struct affine_tree_combination *comb2)
2800 comb1->offset = (comb1->offset + comb2->offset) & comb1->mask;
2801 for (i = 0; i < comb2->n; i++)
2802 aff_combination_add_elt (comb1, comb2->elts[i], comb2->coefs[i]);
2804 aff_combination_add_elt (comb1, comb2->rest, 1);
2807 /* Splits EXPR into an affine combination of parts. */
2810 tree_to_aff_combination (tree expr, tree type,
2811 struct affine_tree_combination *comb)
2813 struct affine_tree_combination tmp;
2814 enum tree_code code;
2815 tree cst, core, toffset;
2816 HOST_WIDE_INT bitpos, bitsize;
2817 enum machine_mode mode;
2818 int unsignedp, volatilep;
2822 code = TREE_CODE (expr);
2826 aff_combination_const (comb, type, int_cst_value (expr));
2831 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
2832 tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp);
2833 if (code == MINUS_EXPR)
2834 aff_combination_scale (&tmp, -1);
2835 aff_combination_add (comb, &tmp);
2839 cst = TREE_OPERAND (expr, 1);
2840 if (TREE_CODE (cst) != INTEGER_CST)
2842 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
2843 aff_combination_scale (comb, int_cst_value (cst));
2847 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
2848 aff_combination_scale (comb, -1);
2852 core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
2853 &toffset, &mode, &unsignedp, &volatilep,
2855 if (bitpos % BITS_PER_UNIT != 0)
2857 aff_combination_const (comb, type, bitpos / BITS_PER_UNIT);
2858 core = build_fold_addr_expr (core);
2859 if (TREE_CODE (core) == ADDR_EXPR)
2860 aff_combination_add_elt (comb, core, 1);
2863 tree_to_aff_combination (core, type, &tmp);
2864 aff_combination_add (comb, &tmp);
2868 tree_to_aff_combination (toffset, type, &tmp);
2869 aff_combination_add (comb, &tmp);
2877 aff_combination_elt (comb, type, expr);
2880 /* Creates EXPR + ELT * SCALE in TYPE. MASK is the mask for width of TYPE. */
2883 add_elt_to_tree (tree expr, tree type, tree elt, unsigned HOST_WIDE_INT scale,
2884 unsigned HOST_WIDE_INT mask)
2886 enum tree_code code;
2889 elt = fold_convert (type, elt);
2896 return fold_build2 (PLUS_EXPR, type, expr, elt);
2902 return fold_build1 (NEGATE_EXPR, type, elt);
2904 return fold_build2 (MINUS_EXPR, type, expr, elt);
2908 return fold_build2 (MULT_EXPR, type, elt,
2909 build_int_cst_type (type, scale));
2911 if ((scale | (mask >> 1)) == mask)
2913 /* Scale is negative. */
2915 scale = (-scale) & mask;
2920 elt = fold_build2 (MULT_EXPR, type, elt,
2921 build_int_cst_type (type, scale));
2922 return fold_build2 (code, type, expr, elt);
2925 /* Copies the tree elements of COMB to ensure that they are not shared. */
2928 unshare_aff_combination (struct affine_tree_combination *comb)
2932 for (i = 0; i < comb->n; i++)
2933 comb->elts[i] = unshare_expr (comb->elts[i]);
2935 comb->rest = unshare_expr (comb->rest);
2938 /* Makes tree from the affine combination COMB. */
2941 aff_combination_to_tree (struct affine_tree_combination *comb)
2943 tree type = comb->type;
2944 tree expr = comb->rest;
2946 unsigned HOST_WIDE_INT off, sgn;
2948 /* Handle the special case produced by get_computation_aff when
2949 the type does not fit in HOST_WIDE_INT. */
2950 if (comb->n == 0 && comb->offset == 0)
2951 return fold_convert (type, expr);
2953 gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
2955 for (i = 0; i < comb->n; i++)
2956 expr = add_elt_to_tree (expr, type, comb->elts[i], comb->coefs[i],
2959 if ((comb->offset | (comb->mask >> 1)) == comb->mask)
2961 /* Offset is negative. */
2962 off = (-comb->offset) & comb->mask;
2970 return add_elt_to_tree (expr, type, build_int_cst_type (type, off), sgn,
2974 /* Determines the expression by that USE is expressed from induction variable
2975 CAND at statement AT in LOOP. The expression is stored in a decomposed
2976 form into AFF. Returns false if USE cannot be expressed using CAND. */
2979 get_computation_aff (struct loop *loop,
2980 struct iv_use *use, struct iv_cand *cand, tree at,
2981 struct affine_tree_combination *aff)
2983 tree ubase = use->iv->base;
2984 tree ustep = use->iv->step;
2985 tree cbase = cand->iv->base;
2986 tree cstep = cand->iv->step;
2987 tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
2991 unsigned HOST_WIDE_INT ustepi, cstepi;
2992 HOST_WIDE_INT ratioi;
2993 struct affine_tree_combination cbase_aff, expr_aff;
2994 tree cstep_orig = cstep, ustep_orig = ustep;
2996 if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
2998 /* We do not have a precision to express the values of use. */
3002 expr = var_at_stmt (loop, cand, at);
3004 if (TREE_TYPE (expr) != ctype)
3006 /* This may happen with the original ivs. */
3007 expr = fold_convert (ctype, expr);
3010 if (TYPE_UNSIGNED (utype))
3014 uutype = unsigned_type_for (utype);
3015 ubase = fold_convert (uutype, ubase);
3016 ustep = fold_convert (uutype, ustep);
3019 if (uutype != ctype)
3021 expr = fold_convert (uutype, expr);
3022 cbase = fold_convert (uutype, cbase);
3023 cstep = fold_convert (uutype, cstep);
3025 /* If the conversion is not noop, we must take it into account when
3026 considering the value of the step. */
3027 if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
3031 if (cst_and_fits_in_hwi (cstep_orig)
3032 && cst_and_fits_in_hwi (ustep_orig))
3034 ustepi = int_cst_value (ustep_orig);
3035 cstepi = int_cst_value (cstep_orig);
3037 if (!divide (TYPE_PRECISION (uutype), ustepi, cstepi, &ratioi))
3039 /* TODO maybe consider case when ustep divides cstep and the ratio is
3040 a power of 2 (so that the division is fast to execute)? We would
3041 need to be much more careful with overflows etc. then. */
3045 ratio = build_int_cst_type (uutype, ratioi);
3049 ratio = constant_multiple_of (uutype, ustep_orig, cstep_orig);
3053 /* Ratioi is only used to detect special cases when the multiplicative
3054 factor is 1 or -1, so if we cannot convert ratio to HOST_WIDE_INT,
3055 we may set it to 0. We prefer cst_and_fits_in_hwi/int_cst_value
3056 to integer_onep/integer_all_onesp, since the former ignores
3058 if (cst_and_fits_in_hwi (ratio))
3059 ratioi = int_cst_value (ratio);
3060 else if (integer_onep (ratio))
3062 else if (integer_all_onesp (ratio))
3068 /* We may need to shift the value if we are after the increment. */
3069 if (stmt_after_increment (loop, cand, at))
3070 cbase = fold_build2 (PLUS_EXPR, uutype, cbase, cstep);
3072 /* use = ubase - ratio * cbase + ratio * var.
3074 In general case ubase + ratio * (var - cbase) could be better (one less
3075 multiplication), but often it is possible to eliminate redundant parts
3076 of computations from (ubase - ratio * cbase) term, and if it does not
3077 happen, fold is able to apply the distributive law to obtain this form
3080 if (TYPE_PRECISION (uutype) > HOST_BITS_PER_WIDE_INT)
3082 /* Let's compute in trees and just return the result in AFF. This case
3083 should not be very common, and fold itself is not that bad either,
3084 so making the aff. functions more complicated to handle this case
3085 is not that urgent. */
3088 delta = fold_build2 (MINUS_EXPR, uutype, ubase, cbase);
3089 expr = fold_build2 (PLUS_EXPR, uutype, expr, delta);
3091 else if (ratioi == -1)
3093 delta = fold_build2 (PLUS_EXPR, uutype, ubase, cbase);
3094 expr = fold_build2 (MINUS_EXPR, uutype, delta, expr);
3098 delta = fold_build2 (MULT_EXPR, uutype, cbase, ratio);
3099 delta = fold_build2 (MINUS_EXPR, uutype, ubase, delta);
3100 expr = fold_build2 (MULT_EXPR, uutype, ratio, expr);
3101 expr = fold_build2 (PLUS_EXPR, uutype, delta, expr);
3112 /* If we got here, the types fits in HOST_WIDE_INT, thus it must be
3113 possible to compute ratioi. */
3114 gcc_assert (ratioi);
3116 tree_to_aff_combination (ubase, uutype, aff);
3117 tree_to_aff_combination (cbase, uutype, &cbase_aff);
3118 tree_to_aff_combination (expr, uutype, &expr_aff);
3119 aff_combination_scale (&cbase_aff, -ratioi);
3120 aff_combination_scale (&expr_aff, ratioi);
3121 aff_combination_add (aff, &cbase_aff);
3122 aff_combination_add (aff, &expr_aff);
3127 /* Determines the expression by that USE is expressed from induction variable
3128 CAND at statement AT in LOOP. The computation is unshared. */
3131 get_computation_at (struct loop *loop,
3132 struct iv_use *use, struct iv_cand *cand, tree at)
3134 struct affine_tree_combination aff;
3135 tree type = TREE_TYPE (use->iv->base);
3137 if (!get_computation_aff (loop, use, cand, at, &aff))
3139 unshare_aff_combination (&aff);
3140 return fold_convert (type, aff_combination_to_tree (&aff));
3143 /* Determines the expression by that USE is expressed from induction variable
3144 CAND in LOOP. The computation is unshared. */
3147 get_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand)
3149 return get_computation_at (loop, use, cand, use->stmt);
3152 /* Returns cost of addition in MODE. */
3155 add_cost (enum machine_mode mode)
3157 static unsigned costs[NUM_MACHINE_MODES];
3165 force_operand (gen_rtx_fmt_ee (PLUS, mode,
3166 gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
3167 gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 2)),
3172 cost = seq_cost (seq);
3178 if (dump_file && (dump_flags & TDF_DETAILS))
3179 fprintf (dump_file, "Addition in %s costs %d\n",
3180 GET_MODE_NAME (mode), cost);
3184 /* Entry in a hashtable of already known costs for multiplication. */
3187 HOST_WIDE_INT cst; /* The constant to multiply by. */
3188 enum machine_mode mode; /* In mode. */
3189 unsigned cost; /* The cost. */
3192 /* Counts hash value for the ENTRY. */
3195 mbc_entry_hash (const void *entry)
3197 const struct mbc_entry *e = entry;
3199 return 57 * (hashval_t) e->mode + (hashval_t) (e->cst % 877);
3202 /* Compares the hash table entries ENTRY1 and ENTRY2. */
3205 mbc_entry_eq (const void *entry1, const void *entry2)
3207 const struct mbc_entry *e1 = entry1;
3208 const struct mbc_entry *e2 = entry2;
3210 return (e1->mode == e2->mode
3211 && e1->cst == e2->cst);
3214 /* Returns cost of multiplication by constant CST in MODE. */
3217 multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode)
3219 static htab_t costs;
3220 struct mbc_entry **cached, act;
3225 costs = htab_create (100, mbc_entry_hash, mbc_entry_eq, free);
3229 cached = (struct mbc_entry **) htab_find_slot (costs, &act, INSERT);
3231 return (*cached)->cost;
3233 *cached = XNEW (struct mbc_entry);
3234 (*cached)->mode = mode;
3235 (*cached)->cst = cst;
3238 expand_mult (mode, gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
3239 gen_int_mode (cst, mode), NULL_RTX, 0);
3243 cost = seq_cost (seq);
3245 if (dump_file && (dump_flags & TDF_DETAILS))
3246 fprintf (dump_file, "Multiplication by %d in %s costs %d\n",
3247 (int) cst, GET_MODE_NAME (mode), cost);
3249 (*cached)->cost = cost;
3254 /* Returns true if multiplying by RATIO is allowed in address. */
3257 multiplier_allowed_in_address_p (HOST_WIDE_INT ratio)
3259 #define MAX_RATIO 128
3260 static sbitmap valid_mult;
3264 rtx reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
3268 valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1);
3269 sbitmap_zero (valid_mult);
3270 addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX);
3271 for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
3273 XEXP (addr, 1) = gen_int_mode (i, Pmode);
3274 if (memory_address_p (Pmode, addr))
3275 SET_BIT (valid_mult, i + MAX_RATIO);
3278 if (dump_file && (dump_flags & TDF_DETAILS))
3280 fprintf (dump_file, " allowed multipliers:");
3281 for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
3282 if (TEST_BIT (valid_mult, i + MAX_RATIO))
3283 fprintf (dump_file, " %d", (int) i);
3284 fprintf (dump_file, "\n");
3285 fprintf (dump_file, "\n");
3289 if (ratio > MAX_RATIO || ratio < -MAX_RATIO)
3292 return TEST_BIT (valid_mult, ratio + MAX_RATIO);
3295 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
3296 If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
3297 variable is omitted. The created memory accesses MODE.
3299 TODO -- there must be some better way. This all is quite crude. */
3302 get_address_cost (bool symbol_present, bool var_present,
3303 unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio)
3305 static bool initialized = false;
3306 static HOST_WIDE_INT rat, off;
3307 static HOST_WIDE_INT min_offset, max_offset;
3308 static unsigned costs[2][2][2][2];
3309 unsigned cost, acost;
3310 rtx seq, addr, base;
3311 bool offset_p, ratio_p;
3313 HOST_WIDE_INT s_offset;
3314 unsigned HOST_WIDE_INT mask;
3322 reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
3324 addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
3325 for (i = 1; i <= 1 << 20; i <<= 1)
3327 XEXP (addr, 1) = gen_int_mode (i, Pmode);
3328 if (!memory_address_p (Pmode, addr))
3331 max_offset = i >> 1;
3334 for (i = 1; i <= 1 << 20; i <<= 1)
3336 XEXP (addr, 1) = gen_int_mode (-i, Pmode);
3337 if (!memory_address_p (Pmode, addr))
3340 min_offset = -(i >> 1);
3342 if (dump_file && (dump_flags & TDF_DETAILS))
3344 fprintf (dump_file, "get_address_cost:\n");
3345 fprintf (dump_file, " min offset %d\n", (int) min_offset);
3346 fprintf (dump_file, " max offset %d\n", (int) max_offset);
3350 for (i = 2; i <= MAX_RATIO; i++)
3351 if (multiplier_allowed_in_address_p (i))
3358 bits = GET_MODE_BITSIZE (Pmode);
3359 mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
3361 if ((offset >> (bits - 1) & 1))
3366 offset_p = (s_offset != 0
3367 && min_offset <= s_offset && s_offset <= max_offset);
3368 ratio_p = (ratio != 1
3369 && multiplier_allowed_in_address_p (ratio));
3371 if (ratio != 1 && !ratio_p)
3372 cost += multiply_by_cost (ratio, Pmode);
3374 if (s_offset && !offset_p && !symbol_present)
3376 cost += add_cost (Pmode);
3380 acost = costs[symbol_present][var_present][offset_p][ratio_p];
3383 int old_cse_not_expected;
3386 addr = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
3387 reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
3389 addr = gen_rtx_fmt_ee (MULT, Pmode, addr, gen_int_mode (rat, Pmode));
3392 addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1);
3396 base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
3398 base = gen_rtx_fmt_e (CONST, Pmode,
3399 gen_rtx_fmt_ee (PLUS, Pmode,
3401 gen_int_mode (off, Pmode)));
3404 base = gen_int_mode (off, Pmode);
3409 addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, base);
3412 /* To avoid splitting addressing modes, pretend that no cse will
3414 old_cse_not_expected = cse_not_expected;
3415 cse_not_expected = true;
3416 addr = memory_address (Pmode, addr);
3417 cse_not_expected = old_cse_not_expected;
3421 acost = seq_cost (seq);
3422 acost += address_cost (addr, Pmode);
3426 costs[symbol_present][var_present][offset_p][ratio_p] = acost;
3429 return cost + acost;
3432 /* Estimates cost of forcing expression EXPR into a variable. */
3435 force_expr_to_var_cost (tree expr)
3437 static bool costs_initialized = false;
3438 static unsigned integer_cost;
3439 static unsigned symbol_cost;
3440 static unsigned address_cost;
3442 unsigned cost0, cost1, cost;
3443 enum machine_mode mode;
3445 if (!costs_initialized)
3447 tree var = create_tmp_var_raw (integer_type_node, "test_var");
3448 rtx x = gen_rtx_MEM (DECL_MODE (var),
3449 gen_rtx_SYMBOL_REF (Pmode, "test_var"));
3451 tree type = build_pointer_type (integer_type_node);
3453 integer_cost = computation_cost (build_int_cst_type (integer_type_node,
3456 SET_DECL_RTL (var, x);
3457 TREE_STATIC (var) = 1;
3458 addr = build1 (ADDR_EXPR, type, var);
3459 symbol_cost = computation_cost (addr) + 1;
3462 = computation_cost (build2 (PLUS_EXPR, type,
3464 build_int_cst_type (type, 2000))) + 1;
3465 if (dump_file && (dump_flags & TDF_DETAILS))
3467 fprintf (dump_file, "force_expr_to_var_cost:\n");
3468 fprintf (dump_file, " integer %d\n", (int) integer_cost);
3469 fprintf (dump_file, " symbol %d\n", (int) symbol_cost);
3470 fprintf (dump_file, " address %d\n", (int) address_cost);
3471 fprintf (dump_file, " other %d\n", (int) target_spill_cost);
3472 fprintf (dump_file, "\n");
3475 costs_initialized = true;
3480 if (SSA_VAR_P (expr))
3483 if (TREE_INVARIANT (expr))
3485 if (TREE_CODE (expr) == INTEGER_CST)
3486 return integer_cost;
3488 if (TREE_CODE (expr) == ADDR_EXPR)
3490 tree obj = TREE_OPERAND (expr, 0);
3492 if (TREE_CODE (obj) == VAR_DECL
3493 || TREE_CODE (obj) == PARM_DECL
3494 || TREE_CODE (obj) == RESULT_DECL)
3498 return address_cost;
3501 switch (TREE_CODE (expr))
3506 op0 = TREE_OPERAND (expr, 0);
3507 op1 = TREE_OPERAND (expr, 1);
3511 if (is_gimple_val (op0))
3514 cost0 = force_expr_to_var_cost (op0);
3516 if (is_gimple_val (op1))
3519 cost1 = force_expr_to_var_cost (op1);
3524 /* Just an arbitrary value, FIXME. */
3525 return target_spill_cost;
3528 mode = TYPE_MODE (TREE_TYPE (expr));
3529 switch (TREE_CODE (expr))
3533 cost = add_cost (mode);
3537 if (cst_and_fits_in_hwi (op0))
3538 cost = multiply_by_cost (int_cst_value (op0), mode);
3539 else if (cst_and_fits_in_hwi (op1))
3540 cost = multiply_by_cost (int_cst_value (op1), mode);
3542 return target_spill_cost;
3552 /* Bound the cost by target_spill_cost. The parts of complicated
3553 computations often are either loop invariant or at least can
3554 be shared between several iv uses, so letting this grow without
3555 limits would not give reasonable results. */
3556 return cost < target_spill_cost ? cost : target_spill_cost;
3559 /* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
3560 invariants the computation depends on. */
3563 force_var_cost (struct ivopts_data *data,
3564 tree expr, bitmap *depends_on)
3568 fd_ivopts_data = data;
3569 walk_tree (&expr, find_depends, depends_on, NULL);
3572 return force_expr_to_var_cost (expr);
3575 /* Estimates cost of expressing address ADDR as var + symbol + offset. The
3576 value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
3577 to false if the corresponding part is missing. DEPENDS_ON is a set of the
3578 invariants the computation depends on. */
3581 split_address_cost (struct ivopts_data *data,
3582 tree addr, bool *symbol_present, bool *var_present,
3583 unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
3586 HOST_WIDE_INT bitsize;
3587 HOST_WIDE_INT bitpos;
3589 enum machine_mode mode;
3590 int unsignedp, volatilep;
3592 core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode,
3593 &unsignedp, &volatilep, false);
3596 || bitpos % BITS_PER_UNIT != 0
3597 || TREE_CODE (core) != VAR_DECL)
3599 *symbol_present = false;
3600 *var_present = true;
3601 fd_ivopts_data = data;
3602 walk_tree (&addr, find_depends, depends_on, NULL);
3603 return target_spill_cost;
3606 *offset += bitpos / BITS_PER_UNIT;
3607 if (TREE_STATIC (core)
3608 || DECL_EXTERNAL (core))
3610 *symbol_present = true;
3611 *var_present = false;
3615 *symbol_present = false;
3616 *var_present = true;
3620 /* Estimates cost of expressing difference of addresses E1 - E2 as
3621 var + symbol + offset. The value of offset is added to OFFSET,
3622 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3623 part is missing. DEPENDS_ON is a set of the invariants the computation
3627 ptr_difference_cost (struct ivopts_data *data,
3628 tree e1, tree e2, bool *symbol_present, bool *var_present,
3629 unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
3631 HOST_WIDE_INT diff = 0;
3634 gcc_assert (TREE_CODE (e1) == ADDR_EXPR);
3636 if (ptr_difference_const (e1, e2, &diff))
3639 *symbol_present = false;
3640 *var_present = false;
3644 if (e2 == integer_zero_node)
3645 return split_address_cost (data, TREE_OPERAND (e1, 0),
3646 symbol_present, var_present, offset, depends_on);
3648 *symbol_present = false;
3649 *var_present = true;
3651 cost = force_var_cost (data, e1, depends_on);
3652 cost += force_var_cost (data, e2, depends_on);
3653 cost += add_cost (Pmode);
3658 /* Estimates cost of expressing difference E1 - E2 as
3659 var + symbol + offset. The value of offset is added to OFFSET,
3660 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3661 part is missing. DEPENDS_ON is a set of the invariants the computation
3665 difference_cost (struct ivopts_data *data,
3666 tree e1, tree e2, bool *symbol_present, bool *var_present,
3667 unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
3670 enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
3671 unsigned HOST_WIDE_INT off1, off2;
3673 e1 = strip_offset (e1, &off1);
3674 e2 = strip_offset (e2, &off2);
3675 *offset += off1 - off2;
3680 if (TREE_CODE (e1) == ADDR_EXPR)
3681 return ptr_difference_cost (data, e1, e2, symbol_present, var_present, offset,
3683 *symbol_present = false;
3685 if (operand_equal_p (e1, e2, 0))
3687 *var_present = false;
3690 *var_present = true;
3692 return force_var_cost (data, e1, depends_on);
3696 cost = force_var_cost (data, e2, depends_on);
3697 cost += multiply_by_cost (-1, mode);
3702 cost = force_var_cost (data, e1, depends_on);
3703 cost += force_var_cost (data, e2, depends_on);
3704 cost += add_cost (mode);
3709 /* Determines the cost of the computation by that USE is expressed
3710 from induction variable CAND. If ADDRESS_P is true, we just need
3711 to create an address from it, otherwise we want to get it into
3712 register. A set of invariants we depend on is stored in
3713 DEPENDS_ON. AT is the statement at that the value is computed. */
3716 get_computation_cost_at (struct ivopts_data *data,
3717 struct iv_use *use, struct iv_cand *cand,
3718 bool address_p, bitmap *depends_on, tree at)
3720 tree ubase = use->iv->base, ustep = use->iv->step;
3722 tree utype = TREE_TYPE (ubase), ctype;
3723 unsigned HOST_WIDE_INT ustepi, cstepi, offset = 0;
3724 HOST_WIDE_INT ratio, aratio;
3725 bool var_present, symbol_present;
3726 unsigned cost = 0, n_sums;
3730 /* Only consider real candidates. */
3734 cbase = cand->iv->base;
3735 cstep = cand->iv->step;
3736 ctype = TREE_TYPE (cbase);
3738 if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
3740 /* We do not have a precision to express the values of use. */
3746 /* Do not try to express address of an object with computation based
3747 on address of a different object. This may cause problems in rtl
3748 level alias analysis (that does not expect this to be happening,
3749 as this is illegal in C), and would be unlikely to be useful
3751 if (use->iv->base_object
3752 && cand->iv->base_object
3753 && !operand_equal_p (use->iv->base_object, cand->iv->base_object, 0))
3757 if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
3759 /* TODO -- add direct handling of this case. */
3763 /* CSTEPI is removed from the offset in case statement is after the
3764 increment. If the step is not constant, we use zero instead.
3765 This is a bit imprecise (there is the extra addition), but
3766 redundancy elimination is likely to transform the code so that
3767 it uses value of the variable before increment anyway,
3768 so it is not that much unrealistic. */
3769 if (cst_and_fits_in_hwi (cstep))
3770 cstepi = int_cst_value (cstep);
3774 if (cst_and_fits_in_hwi (ustep)
3775 && cst_and_fits_in_hwi (cstep))
3777 ustepi = int_cst_value (ustep);
3779 if (!divide (TYPE_PRECISION (utype), ustepi, cstepi, &ratio))
3786 rat = constant_multiple_of (utype, ustep, cstep);
3791 if (cst_and_fits_in_hwi (rat))
3792 ratio = int_cst_value (rat);
3793 else if (integer_onep (rat))
3795 else if (integer_all_onesp (rat))
3801 /* use = ubase + ratio * (var - cbase). If either cbase is a constant
3802 or ratio == 1, it is better to handle this like
3804 ubase - ratio * cbase + ratio * var
3806 (also holds in the case ratio == -1, TODO. */
3808 if (cst_and_fits_in_hwi (cbase))
3810 offset = - ratio * int_cst_value (cbase);
3811 cost += difference_cost (data,
3812 ubase, integer_zero_node,
3813 &symbol_present, &var_present, &offset,
3816 else if (ratio == 1)
3818 cost += difference_cost (data,
3820 &symbol_present, &var_present, &offset,
3825 cost += force_var_cost (data, cbase, depends_on);
3826 cost += add_cost (TYPE_MODE (ctype));
3827 cost += difference_cost (data,
3828 ubase, integer_zero_node,
3829 &symbol_present, &var_present, &offset,
3833 /* If we are after the increment, the value of the candidate is higher by
3835 if (stmt_after_increment (data->current_loop, cand, at))
3836 offset -= ratio * cstepi;
3838 /* Now the computation is in shape symbol + var1 + const + ratio * var2.
3839 (symbol/var/const parts may be omitted). If we are looking for an address,
3840 find the cost of addressing this. */
3842 return cost + get_address_cost (symbol_present, var_present, offset, ratio);
3844 /* Otherwise estimate the costs for computing the expression. */
3845 aratio = ratio > 0 ? ratio : -ratio;
3846 if (!symbol_present && !var_present && !offset)
3849 cost += multiply_by_cost (ratio, TYPE_MODE (ctype));
3855 cost += multiply_by_cost (aratio, TYPE_MODE (ctype));
3859 /* Symbol + offset should be compile-time computable. */
3860 && (symbol_present || offset))
3863 return cost + n_sums * add_cost (TYPE_MODE (ctype));
3867 /* Just get the expression, expand it and measure the cost. */
3868 tree comp = get_computation_at (data->current_loop, use, cand, at);
3874 comp = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (comp)), comp);
3876 return computation_cost (comp);
3880 /* Determines the cost of the computation by that USE is expressed
3881 from induction variable CAND. If ADDRESS_P is true, we just need
3882 to create an address from it, otherwise we want to get it into
3883 register. A set of invariants we depend on is stored in
3887 get_computation_cost (struct ivopts_data *data,
3888 struct iv_use *use, struct iv_cand *cand,
3889 bool address_p, bitmap *depends_on)
3891 return get_computation_cost_at (data,
3892 use, cand, address_p, depends_on, use->stmt);
3895 /* Determines cost of basing replacement of USE on CAND in a generic
3899 determine_use_iv_cost_generic (struct ivopts_data *data,
3900 struct iv_use *use, struct iv_cand *cand)
3905 /* The simple case first -- if we need to express value of the preserved
3906 original biv, the cost is 0. This also prevents us from counting the
3907 cost of increment twice -- once at this use and once in the cost of
3909 if (cand->pos == IP_ORIGINAL
3910 && cand->incremented_at == use->stmt)
3912 set_use_iv_cost (data, use, cand, 0, NULL, NULL_TREE);
3916 cost = get_computation_cost (data, use, cand, false, &depends_on);
3917 set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
3919 return cost != INFTY;
3922 /* Determines cost of basing replacement of USE on CAND in an address. */
3925 determine_use_iv_cost_address (struct ivopts_data *data,
3926 struct iv_use *use, struct iv_cand *cand)
3929 unsigned cost = get_computation_cost (data, use, cand, true, &depends_on);
3931 set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
3933 return cost != INFTY;
3936 /* Computes value of induction variable IV in iteration NITER. */
3939 iv_value (struct iv *iv, tree niter)
3942 tree type = TREE_TYPE (iv->base);
3944 niter = fold_convert (type, niter);
3945 val = fold_build2 (MULT_EXPR, type, iv->step, niter);
3947 return fold_build2 (PLUS_EXPR, type, iv->base, val);
3950 /* Computes value of candidate CAND at position AT in iteration NITER. */
3953 cand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter)
3955 tree val = iv_value (cand->iv, niter);
3956 tree type = TREE_TYPE (cand->iv->base);
3958 if (stmt_after_increment (loop, cand, at))
3959 val = fold_build2 (PLUS_EXPR, type, val, cand->iv->step);
3964 /* Returns period of induction variable iv. */
3967 iv_period (struct iv *iv)
3969 tree step = iv->step, period, type;
3972 gcc_assert (step && TREE_CODE (step) == INTEGER_CST);
3974 /* Period of the iv is gcd (step, type range). Since type range is power
3975 of two, it suffices to determine the maximum power of two that divides
3977 pow2div = num_ending_zeros (step);
3978 type = unsigned_type_for (TREE_TYPE (step));
3980 period = build_low_bits_mask (type,
3981 (TYPE_PRECISION (type)
3982 - tree_low_cst (pow2div, 1)));
3987 /* Returns the comparison operator used when eliminating the iv USE. */
3989 static enum tree_code
3990 iv_elimination_compare (struct ivopts_data *data, struct iv_use *use)
3992 struct loop *loop = data->current_loop;
3996 ex_bb = bb_for_stmt (use->stmt);
3997 exit = EDGE_SUCC (ex_bb, 0);
3998 if (flow_bb_inside_loop_p (loop, exit->dest))
3999 exit = EDGE_SUCC (ex_bb, 1);
4001 return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
4004 /* Check whether it is possible to express the condition in USE by comparison
4005 of candidate CAND. If so, store the value compared with to BOUND. */
4008 may_eliminate_iv (struct ivopts_data *data,
4009 struct iv_use *use, struct iv_cand *cand, tree *bound)
4013 struct tree_niter_desc *niter;
4015 tree wider_type, period, per_type;
4016 struct loop *loop = data->current_loop;
4018 if (TREE_CODE (cand->iv->step) != INTEGER_CST)
4021 /* For now works only for exits that dominate the loop latch. TODO -- extend
4022 for other conditions inside loop body. */
4023 ex_bb = bb_for_stmt (use->stmt);
4024 if (use->stmt != last_stmt (ex_bb)
4025 || TREE_CODE (use->stmt) != COND_EXPR)
4027 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, ex_bb))
4030 exit = EDGE_SUCC (ex_bb, 0);
4031 if (flow_bb_inside_loop_p (loop, exit->dest))
4032 exit = EDGE_SUCC (ex_bb, 1);
4033 if (flow_bb_inside_loop_p (loop, exit->dest))
4036 niter = niter_for_exit (data, exit);
4038 || !zero_p (niter->may_be_zero))
4042 nit_type = TREE_TYPE (nit);
4044 /* Determine whether we may use the variable to test whether niter iterations
4045 elapsed. This is the case iff the period of the induction variable is
4046 greater than the number of iterations. */
4047 period = iv_period (cand->iv);
4050 per_type = TREE_TYPE (period);
4052 wider_type = TREE_TYPE (period);
4053 if (TYPE_PRECISION (nit_type) < TYPE_PRECISION (per_type))
4054 wider_type = per_type;
4056 wider_type = nit_type;
4058 if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
4059 fold_convert (wider_type, period),
4060 fold_convert (wider_type, nit))))
4063 *bound = cand_value_at (loop, cand, use->stmt, nit);
4067 /* Determines cost of basing replacement of USE on CAND in a condition. */
4070 determine_use_iv_cost_condition (struct ivopts_data *data,
4071 struct iv_use *use, struct iv_cand *cand)
4073 tree bound = NULL_TREE, op, cond;
4074 bitmap depends_on = NULL;
4077 /* Only consider real candidates. */
4080 set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE);
4084 if (may_eliminate_iv (data, use, cand, &bound))
4086 cost = force_var_cost (data, bound, &depends_on);
4088 set_use_iv_cost (data, use, cand, cost, depends_on, bound);
4089 return cost != INFTY;
4092 /* The induction variable elimination failed; just express the original
4093 giv. If it is compared with an invariant, note that we cannot get
4095 cost = get_computation_cost (data, use, cand, false, &depends_on);
4098 if (TREE_CODE (cond) != SSA_NAME)
4100 op = TREE_OPERAND (cond, 0);
4101 if (TREE_CODE (op) == SSA_NAME && !zero_p (get_iv (data, op)->step))
4102 op = TREE_OPERAND (cond, 1);
4103 if (TREE_CODE (op) == SSA_NAME)
4105 op = get_iv (data, op)->base;
4106 fd_ivopts_data = data;
4107 walk_tree (&op, find_depends, &depends_on, NULL);
4111 set_use_iv_cost (data, use, cand, cost, depends_on, NULL);
4112 return cost != INFTY;
4115 /* Checks whether it is possible to replace the final value of USE by
4116 a direct computation. If so, the formula is stored to *VALUE. */
4119 may_replace_final_value (struct ivopts_data *data, struct iv_use *use,
4122 struct loop *loop = data->current_loop;
4124 struct tree_niter_desc *niter;
4126 exit = single_dom_exit (loop);
4130 gcc_assert (dominated_by_p (CDI_DOMINATORS, exit->src,
4131 bb_for_stmt (use->stmt)));
4133 niter = niter_for_single_dom_exit (data);
4135 || !zero_p (niter->may_be_zero))
4138 *value = iv_value (use->iv, niter->niter);
4143 /* Determines cost of replacing final value of USE using CAND. */
4146 determine_use_iv_cost_outer (struct ivopts_data *data,
4147 struct iv_use *use, struct iv_cand *cand)
4152 tree value = NULL_TREE;
4153 struct loop *loop = data->current_loop;
4155 /* The simple case first -- if we need to express value of the preserved
4156 original biv, the cost is 0. This also prevents us from counting the
4157 cost of increment twice -- once at this use and once in the cost of
4159 if (cand->pos == IP_ORIGINAL
4160 && cand->incremented_at == use->stmt)
4162 set_use_iv_cost (data, use, cand, 0, NULL, NULL_TREE);
4168 if (!may_replace_final_value (data, use, &value))
4170 set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE);
4175 cost = force_var_cost (data, value, &depends_on);
4177 cost /= AVG_LOOP_NITER (loop);
4179 set_use_iv_cost (data, use, cand, cost, depends_on, value);
4180 return cost != INFTY;
4183 exit = single_dom_exit (loop);
4186 /* If there is just a single exit, we may use value of the candidate
4187 after we take it to determine the value of use. */
4188 cost = get_computation_cost_at (data, use, cand, false, &depends_on,
4189 last_stmt (exit->src));
4191 cost /= AVG_LOOP_NITER (loop);
4195 /* Otherwise we just need to compute the iv. */
4196 cost = get_computation_cost (data, use, cand, false, &depends_on);
4199 set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
4201 return cost != INFTY;
4204 /* Determines cost of basing replacement of USE on CAND. Returns false
4205 if USE cannot be based on CAND. */
4208 determine_use_iv_cost (struct ivopts_data *data,
4209 struct iv_use *use, struct iv_cand *cand)
4213 case USE_NONLINEAR_EXPR:
4214 return determine_use_iv_cost_generic (data, use, cand);
4217 return determine_use_iv_cost_outer (data, use, cand);
4220 return determine_use_iv_cost_address (data, use, cand);
4223 return determine_use_iv_cost_condition (data, use, cand);
4230 /* Determines costs of basing the use of the iv on an iv candidate. */
4233 determine_use_iv_costs (struct ivopts_data *data)
4237 struct iv_cand *cand;
4238 bitmap to_clear = BITMAP_ALLOC (NULL);
4240 alloc_use_cost_map (data);
4242 for (i = 0; i < n_iv_uses (data); i++)
4244 use = iv_use (data, i);
4246 if (data->consider_all_candidates)
4248 for (j = 0; j < n_iv_cands (data); j++)
4250 cand = iv_cand (data, j);
4251 determine_use_iv_cost (data, use, cand);
4258 EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi)
4260 cand = iv_cand (data, j);
4261 if (!determine_use_iv_cost (data, use, cand))
4262 bitmap_set_bit (to_clear, j);
4265 /* Remove the candidates for that the cost is infinite from
4266 the list of related candidates. */
4267 bitmap_and_compl_into (use->related_cands, to_clear);
4268 bitmap_clear (to_clear);
4272 BITMAP_FREE (to_clear);
4274 if (dump_file && (dump_flags & TDF_DETAILS))
4276 fprintf (dump_file, "Use-candidate costs:\n");
4278 for (i = 0; i < n_iv_uses (data); i++)
4280 use = iv_use (data, i);
4282 fprintf (dump_file, "Use %d:\n", i);
4283 fprintf (dump_file, " cand\tcost\tdepends on\n");
4284 for (j = 0; j < use->n_map_members; j++)
4286 if (!use->cost_map[j].cand
4287 || use->cost_map[j].cost == INFTY)
4290 fprintf (dump_file, " %d\t%d\t",
4291 use->cost_map[j].cand->id,
4292 use->cost_map[j].cost);
4293 if (use->cost_map[j].depends_on)
4294 bitmap_print (dump_file,
4295 use->cost_map[j].depends_on, "","");
4296 fprintf (dump_file, "\n");
4299 fprintf (dump_file, "\n");
4301 fprintf (dump_file, "\n");
4305 /* Determines cost of the candidate CAND. */
4308 determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
4310 unsigned cost_base, cost_step;
4319 /* There are two costs associated with the candidate -- its increment
4320 and its initialization. The second is almost negligible for any loop
4321 that rolls enough, so we take it just very little into account. */
4323 base = cand->iv->base;
4324 cost_base = force_var_cost (data, base, NULL);
4325 cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
4327 cand->cost = cost_step + cost_base / AVG_LOOP_NITER (current_loop);
4329 /* Prefer the original iv unless we may gain something by replacing it;
4330 this is not really relevant for artificial ivs created by other
4332 if (cand->pos == IP_ORIGINAL
4333 && !DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
4336 /* Prefer not to insert statements into latch unless there are some
4337 already (so that we do not create unnecessary jumps). */
4338 if (cand->pos == IP_END
4339 && empty_block_p (ip_end_pos (data->current_loop)))
4343 /* Determines costs of computation of the candidates. */
4346 determine_iv_costs (struct ivopts_data *data)
4350 if (dump_file && (dump_flags & TDF_DETAILS))
4352 fprintf (dump_file, "Candidate costs:\n");
4353 fprintf (dump_file, " cand\tcost\n");
4356 for (i = 0; i < n_iv_cands (data); i++)
4358 struct iv_cand *cand = iv_cand (data, i);
4360 determine_iv_cost (data, cand);
4362 if (dump_file && (dump_flags & TDF_DETAILS))
4363 fprintf (dump_file, " %d\t%d\n", i, cand->cost);
4366 if (dump_file && (dump_flags & TDF_DETAILS))
4367 fprintf (dump_file, "\n");
4370 /* Calculates cost for having SIZE induction variables. */
4373 ivopts_global_cost_for_size (struct ivopts_data *data, unsigned size)
4375 return global_cost_for_size (size,
4376 loop_data (data->current_loop)->regs_used,
4380 /* For each size of the induction variable set determine the penalty. */
4383 determine_set_costs (struct ivopts_data *data)
4387 struct loop *loop = data->current_loop;
4390 /* We use the following model (definitely improvable, especially the
4391 cost function -- TODO):
4393 We estimate the number of registers available (using MD data), name it A.
4395 We estimate the number of registers used by the loop, name it U. This
4396 number is obtained as the number of loop phi nodes (not counting virtual
4397 registers and bivs) + the number of variables from outside of the loop.
4399 We set a reserve R (free regs that are used for temporary computations,
4400 etc.). For now the reserve is a constant 3.
4402 Let I be the number of induction variables.
4404 -- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
4405 make a lot of ivs without a reason).
4406 -- if A - R < U + I <= A, the cost is I * PRES_COST
4407 -- if U + I > A, the cost is I * PRES_COST and
4408 number of uses * SPILL_COST * (U + I - A) / (U + I) is added. */
4410 if (dump_file && (dump_flags & TDF_DETAILS))
4412 fprintf (dump_file, "Global costs:\n");
4413 fprintf (dump_file, " target_avail_regs %d\n", target_avail_regs);
4414 fprintf (dump_file, " target_small_cost %d\n", target_small_cost);
4415 fprintf (dump_file, " target_pres_cost %d\n", target_pres_cost);
4416 fprintf (dump_file, " target_spill_cost %d\n", target_spill_cost);
4420 for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
4422 op = PHI_RESULT (phi);
4424 if (!is_gimple_reg (op))
4427 if (get_iv (data, op))
4433 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
4435 struct version_info *info = ver_info (data, j);
4437 if (info->inv_id && info->has_nonlin_use)
4441 loop_data (loop)->regs_used = n;
4442 if (dump_file && (dump_flags & TDF_DETAILS))
4443 fprintf (dump_file, " regs_used %d\n", n);
4445 if (dump_file && (dump_flags & TDF_DETAILS))
4447 fprintf (dump_file, " cost for size:\n");
4448 fprintf (dump_file, " ivs\tcost\n");
4449 for (j = 0; j <= 2 * target_avail_regs; j++)
4450 fprintf (dump_file, " %d\t%d\n", j,
4451 ivopts_global_cost_for_size (data, j));
4452 fprintf (dump_file, "\n");
4456 /* Returns true if A is a cheaper cost pair than B. */
4459 cheaper_cost_pair (struct cost_pair *a, struct cost_pair *b)
4467 if (a->cost < b->cost)
4470 if (a->cost > b->cost)
4473 /* In case the costs are the same, prefer the cheaper candidate. */
4474 if (a->cand->cost < b->cand->cost)
4480 /* Computes the cost field of IVS structure. */
4483 iv_ca_recount_cost (struct ivopts_data *data, struct iv_ca *ivs)
4487 cost += ivs->cand_use_cost;
4488 cost += ivs->cand_cost;
4489 cost += ivopts_global_cost_for_size (data, ivs->n_regs);
4494 /* Remove invariants in set INVS to set IVS. */
4497 iv_ca_set_remove_invariants (struct iv_ca *ivs, bitmap invs)
4505 EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
4507 ivs->n_invariant_uses[iid]--;
4508 if (ivs->n_invariant_uses[iid] == 0)
4513 /* Set USE not to be expressed by any candidate in IVS. */
4516 iv_ca_set_no_cp (struct ivopts_data *data, struct iv_ca *ivs,
4519 unsigned uid = use->id, cid;
4520 struct cost_pair *cp;
4522 cp = ivs->cand_for_use[uid];
4528 ivs->cand_for_use[uid] = NULL;
4529 ivs->n_cand_uses[cid]--;
4531 if (ivs->n_cand_uses[cid] == 0)
4533 bitmap_clear_bit (ivs->cands, cid);
4534 /* Do not count the pseudocandidates. */
4538 ivs->cand_cost -= cp->cand->cost;
4540 iv_ca_set_remove_invariants (ivs, cp->cand->depends_on);
4543 ivs->cand_use_cost -= cp->cost;
4545 iv_ca_set_remove_invariants (ivs, cp->depends_on);
4546 iv_ca_recount_cost (data, ivs);
4549 /* Add invariants in set INVS to set IVS. */
4552 iv_ca_set_add_invariants (struct iv_ca *ivs, bitmap invs)
4560 EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
4562 ivs->n_invariant_uses[iid]++;
4563 if (ivs->n_invariant_uses[iid] == 1)
4568 /* Set cost pair for USE in set IVS to CP. */
4571 iv_ca_set_cp (struct ivopts_data *data, struct iv_ca *ivs,
4572 struct iv_use *use, struct cost_pair *cp)
4574 unsigned uid = use->id, cid;
4576 if (ivs->cand_for_use[uid] == cp)
4579 if (ivs->cand_for_use[uid])
4580 iv_ca_set_no_cp (data, ivs, use);
4587 ivs->cand_for_use[uid] = cp;
4588 ivs->n_cand_uses[cid]++;
4589 if (ivs->n_cand_uses[cid] == 1)
4591 bitmap_set_bit (ivs->cands, cid);
4592 /* Do not count the pseudocandidates. */
4596 ivs->cand_cost += cp->cand->cost;
4598 iv_ca_set_add_invariants (ivs, cp->cand->depends_on);
4601 ivs->cand_use_cost += cp->cost;
4602 iv_ca_set_add_invariants (ivs, cp->depends_on);
4603 iv_ca_recount_cost (data, ivs);
4607 /* Extend set IVS by expressing USE by some of the candidates in it
4611 iv_ca_add_use (struct ivopts_data *data, struct iv_ca *ivs,
4614 struct cost_pair *best_cp = NULL, *cp;
4618 gcc_assert (ivs->upto >= use->id);
4620 if (ivs->upto == use->id)
4626 EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
4628 cp = get_use_iv_cost (data, use, iv_cand (data, i));
4630 if (cheaper_cost_pair (cp, best_cp))
4634 iv_ca_set_cp (data, ivs, use, best_cp);
4637 /* Get cost for assignment IVS. */
4640 iv_ca_cost (struct iv_ca *ivs)
4642 return (ivs->bad_uses ? INFTY : ivs->cost);
4645 /* Returns true if all dependences of CP are among invariants in IVS. */
4648 iv_ca_has_deps (struct iv_ca *ivs, struct cost_pair *cp)
4653 if (!cp->depends_on)
4656 EXECUTE_IF_SET_IN_BITMAP (cp->depends_on, 0, i, bi)
4658 if (ivs->n_invariant_uses[i] == 0)
4665 /* Creates change of expressing USE by NEW_CP instead of OLD_CP and chains
4666 it before NEXT_CHANGE. */
4668 static struct iv_ca_delta *
4669 iv_ca_delta_add (struct iv_use *use, struct cost_pair *old_cp,
4670 struct cost_pair *new_cp, struct iv_ca_delta *next_change)
4672 struct iv_ca_delta *change = XNEW (struct iv_ca_delta);
4675 change->old_cp = old_cp;
4676 change->new_cp = new_cp;
4677 change->next_change = next_change;
4682 /* Joins two lists of changes L1 and L2. Destructive -- old lists
4685 static struct iv_ca_delta *
4686 iv_ca_delta_join (struct iv_ca_delta *l1, struct iv_ca_delta *l2)
4688 struct iv_ca_delta *last;
4696 for (last = l1; last->next_change; last = last->next_change)
4698 last->next_change = l2;
4703 /* Returns candidate by that USE is expressed in IVS. */
4705 static struct cost_pair *
4706 iv_ca_cand_for_use (struct iv_ca *ivs, struct iv_use *use)
4708 return ivs->cand_for_use[use->id];
4711 /* Reverse the list of changes DELTA, forming the inverse to it. */
4713 static struct iv_ca_delta *
4714 iv_ca_delta_reverse (struct iv_ca_delta *delta)
4716 struct iv_ca_delta *act, *next, *prev = NULL;
4717 struct cost_pair *tmp;
4719 for (act = delta; act; act = next)
4721 next = act->next_change;
4722 act->next_change = prev;
4726 act->old_cp = act->new_cp;
4733 /* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
4734 reverted instead. */
4737 iv_ca_delta_commit (struct ivopts_data *data, struct iv_ca *ivs,
4738 struct iv_ca_delta *delta, bool forward)
4740 struct cost_pair *from, *to;
4741 struct iv_ca_delta *act;
4744 delta = iv_ca_delta_reverse (delta);
4746 for (act = delta; act; act = act->next_change)
4750 gcc_assert (iv_ca_cand_for_use (ivs, act->use) == from);
4751 iv_ca_set_cp (data, ivs, act->use, to);
4755 iv_ca_delta_reverse (delta);
4758 /* Returns true if CAND is used in IVS. */
4761 iv_ca_cand_used_p (struct iv_ca *ivs, struct iv_cand *cand)
4763 return ivs->n_cand_uses[cand->id] > 0;
4766 /* Returns number of induction variable candidates in the set IVS. */
4769 iv_ca_n_cands (struct iv_ca *ivs)
4771 return ivs->n_cands;
4774 /* Free the list of changes DELTA. */
4777 iv_ca_delta_free (struct iv_ca_delta **delta)
4779 struct iv_ca_delta *act, *next;
4781 for (act = *delta; act; act = next)
4783 next = act->next_change;
4790 /* Allocates new iv candidates assignment. */
4792 static struct iv_ca *
4793 iv_ca_new (struct ivopts_data *data)
4795 struct iv_ca *nw = XNEW (struct iv_ca);
4799 nw->cand_for_use = XCNEWVEC (struct cost_pair *, n_iv_uses (data));
4800 nw->n_cand_uses = XCNEWVEC (unsigned, n_iv_cands (data));
4801 nw->cands = BITMAP_ALLOC (NULL);
4804 nw->cand_use_cost = 0;
4806 nw->n_invariant_uses = XCNEWVEC (unsigned, data->max_inv_id + 1);
4812 /* Free memory occupied by the set IVS. */
4815 iv_ca_free (struct iv_ca **ivs)
4817 free ((*ivs)->cand_for_use);
4818 free ((*ivs)->n_cand_uses);
4819 BITMAP_FREE ((*ivs)->cands);
4820 free ((*ivs)->n_invariant_uses);
4825 /* Dumps IVS to FILE. */
4828 iv_ca_dump (struct ivopts_data *data, FILE *file, struct iv_ca *ivs)
4830 const char *pref = " invariants ";
4833 fprintf (file, " cost %d\n", iv_ca_cost (ivs));
4834 bitmap_print (file, ivs->cands, " candidates ","\n");
4836 for (i = 1; i <= data->max_inv_id; i++)
4837 if (ivs->n_invariant_uses[i])
4839 fprintf (file, "%s%d", pref, i);
4842 fprintf (file, "\n");
4845 /* Try changing candidate in IVS to CAND for each use. Return cost of the
4846 new set, and store differences in DELTA. Number of induction variables
4847 in the new set is stored to N_IVS. */
4850 iv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs,
4851 struct iv_cand *cand, struct iv_ca_delta **delta,
4856 struct cost_pair *old_cp, *new_cp;
4859 for (i = 0; i < ivs->upto; i++)
4861 use = iv_use (data, i);
4862 old_cp = iv_ca_cand_for_use (ivs, use);
4865 && old_cp->cand == cand)
4868 new_cp = get_use_iv_cost (data, use, cand);
4872 if (!iv_ca_has_deps (ivs, new_cp))
4875 if (!cheaper_cost_pair (new_cp, old_cp))
4878 *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
4881 iv_ca_delta_commit (data, ivs, *delta, true);
4882 cost = iv_ca_cost (ivs);
4884 *n_ivs = iv_ca_n_cands (ivs);
4885 iv_ca_delta_commit (data, ivs, *delta, false);
4890 /* Try narrowing set IVS by removing CAND. Return the cost of
4891 the new set and store the differences in DELTA. */
4894 iv_ca_narrow (struct ivopts_data *data, struct iv_ca *ivs,
4895 struct iv_cand *cand, struct iv_ca_delta **delta)
4899 struct cost_pair *old_cp, *new_cp, *cp;
4901 struct iv_cand *cnd;
4905 for (i = 0; i < n_iv_uses (data); i++)
4907 use = iv_use (data, i);
4909 old_cp = iv_ca_cand_for_use (ivs, use);
4910 if (old_cp->cand != cand)
4915 if (data->consider_all_candidates)
4917 EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, ci, bi)
4922 cnd = iv_cand (data, ci);
4924 cp = get_use_iv_cost (data, use, cnd);
4927 if (!iv_ca_has_deps (ivs, cp))
4930 if (!cheaper_cost_pair (cp, new_cp))
4938 EXECUTE_IF_AND_IN_BITMAP (use->related_cands, ivs->cands, 0, ci, bi)
4943 cnd = iv_cand (data, ci);
4945 cp = get_use_iv_cost (data, use, cnd);
4948 if (!iv_ca_has_deps (ivs, cp))
4951 if (!cheaper_cost_pair (cp, new_cp))
4960 iv_ca_delta_free (delta);
4964 *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
4967 iv_ca_delta_commit (data, ivs, *delta, true);
4968 cost = iv_ca_cost (ivs);
4969 iv_ca_delta_commit (data, ivs, *delta, false);
4974 /* Try optimizing the set of candidates IVS by removing candidates different
4975 from to EXCEPT_CAND from it. Return cost of the new set, and store
4976 differences in DELTA. */
4979 iv_ca_prune (struct ivopts_data *data, struct iv_ca *ivs,
4980 struct iv_cand *except_cand, struct iv_ca_delta **delta)
4983 struct iv_ca_delta *act_delta, *best_delta;
4984 unsigned i, best_cost, acost;
4985 struct iv_cand *cand;
4988 best_cost = iv_ca_cost (ivs);
4990 EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
4992 cand = iv_cand (data, i);
4994 if (cand == except_cand)
4997 acost = iv_ca_narrow (data, ivs, cand, &act_delta);
4999 if (acost < best_cost)
5002 iv_ca_delta_free (&best_delta);
5003 best_delta = act_delta;
5006 iv_ca_delta_free (&act_delta);
5015 /* Recurse to possibly remove other unnecessary ivs. */
5016 iv_ca_delta_commit (data, ivs, best_delta, true);
5017 best_cost = iv_ca_prune (data, ivs, except_cand, delta);
5018 iv_ca_delta_commit (data, ivs, best_delta, false);
5019 *delta = iv_ca_delta_join (best_delta, *delta);
5023 /* Tries to extend the sets IVS in the best possible way in order
5024 to express the USE. */
5027 try_add_cand_for (struct ivopts_data *data, struct iv_ca *ivs,
5030 unsigned best_cost, act_cost;
5033 struct iv_cand *cand;
5034 struct iv_ca_delta *best_delta = NULL, *act_delta;
5035 struct cost_pair *cp;
5037 iv_ca_add_use (data, ivs, use);
5038 best_cost = iv_ca_cost (ivs);
5040 cp = iv_ca_cand_for_use (ivs, use);
5043 best_delta = iv_ca_delta_add (use, NULL, cp, NULL);
5044 iv_ca_set_no_cp (data, ivs, use);
5047 /* First try important candidates. Only if it fails, try the specific ones.
5048 Rationale -- in loops with many variables the best choice often is to use
5049 just one generic biv. If we added here many ivs specific to the uses,
5050 the optimization algorithm later would be likely to get stuck in a local
5051 minimum, thus causing us to create too many ivs. The approach from
5052 few ivs to more seems more likely to be successful -- starting from few
5053 ivs, replacing an expensive use by a specific iv should always be a
5055 EXECUTE_IF_SET_IN_BITMAP (data->important_candidates, 0, i, bi)
5057 cand = iv_cand (data, i);
5059 if (iv_ca_cand_used_p (ivs, cand))
5062 cp = get_use_iv_cost (data, use, cand);
5066 iv_ca_set_cp (data, ivs, use, cp);
5067 act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
5068 iv_ca_set_no_cp (data, ivs, use);
5069 act_delta = iv_ca_delta_add (use, NULL, cp, act_delta);
5071 if (act_cost < best_cost)
5073 best_cost = act_cost;
5075 iv_ca_delta_free (&best_delta);
5076 best_delta = act_delta;
5079 iv_ca_delta_free (&act_delta);
5082 if (best_cost == INFTY)
5084 for (i = 0; i < use->n_map_members; i++)
5086 cp = use->cost_map + i;
5091 /* Already tried this. */
5092 if (cand->important)
5095 if (iv_ca_cand_used_p (ivs, cand))
5099 iv_ca_set_cp (data, ivs, use, cp);
5100 act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
5101 iv_ca_set_no_cp (data, ivs, use);
5102 act_delta = iv_ca_delta_add (use, iv_ca_cand_for_use (ivs, use),
5105 if (act_cost < best_cost)
5107 best_cost = act_cost;
5110 iv_ca_delta_free (&best_delta);
5111 best_delta = act_delta;
5114 iv_ca_delta_free (&act_delta);
5118 iv_ca_delta_commit (data, ivs, best_delta, true);
5119 iv_ca_delta_free (&best_delta);
5121 return (best_cost != INFTY);
5124 /* Finds an initial assignment of candidates to uses. */
5126 static struct iv_ca *
5127 get_initial_solution (struct ivopts_data *data)
5129 struct iv_ca *ivs = iv_ca_new (data);
5132 for (i = 0; i < n_iv_uses (data); i++)
5133 if (!try_add_cand_for (data, ivs, iv_use (data, i)))
5142 /* Tries to improve set of induction variables IVS. */
5145 try_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs)
5147 unsigned i, acost, best_cost = iv_ca_cost (ivs), n_ivs;
5148 struct iv_ca_delta *best_delta = NULL, *act_delta, *tmp_delta;
5149 struct iv_cand *cand;
5151 /* Try extending the set of induction variables by one. */
5152 for (i = 0; i < n_iv_cands (data); i++)
5154 cand = iv_cand (data, i);
5156 if (iv_ca_cand_used_p (ivs, cand))
5159 acost = iv_ca_extend (data, ivs, cand, &act_delta, &n_ivs);
5163 /* If we successfully added the candidate and the set is small enough,
5164 try optimizing it by removing other candidates. */
5165 if (n_ivs <= ALWAYS_PRUNE_CAND_SET_BOUND)
5167 iv_ca_delta_commit (data, ivs, act_delta, true);
5168 acost = iv_ca_prune (data, ivs, cand, &tmp_delta);
5169 iv_ca_delta_commit (data, ivs, act_delta, false);
5170 act_delta = iv_ca_delta_join (act_delta, tmp_delta);
5173 if (acost < best_cost)
5176 iv_ca_delta_free (&best_delta);
5177 best_delta = act_delta;
5180 iv_ca_delta_free (&act_delta);
5185 /* Try removing the candidates from the set instead. */
5186 best_cost = iv_ca_prune (data, ivs, NULL, &best_delta);
5188 /* Nothing more we can do. */
5193 iv_ca_delta_commit (data, ivs, best_delta, true);
5194 gcc_assert (best_cost == iv_ca_cost (ivs));
5195 iv_ca_delta_free (&best_delta);
5199 /* Attempts to find the optimal set of induction variables. We do simple
5200 greedy heuristic -- we try to replace at most one candidate in the selected
5201 solution and remove the unused ivs while this improves the cost. */
5203 static struct iv_ca *
5204 find_optimal_iv_set (struct ivopts_data *data)
5210 /* Get the initial solution. */
5211 set = get_initial_solution (data);
5214 if (dump_file && (dump_flags & TDF_DETAILS))
5215 fprintf (dump_file, "Unable to substitute for ivs, failed.\n");
5219 if (dump_file && (dump_flags & TDF_DETAILS))
5221 fprintf (dump_file, "Initial set of candidates:\n");
5222 iv_ca_dump (data, dump_file, set);
5225 while (try_improve_iv_set (data, set))
5227 if (dump_file && (dump_flags & TDF_DETAILS))
5229 fprintf (dump_file, "Improved to:\n");
5230 iv_ca_dump (data, dump_file, set);
5234 if (dump_file && (dump_flags & TDF_DETAILS))
5235 fprintf (dump_file, "Final cost %d\n\n", iv_ca_cost (set));
5237 for (i = 0; i < n_iv_uses (data); i++)
5239 use = iv_use (data, i);
5240 use->selected = iv_ca_cand_for_use (set, use)->cand;
5246 /* Creates a new induction variable corresponding to CAND. */
5249 create_new_iv (struct ivopts_data *data, struct iv_cand *cand)
5251 block_stmt_iterator incr_pos;
5261 incr_pos = bsi_last (ip_normal_pos (data->current_loop));
5265 incr_pos = bsi_last (ip_end_pos (data->current_loop));
5270 /* Mark that the iv is preserved. */
5271 name_info (data, cand->var_before)->preserve_biv = true;
5272 name_info (data, cand->var_after)->preserve_biv = true;
5274 /* Rewrite the increment so that it uses var_before directly. */
5275 find_interesting_uses_op (data, cand->var_after)->selected = cand;
5280 gimple_add_tmp_var (cand->var_before);
5281 add_referenced_tmp_var (cand->var_before);
5283 base = unshare_expr (cand->iv->base);
5285 create_iv (base, unshare_expr (cand->iv->step),
5286 cand->var_before, data->current_loop,
5287 &incr_pos, after, &cand->var_before, &cand->var_after);
5290 /* Creates new induction variables described in SET. */
5293 create_new_ivs (struct ivopts_data *data, struct iv_ca *set)
5296 struct iv_cand *cand;
5299 EXECUTE_IF_SET_IN_BITMAP (set->cands, 0, i, bi)
5301 cand = iv_cand (data, i);
5302 create_new_iv (data, cand);
5306 /* Removes statement STMT (real or a phi node). If INCLUDING_DEFINED_NAME
5307 is true, remove also the ssa name defined by the statement. */
5310 remove_statement (tree stmt, bool including_defined_name)
5312 if (TREE_CODE (stmt) == PHI_NODE)
5314 if (!including_defined_name)
5316 /* Prevent the ssa name defined by the statement from being removed. */
5317 SET_PHI_RESULT (stmt, NULL);
5319 remove_phi_node (stmt, NULL_TREE);
5323 block_stmt_iterator bsi = bsi_for_stmt (stmt);
5325 bsi_remove (&bsi, true);
5329 /* Rewrites USE (definition of iv used in a nonlinear expression)
5330 using candidate CAND. */
5333 rewrite_use_nonlinear_expr (struct ivopts_data *data,
5334 struct iv_use *use, struct iv_cand *cand)
5337 tree op, stmts, tgt, ass;
5338 block_stmt_iterator bsi, pbsi;
5340 /* An important special case -- if we are asked to express value of
5341 the original iv by itself, just exit; there is no need to
5342 introduce a new computation (that might also need casting the
5343 variable to unsigned and back). */
5344 if (cand->pos == IP_ORIGINAL
5345 && cand->incremented_at == use->stmt)
5347 tree step, ctype, utype;
5348 enum tree_code incr_code = PLUS_EXPR;
5350 gcc_assert (TREE_CODE (use->stmt) == MODIFY_EXPR);
5351 gcc_assert (TREE_OPERAND (use->stmt, 0) == cand->var_after);
5353 step = cand->iv->step;
5354 ctype = TREE_TYPE (step);
5355 utype = TREE_TYPE (cand->var_after);
5356 if (TREE_CODE (step) == NEGATE_EXPR)
5358 incr_code = MINUS_EXPR;
5359 step = TREE_OPERAND (step, 0);
5362 /* Check whether we may leave the computation unchanged.
5363 This is the case only if it does not rely on other
5364 computations in the loop -- otherwise, the computation
5365 we rely upon may be removed in remove_unused_ivs,
5366 thus leading to ICE. */
5367 op = TREE_OPERAND (use->stmt, 1);
5368 if (TREE_CODE (op) == PLUS_EXPR
5369 || TREE_CODE (op) == MINUS_EXPR)
5371 if (TREE_OPERAND (op, 0) == cand->var_before)
5372 op = TREE_OPERAND (op, 1);
5373 else if (TREE_CODE (op) == PLUS_EXPR
5374 && TREE_OPERAND (op, 1) == cand->var_before)
5375 op = TREE_OPERAND (op, 0);
5383 && (TREE_CODE (op) == INTEGER_CST
5384 || operand_equal_p (op, step, 0)))
5387 /* Otherwise, add the necessary computations to express
5389 op = fold_convert (ctype, cand->var_before);
5390 comp = fold_convert (utype,
5391 build2 (incr_code, ctype, op,
5392 unshare_expr (step)));
5395 comp = get_computation (data->current_loop, use, cand);
5397 switch (TREE_CODE (use->stmt))
5400 tgt = PHI_RESULT (use->stmt);
5402 /* If we should keep the biv, do not replace it. */
5403 if (name_info (data, tgt)->preserve_biv)
5406 pbsi = bsi = bsi_start (bb_for_stmt (use->stmt));
5407 while (!bsi_end_p (pbsi)
5408 && TREE_CODE (bsi_stmt (pbsi)) == LABEL_EXPR)
5416 tgt = TREE_OPERAND (use->stmt, 0);
5417 bsi = bsi_for_stmt (use->stmt);
5424 op = force_gimple_operand (comp, &stmts, false, SSA_NAME_VAR (tgt));
5426 if (TREE_CODE (use->stmt) == PHI_NODE)
5429 bsi_insert_after (&bsi, stmts, BSI_CONTINUE_LINKING);
5430 ass = build2 (MODIFY_EXPR, TREE_TYPE (tgt), tgt, op);
5431 bsi_insert_after (&bsi, ass, BSI_NEW_STMT);
5432 remove_statement (use->stmt, false);
5433 SSA_NAME_DEF_STMT (tgt) = ass;
5438 bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
5439 TREE_OPERAND (use->stmt, 1) = op;
5443 /* Replaces ssa name in index IDX by its basic variable. Callback for
5447 idx_remove_ssa_names (tree base, tree *idx,
5448 void *data ATTRIBUTE_UNUSED)
5452 if (TREE_CODE (*idx) == SSA_NAME)
5453 *idx = SSA_NAME_VAR (*idx);
5455 if (TREE_CODE (base) == ARRAY_REF)
5457 op = &TREE_OPERAND (base, 2);
5459 && TREE_CODE (*op) == SSA_NAME)
5460 *op = SSA_NAME_VAR (*op);
5461 op = &TREE_OPERAND (base, 3);
5463 && TREE_CODE (*op) == SSA_NAME)
5464 *op = SSA_NAME_VAR (*op);
5470 /* Unshares REF and replaces ssa names inside it by their basic variables. */
5473 unshare_and_remove_ssa_names (tree ref)
5475 ref = unshare_expr (ref);
5476 for_each_index (&ref, idx_remove_ssa_names, NULL);
5481 /* Extract the alias analysis info for the memory reference REF. There are
5482 several ways how this information may be stored and what precisely is
5483 its semantics depending on the type of the reference, but there always is
5484 somewhere hidden one _DECL node that is used to determine the set of
5485 virtual operands for the reference. The code below deciphers this jungle
5486 and extracts this single useful piece of information. */
5489 get_ref_tag (tree ref, tree orig)
5491 tree var = get_base_address (ref);
5492 tree aref = NULL_TREE, tag, sv;
5493 HOST_WIDE_INT offset, size, maxsize;
5495 for (sv = orig; handled_component_p (sv); sv = TREE_OPERAND (sv, 0))
5497 aref = get_ref_base_and_extent (sv, &offset, &size, &maxsize);
5502 if (aref && SSA_VAR_P (aref) && get_subvars_for_var (aref))
5503 return unshare_expr (sv);
5508 if (TREE_CODE (var) == INDIRECT_REF)
5510 /* In case the base is a dereference of a pointer, first check its name
5511 mem tag, and if it does not have one, use type mem tag. */
5512 var = TREE_OPERAND (var, 0);
5513 if (TREE_CODE (var) != SSA_NAME)
5516 if (SSA_NAME_PTR_INFO (var))
5518 tag = SSA_NAME_PTR_INFO (var)->name_mem_tag;
5523 var = SSA_NAME_VAR (var);
5524 tag = var_ann (var)->type_mem_tag;
5525 gcc_assert (tag != NULL_TREE);
5533 tag = var_ann (var)->type_mem_tag;
5541 /* Copies the reference information from OLD_REF to NEW_REF. */
5544 copy_ref_info (tree new_ref, tree old_ref)
5546 if (TREE_CODE (old_ref) == TARGET_MEM_REF)
5547 copy_mem_ref_info (new_ref, old_ref);
5550 TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
5551 TMR_TAG (new_ref) = get_ref_tag (old_ref, TMR_ORIGINAL (new_ref));
5555 /* Rewrites USE (address that is an iv) using candidate CAND. */
5558 rewrite_use_address (struct ivopts_data *data,
5559 struct iv_use *use, struct iv_cand *cand)
5561 struct affine_tree_combination aff;
5562 block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
5565 get_computation_aff (data->current_loop, use, cand, use->stmt, &aff);
5566 unshare_aff_combination (&aff);
5568 ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff);
5569 copy_ref_info (ref, *use->op_p);
5573 /* Rewrites USE (the condition such that one of the arguments is an iv) using
5577 rewrite_use_compare (struct ivopts_data *data,
5578 struct iv_use *use, struct iv_cand *cand)
5581 tree *op_p, cond, op, stmts, bound;
5582 block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
5583 enum tree_code compare;
5584 struct cost_pair *cp = get_use_iv_cost (data, use, cand);
5589 tree var = var_at_stmt (data->current_loop, cand, use->stmt);
5590 tree var_type = TREE_TYPE (var);
5592 compare = iv_elimination_compare (data, use);
5593 bound = fold_convert (var_type, bound);
5594 op = force_gimple_operand (unshare_expr (bound), &stmts,
5598 bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
5600 *use->op_p = build2 (compare, boolean_type_node, var, op);
5601 update_stmt (use->stmt);
5605 /* The induction variable elimination failed; just express the original
5607 comp = get_computation (data->current_loop, use, cand);
5610 op_p = &TREE_OPERAND (cond, 0);
5611 if (TREE_CODE (*op_p) != SSA_NAME
5612 || zero_p (get_iv (data, *op_p)->step))
5613 op_p = &TREE_OPERAND (cond, 1);
5615 op = force_gimple_operand (comp, &stmts, true, SSA_NAME_VAR (*op_p));
5617 bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
5622 /* Ensure that operand *OP_P may be used at the end of EXIT without
5623 violating loop closed ssa form. */
5626 protect_loop_closed_ssa_form_use (edge exit, use_operand_p op_p)
5629 struct loop *def_loop;
5632 use = USE_FROM_PTR (op_p);
5633 if (TREE_CODE (use) != SSA_NAME)
5636 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
5640 def_loop = def_bb->loop_father;
5641 if (flow_bb_inside_loop_p (def_loop, exit->dest))
5644 /* Try finding a phi node that copies the value out of the loop. */
5645 for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
5646 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == use)
5651 /* Create such a phi node. */
5652 tree new_name = duplicate_ssa_name (use, NULL);
5654 phi = create_phi_node (new_name, exit->dest);
5655 SSA_NAME_DEF_STMT (new_name) = phi;
5656 add_phi_arg (phi, use, exit);
5659 SET_USE (op_p, PHI_RESULT (phi));
5662 /* Ensure that operands of STMT may be used at the end of EXIT without
5663 violating loop closed ssa form. */
5666 protect_loop_closed_ssa_form (edge exit, tree stmt)
5669 use_operand_p use_p;
5671 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
5672 protect_loop_closed_ssa_form_use (exit, use_p);
5675 /* STMTS compute a value of a phi argument OP on EXIT of a loop. Arrange things
5676 so that they are emitted on the correct place, and so that the loop closed
5677 ssa form is preserved. */
5680 compute_phi_arg_on_exit (edge exit, tree stmts, tree op)
5682 tree_stmt_iterator tsi;
5683 block_stmt_iterator bsi;
5684 tree phi, stmt, def, next;
5686 if (!single_pred_p (exit->dest))
5687 split_loop_exit_edge (exit);
5689 /* Ensure there is label in exit->dest, so that we can
5691 tree_block_label (exit->dest);
5692 bsi = bsi_after_labels (exit->dest);
5694 if (TREE_CODE (stmts) == STATEMENT_LIST)
5696 for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi))
5698 tree stmt = tsi_stmt (tsi);
5699 bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
5700 protect_loop_closed_ssa_form (exit, stmt);
5705 bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
5706 protect_loop_closed_ssa_form (exit, stmts);
5712 for (phi = phi_nodes (exit->dest); phi; phi = next)
5714 next = PHI_CHAIN (phi);
5716 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == op)
5718 def = PHI_RESULT (phi);
5719 remove_statement (phi, false);
5720 stmt = build2 (MODIFY_EXPR, TREE_TYPE (op),
5722 SSA_NAME_DEF_STMT (def) = stmt;
5723 bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
5728 /* Rewrites the final value of USE (that is only needed outside of the loop)
5729 using candidate CAND. */
5732 rewrite_use_outer (struct ivopts_data *data,
5733 struct iv_use *use, struct iv_cand *cand)
5736 tree value, op, stmts, tgt;
5739 switch (TREE_CODE (use->stmt))
5742 tgt = PHI_RESULT (use->stmt);
5745 tgt = TREE_OPERAND (use->stmt, 0);
5751 exit = single_dom_exit (data->current_loop);
5757 struct cost_pair *cp = get_use_iv_cost (data, use, cand);
5758 value = unshare_expr (cp->value);
5761 value = get_computation_at (data->current_loop,
5762 use, cand, last_stmt (exit->src));
5764 op = force_gimple_operand (value, &stmts, true, SSA_NAME_VAR (tgt));
5766 /* If we will preserve the iv anyway and we would need to perform
5767 some computation to replace the final value, do nothing. */
5768 if (stmts && name_info (data, tgt)->preserve_biv)
5771 for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
5773 use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, exit);
5775 if (USE_FROM_PTR (use_p) == tgt)
5776 SET_USE (use_p, op);
5780 compute_phi_arg_on_exit (exit, stmts, op);
5782 /* Enable removal of the statement. We cannot remove it directly,
5783 since we may still need the aliasing information attached to the
5784 ssa name defined by it. */
5785 name_info (data, tgt)->iv->have_use_for = false;
5789 /* If the variable is going to be preserved anyway, there is nothing to
5791 if (name_info (data, tgt)->preserve_biv)
5794 /* Otherwise we just need to compute the iv. */
5795 rewrite_use_nonlinear_expr (data, use, cand);
5798 /* Rewrites USE using candidate CAND. */
5801 rewrite_use (struct ivopts_data *data,
5802 struct iv_use *use, struct iv_cand *cand)
5806 case USE_NONLINEAR_EXPR:
5807 rewrite_use_nonlinear_expr (data, use, cand);
5811 rewrite_use_outer (data, use, cand);
5815 rewrite_use_address (data, use, cand);
5819 rewrite_use_compare (data, use, cand);
5825 mark_new_vars_to_rename (use->stmt);
5828 /* Rewrite the uses using the selected induction variables. */
5831 rewrite_uses (struct ivopts_data *data)
5834 struct iv_cand *cand;
5837 for (i = 0; i < n_iv_uses (data); i++)
5839 use = iv_use (data, i);
5840 cand = use->selected;
5843 rewrite_use (data, use, cand);
5847 /* Removes the ivs that are not used after rewriting. */
5850 remove_unused_ivs (struct ivopts_data *data)
5855 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
5857 struct version_info *info;
5859 info = ver_info (data, j);
5861 && !zero_p (info->iv->step)
5863 && !info->iv->have_use_for
5864 && !info->preserve_biv)
5865 remove_statement (SSA_NAME_DEF_STMT (info->iv->ssa_name), true);
5869 /* Frees data allocated by the optimization of a single loop. */
5872 free_loop_data (struct ivopts_data *data)
5878 htab_empty (data->niters);
5880 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
5882 struct version_info *info;
5884 info = ver_info (data, i);
5888 info->has_nonlin_use = false;
5889 info->preserve_biv = false;
5892 bitmap_clear (data->relevant);
5893 bitmap_clear (data->important_candidates);
5895 for (i = 0; i < n_iv_uses (data); i++)
5897 struct iv_use *use = iv_use (data, i);
5900 BITMAP_FREE (use->related_cands);
5901 for (j = 0; j < use->n_map_members; j++)
5902 if (use->cost_map[j].depends_on)
5903 BITMAP_FREE (use->cost_map[j].depends_on);
5904 free (use->cost_map);
5907 VEC_truncate (iv_use_p, data->iv_uses, 0);
5909 for (i = 0; i < n_iv_cands (data); i++)
5911 struct iv_cand *cand = iv_cand (data, i);
5915 if (cand->depends_on)
5916 BITMAP_FREE (cand->depends_on);
5919 VEC_truncate (iv_cand_p, data->iv_candidates, 0);
5921 if (data->version_info_size < num_ssa_names)
5923 data->version_info_size = 2 * num_ssa_names;
5924 free (data->version_info);
5925 data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
5928 data->max_inv_id = 0;
5930 for (i = 0; VEC_iterate (tree, decl_rtl_to_reset, i, obj); i++)
5931 SET_DECL_RTL (obj, NULL_RTX);
5933 VEC_truncate (tree, decl_rtl_to_reset, 0);
5936 /* Finalizes data structures used by the iv optimization pass. LOOPS is the
5940 tree_ssa_iv_optimize_finalize (struct loops *loops, struct ivopts_data *data)
5944 for (i = 1; i < loops->num; i++)
5945 if (loops->parray[i])
5947 free (loops->parray[i]->aux);
5948 loops->parray[i]->aux = NULL;
5951 free_loop_data (data);
5952 free (data->version_info);
5953 BITMAP_FREE (data->relevant);
5954 BITMAP_FREE (data->important_candidates);
5955 htab_delete (data->niters);
5957 VEC_free (tree, heap, decl_rtl_to_reset);
5958 VEC_free (iv_use_p, heap, data->iv_uses);
5959 VEC_free (iv_cand_p, heap, data->iv_candidates);
5962 /* Optimizes the LOOP. Returns true if anything changed. */
5965 tree_ssa_iv_optimize_loop (struct ivopts_data *data, struct loop *loop)
5967 bool changed = false;
5968 struct iv_ca *iv_ca;
5971 data->current_loop = loop;
5973 if (dump_file && (dump_flags & TDF_DETAILS))
5975 fprintf (dump_file, "Processing loop %d\n", loop->num);
5977 exit = single_dom_exit (loop);
5980 fprintf (dump_file, " single exit %d -> %d, exit condition ",
5981 exit->src->index, exit->dest->index);
5982 print_generic_expr (dump_file, last_stmt (exit->src), TDF_SLIM);
5983 fprintf (dump_file, "\n");
5986 fprintf (dump_file, "\n");
5989 /* For each ssa name determines whether it behaves as an induction variable
5991 if (!find_induction_variables (data))
5994 /* Finds interesting uses (item 1). */
5995 find_interesting_uses (data);
5996 if (n_iv_uses (data) > MAX_CONSIDERED_USES)
5999 /* Finds candidates for the induction variables (item 2). */
6000 find_iv_candidates (data);
6002 /* Calculates the costs (item 3, part 1). */
6003 determine_use_iv_costs (data);
6004 determine_iv_costs (data);
6005 determine_set_costs (data);
6007 /* Find the optimal set of induction variables (item 3, part 2). */
6008 iv_ca = find_optimal_iv_set (data);
6013 /* Create the new induction variables (item 4, part 1). */
6014 create_new_ivs (data, iv_ca);
6015 iv_ca_free (&iv_ca);
6017 /* Rewrite the uses (item 4, part 2). */
6018 rewrite_uses (data);
6020 /* Remove the ivs that are unused after rewriting. */
6021 remove_unused_ivs (data);
6023 /* We have changed the structure of induction variables; it might happen
6024 that definitions in the scev database refer to some of them that were
6029 free_loop_data (data);
6034 /* Main entry point. Optimizes induction variables in LOOPS. */
6037 tree_ssa_iv_optimize (struct loops *loops)
6040 struct ivopts_data data;
6042 tree_ssa_iv_optimize_init (loops, &data);
6044 /* Optimize the loops starting with the innermost ones. */
6045 loop = loops->tree_root;
6049 /* Scan the loops, inner ones first. */
6050 while (loop != loops->tree_root)
6052 if (dump_file && (dump_flags & TDF_DETAILS))
6053 flow_loop_dump (loop, dump_file, NULL, 1);
6055 tree_ssa_iv_optimize_loop (&data, loop);
6067 tree_ssa_iv_optimize_finalize (loops, &data);