1 /* Induction variable optimizations.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
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"
93 /* FIXME: Expressions are expanded to RTL in this pass to determine the
94 cost of different addressing modes. This should be moved to a TBD
95 interface between the GIMPLE and RTL worlds. */
98 /* The infinite cost. */
99 #define INFTY 10000000
101 /* The expected number of loop iterations. TODO -- use profiling instead of
103 #define AVG_LOOP_NITER(LOOP) 5
106 /* Representation of the induction variable. */
109 tree base
; /* Initial value of the iv. */
110 tree base_object
; /* A memory object to that the induction variable points. */
111 tree step
; /* Step of the iv (constant only). */
112 tree ssa_name
; /* The ssa name with the value. */
113 bool biv_p
; /* Is it a biv? */
114 bool have_use_for
; /* Do we already have a use for it? */
115 unsigned use_id
; /* The identifier in the use if it is the case. */
118 /* Per-ssa version information (induction variable descriptions, etc.). */
121 tree name
; /* The ssa name. */
122 struct iv
*iv
; /* Induction variable description. */
123 bool has_nonlin_use
; /* For a loop-level invariant, whether it is used in
124 an expression that is not an induction variable. */
125 bool preserve_biv
; /* For the original biv, whether to preserve it. */
126 unsigned inv_id
; /* Id of an invariant. */
132 USE_NONLINEAR_EXPR
, /* Use in a nonlinear expression. */
133 USE_ADDRESS
, /* Use in an address. */
134 USE_COMPARE
/* Use is a compare. */
137 /* Cost of a computation. */
140 int cost
; /* The runtime cost. */
141 unsigned complexity
; /* The estimate of the complexity of the code for
142 the computation (in no concrete units --
143 complexity field should be larger for more
144 complex expressions and addressing modes). */
147 static const comp_cost zero_cost
= {0, 0};
148 static const comp_cost infinite_cost
= {INFTY
, INFTY
};
150 /* The candidate - cost pair. */
153 struct iv_cand
*cand
; /* The candidate. */
154 comp_cost cost
; /* The cost. */
155 bitmap depends_on
; /* The list of invariants that have to be
157 tree value
; /* For final value elimination, the expression for
158 the final value of the iv. For iv elimination,
159 the new bound to compare with. */
165 unsigned id
; /* The id of the use. */
166 enum use_type type
; /* Type of the use. */
167 struct iv
*iv
; /* The induction variable it is based on. */
168 gimple stmt
; /* Statement in that it occurs. */
169 tree
*op_p
; /* The place where it occurs. */
170 bitmap related_cands
; /* The set of "related" iv candidates, plus the common
173 unsigned n_map_members
; /* Number of candidates in the cost_map list. */
174 struct cost_pair
*cost_map
;
175 /* The costs wrto the iv candidates. */
177 struct iv_cand
*selected
;
178 /* The selected candidate. */
181 /* The position where the iv is computed. */
184 IP_NORMAL
, /* At the end, just before the exit condition. */
185 IP_END
, /* At the end of the latch block. */
186 IP_BEFORE_USE
, /* Immediately before a specific use. */
187 IP_AFTER_USE
, /* Immediately after a specific use. */
188 IP_ORIGINAL
/* The original biv. */
191 /* The induction variable candidate. */
194 unsigned id
; /* The number of the candidate. */
195 bool important
; /* Whether this is an "important" candidate, i.e. such
196 that it should be considered by all uses. */
197 ENUM_BITFIELD(iv_position
) pos
: 8; /* Where it is computed. */
198 gimple incremented_at
;/* For original biv, the statement where it is
200 tree var_before
; /* The variable used for it before increment. */
201 tree var_after
; /* The variable used for it after increment. */
202 struct iv
*iv
; /* The value of the candidate. NULL for
203 "pseudocandidate" used to indicate the possibility
204 to replace the final value of an iv by direct
205 computation of the value. */
206 unsigned cost
; /* Cost of the candidate. */
207 unsigned cost_step
; /* Cost of the candidate's increment operation. */
208 struct iv_use
*ainc_use
; /* For IP_{BEFORE,AFTER}_USE candidates, the place
209 where it is incremented. */
210 bitmap depends_on
; /* The list of invariants that are used in step of the
214 /* The data used by the induction variable optimizations. */
216 typedef struct iv_use
*iv_use_p
;
218 DEF_VEC_ALLOC_P(iv_use_p
,heap
);
220 typedef struct iv_cand
*iv_cand_p
;
221 DEF_VEC_P(iv_cand_p
);
222 DEF_VEC_ALLOC_P(iv_cand_p
,heap
);
226 /* The currently optimized loop. */
227 struct loop
*current_loop
;
229 /* Numbers of iterations for all exits of the current loop. */
230 struct pointer_map_t
*niters
;
232 /* Number of registers used in it. */
235 /* The size of version_info array allocated. */
236 unsigned version_info_size
;
238 /* The array of information for the ssa names. */
239 struct version_info
*version_info
;
241 /* The bitmap of indices in version_info whose value was changed. */
244 /* The uses of induction variables. */
245 VEC(iv_use_p
,heap
) *iv_uses
;
247 /* The candidates. */
248 VEC(iv_cand_p
,heap
) *iv_candidates
;
250 /* A bitmap of important candidates. */
251 bitmap important_candidates
;
253 /* The maximum invariant id. */
256 /* Whether to consider just related and important candidates when replacing a
258 bool consider_all_candidates
;
260 /* Are we optimizing for speed? */
264 /* An assignment of iv candidates to uses. */
268 /* The number of uses covered by the assignment. */
271 /* Number of uses that cannot be expressed by the candidates in the set. */
274 /* Candidate assigned to a use, together with the related costs. */
275 struct cost_pair
**cand_for_use
;
277 /* Number of times each candidate is used. */
278 unsigned *n_cand_uses
;
280 /* The candidates used. */
283 /* The number of candidates in the set. */
286 /* Total number of registers needed. */
289 /* Total cost of expressing uses. */
290 comp_cost cand_use_cost
;
292 /* Total cost of candidates. */
295 /* Number of times each invariant is used. */
296 unsigned *n_invariant_uses
;
298 /* Total cost of the assignment. */
302 /* Difference of two iv candidate assignments. */
309 /* An old assignment (for rollback purposes). */
310 struct cost_pair
*old_cp
;
312 /* A new assignment. */
313 struct cost_pair
*new_cp
;
315 /* Next change in the list. */
316 struct iv_ca_delta
*next_change
;
319 /* Bound on number of candidates below that all candidates are considered. */
321 #define CONSIDER_ALL_CANDIDATES_BOUND \
322 ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
324 /* If there are more iv occurrences, we just give up (it is quite unlikely that
325 optimizing such a loop would help, and it would take ages). */
327 #define MAX_CONSIDERED_USES \
328 ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
330 /* If there are at most this number of ivs in the set, try removing unnecessary
331 ivs from the set always. */
333 #define ALWAYS_PRUNE_CAND_SET_BOUND \
334 ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
336 /* The list of trees for that the decl_rtl field must be reset is stored
339 static VEC(tree
,heap
) *decl_rtl_to_reset
;
341 /* Number of uses recorded in DATA. */
343 static inline unsigned
344 n_iv_uses (struct ivopts_data
*data
)
346 return VEC_length (iv_use_p
, data
->iv_uses
);
349 /* Ith use recorded in DATA. */
351 static inline struct iv_use
*
352 iv_use (struct ivopts_data
*data
, unsigned i
)
354 return VEC_index (iv_use_p
, data
->iv_uses
, i
);
357 /* Number of candidates recorded in DATA. */
359 static inline unsigned
360 n_iv_cands (struct ivopts_data
*data
)
362 return VEC_length (iv_cand_p
, data
->iv_candidates
);
365 /* Ith candidate recorded in DATA. */
367 static inline struct iv_cand
*
368 iv_cand (struct ivopts_data
*data
, unsigned i
)
370 return VEC_index (iv_cand_p
, data
->iv_candidates
, i
);
373 /* The single loop exit if it dominates the latch, NULL otherwise. */
376 single_dom_exit (struct loop
*loop
)
378 edge exit
= single_exit (loop
);
383 if (!just_once_each_iteration_p (loop
, exit
->src
))
389 /* Dumps information about the induction variable IV to FILE. */
391 extern void dump_iv (FILE *, struct iv
*);
393 dump_iv (FILE *file
, struct iv
*iv
)
397 fprintf (file
, "ssa name ");
398 print_generic_expr (file
, iv
->ssa_name
, TDF_SLIM
);
399 fprintf (file
, "\n");
402 fprintf (file
, " type ");
403 print_generic_expr (file
, TREE_TYPE (iv
->base
), TDF_SLIM
);
404 fprintf (file
, "\n");
408 fprintf (file
, " base ");
409 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
410 fprintf (file
, "\n");
412 fprintf (file
, " step ");
413 print_generic_expr (file
, iv
->step
, TDF_SLIM
);
414 fprintf (file
, "\n");
418 fprintf (file
, " invariant ");
419 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
420 fprintf (file
, "\n");
425 fprintf (file
, " base object ");
426 print_generic_expr (file
, iv
->base_object
, TDF_SLIM
);
427 fprintf (file
, "\n");
431 fprintf (file
, " is a biv\n");
434 /* Dumps information about the USE to FILE. */
436 extern void dump_use (FILE *, struct iv_use
*);
438 dump_use (FILE *file
, struct iv_use
*use
)
440 fprintf (file
, "use %d\n", use
->id
);
444 case USE_NONLINEAR_EXPR
:
445 fprintf (file
, " generic\n");
449 fprintf (file
, " address\n");
453 fprintf (file
, " compare\n");
460 fprintf (file
, " in statement ");
461 print_gimple_stmt (file
, use
->stmt
, 0, 0);
462 fprintf (file
, "\n");
464 fprintf (file
, " at position ");
466 print_generic_expr (file
, *use
->op_p
, TDF_SLIM
);
467 fprintf (file
, "\n");
469 dump_iv (file
, use
->iv
);
471 if (use
->related_cands
)
473 fprintf (file
, " related candidates ");
474 dump_bitmap (file
, use
->related_cands
);
478 /* Dumps information about the uses to FILE. */
480 extern void dump_uses (FILE *, struct ivopts_data
*);
482 dump_uses (FILE *file
, struct ivopts_data
*data
)
487 for (i
= 0; i
< n_iv_uses (data
); i
++)
489 use
= iv_use (data
, i
);
491 dump_use (file
, use
);
492 fprintf (file
, "\n");
496 /* Dumps information about induction variable candidate CAND to FILE. */
498 extern void dump_cand (FILE *, struct iv_cand
*);
500 dump_cand (FILE *file
, struct iv_cand
*cand
)
502 struct iv
*iv
= cand
->iv
;
504 fprintf (file
, "candidate %d%s\n",
505 cand
->id
, cand
->important
? " (important)" : "");
507 if (cand
->depends_on
)
509 fprintf (file
, " depends on ");
510 dump_bitmap (file
, cand
->depends_on
);
515 fprintf (file
, " final value replacement\n");
522 fprintf (file
, " incremented before exit test\n");
526 fprintf (file
, " incremented before use %d\n", cand
->ainc_use
->id
);
530 fprintf (file
, " incremented after use %d\n", cand
->ainc_use
->id
);
534 fprintf (file
, " incremented at end\n");
538 fprintf (file
, " original biv\n");
545 /* Returns the info for ssa version VER. */
547 static inline struct version_info
*
548 ver_info (struct ivopts_data
*data
, unsigned ver
)
550 return data
->version_info
+ ver
;
553 /* Returns the info for ssa name NAME. */
555 static inline struct version_info
*
556 name_info (struct ivopts_data
*data
, tree name
)
558 return ver_info (data
, SSA_NAME_VERSION (name
));
561 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
565 stmt_after_ip_normal_pos (struct loop
*loop
, gimple stmt
)
567 basic_block bb
= ip_normal_pos (loop
), sbb
= gimple_bb (stmt
);
571 if (sbb
== loop
->latch
)
577 return stmt
== last_stmt (bb
);
580 /* Returns true if STMT if after the place where the original induction
581 variable CAND is incremented. If TRUE_IF_EQUAL is set, we return true
582 if the positions are identical. */
585 stmt_after_inc_pos (struct iv_cand
*cand
, gimple stmt
, bool true_if_equal
)
587 basic_block cand_bb
= gimple_bb (cand
->incremented_at
);
588 basic_block stmt_bb
= gimple_bb (stmt
);
590 if (!dominated_by_p (CDI_DOMINATORS
, stmt_bb
, cand_bb
))
593 if (stmt_bb
!= cand_bb
)
597 && gimple_uid (stmt
) == gimple_uid (cand
->incremented_at
))
599 return gimple_uid (stmt
) > gimple_uid (cand
->incremented_at
);
602 /* Returns true if STMT if after the place where the induction variable
603 CAND is incremented in LOOP. */
606 stmt_after_increment (struct loop
*loop
, struct iv_cand
*cand
, gimple stmt
)
614 return stmt_after_ip_normal_pos (loop
, stmt
);
618 return stmt_after_inc_pos (cand
, stmt
, false);
621 return stmt_after_inc_pos (cand
, stmt
, true);
628 /* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
631 abnormal_ssa_name_p (tree exp
)
636 if (TREE_CODE (exp
) != SSA_NAME
)
639 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
) != 0;
642 /* Returns false if BASE or INDEX contains a ssa name that occurs in an
643 abnormal phi node. Callback for for_each_index. */
646 idx_contains_abnormal_ssa_name_p (tree base
, tree
*index
,
647 void *data ATTRIBUTE_UNUSED
)
649 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
651 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 2)))
653 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 3)))
657 return !abnormal_ssa_name_p (*index
);
660 /* Returns true if EXPR contains a ssa name that occurs in an
661 abnormal phi node. */
664 contains_abnormal_ssa_name_p (tree expr
)
667 enum tree_code_class codeclass
;
672 code
= TREE_CODE (expr
);
673 codeclass
= TREE_CODE_CLASS (code
);
675 if (code
== SSA_NAME
)
676 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr
) != 0;
678 if (code
== INTEGER_CST
679 || is_gimple_min_invariant (expr
))
682 if (code
== ADDR_EXPR
)
683 return !for_each_index (&TREE_OPERAND (expr
, 0),
684 idx_contains_abnormal_ssa_name_p
,
687 if (code
== COND_EXPR
)
688 return contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0))
689 || contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1))
690 || contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 2));
696 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1)))
701 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0)))
713 /* Returns tree describing number of iterations determined from
714 EXIT of DATA->current_loop, or NULL if something goes wrong. */
717 niter_for_exit (struct ivopts_data
*data
, edge exit
)
719 struct tree_niter_desc desc
;
725 data
->niters
= pointer_map_create ();
729 slot
= pointer_map_contains (data
->niters
, exit
);
733 /* Try to determine number of iterations. We must know it
734 unconditionally (i.e., without possibility of # of iterations
735 being zero). Also, we cannot safely work with ssa names that
736 appear in phi nodes on abnormal edges, so that we do not create
737 overlapping life ranges for them (PR 27283). */
738 if (number_of_iterations_exit (data
->current_loop
,
740 && integer_zerop (desc
.may_be_zero
)
741 && !contains_abnormal_ssa_name_p (desc
.niter
))
746 *pointer_map_insert (data
->niters
, exit
) = niter
;
749 niter
= (tree
) *slot
;
754 /* Returns tree describing number of iterations determined from
755 single dominating exit of DATA->current_loop, or NULL if something
759 niter_for_single_dom_exit (struct ivopts_data
*data
)
761 edge exit
= single_dom_exit (data
->current_loop
);
766 return niter_for_exit (data
, exit
);
769 /* Initializes data structures used by the iv optimization pass, stored
773 tree_ssa_iv_optimize_init (struct ivopts_data
*data
)
775 data
->version_info_size
= 2 * num_ssa_names
;
776 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
777 data
->relevant
= BITMAP_ALLOC (NULL
);
778 data
->important_candidates
= BITMAP_ALLOC (NULL
);
779 data
->max_inv_id
= 0;
781 data
->iv_uses
= VEC_alloc (iv_use_p
, heap
, 20);
782 data
->iv_candidates
= VEC_alloc (iv_cand_p
, heap
, 20);
783 decl_rtl_to_reset
= VEC_alloc (tree
, heap
, 20);
786 /* Returns a memory object to that EXPR points. In case we are able to
787 determine that it does not point to any such object, NULL is returned. */
790 determine_base_object (tree expr
)
792 enum tree_code code
= TREE_CODE (expr
);
795 /* If this is a pointer casted to any type, we need to determine
796 the base object for the pointer; so handle conversions before
797 throwing away non-pointer expressions. */
798 if (CONVERT_EXPR_P (expr
))
799 return determine_base_object (TREE_OPERAND (expr
, 0));
801 if (!POINTER_TYPE_P (TREE_TYPE (expr
)))
810 obj
= TREE_OPERAND (expr
, 0);
811 base
= get_base_address (obj
);
816 if (TREE_CODE (base
) == INDIRECT_REF
)
817 return determine_base_object (TREE_OPERAND (base
, 0));
819 return fold_convert (ptr_type_node
,
820 build_fold_addr_expr (base
));
822 case POINTER_PLUS_EXPR
:
823 return determine_base_object (TREE_OPERAND (expr
, 0));
827 /* Pointer addition is done solely using POINTER_PLUS_EXPR. */
831 return fold_convert (ptr_type_node
, expr
);
835 /* Allocates an induction variable with given initial value BASE and step STEP
839 alloc_iv (tree base
, tree step
)
841 struct iv
*iv
= XCNEW (struct iv
);
842 gcc_assert (step
!= NULL_TREE
);
845 iv
->base_object
= determine_base_object (base
);
848 iv
->have_use_for
= false;
850 iv
->ssa_name
= NULL_TREE
;
855 /* Sets STEP and BASE for induction variable IV. */
858 set_iv (struct ivopts_data
*data
, tree iv
, tree base
, tree step
)
860 struct version_info
*info
= name_info (data
, iv
);
862 gcc_assert (!info
->iv
);
864 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (iv
));
865 info
->iv
= alloc_iv (base
, step
);
866 info
->iv
->ssa_name
= iv
;
869 /* Finds induction variable declaration for VAR. */
872 get_iv (struct ivopts_data
*data
, tree var
)
875 tree type
= TREE_TYPE (var
);
877 if (!POINTER_TYPE_P (type
)
878 && !INTEGRAL_TYPE_P (type
))
881 if (!name_info (data
, var
)->iv
)
883 bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
886 || !flow_bb_inside_loop_p (data
->current_loop
, bb
))
887 set_iv (data
, var
, var
, build_int_cst (type
, 0));
890 return name_info (data
, var
)->iv
;
893 /* Determines the step of a biv defined in PHI. Returns NULL if PHI does
894 not define a simple affine biv with nonzero step. */
897 determine_biv_step (gimple phi
)
899 struct loop
*loop
= gimple_bb (phi
)->loop_father
;
900 tree name
= PHI_RESULT (phi
);
903 if (!is_gimple_reg (name
))
906 if (!simple_iv (loop
, loop
, name
, &iv
, true))
909 return integer_zerop (iv
.step
) ? NULL_TREE
: iv
.step
;
912 /* Finds basic ivs. */
915 find_bivs (struct ivopts_data
*data
)
918 tree step
, type
, base
;
920 struct loop
*loop
= data
->current_loop
;
921 gimple_stmt_iterator psi
;
923 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
925 phi
= gsi_stmt (psi
);
927 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
930 step
= determine_biv_step (phi
);
934 base
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
935 base
= expand_simple_operations (base
);
936 if (contains_abnormal_ssa_name_p (base
)
937 || contains_abnormal_ssa_name_p (step
))
940 type
= TREE_TYPE (PHI_RESULT (phi
));
941 base
= fold_convert (type
, base
);
944 if (POINTER_TYPE_P (type
))
945 step
= fold_convert (sizetype
, step
);
947 step
= fold_convert (type
, step
);
950 set_iv (data
, PHI_RESULT (phi
), base
, step
);
957 /* Marks basic ivs. */
960 mark_bivs (struct ivopts_data
*data
)
964 struct iv
*iv
, *incr_iv
;
965 struct loop
*loop
= data
->current_loop
;
967 gimple_stmt_iterator psi
;
969 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
971 phi
= gsi_stmt (psi
);
973 iv
= get_iv (data
, PHI_RESULT (phi
));
977 var
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
978 incr_iv
= get_iv (data
, var
);
982 /* If the increment is in the subloop, ignore it. */
983 incr_bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
984 if (incr_bb
->loop_father
!= data
->current_loop
985 || (incr_bb
->flags
& BB_IRREDUCIBLE_LOOP
))
989 incr_iv
->biv_p
= true;
993 /* Checks whether STMT defines a linear induction variable and stores its
997 find_givs_in_stmt_scev (struct ivopts_data
*data
, gimple stmt
, affine_iv
*iv
)
1000 struct loop
*loop
= data
->current_loop
;
1002 iv
->base
= NULL_TREE
;
1003 iv
->step
= NULL_TREE
;
1005 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1008 lhs
= gimple_assign_lhs (stmt
);
1009 if (TREE_CODE (lhs
) != SSA_NAME
)
1012 if (!simple_iv (loop
, loop_containing_stmt (stmt
), lhs
, iv
, true))
1014 iv
->base
= expand_simple_operations (iv
->base
);
1016 if (contains_abnormal_ssa_name_p (iv
->base
)
1017 || contains_abnormal_ssa_name_p (iv
->step
))
1023 /* Finds general ivs in statement STMT. */
1026 find_givs_in_stmt (struct ivopts_data
*data
, gimple stmt
)
1030 if (!find_givs_in_stmt_scev (data
, stmt
, &iv
))
1033 set_iv (data
, gimple_assign_lhs (stmt
), iv
.base
, iv
.step
);
1036 /* Finds general ivs in basic block BB. */
1039 find_givs_in_bb (struct ivopts_data
*data
, basic_block bb
)
1041 gimple_stmt_iterator bsi
;
1043 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1044 find_givs_in_stmt (data
, gsi_stmt (bsi
));
1047 /* Finds general ivs. */
1050 find_givs (struct ivopts_data
*data
)
1052 struct loop
*loop
= data
->current_loop
;
1053 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1056 for (i
= 0; i
< loop
->num_nodes
; i
++)
1057 find_givs_in_bb (data
, body
[i
]);
1061 /* For each ssa name defined in LOOP determines whether it is an induction
1062 variable and if so, its initial value and step. */
1065 find_induction_variables (struct ivopts_data
*data
)
1070 if (!find_bivs (data
))
1076 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1078 tree niter
= niter_for_single_dom_exit (data
);
1082 fprintf (dump_file
, " number of iterations ");
1083 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1084 fprintf (dump_file
, "\n\n");
1087 fprintf (dump_file
, "Induction variables:\n\n");
1089 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1091 if (ver_info (data
, i
)->iv
)
1092 dump_iv (dump_file
, ver_info (data
, i
)->iv
);
1099 /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV. */
1101 static struct iv_use
*
1102 record_use (struct ivopts_data
*data
, tree
*use_p
, struct iv
*iv
,
1103 gimple stmt
, enum use_type use_type
)
1105 struct iv_use
*use
= XCNEW (struct iv_use
);
1107 use
->id
= n_iv_uses (data
);
1108 use
->type
= use_type
;
1112 use
->related_cands
= BITMAP_ALLOC (NULL
);
1114 /* To avoid showing ssa name in the dumps, if it was not reset by the
1116 iv
->ssa_name
= NULL_TREE
;
1118 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1119 dump_use (dump_file
, use
);
1121 VEC_safe_push (iv_use_p
, heap
, data
->iv_uses
, use
);
1126 /* Checks whether OP is a loop-level invariant and if so, records it.
1127 NONLINEAR_USE is true if the invariant is used in a way we do not
1128 handle specially. */
1131 record_invariant (struct ivopts_data
*data
, tree op
, bool nonlinear_use
)
1134 struct version_info
*info
;
1136 if (TREE_CODE (op
) != SSA_NAME
1137 || !is_gimple_reg (op
))
1140 bb
= gimple_bb (SSA_NAME_DEF_STMT (op
));
1142 && flow_bb_inside_loop_p (data
->current_loop
, bb
))
1145 info
= name_info (data
, op
);
1147 info
->has_nonlin_use
|= nonlinear_use
;
1149 info
->inv_id
= ++data
->max_inv_id
;
1150 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (op
));
1153 /* Checks whether the use OP is interesting and if so, records it. */
1155 static struct iv_use
*
1156 find_interesting_uses_op (struct ivopts_data
*data
, tree op
)
1163 if (TREE_CODE (op
) != SSA_NAME
)
1166 iv
= get_iv (data
, op
);
1170 if (iv
->have_use_for
)
1172 use
= iv_use (data
, iv
->use_id
);
1174 gcc_assert (use
->type
== USE_NONLINEAR_EXPR
);
1178 if (integer_zerop (iv
->step
))
1180 record_invariant (data
, op
, true);
1183 iv
->have_use_for
= true;
1185 civ
= XNEW (struct iv
);
1188 stmt
= SSA_NAME_DEF_STMT (op
);
1189 gcc_assert (gimple_code (stmt
) == GIMPLE_PHI
1190 || is_gimple_assign (stmt
));
1192 use
= record_use (data
, NULL
, civ
, stmt
, USE_NONLINEAR_EXPR
);
1193 iv
->use_id
= use
->id
;
1198 /* Given a condition in statement STMT, checks whether it is a compare
1199 of an induction variable and an invariant. If this is the case,
1200 CONTROL_VAR is set to location of the iv, BOUND to the location of
1201 the invariant, IV_VAR and IV_BOUND are set to the corresponding
1202 induction variable descriptions, and true is returned. If this is not
1203 the case, CONTROL_VAR and BOUND are set to the arguments of the
1204 condition and false is returned. */
1207 extract_cond_operands (struct ivopts_data
*data
, gimple stmt
,
1208 tree
**control_var
, tree
**bound
,
1209 struct iv
**iv_var
, struct iv
**iv_bound
)
1211 /* The objects returned when COND has constant operands. */
1212 static struct iv const_iv
;
1214 tree
*op0
= &zero
, *op1
= &zero
, *tmp_op
;
1215 struct iv
*iv0
= &const_iv
, *iv1
= &const_iv
, *tmp_iv
;
1218 if (gimple_code (stmt
) == GIMPLE_COND
)
1220 op0
= gimple_cond_lhs_ptr (stmt
);
1221 op1
= gimple_cond_rhs_ptr (stmt
);
1225 op0
= gimple_assign_rhs1_ptr (stmt
);
1226 op1
= gimple_assign_rhs2_ptr (stmt
);
1229 zero
= integer_zero_node
;
1230 const_iv
.step
= integer_zero_node
;
1232 if (TREE_CODE (*op0
) == SSA_NAME
)
1233 iv0
= get_iv (data
, *op0
);
1234 if (TREE_CODE (*op1
) == SSA_NAME
)
1235 iv1
= get_iv (data
, *op1
);
1237 /* Exactly one of the compared values must be an iv, and the other one must
1242 if (integer_zerop (iv0
->step
))
1244 /* Control variable may be on the other side. */
1245 tmp_op
= op0
; op0
= op1
; op1
= tmp_op
;
1246 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
1248 ret
= !integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
);
1252 *control_var
= op0
;;
1263 /* Checks whether the condition in STMT is interesting and if so,
1267 find_interesting_uses_cond (struct ivopts_data
*data
, gimple stmt
)
1269 tree
*var_p
, *bound_p
;
1270 struct iv
*var_iv
, *civ
;
1272 if (!extract_cond_operands (data
, stmt
, &var_p
, &bound_p
, &var_iv
, NULL
))
1274 find_interesting_uses_op (data
, *var_p
);
1275 find_interesting_uses_op (data
, *bound_p
);
1279 civ
= XNEW (struct iv
);
1281 record_use (data
, NULL
, civ
, stmt
, USE_COMPARE
);
1284 /* Returns true if expression EXPR is obviously invariant in LOOP,
1285 i.e. if all its operands are defined outside of the LOOP. LOOP
1286 should not be the function body. */
1289 expr_invariant_in_loop_p (struct loop
*loop
, tree expr
)
1294 gcc_assert (loop_depth (loop
) > 0);
1296 if (is_gimple_min_invariant (expr
))
1299 if (TREE_CODE (expr
) == SSA_NAME
)
1301 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
1303 && flow_bb_inside_loop_p (loop
, def_bb
))
1312 len
= TREE_OPERAND_LENGTH (expr
);
1313 for (i
= 0; i
< len
; i
++)
1314 if (!expr_invariant_in_loop_p (loop
, TREE_OPERAND (expr
, i
)))
1320 /* Returns true if statement STMT is obviously invariant in LOOP,
1321 i.e. if all its operands on the RHS are defined outside of the LOOP.
1322 LOOP should not be the function body. */
1325 stmt_invariant_in_loop_p (struct loop
*loop
, gimple stmt
)
1330 gcc_assert (loop_depth (loop
) > 0);
1332 lhs
= gimple_get_lhs (stmt
);
1333 for (i
= 0; i
< gimple_num_ops (stmt
); i
++)
1335 tree op
= gimple_op (stmt
, i
);
1336 if (op
!= lhs
&& !expr_invariant_in_loop_p (loop
, op
))
1343 /* Cumulates the steps of indices into DATA and replaces their values with the
1344 initial ones. Returns false when the value of the index cannot be determined.
1345 Callback for for_each_index. */
1347 struct ifs_ivopts_data
1349 struct ivopts_data
*ivopts_data
;
1355 idx_find_step (tree base
, tree
*idx
, void *data
)
1357 struct ifs_ivopts_data
*dta
= (struct ifs_ivopts_data
*) data
;
1359 tree step
, iv_base
, iv_step
, lbound
, off
;
1360 struct loop
*loop
= dta
->ivopts_data
->current_loop
;
1362 if (TREE_CODE (base
) == MISALIGNED_INDIRECT_REF
1363 || TREE_CODE (base
) == ALIGN_INDIRECT_REF
)
1366 /* If base is a component ref, require that the offset of the reference
1368 if (TREE_CODE (base
) == COMPONENT_REF
)
1370 off
= component_ref_field_offset (base
);
1371 return expr_invariant_in_loop_p (loop
, off
);
1374 /* If base is array, first check whether we will be able to move the
1375 reference out of the loop (in order to take its address in strength
1376 reduction). In order for this to work we need both lower bound
1377 and step to be loop invariants. */
1378 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
1380 /* Moreover, for a range, the size needs to be invariant as well. */
1381 if (TREE_CODE (base
) == ARRAY_RANGE_REF
1382 && !expr_invariant_in_loop_p (loop
, TYPE_SIZE (TREE_TYPE (base
))))
1385 step
= array_ref_element_size (base
);
1386 lbound
= array_ref_low_bound (base
);
1388 if (!expr_invariant_in_loop_p (loop
, step
)
1389 || !expr_invariant_in_loop_p (loop
, lbound
))
1393 if (TREE_CODE (*idx
) != SSA_NAME
)
1396 iv
= get_iv (dta
->ivopts_data
, *idx
);
1400 /* XXX We produce for a base of *D42 with iv->base being &x[0]
1401 *&x[0], which is not folded and does not trigger the
1402 ARRAY_REF path below. */
1405 if (integer_zerop (iv
->step
))
1408 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
1410 step
= array_ref_element_size (base
);
1412 /* We only handle addresses whose step is an integer constant. */
1413 if (TREE_CODE (step
) != INTEGER_CST
)
1417 /* The step for pointer arithmetics already is 1 byte. */
1418 step
= build_int_cst (sizetype
, 1);
1422 if (!convert_affine_scev (dta
->ivopts_data
->current_loop
,
1423 sizetype
, &iv_base
, &iv_step
, dta
->stmt
,
1426 /* The index might wrap. */
1430 step
= fold_build2 (MULT_EXPR
, sizetype
, step
, iv_step
);
1431 dta
->step
= fold_build2 (PLUS_EXPR
, sizetype
, dta
->step
, step
);
1436 /* Records use in index IDX. Callback for for_each_index. Ivopts data
1437 object is passed to it in DATA. */
1440 idx_record_use (tree base
, tree
*idx
,
1443 struct ivopts_data
*data
= (struct ivopts_data
*) vdata
;
1444 find_interesting_uses_op (data
, *idx
);
1445 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
1447 find_interesting_uses_op (data
, array_ref_element_size (base
));
1448 find_interesting_uses_op (data
, array_ref_low_bound (base
));
1453 /* If we can prove that TOP = cst * BOT for some constant cst,
1454 store cst to MUL and return true. Otherwise return false.
1455 The returned value is always sign-extended, regardless of the
1456 signedness of TOP and BOT. */
1459 constant_multiple_of (tree top
, tree bot
, double_int
*mul
)
1462 enum tree_code code
;
1463 double_int res
, p0
, p1
;
1464 unsigned precision
= TYPE_PRECISION (TREE_TYPE (top
));
1469 if (operand_equal_p (top
, bot
, 0))
1471 *mul
= double_int_one
;
1475 code
= TREE_CODE (top
);
1479 mby
= TREE_OPERAND (top
, 1);
1480 if (TREE_CODE (mby
) != INTEGER_CST
)
1483 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &res
))
1486 *mul
= double_int_sext (double_int_mul (res
, tree_to_double_int (mby
)),
1492 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &p0
)
1493 || !constant_multiple_of (TREE_OPERAND (top
, 1), bot
, &p1
))
1496 if (code
== MINUS_EXPR
)
1497 p1
= double_int_neg (p1
);
1498 *mul
= double_int_sext (double_int_add (p0
, p1
), precision
);
1502 if (TREE_CODE (bot
) != INTEGER_CST
)
1505 p0
= double_int_sext (tree_to_double_int (top
), precision
);
1506 p1
= double_int_sext (tree_to_double_int (bot
), precision
);
1507 if (double_int_zero_p (p1
))
1509 *mul
= double_int_sext (double_int_sdivmod (p0
, p1
, FLOOR_DIV_EXPR
, &res
),
1511 return double_int_zero_p (res
);
1518 /* Returns true if memory reference REF with step STEP may be unaligned. */
1521 may_be_unaligned_p (tree ref
, tree step
)
1525 HOST_WIDE_INT bitsize
;
1526 HOST_WIDE_INT bitpos
;
1528 enum machine_mode mode
;
1529 int unsignedp
, volatilep
;
1530 unsigned base_align
;
1532 /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
1533 thus they are not misaligned. */
1534 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
1537 /* The test below is basically copy of what expr.c:normal_inner_ref
1538 does to check whether the object must be loaded by parts when
1539 STRICT_ALIGNMENT is true. */
1540 base
= get_inner_reference (ref
, &bitsize
, &bitpos
, &toffset
, &mode
,
1541 &unsignedp
, &volatilep
, true);
1542 base_type
= TREE_TYPE (base
);
1543 base_align
= TYPE_ALIGN (base_type
);
1545 if (mode
!= BLKmode
)
1547 unsigned mode_align
= GET_MODE_ALIGNMENT (mode
);
1549 if (base_align
< mode_align
1550 || (bitpos
% mode_align
) != 0
1551 || (bitpos
% BITS_PER_UNIT
) != 0)
1555 && (highest_pow2_factor (toffset
) * BITS_PER_UNIT
) < mode_align
)
1558 if ((highest_pow2_factor (step
) * BITS_PER_UNIT
) < mode_align
)
1565 /* Return true if EXPR may be non-addressable. */
1568 may_be_nonaddressable_p (tree expr
)
1570 switch (TREE_CODE (expr
))
1572 case TARGET_MEM_REF
:
1573 /* TARGET_MEM_REFs are translated directly to valid MEMs on the
1574 target, thus they are always addressable. */
1578 return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr
, 1))
1579 || may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1581 case VIEW_CONVERT_EXPR
:
1582 /* This kind of view-conversions may wrap non-addressable objects
1583 and make them look addressable. After some processing the
1584 non-addressability may be uncovered again, causing ADDR_EXPRs
1585 of inappropriate objects to be built. */
1586 if (is_gimple_reg (TREE_OPERAND (expr
, 0))
1587 || !is_gimple_addressable (TREE_OPERAND (expr
, 0)))
1590 /* ... fall through ... */
1593 case ARRAY_RANGE_REF
:
1594 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1606 /* Finds addresses in *OP_P inside STMT. */
1609 find_interesting_uses_address (struct ivopts_data
*data
, gimple stmt
, tree
*op_p
)
1611 tree base
= *op_p
, step
= build_int_cst (sizetype
, 0);
1613 struct ifs_ivopts_data ifs_ivopts_data
;
1615 /* Do not play with volatile memory references. A bit too conservative,
1616 perhaps, but safe. */
1617 if (gimple_has_volatile_ops (stmt
))
1620 /* Ignore bitfields for now. Not really something terribly complicated
1622 if (TREE_CODE (base
) == BIT_FIELD_REF
)
1625 base
= unshare_expr (base
);
1627 if (TREE_CODE (base
) == TARGET_MEM_REF
)
1629 tree type
= build_pointer_type (TREE_TYPE (base
));
1633 && TREE_CODE (TMR_BASE (base
)) == SSA_NAME
)
1635 civ
= get_iv (data
, TMR_BASE (base
));
1639 TMR_BASE (base
) = civ
->base
;
1642 if (TMR_INDEX (base
)
1643 && TREE_CODE (TMR_INDEX (base
)) == SSA_NAME
)
1645 civ
= get_iv (data
, TMR_INDEX (base
));
1649 TMR_INDEX (base
) = civ
->base
;
1654 if (TMR_STEP (base
))
1655 astep
= fold_build2 (MULT_EXPR
, type
, TMR_STEP (base
), astep
);
1657 step
= fold_build2 (PLUS_EXPR
, type
, step
, astep
);
1661 if (integer_zerop (step
))
1663 base
= tree_mem_ref_addr (type
, base
);
1667 ifs_ivopts_data
.ivopts_data
= data
;
1668 ifs_ivopts_data
.stmt
= stmt
;
1669 ifs_ivopts_data
.step
= build_int_cst (sizetype
, 0);
1670 if (!for_each_index (&base
, idx_find_step
, &ifs_ivopts_data
)
1671 || integer_zerop (ifs_ivopts_data
.step
))
1673 step
= ifs_ivopts_data
.step
;
1675 gcc_assert (TREE_CODE (base
) != ALIGN_INDIRECT_REF
);
1676 gcc_assert (TREE_CODE (base
) != MISALIGNED_INDIRECT_REF
);
1678 /* Check that the base expression is addressable. This needs
1679 to be done after substituting bases of IVs into it. */
1680 if (may_be_nonaddressable_p (base
))
1683 /* Moreover, on strict alignment platforms, check that it is
1684 sufficiently aligned. */
1685 if (STRICT_ALIGNMENT
&& may_be_unaligned_p (base
, step
))
1688 base
= build_fold_addr_expr (base
);
1690 /* Substituting bases of IVs into the base expression might
1691 have caused folding opportunities. */
1692 if (TREE_CODE (base
) == ADDR_EXPR
)
1694 tree
*ref
= &TREE_OPERAND (base
, 0);
1695 while (handled_component_p (*ref
))
1696 ref
= &TREE_OPERAND (*ref
, 0);
1697 if (TREE_CODE (*ref
) == INDIRECT_REF
)
1699 tree tem
= gimple_fold_indirect_ref (TREE_OPERAND (*ref
, 0));
1706 civ
= alloc_iv (base
, step
);
1707 record_use (data
, op_p
, civ
, stmt
, USE_ADDRESS
);
1711 for_each_index (op_p
, idx_record_use
, data
);
1714 /* Finds and records invariants used in STMT. */
1717 find_invariants_stmt (struct ivopts_data
*data
, gimple stmt
)
1720 use_operand_p use_p
;
1723 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1725 op
= USE_FROM_PTR (use_p
);
1726 record_invariant (data
, op
, false);
1730 /* Finds interesting uses of induction variables in the statement STMT. */
1733 find_interesting_uses_stmt (struct ivopts_data
*data
, gimple stmt
)
1736 tree op
, *lhs
, *rhs
;
1738 use_operand_p use_p
;
1739 enum tree_code code
;
1741 find_invariants_stmt (data
, stmt
);
1743 if (gimple_code (stmt
) == GIMPLE_COND
)
1745 find_interesting_uses_cond (data
, stmt
);
1749 if (is_gimple_assign (stmt
))
1751 lhs
= gimple_assign_lhs_ptr (stmt
);
1752 rhs
= gimple_assign_rhs1_ptr (stmt
);
1754 if (TREE_CODE (*lhs
) == SSA_NAME
)
1756 /* If the statement defines an induction variable, the uses are not
1757 interesting by themselves. */
1759 iv
= get_iv (data
, *lhs
);
1761 if (iv
&& !integer_zerop (iv
->step
))
1765 code
= gimple_assign_rhs_code (stmt
);
1766 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
1767 && (REFERENCE_CLASS_P (*rhs
)
1768 || is_gimple_val (*rhs
)))
1770 if (REFERENCE_CLASS_P (*rhs
))
1771 find_interesting_uses_address (data
, stmt
, rhs
);
1773 find_interesting_uses_op (data
, *rhs
);
1775 if (REFERENCE_CLASS_P (*lhs
))
1776 find_interesting_uses_address (data
, stmt
, lhs
);
1779 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
1781 find_interesting_uses_cond (data
, stmt
);
1785 /* TODO -- we should also handle address uses of type
1787 memory = call (whatever);
1794 if (gimple_code (stmt
) == GIMPLE_PHI
1795 && gimple_bb (stmt
) == data
->current_loop
->header
)
1797 iv
= get_iv (data
, PHI_RESULT (stmt
));
1799 if (iv
&& !integer_zerop (iv
->step
))
1803 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1805 op
= USE_FROM_PTR (use_p
);
1807 if (TREE_CODE (op
) != SSA_NAME
)
1810 iv
= get_iv (data
, op
);
1814 find_interesting_uses_op (data
, op
);
1818 /* Finds interesting uses of induction variables outside of loops
1819 on loop exit edge EXIT. */
1822 find_interesting_uses_outside (struct ivopts_data
*data
, edge exit
)
1825 gimple_stmt_iterator psi
;
1828 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
1830 phi
= gsi_stmt (psi
);
1831 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1832 if (is_gimple_reg (def
))
1833 find_interesting_uses_op (data
, def
);
1837 /* Finds uses of the induction variables that are interesting. */
1840 find_interesting_uses (struct ivopts_data
*data
)
1843 gimple_stmt_iterator bsi
;
1844 basic_block
*body
= get_loop_body (data
->current_loop
);
1846 struct version_info
*info
;
1849 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1850 fprintf (dump_file
, "Uses:\n\n");
1852 for (i
= 0; i
< data
->current_loop
->num_nodes
; i
++)
1857 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1858 if (e
->dest
!= EXIT_BLOCK_PTR
1859 && !flow_bb_inside_loop_p (data
->current_loop
, e
->dest
))
1860 find_interesting_uses_outside (data
, e
);
1862 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1863 find_interesting_uses_stmt (data
, gsi_stmt (bsi
));
1864 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1865 if (!is_gimple_debug (gsi_stmt (bsi
)))
1866 find_interesting_uses_stmt (data
, gsi_stmt (bsi
));
1869 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1873 fprintf (dump_file
, "\n");
1875 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1877 info
= ver_info (data
, i
);
1880 fprintf (dump_file
, " ");
1881 print_generic_expr (dump_file
, info
->name
, TDF_SLIM
);
1882 fprintf (dump_file
, " is invariant (%d)%s\n",
1883 info
->inv_id
, info
->has_nonlin_use
? "" : ", eliminable");
1887 fprintf (dump_file
, "\n");
1893 /* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
1894 is true, assume we are inside an address. If TOP_COMPREF is true, assume
1895 we are at the top-level of the processed address. */
1898 strip_offset_1 (tree expr
, bool inside_addr
, bool top_compref
,
1899 unsigned HOST_WIDE_INT
*offset
)
1901 tree op0
= NULL_TREE
, op1
= NULL_TREE
, tmp
, step
;
1902 enum tree_code code
;
1903 tree type
, orig_type
= TREE_TYPE (expr
);
1904 unsigned HOST_WIDE_INT off0
, off1
, st
;
1905 tree orig_expr
= expr
;
1909 type
= TREE_TYPE (expr
);
1910 code
= TREE_CODE (expr
);
1916 if (!cst_and_fits_in_hwi (expr
)
1917 || integer_zerop (expr
))
1920 *offset
= int_cst_value (expr
);
1921 return build_int_cst (orig_type
, 0);
1923 case POINTER_PLUS_EXPR
:
1926 op0
= TREE_OPERAND (expr
, 0);
1927 op1
= TREE_OPERAND (expr
, 1);
1929 op0
= strip_offset_1 (op0
, false, false, &off0
);
1930 op1
= strip_offset_1 (op1
, false, false, &off1
);
1932 *offset
= (code
== MINUS_EXPR
? off0
- off1
: off0
+ off1
);
1933 if (op0
== TREE_OPERAND (expr
, 0)
1934 && op1
== TREE_OPERAND (expr
, 1))
1937 if (integer_zerop (op1
))
1939 else if (integer_zerop (op0
))
1941 if (code
== MINUS_EXPR
)
1942 expr
= fold_build1 (NEGATE_EXPR
, type
, op1
);
1947 expr
= fold_build2 (code
, type
, op0
, op1
);
1949 return fold_convert (orig_type
, expr
);
1952 op1
= TREE_OPERAND (expr
, 1);
1953 if (!cst_and_fits_in_hwi (op1
))
1956 op0
= TREE_OPERAND (expr
, 0);
1957 op0
= strip_offset_1 (op0
, false, false, &off0
);
1958 if (op0
== TREE_OPERAND (expr
, 0))
1961 *offset
= off0
* int_cst_value (op1
);
1962 if (integer_zerop (op0
))
1965 expr
= fold_build2 (MULT_EXPR
, type
, op0
, op1
);
1967 return fold_convert (orig_type
, expr
);
1970 case ARRAY_RANGE_REF
:
1974 step
= array_ref_element_size (expr
);
1975 if (!cst_and_fits_in_hwi (step
))
1978 st
= int_cst_value (step
);
1979 op1
= TREE_OPERAND (expr
, 1);
1980 op1
= strip_offset_1 (op1
, false, false, &off1
);
1981 *offset
= off1
* st
;
1984 && integer_zerop (op1
))
1986 /* Strip the component reference completely. */
1987 op0
= TREE_OPERAND (expr
, 0);
1988 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
1998 tmp
= component_ref_field_offset (expr
);
2000 && cst_and_fits_in_hwi (tmp
))
2002 /* Strip the component reference completely. */
2003 op0
= TREE_OPERAND (expr
, 0);
2004 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
2005 *offset
= off0
+ int_cst_value (tmp
);
2011 op0
= TREE_OPERAND (expr
, 0);
2012 op0
= strip_offset_1 (op0
, true, true, &off0
);
2015 if (op0
== TREE_OPERAND (expr
, 0))
2018 expr
= build_fold_addr_expr (op0
);
2019 return fold_convert (orig_type
, expr
);
2022 inside_addr
= false;
2029 /* Default handling of expressions for that we want to recurse into
2030 the first operand. */
2031 op0
= TREE_OPERAND (expr
, 0);
2032 op0
= strip_offset_1 (op0
, inside_addr
, false, &off0
);
2035 if (op0
== TREE_OPERAND (expr
, 0)
2036 && (!op1
|| op1
== TREE_OPERAND (expr
, 1)))
2039 expr
= copy_node (expr
);
2040 TREE_OPERAND (expr
, 0) = op0
;
2042 TREE_OPERAND (expr
, 1) = op1
;
2044 /* Inside address, we might strip the top level component references,
2045 thus changing type of the expression. Handling of ADDR_EXPR
2047 expr
= fold_convert (orig_type
, expr
);
2052 /* Strips constant offsets from EXPR and stores them to OFFSET. */
2055 strip_offset (tree expr
, unsigned HOST_WIDE_INT
*offset
)
2057 return strip_offset_1 (expr
, false, false, offset
);
2060 /* Returns variant of TYPE that can be used as base for different uses.
2061 We return unsigned type with the same precision, which avoids problems
2065 generic_type_for (tree type
)
2067 if (POINTER_TYPE_P (type
))
2068 return unsigned_type_for (type
);
2070 if (TYPE_UNSIGNED (type
))
2073 return unsigned_type_for (type
);
2076 /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
2077 the bitmap to that we should store it. */
2079 static struct ivopts_data
*fd_ivopts_data
;
2081 find_depends (tree
*expr_p
, int *ws ATTRIBUTE_UNUSED
, void *data
)
2083 bitmap
*depends_on
= (bitmap
*) data
;
2084 struct version_info
*info
;
2086 if (TREE_CODE (*expr_p
) != SSA_NAME
)
2088 info
= name_info (fd_ivopts_data
, *expr_p
);
2090 if (!info
->inv_id
|| info
->has_nonlin_use
)
2094 *depends_on
= BITMAP_ALLOC (NULL
);
2095 bitmap_set_bit (*depends_on
, info
->inv_id
);
2100 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2101 position to POS. If USE is not NULL, the candidate is set as related to
2102 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
2103 replacement of the final value of the iv by a direct computation. */
2105 static struct iv_cand
*
2106 add_candidate_1 (struct ivopts_data
*data
,
2107 tree base
, tree step
, bool important
, enum iv_position pos
,
2108 struct iv_use
*use
, gimple incremented_at
)
2111 struct iv_cand
*cand
= NULL
;
2112 tree type
, orig_type
;
2116 orig_type
= TREE_TYPE (base
);
2117 type
= generic_type_for (orig_type
);
2118 if (type
!= orig_type
)
2120 base
= fold_convert (type
, base
);
2121 step
= fold_convert (type
, step
);
2125 for (i
= 0; i
< n_iv_cands (data
); i
++)
2127 cand
= iv_cand (data
, i
);
2129 if (cand
->pos
!= pos
)
2132 if (cand
->incremented_at
!= incremented_at
2133 || ((pos
== IP_AFTER_USE
|| pos
== IP_BEFORE_USE
)
2134 && cand
->ainc_use
!= use
))
2148 if (operand_equal_p (base
, cand
->iv
->base
, 0)
2149 && operand_equal_p (step
, cand
->iv
->step
, 0))
2153 if (i
== n_iv_cands (data
))
2155 cand
= XCNEW (struct iv_cand
);
2161 cand
->iv
= alloc_iv (base
, step
);
2164 if (pos
!= IP_ORIGINAL
&& cand
->iv
)
2166 cand
->var_before
= create_tmp_var_raw (TREE_TYPE (base
), "ivtmp");
2167 cand
->var_after
= cand
->var_before
;
2169 cand
->important
= important
;
2170 cand
->incremented_at
= incremented_at
;
2171 VEC_safe_push (iv_cand_p
, heap
, data
->iv_candidates
, cand
);
2174 && TREE_CODE (step
) != INTEGER_CST
)
2176 fd_ivopts_data
= data
;
2177 walk_tree (&step
, find_depends
, &cand
->depends_on
, NULL
);
2180 if (pos
== IP_AFTER_USE
|| pos
== IP_BEFORE_USE
)
2181 cand
->ainc_use
= use
;
2183 cand
->ainc_use
= NULL
;
2185 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2186 dump_cand (dump_file
, cand
);
2189 if (important
&& !cand
->important
)
2191 cand
->important
= true;
2192 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2193 fprintf (dump_file
, "Candidate %d is important\n", cand
->id
);
2198 bitmap_set_bit (use
->related_cands
, i
);
2199 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2200 fprintf (dump_file
, "Candidate %d is related to use %d\n",
2207 /* Returns true if incrementing the induction variable at the end of the LOOP
2210 The purpose is to avoid splitting latch edge with a biv increment, thus
2211 creating a jump, possibly confusing other optimization passes and leaving
2212 less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS
2213 is not available (so we do not have a better alternative), or if the latch
2214 edge is already nonempty. */
2217 allow_ip_end_pos_p (struct loop
*loop
)
2219 if (!ip_normal_pos (loop
))
2222 if (!empty_block_p (ip_end_pos (loop
)))
2228 /* If possible, adds autoincrement candidates BASE + STEP * i based on use USE.
2229 Important field is set to IMPORTANT. */
2232 add_autoinc_candidates (struct ivopts_data
*data
, tree base
, tree step
,
2233 bool important
, struct iv_use
*use
)
2235 basic_block use_bb
= gimple_bb (use
->stmt
);
2236 enum machine_mode mem_mode
;
2237 unsigned HOST_WIDE_INT cstepi
;
2239 /* If we insert the increment in any position other than the standard
2240 ones, we must ensure that it is incremented once per iteration.
2241 It must not be in an inner nested loop, or one side of an if
2243 if (use_bb
->loop_father
!= data
->current_loop
2244 || !dominated_by_p (CDI_DOMINATORS
, data
->current_loop
->latch
, use_bb
)
2245 || stmt_could_throw_p (use
->stmt
)
2246 || !cst_and_fits_in_hwi (step
))
2249 cstepi
= int_cst_value (step
);
2251 mem_mode
= TYPE_MODE (TREE_TYPE (*use
->op_p
));
2252 if ((HAVE_PRE_INCREMENT
&& GET_MODE_SIZE (mem_mode
) == cstepi
)
2253 || (HAVE_PRE_DECREMENT
&& GET_MODE_SIZE (mem_mode
) == -cstepi
))
2255 enum tree_code code
= MINUS_EXPR
;
2257 tree new_step
= step
;
2259 if (POINTER_TYPE_P (TREE_TYPE (base
)))
2261 new_step
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (step
), step
);
2262 code
= POINTER_PLUS_EXPR
;
2265 new_step
= fold_convert (TREE_TYPE (base
), new_step
);
2266 new_base
= fold_build2 (code
, TREE_TYPE (base
), base
, new_step
);
2267 add_candidate_1 (data
, new_base
, step
, important
, IP_BEFORE_USE
, use
,
2270 if ((HAVE_POST_INCREMENT
&& GET_MODE_SIZE (mem_mode
) == cstepi
)
2271 || (HAVE_POST_DECREMENT
&& GET_MODE_SIZE (mem_mode
) == -cstepi
))
2273 add_candidate_1 (data
, base
, step
, important
, IP_AFTER_USE
, use
,
2278 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2279 position to POS. If USE is not NULL, the candidate is set as related to
2280 it. The candidate computation is scheduled on all available positions. */
2283 add_candidate (struct ivopts_data
*data
,
2284 tree base
, tree step
, bool important
, struct iv_use
*use
)
2286 if (ip_normal_pos (data
->current_loop
))
2287 add_candidate_1 (data
, base
, step
, important
, IP_NORMAL
, use
, NULL
);
2288 if (ip_end_pos (data
->current_loop
)
2289 && allow_ip_end_pos_p (data
->current_loop
))
2290 add_candidate_1 (data
, base
, step
, important
, IP_END
, use
, NULL
);
2292 if (use
!= NULL
&& use
->type
== USE_ADDRESS
)
2293 add_autoinc_candidates (data
, base
, step
, important
, use
);
2296 /* Add a standard "0 + 1 * iteration" iv candidate for a
2297 type with SIZE bits. */
2300 add_standard_iv_candidates_for_size (struct ivopts_data
*data
,
2303 tree type
= lang_hooks
.types
.type_for_size (size
, true);
2304 add_candidate (data
, build_int_cst (type
, 0), build_int_cst (type
, 1),
2308 /* Adds standard iv candidates. */
2311 add_standard_iv_candidates (struct ivopts_data
*data
)
2313 add_standard_iv_candidates_for_size (data
, INT_TYPE_SIZE
);
2315 /* The same for a double-integer type if it is still fast enough. */
2316 if (BITS_PER_WORD
>= INT_TYPE_SIZE
* 2)
2317 add_standard_iv_candidates_for_size (data
, INT_TYPE_SIZE
* 2);
2321 /* Adds candidates bases on the old induction variable IV. */
2324 add_old_iv_candidates (struct ivopts_data
*data
, struct iv
*iv
)
2328 struct iv_cand
*cand
;
2330 add_candidate (data
, iv
->base
, iv
->step
, true, NULL
);
2332 /* The same, but with initial value zero. */
2333 if (POINTER_TYPE_P (TREE_TYPE (iv
->base
)))
2334 add_candidate (data
, size_int (0), iv
->step
, true, NULL
);
2336 add_candidate (data
, build_int_cst (TREE_TYPE (iv
->base
), 0),
2337 iv
->step
, true, NULL
);
2339 phi
= SSA_NAME_DEF_STMT (iv
->ssa_name
);
2340 if (gimple_code (phi
) == GIMPLE_PHI
)
2342 /* Additionally record the possibility of leaving the original iv
2344 def
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (data
->current_loop
));
2345 cand
= add_candidate_1 (data
,
2346 iv
->base
, iv
->step
, true, IP_ORIGINAL
, NULL
,
2347 SSA_NAME_DEF_STMT (def
));
2348 cand
->var_before
= iv
->ssa_name
;
2349 cand
->var_after
= def
;
2353 /* Adds candidates based on the old induction variables. */
2356 add_old_ivs_candidates (struct ivopts_data
*data
)
2362 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
2364 iv
= ver_info (data
, i
)->iv
;
2365 if (iv
&& iv
->biv_p
&& !integer_zerop (iv
->step
))
2366 add_old_iv_candidates (data
, iv
);
2370 /* Adds candidates based on the value of the induction variable IV and USE. */
2373 add_iv_value_candidates (struct ivopts_data
*data
,
2374 struct iv
*iv
, struct iv_use
*use
)
2376 unsigned HOST_WIDE_INT offset
;
2380 add_candidate (data
, iv
->base
, iv
->step
, false, use
);
2382 /* The same, but with initial value zero. Make such variable important,
2383 since it is generic enough so that possibly many uses may be based
2385 basetype
= TREE_TYPE (iv
->base
);
2386 if (POINTER_TYPE_P (basetype
))
2387 basetype
= sizetype
;
2388 add_candidate (data
, build_int_cst (basetype
, 0),
2389 iv
->step
, true, use
);
2391 /* Third, try removing the constant offset. Make sure to even
2392 add a candidate for &a[0] vs. (T *)&a. */
2393 base
= strip_offset (iv
->base
, &offset
);
2395 || base
!= iv
->base
)
2396 add_candidate (data
, base
, iv
->step
, false, use
);
2399 /* Adds candidates based on the uses. */
2402 add_derived_ivs_candidates (struct ivopts_data
*data
)
2406 for (i
= 0; i
< n_iv_uses (data
); i
++)
2408 struct iv_use
*use
= iv_use (data
, i
);
2415 case USE_NONLINEAR_EXPR
:
2418 /* Just add the ivs based on the value of the iv used here. */
2419 add_iv_value_candidates (data
, use
->iv
, use
);
2428 /* Record important candidates and add them to related_cands bitmaps
2432 record_important_candidates (struct ivopts_data
*data
)
2437 for (i
= 0; i
< n_iv_cands (data
); i
++)
2439 struct iv_cand
*cand
= iv_cand (data
, i
);
2441 if (cand
->important
)
2442 bitmap_set_bit (data
->important_candidates
, i
);
2445 data
->consider_all_candidates
= (n_iv_cands (data
)
2446 <= CONSIDER_ALL_CANDIDATES_BOUND
);
2448 if (data
->consider_all_candidates
)
2450 /* We will not need "related_cands" bitmaps in this case,
2451 so release them to decrease peak memory consumption. */
2452 for (i
= 0; i
< n_iv_uses (data
); i
++)
2454 use
= iv_use (data
, i
);
2455 BITMAP_FREE (use
->related_cands
);
2460 /* Add important candidates to the related_cands bitmaps. */
2461 for (i
= 0; i
< n_iv_uses (data
); i
++)
2462 bitmap_ior_into (iv_use (data
, i
)->related_cands
,
2463 data
->important_candidates
);
2467 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
2468 If consider_all_candidates is true, we use a two-dimensional array, otherwise
2469 we allocate a simple list to every use. */
2472 alloc_use_cost_map (struct ivopts_data
*data
)
2474 unsigned i
, size
, s
, j
;
2476 for (i
= 0; i
< n_iv_uses (data
); i
++)
2478 struct iv_use
*use
= iv_use (data
, i
);
2481 if (data
->consider_all_candidates
)
2482 size
= n_iv_cands (data
);
2486 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, j
, bi
)
2491 /* Round up to the power of two, so that moduling by it is fast. */
2492 for (size
= 1; size
< s
; size
<<= 1)
2496 use
->n_map_members
= size
;
2497 use
->cost_map
= XCNEWVEC (struct cost_pair
, size
);
2501 /* Returns description of computation cost of expression whose runtime
2502 cost is RUNTIME and complexity corresponds to COMPLEXITY. */
2505 new_cost (unsigned runtime
, unsigned complexity
)
2509 cost
.cost
= runtime
;
2510 cost
.complexity
= complexity
;
2515 /* Adds costs COST1 and COST2. */
2518 add_costs (comp_cost cost1
, comp_cost cost2
)
2520 cost1
.cost
+= cost2
.cost
;
2521 cost1
.complexity
+= cost2
.complexity
;
2525 /* Subtracts costs COST1 and COST2. */
2528 sub_costs (comp_cost cost1
, comp_cost cost2
)
2530 cost1
.cost
-= cost2
.cost
;
2531 cost1
.complexity
-= cost2
.complexity
;
2536 /* Returns a negative number if COST1 < COST2, a positive number if
2537 COST1 > COST2, and 0 if COST1 = COST2. */
2540 compare_costs (comp_cost cost1
, comp_cost cost2
)
2542 if (cost1
.cost
== cost2
.cost
)
2543 return cost1
.complexity
- cost2
.complexity
;
2545 return cost1
.cost
- cost2
.cost
;
2548 /* Returns true if COST is infinite. */
2551 infinite_cost_p (comp_cost cost
)
2553 return cost
.cost
== INFTY
;
2556 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
2557 on invariants DEPENDS_ON and that the value used in expressing it
2561 set_use_iv_cost (struct ivopts_data
*data
,
2562 struct iv_use
*use
, struct iv_cand
*cand
,
2563 comp_cost cost
, bitmap depends_on
, tree value
)
2567 if (infinite_cost_p (cost
))
2569 BITMAP_FREE (depends_on
);
2573 if (data
->consider_all_candidates
)
2575 use
->cost_map
[cand
->id
].cand
= cand
;
2576 use
->cost_map
[cand
->id
].cost
= cost
;
2577 use
->cost_map
[cand
->id
].depends_on
= depends_on
;
2578 use
->cost_map
[cand
->id
].value
= value
;
2582 /* n_map_members is a power of two, so this computes modulo. */
2583 s
= cand
->id
& (use
->n_map_members
- 1);
2584 for (i
= s
; i
< use
->n_map_members
; i
++)
2585 if (!use
->cost_map
[i
].cand
)
2587 for (i
= 0; i
< s
; i
++)
2588 if (!use
->cost_map
[i
].cand
)
2594 use
->cost_map
[i
].cand
= cand
;
2595 use
->cost_map
[i
].cost
= cost
;
2596 use
->cost_map
[i
].depends_on
= depends_on
;
2597 use
->cost_map
[i
].value
= value
;
2600 /* Gets cost of (USE, CANDIDATE) pair. */
2602 static struct cost_pair
*
2603 get_use_iv_cost (struct ivopts_data
*data
, struct iv_use
*use
,
2604 struct iv_cand
*cand
)
2607 struct cost_pair
*ret
;
2612 if (data
->consider_all_candidates
)
2614 ret
= use
->cost_map
+ cand
->id
;
2621 /* n_map_members is a power of two, so this computes modulo. */
2622 s
= cand
->id
& (use
->n_map_members
- 1);
2623 for (i
= s
; i
< use
->n_map_members
; i
++)
2624 if (use
->cost_map
[i
].cand
== cand
)
2625 return use
->cost_map
+ i
;
2627 for (i
= 0; i
< s
; i
++)
2628 if (use
->cost_map
[i
].cand
== cand
)
2629 return use
->cost_map
+ i
;
2634 /* Returns estimate on cost of computing SEQ. */
2637 seq_cost (rtx seq
, bool speed
)
2642 for (; seq
; seq
= NEXT_INSN (seq
))
2644 set
= single_set (seq
);
2646 cost
+= rtx_cost (set
, SET
,speed
);
2654 /* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
2656 produce_memory_decl_rtl (tree obj
, int *regno
)
2658 addr_space_t as
= TYPE_ADDR_SPACE (TREE_TYPE (obj
));
2659 enum machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
2663 if (TREE_STATIC (obj
) || DECL_EXTERNAL (obj
))
2665 const char *name
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj
));
2666 x
= gen_rtx_SYMBOL_REF (address_mode
, name
);
2667 SET_SYMBOL_REF_DECL (x
, obj
);
2668 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
2669 set_mem_addr_space (x
, as
);
2670 targetm
.encode_section_info (obj
, x
, true);
2674 x
= gen_raw_REG (address_mode
, (*regno
)++);
2675 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
2676 set_mem_addr_space (x
, as
);
2682 /* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
2683 walk_tree. DATA contains the actual fake register number. */
2686 prepare_decl_rtl (tree
*expr_p
, int *ws
, void *data
)
2688 tree obj
= NULL_TREE
;
2690 int *regno
= (int *) data
;
2692 switch (TREE_CODE (*expr_p
))
2695 for (expr_p
= &TREE_OPERAND (*expr_p
, 0);
2696 handled_component_p (*expr_p
);
2697 expr_p
= &TREE_OPERAND (*expr_p
, 0))
2700 if (DECL_P (obj
) && !DECL_RTL_SET_P (obj
))
2701 x
= produce_memory_decl_rtl (obj
, regno
);
2706 obj
= SSA_NAME_VAR (*expr_p
);
2707 if (!DECL_RTL_SET_P (obj
))
2708 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2717 if (DECL_RTL_SET_P (obj
))
2720 if (DECL_MODE (obj
) == BLKmode
)
2721 x
= produce_memory_decl_rtl (obj
, regno
);
2723 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2733 VEC_safe_push (tree
, heap
, decl_rtl_to_reset
, obj
);
2734 SET_DECL_RTL (obj
, x
);
2740 /* Determines cost of the computation of EXPR. */
2743 computation_cost (tree expr
, bool speed
)
2746 tree type
= TREE_TYPE (expr
);
2748 /* Avoid using hard regs in ways which may be unsupported. */
2749 int regno
= LAST_VIRTUAL_REGISTER
+ 1;
2750 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
2751 enum node_frequency real_frequency
= node
->frequency
;
2753 node
->frequency
= NODE_FREQUENCY_NORMAL
;
2754 crtl
->maybe_hot_insn_p
= speed
;
2755 walk_tree (&expr
, prepare_decl_rtl
, ®no
, NULL
);
2757 rslt
= expand_expr (expr
, NULL_RTX
, TYPE_MODE (type
), EXPAND_NORMAL
);
2760 default_rtl_profile ();
2761 node
->frequency
= real_frequency
;
2763 cost
= seq_cost (seq
, speed
);
2765 cost
+= address_cost (XEXP (rslt
, 0), TYPE_MODE (type
),
2766 TYPE_ADDR_SPACE (type
), speed
);
2771 /* Returns variable containing the value of candidate CAND at statement AT. */
2774 var_at_stmt (struct loop
*loop
, struct iv_cand
*cand
, gimple stmt
)
2776 if (stmt_after_increment (loop
, cand
, stmt
))
2777 return cand
->var_after
;
2779 return cand
->var_before
;
2782 /* Return the most significant (sign) bit of T. Similar to tree_int_cst_msb,
2783 but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE. */
2786 tree_int_cst_sign_bit (const_tree t
)
2788 unsigned bitno
= TYPE_PRECISION (TREE_TYPE (t
)) - 1;
2789 unsigned HOST_WIDE_INT w
;
2791 if (bitno
< HOST_BITS_PER_WIDE_INT
)
2792 w
= TREE_INT_CST_LOW (t
);
2795 w
= TREE_INT_CST_HIGH (t
);
2796 bitno
-= HOST_BITS_PER_WIDE_INT
;
2799 return (w
>> bitno
) & 1;
2802 /* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
2803 same precision that is at least as wide as the precision of TYPE, stores
2804 BA to A and BB to B, and returns the type of BA. Otherwise, returns the
2808 determine_common_wider_type (tree
*a
, tree
*b
)
2810 tree wider_type
= NULL
;
2812 tree atype
= TREE_TYPE (*a
);
2814 if (CONVERT_EXPR_P (*a
))
2816 suba
= TREE_OPERAND (*a
, 0);
2817 wider_type
= TREE_TYPE (suba
);
2818 if (TYPE_PRECISION (wider_type
) < TYPE_PRECISION (atype
))
2824 if (CONVERT_EXPR_P (*b
))
2826 subb
= TREE_OPERAND (*b
, 0);
2827 if (TYPE_PRECISION (wider_type
) != TYPE_PRECISION (TREE_TYPE (subb
)))
2838 /* Determines the expression by that USE is expressed from induction variable
2839 CAND at statement AT in LOOP. The expression is stored in a decomposed
2840 form into AFF. Returns false if USE cannot be expressed using CAND. */
2843 get_computation_aff (struct loop
*loop
,
2844 struct iv_use
*use
, struct iv_cand
*cand
, gimple at
,
2845 struct affine_tree_combination
*aff
)
2847 tree ubase
= use
->iv
->base
;
2848 tree ustep
= use
->iv
->step
;
2849 tree cbase
= cand
->iv
->base
;
2850 tree cstep
= cand
->iv
->step
, cstep_common
;
2851 tree utype
= TREE_TYPE (ubase
), ctype
= TREE_TYPE (cbase
);
2852 tree common_type
, var
;
2854 aff_tree cbase_aff
, var_aff
;
2857 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
2859 /* We do not have a precision to express the values of use. */
2863 var
= var_at_stmt (loop
, cand
, at
);
2864 uutype
= unsigned_type_for (utype
);
2866 /* If the conversion is not noop, perform it. */
2867 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
2869 cstep
= fold_convert (uutype
, cstep
);
2870 cbase
= fold_convert (uutype
, cbase
);
2871 var
= fold_convert (uutype
, var
);
2874 if (!constant_multiple_of (ustep
, cstep
, &rat
))
2877 /* In case both UBASE and CBASE are shortened to UUTYPE from some common
2878 type, we achieve better folding by computing their difference in this
2879 wider type, and cast the result to UUTYPE. We do not need to worry about
2880 overflows, as all the arithmetics will in the end be performed in UUTYPE
2882 common_type
= determine_common_wider_type (&ubase
, &cbase
);
2884 /* use = ubase - ratio * cbase + ratio * var. */
2885 tree_to_aff_combination (ubase
, common_type
, aff
);
2886 tree_to_aff_combination (cbase
, common_type
, &cbase_aff
);
2887 tree_to_aff_combination (var
, uutype
, &var_aff
);
2889 /* We need to shift the value if we are after the increment. */
2890 if (stmt_after_increment (loop
, cand
, at
))
2894 if (common_type
!= uutype
)
2895 cstep_common
= fold_convert (common_type
, cstep
);
2897 cstep_common
= cstep
;
2899 tree_to_aff_combination (cstep_common
, common_type
, &cstep_aff
);
2900 aff_combination_add (&cbase_aff
, &cstep_aff
);
2903 aff_combination_scale (&cbase_aff
, double_int_neg (rat
));
2904 aff_combination_add (aff
, &cbase_aff
);
2905 if (common_type
!= uutype
)
2906 aff_combination_convert (aff
, uutype
);
2908 aff_combination_scale (&var_aff
, rat
);
2909 aff_combination_add (aff
, &var_aff
);
2914 /* Determines the expression by that USE is expressed from induction variable
2915 CAND at statement AT in LOOP. The computation is unshared. */
2918 get_computation_at (struct loop
*loop
,
2919 struct iv_use
*use
, struct iv_cand
*cand
, gimple at
)
2922 tree type
= TREE_TYPE (use
->iv
->base
);
2924 if (!get_computation_aff (loop
, use
, cand
, at
, &aff
))
2926 unshare_aff_combination (&aff
);
2927 return fold_convert (type
, aff_combination_to_tree (&aff
));
2930 /* Determines the expression by that USE is expressed from induction variable
2931 CAND in LOOP. The computation is unshared. */
2934 get_computation (struct loop
*loop
, struct iv_use
*use
, struct iv_cand
*cand
)
2936 return get_computation_at (loop
, use
, cand
, use
->stmt
);
2939 /* Adjust the cost COST for being in loop setup rather than loop body.
2940 If we're optimizing for space, the loop setup overhead is constant;
2941 if we're optimizing for speed, amortize it over the per-iteration cost. */
2943 adjust_setup_cost (struct ivopts_data
*data
, unsigned cost
)
2947 else if (optimize_loop_for_speed_p (data
->current_loop
))
2948 return cost
/ AVG_LOOP_NITER (data
->current_loop
);
2953 /* Returns cost of addition in MODE. */
2956 add_cost (enum machine_mode mode
, bool speed
)
2958 static unsigned costs
[NUM_MACHINE_MODES
];
2966 force_operand (gen_rtx_fmt_ee (PLUS
, mode
,
2967 gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 1),
2968 gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 2)),
2973 cost
= seq_cost (seq
, speed
);
2979 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2980 fprintf (dump_file
, "Addition in %s costs %d\n",
2981 GET_MODE_NAME (mode
), cost
);
2985 /* Entry in a hashtable of already known costs for multiplication. */
2988 HOST_WIDE_INT cst
; /* The constant to multiply by. */
2989 enum machine_mode mode
; /* In mode. */
2990 unsigned cost
; /* The cost. */
2993 /* Counts hash value for the ENTRY. */
2996 mbc_entry_hash (const void *entry
)
2998 const struct mbc_entry
*e
= (const struct mbc_entry
*) entry
;
3000 return 57 * (hashval_t
) e
->mode
+ (hashval_t
) (e
->cst
% 877);
3003 /* Compares the hash table entries ENTRY1 and ENTRY2. */
3006 mbc_entry_eq (const void *entry1
, const void *entry2
)
3008 const struct mbc_entry
*e1
= (const struct mbc_entry
*) entry1
;
3009 const struct mbc_entry
*e2
= (const struct mbc_entry
*) entry2
;
3011 return (e1
->mode
== e2
->mode
3012 && e1
->cst
== e2
->cst
);
3015 /* Returns cost of multiplication by constant CST in MODE. */
3018 multiply_by_cost (HOST_WIDE_INT cst
, enum machine_mode mode
, bool speed
)
3020 static htab_t costs
;
3021 struct mbc_entry
**cached
, act
;
3026 costs
= htab_create (100, mbc_entry_hash
, mbc_entry_eq
, free
);
3030 cached
= (struct mbc_entry
**) htab_find_slot (costs
, &act
, INSERT
);
3032 return (*cached
)->cost
;
3034 *cached
= XNEW (struct mbc_entry
);
3035 (*cached
)->mode
= mode
;
3036 (*cached
)->cst
= cst
;
3039 expand_mult (mode
, gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 1),
3040 gen_int_mode (cst
, mode
), NULL_RTX
, 0);
3044 cost
= seq_cost (seq
, speed
);
3046 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3047 fprintf (dump_file
, "Multiplication by %d in %s costs %d\n",
3048 (int) cst
, GET_MODE_NAME (mode
), cost
);
3050 (*cached
)->cost
= cost
;
3055 /* Returns true if multiplying by RATIO is allowed in an address. Test the
3056 validity for a memory reference accessing memory of mode MODE in
3057 address space AS. */
3059 DEF_VEC_P (sbitmap
);
3060 DEF_VEC_ALLOC_P (sbitmap
, heap
);
3063 multiplier_allowed_in_address_p (HOST_WIDE_INT ratio
, enum machine_mode mode
,
3066 #define MAX_RATIO 128
3067 unsigned int data_index
= (int) as
* MAX_MACHINE_MODE
+ (int) mode
;
3068 static VEC (sbitmap
, heap
) *valid_mult_list
;
3071 if (data_index
>= VEC_length (sbitmap
, valid_mult_list
))
3072 VEC_safe_grow_cleared (sbitmap
, heap
, valid_mult_list
, data_index
+ 1);
3074 valid_mult
= VEC_index (sbitmap
, valid_mult_list
, data_index
);
3077 enum machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
3078 rtx reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
3082 valid_mult
= sbitmap_alloc (2 * MAX_RATIO
+ 1);
3083 sbitmap_zero (valid_mult
);
3084 addr
= gen_rtx_fmt_ee (MULT
, address_mode
, reg1
, NULL_RTX
);
3085 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
3087 XEXP (addr
, 1) = gen_int_mode (i
, address_mode
);
3088 if (memory_address_addr_space_p (mode
, addr
, as
))
3089 SET_BIT (valid_mult
, i
+ MAX_RATIO
);
3092 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3094 fprintf (dump_file
, " allowed multipliers:");
3095 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
3096 if (TEST_BIT (valid_mult
, i
+ MAX_RATIO
))
3097 fprintf (dump_file
, " %d", (int) i
);
3098 fprintf (dump_file
, "\n");
3099 fprintf (dump_file
, "\n");
3102 VEC_replace (sbitmap
, valid_mult_list
, data_index
, valid_mult
);
3105 if (ratio
> MAX_RATIO
|| ratio
< -MAX_RATIO
)
3108 return TEST_BIT (valid_mult
, ratio
+ MAX_RATIO
);
3111 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
3112 If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
3113 variable is omitted. Compute the cost for a memory reference that accesses
3114 a memory location of mode MEM_MODE in address space AS.
3116 MAY_AUTOINC is set to true if the autoincrement (increasing index by
3117 size of MEM_MODE / RATIO) is available. To make this determination, we
3118 look at the size of the increment to be made, which is given in CSTEP.
3119 CSTEP may be zero if the step is unknown.
3120 STMT_AFTER_INC is true iff the statement we're looking at is after the
3121 increment of the original biv.
3123 TODO -- there must be some better way. This all is quite crude. */
3127 HOST_WIDE_INT min_offset
, max_offset
;
3128 unsigned costs
[2][2][2][2];
3129 } *address_cost_data
;
3131 DEF_VEC_P (address_cost_data
);
3132 DEF_VEC_ALLOC_P (address_cost_data
, heap
);
3135 get_address_cost (bool symbol_present
, bool var_present
,
3136 unsigned HOST_WIDE_INT offset
, HOST_WIDE_INT ratio
,
3137 HOST_WIDE_INT cstep
, enum machine_mode mem_mode
,
3138 addr_space_t as
, bool speed
,
3139 bool stmt_after_inc
, bool *may_autoinc
)
3141 enum machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
3142 static VEC(address_cost_data
, heap
) *address_cost_data_list
;
3143 unsigned int data_index
= (int) as
* MAX_MACHINE_MODE
+ (int) mem_mode
;
3144 address_cost_data data
;
3145 static bool has_preinc
[MAX_MACHINE_MODE
], has_postinc
[MAX_MACHINE_MODE
];
3146 static bool has_predec
[MAX_MACHINE_MODE
], has_postdec
[MAX_MACHINE_MODE
];
3147 unsigned cost
, acost
, complexity
;
3148 bool offset_p
, ratio_p
, autoinc
;
3149 HOST_WIDE_INT s_offset
, autoinc_offset
, msize
;
3150 unsigned HOST_WIDE_INT mask
;
3153 if (data_index
>= VEC_length (address_cost_data
, address_cost_data_list
))
3154 VEC_safe_grow_cleared (address_cost_data
, heap
, address_cost_data_list
,
3157 data
= VEC_index (address_cost_data
, address_cost_data_list
, data_index
);
3161 HOST_WIDE_INT start
= BIGGEST_ALIGNMENT
/ BITS_PER_UNIT
;
3162 HOST_WIDE_INT rat
, off
;
3163 int old_cse_not_expected
;
3164 unsigned sym_p
, var_p
, off_p
, rat_p
, add_c
;
3165 rtx seq
, addr
, base
;
3168 data
= (address_cost_data
) xcalloc (1, sizeof (*data
));
3170 reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
3172 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, reg1
, NULL_RTX
);
3173 for (i
= start
; i
<= 1 << 20; i
<<= 1)
3175 XEXP (addr
, 1) = gen_int_mode (i
, address_mode
);
3176 if (!memory_address_addr_space_p (mem_mode
, addr
, as
))
3179 data
->max_offset
= i
== start
? 0 : i
>> 1;
3180 off
= data
->max_offset
;
3182 for (i
= start
; i
<= 1 << 20; i
<<= 1)
3184 XEXP (addr
, 1) = gen_int_mode (-i
, address_mode
);
3185 if (!memory_address_addr_space_p (mem_mode
, addr
, as
))
3188 data
->min_offset
= i
== start
? 0 : -(i
>> 1);
3190 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3192 fprintf (dump_file
, "get_address_cost:\n");
3193 fprintf (dump_file
, " min offset %s %d\n",
3194 GET_MODE_NAME (mem_mode
),
3195 (int) data
->min_offset
);
3196 fprintf (dump_file
, " max offset %s %d\n",
3197 GET_MODE_NAME (mem_mode
),
3198 (int) data
->max_offset
);
3202 for (i
= 2; i
<= MAX_RATIO
; i
++)
3203 if (multiplier_allowed_in_address_p (i
, mem_mode
, as
))
3209 /* Compute the cost of various addressing modes. */
3211 reg0
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
3212 reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 2);
3214 if (HAVE_PRE_DECREMENT
)
3216 addr
= gen_rtx_PRE_DEC (address_mode
, reg0
);
3217 has_predec
[mem_mode
]
3218 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3220 if (HAVE_POST_DECREMENT
)
3222 addr
= gen_rtx_POST_DEC (address_mode
, reg0
);
3223 has_postdec
[mem_mode
]
3224 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3226 if (HAVE_PRE_INCREMENT
)
3228 addr
= gen_rtx_PRE_INC (address_mode
, reg0
);
3229 has_preinc
[mem_mode
]
3230 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3232 if (HAVE_POST_INCREMENT
)
3234 addr
= gen_rtx_POST_INC (address_mode
, reg0
);
3235 has_postinc
[mem_mode
]
3236 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3238 for (i
= 0; i
< 16; i
++)
3241 var_p
= (i
>> 1) & 1;
3242 off_p
= (i
>> 2) & 1;
3243 rat_p
= (i
>> 3) & 1;
3247 addr
= gen_rtx_fmt_ee (MULT
, address_mode
, addr
,
3248 gen_int_mode (rat
, address_mode
));
3251 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, addr
, reg1
);
3255 base
= gen_rtx_SYMBOL_REF (address_mode
, ggc_strdup (""));
3256 /* ??? We can run into trouble with some backends by presenting
3257 it with symbols which haven't been properly passed through
3258 targetm.encode_section_info. By setting the local bit, we
3259 enhance the probability of things working. */
3260 SYMBOL_REF_FLAGS (base
) = SYMBOL_FLAG_LOCAL
;
3263 base
= gen_rtx_fmt_e (CONST
, address_mode
,
3265 (PLUS
, address_mode
, base
,
3266 gen_int_mode (off
, address_mode
)));
3269 base
= gen_int_mode (off
, address_mode
);
3274 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, addr
, base
);
3277 /* To avoid splitting addressing modes, pretend that no cse will
3279 old_cse_not_expected
= cse_not_expected
;
3280 cse_not_expected
= true;
3281 addr
= memory_address_addr_space (mem_mode
, addr
, as
);
3282 cse_not_expected
= old_cse_not_expected
;
3286 acost
= seq_cost (seq
, speed
);
3287 acost
+= address_cost (addr
, mem_mode
, as
, speed
);
3291 data
->costs
[sym_p
][var_p
][off_p
][rat_p
] = acost
;
3294 /* On some targets, it is quite expensive to load symbol to a register,
3295 which makes addresses that contain symbols look much more expensive.
3296 However, the symbol will have to be loaded in any case before the
3297 loop (and quite likely we have it in register already), so it does not
3298 make much sense to penalize them too heavily. So make some final
3299 tweaks for the SYMBOL_PRESENT modes:
3301 If VAR_PRESENT is false, and the mode obtained by changing symbol to
3302 var is cheaper, use this mode with small penalty.
3303 If VAR_PRESENT is true, try whether the mode with
3304 SYMBOL_PRESENT = false is cheaper even with cost of addition, and
3305 if this is the case, use it. */
3306 add_c
= add_cost (address_mode
, speed
);
3307 for (i
= 0; i
< 8; i
++)
3310 off_p
= (i
>> 1) & 1;
3311 rat_p
= (i
>> 2) & 1;
3313 acost
= data
->costs
[0][1][off_p
][rat_p
] + 1;
3317 if (acost
< data
->costs
[1][var_p
][off_p
][rat_p
])
3318 data
->costs
[1][var_p
][off_p
][rat_p
] = acost
;
3321 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3323 fprintf (dump_file
, "Address costs:\n");
3325 for (i
= 0; i
< 16; i
++)
3328 var_p
= (i
>> 1) & 1;
3329 off_p
= (i
>> 2) & 1;
3330 rat_p
= (i
>> 3) & 1;
3332 fprintf (dump_file
, " ");
3334 fprintf (dump_file
, "sym + ");
3336 fprintf (dump_file
, "var + ");
3338 fprintf (dump_file
, "cst + ");
3340 fprintf (dump_file
, "rat * ");
3342 acost
= data
->costs
[sym_p
][var_p
][off_p
][rat_p
];
3343 fprintf (dump_file
, "index costs %d\n", acost
);
3345 if (has_predec
[mem_mode
] || has_postdec
[mem_mode
]
3346 || has_preinc
[mem_mode
] || has_postinc
[mem_mode
])
3347 fprintf (dump_file
, " May include autoinc/dec\n");
3348 fprintf (dump_file
, "\n");
3351 VEC_replace (address_cost_data
, address_cost_data_list
,
3355 bits
= GET_MODE_BITSIZE (address_mode
);
3356 mask
= ~(~(unsigned HOST_WIDE_INT
) 0 << (bits
- 1) << 1);
3358 if ((offset
>> (bits
- 1) & 1))
3363 msize
= GET_MODE_SIZE (mem_mode
);
3364 autoinc_offset
= offset
;
3366 autoinc_offset
+= ratio
* cstep
;
3367 if (symbol_present
|| var_present
|| ratio
!= 1)
3369 else if ((has_postinc
[mem_mode
] && autoinc_offset
== 0
3371 || (has_postdec
[mem_mode
] && autoinc_offset
== 0
3373 || (has_preinc
[mem_mode
] && autoinc_offset
== msize
3375 || (has_predec
[mem_mode
] && autoinc_offset
== -msize
3376 && msize
== -cstep
))
3380 offset_p
= (s_offset
!= 0
3381 && data
->min_offset
<= s_offset
3382 && s_offset
<= data
->max_offset
);
3383 ratio_p
= (ratio
!= 1
3384 && multiplier_allowed_in_address_p (ratio
, mem_mode
, as
));
3386 if (ratio
!= 1 && !ratio_p
)
3387 cost
+= multiply_by_cost (ratio
, address_mode
, speed
);
3389 if (s_offset
&& !offset_p
&& !symbol_present
)
3390 cost
+= add_cost (address_mode
, speed
);
3393 *may_autoinc
= autoinc
;
3394 acost
= data
->costs
[symbol_present
][var_present
][offset_p
][ratio_p
];
3395 complexity
= (symbol_present
!= 0) + (var_present
!= 0) + offset_p
+ ratio_p
;
3396 return new_cost (cost
+ acost
, complexity
);
3399 /* Estimates cost of forcing expression EXPR into a variable. */
3402 force_expr_to_var_cost (tree expr
, bool speed
)
3404 static bool costs_initialized
= false;
3405 static unsigned integer_cost
[2];
3406 static unsigned symbol_cost
[2];
3407 static unsigned address_cost
[2];
3409 comp_cost cost0
, cost1
, cost
;
3410 enum machine_mode mode
;
3412 if (!costs_initialized
)
3414 tree type
= build_pointer_type (integer_type_node
);
3419 var
= create_tmp_var_raw (integer_type_node
, "test_var");
3420 TREE_STATIC (var
) = 1;
3421 x
= produce_memory_decl_rtl (var
, NULL
);
3422 SET_DECL_RTL (var
, x
);
3424 addr
= build1 (ADDR_EXPR
, type
, var
);
3427 for (i
= 0; i
< 2; i
++)
3429 integer_cost
[i
] = computation_cost (build_int_cst (integer_type_node
,
3432 symbol_cost
[i
] = computation_cost (addr
, i
) + 1;
3435 = computation_cost (build2 (POINTER_PLUS_EXPR
, type
,
3437 build_int_cst (sizetype
, 2000)), i
) + 1;
3438 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3440 fprintf (dump_file
, "force_expr_to_var_cost %s costs:\n", i
? "speed" : "size");
3441 fprintf (dump_file
, " integer %d\n", (int) integer_cost
[i
]);
3442 fprintf (dump_file
, " symbol %d\n", (int) symbol_cost
[i
]);
3443 fprintf (dump_file
, " address %d\n", (int) address_cost
[i
]);
3444 fprintf (dump_file
, " other %d\n", (int) target_spill_cost
[i
]);
3445 fprintf (dump_file
, "\n");
3449 costs_initialized
= true;
3454 if (SSA_VAR_P (expr
))
3457 if (is_gimple_min_invariant (expr
))
3459 if (TREE_CODE (expr
) == INTEGER_CST
)
3460 return new_cost (integer_cost
[speed
], 0);
3462 if (TREE_CODE (expr
) == ADDR_EXPR
)
3464 tree obj
= TREE_OPERAND (expr
, 0);
3466 if (TREE_CODE (obj
) == VAR_DECL
3467 || TREE_CODE (obj
) == PARM_DECL
3468 || TREE_CODE (obj
) == RESULT_DECL
)
3469 return new_cost (symbol_cost
[speed
], 0);
3472 return new_cost (address_cost
[speed
], 0);
3475 switch (TREE_CODE (expr
))
3477 case POINTER_PLUS_EXPR
:
3481 op0
= TREE_OPERAND (expr
, 0);
3482 op1
= TREE_OPERAND (expr
, 1);
3486 if (is_gimple_val (op0
))
3489 cost0
= force_expr_to_var_cost (op0
, speed
);
3491 if (is_gimple_val (op1
))
3494 cost1
= force_expr_to_var_cost (op1
, speed
);
3499 op0
= TREE_OPERAND (expr
, 0);
3503 if (is_gimple_val (op0
))
3506 cost0
= force_expr_to_var_cost (op0
, speed
);
3512 /* Just an arbitrary value, FIXME. */
3513 return new_cost (target_spill_cost
[speed
], 0);
3516 mode
= TYPE_MODE (TREE_TYPE (expr
));
3517 switch (TREE_CODE (expr
))
3519 case POINTER_PLUS_EXPR
:
3523 cost
= new_cost (add_cost (mode
, speed
), 0);
3527 if (cst_and_fits_in_hwi (op0
))
3528 cost
= new_cost (multiply_by_cost (int_cst_value (op0
), mode
, speed
), 0);
3529 else if (cst_and_fits_in_hwi (op1
))
3530 cost
= new_cost (multiply_by_cost (int_cst_value (op1
), mode
, speed
), 0);
3532 return new_cost (target_spill_cost
[speed
], 0);
3539 cost
= add_costs (cost
, cost0
);
3540 cost
= add_costs (cost
, cost1
);
3542 /* Bound the cost by target_spill_cost. The parts of complicated
3543 computations often are either loop invariant or at least can
3544 be shared between several iv uses, so letting this grow without
3545 limits would not give reasonable results. */
3546 if (cost
.cost
> (int) target_spill_cost
[speed
])
3547 cost
.cost
= target_spill_cost
[speed
];
3552 /* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
3553 invariants the computation depends on. */
3556 force_var_cost (struct ivopts_data
*data
,
3557 tree expr
, bitmap
*depends_on
)
3561 fd_ivopts_data
= data
;
3562 walk_tree (&expr
, find_depends
, depends_on
, NULL
);
3565 return force_expr_to_var_cost (expr
, data
->speed
);
3568 /* Estimates cost of expressing address ADDR as var + symbol + offset. The
3569 value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
3570 to false if the corresponding part is missing. DEPENDS_ON is a set of the
3571 invariants the computation depends on. */
3574 split_address_cost (struct ivopts_data
*data
,
3575 tree addr
, bool *symbol_present
, bool *var_present
,
3576 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3579 HOST_WIDE_INT bitsize
;
3580 HOST_WIDE_INT bitpos
;
3582 enum machine_mode mode
;
3583 int unsignedp
, volatilep
;
3585 core
= get_inner_reference (addr
, &bitsize
, &bitpos
, &toffset
, &mode
,
3586 &unsignedp
, &volatilep
, false);
3589 || bitpos
% BITS_PER_UNIT
!= 0
3590 || TREE_CODE (core
) != VAR_DECL
)
3592 *symbol_present
= false;
3593 *var_present
= true;
3594 fd_ivopts_data
= data
;
3595 walk_tree (&addr
, find_depends
, depends_on
, NULL
);
3596 return new_cost (target_spill_cost
[data
->speed
], 0);
3599 *offset
+= bitpos
/ BITS_PER_UNIT
;
3600 if (TREE_STATIC (core
)
3601 || DECL_EXTERNAL (core
))
3603 *symbol_present
= true;
3604 *var_present
= false;
3608 *symbol_present
= false;
3609 *var_present
= true;
3613 /* Estimates cost of expressing difference of addresses E1 - E2 as
3614 var + symbol + offset. The value of offset is added to OFFSET,
3615 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3616 part is missing. DEPENDS_ON is a set of the invariants the computation
3620 ptr_difference_cost (struct ivopts_data
*data
,
3621 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
3622 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3624 HOST_WIDE_INT diff
= 0;
3625 aff_tree aff_e1
, aff_e2
;
3628 gcc_assert (TREE_CODE (e1
) == ADDR_EXPR
);
3630 if (ptr_difference_const (e1
, e2
, &diff
))
3633 *symbol_present
= false;
3634 *var_present
= false;
3638 if (integer_zerop (e2
))
3639 return split_address_cost (data
, TREE_OPERAND (e1
, 0),
3640 symbol_present
, var_present
, offset
, depends_on
);
3642 *symbol_present
= false;
3643 *var_present
= true;
3645 type
= signed_type_for (TREE_TYPE (e1
));
3646 tree_to_aff_combination (e1
, type
, &aff_e1
);
3647 tree_to_aff_combination (e2
, type
, &aff_e2
);
3648 aff_combination_scale (&aff_e2
, double_int_minus_one
);
3649 aff_combination_add (&aff_e1
, &aff_e2
);
3651 return force_var_cost (data
, aff_combination_to_tree (&aff_e1
), depends_on
);
3654 /* Estimates cost of expressing difference E1 - E2 as
3655 var + symbol + offset. The value of offset is added to OFFSET,
3656 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3657 part is missing. DEPENDS_ON is a set of the invariants the computation
3661 difference_cost (struct ivopts_data
*data
,
3662 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
3663 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3665 enum machine_mode mode
= TYPE_MODE (TREE_TYPE (e1
));
3666 unsigned HOST_WIDE_INT off1
, off2
;
3667 aff_tree aff_e1
, aff_e2
;
3670 e1
= strip_offset (e1
, &off1
);
3671 e2
= strip_offset (e2
, &off2
);
3672 *offset
+= off1
- off2
;
3677 if (TREE_CODE (e1
) == ADDR_EXPR
)
3678 return ptr_difference_cost (data
, e1
, e2
, symbol_present
, var_present
,
3679 offset
, depends_on
);
3680 *symbol_present
= false;
3682 if (operand_equal_p (e1
, e2
, 0))
3684 *var_present
= false;
3688 *var_present
= true;
3690 if (integer_zerop (e2
))
3691 return force_var_cost (data
, e1
, depends_on
);
3693 if (integer_zerop (e1
))
3695 comp_cost cost
= force_var_cost (data
, e2
, depends_on
);
3696 cost
.cost
+= multiply_by_cost (-1, mode
, data
->speed
);
3700 type
= signed_type_for (TREE_TYPE (e1
));
3701 tree_to_aff_combination (e1
, type
, &aff_e1
);
3702 tree_to_aff_combination (e2
, type
, &aff_e2
);
3703 aff_combination_scale (&aff_e2
, double_int_minus_one
);
3704 aff_combination_add (&aff_e1
, &aff_e2
);
3706 return force_var_cost (data
, aff_combination_to_tree (&aff_e1
), depends_on
);
3709 /* Determines the cost of the computation by that USE is expressed
3710 from induction variable CAND. If ADDRESS_P is true, we just need
3711 to create an address from it, otherwise we want to get it into
3712 register. A set of invariants we depend on is stored in
3713 DEPENDS_ON. AT is the statement at that the value is computed.
3714 If CAN_AUTOINC is nonnull, use it to record whether autoinc
3715 addressing is likely. */
3718 get_computation_cost_at (struct ivopts_data
*data
,
3719 struct iv_use
*use
, struct iv_cand
*cand
,
3720 bool address_p
, bitmap
*depends_on
, gimple at
,
3723 tree ubase
= use
->iv
->base
, ustep
= use
->iv
->step
;
3725 tree utype
= TREE_TYPE (ubase
), ctype
;
3726 unsigned HOST_WIDE_INT cstepi
, offset
= 0;
3727 HOST_WIDE_INT ratio
, aratio
;
3728 bool var_present
, symbol_present
, stmt_is_after_inc
;
3731 bool speed
= optimize_bb_for_speed_p (gimple_bb (at
));
3735 /* Only consider real candidates. */
3737 return infinite_cost
;
3739 cbase
= cand
->iv
->base
;
3740 cstep
= cand
->iv
->step
;
3741 ctype
= TREE_TYPE (cbase
);
3743 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
3745 /* We do not have a precision to express the values of use. */
3746 return infinite_cost
;
3751 /* Do not try to express address of an object with computation based
3752 on address of a different object. This may cause problems in rtl
3753 level alias analysis (that does not expect this to be happening,
3754 as this is illegal in C), and would be unlikely to be useful
3756 if (use
->iv
->base_object
3757 && cand
->iv
->base_object
3758 && !operand_equal_p (use
->iv
->base_object
, cand
->iv
->base_object
, 0))
3759 return infinite_cost
;
3762 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
3764 /* TODO -- add direct handling of this case. */
3768 /* CSTEPI is removed from the offset in case statement is after the
3769 increment. If the step is not constant, we use zero instead.
3770 This is a bit imprecise (there is the extra addition), but
3771 redundancy elimination is likely to transform the code so that
3772 it uses value of the variable before increment anyway,
3773 so it is not that much unrealistic. */
3774 if (cst_and_fits_in_hwi (cstep
))
3775 cstepi
= int_cst_value (cstep
);
3779 if (!constant_multiple_of (ustep
, cstep
, &rat
))
3780 return infinite_cost
;
3782 if (double_int_fits_in_shwi_p (rat
))
3783 ratio
= double_int_to_shwi (rat
);
3785 return infinite_cost
;
3788 ctype
= TREE_TYPE (cbase
);
3790 /* use = ubase + ratio * (var - cbase). If either cbase is a constant
3791 or ratio == 1, it is better to handle this like
3793 ubase - ratio * cbase + ratio * var
3795 (also holds in the case ratio == -1, TODO. */
3797 if (cst_and_fits_in_hwi (cbase
))
3799 offset
= - ratio
* int_cst_value (cbase
);
3800 cost
= difference_cost (data
,
3801 ubase
, build_int_cst (utype
, 0),
3802 &symbol_present
, &var_present
, &offset
,
3805 else if (ratio
== 1)
3807 cost
= difference_cost (data
,
3809 &symbol_present
, &var_present
, &offset
,
3813 && !POINTER_TYPE_P (ctype
)
3814 && multiplier_allowed_in_address_p
3815 (ratio
, TYPE_MODE (TREE_TYPE (utype
)),
3816 TYPE_ADDR_SPACE (TREE_TYPE (utype
))))
3819 = fold_build2 (MULT_EXPR
, ctype
, cbase
, build_int_cst (ctype
, ratio
));
3820 cost
= difference_cost (data
,
3822 &symbol_present
, &var_present
, &offset
,
3827 cost
= force_var_cost (data
, cbase
, depends_on
);
3828 cost
.cost
+= add_cost (TYPE_MODE (ctype
), data
->speed
);
3829 cost
= add_costs (cost
,
3830 difference_cost (data
,
3831 ubase
, build_int_cst (utype
, 0),
3832 &symbol_present
, &var_present
,
3833 &offset
, depends_on
));
3836 /* If we are after the increment, the value of the candidate is higher by
3838 stmt_is_after_inc
= stmt_after_increment (data
->current_loop
, cand
, at
);
3839 if (stmt_is_after_inc
)
3840 offset
-= ratio
* cstepi
;
3842 /* Now the computation is in shape symbol + var1 + const + ratio * var2.
3843 (symbol/var1/const parts may be omitted). If we are looking for an
3844 address, find the cost of addressing this. */
3846 return add_costs (cost
,
3847 get_address_cost (symbol_present
, var_present
,
3848 offset
, ratio
, cstepi
,
3849 TYPE_MODE (TREE_TYPE (utype
)),
3850 TYPE_ADDR_SPACE (TREE_TYPE (utype
)),
3851 speed
, stmt_is_after_inc
,
3854 /* Otherwise estimate the costs for computing the expression. */
3855 if (!symbol_present
&& !var_present
&& !offset
)
3858 cost
.cost
+= multiply_by_cost (ratio
, TYPE_MODE (ctype
), speed
);
3862 /* Symbol + offset should be compile-time computable so consider that they
3863 are added once to the variable, if present. */
3864 if (var_present
&& (symbol_present
|| offset
))
3865 cost
.cost
+= adjust_setup_cost (data
,
3866 add_cost (TYPE_MODE (ctype
), speed
));
3868 /* Having offset does not affect runtime cost in case it is added to
3869 symbol, but it increases complexity. */
3873 cost
.cost
+= add_cost (TYPE_MODE (ctype
), speed
);
3875 aratio
= ratio
> 0 ? ratio
: -ratio
;
3877 cost
.cost
+= multiply_by_cost (aratio
, TYPE_MODE (ctype
), speed
);
3881 *can_autoinc
= false;
3884 /* Just get the expression, expand it and measure the cost. */
3885 tree comp
= get_computation_at (data
->current_loop
, use
, cand
, at
);
3888 return infinite_cost
;
3891 comp
= build1 (INDIRECT_REF
, TREE_TYPE (TREE_TYPE (comp
)), comp
);
3893 return new_cost (computation_cost (comp
, speed
), 0);
3897 /* Determines the cost of the computation by that USE is expressed
3898 from induction variable CAND. If ADDRESS_P is true, we just need
3899 to create an address from it, otherwise we want to get it into
3900 register. A set of invariants we depend on is stored in
3901 DEPENDS_ON. If CAN_AUTOINC is nonnull, use it to record whether
3902 autoinc addressing is likely. */
3905 get_computation_cost (struct ivopts_data
*data
,
3906 struct iv_use
*use
, struct iv_cand
*cand
,
3907 bool address_p
, bitmap
*depends_on
, bool *can_autoinc
)
3909 return get_computation_cost_at (data
,
3910 use
, cand
, address_p
, depends_on
, use
->stmt
,
3914 /* Determines cost of basing replacement of USE on CAND in a generic
3918 determine_use_iv_cost_generic (struct ivopts_data
*data
,
3919 struct iv_use
*use
, struct iv_cand
*cand
)
3924 /* The simple case first -- if we need to express value of the preserved
3925 original biv, the cost is 0. This also prevents us from counting the
3926 cost of increment twice -- once at this use and once in the cost of
3928 if (cand
->pos
== IP_ORIGINAL
3929 && cand
->incremented_at
== use
->stmt
)
3931 set_use_iv_cost (data
, use
, cand
, zero_cost
, NULL
, NULL_TREE
);
3935 cost
= get_computation_cost (data
, use
, cand
, false, &depends_on
, NULL
);
3936 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
);
3938 return !infinite_cost_p (cost
);
3941 /* Determines cost of basing replacement of USE on CAND in an address. */
3944 determine_use_iv_cost_address (struct ivopts_data
*data
,
3945 struct iv_use
*use
, struct iv_cand
*cand
)
3949 comp_cost cost
= get_computation_cost (data
, use
, cand
, true, &depends_on
,
3952 if (cand
->ainc_use
== use
)
3955 cost
.cost
-= cand
->cost_step
;
3956 /* If we generated the candidate solely for exploiting autoincrement
3957 opportunities, and it turns out it can't be used, set the cost to
3958 infinity to make sure we ignore it. */
3959 else if (cand
->pos
== IP_AFTER_USE
|| cand
->pos
== IP_BEFORE_USE
)
3960 cost
= infinite_cost
;
3962 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
);
3964 return !infinite_cost_p (cost
);
3967 /* Computes value of candidate CAND at position AT in iteration NITER, and
3968 stores it to VAL. */
3971 cand_value_at (struct loop
*loop
, struct iv_cand
*cand
, gimple at
, tree niter
,
3974 aff_tree step
, delta
, nit
;
3975 struct iv
*iv
= cand
->iv
;
3976 tree type
= TREE_TYPE (iv
->base
);
3977 tree steptype
= type
;
3978 if (POINTER_TYPE_P (type
))
3979 steptype
= sizetype
;
3981 tree_to_aff_combination (iv
->step
, steptype
, &step
);
3982 tree_to_aff_combination (niter
, TREE_TYPE (niter
), &nit
);
3983 aff_combination_convert (&nit
, steptype
);
3984 aff_combination_mult (&nit
, &step
, &delta
);
3985 if (stmt_after_increment (loop
, cand
, at
))
3986 aff_combination_add (&delta
, &step
);
3988 tree_to_aff_combination (iv
->base
, type
, val
);
3989 aff_combination_add (val
, &delta
);
3992 /* Returns period of induction variable iv. */
3995 iv_period (struct iv
*iv
)
3997 tree step
= iv
->step
, period
, type
;
4000 gcc_assert (step
&& TREE_CODE (step
) == INTEGER_CST
);
4002 /* Period of the iv is gcd (step, type range). Since type range is power
4003 of two, it suffices to determine the maximum power of two that divides
4005 pow2div
= num_ending_zeros (step
);
4006 type
= unsigned_type_for (TREE_TYPE (step
));
4008 period
= build_low_bits_mask (type
,
4009 (TYPE_PRECISION (type
)
4010 - tree_low_cst (pow2div
, 1)));
4015 /* Returns the comparison operator used when eliminating the iv USE. */
4017 static enum tree_code
4018 iv_elimination_compare (struct ivopts_data
*data
, struct iv_use
*use
)
4020 struct loop
*loop
= data
->current_loop
;
4024 ex_bb
= gimple_bb (use
->stmt
);
4025 exit
= EDGE_SUCC (ex_bb
, 0);
4026 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
4027 exit
= EDGE_SUCC (ex_bb
, 1);
4029 return (exit
->flags
& EDGE_TRUE_VALUE
? EQ_EXPR
: NE_EXPR
);
4032 /* Check whether it is possible to express the condition in USE by comparison
4033 of candidate CAND. If so, store the value compared with to BOUND. */
4036 may_eliminate_iv (struct ivopts_data
*data
,
4037 struct iv_use
*use
, struct iv_cand
*cand
, tree
*bound
)
4042 struct loop
*loop
= data
->current_loop
;
4045 if (TREE_CODE (cand
->iv
->step
) != INTEGER_CST
)
4048 /* For now works only for exits that dominate the loop latch.
4049 TODO: extend to other conditions inside loop body. */
4050 ex_bb
= gimple_bb (use
->stmt
);
4051 if (use
->stmt
!= last_stmt (ex_bb
)
4052 || gimple_code (use
->stmt
) != GIMPLE_COND
4053 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, ex_bb
))
4056 exit
= EDGE_SUCC (ex_bb
, 0);
4057 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
4058 exit
= EDGE_SUCC (ex_bb
, 1);
4059 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
4062 nit
= niter_for_exit (data
, exit
);
4066 /* Determine whether we can use the variable to test the exit condition.
4067 This is the case iff the period of the induction variable is greater
4068 than the number of iterations for which the exit condition is true. */
4069 period
= iv_period (cand
->iv
);
4071 /* If the number of iterations is constant, compare against it directly. */
4072 if (TREE_CODE (nit
) == INTEGER_CST
)
4074 if (!tree_int_cst_lt (nit
, period
))
4078 /* If not, and if this is the only possible exit of the loop, see whether
4079 we can get a conservative estimate on the number of iterations of the
4080 entire loop and compare against that instead. */
4081 else if (loop_only_exit_p (loop
, exit
))
4083 double_int period_value
, max_niter
;
4084 if (!estimated_loop_iterations (loop
, true, &max_niter
))
4086 period_value
= tree_to_double_int (period
);
4087 if (double_int_ucmp (max_niter
, period_value
) >= 0)
4091 /* Otherwise, punt. */
4095 cand_value_at (loop
, cand
, use
->stmt
, nit
, &bnd
);
4097 *bound
= aff_combination_to_tree (&bnd
);
4098 /* It is unlikely that computing the number of iterations using division
4099 would be more profitable than keeping the original induction variable. */
4100 if (expression_expensive_p (*bound
))
4105 /* Determines cost of basing replacement of USE on CAND in a condition. */
4108 determine_use_iv_cost_condition (struct ivopts_data
*data
,
4109 struct iv_use
*use
, struct iv_cand
*cand
)
4111 tree bound
= NULL_TREE
;
4113 bitmap depends_on_elim
= NULL
, depends_on_express
= NULL
, depends_on
;
4114 comp_cost elim_cost
, express_cost
, cost
;
4116 tree
*control_var
, *bound_cst
;
4118 /* Only consider real candidates. */
4121 set_use_iv_cost (data
, use
, cand
, infinite_cost
, NULL
, NULL_TREE
);
4125 /* Try iv elimination. */
4126 if (may_eliminate_iv (data
, use
, cand
, &bound
))
4128 elim_cost
= force_var_cost (data
, bound
, &depends_on_elim
);
4129 /* The bound is a loop invariant, so it will be only computed
4131 elim_cost
.cost
= adjust_setup_cost (data
, elim_cost
.cost
);
4134 elim_cost
= infinite_cost
;
4136 /* Try expressing the original giv. If it is compared with an invariant,
4137 note that we cannot get rid of it. */
4138 ok
= extract_cond_operands (data
, use
->stmt
, &control_var
, &bound_cst
,
4142 /* When the condition is a comparison of the candidate IV against
4143 zero, prefer this IV.
4145 TODO: The constant that we're substracting from the cost should
4146 be target-dependent. This information should be added to the
4147 target costs for each backend. */
4148 if (!infinite_cost_p (elim_cost
) /* Do not try to decrease infinite! */
4149 && integer_zerop (*bound_cst
)
4150 && (operand_equal_p (*control_var
, cand
->var_after
, 0)
4151 || operand_equal_p (*control_var
, cand
->var_before
, 0)))
4152 elim_cost
.cost
-= 1;
4154 express_cost
= get_computation_cost (data
, use
, cand
, false,
4155 &depends_on_express
, NULL
);
4156 fd_ivopts_data
= data
;
4157 walk_tree (&cmp_iv
->base
, find_depends
, &depends_on_express
, NULL
);
4159 /* Choose the better approach, preferring the eliminated IV. */
4160 if (compare_costs (elim_cost
, express_cost
) <= 0)
4163 depends_on
= depends_on_elim
;
4164 depends_on_elim
= NULL
;
4168 cost
= express_cost
;
4169 depends_on
= depends_on_express
;
4170 depends_on_express
= NULL
;
4174 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, bound
);
4176 if (depends_on_elim
)
4177 BITMAP_FREE (depends_on_elim
);
4178 if (depends_on_express
)
4179 BITMAP_FREE (depends_on_express
);
4181 return !infinite_cost_p (cost
);
4184 /* Determines cost of basing replacement of USE on CAND. Returns false
4185 if USE cannot be based on CAND. */
4188 determine_use_iv_cost (struct ivopts_data
*data
,
4189 struct iv_use
*use
, struct iv_cand
*cand
)
4193 case USE_NONLINEAR_EXPR
:
4194 return determine_use_iv_cost_generic (data
, use
, cand
);
4197 return determine_use_iv_cost_address (data
, use
, cand
);
4200 return determine_use_iv_cost_condition (data
, use
, cand
);
4207 /* Return true if get_computation_cost indicates that autoincrement is
4208 a possibility for the pair of USE and CAND, false otherwise. */
4211 autoinc_possible_for_pair (struct ivopts_data
*data
, struct iv_use
*use
,
4212 struct iv_cand
*cand
)
4218 if (use
->type
!= USE_ADDRESS
)
4221 cost
= get_computation_cost (data
, use
, cand
, true, &depends_on
,
4224 BITMAP_FREE (depends_on
);
4226 return !infinite_cost_p (cost
) && can_autoinc
;
4229 /* Examine IP_ORIGINAL candidates to see if they are incremented next to a
4230 use that allows autoincrement, and set their AINC_USE if possible. */
4233 set_autoinc_for_original_candidates (struct ivopts_data
*data
)
4237 for (i
= 0; i
< n_iv_cands (data
); i
++)
4239 struct iv_cand
*cand
= iv_cand (data
, i
);
4240 struct iv_use
*closest
= NULL
;
4241 if (cand
->pos
!= IP_ORIGINAL
)
4243 for (j
= 0; j
< n_iv_uses (data
); j
++)
4245 struct iv_use
*use
= iv_use (data
, j
);
4246 unsigned uid
= gimple_uid (use
->stmt
);
4247 if (gimple_bb (use
->stmt
) != gimple_bb (cand
->incremented_at
)
4248 || uid
> gimple_uid (cand
->incremented_at
))
4250 if (closest
== NULL
|| uid
> gimple_uid (closest
->stmt
))
4253 if (closest
== NULL
|| !autoinc_possible_for_pair (data
, closest
, cand
))
4255 cand
->ainc_use
= closest
;
4259 /* Finds the candidates for the induction variables. */
4262 find_iv_candidates (struct ivopts_data
*data
)
4264 /* Add commonly used ivs. */
4265 add_standard_iv_candidates (data
);
4267 /* Add old induction variables. */
4268 add_old_ivs_candidates (data
);
4270 /* Add induction variables derived from uses. */
4271 add_derived_ivs_candidates (data
);
4273 set_autoinc_for_original_candidates (data
);
4275 /* Record the important candidates. */
4276 record_important_candidates (data
);
4279 /* Determines costs of basing the use of the iv on an iv candidate. */
4282 determine_use_iv_costs (struct ivopts_data
*data
)
4286 struct iv_cand
*cand
;
4287 bitmap to_clear
= BITMAP_ALLOC (NULL
);
4289 alloc_use_cost_map (data
);
4291 for (i
= 0; i
< n_iv_uses (data
); i
++)
4293 use
= iv_use (data
, i
);
4295 if (data
->consider_all_candidates
)
4297 for (j
= 0; j
< n_iv_cands (data
); j
++)
4299 cand
= iv_cand (data
, j
);
4300 determine_use_iv_cost (data
, use
, cand
);
4307 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, j
, bi
)
4309 cand
= iv_cand (data
, j
);
4310 if (!determine_use_iv_cost (data
, use
, cand
))
4311 bitmap_set_bit (to_clear
, j
);
4314 /* Remove the candidates for that the cost is infinite from
4315 the list of related candidates. */
4316 bitmap_and_compl_into (use
->related_cands
, to_clear
);
4317 bitmap_clear (to_clear
);
4321 BITMAP_FREE (to_clear
);
4323 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4325 fprintf (dump_file
, "Use-candidate costs:\n");
4327 for (i
= 0; i
< n_iv_uses (data
); i
++)
4329 use
= iv_use (data
, i
);
4331 fprintf (dump_file
, "Use %d:\n", i
);
4332 fprintf (dump_file
, " cand\tcost\tcompl.\tdepends on\n");
4333 for (j
= 0; j
< use
->n_map_members
; j
++)
4335 if (!use
->cost_map
[j
].cand
4336 || infinite_cost_p (use
->cost_map
[j
].cost
))
4339 fprintf (dump_file
, " %d\t%d\t%d\t",
4340 use
->cost_map
[j
].cand
->id
,
4341 use
->cost_map
[j
].cost
.cost
,
4342 use
->cost_map
[j
].cost
.complexity
);
4343 if (use
->cost_map
[j
].depends_on
)
4344 bitmap_print (dump_file
,
4345 use
->cost_map
[j
].depends_on
, "","");
4346 fprintf (dump_file
, "\n");
4349 fprintf (dump_file
, "\n");
4351 fprintf (dump_file
, "\n");
4355 /* Determines cost of the candidate CAND. */
4358 determine_iv_cost (struct ivopts_data
*data
, struct iv_cand
*cand
)
4360 comp_cost cost_base
;
4361 unsigned cost
, cost_step
;
4370 /* There are two costs associated with the candidate -- its increment
4371 and its initialization. The second is almost negligible for any loop
4372 that rolls enough, so we take it just very little into account. */
4374 base
= cand
->iv
->base
;
4375 cost_base
= force_var_cost (data
, base
, NULL
);
4376 cost_step
= add_cost (TYPE_MODE (TREE_TYPE (base
)), data
->speed
);
4378 cost
= cost_step
+ adjust_setup_cost (data
, cost_base
.cost
);
4380 /* Prefer the original ivs unless we may gain something by replacing it.
4381 The reason is to make debugging simpler; so this is not relevant for
4382 artificial ivs created by other optimization passes. */
4383 if (cand
->pos
!= IP_ORIGINAL
4384 || DECL_ARTIFICIAL (SSA_NAME_VAR (cand
->var_before
)))
4387 /* Prefer not to insert statements into latch unless there are some
4388 already (so that we do not create unnecessary jumps). */
4389 if (cand
->pos
== IP_END
4390 && empty_block_p (ip_end_pos (data
->current_loop
)))
4394 cand
->cost_step
= cost_step
;
4397 /* Determines costs of computation of the candidates. */
4400 determine_iv_costs (struct ivopts_data
*data
)
4404 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4406 fprintf (dump_file
, "Candidate costs:\n");
4407 fprintf (dump_file
, " cand\tcost\n");
4410 for (i
= 0; i
< n_iv_cands (data
); i
++)
4412 struct iv_cand
*cand
= iv_cand (data
, i
);
4414 determine_iv_cost (data
, cand
);
4416 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4417 fprintf (dump_file
, " %d\t%d\n", i
, cand
->cost
);
4420 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4421 fprintf (dump_file
, "\n");
4424 /* Calculates cost for having SIZE induction variables. */
4427 ivopts_global_cost_for_size (struct ivopts_data
*data
, unsigned size
)
4429 /* We add size to the cost, so that we prefer eliminating ivs
4431 return size
+ estimate_reg_pressure_cost (size
, data
->regs_used
, data
->speed
);
4434 /* For each size of the induction variable set determine the penalty. */
4437 determine_set_costs (struct ivopts_data
*data
)
4441 gimple_stmt_iterator psi
;
4443 struct loop
*loop
= data
->current_loop
;
4446 /* We use the following model (definitely improvable, especially the
4447 cost function -- TODO):
4449 We estimate the number of registers available (using MD data), name it A.
4451 We estimate the number of registers used by the loop, name it U. This
4452 number is obtained as the number of loop phi nodes (not counting virtual
4453 registers and bivs) + the number of variables from outside of the loop.
4455 We set a reserve R (free regs that are used for temporary computations,
4456 etc.). For now the reserve is a constant 3.
4458 Let I be the number of induction variables.
4460 -- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
4461 make a lot of ivs without a reason).
4462 -- if A - R < U + I <= A, the cost is I * PRES_COST
4463 -- if U + I > A, the cost is I * PRES_COST and
4464 number of uses * SPILL_COST * (U + I - A) / (U + I) is added. */
4466 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4468 fprintf (dump_file
, "Global costs:\n");
4469 fprintf (dump_file
, " target_avail_regs %d\n", target_avail_regs
);
4470 fprintf (dump_file
, " target_reg_cost %d\n", target_reg_cost
[data
->speed
]);
4471 fprintf (dump_file
, " target_spill_cost %d\n", target_spill_cost
[data
->speed
]);
4475 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
4477 phi
= gsi_stmt (psi
);
4478 op
= PHI_RESULT (phi
);
4480 if (!is_gimple_reg (op
))
4483 if (get_iv (data
, op
))
4489 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
4491 struct version_info
*info
= ver_info (data
, j
);
4493 if (info
->inv_id
&& info
->has_nonlin_use
)
4497 data
->regs_used
= n
;
4498 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4499 fprintf (dump_file
, " regs_used %d\n", n
);
4501 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4503 fprintf (dump_file
, " cost for size:\n");
4504 fprintf (dump_file
, " ivs\tcost\n");
4505 for (j
= 0; j
<= 2 * target_avail_regs
; j
++)
4506 fprintf (dump_file
, " %d\t%d\n", j
,
4507 ivopts_global_cost_for_size (data
, j
));
4508 fprintf (dump_file
, "\n");
4512 /* Returns true if A is a cheaper cost pair than B. */
4515 cheaper_cost_pair (struct cost_pair
*a
, struct cost_pair
*b
)
4525 cmp
= compare_costs (a
->cost
, b
->cost
);
4532 /* In case the costs are the same, prefer the cheaper candidate. */
4533 if (a
->cand
->cost
< b
->cand
->cost
)
4539 /* Computes the cost field of IVS structure. */
4542 iv_ca_recount_cost (struct ivopts_data
*data
, struct iv_ca
*ivs
)
4544 comp_cost cost
= ivs
->cand_use_cost
;
4545 cost
.cost
+= ivs
->cand_cost
;
4546 cost
.cost
+= ivopts_global_cost_for_size (data
, ivs
->n_regs
);
4551 /* Remove invariants in set INVS to set IVS. */
4554 iv_ca_set_remove_invariants (struct iv_ca
*ivs
, bitmap invs
)
4562 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
4564 ivs
->n_invariant_uses
[iid
]--;
4565 if (ivs
->n_invariant_uses
[iid
] == 0)
4570 /* Set USE not to be expressed by any candidate in IVS. */
4573 iv_ca_set_no_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4576 unsigned uid
= use
->id
, cid
;
4577 struct cost_pair
*cp
;
4579 cp
= ivs
->cand_for_use
[uid
];
4585 ivs
->cand_for_use
[uid
] = NULL
;
4586 ivs
->n_cand_uses
[cid
]--;
4588 if (ivs
->n_cand_uses
[cid
] == 0)
4590 bitmap_clear_bit (ivs
->cands
, cid
);
4591 /* Do not count the pseudocandidates. */
4595 ivs
->cand_cost
-= cp
->cand
->cost
;
4597 iv_ca_set_remove_invariants (ivs
, cp
->cand
->depends_on
);
4600 ivs
->cand_use_cost
= sub_costs (ivs
->cand_use_cost
, cp
->cost
);
4602 iv_ca_set_remove_invariants (ivs
, cp
->depends_on
);
4603 iv_ca_recount_cost (data
, ivs
);
4606 /* Add invariants in set INVS to set IVS. */
4609 iv_ca_set_add_invariants (struct iv_ca
*ivs
, bitmap invs
)
4617 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
4619 ivs
->n_invariant_uses
[iid
]++;
4620 if (ivs
->n_invariant_uses
[iid
] == 1)
4625 /* Set cost pair for USE in set IVS to CP. */
4628 iv_ca_set_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4629 struct iv_use
*use
, struct cost_pair
*cp
)
4631 unsigned uid
= use
->id
, cid
;
4633 if (ivs
->cand_for_use
[uid
] == cp
)
4636 if (ivs
->cand_for_use
[uid
])
4637 iv_ca_set_no_cp (data
, ivs
, use
);
4644 ivs
->cand_for_use
[uid
] = cp
;
4645 ivs
->n_cand_uses
[cid
]++;
4646 if (ivs
->n_cand_uses
[cid
] == 1)
4648 bitmap_set_bit (ivs
->cands
, cid
);
4649 /* Do not count the pseudocandidates. */
4653 ivs
->cand_cost
+= cp
->cand
->cost
;
4655 iv_ca_set_add_invariants (ivs
, cp
->cand
->depends_on
);
4658 ivs
->cand_use_cost
= add_costs (ivs
->cand_use_cost
, cp
->cost
);
4659 iv_ca_set_add_invariants (ivs
, cp
->depends_on
);
4660 iv_ca_recount_cost (data
, ivs
);
4664 /* Extend set IVS by expressing USE by some of the candidates in it
4668 iv_ca_add_use (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4671 struct cost_pair
*best_cp
= NULL
, *cp
;
4675 gcc_assert (ivs
->upto
>= use
->id
);
4677 if (ivs
->upto
== use
->id
)
4683 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
4685 cp
= get_use_iv_cost (data
, use
, iv_cand (data
, i
));
4687 if (cheaper_cost_pair (cp
, best_cp
))
4691 iv_ca_set_cp (data
, ivs
, use
, best_cp
);
4694 /* Get cost for assignment IVS. */
4697 iv_ca_cost (struct iv_ca
*ivs
)
4699 /* This was a conditional expression but it triggered a bug in
4702 return infinite_cost
;
4707 /* Returns true if all dependences of CP are among invariants in IVS. */
4710 iv_ca_has_deps (struct iv_ca
*ivs
, struct cost_pair
*cp
)
4715 if (!cp
->depends_on
)
4718 EXECUTE_IF_SET_IN_BITMAP (cp
->depends_on
, 0, i
, bi
)
4720 if (ivs
->n_invariant_uses
[i
] == 0)
4727 /* Creates change of expressing USE by NEW_CP instead of OLD_CP and chains
4728 it before NEXT_CHANGE. */
4730 static struct iv_ca_delta
*
4731 iv_ca_delta_add (struct iv_use
*use
, struct cost_pair
*old_cp
,
4732 struct cost_pair
*new_cp
, struct iv_ca_delta
*next_change
)
4734 struct iv_ca_delta
*change
= XNEW (struct iv_ca_delta
);
4737 change
->old_cp
= old_cp
;
4738 change
->new_cp
= new_cp
;
4739 change
->next_change
= next_change
;
4744 /* Joins two lists of changes L1 and L2. Destructive -- old lists
4747 static struct iv_ca_delta
*
4748 iv_ca_delta_join (struct iv_ca_delta
*l1
, struct iv_ca_delta
*l2
)
4750 struct iv_ca_delta
*last
;
4758 for (last
= l1
; last
->next_change
; last
= last
->next_change
)
4760 last
->next_change
= l2
;
4765 /* Returns candidate by that USE is expressed in IVS. */
4767 static struct cost_pair
*
4768 iv_ca_cand_for_use (struct iv_ca
*ivs
, struct iv_use
*use
)
4770 return ivs
->cand_for_use
[use
->id
];
4773 /* Reverse the list of changes DELTA, forming the inverse to it. */
4775 static struct iv_ca_delta
*
4776 iv_ca_delta_reverse (struct iv_ca_delta
*delta
)
4778 struct iv_ca_delta
*act
, *next
, *prev
= NULL
;
4779 struct cost_pair
*tmp
;
4781 for (act
= delta
; act
; act
= next
)
4783 next
= act
->next_change
;
4784 act
->next_change
= prev
;
4788 act
->old_cp
= act
->new_cp
;
4795 /* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
4796 reverted instead. */
4799 iv_ca_delta_commit (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4800 struct iv_ca_delta
*delta
, bool forward
)
4802 struct cost_pair
*from
, *to
;
4803 struct iv_ca_delta
*act
;
4806 delta
= iv_ca_delta_reverse (delta
);
4808 for (act
= delta
; act
; act
= act
->next_change
)
4812 gcc_assert (iv_ca_cand_for_use (ivs
, act
->use
) == from
);
4813 iv_ca_set_cp (data
, ivs
, act
->use
, to
);
4817 iv_ca_delta_reverse (delta
);
4820 /* Returns true if CAND is used in IVS. */
4823 iv_ca_cand_used_p (struct iv_ca
*ivs
, struct iv_cand
*cand
)
4825 return ivs
->n_cand_uses
[cand
->id
] > 0;
4828 /* Returns number of induction variable candidates in the set IVS. */
4831 iv_ca_n_cands (struct iv_ca
*ivs
)
4833 return ivs
->n_cands
;
4836 /* Free the list of changes DELTA. */
4839 iv_ca_delta_free (struct iv_ca_delta
**delta
)
4841 struct iv_ca_delta
*act
, *next
;
4843 for (act
= *delta
; act
; act
= next
)
4845 next
= act
->next_change
;
4852 /* Allocates new iv candidates assignment. */
4854 static struct iv_ca
*
4855 iv_ca_new (struct ivopts_data
*data
)
4857 struct iv_ca
*nw
= XNEW (struct iv_ca
);
4861 nw
->cand_for_use
= XCNEWVEC (struct cost_pair
*, n_iv_uses (data
));
4862 nw
->n_cand_uses
= XCNEWVEC (unsigned, n_iv_cands (data
));
4863 nw
->cands
= BITMAP_ALLOC (NULL
);
4866 nw
->cand_use_cost
= zero_cost
;
4868 nw
->n_invariant_uses
= XCNEWVEC (unsigned, data
->max_inv_id
+ 1);
4869 nw
->cost
= zero_cost
;
4874 /* Free memory occupied by the set IVS. */
4877 iv_ca_free (struct iv_ca
**ivs
)
4879 free ((*ivs
)->cand_for_use
);
4880 free ((*ivs
)->n_cand_uses
);
4881 BITMAP_FREE ((*ivs
)->cands
);
4882 free ((*ivs
)->n_invariant_uses
);
4887 /* Dumps IVS to FILE. */
4890 iv_ca_dump (struct ivopts_data
*data
, FILE *file
, struct iv_ca
*ivs
)
4892 const char *pref
= " invariants ";
4894 comp_cost cost
= iv_ca_cost (ivs
);
4896 fprintf (file
, " cost %d (complexity %d)\n", cost
.cost
, cost
.complexity
);
4897 bitmap_print (file
, ivs
->cands
, " candidates ","\n");
4899 for (i
= 1; i
<= data
->max_inv_id
; i
++)
4900 if (ivs
->n_invariant_uses
[i
])
4902 fprintf (file
, "%s%d", pref
, i
);
4905 fprintf (file
, "\n");
4908 /* Try changing candidate in IVS to CAND for each use. Return cost of the
4909 new set, and store differences in DELTA. Number of induction variables
4910 in the new set is stored to N_IVS. */
4913 iv_ca_extend (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4914 struct iv_cand
*cand
, struct iv_ca_delta
**delta
,
4920 struct cost_pair
*old_cp
, *new_cp
;
4923 for (i
= 0; i
< ivs
->upto
; i
++)
4925 use
= iv_use (data
, i
);
4926 old_cp
= iv_ca_cand_for_use (ivs
, use
);
4929 && old_cp
->cand
== cand
)
4932 new_cp
= get_use_iv_cost (data
, use
, cand
);
4936 if (!iv_ca_has_deps (ivs
, new_cp
))
4939 if (!cheaper_cost_pair (new_cp
, old_cp
))
4942 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
4945 iv_ca_delta_commit (data
, ivs
, *delta
, true);
4946 cost
= iv_ca_cost (ivs
);
4948 *n_ivs
= iv_ca_n_cands (ivs
);
4949 iv_ca_delta_commit (data
, ivs
, *delta
, false);
4954 /* Try narrowing set IVS by removing CAND. Return the cost of
4955 the new set and store the differences in DELTA. */
4958 iv_ca_narrow (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4959 struct iv_cand
*cand
, struct iv_ca_delta
**delta
)
4963 struct cost_pair
*old_cp
, *new_cp
, *cp
;
4965 struct iv_cand
*cnd
;
4969 for (i
= 0; i
< n_iv_uses (data
); i
++)
4971 use
= iv_use (data
, i
);
4973 old_cp
= iv_ca_cand_for_use (ivs
, use
);
4974 if (old_cp
->cand
!= cand
)
4979 if (data
->consider_all_candidates
)
4981 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, ci
, bi
)
4986 cnd
= iv_cand (data
, ci
);
4988 cp
= get_use_iv_cost (data
, use
, cnd
);
4991 if (!iv_ca_has_deps (ivs
, cp
))
4994 if (!cheaper_cost_pair (cp
, new_cp
))
5002 EXECUTE_IF_AND_IN_BITMAP (use
->related_cands
, ivs
->cands
, 0, ci
, bi
)
5007 cnd
= iv_cand (data
, ci
);
5009 cp
= get_use_iv_cost (data
, use
, cnd
);
5012 if (!iv_ca_has_deps (ivs
, cp
))
5015 if (!cheaper_cost_pair (cp
, new_cp
))
5024 iv_ca_delta_free (delta
);
5025 return infinite_cost
;
5028 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
5031 iv_ca_delta_commit (data
, ivs
, *delta
, true);
5032 cost
= iv_ca_cost (ivs
);
5033 iv_ca_delta_commit (data
, ivs
, *delta
, false);
5038 /* Try optimizing the set of candidates IVS by removing candidates different
5039 from to EXCEPT_CAND from it. Return cost of the new set, and store
5040 differences in DELTA. */
5043 iv_ca_prune (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5044 struct iv_cand
*except_cand
, struct iv_ca_delta
**delta
)
5047 struct iv_ca_delta
*act_delta
, *best_delta
;
5049 comp_cost best_cost
, acost
;
5050 struct iv_cand
*cand
;
5053 best_cost
= iv_ca_cost (ivs
);
5055 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
5057 cand
= iv_cand (data
, i
);
5059 if (cand
== except_cand
)
5062 acost
= iv_ca_narrow (data
, ivs
, cand
, &act_delta
);
5064 if (compare_costs (acost
, best_cost
) < 0)
5067 iv_ca_delta_free (&best_delta
);
5068 best_delta
= act_delta
;
5071 iv_ca_delta_free (&act_delta
);
5080 /* Recurse to possibly remove other unnecessary ivs. */
5081 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
5082 best_cost
= iv_ca_prune (data
, ivs
, except_cand
, delta
);
5083 iv_ca_delta_commit (data
, ivs
, best_delta
, false);
5084 *delta
= iv_ca_delta_join (best_delta
, *delta
);
5088 /* Tries to extend the sets IVS in the best possible way in order
5089 to express the USE. */
5092 try_add_cand_for (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5095 comp_cost best_cost
, act_cost
;
5098 struct iv_cand
*cand
;
5099 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
;
5100 struct cost_pair
*cp
;
5102 iv_ca_add_use (data
, ivs
, use
);
5103 best_cost
= iv_ca_cost (ivs
);
5105 cp
= iv_ca_cand_for_use (ivs
, use
);
5108 best_delta
= iv_ca_delta_add (use
, NULL
, cp
, NULL
);
5109 iv_ca_set_no_cp (data
, ivs
, use
);
5112 /* First try important candidates not based on any memory object. Only if
5113 this fails, try the specific ones. Rationale -- in loops with many
5114 variables the best choice often is to use just one generic biv. If we
5115 added here many ivs specific to the uses, the optimization algorithm later
5116 would be likely to get stuck in a local minimum, thus causing us to create
5117 too many ivs. The approach from few ivs to more seems more likely to be
5118 successful -- starting from few ivs, replacing an expensive use by a
5119 specific iv should always be a win. */
5120 EXECUTE_IF_SET_IN_BITMAP (data
->important_candidates
, 0, i
, bi
)
5122 cand
= iv_cand (data
, i
);
5124 if (cand
->iv
->base_object
!= NULL_TREE
)
5127 if (iv_ca_cand_used_p (ivs
, cand
))
5130 cp
= get_use_iv_cost (data
, use
, cand
);
5134 iv_ca_set_cp (data
, ivs
, use
, cp
);
5135 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
);
5136 iv_ca_set_no_cp (data
, ivs
, use
);
5137 act_delta
= iv_ca_delta_add (use
, NULL
, cp
, act_delta
);
5139 if (compare_costs (act_cost
, best_cost
) < 0)
5141 best_cost
= act_cost
;
5143 iv_ca_delta_free (&best_delta
);
5144 best_delta
= act_delta
;
5147 iv_ca_delta_free (&act_delta
);
5150 if (infinite_cost_p (best_cost
))
5152 for (i
= 0; i
< use
->n_map_members
; i
++)
5154 cp
= use
->cost_map
+ i
;
5159 /* Already tried this. */
5160 if (cand
->important
&& cand
->iv
->base_object
== NULL_TREE
)
5163 if (iv_ca_cand_used_p (ivs
, cand
))
5167 iv_ca_set_cp (data
, ivs
, use
, cp
);
5168 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
);
5169 iv_ca_set_no_cp (data
, ivs
, use
);
5170 act_delta
= iv_ca_delta_add (use
, iv_ca_cand_for_use (ivs
, use
),
5173 if (compare_costs (act_cost
, best_cost
) < 0)
5175 best_cost
= act_cost
;
5178 iv_ca_delta_free (&best_delta
);
5179 best_delta
= act_delta
;
5182 iv_ca_delta_free (&act_delta
);
5186 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
5187 iv_ca_delta_free (&best_delta
);
5189 return !infinite_cost_p (best_cost
);
5192 /* Finds an initial assignment of candidates to uses. */
5194 static struct iv_ca
*
5195 get_initial_solution (struct ivopts_data
*data
)
5197 struct iv_ca
*ivs
= iv_ca_new (data
);
5200 for (i
= 0; i
< n_iv_uses (data
); i
++)
5201 if (!try_add_cand_for (data
, ivs
, iv_use (data
, i
)))
5210 /* Tries to improve set of induction variables IVS. */
5213 try_improve_iv_set (struct ivopts_data
*data
, struct iv_ca
*ivs
)
5216 comp_cost acost
, best_cost
= iv_ca_cost (ivs
);
5217 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
, *tmp_delta
;
5218 struct iv_cand
*cand
;
5220 /* Try extending the set of induction variables by one. */
5221 for (i
= 0; i
< n_iv_cands (data
); i
++)
5223 cand
= iv_cand (data
, i
);
5225 if (iv_ca_cand_used_p (ivs
, cand
))
5228 acost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, &n_ivs
);
5232 /* If we successfully added the candidate and the set is small enough,
5233 try optimizing it by removing other candidates. */
5234 if (n_ivs
<= ALWAYS_PRUNE_CAND_SET_BOUND
)
5236 iv_ca_delta_commit (data
, ivs
, act_delta
, true);
5237 acost
= iv_ca_prune (data
, ivs
, cand
, &tmp_delta
);
5238 iv_ca_delta_commit (data
, ivs
, act_delta
, false);
5239 act_delta
= iv_ca_delta_join (act_delta
, tmp_delta
);
5242 if (compare_costs (acost
, best_cost
) < 0)
5245 iv_ca_delta_free (&best_delta
);
5246 best_delta
= act_delta
;
5249 iv_ca_delta_free (&act_delta
);
5254 /* Try removing the candidates from the set instead. */
5255 best_cost
= iv_ca_prune (data
, ivs
, NULL
, &best_delta
);
5257 /* Nothing more we can do. */
5262 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
5263 gcc_assert (compare_costs (best_cost
, iv_ca_cost (ivs
)) == 0);
5264 iv_ca_delta_free (&best_delta
);
5268 /* Attempts to find the optimal set of induction variables. We do simple
5269 greedy heuristic -- we try to replace at most one candidate in the selected
5270 solution and remove the unused ivs while this improves the cost. */
5272 static struct iv_ca
*
5273 find_optimal_iv_set (struct ivopts_data
*data
)
5279 /* Get the initial solution. */
5280 set
= get_initial_solution (data
);
5283 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5284 fprintf (dump_file
, "Unable to substitute for ivs, failed.\n");
5288 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5290 fprintf (dump_file
, "Initial set of candidates:\n");
5291 iv_ca_dump (data
, dump_file
, set
);
5294 while (try_improve_iv_set (data
, set
))
5296 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5298 fprintf (dump_file
, "Improved to:\n");
5299 iv_ca_dump (data
, dump_file
, set
);
5303 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5305 comp_cost cost
= iv_ca_cost (set
);
5306 fprintf (dump_file
, "Final cost %d (complexity %d)\n\n", cost
.cost
, cost
.complexity
);
5309 for (i
= 0; i
< n_iv_uses (data
); i
++)
5311 use
= iv_use (data
, i
);
5312 use
->selected
= iv_ca_cand_for_use (set
, use
)->cand
;
5318 /* Creates a new induction variable corresponding to CAND. */
5321 create_new_iv (struct ivopts_data
*data
, struct iv_cand
*cand
)
5323 gimple_stmt_iterator incr_pos
;
5333 incr_pos
= gsi_last_bb (ip_normal_pos (data
->current_loop
));
5337 incr_pos
= gsi_last_bb (ip_end_pos (data
->current_loop
));
5345 incr_pos
= gsi_for_stmt (cand
->incremented_at
);
5349 /* Mark that the iv is preserved. */
5350 name_info (data
, cand
->var_before
)->preserve_biv
= true;
5351 name_info (data
, cand
->var_after
)->preserve_biv
= true;
5353 /* Rewrite the increment so that it uses var_before directly. */
5354 find_interesting_uses_op (data
, cand
->var_after
)->selected
= cand
;
5359 gimple_add_tmp_var (cand
->var_before
);
5360 add_referenced_var (cand
->var_before
);
5362 base
= unshare_expr (cand
->iv
->base
);
5364 create_iv (base
, unshare_expr (cand
->iv
->step
),
5365 cand
->var_before
, data
->current_loop
,
5366 &incr_pos
, after
, &cand
->var_before
, &cand
->var_after
);
5369 /* Creates new induction variables described in SET. */
5372 create_new_ivs (struct ivopts_data
*data
, struct iv_ca
*set
)
5375 struct iv_cand
*cand
;
5378 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
5380 cand
= iv_cand (data
, i
);
5381 create_new_iv (data
, cand
);
5386 /* Rewrites USE (definition of iv used in a nonlinear expression)
5387 using candidate CAND. */
5390 rewrite_use_nonlinear_expr (struct ivopts_data
*data
,
5391 struct iv_use
*use
, struct iv_cand
*cand
)
5396 gimple_stmt_iterator bsi
;
5398 /* An important special case -- if we are asked to express value of
5399 the original iv by itself, just exit; there is no need to
5400 introduce a new computation (that might also need casting the
5401 variable to unsigned and back). */
5402 if (cand
->pos
== IP_ORIGINAL
5403 && cand
->incremented_at
== use
->stmt
)
5405 tree step
, ctype
, utype
;
5406 enum tree_code incr_code
= PLUS_EXPR
, old_code
;
5408 gcc_assert (is_gimple_assign (use
->stmt
));
5409 gcc_assert (gimple_assign_lhs (use
->stmt
) == cand
->var_after
);
5411 step
= cand
->iv
->step
;
5412 ctype
= TREE_TYPE (step
);
5413 utype
= TREE_TYPE (cand
->var_after
);
5414 if (TREE_CODE (step
) == NEGATE_EXPR
)
5416 incr_code
= MINUS_EXPR
;
5417 step
= TREE_OPERAND (step
, 0);
5420 /* Check whether we may leave the computation unchanged.
5421 This is the case only if it does not rely on other
5422 computations in the loop -- otherwise, the computation
5423 we rely upon may be removed in remove_unused_ivs,
5424 thus leading to ICE. */
5425 old_code
= gimple_assign_rhs_code (use
->stmt
);
5426 if (old_code
== PLUS_EXPR
5427 || old_code
== MINUS_EXPR
5428 || old_code
== POINTER_PLUS_EXPR
)
5430 if (gimple_assign_rhs1 (use
->stmt
) == cand
->var_before
)
5431 op
= gimple_assign_rhs2 (use
->stmt
);
5432 else if (old_code
!= MINUS_EXPR
5433 && gimple_assign_rhs2 (use
->stmt
) == cand
->var_before
)
5434 op
= gimple_assign_rhs1 (use
->stmt
);
5442 && (TREE_CODE (op
) == INTEGER_CST
5443 || operand_equal_p (op
, step
, 0)))
5446 /* Otherwise, add the necessary computations to express
5448 op
= fold_convert (ctype
, cand
->var_before
);
5449 comp
= fold_convert (utype
,
5450 build2 (incr_code
, ctype
, op
,
5451 unshare_expr (step
)));
5455 comp
= get_computation (data
->current_loop
, use
, cand
);
5456 gcc_assert (comp
!= NULL_TREE
);
5459 switch (gimple_code (use
->stmt
))
5462 tgt
= PHI_RESULT (use
->stmt
);
5464 /* If we should keep the biv, do not replace it. */
5465 if (name_info (data
, tgt
)->preserve_biv
)
5468 bsi
= gsi_after_labels (gimple_bb (use
->stmt
));
5472 tgt
= gimple_assign_lhs (use
->stmt
);
5473 bsi
= gsi_for_stmt (use
->stmt
);
5480 op
= force_gimple_operand_gsi (&bsi
, comp
, false, SSA_NAME_VAR (tgt
),
5481 true, GSI_SAME_STMT
);
5483 if (gimple_code (use
->stmt
) == GIMPLE_PHI
)
5485 ass
= gimple_build_assign (tgt
, op
);
5486 gsi_insert_before (&bsi
, ass
, GSI_SAME_STMT
);
5488 bsi
= gsi_for_stmt (use
->stmt
);
5489 remove_phi_node (&bsi
, false);
5493 gimple_assign_set_rhs_from_tree (&bsi
, op
);
5494 use
->stmt
= gsi_stmt (bsi
);
5498 /* Replaces ssa name in index IDX by its basic variable. Callback for
5502 idx_remove_ssa_names (tree base
, tree
*idx
,
5503 void *data ATTRIBUTE_UNUSED
)
5507 if (TREE_CODE (*idx
) == SSA_NAME
)
5508 *idx
= SSA_NAME_VAR (*idx
);
5510 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
5512 op
= &TREE_OPERAND (base
, 2);
5514 && TREE_CODE (*op
) == SSA_NAME
)
5515 *op
= SSA_NAME_VAR (*op
);
5516 op
= &TREE_OPERAND (base
, 3);
5518 && TREE_CODE (*op
) == SSA_NAME
)
5519 *op
= SSA_NAME_VAR (*op
);
5525 /* Unshares REF and replaces ssa names inside it by their basic variables. */
5528 unshare_and_remove_ssa_names (tree ref
)
5530 ref
= unshare_expr (ref
);
5531 for_each_index (&ref
, idx_remove_ssa_names
, NULL
);
5536 /* Copies the reference information from OLD_REF to NEW_REF. */
5539 copy_ref_info (tree new_ref
, tree old_ref
)
5541 if (TREE_CODE (old_ref
) == TARGET_MEM_REF
)
5542 copy_mem_ref_info (new_ref
, old_ref
);
5545 TMR_ORIGINAL (new_ref
) = unshare_and_remove_ssa_names (old_ref
);
5546 TREE_SIDE_EFFECTS (new_ref
) = TREE_SIDE_EFFECTS (old_ref
);
5547 TREE_THIS_VOLATILE (new_ref
) = TREE_THIS_VOLATILE (old_ref
);
5551 /* Rewrites USE (address that is an iv) using candidate CAND. */
5554 rewrite_use_address (struct ivopts_data
*data
,
5555 struct iv_use
*use
, struct iv_cand
*cand
)
5558 gimple_stmt_iterator bsi
= gsi_for_stmt (use
->stmt
);
5559 tree base_hint
= NULL_TREE
;
5563 ok
= get_computation_aff (data
->current_loop
, use
, cand
, use
->stmt
, &aff
);
5565 unshare_aff_combination (&aff
);
5567 /* To avoid undefined overflow problems, all IV candidates use unsigned
5568 integer types. The drawback is that this makes it impossible for
5569 create_mem_ref to distinguish an IV that is based on a memory object
5570 from one that represents simply an offset.
5572 To work around this problem, we pass a hint to create_mem_ref that
5573 indicates which variable (if any) in aff is an IV based on a memory
5574 object. Note that we only consider the candidate. If this is not
5575 based on an object, the base of the reference is in some subexpression
5576 of the use -- but these will use pointer types, so they are recognized
5577 by the create_mem_ref heuristics anyway. */
5578 if (cand
->iv
->base_object
)
5579 base_hint
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
5581 ref
= create_mem_ref (&bsi
, TREE_TYPE (*use
->op_p
), &aff
, base_hint
,
5583 copy_ref_info (ref
, *use
->op_p
);
5587 /* Rewrites USE (the condition such that one of the arguments is an iv) using
5591 rewrite_use_compare (struct ivopts_data
*data
,
5592 struct iv_use
*use
, struct iv_cand
*cand
)
5594 tree comp
, *var_p
, op
, bound
;
5595 gimple_stmt_iterator bsi
= gsi_for_stmt (use
->stmt
);
5596 enum tree_code compare
;
5597 struct cost_pair
*cp
= get_use_iv_cost (data
, use
, cand
);
5603 tree var
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
5604 tree var_type
= TREE_TYPE (var
);
5607 compare
= iv_elimination_compare (data
, use
);
5608 bound
= unshare_expr (fold_convert (var_type
, bound
));
5609 op
= force_gimple_operand (bound
, &stmts
, true, NULL_TREE
);
5611 gsi_insert_seq_on_edge_immediate (
5612 loop_preheader_edge (data
->current_loop
),
5615 gimple_cond_set_lhs (use
->stmt
, var
);
5616 gimple_cond_set_code (use
->stmt
, compare
);
5617 gimple_cond_set_rhs (use
->stmt
, op
);
5621 /* The induction variable elimination failed; just express the original
5623 comp
= get_computation (data
->current_loop
, use
, cand
);
5624 gcc_assert (comp
!= NULL_TREE
);
5626 ok
= extract_cond_operands (data
, use
->stmt
, &var_p
, NULL
, NULL
, NULL
);
5629 *var_p
= force_gimple_operand_gsi (&bsi
, comp
, true, SSA_NAME_VAR (*var_p
),
5630 true, GSI_SAME_STMT
);
5633 /* Rewrites USE using candidate CAND. */
5636 rewrite_use (struct ivopts_data
*data
, struct iv_use
*use
, struct iv_cand
*cand
)
5640 case USE_NONLINEAR_EXPR
:
5641 rewrite_use_nonlinear_expr (data
, use
, cand
);
5645 rewrite_use_address (data
, use
, cand
);
5649 rewrite_use_compare (data
, use
, cand
);
5656 update_stmt (use
->stmt
);
5659 /* Rewrite the uses using the selected induction variables. */
5662 rewrite_uses (struct ivopts_data
*data
)
5665 struct iv_cand
*cand
;
5668 for (i
= 0; i
< n_iv_uses (data
); i
++)
5670 use
= iv_use (data
, i
);
5671 cand
= use
->selected
;
5674 rewrite_use (data
, use
, cand
);
5678 /* Removes the ivs that are not used after rewriting. */
5681 remove_unused_ivs (struct ivopts_data
*data
)
5685 bitmap toremove
= BITMAP_ALLOC (NULL
);
5687 /* Figure out an order in which to release SSA DEFs so that we don't
5688 release something that we'd have to propagate into a debug stmt
5690 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
5692 struct version_info
*info
;
5694 info
= ver_info (data
, j
);
5696 && !integer_zerop (info
->iv
->step
)
5698 && !info
->iv
->have_use_for
5699 && !info
->preserve_biv
)
5700 bitmap_set_bit (toremove
, SSA_NAME_VERSION (info
->iv
->ssa_name
));
5703 release_defs_bitset (toremove
);
5705 BITMAP_FREE (toremove
);
5708 /* Frees data allocated by the optimization of a single loop. */
5711 free_loop_data (struct ivopts_data
*data
)
5719 pointer_map_destroy (data
->niters
);
5720 data
->niters
= NULL
;
5723 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
5725 struct version_info
*info
;
5727 info
= ver_info (data
, i
);
5731 info
->has_nonlin_use
= false;
5732 info
->preserve_biv
= false;
5735 bitmap_clear (data
->relevant
);
5736 bitmap_clear (data
->important_candidates
);
5738 for (i
= 0; i
< n_iv_uses (data
); i
++)
5740 struct iv_use
*use
= iv_use (data
, i
);
5743 BITMAP_FREE (use
->related_cands
);
5744 for (j
= 0; j
< use
->n_map_members
; j
++)
5745 if (use
->cost_map
[j
].depends_on
)
5746 BITMAP_FREE (use
->cost_map
[j
].depends_on
);
5747 free (use
->cost_map
);
5750 VEC_truncate (iv_use_p
, data
->iv_uses
, 0);
5752 for (i
= 0; i
< n_iv_cands (data
); i
++)
5754 struct iv_cand
*cand
= iv_cand (data
, i
);
5758 if (cand
->depends_on
)
5759 BITMAP_FREE (cand
->depends_on
);
5762 VEC_truncate (iv_cand_p
, data
->iv_candidates
, 0);
5764 if (data
->version_info_size
< num_ssa_names
)
5766 data
->version_info_size
= 2 * num_ssa_names
;
5767 free (data
->version_info
);
5768 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
5771 data
->max_inv_id
= 0;
5773 for (i
= 0; VEC_iterate (tree
, decl_rtl_to_reset
, i
, obj
); i
++)
5774 SET_DECL_RTL (obj
, NULL_RTX
);
5776 VEC_truncate (tree
, decl_rtl_to_reset
, 0);
5779 /* Finalizes data structures used by the iv optimization pass. LOOPS is the
5783 tree_ssa_iv_optimize_finalize (struct ivopts_data
*data
)
5785 free_loop_data (data
);
5786 free (data
->version_info
);
5787 BITMAP_FREE (data
->relevant
);
5788 BITMAP_FREE (data
->important_candidates
);
5790 VEC_free (tree
, heap
, decl_rtl_to_reset
);
5791 VEC_free (iv_use_p
, heap
, data
->iv_uses
);
5792 VEC_free (iv_cand_p
, heap
, data
->iv_candidates
);
5795 /* Optimizes the LOOP. Returns true if anything changed. */
5798 tree_ssa_iv_optimize_loop (struct ivopts_data
*data
, struct loop
*loop
)
5800 bool changed
= false;
5801 struct iv_ca
*iv_ca
;
5805 gcc_assert (!data
->niters
);
5806 data
->current_loop
= loop
;
5807 data
->speed
= optimize_loop_for_speed_p (loop
);
5809 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5811 fprintf (dump_file
, "Processing loop %d\n", loop
->num
);
5813 exit
= single_dom_exit (loop
);
5816 fprintf (dump_file
, " single exit %d -> %d, exit condition ",
5817 exit
->src
->index
, exit
->dest
->index
);
5818 print_gimple_stmt (dump_file
, last_stmt (exit
->src
), 0, TDF_SLIM
);
5819 fprintf (dump_file
, "\n");
5822 fprintf (dump_file
, "\n");
5825 body
= get_loop_body (loop
);
5826 renumber_gimple_stmt_uids_in_blocks (body
, loop
->num_nodes
);
5829 /* For each ssa name determines whether it behaves as an induction variable
5831 if (!find_induction_variables (data
))
5834 /* Finds interesting uses (item 1). */
5835 find_interesting_uses (data
);
5836 if (n_iv_uses (data
) > MAX_CONSIDERED_USES
)
5839 /* Finds candidates for the induction variables (item 2). */
5840 find_iv_candidates (data
);
5842 /* Calculates the costs (item 3, part 1). */
5843 determine_iv_costs (data
);
5844 determine_use_iv_costs (data
);
5845 determine_set_costs (data
);
5847 /* Find the optimal set of induction variables (item 3, part 2). */
5848 iv_ca
= find_optimal_iv_set (data
);
5853 /* Create the new induction variables (item 4, part 1). */
5854 create_new_ivs (data
, iv_ca
);
5855 iv_ca_free (&iv_ca
);
5857 /* Rewrite the uses (item 4, part 2). */
5858 rewrite_uses (data
);
5860 /* Remove the ivs that are unused after rewriting. */
5861 remove_unused_ivs (data
);
5863 /* We have changed the structure of induction variables; it might happen
5864 that definitions in the scev database refer to some of them that were
5869 free_loop_data (data
);
5874 /* Main entry point. Optimizes induction variables in loops. */
5877 tree_ssa_iv_optimize (void)
5880 struct ivopts_data data
;
5883 tree_ssa_iv_optimize_init (&data
);
5885 /* Optimize the loops starting with the innermost ones. */
5886 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
5888 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5889 flow_loop_dump (loop
, dump_file
, NULL
, 1);
5891 tree_ssa_iv_optimize_loop (&data
, loop
);
5894 tree_ssa_iv_optimize_finalize (&data
);