1 /* Induction variable optimizations.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This pass tries to find the optimal set of induction variables for the loop.
21 It optimizes just the basic linear induction variables (although adding
22 support for other types should not be too hard). It includes the
23 optimizations commonly known as strength reduction, induction variable
24 coalescing and induction variable elimination. It does it in the
27 1) The interesting uses of induction variables are found. This includes
29 -- uses of induction variables in non-linear expressions
30 -- addresses of arrays
31 -- comparisons of induction variables
33 2) Candidates for the induction variables are found. This includes
35 -- old induction variables
36 -- the variables defined by expressions derived from the "interesting
39 3) The optimal (w.r. to a cost function) set of variables is chosen. The
40 cost function assigns a cost to sets of induction variables and consists
43 -- The use costs. Each of the interesting uses chooses the best induction
44 variable in the set and adds its cost to the sum. The cost reflects
45 the time spent on modifying the induction variables value to be usable
46 for the given purpose (adding base and offset for arrays, etc.).
47 -- The variable costs. Each of the variables has a cost assigned that
48 reflects the costs associated with incrementing the value of the
49 variable. The original variables are somewhat preferred.
50 -- The set cost. Depending on the size of the set, extra cost may be
51 added to reflect register pressure.
53 All the costs are defined in a machine-specific way, using the target
54 hooks and machine descriptions to determine them.
56 4) The trees are transformed to use the new variables, the dead code is
59 All of this is done loop by loop. Doing it globally is theoretically
60 possible, it might give a better performance and it might enable us
61 to decide costs more precisely, but getting all the interactions right
62 would be complicated. */
66 #include "coretypes.h"
70 #include "basic-block.h"
71 #include "gimple-pretty-print.h"
74 #include "tree-pass.h"
76 #include "insn-config.h"
77 #include "pointer-set.h"
78 #include "hash-table.h"
79 #include "tree-chrec.h"
80 #include "tree-scalar-evolution.h"
83 #include "langhooks.h"
84 #include "tree-affine.h"
86 #include "tree-inline.h"
87 #include "tree-ssa-propagate.h"
90 /* FIXME: Expressions are expanded to RTL in this pass to determine the
91 cost of different addressing modes. This should be moved to a TBD
92 interface between the GIMPLE and RTL worlds. */
96 /* The infinite cost. */
97 #define INFTY 10000000
99 #define AVG_LOOP_NITER(LOOP) 5
101 /* Returns the expected number of loop iterations for LOOP.
102 The average trip count is computed from profile data if it
105 static inline HOST_WIDE_INT
106 avg_loop_niter (struct loop
*loop
)
108 HOST_WIDE_INT niter
= estimated_stmt_executions_int (loop
);
110 return AVG_LOOP_NITER (loop
);
115 /* Representation of the induction variable. */
118 tree base
; /* Initial value of the iv. */
119 tree base_object
; /* A memory object to that the induction variable points. */
120 tree step
; /* Step of the iv (constant only). */
121 tree ssa_name
; /* The ssa name with the value. */
122 bool biv_p
; /* Is it a biv? */
123 bool have_use_for
; /* Do we already have a use for it? */
124 unsigned use_id
; /* The identifier in the use if it is the case. */
127 /* Per-ssa version information (induction variable descriptions, etc.). */
130 tree name
; /* The ssa name. */
131 struct iv
*iv
; /* Induction variable description. */
132 bool has_nonlin_use
; /* For a loop-level invariant, whether it is used in
133 an expression that is not an induction variable. */
134 bool preserve_biv
; /* For the original biv, whether to preserve it. */
135 unsigned inv_id
; /* Id of an invariant. */
141 USE_NONLINEAR_EXPR
, /* Use in a nonlinear expression. */
142 USE_ADDRESS
, /* Use in an address. */
143 USE_COMPARE
/* Use is a compare. */
146 /* Cost of a computation. */
149 int cost
; /* The runtime cost. */
150 unsigned complexity
; /* The estimate of the complexity of the code for
151 the computation (in no concrete units --
152 complexity field should be larger for more
153 complex expressions and addressing modes). */
156 static const comp_cost no_cost
= {0, 0};
157 static const comp_cost infinite_cost
= {INFTY
, INFTY
};
159 /* The candidate - cost pair. */
162 struct iv_cand
*cand
; /* The candidate. */
163 comp_cost cost
; /* The cost. */
164 bitmap depends_on
; /* The list of invariants that have to be
166 tree value
; /* For final value elimination, the expression for
167 the final value of the iv. For iv elimination,
168 the new bound to compare with. */
169 enum tree_code comp
; /* For iv elimination, the comparison. */
170 int inv_expr_id
; /* Loop invariant expression id. */
176 unsigned id
; /* The id of the use. */
177 enum use_type type
; /* Type of the use. */
178 struct iv
*iv
; /* The induction variable it is based on. */
179 gimple stmt
; /* Statement in that it occurs. */
180 tree
*op_p
; /* The place where it occurs. */
181 bitmap related_cands
; /* The set of "related" iv candidates, plus the common
184 unsigned n_map_members
; /* Number of candidates in the cost_map list. */
185 struct cost_pair
*cost_map
;
186 /* The costs wrto the iv candidates. */
188 struct iv_cand
*selected
;
189 /* The selected candidate. */
192 /* The position where the iv is computed. */
195 IP_NORMAL
, /* At the end, just before the exit condition. */
196 IP_END
, /* At the end of the latch block. */
197 IP_BEFORE_USE
, /* Immediately before a specific use. */
198 IP_AFTER_USE
, /* Immediately after a specific use. */
199 IP_ORIGINAL
/* The original biv. */
202 /* The induction variable candidate. */
205 unsigned id
; /* The number of the candidate. */
206 bool important
; /* Whether this is an "important" candidate, i.e. such
207 that it should be considered by all uses. */
208 ENUM_BITFIELD(iv_position
) pos
: 8; /* Where it is computed. */
209 gimple incremented_at
;/* For original biv, the statement where it is
211 tree var_before
; /* The variable used for it before increment. */
212 tree var_after
; /* The variable used for it after increment. */
213 struct iv
*iv
; /* The value of the candidate. NULL for
214 "pseudocandidate" used to indicate the possibility
215 to replace the final value of an iv by direct
216 computation of the value. */
217 unsigned cost
; /* Cost of the candidate. */
218 unsigned cost_step
; /* Cost of the candidate's increment operation. */
219 struct iv_use
*ainc_use
; /* For IP_{BEFORE,AFTER}_USE candidates, the place
220 where it is incremented. */
221 bitmap depends_on
; /* The list of invariants that are used in step of the
225 /* Loop invariant expression hashtable entry. */
226 struct iv_inv_expr_ent
233 /* The data used by the induction variable optimizations. */
235 typedef struct iv_use
*iv_use_p
;
237 typedef struct iv_cand
*iv_cand_p
;
239 /* Hashtable helpers. */
241 struct iv_inv_expr_hasher
: typed_free_remove
<iv_inv_expr_ent
>
243 typedef iv_inv_expr_ent value_type
;
244 typedef iv_inv_expr_ent compare_type
;
245 static inline hashval_t
hash (const value_type
*);
246 static inline bool equal (const value_type
*, const compare_type
*);
249 /* Hash function for loop invariant expressions. */
252 iv_inv_expr_hasher::hash (const value_type
*expr
)
257 /* Hash table equality function for expressions. */
260 iv_inv_expr_hasher::equal (const value_type
*expr1
, const compare_type
*expr2
)
262 return expr1
->hash
== expr2
->hash
263 && operand_equal_p (expr1
->expr
, expr2
->expr
, 0);
268 /* The currently optimized loop. */
269 struct loop
*current_loop
;
271 /* Numbers of iterations for all exits of the current loop. */
272 struct pointer_map_t
*niters
;
274 /* Number of registers used in it. */
277 /* The size of version_info array allocated. */
278 unsigned version_info_size
;
280 /* The array of information for the ssa names. */
281 struct version_info
*version_info
;
283 /* The hashtable of loop invariant expressions created
285 hash_table
<iv_inv_expr_hasher
> inv_expr_tab
;
287 /* Loop invariant expression id. */
290 /* The bitmap of indices in version_info whose value was changed. */
293 /* The uses of induction variables. */
294 vec
<iv_use_p
> iv_uses
;
296 /* The candidates. */
297 vec
<iv_cand_p
> iv_candidates
;
299 /* A bitmap of important candidates. */
300 bitmap important_candidates
;
302 /* The maximum invariant id. */
305 /* Whether to consider just related and important candidates when replacing a
307 bool consider_all_candidates
;
309 /* Are we optimizing for speed? */
312 /* Whether the loop body includes any function calls. */
313 bool body_includes_call
;
315 /* Whether the loop body can only be exited via single exit. */
316 bool loop_single_exit_p
;
319 /* An assignment of iv candidates to uses. */
323 /* The number of uses covered by the assignment. */
326 /* Number of uses that cannot be expressed by the candidates in the set. */
329 /* Candidate assigned to a use, together with the related costs. */
330 struct cost_pair
**cand_for_use
;
332 /* Number of times each candidate is used. */
333 unsigned *n_cand_uses
;
335 /* The candidates used. */
338 /* The number of candidates in the set. */
341 /* Total number of registers needed. */
344 /* Total cost of expressing uses. */
345 comp_cost cand_use_cost
;
347 /* Total cost of candidates. */
350 /* Number of times each invariant is used. */
351 unsigned *n_invariant_uses
;
353 /* The array holding the number of uses of each loop
354 invariant expressions created by ivopt. */
355 unsigned *used_inv_expr
;
357 /* The number of created loop invariants. */
358 unsigned num_used_inv_expr
;
360 /* Total cost of the assignment. */
364 /* Difference of two iv candidate assignments. */
371 /* An old assignment (for rollback purposes). */
372 struct cost_pair
*old_cp
;
374 /* A new assignment. */
375 struct cost_pair
*new_cp
;
377 /* Next change in the list. */
378 struct iv_ca_delta
*next_change
;
381 /* Bound on number of candidates below that all candidates are considered. */
383 #define CONSIDER_ALL_CANDIDATES_BOUND \
384 ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
386 /* If there are more iv occurrences, we just give up (it is quite unlikely that
387 optimizing such a loop would help, and it would take ages). */
389 #define MAX_CONSIDERED_USES \
390 ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
392 /* If there are at most this number of ivs in the set, try removing unnecessary
393 ivs from the set always. */
395 #define ALWAYS_PRUNE_CAND_SET_BOUND \
396 ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
398 /* The list of trees for that the decl_rtl field must be reset is stored
401 static vec
<tree
> decl_rtl_to_reset
;
403 static comp_cost
force_expr_to_var_cost (tree
, bool);
405 /* Number of uses recorded in DATA. */
407 static inline unsigned
408 n_iv_uses (struct ivopts_data
*data
)
410 return data
->iv_uses
.length ();
413 /* Ith use recorded in DATA. */
415 static inline struct iv_use
*
416 iv_use (struct ivopts_data
*data
, unsigned i
)
418 return data
->iv_uses
[i
];
421 /* Number of candidates recorded in DATA. */
423 static inline unsigned
424 n_iv_cands (struct ivopts_data
*data
)
426 return data
->iv_candidates
.length ();
429 /* Ith candidate recorded in DATA. */
431 static inline struct iv_cand
*
432 iv_cand (struct ivopts_data
*data
, unsigned i
)
434 return data
->iv_candidates
[i
];
437 /* The single loop exit if it dominates the latch, NULL otherwise. */
440 single_dom_exit (struct loop
*loop
)
442 edge exit
= single_exit (loop
);
447 if (!just_once_each_iteration_p (loop
, exit
->src
))
453 /* Dumps information about the induction variable IV to FILE. */
456 dump_iv (FILE *file
, struct iv
*iv
)
460 fprintf (file
, "ssa name ");
461 print_generic_expr (file
, iv
->ssa_name
, TDF_SLIM
);
462 fprintf (file
, "\n");
465 fprintf (file
, " type ");
466 print_generic_expr (file
, TREE_TYPE (iv
->base
), TDF_SLIM
);
467 fprintf (file
, "\n");
471 fprintf (file
, " base ");
472 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
473 fprintf (file
, "\n");
475 fprintf (file
, " step ");
476 print_generic_expr (file
, iv
->step
, TDF_SLIM
);
477 fprintf (file
, "\n");
481 fprintf (file
, " invariant ");
482 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
483 fprintf (file
, "\n");
488 fprintf (file
, " base object ");
489 print_generic_expr (file
, iv
->base_object
, TDF_SLIM
);
490 fprintf (file
, "\n");
494 fprintf (file
, " is a biv\n");
497 /* Dumps information about the USE to FILE. */
500 dump_use (FILE *file
, struct iv_use
*use
)
502 fprintf (file
, "use %d\n", use
->id
);
506 case USE_NONLINEAR_EXPR
:
507 fprintf (file
, " generic\n");
511 fprintf (file
, " address\n");
515 fprintf (file
, " compare\n");
522 fprintf (file
, " in statement ");
523 print_gimple_stmt (file
, use
->stmt
, 0, 0);
524 fprintf (file
, "\n");
526 fprintf (file
, " at position ");
528 print_generic_expr (file
, *use
->op_p
, TDF_SLIM
);
529 fprintf (file
, "\n");
531 dump_iv (file
, use
->iv
);
533 if (use
->related_cands
)
535 fprintf (file
, " related candidates ");
536 dump_bitmap (file
, use
->related_cands
);
540 /* Dumps information about the uses to FILE. */
543 dump_uses (FILE *file
, struct ivopts_data
*data
)
548 for (i
= 0; i
< n_iv_uses (data
); i
++)
550 use
= iv_use (data
, i
);
552 dump_use (file
, use
);
553 fprintf (file
, "\n");
557 /* Dumps information about induction variable candidate CAND to FILE. */
560 dump_cand (FILE *file
, struct iv_cand
*cand
)
562 struct iv
*iv
= cand
->iv
;
564 fprintf (file
, "candidate %d%s\n",
565 cand
->id
, cand
->important
? " (important)" : "");
567 if (cand
->depends_on
)
569 fprintf (file
, " depends on ");
570 dump_bitmap (file
, cand
->depends_on
);
575 fprintf (file
, " final value replacement\n");
579 if (cand
->var_before
)
581 fprintf (file
, " var_before ");
582 print_generic_expr (file
, cand
->var_before
, TDF_SLIM
);
583 fprintf (file
, "\n");
587 fprintf (file
, " var_after ");
588 print_generic_expr (file
, cand
->var_after
, TDF_SLIM
);
589 fprintf (file
, "\n");
595 fprintf (file
, " incremented before exit test\n");
599 fprintf (file
, " incremented before use %d\n", cand
->ainc_use
->id
);
603 fprintf (file
, " incremented after use %d\n", cand
->ainc_use
->id
);
607 fprintf (file
, " incremented at end\n");
611 fprintf (file
, " original biv\n");
618 /* Returns the info for ssa version VER. */
620 static inline struct version_info
*
621 ver_info (struct ivopts_data
*data
, unsigned ver
)
623 return data
->version_info
+ ver
;
626 /* Returns the info for ssa name NAME. */
628 static inline struct version_info
*
629 name_info (struct ivopts_data
*data
, tree name
)
631 return ver_info (data
, SSA_NAME_VERSION (name
));
634 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
638 stmt_after_ip_normal_pos (struct loop
*loop
, gimple stmt
)
640 basic_block bb
= ip_normal_pos (loop
), sbb
= gimple_bb (stmt
);
644 if (sbb
== loop
->latch
)
650 return stmt
== last_stmt (bb
);
653 /* Returns true if STMT if after the place where the original induction
654 variable CAND is incremented. If TRUE_IF_EQUAL is set, we return true
655 if the positions are identical. */
658 stmt_after_inc_pos (struct iv_cand
*cand
, gimple stmt
, bool true_if_equal
)
660 basic_block cand_bb
= gimple_bb (cand
->incremented_at
);
661 basic_block stmt_bb
= gimple_bb (stmt
);
663 if (!dominated_by_p (CDI_DOMINATORS
, stmt_bb
, cand_bb
))
666 if (stmt_bb
!= cand_bb
)
670 && gimple_uid (stmt
) == gimple_uid (cand
->incremented_at
))
672 return gimple_uid (stmt
) > gimple_uid (cand
->incremented_at
);
675 /* Returns true if STMT if after the place where the induction variable
676 CAND is incremented in LOOP. */
679 stmt_after_increment (struct loop
*loop
, struct iv_cand
*cand
, gimple stmt
)
687 return stmt_after_ip_normal_pos (loop
, stmt
);
691 return stmt_after_inc_pos (cand
, stmt
, false);
694 return stmt_after_inc_pos (cand
, stmt
, true);
701 /* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
704 abnormal_ssa_name_p (tree exp
)
709 if (TREE_CODE (exp
) != SSA_NAME
)
712 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
) != 0;
715 /* Returns false if BASE or INDEX contains a ssa name that occurs in an
716 abnormal phi node. Callback for for_each_index. */
719 idx_contains_abnormal_ssa_name_p (tree base
, tree
*index
,
720 void *data ATTRIBUTE_UNUSED
)
722 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
724 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 2)))
726 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 3)))
730 return !abnormal_ssa_name_p (*index
);
733 /* Returns true if EXPR contains a ssa name that occurs in an
734 abnormal phi node. */
737 contains_abnormal_ssa_name_p (tree expr
)
740 enum tree_code_class codeclass
;
745 code
= TREE_CODE (expr
);
746 codeclass
= TREE_CODE_CLASS (code
);
748 if (code
== SSA_NAME
)
749 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr
) != 0;
751 if (code
== INTEGER_CST
752 || is_gimple_min_invariant (expr
))
755 if (code
== ADDR_EXPR
)
756 return !for_each_index (&TREE_OPERAND (expr
, 0),
757 idx_contains_abnormal_ssa_name_p
,
760 if (code
== COND_EXPR
)
761 return contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0))
762 || contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1))
763 || contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 2));
769 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1)))
774 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0)))
786 /* Returns the structure describing number of iterations determined from
787 EXIT of DATA->current_loop, or NULL if something goes wrong. */
789 static struct tree_niter_desc
*
790 niter_for_exit (struct ivopts_data
*data
, edge exit
)
792 struct tree_niter_desc
*desc
;
797 data
->niters
= pointer_map_create ();
801 slot
= pointer_map_contains (data
->niters
, exit
);
805 /* Try to determine number of iterations. We cannot safely work with ssa
806 names that appear in phi nodes on abnormal edges, so that we do not
807 create overlapping life ranges for them (PR 27283). */
808 desc
= XNEW (struct tree_niter_desc
);
809 if (!number_of_iterations_exit (data
->current_loop
,
811 || contains_abnormal_ssa_name_p (desc
->niter
))
816 slot
= pointer_map_insert (data
->niters
, exit
);
820 desc
= (struct tree_niter_desc
*) *slot
;
825 /* Returns the structure describing number of iterations determined from
826 single dominating exit of DATA->current_loop, or NULL if something
829 static struct tree_niter_desc
*
830 niter_for_single_dom_exit (struct ivopts_data
*data
)
832 edge exit
= single_dom_exit (data
->current_loop
);
837 return niter_for_exit (data
, exit
);
840 /* Initializes data structures used by the iv optimization pass, stored
844 tree_ssa_iv_optimize_init (struct ivopts_data
*data
)
846 data
->version_info_size
= 2 * num_ssa_names
;
847 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
848 data
->relevant
= BITMAP_ALLOC (NULL
);
849 data
->important_candidates
= BITMAP_ALLOC (NULL
);
850 data
->max_inv_id
= 0;
852 data
->iv_uses
.create (20);
853 data
->iv_candidates
.create (20);
854 data
->inv_expr_tab
.create (10);
855 data
->inv_expr_id
= 0;
856 decl_rtl_to_reset
.create (20);
859 /* Returns a memory object to that EXPR points. In case we are able to
860 determine that it does not point to any such object, NULL is returned. */
863 determine_base_object (tree expr
)
865 enum tree_code code
= TREE_CODE (expr
);
868 /* If this is a pointer casted to any type, we need to determine
869 the base object for the pointer; so handle conversions before
870 throwing away non-pointer expressions. */
871 if (CONVERT_EXPR_P (expr
))
872 return determine_base_object (TREE_OPERAND (expr
, 0));
874 if (!POINTER_TYPE_P (TREE_TYPE (expr
)))
883 obj
= TREE_OPERAND (expr
, 0);
884 base
= get_base_address (obj
);
889 if (TREE_CODE (base
) == MEM_REF
)
890 return determine_base_object (TREE_OPERAND (base
, 0));
892 return fold_convert (ptr_type_node
,
893 build_fold_addr_expr (base
));
895 case POINTER_PLUS_EXPR
:
896 return determine_base_object (TREE_OPERAND (expr
, 0));
900 /* Pointer addition is done solely using POINTER_PLUS_EXPR. */
904 return fold_convert (ptr_type_node
, expr
);
908 /* Allocates an induction variable with given initial value BASE and step STEP
912 alloc_iv (tree base
, tree step
)
914 struct iv
*iv
= XCNEW (struct iv
);
915 gcc_assert (step
!= NULL_TREE
);
918 iv
->base_object
= determine_base_object (base
);
921 iv
->have_use_for
= false;
923 iv
->ssa_name
= NULL_TREE
;
928 /* Sets STEP and BASE for induction variable IV. */
931 set_iv (struct ivopts_data
*data
, tree iv
, tree base
, tree step
)
933 struct version_info
*info
= name_info (data
, iv
);
935 gcc_assert (!info
->iv
);
937 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (iv
));
938 info
->iv
= alloc_iv (base
, step
);
939 info
->iv
->ssa_name
= iv
;
942 /* Finds induction variable declaration for VAR. */
945 get_iv (struct ivopts_data
*data
, tree var
)
948 tree type
= TREE_TYPE (var
);
950 if (!POINTER_TYPE_P (type
)
951 && !INTEGRAL_TYPE_P (type
))
954 if (!name_info (data
, var
)->iv
)
956 bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
959 || !flow_bb_inside_loop_p (data
->current_loop
, bb
))
960 set_iv (data
, var
, var
, build_int_cst (type
, 0));
963 return name_info (data
, var
)->iv
;
966 /* Determines the step of a biv defined in PHI. Returns NULL if PHI does
967 not define a simple affine biv with nonzero step. */
970 determine_biv_step (gimple phi
)
972 struct loop
*loop
= gimple_bb (phi
)->loop_father
;
973 tree name
= PHI_RESULT (phi
);
976 if (virtual_operand_p (name
))
979 if (!simple_iv (loop
, loop
, name
, &iv
, true))
982 return integer_zerop (iv
.step
) ? NULL_TREE
: iv
.step
;
985 /* Finds basic ivs. */
988 find_bivs (struct ivopts_data
*data
)
991 tree step
, type
, base
;
993 struct loop
*loop
= data
->current_loop
;
994 gimple_stmt_iterator psi
;
996 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
998 phi
= gsi_stmt (psi
);
1000 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
1003 step
= determine_biv_step (phi
);
1007 base
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1008 base
= expand_simple_operations (base
);
1009 if (contains_abnormal_ssa_name_p (base
)
1010 || contains_abnormal_ssa_name_p (step
))
1013 type
= TREE_TYPE (PHI_RESULT (phi
));
1014 base
= fold_convert (type
, base
);
1017 if (POINTER_TYPE_P (type
))
1018 step
= convert_to_ptrofftype (step
);
1020 step
= fold_convert (type
, step
);
1023 set_iv (data
, PHI_RESULT (phi
), base
, step
);
1030 /* Marks basic ivs. */
1033 mark_bivs (struct ivopts_data
*data
)
1037 struct iv
*iv
, *incr_iv
;
1038 struct loop
*loop
= data
->current_loop
;
1039 basic_block incr_bb
;
1040 gimple_stmt_iterator psi
;
1042 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1044 phi
= gsi_stmt (psi
);
1046 iv
= get_iv (data
, PHI_RESULT (phi
));
1050 var
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
1051 incr_iv
= get_iv (data
, var
);
1055 /* If the increment is in the subloop, ignore it. */
1056 incr_bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
1057 if (incr_bb
->loop_father
!= data
->current_loop
1058 || (incr_bb
->flags
& BB_IRREDUCIBLE_LOOP
))
1062 incr_iv
->biv_p
= true;
1066 /* Checks whether STMT defines a linear induction variable and stores its
1067 parameters to IV. */
1070 find_givs_in_stmt_scev (struct ivopts_data
*data
, gimple stmt
, affine_iv
*iv
)
1073 struct loop
*loop
= data
->current_loop
;
1075 iv
->base
= NULL_TREE
;
1076 iv
->step
= NULL_TREE
;
1078 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1081 lhs
= gimple_assign_lhs (stmt
);
1082 if (TREE_CODE (lhs
) != SSA_NAME
)
1085 if (!simple_iv (loop
, loop_containing_stmt (stmt
), lhs
, iv
, true))
1087 iv
->base
= expand_simple_operations (iv
->base
);
1089 if (contains_abnormal_ssa_name_p (iv
->base
)
1090 || contains_abnormal_ssa_name_p (iv
->step
))
1093 /* If STMT could throw, then do not consider STMT as defining a GIV.
1094 While this will suppress optimizations, we can not safely delete this
1095 GIV and associated statements, even if it appears it is not used. */
1096 if (stmt_could_throw_p (stmt
))
1102 /* Finds general ivs in statement STMT. */
1105 find_givs_in_stmt (struct ivopts_data
*data
, gimple stmt
)
1109 if (!find_givs_in_stmt_scev (data
, stmt
, &iv
))
1112 set_iv (data
, gimple_assign_lhs (stmt
), iv
.base
, iv
.step
);
1115 /* Finds general ivs in basic block BB. */
1118 find_givs_in_bb (struct ivopts_data
*data
, basic_block bb
)
1120 gimple_stmt_iterator bsi
;
1122 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1123 find_givs_in_stmt (data
, gsi_stmt (bsi
));
1126 /* Finds general ivs. */
1129 find_givs (struct ivopts_data
*data
)
1131 struct loop
*loop
= data
->current_loop
;
1132 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1135 for (i
= 0; i
< loop
->num_nodes
; i
++)
1136 find_givs_in_bb (data
, body
[i
]);
1140 /* For each ssa name defined in LOOP determines whether it is an induction
1141 variable and if so, its initial value and step. */
1144 find_induction_variables (struct ivopts_data
*data
)
1149 if (!find_bivs (data
))
1155 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1157 struct tree_niter_desc
*niter
= niter_for_single_dom_exit (data
);
1161 fprintf (dump_file
, " number of iterations ");
1162 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1163 if (!integer_zerop (niter
->may_be_zero
))
1165 fprintf (dump_file
, "; zero if ");
1166 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1168 fprintf (dump_file
, "\n\n");
1171 fprintf (dump_file
, "Induction variables:\n\n");
1173 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1175 if (ver_info (data
, i
)->iv
)
1176 dump_iv (dump_file
, ver_info (data
, i
)->iv
);
1183 /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV. */
1185 static struct iv_use
*
1186 record_use (struct ivopts_data
*data
, tree
*use_p
, struct iv
*iv
,
1187 gimple stmt
, enum use_type use_type
)
1189 struct iv_use
*use
= XCNEW (struct iv_use
);
1191 use
->id
= n_iv_uses (data
);
1192 use
->type
= use_type
;
1196 use
->related_cands
= BITMAP_ALLOC (NULL
);
1198 /* To avoid showing ssa name in the dumps, if it was not reset by the
1200 iv
->ssa_name
= NULL_TREE
;
1202 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1203 dump_use (dump_file
, use
);
1205 data
->iv_uses
.safe_push (use
);
1210 /* Checks whether OP is a loop-level invariant and if so, records it.
1211 NONLINEAR_USE is true if the invariant is used in a way we do not
1212 handle specially. */
1215 record_invariant (struct ivopts_data
*data
, tree op
, bool nonlinear_use
)
1218 struct version_info
*info
;
1220 if (TREE_CODE (op
) != SSA_NAME
1221 || virtual_operand_p (op
))
1224 bb
= gimple_bb (SSA_NAME_DEF_STMT (op
));
1226 && flow_bb_inside_loop_p (data
->current_loop
, bb
))
1229 info
= name_info (data
, op
);
1231 info
->has_nonlin_use
|= nonlinear_use
;
1233 info
->inv_id
= ++data
->max_inv_id
;
1234 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (op
));
1237 /* Checks whether the use OP is interesting and if so, records it. */
1239 static struct iv_use
*
1240 find_interesting_uses_op (struct ivopts_data
*data
, tree op
)
1247 if (TREE_CODE (op
) != SSA_NAME
)
1250 iv
= get_iv (data
, op
);
1254 if (iv
->have_use_for
)
1256 use
= iv_use (data
, iv
->use_id
);
1258 gcc_assert (use
->type
== USE_NONLINEAR_EXPR
);
1262 if (integer_zerop (iv
->step
))
1264 record_invariant (data
, op
, true);
1267 iv
->have_use_for
= true;
1269 civ
= XNEW (struct iv
);
1272 stmt
= SSA_NAME_DEF_STMT (op
);
1273 gcc_assert (gimple_code (stmt
) == GIMPLE_PHI
1274 || is_gimple_assign (stmt
));
1276 use
= record_use (data
, NULL
, civ
, stmt
, USE_NONLINEAR_EXPR
);
1277 iv
->use_id
= use
->id
;
1282 /* Given a condition in statement STMT, checks whether it is a compare
1283 of an induction variable and an invariant. If this is the case,
1284 CONTROL_VAR is set to location of the iv, BOUND to the location of
1285 the invariant, IV_VAR and IV_BOUND are set to the corresponding
1286 induction variable descriptions, and true is returned. If this is not
1287 the case, CONTROL_VAR and BOUND are set to the arguments of the
1288 condition and false is returned. */
1291 extract_cond_operands (struct ivopts_data
*data
, gimple stmt
,
1292 tree
**control_var
, tree
**bound
,
1293 struct iv
**iv_var
, struct iv
**iv_bound
)
1295 /* The objects returned when COND has constant operands. */
1296 static struct iv const_iv
;
1298 tree
*op0
= &zero
, *op1
= &zero
, *tmp_op
;
1299 struct iv
*iv0
= &const_iv
, *iv1
= &const_iv
, *tmp_iv
;
1302 if (gimple_code (stmt
) == GIMPLE_COND
)
1304 op0
= gimple_cond_lhs_ptr (stmt
);
1305 op1
= gimple_cond_rhs_ptr (stmt
);
1309 op0
= gimple_assign_rhs1_ptr (stmt
);
1310 op1
= gimple_assign_rhs2_ptr (stmt
);
1313 zero
= integer_zero_node
;
1314 const_iv
.step
= integer_zero_node
;
1316 if (TREE_CODE (*op0
) == SSA_NAME
)
1317 iv0
= get_iv (data
, *op0
);
1318 if (TREE_CODE (*op1
) == SSA_NAME
)
1319 iv1
= get_iv (data
, *op1
);
1321 /* Exactly one of the compared values must be an iv, and the other one must
1326 if (integer_zerop (iv0
->step
))
1328 /* Control variable may be on the other side. */
1329 tmp_op
= op0
; op0
= op1
; op1
= tmp_op
;
1330 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
1332 ret
= !integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
);
1336 *control_var
= op0
;;
1347 /* Checks whether the condition in STMT is interesting and if so,
1351 find_interesting_uses_cond (struct ivopts_data
*data
, gimple stmt
)
1353 tree
*var_p
, *bound_p
;
1354 struct iv
*var_iv
, *civ
;
1356 if (!extract_cond_operands (data
, stmt
, &var_p
, &bound_p
, &var_iv
, NULL
))
1358 find_interesting_uses_op (data
, *var_p
);
1359 find_interesting_uses_op (data
, *bound_p
);
1363 civ
= XNEW (struct iv
);
1365 record_use (data
, NULL
, civ
, stmt
, USE_COMPARE
);
1368 /* Returns the outermost loop EXPR is obviously invariant in
1369 relative to the loop LOOP, i.e. if all its operands are defined
1370 outside of the returned loop. Returns NULL if EXPR is not
1371 even obviously invariant in LOOP. */
1374 outermost_invariant_loop_for_expr (struct loop
*loop
, tree expr
)
1379 if (is_gimple_min_invariant (expr
))
1380 return current_loops
->tree_root
;
1382 if (TREE_CODE (expr
) == SSA_NAME
)
1384 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
1387 if (flow_bb_inside_loop_p (loop
, def_bb
))
1389 return superloop_at_depth (loop
,
1390 loop_depth (def_bb
->loop_father
) + 1);
1393 return current_loops
->tree_root
;
1399 unsigned maxdepth
= 0;
1400 len
= TREE_OPERAND_LENGTH (expr
);
1401 for (i
= 0; i
< len
; i
++)
1403 struct loop
*ivloop
;
1404 if (!TREE_OPERAND (expr
, i
))
1407 ivloop
= outermost_invariant_loop_for_expr (loop
, TREE_OPERAND (expr
, i
));
1410 maxdepth
= MAX (maxdepth
, loop_depth (ivloop
));
1413 return superloop_at_depth (loop
, maxdepth
);
1416 /* Returns true if expression EXPR is obviously invariant in LOOP,
1417 i.e. if all its operands are defined outside of the LOOP. LOOP
1418 should not be the function body. */
1421 expr_invariant_in_loop_p (struct loop
*loop
, tree expr
)
1426 gcc_assert (loop_depth (loop
) > 0);
1428 if (is_gimple_min_invariant (expr
))
1431 if (TREE_CODE (expr
) == SSA_NAME
)
1433 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
1435 && flow_bb_inside_loop_p (loop
, def_bb
))
1444 len
= TREE_OPERAND_LENGTH (expr
);
1445 for (i
= 0; i
< len
; i
++)
1446 if (TREE_OPERAND (expr
, i
)
1447 && !expr_invariant_in_loop_p (loop
, TREE_OPERAND (expr
, i
)))
1453 /* Cumulates the steps of indices into DATA and replaces their values with the
1454 initial ones. Returns false when the value of the index cannot be determined.
1455 Callback for for_each_index. */
1457 struct ifs_ivopts_data
1459 struct ivopts_data
*ivopts_data
;
1465 idx_find_step (tree base
, tree
*idx
, void *data
)
1467 struct ifs_ivopts_data
*dta
= (struct ifs_ivopts_data
*) data
;
1469 tree step
, iv_base
, iv_step
, lbound
, off
;
1470 struct loop
*loop
= dta
->ivopts_data
->current_loop
;
1472 /* If base is a component ref, require that the offset of the reference
1474 if (TREE_CODE (base
) == COMPONENT_REF
)
1476 off
= component_ref_field_offset (base
);
1477 return expr_invariant_in_loop_p (loop
, off
);
1480 /* If base is array, first check whether we will be able to move the
1481 reference out of the loop (in order to take its address in strength
1482 reduction). In order for this to work we need both lower bound
1483 and step to be loop invariants. */
1484 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
1486 /* Moreover, for a range, the size needs to be invariant as well. */
1487 if (TREE_CODE (base
) == ARRAY_RANGE_REF
1488 && !expr_invariant_in_loop_p (loop
, TYPE_SIZE (TREE_TYPE (base
))))
1491 step
= array_ref_element_size (base
);
1492 lbound
= array_ref_low_bound (base
);
1494 if (!expr_invariant_in_loop_p (loop
, step
)
1495 || !expr_invariant_in_loop_p (loop
, lbound
))
1499 if (TREE_CODE (*idx
) != SSA_NAME
)
1502 iv
= get_iv (dta
->ivopts_data
, *idx
);
1506 /* XXX We produce for a base of *D42 with iv->base being &x[0]
1507 *&x[0], which is not folded and does not trigger the
1508 ARRAY_REF path below. */
1511 if (integer_zerop (iv
->step
))
1514 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
1516 step
= array_ref_element_size (base
);
1518 /* We only handle addresses whose step is an integer constant. */
1519 if (TREE_CODE (step
) != INTEGER_CST
)
1523 /* The step for pointer arithmetics already is 1 byte. */
1524 step
= size_one_node
;
1528 if (!convert_affine_scev (dta
->ivopts_data
->current_loop
,
1529 sizetype
, &iv_base
, &iv_step
, dta
->stmt
,
1532 /* The index might wrap. */
1536 step
= fold_build2 (MULT_EXPR
, sizetype
, step
, iv_step
);
1537 dta
->step
= fold_build2 (PLUS_EXPR
, sizetype
, dta
->step
, step
);
1542 /* Records use in index IDX. Callback for for_each_index. Ivopts data
1543 object is passed to it in DATA. */
1546 idx_record_use (tree base
, tree
*idx
,
1549 struct ivopts_data
*data
= (struct ivopts_data
*) vdata
;
1550 find_interesting_uses_op (data
, *idx
);
1551 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
1553 find_interesting_uses_op (data
, array_ref_element_size (base
));
1554 find_interesting_uses_op (data
, array_ref_low_bound (base
));
1559 /* If we can prove that TOP = cst * BOT for some constant cst,
1560 store cst to MUL and return true. Otherwise return false.
1561 The returned value is always sign-extended, regardless of the
1562 signedness of TOP and BOT. */
1565 constant_multiple_of (tree top
, tree bot
, double_int
*mul
)
1568 enum tree_code code
;
1569 double_int res
, p0
, p1
;
1570 unsigned precision
= TYPE_PRECISION (TREE_TYPE (top
));
1575 if (operand_equal_p (top
, bot
, 0))
1577 *mul
= double_int_one
;
1581 code
= TREE_CODE (top
);
1585 mby
= TREE_OPERAND (top
, 1);
1586 if (TREE_CODE (mby
) != INTEGER_CST
)
1589 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &res
))
1592 *mul
= (res
* tree_to_double_int (mby
)).sext (precision
);
1597 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &p0
)
1598 || !constant_multiple_of (TREE_OPERAND (top
, 1), bot
, &p1
))
1601 if (code
== MINUS_EXPR
)
1603 *mul
= (p0
+ p1
).sext (precision
);
1607 if (TREE_CODE (bot
) != INTEGER_CST
)
1610 p0
= tree_to_double_int (top
).sext (precision
);
1611 p1
= tree_to_double_int (bot
).sext (precision
);
1614 *mul
= p0
.sdivmod (p1
, FLOOR_DIV_EXPR
, &res
).sext (precision
);
1615 return res
.is_zero ();
1622 /* Returns true if memory reference REF with step STEP may be unaligned. */
1625 may_be_unaligned_p (tree ref
, tree step
)
1629 HOST_WIDE_INT bitsize
;
1630 HOST_WIDE_INT bitpos
;
1632 enum machine_mode mode
;
1633 int unsignedp
, volatilep
;
1634 unsigned base_align
;
1636 /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
1637 thus they are not misaligned. */
1638 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
1641 /* The test below is basically copy of what expr.c:normal_inner_ref
1642 does to check whether the object must be loaded by parts when
1643 STRICT_ALIGNMENT is true. */
1644 base
= get_inner_reference (ref
, &bitsize
, &bitpos
, &toffset
, &mode
,
1645 &unsignedp
, &volatilep
, true);
1646 base_type
= TREE_TYPE (base
);
1647 base_align
= get_object_alignment (base
);
1648 base_align
= MAX (base_align
, TYPE_ALIGN (base_type
));
1650 if (mode
!= BLKmode
)
1652 unsigned mode_align
= GET_MODE_ALIGNMENT (mode
);
1654 if (base_align
< mode_align
1655 || (bitpos
% mode_align
) != 0
1656 || (bitpos
% BITS_PER_UNIT
) != 0)
1660 && (highest_pow2_factor (toffset
) * BITS_PER_UNIT
) < mode_align
)
1663 if ((highest_pow2_factor (step
) * BITS_PER_UNIT
) < mode_align
)
1670 /* Return true if EXPR may be non-addressable. */
1673 may_be_nonaddressable_p (tree expr
)
1675 switch (TREE_CODE (expr
))
1677 case TARGET_MEM_REF
:
1678 /* TARGET_MEM_REFs are translated directly to valid MEMs on the
1679 target, thus they are always addressable. */
1683 return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr
, 1))
1684 || may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1686 case VIEW_CONVERT_EXPR
:
1687 /* This kind of view-conversions may wrap non-addressable objects
1688 and make them look addressable. After some processing the
1689 non-addressability may be uncovered again, causing ADDR_EXPRs
1690 of inappropriate objects to be built. */
1691 if (is_gimple_reg (TREE_OPERAND (expr
, 0))
1692 || !is_gimple_addressable (TREE_OPERAND (expr
, 0)))
1695 /* ... fall through ... */
1698 case ARRAY_RANGE_REF
:
1699 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1711 /* Finds addresses in *OP_P inside STMT. */
1714 find_interesting_uses_address (struct ivopts_data
*data
, gimple stmt
, tree
*op_p
)
1716 tree base
= *op_p
, step
= size_zero_node
;
1718 struct ifs_ivopts_data ifs_ivopts_data
;
1720 /* Do not play with volatile memory references. A bit too conservative,
1721 perhaps, but safe. */
1722 if (gimple_has_volatile_ops (stmt
))
1725 /* Ignore bitfields for now. Not really something terribly complicated
1727 if (TREE_CODE (base
) == BIT_FIELD_REF
)
1730 base
= unshare_expr (base
);
1732 if (TREE_CODE (base
) == TARGET_MEM_REF
)
1734 tree type
= build_pointer_type (TREE_TYPE (base
));
1738 && TREE_CODE (TMR_BASE (base
)) == SSA_NAME
)
1740 civ
= get_iv (data
, TMR_BASE (base
));
1744 TMR_BASE (base
) = civ
->base
;
1747 if (TMR_INDEX2 (base
)
1748 && TREE_CODE (TMR_INDEX2 (base
)) == SSA_NAME
)
1750 civ
= get_iv (data
, TMR_INDEX2 (base
));
1754 TMR_INDEX2 (base
) = civ
->base
;
1757 if (TMR_INDEX (base
)
1758 && TREE_CODE (TMR_INDEX (base
)) == SSA_NAME
)
1760 civ
= get_iv (data
, TMR_INDEX (base
));
1764 TMR_INDEX (base
) = civ
->base
;
1769 if (TMR_STEP (base
))
1770 astep
= fold_build2 (MULT_EXPR
, type
, TMR_STEP (base
), astep
);
1772 step
= fold_build2 (PLUS_EXPR
, type
, step
, astep
);
1776 if (integer_zerop (step
))
1778 base
= tree_mem_ref_addr (type
, base
);
1782 ifs_ivopts_data
.ivopts_data
= data
;
1783 ifs_ivopts_data
.stmt
= stmt
;
1784 ifs_ivopts_data
.step
= size_zero_node
;
1785 if (!for_each_index (&base
, idx_find_step
, &ifs_ivopts_data
)
1786 || integer_zerop (ifs_ivopts_data
.step
))
1788 step
= ifs_ivopts_data
.step
;
1790 /* Check that the base expression is addressable. This needs
1791 to be done after substituting bases of IVs into it. */
1792 if (may_be_nonaddressable_p (base
))
1795 /* Moreover, on strict alignment platforms, check that it is
1796 sufficiently aligned. */
1797 if (STRICT_ALIGNMENT
&& may_be_unaligned_p (base
, step
))
1800 base
= build_fold_addr_expr (base
);
1802 /* Substituting bases of IVs into the base expression might
1803 have caused folding opportunities. */
1804 if (TREE_CODE (base
) == ADDR_EXPR
)
1806 tree
*ref
= &TREE_OPERAND (base
, 0);
1807 while (handled_component_p (*ref
))
1808 ref
= &TREE_OPERAND (*ref
, 0);
1809 if (TREE_CODE (*ref
) == MEM_REF
)
1811 tree tem
= fold_binary (MEM_REF
, TREE_TYPE (*ref
),
1812 TREE_OPERAND (*ref
, 0),
1813 TREE_OPERAND (*ref
, 1));
1820 civ
= alloc_iv (base
, step
);
1821 record_use (data
, op_p
, civ
, stmt
, USE_ADDRESS
);
1825 for_each_index (op_p
, idx_record_use
, data
);
1828 /* Finds and records invariants used in STMT. */
1831 find_invariants_stmt (struct ivopts_data
*data
, gimple stmt
)
1834 use_operand_p use_p
;
1837 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1839 op
= USE_FROM_PTR (use_p
);
1840 record_invariant (data
, op
, false);
1844 /* Finds interesting uses of induction variables in the statement STMT. */
1847 find_interesting_uses_stmt (struct ivopts_data
*data
, gimple stmt
)
1850 tree op
, *lhs
, *rhs
;
1852 use_operand_p use_p
;
1853 enum tree_code code
;
1855 find_invariants_stmt (data
, stmt
);
1857 if (gimple_code (stmt
) == GIMPLE_COND
)
1859 find_interesting_uses_cond (data
, stmt
);
1863 if (is_gimple_assign (stmt
))
1865 lhs
= gimple_assign_lhs_ptr (stmt
);
1866 rhs
= gimple_assign_rhs1_ptr (stmt
);
1868 if (TREE_CODE (*lhs
) == SSA_NAME
)
1870 /* If the statement defines an induction variable, the uses are not
1871 interesting by themselves. */
1873 iv
= get_iv (data
, *lhs
);
1875 if (iv
&& !integer_zerop (iv
->step
))
1879 code
= gimple_assign_rhs_code (stmt
);
1880 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
1881 && (REFERENCE_CLASS_P (*rhs
)
1882 || is_gimple_val (*rhs
)))
1884 if (REFERENCE_CLASS_P (*rhs
))
1885 find_interesting_uses_address (data
, stmt
, rhs
);
1887 find_interesting_uses_op (data
, *rhs
);
1889 if (REFERENCE_CLASS_P (*lhs
))
1890 find_interesting_uses_address (data
, stmt
, lhs
);
1893 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
1895 find_interesting_uses_cond (data
, stmt
);
1899 /* TODO -- we should also handle address uses of type
1901 memory = call (whatever);
1908 if (gimple_code (stmt
) == GIMPLE_PHI
1909 && gimple_bb (stmt
) == data
->current_loop
->header
)
1911 iv
= get_iv (data
, PHI_RESULT (stmt
));
1913 if (iv
&& !integer_zerop (iv
->step
))
1917 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1919 op
= USE_FROM_PTR (use_p
);
1921 if (TREE_CODE (op
) != SSA_NAME
)
1924 iv
= get_iv (data
, op
);
1928 find_interesting_uses_op (data
, op
);
1932 /* Finds interesting uses of induction variables outside of loops
1933 on loop exit edge EXIT. */
1936 find_interesting_uses_outside (struct ivopts_data
*data
, edge exit
)
1939 gimple_stmt_iterator psi
;
1942 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
1944 phi
= gsi_stmt (psi
);
1945 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1946 if (!virtual_operand_p (def
))
1947 find_interesting_uses_op (data
, def
);
1951 /* Finds uses of the induction variables that are interesting. */
1954 find_interesting_uses (struct ivopts_data
*data
)
1957 gimple_stmt_iterator bsi
;
1958 basic_block
*body
= get_loop_body (data
->current_loop
);
1960 struct version_info
*info
;
1963 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1964 fprintf (dump_file
, "Uses:\n\n");
1966 for (i
= 0; i
< data
->current_loop
->num_nodes
; i
++)
1971 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1972 if (e
->dest
!= EXIT_BLOCK_PTR
1973 && !flow_bb_inside_loop_p (data
->current_loop
, e
->dest
))
1974 find_interesting_uses_outside (data
, e
);
1976 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1977 find_interesting_uses_stmt (data
, gsi_stmt (bsi
));
1978 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1979 if (!is_gimple_debug (gsi_stmt (bsi
)))
1980 find_interesting_uses_stmt (data
, gsi_stmt (bsi
));
1983 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1987 fprintf (dump_file
, "\n");
1989 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1991 info
= ver_info (data
, i
);
1994 fprintf (dump_file
, " ");
1995 print_generic_expr (dump_file
, info
->name
, TDF_SLIM
);
1996 fprintf (dump_file
, " is invariant (%d)%s\n",
1997 info
->inv_id
, info
->has_nonlin_use
? "" : ", eliminable");
2001 fprintf (dump_file
, "\n");
2007 /* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
2008 is true, assume we are inside an address. If TOP_COMPREF is true, assume
2009 we are at the top-level of the processed address. */
2012 strip_offset_1 (tree expr
, bool inside_addr
, bool top_compref
,
2013 unsigned HOST_WIDE_INT
*offset
)
2015 tree op0
= NULL_TREE
, op1
= NULL_TREE
, tmp
, step
;
2016 enum tree_code code
;
2017 tree type
, orig_type
= TREE_TYPE (expr
);
2018 unsigned HOST_WIDE_INT off0
, off1
, st
;
2019 tree orig_expr
= expr
;
2023 type
= TREE_TYPE (expr
);
2024 code
= TREE_CODE (expr
);
2030 if (!cst_and_fits_in_hwi (expr
)
2031 || integer_zerop (expr
))
2034 *offset
= int_cst_value (expr
);
2035 return build_int_cst (orig_type
, 0);
2037 case POINTER_PLUS_EXPR
:
2040 op0
= TREE_OPERAND (expr
, 0);
2041 op1
= TREE_OPERAND (expr
, 1);
2043 op0
= strip_offset_1 (op0
, false, false, &off0
);
2044 op1
= strip_offset_1 (op1
, false, false, &off1
);
2046 *offset
= (code
== MINUS_EXPR
? off0
- off1
: off0
+ off1
);
2047 if (op0
== TREE_OPERAND (expr
, 0)
2048 && op1
== TREE_OPERAND (expr
, 1))
2051 if (integer_zerop (op1
))
2053 else if (integer_zerop (op0
))
2055 if (code
== MINUS_EXPR
)
2056 expr
= fold_build1 (NEGATE_EXPR
, type
, op1
);
2061 expr
= fold_build2 (code
, type
, op0
, op1
);
2063 return fold_convert (orig_type
, expr
);
2066 op1
= TREE_OPERAND (expr
, 1);
2067 if (!cst_and_fits_in_hwi (op1
))
2070 op0
= TREE_OPERAND (expr
, 0);
2071 op0
= strip_offset_1 (op0
, false, false, &off0
);
2072 if (op0
== TREE_OPERAND (expr
, 0))
2075 *offset
= off0
* int_cst_value (op1
);
2076 if (integer_zerop (op0
))
2079 expr
= fold_build2 (MULT_EXPR
, type
, op0
, op1
);
2081 return fold_convert (orig_type
, expr
);
2084 case ARRAY_RANGE_REF
:
2088 step
= array_ref_element_size (expr
);
2089 if (!cst_and_fits_in_hwi (step
))
2092 st
= int_cst_value (step
);
2093 op1
= TREE_OPERAND (expr
, 1);
2094 op1
= strip_offset_1 (op1
, false, false, &off1
);
2095 *offset
= off1
* st
;
2098 && integer_zerop (op1
))
2100 /* Strip the component reference completely. */
2101 op0
= TREE_OPERAND (expr
, 0);
2102 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
2112 tmp
= component_ref_field_offset (expr
);
2114 && cst_and_fits_in_hwi (tmp
))
2116 /* Strip the component reference completely. */
2117 op0
= TREE_OPERAND (expr
, 0);
2118 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
2119 *offset
= off0
+ int_cst_value (tmp
);
2125 op0
= TREE_OPERAND (expr
, 0);
2126 op0
= strip_offset_1 (op0
, true, true, &off0
);
2129 if (op0
== TREE_OPERAND (expr
, 0))
2132 expr
= build_fold_addr_expr (op0
);
2133 return fold_convert (orig_type
, expr
);
2136 /* ??? Offset operand? */
2137 inside_addr
= false;
2144 /* Default handling of expressions for that we want to recurse into
2145 the first operand. */
2146 op0
= TREE_OPERAND (expr
, 0);
2147 op0
= strip_offset_1 (op0
, inside_addr
, false, &off0
);
2150 if (op0
== TREE_OPERAND (expr
, 0)
2151 && (!op1
|| op1
== TREE_OPERAND (expr
, 1)))
2154 expr
= copy_node (expr
);
2155 TREE_OPERAND (expr
, 0) = op0
;
2157 TREE_OPERAND (expr
, 1) = op1
;
2159 /* Inside address, we might strip the top level component references,
2160 thus changing type of the expression. Handling of ADDR_EXPR
2162 expr
= fold_convert (orig_type
, expr
);
2167 /* Strips constant offsets from EXPR and stores them to OFFSET. */
2170 strip_offset (tree expr
, unsigned HOST_WIDE_INT
*offset
)
2172 return strip_offset_1 (expr
, false, false, offset
);
2175 /* Returns variant of TYPE that can be used as base for different uses.
2176 We return unsigned type with the same precision, which avoids problems
2180 generic_type_for (tree type
)
2182 if (POINTER_TYPE_P (type
))
2183 return unsigned_type_for (type
);
2185 if (TYPE_UNSIGNED (type
))
2188 return unsigned_type_for (type
);
2191 /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
2192 the bitmap to that we should store it. */
2194 static struct ivopts_data
*fd_ivopts_data
;
2196 find_depends (tree
*expr_p
, int *ws ATTRIBUTE_UNUSED
, void *data
)
2198 bitmap
*depends_on
= (bitmap
*) data
;
2199 struct version_info
*info
;
2201 if (TREE_CODE (*expr_p
) != SSA_NAME
)
2203 info
= name_info (fd_ivopts_data
, *expr_p
);
2205 if (!info
->inv_id
|| info
->has_nonlin_use
)
2209 *depends_on
= BITMAP_ALLOC (NULL
);
2210 bitmap_set_bit (*depends_on
, info
->inv_id
);
2215 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2216 position to POS. If USE is not NULL, the candidate is set as related to
2217 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
2218 replacement of the final value of the iv by a direct computation. */
2220 static struct iv_cand
*
2221 add_candidate_1 (struct ivopts_data
*data
,
2222 tree base
, tree step
, bool important
, enum iv_position pos
,
2223 struct iv_use
*use
, gimple incremented_at
)
2226 struct iv_cand
*cand
= NULL
;
2227 tree type
, orig_type
;
2229 /* For non-original variables, make sure their values are computed in a type
2230 that does not invoke undefined behavior on overflows (since in general,
2231 we cannot prove that these induction variables are non-wrapping). */
2232 if (pos
!= IP_ORIGINAL
)
2234 orig_type
= TREE_TYPE (base
);
2235 type
= generic_type_for (orig_type
);
2236 if (type
!= orig_type
)
2238 base
= fold_convert (type
, base
);
2239 step
= fold_convert (type
, step
);
2243 for (i
= 0; i
< n_iv_cands (data
); i
++)
2245 cand
= iv_cand (data
, i
);
2247 if (cand
->pos
!= pos
)
2250 if (cand
->incremented_at
!= incremented_at
2251 || ((pos
== IP_AFTER_USE
|| pos
== IP_BEFORE_USE
)
2252 && cand
->ainc_use
!= use
))
2266 if (operand_equal_p (base
, cand
->iv
->base
, 0)
2267 && operand_equal_p (step
, cand
->iv
->step
, 0)
2268 && (TYPE_PRECISION (TREE_TYPE (base
))
2269 == TYPE_PRECISION (TREE_TYPE (cand
->iv
->base
))))
2273 if (i
== n_iv_cands (data
))
2275 cand
= XCNEW (struct iv_cand
);
2281 cand
->iv
= alloc_iv (base
, step
);
2284 if (pos
!= IP_ORIGINAL
&& cand
->iv
)
2286 cand
->var_before
= create_tmp_var_raw (TREE_TYPE (base
), "ivtmp");
2287 cand
->var_after
= cand
->var_before
;
2289 cand
->important
= important
;
2290 cand
->incremented_at
= incremented_at
;
2291 data
->iv_candidates
.safe_push (cand
);
2294 && TREE_CODE (step
) != INTEGER_CST
)
2296 fd_ivopts_data
= data
;
2297 walk_tree (&step
, find_depends
, &cand
->depends_on
, NULL
);
2300 if (pos
== IP_AFTER_USE
|| pos
== IP_BEFORE_USE
)
2301 cand
->ainc_use
= use
;
2303 cand
->ainc_use
= NULL
;
2305 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2306 dump_cand (dump_file
, cand
);
2309 if (important
&& !cand
->important
)
2311 cand
->important
= true;
2312 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2313 fprintf (dump_file
, "Candidate %d is important\n", cand
->id
);
2318 bitmap_set_bit (use
->related_cands
, i
);
2319 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2320 fprintf (dump_file
, "Candidate %d is related to use %d\n",
2327 /* Returns true if incrementing the induction variable at the end of the LOOP
2330 The purpose is to avoid splitting latch edge with a biv increment, thus
2331 creating a jump, possibly confusing other optimization passes and leaving
2332 less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS
2333 is not available (so we do not have a better alternative), or if the latch
2334 edge is already nonempty. */
2337 allow_ip_end_pos_p (struct loop
*loop
)
2339 if (!ip_normal_pos (loop
))
2342 if (!empty_block_p (ip_end_pos (loop
)))
2348 /* If possible, adds autoincrement candidates BASE + STEP * i based on use USE.
2349 Important field is set to IMPORTANT. */
2352 add_autoinc_candidates (struct ivopts_data
*data
, tree base
, tree step
,
2353 bool important
, struct iv_use
*use
)
2355 basic_block use_bb
= gimple_bb (use
->stmt
);
2356 enum machine_mode mem_mode
;
2357 unsigned HOST_WIDE_INT cstepi
;
2359 /* If we insert the increment in any position other than the standard
2360 ones, we must ensure that it is incremented once per iteration.
2361 It must not be in an inner nested loop, or one side of an if
2363 if (use_bb
->loop_father
!= data
->current_loop
2364 || !dominated_by_p (CDI_DOMINATORS
, data
->current_loop
->latch
, use_bb
)
2365 || stmt_could_throw_p (use
->stmt
)
2366 || !cst_and_fits_in_hwi (step
))
2369 cstepi
= int_cst_value (step
);
2371 mem_mode
= TYPE_MODE (TREE_TYPE (*use
->op_p
));
2372 if (((USE_LOAD_PRE_INCREMENT (mem_mode
)
2373 || USE_STORE_PRE_INCREMENT (mem_mode
))
2374 && GET_MODE_SIZE (mem_mode
) == cstepi
)
2375 || ((USE_LOAD_PRE_DECREMENT (mem_mode
)
2376 || USE_STORE_PRE_DECREMENT (mem_mode
))
2377 && GET_MODE_SIZE (mem_mode
) == -cstepi
))
2379 enum tree_code code
= MINUS_EXPR
;
2381 tree new_step
= step
;
2383 if (POINTER_TYPE_P (TREE_TYPE (base
)))
2385 new_step
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (step
), step
);
2386 code
= POINTER_PLUS_EXPR
;
2389 new_step
= fold_convert (TREE_TYPE (base
), new_step
);
2390 new_base
= fold_build2 (code
, TREE_TYPE (base
), base
, new_step
);
2391 add_candidate_1 (data
, new_base
, step
, important
, IP_BEFORE_USE
, use
,
2394 if (((USE_LOAD_POST_INCREMENT (mem_mode
)
2395 || USE_STORE_POST_INCREMENT (mem_mode
))
2396 && GET_MODE_SIZE (mem_mode
) == cstepi
)
2397 || ((USE_LOAD_POST_DECREMENT (mem_mode
)
2398 || USE_STORE_POST_DECREMENT (mem_mode
))
2399 && GET_MODE_SIZE (mem_mode
) == -cstepi
))
2401 add_candidate_1 (data
, base
, step
, important
, IP_AFTER_USE
, use
,
2406 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2407 position to POS. If USE is not NULL, the candidate is set as related to
2408 it. The candidate computation is scheduled on all available positions. */
2411 add_candidate (struct ivopts_data
*data
,
2412 tree base
, tree step
, bool important
, struct iv_use
*use
)
2414 if (ip_normal_pos (data
->current_loop
))
2415 add_candidate_1 (data
, base
, step
, important
, IP_NORMAL
, use
, NULL
);
2416 if (ip_end_pos (data
->current_loop
)
2417 && allow_ip_end_pos_p (data
->current_loop
))
2418 add_candidate_1 (data
, base
, step
, important
, IP_END
, use
, NULL
);
2420 if (use
!= NULL
&& use
->type
== USE_ADDRESS
)
2421 add_autoinc_candidates (data
, base
, step
, important
, use
);
2424 /* Adds standard iv candidates. */
2427 add_standard_iv_candidates (struct ivopts_data
*data
)
2429 add_candidate (data
, integer_zero_node
, integer_one_node
, true, NULL
);
2431 /* The same for a double-integer type if it is still fast enough. */
2433 (long_integer_type_node
) > TYPE_PRECISION (integer_type_node
)
2434 && TYPE_PRECISION (long_integer_type_node
) <= BITS_PER_WORD
)
2435 add_candidate (data
, build_int_cst (long_integer_type_node
, 0),
2436 build_int_cst (long_integer_type_node
, 1), true, NULL
);
2438 /* The same for a double-integer type if it is still fast enough. */
2440 (long_long_integer_type_node
) > TYPE_PRECISION (long_integer_type_node
)
2441 && TYPE_PRECISION (long_long_integer_type_node
) <= BITS_PER_WORD
)
2442 add_candidate (data
, build_int_cst (long_long_integer_type_node
, 0),
2443 build_int_cst (long_long_integer_type_node
, 1), true, NULL
);
2447 /* Adds candidates bases on the old induction variable IV. */
2450 add_old_iv_candidates (struct ivopts_data
*data
, struct iv
*iv
)
2454 struct iv_cand
*cand
;
2456 add_candidate (data
, iv
->base
, iv
->step
, true, NULL
);
2458 /* The same, but with initial value zero. */
2459 if (POINTER_TYPE_P (TREE_TYPE (iv
->base
)))
2460 add_candidate (data
, size_int (0), iv
->step
, true, NULL
);
2462 add_candidate (data
, build_int_cst (TREE_TYPE (iv
->base
), 0),
2463 iv
->step
, true, NULL
);
2465 phi
= SSA_NAME_DEF_STMT (iv
->ssa_name
);
2466 if (gimple_code (phi
) == GIMPLE_PHI
)
2468 /* Additionally record the possibility of leaving the original iv
2470 def
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (data
->current_loop
));
2471 cand
= add_candidate_1 (data
,
2472 iv
->base
, iv
->step
, true, IP_ORIGINAL
, NULL
,
2473 SSA_NAME_DEF_STMT (def
));
2474 cand
->var_before
= iv
->ssa_name
;
2475 cand
->var_after
= def
;
2479 /* Adds candidates based on the old induction variables. */
2482 add_old_ivs_candidates (struct ivopts_data
*data
)
2488 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
2490 iv
= ver_info (data
, i
)->iv
;
2491 if (iv
&& iv
->biv_p
&& !integer_zerop (iv
->step
))
2492 add_old_iv_candidates (data
, iv
);
2496 /* Adds candidates based on the value of the induction variable IV and USE. */
2499 add_iv_value_candidates (struct ivopts_data
*data
,
2500 struct iv
*iv
, struct iv_use
*use
)
2502 unsigned HOST_WIDE_INT offset
;
2506 add_candidate (data
, iv
->base
, iv
->step
, false, use
);
2508 /* The same, but with initial value zero. Make such variable important,
2509 since it is generic enough so that possibly many uses may be based
2511 basetype
= TREE_TYPE (iv
->base
);
2512 if (POINTER_TYPE_P (basetype
))
2513 basetype
= sizetype
;
2514 add_candidate (data
, build_int_cst (basetype
, 0),
2515 iv
->step
, true, use
);
2517 /* Third, try removing the constant offset. Make sure to even
2518 add a candidate for &a[0] vs. (T *)&a. */
2519 base
= strip_offset (iv
->base
, &offset
);
2521 || base
!= iv
->base
)
2522 add_candidate (data
, base
, iv
->step
, false, use
);
2525 /* Adds candidates based on the uses. */
2528 add_derived_ivs_candidates (struct ivopts_data
*data
)
2532 for (i
= 0; i
< n_iv_uses (data
); i
++)
2534 struct iv_use
*use
= iv_use (data
, i
);
2541 case USE_NONLINEAR_EXPR
:
2544 /* Just add the ivs based on the value of the iv used here. */
2545 add_iv_value_candidates (data
, use
->iv
, use
);
2554 /* Record important candidates and add them to related_cands bitmaps
2558 record_important_candidates (struct ivopts_data
*data
)
2563 for (i
= 0; i
< n_iv_cands (data
); i
++)
2565 struct iv_cand
*cand
= iv_cand (data
, i
);
2567 if (cand
->important
)
2568 bitmap_set_bit (data
->important_candidates
, i
);
2571 data
->consider_all_candidates
= (n_iv_cands (data
)
2572 <= CONSIDER_ALL_CANDIDATES_BOUND
);
2574 if (data
->consider_all_candidates
)
2576 /* We will not need "related_cands" bitmaps in this case,
2577 so release them to decrease peak memory consumption. */
2578 for (i
= 0; i
< n_iv_uses (data
); i
++)
2580 use
= iv_use (data
, i
);
2581 BITMAP_FREE (use
->related_cands
);
2586 /* Add important candidates to the related_cands bitmaps. */
2587 for (i
= 0; i
< n_iv_uses (data
); i
++)
2588 bitmap_ior_into (iv_use (data
, i
)->related_cands
,
2589 data
->important_candidates
);
2593 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
2594 If consider_all_candidates is true, we use a two-dimensional array, otherwise
2595 we allocate a simple list to every use. */
2598 alloc_use_cost_map (struct ivopts_data
*data
)
2600 unsigned i
, size
, s
;
2602 for (i
= 0; i
< n_iv_uses (data
); i
++)
2604 struct iv_use
*use
= iv_use (data
, i
);
2606 if (data
->consider_all_candidates
)
2607 size
= n_iv_cands (data
);
2610 s
= bitmap_count_bits (use
->related_cands
);
2612 /* Round up to the power of two, so that moduling by it is fast. */
2613 size
= s
? (1 << ceil_log2 (s
)) : 1;
2616 use
->n_map_members
= size
;
2617 use
->cost_map
= XCNEWVEC (struct cost_pair
, size
);
2621 /* Returns description of computation cost of expression whose runtime
2622 cost is RUNTIME and complexity corresponds to COMPLEXITY. */
2625 new_cost (unsigned runtime
, unsigned complexity
)
2629 cost
.cost
= runtime
;
2630 cost
.complexity
= complexity
;
2635 /* Adds costs COST1 and COST2. */
2638 add_costs (comp_cost cost1
, comp_cost cost2
)
2640 cost1
.cost
+= cost2
.cost
;
2641 cost1
.complexity
+= cost2
.complexity
;
2645 /* Subtracts costs COST1 and COST2. */
2648 sub_costs (comp_cost cost1
, comp_cost cost2
)
2650 cost1
.cost
-= cost2
.cost
;
2651 cost1
.complexity
-= cost2
.complexity
;
2656 /* Returns a negative number if COST1 < COST2, a positive number if
2657 COST1 > COST2, and 0 if COST1 = COST2. */
2660 compare_costs (comp_cost cost1
, comp_cost cost2
)
2662 if (cost1
.cost
== cost2
.cost
)
2663 return cost1
.complexity
- cost2
.complexity
;
2665 return cost1
.cost
- cost2
.cost
;
2668 /* Returns true if COST is infinite. */
2671 infinite_cost_p (comp_cost cost
)
2673 return cost
.cost
== INFTY
;
2676 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
2677 on invariants DEPENDS_ON and that the value used in expressing it
2678 is VALUE, and in case of iv elimination the comparison operator is COMP. */
2681 set_use_iv_cost (struct ivopts_data
*data
,
2682 struct iv_use
*use
, struct iv_cand
*cand
,
2683 comp_cost cost
, bitmap depends_on
, tree value
,
2684 enum tree_code comp
, int inv_expr_id
)
2688 if (infinite_cost_p (cost
))
2690 BITMAP_FREE (depends_on
);
2694 if (data
->consider_all_candidates
)
2696 use
->cost_map
[cand
->id
].cand
= cand
;
2697 use
->cost_map
[cand
->id
].cost
= cost
;
2698 use
->cost_map
[cand
->id
].depends_on
= depends_on
;
2699 use
->cost_map
[cand
->id
].value
= value
;
2700 use
->cost_map
[cand
->id
].comp
= comp
;
2701 use
->cost_map
[cand
->id
].inv_expr_id
= inv_expr_id
;
2705 /* n_map_members is a power of two, so this computes modulo. */
2706 s
= cand
->id
& (use
->n_map_members
- 1);
2707 for (i
= s
; i
< use
->n_map_members
; i
++)
2708 if (!use
->cost_map
[i
].cand
)
2710 for (i
= 0; i
< s
; i
++)
2711 if (!use
->cost_map
[i
].cand
)
2717 use
->cost_map
[i
].cand
= cand
;
2718 use
->cost_map
[i
].cost
= cost
;
2719 use
->cost_map
[i
].depends_on
= depends_on
;
2720 use
->cost_map
[i
].value
= value
;
2721 use
->cost_map
[i
].comp
= comp
;
2722 use
->cost_map
[i
].inv_expr_id
= inv_expr_id
;
2725 /* Gets cost of (USE, CANDIDATE) pair. */
2727 static struct cost_pair
*
2728 get_use_iv_cost (struct ivopts_data
*data
, struct iv_use
*use
,
2729 struct iv_cand
*cand
)
2732 struct cost_pair
*ret
;
2737 if (data
->consider_all_candidates
)
2739 ret
= use
->cost_map
+ cand
->id
;
2746 /* n_map_members is a power of two, so this computes modulo. */
2747 s
= cand
->id
& (use
->n_map_members
- 1);
2748 for (i
= s
; i
< use
->n_map_members
; i
++)
2749 if (use
->cost_map
[i
].cand
== cand
)
2750 return use
->cost_map
+ i
;
2751 else if (use
->cost_map
[i
].cand
== NULL
)
2753 for (i
= 0; i
< s
; i
++)
2754 if (use
->cost_map
[i
].cand
== cand
)
2755 return use
->cost_map
+ i
;
2756 else if (use
->cost_map
[i
].cand
== NULL
)
2762 /* Returns estimate on cost of computing SEQ. */
2765 seq_cost (rtx seq
, bool speed
)
2770 for (; seq
; seq
= NEXT_INSN (seq
))
2772 set
= single_set (seq
);
2774 cost
+= set_src_cost (SET_SRC (set
), speed
);
2782 /* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
2784 produce_memory_decl_rtl (tree obj
, int *regno
)
2786 addr_space_t as
= TYPE_ADDR_SPACE (TREE_TYPE (obj
));
2787 enum machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
2791 if (TREE_STATIC (obj
) || DECL_EXTERNAL (obj
))
2793 const char *name
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj
));
2794 x
= gen_rtx_SYMBOL_REF (address_mode
, name
);
2795 SET_SYMBOL_REF_DECL (x
, obj
);
2796 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
2797 set_mem_addr_space (x
, as
);
2798 targetm
.encode_section_info (obj
, x
, true);
2802 x
= gen_raw_REG (address_mode
, (*regno
)++);
2803 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
2804 set_mem_addr_space (x
, as
);
2810 /* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
2811 walk_tree. DATA contains the actual fake register number. */
2814 prepare_decl_rtl (tree
*expr_p
, int *ws
, void *data
)
2816 tree obj
= NULL_TREE
;
2818 int *regno
= (int *) data
;
2820 switch (TREE_CODE (*expr_p
))
2823 for (expr_p
= &TREE_OPERAND (*expr_p
, 0);
2824 handled_component_p (*expr_p
);
2825 expr_p
= &TREE_OPERAND (*expr_p
, 0))
2828 if (DECL_P (obj
) && HAS_RTL_P (obj
) && !DECL_RTL_SET_P (obj
))
2829 x
= produce_memory_decl_rtl (obj
, regno
);
2834 obj
= SSA_NAME_VAR (*expr_p
);
2835 /* Defer handling of anonymous SSA_NAMEs to the expander. */
2838 if (!DECL_RTL_SET_P (obj
))
2839 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2848 if (DECL_RTL_SET_P (obj
))
2851 if (DECL_MODE (obj
) == BLKmode
)
2852 x
= produce_memory_decl_rtl (obj
, regno
);
2854 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2864 decl_rtl_to_reset
.safe_push (obj
);
2865 SET_DECL_RTL (obj
, x
);
2871 /* Determines cost of the computation of EXPR. */
2874 computation_cost (tree expr
, bool speed
)
2877 tree type
= TREE_TYPE (expr
);
2879 /* Avoid using hard regs in ways which may be unsupported. */
2880 int regno
= LAST_VIRTUAL_REGISTER
+ 1;
2881 struct cgraph_node
*node
= cgraph_get_node (current_function_decl
);
2882 enum node_frequency real_frequency
= node
->frequency
;
2884 node
->frequency
= NODE_FREQUENCY_NORMAL
;
2885 crtl
->maybe_hot_insn_p
= speed
;
2886 walk_tree (&expr
, prepare_decl_rtl
, ®no
, NULL
);
2888 rslt
= expand_expr (expr
, NULL_RTX
, TYPE_MODE (type
), EXPAND_NORMAL
);
2891 default_rtl_profile ();
2892 node
->frequency
= real_frequency
;
2894 cost
= seq_cost (seq
, speed
);
2896 cost
+= address_cost (XEXP (rslt
, 0), TYPE_MODE (type
),
2897 TYPE_ADDR_SPACE (type
), speed
);
2898 else if (!REG_P (rslt
))
2899 cost
+= set_src_cost (rslt
, speed
);
2904 /* Returns variable containing the value of candidate CAND at statement AT. */
2907 var_at_stmt (struct loop
*loop
, struct iv_cand
*cand
, gimple stmt
)
2909 if (stmt_after_increment (loop
, cand
, stmt
))
2910 return cand
->var_after
;
2912 return cand
->var_before
;
2915 /* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
2916 same precision that is at least as wide as the precision of TYPE, stores
2917 BA to A and BB to B, and returns the type of BA. Otherwise, returns the
2921 determine_common_wider_type (tree
*a
, tree
*b
)
2923 tree wider_type
= NULL
;
2925 tree atype
= TREE_TYPE (*a
);
2927 if (CONVERT_EXPR_P (*a
))
2929 suba
= TREE_OPERAND (*a
, 0);
2930 wider_type
= TREE_TYPE (suba
);
2931 if (TYPE_PRECISION (wider_type
) < TYPE_PRECISION (atype
))
2937 if (CONVERT_EXPR_P (*b
))
2939 subb
= TREE_OPERAND (*b
, 0);
2940 if (TYPE_PRECISION (wider_type
) != TYPE_PRECISION (TREE_TYPE (subb
)))
2951 /* Determines the expression by that USE is expressed from induction variable
2952 CAND at statement AT in LOOP. The expression is stored in a decomposed
2953 form into AFF. Returns false if USE cannot be expressed using CAND. */
2956 get_computation_aff (struct loop
*loop
,
2957 struct iv_use
*use
, struct iv_cand
*cand
, gimple at
,
2958 struct affine_tree_combination
*aff
)
2960 tree ubase
= use
->iv
->base
;
2961 tree ustep
= use
->iv
->step
;
2962 tree cbase
= cand
->iv
->base
;
2963 tree cstep
= cand
->iv
->step
, cstep_common
;
2964 tree utype
= TREE_TYPE (ubase
), ctype
= TREE_TYPE (cbase
);
2965 tree common_type
, var
;
2967 aff_tree cbase_aff
, var_aff
;
2970 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
2972 /* We do not have a precision to express the values of use. */
2976 var
= var_at_stmt (loop
, cand
, at
);
2977 uutype
= unsigned_type_for (utype
);
2979 /* If the conversion is not noop, perform it. */
2980 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
2982 cstep
= fold_convert (uutype
, cstep
);
2983 cbase
= fold_convert (uutype
, cbase
);
2984 var
= fold_convert (uutype
, var
);
2987 if (!constant_multiple_of (ustep
, cstep
, &rat
))
2990 /* In case both UBASE and CBASE are shortened to UUTYPE from some common
2991 type, we achieve better folding by computing their difference in this
2992 wider type, and cast the result to UUTYPE. We do not need to worry about
2993 overflows, as all the arithmetics will in the end be performed in UUTYPE
2995 common_type
= determine_common_wider_type (&ubase
, &cbase
);
2997 /* use = ubase - ratio * cbase + ratio * var. */
2998 tree_to_aff_combination (ubase
, common_type
, aff
);
2999 tree_to_aff_combination (cbase
, common_type
, &cbase_aff
);
3000 tree_to_aff_combination (var
, uutype
, &var_aff
);
3002 /* We need to shift the value if we are after the increment. */
3003 if (stmt_after_increment (loop
, cand
, at
))
3007 if (common_type
!= uutype
)
3008 cstep_common
= fold_convert (common_type
, cstep
);
3010 cstep_common
= cstep
;
3012 tree_to_aff_combination (cstep_common
, common_type
, &cstep_aff
);
3013 aff_combination_add (&cbase_aff
, &cstep_aff
);
3016 aff_combination_scale (&cbase_aff
, -rat
);
3017 aff_combination_add (aff
, &cbase_aff
);
3018 if (common_type
!= uutype
)
3019 aff_combination_convert (aff
, uutype
);
3021 aff_combination_scale (&var_aff
, rat
);
3022 aff_combination_add (aff
, &var_aff
);
3027 /* Return the type of USE. */
3030 get_use_type (struct iv_use
*use
)
3032 tree base_type
= TREE_TYPE (use
->iv
->base
);
3035 if (use
->type
== USE_ADDRESS
)
3037 /* The base_type may be a void pointer. Create a pointer type based on
3038 the mem_ref instead. */
3039 type
= build_pointer_type (TREE_TYPE (*use
->op_p
));
3040 gcc_assert (TYPE_ADDR_SPACE (TREE_TYPE (type
))
3041 == TYPE_ADDR_SPACE (TREE_TYPE (base_type
)));
3049 /* Determines the expression by that USE is expressed from induction variable
3050 CAND at statement AT in LOOP. The computation is unshared. */
3053 get_computation_at (struct loop
*loop
,
3054 struct iv_use
*use
, struct iv_cand
*cand
, gimple at
)
3057 tree type
= get_use_type (use
);
3059 if (!get_computation_aff (loop
, use
, cand
, at
, &aff
))
3061 unshare_aff_combination (&aff
);
3062 return fold_convert (type
, aff_combination_to_tree (&aff
));
3065 /* Determines the expression by that USE is expressed from induction variable
3066 CAND in LOOP. The computation is unshared. */
3069 get_computation (struct loop
*loop
, struct iv_use
*use
, struct iv_cand
*cand
)
3071 return get_computation_at (loop
, use
, cand
, use
->stmt
);
3074 /* Adjust the cost COST for being in loop setup rather than loop body.
3075 If we're optimizing for space, the loop setup overhead is constant;
3076 if we're optimizing for speed, amortize it over the per-iteration cost. */
3078 adjust_setup_cost (struct ivopts_data
*data
, unsigned cost
)
3082 else if (optimize_loop_for_speed_p (data
->current_loop
))
3083 return cost
/ avg_loop_niter (data
->current_loop
);
3088 /* Returns true if multiplying by RATIO is allowed in an address. Test the
3089 validity for a memory reference accessing memory of mode MODE in
3090 address space AS. */
3094 multiplier_allowed_in_address_p (HOST_WIDE_INT ratio
, enum machine_mode mode
,
3097 #define MAX_RATIO 128
3098 unsigned int data_index
= (int) as
* MAX_MACHINE_MODE
+ (int) mode
;
3099 static vec
<sbitmap
> valid_mult_list
;
3102 if (data_index
>= valid_mult_list
.length ())
3103 valid_mult_list
.safe_grow_cleared (data_index
+ 1);
3105 valid_mult
= valid_mult_list
[data_index
];
3108 enum machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
3109 rtx reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
3113 valid_mult
= sbitmap_alloc (2 * MAX_RATIO
+ 1);
3114 bitmap_clear (valid_mult
);
3115 addr
= gen_rtx_fmt_ee (MULT
, address_mode
, reg1
, NULL_RTX
);
3116 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
3118 XEXP (addr
, 1) = gen_int_mode (i
, address_mode
);
3119 if (memory_address_addr_space_p (mode
, addr
, as
))
3120 bitmap_set_bit (valid_mult
, i
+ MAX_RATIO
);
3123 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3125 fprintf (dump_file
, " allowed multipliers:");
3126 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
3127 if (bitmap_bit_p (valid_mult
, i
+ MAX_RATIO
))
3128 fprintf (dump_file
, " %d", (int) i
);
3129 fprintf (dump_file
, "\n");
3130 fprintf (dump_file
, "\n");
3133 valid_mult_list
[data_index
] = valid_mult
;
3136 if (ratio
> MAX_RATIO
|| ratio
< -MAX_RATIO
)
3139 return bitmap_bit_p (valid_mult
, ratio
+ MAX_RATIO
);
3142 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
3143 If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
3144 variable is omitted. Compute the cost for a memory reference that accesses
3145 a memory location of mode MEM_MODE in address space AS.
3147 MAY_AUTOINC is set to true if the autoincrement (increasing index by
3148 size of MEM_MODE / RATIO) is available. To make this determination, we
3149 look at the size of the increment to be made, which is given in CSTEP.
3150 CSTEP may be zero if the step is unknown.
3151 STMT_AFTER_INC is true iff the statement we're looking at is after the
3152 increment of the original biv.
3154 TODO -- there must be some better way. This all is quite crude. */
3156 typedef struct address_cost_data_s
3158 HOST_WIDE_INT min_offset
, max_offset
;
3159 unsigned costs
[2][2][2][2];
3160 } *address_cost_data
;
3164 get_address_cost (bool symbol_present
, bool var_present
,
3165 unsigned HOST_WIDE_INT offset
, HOST_WIDE_INT ratio
,
3166 HOST_WIDE_INT cstep
, enum machine_mode mem_mode
,
3167 addr_space_t as
, bool speed
,
3168 bool stmt_after_inc
, bool *may_autoinc
)
3170 enum machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
3171 static vec
<address_cost_data
> address_cost_data_list
;
3172 unsigned int data_index
= (int) as
* MAX_MACHINE_MODE
+ (int) mem_mode
;
3173 address_cost_data data
;
3174 static bool has_preinc
[MAX_MACHINE_MODE
], has_postinc
[MAX_MACHINE_MODE
];
3175 static bool has_predec
[MAX_MACHINE_MODE
], has_postdec
[MAX_MACHINE_MODE
];
3176 unsigned cost
, acost
, complexity
;
3177 bool offset_p
, ratio_p
, autoinc
;
3178 HOST_WIDE_INT s_offset
, autoinc_offset
, msize
;
3179 unsigned HOST_WIDE_INT mask
;
3182 if (data_index
>= address_cost_data_list
.length ())
3183 address_cost_data_list
.safe_grow_cleared (data_index
+ 1);
3185 data
= address_cost_data_list
[data_index
];
3189 HOST_WIDE_INT rat
, off
= 0;
3190 int old_cse_not_expected
, width
;
3191 unsigned sym_p
, var_p
, off_p
, rat_p
, add_c
;
3192 rtx seq
, addr
, base
;
3195 data
= (address_cost_data
) xcalloc (1, sizeof (*data
));
3197 reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
3199 width
= GET_MODE_BITSIZE (address_mode
) - 1;
3200 if (width
> (HOST_BITS_PER_WIDE_INT
- 1))
3201 width
= HOST_BITS_PER_WIDE_INT
- 1;
3202 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, reg1
, NULL_RTX
);
3204 for (i
= width
; i
>= 0; i
--)
3206 off
= -((unsigned HOST_WIDE_INT
) 1 << i
);
3207 XEXP (addr
, 1) = gen_int_mode (off
, address_mode
);
3208 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
3211 data
->min_offset
= (i
== -1? 0 : off
);
3213 for (i
= width
; i
>= 0; i
--)
3215 off
= ((unsigned HOST_WIDE_INT
) 1 << i
) - 1;
3216 XEXP (addr
, 1) = gen_int_mode (off
, address_mode
);
3217 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
3222 data
->max_offset
= off
;
3224 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3226 fprintf (dump_file
, "get_address_cost:\n");
3227 fprintf (dump_file
, " min offset %s " HOST_WIDE_INT_PRINT_DEC
"\n",
3228 GET_MODE_NAME (mem_mode
),
3230 fprintf (dump_file
, " max offset %s " HOST_WIDE_INT_PRINT_DEC
"\n",
3231 GET_MODE_NAME (mem_mode
),
3236 for (i
= 2; i
<= MAX_RATIO
; i
++)
3237 if (multiplier_allowed_in_address_p (i
, mem_mode
, as
))
3243 /* Compute the cost of various addressing modes. */
3245 reg0
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
3246 reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 2);
3248 if (USE_LOAD_PRE_DECREMENT (mem_mode
)
3249 || USE_STORE_PRE_DECREMENT (mem_mode
))
3251 addr
= gen_rtx_PRE_DEC (address_mode
, reg0
);
3252 has_predec
[mem_mode
]
3253 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3255 if (USE_LOAD_POST_DECREMENT (mem_mode
)
3256 || USE_STORE_POST_DECREMENT (mem_mode
))
3258 addr
= gen_rtx_POST_DEC (address_mode
, reg0
);
3259 has_postdec
[mem_mode
]
3260 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3262 if (USE_LOAD_PRE_INCREMENT (mem_mode
)
3263 || USE_STORE_PRE_DECREMENT (mem_mode
))
3265 addr
= gen_rtx_PRE_INC (address_mode
, reg0
);
3266 has_preinc
[mem_mode
]
3267 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3269 if (USE_LOAD_POST_INCREMENT (mem_mode
)
3270 || USE_STORE_POST_INCREMENT (mem_mode
))
3272 addr
= gen_rtx_POST_INC (address_mode
, reg0
);
3273 has_postinc
[mem_mode
]
3274 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3276 for (i
= 0; i
< 16; i
++)
3279 var_p
= (i
>> 1) & 1;
3280 off_p
= (i
>> 2) & 1;
3281 rat_p
= (i
>> 3) & 1;
3285 addr
= gen_rtx_fmt_ee (MULT
, address_mode
, addr
,
3286 gen_int_mode (rat
, address_mode
));
3289 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, addr
, reg1
);
3293 base
= gen_rtx_SYMBOL_REF (address_mode
, ggc_strdup (""));
3294 /* ??? We can run into trouble with some backends by presenting
3295 it with symbols which haven't been properly passed through
3296 targetm.encode_section_info. By setting the local bit, we
3297 enhance the probability of things working. */
3298 SYMBOL_REF_FLAGS (base
) = SYMBOL_FLAG_LOCAL
;
3301 base
= gen_rtx_fmt_e (CONST
, address_mode
,
3303 (PLUS
, address_mode
, base
,
3304 gen_int_mode (off
, address_mode
)));
3307 base
= gen_int_mode (off
, address_mode
);
3312 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, addr
, base
);
3315 /* To avoid splitting addressing modes, pretend that no cse will
3317 old_cse_not_expected
= cse_not_expected
;
3318 cse_not_expected
= true;
3319 addr
= memory_address_addr_space (mem_mode
, addr
, as
);
3320 cse_not_expected
= old_cse_not_expected
;
3324 acost
= seq_cost (seq
, speed
);
3325 acost
+= address_cost (addr
, mem_mode
, as
, speed
);
3329 data
->costs
[sym_p
][var_p
][off_p
][rat_p
] = acost
;
3332 /* On some targets, it is quite expensive to load symbol to a register,
3333 which makes addresses that contain symbols look much more expensive.
3334 However, the symbol will have to be loaded in any case before the
3335 loop (and quite likely we have it in register already), so it does not
3336 make much sense to penalize them too heavily. So make some final
3337 tweaks for the SYMBOL_PRESENT modes:
3339 If VAR_PRESENT is false, and the mode obtained by changing symbol to
3340 var is cheaper, use this mode with small penalty.
3341 If VAR_PRESENT is true, try whether the mode with
3342 SYMBOL_PRESENT = false is cheaper even with cost of addition, and
3343 if this is the case, use it. */
3344 add_c
= add_cost (speed
, address_mode
);
3345 for (i
= 0; i
< 8; i
++)
3348 off_p
= (i
>> 1) & 1;
3349 rat_p
= (i
>> 2) & 1;
3351 acost
= data
->costs
[0][1][off_p
][rat_p
] + 1;
3355 if (acost
< data
->costs
[1][var_p
][off_p
][rat_p
])
3356 data
->costs
[1][var_p
][off_p
][rat_p
] = acost
;
3359 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3361 fprintf (dump_file
, "Address costs:\n");
3363 for (i
= 0; i
< 16; i
++)
3366 var_p
= (i
>> 1) & 1;
3367 off_p
= (i
>> 2) & 1;
3368 rat_p
= (i
>> 3) & 1;
3370 fprintf (dump_file
, " ");
3372 fprintf (dump_file
, "sym + ");
3374 fprintf (dump_file
, "var + ");
3376 fprintf (dump_file
, "cst + ");
3378 fprintf (dump_file
, "rat * ");
3380 acost
= data
->costs
[sym_p
][var_p
][off_p
][rat_p
];
3381 fprintf (dump_file
, "index costs %d\n", acost
);
3383 if (has_predec
[mem_mode
] || has_postdec
[mem_mode
]
3384 || has_preinc
[mem_mode
] || has_postinc
[mem_mode
])
3385 fprintf (dump_file
, " May include autoinc/dec\n");
3386 fprintf (dump_file
, "\n");
3389 address_cost_data_list
[data_index
] = data
;
3392 bits
= GET_MODE_BITSIZE (address_mode
);
3393 mask
= ~(~(unsigned HOST_WIDE_INT
) 0 << (bits
- 1) << 1);
3395 if ((offset
>> (bits
- 1) & 1))
3400 msize
= GET_MODE_SIZE (mem_mode
);
3401 autoinc_offset
= offset
;
3403 autoinc_offset
+= ratio
* cstep
;
3404 if (symbol_present
|| var_present
|| ratio
!= 1)
3406 else if ((has_postinc
[mem_mode
] && autoinc_offset
== 0
3408 || (has_postdec
[mem_mode
] && autoinc_offset
== 0
3410 || (has_preinc
[mem_mode
] && autoinc_offset
== msize
3412 || (has_predec
[mem_mode
] && autoinc_offset
== -msize
3413 && msize
== -cstep
))
3417 offset_p
= (s_offset
!= 0
3418 && data
->min_offset
<= s_offset
3419 && s_offset
<= data
->max_offset
);
3420 ratio_p
= (ratio
!= 1
3421 && multiplier_allowed_in_address_p (ratio
, mem_mode
, as
));
3423 if (ratio
!= 1 && !ratio_p
)
3424 cost
+= mult_by_coeff_cost (ratio
, address_mode
, speed
);
3426 if (s_offset
&& !offset_p
&& !symbol_present
)
3427 cost
+= add_cost (speed
, address_mode
);
3430 *may_autoinc
= autoinc
;
3431 acost
= data
->costs
[symbol_present
][var_present
][offset_p
][ratio_p
];
3432 complexity
= (symbol_present
!= 0) + (var_present
!= 0) + offset_p
+ ratio_p
;
3433 return new_cost (cost
+ acost
, complexity
);
3436 /* Calculate the SPEED or size cost of shiftadd EXPR in MODE. MULT is the
3437 the EXPR operand holding the shift. COST0 and COST1 are the costs for
3438 calculating the operands of EXPR. Returns true if successful, and returns
3439 the cost in COST. */
3442 get_shiftadd_cost (tree expr
, enum machine_mode mode
, comp_cost cost0
,
3443 comp_cost cost1
, tree mult
, bool speed
, comp_cost
*cost
)
3446 tree op1
= TREE_OPERAND (expr
, 1);
3447 tree cst
= TREE_OPERAND (mult
, 1);
3448 tree multop
= TREE_OPERAND (mult
, 0);
3449 int m
= exact_log2 (int_cst_value (cst
));
3450 int maxm
= MIN (BITS_PER_WORD
, GET_MODE_BITSIZE (mode
));
3453 if (!(m
>= 0 && m
< maxm
))
3456 sa_cost
= (TREE_CODE (expr
) != MINUS_EXPR
3457 ? shiftadd_cost (speed
, mode
, m
)
3459 ? shiftsub1_cost (speed
, mode
, m
)
3460 : shiftsub0_cost (speed
, mode
, m
)));
3461 res
= new_cost (sa_cost
, 0);
3462 res
= add_costs (res
, mult
== op1
? cost0
: cost1
);
3464 STRIP_NOPS (multop
);
3465 if (!is_gimple_val (multop
))
3466 res
= add_costs (res
, force_expr_to_var_cost (multop
, speed
));
3472 /* Estimates cost of forcing expression EXPR into a variable. */
3475 force_expr_to_var_cost (tree expr
, bool speed
)
3477 static bool costs_initialized
= false;
3478 static unsigned integer_cost
[2];
3479 static unsigned symbol_cost
[2];
3480 static unsigned address_cost
[2];
3482 comp_cost cost0
, cost1
, cost
;
3483 enum machine_mode mode
;
3485 if (!costs_initialized
)
3487 tree type
= build_pointer_type (integer_type_node
);
3492 var
= create_tmp_var_raw (integer_type_node
, "test_var");
3493 TREE_STATIC (var
) = 1;
3494 x
= produce_memory_decl_rtl (var
, NULL
);
3495 SET_DECL_RTL (var
, x
);
3497 addr
= build1 (ADDR_EXPR
, type
, var
);
3500 for (i
= 0; i
< 2; i
++)
3502 integer_cost
[i
] = computation_cost (build_int_cst (integer_type_node
,
3505 symbol_cost
[i
] = computation_cost (addr
, i
) + 1;
3508 = computation_cost (fold_build_pointer_plus_hwi (addr
, 2000), i
) + 1;
3509 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3511 fprintf (dump_file
, "force_expr_to_var_cost %s costs:\n", i
? "speed" : "size");
3512 fprintf (dump_file
, " integer %d\n", (int) integer_cost
[i
]);
3513 fprintf (dump_file
, " symbol %d\n", (int) symbol_cost
[i
]);
3514 fprintf (dump_file
, " address %d\n", (int) address_cost
[i
]);
3515 fprintf (dump_file
, " other %d\n", (int) target_spill_cost
[i
]);
3516 fprintf (dump_file
, "\n");
3520 costs_initialized
= true;
3525 if (SSA_VAR_P (expr
))
3528 if (is_gimple_min_invariant (expr
))
3530 if (TREE_CODE (expr
) == INTEGER_CST
)
3531 return new_cost (integer_cost
[speed
], 0);
3533 if (TREE_CODE (expr
) == ADDR_EXPR
)
3535 tree obj
= TREE_OPERAND (expr
, 0);
3537 if (TREE_CODE (obj
) == VAR_DECL
3538 || TREE_CODE (obj
) == PARM_DECL
3539 || TREE_CODE (obj
) == RESULT_DECL
)
3540 return new_cost (symbol_cost
[speed
], 0);
3543 return new_cost (address_cost
[speed
], 0);
3546 switch (TREE_CODE (expr
))
3548 case POINTER_PLUS_EXPR
:
3552 op0
= TREE_OPERAND (expr
, 0);
3553 op1
= TREE_OPERAND (expr
, 1);
3557 if (is_gimple_val (op0
))
3560 cost0
= force_expr_to_var_cost (op0
, speed
);
3562 if (is_gimple_val (op1
))
3565 cost1
= force_expr_to_var_cost (op1
, speed
);
3570 op0
= TREE_OPERAND (expr
, 0);
3574 if (is_gimple_val (op0
))
3577 cost0
= force_expr_to_var_cost (op0
, speed
);
3583 /* Just an arbitrary value, FIXME. */
3584 return new_cost (target_spill_cost
[speed
], 0);
3587 mode
= TYPE_MODE (TREE_TYPE (expr
));
3588 switch (TREE_CODE (expr
))
3590 case POINTER_PLUS_EXPR
:
3594 cost
= new_cost (add_cost (speed
, mode
), 0);
3595 if (TREE_CODE (expr
) != NEGATE_EXPR
)
3597 tree mult
= NULL_TREE
;
3599 if (TREE_CODE (op1
) == MULT_EXPR
)
3601 else if (TREE_CODE (op0
) == MULT_EXPR
)
3604 if (mult
!= NULL_TREE
3605 && cst_and_fits_in_hwi (TREE_OPERAND (mult
, 1))
3606 && get_shiftadd_cost (expr
, mode
, cost0
, cost1
, mult
,
3613 if (cst_and_fits_in_hwi (op0
))
3614 cost
= new_cost (mult_by_coeff_cost (int_cst_value (op0
),
3616 else if (cst_and_fits_in_hwi (op1
))
3617 cost
= new_cost (mult_by_coeff_cost (int_cst_value (op1
),
3620 return new_cost (target_spill_cost
[speed
], 0);
3627 cost
= add_costs (cost
, cost0
);
3628 cost
= add_costs (cost
, cost1
);
3630 /* Bound the cost by target_spill_cost. The parts of complicated
3631 computations often are either loop invariant or at least can
3632 be shared between several iv uses, so letting this grow without
3633 limits would not give reasonable results. */
3634 if (cost
.cost
> (int) target_spill_cost
[speed
])
3635 cost
.cost
= target_spill_cost
[speed
];
3640 /* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
3641 invariants the computation depends on. */
3644 force_var_cost (struct ivopts_data
*data
,
3645 tree expr
, bitmap
*depends_on
)
3649 fd_ivopts_data
= data
;
3650 walk_tree (&expr
, find_depends
, depends_on
, NULL
);
3653 return force_expr_to_var_cost (expr
, data
->speed
);
3656 /* Estimates cost of expressing address ADDR as var + symbol + offset. The
3657 value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
3658 to false if the corresponding part is missing. DEPENDS_ON is a set of the
3659 invariants the computation depends on. */
3662 split_address_cost (struct ivopts_data
*data
,
3663 tree addr
, bool *symbol_present
, bool *var_present
,
3664 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3667 HOST_WIDE_INT bitsize
;
3668 HOST_WIDE_INT bitpos
;
3670 enum machine_mode mode
;
3671 int unsignedp
, volatilep
;
3673 core
= get_inner_reference (addr
, &bitsize
, &bitpos
, &toffset
, &mode
,
3674 &unsignedp
, &volatilep
, false);
3677 || bitpos
% BITS_PER_UNIT
!= 0
3678 || TREE_CODE (core
) != VAR_DECL
)
3680 *symbol_present
= false;
3681 *var_present
= true;
3682 fd_ivopts_data
= data
;
3683 walk_tree (&addr
, find_depends
, depends_on
, NULL
);
3684 return new_cost (target_spill_cost
[data
->speed
], 0);
3687 *offset
+= bitpos
/ BITS_PER_UNIT
;
3688 if (TREE_STATIC (core
)
3689 || DECL_EXTERNAL (core
))
3691 *symbol_present
= true;
3692 *var_present
= false;
3696 *symbol_present
= false;
3697 *var_present
= true;
3701 /* Estimates cost of expressing difference of addresses E1 - E2 as
3702 var + symbol + offset. The value of offset is added to OFFSET,
3703 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3704 part is missing. DEPENDS_ON is a set of the invariants the computation
3708 ptr_difference_cost (struct ivopts_data
*data
,
3709 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
3710 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3712 HOST_WIDE_INT diff
= 0;
3713 aff_tree aff_e1
, aff_e2
;
3716 gcc_assert (TREE_CODE (e1
) == ADDR_EXPR
);
3718 if (ptr_difference_const (e1
, e2
, &diff
))
3721 *symbol_present
= false;
3722 *var_present
= false;
3726 if (integer_zerop (e2
))
3727 return split_address_cost (data
, TREE_OPERAND (e1
, 0),
3728 symbol_present
, var_present
, offset
, depends_on
);
3730 *symbol_present
= false;
3731 *var_present
= true;
3733 type
= signed_type_for (TREE_TYPE (e1
));
3734 tree_to_aff_combination (e1
, type
, &aff_e1
);
3735 tree_to_aff_combination (e2
, type
, &aff_e2
);
3736 aff_combination_scale (&aff_e2
, double_int_minus_one
);
3737 aff_combination_add (&aff_e1
, &aff_e2
);
3739 return force_var_cost (data
, aff_combination_to_tree (&aff_e1
), depends_on
);
3742 /* Estimates cost of expressing difference E1 - E2 as
3743 var + symbol + offset. The value of offset is added to OFFSET,
3744 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3745 part is missing. DEPENDS_ON is a set of the invariants the computation
3749 difference_cost (struct ivopts_data
*data
,
3750 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
3751 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3753 enum machine_mode mode
= TYPE_MODE (TREE_TYPE (e1
));
3754 unsigned HOST_WIDE_INT off1
, off2
;
3755 aff_tree aff_e1
, aff_e2
;
3758 e1
= strip_offset (e1
, &off1
);
3759 e2
= strip_offset (e2
, &off2
);
3760 *offset
+= off1
- off2
;
3765 if (TREE_CODE (e1
) == ADDR_EXPR
)
3766 return ptr_difference_cost (data
, e1
, e2
, symbol_present
, var_present
,
3767 offset
, depends_on
);
3768 *symbol_present
= false;
3770 if (operand_equal_p (e1
, e2
, 0))
3772 *var_present
= false;
3776 *var_present
= true;
3778 if (integer_zerop (e2
))
3779 return force_var_cost (data
, e1
, depends_on
);
3781 if (integer_zerop (e1
))
3783 comp_cost cost
= force_var_cost (data
, e2
, depends_on
);
3784 cost
.cost
+= mult_by_coeff_cost (-1, mode
, data
->speed
);
3788 type
= signed_type_for (TREE_TYPE (e1
));
3789 tree_to_aff_combination (e1
, type
, &aff_e1
);
3790 tree_to_aff_combination (e2
, type
, &aff_e2
);
3791 aff_combination_scale (&aff_e2
, double_int_minus_one
);
3792 aff_combination_add (&aff_e1
, &aff_e2
);
3794 return force_var_cost (data
, aff_combination_to_tree (&aff_e1
), depends_on
);
3797 /* Returns true if AFF1 and AFF2 are identical. */
3800 compare_aff_trees (aff_tree
*aff1
, aff_tree
*aff2
)
3804 if (aff1
->n
!= aff2
->n
)
3807 for (i
= 0; i
< aff1
->n
; i
++)
3809 if (aff1
->elts
[i
].coef
!= aff2
->elts
[i
].coef
)
3812 if (!operand_equal_p (aff1
->elts
[i
].val
, aff2
->elts
[i
].val
, 0))
3818 /* Stores EXPR in DATA->inv_expr_tab, and assigns it an inv_expr_id. */
3821 get_expr_id (struct ivopts_data
*data
, tree expr
)
3823 struct iv_inv_expr_ent ent
;
3824 struct iv_inv_expr_ent
**slot
;
3827 ent
.hash
= iterative_hash_expr (expr
, 0);
3828 slot
= data
->inv_expr_tab
.find_slot (&ent
, INSERT
);
3832 *slot
= XNEW (struct iv_inv_expr_ent
);
3833 (*slot
)->expr
= expr
;
3834 (*slot
)->hash
= ent
.hash
;
3835 (*slot
)->id
= data
->inv_expr_id
++;
3839 /* Returns the pseudo expr id if expression UBASE - RATIO * CBASE
3840 requires a new compiler generated temporary. Returns -1 otherwise.
3841 ADDRESS_P is a flag indicating if the expression is for address
3845 get_loop_invariant_expr_id (struct ivopts_data
*data
, tree ubase
,
3846 tree cbase
, HOST_WIDE_INT ratio
,
3849 aff_tree ubase_aff
, cbase_aff
;
3857 if ((TREE_CODE (ubase
) == INTEGER_CST
)
3858 && (TREE_CODE (cbase
) == INTEGER_CST
))
3861 /* Strips the constant part. */
3862 if (TREE_CODE (ubase
) == PLUS_EXPR
3863 || TREE_CODE (ubase
) == MINUS_EXPR
3864 || TREE_CODE (ubase
) == POINTER_PLUS_EXPR
)
3866 if (TREE_CODE (TREE_OPERAND (ubase
, 1)) == INTEGER_CST
)
3867 ubase
= TREE_OPERAND (ubase
, 0);
3870 /* Strips the constant part. */
3871 if (TREE_CODE (cbase
) == PLUS_EXPR
3872 || TREE_CODE (cbase
) == MINUS_EXPR
3873 || TREE_CODE (cbase
) == POINTER_PLUS_EXPR
)
3875 if (TREE_CODE (TREE_OPERAND (cbase
, 1)) == INTEGER_CST
)
3876 cbase
= TREE_OPERAND (cbase
, 0);
3881 if (((TREE_CODE (ubase
) == SSA_NAME
)
3882 || (TREE_CODE (ubase
) == ADDR_EXPR
3883 && is_gimple_min_invariant (ubase
)))
3884 && (TREE_CODE (cbase
) == INTEGER_CST
))
3887 if (((TREE_CODE (cbase
) == SSA_NAME
)
3888 || (TREE_CODE (cbase
) == ADDR_EXPR
3889 && is_gimple_min_invariant (cbase
)))
3890 && (TREE_CODE (ubase
) == INTEGER_CST
))
3896 if (operand_equal_p (ubase
, cbase
, 0))
3899 if (TREE_CODE (ubase
) == ADDR_EXPR
3900 && TREE_CODE (cbase
) == ADDR_EXPR
)
3904 usym
= TREE_OPERAND (ubase
, 0);
3905 csym
= TREE_OPERAND (cbase
, 0);
3906 if (TREE_CODE (usym
) == ARRAY_REF
)
3908 tree ind
= TREE_OPERAND (usym
, 1);
3909 if (TREE_CODE (ind
) == INTEGER_CST
3910 && host_integerp (ind
, 0)
3911 && TREE_INT_CST_LOW (ind
) == 0)
3912 usym
= TREE_OPERAND (usym
, 0);
3914 if (TREE_CODE (csym
) == ARRAY_REF
)
3916 tree ind
= TREE_OPERAND (csym
, 1);
3917 if (TREE_CODE (ind
) == INTEGER_CST
3918 && host_integerp (ind
, 0)
3919 && TREE_INT_CST_LOW (ind
) == 0)
3920 csym
= TREE_OPERAND (csym
, 0);
3922 if (operand_equal_p (usym
, csym
, 0))
3925 /* Now do more complex comparison */
3926 tree_to_aff_combination (ubase
, TREE_TYPE (ubase
), &ubase_aff
);
3927 tree_to_aff_combination (cbase
, TREE_TYPE (cbase
), &cbase_aff
);
3928 if (compare_aff_trees (&ubase_aff
, &cbase_aff
))
3932 tree_to_aff_combination (ub
, TREE_TYPE (ub
), &ubase_aff
);
3933 tree_to_aff_combination (cb
, TREE_TYPE (cb
), &cbase_aff
);
3935 aff_combination_scale (&cbase_aff
, double_int::from_shwi (-1 * ratio
));
3936 aff_combination_add (&ubase_aff
, &cbase_aff
);
3937 expr
= aff_combination_to_tree (&ubase_aff
);
3938 return get_expr_id (data
, expr
);
3943 /* Determines the cost of the computation by that USE is expressed
3944 from induction variable CAND. If ADDRESS_P is true, we just need
3945 to create an address from it, otherwise we want to get it into
3946 register. A set of invariants we depend on is stored in
3947 DEPENDS_ON. AT is the statement at that the value is computed.
3948 If CAN_AUTOINC is nonnull, use it to record whether autoinc
3949 addressing is likely. */
3952 get_computation_cost_at (struct ivopts_data
*data
,
3953 struct iv_use
*use
, struct iv_cand
*cand
,
3954 bool address_p
, bitmap
*depends_on
, gimple at
,
3958 tree ubase
= use
->iv
->base
, ustep
= use
->iv
->step
;
3960 tree utype
= TREE_TYPE (ubase
), ctype
;
3961 unsigned HOST_WIDE_INT cstepi
, offset
= 0;
3962 HOST_WIDE_INT ratio
, aratio
;
3963 bool var_present
, symbol_present
, stmt_is_after_inc
;
3966 bool speed
= optimize_bb_for_speed_p (gimple_bb (at
));
3967 enum machine_mode mem_mode
= (address_p
3968 ? TYPE_MODE (TREE_TYPE (*use
->op_p
))
3973 /* Only consider real candidates. */
3975 return infinite_cost
;
3977 cbase
= cand
->iv
->base
;
3978 cstep
= cand
->iv
->step
;
3979 ctype
= TREE_TYPE (cbase
);
3981 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
3983 /* We do not have a precision to express the values of use. */
3984 return infinite_cost
;
3988 || (use
->iv
->base_object
3989 && cand
->iv
->base_object
3990 && POINTER_TYPE_P (TREE_TYPE (use
->iv
->base_object
))
3991 && POINTER_TYPE_P (TREE_TYPE (cand
->iv
->base_object
))))
3993 /* Do not try to express address of an object with computation based
3994 on address of a different object. This may cause problems in rtl
3995 level alias analysis (that does not expect this to be happening,
3996 as this is illegal in C), and would be unlikely to be useful
3998 if (use
->iv
->base_object
3999 && cand
->iv
->base_object
4000 && !operand_equal_p (use
->iv
->base_object
, cand
->iv
->base_object
, 0))
4001 return infinite_cost
;
4004 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
4006 /* TODO -- add direct handling of this case. */
4010 /* CSTEPI is removed from the offset in case statement is after the
4011 increment. If the step is not constant, we use zero instead.
4012 This is a bit imprecise (there is the extra addition), but
4013 redundancy elimination is likely to transform the code so that
4014 it uses value of the variable before increment anyway,
4015 so it is not that much unrealistic. */
4016 if (cst_and_fits_in_hwi (cstep
))
4017 cstepi
= int_cst_value (cstep
);
4021 if (!constant_multiple_of (ustep
, cstep
, &rat
))
4022 return infinite_cost
;
4024 if (rat
.fits_shwi ())
4025 ratio
= rat
.to_shwi ();
4027 return infinite_cost
;
4030 ctype
= TREE_TYPE (cbase
);
4032 stmt_is_after_inc
= stmt_after_increment (data
->current_loop
, cand
, at
);
4034 /* use = ubase + ratio * (var - cbase). If either cbase is a constant
4035 or ratio == 1, it is better to handle this like
4037 ubase - ratio * cbase + ratio * var
4039 (also holds in the case ratio == -1, TODO. */
4041 if (cst_and_fits_in_hwi (cbase
))
4043 offset
= - ratio
* int_cst_value (cbase
);
4044 cost
= difference_cost (data
,
4045 ubase
, build_int_cst (utype
, 0),
4046 &symbol_present
, &var_present
, &offset
,
4048 cost
.cost
/= avg_loop_niter (data
->current_loop
);
4050 else if (ratio
== 1)
4052 tree real_cbase
= cbase
;
4054 /* Check to see if any adjustment is needed. */
4055 if (cstepi
== 0 && stmt_is_after_inc
)
4057 aff_tree real_cbase_aff
;
4060 tree_to_aff_combination (cbase
, TREE_TYPE (real_cbase
),
4062 tree_to_aff_combination (cstep
, TREE_TYPE (cstep
), &cstep_aff
);
4064 aff_combination_add (&real_cbase_aff
, &cstep_aff
);
4065 real_cbase
= aff_combination_to_tree (&real_cbase_aff
);
4068 cost
= difference_cost (data
,
4070 &symbol_present
, &var_present
, &offset
,
4072 cost
.cost
/= avg_loop_niter (data
->current_loop
);
4075 && !POINTER_TYPE_P (ctype
)
4076 && multiplier_allowed_in_address_p
4078 TYPE_ADDR_SPACE (TREE_TYPE (utype
))))
4081 = fold_build2 (MULT_EXPR
, ctype
, cbase
, build_int_cst (ctype
, ratio
));
4082 cost
= difference_cost (data
,
4084 &symbol_present
, &var_present
, &offset
,
4086 cost
.cost
/= avg_loop_niter (data
->current_loop
);
4090 cost
= force_var_cost (data
, cbase
, depends_on
);
4091 cost
= add_costs (cost
,
4092 difference_cost (data
,
4093 ubase
, build_int_cst (utype
, 0),
4094 &symbol_present
, &var_present
,
4095 &offset
, depends_on
));
4096 cost
.cost
/= avg_loop_niter (data
->current_loop
);
4097 cost
.cost
+= add_cost (data
->speed
, TYPE_MODE (ctype
));
4103 get_loop_invariant_expr_id (data
, ubase
, cbase
, ratio
, address_p
);
4104 /* Clear depends on. */
4105 if (*inv_expr_id
!= -1 && depends_on
&& *depends_on
)
4106 bitmap_clear (*depends_on
);
4109 /* If we are after the increment, the value of the candidate is higher by
4111 if (stmt_is_after_inc
)
4112 offset
-= ratio
* cstepi
;
4114 /* Now the computation is in shape symbol + var1 + const + ratio * var2.
4115 (symbol/var1/const parts may be omitted). If we are looking for an
4116 address, find the cost of addressing this. */
4118 return add_costs (cost
,
4119 get_address_cost (symbol_present
, var_present
,
4120 offset
, ratio
, cstepi
,
4122 TYPE_ADDR_SPACE (TREE_TYPE (utype
)),
4123 speed
, stmt_is_after_inc
,
4126 /* Otherwise estimate the costs for computing the expression. */
4127 if (!symbol_present
&& !var_present
&& !offset
)
4130 cost
.cost
+= mult_by_coeff_cost (ratio
, TYPE_MODE (ctype
), speed
);
4134 /* Symbol + offset should be compile-time computable so consider that they
4135 are added once to the variable, if present. */
4136 if (var_present
&& (symbol_present
|| offset
))
4137 cost
.cost
+= adjust_setup_cost (data
,
4138 add_cost (speed
, TYPE_MODE (ctype
)));
4140 /* Having offset does not affect runtime cost in case it is added to
4141 symbol, but it increases complexity. */
4145 cost
.cost
+= add_cost (speed
, TYPE_MODE (ctype
));
4147 aratio
= ratio
> 0 ? ratio
: -ratio
;
4149 cost
.cost
+= mult_by_coeff_cost (aratio
, TYPE_MODE (ctype
), speed
);
4154 *can_autoinc
= false;
4157 /* Just get the expression, expand it and measure the cost. */
4158 tree comp
= get_computation_at (data
->current_loop
, use
, cand
, at
);
4161 return infinite_cost
;
4164 comp
= build_simple_mem_ref (comp
);
4166 return new_cost (computation_cost (comp
, speed
), 0);
4170 /* Determines the cost of the computation by that USE is expressed
4171 from induction variable CAND. If ADDRESS_P is true, we just need
4172 to create an address from it, otherwise we want to get it into
4173 register. A set of invariants we depend on is stored in
4174 DEPENDS_ON. If CAN_AUTOINC is nonnull, use it to record whether
4175 autoinc addressing is likely. */
4178 get_computation_cost (struct ivopts_data
*data
,
4179 struct iv_use
*use
, struct iv_cand
*cand
,
4180 bool address_p
, bitmap
*depends_on
,
4181 bool *can_autoinc
, int *inv_expr_id
)
4183 return get_computation_cost_at (data
,
4184 use
, cand
, address_p
, depends_on
, use
->stmt
,
4185 can_autoinc
, inv_expr_id
);
4188 /* Determines cost of basing replacement of USE on CAND in a generic
4192 determine_use_iv_cost_generic (struct ivopts_data
*data
,
4193 struct iv_use
*use
, struct iv_cand
*cand
)
4197 int inv_expr_id
= -1;
4199 /* The simple case first -- if we need to express value of the preserved
4200 original biv, the cost is 0. This also prevents us from counting the
4201 cost of increment twice -- once at this use and once in the cost of
4203 if (cand
->pos
== IP_ORIGINAL
4204 && cand
->incremented_at
== use
->stmt
)
4206 set_use_iv_cost (data
, use
, cand
, no_cost
, NULL
, NULL_TREE
,
4211 cost
= get_computation_cost (data
, use
, cand
, false, &depends_on
,
4212 NULL
, &inv_expr_id
);
4214 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
, ERROR_MARK
,
4217 return !infinite_cost_p (cost
);
4220 /* Determines cost of basing replacement of USE on CAND in an address. */
4223 determine_use_iv_cost_address (struct ivopts_data
*data
,
4224 struct iv_use
*use
, struct iv_cand
*cand
)
4228 int inv_expr_id
= -1;
4229 comp_cost cost
= get_computation_cost (data
, use
, cand
, true, &depends_on
,
4230 &can_autoinc
, &inv_expr_id
);
4232 if (cand
->ainc_use
== use
)
4235 cost
.cost
-= cand
->cost_step
;
4236 /* If we generated the candidate solely for exploiting autoincrement
4237 opportunities, and it turns out it can't be used, set the cost to
4238 infinity to make sure we ignore it. */
4239 else if (cand
->pos
== IP_AFTER_USE
|| cand
->pos
== IP_BEFORE_USE
)
4240 cost
= infinite_cost
;
4242 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
, ERROR_MARK
,
4245 return !infinite_cost_p (cost
);
4248 /* Computes value of candidate CAND at position AT in iteration NITER, and
4249 stores it to VAL. */
4252 cand_value_at (struct loop
*loop
, struct iv_cand
*cand
, gimple at
, tree niter
,
4255 aff_tree step
, delta
, nit
;
4256 struct iv
*iv
= cand
->iv
;
4257 tree type
= TREE_TYPE (iv
->base
);
4258 tree steptype
= type
;
4259 if (POINTER_TYPE_P (type
))
4260 steptype
= sizetype
;
4262 tree_to_aff_combination (iv
->step
, steptype
, &step
);
4263 tree_to_aff_combination (niter
, TREE_TYPE (niter
), &nit
);
4264 aff_combination_convert (&nit
, steptype
);
4265 aff_combination_mult (&nit
, &step
, &delta
);
4266 if (stmt_after_increment (loop
, cand
, at
))
4267 aff_combination_add (&delta
, &step
);
4269 tree_to_aff_combination (iv
->base
, type
, val
);
4270 aff_combination_add (val
, &delta
);
4273 /* Returns period of induction variable iv. */
4276 iv_period (struct iv
*iv
)
4278 tree step
= iv
->step
, period
, type
;
4281 gcc_assert (step
&& TREE_CODE (step
) == INTEGER_CST
);
4283 type
= unsigned_type_for (TREE_TYPE (step
));
4284 /* Period of the iv is lcm (step, type_range)/step -1,
4285 i.e., N*type_range/step - 1. Since type range is power
4286 of two, N == (step >> num_of_ending_zeros_binary (step),
4287 so the final result is
4289 (type_range >> num_of_ending_zeros_binary (step)) - 1
4292 pow2div
= num_ending_zeros (step
);
4294 period
= build_low_bits_mask (type
,
4295 (TYPE_PRECISION (type
)
4296 - tree_low_cst (pow2div
, 1)));
4301 /* Returns the comparison operator used when eliminating the iv USE. */
4303 static enum tree_code
4304 iv_elimination_compare (struct ivopts_data
*data
, struct iv_use
*use
)
4306 struct loop
*loop
= data
->current_loop
;
4310 ex_bb
= gimple_bb (use
->stmt
);
4311 exit
= EDGE_SUCC (ex_bb
, 0);
4312 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
4313 exit
= EDGE_SUCC (ex_bb
, 1);
4315 return (exit
->flags
& EDGE_TRUE_VALUE
? EQ_EXPR
: NE_EXPR
);
4319 strip_wrap_conserving_type_conversions (tree exp
)
4321 while (tree_ssa_useless_type_conversion (exp
)
4322 && (nowrap_type_p (TREE_TYPE (exp
))
4323 == nowrap_type_p (TREE_TYPE (TREE_OPERAND (exp
, 0)))))
4324 exp
= TREE_OPERAND (exp
, 0);
4328 /* Walk the SSA form and check whether E == WHAT. Fairly simplistic, we
4329 check for an exact match. */
4332 expr_equal_p (tree e
, tree what
)
4335 enum tree_code code
;
4337 e
= strip_wrap_conserving_type_conversions (e
);
4338 what
= strip_wrap_conserving_type_conversions (what
);
4340 code
= TREE_CODE (what
);
4341 if (TREE_TYPE (e
) != TREE_TYPE (what
))
4344 if (operand_equal_p (e
, what
, 0))
4347 if (TREE_CODE (e
) != SSA_NAME
)
4350 stmt
= SSA_NAME_DEF_STMT (e
);
4351 if (gimple_code (stmt
) != GIMPLE_ASSIGN
4352 || gimple_assign_rhs_code (stmt
) != code
)
4355 switch (get_gimple_rhs_class (code
))
4357 case GIMPLE_BINARY_RHS
:
4358 if (!expr_equal_p (gimple_assign_rhs2 (stmt
), TREE_OPERAND (what
, 1)))
4362 case GIMPLE_UNARY_RHS
:
4363 case GIMPLE_SINGLE_RHS
:
4364 return expr_equal_p (gimple_assign_rhs1 (stmt
), TREE_OPERAND (what
, 0));
4370 /* Returns true if we can prove that BASE - OFFSET does not overflow. For now,
4371 we only detect the situation that BASE = SOMETHING + OFFSET, where the
4372 calculation is performed in non-wrapping type.
4374 TODO: More generally, we could test for the situation that
4375 BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero.
4376 This would require knowing the sign of OFFSET.
4378 Also, we only look for the first addition in the computation of BASE.
4379 More complex analysis would be better, but introducing it just for
4380 this optimization seems like an overkill. */
4383 difference_cannot_overflow_p (tree base
, tree offset
)
4385 enum tree_code code
;
4388 if (!nowrap_type_p (TREE_TYPE (base
)))
4391 base
= expand_simple_operations (base
);
4393 if (TREE_CODE (base
) == SSA_NAME
)
4395 gimple stmt
= SSA_NAME_DEF_STMT (base
);
4397 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
4400 code
= gimple_assign_rhs_code (stmt
);
4401 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
4404 e1
= gimple_assign_rhs1 (stmt
);
4405 e2
= gimple_assign_rhs2 (stmt
);
4409 code
= TREE_CODE (base
);
4410 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
4412 e1
= TREE_OPERAND (base
, 0);
4413 e2
= TREE_OPERAND (base
, 1);
4416 /* TODO: deeper inspection may be necessary to prove the equality. */
4420 return expr_equal_p (e1
, offset
) || expr_equal_p (e2
, offset
);
4421 case POINTER_PLUS_EXPR
:
4422 return expr_equal_p (e2
, offset
);
4429 /* Tries to replace loop exit by one formulated in terms of a LT_EXPR
4430 comparison with CAND. NITER describes the number of iterations of
4431 the loops. If successful, the comparison in COMP_P is altered accordingly.
4433 We aim to handle the following situation:
4449 Here, the number of iterations of the loop is (a + 1 > b) ? 0 : b - a - 1.
4450 We aim to optimize this to
4458 while (p < p_0 - a + b);
4460 This preserves the correctness, since the pointer arithmetics does not
4461 overflow. More precisely:
4463 1) if a + 1 <= b, then p_0 - a + b is the final value of p, hence there is no
4464 overflow in computing it or the values of p.
4465 2) if a + 1 > b, then we need to verify that the expression p_0 - a does not
4466 overflow. To prove this, we use the fact that p_0 = base + a. */
4469 iv_elimination_compare_lt (struct ivopts_data
*data
,
4470 struct iv_cand
*cand
, enum tree_code
*comp_p
,
4471 struct tree_niter_desc
*niter
)
4473 tree cand_type
, a
, b
, mbz
, nit_type
= TREE_TYPE (niter
->niter
), offset
;
4474 struct affine_tree_combination nit
, tmpa
, tmpb
;
4475 enum tree_code comp
;
4478 /* We need to know that the candidate induction variable does not overflow.
4479 While more complex analysis may be used to prove this, for now just
4480 check that the variable appears in the original program and that it
4481 is computed in a type that guarantees no overflows. */
4482 cand_type
= TREE_TYPE (cand
->iv
->base
);
4483 if (cand
->pos
!= IP_ORIGINAL
|| !nowrap_type_p (cand_type
))
4486 /* Make sure that the loop iterates till the loop bound is hit, as otherwise
4487 the calculation of the BOUND could overflow, making the comparison
4489 if (!data
->loop_single_exit_p
)
4492 /* We need to be able to decide whether candidate is increasing or decreasing
4493 in order to choose the right comparison operator. */
4494 if (!cst_and_fits_in_hwi (cand
->iv
->step
))
4496 step
= int_cst_value (cand
->iv
->step
);
4498 /* Check that the number of iterations matches the expected pattern:
4499 a + 1 > b ? 0 : b - a - 1. */
4500 mbz
= niter
->may_be_zero
;
4501 if (TREE_CODE (mbz
) == GT_EXPR
)
4503 /* Handle a + 1 > b. */
4504 tree op0
= TREE_OPERAND (mbz
, 0);
4505 if (TREE_CODE (op0
) == PLUS_EXPR
&& integer_onep (TREE_OPERAND (op0
, 1)))
4507 a
= TREE_OPERAND (op0
, 0);
4508 b
= TREE_OPERAND (mbz
, 1);
4513 else if (TREE_CODE (mbz
) == LT_EXPR
)
4515 tree op1
= TREE_OPERAND (mbz
, 1);
4517 /* Handle b < a + 1. */
4518 if (TREE_CODE (op1
) == PLUS_EXPR
&& integer_onep (TREE_OPERAND (op1
, 1)))
4520 a
= TREE_OPERAND (op1
, 0);
4521 b
= TREE_OPERAND (mbz
, 0);
4529 /* Expected number of iterations is B - A - 1. Check that it matches
4530 the actual number, i.e., that B - A - NITER = 1. */
4531 tree_to_aff_combination (niter
->niter
, nit_type
, &nit
);
4532 tree_to_aff_combination (fold_convert (nit_type
, a
), nit_type
, &tmpa
);
4533 tree_to_aff_combination (fold_convert (nit_type
, b
), nit_type
, &tmpb
);
4534 aff_combination_scale (&nit
, double_int_minus_one
);
4535 aff_combination_scale (&tmpa
, double_int_minus_one
);
4536 aff_combination_add (&tmpb
, &tmpa
);
4537 aff_combination_add (&tmpb
, &nit
);
4538 if (tmpb
.n
!= 0 || tmpb
.offset
!= double_int_one
)
4541 /* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not
4543 offset
= fold_build2 (MULT_EXPR
, TREE_TYPE (cand
->iv
->step
),
4545 fold_convert (TREE_TYPE (cand
->iv
->step
), a
));
4546 if (!difference_cannot_overflow_p (cand
->iv
->base
, offset
))
4549 /* Determine the new comparison operator. */
4550 comp
= step
< 0 ? GT_EXPR
: LT_EXPR
;
4551 if (*comp_p
== NE_EXPR
)
4553 else if (*comp_p
== EQ_EXPR
)
4554 *comp_p
= invert_tree_comparison (comp
, false);
4561 /* Check whether it is possible to express the condition in USE by comparison
4562 of candidate CAND. If so, store the value compared with to BOUND, and the
4563 comparison operator to COMP. */
4566 may_eliminate_iv (struct ivopts_data
*data
,
4567 struct iv_use
*use
, struct iv_cand
*cand
, tree
*bound
,
4568 enum tree_code
*comp
)
4573 struct loop
*loop
= data
->current_loop
;
4575 struct tree_niter_desc
*desc
= NULL
;
4577 if (TREE_CODE (cand
->iv
->step
) != INTEGER_CST
)
4580 /* For now works only for exits that dominate the loop latch.
4581 TODO: extend to other conditions inside loop body. */
4582 ex_bb
= gimple_bb (use
->stmt
);
4583 if (use
->stmt
!= last_stmt (ex_bb
)
4584 || gimple_code (use
->stmt
) != GIMPLE_COND
4585 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, ex_bb
))
4588 exit
= EDGE_SUCC (ex_bb
, 0);
4589 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
4590 exit
= EDGE_SUCC (ex_bb
, 1);
4591 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
4594 desc
= niter_for_exit (data
, exit
);
4598 /* Determine whether we can use the variable to test the exit condition.
4599 This is the case iff the period of the induction variable is greater
4600 than the number of iterations for which the exit condition is true. */
4601 period
= iv_period (cand
->iv
);
4603 /* If the number of iterations is constant, compare against it directly. */
4604 if (TREE_CODE (desc
->niter
) == INTEGER_CST
)
4606 /* See cand_value_at. */
4607 if (stmt_after_increment (loop
, cand
, use
->stmt
))
4609 if (!tree_int_cst_lt (desc
->niter
, period
))
4614 if (tree_int_cst_lt (period
, desc
->niter
))
4619 /* If not, and if this is the only possible exit of the loop, see whether
4620 we can get a conservative estimate on the number of iterations of the
4621 entire loop and compare against that instead. */
4624 double_int period_value
, max_niter
;
4626 max_niter
= desc
->max
;
4627 if (stmt_after_increment (loop
, cand
, use
->stmt
))
4628 max_niter
+= double_int_one
;
4629 period_value
= tree_to_double_int (period
);
4630 if (max_niter
.ugt (period_value
))
4632 /* See if we can take advantage of inferred loop bound information. */
4633 if (data
->loop_single_exit_p
)
4635 if (!max_loop_iterations (loop
, &max_niter
))
4637 /* The loop bound is already adjusted by adding 1. */
4638 if (max_niter
.ugt (period_value
))
4646 cand_value_at (loop
, cand
, use
->stmt
, desc
->niter
, &bnd
);
4648 *bound
= aff_combination_to_tree (&bnd
);
4649 *comp
= iv_elimination_compare (data
, use
);
4651 /* It is unlikely that computing the number of iterations using division
4652 would be more profitable than keeping the original induction variable. */
4653 if (expression_expensive_p (*bound
))
4656 /* Sometimes, it is possible to handle the situation that the number of
4657 iterations may be zero unless additional assumtions by using <
4658 instead of != in the exit condition.
4660 TODO: we could also calculate the value MAY_BE_ZERO ? 0 : NITER and
4661 base the exit condition on it. However, that is often too
4663 if (!integer_zerop (desc
->may_be_zero
))
4664 return iv_elimination_compare_lt (data
, cand
, comp
, desc
);
4669 /* Calculates the cost of BOUND, if it is a PARM_DECL. A PARM_DECL must
4670 be copied, if is is used in the loop body and DATA->body_includes_call. */
4673 parm_decl_cost (struct ivopts_data
*data
, tree bound
)
4675 tree sbound
= bound
;
4676 STRIP_NOPS (sbound
);
4678 if (TREE_CODE (sbound
) == SSA_NAME
4679 && SSA_NAME_IS_DEFAULT_DEF (sbound
)
4680 && TREE_CODE (SSA_NAME_VAR (sbound
)) == PARM_DECL
4681 && data
->body_includes_call
)
4682 return COSTS_N_INSNS (1);
4687 /* Determines cost of basing replacement of USE on CAND in a condition. */
4690 determine_use_iv_cost_condition (struct ivopts_data
*data
,
4691 struct iv_use
*use
, struct iv_cand
*cand
)
4693 tree bound
= NULL_TREE
;
4695 bitmap depends_on_elim
= NULL
, depends_on_express
= NULL
, depends_on
;
4696 comp_cost elim_cost
, express_cost
, cost
, bound_cost
;
4698 int elim_inv_expr_id
= -1, express_inv_expr_id
= -1, inv_expr_id
;
4699 tree
*control_var
, *bound_cst
;
4700 enum tree_code comp
= ERROR_MARK
;
4702 /* Only consider real candidates. */
4705 set_use_iv_cost (data
, use
, cand
, infinite_cost
, NULL
, NULL_TREE
,
4710 /* Try iv elimination. */
4711 if (may_eliminate_iv (data
, use
, cand
, &bound
, &comp
))
4713 elim_cost
= force_var_cost (data
, bound
, &depends_on_elim
);
4714 if (elim_cost
.cost
== 0)
4715 elim_cost
.cost
= parm_decl_cost (data
, bound
);
4716 else if (TREE_CODE (bound
) == INTEGER_CST
)
4718 /* If we replace a loop condition 'i < n' with 'p < base + n',
4719 depends_on_elim will have 'base' and 'n' set, which implies
4720 that both 'base' and 'n' will be live during the loop. More likely,
4721 'base + n' will be loop invariant, resulting in only one live value
4722 during the loop. So in that case we clear depends_on_elim and set
4723 elim_inv_expr_id instead. */
4724 if (depends_on_elim
&& bitmap_count_bits (depends_on_elim
) > 1)
4726 elim_inv_expr_id
= get_expr_id (data
, bound
);
4727 bitmap_clear (depends_on_elim
);
4729 /* The bound is a loop invariant, so it will be only computed
4731 elim_cost
.cost
= adjust_setup_cost (data
, elim_cost
.cost
);
4734 elim_cost
= infinite_cost
;
4736 /* Try expressing the original giv. If it is compared with an invariant,
4737 note that we cannot get rid of it. */
4738 ok
= extract_cond_operands (data
, use
->stmt
, &control_var
, &bound_cst
,
4742 /* When the condition is a comparison of the candidate IV against
4743 zero, prefer this IV.
4745 TODO: The constant that we're subtracting from the cost should
4746 be target-dependent. This information should be added to the
4747 target costs for each backend. */
4748 if (!infinite_cost_p (elim_cost
) /* Do not try to decrease infinite! */
4749 && integer_zerop (*bound_cst
)
4750 && (operand_equal_p (*control_var
, cand
->var_after
, 0)
4751 || operand_equal_p (*control_var
, cand
->var_before
, 0)))
4752 elim_cost
.cost
-= 1;
4754 express_cost
= get_computation_cost (data
, use
, cand
, false,
4755 &depends_on_express
, NULL
,
4756 &express_inv_expr_id
);
4757 fd_ivopts_data
= data
;
4758 walk_tree (&cmp_iv
->base
, find_depends
, &depends_on_express
, NULL
);
4760 /* Count the cost of the original bound as well. */
4761 bound_cost
= force_var_cost (data
, *bound_cst
, NULL
);
4762 if (bound_cost
.cost
== 0)
4763 bound_cost
.cost
= parm_decl_cost (data
, *bound_cst
);
4764 else if (TREE_CODE (*bound_cst
) == INTEGER_CST
)
4765 bound_cost
.cost
= 0;
4766 express_cost
.cost
+= bound_cost
.cost
;
4768 /* Choose the better approach, preferring the eliminated IV. */
4769 if (compare_costs (elim_cost
, express_cost
) <= 0)
4772 depends_on
= depends_on_elim
;
4773 depends_on_elim
= NULL
;
4774 inv_expr_id
= elim_inv_expr_id
;
4778 cost
= express_cost
;
4779 depends_on
= depends_on_express
;
4780 depends_on_express
= NULL
;
4783 inv_expr_id
= express_inv_expr_id
;
4786 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, bound
, comp
, inv_expr_id
);
4788 if (depends_on_elim
)
4789 BITMAP_FREE (depends_on_elim
);
4790 if (depends_on_express
)
4791 BITMAP_FREE (depends_on_express
);
4793 return !infinite_cost_p (cost
);
4796 /* Determines cost of basing replacement of USE on CAND. Returns false
4797 if USE cannot be based on CAND. */
4800 determine_use_iv_cost (struct ivopts_data
*data
,
4801 struct iv_use
*use
, struct iv_cand
*cand
)
4805 case USE_NONLINEAR_EXPR
:
4806 return determine_use_iv_cost_generic (data
, use
, cand
);
4809 return determine_use_iv_cost_address (data
, use
, cand
);
4812 return determine_use_iv_cost_condition (data
, use
, cand
);
4819 /* Return true if get_computation_cost indicates that autoincrement is
4820 a possibility for the pair of USE and CAND, false otherwise. */
4823 autoinc_possible_for_pair (struct ivopts_data
*data
, struct iv_use
*use
,
4824 struct iv_cand
*cand
)
4830 if (use
->type
!= USE_ADDRESS
)
4833 cost
= get_computation_cost (data
, use
, cand
, true, &depends_on
,
4834 &can_autoinc
, NULL
);
4836 BITMAP_FREE (depends_on
);
4838 return !infinite_cost_p (cost
) && can_autoinc
;
4841 /* Examine IP_ORIGINAL candidates to see if they are incremented next to a
4842 use that allows autoincrement, and set their AINC_USE if possible. */
4845 set_autoinc_for_original_candidates (struct ivopts_data
*data
)
4849 for (i
= 0; i
< n_iv_cands (data
); i
++)
4851 struct iv_cand
*cand
= iv_cand (data
, i
);
4852 struct iv_use
*closest_before
= NULL
;
4853 struct iv_use
*closest_after
= NULL
;
4854 if (cand
->pos
!= IP_ORIGINAL
)
4857 for (j
= 0; j
< n_iv_uses (data
); j
++)
4859 struct iv_use
*use
= iv_use (data
, j
);
4860 unsigned uid
= gimple_uid (use
->stmt
);
4862 if (gimple_bb (use
->stmt
) != gimple_bb (cand
->incremented_at
))
4865 if (uid
< gimple_uid (cand
->incremented_at
)
4866 && (closest_before
== NULL
4867 || uid
> gimple_uid (closest_before
->stmt
)))
4868 closest_before
= use
;
4870 if (uid
> gimple_uid (cand
->incremented_at
)
4871 && (closest_after
== NULL
4872 || uid
< gimple_uid (closest_after
->stmt
)))
4873 closest_after
= use
;
4876 if (closest_before
!= NULL
4877 && autoinc_possible_for_pair (data
, closest_before
, cand
))
4878 cand
->ainc_use
= closest_before
;
4879 else if (closest_after
!= NULL
4880 && autoinc_possible_for_pair (data
, closest_after
, cand
))
4881 cand
->ainc_use
= closest_after
;
4885 /* Finds the candidates for the induction variables. */
4888 find_iv_candidates (struct ivopts_data
*data
)
4890 /* Add commonly used ivs. */
4891 add_standard_iv_candidates (data
);
4893 /* Add old induction variables. */
4894 add_old_ivs_candidates (data
);
4896 /* Add induction variables derived from uses. */
4897 add_derived_ivs_candidates (data
);
4899 set_autoinc_for_original_candidates (data
);
4901 /* Record the important candidates. */
4902 record_important_candidates (data
);
4905 /* Determines costs of basing the use of the iv on an iv candidate. */
4908 determine_use_iv_costs (struct ivopts_data
*data
)
4912 struct iv_cand
*cand
;
4913 bitmap to_clear
= BITMAP_ALLOC (NULL
);
4915 alloc_use_cost_map (data
);
4917 for (i
= 0; i
< n_iv_uses (data
); i
++)
4919 use
= iv_use (data
, i
);
4921 if (data
->consider_all_candidates
)
4923 for (j
= 0; j
< n_iv_cands (data
); j
++)
4925 cand
= iv_cand (data
, j
);
4926 determine_use_iv_cost (data
, use
, cand
);
4933 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, j
, bi
)
4935 cand
= iv_cand (data
, j
);
4936 if (!determine_use_iv_cost (data
, use
, cand
))
4937 bitmap_set_bit (to_clear
, j
);
4940 /* Remove the candidates for that the cost is infinite from
4941 the list of related candidates. */
4942 bitmap_and_compl_into (use
->related_cands
, to_clear
);
4943 bitmap_clear (to_clear
);
4947 BITMAP_FREE (to_clear
);
4949 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4951 fprintf (dump_file
, "Use-candidate costs:\n");
4953 for (i
= 0; i
< n_iv_uses (data
); i
++)
4955 use
= iv_use (data
, i
);
4957 fprintf (dump_file
, "Use %d:\n", i
);
4958 fprintf (dump_file
, " cand\tcost\tcompl.\tdepends on\n");
4959 for (j
= 0; j
< use
->n_map_members
; j
++)
4961 if (!use
->cost_map
[j
].cand
4962 || infinite_cost_p (use
->cost_map
[j
].cost
))
4965 fprintf (dump_file
, " %d\t%d\t%d\t",
4966 use
->cost_map
[j
].cand
->id
,
4967 use
->cost_map
[j
].cost
.cost
,
4968 use
->cost_map
[j
].cost
.complexity
);
4969 if (use
->cost_map
[j
].depends_on
)
4970 bitmap_print (dump_file
,
4971 use
->cost_map
[j
].depends_on
, "","");
4972 if (use
->cost_map
[j
].inv_expr_id
!= -1)
4973 fprintf (dump_file
, " inv_expr:%d", use
->cost_map
[j
].inv_expr_id
);
4974 fprintf (dump_file
, "\n");
4977 fprintf (dump_file
, "\n");
4979 fprintf (dump_file
, "\n");
4983 /* Determines cost of the candidate CAND. */
4986 determine_iv_cost (struct ivopts_data
*data
, struct iv_cand
*cand
)
4988 comp_cost cost_base
;
4989 unsigned cost
, cost_step
;
4998 /* There are two costs associated with the candidate -- its increment
4999 and its initialization. The second is almost negligible for any loop
5000 that rolls enough, so we take it just very little into account. */
5002 base
= cand
->iv
->base
;
5003 cost_base
= force_var_cost (data
, base
, NULL
);
5004 /* It will be exceptional that the iv register happens to be initialized with
5005 the proper value at no cost. In general, there will at least be a regcopy
5007 if (cost_base
.cost
== 0)
5008 cost_base
.cost
= COSTS_N_INSNS (1);
5009 cost_step
= add_cost (data
->speed
, TYPE_MODE (TREE_TYPE (base
)));
5011 cost
= cost_step
+ adjust_setup_cost (data
, cost_base
.cost
);
5013 /* Prefer the original ivs unless we may gain something by replacing it.
5014 The reason is to make debugging simpler; so this is not relevant for
5015 artificial ivs created by other optimization passes. */
5016 if (cand
->pos
!= IP_ORIGINAL
5017 || !SSA_NAME_VAR (cand
->var_before
)
5018 || DECL_ARTIFICIAL (SSA_NAME_VAR (cand
->var_before
)))
5021 /* Prefer not to insert statements into latch unless there are some
5022 already (so that we do not create unnecessary jumps). */
5023 if (cand
->pos
== IP_END
5024 && empty_block_p (ip_end_pos (data
->current_loop
)))
5028 cand
->cost_step
= cost_step
;
5031 /* Determines costs of computation of the candidates. */
5034 determine_iv_costs (struct ivopts_data
*data
)
5038 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5040 fprintf (dump_file
, "Candidate costs:\n");
5041 fprintf (dump_file
, " cand\tcost\n");
5044 for (i
= 0; i
< n_iv_cands (data
); i
++)
5046 struct iv_cand
*cand
= iv_cand (data
, i
);
5048 determine_iv_cost (data
, cand
);
5050 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5051 fprintf (dump_file
, " %d\t%d\n", i
, cand
->cost
);
5054 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5055 fprintf (dump_file
, "\n");
5058 /* Calculates cost for having SIZE induction variables. */
5061 ivopts_global_cost_for_size (struct ivopts_data
*data
, unsigned size
)
5063 /* We add size to the cost, so that we prefer eliminating ivs
5065 return size
+ estimate_reg_pressure_cost (size
, data
->regs_used
, data
->speed
,
5066 data
->body_includes_call
);
5069 /* For each size of the induction variable set determine the penalty. */
5072 determine_set_costs (struct ivopts_data
*data
)
5076 gimple_stmt_iterator psi
;
5078 struct loop
*loop
= data
->current_loop
;
5081 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5083 fprintf (dump_file
, "Global costs:\n");
5084 fprintf (dump_file
, " target_avail_regs %d\n", target_avail_regs
);
5085 fprintf (dump_file
, " target_clobbered_regs %d\n", target_clobbered_regs
);
5086 fprintf (dump_file
, " target_reg_cost %d\n", target_reg_cost
[data
->speed
]);
5087 fprintf (dump_file
, " target_spill_cost %d\n", target_spill_cost
[data
->speed
]);
5091 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
5093 phi
= gsi_stmt (psi
);
5094 op
= PHI_RESULT (phi
);
5096 if (virtual_operand_p (op
))
5099 if (get_iv (data
, op
))
5105 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
5107 struct version_info
*info
= ver_info (data
, j
);
5109 if (info
->inv_id
&& info
->has_nonlin_use
)
5113 data
->regs_used
= n
;
5114 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5115 fprintf (dump_file
, " regs_used %d\n", n
);
5117 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5119 fprintf (dump_file
, " cost for size:\n");
5120 fprintf (dump_file
, " ivs\tcost\n");
5121 for (j
= 0; j
<= 2 * target_avail_regs
; j
++)
5122 fprintf (dump_file
, " %d\t%d\n", j
,
5123 ivopts_global_cost_for_size (data
, j
));
5124 fprintf (dump_file
, "\n");
5128 /* Returns true if A is a cheaper cost pair than B. */
5131 cheaper_cost_pair (struct cost_pair
*a
, struct cost_pair
*b
)
5141 cmp
= compare_costs (a
->cost
, b
->cost
);
5148 /* In case the costs are the same, prefer the cheaper candidate. */
5149 if (a
->cand
->cost
< b
->cand
->cost
)
5156 /* Returns candidate by that USE is expressed in IVS. */
5158 static struct cost_pair
*
5159 iv_ca_cand_for_use (struct iv_ca
*ivs
, struct iv_use
*use
)
5161 return ivs
->cand_for_use
[use
->id
];
5164 /* Computes the cost field of IVS structure. */
5167 iv_ca_recount_cost (struct ivopts_data
*data
, struct iv_ca
*ivs
)
5169 comp_cost cost
= ivs
->cand_use_cost
;
5171 cost
.cost
+= ivs
->cand_cost
;
5173 cost
.cost
+= ivopts_global_cost_for_size (data
,
5174 ivs
->n_regs
+ ivs
->num_used_inv_expr
);
5179 /* Remove invariants in set INVS to set IVS. */
5182 iv_ca_set_remove_invariants (struct iv_ca
*ivs
, bitmap invs
)
5190 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
5192 ivs
->n_invariant_uses
[iid
]--;
5193 if (ivs
->n_invariant_uses
[iid
] == 0)
5198 /* Set USE not to be expressed by any candidate in IVS. */
5201 iv_ca_set_no_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5204 unsigned uid
= use
->id
, cid
;
5205 struct cost_pair
*cp
;
5207 cp
= ivs
->cand_for_use
[uid
];
5213 ivs
->cand_for_use
[uid
] = NULL
;
5214 ivs
->n_cand_uses
[cid
]--;
5216 if (ivs
->n_cand_uses
[cid
] == 0)
5218 bitmap_clear_bit (ivs
->cands
, cid
);
5219 /* Do not count the pseudocandidates. */
5223 ivs
->cand_cost
-= cp
->cand
->cost
;
5225 iv_ca_set_remove_invariants (ivs
, cp
->cand
->depends_on
);
5228 ivs
->cand_use_cost
= sub_costs (ivs
->cand_use_cost
, cp
->cost
);
5230 iv_ca_set_remove_invariants (ivs
, cp
->depends_on
);
5232 if (cp
->inv_expr_id
!= -1)
5234 ivs
->used_inv_expr
[cp
->inv_expr_id
]--;
5235 if (ivs
->used_inv_expr
[cp
->inv_expr_id
] == 0)
5236 ivs
->num_used_inv_expr
--;
5238 iv_ca_recount_cost (data
, ivs
);
5241 /* Add invariants in set INVS to set IVS. */
5244 iv_ca_set_add_invariants (struct iv_ca
*ivs
, bitmap invs
)
5252 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
5254 ivs
->n_invariant_uses
[iid
]++;
5255 if (ivs
->n_invariant_uses
[iid
] == 1)
5260 /* Set cost pair for USE in set IVS to CP. */
5263 iv_ca_set_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5264 struct iv_use
*use
, struct cost_pair
*cp
)
5266 unsigned uid
= use
->id
, cid
;
5268 if (ivs
->cand_for_use
[uid
] == cp
)
5271 if (ivs
->cand_for_use
[uid
])
5272 iv_ca_set_no_cp (data
, ivs
, use
);
5279 ivs
->cand_for_use
[uid
] = cp
;
5280 ivs
->n_cand_uses
[cid
]++;
5281 if (ivs
->n_cand_uses
[cid
] == 1)
5283 bitmap_set_bit (ivs
->cands
, cid
);
5284 /* Do not count the pseudocandidates. */
5288 ivs
->cand_cost
+= cp
->cand
->cost
;
5290 iv_ca_set_add_invariants (ivs
, cp
->cand
->depends_on
);
5293 ivs
->cand_use_cost
= add_costs (ivs
->cand_use_cost
, cp
->cost
);
5294 iv_ca_set_add_invariants (ivs
, cp
->depends_on
);
5296 if (cp
->inv_expr_id
!= -1)
5298 ivs
->used_inv_expr
[cp
->inv_expr_id
]++;
5299 if (ivs
->used_inv_expr
[cp
->inv_expr_id
] == 1)
5300 ivs
->num_used_inv_expr
++;
5302 iv_ca_recount_cost (data
, ivs
);
5306 /* Extend set IVS by expressing USE by some of the candidates in it
5307 if possible. All important candidates will be considered
5308 if IMPORTANT_CANDIDATES is true. */
5311 iv_ca_add_use (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5312 struct iv_use
*use
, bool important_candidates
)
5314 struct cost_pair
*best_cp
= NULL
, *cp
;
5319 gcc_assert (ivs
->upto
>= use
->id
);
5321 if (ivs
->upto
== use
->id
)
5327 cands
= (important_candidates
? data
->important_candidates
: ivs
->cands
);
5328 EXECUTE_IF_SET_IN_BITMAP (cands
, 0, i
, bi
)
5330 struct iv_cand
*cand
= iv_cand (data
, i
);
5332 cp
= get_use_iv_cost (data
, use
, cand
);
5334 if (cheaper_cost_pair (cp
, best_cp
))
5338 iv_ca_set_cp (data
, ivs
, use
, best_cp
);
5341 /* Get cost for assignment IVS. */
5344 iv_ca_cost (struct iv_ca
*ivs
)
5346 /* This was a conditional expression but it triggered a bug in
5349 return infinite_cost
;
5354 /* Returns true if all dependences of CP are among invariants in IVS. */
5357 iv_ca_has_deps (struct iv_ca
*ivs
, struct cost_pair
*cp
)
5362 if (!cp
->depends_on
)
5365 EXECUTE_IF_SET_IN_BITMAP (cp
->depends_on
, 0, i
, bi
)
5367 if (ivs
->n_invariant_uses
[i
] == 0)
5374 /* Creates change of expressing USE by NEW_CP instead of OLD_CP and chains
5375 it before NEXT_CHANGE. */
5377 static struct iv_ca_delta
*
5378 iv_ca_delta_add (struct iv_use
*use
, struct cost_pair
*old_cp
,
5379 struct cost_pair
*new_cp
, struct iv_ca_delta
*next_change
)
5381 struct iv_ca_delta
*change
= XNEW (struct iv_ca_delta
);
5384 change
->old_cp
= old_cp
;
5385 change
->new_cp
= new_cp
;
5386 change
->next_change
= next_change
;
5391 /* Joins two lists of changes L1 and L2. Destructive -- old lists
5394 static struct iv_ca_delta
*
5395 iv_ca_delta_join (struct iv_ca_delta
*l1
, struct iv_ca_delta
*l2
)
5397 struct iv_ca_delta
*last
;
5405 for (last
= l1
; last
->next_change
; last
= last
->next_change
)
5407 last
->next_change
= l2
;
5412 /* Reverse the list of changes DELTA, forming the inverse to it. */
5414 static struct iv_ca_delta
*
5415 iv_ca_delta_reverse (struct iv_ca_delta
*delta
)
5417 struct iv_ca_delta
*act
, *next
, *prev
= NULL
;
5418 struct cost_pair
*tmp
;
5420 for (act
= delta
; act
; act
= next
)
5422 next
= act
->next_change
;
5423 act
->next_change
= prev
;
5427 act
->old_cp
= act
->new_cp
;
5434 /* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
5435 reverted instead. */
5438 iv_ca_delta_commit (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5439 struct iv_ca_delta
*delta
, bool forward
)
5441 struct cost_pair
*from
, *to
;
5442 struct iv_ca_delta
*act
;
5445 delta
= iv_ca_delta_reverse (delta
);
5447 for (act
= delta
; act
; act
= act
->next_change
)
5451 gcc_assert (iv_ca_cand_for_use (ivs
, act
->use
) == from
);
5452 iv_ca_set_cp (data
, ivs
, act
->use
, to
);
5456 iv_ca_delta_reverse (delta
);
5459 /* Returns true if CAND is used in IVS. */
5462 iv_ca_cand_used_p (struct iv_ca
*ivs
, struct iv_cand
*cand
)
5464 return ivs
->n_cand_uses
[cand
->id
] > 0;
5467 /* Returns number of induction variable candidates in the set IVS. */
5470 iv_ca_n_cands (struct iv_ca
*ivs
)
5472 return ivs
->n_cands
;
5475 /* Free the list of changes DELTA. */
5478 iv_ca_delta_free (struct iv_ca_delta
**delta
)
5480 struct iv_ca_delta
*act
, *next
;
5482 for (act
= *delta
; act
; act
= next
)
5484 next
= act
->next_change
;
5491 /* Allocates new iv candidates assignment. */
5493 static struct iv_ca
*
5494 iv_ca_new (struct ivopts_data
*data
)
5496 struct iv_ca
*nw
= XNEW (struct iv_ca
);
5500 nw
->cand_for_use
= XCNEWVEC (struct cost_pair
*, n_iv_uses (data
));
5501 nw
->n_cand_uses
= XCNEWVEC (unsigned, n_iv_cands (data
));
5502 nw
->cands
= BITMAP_ALLOC (NULL
);
5505 nw
->cand_use_cost
= no_cost
;
5507 nw
->n_invariant_uses
= XCNEWVEC (unsigned, data
->max_inv_id
+ 1);
5509 nw
->used_inv_expr
= XCNEWVEC (unsigned, data
->inv_expr_id
+ 1);
5510 nw
->num_used_inv_expr
= 0;
5515 /* Free memory occupied by the set IVS. */
5518 iv_ca_free (struct iv_ca
**ivs
)
5520 free ((*ivs
)->cand_for_use
);
5521 free ((*ivs
)->n_cand_uses
);
5522 BITMAP_FREE ((*ivs
)->cands
);
5523 free ((*ivs
)->n_invariant_uses
);
5524 free ((*ivs
)->used_inv_expr
);
5529 /* Dumps IVS to FILE. */
5532 iv_ca_dump (struct ivopts_data
*data
, FILE *file
, struct iv_ca
*ivs
)
5534 const char *pref
= " invariants ";
5536 comp_cost cost
= iv_ca_cost (ivs
);
5538 fprintf (file
, " cost: %d (complexity %d)\n", cost
.cost
, cost
.complexity
);
5539 fprintf (file
, " cand_cost: %d\n cand_use_cost: %d (complexity %d)\n",
5540 ivs
->cand_cost
, ivs
->cand_use_cost
.cost
, ivs
->cand_use_cost
.complexity
);
5541 bitmap_print (file
, ivs
->cands
, " candidates: ","\n");
5543 for (i
= 0; i
< ivs
->upto
; i
++)
5545 struct iv_use
*use
= iv_use (data
, i
);
5546 struct cost_pair
*cp
= iv_ca_cand_for_use (ivs
, use
);
5548 fprintf (file
, " use:%d --> iv_cand:%d, cost=(%d,%d)\n",
5549 use
->id
, cp
->cand
->id
, cp
->cost
.cost
, cp
->cost
.complexity
);
5551 fprintf (file
, " use:%d --> ??\n", use
->id
);
5554 for (i
= 1; i
<= data
->max_inv_id
; i
++)
5555 if (ivs
->n_invariant_uses
[i
])
5557 fprintf (file
, "%s%d", pref
, i
);
5560 fprintf (file
, "\n\n");
5563 /* Try changing candidate in IVS to CAND for each use. Return cost of the
5564 new set, and store differences in DELTA. Number of induction variables
5565 in the new set is stored to N_IVS. MIN_NCAND is a flag. When it is true
5566 the function will try to find a solution with mimimal iv candidates. */
5569 iv_ca_extend (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5570 struct iv_cand
*cand
, struct iv_ca_delta
**delta
,
5571 unsigned *n_ivs
, bool min_ncand
)
5576 struct cost_pair
*old_cp
, *new_cp
;
5579 for (i
= 0; i
< ivs
->upto
; i
++)
5581 use
= iv_use (data
, i
);
5582 old_cp
= iv_ca_cand_for_use (ivs
, use
);
5585 && old_cp
->cand
== cand
)
5588 new_cp
= get_use_iv_cost (data
, use
, cand
);
5592 if (!min_ncand
&& !iv_ca_has_deps (ivs
, new_cp
))
5595 if (!min_ncand
&& !cheaper_cost_pair (new_cp
, old_cp
))
5598 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
5601 iv_ca_delta_commit (data
, ivs
, *delta
, true);
5602 cost
= iv_ca_cost (ivs
);
5604 *n_ivs
= iv_ca_n_cands (ivs
);
5605 iv_ca_delta_commit (data
, ivs
, *delta
, false);
5610 /* Try narrowing set IVS by removing CAND. Return the cost of
5611 the new set and store the differences in DELTA. */
5614 iv_ca_narrow (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5615 struct iv_cand
*cand
, struct iv_ca_delta
**delta
)
5619 struct cost_pair
*old_cp
, *new_cp
, *cp
;
5621 struct iv_cand
*cnd
;
5625 for (i
= 0; i
< n_iv_uses (data
); i
++)
5627 use
= iv_use (data
, i
);
5629 old_cp
= iv_ca_cand_for_use (ivs
, use
);
5630 if (old_cp
->cand
!= cand
)
5635 if (data
->consider_all_candidates
)
5637 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, ci
, bi
)
5642 cnd
= iv_cand (data
, ci
);
5644 cp
= get_use_iv_cost (data
, use
, cnd
);
5648 if (!iv_ca_has_deps (ivs
, cp
))
5651 if (!cheaper_cost_pair (cp
, new_cp
))
5659 EXECUTE_IF_AND_IN_BITMAP (use
->related_cands
, ivs
->cands
, 0, ci
, bi
)
5664 cnd
= iv_cand (data
, ci
);
5666 cp
= get_use_iv_cost (data
, use
, cnd
);
5669 if (!iv_ca_has_deps (ivs
, cp
))
5672 if (!cheaper_cost_pair (cp
, new_cp
))
5681 iv_ca_delta_free (delta
);
5682 return infinite_cost
;
5685 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
5688 iv_ca_delta_commit (data
, ivs
, *delta
, true);
5689 cost
= iv_ca_cost (ivs
);
5690 iv_ca_delta_commit (data
, ivs
, *delta
, false);
5695 /* Try optimizing the set of candidates IVS by removing candidates different
5696 from to EXCEPT_CAND from it. Return cost of the new set, and store
5697 differences in DELTA. */
5700 iv_ca_prune (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5701 struct iv_cand
*except_cand
, struct iv_ca_delta
**delta
)
5704 struct iv_ca_delta
*act_delta
, *best_delta
;
5706 comp_cost best_cost
, acost
;
5707 struct iv_cand
*cand
;
5710 best_cost
= iv_ca_cost (ivs
);
5712 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
5714 cand
= iv_cand (data
, i
);
5716 if (cand
== except_cand
)
5719 acost
= iv_ca_narrow (data
, ivs
, cand
, &act_delta
);
5721 if (compare_costs (acost
, best_cost
) < 0)
5724 iv_ca_delta_free (&best_delta
);
5725 best_delta
= act_delta
;
5728 iv_ca_delta_free (&act_delta
);
5737 /* Recurse to possibly remove other unnecessary ivs. */
5738 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
5739 best_cost
= iv_ca_prune (data
, ivs
, except_cand
, delta
);
5740 iv_ca_delta_commit (data
, ivs
, best_delta
, false);
5741 *delta
= iv_ca_delta_join (best_delta
, *delta
);
5745 /* Tries to extend the sets IVS in the best possible way in order
5746 to express the USE. If ORIGINALP is true, prefer candidates from
5747 the original set of IVs, otherwise favor important candidates not
5748 based on any memory object. */
5751 try_add_cand_for (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5752 struct iv_use
*use
, bool originalp
)
5754 comp_cost best_cost
, act_cost
;
5757 struct iv_cand
*cand
;
5758 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
;
5759 struct cost_pair
*cp
;
5761 iv_ca_add_use (data
, ivs
, use
, false);
5762 best_cost
= iv_ca_cost (ivs
);
5764 cp
= iv_ca_cand_for_use (ivs
, use
);
5769 iv_ca_add_use (data
, ivs
, use
, true);
5770 best_cost
= iv_ca_cost (ivs
);
5771 cp
= iv_ca_cand_for_use (ivs
, use
);
5775 best_delta
= iv_ca_delta_add (use
, NULL
, cp
, NULL
);
5776 iv_ca_set_no_cp (data
, ivs
, use
);
5779 /* If ORIGINALP is true, try to find the original IV for the use. Otherwise
5780 first try important candidates not based on any memory object. Only if
5781 this fails, try the specific ones. Rationale -- in loops with many
5782 variables the best choice often is to use just one generic biv. If we
5783 added here many ivs specific to the uses, the optimization algorithm later
5784 would be likely to get stuck in a local minimum, thus causing us to create
5785 too many ivs. The approach from few ivs to more seems more likely to be
5786 successful -- starting from few ivs, replacing an expensive use by a
5787 specific iv should always be a win. */
5788 EXECUTE_IF_SET_IN_BITMAP (data
->important_candidates
, 0, i
, bi
)
5790 cand
= iv_cand (data
, i
);
5792 if (originalp
&& cand
->pos
!=IP_ORIGINAL
)
5795 if (!originalp
&& cand
->iv
->base_object
!= NULL_TREE
)
5798 if (iv_ca_cand_used_p (ivs
, cand
))
5801 cp
= get_use_iv_cost (data
, use
, cand
);
5805 iv_ca_set_cp (data
, ivs
, use
, cp
);
5806 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
,
5808 iv_ca_set_no_cp (data
, ivs
, use
);
5809 act_delta
= iv_ca_delta_add (use
, NULL
, cp
, act_delta
);
5811 if (compare_costs (act_cost
, best_cost
) < 0)
5813 best_cost
= act_cost
;
5815 iv_ca_delta_free (&best_delta
);
5816 best_delta
= act_delta
;
5819 iv_ca_delta_free (&act_delta
);
5822 if (infinite_cost_p (best_cost
))
5824 for (i
= 0; i
< use
->n_map_members
; i
++)
5826 cp
= use
->cost_map
+ i
;
5831 /* Already tried this. */
5832 if (cand
->important
)
5834 if (originalp
&& cand
->pos
== IP_ORIGINAL
)
5836 if (!originalp
&& cand
->iv
->base_object
== NULL_TREE
)
5840 if (iv_ca_cand_used_p (ivs
, cand
))
5844 iv_ca_set_cp (data
, ivs
, use
, cp
);
5845 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
, true);
5846 iv_ca_set_no_cp (data
, ivs
, use
);
5847 act_delta
= iv_ca_delta_add (use
, iv_ca_cand_for_use (ivs
, use
),
5850 if (compare_costs (act_cost
, best_cost
) < 0)
5852 best_cost
= act_cost
;
5855 iv_ca_delta_free (&best_delta
);
5856 best_delta
= act_delta
;
5859 iv_ca_delta_free (&act_delta
);
5863 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
5864 iv_ca_delta_free (&best_delta
);
5866 return !infinite_cost_p (best_cost
);
5869 /* Finds an initial assignment of candidates to uses. */
5871 static struct iv_ca
*
5872 get_initial_solution (struct ivopts_data
*data
, bool originalp
)
5874 struct iv_ca
*ivs
= iv_ca_new (data
);
5877 for (i
= 0; i
< n_iv_uses (data
); i
++)
5878 if (!try_add_cand_for (data
, ivs
, iv_use (data
, i
), originalp
))
5887 /* Tries to improve set of induction variables IVS. */
5890 try_improve_iv_set (struct ivopts_data
*data
, struct iv_ca
*ivs
)
5893 comp_cost acost
, best_cost
= iv_ca_cost (ivs
);
5894 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
, *tmp_delta
;
5895 struct iv_cand
*cand
;
5897 /* Try extending the set of induction variables by one. */
5898 for (i
= 0; i
< n_iv_cands (data
); i
++)
5900 cand
= iv_cand (data
, i
);
5902 if (iv_ca_cand_used_p (ivs
, cand
))
5905 acost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, &n_ivs
, false);
5909 /* If we successfully added the candidate and the set is small enough,
5910 try optimizing it by removing other candidates. */
5911 if (n_ivs
<= ALWAYS_PRUNE_CAND_SET_BOUND
)
5913 iv_ca_delta_commit (data
, ivs
, act_delta
, true);
5914 acost
= iv_ca_prune (data
, ivs
, cand
, &tmp_delta
);
5915 iv_ca_delta_commit (data
, ivs
, act_delta
, false);
5916 act_delta
= iv_ca_delta_join (act_delta
, tmp_delta
);
5919 if (compare_costs (acost
, best_cost
) < 0)
5922 iv_ca_delta_free (&best_delta
);
5923 best_delta
= act_delta
;
5926 iv_ca_delta_free (&act_delta
);
5931 /* Try removing the candidates from the set instead. */
5932 best_cost
= iv_ca_prune (data
, ivs
, NULL
, &best_delta
);
5934 /* Nothing more we can do. */
5939 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
5940 gcc_assert (compare_costs (best_cost
, iv_ca_cost (ivs
)) == 0);
5941 iv_ca_delta_free (&best_delta
);
5945 /* Attempts to find the optimal set of induction variables. We do simple
5946 greedy heuristic -- we try to replace at most one candidate in the selected
5947 solution and remove the unused ivs while this improves the cost. */
5949 static struct iv_ca
*
5950 find_optimal_iv_set_1 (struct ivopts_data
*data
, bool originalp
)
5954 /* Get the initial solution. */
5955 set
= get_initial_solution (data
, originalp
);
5958 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5959 fprintf (dump_file
, "Unable to substitute for ivs, failed.\n");
5963 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5965 fprintf (dump_file
, "Initial set of candidates:\n");
5966 iv_ca_dump (data
, dump_file
, set
);
5969 while (try_improve_iv_set (data
, set
))
5971 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5973 fprintf (dump_file
, "Improved to:\n");
5974 iv_ca_dump (data
, dump_file
, set
);
5981 static struct iv_ca
*
5982 find_optimal_iv_set (struct ivopts_data
*data
)
5985 struct iv_ca
*set
, *origset
;
5987 comp_cost cost
, origcost
;
5989 /* Determine the cost based on a strategy that starts with original IVs,
5990 and try again using a strategy that prefers candidates not based
5992 origset
= find_optimal_iv_set_1 (data
, true);
5993 set
= find_optimal_iv_set_1 (data
, false);
5995 if (!origset
&& !set
)
5998 origcost
= origset
? iv_ca_cost (origset
) : infinite_cost
;
5999 cost
= set
? iv_ca_cost (set
) : infinite_cost
;
6001 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6003 fprintf (dump_file
, "Original cost %d (complexity %d)\n\n",
6004 origcost
.cost
, origcost
.complexity
);
6005 fprintf (dump_file
, "Final cost %d (complexity %d)\n\n",
6006 cost
.cost
, cost
.complexity
);
6009 /* Choose the one with the best cost. */
6010 if (compare_costs (origcost
, cost
) <= 0)
6017 iv_ca_free (&origset
);
6019 for (i
= 0; i
< n_iv_uses (data
); i
++)
6021 use
= iv_use (data
, i
);
6022 use
->selected
= iv_ca_cand_for_use (set
, use
)->cand
;
6028 /* Creates a new induction variable corresponding to CAND. */
6031 create_new_iv (struct ivopts_data
*data
, struct iv_cand
*cand
)
6033 gimple_stmt_iterator incr_pos
;
6043 incr_pos
= gsi_last_bb (ip_normal_pos (data
->current_loop
));
6047 incr_pos
= gsi_last_bb (ip_end_pos (data
->current_loop
));
6055 incr_pos
= gsi_for_stmt (cand
->incremented_at
);
6059 /* Mark that the iv is preserved. */
6060 name_info (data
, cand
->var_before
)->preserve_biv
= true;
6061 name_info (data
, cand
->var_after
)->preserve_biv
= true;
6063 /* Rewrite the increment so that it uses var_before directly. */
6064 find_interesting_uses_op (data
, cand
->var_after
)->selected
= cand
;
6068 gimple_add_tmp_var (cand
->var_before
);
6070 base
= unshare_expr (cand
->iv
->base
);
6072 create_iv (base
, unshare_expr (cand
->iv
->step
),
6073 cand
->var_before
, data
->current_loop
,
6074 &incr_pos
, after
, &cand
->var_before
, &cand
->var_after
);
6077 /* Creates new induction variables described in SET. */
6080 create_new_ivs (struct ivopts_data
*data
, struct iv_ca
*set
)
6083 struct iv_cand
*cand
;
6086 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
6088 cand
= iv_cand (data
, i
);
6089 create_new_iv (data
, cand
);
6092 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6094 fprintf (dump_file
, "\nSelected IV set: \n");
6095 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
6097 cand
= iv_cand (data
, i
);
6098 dump_cand (dump_file
, cand
);
6100 fprintf (dump_file
, "\n");
6104 /* Rewrites USE (definition of iv used in a nonlinear expression)
6105 using candidate CAND. */
6108 rewrite_use_nonlinear_expr (struct ivopts_data
*data
,
6109 struct iv_use
*use
, struct iv_cand
*cand
)
6114 gimple_stmt_iterator bsi
;
6116 /* An important special case -- if we are asked to express value of
6117 the original iv by itself, just exit; there is no need to
6118 introduce a new computation (that might also need casting the
6119 variable to unsigned and back). */
6120 if (cand
->pos
== IP_ORIGINAL
6121 && cand
->incremented_at
== use
->stmt
)
6123 enum tree_code stmt_code
;
6125 gcc_assert (is_gimple_assign (use
->stmt
));
6126 gcc_assert (gimple_assign_lhs (use
->stmt
) == cand
->var_after
);
6128 /* Check whether we may leave the computation unchanged.
6129 This is the case only if it does not rely on other
6130 computations in the loop -- otherwise, the computation
6131 we rely upon may be removed in remove_unused_ivs,
6132 thus leading to ICE. */
6133 stmt_code
= gimple_assign_rhs_code (use
->stmt
);
6134 if (stmt_code
== PLUS_EXPR
6135 || stmt_code
== MINUS_EXPR
6136 || stmt_code
== POINTER_PLUS_EXPR
)
6138 if (gimple_assign_rhs1 (use
->stmt
) == cand
->var_before
)
6139 op
= gimple_assign_rhs2 (use
->stmt
);
6140 else if (gimple_assign_rhs2 (use
->stmt
) == cand
->var_before
)
6141 op
= gimple_assign_rhs1 (use
->stmt
);
6148 if (op
&& expr_invariant_in_loop_p (data
->current_loop
, op
))
6152 comp
= get_computation (data
->current_loop
, use
, cand
);
6153 gcc_assert (comp
!= NULL_TREE
);
6155 switch (gimple_code (use
->stmt
))
6158 tgt
= PHI_RESULT (use
->stmt
);
6160 /* If we should keep the biv, do not replace it. */
6161 if (name_info (data
, tgt
)->preserve_biv
)
6164 bsi
= gsi_after_labels (gimple_bb (use
->stmt
));
6168 tgt
= gimple_assign_lhs (use
->stmt
);
6169 bsi
= gsi_for_stmt (use
->stmt
);
6176 if (!valid_gimple_rhs_p (comp
)
6177 || (gimple_code (use
->stmt
) != GIMPLE_PHI
6178 /* We can't allow re-allocating the stmt as it might be pointed
6180 && (get_gimple_rhs_num_ops (TREE_CODE (comp
))
6181 >= gimple_num_ops (gsi_stmt (bsi
)))))
6183 comp
= force_gimple_operand_gsi (&bsi
, comp
, true, NULL_TREE
,
6184 true, GSI_SAME_STMT
);
6185 if (POINTER_TYPE_P (TREE_TYPE (tgt
)))
6187 duplicate_ssa_name_ptr_info (comp
, SSA_NAME_PTR_INFO (tgt
));
6188 /* As this isn't a plain copy we have to reset alignment
6190 if (SSA_NAME_PTR_INFO (comp
))
6191 mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (comp
));
6195 if (gimple_code (use
->stmt
) == GIMPLE_PHI
)
6197 ass
= gimple_build_assign (tgt
, comp
);
6198 gsi_insert_before (&bsi
, ass
, GSI_SAME_STMT
);
6200 bsi
= gsi_for_stmt (use
->stmt
);
6201 remove_phi_node (&bsi
, false);
6205 gimple_assign_set_rhs_from_tree (&bsi
, comp
);
6206 use
->stmt
= gsi_stmt (bsi
);
6210 /* Performs a peephole optimization to reorder the iv update statement with
6211 a mem ref to enable instruction combining in later phases. The mem ref uses
6212 the iv value before the update, so the reordering transformation requires
6213 adjustment of the offset. CAND is the selected IV_CAND.
6217 t = MEM_REF (base, iv1, 8, 16); // base, index, stride, offset
6225 directly propagating t over to (1) will introduce overlapping live range
6226 thus increase register pressure. This peephole transform it into:
6230 t = MEM_REF (base, iv2, 8, 8);
6237 adjust_iv_update_pos (struct iv_cand
*cand
, struct iv_use
*use
)
6240 gimple iv_update
, stmt
;
6242 gimple_stmt_iterator gsi
, gsi_iv
;
6244 if (cand
->pos
!= IP_NORMAL
)
6247 var_after
= cand
->var_after
;
6248 iv_update
= SSA_NAME_DEF_STMT (var_after
);
6250 bb
= gimple_bb (iv_update
);
6251 gsi
= gsi_last_nondebug_bb (bb
);
6252 stmt
= gsi_stmt (gsi
);
6254 /* Only handle conditional statement for now. */
6255 if (gimple_code (stmt
) != GIMPLE_COND
)
6258 gsi_prev_nondebug (&gsi
);
6259 stmt
= gsi_stmt (gsi
);
6260 if (stmt
!= iv_update
)
6263 gsi_prev_nondebug (&gsi
);
6264 if (gsi_end_p (gsi
))
6267 stmt
= gsi_stmt (gsi
);
6268 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
6271 if (stmt
!= use
->stmt
)
6274 if (TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
6277 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6279 fprintf (dump_file
, "Reordering \n");
6280 print_gimple_stmt (dump_file
, iv_update
, 0, 0);
6281 print_gimple_stmt (dump_file
, use
->stmt
, 0, 0);
6282 fprintf (dump_file
, "\n");
6285 gsi
= gsi_for_stmt (use
->stmt
);
6286 gsi_iv
= gsi_for_stmt (iv_update
);
6287 gsi_move_before (&gsi_iv
, &gsi
);
6289 cand
->pos
= IP_BEFORE_USE
;
6290 cand
->incremented_at
= use
->stmt
;
6293 /* Rewrites USE (address that is an iv) using candidate CAND. */
6296 rewrite_use_address (struct ivopts_data
*data
,
6297 struct iv_use
*use
, struct iv_cand
*cand
)
6300 gimple_stmt_iterator bsi
= gsi_for_stmt (use
->stmt
);
6301 tree base_hint
= NULL_TREE
;
6305 adjust_iv_update_pos (cand
, use
);
6306 ok
= get_computation_aff (data
->current_loop
, use
, cand
, use
->stmt
, &aff
);
6308 unshare_aff_combination (&aff
);
6310 /* To avoid undefined overflow problems, all IV candidates use unsigned
6311 integer types. The drawback is that this makes it impossible for
6312 create_mem_ref to distinguish an IV that is based on a memory object
6313 from one that represents simply an offset.
6315 To work around this problem, we pass a hint to create_mem_ref that
6316 indicates which variable (if any) in aff is an IV based on a memory
6317 object. Note that we only consider the candidate. If this is not
6318 based on an object, the base of the reference is in some subexpression
6319 of the use -- but these will use pointer types, so they are recognized
6320 by the create_mem_ref heuristics anyway. */
6321 if (cand
->iv
->base_object
)
6322 base_hint
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
6324 iv
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
6325 ref
= create_mem_ref (&bsi
, TREE_TYPE (*use
->op_p
), &aff
,
6326 reference_alias_ptr_type (*use
->op_p
),
6327 iv
, base_hint
, data
->speed
);
6328 copy_ref_info (ref
, *use
->op_p
);
6332 /* Rewrites USE (the condition such that one of the arguments is an iv) using
6336 rewrite_use_compare (struct ivopts_data
*data
,
6337 struct iv_use
*use
, struct iv_cand
*cand
)
6339 tree comp
, *var_p
, op
, bound
;
6340 gimple_stmt_iterator bsi
= gsi_for_stmt (use
->stmt
);
6341 enum tree_code compare
;
6342 struct cost_pair
*cp
= get_use_iv_cost (data
, use
, cand
);
6348 tree var
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
6349 tree var_type
= TREE_TYPE (var
);
6352 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6354 fprintf (dump_file
, "Replacing exit test: ");
6355 print_gimple_stmt (dump_file
, use
->stmt
, 0, TDF_SLIM
);
6358 bound
= unshare_expr (fold_convert (var_type
, bound
));
6359 op
= force_gimple_operand (bound
, &stmts
, true, NULL_TREE
);
6361 gsi_insert_seq_on_edge_immediate (
6362 loop_preheader_edge (data
->current_loop
),
6365 gimple_cond_set_lhs (use
->stmt
, var
);
6366 gimple_cond_set_code (use
->stmt
, compare
);
6367 gimple_cond_set_rhs (use
->stmt
, op
);
6371 /* The induction variable elimination failed; just express the original
6373 comp
= get_computation (data
->current_loop
, use
, cand
);
6374 gcc_assert (comp
!= NULL_TREE
);
6376 ok
= extract_cond_operands (data
, use
->stmt
, &var_p
, NULL
, NULL
, NULL
);
6379 *var_p
= force_gimple_operand_gsi (&bsi
, comp
, true, SSA_NAME_VAR (*var_p
),
6380 true, GSI_SAME_STMT
);
6383 /* Rewrites USE using candidate CAND. */
6386 rewrite_use (struct ivopts_data
*data
, struct iv_use
*use
, struct iv_cand
*cand
)
6390 case USE_NONLINEAR_EXPR
:
6391 rewrite_use_nonlinear_expr (data
, use
, cand
);
6395 rewrite_use_address (data
, use
, cand
);
6399 rewrite_use_compare (data
, use
, cand
);
6406 update_stmt (use
->stmt
);
6409 /* Rewrite the uses using the selected induction variables. */
6412 rewrite_uses (struct ivopts_data
*data
)
6415 struct iv_cand
*cand
;
6418 for (i
= 0; i
< n_iv_uses (data
); i
++)
6420 use
= iv_use (data
, i
);
6421 cand
= use
->selected
;
6424 rewrite_use (data
, use
, cand
);
6428 /* Removes the ivs that are not used after rewriting. */
6431 remove_unused_ivs (struct ivopts_data
*data
)
6435 bitmap toremove
= BITMAP_ALLOC (NULL
);
6437 /* Figure out an order in which to release SSA DEFs so that we don't
6438 release something that we'd have to propagate into a debug stmt
6440 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
6442 struct version_info
*info
;
6444 info
= ver_info (data
, j
);
6446 && !integer_zerop (info
->iv
->step
)
6448 && !info
->iv
->have_use_for
6449 && !info
->preserve_biv
)
6451 bitmap_set_bit (toremove
, SSA_NAME_VERSION (info
->iv
->ssa_name
));
6453 tree def
= info
->iv
->ssa_name
;
6455 if (MAY_HAVE_DEBUG_STMTS
&& SSA_NAME_DEF_STMT (def
))
6457 imm_use_iterator imm_iter
;
6458 use_operand_p use_p
;
6462 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, def
)
6464 if (!gimple_debug_bind_p (stmt
))
6467 /* We just want to determine whether to do nothing
6468 (count == 0), to substitute the computed
6469 expression into a single use of the SSA DEF by
6470 itself (count == 1), or to use a debug temp
6471 because the SSA DEF is used multiple times or as
6472 part of a larger expression (count > 1). */
6474 if (gimple_debug_bind_get_value (stmt
) != def
)
6478 BREAK_FROM_IMM_USE_STMT (imm_iter
);
6484 struct iv_use dummy_use
;
6485 struct iv_cand
*best_cand
= NULL
, *cand
;
6486 unsigned i
, best_pref
= 0, cand_pref
;
6488 memset (&dummy_use
, 0, sizeof (dummy_use
));
6489 dummy_use
.iv
= info
->iv
;
6490 for (i
= 0; i
< n_iv_uses (data
) && i
< 64; i
++)
6492 cand
= iv_use (data
, i
)->selected
;
6493 if (cand
== best_cand
)
6495 cand_pref
= operand_equal_p (cand
->iv
->step
,
6499 += TYPE_MODE (TREE_TYPE (cand
->iv
->base
))
6500 == TYPE_MODE (TREE_TYPE (info
->iv
->base
))
6503 += TREE_CODE (cand
->iv
->base
) == INTEGER_CST
6505 if (best_cand
== NULL
|| best_pref
< cand_pref
)
6508 best_pref
= cand_pref
;
6515 tree comp
= get_computation_at (data
->current_loop
,
6516 &dummy_use
, best_cand
,
6517 SSA_NAME_DEF_STMT (def
));
6523 tree vexpr
= make_node (DEBUG_EXPR_DECL
);
6524 DECL_ARTIFICIAL (vexpr
) = 1;
6525 TREE_TYPE (vexpr
) = TREE_TYPE (comp
);
6526 if (SSA_NAME_VAR (def
))
6527 DECL_MODE (vexpr
) = DECL_MODE (SSA_NAME_VAR (def
));
6529 DECL_MODE (vexpr
) = TYPE_MODE (TREE_TYPE (vexpr
));
6530 gimple def_temp
= gimple_build_debug_bind (vexpr
, comp
, NULL
);
6531 gimple_stmt_iterator gsi
;
6533 if (gimple_code (SSA_NAME_DEF_STMT (def
)) == GIMPLE_PHI
)
6534 gsi
= gsi_after_labels (gimple_bb
6535 (SSA_NAME_DEF_STMT (def
)));
6537 gsi
= gsi_for_stmt (SSA_NAME_DEF_STMT (def
));
6539 gsi_insert_before (&gsi
, def_temp
, GSI_SAME_STMT
);
6543 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, def
)
6545 if (!gimple_debug_bind_p (stmt
))
6548 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
6549 SET_USE (use_p
, comp
);
6557 release_defs_bitset (toremove
);
6559 BITMAP_FREE (toremove
);
6562 /* Frees memory occupied by struct tree_niter_desc in *VALUE. Callback
6563 for pointer_map_traverse. */
6566 free_tree_niter_desc (const void *key ATTRIBUTE_UNUSED
, void **value
,
6567 void *data ATTRIBUTE_UNUSED
)
6569 struct tree_niter_desc
*const niter
= (struct tree_niter_desc
*) *value
;
6575 /* Frees data allocated by the optimization of a single loop. */
6578 free_loop_data (struct ivopts_data
*data
)
6586 pointer_map_traverse (data
->niters
, free_tree_niter_desc
, NULL
);
6587 pointer_map_destroy (data
->niters
);
6588 data
->niters
= NULL
;
6591 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
6593 struct version_info
*info
;
6595 info
= ver_info (data
, i
);
6598 info
->has_nonlin_use
= false;
6599 info
->preserve_biv
= false;
6602 bitmap_clear (data
->relevant
);
6603 bitmap_clear (data
->important_candidates
);
6605 for (i
= 0; i
< n_iv_uses (data
); i
++)
6607 struct iv_use
*use
= iv_use (data
, i
);
6610 BITMAP_FREE (use
->related_cands
);
6611 for (j
= 0; j
< use
->n_map_members
; j
++)
6612 if (use
->cost_map
[j
].depends_on
)
6613 BITMAP_FREE (use
->cost_map
[j
].depends_on
);
6614 free (use
->cost_map
);
6617 data
->iv_uses
.truncate (0);
6619 for (i
= 0; i
< n_iv_cands (data
); i
++)
6621 struct iv_cand
*cand
= iv_cand (data
, i
);
6624 if (cand
->depends_on
)
6625 BITMAP_FREE (cand
->depends_on
);
6628 data
->iv_candidates
.truncate (0);
6630 if (data
->version_info_size
< num_ssa_names
)
6632 data
->version_info_size
= 2 * num_ssa_names
;
6633 free (data
->version_info
);
6634 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
6637 data
->max_inv_id
= 0;
6639 FOR_EACH_VEC_ELT (decl_rtl_to_reset
, i
, obj
)
6640 SET_DECL_RTL (obj
, NULL_RTX
);
6642 decl_rtl_to_reset
.truncate (0);
6644 data
->inv_expr_tab
.empty ();
6645 data
->inv_expr_id
= 0;
6648 /* Finalizes data structures used by the iv optimization pass. LOOPS is the
6652 tree_ssa_iv_optimize_finalize (struct ivopts_data
*data
)
6654 free_loop_data (data
);
6655 free (data
->version_info
);
6656 BITMAP_FREE (data
->relevant
);
6657 BITMAP_FREE (data
->important_candidates
);
6659 decl_rtl_to_reset
.release ();
6660 data
->iv_uses
.release ();
6661 data
->iv_candidates
.release ();
6662 data
->inv_expr_tab
.dispose ();
6665 /* Returns true if the loop body BODY includes any function calls. */
6668 loop_body_includes_call (basic_block
*body
, unsigned num_nodes
)
6670 gimple_stmt_iterator gsi
;
6673 for (i
= 0; i
< num_nodes
; i
++)
6674 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
6676 gimple stmt
= gsi_stmt (gsi
);
6677 if (is_gimple_call (stmt
)
6678 && !is_inexpensive_builtin (gimple_call_fndecl (stmt
)))
6684 /* Optimizes the LOOP. Returns true if anything changed. */
6687 tree_ssa_iv_optimize_loop (struct ivopts_data
*data
, struct loop
*loop
)
6689 bool changed
= false;
6690 struct iv_ca
*iv_ca
;
6691 edge exit
= single_dom_exit (loop
);
6694 gcc_assert (!data
->niters
);
6695 data
->current_loop
= loop
;
6696 data
->speed
= optimize_loop_for_speed_p (loop
);
6698 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6700 fprintf (dump_file
, "Processing loop %d\n", loop
->num
);
6704 fprintf (dump_file
, " single exit %d -> %d, exit condition ",
6705 exit
->src
->index
, exit
->dest
->index
);
6706 print_gimple_stmt (dump_file
, last_stmt (exit
->src
), 0, TDF_SLIM
);
6707 fprintf (dump_file
, "\n");
6710 fprintf (dump_file
, "\n");
6713 body
= get_loop_body (loop
);
6714 data
->body_includes_call
= loop_body_includes_call (body
, loop
->num_nodes
);
6715 renumber_gimple_stmt_uids_in_blocks (body
, loop
->num_nodes
);
6718 data
->loop_single_exit_p
= exit
!= NULL
&& loop_only_exit_p (loop
, exit
);
6720 /* For each ssa name determines whether it behaves as an induction variable
6722 if (!find_induction_variables (data
))
6725 /* Finds interesting uses (item 1). */
6726 find_interesting_uses (data
);
6727 if (n_iv_uses (data
) > MAX_CONSIDERED_USES
)
6730 /* Finds candidates for the induction variables (item 2). */
6731 find_iv_candidates (data
);
6733 /* Calculates the costs (item 3, part 1). */
6734 determine_iv_costs (data
);
6735 determine_use_iv_costs (data
);
6736 determine_set_costs (data
);
6738 /* Find the optimal set of induction variables (item 3, part 2). */
6739 iv_ca
= find_optimal_iv_set (data
);
6744 /* Create the new induction variables (item 4, part 1). */
6745 create_new_ivs (data
, iv_ca
);
6746 iv_ca_free (&iv_ca
);
6748 /* Rewrite the uses (item 4, part 2). */
6749 rewrite_uses (data
);
6751 /* Remove the ivs that are unused after rewriting. */
6752 remove_unused_ivs (data
);
6754 /* We have changed the structure of induction variables; it might happen
6755 that definitions in the scev database refer to some of them that were
6760 free_loop_data (data
);
6765 /* Main entry point. Optimizes induction variables in loops. */
6768 tree_ssa_iv_optimize (void)
6771 struct ivopts_data data
;
6774 tree_ssa_iv_optimize_init (&data
);
6776 /* Optimize the loops starting with the innermost ones. */
6777 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
6779 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6780 flow_loop_dump (loop
, dump_file
, NULL
, 1);
6782 tree_ssa_iv_optimize_loop (&data
, loop
);
6785 tree_ssa_iv_optimize_finalize (&data
);