1 /* Induction variable optimizations.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This pass tries to find the optimal set of induction variables for the loop.
21 It optimizes just the basic linear induction variables (although adding
22 support for other types should not be too hard). It includes the
23 optimizations commonly known as strength reduction, induction variable
24 coalescing and induction variable elimination. It does it in the
27 1) The interesting uses of induction variables are found. This includes
29 -- uses of induction variables in non-linear expressions
30 -- addresses of arrays
31 -- comparisons of induction variables
33 2) Candidates for the induction variables are found. This includes
35 -- old induction variables
36 -- the variables defined by expressions derived from the "interesting
39 3) The optimal (w.r. to a cost function) set of variables is chosen. The
40 cost function assigns a cost to sets of induction variables and consists
43 -- The use costs. Each of the interesting uses chooses the best induction
44 variable in the set and adds its cost to the sum. The cost reflects
45 the time spent on modifying the induction variables value to be usable
46 for the given purpose (adding base and offset for arrays, etc.).
47 -- The variable costs. Each of the variables has a cost assigned that
48 reflects the costs associated with incrementing the value of the
49 variable. The original variables are somewhat preferred.
50 -- The set cost. Depending on the size of the set, extra cost may be
51 added to reflect register pressure.
53 All the costs are defined in a machine-specific way, using the target
54 hooks and machine descriptions to determine them.
56 4) The trees are transformed to use the new variables, the dead code is
59 All of this is done loop by loop. Doing it globally is theoretically
60 possible, it might give a better performance and it might enable us
61 to decide costs more precisely, but getting all the interactions right
62 would be complicated. */
66 #include "coretypes.h"
71 #include "hard-reg-set.h"
72 #include "basic-block.h"
74 #include "diagnostic.h"
75 #include "tree-flow.h"
76 #include "tree-dump.h"
81 #include "tree-pass.h"
83 #include "insn-config.h"
85 #include "pointer-set.h"
87 #include "tree-chrec.h"
88 #include "tree-scalar-evolution.h"
91 #include "langhooks.h"
92 #include "tree-affine.h"
95 /* The infinite cost. */
96 #define INFTY 10000000
98 /* The expected number of loop iterations. TODO -- use profiling instead of
100 #define AVG_LOOP_NITER(LOOP) 5
103 /* Representation of the induction variable. */
106 tree base
; /* Initial value of the iv. */
107 tree base_object
; /* A memory object to that the induction variable points. */
108 tree step
; /* Step of the iv (constant only). */
109 tree ssa_name
; /* The ssa name with the value. */
110 bool biv_p
; /* Is it a biv? */
111 bool have_use_for
; /* Do we already have a use for it? */
112 unsigned use_id
; /* The identifier in the use if it is the case. */
115 /* Per-ssa version information (induction variable descriptions, etc.). */
118 tree name
; /* The ssa name. */
119 struct iv
*iv
; /* Induction variable description. */
120 bool has_nonlin_use
; /* For a loop-level invariant, whether it is used in
121 an expression that is not an induction variable. */
122 unsigned inv_id
; /* Id of an invariant. */
123 bool preserve_biv
; /* For the original biv, whether to preserve it. */
129 USE_NONLINEAR_EXPR
, /* Use in a nonlinear expression. */
130 USE_ADDRESS
, /* Use in an address. */
131 USE_COMPARE
/* Use is a compare. */
134 /* Cost of a computation. */
137 unsigned cost
; /* The runtime cost. */
138 unsigned complexity
; /* The estimate of the complexity of the code for
139 the computation (in no concrete units --
140 complexity field should be larger for more
141 complex expressions and addressing modes). */
144 static const comp_cost zero_cost
= {0, 0};
145 static const comp_cost infinite_cost
= {INFTY
, INFTY
};
147 /* The candidate - cost pair. */
150 struct iv_cand
*cand
; /* The candidate. */
151 comp_cost cost
; /* The cost. */
152 bitmap depends_on
; /* The list of invariants that have to be
154 tree value
; /* For final value elimination, the expression for
155 the final value of the iv. For iv elimination,
156 the new bound to compare with. */
162 unsigned id
; /* The id of the use. */
163 enum use_type type
; /* Type of the use. */
164 struct iv
*iv
; /* The induction variable it is based on. */
165 tree stmt
; /* Statement in that it occurs. */
166 tree
*op_p
; /* The place where it occurs. */
167 bitmap related_cands
; /* The set of "related" iv candidates, plus the common
170 unsigned n_map_members
; /* Number of candidates in the cost_map list. */
171 struct cost_pair
*cost_map
;
172 /* The costs wrto the iv candidates. */
174 struct iv_cand
*selected
;
175 /* The selected candidate. */
178 /* The position where the iv is computed. */
181 IP_NORMAL
, /* At the end, just before the exit condition. */
182 IP_END
, /* At the end of the latch block. */
183 IP_ORIGINAL
/* The original biv. */
186 /* The induction variable candidate. */
189 unsigned id
; /* The number of the candidate. */
190 bool important
; /* Whether this is an "important" candidate, i.e. such
191 that it should be considered by all uses. */
192 enum iv_position pos
; /* Where it is computed. */
193 tree incremented_at
; /* For original biv, the statement where it is
195 tree var_before
; /* The variable used for it before increment. */
196 tree var_after
; /* The variable used for it after increment. */
197 struct iv
*iv
; /* The value of the candidate. NULL for
198 "pseudocandidate" used to indicate the possibility
199 to replace the final value of an iv by direct
200 computation of the value. */
201 unsigned cost
; /* Cost of the candidate. */
202 bitmap depends_on
; /* The list of invariants that are used in step of the
206 /* The data used by the induction variable optimizations. */
208 typedef struct iv_use
*iv_use_p
;
210 DEF_VEC_ALLOC_P(iv_use_p
,heap
);
212 typedef struct iv_cand
*iv_cand_p
;
213 DEF_VEC_P(iv_cand_p
);
214 DEF_VEC_ALLOC_P(iv_cand_p
,heap
);
218 /* The currently optimized loop. */
219 struct loop
*current_loop
;
221 /* Number of registers used in it. */
224 /* Numbers of iterations for all exits of the current loop. */
225 struct pointer_map_t
*niters
;
227 /* The size of version_info array allocated. */
228 unsigned version_info_size
;
230 /* The array of information for the ssa names. */
231 struct version_info
*version_info
;
233 /* The bitmap of indices in version_info whose value was changed. */
236 /* The maximum invariant id. */
239 /* The uses of induction variables. */
240 VEC(iv_use_p
,heap
) *iv_uses
;
242 /* The candidates. */
243 VEC(iv_cand_p
,heap
) *iv_candidates
;
245 /* A bitmap of important candidates. */
246 bitmap important_candidates
;
248 /* Whether to consider just related and important candidates when replacing a
250 bool consider_all_candidates
;
253 /* An assignment of iv candidates to uses. */
257 /* The number of uses covered by the assignment. */
260 /* Number of uses that cannot be expressed by the candidates in the set. */
263 /* Candidate assigned to a use, together with the related costs. */
264 struct cost_pair
**cand_for_use
;
266 /* Number of times each candidate is used. */
267 unsigned *n_cand_uses
;
269 /* The candidates used. */
272 /* The number of candidates in the set. */
275 /* Total number of registers needed. */
278 /* Total cost of expressing uses. */
279 comp_cost cand_use_cost
;
281 /* Total cost of candidates. */
284 /* Number of times each invariant is used. */
285 unsigned *n_invariant_uses
;
287 /* Total cost of the assignment. */
291 /* Difference of two iv candidate assignments. */
298 /* An old assignment (for rollback purposes). */
299 struct cost_pair
*old_cp
;
301 /* A new assignment. */
302 struct cost_pair
*new_cp
;
304 /* Next change in the list. */
305 struct iv_ca_delta
*next_change
;
308 /* Bound on number of candidates below that all candidates are considered. */
310 #define CONSIDER_ALL_CANDIDATES_BOUND \
311 ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
313 /* If there are more iv occurrences, we just give up (it is quite unlikely that
314 optimizing such a loop would help, and it would take ages). */
316 #define MAX_CONSIDERED_USES \
317 ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
319 /* If there are at most this number of ivs in the set, try removing unnecessary
320 ivs from the set always. */
322 #define ALWAYS_PRUNE_CAND_SET_BOUND \
323 ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
325 /* The list of trees for that the decl_rtl field must be reset is stored
328 static VEC(tree
,heap
) *decl_rtl_to_reset
;
330 /* Number of uses recorded in DATA. */
332 static inline unsigned
333 n_iv_uses (struct ivopts_data
*data
)
335 return VEC_length (iv_use_p
, data
->iv_uses
);
338 /* Ith use recorded in DATA. */
340 static inline struct iv_use
*
341 iv_use (struct ivopts_data
*data
, unsigned i
)
343 return VEC_index (iv_use_p
, data
->iv_uses
, i
);
346 /* Number of candidates recorded in DATA. */
348 static inline unsigned
349 n_iv_cands (struct ivopts_data
*data
)
351 return VEC_length (iv_cand_p
, data
->iv_candidates
);
354 /* Ith candidate recorded in DATA. */
356 static inline struct iv_cand
*
357 iv_cand (struct ivopts_data
*data
, unsigned i
)
359 return VEC_index (iv_cand_p
, data
->iv_candidates
, i
);
362 /* The single loop exit if it dominates the latch, NULL otherwise. */
365 single_dom_exit (struct loop
*loop
)
367 edge exit
= single_exit (loop
);
372 if (!just_once_each_iteration_p (loop
, exit
->src
))
378 /* Dumps information about the induction variable IV to FILE. */
380 extern void dump_iv (FILE *, struct iv
*);
382 dump_iv (FILE *file
, struct iv
*iv
)
386 fprintf (file
, "ssa name ");
387 print_generic_expr (file
, iv
->ssa_name
, TDF_SLIM
);
388 fprintf (file
, "\n");
391 fprintf (file
, " type ");
392 print_generic_expr (file
, TREE_TYPE (iv
->base
), TDF_SLIM
);
393 fprintf (file
, "\n");
397 fprintf (file
, " base ");
398 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
399 fprintf (file
, "\n");
401 fprintf (file
, " step ");
402 print_generic_expr (file
, iv
->step
, TDF_SLIM
);
403 fprintf (file
, "\n");
407 fprintf (file
, " invariant ");
408 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
409 fprintf (file
, "\n");
414 fprintf (file
, " base object ");
415 print_generic_expr (file
, iv
->base_object
, TDF_SLIM
);
416 fprintf (file
, "\n");
420 fprintf (file
, " is a biv\n");
423 /* Dumps information about the USE to FILE. */
425 extern void dump_use (FILE *, struct iv_use
*);
427 dump_use (FILE *file
, struct iv_use
*use
)
429 fprintf (file
, "use %d\n", use
->id
);
433 case USE_NONLINEAR_EXPR
:
434 fprintf (file
, " generic\n");
438 fprintf (file
, " address\n");
442 fprintf (file
, " compare\n");
449 fprintf (file
, " in statement ");
450 print_generic_expr (file
, use
->stmt
, TDF_SLIM
);
451 fprintf (file
, "\n");
453 fprintf (file
, " at position ");
455 print_generic_expr (file
, *use
->op_p
, TDF_SLIM
);
456 fprintf (file
, "\n");
458 dump_iv (file
, use
->iv
);
460 if (use
->related_cands
)
462 fprintf (file
, " related candidates ");
463 dump_bitmap (file
, use
->related_cands
);
467 /* Dumps information about the uses to FILE. */
469 extern void dump_uses (FILE *, struct ivopts_data
*);
471 dump_uses (FILE *file
, struct ivopts_data
*data
)
476 for (i
= 0; i
< n_iv_uses (data
); i
++)
478 use
= iv_use (data
, i
);
480 dump_use (file
, use
);
481 fprintf (file
, "\n");
485 /* Dumps information about induction variable candidate CAND to FILE. */
487 extern void dump_cand (FILE *, struct iv_cand
*);
489 dump_cand (FILE *file
, struct iv_cand
*cand
)
491 struct iv
*iv
= cand
->iv
;
493 fprintf (file
, "candidate %d%s\n",
494 cand
->id
, cand
->important
? " (important)" : "");
496 if (cand
->depends_on
)
498 fprintf (file
, " depends on ");
499 dump_bitmap (file
, cand
->depends_on
);
504 fprintf (file
, " final value replacement\n");
511 fprintf (file
, " incremented before exit test\n");
515 fprintf (file
, " incremented at end\n");
519 fprintf (file
, " original biv\n");
526 /* Returns the info for ssa version VER. */
528 static inline struct version_info
*
529 ver_info (struct ivopts_data
*data
, unsigned ver
)
531 return data
->version_info
+ ver
;
534 /* Returns the info for ssa name NAME. */
536 static inline struct version_info
*
537 name_info (struct ivopts_data
*data
, tree name
)
539 return ver_info (data
, SSA_NAME_VERSION (name
));
542 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
546 stmt_after_ip_normal_pos (struct loop
*loop
, tree stmt
)
548 basic_block bb
= ip_normal_pos (loop
), sbb
= bb_for_stmt (stmt
);
552 if (sbb
== loop
->latch
)
558 return stmt
== last_stmt (bb
);
561 /* Returns true if STMT if after the place where the original induction
562 variable CAND is incremented. */
565 stmt_after_ip_original_pos (struct iv_cand
*cand
, tree stmt
)
567 basic_block cand_bb
= bb_for_stmt (cand
->incremented_at
);
568 basic_block stmt_bb
= bb_for_stmt (stmt
);
569 block_stmt_iterator bsi
;
571 if (!dominated_by_p (CDI_DOMINATORS
, stmt_bb
, cand_bb
))
574 if (stmt_bb
!= cand_bb
)
577 /* Scan the block from the end, since the original ivs are usually
578 incremented at the end of the loop body. */
579 for (bsi
= bsi_last (stmt_bb
); ; bsi_prev (&bsi
))
581 if (bsi_stmt (bsi
) == cand
->incremented_at
)
583 if (bsi_stmt (bsi
) == stmt
)
588 /* Returns true if STMT if after the place where the induction variable
589 CAND is incremented in LOOP. */
592 stmt_after_increment (struct loop
*loop
, struct iv_cand
*cand
, tree stmt
)
600 return stmt_after_ip_normal_pos (loop
, stmt
);
603 return stmt_after_ip_original_pos (cand
, stmt
);
610 /* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
613 abnormal_ssa_name_p (tree exp
)
618 if (TREE_CODE (exp
) != SSA_NAME
)
621 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
) != 0;
624 /* Returns false if BASE or INDEX contains a ssa name that occurs in an
625 abnormal phi node. Callback for for_each_index. */
628 idx_contains_abnormal_ssa_name_p (tree base
, tree
*index
,
629 void *data ATTRIBUTE_UNUSED
)
631 if (TREE_CODE (base
) == ARRAY_REF
)
633 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 2)))
635 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 3)))
639 return !abnormal_ssa_name_p (*index
);
642 /* Returns true if EXPR contains a ssa name that occurs in an
643 abnormal phi node. */
646 contains_abnormal_ssa_name_p (tree expr
)
649 enum tree_code_class codeclass
;
654 code
= TREE_CODE (expr
);
655 codeclass
= TREE_CODE_CLASS (code
);
657 if (code
== SSA_NAME
)
658 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr
) != 0;
660 if (code
== INTEGER_CST
661 || is_gimple_min_invariant (expr
))
664 if (code
== ADDR_EXPR
)
665 return !for_each_index (&TREE_OPERAND (expr
, 0),
666 idx_contains_abnormal_ssa_name_p
,
673 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1)))
678 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0)))
690 /* Returns tree describing number of iterations determined from
691 EXIT of DATA->current_loop, or NULL if something goes wrong. */
694 niter_for_exit (struct ivopts_data
*data
, edge exit
)
696 struct tree_niter_desc desc
;
702 data
->niters
= pointer_map_create ();
706 slot
= pointer_map_contains (data
->niters
, exit
);
710 /* Try to determine number of iterations. We must know it
711 unconditionally (i.e., without possibility of # of iterations
712 being zero). Also, we cannot safely work with ssa names that
713 appear in phi nodes on abnormal edges, so that we do not create
714 overlapping life ranges for them (PR 27283). */
715 if (number_of_iterations_exit (data
->current_loop
,
717 && integer_zerop (desc
.may_be_zero
)
718 && !contains_abnormal_ssa_name_p (desc
.niter
))
723 *pointer_map_insert (data
->niters
, exit
) = niter
;
726 niter
= (tree
) *slot
;
731 /* Returns tree describing number of iterations determined from
732 single dominating exit of DATA->current_loop, or NULL if something
736 niter_for_single_dom_exit (struct ivopts_data
*data
)
738 edge exit
= single_dom_exit (data
->current_loop
);
743 return niter_for_exit (data
, exit
);
746 /* Initializes data structures used by the iv optimization pass, stored
750 tree_ssa_iv_optimize_init (struct ivopts_data
*data
)
752 data
->version_info_size
= 2 * num_ssa_names
;
753 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
754 data
->relevant
= BITMAP_ALLOC (NULL
);
755 data
->important_candidates
= BITMAP_ALLOC (NULL
);
756 data
->max_inv_id
= 0;
758 data
->iv_uses
= VEC_alloc (iv_use_p
, heap
, 20);
759 data
->iv_candidates
= VEC_alloc (iv_cand_p
, heap
, 20);
760 decl_rtl_to_reset
= VEC_alloc (tree
, heap
, 20);
763 /* Returns a memory object to that EXPR points. In case we are able to
764 determine that it does not point to any such object, NULL is returned. */
767 determine_base_object (tree expr
)
769 enum tree_code code
= TREE_CODE (expr
);
772 /* If this is a pointer casted to any type, we need to determine
773 the base object for the pointer; so handle conversions before
774 throwing away non-pointer expressions. */
775 if (TREE_CODE (expr
) == NOP_EXPR
776 || TREE_CODE (expr
) == CONVERT_EXPR
)
777 return determine_base_object (TREE_OPERAND (expr
, 0));
779 if (!POINTER_TYPE_P (TREE_TYPE (expr
)))
788 obj
= TREE_OPERAND (expr
, 0);
789 base
= get_base_address (obj
);
794 if (TREE_CODE (base
) == INDIRECT_REF
)
795 return determine_base_object (TREE_OPERAND (base
, 0));
797 return fold_convert (ptr_type_node
,
798 build_fold_addr_expr (base
));
800 case POINTER_PLUS_EXPR
:
801 return determine_base_object (TREE_OPERAND (expr
, 0));
805 /* Pointer addition is done solely using POINTER_PLUS_EXPR. */
809 return fold_convert (ptr_type_node
, expr
);
813 /* Allocates an induction variable with given initial value BASE and step STEP
817 alloc_iv (tree base
, tree step
)
819 struct iv
*iv
= XCNEW (struct iv
);
820 gcc_assert (step
!= NULL_TREE
);
823 iv
->base_object
= determine_base_object (base
);
826 iv
->have_use_for
= false;
828 iv
->ssa_name
= NULL_TREE
;
833 /* Sets STEP and BASE for induction variable IV. */
836 set_iv (struct ivopts_data
*data
, tree iv
, tree base
, tree step
)
838 struct version_info
*info
= name_info (data
, iv
);
840 gcc_assert (!info
->iv
);
842 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (iv
));
843 info
->iv
= alloc_iv (base
, step
);
844 info
->iv
->ssa_name
= iv
;
847 /* Finds induction variable declaration for VAR. */
850 get_iv (struct ivopts_data
*data
, tree var
)
853 tree type
= TREE_TYPE (var
);
855 if (!POINTER_TYPE_P (type
)
856 && !INTEGRAL_TYPE_P (type
))
859 if (!name_info (data
, var
)->iv
)
861 bb
= bb_for_stmt (SSA_NAME_DEF_STMT (var
));
864 || !flow_bb_inside_loop_p (data
->current_loop
, bb
))
865 set_iv (data
, var
, var
, build_int_cst (type
, 0));
868 return name_info (data
, var
)->iv
;
871 /* Determines the step of a biv defined in PHI. Returns NULL if PHI does
872 not define a simple affine biv with nonzero step. */
875 determine_biv_step (tree phi
)
877 struct loop
*loop
= bb_for_stmt (phi
)->loop_father
;
878 tree name
= PHI_RESULT (phi
);
881 if (!is_gimple_reg (name
))
884 if (!simple_iv (loop
, phi
, name
, &iv
, true))
887 return integer_zerop (iv
.step
) ? NULL_TREE
: iv
.step
;
890 /* Finds basic ivs. */
893 find_bivs (struct ivopts_data
*data
)
895 tree phi
, step
, type
, base
;
897 struct loop
*loop
= data
->current_loop
;
899 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
901 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
904 step
= determine_biv_step (phi
);
908 base
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
909 base
= expand_simple_operations (base
);
910 if (contains_abnormal_ssa_name_p (base
)
911 || contains_abnormal_ssa_name_p (step
))
914 type
= TREE_TYPE (PHI_RESULT (phi
));
915 base
= fold_convert (type
, base
);
917 step
= fold_convert (type
, step
);
919 set_iv (data
, PHI_RESULT (phi
), base
, step
);
926 /* Marks basic ivs. */
929 mark_bivs (struct ivopts_data
*data
)
932 struct iv
*iv
, *incr_iv
;
933 struct loop
*loop
= data
->current_loop
;
936 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
938 iv
= get_iv (data
, PHI_RESULT (phi
));
942 var
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
943 incr_iv
= get_iv (data
, var
);
947 /* If the increment is in the subloop, ignore it. */
948 incr_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (var
));
949 if (incr_bb
->loop_father
!= data
->current_loop
950 || (incr_bb
->flags
& BB_IRREDUCIBLE_LOOP
))
954 incr_iv
->biv_p
= true;
958 /* Checks whether STMT defines a linear induction variable and stores its
962 find_givs_in_stmt_scev (struct ivopts_data
*data
, tree stmt
, affine_iv
*iv
)
965 struct loop
*loop
= data
->current_loop
;
967 iv
->base
= NULL_TREE
;
968 iv
->step
= NULL_TREE
;
970 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
973 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
974 if (TREE_CODE (lhs
) != SSA_NAME
)
977 if (!simple_iv (loop
, stmt
, GIMPLE_STMT_OPERAND (stmt
, 1), iv
, true))
979 iv
->base
= expand_simple_operations (iv
->base
);
981 if (contains_abnormal_ssa_name_p (iv
->base
)
982 || contains_abnormal_ssa_name_p (iv
->step
))
988 /* Finds general ivs in statement STMT. */
991 find_givs_in_stmt (struct ivopts_data
*data
, tree stmt
)
995 if (!find_givs_in_stmt_scev (data
, stmt
, &iv
))
998 set_iv (data
, GIMPLE_STMT_OPERAND (stmt
, 0), iv
.base
, iv
.step
);
1001 /* Finds general ivs in basic block BB. */
1004 find_givs_in_bb (struct ivopts_data
*data
, basic_block bb
)
1006 block_stmt_iterator bsi
;
1008 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1009 find_givs_in_stmt (data
, bsi_stmt (bsi
));
1012 /* Finds general ivs. */
1015 find_givs (struct ivopts_data
*data
)
1017 struct loop
*loop
= data
->current_loop
;
1018 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1021 for (i
= 0; i
< loop
->num_nodes
; i
++)
1022 find_givs_in_bb (data
, body
[i
]);
1026 /* For each ssa name defined in LOOP determines whether it is an induction
1027 variable and if so, its initial value and step. */
1030 find_induction_variables (struct ivopts_data
*data
)
1035 if (!find_bivs (data
))
1041 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1043 tree niter
= niter_for_single_dom_exit (data
);
1047 fprintf (dump_file
, " number of iterations ");
1048 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1049 fprintf (dump_file
, "\n\n");
1052 fprintf (dump_file
, "Induction variables:\n\n");
1054 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1056 if (ver_info (data
, i
)->iv
)
1057 dump_iv (dump_file
, ver_info (data
, i
)->iv
);
1064 /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV. */
1066 static struct iv_use
*
1067 record_use (struct ivopts_data
*data
, tree
*use_p
, struct iv
*iv
,
1068 tree stmt
, enum use_type use_type
)
1070 struct iv_use
*use
= XCNEW (struct iv_use
);
1072 use
->id
= n_iv_uses (data
);
1073 use
->type
= use_type
;
1077 use
->related_cands
= BITMAP_ALLOC (NULL
);
1079 /* To avoid showing ssa name in the dumps, if it was not reset by the
1081 iv
->ssa_name
= NULL_TREE
;
1083 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1084 dump_use (dump_file
, use
);
1086 VEC_safe_push (iv_use_p
, heap
, data
->iv_uses
, use
);
1091 /* Checks whether OP is a loop-level invariant and if so, records it.
1092 NONLINEAR_USE is true if the invariant is used in a way we do not
1093 handle specially. */
1096 record_invariant (struct ivopts_data
*data
, tree op
, bool nonlinear_use
)
1099 struct version_info
*info
;
1101 if (TREE_CODE (op
) != SSA_NAME
1102 || !is_gimple_reg (op
))
1105 bb
= bb_for_stmt (SSA_NAME_DEF_STMT (op
));
1107 && flow_bb_inside_loop_p (data
->current_loop
, bb
))
1110 info
= name_info (data
, op
);
1112 info
->has_nonlin_use
|= nonlinear_use
;
1114 info
->inv_id
= ++data
->max_inv_id
;
1115 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (op
));
1118 /* Checks whether the use OP is interesting and if so, records it. */
1120 static struct iv_use
*
1121 find_interesting_uses_op (struct ivopts_data
*data
, tree op
)
1128 if (TREE_CODE (op
) != SSA_NAME
)
1131 iv
= get_iv (data
, op
);
1135 if (iv
->have_use_for
)
1137 use
= iv_use (data
, iv
->use_id
);
1139 gcc_assert (use
->type
== USE_NONLINEAR_EXPR
);
1143 if (integer_zerop (iv
->step
))
1145 record_invariant (data
, op
, true);
1148 iv
->have_use_for
= true;
1150 civ
= XNEW (struct iv
);
1153 stmt
= SSA_NAME_DEF_STMT (op
);
1154 gcc_assert (TREE_CODE (stmt
) == PHI_NODE
1155 || TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
);
1157 use
= record_use (data
, NULL
, civ
, stmt
, USE_NONLINEAR_EXPR
);
1158 iv
->use_id
= use
->id
;
1163 /* Given a condition *COND_P, checks whether it is a compare of an induction
1164 variable and an invariant. If this is the case, CONTROL_VAR is set
1165 to location of the iv, BOUND to the location of the invariant,
1166 IV_VAR and IV_BOUND are set to the corresponding induction variable
1167 descriptions, and true is returned. If this is not the case,
1168 CONTROL_VAR and BOUND are set to the arguments of the condition and
1169 false is returned. */
1172 extract_cond_operands (struct ivopts_data
*data
, tree
*cond_p
,
1173 tree
**control_var
, tree
**bound
,
1174 struct iv
**iv_var
, struct iv
**iv_bound
)
1176 /* The nodes returned when COND has just one operand. Note that you should
1177 not modify anything in BOUND or IV_BOUND because of this. */
1178 static struct iv const_iv
;
1180 tree cond
= *cond_p
;
1181 tree
*op0
= &zero
, *op1
= &zero
, *tmp_op
;
1182 struct iv
*iv0
= &const_iv
, *iv1
= &const_iv
, *tmp_iv
;
1185 zero
= integer_zero_node
;
1186 const_iv
.step
= integer_zero_node
;
1188 if (TREE_CODE (cond
) == SSA_NAME
)
1191 iv0
= get_iv (data
, cond
);
1192 ret
= (iv0
&& !integer_zerop (iv0
->step
));
1196 if (!COMPARISON_CLASS_P (cond
))
1202 op0
= &TREE_OPERAND (cond
, 0);
1203 op1
= &TREE_OPERAND (cond
, 1);
1204 if (TREE_CODE (*op0
) == SSA_NAME
)
1205 iv0
= get_iv (data
, *op0
);
1206 if (TREE_CODE (*op1
) == SSA_NAME
)
1207 iv1
= get_iv (data
, *op1
);
1209 /* Exactly one of the compared values must be an iv, and the other one must
1214 if (integer_zerop (iv0
->step
))
1216 /* Control variable may be on the other side. */
1217 tmp_op
= op0
; op0
= op1
; op1
= tmp_op
;
1218 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
1220 ret
= !integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
);
1224 *control_var
= op0
;;
1235 /* Checks whether the condition *COND_P in STMT is interesting
1236 and if so, records it. */
1239 find_interesting_uses_cond (struct ivopts_data
*data
, tree stmt
, tree
*cond_p
)
1241 tree
*var_p
, *bound_p
;
1242 struct iv
*var_iv
, *civ
;
1244 if (!extract_cond_operands (data
, cond_p
, &var_p
, &bound_p
, &var_iv
, NULL
))
1246 find_interesting_uses_op (data
, *var_p
);
1247 find_interesting_uses_op (data
, *bound_p
);
1251 civ
= XNEW (struct iv
);
1253 record_use (data
, cond_p
, civ
, stmt
, USE_COMPARE
);
1256 /* Returns true if expression EXPR is obviously invariant in LOOP,
1257 i.e. if all its operands are defined outside of the LOOP. */
1260 expr_invariant_in_loop_p (struct loop
*loop
, tree expr
)
1265 if (is_gimple_min_invariant (expr
))
1268 if (TREE_CODE (expr
) == SSA_NAME
)
1270 def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (expr
));
1272 && flow_bb_inside_loop_p (loop
, def_bb
))
1278 if (!EXPR_P (expr
) && !GIMPLE_STMT_P (expr
))
1281 len
= TREE_OPERAND_LENGTH (expr
);
1282 for (i
= 0; i
< len
; i
++)
1283 if (!expr_invariant_in_loop_p (loop
, TREE_OPERAND (expr
, i
)))
1289 /* Cumulates the steps of indices into DATA and replaces their values with the
1290 initial ones. Returns false when the value of the index cannot be determined.
1291 Callback for for_each_index. */
1293 struct ifs_ivopts_data
1295 struct ivopts_data
*ivopts_data
;
1301 idx_find_step (tree base
, tree
*idx
, void *data
)
1303 struct ifs_ivopts_data
*dta
= (struct ifs_ivopts_data
*) data
;
1305 tree step
, iv_base
, iv_step
, lbound
, off
;
1306 struct loop
*loop
= dta
->ivopts_data
->current_loop
;
1308 if (TREE_CODE (base
) == MISALIGNED_INDIRECT_REF
1309 || TREE_CODE (base
) == ALIGN_INDIRECT_REF
)
1312 /* If base is a component ref, require that the offset of the reference
1314 if (TREE_CODE (base
) == COMPONENT_REF
)
1316 off
= component_ref_field_offset (base
);
1317 return expr_invariant_in_loop_p (loop
, off
);
1320 /* If base is array, first check whether we will be able to move the
1321 reference out of the loop (in order to take its address in strength
1322 reduction). In order for this to work we need both lower bound
1323 and step to be loop invariants. */
1324 if (TREE_CODE (base
) == ARRAY_REF
)
1326 step
= array_ref_element_size (base
);
1327 lbound
= array_ref_low_bound (base
);
1329 if (!expr_invariant_in_loop_p (loop
, step
)
1330 || !expr_invariant_in_loop_p (loop
, lbound
))
1334 if (TREE_CODE (*idx
) != SSA_NAME
)
1337 iv
= get_iv (dta
->ivopts_data
, *idx
);
1341 /* XXX We produce for a base of *D42 with iv->base being &x[0]
1342 *&x[0], which is not folded and does not trigger the
1343 ARRAY_REF path below. */
1346 if (integer_zerop (iv
->step
))
1349 if (TREE_CODE (base
) == ARRAY_REF
)
1351 step
= array_ref_element_size (base
);
1353 /* We only handle addresses whose step is an integer constant. */
1354 if (TREE_CODE (step
) != INTEGER_CST
)
1358 /* The step for pointer arithmetics already is 1 byte. */
1359 step
= build_int_cst (sizetype
, 1);
1363 if (!convert_affine_scev (dta
->ivopts_data
->current_loop
,
1364 sizetype
, &iv_base
, &iv_step
, dta
->stmt
,
1367 /* The index might wrap. */
1371 step
= fold_build2 (MULT_EXPR
, sizetype
, step
, iv_step
);
1372 dta
->step
= fold_build2 (PLUS_EXPR
, sizetype
, dta
->step
, step
);
1377 /* Records use in index IDX. Callback for for_each_index. Ivopts data
1378 object is passed to it in DATA. */
1381 idx_record_use (tree base
, tree
*idx
,
1384 struct ivopts_data
*data
= (struct ivopts_data
*) vdata
;
1385 find_interesting_uses_op (data
, *idx
);
1386 if (TREE_CODE (base
) == ARRAY_REF
)
1388 find_interesting_uses_op (data
, array_ref_element_size (base
));
1389 find_interesting_uses_op (data
, array_ref_low_bound (base
));
1394 /* Returns true if memory reference REF may be unaligned. */
1397 may_be_unaligned_p (tree ref
)
1401 HOST_WIDE_INT bitsize
;
1402 HOST_WIDE_INT bitpos
;
1404 enum machine_mode mode
;
1405 int unsignedp
, volatilep
;
1406 unsigned base_align
;
1408 /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
1409 thus they are not misaligned. */
1410 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
1413 /* The test below is basically copy of what expr.c:normal_inner_ref
1414 does to check whether the object must be loaded by parts when
1415 STRICT_ALIGNMENT is true. */
1416 base
= get_inner_reference (ref
, &bitsize
, &bitpos
, &toffset
, &mode
,
1417 &unsignedp
, &volatilep
, true);
1418 base_type
= TREE_TYPE (base
);
1419 base_align
= TYPE_ALIGN (base_type
);
1421 if (mode
!= BLKmode
)
1423 unsigned mode_align
= GET_MODE_ALIGNMENT (mode
);
1425 if (base_align
< mode_align
1426 || (bitpos
% mode_align
) != 0
1427 || (bitpos
% BITS_PER_UNIT
) != 0)
1431 && (highest_pow2_factor (toffset
) * BITS_PER_UNIT
) < mode_align
)
1438 /* Return true if EXPR may be non-addressable. */
1441 may_be_nonaddressable_p (tree expr
)
1443 switch (TREE_CODE (expr
))
1445 case TARGET_MEM_REF
:
1446 /* TARGET_MEM_REFs are translated directly to valid MEMs on the
1447 target, thus they are always addressable. */
1451 return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr
, 1))
1452 || may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1454 case VIEW_CONVERT_EXPR
:
1455 /* This kind of view-conversions may wrap non-addressable objects
1456 and make them look addressable. After some processing the
1457 non-addressability may be uncovered again, causing ADDR_EXPRs
1458 of inappropriate objects to be built. */
1459 if (is_gimple_reg (TREE_OPERAND (expr
, 0))
1460 || !is_gimple_addressable (TREE_OPERAND (expr
, 0)))
1463 /* ... fall through ... */
1466 case ARRAY_RANGE_REF
:
1467 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1470 case NON_LVALUE_EXPR
:
1481 /* Finds addresses in *OP_P inside STMT. */
1484 find_interesting_uses_address (struct ivopts_data
*data
, tree stmt
, tree
*op_p
)
1486 tree base
= *op_p
, step
= build_int_cst (sizetype
, 0);
1488 struct ifs_ivopts_data ifs_ivopts_data
;
1490 /* Do not play with volatile memory references. A bit too conservative,
1491 perhaps, but safe. */
1492 if (stmt_ann (stmt
)->has_volatile_ops
)
1495 /* Ignore bitfields for now. Not really something terribly complicated
1497 if (TREE_CODE (base
) == BIT_FIELD_REF
)
1500 base
= unshare_expr (base
);
1502 if (TREE_CODE (base
) == TARGET_MEM_REF
)
1504 tree type
= build_pointer_type (TREE_TYPE (base
));
1508 && TREE_CODE (TMR_BASE (base
)) == SSA_NAME
)
1510 civ
= get_iv (data
, TMR_BASE (base
));
1514 TMR_BASE (base
) = civ
->base
;
1517 if (TMR_INDEX (base
)
1518 && TREE_CODE (TMR_INDEX (base
)) == SSA_NAME
)
1520 civ
= get_iv (data
, TMR_INDEX (base
));
1524 TMR_INDEX (base
) = civ
->base
;
1529 if (TMR_STEP (base
))
1530 astep
= fold_build2 (MULT_EXPR
, type
, TMR_STEP (base
), astep
);
1532 step
= fold_build2 (PLUS_EXPR
, type
, step
, astep
);
1536 if (integer_zerop (step
))
1538 base
= tree_mem_ref_addr (type
, base
);
1542 ifs_ivopts_data
.ivopts_data
= data
;
1543 ifs_ivopts_data
.stmt
= stmt
;
1544 ifs_ivopts_data
.step
= build_int_cst (sizetype
, 0);
1545 if (!for_each_index (&base
, idx_find_step
, &ifs_ivopts_data
)
1546 || integer_zerop (ifs_ivopts_data
.step
))
1548 step
= ifs_ivopts_data
.step
;
1550 gcc_assert (TREE_CODE (base
) != ALIGN_INDIRECT_REF
);
1551 gcc_assert (TREE_CODE (base
) != MISALIGNED_INDIRECT_REF
);
1553 /* Check that the base expression is addressable. This needs
1554 to be done after substituting bases of IVs into it. */
1555 if (may_be_nonaddressable_p (base
))
1558 /* Moreover, on strict alignment platforms, check that it is
1559 sufficiently aligned. */
1560 if (STRICT_ALIGNMENT
&& may_be_unaligned_p (base
))
1563 base
= build_fold_addr_expr (base
);
1565 /* Substituting bases of IVs into the base expression might
1566 have caused folding opportunities. */
1567 if (TREE_CODE (base
) == ADDR_EXPR
)
1569 tree
*ref
= &TREE_OPERAND (base
, 0);
1570 while (handled_component_p (*ref
))
1571 ref
= &TREE_OPERAND (*ref
, 0);
1572 if (TREE_CODE (*ref
) == INDIRECT_REF
)
1573 *ref
= fold_indirect_ref (*ref
);
1577 civ
= alloc_iv (base
, step
);
1578 record_use (data
, op_p
, civ
, stmt
, USE_ADDRESS
);
1582 for_each_index (op_p
, idx_record_use
, data
);
1585 /* Finds and records invariants used in STMT. */
1588 find_invariants_stmt (struct ivopts_data
*data
, tree stmt
)
1591 use_operand_p use_p
;
1594 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1596 op
= USE_FROM_PTR (use_p
);
1597 record_invariant (data
, op
, false);
1601 /* Finds interesting uses of induction variables in the statement STMT. */
1604 find_interesting_uses_stmt (struct ivopts_data
*data
, tree stmt
)
1609 use_operand_p use_p
;
1611 find_invariants_stmt (data
, stmt
);
1613 if (TREE_CODE (stmt
) == COND_EXPR
)
1615 find_interesting_uses_cond (data
, stmt
, &COND_EXPR_COND (stmt
));
1619 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
1621 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
1622 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1624 if (TREE_CODE (lhs
) == SSA_NAME
)
1626 /* If the statement defines an induction variable, the uses are not
1627 interesting by themselves. */
1629 iv
= get_iv (data
, lhs
);
1631 if (iv
&& !integer_zerop (iv
->step
))
1635 switch (TREE_CODE_CLASS (TREE_CODE (rhs
)))
1637 case tcc_comparison
:
1638 find_interesting_uses_cond (data
, stmt
,
1639 &GIMPLE_STMT_OPERAND (stmt
, 1));
1643 find_interesting_uses_address (data
, stmt
,
1644 &GIMPLE_STMT_OPERAND (stmt
, 1));
1645 if (REFERENCE_CLASS_P (lhs
))
1646 find_interesting_uses_address (data
, stmt
,
1647 &GIMPLE_STMT_OPERAND (stmt
, 0));
1653 if (REFERENCE_CLASS_P (lhs
)
1654 && is_gimple_val (rhs
))
1656 find_interesting_uses_address (data
, stmt
,
1657 &GIMPLE_STMT_OPERAND (stmt
, 0));
1658 find_interesting_uses_op (data
, rhs
);
1662 /* TODO -- we should also handle address uses of type
1664 memory = call (whatever);
1671 if (TREE_CODE (stmt
) == PHI_NODE
1672 && bb_for_stmt (stmt
) == data
->current_loop
->header
)
1674 lhs
= PHI_RESULT (stmt
);
1675 iv
= get_iv (data
, lhs
);
1677 if (iv
&& !integer_zerop (iv
->step
))
1681 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1683 op
= USE_FROM_PTR (use_p
);
1685 if (TREE_CODE (op
) != SSA_NAME
)
1688 iv
= get_iv (data
, op
);
1692 find_interesting_uses_op (data
, op
);
1696 /* Finds interesting uses of induction variables outside of loops
1697 on loop exit edge EXIT. */
1700 find_interesting_uses_outside (struct ivopts_data
*data
, edge exit
)
1704 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= PHI_CHAIN (phi
))
1706 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1707 if (is_gimple_reg (def
))
1708 find_interesting_uses_op (data
, def
);
1712 /* Finds uses of the induction variables that are interesting. */
1715 find_interesting_uses (struct ivopts_data
*data
)
1718 block_stmt_iterator bsi
;
1720 basic_block
*body
= get_loop_body (data
->current_loop
);
1722 struct version_info
*info
;
1725 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1726 fprintf (dump_file
, "Uses:\n\n");
1728 for (i
= 0; i
< data
->current_loop
->num_nodes
; i
++)
1733 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1734 if (e
->dest
!= EXIT_BLOCK_PTR
1735 && !flow_bb_inside_loop_p (data
->current_loop
, e
->dest
))
1736 find_interesting_uses_outside (data
, e
);
1738 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1739 find_interesting_uses_stmt (data
, phi
);
1740 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1741 find_interesting_uses_stmt (data
, bsi_stmt (bsi
));
1744 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1748 fprintf (dump_file
, "\n");
1750 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1752 info
= ver_info (data
, i
);
1755 fprintf (dump_file
, " ");
1756 print_generic_expr (dump_file
, info
->name
, TDF_SLIM
);
1757 fprintf (dump_file
, " is invariant (%d)%s\n",
1758 info
->inv_id
, info
->has_nonlin_use
? "" : ", eliminable");
1762 fprintf (dump_file
, "\n");
1768 /* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
1769 is true, assume we are inside an address. If TOP_COMPREF is true, assume
1770 we are at the top-level of the processed address. */
1773 strip_offset_1 (tree expr
, bool inside_addr
, bool top_compref
,
1774 unsigned HOST_WIDE_INT
*offset
)
1776 tree op0
= NULL_TREE
, op1
= NULL_TREE
, tmp
, step
;
1777 enum tree_code code
;
1778 tree type
, orig_type
= TREE_TYPE (expr
);
1779 unsigned HOST_WIDE_INT off0
, off1
, st
;
1780 tree orig_expr
= expr
;
1784 type
= TREE_TYPE (expr
);
1785 code
= TREE_CODE (expr
);
1791 if (!cst_and_fits_in_hwi (expr
)
1792 || integer_zerop (expr
))
1795 *offset
= int_cst_value (expr
);
1796 return build_int_cst (orig_type
, 0);
1798 case POINTER_PLUS_EXPR
:
1801 op0
= TREE_OPERAND (expr
, 0);
1802 op1
= TREE_OPERAND (expr
, 1);
1804 op0
= strip_offset_1 (op0
, false, false, &off0
);
1805 op1
= strip_offset_1 (op1
, false, false, &off1
);
1807 *offset
= (code
== MINUS_EXPR
? off0
- off1
: off0
+ off1
);
1808 if (op0
== TREE_OPERAND (expr
, 0)
1809 && op1
== TREE_OPERAND (expr
, 1))
1812 if (integer_zerop (op1
))
1814 else if (integer_zerop (op0
))
1816 if (code
== MINUS_EXPR
)
1817 expr
= fold_build1 (NEGATE_EXPR
, type
, op1
);
1822 expr
= fold_build2 (code
, type
, op0
, op1
);
1824 return fold_convert (orig_type
, expr
);
1830 step
= array_ref_element_size (expr
);
1831 if (!cst_and_fits_in_hwi (step
))
1834 st
= int_cst_value (step
);
1835 op1
= TREE_OPERAND (expr
, 1);
1836 op1
= strip_offset_1 (op1
, false, false, &off1
);
1837 *offset
= off1
* st
;
1840 && integer_zerop (op1
))
1842 /* Strip the component reference completely. */
1843 op0
= TREE_OPERAND (expr
, 0);
1844 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
1854 tmp
= component_ref_field_offset (expr
);
1856 && cst_and_fits_in_hwi (tmp
))
1858 /* Strip the component reference completely. */
1859 op0
= TREE_OPERAND (expr
, 0);
1860 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
1861 *offset
= off0
+ int_cst_value (tmp
);
1867 op0
= TREE_OPERAND (expr
, 0);
1868 op0
= strip_offset_1 (op0
, true, true, &off0
);
1871 if (op0
== TREE_OPERAND (expr
, 0))
1874 expr
= build_fold_addr_expr (op0
);
1875 return fold_convert (orig_type
, expr
);
1878 inside_addr
= false;
1885 /* Default handling of expressions for that we want to recurse into
1886 the first operand. */
1887 op0
= TREE_OPERAND (expr
, 0);
1888 op0
= strip_offset_1 (op0
, inside_addr
, false, &off0
);
1891 if (op0
== TREE_OPERAND (expr
, 0)
1892 && (!op1
|| op1
== TREE_OPERAND (expr
, 1)))
1895 expr
= copy_node (expr
);
1896 TREE_OPERAND (expr
, 0) = op0
;
1898 TREE_OPERAND (expr
, 1) = op1
;
1900 /* Inside address, we might strip the top level component references,
1901 thus changing type of the expression. Handling of ADDR_EXPR
1903 expr
= fold_convert (orig_type
, expr
);
1908 /* Strips constant offsets from EXPR and stores them to OFFSET. */
1911 strip_offset (tree expr
, unsigned HOST_WIDE_INT
*offset
)
1913 return strip_offset_1 (expr
, false, false, offset
);
1916 /* Returns variant of TYPE that can be used as base for different uses.
1917 We return unsigned type with the same precision, which avoids problems
1921 generic_type_for (tree type
)
1923 if (GENERIC_ADDR_SPACE_POINTER_TYPE_P (type
))
1924 return unsigned_type_for (type
);
1926 if (OTHER_ADDR_SPACE_POINTER_TYPE_P (type
))
1928 int qual
= ENCODE_QUAL_ADDR_SPACE (TYPE_ADDR_SPACE (TREE_TYPE (type
)));
1929 return build_pointer_type
1930 (build_qualified_type (void_type_node
, qual
));
1933 if (TYPE_UNSIGNED (type
))
1936 return unsigned_type_for (type
);
1939 /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
1940 the bitmap to that we should store it. */
1942 static struct ivopts_data
*fd_ivopts_data
;
1944 find_depends (tree
*expr_p
, int *ws ATTRIBUTE_UNUSED
, void *data
)
1946 bitmap
*depends_on
= (bitmap
*) data
;
1947 struct version_info
*info
;
1949 if (TREE_CODE (*expr_p
) != SSA_NAME
)
1951 info
= name_info (fd_ivopts_data
, *expr_p
);
1953 if (!info
->inv_id
|| info
->has_nonlin_use
)
1957 *depends_on
= BITMAP_ALLOC (NULL
);
1958 bitmap_set_bit (*depends_on
, info
->inv_id
);
1963 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
1964 position to POS. If USE is not NULL, the candidate is set as related to
1965 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
1966 replacement of the final value of the iv by a direct computation. */
1968 static struct iv_cand
*
1969 add_candidate_1 (struct ivopts_data
*data
,
1970 tree base
, tree step
, bool important
, enum iv_position pos
,
1971 struct iv_use
*use
, tree incremented_at
)
1974 struct iv_cand
*cand
= NULL
;
1975 tree type
, orig_type
;
1979 orig_type
= TREE_TYPE (base
);
1980 type
= generic_type_for (orig_type
);
1981 if (type
!= orig_type
)
1983 base
= fold_convert (type
, base
);
1984 step
= fold_convert (type
, step
);
1988 for (i
= 0; i
< n_iv_cands (data
); i
++)
1990 cand
= iv_cand (data
, i
);
1992 if (cand
->pos
!= pos
)
1995 if (cand
->incremented_at
!= incremented_at
)
2009 if (operand_equal_p (base
, cand
->iv
->base
, 0)
2010 && operand_equal_p (step
, cand
->iv
->step
, 0))
2014 if (i
== n_iv_cands (data
))
2016 cand
= XCNEW (struct iv_cand
);
2022 cand
->iv
= alloc_iv (base
, step
);
2025 if (pos
!= IP_ORIGINAL
&& cand
->iv
)
2027 cand
->var_before
= create_tmp_var_raw (TREE_TYPE (base
), "ivtmp");
2028 cand
->var_after
= cand
->var_before
;
2030 cand
->important
= important
;
2031 cand
->incremented_at
= incremented_at
;
2032 VEC_safe_push (iv_cand_p
, heap
, data
->iv_candidates
, cand
);
2035 && TREE_CODE (step
) != INTEGER_CST
)
2037 fd_ivopts_data
= data
;
2038 walk_tree (&step
, find_depends
, &cand
->depends_on
, NULL
);
2041 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2042 dump_cand (dump_file
, cand
);
2045 if (important
&& !cand
->important
)
2047 cand
->important
= true;
2048 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2049 fprintf (dump_file
, "Candidate %d is important\n", cand
->id
);
2054 bitmap_set_bit (use
->related_cands
, i
);
2055 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2056 fprintf (dump_file
, "Candidate %d is related to use %d\n",
2063 /* Returns true if incrementing the induction variable at the end of the LOOP
2066 The purpose is to avoid splitting latch edge with a biv increment, thus
2067 creating a jump, possibly confusing other optimization passes and leaving
2068 less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS
2069 is not available (so we do not have a better alternative), or if the latch
2070 edge is already nonempty. */
2073 allow_ip_end_pos_p (struct loop
*loop
)
2075 if (!ip_normal_pos (loop
))
2078 if (!empty_block_p (ip_end_pos (loop
)))
2084 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2085 position to POS. If USE is not NULL, the candidate is set as related to
2086 it. The candidate computation is scheduled on all available positions. */
2089 add_candidate (struct ivopts_data
*data
,
2090 tree base
, tree step
, bool important
, struct iv_use
*use
)
2092 if (ip_normal_pos (data
->current_loop
))
2093 add_candidate_1 (data
, base
, step
, important
, IP_NORMAL
, use
, NULL_TREE
);
2094 if (ip_end_pos (data
->current_loop
)
2095 && allow_ip_end_pos_p (data
->current_loop
))
2096 add_candidate_1 (data
, base
, step
, important
, IP_END
, use
, NULL_TREE
);
2099 /* Add a standard "0 + 1 * iteration" iv candidate for a
2100 type with SIZE bits. */
2103 add_standard_iv_candidates_for_size (struct ivopts_data
*data
,
2106 tree type
= lang_hooks
.types
.type_for_size (size
, true);
2107 add_candidate (data
, build_int_cst (type
, 0), build_int_cst (type
, 1),
2111 /* Adds standard iv candidates. */
2114 add_standard_iv_candidates (struct ivopts_data
*data
)
2116 add_standard_iv_candidates_for_size (data
, INT_TYPE_SIZE
);
2118 /* The same for a double-integer type if it is still fast enough. */
2119 if (BITS_PER_WORD
>= INT_TYPE_SIZE
* 2)
2120 add_standard_iv_candidates_for_size (data
, INT_TYPE_SIZE
* 2);
2124 /* Adds candidates bases on the old induction variable IV. */
2127 add_old_iv_candidates (struct ivopts_data
*data
, struct iv
*iv
)
2130 struct iv_cand
*cand
;
2132 add_candidate (data
, iv
->base
, iv
->step
, true, NULL
);
2134 /* The same, but with initial value zero. */
2135 add_candidate (data
,
2136 build_int_cst (TREE_TYPE (iv
->base
), 0),
2137 iv
->step
, true, NULL
);
2139 phi
= SSA_NAME_DEF_STMT (iv
->ssa_name
);
2140 if (TREE_CODE (phi
) == PHI_NODE
)
2142 /* Additionally record the possibility of leaving the original iv
2144 def
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (data
->current_loop
));
2145 cand
= add_candidate_1 (data
,
2146 iv
->base
, iv
->step
, true, IP_ORIGINAL
, NULL
,
2147 SSA_NAME_DEF_STMT (def
));
2148 cand
->var_before
= iv
->ssa_name
;
2149 cand
->var_after
= def
;
2153 /* Adds candidates based on the old induction variables. */
2156 add_old_ivs_candidates (struct ivopts_data
*data
)
2162 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
2164 iv
= ver_info (data
, i
)->iv
;
2165 if (iv
&& iv
->biv_p
&& !integer_zerop (iv
->step
))
2166 add_old_iv_candidates (data
, iv
);
2170 /* Adds candidates based on the value of the induction variable IV and USE. */
2173 add_iv_value_candidates (struct ivopts_data
*data
,
2174 struct iv
*iv
, struct iv_use
*use
)
2176 unsigned HOST_WIDE_INT offset
;
2179 add_candidate (data
, iv
->base
, iv
->step
, false, use
);
2181 /* The same, but with initial value zero. Make such variable important,
2182 since it is generic enough so that possibly many uses may be based
2184 add_candidate (data
, build_int_cst (TREE_TYPE (iv
->base
), 0),
2185 iv
->step
, true, use
);
2187 /* Third, try removing the constant offset. */
2188 base
= strip_offset (iv
->base
, &offset
);
2190 add_candidate (data
, base
, iv
->step
, false, use
);
2193 /* Adds candidates based on the uses. */
2196 add_derived_ivs_candidates (struct ivopts_data
*data
)
2200 for (i
= 0; i
< n_iv_uses (data
); i
++)
2202 struct iv_use
*use
= iv_use (data
, i
);
2209 case USE_NONLINEAR_EXPR
:
2212 /* Just add the ivs based on the value of the iv used here. */
2213 add_iv_value_candidates (data
, use
->iv
, use
);
2222 /* Record important candidates and add them to related_cands bitmaps
2226 record_important_candidates (struct ivopts_data
*data
)
2231 for (i
= 0; i
< n_iv_cands (data
); i
++)
2233 struct iv_cand
*cand
= iv_cand (data
, i
);
2235 if (cand
->important
)
2236 bitmap_set_bit (data
->important_candidates
, i
);
2239 data
->consider_all_candidates
= (n_iv_cands (data
)
2240 <= CONSIDER_ALL_CANDIDATES_BOUND
);
2242 if (data
->consider_all_candidates
)
2244 /* We will not need "related_cands" bitmaps in this case,
2245 so release them to decrease peak memory consumption. */
2246 for (i
= 0; i
< n_iv_uses (data
); i
++)
2248 use
= iv_use (data
, i
);
2249 BITMAP_FREE (use
->related_cands
);
2254 /* Add important candidates to the related_cands bitmaps. */
2255 for (i
= 0; i
< n_iv_uses (data
); i
++)
2256 bitmap_ior_into (iv_use (data
, i
)->related_cands
,
2257 data
->important_candidates
);
2261 /* Finds the candidates for the induction variables. */
2264 find_iv_candidates (struct ivopts_data
*data
)
2266 /* Add commonly used ivs. */
2267 add_standard_iv_candidates (data
);
2269 /* Add old induction variables. */
2270 add_old_ivs_candidates (data
);
2272 /* Add induction variables derived from uses. */
2273 add_derived_ivs_candidates (data
);
2275 /* Record the important candidates. */
2276 record_important_candidates (data
);
2279 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
2280 If consider_all_candidates is true, we use a two-dimensional array, otherwise
2281 we allocate a simple list to every use. */
2284 alloc_use_cost_map (struct ivopts_data
*data
)
2286 unsigned i
, size
, s
, j
;
2288 for (i
= 0; i
< n_iv_uses (data
); i
++)
2290 struct iv_use
*use
= iv_use (data
, i
);
2293 if (data
->consider_all_candidates
)
2294 size
= n_iv_cands (data
);
2298 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, j
, bi
)
2303 /* Round up to the power of two, so that moduling by it is fast. */
2304 for (size
= 1; size
< s
; size
<<= 1)
2308 use
->n_map_members
= size
;
2309 use
->cost_map
= XCNEWVEC (struct cost_pair
, size
);
2313 /* Returns description of computation cost of expression whose runtime
2314 cost is RUNTIME and complexity corresponds to COMPLEXITY. */
2317 new_cost (unsigned runtime
, unsigned complexity
)
2321 cost
.cost
= runtime
;
2322 cost
.complexity
= complexity
;
2327 /* Adds costs COST1 and COST2. */
2330 add_costs (comp_cost cost1
, comp_cost cost2
)
2332 cost1
.cost
+= cost2
.cost
;
2333 cost1
.complexity
+= cost2
.complexity
;
2337 /* Subtracts costs COST1 and COST2. */
2340 sub_costs (comp_cost cost1
, comp_cost cost2
)
2342 cost1
.cost
-= cost2
.cost
;
2343 cost1
.complexity
-= cost2
.complexity
;
2348 /* Returns a negative number if COST1 < COST2, a positive number if
2349 COST1 > COST2, and 0 if COST1 = COST2. */
2352 compare_costs (comp_cost cost1
, comp_cost cost2
)
2354 if (cost1
.cost
== cost2
.cost
)
2355 return cost1
.complexity
- cost2
.complexity
;
2357 return cost1
.cost
- cost2
.cost
;
2360 /* Returns true if COST is infinite. */
2363 infinite_cost_p (comp_cost cost
)
2365 return cost
.cost
== INFTY
;
2368 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
2369 on invariants DEPENDS_ON and that the value used in expressing it
2373 set_use_iv_cost (struct ivopts_data
*data
,
2374 struct iv_use
*use
, struct iv_cand
*cand
,
2375 comp_cost cost
, bitmap depends_on
, tree value
)
2379 if (infinite_cost_p (cost
))
2381 BITMAP_FREE (depends_on
);
2385 if (data
->consider_all_candidates
)
2387 use
->cost_map
[cand
->id
].cand
= cand
;
2388 use
->cost_map
[cand
->id
].cost
= cost
;
2389 use
->cost_map
[cand
->id
].depends_on
= depends_on
;
2390 use
->cost_map
[cand
->id
].value
= value
;
2394 /* n_map_members is a power of two, so this computes modulo. */
2395 s
= cand
->id
& (use
->n_map_members
- 1);
2396 for (i
= s
; i
< use
->n_map_members
; i
++)
2397 if (!use
->cost_map
[i
].cand
)
2399 for (i
= 0; i
< s
; i
++)
2400 if (!use
->cost_map
[i
].cand
)
2406 use
->cost_map
[i
].cand
= cand
;
2407 use
->cost_map
[i
].cost
= cost
;
2408 use
->cost_map
[i
].depends_on
= depends_on
;
2409 use
->cost_map
[i
].value
= value
;
2412 /* Gets cost of (USE, CANDIDATE) pair. */
2414 static struct cost_pair
*
2415 get_use_iv_cost (struct ivopts_data
*data
, struct iv_use
*use
,
2416 struct iv_cand
*cand
)
2419 struct cost_pair
*ret
;
2424 if (data
->consider_all_candidates
)
2426 ret
= use
->cost_map
+ cand
->id
;
2433 /* n_map_members is a power of two, so this computes modulo. */
2434 s
= cand
->id
& (use
->n_map_members
- 1);
2435 for (i
= s
; i
< use
->n_map_members
; i
++)
2436 if (use
->cost_map
[i
].cand
== cand
)
2437 return use
->cost_map
+ i
;
2439 for (i
= 0; i
< s
; i
++)
2440 if (use
->cost_map
[i
].cand
== cand
)
2441 return use
->cost_map
+ i
;
2446 /* Returns estimate on cost of computing SEQ. */
2454 for (; seq
; seq
= NEXT_INSN (seq
))
2456 set
= single_set (seq
);
2458 cost
+= rtx_cost (set
, SET
);
2466 /* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
2468 produce_memory_decl_rtl (tree obj
, int *regno
)
2473 if (TREE_STATIC (obj
) || DECL_EXTERNAL (obj
))
2475 const char *name
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj
));
2476 x
= gen_rtx_SYMBOL_REF (Pmode
, name
);
2477 SET_SYMBOL_REF_DECL (x
, obj
);
2478 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
2479 targetm
.encode_section_info (obj
, x
, true);
2483 x
= gen_raw_REG (Pmode
, (*regno
)++);
2484 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
2490 /* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
2491 walk_tree. DATA contains the actual fake register number. */
2494 prepare_decl_rtl (tree
*expr_p
, int *ws
, void *data
)
2496 tree obj
= NULL_TREE
;
2498 int *regno
= (int *) data
;
2500 switch (TREE_CODE (*expr_p
))
2503 for (expr_p
= &TREE_OPERAND (*expr_p
, 0);
2504 handled_component_p (*expr_p
);
2505 expr_p
= &TREE_OPERAND (*expr_p
, 0))
2508 if (DECL_P (obj
) && !DECL_RTL_SET_P (obj
))
2509 x
= produce_memory_decl_rtl (obj
, regno
);
2514 obj
= SSA_NAME_VAR (*expr_p
);
2515 if (!DECL_RTL_SET_P (obj
))
2516 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2525 if (DECL_RTL_SET_P (obj
))
2528 if (DECL_MODE (obj
) == BLKmode
)
2529 x
= produce_memory_decl_rtl (obj
, regno
);
2531 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2541 VEC_safe_push (tree
, heap
, decl_rtl_to_reset
, obj
);
2542 SET_DECL_RTL (obj
, x
);
2548 /* Determines cost of the computation of EXPR. */
2551 computation_cost (tree expr
)
2554 tree type
= TREE_TYPE (expr
);
2556 /* Avoid using hard regs in ways which may be unsupported. */
2557 int regno
= LAST_VIRTUAL_REGISTER
+ 1;
2559 walk_tree (&expr
, prepare_decl_rtl
, ®no
, NULL
);
2561 rslt
= expand_expr (expr
, NULL_RTX
, TYPE_MODE (type
), EXPAND_NORMAL
);
2565 cost
= seq_cost (seq
);
2567 cost
+= address_cost (XEXP (rslt
, 0), TYPE_MODE (type
));
2572 /* Returns variable containing the value of candidate CAND at statement AT. */
2575 var_at_stmt (struct loop
*loop
, struct iv_cand
*cand
, tree stmt
)
2577 if (stmt_after_increment (loop
, cand
, stmt
))
2578 return cand
->var_after
;
2580 return cand
->var_before
;
2583 /* Return the most significant (sign) bit of T. Similar to tree_int_cst_msb,
2584 but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE. */
2587 tree_int_cst_sign_bit (const_tree t
)
2589 unsigned bitno
= TYPE_PRECISION (TREE_TYPE (t
)) - 1;
2590 unsigned HOST_WIDE_INT w
;
2592 if (bitno
< HOST_BITS_PER_WIDE_INT
)
2593 w
= TREE_INT_CST_LOW (t
);
2596 w
= TREE_INT_CST_HIGH (t
);
2597 bitno
-= HOST_BITS_PER_WIDE_INT
;
2600 return (w
>> bitno
) & 1;
2603 /* If we can prove that TOP = cst * BOT for some constant cst,
2604 store cst to MUL and return true. Otherwise return false.
2605 The returned value is always sign-extended, regardless of the
2606 signedness of TOP and BOT. */
2609 constant_multiple_of (tree top
, tree bot
, double_int
*mul
)
2612 enum tree_code code
;
2613 double_int res
, p0
, p1
;
2614 unsigned precision
= TYPE_PRECISION (TREE_TYPE (top
));
2619 if (operand_equal_p (top
, bot
, 0))
2621 *mul
= double_int_one
;
2625 code
= TREE_CODE (top
);
2629 mby
= TREE_OPERAND (top
, 1);
2630 if (TREE_CODE (mby
) != INTEGER_CST
)
2633 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &res
))
2636 *mul
= double_int_sext (double_int_mul (res
, tree_to_double_int (mby
)),
2642 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &p0
)
2643 || !constant_multiple_of (TREE_OPERAND (top
, 1), bot
, &p1
))
2646 if (code
== MINUS_EXPR
)
2647 p1
= double_int_neg (p1
);
2648 *mul
= double_int_sext (double_int_add (p0
, p1
), precision
);
2652 if (TREE_CODE (bot
) != INTEGER_CST
)
2655 p0
= double_int_sext (tree_to_double_int (top
), precision
);
2656 p1
= double_int_sext (tree_to_double_int (bot
), precision
);
2657 if (double_int_zero_p (p1
))
2659 *mul
= double_int_sext (double_int_sdivmod (p0
, p1
, FLOOR_DIV_EXPR
, &res
),
2661 return double_int_zero_p (res
);
2668 /* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
2669 same precision that is at least as wide as the precision of TYPE, stores
2670 BA to A and BB to B, and returns the type of BA. Otherwise, returns the
2674 determine_common_wider_type (tree
*a
, tree
*b
)
2676 tree wider_type
= NULL
;
2678 tree atype
= TREE_TYPE (*a
);
2680 if ((TREE_CODE (*a
) == NOP_EXPR
2681 || TREE_CODE (*a
) == CONVERT_EXPR
))
2683 suba
= TREE_OPERAND (*a
, 0);
2684 wider_type
= TREE_TYPE (suba
);
2685 if (TYPE_PRECISION (wider_type
) < TYPE_PRECISION (atype
))
2691 if ((TREE_CODE (*b
) == NOP_EXPR
2692 || TREE_CODE (*b
) == CONVERT_EXPR
))
2694 subb
= TREE_OPERAND (*b
, 0);
2695 if (TYPE_PRECISION (wider_type
) != TYPE_PRECISION (TREE_TYPE (subb
)))
2706 /* Determines the expression by that USE is expressed from induction variable
2707 CAND at statement AT in LOOP. The expression is stored in a decomposed
2708 form into AFF. Returns false if USE cannot be expressed using CAND. */
2711 get_computation_aff (struct loop
*loop
,
2712 struct iv_use
*use
, struct iv_cand
*cand
, tree at
,
2713 struct affine_tree_combination
*aff
)
2715 tree ubase
= use
->iv
->base
;
2716 tree ustep
= use
->iv
->step
;
2717 tree cbase
= cand
->iv
->base
;
2718 tree cstep
= cand
->iv
->step
, cstep_common
;
2719 tree utype
= TREE_TYPE (ubase
), ctype
= TREE_TYPE (cbase
);
2720 tree common_type
, var
;
2722 aff_tree cbase_aff
, var_aff
;
2725 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
2727 /* We do not have a precision to express the values of use. */
2731 var
= var_at_stmt (loop
, cand
, at
);
2732 uutype
= unsigned_type_for (utype
);
2734 /* If the conversion is not noop, perform it. */
2735 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
2737 cstep
= fold_convert (uutype
, cstep
);
2738 cbase
= fold_convert (uutype
, cbase
);
2739 var
= fold_convert (uutype
, var
);
2742 if (!constant_multiple_of (ustep
, cstep
, &rat
))
2745 /* In case both UBASE and CBASE are shortened to UUTYPE from some common
2746 type, we achieve better folding by computing their difference in this
2747 wider type, and cast the result to UUTYPE. We do not need to worry about
2748 overflows, as all the arithmetics will in the end be performed in UUTYPE
2750 common_type
= determine_common_wider_type (&ubase
, &cbase
);
2752 /* use = ubase - ratio * cbase + ratio * var. */
2753 tree_to_aff_combination (ubase
, common_type
, aff
);
2754 tree_to_aff_combination (cbase
, common_type
, &cbase_aff
);
2755 tree_to_aff_combination (var
, uutype
, &var_aff
);
2757 /* We need to shift the value if we are after the increment. */
2758 if (stmt_after_increment (loop
, cand
, at
))
2762 if (common_type
!= uutype
)
2763 cstep_common
= fold_convert (common_type
, cstep
);
2765 cstep_common
= cstep
;
2767 tree_to_aff_combination (cstep_common
, common_type
, &cstep_aff
);
2768 aff_combination_add (&cbase_aff
, &cstep_aff
);
2771 aff_combination_scale (&cbase_aff
, double_int_neg (rat
));
2772 aff_combination_add (aff
, &cbase_aff
);
2773 if (common_type
!= uutype
)
2774 aff_combination_convert (aff
, uutype
);
2776 aff_combination_scale (&var_aff
, rat
);
2777 aff_combination_add (aff
, &var_aff
);
2782 /* Determines the expression by that USE is expressed from induction variable
2783 CAND at statement AT in LOOP. The computation is unshared. */
2786 get_computation_at (struct loop
*loop
,
2787 struct iv_use
*use
, struct iv_cand
*cand
, tree at
)
2790 tree type
= TREE_TYPE (use
->iv
->base
);
2792 if (!get_computation_aff (loop
, use
, cand
, at
, &aff
))
2794 unshare_aff_combination (&aff
);
2795 return fold_convert (type
, aff_combination_to_tree (&aff
));
2798 /* Determines the expression by that USE is expressed from induction variable
2799 CAND in LOOP. The computation is unshared. */
2802 get_computation (struct loop
*loop
, struct iv_use
*use
, struct iv_cand
*cand
)
2804 return get_computation_at (loop
, use
, cand
, use
->stmt
);
2807 /* Returns cost of addition in MODE. */
2810 add_cost (enum machine_mode mode
)
2812 static unsigned costs
[NUM_MACHINE_MODES
];
2820 force_operand (gen_rtx_fmt_ee (PLUS
, mode
,
2821 gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 1),
2822 gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 2)),
2827 cost
= seq_cost (seq
);
2833 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2834 fprintf (dump_file
, "Addition in %s costs %d\n",
2835 GET_MODE_NAME (mode
), cost
);
2839 /* Entry in a hashtable of already known costs for multiplication. */
2842 HOST_WIDE_INT cst
; /* The constant to multiply by. */
2843 enum machine_mode mode
; /* In mode. */
2844 unsigned cost
; /* The cost. */
2847 /* Counts hash value for the ENTRY. */
2850 mbc_entry_hash (const void *entry
)
2852 const struct mbc_entry
*e
= (const struct mbc_entry
*) entry
;
2854 return 57 * (hashval_t
) e
->mode
+ (hashval_t
) (e
->cst
% 877);
2857 /* Compares the hash table entries ENTRY1 and ENTRY2. */
2860 mbc_entry_eq (const void *entry1
, const void *entry2
)
2862 const struct mbc_entry
*e1
= (const struct mbc_entry
*) entry1
;
2863 const struct mbc_entry
*e2
= (const struct mbc_entry
*) entry2
;
2865 return (e1
->mode
== e2
->mode
2866 && e1
->cst
== e2
->cst
);
2869 /* Returns cost of multiplication by constant CST in MODE. */
2872 multiply_by_cost (HOST_WIDE_INT cst
, enum machine_mode mode
)
2874 static htab_t costs
;
2875 struct mbc_entry
**cached
, act
;
2880 costs
= htab_create (100, mbc_entry_hash
, mbc_entry_eq
, free
);
2884 cached
= (struct mbc_entry
**) htab_find_slot (costs
, &act
, INSERT
);
2886 return (*cached
)->cost
;
2888 *cached
= XNEW (struct mbc_entry
);
2889 (*cached
)->mode
= mode
;
2890 (*cached
)->cst
= cst
;
2893 expand_mult (mode
, gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 1),
2894 gen_int_mode (cst
, mode
), NULL_RTX
, 0);
2898 cost
= seq_cost (seq
);
2900 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2901 fprintf (dump_file
, "Multiplication by %d in %s costs %d\n",
2902 (int) cst
, GET_MODE_NAME (mode
), cost
);
2904 (*cached
)->cost
= cost
;
2909 /* Returns true if multiplying by RATIO is allowed in an address. Test the
2910 validity for a memory reference accessing memory of mode MODE. */
2913 multiplier_allowed_in_address_p (HOST_WIDE_INT ratio
, enum machine_mode mode
)
2915 #define MAX_RATIO 128
2916 static sbitmap valid_mult
[MAX_MACHINE_MODE
];
2918 if (!valid_mult
[mode
])
2920 rtx reg1
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 1);
2924 valid_mult
[mode
] = sbitmap_alloc (2 * MAX_RATIO
+ 1);
2925 sbitmap_zero (valid_mult
[mode
]);
2926 addr
= gen_rtx_fmt_ee (MULT
, Pmode
, reg1
, NULL_RTX
);
2927 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
2929 XEXP (addr
, 1) = gen_int_mode (i
, Pmode
);
2930 if (memory_address_p (mode
, addr
))
2931 SET_BIT (valid_mult
[mode
], i
+ MAX_RATIO
);
2934 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2936 fprintf (dump_file
, " allowed multipliers:");
2937 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
2938 if (TEST_BIT (valid_mult
[mode
], i
+ MAX_RATIO
))
2939 fprintf (dump_file
, " %d", (int) i
);
2940 fprintf (dump_file
, "\n");
2941 fprintf (dump_file
, "\n");
2945 if (ratio
> MAX_RATIO
|| ratio
< -MAX_RATIO
)
2948 return TEST_BIT (valid_mult
[mode
], ratio
+ MAX_RATIO
);
2951 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
2952 If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
2953 variable is omitted. Compute the cost for a memory reference that accesses
2954 a memory location of mode MEM_MODE.
2956 TODO -- there must be some better way. This all is quite crude. */
2959 get_address_cost (bool symbol_present
, bool var_present
,
2960 unsigned HOST_WIDE_INT offset
, HOST_WIDE_INT ratio
,
2961 enum machine_mode mem_mode
)
2963 static bool initialized
[MAX_MACHINE_MODE
];
2964 static HOST_WIDE_INT rat
[MAX_MACHINE_MODE
], off
[MAX_MACHINE_MODE
];
2965 static HOST_WIDE_INT min_offset
[MAX_MACHINE_MODE
], max_offset
[MAX_MACHINE_MODE
];
2966 static unsigned costs
[MAX_MACHINE_MODE
][2][2][2][2];
2967 unsigned cost
, acost
, complexity
;
2968 bool offset_p
, ratio_p
;
2969 HOST_WIDE_INT s_offset
;
2970 unsigned HOST_WIDE_INT mask
;
2973 if (!initialized
[mem_mode
])
2976 HOST_WIDE_INT start
= BIGGEST_ALIGNMENT
/ BITS_PER_UNIT
;
2977 int old_cse_not_expected
;
2978 unsigned sym_p
, var_p
, off_p
, rat_p
, add_c
;
2979 rtx seq
, addr
, base
;
2982 initialized
[mem_mode
] = true;
2984 reg1
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 1);
2986 addr
= gen_rtx_fmt_ee (PLUS
, Pmode
, reg1
, NULL_RTX
);
2987 for (i
= start
; i
<= 1 << 20; i
<<= 1)
2989 XEXP (addr
, 1) = gen_int_mode (i
, Pmode
);
2990 if (!memory_address_p (mem_mode
, addr
))
2993 max_offset
[mem_mode
] = i
== start
? 0 : i
>> 1;
2994 off
[mem_mode
] = max_offset
[mem_mode
];
2996 for (i
= start
; i
<= 1 << 20; i
<<= 1)
2998 XEXP (addr
, 1) = gen_int_mode (-i
, Pmode
);
2999 if (!memory_address_p (mem_mode
, addr
))
3002 min_offset
[mem_mode
] = i
== start
? 0 : -(i
>> 1);
3004 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3006 fprintf (dump_file
, "get_address_cost:\n");
3007 fprintf (dump_file
, " min offset %s %d\n",
3008 GET_MODE_NAME (mem_mode
),
3009 (int) min_offset
[mem_mode
]);
3010 fprintf (dump_file
, " max offset %s %d\n",
3011 GET_MODE_NAME (mem_mode
),
3012 (int) max_offset
[mem_mode
]);
3016 for (i
= 2; i
<= MAX_RATIO
; i
++)
3017 if (multiplier_allowed_in_address_p (i
, mem_mode
))
3023 /* Compute the cost of various addressing modes. */
3025 reg0
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 1);
3026 reg1
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 2);
3028 for (i
= 0; i
< 16; i
++)
3031 var_p
= (i
>> 1) & 1;
3032 off_p
= (i
>> 2) & 1;
3033 rat_p
= (i
>> 3) & 1;
3037 addr
= gen_rtx_fmt_ee (MULT
, Pmode
, addr
,
3038 gen_int_mode (rat
[mem_mode
], Pmode
));
3041 addr
= gen_rtx_fmt_ee (PLUS
, Pmode
, addr
, reg1
);
3045 base
= gen_rtx_SYMBOL_REF (Pmode
, ggc_strdup (""));
3046 /* ??? We can run into trouble with some backends by presenting
3047 it with symbols which havn't been properly passed through
3048 targetm.encode_section_info. By setting the local bit, we
3049 enhance the probability of things working. */
3050 SYMBOL_REF_FLAGS (base
) = SYMBOL_FLAG_LOCAL
;
3053 base
= gen_rtx_fmt_e (CONST
, Pmode
,
3054 gen_rtx_fmt_ee (PLUS
, Pmode
,
3056 gen_int_mode (off
[mem_mode
],
3060 base
= gen_int_mode (off
[mem_mode
], Pmode
);
3065 addr
= gen_rtx_fmt_ee (PLUS
, Pmode
, addr
, base
);
3068 /* To avoid splitting addressing modes, pretend that no cse will
3070 old_cse_not_expected
= cse_not_expected
;
3071 cse_not_expected
= true;
3072 addr
= memory_address (mem_mode
, addr
);
3073 cse_not_expected
= old_cse_not_expected
;
3077 acost
= seq_cost (seq
);
3078 acost
+= address_cost (addr
, mem_mode
);
3082 costs
[mem_mode
][sym_p
][var_p
][off_p
][rat_p
] = acost
;
3085 /* On some targets, it is quite expensive to load symbol to a register,
3086 which makes addresses that contain symbols look much more expensive.
3087 However, the symbol will have to be loaded in any case before the
3088 loop (and quite likely we have it in register already), so it does not
3089 make much sense to penalize them too heavily. So make some final
3090 tweaks for the SYMBOL_PRESENT modes:
3092 If VAR_PRESENT is false, and the mode obtained by changing symbol to
3093 var is cheaper, use this mode with small penalty.
3094 If VAR_PRESENT is true, try whether the mode with
3095 SYMBOL_PRESENT = false is cheaper even with cost of addition, and
3096 if this is the case, use it. */
3097 add_c
= add_cost (Pmode
);
3098 for (i
= 0; i
< 8; i
++)
3101 off_p
= (i
>> 1) & 1;
3102 rat_p
= (i
>> 2) & 1;
3104 acost
= costs
[mem_mode
][0][1][off_p
][rat_p
] + 1;
3108 if (acost
< costs
[mem_mode
][1][var_p
][off_p
][rat_p
])
3109 costs
[mem_mode
][1][var_p
][off_p
][rat_p
] = acost
;
3112 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3114 fprintf (dump_file
, "Address costs:\n");
3116 for (i
= 0; i
< 16; i
++)
3119 var_p
= (i
>> 1) & 1;
3120 off_p
= (i
>> 2) & 1;
3121 rat_p
= (i
>> 3) & 1;
3123 fprintf (dump_file
, " ");
3125 fprintf (dump_file
, "sym + ");
3127 fprintf (dump_file
, "var + ");
3129 fprintf (dump_file
, "cst + ");
3131 fprintf (dump_file
, "rat * ");
3133 acost
= costs
[mem_mode
][sym_p
][var_p
][off_p
][rat_p
];
3134 fprintf (dump_file
, "index costs %d\n", acost
);
3136 fprintf (dump_file
, "\n");
3140 bits
= GET_MODE_BITSIZE (Pmode
);
3141 mask
= ~(~(unsigned HOST_WIDE_INT
) 0 << (bits
- 1) << 1);
3143 if ((offset
>> (bits
- 1) & 1))
3148 offset_p
= (s_offset
!= 0
3149 && min_offset
[mem_mode
] <= s_offset
3150 && s_offset
<= max_offset
[mem_mode
]);
3151 ratio_p
= (ratio
!= 1
3152 && multiplier_allowed_in_address_p (ratio
, mem_mode
));
3154 if (ratio
!= 1 && !ratio_p
)
3155 cost
+= multiply_by_cost (ratio
, Pmode
);
3157 if (s_offset
&& !offset_p
&& !symbol_present
)
3158 cost
+= add_cost (Pmode
);
3160 acost
= costs
[mem_mode
][symbol_present
][var_present
][offset_p
][ratio_p
];
3161 complexity
= (symbol_present
!= 0) + (var_present
!= 0) + offset_p
+ ratio_p
;
3162 return new_cost (cost
+ acost
, complexity
);
3165 /* Estimates cost of forcing expression EXPR into a variable. */
3168 force_expr_to_var_cost (tree expr
)
3170 static bool costs_initialized
= false;
3171 static unsigned integer_cost
;
3172 static unsigned symbol_cost
;
3173 static unsigned address_cost
;
3175 comp_cost cost0
, cost1
, cost
;
3176 enum machine_mode mode
;
3178 if (!costs_initialized
)
3180 tree type
= build_pointer_type (integer_type_node
);
3184 var
= create_tmp_var_raw (integer_type_node
, "test_var");
3185 TREE_STATIC (var
) = 1;
3186 x
= produce_memory_decl_rtl (var
, NULL
);
3187 SET_DECL_RTL (var
, x
);
3189 integer_cost
= computation_cost (build_int_cst (integer_type_node
,
3192 addr
= build1 (ADDR_EXPR
, type
, var
);
3193 symbol_cost
= computation_cost (addr
) + 1;
3196 = computation_cost (build2 (POINTER_PLUS_EXPR
, type
,
3198 build_int_cst (sizetype
, 2000))) + 1;
3199 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3201 fprintf (dump_file
, "force_expr_to_var_cost:\n");
3202 fprintf (dump_file
, " integer %d\n", (int) integer_cost
);
3203 fprintf (dump_file
, " symbol %d\n", (int) symbol_cost
);
3204 fprintf (dump_file
, " address %d\n", (int) address_cost
);
3205 fprintf (dump_file
, " other %d\n", (int) target_spill_cost
);
3206 fprintf (dump_file
, "\n");
3209 costs_initialized
= true;
3214 if (SSA_VAR_P (expr
))
3217 if (TREE_INVARIANT (expr
))
3219 if (TREE_CODE (expr
) == INTEGER_CST
)
3220 return new_cost (integer_cost
, 0);
3222 if (TREE_CODE (expr
) == ADDR_EXPR
)
3224 tree obj
= TREE_OPERAND (expr
, 0);
3226 if (TREE_CODE (obj
) == VAR_DECL
3227 || TREE_CODE (obj
) == PARM_DECL
3228 || TREE_CODE (obj
) == RESULT_DECL
)
3229 return new_cost (symbol_cost
, 0);
3232 return new_cost (address_cost
, 0);
3235 switch (TREE_CODE (expr
))
3237 case POINTER_PLUS_EXPR
:
3241 op0
= TREE_OPERAND (expr
, 0);
3242 op1
= TREE_OPERAND (expr
, 1);
3246 if (is_gimple_val (op0
))
3249 cost0
= force_expr_to_var_cost (op0
);
3251 if (is_gimple_val (op1
))
3254 cost1
= force_expr_to_var_cost (op1
);
3259 /* Just an arbitrary value, FIXME. */
3260 return new_cost (target_spill_cost
, 0);
3263 mode
= TYPE_MODE (TREE_TYPE (expr
));
3264 switch (TREE_CODE (expr
))
3266 case POINTER_PLUS_EXPR
:
3269 cost
= new_cost (add_cost (mode
), 0);
3273 if (cst_and_fits_in_hwi (op0
))
3274 cost
= new_cost (multiply_by_cost (int_cst_value (op0
), mode
), 0);
3275 else if (cst_and_fits_in_hwi (op1
))
3276 cost
= new_cost (multiply_by_cost (int_cst_value (op1
), mode
), 0);
3278 return new_cost (target_spill_cost
, 0);
3285 cost
= add_costs (cost
, cost0
);
3286 cost
= add_costs (cost
, cost1
);
3288 /* Bound the cost by target_spill_cost. The parts of complicated
3289 computations often are either loop invariant or at least can
3290 be shared between several iv uses, so letting this grow without
3291 limits would not give reasonable results. */
3292 if (cost
.cost
> target_spill_cost
)
3293 cost
.cost
= target_spill_cost
;
3298 /* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
3299 invariants the computation depends on. */
3302 force_var_cost (struct ivopts_data
*data
,
3303 tree expr
, bitmap
*depends_on
)
3307 fd_ivopts_data
= data
;
3308 walk_tree (&expr
, find_depends
, depends_on
, NULL
);
3311 return force_expr_to_var_cost (expr
);
3314 /* Estimates cost of expressing address ADDR as var + symbol + offset. The
3315 value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
3316 to false if the corresponding part is missing. DEPENDS_ON is a set of the
3317 invariants the computation depends on. */
3320 split_address_cost (struct ivopts_data
*data
,
3321 tree addr
, bool *symbol_present
, bool *var_present
,
3322 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3325 HOST_WIDE_INT bitsize
;
3326 HOST_WIDE_INT bitpos
;
3328 enum machine_mode mode
;
3329 int unsignedp
, volatilep
;
3331 core
= get_inner_reference (addr
, &bitsize
, &bitpos
, &toffset
, &mode
,
3332 &unsignedp
, &volatilep
, false);
3335 || bitpos
% BITS_PER_UNIT
!= 0
3336 || TREE_CODE (core
) != VAR_DECL
)
3338 *symbol_present
= false;
3339 *var_present
= true;
3340 fd_ivopts_data
= data
;
3341 walk_tree (&addr
, find_depends
, depends_on
, NULL
);
3342 return new_cost (target_spill_cost
, 0);
3345 *offset
+= bitpos
/ BITS_PER_UNIT
;
3346 if (TREE_STATIC (core
)
3347 || DECL_EXTERNAL (core
))
3349 *symbol_present
= true;
3350 *var_present
= false;
3354 *symbol_present
= false;
3355 *var_present
= true;
3359 /* Estimates cost of expressing difference of addresses E1 - E2 as
3360 var + symbol + offset. The value of offset is added to OFFSET,
3361 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3362 part is missing. DEPENDS_ON is a set of the invariants the computation
3366 ptr_difference_cost (struct ivopts_data
*data
,
3367 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
3368 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3370 HOST_WIDE_INT diff
= 0;
3373 gcc_assert (TREE_CODE (e1
) == ADDR_EXPR
);
3375 if (ptr_difference_const (e1
, e2
, &diff
))
3378 *symbol_present
= false;
3379 *var_present
= false;
3383 if (integer_zerop (e2
))
3384 return split_address_cost (data
, TREE_OPERAND (e1
, 0),
3385 symbol_present
, var_present
, offset
, depends_on
);
3387 *symbol_present
= false;
3388 *var_present
= true;
3390 cost
= force_var_cost (data
, e1
, depends_on
);
3391 cost
= add_costs (cost
, force_var_cost (data
, e2
, depends_on
));
3392 cost
.cost
+= add_cost (Pmode
);
3397 /* Estimates cost of expressing difference E1 - E2 as
3398 var + symbol + offset. The value of offset is added to OFFSET,
3399 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3400 part is missing. DEPENDS_ON is a set of the invariants the computation
3404 difference_cost (struct ivopts_data
*data
,
3405 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
3406 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3409 enum machine_mode mode
= TYPE_MODE (TREE_TYPE (e1
));
3410 unsigned HOST_WIDE_INT off1
, off2
;
3412 e1
= strip_offset (e1
, &off1
);
3413 e2
= strip_offset (e2
, &off2
);
3414 *offset
+= off1
- off2
;
3419 if (TREE_CODE (e1
) == ADDR_EXPR
)
3420 return ptr_difference_cost (data
, e1
, e2
, symbol_present
, var_present
, offset
,
3422 *symbol_present
= false;
3424 if (operand_equal_p (e1
, e2
, 0))
3426 *var_present
= false;
3429 *var_present
= true;
3430 if (integer_zerop (e2
))
3431 return force_var_cost (data
, e1
, depends_on
);
3433 if (integer_zerop (e1
))
3435 cost
= force_var_cost (data
, e2
, depends_on
);
3436 cost
.cost
+= multiply_by_cost (-1, mode
);
3441 cost
= force_var_cost (data
, e1
, depends_on
);
3442 cost
= add_costs (cost
, force_var_cost (data
, e2
, depends_on
));
3443 cost
.cost
+= add_cost (mode
);
3448 /* Determines the cost of the computation by that USE is expressed
3449 from induction variable CAND. If ADDRESS_P is true, we just need
3450 to create an address from it, otherwise we want to get it into
3451 register. A set of invariants we depend on is stored in
3452 DEPENDS_ON. AT is the statement at that the value is computed. */
3455 get_computation_cost_at (struct ivopts_data
*data
,
3456 struct iv_use
*use
, struct iv_cand
*cand
,
3457 bool address_p
, bitmap
*depends_on
, tree at
)
3459 tree ubase
= use
->iv
->base
, ustep
= use
->iv
->step
;
3461 tree utype
= TREE_TYPE (ubase
), ctype
;
3462 unsigned HOST_WIDE_INT cstepi
, offset
= 0;
3463 HOST_WIDE_INT ratio
, aratio
;
3464 bool var_present
, symbol_present
;
3471 /* Only consider real candidates. */
3473 return infinite_cost
;
3475 cbase
= cand
->iv
->base
;
3476 cstep
= cand
->iv
->step
;
3477 ctype
= TREE_TYPE (cbase
);
3479 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
3481 /* We do not have a precision to express the values of use. */
3482 return infinite_cost
;
3487 /* Do not try to express address of an object with computation based
3488 on address of a different object. This may cause problems in rtl
3489 level alias analysis (that does not expect this to be happening,
3490 as this is illegal in C), and would be unlikely to be useful
3492 if (use
->iv
->base_object
3493 && cand
->iv
->base_object
3494 && !operand_equal_p (use
->iv
->base_object
, cand
->iv
->base_object
, 0))
3495 return infinite_cost
;
3498 if (TYPE_PRECISION (utype
) != TYPE_PRECISION (ctype
))
3500 /* TODO -- add direct handling of this case. */
3504 /* CSTEPI is removed from the offset in case statement is after the
3505 increment. If the step is not constant, we use zero instead.
3506 This is a bit imprecise (there is the extra addition), but
3507 redundancy elimination is likely to transform the code so that
3508 it uses value of the variable before increment anyway,
3509 so it is not that much unrealistic. */
3510 if (cst_and_fits_in_hwi (cstep
))
3511 cstepi
= int_cst_value (cstep
);
3515 if (!constant_multiple_of (ustep
, cstep
, &rat
))
3516 return infinite_cost
;
3518 if (double_int_fits_in_shwi_p (rat
))
3519 ratio
= double_int_to_shwi (rat
);
3521 return infinite_cost
;
3523 /* use = ubase + ratio * (var - cbase). If either cbase is a constant
3524 or ratio == 1, it is better to handle this like
3526 ubase - ratio * cbase + ratio * var
3528 (also holds in the case ratio == -1, TODO. */
3530 if (cst_and_fits_in_hwi (cbase
))
3532 offset
= - ratio
* int_cst_value (cbase
);
3533 cost
= difference_cost (data
,
3534 ubase
, build_int_cst (utype
, 0),
3535 &symbol_present
, &var_present
, &offset
,
3538 else if (ratio
== 1)
3540 cost
= difference_cost (data
,
3542 &symbol_present
, &var_present
, &offset
,
3547 cost
= force_var_cost (data
, cbase
, depends_on
);
3548 cost
.cost
+= add_cost (TYPE_MODE (ctype
));
3549 cost
= add_costs (cost
,
3550 difference_cost (data
,
3551 ubase
, build_int_cst (utype
, 0),
3552 &symbol_present
, &var_present
,
3553 &offset
, depends_on
));
3556 /* If we are after the increment, the value of the candidate is higher by
3558 if (stmt_after_increment (data
->current_loop
, cand
, at
))
3559 offset
-= ratio
* cstepi
;
3561 /* Now the computation is in shape symbol + var1 + const + ratio * var2.
3562 (symbol/var/const parts may be omitted). If we are looking for an address,
3563 find the cost of addressing this. */
3565 return add_costs (cost
, get_address_cost (symbol_present
, var_present
,
3567 TYPE_MODE (TREE_TYPE (*use
->op_p
))));
3569 /* Otherwise estimate the costs for computing the expression. */
3570 aratio
= ratio
> 0 ? ratio
: -ratio
;
3571 if (!symbol_present
&& !var_present
&& !offset
)
3574 cost
.cost
+= multiply_by_cost (ratio
, TYPE_MODE (ctype
));
3580 cost
.cost
+= multiply_by_cost (aratio
, TYPE_MODE (ctype
));
3584 /* Symbol + offset should be compile-time computable. */
3585 && (symbol_present
|| offset
))
3588 /* Having offset does not affect runtime cost in case it is added to
3589 symbol, but it increases complexity. */
3593 cost
.cost
+= n_sums
* add_cost (TYPE_MODE (ctype
));
3598 /* Just get the expression, expand it and measure the cost. */
3599 tree comp
= get_computation_at (data
->current_loop
, use
, cand
, at
);
3602 return infinite_cost
;
3605 comp
= build1 (INDIRECT_REF
, TREE_TYPE (TREE_TYPE (comp
)), comp
);
3607 return new_cost (computation_cost (comp
), 0);
3611 /* Determines the cost of the computation by that USE is expressed
3612 from induction variable CAND. If ADDRESS_P is true, we just need
3613 to create an address from it, otherwise we want to get it into
3614 register. A set of invariants we depend on is stored in
3618 get_computation_cost (struct ivopts_data
*data
,
3619 struct iv_use
*use
, struct iv_cand
*cand
,
3620 bool address_p
, bitmap
*depends_on
)
3622 return get_computation_cost_at (data
,
3623 use
, cand
, address_p
, depends_on
, use
->stmt
);
3626 /* Determines cost of basing replacement of USE on CAND in a generic
3630 determine_use_iv_cost_generic (struct ivopts_data
*data
,
3631 struct iv_use
*use
, struct iv_cand
*cand
)
3636 /* The simple case first -- if we need to express value of the preserved
3637 original biv, the cost is 0. This also prevents us from counting the
3638 cost of increment twice -- once at this use and once in the cost of
3640 if (cand
->pos
== IP_ORIGINAL
3641 && cand
->incremented_at
== use
->stmt
)
3643 set_use_iv_cost (data
, use
, cand
, zero_cost
, NULL
, NULL_TREE
);
3647 cost
= get_computation_cost (data
, use
, cand
, false, &depends_on
);
3648 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
);
3650 return !infinite_cost_p (cost
);
3653 /* Determines cost of basing replacement of USE on CAND in an address. */
3656 determine_use_iv_cost_address (struct ivopts_data
*data
,
3657 struct iv_use
*use
, struct iv_cand
*cand
)
3660 comp_cost cost
= get_computation_cost (data
, use
, cand
, true, &depends_on
);
3662 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
);
3664 return !infinite_cost_p (cost
);
3667 /* Computes value of candidate CAND at position AT in iteration NITER, and
3668 stores it to VAL. */
3671 cand_value_at (struct loop
*loop
, struct iv_cand
*cand
, tree at
, tree niter
,
3674 aff_tree step
, delta
, nit
;
3675 struct iv
*iv
= cand
->iv
;
3676 tree type
= TREE_TYPE (iv
->base
);
3678 tree_to_aff_combination (iv
->step
, type
, &step
);
3679 tree_to_aff_combination (niter
, TREE_TYPE (niter
), &nit
);
3680 aff_combination_convert (&nit
, type
);
3681 aff_combination_mult (&nit
, &step
, &delta
);
3682 if (stmt_after_increment (loop
, cand
, at
))
3683 aff_combination_add (&delta
, &step
);
3685 tree_to_aff_combination (iv
->base
, type
, val
);
3686 aff_combination_add (val
, &delta
);
3689 /* Returns period of induction variable iv. */
3692 iv_period (struct iv
*iv
)
3694 tree step
= iv
->step
, period
, type
;
3697 gcc_assert (step
&& TREE_CODE (step
) == INTEGER_CST
);
3699 /* Period of the iv is gcd (step, type range). Since type range is power
3700 of two, it suffices to determine the maximum power of two that divides
3702 pow2div
= num_ending_zeros (step
);
3703 type
= unsigned_type_for (TREE_TYPE (step
));
3705 period
= build_low_bits_mask (type
,
3706 (TYPE_PRECISION (type
)
3707 - tree_low_cst (pow2div
, 1)));
3712 /* Returns the comparison operator used when eliminating the iv USE. */
3714 static enum tree_code
3715 iv_elimination_compare (struct ivopts_data
*data
, struct iv_use
*use
)
3717 struct loop
*loop
= data
->current_loop
;
3721 ex_bb
= bb_for_stmt (use
->stmt
);
3722 exit
= EDGE_SUCC (ex_bb
, 0);
3723 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
3724 exit
= EDGE_SUCC (ex_bb
, 1);
3726 return (exit
->flags
& EDGE_TRUE_VALUE
? EQ_EXPR
: NE_EXPR
);
3729 /* Check whether it is possible to express the condition in USE by comparison
3730 of candidate CAND. If so, store the value compared with to BOUND. */
3733 may_eliminate_iv (struct ivopts_data
*data
,
3734 struct iv_use
*use
, struct iv_cand
*cand
, tree
*bound
)
3739 struct loop
*loop
= data
->current_loop
;
3742 if (TREE_CODE (cand
->iv
->step
) != INTEGER_CST
)
3745 /* For now works only for exits that dominate the loop latch.
3746 TODO: extend to other conditions inside loop body. */
3747 ex_bb
= bb_for_stmt (use
->stmt
);
3748 if (use
->stmt
!= last_stmt (ex_bb
)
3749 || TREE_CODE (use
->stmt
) != COND_EXPR
)
3751 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, ex_bb
))
3754 exit
= EDGE_SUCC (ex_bb
, 0);
3755 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
3756 exit
= EDGE_SUCC (ex_bb
, 1);
3757 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
3760 nit
= niter_for_exit (data
, exit
);
3764 /* Determine whether we can use the variable to test the exit condition.
3765 This is the case iff the period of the induction variable is greater
3766 than the number of iterations for which the exit condition is true. */
3767 period
= iv_period (cand
->iv
);
3769 /* If the number of iterations is constant, compare against it directly. */
3770 if (TREE_CODE (nit
) == INTEGER_CST
)
3772 if (!tree_int_cst_lt (nit
, period
))
3776 /* If not, and if this is the only possible exit of the loop, see whether
3777 we can get a conservative estimate on the number of iterations of the
3778 entire loop and compare against that instead. */
3779 else if (loop_only_exit_p (loop
, exit
))
3781 double_int period_value
, max_niter
;
3782 if (!estimated_loop_iterations (loop
, true, &max_niter
))
3784 period_value
= tree_to_double_int (period
);
3785 if (double_int_ucmp (max_niter
, period_value
) >= 0)
3789 /* Otherwise, punt. */
3793 cand_value_at (loop
, cand
, use
->stmt
, nit
, &bnd
);
3795 *bound
= aff_combination_to_tree (&bnd
);
3796 /* It is unlikely that computing the number of iterations using division
3797 would be more profitable than keeping the original induction variable. */
3798 if (expression_expensive_p (*bound
))
3803 /* Determines cost of basing replacement of USE on CAND in a condition. */
3806 determine_use_iv_cost_condition (struct ivopts_data
*data
,
3807 struct iv_use
*use
, struct iv_cand
*cand
)
3809 tree bound
= NULL_TREE
;
3811 bitmap depends_on_elim
= NULL
, depends_on_express
= NULL
, depends_on
;
3812 comp_cost elim_cost
, express_cost
, cost
;
3815 /* Only consider real candidates. */
3818 set_use_iv_cost (data
, use
, cand
, infinite_cost
, NULL
, NULL_TREE
);
3822 /* Try iv elimination. */
3823 if (may_eliminate_iv (data
, use
, cand
, &bound
))
3825 elim_cost
= force_var_cost (data
, bound
, &depends_on_elim
);
3826 /* The bound is a loop invariant, so it will be only computed
3828 elim_cost
.cost
/= AVG_LOOP_NITER (data
->current_loop
);
3831 elim_cost
= infinite_cost
;
3833 /* Try expressing the original giv. If it is compared with an invariant,
3834 note that we cannot get rid of it. */
3835 ok
= extract_cond_operands (data
, use
->op_p
, NULL
, NULL
, NULL
, &cmp_iv
);
3838 express_cost
= get_computation_cost (data
, use
, cand
, false,
3839 &depends_on_express
);
3840 fd_ivopts_data
= data
;
3841 walk_tree (&cmp_iv
->base
, find_depends
, &depends_on_express
, NULL
);
3843 /* Choose the better approach. */
3844 if (compare_costs (elim_cost
, express_cost
) < 0)
3847 depends_on
= depends_on_elim
;
3848 depends_on_elim
= NULL
;
3852 cost
= express_cost
;
3853 depends_on
= depends_on_express
;
3854 depends_on_express
= NULL
;
3858 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, bound
);
3860 if (depends_on_elim
)
3861 BITMAP_FREE (depends_on_elim
);
3862 if (depends_on_express
)
3863 BITMAP_FREE (depends_on_express
);
3865 return !infinite_cost_p (cost
);
3868 /* Determines cost of basing replacement of USE on CAND. Returns false
3869 if USE cannot be based on CAND. */
3872 determine_use_iv_cost (struct ivopts_data
*data
,
3873 struct iv_use
*use
, struct iv_cand
*cand
)
3877 case USE_NONLINEAR_EXPR
:
3878 return determine_use_iv_cost_generic (data
, use
, cand
);
3881 return determine_use_iv_cost_address (data
, use
, cand
);
3884 return determine_use_iv_cost_condition (data
, use
, cand
);
3891 /* Determines costs of basing the use of the iv on an iv candidate. */
3894 determine_use_iv_costs (struct ivopts_data
*data
)
3898 struct iv_cand
*cand
;
3899 bitmap to_clear
= BITMAP_ALLOC (NULL
);
3901 alloc_use_cost_map (data
);
3903 for (i
= 0; i
< n_iv_uses (data
); i
++)
3905 use
= iv_use (data
, i
);
3907 if (data
->consider_all_candidates
)
3909 for (j
= 0; j
< n_iv_cands (data
); j
++)
3911 cand
= iv_cand (data
, j
);
3912 determine_use_iv_cost (data
, use
, cand
);
3919 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, j
, bi
)
3921 cand
= iv_cand (data
, j
);
3922 if (!determine_use_iv_cost (data
, use
, cand
))
3923 bitmap_set_bit (to_clear
, j
);
3926 /* Remove the candidates for that the cost is infinite from
3927 the list of related candidates. */
3928 bitmap_and_compl_into (use
->related_cands
, to_clear
);
3929 bitmap_clear (to_clear
);
3933 BITMAP_FREE (to_clear
);
3935 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3937 fprintf (dump_file
, "Use-candidate costs:\n");
3939 for (i
= 0; i
< n_iv_uses (data
); i
++)
3941 use
= iv_use (data
, i
);
3943 fprintf (dump_file
, "Use %d:\n", i
);
3944 fprintf (dump_file
, " cand\tcost\tcompl.\tdepends on\n");
3945 for (j
= 0; j
< use
->n_map_members
; j
++)
3947 if (!use
->cost_map
[j
].cand
3948 || infinite_cost_p (use
->cost_map
[j
].cost
))
3951 fprintf (dump_file
, " %d\t%d\t%d\t",
3952 use
->cost_map
[j
].cand
->id
,
3953 use
->cost_map
[j
].cost
.cost
,
3954 use
->cost_map
[j
].cost
.complexity
);
3955 if (use
->cost_map
[j
].depends_on
)
3956 bitmap_print (dump_file
,
3957 use
->cost_map
[j
].depends_on
, "","");
3958 fprintf (dump_file
, "\n");
3961 fprintf (dump_file
, "\n");
3963 fprintf (dump_file
, "\n");
3967 /* Determines cost of the candidate CAND. */
3970 determine_iv_cost (struct ivopts_data
*data
, struct iv_cand
*cand
)
3972 comp_cost cost_base
;
3973 unsigned cost
, cost_step
;
3982 /* There are two costs associated with the candidate -- its increment
3983 and its initialization. The second is almost negligible for any loop
3984 that rolls enough, so we take it just very little into account. */
3986 base
= cand
->iv
->base
;
3987 cost_base
= force_var_cost (data
, base
, NULL
);
3988 cost_step
= add_cost (TYPE_MODE (TREE_TYPE (base
)));
3990 cost
= cost_step
+ cost_base
.cost
/ AVG_LOOP_NITER (current_loop
);
3992 /* Prefer the original ivs unless we may gain something by replacing it.
3993 The reason is to makee debugging simpler; so this is not relevant for
3994 artificial ivs created by other optimization passes. */
3995 if (cand
->pos
!= IP_ORIGINAL
3996 || DECL_ARTIFICIAL (SSA_NAME_VAR (cand
->var_before
)))
3999 /* Prefer not to insert statements into latch unless there are some
4000 already (so that we do not create unnecessary jumps). */
4001 if (cand
->pos
== IP_END
4002 && empty_block_p (ip_end_pos (data
->current_loop
)))
4008 /* Determines costs of computation of the candidates. */
4011 determine_iv_costs (struct ivopts_data
*data
)
4015 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4017 fprintf (dump_file
, "Candidate costs:\n");
4018 fprintf (dump_file
, " cand\tcost\n");
4021 for (i
= 0; i
< n_iv_cands (data
); i
++)
4023 struct iv_cand
*cand
= iv_cand (data
, i
);
4025 determine_iv_cost (data
, cand
);
4027 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4028 fprintf (dump_file
, " %d\t%d\n", i
, cand
->cost
);
4031 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4032 fprintf (dump_file
, "\n");
4035 /* Calculates cost for having SIZE induction variables. */
4038 ivopts_global_cost_for_size (struct ivopts_data
*data
, unsigned size
)
4040 /* We add size to the cost, so that we prefer eliminating ivs
4042 return size
+ estimate_reg_pressure_cost (size
, data
->regs_used
);
4045 /* For each size of the induction variable set determine the penalty. */
4048 determine_set_costs (struct ivopts_data
*data
)
4052 struct loop
*loop
= data
->current_loop
;
4055 /* We use the following model (definitely improvable, especially the
4056 cost function -- TODO):
4058 We estimate the number of registers available (using MD data), name it A.
4060 We estimate the number of registers used by the loop, name it U. This
4061 number is obtained as the number of loop phi nodes (not counting virtual
4062 registers and bivs) + the number of variables from outside of the loop.
4064 We set a reserve R (free regs that are used for temporary computations,
4065 etc.). For now the reserve is a constant 3.
4067 Let I be the number of induction variables.
4069 -- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
4070 make a lot of ivs without a reason).
4071 -- if A - R < U + I <= A, the cost is I * PRES_COST
4072 -- if U + I > A, the cost is I * PRES_COST and
4073 number of uses * SPILL_COST * (U + I - A) / (U + I) is added. */
4075 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4077 fprintf (dump_file
, "Global costs:\n");
4078 fprintf (dump_file
, " target_avail_regs %d\n", target_avail_regs
);
4079 fprintf (dump_file
, " target_reg_cost %d\n", target_reg_cost
);
4080 fprintf (dump_file
, " target_spill_cost %d\n", target_spill_cost
);
4084 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
4086 op
= PHI_RESULT (phi
);
4088 if (!is_gimple_reg (op
))
4091 if (get_iv (data
, op
))
4097 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
4099 struct version_info
*info
= ver_info (data
, j
);
4101 if (info
->inv_id
&& info
->has_nonlin_use
)
4105 data
->regs_used
= n
;
4106 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4107 fprintf (dump_file
, " regs_used %d\n", n
);
4109 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4111 fprintf (dump_file
, " cost for size:\n");
4112 fprintf (dump_file
, " ivs\tcost\n");
4113 for (j
= 0; j
<= 2 * target_avail_regs
; j
++)
4114 fprintf (dump_file
, " %d\t%d\n", j
,
4115 ivopts_global_cost_for_size (data
, j
));
4116 fprintf (dump_file
, "\n");
4120 /* Returns true if A is a cheaper cost pair than B. */
4123 cheaper_cost_pair (struct cost_pair
*a
, struct cost_pair
*b
)
4133 cmp
= compare_costs (a
->cost
, b
->cost
);
4140 /* In case the costs are the same, prefer the cheaper candidate. */
4141 if (a
->cand
->cost
< b
->cand
->cost
)
4147 /* Computes the cost field of IVS structure. */
4150 iv_ca_recount_cost (struct ivopts_data
*data
, struct iv_ca
*ivs
)
4152 comp_cost cost
= ivs
->cand_use_cost
;
4153 cost
.cost
+= ivs
->cand_cost
;
4154 cost
.cost
+= ivopts_global_cost_for_size (data
, ivs
->n_regs
);
4159 /* Remove invariants in set INVS to set IVS. */
4162 iv_ca_set_remove_invariants (struct iv_ca
*ivs
, bitmap invs
)
4170 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
4172 ivs
->n_invariant_uses
[iid
]--;
4173 if (ivs
->n_invariant_uses
[iid
] == 0)
4178 /* Set USE not to be expressed by any candidate in IVS. */
4181 iv_ca_set_no_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4184 unsigned uid
= use
->id
, cid
;
4185 struct cost_pair
*cp
;
4187 cp
= ivs
->cand_for_use
[uid
];
4193 ivs
->cand_for_use
[uid
] = NULL
;
4194 ivs
->n_cand_uses
[cid
]--;
4196 if (ivs
->n_cand_uses
[cid
] == 0)
4198 bitmap_clear_bit (ivs
->cands
, cid
);
4199 /* Do not count the pseudocandidates. */
4203 ivs
->cand_cost
-= cp
->cand
->cost
;
4205 iv_ca_set_remove_invariants (ivs
, cp
->cand
->depends_on
);
4208 ivs
->cand_use_cost
= sub_costs (ivs
->cand_use_cost
, cp
->cost
);
4210 iv_ca_set_remove_invariants (ivs
, cp
->depends_on
);
4211 iv_ca_recount_cost (data
, ivs
);
4214 /* Add invariants in set INVS to set IVS. */
4217 iv_ca_set_add_invariants (struct iv_ca
*ivs
, bitmap invs
)
4225 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
4227 ivs
->n_invariant_uses
[iid
]++;
4228 if (ivs
->n_invariant_uses
[iid
] == 1)
4233 /* Set cost pair for USE in set IVS to CP. */
4236 iv_ca_set_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4237 struct iv_use
*use
, struct cost_pair
*cp
)
4239 unsigned uid
= use
->id
, cid
;
4241 if (ivs
->cand_for_use
[uid
] == cp
)
4244 if (ivs
->cand_for_use
[uid
])
4245 iv_ca_set_no_cp (data
, ivs
, use
);
4252 ivs
->cand_for_use
[uid
] = cp
;
4253 ivs
->n_cand_uses
[cid
]++;
4254 if (ivs
->n_cand_uses
[cid
] == 1)
4256 bitmap_set_bit (ivs
->cands
, cid
);
4257 /* Do not count the pseudocandidates. */
4261 ivs
->cand_cost
+= cp
->cand
->cost
;
4263 iv_ca_set_add_invariants (ivs
, cp
->cand
->depends_on
);
4266 ivs
->cand_use_cost
= add_costs (ivs
->cand_use_cost
, cp
->cost
);
4267 iv_ca_set_add_invariants (ivs
, cp
->depends_on
);
4268 iv_ca_recount_cost (data
, ivs
);
4272 /* Extend set IVS by expressing USE by some of the candidates in it
4276 iv_ca_add_use (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4279 struct cost_pair
*best_cp
= NULL
, *cp
;
4283 gcc_assert (ivs
->upto
>= use
->id
);
4285 if (ivs
->upto
== use
->id
)
4291 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
4293 cp
= get_use_iv_cost (data
, use
, iv_cand (data
, i
));
4295 if (cheaper_cost_pair (cp
, best_cp
))
4299 iv_ca_set_cp (data
, ivs
, use
, best_cp
);
4302 /* Get cost for assignment IVS. */
4305 iv_ca_cost (struct iv_ca
*ivs
)
4307 return (ivs
->bad_uses
? infinite_cost
: ivs
->cost
);
4310 /* Returns true if all dependences of CP are among invariants in IVS. */
4313 iv_ca_has_deps (struct iv_ca
*ivs
, struct cost_pair
*cp
)
4318 if (!cp
->depends_on
)
4321 EXECUTE_IF_SET_IN_BITMAP (cp
->depends_on
, 0, i
, bi
)
4323 if (ivs
->n_invariant_uses
[i
] == 0)
4330 /* Creates change of expressing USE by NEW_CP instead of OLD_CP and chains
4331 it before NEXT_CHANGE. */
4333 static struct iv_ca_delta
*
4334 iv_ca_delta_add (struct iv_use
*use
, struct cost_pair
*old_cp
,
4335 struct cost_pair
*new_cp
, struct iv_ca_delta
*next_change
)
4337 struct iv_ca_delta
*change
= XNEW (struct iv_ca_delta
);
4340 change
->old_cp
= old_cp
;
4341 change
->new_cp
= new_cp
;
4342 change
->next_change
= next_change
;
4347 /* Joins two lists of changes L1 and L2. Destructive -- old lists
4350 static struct iv_ca_delta
*
4351 iv_ca_delta_join (struct iv_ca_delta
*l1
, struct iv_ca_delta
*l2
)
4353 struct iv_ca_delta
*last
;
4361 for (last
= l1
; last
->next_change
; last
= last
->next_change
)
4363 last
->next_change
= l2
;
4368 /* Returns candidate by that USE is expressed in IVS. */
4370 static struct cost_pair
*
4371 iv_ca_cand_for_use (struct iv_ca
*ivs
, struct iv_use
*use
)
4373 return ivs
->cand_for_use
[use
->id
];
4376 /* Reverse the list of changes DELTA, forming the inverse to it. */
4378 static struct iv_ca_delta
*
4379 iv_ca_delta_reverse (struct iv_ca_delta
*delta
)
4381 struct iv_ca_delta
*act
, *next
, *prev
= NULL
;
4382 struct cost_pair
*tmp
;
4384 for (act
= delta
; act
; act
= next
)
4386 next
= act
->next_change
;
4387 act
->next_change
= prev
;
4391 act
->old_cp
= act
->new_cp
;
4398 /* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
4399 reverted instead. */
4402 iv_ca_delta_commit (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4403 struct iv_ca_delta
*delta
, bool forward
)
4405 struct cost_pair
*from
, *to
;
4406 struct iv_ca_delta
*act
;
4409 delta
= iv_ca_delta_reverse (delta
);
4411 for (act
= delta
; act
; act
= act
->next_change
)
4415 gcc_assert (iv_ca_cand_for_use (ivs
, act
->use
) == from
);
4416 iv_ca_set_cp (data
, ivs
, act
->use
, to
);
4420 iv_ca_delta_reverse (delta
);
4423 /* Returns true if CAND is used in IVS. */
4426 iv_ca_cand_used_p (struct iv_ca
*ivs
, struct iv_cand
*cand
)
4428 return ivs
->n_cand_uses
[cand
->id
] > 0;
4431 /* Returns number of induction variable candidates in the set IVS. */
4434 iv_ca_n_cands (struct iv_ca
*ivs
)
4436 return ivs
->n_cands
;
4439 /* Free the list of changes DELTA. */
4442 iv_ca_delta_free (struct iv_ca_delta
**delta
)
4444 struct iv_ca_delta
*act
, *next
;
4446 for (act
= *delta
; act
; act
= next
)
4448 next
= act
->next_change
;
4455 /* Allocates new iv candidates assignment. */
4457 static struct iv_ca
*
4458 iv_ca_new (struct ivopts_data
*data
)
4460 struct iv_ca
*nw
= XNEW (struct iv_ca
);
4464 nw
->cand_for_use
= XCNEWVEC (struct cost_pair
*, n_iv_uses (data
));
4465 nw
->n_cand_uses
= XCNEWVEC (unsigned, n_iv_cands (data
));
4466 nw
->cands
= BITMAP_ALLOC (NULL
);
4469 nw
->cand_use_cost
= zero_cost
;
4471 nw
->n_invariant_uses
= XCNEWVEC (unsigned, data
->max_inv_id
+ 1);
4472 nw
->cost
= zero_cost
;
4477 /* Free memory occupied by the set IVS. */
4480 iv_ca_free (struct iv_ca
**ivs
)
4482 free ((*ivs
)->cand_for_use
);
4483 free ((*ivs
)->n_cand_uses
);
4484 BITMAP_FREE ((*ivs
)->cands
);
4485 free ((*ivs
)->n_invariant_uses
);
4490 /* Dumps IVS to FILE. */
4493 iv_ca_dump (struct ivopts_data
*data
, FILE *file
, struct iv_ca
*ivs
)
4495 const char *pref
= " invariants ";
4497 comp_cost cost
= iv_ca_cost (ivs
);
4499 fprintf (file
, " cost %d (complexity %d)\n", cost
.cost
, cost
.complexity
);
4500 bitmap_print (file
, ivs
->cands
, " candidates ","\n");
4502 for (i
= 1; i
<= data
->max_inv_id
; i
++)
4503 if (ivs
->n_invariant_uses
[i
])
4505 fprintf (file
, "%s%d", pref
, i
);
4508 fprintf (file
, "\n");
4511 /* Try changing candidate in IVS to CAND for each use. Return cost of the
4512 new set, and store differences in DELTA. Number of induction variables
4513 in the new set is stored to N_IVS. */
4516 iv_ca_extend (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4517 struct iv_cand
*cand
, struct iv_ca_delta
**delta
,
4523 struct cost_pair
*old_cp
, *new_cp
;
4526 for (i
= 0; i
< ivs
->upto
; i
++)
4528 use
= iv_use (data
, i
);
4529 old_cp
= iv_ca_cand_for_use (ivs
, use
);
4532 && old_cp
->cand
== cand
)
4535 new_cp
= get_use_iv_cost (data
, use
, cand
);
4539 if (!iv_ca_has_deps (ivs
, new_cp
))
4542 if (!cheaper_cost_pair (new_cp
, old_cp
))
4545 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
4548 iv_ca_delta_commit (data
, ivs
, *delta
, true);
4549 cost
= iv_ca_cost (ivs
);
4551 *n_ivs
= iv_ca_n_cands (ivs
);
4552 iv_ca_delta_commit (data
, ivs
, *delta
, false);
4557 /* Try narrowing set IVS by removing CAND. Return the cost of
4558 the new set and store the differences in DELTA. */
4561 iv_ca_narrow (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4562 struct iv_cand
*cand
, struct iv_ca_delta
**delta
)
4566 struct cost_pair
*old_cp
, *new_cp
, *cp
;
4568 struct iv_cand
*cnd
;
4572 for (i
= 0; i
< n_iv_uses (data
); i
++)
4574 use
= iv_use (data
, i
);
4576 old_cp
= iv_ca_cand_for_use (ivs
, use
);
4577 if (old_cp
->cand
!= cand
)
4582 if (data
->consider_all_candidates
)
4584 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, ci
, bi
)
4589 cnd
= iv_cand (data
, ci
);
4591 cp
= get_use_iv_cost (data
, use
, cnd
);
4594 if (!iv_ca_has_deps (ivs
, cp
))
4597 if (!cheaper_cost_pair (cp
, new_cp
))
4605 EXECUTE_IF_AND_IN_BITMAP (use
->related_cands
, ivs
->cands
, 0, ci
, bi
)
4610 cnd
= iv_cand (data
, ci
);
4612 cp
= get_use_iv_cost (data
, use
, cnd
);
4615 if (!iv_ca_has_deps (ivs
, cp
))
4618 if (!cheaper_cost_pair (cp
, new_cp
))
4627 iv_ca_delta_free (delta
);
4628 return infinite_cost
;
4631 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
4634 iv_ca_delta_commit (data
, ivs
, *delta
, true);
4635 cost
= iv_ca_cost (ivs
);
4636 iv_ca_delta_commit (data
, ivs
, *delta
, false);
4641 /* Try optimizing the set of candidates IVS by removing candidates different
4642 from to EXCEPT_CAND from it. Return cost of the new set, and store
4643 differences in DELTA. */
4646 iv_ca_prune (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4647 struct iv_cand
*except_cand
, struct iv_ca_delta
**delta
)
4650 struct iv_ca_delta
*act_delta
, *best_delta
;
4652 comp_cost best_cost
, acost
;
4653 struct iv_cand
*cand
;
4656 best_cost
= iv_ca_cost (ivs
);
4658 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
4660 cand
= iv_cand (data
, i
);
4662 if (cand
== except_cand
)
4665 acost
= iv_ca_narrow (data
, ivs
, cand
, &act_delta
);
4667 if (compare_costs (acost
, best_cost
) < 0)
4670 iv_ca_delta_free (&best_delta
);
4671 best_delta
= act_delta
;
4674 iv_ca_delta_free (&act_delta
);
4683 /* Recurse to possibly remove other unnecessary ivs. */
4684 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
4685 best_cost
= iv_ca_prune (data
, ivs
, except_cand
, delta
);
4686 iv_ca_delta_commit (data
, ivs
, best_delta
, false);
4687 *delta
= iv_ca_delta_join (best_delta
, *delta
);
4691 /* Tries to extend the sets IVS in the best possible way in order
4692 to express the USE. */
4695 try_add_cand_for (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4698 comp_cost best_cost
, act_cost
;
4701 struct iv_cand
*cand
;
4702 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
;
4703 struct cost_pair
*cp
;
4705 iv_ca_add_use (data
, ivs
, use
);
4706 best_cost
= iv_ca_cost (ivs
);
4708 cp
= iv_ca_cand_for_use (ivs
, use
);
4711 best_delta
= iv_ca_delta_add (use
, NULL
, cp
, NULL
);
4712 iv_ca_set_no_cp (data
, ivs
, use
);
4715 /* First try important candidates not based on any memory object. Only if
4716 this fails, try the specific ones. Rationale -- in loops with many
4717 variables the best choice often is to use just one generic biv. If we
4718 added here many ivs specific to the uses, the optimization algorithm later
4719 would be likely to get stuck in a local minimum, thus causing us to create
4720 too many ivs. The approach from few ivs to more seems more likely to be
4721 successful -- starting from few ivs, replacing an expensive use by a
4722 specific iv should always be a win. */
4723 EXECUTE_IF_SET_IN_BITMAP (data
->important_candidates
, 0, i
, bi
)
4725 cand
= iv_cand (data
, i
);
4727 if (cand
->iv
->base_object
!= NULL_TREE
)
4730 if (iv_ca_cand_used_p (ivs
, cand
))
4733 cp
= get_use_iv_cost (data
, use
, cand
);
4737 iv_ca_set_cp (data
, ivs
, use
, cp
);
4738 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
);
4739 iv_ca_set_no_cp (data
, ivs
, use
);
4740 act_delta
= iv_ca_delta_add (use
, NULL
, cp
, act_delta
);
4742 if (compare_costs (act_cost
, best_cost
) < 0)
4744 best_cost
= act_cost
;
4746 iv_ca_delta_free (&best_delta
);
4747 best_delta
= act_delta
;
4750 iv_ca_delta_free (&act_delta
);
4753 if (infinite_cost_p (best_cost
))
4755 for (i
= 0; i
< use
->n_map_members
; i
++)
4757 cp
= use
->cost_map
+ i
;
4762 /* Already tried this. */
4763 if (cand
->important
&& cand
->iv
->base_object
== NULL_TREE
)
4766 if (iv_ca_cand_used_p (ivs
, cand
))
4770 iv_ca_set_cp (data
, ivs
, use
, cp
);
4771 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
);
4772 iv_ca_set_no_cp (data
, ivs
, use
);
4773 act_delta
= iv_ca_delta_add (use
, iv_ca_cand_for_use (ivs
, use
),
4776 if (compare_costs (act_cost
, best_cost
) < 0)
4778 best_cost
= act_cost
;
4781 iv_ca_delta_free (&best_delta
);
4782 best_delta
= act_delta
;
4785 iv_ca_delta_free (&act_delta
);
4789 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
4790 iv_ca_delta_free (&best_delta
);
4792 return !infinite_cost_p (best_cost
);
4795 /* Finds an initial assignment of candidates to uses. */
4797 static struct iv_ca
*
4798 get_initial_solution (struct ivopts_data
*data
)
4800 struct iv_ca
*ivs
= iv_ca_new (data
);
4803 for (i
= 0; i
< n_iv_uses (data
); i
++)
4804 if (!try_add_cand_for (data
, ivs
, iv_use (data
, i
)))
4813 /* Tries to improve set of induction variables IVS. */
4816 try_improve_iv_set (struct ivopts_data
*data
, struct iv_ca
*ivs
)
4819 comp_cost acost
, best_cost
= iv_ca_cost (ivs
);
4820 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
, *tmp_delta
;
4821 struct iv_cand
*cand
;
4823 /* Try extending the set of induction variables by one. */
4824 for (i
= 0; i
< n_iv_cands (data
); i
++)
4826 cand
= iv_cand (data
, i
);
4828 if (iv_ca_cand_used_p (ivs
, cand
))
4831 acost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, &n_ivs
);
4835 /* If we successfully added the candidate and the set is small enough,
4836 try optimizing it by removing other candidates. */
4837 if (n_ivs
<= ALWAYS_PRUNE_CAND_SET_BOUND
)
4839 iv_ca_delta_commit (data
, ivs
, act_delta
, true);
4840 acost
= iv_ca_prune (data
, ivs
, cand
, &tmp_delta
);
4841 iv_ca_delta_commit (data
, ivs
, act_delta
, false);
4842 act_delta
= iv_ca_delta_join (act_delta
, tmp_delta
);
4845 if (compare_costs (acost
, best_cost
) < 0)
4848 iv_ca_delta_free (&best_delta
);
4849 best_delta
= act_delta
;
4852 iv_ca_delta_free (&act_delta
);
4857 /* Try removing the candidates from the set instead. */
4858 best_cost
= iv_ca_prune (data
, ivs
, NULL
, &best_delta
);
4860 /* Nothing more we can do. */
4865 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
4866 gcc_assert (compare_costs (best_cost
, iv_ca_cost (ivs
)) == 0);
4867 iv_ca_delta_free (&best_delta
);
4871 /* Attempts to find the optimal set of induction variables. We do simple
4872 greedy heuristic -- we try to replace at most one candidate in the selected
4873 solution and remove the unused ivs while this improves the cost. */
4875 static struct iv_ca
*
4876 find_optimal_iv_set (struct ivopts_data
*data
)
4882 /* Get the initial solution. */
4883 set
= get_initial_solution (data
);
4886 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4887 fprintf (dump_file
, "Unable to substitute for ivs, failed.\n");
4891 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4893 fprintf (dump_file
, "Initial set of candidates:\n");
4894 iv_ca_dump (data
, dump_file
, set
);
4897 while (try_improve_iv_set (data
, set
))
4899 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4901 fprintf (dump_file
, "Improved to:\n");
4902 iv_ca_dump (data
, dump_file
, set
);
4906 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4908 comp_cost cost
= iv_ca_cost (set
);
4909 fprintf (dump_file
, "Final cost %d (complexity %d)\n\n", cost
.cost
, cost
.complexity
);
4912 for (i
= 0; i
< n_iv_uses (data
); i
++)
4914 use
= iv_use (data
, i
);
4915 use
->selected
= iv_ca_cand_for_use (set
, use
)->cand
;
4921 /* Creates a new induction variable corresponding to CAND. */
4924 create_new_iv (struct ivopts_data
*data
, struct iv_cand
*cand
)
4926 block_stmt_iterator incr_pos
;
4936 incr_pos
= bsi_last (ip_normal_pos (data
->current_loop
));
4940 incr_pos
= bsi_last (ip_end_pos (data
->current_loop
));
4945 /* Mark that the iv is preserved. */
4946 name_info (data
, cand
->var_before
)->preserve_biv
= true;
4947 name_info (data
, cand
->var_after
)->preserve_biv
= true;
4949 /* Rewrite the increment so that it uses var_before directly. */
4950 find_interesting_uses_op (data
, cand
->var_after
)->selected
= cand
;
4955 gimple_add_tmp_var (cand
->var_before
);
4956 add_referenced_var (cand
->var_before
);
4958 base
= unshare_expr (cand
->iv
->base
);
4960 create_iv (base
, unshare_expr (cand
->iv
->step
),
4961 cand
->var_before
, data
->current_loop
,
4962 &incr_pos
, after
, &cand
->var_before
, &cand
->var_after
);
4965 /* Creates new induction variables described in SET. */
4968 create_new_ivs (struct ivopts_data
*data
, struct iv_ca
*set
)
4971 struct iv_cand
*cand
;
4974 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
4976 cand
= iv_cand (data
, i
);
4977 create_new_iv (data
, cand
);
4981 /* Removes statement STMT (real or a phi node). If INCLUDING_DEFINED_NAME
4982 is true, remove also the ssa name defined by the statement. */
4985 remove_statement (tree stmt
, bool including_defined_name
)
4987 if (TREE_CODE (stmt
) == PHI_NODE
)
4989 remove_phi_node (stmt
, NULL_TREE
, including_defined_name
);
4993 block_stmt_iterator bsi
= bsi_for_stmt (stmt
);
4995 bsi_remove (&bsi
, true);
4996 release_defs (stmt
);
5000 /* Rewrites USE (definition of iv used in a nonlinear expression)
5001 using candidate CAND. */
5004 rewrite_use_nonlinear_expr (struct ivopts_data
*data
,
5005 struct iv_use
*use
, struct iv_cand
*cand
)
5009 block_stmt_iterator bsi
;
5011 /* An important special case -- if we are asked to express value of
5012 the original iv by itself, just exit; there is no need to
5013 introduce a new computation (that might also need casting the
5014 variable to unsigned and back). */
5015 if (cand
->pos
== IP_ORIGINAL
5016 && cand
->incremented_at
== use
->stmt
)
5018 tree step
, ctype
, utype
;
5019 enum tree_code incr_code
= PLUS_EXPR
;
5021 gcc_assert (TREE_CODE (use
->stmt
) == GIMPLE_MODIFY_STMT
);
5022 gcc_assert (GIMPLE_STMT_OPERAND (use
->stmt
, 0) == cand
->var_after
);
5024 step
= cand
->iv
->step
;
5025 ctype
= TREE_TYPE (step
);
5026 utype
= TREE_TYPE (cand
->var_after
);
5027 if (TREE_CODE (step
) == NEGATE_EXPR
)
5029 incr_code
= MINUS_EXPR
;
5030 step
= TREE_OPERAND (step
, 0);
5033 /* Check whether we may leave the computation unchanged.
5034 This is the case only if it does not rely on other
5035 computations in the loop -- otherwise, the computation
5036 we rely upon may be removed in remove_unused_ivs,
5037 thus leading to ICE. */
5038 op
= GIMPLE_STMT_OPERAND (use
->stmt
, 1);
5039 if (TREE_CODE (op
) == PLUS_EXPR
5040 || TREE_CODE (op
) == MINUS_EXPR
5041 || TREE_CODE (op
) == POINTER_PLUS_EXPR
)
5043 if (TREE_OPERAND (op
, 0) == cand
->var_before
)
5044 op
= TREE_OPERAND (op
, 1);
5045 else if (TREE_CODE (op
) != MINUS_EXPR
5046 && TREE_OPERAND (op
, 1) == cand
->var_before
)
5047 op
= TREE_OPERAND (op
, 0);
5055 && (TREE_CODE (op
) == INTEGER_CST
5056 || operand_equal_p (op
, step
, 0)))
5059 /* Otherwise, add the necessary computations to express
5061 op
= fold_convert (ctype
, cand
->var_before
);
5062 comp
= fold_convert (utype
,
5063 build2 (incr_code
, ctype
, op
,
5064 unshare_expr (step
)));
5068 comp
= get_computation (data
->current_loop
, use
, cand
);
5069 gcc_assert (comp
!= NULL_TREE
);
5072 switch (TREE_CODE (use
->stmt
))
5075 tgt
= PHI_RESULT (use
->stmt
);
5077 /* If we should keep the biv, do not replace it. */
5078 if (name_info (data
, tgt
)->preserve_biv
)
5081 bsi
= bsi_after_labels (bb_for_stmt (use
->stmt
));
5084 case GIMPLE_MODIFY_STMT
:
5085 tgt
= GIMPLE_STMT_OPERAND (use
->stmt
, 0);
5086 bsi
= bsi_for_stmt (use
->stmt
);
5093 op
= force_gimple_operand_bsi (&bsi
, comp
, false, SSA_NAME_VAR (tgt
),
5094 true, BSI_SAME_STMT
);
5096 if (TREE_CODE (use
->stmt
) == PHI_NODE
)
5098 ass
= build_gimple_modify_stmt (tgt
, op
);
5099 bsi_insert_before (&bsi
, ass
, BSI_SAME_STMT
);
5100 remove_statement (use
->stmt
, false);
5101 SSA_NAME_DEF_STMT (tgt
) = ass
;
5104 GIMPLE_STMT_OPERAND (use
->stmt
, 1) = op
;
5107 /* Replaces ssa name in index IDX by its basic variable. Callback for
5111 idx_remove_ssa_names (tree base
, tree
*idx
,
5112 void *data ATTRIBUTE_UNUSED
)
5116 if (TREE_CODE (*idx
) == SSA_NAME
)
5117 *idx
= SSA_NAME_VAR (*idx
);
5119 if (TREE_CODE (base
) == ARRAY_REF
)
5121 op
= &TREE_OPERAND (base
, 2);
5123 && TREE_CODE (*op
) == SSA_NAME
)
5124 *op
= SSA_NAME_VAR (*op
);
5125 op
= &TREE_OPERAND (base
, 3);
5127 && TREE_CODE (*op
) == SSA_NAME
)
5128 *op
= SSA_NAME_VAR (*op
);
5134 /* Unshares REF and replaces ssa names inside it by their basic variables. */
5137 unshare_and_remove_ssa_names (tree ref
)
5139 ref
= unshare_expr (ref
);
5140 for_each_index (&ref
, idx_remove_ssa_names
, NULL
);
5145 /* Extract the alias analysis info for the memory reference REF. There are
5146 several ways how this information may be stored and what precisely is
5147 its semantics depending on the type of the reference, but there always is
5148 somewhere hidden one _DECL node that is used to determine the set of
5149 virtual operands for the reference. The code below deciphers this jungle
5150 and extracts this single useful piece of information. */
5153 get_ref_tag (tree ref
, tree orig
)
5155 tree var
= get_base_address (ref
);
5156 tree aref
= NULL_TREE
, tag
, sv
;
5157 HOST_WIDE_INT offset
, size
, maxsize
;
5159 for (sv
= orig
; handled_component_p (sv
); sv
= TREE_OPERAND (sv
, 0))
5161 aref
= get_ref_base_and_extent (sv
, &offset
, &size
, &maxsize
);
5166 if (aref
&& SSA_VAR_P (aref
) && get_subvars_for_var (aref
))
5172 if (TREE_CODE (var
) == INDIRECT_REF
)
5174 /* If the base is a dereference of a pointer, first check its name memory
5175 tag. If it does not have one, use its symbol memory tag. */
5176 var
= TREE_OPERAND (var
, 0);
5177 if (TREE_CODE (var
) != SSA_NAME
)
5180 if (SSA_NAME_PTR_INFO (var
))
5182 tag
= SSA_NAME_PTR_INFO (var
)->name_mem_tag
;
5187 var
= SSA_NAME_VAR (var
);
5188 tag
= symbol_mem_tag (var
);
5189 gcc_assert (tag
!= NULL_TREE
);
5197 tag
= symbol_mem_tag (var
);
5205 /* Copies the reference information from OLD_REF to NEW_REF. */
5208 copy_ref_info (tree new_ref
, tree old_ref
)
5210 if (TREE_CODE (old_ref
) == TARGET_MEM_REF
)
5211 copy_mem_ref_info (new_ref
, old_ref
);
5214 TMR_ORIGINAL (new_ref
) = unshare_and_remove_ssa_names (old_ref
);
5215 TMR_TAG (new_ref
) = get_ref_tag (old_ref
, TMR_ORIGINAL (new_ref
));
5219 /* Rewrites USE (address that is an iv) using candidate CAND. */
5222 rewrite_use_address (struct ivopts_data
*data
,
5223 struct iv_use
*use
, struct iv_cand
*cand
)
5226 block_stmt_iterator bsi
= bsi_for_stmt (use
->stmt
);
5230 ok
= get_computation_aff (data
->current_loop
, use
, cand
, use
->stmt
, &aff
);
5232 unshare_aff_combination (&aff
);
5234 ref
= create_mem_ref (&bsi
, TREE_TYPE (*use
->op_p
), &aff
);
5235 copy_ref_info (ref
, *use
->op_p
);
5239 /* Rewrites USE (the condition such that one of the arguments is an iv) using
5243 rewrite_use_compare (struct ivopts_data
*data
,
5244 struct iv_use
*use
, struct iv_cand
*cand
)
5246 tree comp
, *var_p
, op
, bound
;
5247 block_stmt_iterator bsi
= bsi_for_stmt (use
->stmt
);
5248 enum tree_code compare
;
5249 struct cost_pair
*cp
= get_use_iv_cost (data
, use
, cand
);
5255 tree var
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
5256 tree var_type
= TREE_TYPE (var
);
5258 compare
= iv_elimination_compare (data
, use
);
5259 bound
= unshare_expr (fold_convert (var_type
, bound
));
5260 op
= force_gimple_operand_bsi (&bsi
, bound
, true, NULL_TREE
,
5261 true, BSI_SAME_STMT
);
5263 *use
->op_p
= build2 (compare
, boolean_type_node
, var
, op
);
5267 /* The induction variable elimination failed; just express the original
5269 comp
= get_computation (data
->current_loop
, use
, cand
);
5270 gcc_assert (comp
!= NULL_TREE
);
5272 ok
= extract_cond_operands (data
, use
->op_p
, &var_p
, NULL
, NULL
, NULL
);
5275 *var_p
= force_gimple_operand_bsi (&bsi
, comp
, true, SSA_NAME_VAR (*var_p
),
5276 true, BSI_SAME_STMT
);
5279 /* Rewrites USE using candidate CAND. */
5282 rewrite_use (struct ivopts_data
*data
, struct iv_use
*use
, struct iv_cand
*cand
)
5284 push_stmt_changes (&use
->stmt
);
5288 case USE_NONLINEAR_EXPR
:
5289 rewrite_use_nonlinear_expr (data
, use
, cand
);
5293 rewrite_use_address (data
, use
, cand
);
5297 rewrite_use_compare (data
, use
, cand
);
5304 pop_stmt_changes (&use
->stmt
);
5307 /* Rewrite the uses using the selected induction variables. */
5310 rewrite_uses (struct ivopts_data
*data
)
5313 struct iv_cand
*cand
;
5316 for (i
= 0; i
< n_iv_uses (data
); i
++)
5318 use
= iv_use (data
, i
);
5319 cand
= use
->selected
;
5322 rewrite_use (data
, use
, cand
);
5326 /* Removes the ivs that are not used after rewriting. */
5329 remove_unused_ivs (struct ivopts_data
*data
)
5334 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
5336 struct version_info
*info
;
5338 info
= ver_info (data
, j
);
5340 && !integer_zerop (info
->iv
->step
)
5342 && !info
->iv
->have_use_for
5343 && !info
->preserve_biv
)
5344 remove_statement (SSA_NAME_DEF_STMT (info
->iv
->ssa_name
), true);
5348 /* Frees data allocated by the optimization of a single loop. */
5351 free_loop_data (struct ivopts_data
*data
)
5359 pointer_map_destroy (data
->niters
);
5360 data
->niters
= NULL
;
5363 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
5365 struct version_info
*info
;
5367 info
= ver_info (data
, i
);
5371 info
->has_nonlin_use
= false;
5372 info
->preserve_biv
= false;
5375 bitmap_clear (data
->relevant
);
5376 bitmap_clear (data
->important_candidates
);
5378 for (i
= 0; i
< n_iv_uses (data
); i
++)
5380 struct iv_use
*use
= iv_use (data
, i
);
5383 BITMAP_FREE (use
->related_cands
);
5384 for (j
= 0; j
< use
->n_map_members
; j
++)
5385 if (use
->cost_map
[j
].depends_on
)
5386 BITMAP_FREE (use
->cost_map
[j
].depends_on
);
5387 free (use
->cost_map
);
5390 VEC_truncate (iv_use_p
, data
->iv_uses
, 0);
5392 for (i
= 0; i
< n_iv_cands (data
); i
++)
5394 struct iv_cand
*cand
= iv_cand (data
, i
);
5398 if (cand
->depends_on
)
5399 BITMAP_FREE (cand
->depends_on
);
5402 VEC_truncate (iv_cand_p
, data
->iv_candidates
, 0);
5404 if (data
->version_info_size
< num_ssa_names
)
5406 data
->version_info_size
= 2 * num_ssa_names
;
5407 free (data
->version_info
);
5408 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
5411 data
->max_inv_id
= 0;
5413 for (i
= 0; VEC_iterate (tree
, decl_rtl_to_reset
, i
, obj
); i
++)
5414 SET_DECL_RTL (obj
, NULL_RTX
);
5416 VEC_truncate (tree
, decl_rtl_to_reset
, 0);
5419 /* Finalizes data structures used by the iv optimization pass. LOOPS is the
5423 tree_ssa_iv_optimize_finalize (struct ivopts_data
*data
)
5425 free_loop_data (data
);
5426 free (data
->version_info
);
5427 BITMAP_FREE (data
->relevant
);
5428 BITMAP_FREE (data
->important_candidates
);
5430 VEC_free (tree
, heap
, decl_rtl_to_reset
);
5431 VEC_free (iv_use_p
, heap
, data
->iv_uses
);
5432 VEC_free (iv_cand_p
, heap
, data
->iv_candidates
);
5435 /* Optimizes the LOOP. Returns true if anything changed. */
5438 tree_ssa_iv_optimize_loop (struct ivopts_data
*data
, struct loop
*loop
)
5440 bool changed
= false;
5441 struct iv_ca
*iv_ca
;
5444 gcc_assert (!data
->niters
);
5445 data
->current_loop
= loop
;
5447 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5449 fprintf (dump_file
, "Processing loop %d\n", loop
->num
);
5451 exit
= single_dom_exit (loop
);
5454 fprintf (dump_file
, " single exit %d -> %d, exit condition ",
5455 exit
->src
->index
, exit
->dest
->index
);
5456 print_generic_expr (dump_file
, last_stmt (exit
->src
), TDF_SLIM
);
5457 fprintf (dump_file
, "\n");
5460 fprintf (dump_file
, "\n");
5463 /* For each ssa name determines whether it behaves as an induction variable
5465 if (!find_induction_variables (data
))
5468 /* Finds interesting uses (item 1). */
5469 find_interesting_uses (data
);
5470 if (n_iv_uses (data
) > MAX_CONSIDERED_USES
)
5473 /* Finds candidates for the induction variables (item 2). */
5474 find_iv_candidates (data
);
5476 /* Calculates the costs (item 3, part 1). */
5477 determine_use_iv_costs (data
);
5478 determine_iv_costs (data
);
5479 determine_set_costs (data
);
5481 /* Find the optimal set of induction variables (item 3, part 2). */
5482 iv_ca
= find_optimal_iv_set (data
);
5487 /* Create the new induction variables (item 4, part 1). */
5488 create_new_ivs (data
, iv_ca
);
5489 iv_ca_free (&iv_ca
);
5491 /* Rewrite the uses (item 4, part 2). */
5492 rewrite_uses (data
);
5494 /* Remove the ivs that are unused after rewriting. */
5495 remove_unused_ivs (data
);
5497 /* We have changed the structure of induction variables; it might happen
5498 that definitions in the scev database refer to some of them that were
5503 free_loop_data (data
);
5508 /* Main entry point. Optimizes induction variables in loops. */
5511 tree_ssa_iv_optimize (void)
5514 struct ivopts_data data
;
5517 tree_ssa_iv_optimize_init (&data
);
5519 /* Optimize the loops starting with the innermost ones. */
5520 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
5522 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5523 flow_loop_dump (loop
, dump_file
, NULL
, 1);
5525 tree_ssa_iv_optimize_loop (&data
, loop
);
5528 tree_ssa_iv_optimize_finalize (&data
);