1 /* Induction variable optimizations.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This pass tries to find the optimal set of induction variables for the loop.
21 It optimizes just the basic linear induction variables (although adding
22 support for other types should not be too hard). It includes the
23 optimizations commonly known as strength reduction, induction variable
24 coalescing and induction variable elimination. It does it in the
27 1) The interesting uses of induction variables are found. This includes
29 -- uses of induction variables in non-linear expressions
30 -- addresses of arrays
31 -- comparisons of induction variables
33 2) Candidates for the induction variables are found. This includes
35 -- old induction variables
36 -- the variables defined by expressions derived from the "interesting
39 3) The optimal (w.r. to a cost function) set of variables is chosen. The
40 cost function assigns a cost to sets of induction variables and consists
43 -- The use costs. Each of the interesting uses chooses the best induction
44 variable in the set and adds its cost to the sum. The cost reflects
45 the time spent on modifying the induction variables value to be usable
46 for the given purpose (adding base and offset for arrays, etc.).
47 -- The variable costs. Each of the variables has a cost assigned that
48 reflects the costs associated with incrementing the value of the
49 variable. The original variables are somewhat preferred.
50 -- The set cost. Depending on the size of the set, extra cost may be
51 added to reflect register pressure.
53 All the costs are defined in a machine-specific way, using the target
54 hooks and machine descriptions to determine them.
56 4) The trees are transformed to use the new variables, the dead code is
59 All of this is done loop by loop. Doing it globally is theoretically
60 possible, it might give a better performance and it might enable us
61 to decide costs more precisely, but getting all the interactions right
62 would be complicated. */
66 #include "coretypes.h"
71 #include "hard-reg-set.h"
72 #include "basic-block.h"
74 #include "diagnostic.h"
75 #include "tree-flow.h"
76 #include "tree-dump.h"
81 #include "tree-pass.h"
83 #include "insn-config.h"
85 #include "pointer-set.h"
87 #include "tree-chrec.h"
88 #include "tree-scalar-evolution.h"
91 #include "langhooks.h"
92 #include "tree-affine.h"
95 /* The infinite cost. */
96 #define INFTY 10000000
98 /* The expected number of loop iterations. TODO -- use profiling instead of
100 #define AVG_LOOP_NITER(LOOP) 5
103 /* Representation of the induction variable. */
106 tree base
; /* Initial value of the iv. */
107 tree base_object
; /* A memory object to that the induction variable points. */
108 tree step
; /* Step of the iv (constant only). */
109 tree ssa_name
; /* The ssa name with the value. */
110 bool biv_p
; /* Is it a biv? */
111 bool have_use_for
; /* Do we already have a use for it? */
112 unsigned use_id
; /* The identifier in the use if it is the case. */
115 /* Per-ssa version information (induction variable descriptions, etc.). */
118 tree name
; /* The ssa name. */
119 struct iv
*iv
; /* Induction variable description. */
120 bool has_nonlin_use
; /* For a loop-level invariant, whether it is used in
121 an expression that is not an induction variable. */
122 unsigned inv_id
; /* Id of an invariant. */
123 bool preserve_biv
; /* For the original biv, whether to preserve it. */
129 USE_NONLINEAR_EXPR
, /* Use in a nonlinear expression. */
130 USE_ADDRESS
, /* Use in an address. */
131 USE_COMPARE
/* Use is a compare. */
134 /* Cost of a computation. */
137 unsigned cost
; /* The runtime cost. */
138 unsigned complexity
; /* The estimate of the complexity of the code for
139 the computation (in no concrete units --
140 complexity field should be larger for more
141 complex expressions and addressing modes). */
144 static const comp_cost zero_cost
= {0, 0};
145 static const comp_cost infinite_cost
= {INFTY
, INFTY
};
147 /* The candidate - cost pair. */
150 struct iv_cand
*cand
; /* The candidate. */
151 comp_cost cost
; /* The cost. */
152 bitmap depends_on
; /* The list of invariants that have to be
154 tree value
; /* For final value elimination, the expression for
155 the final value of the iv. For iv elimination,
156 the new bound to compare with. */
162 unsigned id
; /* The id of the use. */
163 enum use_type type
; /* Type of the use. */
164 struct iv
*iv
; /* The induction variable it is based on. */
165 tree stmt
; /* Statement in that it occurs. */
166 tree
*op_p
; /* The place where it occurs. */
167 bitmap related_cands
; /* The set of "related" iv candidates, plus the common
170 unsigned n_map_members
; /* Number of candidates in the cost_map list. */
171 struct cost_pair
*cost_map
;
172 /* The costs wrto the iv candidates. */
174 struct iv_cand
*selected
;
175 /* The selected candidate. */
178 /* The position where the iv is computed. */
181 IP_NORMAL
, /* At the end, just before the exit condition. */
182 IP_END
, /* At the end of the latch block. */
183 IP_ORIGINAL
/* The original biv. */
186 /* The induction variable candidate. */
189 unsigned id
; /* The number of the candidate. */
190 bool important
; /* Whether this is an "important" candidate, i.e. such
191 that it should be considered by all uses. */
192 enum iv_position pos
; /* Where it is computed. */
193 tree incremented_at
; /* For original biv, the statement where it is
195 tree var_before
; /* The variable used for it before increment. */
196 tree var_after
; /* The variable used for it after increment. */
197 struct iv
*iv
; /* The value of the candidate. NULL for
198 "pseudocandidate" used to indicate the possibility
199 to replace the final value of an iv by direct
200 computation of the value. */
201 unsigned cost
; /* Cost of the candidate. */
202 bitmap depends_on
; /* The list of invariants that are used in step of the
206 /* The data used by the induction variable optimizations. */
208 typedef struct iv_use
*iv_use_p
;
210 DEF_VEC_ALLOC_P(iv_use_p
,heap
);
212 typedef struct iv_cand
*iv_cand_p
;
213 DEF_VEC_P(iv_cand_p
);
214 DEF_VEC_ALLOC_P(iv_cand_p
,heap
);
218 /* The currently optimized loop. */
219 struct loop
*current_loop
;
221 /* Number of registers used in it. */
224 /* Numbers of iterations for all exits of the current loop. */
225 struct pointer_map_t
*niters
;
227 /* The size of version_info array allocated. */
228 unsigned version_info_size
;
230 /* The array of information for the ssa names. */
231 struct version_info
*version_info
;
233 /* The bitmap of indices in version_info whose value was changed. */
236 /* The maximum invariant id. */
239 /* The uses of induction variables. */
240 VEC(iv_use_p
,heap
) *iv_uses
;
242 /* The candidates. */
243 VEC(iv_cand_p
,heap
) *iv_candidates
;
245 /* A bitmap of important candidates. */
246 bitmap important_candidates
;
248 /* Whether to consider just related and important candidates when replacing a
250 bool consider_all_candidates
;
253 /* An assignment of iv candidates to uses. */
257 /* The number of uses covered by the assignment. */
260 /* Number of uses that cannot be expressed by the candidates in the set. */
263 /* Candidate assigned to a use, together with the related costs. */
264 struct cost_pair
**cand_for_use
;
266 /* Number of times each candidate is used. */
267 unsigned *n_cand_uses
;
269 /* The candidates used. */
272 /* The number of candidates in the set. */
275 /* Total number of registers needed. */
278 /* Total cost of expressing uses. */
279 comp_cost cand_use_cost
;
281 /* Total cost of candidates. */
284 /* Number of times each invariant is used. */
285 unsigned *n_invariant_uses
;
287 /* Total cost of the assignment. */
291 /* Difference of two iv candidate assignments. */
298 /* An old assignment (for rollback purposes). */
299 struct cost_pair
*old_cp
;
301 /* A new assignment. */
302 struct cost_pair
*new_cp
;
304 /* Next change in the list. */
305 struct iv_ca_delta
*next_change
;
308 /* Bound on number of candidates below that all candidates are considered. */
310 #define CONSIDER_ALL_CANDIDATES_BOUND \
311 ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
313 /* If there are more iv occurrences, we just give up (it is quite unlikely that
314 optimizing such a loop would help, and it would take ages). */
316 #define MAX_CONSIDERED_USES \
317 ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
319 /* If there are at most this number of ivs in the set, try removing unnecessary
320 ivs from the set always. */
322 #define ALWAYS_PRUNE_CAND_SET_BOUND \
323 ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
325 /* The list of trees for that the decl_rtl field must be reset is stored
328 static VEC(tree
,heap
) *decl_rtl_to_reset
;
330 /* Number of uses recorded in DATA. */
332 static inline unsigned
333 n_iv_uses (struct ivopts_data
*data
)
335 return VEC_length (iv_use_p
, data
->iv_uses
);
338 /* Ith use recorded in DATA. */
340 static inline struct iv_use
*
341 iv_use (struct ivopts_data
*data
, unsigned i
)
343 return VEC_index (iv_use_p
, data
->iv_uses
, i
);
346 /* Number of candidates recorded in DATA. */
348 static inline unsigned
349 n_iv_cands (struct ivopts_data
*data
)
351 return VEC_length (iv_cand_p
, data
->iv_candidates
);
354 /* Ith candidate recorded in DATA. */
356 static inline struct iv_cand
*
357 iv_cand (struct ivopts_data
*data
, unsigned i
)
359 return VEC_index (iv_cand_p
, data
->iv_candidates
, i
);
362 /* The single loop exit if it dominates the latch, NULL otherwise. */
365 single_dom_exit (struct loop
*loop
)
367 edge exit
= single_exit (loop
);
372 if (!just_once_each_iteration_p (loop
, exit
->src
))
378 /* Dumps information about the induction variable IV to FILE. */
380 extern void dump_iv (FILE *, struct iv
*);
382 dump_iv (FILE *file
, struct iv
*iv
)
386 fprintf (file
, "ssa name ");
387 print_generic_expr (file
, iv
->ssa_name
, TDF_SLIM
);
388 fprintf (file
, "\n");
391 fprintf (file
, " type ");
392 print_generic_expr (file
, TREE_TYPE (iv
->base
), TDF_SLIM
);
393 fprintf (file
, "\n");
397 fprintf (file
, " base ");
398 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
399 fprintf (file
, "\n");
401 fprintf (file
, " step ");
402 print_generic_expr (file
, iv
->step
, TDF_SLIM
);
403 fprintf (file
, "\n");
407 fprintf (file
, " invariant ");
408 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
409 fprintf (file
, "\n");
414 fprintf (file
, " base object ");
415 print_generic_expr (file
, iv
->base_object
, TDF_SLIM
);
416 fprintf (file
, "\n");
420 fprintf (file
, " is a biv\n");
423 /* Dumps information about the USE to FILE. */
425 extern void dump_use (FILE *, struct iv_use
*);
427 dump_use (FILE *file
, struct iv_use
*use
)
429 fprintf (file
, "use %d\n", use
->id
);
433 case USE_NONLINEAR_EXPR
:
434 fprintf (file
, " generic\n");
438 fprintf (file
, " address\n");
442 fprintf (file
, " compare\n");
449 fprintf (file
, " in statement ");
450 print_generic_expr (file
, use
->stmt
, TDF_SLIM
);
451 fprintf (file
, "\n");
453 fprintf (file
, " at position ");
455 print_generic_expr (file
, *use
->op_p
, TDF_SLIM
);
456 fprintf (file
, "\n");
458 dump_iv (file
, use
->iv
);
460 if (use
->related_cands
)
462 fprintf (file
, " related candidates ");
463 dump_bitmap (file
, use
->related_cands
);
467 /* Dumps information about the uses to FILE. */
469 extern void dump_uses (FILE *, struct ivopts_data
*);
471 dump_uses (FILE *file
, struct ivopts_data
*data
)
476 for (i
= 0; i
< n_iv_uses (data
); i
++)
478 use
= iv_use (data
, i
);
480 dump_use (file
, use
);
481 fprintf (file
, "\n");
485 /* Dumps information about induction variable candidate CAND to FILE. */
487 extern void dump_cand (FILE *, struct iv_cand
*);
489 dump_cand (FILE *file
, struct iv_cand
*cand
)
491 struct iv
*iv
= cand
->iv
;
493 fprintf (file
, "candidate %d%s\n",
494 cand
->id
, cand
->important
? " (important)" : "");
496 if (cand
->depends_on
)
498 fprintf (file
, " depends on ");
499 dump_bitmap (file
, cand
->depends_on
);
504 fprintf (file
, " final value replacement\n");
511 fprintf (file
, " incremented before exit test\n");
515 fprintf (file
, " incremented at end\n");
519 fprintf (file
, " original biv\n");
526 /* Returns the info for ssa version VER. */
528 static inline struct version_info
*
529 ver_info (struct ivopts_data
*data
, unsigned ver
)
531 return data
->version_info
+ ver
;
534 /* Returns the info for ssa name NAME. */
536 static inline struct version_info
*
537 name_info (struct ivopts_data
*data
, tree name
)
539 return ver_info (data
, SSA_NAME_VERSION (name
));
542 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
546 stmt_after_ip_normal_pos (struct loop
*loop
, tree stmt
)
548 basic_block bb
= ip_normal_pos (loop
), sbb
= bb_for_stmt (stmt
);
552 if (sbb
== loop
->latch
)
558 return stmt
== last_stmt (bb
);
561 /* Returns true if STMT if after the place where the original induction
562 variable CAND is incremented. */
565 stmt_after_ip_original_pos (struct iv_cand
*cand
, tree stmt
)
567 basic_block cand_bb
= bb_for_stmt (cand
->incremented_at
);
568 basic_block stmt_bb
= bb_for_stmt (stmt
);
569 block_stmt_iterator bsi
;
571 if (!dominated_by_p (CDI_DOMINATORS
, stmt_bb
, cand_bb
))
574 if (stmt_bb
!= cand_bb
)
577 /* Scan the block from the end, since the original ivs are usually
578 incremented at the end of the loop body. */
579 for (bsi
= bsi_last (stmt_bb
); ; bsi_prev (&bsi
))
581 if (bsi_stmt (bsi
) == cand
->incremented_at
)
583 if (bsi_stmt (bsi
) == stmt
)
588 /* Returns true if STMT if after the place where the induction variable
589 CAND is incremented in LOOP. */
592 stmt_after_increment (struct loop
*loop
, struct iv_cand
*cand
, tree stmt
)
600 return stmt_after_ip_normal_pos (loop
, stmt
);
603 return stmt_after_ip_original_pos (cand
, stmt
);
610 /* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
613 abnormal_ssa_name_p (tree exp
)
618 if (TREE_CODE (exp
) != SSA_NAME
)
621 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
) != 0;
624 /* Returns false if BASE or INDEX contains a ssa name that occurs in an
625 abnormal phi node. Callback for for_each_index. */
628 idx_contains_abnormal_ssa_name_p (tree base
, tree
*index
,
629 void *data ATTRIBUTE_UNUSED
)
631 if (TREE_CODE (base
) == ARRAY_REF
)
633 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 2)))
635 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 3)))
639 return !abnormal_ssa_name_p (*index
);
642 /* Returns true if EXPR contains a ssa name that occurs in an
643 abnormal phi node. */
646 contains_abnormal_ssa_name_p (tree expr
)
649 enum tree_code_class codeclass
;
654 code
= TREE_CODE (expr
);
655 codeclass
= TREE_CODE_CLASS (code
);
657 if (code
== SSA_NAME
)
658 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr
) != 0;
660 if (code
== INTEGER_CST
661 || is_gimple_min_invariant (expr
))
664 if (code
== ADDR_EXPR
)
665 return !for_each_index (&TREE_OPERAND (expr
, 0),
666 idx_contains_abnormal_ssa_name_p
,
673 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1)))
678 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0)))
690 /* Returns tree describing number of iterations determined from
691 EXIT of DATA->current_loop, or NULL if something goes wrong. */
694 niter_for_exit (struct ivopts_data
*data
, edge exit
)
696 struct tree_niter_desc desc
;
702 data
->niters
= pointer_map_create ();
706 slot
= pointer_map_contains (data
->niters
, exit
);
710 /* Try to determine number of iterations. We must know it
711 unconditionally (i.e., without possibility of # of iterations
712 being zero). Also, we cannot safely work with ssa names that
713 appear in phi nodes on abnormal edges, so that we do not create
714 overlapping life ranges for them (PR 27283). */
715 if (number_of_iterations_exit (data
->current_loop
,
717 && integer_zerop (desc
.may_be_zero
)
718 && !contains_abnormal_ssa_name_p (desc
.niter
))
723 *pointer_map_insert (data
->niters
, exit
) = niter
;
726 niter
= (tree
) *slot
;
731 /* Returns tree describing number of iterations determined from
732 single dominating exit of DATA->current_loop, or NULL if something
736 niter_for_single_dom_exit (struct ivopts_data
*data
)
738 edge exit
= single_dom_exit (data
->current_loop
);
743 return niter_for_exit (data
, exit
);
746 /* Initializes data structures used by the iv optimization pass, stored
750 tree_ssa_iv_optimize_init (struct ivopts_data
*data
)
752 data
->version_info_size
= 2 * num_ssa_names
;
753 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
754 data
->relevant
= BITMAP_ALLOC (NULL
);
755 data
->important_candidates
= BITMAP_ALLOC (NULL
);
756 data
->max_inv_id
= 0;
758 data
->iv_uses
= VEC_alloc (iv_use_p
, heap
, 20);
759 data
->iv_candidates
= VEC_alloc (iv_cand_p
, heap
, 20);
760 decl_rtl_to_reset
= VEC_alloc (tree
, heap
, 20);
763 /* Returns a memory object to that EXPR points. In case we are able to
764 determine that it does not point to any such object, NULL is returned. */
767 determine_base_object (tree expr
)
769 enum tree_code code
= TREE_CODE (expr
);
772 /* If this is a pointer casted to any type, we need to determine
773 the base object for the pointer; so handle conversions before
774 throwing away non-pointer expressions. */
775 if (TREE_CODE (expr
) == NOP_EXPR
776 || TREE_CODE (expr
) == CONVERT_EXPR
)
777 return determine_base_object (TREE_OPERAND (expr
, 0));
779 if (!POINTER_TYPE_P (TREE_TYPE (expr
)))
788 obj
= TREE_OPERAND (expr
, 0);
789 base
= get_base_address (obj
);
794 if (TREE_CODE (base
) == INDIRECT_REF
)
795 return determine_base_object (TREE_OPERAND (base
, 0));
797 return fold_convert (ptr_type_node
,
798 build_fold_addr_expr (base
));
800 case POINTER_PLUS_EXPR
:
801 return determine_base_object (TREE_OPERAND (expr
, 0));
805 /* Pointer addition is done solely using POINTER_PLUS_EXPR. */
809 return fold_convert (ptr_type_node
, expr
);
813 /* Allocates an induction variable with given initial value BASE and step STEP
817 alloc_iv (tree base
, tree step
)
819 struct iv
*iv
= XCNEW (struct iv
);
820 gcc_assert (step
!= NULL_TREE
);
823 iv
->base_object
= determine_base_object (base
);
826 iv
->have_use_for
= false;
828 iv
->ssa_name
= NULL_TREE
;
833 /* Sets STEP and BASE for induction variable IV. */
836 set_iv (struct ivopts_data
*data
, tree iv
, tree base
, tree step
)
838 struct version_info
*info
= name_info (data
, iv
);
840 gcc_assert (!info
->iv
);
842 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (iv
));
843 info
->iv
= alloc_iv (base
, step
);
844 info
->iv
->ssa_name
= iv
;
847 /* Finds induction variable declaration for VAR. */
850 get_iv (struct ivopts_data
*data
, tree var
)
853 tree type
= TREE_TYPE (var
);
855 if (!POINTER_TYPE_P (type
)
856 && !INTEGRAL_TYPE_P (type
))
859 if (!name_info (data
, var
)->iv
)
861 bb
= bb_for_stmt (SSA_NAME_DEF_STMT (var
));
864 || !flow_bb_inside_loop_p (data
->current_loop
, bb
))
865 set_iv (data
, var
, var
, build_int_cst (type
, 0));
868 return name_info (data
, var
)->iv
;
871 /* Determines the step of a biv defined in PHI. Returns NULL if PHI does
872 not define a simple affine biv with nonzero step. */
875 determine_biv_step (tree phi
)
877 struct loop
*loop
= bb_for_stmt (phi
)->loop_father
;
878 tree name
= PHI_RESULT (phi
);
881 if (!is_gimple_reg (name
))
884 if (!simple_iv (loop
, phi
, name
, &iv
, true))
887 return integer_zerop (iv
.step
) ? NULL_TREE
: iv
.step
;
890 /* Finds basic ivs. */
893 find_bivs (struct ivopts_data
*data
)
895 tree phi
, step
, type
, base
;
897 struct loop
*loop
= data
->current_loop
;
899 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
901 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
904 step
= determine_biv_step (phi
);
908 base
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
909 base
= expand_simple_operations (base
);
910 if (contains_abnormal_ssa_name_p (base
)
911 || contains_abnormal_ssa_name_p (step
))
914 type
= TREE_TYPE (PHI_RESULT (phi
));
915 base
= fold_convert (type
, base
);
917 step
= fold_convert (type
, step
);
919 set_iv (data
, PHI_RESULT (phi
), base
, step
);
926 /* Marks basic ivs. */
929 mark_bivs (struct ivopts_data
*data
)
932 struct iv
*iv
, *incr_iv
;
933 struct loop
*loop
= data
->current_loop
;
936 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
938 iv
= get_iv (data
, PHI_RESULT (phi
));
942 var
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
943 incr_iv
= get_iv (data
, var
);
947 /* If the increment is in the subloop, ignore it. */
948 incr_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (var
));
949 if (incr_bb
->loop_father
!= data
->current_loop
950 || (incr_bb
->flags
& BB_IRREDUCIBLE_LOOP
))
954 incr_iv
->biv_p
= true;
958 /* Checks whether STMT defines a linear induction variable and stores its
962 find_givs_in_stmt_scev (struct ivopts_data
*data
, tree stmt
, affine_iv
*iv
)
965 struct loop
*loop
= data
->current_loop
;
967 iv
->base
= NULL_TREE
;
968 iv
->step
= NULL_TREE
;
970 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
973 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
974 if (TREE_CODE (lhs
) != SSA_NAME
)
977 if (!simple_iv (loop
, stmt
, GIMPLE_STMT_OPERAND (stmt
, 1), iv
, true))
979 iv
->base
= expand_simple_operations (iv
->base
);
981 if (contains_abnormal_ssa_name_p (iv
->base
)
982 || contains_abnormal_ssa_name_p (iv
->step
))
988 /* Finds general ivs in statement STMT. */
991 find_givs_in_stmt (struct ivopts_data
*data
, tree stmt
)
995 if (!find_givs_in_stmt_scev (data
, stmt
, &iv
))
998 set_iv (data
, GIMPLE_STMT_OPERAND (stmt
, 0), iv
.base
, iv
.step
);
1001 /* Finds general ivs in basic block BB. */
1004 find_givs_in_bb (struct ivopts_data
*data
, basic_block bb
)
1006 block_stmt_iterator bsi
;
1008 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1009 find_givs_in_stmt (data
, bsi_stmt (bsi
));
1012 /* Finds general ivs. */
1015 find_givs (struct ivopts_data
*data
)
1017 struct loop
*loop
= data
->current_loop
;
1018 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1021 for (i
= 0; i
< loop
->num_nodes
; i
++)
1022 find_givs_in_bb (data
, body
[i
]);
1026 /* For each ssa name defined in LOOP determines whether it is an induction
1027 variable and if so, its initial value and step. */
1030 find_induction_variables (struct ivopts_data
*data
)
1035 if (!find_bivs (data
))
1041 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1043 tree niter
= niter_for_single_dom_exit (data
);
1047 fprintf (dump_file
, " number of iterations ");
1048 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1049 fprintf (dump_file
, "\n\n");
1052 fprintf (dump_file
, "Induction variables:\n\n");
1054 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1056 if (ver_info (data
, i
)->iv
)
1057 dump_iv (dump_file
, ver_info (data
, i
)->iv
);
1064 /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV. */
1066 static struct iv_use
*
1067 record_use (struct ivopts_data
*data
, tree
*use_p
, struct iv
*iv
,
1068 tree stmt
, enum use_type use_type
)
1070 struct iv_use
*use
= XCNEW (struct iv_use
);
1072 use
->id
= n_iv_uses (data
);
1073 use
->type
= use_type
;
1077 use
->related_cands
= BITMAP_ALLOC (NULL
);
1079 /* To avoid showing ssa name in the dumps, if it was not reset by the
1081 iv
->ssa_name
= NULL_TREE
;
1083 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1084 dump_use (dump_file
, use
);
1086 VEC_safe_push (iv_use_p
, heap
, data
->iv_uses
, use
);
1091 /* Checks whether OP is a loop-level invariant and if so, records it.
1092 NONLINEAR_USE is true if the invariant is used in a way we do not
1093 handle specially. */
1096 record_invariant (struct ivopts_data
*data
, tree op
, bool nonlinear_use
)
1099 struct version_info
*info
;
1101 if (TREE_CODE (op
) != SSA_NAME
1102 || !is_gimple_reg (op
))
1105 bb
= bb_for_stmt (SSA_NAME_DEF_STMT (op
));
1107 && flow_bb_inside_loop_p (data
->current_loop
, bb
))
1110 info
= name_info (data
, op
);
1112 info
->has_nonlin_use
|= nonlinear_use
;
1114 info
->inv_id
= ++data
->max_inv_id
;
1115 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (op
));
1118 /* Checks whether the use OP is interesting and if so, records it. */
1120 static struct iv_use
*
1121 find_interesting_uses_op (struct ivopts_data
*data
, tree op
)
1128 if (TREE_CODE (op
) != SSA_NAME
)
1131 iv
= get_iv (data
, op
);
1135 if (iv
->have_use_for
)
1137 use
= iv_use (data
, iv
->use_id
);
1139 gcc_assert (use
->type
== USE_NONLINEAR_EXPR
);
1143 if (integer_zerop (iv
->step
))
1145 record_invariant (data
, op
, true);
1148 iv
->have_use_for
= true;
1150 civ
= XNEW (struct iv
);
1153 stmt
= SSA_NAME_DEF_STMT (op
);
1154 gcc_assert (TREE_CODE (stmt
) == PHI_NODE
1155 || TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
);
1157 use
= record_use (data
, NULL
, civ
, stmt
, USE_NONLINEAR_EXPR
);
1158 iv
->use_id
= use
->id
;
1163 /* Given a condition *COND_P, checks whether it is a compare of an induction
1164 variable and an invariant. If this is the case, CONTROL_VAR is set
1165 to location of the iv, BOUND to the location of the invariant,
1166 IV_VAR and IV_BOUND are set to the corresponding induction variable
1167 descriptions, and true is returned. If this is not the case,
1168 CONTROL_VAR and BOUND are set to the arguments of the condition and
1169 false is returned. */
1172 extract_cond_operands (struct ivopts_data
*data
, tree
*cond_p
,
1173 tree
**control_var
, tree
**bound
,
1174 struct iv
**iv_var
, struct iv
**iv_bound
)
1176 /* The nodes returned when COND has just one operand. Note that you should
1177 not modify anything in BOUND or IV_BOUND because of this. */
1178 static struct iv const_iv
;
1180 tree cond
= *cond_p
;
1181 tree
*op0
= &zero
, *op1
= &zero
, *tmp_op
;
1182 struct iv
*iv0
= &const_iv
, *iv1
= &const_iv
, *tmp_iv
;
1185 zero
= integer_zero_node
;
1186 const_iv
.step
= integer_zero_node
;
1188 if (TREE_CODE (cond
) == SSA_NAME
)
1191 iv0
= get_iv (data
, cond
);
1192 ret
= (iv0
&& !integer_zerop (iv0
->step
));
1196 if (!COMPARISON_CLASS_P (cond
))
1202 op0
= &TREE_OPERAND (cond
, 0);
1203 op1
= &TREE_OPERAND (cond
, 1);
1204 if (TREE_CODE (*op0
) == SSA_NAME
)
1205 iv0
= get_iv (data
, *op0
);
1206 if (TREE_CODE (*op1
) == SSA_NAME
)
1207 iv1
= get_iv (data
, *op1
);
1209 /* Exactly one of the compared values must be an iv, and the other one must
1214 if (integer_zerop (iv0
->step
))
1216 /* Control variable may be on the other side. */
1217 tmp_op
= op0
; op0
= op1
; op1
= tmp_op
;
1218 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
1220 ret
= !integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
);
1224 *control_var
= op0
;;
1235 /* Checks whether the condition *COND_P in STMT is interesting
1236 and if so, records it. */
1239 find_interesting_uses_cond (struct ivopts_data
*data
, tree stmt
, tree
*cond_p
)
1241 tree
*var_p
, *bound_p
;
1242 struct iv
*var_iv
, *civ
;
1244 if (!extract_cond_operands (data
, cond_p
, &var_p
, &bound_p
, &var_iv
, NULL
))
1246 find_interesting_uses_op (data
, *var_p
);
1247 find_interesting_uses_op (data
, *bound_p
);
1251 civ
= XNEW (struct iv
);
1253 record_use (data
, cond_p
, civ
, stmt
, USE_COMPARE
);
1256 /* Returns true if expression EXPR is obviously invariant in LOOP,
1257 i.e. if all its operands are defined outside of the LOOP. */
1260 expr_invariant_in_loop_p (struct loop
*loop
, tree expr
)
1265 if (is_gimple_min_invariant (expr
))
1268 if (TREE_CODE (expr
) == SSA_NAME
)
1270 def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (expr
));
1272 && flow_bb_inside_loop_p (loop
, def_bb
))
1278 if (!EXPR_P (expr
) && !GIMPLE_STMT_P (expr
))
1281 len
= TREE_OPERAND_LENGTH (expr
);
1282 for (i
= 0; i
< len
; i
++)
1283 if (!expr_invariant_in_loop_p (loop
, TREE_OPERAND (expr
, i
)))
1289 /* Cumulates the steps of indices into DATA and replaces their values with the
1290 initial ones. Returns false when the value of the index cannot be determined.
1291 Callback for for_each_index. */
1293 struct ifs_ivopts_data
1295 struct ivopts_data
*ivopts_data
;
1301 idx_find_step (tree base
, tree
*idx
, void *data
)
1303 struct ifs_ivopts_data
*dta
= (struct ifs_ivopts_data
*) data
;
1305 tree step
, iv_base
, iv_step
, lbound
, off
;
1306 struct loop
*loop
= dta
->ivopts_data
->current_loop
;
1308 if (TREE_CODE (base
) == MISALIGNED_INDIRECT_REF
1309 || TREE_CODE (base
) == ALIGN_INDIRECT_REF
)
1312 /* If base is a component ref, require that the offset of the reference
1314 if (TREE_CODE (base
) == COMPONENT_REF
)
1316 off
= component_ref_field_offset (base
);
1317 return expr_invariant_in_loop_p (loop
, off
);
1320 /* If base is array, first check whether we will be able to move the
1321 reference out of the loop (in order to take its address in strength
1322 reduction). In order for this to work we need both lower bound
1323 and step to be loop invariants. */
1324 if (TREE_CODE (base
) == ARRAY_REF
)
1326 step
= array_ref_element_size (base
);
1327 lbound
= array_ref_low_bound (base
);
1329 if (!expr_invariant_in_loop_p (loop
, step
)
1330 || !expr_invariant_in_loop_p (loop
, lbound
))
1334 if (TREE_CODE (*idx
) != SSA_NAME
)
1337 iv
= get_iv (dta
->ivopts_data
, *idx
);
1341 /* XXX We produce for a base of *D42 with iv->base being &x[0]
1342 *&x[0], which is not folded and does not trigger the
1343 ARRAY_REF path below. */
1346 if (integer_zerop (iv
->step
))
1349 if (TREE_CODE (base
) == ARRAY_REF
)
1351 step
= array_ref_element_size (base
);
1353 /* We only handle addresses whose step is an integer constant. */
1354 if (TREE_CODE (step
) != INTEGER_CST
)
1358 /* The step for pointer arithmetics already is 1 byte. */
1359 step
= build_int_cst (sizetype
, 1);
1363 if (!convert_affine_scev (dta
->ivopts_data
->current_loop
,
1364 sizetype
, &iv_base
, &iv_step
, dta
->stmt
,
1367 /* The index might wrap. */
1371 step
= fold_build2 (MULT_EXPR
, sizetype
, step
, iv_step
);
1372 dta
->step
= fold_build2 (PLUS_EXPR
, sizetype
, dta
->step
, step
);
1377 /* Records use in index IDX. Callback for for_each_index. Ivopts data
1378 object is passed to it in DATA. */
1381 idx_record_use (tree base
, tree
*idx
,
1384 struct ivopts_data
*data
= (struct ivopts_data
*) vdata
;
1385 find_interesting_uses_op (data
, *idx
);
1386 if (TREE_CODE (base
) == ARRAY_REF
)
1388 find_interesting_uses_op (data
, array_ref_element_size (base
));
1389 find_interesting_uses_op (data
, array_ref_low_bound (base
));
1394 /* Returns true if memory reference REF may be unaligned. */
1397 may_be_unaligned_p (tree ref
)
1401 HOST_WIDE_INT bitsize
;
1402 HOST_WIDE_INT bitpos
;
1404 enum machine_mode mode
;
1405 int unsignedp
, volatilep
;
1406 unsigned base_align
;
1408 /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
1409 thus they are not misaligned. */
1410 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
1413 /* The test below is basically copy of what expr.c:normal_inner_ref
1414 does to check whether the object must be loaded by parts when
1415 STRICT_ALIGNMENT is true. */
1416 base
= get_inner_reference (ref
, &bitsize
, &bitpos
, &toffset
, &mode
,
1417 &unsignedp
, &volatilep
, true);
1418 base_type
= TREE_TYPE (base
);
1419 base_align
= TYPE_ALIGN (base_type
);
1422 && (base_align
< GET_MODE_ALIGNMENT (mode
)
1423 || bitpos
% GET_MODE_ALIGNMENT (mode
) != 0
1424 || bitpos
% BITS_PER_UNIT
!= 0))
1430 /* Return true if EXPR may be non-addressable. */
1433 may_be_nonaddressable_p (tree expr
)
1435 switch (TREE_CODE (expr
))
1438 return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr
, 1))
1439 || may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1442 case ARRAY_RANGE_REF
:
1443 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1445 case VIEW_CONVERT_EXPR
:
1446 /* This kind of view-conversions may wrap non-addressable objects
1447 and make them look addressable. After some processing the
1448 non-addressability may be uncovered again, causing ADDR_EXPRs
1449 of inappropriate objects to be built. */
1450 return AGGREGATE_TYPE_P (TREE_TYPE (expr
))
1451 && !AGGREGATE_TYPE_P (TREE_TYPE (TREE_OPERAND (expr
, 0)));
1460 /* Finds addresses in *OP_P inside STMT. */
1463 find_interesting_uses_address (struct ivopts_data
*data
, tree stmt
, tree
*op_p
)
1465 tree base
= *op_p
, step
= build_int_cst (sizetype
, 0);
1467 struct ifs_ivopts_data ifs_ivopts_data
;
1469 /* Do not play with volatile memory references. A bit too conservative,
1470 perhaps, but safe. */
1471 if (stmt_ann (stmt
)->has_volatile_ops
)
1474 /* Ignore bitfields for now. Not really something terribly complicated
1476 if (TREE_CODE (base
) == BIT_FIELD_REF
)
1479 if (may_be_nonaddressable_p (base
))
1482 if (STRICT_ALIGNMENT
1483 && may_be_unaligned_p (base
))
1486 base
= unshare_expr (base
);
1488 if (TREE_CODE (base
) == TARGET_MEM_REF
)
1490 tree type
= build_pointer_type (TREE_TYPE (base
));
1494 && TREE_CODE (TMR_BASE (base
)) == SSA_NAME
)
1496 civ
= get_iv (data
, TMR_BASE (base
));
1500 TMR_BASE (base
) = civ
->base
;
1503 if (TMR_INDEX (base
)
1504 && TREE_CODE (TMR_INDEX (base
)) == SSA_NAME
)
1506 civ
= get_iv (data
, TMR_INDEX (base
));
1510 TMR_INDEX (base
) = civ
->base
;
1515 if (TMR_STEP (base
))
1516 astep
= fold_build2 (MULT_EXPR
, type
, TMR_STEP (base
), astep
);
1518 step
= fold_build2 (PLUS_EXPR
, type
, step
, astep
);
1522 if (integer_zerop (step
))
1524 base
= tree_mem_ref_addr (type
, base
);
1528 ifs_ivopts_data
.ivopts_data
= data
;
1529 ifs_ivopts_data
.stmt
= stmt
;
1530 ifs_ivopts_data
.step
= build_int_cst (sizetype
, 0);
1531 if (!for_each_index (&base
, idx_find_step
, &ifs_ivopts_data
)
1532 || integer_zerop (ifs_ivopts_data
.step
))
1534 step
= ifs_ivopts_data
.step
;
1536 gcc_assert (TREE_CODE (base
) != ALIGN_INDIRECT_REF
);
1537 gcc_assert (TREE_CODE (base
) != MISALIGNED_INDIRECT_REF
);
1539 base
= build_fold_addr_expr (base
);
1541 /* Substituting bases of IVs into the base expression might
1542 have caused folding opportunities. */
1543 if (TREE_CODE (base
) == ADDR_EXPR
)
1545 tree
*ref
= &TREE_OPERAND (base
, 0);
1546 while (handled_component_p (*ref
))
1547 ref
= &TREE_OPERAND (*ref
, 0);
1548 if (TREE_CODE (*ref
) == INDIRECT_REF
)
1549 *ref
= fold_indirect_ref (*ref
);
1553 civ
= alloc_iv (base
, step
);
1554 record_use (data
, op_p
, civ
, stmt
, USE_ADDRESS
);
1558 for_each_index (op_p
, idx_record_use
, data
);
1561 /* Finds and records invariants used in STMT. */
1564 find_invariants_stmt (struct ivopts_data
*data
, tree stmt
)
1567 use_operand_p use_p
;
1570 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1572 op
= USE_FROM_PTR (use_p
);
1573 record_invariant (data
, op
, false);
1577 /* Finds interesting uses of induction variables in the statement STMT. */
1580 find_interesting_uses_stmt (struct ivopts_data
*data
, tree stmt
)
1585 use_operand_p use_p
;
1587 find_invariants_stmt (data
, stmt
);
1589 if (TREE_CODE (stmt
) == COND_EXPR
)
1591 find_interesting_uses_cond (data
, stmt
, &COND_EXPR_COND (stmt
));
1595 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
1597 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
1598 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1600 if (TREE_CODE (lhs
) == SSA_NAME
)
1602 /* If the statement defines an induction variable, the uses are not
1603 interesting by themselves. */
1605 iv
= get_iv (data
, lhs
);
1607 if (iv
&& !integer_zerop (iv
->step
))
1611 switch (TREE_CODE_CLASS (TREE_CODE (rhs
)))
1613 case tcc_comparison
:
1614 find_interesting_uses_cond (data
, stmt
,
1615 &GIMPLE_STMT_OPERAND (stmt
, 1));
1619 find_interesting_uses_address (data
, stmt
,
1620 &GIMPLE_STMT_OPERAND (stmt
, 1));
1621 if (REFERENCE_CLASS_P (lhs
))
1622 find_interesting_uses_address (data
, stmt
,
1623 &GIMPLE_STMT_OPERAND (stmt
, 0));
1629 if (REFERENCE_CLASS_P (lhs
)
1630 && is_gimple_val (rhs
))
1632 find_interesting_uses_address (data
, stmt
,
1633 &GIMPLE_STMT_OPERAND (stmt
, 0));
1634 find_interesting_uses_op (data
, rhs
);
1638 /* TODO -- we should also handle address uses of type
1640 memory = call (whatever);
1647 if (TREE_CODE (stmt
) == PHI_NODE
1648 && bb_for_stmt (stmt
) == data
->current_loop
->header
)
1650 lhs
= PHI_RESULT (stmt
);
1651 iv
= get_iv (data
, lhs
);
1653 if (iv
&& !integer_zerop (iv
->step
))
1657 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1659 op
= USE_FROM_PTR (use_p
);
1661 if (TREE_CODE (op
) != SSA_NAME
)
1664 iv
= get_iv (data
, op
);
1668 find_interesting_uses_op (data
, op
);
1672 /* Finds interesting uses of induction variables outside of loops
1673 on loop exit edge EXIT. */
1676 find_interesting_uses_outside (struct ivopts_data
*data
, edge exit
)
1680 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= PHI_CHAIN (phi
))
1682 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1683 if (is_gimple_reg (def
))
1684 find_interesting_uses_op (data
, def
);
1688 /* Finds uses of the induction variables that are interesting. */
1691 find_interesting_uses (struct ivopts_data
*data
)
1694 block_stmt_iterator bsi
;
1696 basic_block
*body
= get_loop_body (data
->current_loop
);
1698 struct version_info
*info
;
1701 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1702 fprintf (dump_file
, "Uses:\n\n");
1704 for (i
= 0; i
< data
->current_loop
->num_nodes
; i
++)
1709 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1710 if (e
->dest
!= EXIT_BLOCK_PTR
1711 && !flow_bb_inside_loop_p (data
->current_loop
, e
->dest
))
1712 find_interesting_uses_outside (data
, e
);
1714 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1715 find_interesting_uses_stmt (data
, phi
);
1716 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1717 find_interesting_uses_stmt (data
, bsi_stmt (bsi
));
1720 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1724 fprintf (dump_file
, "\n");
1726 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1728 info
= ver_info (data
, i
);
1731 fprintf (dump_file
, " ");
1732 print_generic_expr (dump_file
, info
->name
, TDF_SLIM
);
1733 fprintf (dump_file
, " is invariant (%d)%s\n",
1734 info
->inv_id
, info
->has_nonlin_use
? "" : ", eliminable");
1738 fprintf (dump_file
, "\n");
1744 /* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
1745 is true, assume we are inside an address. If TOP_COMPREF is true, assume
1746 we are at the top-level of the processed address. */
1749 strip_offset_1 (tree expr
, bool inside_addr
, bool top_compref
,
1750 unsigned HOST_WIDE_INT
*offset
)
1752 tree op0
= NULL_TREE
, op1
= NULL_TREE
, tmp
, step
;
1753 enum tree_code code
;
1754 tree type
, orig_type
= TREE_TYPE (expr
);
1755 unsigned HOST_WIDE_INT off0
, off1
, st
;
1756 tree orig_expr
= expr
;
1760 type
= TREE_TYPE (expr
);
1761 code
= TREE_CODE (expr
);
1767 if (!cst_and_fits_in_hwi (expr
)
1768 || integer_zerop (expr
))
1771 *offset
= int_cst_value (expr
);
1772 return build_int_cst (orig_type
, 0);
1774 case POINTER_PLUS_EXPR
:
1777 op0
= TREE_OPERAND (expr
, 0);
1778 op1
= TREE_OPERAND (expr
, 1);
1780 op0
= strip_offset_1 (op0
, false, false, &off0
);
1781 op1
= strip_offset_1 (op1
, false, false, &off1
);
1783 *offset
= (code
== MINUS_EXPR
? off0
- off1
: off0
+ off1
);
1784 if (op0
== TREE_OPERAND (expr
, 0)
1785 && op1
== TREE_OPERAND (expr
, 1))
1788 if (integer_zerop (op1
))
1790 else if (integer_zerop (op0
))
1792 if (code
== MINUS_EXPR
)
1793 expr
= fold_build1 (NEGATE_EXPR
, type
, op1
);
1798 expr
= fold_build2 (code
, type
, op0
, op1
);
1800 return fold_convert (orig_type
, expr
);
1806 step
= array_ref_element_size (expr
);
1807 if (!cst_and_fits_in_hwi (step
))
1810 st
= int_cst_value (step
);
1811 op1
= TREE_OPERAND (expr
, 1);
1812 op1
= strip_offset_1 (op1
, false, false, &off1
);
1813 *offset
= off1
* st
;
1816 && integer_zerop (op1
))
1818 /* Strip the component reference completely. */
1819 op0
= TREE_OPERAND (expr
, 0);
1820 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
1830 tmp
= component_ref_field_offset (expr
);
1832 && cst_and_fits_in_hwi (tmp
))
1834 /* Strip the component reference completely. */
1835 op0
= TREE_OPERAND (expr
, 0);
1836 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
1837 *offset
= off0
+ int_cst_value (tmp
);
1843 op0
= TREE_OPERAND (expr
, 0);
1844 op0
= strip_offset_1 (op0
, true, true, &off0
);
1847 if (op0
== TREE_OPERAND (expr
, 0))
1850 expr
= build_fold_addr_expr (op0
);
1851 return fold_convert (orig_type
, expr
);
1854 inside_addr
= false;
1861 /* Default handling of expressions for that we want to recurse into
1862 the first operand. */
1863 op0
= TREE_OPERAND (expr
, 0);
1864 op0
= strip_offset_1 (op0
, inside_addr
, false, &off0
);
1867 if (op0
== TREE_OPERAND (expr
, 0)
1868 && (!op1
|| op1
== TREE_OPERAND (expr
, 1)))
1871 expr
= copy_node (expr
);
1872 TREE_OPERAND (expr
, 0) = op0
;
1874 TREE_OPERAND (expr
, 1) = op1
;
1876 /* Inside address, we might strip the top level component references,
1877 thus changing type of the expression. Handling of ADDR_EXPR
1879 expr
= fold_convert (orig_type
, expr
);
1884 /* Strips constant offsets from EXPR and stores them to OFFSET. */
1887 strip_offset (tree expr
, unsigned HOST_WIDE_INT
*offset
)
1889 return strip_offset_1 (expr
, false, false, offset
);
1892 /* Returns variant of TYPE that can be used as base for different uses.
1893 We return unsigned type with the same precision, which avoids problems
1897 generic_type_for (tree type
)
1899 if (POINTER_TYPE_P (type
))
1900 return unsigned_type_for (type
);
1902 if (TYPE_UNSIGNED (type
))
1905 return unsigned_type_for (type
);
1908 /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
1909 the bitmap to that we should store it. */
1911 static struct ivopts_data
*fd_ivopts_data
;
1913 find_depends (tree
*expr_p
, int *ws ATTRIBUTE_UNUSED
, void *data
)
1915 bitmap
*depends_on
= (bitmap
*) data
;
1916 struct version_info
*info
;
1918 if (TREE_CODE (*expr_p
) != SSA_NAME
)
1920 info
= name_info (fd_ivopts_data
, *expr_p
);
1922 if (!info
->inv_id
|| info
->has_nonlin_use
)
1926 *depends_on
= BITMAP_ALLOC (NULL
);
1927 bitmap_set_bit (*depends_on
, info
->inv_id
);
1932 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
1933 position to POS. If USE is not NULL, the candidate is set as related to
1934 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
1935 replacement of the final value of the iv by a direct computation. */
1937 static struct iv_cand
*
1938 add_candidate_1 (struct ivopts_data
*data
,
1939 tree base
, tree step
, bool important
, enum iv_position pos
,
1940 struct iv_use
*use
, tree incremented_at
)
1943 struct iv_cand
*cand
= NULL
;
1944 tree type
, orig_type
;
1948 orig_type
= TREE_TYPE (base
);
1949 type
= generic_type_for (orig_type
);
1950 if (type
!= orig_type
)
1952 base
= fold_convert (type
, base
);
1953 step
= fold_convert (type
, step
);
1957 for (i
= 0; i
< n_iv_cands (data
); i
++)
1959 cand
= iv_cand (data
, i
);
1961 if (cand
->pos
!= pos
)
1964 if (cand
->incremented_at
!= incremented_at
)
1978 if (operand_equal_p (base
, cand
->iv
->base
, 0)
1979 && operand_equal_p (step
, cand
->iv
->step
, 0))
1983 if (i
== n_iv_cands (data
))
1985 cand
= XCNEW (struct iv_cand
);
1991 cand
->iv
= alloc_iv (base
, step
);
1994 if (pos
!= IP_ORIGINAL
&& cand
->iv
)
1996 cand
->var_before
= create_tmp_var_raw (TREE_TYPE (base
), "ivtmp");
1997 cand
->var_after
= cand
->var_before
;
1999 cand
->important
= important
;
2000 cand
->incremented_at
= incremented_at
;
2001 VEC_safe_push (iv_cand_p
, heap
, data
->iv_candidates
, cand
);
2004 && TREE_CODE (step
) != INTEGER_CST
)
2006 fd_ivopts_data
= data
;
2007 walk_tree (&step
, find_depends
, &cand
->depends_on
, NULL
);
2010 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2011 dump_cand (dump_file
, cand
);
2014 if (important
&& !cand
->important
)
2016 cand
->important
= true;
2017 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2018 fprintf (dump_file
, "Candidate %d is important\n", cand
->id
);
2023 bitmap_set_bit (use
->related_cands
, i
);
2024 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2025 fprintf (dump_file
, "Candidate %d is related to use %d\n",
2032 /* Returns true if incrementing the induction variable at the end of the LOOP
2035 The purpose is to avoid splitting latch edge with a biv increment, thus
2036 creating a jump, possibly confusing other optimization passes and leaving
2037 less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS
2038 is not available (so we do not have a better alternative), or if the latch
2039 edge is already nonempty. */
2042 allow_ip_end_pos_p (struct loop
*loop
)
2044 if (!ip_normal_pos (loop
))
2047 if (!empty_block_p (ip_end_pos (loop
)))
2053 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2054 position to POS. If USE is not NULL, the candidate is set as related to
2055 it. The candidate computation is scheduled on all available positions. */
2058 add_candidate (struct ivopts_data
*data
,
2059 tree base
, tree step
, bool important
, struct iv_use
*use
)
2061 if (ip_normal_pos (data
->current_loop
))
2062 add_candidate_1 (data
, base
, step
, important
, IP_NORMAL
, use
, NULL_TREE
);
2063 if (ip_end_pos (data
->current_loop
)
2064 && allow_ip_end_pos_p (data
->current_loop
))
2065 add_candidate_1 (data
, base
, step
, important
, IP_END
, use
, NULL_TREE
);
2068 /* Add a standard "0 + 1 * iteration" iv candidate for a
2069 type with SIZE bits. */
2072 add_standard_iv_candidates_for_size (struct ivopts_data
*data
,
2075 tree type
= lang_hooks
.types
.type_for_size (size
, true);
2076 add_candidate (data
, build_int_cst (type
, 0), build_int_cst (type
, 1),
2080 /* Adds standard iv candidates. */
2083 add_standard_iv_candidates (struct ivopts_data
*data
)
2085 add_standard_iv_candidates_for_size (data
, INT_TYPE_SIZE
);
2087 /* The same for a double-integer type if it is still fast enough. */
2088 if (BITS_PER_WORD
>= INT_TYPE_SIZE
* 2)
2089 add_standard_iv_candidates_for_size (data
, INT_TYPE_SIZE
* 2);
2093 /* Adds candidates bases on the old induction variable IV. */
2096 add_old_iv_candidates (struct ivopts_data
*data
, struct iv
*iv
)
2099 struct iv_cand
*cand
;
2101 add_candidate (data
, iv
->base
, iv
->step
, true, NULL
);
2103 /* The same, but with initial value zero. */
2104 add_candidate (data
,
2105 build_int_cst (TREE_TYPE (iv
->base
), 0),
2106 iv
->step
, true, NULL
);
2108 phi
= SSA_NAME_DEF_STMT (iv
->ssa_name
);
2109 if (TREE_CODE (phi
) == PHI_NODE
)
2111 /* Additionally record the possibility of leaving the original iv
2113 def
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (data
->current_loop
));
2114 cand
= add_candidate_1 (data
,
2115 iv
->base
, iv
->step
, true, IP_ORIGINAL
, NULL
,
2116 SSA_NAME_DEF_STMT (def
));
2117 cand
->var_before
= iv
->ssa_name
;
2118 cand
->var_after
= def
;
2122 /* Adds candidates based on the old induction variables. */
2125 add_old_ivs_candidates (struct ivopts_data
*data
)
2131 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
2133 iv
= ver_info (data
, i
)->iv
;
2134 if (iv
&& iv
->biv_p
&& !integer_zerop (iv
->step
))
2135 add_old_iv_candidates (data
, iv
);
2139 /* Adds candidates based on the value of the induction variable IV and USE. */
2142 add_iv_value_candidates (struct ivopts_data
*data
,
2143 struct iv
*iv
, struct iv_use
*use
)
2145 unsigned HOST_WIDE_INT offset
;
2148 add_candidate (data
, iv
->base
, iv
->step
, false, use
);
2150 /* The same, but with initial value zero. Make such variable important,
2151 since it is generic enough so that possibly many uses may be based
2153 add_candidate (data
, build_int_cst (TREE_TYPE (iv
->base
), 0),
2154 iv
->step
, true, use
);
2156 /* Third, try removing the constant offset. */
2157 base
= strip_offset (iv
->base
, &offset
);
2159 add_candidate (data
, base
, iv
->step
, false, use
);
2162 /* Adds candidates based on the uses. */
2165 add_derived_ivs_candidates (struct ivopts_data
*data
)
2169 for (i
= 0; i
< n_iv_uses (data
); i
++)
2171 struct iv_use
*use
= iv_use (data
, i
);
2178 case USE_NONLINEAR_EXPR
:
2181 /* Just add the ivs based on the value of the iv used here. */
2182 add_iv_value_candidates (data
, use
->iv
, use
);
2191 /* Record important candidates and add them to related_cands bitmaps
2195 record_important_candidates (struct ivopts_data
*data
)
2200 for (i
= 0; i
< n_iv_cands (data
); i
++)
2202 struct iv_cand
*cand
= iv_cand (data
, i
);
2204 if (cand
->important
)
2205 bitmap_set_bit (data
->important_candidates
, i
);
2208 data
->consider_all_candidates
= (n_iv_cands (data
)
2209 <= CONSIDER_ALL_CANDIDATES_BOUND
);
2211 if (data
->consider_all_candidates
)
2213 /* We will not need "related_cands" bitmaps in this case,
2214 so release them to decrease peak memory consumption. */
2215 for (i
= 0; i
< n_iv_uses (data
); i
++)
2217 use
= iv_use (data
, i
);
2218 BITMAP_FREE (use
->related_cands
);
2223 /* Add important candidates to the related_cands bitmaps. */
2224 for (i
= 0; i
< n_iv_uses (data
); i
++)
2225 bitmap_ior_into (iv_use (data
, i
)->related_cands
,
2226 data
->important_candidates
);
2230 /* Finds the candidates for the induction variables. */
2233 find_iv_candidates (struct ivopts_data
*data
)
2235 /* Add commonly used ivs. */
2236 add_standard_iv_candidates (data
);
2238 /* Add old induction variables. */
2239 add_old_ivs_candidates (data
);
2241 /* Add induction variables derived from uses. */
2242 add_derived_ivs_candidates (data
);
2244 /* Record the important candidates. */
2245 record_important_candidates (data
);
2248 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
2249 If consider_all_candidates is true, we use a two-dimensional array, otherwise
2250 we allocate a simple list to every use. */
2253 alloc_use_cost_map (struct ivopts_data
*data
)
2255 unsigned i
, size
, s
, j
;
2257 for (i
= 0; i
< n_iv_uses (data
); i
++)
2259 struct iv_use
*use
= iv_use (data
, i
);
2262 if (data
->consider_all_candidates
)
2263 size
= n_iv_cands (data
);
2267 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, j
, bi
)
2272 /* Round up to the power of two, so that moduling by it is fast. */
2273 for (size
= 1; size
< s
; size
<<= 1)
2277 use
->n_map_members
= size
;
2278 use
->cost_map
= XCNEWVEC (struct cost_pair
, size
);
2282 /* Returns description of computation cost of expression whose runtime
2283 cost is RUNTIME and complexity corresponds to COMPLEXITY. */
2286 new_cost (unsigned runtime
, unsigned complexity
)
2290 cost
.cost
= runtime
;
2291 cost
.complexity
= complexity
;
2296 /* Adds costs COST1 and COST2. */
2299 add_costs (comp_cost cost1
, comp_cost cost2
)
2301 cost1
.cost
+= cost2
.cost
;
2302 cost1
.complexity
+= cost2
.complexity
;
2306 /* Subtracts costs COST1 and COST2. */
2309 sub_costs (comp_cost cost1
, comp_cost cost2
)
2311 cost1
.cost
-= cost2
.cost
;
2312 cost1
.complexity
-= cost2
.complexity
;
2317 /* Returns a negative number if COST1 < COST2, a positive number if
2318 COST1 > COST2, and 0 if COST1 = COST2. */
2321 compare_costs (comp_cost cost1
, comp_cost cost2
)
2323 if (cost1
.cost
== cost2
.cost
)
2324 return cost1
.complexity
- cost2
.complexity
;
2326 return cost1
.cost
- cost2
.cost
;
2329 /* Returns true if COST is infinite. */
2332 infinite_cost_p (comp_cost cost
)
2334 return cost
.cost
== INFTY
;
2337 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
2338 on invariants DEPENDS_ON and that the value used in expressing it
2342 set_use_iv_cost (struct ivopts_data
*data
,
2343 struct iv_use
*use
, struct iv_cand
*cand
,
2344 comp_cost cost
, bitmap depends_on
, tree value
)
2348 if (infinite_cost_p (cost
))
2350 BITMAP_FREE (depends_on
);
2354 if (data
->consider_all_candidates
)
2356 use
->cost_map
[cand
->id
].cand
= cand
;
2357 use
->cost_map
[cand
->id
].cost
= cost
;
2358 use
->cost_map
[cand
->id
].depends_on
= depends_on
;
2359 use
->cost_map
[cand
->id
].value
= value
;
2363 /* n_map_members is a power of two, so this computes modulo. */
2364 s
= cand
->id
& (use
->n_map_members
- 1);
2365 for (i
= s
; i
< use
->n_map_members
; i
++)
2366 if (!use
->cost_map
[i
].cand
)
2368 for (i
= 0; i
< s
; i
++)
2369 if (!use
->cost_map
[i
].cand
)
2375 use
->cost_map
[i
].cand
= cand
;
2376 use
->cost_map
[i
].cost
= cost
;
2377 use
->cost_map
[i
].depends_on
= depends_on
;
2378 use
->cost_map
[i
].value
= value
;
2381 /* Gets cost of (USE, CANDIDATE) pair. */
2383 static struct cost_pair
*
2384 get_use_iv_cost (struct ivopts_data
*data
, struct iv_use
*use
,
2385 struct iv_cand
*cand
)
2388 struct cost_pair
*ret
;
2393 if (data
->consider_all_candidates
)
2395 ret
= use
->cost_map
+ cand
->id
;
2402 /* n_map_members is a power of two, so this computes modulo. */
2403 s
= cand
->id
& (use
->n_map_members
- 1);
2404 for (i
= s
; i
< use
->n_map_members
; i
++)
2405 if (use
->cost_map
[i
].cand
== cand
)
2406 return use
->cost_map
+ i
;
2408 for (i
= 0; i
< s
; i
++)
2409 if (use
->cost_map
[i
].cand
== cand
)
2410 return use
->cost_map
+ i
;
2415 /* Returns estimate on cost of computing SEQ. */
2423 for (; seq
; seq
= NEXT_INSN (seq
))
2425 set
= single_set (seq
);
2427 cost
+= rtx_cost (set
, SET
);
2435 /* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
2437 produce_memory_decl_rtl (tree obj
, int *regno
)
2442 if (TREE_STATIC (obj
) || DECL_EXTERNAL (obj
))
2444 const char *name
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj
));
2445 x
= gen_rtx_SYMBOL_REF (Pmode
, name
);
2446 SET_SYMBOL_REF_DECL (x
, obj
);
2447 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
2448 targetm
.encode_section_info (obj
, x
, true);
2452 x
= gen_raw_REG (Pmode
, (*regno
)++);
2453 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
2459 /* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
2460 walk_tree. DATA contains the actual fake register number. */
2463 prepare_decl_rtl (tree
*expr_p
, int *ws
, void *data
)
2465 tree obj
= NULL_TREE
;
2467 int *regno
= (int *) data
;
2469 switch (TREE_CODE (*expr_p
))
2472 for (expr_p
= &TREE_OPERAND (*expr_p
, 0);
2473 handled_component_p (*expr_p
);
2474 expr_p
= &TREE_OPERAND (*expr_p
, 0))
2477 if (DECL_P (obj
) && !DECL_RTL_SET_P (obj
))
2478 x
= produce_memory_decl_rtl (obj
, regno
);
2483 obj
= SSA_NAME_VAR (*expr_p
);
2484 if (!DECL_RTL_SET_P (obj
))
2485 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2494 if (DECL_RTL_SET_P (obj
))
2497 if (DECL_MODE (obj
) == BLKmode
)
2498 x
= produce_memory_decl_rtl (obj
, regno
);
2500 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2510 VEC_safe_push (tree
, heap
, decl_rtl_to_reset
, obj
);
2511 SET_DECL_RTL (obj
, x
);
2517 /* Determines cost of the computation of EXPR. */
2520 computation_cost (tree expr
)
2523 tree type
= TREE_TYPE (expr
);
2525 /* Avoid using hard regs in ways which may be unsupported. */
2526 int regno
= LAST_VIRTUAL_REGISTER
+ 1;
2528 walk_tree (&expr
, prepare_decl_rtl
, ®no
, NULL
);
2530 rslt
= expand_expr (expr
, NULL_RTX
, TYPE_MODE (type
), EXPAND_NORMAL
);
2534 cost
= seq_cost (seq
);
2536 cost
+= address_cost (XEXP (rslt
, 0), TYPE_MODE (type
));
2541 /* Returns variable containing the value of candidate CAND at statement AT. */
2544 var_at_stmt (struct loop
*loop
, struct iv_cand
*cand
, tree stmt
)
2546 if (stmt_after_increment (loop
, cand
, stmt
))
2547 return cand
->var_after
;
2549 return cand
->var_before
;
2552 /* Return the most significant (sign) bit of T. Similar to tree_int_cst_msb,
2553 but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE. */
2556 tree_int_cst_sign_bit (const_tree t
)
2558 unsigned bitno
= TYPE_PRECISION (TREE_TYPE (t
)) - 1;
2559 unsigned HOST_WIDE_INT w
;
2561 if (bitno
< HOST_BITS_PER_WIDE_INT
)
2562 w
= TREE_INT_CST_LOW (t
);
2565 w
= TREE_INT_CST_HIGH (t
);
2566 bitno
-= HOST_BITS_PER_WIDE_INT
;
2569 return (w
>> bitno
) & 1;
2572 /* If we can prove that TOP = cst * BOT for some constant cst,
2573 store cst to MUL and return true. Otherwise return false.
2574 The returned value is always sign-extended, regardless of the
2575 signedness of TOP and BOT. */
2578 constant_multiple_of (tree top
, tree bot
, double_int
*mul
)
2581 enum tree_code code
;
2582 double_int res
, p0
, p1
;
2583 unsigned precision
= TYPE_PRECISION (TREE_TYPE (top
));
2588 if (operand_equal_p (top
, bot
, 0))
2590 *mul
= double_int_one
;
2594 code
= TREE_CODE (top
);
2598 mby
= TREE_OPERAND (top
, 1);
2599 if (TREE_CODE (mby
) != INTEGER_CST
)
2602 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &res
))
2605 *mul
= double_int_sext (double_int_mul (res
, tree_to_double_int (mby
)),
2611 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &p0
)
2612 || !constant_multiple_of (TREE_OPERAND (top
, 1), bot
, &p1
))
2615 if (code
== MINUS_EXPR
)
2616 p1
= double_int_neg (p1
);
2617 *mul
= double_int_sext (double_int_add (p0
, p1
), precision
);
2621 if (TREE_CODE (bot
) != INTEGER_CST
)
2624 p0
= double_int_sext (tree_to_double_int (top
), precision
);
2625 p1
= double_int_sext (tree_to_double_int (bot
), precision
);
2626 if (double_int_zero_p (p1
))
2628 *mul
= double_int_sext (double_int_sdivmod (p0
, p1
, FLOOR_DIV_EXPR
, &res
),
2630 return double_int_zero_p (res
);
2637 /* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
2638 same precision that is at least as wide as the precision of TYPE, stores
2639 BA to A and BB to B, and returns the type of BA. Otherwise, returns the
2643 determine_common_wider_type (tree
*a
, tree
*b
)
2645 tree wider_type
= NULL
;
2647 tree atype
= TREE_TYPE (*a
);
2649 if ((TREE_CODE (*a
) == NOP_EXPR
2650 || TREE_CODE (*a
) == CONVERT_EXPR
))
2652 suba
= TREE_OPERAND (*a
, 0);
2653 wider_type
= TREE_TYPE (suba
);
2654 if (TYPE_PRECISION (wider_type
) < TYPE_PRECISION (atype
))
2660 if ((TREE_CODE (*b
) == NOP_EXPR
2661 || TREE_CODE (*b
) == CONVERT_EXPR
))
2663 subb
= TREE_OPERAND (*b
, 0);
2664 if (TYPE_PRECISION (wider_type
) != TYPE_PRECISION (TREE_TYPE (subb
)))
2675 /* Determines the expression by that USE is expressed from induction variable
2676 CAND at statement AT in LOOP. The expression is stored in a decomposed
2677 form into AFF. Returns false if USE cannot be expressed using CAND. */
2680 get_computation_aff (struct loop
*loop
,
2681 struct iv_use
*use
, struct iv_cand
*cand
, tree at
,
2682 struct affine_tree_combination
*aff
)
2684 tree ubase
= use
->iv
->base
;
2685 tree ustep
= use
->iv
->step
;
2686 tree cbase
= cand
->iv
->base
;
2687 tree cstep
= cand
->iv
->step
, cstep_common
;
2688 tree utype
= TREE_TYPE (ubase
), ctype
= TREE_TYPE (cbase
);
2689 tree common_type
, var
;
2691 aff_tree cbase_aff
, var_aff
;
2694 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
2696 /* We do not have a precision to express the values of use. */
2700 var
= var_at_stmt (loop
, cand
, at
);
2701 uutype
= unsigned_type_for (utype
);
2703 /* If the conversion is not noop, perform it. */
2704 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
2706 cstep
= fold_convert (uutype
, cstep
);
2707 cbase
= fold_convert (uutype
, cbase
);
2708 var
= fold_convert (uutype
, var
);
2711 if (!constant_multiple_of (ustep
, cstep
, &rat
))
2714 /* In case both UBASE and CBASE are shortened to UUTYPE from some common
2715 type, we achieve better folding by computing their difference in this
2716 wider type, and cast the result to UUTYPE. We do not need to worry about
2717 overflows, as all the arithmetics will in the end be performed in UUTYPE
2719 common_type
= determine_common_wider_type (&ubase
, &cbase
);
2721 /* use = ubase - ratio * cbase + ratio * var. */
2722 tree_to_aff_combination (ubase
, common_type
, aff
);
2723 tree_to_aff_combination (cbase
, common_type
, &cbase_aff
);
2724 tree_to_aff_combination (var
, uutype
, &var_aff
);
2726 /* We need to shift the value if we are after the increment. */
2727 if (stmt_after_increment (loop
, cand
, at
))
2731 if (common_type
!= uutype
)
2732 cstep_common
= fold_convert (common_type
, cstep
);
2734 cstep_common
= cstep
;
2736 tree_to_aff_combination (cstep_common
, common_type
, &cstep_aff
);
2737 aff_combination_add (&cbase_aff
, &cstep_aff
);
2740 aff_combination_scale (&cbase_aff
, double_int_neg (rat
));
2741 aff_combination_add (aff
, &cbase_aff
);
2742 if (common_type
!= uutype
)
2743 aff_combination_convert (aff
, uutype
);
2745 aff_combination_scale (&var_aff
, rat
);
2746 aff_combination_add (aff
, &var_aff
);
2751 /* Determines the expression by that USE is expressed from induction variable
2752 CAND at statement AT in LOOP. The computation is unshared. */
2755 get_computation_at (struct loop
*loop
,
2756 struct iv_use
*use
, struct iv_cand
*cand
, tree at
)
2759 tree type
= TREE_TYPE (use
->iv
->base
);
2761 if (!get_computation_aff (loop
, use
, cand
, at
, &aff
))
2763 unshare_aff_combination (&aff
);
2764 return fold_convert (type
, aff_combination_to_tree (&aff
));
2767 /* Determines the expression by that USE is expressed from induction variable
2768 CAND in LOOP. The computation is unshared. */
2771 get_computation (struct loop
*loop
, struct iv_use
*use
, struct iv_cand
*cand
)
2773 return get_computation_at (loop
, use
, cand
, use
->stmt
);
2776 /* Returns cost of addition in MODE. */
2779 add_cost (enum machine_mode mode
)
2781 static unsigned costs
[NUM_MACHINE_MODES
];
2789 force_operand (gen_rtx_fmt_ee (PLUS
, mode
,
2790 gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 1),
2791 gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 2)),
2796 cost
= seq_cost (seq
);
2802 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2803 fprintf (dump_file
, "Addition in %s costs %d\n",
2804 GET_MODE_NAME (mode
), cost
);
2808 /* Entry in a hashtable of already known costs for multiplication. */
2811 HOST_WIDE_INT cst
; /* The constant to multiply by. */
2812 enum machine_mode mode
; /* In mode. */
2813 unsigned cost
; /* The cost. */
2816 /* Counts hash value for the ENTRY. */
2819 mbc_entry_hash (const void *entry
)
2821 const struct mbc_entry
*e
= (const struct mbc_entry
*) entry
;
2823 return 57 * (hashval_t
) e
->mode
+ (hashval_t
) (e
->cst
% 877);
2826 /* Compares the hash table entries ENTRY1 and ENTRY2. */
2829 mbc_entry_eq (const void *entry1
, const void *entry2
)
2831 const struct mbc_entry
*e1
= (const struct mbc_entry
*) entry1
;
2832 const struct mbc_entry
*e2
= (const struct mbc_entry
*) entry2
;
2834 return (e1
->mode
== e2
->mode
2835 && e1
->cst
== e2
->cst
);
2838 /* Returns cost of multiplication by constant CST in MODE. */
2841 multiply_by_cost (HOST_WIDE_INT cst
, enum machine_mode mode
)
2843 static htab_t costs
;
2844 struct mbc_entry
**cached
, act
;
2849 costs
= htab_create (100, mbc_entry_hash
, mbc_entry_eq
, free
);
2853 cached
= (struct mbc_entry
**) htab_find_slot (costs
, &act
, INSERT
);
2855 return (*cached
)->cost
;
2857 *cached
= XNEW (struct mbc_entry
);
2858 (*cached
)->mode
= mode
;
2859 (*cached
)->cst
= cst
;
2862 expand_mult (mode
, gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 1),
2863 gen_int_mode (cst
, mode
), NULL_RTX
, 0);
2867 cost
= seq_cost (seq
);
2869 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2870 fprintf (dump_file
, "Multiplication by %d in %s costs %d\n",
2871 (int) cst
, GET_MODE_NAME (mode
), cost
);
2873 (*cached
)->cost
= cost
;
2878 /* Returns true if multiplying by RATIO is allowed in an address. Test the
2879 validity for a memory reference accessing memory of mode MODE. */
2882 multiplier_allowed_in_address_p (HOST_WIDE_INT ratio
, enum machine_mode mode
)
2884 #define MAX_RATIO 128
2885 static sbitmap valid_mult
[MAX_MACHINE_MODE
];
2887 if (!valid_mult
[mode
])
2889 rtx reg1
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 1);
2893 valid_mult
[mode
] = sbitmap_alloc (2 * MAX_RATIO
+ 1);
2894 sbitmap_zero (valid_mult
[mode
]);
2895 addr
= gen_rtx_fmt_ee (MULT
, Pmode
, reg1
, NULL_RTX
);
2896 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
2898 XEXP (addr
, 1) = gen_int_mode (i
, Pmode
);
2899 if (memory_address_p (mode
, addr
))
2900 SET_BIT (valid_mult
[mode
], i
+ MAX_RATIO
);
2903 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2905 fprintf (dump_file
, " allowed multipliers:");
2906 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
2907 if (TEST_BIT (valid_mult
[mode
], i
+ MAX_RATIO
))
2908 fprintf (dump_file
, " %d", (int) i
);
2909 fprintf (dump_file
, "\n");
2910 fprintf (dump_file
, "\n");
2914 if (ratio
> MAX_RATIO
|| ratio
< -MAX_RATIO
)
2917 return TEST_BIT (valid_mult
[mode
], ratio
+ MAX_RATIO
);
2920 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
2921 If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
2922 variable is omitted. Compute the cost for a memory reference that accesses
2923 a memory location of mode MEM_MODE.
2925 TODO -- there must be some better way. This all is quite crude. */
2928 get_address_cost (bool symbol_present
, bool var_present
,
2929 unsigned HOST_WIDE_INT offset
, HOST_WIDE_INT ratio
,
2930 enum machine_mode mem_mode
)
2932 static bool initialized
[MAX_MACHINE_MODE
];
2933 static HOST_WIDE_INT rat
[MAX_MACHINE_MODE
], off
[MAX_MACHINE_MODE
];
2934 static HOST_WIDE_INT min_offset
[MAX_MACHINE_MODE
], max_offset
[MAX_MACHINE_MODE
];
2935 static unsigned costs
[MAX_MACHINE_MODE
][2][2][2][2];
2936 unsigned cost
, acost
, complexity
;
2937 bool offset_p
, ratio_p
;
2938 HOST_WIDE_INT s_offset
;
2939 unsigned HOST_WIDE_INT mask
;
2942 if (!initialized
[mem_mode
])
2945 HOST_WIDE_INT start
= BIGGEST_ALIGNMENT
/ BITS_PER_UNIT
;
2946 int old_cse_not_expected
;
2947 unsigned sym_p
, var_p
, off_p
, rat_p
, add_c
;
2948 rtx seq
, addr
, base
;
2951 initialized
[mem_mode
] = true;
2953 reg1
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 1);
2955 addr
= gen_rtx_fmt_ee (PLUS
, Pmode
, reg1
, NULL_RTX
);
2956 for (i
= start
; i
<= 1 << 20; i
<<= 1)
2958 XEXP (addr
, 1) = gen_int_mode (i
, Pmode
);
2959 if (!memory_address_p (mem_mode
, addr
))
2962 max_offset
[mem_mode
] = i
== start
? 0 : i
>> 1;
2963 off
[mem_mode
] = max_offset
[mem_mode
];
2965 for (i
= start
; i
<= 1 << 20; i
<<= 1)
2967 XEXP (addr
, 1) = gen_int_mode (-i
, Pmode
);
2968 if (!memory_address_p (mem_mode
, addr
))
2971 min_offset
[mem_mode
] = i
== start
? 0 : -(i
>> 1);
2973 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2975 fprintf (dump_file
, "get_address_cost:\n");
2976 fprintf (dump_file
, " min offset %s %d\n",
2977 GET_MODE_NAME (mem_mode
),
2978 (int) min_offset
[mem_mode
]);
2979 fprintf (dump_file
, " max offset %s %d\n",
2980 GET_MODE_NAME (mem_mode
),
2981 (int) max_offset
[mem_mode
]);
2985 for (i
= 2; i
<= MAX_RATIO
; i
++)
2986 if (multiplier_allowed_in_address_p (i
, mem_mode
))
2992 /* Compute the cost of various addressing modes. */
2994 reg0
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 1);
2995 reg1
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 2);
2997 for (i
= 0; i
< 16; i
++)
3000 var_p
= (i
>> 1) & 1;
3001 off_p
= (i
>> 2) & 1;
3002 rat_p
= (i
>> 3) & 1;
3006 addr
= gen_rtx_fmt_ee (MULT
, Pmode
, addr
,
3007 gen_int_mode (rat
[mem_mode
], Pmode
));
3010 addr
= gen_rtx_fmt_ee (PLUS
, Pmode
, addr
, reg1
);
3014 base
= gen_rtx_SYMBOL_REF (Pmode
, ggc_strdup (""));
3015 /* ??? We can run into trouble with some backends by presenting
3016 it with symbols which havn't been properly passed through
3017 targetm.encode_section_info. By setting the local bit, we
3018 enhance the probability of things working. */
3019 SYMBOL_REF_FLAGS (base
) = SYMBOL_FLAG_LOCAL
;
3022 base
= gen_rtx_fmt_e (CONST
, Pmode
,
3023 gen_rtx_fmt_ee (PLUS
, Pmode
,
3025 gen_int_mode (off
[mem_mode
],
3029 base
= gen_int_mode (off
[mem_mode
], Pmode
);
3034 addr
= gen_rtx_fmt_ee (PLUS
, Pmode
, addr
, base
);
3037 /* To avoid splitting addressing modes, pretend that no cse will
3039 old_cse_not_expected
= cse_not_expected
;
3040 cse_not_expected
= true;
3041 addr
= memory_address (mem_mode
, addr
);
3042 cse_not_expected
= old_cse_not_expected
;
3046 acost
= seq_cost (seq
);
3047 acost
+= address_cost (addr
, mem_mode
);
3051 costs
[mem_mode
][sym_p
][var_p
][off_p
][rat_p
] = acost
;
3054 /* On some targets, it is quite expensive to load symbol to a register,
3055 which makes addresses that contain symbols look much more expensive.
3056 However, the symbol will have to be loaded in any case before the
3057 loop (and quite likely we have it in register already), so it does not
3058 make much sense to penalize them too heavily. So make some final
3059 tweaks for the SYMBOL_PRESENT modes:
3061 If VAR_PRESENT is false, and the mode obtained by changing symbol to
3062 var is cheaper, use this mode with small penalty.
3063 If VAR_PRESENT is true, try whether the mode with
3064 SYMBOL_PRESENT = false is cheaper even with cost of addition, and
3065 if this is the case, use it. */
3066 add_c
= add_cost (Pmode
);
3067 for (i
= 0; i
< 8; i
++)
3070 off_p
= (i
>> 1) & 1;
3071 rat_p
= (i
>> 2) & 1;
3073 acost
= costs
[mem_mode
][0][1][off_p
][rat_p
] + 1;
3077 if (acost
< costs
[mem_mode
][1][var_p
][off_p
][rat_p
])
3078 costs
[mem_mode
][1][var_p
][off_p
][rat_p
] = acost
;
3081 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3083 fprintf (dump_file
, "Address costs:\n");
3085 for (i
= 0; i
< 16; i
++)
3088 var_p
= (i
>> 1) & 1;
3089 off_p
= (i
>> 2) & 1;
3090 rat_p
= (i
>> 3) & 1;
3092 fprintf (dump_file
, " ");
3094 fprintf (dump_file
, "sym + ");
3096 fprintf (dump_file
, "var + ");
3098 fprintf (dump_file
, "cst + ");
3100 fprintf (dump_file
, "rat * ");
3102 acost
= costs
[mem_mode
][sym_p
][var_p
][off_p
][rat_p
];
3103 fprintf (dump_file
, "index costs %d\n", acost
);
3105 fprintf (dump_file
, "\n");
3109 bits
= GET_MODE_BITSIZE (Pmode
);
3110 mask
= ~(~(unsigned HOST_WIDE_INT
) 0 << (bits
- 1) << 1);
3112 if ((offset
>> (bits
- 1) & 1))
3117 offset_p
= (s_offset
!= 0
3118 && min_offset
[mem_mode
] <= s_offset
3119 && s_offset
<= max_offset
[mem_mode
]);
3120 ratio_p
= (ratio
!= 1
3121 && multiplier_allowed_in_address_p (ratio
, mem_mode
));
3123 if (ratio
!= 1 && !ratio_p
)
3124 cost
+= multiply_by_cost (ratio
, Pmode
);
3126 if (s_offset
&& !offset_p
&& !symbol_present
)
3127 cost
+= add_cost (Pmode
);
3129 acost
= costs
[mem_mode
][symbol_present
][var_present
][offset_p
][ratio_p
];
3130 complexity
= (symbol_present
!= 0) + (var_present
!= 0) + offset_p
+ ratio_p
;
3131 return new_cost (cost
+ acost
, complexity
);
3134 /* Estimates cost of forcing expression EXPR into a variable. */
3137 force_expr_to_var_cost (tree expr
)
3139 static bool costs_initialized
= false;
3140 static unsigned integer_cost
;
3141 static unsigned symbol_cost
;
3142 static unsigned address_cost
;
3144 comp_cost cost0
, cost1
, cost
;
3145 enum machine_mode mode
;
3147 if (!costs_initialized
)
3149 tree type
= build_pointer_type (integer_type_node
);
3153 var
= create_tmp_var_raw (integer_type_node
, "test_var");
3154 TREE_STATIC (var
) = 1;
3155 x
= produce_memory_decl_rtl (var
, NULL
);
3156 SET_DECL_RTL (var
, x
);
3158 integer_cost
= computation_cost (build_int_cst (integer_type_node
,
3161 addr
= build1 (ADDR_EXPR
, type
, var
);
3162 symbol_cost
= computation_cost (addr
) + 1;
3165 = computation_cost (build2 (POINTER_PLUS_EXPR
, type
,
3167 build_int_cst (sizetype
, 2000))) + 1;
3168 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3170 fprintf (dump_file
, "force_expr_to_var_cost:\n");
3171 fprintf (dump_file
, " integer %d\n", (int) integer_cost
);
3172 fprintf (dump_file
, " symbol %d\n", (int) symbol_cost
);
3173 fprintf (dump_file
, " address %d\n", (int) address_cost
);
3174 fprintf (dump_file
, " other %d\n", (int) target_spill_cost
);
3175 fprintf (dump_file
, "\n");
3178 costs_initialized
= true;
3183 if (SSA_VAR_P (expr
))
3186 if (TREE_INVARIANT (expr
))
3188 if (TREE_CODE (expr
) == INTEGER_CST
)
3189 return new_cost (integer_cost
, 0);
3191 if (TREE_CODE (expr
) == ADDR_EXPR
)
3193 tree obj
= TREE_OPERAND (expr
, 0);
3195 if (TREE_CODE (obj
) == VAR_DECL
3196 || TREE_CODE (obj
) == PARM_DECL
3197 || TREE_CODE (obj
) == RESULT_DECL
)
3198 return new_cost (symbol_cost
, 0);
3201 return new_cost (address_cost
, 0);
3204 switch (TREE_CODE (expr
))
3206 case POINTER_PLUS_EXPR
:
3210 op0
= TREE_OPERAND (expr
, 0);
3211 op1
= TREE_OPERAND (expr
, 1);
3215 if (is_gimple_val (op0
))
3218 cost0
= force_expr_to_var_cost (op0
);
3220 if (is_gimple_val (op1
))
3223 cost1
= force_expr_to_var_cost (op1
);
3228 /* Just an arbitrary value, FIXME. */
3229 return new_cost (target_spill_cost
, 0);
3232 mode
= TYPE_MODE (TREE_TYPE (expr
));
3233 switch (TREE_CODE (expr
))
3235 case POINTER_PLUS_EXPR
:
3238 cost
= new_cost (add_cost (mode
), 0);
3242 if (cst_and_fits_in_hwi (op0
))
3243 cost
= new_cost (multiply_by_cost (int_cst_value (op0
), mode
), 0);
3244 else if (cst_and_fits_in_hwi (op1
))
3245 cost
= new_cost (multiply_by_cost (int_cst_value (op1
), mode
), 0);
3247 return new_cost (target_spill_cost
, 0);
3254 cost
= add_costs (cost
, cost0
);
3255 cost
= add_costs (cost
, cost1
);
3257 /* Bound the cost by target_spill_cost. The parts of complicated
3258 computations often are either loop invariant or at least can
3259 be shared between several iv uses, so letting this grow without
3260 limits would not give reasonable results. */
3261 if (cost
.cost
> target_spill_cost
)
3262 cost
.cost
= target_spill_cost
;
3267 /* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
3268 invariants the computation depends on. */
3271 force_var_cost (struct ivopts_data
*data
,
3272 tree expr
, bitmap
*depends_on
)
3276 fd_ivopts_data
= data
;
3277 walk_tree (&expr
, find_depends
, depends_on
, NULL
);
3280 return force_expr_to_var_cost (expr
);
3283 /* Estimates cost of expressing address ADDR as var + symbol + offset. The
3284 value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
3285 to false if the corresponding part is missing. DEPENDS_ON is a set of the
3286 invariants the computation depends on. */
3289 split_address_cost (struct ivopts_data
*data
,
3290 tree addr
, bool *symbol_present
, bool *var_present
,
3291 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3294 HOST_WIDE_INT bitsize
;
3295 HOST_WIDE_INT bitpos
;
3297 enum machine_mode mode
;
3298 int unsignedp
, volatilep
;
3300 core
= get_inner_reference (addr
, &bitsize
, &bitpos
, &toffset
, &mode
,
3301 &unsignedp
, &volatilep
, false);
3304 || bitpos
% BITS_PER_UNIT
!= 0
3305 || TREE_CODE (core
) != VAR_DECL
)
3307 *symbol_present
= false;
3308 *var_present
= true;
3309 fd_ivopts_data
= data
;
3310 walk_tree (&addr
, find_depends
, depends_on
, NULL
);
3311 return new_cost (target_spill_cost
, 0);
3314 *offset
+= bitpos
/ BITS_PER_UNIT
;
3315 if (TREE_STATIC (core
)
3316 || DECL_EXTERNAL (core
))
3318 *symbol_present
= true;
3319 *var_present
= false;
3323 *symbol_present
= false;
3324 *var_present
= true;
3328 /* Estimates cost of expressing difference of addresses E1 - E2 as
3329 var + symbol + offset. The value of offset is added to OFFSET,
3330 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3331 part is missing. DEPENDS_ON is a set of the invariants the computation
3335 ptr_difference_cost (struct ivopts_data
*data
,
3336 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
3337 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3339 HOST_WIDE_INT diff
= 0;
3342 gcc_assert (TREE_CODE (e1
) == ADDR_EXPR
);
3344 if (ptr_difference_const (e1
, e2
, &diff
))
3347 *symbol_present
= false;
3348 *var_present
= false;
3352 if (integer_zerop (e2
))
3353 return split_address_cost (data
, TREE_OPERAND (e1
, 0),
3354 symbol_present
, var_present
, offset
, depends_on
);
3356 *symbol_present
= false;
3357 *var_present
= true;
3359 cost
= force_var_cost (data
, e1
, depends_on
);
3360 cost
= add_costs (cost
, force_var_cost (data
, e2
, depends_on
));
3361 cost
.cost
+= add_cost (Pmode
);
3366 /* Estimates cost of expressing difference E1 - E2 as
3367 var + symbol + offset. The value of offset is added to OFFSET,
3368 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3369 part is missing. DEPENDS_ON is a set of the invariants the computation
3373 difference_cost (struct ivopts_data
*data
,
3374 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
3375 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3378 enum machine_mode mode
= TYPE_MODE (TREE_TYPE (e1
));
3379 unsigned HOST_WIDE_INT off1
, off2
;
3381 e1
= strip_offset (e1
, &off1
);
3382 e2
= strip_offset (e2
, &off2
);
3383 *offset
+= off1
- off2
;
3388 if (TREE_CODE (e1
) == ADDR_EXPR
)
3389 return ptr_difference_cost (data
, e1
, e2
, symbol_present
, var_present
, offset
,
3391 *symbol_present
= false;
3393 if (operand_equal_p (e1
, e2
, 0))
3395 *var_present
= false;
3398 *var_present
= true;
3399 if (integer_zerop (e2
))
3400 return force_var_cost (data
, e1
, depends_on
);
3402 if (integer_zerop (e1
))
3404 cost
= force_var_cost (data
, e2
, depends_on
);
3405 cost
.cost
+= multiply_by_cost (-1, mode
);
3410 cost
= force_var_cost (data
, e1
, depends_on
);
3411 cost
= add_costs (cost
, force_var_cost (data
, e2
, depends_on
));
3412 cost
.cost
+= add_cost (mode
);
3417 /* Determines the cost of the computation by that USE is expressed
3418 from induction variable CAND. If ADDRESS_P is true, we just need
3419 to create an address from it, otherwise we want to get it into
3420 register. A set of invariants we depend on is stored in
3421 DEPENDS_ON. AT is the statement at that the value is computed. */
3424 get_computation_cost_at (struct ivopts_data
*data
,
3425 struct iv_use
*use
, struct iv_cand
*cand
,
3426 bool address_p
, bitmap
*depends_on
, tree at
)
3428 tree ubase
= use
->iv
->base
, ustep
= use
->iv
->step
;
3430 tree utype
= TREE_TYPE (ubase
), ctype
;
3431 unsigned HOST_WIDE_INT cstepi
, offset
= 0;
3432 HOST_WIDE_INT ratio
, aratio
;
3433 bool var_present
, symbol_present
;
3440 /* Only consider real candidates. */
3442 return infinite_cost
;
3444 cbase
= cand
->iv
->base
;
3445 cstep
= cand
->iv
->step
;
3446 ctype
= TREE_TYPE (cbase
);
3448 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
3450 /* We do not have a precision to express the values of use. */
3451 return infinite_cost
;
3456 /* Do not try to express address of an object with computation based
3457 on address of a different object. This may cause problems in rtl
3458 level alias analysis (that does not expect this to be happening,
3459 as this is illegal in C), and would be unlikely to be useful
3461 if (use
->iv
->base_object
3462 && cand
->iv
->base_object
3463 && !operand_equal_p (use
->iv
->base_object
, cand
->iv
->base_object
, 0))
3464 return infinite_cost
;
3467 if (TYPE_PRECISION (utype
) != TYPE_PRECISION (ctype
))
3469 /* TODO -- add direct handling of this case. */
3473 /* CSTEPI is removed from the offset in case statement is after the
3474 increment. If the step is not constant, we use zero instead.
3475 This is a bit imprecise (there is the extra addition), but
3476 redundancy elimination is likely to transform the code so that
3477 it uses value of the variable before increment anyway,
3478 so it is not that much unrealistic. */
3479 if (cst_and_fits_in_hwi (cstep
))
3480 cstepi
= int_cst_value (cstep
);
3484 if (!constant_multiple_of (ustep
, cstep
, &rat
))
3485 return infinite_cost
;
3487 if (double_int_fits_in_shwi_p (rat
))
3488 ratio
= double_int_to_shwi (rat
);
3490 return infinite_cost
;
3492 /* use = ubase + ratio * (var - cbase). If either cbase is a constant
3493 or ratio == 1, it is better to handle this like
3495 ubase - ratio * cbase + ratio * var
3497 (also holds in the case ratio == -1, TODO. */
3499 if (cst_and_fits_in_hwi (cbase
))
3501 offset
= - ratio
* int_cst_value (cbase
);
3502 cost
= difference_cost (data
,
3503 ubase
, build_int_cst (utype
, 0),
3504 &symbol_present
, &var_present
, &offset
,
3507 else if (ratio
== 1)
3509 cost
= difference_cost (data
,
3511 &symbol_present
, &var_present
, &offset
,
3516 cost
= force_var_cost (data
, cbase
, depends_on
);
3517 cost
.cost
+= add_cost (TYPE_MODE (ctype
));
3518 cost
= add_costs (cost
,
3519 difference_cost (data
,
3520 ubase
, build_int_cst (utype
, 0),
3521 &symbol_present
, &var_present
,
3522 &offset
, depends_on
));
3525 /* If we are after the increment, the value of the candidate is higher by
3527 if (stmt_after_increment (data
->current_loop
, cand
, at
))
3528 offset
-= ratio
* cstepi
;
3530 /* Now the computation is in shape symbol + var1 + const + ratio * var2.
3531 (symbol/var/const parts may be omitted). If we are looking for an address,
3532 find the cost of addressing this. */
3534 return add_costs (cost
, get_address_cost (symbol_present
, var_present
,
3536 TYPE_MODE (TREE_TYPE (*use
->op_p
))));
3538 /* Otherwise estimate the costs for computing the expression. */
3539 aratio
= ratio
> 0 ? ratio
: -ratio
;
3540 if (!symbol_present
&& !var_present
&& !offset
)
3543 cost
.cost
+= multiply_by_cost (ratio
, TYPE_MODE (ctype
));
3549 cost
.cost
+= multiply_by_cost (aratio
, TYPE_MODE (ctype
));
3553 /* Symbol + offset should be compile-time computable. */
3554 && (symbol_present
|| offset
))
3557 /* Having offset does not affect runtime cost in case it is added to
3558 symbol, but it increases complexity. */
3562 cost
.cost
+= n_sums
* add_cost (TYPE_MODE (ctype
));
3567 /* Just get the expression, expand it and measure the cost. */
3568 tree comp
= get_computation_at (data
->current_loop
, use
, cand
, at
);
3571 return infinite_cost
;
3574 comp
= build1 (INDIRECT_REF
, TREE_TYPE (TREE_TYPE (comp
)), comp
);
3576 return new_cost (computation_cost (comp
), 0);
3580 /* Determines the cost of the computation by that USE is expressed
3581 from induction variable CAND. If ADDRESS_P is true, we just need
3582 to create an address from it, otherwise we want to get it into
3583 register. A set of invariants we depend on is stored in
3587 get_computation_cost (struct ivopts_data
*data
,
3588 struct iv_use
*use
, struct iv_cand
*cand
,
3589 bool address_p
, bitmap
*depends_on
)
3591 return get_computation_cost_at (data
,
3592 use
, cand
, address_p
, depends_on
, use
->stmt
);
3595 /* Determines cost of basing replacement of USE on CAND in a generic
3599 determine_use_iv_cost_generic (struct ivopts_data
*data
,
3600 struct iv_use
*use
, struct iv_cand
*cand
)
3605 /* The simple case first -- if we need to express value of the preserved
3606 original biv, the cost is 0. This also prevents us from counting the
3607 cost of increment twice -- once at this use and once in the cost of
3609 if (cand
->pos
== IP_ORIGINAL
3610 && cand
->incremented_at
== use
->stmt
)
3612 set_use_iv_cost (data
, use
, cand
, zero_cost
, NULL
, NULL_TREE
);
3616 cost
= get_computation_cost (data
, use
, cand
, false, &depends_on
);
3617 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
);
3619 return !infinite_cost_p (cost
);
3622 /* Determines cost of basing replacement of USE on CAND in an address. */
3625 determine_use_iv_cost_address (struct ivopts_data
*data
,
3626 struct iv_use
*use
, struct iv_cand
*cand
)
3629 comp_cost cost
= get_computation_cost (data
, use
, cand
, true, &depends_on
);
3631 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
);
3633 return !infinite_cost_p (cost
);
3636 /* Computes value of candidate CAND at position AT in iteration NITER, and
3637 stores it to VAL. */
3640 cand_value_at (struct loop
*loop
, struct iv_cand
*cand
, tree at
, tree niter
,
3643 aff_tree step
, delta
, nit
;
3644 struct iv
*iv
= cand
->iv
;
3645 tree type
= TREE_TYPE (iv
->base
);
3647 tree_to_aff_combination (iv
->step
, type
, &step
);
3648 tree_to_aff_combination (niter
, TREE_TYPE (niter
), &nit
);
3649 aff_combination_convert (&nit
, type
);
3650 aff_combination_mult (&nit
, &step
, &delta
);
3651 if (stmt_after_increment (loop
, cand
, at
))
3652 aff_combination_add (&delta
, &step
);
3654 tree_to_aff_combination (iv
->base
, type
, val
);
3655 aff_combination_add (val
, &delta
);
3658 /* Returns period of induction variable iv. */
3661 iv_period (struct iv
*iv
)
3663 tree step
= iv
->step
, period
, type
;
3666 gcc_assert (step
&& TREE_CODE (step
) == INTEGER_CST
);
3668 /* Period of the iv is gcd (step, type range). Since type range is power
3669 of two, it suffices to determine the maximum power of two that divides
3671 pow2div
= num_ending_zeros (step
);
3672 type
= unsigned_type_for (TREE_TYPE (step
));
3674 period
= build_low_bits_mask (type
,
3675 (TYPE_PRECISION (type
)
3676 - tree_low_cst (pow2div
, 1)));
3681 /* Returns the comparison operator used when eliminating the iv USE. */
3683 static enum tree_code
3684 iv_elimination_compare (struct ivopts_data
*data
, struct iv_use
*use
)
3686 struct loop
*loop
= data
->current_loop
;
3690 ex_bb
= bb_for_stmt (use
->stmt
);
3691 exit
= EDGE_SUCC (ex_bb
, 0);
3692 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
3693 exit
= EDGE_SUCC (ex_bb
, 1);
3695 return (exit
->flags
& EDGE_TRUE_VALUE
? EQ_EXPR
: NE_EXPR
);
3698 /* Check whether it is possible to express the condition in USE by comparison
3699 of candidate CAND. If so, store the value compared with to BOUND. */
3702 may_eliminate_iv (struct ivopts_data
*data
,
3703 struct iv_use
*use
, struct iv_cand
*cand
, tree
*bound
)
3708 struct loop
*loop
= data
->current_loop
;
3710 double_int period_value
, max_niter
;
3712 if (TREE_CODE (cand
->iv
->step
) != INTEGER_CST
)
3715 /* For now works only for exits that dominate the loop latch. TODO -- extend
3716 for other conditions inside loop body. */
3717 ex_bb
= bb_for_stmt (use
->stmt
);
3718 if (use
->stmt
!= last_stmt (ex_bb
)
3719 || TREE_CODE (use
->stmt
) != COND_EXPR
)
3721 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, ex_bb
))
3724 exit
= EDGE_SUCC (ex_bb
, 0);
3725 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
3726 exit
= EDGE_SUCC (ex_bb
, 1);
3727 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
3730 nit
= niter_for_exit (data
, exit
);
3734 /* Determine whether we may use the variable to test whether niter iterations
3735 elapsed. This is the case iff the period of the induction variable is
3736 greater than the number of iterations. */
3737 period
= iv_period (cand
->iv
);
3741 /* Compare the period with the estimate on the number of iterations of the
3743 if (!estimated_loop_iterations (loop
, true, &max_niter
))
3745 period_value
= tree_to_double_int (period
);
3746 if (double_int_ucmp (period_value
, max_niter
) <= 0)
3749 cand_value_at (loop
, cand
, use
->stmt
, nit
, &bnd
);
3750 *bound
= aff_combination_to_tree (&bnd
);
3754 /* Determines cost of basing replacement of USE on CAND in a condition. */
3757 determine_use_iv_cost_condition (struct ivopts_data
*data
,
3758 struct iv_use
*use
, struct iv_cand
*cand
)
3760 tree bound
= NULL_TREE
;
3762 bitmap depends_on_elim
= NULL
, depends_on_express
= NULL
, depends_on
;
3763 comp_cost elim_cost
, express_cost
, cost
;
3766 /* Only consider real candidates. */
3769 set_use_iv_cost (data
, use
, cand
, infinite_cost
, NULL
, NULL_TREE
);
3773 /* Try iv elimination. */
3774 if (may_eliminate_iv (data
, use
, cand
, &bound
))
3776 elim_cost
= force_var_cost (data
, bound
, &depends_on_elim
);
3777 /* The bound is a loop invariant, so it will be only computed
3779 elim_cost
.cost
/= AVG_LOOP_NITER (data
->current_loop
);
3782 elim_cost
= infinite_cost
;
3784 /* Try expressing the original giv. If it is compared with an invariant,
3785 note that we cannot get rid of it. */
3786 ok
= extract_cond_operands (data
, use
->op_p
, NULL
, NULL
, NULL
, &cmp_iv
);
3789 express_cost
= get_computation_cost (data
, use
, cand
, false,
3790 &depends_on_express
);
3791 fd_ivopts_data
= data
;
3792 walk_tree (&cmp_iv
->base
, find_depends
, &depends_on_express
, NULL
);
3794 /* Choose the better approach. */
3795 if (compare_costs (elim_cost
, express_cost
) < 0)
3798 depends_on
= depends_on_elim
;
3799 depends_on_elim
= NULL
;
3803 cost
= express_cost
;
3804 depends_on
= depends_on_express
;
3805 depends_on_express
= NULL
;
3809 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, bound
);
3811 if (depends_on_elim
)
3812 BITMAP_FREE (depends_on_elim
);
3813 if (depends_on_express
)
3814 BITMAP_FREE (depends_on_express
);
3816 return !infinite_cost_p (cost
);
3819 /* Determines cost of basing replacement of USE on CAND. Returns false
3820 if USE cannot be based on CAND. */
3823 determine_use_iv_cost (struct ivopts_data
*data
,
3824 struct iv_use
*use
, struct iv_cand
*cand
)
3828 case USE_NONLINEAR_EXPR
:
3829 return determine_use_iv_cost_generic (data
, use
, cand
);
3832 return determine_use_iv_cost_address (data
, use
, cand
);
3835 return determine_use_iv_cost_condition (data
, use
, cand
);
3842 /* Determines costs of basing the use of the iv on an iv candidate. */
3845 determine_use_iv_costs (struct ivopts_data
*data
)
3849 struct iv_cand
*cand
;
3850 bitmap to_clear
= BITMAP_ALLOC (NULL
);
3852 alloc_use_cost_map (data
);
3854 for (i
= 0; i
< n_iv_uses (data
); i
++)
3856 use
= iv_use (data
, i
);
3858 if (data
->consider_all_candidates
)
3860 for (j
= 0; j
< n_iv_cands (data
); j
++)
3862 cand
= iv_cand (data
, j
);
3863 determine_use_iv_cost (data
, use
, cand
);
3870 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, j
, bi
)
3872 cand
= iv_cand (data
, j
);
3873 if (!determine_use_iv_cost (data
, use
, cand
))
3874 bitmap_set_bit (to_clear
, j
);
3877 /* Remove the candidates for that the cost is infinite from
3878 the list of related candidates. */
3879 bitmap_and_compl_into (use
->related_cands
, to_clear
);
3880 bitmap_clear (to_clear
);
3884 BITMAP_FREE (to_clear
);
3886 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3888 fprintf (dump_file
, "Use-candidate costs:\n");
3890 for (i
= 0; i
< n_iv_uses (data
); i
++)
3892 use
= iv_use (data
, i
);
3894 fprintf (dump_file
, "Use %d:\n", i
);
3895 fprintf (dump_file
, " cand\tcost\tcompl.\tdepends on\n");
3896 for (j
= 0; j
< use
->n_map_members
; j
++)
3898 if (!use
->cost_map
[j
].cand
3899 || infinite_cost_p (use
->cost_map
[j
].cost
))
3902 fprintf (dump_file
, " %d\t%d\t%d\t",
3903 use
->cost_map
[j
].cand
->id
,
3904 use
->cost_map
[j
].cost
.cost
,
3905 use
->cost_map
[j
].cost
.complexity
);
3906 if (use
->cost_map
[j
].depends_on
)
3907 bitmap_print (dump_file
,
3908 use
->cost_map
[j
].depends_on
, "","");
3909 fprintf (dump_file
, "\n");
3912 fprintf (dump_file
, "\n");
3914 fprintf (dump_file
, "\n");
3918 /* Determines cost of the candidate CAND. */
3921 determine_iv_cost (struct ivopts_data
*data
, struct iv_cand
*cand
)
3923 comp_cost cost_base
;
3924 unsigned cost
, cost_step
;
3933 /* There are two costs associated with the candidate -- its increment
3934 and its initialization. The second is almost negligible for any loop
3935 that rolls enough, so we take it just very little into account. */
3937 base
= cand
->iv
->base
;
3938 cost_base
= force_var_cost (data
, base
, NULL
);
3939 cost_step
= add_cost (TYPE_MODE (TREE_TYPE (base
)));
3941 cost
= cost_step
+ cost_base
.cost
/ AVG_LOOP_NITER (current_loop
);
3943 /* Prefer the original ivs unless we may gain something by replacing it.
3944 The reason is to makee debugging simpler; so this is not relevant for
3945 artificial ivs created by other optimization passes. */
3946 if (cand
->pos
!= IP_ORIGINAL
3947 || DECL_ARTIFICIAL (SSA_NAME_VAR (cand
->var_before
)))
3950 /* Prefer not to insert statements into latch unless there are some
3951 already (so that we do not create unnecessary jumps). */
3952 if (cand
->pos
== IP_END
3953 && empty_block_p (ip_end_pos (data
->current_loop
)))
3959 /* Determines costs of computation of the candidates. */
3962 determine_iv_costs (struct ivopts_data
*data
)
3966 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3968 fprintf (dump_file
, "Candidate costs:\n");
3969 fprintf (dump_file
, " cand\tcost\n");
3972 for (i
= 0; i
< n_iv_cands (data
); i
++)
3974 struct iv_cand
*cand
= iv_cand (data
, i
);
3976 determine_iv_cost (data
, cand
);
3978 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3979 fprintf (dump_file
, " %d\t%d\n", i
, cand
->cost
);
3982 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3983 fprintf (dump_file
, "\n");
3986 /* Calculates cost for having SIZE induction variables. */
3989 ivopts_global_cost_for_size (struct ivopts_data
*data
, unsigned size
)
3991 /* We add size to the cost, so that we prefer eliminating ivs
3993 return size
+ estimate_reg_pressure_cost (size
, data
->regs_used
);
3996 /* For each size of the induction variable set determine the penalty. */
3999 determine_set_costs (struct ivopts_data
*data
)
4003 struct loop
*loop
= data
->current_loop
;
4006 /* We use the following model (definitely improvable, especially the
4007 cost function -- TODO):
4009 We estimate the number of registers available (using MD data), name it A.
4011 We estimate the number of registers used by the loop, name it U. This
4012 number is obtained as the number of loop phi nodes (not counting virtual
4013 registers and bivs) + the number of variables from outside of the loop.
4015 We set a reserve R (free regs that are used for temporary computations,
4016 etc.). For now the reserve is a constant 3.
4018 Let I be the number of induction variables.
4020 -- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
4021 make a lot of ivs without a reason).
4022 -- if A - R < U + I <= A, the cost is I * PRES_COST
4023 -- if U + I > A, the cost is I * PRES_COST and
4024 number of uses * SPILL_COST * (U + I - A) / (U + I) is added. */
4026 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4028 fprintf (dump_file
, "Global costs:\n");
4029 fprintf (dump_file
, " target_avail_regs %d\n", target_avail_regs
);
4030 fprintf (dump_file
, " target_reg_cost %d\n", target_reg_cost
);
4031 fprintf (dump_file
, " target_spill_cost %d\n", target_spill_cost
);
4035 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
4037 op
= PHI_RESULT (phi
);
4039 if (!is_gimple_reg (op
))
4042 if (get_iv (data
, op
))
4048 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
4050 struct version_info
*info
= ver_info (data
, j
);
4052 if (info
->inv_id
&& info
->has_nonlin_use
)
4056 data
->regs_used
= n
;
4057 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4058 fprintf (dump_file
, " regs_used %d\n", n
);
4060 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4062 fprintf (dump_file
, " cost for size:\n");
4063 fprintf (dump_file
, " ivs\tcost\n");
4064 for (j
= 0; j
<= 2 * target_avail_regs
; j
++)
4065 fprintf (dump_file
, " %d\t%d\n", j
,
4066 ivopts_global_cost_for_size (data
, j
));
4067 fprintf (dump_file
, "\n");
4071 /* Returns true if A is a cheaper cost pair than B. */
4074 cheaper_cost_pair (struct cost_pair
*a
, struct cost_pair
*b
)
4084 cmp
= compare_costs (a
->cost
, b
->cost
);
4091 /* In case the costs are the same, prefer the cheaper candidate. */
4092 if (a
->cand
->cost
< b
->cand
->cost
)
4098 /* Computes the cost field of IVS structure. */
4101 iv_ca_recount_cost (struct ivopts_data
*data
, struct iv_ca
*ivs
)
4103 comp_cost cost
= ivs
->cand_use_cost
;
4104 cost
.cost
+= ivs
->cand_cost
;
4105 cost
.cost
+= ivopts_global_cost_for_size (data
, ivs
->n_regs
);
4110 /* Remove invariants in set INVS to set IVS. */
4113 iv_ca_set_remove_invariants (struct iv_ca
*ivs
, bitmap invs
)
4121 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
4123 ivs
->n_invariant_uses
[iid
]--;
4124 if (ivs
->n_invariant_uses
[iid
] == 0)
4129 /* Set USE not to be expressed by any candidate in IVS. */
4132 iv_ca_set_no_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4135 unsigned uid
= use
->id
, cid
;
4136 struct cost_pair
*cp
;
4138 cp
= ivs
->cand_for_use
[uid
];
4144 ivs
->cand_for_use
[uid
] = NULL
;
4145 ivs
->n_cand_uses
[cid
]--;
4147 if (ivs
->n_cand_uses
[cid
] == 0)
4149 bitmap_clear_bit (ivs
->cands
, cid
);
4150 /* Do not count the pseudocandidates. */
4154 ivs
->cand_cost
-= cp
->cand
->cost
;
4156 iv_ca_set_remove_invariants (ivs
, cp
->cand
->depends_on
);
4159 ivs
->cand_use_cost
= sub_costs (ivs
->cand_use_cost
, cp
->cost
);
4161 iv_ca_set_remove_invariants (ivs
, cp
->depends_on
);
4162 iv_ca_recount_cost (data
, ivs
);
4165 /* Add invariants in set INVS to set IVS. */
4168 iv_ca_set_add_invariants (struct iv_ca
*ivs
, bitmap invs
)
4176 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
4178 ivs
->n_invariant_uses
[iid
]++;
4179 if (ivs
->n_invariant_uses
[iid
] == 1)
4184 /* Set cost pair for USE in set IVS to CP. */
4187 iv_ca_set_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4188 struct iv_use
*use
, struct cost_pair
*cp
)
4190 unsigned uid
= use
->id
, cid
;
4192 if (ivs
->cand_for_use
[uid
] == cp
)
4195 if (ivs
->cand_for_use
[uid
])
4196 iv_ca_set_no_cp (data
, ivs
, use
);
4203 ivs
->cand_for_use
[uid
] = cp
;
4204 ivs
->n_cand_uses
[cid
]++;
4205 if (ivs
->n_cand_uses
[cid
] == 1)
4207 bitmap_set_bit (ivs
->cands
, cid
);
4208 /* Do not count the pseudocandidates. */
4212 ivs
->cand_cost
+= cp
->cand
->cost
;
4214 iv_ca_set_add_invariants (ivs
, cp
->cand
->depends_on
);
4217 ivs
->cand_use_cost
= add_costs (ivs
->cand_use_cost
, cp
->cost
);
4218 iv_ca_set_add_invariants (ivs
, cp
->depends_on
);
4219 iv_ca_recount_cost (data
, ivs
);
4223 /* Extend set IVS by expressing USE by some of the candidates in it
4227 iv_ca_add_use (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4230 struct cost_pair
*best_cp
= NULL
, *cp
;
4234 gcc_assert (ivs
->upto
>= use
->id
);
4236 if (ivs
->upto
== use
->id
)
4242 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
4244 cp
= get_use_iv_cost (data
, use
, iv_cand (data
, i
));
4246 if (cheaper_cost_pair (cp
, best_cp
))
4250 iv_ca_set_cp (data
, ivs
, use
, best_cp
);
4253 /* Get cost for assignment IVS. */
4256 iv_ca_cost (struct iv_ca
*ivs
)
4258 return (ivs
->bad_uses
? infinite_cost
: ivs
->cost
);
4261 /* Returns true if all dependences of CP are among invariants in IVS. */
4264 iv_ca_has_deps (struct iv_ca
*ivs
, struct cost_pair
*cp
)
4269 if (!cp
->depends_on
)
4272 EXECUTE_IF_SET_IN_BITMAP (cp
->depends_on
, 0, i
, bi
)
4274 if (ivs
->n_invariant_uses
[i
] == 0)
4281 /* Creates change of expressing USE by NEW_CP instead of OLD_CP and chains
4282 it before NEXT_CHANGE. */
4284 static struct iv_ca_delta
*
4285 iv_ca_delta_add (struct iv_use
*use
, struct cost_pair
*old_cp
,
4286 struct cost_pair
*new_cp
, struct iv_ca_delta
*next_change
)
4288 struct iv_ca_delta
*change
= XNEW (struct iv_ca_delta
);
4291 change
->old_cp
= old_cp
;
4292 change
->new_cp
= new_cp
;
4293 change
->next_change
= next_change
;
4298 /* Joins two lists of changes L1 and L2. Destructive -- old lists
4301 static struct iv_ca_delta
*
4302 iv_ca_delta_join (struct iv_ca_delta
*l1
, struct iv_ca_delta
*l2
)
4304 struct iv_ca_delta
*last
;
4312 for (last
= l1
; last
->next_change
; last
= last
->next_change
)
4314 last
->next_change
= l2
;
4319 /* Returns candidate by that USE is expressed in IVS. */
4321 static struct cost_pair
*
4322 iv_ca_cand_for_use (struct iv_ca
*ivs
, struct iv_use
*use
)
4324 return ivs
->cand_for_use
[use
->id
];
4327 /* Reverse the list of changes DELTA, forming the inverse to it. */
4329 static struct iv_ca_delta
*
4330 iv_ca_delta_reverse (struct iv_ca_delta
*delta
)
4332 struct iv_ca_delta
*act
, *next
, *prev
= NULL
;
4333 struct cost_pair
*tmp
;
4335 for (act
= delta
; act
; act
= next
)
4337 next
= act
->next_change
;
4338 act
->next_change
= prev
;
4342 act
->old_cp
= act
->new_cp
;
4349 /* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
4350 reverted instead. */
4353 iv_ca_delta_commit (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4354 struct iv_ca_delta
*delta
, bool forward
)
4356 struct cost_pair
*from
, *to
;
4357 struct iv_ca_delta
*act
;
4360 delta
= iv_ca_delta_reverse (delta
);
4362 for (act
= delta
; act
; act
= act
->next_change
)
4366 gcc_assert (iv_ca_cand_for_use (ivs
, act
->use
) == from
);
4367 iv_ca_set_cp (data
, ivs
, act
->use
, to
);
4371 iv_ca_delta_reverse (delta
);
4374 /* Returns true if CAND is used in IVS. */
4377 iv_ca_cand_used_p (struct iv_ca
*ivs
, struct iv_cand
*cand
)
4379 return ivs
->n_cand_uses
[cand
->id
] > 0;
4382 /* Returns number of induction variable candidates in the set IVS. */
4385 iv_ca_n_cands (struct iv_ca
*ivs
)
4387 return ivs
->n_cands
;
4390 /* Free the list of changes DELTA. */
4393 iv_ca_delta_free (struct iv_ca_delta
**delta
)
4395 struct iv_ca_delta
*act
, *next
;
4397 for (act
= *delta
; act
; act
= next
)
4399 next
= act
->next_change
;
4406 /* Allocates new iv candidates assignment. */
4408 static struct iv_ca
*
4409 iv_ca_new (struct ivopts_data
*data
)
4411 struct iv_ca
*nw
= XNEW (struct iv_ca
);
4415 nw
->cand_for_use
= XCNEWVEC (struct cost_pair
*, n_iv_uses (data
));
4416 nw
->n_cand_uses
= XCNEWVEC (unsigned, n_iv_cands (data
));
4417 nw
->cands
= BITMAP_ALLOC (NULL
);
4420 nw
->cand_use_cost
= zero_cost
;
4422 nw
->n_invariant_uses
= XCNEWVEC (unsigned, data
->max_inv_id
+ 1);
4423 nw
->cost
= zero_cost
;
4428 /* Free memory occupied by the set IVS. */
4431 iv_ca_free (struct iv_ca
**ivs
)
4433 free ((*ivs
)->cand_for_use
);
4434 free ((*ivs
)->n_cand_uses
);
4435 BITMAP_FREE ((*ivs
)->cands
);
4436 free ((*ivs
)->n_invariant_uses
);
4441 /* Dumps IVS to FILE. */
4444 iv_ca_dump (struct ivopts_data
*data
, FILE *file
, struct iv_ca
*ivs
)
4446 const char *pref
= " invariants ";
4448 comp_cost cost
= iv_ca_cost (ivs
);
4450 fprintf (file
, " cost %d (complexity %d)\n", cost
.cost
, cost
.complexity
);
4451 bitmap_print (file
, ivs
->cands
, " candidates ","\n");
4453 for (i
= 1; i
<= data
->max_inv_id
; i
++)
4454 if (ivs
->n_invariant_uses
[i
])
4456 fprintf (file
, "%s%d", pref
, i
);
4459 fprintf (file
, "\n");
4462 /* Try changing candidate in IVS to CAND for each use. Return cost of the
4463 new set, and store differences in DELTA. Number of induction variables
4464 in the new set is stored to N_IVS. */
4467 iv_ca_extend (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4468 struct iv_cand
*cand
, struct iv_ca_delta
**delta
,
4474 struct cost_pair
*old_cp
, *new_cp
;
4477 for (i
= 0; i
< ivs
->upto
; i
++)
4479 use
= iv_use (data
, i
);
4480 old_cp
= iv_ca_cand_for_use (ivs
, use
);
4483 && old_cp
->cand
== cand
)
4486 new_cp
= get_use_iv_cost (data
, use
, cand
);
4490 if (!iv_ca_has_deps (ivs
, new_cp
))
4493 if (!cheaper_cost_pair (new_cp
, old_cp
))
4496 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
4499 iv_ca_delta_commit (data
, ivs
, *delta
, true);
4500 cost
= iv_ca_cost (ivs
);
4502 *n_ivs
= iv_ca_n_cands (ivs
);
4503 iv_ca_delta_commit (data
, ivs
, *delta
, false);
4508 /* Try narrowing set IVS by removing CAND. Return the cost of
4509 the new set and store the differences in DELTA. */
4512 iv_ca_narrow (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4513 struct iv_cand
*cand
, struct iv_ca_delta
**delta
)
4517 struct cost_pair
*old_cp
, *new_cp
, *cp
;
4519 struct iv_cand
*cnd
;
4523 for (i
= 0; i
< n_iv_uses (data
); i
++)
4525 use
= iv_use (data
, i
);
4527 old_cp
= iv_ca_cand_for_use (ivs
, use
);
4528 if (old_cp
->cand
!= cand
)
4533 if (data
->consider_all_candidates
)
4535 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, ci
, bi
)
4540 cnd
= iv_cand (data
, ci
);
4542 cp
= get_use_iv_cost (data
, use
, cnd
);
4545 if (!iv_ca_has_deps (ivs
, cp
))
4548 if (!cheaper_cost_pair (cp
, new_cp
))
4556 EXECUTE_IF_AND_IN_BITMAP (use
->related_cands
, ivs
->cands
, 0, ci
, bi
)
4561 cnd
= iv_cand (data
, ci
);
4563 cp
= get_use_iv_cost (data
, use
, cnd
);
4566 if (!iv_ca_has_deps (ivs
, cp
))
4569 if (!cheaper_cost_pair (cp
, new_cp
))
4578 iv_ca_delta_free (delta
);
4579 return infinite_cost
;
4582 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
4585 iv_ca_delta_commit (data
, ivs
, *delta
, true);
4586 cost
= iv_ca_cost (ivs
);
4587 iv_ca_delta_commit (data
, ivs
, *delta
, false);
4592 /* Try optimizing the set of candidates IVS by removing candidates different
4593 from to EXCEPT_CAND from it. Return cost of the new set, and store
4594 differences in DELTA. */
4597 iv_ca_prune (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4598 struct iv_cand
*except_cand
, struct iv_ca_delta
**delta
)
4601 struct iv_ca_delta
*act_delta
, *best_delta
;
4603 comp_cost best_cost
, acost
;
4604 struct iv_cand
*cand
;
4607 best_cost
= iv_ca_cost (ivs
);
4609 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
4611 cand
= iv_cand (data
, i
);
4613 if (cand
== except_cand
)
4616 acost
= iv_ca_narrow (data
, ivs
, cand
, &act_delta
);
4618 if (compare_costs (acost
, best_cost
) < 0)
4621 iv_ca_delta_free (&best_delta
);
4622 best_delta
= act_delta
;
4625 iv_ca_delta_free (&act_delta
);
4634 /* Recurse to possibly remove other unnecessary ivs. */
4635 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
4636 best_cost
= iv_ca_prune (data
, ivs
, except_cand
, delta
);
4637 iv_ca_delta_commit (data
, ivs
, best_delta
, false);
4638 *delta
= iv_ca_delta_join (best_delta
, *delta
);
4642 /* Tries to extend the sets IVS in the best possible way in order
4643 to express the USE. */
4646 try_add_cand_for (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4649 comp_cost best_cost
, act_cost
;
4652 struct iv_cand
*cand
;
4653 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
;
4654 struct cost_pair
*cp
;
4656 iv_ca_add_use (data
, ivs
, use
);
4657 best_cost
= iv_ca_cost (ivs
);
4659 cp
= iv_ca_cand_for_use (ivs
, use
);
4662 best_delta
= iv_ca_delta_add (use
, NULL
, cp
, NULL
);
4663 iv_ca_set_no_cp (data
, ivs
, use
);
4666 /* First try important candidates not based on any memory object. Only if
4667 this fails, try the specific ones. Rationale -- in loops with many
4668 variables the best choice often is to use just one generic biv. If we
4669 added here many ivs specific to the uses, the optimization algorithm later
4670 would be likely to get stuck in a local minimum, thus causing us to create
4671 too many ivs. The approach from few ivs to more seems more likely to be
4672 successful -- starting from few ivs, replacing an expensive use by a
4673 specific iv should always be a win. */
4674 EXECUTE_IF_SET_IN_BITMAP (data
->important_candidates
, 0, i
, bi
)
4676 cand
= iv_cand (data
, i
);
4678 if (cand
->iv
->base_object
!= NULL_TREE
)
4681 if (iv_ca_cand_used_p (ivs
, cand
))
4684 cp
= get_use_iv_cost (data
, use
, cand
);
4688 iv_ca_set_cp (data
, ivs
, use
, cp
);
4689 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
);
4690 iv_ca_set_no_cp (data
, ivs
, use
);
4691 act_delta
= iv_ca_delta_add (use
, NULL
, cp
, act_delta
);
4693 if (compare_costs (act_cost
, best_cost
) < 0)
4695 best_cost
= act_cost
;
4697 iv_ca_delta_free (&best_delta
);
4698 best_delta
= act_delta
;
4701 iv_ca_delta_free (&act_delta
);
4704 if (infinite_cost_p (best_cost
))
4706 for (i
= 0; i
< use
->n_map_members
; i
++)
4708 cp
= use
->cost_map
+ i
;
4713 /* Already tried this. */
4714 if (cand
->important
&& cand
->iv
->base_object
== NULL_TREE
)
4717 if (iv_ca_cand_used_p (ivs
, cand
))
4721 iv_ca_set_cp (data
, ivs
, use
, cp
);
4722 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
);
4723 iv_ca_set_no_cp (data
, ivs
, use
);
4724 act_delta
= iv_ca_delta_add (use
, iv_ca_cand_for_use (ivs
, use
),
4727 if (compare_costs (act_cost
, best_cost
) < 0)
4729 best_cost
= act_cost
;
4732 iv_ca_delta_free (&best_delta
);
4733 best_delta
= act_delta
;
4736 iv_ca_delta_free (&act_delta
);
4740 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
4741 iv_ca_delta_free (&best_delta
);
4743 return !infinite_cost_p (best_cost
);
4746 /* Finds an initial assignment of candidates to uses. */
4748 static struct iv_ca
*
4749 get_initial_solution (struct ivopts_data
*data
)
4751 struct iv_ca
*ivs
= iv_ca_new (data
);
4754 for (i
= 0; i
< n_iv_uses (data
); i
++)
4755 if (!try_add_cand_for (data
, ivs
, iv_use (data
, i
)))
4764 /* Tries to improve set of induction variables IVS. */
4767 try_improve_iv_set (struct ivopts_data
*data
, struct iv_ca
*ivs
)
4770 comp_cost acost
, best_cost
= iv_ca_cost (ivs
);
4771 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
, *tmp_delta
;
4772 struct iv_cand
*cand
;
4774 /* Try extending the set of induction variables by one. */
4775 for (i
= 0; i
< n_iv_cands (data
); i
++)
4777 cand
= iv_cand (data
, i
);
4779 if (iv_ca_cand_used_p (ivs
, cand
))
4782 acost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, &n_ivs
);
4786 /* If we successfully added the candidate and the set is small enough,
4787 try optimizing it by removing other candidates. */
4788 if (n_ivs
<= ALWAYS_PRUNE_CAND_SET_BOUND
)
4790 iv_ca_delta_commit (data
, ivs
, act_delta
, true);
4791 acost
= iv_ca_prune (data
, ivs
, cand
, &tmp_delta
);
4792 iv_ca_delta_commit (data
, ivs
, act_delta
, false);
4793 act_delta
= iv_ca_delta_join (act_delta
, tmp_delta
);
4796 if (compare_costs (acost
, best_cost
) < 0)
4799 iv_ca_delta_free (&best_delta
);
4800 best_delta
= act_delta
;
4803 iv_ca_delta_free (&act_delta
);
4808 /* Try removing the candidates from the set instead. */
4809 best_cost
= iv_ca_prune (data
, ivs
, NULL
, &best_delta
);
4811 /* Nothing more we can do. */
4816 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
4817 gcc_assert (compare_costs (best_cost
, iv_ca_cost (ivs
)) == 0);
4818 iv_ca_delta_free (&best_delta
);
4822 /* Attempts to find the optimal set of induction variables. We do simple
4823 greedy heuristic -- we try to replace at most one candidate in the selected
4824 solution and remove the unused ivs while this improves the cost. */
4826 static struct iv_ca
*
4827 find_optimal_iv_set (struct ivopts_data
*data
)
4833 /* Get the initial solution. */
4834 set
= get_initial_solution (data
);
4837 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4838 fprintf (dump_file
, "Unable to substitute for ivs, failed.\n");
4842 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4844 fprintf (dump_file
, "Initial set of candidates:\n");
4845 iv_ca_dump (data
, dump_file
, set
);
4848 while (try_improve_iv_set (data
, set
))
4850 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4852 fprintf (dump_file
, "Improved to:\n");
4853 iv_ca_dump (data
, dump_file
, set
);
4857 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4859 comp_cost cost
= iv_ca_cost (set
);
4860 fprintf (dump_file
, "Final cost %d (complexity %d)\n\n", cost
.cost
, cost
.complexity
);
4863 for (i
= 0; i
< n_iv_uses (data
); i
++)
4865 use
= iv_use (data
, i
);
4866 use
->selected
= iv_ca_cand_for_use (set
, use
)->cand
;
4872 /* Creates a new induction variable corresponding to CAND. */
4875 create_new_iv (struct ivopts_data
*data
, struct iv_cand
*cand
)
4877 block_stmt_iterator incr_pos
;
4887 incr_pos
= bsi_last (ip_normal_pos (data
->current_loop
));
4891 incr_pos
= bsi_last (ip_end_pos (data
->current_loop
));
4896 /* Mark that the iv is preserved. */
4897 name_info (data
, cand
->var_before
)->preserve_biv
= true;
4898 name_info (data
, cand
->var_after
)->preserve_biv
= true;
4900 /* Rewrite the increment so that it uses var_before directly. */
4901 find_interesting_uses_op (data
, cand
->var_after
)->selected
= cand
;
4906 gimple_add_tmp_var (cand
->var_before
);
4907 add_referenced_var (cand
->var_before
);
4909 base
= unshare_expr (cand
->iv
->base
);
4911 create_iv (base
, unshare_expr (cand
->iv
->step
),
4912 cand
->var_before
, data
->current_loop
,
4913 &incr_pos
, after
, &cand
->var_before
, &cand
->var_after
);
4916 /* Creates new induction variables described in SET. */
4919 create_new_ivs (struct ivopts_data
*data
, struct iv_ca
*set
)
4922 struct iv_cand
*cand
;
4925 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
4927 cand
= iv_cand (data
, i
);
4928 create_new_iv (data
, cand
);
4932 /* Removes statement STMT (real or a phi node). If INCLUDING_DEFINED_NAME
4933 is true, remove also the ssa name defined by the statement. */
4936 remove_statement (tree stmt
, bool including_defined_name
)
4938 if (TREE_CODE (stmt
) == PHI_NODE
)
4940 remove_phi_node (stmt
, NULL_TREE
, including_defined_name
);
4944 block_stmt_iterator bsi
= bsi_for_stmt (stmt
);
4946 bsi_remove (&bsi
, true);
4947 release_defs (stmt
);
4951 /* Rewrites USE (definition of iv used in a nonlinear expression)
4952 using candidate CAND. */
4955 rewrite_use_nonlinear_expr (struct ivopts_data
*data
,
4956 struct iv_use
*use
, struct iv_cand
*cand
)
4960 block_stmt_iterator bsi
;
4962 /* An important special case -- if we are asked to express value of
4963 the original iv by itself, just exit; there is no need to
4964 introduce a new computation (that might also need casting the
4965 variable to unsigned and back). */
4966 if (cand
->pos
== IP_ORIGINAL
4967 && cand
->incremented_at
== use
->stmt
)
4969 tree step
, ctype
, utype
;
4970 enum tree_code incr_code
= PLUS_EXPR
;
4972 gcc_assert (TREE_CODE (use
->stmt
) == GIMPLE_MODIFY_STMT
);
4973 gcc_assert (GIMPLE_STMT_OPERAND (use
->stmt
, 0) == cand
->var_after
);
4975 step
= cand
->iv
->step
;
4976 ctype
= TREE_TYPE (step
);
4977 utype
= TREE_TYPE (cand
->var_after
);
4978 if (TREE_CODE (step
) == NEGATE_EXPR
)
4980 incr_code
= MINUS_EXPR
;
4981 step
= TREE_OPERAND (step
, 0);
4984 /* Check whether we may leave the computation unchanged.
4985 This is the case only if it does not rely on other
4986 computations in the loop -- otherwise, the computation
4987 we rely upon may be removed in remove_unused_ivs,
4988 thus leading to ICE. */
4989 op
= GIMPLE_STMT_OPERAND (use
->stmt
, 1);
4990 if (TREE_CODE (op
) == PLUS_EXPR
4991 || TREE_CODE (op
) == MINUS_EXPR
4992 || TREE_CODE (op
) == POINTER_PLUS_EXPR
)
4994 if (TREE_OPERAND (op
, 0) == cand
->var_before
)
4995 op
= TREE_OPERAND (op
, 1);
4996 else if (TREE_CODE (op
) != MINUS_EXPR
4997 && TREE_OPERAND (op
, 1) == cand
->var_before
)
4998 op
= TREE_OPERAND (op
, 0);
5006 && (TREE_CODE (op
) == INTEGER_CST
5007 || operand_equal_p (op
, step
, 0)))
5010 /* Otherwise, add the necessary computations to express
5012 op
= fold_convert (ctype
, cand
->var_before
);
5013 comp
= fold_convert (utype
,
5014 build2 (incr_code
, ctype
, op
,
5015 unshare_expr (step
)));
5019 comp
= get_computation (data
->current_loop
, use
, cand
);
5020 gcc_assert (comp
!= NULL_TREE
);
5023 switch (TREE_CODE (use
->stmt
))
5026 tgt
= PHI_RESULT (use
->stmt
);
5028 /* If we should keep the biv, do not replace it. */
5029 if (name_info (data
, tgt
)->preserve_biv
)
5032 bsi
= bsi_after_labels (bb_for_stmt (use
->stmt
));
5035 case GIMPLE_MODIFY_STMT
:
5036 tgt
= GIMPLE_STMT_OPERAND (use
->stmt
, 0);
5037 bsi
= bsi_for_stmt (use
->stmt
);
5044 op
= force_gimple_operand_bsi (&bsi
, comp
, false, SSA_NAME_VAR (tgt
),
5045 true, BSI_SAME_STMT
);
5047 if (TREE_CODE (use
->stmt
) == PHI_NODE
)
5049 ass
= build_gimple_modify_stmt (tgt
, op
);
5050 bsi_insert_before (&bsi
, ass
, BSI_SAME_STMT
);
5051 remove_statement (use
->stmt
, false);
5052 SSA_NAME_DEF_STMT (tgt
) = ass
;
5055 GIMPLE_STMT_OPERAND (use
->stmt
, 1) = op
;
5058 /* Replaces ssa name in index IDX by its basic variable. Callback for
5062 idx_remove_ssa_names (tree base
, tree
*idx
,
5063 void *data ATTRIBUTE_UNUSED
)
5067 if (TREE_CODE (*idx
) == SSA_NAME
)
5068 *idx
= SSA_NAME_VAR (*idx
);
5070 if (TREE_CODE (base
) == ARRAY_REF
)
5072 op
= &TREE_OPERAND (base
, 2);
5074 && TREE_CODE (*op
) == SSA_NAME
)
5075 *op
= SSA_NAME_VAR (*op
);
5076 op
= &TREE_OPERAND (base
, 3);
5078 && TREE_CODE (*op
) == SSA_NAME
)
5079 *op
= SSA_NAME_VAR (*op
);
5085 /* Unshares REF and replaces ssa names inside it by their basic variables. */
5088 unshare_and_remove_ssa_names (tree ref
)
5090 ref
= unshare_expr (ref
);
5091 for_each_index (&ref
, idx_remove_ssa_names
, NULL
);
5096 /* Extract the alias analysis info for the memory reference REF. There are
5097 several ways how this information may be stored and what precisely is
5098 its semantics depending on the type of the reference, but there always is
5099 somewhere hidden one _DECL node that is used to determine the set of
5100 virtual operands for the reference. The code below deciphers this jungle
5101 and extracts this single useful piece of information. */
5104 get_ref_tag (tree ref
, tree orig
)
5106 tree var
= get_base_address (ref
);
5107 tree aref
= NULL_TREE
, tag
, sv
;
5108 HOST_WIDE_INT offset
, size
, maxsize
;
5110 for (sv
= orig
; handled_component_p (sv
); sv
= TREE_OPERAND (sv
, 0))
5112 aref
= get_ref_base_and_extent (sv
, &offset
, &size
, &maxsize
);
5117 if (aref
&& SSA_VAR_P (aref
) && get_subvars_for_var (aref
))
5123 if (TREE_CODE (var
) == INDIRECT_REF
)
5125 /* If the base is a dereference of a pointer, first check its name memory
5126 tag. If it does not have one, use its symbol memory tag. */
5127 var
= TREE_OPERAND (var
, 0);
5128 if (TREE_CODE (var
) != SSA_NAME
)
5131 if (SSA_NAME_PTR_INFO (var
))
5133 tag
= SSA_NAME_PTR_INFO (var
)->name_mem_tag
;
5138 var
= SSA_NAME_VAR (var
);
5139 tag
= symbol_mem_tag (var
);
5140 gcc_assert (tag
!= NULL_TREE
);
5148 tag
= symbol_mem_tag (var
);
5156 /* Copies the reference information from OLD_REF to NEW_REF. */
5159 copy_ref_info (tree new_ref
, tree old_ref
)
5161 if (TREE_CODE (old_ref
) == TARGET_MEM_REF
)
5162 copy_mem_ref_info (new_ref
, old_ref
);
5165 TMR_ORIGINAL (new_ref
) = unshare_and_remove_ssa_names (old_ref
);
5166 TMR_TAG (new_ref
) = get_ref_tag (old_ref
, TMR_ORIGINAL (new_ref
));
5170 /* Rewrites USE (address that is an iv) using candidate CAND. */
5173 rewrite_use_address (struct ivopts_data
*data
,
5174 struct iv_use
*use
, struct iv_cand
*cand
)
5177 block_stmt_iterator bsi
= bsi_for_stmt (use
->stmt
);
5181 ok
= get_computation_aff (data
->current_loop
, use
, cand
, use
->stmt
, &aff
);
5183 unshare_aff_combination (&aff
);
5185 ref
= create_mem_ref (&bsi
, TREE_TYPE (*use
->op_p
), &aff
);
5186 copy_ref_info (ref
, *use
->op_p
);
5190 /* Rewrites USE (the condition such that one of the arguments is an iv) using
5194 rewrite_use_compare (struct ivopts_data
*data
,
5195 struct iv_use
*use
, struct iv_cand
*cand
)
5197 tree comp
, *var_p
, op
, bound
;
5198 block_stmt_iterator bsi
= bsi_for_stmt (use
->stmt
);
5199 enum tree_code compare
;
5200 struct cost_pair
*cp
= get_use_iv_cost (data
, use
, cand
);
5206 tree var
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
5207 tree var_type
= TREE_TYPE (var
);
5209 compare
= iv_elimination_compare (data
, use
);
5210 bound
= unshare_expr (fold_convert (var_type
, bound
));
5211 op
= force_gimple_operand_bsi (&bsi
, bound
, true, NULL_TREE
,
5212 true, BSI_SAME_STMT
);
5214 *use
->op_p
= build2 (compare
, boolean_type_node
, var
, op
);
5218 /* The induction variable elimination failed; just express the original
5220 comp
= get_computation (data
->current_loop
, use
, cand
);
5221 gcc_assert (comp
!= NULL_TREE
);
5223 ok
= extract_cond_operands (data
, use
->op_p
, &var_p
, NULL
, NULL
, NULL
);
5226 *var_p
= force_gimple_operand_bsi (&bsi
, comp
, true, SSA_NAME_VAR (*var_p
),
5227 true, BSI_SAME_STMT
);
5230 /* Rewrites USE using candidate CAND. */
5233 rewrite_use (struct ivopts_data
*data
, struct iv_use
*use
, struct iv_cand
*cand
)
5235 push_stmt_changes (&use
->stmt
);
5239 case USE_NONLINEAR_EXPR
:
5240 rewrite_use_nonlinear_expr (data
, use
, cand
);
5244 rewrite_use_address (data
, use
, cand
);
5248 rewrite_use_compare (data
, use
, cand
);
5255 pop_stmt_changes (&use
->stmt
);
5258 /* Rewrite the uses using the selected induction variables. */
5261 rewrite_uses (struct ivopts_data
*data
)
5264 struct iv_cand
*cand
;
5267 for (i
= 0; i
< n_iv_uses (data
); i
++)
5269 use
= iv_use (data
, i
);
5270 cand
= use
->selected
;
5273 rewrite_use (data
, use
, cand
);
5277 /* Removes the ivs that are not used after rewriting. */
5280 remove_unused_ivs (struct ivopts_data
*data
)
5285 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
5287 struct version_info
*info
;
5289 info
= ver_info (data
, j
);
5291 && !integer_zerop (info
->iv
->step
)
5293 && !info
->iv
->have_use_for
5294 && !info
->preserve_biv
)
5295 remove_statement (SSA_NAME_DEF_STMT (info
->iv
->ssa_name
), true);
5299 /* Frees data allocated by the optimization of a single loop. */
5302 free_loop_data (struct ivopts_data
*data
)
5310 pointer_map_destroy (data
->niters
);
5311 data
->niters
= NULL
;
5314 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
5316 struct version_info
*info
;
5318 info
= ver_info (data
, i
);
5322 info
->has_nonlin_use
= false;
5323 info
->preserve_biv
= false;
5326 bitmap_clear (data
->relevant
);
5327 bitmap_clear (data
->important_candidates
);
5329 for (i
= 0; i
< n_iv_uses (data
); i
++)
5331 struct iv_use
*use
= iv_use (data
, i
);
5334 BITMAP_FREE (use
->related_cands
);
5335 for (j
= 0; j
< use
->n_map_members
; j
++)
5336 if (use
->cost_map
[j
].depends_on
)
5337 BITMAP_FREE (use
->cost_map
[j
].depends_on
);
5338 free (use
->cost_map
);
5341 VEC_truncate (iv_use_p
, data
->iv_uses
, 0);
5343 for (i
= 0; i
< n_iv_cands (data
); i
++)
5345 struct iv_cand
*cand
= iv_cand (data
, i
);
5349 if (cand
->depends_on
)
5350 BITMAP_FREE (cand
->depends_on
);
5353 VEC_truncate (iv_cand_p
, data
->iv_candidates
, 0);
5355 if (data
->version_info_size
< num_ssa_names
)
5357 data
->version_info_size
= 2 * num_ssa_names
;
5358 free (data
->version_info
);
5359 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
5362 data
->max_inv_id
= 0;
5364 for (i
= 0; VEC_iterate (tree
, decl_rtl_to_reset
, i
, obj
); i
++)
5365 SET_DECL_RTL (obj
, NULL_RTX
);
5367 VEC_truncate (tree
, decl_rtl_to_reset
, 0);
5370 /* Finalizes data structures used by the iv optimization pass. LOOPS is the
5374 tree_ssa_iv_optimize_finalize (struct ivopts_data
*data
)
5376 free_loop_data (data
);
5377 free (data
->version_info
);
5378 BITMAP_FREE (data
->relevant
);
5379 BITMAP_FREE (data
->important_candidates
);
5381 VEC_free (tree
, heap
, decl_rtl_to_reset
);
5382 VEC_free (iv_use_p
, heap
, data
->iv_uses
);
5383 VEC_free (iv_cand_p
, heap
, data
->iv_candidates
);
5386 /* Optimizes the LOOP. Returns true if anything changed. */
5389 tree_ssa_iv_optimize_loop (struct ivopts_data
*data
, struct loop
*loop
)
5391 bool changed
= false;
5392 struct iv_ca
*iv_ca
;
5395 gcc_assert (!data
->niters
);
5396 data
->current_loop
= loop
;
5398 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5400 fprintf (dump_file
, "Processing loop %d\n", loop
->num
);
5402 exit
= single_dom_exit (loop
);
5405 fprintf (dump_file
, " single exit %d -> %d, exit condition ",
5406 exit
->src
->index
, exit
->dest
->index
);
5407 print_generic_expr (dump_file
, last_stmt (exit
->src
), TDF_SLIM
);
5408 fprintf (dump_file
, "\n");
5411 fprintf (dump_file
, "\n");
5414 /* For each ssa name determines whether it behaves as an induction variable
5416 if (!find_induction_variables (data
))
5419 /* Finds interesting uses (item 1). */
5420 find_interesting_uses (data
);
5421 if (n_iv_uses (data
) > MAX_CONSIDERED_USES
)
5424 /* Finds candidates for the induction variables (item 2). */
5425 find_iv_candidates (data
);
5427 /* Calculates the costs (item 3, part 1). */
5428 determine_use_iv_costs (data
);
5429 determine_iv_costs (data
);
5430 determine_set_costs (data
);
5432 /* Find the optimal set of induction variables (item 3, part 2). */
5433 iv_ca
= find_optimal_iv_set (data
);
5438 /* Create the new induction variables (item 4, part 1). */
5439 create_new_ivs (data
, iv_ca
);
5440 iv_ca_free (&iv_ca
);
5442 /* Rewrite the uses (item 4, part 2). */
5443 rewrite_uses (data
);
5445 /* Remove the ivs that are unused after rewriting. */
5446 remove_unused_ivs (data
);
5448 /* We have changed the structure of induction variables; it might happen
5449 that definitions in the scev database refer to some of them that were
5454 free_loop_data (data
);
5459 /* Main entry point. Optimizes induction variables in loops. */
5462 tree_ssa_iv_optimize (void)
5465 struct ivopts_data data
;
5468 tree_ssa_iv_optimize_init (&data
);
5470 /* Optimize the loops starting with the innermost ones. */
5471 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
5473 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5474 flow_loop_dump (loop
, dump_file
, NULL
, 1);
5476 tree_ssa_iv_optimize_loop (&data
, loop
);
5479 tree_ssa_iv_optimize_finalize (&data
);