1 /* Induction variable optimizations.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass tries to find the optimal set of induction variables for the loop.
22 It optimizes just the basic linear induction variables (although adding
23 support for other types should not be too hard). It includes the
24 optimizations commonly known as strength reduction, induction variable
25 coalescing and induction variable elimination. It does it in the
28 1) The interesting uses of induction variables are found. This includes
30 -- uses of induction variables in non-linear expressions
31 -- addresses of arrays
32 -- comparisons of induction variables
34 2) Candidates for the induction variables are found. This includes
36 -- old induction variables
37 -- the variables defined by expressions derived from the "interesting
40 3) The optimal (w.r. to a cost function) set of variables is chosen. The
41 cost function assigns a cost to sets of induction variables and consists
44 -- The use costs. Each of the interesting uses chooses the best induction
45 variable in the set and adds its cost to the sum. The cost reflects
46 the time spent on modifying the induction variables value to be usable
47 for the given purpose (adding base and offset for arrays, etc.).
48 -- The variable costs. Each of the variables has a cost assigned that
49 reflects the costs associated with incrementing the value of the
50 variable. The original variables are somewhat preferred.
51 -- The set cost. Depending on the size of the set, extra cost may be
52 added to reflect register pressure.
54 All the costs are defined in a machine-specific way, using the target
55 hooks and machine descriptions to determine them.
57 4) The trees are transformed to use the new variables, the dead code is
60 All of this is done loop by loop. Doing it globally is theoretically
61 possible, it might give a better performance and it might enable us
62 to decide costs more precisely, but getting all the interactions right
63 would be complicated. */
67 #include "coretypes.h"
71 #include "basic-block.h"
73 #include "tree-pretty-print.h"
74 #include "gimple-pretty-print.h"
75 #include "tree-flow.h"
76 #include "tree-dump.h"
79 #include "tree-pass.h"
81 #include "insn-config.h"
83 #include "pointer-set.h"
85 #include "tree-chrec.h"
86 #include "tree-scalar-evolution.h"
89 #include "langhooks.h"
90 #include "tree-affine.h"
92 #include "tree-inline.h"
93 #include "tree-ssa-propagate.h"
95 /* FIXME: add_cost and zero_cost defined in exprmed.h conflict with local uses.
101 /* FIXME: Expressions are expanded to RTL in this pass to determine the
102 cost of different addressing modes. This should be moved to a TBD
103 interface between the GIMPLE and RTL worlds. */
106 /* The infinite cost. */
107 #define INFTY 10000000
109 #define AVG_LOOP_NITER(LOOP) 5
111 /* Returns the expected number of loop iterations for LOOP.
112 The average trip count is computed from profile data if it
115 static inline HOST_WIDE_INT
116 avg_loop_niter (struct loop
*loop
)
118 HOST_WIDE_INT niter
= max_stmt_executions_int (loop
, false);
120 return AVG_LOOP_NITER (loop
);
125 /* Representation of the induction variable. */
128 tree base
; /* Initial value of the iv. */
129 tree base_object
; /* A memory object to that the induction variable points. */
130 tree step
; /* Step of the iv (constant only). */
131 tree ssa_name
; /* The ssa name with the value. */
132 bool biv_p
; /* Is it a biv? */
133 bool have_use_for
; /* Do we already have a use for it? */
134 unsigned use_id
; /* The identifier in the use if it is the case. */
137 /* Per-ssa version information (induction variable descriptions, etc.). */
140 tree name
; /* The ssa name. */
141 struct iv
*iv
; /* Induction variable description. */
142 bool has_nonlin_use
; /* For a loop-level invariant, whether it is used in
143 an expression that is not an induction variable. */
144 bool preserve_biv
; /* For the original biv, whether to preserve it. */
145 unsigned inv_id
; /* Id of an invariant. */
151 USE_NONLINEAR_EXPR
, /* Use in a nonlinear expression. */
152 USE_ADDRESS
, /* Use in an address. */
153 USE_COMPARE
/* Use is a compare. */
156 /* Cost of a computation. */
159 int cost
; /* The runtime cost. */
160 unsigned complexity
; /* The estimate of the complexity of the code for
161 the computation (in no concrete units --
162 complexity field should be larger for more
163 complex expressions and addressing modes). */
166 static const comp_cost zero_cost
= {0, 0};
167 static const comp_cost infinite_cost
= {INFTY
, INFTY
};
169 /* The candidate - cost pair. */
172 struct iv_cand
*cand
; /* The candidate. */
173 comp_cost cost
; /* The cost. */
174 bitmap depends_on
; /* The list of invariants that have to be
176 tree value
; /* For final value elimination, the expression for
177 the final value of the iv. For iv elimination,
178 the new bound to compare with. */
179 enum tree_code comp
; /* For iv elimination, the comparison. */
180 int inv_expr_id
; /* Loop invariant expression id. */
186 unsigned id
; /* The id of the use. */
187 enum use_type type
; /* Type of the use. */
188 struct iv
*iv
; /* The induction variable it is based on. */
189 gimple stmt
; /* Statement in that it occurs. */
190 tree
*op_p
; /* The place where it occurs. */
191 bitmap related_cands
; /* The set of "related" iv candidates, plus the common
194 unsigned n_map_members
; /* Number of candidates in the cost_map list. */
195 struct cost_pair
*cost_map
;
196 /* The costs wrto the iv candidates. */
198 struct iv_cand
*selected
;
199 /* The selected candidate. */
202 /* The position where the iv is computed. */
205 IP_NORMAL
, /* At the end, just before the exit condition. */
206 IP_END
, /* At the end of the latch block. */
207 IP_BEFORE_USE
, /* Immediately before a specific use. */
208 IP_AFTER_USE
, /* Immediately after a specific use. */
209 IP_ORIGINAL
/* The original biv. */
212 /* The induction variable candidate. */
215 unsigned id
; /* The number of the candidate. */
216 bool important
; /* Whether this is an "important" candidate, i.e. such
217 that it should be considered by all uses. */
218 ENUM_BITFIELD(iv_position
) pos
: 8; /* Where it is computed. */
219 gimple incremented_at
;/* For original biv, the statement where it is
221 tree var_before
; /* The variable used for it before increment. */
222 tree var_after
; /* The variable used for it after increment. */
223 struct iv
*iv
; /* The value of the candidate. NULL for
224 "pseudocandidate" used to indicate the possibility
225 to replace the final value of an iv by direct
226 computation of the value. */
227 unsigned cost
; /* Cost of the candidate. */
228 unsigned cost_step
; /* Cost of the candidate's increment operation. */
229 struct iv_use
*ainc_use
; /* For IP_{BEFORE,AFTER}_USE candidates, the place
230 where it is incremented. */
231 bitmap depends_on
; /* The list of invariants that are used in step of the
235 /* Loop invariant expression hashtable entry. */
236 struct iv_inv_expr_ent
243 /* The data used by the induction variable optimizations. */
245 typedef struct iv_use
*iv_use_p
;
247 DEF_VEC_ALLOC_P(iv_use_p
,heap
);
249 typedef struct iv_cand
*iv_cand_p
;
250 DEF_VEC_P(iv_cand_p
);
251 DEF_VEC_ALLOC_P(iv_cand_p
,heap
);
255 /* The currently optimized loop. */
256 struct loop
*current_loop
;
258 /* Numbers of iterations for all exits of the current loop. */
259 struct pointer_map_t
*niters
;
261 /* Number of registers used in it. */
264 /* The size of version_info array allocated. */
265 unsigned version_info_size
;
267 /* The array of information for the ssa names. */
268 struct version_info
*version_info
;
270 /* The hashtable of loop invariant expressions created
274 /* Loop invariant expression id. */
277 /* The bitmap of indices in version_info whose value was changed. */
280 /* The uses of induction variables. */
281 VEC(iv_use_p
,heap
) *iv_uses
;
283 /* The candidates. */
284 VEC(iv_cand_p
,heap
) *iv_candidates
;
286 /* A bitmap of important candidates. */
287 bitmap important_candidates
;
289 /* The maximum invariant id. */
292 /* Whether to consider just related and important candidates when replacing a
294 bool consider_all_candidates
;
296 /* Are we optimizing for speed? */
299 /* Whether the loop body includes any function calls. */
300 bool body_includes_call
;
302 /* Whether the loop body can only be exited via single exit. */
303 bool loop_single_exit_p
;
306 /* An assignment of iv candidates to uses. */
310 /* The number of uses covered by the assignment. */
313 /* Number of uses that cannot be expressed by the candidates in the set. */
316 /* Candidate assigned to a use, together with the related costs. */
317 struct cost_pair
**cand_for_use
;
319 /* Number of times each candidate is used. */
320 unsigned *n_cand_uses
;
322 /* The candidates used. */
325 /* The number of candidates in the set. */
328 /* Total number of registers needed. */
331 /* Total cost of expressing uses. */
332 comp_cost cand_use_cost
;
334 /* Total cost of candidates. */
337 /* Number of times each invariant is used. */
338 unsigned *n_invariant_uses
;
340 /* The array holding the number of uses of each loop
341 invariant expressions created by ivopt. */
342 unsigned *used_inv_expr
;
344 /* The number of created loop invariants. */
345 unsigned num_used_inv_expr
;
347 /* Total cost of the assignment. */
351 /* Difference of two iv candidate assignments. */
358 /* An old assignment (for rollback purposes). */
359 struct cost_pair
*old_cp
;
361 /* A new assignment. */
362 struct cost_pair
*new_cp
;
364 /* Next change in the list. */
365 struct iv_ca_delta
*next_change
;
368 /* Bound on number of candidates below that all candidates are considered. */
370 #define CONSIDER_ALL_CANDIDATES_BOUND \
371 ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
373 /* If there are more iv occurrences, we just give up (it is quite unlikely that
374 optimizing such a loop would help, and it would take ages). */
376 #define MAX_CONSIDERED_USES \
377 ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
379 /* If there are at most this number of ivs in the set, try removing unnecessary
380 ivs from the set always. */
382 #define ALWAYS_PRUNE_CAND_SET_BOUND \
383 ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
385 /* The list of trees for that the decl_rtl field must be reset is stored
388 static VEC(tree
,heap
) *decl_rtl_to_reset
;
390 static comp_cost
force_expr_to_var_cost (tree
, bool);
392 /* Number of uses recorded in DATA. */
394 static inline unsigned
395 n_iv_uses (struct ivopts_data
*data
)
397 return VEC_length (iv_use_p
, data
->iv_uses
);
400 /* Ith use recorded in DATA. */
402 static inline struct iv_use
*
403 iv_use (struct ivopts_data
*data
, unsigned i
)
405 return VEC_index (iv_use_p
, data
->iv_uses
, i
);
408 /* Number of candidates recorded in DATA. */
410 static inline unsigned
411 n_iv_cands (struct ivopts_data
*data
)
413 return VEC_length (iv_cand_p
, data
->iv_candidates
);
416 /* Ith candidate recorded in DATA. */
418 static inline struct iv_cand
*
419 iv_cand (struct ivopts_data
*data
, unsigned i
)
421 return VEC_index (iv_cand_p
, data
->iv_candidates
, i
);
424 /* The single loop exit if it dominates the latch, NULL otherwise. */
427 single_dom_exit (struct loop
*loop
)
429 edge exit
= single_exit (loop
);
434 if (!just_once_each_iteration_p (loop
, exit
->src
))
440 /* Dumps information about the induction variable IV to FILE. */
442 extern void dump_iv (FILE *, struct iv
*);
444 dump_iv (FILE *file
, struct iv
*iv
)
448 fprintf (file
, "ssa name ");
449 print_generic_expr (file
, iv
->ssa_name
, TDF_SLIM
);
450 fprintf (file
, "\n");
453 fprintf (file
, " type ");
454 print_generic_expr (file
, TREE_TYPE (iv
->base
), TDF_SLIM
);
455 fprintf (file
, "\n");
459 fprintf (file
, " base ");
460 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
461 fprintf (file
, "\n");
463 fprintf (file
, " step ");
464 print_generic_expr (file
, iv
->step
, TDF_SLIM
);
465 fprintf (file
, "\n");
469 fprintf (file
, " invariant ");
470 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
471 fprintf (file
, "\n");
476 fprintf (file
, " base object ");
477 print_generic_expr (file
, iv
->base_object
, TDF_SLIM
);
478 fprintf (file
, "\n");
482 fprintf (file
, " is a biv\n");
485 /* Dumps information about the USE to FILE. */
487 extern void dump_use (FILE *, struct iv_use
*);
489 dump_use (FILE *file
, struct iv_use
*use
)
491 fprintf (file
, "use %d\n", use
->id
);
495 case USE_NONLINEAR_EXPR
:
496 fprintf (file
, " generic\n");
500 fprintf (file
, " address\n");
504 fprintf (file
, " compare\n");
511 fprintf (file
, " in statement ");
512 print_gimple_stmt (file
, use
->stmt
, 0, 0);
513 fprintf (file
, "\n");
515 fprintf (file
, " at position ");
517 print_generic_expr (file
, *use
->op_p
, TDF_SLIM
);
518 fprintf (file
, "\n");
520 dump_iv (file
, use
->iv
);
522 if (use
->related_cands
)
524 fprintf (file
, " related candidates ");
525 dump_bitmap (file
, use
->related_cands
);
529 /* Dumps information about the uses to FILE. */
531 extern void dump_uses (FILE *, struct ivopts_data
*);
533 dump_uses (FILE *file
, struct ivopts_data
*data
)
538 for (i
= 0; i
< n_iv_uses (data
); i
++)
540 use
= iv_use (data
, i
);
542 dump_use (file
, use
);
543 fprintf (file
, "\n");
547 /* Dumps information about induction variable candidate CAND to FILE. */
549 extern void dump_cand (FILE *, struct iv_cand
*);
551 dump_cand (FILE *file
, struct iv_cand
*cand
)
553 struct iv
*iv
= cand
->iv
;
555 fprintf (file
, "candidate %d%s\n",
556 cand
->id
, cand
->important
? " (important)" : "");
558 if (cand
->depends_on
)
560 fprintf (file
, " depends on ");
561 dump_bitmap (file
, cand
->depends_on
);
566 fprintf (file
, " final value replacement\n");
570 if (cand
->var_before
)
572 fprintf (file
, " var_before ");
573 print_generic_expr (file
, cand
->var_before
, TDF_SLIM
);
574 fprintf (file
, "\n");
578 fprintf (file
, " var_after ");
579 print_generic_expr (file
, cand
->var_after
, TDF_SLIM
);
580 fprintf (file
, "\n");
586 fprintf (file
, " incremented before exit test\n");
590 fprintf (file
, " incremented before use %d\n", cand
->ainc_use
->id
);
594 fprintf (file
, " incremented after use %d\n", cand
->ainc_use
->id
);
598 fprintf (file
, " incremented at end\n");
602 fprintf (file
, " original biv\n");
609 /* Returns the info for ssa version VER. */
611 static inline struct version_info
*
612 ver_info (struct ivopts_data
*data
, unsigned ver
)
614 return data
->version_info
+ ver
;
617 /* Returns the info for ssa name NAME. */
619 static inline struct version_info
*
620 name_info (struct ivopts_data
*data
, tree name
)
622 return ver_info (data
, SSA_NAME_VERSION (name
));
625 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
629 stmt_after_ip_normal_pos (struct loop
*loop
, gimple stmt
)
631 basic_block bb
= ip_normal_pos (loop
), sbb
= gimple_bb (stmt
);
635 if (sbb
== loop
->latch
)
641 return stmt
== last_stmt (bb
);
644 /* Returns true if STMT if after the place where the original induction
645 variable CAND is incremented. If TRUE_IF_EQUAL is set, we return true
646 if the positions are identical. */
649 stmt_after_inc_pos (struct iv_cand
*cand
, gimple stmt
, bool true_if_equal
)
651 basic_block cand_bb
= gimple_bb (cand
->incremented_at
);
652 basic_block stmt_bb
= gimple_bb (stmt
);
654 if (!dominated_by_p (CDI_DOMINATORS
, stmt_bb
, cand_bb
))
657 if (stmt_bb
!= cand_bb
)
661 && gimple_uid (stmt
) == gimple_uid (cand
->incremented_at
))
663 return gimple_uid (stmt
) > gimple_uid (cand
->incremented_at
);
666 /* Returns true if STMT if after the place where the induction variable
667 CAND is incremented in LOOP. */
670 stmt_after_increment (struct loop
*loop
, struct iv_cand
*cand
, gimple stmt
)
678 return stmt_after_ip_normal_pos (loop
, stmt
);
682 return stmt_after_inc_pos (cand
, stmt
, false);
685 return stmt_after_inc_pos (cand
, stmt
, true);
692 /* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
695 abnormal_ssa_name_p (tree exp
)
700 if (TREE_CODE (exp
) != SSA_NAME
)
703 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
) != 0;
706 /* Returns false if BASE or INDEX contains a ssa name that occurs in an
707 abnormal phi node. Callback for for_each_index. */
710 idx_contains_abnormal_ssa_name_p (tree base
, tree
*index
,
711 void *data ATTRIBUTE_UNUSED
)
713 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
715 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 2)))
717 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 3)))
721 return !abnormal_ssa_name_p (*index
);
724 /* Returns true if EXPR contains a ssa name that occurs in an
725 abnormal phi node. */
728 contains_abnormal_ssa_name_p (tree expr
)
731 enum tree_code_class codeclass
;
736 code
= TREE_CODE (expr
);
737 codeclass
= TREE_CODE_CLASS (code
);
739 if (code
== SSA_NAME
)
740 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr
) != 0;
742 if (code
== INTEGER_CST
743 || is_gimple_min_invariant (expr
))
746 if (code
== ADDR_EXPR
)
747 return !for_each_index (&TREE_OPERAND (expr
, 0),
748 idx_contains_abnormal_ssa_name_p
,
751 if (code
== COND_EXPR
)
752 return contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0))
753 || contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1))
754 || contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 2));
760 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1)))
765 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0)))
777 /* Returns the structure describing number of iterations determined from
778 EXIT of DATA->current_loop, or NULL if something goes wrong. */
780 static struct tree_niter_desc
*
781 niter_for_exit (struct ivopts_data
*data
, edge exit
)
783 struct tree_niter_desc
*desc
;
788 data
->niters
= pointer_map_create ();
792 slot
= pointer_map_contains (data
->niters
, exit
);
796 /* Try to determine number of iterations. We cannot safely work with ssa
797 names that appear in phi nodes on abnormal edges, so that we do not
798 create overlapping life ranges for them (PR 27283). */
799 desc
= XNEW (struct tree_niter_desc
);
800 if (!number_of_iterations_exit (data
->current_loop
,
802 || contains_abnormal_ssa_name_p (desc
->niter
))
807 slot
= pointer_map_insert (data
->niters
, exit
);
811 desc
= (struct tree_niter_desc
*) *slot
;
816 /* Returns the structure describing number of iterations determined from
817 single dominating exit of DATA->current_loop, or NULL if something
820 static struct tree_niter_desc
*
821 niter_for_single_dom_exit (struct ivopts_data
*data
)
823 edge exit
= single_dom_exit (data
->current_loop
);
828 return niter_for_exit (data
, exit
);
831 /* Hash table equality function for expressions. */
834 htab_inv_expr_eq (const void *ent1
, const void *ent2
)
836 const struct iv_inv_expr_ent
*expr1
=
837 (const struct iv_inv_expr_ent
*)ent1
;
838 const struct iv_inv_expr_ent
*expr2
=
839 (const struct iv_inv_expr_ent
*)ent2
;
841 return expr1
->hash
== expr2
->hash
842 && operand_equal_p (expr1
->expr
, expr2
->expr
, 0);
845 /* Hash function for loop invariant expressions. */
848 htab_inv_expr_hash (const void *ent
)
850 const struct iv_inv_expr_ent
*expr
=
851 (const struct iv_inv_expr_ent
*)ent
;
855 /* Initializes data structures used by the iv optimization pass, stored
859 tree_ssa_iv_optimize_init (struct ivopts_data
*data
)
861 data
->version_info_size
= 2 * num_ssa_names
;
862 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
863 data
->relevant
= BITMAP_ALLOC (NULL
);
864 data
->important_candidates
= BITMAP_ALLOC (NULL
);
865 data
->max_inv_id
= 0;
867 data
->iv_uses
= VEC_alloc (iv_use_p
, heap
, 20);
868 data
->iv_candidates
= VEC_alloc (iv_cand_p
, heap
, 20);
869 data
->inv_expr_tab
= htab_create (10, htab_inv_expr_hash
,
870 htab_inv_expr_eq
, free
);
871 data
->inv_expr_id
= 0;
872 decl_rtl_to_reset
= VEC_alloc (tree
, heap
, 20);
875 /* Returns a memory object to that EXPR points. In case we are able to
876 determine that it does not point to any such object, NULL is returned. */
879 determine_base_object (tree expr
)
881 enum tree_code code
= TREE_CODE (expr
);
884 /* If this is a pointer casted to any type, we need to determine
885 the base object for the pointer; so handle conversions before
886 throwing away non-pointer expressions. */
887 if (CONVERT_EXPR_P (expr
))
888 return determine_base_object (TREE_OPERAND (expr
, 0));
890 if (!POINTER_TYPE_P (TREE_TYPE (expr
)))
899 obj
= TREE_OPERAND (expr
, 0);
900 base
= get_base_address (obj
);
905 if (TREE_CODE (base
) == MEM_REF
)
906 return determine_base_object (TREE_OPERAND (base
, 0));
908 return fold_convert (ptr_type_node
,
909 build_fold_addr_expr (base
));
911 case POINTER_PLUS_EXPR
:
912 return determine_base_object (TREE_OPERAND (expr
, 0));
916 /* Pointer addition is done solely using POINTER_PLUS_EXPR. */
920 return fold_convert (ptr_type_node
, expr
);
924 /* Allocates an induction variable with given initial value BASE and step STEP
928 alloc_iv (tree base
, tree step
)
930 struct iv
*iv
= XCNEW (struct iv
);
931 gcc_assert (step
!= NULL_TREE
);
934 iv
->base_object
= determine_base_object (base
);
937 iv
->have_use_for
= false;
939 iv
->ssa_name
= NULL_TREE
;
944 /* Sets STEP and BASE for induction variable IV. */
947 set_iv (struct ivopts_data
*data
, tree iv
, tree base
, tree step
)
949 struct version_info
*info
= name_info (data
, iv
);
951 gcc_assert (!info
->iv
);
953 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (iv
));
954 info
->iv
= alloc_iv (base
, step
);
955 info
->iv
->ssa_name
= iv
;
958 /* Finds induction variable declaration for VAR. */
961 get_iv (struct ivopts_data
*data
, tree var
)
964 tree type
= TREE_TYPE (var
);
966 if (!POINTER_TYPE_P (type
)
967 && !INTEGRAL_TYPE_P (type
))
970 if (!name_info (data
, var
)->iv
)
972 bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
975 || !flow_bb_inside_loop_p (data
->current_loop
, bb
))
976 set_iv (data
, var
, var
, build_int_cst (type
, 0));
979 return name_info (data
, var
)->iv
;
982 /* Determines the step of a biv defined in PHI. Returns NULL if PHI does
983 not define a simple affine biv with nonzero step. */
986 determine_biv_step (gimple phi
)
988 struct loop
*loop
= gimple_bb (phi
)->loop_father
;
989 tree name
= PHI_RESULT (phi
);
992 if (!is_gimple_reg (name
))
995 if (!simple_iv (loop
, loop
, name
, &iv
, true))
998 return integer_zerop (iv
.step
) ? NULL_TREE
: iv
.step
;
1001 /* Finds basic ivs. */
1004 find_bivs (struct ivopts_data
*data
)
1007 tree step
, type
, base
;
1009 struct loop
*loop
= data
->current_loop
;
1010 gimple_stmt_iterator psi
;
1012 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1014 phi
= gsi_stmt (psi
);
1016 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
1019 step
= determine_biv_step (phi
);
1023 base
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1024 base
= expand_simple_operations (base
);
1025 if (contains_abnormal_ssa_name_p (base
)
1026 || contains_abnormal_ssa_name_p (step
))
1029 type
= TREE_TYPE (PHI_RESULT (phi
));
1030 base
= fold_convert (type
, base
);
1033 if (POINTER_TYPE_P (type
))
1034 step
= convert_to_ptrofftype (step
);
1036 step
= fold_convert (type
, step
);
1039 set_iv (data
, PHI_RESULT (phi
), base
, step
);
1046 /* Marks basic ivs. */
1049 mark_bivs (struct ivopts_data
*data
)
1053 struct iv
*iv
, *incr_iv
;
1054 struct loop
*loop
= data
->current_loop
;
1055 basic_block incr_bb
;
1056 gimple_stmt_iterator psi
;
1058 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1060 phi
= gsi_stmt (psi
);
1062 iv
= get_iv (data
, PHI_RESULT (phi
));
1066 var
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
1067 incr_iv
= get_iv (data
, var
);
1071 /* If the increment is in the subloop, ignore it. */
1072 incr_bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
1073 if (incr_bb
->loop_father
!= data
->current_loop
1074 || (incr_bb
->flags
& BB_IRREDUCIBLE_LOOP
))
1078 incr_iv
->biv_p
= true;
1082 /* Checks whether STMT defines a linear induction variable and stores its
1083 parameters to IV. */
1086 find_givs_in_stmt_scev (struct ivopts_data
*data
, gimple stmt
, affine_iv
*iv
)
1089 struct loop
*loop
= data
->current_loop
;
1091 iv
->base
= NULL_TREE
;
1092 iv
->step
= NULL_TREE
;
1094 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1097 lhs
= gimple_assign_lhs (stmt
);
1098 if (TREE_CODE (lhs
) != SSA_NAME
)
1101 if (!simple_iv (loop
, loop_containing_stmt (stmt
), lhs
, iv
, true))
1103 iv
->base
= expand_simple_operations (iv
->base
);
1105 if (contains_abnormal_ssa_name_p (iv
->base
)
1106 || contains_abnormal_ssa_name_p (iv
->step
))
1109 /* If STMT could throw, then do not consider STMT as defining a GIV.
1110 While this will suppress optimizations, we can not safely delete this
1111 GIV and associated statements, even if it appears it is not used. */
1112 if (stmt_could_throw_p (stmt
))
1118 /* Finds general ivs in statement STMT. */
1121 find_givs_in_stmt (struct ivopts_data
*data
, gimple stmt
)
1125 if (!find_givs_in_stmt_scev (data
, stmt
, &iv
))
1128 set_iv (data
, gimple_assign_lhs (stmt
), iv
.base
, iv
.step
);
1131 /* Finds general ivs in basic block BB. */
1134 find_givs_in_bb (struct ivopts_data
*data
, basic_block bb
)
1136 gimple_stmt_iterator bsi
;
1138 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1139 find_givs_in_stmt (data
, gsi_stmt (bsi
));
1142 /* Finds general ivs. */
1145 find_givs (struct ivopts_data
*data
)
1147 struct loop
*loop
= data
->current_loop
;
1148 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1151 for (i
= 0; i
< loop
->num_nodes
; i
++)
1152 find_givs_in_bb (data
, body
[i
]);
1156 /* For each ssa name defined in LOOP determines whether it is an induction
1157 variable and if so, its initial value and step. */
1160 find_induction_variables (struct ivopts_data
*data
)
1165 if (!find_bivs (data
))
1171 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1173 struct tree_niter_desc
*niter
= niter_for_single_dom_exit (data
);
1177 fprintf (dump_file
, " number of iterations ");
1178 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1179 if (!integer_zerop (niter
->may_be_zero
))
1181 fprintf (dump_file
, "; zero if ");
1182 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1184 fprintf (dump_file
, "\n\n");
1187 fprintf (dump_file
, "Induction variables:\n\n");
1189 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1191 if (ver_info (data
, i
)->iv
)
1192 dump_iv (dump_file
, ver_info (data
, i
)->iv
);
1199 /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV. */
1201 static struct iv_use
*
1202 record_use (struct ivopts_data
*data
, tree
*use_p
, struct iv
*iv
,
1203 gimple stmt
, enum use_type use_type
)
1205 struct iv_use
*use
= XCNEW (struct iv_use
);
1207 use
->id
= n_iv_uses (data
);
1208 use
->type
= use_type
;
1212 use
->related_cands
= BITMAP_ALLOC (NULL
);
1214 /* To avoid showing ssa name in the dumps, if it was not reset by the
1216 iv
->ssa_name
= NULL_TREE
;
1218 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1219 dump_use (dump_file
, use
);
1221 VEC_safe_push (iv_use_p
, heap
, data
->iv_uses
, use
);
1226 /* Checks whether OP is a loop-level invariant and if so, records it.
1227 NONLINEAR_USE is true if the invariant is used in a way we do not
1228 handle specially. */
1231 record_invariant (struct ivopts_data
*data
, tree op
, bool nonlinear_use
)
1234 struct version_info
*info
;
1236 if (TREE_CODE (op
) != SSA_NAME
1237 || !is_gimple_reg (op
))
1240 bb
= gimple_bb (SSA_NAME_DEF_STMT (op
));
1242 && flow_bb_inside_loop_p (data
->current_loop
, bb
))
1245 info
= name_info (data
, op
);
1247 info
->has_nonlin_use
|= nonlinear_use
;
1249 info
->inv_id
= ++data
->max_inv_id
;
1250 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (op
));
1253 /* Checks whether the use OP is interesting and if so, records it. */
1255 static struct iv_use
*
1256 find_interesting_uses_op (struct ivopts_data
*data
, tree op
)
1263 if (TREE_CODE (op
) != SSA_NAME
)
1266 iv
= get_iv (data
, op
);
1270 if (iv
->have_use_for
)
1272 use
= iv_use (data
, iv
->use_id
);
1274 gcc_assert (use
->type
== USE_NONLINEAR_EXPR
);
1278 if (integer_zerop (iv
->step
))
1280 record_invariant (data
, op
, true);
1283 iv
->have_use_for
= true;
1285 civ
= XNEW (struct iv
);
1288 stmt
= SSA_NAME_DEF_STMT (op
);
1289 gcc_assert (gimple_code (stmt
) == GIMPLE_PHI
1290 || is_gimple_assign (stmt
));
1292 use
= record_use (data
, NULL
, civ
, stmt
, USE_NONLINEAR_EXPR
);
1293 iv
->use_id
= use
->id
;
1298 /* Given a condition in statement STMT, checks whether it is a compare
1299 of an induction variable and an invariant. If this is the case,
1300 CONTROL_VAR is set to location of the iv, BOUND to the location of
1301 the invariant, IV_VAR and IV_BOUND are set to the corresponding
1302 induction variable descriptions, and true is returned. If this is not
1303 the case, CONTROL_VAR and BOUND are set to the arguments of the
1304 condition and false is returned. */
1307 extract_cond_operands (struct ivopts_data
*data
, gimple stmt
,
1308 tree
**control_var
, tree
**bound
,
1309 struct iv
**iv_var
, struct iv
**iv_bound
)
1311 /* The objects returned when COND has constant operands. */
1312 static struct iv const_iv
;
1314 tree
*op0
= &zero
, *op1
= &zero
, *tmp_op
;
1315 struct iv
*iv0
= &const_iv
, *iv1
= &const_iv
, *tmp_iv
;
1318 if (gimple_code (stmt
) == GIMPLE_COND
)
1320 op0
= gimple_cond_lhs_ptr (stmt
);
1321 op1
= gimple_cond_rhs_ptr (stmt
);
1325 op0
= gimple_assign_rhs1_ptr (stmt
);
1326 op1
= gimple_assign_rhs2_ptr (stmt
);
1329 zero
= integer_zero_node
;
1330 const_iv
.step
= integer_zero_node
;
1332 if (TREE_CODE (*op0
) == SSA_NAME
)
1333 iv0
= get_iv (data
, *op0
);
1334 if (TREE_CODE (*op1
) == SSA_NAME
)
1335 iv1
= get_iv (data
, *op1
);
1337 /* Exactly one of the compared values must be an iv, and the other one must
1342 if (integer_zerop (iv0
->step
))
1344 /* Control variable may be on the other side. */
1345 tmp_op
= op0
; op0
= op1
; op1
= tmp_op
;
1346 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
1348 ret
= !integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
);
1352 *control_var
= op0
;;
1363 /* Checks whether the condition in STMT is interesting and if so,
1367 find_interesting_uses_cond (struct ivopts_data
*data
, gimple stmt
)
1369 tree
*var_p
, *bound_p
;
1370 struct iv
*var_iv
, *civ
;
1372 if (!extract_cond_operands (data
, stmt
, &var_p
, &bound_p
, &var_iv
, NULL
))
1374 find_interesting_uses_op (data
, *var_p
);
1375 find_interesting_uses_op (data
, *bound_p
);
1379 civ
= XNEW (struct iv
);
1381 record_use (data
, NULL
, civ
, stmt
, USE_COMPARE
);
1384 /* Returns true if expression EXPR is obviously invariant in LOOP,
1385 i.e. if all its operands are defined outside of the LOOP. LOOP
1386 should not be the function body. */
1389 expr_invariant_in_loop_p (struct loop
*loop
, tree expr
)
1394 gcc_assert (loop_depth (loop
) > 0);
1396 if (is_gimple_min_invariant (expr
))
1399 if (TREE_CODE (expr
) == SSA_NAME
)
1401 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
1403 && flow_bb_inside_loop_p (loop
, def_bb
))
1412 len
= TREE_OPERAND_LENGTH (expr
);
1413 for (i
= 0; i
< len
; i
++)
1414 if (!expr_invariant_in_loop_p (loop
, TREE_OPERAND (expr
, i
)))
1420 /* Returns true if statement STMT is obviously invariant in LOOP,
1421 i.e. if all its operands on the RHS are defined outside of the LOOP.
1422 LOOP should not be the function body. */
1425 stmt_invariant_in_loop_p (struct loop
*loop
, gimple stmt
)
1430 gcc_assert (loop_depth (loop
) > 0);
1432 lhs
= gimple_get_lhs (stmt
);
1433 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
1435 tree op
= gimple_op (stmt
, i
);
1436 if (op
!= lhs
&& !expr_invariant_in_loop_p (loop
, op
))
1443 /* Cumulates the steps of indices into DATA and replaces their values with the
1444 initial ones. Returns false when the value of the index cannot be determined.
1445 Callback for for_each_index. */
1447 struct ifs_ivopts_data
1449 struct ivopts_data
*ivopts_data
;
1455 idx_find_step (tree base
, tree
*idx
, void *data
)
1457 struct ifs_ivopts_data
*dta
= (struct ifs_ivopts_data
*) data
;
1459 tree step
, iv_base
, iv_step
, lbound
, off
;
1460 struct loop
*loop
= dta
->ivopts_data
->current_loop
;
1462 /* If base is a component ref, require that the offset of the reference
1464 if (TREE_CODE (base
) == COMPONENT_REF
)
1466 off
= component_ref_field_offset (base
);
1467 return expr_invariant_in_loop_p (loop
, off
);
1470 /* If base is array, first check whether we will be able to move the
1471 reference out of the loop (in order to take its address in strength
1472 reduction). In order for this to work we need both lower bound
1473 and step to be loop invariants. */
1474 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
1476 /* Moreover, for a range, the size needs to be invariant as well. */
1477 if (TREE_CODE (base
) == ARRAY_RANGE_REF
1478 && !expr_invariant_in_loop_p (loop
, TYPE_SIZE (TREE_TYPE (base
))))
1481 step
= array_ref_element_size (base
);
1482 lbound
= array_ref_low_bound (base
);
1484 if (!expr_invariant_in_loop_p (loop
, step
)
1485 || !expr_invariant_in_loop_p (loop
, lbound
))
1489 if (TREE_CODE (*idx
) != SSA_NAME
)
1492 iv
= get_iv (dta
->ivopts_data
, *idx
);
1496 /* XXX We produce for a base of *D42 with iv->base being &x[0]
1497 *&x[0], which is not folded and does not trigger the
1498 ARRAY_REF path below. */
1501 if (integer_zerop (iv
->step
))
1504 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
1506 step
= array_ref_element_size (base
);
1508 /* We only handle addresses whose step is an integer constant. */
1509 if (TREE_CODE (step
) != INTEGER_CST
)
1513 /* The step for pointer arithmetics already is 1 byte. */
1514 step
= size_one_node
;
1518 if (!convert_affine_scev (dta
->ivopts_data
->current_loop
,
1519 sizetype
, &iv_base
, &iv_step
, dta
->stmt
,
1522 /* The index might wrap. */
1526 step
= fold_build2 (MULT_EXPR
, sizetype
, step
, iv_step
);
1527 dta
->step
= fold_build2 (PLUS_EXPR
, sizetype
, dta
->step
, step
);
1532 /* Records use in index IDX. Callback for for_each_index. Ivopts data
1533 object is passed to it in DATA. */
1536 idx_record_use (tree base
, tree
*idx
,
1539 struct ivopts_data
*data
= (struct ivopts_data
*) vdata
;
1540 find_interesting_uses_op (data
, *idx
);
1541 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
1543 find_interesting_uses_op (data
, array_ref_element_size (base
));
1544 find_interesting_uses_op (data
, array_ref_low_bound (base
));
1549 /* If we can prove that TOP = cst * BOT for some constant cst,
1550 store cst to MUL and return true. Otherwise return false.
1551 The returned value is always sign-extended, regardless of the
1552 signedness of TOP and BOT. */
1555 constant_multiple_of (tree top
, tree bot
, double_int
*mul
)
1558 enum tree_code code
;
1559 double_int res
, p0
, p1
;
1560 unsigned precision
= TYPE_PRECISION (TREE_TYPE (top
));
1565 if (operand_equal_p (top
, bot
, 0))
1567 *mul
= double_int_one
;
1571 code
= TREE_CODE (top
);
1575 mby
= TREE_OPERAND (top
, 1);
1576 if (TREE_CODE (mby
) != INTEGER_CST
)
1579 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &res
))
1582 *mul
= double_int_sext (double_int_mul (res
, tree_to_double_int (mby
)),
1588 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &p0
)
1589 || !constant_multiple_of (TREE_OPERAND (top
, 1), bot
, &p1
))
1592 if (code
== MINUS_EXPR
)
1593 p1
= double_int_neg (p1
);
1594 *mul
= double_int_sext (double_int_add (p0
, p1
), precision
);
1598 if (TREE_CODE (bot
) != INTEGER_CST
)
1601 p0
= double_int_sext (tree_to_double_int (top
), precision
);
1602 p1
= double_int_sext (tree_to_double_int (bot
), precision
);
1603 if (double_int_zero_p (p1
))
1605 *mul
= double_int_sext (double_int_sdivmod (p0
, p1
, FLOOR_DIV_EXPR
, &res
),
1607 return double_int_zero_p (res
);
1614 /* Returns true if memory reference REF with step STEP may be unaligned. */
1617 may_be_unaligned_p (tree ref
, tree step
)
1621 HOST_WIDE_INT bitsize
;
1622 HOST_WIDE_INT bitpos
;
1624 enum machine_mode mode
;
1625 int unsignedp
, volatilep
;
1626 unsigned base_align
;
1628 /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
1629 thus they are not misaligned. */
1630 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
1633 /* The test below is basically copy of what expr.c:normal_inner_ref
1634 does to check whether the object must be loaded by parts when
1635 STRICT_ALIGNMENT is true. */
1636 base
= get_inner_reference (ref
, &bitsize
, &bitpos
, &toffset
, &mode
,
1637 &unsignedp
, &volatilep
, true);
1638 base_type
= TREE_TYPE (base
);
1639 base_align
= get_object_alignment (base
);
1640 base_align
= MAX (base_align
, TYPE_ALIGN (base_type
));
1642 if (mode
!= BLKmode
)
1644 unsigned mode_align
= GET_MODE_ALIGNMENT (mode
);
1646 if (base_align
< mode_align
1647 || (bitpos
% mode_align
) != 0
1648 || (bitpos
% BITS_PER_UNIT
) != 0)
1652 && (highest_pow2_factor (toffset
) * BITS_PER_UNIT
) < mode_align
)
1655 if ((highest_pow2_factor (step
) * BITS_PER_UNIT
) < mode_align
)
1662 /* Return true if EXPR may be non-addressable. */
1665 may_be_nonaddressable_p (tree expr
)
1667 switch (TREE_CODE (expr
))
1669 case TARGET_MEM_REF
:
1670 /* TARGET_MEM_REFs are translated directly to valid MEMs on the
1671 target, thus they are always addressable. */
1675 return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr
, 1))
1676 || may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1678 case VIEW_CONVERT_EXPR
:
1679 /* This kind of view-conversions may wrap non-addressable objects
1680 and make them look addressable. After some processing the
1681 non-addressability may be uncovered again, causing ADDR_EXPRs
1682 of inappropriate objects to be built. */
1683 if (is_gimple_reg (TREE_OPERAND (expr
, 0))
1684 || !is_gimple_addressable (TREE_OPERAND (expr
, 0)))
1687 /* ... fall through ... */
1690 case ARRAY_RANGE_REF
:
1691 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1703 /* Finds addresses in *OP_P inside STMT. */
1706 find_interesting_uses_address (struct ivopts_data
*data
, gimple stmt
, tree
*op_p
)
1708 tree base
= *op_p
, step
= size_zero_node
;
1710 struct ifs_ivopts_data ifs_ivopts_data
;
1712 /* Do not play with volatile memory references. A bit too conservative,
1713 perhaps, but safe. */
1714 if (gimple_has_volatile_ops (stmt
))
1717 /* Ignore bitfields for now. Not really something terribly complicated
1719 if (TREE_CODE (base
) == BIT_FIELD_REF
)
1722 base
= unshare_expr (base
);
1724 if (TREE_CODE (base
) == TARGET_MEM_REF
)
1726 tree type
= build_pointer_type (TREE_TYPE (base
));
1730 && TREE_CODE (TMR_BASE (base
)) == SSA_NAME
)
1732 civ
= get_iv (data
, TMR_BASE (base
));
1736 TMR_BASE (base
) = civ
->base
;
1739 if (TMR_INDEX2 (base
)
1740 && TREE_CODE (TMR_INDEX2 (base
)) == SSA_NAME
)
1742 civ
= get_iv (data
, TMR_INDEX2 (base
));
1746 TMR_INDEX2 (base
) = civ
->base
;
1749 if (TMR_INDEX (base
)
1750 && TREE_CODE (TMR_INDEX (base
)) == SSA_NAME
)
1752 civ
= get_iv (data
, TMR_INDEX (base
));
1756 TMR_INDEX (base
) = civ
->base
;
1761 if (TMR_STEP (base
))
1762 astep
= fold_build2 (MULT_EXPR
, type
, TMR_STEP (base
), astep
);
1764 step
= fold_build2 (PLUS_EXPR
, type
, step
, astep
);
1768 if (integer_zerop (step
))
1770 base
= tree_mem_ref_addr (type
, base
);
1774 ifs_ivopts_data
.ivopts_data
= data
;
1775 ifs_ivopts_data
.stmt
= stmt
;
1776 ifs_ivopts_data
.step
= size_zero_node
;
1777 if (!for_each_index (&base
, idx_find_step
, &ifs_ivopts_data
)
1778 || integer_zerop (ifs_ivopts_data
.step
))
1780 step
= ifs_ivopts_data
.step
;
1782 /* Check that the base expression is addressable. This needs
1783 to be done after substituting bases of IVs into it. */
1784 if (may_be_nonaddressable_p (base
))
1787 /* Moreover, on strict alignment platforms, check that it is
1788 sufficiently aligned. */
1789 if (STRICT_ALIGNMENT
&& may_be_unaligned_p (base
, step
))
1792 base
= build_fold_addr_expr (base
);
1794 /* Substituting bases of IVs into the base expression might
1795 have caused folding opportunities. */
1796 if (TREE_CODE (base
) == ADDR_EXPR
)
1798 tree
*ref
= &TREE_OPERAND (base
, 0);
1799 while (handled_component_p (*ref
))
1800 ref
= &TREE_OPERAND (*ref
, 0);
1801 if (TREE_CODE (*ref
) == MEM_REF
)
1803 tree tem
= fold_binary (MEM_REF
, TREE_TYPE (*ref
),
1804 TREE_OPERAND (*ref
, 0),
1805 TREE_OPERAND (*ref
, 1));
1812 civ
= alloc_iv (base
, step
);
1813 record_use (data
, op_p
, civ
, stmt
, USE_ADDRESS
);
1817 for_each_index (op_p
, idx_record_use
, data
);
1820 /* Finds and records invariants used in STMT. */
1823 find_invariants_stmt (struct ivopts_data
*data
, gimple stmt
)
1826 use_operand_p use_p
;
1829 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1831 op
= USE_FROM_PTR (use_p
);
1832 record_invariant (data
, op
, false);
1836 /* Finds interesting uses of induction variables in the statement STMT. */
1839 find_interesting_uses_stmt (struct ivopts_data
*data
, gimple stmt
)
1842 tree op
, *lhs
, *rhs
;
1844 use_operand_p use_p
;
1845 enum tree_code code
;
1847 find_invariants_stmt (data
, stmt
);
1849 if (gimple_code (stmt
) == GIMPLE_COND
)
1851 find_interesting_uses_cond (data
, stmt
);
1855 if (is_gimple_assign (stmt
))
1857 lhs
= gimple_assign_lhs_ptr (stmt
);
1858 rhs
= gimple_assign_rhs1_ptr (stmt
);
1860 if (TREE_CODE (*lhs
) == SSA_NAME
)
1862 /* If the statement defines an induction variable, the uses are not
1863 interesting by themselves. */
1865 iv
= get_iv (data
, *lhs
);
1867 if (iv
&& !integer_zerop (iv
->step
))
1871 code
= gimple_assign_rhs_code (stmt
);
1872 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
1873 && (REFERENCE_CLASS_P (*rhs
)
1874 || is_gimple_val (*rhs
)))
1876 if (REFERENCE_CLASS_P (*rhs
))
1877 find_interesting_uses_address (data
, stmt
, rhs
);
1879 find_interesting_uses_op (data
, *rhs
);
1881 if (REFERENCE_CLASS_P (*lhs
))
1882 find_interesting_uses_address (data
, stmt
, lhs
);
1885 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
1887 find_interesting_uses_cond (data
, stmt
);
1891 /* TODO -- we should also handle address uses of type
1893 memory = call (whatever);
1900 if (gimple_code (stmt
) == GIMPLE_PHI
1901 && gimple_bb (stmt
) == data
->current_loop
->header
)
1903 iv
= get_iv (data
, PHI_RESULT (stmt
));
1905 if (iv
&& !integer_zerop (iv
->step
))
1909 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1911 op
= USE_FROM_PTR (use_p
);
1913 if (TREE_CODE (op
) != SSA_NAME
)
1916 iv
= get_iv (data
, op
);
1920 find_interesting_uses_op (data
, op
);
1924 /* Finds interesting uses of induction variables outside of loops
1925 on loop exit edge EXIT. */
1928 find_interesting_uses_outside (struct ivopts_data
*data
, edge exit
)
1931 gimple_stmt_iterator psi
;
1934 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
1936 phi
= gsi_stmt (psi
);
1937 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1938 if (is_gimple_reg (def
))
1939 find_interesting_uses_op (data
, def
);
1943 /* Finds uses of the induction variables that are interesting. */
1946 find_interesting_uses (struct ivopts_data
*data
)
1949 gimple_stmt_iterator bsi
;
1950 basic_block
*body
= get_loop_body (data
->current_loop
);
1952 struct version_info
*info
;
1955 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1956 fprintf (dump_file
, "Uses:\n\n");
1958 for (i
= 0; i
< data
->current_loop
->num_nodes
; i
++)
1963 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1964 if (e
->dest
!= EXIT_BLOCK_PTR
1965 && !flow_bb_inside_loop_p (data
->current_loop
, e
->dest
))
1966 find_interesting_uses_outside (data
, e
);
1968 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1969 find_interesting_uses_stmt (data
, gsi_stmt (bsi
));
1970 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1971 if (!is_gimple_debug (gsi_stmt (bsi
)))
1972 find_interesting_uses_stmt (data
, gsi_stmt (bsi
));
1975 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1979 fprintf (dump_file
, "\n");
1981 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1983 info
= ver_info (data
, i
);
1986 fprintf (dump_file
, " ");
1987 print_generic_expr (dump_file
, info
->name
, TDF_SLIM
);
1988 fprintf (dump_file
, " is invariant (%d)%s\n",
1989 info
->inv_id
, info
->has_nonlin_use
? "" : ", eliminable");
1993 fprintf (dump_file
, "\n");
1999 /* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
2000 is true, assume we are inside an address. If TOP_COMPREF is true, assume
2001 we are at the top-level of the processed address. */
2004 strip_offset_1 (tree expr
, bool inside_addr
, bool top_compref
,
2005 unsigned HOST_WIDE_INT
*offset
)
2007 tree op0
= NULL_TREE
, op1
= NULL_TREE
, tmp
, step
;
2008 enum tree_code code
;
2009 tree type
, orig_type
= TREE_TYPE (expr
);
2010 unsigned HOST_WIDE_INT off0
, off1
, st
;
2011 tree orig_expr
= expr
;
2015 type
= TREE_TYPE (expr
);
2016 code
= TREE_CODE (expr
);
2022 if (!cst_and_fits_in_hwi (expr
)
2023 || integer_zerop (expr
))
2026 *offset
= int_cst_value (expr
);
2027 return build_int_cst (orig_type
, 0);
2029 case POINTER_PLUS_EXPR
:
2032 op0
= TREE_OPERAND (expr
, 0);
2033 op1
= TREE_OPERAND (expr
, 1);
2035 op0
= strip_offset_1 (op0
, false, false, &off0
);
2036 op1
= strip_offset_1 (op1
, false, false, &off1
);
2038 *offset
= (code
== MINUS_EXPR
? off0
- off1
: off0
+ off1
);
2039 if (op0
== TREE_OPERAND (expr
, 0)
2040 && op1
== TREE_OPERAND (expr
, 1))
2043 if (integer_zerop (op1
))
2045 else if (integer_zerop (op0
))
2047 if (code
== MINUS_EXPR
)
2048 expr
= fold_build1 (NEGATE_EXPR
, type
, op1
);
2053 expr
= fold_build2 (code
, type
, op0
, op1
);
2055 return fold_convert (orig_type
, expr
);
2058 op1
= TREE_OPERAND (expr
, 1);
2059 if (!cst_and_fits_in_hwi (op1
))
2062 op0
= TREE_OPERAND (expr
, 0);
2063 op0
= strip_offset_1 (op0
, false, false, &off0
);
2064 if (op0
== TREE_OPERAND (expr
, 0))
2067 *offset
= off0
* int_cst_value (op1
);
2068 if (integer_zerop (op0
))
2071 expr
= fold_build2 (MULT_EXPR
, type
, op0
, op1
);
2073 return fold_convert (orig_type
, expr
);
2076 case ARRAY_RANGE_REF
:
2080 step
= array_ref_element_size (expr
);
2081 if (!cst_and_fits_in_hwi (step
))
2084 st
= int_cst_value (step
);
2085 op1
= TREE_OPERAND (expr
, 1);
2086 op1
= strip_offset_1 (op1
, false, false, &off1
);
2087 *offset
= off1
* st
;
2090 && integer_zerop (op1
))
2092 /* Strip the component reference completely. */
2093 op0
= TREE_OPERAND (expr
, 0);
2094 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
2104 tmp
= component_ref_field_offset (expr
);
2106 && cst_and_fits_in_hwi (tmp
))
2108 /* Strip the component reference completely. */
2109 op0
= TREE_OPERAND (expr
, 0);
2110 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
2111 *offset
= off0
+ int_cst_value (tmp
);
2117 op0
= TREE_OPERAND (expr
, 0);
2118 op0
= strip_offset_1 (op0
, true, true, &off0
);
2121 if (op0
== TREE_OPERAND (expr
, 0))
2124 expr
= build_fold_addr_expr (op0
);
2125 return fold_convert (orig_type
, expr
);
2128 /* ??? Offset operand? */
2129 inside_addr
= false;
2136 /* Default handling of expressions for that we want to recurse into
2137 the first operand. */
2138 op0
= TREE_OPERAND (expr
, 0);
2139 op0
= strip_offset_1 (op0
, inside_addr
, false, &off0
);
2142 if (op0
== TREE_OPERAND (expr
, 0)
2143 && (!op1
|| op1
== TREE_OPERAND (expr
, 1)))
2146 expr
= copy_node (expr
);
2147 TREE_OPERAND (expr
, 0) = op0
;
2149 TREE_OPERAND (expr
, 1) = op1
;
2151 /* Inside address, we might strip the top level component references,
2152 thus changing type of the expression. Handling of ADDR_EXPR
2154 expr
= fold_convert (orig_type
, expr
);
2159 /* Strips constant offsets from EXPR and stores them to OFFSET. */
2162 strip_offset (tree expr
, unsigned HOST_WIDE_INT
*offset
)
2164 return strip_offset_1 (expr
, false, false, offset
);
2167 /* Returns variant of TYPE that can be used as base for different uses.
2168 We return unsigned type with the same precision, which avoids problems
2172 generic_type_for (tree type
)
2174 if (POINTER_TYPE_P (type
))
2175 return unsigned_type_for (type
);
2177 if (TYPE_UNSIGNED (type
))
2180 return unsigned_type_for (type
);
2183 /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
2184 the bitmap to that we should store it. */
2186 static struct ivopts_data
*fd_ivopts_data
;
2188 find_depends (tree
*expr_p
, int *ws ATTRIBUTE_UNUSED
, void *data
)
2190 bitmap
*depends_on
= (bitmap
*) data
;
2191 struct version_info
*info
;
2193 if (TREE_CODE (*expr_p
) != SSA_NAME
)
2195 info
= name_info (fd_ivopts_data
, *expr_p
);
2197 if (!info
->inv_id
|| info
->has_nonlin_use
)
2201 *depends_on
= BITMAP_ALLOC (NULL
);
2202 bitmap_set_bit (*depends_on
, info
->inv_id
);
2207 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2208 position to POS. If USE is not NULL, the candidate is set as related to
2209 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
2210 replacement of the final value of the iv by a direct computation. */
2212 static struct iv_cand
*
2213 add_candidate_1 (struct ivopts_data
*data
,
2214 tree base
, tree step
, bool important
, enum iv_position pos
,
2215 struct iv_use
*use
, gimple incremented_at
)
2218 struct iv_cand
*cand
= NULL
;
2219 tree type
, orig_type
;
2221 /* For non-original variables, make sure their values are computed in a type
2222 that does not invoke undefined behavior on overflows (since in general,
2223 we cannot prove that these induction variables are non-wrapping). */
2224 if (pos
!= IP_ORIGINAL
)
2226 orig_type
= TREE_TYPE (base
);
2227 type
= generic_type_for (orig_type
);
2228 if (type
!= orig_type
)
2230 base
= fold_convert (type
, base
);
2231 step
= fold_convert (type
, step
);
2235 for (i
= 0; i
< n_iv_cands (data
); i
++)
2237 cand
= iv_cand (data
, i
);
2239 if (cand
->pos
!= pos
)
2242 if (cand
->incremented_at
!= incremented_at
2243 || ((pos
== IP_AFTER_USE
|| pos
== IP_BEFORE_USE
)
2244 && cand
->ainc_use
!= use
))
2258 if (operand_equal_p (base
, cand
->iv
->base
, 0)
2259 && operand_equal_p (step
, cand
->iv
->step
, 0)
2260 && (TYPE_PRECISION (TREE_TYPE (base
))
2261 == TYPE_PRECISION (TREE_TYPE (cand
->iv
->base
))))
2265 if (i
== n_iv_cands (data
))
2267 cand
= XCNEW (struct iv_cand
);
2273 cand
->iv
= alloc_iv (base
, step
);
2276 if (pos
!= IP_ORIGINAL
&& cand
->iv
)
2278 cand
->var_before
= create_tmp_var_raw (TREE_TYPE (base
), "ivtmp");
2279 cand
->var_after
= cand
->var_before
;
2281 cand
->important
= important
;
2282 cand
->incremented_at
= incremented_at
;
2283 VEC_safe_push (iv_cand_p
, heap
, data
->iv_candidates
, cand
);
2286 && TREE_CODE (step
) != INTEGER_CST
)
2288 fd_ivopts_data
= data
;
2289 walk_tree (&step
, find_depends
, &cand
->depends_on
, NULL
);
2292 if (pos
== IP_AFTER_USE
|| pos
== IP_BEFORE_USE
)
2293 cand
->ainc_use
= use
;
2295 cand
->ainc_use
= NULL
;
2297 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2298 dump_cand (dump_file
, cand
);
2301 if (important
&& !cand
->important
)
2303 cand
->important
= true;
2304 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2305 fprintf (dump_file
, "Candidate %d is important\n", cand
->id
);
2310 bitmap_set_bit (use
->related_cands
, i
);
2311 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2312 fprintf (dump_file
, "Candidate %d is related to use %d\n",
2319 /* Returns true if incrementing the induction variable at the end of the LOOP
2322 The purpose is to avoid splitting latch edge with a biv increment, thus
2323 creating a jump, possibly confusing other optimization passes and leaving
2324 less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS
2325 is not available (so we do not have a better alternative), or if the latch
2326 edge is already nonempty. */
2329 allow_ip_end_pos_p (struct loop
*loop
)
2331 if (!ip_normal_pos (loop
))
2334 if (!empty_block_p (ip_end_pos (loop
)))
2340 /* If possible, adds autoincrement candidates BASE + STEP * i based on use USE.
2341 Important field is set to IMPORTANT. */
2344 add_autoinc_candidates (struct ivopts_data
*data
, tree base
, tree step
,
2345 bool important
, struct iv_use
*use
)
2347 basic_block use_bb
= gimple_bb (use
->stmt
);
2348 enum machine_mode mem_mode
;
2349 unsigned HOST_WIDE_INT cstepi
;
2351 /* If we insert the increment in any position other than the standard
2352 ones, we must ensure that it is incremented once per iteration.
2353 It must not be in an inner nested loop, or one side of an if
2355 if (use_bb
->loop_father
!= data
->current_loop
2356 || !dominated_by_p (CDI_DOMINATORS
, data
->current_loop
->latch
, use_bb
)
2357 || stmt_could_throw_p (use
->stmt
)
2358 || !cst_and_fits_in_hwi (step
))
2361 cstepi
= int_cst_value (step
);
2363 mem_mode
= TYPE_MODE (TREE_TYPE (*use
->op_p
));
2364 if ((HAVE_PRE_INCREMENT
&& GET_MODE_SIZE (mem_mode
) == cstepi
)
2365 || (HAVE_PRE_DECREMENT
&& GET_MODE_SIZE (mem_mode
) == -cstepi
))
2367 enum tree_code code
= MINUS_EXPR
;
2369 tree new_step
= step
;
2371 if (POINTER_TYPE_P (TREE_TYPE (base
)))
2373 new_step
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (step
), step
);
2374 code
= POINTER_PLUS_EXPR
;
2377 new_step
= fold_convert (TREE_TYPE (base
), new_step
);
2378 new_base
= fold_build2 (code
, TREE_TYPE (base
), base
, new_step
);
2379 add_candidate_1 (data
, new_base
, step
, important
, IP_BEFORE_USE
, use
,
2382 if ((HAVE_POST_INCREMENT
&& GET_MODE_SIZE (mem_mode
) == cstepi
)
2383 || (HAVE_POST_DECREMENT
&& GET_MODE_SIZE (mem_mode
) == -cstepi
))
2385 add_candidate_1 (data
, base
, step
, important
, IP_AFTER_USE
, use
,
2390 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2391 position to POS. If USE is not NULL, the candidate is set as related to
2392 it. The candidate computation is scheduled on all available positions. */
2395 add_candidate (struct ivopts_data
*data
,
2396 tree base
, tree step
, bool important
, struct iv_use
*use
)
2398 if (ip_normal_pos (data
->current_loop
))
2399 add_candidate_1 (data
, base
, step
, important
, IP_NORMAL
, use
, NULL
);
2400 if (ip_end_pos (data
->current_loop
)
2401 && allow_ip_end_pos_p (data
->current_loop
))
2402 add_candidate_1 (data
, base
, step
, important
, IP_END
, use
, NULL
);
2404 if (use
!= NULL
&& use
->type
== USE_ADDRESS
)
2405 add_autoinc_candidates (data
, base
, step
, important
, use
);
2408 /* Adds standard iv candidates. */
2411 add_standard_iv_candidates (struct ivopts_data
*data
)
2413 add_candidate (data
, integer_zero_node
, integer_one_node
, true, NULL
);
2415 /* The same for a double-integer type if it is still fast enough. */
2417 (long_integer_type_node
) > TYPE_PRECISION (integer_type_node
)
2418 && TYPE_PRECISION (long_integer_type_node
) <= BITS_PER_WORD
)
2419 add_candidate (data
, build_int_cst (long_integer_type_node
, 0),
2420 build_int_cst (long_integer_type_node
, 1), true, NULL
);
2422 /* The same for a double-integer type if it is still fast enough. */
2424 (long_long_integer_type_node
) > TYPE_PRECISION (long_integer_type_node
)
2425 && TYPE_PRECISION (long_long_integer_type_node
) <= BITS_PER_WORD
)
2426 add_candidate (data
, build_int_cst (long_long_integer_type_node
, 0),
2427 build_int_cst (long_long_integer_type_node
, 1), true, NULL
);
2431 /* Adds candidates bases on the old induction variable IV. */
2434 add_old_iv_candidates (struct ivopts_data
*data
, struct iv
*iv
)
2438 struct iv_cand
*cand
;
2440 add_candidate (data
, iv
->base
, iv
->step
, true, NULL
);
2442 /* The same, but with initial value zero. */
2443 if (POINTER_TYPE_P (TREE_TYPE (iv
->base
)))
2444 add_candidate (data
, size_int (0), iv
->step
, true, NULL
);
2446 add_candidate (data
, build_int_cst (TREE_TYPE (iv
->base
), 0),
2447 iv
->step
, true, NULL
);
2449 phi
= SSA_NAME_DEF_STMT (iv
->ssa_name
);
2450 if (gimple_code (phi
) == GIMPLE_PHI
)
2452 /* Additionally record the possibility of leaving the original iv
2454 def
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (data
->current_loop
));
2455 cand
= add_candidate_1 (data
,
2456 iv
->base
, iv
->step
, true, IP_ORIGINAL
, NULL
,
2457 SSA_NAME_DEF_STMT (def
));
2458 cand
->var_before
= iv
->ssa_name
;
2459 cand
->var_after
= def
;
2463 /* Adds candidates based on the old induction variables. */
2466 add_old_ivs_candidates (struct ivopts_data
*data
)
2472 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
2474 iv
= ver_info (data
, i
)->iv
;
2475 if (iv
&& iv
->biv_p
&& !integer_zerop (iv
->step
))
2476 add_old_iv_candidates (data
, iv
);
2480 /* Adds candidates based on the value of the induction variable IV and USE. */
2483 add_iv_value_candidates (struct ivopts_data
*data
,
2484 struct iv
*iv
, struct iv_use
*use
)
2486 unsigned HOST_WIDE_INT offset
;
2490 add_candidate (data
, iv
->base
, iv
->step
, false, use
);
2492 /* The same, but with initial value zero. Make such variable important,
2493 since it is generic enough so that possibly many uses may be based
2495 basetype
= TREE_TYPE (iv
->base
);
2496 if (POINTER_TYPE_P (basetype
))
2497 basetype
= sizetype
;
2498 add_candidate (data
, build_int_cst (basetype
, 0),
2499 iv
->step
, true, use
);
2501 /* Third, try removing the constant offset. Make sure to even
2502 add a candidate for &a[0] vs. (T *)&a. */
2503 base
= strip_offset (iv
->base
, &offset
);
2505 || base
!= iv
->base
)
2506 add_candidate (data
, base
, iv
->step
, false, use
);
2509 /* Adds candidates based on the uses. */
2512 add_derived_ivs_candidates (struct ivopts_data
*data
)
2516 for (i
= 0; i
< n_iv_uses (data
); i
++)
2518 struct iv_use
*use
= iv_use (data
, i
);
2525 case USE_NONLINEAR_EXPR
:
2528 /* Just add the ivs based on the value of the iv used here. */
2529 add_iv_value_candidates (data
, use
->iv
, use
);
2538 /* Record important candidates and add them to related_cands bitmaps
2542 record_important_candidates (struct ivopts_data
*data
)
2547 for (i
= 0; i
< n_iv_cands (data
); i
++)
2549 struct iv_cand
*cand
= iv_cand (data
, i
);
2551 if (cand
->important
)
2552 bitmap_set_bit (data
->important_candidates
, i
);
2555 data
->consider_all_candidates
= (n_iv_cands (data
)
2556 <= CONSIDER_ALL_CANDIDATES_BOUND
);
2558 if (data
->consider_all_candidates
)
2560 /* We will not need "related_cands" bitmaps in this case,
2561 so release them to decrease peak memory consumption. */
2562 for (i
= 0; i
< n_iv_uses (data
); i
++)
2564 use
= iv_use (data
, i
);
2565 BITMAP_FREE (use
->related_cands
);
2570 /* Add important candidates to the related_cands bitmaps. */
2571 for (i
= 0; i
< n_iv_uses (data
); i
++)
2572 bitmap_ior_into (iv_use (data
, i
)->related_cands
,
2573 data
->important_candidates
);
2577 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
2578 If consider_all_candidates is true, we use a two-dimensional array, otherwise
2579 we allocate a simple list to every use. */
2582 alloc_use_cost_map (struct ivopts_data
*data
)
2584 unsigned i
, size
, s
, j
;
2586 for (i
= 0; i
< n_iv_uses (data
); i
++)
2588 struct iv_use
*use
= iv_use (data
, i
);
2591 if (data
->consider_all_candidates
)
2592 size
= n_iv_cands (data
);
2596 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, j
, bi
)
2601 /* Round up to the power of two, so that moduling by it is fast. */
2602 for (size
= 1; size
< s
; size
<<= 1)
2606 use
->n_map_members
= size
;
2607 use
->cost_map
= XCNEWVEC (struct cost_pair
, size
);
2611 /* Returns description of computation cost of expression whose runtime
2612 cost is RUNTIME and complexity corresponds to COMPLEXITY. */
2615 new_cost (unsigned runtime
, unsigned complexity
)
2619 cost
.cost
= runtime
;
2620 cost
.complexity
= complexity
;
2625 /* Adds costs COST1 and COST2. */
2628 add_costs (comp_cost cost1
, comp_cost cost2
)
2630 cost1
.cost
+= cost2
.cost
;
2631 cost1
.complexity
+= cost2
.complexity
;
2635 /* Subtracts costs COST1 and COST2. */
2638 sub_costs (comp_cost cost1
, comp_cost cost2
)
2640 cost1
.cost
-= cost2
.cost
;
2641 cost1
.complexity
-= cost2
.complexity
;
2646 /* Returns a negative number if COST1 < COST2, a positive number if
2647 COST1 > COST2, and 0 if COST1 = COST2. */
2650 compare_costs (comp_cost cost1
, comp_cost cost2
)
2652 if (cost1
.cost
== cost2
.cost
)
2653 return cost1
.complexity
- cost2
.complexity
;
2655 return cost1
.cost
- cost2
.cost
;
2658 /* Returns true if COST is infinite. */
2661 infinite_cost_p (comp_cost cost
)
2663 return cost
.cost
== INFTY
;
2666 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
2667 on invariants DEPENDS_ON and that the value used in expressing it
2668 is VALUE, and in case of iv elimination the comparison operator is COMP. */
2671 set_use_iv_cost (struct ivopts_data
*data
,
2672 struct iv_use
*use
, struct iv_cand
*cand
,
2673 comp_cost cost
, bitmap depends_on
, tree value
,
2674 enum tree_code comp
, int inv_expr_id
)
2678 if (infinite_cost_p (cost
))
2680 BITMAP_FREE (depends_on
);
2684 if (data
->consider_all_candidates
)
2686 use
->cost_map
[cand
->id
].cand
= cand
;
2687 use
->cost_map
[cand
->id
].cost
= cost
;
2688 use
->cost_map
[cand
->id
].depends_on
= depends_on
;
2689 use
->cost_map
[cand
->id
].value
= value
;
2690 use
->cost_map
[cand
->id
].comp
= comp
;
2691 use
->cost_map
[cand
->id
].inv_expr_id
= inv_expr_id
;
2695 /* n_map_members is a power of two, so this computes modulo. */
2696 s
= cand
->id
& (use
->n_map_members
- 1);
2697 for (i
= s
; i
< use
->n_map_members
; i
++)
2698 if (!use
->cost_map
[i
].cand
)
2700 for (i
= 0; i
< s
; i
++)
2701 if (!use
->cost_map
[i
].cand
)
2707 use
->cost_map
[i
].cand
= cand
;
2708 use
->cost_map
[i
].cost
= cost
;
2709 use
->cost_map
[i
].depends_on
= depends_on
;
2710 use
->cost_map
[i
].value
= value
;
2711 use
->cost_map
[i
].comp
= comp
;
2712 use
->cost_map
[i
].inv_expr_id
= inv_expr_id
;
2715 /* Gets cost of (USE, CANDIDATE) pair. */
2717 static struct cost_pair
*
2718 get_use_iv_cost (struct ivopts_data
*data
, struct iv_use
*use
,
2719 struct iv_cand
*cand
)
2722 struct cost_pair
*ret
;
2727 if (data
->consider_all_candidates
)
2729 ret
= use
->cost_map
+ cand
->id
;
2736 /* n_map_members is a power of two, so this computes modulo. */
2737 s
= cand
->id
& (use
->n_map_members
- 1);
2738 for (i
= s
; i
< use
->n_map_members
; i
++)
2739 if (use
->cost_map
[i
].cand
== cand
)
2740 return use
->cost_map
+ i
;
2742 for (i
= 0; i
< s
; i
++)
2743 if (use
->cost_map
[i
].cand
== cand
)
2744 return use
->cost_map
+ i
;
2749 /* Returns estimate on cost of computing SEQ. */
2752 seq_cost (rtx seq
, bool speed
)
2757 for (; seq
; seq
= NEXT_INSN (seq
))
2759 set
= single_set (seq
);
2761 cost
+= set_src_cost (SET_SRC (set
), speed
);
2769 /* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
2771 produce_memory_decl_rtl (tree obj
, int *regno
)
2773 addr_space_t as
= TYPE_ADDR_SPACE (TREE_TYPE (obj
));
2774 enum machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
2778 if (TREE_STATIC (obj
) || DECL_EXTERNAL (obj
))
2780 const char *name
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj
));
2781 x
= gen_rtx_SYMBOL_REF (address_mode
, name
);
2782 SET_SYMBOL_REF_DECL (x
, obj
);
2783 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
2784 set_mem_addr_space (x
, as
);
2785 targetm
.encode_section_info (obj
, x
, true);
2789 x
= gen_raw_REG (address_mode
, (*regno
)++);
2790 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
2791 set_mem_addr_space (x
, as
);
2797 /* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
2798 walk_tree. DATA contains the actual fake register number. */
2801 prepare_decl_rtl (tree
*expr_p
, int *ws
, void *data
)
2803 tree obj
= NULL_TREE
;
2805 int *regno
= (int *) data
;
2807 switch (TREE_CODE (*expr_p
))
2810 for (expr_p
= &TREE_OPERAND (*expr_p
, 0);
2811 handled_component_p (*expr_p
);
2812 expr_p
= &TREE_OPERAND (*expr_p
, 0))
2815 if (DECL_P (obj
) && !DECL_RTL_SET_P (obj
))
2816 x
= produce_memory_decl_rtl (obj
, regno
);
2821 obj
= SSA_NAME_VAR (*expr_p
);
2822 if (!DECL_RTL_SET_P (obj
))
2823 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2832 if (DECL_RTL_SET_P (obj
))
2835 if (DECL_MODE (obj
) == BLKmode
)
2836 x
= produce_memory_decl_rtl (obj
, regno
);
2838 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2848 VEC_safe_push (tree
, heap
, decl_rtl_to_reset
, obj
);
2849 SET_DECL_RTL (obj
, x
);
2855 /* Determines cost of the computation of EXPR. */
2858 computation_cost (tree expr
, bool speed
)
2861 tree type
= TREE_TYPE (expr
);
2863 /* Avoid using hard regs in ways which may be unsupported. */
2864 int regno
= LAST_VIRTUAL_REGISTER
+ 1;
2865 struct cgraph_node
*node
= cgraph_get_node (current_function_decl
);
2866 enum node_frequency real_frequency
= node
->frequency
;
2868 node
->frequency
= NODE_FREQUENCY_NORMAL
;
2869 crtl
->maybe_hot_insn_p
= speed
;
2870 walk_tree (&expr
, prepare_decl_rtl
, ®no
, NULL
);
2872 rslt
= expand_expr (expr
, NULL_RTX
, TYPE_MODE (type
), EXPAND_NORMAL
);
2875 default_rtl_profile ();
2876 node
->frequency
= real_frequency
;
2878 cost
= seq_cost (seq
, speed
);
2880 cost
+= address_cost (XEXP (rslt
, 0), TYPE_MODE (type
),
2881 TYPE_ADDR_SPACE (type
), speed
);
2882 else if (!REG_P (rslt
))
2883 cost
+= set_src_cost (rslt
, speed
);
2888 /* Returns variable containing the value of candidate CAND at statement AT. */
2891 var_at_stmt (struct loop
*loop
, struct iv_cand
*cand
, gimple stmt
)
2893 if (stmt_after_increment (loop
, cand
, stmt
))
2894 return cand
->var_after
;
2896 return cand
->var_before
;
2899 /* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
2900 same precision that is at least as wide as the precision of TYPE, stores
2901 BA to A and BB to B, and returns the type of BA. Otherwise, returns the
2905 determine_common_wider_type (tree
*a
, tree
*b
)
2907 tree wider_type
= NULL
;
2909 tree atype
= TREE_TYPE (*a
);
2911 if (CONVERT_EXPR_P (*a
))
2913 suba
= TREE_OPERAND (*a
, 0);
2914 wider_type
= TREE_TYPE (suba
);
2915 if (TYPE_PRECISION (wider_type
) < TYPE_PRECISION (atype
))
2921 if (CONVERT_EXPR_P (*b
))
2923 subb
= TREE_OPERAND (*b
, 0);
2924 if (TYPE_PRECISION (wider_type
) != TYPE_PRECISION (TREE_TYPE (subb
)))
2935 /* Determines the expression by that USE is expressed from induction variable
2936 CAND at statement AT in LOOP. The expression is stored in a decomposed
2937 form into AFF. Returns false if USE cannot be expressed using CAND. */
2940 get_computation_aff (struct loop
*loop
,
2941 struct iv_use
*use
, struct iv_cand
*cand
, gimple at
,
2942 struct affine_tree_combination
*aff
)
2944 tree ubase
= use
->iv
->base
;
2945 tree ustep
= use
->iv
->step
;
2946 tree cbase
= cand
->iv
->base
;
2947 tree cstep
= cand
->iv
->step
, cstep_common
;
2948 tree utype
= TREE_TYPE (ubase
), ctype
= TREE_TYPE (cbase
);
2949 tree common_type
, var
;
2951 aff_tree cbase_aff
, var_aff
;
2954 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
2956 /* We do not have a precision to express the values of use. */
2960 var
= var_at_stmt (loop
, cand
, at
);
2961 uutype
= unsigned_type_for (utype
);
2963 /* If the conversion is not noop, perform it. */
2964 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
2966 cstep
= fold_convert (uutype
, cstep
);
2967 cbase
= fold_convert (uutype
, cbase
);
2968 var
= fold_convert (uutype
, var
);
2971 if (!constant_multiple_of (ustep
, cstep
, &rat
))
2974 /* In case both UBASE and CBASE are shortened to UUTYPE from some common
2975 type, we achieve better folding by computing their difference in this
2976 wider type, and cast the result to UUTYPE. We do not need to worry about
2977 overflows, as all the arithmetics will in the end be performed in UUTYPE
2979 common_type
= determine_common_wider_type (&ubase
, &cbase
);
2981 /* use = ubase - ratio * cbase + ratio * var. */
2982 tree_to_aff_combination (ubase
, common_type
, aff
);
2983 tree_to_aff_combination (cbase
, common_type
, &cbase_aff
);
2984 tree_to_aff_combination (var
, uutype
, &var_aff
);
2986 /* We need to shift the value if we are after the increment. */
2987 if (stmt_after_increment (loop
, cand
, at
))
2991 if (common_type
!= uutype
)
2992 cstep_common
= fold_convert (common_type
, cstep
);
2994 cstep_common
= cstep
;
2996 tree_to_aff_combination (cstep_common
, common_type
, &cstep_aff
);
2997 aff_combination_add (&cbase_aff
, &cstep_aff
);
3000 aff_combination_scale (&cbase_aff
, double_int_neg (rat
));
3001 aff_combination_add (aff
, &cbase_aff
);
3002 if (common_type
!= uutype
)
3003 aff_combination_convert (aff
, uutype
);
3005 aff_combination_scale (&var_aff
, rat
);
3006 aff_combination_add (aff
, &var_aff
);
3011 /* Determines the expression by that USE is expressed from induction variable
3012 CAND at statement AT in LOOP. The computation is unshared. */
3015 get_computation_at (struct loop
*loop
,
3016 struct iv_use
*use
, struct iv_cand
*cand
, gimple at
)
3019 tree type
= TREE_TYPE (use
->iv
->base
);
3021 if (!get_computation_aff (loop
, use
, cand
, at
, &aff
))
3023 unshare_aff_combination (&aff
);
3024 return fold_convert (type
, aff_combination_to_tree (&aff
));
3027 /* Determines the expression by that USE is expressed from induction variable
3028 CAND in LOOP. The computation is unshared. */
3031 get_computation (struct loop
*loop
, struct iv_use
*use
, struct iv_cand
*cand
)
3033 return get_computation_at (loop
, use
, cand
, use
->stmt
);
3036 /* Adjust the cost COST for being in loop setup rather than loop body.
3037 If we're optimizing for space, the loop setup overhead is constant;
3038 if we're optimizing for speed, amortize it over the per-iteration cost. */
3040 adjust_setup_cost (struct ivopts_data
*data
, unsigned cost
)
3044 else if (optimize_loop_for_speed_p (data
->current_loop
))
3045 return cost
/ avg_loop_niter (data
->current_loop
);
3050 /* Returns cost of addition in MODE. */
3053 add_cost (enum machine_mode mode
, bool speed
)
3055 static unsigned costs
[NUM_MACHINE_MODES
];
3063 force_operand (gen_rtx_fmt_ee (PLUS
, mode
,
3064 gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 1),
3065 gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 2)),
3070 cost
= seq_cost (seq
, speed
);
3076 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3077 fprintf (dump_file
, "Addition in %s costs %d\n",
3078 GET_MODE_NAME (mode
), cost
);
3082 /* Entry in a hashtable of already known costs for multiplication. */
3085 HOST_WIDE_INT cst
; /* The constant to multiply by. */
3086 enum machine_mode mode
; /* In mode. */
3087 unsigned cost
; /* The cost. */
3090 /* Counts hash value for the ENTRY. */
3093 mbc_entry_hash (const void *entry
)
3095 const struct mbc_entry
*e
= (const struct mbc_entry
*) entry
;
3097 return 57 * (hashval_t
) e
->mode
+ (hashval_t
) (e
->cst
% 877);
3100 /* Compares the hash table entries ENTRY1 and ENTRY2. */
3103 mbc_entry_eq (const void *entry1
, const void *entry2
)
3105 const struct mbc_entry
*e1
= (const struct mbc_entry
*) entry1
;
3106 const struct mbc_entry
*e2
= (const struct mbc_entry
*) entry2
;
3108 return (e1
->mode
== e2
->mode
3109 && e1
->cst
== e2
->cst
);
3112 /* Returns cost of multiplication by constant CST in MODE. */
3115 multiply_by_cost (HOST_WIDE_INT cst
, enum machine_mode mode
, bool speed
)
3117 static htab_t costs
;
3118 struct mbc_entry
**cached
, act
;
3123 costs
= htab_create (100, mbc_entry_hash
, mbc_entry_eq
, free
);
3127 cached
= (struct mbc_entry
**) htab_find_slot (costs
, &act
, INSERT
);
3129 return (*cached
)->cost
;
3131 *cached
= XNEW (struct mbc_entry
);
3132 (*cached
)->mode
= mode
;
3133 (*cached
)->cst
= cst
;
3136 expand_mult (mode
, gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 1),
3137 gen_int_mode (cst
, mode
), NULL_RTX
, 0);
3141 cost
= seq_cost (seq
, speed
);
3143 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3144 fprintf (dump_file
, "Multiplication by %d in %s costs %d\n",
3145 (int) cst
, GET_MODE_NAME (mode
), cost
);
3147 (*cached
)->cost
= cost
;
3152 /* Returns true if multiplying by RATIO is allowed in an address. Test the
3153 validity for a memory reference accessing memory of mode MODE in
3154 address space AS. */
3156 DEF_VEC_P (sbitmap
);
3157 DEF_VEC_ALLOC_P (sbitmap
, heap
);
3160 multiplier_allowed_in_address_p (HOST_WIDE_INT ratio
, enum machine_mode mode
,
3163 #define MAX_RATIO 128
3164 unsigned int data_index
= (int) as
* MAX_MACHINE_MODE
+ (int) mode
;
3165 static VEC (sbitmap
, heap
) *valid_mult_list
;
3168 if (data_index
>= VEC_length (sbitmap
, valid_mult_list
))
3169 VEC_safe_grow_cleared (sbitmap
, heap
, valid_mult_list
, data_index
+ 1);
3171 valid_mult
= VEC_index (sbitmap
, valid_mult_list
, data_index
);
3174 enum machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
3175 rtx reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
3179 valid_mult
= sbitmap_alloc (2 * MAX_RATIO
+ 1);
3180 sbitmap_zero (valid_mult
);
3181 addr
= gen_rtx_fmt_ee (MULT
, address_mode
, reg1
, NULL_RTX
);
3182 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
3184 XEXP (addr
, 1) = gen_int_mode (i
, address_mode
);
3185 if (memory_address_addr_space_p (mode
, addr
, as
))
3186 SET_BIT (valid_mult
, i
+ MAX_RATIO
);
3189 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3191 fprintf (dump_file
, " allowed multipliers:");
3192 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
3193 if (TEST_BIT (valid_mult
, i
+ MAX_RATIO
))
3194 fprintf (dump_file
, " %d", (int) i
);
3195 fprintf (dump_file
, "\n");
3196 fprintf (dump_file
, "\n");
3199 VEC_replace (sbitmap
, valid_mult_list
, data_index
, valid_mult
);
3202 if (ratio
> MAX_RATIO
|| ratio
< -MAX_RATIO
)
3205 return TEST_BIT (valid_mult
, ratio
+ MAX_RATIO
);
3208 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
3209 If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
3210 variable is omitted. Compute the cost for a memory reference that accesses
3211 a memory location of mode MEM_MODE in address space AS.
3213 MAY_AUTOINC is set to true if the autoincrement (increasing index by
3214 size of MEM_MODE / RATIO) is available. To make this determination, we
3215 look at the size of the increment to be made, which is given in CSTEP.
3216 CSTEP may be zero if the step is unknown.
3217 STMT_AFTER_INC is true iff the statement we're looking at is after the
3218 increment of the original biv.
3220 TODO -- there must be some better way. This all is quite crude. */
3224 HOST_WIDE_INT min_offset
, max_offset
;
3225 unsigned costs
[2][2][2][2];
3226 } *address_cost_data
;
3228 DEF_VEC_P (address_cost_data
);
3229 DEF_VEC_ALLOC_P (address_cost_data
, heap
);
3232 get_address_cost (bool symbol_present
, bool var_present
,
3233 unsigned HOST_WIDE_INT offset
, HOST_WIDE_INT ratio
,
3234 HOST_WIDE_INT cstep
, enum machine_mode mem_mode
,
3235 addr_space_t as
, bool speed
,
3236 bool stmt_after_inc
, bool *may_autoinc
)
3238 enum machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
3239 static VEC(address_cost_data
, heap
) *address_cost_data_list
;
3240 unsigned int data_index
= (int) as
* MAX_MACHINE_MODE
+ (int) mem_mode
;
3241 address_cost_data data
;
3242 static bool has_preinc
[MAX_MACHINE_MODE
], has_postinc
[MAX_MACHINE_MODE
];
3243 static bool has_predec
[MAX_MACHINE_MODE
], has_postdec
[MAX_MACHINE_MODE
];
3244 unsigned cost
, acost
, complexity
;
3245 bool offset_p
, ratio_p
, autoinc
;
3246 HOST_WIDE_INT s_offset
, autoinc_offset
, msize
;
3247 unsigned HOST_WIDE_INT mask
;
3250 if (data_index
>= VEC_length (address_cost_data
, address_cost_data_list
))
3251 VEC_safe_grow_cleared (address_cost_data
, heap
, address_cost_data_list
,
3254 data
= VEC_index (address_cost_data
, address_cost_data_list
, data_index
);
3258 HOST_WIDE_INT rat
, off
= 0;
3259 int old_cse_not_expected
, width
;
3260 unsigned sym_p
, var_p
, off_p
, rat_p
, add_c
;
3261 rtx seq
, addr
, base
;
3264 data
= (address_cost_data
) xcalloc (1, sizeof (*data
));
3266 reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
3268 width
= GET_MODE_BITSIZE (address_mode
) - 1;
3269 if (width
> (HOST_BITS_PER_WIDE_INT
- 1))
3270 width
= HOST_BITS_PER_WIDE_INT
- 1;
3271 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, reg1
, NULL_RTX
);
3273 for (i
= width
; i
>= 0; i
--)
3275 off
= -((HOST_WIDE_INT
) 1 << i
);
3276 XEXP (addr
, 1) = gen_int_mode (off
, address_mode
);
3277 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
3280 data
->min_offset
= (i
== -1? 0 : off
);
3282 for (i
= width
; i
>= 0; i
--)
3284 off
= ((HOST_WIDE_INT
) 1 << i
) - 1;
3285 XEXP (addr
, 1) = gen_int_mode (off
, address_mode
);
3286 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
3291 data
->max_offset
= off
;
3293 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3295 fprintf (dump_file
, "get_address_cost:\n");
3296 fprintf (dump_file
, " min offset %s " HOST_WIDE_INT_PRINT_DEC
"\n",
3297 GET_MODE_NAME (mem_mode
),
3299 fprintf (dump_file
, " max offset %s " HOST_WIDE_INT_PRINT_DEC
"\n",
3300 GET_MODE_NAME (mem_mode
),
3305 for (i
= 2; i
<= MAX_RATIO
; i
++)
3306 if (multiplier_allowed_in_address_p (i
, mem_mode
, as
))
3312 /* Compute the cost of various addressing modes. */
3314 reg0
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
3315 reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 2);
3317 if (HAVE_PRE_DECREMENT
)
3319 addr
= gen_rtx_PRE_DEC (address_mode
, reg0
);
3320 has_predec
[mem_mode
]
3321 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3323 if (HAVE_POST_DECREMENT
)
3325 addr
= gen_rtx_POST_DEC (address_mode
, reg0
);
3326 has_postdec
[mem_mode
]
3327 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3329 if (HAVE_PRE_INCREMENT
)
3331 addr
= gen_rtx_PRE_INC (address_mode
, reg0
);
3332 has_preinc
[mem_mode
]
3333 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3335 if (HAVE_POST_INCREMENT
)
3337 addr
= gen_rtx_POST_INC (address_mode
, reg0
);
3338 has_postinc
[mem_mode
]
3339 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3341 for (i
= 0; i
< 16; i
++)
3344 var_p
= (i
>> 1) & 1;
3345 off_p
= (i
>> 2) & 1;
3346 rat_p
= (i
>> 3) & 1;
3350 addr
= gen_rtx_fmt_ee (MULT
, address_mode
, addr
,
3351 gen_int_mode (rat
, address_mode
));
3354 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, addr
, reg1
);
3358 base
= gen_rtx_SYMBOL_REF (address_mode
, ggc_strdup (""));
3359 /* ??? We can run into trouble with some backends by presenting
3360 it with symbols which haven't been properly passed through
3361 targetm.encode_section_info. By setting the local bit, we
3362 enhance the probability of things working. */
3363 SYMBOL_REF_FLAGS (base
) = SYMBOL_FLAG_LOCAL
;
3366 base
= gen_rtx_fmt_e (CONST
, address_mode
,
3368 (PLUS
, address_mode
, base
,
3369 gen_int_mode (off
, address_mode
)));
3372 base
= gen_int_mode (off
, address_mode
);
3377 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, addr
, base
);
3380 /* To avoid splitting addressing modes, pretend that no cse will
3382 old_cse_not_expected
= cse_not_expected
;
3383 cse_not_expected
= true;
3384 addr
= memory_address_addr_space (mem_mode
, addr
, as
);
3385 cse_not_expected
= old_cse_not_expected
;
3389 acost
= seq_cost (seq
, speed
);
3390 acost
+= address_cost (addr
, mem_mode
, as
, speed
);
3394 data
->costs
[sym_p
][var_p
][off_p
][rat_p
] = acost
;
3397 /* On some targets, it is quite expensive to load symbol to a register,
3398 which makes addresses that contain symbols look much more expensive.
3399 However, the symbol will have to be loaded in any case before the
3400 loop (and quite likely we have it in register already), so it does not
3401 make much sense to penalize them too heavily. So make some final
3402 tweaks for the SYMBOL_PRESENT modes:
3404 If VAR_PRESENT is false, and the mode obtained by changing symbol to
3405 var is cheaper, use this mode with small penalty.
3406 If VAR_PRESENT is true, try whether the mode with
3407 SYMBOL_PRESENT = false is cheaper even with cost of addition, and
3408 if this is the case, use it. */
3409 add_c
= add_cost (address_mode
, speed
);
3410 for (i
= 0; i
< 8; i
++)
3413 off_p
= (i
>> 1) & 1;
3414 rat_p
= (i
>> 2) & 1;
3416 acost
= data
->costs
[0][1][off_p
][rat_p
] + 1;
3420 if (acost
< data
->costs
[1][var_p
][off_p
][rat_p
])
3421 data
->costs
[1][var_p
][off_p
][rat_p
] = acost
;
3424 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3426 fprintf (dump_file
, "Address costs:\n");
3428 for (i
= 0; i
< 16; i
++)
3431 var_p
= (i
>> 1) & 1;
3432 off_p
= (i
>> 2) & 1;
3433 rat_p
= (i
>> 3) & 1;
3435 fprintf (dump_file
, " ");
3437 fprintf (dump_file
, "sym + ");
3439 fprintf (dump_file
, "var + ");
3441 fprintf (dump_file
, "cst + ");
3443 fprintf (dump_file
, "rat * ");
3445 acost
= data
->costs
[sym_p
][var_p
][off_p
][rat_p
];
3446 fprintf (dump_file
, "index costs %d\n", acost
);
3448 if (has_predec
[mem_mode
] || has_postdec
[mem_mode
]
3449 || has_preinc
[mem_mode
] || has_postinc
[mem_mode
])
3450 fprintf (dump_file
, " May include autoinc/dec\n");
3451 fprintf (dump_file
, "\n");
3454 VEC_replace (address_cost_data
, address_cost_data_list
,
3458 bits
= GET_MODE_BITSIZE (address_mode
);
3459 mask
= ~(~(unsigned HOST_WIDE_INT
) 0 << (bits
- 1) << 1);
3461 if ((offset
>> (bits
- 1) & 1))
3466 msize
= GET_MODE_SIZE (mem_mode
);
3467 autoinc_offset
= offset
;
3469 autoinc_offset
+= ratio
* cstep
;
3470 if (symbol_present
|| var_present
|| ratio
!= 1)
3472 else if ((has_postinc
[mem_mode
] && autoinc_offset
== 0
3474 || (has_postdec
[mem_mode
] && autoinc_offset
== 0
3476 || (has_preinc
[mem_mode
] && autoinc_offset
== msize
3478 || (has_predec
[mem_mode
] && autoinc_offset
== -msize
3479 && msize
== -cstep
))
3483 offset_p
= (s_offset
!= 0
3484 && data
->min_offset
<= s_offset
3485 && s_offset
<= data
->max_offset
);
3486 ratio_p
= (ratio
!= 1
3487 && multiplier_allowed_in_address_p (ratio
, mem_mode
, as
));
3489 if (ratio
!= 1 && !ratio_p
)
3490 cost
+= multiply_by_cost (ratio
, address_mode
, speed
);
3492 if (s_offset
&& !offset_p
&& !symbol_present
)
3493 cost
+= add_cost (address_mode
, speed
);
3496 *may_autoinc
= autoinc
;
3497 acost
= data
->costs
[symbol_present
][var_present
][offset_p
][ratio_p
];
3498 complexity
= (symbol_present
!= 0) + (var_present
!= 0) + offset_p
+ ratio_p
;
3499 return new_cost (cost
+ acost
, complexity
);
3502 /* Calculate the SPEED or size cost of shiftadd EXPR in MODE. MULT is the
3503 the EXPR operand holding the shift. COST0 and COST1 are the costs for
3504 calculating the operands of EXPR. Returns true if successful, and returns
3505 the cost in COST. */
3508 get_shiftadd_cost (tree expr
, enum machine_mode mode
, comp_cost cost0
,
3509 comp_cost cost1
, tree mult
, bool speed
, comp_cost
*cost
)
3512 tree op1
= TREE_OPERAND (expr
, 1);
3513 tree cst
= TREE_OPERAND (mult
, 1);
3514 tree multop
= TREE_OPERAND (mult
, 0);
3515 int m
= exact_log2 (int_cst_value (cst
));
3516 int maxm
= MIN (BITS_PER_WORD
, GET_MODE_BITSIZE (mode
));
3519 if (!(m
>= 0 && m
< maxm
))
3522 sa_cost
= (TREE_CODE (expr
) != MINUS_EXPR
3523 ? shiftadd_cost
[speed
][mode
][m
]
3525 ? shiftsub1_cost
[speed
][mode
][m
]
3526 : shiftsub0_cost
[speed
][mode
][m
]));
3527 res
= new_cost (sa_cost
, 0);
3528 res
= add_costs (res
, mult
== op1
? cost0
: cost1
);
3530 STRIP_NOPS (multop
);
3531 if (!is_gimple_val (multop
))
3532 res
= add_costs (res
, force_expr_to_var_cost (multop
, speed
));
3538 /* Estimates cost of forcing expression EXPR into a variable. */
3541 force_expr_to_var_cost (tree expr
, bool speed
)
3543 static bool costs_initialized
= false;
3544 static unsigned integer_cost
[2];
3545 static unsigned symbol_cost
[2];
3546 static unsigned address_cost
[2];
3548 comp_cost cost0
, cost1
, cost
;
3549 enum machine_mode mode
;
3551 if (!costs_initialized
)
3553 tree type
= build_pointer_type (integer_type_node
);
3558 var
= create_tmp_var_raw (integer_type_node
, "test_var");
3559 TREE_STATIC (var
) = 1;
3560 x
= produce_memory_decl_rtl (var
, NULL
);
3561 SET_DECL_RTL (var
, x
);
3563 addr
= build1 (ADDR_EXPR
, type
, var
);
3566 for (i
= 0; i
< 2; i
++)
3568 integer_cost
[i
] = computation_cost (build_int_cst (integer_type_node
,
3571 symbol_cost
[i
] = computation_cost (addr
, i
) + 1;
3574 = computation_cost (fold_build_pointer_plus_hwi (addr
, 2000), i
) + 1;
3575 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3577 fprintf (dump_file
, "force_expr_to_var_cost %s costs:\n", i
? "speed" : "size");
3578 fprintf (dump_file
, " integer %d\n", (int) integer_cost
[i
]);
3579 fprintf (dump_file
, " symbol %d\n", (int) symbol_cost
[i
]);
3580 fprintf (dump_file
, " address %d\n", (int) address_cost
[i
]);
3581 fprintf (dump_file
, " other %d\n", (int) target_spill_cost
[i
]);
3582 fprintf (dump_file
, "\n");
3586 costs_initialized
= true;
3591 if (SSA_VAR_P (expr
))
3594 if (is_gimple_min_invariant (expr
))
3596 if (TREE_CODE (expr
) == INTEGER_CST
)
3597 return new_cost (integer_cost
[speed
], 0);
3599 if (TREE_CODE (expr
) == ADDR_EXPR
)
3601 tree obj
= TREE_OPERAND (expr
, 0);
3603 if (TREE_CODE (obj
) == VAR_DECL
3604 || TREE_CODE (obj
) == PARM_DECL
3605 || TREE_CODE (obj
) == RESULT_DECL
)
3606 return new_cost (symbol_cost
[speed
], 0);
3609 return new_cost (address_cost
[speed
], 0);
3612 switch (TREE_CODE (expr
))
3614 case POINTER_PLUS_EXPR
:
3618 op0
= TREE_OPERAND (expr
, 0);
3619 op1
= TREE_OPERAND (expr
, 1);
3623 if (is_gimple_val (op0
))
3626 cost0
= force_expr_to_var_cost (op0
, speed
);
3628 if (is_gimple_val (op1
))
3631 cost1
= force_expr_to_var_cost (op1
, speed
);
3636 op0
= TREE_OPERAND (expr
, 0);
3640 if (is_gimple_val (op0
))
3643 cost0
= force_expr_to_var_cost (op0
, speed
);
3649 /* Just an arbitrary value, FIXME. */
3650 return new_cost (target_spill_cost
[speed
], 0);
3653 mode
= TYPE_MODE (TREE_TYPE (expr
));
3654 switch (TREE_CODE (expr
))
3656 case POINTER_PLUS_EXPR
:
3660 cost
= new_cost (add_cost (mode
, speed
), 0);
3661 if (TREE_CODE (expr
) != NEGATE_EXPR
)
3663 tree mult
= NULL_TREE
;
3665 if (TREE_CODE (op1
) == MULT_EXPR
)
3667 else if (TREE_CODE (op0
) == MULT_EXPR
)
3670 if (mult
!= NULL_TREE
3671 && cst_and_fits_in_hwi (TREE_OPERAND (mult
, 1))
3672 && get_shiftadd_cost (expr
, mode
, cost0
, cost1
, mult
, speed
,
3679 if (cst_and_fits_in_hwi (op0
))
3680 cost
= new_cost (multiply_by_cost (int_cst_value (op0
), mode
, speed
), 0);
3681 else if (cst_and_fits_in_hwi (op1
))
3682 cost
= new_cost (multiply_by_cost (int_cst_value (op1
), mode
, speed
), 0);
3684 return new_cost (target_spill_cost
[speed
], 0);
3691 cost
= add_costs (cost
, cost0
);
3692 cost
= add_costs (cost
, cost1
);
3694 /* Bound the cost by target_spill_cost. The parts of complicated
3695 computations often are either loop invariant or at least can
3696 be shared between several iv uses, so letting this grow without
3697 limits would not give reasonable results. */
3698 if (cost
.cost
> (int) target_spill_cost
[speed
])
3699 cost
.cost
= target_spill_cost
[speed
];
3704 /* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
3705 invariants the computation depends on. */
3708 force_var_cost (struct ivopts_data
*data
,
3709 tree expr
, bitmap
*depends_on
)
3713 fd_ivopts_data
= data
;
3714 walk_tree (&expr
, find_depends
, depends_on
, NULL
);
3717 return force_expr_to_var_cost (expr
, data
->speed
);
3720 /* Estimates cost of expressing address ADDR as var + symbol + offset. The
3721 value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
3722 to false if the corresponding part is missing. DEPENDS_ON is a set of the
3723 invariants the computation depends on. */
3726 split_address_cost (struct ivopts_data
*data
,
3727 tree addr
, bool *symbol_present
, bool *var_present
,
3728 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3731 HOST_WIDE_INT bitsize
;
3732 HOST_WIDE_INT bitpos
;
3734 enum machine_mode mode
;
3735 int unsignedp
, volatilep
;
3737 core
= get_inner_reference (addr
, &bitsize
, &bitpos
, &toffset
, &mode
,
3738 &unsignedp
, &volatilep
, false);
3741 || bitpos
% BITS_PER_UNIT
!= 0
3742 || TREE_CODE (core
) != VAR_DECL
)
3744 *symbol_present
= false;
3745 *var_present
= true;
3746 fd_ivopts_data
= data
;
3747 walk_tree (&addr
, find_depends
, depends_on
, NULL
);
3748 return new_cost (target_spill_cost
[data
->speed
], 0);
3751 *offset
+= bitpos
/ BITS_PER_UNIT
;
3752 if (TREE_STATIC (core
)
3753 || DECL_EXTERNAL (core
))
3755 *symbol_present
= true;
3756 *var_present
= false;
3760 *symbol_present
= false;
3761 *var_present
= true;
3765 /* Estimates cost of expressing difference of addresses E1 - E2 as
3766 var + symbol + offset. The value of offset is added to OFFSET,
3767 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3768 part is missing. DEPENDS_ON is a set of the invariants the computation
3772 ptr_difference_cost (struct ivopts_data
*data
,
3773 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
3774 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3776 HOST_WIDE_INT diff
= 0;
3777 aff_tree aff_e1
, aff_e2
;
3780 gcc_assert (TREE_CODE (e1
) == ADDR_EXPR
);
3782 if (ptr_difference_const (e1
, e2
, &diff
))
3785 *symbol_present
= false;
3786 *var_present
= false;
3790 if (integer_zerop (e2
))
3791 return split_address_cost (data
, TREE_OPERAND (e1
, 0),
3792 symbol_present
, var_present
, offset
, depends_on
);
3794 *symbol_present
= false;
3795 *var_present
= true;
3797 type
= signed_type_for (TREE_TYPE (e1
));
3798 tree_to_aff_combination (e1
, type
, &aff_e1
);
3799 tree_to_aff_combination (e2
, type
, &aff_e2
);
3800 aff_combination_scale (&aff_e2
, double_int_minus_one
);
3801 aff_combination_add (&aff_e1
, &aff_e2
);
3803 return force_var_cost (data
, aff_combination_to_tree (&aff_e1
), depends_on
);
3806 /* Estimates cost of expressing difference E1 - E2 as
3807 var + symbol + offset. The value of offset is added to OFFSET,
3808 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3809 part is missing. DEPENDS_ON is a set of the invariants the computation
3813 difference_cost (struct ivopts_data
*data
,
3814 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
3815 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3817 enum machine_mode mode
= TYPE_MODE (TREE_TYPE (e1
));
3818 unsigned HOST_WIDE_INT off1
, off2
;
3819 aff_tree aff_e1
, aff_e2
;
3822 e1
= strip_offset (e1
, &off1
);
3823 e2
= strip_offset (e2
, &off2
);
3824 *offset
+= off1
- off2
;
3829 if (TREE_CODE (e1
) == ADDR_EXPR
)
3830 return ptr_difference_cost (data
, e1
, e2
, symbol_present
, var_present
,
3831 offset
, depends_on
);
3832 *symbol_present
= false;
3834 if (operand_equal_p (e1
, e2
, 0))
3836 *var_present
= false;
3840 *var_present
= true;
3842 if (integer_zerop (e2
))
3843 return force_var_cost (data
, e1
, depends_on
);
3845 if (integer_zerop (e1
))
3847 comp_cost cost
= force_var_cost (data
, e2
, depends_on
);
3848 cost
.cost
+= multiply_by_cost (-1, mode
, data
->speed
);
3852 type
= signed_type_for (TREE_TYPE (e1
));
3853 tree_to_aff_combination (e1
, type
, &aff_e1
);
3854 tree_to_aff_combination (e2
, type
, &aff_e2
);
3855 aff_combination_scale (&aff_e2
, double_int_minus_one
);
3856 aff_combination_add (&aff_e1
, &aff_e2
);
3858 return force_var_cost (data
, aff_combination_to_tree (&aff_e1
), depends_on
);
3861 /* Returns true if AFF1 and AFF2 are identical. */
3864 compare_aff_trees (aff_tree
*aff1
, aff_tree
*aff2
)
3868 if (aff1
->n
!= aff2
->n
)
3871 for (i
= 0; i
< aff1
->n
; i
++)
3873 if (double_int_cmp (aff1
->elts
[i
].coef
, aff2
->elts
[i
].coef
, 0) != 0)
3876 if (!operand_equal_p (aff1
->elts
[i
].val
, aff2
->elts
[i
].val
, 0))
3882 /* Stores EXPR in DATA->inv_expr_tab, and assigns it an inv_expr_id. */
3885 get_expr_id (struct ivopts_data
*data
, tree expr
)
3887 struct iv_inv_expr_ent ent
;
3888 struct iv_inv_expr_ent
**slot
;
3891 ent
.hash
= iterative_hash_expr (expr
, 0);
3892 slot
= (struct iv_inv_expr_ent
**) htab_find_slot (data
->inv_expr_tab
,
3897 *slot
= XNEW (struct iv_inv_expr_ent
);
3898 (*slot
)->expr
= expr
;
3899 (*slot
)->hash
= ent
.hash
;
3900 (*slot
)->id
= data
->inv_expr_id
++;
3904 /* Returns the pseudo expr id if expression UBASE - RATIO * CBASE
3905 requires a new compiler generated temporary. Returns -1 otherwise.
3906 ADDRESS_P is a flag indicating if the expression is for address
3910 get_loop_invariant_expr_id (struct ivopts_data
*data
, tree ubase
,
3911 tree cbase
, HOST_WIDE_INT ratio
,
3914 aff_tree ubase_aff
, cbase_aff
;
3922 if ((TREE_CODE (ubase
) == INTEGER_CST
)
3923 && (TREE_CODE (cbase
) == INTEGER_CST
))
3926 /* Strips the constant part. */
3927 if (TREE_CODE (ubase
) == PLUS_EXPR
3928 || TREE_CODE (ubase
) == MINUS_EXPR
3929 || TREE_CODE (ubase
) == POINTER_PLUS_EXPR
)
3931 if (TREE_CODE (TREE_OPERAND (ubase
, 1)) == INTEGER_CST
)
3932 ubase
= TREE_OPERAND (ubase
, 0);
3935 /* Strips the constant part. */
3936 if (TREE_CODE (cbase
) == PLUS_EXPR
3937 || TREE_CODE (cbase
) == MINUS_EXPR
3938 || TREE_CODE (cbase
) == POINTER_PLUS_EXPR
)
3940 if (TREE_CODE (TREE_OPERAND (cbase
, 1)) == INTEGER_CST
)
3941 cbase
= TREE_OPERAND (cbase
, 0);
3946 if (((TREE_CODE (ubase
) == SSA_NAME
)
3947 || (TREE_CODE (ubase
) == ADDR_EXPR
3948 && is_gimple_min_invariant (ubase
)))
3949 && (TREE_CODE (cbase
) == INTEGER_CST
))
3952 if (((TREE_CODE (cbase
) == SSA_NAME
)
3953 || (TREE_CODE (cbase
) == ADDR_EXPR
3954 && is_gimple_min_invariant (cbase
)))
3955 && (TREE_CODE (ubase
) == INTEGER_CST
))
3961 if(operand_equal_p (ubase
, cbase
, 0))
3964 if (TREE_CODE (ubase
) == ADDR_EXPR
3965 && TREE_CODE (cbase
) == ADDR_EXPR
)
3969 usym
= TREE_OPERAND (ubase
, 0);
3970 csym
= TREE_OPERAND (cbase
, 0);
3971 if (TREE_CODE (usym
) == ARRAY_REF
)
3973 tree ind
= TREE_OPERAND (usym
, 1);
3974 if (TREE_CODE (ind
) == INTEGER_CST
3975 && host_integerp (ind
, 0)
3976 && TREE_INT_CST_LOW (ind
) == 0)
3977 usym
= TREE_OPERAND (usym
, 0);
3979 if (TREE_CODE (csym
) == ARRAY_REF
)
3981 tree ind
= TREE_OPERAND (csym
, 1);
3982 if (TREE_CODE (ind
) == INTEGER_CST
3983 && host_integerp (ind
, 0)
3984 && TREE_INT_CST_LOW (ind
) == 0)
3985 csym
= TREE_OPERAND (csym
, 0);
3987 if (operand_equal_p (usym
, csym
, 0))
3990 /* Now do more complex comparison */
3991 tree_to_aff_combination (ubase
, TREE_TYPE (ubase
), &ubase_aff
);
3992 tree_to_aff_combination (cbase
, TREE_TYPE (cbase
), &cbase_aff
);
3993 if (compare_aff_trees (&ubase_aff
, &cbase_aff
))
3997 tree_to_aff_combination (ub
, TREE_TYPE (ub
), &ubase_aff
);
3998 tree_to_aff_combination (cb
, TREE_TYPE (cb
), &cbase_aff
);
4000 aff_combination_scale (&cbase_aff
, shwi_to_double_int (-1 * ratio
));
4001 aff_combination_add (&ubase_aff
, &cbase_aff
);
4002 expr
= aff_combination_to_tree (&ubase_aff
);
4003 return get_expr_id (data
, expr
);
4008 /* Determines the cost of the computation by that USE is expressed
4009 from induction variable CAND. If ADDRESS_P is true, we just need
4010 to create an address from it, otherwise we want to get it into
4011 register. A set of invariants we depend on is stored in
4012 DEPENDS_ON. AT is the statement at that the value is computed.
4013 If CAN_AUTOINC is nonnull, use it to record whether autoinc
4014 addressing is likely. */
4017 get_computation_cost_at (struct ivopts_data
*data
,
4018 struct iv_use
*use
, struct iv_cand
*cand
,
4019 bool address_p
, bitmap
*depends_on
, gimple at
,
4023 tree ubase
= use
->iv
->base
, ustep
= use
->iv
->step
;
4025 tree utype
= TREE_TYPE (ubase
), ctype
;
4026 unsigned HOST_WIDE_INT cstepi
, offset
= 0;
4027 HOST_WIDE_INT ratio
, aratio
;
4028 bool var_present
, symbol_present
, stmt_is_after_inc
;
4031 bool speed
= optimize_bb_for_speed_p (gimple_bb (at
));
4035 /* Only consider real candidates. */
4037 return infinite_cost
;
4039 cbase
= cand
->iv
->base
;
4040 cstep
= cand
->iv
->step
;
4041 ctype
= TREE_TYPE (cbase
);
4043 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
4045 /* We do not have a precision to express the values of use. */
4046 return infinite_cost
;
4050 || (use
->iv
->base_object
4051 && cand
->iv
->base_object
4052 && POINTER_TYPE_P (TREE_TYPE (use
->iv
->base_object
))
4053 && POINTER_TYPE_P (TREE_TYPE (cand
->iv
->base_object
))))
4055 /* Do not try to express address of an object with computation based
4056 on address of a different object. This may cause problems in rtl
4057 level alias analysis (that does not expect this to be happening,
4058 as this is illegal in C), and would be unlikely to be useful
4060 if (use
->iv
->base_object
4061 && cand
->iv
->base_object
4062 && !operand_equal_p (use
->iv
->base_object
, cand
->iv
->base_object
, 0))
4063 return infinite_cost
;
4066 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
4068 /* TODO -- add direct handling of this case. */
4072 /* CSTEPI is removed from the offset in case statement is after the
4073 increment. If the step is not constant, we use zero instead.
4074 This is a bit imprecise (there is the extra addition), but
4075 redundancy elimination is likely to transform the code so that
4076 it uses value of the variable before increment anyway,
4077 so it is not that much unrealistic. */
4078 if (cst_and_fits_in_hwi (cstep
))
4079 cstepi
= int_cst_value (cstep
);
4083 if (!constant_multiple_of (ustep
, cstep
, &rat
))
4084 return infinite_cost
;
4086 if (double_int_fits_in_shwi_p (rat
))
4087 ratio
= double_int_to_shwi (rat
);
4089 return infinite_cost
;
4092 ctype
= TREE_TYPE (cbase
);
4094 stmt_is_after_inc
= stmt_after_increment (data
->current_loop
, cand
, at
);
4096 /* use = ubase + ratio * (var - cbase). If either cbase is a constant
4097 or ratio == 1, it is better to handle this like
4099 ubase - ratio * cbase + ratio * var
4101 (also holds in the case ratio == -1, TODO. */
4103 if (cst_and_fits_in_hwi (cbase
))
4105 offset
= - ratio
* int_cst_value (cbase
);
4106 cost
= difference_cost (data
,
4107 ubase
, build_int_cst (utype
, 0),
4108 &symbol_present
, &var_present
, &offset
,
4110 cost
.cost
/= avg_loop_niter (data
->current_loop
);
4112 else if (ratio
== 1)
4114 tree real_cbase
= cbase
;
4116 /* Check to see if any adjustment is needed. */
4117 if (cstepi
== 0 && stmt_is_after_inc
)
4119 aff_tree real_cbase_aff
;
4122 tree_to_aff_combination (cbase
, TREE_TYPE (real_cbase
),
4124 tree_to_aff_combination (cstep
, TREE_TYPE (cstep
), &cstep_aff
);
4126 aff_combination_add (&real_cbase_aff
, &cstep_aff
);
4127 real_cbase
= aff_combination_to_tree (&real_cbase_aff
);
4130 cost
= difference_cost (data
,
4132 &symbol_present
, &var_present
, &offset
,
4134 cost
.cost
/= avg_loop_niter (data
->current_loop
);
4137 && !POINTER_TYPE_P (ctype
)
4138 && multiplier_allowed_in_address_p
4139 (ratio
, TYPE_MODE (TREE_TYPE (utype
)),
4140 TYPE_ADDR_SPACE (TREE_TYPE (utype
))))
4143 = fold_build2 (MULT_EXPR
, ctype
, cbase
, build_int_cst (ctype
, ratio
));
4144 cost
= difference_cost (data
,
4146 &symbol_present
, &var_present
, &offset
,
4148 cost
.cost
/= avg_loop_niter (data
->current_loop
);
4152 cost
= force_var_cost (data
, cbase
, depends_on
);
4153 cost
= add_costs (cost
,
4154 difference_cost (data
,
4155 ubase
, build_int_cst (utype
, 0),
4156 &symbol_present
, &var_present
,
4157 &offset
, depends_on
));
4158 cost
.cost
/= avg_loop_niter (data
->current_loop
);
4159 cost
.cost
+= add_cost (TYPE_MODE (ctype
), data
->speed
);
4165 get_loop_invariant_expr_id (data
, ubase
, cbase
, ratio
, address_p
);
4166 /* Clear depends on. */
4167 if (*inv_expr_id
!= -1 && depends_on
&& *depends_on
)
4168 bitmap_clear (*depends_on
);
4171 /* If we are after the increment, the value of the candidate is higher by
4173 if (stmt_is_after_inc
)
4174 offset
-= ratio
* cstepi
;
4176 /* Now the computation is in shape symbol + var1 + const + ratio * var2.
4177 (symbol/var1/const parts may be omitted). If we are looking for an
4178 address, find the cost of addressing this. */
4180 return add_costs (cost
,
4181 get_address_cost (symbol_present
, var_present
,
4182 offset
, ratio
, cstepi
,
4183 TYPE_MODE (TREE_TYPE (utype
)),
4184 TYPE_ADDR_SPACE (TREE_TYPE (utype
)),
4185 speed
, stmt_is_after_inc
,
4188 /* Otherwise estimate the costs for computing the expression. */
4189 if (!symbol_present
&& !var_present
&& !offset
)
4192 cost
.cost
+= multiply_by_cost (ratio
, TYPE_MODE (ctype
), speed
);
4196 /* Symbol + offset should be compile-time computable so consider that they
4197 are added once to the variable, if present. */
4198 if (var_present
&& (symbol_present
|| offset
))
4199 cost
.cost
+= adjust_setup_cost (data
,
4200 add_cost (TYPE_MODE (ctype
), speed
));
4202 /* Having offset does not affect runtime cost in case it is added to
4203 symbol, but it increases complexity. */
4207 cost
.cost
+= add_cost (TYPE_MODE (ctype
), speed
);
4209 aratio
= ratio
> 0 ? ratio
: -ratio
;
4211 cost
.cost
+= multiply_by_cost (aratio
, TYPE_MODE (ctype
), speed
);
4216 *can_autoinc
= false;
4219 /* Just get the expression, expand it and measure the cost. */
4220 tree comp
= get_computation_at (data
->current_loop
, use
, cand
, at
);
4223 return infinite_cost
;
4226 comp
= build_simple_mem_ref (comp
);
4228 return new_cost (computation_cost (comp
, speed
), 0);
4232 /* Determines the cost of the computation by that USE is expressed
4233 from induction variable CAND. If ADDRESS_P is true, we just need
4234 to create an address from it, otherwise we want to get it into
4235 register. A set of invariants we depend on is stored in
4236 DEPENDS_ON. If CAN_AUTOINC is nonnull, use it to record whether
4237 autoinc addressing is likely. */
4240 get_computation_cost (struct ivopts_data
*data
,
4241 struct iv_use
*use
, struct iv_cand
*cand
,
4242 bool address_p
, bitmap
*depends_on
,
4243 bool *can_autoinc
, int *inv_expr_id
)
4245 return get_computation_cost_at (data
,
4246 use
, cand
, address_p
, depends_on
, use
->stmt
,
4247 can_autoinc
, inv_expr_id
);
4250 /* Determines cost of basing replacement of USE on CAND in a generic
4254 determine_use_iv_cost_generic (struct ivopts_data
*data
,
4255 struct iv_use
*use
, struct iv_cand
*cand
)
4259 int inv_expr_id
= -1;
4261 /* The simple case first -- if we need to express value of the preserved
4262 original biv, the cost is 0. This also prevents us from counting the
4263 cost of increment twice -- once at this use and once in the cost of
4265 if (cand
->pos
== IP_ORIGINAL
4266 && cand
->incremented_at
== use
->stmt
)
4268 set_use_iv_cost (data
, use
, cand
, zero_cost
, NULL
, NULL_TREE
,
4273 cost
= get_computation_cost (data
, use
, cand
, false, &depends_on
,
4274 NULL
, &inv_expr_id
);
4276 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
, ERROR_MARK
,
4279 return !infinite_cost_p (cost
);
4282 /* Determines cost of basing replacement of USE on CAND in an address. */
4285 determine_use_iv_cost_address (struct ivopts_data
*data
,
4286 struct iv_use
*use
, struct iv_cand
*cand
)
4290 int inv_expr_id
= -1;
4291 comp_cost cost
= get_computation_cost (data
, use
, cand
, true, &depends_on
,
4292 &can_autoinc
, &inv_expr_id
);
4294 if (cand
->ainc_use
== use
)
4297 cost
.cost
-= cand
->cost_step
;
4298 /* If we generated the candidate solely for exploiting autoincrement
4299 opportunities, and it turns out it can't be used, set the cost to
4300 infinity to make sure we ignore it. */
4301 else if (cand
->pos
== IP_AFTER_USE
|| cand
->pos
== IP_BEFORE_USE
)
4302 cost
= infinite_cost
;
4304 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
, ERROR_MARK
,
4307 return !infinite_cost_p (cost
);
4310 /* Computes value of candidate CAND at position AT in iteration NITER, and
4311 stores it to VAL. */
4314 cand_value_at (struct loop
*loop
, struct iv_cand
*cand
, gimple at
, tree niter
,
4317 aff_tree step
, delta
, nit
;
4318 struct iv
*iv
= cand
->iv
;
4319 tree type
= TREE_TYPE (iv
->base
);
4320 tree steptype
= type
;
4321 if (POINTER_TYPE_P (type
))
4322 steptype
= sizetype
;
4324 tree_to_aff_combination (iv
->step
, steptype
, &step
);
4325 tree_to_aff_combination (niter
, TREE_TYPE (niter
), &nit
);
4326 aff_combination_convert (&nit
, steptype
);
4327 aff_combination_mult (&nit
, &step
, &delta
);
4328 if (stmt_after_increment (loop
, cand
, at
))
4329 aff_combination_add (&delta
, &step
);
4331 tree_to_aff_combination (iv
->base
, type
, val
);
4332 aff_combination_add (val
, &delta
);
4335 /* Returns period of induction variable iv. */
4338 iv_period (struct iv
*iv
)
4340 tree step
= iv
->step
, period
, type
;
4343 gcc_assert (step
&& TREE_CODE (step
) == INTEGER_CST
);
4345 type
= unsigned_type_for (TREE_TYPE (step
));
4346 /* Period of the iv is lcm (step, type_range)/step -1,
4347 i.e., N*type_range/step - 1. Since type range is power
4348 of two, N == (step >> num_of_ending_zeros_binary (step),
4349 so the final result is
4351 (type_range >> num_of_ending_zeros_binary (step)) - 1
4354 pow2div
= num_ending_zeros (step
);
4356 period
= build_low_bits_mask (type
,
4357 (TYPE_PRECISION (type
)
4358 - tree_low_cst (pow2div
, 1)));
4363 /* Returns the comparison operator used when eliminating the iv USE. */
4365 static enum tree_code
4366 iv_elimination_compare (struct ivopts_data
*data
, struct iv_use
*use
)
4368 struct loop
*loop
= data
->current_loop
;
4372 ex_bb
= gimple_bb (use
->stmt
);
4373 exit
= EDGE_SUCC (ex_bb
, 0);
4374 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
4375 exit
= EDGE_SUCC (ex_bb
, 1);
4377 return (exit
->flags
& EDGE_TRUE_VALUE
? EQ_EXPR
: NE_EXPR
);
4381 strip_wrap_conserving_type_conversions (tree exp
)
4383 while (tree_ssa_useless_type_conversion (exp
)
4384 && (nowrap_type_p (TREE_TYPE (exp
))
4385 == nowrap_type_p (TREE_TYPE (TREE_OPERAND (exp
, 0)))))
4386 exp
= TREE_OPERAND (exp
, 0);
4390 /* Walk the SSA form and check whether E == WHAT. Fairly simplistic, we
4391 check for an exact match. */
4394 expr_equal_p (tree e
, tree what
)
4397 enum tree_code code
;
4399 e
= strip_wrap_conserving_type_conversions (e
);
4400 what
= strip_wrap_conserving_type_conversions (what
);
4402 code
= TREE_CODE (what
);
4403 if (TREE_TYPE (e
) != TREE_TYPE (what
))
4406 if (operand_equal_p (e
, what
, 0))
4409 if (TREE_CODE (e
) != SSA_NAME
)
4412 stmt
= SSA_NAME_DEF_STMT (e
);
4413 if (gimple_code (stmt
) != GIMPLE_ASSIGN
4414 || gimple_assign_rhs_code (stmt
) != code
)
4417 switch (get_gimple_rhs_class (code
))
4419 case GIMPLE_BINARY_RHS
:
4420 if (!expr_equal_p (gimple_assign_rhs2 (stmt
), TREE_OPERAND (what
, 1)))
4424 case GIMPLE_UNARY_RHS
:
4425 case GIMPLE_SINGLE_RHS
:
4426 return expr_equal_p (gimple_assign_rhs1 (stmt
), TREE_OPERAND (what
, 0));
4432 /* Returns true if we can prove that BASE - OFFSET does not overflow. For now,
4433 we only detect the situation that BASE = SOMETHING + OFFSET, where the
4434 calculation is performed in non-wrapping type.
4436 TODO: More generally, we could test for the situation that
4437 BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero.
4438 This would require knowing the sign of OFFSET.
4440 Also, we only look for the first addition in the computation of BASE.
4441 More complex analysis would be better, but introducing it just for
4442 this optimization seems like an overkill. */
4445 difference_cannot_overflow_p (tree base
, tree offset
)
4447 enum tree_code code
;
4450 if (!nowrap_type_p (TREE_TYPE (base
)))
4453 base
= expand_simple_operations (base
);
4455 if (TREE_CODE (base
) == SSA_NAME
)
4457 gimple stmt
= SSA_NAME_DEF_STMT (base
);
4459 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
4462 code
= gimple_assign_rhs_code (stmt
);
4463 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
4466 e1
= gimple_assign_rhs1 (stmt
);
4467 e2
= gimple_assign_rhs2 (stmt
);
4471 code
= TREE_CODE (base
);
4472 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
4474 e1
= TREE_OPERAND (base
, 0);
4475 e2
= TREE_OPERAND (base
, 1);
4478 /* TODO: deeper inspection may be necessary to prove the equality. */
4482 return expr_equal_p (e1
, offset
) || expr_equal_p (e2
, offset
);
4483 case POINTER_PLUS_EXPR
:
4484 return expr_equal_p (e2
, offset
);
4491 /* Tries to replace loop exit by one formulated in terms of a LT_EXPR
4492 comparison with CAND. NITER describes the number of iterations of
4493 the loops. If successful, the comparison in COMP_P is altered accordingly.
4495 We aim to handle the following situation:
4511 Here, the number of iterations of the loop is (a + 1 > b) ? 0 : b - a - 1.
4512 We aim to optimize this to
4520 while (p < p_0 - a + b);
4522 This preserves the correctness, since the pointer arithmetics does not
4523 overflow. More precisely:
4525 1) if a + 1 <= b, then p_0 - a + b is the final value of p, hence there is no
4526 overflow in computing it or the values of p.
4527 2) if a + 1 > b, then we need to verify that the expression p_0 - a does not
4528 overflow. To prove this, we use the fact that p_0 = base + a. */
4531 iv_elimination_compare_lt (struct ivopts_data
*data
,
4532 struct iv_cand
*cand
, enum tree_code
*comp_p
,
4533 struct tree_niter_desc
*niter
)
4535 tree cand_type
, a
, b
, mbz
, nit_type
= TREE_TYPE (niter
->niter
), offset
;
4536 struct affine_tree_combination nit
, tmpa
, tmpb
;
4537 enum tree_code comp
;
4540 /* We need to know that the candidate induction variable does not overflow.
4541 While more complex analysis may be used to prove this, for now just
4542 check that the variable appears in the original program and that it
4543 is computed in a type that guarantees no overflows. */
4544 cand_type
= TREE_TYPE (cand
->iv
->base
);
4545 if (cand
->pos
!= IP_ORIGINAL
|| !nowrap_type_p (cand_type
))
4548 /* Make sure that the loop iterates till the loop bound is hit, as otherwise
4549 the calculation of the BOUND could overflow, making the comparison
4551 if (!data
->loop_single_exit_p
)
4554 /* We need to be able to decide whether candidate is increasing or decreasing
4555 in order to choose the right comparison operator. */
4556 if (!cst_and_fits_in_hwi (cand
->iv
->step
))
4558 step
= int_cst_value (cand
->iv
->step
);
4560 /* Check that the number of iterations matches the expected pattern:
4561 a + 1 > b ? 0 : b - a - 1. */
4562 mbz
= niter
->may_be_zero
;
4563 if (TREE_CODE (mbz
) == GT_EXPR
)
4565 /* Handle a + 1 > b. */
4566 tree op0
= TREE_OPERAND (mbz
, 0);
4567 if (TREE_CODE (op0
) == PLUS_EXPR
&& integer_onep (TREE_OPERAND (op0
, 1)))
4569 a
= TREE_OPERAND (op0
, 0);
4570 b
= TREE_OPERAND (mbz
, 1);
4575 else if (TREE_CODE (mbz
) == LT_EXPR
)
4577 tree op1
= TREE_OPERAND (mbz
, 1);
4579 /* Handle b < a + 1. */
4580 if (TREE_CODE (op1
) == PLUS_EXPR
&& integer_onep (TREE_OPERAND (op1
, 1)))
4582 a
= TREE_OPERAND (op1
, 0);
4583 b
= TREE_OPERAND (mbz
, 0);
4591 /* Expected number of iterations is B - A - 1. Check that it matches
4592 the actual number, i.e., that B - A - NITER = 1. */
4593 tree_to_aff_combination (niter
->niter
, nit_type
, &nit
);
4594 tree_to_aff_combination (fold_convert (nit_type
, a
), nit_type
, &tmpa
);
4595 tree_to_aff_combination (fold_convert (nit_type
, b
), nit_type
, &tmpb
);
4596 aff_combination_scale (&nit
, double_int_minus_one
);
4597 aff_combination_scale (&tmpa
, double_int_minus_one
);
4598 aff_combination_add (&tmpb
, &tmpa
);
4599 aff_combination_add (&tmpb
, &nit
);
4600 if (tmpb
.n
!= 0 || !double_int_equal_p (tmpb
.offset
, double_int_one
))
4603 /* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not
4605 offset
= fold_build2 (MULT_EXPR
, TREE_TYPE (cand
->iv
->step
),
4607 fold_convert (TREE_TYPE (cand
->iv
->step
), a
));
4608 if (!difference_cannot_overflow_p (cand
->iv
->base
, offset
))
4611 /* Determine the new comparison operator. */
4612 comp
= step
< 0 ? GT_EXPR
: LT_EXPR
;
4613 if (*comp_p
== NE_EXPR
)
4615 else if (*comp_p
== EQ_EXPR
)
4616 *comp_p
= invert_tree_comparison (comp
, false);
4623 /* Check whether it is possible to express the condition in USE by comparison
4624 of candidate CAND. If so, store the value compared with to BOUND, and the
4625 comparison operator to COMP. */
4628 may_eliminate_iv (struct ivopts_data
*data
,
4629 struct iv_use
*use
, struct iv_cand
*cand
, tree
*bound
,
4630 enum tree_code
*comp
)
4635 struct loop
*loop
= data
->current_loop
;
4637 struct tree_niter_desc
*desc
= NULL
;
4639 if (TREE_CODE (cand
->iv
->step
) != INTEGER_CST
)
4642 /* For now works only for exits that dominate the loop latch.
4643 TODO: extend to other conditions inside loop body. */
4644 ex_bb
= gimple_bb (use
->stmt
);
4645 if (use
->stmt
!= last_stmt (ex_bb
)
4646 || gimple_code (use
->stmt
) != GIMPLE_COND
4647 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, ex_bb
))
4650 exit
= EDGE_SUCC (ex_bb
, 0);
4651 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
4652 exit
= EDGE_SUCC (ex_bb
, 1);
4653 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
4656 desc
= niter_for_exit (data
, exit
);
4660 /* Determine whether we can use the variable to test the exit condition.
4661 This is the case iff the period of the induction variable is greater
4662 than the number of iterations for which the exit condition is true. */
4663 period
= iv_period (cand
->iv
);
4665 /* If the number of iterations is constant, compare against it directly. */
4666 if (TREE_CODE (desc
->niter
) == INTEGER_CST
)
4668 /* See cand_value_at. */
4669 if (stmt_after_increment (loop
, cand
, use
->stmt
))
4671 if (!tree_int_cst_lt (desc
->niter
, period
))
4676 if (tree_int_cst_lt (period
, desc
->niter
))
4681 /* If not, and if this is the only possible exit of the loop, see whether
4682 we can get a conservative estimate on the number of iterations of the
4683 entire loop and compare against that instead. */
4686 double_int period_value
, max_niter
;
4688 max_niter
= desc
->max
;
4689 if (stmt_after_increment (loop
, cand
, use
->stmt
))
4690 max_niter
= double_int_add (max_niter
, double_int_one
);
4691 period_value
= tree_to_double_int (period
);
4692 if (double_int_ucmp (max_niter
, period_value
) > 0)
4694 /* See if we can take advantage of infered loop bound information. */
4695 if (data
->loop_single_exit_p
)
4697 if (!estimated_loop_iterations (loop
, true, &max_niter
))
4699 /* The loop bound is already adjusted by adding 1. */
4700 if (double_int_ucmp (max_niter
, period_value
) > 0)
4708 cand_value_at (loop
, cand
, use
->stmt
, desc
->niter
, &bnd
);
4710 *bound
= aff_combination_to_tree (&bnd
);
4711 *comp
= iv_elimination_compare (data
, use
);
4713 /* It is unlikely that computing the number of iterations using division
4714 would be more profitable than keeping the original induction variable. */
4715 if (expression_expensive_p (*bound
))
4718 /* Sometimes, it is possible to handle the situation that the number of
4719 iterations may be zero unless additional assumtions by using <
4720 instead of != in the exit condition.
4722 TODO: we could also calculate the value MAY_BE_ZERO ? 0 : NITER and
4723 base the exit condition on it. However, that is often too
4725 if (!integer_zerop (desc
->may_be_zero
))
4726 return iv_elimination_compare_lt (data
, cand
, comp
, desc
);
4731 /* Calculates the cost of BOUND, if it is a PARM_DECL. A PARM_DECL must
4732 be copied, if is is used in the loop body and DATA->body_includes_call. */
4735 parm_decl_cost (struct ivopts_data
*data
, tree bound
)
4737 tree sbound
= bound
;
4738 STRIP_NOPS (sbound
);
4740 if (TREE_CODE (sbound
) == SSA_NAME
4741 && TREE_CODE (SSA_NAME_VAR (sbound
)) == PARM_DECL
4742 && gimple_nop_p (SSA_NAME_DEF_STMT (sbound
))
4743 && data
->body_includes_call
)
4744 return COSTS_N_INSNS (1);
4749 /* Determines cost of basing replacement of USE on CAND in a condition. */
4752 determine_use_iv_cost_condition (struct ivopts_data
*data
,
4753 struct iv_use
*use
, struct iv_cand
*cand
)
4755 tree bound
= NULL_TREE
;
4757 bitmap depends_on_elim
= NULL
, depends_on_express
= NULL
, depends_on
;
4758 comp_cost elim_cost
, express_cost
, cost
, bound_cost
;
4760 int elim_inv_expr_id
= -1, express_inv_expr_id
= -1, inv_expr_id
;
4761 tree
*control_var
, *bound_cst
;
4762 enum tree_code comp
= ERROR_MARK
;
4764 /* Only consider real candidates. */
4767 set_use_iv_cost (data
, use
, cand
, infinite_cost
, NULL
, NULL_TREE
,
4772 /* Try iv elimination. */
4773 if (may_eliminate_iv (data
, use
, cand
, &bound
, &comp
))
4775 elim_cost
= force_var_cost (data
, bound
, &depends_on_elim
);
4776 if (elim_cost
.cost
== 0)
4777 elim_cost
.cost
= parm_decl_cost (data
, bound
);
4778 else if (TREE_CODE (bound
) == INTEGER_CST
)
4780 /* If we replace a loop condition 'i < n' with 'p < base + n',
4781 depends_on_elim will have 'base' and 'n' set, which implies
4782 that both 'base' and 'n' will be live during the loop. More likely,
4783 'base + n' will be loop invariant, resulting in only one live value
4784 during the loop. So in that case we clear depends_on_elim and set
4785 elim_inv_expr_id instead. */
4786 if (depends_on_elim
&& bitmap_count_bits (depends_on_elim
) > 1)
4788 elim_inv_expr_id
= get_expr_id (data
, bound
);
4789 bitmap_clear (depends_on_elim
);
4791 /* The bound is a loop invariant, so it will be only computed
4793 elim_cost
.cost
= adjust_setup_cost (data
, elim_cost
.cost
);
4796 elim_cost
= infinite_cost
;
4798 /* Try expressing the original giv. If it is compared with an invariant,
4799 note that we cannot get rid of it. */
4800 ok
= extract_cond_operands (data
, use
->stmt
, &control_var
, &bound_cst
,
4804 /* When the condition is a comparison of the candidate IV against
4805 zero, prefer this IV.
4807 TODO: The constant that we're substracting from the cost should
4808 be target-dependent. This information should be added to the
4809 target costs for each backend. */
4810 if (!infinite_cost_p (elim_cost
) /* Do not try to decrease infinite! */
4811 && integer_zerop (*bound_cst
)
4812 && (operand_equal_p (*control_var
, cand
->var_after
, 0)
4813 || operand_equal_p (*control_var
, cand
->var_before
, 0)))
4814 elim_cost
.cost
-= 1;
4816 express_cost
= get_computation_cost (data
, use
, cand
, false,
4817 &depends_on_express
, NULL
,
4818 &express_inv_expr_id
);
4819 fd_ivopts_data
= data
;
4820 walk_tree (&cmp_iv
->base
, find_depends
, &depends_on_express
, NULL
);
4822 /* Count the cost of the original bound as well. */
4823 bound_cost
= force_var_cost (data
, *bound_cst
, NULL
);
4824 if (bound_cost
.cost
== 0)
4825 bound_cost
.cost
= parm_decl_cost (data
, *bound_cst
);
4826 else if (TREE_CODE (*bound_cst
) == INTEGER_CST
)
4827 bound_cost
.cost
= 0;
4828 express_cost
.cost
+= bound_cost
.cost
;
4830 /* Choose the better approach, preferring the eliminated IV. */
4831 if (compare_costs (elim_cost
, express_cost
) <= 0)
4834 depends_on
= depends_on_elim
;
4835 depends_on_elim
= NULL
;
4836 inv_expr_id
= elim_inv_expr_id
;
4840 cost
= express_cost
;
4841 depends_on
= depends_on_express
;
4842 depends_on_express
= NULL
;
4845 inv_expr_id
= express_inv_expr_id
;
4848 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, bound
, comp
, inv_expr_id
);
4850 if (depends_on_elim
)
4851 BITMAP_FREE (depends_on_elim
);
4852 if (depends_on_express
)
4853 BITMAP_FREE (depends_on_express
);
4855 return !infinite_cost_p (cost
);
4858 /* Determines cost of basing replacement of USE on CAND. Returns false
4859 if USE cannot be based on CAND. */
4862 determine_use_iv_cost (struct ivopts_data
*data
,
4863 struct iv_use
*use
, struct iv_cand
*cand
)
4867 case USE_NONLINEAR_EXPR
:
4868 return determine_use_iv_cost_generic (data
, use
, cand
);
4871 return determine_use_iv_cost_address (data
, use
, cand
);
4874 return determine_use_iv_cost_condition (data
, use
, cand
);
4881 /* Return true if get_computation_cost indicates that autoincrement is
4882 a possibility for the pair of USE and CAND, false otherwise. */
4885 autoinc_possible_for_pair (struct ivopts_data
*data
, struct iv_use
*use
,
4886 struct iv_cand
*cand
)
4892 if (use
->type
!= USE_ADDRESS
)
4895 cost
= get_computation_cost (data
, use
, cand
, true, &depends_on
,
4896 &can_autoinc
, NULL
);
4898 BITMAP_FREE (depends_on
);
4900 return !infinite_cost_p (cost
) && can_autoinc
;
4903 /* Examine IP_ORIGINAL candidates to see if they are incremented next to a
4904 use that allows autoincrement, and set their AINC_USE if possible. */
4907 set_autoinc_for_original_candidates (struct ivopts_data
*data
)
4911 for (i
= 0; i
< n_iv_cands (data
); i
++)
4913 struct iv_cand
*cand
= iv_cand (data
, i
);
4914 struct iv_use
*closest
= NULL
;
4915 if (cand
->pos
!= IP_ORIGINAL
)
4917 for (j
= 0; j
< n_iv_uses (data
); j
++)
4919 struct iv_use
*use
= iv_use (data
, j
);
4920 unsigned uid
= gimple_uid (use
->stmt
);
4921 if (gimple_bb (use
->stmt
) != gimple_bb (cand
->incremented_at
)
4922 || uid
> gimple_uid (cand
->incremented_at
))
4924 if (closest
== NULL
|| uid
> gimple_uid (closest
->stmt
))
4927 if (closest
== NULL
|| !autoinc_possible_for_pair (data
, closest
, cand
))
4929 cand
->ainc_use
= closest
;
4933 /* Finds the candidates for the induction variables. */
4936 find_iv_candidates (struct ivopts_data
*data
)
4938 /* Add commonly used ivs. */
4939 add_standard_iv_candidates (data
);
4941 /* Add old induction variables. */
4942 add_old_ivs_candidates (data
);
4944 /* Add induction variables derived from uses. */
4945 add_derived_ivs_candidates (data
);
4947 set_autoinc_for_original_candidates (data
);
4949 /* Record the important candidates. */
4950 record_important_candidates (data
);
4953 /* Determines costs of basing the use of the iv on an iv candidate. */
4956 determine_use_iv_costs (struct ivopts_data
*data
)
4960 struct iv_cand
*cand
;
4961 bitmap to_clear
= BITMAP_ALLOC (NULL
);
4963 alloc_use_cost_map (data
);
4965 for (i
= 0; i
< n_iv_uses (data
); i
++)
4967 use
= iv_use (data
, i
);
4969 if (data
->consider_all_candidates
)
4971 for (j
= 0; j
< n_iv_cands (data
); j
++)
4973 cand
= iv_cand (data
, j
);
4974 determine_use_iv_cost (data
, use
, cand
);
4981 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, j
, bi
)
4983 cand
= iv_cand (data
, j
);
4984 if (!determine_use_iv_cost (data
, use
, cand
))
4985 bitmap_set_bit (to_clear
, j
);
4988 /* Remove the candidates for that the cost is infinite from
4989 the list of related candidates. */
4990 bitmap_and_compl_into (use
->related_cands
, to_clear
);
4991 bitmap_clear (to_clear
);
4995 BITMAP_FREE (to_clear
);
4997 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4999 fprintf (dump_file
, "Use-candidate costs:\n");
5001 for (i
= 0; i
< n_iv_uses (data
); i
++)
5003 use
= iv_use (data
, i
);
5005 fprintf (dump_file
, "Use %d:\n", i
);
5006 fprintf (dump_file
, " cand\tcost\tcompl.\tdepends on\n");
5007 for (j
= 0; j
< use
->n_map_members
; j
++)
5009 if (!use
->cost_map
[j
].cand
5010 || infinite_cost_p (use
->cost_map
[j
].cost
))
5013 fprintf (dump_file
, " %d\t%d\t%d\t",
5014 use
->cost_map
[j
].cand
->id
,
5015 use
->cost_map
[j
].cost
.cost
,
5016 use
->cost_map
[j
].cost
.complexity
);
5017 if (use
->cost_map
[j
].depends_on
)
5018 bitmap_print (dump_file
,
5019 use
->cost_map
[j
].depends_on
, "","");
5020 if (use
->cost_map
[j
].inv_expr_id
!= -1)
5021 fprintf (dump_file
, " inv_expr:%d", use
->cost_map
[j
].inv_expr_id
);
5022 fprintf (dump_file
, "\n");
5025 fprintf (dump_file
, "\n");
5027 fprintf (dump_file
, "\n");
5031 /* Determines cost of the candidate CAND. */
5034 determine_iv_cost (struct ivopts_data
*data
, struct iv_cand
*cand
)
5036 comp_cost cost_base
;
5037 unsigned cost
, cost_step
;
5046 /* There are two costs associated with the candidate -- its increment
5047 and its initialization. The second is almost negligible for any loop
5048 that rolls enough, so we take it just very little into account. */
5050 base
= cand
->iv
->base
;
5051 cost_base
= force_var_cost (data
, base
, NULL
);
5052 /* It will be exceptional that the iv register happens to be initialized with
5053 the proper value at no cost. In general, there will at least be a regcopy
5055 if (cost_base
.cost
== 0)
5056 cost_base
.cost
= COSTS_N_INSNS (1);
5057 cost_step
= add_cost (TYPE_MODE (TREE_TYPE (base
)), data
->speed
);
5059 cost
= cost_step
+ adjust_setup_cost (data
, cost_base
.cost
);
5061 /* Prefer the original ivs unless we may gain something by replacing it.
5062 The reason is to make debugging simpler; so this is not relevant for
5063 artificial ivs created by other optimization passes. */
5064 if (cand
->pos
!= IP_ORIGINAL
5065 || DECL_ARTIFICIAL (SSA_NAME_VAR (cand
->var_before
)))
5068 /* Prefer not to insert statements into latch unless there are some
5069 already (so that we do not create unnecessary jumps). */
5070 if (cand
->pos
== IP_END
5071 && empty_block_p (ip_end_pos (data
->current_loop
)))
5075 cand
->cost_step
= cost_step
;
5078 /* Determines costs of computation of the candidates. */
5081 determine_iv_costs (struct ivopts_data
*data
)
5085 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5087 fprintf (dump_file
, "Candidate costs:\n");
5088 fprintf (dump_file
, " cand\tcost\n");
5091 for (i
= 0; i
< n_iv_cands (data
); i
++)
5093 struct iv_cand
*cand
= iv_cand (data
, i
);
5095 determine_iv_cost (data
, cand
);
5097 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5098 fprintf (dump_file
, " %d\t%d\n", i
, cand
->cost
);
5101 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5102 fprintf (dump_file
, "\n");
5105 /* Calculates cost for having SIZE induction variables. */
5108 ivopts_global_cost_for_size (struct ivopts_data
*data
, unsigned size
)
5110 /* We add size to the cost, so that we prefer eliminating ivs
5112 return size
+ estimate_reg_pressure_cost (size
, data
->regs_used
, data
->speed
,
5113 data
->body_includes_call
);
5116 /* For each size of the induction variable set determine the penalty. */
5119 determine_set_costs (struct ivopts_data
*data
)
5123 gimple_stmt_iterator psi
;
5125 struct loop
*loop
= data
->current_loop
;
5128 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5130 fprintf (dump_file
, "Global costs:\n");
5131 fprintf (dump_file
, " target_avail_regs %d\n", target_avail_regs
);
5132 fprintf (dump_file
, " target_clobbered_regs %d\n", target_clobbered_regs
);
5133 fprintf (dump_file
, " target_reg_cost %d\n", target_reg_cost
[data
->speed
]);
5134 fprintf (dump_file
, " target_spill_cost %d\n", target_spill_cost
[data
->speed
]);
5138 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
5140 phi
= gsi_stmt (psi
);
5141 op
= PHI_RESULT (phi
);
5143 if (!is_gimple_reg (op
))
5146 if (get_iv (data
, op
))
5152 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
5154 struct version_info
*info
= ver_info (data
, j
);
5156 if (info
->inv_id
&& info
->has_nonlin_use
)
5160 data
->regs_used
= n
;
5161 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5162 fprintf (dump_file
, " regs_used %d\n", n
);
5164 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5166 fprintf (dump_file
, " cost for size:\n");
5167 fprintf (dump_file
, " ivs\tcost\n");
5168 for (j
= 0; j
<= 2 * target_avail_regs
; j
++)
5169 fprintf (dump_file
, " %d\t%d\n", j
,
5170 ivopts_global_cost_for_size (data
, j
));
5171 fprintf (dump_file
, "\n");
5175 /* Returns true if A is a cheaper cost pair than B. */
5178 cheaper_cost_pair (struct cost_pair
*a
, struct cost_pair
*b
)
5188 cmp
= compare_costs (a
->cost
, b
->cost
);
5195 /* In case the costs are the same, prefer the cheaper candidate. */
5196 if (a
->cand
->cost
< b
->cand
->cost
)
5203 /* Returns candidate by that USE is expressed in IVS. */
5205 static struct cost_pair
*
5206 iv_ca_cand_for_use (struct iv_ca
*ivs
, struct iv_use
*use
)
5208 return ivs
->cand_for_use
[use
->id
];
5211 /* Computes the cost field of IVS structure. */
5214 iv_ca_recount_cost (struct ivopts_data
*data
, struct iv_ca
*ivs
)
5216 comp_cost cost
= ivs
->cand_use_cost
;
5218 cost
.cost
+= ivs
->cand_cost
;
5220 cost
.cost
+= ivopts_global_cost_for_size (data
,
5221 ivs
->n_regs
+ ivs
->num_used_inv_expr
);
5226 /* Remove invariants in set INVS to set IVS. */
5229 iv_ca_set_remove_invariants (struct iv_ca
*ivs
, bitmap invs
)
5237 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
5239 ivs
->n_invariant_uses
[iid
]--;
5240 if (ivs
->n_invariant_uses
[iid
] == 0)
5245 /* Set USE not to be expressed by any candidate in IVS. */
5248 iv_ca_set_no_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5251 unsigned uid
= use
->id
, cid
;
5252 struct cost_pair
*cp
;
5254 cp
= ivs
->cand_for_use
[uid
];
5260 ivs
->cand_for_use
[uid
] = NULL
;
5261 ivs
->n_cand_uses
[cid
]--;
5263 if (ivs
->n_cand_uses
[cid
] == 0)
5265 bitmap_clear_bit (ivs
->cands
, cid
);
5266 /* Do not count the pseudocandidates. */
5270 ivs
->cand_cost
-= cp
->cand
->cost
;
5272 iv_ca_set_remove_invariants (ivs
, cp
->cand
->depends_on
);
5275 ivs
->cand_use_cost
= sub_costs (ivs
->cand_use_cost
, cp
->cost
);
5277 iv_ca_set_remove_invariants (ivs
, cp
->depends_on
);
5279 if (cp
->inv_expr_id
!= -1)
5281 ivs
->used_inv_expr
[cp
->inv_expr_id
]--;
5282 if (ivs
->used_inv_expr
[cp
->inv_expr_id
] == 0)
5283 ivs
->num_used_inv_expr
--;
5285 iv_ca_recount_cost (data
, ivs
);
5288 /* Add invariants in set INVS to set IVS. */
5291 iv_ca_set_add_invariants (struct iv_ca
*ivs
, bitmap invs
)
5299 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
5301 ivs
->n_invariant_uses
[iid
]++;
5302 if (ivs
->n_invariant_uses
[iid
] == 1)
5307 /* Set cost pair for USE in set IVS to CP. */
5310 iv_ca_set_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5311 struct iv_use
*use
, struct cost_pair
*cp
)
5313 unsigned uid
= use
->id
, cid
;
5315 if (ivs
->cand_for_use
[uid
] == cp
)
5318 if (ivs
->cand_for_use
[uid
])
5319 iv_ca_set_no_cp (data
, ivs
, use
);
5326 ivs
->cand_for_use
[uid
] = cp
;
5327 ivs
->n_cand_uses
[cid
]++;
5328 if (ivs
->n_cand_uses
[cid
] == 1)
5330 bitmap_set_bit (ivs
->cands
, cid
);
5331 /* Do not count the pseudocandidates. */
5335 ivs
->cand_cost
+= cp
->cand
->cost
;
5337 iv_ca_set_add_invariants (ivs
, cp
->cand
->depends_on
);
5340 ivs
->cand_use_cost
= add_costs (ivs
->cand_use_cost
, cp
->cost
);
5341 iv_ca_set_add_invariants (ivs
, cp
->depends_on
);
5343 if (cp
->inv_expr_id
!= -1)
5345 ivs
->used_inv_expr
[cp
->inv_expr_id
]++;
5346 if (ivs
->used_inv_expr
[cp
->inv_expr_id
] == 1)
5347 ivs
->num_used_inv_expr
++;
5349 iv_ca_recount_cost (data
, ivs
);
5353 /* Extend set IVS by expressing USE by some of the candidates in it
5354 if possible. All important candidates will be considered
5355 if IMPORTANT_CANDIDATES is true. */
5358 iv_ca_add_use (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5359 struct iv_use
*use
, bool important_candidates
)
5361 struct cost_pair
*best_cp
= NULL
, *cp
;
5366 gcc_assert (ivs
->upto
>= use
->id
);
5368 if (ivs
->upto
== use
->id
)
5374 cands
= (important_candidates
? data
->important_candidates
: ivs
->cands
);
5375 EXECUTE_IF_SET_IN_BITMAP (cands
, 0, i
, bi
)
5377 struct iv_cand
*cand
= iv_cand (data
, i
);
5379 cp
= get_use_iv_cost (data
, use
, cand
);
5381 if (cheaper_cost_pair (cp
, best_cp
))
5385 iv_ca_set_cp (data
, ivs
, use
, best_cp
);
5388 /* Get cost for assignment IVS. */
5391 iv_ca_cost (struct iv_ca
*ivs
)
5393 /* This was a conditional expression but it triggered a bug in
5396 return infinite_cost
;
5401 /* Returns true if all dependences of CP are among invariants in IVS. */
5404 iv_ca_has_deps (struct iv_ca
*ivs
, struct cost_pair
*cp
)
5409 if (!cp
->depends_on
)
5412 EXECUTE_IF_SET_IN_BITMAP (cp
->depends_on
, 0, i
, bi
)
5414 if (ivs
->n_invariant_uses
[i
] == 0)
5421 /* Creates change of expressing USE by NEW_CP instead of OLD_CP and chains
5422 it before NEXT_CHANGE. */
5424 static struct iv_ca_delta
*
5425 iv_ca_delta_add (struct iv_use
*use
, struct cost_pair
*old_cp
,
5426 struct cost_pair
*new_cp
, struct iv_ca_delta
*next_change
)
5428 struct iv_ca_delta
*change
= XNEW (struct iv_ca_delta
);
5431 change
->old_cp
= old_cp
;
5432 change
->new_cp
= new_cp
;
5433 change
->next_change
= next_change
;
5438 /* Joins two lists of changes L1 and L2. Destructive -- old lists
5441 static struct iv_ca_delta
*
5442 iv_ca_delta_join (struct iv_ca_delta
*l1
, struct iv_ca_delta
*l2
)
5444 struct iv_ca_delta
*last
;
5452 for (last
= l1
; last
->next_change
; last
= last
->next_change
)
5454 last
->next_change
= l2
;
5459 /* Reverse the list of changes DELTA, forming the inverse to it. */
5461 static struct iv_ca_delta
*
5462 iv_ca_delta_reverse (struct iv_ca_delta
*delta
)
5464 struct iv_ca_delta
*act
, *next
, *prev
= NULL
;
5465 struct cost_pair
*tmp
;
5467 for (act
= delta
; act
; act
= next
)
5469 next
= act
->next_change
;
5470 act
->next_change
= prev
;
5474 act
->old_cp
= act
->new_cp
;
5481 /* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
5482 reverted instead. */
5485 iv_ca_delta_commit (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5486 struct iv_ca_delta
*delta
, bool forward
)
5488 struct cost_pair
*from
, *to
;
5489 struct iv_ca_delta
*act
;
5492 delta
= iv_ca_delta_reverse (delta
);
5494 for (act
= delta
; act
; act
= act
->next_change
)
5498 gcc_assert (iv_ca_cand_for_use (ivs
, act
->use
) == from
);
5499 iv_ca_set_cp (data
, ivs
, act
->use
, to
);
5503 iv_ca_delta_reverse (delta
);
5506 /* Returns true if CAND is used in IVS. */
5509 iv_ca_cand_used_p (struct iv_ca
*ivs
, struct iv_cand
*cand
)
5511 return ivs
->n_cand_uses
[cand
->id
] > 0;
5514 /* Returns number of induction variable candidates in the set IVS. */
5517 iv_ca_n_cands (struct iv_ca
*ivs
)
5519 return ivs
->n_cands
;
5522 /* Free the list of changes DELTA. */
5525 iv_ca_delta_free (struct iv_ca_delta
**delta
)
5527 struct iv_ca_delta
*act
, *next
;
5529 for (act
= *delta
; act
; act
= next
)
5531 next
= act
->next_change
;
5538 /* Allocates new iv candidates assignment. */
5540 static struct iv_ca
*
5541 iv_ca_new (struct ivopts_data
*data
)
5543 struct iv_ca
*nw
= XNEW (struct iv_ca
);
5547 nw
->cand_for_use
= XCNEWVEC (struct cost_pair
*, n_iv_uses (data
));
5548 nw
->n_cand_uses
= XCNEWVEC (unsigned, n_iv_cands (data
));
5549 nw
->cands
= BITMAP_ALLOC (NULL
);
5552 nw
->cand_use_cost
= zero_cost
;
5554 nw
->n_invariant_uses
= XCNEWVEC (unsigned, data
->max_inv_id
+ 1);
5555 nw
->cost
= zero_cost
;
5556 nw
->used_inv_expr
= XCNEWVEC (unsigned, data
->inv_expr_id
+ 1);
5557 nw
->num_used_inv_expr
= 0;
5562 /* Free memory occupied by the set IVS. */
5565 iv_ca_free (struct iv_ca
**ivs
)
5567 free ((*ivs
)->cand_for_use
);
5568 free ((*ivs
)->n_cand_uses
);
5569 BITMAP_FREE ((*ivs
)->cands
);
5570 free ((*ivs
)->n_invariant_uses
);
5571 free ((*ivs
)->used_inv_expr
);
5576 /* Dumps IVS to FILE. */
5579 iv_ca_dump (struct ivopts_data
*data
, FILE *file
, struct iv_ca
*ivs
)
5581 const char *pref
= " invariants ";
5583 comp_cost cost
= iv_ca_cost (ivs
);
5585 fprintf (file
, " cost: %d (complexity %d)\n", cost
.cost
, cost
.complexity
);
5586 fprintf (file
, " cand_cost: %d\n cand_use_cost: %d (complexity %d)\n",
5587 ivs
->cand_cost
, ivs
->cand_use_cost
.cost
, ivs
->cand_use_cost
.complexity
);
5588 bitmap_print (file
, ivs
->cands
, " candidates: ","\n");
5590 for (i
= 0; i
< ivs
->upto
; i
++)
5592 struct iv_use
*use
= iv_use (data
, i
);
5593 struct cost_pair
*cp
= iv_ca_cand_for_use (ivs
, use
);
5595 fprintf (file
, " use:%d --> iv_cand:%d, cost=(%d,%d)\n",
5596 use
->id
, cp
->cand
->id
, cp
->cost
.cost
, cp
->cost
.complexity
);
5598 fprintf (file
, " use:%d --> ??\n", use
->id
);
5601 for (i
= 1; i
<= data
->max_inv_id
; i
++)
5602 if (ivs
->n_invariant_uses
[i
])
5604 fprintf (file
, "%s%d", pref
, i
);
5607 fprintf (file
, "\n\n");
5610 /* Try changing candidate in IVS to CAND for each use. Return cost of the
5611 new set, and store differences in DELTA. Number of induction variables
5612 in the new set is stored to N_IVS. MIN_NCAND is a flag. When it is true
5613 the function will try to find a solution with mimimal iv candidates. */
5616 iv_ca_extend (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5617 struct iv_cand
*cand
, struct iv_ca_delta
**delta
,
5618 unsigned *n_ivs
, bool min_ncand
)
5623 struct cost_pair
*old_cp
, *new_cp
;
5626 for (i
= 0; i
< ivs
->upto
; i
++)
5628 use
= iv_use (data
, i
);
5629 old_cp
= iv_ca_cand_for_use (ivs
, use
);
5632 && old_cp
->cand
== cand
)
5635 new_cp
= get_use_iv_cost (data
, use
, cand
);
5639 if (!min_ncand
&& !iv_ca_has_deps (ivs
, new_cp
))
5642 if (!min_ncand
&& !cheaper_cost_pair (new_cp
, old_cp
))
5645 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
5648 iv_ca_delta_commit (data
, ivs
, *delta
, true);
5649 cost
= iv_ca_cost (ivs
);
5651 *n_ivs
= iv_ca_n_cands (ivs
);
5652 iv_ca_delta_commit (data
, ivs
, *delta
, false);
5657 /* Try narrowing set IVS by removing CAND. Return the cost of
5658 the new set and store the differences in DELTA. */
5661 iv_ca_narrow (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5662 struct iv_cand
*cand
, struct iv_ca_delta
**delta
)
5666 struct cost_pair
*old_cp
, *new_cp
, *cp
;
5668 struct iv_cand
*cnd
;
5672 for (i
= 0; i
< n_iv_uses (data
); i
++)
5674 use
= iv_use (data
, i
);
5676 old_cp
= iv_ca_cand_for_use (ivs
, use
);
5677 if (old_cp
->cand
!= cand
)
5682 if (data
->consider_all_candidates
)
5684 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, ci
, bi
)
5689 cnd
= iv_cand (data
, ci
);
5691 cp
= get_use_iv_cost (data
, use
, cnd
);
5695 if (!iv_ca_has_deps (ivs
, cp
))
5698 if (!cheaper_cost_pair (cp
, new_cp
))
5706 EXECUTE_IF_AND_IN_BITMAP (use
->related_cands
, ivs
->cands
, 0, ci
, bi
)
5711 cnd
= iv_cand (data
, ci
);
5713 cp
= get_use_iv_cost (data
, use
, cnd
);
5716 if (!iv_ca_has_deps (ivs
, cp
))
5719 if (!cheaper_cost_pair (cp
, new_cp
))
5728 iv_ca_delta_free (delta
);
5729 return infinite_cost
;
5732 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
5735 iv_ca_delta_commit (data
, ivs
, *delta
, true);
5736 cost
= iv_ca_cost (ivs
);
5737 iv_ca_delta_commit (data
, ivs
, *delta
, false);
5742 /* Try optimizing the set of candidates IVS by removing candidates different
5743 from to EXCEPT_CAND from it. Return cost of the new set, and store
5744 differences in DELTA. */
5747 iv_ca_prune (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5748 struct iv_cand
*except_cand
, struct iv_ca_delta
**delta
)
5751 struct iv_ca_delta
*act_delta
, *best_delta
;
5753 comp_cost best_cost
, acost
;
5754 struct iv_cand
*cand
;
5757 best_cost
= iv_ca_cost (ivs
);
5759 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
5761 cand
= iv_cand (data
, i
);
5763 if (cand
== except_cand
)
5766 acost
= iv_ca_narrow (data
, ivs
, cand
, &act_delta
);
5768 if (compare_costs (acost
, best_cost
) < 0)
5771 iv_ca_delta_free (&best_delta
);
5772 best_delta
= act_delta
;
5775 iv_ca_delta_free (&act_delta
);
5784 /* Recurse to possibly remove other unnecessary ivs. */
5785 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
5786 best_cost
= iv_ca_prune (data
, ivs
, except_cand
, delta
);
5787 iv_ca_delta_commit (data
, ivs
, best_delta
, false);
5788 *delta
= iv_ca_delta_join (best_delta
, *delta
);
5792 /* Tries to extend the sets IVS in the best possible way in order
5793 to express the USE. If ORIGINALP is true, prefer candidates from
5794 the original set of IVs, otherwise favor important candidates not
5795 based on any memory object. */
5798 try_add_cand_for (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5799 struct iv_use
*use
, bool originalp
)
5801 comp_cost best_cost
, act_cost
;
5804 struct iv_cand
*cand
;
5805 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
;
5806 struct cost_pair
*cp
;
5808 iv_ca_add_use (data
, ivs
, use
, false);
5809 best_cost
= iv_ca_cost (ivs
);
5811 cp
= iv_ca_cand_for_use (ivs
, use
);
5816 iv_ca_add_use (data
, ivs
, use
, true);
5817 best_cost
= iv_ca_cost (ivs
);
5818 cp
= iv_ca_cand_for_use (ivs
, use
);
5822 best_delta
= iv_ca_delta_add (use
, NULL
, cp
, NULL
);
5823 iv_ca_set_no_cp (data
, ivs
, use
);
5826 /* If ORIGINALP is true, try to find the original IV for the use. Otherwise
5827 first try important candidates not based on any memory object. Only if
5828 this fails, try the specific ones. Rationale -- in loops with many
5829 variables the best choice often is to use just one generic biv. If we
5830 added here many ivs specific to the uses, the optimization algorithm later
5831 would be likely to get stuck in a local minimum, thus causing us to create
5832 too many ivs. The approach from few ivs to more seems more likely to be
5833 successful -- starting from few ivs, replacing an expensive use by a
5834 specific iv should always be a win. */
5835 EXECUTE_IF_SET_IN_BITMAP (data
->important_candidates
, 0, i
, bi
)
5837 cand
= iv_cand (data
, i
);
5839 if (originalp
&& cand
->pos
!=IP_ORIGINAL
)
5842 if (!originalp
&& cand
->iv
->base_object
!= NULL_TREE
)
5845 if (iv_ca_cand_used_p (ivs
, cand
))
5848 cp
= get_use_iv_cost (data
, use
, cand
);
5852 iv_ca_set_cp (data
, ivs
, use
, cp
);
5853 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
,
5855 iv_ca_set_no_cp (data
, ivs
, use
);
5856 act_delta
= iv_ca_delta_add (use
, NULL
, cp
, act_delta
);
5858 if (compare_costs (act_cost
, best_cost
) < 0)
5860 best_cost
= act_cost
;
5862 iv_ca_delta_free (&best_delta
);
5863 best_delta
= act_delta
;
5866 iv_ca_delta_free (&act_delta
);
5869 if (infinite_cost_p (best_cost
))
5871 for (i
= 0; i
< use
->n_map_members
; i
++)
5873 cp
= use
->cost_map
+ i
;
5878 /* Already tried this. */
5879 if (cand
->important
)
5881 if (originalp
&& cand
->pos
== IP_ORIGINAL
)
5883 if (!originalp
&& cand
->iv
->base_object
== NULL_TREE
)
5887 if (iv_ca_cand_used_p (ivs
, cand
))
5891 iv_ca_set_cp (data
, ivs
, use
, cp
);
5892 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
, true);
5893 iv_ca_set_no_cp (data
, ivs
, use
);
5894 act_delta
= iv_ca_delta_add (use
, iv_ca_cand_for_use (ivs
, use
),
5897 if (compare_costs (act_cost
, best_cost
) < 0)
5899 best_cost
= act_cost
;
5902 iv_ca_delta_free (&best_delta
);
5903 best_delta
= act_delta
;
5906 iv_ca_delta_free (&act_delta
);
5910 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
5911 iv_ca_delta_free (&best_delta
);
5913 return !infinite_cost_p (best_cost
);
5916 /* Finds an initial assignment of candidates to uses. */
5918 static struct iv_ca
*
5919 get_initial_solution (struct ivopts_data
*data
, bool originalp
)
5921 struct iv_ca
*ivs
= iv_ca_new (data
);
5924 for (i
= 0; i
< n_iv_uses (data
); i
++)
5925 if (!try_add_cand_for (data
, ivs
, iv_use (data
, i
), originalp
))
5934 /* Tries to improve set of induction variables IVS. */
5937 try_improve_iv_set (struct ivopts_data
*data
, struct iv_ca
*ivs
)
5940 comp_cost acost
, best_cost
= iv_ca_cost (ivs
);
5941 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
, *tmp_delta
;
5942 struct iv_cand
*cand
;
5944 /* Try extending the set of induction variables by one. */
5945 for (i
= 0; i
< n_iv_cands (data
); i
++)
5947 cand
= iv_cand (data
, i
);
5949 if (iv_ca_cand_used_p (ivs
, cand
))
5952 acost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, &n_ivs
, false);
5956 /* If we successfully added the candidate and the set is small enough,
5957 try optimizing it by removing other candidates. */
5958 if (n_ivs
<= ALWAYS_PRUNE_CAND_SET_BOUND
)
5960 iv_ca_delta_commit (data
, ivs
, act_delta
, true);
5961 acost
= iv_ca_prune (data
, ivs
, cand
, &tmp_delta
);
5962 iv_ca_delta_commit (data
, ivs
, act_delta
, false);
5963 act_delta
= iv_ca_delta_join (act_delta
, tmp_delta
);
5966 if (compare_costs (acost
, best_cost
) < 0)
5969 iv_ca_delta_free (&best_delta
);
5970 best_delta
= act_delta
;
5973 iv_ca_delta_free (&act_delta
);
5978 /* Try removing the candidates from the set instead. */
5979 best_cost
= iv_ca_prune (data
, ivs
, NULL
, &best_delta
);
5981 /* Nothing more we can do. */
5986 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
5987 gcc_assert (compare_costs (best_cost
, iv_ca_cost (ivs
)) == 0);
5988 iv_ca_delta_free (&best_delta
);
5992 /* Attempts to find the optimal set of induction variables. We do simple
5993 greedy heuristic -- we try to replace at most one candidate in the selected
5994 solution and remove the unused ivs while this improves the cost. */
5996 static struct iv_ca
*
5997 find_optimal_iv_set_1 (struct ivopts_data
*data
, bool originalp
)
6001 /* Get the initial solution. */
6002 set
= get_initial_solution (data
, originalp
);
6005 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6006 fprintf (dump_file
, "Unable to substitute for ivs, failed.\n");
6010 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6012 fprintf (dump_file
, "Initial set of candidates:\n");
6013 iv_ca_dump (data
, dump_file
, set
);
6016 while (try_improve_iv_set (data
, set
))
6018 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6020 fprintf (dump_file
, "Improved to:\n");
6021 iv_ca_dump (data
, dump_file
, set
);
6028 static struct iv_ca
*
6029 find_optimal_iv_set (struct ivopts_data
*data
)
6032 struct iv_ca
*set
, *origset
;
6034 comp_cost cost
, origcost
;
6036 /* Determine the cost based on a strategy that starts with original IVs,
6037 and try again using a strategy that prefers candidates not based
6039 origset
= find_optimal_iv_set_1 (data
, true);
6040 set
= find_optimal_iv_set_1 (data
, false);
6042 if (!origset
&& !set
)
6045 origcost
= origset
? iv_ca_cost (origset
) : infinite_cost
;
6046 cost
= set
? iv_ca_cost (set
) : infinite_cost
;
6048 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6050 fprintf (dump_file
, "Original cost %d (complexity %d)\n\n",
6051 origcost
.cost
, origcost
.complexity
);
6052 fprintf (dump_file
, "Final cost %d (complexity %d)\n\n",
6053 cost
.cost
, cost
.complexity
);
6056 /* Choose the one with the best cost. */
6057 if (compare_costs (origcost
, cost
) <= 0)
6064 iv_ca_free (&origset
);
6066 for (i
= 0; i
< n_iv_uses (data
); i
++)
6068 use
= iv_use (data
, i
);
6069 use
->selected
= iv_ca_cand_for_use (set
, use
)->cand
;
6075 /* Creates a new induction variable corresponding to CAND. */
6078 create_new_iv (struct ivopts_data
*data
, struct iv_cand
*cand
)
6080 gimple_stmt_iterator incr_pos
;
6090 incr_pos
= gsi_last_bb (ip_normal_pos (data
->current_loop
));
6094 incr_pos
= gsi_last_bb (ip_end_pos (data
->current_loop
));
6102 incr_pos
= gsi_for_stmt (cand
->incremented_at
);
6106 /* Mark that the iv is preserved. */
6107 name_info (data
, cand
->var_before
)->preserve_biv
= true;
6108 name_info (data
, cand
->var_after
)->preserve_biv
= true;
6110 /* Rewrite the increment so that it uses var_before directly. */
6111 find_interesting_uses_op (data
, cand
->var_after
)->selected
= cand
;
6115 gimple_add_tmp_var (cand
->var_before
);
6116 add_referenced_var (cand
->var_before
);
6118 base
= unshare_expr (cand
->iv
->base
);
6120 create_iv (base
, unshare_expr (cand
->iv
->step
),
6121 cand
->var_before
, data
->current_loop
,
6122 &incr_pos
, after
, &cand
->var_before
, &cand
->var_after
);
6125 /* Creates new induction variables described in SET. */
6128 create_new_ivs (struct ivopts_data
*data
, struct iv_ca
*set
)
6131 struct iv_cand
*cand
;
6134 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
6136 cand
= iv_cand (data
, i
);
6137 create_new_iv (data
, cand
);
6140 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6142 fprintf (dump_file
, "\nSelected IV set: \n");
6143 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
6145 cand
= iv_cand (data
, i
);
6146 dump_cand (dump_file
, cand
);
6148 fprintf (dump_file
, "\n");
6152 /* Rewrites USE (definition of iv used in a nonlinear expression)
6153 using candidate CAND. */
6156 rewrite_use_nonlinear_expr (struct ivopts_data
*data
,
6157 struct iv_use
*use
, struct iv_cand
*cand
)
6162 gimple_stmt_iterator bsi
;
6164 /* An important special case -- if we are asked to express value of
6165 the original iv by itself, just exit; there is no need to
6166 introduce a new computation (that might also need casting the
6167 variable to unsigned and back). */
6168 if (cand
->pos
== IP_ORIGINAL
6169 && cand
->incremented_at
== use
->stmt
)
6171 tree step
, ctype
, utype
;
6172 enum tree_code incr_code
= PLUS_EXPR
, old_code
;
6174 gcc_assert (is_gimple_assign (use
->stmt
));
6175 gcc_assert (gimple_assign_lhs (use
->stmt
) == cand
->var_after
);
6177 step
= cand
->iv
->step
;
6178 ctype
= TREE_TYPE (step
);
6179 utype
= TREE_TYPE (cand
->var_after
);
6180 if (TREE_CODE (step
) == NEGATE_EXPR
)
6182 incr_code
= MINUS_EXPR
;
6183 step
= TREE_OPERAND (step
, 0);
6186 /* Check whether we may leave the computation unchanged.
6187 This is the case only if it does not rely on other
6188 computations in the loop -- otherwise, the computation
6189 we rely upon may be removed in remove_unused_ivs,
6190 thus leading to ICE. */
6191 old_code
= gimple_assign_rhs_code (use
->stmt
);
6192 if (old_code
== PLUS_EXPR
6193 || old_code
== MINUS_EXPR
6194 || old_code
== POINTER_PLUS_EXPR
)
6196 if (gimple_assign_rhs1 (use
->stmt
) == cand
->var_before
)
6197 op
= gimple_assign_rhs2 (use
->stmt
);
6198 else if (old_code
!= MINUS_EXPR
6199 && gimple_assign_rhs2 (use
->stmt
) == cand
->var_before
)
6200 op
= gimple_assign_rhs1 (use
->stmt
);
6208 && (TREE_CODE (op
) == INTEGER_CST
6209 || operand_equal_p (op
, step
, 0)))
6212 /* Otherwise, add the necessary computations to express
6214 op
= fold_convert (ctype
, cand
->var_before
);
6215 comp
= fold_convert (utype
,
6216 build2 (incr_code
, ctype
, op
,
6217 unshare_expr (step
)));
6221 comp
= get_computation (data
->current_loop
, use
, cand
);
6222 gcc_assert (comp
!= NULL_TREE
);
6225 switch (gimple_code (use
->stmt
))
6228 tgt
= PHI_RESULT (use
->stmt
);
6230 /* If we should keep the biv, do not replace it. */
6231 if (name_info (data
, tgt
)->preserve_biv
)
6234 bsi
= gsi_after_labels (gimple_bb (use
->stmt
));
6238 tgt
= gimple_assign_lhs (use
->stmt
);
6239 bsi
= gsi_for_stmt (use
->stmt
);
6246 if (!valid_gimple_rhs_p (comp
)
6247 || (gimple_code (use
->stmt
) != GIMPLE_PHI
6248 /* We can't allow re-allocating the stmt as it might be pointed
6250 && (get_gimple_rhs_num_ops (TREE_CODE (comp
))
6251 >= gimple_num_ops (gsi_stmt (bsi
)))))
6253 comp
= force_gimple_operand_gsi (&bsi
, comp
, true, NULL_TREE
,
6254 true, GSI_SAME_STMT
);
6255 if (POINTER_TYPE_P (TREE_TYPE (tgt
)))
6257 duplicate_ssa_name_ptr_info (comp
, SSA_NAME_PTR_INFO (tgt
));
6258 /* As this isn't a plain copy we have to reset alignment
6260 if (SSA_NAME_PTR_INFO (comp
))
6262 SSA_NAME_PTR_INFO (comp
)->align
= 1;
6263 SSA_NAME_PTR_INFO (comp
)->misalign
= 0;
6268 if (gimple_code (use
->stmt
) == GIMPLE_PHI
)
6270 ass
= gimple_build_assign (tgt
, comp
);
6271 gsi_insert_before (&bsi
, ass
, GSI_SAME_STMT
);
6273 bsi
= gsi_for_stmt (use
->stmt
);
6274 remove_phi_node (&bsi
, false);
6278 gimple_assign_set_rhs_from_tree (&bsi
, comp
);
6279 use
->stmt
= gsi_stmt (bsi
);
6283 /* Performs a peephole optimization to reorder the iv update statement with
6284 a mem ref to enable instruction combining in later phases. The mem ref uses
6285 the iv value before the update, so the reordering transformation requires
6286 adjustment of the offset. CAND is the selected IV_CAND.
6290 t = MEM_REF (base, iv1, 8, 16); // base, index, stride, offset
6298 directly propagating t over to (1) will introduce overlapping live range
6299 thus increase register pressure. This peephole transform it into:
6303 t = MEM_REF (base, iv2, 8, 8);
6310 adjust_iv_update_pos (struct iv_cand
*cand
, struct iv_use
*use
)
6313 gimple iv_update
, stmt
;
6315 gimple_stmt_iterator gsi
, gsi_iv
;
6317 if (cand
->pos
!= IP_NORMAL
)
6320 var_after
= cand
->var_after
;
6321 iv_update
= SSA_NAME_DEF_STMT (var_after
);
6323 bb
= gimple_bb (iv_update
);
6324 gsi
= gsi_last_nondebug_bb (bb
);
6325 stmt
= gsi_stmt (gsi
);
6327 /* Only handle conditional statement for now. */
6328 if (gimple_code (stmt
) != GIMPLE_COND
)
6331 gsi_prev_nondebug (&gsi
);
6332 stmt
= gsi_stmt (gsi
);
6333 if (stmt
!= iv_update
)
6336 gsi_prev_nondebug (&gsi
);
6337 if (gsi_end_p (gsi
))
6340 stmt
= gsi_stmt (gsi
);
6341 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
6344 if (stmt
!= use
->stmt
)
6347 if (TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
6350 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6352 fprintf (dump_file
, "Reordering \n");
6353 print_gimple_stmt (dump_file
, iv_update
, 0, 0);
6354 print_gimple_stmt (dump_file
, use
->stmt
, 0, 0);
6355 fprintf (dump_file
, "\n");
6358 gsi
= gsi_for_stmt (use
->stmt
);
6359 gsi_iv
= gsi_for_stmt (iv_update
);
6360 gsi_move_before (&gsi_iv
, &gsi
);
6362 cand
->pos
= IP_BEFORE_USE
;
6363 cand
->incremented_at
= use
->stmt
;
6366 /* Rewrites USE (address that is an iv) using candidate CAND. */
6369 rewrite_use_address (struct ivopts_data
*data
,
6370 struct iv_use
*use
, struct iv_cand
*cand
)
6373 gimple_stmt_iterator bsi
= gsi_for_stmt (use
->stmt
);
6374 tree base_hint
= NULL_TREE
;
6378 adjust_iv_update_pos (cand
, use
);
6379 ok
= get_computation_aff (data
->current_loop
, use
, cand
, use
->stmt
, &aff
);
6381 unshare_aff_combination (&aff
);
6383 /* To avoid undefined overflow problems, all IV candidates use unsigned
6384 integer types. The drawback is that this makes it impossible for
6385 create_mem_ref to distinguish an IV that is based on a memory object
6386 from one that represents simply an offset.
6388 To work around this problem, we pass a hint to create_mem_ref that
6389 indicates which variable (if any) in aff is an IV based on a memory
6390 object. Note that we only consider the candidate. If this is not
6391 based on an object, the base of the reference is in some subexpression
6392 of the use -- but these will use pointer types, so they are recognized
6393 by the create_mem_ref heuristics anyway. */
6394 if (cand
->iv
->base_object
)
6395 base_hint
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
6397 iv
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
6398 ref
= create_mem_ref (&bsi
, TREE_TYPE (*use
->op_p
), &aff
,
6399 reference_alias_ptr_type (*use
->op_p
),
6400 iv
, base_hint
, data
->speed
);
6401 copy_ref_info (ref
, *use
->op_p
);
6405 /* Rewrites USE (the condition such that one of the arguments is an iv) using
6409 rewrite_use_compare (struct ivopts_data
*data
,
6410 struct iv_use
*use
, struct iv_cand
*cand
)
6412 tree comp
, *var_p
, op
, bound
;
6413 gimple_stmt_iterator bsi
= gsi_for_stmt (use
->stmt
);
6414 enum tree_code compare
;
6415 struct cost_pair
*cp
= get_use_iv_cost (data
, use
, cand
);
6421 tree var
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
6422 tree var_type
= TREE_TYPE (var
);
6425 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6427 fprintf (dump_file
, "Replacing exit test: ");
6428 print_gimple_stmt (dump_file
, use
->stmt
, 0, TDF_SLIM
);
6431 bound
= unshare_expr (fold_convert (var_type
, bound
));
6432 op
= force_gimple_operand (bound
, &stmts
, true, NULL_TREE
);
6434 gsi_insert_seq_on_edge_immediate (
6435 loop_preheader_edge (data
->current_loop
),
6438 gimple_cond_set_lhs (use
->stmt
, var
);
6439 gimple_cond_set_code (use
->stmt
, compare
);
6440 gimple_cond_set_rhs (use
->stmt
, op
);
6444 /* The induction variable elimination failed; just express the original
6446 comp
= get_computation (data
->current_loop
, use
, cand
);
6447 gcc_assert (comp
!= NULL_TREE
);
6449 ok
= extract_cond_operands (data
, use
->stmt
, &var_p
, NULL
, NULL
, NULL
);
6452 *var_p
= force_gimple_operand_gsi (&bsi
, comp
, true, SSA_NAME_VAR (*var_p
),
6453 true, GSI_SAME_STMT
);
6456 /* Rewrites USE using candidate CAND. */
6459 rewrite_use (struct ivopts_data
*data
, struct iv_use
*use
, struct iv_cand
*cand
)
6463 case USE_NONLINEAR_EXPR
:
6464 rewrite_use_nonlinear_expr (data
, use
, cand
);
6468 rewrite_use_address (data
, use
, cand
);
6472 rewrite_use_compare (data
, use
, cand
);
6479 update_stmt (use
->stmt
);
6482 /* Rewrite the uses using the selected induction variables. */
6485 rewrite_uses (struct ivopts_data
*data
)
6488 struct iv_cand
*cand
;
6491 for (i
= 0; i
< n_iv_uses (data
); i
++)
6493 use
= iv_use (data
, i
);
6494 cand
= use
->selected
;
6497 rewrite_use (data
, use
, cand
);
6501 /* Removes the ivs that are not used after rewriting. */
6504 remove_unused_ivs (struct ivopts_data
*data
)
6508 bitmap toremove
= BITMAP_ALLOC (NULL
);
6510 /* Figure out an order in which to release SSA DEFs so that we don't
6511 release something that we'd have to propagate into a debug stmt
6513 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
6515 struct version_info
*info
;
6517 info
= ver_info (data
, j
);
6519 && !integer_zerop (info
->iv
->step
)
6521 && !info
->iv
->have_use_for
6522 && !info
->preserve_biv
)
6523 bitmap_set_bit (toremove
, SSA_NAME_VERSION (info
->iv
->ssa_name
));
6526 release_defs_bitset (toremove
);
6528 BITMAP_FREE (toremove
);
6531 /* Frees memory occupied by struct tree_niter_desc in *VALUE. Callback
6532 for pointer_map_traverse. */
6535 free_tree_niter_desc (const void *key ATTRIBUTE_UNUSED
, void **value
,
6536 void *data ATTRIBUTE_UNUSED
)
6538 struct tree_niter_desc
*const niter
= (struct tree_niter_desc
*) *value
;
6544 /* Frees data allocated by the optimization of a single loop. */
6547 free_loop_data (struct ivopts_data
*data
)
6555 pointer_map_traverse (data
->niters
, free_tree_niter_desc
, NULL
);
6556 pointer_map_destroy (data
->niters
);
6557 data
->niters
= NULL
;
6560 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
6562 struct version_info
*info
;
6564 info
= ver_info (data
, i
);
6567 info
->has_nonlin_use
= false;
6568 info
->preserve_biv
= false;
6571 bitmap_clear (data
->relevant
);
6572 bitmap_clear (data
->important_candidates
);
6574 for (i
= 0; i
< n_iv_uses (data
); i
++)
6576 struct iv_use
*use
= iv_use (data
, i
);
6579 BITMAP_FREE (use
->related_cands
);
6580 for (j
= 0; j
< use
->n_map_members
; j
++)
6581 if (use
->cost_map
[j
].depends_on
)
6582 BITMAP_FREE (use
->cost_map
[j
].depends_on
);
6583 free (use
->cost_map
);
6586 VEC_truncate (iv_use_p
, data
->iv_uses
, 0);
6588 for (i
= 0; i
< n_iv_cands (data
); i
++)
6590 struct iv_cand
*cand
= iv_cand (data
, i
);
6593 if (cand
->depends_on
)
6594 BITMAP_FREE (cand
->depends_on
);
6597 VEC_truncate (iv_cand_p
, data
->iv_candidates
, 0);
6599 if (data
->version_info_size
< num_ssa_names
)
6601 data
->version_info_size
= 2 * num_ssa_names
;
6602 free (data
->version_info
);
6603 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
6606 data
->max_inv_id
= 0;
6608 FOR_EACH_VEC_ELT (tree
, decl_rtl_to_reset
, i
, obj
)
6609 SET_DECL_RTL (obj
, NULL_RTX
);
6611 VEC_truncate (tree
, decl_rtl_to_reset
, 0);
6613 htab_empty (data
->inv_expr_tab
);
6614 data
->inv_expr_id
= 0;
6617 /* Finalizes data structures used by the iv optimization pass. LOOPS is the
6621 tree_ssa_iv_optimize_finalize (struct ivopts_data
*data
)
6623 free_loop_data (data
);
6624 free (data
->version_info
);
6625 BITMAP_FREE (data
->relevant
);
6626 BITMAP_FREE (data
->important_candidates
);
6628 VEC_free (tree
, heap
, decl_rtl_to_reset
);
6629 VEC_free (iv_use_p
, heap
, data
->iv_uses
);
6630 VEC_free (iv_cand_p
, heap
, data
->iv_candidates
);
6631 htab_delete (data
->inv_expr_tab
);
6634 /* Returns true if the loop body BODY includes any function calls. */
6637 loop_body_includes_call (basic_block
*body
, unsigned num_nodes
)
6639 gimple_stmt_iterator gsi
;
6642 for (i
= 0; i
< num_nodes
; i
++)
6643 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
6645 gimple stmt
= gsi_stmt (gsi
);
6646 if (is_gimple_call (stmt
)
6647 && !is_inexpensive_builtin (gimple_call_fndecl (stmt
)))
6653 /* Optimizes the LOOP. Returns true if anything changed. */
6656 tree_ssa_iv_optimize_loop (struct ivopts_data
*data
, struct loop
*loop
)
6658 bool changed
= false;
6659 struct iv_ca
*iv_ca
;
6660 edge exit
= single_dom_exit (loop
);
6663 gcc_assert (!data
->niters
);
6664 data
->current_loop
= loop
;
6665 data
->speed
= optimize_loop_for_speed_p (loop
);
6667 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6669 fprintf (dump_file
, "Processing loop %d\n", loop
->num
);
6673 fprintf (dump_file
, " single exit %d -> %d, exit condition ",
6674 exit
->src
->index
, exit
->dest
->index
);
6675 print_gimple_stmt (dump_file
, last_stmt (exit
->src
), 0, TDF_SLIM
);
6676 fprintf (dump_file
, "\n");
6679 fprintf (dump_file
, "\n");
6682 body
= get_loop_body (loop
);
6683 data
->body_includes_call
= loop_body_includes_call (body
, loop
->num_nodes
);
6684 renumber_gimple_stmt_uids_in_blocks (body
, loop
->num_nodes
);
6687 data
->loop_single_exit_p
= exit
!= NULL
&& loop_only_exit_p (loop
, exit
);
6689 /* For each ssa name determines whether it behaves as an induction variable
6691 if (!find_induction_variables (data
))
6694 /* Finds interesting uses (item 1). */
6695 find_interesting_uses (data
);
6696 if (n_iv_uses (data
) > MAX_CONSIDERED_USES
)
6699 /* Finds candidates for the induction variables (item 2). */
6700 find_iv_candidates (data
);
6702 /* Calculates the costs (item 3, part 1). */
6703 determine_iv_costs (data
);
6704 determine_use_iv_costs (data
);
6705 determine_set_costs (data
);
6707 /* Find the optimal set of induction variables (item 3, part 2). */
6708 iv_ca
= find_optimal_iv_set (data
);
6713 /* Create the new induction variables (item 4, part 1). */
6714 create_new_ivs (data
, iv_ca
);
6715 iv_ca_free (&iv_ca
);
6717 /* Rewrite the uses (item 4, part 2). */
6718 rewrite_uses (data
);
6720 /* Remove the ivs that are unused after rewriting. */
6721 remove_unused_ivs (data
);
6723 /* We have changed the structure of induction variables; it might happen
6724 that definitions in the scev database refer to some of them that were
6729 free_loop_data (data
);
6734 /* Main entry point. Optimizes induction variables in loops. */
6737 tree_ssa_iv_optimize (void)
6740 struct ivopts_data data
;
6743 tree_ssa_iv_optimize_init (&data
);
6745 /* Optimize the loops starting with the innermost ones. */
6746 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
6748 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6749 flow_loop_dump (loop
, dump_file
, NULL
, 1);
6751 tree_ssa_iv_optimize_loop (&data
, loop
);
6754 tree_ssa_iv_optimize_finalize (&data
);