1 /* Induction variable optimizations.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This pass tries to find the optimal set of induction variables for the loop.
21 It optimizes just the basic linear induction variables (although adding
22 support for other types should not be too hard). It includes the
23 optimizations commonly known as strength reduction, induction variable
24 coalescing and induction variable elimination. It does it in the
27 1) The interesting uses of induction variables are found. This includes
29 -- uses of induction variables in non-linear expressions
30 -- addresses of arrays
31 -- comparisons of induction variables
33 2) Candidates for the induction variables are found. This includes
35 -- old induction variables
36 -- the variables defined by expressions derived from the "interesting
39 3) The optimal (w.r. to a cost function) set of variables is chosen. The
40 cost function assigns a cost to sets of induction variables and consists
43 -- The use costs. Each of the interesting uses chooses the best induction
44 variable in the set and adds its cost to the sum. The cost reflects
45 the time spent on modifying the induction variables value to be usable
46 for the given purpose (adding base and offset for arrays, etc.).
47 -- The variable costs. Each of the variables has a cost assigned that
48 reflects the costs associated with incrementing the value of the
49 variable. The original variables are somewhat preferred.
50 -- The set cost. Depending on the size of the set, extra cost may be
51 added to reflect register pressure.
53 All the costs are defined in a machine-specific way, using the target
54 hooks and machine descriptions to determine them.
56 4) The trees are transformed to use the new variables, the dead code is
59 All of this is done loop by loop. Doing it globally is theoretically
60 possible, it might give a better performance and it might enable us
61 to decide costs more precisely, but getting all the interactions right
62 would be complicated. */
66 #include "coretypes.h"
69 #include "stor-layout.h"
71 #include "basic-block.h"
72 #include "gimple-pretty-print.h"
73 #include "pointer-set.h"
74 #include "hash-table.h"
75 #include "tree-ssa-alias.h"
76 #include "internal-fn.h"
78 #include "gimple-expr.h"
82 #include "gimple-iterator.h"
83 #include "gimplify-me.h"
84 #include "gimple-ssa.h"
87 #include "tree-phinodes.h"
88 #include "ssa-iterators.h"
89 #include "stringpool.h"
90 #include "tree-ssanames.h"
91 #include "tree-ssa-loop-ivopts.h"
92 #include "tree-ssa-loop-manip.h"
93 #include "tree-ssa-loop-niter.h"
94 #include "tree-ssa-loop.h"
99 #include "tree-pass.h"
100 #include "insn-config.h"
101 #include "tree-chrec.h"
102 #include "tree-scalar-evolution.h"
105 #include "langhooks.h"
106 #include "tree-affine.h"
108 #include "tree-inline.h"
109 #include "tree-ssa-propagate.h"
111 #include "tree-ssa-address.h"
113 /* FIXME: Expressions are expanded to RTL in this pass to determine the
114 cost of different addressing modes. This should be moved to a TBD
115 interface between the GIMPLE and RTL worlds. */
119 /* The infinite cost. */
120 #define INFTY 10000000
122 #define AVG_LOOP_NITER(LOOP) 5
124 /* Returns the expected number of loop iterations for LOOP.
125 The average trip count is computed from profile data if it
128 static inline HOST_WIDE_INT
129 avg_loop_niter (struct loop
*loop
)
131 HOST_WIDE_INT niter
= estimated_stmt_executions_int (loop
);
133 return AVG_LOOP_NITER (loop
);
138 /* Representation of the induction variable. */
141 tree base
; /* Initial value of the iv. */
142 tree base_object
; /* A memory object to that the induction variable points. */
143 tree step
; /* Step of the iv (constant only). */
144 tree ssa_name
; /* The ssa name with the value. */
145 bool biv_p
; /* Is it a biv? */
146 bool have_use_for
; /* Do we already have a use for it? */
147 unsigned use_id
; /* The identifier in the use if it is the case. */
150 /* Per-ssa version information (induction variable descriptions, etc.). */
153 tree name
; /* The ssa name. */
154 struct iv
*iv
; /* Induction variable description. */
155 bool has_nonlin_use
; /* For a loop-level invariant, whether it is used in
156 an expression that is not an induction variable. */
157 bool preserve_biv
; /* For the original biv, whether to preserve it. */
158 unsigned inv_id
; /* Id of an invariant. */
164 USE_NONLINEAR_EXPR
, /* Use in a nonlinear expression. */
165 USE_ADDRESS
, /* Use in an address. */
166 USE_COMPARE
/* Use is a compare. */
169 /* Cost of a computation. */
172 int cost
; /* The runtime cost. */
173 unsigned complexity
; /* The estimate of the complexity of the code for
174 the computation (in no concrete units --
175 complexity field should be larger for more
176 complex expressions and addressing modes). */
179 static const comp_cost no_cost
= {0, 0};
180 static const comp_cost infinite_cost
= {INFTY
, INFTY
};
182 /* The candidate - cost pair. */
185 struct iv_cand
*cand
; /* The candidate. */
186 comp_cost cost
; /* The cost. */
187 bitmap depends_on
; /* The list of invariants that have to be
189 tree value
; /* For final value elimination, the expression for
190 the final value of the iv. For iv elimination,
191 the new bound to compare with. */
192 enum tree_code comp
; /* For iv elimination, the comparison. */
193 int inv_expr_id
; /* Loop invariant expression id. */
199 unsigned id
; /* The id of the use. */
200 enum use_type type
; /* Type of the use. */
201 struct iv
*iv
; /* The induction variable it is based on. */
202 gimple stmt
; /* Statement in that it occurs. */
203 tree
*op_p
; /* The place where it occurs. */
204 bitmap related_cands
; /* The set of "related" iv candidates, plus the common
207 unsigned n_map_members
; /* Number of candidates in the cost_map list. */
208 struct cost_pair
*cost_map
;
209 /* The costs wrto the iv candidates. */
211 struct iv_cand
*selected
;
212 /* The selected candidate. */
215 /* The position where the iv is computed. */
218 IP_NORMAL
, /* At the end, just before the exit condition. */
219 IP_END
, /* At the end of the latch block. */
220 IP_BEFORE_USE
, /* Immediately before a specific use. */
221 IP_AFTER_USE
, /* Immediately after a specific use. */
222 IP_ORIGINAL
/* The original biv. */
225 /* The induction variable candidate. */
228 unsigned id
; /* The number of the candidate. */
229 bool important
; /* Whether this is an "important" candidate, i.e. such
230 that it should be considered by all uses. */
231 ENUM_BITFIELD(iv_position
) pos
: 8; /* Where it is computed. */
232 gimple incremented_at
;/* For original biv, the statement where it is
234 tree var_before
; /* The variable used for it before increment. */
235 tree var_after
; /* The variable used for it after increment. */
236 struct iv
*iv
; /* The value of the candidate. NULL for
237 "pseudocandidate" used to indicate the possibility
238 to replace the final value of an iv by direct
239 computation of the value. */
240 unsigned cost
; /* Cost of the candidate. */
241 unsigned cost_step
; /* Cost of the candidate's increment operation. */
242 struct iv_use
*ainc_use
; /* For IP_{BEFORE,AFTER}_USE candidates, the place
243 where it is incremented. */
244 bitmap depends_on
; /* The list of invariants that are used in step of the
248 /* Loop invariant expression hashtable entry. */
249 struct iv_inv_expr_ent
256 /* The data used by the induction variable optimizations. */
258 typedef struct iv_use
*iv_use_p
;
260 typedef struct iv_cand
*iv_cand_p
;
262 /* Hashtable helpers. */
264 struct iv_inv_expr_hasher
: typed_free_remove
<iv_inv_expr_ent
>
266 typedef iv_inv_expr_ent value_type
;
267 typedef iv_inv_expr_ent compare_type
;
268 static inline hashval_t
hash (const value_type
*);
269 static inline bool equal (const value_type
*, const compare_type
*);
272 /* Hash function for loop invariant expressions. */
275 iv_inv_expr_hasher::hash (const value_type
*expr
)
280 /* Hash table equality function for expressions. */
283 iv_inv_expr_hasher::equal (const value_type
*expr1
, const compare_type
*expr2
)
285 return expr1
->hash
== expr2
->hash
286 && operand_equal_p (expr1
->expr
, expr2
->expr
, 0);
291 /* The currently optimized loop. */
292 struct loop
*current_loop
;
294 /* Numbers of iterations for all exits of the current loop. */
295 struct pointer_map_t
*niters
;
297 /* Number of registers used in it. */
300 /* The size of version_info array allocated. */
301 unsigned version_info_size
;
303 /* The array of information for the ssa names. */
304 struct version_info
*version_info
;
306 /* The hashtable of loop invariant expressions created
308 hash_table
<iv_inv_expr_hasher
> inv_expr_tab
;
310 /* Loop invariant expression id. */
313 /* The bitmap of indices in version_info whose value was changed. */
316 /* The uses of induction variables. */
317 vec
<iv_use_p
> iv_uses
;
319 /* The candidates. */
320 vec
<iv_cand_p
> iv_candidates
;
322 /* A bitmap of important candidates. */
323 bitmap important_candidates
;
325 /* The maximum invariant id. */
328 /* Whether to consider just related and important candidates when replacing a
330 bool consider_all_candidates
;
332 /* Are we optimizing for speed? */
335 /* Whether the loop body includes any function calls. */
336 bool body_includes_call
;
338 /* Whether the loop body can only be exited via single exit. */
339 bool loop_single_exit_p
;
342 /* An assignment of iv candidates to uses. */
346 /* The number of uses covered by the assignment. */
349 /* Number of uses that cannot be expressed by the candidates in the set. */
352 /* Candidate assigned to a use, together with the related costs. */
353 struct cost_pair
**cand_for_use
;
355 /* Number of times each candidate is used. */
356 unsigned *n_cand_uses
;
358 /* The candidates used. */
361 /* The number of candidates in the set. */
364 /* Total number of registers needed. */
367 /* Total cost of expressing uses. */
368 comp_cost cand_use_cost
;
370 /* Total cost of candidates. */
373 /* Number of times each invariant is used. */
374 unsigned *n_invariant_uses
;
376 /* The array holding the number of uses of each loop
377 invariant expressions created by ivopt. */
378 unsigned *used_inv_expr
;
380 /* The number of created loop invariants. */
381 unsigned num_used_inv_expr
;
383 /* Total cost of the assignment. */
387 /* Difference of two iv candidate assignments. */
394 /* An old assignment (for rollback purposes). */
395 struct cost_pair
*old_cp
;
397 /* A new assignment. */
398 struct cost_pair
*new_cp
;
400 /* Next change in the list. */
401 struct iv_ca_delta
*next_change
;
404 /* Bound on number of candidates below that all candidates are considered. */
406 #define CONSIDER_ALL_CANDIDATES_BOUND \
407 ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
409 /* If there are more iv occurrences, we just give up (it is quite unlikely that
410 optimizing such a loop would help, and it would take ages). */
412 #define MAX_CONSIDERED_USES \
413 ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
415 /* If there are at most this number of ivs in the set, try removing unnecessary
416 ivs from the set always. */
418 #define ALWAYS_PRUNE_CAND_SET_BOUND \
419 ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
421 /* The list of trees for that the decl_rtl field must be reset is stored
424 static vec
<tree
> decl_rtl_to_reset
;
426 static comp_cost
force_expr_to_var_cost (tree
, bool);
428 /* Number of uses recorded in DATA. */
430 static inline unsigned
431 n_iv_uses (struct ivopts_data
*data
)
433 return data
->iv_uses
.length ();
436 /* Ith use recorded in DATA. */
438 static inline struct iv_use
*
439 iv_use (struct ivopts_data
*data
, unsigned i
)
441 return data
->iv_uses
[i
];
444 /* Number of candidates recorded in DATA. */
446 static inline unsigned
447 n_iv_cands (struct ivopts_data
*data
)
449 return data
->iv_candidates
.length ();
452 /* Ith candidate recorded in DATA. */
454 static inline struct iv_cand
*
455 iv_cand (struct ivopts_data
*data
, unsigned i
)
457 return data
->iv_candidates
[i
];
460 /* The single loop exit if it dominates the latch, NULL otherwise. */
463 single_dom_exit (struct loop
*loop
)
465 edge exit
= single_exit (loop
);
470 if (!just_once_each_iteration_p (loop
, exit
->src
))
476 /* Dumps information about the induction variable IV to FILE. */
479 dump_iv (FILE *file
, struct iv
*iv
)
483 fprintf (file
, "ssa name ");
484 print_generic_expr (file
, iv
->ssa_name
, TDF_SLIM
);
485 fprintf (file
, "\n");
488 fprintf (file
, " type ");
489 print_generic_expr (file
, TREE_TYPE (iv
->base
), TDF_SLIM
);
490 fprintf (file
, "\n");
494 fprintf (file
, " base ");
495 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
496 fprintf (file
, "\n");
498 fprintf (file
, " step ");
499 print_generic_expr (file
, iv
->step
, TDF_SLIM
);
500 fprintf (file
, "\n");
504 fprintf (file
, " invariant ");
505 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
506 fprintf (file
, "\n");
511 fprintf (file
, " base object ");
512 print_generic_expr (file
, iv
->base_object
, TDF_SLIM
);
513 fprintf (file
, "\n");
517 fprintf (file
, " is a biv\n");
520 /* Dumps information about the USE to FILE. */
523 dump_use (FILE *file
, struct iv_use
*use
)
525 fprintf (file
, "use %d\n", use
->id
);
529 case USE_NONLINEAR_EXPR
:
530 fprintf (file
, " generic\n");
534 fprintf (file
, " address\n");
538 fprintf (file
, " compare\n");
545 fprintf (file
, " in statement ");
546 print_gimple_stmt (file
, use
->stmt
, 0, 0);
547 fprintf (file
, "\n");
549 fprintf (file
, " at position ");
551 print_generic_expr (file
, *use
->op_p
, TDF_SLIM
);
552 fprintf (file
, "\n");
554 dump_iv (file
, use
->iv
);
556 if (use
->related_cands
)
558 fprintf (file
, " related candidates ");
559 dump_bitmap (file
, use
->related_cands
);
563 /* Dumps information about the uses to FILE. */
566 dump_uses (FILE *file
, struct ivopts_data
*data
)
571 for (i
= 0; i
< n_iv_uses (data
); i
++)
573 use
= iv_use (data
, i
);
575 dump_use (file
, use
);
576 fprintf (file
, "\n");
580 /* Dumps information about induction variable candidate CAND to FILE. */
583 dump_cand (FILE *file
, struct iv_cand
*cand
)
585 struct iv
*iv
= cand
->iv
;
587 fprintf (file
, "candidate %d%s\n",
588 cand
->id
, cand
->important
? " (important)" : "");
590 if (cand
->depends_on
)
592 fprintf (file
, " depends on ");
593 dump_bitmap (file
, cand
->depends_on
);
598 fprintf (file
, " final value replacement\n");
602 if (cand
->var_before
)
604 fprintf (file
, " var_before ");
605 print_generic_expr (file
, cand
->var_before
, TDF_SLIM
);
606 fprintf (file
, "\n");
610 fprintf (file
, " var_after ");
611 print_generic_expr (file
, cand
->var_after
, TDF_SLIM
);
612 fprintf (file
, "\n");
618 fprintf (file
, " incremented before exit test\n");
622 fprintf (file
, " incremented before use %d\n", cand
->ainc_use
->id
);
626 fprintf (file
, " incremented after use %d\n", cand
->ainc_use
->id
);
630 fprintf (file
, " incremented at end\n");
634 fprintf (file
, " original biv\n");
641 /* Returns the info for ssa version VER. */
643 static inline struct version_info
*
644 ver_info (struct ivopts_data
*data
, unsigned ver
)
646 return data
->version_info
+ ver
;
649 /* Returns the info for ssa name NAME. */
651 static inline struct version_info
*
652 name_info (struct ivopts_data
*data
, tree name
)
654 return ver_info (data
, SSA_NAME_VERSION (name
));
657 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
661 stmt_after_ip_normal_pos (struct loop
*loop
, gimple stmt
)
663 basic_block bb
= ip_normal_pos (loop
), sbb
= gimple_bb (stmt
);
667 if (sbb
== loop
->latch
)
673 return stmt
== last_stmt (bb
);
676 /* Returns true if STMT if after the place where the original induction
677 variable CAND is incremented. If TRUE_IF_EQUAL is set, we return true
678 if the positions are identical. */
681 stmt_after_inc_pos (struct iv_cand
*cand
, gimple stmt
, bool true_if_equal
)
683 basic_block cand_bb
= gimple_bb (cand
->incremented_at
);
684 basic_block stmt_bb
= gimple_bb (stmt
);
686 if (!dominated_by_p (CDI_DOMINATORS
, stmt_bb
, cand_bb
))
689 if (stmt_bb
!= cand_bb
)
693 && gimple_uid (stmt
) == gimple_uid (cand
->incremented_at
))
695 return gimple_uid (stmt
) > gimple_uid (cand
->incremented_at
);
698 /* Returns true if STMT if after the place where the induction variable
699 CAND is incremented in LOOP. */
702 stmt_after_increment (struct loop
*loop
, struct iv_cand
*cand
, gimple stmt
)
710 return stmt_after_ip_normal_pos (loop
, stmt
);
714 return stmt_after_inc_pos (cand
, stmt
, false);
717 return stmt_after_inc_pos (cand
, stmt
, true);
724 /* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
727 abnormal_ssa_name_p (tree exp
)
732 if (TREE_CODE (exp
) != SSA_NAME
)
735 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
) != 0;
738 /* Returns false if BASE or INDEX contains a ssa name that occurs in an
739 abnormal phi node. Callback for for_each_index. */
742 idx_contains_abnormal_ssa_name_p (tree base
, tree
*index
,
743 void *data ATTRIBUTE_UNUSED
)
745 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
747 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 2)))
749 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 3)))
753 return !abnormal_ssa_name_p (*index
);
756 /* Returns true if EXPR contains a ssa name that occurs in an
757 abnormal phi node. */
760 contains_abnormal_ssa_name_p (tree expr
)
763 enum tree_code_class codeclass
;
768 code
= TREE_CODE (expr
);
769 codeclass
= TREE_CODE_CLASS (code
);
771 if (code
== SSA_NAME
)
772 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr
) != 0;
774 if (code
== INTEGER_CST
775 || is_gimple_min_invariant (expr
))
778 if (code
== ADDR_EXPR
)
779 return !for_each_index (&TREE_OPERAND (expr
, 0),
780 idx_contains_abnormal_ssa_name_p
,
783 if (code
== COND_EXPR
)
784 return contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0))
785 || contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1))
786 || contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 2));
792 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1)))
797 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0)))
809 /* Returns the structure describing number of iterations determined from
810 EXIT of DATA->current_loop, or NULL if something goes wrong. */
812 static struct tree_niter_desc
*
813 niter_for_exit (struct ivopts_data
*data
, edge exit
)
815 struct tree_niter_desc
*desc
;
820 data
->niters
= pointer_map_create ();
824 slot
= pointer_map_contains (data
->niters
, exit
);
828 /* Try to determine number of iterations. We cannot safely work with ssa
829 names that appear in phi nodes on abnormal edges, so that we do not
830 create overlapping life ranges for them (PR 27283). */
831 desc
= XNEW (struct tree_niter_desc
);
832 if (!number_of_iterations_exit (data
->current_loop
,
834 || contains_abnormal_ssa_name_p (desc
->niter
))
839 slot
= pointer_map_insert (data
->niters
, exit
);
843 desc
= (struct tree_niter_desc
*) *slot
;
848 /* Returns the structure describing number of iterations determined from
849 single dominating exit of DATA->current_loop, or NULL if something
852 static struct tree_niter_desc
*
853 niter_for_single_dom_exit (struct ivopts_data
*data
)
855 edge exit
= single_dom_exit (data
->current_loop
);
860 return niter_for_exit (data
, exit
);
863 /* Initializes data structures used by the iv optimization pass, stored
867 tree_ssa_iv_optimize_init (struct ivopts_data
*data
)
869 data
->version_info_size
= 2 * num_ssa_names
;
870 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
871 data
->relevant
= BITMAP_ALLOC (NULL
);
872 data
->important_candidates
= BITMAP_ALLOC (NULL
);
873 data
->max_inv_id
= 0;
875 data
->iv_uses
.create (20);
876 data
->iv_candidates
.create (20);
877 data
->inv_expr_tab
.create (10);
878 data
->inv_expr_id
= 0;
879 decl_rtl_to_reset
.create (20);
882 /* Returns a memory object to that EXPR points. In case we are able to
883 determine that it does not point to any such object, NULL is returned. */
886 determine_base_object (tree expr
)
888 enum tree_code code
= TREE_CODE (expr
);
891 /* If this is a pointer casted to any type, we need to determine
892 the base object for the pointer; so handle conversions before
893 throwing away non-pointer expressions. */
894 if (CONVERT_EXPR_P (expr
))
895 return determine_base_object (TREE_OPERAND (expr
, 0));
897 if (!POINTER_TYPE_P (TREE_TYPE (expr
)))
906 obj
= TREE_OPERAND (expr
, 0);
907 base
= get_base_address (obj
);
912 if (TREE_CODE (base
) == MEM_REF
)
913 return determine_base_object (TREE_OPERAND (base
, 0));
915 return fold_convert (ptr_type_node
,
916 build_fold_addr_expr (base
));
918 case POINTER_PLUS_EXPR
:
919 return determine_base_object (TREE_OPERAND (expr
, 0));
923 /* Pointer addition is done solely using POINTER_PLUS_EXPR. */
927 return fold_convert (ptr_type_node
, expr
);
931 /* Allocates an induction variable with given initial value BASE and step STEP
935 alloc_iv (tree base
, tree step
)
937 tree base_object
= base
;
938 struct iv
*iv
= XCNEW (struct iv
);
939 gcc_assert (step
!= NULL_TREE
);
941 /* Lower all address expressions except ones with DECL_P as operand.
943 1) More accurate cost can be computed for address expressions;
944 2) Duplicate candidates won't be created for bases in different
945 forms, like &a[0] and &a. */
946 STRIP_NOPS (base_object
);
947 if (TREE_CODE (base_object
) == ADDR_EXPR
948 && !DECL_P (TREE_OPERAND (base_object
, 0)))
952 base_object
= get_inner_reference_aff (TREE_OPERAND (base_object
, 0),
954 gcc_assert (base_object
!= NULL_TREE
);
955 base_object
= build_fold_addr_expr (base_object
);
956 base
= fold_convert (TREE_TYPE (base
), aff_combination_to_tree (&comb
));
960 iv
->base_object
= determine_base_object (base_object
);
963 iv
->have_use_for
= false;
965 iv
->ssa_name
= NULL_TREE
;
970 /* Sets STEP and BASE for induction variable IV. */
973 set_iv (struct ivopts_data
*data
, tree iv
, tree base
, tree step
)
975 struct version_info
*info
= name_info (data
, iv
);
977 gcc_assert (!info
->iv
);
979 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (iv
));
980 info
->iv
= alloc_iv (base
, step
);
981 info
->iv
->ssa_name
= iv
;
984 /* Finds induction variable declaration for VAR. */
987 get_iv (struct ivopts_data
*data
, tree var
)
990 tree type
= TREE_TYPE (var
);
992 if (!POINTER_TYPE_P (type
)
993 && !INTEGRAL_TYPE_P (type
))
996 if (!name_info (data
, var
)->iv
)
998 bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
1001 || !flow_bb_inside_loop_p (data
->current_loop
, bb
))
1002 set_iv (data
, var
, var
, build_int_cst (type
, 0));
1005 return name_info (data
, var
)->iv
;
1008 /* Determines the step of a biv defined in PHI. Returns NULL if PHI does
1009 not define a simple affine biv with nonzero step. */
1012 determine_biv_step (gimple phi
)
1014 struct loop
*loop
= gimple_bb (phi
)->loop_father
;
1015 tree name
= PHI_RESULT (phi
);
1018 if (virtual_operand_p (name
))
1021 if (!simple_iv (loop
, loop
, name
, &iv
, true))
1024 return integer_zerop (iv
.step
) ? NULL_TREE
: iv
.step
;
1027 /* Finds basic ivs. */
1030 find_bivs (struct ivopts_data
*data
)
1033 tree step
, type
, base
;
1035 struct loop
*loop
= data
->current_loop
;
1036 gimple_stmt_iterator psi
;
1038 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1040 phi
= gsi_stmt (psi
);
1042 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
1045 step
= determine_biv_step (phi
);
1049 base
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1050 base
= expand_simple_operations (base
);
1051 if (contains_abnormal_ssa_name_p (base
)
1052 || contains_abnormal_ssa_name_p (step
))
1055 type
= TREE_TYPE (PHI_RESULT (phi
));
1056 base
= fold_convert (type
, base
);
1059 if (POINTER_TYPE_P (type
))
1060 step
= convert_to_ptrofftype (step
);
1062 step
= fold_convert (type
, step
);
1065 set_iv (data
, PHI_RESULT (phi
), base
, step
);
1072 /* Marks basic ivs. */
1075 mark_bivs (struct ivopts_data
*data
)
1079 struct iv
*iv
, *incr_iv
;
1080 struct loop
*loop
= data
->current_loop
;
1081 basic_block incr_bb
;
1082 gimple_stmt_iterator psi
;
1084 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1086 phi
= gsi_stmt (psi
);
1088 iv
= get_iv (data
, PHI_RESULT (phi
));
1092 var
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
1093 incr_iv
= get_iv (data
, var
);
1097 /* If the increment is in the subloop, ignore it. */
1098 incr_bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
1099 if (incr_bb
->loop_father
!= data
->current_loop
1100 || (incr_bb
->flags
& BB_IRREDUCIBLE_LOOP
))
1104 incr_iv
->biv_p
= true;
1108 /* Checks whether STMT defines a linear induction variable and stores its
1109 parameters to IV. */
1112 find_givs_in_stmt_scev (struct ivopts_data
*data
, gimple stmt
, affine_iv
*iv
)
1115 struct loop
*loop
= data
->current_loop
;
1117 iv
->base
= NULL_TREE
;
1118 iv
->step
= NULL_TREE
;
1120 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1123 lhs
= gimple_assign_lhs (stmt
);
1124 if (TREE_CODE (lhs
) != SSA_NAME
)
1127 if (!simple_iv (loop
, loop_containing_stmt (stmt
), lhs
, iv
, true))
1129 iv
->base
= expand_simple_operations (iv
->base
);
1131 if (contains_abnormal_ssa_name_p (iv
->base
)
1132 || contains_abnormal_ssa_name_p (iv
->step
))
1135 /* If STMT could throw, then do not consider STMT as defining a GIV.
1136 While this will suppress optimizations, we can not safely delete this
1137 GIV and associated statements, even if it appears it is not used. */
1138 if (stmt_could_throw_p (stmt
))
1144 /* Finds general ivs in statement STMT. */
1147 find_givs_in_stmt (struct ivopts_data
*data
, gimple stmt
)
1151 if (!find_givs_in_stmt_scev (data
, stmt
, &iv
))
1154 set_iv (data
, gimple_assign_lhs (stmt
), iv
.base
, iv
.step
);
1157 /* Finds general ivs in basic block BB. */
1160 find_givs_in_bb (struct ivopts_data
*data
, basic_block bb
)
1162 gimple_stmt_iterator bsi
;
1164 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1165 find_givs_in_stmt (data
, gsi_stmt (bsi
));
1168 /* Finds general ivs. */
1171 find_givs (struct ivopts_data
*data
)
1173 struct loop
*loop
= data
->current_loop
;
1174 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1177 for (i
= 0; i
< loop
->num_nodes
; i
++)
1178 find_givs_in_bb (data
, body
[i
]);
1182 /* For each ssa name defined in LOOP determines whether it is an induction
1183 variable and if so, its initial value and step. */
1186 find_induction_variables (struct ivopts_data
*data
)
1191 if (!find_bivs (data
))
1197 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1199 struct tree_niter_desc
*niter
= niter_for_single_dom_exit (data
);
1203 fprintf (dump_file
, " number of iterations ");
1204 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1205 if (!integer_zerop (niter
->may_be_zero
))
1207 fprintf (dump_file
, "; zero if ");
1208 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1210 fprintf (dump_file
, "\n\n");
1213 fprintf (dump_file
, "Induction variables:\n\n");
1215 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1217 if (ver_info (data
, i
)->iv
)
1218 dump_iv (dump_file
, ver_info (data
, i
)->iv
);
1225 /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV. */
1227 static struct iv_use
*
1228 record_use (struct ivopts_data
*data
, tree
*use_p
, struct iv
*iv
,
1229 gimple stmt
, enum use_type use_type
)
1231 struct iv_use
*use
= XCNEW (struct iv_use
);
1233 use
->id
= n_iv_uses (data
);
1234 use
->type
= use_type
;
1238 use
->related_cands
= BITMAP_ALLOC (NULL
);
1240 /* To avoid showing ssa name in the dumps, if it was not reset by the
1242 iv
->ssa_name
= NULL_TREE
;
1244 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1245 dump_use (dump_file
, use
);
1247 data
->iv_uses
.safe_push (use
);
1252 /* Checks whether OP is a loop-level invariant and if so, records it.
1253 NONLINEAR_USE is true if the invariant is used in a way we do not
1254 handle specially. */
1257 record_invariant (struct ivopts_data
*data
, tree op
, bool nonlinear_use
)
1260 struct version_info
*info
;
1262 if (TREE_CODE (op
) != SSA_NAME
1263 || virtual_operand_p (op
))
1266 bb
= gimple_bb (SSA_NAME_DEF_STMT (op
));
1268 && flow_bb_inside_loop_p (data
->current_loop
, bb
))
1271 info
= name_info (data
, op
);
1273 info
->has_nonlin_use
|= nonlinear_use
;
1275 info
->inv_id
= ++data
->max_inv_id
;
1276 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (op
));
1279 /* Checks whether the use OP is interesting and if so, records it. */
1281 static struct iv_use
*
1282 find_interesting_uses_op (struct ivopts_data
*data
, tree op
)
1289 if (TREE_CODE (op
) != SSA_NAME
)
1292 iv
= get_iv (data
, op
);
1296 if (iv
->have_use_for
)
1298 use
= iv_use (data
, iv
->use_id
);
1300 gcc_assert (use
->type
== USE_NONLINEAR_EXPR
);
1304 if (integer_zerop (iv
->step
))
1306 record_invariant (data
, op
, true);
1309 iv
->have_use_for
= true;
1311 civ
= XNEW (struct iv
);
1314 stmt
= SSA_NAME_DEF_STMT (op
);
1315 gcc_assert (gimple_code (stmt
) == GIMPLE_PHI
1316 || is_gimple_assign (stmt
));
1318 use
= record_use (data
, NULL
, civ
, stmt
, USE_NONLINEAR_EXPR
);
1319 iv
->use_id
= use
->id
;
1324 /* Given a condition in statement STMT, checks whether it is a compare
1325 of an induction variable and an invariant. If this is the case,
1326 CONTROL_VAR is set to location of the iv, BOUND to the location of
1327 the invariant, IV_VAR and IV_BOUND are set to the corresponding
1328 induction variable descriptions, and true is returned. If this is not
1329 the case, CONTROL_VAR and BOUND are set to the arguments of the
1330 condition and false is returned. */
1333 extract_cond_operands (struct ivopts_data
*data
, gimple stmt
,
1334 tree
**control_var
, tree
**bound
,
1335 struct iv
**iv_var
, struct iv
**iv_bound
)
1337 /* The objects returned when COND has constant operands. */
1338 static struct iv const_iv
;
1340 tree
*op0
= &zero
, *op1
= &zero
, *tmp_op
;
1341 struct iv
*iv0
= &const_iv
, *iv1
= &const_iv
, *tmp_iv
;
1344 if (gimple_code (stmt
) == GIMPLE_COND
)
1346 op0
= gimple_cond_lhs_ptr (stmt
);
1347 op1
= gimple_cond_rhs_ptr (stmt
);
1351 op0
= gimple_assign_rhs1_ptr (stmt
);
1352 op1
= gimple_assign_rhs2_ptr (stmt
);
1355 zero
= integer_zero_node
;
1356 const_iv
.step
= integer_zero_node
;
1358 if (TREE_CODE (*op0
) == SSA_NAME
)
1359 iv0
= get_iv (data
, *op0
);
1360 if (TREE_CODE (*op1
) == SSA_NAME
)
1361 iv1
= get_iv (data
, *op1
);
1363 /* Exactly one of the compared values must be an iv, and the other one must
1368 if (integer_zerop (iv0
->step
))
1370 /* Control variable may be on the other side. */
1371 tmp_op
= op0
; op0
= op1
; op1
= tmp_op
;
1372 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
1374 ret
= !integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
);
1378 *control_var
= op0
;;
1389 /* Checks whether the condition in STMT is interesting and if so,
1393 find_interesting_uses_cond (struct ivopts_data
*data
, gimple stmt
)
1395 tree
*var_p
, *bound_p
;
1396 struct iv
*var_iv
, *civ
;
1398 if (!extract_cond_operands (data
, stmt
, &var_p
, &bound_p
, &var_iv
, NULL
))
1400 find_interesting_uses_op (data
, *var_p
);
1401 find_interesting_uses_op (data
, *bound_p
);
1405 civ
= XNEW (struct iv
);
1407 record_use (data
, NULL
, civ
, stmt
, USE_COMPARE
);
1410 /* Returns the outermost loop EXPR is obviously invariant in
1411 relative to the loop LOOP, i.e. if all its operands are defined
1412 outside of the returned loop. Returns NULL if EXPR is not
1413 even obviously invariant in LOOP. */
1416 outermost_invariant_loop_for_expr (struct loop
*loop
, tree expr
)
1421 if (is_gimple_min_invariant (expr
))
1422 return current_loops
->tree_root
;
1424 if (TREE_CODE (expr
) == SSA_NAME
)
1426 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
1429 if (flow_bb_inside_loop_p (loop
, def_bb
))
1431 return superloop_at_depth (loop
,
1432 loop_depth (def_bb
->loop_father
) + 1);
1435 return current_loops
->tree_root
;
1441 unsigned maxdepth
= 0;
1442 len
= TREE_OPERAND_LENGTH (expr
);
1443 for (i
= 0; i
< len
; i
++)
1445 struct loop
*ivloop
;
1446 if (!TREE_OPERAND (expr
, i
))
1449 ivloop
= outermost_invariant_loop_for_expr (loop
, TREE_OPERAND (expr
, i
));
1452 maxdepth
= MAX (maxdepth
, loop_depth (ivloop
));
1455 return superloop_at_depth (loop
, maxdepth
);
1458 /* Returns true if expression EXPR is obviously invariant in LOOP,
1459 i.e. if all its operands are defined outside of the LOOP. LOOP
1460 should not be the function body. */
1463 expr_invariant_in_loop_p (struct loop
*loop
, tree expr
)
1468 gcc_assert (loop_depth (loop
) > 0);
1470 if (is_gimple_min_invariant (expr
))
1473 if (TREE_CODE (expr
) == SSA_NAME
)
1475 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
1477 && flow_bb_inside_loop_p (loop
, def_bb
))
1486 len
= TREE_OPERAND_LENGTH (expr
);
1487 for (i
= 0; i
< len
; i
++)
1488 if (TREE_OPERAND (expr
, i
)
1489 && !expr_invariant_in_loop_p (loop
, TREE_OPERAND (expr
, i
)))
1495 /* Cumulates the steps of indices into DATA and replaces their values with the
1496 initial ones. Returns false when the value of the index cannot be determined.
1497 Callback for for_each_index. */
1499 struct ifs_ivopts_data
1501 struct ivopts_data
*ivopts_data
;
1507 idx_find_step (tree base
, tree
*idx
, void *data
)
1509 struct ifs_ivopts_data
*dta
= (struct ifs_ivopts_data
*) data
;
1511 tree step
, iv_base
, iv_step
, lbound
, off
;
1512 struct loop
*loop
= dta
->ivopts_data
->current_loop
;
1514 /* If base is a component ref, require that the offset of the reference
1516 if (TREE_CODE (base
) == COMPONENT_REF
)
1518 off
= component_ref_field_offset (base
);
1519 return expr_invariant_in_loop_p (loop
, off
);
1522 /* If base is array, first check whether we will be able to move the
1523 reference out of the loop (in order to take its address in strength
1524 reduction). In order for this to work we need both lower bound
1525 and step to be loop invariants. */
1526 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
1528 /* Moreover, for a range, the size needs to be invariant as well. */
1529 if (TREE_CODE (base
) == ARRAY_RANGE_REF
1530 && !expr_invariant_in_loop_p (loop
, TYPE_SIZE (TREE_TYPE (base
))))
1533 step
= array_ref_element_size (base
);
1534 lbound
= array_ref_low_bound (base
);
1536 if (!expr_invariant_in_loop_p (loop
, step
)
1537 || !expr_invariant_in_loop_p (loop
, lbound
))
1541 if (TREE_CODE (*idx
) != SSA_NAME
)
1544 iv
= get_iv (dta
->ivopts_data
, *idx
);
1548 /* XXX We produce for a base of *D42 with iv->base being &x[0]
1549 *&x[0], which is not folded and does not trigger the
1550 ARRAY_REF path below. */
1553 if (integer_zerop (iv
->step
))
1556 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
1558 step
= array_ref_element_size (base
);
1560 /* We only handle addresses whose step is an integer constant. */
1561 if (TREE_CODE (step
) != INTEGER_CST
)
1565 /* The step for pointer arithmetics already is 1 byte. */
1566 step
= size_one_node
;
1570 if (!convert_affine_scev (dta
->ivopts_data
->current_loop
,
1571 sizetype
, &iv_base
, &iv_step
, dta
->stmt
,
1574 /* The index might wrap. */
1578 step
= fold_build2 (MULT_EXPR
, sizetype
, step
, iv_step
);
1579 dta
->step
= fold_build2 (PLUS_EXPR
, sizetype
, dta
->step
, step
);
1584 /* Records use in index IDX. Callback for for_each_index. Ivopts data
1585 object is passed to it in DATA. */
1588 idx_record_use (tree base
, tree
*idx
,
1591 struct ivopts_data
*data
= (struct ivopts_data
*) vdata
;
1592 find_interesting_uses_op (data
, *idx
);
1593 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
1595 find_interesting_uses_op (data
, array_ref_element_size (base
));
1596 find_interesting_uses_op (data
, array_ref_low_bound (base
));
1601 /* If we can prove that TOP = cst * BOT for some constant cst,
1602 store cst to MUL and return true. Otherwise return false.
1603 The returned value is always sign-extended, regardless of the
1604 signedness of TOP and BOT. */
1607 constant_multiple_of (tree top
, tree bot
, widest_int
*mul
)
1610 enum tree_code code
;
1611 unsigned precision
= TYPE_PRECISION (TREE_TYPE (top
));
1612 widest_int res
, p0
, p1
;
1617 if (operand_equal_p (top
, bot
, 0))
1623 code
= TREE_CODE (top
);
1627 mby
= TREE_OPERAND (top
, 1);
1628 if (TREE_CODE (mby
) != INTEGER_CST
)
1631 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &res
))
1634 *mul
= wi::sext (res
* wi::to_widest (mby
), precision
);
1639 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &p0
)
1640 || !constant_multiple_of (TREE_OPERAND (top
, 1), bot
, &p1
))
1643 if (code
== MINUS_EXPR
)
1645 *mul
= wi::sext (p0
+ p1
, precision
);
1649 if (TREE_CODE (bot
) != INTEGER_CST
)
1652 p0
= widest_int::from (top
, SIGNED
);
1653 p1
= widest_int::from (bot
, SIGNED
);
1656 *mul
= wi::sext (wi::divmod_trunc (p0
, p1
, SIGNED
, &res
), precision
);
1664 /* Returns true if memory reference REF with step STEP may be unaligned. */
1667 may_be_unaligned_p (tree ref
, tree step
)
1671 HOST_WIDE_INT bitsize
;
1672 HOST_WIDE_INT bitpos
;
1674 enum machine_mode mode
;
1675 int unsignedp
, volatilep
;
1676 unsigned base_align
;
1678 /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
1679 thus they are not misaligned. */
1680 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
1683 /* The test below is basically copy of what expr.c:normal_inner_ref
1684 does to check whether the object must be loaded by parts when
1685 STRICT_ALIGNMENT is true. */
1686 base
= get_inner_reference (ref
, &bitsize
, &bitpos
, &toffset
, &mode
,
1687 &unsignedp
, &volatilep
, true);
1688 base_type
= TREE_TYPE (base
);
1689 base_align
= get_object_alignment (base
);
1690 base_align
= MAX (base_align
, TYPE_ALIGN (base_type
));
1692 if (mode
!= BLKmode
)
1694 unsigned mode_align
= GET_MODE_ALIGNMENT (mode
);
1696 if (base_align
< mode_align
1697 || (bitpos
% mode_align
) != 0
1698 || (bitpos
% BITS_PER_UNIT
) != 0)
1702 && (highest_pow2_factor (toffset
) * BITS_PER_UNIT
) < mode_align
)
1705 if ((highest_pow2_factor (step
) * BITS_PER_UNIT
) < mode_align
)
1712 /* Return true if EXPR may be non-addressable. */
1715 may_be_nonaddressable_p (tree expr
)
1717 switch (TREE_CODE (expr
))
1719 case TARGET_MEM_REF
:
1720 /* TARGET_MEM_REFs are translated directly to valid MEMs on the
1721 target, thus they are always addressable. */
1725 return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr
, 1))
1726 || may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1728 case VIEW_CONVERT_EXPR
:
1729 /* This kind of view-conversions may wrap non-addressable objects
1730 and make them look addressable. After some processing the
1731 non-addressability may be uncovered again, causing ADDR_EXPRs
1732 of inappropriate objects to be built. */
1733 if (is_gimple_reg (TREE_OPERAND (expr
, 0))
1734 || !is_gimple_addressable (TREE_OPERAND (expr
, 0)))
1737 /* ... fall through ... */
1740 case ARRAY_RANGE_REF
:
1741 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1753 /* Finds addresses in *OP_P inside STMT. */
1756 find_interesting_uses_address (struct ivopts_data
*data
, gimple stmt
, tree
*op_p
)
1758 tree base
= *op_p
, step
= size_zero_node
;
1760 struct ifs_ivopts_data ifs_ivopts_data
;
1762 /* Do not play with volatile memory references. A bit too conservative,
1763 perhaps, but safe. */
1764 if (gimple_has_volatile_ops (stmt
))
1767 /* Ignore bitfields for now. Not really something terribly complicated
1769 if (TREE_CODE (base
) == BIT_FIELD_REF
)
1772 base
= unshare_expr (base
);
1774 if (TREE_CODE (base
) == TARGET_MEM_REF
)
1776 tree type
= build_pointer_type (TREE_TYPE (base
));
1780 && TREE_CODE (TMR_BASE (base
)) == SSA_NAME
)
1782 civ
= get_iv (data
, TMR_BASE (base
));
1786 TMR_BASE (base
) = civ
->base
;
1789 if (TMR_INDEX2 (base
)
1790 && TREE_CODE (TMR_INDEX2 (base
)) == SSA_NAME
)
1792 civ
= get_iv (data
, TMR_INDEX2 (base
));
1796 TMR_INDEX2 (base
) = civ
->base
;
1799 if (TMR_INDEX (base
)
1800 && TREE_CODE (TMR_INDEX (base
)) == SSA_NAME
)
1802 civ
= get_iv (data
, TMR_INDEX (base
));
1806 TMR_INDEX (base
) = civ
->base
;
1811 if (TMR_STEP (base
))
1812 astep
= fold_build2 (MULT_EXPR
, type
, TMR_STEP (base
), astep
);
1814 step
= fold_build2 (PLUS_EXPR
, type
, step
, astep
);
1818 if (integer_zerop (step
))
1820 base
= tree_mem_ref_addr (type
, base
);
1824 ifs_ivopts_data
.ivopts_data
= data
;
1825 ifs_ivopts_data
.stmt
= stmt
;
1826 ifs_ivopts_data
.step
= size_zero_node
;
1827 if (!for_each_index (&base
, idx_find_step
, &ifs_ivopts_data
)
1828 || integer_zerop (ifs_ivopts_data
.step
))
1830 step
= ifs_ivopts_data
.step
;
1832 /* Check that the base expression is addressable. This needs
1833 to be done after substituting bases of IVs into it. */
1834 if (may_be_nonaddressable_p (base
))
1837 /* Moreover, on strict alignment platforms, check that it is
1838 sufficiently aligned. */
1839 if (STRICT_ALIGNMENT
&& may_be_unaligned_p (base
, step
))
1842 base
= build_fold_addr_expr (base
);
1844 /* Substituting bases of IVs into the base expression might
1845 have caused folding opportunities. */
1846 if (TREE_CODE (base
) == ADDR_EXPR
)
1848 tree
*ref
= &TREE_OPERAND (base
, 0);
1849 while (handled_component_p (*ref
))
1850 ref
= &TREE_OPERAND (*ref
, 0);
1851 if (TREE_CODE (*ref
) == MEM_REF
)
1853 tree tem
= fold_binary (MEM_REF
, TREE_TYPE (*ref
),
1854 TREE_OPERAND (*ref
, 0),
1855 TREE_OPERAND (*ref
, 1));
1862 civ
= alloc_iv (base
, step
);
1863 record_use (data
, op_p
, civ
, stmt
, USE_ADDRESS
);
1867 for_each_index (op_p
, idx_record_use
, data
);
1870 /* Finds and records invariants used in STMT. */
1873 find_invariants_stmt (struct ivopts_data
*data
, gimple stmt
)
1876 use_operand_p use_p
;
1879 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1881 op
= USE_FROM_PTR (use_p
);
1882 record_invariant (data
, op
, false);
1886 /* Finds interesting uses of induction variables in the statement STMT. */
1889 find_interesting_uses_stmt (struct ivopts_data
*data
, gimple stmt
)
1892 tree op
, *lhs
, *rhs
;
1894 use_operand_p use_p
;
1895 enum tree_code code
;
1897 find_invariants_stmt (data
, stmt
);
1899 if (gimple_code (stmt
) == GIMPLE_COND
)
1901 find_interesting_uses_cond (data
, stmt
);
1905 if (is_gimple_assign (stmt
))
1907 lhs
= gimple_assign_lhs_ptr (stmt
);
1908 rhs
= gimple_assign_rhs1_ptr (stmt
);
1910 if (TREE_CODE (*lhs
) == SSA_NAME
)
1912 /* If the statement defines an induction variable, the uses are not
1913 interesting by themselves. */
1915 iv
= get_iv (data
, *lhs
);
1917 if (iv
&& !integer_zerop (iv
->step
))
1921 code
= gimple_assign_rhs_code (stmt
);
1922 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
1923 && (REFERENCE_CLASS_P (*rhs
)
1924 || is_gimple_val (*rhs
)))
1926 if (REFERENCE_CLASS_P (*rhs
))
1927 find_interesting_uses_address (data
, stmt
, rhs
);
1929 find_interesting_uses_op (data
, *rhs
);
1931 if (REFERENCE_CLASS_P (*lhs
))
1932 find_interesting_uses_address (data
, stmt
, lhs
);
1935 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
1937 find_interesting_uses_cond (data
, stmt
);
1941 /* TODO -- we should also handle address uses of type
1943 memory = call (whatever);
1950 if (gimple_code (stmt
) == GIMPLE_PHI
1951 && gimple_bb (stmt
) == data
->current_loop
->header
)
1953 iv
= get_iv (data
, PHI_RESULT (stmt
));
1955 if (iv
&& !integer_zerop (iv
->step
))
1959 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
1961 op
= USE_FROM_PTR (use_p
);
1963 if (TREE_CODE (op
) != SSA_NAME
)
1966 iv
= get_iv (data
, op
);
1970 find_interesting_uses_op (data
, op
);
1974 /* Finds interesting uses of induction variables outside of loops
1975 on loop exit edge EXIT. */
1978 find_interesting_uses_outside (struct ivopts_data
*data
, edge exit
)
1981 gimple_stmt_iterator psi
;
1984 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
1986 phi
= gsi_stmt (psi
);
1987 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1988 if (!virtual_operand_p (def
))
1989 find_interesting_uses_op (data
, def
);
1993 /* Finds uses of the induction variables that are interesting. */
1996 find_interesting_uses (struct ivopts_data
*data
)
1999 gimple_stmt_iterator bsi
;
2000 basic_block
*body
= get_loop_body (data
->current_loop
);
2002 struct version_info
*info
;
2005 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2006 fprintf (dump_file
, "Uses:\n\n");
2008 for (i
= 0; i
< data
->current_loop
->num_nodes
; i
++)
2013 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2014 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2015 && !flow_bb_inside_loop_p (data
->current_loop
, e
->dest
))
2016 find_interesting_uses_outside (data
, e
);
2018 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2019 find_interesting_uses_stmt (data
, gsi_stmt (bsi
));
2020 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2021 if (!is_gimple_debug (gsi_stmt (bsi
)))
2022 find_interesting_uses_stmt (data
, gsi_stmt (bsi
));
2025 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2029 fprintf (dump_file
, "\n");
2031 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
2033 info
= ver_info (data
, i
);
2036 fprintf (dump_file
, " ");
2037 print_generic_expr (dump_file
, info
->name
, TDF_SLIM
);
2038 fprintf (dump_file
, " is invariant (%d)%s\n",
2039 info
->inv_id
, info
->has_nonlin_use
? "" : ", eliminable");
2043 fprintf (dump_file
, "\n");
2049 /* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
2050 is true, assume we are inside an address. If TOP_COMPREF is true, assume
2051 we are at the top-level of the processed address. */
2054 strip_offset_1 (tree expr
, bool inside_addr
, bool top_compref
,
2055 HOST_WIDE_INT
*offset
)
2057 tree op0
= NULL_TREE
, op1
= NULL_TREE
, tmp
, step
;
2058 enum tree_code code
;
2059 tree type
, orig_type
= TREE_TYPE (expr
);
2060 HOST_WIDE_INT off0
, off1
, st
;
2061 tree orig_expr
= expr
;
2065 type
= TREE_TYPE (expr
);
2066 code
= TREE_CODE (expr
);
2072 if (!cst_and_fits_in_hwi (expr
)
2073 || integer_zerop (expr
))
2076 *offset
= int_cst_value (expr
);
2077 return build_int_cst (orig_type
, 0);
2079 case POINTER_PLUS_EXPR
:
2082 op0
= TREE_OPERAND (expr
, 0);
2083 op1
= TREE_OPERAND (expr
, 1);
2085 op0
= strip_offset_1 (op0
, false, false, &off0
);
2086 op1
= strip_offset_1 (op1
, false, false, &off1
);
2088 *offset
= (code
== MINUS_EXPR
? off0
- off1
: off0
+ off1
);
2089 if (op0
== TREE_OPERAND (expr
, 0)
2090 && op1
== TREE_OPERAND (expr
, 1))
2093 if (integer_zerop (op1
))
2095 else if (integer_zerop (op0
))
2097 if (code
== MINUS_EXPR
)
2098 expr
= fold_build1 (NEGATE_EXPR
, type
, op1
);
2103 expr
= fold_build2 (code
, type
, op0
, op1
);
2105 return fold_convert (orig_type
, expr
);
2108 op1
= TREE_OPERAND (expr
, 1);
2109 if (!cst_and_fits_in_hwi (op1
))
2112 op0
= TREE_OPERAND (expr
, 0);
2113 op0
= strip_offset_1 (op0
, false, false, &off0
);
2114 if (op0
== TREE_OPERAND (expr
, 0))
2117 *offset
= off0
* int_cst_value (op1
);
2118 if (integer_zerop (op0
))
2121 expr
= fold_build2 (MULT_EXPR
, type
, op0
, op1
);
2123 return fold_convert (orig_type
, expr
);
2126 case ARRAY_RANGE_REF
:
2130 step
= array_ref_element_size (expr
);
2131 if (!cst_and_fits_in_hwi (step
))
2134 st
= int_cst_value (step
);
2135 op1
= TREE_OPERAND (expr
, 1);
2136 op1
= strip_offset_1 (op1
, false, false, &off1
);
2137 *offset
= off1
* st
;
2140 && integer_zerop (op1
))
2142 /* Strip the component reference completely. */
2143 op0
= TREE_OPERAND (expr
, 0);
2144 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
2157 tmp
= component_ref_field_offset (expr
);
2158 field
= TREE_OPERAND (expr
, 1);
2160 && cst_and_fits_in_hwi (tmp
)
2161 && cst_and_fits_in_hwi (DECL_FIELD_BIT_OFFSET (field
)))
2163 HOST_WIDE_INT boffset
, abs_off
;
2165 /* Strip the component reference completely. */
2166 op0
= TREE_OPERAND (expr
, 0);
2167 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
2168 boffset
= int_cst_value (DECL_FIELD_BIT_OFFSET (field
));
2169 abs_off
= abs_hwi (boffset
) / BITS_PER_UNIT
;
2173 *offset
= off0
+ int_cst_value (tmp
) + abs_off
;
2180 op0
= TREE_OPERAND (expr
, 0);
2181 op0
= strip_offset_1 (op0
, true, true, &off0
);
2184 if (op0
== TREE_OPERAND (expr
, 0))
2187 expr
= build_fold_addr_expr (op0
);
2188 return fold_convert (orig_type
, expr
);
2191 /* ??? Offset operand? */
2192 inside_addr
= false;
2199 /* Default handling of expressions for that we want to recurse into
2200 the first operand. */
2201 op0
= TREE_OPERAND (expr
, 0);
2202 op0
= strip_offset_1 (op0
, inside_addr
, false, &off0
);
2205 if (op0
== TREE_OPERAND (expr
, 0)
2206 && (!op1
|| op1
== TREE_OPERAND (expr
, 1)))
2209 expr
= copy_node (expr
);
2210 TREE_OPERAND (expr
, 0) = op0
;
2212 TREE_OPERAND (expr
, 1) = op1
;
2214 /* Inside address, we might strip the top level component references,
2215 thus changing type of the expression. Handling of ADDR_EXPR
2217 expr
= fold_convert (orig_type
, expr
);
2222 /* Strips constant offsets from EXPR and stores them to OFFSET. */
2225 strip_offset (tree expr
, unsigned HOST_WIDE_INT
*offset
)
2228 tree core
= strip_offset_1 (expr
, false, false, &off
);
2233 /* Returns variant of TYPE that can be used as base for different uses.
2234 We return unsigned type with the same precision, which avoids problems
2238 generic_type_for (tree type
)
2240 if (POINTER_TYPE_P (type
))
2241 return unsigned_type_for (type
);
2243 if (TYPE_UNSIGNED (type
))
2246 return unsigned_type_for (type
);
2249 /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
2250 the bitmap to that we should store it. */
2252 static struct ivopts_data
*fd_ivopts_data
;
2254 find_depends (tree
*expr_p
, int *ws ATTRIBUTE_UNUSED
, void *data
)
2256 bitmap
*depends_on
= (bitmap
*) data
;
2257 struct version_info
*info
;
2259 if (TREE_CODE (*expr_p
) != SSA_NAME
)
2261 info
= name_info (fd_ivopts_data
, *expr_p
);
2263 if (!info
->inv_id
|| info
->has_nonlin_use
)
2267 *depends_on
= BITMAP_ALLOC (NULL
);
2268 bitmap_set_bit (*depends_on
, info
->inv_id
);
2273 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2274 position to POS. If USE is not NULL, the candidate is set as related to
2275 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
2276 replacement of the final value of the iv by a direct computation. */
2278 static struct iv_cand
*
2279 add_candidate_1 (struct ivopts_data
*data
,
2280 tree base
, tree step
, bool important
, enum iv_position pos
,
2281 struct iv_use
*use
, gimple incremented_at
)
2284 struct iv_cand
*cand
= NULL
;
2285 tree type
, orig_type
;
2287 /* For non-original variables, make sure their values are computed in a type
2288 that does not invoke undefined behavior on overflows (since in general,
2289 we cannot prove that these induction variables are non-wrapping). */
2290 if (pos
!= IP_ORIGINAL
)
2292 orig_type
= TREE_TYPE (base
);
2293 type
= generic_type_for (orig_type
);
2294 if (type
!= orig_type
)
2296 base
= fold_convert (type
, base
);
2297 step
= fold_convert (type
, step
);
2301 for (i
= 0; i
< n_iv_cands (data
); i
++)
2303 cand
= iv_cand (data
, i
);
2305 if (cand
->pos
!= pos
)
2308 if (cand
->incremented_at
!= incremented_at
2309 || ((pos
== IP_AFTER_USE
|| pos
== IP_BEFORE_USE
)
2310 && cand
->ainc_use
!= use
))
2324 if (operand_equal_p (base
, cand
->iv
->base
, 0)
2325 && operand_equal_p (step
, cand
->iv
->step
, 0)
2326 && (TYPE_PRECISION (TREE_TYPE (base
))
2327 == TYPE_PRECISION (TREE_TYPE (cand
->iv
->base
))))
2331 if (i
== n_iv_cands (data
))
2333 cand
= XCNEW (struct iv_cand
);
2339 cand
->iv
= alloc_iv (base
, step
);
2342 if (pos
!= IP_ORIGINAL
&& cand
->iv
)
2344 cand
->var_before
= create_tmp_var_raw (TREE_TYPE (base
), "ivtmp");
2345 cand
->var_after
= cand
->var_before
;
2347 cand
->important
= important
;
2348 cand
->incremented_at
= incremented_at
;
2349 data
->iv_candidates
.safe_push (cand
);
2352 && TREE_CODE (step
) != INTEGER_CST
)
2354 fd_ivopts_data
= data
;
2355 walk_tree (&step
, find_depends
, &cand
->depends_on
, NULL
);
2358 if (pos
== IP_AFTER_USE
|| pos
== IP_BEFORE_USE
)
2359 cand
->ainc_use
= use
;
2361 cand
->ainc_use
= NULL
;
2363 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2364 dump_cand (dump_file
, cand
);
2367 if (important
&& !cand
->important
)
2369 cand
->important
= true;
2370 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2371 fprintf (dump_file
, "Candidate %d is important\n", cand
->id
);
2376 bitmap_set_bit (use
->related_cands
, i
);
2377 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2378 fprintf (dump_file
, "Candidate %d is related to use %d\n",
2385 /* Returns true if incrementing the induction variable at the end of the LOOP
2388 The purpose is to avoid splitting latch edge with a biv increment, thus
2389 creating a jump, possibly confusing other optimization passes and leaving
2390 less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS
2391 is not available (so we do not have a better alternative), or if the latch
2392 edge is already nonempty. */
2395 allow_ip_end_pos_p (struct loop
*loop
)
2397 if (!ip_normal_pos (loop
))
2400 if (!empty_block_p (ip_end_pos (loop
)))
2406 /* If possible, adds autoincrement candidates BASE + STEP * i based on use USE.
2407 Important field is set to IMPORTANT. */
2410 add_autoinc_candidates (struct ivopts_data
*data
, tree base
, tree step
,
2411 bool important
, struct iv_use
*use
)
2413 basic_block use_bb
= gimple_bb (use
->stmt
);
2414 enum machine_mode mem_mode
;
2415 unsigned HOST_WIDE_INT cstepi
;
2417 /* If we insert the increment in any position other than the standard
2418 ones, we must ensure that it is incremented once per iteration.
2419 It must not be in an inner nested loop, or one side of an if
2421 if (use_bb
->loop_father
!= data
->current_loop
2422 || !dominated_by_p (CDI_DOMINATORS
, data
->current_loop
->latch
, use_bb
)
2423 || stmt_could_throw_p (use
->stmt
)
2424 || !cst_and_fits_in_hwi (step
))
2427 cstepi
= int_cst_value (step
);
2429 mem_mode
= TYPE_MODE (TREE_TYPE (*use
->op_p
));
2430 if (((USE_LOAD_PRE_INCREMENT (mem_mode
)
2431 || USE_STORE_PRE_INCREMENT (mem_mode
))
2432 && GET_MODE_SIZE (mem_mode
) == cstepi
)
2433 || ((USE_LOAD_PRE_DECREMENT (mem_mode
)
2434 || USE_STORE_PRE_DECREMENT (mem_mode
))
2435 && GET_MODE_SIZE (mem_mode
) == -cstepi
))
2437 enum tree_code code
= MINUS_EXPR
;
2439 tree new_step
= step
;
2441 if (POINTER_TYPE_P (TREE_TYPE (base
)))
2443 new_step
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (step
), step
);
2444 code
= POINTER_PLUS_EXPR
;
2447 new_step
= fold_convert (TREE_TYPE (base
), new_step
);
2448 new_base
= fold_build2 (code
, TREE_TYPE (base
), base
, new_step
);
2449 add_candidate_1 (data
, new_base
, step
, important
, IP_BEFORE_USE
, use
,
2452 if (((USE_LOAD_POST_INCREMENT (mem_mode
)
2453 || USE_STORE_POST_INCREMENT (mem_mode
))
2454 && GET_MODE_SIZE (mem_mode
) == cstepi
)
2455 || ((USE_LOAD_POST_DECREMENT (mem_mode
)
2456 || USE_STORE_POST_DECREMENT (mem_mode
))
2457 && GET_MODE_SIZE (mem_mode
) == -cstepi
))
2459 add_candidate_1 (data
, base
, step
, important
, IP_AFTER_USE
, use
,
2464 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2465 position to POS. If USE is not NULL, the candidate is set as related to
2466 it. The candidate computation is scheduled on all available positions. */
2469 add_candidate (struct ivopts_data
*data
,
2470 tree base
, tree step
, bool important
, struct iv_use
*use
)
2472 if (ip_normal_pos (data
->current_loop
))
2473 add_candidate_1 (data
, base
, step
, important
, IP_NORMAL
, use
, NULL
);
2474 if (ip_end_pos (data
->current_loop
)
2475 && allow_ip_end_pos_p (data
->current_loop
))
2476 add_candidate_1 (data
, base
, step
, important
, IP_END
, use
, NULL
);
2478 if (use
!= NULL
&& use
->type
== USE_ADDRESS
)
2479 add_autoinc_candidates (data
, base
, step
, important
, use
);
2482 /* Adds standard iv candidates. */
2485 add_standard_iv_candidates (struct ivopts_data
*data
)
2487 add_candidate (data
, integer_zero_node
, integer_one_node
, true, NULL
);
2489 /* The same for a double-integer type if it is still fast enough. */
2491 (long_integer_type_node
) > TYPE_PRECISION (integer_type_node
)
2492 && TYPE_PRECISION (long_integer_type_node
) <= BITS_PER_WORD
)
2493 add_candidate (data
, build_int_cst (long_integer_type_node
, 0),
2494 build_int_cst (long_integer_type_node
, 1), true, NULL
);
2496 /* The same for a double-integer type if it is still fast enough. */
2498 (long_long_integer_type_node
) > TYPE_PRECISION (long_integer_type_node
)
2499 && TYPE_PRECISION (long_long_integer_type_node
) <= BITS_PER_WORD
)
2500 add_candidate (data
, build_int_cst (long_long_integer_type_node
, 0),
2501 build_int_cst (long_long_integer_type_node
, 1), true, NULL
);
2505 /* Adds candidates bases on the old induction variable IV. */
2508 add_old_iv_candidates (struct ivopts_data
*data
, struct iv
*iv
)
2512 struct iv_cand
*cand
;
2514 add_candidate (data
, iv
->base
, iv
->step
, true, NULL
);
2516 /* The same, but with initial value zero. */
2517 if (POINTER_TYPE_P (TREE_TYPE (iv
->base
)))
2518 add_candidate (data
, size_int (0), iv
->step
, true, NULL
);
2520 add_candidate (data
, build_int_cst (TREE_TYPE (iv
->base
), 0),
2521 iv
->step
, true, NULL
);
2523 phi
= SSA_NAME_DEF_STMT (iv
->ssa_name
);
2524 if (gimple_code (phi
) == GIMPLE_PHI
)
2526 /* Additionally record the possibility of leaving the original iv
2528 def
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (data
->current_loop
));
2529 cand
= add_candidate_1 (data
,
2530 iv
->base
, iv
->step
, true, IP_ORIGINAL
, NULL
,
2531 SSA_NAME_DEF_STMT (def
));
2532 cand
->var_before
= iv
->ssa_name
;
2533 cand
->var_after
= def
;
2537 /* Adds candidates based on the old induction variables. */
2540 add_old_ivs_candidates (struct ivopts_data
*data
)
2546 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
2548 iv
= ver_info (data
, i
)->iv
;
2549 if (iv
&& iv
->biv_p
&& !integer_zerop (iv
->step
))
2550 add_old_iv_candidates (data
, iv
);
2554 /* Adds candidates based on the value of the induction variable IV and USE. */
2557 add_iv_value_candidates (struct ivopts_data
*data
,
2558 struct iv
*iv
, struct iv_use
*use
)
2560 unsigned HOST_WIDE_INT offset
;
2564 add_candidate (data
, iv
->base
, iv
->step
, false, use
);
2566 /* The same, but with initial value zero. Make such variable important,
2567 since it is generic enough so that possibly many uses may be based
2569 basetype
= TREE_TYPE (iv
->base
);
2570 if (POINTER_TYPE_P (basetype
))
2571 basetype
= sizetype
;
2572 add_candidate (data
, build_int_cst (basetype
, 0),
2573 iv
->step
, true, use
);
2575 /* Third, try removing the constant offset. Make sure to even
2576 add a candidate for &a[0] vs. (T *)&a. */
2577 base
= strip_offset (iv
->base
, &offset
);
2579 || base
!= iv
->base
)
2580 add_candidate (data
, base
, iv
->step
, false, use
);
2583 /* Adds candidates based on the uses. */
2586 add_derived_ivs_candidates (struct ivopts_data
*data
)
2590 for (i
= 0; i
< n_iv_uses (data
); i
++)
2592 struct iv_use
*use
= iv_use (data
, i
);
2599 case USE_NONLINEAR_EXPR
:
2602 /* Just add the ivs based on the value of the iv used here. */
2603 add_iv_value_candidates (data
, use
->iv
, use
);
2612 /* Record important candidates and add them to related_cands bitmaps
2616 record_important_candidates (struct ivopts_data
*data
)
2621 for (i
= 0; i
< n_iv_cands (data
); i
++)
2623 struct iv_cand
*cand
= iv_cand (data
, i
);
2625 if (cand
->important
)
2626 bitmap_set_bit (data
->important_candidates
, i
);
2629 data
->consider_all_candidates
= (n_iv_cands (data
)
2630 <= CONSIDER_ALL_CANDIDATES_BOUND
);
2632 if (data
->consider_all_candidates
)
2634 /* We will not need "related_cands" bitmaps in this case,
2635 so release them to decrease peak memory consumption. */
2636 for (i
= 0; i
< n_iv_uses (data
); i
++)
2638 use
= iv_use (data
, i
);
2639 BITMAP_FREE (use
->related_cands
);
2644 /* Add important candidates to the related_cands bitmaps. */
2645 for (i
= 0; i
< n_iv_uses (data
); i
++)
2646 bitmap_ior_into (iv_use (data
, i
)->related_cands
,
2647 data
->important_candidates
);
2651 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
2652 If consider_all_candidates is true, we use a two-dimensional array, otherwise
2653 we allocate a simple list to every use. */
2656 alloc_use_cost_map (struct ivopts_data
*data
)
2658 unsigned i
, size
, s
;
2660 for (i
= 0; i
< n_iv_uses (data
); i
++)
2662 struct iv_use
*use
= iv_use (data
, i
);
2664 if (data
->consider_all_candidates
)
2665 size
= n_iv_cands (data
);
2668 s
= bitmap_count_bits (use
->related_cands
);
2670 /* Round up to the power of two, so that moduling by it is fast. */
2671 size
= s
? (1 << ceil_log2 (s
)) : 1;
2674 use
->n_map_members
= size
;
2675 use
->cost_map
= XCNEWVEC (struct cost_pair
, size
);
2679 /* Returns description of computation cost of expression whose runtime
2680 cost is RUNTIME and complexity corresponds to COMPLEXITY. */
2683 new_cost (unsigned runtime
, unsigned complexity
)
2687 cost
.cost
= runtime
;
2688 cost
.complexity
= complexity
;
2693 /* Adds costs COST1 and COST2. */
2696 add_costs (comp_cost cost1
, comp_cost cost2
)
2698 cost1
.cost
+= cost2
.cost
;
2699 cost1
.complexity
+= cost2
.complexity
;
2703 /* Subtracts costs COST1 and COST2. */
2706 sub_costs (comp_cost cost1
, comp_cost cost2
)
2708 cost1
.cost
-= cost2
.cost
;
2709 cost1
.complexity
-= cost2
.complexity
;
2714 /* Returns a negative number if COST1 < COST2, a positive number if
2715 COST1 > COST2, and 0 if COST1 = COST2. */
2718 compare_costs (comp_cost cost1
, comp_cost cost2
)
2720 if (cost1
.cost
== cost2
.cost
)
2721 return cost1
.complexity
- cost2
.complexity
;
2723 return cost1
.cost
- cost2
.cost
;
2726 /* Returns true if COST is infinite. */
2729 infinite_cost_p (comp_cost cost
)
2731 return cost
.cost
== INFTY
;
2734 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
2735 on invariants DEPENDS_ON and that the value used in expressing it
2736 is VALUE, and in case of iv elimination the comparison operator is COMP. */
2739 set_use_iv_cost (struct ivopts_data
*data
,
2740 struct iv_use
*use
, struct iv_cand
*cand
,
2741 comp_cost cost
, bitmap depends_on
, tree value
,
2742 enum tree_code comp
, int inv_expr_id
)
2746 if (infinite_cost_p (cost
))
2748 BITMAP_FREE (depends_on
);
2752 if (data
->consider_all_candidates
)
2754 use
->cost_map
[cand
->id
].cand
= cand
;
2755 use
->cost_map
[cand
->id
].cost
= cost
;
2756 use
->cost_map
[cand
->id
].depends_on
= depends_on
;
2757 use
->cost_map
[cand
->id
].value
= value
;
2758 use
->cost_map
[cand
->id
].comp
= comp
;
2759 use
->cost_map
[cand
->id
].inv_expr_id
= inv_expr_id
;
2763 /* n_map_members is a power of two, so this computes modulo. */
2764 s
= cand
->id
& (use
->n_map_members
- 1);
2765 for (i
= s
; i
< use
->n_map_members
; i
++)
2766 if (!use
->cost_map
[i
].cand
)
2768 for (i
= 0; i
< s
; i
++)
2769 if (!use
->cost_map
[i
].cand
)
2775 use
->cost_map
[i
].cand
= cand
;
2776 use
->cost_map
[i
].cost
= cost
;
2777 use
->cost_map
[i
].depends_on
= depends_on
;
2778 use
->cost_map
[i
].value
= value
;
2779 use
->cost_map
[i
].comp
= comp
;
2780 use
->cost_map
[i
].inv_expr_id
= inv_expr_id
;
2783 /* Gets cost of (USE, CANDIDATE) pair. */
2785 static struct cost_pair
*
2786 get_use_iv_cost (struct ivopts_data
*data
, struct iv_use
*use
,
2787 struct iv_cand
*cand
)
2790 struct cost_pair
*ret
;
2795 if (data
->consider_all_candidates
)
2797 ret
= use
->cost_map
+ cand
->id
;
2804 /* n_map_members is a power of two, so this computes modulo. */
2805 s
= cand
->id
& (use
->n_map_members
- 1);
2806 for (i
= s
; i
< use
->n_map_members
; i
++)
2807 if (use
->cost_map
[i
].cand
== cand
)
2808 return use
->cost_map
+ i
;
2809 else if (use
->cost_map
[i
].cand
== NULL
)
2811 for (i
= 0; i
< s
; i
++)
2812 if (use
->cost_map
[i
].cand
== cand
)
2813 return use
->cost_map
+ i
;
2814 else if (use
->cost_map
[i
].cand
== NULL
)
2820 /* Returns estimate on cost of computing SEQ. */
2823 seq_cost (rtx seq
, bool speed
)
2828 for (; seq
; seq
= NEXT_INSN (seq
))
2830 set
= single_set (seq
);
2832 cost
+= set_src_cost (SET_SRC (set
), speed
);
2840 /* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
2842 produce_memory_decl_rtl (tree obj
, int *regno
)
2844 addr_space_t as
= TYPE_ADDR_SPACE (TREE_TYPE (obj
));
2845 enum machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
2849 if (TREE_STATIC (obj
) || DECL_EXTERNAL (obj
))
2851 const char *name
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj
));
2852 x
= gen_rtx_SYMBOL_REF (address_mode
, name
);
2853 SET_SYMBOL_REF_DECL (x
, obj
);
2854 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
2855 set_mem_addr_space (x
, as
);
2856 targetm
.encode_section_info (obj
, x
, true);
2860 x
= gen_raw_REG (address_mode
, (*regno
)++);
2861 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
2862 set_mem_addr_space (x
, as
);
2868 /* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
2869 walk_tree. DATA contains the actual fake register number. */
2872 prepare_decl_rtl (tree
*expr_p
, int *ws
, void *data
)
2874 tree obj
= NULL_TREE
;
2876 int *regno
= (int *) data
;
2878 switch (TREE_CODE (*expr_p
))
2881 for (expr_p
= &TREE_OPERAND (*expr_p
, 0);
2882 handled_component_p (*expr_p
);
2883 expr_p
= &TREE_OPERAND (*expr_p
, 0))
2886 if (DECL_P (obj
) && HAS_RTL_P (obj
) && !DECL_RTL_SET_P (obj
))
2887 x
= produce_memory_decl_rtl (obj
, regno
);
2892 obj
= SSA_NAME_VAR (*expr_p
);
2893 /* Defer handling of anonymous SSA_NAMEs to the expander. */
2896 if (!DECL_RTL_SET_P (obj
))
2897 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2906 if (DECL_RTL_SET_P (obj
))
2909 if (DECL_MODE (obj
) == BLKmode
)
2910 x
= produce_memory_decl_rtl (obj
, regno
);
2912 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
2922 decl_rtl_to_reset
.safe_push (obj
);
2923 SET_DECL_RTL (obj
, x
);
2929 /* Determines cost of the computation of EXPR. */
2932 computation_cost (tree expr
, bool speed
)
2935 tree type
= TREE_TYPE (expr
);
2937 /* Avoid using hard regs in ways which may be unsupported. */
2938 int regno
= LAST_VIRTUAL_REGISTER
+ 1;
2939 struct cgraph_node
*node
= cgraph_get_node (current_function_decl
);
2940 enum node_frequency real_frequency
= node
->frequency
;
2942 node
->frequency
= NODE_FREQUENCY_NORMAL
;
2943 crtl
->maybe_hot_insn_p
= speed
;
2944 walk_tree (&expr
, prepare_decl_rtl
, ®no
, NULL
);
2946 rslt
= expand_expr (expr
, NULL_RTX
, TYPE_MODE (type
), EXPAND_NORMAL
);
2949 default_rtl_profile ();
2950 node
->frequency
= real_frequency
;
2952 cost
= seq_cost (seq
, speed
);
2954 cost
+= address_cost (XEXP (rslt
, 0), TYPE_MODE (type
),
2955 TYPE_ADDR_SPACE (type
), speed
);
2956 else if (!REG_P (rslt
))
2957 cost
+= set_src_cost (rslt
, speed
);
2962 /* Returns variable containing the value of candidate CAND at statement AT. */
2965 var_at_stmt (struct loop
*loop
, struct iv_cand
*cand
, gimple stmt
)
2967 if (stmt_after_increment (loop
, cand
, stmt
))
2968 return cand
->var_after
;
2970 return cand
->var_before
;
2973 /* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
2974 same precision that is at least as wide as the precision of TYPE, stores
2975 BA to A and BB to B, and returns the type of BA. Otherwise, returns the
2979 determine_common_wider_type (tree
*a
, tree
*b
)
2981 tree wider_type
= NULL
;
2983 tree atype
= TREE_TYPE (*a
);
2985 if (CONVERT_EXPR_P (*a
))
2987 suba
= TREE_OPERAND (*a
, 0);
2988 wider_type
= TREE_TYPE (suba
);
2989 if (TYPE_PRECISION (wider_type
) < TYPE_PRECISION (atype
))
2995 if (CONVERT_EXPR_P (*b
))
2997 subb
= TREE_OPERAND (*b
, 0);
2998 if (TYPE_PRECISION (wider_type
) != TYPE_PRECISION (TREE_TYPE (subb
)))
3009 /* Determines the expression by that USE is expressed from induction variable
3010 CAND at statement AT in LOOP. The expression is stored in a decomposed
3011 form into AFF. Returns false if USE cannot be expressed using CAND. */
3014 get_computation_aff (struct loop
*loop
,
3015 struct iv_use
*use
, struct iv_cand
*cand
, gimple at
,
3016 struct affine_tree_combination
*aff
)
3018 tree ubase
= use
->iv
->base
;
3019 tree ustep
= use
->iv
->step
;
3020 tree cbase
= cand
->iv
->base
;
3021 tree cstep
= cand
->iv
->step
, cstep_common
;
3022 tree utype
= TREE_TYPE (ubase
), ctype
= TREE_TYPE (cbase
);
3023 tree common_type
, var
;
3025 aff_tree cbase_aff
, var_aff
;
3028 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
3030 /* We do not have a precision to express the values of use. */
3034 var
= var_at_stmt (loop
, cand
, at
);
3035 uutype
= unsigned_type_for (utype
);
3037 /* If the conversion is not noop, perform it. */
3038 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
3040 cstep
= fold_convert (uutype
, cstep
);
3041 cbase
= fold_convert (uutype
, cbase
);
3042 var
= fold_convert (uutype
, var
);
3045 if (!constant_multiple_of (ustep
, cstep
, &rat
))
3048 /* In case both UBASE and CBASE are shortened to UUTYPE from some common
3049 type, we achieve better folding by computing their difference in this
3050 wider type, and cast the result to UUTYPE. We do not need to worry about
3051 overflows, as all the arithmetics will in the end be performed in UUTYPE
3053 common_type
= determine_common_wider_type (&ubase
, &cbase
);
3055 /* use = ubase - ratio * cbase + ratio * var. */
3056 tree_to_aff_combination (ubase
, common_type
, aff
);
3057 tree_to_aff_combination (cbase
, common_type
, &cbase_aff
);
3058 tree_to_aff_combination (var
, uutype
, &var_aff
);
3060 /* We need to shift the value if we are after the increment. */
3061 if (stmt_after_increment (loop
, cand
, at
))
3065 if (common_type
!= uutype
)
3066 cstep_common
= fold_convert (common_type
, cstep
);
3068 cstep_common
= cstep
;
3070 tree_to_aff_combination (cstep_common
, common_type
, &cstep_aff
);
3071 aff_combination_add (&cbase_aff
, &cstep_aff
);
3074 aff_combination_scale (&cbase_aff
, -rat
);
3075 aff_combination_add (aff
, &cbase_aff
);
3076 if (common_type
!= uutype
)
3077 aff_combination_convert (aff
, uutype
);
3079 aff_combination_scale (&var_aff
, rat
);
3080 aff_combination_add (aff
, &var_aff
);
3085 /* Return the type of USE. */
3088 get_use_type (struct iv_use
*use
)
3090 tree base_type
= TREE_TYPE (use
->iv
->base
);
3093 if (use
->type
== USE_ADDRESS
)
3095 /* The base_type may be a void pointer. Create a pointer type based on
3096 the mem_ref instead. */
3097 type
= build_pointer_type (TREE_TYPE (*use
->op_p
));
3098 gcc_assert (TYPE_ADDR_SPACE (TREE_TYPE (type
))
3099 == TYPE_ADDR_SPACE (TREE_TYPE (base_type
)));
3107 /* Determines the expression by that USE is expressed from induction variable
3108 CAND at statement AT in LOOP. The computation is unshared. */
3111 get_computation_at (struct loop
*loop
,
3112 struct iv_use
*use
, struct iv_cand
*cand
, gimple at
)
3115 tree type
= get_use_type (use
);
3117 if (!get_computation_aff (loop
, use
, cand
, at
, &aff
))
3119 unshare_aff_combination (&aff
);
3120 return fold_convert (type
, aff_combination_to_tree (&aff
));
3123 /* Determines the expression by that USE is expressed from induction variable
3124 CAND in LOOP. The computation is unshared. */
3127 get_computation (struct loop
*loop
, struct iv_use
*use
, struct iv_cand
*cand
)
3129 return get_computation_at (loop
, use
, cand
, use
->stmt
);
3132 /* Adjust the cost COST for being in loop setup rather than loop body.
3133 If we're optimizing for space, the loop setup overhead is constant;
3134 if we're optimizing for speed, amortize it over the per-iteration cost. */
3136 adjust_setup_cost (struct ivopts_data
*data
, unsigned cost
)
3140 else if (optimize_loop_for_speed_p (data
->current_loop
))
3141 return cost
/ avg_loop_niter (data
->current_loop
);
3146 /* Returns true if multiplying by RATIO is allowed in an address. Test the
3147 validity for a memory reference accessing memory of mode MODE in
3148 address space AS. */
3152 multiplier_allowed_in_address_p (HOST_WIDE_INT ratio
, enum machine_mode mode
,
3155 #define MAX_RATIO 128
3156 unsigned int data_index
= (int) as
* MAX_MACHINE_MODE
+ (int) mode
;
3157 static vec
<sbitmap
> valid_mult_list
;
3160 if (data_index
>= valid_mult_list
.length ())
3161 valid_mult_list
.safe_grow_cleared (data_index
+ 1);
3163 valid_mult
= valid_mult_list
[data_index
];
3166 enum machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
3167 rtx reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
3168 rtx reg2
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 2);
3172 valid_mult
= sbitmap_alloc (2 * MAX_RATIO
+ 1);
3173 bitmap_clear (valid_mult
);
3174 scaled
= gen_rtx_fmt_ee (MULT
, address_mode
, reg1
, NULL_RTX
);
3175 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, scaled
, reg2
);
3176 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
3178 XEXP (scaled
, 1) = gen_int_mode (i
, address_mode
);
3179 if (memory_address_addr_space_p (mode
, addr
, as
)
3180 || memory_address_addr_space_p (mode
, scaled
, as
))
3181 bitmap_set_bit (valid_mult
, i
+ MAX_RATIO
);
3184 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3186 fprintf (dump_file
, " allowed multipliers:");
3187 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
3188 if (bitmap_bit_p (valid_mult
, i
+ MAX_RATIO
))
3189 fprintf (dump_file
, " %d", (int) i
);
3190 fprintf (dump_file
, "\n");
3191 fprintf (dump_file
, "\n");
3194 valid_mult_list
[data_index
] = valid_mult
;
3197 if (ratio
> MAX_RATIO
|| ratio
< -MAX_RATIO
)
3200 return bitmap_bit_p (valid_mult
, ratio
+ MAX_RATIO
);
3203 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
3204 If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
3205 variable is omitted. Compute the cost for a memory reference that accesses
3206 a memory location of mode MEM_MODE in address space AS.
3208 MAY_AUTOINC is set to true if the autoincrement (increasing index by
3209 size of MEM_MODE / RATIO) is available. To make this determination, we
3210 look at the size of the increment to be made, which is given in CSTEP.
3211 CSTEP may be zero if the step is unknown.
3212 STMT_AFTER_INC is true iff the statement we're looking at is after the
3213 increment of the original biv.
3215 TODO -- there must be some better way. This all is quite crude. */
3219 AINC_PRE_INC
, /* Pre increment. */
3220 AINC_PRE_DEC
, /* Pre decrement. */
3221 AINC_POST_INC
, /* Post increment. */
3222 AINC_POST_DEC
, /* Post decrement. */
3223 AINC_NONE
/* Also the number of auto increment types. */
3226 typedef struct address_cost_data_s
3228 HOST_WIDE_INT min_offset
, max_offset
;
3229 unsigned costs
[2][2][2][2];
3230 unsigned ainc_costs
[AINC_NONE
];
3231 } *address_cost_data
;
3235 get_address_cost (bool symbol_present
, bool var_present
,
3236 unsigned HOST_WIDE_INT offset
, HOST_WIDE_INT ratio
,
3237 HOST_WIDE_INT cstep
, enum machine_mode mem_mode
,
3238 addr_space_t as
, bool speed
,
3239 bool stmt_after_inc
, bool *may_autoinc
)
3241 enum machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
3242 static vec
<address_cost_data
> address_cost_data_list
;
3243 unsigned int data_index
= (int) as
* MAX_MACHINE_MODE
+ (int) mem_mode
;
3244 address_cost_data data
;
3245 static bool has_preinc
[MAX_MACHINE_MODE
], has_postinc
[MAX_MACHINE_MODE
];
3246 static bool has_predec
[MAX_MACHINE_MODE
], has_postdec
[MAX_MACHINE_MODE
];
3247 unsigned cost
, acost
, complexity
;
3248 enum ainc_type autoinc_type
;
3249 bool offset_p
, ratio_p
, autoinc
;
3250 HOST_WIDE_INT s_offset
, autoinc_offset
, msize
;
3251 unsigned HOST_WIDE_INT mask
;
3254 if (data_index
>= address_cost_data_list
.length ())
3255 address_cost_data_list
.safe_grow_cleared (data_index
+ 1);
3257 data
= address_cost_data_list
[data_index
];
3261 HOST_WIDE_INT rat
, off
= 0;
3262 int old_cse_not_expected
, width
;
3263 unsigned sym_p
, var_p
, off_p
, rat_p
, add_c
;
3264 rtx seq
, addr
, base
;
3267 data
= (address_cost_data
) xcalloc (1, sizeof (*data
));
3269 reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
3271 width
= GET_MODE_BITSIZE (address_mode
) - 1;
3272 if (width
> (HOST_BITS_PER_WIDE_INT
- 1))
3273 width
= HOST_BITS_PER_WIDE_INT
- 1;
3274 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, reg1
, NULL_RTX
);
3276 for (i
= width
; i
>= 0; i
--)
3278 off
= -((unsigned HOST_WIDE_INT
) 1 << i
);
3279 XEXP (addr
, 1) = gen_int_mode (off
, address_mode
);
3280 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
3283 data
->min_offset
= (i
== -1? 0 : off
);
3285 for (i
= width
; i
>= 0; i
--)
3287 off
= ((unsigned HOST_WIDE_INT
) 1 << i
) - 1;
3288 XEXP (addr
, 1) = gen_int_mode (off
, address_mode
);
3289 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
3294 data
->max_offset
= off
;
3296 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3298 fprintf (dump_file
, "get_address_cost:\n");
3299 fprintf (dump_file
, " min offset %s " HOST_WIDE_INT_PRINT_DEC
"\n",
3300 GET_MODE_NAME (mem_mode
),
3302 fprintf (dump_file
, " max offset %s " HOST_WIDE_INT_PRINT_DEC
"\n",
3303 GET_MODE_NAME (mem_mode
),
3308 for (i
= 2; i
<= MAX_RATIO
; i
++)
3309 if (multiplier_allowed_in_address_p (i
, mem_mode
, as
))
3315 /* Compute the cost of various addressing modes. */
3317 reg0
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
3318 reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 2);
3320 if (USE_LOAD_PRE_DECREMENT (mem_mode
)
3321 || USE_STORE_PRE_DECREMENT (mem_mode
))
3323 addr
= gen_rtx_PRE_DEC (address_mode
, reg0
);
3324 has_predec
[mem_mode
]
3325 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3327 if (has_predec
[mem_mode
])
3328 data
->ainc_costs
[AINC_PRE_DEC
]
3329 = address_cost (addr
, mem_mode
, as
, speed
);
3331 if (USE_LOAD_POST_DECREMENT (mem_mode
)
3332 || USE_STORE_POST_DECREMENT (mem_mode
))
3334 addr
= gen_rtx_POST_DEC (address_mode
, reg0
);
3335 has_postdec
[mem_mode
]
3336 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3338 if (has_postdec
[mem_mode
])
3339 data
->ainc_costs
[AINC_POST_DEC
]
3340 = address_cost (addr
, mem_mode
, as
, speed
);
3342 if (USE_LOAD_PRE_INCREMENT (mem_mode
)
3343 || USE_STORE_PRE_DECREMENT (mem_mode
))
3345 addr
= gen_rtx_PRE_INC (address_mode
, reg0
);
3346 has_preinc
[mem_mode
]
3347 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3349 if (has_preinc
[mem_mode
])
3350 data
->ainc_costs
[AINC_PRE_INC
]
3351 = address_cost (addr
, mem_mode
, as
, speed
);
3353 if (USE_LOAD_POST_INCREMENT (mem_mode
)
3354 || USE_STORE_POST_INCREMENT (mem_mode
))
3356 addr
= gen_rtx_POST_INC (address_mode
, reg0
);
3357 has_postinc
[mem_mode
]
3358 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3360 if (has_postinc
[mem_mode
])
3361 data
->ainc_costs
[AINC_POST_INC
]
3362 = address_cost (addr
, mem_mode
, as
, speed
);
3364 for (i
= 0; i
< 16; i
++)
3367 var_p
= (i
>> 1) & 1;
3368 off_p
= (i
>> 2) & 1;
3369 rat_p
= (i
>> 3) & 1;
3373 addr
= gen_rtx_fmt_ee (MULT
, address_mode
, addr
,
3374 gen_int_mode (rat
, address_mode
));
3377 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, addr
, reg1
);
3381 base
= gen_rtx_SYMBOL_REF (address_mode
, ggc_strdup (""));
3382 /* ??? We can run into trouble with some backends by presenting
3383 it with symbols which haven't been properly passed through
3384 targetm.encode_section_info. By setting the local bit, we
3385 enhance the probability of things working. */
3386 SYMBOL_REF_FLAGS (base
) = SYMBOL_FLAG_LOCAL
;
3389 base
= gen_rtx_fmt_e (CONST
, address_mode
,
3391 (PLUS
, address_mode
, base
,
3392 gen_int_mode (off
, address_mode
)));
3395 base
= gen_int_mode (off
, address_mode
);
3400 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, addr
, base
);
3403 /* To avoid splitting addressing modes, pretend that no cse will
3405 old_cse_not_expected
= cse_not_expected
;
3406 cse_not_expected
= true;
3407 addr
= memory_address_addr_space (mem_mode
, addr
, as
);
3408 cse_not_expected
= old_cse_not_expected
;
3412 acost
= seq_cost (seq
, speed
);
3413 acost
+= address_cost (addr
, mem_mode
, as
, speed
);
3417 data
->costs
[sym_p
][var_p
][off_p
][rat_p
] = acost
;
3420 /* On some targets, it is quite expensive to load symbol to a register,
3421 which makes addresses that contain symbols look much more expensive.
3422 However, the symbol will have to be loaded in any case before the
3423 loop (and quite likely we have it in register already), so it does not
3424 make much sense to penalize them too heavily. So make some final
3425 tweaks for the SYMBOL_PRESENT modes:
3427 If VAR_PRESENT is false, and the mode obtained by changing symbol to
3428 var is cheaper, use this mode with small penalty.
3429 If VAR_PRESENT is true, try whether the mode with
3430 SYMBOL_PRESENT = false is cheaper even with cost of addition, and
3431 if this is the case, use it. */
3432 add_c
= add_cost (speed
, address_mode
);
3433 for (i
= 0; i
< 8; i
++)
3436 off_p
= (i
>> 1) & 1;
3437 rat_p
= (i
>> 2) & 1;
3439 acost
= data
->costs
[0][1][off_p
][rat_p
] + 1;
3443 if (acost
< data
->costs
[1][var_p
][off_p
][rat_p
])
3444 data
->costs
[1][var_p
][off_p
][rat_p
] = acost
;
3447 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3449 fprintf (dump_file
, "Address costs:\n");
3451 for (i
= 0; i
< 16; i
++)
3454 var_p
= (i
>> 1) & 1;
3455 off_p
= (i
>> 2) & 1;
3456 rat_p
= (i
>> 3) & 1;
3458 fprintf (dump_file
, " ");
3460 fprintf (dump_file
, "sym + ");
3462 fprintf (dump_file
, "var + ");
3464 fprintf (dump_file
, "cst + ");
3466 fprintf (dump_file
, "rat * ");
3468 acost
= data
->costs
[sym_p
][var_p
][off_p
][rat_p
];
3469 fprintf (dump_file
, "index costs %d\n", acost
);
3471 if (has_predec
[mem_mode
] || has_postdec
[mem_mode
]
3472 || has_preinc
[mem_mode
] || has_postinc
[mem_mode
])
3473 fprintf (dump_file
, " May include autoinc/dec\n");
3474 fprintf (dump_file
, "\n");
3477 address_cost_data_list
[data_index
] = data
;
3480 bits
= GET_MODE_BITSIZE (address_mode
);
3481 mask
= ~(~(unsigned HOST_WIDE_INT
) 0 << (bits
- 1) << 1);
3483 if ((offset
>> (bits
- 1) & 1))
3488 autoinc_type
= AINC_NONE
;
3489 msize
= GET_MODE_SIZE (mem_mode
);
3490 autoinc_offset
= offset
;
3492 autoinc_offset
+= ratio
* cstep
;
3493 if (symbol_present
|| var_present
|| ratio
!= 1)
3497 if (has_postinc
[mem_mode
] && autoinc_offset
== 0
3499 autoinc_type
= AINC_POST_INC
;
3500 else if (has_postdec
[mem_mode
] && autoinc_offset
== 0
3502 autoinc_type
= AINC_POST_DEC
;
3503 else if (has_preinc
[mem_mode
] && autoinc_offset
== msize
3505 autoinc_type
= AINC_PRE_INC
;
3506 else if (has_predec
[mem_mode
] && autoinc_offset
== -msize
3508 autoinc_type
= AINC_PRE_DEC
;
3510 if (autoinc_type
!= AINC_NONE
)
3515 offset_p
= (s_offset
!= 0
3516 && data
->min_offset
<= s_offset
3517 && s_offset
<= data
->max_offset
);
3518 ratio_p
= (ratio
!= 1
3519 && multiplier_allowed_in_address_p (ratio
, mem_mode
, as
));
3521 if (ratio
!= 1 && !ratio_p
)
3522 cost
+= mult_by_coeff_cost (ratio
, address_mode
, speed
);
3524 if (s_offset
&& !offset_p
&& !symbol_present
)
3525 cost
+= add_cost (speed
, address_mode
);
3528 *may_autoinc
= autoinc
;
3530 acost
= data
->ainc_costs
[autoinc_type
];
3532 acost
= data
->costs
[symbol_present
][var_present
][offset_p
][ratio_p
];
3533 complexity
= (symbol_present
!= 0) + (var_present
!= 0) + offset_p
+ ratio_p
;
3534 return new_cost (cost
+ acost
, complexity
);
3537 /* Calculate the SPEED or size cost of shiftadd EXPR in MODE. MULT is the
3538 the EXPR operand holding the shift. COST0 and COST1 are the costs for
3539 calculating the operands of EXPR. Returns true if successful, and returns
3540 the cost in COST. */
3543 get_shiftadd_cost (tree expr
, enum machine_mode mode
, comp_cost cost0
,
3544 comp_cost cost1
, tree mult
, bool speed
, comp_cost
*cost
)
3547 tree op1
= TREE_OPERAND (expr
, 1);
3548 tree cst
= TREE_OPERAND (mult
, 1);
3549 tree multop
= TREE_OPERAND (mult
, 0);
3550 int m
= exact_log2 (int_cst_value (cst
));
3551 int maxm
= MIN (BITS_PER_WORD
, GET_MODE_BITSIZE (mode
));
3553 bool equal_p
= false;
3555 if (!(m
>= 0 && m
< maxm
))
3558 if (operand_equal_p (op1
, mult
, 0))
3561 sa_cost
= (TREE_CODE (expr
) != MINUS_EXPR
3562 ? shiftadd_cost (speed
, mode
, m
)
3564 ? shiftsub1_cost (speed
, mode
, m
)
3565 : shiftsub0_cost (speed
, mode
, m
)));
3566 res
= new_cost (sa_cost
, 0);
3567 res
= add_costs (res
, equal_p
? cost0
: cost1
);
3569 STRIP_NOPS (multop
);
3570 if (!is_gimple_val (multop
))
3571 res
= add_costs (res
, force_expr_to_var_cost (multop
, speed
));
3577 /* Estimates cost of forcing expression EXPR into a variable. */
3580 force_expr_to_var_cost (tree expr
, bool speed
)
3582 static bool costs_initialized
= false;
3583 static unsigned integer_cost
[2];
3584 static unsigned symbol_cost
[2];
3585 static unsigned address_cost
[2];
3587 comp_cost cost0
, cost1
, cost
;
3588 enum machine_mode mode
;
3590 if (!costs_initialized
)
3592 tree type
= build_pointer_type (integer_type_node
);
3597 var
= create_tmp_var_raw (integer_type_node
, "test_var");
3598 TREE_STATIC (var
) = 1;
3599 x
= produce_memory_decl_rtl (var
, NULL
);
3600 SET_DECL_RTL (var
, x
);
3602 addr
= build1 (ADDR_EXPR
, type
, var
);
3605 for (i
= 0; i
< 2; i
++)
3607 integer_cost
[i
] = computation_cost (build_int_cst (integer_type_node
,
3610 symbol_cost
[i
] = computation_cost (addr
, i
) + 1;
3613 = computation_cost (fold_build_pointer_plus_hwi (addr
, 2000), i
) + 1;
3614 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3616 fprintf (dump_file
, "force_expr_to_var_cost %s costs:\n", i
? "speed" : "size");
3617 fprintf (dump_file
, " integer %d\n", (int) integer_cost
[i
]);
3618 fprintf (dump_file
, " symbol %d\n", (int) symbol_cost
[i
]);
3619 fprintf (dump_file
, " address %d\n", (int) address_cost
[i
]);
3620 fprintf (dump_file
, " other %d\n", (int) target_spill_cost
[i
]);
3621 fprintf (dump_file
, "\n");
3625 costs_initialized
= true;
3630 if (SSA_VAR_P (expr
))
3633 if (is_gimple_min_invariant (expr
))
3635 if (TREE_CODE (expr
) == INTEGER_CST
)
3636 return new_cost (integer_cost
[speed
], 0);
3638 if (TREE_CODE (expr
) == ADDR_EXPR
)
3640 tree obj
= TREE_OPERAND (expr
, 0);
3642 if (TREE_CODE (obj
) == VAR_DECL
3643 || TREE_CODE (obj
) == PARM_DECL
3644 || TREE_CODE (obj
) == RESULT_DECL
)
3645 return new_cost (symbol_cost
[speed
], 0);
3648 return new_cost (address_cost
[speed
], 0);
3651 switch (TREE_CODE (expr
))
3653 case POINTER_PLUS_EXPR
:
3657 op0
= TREE_OPERAND (expr
, 0);
3658 op1
= TREE_OPERAND (expr
, 1);
3665 op0
= TREE_OPERAND (expr
, 0);
3671 /* Just an arbitrary value, FIXME. */
3672 return new_cost (target_spill_cost
[speed
], 0);
3675 if (op0
== NULL_TREE
3676 || TREE_CODE (op0
) == SSA_NAME
|| CONSTANT_CLASS_P (op0
))
3679 cost0
= force_expr_to_var_cost (op0
, speed
);
3681 if (op1
== NULL_TREE
3682 || TREE_CODE (op1
) == SSA_NAME
|| CONSTANT_CLASS_P (op1
))
3685 cost1
= force_expr_to_var_cost (op1
, speed
);
3687 mode
= TYPE_MODE (TREE_TYPE (expr
));
3688 switch (TREE_CODE (expr
))
3690 case POINTER_PLUS_EXPR
:
3694 cost
= new_cost (add_cost (speed
, mode
), 0);
3695 if (TREE_CODE (expr
) != NEGATE_EXPR
)
3697 tree mult
= NULL_TREE
;
3699 if (TREE_CODE (op1
) == MULT_EXPR
)
3701 else if (TREE_CODE (op0
) == MULT_EXPR
)
3704 if (mult
!= NULL_TREE
3705 && cst_and_fits_in_hwi (TREE_OPERAND (mult
, 1))
3706 && get_shiftadd_cost (expr
, mode
, cost0
, cost1
, mult
,
3714 tree inner_mode
, outer_mode
;
3715 outer_mode
= TREE_TYPE (expr
);
3716 inner_mode
= TREE_TYPE (op0
);
3717 cost
= new_cost (convert_cost (TYPE_MODE (outer_mode
),
3718 TYPE_MODE (inner_mode
), speed
), 0);
3723 if (cst_and_fits_in_hwi (op0
))
3724 cost
= new_cost (mult_by_coeff_cost (int_cst_value (op0
),
3726 else if (cst_and_fits_in_hwi (op1
))
3727 cost
= new_cost (mult_by_coeff_cost (int_cst_value (op1
),
3730 return new_cost (target_spill_cost
[speed
], 0);
3737 cost
= add_costs (cost
, cost0
);
3738 cost
= add_costs (cost
, cost1
);
3740 /* Bound the cost by target_spill_cost. The parts of complicated
3741 computations often are either loop invariant or at least can
3742 be shared between several iv uses, so letting this grow without
3743 limits would not give reasonable results. */
3744 if (cost
.cost
> (int) target_spill_cost
[speed
])
3745 cost
.cost
= target_spill_cost
[speed
];
3750 /* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
3751 invariants the computation depends on. */
3754 force_var_cost (struct ivopts_data
*data
,
3755 tree expr
, bitmap
*depends_on
)
3759 fd_ivopts_data
= data
;
3760 walk_tree (&expr
, find_depends
, depends_on
, NULL
);
3763 return force_expr_to_var_cost (expr
, data
->speed
);
3766 /* Estimates cost of expressing address ADDR as var + symbol + offset. The
3767 value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
3768 to false if the corresponding part is missing. DEPENDS_ON is a set of the
3769 invariants the computation depends on. */
3772 split_address_cost (struct ivopts_data
*data
,
3773 tree addr
, bool *symbol_present
, bool *var_present
,
3774 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3777 HOST_WIDE_INT bitsize
;
3778 HOST_WIDE_INT bitpos
;
3780 enum machine_mode mode
;
3781 int unsignedp
, volatilep
;
3783 core
= get_inner_reference (addr
, &bitsize
, &bitpos
, &toffset
, &mode
,
3784 &unsignedp
, &volatilep
, false);
3787 || bitpos
% BITS_PER_UNIT
!= 0
3788 || TREE_CODE (core
) != VAR_DECL
)
3790 *symbol_present
= false;
3791 *var_present
= true;
3792 fd_ivopts_data
= data
;
3793 walk_tree (&addr
, find_depends
, depends_on
, NULL
);
3794 return new_cost (target_spill_cost
[data
->speed
], 0);
3797 *offset
+= bitpos
/ BITS_PER_UNIT
;
3798 if (TREE_STATIC (core
)
3799 || DECL_EXTERNAL (core
))
3801 *symbol_present
= true;
3802 *var_present
= false;
3806 *symbol_present
= false;
3807 *var_present
= true;
3811 /* Estimates cost of expressing difference of addresses E1 - E2 as
3812 var + symbol + offset. The value of offset is added to OFFSET,
3813 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3814 part is missing. DEPENDS_ON is a set of the invariants the computation
3818 ptr_difference_cost (struct ivopts_data
*data
,
3819 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
3820 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3822 HOST_WIDE_INT diff
= 0;
3823 aff_tree aff_e1
, aff_e2
;
3826 gcc_assert (TREE_CODE (e1
) == ADDR_EXPR
);
3828 if (ptr_difference_const (e1
, e2
, &diff
))
3831 *symbol_present
= false;
3832 *var_present
= false;
3836 if (integer_zerop (e2
))
3837 return split_address_cost (data
, TREE_OPERAND (e1
, 0),
3838 symbol_present
, var_present
, offset
, depends_on
);
3840 *symbol_present
= false;
3841 *var_present
= true;
3843 type
= signed_type_for (TREE_TYPE (e1
));
3844 tree_to_aff_combination (e1
, type
, &aff_e1
);
3845 tree_to_aff_combination (e2
, type
, &aff_e2
);
3846 aff_combination_scale (&aff_e2
, -1);
3847 aff_combination_add (&aff_e1
, &aff_e2
);
3849 return force_var_cost (data
, aff_combination_to_tree (&aff_e1
), depends_on
);
3852 /* Estimates cost of expressing difference E1 - E2 as
3853 var + symbol + offset. The value of offset is added to OFFSET,
3854 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
3855 part is missing. DEPENDS_ON is a set of the invariants the computation
3859 difference_cost (struct ivopts_data
*data
,
3860 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
3861 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
3863 enum machine_mode mode
= TYPE_MODE (TREE_TYPE (e1
));
3864 unsigned HOST_WIDE_INT off1
, off2
;
3865 aff_tree aff_e1
, aff_e2
;
3868 e1
= strip_offset (e1
, &off1
);
3869 e2
= strip_offset (e2
, &off2
);
3870 *offset
+= off1
- off2
;
3875 if (TREE_CODE (e1
) == ADDR_EXPR
)
3876 return ptr_difference_cost (data
, e1
, e2
, symbol_present
, var_present
,
3877 offset
, depends_on
);
3878 *symbol_present
= false;
3880 if (operand_equal_p (e1
, e2
, 0))
3882 *var_present
= false;
3886 *var_present
= true;
3888 if (integer_zerop (e2
))
3889 return force_var_cost (data
, e1
, depends_on
);
3891 if (integer_zerop (e1
))
3893 comp_cost cost
= force_var_cost (data
, e2
, depends_on
);
3894 cost
.cost
+= mult_by_coeff_cost (-1, mode
, data
->speed
);
3898 type
= signed_type_for (TREE_TYPE (e1
));
3899 tree_to_aff_combination (e1
, type
, &aff_e1
);
3900 tree_to_aff_combination (e2
, type
, &aff_e2
);
3901 aff_combination_scale (&aff_e2
, -1);
3902 aff_combination_add (&aff_e1
, &aff_e2
);
3904 return force_var_cost (data
, aff_combination_to_tree (&aff_e1
), depends_on
);
3907 /* Returns true if AFF1 and AFF2 are identical. */
3910 compare_aff_trees (aff_tree
*aff1
, aff_tree
*aff2
)
3914 if (aff1
->n
!= aff2
->n
)
3917 for (i
= 0; i
< aff1
->n
; i
++)
3919 if (aff1
->elts
[i
].coef
!= aff2
->elts
[i
].coef
)
3922 if (!operand_equal_p (aff1
->elts
[i
].val
, aff2
->elts
[i
].val
, 0))
3928 /* Stores EXPR in DATA->inv_expr_tab, and assigns it an inv_expr_id. */
3931 get_expr_id (struct ivopts_data
*data
, tree expr
)
3933 struct iv_inv_expr_ent ent
;
3934 struct iv_inv_expr_ent
**slot
;
3937 ent
.hash
= iterative_hash_expr (expr
, 0);
3938 slot
= data
->inv_expr_tab
.find_slot (&ent
, INSERT
);
3942 *slot
= XNEW (struct iv_inv_expr_ent
);
3943 (*slot
)->expr
= expr
;
3944 (*slot
)->hash
= ent
.hash
;
3945 (*slot
)->id
= data
->inv_expr_id
++;
3949 /* Returns the pseudo expr id if expression UBASE - RATIO * CBASE
3950 requires a new compiler generated temporary. Returns -1 otherwise.
3951 ADDRESS_P is a flag indicating if the expression is for address
3955 get_loop_invariant_expr_id (struct ivopts_data
*data
, tree ubase
,
3956 tree cbase
, HOST_WIDE_INT ratio
,
3959 aff_tree ubase_aff
, cbase_aff
;
3967 if ((TREE_CODE (ubase
) == INTEGER_CST
)
3968 && (TREE_CODE (cbase
) == INTEGER_CST
))
3971 /* Strips the constant part. */
3972 if (TREE_CODE (ubase
) == PLUS_EXPR
3973 || TREE_CODE (ubase
) == MINUS_EXPR
3974 || TREE_CODE (ubase
) == POINTER_PLUS_EXPR
)
3976 if (TREE_CODE (TREE_OPERAND (ubase
, 1)) == INTEGER_CST
)
3977 ubase
= TREE_OPERAND (ubase
, 0);
3980 /* Strips the constant part. */
3981 if (TREE_CODE (cbase
) == PLUS_EXPR
3982 || TREE_CODE (cbase
) == MINUS_EXPR
3983 || TREE_CODE (cbase
) == POINTER_PLUS_EXPR
)
3985 if (TREE_CODE (TREE_OPERAND (cbase
, 1)) == INTEGER_CST
)
3986 cbase
= TREE_OPERAND (cbase
, 0);
3991 if (((TREE_CODE (ubase
) == SSA_NAME
)
3992 || (TREE_CODE (ubase
) == ADDR_EXPR
3993 && is_gimple_min_invariant (ubase
)))
3994 && (TREE_CODE (cbase
) == INTEGER_CST
))
3997 if (((TREE_CODE (cbase
) == SSA_NAME
)
3998 || (TREE_CODE (cbase
) == ADDR_EXPR
3999 && is_gimple_min_invariant (cbase
)))
4000 && (TREE_CODE (ubase
) == INTEGER_CST
))
4006 if (operand_equal_p (ubase
, cbase
, 0))
4009 if (TREE_CODE (ubase
) == ADDR_EXPR
4010 && TREE_CODE (cbase
) == ADDR_EXPR
)
4014 usym
= TREE_OPERAND (ubase
, 0);
4015 csym
= TREE_OPERAND (cbase
, 0);
4016 if (TREE_CODE (usym
) == ARRAY_REF
)
4018 tree ind
= TREE_OPERAND (usym
, 1);
4019 if (TREE_CODE (ind
) == INTEGER_CST
4020 && tree_fits_shwi_p (ind
)
4021 && tree_to_shwi (ind
) == 0)
4022 usym
= TREE_OPERAND (usym
, 0);
4024 if (TREE_CODE (csym
) == ARRAY_REF
)
4026 tree ind
= TREE_OPERAND (csym
, 1);
4027 if (TREE_CODE (ind
) == INTEGER_CST
4028 && tree_fits_shwi_p (ind
)
4029 && tree_to_shwi (ind
) == 0)
4030 csym
= TREE_OPERAND (csym
, 0);
4032 if (operand_equal_p (usym
, csym
, 0))
4035 /* Now do more complex comparison */
4036 tree_to_aff_combination (ubase
, TREE_TYPE (ubase
), &ubase_aff
);
4037 tree_to_aff_combination (cbase
, TREE_TYPE (cbase
), &cbase_aff
);
4038 if (compare_aff_trees (&ubase_aff
, &cbase_aff
))
4042 tree_to_aff_combination (ub
, TREE_TYPE (ub
), &ubase_aff
);
4043 tree_to_aff_combination (cb
, TREE_TYPE (cb
), &cbase_aff
);
4045 aff_combination_scale (&cbase_aff
, -1 * ratio
);
4046 aff_combination_add (&ubase_aff
, &cbase_aff
);
4047 expr
= aff_combination_to_tree (&ubase_aff
);
4048 return get_expr_id (data
, expr
);
4053 /* Determines the cost of the computation by that USE is expressed
4054 from induction variable CAND. If ADDRESS_P is true, we just need
4055 to create an address from it, otherwise we want to get it into
4056 register. A set of invariants we depend on is stored in
4057 DEPENDS_ON. AT is the statement at that the value is computed.
4058 If CAN_AUTOINC is nonnull, use it to record whether autoinc
4059 addressing is likely. */
4062 get_computation_cost_at (struct ivopts_data
*data
,
4063 struct iv_use
*use
, struct iv_cand
*cand
,
4064 bool address_p
, bitmap
*depends_on
, gimple at
,
4068 tree ubase
= use
->iv
->base
, ustep
= use
->iv
->step
;
4070 tree utype
= TREE_TYPE (ubase
), ctype
;
4071 unsigned HOST_WIDE_INT cstepi
, offset
= 0;
4072 HOST_WIDE_INT ratio
, aratio
;
4073 bool var_present
, symbol_present
, stmt_is_after_inc
;
4076 bool speed
= optimize_bb_for_speed_p (gimple_bb (at
));
4077 enum machine_mode mem_mode
= (address_p
4078 ? TYPE_MODE (TREE_TYPE (*use
->op_p
))
4083 /* Only consider real candidates. */
4085 return infinite_cost
;
4087 cbase
= cand
->iv
->base
;
4088 cstep
= cand
->iv
->step
;
4089 ctype
= TREE_TYPE (cbase
);
4091 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
4093 /* We do not have a precision to express the values of use. */
4094 return infinite_cost
;
4098 || (use
->iv
->base_object
4099 && cand
->iv
->base_object
4100 && POINTER_TYPE_P (TREE_TYPE (use
->iv
->base_object
))
4101 && POINTER_TYPE_P (TREE_TYPE (cand
->iv
->base_object
))))
4103 /* Do not try to express address of an object with computation based
4104 on address of a different object. This may cause problems in rtl
4105 level alias analysis (that does not expect this to be happening,
4106 as this is illegal in C), and would be unlikely to be useful
4108 if (use
->iv
->base_object
4109 && cand
->iv
->base_object
4110 && !operand_equal_p (use
->iv
->base_object
, cand
->iv
->base_object
, 0))
4111 return infinite_cost
;
4114 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
4116 /* TODO -- add direct handling of this case. */
4120 /* CSTEPI is removed from the offset in case statement is after the
4121 increment. If the step is not constant, we use zero instead.
4122 This is a bit imprecise (there is the extra addition), but
4123 redundancy elimination is likely to transform the code so that
4124 it uses value of the variable before increment anyway,
4125 so it is not that much unrealistic. */
4126 if (cst_and_fits_in_hwi (cstep
))
4127 cstepi
= int_cst_value (cstep
);
4131 if (!constant_multiple_of (ustep
, cstep
, &rat
))
4132 return infinite_cost
;
4134 if (wi::fits_shwi_p (rat
))
4135 ratio
= rat
.to_shwi ();
4137 return infinite_cost
;
4140 ctype
= TREE_TYPE (cbase
);
4142 stmt_is_after_inc
= stmt_after_increment (data
->current_loop
, cand
, at
);
4144 /* use = ubase + ratio * (var - cbase). If either cbase is a constant
4145 or ratio == 1, it is better to handle this like
4147 ubase - ratio * cbase + ratio * var
4149 (also holds in the case ratio == -1, TODO. */
4151 if (cst_and_fits_in_hwi (cbase
))
4153 offset
= - ratio
* int_cst_value (cbase
);
4154 cost
= difference_cost (data
,
4155 ubase
, build_int_cst (utype
, 0),
4156 &symbol_present
, &var_present
, &offset
,
4158 cost
.cost
/= avg_loop_niter (data
->current_loop
);
4160 else if (ratio
== 1)
4162 tree real_cbase
= cbase
;
4164 /* Check to see if any adjustment is needed. */
4165 if (cstepi
== 0 && stmt_is_after_inc
)
4167 aff_tree real_cbase_aff
;
4170 tree_to_aff_combination (cbase
, TREE_TYPE (real_cbase
),
4172 tree_to_aff_combination (cstep
, TREE_TYPE (cstep
), &cstep_aff
);
4174 aff_combination_add (&real_cbase_aff
, &cstep_aff
);
4175 real_cbase
= aff_combination_to_tree (&real_cbase_aff
);
4178 cost
= difference_cost (data
,
4180 &symbol_present
, &var_present
, &offset
,
4182 cost
.cost
/= avg_loop_niter (data
->current_loop
);
4185 && !POINTER_TYPE_P (ctype
)
4186 && multiplier_allowed_in_address_p
4188 TYPE_ADDR_SPACE (TREE_TYPE (utype
))))
4191 = fold_build2 (MULT_EXPR
, ctype
, cbase
, build_int_cst (ctype
, ratio
));
4192 cost
= difference_cost (data
,
4194 &symbol_present
, &var_present
, &offset
,
4196 cost
.cost
/= avg_loop_niter (data
->current_loop
);
4200 cost
= force_var_cost (data
, cbase
, depends_on
);
4201 cost
= add_costs (cost
,
4202 difference_cost (data
,
4203 ubase
, build_int_cst (utype
, 0),
4204 &symbol_present
, &var_present
,
4205 &offset
, depends_on
));
4206 cost
.cost
/= avg_loop_niter (data
->current_loop
);
4207 cost
.cost
+= add_cost (data
->speed
, TYPE_MODE (ctype
));
4213 get_loop_invariant_expr_id (data
, ubase
, cbase
, ratio
, address_p
);
4214 /* Clear depends on. */
4215 if (*inv_expr_id
!= -1 && depends_on
&& *depends_on
)
4216 bitmap_clear (*depends_on
);
4219 /* If we are after the increment, the value of the candidate is higher by
4221 if (stmt_is_after_inc
)
4222 offset
-= ratio
* cstepi
;
4224 /* Now the computation is in shape symbol + var1 + const + ratio * var2.
4225 (symbol/var1/const parts may be omitted). If we are looking for an
4226 address, find the cost of addressing this. */
4228 return add_costs (cost
,
4229 get_address_cost (symbol_present
, var_present
,
4230 offset
, ratio
, cstepi
,
4232 TYPE_ADDR_SPACE (TREE_TYPE (utype
)),
4233 speed
, stmt_is_after_inc
,
4236 /* Otherwise estimate the costs for computing the expression. */
4237 if (!symbol_present
&& !var_present
&& !offset
)
4240 cost
.cost
+= mult_by_coeff_cost (ratio
, TYPE_MODE (ctype
), speed
);
4244 /* Symbol + offset should be compile-time computable so consider that they
4245 are added once to the variable, if present. */
4246 if (var_present
&& (symbol_present
|| offset
))
4247 cost
.cost
+= adjust_setup_cost (data
,
4248 add_cost (speed
, TYPE_MODE (ctype
)));
4250 /* Having offset does not affect runtime cost in case it is added to
4251 symbol, but it increases complexity. */
4255 cost
.cost
+= add_cost (speed
, TYPE_MODE (ctype
));
4257 aratio
= ratio
> 0 ? ratio
: -ratio
;
4259 cost
.cost
+= mult_by_coeff_cost (aratio
, TYPE_MODE (ctype
), speed
);
4264 *can_autoinc
= false;
4267 /* Just get the expression, expand it and measure the cost. */
4268 tree comp
= get_computation_at (data
->current_loop
, use
, cand
, at
);
4271 return infinite_cost
;
4274 comp
= build_simple_mem_ref (comp
);
4276 return new_cost (computation_cost (comp
, speed
), 0);
4280 /* Determines the cost of the computation by that USE is expressed
4281 from induction variable CAND. If ADDRESS_P is true, we just need
4282 to create an address from it, otherwise we want to get it into
4283 register. A set of invariants we depend on is stored in
4284 DEPENDS_ON. If CAN_AUTOINC is nonnull, use it to record whether
4285 autoinc addressing is likely. */
4288 get_computation_cost (struct ivopts_data
*data
,
4289 struct iv_use
*use
, struct iv_cand
*cand
,
4290 bool address_p
, bitmap
*depends_on
,
4291 bool *can_autoinc
, int *inv_expr_id
)
4293 return get_computation_cost_at (data
,
4294 use
, cand
, address_p
, depends_on
, use
->stmt
,
4295 can_autoinc
, inv_expr_id
);
4298 /* Determines cost of basing replacement of USE on CAND in a generic
4302 determine_use_iv_cost_generic (struct ivopts_data
*data
,
4303 struct iv_use
*use
, struct iv_cand
*cand
)
4307 int inv_expr_id
= -1;
4309 /* The simple case first -- if we need to express value of the preserved
4310 original biv, the cost is 0. This also prevents us from counting the
4311 cost of increment twice -- once at this use and once in the cost of
4313 if (cand
->pos
== IP_ORIGINAL
4314 && cand
->incremented_at
== use
->stmt
)
4316 set_use_iv_cost (data
, use
, cand
, no_cost
, NULL
, NULL_TREE
,
4321 cost
= get_computation_cost (data
, use
, cand
, false, &depends_on
,
4322 NULL
, &inv_expr_id
);
4324 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
, ERROR_MARK
,
4327 return !infinite_cost_p (cost
);
4330 /* Determines cost of basing replacement of USE on CAND in an address. */
4333 determine_use_iv_cost_address (struct ivopts_data
*data
,
4334 struct iv_use
*use
, struct iv_cand
*cand
)
4338 int inv_expr_id
= -1;
4339 comp_cost cost
= get_computation_cost (data
, use
, cand
, true, &depends_on
,
4340 &can_autoinc
, &inv_expr_id
);
4342 if (cand
->ainc_use
== use
)
4345 cost
.cost
-= cand
->cost_step
;
4346 /* If we generated the candidate solely for exploiting autoincrement
4347 opportunities, and it turns out it can't be used, set the cost to
4348 infinity to make sure we ignore it. */
4349 else if (cand
->pos
== IP_AFTER_USE
|| cand
->pos
== IP_BEFORE_USE
)
4350 cost
= infinite_cost
;
4352 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
, ERROR_MARK
,
4355 return !infinite_cost_p (cost
);
4358 /* Computes value of candidate CAND at position AT in iteration NITER, and
4359 stores it to VAL. */
4362 cand_value_at (struct loop
*loop
, struct iv_cand
*cand
, gimple at
, tree niter
,
4365 aff_tree step
, delta
, nit
;
4366 struct iv
*iv
= cand
->iv
;
4367 tree type
= TREE_TYPE (iv
->base
);
4368 tree steptype
= type
;
4369 if (POINTER_TYPE_P (type
))
4370 steptype
= sizetype
;
4372 tree_to_aff_combination (iv
->step
, steptype
, &step
);
4373 tree_to_aff_combination (niter
, TREE_TYPE (niter
), &nit
);
4374 aff_combination_convert (&nit
, steptype
);
4375 aff_combination_mult (&nit
, &step
, &delta
);
4376 if (stmt_after_increment (loop
, cand
, at
))
4377 aff_combination_add (&delta
, &step
);
4379 tree_to_aff_combination (iv
->base
, type
, val
);
4380 aff_combination_add (val
, &delta
);
4383 /* Returns period of induction variable iv. */
4386 iv_period (struct iv
*iv
)
4388 tree step
= iv
->step
, period
, type
;
4391 gcc_assert (step
&& TREE_CODE (step
) == INTEGER_CST
);
4393 type
= unsigned_type_for (TREE_TYPE (step
));
4394 /* Period of the iv is lcm (step, type_range)/step -1,
4395 i.e., N*type_range/step - 1. Since type range is power
4396 of two, N == (step >> num_of_ending_zeros_binary (step),
4397 so the final result is
4399 (type_range >> num_of_ending_zeros_binary (step)) - 1
4402 pow2div
= num_ending_zeros (step
);
4404 period
= build_low_bits_mask (type
,
4405 (TYPE_PRECISION (type
)
4406 - tree_to_uhwi (pow2div
)));
4411 /* Returns the comparison operator used when eliminating the iv USE. */
4413 static enum tree_code
4414 iv_elimination_compare (struct ivopts_data
*data
, struct iv_use
*use
)
4416 struct loop
*loop
= data
->current_loop
;
4420 ex_bb
= gimple_bb (use
->stmt
);
4421 exit
= EDGE_SUCC (ex_bb
, 0);
4422 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
4423 exit
= EDGE_SUCC (ex_bb
, 1);
4425 return (exit
->flags
& EDGE_TRUE_VALUE
? EQ_EXPR
: NE_EXPR
);
4429 strip_wrap_conserving_type_conversions (tree exp
)
4431 while (tree_ssa_useless_type_conversion (exp
)
4432 && (nowrap_type_p (TREE_TYPE (exp
))
4433 == nowrap_type_p (TREE_TYPE (TREE_OPERAND (exp
, 0)))))
4434 exp
= TREE_OPERAND (exp
, 0);
4438 /* Walk the SSA form and check whether E == WHAT. Fairly simplistic, we
4439 check for an exact match. */
4442 expr_equal_p (tree e
, tree what
)
4445 enum tree_code code
;
4447 e
= strip_wrap_conserving_type_conversions (e
);
4448 what
= strip_wrap_conserving_type_conversions (what
);
4450 code
= TREE_CODE (what
);
4451 if (TREE_TYPE (e
) != TREE_TYPE (what
))
4454 if (operand_equal_p (e
, what
, 0))
4457 if (TREE_CODE (e
) != SSA_NAME
)
4460 stmt
= SSA_NAME_DEF_STMT (e
);
4461 if (gimple_code (stmt
) != GIMPLE_ASSIGN
4462 || gimple_assign_rhs_code (stmt
) != code
)
4465 switch (get_gimple_rhs_class (code
))
4467 case GIMPLE_BINARY_RHS
:
4468 if (!expr_equal_p (gimple_assign_rhs2 (stmt
), TREE_OPERAND (what
, 1)))
4472 case GIMPLE_UNARY_RHS
:
4473 case GIMPLE_SINGLE_RHS
:
4474 return expr_equal_p (gimple_assign_rhs1 (stmt
), TREE_OPERAND (what
, 0));
4480 /* Returns true if we can prove that BASE - OFFSET does not overflow. For now,
4481 we only detect the situation that BASE = SOMETHING + OFFSET, where the
4482 calculation is performed in non-wrapping type.
4484 TODO: More generally, we could test for the situation that
4485 BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero.
4486 This would require knowing the sign of OFFSET.
4488 Also, we only look for the first addition in the computation of BASE.
4489 More complex analysis would be better, but introducing it just for
4490 this optimization seems like an overkill. */
4493 difference_cannot_overflow_p (tree base
, tree offset
)
4495 enum tree_code code
;
4498 if (!nowrap_type_p (TREE_TYPE (base
)))
4501 base
= expand_simple_operations (base
);
4503 if (TREE_CODE (base
) == SSA_NAME
)
4505 gimple stmt
= SSA_NAME_DEF_STMT (base
);
4507 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
4510 code
= gimple_assign_rhs_code (stmt
);
4511 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
4514 e1
= gimple_assign_rhs1 (stmt
);
4515 e2
= gimple_assign_rhs2 (stmt
);
4519 code
= TREE_CODE (base
);
4520 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
4522 e1
= TREE_OPERAND (base
, 0);
4523 e2
= TREE_OPERAND (base
, 1);
4526 /* TODO: deeper inspection may be necessary to prove the equality. */
4530 return expr_equal_p (e1
, offset
) || expr_equal_p (e2
, offset
);
4531 case POINTER_PLUS_EXPR
:
4532 return expr_equal_p (e2
, offset
);
4539 /* Tries to replace loop exit by one formulated in terms of a LT_EXPR
4540 comparison with CAND. NITER describes the number of iterations of
4541 the loops. If successful, the comparison in COMP_P is altered accordingly.
4543 We aim to handle the following situation:
4559 Here, the number of iterations of the loop is (a + 1 > b) ? 0 : b - a - 1.
4560 We aim to optimize this to
4568 while (p < p_0 - a + b);
4570 This preserves the correctness, since the pointer arithmetics does not
4571 overflow. More precisely:
4573 1) if a + 1 <= b, then p_0 - a + b is the final value of p, hence there is no
4574 overflow in computing it or the values of p.
4575 2) if a + 1 > b, then we need to verify that the expression p_0 - a does not
4576 overflow. To prove this, we use the fact that p_0 = base + a. */
4579 iv_elimination_compare_lt (struct ivopts_data
*data
,
4580 struct iv_cand
*cand
, enum tree_code
*comp_p
,
4581 struct tree_niter_desc
*niter
)
4583 tree cand_type
, a
, b
, mbz
, nit_type
= TREE_TYPE (niter
->niter
), offset
;
4584 struct affine_tree_combination nit
, tmpa
, tmpb
;
4585 enum tree_code comp
;
4588 /* We need to know that the candidate induction variable does not overflow.
4589 While more complex analysis may be used to prove this, for now just
4590 check that the variable appears in the original program and that it
4591 is computed in a type that guarantees no overflows. */
4592 cand_type
= TREE_TYPE (cand
->iv
->base
);
4593 if (cand
->pos
!= IP_ORIGINAL
|| !nowrap_type_p (cand_type
))
4596 /* Make sure that the loop iterates till the loop bound is hit, as otherwise
4597 the calculation of the BOUND could overflow, making the comparison
4599 if (!data
->loop_single_exit_p
)
4602 /* We need to be able to decide whether candidate is increasing or decreasing
4603 in order to choose the right comparison operator. */
4604 if (!cst_and_fits_in_hwi (cand
->iv
->step
))
4606 step
= int_cst_value (cand
->iv
->step
);
4608 /* Check that the number of iterations matches the expected pattern:
4609 a + 1 > b ? 0 : b - a - 1. */
4610 mbz
= niter
->may_be_zero
;
4611 if (TREE_CODE (mbz
) == GT_EXPR
)
4613 /* Handle a + 1 > b. */
4614 tree op0
= TREE_OPERAND (mbz
, 0);
4615 if (TREE_CODE (op0
) == PLUS_EXPR
&& integer_onep (TREE_OPERAND (op0
, 1)))
4617 a
= TREE_OPERAND (op0
, 0);
4618 b
= TREE_OPERAND (mbz
, 1);
4623 else if (TREE_CODE (mbz
) == LT_EXPR
)
4625 tree op1
= TREE_OPERAND (mbz
, 1);
4627 /* Handle b < a + 1. */
4628 if (TREE_CODE (op1
) == PLUS_EXPR
&& integer_onep (TREE_OPERAND (op1
, 1)))
4630 a
= TREE_OPERAND (op1
, 0);
4631 b
= TREE_OPERAND (mbz
, 0);
4639 /* Expected number of iterations is B - A - 1. Check that it matches
4640 the actual number, i.e., that B - A - NITER = 1. */
4641 tree_to_aff_combination (niter
->niter
, nit_type
, &nit
);
4642 tree_to_aff_combination (fold_convert (nit_type
, a
), nit_type
, &tmpa
);
4643 tree_to_aff_combination (fold_convert (nit_type
, b
), nit_type
, &tmpb
);
4644 aff_combination_scale (&nit
, -1);
4645 aff_combination_scale (&tmpa
, -1);
4646 aff_combination_add (&tmpb
, &tmpa
);
4647 aff_combination_add (&tmpb
, &nit
);
4648 if (tmpb
.n
!= 0 || tmpb
.offset
!= 1)
4651 /* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not
4653 offset
= fold_build2 (MULT_EXPR
, TREE_TYPE (cand
->iv
->step
),
4655 fold_convert (TREE_TYPE (cand
->iv
->step
), a
));
4656 if (!difference_cannot_overflow_p (cand
->iv
->base
, offset
))
4659 /* Determine the new comparison operator. */
4660 comp
= step
< 0 ? GT_EXPR
: LT_EXPR
;
4661 if (*comp_p
== NE_EXPR
)
4663 else if (*comp_p
== EQ_EXPR
)
4664 *comp_p
= invert_tree_comparison (comp
, false);
4671 /* Check whether it is possible to express the condition in USE by comparison
4672 of candidate CAND. If so, store the value compared with to BOUND, and the
4673 comparison operator to COMP. */
4676 may_eliminate_iv (struct ivopts_data
*data
,
4677 struct iv_use
*use
, struct iv_cand
*cand
, tree
*bound
,
4678 enum tree_code
*comp
)
4683 struct loop
*loop
= data
->current_loop
;
4685 struct tree_niter_desc
*desc
= NULL
;
4687 if (TREE_CODE (cand
->iv
->step
) != INTEGER_CST
)
4690 /* For now works only for exits that dominate the loop latch.
4691 TODO: extend to other conditions inside loop body. */
4692 ex_bb
= gimple_bb (use
->stmt
);
4693 if (use
->stmt
!= last_stmt (ex_bb
)
4694 || gimple_code (use
->stmt
) != GIMPLE_COND
4695 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, ex_bb
))
4698 exit
= EDGE_SUCC (ex_bb
, 0);
4699 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
4700 exit
= EDGE_SUCC (ex_bb
, 1);
4701 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
4704 desc
= niter_for_exit (data
, exit
);
4708 /* Determine whether we can use the variable to test the exit condition.
4709 This is the case iff the period of the induction variable is greater
4710 than the number of iterations for which the exit condition is true. */
4711 period
= iv_period (cand
->iv
);
4713 /* If the number of iterations is constant, compare against it directly. */
4714 if (TREE_CODE (desc
->niter
) == INTEGER_CST
)
4716 /* See cand_value_at. */
4717 if (stmt_after_increment (loop
, cand
, use
->stmt
))
4719 if (!tree_int_cst_lt (desc
->niter
, period
))
4724 if (tree_int_cst_lt (period
, desc
->niter
))
4729 /* If not, and if this is the only possible exit of the loop, see whether
4730 we can get a conservative estimate on the number of iterations of the
4731 entire loop and compare against that instead. */
4734 widest_int period_value
, max_niter
;
4736 max_niter
= desc
->max
;
4737 if (stmt_after_increment (loop
, cand
, use
->stmt
))
4739 period_value
= wi::to_widest (period
);
4740 if (wi::gtu_p (max_niter
, period_value
))
4742 /* See if we can take advantage of inferred loop bound information. */
4743 if (data
->loop_single_exit_p
)
4745 if (!max_loop_iterations (loop
, &max_niter
))
4747 /* The loop bound is already adjusted by adding 1. */
4748 if (wi::gtu_p (max_niter
, period_value
))
4756 cand_value_at (loop
, cand
, use
->stmt
, desc
->niter
, &bnd
);
4758 *bound
= aff_combination_to_tree (&bnd
);
4759 *comp
= iv_elimination_compare (data
, use
);
4761 /* It is unlikely that computing the number of iterations using division
4762 would be more profitable than keeping the original induction variable. */
4763 if (expression_expensive_p (*bound
))
4766 /* Sometimes, it is possible to handle the situation that the number of
4767 iterations may be zero unless additional assumtions by using <
4768 instead of != in the exit condition.
4770 TODO: we could also calculate the value MAY_BE_ZERO ? 0 : NITER and
4771 base the exit condition on it. However, that is often too
4773 if (!integer_zerop (desc
->may_be_zero
))
4774 return iv_elimination_compare_lt (data
, cand
, comp
, desc
);
4779 /* Calculates the cost of BOUND, if it is a PARM_DECL. A PARM_DECL must
4780 be copied, if is is used in the loop body and DATA->body_includes_call. */
4783 parm_decl_cost (struct ivopts_data
*data
, tree bound
)
4785 tree sbound
= bound
;
4786 STRIP_NOPS (sbound
);
4788 if (TREE_CODE (sbound
) == SSA_NAME
4789 && SSA_NAME_IS_DEFAULT_DEF (sbound
)
4790 && TREE_CODE (SSA_NAME_VAR (sbound
)) == PARM_DECL
4791 && data
->body_includes_call
)
4792 return COSTS_N_INSNS (1);
4797 /* Determines cost of basing replacement of USE on CAND in a condition. */
4800 determine_use_iv_cost_condition (struct ivopts_data
*data
,
4801 struct iv_use
*use
, struct iv_cand
*cand
)
4803 tree bound
= NULL_TREE
;
4805 bitmap depends_on_elim
= NULL
, depends_on_express
= NULL
, depends_on
;
4806 comp_cost elim_cost
, express_cost
, cost
, bound_cost
;
4808 int elim_inv_expr_id
= -1, express_inv_expr_id
= -1, inv_expr_id
;
4809 tree
*control_var
, *bound_cst
;
4810 enum tree_code comp
= ERROR_MARK
;
4812 /* Only consider real candidates. */
4815 set_use_iv_cost (data
, use
, cand
, infinite_cost
, NULL
, NULL_TREE
,
4820 /* Try iv elimination. */
4821 if (may_eliminate_iv (data
, use
, cand
, &bound
, &comp
))
4823 elim_cost
= force_var_cost (data
, bound
, &depends_on_elim
);
4824 if (elim_cost
.cost
== 0)
4825 elim_cost
.cost
= parm_decl_cost (data
, bound
);
4826 else if (TREE_CODE (bound
) == INTEGER_CST
)
4828 /* If we replace a loop condition 'i < n' with 'p < base + n',
4829 depends_on_elim will have 'base' and 'n' set, which implies
4830 that both 'base' and 'n' will be live during the loop. More likely,
4831 'base + n' will be loop invariant, resulting in only one live value
4832 during the loop. So in that case we clear depends_on_elim and set
4833 elim_inv_expr_id instead. */
4834 if (depends_on_elim
&& bitmap_count_bits (depends_on_elim
) > 1)
4836 elim_inv_expr_id
= get_expr_id (data
, bound
);
4837 bitmap_clear (depends_on_elim
);
4839 /* The bound is a loop invariant, so it will be only computed
4841 elim_cost
.cost
= adjust_setup_cost (data
, elim_cost
.cost
);
4844 elim_cost
= infinite_cost
;
4846 /* Try expressing the original giv. If it is compared with an invariant,
4847 note that we cannot get rid of it. */
4848 ok
= extract_cond_operands (data
, use
->stmt
, &control_var
, &bound_cst
,
4852 /* When the condition is a comparison of the candidate IV against
4853 zero, prefer this IV.
4855 TODO: The constant that we're subtracting from the cost should
4856 be target-dependent. This information should be added to the
4857 target costs for each backend. */
4858 if (!infinite_cost_p (elim_cost
) /* Do not try to decrease infinite! */
4859 && integer_zerop (*bound_cst
)
4860 && (operand_equal_p (*control_var
, cand
->var_after
, 0)
4861 || operand_equal_p (*control_var
, cand
->var_before
, 0)))
4862 elim_cost
.cost
-= 1;
4864 express_cost
= get_computation_cost (data
, use
, cand
, false,
4865 &depends_on_express
, NULL
,
4866 &express_inv_expr_id
);
4867 fd_ivopts_data
= data
;
4868 walk_tree (&cmp_iv
->base
, find_depends
, &depends_on_express
, NULL
);
4870 /* Count the cost of the original bound as well. */
4871 bound_cost
= force_var_cost (data
, *bound_cst
, NULL
);
4872 if (bound_cost
.cost
== 0)
4873 bound_cost
.cost
= parm_decl_cost (data
, *bound_cst
);
4874 else if (TREE_CODE (*bound_cst
) == INTEGER_CST
)
4875 bound_cost
.cost
= 0;
4876 express_cost
.cost
+= bound_cost
.cost
;
4878 /* Choose the better approach, preferring the eliminated IV. */
4879 if (compare_costs (elim_cost
, express_cost
) <= 0)
4882 depends_on
= depends_on_elim
;
4883 depends_on_elim
= NULL
;
4884 inv_expr_id
= elim_inv_expr_id
;
4888 cost
= express_cost
;
4889 depends_on
= depends_on_express
;
4890 depends_on_express
= NULL
;
4893 inv_expr_id
= express_inv_expr_id
;
4896 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, bound
, comp
, inv_expr_id
);
4898 if (depends_on_elim
)
4899 BITMAP_FREE (depends_on_elim
);
4900 if (depends_on_express
)
4901 BITMAP_FREE (depends_on_express
);
4903 return !infinite_cost_p (cost
);
4906 /* Determines cost of basing replacement of USE on CAND. Returns false
4907 if USE cannot be based on CAND. */
4910 determine_use_iv_cost (struct ivopts_data
*data
,
4911 struct iv_use
*use
, struct iv_cand
*cand
)
4915 case USE_NONLINEAR_EXPR
:
4916 return determine_use_iv_cost_generic (data
, use
, cand
);
4919 return determine_use_iv_cost_address (data
, use
, cand
);
4922 return determine_use_iv_cost_condition (data
, use
, cand
);
4929 /* Return true if get_computation_cost indicates that autoincrement is
4930 a possibility for the pair of USE and CAND, false otherwise. */
4933 autoinc_possible_for_pair (struct ivopts_data
*data
, struct iv_use
*use
,
4934 struct iv_cand
*cand
)
4940 if (use
->type
!= USE_ADDRESS
)
4943 cost
= get_computation_cost (data
, use
, cand
, true, &depends_on
,
4944 &can_autoinc
, NULL
);
4946 BITMAP_FREE (depends_on
);
4948 return !infinite_cost_p (cost
) && can_autoinc
;
4951 /* Examine IP_ORIGINAL candidates to see if they are incremented next to a
4952 use that allows autoincrement, and set their AINC_USE if possible. */
4955 set_autoinc_for_original_candidates (struct ivopts_data
*data
)
4959 for (i
= 0; i
< n_iv_cands (data
); i
++)
4961 struct iv_cand
*cand
= iv_cand (data
, i
);
4962 struct iv_use
*closest_before
= NULL
;
4963 struct iv_use
*closest_after
= NULL
;
4964 if (cand
->pos
!= IP_ORIGINAL
)
4967 for (j
= 0; j
< n_iv_uses (data
); j
++)
4969 struct iv_use
*use
= iv_use (data
, j
);
4970 unsigned uid
= gimple_uid (use
->stmt
);
4972 if (gimple_bb (use
->stmt
) != gimple_bb (cand
->incremented_at
))
4975 if (uid
< gimple_uid (cand
->incremented_at
)
4976 && (closest_before
== NULL
4977 || uid
> gimple_uid (closest_before
->stmt
)))
4978 closest_before
= use
;
4980 if (uid
> gimple_uid (cand
->incremented_at
)
4981 && (closest_after
== NULL
4982 || uid
< gimple_uid (closest_after
->stmt
)))
4983 closest_after
= use
;
4986 if (closest_before
!= NULL
4987 && autoinc_possible_for_pair (data
, closest_before
, cand
))
4988 cand
->ainc_use
= closest_before
;
4989 else if (closest_after
!= NULL
4990 && autoinc_possible_for_pair (data
, closest_after
, cand
))
4991 cand
->ainc_use
= closest_after
;
4995 /* Finds the candidates for the induction variables. */
4998 find_iv_candidates (struct ivopts_data
*data
)
5000 /* Add commonly used ivs. */
5001 add_standard_iv_candidates (data
);
5003 /* Add old induction variables. */
5004 add_old_ivs_candidates (data
);
5006 /* Add induction variables derived from uses. */
5007 add_derived_ivs_candidates (data
);
5009 set_autoinc_for_original_candidates (data
);
5011 /* Record the important candidates. */
5012 record_important_candidates (data
);
5015 /* Determines costs of basing the use of the iv on an iv candidate. */
5018 determine_use_iv_costs (struct ivopts_data
*data
)
5022 struct iv_cand
*cand
;
5023 bitmap to_clear
= BITMAP_ALLOC (NULL
);
5025 alloc_use_cost_map (data
);
5027 for (i
= 0; i
< n_iv_uses (data
); i
++)
5029 use
= iv_use (data
, i
);
5031 if (data
->consider_all_candidates
)
5033 for (j
= 0; j
< n_iv_cands (data
); j
++)
5035 cand
= iv_cand (data
, j
);
5036 determine_use_iv_cost (data
, use
, cand
);
5043 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, j
, bi
)
5045 cand
= iv_cand (data
, j
);
5046 if (!determine_use_iv_cost (data
, use
, cand
))
5047 bitmap_set_bit (to_clear
, j
);
5050 /* Remove the candidates for that the cost is infinite from
5051 the list of related candidates. */
5052 bitmap_and_compl_into (use
->related_cands
, to_clear
);
5053 bitmap_clear (to_clear
);
5057 BITMAP_FREE (to_clear
);
5059 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5061 fprintf (dump_file
, "Use-candidate costs:\n");
5063 for (i
= 0; i
< n_iv_uses (data
); i
++)
5065 use
= iv_use (data
, i
);
5067 fprintf (dump_file
, "Use %d:\n", i
);
5068 fprintf (dump_file
, " cand\tcost\tcompl.\tdepends on\n");
5069 for (j
= 0; j
< use
->n_map_members
; j
++)
5071 if (!use
->cost_map
[j
].cand
5072 || infinite_cost_p (use
->cost_map
[j
].cost
))
5075 fprintf (dump_file
, " %d\t%d\t%d\t",
5076 use
->cost_map
[j
].cand
->id
,
5077 use
->cost_map
[j
].cost
.cost
,
5078 use
->cost_map
[j
].cost
.complexity
);
5079 if (use
->cost_map
[j
].depends_on
)
5080 bitmap_print (dump_file
,
5081 use
->cost_map
[j
].depends_on
, "","");
5082 if (use
->cost_map
[j
].inv_expr_id
!= -1)
5083 fprintf (dump_file
, " inv_expr:%d", use
->cost_map
[j
].inv_expr_id
);
5084 fprintf (dump_file
, "\n");
5087 fprintf (dump_file
, "\n");
5089 fprintf (dump_file
, "\n");
5093 /* Determines cost of the candidate CAND. */
5096 determine_iv_cost (struct ivopts_data
*data
, struct iv_cand
*cand
)
5098 comp_cost cost_base
;
5099 unsigned cost
, cost_step
;
5108 /* There are two costs associated with the candidate -- its increment
5109 and its initialization. The second is almost negligible for any loop
5110 that rolls enough, so we take it just very little into account. */
5112 base
= cand
->iv
->base
;
5113 cost_base
= force_var_cost (data
, base
, NULL
);
5114 /* It will be exceptional that the iv register happens to be initialized with
5115 the proper value at no cost. In general, there will at least be a regcopy
5117 if (cost_base
.cost
== 0)
5118 cost_base
.cost
= COSTS_N_INSNS (1);
5119 cost_step
= add_cost (data
->speed
, TYPE_MODE (TREE_TYPE (base
)));
5121 cost
= cost_step
+ adjust_setup_cost (data
, cost_base
.cost
);
5123 /* Prefer the original ivs unless we may gain something by replacing it.
5124 The reason is to make debugging simpler; so this is not relevant for
5125 artificial ivs created by other optimization passes. */
5126 if (cand
->pos
!= IP_ORIGINAL
5127 || !SSA_NAME_VAR (cand
->var_before
)
5128 || DECL_ARTIFICIAL (SSA_NAME_VAR (cand
->var_before
)))
5131 /* Prefer not to insert statements into latch unless there are some
5132 already (so that we do not create unnecessary jumps). */
5133 if (cand
->pos
== IP_END
5134 && empty_block_p (ip_end_pos (data
->current_loop
)))
5138 cand
->cost_step
= cost_step
;
5141 /* Determines costs of computation of the candidates. */
5144 determine_iv_costs (struct ivopts_data
*data
)
5148 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5150 fprintf (dump_file
, "Candidate costs:\n");
5151 fprintf (dump_file
, " cand\tcost\n");
5154 for (i
= 0; i
< n_iv_cands (data
); i
++)
5156 struct iv_cand
*cand
= iv_cand (data
, i
);
5158 determine_iv_cost (data
, cand
);
5160 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5161 fprintf (dump_file
, " %d\t%d\n", i
, cand
->cost
);
5164 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5165 fprintf (dump_file
, "\n");
5168 /* Calculates cost for having SIZE induction variables. */
5171 ivopts_global_cost_for_size (struct ivopts_data
*data
, unsigned size
)
5173 /* We add size to the cost, so that we prefer eliminating ivs
5175 return size
+ estimate_reg_pressure_cost (size
, data
->regs_used
, data
->speed
,
5176 data
->body_includes_call
);
5179 /* For each size of the induction variable set determine the penalty. */
5182 determine_set_costs (struct ivopts_data
*data
)
5186 gimple_stmt_iterator psi
;
5188 struct loop
*loop
= data
->current_loop
;
5191 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5193 fprintf (dump_file
, "Global costs:\n");
5194 fprintf (dump_file
, " target_avail_regs %d\n", target_avail_regs
);
5195 fprintf (dump_file
, " target_clobbered_regs %d\n", target_clobbered_regs
);
5196 fprintf (dump_file
, " target_reg_cost %d\n", target_reg_cost
[data
->speed
]);
5197 fprintf (dump_file
, " target_spill_cost %d\n", target_spill_cost
[data
->speed
]);
5201 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
5203 phi
= gsi_stmt (psi
);
5204 op
= PHI_RESULT (phi
);
5206 if (virtual_operand_p (op
))
5209 if (get_iv (data
, op
))
5215 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
5217 struct version_info
*info
= ver_info (data
, j
);
5219 if (info
->inv_id
&& info
->has_nonlin_use
)
5223 data
->regs_used
= n
;
5224 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5225 fprintf (dump_file
, " regs_used %d\n", n
);
5227 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5229 fprintf (dump_file
, " cost for size:\n");
5230 fprintf (dump_file
, " ivs\tcost\n");
5231 for (j
= 0; j
<= 2 * target_avail_regs
; j
++)
5232 fprintf (dump_file
, " %d\t%d\n", j
,
5233 ivopts_global_cost_for_size (data
, j
));
5234 fprintf (dump_file
, "\n");
5238 /* Returns true if A is a cheaper cost pair than B. */
5241 cheaper_cost_pair (struct cost_pair
*a
, struct cost_pair
*b
)
5251 cmp
= compare_costs (a
->cost
, b
->cost
);
5258 /* In case the costs are the same, prefer the cheaper candidate. */
5259 if (a
->cand
->cost
< b
->cand
->cost
)
5266 /* Returns candidate by that USE is expressed in IVS. */
5268 static struct cost_pair
*
5269 iv_ca_cand_for_use (struct iv_ca
*ivs
, struct iv_use
*use
)
5271 return ivs
->cand_for_use
[use
->id
];
5274 /* Computes the cost field of IVS structure. */
5277 iv_ca_recount_cost (struct ivopts_data
*data
, struct iv_ca
*ivs
)
5279 comp_cost cost
= ivs
->cand_use_cost
;
5281 cost
.cost
+= ivs
->cand_cost
;
5283 cost
.cost
+= ivopts_global_cost_for_size (data
,
5284 ivs
->n_regs
+ ivs
->num_used_inv_expr
);
5289 /* Remove invariants in set INVS to set IVS. */
5292 iv_ca_set_remove_invariants (struct iv_ca
*ivs
, bitmap invs
)
5300 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
5302 ivs
->n_invariant_uses
[iid
]--;
5303 if (ivs
->n_invariant_uses
[iid
] == 0)
5308 /* Set USE not to be expressed by any candidate in IVS. */
5311 iv_ca_set_no_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5314 unsigned uid
= use
->id
, cid
;
5315 struct cost_pair
*cp
;
5317 cp
= ivs
->cand_for_use
[uid
];
5323 ivs
->cand_for_use
[uid
] = NULL
;
5324 ivs
->n_cand_uses
[cid
]--;
5326 if (ivs
->n_cand_uses
[cid
] == 0)
5328 bitmap_clear_bit (ivs
->cands
, cid
);
5329 /* Do not count the pseudocandidates. */
5333 ivs
->cand_cost
-= cp
->cand
->cost
;
5335 iv_ca_set_remove_invariants (ivs
, cp
->cand
->depends_on
);
5338 ivs
->cand_use_cost
= sub_costs (ivs
->cand_use_cost
, cp
->cost
);
5340 iv_ca_set_remove_invariants (ivs
, cp
->depends_on
);
5342 if (cp
->inv_expr_id
!= -1)
5344 ivs
->used_inv_expr
[cp
->inv_expr_id
]--;
5345 if (ivs
->used_inv_expr
[cp
->inv_expr_id
] == 0)
5346 ivs
->num_used_inv_expr
--;
5348 iv_ca_recount_cost (data
, ivs
);
5351 /* Add invariants in set INVS to set IVS. */
5354 iv_ca_set_add_invariants (struct iv_ca
*ivs
, bitmap invs
)
5362 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
5364 ivs
->n_invariant_uses
[iid
]++;
5365 if (ivs
->n_invariant_uses
[iid
] == 1)
5370 /* Set cost pair for USE in set IVS to CP. */
5373 iv_ca_set_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5374 struct iv_use
*use
, struct cost_pair
*cp
)
5376 unsigned uid
= use
->id
, cid
;
5378 if (ivs
->cand_for_use
[uid
] == cp
)
5381 if (ivs
->cand_for_use
[uid
])
5382 iv_ca_set_no_cp (data
, ivs
, use
);
5389 ivs
->cand_for_use
[uid
] = cp
;
5390 ivs
->n_cand_uses
[cid
]++;
5391 if (ivs
->n_cand_uses
[cid
] == 1)
5393 bitmap_set_bit (ivs
->cands
, cid
);
5394 /* Do not count the pseudocandidates. */
5398 ivs
->cand_cost
+= cp
->cand
->cost
;
5400 iv_ca_set_add_invariants (ivs
, cp
->cand
->depends_on
);
5403 ivs
->cand_use_cost
= add_costs (ivs
->cand_use_cost
, cp
->cost
);
5404 iv_ca_set_add_invariants (ivs
, cp
->depends_on
);
5406 if (cp
->inv_expr_id
!= -1)
5408 ivs
->used_inv_expr
[cp
->inv_expr_id
]++;
5409 if (ivs
->used_inv_expr
[cp
->inv_expr_id
] == 1)
5410 ivs
->num_used_inv_expr
++;
5412 iv_ca_recount_cost (data
, ivs
);
5416 /* Extend set IVS by expressing USE by some of the candidates in it
5417 if possible. All important candidates will be considered
5418 if IMPORTANT_CANDIDATES is true. */
5421 iv_ca_add_use (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5422 struct iv_use
*use
, bool important_candidates
)
5424 struct cost_pair
*best_cp
= NULL
, *cp
;
5429 gcc_assert (ivs
->upto
>= use
->id
);
5431 if (ivs
->upto
== use
->id
)
5437 cands
= (important_candidates
? data
->important_candidates
: ivs
->cands
);
5438 EXECUTE_IF_SET_IN_BITMAP (cands
, 0, i
, bi
)
5440 struct iv_cand
*cand
= iv_cand (data
, i
);
5442 cp
= get_use_iv_cost (data
, use
, cand
);
5444 if (cheaper_cost_pair (cp
, best_cp
))
5448 iv_ca_set_cp (data
, ivs
, use
, best_cp
);
5451 /* Get cost for assignment IVS. */
5454 iv_ca_cost (struct iv_ca
*ivs
)
5456 /* This was a conditional expression but it triggered a bug in
5459 return infinite_cost
;
5464 /* Returns true if all dependences of CP are among invariants in IVS. */
5467 iv_ca_has_deps (struct iv_ca
*ivs
, struct cost_pair
*cp
)
5472 if (!cp
->depends_on
)
5475 EXECUTE_IF_SET_IN_BITMAP (cp
->depends_on
, 0, i
, bi
)
5477 if (ivs
->n_invariant_uses
[i
] == 0)
5484 /* Creates change of expressing USE by NEW_CP instead of OLD_CP and chains
5485 it before NEXT_CHANGE. */
5487 static struct iv_ca_delta
*
5488 iv_ca_delta_add (struct iv_use
*use
, struct cost_pair
*old_cp
,
5489 struct cost_pair
*new_cp
, struct iv_ca_delta
*next_change
)
5491 struct iv_ca_delta
*change
= XNEW (struct iv_ca_delta
);
5494 change
->old_cp
= old_cp
;
5495 change
->new_cp
= new_cp
;
5496 change
->next_change
= next_change
;
5501 /* Joins two lists of changes L1 and L2. Destructive -- old lists
5504 static struct iv_ca_delta
*
5505 iv_ca_delta_join (struct iv_ca_delta
*l1
, struct iv_ca_delta
*l2
)
5507 struct iv_ca_delta
*last
;
5515 for (last
= l1
; last
->next_change
; last
= last
->next_change
)
5517 last
->next_change
= l2
;
5522 /* Reverse the list of changes DELTA, forming the inverse to it. */
5524 static struct iv_ca_delta
*
5525 iv_ca_delta_reverse (struct iv_ca_delta
*delta
)
5527 struct iv_ca_delta
*act
, *next
, *prev
= NULL
;
5528 struct cost_pair
*tmp
;
5530 for (act
= delta
; act
; act
= next
)
5532 next
= act
->next_change
;
5533 act
->next_change
= prev
;
5537 act
->old_cp
= act
->new_cp
;
5544 /* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
5545 reverted instead. */
5548 iv_ca_delta_commit (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5549 struct iv_ca_delta
*delta
, bool forward
)
5551 struct cost_pair
*from
, *to
;
5552 struct iv_ca_delta
*act
;
5555 delta
= iv_ca_delta_reverse (delta
);
5557 for (act
= delta
; act
; act
= act
->next_change
)
5561 gcc_assert (iv_ca_cand_for_use (ivs
, act
->use
) == from
);
5562 iv_ca_set_cp (data
, ivs
, act
->use
, to
);
5566 iv_ca_delta_reverse (delta
);
5569 /* Returns true if CAND is used in IVS. */
5572 iv_ca_cand_used_p (struct iv_ca
*ivs
, struct iv_cand
*cand
)
5574 return ivs
->n_cand_uses
[cand
->id
] > 0;
5577 /* Returns number of induction variable candidates in the set IVS. */
5580 iv_ca_n_cands (struct iv_ca
*ivs
)
5582 return ivs
->n_cands
;
5585 /* Free the list of changes DELTA. */
5588 iv_ca_delta_free (struct iv_ca_delta
**delta
)
5590 struct iv_ca_delta
*act
, *next
;
5592 for (act
= *delta
; act
; act
= next
)
5594 next
= act
->next_change
;
5601 /* Allocates new iv candidates assignment. */
5603 static struct iv_ca
*
5604 iv_ca_new (struct ivopts_data
*data
)
5606 struct iv_ca
*nw
= XNEW (struct iv_ca
);
5610 nw
->cand_for_use
= XCNEWVEC (struct cost_pair
*, n_iv_uses (data
));
5611 nw
->n_cand_uses
= XCNEWVEC (unsigned, n_iv_cands (data
));
5612 nw
->cands
= BITMAP_ALLOC (NULL
);
5615 nw
->cand_use_cost
= no_cost
;
5617 nw
->n_invariant_uses
= XCNEWVEC (unsigned, data
->max_inv_id
+ 1);
5619 nw
->used_inv_expr
= XCNEWVEC (unsigned, data
->inv_expr_id
+ 1);
5620 nw
->num_used_inv_expr
= 0;
5625 /* Free memory occupied by the set IVS. */
5628 iv_ca_free (struct iv_ca
**ivs
)
5630 free ((*ivs
)->cand_for_use
);
5631 free ((*ivs
)->n_cand_uses
);
5632 BITMAP_FREE ((*ivs
)->cands
);
5633 free ((*ivs
)->n_invariant_uses
);
5634 free ((*ivs
)->used_inv_expr
);
5639 /* Dumps IVS to FILE. */
5642 iv_ca_dump (struct ivopts_data
*data
, FILE *file
, struct iv_ca
*ivs
)
5644 const char *pref
= " invariants ";
5646 comp_cost cost
= iv_ca_cost (ivs
);
5648 fprintf (file
, " cost: %d (complexity %d)\n", cost
.cost
, cost
.complexity
);
5649 fprintf (file
, " cand_cost: %d\n cand_use_cost: %d (complexity %d)\n",
5650 ivs
->cand_cost
, ivs
->cand_use_cost
.cost
, ivs
->cand_use_cost
.complexity
);
5651 bitmap_print (file
, ivs
->cands
, " candidates: ","\n");
5653 for (i
= 0; i
< ivs
->upto
; i
++)
5655 struct iv_use
*use
= iv_use (data
, i
);
5656 struct cost_pair
*cp
= iv_ca_cand_for_use (ivs
, use
);
5658 fprintf (file
, " use:%d --> iv_cand:%d, cost=(%d,%d)\n",
5659 use
->id
, cp
->cand
->id
, cp
->cost
.cost
, cp
->cost
.complexity
);
5661 fprintf (file
, " use:%d --> ??\n", use
->id
);
5664 for (i
= 1; i
<= data
->max_inv_id
; i
++)
5665 if (ivs
->n_invariant_uses
[i
])
5667 fprintf (file
, "%s%d", pref
, i
);
5670 fprintf (file
, "\n\n");
5673 /* Try changing candidate in IVS to CAND for each use. Return cost of the
5674 new set, and store differences in DELTA. Number of induction variables
5675 in the new set is stored to N_IVS. MIN_NCAND is a flag. When it is true
5676 the function will try to find a solution with mimimal iv candidates. */
5679 iv_ca_extend (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5680 struct iv_cand
*cand
, struct iv_ca_delta
**delta
,
5681 unsigned *n_ivs
, bool min_ncand
)
5686 struct cost_pair
*old_cp
, *new_cp
;
5689 for (i
= 0; i
< ivs
->upto
; i
++)
5691 use
= iv_use (data
, i
);
5692 old_cp
= iv_ca_cand_for_use (ivs
, use
);
5695 && old_cp
->cand
== cand
)
5698 new_cp
= get_use_iv_cost (data
, use
, cand
);
5702 if (!min_ncand
&& !iv_ca_has_deps (ivs
, new_cp
))
5705 if (!min_ncand
&& !cheaper_cost_pair (new_cp
, old_cp
))
5708 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
5711 iv_ca_delta_commit (data
, ivs
, *delta
, true);
5712 cost
= iv_ca_cost (ivs
);
5714 *n_ivs
= iv_ca_n_cands (ivs
);
5715 iv_ca_delta_commit (data
, ivs
, *delta
, false);
5720 /* Try narrowing set IVS by removing CAND. Return the cost of
5721 the new set and store the differences in DELTA. */
5724 iv_ca_narrow (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5725 struct iv_cand
*cand
, struct iv_ca_delta
**delta
)
5729 struct cost_pair
*old_cp
, *new_cp
, *cp
;
5731 struct iv_cand
*cnd
;
5735 for (i
= 0; i
< n_iv_uses (data
); i
++)
5737 use
= iv_use (data
, i
);
5739 old_cp
= iv_ca_cand_for_use (ivs
, use
);
5740 if (old_cp
->cand
!= cand
)
5745 if (data
->consider_all_candidates
)
5747 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, ci
, bi
)
5752 cnd
= iv_cand (data
, ci
);
5754 cp
= get_use_iv_cost (data
, use
, cnd
);
5758 if (!iv_ca_has_deps (ivs
, cp
))
5761 if (!cheaper_cost_pair (cp
, new_cp
))
5769 EXECUTE_IF_AND_IN_BITMAP (use
->related_cands
, ivs
->cands
, 0, ci
, bi
)
5774 cnd
= iv_cand (data
, ci
);
5776 cp
= get_use_iv_cost (data
, use
, cnd
);
5779 if (!iv_ca_has_deps (ivs
, cp
))
5782 if (!cheaper_cost_pair (cp
, new_cp
))
5791 iv_ca_delta_free (delta
);
5792 return infinite_cost
;
5795 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
5798 iv_ca_delta_commit (data
, ivs
, *delta
, true);
5799 cost
= iv_ca_cost (ivs
);
5800 iv_ca_delta_commit (data
, ivs
, *delta
, false);
5805 /* Try optimizing the set of candidates IVS by removing candidates different
5806 from to EXCEPT_CAND from it. Return cost of the new set, and store
5807 differences in DELTA. */
5810 iv_ca_prune (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5811 struct iv_cand
*except_cand
, struct iv_ca_delta
**delta
)
5814 struct iv_ca_delta
*act_delta
, *best_delta
;
5816 comp_cost best_cost
, acost
;
5817 struct iv_cand
*cand
;
5820 best_cost
= iv_ca_cost (ivs
);
5822 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
5824 cand
= iv_cand (data
, i
);
5826 if (cand
== except_cand
)
5829 acost
= iv_ca_narrow (data
, ivs
, cand
, &act_delta
);
5831 if (compare_costs (acost
, best_cost
) < 0)
5834 iv_ca_delta_free (&best_delta
);
5835 best_delta
= act_delta
;
5838 iv_ca_delta_free (&act_delta
);
5847 /* Recurse to possibly remove other unnecessary ivs. */
5848 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
5849 best_cost
= iv_ca_prune (data
, ivs
, except_cand
, delta
);
5850 iv_ca_delta_commit (data
, ivs
, best_delta
, false);
5851 *delta
= iv_ca_delta_join (best_delta
, *delta
);
5855 /* Tries to extend the sets IVS in the best possible way in order
5856 to express the USE. If ORIGINALP is true, prefer candidates from
5857 the original set of IVs, otherwise favor important candidates not
5858 based on any memory object. */
5861 try_add_cand_for (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5862 struct iv_use
*use
, bool originalp
)
5864 comp_cost best_cost
, act_cost
;
5867 struct iv_cand
*cand
;
5868 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
;
5869 struct cost_pair
*cp
;
5871 iv_ca_add_use (data
, ivs
, use
, false);
5872 best_cost
= iv_ca_cost (ivs
);
5874 cp
= iv_ca_cand_for_use (ivs
, use
);
5879 iv_ca_add_use (data
, ivs
, use
, true);
5880 best_cost
= iv_ca_cost (ivs
);
5881 cp
= iv_ca_cand_for_use (ivs
, use
);
5885 best_delta
= iv_ca_delta_add (use
, NULL
, cp
, NULL
);
5886 iv_ca_set_no_cp (data
, ivs
, use
);
5889 /* If ORIGINALP is true, try to find the original IV for the use. Otherwise
5890 first try important candidates not based on any memory object. Only if
5891 this fails, try the specific ones. Rationale -- in loops with many
5892 variables the best choice often is to use just one generic biv. If we
5893 added here many ivs specific to the uses, the optimization algorithm later
5894 would be likely to get stuck in a local minimum, thus causing us to create
5895 too many ivs. The approach from few ivs to more seems more likely to be
5896 successful -- starting from few ivs, replacing an expensive use by a
5897 specific iv should always be a win. */
5898 EXECUTE_IF_SET_IN_BITMAP (data
->important_candidates
, 0, i
, bi
)
5900 cand
= iv_cand (data
, i
);
5902 if (originalp
&& cand
->pos
!=IP_ORIGINAL
)
5905 if (!originalp
&& cand
->iv
->base_object
!= NULL_TREE
)
5908 if (iv_ca_cand_used_p (ivs
, cand
))
5911 cp
= get_use_iv_cost (data
, use
, cand
);
5915 iv_ca_set_cp (data
, ivs
, use
, cp
);
5916 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
,
5918 iv_ca_set_no_cp (data
, ivs
, use
);
5919 act_delta
= iv_ca_delta_add (use
, NULL
, cp
, act_delta
);
5921 if (compare_costs (act_cost
, best_cost
) < 0)
5923 best_cost
= act_cost
;
5925 iv_ca_delta_free (&best_delta
);
5926 best_delta
= act_delta
;
5929 iv_ca_delta_free (&act_delta
);
5932 if (infinite_cost_p (best_cost
))
5934 for (i
= 0; i
< use
->n_map_members
; i
++)
5936 cp
= use
->cost_map
+ i
;
5941 /* Already tried this. */
5942 if (cand
->important
)
5944 if (originalp
&& cand
->pos
== IP_ORIGINAL
)
5946 if (!originalp
&& cand
->iv
->base_object
== NULL_TREE
)
5950 if (iv_ca_cand_used_p (ivs
, cand
))
5954 iv_ca_set_cp (data
, ivs
, use
, cp
);
5955 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
, true);
5956 iv_ca_set_no_cp (data
, ivs
, use
);
5957 act_delta
= iv_ca_delta_add (use
, iv_ca_cand_for_use (ivs
, use
),
5960 if (compare_costs (act_cost
, best_cost
) < 0)
5962 best_cost
= act_cost
;
5965 iv_ca_delta_free (&best_delta
);
5966 best_delta
= act_delta
;
5969 iv_ca_delta_free (&act_delta
);
5973 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
5974 iv_ca_delta_free (&best_delta
);
5976 return !infinite_cost_p (best_cost
);
5979 /* Finds an initial assignment of candidates to uses. */
5981 static struct iv_ca
*
5982 get_initial_solution (struct ivopts_data
*data
, bool originalp
)
5984 struct iv_ca
*ivs
= iv_ca_new (data
);
5987 for (i
= 0; i
< n_iv_uses (data
); i
++)
5988 if (!try_add_cand_for (data
, ivs
, iv_use (data
, i
), originalp
))
5997 /* Tries to improve set of induction variables IVS. */
6000 try_improve_iv_set (struct ivopts_data
*data
, struct iv_ca
*ivs
)
6003 comp_cost acost
, best_cost
= iv_ca_cost (ivs
);
6004 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
, *tmp_delta
;
6005 struct iv_cand
*cand
;
6007 /* Try extending the set of induction variables by one. */
6008 for (i
= 0; i
< n_iv_cands (data
); i
++)
6010 cand
= iv_cand (data
, i
);
6012 if (iv_ca_cand_used_p (ivs
, cand
))
6015 acost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, &n_ivs
, false);
6019 /* If we successfully added the candidate and the set is small enough,
6020 try optimizing it by removing other candidates. */
6021 if (n_ivs
<= ALWAYS_PRUNE_CAND_SET_BOUND
)
6023 iv_ca_delta_commit (data
, ivs
, act_delta
, true);
6024 acost
= iv_ca_prune (data
, ivs
, cand
, &tmp_delta
);
6025 iv_ca_delta_commit (data
, ivs
, act_delta
, false);
6026 act_delta
= iv_ca_delta_join (act_delta
, tmp_delta
);
6029 if (compare_costs (acost
, best_cost
) < 0)
6032 iv_ca_delta_free (&best_delta
);
6033 best_delta
= act_delta
;
6036 iv_ca_delta_free (&act_delta
);
6041 /* Try removing the candidates from the set instead. */
6042 best_cost
= iv_ca_prune (data
, ivs
, NULL
, &best_delta
);
6044 /* Nothing more we can do. */
6049 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
6050 gcc_assert (compare_costs (best_cost
, iv_ca_cost (ivs
)) == 0);
6051 iv_ca_delta_free (&best_delta
);
6055 /* Attempts to find the optimal set of induction variables. We do simple
6056 greedy heuristic -- we try to replace at most one candidate in the selected
6057 solution and remove the unused ivs while this improves the cost. */
6059 static struct iv_ca
*
6060 find_optimal_iv_set_1 (struct ivopts_data
*data
, bool originalp
)
6064 /* Get the initial solution. */
6065 set
= get_initial_solution (data
, originalp
);
6068 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6069 fprintf (dump_file
, "Unable to substitute for ivs, failed.\n");
6073 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6075 fprintf (dump_file
, "Initial set of candidates:\n");
6076 iv_ca_dump (data
, dump_file
, set
);
6079 while (try_improve_iv_set (data
, set
))
6081 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6083 fprintf (dump_file
, "Improved to:\n");
6084 iv_ca_dump (data
, dump_file
, set
);
6091 static struct iv_ca
*
6092 find_optimal_iv_set (struct ivopts_data
*data
)
6095 struct iv_ca
*set
, *origset
;
6097 comp_cost cost
, origcost
;
6099 /* Determine the cost based on a strategy that starts with original IVs,
6100 and try again using a strategy that prefers candidates not based
6102 origset
= find_optimal_iv_set_1 (data
, true);
6103 set
= find_optimal_iv_set_1 (data
, false);
6105 if (!origset
&& !set
)
6108 origcost
= origset
? iv_ca_cost (origset
) : infinite_cost
;
6109 cost
= set
? iv_ca_cost (set
) : infinite_cost
;
6111 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6113 fprintf (dump_file
, "Original cost %d (complexity %d)\n\n",
6114 origcost
.cost
, origcost
.complexity
);
6115 fprintf (dump_file
, "Final cost %d (complexity %d)\n\n",
6116 cost
.cost
, cost
.complexity
);
6119 /* Choose the one with the best cost. */
6120 if (compare_costs (origcost
, cost
) <= 0)
6127 iv_ca_free (&origset
);
6129 for (i
= 0; i
< n_iv_uses (data
); i
++)
6131 use
= iv_use (data
, i
);
6132 use
->selected
= iv_ca_cand_for_use (set
, use
)->cand
;
6138 /* Creates a new induction variable corresponding to CAND. */
6141 create_new_iv (struct ivopts_data
*data
, struct iv_cand
*cand
)
6143 gimple_stmt_iterator incr_pos
;
6153 incr_pos
= gsi_last_bb (ip_normal_pos (data
->current_loop
));
6157 incr_pos
= gsi_last_bb (ip_end_pos (data
->current_loop
));
6165 incr_pos
= gsi_for_stmt (cand
->incremented_at
);
6169 /* Mark that the iv is preserved. */
6170 name_info (data
, cand
->var_before
)->preserve_biv
= true;
6171 name_info (data
, cand
->var_after
)->preserve_biv
= true;
6173 /* Rewrite the increment so that it uses var_before directly. */
6174 find_interesting_uses_op (data
, cand
->var_after
)->selected
= cand
;
6178 gimple_add_tmp_var (cand
->var_before
);
6180 base
= unshare_expr (cand
->iv
->base
);
6182 create_iv (base
, unshare_expr (cand
->iv
->step
),
6183 cand
->var_before
, data
->current_loop
,
6184 &incr_pos
, after
, &cand
->var_before
, &cand
->var_after
);
6187 /* Creates new induction variables described in SET. */
6190 create_new_ivs (struct ivopts_data
*data
, struct iv_ca
*set
)
6193 struct iv_cand
*cand
;
6196 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
6198 cand
= iv_cand (data
, i
);
6199 create_new_iv (data
, cand
);
6202 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6204 fprintf (dump_file
, "\nSelected IV set: \n");
6205 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
6207 cand
= iv_cand (data
, i
);
6208 dump_cand (dump_file
, cand
);
6210 fprintf (dump_file
, "\n");
6214 /* Rewrites USE (definition of iv used in a nonlinear expression)
6215 using candidate CAND. */
6218 rewrite_use_nonlinear_expr (struct ivopts_data
*data
,
6219 struct iv_use
*use
, struct iv_cand
*cand
)
6224 gimple_stmt_iterator bsi
;
6226 /* An important special case -- if we are asked to express value of
6227 the original iv by itself, just exit; there is no need to
6228 introduce a new computation (that might also need casting the
6229 variable to unsigned and back). */
6230 if (cand
->pos
== IP_ORIGINAL
6231 && cand
->incremented_at
== use
->stmt
)
6233 enum tree_code stmt_code
;
6235 gcc_assert (is_gimple_assign (use
->stmt
));
6236 gcc_assert (gimple_assign_lhs (use
->stmt
) == cand
->var_after
);
6238 /* Check whether we may leave the computation unchanged.
6239 This is the case only if it does not rely on other
6240 computations in the loop -- otherwise, the computation
6241 we rely upon may be removed in remove_unused_ivs,
6242 thus leading to ICE. */
6243 stmt_code
= gimple_assign_rhs_code (use
->stmt
);
6244 if (stmt_code
== PLUS_EXPR
6245 || stmt_code
== MINUS_EXPR
6246 || stmt_code
== POINTER_PLUS_EXPR
)
6248 if (gimple_assign_rhs1 (use
->stmt
) == cand
->var_before
)
6249 op
= gimple_assign_rhs2 (use
->stmt
);
6250 else if (gimple_assign_rhs2 (use
->stmt
) == cand
->var_before
)
6251 op
= gimple_assign_rhs1 (use
->stmt
);
6258 if (op
&& expr_invariant_in_loop_p (data
->current_loop
, op
))
6262 comp
= get_computation (data
->current_loop
, use
, cand
);
6263 gcc_assert (comp
!= NULL_TREE
);
6265 switch (gimple_code (use
->stmt
))
6268 tgt
= PHI_RESULT (use
->stmt
);
6270 /* If we should keep the biv, do not replace it. */
6271 if (name_info (data
, tgt
)->preserve_biv
)
6274 bsi
= gsi_after_labels (gimple_bb (use
->stmt
));
6278 tgt
= gimple_assign_lhs (use
->stmt
);
6279 bsi
= gsi_for_stmt (use
->stmt
);
6286 if (!valid_gimple_rhs_p (comp
)
6287 || (gimple_code (use
->stmt
) != GIMPLE_PHI
6288 /* We can't allow re-allocating the stmt as it might be pointed
6290 && (get_gimple_rhs_num_ops (TREE_CODE (comp
))
6291 >= gimple_num_ops (gsi_stmt (bsi
)))))
6293 comp
= force_gimple_operand_gsi (&bsi
, comp
, true, NULL_TREE
,
6294 true, GSI_SAME_STMT
);
6295 if (POINTER_TYPE_P (TREE_TYPE (tgt
)))
6297 duplicate_ssa_name_ptr_info (comp
, SSA_NAME_PTR_INFO (tgt
));
6298 /* As this isn't a plain copy we have to reset alignment
6300 if (SSA_NAME_PTR_INFO (comp
))
6301 mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (comp
));
6305 if (gimple_code (use
->stmt
) == GIMPLE_PHI
)
6307 ass
= gimple_build_assign (tgt
, comp
);
6308 gsi_insert_before (&bsi
, ass
, GSI_SAME_STMT
);
6310 bsi
= gsi_for_stmt (use
->stmt
);
6311 remove_phi_node (&bsi
, false);
6315 gimple_assign_set_rhs_from_tree (&bsi
, comp
);
6316 use
->stmt
= gsi_stmt (bsi
);
6320 /* Performs a peephole optimization to reorder the iv update statement with
6321 a mem ref to enable instruction combining in later phases. The mem ref uses
6322 the iv value before the update, so the reordering transformation requires
6323 adjustment of the offset. CAND is the selected IV_CAND.
6327 t = MEM_REF (base, iv1, 8, 16); // base, index, stride, offset
6335 directly propagating t over to (1) will introduce overlapping live range
6336 thus increase register pressure. This peephole transform it into:
6340 t = MEM_REF (base, iv2, 8, 8);
6347 adjust_iv_update_pos (struct iv_cand
*cand
, struct iv_use
*use
)
6350 gimple iv_update
, stmt
;
6352 gimple_stmt_iterator gsi
, gsi_iv
;
6354 if (cand
->pos
!= IP_NORMAL
)
6357 var_after
= cand
->var_after
;
6358 iv_update
= SSA_NAME_DEF_STMT (var_after
);
6360 bb
= gimple_bb (iv_update
);
6361 gsi
= gsi_last_nondebug_bb (bb
);
6362 stmt
= gsi_stmt (gsi
);
6364 /* Only handle conditional statement for now. */
6365 if (gimple_code (stmt
) != GIMPLE_COND
)
6368 gsi_prev_nondebug (&gsi
);
6369 stmt
= gsi_stmt (gsi
);
6370 if (stmt
!= iv_update
)
6373 gsi_prev_nondebug (&gsi
);
6374 if (gsi_end_p (gsi
))
6377 stmt
= gsi_stmt (gsi
);
6378 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
6381 if (stmt
!= use
->stmt
)
6384 if (TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
6387 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6389 fprintf (dump_file
, "Reordering \n");
6390 print_gimple_stmt (dump_file
, iv_update
, 0, 0);
6391 print_gimple_stmt (dump_file
, use
->stmt
, 0, 0);
6392 fprintf (dump_file
, "\n");
6395 gsi
= gsi_for_stmt (use
->stmt
);
6396 gsi_iv
= gsi_for_stmt (iv_update
);
6397 gsi_move_before (&gsi_iv
, &gsi
);
6399 cand
->pos
= IP_BEFORE_USE
;
6400 cand
->incremented_at
= use
->stmt
;
6403 /* Rewrites USE (address that is an iv) using candidate CAND. */
6406 rewrite_use_address (struct ivopts_data
*data
,
6407 struct iv_use
*use
, struct iv_cand
*cand
)
6410 gimple_stmt_iterator bsi
= gsi_for_stmt (use
->stmt
);
6411 tree base_hint
= NULL_TREE
;
6415 adjust_iv_update_pos (cand
, use
);
6416 ok
= get_computation_aff (data
->current_loop
, use
, cand
, use
->stmt
, &aff
);
6418 unshare_aff_combination (&aff
);
6420 /* To avoid undefined overflow problems, all IV candidates use unsigned
6421 integer types. The drawback is that this makes it impossible for
6422 create_mem_ref to distinguish an IV that is based on a memory object
6423 from one that represents simply an offset.
6425 To work around this problem, we pass a hint to create_mem_ref that
6426 indicates which variable (if any) in aff is an IV based on a memory
6427 object. Note that we only consider the candidate. If this is not
6428 based on an object, the base of the reference is in some subexpression
6429 of the use -- but these will use pointer types, so they are recognized
6430 by the create_mem_ref heuristics anyway. */
6431 if (cand
->iv
->base_object
)
6432 base_hint
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
6434 iv
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
6435 ref
= create_mem_ref (&bsi
, TREE_TYPE (*use
->op_p
), &aff
,
6436 reference_alias_ptr_type (*use
->op_p
),
6437 iv
, base_hint
, data
->speed
);
6438 copy_ref_info (ref
, *use
->op_p
);
6442 /* Rewrites USE (the condition such that one of the arguments is an iv) using
6446 rewrite_use_compare (struct ivopts_data
*data
,
6447 struct iv_use
*use
, struct iv_cand
*cand
)
6449 tree comp
, *var_p
, op
, bound
;
6450 gimple_stmt_iterator bsi
= gsi_for_stmt (use
->stmt
);
6451 enum tree_code compare
;
6452 struct cost_pair
*cp
= get_use_iv_cost (data
, use
, cand
);
6458 tree var
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
6459 tree var_type
= TREE_TYPE (var
);
6462 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6464 fprintf (dump_file
, "Replacing exit test: ");
6465 print_gimple_stmt (dump_file
, use
->stmt
, 0, TDF_SLIM
);
6468 bound
= unshare_expr (fold_convert (var_type
, bound
));
6469 op
= force_gimple_operand (bound
, &stmts
, true, NULL_TREE
);
6471 gsi_insert_seq_on_edge_immediate (
6472 loop_preheader_edge (data
->current_loop
),
6475 gimple_cond_set_lhs (use
->stmt
, var
);
6476 gimple_cond_set_code (use
->stmt
, compare
);
6477 gimple_cond_set_rhs (use
->stmt
, op
);
6481 /* The induction variable elimination failed; just express the original
6483 comp
= get_computation (data
->current_loop
, use
, cand
);
6484 gcc_assert (comp
!= NULL_TREE
);
6486 ok
= extract_cond_operands (data
, use
->stmt
, &var_p
, NULL
, NULL
, NULL
);
6489 *var_p
= force_gimple_operand_gsi (&bsi
, comp
, true, SSA_NAME_VAR (*var_p
),
6490 true, GSI_SAME_STMT
);
6493 /* Rewrites USE using candidate CAND. */
6496 rewrite_use (struct ivopts_data
*data
, struct iv_use
*use
, struct iv_cand
*cand
)
6500 case USE_NONLINEAR_EXPR
:
6501 rewrite_use_nonlinear_expr (data
, use
, cand
);
6505 rewrite_use_address (data
, use
, cand
);
6509 rewrite_use_compare (data
, use
, cand
);
6516 update_stmt (use
->stmt
);
6519 /* Rewrite the uses using the selected induction variables. */
6522 rewrite_uses (struct ivopts_data
*data
)
6525 struct iv_cand
*cand
;
6528 for (i
= 0; i
< n_iv_uses (data
); i
++)
6530 use
= iv_use (data
, i
);
6531 cand
= use
->selected
;
6534 rewrite_use (data
, use
, cand
);
6538 /* Removes the ivs that are not used after rewriting. */
6541 remove_unused_ivs (struct ivopts_data
*data
)
6545 bitmap toremove
= BITMAP_ALLOC (NULL
);
6547 /* Figure out an order in which to release SSA DEFs so that we don't
6548 release something that we'd have to propagate into a debug stmt
6550 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
6552 struct version_info
*info
;
6554 info
= ver_info (data
, j
);
6556 && !integer_zerop (info
->iv
->step
)
6558 && !info
->iv
->have_use_for
6559 && !info
->preserve_biv
)
6561 bitmap_set_bit (toremove
, SSA_NAME_VERSION (info
->iv
->ssa_name
));
6563 tree def
= info
->iv
->ssa_name
;
6565 if (MAY_HAVE_DEBUG_STMTS
&& SSA_NAME_DEF_STMT (def
))
6567 imm_use_iterator imm_iter
;
6568 use_operand_p use_p
;
6572 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, def
)
6574 if (!gimple_debug_bind_p (stmt
))
6577 /* We just want to determine whether to do nothing
6578 (count == 0), to substitute the computed
6579 expression into a single use of the SSA DEF by
6580 itself (count == 1), or to use a debug temp
6581 because the SSA DEF is used multiple times or as
6582 part of a larger expression (count > 1). */
6584 if (gimple_debug_bind_get_value (stmt
) != def
)
6588 BREAK_FROM_IMM_USE_STMT (imm_iter
);
6594 struct iv_use dummy_use
;
6595 struct iv_cand
*best_cand
= NULL
, *cand
;
6596 unsigned i
, best_pref
= 0, cand_pref
;
6598 memset (&dummy_use
, 0, sizeof (dummy_use
));
6599 dummy_use
.iv
= info
->iv
;
6600 for (i
= 0; i
< n_iv_uses (data
) && i
< 64; i
++)
6602 cand
= iv_use (data
, i
)->selected
;
6603 if (cand
== best_cand
)
6605 cand_pref
= operand_equal_p (cand
->iv
->step
,
6609 += TYPE_MODE (TREE_TYPE (cand
->iv
->base
))
6610 == TYPE_MODE (TREE_TYPE (info
->iv
->base
))
6613 += TREE_CODE (cand
->iv
->base
) == INTEGER_CST
6615 if (best_cand
== NULL
|| best_pref
< cand_pref
)
6618 best_pref
= cand_pref
;
6625 tree comp
= get_computation_at (data
->current_loop
,
6626 &dummy_use
, best_cand
,
6627 SSA_NAME_DEF_STMT (def
));
6633 tree vexpr
= make_node (DEBUG_EXPR_DECL
);
6634 DECL_ARTIFICIAL (vexpr
) = 1;
6635 TREE_TYPE (vexpr
) = TREE_TYPE (comp
);
6636 if (SSA_NAME_VAR (def
))
6637 DECL_MODE (vexpr
) = DECL_MODE (SSA_NAME_VAR (def
));
6639 DECL_MODE (vexpr
) = TYPE_MODE (TREE_TYPE (vexpr
));
6640 gimple def_temp
= gimple_build_debug_bind (vexpr
, comp
, NULL
);
6641 gimple_stmt_iterator gsi
;
6643 if (gimple_code (SSA_NAME_DEF_STMT (def
)) == GIMPLE_PHI
)
6644 gsi
= gsi_after_labels (gimple_bb
6645 (SSA_NAME_DEF_STMT (def
)));
6647 gsi
= gsi_for_stmt (SSA_NAME_DEF_STMT (def
));
6649 gsi_insert_before (&gsi
, def_temp
, GSI_SAME_STMT
);
6653 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, def
)
6655 if (!gimple_debug_bind_p (stmt
))
6658 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
6659 SET_USE (use_p
, comp
);
6667 release_defs_bitset (toremove
);
6669 BITMAP_FREE (toremove
);
6672 /* Frees memory occupied by struct tree_niter_desc in *VALUE. Callback
6673 for pointer_map_traverse. */
6676 free_tree_niter_desc (const void *key ATTRIBUTE_UNUSED
, void **value
,
6677 void *data ATTRIBUTE_UNUSED
)
6679 struct tree_niter_desc
*const niter
= (struct tree_niter_desc
*) *value
;
6685 /* Frees data allocated by the optimization of a single loop. */
6688 free_loop_data (struct ivopts_data
*data
)
6696 pointer_map_traverse (data
->niters
, free_tree_niter_desc
, NULL
);
6697 pointer_map_destroy (data
->niters
);
6698 data
->niters
= NULL
;
6701 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
6703 struct version_info
*info
;
6705 info
= ver_info (data
, i
);
6708 info
->has_nonlin_use
= false;
6709 info
->preserve_biv
= false;
6712 bitmap_clear (data
->relevant
);
6713 bitmap_clear (data
->important_candidates
);
6715 for (i
= 0; i
< n_iv_uses (data
); i
++)
6717 struct iv_use
*use
= iv_use (data
, i
);
6720 BITMAP_FREE (use
->related_cands
);
6721 for (j
= 0; j
< use
->n_map_members
; j
++)
6722 if (use
->cost_map
[j
].depends_on
)
6723 BITMAP_FREE (use
->cost_map
[j
].depends_on
);
6724 free (use
->cost_map
);
6727 data
->iv_uses
.truncate (0);
6729 for (i
= 0; i
< n_iv_cands (data
); i
++)
6731 struct iv_cand
*cand
= iv_cand (data
, i
);
6734 if (cand
->depends_on
)
6735 BITMAP_FREE (cand
->depends_on
);
6738 data
->iv_candidates
.truncate (0);
6740 if (data
->version_info_size
< num_ssa_names
)
6742 data
->version_info_size
= 2 * num_ssa_names
;
6743 free (data
->version_info
);
6744 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
6747 data
->max_inv_id
= 0;
6749 FOR_EACH_VEC_ELT (decl_rtl_to_reset
, i
, obj
)
6750 SET_DECL_RTL (obj
, NULL_RTX
);
6752 decl_rtl_to_reset
.truncate (0);
6754 data
->inv_expr_tab
.empty ();
6755 data
->inv_expr_id
= 0;
6758 /* Finalizes data structures used by the iv optimization pass. LOOPS is the
6762 tree_ssa_iv_optimize_finalize (struct ivopts_data
*data
)
6764 free_loop_data (data
);
6765 free (data
->version_info
);
6766 BITMAP_FREE (data
->relevant
);
6767 BITMAP_FREE (data
->important_candidates
);
6769 decl_rtl_to_reset
.release ();
6770 data
->iv_uses
.release ();
6771 data
->iv_candidates
.release ();
6772 data
->inv_expr_tab
.dispose ();
6775 /* Returns true if the loop body BODY includes any function calls. */
6778 loop_body_includes_call (basic_block
*body
, unsigned num_nodes
)
6780 gimple_stmt_iterator gsi
;
6783 for (i
= 0; i
< num_nodes
; i
++)
6784 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
6786 gimple stmt
= gsi_stmt (gsi
);
6787 if (is_gimple_call (stmt
)
6788 && !is_inexpensive_builtin (gimple_call_fndecl (stmt
)))
6794 /* Optimizes the LOOP. Returns true if anything changed. */
6797 tree_ssa_iv_optimize_loop (struct ivopts_data
*data
, struct loop
*loop
)
6799 bool changed
= false;
6800 struct iv_ca
*iv_ca
;
6801 edge exit
= single_dom_exit (loop
);
6804 gcc_assert (!data
->niters
);
6805 data
->current_loop
= loop
;
6806 data
->speed
= optimize_loop_for_speed_p (loop
);
6808 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6810 fprintf (dump_file
, "Processing loop %d\n", loop
->num
);
6814 fprintf (dump_file
, " single exit %d -> %d, exit condition ",
6815 exit
->src
->index
, exit
->dest
->index
);
6816 print_gimple_stmt (dump_file
, last_stmt (exit
->src
), 0, TDF_SLIM
);
6817 fprintf (dump_file
, "\n");
6820 fprintf (dump_file
, "\n");
6823 body
= get_loop_body (loop
);
6824 data
->body_includes_call
= loop_body_includes_call (body
, loop
->num_nodes
);
6825 renumber_gimple_stmt_uids_in_blocks (body
, loop
->num_nodes
);
6828 data
->loop_single_exit_p
= exit
!= NULL
&& loop_only_exit_p (loop
, exit
);
6830 /* For each ssa name determines whether it behaves as an induction variable
6832 if (!find_induction_variables (data
))
6835 /* Finds interesting uses (item 1). */
6836 find_interesting_uses (data
);
6837 if (n_iv_uses (data
) > MAX_CONSIDERED_USES
)
6840 /* Finds candidates for the induction variables (item 2). */
6841 find_iv_candidates (data
);
6843 /* Calculates the costs (item 3, part 1). */
6844 determine_iv_costs (data
);
6845 determine_use_iv_costs (data
);
6846 determine_set_costs (data
);
6848 /* Find the optimal set of induction variables (item 3, part 2). */
6849 iv_ca
= find_optimal_iv_set (data
);
6854 /* Create the new induction variables (item 4, part 1). */
6855 create_new_ivs (data
, iv_ca
);
6856 iv_ca_free (&iv_ca
);
6858 /* Rewrite the uses (item 4, part 2). */
6859 rewrite_uses (data
);
6861 /* Remove the ivs that are unused after rewriting. */
6862 remove_unused_ivs (data
);
6864 /* We have changed the structure of induction variables; it might happen
6865 that definitions in the scev database refer to some of them that were
6870 free_loop_data (data
);
6875 /* Main entry point. Optimizes induction variables in loops. */
6878 tree_ssa_iv_optimize (void)
6881 struct ivopts_data data
;
6883 tree_ssa_iv_optimize_init (&data
);
6885 /* Optimize the loops starting with the innermost ones. */
6886 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
6888 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6889 flow_loop_dump (loop
, dump_file
, NULL
, 1);
6891 tree_ssa_iv_optimize_loop (&data
, loop
);
6894 tree_ssa_iv_optimize_finalize (&data
);