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
);
918 if (POINTER_TYPE_P (type
))
919 step
= fold_convert (sizetype
, step
);
921 step
= fold_convert (type
, step
);
924 set_iv (data
, PHI_RESULT (phi
), base
, step
);
931 /* Marks basic ivs. */
934 mark_bivs (struct ivopts_data
*data
)
937 struct iv
*iv
, *incr_iv
;
938 struct loop
*loop
= data
->current_loop
;
941 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
943 iv
= get_iv (data
, PHI_RESULT (phi
));
947 var
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
948 incr_iv
= get_iv (data
, var
);
952 /* If the increment is in the subloop, ignore it. */
953 incr_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (var
));
954 if (incr_bb
->loop_father
!= data
->current_loop
955 || (incr_bb
->flags
& BB_IRREDUCIBLE_LOOP
))
959 incr_iv
->biv_p
= true;
963 /* Checks whether STMT defines a linear induction variable and stores its
967 find_givs_in_stmt_scev (struct ivopts_data
*data
, tree stmt
, affine_iv
*iv
)
970 struct loop
*loop
= data
->current_loop
;
972 iv
->base
= NULL_TREE
;
973 iv
->step
= NULL_TREE
;
975 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
978 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
979 if (TREE_CODE (lhs
) != SSA_NAME
)
982 if (!simple_iv (loop
, stmt
, GIMPLE_STMT_OPERAND (stmt
, 1), iv
, true))
984 iv
->base
= expand_simple_operations (iv
->base
);
986 if (contains_abnormal_ssa_name_p (iv
->base
)
987 || contains_abnormal_ssa_name_p (iv
->step
))
993 /* Finds general ivs in statement STMT. */
996 find_givs_in_stmt (struct ivopts_data
*data
, tree stmt
)
1000 if (!find_givs_in_stmt_scev (data
, stmt
, &iv
))
1003 set_iv (data
, GIMPLE_STMT_OPERAND (stmt
, 0), iv
.base
, iv
.step
);
1006 /* Finds general ivs in basic block BB. */
1009 find_givs_in_bb (struct ivopts_data
*data
, basic_block bb
)
1011 block_stmt_iterator bsi
;
1013 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1014 find_givs_in_stmt (data
, bsi_stmt (bsi
));
1017 /* Finds general ivs. */
1020 find_givs (struct ivopts_data
*data
)
1022 struct loop
*loop
= data
->current_loop
;
1023 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1026 for (i
= 0; i
< loop
->num_nodes
; i
++)
1027 find_givs_in_bb (data
, body
[i
]);
1031 /* For each ssa name defined in LOOP determines whether it is an induction
1032 variable and if so, its initial value and step. */
1035 find_induction_variables (struct ivopts_data
*data
)
1040 if (!find_bivs (data
))
1046 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1048 tree niter
= niter_for_single_dom_exit (data
);
1052 fprintf (dump_file
, " number of iterations ");
1053 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1054 fprintf (dump_file
, "\n\n");
1057 fprintf (dump_file
, "Induction variables:\n\n");
1059 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1061 if (ver_info (data
, i
)->iv
)
1062 dump_iv (dump_file
, ver_info (data
, i
)->iv
);
1069 /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV. */
1071 static struct iv_use
*
1072 record_use (struct ivopts_data
*data
, tree
*use_p
, struct iv
*iv
,
1073 tree stmt
, enum use_type use_type
)
1075 struct iv_use
*use
= XCNEW (struct iv_use
);
1077 use
->id
= n_iv_uses (data
);
1078 use
->type
= use_type
;
1082 use
->related_cands
= BITMAP_ALLOC (NULL
);
1084 /* To avoid showing ssa name in the dumps, if it was not reset by the
1086 iv
->ssa_name
= NULL_TREE
;
1088 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1089 dump_use (dump_file
, use
);
1091 VEC_safe_push (iv_use_p
, heap
, data
->iv_uses
, use
);
1096 /* Checks whether OP is a loop-level invariant and if so, records it.
1097 NONLINEAR_USE is true if the invariant is used in a way we do not
1098 handle specially. */
1101 record_invariant (struct ivopts_data
*data
, tree op
, bool nonlinear_use
)
1104 struct version_info
*info
;
1106 if (TREE_CODE (op
) != SSA_NAME
1107 || !is_gimple_reg (op
))
1110 bb
= bb_for_stmt (SSA_NAME_DEF_STMT (op
));
1112 && flow_bb_inside_loop_p (data
->current_loop
, bb
))
1115 info
= name_info (data
, op
);
1117 info
->has_nonlin_use
|= nonlinear_use
;
1119 info
->inv_id
= ++data
->max_inv_id
;
1120 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (op
));
1123 /* Checks whether the use OP is interesting and if so, records it. */
1125 static struct iv_use
*
1126 find_interesting_uses_op (struct ivopts_data
*data
, tree op
)
1133 if (TREE_CODE (op
) != SSA_NAME
)
1136 iv
= get_iv (data
, op
);
1140 if (iv
->have_use_for
)
1142 use
= iv_use (data
, iv
->use_id
);
1144 gcc_assert (use
->type
== USE_NONLINEAR_EXPR
);
1148 if (integer_zerop (iv
->step
))
1150 record_invariant (data
, op
, true);
1153 iv
->have_use_for
= true;
1155 civ
= XNEW (struct iv
);
1158 stmt
= SSA_NAME_DEF_STMT (op
);
1159 gcc_assert (TREE_CODE (stmt
) == PHI_NODE
1160 || TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
);
1162 use
= record_use (data
, NULL
, civ
, stmt
, USE_NONLINEAR_EXPR
);
1163 iv
->use_id
= use
->id
;
1168 /* Given a condition *COND_P, checks whether it is a compare of an induction
1169 variable and an invariant. If this is the case, CONTROL_VAR is set
1170 to location of the iv, BOUND to the location of the invariant,
1171 IV_VAR and IV_BOUND are set to the corresponding induction variable
1172 descriptions, and true is returned. If this is not the case,
1173 CONTROL_VAR and BOUND are set to the arguments of the condition and
1174 false is returned. */
1177 extract_cond_operands (struct ivopts_data
*data
, tree
*cond_p
,
1178 tree
**control_var
, tree
**bound
,
1179 struct iv
**iv_var
, struct iv
**iv_bound
)
1181 /* The nodes returned when COND has just one operand. Note that you should
1182 not modify anything in BOUND or IV_BOUND because of this. */
1183 static struct iv const_iv
;
1185 tree cond
= *cond_p
;
1186 tree
*op0
= &zero
, *op1
= &zero
, *tmp_op
;
1187 struct iv
*iv0
= &const_iv
, *iv1
= &const_iv
, *tmp_iv
;
1190 zero
= integer_zero_node
;
1191 const_iv
.step
= integer_zero_node
;
1193 if (TREE_CODE (cond
) == SSA_NAME
)
1196 iv0
= get_iv (data
, cond
);
1197 ret
= (iv0
&& !integer_zerop (iv0
->step
));
1201 if (!COMPARISON_CLASS_P (cond
))
1207 op0
= &TREE_OPERAND (cond
, 0);
1208 op1
= &TREE_OPERAND (cond
, 1);
1209 if (TREE_CODE (*op0
) == SSA_NAME
)
1210 iv0
= get_iv (data
, *op0
);
1211 if (TREE_CODE (*op1
) == SSA_NAME
)
1212 iv1
= get_iv (data
, *op1
);
1214 /* Exactly one of the compared values must be an iv, and the other one must
1219 if (integer_zerop (iv0
->step
))
1221 /* Control variable may be on the other side. */
1222 tmp_op
= op0
; op0
= op1
; op1
= tmp_op
;
1223 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
1225 ret
= !integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
);
1229 *control_var
= op0
;;
1240 /* Checks whether the condition *COND_P in STMT is interesting
1241 and if so, records it. */
1244 find_interesting_uses_cond (struct ivopts_data
*data
, tree stmt
, tree
*cond_p
)
1246 tree
*var_p
, *bound_p
;
1247 struct iv
*var_iv
, *civ
;
1249 if (!extract_cond_operands (data
, cond_p
, &var_p
, &bound_p
, &var_iv
, NULL
))
1251 find_interesting_uses_op (data
, *var_p
);
1252 find_interesting_uses_op (data
, *bound_p
);
1256 civ
= XNEW (struct iv
);
1258 record_use (data
, cond_p
, civ
, stmt
, USE_COMPARE
);
1261 /* Returns true if expression EXPR is obviously invariant in LOOP,
1262 i.e. if all its operands are defined outside of the LOOP. LOOP
1263 should not be the function body. */
1266 expr_invariant_in_loop_p (struct loop
*loop
, tree expr
)
1271 gcc_assert (loop_depth (loop
) > 0);
1273 if (is_gimple_min_invariant (expr
))
1276 if (TREE_CODE (expr
) == SSA_NAME
)
1278 def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (expr
));
1280 && flow_bb_inside_loop_p (loop
, def_bb
))
1286 if (!EXPR_P (expr
) && !GIMPLE_STMT_P (expr
))
1289 len
= TREE_OPERAND_LENGTH (expr
);
1290 for (i
= 0; i
< len
; i
++)
1291 if (!expr_invariant_in_loop_p (loop
, TREE_OPERAND (expr
, i
)))
1297 /* Cumulates the steps of indices into DATA and replaces their values with the
1298 initial ones. Returns false when the value of the index cannot be determined.
1299 Callback for for_each_index. */
1301 struct ifs_ivopts_data
1303 struct ivopts_data
*ivopts_data
;
1309 idx_find_step (tree base
, tree
*idx
, void *data
)
1311 struct ifs_ivopts_data
*dta
= (struct ifs_ivopts_data
*) data
;
1313 tree step
, iv_base
, iv_step
, lbound
, off
;
1314 struct loop
*loop
= dta
->ivopts_data
->current_loop
;
1316 if (TREE_CODE (base
) == MISALIGNED_INDIRECT_REF
1317 || TREE_CODE (base
) == ALIGN_INDIRECT_REF
)
1320 /* If base is a component ref, require that the offset of the reference
1322 if (TREE_CODE (base
) == COMPONENT_REF
)
1324 off
= component_ref_field_offset (base
);
1325 return expr_invariant_in_loop_p (loop
, off
);
1328 /* If base is array, first check whether we will be able to move the
1329 reference out of the loop (in order to take its address in strength
1330 reduction). In order for this to work we need both lower bound
1331 and step to be loop invariants. */
1332 if (TREE_CODE (base
) == ARRAY_REF
)
1334 step
= array_ref_element_size (base
);
1335 lbound
= array_ref_low_bound (base
);
1337 if (!expr_invariant_in_loop_p (loop
, step
)
1338 || !expr_invariant_in_loop_p (loop
, lbound
))
1342 if (TREE_CODE (*idx
) != SSA_NAME
)
1345 iv
= get_iv (dta
->ivopts_data
, *idx
);
1349 /* XXX We produce for a base of *D42 with iv->base being &x[0]
1350 *&x[0], which is not folded and does not trigger the
1351 ARRAY_REF path below. */
1354 if (integer_zerop (iv
->step
))
1357 if (TREE_CODE (base
) == ARRAY_REF
)
1359 step
= array_ref_element_size (base
);
1361 /* We only handle addresses whose step is an integer constant. */
1362 if (TREE_CODE (step
) != INTEGER_CST
)
1366 /* The step for pointer arithmetics already is 1 byte. */
1367 step
= build_int_cst (sizetype
, 1);
1371 if (!convert_affine_scev (dta
->ivopts_data
->current_loop
,
1372 sizetype
, &iv_base
, &iv_step
, dta
->stmt
,
1375 /* The index might wrap. */
1379 step
= fold_build2 (MULT_EXPR
, sizetype
, step
, iv_step
);
1380 dta
->step
= fold_build2 (PLUS_EXPR
, sizetype
, dta
->step
, step
);
1385 /* Records use in index IDX. Callback for for_each_index. Ivopts data
1386 object is passed to it in DATA. */
1389 idx_record_use (tree base
, tree
*idx
,
1392 struct ivopts_data
*data
= (struct ivopts_data
*) vdata
;
1393 find_interesting_uses_op (data
, *idx
);
1394 if (TREE_CODE (base
) == ARRAY_REF
)
1396 find_interesting_uses_op (data
, array_ref_element_size (base
));
1397 find_interesting_uses_op (data
, array_ref_low_bound (base
));
1402 /* If we can prove that TOP = cst * BOT for some constant cst,
1403 store cst to MUL and return true. Otherwise return false.
1404 The returned value is always sign-extended, regardless of the
1405 signedness of TOP and BOT. */
1408 constant_multiple_of (tree top
, tree bot
, double_int
*mul
)
1411 enum tree_code code
;
1412 double_int res
, p0
, p1
;
1413 unsigned precision
= TYPE_PRECISION (TREE_TYPE (top
));
1418 if (operand_equal_p (top
, bot
, 0))
1420 *mul
= double_int_one
;
1424 code
= TREE_CODE (top
);
1428 mby
= TREE_OPERAND (top
, 1);
1429 if (TREE_CODE (mby
) != INTEGER_CST
)
1432 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &res
))
1435 *mul
= double_int_sext (double_int_mul (res
, tree_to_double_int (mby
)),
1441 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &p0
)
1442 || !constant_multiple_of (TREE_OPERAND (top
, 1), bot
, &p1
))
1445 if (code
== MINUS_EXPR
)
1446 p1
= double_int_neg (p1
);
1447 *mul
= double_int_sext (double_int_add (p0
, p1
), precision
);
1451 if (TREE_CODE (bot
) != INTEGER_CST
)
1454 p0
= double_int_sext (tree_to_double_int (top
), precision
);
1455 p1
= double_int_sext (tree_to_double_int (bot
), precision
);
1456 if (double_int_zero_p (p1
))
1458 *mul
= double_int_sext (double_int_sdivmod (p0
, p1
, FLOOR_DIV_EXPR
, &res
),
1460 return double_int_zero_p (res
);
1467 /* Returns true if memory reference REF with step STEP may be unaligned. */
1470 may_be_unaligned_p (tree ref
, tree step
)
1474 HOST_WIDE_INT bitsize
;
1475 HOST_WIDE_INT bitpos
;
1477 enum machine_mode mode
;
1478 int unsignedp
, volatilep
;
1479 unsigned base_align
;
1481 /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
1482 thus they are not misaligned. */
1483 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
1486 /* The test below is basically copy of what expr.c:normal_inner_ref
1487 does to check whether the object must be loaded by parts when
1488 STRICT_ALIGNMENT is true. */
1489 base
= get_inner_reference (ref
, &bitsize
, &bitpos
, &toffset
, &mode
,
1490 &unsignedp
, &volatilep
, true);
1491 base_type
= TREE_TYPE (base
);
1492 base_align
= TYPE_ALIGN (base_type
);
1494 if (mode
!= BLKmode
)
1497 tree al
= build_int_cst (TREE_TYPE (step
),
1498 GET_MODE_ALIGNMENT (mode
) / BITS_PER_UNIT
);
1500 if (base_align
< GET_MODE_ALIGNMENT (mode
)
1501 || bitpos
% GET_MODE_ALIGNMENT (mode
) != 0
1502 || bitpos
% BITS_PER_UNIT
!= 0)
1505 if (!constant_multiple_of (step
, al
, &mul
))
1512 /* Return true if EXPR may be non-addressable. */
1515 may_be_nonaddressable_p (tree expr
)
1517 switch (TREE_CODE (expr
))
1519 case TARGET_MEM_REF
:
1520 /* TARGET_MEM_REFs are translated directly to valid MEMs on the
1521 target, thus they are always addressable. */
1525 return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr
, 1))
1526 || may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1528 case VIEW_CONVERT_EXPR
:
1529 /* This kind of view-conversions may wrap non-addressable objects
1530 and make them look addressable. After some processing the
1531 non-addressability may be uncovered again, causing ADDR_EXPRs
1532 of inappropriate objects to be built. */
1533 if (is_gimple_reg (TREE_OPERAND (expr
, 0))
1534 || is_gimple_min_invariant (TREE_OPERAND (expr
, 0)))
1537 /* ... fall through ... */
1540 case ARRAY_RANGE_REF
:
1541 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1554 /* Finds addresses in *OP_P inside STMT. */
1557 find_interesting_uses_address (struct ivopts_data
*data
, tree stmt
, tree
*op_p
)
1559 tree base
= *op_p
, step
= build_int_cst (sizetype
, 0);
1561 struct ifs_ivopts_data ifs_ivopts_data
;
1563 /* Do not play with volatile memory references. A bit too conservative,
1564 perhaps, but safe. */
1565 if (stmt_ann (stmt
)->has_volatile_ops
)
1568 /* Ignore bitfields for now. Not really something terribly complicated
1570 if (TREE_CODE (base
) == BIT_FIELD_REF
)
1573 base
= unshare_expr (base
);
1575 if (TREE_CODE (base
) == TARGET_MEM_REF
)
1577 tree type
= build_pointer_type (TREE_TYPE (base
));
1581 && TREE_CODE (TMR_BASE (base
)) == SSA_NAME
)
1583 civ
= get_iv (data
, TMR_BASE (base
));
1587 TMR_BASE (base
) = civ
->base
;
1590 if (TMR_INDEX (base
)
1591 && TREE_CODE (TMR_INDEX (base
)) == SSA_NAME
)
1593 civ
= get_iv (data
, TMR_INDEX (base
));
1597 TMR_INDEX (base
) = civ
->base
;
1602 if (TMR_STEP (base
))
1603 astep
= fold_build2 (MULT_EXPR
, type
, TMR_STEP (base
), astep
);
1605 step
= fold_build2 (PLUS_EXPR
, type
, step
, astep
);
1609 if (integer_zerop (step
))
1611 base
= tree_mem_ref_addr (type
, base
);
1615 ifs_ivopts_data
.ivopts_data
= data
;
1616 ifs_ivopts_data
.stmt
= stmt
;
1617 ifs_ivopts_data
.step
= build_int_cst (sizetype
, 0);
1618 if (!for_each_index (&base
, idx_find_step
, &ifs_ivopts_data
)
1619 || integer_zerop (ifs_ivopts_data
.step
))
1621 step
= ifs_ivopts_data
.step
;
1623 gcc_assert (TREE_CODE (base
) != ALIGN_INDIRECT_REF
);
1624 gcc_assert (TREE_CODE (base
) != MISALIGNED_INDIRECT_REF
);
1626 /* Check that the base expression is addressable. This needs
1627 to be done after substituting bases of IVs into it. */
1628 if (may_be_nonaddressable_p (base
))
1631 /* Moreover, on strict alignment platforms, check that it is
1632 sufficiently aligned. */
1633 if (STRICT_ALIGNMENT
&& may_be_unaligned_p (base
, step
))
1636 base
= build_fold_addr_expr (base
);
1638 /* Substituting bases of IVs into the base expression might
1639 have caused folding opportunities. */
1640 if (TREE_CODE (base
) == ADDR_EXPR
)
1642 tree
*ref
= &TREE_OPERAND (base
, 0);
1643 while (handled_component_p (*ref
))
1644 ref
= &TREE_OPERAND (*ref
, 0);
1645 if (TREE_CODE (*ref
) == INDIRECT_REF
)
1646 *ref
= fold_indirect_ref (*ref
);
1650 civ
= alloc_iv (base
, step
);
1651 record_use (data
, op_p
, civ
, stmt
, USE_ADDRESS
);
1655 for_each_index (op_p
, idx_record_use
, data
);
1658 /* Finds and records invariants used in STMT. */
1661 find_invariants_stmt (struct ivopts_data
*data
, tree stmt
)
1664 use_operand_p use_p
;
1667 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1669 op
= USE_FROM_PTR (use_p
);
1670 record_invariant (data
, op
, false);
1674 /* Finds interesting uses of induction variables in the statement STMT. */
1677 find_interesting_uses_stmt (struct ivopts_data
*data
, tree stmt
)
1682 use_operand_p use_p
;
1684 find_invariants_stmt (data
, stmt
);
1686 if (TREE_CODE (stmt
) == COND_EXPR
)
1688 find_interesting_uses_cond (data
, stmt
, &COND_EXPR_COND (stmt
));
1692 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
1694 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
1695 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1697 if (TREE_CODE (lhs
) == SSA_NAME
)
1699 /* If the statement defines an induction variable, the uses are not
1700 interesting by themselves. */
1702 iv
= get_iv (data
, lhs
);
1704 if (iv
&& !integer_zerop (iv
->step
))
1708 switch (TREE_CODE_CLASS (TREE_CODE (rhs
)))
1710 case tcc_comparison
:
1711 find_interesting_uses_cond (data
, stmt
,
1712 &GIMPLE_STMT_OPERAND (stmt
, 1));
1716 find_interesting_uses_address (data
, stmt
,
1717 &GIMPLE_STMT_OPERAND (stmt
, 1));
1718 if (REFERENCE_CLASS_P (lhs
))
1719 find_interesting_uses_address (data
, stmt
,
1720 &GIMPLE_STMT_OPERAND (stmt
, 0));
1726 if (REFERENCE_CLASS_P (lhs
)
1727 && is_gimple_val (rhs
))
1729 find_interesting_uses_address (data
, stmt
,
1730 &GIMPLE_STMT_OPERAND (stmt
, 0));
1731 find_interesting_uses_op (data
, rhs
);
1735 /* TODO -- we should also handle address uses of type
1737 memory = call (whatever);
1744 if (TREE_CODE (stmt
) == PHI_NODE
1745 && bb_for_stmt (stmt
) == data
->current_loop
->header
)
1747 lhs
= PHI_RESULT (stmt
);
1748 iv
= get_iv (data
, lhs
);
1750 if (iv
&& !integer_zerop (iv
->step
))
1754 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1756 op
= USE_FROM_PTR (use_p
);
1758 if (TREE_CODE (op
) != SSA_NAME
)
1761 iv
= get_iv (data
, op
);
1765 find_interesting_uses_op (data
, op
);
1769 /* Finds interesting uses of induction variables outside of loops
1770 on loop exit edge EXIT. */
1773 find_interesting_uses_outside (struct ivopts_data
*data
, edge exit
)
1777 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= PHI_CHAIN (phi
))
1779 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1780 if (is_gimple_reg (def
))
1781 find_interesting_uses_op (data
, def
);
1785 /* Finds uses of the induction variables that are interesting. */
1788 find_interesting_uses (struct ivopts_data
*data
)
1791 block_stmt_iterator bsi
;
1793 basic_block
*body
= get_loop_body (data
->current_loop
);
1795 struct version_info
*info
;
1798 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1799 fprintf (dump_file
, "Uses:\n\n");
1801 for (i
= 0; i
< data
->current_loop
->num_nodes
; i
++)
1806 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1807 if (e
->dest
!= EXIT_BLOCK_PTR
1808 && !flow_bb_inside_loop_p (data
->current_loop
, e
->dest
))
1809 find_interesting_uses_outside (data
, e
);
1811 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1812 find_interesting_uses_stmt (data
, phi
);
1813 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1814 find_interesting_uses_stmt (data
, bsi_stmt (bsi
));
1817 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1821 fprintf (dump_file
, "\n");
1823 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1825 info
= ver_info (data
, i
);
1828 fprintf (dump_file
, " ");
1829 print_generic_expr (dump_file
, info
->name
, TDF_SLIM
);
1830 fprintf (dump_file
, " is invariant (%d)%s\n",
1831 info
->inv_id
, info
->has_nonlin_use
? "" : ", eliminable");
1835 fprintf (dump_file
, "\n");
1841 /* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
1842 is true, assume we are inside an address. If TOP_COMPREF is true, assume
1843 we are at the top-level of the processed address. */
1846 strip_offset_1 (tree expr
, bool inside_addr
, bool top_compref
,
1847 unsigned HOST_WIDE_INT
*offset
)
1849 tree op0
= NULL_TREE
, op1
= NULL_TREE
, tmp
, step
;
1850 enum tree_code code
;
1851 tree type
, orig_type
= TREE_TYPE (expr
);
1852 unsigned HOST_WIDE_INT off0
, off1
, st
;
1853 tree orig_expr
= expr
;
1857 type
= TREE_TYPE (expr
);
1858 code
= TREE_CODE (expr
);
1864 if (!cst_and_fits_in_hwi (expr
)
1865 || integer_zerop (expr
))
1868 *offset
= int_cst_value (expr
);
1869 return build_int_cst (orig_type
, 0);
1871 case POINTER_PLUS_EXPR
:
1874 op0
= TREE_OPERAND (expr
, 0);
1875 op1
= TREE_OPERAND (expr
, 1);
1877 op0
= strip_offset_1 (op0
, false, false, &off0
);
1878 op1
= strip_offset_1 (op1
, false, false, &off1
);
1880 *offset
= (code
== MINUS_EXPR
? off0
- off1
: off0
+ off1
);
1881 if (op0
== TREE_OPERAND (expr
, 0)
1882 && op1
== TREE_OPERAND (expr
, 1))
1885 if (integer_zerop (op1
))
1887 else if (integer_zerop (op0
))
1889 if (code
== MINUS_EXPR
)
1890 expr
= fold_build1 (NEGATE_EXPR
, type
, op1
);
1895 expr
= fold_build2 (code
, type
, op0
, op1
);
1897 return fold_convert (orig_type
, expr
);
1903 step
= array_ref_element_size (expr
);
1904 if (!cst_and_fits_in_hwi (step
))
1907 st
= int_cst_value (step
);
1908 op1
= TREE_OPERAND (expr
, 1);
1909 op1
= strip_offset_1 (op1
, false, false, &off1
);
1910 *offset
= off1
* st
;
1913 && integer_zerop (op1
))
1915 /* Strip the component reference completely. */
1916 op0
= TREE_OPERAND (expr
, 0);
1917 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
1927 tmp
= component_ref_field_offset (expr
);
1929 && cst_and_fits_in_hwi (tmp
))
1931 /* Strip the component reference completely. */
1932 op0
= TREE_OPERAND (expr
, 0);
1933 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
1934 *offset
= off0
+ int_cst_value (tmp
);
1940 op0
= TREE_OPERAND (expr
, 0);
1941 op0
= strip_offset_1 (op0
, true, true, &off0
);
1944 if (op0
== TREE_OPERAND (expr
, 0))
1947 expr
= build_fold_addr_expr (op0
);
1948 return fold_convert (orig_type
, expr
);
1951 inside_addr
= false;
1958 /* Default handling of expressions for that we want to recurse into
1959 the first operand. */
1960 op0
= TREE_OPERAND (expr
, 0);
1961 op0
= strip_offset_1 (op0
, inside_addr
, false, &off0
);
1964 if (op0
== TREE_OPERAND (expr
, 0)
1965 && (!op1
|| op1
== TREE_OPERAND (expr
, 1)))
1968 expr
= copy_node (expr
);
1969 TREE_OPERAND (expr
, 0) = op0
;
1971 TREE_OPERAND (expr
, 1) = op1
;
1973 /* Inside address, we might strip the top level component references,
1974 thus changing type of the expression. Handling of ADDR_EXPR
1976 expr
= fold_convert (orig_type
, expr
);
1981 /* Strips constant offsets from EXPR and stores them to OFFSET. */
1984 strip_offset (tree expr
, unsigned HOST_WIDE_INT
*offset
)
1986 return strip_offset_1 (expr
, false, false, offset
);
1989 /* Returns variant of TYPE that can be used as base for different uses.
1990 We return unsigned type with the same precision, which avoids problems
1994 generic_type_for (tree type
)
1996 if (POINTER_TYPE_P (type
))
1997 return unsigned_type_for (type
);
1999 if (TYPE_UNSIGNED (type
))
2002 return unsigned_type_for (type
);
2005 /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
2006 the bitmap to that we should store it. */
2008 static struct ivopts_data
*fd_ivopts_data
;
2010 find_depends (tree
*expr_p
, int *ws ATTRIBUTE_UNUSED
, void *data
)
2012 bitmap
*depends_on
= (bitmap
*) data
;
2013 struct version_info
*info
;
2015 if (TREE_CODE (*expr_p
) != SSA_NAME
)
2017 info
= name_info (fd_ivopts_data
, *expr_p
);
2019 if (!info
->inv_id
|| info
->has_nonlin_use
)
2023 *depends_on
= BITMAP_ALLOC (NULL
);
2024 bitmap_set_bit (*depends_on
, info
->inv_id
);
2029 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2030 position to POS. If USE is not NULL, the candidate is set as related to
2031 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
2032 replacement of the final value of the iv by a direct computation. */
2034 static struct iv_cand
*
2035 add_candidate_1 (struct ivopts_data
*data
,
2036 tree base
, tree step
, bool important
, enum iv_position pos
,
2037 struct iv_use
*use
, tree incremented_at
)
2040 struct iv_cand
*cand
= NULL
;
2041 tree type
, orig_type
;
2045 orig_type
= TREE_TYPE (base
);
2046 type
= generic_type_for (orig_type
);
2047 /* Don't convert the base to the generic type for pointers as the generic
2048 type is an integer type with the same size as the pointer type. */
2049 if (type
!= orig_type
&& !POINTER_TYPE_P (orig_type
))
2051 base
= fold_convert (type
, base
);
2052 step
= fold_convert (type
, step
);
2056 for (i
= 0; i
< n_iv_cands (data
); i
++)
2058 cand
= iv_cand (data
, i
);
2060 if (cand
->pos
!= pos
)
2063 if (cand
->incremented_at
!= incremented_at
)
2077 if (operand_equal_p (base
, cand
->iv
->base
, 0)
2078 && operand_equal_p (step
, cand
->iv
->step
, 0))
2082 if (i
== n_iv_cands (data
))
2084 cand
= XCNEW (struct iv_cand
);
2090 cand
->iv
= alloc_iv (base
, step
);
2093 if (pos
!= IP_ORIGINAL
&& cand
->iv
)
2095 cand
->var_before
= create_tmp_var_raw (TREE_TYPE (base
), "ivtmp");
2096 cand
->var_after
= cand
->var_before
;
2098 cand
->important
= important
;
2099 cand
->incremented_at
= incremented_at
;
2100 VEC_safe_push (iv_cand_p
, heap
, data
->iv_candidates
, cand
);
2103 && TREE_CODE (step
) != INTEGER_CST
)
2105 fd_ivopts_data
= data
;
2106 walk_tree (&step
, find_depends
, &cand
->depends_on
, NULL
);
2109 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2110 dump_cand (dump_file
, cand
);
2113 if (important
&& !cand
->important
)
2115 cand
->important
= true;
2116 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2117 fprintf (dump_file
, "Candidate %d is important\n", cand
->id
);
2122 bitmap_set_bit (use
->related_cands
, i
);
2123 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2124 fprintf (dump_file
, "Candidate %d is related to use %d\n",
2131 /* Returns true if incrementing the induction variable at the end of the LOOP
2134 The purpose is to avoid splitting latch edge with a biv increment, thus
2135 creating a jump, possibly confusing other optimization passes and leaving
2136 less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS
2137 is not available (so we do not have a better alternative), or if the latch
2138 edge is already nonempty. */
2141 allow_ip_end_pos_p (struct loop
*loop
)
2143 if (!ip_normal_pos (loop
))
2146 if (!empty_block_p (ip_end_pos (loop
)))
2152 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2153 position to POS. If USE is not NULL, the candidate is set as related to
2154 it. The candidate computation is scheduled on all available positions. */
2157 add_candidate (struct ivopts_data
*data
,
2158 tree base
, tree step
, bool important
, struct iv_use
*use
)
2160 if (ip_normal_pos (data
->current_loop
))
2161 add_candidate_1 (data
, base
, step
, important
, IP_NORMAL
, use
, NULL_TREE
);
2162 if (ip_end_pos (data
->current_loop
)
2163 && allow_ip_end_pos_p (data
->current_loop
))
2164 add_candidate_1 (data
, base
, step
, important
, IP_END
, use
, NULL_TREE
);
2167 /* Add a standard "0 + 1 * iteration" iv candidate for a
2168 type with SIZE bits. */
2171 add_standard_iv_candidates_for_size (struct ivopts_data
*data
,
2174 tree type
= lang_hooks
.types
.type_for_size (size
, true);
2175 add_candidate (data
, build_int_cst (type
, 0), build_int_cst (type
, 1),
2179 /* Adds standard iv candidates. */
2182 add_standard_iv_candidates (struct ivopts_data
*data
)
2184 add_standard_iv_candidates_for_size (data
, INT_TYPE_SIZE
);
2186 /* The same for a double-integer type if it is still fast enough. */
2187 if (BITS_PER_WORD
>= INT_TYPE_SIZE
* 2)
2188 add_standard_iv_candidates_for_size (data
, INT_TYPE_SIZE
* 2);
2192 /* Adds candidates bases on the old induction variable IV. */
2195 add_old_iv_candidates (struct ivopts_data
*data
, struct iv
*iv
)
2198 struct iv_cand
*cand
;
2200 add_candidate (data
, iv
->base
, iv
->step
, true, NULL
);
2202 /* The same, but with initial value zero. */
2203 add_candidate (data
,
2204 build_int_cst (TREE_TYPE (iv
->base
), 0),
2205 iv
->step
, true, NULL
);
2207 phi
= SSA_NAME_DEF_STMT (iv
->ssa_name
);
2208 if (TREE_CODE (phi
) == PHI_NODE
)
2210 /* Additionally record the possibility of leaving the original iv
2212 def
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (data
->current_loop
));
2213 cand
= add_candidate_1 (data
,
2214 iv
->base
, iv
->step
, true, IP_ORIGINAL
, NULL
,
2215 SSA_NAME_DEF_STMT (def
));
2216 cand
->var_before
= iv
->ssa_name
;
2217 cand
->var_after
= def
;
2221 /* Adds candidates based on the old induction variables. */
2224 add_old_ivs_candidates (struct ivopts_data
*data
)
2230 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
2232 iv
= ver_info (data
, i
)->iv
;
2233 if (iv
&& iv
->biv_p
&& !integer_zerop (iv
->step
))
2234 add_old_iv_candidates (data
, iv
);
2238 /* Adds candidates based on the value of the induction variable IV and USE. */
2241 add_iv_value_candidates (struct ivopts_data
*data
,
2242 struct iv
*iv
, struct iv_use
*use
)
2244 unsigned HOST_WIDE_INT offset
;
2248 add_candidate (data
, iv
->base
, iv
->step
, false, use
);
2250 /* The same, but with initial value zero. Make such variable important,
2251 since it is generic enough so that possibly many uses may be based
2253 basetype
= TREE_TYPE (iv
->base
);
2254 if (POINTER_TYPE_P (basetype
))
2255 basetype
= sizetype
;
2256 add_candidate (data
, build_int_cst (basetype
, 0),
2257 iv
->step
, true, use
);
2259 /* Third, try removing the constant offset. */
2260 base
= strip_offset (iv
->base
, &offset
);
2262 add_candidate (data
, base
, iv
->step
, false, use
);
2265 /* Adds candidates based on the uses. */
2268 add_derived_ivs_candidates (struct ivopts_data
*data
)
2272 for (i
= 0; i
< n_iv_uses (data
); i
++)
2274 struct iv_use
*use
= iv_use (data
, i
);
2281 case USE_NONLINEAR_EXPR
:
2284 /* Just add the ivs based on the value of the iv used here. */
2285 add_iv_value_candidates (data
, use
->iv
, use
);
2294 /* Record important candidates and add them to related_cands bitmaps
2298 record_important_candidates (struct ivopts_data
*data
)
2303 for (i
= 0; i
< n_iv_cands (data
); i
++)
2305 struct iv_cand
*cand
= iv_cand (data
, i
);
2307 if (cand
->important
)
2308 bitmap_set_bit (data
->important_candidates
, i
);
2311 data
->consider_all_candidates
= (n_iv_cands (data
)
2312 <= CONSIDER_ALL_CANDIDATES_BOUND
);
2314 if (data
->consider_all_candidates
)
2316 /* We will not need "related_cands" bitmaps in this case,
2317 so release them to decrease peak memory consumption. */
2318 for (i
= 0; i
< n_iv_uses (data
); i
++)
2320 use
= iv_use (data
, i
);
2321 BITMAP_FREE (use
->related_cands
);
2326 /* Add important candidates to the related_cands bitmaps. */
2327 for (i
= 0; i
< n_iv_uses (data
); i
++)
2328 bitmap_ior_into (iv_use (data
, i
)->related_cands
,
2329 data
->important_candidates
);
2333 /* Finds the candidates for the induction variables. */
2336 find_iv_candidates (struct ivopts_data
*data
)
2338 /* Add commonly used ivs. */
2339 add_standard_iv_candidates (data
);
2341 /* Add old induction variables. */
2342 add_old_ivs_candidates (data
);
2344 /* Add induction variables derived from uses. */
2345 add_derived_ivs_candidates (data
);
2347 /* Record the important candidates. */
2348 record_important_candidates (data
);
2351 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
2352 If consider_all_candidates is true, we use a two-dimensional array, otherwise
2353 we allocate a simple list to every use. */
2356 alloc_use_cost_map (struct ivopts_data
*data
)
2358 unsigned i
, size
, s
, j
;
2360 for (i
= 0; i
< n_iv_uses (data
); i
++)
2362 struct iv_use
*use
= iv_use (data
, i
);
2365 if (data
->consider_all_candidates
)
2366 size
= n_iv_cands (data
);
2370 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, j
, bi
)
2375 /* Round up to the power of two, so that moduling by it is fast. */
2376 for (size
= 1; size
< s
; size
<<= 1)
2380 use
->n_map_members
= size
;
2381 use
->cost_map
= XCNEWVEC (struct cost_pair
, size
);
2385 /* Returns description of computation cost of expression whose runtime
2386 cost is RUNTIME and complexity corresponds to COMPLEXITY. */
2389 new_cost (unsigned runtime
, unsigned complexity
)
2393 cost
.cost
= runtime
;
2394 cost
.complexity
= complexity
;
2399 /* Adds costs COST1 and COST2. */
2402 add_costs (comp_cost cost1
, comp_cost cost2
)
2404 cost1
.cost
+= cost2
.cost
;
2405 cost1
.complexity
+= cost2
.complexity
;
2409 /* Subtracts costs COST1 and COST2. */
2412 sub_costs (comp_cost cost1
, comp_cost cost2
)
2414 cost1
.cost
-= cost2
.cost
;
2415 cost1
.complexity
-= cost2
.complexity
;
2420 /* Returns a negative number if COST1 < COST2, a positive number if
2421 COST1 > COST2, and 0 if COST1 = COST2. */
2424 compare_costs (comp_cost cost1
, comp_cost cost2
)
2426 if (cost1
.cost
== cost2
.cost
)
2427 return cost1
.complexity
- cost2
.complexity
;
2429 return cost1
.cost
- cost2
.cost
;
2432 /* Returns true if COST is infinite. */
2435 infinite_cost_p (comp_cost cost
)
2437 return cost
.cost
== INFTY
;
2440 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
2441 on invariants DEPENDS_ON and that the value used in expressing it
2445 set_use_iv_cost (struct ivopts_data
*data
,
2446 struct iv_use
*use
, struct iv_cand
*cand
,
2447 comp_cost cost
, bitmap depends_on
, tree value
)
2451 if (infinite_cost_p (cost
))
2453 BITMAP_FREE (depends_on
);
2457 if (data
->consider_all_candidates
)
2459 use
->cost_map
[cand
->id
].cand
= cand
;
2460 use
->cost_map
[cand
->id
].cost
= cost
;
2461 use
->cost_map
[cand
->id
].depends_on
= depends_on
;
2462 use
->cost_map
[cand
->id
].value
= value
;
2466 /* n_map_members is a power of two, so this computes modulo. */
2467 s
= cand
->id
& (use
->n_map_members
- 1);
2468 for (i
= s
; i
< use
->n_map_members
; i
++)
2469 if (!use
->cost_map
[i
].cand
)
2471 for (i
= 0; i
< s
; i
++)
2472 if (!use
->cost_map
[i
].cand
)
2478 use
->cost_map
[i
].cand
= cand
;
2479 use
->cost_map
[i
].cost
= cost
;
2480 use
->cost_map
[i
].depends_on
= depends_on
;
2481 use
->cost_map
[i
].value
= value
;
2484 /* Gets cost of (USE, CANDIDATE) pair. */
2486 static struct cost_pair
*
2487 get_use_iv_cost (struct ivopts_data
*data
, struct iv_use
*use
,
2488 struct iv_cand
*cand
)
2491 struct cost_pair
*ret
;
2496 if (data
->consider_all_candidates
)
2498 ret
= use
->cost_map
+ cand
->id
;
2505 /* n_map_members is a power of two, so this computes modulo. */
2506 s
= cand
->id
& (use
->n_map_members
- 1);
2507 for (i
= s
; i
< use
->n_map_members
; i
++)
2508 if (use
->cost_map
[i
].cand
== cand
)
2509 return use
->cost_map
+ i
;
2511 for (i
= 0; i
< s
; i
++)
2512 if (use
->cost_map
[i
].cand
== cand
)
2513 return use
->cost_map
+ i
;
2518 /* Returns estimate on cost of computing SEQ. */
2526 for (; seq
; seq
= NEXT_INSN (seq
))
2528 set
= single_set (seq
);
2530 cost
+= rtx_cost (set
, SET
);
2538 /* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
2540 produce_memory_decl_rtl (tree obj
, int *regno
)
2545 if (TREE_STATIC (obj
) || DECL_EXTERNAL (obj
))
2547 const char *name
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj
));
2548 x
= gen_rtx_SYMBOL_REF (Pmode
, name
);
2549 SET_SYMBOL_REF_DECL (x
, obj
);
2550 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
2551 targetm
.encode_section_info (obj
, x
, true);
2555 x
= gen_raw_REG (Pmode
, (*regno
)++);
2556 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
2562 /* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
2563 walk_tree. DATA contains the actual fake register number. */
2566 prepare_decl_rtl (tree
*expr_p
, int *ws
, void *data
)
2568 tree obj
= NULL_TREE
;
2570 int *regno
= (int *) data
;
2572 switch (TREE_CODE (*expr_p
))
2575 for (expr_p
= &TREE_OPERAND (*expr_p
, 0);
2576 handled_component_p (*expr_p
);
2577 expr_p
= &TREE_OPERAND (*expr_p
, 0))
2580 if (DECL_P (obj
) && !DECL_RTL_SET_P (obj
))
2581 x
= produce_memory_decl_rtl (obj
, regno
);
2586 obj
= SSA_NAME_VAR (*expr_p
);
2587 if (!DECL_RTL_SET_P (obj
))
2588 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2597 if (DECL_RTL_SET_P (obj
))
2600 if (DECL_MODE (obj
) == BLKmode
)
2601 x
= produce_memory_decl_rtl (obj
, regno
);
2603 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2613 VEC_safe_push (tree
, heap
, decl_rtl_to_reset
, obj
);
2614 SET_DECL_RTL (obj
, x
);
2620 /* Determines cost of the computation of EXPR. */
2623 computation_cost (tree expr
)
2626 tree type
= TREE_TYPE (expr
);
2628 /* Avoid using hard regs in ways which may be unsupported. */
2629 int regno
= LAST_VIRTUAL_REGISTER
+ 1;
2631 walk_tree (&expr
, prepare_decl_rtl
, ®no
, NULL
);
2633 rslt
= expand_expr (expr
, NULL_RTX
, TYPE_MODE (type
), EXPAND_NORMAL
);
2637 cost
= seq_cost (seq
);
2639 cost
+= address_cost (XEXP (rslt
, 0), TYPE_MODE (type
));
2644 /* Returns variable containing the value of candidate CAND at statement AT. */
2647 var_at_stmt (struct loop
*loop
, struct iv_cand
*cand
, tree stmt
)
2649 if (stmt_after_increment (loop
, cand
, stmt
))
2650 return cand
->var_after
;
2652 return cand
->var_before
;
2655 /* Return the most significant (sign) bit of T. Similar to tree_int_cst_msb,
2656 but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE. */
2659 tree_int_cst_sign_bit (const_tree t
)
2661 unsigned bitno
= TYPE_PRECISION (TREE_TYPE (t
)) - 1;
2662 unsigned HOST_WIDE_INT w
;
2664 if (bitno
< HOST_BITS_PER_WIDE_INT
)
2665 w
= TREE_INT_CST_LOW (t
);
2668 w
= TREE_INT_CST_HIGH (t
);
2669 bitno
-= HOST_BITS_PER_WIDE_INT
;
2672 return (w
>> bitno
) & 1;
2675 /* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
2676 same precision that is at least as wide as the precision of TYPE, stores
2677 BA to A and BB to B, and returns the type of BA. Otherwise, returns the
2681 determine_common_wider_type (tree
*a
, tree
*b
)
2683 tree wider_type
= NULL
;
2685 tree atype
= TREE_TYPE (*a
);
2687 if ((TREE_CODE (*a
) == NOP_EXPR
2688 || TREE_CODE (*a
) == CONVERT_EXPR
))
2690 suba
= TREE_OPERAND (*a
, 0);
2691 wider_type
= TREE_TYPE (suba
);
2692 if (TYPE_PRECISION (wider_type
) < TYPE_PRECISION (atype
))
2698 if ((TREE_CODE (*b
) == NOP_EXPR
2699 || TREE_CODE (*b
) == CONVERT_EXPR
))
2701 subb
= TREE_OPERAND (*b
, 0);
2702 if (TYPE_PRECISION (wider_type
) != TYPE_PRECISION (TREE_TYPE (subb
)))
2713 /* Determines the expression by that USE is expressed from induction variable
2714 CAND at statement AT in LOOP. The expression is stored in a decomposed
2715 form into AFF. Returns false if USE cannot be expressed using CAND. */
2718 get_computation_aff (struct loop
*loop
,
2719 struct iv_use
*use
, struct iv_cand
*cand
, tree at
,
2720 struct affine_tree_combination
*aff
)
2722 tree ubase
= use
->iv
->base
;
2723 tree ustep
= use
->iv
->step
;
2724 tree cbase
= cand
->iv
->base
;
2725 tree cstep
= cand
->iv
->step
, cstep_common
;
2726 tree utype
= TREE_TYPE (ubase
), ctype
= TREE_TYPE (cbase
);
2727 tree common_type
, var
;
2729 aff_tree cbase_aff
, var_aff
;
2732 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
2734 /* We do not have a precision to express the values of use. */
2738 var
= var_at_stmt (loop
, cand
, at
);
2739 uutype
= unsigned_type_for (utype
);
2741 /* If the conversion is not noop, perform it. */
2742 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
2744 cstep
= fold_convert (uutype
, cstep
);
2745 cbase
= fold_convert (uutype
, cbase
);
2746 var
= fold_convert (uutype
, var
);
2749 if (!constant_multiple_of (ustep
, cstep
, &rat
))
2752 /* In case both UBASE and CBASE are shortened to UUTYPE from some common
2753 type, we achieve better folding by computing their difference in this
2754 wider type, and cast the result to UUTYPE. We do not need to worry about
2755 overflows, as all the arithmetics will in the end be performed in UUTYPE
2757 common_type
= determine_common_wider_type (&ubase
, &cbase
);
2759 /* use = ubase - ratio * cbase + ratio * var. */
2760 tree_to_aff_combination (ubase
, common_type
, aff
);
2761 tree_to_aff_combination (cbase
, common_type
, &cbase_aff
);
2762 tree_to_aff_combination (var
, uutype
, &var_aff
);
2764 /* We need to shift the value if we are after the increment. */
2765 if (stmt_after_increment (loop
, cand
, at
))
2769 if (common_type
!= uutype
)
2770 cstep_common
= fold_convert (common_type
, cstep
);
2772 cstep_common
= cstep
;
2774 tree_to_aff_combination (cstep_common
, common_type
, &cstep_aff
);
2775 aff_combination_add (&cbase_aff
, &cstep_aff
);
2778 aff_combination_scale (&cbase_aff
, double_int_neg (rat
));
2779 aff_combination_add (aff
, &cbase_aff
);
2780 if (common_type
!= uutype
)
2781 aff_combination_convert (aff
, uutype
);
2783 aff_combination_scale (&var_aff
, rat
);
2784 aff_combination_add (aff
, &var_aff
);
2789 /* Determines the expression by that USE is expressed from induction variable
2790 CAND at statement AT in LOOP. The computation is unshared. */
2793 get_computation_at (struct loop
*loop
,
2794 struct iv_use
*use
, struct iv_cand
*cand
, tree at
)
2797 tree type
= TREE_TYPE (use
->iv
->base
);
2799 if (!get_computation_aff (loop
, use
, cand
, at
, &aff
))
2801 unshare_aff_combination (&aff
);
2802 return fold_convert (type
, aff_combination_to_tree (&aff
));
2805 /* Determines the expression by that USE is expressed from induction variable
2806 CAND in LOOP. The computation is unshared. */
2809 get_computation (struct loop
*loop
, struct iv_use
*use
, struct iv_cand
*cand
)
2811 return get_computation_at (loop
, use
, cand
, use
->stmt
);
2814 /* Returns cost of addition in MODE. */
2817 add_cost (enum machine_mode mode
)
2819 static unsigned costs
[NUM_MACHINE_MODES
];
2827 force_operand (gen_rtx_fmt_ee (PLUS
, mode
,
2828 gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 1),
2829 gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 2)),
2834 cost
= seq_cost (seq
);
2840 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2841 fprintf (dump_file
, "Addition in %s costs %d\n",
2842 GET_MODE_NAME (mode
), cost
);
2846 /* Entry in a hashtable of already known costs for multiplication. */
2849 HOST_WIDE_INT cst
; /* The constant to multiply by. */
2850 enum machine_mode mode
; /* In mode. */
2851 unsigned cost
; /* The cost. */
2854 /* Counts hash value for the ENTRY. */
2857 mbc_entry_hash (const void *entry
)
2859 const struct mbc_entry
*e
= (const struct mbc_entry
*) entry
;
2861 return 57 * (hashval_t
) e
->mode
+ (hashval_t
) (e
->cst
% 877);
2864 /* Compares the hash table entries ENTRY1 and ENTRY2. */
2867 mbc_entry_eq (const void *entry1
, const void *entry2
)
2869 const struct mbc_entry
*e1
= (const struct mbc_entry
*) entry1
;
2870 const struct mbc_entry
*e2
= (const struct mbc_entry
*) entry2
;
2872 return (e1
->mode
== e2
->mode
2873 && e1
->cst
== e2
->cst
);
2876 /* Returns cost of multiplication by constant CST in MODE. */
2879 multiply_by_cost (HOST_WIDE_INT cst
, enum machine_mode mode
)
2881 static htab_t costs
;
2882 struct mbc_entry
**cached
, act
;
2887 costs
= htab_create (100, mbc_entry_hash
, mbc_entry_eq
, free
);
2891 cached
= (struct mbc_entry
**) htab_find_slot (costs
, &act
, INSERT
);
2893 return (*cached
)->cost
;
2895 *cached
= XNEW (struct mbc_entry
);
2896 (*cached
)->mode
= mode
;
2897 (*cached
)->cst
= cst
;
2900 expand_mult (mode
, gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 1),
2901 gen_int_mode (cst
, mode
), NULL_RTX
, 0);
2905 cost
= seq_cost (seq
);
2907 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2908 fprintf (dump_file
, "Multiplication by %d in %s costs %d\n",
2909 (int) cst
, GET_MODE_NAME (mode
), cost
);
2911 (*cached
)->cost
= cost
;
2916 /* Returns true if multiplying by RATIO is allowed in an address. Test the
2917 validity for a memory reference accessing memory of mode MODE. */
2920 multiplier_allowed_in_address_p (HOST_WIDE_INT ratio
, enum machine_mode mode
)
2922 #define MAX_RATIO 128
2923 static sbitmap valid_mult
[MAX_MACHINE_MODE
];
2925 if (!valid_mult
[mode
])
2927 rtx reg1
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 1);
2931 valid_mult
[mode
] = sbitmap_alloc (2 * MAX_RATIO
+ 1);
2932 sbitmap_zero (valid_mult
[mode
]);
2933 addr
= gen_rtx_fmt_ee (MULT
, Pmode
, reg1
, NULL_RTX
);
2934 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
2936 XEXP (addr
, 1) = gen_int_mode (i
, Pmode
);
2937 if (memory_address_p (mode
, addr
))
2938 SET_BIT (valid_mult
[mode
], i
+ MAX_RATIO
);
2941 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2943 fprintf (dump_file
, " allowed multipliers:");
2944 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
2945 if (TEST_BIT (valid_mult
[mode
], i
+ MAX_RATIO
))
2946 fprintf (dump_file
, " %d", (int) i
);
2947 fprintf (dump_file
, "\n");
2948 fprintf (dump_file
, "\n");
2952 if (ratio
> MAX_RATIO
|| ratio
< -MAX_RATIO
)
2955 return TEST_BIT (valid_mult
[mode
], ratio
+ MAX_RATIO
);
2958 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
2959 If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
2960 variable is omitted. Compute the cost for a memory reference that accesses
2961 a memory location of mode MEM_MODE.
2963 TODO -- there must be some better way. This all is quite crude. */
2966 get_address_cost (bool symbol_present
, bool var_present
,
2967 unsigned HOST_WIDE_INT offset
, HOST_WIDE_INT ratio
,
2968 enum machine_mode mem_mode
)
2970 static bool initialized
[MAX_MACHINE_MODE
];
2971 static HOST_WIDE_INT rat
[MAX_MACHINE_MODE
], off
[MAX_MACHINE_MODE
];
2972 static HOST_WIDE_INT min_offset
[MAX_MACHINE_MODE
], max_offset
[MAX_MACHINE_MODE
];
2973 static unsigned costs
[MAX_MACHINE_MODE
][2][2][2][2];
2974 unsigned cost
, acost
, complexity
;
2975 bool offset_p
, ratio_p
;
2976 HOST_WIDE_INT s_offset
;
2977 unsigned HOST_WIDE_INT mask
;
2980 if (!initialized
[mem_mode
])
2983 HOST_WIDE_INT start
= BIGGEST_ALIGNMENT
/ BITS_PER_UNIT
;
2984 int old_cse_not_expected
;
2985 unsigned sym_p
, var_p
, off_p
, rat_p
, add_c
;
2986 rtx seq
, addr
, base
;
2989 initialized
[mem_mode
] = true;
2991 reg1
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 1);
2993 addr
= gen_rtx_fmt_ee (PLUS
, Pmode
, reg1
, NULL_RTX
);
2994 for (i
= start
; i
<= 1 << 20; i
<<= 1)
2996 XEXP (addr
, 1) = gen_int_mode (i
, Pmode
);
2997 if (!memory_address_p (mem_mode
, addr
))
3000 max_offset
[mem_mode
] = i
== start
? 0 : i
>> 1;
3001 off
[mem_mode
] = max_offset
[mem_mode
];
3003 for (i
= start
; i
<= 1 << 20; i
<<= 1)
3005 XEXP (addr
, 1) = gen_int_mode (-i
, Pmode
);
3006 if (!memory_address_p (mem_mode
, addr
))
3009 min_offset
[mem_mode
] = i
== start
? 0 : -(i
>> 1);
3011 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3013 fprintf (dump_file
, "get_address_cost:\n");
3014 fprintf (dump_file
, " min offset %s %d\n",
3015 GET_MODE_NAME (mem_mode
),
3016 (int) min_offset
[mem_mode
]);
3017 fprintf (dump_file
, " max offset %s %d\n",
3018 GET_MODE_NAME (mem_mode
),
3019 (int) max_offset
[mem_mode
]);
3023 for (i
= 2; i
<= MAX_RATIO
; i
++)
3024 if (multiplier_allowed_in_address_p (i
, mem_mode
))
3030 /* Compute the cost of various addressing modes. */
3032 reg0
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 1);
3033 reg1
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 2);
3035 for (i
= 0; i
< 16; i
++)
3038 var_p
= (i
>> 1) & 1;
3039 off_p
= (i
>> 2) & 1;
3040 rat_p
= (i
>> 3) & 1;
3044 addr
= gen_rtx_fmt_ee (MULT
, Pmode
, addr
,
3045 gen_int_mode (rat
[mem_mode
], Pmode
));
3048 addr
= gen_rtx_fmt_ee (PLUS
, Pmode
, addr
, reg1
);
3052 base
= gen_rtx_SYMBOL_REF (Pmode
, ggc_strdup (""));
3053 /* ??? We can run into trouble with some backends by presenting
3054 it with symbols which havn't been properly passed through
3055 targetm.encode_section_info. By setting the local bit, we
3056 enhance the probability of things working. */
3057 SYMBOL_REF_FLAGS (base
) = SYMBOL_FLAG_LOCAL
;
3060 base
= gen_rtx_fmt_e (CONST
, Pmode
,
3061 gen_rtx_fmt_ee (PLUS
, Pmode
,
3063 gen_int_mode (off
[mem_mode
],
3067 base
= gen_int_mode (off
[mem_mode
], Pmode
);
3072 addr
= gen_rtx_fmt_ee (PLUS
, Pmode
, addr
, base
);
3075 /* To avoid splitting addressing modes, pretend that no cse will
3077 old_cse_not_expected
= cse_not_expected
;
3078 cse_not_expected
= true;
3079 addr
= memory_address (mem_mode
, addr
);
3080 cse_not_expected
= old_cse_not_expected
;
3084 acost
= seq_cost (seq
);
3085 acost
+= address_cost (addr
, mem_mode
);
3089 costs
[mem_mode
][sym_p
][var_p
][off_p
][rat_p
] = acost
;
3092 /* On some targets, it is quite expensive to load symbol to a register,
3093 which makes addresses that contain symbols look much more expensive.
3094 However, the symbol will have to be loaded in any case before the
3095 loop (and quite likely we have it in register already), so it does not
3096 make much sense to penalize them too heavily. So make some final
3097 tweaks for the SYMBOL_PRESENT modes:
3099 If VAR_PRESENT is false, and the mode obtained by changing symbol to
3100 var is cheaper, use this mode with small penalty.
3101 If VAR_PRESENT is true, try whether the mode with
3102 SYMBOL_PRESENT = false is cheaper even with cost of addition, and
3103 if this is the case, use it. */
3104 add_c
= add_cost (Pmode
);
3105 for (i
= 0; i
< 8; i
++)
3108 off_p
= (i
>> 1) & 1;
3109 rat_p
= (i
>> 2) & 1;
3111 acost
= costs
[mem_mode
][0][1][off_p
][rat_p
] + 1;
3115 if (acost
< costs
[mem_mode
][1][var_p
][off_p
][rat_p
])
3116 costs
[mem_mode
][1][var_p
][off_p
][rat_p
] = acost
;
3119 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3121 fprintf (dump_file
, "Address costs:\n");
3123 for (i
= 0; i
< 16; i
++)
3126 var_p
= (i
>> 1) & 1;
3127 off_p
= (i
>> 2) & 1;
3128 rat_p
= (i
>> 3) & 1;
3130 fprintf (dump_file
, " ");
3132 fprintf (dump_file
, "sym + ");
3134 fprintf (dump_file
, "var + ");
3136 fprintf (dump_file
, "cst + ");
3138 fprintf (dump_file
, "rat * ");
3140 acost
= costs
[mem_mode
][sym_p
][var_p
][off_p
][rat_p
];
3141 fprintf (dump_file
, "index costs %d\n", acost
);
3143 fprintf (dump_file
, "\n");
3147 bits
= GET_MODE_BITSIZE (Pmode
);
3148 mask
= ~(~(unsigned HOST_WIDE_INT
) 0 << (bits
- 1) << 1);
3150 if ((offset
>> (bits
- 1) & 1))
3155 offset_p
= (s_offset
!= 0
3156 && min_offset
[mem_mode
] <= s_offset
3157 && s_offset
<= max_offset
[mem_mode
]);
3158 ratio_p
= (ratio
!= 1
3159 && multiplier_allowed_in_address_p (ratio
, mem_mode
));
3161 if (ratio
!= 1 && !ratio_p
)
3162 cost
+= multiply_by_cost (ratio
, Pmode
);
3164 if (s_offset
&& !offset_p
&& !symbol_present
)
3165 cost
+= add_cost (Pmode
);
3167 acost
= costs
[mem_mode
][symbol_present
][var_present
][offset_p
][ratio_p
];
3168 complexity
= (symbol_present
!= 0) + (var_present
!= 0) + offset_p
+ ratio_p
;
3169 return new_cost (cost
+ acost
, complexity
);
3172 /* Estimates cost of forcing expression EXPR into a variable. */
3175 force_expr_to_var_cost (tree expr
)
3177 static bool costs_initialized
= false;
3178 static unsigned integer_cost
;
3179 static unsigned symbol_cost
;
3180 static unsigned address_cost
;
3182 comp_cost cost0
, cost1
, cost
;
3183 enum machine_mode mode
;
3185 if (!costs_initialized
)
3187 tree type
= build_pointer_type (integer_type_node
);
3191 var
= create_tmp_var_raw (integer_type_node
, "test_var");
3192 TREE_STATIC (var
) = 1;
3193 x
= produce_memory_decl_rtl (var
, NULL
);
3194 SET_DECL_RTL (var
, x
);
3196 integer_cost
= computation_cost (build_int_cst (integer_type_node
,
3199 addr
= build1 (ADDR_EXPR
, type
, var
);
3200 symbol_cost
= computation_cost (addr
) + 1;
3203 = computation_cost (build2 (POINTER_PLUS_EXPR
, type
,
3205 build_int_cst (sizetype
, 2000))) + 1;
3206 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3208 fprintf (dump_file
, "force_expr_to_var_cost:\n");
3209 fprintf (dump_file
, " integer %d\n", (int) integer_cost
);
3210 fprintf (dump_file
, " symbol %d\n", (int) symbol_cost
);
3211 fprintf (dump_file
, " address %d\n", (int) address_cost
);
3212 fprintf (dump_file
, " other %d\n", (int) target_spill_cost
);
3213 fprintf (dump_file
, "\n");
3216 costs_initialized
= true;
3221 if (SSA_VAR_P (expr
))
3224 if (is_gimple_min_invariant (expr
))
3226 if (TREE_CODE (expr
) == INTEGER_CST
)
3227 return new_cost (integer_cost
, 0);
3229 if (TREE_CODE (expr
) == ADDR_EXPR
)
3231 tree obj
= TREE_OPERAND (expr
, 0);
3233 if (TREE_CODE (obj
) == VAR_DECL
3234 || TREE_CODE (obj
) == PARM_DECL
3235 || TREE_CODE (obj
) == RESULT_DECL
)
3236 return new_cost (symbol_cost
, 0);
3239 return new_cost (address_cost
, 0);
3242 switch (TREE_CODE (expr
))
3244 case POINTER_PLUS_EXPR
:
3248 op0
= TREE_OPERAND (expr
, 0);
3249 op1
= TREE_OPERAND (expr
, 1);
3253 if (is_gimple_val (op0
))
3256 cost0
= force_expr_to_var_cost (op0
);
3258 if (is_gimple_val (op1
))
3261 cost1
= force_expr_to_var_cost (op1
);
3266 /* Just an arbitrary value, FIXME. */
3267 return new_cost (target_spill_cost
, 0);
3270 mode
= TYPE_MODE (TREE_TYPE (expr
));
3271 switch (TREE_CODE (expr
))
3273 case POINTER_PLUS_EXPR
:
3276 cost
= new_cost (add_cost (mode
), 0);
3280 if (cst_and_fits_in_hwi (op0
))
3281 cost
= new_cost (multiply_by_cost (int_cst_value (op0
), mode
), 0);
3282 else if (cst_and_fits_in_hwi (op1
))
3283 cost
= new_cost (multiply_by_cost (int_cst_value (op1
), mode
), 0);
3285 return new_cost (target_spill_cost
, 0);
3292 cost
= add_costs (cost
, cost0
);
3293 cost
= add_costs (cost
, cost1
);
3295 /* Bound the cost by target_spill_cost. The parts of complicated
3296 computations often are either loop invariant or at least can
3297 be shared between several iv uses, so letting this grow without
3298 limits would not give reasonable results. */
3299 if (cost
.cost
> target_spill_cost
)
3300 cost
.cost
= target_spill_cost
;
3305 /* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
3306 invariants the computation depends on. */
3309 force_var_cost (struct ivopts_data
*data
,
3310 tree expr
, bitmap
*depends_on
)
3314 fd_ivopts_data
= data
;
3315 walk_tree (&expr
, find_depends
, depends_on
, NULL
);
3318 return force_expr_to_var_cost (expr
);
3321 /* Estimates cost of expressing address ADDR as var + symbol + offset. The
3322 value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
3323 to false if the corresponding part is missing. DEPENDS_ON is a set of the
3324 invariants the computation depends on. */
3327 split_address_cost (struct ivopts_data
*data
,
3328 tree addr
, bool *symbol_present
, bool *var_present
,
3329 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3332 HOST_WIDE_INT bitsize
;
3333 HOST_WIDE_INT bitpos
;
3335 enum machine_mode mode
;
3336 int unsignedp
, volatilep
;
3338 core
= get_inner_reference (addr
, &bitsize
, &bitpos
, &toffset
, &mode
,
3339 &unsignedp
, &volatilep
, false);
3342 || bitpos
% BITS_PER_UNIT
!= 0
3343 || TREE_CODE (core
) != VAR_DECL
)
3345 *symbol_present
= false;
3346 *var_present
= true;
3347 fd_ivopts_data
= data
;
3348 walk_tree (&addr
, find_depends
, depends_on
, NULL
);
3349 return new_cost (target_spill_cost
, 0);
3352 *offset
+= bitpos
/ BITS_PER_UNIT
;
3353 if (TREE_STATIC (core
)
3354 || DECL_EXTERNAL (core
))
3356 *symbol_present
= true;
3357 *var_present
= false;
3361 *symbol_present
= false;
3362 *var_present
= true;
3366 /* Estimates cost of expressing difference of addresses 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 ptr_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
)
3377 HOST_WIDE_INT diff
= 0;
3380 gcc_assert (TREE_CODE (e1
) == ADDR_EXPR
);
3382 if (ptr_difference_const (e1
, e2
, &diff
))
3385 *symbol_present
= false;
3386 *var_present
= false;
3390 if (integer_zerop (e2
))
3391 return split_address_cost (data
, TREE_OPERAND (e1
, 0),
3392 symbol_present
, var_present
, offset
, depends_on
);
3394 *symbol_present
= false;
3395 *var_present
= true;
3397 cost
= force_var_cost (data
, e1
, depends_on
);
3398 cost
= add_costs (cost
, force_var_cost (data
, e2
, depends_on
));
3399 cost
.cost
+= add_cost (Pmode
);
3404 /* Estimates cost of expressing difference E1 - E2 as
3405 var + symbol + offset. The value of offset is added to OFFSET,
3406 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3407 part is missing. DEPENDS_ON is a set of the invariants the computation
3411 difference_cost (struct ivopts_data
*data
,
3412 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
3413 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3416 enum machine_mode mode
= TYPE_MODE (TREE_TYPE (e1
));
3417 unsigned HOST_WIDE_INT off1
, off2
;
3419 e1
= strip_offset (e1
, &off1
);
3420 e2
= strip_offset (e2
, &off2
);
3421 *offset
+= off1
- off2
;
3426 if (TREE_CODE (e1
) == ADDR_EXPR
)
3427 return ptr_difference_cost (data
, e1
, e2
, symbol_present
, var_present
, offset
,
3429 *symbol_present
= false;
3431 if (operand_equal_p (e1
, e2
, 0))
3433 *var_present
= false;
3436 *var_present
= true;
3437 if (integer_zerop (e2
))
3438 return force_var_cost (data
, e1
, depends_on
);
3440 if (integer_zerop (e1
))
3442 cost
= force_var_cost (data
, e2
, depends_on
);
3443 cost
.cost
+= multiply_by_cost (-1, mode
);
3448 cost
= force_var_cost (data
, e1
, depends_on
);
3449 cost
= add_costs (cost
, force_var_cost (data
, e2
, depends_on
));
3450 cost
.cost
+= add_cost (mode
);
3455 /* Determines the cost of the computation by that USE is expressed
3456 from induction variable CAND. If ADDRESS_P is true, we just need
3457 to create an address from it, otherwise we want to get it into
3458 register. A set of invariants we depend on is stored in
3459 DEPENDS_ON. AT is the statement at that the value is computed. */
3462 get_computation_cost_at (struct ivopts_data
*data
,
3463 struct iv_use
*use
, struct iv_cand
*cand
,
3464 bool address_p
, bitmap
*depends_on
, tree at
)
3466 tree ubase
= use
->iv
->base
, ustep
= use
->iv
->step
;
3468 tree utype
= TREE_TYPE (ubase
), ctype
;
3469 unsigned HOST_WIDE_INT cstepi
, offset
= 0;
3470 HOST_WIDE_INT ratio
, aratio
;
3471 bool var_present
, symbol_present
;
3478 /* Only consider real candidates. */
3480 return infinite_cost
;
3482 cbase
= cand
->iv
->base
;
3483 cstep
= cand
->iv
->step
;
3484 ctype
= TREE_TYPE (cbase
);
3486 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
3488 /* We do not have a precision to express the values of use. */
3489 return infinite_cost
;
3494 /* Do not try to express address of an object with computation based
3495 on address of a different object. This may cause problems in rtl
3496 level alias analysis (that does not expect this to be happening,
3497 as this is illegal in C), and would be unlikely to be useful
3499 if (use
->iv
->base_object
3500 && cand
->iv
->base_object
3501 && !operand_equal_p (use
->iv
->base_object
, cand
->iv
->base_object
, 0))
3502 return infinite_cost
;
3505 if (TYPE_PRECISION (utype
) != TYPE_PRECISION (ctype
))
3507 /* TODO -- add direct handling of this case. */
3511 /* CSTEPI is removed from the offset in case statement is after the
3512 increment. If the step is not constant, we use zero instead.
3513 This is a bit imprecise (there is the extra addition), but
3514 redundancy elimination is likely to transform the code so that
3515 it uses value of the variable before increment anyway,
3516 so it is not that much unrealistic. */
3517 if (cst_and_fits_in_hwi (cstep
))
3518 cstepi
= int_cst_value (cstep
);
3522 if (!constant_multiple_of (ustep
, cstep
, &rat
))
3523 return infinite_cost
;
3525 if (double_int_fits_in_shwi_p (rat
))
3526 ratio
= double_int_to_shwi (rat
);
3528 return infinite_cost
;
3530 /* use = ubase + ratio * (var - cbase). If either cbase is a constant
3531 or ratio == 1, it is better to handle this like
3533 ubase - ratio * cbase + ratio * var
3535 (also holds in the case ratio == -1, TODO. */
3537 if (cst_and_fits_in_hwi (cbase
))
3539 offset
= - ratio
* int_cst_value (cbase
);
3540 cost
= difference_cost (data
,
3541 ubase
, build_int_cst (utype
, 0),
3542 &symbol_present
, &var_present
, &offset
,
3545 else if (ratio
== 1)
3547 cost
= difference_cost (data
,
3549 &symbol_present
, &var_present
, &offset
,
3554 cost
= force_var_cost (data
, cbase
, depends_on
);
3555 cost
.cost
+= add_cost (TYPE_MODE (ctype
));
3556 cost
= add_costs (cost
,
3557 difference_cost (data
,
3558 ubase
, build_int_cst (utype
, 0),
3559 &symbol_present
, &var_present
,
3560 &offset
, depends_on
));
3563 /* If we are after the increment, the value of the candidate is higher by
3565 if (stmt_after_increment (data
->current_loop
, cand
, at
))
3566 offset
-= ratio
* cstepi
;
3568 /* Now the computation is in shape symbol + var1 + const + ratio * var2.
3569 (symbol/var/const parts may be omitted). If we are looking for an address,
3570 find the cost of addressing this. */
3572 return add_costs (cost
, get_address_cost (symbol_present
, var_present
,
3574 TYPE_MODE (TREE_TYPE (*use
->op_p
))));
3576 /* Otherwise estimate the costs for computing the expression. */
3577 aratio
= ratio
> 0 ? ratio
: -ratio
;
3578 if (!symbol_present
&& !var_present
&& !offset
)
3581 cost
.cost
+= multiply_by_cost (ratio
, TYPE_MODE (ctype
));
3587 cost
.cost
+= multiply_by_cost (aratio
, TYPE_MODE (ctype
));
3591 /* Symbol + offset should be compile-time computable. */
3592 && (symbol_present
|| offset
))
3595 /* Having offset does not affect runtime cost in case it is added to
3596 symbol, but it increases complexity. */
3600 cost
.cost
+= n_sums
* add_cost (TYPE_MODE (ctype
));
3605 /* Just get the expression, expand it and measure the cost. */
3606 tree comp
= get_computation_at (data
->current_loop
, use
, cand
, at
);
3609 return infinite_cost
;
3612 comp
= build1 (INDIRECT_REF
, TREE_TYPE (TREE_TYPE (comp
)), comp
);
3614 return new_cost (computation_cost (comp
), 0);
3618 /* Determines the cost of the computation by that USE is expressed
3619 from induction variable CAND. If ADDRESS_P is true, we just need
3620 to create an address from it, otherwise we want to get it into
3621 register. A set of invariants we depend on is stored in
3625 get_computation_cost (struct ivopts_data
*data
,
3626 struct iv_use
*use
, struct iv_cand
*cand
,
3627 bool address_p
, bitmap
*depends_on
)
3629 return get_computation_cost_at (data
,
3630 use
, cand
, address_p
, depends_on
, use
->stmt
);
3633 /* Determines cost of basing replacement of USE on CAND in a generic
3637 determine_use_iv_cost_generic (struct ivopts_data
*data
,
3638 struct iv_use
*use
, struct iv_cand
*cand
)
3643 /* The simple case first -- if we need to express value of the preserved
3644 original biv, the cost is 0. This also prevents us from counting the
3645 cost of increment twice -- once at this use and once in the cost of
3647 if (cand
->pos
== IP_ORIGINAL
3648 && cand
->incremented_at
== use
->stmt
)
3650 set_use_iv_cost (data
, use
, cand
, zero_cost
, NULL
, NULL_TREE
);
3654 cost
= get_computation_cost (data
, use
, cand
, false, &depends_on
);
3655 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
);
3657 return !infinite_cost_p (cost
);
3660 /* Determines cost of basing replacement of USE on CAND in an address. */
3663 determine_use_iv_cost_address (struct ivopts_data
*data
,
3664 struct iv_use
*use
, struct iv_cand
*cand
)
3667 comp_cost cost
= get_computation_cost (data
, use
, cand
, true, &depends_on
);
3669 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
);
3671 return !infinite_cost_p (cost
);
3674 /* Computes value of candidate CAND at position AT in iteration NITER, and
3675 stores it to VAL. */
3678 cand_value_at (struct loop
*loop
, struct iv_cand
*cand
, tree at
, tree niter
,
3681 aff_tree step
, delta
, nit
;
3682 struct iv
*iv
= cand
->iv
;
3683 tree type
= TREE_TYPE (iv
->base
);
3684 tree steptype
= type
;
3685 if (POINTER_TYPE_P (type
))
3686 steptype
= sizetype
;
3688 tree_to_aff_combination (iv
->step
, steptype
, &step
);
3689 tree_to_aff_combination (niter
, TREE_TYPE (niter
), &nit
);
3690 aff_combination_convert (&nit
, steptype
);
3691 aff_combination_mult (&nit
, &step
, &delta
);
3692 if (stmt_after_increment (loop
, cand
, at
))
3693 aff_combination_add (&delta
, &step
);
3695 tree_to_aff_combination (iv
->base
, type
, val
);
3696 aff_combination_add (val
, &delta
);
3699 /* Returns period of induction variable iv. */
3702 iv_period (struct iv
*iv
)
3704 tree step
= iv
->step
, period
, type
;
3707 gcc_assert (step
&& TREE_CODE (step
) == INTEGER_CST
);
3709 /* Period of the iv is gcd (step, type range). Since type range is power
3710 of two, it suffices to determine the maximum power of two that divides
3712 pow2div
= num_ending_zeros (step
);
3713 type
= unsigned_type_for (TREE_TYPE (step
));
3715 period
= build_low_bits_mask (type
,
3716 (TYPE_PRECISION (type
)
3717 - tree_low_cst (pow2div
, 1)));
3722 /* Returns the comparison operator used when eliminating the iv USE. */
3724 static enum tree_code
3725 iv_elimination_compare (struct ivopts_data
*data
, struct iv_use
*use
)
3727 struct loop
*loop
= data
->current_loop
;
3731 ex_bb
= bb_for_stmt (use
->stmt
);
3732 exit
= EDGE_SUCC (ex_bb
, 0);
3733 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
3734 exit
= EDGE_SUCC (ex_bb
, 1);
3736 return (exit
->flags
& EDGE_TRUE_VALUE
? EQ_EXPR
: NE_EXPR
);
3739 /* Check whether it is possible to express the condition in USE by comparison
3740 of candidate CAND. If so, store the value compared with to BOUND. */
3743 may_eliminate_iv (struct ivopts_data
*data
,
3744 struct iv_use
*use
, struct iv_cand
*cand
, tree
*bound
)
3749 struct loop
*loop
= data
->current_loop
;
3751 double_int period_value
, max_niter
;
3753 if (TREE_CODE (cand
->iv
->step
) != INTEGER_CST
)
3756 /* For now works only for exits that dominate the loop latch. TODO -- extend
3757 for other conditions inside loop body. */
3758 ex_bb
= bb_for_stmt (use
->stmt
);
3759 if (use
->stmt
!= last_stmt (ex_bb
)
3760 || TREE_CODE (use
->stmt
) != COND_EXPR
)
3762 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, ex_bb
))
3765 exit
= EDGE_SUCC (ex_bb
, 0);
3766 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
3767 exit
= EDGE_SUCC (ex_bb
, 1);
3768 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
3771 nit
= niter_for_exit (data
, exit
);
3775 /* Determine whether we may use the variable to test whether niter iterations
3776 elapsed. This is the case iff the period of the induction variable is
3777 greater than the number of iterations. */
3778 period
= iv_period (cand
->iv
);
3782 /* Compare the period with the estimate on the number of iterations of the
3784 if (!estimated_loop_iterations (loop
, true, &max_niter
))
3786 period_value
= tree_to_double_int (period
);
3787 if (double_int_ucmp (period_value
, max_niter
) <= 0)
3790 cand_value_at (loop
, cand
, use
->stmt
, nit
, &bnd
);
3791 *bound
= aff_combination_to_tree (&bnd
);
3795 /* Determines cost of basing replacement of USE on CAND in a condition. */
3798 determine_use_iv_cost_condition (struct ivopts_data
*data
,
3799 struct iv_use
*use
, struct iv_cand
*cand
)
3801 tree bound
= NULL_TREE
;
3803 bitmap depends_on_elim
= NULL
, depends_on_express
= NULL
, depends_on
;
3804 comp_cost elim_cost
, express_cost
, cost
;
3807 /* Only consider real candidates. */
3810 set_use_iv_cost (data
, use
, cand
, infinite_cost
, NULL
, NULL_TREE
);
3814 /* Try iv elimination. */
3815 if (may_eliminate_iv (data
, use
, cand
, &bound
))
3817 elim_cost
= force_var_cost (data
, bound
, &depends_on_elim
);
3818 /* The bound is a loop invariant, so it will be only computed
3820 elim_cost
.cost
/= AVG_LOOP_NITER (data
->current_loop
);
3823 elim_cost
= infinite_cost
;
3825 /* Try expressing the original giv. If it is compared with an invariant,
3826 note that we cannot get rid of it. */
3827 ok
= extract_cond_operands (data
, use
->op_p
, NULL
, NULL
, NULL
, &cmp_iv
);
3830 express_cost
= get_computation_cost (data
, use
, cand
, false,
3831 &depends_on_express
);
3832 fd_ivopts_data
= data
;
3833 walk_tree (&cmp_iv
->base
, find_depends
, &depends_on_express
, NULL
);
3835 /* Choose the better approach. */
3836 if (compare_costs (elim_cost
, express_cost
) < 0)
3839 depends_on
= depends_on_elim
;
3840 depends_on_elim
= NULL
;
3844 cost
= express_cost
;
3845 depends_on
= depends_on_express
;
3846 depends_on_express
= NULL
;
3850 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, bound
);
3852 if (depends_on_elim
)
3853 BITMAP_FREE (depends_on_elim
);
3854 if (depends_on_express
)
3855 BITMAP_FREE (depends_on_express
);
3857 return !infinite_cost_p (cost
);
3860 /* Determines cost of basing replacement of USE on CAND. Returns false
3861 if USE cannot be based on CAND. */
3864 determine_use_iv_cost (struct ivopts_data
*data
,
3865 struct iv_use
*use
, struct iv_cand
*cand
)
3869 case USE_NONLINEAR_EXPR
:
3870 return determine_use_iv_cost_generic (data
, use
, cand
);
3873 return determine_use_iv_cost_address (data
, use
, cand
);
3876 return determine_use_iv_cost_condition (data
, use
, cand
);
3883 /* Determines costs of basing the use of the iv on an iv candidate. */
3886 determine_use_iv_costs (struct ivopts_data
*data
)
3890 struct iv_cand
*cand
;
3891 bitmap to_clear
= BITMAP_ALLOC (NULL
);
3893 alloc_use_cost_map (data
);
3895 for (i
= 0; i
< n_iv_uses (data
); i
++)
3897 use
= iv_use (data
, i
);
3899 if (data
->consider_all_candidates
)
3901 for (j
= 0; j
< n_iv_cands (data
); j
++)
3903 cand
= iv_cand (data
, j
);
3904 determine_use_iv_cost (data
, use
, cand
);
3911 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, j
, bi
)
3913 cand
= iv_cand (data
, j
);
3914 if (!determine_use_iv_cost (data
, use
, cand
))
3915 bitmap_set_bit (to_clear
, j
);
3918 /* Remove the candidates for that the cost is infinite from
3919 the list of related candidates. */
3920 bitmap_and_compl_into (use
->related_cands
, to_clear
);
3921 bitmap_clear (to_clear
);
3925 BITMAP_FREE (to_clear
);
3927 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3929 fprintf (dump_file
, "Use-candidate costs:\n");
3931 for (i
= 0; i
< n_iv_uses (data
); i
++)
3933 use
= iv_use (data
, i
);
3935 fprintf (dump_file
, "Use %d:\n", i
);
3936 fprintf (dump_file
, " cand\tcost\tcompl.\tdepends on\n");
3937 for (j
= 0; j
< use
->n_map_members
; j
++)
3939 if (!use
->cost_map
[j
].cand
3940 || infinite_cost_p (use
->cost_map
[j
].cost
))
3943 fprintf (dump_file
, " %d\t%d\t%d\t",
3944 use
->cost_map
[j
].cand
->id
,
3945 use
->cost_map
[j
].cost
.cost
,
3946 use
->cost_map
[j
].cost
.complexity
);
3947 if (use
->cost_map
[j
].depends_on
)
3948 bitmap_print (dump_file
,
3949 use
->cost_map
[j
].depends_on
, "","");
3950 fprintf (dump_file
, "\n");
3953 fprintf (dump_file
, "\n");
3955 fprintf (dump_file
, "\n");
3959 /* Determines cost of the candidate CAND. */
3962 determine_iv_cost (struct ivopts_data
*data
, struct iv_cand
*cand
)
3964 comp_cost cost_base
;
3965 unsigned cost
, cost_step
;
3974 /* There are two costs associated with the candidate -- its increment
3975 and its initialization. The second is almost negligible for any loop
3976 that rolls enough, so we take it just very little into account. */
3978 base
= cand
->iv
->base
;
3979 cost_base
= force_var_cost (data
, base
, NULL
);
3980 cost_step
= add_cost (TYPE_MODE (TREE_TYPE (base
)));
3982 cost
= cost_step
+ cost_base
.cost
/ AVG_LOOP_NITER (current_loop
);
3984 /* Prefer the original ivs unless we may gain something by replacing it.
3985 The reason is to makee debugging simpler; so this is not relevant for
3986 artificial ivs created by other optimization passes. */
3987 if (cand
->pos
!= IP_ORIGINAL
3988 || DECL_ARTIFICIAL (SSA_NAME_VAR (cand
->var_before
)))
3991 /* Prefer not to insert statements into latch unless there are some
3992 already (so that we do not create unnecessary jumps). */
3993 if (cand
->pos
== IP_END
3994 && empty_block_p (ip_end_pos (data
->current_loop
)))
4000 /* Determines costs of computation of the candidates. */
4003 determine_iv_costs (struct ivopts_data
*data
)
4007 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4009 fprintf (dump_file
, "Candidate costs:\n");
4010 fprintf (dump_file
, " cand\tcost\n");
4013 for (i
= 0; i
< n_iv_cands (data
); i
++)
4015 struct iv_cand
*cand
= iv_cand (data
, i
);
4017 determine_iv_cost (data
, cand
);
4019 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4020 fprintf (dump_file
, " %d\t%d\n", i
, cand
->cost
);
4023 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4024 fprintf (dump_file
, "\n");
4027 /* Calculates cost for having SIZE induction variables. */
4030 ivopts_global_cost_for_size (struct ivopts_data
*data
, unsigned size
)
4032 /* We add size to the cost, so that we prefer eliminating ivs
4034 return size
+ estimate_reg_pressure_cost (size
, data
->regs_used
);
4037 /* For each size of the induction variable set determine the penalty. */
4040 determine_set_costs (struct ivopts_data
*data
)
4044 struct loop
*loop
= data
->current_loop
;
4047 /* We use the following model (definitely improvable, especially the
4048 cost function -- TODO):
4050 We estimate the number of registers available (using MD data), name it A.
4052 We estimate the number of registers used by the loop, name it U. This
4053 number is obtained as the number of loop phi nodes (not counting virtual
4054 registers and bivs) + the number of variables from outside of the loop.
4056 We set a reserve R (free regs that are used for temporary computations,
4057 etc.). For now the reserve is a constant 3.
4059 Let I be the number of induction variables.
4061 -- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
4062 make a lot of ivs without a reason).
4063 -- if A - R < U + I <= A, the cost is I * PRES_COST
4064 -- if U + I > A, the cost is I * PRES_COST and
4065 number of uses * SPILL_COST * (U + I - A) / (U + I) is added. */
4067 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4069 fprintf (dump_file
, "Global costs:\n");
4070 fprintf (dump_file
, " target_avail_regs %d\n", target_avail_regs
);
4071 fprintf (dump_file
, " target_reg_cost %d\n", target_reg_cost
);
4072 fprintf (dump_file
, " target_spill_cost %d\n", target_spill_cost
);
4076 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
4078 op
= PHI_RESULT (phi
);
4080 if (!is_gimple_reg (op
))
4083 if (get_iv (data
, op
))
4089 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
4091 struct version_info
*info
= ver_info (data
, j
);
4093 if (info
->inv_id
&& info
->has_nonlin_use
)
4097 data
->regs_used
= n
;
4098 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4099 fprintf (dump_file
, " regs_used %d\n", n
);
4101 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4103 fprintf (dump_file
, " cost for size:\n");
4104 fprintf (dump_file
, " ivs\tcost\n");
4105 for (j
= 0; j
<= 2 * target_avail_regs
; j
++)
4106 fprintf (dump_file
, " %d\t%d\n", j
,
4107 ivopts_global_cost_for_size (data
, j
));
4108 fprintf (dump_file
, "\n");
4112 /* Returns true if A is a cheaper cost pair than B. */
4115 cheaper_cost_pair (struct cost_pair
*a
, struct cost_pair
*b
)
4125 cmp
= compare_costs (a
->cost
, b
->cost
);
4132 /* In case the costs are the same, prefer the cheaper candidate. */
4133 if (a
->cand
->cost
< b
->cand
->cost
)
4139 /* Computes the cost field of IVS structure. */
4142 iv_ca_recount_cost (struct ivopts_data
*data
, struct iv_ca
*ivs
)
4144 comp_cost cost
= ivs
->cand_use_cost
;
4145 cost
.cost
+= ivs
->cand_cost
;
4146 cost
.cost
+= ivopts_global_cost_for_size (data
, ivs
->n_regs
);
4151 /* Remove invariants in set INVS to set IVS. */
4154 iv_ca_set_remove_invariants (struct iv_ca
*ivs
, bitmap invs
)
4162 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
4164 ivs
->n_invariant_uses
[iid
]--;
4165 if (ivs
->n_invariant_uses
[iid
] == 0)
4170 /* Set USE not to be expressed by any candidate in IVS. */
4173 iv_ca_set_no_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4176 unsigned uid
= use
->id
, cid
;
4177 struct cost_pair
*cp
;
4179 cp
= ivs
->cand_for_use
[uid
];
4185 ivs
->cand_for_use
[uid
] = NULL
;
4186 ivs
->n_cand_uses
[cid
]--;
4188 if (ivs
->n_cand_uses
[cid
] == 0)
4190 bitmap_clear_bit (ivs
->cands
, cid
);
4191 /* Do not count the pseudocandidates. */
4195 ivs
->cand_cost
-= cp
->cand
->cost
;
4197 iv_ca_set_remove_invariants (ivs
, cp
->cand
->depends_on
);
4200 ivs
->cand_use_cost
= sub_costs (ivs
->cand_use_cost
, cp
->cost
);
4202 iv_ca_set_remove_invariants (ivs
, cp
->depends_on
);
4203 iv_ca_recount_cost (data
, ivs
);
4206 /* Add invariants in set INVS to set IVS. */
4209 iv_ca_set_add_invariants (struct iv_ca
*ivs
, bitmap invs
)
4217 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
4219 ivs
->n_invariant_uses
[iid
]++;
4220 if (ivs
->n_invariant_uses
[iid
] == 1)
4225 /* Set cost pair for USE in set IVS to CP. */
4228 iv_ca_set_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4229 struct iv_use
*use
, struct cost_pair
*cp
)
4231 unsigned uid
= use
->id
, cid
;
4233 if (ivs
->cand_for_use
[uid
] == cp
)
4236 if (ivs
->cand_for_use
[uid
])
4237 iv_ca_set_no_cp (data
, ivs
, use
);
4244 ivs
->cand_for_use
[uid
] = cp
;
4245 ivs
->n_cand_uses
[cid
]++;
4246 if (ivs
->n_cand_uses
[cid
] == 1)
4248 bitmap_set_bit (ivs
->cands
, cid
);
4249 /* Do not count the pseudocandidates. */
4253 ivs
->cand_cost
+= cp
->cand
->cost
;
4255 iv_ca_set_add_invariants (ivs
, cp
->cand
->depends_on
);
4258 ivs
->cand_use_cost
= add_costs (ivs
->cand_use_cost
, cp
->cost
);
4259 iv_ca_set_add_invariants (ivs
, cp
->depends_on
);
4260 iv_ca_recount_cost (data
, ivs
);
4264 /* Extend set IVS by expressing USE by some of the candidates in it
4268 iv_ca_add_use (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4271 struct cost_pair
*best_cp
= NULL
, *cp
;
4275 gcc_assert (ivs
->upto
>= use
->id
);
4277 if (ivs
->upto
== use
->id
)
4283 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
4285 cp
= get_use_iv_cost (data
, use
, iv_cand (data
, i
));
4287 if (cheaper_cost_pair (cp
, best_cp
))
4291 iv_ca_set_cp (data
, ivs
, use
, best_cp
);
4294 /* Get cost for assignment IVS. */
4297 iv_ca_cost (struct iv_ca
*ivs
)
4299 return (ivs
->bad_uses
? infinite_cost
: ivs
->cost
);
4302 /* Returns true if all dependences of CP are among invariants in IVS. */
4305 iv_ca_has_deps (struct iv_ca
*ivs
, struct cost_pair
*cp
)
4310 if (!cp
->depends_on
)
4313 EXECUTE_IF_SET_IN_BITMAP (cp
->depends_on
, 0, i
, bi
)
4315 if (ivs
->n_invariant_uses
[i
] == 0)
4322 /* Creates change of expressing USE by NEW_CP instead of OLD_CP and chains
4323 it before NEXT_CHANGE. */
4325 static struct iv_ca_delta
*
4326 iv_ca_delta_add (struct iv_use
*use
, struct cost_pair
*old_cp
,
4327 struct cost_pair
*new_cp
, struct iv_ca_delta
*next_change
)
4329 struct iv_ca_delta
*change
= XNEW (struct iv_ca_delta
);
4332 change
->old_cp
= old_cp
;
4333 change
->new_cp
= new_cp
;
4334 change
->next_change
= next_change
;
4339 /* Joins two lists of changes L1 and L2. Destructive -- old lists
4342 static struct iv_ca_delta
*
4343 iv_ca_delta_join (struct iv_ca_delta
*l1
, struct iv_ca_delta
*l2
)
4345 struct iv_ca_delta
*last
;
4353 for (last
= l1
; last
->next_change
; last
= last
->next_change
)
4355 last
->next_change
= l2
;
4360 /* Returns candidate by that USE is expressed in IVS. */
4362 static struct cost_pair
*
4363 iv_ca_cand_for_use (struct iv_ca
*ivs
, struct iv_use
*use
)
4365 return ivs
->cand_for_use
[use
->id
];
4368 /* Reverse the list of changes DELTA, forming the inverse to it. */
4370 static struct iv_ca_delta
*
4371 iv_ca_delta_reverse (struct iv_ca_delta
*delta
)
4373 struct iv_ca_delta
*act
, *next
, *prev
= NULL
;
4374 struct cost_pair
*tmp
;
4376 for (act
= delta
; act
; act
= next
)
4378 next
= act
->next_change
;
4379 act
->next_change
= prev
;
4383 act
->old_cp
= act
->new_cp
;
4390 /* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
4391 reverted instead. */
4394 iv_ca_delta_commit (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4395 struct iv_ca_delta
*delta
, bool forward
)
4397 struct cost_pair
*from
, *to
;
4398 struct iv_ca_delta
*act
;
4401 delta
= iv_ca_delta_reverse (delta
);
4403 for (act
= delta
; act
; act
= act
->next_change
)
4407 gcc_assert (iv_ca_cand_for_use (ivs
, act
->use
) == from
);
4408 iv_ca_set_cp (data
, ivs
, act
->use
, to
);
4412 iv_ca_delta_reverse (delta
);
4415 /* Returns true if CAND is used in IVS. */
4418 iv_ca_cand_used_p (struct iv_ca
*ivs
, struct iv_cand
*cand
)
4420 return ivs
->n_cand_uses
[cand
->id
] > 0;
4423 /* Returns number of induction variable candidates in the set IVS. */
4426 iv_ca_n_cands (struct iv_ca
*ivs
)
4428 return ivs
->n_cands
;
4431 /* Free the list of changes DELTA. */
4434 iv_ca_delta_free (struct iv_ca_delta
**delta
)
4436 struct iv_ca_delta
*act
, *next
;
4438 for (act
= *delta
; act
; act
= next
)
4440 next
= act
->next_change
;
4447 /* Allocates new iv candidates assignment. */
4449 static struct iv_ca
*
4450 iv_ca_new (struct ivopts_data
*data
)
4452 struct iv_ca
*nw
= XNEW (struct iv_ca
);
4456 nw
->cand_for_use
= XCNEWVEC (struct cost_pair
*, n_iv_uses (data
));
4457 nw
->n_cand_uses
= XCNEWVEC (unsigned, n_iv_cands (data
));
4458 nw
->cands
= BITMAP_ALLOC (NULL
);
4461 nw
->cand_use_cost
= zero_cost
;
4463 nw
->n_invariant_uses
= XCNEWVEC (unsigned, data
->max_inv_id
+ 1);
4464 nw
->cost
= zero_cost
;
4469 /* Free memory occupied by the set IVS. */
4472 iv_ca_free (struct iv_ca
**ivs
)
4474 free ((*ivs
)->cand_for_use
);
4475 free ((*ivs
)->n_cand_uses
);
4476 BITMAP_FREE ((*ivs
)->cands
);
4477 free ((*ivs
)->n_invariant_uses
);
4482 /* Dumps IVS to FILE. */
4485 iv_ca_dump (struct ivopts_data
*data
, FILE *file
, struct iv_ca
*ivs
)
4487 const char *pref
= " invariants ";
4489 comp_cost cost
= iv_ca_cost (ivs
);
4491 fprintf (file
, " cost %d (complexity %d)\n", cost
.cost
, cost
.complexity
);
4492 bitmap_print (file
, ivs
->cands
, " candidates ","\n");
4494 for (i
= 1; i
<= data
->max_inv_id
; i
++)
4495 if (ivs
->n_invariant_uses
[i
])
4497 fprintf (file
, "%s%d", pref
, i
);
4500 fprintf (file
, "\n");
4503 /* Try changing candidate in IVS to CAND for each use. Return cost of the
4504 new set, and store differences in DELTA. Number of induction variables
4505 in the new set is stored to N_IVS. */
4508 iv_ca_extend (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4509 struct iv_cand
*cand
, struct iv_ca_delta
**delta
,
4515 struct cost_pair
*old_cp
, *new_cp
;
4518 for (i
= 0; i
< ivs
->upto
; i
++)
4520 use
= iv_use (data
, i
);
4521 old_cp
= iv_ca_cand_for_use (ivs
, use
);
4524 && old_cp
->cand
== cand
)
4527 new_cp
= get_use_iv_cost (data
, use
, cand
);
4531 if (!iv_ca_has_deps (ivs
, new_cp
))
4534 if (!cheaper_cost_pair (new_cp
, old_cp
))
4537 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
4540 iv_ca_delta_commit (data
, ivs
, *delta
, true);
4541 cost
= iv_ca_cost (ivs
);
4543 *n_ivs
= iv_ca_n_cands (ivs
);
4544 iv_ca_delta_commit (data
, ivs
, *delta
, false);
4549 /* Try narrowing set IVS by removing CAND. Return the cost of
4550 the new set and store the differences in DELTA. */
4553 iv_ca_narrow (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4554 struct iv_cand
*cand
, struct iv_ca_delta
**delta
)
4558 struct cost_pair
*old_cp
, *new_cp
, *cp
;
4560 struct iv_cand
*cnd
;
4564 for (i
= 0; i
< n_iv_uses (data
); i
++)
4566 use
= iv_use (data
, i
);
4568 old_cp
= iv_ca_cand_for_use (ivs
, use
);
4569 if (old_cp
->cand
!= cand
)
4574 if (data
->consider_all_candidates
)
4576 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, ci
, bi
)
4581 cnd
= iv_cand (data
, ci
);
4583 cp
= get_use_iv_cost (data
, use
, cnd
);
4586 if (!iv_ca_has_deps (ivs
, cp
))
4589 if (!cheaper_cost_pair (cp
, new_cp
))
4597 EXECUTE_IF_AND_IN_BITMAP (use
->related_cands
, ivs
->cands
, 0, ci
, bi
)
4602 cnd
= iv_cand (data
, ci
);
4604 cp
= get_use_iv_cost (data
, use
, cnd
);
4607 if (!iv_ca_has_deps (ivs
, cp
))
4610 if (!cheaper_cost_pair (cp
, new_cp
))
4619 iv_ca_delta_free (delta
);
4620 return infinite_cost
;
4623 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
4626 iv_ca_delta_commit (data
, ivs
, *delta
, true);
4627 cost
= iv_ca_cost (ivs
);
4628 iv_ca_delta_commit (data
, ivs
, *delta
, false);
4633 /* Try optimizing the set of candidates IVS by removing candidates different
4634 from to EXCEPT_CAND from it. Return cost of the new set, and store
4635 differences in DELTA. */
4638 iv_ca_prune (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4639 struct iv_cand
*except_cand
, struct iv_ca_delta
**delta
)
4642 struct iv_ca_delta
*act_delta
, *best_delta
;
4644 comp_cost best_cost
, acost
;
4645 struct iv_cand
*cand
;
4648 best_cost
= iv_ca_cost (ivs
);
4650 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
4652 cand
= iv_cand (data
, i
);
4654 if (cand
== except_cand
)
4657 acost
= iv_ca_narrow (data
, ivs
, cand
, &act_delta
);
4659 if (compare_costs (acost
, best_cost
) < 0)
4662 iv_ca_delta_free (&best_delta
);
4663 best_delta
= act_delta
;
4666 iv_ca_delta_free (&act_delta
);
4675 /* Recurse to possibly remove other unnecessary ivs. */
4676 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
4677 best_cost
= iv_ca_prune (data
, ivs
, except_cand
, delta
);
4678 iv_ca_delta_commit (data
, ivs
, best_delta
, false);
4679 *delta
= iv_ca_delta_join (best_delta
, *delta
);
4683 /* Tries to extend the sets IVS in the best possible way in order
4684 to express the USE. */
4687 try_add_cand_for (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4690 comp_cost best_cost
, act_cost
;
4693 struct iv_cand
*cand
;
4694 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
;
4695 struct cost_pair
*cp
;
4697 iv_ca_add_use (data
, ivs
, use
);
4698 best_cost
= iv_ca_cost (ivs
);
4700 cp
= iv_ca_cand_for_use (ivs
, use
);
4703 best_delta
= iv_ca_delta_add (use
, NULL
, cp
, NULL
);
4704 iv_ca_set_no_cp (data
, ivs
, use
);
4707 /* First try important candidates not based on any memory object. Only if
4708 this fails, try the specific ones. Rationale -- in loops with many
4709 variables the best choice often is to use just one generic biv. If we
4710 added here many ivs specific to the uses, the optimization algorithm later
4711 would be likely to get stuck in a local minimum, thus causing us to create
4712 too many ivs. The approach from few ivs to more seems more likely to be
4713 successful -- starting from few ivs, replacing an expensive use by a
4714 specific iv should always be a win. */
4715 EXECUTE_IF_SET_IN_BITMAP (data
->important_candidates
, 0, i
, bi
)
4717 cand
= iv_cand (data
, i
);
4719 if (cand
->iv
->base_object
!= NULL_TREE
)
4722 if (iv_ca_cand_used_p (ivs
, cand
))
4725 cp
= get_use_iv_cost (data
, use
, cand
);
4729 iv_ca_set_cp (data
, ivs
, use
, cp
);
4730 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
);
4731 iv_ca_set_no_cp (data
, ivs
, use
);
4732 act_delta
= iv_ca_delta_add (use
, NULL
, cp
, act_delta
);
4734 if (compare_costs (act_cost
, best_cost
) < 0)
4736 best_cost
= act_cost
;
4738 iv_ca_delta_free (&best_delta
);
4739 best_delta
= act_delta
;
4742 iv_ca_delta_free (&act_delta
);
4745 if (infinite_cost_p (best_cost
))
4747 for (i
= 0; i
< use
->n_map_members
; i
++)
4749 cp
= use
->cost_map
+ i
;
4754 /* Already tried this. */
4755 if (cand
->important
&& cand
->iv
->base_object
== NULL_TREE
)
4758 if (iv_ca_cand_used_p (ivs
, cand
))
4762 iv_ca_set_cp (data
, ivs
, use
, cp
);
4763 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
);
4764 iv_ca_set_no_cp (data
, ivs
, use
);
4765 act_delta
= iv_ca_delta_add (use
, iv_ca_cand_for_use (ivs
, use
),
4768 if (compare_costs (act_cost
, best_cost
) < 0)
4770 best_cost
= act_cost
;
4773 iv_ca_delta_free (&best_delta
);
4774 best_delta
= act_delta
;
4777 iv_ca_delta_free (&act_delta
);
4781 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
4782 iv_ca_delta_free (&best_delta
);
4784 return !infinite_cost_p (best_cost
);
4787 /* Finds an initial assignment of candidates to uses. */
4789 static struct iv_ca
*
4790 get_initial_solution (struct ivopts_data
*data
)
4792 struct iv_ca
*ivs
= iv_ca_new (data
);
4795 for (i
= 0; i
< n_iv_uses (data
); i
++)
4796 if (!try_add_cand_for (data
, ivs
, iv_use (data
, i
)))
4805 /* Tries to improve set of induction variables IVS. */
4808 try_improve_iv_set (struct ivopts_data
*data
, struct iv_ca
*ivs
)
4811 comp_cost acost
, best_cost
= iv_ca_cost (ivs
);
4812 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
, *tmp_delta
;
4813 struct iv_cand
*cand
;
4815 /* Try extending the set of induction variables by one. */
4816 for (i
= 0; i
< n_iv_cands (data
); i
++)
4818 cand
= iv_cand (data
, i
);
4820 if (iv_ca_cand_used_p (ivs
, cand
))
4823 acost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, &n_ivs
);
4827 /* If we successfully added the candidate and the set is small enough,
4828 try optimizing it by removing other candidates. */
4829 if (n_ivs
<= ALWAYS_PRUNE_CAND_SET_BOUND
)
4831 iv_ca_delta_commit (data
, ivs
, act_delta
, true);
4832 acost
= iv_ca_prune (data
, ivs
, cand
, &tmp_delta
);
4833 iv_ca_delta_commit (data
, ivs
, act_delta
, false);
4834 act_delta
= iv_ca_delta_join (act_delta
, tmp_delta
);
4837 if (compare_costs (acost
, best_cost
) < 0)
4840 iv_ca_delta_free (&best_delta
);
4841 best_delta
= act_delta
;
4844 iv_ca_delta_free (&act_delta
);
4849 /* Try removing the candidates from the set instead. */
4850 best_cost
= iv_ca_prune (data
, ivs
, NULL
, &best_delta
);
4852 /* Nothing more we can do. */
4857 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
4858 gcc_assert (compare_costs (best_cost
, iv_ca_cost (ivs
)) == 0);
4859 iv_ca_delta_free (&best_delta
);
4863 /* Attempts to find the optimal set of induction variables. We do simple
4864 greedy heuristic -- we try to replace at most one candidate in the selected
4865 solution and remove the unused ivs while this improves the cost. */
4867 static struct iv_ca
*
4868 find_optimal_iv_set (struct ivopts_data
*data
)
4874 /* Get the initial solution. */
4875 set
= get_initial_solution (data
);
4878 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4879 fprintf (dump_file
, "Unable to substitute for ivs, failed.\n");
4883 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4885 fprintf (dump_file
, "Initial set of candidates:\n");
4886 iv_ca_dump (data
, dump_file
, set
);
4889 while (try_improve_iv_set (data
, set
))
4891 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4893 fprintf (dump_file
, "Improved to:\n");
4894 iv_ca_dump (data
, dump_file
, set
);
4898 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4900 comp_cost cost
= iv_ca_cost (set
);
4901 fprintf (dump_file
, "Final cost %d (complexity %d)\n\n", cost
.cost
, cost
.complexity
);
4904 for (i
= 0; i
< n_iv_uses (data
); i
++)
4906 use
= iv_use (data
, i
);
4907 use
->selected
= iv_ca_cand_for_use (set
, use
)->cand
;
4913 /* Creates a new induction variable corresponding to CAND. */
4916 create_new_iv (struct ivopts_data
*data
, struct iv_cand
*cand
)
4918 block_stmt_iterator incr_pos
;
4928 incr_pos
= bsi_last (ip_normal_pos (data
->current_loop
));
4932 incr_pos
= bsi_last (ip_end_pos (data
->current_loop
));
4937 /* Mark that the iv is preserved. */
4938 name_info (data
, cand
->var_before
)->preserve_biv
= true;
4939 name_info (data
, cand
->var_after
)->preserve_biv
= true;
4941 /* Rewrite the increment so that it uses var_before directly. */
4942 find_interesting_uses_op (data
, cand
->var_after
)->selected
= cand
;
4947 gimple_add_tmp_var (cand
->var_before
);
4948 add_referenced_var (cand
->var_before
);
4950 base
= unshare_expr (cand
->iv
->base
);
4952 create_iv (base
, unshare_expr (cand
->iv
->step
),
4953 cand
->var_before
, data
->current_loop
,
4954 &incr_pos
, after
, &cand
->var_before
, &cand
->var_after
);
4957 /* Creates new induction variables described in SET. */
4960 create_new_ivs (struct ivopts_data
*data
, struct iv_ca
*set
)
4963 struct iv_cand
*cand
;
4966 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
4968 cand
= iv_cand (data
, i
);
4969 create_new_iv (data
, cand
);
4973 /* Removes statement STMT (real or a phi node). If INCLUDING_DEFINED_NAME
4974 is true, remove also the ssa name defined by the statement. */
4977 remove_statement (tree stmt
, bool including_defined_name
)
4979 if (TREE_CODE (stmt
) == PHI_NODE
)
4981 remove_phi_node (stmt
, NULL_TREE
, including_defined_name
);
4985 block_stmt_iterator bsi
= bsi_for_stmt (stmt
);
4987 bsi_remove (&bsi
, true);
4988 release_defs (stmt
);
4992 /* Rewrites USE (definition of iv used in a nonlinear expression)
4993 using candidate CAND. */
4996 rewrite_use_nonlinear_expr (struct ivopts_data
*data
,
4997 struct iv_use
*use
, struct iv_cand
*cand
)
5001 block_stmt_iterator bsi
;
5003 /* An important special case -- if we are asked to express value of
5004 the original iv by itself, just exit; there is no need to
5005 introduce a new computation (that might also need casting the
5006 variable to unsigned and back). */
5007 if (cand
->pos
== IP_ORIGINAL
5008 && cand
->incremented_at
== use
->stmt
)
5010 tree step
, ctype
, utype
;
5011 enum tree_code incr_code
= PLUS_EXPR
;
5013 gcc_assert (TREE_CODE (use
->stmt
) == GIMPLE_MODIFY_STMT
);
5014 gcc_assert (GIMPLE_STMT_OPERAND (use
->stmt
, 0) == cand
->var_after
);
5016 step
= cand
->iv
->step
;
5017 ctype
= TREE_TYPE (step
);
5018 utype
= TREE_TYPE (cand
->var_after
);
5019 if (TREE_CODE (step
) == NEGATE_EXPR
)
5021 incr_code
= MINUS_EXPR
;
5022 step
= TREE_OPERAND (step
, 0);
5025 /* Check whether we may leave the computation unchanged.
5026 This is the case only if it does not rely on other
5027 computations in the loop -- otherwise, the computation
5028 we rely upon may be removed in remove_unused_ivs,
5029 thus leading to ICE. */
5030 op
= GIMPLE_STMT_OPERAND (use
->stmt
, 1);
5031 if (TREE_CODE (op
) == PLUS_EXPR
5032 || TREE_CODE (op
) == MINUS_EXPR
5033 || TREE_CODE (op
) == POINTER_PLUS_EXPR
)
5035 if (TREE_OPERAND (op
, 0) == cand
->var_before
)
5036 op
= TREE_OPERAND (op
, 1);
5037 else if (TREE_CODE (op
) != MINUS_EXPR
5038 && TREE_OPERAND (op
, 1) == cand
->var_before
)
5039 op
= TREE_OPERAND (op
, 0);
5047 && (TREE_CODE (op
) == INTEGER_CST
5048 || operand_equal_p (op
, step
, 0)))
5051 /* Otherwise, add the necessary computations to express
5053 op
= fold_convert (ctype
, cand
->var_before
);
5054 comp
= fold_convert (utype
,
5055 build2 (incr_code
, ctype
, op
,
5056 unshare_expr (step
)));
5060 comp
= get_computation (data
->current_loop
, use
, cand
);
5061 gcc_assert (comp
!= NULL_TREE
);
5064 switch (TREE_CODE (use
->stmt
))
5067 tgt
= PHI_RESULT (use
->stmt
);
5069 /* If we should keep the biv, do not replace it. */
5070 if (name_info (data
, tgt
)->preserve_biv
)
5073 bsi
= bsi_after_labels (bb_for_stmt (use
->stmt
));
5076 case GIMPLE_MODIFY_STMT
:
5077 tgt
= GIMPLE_STMT_OPERAND (use
->stmt
, 0);
5078 bsi
= bsi_for_stmt (use
->stmt
);
5085 op
= force_gimple_operand_bsi (&bsi
, comp
, false, SSA_NAME_VAR (tgt
),
5086 true, BSI_SAME_STMT
);
5088 if (TREE_CODE (use
->stmt
) == PHI_NODE
)
5090 ass
= build_gimple_modify_stmt (tgt
, op
);
5091 bsi_insert_before (&bsi
, ass
, BSI_SAME_STMT
);
5092 remove_statement (use
->stmt
, false);
5093 SSA_NAME_DEF_STMT (tgt
) = ass
;
5096 GIMPLE_STMT_OPERAND (use
->stmt
, 1) = op
;
5099 /* Replaces ssa name in index IDX by its basic variable. Callback for
5103 idx_remove_ssa_names (tree base
, tree
*idx
,
5104 void *data ATTRIBUTE_UNUSED
)
5108 if (TREE_CODE (*idx
) == SSA_NAME
)
5109 *idx
= SSA_NAME_VAR (*idx
);
5111 if (TREE_CODE (base
) == ARRAY_REF
)
5113 op
= &TREE_OPERAND (base
, 2);
5115 && TREE_CODE (*op
) == SSA_NAME
)
5116 *op
= SSA_NAME_VAR (*op
);
5117 op
= &TREE_OPERAND (base
, 3);
5119 && TREE_CODE (*op
) == SSA_NAME
)
5120 *op
= SSA_NAME_VAR (*op
);
5126 /* Unshares REF and replaces ssa names inside it by their basic variables. */
5129 unshare_and_remove_ssa_names (tree ref
)
5131 ref
= unshare_expr (ref
);
5132 for_each_index (&ref
, idx_remove_ssa_names
, NULL
);
5137 /* Extract the alias analysis info for the memory reference REF. There are
5138 several ways how this information may be stored and what precisely is
5139 its semantics depending on the type of the reference, but there always is
5140 somewhere hidden one _DECL node that is used to determine the set of
5141 virtual operands for the reference. The code below deciphers this jungle
5142 and extracts this single useful piece of information. */
5145 get_ref_tag (tree ref
, tree orig
)
5147 tree var
= get_base_address (ref
);
5148 tree aref
= NULL_TREE
, tag
, sv
;
5149 HOST_WIDE_INT offset
, size
, maxsize
;
5151 for (sv
= orig
; handled_component_p (sv
); sv
= TREE_OPERAND (sv
, 0))
5153 aref
= get_ref_base_and_extent (sv
, &offset
, &size
, &maxsize
);
5161 if (TREE_CODE (var
) == INDIRECT_REF
)
5163 /* If the base is a dereference of a pointer, first check its name memory
5164 tag. If it does not have one, use its symbol memory tag. */
5165 var
= TREE_OPERAND (var
, 0);
5166 if (TREE_CODE (var
) != SSA_NAME
)
5169 if (SSA_NAME_PTR_INFO (var
))
5171 tag
= SSA_NAME_PTR_INFO (var
)->name_mem_tag
;
5176 var
= SSA_NAME_VAR (var
);
5177 tag
= symbol_mem_tag (var
);
5178 gcc_assert (tag
!= NULL_TREE
);
5186 tag
= symbol_mem_tag (var
);
5194 /* Copies the reference information from OLD_REF to NEW_REF. */
5197 copy_ref_info (tree new_ref
, tree old_ref
)
5199 if (TREE_CODE (old_ref
) == TARGET_MEM_REF
)
5200 copy_mem_ref_info (new_ref
, old_ref
);
5203 TMR_ORIGINAL (new_ref
) = unshare_and_remove_ssa_names (old_ref
);
5204 TMR_TAG (new_ref
) = get_ref_tag (old_ref
, TMR_ORIGINAL (new_ref
));
5208 /* Rewrites USE (address that is an iv) using candidate CAND. */
5211 rewrite_use_address (struct ivopts_data
*data
,
5212 struct iv_use
*use
, struct iv_cand
*cand
)
5215 block_stmt_iterator bsi
= bsi_for_stmt (use
->stmt
);
5219 ok
= get_computation_aff (data
->current_loop
, use
, cand
, use
->stmt
, &aff
);
5221 unshare_aff_combination (&aff
);
5223 ref
= create_mem_ref (&bsi
, TREE_TYPE (*use
->op_p
), &aff
);
5224 copy_ref_info (ref
, *use
->op_p
);
5228 /* Rewrites USE (the condition such that one of the arguments is an iv) using
5232 rewrite_use_compare (struct ivopts_data
*data
,
5233 struct iv_use
*use
, struct iv_cand
*cand
)
5235 tree comp
, *var_p
, op
, bound
;
5236 block_stmt_iterator bsi
= bsi_for_stmt (use
->stmt
);
5237 enum tree_code compare
;
5238 struct cost_pair
*cp
= get_use_iv_cost (data
, use
, cand
);
5244 tree var
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
5245 tree var_type
= TREE_TYPE (var
);
5247 compare
= iv_elimination_compare (data
, use
);
5248 bound
= unshare_expr (fold_convert (var_type
, bound
));
5249 op
= force_gimple_operand_bsi (&bsi
, bound
, true, NULL_TREE
,
5250 true, BSI_SAME_STMT
);
5252 *use
->op_p
= build2 (compare
, boolean_type_node
, var
, op
);
5256 /* The induction variable elimination failed; just express the original
5258 comp
= get_computation (data
->current_loop
, use
, cand
);
5259 gcc_assert (comp
!= NULL_TREE
);
5261 ok
= extract_cond_operands (data
, use
->op_p
, &var_p
, NULL
, NULL
, NULL
);
5264 *var_p
= force_gimple_operand_bsi (&bsi
, comp
, true, SSA_NAME_VAR (*var_p
),
5265 true, BSI_SAME_STMT
);
5268 /* Rewrites USE using candidate CAND. */
5271 rewrite_use (struct ivopts_data
*data
, struct iv_use
*use
, struct iv_cand
*cand
)
5273 push_stmt_changes (&use
->stmt
);
5277 case USE_NONLINEAR_EXPR
:
5278 rewrite_use_nonlinear_expr (data
, use
, cand
);
5282 rewrite_use_address (data
, use
, cand
);
5286 rewrite_use_compare (data
, use
, cand
);
5293 pop_stmt_changes (&use
->stmt
);
5296 /* Rewrite the uses using the selected induction variables. */
5299 rewrite_uses (struct ivopts_data
*data
)
5302 struct iv_cand
*cand
;
5305 for (i
= 0; i
< n_iv_uses (data
); i
++)
5307 use
= iv_use (data
, i
);
5308 cand
= use
->selected
;
5311 rewrite_use (data
, use
, cand
);
5315 /* Removes the ivs that are not used after rewriting. */
5318 remove_unused_ivs (struct ivopts_data
*data
)
5323 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
5325 struct version_info
*info
;
5327 info
= ver_info (data
, j
);
5329 && !integer_zerop (info
->iv
->step
)
5331 && !info
->iv
->have_use_for
5332 && !info
->preserve_biv
)
5333 remove_statement (SSA_NAME_DEF_STMT (info
->iv
->ssa_name
), true);
5337 /* Frees data allocated by the optimization of a single loop. */
5340 free_loop_data (struct ivopts_data
*data
)
5348 pointer_map_destroy (data
->niters
);
5349 data
->niters
= NULL
;
5352 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
5354 struct version_info
*info
;
5356 info
= ver_info (data
, i
);
5360 info
->has_nonlin_use
= false;
5361 info
->preserve_biv
= false;
5364 bitmap_clear (data
->relevant
);
5365 bitmap_clear (data
->important_candidates
);
5367 for (i
= 0; i
< n_iv_uses (data
); i
++)
5369 struct iv_use
*use
= iv_use (data
, i
);
5372 BITMAP_FREE (use
->related_cands
);
5373 for (j
= 0; j
< use
->n_map_members
; j
++)
5374 if (use
->cost_map
[j
].depends_on
)
5375 BITMAP_FREE (use
->cost_map
[j
].depends_on
);
5376 free (use
->cost_map
);
5379 VEC_truncate (iv_use_p
, data
->iv_uses
, 0);
5381 for (i
= 0; i
< n_iv_cands (data
); i
++)
5383 struct iv_cand
*cand
= iv_cand (data
, i
);
5387 if (cand
->depends_on
)
5388 BITMAP_FREE (cand
->depends_on
);
5391 VEC_truncate (iv_cand_p
, data
->iv_candidates
, 0);
5393 if (data
->version_info_size
< num_ssa_names
)
5395 data
->version_info_size
= 2 * num_ssa_names
;
5396 free (data
->version_info
);
5397 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
5400 data
->max_inv_id
= 0;
5402 for (i
= 0; VEC_iterate (tree
, decl_rtl_to_reset
, i
, obj
); i
++)
5403 SET_DECL_RTL (obj
, NULL_RTX
);
5405 VEC_truncate (tree
, decl_rtl_to_reset
, 0);
5408 /* Finalizes data structures used by the iv optimization pass. LOOPS is the
5412 tree_ssa_iv_optimize_finalize (struct ivopts_data
*data
)
5414 free_loop_data (data
);
5415 free (data
->version_info
);
5416 BITMAP_FREE (data
->relevant
);
5417 BITMAP_FREE (data
->important_candidates
);
5419 VEC_free (tree
, heap
, decl_rtl_to_reset
);
5420 VEC_free (iv_use_p
, heap
, data
->iv_uses
);
5421 VEC_free (iv_cand_p
, heap
, data
->iv_candidates
);
5424 /* Optimizes the LOOP. Returns true if anything changed. */
5427 tree_ssa_iv_optimize_loop (struct ivopts_data
*data
, struct loop
*loop
)
5429 bool changed
= false;
5430 struct iv_ca
*iv_ca
;
5433 gcc_assert (!data
->niters
);
5434 data
->current_loop
= loop
;
5436 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5438 fprintf (dump_file
, "Processing loop %d\n", loop
->num
);
5440 exit
= single_dom_exit (loop
);
5443 fprintf (dump_file
, " single exit %d -> %d, exit condition ",
5444 exit
->src
->index
, exit
->dest
->index
);
5445 print_generic_expr (dump_file
, last_stmt (exit
->src
), TDF_SLIM
);
5446 fprintf (dump_file
, "\n");
5449 fprintf (dump_file
, "\n");
5452 /* For each ssa name determines whether it behaves as an induction variable
5454 if (!find_induction_variables (data
))
5457 /* Finds interesting uses (item 1). */
5458 find_interesting_uses (data
);
5459 if (n_iv_uses (data
) > MAX_CONSIDERED_USES
)
5462 /* Finds candidates for the induction variables (item 2). */
5463 find_iv_candidates (data
);
5465 /* Calculates the costs (item 3, part 1). */
5466 determine_use_iv_costs (data
);
5467 determine_iv_costs (data
);
5468 determine_set_costs (data
);
5470 /* Find the optimal set of induction variables (item 3, part 2). */
5471 iv_ca
= find_optimal_iv_set (data
);
5476 /* Create the new induction variables (item 4, part 1). */
5477 create_new_ivs (data
, iv_ca
);
5478 iv_ca_free (&iv_ca
);
5480 /* Rewrite the uses (item 4, part 2). */
5481 rewrite_uses (data
);
5483 /* Remove the ivs that are unused after rewriting. */
5484 remove_unused_ivs (data
);
5486 /* We have changed the structure of induction variables; it might happen
5487 that definitions in the scev database refer to some of them that were
5492 free_loop_data (data
);
5497 /* Main entry point. Optimizes induction variables in loops. */
5500 tree_ssa_iv_optimize (void)
5503 struct ivopts_data data
;
5506 tree_ssa_iv_optimize_init (&data
);
5508 /* Optimize the loops starting with the innermost ones. */
5509 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
5511 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5512 flow_loop_dump (loop
, dump_file
, NULL
, 1);
5514 tree_ssa_iv_optimize_loop (&data
, loop
);
5517 tree_ssa_iv_optimize_finalize (&data
);