1 /* Induction variable optimizations.
2 Copyright (C) 2003, 2004 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
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"
72 #include "hard-reg-set.h"
73 #include "basic-block.h"
75 #include "diagnostic.h"
76 #include "tree-flow.h"
77 #include "tree-dump.h"
82 #include "tree-pass.h"
84 #include "insn-config.h"
87 #include "tree-chrec.h"
88 #include "tree-scalar-evolution.h"
92 /* The infinite cost. */
93 #define INFTY 10000000
95 /* The expected number of loop iterations. TODO -- use profiling instead of
97 #define AVG_LOOP_NITER(LOOP) 5
99 /* Just to shorten the ugly names. */
100 #define EXEC_BINARY nondestructive_fold_binary_to_constant
101 #define EXEC_UNARY nondestructive_fold_unary_to_constant
103 /* Representation of the induction variable. */
106 tree base
; /* Initial value of the iv. */
107 tree step
; /* Step of the iv (constant only). */
108 tree ssa_name
; /* The ssa name with the value. */
109 bool biv_p
; /* Is it a biv? */
110 bool have_use_for
; /* Do we already have a use for it? */
111 unsigned use_id
; /* The identifier in the use if it is the case. */
114 /* Per-ssa version information (induction variable descriptions, etc.). */
117 tree name
; /* The ssa name. */
118 struct iv
*iv
; /* Induction variable description. */
119 bool has_nonlin_use
; /* For a loop-level invariant, whether it is used in
120 an expression that is not an induction variable. */
121 unsigned inv_id
; /* Id of an invariant. */
122 bool preserve_biv
; /* For the original biv, whether to preserve it. */
125 /* Information attached to loop. */
128 struct tree_niter_desc niter
;
129 /* Number of iterations. */
131 unsigned regs_used
; /* Number of registers used. */
137 USE_NONLINEAR_EXPR
, /* Use in a nonlinear expression. */
138 USE_OUTER
, /* The induction variable is used outside the loop. */
139 USE_ADDRESS
, /* Use in an address. */
140 USE_COMPARE
/* Use is a compare. */
143 /* The candidate - cost pair. */
146 struct iv_cand
*cand
; /* The candidate. */
147 unsigned cost
; /* The cost. */
148 bitmap depends_on
; /* The list of invariants that have to be
155 unsigned id
; /* The id of the use. */
156 enum use_type type
; /* Type of the use. */
157 struct iv
*iv
; /* The induction variable it is based on. */
158 tree stmt
; /* Statement in that it occurs. */
159 tree
*op_p
; /* The place where it occurs. */
160 bitmap related_cands
; /* The set of "related" iv candidates. */
162 unsigned n_map_members
; /* Number of candidates in the cost_map list. */
163 struct cost_pair
*cost_map
;
164 /* The costs wrto the iv candidates. */
166 struct iv_cand
*selected
;
167 /* The selected candidate. */
170 /* The position where the iv is computed. */
173 IP_NORMAL
, /* At the end, just before the exit condition. */
174 IP_END
, /* At the end of the latch block. */
175 IP_ORIGINAL
/* The original biv. */
178 /* The induction variable candidate. */
181 unsigned id
; /* The number of the candidate. */
182 bool important
; /* Whether this is an "important" candidate, i.e. such
183 that it should be considered by all uses. */
184 enum iv_position pos
; /* Where it is computed. */
185 tree incremented_at
; /* For original biv, the statement where it is
187 tree var_before
; /* The variable used for it before increment. */
188 tree var_after
; /* The variable used for it after increment. */
189 struct iv
*iv
; /* The value of the candidate. NULL for
190 "pseudocandidate" used to indicate the possibility
191 to replace the final value of an iv by direct
192 computation of the value. */
193 unsigned cost
; /* Cost of the candidate. */
196 /* The data used by the induction variable optimizations. */
200 /* The currently optimized loop. */
201 struct loop
*current_loop
;
203 /* The size of version_info array allocated. */
204 unsigned version_info_size
;
206 /* The array of information for the ssa names. */
207 struct version_info
*version_info
;
209 /* The bitmap of indices in version_info whose value was changed. */
212 /* The maximum invariant id. */
215 /* The uses of induction variables. */
218 /* The candidates. */
219 varray_type iv_candidates
;
221 /* Whether to consider just related and important candidates when replacing a
223 bool consider_all_candidates
;
226 /* Bound on number of candidates below that all candidates are considered. */
228 #define CONSIDER_ALL_CANDIDATES_BOUND \
229 ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
231 /* If there are more iv occurrences, we just give up (it is quite unlikely that
232 optimizing such a loop would help, and it would take ages). */
234 #define MAX_CONSIDERED_USES \
235 ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
237 /* The list of trees for that the decl_rtl field must be reset is stored
240 static varray_type decl_rtl_to_reset
;
242 /* Number of uses recorded in DATA. */
244 static inline unsigned
245 n_iv_uses (struct ivopts_data
*data
)
247 return VARRAY_ACTIVE_SIZE (data
->iv_uses
);
250 /* Ith use recorded in DATA. */
252 static inline struct iv_use
*
253 iv_use (struct ivopts_data
*data
, unsigned i
)
255 return VARRAY_GENERIC_PTR_NOGC (data
->iv_uses
, i
);
258 /* Number of candidates recorded in DATA. */
260 static inline unsigned
261 n_iv_cands (struct ivopts_data
*data
)
263 return VARRAY_ACTIVE_SIZE (data
->iv_candidates
);
266 /* Ith candidate recorded in DATA. */
268 static inline struct iv_cand
*
269 iv_cand (struct ivopts_data
*data
, unsigned i
)
271 return VARRAY_GENERIC_PTR_NOGC (data
->iv_candidates
, i
);
274 /* The data for LOOP. */
276 static inline struct loop_data
*
277 loop_data (struct loop
*loop
)
282 /* The single loop exit if it dominates the latch, NULL otherwise. */
285 single_dom_exit (struct loop
*loop
)
287 edge exit
= loop
->single_exit
;
292 if (!just_once_each_iteration_p (loop
, exit
->src
))
298 /* Dumps information about the induction variable IV to FILE. */
300 extern void dump_iv (FILE *, struct iv
*);
302 dump_iv (FILE *file
, struct iv
*iv
)
304 fprintf (file
, "ssa name ");
305 print_generic_expr (file
, iv
->ssa_name
, TDF_SLIM
);
306 fprintf (file
, "\n");
308 fprintf (file
, " type ");
309 print_generic_expr (file
, TREE_TYPE (iv
->base
), TDF_SLIM
);
310 fprintf (file
, "\n");
314 fprintf (file
, " base ");
315 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
316 fprintf (file
, "\n");
318 fprintf (file
, " step ");
319 print_generic_expr (file
, iv
->step
, TDF_SLIM
);
320 fprintf (file
, "\n");
324 fprintf (file
, " invariant ");
325 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
326 fprintf (file
, "\n");
330 fprintf (file
, " is a biv\n");
333 /* Dumps information about the USE to FILE. */
335 extern void dump_use (FILE *, struct iv_use
*);
337 dump_use (FILE *file
, struct iv_use
*use
)
339 struct iv
*iv
= use
->iv
;
341 fprintf (file
, "use %d\n", use
->id
);
345 case USE_NONLINEAR_EXPR
:
346 fprintf (file
, " generic\n");
350 fprintf (file
, " outside\n");
354 fprintf (file
, " address\n");
358 fprintf (file
, " compare\n");
365 fprintf (file
, " in statement ");
366 print_generic_expr (file
, use
->stmt
, TDF_SLIM
);
367 fprintf (file
, "\n");
369 fprintf (file
, " at position ");
371 print_generic_expr (file
, *use
->op_p
, TDF_SLIM
);
372 fprintf (file
, "\n");
374 fprintf (file
, " type ");
375 print_generic_expr (file
, TREE_TYPE (iv
->base
), TDF_SLIM
);
376 fprintf (file
, "\n");
380 fprintf (file
, " base ");
381 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
382 fprintf (file
, "\n");
384 fprintf (file
, " step ");
385 print_generic_expr (file
, iv
->step
, TDF_SLIM
);
386 fprintf (file
, "\n");
390 fprintf (file
, " invariant ");
391 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
392 fprintf (file
, "\n");
395 fprintf (file
, " related candidates ");
396 dump_bitmap (file
, use
->related_cands
);
399 /* Dumps information about the uses to FILE. */
401 extern void dump_uses (FILE *, struct ivopts_data
*);
403 dump_uses (FILE *file
, struct ivopts_data
*data
)
408 for (i
= 0; i
< n_iv_uses (data
); i
++)
410 use
= iv_use (data
, i
);
412 dump_use (file
, use
);
413 fprintf (file
, "\n");
417 /* Dumps information about induction variable candidate CAND to FILE. */
419 extern void dump_cand (FILE *, struct iv_cand
*);
421 dump_cand (FILE *file
, struct iv_cand
*cand
)
423 struct iv
*iv
= cand
->iv
;
425 fprintf (file
, "candidate %d%s\n",
426 cand
->id
, cand
->important
? " (important)" : "");
430 fprintf (file
, " final value replacement\n");
437 fprintf (file
, " incremented before exit test\n");
441 fprintf (file
, " incremented at end\n");
445 fprintf (file
, " original biv\n");
449 fprintf (file
, " type ");
450 print_generic_expr (file
, TREE_TYPE (iv
->base
), TDF_SLIM
);
451 fprintf (file
, "\n");
455 fprintf (file
, " base ");
456 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
457 fprintf (file
, "\n");
459 fprintf (file
, " step ");
460 print_generic_expr (file
, iv
->step
, TDF_SLIM
);
461 fprintf (file
, "\n");
465 fprintf (file
, " invariant ");
466 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
467 fprintf (file
, "\n");
471 /* Returns the info for ssa version VER. */
473 static inline struct version_info
*
474 ver_info (struct ivopts_data
*data
, unsigned ver
)
476 return data
->version_info
+ ver
;
479 /* Returns the info for ssa name NAME. */
481 static inline struct version_info
*
482 name_info (struct ivopts_data
*data
, tree name
)
484 return ver_info (data
, SSA_NAME_VERSION (name
));
487 /* Checks whether there exists number X such that X * B = A, counting modulo
491 divide (unsigned bits
, unsigned HOST_WIDE_INT a
, unsigned HOST_WIDE_INT b
,
494 unsigned HOST_WIDE_INT mask
= ~(~(unsigned HOST_WIDE_INT
) 0 << (bits
- 1) << 1);
495 unsigned HOST_WIDE_INT inv
, ex
, val
;
501 /* First divide the whole equation by 2 as long as possible. */
502 while (!(a
& 1) && !(b
& 1))
512 /* If b is still even, a is odd and there is no such x. */
516 /* Find the inverse of b. We compute it as
517 b^(2^(bits - 1) - 1) (mod 2^bits). */
520 for (i
= 0; i
< bits
- 1; i
++)
522 inv
= (inv
* ex
) & mask
;
523 ex
= (ex
* ex
) & mask
;
526 val
= (a
* inv
) & mask
;
528 gcc_assert (((val
* b
) & mask
) == a
);
530 if ((val
>> (bits
- 1)) & 1)
538 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
542 stmt_after_ip_normal_pos (struct loop
*loop
, tree stmt
)
544 basic_block bb
= ip_normal_pos (loop
), sbb
= bb_for_stmt (stmt
);
548 if (sbb
== loop
->latch
)
554 return stmt
== last_stmt (bb
);
557 /* Returns true if STMT if after the place where the original induction
558 variable CAND is incremented. */
561 stmt_after_ip_original_pos (struct iv_cand
*cand
, tree stmt
)
563 basic_block cand_bb
= bb_for_stmt (cand
->incremented_at
);
564 basic_block stmt_bb
= bb_for_stmt (stmt
);
565 block_stmt_iterator bsi
;
567 if (!dominated_by_p (CDI_DOMINATORS
, stmt_bb
, cand_bb
))
570 if (stmt_bb
!= cand_bb
)
573 /* Scan the block from the end, since the original ivs are usually
574 incremented at the end of the loop body. */
575 for (bsi
= bsi_last (stmt_bb
); ; bsi_prev (&bsi
))
577 if (bsi_stmt (bsi
) == cand
->incremented_at
)
579 if (bsi_stmt (bsi
) == stmt
)
584 /* Returns true if STMT if after the place where the induction variable
585 CAND is incremented in LOOP. */
588 stmt_after_increment (struct loop
*loop
, struct iv_cand
*cand
, tree stmt
)
596 return stmt_after_ip_normal_pos (loop
, stmt
);
599 return stmt_after_ip_original_pos (cand
, stmt
);
606 /* Initializes data structures used by the iv optimization pass, stored
607 in DATA. LOOPS is the loop tree. */
610 tree_ssa_iv_optimize_init (struct loops
*loops
, struct ivopts_data
*data
)
614 data
->version_info_size
= 2 * num_ssa_names
;
615 data
->version_info
= xcalloc (data
->version_info_size
,
616 sizeof (struct version_info
));
617 data
->relevant
= BITMAP_XMALLOC ();
618 data
->max_inv_id
= 0;
620 for (i
= 1; i
< loops
->num
; i
++)
621 if (loops
->parray
[i
])
622 loops
->parray
[i
]->aux
= xcalloc (1, sizeof (struct loop_data
));
624 VARRAY_GENERIC_PTR_NOGC_INIT (data
->iv_uses
, 20, "iv_uses");
625 VARRAY_GENERIC_PTR_NOGC_INIT (data
->iv_candidates
, 20, "iv_candidates");
626 VARRAY_GENERIC_PTR_NOGC_INIT (decl_rtl_to_reset
, 20, "decl_rtl_to_reset");
629 /* Allocates an induction variable with given initial value BASE and step STEP
633 alloc_iv (tree base
, tree step
)
635 struct iv
*iv
= xcalloc (1, sizeof (struct iv
));
637 if (step
&& integer_zerop (step
))
643 iv
->have_use_for
= false;
645 iv
->ssa_name
= NULL_TREE
;
650 /* Sets STEP and BASE for induction variable IV. */
653 set_iv (struct ivopts_data
*data
, tree iv
, tree base
, tree step
)
655 struct version_info
*info
= name_info (data
, iv
);
657 gcc_assert (!info
->iv
);
659 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (iv
));
660 info
->iv
= alloc_iv (base
, step
);
661 info
->iv
->ssa_name
= iv
;
664 /* Finds induction variable declaration for VAR. */
667 get_iv (struct ivopts_data
*data
, tree var
)
671 if (!name_info (data
, var
)->iv
)
673 bb
= bb_for_stmt (SSA_NAME_DEF_STMT (var
));
676 || !flow_bb_inside_loop_p (data
->current_loop
, bb
))
677 set_iv (data
, var
, var
, NULL_TREE
);
680 return name_info (data
, var
)->iv
;
683 /* Determines the step of a biv defined in PHI. */
686 determine_biv_step (tree phi
)
688 struct loop
*loop
= bb_for_stmt (phi
)->loop_father
;
689 tree name
= PHI_RESULT (phi
), base
, step
;
690 tree type
= TREE_TYPE (name
);
692 if (!is_gimple_reg (name
))
695 if (!simple_iv (loop
, phi
, name
, &base
, &step
))
699 return build_int_cst (type
, 0);
704 /* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
707 abnormal_ssa_name_p (tree exp
)
712 if (TREE_CODE (exp
) != SSA_NAME
)
715 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
) != 0;
718 /* Returns false if BASE or INDEX contains a ssa name that occurs in an
719 abnormal phi node. Callback for for_each_index. */
722 idx_contains_abnormal_ssa_name_p (tree base
, tree
*index
,
723 void *data ATTRIBUTE_UNUSED
)
725 if (TREE_CODE (base
) == ARRAY_REF
)
727 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 2)))
729 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 3)))
733 return !abnormal_ssa_name_p (*index
);
736 /* Returns true if EXPR contains a ssa name that occurs in an
737 abnormal phi node. */
740 contains_abnormal_ssa_name_p (tree expr
)
742 enum tree_code code
= TREE_CODE (expr
);
743 enum tree_code_class
class = TREE_CODE_CLASS (code
);
745 if (code
== SSA_NAME
)
746 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr
) != 0;
748 if (code
== INTEGER_CST
749 || is_gimple_min_invariant (expr
))
752 if (code
== ADDR_EXPR
)
753 return !for_each_index (&TREE_OPERAND (expr
, 1),
754 idx_contains_abnormal_ssa_name_p
,
761 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1)))
766 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0)))
778 /* Finds basic ivs. */
781 find_bivs (struct ivopts_data
*data
)
783 tree phi
, step
, type
, base
;
785 struct loop
*loop
= data
->current_loop
;
787 for (phi
= phi_nodes (loop
->header
); phi
; phi
= TREE_CHAIN (phi
))
789 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
792 step
= determine_biv_step (phi
);
796 if (cst_and_fits_in_hwi (step
)
797 && int_cst_value (step
) == 0)
800 base
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
801 if (contains_abnormal_ssa_name_p (base
))
804 type
= TREE_TYPE (PHI_RESULT (phi
));
805 base
= fold_convert (type
, base
);
806 step
= fold_convert (type
, step
);
808 /* FIXME: We do not handle induction variables whose step does
809 not satisfy cst_and_fits_in_hwi. */
810 if (!cst_and_fits_in_hwi (step
))
813 set_iv (data
, PHI_RESULT (phi
), base
, step
);
820 /* Marks basic ivs. */
823 mark_bivs (struct ivopts_data
*data
)
826 struct iv
*iv
, *incr_iv
;
827 struct loop
*loop
= data
->current_loop
;
830 for (phi
= phi_nodes (loop
->header
); phi
; phi
= TREE_CHAIN (phi
))
832 iv
= get_iv (data
, PHI_RESULT (phi
));
836 var
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
837 incr_iv
= get_iv (data
, var
);
841 /* If the increment is in the subloop, ignore it. */
842 incr_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (var
));
843 if (incr_bb
->loop_father
!= data
->current_loop
844 || (incr_bb
->flags
& BB_IRREDUCIBLE_LOOP
))
848 incr_iv
->biv_p
= true;
852 /* Checks whether STMT defines a linear induction variable and stores its
853 parameters to BASE and STEP. */
856 find_givs_in_stmt_scev (struct ivopts_data
*data
, tree stmt
,
857 tree
*base
, tree
*step
)
860 struct loop
*loop
= data
->current_loop
;
865 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
868 lhs
= TREE_OPERAND (stmt
, 0);
869 if (TREE_CODE (lhs
) != SSA_NAME
)
872 if (!simple_iv (loop
, stmt
, TREE_OPERAND (stmt
, 1), base
, step
))
875 /* FIXME: We do not handle induction variables whose step does
876 not satisfy cst_and_fits_in_hwi. */
878 && !cst_and_fits_in_hwi (*step
))
881 if (contains_abnormal_ssa_name_p (*base
))
887 /* Finds general ivs in statement STMT. */
890 find_givs_in_stmt (struct ivopts_data
*data
, tree stmt
)
894 if (!find_givs_in_stmt_scev (data
, stmt
, &base
, &step
))
897 set_iv (data
, TREE_OPERAND (stmt
, 0), base
, step
);
900 /* Finds general ivs in basic block BB. */
903 find_givs_in_bb (struct ivopts_data
*data
, basic_block bb
)
905 block_stmt_iterator bsi
;
907 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
908 find_givs_in_stmt (data
, bsi_stmt (bsi
));
911 /* Finds general ivs. */
914 find_givs (struct ivopts_data
*data
)
916 struct loop
*loop
= data
->current_loop
;
917 basic_block
*body
= get_loop_body_in_dom_order (loop
);
920 for (i
= 0; i
< loop
->num_nodes
; i
++)
921 find_givs_in_bb (data
, body
[i
]);
925 /* Determine the number of iterations of the current loop. */
928 determine_number_of_iterations (struct ivopts_data
*data
)
930 struct loop
*loop
= data
->current_loop
;
931 edge exit
= single_dom_exit (loop
);
936 number_of_iterations_exit (loop
, exit
, &loop_data (loop
)->niter
);
939 /* For each ssa name defined in LOOP determines whether it is an induction
940 variable and if so, its initial value and step. */
943 find_induction_variables (struct ivopts_data
*data
)
946 struct loop
*loop
= data
->current_loop
;
949 if (!find_bivs (data
))
954 determine_number_of_iterations (data
);
956 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
958 if (loop_data (loop
)->niter
.niter
)
960 fprintf (dump_file
, " number of iterations ");
961 print_generic_expr (dump_file
, loop_data (loop
)->niter
.niter
,
963 fprintf (dump_file
, "\n");
965 fprintf (dump_file
, " may be zero if ");
966 print_generic_expr (dump_file
, loop_data (loop
)->niter
.may_be_zero
,
968 fprintf (dump_file
, "\n");
970 fprintf (dump_file
, " bogus unless ");
971 print_generic_expr (dump_file
, loop_data (loop
)->niter
.assumptions
,
973 fprintf (dump_file
, "\n");
974 fprintf (dump_file
, "\n");
977 fprintf (dump_file
, "Induction variables:\n\n");
979 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
981 if (ver_info (data
, i
)->iv
)
982 dump_iv (dump_file
, ver_info (data
, i
)->iv
);
989 /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV. */
991 static struct iv_use
*
992 record_use (struct ivopts_data
*data
, tree
*use_p
, struct iv
*iv
,
993 tree stmt
, enum use_type use_type
)
995 struct iv_use
*use
= xcalloc (1, sizeof (struct iv_use
));
997 use
->id
= n_iv_uses (data
);
998 use
->type
= use_type
;
1002 use
->related_cands
= BITMAP_XMALLOC ();
1004 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1005 dump_use (dump_file
, use
);
1007 VARRAY_PUSH_GENERIC_PTR_NOGC (data
->iv_uses
, use
);
1012 /* Checks whether OP is a loop-level invariant and if so, records it.
1013 NONLINEAR_USE is true if the invariant is used in a way we do not
1014 handle specially. */
1017 record_invariant (struct ivopts_data
*data
, tree op
, bool nonlinear_use
)
1020 struct version_info
*info
;
1022 if (TREE_CODE (op
) != SSA_NAME
1023 || !is_gimple_reg (op
))
1026 bb
= bb_for_stmt (SSA_NAME_DEF_STMT (op
));
1028 && flow_bb_inside_loop_p (data
->current_loop
, bb
))
1031 info
= name_info (data
, op
);
1033 info
->has_nonlin_use
|= nonlinear_use
;
1035 info
->inv_id
= ++data
->max_inv_id
;
1036 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (op
));
1039 /* Checks whether the use OP is interesting and if so, records it
1042 static struct iv_use
*
1043 find_interesting_uses_outer_or_nonlin (struct ivopts_data
*data
, tree op
,
1051 if (TREE_CODE (op
) != SSA_NAME
)
1054 iv
= get_iv (data
, op
);
1058 if (iv
->have_use_for
)
1060 use
= iv_use (data
, iv
->use_id
);
1062 gcc_assert (use
->type
== USE_NONLINEAR_EXPR
1063 || use
->type
== USE_OUTER
);
1065 if (type
== USE_NONLINEAR_EXPR
)
1066 use
->type
= USE_NONLINEAR_EXPR
;
1070 if (zero_p (iv
->step
))
1072 record_invariant (data
, op
, true);
1075 iv
->have_use_for
= true;
1077 civ
= xmalloc (sizeof (struct iv
));
1080 stmt
= SSA_NAME_DEF_STMT (op
);
1081 gcc_assert (TREE_CODE (stmt
) == PHI_NODE
1082 || TREE_CODE (stmt
) == MODIFY_EXPR
);
1084 use
= record_use (data
, NULL
, civ
, stmt
, type
);
1085 iv
->use_id
= use
->id
;
1090 /* Checks whether the use OP is interesting and if so, records it. */
1092 static struct iv_use
*
1093 find_interesting_uses_op (struct ivopts_data
*data
, tree op
)
1095 return find_interesting_uses_outer_or_nonlin (data
, op
, USE_NONLINEAR_EXPR
);
1098 /* Records a definition of induction variable OP that is used outside of the
1101 static struct iv_use
*
1102 find_interesting_uses_outer (struct ivopts_data
*data
, tree op
)
1104 return find_interesting_uses_outer_or_nonlin (data
, op
, USE_OUTER
);
1107 /* Checks whether the condition *COND_P in STMT is interesting
1108 and if so, records it. */
1111 find_interesting_uses_cond (struct ivopts_data
*data
, tree stmt
, tree
*cond_p
)
1115 struct iv
*iv0
= NULL
, *iv1
= NULL
, *civ
;
1117 tree zero
= integer_zero_node
;
1119 const_iv
.step
= NULL_TREE
;
1121 if (integer_zerop (*cond_p
)
1122 || integer_nonzerop (*cond_p
))
1125 if (TREE_CODE (*cond_p
) == SSA_NAME
)
1132 op0_p
= &TREE_OPERAND (*cond_p
, 0);
1133 op1_p
= &TREE_OPERAND (*cond_p
, 1);
1136 if (TREE_CODE (*op0_p
) == SSA_NAME
)
1137 iv0
= get_iv (data
, *op0_p
);
1141 if (TREE_CODE (*op1_p
) == SSA_NAME
)
1142 iv1
= get_iv (data
, *op1_p
);
1146 if (/* When comparing with non-invariant value, we may not do any senseful
1147 induction variable elimination. */
1149 /* Eliminating condition based on two ivs would be nontrivial.
1150 ??? TODO -- it is not really important to handle this case. */
1151 || (!zero_p (iv0
->step
) && !zero_p (iv1
->step
)))
1153 find_interesting_uses_op (data
, *op0_p
);
1154 find_interesting_uses_op (data
, *op1_p
);
1158 if (zero_p (iv0
->step
) && zero_p (iv1
->step
))
1160 /* If both are invariants, this is a work for unswitching. */
1164 civ
= xmalloc (sizeof (struct iv
));
1165 *civ
= zero_p (iv0
->step
) ? *iv1
: *iv0
;
1166 record_use (data
, cond_p
, civ
, stmt
, USE_COMPARE
);
1169 /* Returns true if expression EXPR is obviously invariant in LOOP,
1170 i.e. if all its operands are defined outside of the LOOP. */
1173 expr_invariant_in_loop_p (struct loop
*loop
, tree expr
)
1178 if (is_gimple_min_invariant (expr
))
1181 if (TREE_CODE (expr
) == SSA_NAME
)
1183 def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (expr
));
1185 && flow_bb_inside_loop_p (loop
, def_bb
))
1194 len
= first_rtl_op (TREE_CODE (expr
));
1195 for (i
= 0; i
< len
; i
++)
1196 if (!expr_invariant_in_loop_p (loop
, TREE_OPERAND (expr
, i
)))
1202 /* Cumulates the steps of indices into DATA and replaces their values with the
1203 initial ones. Returns false when the value of the index cannot be determined.
1204 Callback for for_each_index. */
1206 struct ifs_ivopts_data
1208 struct ivopts_data
*ivopts_data
;
1214 idx_find_step (tree base
, tree
*idx
, void *data
)
1216 struct ifs_ivopts_data
*dta
= data
;
1218 tree step
, type
, iv_type
, iv_step
, lbound
, off
;
1219 struct loop
*loop
= dta
->ivopts_data
->current_loop
;
1221 if (TREE_CODE (base
) == MISALIGNED_INDIRECT_REF
1222 || TREE_CODE (base
) == ALIGN_INDIRECT_REF
)
1225 /* If base is a component ref, require that the offset of the reference
1227 if (TREE_CODE (base
) == COMPONENT_REF
)
1229 off
= component_ref_field_offset (base
);
1230 return expr_invariant_in_loop_p (loop
, off
);
1233 /* If base is array, first check whether we will be able to move the
1234 reference out of the loop (in order to take its address in strength
1235 reduction). In order for this to work we need both lower bound
1236 and step to be loop invariants. */
1237 if (TREE_CODE (base
) == ARRAY_REF
)
1239 step
= array_ref_element_size (base
);
1240 lbound
= array_ref_low_bound (base
);
1242 if (!expr_invariant_in_loop_p (loop
, step
)
1243 || !expr_invariant_in_loop_p (loop
, lbound
))
1247 if (TREE_CODE (*idx
) != SSA_NAME
)
1250 iv
= get_iv (dta
->ivopts_data
, *idx
);
1259 iv_type
= TREE_TYPE (iv
->base
);
1260 type
= build_pointer_type (TREE_TYPE (base
));
1261 if (TREE_CODE (base
) == ARRAY_REF
)
1263 step
= array_ref_element_size (base
);
1265 /* We only handle addresses whose step is an integer constant. */
1266 if (TREE_CODE (step
) != INTEGER_CST
)
1270 /* The step for pointer arithmetics already is 1 byte. */
1271 step
= build_int_cst (type
, 1);
1273 if (TYPE_PRECISION (iv_type
) < TYPE_PRECISION (type
))
1274 iv_step
= can_count_iv_in_wider_type (dta
->ivopts_data
->current_loop
,
1275 type
, iv
->base
, iv
->step
, dta
->stmt
);
1277 iv_step
= fold_convert (iv_type
, iv
->step
);
1281 /* The index might wrap. */
1285 step
= EXEC_BINARY (MULT_EXPR
, type
, step
, iv_step
);
1288 *dta
->step_p
= step
;
1290 *dta
->step_p
= EXEC_BINARY (PLUS_EXPR
, type
, *dta
->step_p
, step
);
1295 /* Records use in index IDX. Callback for for_each_index. Ivopts data
1296 object is passed to it in DATA. */
1299 idx_record_use (tree base
, tree
*idx
,
1302 find_interesting_uses_op (data
, *idx
);
1303 if (TREE_CODE (base
) == ARRAY_REF
)
1305 find_interesting_uses_op (data
, array_ref_element_size (base
));
1306 find_interesting_uses_op (data
, array_ref_low_bound (base
));
1311 /* Finds addresses in *OP_P inside STMT. */
1314 find_interesting_uses_address (struct ivopts_data
*data
, tree stmt
, tree
*op_p
)
1316 tree base
= unshare_expr (*op_p
), step
= NULL
;
1318 struct ifs_ivopts_data ifs_ivopts_data
;
1320 /* Ignore bitfields for now. Not really something terribly complicated
1322 if (TREE_CODE (base
) == COMPONENT_REF
1323 && DECL_NONADDRESSABLE_P (TREE_OPERAND (base
, 1)))
1326 ifs_ivopts_data
.ivopts_data
= data
;
1327 ifs_ivopts_data
.stmt
= stmt
;
1328 ifs_ivopts_data
.step_p
= &step
;
1329 if (!for_each_index (&base
, idx_find_step
, &ifs_ivopts_data
)
1333 gcc_assert (TREE_CODE (base
) != ALIGN_INDIRECT_REF
);
1334 gcc_assert (TREE_CODE (base
) != MISALIGNED_INDIRECT_REF
);
1336 if (TREE_CODE (base
) == INDIRECT_REF
)
1337 base
= TREE_OPERAND (base
, 0);
1339 base
= build_addr (base
);
1341 civ
= alloc_iv (base
, step
);
1342 record_use (data
, op_p
, civ
, stmt
, USE_ADDRESS
);
1346 for_each_index (op_p
, idx_record_use
, data
);
1349 /* Finds and records invariants used in STMT. */
1352 find_invariants_stmt (struct ivopts_data
*data
, tree stmt
)
1354 use_optype uses
= NULL
;
1358 if (TREE_CODE (stmt
) == PHI_NODE
)
1359 n
= PHI_NUM_ARGS (stmt
);
1362 get_stmt_operands (stmt
);
1363 uses
= STMT_USE_OPS (stmt
);
1364 n
= NUM_USES (uses
);
1367 for (i
= 0; i
< n
; i
++)
1369 if (TREE_CODE (stmt
) == PHI_NODE
)
1370 op
= PHI_ARG_DEF (stmt
, i
);
1372 op
= USE_OP (uses
, i
);
1374 record_invariant (data
, op
, false);
1378 /* Finds interesting uses of induction variables in the statement STMT. */
1381 find_interesting_uses_stmt (struct ivopts_data
*data
, tree stmt
)
1385 use_optype uses
= NULL
;
1388 find_invariants_stmt (data
, stmt
);
1390 if (TREE_CODE (stmt
) == COND_EXPR
)
1392 find_interesting_uses_cond (data
, stmt
, &COND_EXPR_COND (stmt
));
1396 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
1398 lhs
= TREE_OPERAND (stmt
, 0);
1399 rhs
= TREE_OPERAND (stmt
, 1);
1401 if (TREE_CODE (lhs
) == SSA_NAME
)
1403 /* If the statement defines an induction variable, the uses are not
1404 interesting by themselves. */
1406 iv
= get_iv (data
, lhs
);
1408 if (iv
&& !zero_p (iv
->step
))
1412 switch (TREE_CODE_CLASS (TREE_CODE (rhs
)))
1414 case tcc_comparison
:
1415 find_interesting_uses_cond (data
, stmt
, &TREE_OPERAND (stmt
, 1));
1419 find_interesting_uses_address (data
, stmt
, &TREE_OPERAND (stmt
, 1));
1420 if (REFERENCE_CLASS_P (lhs
))
1421 find_interesting_uses_address (data
, stmt
, &TREE_OPERAND (stmt
, 0));
1427 if (REFERENCE_CLASS_P (lhs
)
1428 && is_gimple_val (rhs
))
1430 find_interesting_uses_address (data
, stmt
, &TREE_OPERAND (stmt
, 0));
1431 find_interesting_uses_op (data
, rhs
);
1435 /* TODO -- we should also handle address uses of type
1437 memory = call (whatever);
1444 if (TREE_CODE (stmt
) == PHI_NODE
1445 && bb_for_stmt (stmt
) == data
->current_loop
->header
)
1447 lhs
= PHI_RESULT (stmt
);
1448 iv
= get_iv (data
, lhs
);
1450 if (iv
&& !zero_p (iv
->step
))
1454 if (TREE_CODE (stmt
) == PHI_NODE
)
1455 n
= PHI_NUM_ARGS (stmt
);
1458 uses
= STMT_USE_OPS (stmt
);
1459 n
= NUM_USES (uses
);
1462 for (i
= 0; i
< n
; i
++)
1464 if (TREE_CODE (stmt
) == PHI_NODE
)
1465 op
= PHI_ARG_DEF (stmt
, i
);
1467 op
= USE_OP (uses
, i
);
1469 if (TREE_CODE (op
) != SSA_NAME
)
1472 iv
= get_iv (data
, op
);
1476 find_interesting_uses_op (data
, op
);
1480 /* Finds interesting uses of induction variables outside of loops
1481 on loop exit edge EXIT. */
1484 find_interesting_uses_outside (struct ivopts_data
*data
, edge exit
)
1488 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= TREE_CHAIN (phi
))
1490 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1491 find_interesting_uses_outer (data
, def
);
1495 /* Finds uses of the induction variables that are interesting. */
1498 find_interesting_uses (struct ivopts_data
*data
)
1501 block_stmt_iterator bsi
;
1503 basic_block
*body
= get_loop_body (data
->current_loop
);
1505 struct version_info
*info
;
1508 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1509 fprintf (dump_file
, "Uses:\n\n");
1511 for (i
= 0; i
< data
->current_loop
->num_nodes
; i
++)
1516 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1517 if (e
->dest
!= EXIT_BLOCK_PTR
1518 && !flow_bb_inside_loop_p (data
->current_loop
, e
->dest
))
1519 find_interesting_uses_outside (data
, e
);
1521 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
1522 find_interesting_uses_stmt (data
, phi
);
1523 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1524 find_interesting_uses_stmt (data
, bsi_stmt (bsi
));
1527 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1531 fprintf (dump_file
, "\n");
1533 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1535 info
= ver_info (data
, i
);
1538 fprintf (dump_file
, " ");
1539 print_generic_expr (dump_file
, info
->name
, TDF_SLIM
);
1540 fprintf (dump_file
, " is invariant (%d)%s\n",
1541 info
->inv_id
, info
->has_nonlin_use
? "" : ", eliminable");
1545 fprintf (dump_file
, "\n");
1551 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
1552 position to POS. If USE is not NULL, the candidate is set as related to
1553 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
1554 replacement of the final value of the iv by a direct computation. */
1556 static struct iv_cand
*
1557 add_candidate_1 (struct ivopts_data
*data
,
1558 tree base
, tree step
, bool important
, enum iv_position pos
,
1559 struct iv_use
*use
, tree incremented_at
)
1562 struct iv_cand
*cand
= NULL
;
1567 type
= TREE_TYPE (base
);
1568 if (!TYPE_UNSIGNED (type
))
1570 type
= unsigned_type_for (type
);
1571 base
= fold_convert (type
, base
);
1573 step
= fold_convert (type
, step
);
1577 for (i
= 0; i
< n_iv_cands (data
); i
++)
1579 cand
= iv_cand (data
, i
);
1581 if (cand
->pos
!= pos
)
1584 if (cand
->incremented_at
!= incremented_at
)
1598 if (!operand_equal_p (base
, cand
->iv
->base
, 0))
1601 if (zero_p (cand
->iv
->step
))
1608 if (step
&& operand_equal_p (step
, cand
->iv
->step
, 0))
1613 if (i
== n_iv_cands (data
))
1615 cand
= xcalloc (1, sizeof (struct iv_cand
));
1621 cand
->iv
= alloc_iv (base
, step
);
1624 if (pos
!= IP_ORIGINAL
&& cand
->iv
)
1626 cand
->var_before
= create_tmp_var_raw (TREE_TYPE (base
), "ivtmp");
1627 cand
->var_after
= cand
->var_before
;
1629 cand
->important
= important
;
1630 cand
->incremented_at
= incremented_at
;
1631 VARRAY_PUSH_GENERIC_PTR_NOGC (data
->iv_candidates
, cand
);
1633 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1634 dump_cand (dump_file
, cand
);
1637 if (important
&& !cand
->important
)
1639 cand
->important
= true;
1640 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1641 fprintf (dump_file
, "Candidate %d is important\n", cand
->id
);
1646 bitmap_set_bit (use
->related_cands
, i
);
1647 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1648 fprintf (dump_file
, "Candidate %d is related to use %d\n",
1655 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
1656 position to POS. If USE is not NULL, the candidate is set as related to
1657 it. The candidate computation is scheduled on all available positions. */
1660 add_candidate (struct ivopts_data
*data
,
1661 tree base
, tree step
, bool important
, struct iv_use
*use
)
1663 if (ip_normal_pos (data
->current_loop
))
1664 add_candidate_1 (data
, base
, step
, important
, IP_NORMAL
, use
, NULL_TREE
);
1665 if (ip_end_pos (data
->current_loop
))
1666 add_candidate_1 (data
, base
, step
, important
, IP_END
, use
, NULL_TREE
);
1669 /* Adds standard iv candidates. */
1672 add_standard_iv_candidates (struct ivopts_data
*data
)
1674 /* Add 0 + 1 * iteration candidate. */
1675 add_candidate (data
,
1676 build_int_cst (unsigned_intSI_type_node
, 0),
1677 build_int_cst (unsigned_intSI_type_node
, 1),
1680 /* The same for a long type if it is still fast enough. */
1681 if (BITS_PER_WORD
> 32)
1682 add_candidate (data
,
1683 build_int_cst (unsigned_intDI_type_node
, 0),
1684 build_int_cst (unsigned_intDI_type_node
, 1),
1689 /* Adds candidates bases on the old induction variable IV. */
1692 add_old_iv_candidates (struct ivopts_data
*data
, struct iv
*iv
)
1695 struct iv_cand
*cand
;
1697 add_candidate (data
, iv
->base
, iv
->step
, true, NULL
);
1699 /* The same, but with initial value zero. */
1700 add_candidate (data
,
1701 build_int_cst (TREE_TYPE (iv
->base
), 0),
1702 iv
->step
, true, NULL
);
1704 phi
= SSA_NAME_DEF_STMT (iv
->ssa_name
);
1705 if (TREE_CODE (phi
) == PHI_NODE
)
1707 /* Additionally record the possibility of leaving the original iv
1709 def
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (data
->current_loop
));
1710 cand
= add_candidate_1 (data
,
1711 iv
->base
, iv
->step
, true, IP_ORIGINAL
, NULL
,
1712 SSA_NAME_DEF_STMT (def
));
1713 cand
->var_before
= iv
->ssa_name
;
1714 cand
->var_after
= def
;
1718 /* Adds candidates based on the old induction variables. */
1721 add_old_ivs_candidates (struct ivopts_data
*data
)
1727 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1729 iv
= ver_info (data
, i
)->iv
;
1730 if (iv
&& iv
->biv_p
&& !zero_p (iv
->step
))
1731 add_old_iv_candidates (data
, iv
);
1735 /* Adds candidates based on the value of the induction variable IV and USE. */
1738 add_iv_value_candidates (struct ivopts_data
*data
,
1739 struct iv
*iv
, struct iv_use
*use
)
1741 add_candidate (data
, iv
->base
, iv
->step
, false, use
);
1743 /* The same, but with initial value zero. */
1744 add_candidate (data
, build_int_cst (TREE_TYPE (iv
->base
), 0),
1745 iv
->step
, false, use
);
1748 /* Adds candidates based on the address IV and USE. */
1751 add_address_candidates (struct ivopts_data
*data
,
1752 struct iv
*iv
, struct iv_use
*use
)
1754 tree base
, abase
, tmp
, *act
;
1756 /* First, the trivial choices. */
1757 add_iv_value_candidates (data
, iv
, use
);
1759 /* Second, try removing the COMPONENT_REFs. */
1760 if (TREE_CODE (iv
->base
) == ADDR_EXPR
)
1762 base
= TREE_OPERAND (iv
->base
, 0);
1763 while (TREE_CODE (base
) == COMPONENT_REF
1764 || (TREE_CODE (base
) == ARRAY_REF
1765 && TREE_CODE (TREE_OPERAND (base
, 1)) == INTEGER_CST
))
1766 base
= TREE_OPERAND (base
, 0);
1768 if (base
!= TREE_OPERAND (iv
->base
, 0))
1770 gcc_assert (TREE_CODE (base
) != ALIGN_INDIRECT_REF
);
1771 gcc_assert (TREE_CODE (base
) != MISALIGNED_INDIRECT_REF
);
1773 if (TREE_CODE (base
) == INDIRECT_REF
)
1774 base
= TREE_OPERAND (base
, 0);
1776 base
= build_addr (base
);
1777 add_candidate (data
, base
, iv
->step
, false, use
);
1781 /* Third, try removing the constant offset. */
1783 while (TREE_CODE (abase
) == PLUS_EXPR
1784 && TREE_CODE (TREE_OPERAND (abase
, 1)) != INTEGER_CST
)
1785 abase
= TREE_OPERAND (abase
, 0);
1786 /* We found the offset, so make the copy of the non-shared part and
1788 if (TREE_CODE (abase
) == PLUS_EXPR
)
1793 for (tmp
= iv
->base
; tmp
!= abase
; tmp
= TREE_OPERAND (tmp
, 0))
1795 *act
= build2 (PLUS_EXPR
, TREE_TYPE (tmp
),
1796 NULL_TREE
, TREE_OPERAND (tmp
, 1));
1797 act
= &TREE_OPERAND (*act
, 0);
1799 *act
= TREE_OPERAND (tmp
, 0);
1801 add_candidate (data
, base
, iv
->step
, false, use
);
1805 /* Possibly adds pseudocandidate for replacing the final value of USE by
1806 a direct computation. */
1809 add_iv_outer_candidates (struct ivopts_data
*data
, struct iv_use
*use
)
1811 struct tree_niter_desc
*niter
;
1812 struct loop
*loop
= data
->current_loop
;
1814 /* We must know where we exit the loop and how many times does it roll. */
1815 if (!single_dom_exit (loop
))
1818 niter
= &loop_data (loop
)->niter
;
1820 || !operand_equal_p (niter
->assumptions
, boolean_true_node
, 0)
1821 || !operand_equal_p (niter
->may_be_zero
, boolean_false_node
, 0))
1824 add_candidate_1 (data
, NULL
, NULL
, false, IP_NORMAL
, use
, NULL_TREE
);
1827 /* Adds candidates based on the uses. */
1830 add_derived_ivs_candidates (struct ivopts_data
*data
)
1834 for (i
= 0; i
< n_iv_uses (data
); i
++)
1836 struct iv_use
*use
= iv_use (data
, i
);
1843 case USE_NONLINEAR_EXPR
:
1845 /* Just add the ivs based on the value of the iv used here. */
1846 add_iv_value_candidates (data
, use
->iv
, use
);
1850 add_iv_value_candidates (data
, use
->iv
, use
);
1852 /* Additionally, add the pseudocandidate for the possibility to
1853 replace the final value by a direct computation. */
1854 add_iv_outer_candidates (data
, use
);
1858 add_address_candidates (data
, use
->iv
, use
);
1867 /* Finds the candidates for the induction variables. */
1870 find_iv_candidates (struct ivopts_data
*data
)
1872 /* Add commonly used ivs. */
1873 add_standard_iv_candidates (data
);
1875 /* Add old induction variables. */
1876 add_old_ivs_candidates (data
);
1878 /* Add induction variables derived from uses. */
1879 add_derived_ivs_candidates (data
);
1882 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
1883 If consider_all_candidates is true, we use a two-dimensional array, otherwise
1884 we allocate a simple list to every use. */
1887 alloc_use_cost_map (struct ivopts_data
*data
)
1889 unsigned i
, n_imp
= 0, size
, j
;
1891 if (!data
->consider_all_candidates
)
1893 for (i
= 0; i
< n_iv_cands (data
); i
++)
1895 struct iv_cand
*cand
= iv_cand (data
, i
);
1896 if (cand
->important
)
1901 for (i
= 0; i
< n_iv_uses (data
); i
++)
1903 struct iv_use
*use
= iv_use (data
, i
);
1906 if (data
->consider_all_candidates
)
1908 size
= n_iv_cands (data
);
1909 use
->n_map_members
= size
;
1914 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, j
, bi
)
1918 use
->n_map_members
= 0;
1921 use
->cost_map
= xcalloc (size
, sizeof (struct cost_pair
));
1925 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
1926 on invariants DEPENDS_ON. */
1929 set_use_iv_cost (struct ivopts_data
*data
,
1930 struct iv_use
*use
, struct iv_cand
*cand
, unsigned cost
,
1936 BITMAP_XFREE (depends_on
);
1940 if (data
->consider_all_candidates
)
1942 use
->cost_map
[cand
->id
].cand
= cand
;
1943 use
->cost_map
[cand
->id
].cost
= cost
;
1944 use
->cost_map
[cand
->id
].depends_on
= depends_on
;
1951 use
->cost_map
[use
->n_map_members
].cand
= cand
;
1952 use
->cost_map
[use
->n_map_members
].cost
= cost
;
1953 use
->cost_map
[use
->n_map_members
].depends_on
= depends_on
;
1954 use
->n_map_members
++;
1957 /* Gets cost of (USE, CANDIDATE) pair. Stores the bitmap of dependencies to
1961 get_use_iv_cost (struct ivopts_data
*data
,
1962 struct iv_use
*use
, struct iv_cand
*cand
, bitmap
*depends_on
)
1969 if (data
->consider_all_candidates
)
1973 for (i
= 0; i
< use
->n_map_members
; i
++)
1974 if (use
->cost_map
[i
].cand
== cand
)
1977 if (i
== use
->n_map_members
)
1982 *depends_on
= use
->cost_map
[i
].depends_on
;
1983 return use
->cost_map
[i
].cost
;
1986 /* Returns estimate on cost of computing SEQ. */
1994 for (; seq
; seq
= NEXT_INSN (seq
))
1996 set
= single_set (seq
);
1998 cost
+= rtx_cost (set
, SET
);
2006 /* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
2008 produce_memory_decl_rtl (tree obj
, int *regno
)
2013 if (TREE_STATIC (obj
) || DECL_EXTERNAL (obj
))
2015 const char *name
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj
));
2016 x
= gen_rtx_SYMBOL_REF (Pmode
, name
);
2019 x
= gen_raw_REG (Pmode
, (*regno
)++);
2021 return gen_rtx_MEM (DECL_MODE (obj
), x
);
2024 /* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
2025 walk_tree. DATA contains the actual fake register number. */
2028 prepare_decl_rtl (tree
*expr_p
, int *ws
, void *data
)
2030 tree obj
= NULL_TREE
;
2034 switch (TREE_CODE (*expr_p
))
2037 for (expr_p
= &TREE_OPERAND (*expr_p
, 0);
2038 (handled_component_p (*expr_p
)
2039 || TREE_CODE (*expr_p
) == REALPART_EXPR
2040 || TREE_CODE (*expr_p
) == IMAGPART_EXPR
);
2041 expr_p
= &TREE_OPERAND (*expr_p
, 0));
2044 x
= produce_memory_decl_rtl (obj
, regno
);
2049 obj
= SSA_NAME_VAR (*expr_p
);
2050 if (!DECL_RTL_SET_P (obj
))
2051 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2060 if (DECL_RTL_SET_P (obj
))
2063 if (DECL_MODE (obj
) == BLKmode
)
2064 x
= produce_memory_decl_rtl (obj
, regno
);
2066 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2076 VARRAY_PUSH_GENERIC_PTR_NOGC (decl_rtl_to_reset
, obj
);
2077 SET_DECL_RTL (obj
, x
);
2083 /* Determines cost of the computation of EXPR. */
2086 computation_cost (tree expr
)
2089 tree type
= TREE_TYPE (expr
);
2093 walk_tree (&expr
, prepare_decl_rtl
, ®no
, NULL
);
2095 rslt
= expand_expr (expr
, NULL_RTX
, TYPE_MODE (type
), EXPAND_NORMAL
);
2099 cost
= seq_cost (seq
);
2100 if (GET_CODE (rslt
) == MEM
)
2101 cost
+= address_cost (XEXP (rslt
, 0), TYPE_MODE (type
));
2106 /* Returns variable containing the value of candidate CAND at statement AT. */
2109 var_at_stmt (struct loop
*loop
, struct iv_cand
*cand
, tree stmt
)
2111 if (stmt_after_increment (loop
, cand
, stmt
))
2112 return cand
->var_after
;
2114 return cand
->var_before
;
2117 /* Determines the expression by that USE is expressed from induction variable
2118 CAND at statement AT in LOOP. */
2121 get_computation_at (struct loop
*loop
,
2122 struct iv_use
*use
, struct iv_cand
*cand
, tree at
)
2124 tree ubase
= use
->iv
->base
;
2125 tree ustep
= use
->iv
->step
;
2126 tree cbase
= cand
->iv
->base
;
2127 tree cstep
= cand
->iv
->step
;
2128 tree utype
= TREE_TYPE (ubase
), ctype
= TREE_TYPE (cbase
);
2132 unsigned HOST_WIDE_INT ustepi
, cstepi
;
2133 HOST_WIDE_INT ratioi
;
2135 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
2137 /* We do not have a precision to express the values of use. */
2141 expr
= var_at_stmt (loop
, cand
, at
);
2143 if (TREE_TYPE (expr
) != ctype
)
2145 /* This may happen with the original ivs. */
2146 expr
= fold_convert (ctype
, expr
);
2149 if (TYPE_UNSIGNED (utype
))
2153 uutype
= unsigned_type_for (utype
);
2154 ubase
= fold_convert (uutype
, ubase
);
2155 ustep
= fold_convert (uutype
, ustep
);
2158 if (uutype
!= ctype
)
2160 expr
= fold_convert (uutype
, expr
);
2161 cbase
= fold_convert (uutype
, cbase
);
2162 cstep
= fold_convert (uutype
, cstep
);
2165 if (!cst_and_fits_in_hwi (cstep
)
2166 || !cst_and_fits_in_hwi (ustep
))
2169 ustepi
= int_cst_value (ustep
);
2170 cstepi
= int_cst_value (cstep
);
2172 if (!divide (TYPE_PRECISION (uutype
), ustepi
, cstepi
, &ratioi
))
2174 /* TODO maybe consider case when ustep divides cstep and the ratio is
2175 a power of 2 (so that the division is fast to execute)? We would
2176 need to be much more careful with overflows etc. then. */
2180 /* We may need to shift the value if we are after the increment. */
2181 if (stmt_after_increment (loop
, cand
, at
))
2182 cbase
= fold (build2 (PLUS_EXPR
, uutype
, cbase
, cstep
));
2184 /* use = ubase + ratio * (var - cbase). If either cbase is a constant
2185 or |ratio| == 1, it is better to handle this like
2187 ubase - ratio * cbase + ratio * var. */
2191 delta
= fold (build2 (MINUS_EXPR
, uutype
, ubase
, cbase
));
2192 expr
= fold (build2 (PLUS_EXPR
, uutype
, expr
, delta
));
2194 else if (ratioi
== -1)
2196 delta
= fold (build2 (PLUS_EXPR
, uutype
, ubase
, cbase
));
2197 expr
= fold (build2 (MINUS_EXPR
, uutype
, delta
, expr
));
2199 else if (TREE_CODE (cbase
) == INTEGER_CST
)
2201 ratio
= build_int_cst_type (uutype
, ratioi
);
2202 delta
= fold (build2 (MULT_EXPR
, uutype
, ratio
, cbase
));
2203 delta
= fold (build2 (MINUS_EXPR
, uutype
, ubase
, delta
));
2204 expr
= fold (build2 (MULT_EXPR
, uutype
, ratio
, expr
));
2205 expr
= fold (build2 (PLUS_EXPR
, uutype
, delta
, expr
));
2209 expr
= fold (build2 (MINUS_EXPR
, uutype
, expr
, cbase
));
2210 ratio
= build_int_cst_type (uutype
, ratioi
);
2211 expr
= fold (build2 (MULT_EXPR
, uutype
, ratio
, expr
));
2212 expr
= fold (build2 (PLUS_EXPR
, uutype
, ubase
, expr
));
2215 return fold_convert (utype
, expr
);
2218 /* Determines the expression by that USE is expressed from induction variable
2222 get_computation (struct loop
*loop
, struct iv_use
*use
, struct iv_cand
*cand
)
2224 return get_computation_at (loop
, use
, cand
, use
->stmt
);
2227 /* Strips constant offsets from EXPR and adds them to OFFSET. */
2230 strip_offset (tree
*expr
, unsigned HOST_WIDE_INT
*offset
)
2233 enum tree_code code
;
2237 if (cst_and_fits_in_hwi (*expr
))
2239 *offset
+= int_cst_value (*expr
);
2240 *expr
= integer_zero_node
;
2244 code
= TREE_CODE (*expr
);
2246 if (code
!= PLUS_EXPR
&& code
!= MINUS_EXPR
)
2249 op0
= TREE_OPERAND (*expr
, 0);
2250 op1
= TREE_OPERAND (*expr
, 1);
2252 if (cst_and_fits_in_hwi (op1
))
2254 if (code
== PLUS_EXPR
)
2255 *offset
+= int_cst_value (op1
);
2257 *offset
-= int_cst_value (op1
);
2263 if (code
!= PLUS_EXPR
)
2266 if (!cst_and_fits_in_hwi (op0
))
2269 *offset
+= int_cst_value (op0
);
2274 /* Returns cost of addition in MODE. */
2277 add_cost (enum machine_mode mode
)
2279 static unsigned costs
[NUM_MACHINE_MODES
];
2287 force_operand (gen_rtx_fmt_ee (PLUS
, mode
,
2288 gen_raw_REG (mode
, FIRST_PSEUDO_REGISTER
),
2289 gen_raw_REG (mode
, FIRST_PSEUDO_REGISTER
+ 1)),
2294 cost
= seq_cost (seq
);
2300 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2301 fprintf (dump_file
, "Addition in %s costs %d\n",
2302 GET_MODE_NAME (mode
), cost
);
2306 /* Entry in a hashtable of already known costs for multiplication. */
2309 HOST_WIDE_INT cst
; /* The constant to multiply by. */
2310 enum machine_mode mode
; /* In mode. */
2311 unsigned cost
; /* The cost. */
2314 /* Counts hash value for the ENTRY. */
2317 mbc_entry_hash (const void *entry
)
2319 const struct mbc_entry
*e
= entry
;
2321 return 57 * (hashval_t
) e
->mode
+ (hashval_t
) (e
->cst
% 877);
2324 /* Compares the hash table entries ENTRY1 and ENTRY2. */
2327 mbc_entry_eq (const void *entry1
, const void *entry2
)
2329 const struct mbc_entry
*e1
= entry1
;
2330 const struct mbc_entry
*e2
= entry2
;
2332 return (e1
->mode
== e2
->mode
2333 && e1
->cst
== e2
->cst
);
2336 /* Returns cost of multiplication by constant CST in MODE. */
2339 multiply_by_cost (HOST_WIDE_INT cst
, enum machine_mode mode
)
2341 static htab_t costs
;
2342 struct mbc_entry
**cached
, act
;
2347 costs
= htab_create (100, mbc_entry_hash
, mbc_entry_eq
, free
);
2351 cached
= (struct mbc_entry
**) htab_find_slot (costs
, &act
, INSERT
);
2353 return (*cached
)->cost
;
2355 *cached
= xmalloc (sizeof (struct mbc_entry
));
2356 (*cached
)->mode
= mode
;
2357 (*cached
)->cst
= cst
;
2360 expand_mult (mode
, gen_raw_REG (mode
, FIRST_PSEUDO_REGISTER
), GEN_INT (cst
),
2365 cost
= seq_cost (seq
);
2367 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2368 fprintf (dump_file
, "Multiplication by %d in %s costs %d\n",
2369 (int) cst
, GET_MODE_NAME (mode
), cost
);
2371 (*cached
)->cost
= cost
;
2376 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
2377 If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
2378 variable is omitted. The created memory accesses MODE.
2380 TODO -- there must be some better way. This all is quite crude. */
2383 get_address_cost (bool symbol_present
, bool var_present
,
2384 unsigned HOST_WIDE_INT offset
, HOST_WIDE_INT ratio
)
2386 #define MAX_RATIO 128
2387 static sbitmap valid_mult
;
2388 static HOST_WIDE_INT rat
, off
;
2389 static HOST_WIDE_INT min_offset
, max_offset
;
2390 static unsigned costs
[2][2][2][2];
2391 unsigned cost
, acost
;
2392 rtx seq
, addr
, base
;
2393 bool offset_p
, ratio_p
;
2395 HOST_WIDE_INT s_offset
;
2396 unsigned HOST_WIDE_INT mask
;
2403 reg1
= gen_raw_REG (Pmode
, FIRST_PSEUDO_REGISTER
);
2405 addr
= gen_rtx_fmt_ee (PLUS
, Pmode
, reg1
, NULL_RTX
);
2406 for (i
= 1; i
<= 1 << 20; i
<<= 1)
2408 XEXP (addr
, 1) = GEN_INT (i
);
2409 if (!memory_address_p (Pmode
, addr
))
2412 max_offset
= i
>> 1;
2415 for (i
= 1; i
<= 1 << 20; i
<<= 1)
2417 XEXP (addr
, 1) = GEN_INT (-i
);
2418 if (!memory_address_p (Pmode
, addr
))
2421 min_offset
= -(i
>> 1);
2423 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2425 fprintf (dump_file
, "get_address_cost:\n");
2426 fprintf (dump_file
, " min offset %d\n", (int) min_offset
);
2427 fprintf (dump_file
, " max offset %d\n", (int) max_offset
);
2430 valid_mult
= sbitmap_alloc (2 * MAX_RATIO
+ 1);
2431 sbitmap_zero (valid_mult
);
2433 addr
= gen_rtx_fmt_ee (MULT
, Pmode
, reg1
, NULL_RTX
);
2434 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
2436 XEXP (addr
, 1) = GEN_INT (i
);
2437 if (memory_address_p (Pmode
, addr
))
2439 SET_BIT (valid_mult
, i
+ MAX_RATIO
);
2444 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2446 fprintf (dump_file
, " allowed multipliers:");
2447 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
2448 if (TEST_BIT (valid_mult
, i
+ MAX_RATIO
))
2449 fprintf (dump_file
, " %d", (int) i
);
2450 fprintf (dump_file
, "\n");
2451 fprintf (dump_file
, "\n");
2455 bits
= GET_MODE_BITSIZE (Pmode
);
2456 mask
= ~(~(unsigned HOST_WIDE_INT
) 0 << (bits
- 1) << 1);
2458 if ((offset
>> (bits
- 1) & 1))
2463 offset_p
= (min_offset
<= s_offset
&& s_offset
<= max_offset
);
2464 ratio_p
= (ratio
!= 1
2465 && -MAX_RATIO
<= ratio
&& ratio
<= MAX_RATIO
2466 && TEST_BIT (valid_mult
, ratio
+ MAX_RATIO
));
2468 if (ratio
!= 1 && !ratio_p
)
2469 cost
+= multiply_by_cost (ratio
, Pmode
);
2471 if (s_offset
&& !offset_p
&& !symbol_present
)
2473 cost
+= add_cost (Pmode
);
2477 acost
= costs
[symbol_present
][var_present
][offset_p
][ratio_p
];
2482 addr
= gen_raw_REG (Pmode
, FIRST_PSEUDO_REGISTER
);
2483 reg1
= gen_raw_REG (Pmode
, FIRST_PSEUDO_REGISTER
+ 1);
2485 addr
= gen_rtx_fmt_ee (MULT
, Pmode
, addr
, GEN_INT (rat
));
2489 base
= gen_rtx_SYMBOL_REF (Pmode
, ggc_strdup (""));
2491 base
= gen_rtx_fmt_e (CONST
, Pmode
,
2492 gen_rtx_fmt_ee (PLUS
, Pmode
,
2496 base
= gen_rtx_fmt_ee (PLUS
, Pmode
, reg1
, base
);
2499 else if (var_present
)
2503 base
= gen_rtx_fmt_ee (PLUS
, Pmode
, base
, GEN_INT (off
));
2506 base
= GEN_INT (off
);
2511 addr
= gen_rtx_fmt_ee (PLUS
, Pmode
, base
, addr
);
2514 addr
= memory_address (Pmode
, addr
);
2518 acost
= seq_cost (seq
);
2519 acost
+= address_cost (addr
, Pmode
);
2523 costs
[symbol_present
][var_present
][offset_p
][ratio_p
] = acost
;
2526 return cost
+ acost
;
2529 /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
2530 the bitmap to that we should store it. */
2532 static struct ivopts_data
*fd_ivopts_data
;
2534 find_depends (tree
*expr_p
, int *ws ATTRIBUTE_UNUSED
, void *data
)
2536 bitmap
*depends_on
= data
;
2537 struct version_info
*info
;
2539 if (TREE_CODE (*expr_p
) != SSA_NAME
)
2541 info
= name_info (fd_ivopts_data
, *expr_p
);
2543 if (!info
->inv_id
|| info
->has_nonlin_use
)
2547 *depends_on
= BITMAP_XMALLOC ();
2548 bitmap_set_bit (*depends_on
, info
->inv_id
);
2553 /* Estimates cost of forcing EXPR into variable. DEPENDS_ON is a set of the
2554 invariants the computation depends on. */
2557 force_var_cost (struct ivopts_data
*data
,
2558 tree expr
, bitmap
*depends_on
)
2560 static bool costs_initialized
= false;
2561 static unsigned integer_cost
;
2562 static unsigned symbol_cost
;
2563 static unsigned address_cost
;
2565 if (!costs_initialized
)
2567 tree var
= create_tmp_var_raw (integer_type_node
, "test_var");
2568 rtx x
= gen_rtx_MEM (DECL_MODE (var
),
2569 gen_rtx_SYMBOL_REF (Pmode
, "test_var"));
2571 tree type
= build_pointer_type (integer_type_node
);
2573 integer_cost
= computation_cost (build_int_cst_type (integer_type_node
,
2576 SET_DECL_RTL (var
, x
);
2577 TREE_STATIC (var
) = 1;
2578 addr
= build1 (ADDR_EXPR
, type
, var
);
2579 symbol_cost
= computation_cost (addr
) + 1;
2582 = computation_cost (build2 (PLUS_EXPR
, type
,
2584 build_int_cst_type (type
, 2000))) + 1;
2585 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2587 fprintf (dump_file
, "force_var_cost:\n");
2588 fprintf (dump_file
, " integer %d\n", (int) integer_cost
);
2589 fprintf (dump_file
, " symbol %d\n", (int) symbol_cost
);
2590 fprintf (dump_file
, " address %d\n", (int) address_cost
);
2591 fprintf (dump_file
, " other %d\n", (int) target_spill_cost
);
2592 fprintf (dump_file
, "\n");
2595 costs_initialized
= true;
2600 fd_ivopts_data
= data
;
2601 walk_tree (&expr
, find_depends
, depends_on
, NULL
);
2604 if (SSA_VAR_P (expr
))
2607 if (TREE_INVARIANT (expr
))
2609 if (TREE_CODE (expr
) == INTEGER_CST
)
2610 return integer_cost
;
2612 if (TREE_CODE (expr
) == ADDR_EXPR
)
2614 tree obj
= TREE_OPERAND (expr
, 0);
2616 if (TREE_CODE (obj
) == VAR_DECL
2617 || TREE_CODE (obj
) == PARM_DECL
2618 || TREE_CODE (obj
) == RESULT_DECL
)
2622 return address_cost
;
2625 /* Just an arbitrary value, FIXME. */
2626 return target_spill_cost
;
2629 /* Estimates cost of expressing address ADDR as var + symbol + offset. The
2630 value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
2631 to false if the corresponding part is missing. DEPENDS_ON is a set of the
2632 invariants the computation depends on. */
2635 split_address_cost (struct ivopts_data
*data
,
2636 tree addr
, bool *symbol_present
, bool *var_present
,
2637 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
2640 HOST_WIDE_INT bitsize
;
2641 HOST_WIDE_INT bitpos
;
2643 enum machine_mode mode
;
2644 int unsignedp
, volatilep
;
2646 core
= get_inner_reference (addr
, &bitsize
, &bitpos
, &toffset
, &mode
,
2647 &unsignedp
, &volatilep
);
2650 || bitpos
% BITS_PER_UNIT
!= 0
2651 || TREE_CODE (core
) != VAR_DECL
)
2653 *symbol_present
= false;
2654 *var_present
= true;
2655 fd_ivopts_data
= data
;
2656 walk_tree (&addr
, find_depends
, depends_on
, NULL
);
2657 return target_spill_cost
;
2660 *offset
+= bitpos
/ BITS_PER_UNIT
;
2661 if (TREE_STATIC (core
)
2662 || DECL_EXTERNAL (core
))
2664 *symbol_present
= true;
2665 *var_present
= false;
2669 *symbol_present
= false;
2670 *var_present
= true;
2674 /* Estimates cost of expressing difference of addresses E1 - E2 as
2675 var + symbol + offset. The value of offset is added to OFFSET,
2676 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
2677 part is missing. DEPENDS_ON is a set of the invariants the computation
2681 ptr_difference_cost (struct ivopts_data
*data
,
2682 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
2683 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
2685 HOST_WIDE_INT diff
= 0;
2688 gcc_assert (TREE_CODE (e1
) == ADDR_EXPR
);
2690 if (TREE_CODE (e2
) == ADDR_EXPR
2691 && ptr_difference_const (TREE_OPERAND (e1
, 0),
2692 TREE_OPERAND (e2
, 0), &diff
))
2695 *symbol_present
= false;
2696 *var_present
= false;
2700 if (e2
== integer_zero_node
)
2701 return split_address_cost (data
, TREE_OPERAND (e1
, 0),
2702 symbol_present
, var_present
, offset
, depends_on
);
2704 *symbol_present
= false;
2705 *var_present
= true;
2707 cost
= force_var_cost (data
, e1
, depends_on
);
2708 cost
+= force_var_cost (data
, e2
, depends_on
);
2709 cost
+= add_cost (Pmode
);
2714 /* Estimates cost of expressing difference E1 - E2 as
2715 var + symbol + offset. The value of offset is added to OFFSET,
2716 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
2717 part is missing. DEPENDS_ON is a set of the invariants the computation
2721 difference_cost (struct ivopts_data
*data
,
2722 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
2723 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
2726 enum machine_mode mode
= TYPE_MODE (TREE_TYPE (e1
));
2728 strip_offset (&e1
, offset
);
2730 strip_offset (&e2
, offset
);
2733 if (TREE_CODE (e1
) == ADDR_EXPR
)
2734 return ptr_difference_cost (data
, e1
, e2
, symbol_present
, var_present
, offset
,
2736 *symbol_present
= false;
2738 if (operand_equal_p (e1
, e2
, 0))
2740 *var_present
= false;
2743 *var_present
= true;
2745 return force_var_cost (data
, e1
, depends_on
);
2749 cost
= force_var_cost (data
, e2
, depends_on
);
2750 cost
+= multiply_by_cost (-1, mode
);
2755 cost
= force_var_cost (data
, e1
, depends_on
);
2756 cost
+= force_var_cost (data
, e2
, depends_on
);
2757 cost
+= add_cost (mode
);
2762 /* Determines the cost of the computation by that USE is expressed
2763 from induction variable CAND. If ADDRESS_P is true, we just need
2764 to create an address from it, otherwise we want to get it into
2765 register. A set of invariants we depend on is stored in
2766 DEPENDS_ON. AT is the statement at that the value is computed. */
2769 get_computation_cost_at (struct ivopts_data
*data
,
2770 struct iv_use
*use
, struct iv_cand
*cand
,
2771 bool address_p
, bitmap
*depends_on
, tree at
)
2773 tree ubase
= use
->iv
->base
, ustep
= use
->iv
->step
;
2775 tree utype
= TREE_TYPE (ubase
), ctype
;
2776 unsigned HOST_WIDE_INT ustepi
, cstepi
, offset
= 0;
2777 HOST_WIDE_INT ratio
, aratio
;
2778 bool var_present
, symbol_present
;
2779 unsigned cost
= 0, n_sums
;
2783 /* Only consider real candidates. */
2787 cbase
= cand
->iv
->base
;
2788 cstep
= cand
->iv
->step
;
2789 ctype
= TREE_TYPE (cbase
);
2791 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
2793 /* We do not have a precision to express the values of use. */
2797 if (!cst_and_fits_in_hwi (ustep
)
2798 || !cst_and_fits_in_hwi (cstep
))
2801 if (TREE_CODE (ubase
) == INTEGER_CST
2802 && !cst_and_fits_in_hwi (ubase
))
2805 if (TREE_CODE (cbase
) == INTEGER_CST
2806 && !cst_and_fits_in_hwi (cbase
))
2809 ustepi
= int_cst_value (ustep
);
2810 cstepi
= int_cst_value (cstep
);
2812 if (TYPE_PRECISION (utype
) != TYPE_PRECISION (ctype
))
2814 /* TODO -- add direct handling of this case. */
2818 if (!divide (TYPE_PRECISION (utype
), ustepi
, cstepi
, &ratio
))
2821 /* use = ubase + ratio * (var - cbase). If either cbase is a constant
2822 or ratio == 1, it is better to handle this like
2824 ubase - ratio * cbase + ratio * var
2826 (also holds in the case ratio == -1, TODO. */
2828 if (TREE_CODE (cbase
) == INTEGER_CST
)
2830 offset
= - ratio
* int_cst_value (cbase
);
2831 cost
+= difference_cost (data
,
2832 ubase
, integer_zero_node
,
2833 &symbol_present
, &var_present
, &offset
,
2836 else if (ratio
== 1)
2838 cost
+= difference_cost (data
,
2840 &symbol_present
, &var_present
, &offset
,
2845 cost
+= force_var_cost (data
, cbase
, depends_on
);
2846 cost
+= add_cost (TYPE_MODE (ctype
));
2847 cost
+= difference_cost (data
,
2848 ubase
, integer_zero_node
,
2849 &symbol_present
, &var_present
, &offset
,
2853 /* If we are after the increment, the value of the candidate is higher by
2855 if (stmt_after_increment (data
->current_loop
, cand
, at
))
2856 offset
-= ratio
* cstepi
;
2858 /* Now the computation is in shape symbol + var1 + const + ratio * var2.
2859 (symbol/var/const parts may be omitted). If we are looking for an address,
2860 find the cost of addressing this. */
2862 return get_address_cost (symbol_present
, var_present
, offset
, ratio
);
2864 /* Otherwise estimate the costs for computing the expression. */
2865 aratio
= ratio
> 0 ? ratio
: -ratio
;
2866 if (!symbol_present
&& !var_present
&& !offset
)
2869 cost
+= multiply_by_cost (ratio
, TYPE_MODE (ctype
));
2875 cost
+= multiply_by_cost (aratio
, TYPE_MODE (ctype
));
2879 /* Symbol + offset should be compile-time computable. */
2880 && (symbol_present
|| offset
))
2883 return cost
+ n_sums
* add_cost (TYPE_MODE (ctype
));
2887 /* Just get the expression, expand it and measure the cost. */
2888 tree comp
= get_computation_at (data
->current_loop
, use
, cand
, at
);
2894 comp
= build1 (INDIRECT_REF
, TREE_TYPE (TREE_TYPE (comp
)), comp
);
2896 return computation_cost (comp
);
2900 /* Determines the cost of the computation by that USE is expressed
2901 from induction variable CAND. If ADDRESS_P is true, we just need
2902 to create an address from it, otherwise we want to get it into
2903 register. A set of invariants we depend on is stored in
2907 get_computation_cost (struct ivopts_data
*data
,
2908 struct iv_use
*use
, struct iv_cand
*cand
,
2909 bool address_p
, bitmap
*depends_on
)
2911 return get_computation_cost_at (data
,
2912 use
, cand
, address_p
, depends_on
, use
->stmt
);
2915 /* Determines cost of basing replacement of USE on CAND in a generic
2919 determine_use_iv_cost_generic (struct ivopts_data
*data
,
2920 struct iv_use
*use
, struct iv_cand
*cand
)
2923 unsigned cost
= get_computation_cost (data
, use
, cand
, false, &depends_on
);
2925 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
);
2928 /* Determines cost of basing replacement of USE on CAND in an address. */
2931 determine_use_iv_cost_address (struct ivopts_data
*data
,
2932 struct iv_use
*use
, struct iv_cand
*cand
)
2935 unsigned cost
= get_computation_cost (data
, use
, cand
, true, &depends_on
);
2937 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
);
2940 /* Computes value of induction variable IV in iteration NITER. */
2943 iv_value (struct iv
*iv
, tree niter
)
2946 tree type
= TREE_TYPE (iv
->base
);
2948 niter
= fold_convert (type
, niter
);
2949 val
= fold (build2 (MULT_EXPR
, type
, iv
->step
, niter
));
2951 return fold (build2 (PLUS_EXPR
, type
, iv
->base
, val
));
2954 /* Computes value of candidate CAND at position AT in iteration NITER. */
2957 cand_value_at (struct loop
*loop
, struct iv_cand
*cand
, tree at
, tree niter
)
2959 tree val
= iv_value (cand
->iv
, niter
);
2960 tree type
= TREE_TYPE (cand
->iv
->base
);
2962 if (stmt_after_increment (loop
, cand
, at
))
2963 val
= fold (build2 (PLUS_EXPR
, type
, val
, cand
->iv
->step
));
2968 /* Check whether it is possible to express the condition in USE by comparison
2969 of candidate CAND. If so, store the comparison code to COMPARE and the
2970 value compared with to BOUND. */
2973 may_eliminate_iv (struct loop
*loop
,
2974 struct iv_use
*use
, struct iv_cand
*cand
,
2975 enum tree_code
*compare
, tree
*bound
)
2978 struct tree_niter_desc
*niter
, new_niter
;
2979 tree wider_type
, type
, base
;
2981 /* For now just very primitive -- we work just for the single exit condition,
2982 and are quite conservative about the possible overflows. TODO -- both of
2983 these can be improved. */
2984 exit
= single_dom_exit (loop
);
2987 if (use
->stmt
!= last_stmt (exit
->src
))
2990 niter
= &loop_data (loop
)->niter
;
2992 || !integer_nonzerop (niter
->assumptions
)
2993 || !integer_zerop (niter
->may_be_zero
))
2996 if (exit
->flags
& EDGE_TRUE_VALUE
)
3001 *bound
= cand_value_at (loop
, cand
, use
->stmt
, niter
->niter
);
3003 /* Let us check there is not some problem with overflows, by checking that
3004 the number of iterations is unchanged. */
3005 base
= cand
->iv
->base
;
3006 type
= TREE_TYPE (base
);
3007 if (stmt_after_increment (loop
, cand
, use
->stmt
))
3008 base
= fold (build2 (PLUS_EXPR
, type
, base
, cand
->iv
->step
));
3010 new_niter
.niter
= NULL_TREE
;
3011 number_of_iterations_cond (TREE_TYPE (cand
->iv
->base
), base
,
3012 cand
->iv
->step
, NE_EXPR
, *bound
, NULL_TREE
,
3014 if (!new_niter
.niter
3015 || !integer_nonzerop (new_niter
.assumptions
)
3016 || !integer_zerop (new_niter
.may_be_zero
))
3019 wider_type
= TREE_TYPE (new_niter
.niter
);
3020 if (TYPE_PRECISION (wider_type
) < TYPE_PRECISION (TREE_TYPE (niter
->niter
)))
3021 wider_type
= TREE_TYPE (niter
->niter
);
3022 if (!operand_equal_p (fold_convert (wider_type
, niter
->niter
),
3023 fold_convert (wider_type
, new_niter
.niter
), 0))
3029 /* Determines cost of basing replacement of USE on CAND in a condition. */
3032 determine_use_iv_cost_condition (struct ivopts_data
*data
,
3033 struct iv_use
*use
, struct iv_cand
*cand
)
3036 enum tree_code compare
;
3038 /* Only consider real candidates. */
3041 set_use_iv_cost (data
, use
, cand
, INFTY
, NULL
);
3045 if (may_eliminate_iv (data
->current_loop
, use
, cand
, &compare
, &bound
))
3047 bitmap depends_on
= NULL
;
3048 unsigned cost
= force_var_cost (data
, bound
, &depends_on
);
3050 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
);
3054 /* The induction variable elimination failed; just express the original
3055 giv. If it is compared with an invariant, note that we cannot get
3057 if (TREE_CODE (*use
->op_p
) == SSA_NAME
)
3058 record_invariant (data
, *use
->op_p
, true);
3061 record_invariant (data
, TREE_OPERAND (*use
->op_p
, 0), true);
3062 record_invariant (data
, TREE_OPERAND (*use
->op_p
, 1), true);
3065 determine_use_iv_cost_generic (data
, use
, cand
);
3068 /* Checks whether it is possible to replace the final value of USE by
3069 a direct computation. If so, the formula is stored to *VALUE. */
3072 may_replace_final_value (struct loop
*loop
, struct iv_use
*use
, tree
*value
)
3075 struct tree_niter_desc
*niter
;
3077 exit
= single_dom_exit (loop
);
3081 gcc_assert (dominated_by_p (CDI_DOMINATORS
, exit
->src
,
3082 bb_for_stmt (use
->stmt
)));
3084 niter
= &loop_data (loop
)->niter
;
3086 || !operand_equal_p (niter
->assumptions
, boolean_true_node
, 0)
3087 || !operand_equal_p (niter
->may_be_zero
, boolean_false_node
, 0))
3090 *value
= iv_value (use
->iv
, niter
->niter
);
3095 /* Determines cost of replacing final value of USE using CAND. */
3098 determine_use_iv_cost_outer (struct ivopts_data
*data
,
3099 struct iv_use
*use
, struct iv_cand
*cand
)
3105 struct loop
*loop
= data
->current_loop
;
3109 if (!may_replace_final_value (loop
, use
, &value
))
3111 set_use_iv_cost (data
, use
, cand
, INFTY
, NULL
);
3116 cost
= force_var_cost (data
, value
, &depends_on
);
3118 cost
/= AVG_LOOP_NITER (loop
);
3120 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
);
3124 exit
= single_dom_exit (loop
);
3127 /* If there is just a single exit, we may use value of the candidate
3128 after we take it to determine the value of use. */
3129 cost
= get_computation_cost_at (data
, use
, cand
, false, &depends_on
,
3130 last_stmt (exit
->src
));
3132 cost
/= AVG_LOOP_NITER (loop
);
3136 /* Otherwise we just need to compute the iv. */
3137 cost
= get_computation_cost (data
, use
, cand
, false, &depends_on
);
3140 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
);
3143 /* Determines cost of basing replacement of USE on CAND. */
3146 determine_use_iv_cost (struct ivopts_data
*data
,
3147 struct iv_use
*use
, struct iv_cand
*cand
)
3151 case USE_NONLINEAR_EXPR
:
3152 determine_use_iv_cost_generic (data
, use
, cand
);
3156 determine_use_iv_cost_outer (data
, use
, cand
);
3160 determine_use_iv_cost_address (data
, use
, cand
);
3164 determine_use_iv_cost_condition (data
, use
, cand
);
3172 /* Determines costs of basing the use of the iv on an iv candidate. */
3175 determine_use_iv_costs (struct ivopts_data
*data
)
3179 struct iv_cand
*cand
;
3181 data
->consider_all_candidates
= (n_iv_cands (data
)
3182 <= CONSIDER_ALL_CANDIDATES_BOUND
);
3184 alloc_use_cost_map (data
);
3186 if (!data
->consider_all_candidates
)
3188 /* Add the important candidate entries. */
3189 for (j
= 0; j
< n_iv_cands (data
); j
++)
3191 cand
= iv_cand (data
, j
);
3192 if (!cand
->important
)
3194 for (i
= 0; i
< n_iv_uses (data
); i
++)
3196 use
= iv_use (data
, i
);
3197 determine_use_iv_cost (data
, use
, cand
);
3202 for (i
= 0; i
< n_iv_uses (data
); i
++)
3204 use
= iv_use (data
, i
);
3206 if (data
->consider_all_candidates
)
3208 for (j
= 0; j
< n_iv_cands (data
); j
++)
3210 cand
= iv_cand (data
, j
);
3211 determine_use_iv_cost (data
, use
, cand
);
3218 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, j
, bi
)
3220 cand
= iv_cand (data
, j
);
3221 if (!cand
->important
)
3222 determine_use_iv_cost (data
, use
, cand
);
3227 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3229 fprintf (dump_file
, "Use-candidate costs:\n");
3231 for (i
= 0; i
< n_iv_uses (data
); i
++)
3233 use
= iv_use (data
, i
);
3235 fprintf (dump_file
, "Use %d:\n", i
);
3236 fprintf (dump_file
, " cand\tcost\tdepends on\n");
3237 for (j
= 0; j
< use
->n_map_members
; j
++)
3239 if (!use
->cost_map
[j
].cand
3240 || use
->cost_map
[j
].cost
== INFTY
)
3243 fprintf (dump_file
, " %d\t%d\t",
3244 use
->cost_map
[j
].cand
->id
,
3245 use
->cost_map
[j
].cost
);
3246 if (use
->cost_map
[j
].depends_on
)
3247 bitmap_print (dump_file
,
3248 use
->cost_map
[j
].depends_on
, "","");
3249 fprintf (dump_file
, "\n");
3252 fprintf (dump_file
, "\n");
3254 fprintf (dump_file
, "\n");
3258 /* Determines cost of the candidate CAND. */
3261 determine_iv_cost (struct ivopts_data
*data
, struct iv_cand
*cand
)
3263 unsigned cost_base
, cost_step
;
3273 /* There are two costs associated with the candidate -- its increment
3274 and its initialization. The second is almost negligible for any loop
3275 that rolls enough, so we take it just very little into account. */
3277 base
= cand
->iv
->base
;
3278 cost_base
= force_var_cost (data
, base
, NULL
);
3279 cost_step
= add_cost (TYPE_MODE (TREE_TYPE (base
)));
3281 cand
->cost
= cost_step
+ cost_base
/ AVG_LOOP_NITER (current_loop
);
3283 /* Prefer the original iv unless we may gain something by replacing it. */
3284 if (cand
->pos
== IP_ORIGINAL
)
3287 /* Prefer not to insert statements into latch unless there are some
3288 already (so that we do not create unnecessary jumps). */
3289 if (cand
->pos
== IP_END
)
3291 bb
= ip_end_pos (data
->current_loop
);
3292 last
= last_stmt (bb
);
3295 || TREE_CODE (last
) == LABEL_EXPR
)
3300 /* Determines costs of computation of the candidates. */
3303 determine_iv_costs (struct ivopts_data
*data
)
3307 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3309 fprintf (dump_file
, "Candidate costs:\n");
3310 fprintf (dump_file
, " cand\tcost\n");
3313 for (i
= 0; i
< n_iv_cands (data
); i
++)
3315 struct iv_cand
*cand
= iv_cand (data
, i
);
3317 determine_iv_cost (data
, cand
);
3319 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3320 fprintf (dump_file
, " %d\t%d\n", i
, cand
->cost
);
3323 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3324 fprintf (dump_file
, "\n");
3327 /* Calculates cost for having SIZE induction variables. */
3330 ivopts_global_cost_for_size (struct ivopts_data
*data
, unsigned size
)
3332 return global_cost_for_size (size
,
3333 loop_data (data
->current_loop
)->regs_used
,
3337 /* For each size of the induction variable set determine the penalty. */
3340 determine_set_costs (struct ivopts_data
*data
)
3344 struct loop
*loop
= data
->current_loop
;
3347 /* We use the following model (definitely improvable, especially the
3348 cost function -- TODO):
3350 We estimate the number of registers available (using MD data), name it A.
3352 We estimate the number of registers used by the loop, name it U. This
3353 number is obtained as the number of loop phi nodes (not counting virtual
3354 registers and bivs) + the number of variables from outside of the loop.
3356 We set a reserve R (free regs that are used for temporary computations,
3357 etc.). For now the reserve is a constant 3.
3359 Let I be the number of induction variables.
3361 -- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
3362 make a lot of ivs without a reason).
3363 -- if A - R < U + I <= A, the cost is I * PRES_COST
3364 -- if U + I > A, the cost is I * PRES_COST and
3365 number of uses * SPILL_COST * (U + I - A) / (U + I) is added. */
3367 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3369 fprintf (dump_file
, "Global costs:\n");
3370 fprintf (dump_file
, " target_avail_regs %d\n", target_avail_regs
);
3371 fprintf (dump_file
, " target_small_cost %d\n", target_small_cost
);
3372 fprintf (dump_file
, " target_pres_cost %d\n", target_pres_cost
);
3373 fprintf (dump_file
, " target_spill_cost %d\n", target_spill_cost
);
3377 for (phi
= phi_nodes (loop
->header
); phi
; phi
= TREE_CHAIN (phi
))
3379 op
= PHI_RESULT (phi
);
3381 if (!is_gimple_reg (op
))
3384 if (get_iv (data
, op
))
3390 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
3392 struct version_info
*info
= ver_info (data
, j
);
3394 if (info
->inv_id
&& info
->has_nonlin_use
)
3398 loop_data (loop
)->regs_used
= n
;
3399 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3400 fprintf (dump_file
, " regs_used %d\n", n
);
3402 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3404 fprintf (dump_file
, " cost for size:\n");
3405 fprintf (dump_file
, " ivs\tcost\n");
3406 for (j
= 0; j
<= 2 * target_avail_regs
; j
++)
3407 fprintf (dump_file
, " %d\t%d\n", j
,
3408 ivopts_global_cost_for_size (data
, j
));
3409 fprintf (dump_file
, "\n");
3413 /* Finds a best candidate for USE and stores it to CAND. The candidates are
3414 taken from the set SOL and they may depend on invariants in the set INV.
3415 The really used candidate and invariants are noted to USED_IVS and
3419 find_best_candidate (struct ivopts_data
*data
,
3420 struct iv_use
*use
, bitmap sol
, bitmap inv
,
3421 bitmap used_ivs
, bitmap used_inv
, struct iv_cand
**cand
)
3424 unsigned best_cost
= INFTY
, cost
;
3425 struct iv_cand
*cnd
= NULL
, *acnd
;
3426 bitmap depends_on
= NULL
, asol
;
3427 bitmap_iterator bi
, bi1
;
3429 if (data
->consider_all_candidates
)
3433 asol
= BITMAP_XMALLOC ();
3434 bitmap_a_and_b (asol
, sol
, use
->related_cands
);
3437 EXECUTE_IF_SET_IN_BITMAP (asol
, 0, c
, bi
)
3439 acnd
= iv_cand (data
, c
);
3440 cost
= get_use_iv_cost (data
, use
, acnd
, &depends_on
);
3444 if (cost
> best_cost
)
3446 if (cost
== best_cost
)
3448 /* Prefer the cheaper iv. */
3449 if (acnd
->cost
>= cnd
->cost
)
3455 EXECUTE_IF_AND_COMPL_IN_BITMAP (depends_on
, inv
, 0, d
, bi1
)
3460 bitmap_a_or_b (used_inv
, used_inv
, depends_on
);
3469 if (cnd
&& used_ivs
)
3470 bitmap_set_bit (used_ivs
, cnd
->id
);
3475 if (!data
->consider_all_candidates
)
3476 BITMAP_XFREE (asol
);
3481 /* Returns cost of set of ivs SOL + invariants INV. Removes unnecessary
3482 induction variable candidates and invariants from the sets. Only
3483 uses 0 .. MAX_USE - 1 are taken into account. */
3486 set_cost_up_to (struct ivopts_data
*data
, bitmap sol
, bitmap inv
,
3490 unsigned cost
= 0, size
= 0, acost
;
3492 struct iv_cand
*cand
;
3493 bitmap used_ivs
= BITMAP_XMALLOC (), used_inv
= BITMAP_XMALLOC ();
3496 for (i
= 0; i
< max_use
; i
++)
3498 use
= iv_use (data
, i
);
3499 acost
= find_best_candidate (data
, use
, sol
, inv
,
3500 used_ivs
, used_inv
, NULL
);
3503 BITMAP_XFREE (used_ivs
);
3504 BITMAP_XFREE (used_inv
);
3510 EXECUTE_IF_SET_IN_BITMAP (used_ivs
, 0, i
, bi
)
3512 cand
= iv_cand (data
, i
);
3514 /* Do not count the pseudocandidates. */
3520 EXECUTE_IF_SET_IN_BITMAP (used_inv
, 0, i
, bi
)
3524 cost
+= ivopts_global_cost_for_size (data
, size
);
3526 bitmap_copy (sol
, used_ivs
);
3527 bitmap_copy (inv
, used_inv
);
3529 BITMAP_XFREE (used_ivs
);
3530 BITMAP_XFREE (used_inv
);
3535 /* Computes cost of set of ivs SOL + invariants INV. Removes unnecessary
3536 induction variable candidates and invariants from the sets. */
3539 set_cost (struct ivopts_data
*data
, bitmap sol
, bitmap inv
)
3541 return set_cost_up_to (data
, sol
, inv
, n_iv_uses (data
));
3544 /* Tries to extend the sets IVS and INV in the best possible way in order
3545 to express the USE. */
3548 try_add_cand_for (struct ivopts_data
*data
, bitmap ivs
, bitmap inv
,
3551 unsigned best_cost
= set_cost_up_to (data
, ivs
, inv
, use
->id
+ 1), act_cost
;
3552 bitmap best_ivs
= BITMAP_XMALLOC ();
3553 bitmap best_inv
= BITMAP_XMALLOC ();
3554 bitmap act_ivs
= BITMAP_XMALLOC ();
3555 bitmap act_inv
= BITMAP_XMALLOC ();
3557 struct cost_pair
*cp
;
3559 bitmap_copy (best_ivs
, ivs
);
3560 bitmap_copy (best_inv
, inv
);
3562 for (i
= 0; i
< use
->n_map_members
; i
++)
3564 cp
= use
->cost_map
+ i
;
3565 if (cp
->cost
== INFTY
)
3568 bitmap_copy (act_ivs
, ivs
);
3569 bitmap_set_bit (act_ivs
, cp
->cand
->id
);
3571 bitmap_a_or_b (act_inv
, inv
, cp
->depends_on
);
3573 bitmap_copy (act_inv
, inv
);
3574 act_cost
= set_cost_up_to (data
, act_ivs
, act_inv
, use
->id
+ 1);
3576 if (act_cost
< best_cost
)
3578 best_cost
= act_cost
;
3579 bitmap_copy (best_ivs
, act_ivs
);
3580 bitmap_copy (best_inv
, act_inv
);
3584 bitmap_copy (ivs
, best_ivs
);
3585 bitmap_copy (inv
, best_inv
);
3587 BITMAP_XFREE (best_ivs
);
3588 BITMAP_XFREE (best_inv
);
3589 BITMAP_XFREE (act_ivs
);
3590 BITMAP_XFREE (act_inv
);
3592 return (best_cost
!= INFTY
);
3595 /* Finds an initial set of IVS and invariants INV. We do this by simply
3596 choosing the best candidate for each use. */
3599 get_initial_solution (struct ivopts_data
*data
, bitmap ivs
, bitmap inv
)
3603 for (i
= 0; i
< n_iv_uses (data
); i
++)
3604 if (!try_add_cand_for (data
, ivs
, inv
, iv_use (data
, i
)))
3607 return set_cost (data
, ivs
, inv
);
3610 /* Tries to improve set of induction variables IVS and invariants INV to get
3611 it better than COST. */
3614 try_improve_iv_set (struct ivopts_data
*data
,
3615 bitmap ivs
, bitmap inv
, unsigned *cost
)
3618 bitmap new_ivs
= BITMAP_XMALLOC (), new_inv
= BITMAP_XMALLOC ();
3619 bitmap best_new_ivs
= NULL
, best_new_inv
= NULL
;
3621 /* Try altering the set of induction variables by one. */
3622 for (i
= 0; i
< n_iv_cands (data
); i
++)
3624 bitmap_copy (new_ivs
, ivs
);
3625 bitmap_copy (new_inv
, inv
);
3627 if (bitmap_bit_p (ivs
, i
))
3628 bitmap_clear_bit (new_ivs
, i
);
3630 bitmap_set_bit (new_ivs
, i
);
3632 acost
= set_cost (data
, new_ivs
, new_inv
);
3638 best_new_ivs
= BITMAP_XMALLOC ();
3639 best_new_inv
= BITMAP_XMALLOC ();
3643 bitmap_copy (best_new_ivs
, new_ivs
);
3644 bitmap_copy (best_new_inv
, new_inv
);
3647 /* Ditto for invariants. */
3648 for (i
= 1; i
<= data
->max_inv_id
; i
++)
3650 if (ver_info (data
, i
)->has_nonlin_use
)
3653 bitmap_copy (new_ivs
, ivs
);
3654 bitmap_copy (new_inv
, inv
);
3656 if (bitmap_bit_p (inv
, i
))
3657 bitmap_clear_bit (new_inv
, i
);
3659 bitmap_set_bit (new_inv
, i
);
3661 acost
= set_cost (data
, new_ivs
, new_inv
);
3667 best_new_ivs
= BITMAP_XMALLOC ();
3668 best_new_inv
= BITMAP_XMALLOC ();
3672 bitmap_copy (best_new_ivs
, new_ivs
);
3673 bitmap_copy (best_new_inv
, new_inv
);
3676 BITMAP_XFREE (new_ivs
);
3677 BITMAP_XFREE (new_inv
);
3682 bitmap_copy (ivs
, best_new_ivs
);
3683 bitmap_copy (inv
, best_new_inv
);
3684 BITMAP_XFREE (best_new_ivs
);
3685 BITMAP_XFREE (best_new_inv
);
3689 /* Attempts to find the optimal set of induction variables. We do simple
3690 greedy heuristic -- we try to replace at most one candidate in the selected
3691 solution and remove the unused ivs while this improves the cost. */
3694 find_optimal_iv_set (struct ivopts_data
*data
)
3697 bitmap set
= BITMAP_XMALLOC ();
3698 bitmap inv
= BITMAP_XMALLOC ();
3701 /* Set the upper bound. */
3702 cost
= get_initial_solution (data
, set
, inv
);
3705 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3706 fprintf (dump_file
, "Unable to substitute for ivs, failed.\n");
3712 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3714 fprintf (dump_file
, "Initial set of candidates (cost %d): ", cost
);
3715 bitmap_print (dump_file
, set
, "", "");
3716 fprintf (dump_file
, " invariants ");
3717 bitmap_print (dump_file
, inv
, "", "");
3718 fprintf (dump_file
, "\n");
3721 while (try_improve_iv_set (data
, set
, inv
, &cost
))
3723 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3725 fprintf (dump_file
, "Improved to (cost %d): ", cost
);
3726 bitmap_print (dump_file
, set
, "", "");
3727 fprintf (dump_file
, " invariants ");
3728 bitmap_print (dump_file
, inv
, "", "");
3729 fprintf (dump_file
, "\n");
3733 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3734 fprintf (dump_file
, "Final cost %d\n\n", cost
);
3736 for (i
= 0; i
< n_iv_uses (data
); i
++)
3738 use
= iv_use (data
, i
);
3739 find_best_candidate (data
, use
, set
, inv
, NULL
, NULL
, &use
->selected
);
3747 /* Creates a new induction variable corresponding to CAND. */
3750 create_new_iv (struct ivopts_data
*data
, struct iv_cand
*cand
)
3752 block_stmt_iterator incr_pos
;
3762 incr_pos
= bsi_last (ip_normal_pos (data
->current_loop
));
3766 incr_pos
= bsi_last (ip_end_pos (data
->current_loop
));
3771 /* Mark that the iv is preserved. */
3772 name_info (data
, cand
->var_before
)->preserve_biv
= true;
3773 name_info (data
, cand
->var_after
)->preserve_biv
= true;
3775 /* Rewrite the increment so that it uses var_before directly. */
3776 find_interesting_uses_op (data
, cand
->var_after
)->selected
= cand
;
3781 gimple_add_tmp_var (cand
->var_before
);
3782 add_referenced_tmp_var (cand
->var_before
);
3784 base
= unshare_expr (cand
->iv
->base
);
3786 create_iv (base
, cand
->iv
->step
, cand
->var_before
, data
->current_loop
,
3787 &incr_pos
, after
, &cand
->var_before
, &cand
->var_after
);
3790 /* Creates new induction variables described in SET. */
3793 create_new_ivs (struct ivopts_data
*data
, bitmap set
)
3796 struct iv_cand
*cand
;
3799 EXECUTE_IF_SET_IN_BITMAP (set
, 0, i
, bi
)
3801 cand
= iv_cand (data
, i
);
3802 create_new_iv (data
, cand
);
3806 /* Removes statement STMT (real or a phi node). If INCLUDING_DEFINED_NAME
3807 is true, remove also the ssa name defined by the statement. */
3810 remove_statement (tree stmt
, bool including_defined_name
)
3812 if (TREE_CODE (stmt
) == PHI_NODE
)
3814 if (!including_defined_name
)
3816 /* Prevent the ssa name defined by the statement from being removed. */
3817 SET_PHI_RESULT (stmt
, NULL
);
3819 remove_phi_node (stmt
, NULL_TREE
, bb_for_stmt (stmt
));
3823 block_stmt_iterator bsi
= stmt_for_bsi (stmt
);
3829 /* Rewrites USE (definition of iv used in a nonlinear expression)
3830 using candidate CAND. */
3833 rewrite_use_nonlinear_expr (struct ivopts_data
*data
,
3834 struct iv_use
*use
, struct iv_cand
*cand
)
3836 tree comp
= unshare_expr (get_computation (data
->current_loop
,
3838 tree op
, stmts
, tgt
, ass
;
3839 block_stmt_iterator bsi
, pbsi
;
3841 switch (TREE_CODE (use
->stmt
))
3844 tgt
= PHI_RESULT (use
->stmt
);
3846 /* If we should keep the biv, do not replace it. */
3847 if (name_info (data
, tgt
)->preserve_biv
)
3850 pbsi
= bsi
= bsi_start (bb_for_stmt (use
->stmt
));
3851 while (!bsi_end_p (pbsi
)
3852 && TREE_CODE (bsi_stmt (pbsi
)) == LABEL_EXPR
)
3860 tgt
= TREE_OPERAND (use
->stmt
, 0);
3861 bsi
= stmt_for_bsi (use
->stmt
);
3868 op
= force_gimple_operand (comp
, &stmts
, false, SSA_NAME_VAR (tgt
));
3870 if (TREE_CODE (use
->stmt
) == PHI_NODE
)
3873 bsi_insert_after (&bsi
, stmts
, BSI_CONTINUE_LINKING
);
3874 ass
= build2 (MODIFY_EXPR
, TREE_TYPE (tgt
), tgt
, op
);
3875 bsi_insert_after (&bsi
, ass
, BSI_NEW_STMT
);
3876 remove_statement (use
->stmt
, false);
3877 SSA_NAME_DEF_STMT (tgt
) = ass
;
3882 bsi_insert_before (&bsi
, stmts
, BSI_SAME_STMT
);
3883 TREE_OPERAND (use
->stmt
, 1) = op
;
3887 /* Replaces ssa name in index IDX by its basic variable. Callback for
3891 idx_remove_ssa_names (tree base
, tree
*idx
,
3892 void *data ATTRIBUTE_UNUSED
)
3896 if (TREE_CODE (*idx
) == SSA_NAME
)
3897 *idx
= SSA_NAME_VAR (*idx
);
3899 if (TREE_CODE (base
) == ARRAY_REF
)
3901 op
= &TREE_OPERAND (base
, 2);
3903 && TREE_CODE (*op
) == SSA_NAME
)
3904 *op
= SSA_NAME_VAR (*op
);
3905 op
= &TREE_OPERAND (base
, 3);
3907 && TREE_CODE (*op
) == SSA_NAME
)
3908 *op
= SSA_NAME_VAR (*op
);
3914 /* Unshares REF and replaces ssa names inside it by their basic variables. */
3917 unshare_and_remove_ssa_names (tree ref
)
3919 ref
= unshare_expr (ref
);
3920 for_each_index (&ref
, idx_remove_ssa_names
, NULL
);
3925 /* Rewrites base of memory access OP with expression WITH in statement
3926 pointed to by BSI. */
3929 rewrite_address_base (block_stmt_iterator
*bsi
, tree
*op
, tree with
)
3931 tree bvar
, var
, new_var
, new_name
, copy
, name
;
3934 var
= bvar
= get_base_address (*op
);
3936 if (!var
|| TREE_CODE (with
) != SSA_NAME
)
3939 gcc_assert (TREE_CODE (var
) != ALIGN_INDIRECT_REF
);
3940 gcc_assert (TREE_CODE (var
) != MISALIGNED_INDIRECT_REF
);
3941 if (TREE_CODE (var
) == INDIRECT_REF
)
3942 var
= TREE_OPERAND (var
, 0);
3943 if (TREE_CODE (var
) == SSA_NAME
)
3946 var
= SSA_NAME_VAR (var
);
3948 else if (DECL_P (var
))
3953 if (var_ann (var
)->type_mem_tag
)
3954 var
= var_ann (var
)->type_mem_tag
;
3956 /* We need to add a memory tag for the variable. But we do not want
3957 to add it to the temporary used for the computations, since this leads
3958 to problems in redundancy elimination when there are common parts
3959 in two computations referring to the different arrays. So we copy
3960 the variable to a new temporary. */
3961 copy
= build2 (MODIFY_EXPR
, void_type_node
, NULL_TREE
, with
);
3963 new_name
= duplicate_ssa_name (name
, copy
);
3966 new_var
= create_tmp_var (TREE_TYPE (with
), "ruatmp");
3967 add_referenced_tmp_var (new_var
);
3968 var_ann (new_var
)->type_mem_tag
= var
;
3969 new_name
= make_ssa_name (new_var
, copy
);
3971 TREE_OPERAND (copy
, 0) = new_name
;
3972 bsi_insert_before (bsi
, copy
, BSI_SAME_STMT
);
3978 gcc_assert (TREE_CODE (*op
) != ALIGN_INDIRECT_REF
);
3979 gcc_assert (TREE_CODE (*op
) != MISALIGNED_INDIRECT_REF
);
3981 if (TREE_CODE (*op
) == INDIRECT_REF
)
3982 orig
= REF_ORIGINAL (*op
);
3984 orig
= unshare_and_remove_ssa_names (*op
);
3986 *op
= build1 (INDIRECT_REF
, TREE_TYPE (*op
), with
);
3988 /* Record the original reference, for purposes of alias analysis. */
3989 REF_ORIGINAL (*op
) = orig
;
3992 /* Rewrites USE (address that is an iv) using candidate CAND. */
3995 rewrite_use_address (struct ivopts_data
*data
,
3996 struct iv_use
*use
, struct iv_cand
*cand
)
3998 tree comp
= unshare_expr (get_computation (data
->current_loop
,
4000 block_stmt_iterator bsi
= stmt_for_bsi (use
->stmt
);
4002 tree op
= force_gimple_operand (comp
, &stmts
, true, NULL_TREE
);
4005 bsi_insert_before (&bsi
, stmts
, BSI_SAME_STMT
);
4007 rewrite_address_base (&bsi
, use
->op_p
, op
);
4010 /* Rewrites USE (the condition such that one of the arguments is an iv) using
4014 rewrite_use_compare (struct ivopts_data
*data
,
4015 struct iv_use
*use
, struct iv_cand
*cand
)
4018 tree
*op_p
, cond
, op
, stmts
, bound
;
4019 block_stmt_iterator bsi
= stmt_for_bsi (use
->stmt
);
4020 enum tree_code compare
;
4022 if (may_eliminate_iv (data
->current_loop
,
4023 use
, cand
, &compare
, &bound
))
4025 op
= force_gimple_operand (unshare_expr (bound
), &stmts
,
4029 bsi_insert_before (&bsi
, stmts
, BSI_SAME_STMT
);
4031 *use
->op_p
= build2 (compare
, boolean_type_node
,
4032 var_at_stmt (data
->current_loop
,
4033 cand
, use
->stmt
), op
);
4034 modify_stmt (use
->stmt
);
4038 /* The induction variable elimination failed; just express the original
4040 comp
= unshare_expr (get_computation (data
->current_loop
, use
, cand
));
4043 op_p
= &TREE_OPERAND (cond
, 0);
4044 if (TREE_CODE (*op_p
) != SSA_NAME
4045 || zero_p (get_iv (data
, *op_p
)->step
))
4046 op_p
= &TREE_OPERAND (cond
, 1);
4048 op
= force_gimple_operand (comp
, &stmts
, true, SSA_NAME_VAR (*op_p
));
4050 bsi_insert_before (&bsi
, stmts
, BSI_SAME_STMT
);
4055 /* Ensure that operand *OP_P may be used at the end of EXIT without
4056 violating loop closed ssa form. */
4059 protect_loop_closed_ssa_form_use (edge exit
, use_operand_p op_p
)
4062 struct loop
*def_loop
;
4065 use
= USE_FROM_PTR (op_p
);
4066 if (TREE_CODE (use
) != SSA_NAME
)
4069 def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (use
));
4073 def_loop
= def_bb
->loop_father
;
4074 if (flow_bb_inside_loop_p (def_loop
, exit
->dest
))
4077 /* Try finding a phi node that copies the value out of the loop. */
4078 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= TREE_CHAIN (phi
))
4079 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == use
)
4084 /* Create such a phi node. */
4085 tree new_name
= duplicate_ssa_name (use
, NULL
);
4087 phi
= create_phi_node (new_name
, exit
->dest
);
4088 SSA_NAME_DEF_STMT (new_name
) = phi
;
4089 add_phi_arg (&phi
, use
, exit
);
4092 SET_USE (op_p
, PHI_RESULT (phi
));
4095 /* Ensure that operands of STMT may be used at the end of EXIT without
4096 violating loop closed ssa form. */
4099 protect_loop_closed_ssa_form (edge exit
, tree stmt
)
4103 v_may_def_optype v_may_defs
;
4106 get_stmt_operands (stmt
);
4108 uses
= STMT_USE_OPS (stmt
);
4109 for (i
= 0; i
< NUM_USES (uses
); i
++)
4110 protect_loop_closed_ssa_form_use (exit
, USE_OP_PTR (uses
, i
));
4112 vuses
= STMT_VUSE_OPS (stmt
);
4113 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
4114 protect_loop_closed_ssa_form_use (exit
, VUSE_OP_PTR (vuses
, i
));
4116 v_may_defs
= STMT_V_MAY_DEF_OPS (stmt
);
4117 for (i
= 0; i
< NUM_V_MAY_DEFS (v_may_defs
); i
++)
4118 protect_loop_closed_ssa_form_use (exit
, V_MAY_DEF_OP_PTR (v_may_defs
, i
));
4121 /* STMTS compute a value of a phi argument OP on EXIT of a loop. Arrange things
4122 so that they are emitted on the correct place, and so that the loop closed
4123 ssa form is preserved. */
4126 compute_phi_arg_on_exit (edge exit
, tree stmts
, tree op
)
4128 tree_stmt_iterator tsi
;
4129 block_stmt_iterator bsi
;
4130 tree phi
, stmt
, def
, next
;
4132 if (EDGE_COUNT (exit
->dest
->preds
) > 1)
4133 split_loop_exit_edge (exit
);
4135 if (TREE_CODE (stmts
) == STATEMENT_LIST
)
4137 for (tsi
= tsi_start (stmts
); !tsi_end_p (tsi
); tsi_next (&tsi
))
4138 protect_loop_closed_ssa_form (exit
, tsi_stmt (tsi
));
4141 protect_loop_closed_ssa_form (exit
, stmts
);
4143 /* Ensure there is label in exit->dest, so that we can
4145 tree_block_label (exit
->dest
);
4146 bsi
= bsi_after_labels (exit
->dest
);
4147 bsi_insert_after (&bsi
, stmts
, BSI_CONTINUE_LINKING
);
4152 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= next
)
4154 next
= TREE_CHAIN (phi
);
4156 if (PHI_ARG_DEF_FROM_EDGE (phi
, exit
) == op
)
4158 def
= PHI_RESULT (phi
);
4159 remove_statement (phi
, false);
4160 stmt
= build2 (MODIFY_EXPR
, TREE_TYPE (op
),
4162 SSA_NAME_DEF_STMT (def
) = stmt
;
4163 bsi_insert_after (&bsi
, stmt
, BSI_CONTINUE_LINKING
);
4168 /* Rewrites the final value of USE (that is only needed outside of the loop)
4169 using candidate CAND. */
4172 rewrite_use_outer (struct ivopts_data
*data
,
4173 struct iv_use
*use
, struct iv_cand
*cand
)
4176 tree value
, op
, stmts
, tgt
;
4179 switch (TREE_CODE (use
->stmt
))
4182 tgt
= PHI_RESULT (use
->stmt
);
4185 tgt
= TREE_OPERAND (use
->stmt
, 0);
4191 exit
= single_dom_exit (data
->current_loop
);
4197 bool ok
= may_replace_final_value (data
->current_loop
, use
, &value
);
4201 value
= get_computation_at (data
->current_loop
,
4202 use
, cand
, last_stmt (exit
->src
));
4204 value
= unshare_expr (value
);
4205 op
= force_gimple_operand (value
, &stmts
, true, SSA_NAME_VAR (tgt
));
4207 /* If we will preserve the iv anyway and we would need to perform
4208 some computation to replace the final value, do nothing. */
4209 if (stmts
&& name_info (data
, tgt
)->preserve_biv
)
4212 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= TREE_CHAIN (phi
))
4214 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, exit
);
4216 if (USE_FROM_PTR (use_p
) == tgt
)
4217 SET_USE (use_p
, op
);
4221 compute_phi_arg_on_exit (exit
, stmts
, op
);
4223 /* Enable removal of the statement. We cannot remove it directly,
4224 since we may still need the aliasing information attached to the
4225 ssa name defined by it. */
4226 name_info (data
, tgt
)->iv
->have_use_for
= false;
4230 /* If the variable is going to be preserved anyway, there is nothing to
4232 if (name_info (data
, tgt
)->preserve_biv
)
4235 /* Otherwise we just need to compute the iv. */
4236 rewrite_use_nonlinear_expr (data
, use
, cand
);
4239 /* Rewrites USE using candidate CAND. */
4242 rewrite_use (struct ivopts_data
*data
,
4243 struct iv_use
*use
, struct iv_cand
*cand
)
4247 case USE_NONLINEAR_EXPR
:
4248 rewrite_use_nonlinear_expr (data
, use
, cand
);
4252 rewrite_use_outer (data
, use
, cand
);
4256 rewrite_use_address (data
, use
, cand
);
4260 rewrite_use_compare (data
, use
, cand
);
4266 modify_stmt (use
->stmt
);
4269 /* Rewrite the uses using the selected induction variables. */
4272 rewrite_uses (struct ivopts_data
*data
)
4275 struct iv_cand
*cand
;
4278 for (i
= 0; i
< n_iv_uses (data
); i
++)
4280 use
= iv_use (data
, i
);
4281 cand
= use
->selected
;
4284 rewrite_use (data
, use
, cand
);
4288 /* Removes the ivs that are not used after rewriting. */
4291 remove_unused_ivs (struct ivopts_data
*data
)
4296 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
4298 struct version_info
*info
;
4300 info
= ver_info (data
, j
);
4302 && !zero_p (info
->iv
->step
)
4304 && !info
->iv
->have_use_for
4305 && !info
->preserve_biv
)
4306 remove_statement (SSA_NAME_DEF_STMT (info
->iv
->ssa_name
), true);
4310 /* Frees data allocated by the optimization of a single loop. */
4313 free_loop_data (struct ivopts_data
*data
)
4318 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
4320 struct version_info
*info
;
4322 info
= ver_info (data
, i
);
4326 info
->has_nonlin_use
= false;
4327 info
->preserve_biv
= false;
4330 bitmap_clear (data
->relevant
);
4332 for (i
= 0; i
< n_iv_uses (data
); i
++)
4334 struct iv_use
*use
= iv_use (data
, i
);
4337 BITMAP_XFREE (use
->related_cands
);
4338 for (j
= 0; j
< use
->n_map_members
; j
++)
4339 if (use
->cost_map
[j
].depends_on
)
4340 BITMAP_XFREE (use
->cost_map
[j
].depends_on
);
4341 free (use
->cost_map
);
4344 VARRAY_POP_ALL (data
->iv_uses
);
4346 for (i
= 0; i
< n_iv_cands (data
); i
++)
4348 struct iv_cand
*cand
= iv_cand (data
, i
);
4354 VARRAY_POP_ALL (data
->iv_candidates
);
4356 if (data
->version_info_size
< num_ssa_names
)
4358 data
->version_info_size
= 2 * num_ssa_names
;
4359 free (data
->version_info
);
4360 data
->version_info
= xcalloc (data
->version_info_size
,
4361 sizeof (struct version_info
));
4364 data
->max_inv_id
= 0;
4366 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (decl_rtl_to_reset
); i
++)
4368 tree obj
= VARRAY_GENERIC_PTR_NOGC (decl_rtl_to_reset
, i
);
4370 SET_DECL_RTL (obj
, NULL_RTX
);
4372 VARRAY_POP_ALL (decl_rtl_to_reset
);
4375 /* Finalizes data structures used by the iv optimization pass. LOOPS is the
4379 tree_ssa_iv_optimize_finalize (struct loops
*loops
, struct ivopts_data
*data
)
4383 for (i
= 1; i
< loops
->num
; i
++)
4384 if (loops
->parray
[i
])
4386 free (loops
->parray
[i
]->aux
);
4387 loops
->parray
[i
]->aux
= NULL
;
4390 free_loop_data (data
);
4391 free (data
->version_info
);
4392 BITMAP_XFREE (data
->relevant
);
4394 VARRAY_FREE (decl_rtl_to_reset
);
4395 VARRAY_FREE (data
->iv_uses
);
4396 VARRAY_FREE (data
->iv_candidates
);
4399 /* Optimizes the LOOP. Returns true if anything changed. */
4402 tree_ssa_iv_optimize_loop (struct ivopts_data
*data
, struct loop
*loop
)
4404 bool changed
= false;
4408 data
->current_loop
= loop
;
4410 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4412 fprintf (dump_file
, "Processing loop %d\n", loop
->num
);
4414 exit
= single_dom_exit (loop
);
4417 fprintf (dump_file
, " single exit %d -> %d, exit condition ",
4418 exit
->src
->index
, exit
->dest
->index
);
4419 print_generic_expr (dump_file
, last_stmt (exit
->src
), TDF_SLIM
);
4420 fprintf (dump_file
, "\n");
4423 fprintf (dump_file
, "\n");
4426 /* For each ssa name determines whether it behaves as an induction variable
4428 if (!find_induction_variables (data
))
4431 /* Finds interesting uses (item 1). */
4432 find_interesting_uses (data
);
4433 if (n_iv_uses (data
) > MAX_CONSIDERED_USES
)
4436 /* Finds candidates for the induction variables (item 2). */
4437 find_iv_candidates (data
);
4439 /* Calculates the costs (item 3, part 1). */
4440 determine_use_iv_costs (data
);
4441 determine_iv_costs (data
);
4442 determine_set_costs (data
);
4444 /* Find the optimal set of induction variables (item 3, part 2). */
4445 iv_set
= find_optimal_iv_set (data
);
4450 /* Create the new induction variables (item 4, part 1). */
4451 create_new_ivs (data
, iv_set
);
4453 /* Rewrite the uses (item 4, part 2). */
4454 rewrite_uses (data
);
4456 /* Remove the ivs that are unused after rewriting. */
4457 remove_unused_ivs (data
);
4459 loop_commit_inserts ();
4461 BITMAP_XFREE (iv_set
);
4463 /* We have changed the structure of induction variables; it might happen
4464 that definitions in the scev database refer to some of them that were
4469 free_loop_data (data
);
4474 /* Main entry point. Optimizes induction variables in LOOPS. */
4477 tree_ssa_iv_optimize (struct loops
*loops
)
4480 struct ivopts_data data
;
4482 tree_ssa_iv_optimize_init (loops
, &data
);
4484 /* Optimize the loops starting with the innermost ones. */
4485 loop
= loops
->tree_root
;
4489 #ifdef ENABLE_CHECKING
4490 verify_loop_closed_ssa ();
4494 /* Scan the loops, inner ones first. */
4495 while (loop
!= loops
->tree_root
)
4497 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4498 flow_loop_dump (loop
, dump_file
, NULL
, 1);
4499 if (tree_ssa_iv_optimize_loop (&data
, loop
))
4501 #ifdef ENABLE_CHECKING
4502 verify_loop_closed_ssa ();
4517 tree_ssa_iv_optimize_finalize (loops
, &data
);