1 /* Induction variable optimizations.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass tries to find the optimal set of induction variables for the loop.
22 It optimizes just the basic linear induction variables (although adding
23 support for other types should not be too hard). It includes the
24 optimizations commonly known as strength reduction, induction variable
25 coalescing and induction variable elimination. It does it in the
28 1) The interesting uses of induction variables are found. This includes
30 -- uses of induction variables in non-linear expressions
31 -- addresses of arrays
32 -- comparisons of induction variables
34 2) Candidates for the induction variables are found. This includes
36 -- old induction variables
37 -- the variables defined by expressions derived from the "interesting
40 3) The optimal (w.r. to a cost function) set of variables is chosen. The
41 cost function assigns a cost to sets of induction variables and consists
44 -- The use costs. Each of the interesting uses chooses the best induction
45 variable in the set and adds its cost to the sum. The cost reflects
46 the time spent on modifying the induction variables value to be usable
47 for the given purpose (adding base and offset for arrays, etc.).
48 -- The variable costs. Each of the variables has a cost assigned that
49 reflects the costs associated with incrementing the value of the
50 variable. The original variables are somewhat preferred.
51 -- The set cost. Depending on the size of the set, extra cost may be
52 added to reflect register pressure.
54 All the costs are defined in a machine-specific way, using the target
55 hooks and machine descriptions to determine them.
57 4) The trees are transformed to use the new variables, the dead code is
60 All of this is done loop by loop. Doing it globally is theoretically
61 possible, it might give a better performance and it might enable us
62 to decide costs more precisely, but getting all the interactions right
63 would be complicated. */
67 #include "coretypes.h"
72 #include "hard-reg-set.h"
73 #include "basic-block.h"
75 #include "diagnostic.h"
76 #include "tree-flow.h"
77 #include "tree-dump.h"
82 #include "tree-pass.h"
84 #include "insn-config.h"
86 #include "pointer-set.h"
88 #include "tree-chrec.h"
89 #include "tree-scalar-evolution.h"
92 #include "langhooks.h"
93 #include "tree-affine.h"
96 /* The infinite cost. */
97 #define INFTY 10000000
99 /* The expected number of loop iterations. TODO -- use profiling instead of
101 #define AVG_LOOP_NITER(LOOP) 5
104 /* Representation of the induction variable. */
107 tree base
; /* Initial value of the iv. */
108 tree base_object
; /* A memory object to that the induction variable points. */
109 tree step
; /* Step of the iv (constant only). */
110 tree ssa_name
; /* The ssa name with the value. */
111 bool biv_p
; /* Is it a biv? */
112 bool have_use_for
; /* Do we already have a use for it? */
113 unsigned use_id
; /* The identifier in the use if it is the case. */
116 /* Per-ssa version information (induction variable descriptions, etc.). */
119 tree name
; /* The ssa name. */
120 struct iv
*iv
; /* Induction variable description. */
121 bool has_nonlin_use
; /* For a loop-level invariant, whether it is used in
122 an expression that is not an induction variable. */
123 unsigned inv_id
; /* Id of an invariant. */
124 bool preserve_biv
; /* For the original biv, whether to preserve it. */
130 USE_NONLINEAR_EXPR
, /* Use in a nonlinear expression. */
131 USE_ADDRESS
, /* Use in an address. */
132 USE_COMPARE
/* Use is a compare. */
135 /* Cost of a computation. */
138 unsigned cost
; /* The runtime cost. */
139 unsigned complexity
; /* The estimate of the complexity of the code for
140 the computation (in no concrete units --
141 complexity field should be larger for more
142 complex expressions and addressing modes). */
145 static const comp_cost zero_cost
= {0, 0};
146 static const comp_cost infinite_cost
= {INFTY
, INFTY
};
148 /* The candidate - cost pair. */
151 struct iv_cand
*cand
; /* The candidate. */
152 comp_cost cost
; /* The cost. */
153 bitmap depends_on
; /* The list of invariants that have to be
155 tree value
; /* For final value elimination, the expression for
156 the final value of the iv. For iv elimination,
157 the new bound to compare with. */
163 unsigned id
; /* The id of the use. */
164 enum use_type type
; /* Type of the use. */
165 struct iv
*iv
; /* The induction variable it is based on. */
166 tree stmt
; /* Statement in that it occurs. */
167 tree
*op_p
; /* The place where it occurs. */
168 bitmap related_cands
; /* The set of "related" iv candidates, plus the common
171 unsigned n_map_members
; /* Number of candidates in the cost_map list. */
172 struct cost_pair
*cost_map
;
173 /* The costs wrto the iv candidates. */
175 struct iv_cand
*selected
;
176 /* The selected candidate. */
179 /* The position where the iv is computed. */
182 IP_NORMAL
, /* At the end, just before the exit condition. */
183 IP_END
, /* At the end of the latch block. */
184 IP_ORIGINAL
/* The original biv. */
187 /* The induction variable candidate. */
190 unsigned id
; /* The number of the candidate. */
191 bool important
; /* Whether this is an "important" candidate, i.e. such
192 that it should be considered by all uses. */
193 enum iv_position pos
; /* Where it is computed. */
194 tree incremented_at
; /* For original biv, the statement where it is
196 tree var_before
; /* The variable used for it before increment. */
197 tree var_after
; /* The variable used for it after increment. */
198 struct iv
*iv
; /* The value of the candidate. NULL for
199 "pseudocandidate" used to indicate the possibility
200 to replace the final value of an iv by direct
201 computation of the value. */
202 unsigned cost
; /* Cost of the candidate. */
203 bitmap depends_on
; /* The list of invariants that are used in step of the
207 /* The data used by the induction variable optimizations. */
209 typedef struct iv_use
*iv_use_p
;
211 DEF_VEC_ALLOC_P(iv_use_p
,heap
);
213 typedef struct iv_cand
*iv_cand_p
;
214 DEF_VEC_P(iv_cand_p
);
215 DEF_VEC_ALLOC_P(iv_cand_p
,heap
);
219 /* The currently optimized loop. */
220 struct loop
*current_loop
;
222 /* Number of registers used in it. */
225 /* Numbers of iterations for all exits of the current loop. */
226 struct pointer_map_t
*niters
;
228 /* The size of version_info array allocated. */
229 unsigned version_info_size
;
231 /* The array of information for the ssa names. */
232 struct version_info
*version_info
;
234 /* The bitmap of indices in version_info whose value was changed. */
237 /* The maximum invariant id. */
240 /* The uses of induction variables. */
241 VEC(iv_use_p
,heap
) *iv_uses
;
243 /* The candidates. */
244 VEC(iv_cand_p
,heap
) *iv_candidates
;
246 /* A bitmap of important candidates. */
247 bitmap important_candidates
;
249 /* Whether to consider just related and important candidates when replacing a
251 bool consider_all_candidates
;
254 /* An assignment of iv candidates to uses. */
258 /* The number of uses covered by the assignment. */
261 /* Number of uses that cannot be expressed by the candidates in the set. */
264 /* Candidate assigned to a use, together with the related costs. */
265 struct cost_pair
**cand_for_use
;
267 /* Number of times each candidate is used. */
268 unsigned *n_cand_uses
;
270 /* The candidates used. */
273 /* The number of candidates in the set. */
276 /* Total number of registers needed. */
279 /* Total cost of expressing uses. */
280 comp_cost cand_use_cost
;
282 /* Total cost of candidates. */
285 /* Number of times each invariant is used. */
286 unsigned *n_invariant_uses
;
288 /* Total cost of the assignment. */
292 /* Difference of two iv candidate assignments. */
299 /* An old assignment (for rollback purposes). */
300 struct cost_pair
*old_cp
;
302 /* A new assignment. */
303 struct cost_pair
*new_cp
;
305 /* Next change in the list. */
306 struct iv_ca_delta
*next_change
;
309 /* Bound on number of candidates below that all candidates are considered. */
311 #define CONSIDER_ALL_CANDIDATES_BOUND \
312 ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
314 /* If there are more iv occurrences, we just give up (it is quite unlikely that
315 optimizing such a loop would help, and it would take ages). */
317 #define MAX_CONSIDERED_USES \
318 ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
320 /* If there are at most this number of ivs in the set, try removing unnecessary
321 ivs from the set always. */
323 #define ALWAYS_PRUNE_CAND_SET_BOUND \
324 ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
326 /* The list of trees for that the decl_rtl field must be reset is stored
329 static VEC(tree
,heap
) *decl_rtl_to_reset
;
331 /* Number of uses recorded in DATA. */
333 static inline unsigned
334 n_iv_uses (struct ivopts_data
*data
)
336 return VEC_length (iv_use_p
, data
->iv_uses
);
339 /* Ith use recorded in DATA. */
341 static inline struct iv_use
*
342 iv_use (struct ivopts_data
*data
, unsigned i
)
344 return VEC_index (iv_use_p
, data
->iv_uses
, i
);
347 /* Number of candidates recorded in DATA. */
349 static inline unsigned
350 n_iv_cands (struct ivopts_data
*data
)
352 return VEC_length (iv_cand_p
, data
->iv_candidates
);
355 /* Ith candidate recorded in DATA. */
357 static inline struct iv_cand
*
358 iv_cand (struct ivopts_data
*data
, unsigned i
)
360 return VEC_index (iv_cand_p
, data
->iv_candidates
, i
);
363 /* The single loop exit if it dominates the latch, NULL otherwise. */
366 single_dom_exit (struct loop
*loop
)
368 edge exit
= single_exit (loop
);
373 if (!just_once_each_iteration_p (loop
, exit
->src
))
379 /* Dumps information about the induction variable IV to FILE. */
381 extern void dump_iv (FILE *, struct iv
*);
383 dump_iv (FILE *file
, struct iv
*iv
)
387 fprintf (file
, "ssa name ");
388 print_generic_expr (file
, iv
->ssa_name
, TDF_SLIM
);
389 fprintf (file
, "\n");
392 fprintf (file
, " type ");
393 print_generic_expr (file
, TREE_TYPE (iv
->base
), TDF_SLIM
);
394 fprintf (file
, "\n");
398 fprintf (file
, " base ");
399 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
400 fprintf (file
, "\n");
402 fprintf (file
, " step ");
403 print_generic_expr (file
, iv
->step
, TDF_SLIM
);
404 fprintf (file
, "\n");
408 fprintf (file
, " invariant ");
409 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
410 fprintf (file
, "\n");
415 fprintf (file
, " base object ");
416 print_generic_expr (file
, iv
->base_object
, TDF_SLIM
);
417 fprintf (file
, "\n");
421 fprintf (file
, " is a biv\n");
424 /* Dumps information about the USE to FILE. */
426 extern void dump_use (FILE *, struct iv_use
*);
428 dump_use (FILE *file
, struct iv_use
*use
)
430 fprintf (file
, "use %d\n", use
->id
);
434 case USE_NONLINEAR_EXPR
:
435 fprintf (file
, " generic\n");
439 fprintf (file
, " address\n");
443 fprintf (file
, " compare\n");
450 fprintf (file
, " in statement ");
451 print_generic_expr (file
, use
->stmt
, TDF_SLIM
);
452 fprintf (file
, "\n");
454 fprintf (file
, " at position ");
456 print_generic_expr (file
, *use
->op_p
, TDF_SLIM
);
457 fprintf (file
, "\n");
459 dump_iv (file
, use
->iv
);
461 if (use
->related_cands
)
463 fprintf (file
, " related candidates ");
464 dump_bitmap (file
, use
->related_cands
);
468 /* Dumps information about the uses to FILE. */
470 extern void dump_uses (FILE *, struct ivopts_data
*);
472 dump_uses (FILE *file
, struct ivopts_data
*data
)
477 for (i
= 0; i
< n_iv_uses (data
); i
++)
479 use
= iv_use (data
, i
);
481 dump_use (file
, use
);
482 fprintf (file
, "\n");
486 /* Dumps information about induction variable candidate CAND to FILE. */
488 extern void dump_cand (FILE *, struct iv_cand
*);
490 dump_cand (FILE *file
, struct iv_cand
*cand
)
492 struct iv
*iv
= cand
->iv
;
494 fprintf (file
, "candidate %d%s\n",
495 cand
->id
, cand
->important
? " (important)" : "");
497 if (cand
->depends_on
)
499 fprintf (file
, " depends on ");
500 dump_bitmap (file
, cand
->depends_on
);
505 fprintf (file
, " final value replacement\n");
512 fprintf (file
, " incremented before exit test\n");
516 fprintf (file
, " incremented at end\n");
520 fprintf (file
, " original biv\n");
527 /* Returns the info for ssa version VER. */
529 static inline struct version_info
*
530 ver_info (struct ivopts_data
*data
, unsigned ver
)
532 return data
->version_info
+ ver
;
535 /* Returns the info for ssa name NAME. */
537 static inline struct version_info
*
538 name_info (struct ivopts_data
*data
, tree name
)
540 return ver_info (data
, SSA_NAME_VERSION (name
));
543 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
547 stmt_after_ip_normal_pos (struct loop
*loop
, tree stmt
)
549 basic_block bb
= ip_normal_pos (loop
), sbb
= bb_for_stmt (stmt
);
553 if (sbb
== loop
->latch
)
559 return stmt
== last_stmt (bb
);
562 /* Returns true if STMT if after the place where the original induction
563 variable CAND is incremented. */
566 stmt_after_ip_original_pos (struct iv_cand
*cand
, tree stmt
)
568 basic_block cand_bb
= bb_for_stmt (cand
->incremented_at
);
569 basic_block stmt_bb
= bb_for_stmt (stmt
);
570 block_stmt_iterator bsi
;
572 if (!dominated_by_p (CDI_DOMINATORS
, stmt_bb
, cand_bb
))
575 if (stmt_bb
!= cand_bb
)
578 /* Scan the block from the end, since the original ivs are usually
579 incremented at the end of the loop body. */
580 for (bsi
= bsi_last (stmt_bb
); ; bsi_prev (&bsi
))
582 if (bsi_stmt (bsi
) == cand
->incremented_at
)
584 if (bsi_stmt (bsi
) == stmt
)
589 /* Returns true if STMT if after the place where the induction variable
590 CAND is incremented in LOOP. */
593 stmt_after_increment (struct loop
*loop
, struct iv_cand
*cand
, tree stmt
)
601 return stmt_after_ip_normal_pos (loop
, stmt
);
604 return stmt_after_ip_original_pos (cand
, stmt
);
611 /* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
614 abnormal_ssa_name_p (tree exp
)
619 if (TREE_CODE (exp
) != SSA_NAME
)
622 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
) != 0;
625 /* Returns false if BASE or INDEX contains a ssa name that occurs in an
626 abnormal phi node. Callback for for_each_index. */
629 idx_contains_abnormal_ssa_name_p (tree base
, tree
*index
,
630 void *data ATTRIBUTE_UNUSED
)
632 if (TREE_CODE (base
) == ARRAY_REF
)
634 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 2)))
636 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 3)))
640 return !abnormal_ssa_name_p (*index
);
643 /* Returns true if EXPR contains a ssa name that occurs in an
644 abnormal phi node. */
647 contains_abnormal_ssa_name_p (tree expr
)
650 enum tree_code_class codeclass
;
655 code
= TREE_CODE (expr
);
656 codeclass
= TREE_CODE_CLASS (code
);
658 if (code
== SSA_NAME
)
659 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr
) != 0;
661 if (code
== INTEGER_CST
662 || is_gimple_min_invariant (expr
))
665 if (code
== ADDR_EXPR
)
666 return !for_each_index (&TREE_OPERAND (expr
, 0),
667 idx_contains_abnormal_ssa_name_p
,
674 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1)))
679 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0)))
691 /* Returns tree describing number of iterations determined from
692 EXIT of DATA->current_loop, or NULL if something goes wrong. */
695 niter_for_exit (struct ivopts_data
*data
, edge exit
)
697 struct tree_niter_desc desc
;
703 data
->niters
= pointer_map_create ();
707 slot
= pointer_map_contains (data
->niters
, exit
);
711 /* Try to determine number of iterations. We must know it
712 unconditionally (i.e., without possibility of # of iterations
713 being zero). Also, we cannot safely work with ssa names that
714 appear in phi nodes on abnormal edges, so that we do not create
715 overlapping life ranges for them (PR 27283). */
716 if (number_of_iterations_exit (data
->current_loop
,
718 && integer_zerop (desc
.may_be_zero
)
719 && !contains_abnormal_ssa_name_p (desc
.niter
))
724 *pointer_map_insert (data
->niters
, exit
) = niter
;
727 niter
= (tree
) *slot
;
732 /* Returns tree describing number of iterations determined from
733 single dominating exit of DATA->current_loop, or NULL if something
737 niter_for_single_dom_exit (struct ivopts_data
*data
)
739 edge exit
= single_dom_exit (data
->current_loop
);
744 return niter_for_exit (data
, exit
);
747 /* Initializes data structures used by the iv optimization pass, stored
751 tree_ssa_iv_optimize_init (struct ivopts_data
*data
)
753 data
->version_info_size
= 2 * num_ssa_names
;
754 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
755 data
->relevant
= BITMAP_ALLOC (NULL
);
756 data
->important_candidates
= BITMAP_ALLOC (NULL
);
757 data
->max_inv_id
= 0;
759 data
->iv_uses
= VEC_alloc (iv_use_p
, heap
, 20);
760 data
->iv_candidates
= VEC_alloc (iv_cand_p
, heap
, 20);
761 decl_rtl_to_reset
= VEC_alloc (tree
, heap
, 20);
764 /* Returns a memory object to that EXPR points. In case we are able to
765 determine that it does not point to any such object, NULL is returned. */
768 determine_base_object (tree expr
)
770 enum tree_code code
= TREE_CODE (expr
);
773 /* If this is a pointer casted to any type, we need to determine
774 the base object for the pointer; so handle conversions before
775 throwing away non-pointer expressions. */
776 if (CONVERT_EXPR_P (expr
))
777 return determine_base_object (TREE_OPERAND (expr
, 0));
779 if (!POINTER_TYPE_P (TREE_TYPE (expr
)))
788 obj
= TREE_OPERAND (expr
, 0);
789 base
= get_base_address (obj
);
794 if (TREE_CODE (base
) == INDIRECT_REF
)
795 return determine_base_object (TREE_OPERAND (base
, 0));
797 return fold_convert (ptr_type_node
,
798 build_fold_addr_expr (base
));
800 case POINTER_PLUS_EXPR
:
801 return determine_base_object (TREE_OPERAND (expr
, 0));
805 /* Pointer addition is done solely using POINTER_PLUS_EXPR. */
809 return fold_convert (ptr_type_node
, expr
);
813 /* Allocates an induction variable with given initial value BASE and step STEP
817 alloc_iv (tree base
, tree step
)
819 struct iv
*iv
= XCNEW (struct iv
);
820 gcc_assert (step
!= NULL_TREE
);
823 iv
->base_object
= determine_base_object (base
);
826 iv
->have_use_for
= false;
828 iv
->ssa_name
= NULL_TREE
;
833 /* Sets STEP and BASE for induction variable IV. */
836 set_iv (struct ivopts_data
*data
, tree iv
, tree base
, tree step
)
838 struct version_info
*info
= name_info (data
, iv
);
840 gcc_assert (!info
->iv
);
842 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (iv
));
843 info
->iv
= alloc_iv (base
, step
);
844 info
->iv
->ssa_name
= iv
;
847 /* Finds induction variable declaration for VAR. */
850 get_iv (struct ivopts_data
*data
, tree var
)
853 tree type
= TREE_TYPE (var
);
855 if (!POINTER_TYPE_P (type
)
856 && !INTEGRAL_TYPE_P (type
))
859 if (!name_info (data
, var
)->iv
)
861 bb
= bb_for_stmt (SSA_NAME_DEF_STMT (var
));
864 || !flow_bb_inside_loop_p (data
->current_loop
, bb
))
865 set_iv (data
, var
, var
, build_int_cst (type
, 0));
868 return name_info (data
, var
)->iv
;
871 /* Determines the step of a biv defined in PHI. Returns NULL if PHI does
872 not define a simple affine biv with nonzero step. */
875 determine_biv_step (tree phi
)
877 struct loop
*loop
= bb_for_stmt (phi
)->loop_father
;
878 tree name
= PHI_RESULT (phi
);
881 if (!is_gimple_reg (name
))
884 if (!simple_iv (loop
, phi
, name
, &iv
, true))
887 return integer_zerop (iv
.step
) ? NULL_TREE
: iv
.step
;
890 /* Finds basic ivs. */
893 find_bivs (struct ivopts_data
*data
)
895 tree phi
, step
, type
, base
;
897 struct loop
*loop
= data
->current_loop
;
899 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
901 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
904 step
= determine_biv_step (phi
);
908 base
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
909 base
= expand_simple_operations (base
);
910 if (contains_abnormal_ssa_name_p (base
)
911 || contains_abnormal_ssa_name_p (step
))
914 type
= TREE_TYPE (PHI_RESULT (phi
));
915 base
= fold_convert (type
, base
);
918 if (POINTER_TYPE_P (type
))
919 step
= fold_convert (sizetype
, step
);
921 step
= fold_convert (type
, step
);
924 set_iv (data
, PHI_RESULT (phi
), base
, step
);
931 /* Marks basic ivs. */
934 mark_bivs (struct ivopts_data
*data
)
937 struct iv
*iv
, *incr_iv
;
938 struct loop
*loop
= data
->current_loop
;
941 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
943 iv
= get_iv (data
, PHI_RESULT (phi
));
947 var
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
948 incr_iv
= get_iv (data
, var
);
952 /* If the increment is in the subloop, ignore it. */
953 incr_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (var
));
954 if (incr_bb
->loop_father
!= data
->current_loop
955 || (incr_bb
->flags
& BB_IRREDUCIBLE_LOOP
))
959 incr_iv
->biv_p
= true;
963 /* Checks whether STMT defines a linear induction variable and stores its
967 find_givs_in_stmt_scev (struct ivopts_data
*data
, tree stmt
, affine_iv
*iv
)
970 struct loop
*loop
= data
->current_loop
;
972 iv
->base
= NULL_TREE
;
973 iv
->step
= NULL_TREE
;
975 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
978 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
979 if (TREE_CODE (lhs
) != SSA_NAME
)
982 if (!simple_iv (loop
, stmt
, GIMPLE_STMT_OPERAND (stmt
, 1), iv
, true))
984 iv
->base
= expand_simple_operations (iv
->base
);
986 if (contains_abnormal_ssa_name_p (iv
->base
)
987 || contains_abnormal_ssa_name_p (iv
->step
))
993 /* Finds general ivs in statement STMT. */
996 find_givs_in_stmt (struct ivopts_data
*data
, tree stmt
)
1000 if (!find_givs_in_stmt_scev (data
, stmt
, &iv
))
1003 set_iv (data
, GIMPLE_STMT_OPERAND (stmt
, 0), iv
.base
, iv
.step
);
1006 /* Finds general ivs in basic block BB. */
1009 find_givs_in_bb (struct ivopts_data
*data
, basic_block bb
)
1011 block_stmt_iterator bsi
;
1013 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1014 find_givs_in_stmt (data
, bsi_stmt (bsi
));
1017 /* Finds general ivs. */
1020 find_givs (struct ivopts_data
*data
)
1022 struct loop
*loop
= data
->current_loop
;
1023 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1026 for (i
= 0; i
< loop
->num_nodes
; i
++)
1027 find_givs_in_bb (data
, body
[i
]);
1031 /* For each ssa name defined in LOOP determines whether it is an induction
1032 variable and if so, its initial value and step. */
1035 find_induction_variables (struct ivopts_data
*data
)
1040 if (!find_bivs (data
))
1046 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1048 tree niter
= niter_for_single_dom_exit (data
);
1052 fprintf (dump_file
, " number of iterations ");
1053 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1054 fprintf (dump_file
, "\n\n");
1057 fprintf (dump_file
, "Induction variables:\n\n");
1059 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1061 if (ver_info (data
, i
)->iv
)
1062 dump_iv (dump_file
, ver_info (data
, i
)->iv
);
1069 /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV. */
1071 static struct iv_use
*
1072 record_use (struct ivopts_data
*data
, tree
*use_p
, struct iv
*iv
,
1073 tree stmt
, enum use_type use_type
)
1075 struct iv_use
*use
= XCNEW (struct iv_use
);
1077 use
->id
= n_iv_uses (data
);
1078 use
->type
= use_type
;
1082 use
->related_cands
= BITMAP_ALLOC (NULL
);
1084 /* To avoid showing ssa name in the dumps, if it was not reset by the
1086 iv
->ssa_name
= NULL_TREE
;
1088 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1089 dump_use (dump_file
, use
);
1091 VEC_safe_push (iv_use_p
, heap
, data
->iv_uses
, use
);
1096 /* Checks whether OP is a loop-level invariant and if so, records it.
1097 NONLINEAR_USE is true if the invariant is used in a way we do not
1098 handle specially. */
1101 record_invariant (struct ivopts_data
*data
, tree op
, bool nonlinear_use
)
1104 struct version_info
*info
;
1106 if (TREE_CODE (op
) != SSA_NAME
1107 || !is_gimple_reg (op
))
1110 bb
= bb_for_stmt (SSA_NAME_DEF_STMT (op
));
1112 && flow_bb_inside_loop_p (data
->current_loop
, bb
))
1115 info
= name_info (data
, op
);
1117 info
->has_nonlin_use
|= nonlinear_use
;
1119 info
->inv_id
= ++data
->max_inv_id
;
1120 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (op
));
1123 /* Checks whether the use OP is interesting and if so, records it. */
1125 static struct iv_use
*
1126 find_interesting_uses_op (struct ivopts_data
*data
, tree op
)
1133 if (TREE_CODE (op
) != SSA_NAME
)
1136 iv
= get_iv (data
, op
);
1140 if (iv
->have_use_for
)
1142 use
= iv_use (data
, iv
->use_id
);
1144 gcc_assert (use
->type
== USE_NONLINEAR_EXPR
);
1148 if (integer_zerop (iv
->step
))
1150 record_invariant (data
, op
, true);
1153 iv
->have_use_for
= true;
1155 civ
= XNEW (struct iv
);
1158 stmt
= SSA_NAME_DEF_STMT (op
);
1159 gcc_assert (TREE_CODE (stmt
) == PHI_NODE
1160 || TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
);
1162 use
= record_use (data
, NULL
, civ
, stmt
, USE_NONLINEAR_EXPR
);
1163 iv
->use_id
= use
->id
;
1168 /* Given a condition *COND_P, checks whether it is a compare of an induction
1169 variable and an invariant. If this is the case, CONTROL_VAR is set
1170 to location of the iv, BOUND to the location of the invariant,
1171 IV_VAR and IV_BOUND are set to the corresponding induction variable
1172 descriptions, and true is returned. If this is not the case,
1173 CONTROL_VAR and BOUND are set to the arguments of the condition and
1174 false is returned. */
1177 extract_cond_operands (struct ivopts_data
*data
, tree
*cond_p
,
1178 tree
**control_var
, tree
**bound
,
1179 struct iv
**iv_var
, struct iv
**iv_bound
)
1181 /* The nodes returned when COND has just one operand. Note that you should
1182 not modify anything in BOUND or IV_BOUND because of this. */
1183 static struct iv const_iv
;
1185 tree cond
= *cond_p
;
1186 tree
*op0
= &zero
, *op1
= &zero
, *tmp_op
;
1187 struct iv
*iv0
= &const_iv
, *iv1
= &const_iv
, *tmp_iv
;
1190 zero
= integer_zero_node
;
1191 const_iv
.step
= integer_zero_node
;
1193 if (TREE_CODE (cond
) == SSA_NAME
)
1196 iv0
= get_iv (data
, cond
);
1197 ret
= (iv0
&& !integer_zerop (iv0
->step
));
1201 if (!COMPARISON_CLASS_P (cond
))
1207 op0
= &TREE_OPERAND (cond
, 0);
1208 op1
= &TREE_OPERAND (cond
, 1);
1209 if (TREE_CODE (*op0
) == SSA_NAME
)
1210 iv0
= get_iv (data
, *op0
);
1211 if (TREE_CODE (*op1
) == SSA_NAME
)
1212 iv1
= get_iv (data
, *op1
);
1214 /* Exactly one of the compared values must be an iv, and the other one must
1219 if (integer_zerop (iv0
->step
))
1221 /* Control variable may be on the other side. */
1222 tmp_op
= op0
; op0
= op1
; op1
= tmp_op
;
1223 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
1225 ret
= !integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
);
1229 *control_var
= op0
;;
1240 /* Checks whether the condition *COND_P in STMT is interesting
1241 and if so, records it. */
1244 find_interesting_uses_cond (struct ivopts_data
*data
, tree stmt
, tree
*cond_p
)
1246 tree
*var_p
, *bound_p
;
1247 struct iv
*var_iv
, *civ
;
1249 if (!extract_cond_operands (data
, cond_p
, &var_p
, &bound_p
, &var_iv
, NULL
))
1251 find_interesting_uses_op (data
, *var_p
);
1252 find_interesting_uses_op (data
, *bound_p
);
1256 civ
= XNEW (struct iv
);
1258 record_use (data
, cond_p
, civ
, stmt
, USE_COMPARE
);
1261 /* Returns true if expression EXPR is obviously invariant in LOOP,
1262 i.e. if all its operands are defined outside of the LOOP. LOOP
1263 should not be the function body. */
1266 expr_invariant_in_loop_p (struct loop
*loop
, tree expr
)
1271 gcc_assert (loop_depth (loop
) > 0);
1273 if (is_gimple_min_invariant (expr
))
1276 if (TREE_CODE (expr
) == SSA_NAME
)
1278 def_bb
= bb_for_stmt (SSA_NAME_DEF_STMT (expr
));
1280 && flow_bb_inside_loop_p (loop
, def_bb
))
1286 if (!EXPR_P (expr
) && !GIMPLE_STMT_P (expr
))
1289 len
= TREE_OPERAND_LENGTH (expr
);
1290 for (i
= 0; i
< len
; i
++)
1291 if (!expr_invariant_in_loop_p (loop
, TREE_OPERAND (expr
, i
)))
1297 /* Cumulates the steps of indices into DATA and replaces their values with the
1298 initial ones. Returns false when the value of the index cannot be determined.
1299 Callback for for_each_index. */
1301 struct ifs_ivopts_data
1303 struct ivopts_data
*ivopts_data
;
1309 idx_find_step (tree base
, tree
*idx
, void *data
)
1311 struct ifs_ivopts_data
*dta
= (struct ifs_ivopts_data
*) data
;
1313 tree step
, iv_base
, iv_step
, lbound
, off
;
1314 struct loop
*loop
= dta
->ivopts_data
->current_loop
;
1316 if (TREE_CODE (base
) == MISALIGNED_INDIRECT_REF
1317 || TREE_CODE (base
) == ALIGN_INDIRECT_REF
)
1320 /* If base is a component ref, require that the offset of the reference
1322 if (TREE_CODE (base
) == COMPONENT_REF
)
1324 off
= component_ref_field_offset (base
);
1325 return expr_invariant_in_loop_p (loop
, off
);
1328 /* If base is array, first check whether we will be able to move the
1329 reference out of the loop (in order to take its address in strength
1330 reduction). In order for this to work we need both lower bound
1331 and step to be loop invariants. */
1332 if (TREE_CODE (base
) == ARRAY_REF
)
1334 step
= array_ref_element_size (base
);
1335 lbound
= array_ref_low_bound (base
);
1337 if (!expr_invariant_in_loop_p (loop
, step
)
1338 || !expr_invariant_in_loop_p (loop
, lbound
))
1342 if (TREE_CODE (*idx
) != SSA_NAME
)
1345 iv
= get_iv (dta
->ivopts_data
, *idx
);
1349 /* XXX We produce for a base of *D42 with iv->base being &x[0]
1350 *&x[0], which is not folded and does not trigger the
1351 ARRAY_REF path below. */
1354 if (integer_zerop (iv
->step
))
1357 if (TREE_CODE (base
) == ARRAY_REF
)
1359 step
= array_ref_element_size (base
);
1361 /* We only handle addresses whose step is an integer constant. */
1362 if (TREE_CODE (step
) != INTEGER_CST
)
1366 /* The step for pointer arithmetics already is 1 byte. */
1367 step
= build_int_cst (sizetype
, 1);
1371 if (!convert_affine_scev (dta
->ivopts_data
->current_loop
,
1372 sizetype
, &iv_base
, &iv_step
, dta
->stmt
,
1375 /* The index might wrap. */
1379 step
= fold_build2 (MULT_EXPR
, sizetype
, step
, iv_step
);
1380 dta
->step
= fold_build2 (PLUS_EXPR
, sizetype
, dta
->step
, step
);
1385 /* Records use in index IDX. Callback for for_each_index. Ivopts data
1386 object is passed to it in DATA. */
1389 idx_record_use (tree base
, tree
*idx
,
1392 struct ivopts_data
*data
= (struct ivopts_data
*) vdata
;
1393 find_interesting_uses_op (data
, *idx
);
1394 if (TREE_CODE (base
) == ARRAY_REF
)
1396 find_interesting_uses_op (data
, array_ref_element_size (base
));
1397 find_interesting_uses_op (data
, array_ref_low_bound (base
));
1402 /* If we can prove that TOP = cst * BOT for some constant cst,
1403 store cst to MUL and return true. Otherwise return false.
1404 The returned value is always sign-extended, regardless of the
1405 signedness of TOP and BOT. */
1408 constant_multiple_of (tree top
, tree bot
, double_int
*mul
)
1411 enum tree_code code
;
1412 double_int res
, p0
, p1
;
1413 unsigned precision
= TYPE_PRECISION (TREE_TYPE (top
));
1418 if (operand_equal_p (top
, bot
, 0))
1420 *mul
= double_int_one
;
1424 code
= TREE_CODE (top
);
1428 mby
= TREE_OPERAND (top
, 1);
1429 if (TREE_CODE (mby
) != INTEGER_CST
)
1432 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &res
))
1435 *mul
= double_int_sext (double_int_mul (res
, tree_to_double_int (mby
)),
1441 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &p0
)
1442 || !constant_multiple_of (TREE_OPERAND (top
, 1), bot
, &p1
))
1445 if (code
== MINUS_EXPR
)
1446 p1
= double_int_neg (p1
);
1447 *mul
= double_int_sext (double_int_add (p0
, p1
), precision
);
1451 if (TREE_CODE (bot
) != INTEGER_CST
)
1454 p0
= double_int_sext (tree_to_double_int (top
), precision
);
1455 p1
= double_int_sext (tree_to_double_int (bot
), precision
);
1456 if (double_int_zero_p (p1
))
1458 *mul
= double_int_sext (double_int_sdivmod (p0
, p1
, FLOOR_DIV_EXPR
, &res
),
1460 return double_int_zero_p (res
);
1467 /* Returns true if memory reference REF with step STEP may be unaligned. */
1470 may_be_unaligned_p (tree ref
, tree step
)
1474 HOST_WIDE_INT bitsize
;
1475 HOST_WIDE_INT bitpos
;
1477 enum machine_mode mode
;
1478 int unsignedp
, volatilep
;
1479 unsigned base_align
;
1481 /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
1482 thus they are not misaligned. */
1483 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
1486 /* The test below is basically copy of what expr.c:normal_inner_ref
1487 does to check whether the object must be loaded by parts when
1488 STRICT_ALIGNMENT is true. */
1489 base
= get_inner_reference (ref
, &bitsize
, &bitpos
, &toffset
, &mode
,
1490 &unsignedp
, &volatilep
, true);
1491 base_type
= TREE_TYPE (base
);
1492 base_align
= TYPE_ALIGN (base_type
);
1494 if (mode
!= BLKmode
)
1497 tree al
= build_int_cst (TREE_TYPE (step
),
1498 GET_MODE_ALIGNMENT (mode
) / BITS_PER_UNIT
);
1500 if (base_align
< GET_MODE_ALIGNMENT (mode
)
1501 || bitpos
% GET_MODE_ALIGNMENT (mode
) != 0
1502 || bitpos
% BITS_PER_UNIT
!= 0)
1505 if (!constant_multiple_of (step
, al
, &mul
))
1512 /* Return true if EXPR may be non-addressable. */
1515 may_be_nonaddressable_p (tree expr
)
1517 switch (TREE_CODE (expr
))
1519 case TARGET_MEM_REF
:
1520 /* TARGET_MEM_REFs are translated directly to valid MEMs on the
1521 target, thus they are always addressable. */
1525 return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr
, 1))
1526 || may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1528 case VIEW_CONVERT_EXPR
:
1529 /* This kind of view-conversions may wrap non-addressable objects
1530 and make them look addressable. After some processing the
1531 non-addressability may be uncovered again, causing ADDR_EXPRs
1532 of inappropriate objects to be built. */
1533 if (is_gimple_reg (TREE_OPERAND (expr
, 0))
1534 || is_gimple_min_invariant (TREE_OPERAND (expr
, 0)))
1537 /* ... fall through ... */
1540 case ARRAY_RANGE_REF
:
1541 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1553 /* Finds addresses in *OP_P inside STMT. */
1556 find_interesting_uses_address (struct ivopts_data
*data
, tree stmt
, tree
*op_p
)
1558 tree base
= *op_p
, step
= build_int_cst (sizetype
, 0);
1560 struct ifs_ivopts_data ifs_ivopts_data
;
1562 /* Do not play with volatile memory references. A bit too conservative,
1563 perhaps, but safe. */
1564 if (stmt_ann (stmt
)->has_volatile_ops
)
1567 /* Ignore bitfields for now. Not really something terribly complicated
1569 if (TREE_CODE (base
) == BIT_FIELD_REF
)
1572 base
= unshare_expr (base
);
1574 if (TREE_CODE (base
) == TARGET_MEM_REF
)
1576 tree type
= build_pointer_type (TREE_TYPE (base
));
1580 && TREE_CODE (TMR_BASE (base
)) == SSA_NAME
)
1582 civ
= get_iv (data
, TMR_BASE (base
));
1586 TMR_BASE (base
) = civ
->base
;
1589 if (TMR_INDEX (base
)
1590 && TREE_CODE (TMR_INDEX (base
)) == SSA_NAME
)
1592 civ
= get_iv (data
, TMR_INDEX (base
));
1596 TMR_INDEX (base
) = civ
->base
;
1601 if (TMR_STEP (base
))
1602 astep
= fold_build2 (MULT_EXPR
, type
, TMR_STEP (base
), astep
);
1604 step
= fold_build2 (PLUS_EXPR
, type
, step
, astep
);
1608 if (integer_zerop (step
))
1610 base
= tree_mem_ref_addr (type
, base
);
1614 ifs_ivopts_data
.ivopts_data
= data
;
1615 ifs_ivopts_data
.stmt
= stmt
;
1616 ifs_ivopts_data
.step
= build_int_cst (sizetype
, 0);
1617 if (!for_each_index (&base
, idx_find_step
, &ifs_ivopts_data
)
1618 || integer_zerop (ifs_ivopts_data
.step
))
1620 step
= ifs_ivopts_data
.step
;
1622 gcc_assert (TREE_CODE (base
) != ALIGN_INDIRECT_REF
);
1623 gcc_assert (TREE_CODE (base
) != MISALIGNED_INDIRECT_REF
);
1625 /* Check that the base expression is addressable. This needs
1626 to be done after substituting bases of IVs into it. */
1627 if (may_be_nonaddressable_p (base
))
1630 /* Moreover, on strict alignment platforms, check that it is
1631 sufficiently aligned. */
1632 if (STRICT_ALIGNMENT
&& may_be_unaligned_p (base
, step
))
1635 base
= build_fold_addr_expr (base
);
1637 /* Substituting bases of IVs into the base expression might
1638 have caused folding opportunities. */
1639 if (TREE_CODE (base
) == ADDR_EXPR
)
1641 tree
*ref
= &TREE_OPERAND (base
, 0);
1642 while (handled_component_p (*ref
))
1643 ref
= &TREE_OPERAND (*ref
, 0);
1644 if (TREE_CODE (*ref
) == INDIRECT_REF
)
1645 *ref
= fold_indirect_ref (*ref
);
1649 civ
= alloc_iv (base
, step
);
1650 record_use (data
, op_p
, civ
, stmt
, USE_ADDRESS
);
1654 for_each_index (op_p
, idx_record_use
, data
);
1657 /* Finds and records invariants used in STMT. */
1660 find_invariants_stmt (struct ivopts_data
*data
, tree stmt
)
1663 use_operand_p use_p
;
1666 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1668 op
= USE_FROM_PTR (use_p
);
1669 record_invariant (data
, op
, false);
1673 /* Finds interesting uses of induction variables in the statement STMT. */
1676 find_interesting_uses_stmt (struct ivopts_data
*data
, tree stmt
)
1681 use_operand_p use_p
;
1683 find_invariants_stmt (data
, stmt
);
1685 if (TREE_CODE (stmt
) == COND_EXPR
)
1687 find_interesting_uses_cond (data
, stmt
, &COND_EXPR_COND (stmt
));
1691 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
1693 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
1694 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1696 if (TREE_CODE (lhs
) == SSA_NAME
)
1698 /* If the statement defines an induction variable, the uses are not
1699 interesting by themselves. */
1701 iv
= get_iv (data
, lhs
);
1703 if (iv
&& !integer_zerop (iv
->step
))
1707 switch (TREE_CODE_CLASS (TREE_CODE (rhs
)))
1709 case tcc_comparison
:
1710 find_interesting_uses_cond (data
, stmt
,
1711 &GIMPLE_STMT_OPERAND (stmt
, 1));
1715 find_interesting_uses_address (data
, stmt
,
1716 &GIMPLE_STMT_OPERAND (stmt
, 1));
1717 if (REFERENCE_CLASS_P (lhs
))
1718 find_interesting_uses_address (data
, stmt
,
1719 &GIMPLE_STMT_OPERAND (stmt
, 0));
1725 if (REFERENCE_CLASS_P (lhs
)
1726 && is_gimple_val (rhs
))
1728 find_interesting_uses_address (data
, stmt
,
1729 &GIMPLE_STMT_OPERAND (stmt
, 0));
1730 find_interesting_uses_op (data
, rhs
);
1734 /* TODO -- we should also handle address uses of type
1736 memory = call (whatever);
1743 if (TREE_CODE (stmt
) == PHI_NODE
1744 && bb_for_stmt (stmt
) == data
->current_loop
->header
)
1746 lhs
= PHI_RESULT (stmt
);
1747 iv
= get_iv (data
, lhs
);
1749 if (iv
&& !integer_zerop (iv
->step
))
1753 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1755 op
= USE_FROM_PTR (use_p
);
1757 if (TREE_CODE (op
) != SSA_NAME
)
1760 iv
= get_iv (data
, op
);
1764 find_interesting_uses_op (data
, op
);
1768 /* Finds interesting uses of induction variables outside of loops
1769 on loop exit edge EXIT. */
1772 find_interesting_uses_outside (struct ivopts_data
*data
, edge exit
)
1776 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= PHI_CHAIN (phi
))
1778 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1779 if (is_gimple_reg (def
))
1780 find_interesting_uses_op (data
, def
);
1784 /* Finds uses of the induction variables that are interesting. */
1787 find_interesting_uses (struct ivopts_data
*data
)
1790 block_stmt_iterator bsi
;
1792 basic_block
*body
= get_loop_body (data
->current_loop
);
1794 struct version_info
*info
;
1797 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1798 fprintf (dump_file
, "Uses:\n\n");
1800 for (i
= 0; i
< data
->current_loop
->num_nodes
; i
++)
1805 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1806 if (e
->dest
!= EXIT_BLOCK_PTR
1807 && !flow_bb_inside_loop_p (data
->current_loop
, e
->dest
))
1808 find_interesting_uses_outside (data
, e
);
1810 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1811 find_interesting_uses_stmt (data
, phi
);
1812 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1813 find_interesting_uses_stmt (data
, bsi_stmt (bsi
));
1816 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1820 fprintf (dump_file
, "\n");
1822 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1824 info
= ver_info (data
, i
);
1827 fprintf (dump_file
, " ");
1828 print_generic_expr (dump_file
, info
->name
, TDF_SLIM
);
1829 fprintf (dump_file
, " is invariant (%d)%s\n",
1830 info
->inv_id
, info
->has_nonlin_use
? "" : ", eliminable");
1834 fprintf (dump_file
, "\n");
1840 /* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
1841 is true, assume we are inside an address. If TOP_COMPREF is true, assume
1842 we are at the top-level of the processed address. */
1845 strip_offset_1 (tree expr
, bool inside_addr
, bool top_compref
,
1846 unsigned HOST_WIDE_INT
*offset
)
1848 tree op0
= NULL_TREE
, op1
= NULL_TREE
, tmp
, step
;
1849 enum tree_code code
;
1850 tree type
, orig_type
= TREE_TYPE (expr
);
1851 unsigned HOST_WIDE_INT off0
, off1
, st
;
1852 tree orig_expr
= expr
;
1856 type
= TREE_TYPE (expr
);
1857 code
= TREE_CODE (expr
);
1863 if (!cst_and_fits_in_hwi (expr
)
1864 || integer_zerop (expr
))
1867 *offset
= int_cst_value (expr
);
1868 return build_int_cst (orig_type
, 0);
1870 case POINTER_PLUS_EXPR
:
1873 op0
= TREE_OPERAND (expr
, 0);
1874 op1
= TREE_OPERAND (expr
, 1);
1876 op0
= strip_offset_1 (op0
, false, false, &off0
);
1877 op1
= strip_offset_1 (op1
, false, false, &off1
);
1879 *offset
= (code
== MINUS_EXPR
? off0
- off1
: off0
+ off1
);
1880 if (op0
== TREE_OPERAND (expr
, 0)
1881 && op1
== TREE_OPERAND (expr
, 1))
1884 if (integer_zerop (op1
))
1886 else if (integer_zerop (op0
))
1888 if (code
== MINUS_EXPR
)
1889 expr
= fold_build1 (NEGATE_EXPR
, type
, op1
);
1894 expr
= fold_build2 (code
, type
, op0
, op1
);
1896 return fold_convert (orig_type
, expr
);
1902 step
= array_ref_element_size (expr
);
1903 if (!cst_and_fits_in_hwi (step
))
1906 st
= int_cst_value (step
);
1907 op1
= TREE_OPERAND (expr
, 1);
1908 op1
= strip_offset_1 (op1
, false, false, &off1
);
1909 *offset
= off1
* st
;
1912 && integer_zerop (op1
))
1914 /* Strip the component reference completely. */
1915 op0
= TREE_OPERAND (expr
, 0);
1916 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
1926 tmp
= component_ref_field_offset (expr
);
1928 && cst_and_fits_in_hwi (tmp
))
1930 /* Strip the component reference completely. */
1931 op0
= TREE_OPERAND (expr
, 0);
1932 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
1933 *offset
= off0
+ int_cst_value (tmp
);
1939 op0
= TREE_OPERAND (expr
, 0);
1940 op0
= strip_offset_1 (op0
, true, true, &off0
);
1943 if (op0
== TREE_OPERAND (expr
, 0))
1946 expr
= build_fold_addr_expr (op0
);
1947 return fold_convert (orig_type
, expr
);
1950 inside_addr
= false;
1957 /* Default handling of expressions for that we want to recurse into
1958 the first operand. */
1959 op0
= TREE_OPERAND (expr
, 0);
1960 op0
= strip_offset_1 (op0
, inside_addr
, false, &off0
);
1963 if (op0
== TREE_OPERAND (expr
, 0)
1964 && (!op1
|| op1
== TREE_OPERAND (expr
, 1)))
1967 expr
= copy_node (expr
);
1968 TREE_OPERAND (expr
, 0) = op0
;
1970 TREE_OPERAND (expr
, 1) = op1
;
1972 /* Inside address, we might strip the top level component references,
1973 thus changing type of the expression. Handling of ADDR_EXPR
1975 expr
= fold_convert (orig_type
, expr
);
1980 /* Strips constant offsets from EXPR and stores them to OFFSET. */
1983 strip_offset (tree expr
, unsigned HOST_WIDE_INT
*offset
)
1985 return strip_offset_1 (expr
, false, false, offset
);
1988 /* Returns variant of TYPE that can be used as base for different uses.
1989 We return unsigned type with the same precision, which avoids problems
1993 generic_type_for (tree type
)
1995 if (POINTER_TYPE_P (type
))
1996 return unsigned_type_for (type
);
1998 if (TYPE_UNSIGNED (type
))
2001 return unsigned_type_for (type
);
2004 /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
2005 the bitmap to that we should store it. */
2007 static struct ivopts_data
*fd_ivopts_data
;
2009 find_depends (tree
*expr_p
, int *ws ATTRIBUTE_UNUSED
, void *data
)
2011 bitmap
*depends_on
= (bitmap
*) data
;
2012 struct version_info
*info
;
2014 if (TREE_CODE (*expr_p
) != SSA_NAME
)
2016 info
= name_info (fd_ivopts_data
, *expr_p
);
2018 if (!info
->inv_id
|| info
->has_nonlin_use
)
2022 *depends_on
= BITMAP_ALLOC (NULL
);
2023 bitmap_set_bit (*depends_on
, info
->inv_id
);
2028 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2029 position to POS. If USE is not NULL, the candidate is set as related to
2030 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
2031 replacement of the final value of the iv by a direct computation. */
2033 static struct iv_cand
*
2034 add_candidate_1 (struct ivopts_data
*data
,
2035 tree base
, tree step
, bool important
, enum iv_position pos
,
2036 struct iv_use
*use
, tree incremented_at
)
2039 struct iv_cand
*cand
= NULL
;
2040 tree type
, orig_type
;
2044 orig_type
= TREE_TYPE (base
);
2045 type
= generic_type_for (orig_type
);
2046 /* Don't convert the base to the generic type for pointers as the generic
2047 type is an integer type with the same size as the pointer type. */
2048 if (type
!= orig_type
&& !POINTER_TYPE_P (orig_type
))
2050 base
= fold_convert (type
, base
);
2051 step
= fold_convert (type
, step
);
2055 for (i
= 0; i
< n_iv_cands (data
); i
++)
2057 cand
= iv_cand (data
, i
);
2059 if (cand
->pos
!= pos
)
2062 if (cand
->incremented_at
!= incremented_at
)
2076 if (operand_equal_p (base
, cand
->iv
->base
, 0)
2077 && operand_equal_p (step
, cand
->iv
->step
, 0))
2081 if (i
== n_iv_cands (data
))
2083 cand
= XCNEW (struct iv_cand
);
2089 cand
->iv
= alloc_iv (base
, step
);
2092 if (pos
!= IP_ORIGINAL
&& cand
->iv
)
2094 cand
->var_before
= create_tmp_var_raw (TREE_TYPE (base
), "ivtmp");
2095 cand
->var_after
= cand
->var_before
;
2097 cand
->important
= important
;
2098 cand
->incremented_at
= incremented_at
;
2099 VEC_safe_push (iv_cand_p
, heap
, data
->iv_candidates
, cand
);
2102 && TREE_CODE (step
) != INTEGER_CST
)
2104 fd_ivopts_data
= data
;
2105 walk_tree (&step
, find_depends
, &cand
->depends_on
, NULL
);
2108 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2109 dump_cand (dump_file
, cand
);
2112 if (important
&& !cand
->important
)
2114 cand
->important
= true;
2115 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2116 fprintf (dump_file
, "Candidate %d is important\n", cand
->id
);
2121 bitmap_set_bit (use
->related_cands
, i
);
2122 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2123 fprintf (dump_file
, "Candidate %d is related to use %d\n",
2130 /* Returns true if incrementing the induction variable at the end of the LOOP
2133 The purpose is to avoid splitting latch edge with a biv increment, thus
2134 creating a jump, possibly confusing other optimization passes and leaving
2135 less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS
2136 is not available (so we do not have a better alternative), or if the latch
2137 edge is already nonempty. */
2140 allow_ip_end_pos_p (struct loop
*loop
)
2142 if (!ip_normal_pos (loop
))
2145 if (!empty_block_p (ip_end_pos (loop
)))
2151 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2152 position to POS. If USE is not NULL, the candidate is set as related to
2153 it. The candidate computation is scheduled on all available positions. */
2156 add_candidate (struct ivopts_data
*data
,
2157 tree base
, tree step
, bool important
, struct iv_use
*use
)
2159 if (ip_normal_pos (data
->current_loop
))
2160 add_candidate_1 (data
, base
, step
, important
, IP_NORMAL
, use
, NULL_TREE
);
2161 if (ip_end_pos (data
->current_loop
)
2162 && allow_ip_end_pos_p (data
->current_loop
))
2163 add_candidate_1 (data
, base
, step
, important
, IP_END
, use
, NULL_TREE
);
2166 /* Add a standard "0 + 1 * iteration" iv candidate for a
2167 type with SIZE bits. */
2170 add_standard_iv_candidates_for_size (struct ivopts_data
*data
,
2173 tree type
= lang_hooks
.types
.type_for_size (size
, true);
2174 add_candidate (data
, build_int_cst (type
, 0), build_int_cst (type
, 1),
2178 /* Adds standard iv candidates. */
2181 add_standard_iv_candidates (struct ivopts_data
*data
)
2183 add_standard_iv_candidates_for_size (data
, INT_TYPE_SIZE
);
2185 /* The same for a double-integer type if it is still fast enough. */
2186 if (BITS_PER_WORD
>= INT_TYPE_SIZE
* 2)
2187 add_standard_iv_candidates_for_size (data
, INT_TYPE_SIZE
* 2);
2191 /* Adds candidates bases on the old induction variable IV. */
2194 add_old_iv_candidates (struct ivopts_data
*data
, struct iv
*iv
)
2197 struct iv_cand
*cand
;
2199 add_candidate (data
, iv
->base
, iv
->step
, true, NULL
);
2201 /* The same, but with initial value zero. */
2202 add_candidate (data
,
2203 build_int_cst (TREE_TYPE (iv
->base
), 0),
2204 iv
->step
, true, NULL
);
2206 phi
= SSA_NAME_DEF_STMT (iv
->ssa_name
);
2207 if (TREE_CODE (phi
) == PHI_NODE
)
2209 /* Additionally record the possibility of leaving the original iv
2211 def
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (data
->current_loop
));
2212 cand
= add_candidate_1 (data
,
2213 iv
->base
, iv
->step
, true, IP_ORIGINAL
, NULL
,
2214 SSA_NAME_DEF_STMT (def
));
2215 cand
->var_before
= iv
->ssa_name
;
2216 cand
->var_after
= def
;
2220 /* Adds candidates based on the old induction variables. */
2223 add_old_ivs_candidates (struct ivopts_data
*data
)
2229 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
2231 iv
= ver_info (data
, i
)->iv
;
2232 if (iv
&& iv
->biv_p
&& !integer_zerop (iv
->step
))
2233 add_old_iv_candidates (data
, iv
);
2237 /* Adds candidates based on the value of the induction variable IV and USE. */
2240 add_iv_value_candidates (struct ivopts_data
*data
,
2241 struct iv
*iv
, struct iv_use
*use
)
2243 unsigned HOST_WIDE_INT offset
;
2247 add_candidate (data
, iv
->base
, iv
->step
, false, use
);
2249 /* The same, but with initial value zero. Make such variable important,
2250 since it is generic enough so that possibly many uses may be based
2252 basetype
= TREE_TYPE (iv
->base
);
2253 if (POINTER_TYPE_P (basetype
))
2254 basetype
= sizetype
;
2255 add_candidate (data
, build_int_cst (basetype
, 0),
2256 iv
->step
, true, use
);
2258 /* Third, try removing the constant offset. */
2259 base
= strip_offset (iv
->base
, &offset
);
2261 add_candidate (data
, base
, iv
->step
, false, use
);
2264 /* Adds candidates based on the uses. */
2267 add_derived_ivs_candidates (struct ivopts_data
*data
)
2271 for (i
= 0; i
< n_iv_uses (data
); i
++)
2273 struct iv_use
*use
= iv_use (data
, i
);
2280 case USE_NONLINEAR_EXPR
:
2283 /* Just add the ivs based on the value of the iv used here. */
2284 add_iv_value_candidates (data
, use
->iv
, use
);
2293 /* Record important candidates and add them to related_cands bitmaps
2297 record_important_candidates (struct ivopts_data
*data
)
2302 for (i
= 0; i
< n_iv_cands (data
); i
++)
2304 struct iv_cand
*cand
= iv_cand (data
, i
);
2306 if (cand
->important
)
2307 bitmap_set_bit (data
->important_candidates
, i
);
2310 data
->consider_all_candidates
= (n_iv_cands (data
)
2311 <= CONSIDER_ALL_CANDIDATES_BOUND
);
2313 if (data
->consider_all_candidates
)
2315 /* We will not need "related_cands" bitmaps in this case,
2316 so release them to decrease peak memory consumption. */
2317 for (i
= 0; i
< n_iv_uses (data
); i
++)
2319 use
= iv_use (data
, i
);
2320 BITMAP_FREE (use
->related_cands
);
2325 /* Add important candidates to the related_cands bitmaps. */
2326 for (i
= 0; i
< n_iv_uses (data
); i
++)
2327 bitmap_ior_into (iv_use (data
, i
)->related_cands
,
2328 data
->important_candidates
);
2332 /* Finds the candidates for the induction variables. */
2335 find_iv_candidates (struct ivopts_data
*data
)
2337 /* Add commonly used ivs. */
2338 add_standard_iv_candidates (data
);
2340 /* Add old induction variables. */
2341 add_old_ivs_candidates (data
);
2343 /* Add induction variables derived from uses. */
2344 add_derived_ivs_candidates (data
);
2346 /* Record the important candidates. */
2347 record_important_candidates (data
);
2350 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
2351 If consider_all_candidates is true, we use a two-dimensional array, otherwise
2352 we allocate a simple list to every use. */
2355 alloc_use_cost_map (struct ivopts_data
*data
)
2357 unsigned i
, size
, s
, j
;
2359 for (i
= 0; i
< n_iv_uses (data
); i
++)
2361 struct iv_use
*use
= iv_use (data
, i
);
2364 if (data
->consider_all_candidates
)
2365 size
= n_iv_cands (data
);
2369 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, j
, bi
)
2374 /* Round up to the power of two, so that moduling by it is fast. */
2375 for (size
= 1; size
< s
; size
<<= 1)
2379 use
->n_map_members
= size
;
2380 use
->cost_map
= XCNEWVEC (struct cost_pair
, size
);
2384 /* Returns description of computation cost of expression whose runtime
2385 cost is RUNTIME and complexity corresponds to COMPLEXITY. */
2388 new_cost (unsigned runtime
, unsigned complexity
)
2392 cost
.cost
= runtime
;
2393 cost
.complexity
= complexity
;
2398 /* Adds costs COST1 and COST2. */
2401 add_costs (comp_cost cost1
, comp_cost cost2
)
2403 cost1
.cost
+= cost2
.cost
;
2404 cost1
.complexity
+= cost2
.complexity
;
2408 /* Subtracts costs COST1 and COST2. */
2411 sub_costs (comp_cost cost1
, comp_cost cost2
)
2413 cost1
.cost
-= cost2
.cost
;
2414 cost1
.complexity
-= cost2
.complexity
;
2419 /* Returns a negative number if COST1 < COST2, a positive number if
2420 COST1 > COST2, and 0 if COST1 = COST2. */
2423 compare_costs (comp_cost cost1
, comp_cost cost2
)
2425 if (cost1
.cost
== cost2
.cost
)
2426 return cost1
.complexity
- cost2
.complexity
;
2428 return cost1
.cost
- cost2
.cost
;
2431 /* Returns true if COST is infinite. */
2434 infinite_cost_p (comp_cost cost
)
2436 return cost
.cost
== INFTY
;
2439 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
2440 on invariants DEPENDS_ON and that the value used in expressing it
2444 set_use_iv_cost (struct ivopts_data
*data
,
2445 struct iv_use
*use
, struct iv_cand
*cand
,
2446 comp_cost cost
, bitmap depends_on
, tree value
)
2450 if (infinite_cost_p (cost
))
2452 BITMAP_FREE (depends_on
);
2456 if (data
->consider_all_candidates
)
2458 use
->cost_map
[cand
->id
].cand
= cand
;
2459 use
->cost_map
[cand
->id
].cost
= cost
;
2460 use
->cost_map
[cand
->id
].depends_on
= depends_on
;
2461 use
->cost_map
[cand
->id
].value
= value
;
2465 /* n_map_members is a power of two, so this computes modulo. */
2466 s
= cand
->id
& (use
->n_map_members
- 1);
2467 for (i
= s
; i
< use
->n_map_members
; i
++)
2468 if (!use
->cost_map
[i
].cand
)
2470 for (i
= 0; i
< s
; i
++)
2471 if (!use
->cost_map
[i
].cand
)
2477 use
->cost_map
[i
].cand
= cand
;
2478 use
->cost_map
[i
].cost
= cost
;
2479 use
->cost_map
[i
].depends_on
= depends_on
;
2480 use
->cost_map
[i
].value
= value
;
2483 /* Gets cost of (USE, CANDIDATE) pair. */
2485 static struct cost_pair
*
2486 get_use_iv_cost (struct ivopts_data
*data
, struct iv_use
*use
,
2487 struct iv_cand
*cand
)
2490 struct cost_pair
*ret
;
2495 if (data
->consider_all_candidates
)
2497 ret
= use
->cost_map
+ cand
->id
;
2504 /* n_map_members is a power of two, so this computes modulo. */
2505 s
= cand
->id
& (use
->n_map_members
- 1);
2506 for (i
= s
; i
< use
->n_map_members
; i
++)
2507 if (use
->cost_map
[i
].cand
== cand
)
2508 return use
->cost_map
+ i
;
2510 for (i
= 0; i
< s
; i
++)
2511 if (use
->cost_map
[i
].cand
== cand
)
2512 return use
->cost_map
+ i
;
2517 /* Returns estimate on cost of computing SEQ. */
2525 for (; seq
; seq
= NEXT_INSN (seq
))
2527 set
= single_set (seq
);
2529 cost
+= rtx_cost (set
, SET
);
2537 /* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
2539 produce_memory_decl_rtl (tree obj
, int *regno
)
2544 if (TREE_STATIC (obj
) || DECL_EXTERNAL (obj
))
2546 const char *name
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj
));
2547 x
= gen_rtx_SYMBOL_REF (Pmode
, name
);
2548 SET_SYMBOL_REF_DECL (x
, obj
);
2549 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
2550 targetm
.encode_section_info (obj
, x
, true);
2554 x
= gen_raw_REG (Pmode
, (*regno
)++);
2555 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
2561 /* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
2562 walk_tree. DATA contains the actual fake register number. */
2565 prepare_decl_rtl (tree
*expr_p
, int *ws
, void *data
)
2567 tree obj
= NULL_TREE
;
2569 int *regno
= (int *) data
;
2571 switch (TREE_CODE (*expr_p
))
2574 for (expr_p
= &TREE_OPERAND (*expr_p
, 0);
2575 handled_component_p (*expr_p
);
2576 expr_p
= &TREE_OPERAND (*expr_p
, 0))
2579 if (DECL_P (obj
) && !DECL_RTL_SET_P (obj
))
2580 x
= produce_memory_decl_rtl (obj
, regno
);
2585 obj
= SSA_NAME_VAR (*expr_p
);
2586 if (!DECL_RTL_SET_P (obj
))
2587 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2596 if (DECL_RTL_SET_P (obj
))
2599 if (DECL_MODE (obj
) == BLKmode
)
2600 x
= produce_memory_decl_rtl (obj
, regno
);
2602 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2612 VEC_safe_push (tree
, heap
, decl_rtl_to_reset
, obj
);
2613 SET_DECL_RTL (obj
, x
);
2619 /* Determines cost of the computation of EXPR. */
2622 computation_cost (tree expr
)
2625 tree type
= TREE_TYPE (expr
);
2627 /* Avoid using hard regs in ways which may be unsupported. */
2628 int regno
= LAST_VIRTUAL_REGISTER
+ 1;
2630 walk_tree (&expr
, prepare_decl_rtl
, ®no
, NULL
);
2632 rslt
= expand_expr (expr
, NULL_RTX
, TYPE_MODE (type
), EXPAND_NORMAL
);
2636 cost
= seq_cost (seq
);
2638 cost
+= address_cost (XEXP (rslt
, 0), TYPE_MODE (type
));
2643 /* Returns variable containing the value of candidate CAND at statement AT. */
2646 var_at_stmt (struct loop
*loop
, struct iv_cand
*cand
, tree stmt
)
2648 if (stmt_after_increment (loop
, cand
, stmt
))
2649 return cand
->var_after
;
2651 return cand
->var_before
;
2654 /* Return the most significant (sign) bit of T. Similar to tree_int_cst_msb,
2655 but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE. */
2658 tree_int_cst_sign_bit (const_tree t
)
2660 unsigned bitno
= TYPE_PRECISION (TREE_TYPE (t
)) - 1;
2661 unsigned HOST_WIDE_INT w
;
2663 if (bitno
< HOST_BITS_PER_WIDE_INT
)
2664 w
= TREE_INT_CST_LOW (t
);
2667 w
= TREE_INT_CST_HIGH (t
);
2668 bitno
-= HOST_BITS_PER_WIDE_INT
;
2671 return (w
>> bitno
) & 1;
2674 /* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
2675 same precision that is at least as wide as the precision of TYPE, stores
2676 BA to A and BB to B, and returns the type of BA. Otherwise, returns the
2680 determine_common_wider_type (tree
*a
, tree
*b
)
2682 tree wider_type
= NULL
;
2684 tree atype
= TREE_TYPE (*a
);
2686 if (CONVERT_EXPR_P (*a
))
2688 suba
= TREE_OPERAND (*a
, 0);
2689 wider_type
= TREE_TYPE (suba
);
2690 if (TYPE_PRECISION (wider_type
) < TYPE_PRECISION (atype
))
2696 if (CONVERT_EXPR_P (*b
))
2698 subb
= TREE_OPERAND (*b
, 0);
2699 if (TYPE_PRECISION (wider_type
) != TYPE_PRECISION (TREE_TYPE (subb
)))
2710 /* Determines the expression by that USE is expressed from induction variable
2711 CAND at statement AT in LOOP. The expression is stored in a decomposed
2712 form into AFF. Returns false if USE cannot be expressed using CAND. */
2715 get_computation_aff (struct loop
*loop
,
2716 struct iv_use
*use
, struct iv_cand
*cand
, tree at
,
2717 struct affine_tree_combination
*aff
)
2719 tree ubase
= use
->iv
->base
;
2720 tree ustep
= use
->iv
->step
;
2721 tree cbase
= cand
->iv
->base
;
2722 tree cstep
= cand
->iv
->step
, cstep_common
;
2723 tree utype
= TREE_TYPE (ubase
), ctype
= TREE_TYPE (cbase
);
2724 tree common_type
, var
;
2726 aff_tree cbase_aff
, var_aff
;
2729 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
2731 /* We do not have a precision to express the values of use. */
2735 var
= var_at_stmt (loop
, cand
, at
);
2736 uutype
= unsigned_type_for (utype
);
2738 /* If the conversion is not noop, perform it. */
2739 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
2741 cstep
= fold_convert (uutype
, cstep
);
2742 cbase
= fold_convert (uutype
, cbase
);
2743 var
= fold_convert (uutype
, var
);
2746 if (!constant_multiple_of (ustep
, cstep
, &rat
))
2749 /* In case both UBASE and CBASE are shortened to UUTYPE from some common
2750 type, we achieve better folding by computing their difference in this
2751 wider type, and cast the result to UUTYPE. We do not need to worry about
2752 overflows, as all the arithmetics will in the end be performed in UUTYPE
2754 common_type
= determine_common_wider_type (&ubase
, &cbase
);
2756 /* use = ubase - ratio * cbase + ratio * var. */
2757 tree_to_aff_combination (ubase
, common_type
, aff
);
2758 tree_to_aff_combination (cbase
, common_type
, &cbase_aff
);
2759 tree_to_aff_combination (var
, uutype
, &var_aff
);
2761 /* We need to shift the value if we are after the increment. */
2762 if (stmt_after_increment (loop
, cand
, at
))
2766 if (common_type
!= uutype
)
2767 cstep_common
= fold_convert (common_type
, cstep
);
2769 cstep_common
= cstep
;
2771 tree_to_aff_combination (cstep_common
, common_type
, &cstep_aff
);
2772 aff_combination_add (&cbase_aff
, &cstep_aff
);
2775 aff_combination_scale (&cbase_aff
, double_int_neg (rat
));
2776 aff_combination_add (aff
, &cbase_aff
);
2777 if (common_type
!= uutype
)
2778 aff_combination_convert (aff
, uutype
);
2780 aff_combination_scale (&var_aff
, rat
);
2781 aff_combination_add (aff
, &var_aff
);
2786 /* Determines the expression by that USE is expressed from induction variable
2787 CAND at statement AT in LOOP. The computation is unshared. */
2790 get_computation_at (struct loop
*loop
,
2791 struct iv_use
*use
, struct iv_cand
*cand
, tree at
)
2794 tree type
= TREE_TYPE (use
->iv
->base
);
2796 if (!get_computation_aff (loop
, use
, cand
, at
, &aff
))
2798 unshare_aff_combination (&aff
);
2799 return fold_convert (type
, aff_combination_to_tree (&aff
));
2802 /* Determines the expression by that USE is expressed from induction variable
2803 CAND in LOOP. The computation is unshared. */
2806 get_computation (struct loop
*loop
, struct iv_use
*use
, struct iv_cand
*cand
)
2808 return get_computation_at (loop
, use
, cand
, use
->stmt
);
2811 /* Returns cost of addition in MODE. */
2814 add_cost (enum machine_mode mode
)
2816 static unsigned costs
[NUM_MACHINE_MODES
];
2824 force_operand (gen_rtx_fmt_ee (PLUS
, mode
,
2825 gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 1),
2826 gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 2)),
2831 cost
= seq_cost (seq
);
2837 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2838 fprintf (dump_file
, "Addition in %s costs %d\n",
2839 GET_MODE_NAME (mode
), cost
);
2843 /* Entry in a hashtable of already known costs for multiplication. */
2846 HOST_WIDE_INT cst
; /* The constant to multiply by. */
2847 enum machine_mode mode
; /* In mode. */
2848 unsigned cost
; /* The cost. */
2851 /* Counts hash value for the ENTRY. */
2854 mbc_entry_hash (const void *entry
)
2856 const struct mbc_entry
*e
= (const struct mbc_entry
*) entry
;
2858 return 57 * (hashval_t
) e
->mode
+ (hashval_t
) (e
->cst
% 877);
2861 /* Compares the hash table entries ENTRY1 and ENTRY2. */
2864 mbc_entry_eq (const void *entry1
, const void *entry2
)
2866 const struct mbc_entry
*e1
= (const struct mbc_entry
*) entry1
;
2867 const struct mbc_entry
*e2
= (const struct mbc_entry
*) entry2
;
2869 return (e1
->mode
== e2
->mode
2870 && e1
->cst
== e2
->cst
);
2873 /* Returns cost of multiplication by constant CST in MODE. */
2876 multiply_by_cost (HOST_WIDE_INT cst
, enum machine_mode mode
)
2878 static htab_t costs
;
2879 struct mbc_entry
**cached
, act
;
2884 costs
= htab_create (100, mbc_entry_hash
, mbc_entry_eq
, free
);
2888 cached
= (struct mbc_entry
**) htab_find_slot (costs
, &act
, INSERT
);
2890 return (*cached
)->cost
;
2892 *cached
= XNEW (struct mbc_entry
);
2893 (*cached
)->mode
= mode
;
2894 (*cached
)->cst
= cst
;
2897 expand_mult (mode
, gen_raw_REG (mode
, LAST_VIRTUAL_REGISTER
+ 1),
2898 gen_int_mode (cst
, mode
), NULL_RTX
, 0);
2902 cost
= seq_cost (seq
);
2904 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2905 fprintf (dump_file
, "Multiplication by %d in %s costs %d\n",
2906 (int) cst
, GET_MODE_NAME (mode
), cost
);
2908 (*cached
)->cost
= cost
;
2913 /* Returns true if multiplying by RATIO is allowed in an address. Test the
2914 validity for a memory reference accessing memory of mode MODE. */
2917 multiplier_allowed_in_address_p (HOST_WIDE_INT ratio
, enum machine_mode mode
)
2919 #define MAX_RATIO 128
2920 static sbitmap valid_mult
[MAX_MACHINE_MODE
];
2922 if (!valid_mult
[mode
])
2924 rtx reg1
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 1);
2928 valid_mult
[mode
] = sbitmap_alloc (2 * MAX_RATIO
+ 1);
2929 sbitmap_zero (valid_mult
[mode
]);
2930 addr
= gen_rtx_fmt_ee (MULT
, Pmode
, reg1
, NULL_RTX
);
2931 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
2933 XEXP (addr
, 1) = gen_int_mode (i
, Pmode
);
2934 if (memory_address_p (mode
, addr
))
2935 SET_BIT (valid_mult
[mode
], i
+ MAX_RATIO
);
2938 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2940 fprintf (dump_file
, " allowed multipliers:");
2941 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
2942 if (TEST_BIT (valid_mult
[mode
], i
+ MAX_RATIO
))
2943 fprintf (dump_file
, " %d", (int) i
);
2944 fprintf (dump_file
, "\n");
2945 fprintf (dump_file
, "\n");
2949 if (ratio
> MAX_RATIO
|| ratio
< -MAX_RATIO
)
2952 return TEST_BIT (valid_mult
[mode
], ratio
+ MAX_RATIO
);
2955 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
2956 If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
2957 variable is omitted. Compute the cost for a memory reference that accesses
2958 a memory location of mode MEM_MODE.
2960 TODO -- there must be some better way. This all is quite crude. */
2963 get_address_cost (bool symbol_present
, bool var_present
,
2964 unsigned HOST_WIDE_INT offset
, HOST_WIDE_INT ratio
,
2965 enum machine_mode mem_mode
)
2967 static bool initialized
[MAX_MACHINE_MODE
];
2968 static HOST_WIDE_INT rat
[MAX_MACHINE_MODE
], off
[MAX_MACHINE_MODE
];
2969 static HOST_WIDE_INT min_offset
[MAX_MACHINE_MODE
], max_offset
[MAX_MACHINE_MODE
];
2970 static unsigned costs
[MAX_MACHINE_MODE
][2][2][2][2];
2971 unsigned cost
, acost
, complexity
;
2972 bool offset_p
, ratio_p
;
2973 HOST_WIDE_INT s_offset
;
2974 unsigned HOST_WIDE_INT mask
;
2977 if (!initialized
[mem_mode
])
2980 HOST_WIDE_INT start
= BIGGEST_ALIGNMENT
/ BITS_PER_UNIT
;
2981 int old_cse_not_expected
;
2982 unsigned sym_p
, var_p
, off_p
, rat_p
, add_c
;
2983 rtx seq
, addr
, base
;
2986 initialized
[mem_mode
] = true;
2988 reg1
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 1);
2990 addr
= gen_rtx_fmt_ee (PLUS
, Pmode
, reg1
, NULL_RTX
);
2991 for (i
= start
; i
<= 1 << 20; i
<<= 1)
2993 XEXP (addr
, 1) = gen_int_mode (i
, Pmode
);
2994 if (!memory_address_p (mem_mode
, addr
))
2997 max_offset
[mem_mode
] = i
== start
? 0 : i
>> 1;
2998 off
[mem_mode
] = max_offset
[mem_mode
];
3000 for (i
= start
; i
<= 1 << 20; i
<<= 1)
3002 XEXP (addr
, 1) = gen_int_mode (-i
, Pmode
);
3003 if (!memory_address_p (mem_mode
, addr
))
3006 min_offset
[mem_mode
] = i
== start
? 0 : -(i
>> 1);
3008 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3010 fprintf (dump_file
, "get_address_cost:\n");
3011 fprintf (dump_file
, " min offset %s %d\n",
3012 GET_MODE_NAME (mem_mode
),
3013 (int) min_offset
[mem_mode
]);
3014 fprintf (dump_file
, " max offset %s %d\n",
3015 GET_MODE_NAME (mem_mode
),
3016 (int) max_offset
[mem_mode
]);
3020 for (i
= 2; i
<= MAX_RATIO
; i
++)
3021 if (multiplier_allowed_in_address_p (i
, mem_mode
))
3027 /* Compute the cost of various addressing modes. */
3029 reg0
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 1);
3030 reg1
= gen_raw_REG (Pmode
, LAST_VIRTUAL_REGISTER
+ 2);
3032 for (i
= 0; i
< 16; i
++)
3035 var_p
= (i
>> 1) & 1;
3036 off_p
= (i
>> 2) & 1;
3037 rat_p
= (i
>> 3) & 1;
3041 addr
= gen_rtx_fmt_ee (MULT
, Pmode
, addr
,
3042 gen_int_mode (rat
[mem_mode
], Pmode
));
3045 addr
= gen_rtx_fmt_ee (PLUS
, Pmode
, addr
, reg1
);
3049 base
= gen_rtx_SYMBOL_REF (Pmode
, ggc_strdup (""));
3050 /* ??? We can run into trouble with some backends by presenting
3051 it with symbols which haven't been properly passed through
3052 targetm.encode_section_info. By setting the local bit, we
3053 enhance the probability of things working. */
3054 SYMBOL_REF_FLAGS (base
) = SYMBOL_FLAG_LOCAL
;
3057 base
= gen_rtx_fmt_e (CONST
, Pmode
,
3058 gen_rtx_fmt_ee (PLUS
, Pmode
,
3060 gen_int_mode (off
[mem_mode
],
3064 base
= gen_int_mode (off
[mem_mode
], Pmode
);
3069 addr
= gen_rtx_fmt_ee (PLUS
, Pmode
, addr
, base
);
3072 /* To avoid splitting addressing modes, pretend that no cse will
3074 old_cse_not_expected
= cse_not_expected
;
3075 cse_not_expected
= true;
3076 addr
= memory_address (mem_mode
, addr
);
3077 cse_not_expected
= old_cse_not_expected
;
3081 acost
= seq_cost (seq
);
3082 acost
+= address_cost (addr
, mem_mode
);
3086 costs
[mem_mode
][sym_p
][var_p
][off_p
][rat_p
] = acost
;
3089 /* On some targets, it is quite expensive to load symbol to a register,
3090 which makes addresses that contain symbols look much more expensive.
3091 However, the symbol will have to be loaded in any case before the
3092 loop (and quite likely we have it in register already), so it does not
3093 make much sense to penalize them too heavily. So make some final
3094 tweaks for the SYMBOL_PRESENT modes:
3096 If VAR_PRESENT is false, and the mode obtained by changing symbol to
3097 var is cheaper, use this mode with small penalty.
3098 If VAR_PRESENT is true, try whether the mode with
3099 SYMBOL_PRESENT = false is cheaper even with cost of addition, and
3100 if this is the case, use it. */
3101 add_c
= add_cost (Pmode
);
3102 for (i
= 0; i
< 8; i
++)
3105 off_p
= (i
>> 1) & 1;
3106 rat_p
= (i
>> 2) & 1;
3108 acost
= costs
[mem_mode
][0][1][off_p
][rat_p
] + 1;
3112 if (acost
< costs
[mem_mode
][1][var_p
][off_p
][rat_p
])
3113 costs
[mem_mode
][1][var_p
][off_p
][rat_p
] = acost
;
3116 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3118 fprintf (dump_file
, "Address costs:\n");
3120 for (i
= 0; i
< 16; i
++)
3123 var_p
= (i
>> 1) & 1;
3124 off_p
= (i
>> 2) & 1;
3125 rat_p
= (i
>> 3) & 1;
3127 fprintf (dump_file
, " ");
3129 fprintf (dump_file
, "sym + ");
3131 fprintf (dump_file
, "var + ");
3133 fprintf (dump_file
, "cst + ");
3135 fprintf (dump_file
, "rat * ");
3137 acost
= costs
[mem_mode
][sym_p
][var_p
][off_p
][rat_p
];
3138 fprintf (dump_file
, "index costs %d\n", acost
);
3140 fprintf (dump_file
, "\n");
3144 bits
= GET_MODE_BITSIZE (Pmode
);
3145 mask
= ~(~(unsigned HOST_WIDE_INT
) 0 << (bits
- 1) << 1);
3147 if ((offset
>> (bits
- 1) & 1))
3152 offset_p
= (s_offset
!= 0
3153 && min_offset
[mem_mode
] <= s_offset
3154 && s_offset
<= max_offset
[mem_mode
]);
3155 ratio_p
= (ratio
!= 1
3156 && multiplier_allowed_in_address_p (ratio
, mem_mode
));
3158 if (ratio
!= 1 && !ratio_p
)
3159 cost
+= multiply_by_cost (ratio
, Pmode
);
3161 if (s_offset
&& !offset_p
&& !symbol_present
)
3162 cost
+= add_cost (Pmode
);
3164 acost
= costs
[mem_mode
][symbol_present
][var_present
][offset_p
][ratio_p
];
3165 complexity
= (symbol_present
!= 0) + (var_present
!= 0) + offset_p
+ ratio_p
;
3166 return new_cost (cost
+ acost
, complexity
);
3169 /* Estimates cost of forcing expression EXPR into a variable. */
3172 force_expr_to_var_cost (tree expr
)
3174 static bool costs_initialized
= false;
3175 static unsigned integer_cost
;
3176 static unsigned symbol_cost
;
3177 static unsigned address_cost
;
3179 comp_cost cost0
, cost1
, cost
;
3180 enum machine_mode mode
;
3182 if (!costs_initialized
)
3184 tree type
= build_pointer_type (integer_type_node
);
3188 var
= create_tmp_var_raw (integer_type_node
, "test_var");
3189 TREE_STATIC (var
) = 1;
3190 x
= produce_memory_decl_rtl (var
, NULL
);
3191 SET_DECL_RTL (var
, x
);
3193 integer_cost
= computation_cost (build_int_cst (integer_type_node
,
3196 addr
= build1 (ADDR_EXPR
, type
, var
);
3197 symbol_cost
= computation_cost (addr
) + 1;
3200 = computation_cost (build2 (POINTER_PLUS_EXPR
, type
,
3202 build_int_cst (sizetype
, 2000))) + 1;
3203 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3205 fprintf (dump_file
, "force_expr_to_var_cost:\n");
3206 fprintf (dump_file
, " integer %d\n", (int) integer_cost
);
3207 fprintf (dump_file
, " symbol %d\n", (int) symbol_cost
);
3208 fprintf (dump_file
, " address %d\n", (int) address_cost
);
3209 fprintf (dump_file
, " other %d\n", (int) target_spill_cost
);
3210 fprintf (dump_file
, "\n");
3213 costs_initialized
= true;
3218 if (SSA_VAR_P (expr
))
3221 if (is_gimple_min_invariant (expr
))
3223 if (TREE_CODE (expr
) == INTEGER_CST
)
3224 return new_cost (integer_cost
, 0);
3226 if (TREE_CODE (expr
) == ADDR_EXPR
)
3228 tree obj
= TREE_OPERAND (expr
, 0);
3230 if (TREE_CODE (obj
) == VAR_DECL
3231 || TREE_CODE (obj
) == PARM_DECL
3232 || TREE_CODE (obj
) == RESULT_DECL
)
3233 return new_cost (symbol_cost
, 0);
3236 return new_cost (address_cost
, 0);
3239 switch (TREE_CODE (expr
))
3241 case POINTER_PLUS_EXPR
:
3245 op0
= TREE_OPERAND (expr
, 0);
3246 op1
= TREE_OPERAND (expr
, 1);
3250 if (is_gimple_val (op0
))
3253 cost0
= force_expr_to_var_cost (op0
);
3255 if (is_gimple_val (op1
))
3258 cost1
= force_expr_to_var_cost (op1
);
3263 /* Just an arbitrary value, FIXME. */
3264 return new_cost (target_spill_cost
, 0);
3267 mode
= TYPE_MODE (TREE_TYPE (expr
));
3268 switch (TREE_CODE (expr
))
3270 case POINTER_PLUS_EXPR
:
3273 cost
= new_cost (add_cost (mode
), 0);
3277 if (cst_and_fits_in_hwi (op0
))
3278 cost
= new_cost (multiply_by_cost (int_cst_value (op0
), mode
), 0);
3279 else if (cst_and_fits_in_hwi (op1
))
3280 cost
= new_cost (multiply_by_cost (int_cst_value (op1
), mode
), 0);
3282 return new_cost (target_spill_cost
, 0);
3289 cost
= add_costs (cost
, cost0
);
3290 cost
= add_costs (cost
, cost1
);
3292 /* Bound the cost by target_spill_cost. The parts of complicated
3293 computations often are either loop invariant or at least can
3294 be shared between several iv uses, so letting this grow without
3295 limits would not give reasonable results. */
3296 if (cost
.cost
> target_spill_cost
)
3297 cost
.cost
= target_spill_cost
;
3302 /* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
3303 invariants the computation depends on. */
3306 force_var_cost (struct ivopts_data
*data
,
3307 tree expr
, bitmap
*depends_on
)
3311 fd_ivopts_data
= data
;
3312 walk_tree (&expr
, find_depends
, depends_on
, NULL
);
3315 return force_expr_to_var_cost (expr
);
3318 /* Estimates cost of expressing address ADDR as var + symbol + offset. The
3319 value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
3320 to false if the corresponding part is missing. DEPENDS_ON is a set of the
3321 invariants the computation depends on. */
3324 split_address_cost (struct ivopts_data
*data
,
3325 tree addr
, bool *symbol_present
, bool *var_present
,
3326 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3329 HOST_WIDE_INT bitsize
;
3330 HOST_WIDE_INT bitpos
;
3332 enum machine_mode mode
;
3333 int unsignedp
, volatilep
;
3335 core
= get_inner_reference (addr
, &bitsize
, &bitpos
, &toffset
, &mode
,
3336 &unsignedp
, &volatilep
, false);
3339 || bitpos
% BITS_PER_UNIT
!= 0
3340 || TREE_CODE (core
) != VAR_DECL
)
3342 *symbol_present
= false;
3343 *var_present
= true;
3344 fd_ivopts_data
= data
;
3345 walk_tree (&addr
, find_depends
, depends_on
, NULL
);
3346 return new_cost (target_spill_cost
, 0);
3349 *offset
+= bitpos
/ BITS_PER_UNIT
;
3350 if (TREE_STATIC (core
)
3351 || DECL_EXTERNAL (core
))
3353 *symbol_present
= true;
3354 *var_present
= false;
3358 *symbol_present
= false;
3359 *var_present
= true;
3363 /* Estimates cost of expressing difference of addresses E1 - E2 as
3364 var + symbol + offset. The value of offset is added to OFFSET,
3365 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3366 part is missing. DEPENDS_ON is a set of the invariants the computation
3370 ptr_difference_cost (struct ivopts_data
*data
,
3371 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
3372 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3374 HOST_WIDE_INT diff
= 0;
3377 gcc_assert (TREE_CODE (e1
) == ADDR_EXPR
);
3379 if (ptr_difference_const (e1
, e2
, &diff
))
3382 *symbol_present
= false;
3383 *var_present
= false;
3387 if (integer_zerop (e2
))
3388 return split_address_cost (data
, TREE_OPERAND (e1
, 0),
3389 symbol_present
, var_present
, offset
, depends_on
);
3391 *symbol_present
= false;
3392 *var_present
= true;
3394 cost
= force_var_cost (data
, e1
, depends_on
);
3395 cost
= add_costs (cost
, force_var_cost (data
, e2
, depends_on
));
3396 cost
.cost
+= add_cost (Pmode
);
3401 /* Estimates cost of expressing difference E1 - E2 as
3402 var + symbol + offset. The value of offset is added to OFFSET,
3403 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3404 part is missing. DEPENDS_ON is a set of the invariants the computation
3408 difference_cost (struct ivopts_data
*data
,
3409 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
3410 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3413 enum machine_mode mode
= TYPE_MODE (TREE_TYPE (e1
));
3414 unsigned HOST_WIDE_INT off1
, off2
;
3416 e1
= strip_offset (e1
, &off1
);
3417 e2
= strip_offset (e2
, &off2
);
3418 *offset
+= off1
- off2
;
3423 if (TREE_CODE (e1
) == ADDR_EXPR
)
3424 return ptr_difference_cost (data
, e1
, e2
, symbol_present
, var_present
, offset
,
3426 *symbol_present
= false;
3428 if (operand_equal_p (e1
, e2
, 0))
3430 *var_present
= false;
3433 *var_present
= true;
3434 if (integer_zerop (e2
))
3435 return force_var_cost (data
, e1
, depends_on
);
3437 if (integer_zerop (e1
))
3439 cost
= force_var_cost (data
, e2
, depends_on
);
3440 cost
.cost
+= multiply_by_cost (-1, mode
);
3445 cost
= force_var_cost (data
, e1
, depends_on
);
3446 cost
= add_costs (cost
, force_var_cost (data
, e2
, depends_on
));
3447 cost
.cost
+= add_cost (mode
);
3452 /* Determines the cost of the computation by that USE is expressed
3453 from induction variable CAND. If ADDRESS_P is true, we just need
3454 to create an address from it, otherwise we want to get it into
3455 register. A set of invariants we depend on is stored in
3456 DEPENDS_ON. AT is the statement at that the value is computed. */
3459 get_computation_cost_at (struct ivopts_data
*data
,
3460 struct iv_use
*use
, struct iv_cand
*cand
,
3461 bool address_p
, bitmap
*depends_on
, tree at
)
3463 tree ubase
= use
->iv
->base
, ustep
= use
->iv
->step
;
3465 tree utype
= TREE_TYPE (ubase
), ctype
;
3466 unsigned HOST_WIDE_INT cstepi
, offset
= 0;
3467 HOST_WIDE_INT ratio
, aratio
;
3468 bool var_present
, symbol_present
;
3475 /* Only consider real candidates. */
3477 return infinite_cost
;
3479 cbase
= cand
->iv
->base
;
3480 cstep
= cand
->iv
->step
;
3481 ctype
= TREE_TYPE (cbase
);
3483 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
3485 /* We do not have a precision to express the values of use. */
3486 return infinite_cost
;
3491 /* Do not try to express address of an object with computation based
3492 on address of a different object. This may cause problems in rtl
3493 level alias analysis (that does not expect this to be happening,
3494 as this is illegal in C), and would be unlikely to be useful
3496 if (use
->iv
->base_object
3497 && cand
->iv
->base_object
3498 && !operand_equal_p (use
->iv
->base_object
, cand
->iv
->base_object
, 0))
3499 return infinite_cost
;
3502 if (TYPE_PRECISION (utype
) != TYPE_PRECISION (ctype
))
3504 /* TODO -- add direct handling of this case. */
3508 /* CSTEPI is removed from the offset in case statement is after the
3509 increment. If the step is not constant, we use zero instead.
3510 This is a bit imprecise (there is the extra addition), but
3511 redundancy elimination is likely to transform the code so that
3512 it uses value of the variable before increment anyway,
3513 so it is not that much unrealistic. */
3514 if (cst_and_fits_in_hwi (cstep
))
3515 cstepi
= int_cst_value (cstep
);
3519 if (!constant_multiple_of (ustep
, cstep
, &rat
))
3520 return infinite_cost
;
3522 if (double_int_fits_in_shwi_p (rat
))
3523 ratio
= double_int_to_shwi (rat
);
3525 return infinite_cost
;
3527 /* use = ubase + ratio * (var - cbase). If either cbase is a constant
3528 or ratio == 1, it is better to handle this like
3530 ubase - ratio * cbase + ratio * var
3532 (also holds in the case ratio == -1, TODO. */
3534 if (cst_and_fits_in_hwi (cbase
))
3536 offset
= - ratio
* int_cst_value (cbase
);
3537 cost
= difference_cost (data
,
3538 ubase
, build_int_cst (utype
, 0),
3539 &symbol_present
, &var_present
, &offset
,
3542 else if (ratio
== 1)
3544 cost
= difference_cost (data
,
3546 &symbol_present
, &var_present
, &offset
,
3551 cost
= force_var_cost (data
, cbase
, depends_on
);
3552 cost
.cost
+= add_cost (TYPE_MODE (ctype
));
3553 cost
= add_costs (cost
,
3554 difference_cost (data
,
3555 ubase
, build_int_cst (utype
, 0),
3556 &symbol_present
, &var_present
,
3557 &offset
, depends_on
));
3560 /* If we are after the increment, the value of the candidate is higher by
3562 if (stmt_after_increment (data
->current_loop
, cand
, at
))
3563 offset
-= ratio
* cstepi
;
3565 /* Now the computation is in shape symbol + var1 + const + ratio * var2.
3566 (symbol/var/const parts may be omitted). If we are looking for an address,
3567 find the cost of addressing this. */
3569 return add_costs (cost
, get_address_cost (symbol_present
, var_present
,
3571 TYPE_MODE (TREE_TYPE (*use
->op_p
))));
3573 /* Otherwise estimate the costs for computing the expression. */
3574 aratio
= ratio
> 0 ? ratio
: -ratio
;
3575 if (!symbol_present
&& !var_present
&& !offset
)
3578 cost
.cost
+= multiply_by_cost (ratio
, TYPE_MODE (ctype
));
3584 cost
.cost
+= multiply_by_cost (aratio
, TYPE_MODE (ctype
));
3588 /* Symbol + offset should be compile-time computable. */
3589 && (symbol_present
|| offset
))
3592 /* Having offset does not affect runtime cost in case it is added to
3593 symbol, but it increases complexity. */
3597 cost
.cost
+= n_sums
* add_cost (TYPE_MODE (ctype
));
3602 /* Just get the expression, expand it and measure the cost. */
3603 tree comp
= get_computation_at (data
->current_loop
, use
, cand
, at
);
3606 return infinite_cost
;
3609 comp
= build1 (INDIRECT_REF
, TREE_TYPE (TREE_TYPE (comp
)), comp
);
3611 return new_cost (computation_cost (comp
), 0);
3615 /* Determines the cost of the computation by that USE is expressed
3616 from induction variable CAND. If ADDRESS_P is true, we just need
3617 to create an address from it, otherwise we want to get it into
3618 register. A set of invariants we depend on is stored in
3622 get_computation_cost (struct ivopts_data
*data
,
3623 struct iv_use
*use
, struct iv_cand
*cand
,
3624 bool address_p
, bitmap
*depends_on
)
3626 return get_computation_cost_at (data
,
3627 use
, cand
, address_p
, depends_on
, use
->stmt
);
3630 /* Determines cost of basing replacement of USE on CAND in a generic
3634 determine_use_iv_cost_generic (struct ivopts_data
*data
,
3635 struct iv_use
*use
, struct iv_cand
*cand
)
3640 /* The simple case first -- if we need to express value of the preserved
3641 original biv, the cost is 0. This also prevents us from counting the
3642 cost of increment twice -- once at this use and once in the cost of
3644 if (cand
->pos
== IP_ORIGINAL
3645 && cand
->incremented_at
== use
->stmt
)
3647 set_use_iv_cost (data
, use
, cand
, zero_cost
, NULL
, NULL_TREE
);
3651 cost
= get_computation_cost (data
, use
, cand
, false, &depends_on
);
3652 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
);
3654 return !infinite_cost_p (cost
);
3657 /* Determines cost of basing replacement of USE on CAND in an address. */
3660 determine_use_iv_cost_address (struct ivopts_data
*data
,
3661 struct iv_use
*use
, struct iv_cand
*cand
)
3664 comp_cost cost
= get_computation_cost (data
, use
, cand
, true, &depends_on
);
3666 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
);
3668 return !infinite_cost_p (cost
);
3671 /* Computes value of candidate CAND at position AT in iteration NITER, and
3672 stores it to VAL. */
3675 cand_value_at (struct loop
*loop
, struct iv_cand
*cand
, tree at
, tree niter
,
3678 aff_tree step
, delta
, nit
;
3679 struct iv
*iv
= cand
->iv
;
3680 tree type
= TREE_TYPE (iv
->base
);
3681 tree steptype
= type
;
3682 if (POINTER_TYPE_P (type
))
3683 steptype
= sizetype
;
3685 tree_to_aff_combination (iv
->step
, steptype
, &step
);
3686 tree_to_aff_combination (niter
, TREE_TYPE (niter
), &nit
);
3687 aff_combination_convert (&nit
, steptype
);
3688 aff_combination_mult (&nit
, &step
, &delta
);
3689 if (stmt_after_increment (loop
, cand
, at
))
3690 aff_combination_add (&delta
, &step
);
3692 tree_to_aff_combination (iv
->base
, type
, val
);
3693 aff_combination_add (val
, &delta
);
3696 /* Returns period of induction variable iv. */
3699 iv_period (struct iv
*iv
)
3701 tree step
= iv
->step
, period
, type
;
3704 gcc_assert (step
&& TREE_CODE (step
) == INTEGER_CST
);
3706 /* Period of the iv is gcd (step, type range). Since type range is power
3707 of two, it suffices to determine the maximum power of two that divides
3709 pow2div
= num_ending_zeros (step
);
3710 type
= unsigned_type_for (TREE_TYPE (step
));
3712 period
= build_low_bits_mask (type
,
3713 (TYPE_PRECISION (type
)
3714 - tree_low_cst (pow2div
, 1)));
3719 /* Returns the comparison operator used when eliminating the iv USE. */
3721 static enum tree_code
3722 iv_elimination_compare (struct ivopts_data
*data
, struct iv_use
*use
)
3724 struct loop
*loop
= data
->current_loop
;
3728 ex_bb
= bb_for_stmt (use
->stmt
);
3729 exit
= EDGE_SUCC (ex_bb
, 0);
3730 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
3731 exit
= EDGE_SUCC (ex_bb
, 1);
3733 return (exit
->flags
& EDGE_TRUE_VALUE
? EQ_EXPR
: NE_EXPR
);
3736 /* Check whether it is possible to express the condition in USE by comparison
3737 of candidate CAND. If so, store the value compared with to BOUND. */
3740 may_eliminate_iv (struct ivopts_data
*data
,
3741 struct iv_use
*use
, struct iv_cand
*cand
, tree
*bound
)
3746 struct loop
*loop
= data
->current_loop
;
3749 if (TREE_CODE (cand
->iv
->step
) != INTEGER_CST
)
3752 /* For now works only for exits that dominate the loop latch.
3753 TODO: extend to other conditions inside loop body. */
3754 ex_bb
= bb_for_stmt (use
->stmt
);
3755 if (use
->stmt
!= last_stmt (ex_bb
)
3756 || TREE_CODE (use
->stmt
) != COND_EXPR
)
3758 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, ex_bb
))
3761 exit
= EDGE_SUCC (ex_bb
, 0);
3762 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
3763 exit
= EDGE_SUCC (ex_bb
, 1);
3764 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
3767 nit
= niter_for_exit (data
, exit
);
3771 /* Determine whether we can use the variable to test the exit condition.
3772 This is the case iff the period of the induction variable is greater
3773 than the number of iterations for which the exit condition is true. */
3774 period
= iv_period (cand
->iv
);
3776 /* If the number of iterations is constant, compare against it directly. */
3777 if (TREE_CODE (nit
) == INTEGER_CST
)
3779 if (!tree_int_cst_lt (nit
, period
))
3783 /* If not, and if this is the only possible exit of the loop, see whether
3784 we can get a conservative estimate on the number of iterations of the
3785 entire loop and compare against that instead. */
3786 else if (loop_only_exit_p (loop
, exit
))
3788 double_int period_value
, max_niter
;
3789 if (!estimated_loop_iterations (loop
, true, &max_niter
))
3791 period_value
= tree_to_double_int (period
);
3792 if (double_int_ucmp (max_niter
, period_value
) >= 0)
3796 /* Otherwise, punt. */
3800 cand_value_at (loop
, cand
, use
->stmt
, nit
, &bnd
);
3801 *bound
= aff_combination_to_tree (&bnd
);
3805 /* Determines cost of basing replacement of USE on CAND in a condition. */
3808 determine_use_iv_cost_condition (struct ivopts_data
*data
,
3809 struct iv_use
*use
, struct iv_cand
*cand
)
3811 tree bound
= NULL_TREE
;
3813 bitmap depends_on_elim
= NULL
, depends_on_express
= NULL
, depends_on
;
3814 comp_cost elim_cost
, express_cost
, cost
;
3817 /* Only consider real candidates. */
3820 set_use_iv_cost (data
, use
, cand
, infinite_cost
, NULL
, NULL_TREE
);
3824 /* Try iv elimination. */
3825 if (may_eliminate_iv (data
, use
, cand
, &bound
))
3827 elim_cost
= force_var_cost (data
, bound
, &depends_on_elim
);
3828 /* The bound is a loop invariant, so it will be only computed
3830 elim_cost
.cost
/= AVG_LOOP_NITER (data
->current_loop
);
3833 elim_cost
= infinite_cost
;
3835 /* Try expressing the original giv. If it is compared with an invariant,
3836 note that we cannot get rid of it. */
3837 ok
= extract_cond_operands (data
, use
->op_p
, NULL
, NULL
, NULL
, &cmp_iv
);
3840 express_cost
= get_computation_cost (data
, use
, cand
, false,
3841 &depends_on_express
);
3842 fd_ivopts_data
= data
;
3843 walk_tree (&cmp_iv
->base
, find_depends
, &depends_on_express
, NULL
);
3845 /* Choose the better approach. */
3846 if (compare_costs (elim_cost
, express_cost
) < 0)
3849 depends_on
= depends_on_elim
;
3850 depends_on_elim
= NULL
;
3854 cost
= express_cost
;
3855 depends_on
= depends_on_express
;
3856 depends_on_express
= NULL
;
3860 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, bound
);
3862 if (depends_on_elim
)
3863 BITMAP_FREE (depends_on_elim
);
3864 if (depends_on_express
)
3865 BITMAP_FREE (depends_on_express
);
3867 return !infinite_cost_p (cost
);
3870 /* Determines cost of basing replacement of USE on CAND. Returns false
3871 if USE cannot be based on CAND. */
3874 determine_use_iv_cost (struct ivopts_data
*data
,
3875 struct iv_use
*use
, struct iv_cand
*cand
)
3879 case USE_NONLINEAR_EXPR
:
3880 return determine_use_iv_cost_generic (data
, use
, cand
);
3883 return determine_use_iv_cost_address (data
, use
, cand
);
3886 return determine_use_iv_cost_condition (data
, use
, cand
);
3893 /* Determines costs of basing the use of the iv on an iv candidate. */
3896 determine_use_iv_costs (struct ivopts_data
*data
)
3900 struct iv_cand
*cand
;
3901 bitmap to_clear
= BITMAP_ALLOC (NULL
);
3903 alloc_use_cost_map (data
);
3905 for (i
= 0; i
< n_iv_uses (data
); i
++)
3907 use
= iv_use (data
, i
);
3909 if (data
->consider_all_candidates
)
3911 for (j
= 0; j
< n_iv_cands (data
); j
++)
3913 cand
= iv_cand (data
, j
);
3914 determine_use_iv_cost (data
, use
, cand
);
3921 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, j
, bi
)
3923 cand
= iv_cand (data
, j
);
3924 if (!determine_use_iv_cost (data
, use
, cand
))
3925 bitmap_set_bit (to_clear
, j
);
3928 /* Remove the candidates for that the cost is infinite from
3929 the list of related candidates. */
3930 bitmap_and_compl_into (use
->related_cands
, to_clear
);
3931 bitmap_clear (to_clear
);
3935 BITMAP_FREE (to_clear
);
3937 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3939 fprintf (dump_file
, "Use-candidate costs:\n");
3941 for (i
= 0; i
< n_iv_uses (data
); i
++)
3943 use
= iv_use (data
, i
);
3945 fprintf (dump_file
, "Use %d:\n", i
);
3946 fprintf (dump_file
, " cand\tcost\tcompl.\tdepends on\n");
3947 for (j
= 0; j
< use
->n_map_members
; j
++)
3949 if (!use
->cost_map
[j
].cand
3950 || infinite_cost_p (use
->cost_map
[j
].cost
))
3953 fprintf (dump_file
, " %d\t%d\t%d\t",
3954 use
->cost_map
[j
].cand
->id
,
3955 use
->cost_map
[j
].cost
.cost
,
3956 use
->cost_map
[j
].cost
.complexity
);
3957 if (use
->cost_map
[j
].depends_on
)
3958 bitmap_print (dump_file
,
3959 use
->cost_map
[j
].depends_on
, "","");
3960 fprintf (dump_file
, "\n");
3963 fprintf (dump_file
, "\n");
3965 fprintf (dump_file
, "\n");
3969 /* Determines cost of the candidate CAND. */
3972 determine_iv_cost (struct ivopts_data
*data
, struct iv_cand
*cand
)
3974 comp_cost cost_base
;
3975 unsigned cost
, cost_step
;
3984 /* There are two costs associated with the candidate -- its increment
3985 and its initialization. The second is almost negligible for any loop
3986 that rolls enough, so we take it just very little into account. */
3988 base
= cand
->iv
->base
;
3989 cost_base
= force_var_cost (data
, base
, NULL
);
3990 cost_step
= add_cost (TYPE_MODE (TREE_TYPE (base
)));
3992 cost
= cost_step
+ cost_base
.cost
/ AVG_LOOP_NITER (current_loop
);
3994 /* Prefer the original ivs unless we may gain something by replacing it.
3995 The reason is to make debugging simpler; so this is not relevant for
3996 artificial ivs created by other optimization passes. */
3997 if (cand
->pos
!= IP_ORIGINAL
3998 || DECL_ARTIFICIAL (SSA_NAME_VAR (cand
->var_before
)))
4001 /* Prefer not to insert statements into latch unless there are some
4002 already (so that we do not create unnecessary jumps). */
4003 if (cand
->pos
== IP_END
4004 && empty_block_p (ip_end_pos (data
->current_loop
)))
4010 /* Determines costs of computation of the candidates. */
4013 determine_iv_costs (struct ivopts_data
*data
)
4017 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4019 fprintf (dump_file
, "Candidate costs:\n");
4020 fprintf (dump_file
, " cand\tcost\n");
4023 for (i
= 0; i
< n_iv_cands (data
); i
++)
4025 struct iv_cand
*cand
= iv_cand (data
, i
);
4027 determine_iv_cost (data
, cand
);
4029 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4030 fprintf (dump_file
, " %d\t%d\n", i
, cand
->cost
);
4033 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4034 fprintf (dump_file
, "\n");
4037 /* Calculates cost for having SIZE induction variables. */
4040 ivopts_global_cost_for_size (struct ivopts_data
*data
, unsigned size
)
4042 /* We add size to the cost, so that we prefer eliminating ivs
4044 return size
+ estimate_reg_pressure_cost (size
, data
->regs_used
);
4047 /* For each size of the induction variable set determine the penalty. */
4050 determine_set_costs (struct ivopts_data
*data
)
4054 struct loop
*loop
= data
->current_loop
;
4057 /* We use the following model (definitely improvable, especially the
4058 cost function -- TODO):
4060 We estimate the number of registers available (using MD data), name it A.
4062 We estimate the number of registers used by the loop, name it U. This
4063 number is obtained as the number of loop phi nodes (not counting virtual
4064 registers and bivs) + the number of variables from outside of the loop.
4066 We set a reserve R (free regs that are used for temporary computations,
4067 etc.). For now the reserve is a constant 3.
4069 Let I be the number of induction variables.
4071 -- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
4072 make a lot of ivs without a reason).
4073 -- if A - R < U + I <= A, the cost is I * PRES_COST
4074 -- if U + I > A, the cost is I * PRES_COST and
4075 number of uses * SPILL_COST * (U + I - A) / (U + I) is added. */
4077 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4079 fprintf (dump_file
, "Global costs:\n");
4080 fprintf (dump_file
, " target_avail_regs %d\n", target_avail_regs
);
4081 fprintf (dump_file
, " target_reg_cost %d\n", target_reg_cost
);
4082 fprintf (dump_file
, " target_spill_cost %d\n", target_spill_cost
);
4086 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
4088 op
= PHI_RESULT (phi
);
4090 if (!is_gimple_reg (op
))
4093 if (get_iv (data
, op
))
4099 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
4101 struct version_info
*info
= ver_info (data
, j
);
4103 if (info
->inv_id
&& info
->has_nonlin_use
)
4107 data
->regs_used
= n
;
4108 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4109 fprintf (dump_file
, " regs_used %d\n", n
);
4111 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4113 fprintf (dump_file
, " cost for size:\n");
4114 fprintf (dump_file
, " ivs\tcost\n");
4115 for (j
= 0; j
<= 2 * target_avail_regs
; j
++)
4116 fprintf (dump_file
, " %d\t%d\n", j
,
4117 ivopts_global_cost_for_size (data
, j
));
4118 fprintf (dump_file
, "\n");
4122 /* Returns true if A is a cheaper cost pair than B. */
4125 cheaper_cost_pair (struct cost_pair
*a
, struct cost_pair
*b
)
4135 cmp
= compare_costs (a
->cost
, b
->cost
);
4142 /* In case the costs are the same, prefer the cheaper candidate. */
4143 if (a
->cand
->cost
< b
->cand
->cost
)
4149 /* Computes the cost field of IVS structure. */
4152 iv_ca_recount_cost (struct ivopts_data
*data
, struct iv_ca
*ivs
)
4154 comp_cost cost
= ivs
->cand_use_cost
;
4155 cost
.cost
+= ivs
->cand_cost
;
4156 cost
.cost
+= ivopts_global_cost_for_size (data
, ivs
->n_regs
);
4161 /* Remove invariants in set INVS to set IVS. */
4164 iv_ca_set_remove_invariants (struct iv_ca
*ivs
, bitmap invs
)
4172 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
4174 ivs
->n_invariant_uses
[iid
]--;
4175 if (ivs
->n_invariant_uses
[iid
] == 0)
4180 /* Set USE not to be expressed by any candidate in IVS. */
4183 iv_ca_set_no_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4186 unsigned uid
= use
->id
, cid
;
4187 struct cost_pair
*cp
;
4189 cp
= ivs
->cand_for_use
[uid
];
4195 ivs
->cand_for_use
[uid
] = NULL
;
4196 ivs
->n_cand_uses
[cid
]--;
4198 if (ivs
->n_cand_uses
[cid
] == 0)
4200 bitmap_clear_bit (ivs
->cands
, cid
);
4201 /* Do not count the pseudocandidates. */
4205 ivs
->cand_cost
-= cp
->cand
->cost
;
4207 iv_ca_set_remove_invariants (ivs
, cp
->cand
->depends_on
);
4210 ivs
->cand_use_cost
= sub_costs (ivs
->cand_use_cost
, cp
->cost
);
4212 iv_ca_set_remove_invariants (ivs
, cp
->depends_on
);
4213 iv_ca_recount_cost (data
, ivs
);
4216 /* Add invariants in set INVS to set IVS. */
4219 iv_ca_set_add_invariants (struct iv_ca
*ivs
, bitmap invs
)
4227 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
4229 ivs
->n_invariant_uses
[iid
]++;
4230 if (ivs
->n_invariant_uses
[iid
] == 1)
4235 /* Set cost pair for USE in set IVS to CP. */
4238 iv_ca_set_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4239 struct iv_use
*use
, struct cost_pair
*cp
)
4241 unsigned uid
= use
->id
, cid
;
4243 if (ivs
->cand_for_use
[uid
] == cp
)
4246 if (ivs
->cand_for_use
[uid
])
4247 iv_ca_set_no_cp (data
, ivs
, use
);
4254 ivs
->cand_for_use
[uid
] = cp
;
4255 ivs
->n_cand_uses
[cid
]++;
4256 if (ivs
->n_cand_uses
[cid
] == 1)
4258 bitmap_set_bit (ivs
->cands
, cid
);
4259 /* Do not count the pseudocandidates. */
4263 ivs
->cand_cost
+= cp
->cand
->cost
;
4265 iv_ca_set_add_invariants (ivs
, cp
->cand
->depends_on
);
4268 ivs
->cand_use_cost
= add_costs (ivs
->cand_use_cost
, cp
->cost
);
4269 iv_ca_set_add_invariants (ivs
, cp
->depends_on
);
4270 iv_ca_recount_cost (data
, ivs
);
4274 /* Extend set IVS by expressing USE by some of the candidates in it
4278 iv_ca_add_use (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4281 struct cost_pair
*best_cp
= NULL
, *cp
;
4285 gcc_assert (ivs
->upto
>= use
->id
);
4287 if (ivs
->upto
== use
->id
)
4293 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
4295 cp
= get_use_iv_cost (data
, use
, iv_cand (data
, i
));
4297 if (cheaper_cost_pair (cp
, best_cp
))
4301 iv_ca_set_cp (data
, ivs
, use
, best_cp
);
4304 /* Get cost for assignment IVS. */
4307 iv_ca_cost (struct iv_ca
*ivs
)
4309 return (ivs
->bad_uses
? infinite_cost
: ivs
->cost
);
4312 /* Returns true if all dependences of CP are among invariants in IVS. */
4315 iv_ca_has_deps (struct iv_ca
*ivs
, struct cost_pair
*cp
)
4320 if (!cp
->depends_on
)
4323 EXECUTE_IF_SET_IN_BITMAP (cp
->depends_on
, 0, i
, bi
)
4325 if (ivs
->n_invariant_uses
[i
] == 0)
4332 /* Creates change of expressing USE by NEW_CP instead of OLD_CP and chains
4333 it before NEXT_CHANGE. */
4335 static struct iv_ca_delta
*
4336 iv_ca_delta_add (struct iv_use
*use
, struct cost_pair
*old_cp
,
4337 struct cost_pair
*new_cp
, struct iv_ca_delta
*next_change
)
4339 struct iv_ca_delta
*change
= XNEW (struct iv_ca_delta
);
4342 change
->old_cp
= old_cp
;
4343 change
->new_cp
= new_cp
;
4344 change
->next_change
= next_change
;
4349 /* Joins two lists of changes L1 and L2. Destructive -- old lists
4352 static struct iv_ca_delta
*
4353 iv_ca_delta_join (struct iv_ca_delta
*l1
, struct iv_ca_delta
*l2
)
4355 struct iv_ca_delta
*last
;
4363 for (last
= l1
; last
->next_change
; last
= last
->next_change
)
4365 last
->next_change
= l2
;
4370 /* Returns candidate by that USE is expressed in IVS. */
4372 static struct cost_pair
*
4373 iv_ca_cand_for_use (struct iv_ca
*ivs
, struct iv_use
*use
)
4375 return ivs
->cand_for_use
[use
->id
];
4378 /* Reverse the list of changes DELTA, forming the inverse to it. */
4380 static struct iv_ca_delta
*
4381 iv_ca_delta_reverse (struct iv_ca_delta
*delta
)
4383 struct iv_ca_delta
*act
, *next
, *prev
= NULL
;
4384 struct cost_pair
*tmp
;
4386 for (act
= delta
; act
; act
= next
)
4388 next
= act
->next_change
;
4389 act
->next_change
= prev
;
4393 act
->old_cp
= act
->new_cp
;
4400 /* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
4401 reverted instead. */
4404 iv_ca_delta_commit (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4405 struct iv_ca_delta
*delta
, bool forward
)
4407 struct cost_pair
*from
, *to
;
4408 struct iv_ca_delta
*act
;
4411 delta
= iv_ca_delta_reverse (delta
);
4413 for (act
= delta
; act
; act
= act
->next_change
)
4417 gcc_assert (iv_ca_cand_for_use (ivs
, act
->use
) == from
);
4418 iv_ca_set_cp (data
, ivs
, act
->use
, to
);
4422 iv_ca_delta_reverse (delta
);
4425 /* Returns true if CAND is used in IVS. */
4428 iv_ca_cand_used_p (struct iv_ca
*ivs
, struct iv_cand
*cand
)
4430 return ivs
->n_cand_uses
[cand
->id
] > 0;
4433 /* Returns number of induction variable candidates in the set IVS. */
4436 iv_ca_n_cands (struct iv_ca
*ivs
)
4438 return ivs
->n_cands
;
4441 /* Free the list of changes DELTA. */
4444 iv_ca_delta_free (struct iv_ca_delta
**delta
)
4446 struct iv_ca_delta
*act
, *next
;
4448 for (act
= *delta
; act
; act
= next
)
4450 next
= act
->next_change
;
4457 /* Allocates new iv candidates assignment. */
4459 static struct iv_ca
*
4460 iv_ca_new (struct ivopts_data
*data
)
4462 struct iv_ca
*nw
= XNEW (struct iv_ca
);
4466 nw
->cand_for_use
= XCNEWVEC (struct cost_pair
*, n_iv_uses (data
));
4467 nw
->n_cand_uses
= XCNEWVEC (unsigned, n_iv_cands (data
));
4468 nw
->cands
= BITMAP_ALLOC (NULL
);
4471 nw
->cand_use_cost
= zero_cost
;
4473 nw
->n_invariant_uses
= XCNEWVEC (unsigned, data
->max_inv_id
+ 1);
4474 nw
->cost
= zero_cost
;
4479 /* Free memory occupied by the set IVS. */
4482 iv_ca_free (struct iv_ca
**ivs
)
4484 free ((*ivs
)->cand_for_use
);
4485 free ((*ivs
)->n_cand_uses
);
4486 BITMAP_FREE ((*ivs
)->cands
);
4487 free ((*ivs
)->n_invariant_uses
);
4492 /* Dumps IVS to FILE. */
4495 iv_ca_dump (struct ivopts_data
*data
, FILE *file
, struct iv_ca
*ivs
)
4497 const char *pref
= " invariants ";
4499 comp_cost cost
= iv_ca_cost (ivs
);
4501 fprintf (file
, " cost %d (complexity %d)\n", cost
.cost
, cost
.complexity
);
4502 bitmap_print (file
, ivs
->cands
, " candidates ","\n");
4504 for (i
= 1; i
<= data
->max_inv_id
; i
++)
4505 if (ivs
->n_invariant_uses
[i
])
4507 fprintf (file
, "%s%d", pref
, i
);
4510 fprintf (file
, "\n");
4513 /* Try changing candidate in IVS to CAND for each use. Return cost of the
4514 new set, and store differences in DELTA. Number of induction variables
4515 in the new set is stored to N_IVS. */
4518 iv_ca_extend (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4519 struct iv_cand
*cand
, struct iv_ca_delta
**delta
,
4525 struct cost_pair
*old_cp
, *new_cp
;
4528 for (i
= 0; i
< ivs
->upto
; i
++)
4530 use
= iv_use (data
, i
);
4531 old_cp
= iv_ca_cand_for_use (ivs
, use
);
4534 && old_cp
->cand
== cand
)
4537 new_cp
= get_use_iv_cost (data
, use
, cand
);
4541 if (!iv_ca_has_deps (ivs
, new_cp
))
4544 if (!cheaper_cost_pair (new_cp
, old_cp
))
4547 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
4550 iv_ca_delta_commit (data
, ivs
, *delta
, true);
4551 cost
= iv_ca_cost (ivs
);
4553 *n_ivs
= iv_ca_n_cands (ivs
);
4554 iv_ca_delta_commit (data
, ivs
, *delta
, false);
4559 /* Try narrowing set IVS by removing CAND. Return the cost of
4560 the new set and store the differences in DELTA. */
4563 iv_ca_narrow (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4564 struct iv_cand
*cand
, struct iv_ca_delta
**delta
)
4568 struct cost_pair
*old_cp
, *new_cp
, *cp
;
4570 struct iv_cand
*cnd
;
4574 for (i
= 0; i
< n_iv_uses (data
); i
++)
4576 use
= iv_use (data
, i
);
4578 old_cp
= iv_ca_cand_for_use (ivs
, use
);
4579 if (old_cp
->cand
!= cand
)
4584 if (data
->consider_all_candidates
)
4586 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, ci
, bi
)
4591 cnd
= iv_cand (data
, ci
);
4593 cp
= get_use_iv_cost (data
, use
, cnd
);
4596 if (!iv_ca_has_deps (ivs
, cp
))
4599 if (!cheaper_cost_pair (cp
, new_cp
))
4607 EXECUTE_IF_AND_IN_BITMAP (use
->related_cands
, ivs
->cands
, 0, ci
, bi
)
4612 cnd
= iv_cand (data
, ci
);
4614 cp
= get_use_iv_cost (data
, use
, cnd
);
4617 if (!iv_ca_has_deps (ivs
, cp
))
4620 if (!cheaper_cost_pair (cp
, new_cp
))
4629 iv_ca_delta_free (delta
);
4630 return infinite_cost
;
4633 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
4636 iv_ca_delta_commit (data
, ivs
, *delta
, true);
4637 cost
= iv_ca_cost (ivs
);
4638 iv_ca_delta_commit (data
, ivs
, *delta
, false);
4643 /* Try optimizing the set of candidates IVS by removing candidates different
4644 from to EXCEPT_CAND from it. Return cost of the new set, and store
4645 differences in DELTA. */
4648 iv_ca_prune (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4649 struct iv_cand
*except_cand
, struct iv_ca_delta
**delta
)
4652 struct iv_ca_delta
*act_delta
, *best_delta
;
4654 comp_cost best_cost
, acost
;
4655 struct iv_cand
*cand
;
4658 best_cost
= iv_ca_cost (ivs
);
4660 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
4662 cand
= iv_cand (data
, i
);
4664 if (cand
== except_cand
)
4667 acost
= iv_ca_narrow (data
, ivs
, cand
, &act_delta
);
4669 if (compare_costs (acost
, best_cost
) < 0)
4672 iv_ca_delta_free (&best_delta
);
4673 best_delta
= act_delta
;
4676 iv_ca_delta_free (&act_delta
);
4685 /* Recurse to possibly remove other unnecessary ivs. */
4686 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
4687 best_cost
= iv_ca_prune (data
, ivs
, except_cand
, delta
);
4688 iv_ca_delta_commit (data
, ivs
, best_delta
, false);
4689 *delta
= iv_ca_delta_join (best_delta
, *delta
);
4693 /* Tries to extend the sets IVS in the best possible way in order
4694 to express the USE. */
4697 try_add_cand_for (struct ivopts_data
*data
, struct iv_ca
*ivs
,
4700 comp_cost best_cost
, act_cost
;
4703 struct iv_cand
*cand
;
4704 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
;
4705 struct cost_pair
*cp
;
4707 iv_ca_add_use (data
, ivs
, use
);
4708 best_cost
= iv_ca_cost (ivs
);
4710 cp
= iv_ca_cand_for_use (ivs
, use
);
4713 best_delta
= iv_ca_delta_add (use
, NULL
, cp
, NULL
);
4714 iv_ca_set_no_cp (data
, ivs
, use
);
4717 /* First try important candidates not based on any memory object. Only if
4718 this fails, try the specific ones. Rationale -- in loops with many
4719 variables the best choice often is to use just one generic biv. If we
4720 added here many ivs specific to the uses, the optimization algorithm later
4721 would be likely to get stuck in a local minimum, thus causing us to create
4722 too many ivs. The approach from few ivs to more seems more likely to be
4723 successful -- starting from few ivs, replacing an expensive use by a
4724 specific iv should always be a win. */
4725 EXECUTE_IF_SET_IN_BITMAP (data
->important_candidates
, 0, i
, bi
)
4727 cand
= iv_cand (data
, i
);
4729 if (cand
->iv
->base_object
!= NULL_TREE
)
4732 if (iv_ca_cand_used_p (ivs
, cand
))
4735 cp
= get_use_iv_cost (data
, use
, cand
);
4739 iv_ca_set_cp (data
, ivs
, use
, cp
);
4740 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
);
4741 iv_ca_set_no_cp (data
, ivs
, use
);
4742 act_delta
= iv_ca_delta_add (use
, NULL
, cp
, act_delta
);
4744 if (compare_costs (act_cost
, best_cost
) < 0)
4746 best_cost
= act_cost
;
4748 iv_ca_delta_free (&best_delta
);
4749 best_delta
= act_delta
;
4752 iv_ca_delta_free (&act_delta
);
4755 if (infinite_cost_p (best_cost
))
4757 for (i
= 0; i
< use
->n_map_members
; i
++)
4759 cp
= use
->cost_map
+ i
;
4764 /* Already tried this. */
4765 if (cand
->important
&& cand
->iv
->base_object
== NULL_TREE
)
4768 if (iv_ca_cand_used_p (ivs
, cand
))
4772 iv_ca_set_cp (data
, ivs
, use
, cp
);
4773 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
);
4774 iv_ca_set_no_cp (data
, ivs
, use
);
4775 act_delta
= iv_ca_delta_add (use
, iv_ca_cand_for_use (ivs
, use
),
4778 if (compare_costs (act_cost
, best_cost
) < 0)
4780 best_cost
= act_cost
;
4783 iv_ca_delta_free (&best_delta
);
4784 best_delta
= act_delta
;
4787 iv_ca_delta_free (&act_delta
);
4791 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
4792 iv_ca_delta_free (&best_delta
);
4794 return !infinite_cost_p (best_cost
);
4797 /* Finds an initial assignment of candidates to uses. */
4799 static struct iv_ca
*
4800 get_initial_solution (struct ivopts_data
*data
)
4802 struct iv_ca
*ivs
= iv_ca_new (data
);
4805 for (i
= 0; i
< n_iv_uses (data
); i
++)
4806 if (!try_add_cand_for (data
, ivs
, iv_use (data
, i
)))
4815 /* Tries to improve set of induction variables IVS. */
4818 try_improve_iv_set (struct ivopts_data
*data
, struct iv_ca
*ivs
)
4821 comp_cost acost
, best_cost
= iv_ca_cost (ivs
);
4822 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
, *tmp_delta
;
4823 struct iv_cand
*cand
;
4825 /* Try extending the set of induction variables by one. */
4826 for (i
= 0; i
< n_iv_cands (data
); i
++)
4828 cand
= iv_cand (data
, i
);
4830 if (iv_ca_cand_used_p (ivs
, cand
))
4833 acost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, &n_ivs
);
4837 /* If we successfully added the candidate and the set is small enough,
4838 try optimizing it by removing other candidates. */
4839 if (n_ivs
<= ALWAYS_PRUNE_CAND_SET_BOUND
)
4841 iv_ca_delta_commit (data
, ivs
, act_delta
, true);
4842 acost
= iv_ca_prune (data
, ivs
, cand
, &tmp_delta
);
4843 iv_ca_delta_commit (data
, ivs
, act_delta
, false);
4844 act_delta
= iv_ca_delta_join (act_delta
, tmp_delta
);
4847 if (compare_costs (acost
, best_cost
) < 0)
4850 iv_ca_delta_free (&best_delta
);
4851 best_delta
= act_delta
;
4854 iv_ca_delta_free (&act_delta
);
4859 /* Try removing the candidates from the set instead. */
4860 best_cost
= iv_ca_prune (data
, ivs
, NULL
, &best_delta
);
4862 /* Nothing more we can do. */
4867 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
4868 gcc_assert (compare_costs (best_cost
, iv_ca_cost (ivs
)) == 0);
4869 iv_ca_delta_free (&best_delta
);
4873 /* Attempts to find the optimal set of induction variables. We do simple
4874 greedy heuristic -- we try to replace at most one candidate in the selected
4875 solution and remove the unused ivs while this improves the cost. */
4877 static struct iv_ca
*
4878 find_optimal_iv_set (struct ivopts_data
*data
)
4884 /* Get the initial solution. */
4885 set
= get_initial_solution (data
);
4888 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4889 fprintf (dump_file
, "Unable to substitute for ivs, failed.\n");
4893 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4895 fprintf (dump_file
, "Initial set of candidates:\n");
4896 iv_ca_dump (data
, dump_file
, set
);
4899 while (try_improve_iv_set (data
, set
))
4901 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4903 fprintf (dump_file
, "Improved to:\n");
4904 iv_ca_dump (data
, dump_file
, set
);
4908 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4910 comp_cost cost
= iv_ca_cost (set
);
4911 fprintf (dump_file
, "Final cost %d (complexity %d)\n\n", cost
.cost
, cost
.complexity
);
4914 for (i
= 0; i
< n_iv_uses (data
); i
++)
4916 use
= iv_use (data
, i
);
4917 use
->selected
= iv_ca_cand_for_use (set
, use
)->cand
;
4923 /* Creates a new induction variable corresponding to CAND. */
4926 create_new_iv (struct ivopts_data
*data
, struct iv_cand
*cand
)
4928 block_stmt_iterator incr_pos
;
4938 incr_pos
= bsi_last (ip_normal_pos (data
->current_loop
));
4942 incr_pos
= bsi_last (ip_end_pos (data
->current_loop
));
4947 /* Mark that the iv is preserved. */
4948 name_info (data
, cand
->var_before
)->preserve_biv
= true;
4949 name_info (data
, cand
->var_after
)->preserve_biv
= true;
4951 /* Rewrite the increment so that it uses var_before directly. */
4952 find_interesting_uses_op (data
, cand
->var_after
)->selected
= cand
;
4957 gimple_add_tmp_var (cand
->var_before
);
4958 add_referenced_var (cand
->var_before
);
4960 base
= unshare_expr (cand
->iv
->base
);
4962 create_iv (base
, unshare_expr (cand
->iv
->step
),
4963 cand
->var_before
, data
->current_loop
,
4964 &incr_pos
, after
, &cand
->var_before
, &cand
->var_after
);
4967 /* Creates new induction variables described in SET. */
4970 create_new_ivs (struct ivopts_data
*data
, struct iv_ca
*set
)
4973 struct iv_cand
*cand
;
4976 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
4978 cand
= iv_cand (data
, i
);
4979 create_new_iv (data
, cand
);
4983 /* Removes statement STMT (real or a phi node). If INCLUDING_DEFINED_NAME
4984 is true, remove also the ssa name defined by the statement. */
4987 remove_statement (tree stmt
, bool including_defined_name
)
4989 if (TREE_CODE (stmt
) == PHI_NODE
)
4991 remove_phi_node (stmt
, NULL_TREE
, including_defined_name
);
4995 block_stmt_iterator bsi
= bsi_for_stmt (stmt
);
4997 bsi_remove (&bsi
, true);
4998 release_defs (stmt
);
5002 /* Rewrites USE (definition of iv used in a nonlinear expression)
5003 using candidate CAND. */
5006 rewrite_use_nonlinear_expr (struct ivopts_data
*data
,
5007 struct iv_use
*use
, struct iv_cand
*cand
)
5011 block_stmt_iterator bsi
;
5013 /* An important special case -- if we are asked to express value of
5014 the original iv by itself, just exit; there is no need to
5015 introduce a new computation (that might also need casting the
5016 variable to unsigned and back). */
5017 if (cand
->pos
== IP_ORIGINAL
5018 && cand
->incremented_at
== use
->stmt
)
5020 tree step
, ctype
, utype
;
5021 enum tree_code incr_code
= PLUS_EXPR
;
5023 gcc_assert (TREE_CODE (use
->stmt
) == GIMPLE_MODIFY_STMT
);
5024 gcc_assert (GIMPLE_STMT_OPERAND (use
->stmt
, 0) == cand
->var_after
);
5026 step
= cand
->iv
->step
;
5027 ctype
= TREE_TYPE (step
);
5028 utype
= TREE_TYPE (cand
->var_after
);
5029 if (TREE_CODE (step
) == NEGATE_EXPR
)
5031 incr_code
= MINUS_EXPR
;
5032 step
= TREE_OPERAND (step
, 0);
5035 /* Check whether we may leave the computation unchanged.
5036 This is the case only if it does not rely on other
5037 computations in the loop -- otherwise, the computation
5038 we rely upon may be removed in remove_unused_ivs,
5039 thus leading to ICE. */
5040 op
= GIMPLE_STMT_OPERAND (use
->stmt
, 1);
5041 if (TREE_CODE (op
) == PLUS_EXPR
5042 || TREE_CODE (op
) == MINUS_EXPR
5043 || TREE_CODE (op
) == POINTER_PLUS_EXPR
)
5045 if (TREE_OPERAND (op
, 0) == cand
->var_before
)
5046 op
= TREE_OPERAND (op
, 1);
5047 else if (TREE_CODE (op
) != MINUS_EXPR
5048 && TREE_OPERAND (op
, 1) == cand
->var_before
)
5049 op
= TREE_OPERAND (op
, 0);
5057 && (TREE_CODE (op
) == INTEGER_CST
5058 || operand_equal_p (op
, step
, 0)))
5061 /* Otherwise, add the necessary computations to express
5063 op
= fold_convert (ctype
, cand
->var_before
);
5064 comp
= fold_convert (utype
,
5065 build2 (incr_code
, ctype
, op
,
5066 unshare_expr (step
)));
5070 comp
= get_computation (data
->current_loop
, use
, cand
);
5071 gcc_assert (comp
!= NULL_TREE
);
5074 switch (TREE_CODE (use
->stmt
))
5077 tgt
= PHI_RESULT (use
->stmt
);
5079 /* If we should keep the biv, do not replace it. */
5080 if (name_info (data
, tgt
)->preserve_biv
)
5083 bsi
= bsi_after_labels (bb_for_stmt (use
->stmt
));
5086 case GIMPLE_MODIFY_STMT
:
5087 tgt
= GIMPLE_STMT_OPERAND (use
->stmt
, 0);
5088 bsi
= bsi_for_stmt (use
->stmt
);
5095 op
= force_gimple_operand_bsi (&bsi
, comp
, false, SSA_NAME_VAR (tgt
),
5096 true, BSI_SAME_STMT
);
5098 if (TREE_CODE (use
->stmt
) == PHI_NODE
)
5100 ass
= build_gimple_modify_stmt (tgt
, op
);
5101 bsi_insert_before (&bsi
, ass
, BSI_SAME_STMT
);
5102 remove_statement (use
->stmt
, false);
5103 SSA_NAME_DEF_STMT (tgt
) = ass
;
5106 GIMPLE_STMT_OPERAND (use
->stmt
, 1) = op
;
5109 /* Replaces ssa name in index IDX by its basic variable. Callback for
5113 idx_remove_ssa_names (tree base
, tree
*idx
,
5114 void *data ATTRIBUTE_UNUSED
)
5118 if (TREE_CODE (*idx
) == SSA_NAME
)
5119 *idx
= SSA_NAME_VAR (*idx
);
5121 if (TREE_CODE (base
) == ARRAY_REF
)
5123 op
= &TREE_OPERAND (base
, 2);
5125 && TREE_CODE (*op
) == SSA_NAME
)
5126 *op
= SSA_NAME_VAR (*op
);
5127 op
= &TREE_OPERAND (base
, 3);
5129 && TREE_CODE (*op
) == SSA_NAME
)
5130 *op
= SSA_NAME_VAR (*op
);
5136 /* Unshares REF and replaces ssa names inside it by their basic variables. */
5139 unshare_and_remove_ssa_names (tree ref
)
5141 ref
= unshare_expr (ref
);
5142 for_each_index (&ref
, idx_remove_ssa_names
, NULL
);
5147 /* Extract the alias analysis info for the memory reference REF. There are
5148 several ways how this information may be stored and what precisely is
5149 its semantics depending on the type of the reference, but there always is
5150 somewhere hidden one _DECL node that is used to determine the set of
5151 virtual operands for the reference. The code below deciphers this jungle
5152 and extracts this single useful piece of information. */
5155 get_ref_tag (tree ref
, tree orig
)
5157 tree var
= get_base_address (ref
);
5158 tree aref
= NULL_TREE
, tag
, sv
;
5159 HOST_WIDE_INT offset
, size
, maxsize
;
5161 for (sv
= orig
; handled_component_p (sv
); sv
= TREE_OPERAND (sv
, 0))
5163 aref
= get_ref_base_and_extent (sv
, &offset
, &size
, &maxsize
);
5171 if (TREE_CODE (var
) == INDIRECT_REF
)
5173 /* If the base is a dereference of a pointer, first check its name memory
5174 tag. If it does not have one, use its symbol memory tag. */
5175 var
= TREE_OPERAND (var
, 0);
5176 if (TREE_CODE (var
) != SSA_NAME
)
5179 if (SSA_NAME_PTR_INFO (var
))
5181 tag
= SSA_NAME_PTR_INFO (var
)->name_mem_tag
;
5186 var
= SSA_NAME_VAR (var
);
5187 tag
= symbol_mem_tag (var
);
5188 gcc_assert (tag
!= NULL_TREE
);
5196 tag
= symbol_mem_tag (var
);
5204 /* Copies the reference information from OLD_REF to NEW_REF. */
5207 copy_ref_info (tree new_ref
, tree old_ref
)
5209 if (TREE_CODE (old_ref
) == TARGET_MEM_REF
)
5210 copy_mem_ref_info (new_ref
, old_ref
);
5213 TMR_ORIGINAL (new_ref
) = unshare_and_remove_ssa_names (old_ref
);
5214 TMR_TAG (new_ref
) = get_ref_tag (old_ref
, TMR_ORIGINAL (new_ref
));
5218 /* Rewrites USE (address that is an iv) using candidate CAND. */
5221 rewrite_use_address (struct ivopts_data
*data
,
5222 struct iv_use
*use
, struct iv_cand
*cand
)
5225 block_stmt_iterator bsi
= bsi_for_stmt (use
->stmt
);
5229 ok
= get_computation_aff (data
->current_loop
, use
, cand
, use
->stmt
, &aff
);
5231 unshare_aff_combination (&aff
);
5233 ref
= create_mem_ref (&bsi
, TREE_TYPE (*use
->op_p
), &aff
);
5234 copy_ref_info (ref
, *use
->op_p
);
5238 /* Rewrites USE (the condition such that one of the arguments is an iv) using
5242 rewrite_use_compare (struct ivopts_data
*data
,
5243 struct iv_use
*use
, struct iv_cand
*cand
)
5245 tree comp
, *var_p
, op
, bound
;
5246 block_stmt_iterator bsi
= bsi_for_stmt (use
->stmt
);
5247 enum tree_code compare
;
5248 struct cost_pair
*cp
= get_use_iv_cost (data
, use
, cand
);
5254 tree var
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
5255 tree var_type
= TREE_TYPE (var
);
5257 compare
= iv_elimination_compare (data
, use
);
5258 bound
= unshare_expr (fold_convert (var_type
, bound
));
5259 op
= force_gimple_operand_bsi (&bsi
, bound
, true, NULL_TREE
,
5260 true, BSI_SAME_STMT
);
5262 *use
->op_p
= build2 (compare
, boolean_type_node
, var
, op
);
5266 /* The induction variable elimination failed; just express the original
5268 comp
= get_computation (data
->current_loop
, use
, cand
);
5269 gcc_assert (comp
!= NULL_TREE
);
5271 ok
= extract_cond_operands (data
, use
->op_p
, &var_p
, NULL
, NULL
, NULL
);
5274 *var_p
= force_gimple_operand_bsi (&bsi
, comp
, true, SSA_NAME_VAR (*var_p
),
5275 true, BSI_SAME_STMT
);
5278 /* Rewrites USE using candidate CAND. */
5281 rewrite_use (struct ivopts_data
*data
, struct iv_use
*use
, struct iv_cand
*cand
)
5283 push_stmt_changes (&use
->stmt
);
5287 case USE_NONLINEAR_EXPR
:
5288 rewrite_use_nonlinear_expr (data
, use
, cand
);
5292 rewrite_use_address (data
, use
, cand
);
5296 rewrite_use_compare (data
, use
, cand
);
5303 pop_stmt_changes (&use
->stmt
);
5306 /* Rewrite the uses using the selected induction variables. */
5309 rewrite_uses (struct ivopts_data
*data
)
5312 struct iv_cand
*cand
;
5315 for (i
= 0; i
< n_iv_uses (data
); i
++)
5317 use
= iv_use (data
, i
);
5318 cand
= use
->selected
;
5321 rewrite_use (data
, use
, cand
);
5325 /* Removes the ivs that are not used after rewriting. */
5328 remove_unused_ivs (struct ivopts_data
*data
)
5333 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
5335 struct version_info
*info
;
5337 info
= ver_info (data
, j
);
5339 && !integer_zerop (info
->iv
->step
)
5341 && !info
->iv
->have_use_for
5342 && !info
->preserve_biv
)
5343 remove_statement (SSA_NAME_DEF_STMT (info
->iv
->ssa_name
), true);
5347 /* Frees data allocated by the optimization of a single loop. */
5350 free_loop_data (struct ivopts_data
*data
)
5358 pointer_map_destroy (data
->niters
);
5359 data
->niters
= NULL
;
5362 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
5364 struct version_info
*info
;
5366 info
= ver_info (data
, i
);
5370 info
->has_nonlin_use
= false;
5371 info
->preserve_biv
= false;
5374 bitmap_clear (data
->relevant
);
5375 bitmap_clear (data
->important_candidates
);
5377 for (i
= 0; i
< n_iv_uses (data
); i
++)
5379 struct iv_use
*use
= iv_use (data
, i
);
5382 BITMAP_FREE (use
->related_cands
);
5383 for (j
= 0; j
< use
->n_map_members
; j
++)
5384 if (use
->cost_map
[j
].depends_on
)
5385 BITMAP_FREE (use
->cost_map
[j
].depends_on
);
5386 free (use
->cost_map
);
5389 VEC_truncate (iv_use_p
, data
->iv_uses
, 0);
5391 for (i
= 0; i
< n_iv_cands (data
); i
++)
5393 struct iv_cand
*cand
= iv_cand (data
, i
);
5397 if (cand
->depends_on
)
5398 BITMAP_FREE (cand
->depends_on
);
5401 VEC_truncate (iv_cand_p
, data
->iv_candidates
, 0);
5403 if (data
->version_info_size
< num_ssa_names
)
5405 data
->version_info_size
= 2 * num_ssa_names
;
5406 free (data
->version_info
);
5407 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
5410 data
->max_inv_id
= 0;
5412 for (i
= 0; VEC_iterate (tree
, decl_rtl_to_reset
, i
, obj
); i
++)
5413 SET_DECL_RTL (obj
, NULL_RTX
);
5415 VEC_truncate (tree
, decl_rtl_to_reset
, 0);
5418 /* Finalizes data structures used by the iv optimization pass. LOOPS is the
5422 tree_ssa_iv_optimize_finalize (struct ivopts_data
*data
)
5424 free_loop_data (data
);
5425 free (data
->version_info
);
5426 BITMAP_FREE (data
->relevant
);
5427 BITMAP_FREE (data
->important_candidates
);
5429 VEC_free (tree
, heap
, decl_rtl_to_reset
);
5430 VEC_free (iv_use_p
, heap
, data
->iv_uses
);
5431 VEC_free (iv_cand_p
, heap
, data
->iv_candidates
);
5434 /* Optimizes the LOOP. Returns true if anything changed. */
5437 tree_ssa_iv_optimize_loop (struct ivopts_data
*data
, struct loop
*loop
)
5439 bool changed
= false;
5440 struct iv_ca
*iv_ca
;
5443 gcc_assert (!data
->niters
);
5444 data
->current_loop
= loop
;
5446 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5448 fprintf (dump_file
, "Processing loop %d\n", loop
->num
);
5450 exit
= single_dom_exit (loop
);
5453 fprintf (dump_file
, " single exit %d -> %d, exit condition ",
5454 exit
->src
->index
, exit
->dest
->index
);
5455 print_generic_expr (dump_file
, last_stmt (exit
->src
), TDF_SLIM
);
5456 fprintf (dump_file
, "\n");
5459 fprintf (dump_file
, "\n");
5462 /* For each ssa name determines whether it behaves as an induction variable
5464 if (!find_induction_variables (data
))
5467 /* Finds interesting uses (item 1). */
5468 find_interesting_uses (data
);
5469 if (n_iv_uses (data
) > MAX_CONSIDERED_USES
)
5472 /* Finds candidates for the induction variables (item 2). */
5473 find_iv_candidates (data
);
5475 /* Calculates the costs (item 3, part 1). */
5476 determine_use_iv_costs (data
);
5477 determine_iv_costs (data
);
5478 determine_set_costs (data
);
5480 /* Find the optimal set of induction variables (item 3, part 2). */
5481 iv_ca
= find_optimal_iv_set (data
);
5486 /* Create the new induction variables (item 4, part 1). */
5487 create_new_ivs (data
, iv_ca
);
5488 iv_ca_free (&iv_ca
);
5490 /* Rewrite the uses (item 4, part 2). */
5491 rewrite_uses (data
);
5493 /* Remove the ivs that are unused after rewriting. */
5494 remove_unused_ivs (data
);
5496 /* We have changed the structure of induction variables; it might happen
5497 that definitions in the scev database refer to some of them that were
5502 free_loop_data (data
);
5507 /* Main entry point. Optimizes induction variables in loops. */
5510 tree_ssa_iv_optimize (void)
5513 struct ivopts_data data
;
5516 tree_ssa_iv_optimize_init (&data
);
5518 /* Optimize the loops starting with the innermost ones. */
5519 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
5521 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5522 flow_loop_dump (loop
, dump_file
, NULL
, 1);
5524 tree_ssa_iv_optimize_loop (&data
, loop
);
5527 tree_ssa_iv_optimize_finalize (&data
);