1 /* Induction variable optimizations.
2 Copyright (C) 2003-2015 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"
75 #include "fold-const.h"
76 #include "stor-layout.h"
79 #include "hard-reg-set.h"
81 #include "dominance.h"
83 #include "basic-block.h"
84 #include "gimple-pretty-print.h"
86 #include "hash-table.h"
87 #include "tree-ssa-alias.h"
88 #include "internal-fn.h"
90 #include "gimple-expr.h"
94 #include "gimple-iterator.h"
95 #include "gimplify-me.h"
96 #include "gimple-ssa.h"
97 #include "plugin-api.h"
100 #include "tree-cfg.h"
101 #include "tree-phinodes.h"
102 #include "ssa-iterators.h"
103 #include "stringpool.h"
104 #include "tree-ssanames.h"
105 #include "tree-ssa-loop-ivopts.h"
106 #include "tree-ssa-loop-manip.h"
107 #include "tree-ssa-loop-niter.h"
108 #include "tree-ssa-loop.h"
112 #include "statistics.h"
113 #include "insn-config.h"
118 #include "emit-rtl.h"
122 #include "tree-dfa.h"
123 #include "tree-ssa.h"
125 #include "tree-pass.h"
126 #include "tree-chrec.h"
127 #include "tree-scalar-evolution.h"
129 #include "langhooks.h"
130 #include "tree-affine.h"
132 #include "tree-inline.h"
133 #include "tree-ssa-propagate.h"
134 #include "tree-ssa-address.h"
135 #include "builtins.h"
136 #include "tree-vectorizer.h"
138 /* FIXME: Expressions are expanded to RTL in this pass to determine the
139 cost of different addressing modes. This should be moved to a TBD
140 interface between the GIMPLE and RTL worlds. */
143 /* The infinite cost. */
144 #define INFTY 10000000
146 #define AVG_LOOP_NITER(LOOP) 5
148 /* Returns the expected number of loop iterations for LOOP.
149 The average trip count is computed from profile data if it
152 static inline HOST_WIDE_INT
153 avg_loop_niter (struct loop
*loop
)
155 HOST_WIDE_INT niter
= estimated_stmt_executions_int (loop
);
157 return AVG_LOOP_NITER (loop
);
162 /* Representation of the induction variable. */
165 tree base
; /* Initial value of the iv. */
166 tree base_object
; /* A memory object to that the induction variable points. */
167 tree step
; /* Step of the iv (constant only). */
168 tree ssa_name
; /* The ssa name with the value. */
169 unsigned use_id
; /* The identifier in the use if it is the case. */
170 bool biv_p
; /* Is it a biv? */
171 bool have_use_for
; /* Do we already have a use for it? */
172 bool no_overflow
; /* True if the iv doesn't overflow. */
175 /* Per-ssa version information (induction variable descriptions, etc.). */
178 tree name
; /* The ssa name. */
179 struct iv
*iv
; /* Induction variable description. */
180 bool has_nonlin_use
; /* For a loop-level invariant, whether it is used in
181 an expression that is not an induction variable. */
182 bool preserve_biv
; /* For the original biv, whether to preserve it. */
183 unsigned inv_id
; /* Id of an invariant. */
189 USE_NONLINEAR_EXPR
, /* Use in a nonlinear expression. */
190 USE_ADDRESS
, /* Use in an address. */
191 USE_COMPARE
/* Use is a compare. */
194 /* Cost of a computation. */
197 int cost
; /* The runtime cost. */
198 unsigned complexity
; /* The estimate of the complexity of the code for
199 the computation (in no concrete units --
200 complexity field should be larger for more
201 complex expressions and addressing modes). */
204 static const comp_cost no_cost
= {0, 0};
205 static const comp_cost infinite_cost
= {INFTY
, INFTY
};
207 /* The candidate - cost pair. */
210 struct iv_cand
*cand
; /* The candidate. */
211 comp_cost cost
; /* The cost. */
212 bitmap depends_on
; /* The list of invariants that have to be
214 tree value
; /* For final value elimination, the expression for
215 the final value of the iv. For iv elimination,
216 the new bound to compare with. */
217 enum tree_code comp
; /* For iv elimination, the comparison. */
218 int inv_expr_id
; /* Loop invariant expression id. */
224 unsigned id
; /* The id of the use. */
225 unsigned sub_id
; /* The id of the sub use. */
226 enum use_type type
; /* Type of the use. */
227 struct iv
*iv
; /* The induction variable it is based on. */
228 gimple stmt
; /* Statement in that it occurs. */
229 tree
*op_p
; /* The place where it occurs. */
230 bitmap related_cands
; /* The set of "related" iv candidates, plus the common
233 unsigned n_map_members
; /* Number of candidates in the cost_map list. */
234 struct cost_pair
*cost_map
;
235 /* The costs wrto the iv candidates. */
237 struct iv_cand
*selected
;
238 /* The selected candidate. */
240 struct iv_use
*next
; /* The next sub use. */
241 tree addr_base
; /* Base address with const offset stripped. */
242 unsigned HOST_WIDE_INT addr_offset
;
243 /* Const offset stripped from base address. */
246 /* The position where the iv is computed. */
249 IP_NORMAL
, /* At the end, just before the exit condition. */
250 IP_END
, /* At the end of the latch block. */
251 IP_BEFORE_USE
, /* Immediately before a specific use. */
252 IP_AFTER_USE
, /* Immediately after a specific use. */
253 IP_ORIGINAL
/* The original biv. */
256 /* The induction variable candidate. */
259 unsigned id
; /* The number of the candidate. */
260 bool important
; /* Whether this is an "important" candidate, i.e. such
261 that it should be considered by all uses. */
262 ENUM_BITFIELD(iv_position
) pos
: 8; /* Where it is computed. */
263 gimple incremented_at
;/* For original biv, the statement where it is
265 tree var_before
; /* The variable used for it before increment. */
266 tree var_after
; /* The variable used for it after increment. */
267 struct iv
*iv
; /* The value of the candidate. NULL for
268 "pseudocandidate" used to indicate the possibility
269 to replace the final value of an iv by direct
270 computation of the value. */
271 unsigned cost
; /* Cost of the candidate. */
272 unsigned cost_step
; /* Cost of the candidate's increment operation. */
273 struct iv_use
*ainc_use
; /* For IP_{BEFORE,AFTER}_USE candidates, the place
274 where it is incremented. */
275 bitmap depends_on
; /* The list of invariants that are used in step of the
279 /* Loop invariant expression hashtable entry. */
280 struct iv_inv_expr_ent
287 /* The data used by the induction variable optimizations. */
289 typedef struct iv_use
*iv_use_p
;
291 typedef struct iv_cand
*iv_cand_p
;
293 /* Hashtable helpers. */
295 struct iv_inv_expr_hasher
: typed_free_remove
<iv_inv_expr_ent
>
297 typedef iv_inv_expr_ent
*value_type
;
298 typedef iv_inv_expr_ent
*compare_type
;
299 static inline hashval_t
hash (const iv_inv_expr_ent
*);
300 static inline bool equal (const iv_inv_expr_ent
*, const iv_inv_expr_ent
*);
303 /* Hash function for loop invariant expressions. */
306 iv_inv_expr_hasher::hash (const iv_inv_expr_ent
*expr
)
311 /* Hash table equality function for expressions. */
314 iv_inv_expr_hasher::equal (const iv_inv_expr_ent
*expr1
,
315 const iv_inv_expr_ent
*expr2
)
317 return expr1
->hash
== expr2
->hash
318 && operand_equal_p (expr1
->expr
, expr2
->expr
, 0);
323 /* The currently optimized loop. */
324 struct loop
*current_loop
;
325 source_location loop_loc
;
327 /* Numbers of iterations for all exits of the current loop. */
328 hash_map
<edge
, tree_niter_desc
*> *niters
;
330 /* Number of registers used in it. */
333 /* The size of version_info array allocated. */
334 unsigned version_info_size
;
336 /* The array of information for the ssa names. */
337 struct version_info
*version_info
;
339 /* The hashtable of loop invariant expressions created
341 hash_table
<iv_inv_expr_hasher
> *inv_expr_tab
;
343 /* Loop invariant expression id. */
346 /* The bitmap of indices in version_info whose value was changed. */
349 /* The uses of induction variables. */
350 vec
<iv_use_p
> iv_uses
;
352 /* The candidates. */
353 vec
<iv_cand_p
> iv_candidates
;
355 /* A bitmap of important candidates. */
356 bitmap important_candidates
;
358 /* Cache used by tree_to_aff_combination_expand. */
359 hash_map
<tree
, name_expansion
*> *name_expansion_cache
;
361 /* The maximum invariant id. */
364 /* Whether to consider just related and important candidates when replacing a
366 bool consider_all_candidates
;
368 /* Are we optimizing for speed? */
371 /* Whether the loop body includes any function calls. */
372 bool body_includes_call
;
374 /* Whether the loop body can only be exited via single exit. */
375 bool loop_single_exit_p
;
378 /* An assignment of iv candidates to uses. */
382 /* The number of uses covered by the assignment. */
385 /* Number of uses that cannot be expressed by the candidates in the set. */
388 /* Candidate assigned to a use, together with the related costs. */
389 struct cost_pair
**cand_for_use
;
391 /* Number of times each candidate is used. */
392 unsigned *n_cand_uses
;
394 /* The candidates used. */
397 /* The number of candidates in the set. */
400 /* Total number of registers needed. */
403 /* Total cost of expressing uses. */
404 comp_cost cand_use_cost
;
406 /* Total cost of candidates. */
409 /* Number of times each invariant is used. */
410 unsigned *n_invariant_uses
;
412 /* The array holding the number of uses of each loop
413 invariant expressions created by ivopt. */
414 unsigned *used_inv_expr
;
416 /* The number of created loop invariants. */
417 unsigned num_used_inv_expr
;
419 /* Total cost of the assignment. */
423 /* Difference of two iv candidate assignments. */
430 /* An old assignment (for rollback purposes). */
431 struct cost_pair
*old_cp
;
433 /* A new assignment. */
434 struct cost_pair
*new_cp
;
436 /* Next change in the list. */
437 struct iv_ca_delta
*next_change
;
440 /* Bound on number of candidates below that all candidates are considered. */
442 #define CONSIDER_ALL_CANDIDATES_BOUND \
443 ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
445 /* If there are more iv occurrences, we just give up (it is quite unlikely that
446 optimizing such a loop would help, and it would take ages). */
448 #define MAX_CONSIDERED_USES \
449 ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
451 /* If there are at most this number of ivs in the set, try removing unnecessary
452 ivs from the set always. */
454 #define ALWAYS_PRUNE_CAND_SET_BOUND \
455 ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
457 /* The list of trees for that the decl_rtl field must be reset is stored
460 static vec
<tree
> decl_rtl_to_reset
;
462 static comp_cost
force_expr_to_var_cost (tree
, bool);
464 /* Number of uses recorded in DATA. */
466 static inline unsigned
467 n_iv_uses (struct ivopts_data
*data
)
469 return data
->iv_uses
.length ();
472 /* Ith use recorded in DATA. */
474 static inline struct iv_use
*
475 iv_use (struct ivopts_data
*data
, unsigned i
)
477 return data
->iv_uses
[i
];
480 /* Number of candidates recorded in DATA. */
482 static inline unsigned
483 n_iv_cands (struct ivopts_data
*data
)
485 return data
->iv_candidates
.length ();
488 /* Ith candidate recorded in DATA. */
490 static inline struct iv_cand
*
491 iv_cand (struct ivopts_data
*data
, unsigned i
)
493 return data
->iv_candidates
[i
];
496 /* The single loop exit if it dominates the latch, NULL otherwise. */
499 single_dom_exit (struct loop
*loop
)
501 edge exit
= single_exit (loop
);
506 if (!just_once_each_iteration_p (loop
, exit
->src
))
512 /* Dumps information about the induction variable IV to FILE. */
515 dump_iv (FILE *file
, struct iv
*iv
, bool dump_name
)
517 if (iv
->ssa_name
&& dump_name
)
519 fprintf (file
, "ssa name ");
520 print_generic_expr (file
, iv
->ssa_name
, TDF_SLIM
);
521 fprintf (file
, "\n");
524 fprintf (file
, " type ");
525 print_generic_expr (file
, TREE_TYPE (iv
->base
), TDF_SLIM
);
526 fprintf (file
, "\n");
530 fprintf (file
, " base ");
531 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
532 fprintf (file
, "\n");
534 fprintf (file
, " step ");
535 print_generic_expr (file
, iv
->step
, TDF_SLIM
);
536 fprintf (file
, "\n");
540 fprintf (file
, " invariant ");
541 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
542 fprintf (file
, "\n");
547 fprintf (file
, " base object ");
548 print_generic_expr (file
, iv
->base_object
, TDF_SLIM
);
549 fprintf (file
, "\n");
553 fprintf (file
, " is a biv\n");
556 /* Dumps information about the USE to FILE. */
559 dump_use (FILE *file
, struct iv_use
*use
)
561 fprintf (file
, "use %d", use
->id
);
563 fprintf (file
, ".%d", use
->sub_id
);
565 fprintf (file
, "\n");
569 case USE_NONLINEAR_EXPR
:
570 fprintf (file
, " generic\n");
574 fprintf (file
, " address\n");
578 fprintf (file
, " compare\n");
585 fprintf (file
, " in statement ");
586 print_gimple_stmt (file
, use
->stmt
, 0, 0);
587 fprintf (file
, "\n");
589 fprintf (file
, " at position ");
591 print_generic_expr (file
, *use
->op_p
, TDF_SLIM
);
592 fprintf (file
, "\n");
594 dump_iv (file
, use
->iv
, false);
596 if (use
->related_cands
)
598 fprintf (file
, " related candidates ");
599 dump_bitmap (file
, use
->related_cands
);
603 /* Dumps information about the uses to FILE. */
606 dump_uses (FILE *file
, struct ivopts_data
*data
)
611 for (i
= 0; i
< n_iv_uses (data
); i
++)
613 use
= iv_use (data
, i
);
616 dump_use (file
, use
);
620 fprintf (file
, "\n");
624 /* Dumps information about induction variable candidate CAND to FILE. */
627 dump_cand (FILE *file
, struct iv_cand
*cand
)
629 struct iv
*iv
= cand
->iv
;
631 fprintf (file
, "candidate %d%s\n",
632 cand
->id
, cand
->important
? " (important)" : "");
634 if (cand
->depends_on
)
636 fprintf (file
, " depends on ");
637 dump_bitmap (file
, cand
->depends_on
);
642 fprintf (file
, " final value replacement\n");
646 if (cand
->var_before
)
648 fprintf (file
, " var_before ");
649 print_generic_expr (file
, cand
->var_before
, TDF_SLIM
);
650 fprintf (file
, "\n");
654 fprintf (file
, " var_after ");
655 print_generic_expr (file
, cand
->var_after
, TDF_SLIM
);
656 fprintf (file
, "\n");
662 fprintf (file
, " incremented before exit test\n");
666 fprintf (file
, " incremented before use %d\n", cand
->ainc_use
->id
);
670 fprintf (file
, " incremented after use %d\n", cand
->ainc_use
->id
);
674 fprintf (file
, " incremented at end\n");
678 fprintf (file
, " original biv\n");
682 dump_iv (file
, iv
, false);
685 /* Returns the info for ssa version VER. */
687 static inline struct version_info
*
688 ver_info (struct ivopts_data
*data
, unsigned ver
)
690 return data
->version_info
+ ver
;
693 /* Returns the info for ssa name NAME. */
695 static inline struct version_info
*
696 name_info (struct ivopts_data
*data
, tree name
)
698 return ver_info (data
, SSA_NAME_VERSION (name
));
701 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
705 stmt_after_ip_normal_pos (struct loop
*loop
, gimple stmt
)
707 basic_block bb
= ip_normal_pos (loop
), sbb
= gimple_bb (stmt
);
711 if (sbb
== loop
->latch
)
717 return stmt
== last_stmt (bb
);
720 /* Returns true if STMT if after the place where the original induction
721 variable CAND is incremented. If TRUE_IF_EQUAL is set, we return true
722 if the positions are identical. */
725 stmt_after_inc_pos (struct iv_cand
*cand
, gimple stmt
, bool true_if_equal
)
727 basic_block cand_bb
= gimple_bb (cand
->incremented_at
);
728 basic_block stmt_bb
= gimple_bb (stmt
);
730 if (!dominated_by_p (CDI_DOMINATORS
, stmt_bb
, cand_bb
))
733 if (stmt_bb
!= cand_bb
)
737 && gimple_uid (stmt
) == gimple_uid (cand
->incremented_at
))
739 return gimple_uid (stmt
) > gimple_uid (cand
->incremented_at
);
742 /* Returns true if STMT if after the place where the induction variable
743 CAND is incremented in LOOP. */
746 stmt_after_increment (struct loop
*loop
, struct iv_cand
*cand
, gimple stmt
)
754 return stmt_after_ip_normal_pos (loop
, stmt
);
758 return stmt_after_inc_pos (cand
, stmt
, false);
761 return stmt_after_inc_pos (cand
, stmt
, true);
768 /* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
771 abnormal_ssa_name_p (tree exp
)
776 if (TREE_CODE (exp
) != SSA_NAME
)
779 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
) != 0;
782 /* Returns false if BASE or INDEX contains a ssa name that occurs in an
783 abnormal phi node. Callback for for_each_index. */
786 idx_contains_abnormal_ssa_name_p (tree base
, tree
*index
,
787 void *data ATTRIBUTE_UNUSED
)
789 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
791 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 2)))
793 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 3)))
797 return !abnormal_ssa_name_p (*index
);
800 /* Returns true if EXPR contains a ssa name that occurs in an
801 abnormal phi node. */
804 contains_abnormal_ssa_name_p (tree expr
)
807 enum tree_code_class codeclass
;
812 code
= TREE_CODE (expr
);
813 codeclass
= TREE_CODE_CLASS (code
);
815 if (code
== SSA_NAME
)
816 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr
) != 0;
818 if (code
== INTEGER_CST
819 || is_gimple_min_invariant (expr
))
822 if (code
== ADDR_EXPR
)
823 return !for_each_index (&TREE_OPERAND (expr
, 0),
824 idx_contains_abnormal_ssa_name_p
,
827 if (code
== COND_EXPR
)
828 return contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0))
829 || contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1))
830 || contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 2));
836 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1)))
841 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0)))
853 /* Returns the structure describing number of iterations determined from
854 EXIT of DATA->current_loop, or NULL if something goes wrong. */
856 static struct tree_niter_desc
*
857 niter_for_exit (struct ivopts_data
*data
, edge exit
)
859 struct tree_niter_desc
*desc
;
860 tree_niter_desc
**slot
;
864 data
->niters
= new hash_map
<edge
, tree_niter_desc
*>;
868 slot
= data
->niters
->get (exit
);
872 /* Try to determine number of iterations. We cannot safely work with ssa
873 names that appear in phi nodes on abnormal edges, so that we do not
874 create overlapping life ranges for them (PR 27283). */
875 desc
= XNEW (struct tree_niter_desc
);
876 if (!number_of_iterations_exit (data
->current_loop
,
878 || contains_abnormal_ssa_name_p (desc
->niter
))
883 data
->niters
->put (exit
, desc
);
891 /* Returns the structure describing number of iterations determined from
892 single dominating exit of DATA->current_loop, or NULL if something
895 static struct tree_niter_desc
*
896 niter_for_single_dom_exit (struct ivopts_data
*data
)
898 edge exit
= single_dom_exit (data
->current_loop
);
903 return niter_for_exit (data
, exit
);
906 /* Initializes data structures used by the iv optimization pass, stored
910 tree_ssa_iv_optimize_init (struct ivopts_data
*data
)
912 data
->version_info_size
= 2 * num_ssa_names
;
913 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
914 data
->relevant
= BITMAP_ALLOC (NULL
);
915 data
->important_candidates
= BITMAP_ALLOC (NULL
);
916 data
->max_inv_id
= 0;
918 data
->iv_uses
.create (20);
919 data
->iv_candidates
.create (20);
920 data
->inv_expr_tab
= new hash_table
<iv_inv_expr_hasher
> (10);
921 data
->inv_expr_id
= 0;
922 data
->name_expansion_cache
= NULL
;
923 decl_rtl_to_reset
.create (20);
926 /* Returns a memory object to that EXPR points. In case we are able to
927 determine that it does not point to any such object, NULL is returned. */
930 determine_base_object (tree expr
)
932 enum tree_code code
= TREE_CODE (expr
);
935 /* If this is a pointer casted to any type, we need to determine
936 the base object for the pointer; so handle conversions before
937 throwing away non-pointer expressions. */
938 if (CONVERT_EXPR_P (expr
))
939 return determine_base_object (TREE_OPERAND (expr
, 0));
941 if (!POINTER_TYPE_P (TREE_TYPE (expr
)))
950 obj
= TREE_OPERAND (expr
, 0);
951 base
= get_base_address (obj
);
956 if (TREE_CODE (base
) == MEM_REF
)
957 return determine_base_object (TREE_OPERAND (base
, 0));
959 return fold_convert (ptr_type_node
,
960 build_fold_addr_expr (base
));
962 case POINTER_PLUS_EXPR
:
963 return determine_base_object (TREE_OPERAND (expr
, 0));
967 /* Pointer addition is done solely using POINTER_PLUS_EXPR. */
971 return fold_convert (ptr_type_node
, expr
);
975 /* Return true if address expression with non-DECL_P operand appears
979 contain_complex_addr_expr (tree expr
)
984 switch (TREE_CODE (expr
))
986 case POINTER_PLUS_EXPR
:
989 res
|= contain_complex_addr_expr (TREE_OPERAND (expr
, 0));
990 res
|= contain_complex_addr_expr (TREE_OPERAND (expr
, 1));
994 return (!DECL_P (TREE_OPERAND (expr
, 0)));
1003 /* Allocates an induction variable with given initial value BASE and step STEP
1004 for loop LOOP. NO_OVERFLOW implies the iv doesn't overflow. */
1007 alloc_iv (tree base
, tree step
, bool no_overflow
= false)
1010 struct iv
*iv
= XCNEW (struct iv
);
1011 gcc_assert (step
!= NULL_TREE
);
1013 /* Lower address expression in base except ones with DECL_P as operand.
1015 1) More accurate cost can be computed for address expressions;
1016 2) Duplicate candidates won't be created for bases in different
1017 forms, like &a[0] and &a. */
1019 if ((TREE_CODE (expr
) == ADDR_EXPR
&& !DECL_P (TREE_OPERAND (expr
, 0)))
1020 || contain_complex_addr_expr (expr
))
1023 tree_to_aff_combination (expr
, TREE_TYPE (base
), &comb
);
1024 base
= fold_convert (TREE_TYPE (base
), aff_combination_to_tree (&comb
));
1028 iv
->base_object
= determine_base_object (base
);
1031 iv
->have_use_for
= false;
1033 iv
->ssa_name
= NULL_TREE
;
1034 iv
->no_overflow
= no_overflow
;
1039 /* Sets STEP and BASE for induction variable IV. NO_OVERFLOW implies the IV
1040 doesn't overflow. */
1043 set_iv (struct ivopts_data
*data
, tree iv
, tree base
, tree step
,
1046 struct version_info
*info
= name_info (data
, iv
);
1048 gcc_assert (!info
->iv
);
1050 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (iv
));
1051 info
->iv
= alloc_iv (base
, step
, no_overflow
);
1052 info
->iv
->ssa_name
= iv
;
1055 /* Finds induction variable declaration for VAR. */
1058 get_iv (struct ivopts_data
*data
, tree var
)
1061 tree type
= TREE_TYPE (var
);
1063 if (!POINTER_TYPE_P (type
)
1064 && !INTEGRAL_TYPE_P (type
))
1067 if (!name_info (data
, var
)->iv
)
1069 bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
1072 || !flow_bb_inside_loop_p (data
->current_loop
, bb
))
1073 set_iv (data
, var
, var
, build_int_cst (type
, 0), true);
1076 return name_info (data
, var
)->iv
;
1079 /* Return the first non-invariant ssa var found in EXPR. */
1082 extract_single_var_from_expr (tree expr
)
1086 enum tree_code code
;
1088 if (!expr
|| is_gimple_min_invariant (expr
))
1091 code
= TREE_CODE (expr
);
1092 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1094 n
= TREE_OPERAND_LENGTH (expr
);
1095 for (i
= 0; i
< n
; i
++)
1097 tmp
= extract_single_var_from_expr (TREE_OPERAND (expr
, i
));
1103 return (TREE_CODE (expr
) == SSA_NAME
) ? expr
: NULL
;
1106 /* Finds basic ivs. */
1109 find_bivs (struct ivopts_data
*data
)
1113 tree step
, type
, base
, stop
;
1115 struct loop
*loop
= data
->current_loop
;
1118 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1122 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
1125 if (virtual_operand_p (PHI_RESULT (phi
)))
1128 if (!simple_iv (loop
, loop
, PHI_RESULT (phi
), &iv
, true))
1131 if (integer_zerop (iv
.step
))
1135 base
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1136 /* Stop expanding iv base at the first ssa var referred by iv step.
1137 Ideally we should stop at any ssa var, because that's expensive
1138 and unusual to happen, we just do it on the first one.
1140 See PR64705 for the rationale. */
1141 stop
= extract_single_var_from_expr (step
);
1142 base
= expand_simple_operations (base
, stop
);
1143 if (contains_abnormal_ssa_name_p (base
)
1144 || contains_abnormal_ssa_name_p (step
))
1147 type
= TREE_TYPE (PHI_RESULT (phi
));
1148 base
= fold_convert (type
, base
);
1151 if (POINTER_TYPE_P (type
))
1152 step
= convert_to_ptrofftype (step
);
1154 step
= fold_convert (type
, step
);
1157 set_iv (data
, PHI_RESULT (phi
), base
, step
, iv
.no_overflow
);
1164 /* Marks basic ivs. */
1167 mark_bivs (struct ivopts_data
*data
)
1172 struct iv
*iv
, *incr_iv
;
1173 struct loop
*loop
= data
->current_loop
;
1174 basic_block incr_bb
;
1177 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1181 iv
= get_iv (data
, PHI_RESULT (phi
));
1185 var
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
1186 def
= SSA_NAME_DEF_STMT (var
);
1187 /* Don't mark iv peeled from other one as biv. */
1189 && gimple_code (def
) == GIMPLE_PHI
1190 && gimple_bb (def
) == loop
->header
)
1193 incr_iv
= get_iv (data
, var
);
1197 /* If the increment is in the subloop, ignore it. */
1198 incr_bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
1199 if (incr_bb
->loop_father
!= data
->current_loop
1200 || (incr_bb
->flags
& BB_IRREDUCIBLE_LOOP
))
1204 incr_iv
->biv_p
= true;
1208 /* Checks whether STMT defines a linear induction variable and stores its
1209 parameters to IV. */
1212 find_givs_in_stmt_scev (struct ivopts_data
*data
, gimple stmt
, affine_iv
*iv
)
1215 struct loop
*loop
= data
->current_loop
;
1217 iv
->base
= NULL_TREE
;
1218 iv
->step
= NULL_TREE
;
1220 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1223 lhs
= gimple_assign_lhs (stmt
);
1224 if (TREE_CODE (lhs
) != SSA_NAME
)
1227 if (!simple_iv (loop
, loop_containing_stmt (stmt
), lhs
, iv
, true))
1230 /* Stop expanding iv base at the first ssa var referred by iv step.
1231 Ideally we should stop at any ssa var, because that's expensive
1232 and unusual to happen, we just do it on the first one.
1234 See PR64705 for the rationale. */
1235 stop
= extract_single_var_from_expr (iv
->step
);
1236 iv
->base
= expand_simple_operations (iv
->base
, stop
);
1237 if (contains_abnormal_ssa_name_p (iv
->base
)
1238 || contains_abnormal_ssa_name_p (iv
->step
))
1241 /* If STMT could throw, then do not consider STMT as defining a GIV.
1242 While this will suppress optimizations, we can not safely delete this
1243 GIV and associated statements, even if it appears it is not used. */
1244 if (stmt_could_throw_p (stmt
))
1250 /* Finds general ivs in statement STMT. */
1253 find_givs_in_stmt (struct ivopts_data
*data
, gimple stmt
)
1257 if (!find_givs_in_stmt_scev (data
, stmt
, &iv
))
1260 set_iv (data
, gimple_assign_lhs (stmt
), iv
.base
, iv
.step
, iv
.no_overflow
);
1263 /* Finds general ivs in basic block BB. */
1266 find_givs_in_bb (struct ivopts_data
*data
, basic_block bb
)
1268 gimple_stmt_iterator bsi
;
1270 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1271 find_givs_in_stmt (data
, gsi_stmt (bsi
));
1274 /* Finds general ivs. */
1277 find_givs (struct ivopts_data
*data
)
1279 struct loop
*loop
= data
->current_loop
;
1280 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1283 for (i
= 0; i
< loop
->num_nodes
; i
++)
1284 find_givs_in_bb (data
, body
[i
]);
1288 /* For each ssa name defined in LOOP determines whether it is an induction
1289 variable and if so, its initial value and step. */
1292 find_induction_variables (struct ivopts_data
*data
)
1297 if (!find_bivs (data
))
1303 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1305 struct tree_niter_desc
*niter
= niter_for_single_dom_exit (data
);
1309 fprintf (dump_file
, " number of iterations ");
1310 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1311 if (!integer_zerop (niter
->may_be_zero
))
1313 fprintf (dump_file
, "; zero if ");
1314 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1316 fprintf (dump_file
, "\n\n");
1319 fprintf (dump_file
, "Induction variables:\n\n");
1321 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1323 if (ver_info (data
, i
)->iv
)
1324 dump_iv (dump_file
, ver_info (data
, i
)->iv
, true);
1331 /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV.
1332 For address type use, ADDR_BASE is the stripped IV base, ADDR_OFFSET
1333 is the const offset stripped from IV base. For uses of other types,
1334 ADDR_BASE and ADDR_OFFSET are zero by default. */
1336 static struct iv_use
*
1337 record_use (struct ivopts_data
*data
, tree
*use_p
, struct iv
*iv
,
1338 gimple stmt
, enum use_type use_type
, tree addr_base
= NULL
,
1339 unsigned HOST_WIDE_INT addr_offset
= 0)
1341 struct iv_use
*use
= XCNEW (struct iv_use
);
1343 use
->id
= n_iv_uses (data
);
1345 use
->type
= use_type
;
1349 use
->related_cands
= BITMAP_ALLOC (NULL
);
1351 use
->addr_base
= addr_base
;
1352 use
->addr_offset
= addr_offset
;
1354 data
->iv_uses
.safe_push (use
);
1359 /* Records a sub use of type USE_TYPE at *USE_P in STMT whose value is IV.
1360 The sub use is recorded under the one whose use id is ID_GROUP. */
1362 static struct iv_use
*
1363 record_sub_use (struct ivopts_data
*data
, tree
*use_p
,
1364 struct iv
*iv
, gimple stmt
, enum use_type use_type
,
1365 tree addr_base
, unsigned HOST_WIDE_INT addr_offset
,
1366 unsigned int id_group
)
1368 struct iv_use
*use
= XCNEW (struct iv_use
);
1369 struct iv_use
*group
= iv_use (data
, id_group
);
1371 use
->id
= group
->id
;
1373 use
->type
= use_type
;
1377 use
->related_cands
= NULL
;
1378 use
->addr_base
= addr_base
;
1379 use
->addr_offset
= addr_offset
;
1381 /* Sub use list is maintained in offset ascending order. */
1382 if (addr_offset
<= group
->addr_offset
)
1384 use
->related_cands
= group
->related_cands
;
1385 group
->related_cands
= NULL
;
1387 data
->iv_uses
[id_group
] = use
;
1395 group
= group
->next
;
1397 while (group
&& addr_offset
> group
->addr_offset
);
1398 use
->next
= pre
->next
;
1402 /* To avoid showing ssa name in the dumps, if it was not reset by the
1404 iv
->ssa_name
= NULL_TREE
;
1409 /* Checks whether OP is a loop-level invariant and if so, records it.
1410 NONLINEAR_USE is true if the invariant is used in a way we do not
1411 handle specially. */
1414 record_invariant (struct ivopts_data
*data
, tree op
, bool nonlinear_use
)
1417 struct version_info
*info
;
1419 if (TREE_CODE (op
) != SSA_NAME
1420 || virtual_operand_p (op
))
1423 bb
= gimple_bb (SSA_NAME_DEF_STMT (op
));
1425 && flow_bb_inside_loop_p (data
->current_loop
, bb
))
1428 info
= name_info (data
, op
);
1430 info
->has_nonlin_use
|= nonlinear_use
;
1432 info
->inv_id
= ++data
->max_inv_id
;
1433 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (op
));
1436 /* Checks whether the use OP is interesting and if so, records it. */
1438 static struct iv_use
*
1439 find_interesting_uses_op (struct ivopts_data
*data
, tree op
)
1446 if (TREE_CODE (op
) != SSA_NAME
)
1449 iv
= get_iv (data
, op
);
1453 if (iv
->have_use_for
)
1455 use
= iv_use (data
, iv
->use_id
);
1457 gcc_assert (use
->type
== USE_NONLINEAR_EXPR
);
1461 if (integer_zerop (iv
->step
))
1463 record_invariant (data
, op
, true);
1466 iv
->have_use_for
= true;
1468 civ
= XNEW (struct iv
);
1471 stmt
= SSA_NAME_DEF_STMT (op
);
1472 gcc_assert (gimple_code (stmt
) == GIMPLE_PHI
1473 || is_gimple_assign (stmt
));
1475 use
= record_use (data
, NULL
, civ
, stmt
, USE_NONLINEAR_EXPR
);
1476 iv
->use_id
= use
->id
;
1481 /* Given a condition in statement STMT, checks whether it is a compare
1482 of an induction variable and an invariant. If this is the case,
1483 CONTROL_VAR is set to location of the iv, BOUND to the location of
1484 the invariant, IV_VAR and IV_BOUND are set to the corresponding
1485 induction variable descriptions, and true is returned. If this is not
1486 the case, CONTROL_VAR and BOUND are set to the arguments of the
1487 condition and false is returned. */
1490 extract_cond_operands (struct ivopts_data
*data
, gimple stmt
,
1491 tree
**control_var
, tree
**bound
,
1492 struct iv
**iv_var
, struct iv
**iv_bound
)
1494 /* The objects returned when COND has constant operands. */
1495 static struct iv const_iv
;
1497 tree
*op0
= &zero
, *op1
= &zero
, *tmp_op
;
1498 struct iv
*iv0
= &const_iv
, *iv1
= &const_iv
, *tmp_iv
;
1501 if (gimple_code (stmt
) == GIMPLE_COND
)
1503 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
1504 op0
= gimple_cond_lhs_ptr (cond_stmt
);
1505 op1
= gimple_cond_rhs_ptr (cond_stmt
);
1509 op0
= gimple_assign_rhs1_ptr (stmt
);
1510 op1
= gimple_assign_rhs2_ptr (stmt
);
1513 zero
= integer_zero_node
;
1514 const_iv
.step
= integer_zero_node
;
1516 if (TREE_CODE (*op0
) == SSA_NAME
)
1517 iv0
= get_iv (data
, *op0
);
1518 if (TREE_CODE (*op1
) == SSA_NAME
)
1519 iv1
= get_iv (data
, *op1
);
1521 /* Exactly one of the compared values must be an iv, and the other one must
1526 if (integer_zerop (iv0
->step
))
1528 /* Control variable may be on the other side. */
1529 tmp_op
= op0
; op0
= op1
; op1
= tmp_op
;
1530 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
1532 ret
= !integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
);
1547 /* Checks whether the condition in STMT is interesting and if so,
1551 find_interesting_uses_cond (struct ivopts_data
*data
, gimple stmt
)
1553 tree
*var_p
, *bound_p
;
1554 struct iv
*var_iv
, *civ
;
1556 if (!extract_cond_operands (data
, stmt
, &var_p
, &bound_p
, &var_iv
, NULL
))
1558 find_interesting_uses_op (data
, *var_p
);
1559 find_interesting_uses_op (data
, *bound_p
);
1563 civ
= XNEW (struct iv
);
1565 record_use (data
, NULL
, civ
, stmt
, USE_COMPARE
);
1568 /* Returns the outermost loop EXPR is obviously invariant in
1569 relative to the loop LOOP, i.e. if all its operands are defined
1570 outside of the returned loop. Returns NULL if EXPR is not
1571 even obviously invariant in LOOP. */
1574 outermost_invariant_loop_for_expr (struct loop
*loop
, tree expr
)
1579 if (is_gimple_min_invariant (expr
))
1580 return current_loops
->tree_root
;
1582 if (TREE_CODE (expr
) == SSA_NAME
)
1584 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
1587 if (flow_bb_inside_loop_p (loop
, def_bb
))
1589 return superloop_at_depth (loop
,
1590 loop_depth (def_bb
->loop_father
) + 1);
1593 return current_loops
->tree_root
;
1599 unsigned maxdepth
= 0;
1600 len
= TREE_OPERAND_LENGTH (expr
);
1601 for (i
= 0; i
< len
; i
++)
1603 struct loop
*ivloop
;
1604 if (!TREE_OPERAND (expr
, i
))
1607 ivloop
= outermost_invariant_loop_for_expr (loop
, TREE_OPERAND (expr
, i
));
1610 maxdepth
= MAX (maxdepth
, loop_depth (ivloop
));
1613 return superloop_at_depth (loop
, maxdepth
);
1616 /* Returns true if expression EXPR is obviously invariant in LOOP,
1617 i.e. if all its operands are defined outside of the LOOP. LOOP
1618 should not be the function body. */
1621 expr_invariant_in_loop_p (struct loop
*loop
, tree expr
)
1626 gcc_assert (loop_depth (loop
) > 0);
1628 if (is_gimple_min_invariant (expr
))
1631 if (TREE_CODE (expr
) == SSA_NAME
)
1633 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
1635 && flow_bb_inside_loop_p (loop
, def_bb
))
1644 len
= TREE_OPERAND_LENGTH (expr
);
1645 for (i
= 0; i
< len
; i
++)
1646 if (TREE_OPERAND (expr
, i
)
1647 && !expr_invariant_in_loop_p (loop
, TREE_OPERAND (expr
, i
)))
1653 /* Cumulates the steps of indices into DATA and replaces their values with the
1654 initial ones. Returns false when the value of the index cannot be determined.
1655 Callback for for_each_index. */
1657 struct ifs_ivopts_data
1659 struct ivopts_data
*ivopts_data
;
1665 idx_find_step (tree base
, tree
*idx
, void *data
)
1667 struct ifs_ivopts_data
*dta
= (struct ifs_ivopts_data
*) data
;
1669 bool use_overflow_semantics
= false;
1670 tree step
, iv_base
, iv_step
, lbound
, off
;
1671 struct loop
*loop
= dta
->ivopts_data
->current_loop
;
1673 /* If base is a component ref, require that the offset of the reference
1675 if (TREE_CODE (base
) == COMPONENT_REF
)
1677 off
= component_ref_field_offset (base
);
1678 return expr_invariant_in_loop_p (loop
, off
);
1681 /* If base is array, first check whether we will be able to move the
1682 reference out of the loop (in order to take its address in strength
1683 reduction). In order for this to work we need both lower bound
1684 and step to be loop invariants. */
1685 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
1687 /* Moreover, for a range, the size needs to be invariant as well. */
1688 if (TREE_CODE (base
) == ARRAY_RANGE_REF
1689 && !expr_invariant_in_loop_p (loop
, TYPE_SIZE (TREE_TYPE (base
))))
1692 step
= array_ref_element_size (base
);
1693 lbound
= array_ref_low_bound (base
);
1695 if (!expr_invariant_in_loop_p (loop
, step
)
1696 || !expr_invariant_in_loop_p (loop
, lbound
))
1700 if (TREE_CODE (*idx
) != SSA_NAME
)
1703 iv
= get_iv (dta
->ivopts_data
, *idx
);
1707 /* XXX We produce for a base of *D42 with iv->base being &x[0]
1708 *&x[0], which is not folded and does not trigger the
1709 ARRAY_REF path below. */
1712 if (integer_zerop (iv
->step
))
1715 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
1717 step
= array_ref_element_size (base
);
1719 /* We only handle addresses whose step is an integer constant. */
1720 if (TREE_CODE (step
) != INTEGER_CST
)
1724 /* The step for pointer arithmetics already is 1 byte. */
1725 step
= size_one_node
;
1729 if (iv
->no_overflow
&& nowrap_type_p (TREE_TYPE (iv_step
)))
1730 use_overflow_semantics
= true;
1732 if (!convert_affine_scev (dta
->ivopts_data
->current_loop
,
1733 sizetype
, &iv_base
, &iv_step
, dta
->stmt
,
1734 use_overflow_semantics
))
1736 /* The index might wrap. */
1740 step
= fold_build2 (MULT_EXPR
, sizetype
, step
, iv_step
);
1741 dta
->step
= fold_build2 (PLUS_EXPR
, sizetype
, dta
->step
, step
);
1746 /* Records use in index IDX. Callback for for_each_index. Ivopts data
1747 object is passed to it in DATA. */
1750 idx_record_use (tree base
, tree
*idx
,
1753 struct ivopts_data
*data
= (struct ivopts_data
*) vdata
;
1754 find_interesting_uses_op (data
, *idx
);
1755 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
1757 find_interesting_uses_op (data
, array_ref_element_size (base
));
1758 find_interesting_uses_op (data
, array_ref_low_bound (base
));
1763 /* If we can prove that TOP = cst * BOT for some constant cst,
1764 store cst to MUL and return true. Otherwise return false.
1765 The returned value is always sign-extended, regardless of the
1766 signedness of TOP and BOT. */
1769 constant_multiple_of (tree top
, tree bot
, widest_int
*mul
)
1772 enum tree_code code
;
1773 unsigned precision
= TYPE_PRECISION (TREE_TYPE (top
));
1774 widest_int res
, p0
, p1
;
1779 if (operand_equal_p (top
, bot
, 0))
1785 code
= TREE_CODE (top
);
1789 mby
= TREE_OPERAND (top
, 1);
1790 if (TREE_CODE (mby
) != INTEGER_CST
)
1793 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &res
))
1796 *mul
= wi::sext (res
* wi::to_widest (mby
), precision
);
1801 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &p0
)
1802 || !constant_multiple_of (TREE_OPERAND (top
, 1), bot
, &p1
))
1805 if (code
== MINUS_EXPR
)
1807 *mul
= wi::sext (p0
+ p1
, precision
);
1811 if (TREE_CODE (bot
) != INTEGER_CST
)
1814 p0
= widest_int::from (top
, SIGNED
);
1815 p1
= widest_int::from (bot
, SIGNED
);
1818 *mul
= wi::sext (wi::divmod_trunc (p0
, p1
, SIGNED
, &res
), precision
);
1826 /* Return true if memory reference REF with step STEP may be unaligned. */
1829 may_be_unaligned_p (tree ref
, tree step
)
1831 /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
1832 thus they are not misaligned. */
1833 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
1836 unsigned int align
= TYPE_ALIGN (TREE_TYPE (ref
));
1837 if (GET_MODE_ALIGNMENT (TYPE_MODE (TREE_TYPE (ref
))) > align
)
1838 align
= GET_MODE_ALIGNMENT (TYPE_MODE (TREE_TYPE (ref
)));
1840 unsigned HOST_WIDE_INT bitpos
;
1841 unsigned int ref_align
;
1842 get_object_alignment_1 (ref
, &ref_align
, &bitpos
);
1843 if (ref_align
< align
1844 || (bitpos
% align
) != 0
1845 || (bitpos
% BITS_PER_UNIT
) != 0)
1848 unsigned int trailing_zeros
= tree_ctz (step
);
1849 if (trailing_zeros
< HOST_BITS_PER_INT
1850 && (1U << trailing_zeros
) * BITS_PER_UNIT
< align
)
1856 /* Return true if EXPR may be non-addressable. */
1859 may_be_nonaddressable_p (tree expr
)
1861 switch (TREE_CODE (expr
))
1863 case TARGET_MEM_REF
:
1864 /* TARGET_MEM_REFs are translated directly to valid MEMs on the
1865 target, thus they are always addressable. */
1869 return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr
, 1))
1870 || may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1872 case VIEW_CONVERT_EXPR
:
1873 /* This kind of view-conversions may wrap non-addressable objects
1874 and make them look addressable. After some processing the
1875 non-addressability may be uncovered again, causing ADDR_EXPRs
1876 of inappropriate objects to be built. */
1877 if (is_gimple_reg (TREE_OPERAND (expr
, 0))
1878 || !is_gimple_addressable (TREE_OPERAND (expr
, 0)))
1881 /* ... fall through ... */
1884 case ARRAY_RANGE_REF
:
1885 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
1898 strip_offset (tree expr
, unsigned HOST_WIDE_INT
*offset
);
1900 /* Record a use of type USE_TYPE at *USE_P in STMT whose value is IV.
1901 If there is an existing use which has same stripped iv base and step,
1902 this function records this one as a sub use to that; otherwise records
1903 it as a normal one. */
1905 static struct iv_use
*
1906 record_group_use (struct ivopts_data
*data
, tree
*use_p
,
1907 struct iv
*iv
, gimple stmt
, enum use_type use_type
)
1912 unsigned HOST_WIDE_INT addr_offset
;
1914 /* Only support sub use for address type uses, that is, with base
1916 if (!iv
->base_object
)
1917 return record_use (data
, use_p
, iv
, stmt
, use_type
);
1919 addr_base
= strip_offset (iv
->base
, &addr_offset
);
1920 for (i
= 0; i
< n_iv_uses (data
); i
++)
1922 use
= iv_use (data
, i
);
1923 if (use
->type
!= USE_ADDRESS
|| !use
->iv
->base_object
)
1926 /* Check if it has the same stripped base and step. */
1927 if (operand_equal_p (iv
->base_object
, use
->iv
->base_object
, 0)
1928 && operand_equal_p (iv
->step
, use
->iv
->step
, 0)
1929 && operand_equal_p (addr_base
, use
->addr_base
, 0))
1933 if (i
== n_iv_uses (data
))
1934 return record_use (data
, use_p
, iv
, stmt
,
1935 use_type
, addr_base
, addr_offset
);
1937 return record_sub_use (data
, use_p
, iv
, stmt
,
1938 use_type
, addr_base
, addr_offset
, i
);
1941 /* Finds addresses in *OP_P inside STMT. */
1944 find_interesting_uses_address (struct ivopts_data
*data
, gimple stmt
, tree
*op_p
)
1946 tree base
= *op_p
, step
= size_zero_node
;
1948 struct ifs_ivopts_data ifs_ivopts_data
;
1950 /* Do not play with volatile memory references. A bit too conservative,
1951 perhaps, but safe. */
1952 if (gimple_has_volatile_ops (stmt
))
1955 /* Ignore bitfields for now. Not really something terribly complicated
1957 if (TREE_CODE (base
) == BIT_FIELD_REF
)
1960 base
= unshare_expr (base
);
1962 if (TREE_CODE (base
) == TARGET_MEM_REF
)
1964 tree type
= build_pointer_type (TREE_TYPE (base
));
1968 && TREE_CODE (TMR_BASE (base
)) == SSA_NAME
)
1970 civ
= get_iv (data
, TMR_BASE (base
));
1974 TMR_BASE (base
) = civ
->base
;
1977 if (TMR_INDEX2 (base
)
1978 && TREE_CODE (TMR_INDEX2 (base
)) == SSA_NAME
)
1980 civ
= get_iv (data
, TMR_INDEX2 (base
));
1984 TMR_INDEX2 (base
) = civ
->base
;
1987 if (TMR_INDEX (base
)
1988 && TREE_CODE (TMR_INDEX (base
)) == SSA_NAME
)
1990 civ
= get_iv (data
, TMR_INDEX (base
));
1994 TMR_INDEX (base
) = civ
->base
;
1999 if (TMR_STEP (base
))
2000 astep
= fold_build2 (MULT_EXPR
, type
, TMR_STEP (base
), astep
);
2002 step
= fold_build2 (PLUS_EXPR
, type
, step
, astep
);
2006 if (integer_zerop (step
))
2008 base
= tree_mem_ref_addr (type
, base
);
2012 ifs_ivopts_data
.ivopts_data
= data
;
2013 ifs_ivopts_data
.stmt
= stmt
;
2014 ifs_ivopts_data
.step
= size_zero_node
;
2015 if (!for_each_index (&base
, idx_find_step
, &ifs_ivopts_data
)
2016 || integer_zerop (ifs_ivopts_data
.step
))
2018 step
= ifs_ivopts_data
.step
;
2020 /* Check that the base expression is addressable. This needs
2021 to be done after substituting bases of IVs into it. */
2022 if (may_be_nonaddressable_p (base
))
2025 /* Moreover, on strict alignment platforms, check that it is
2026 sufficiently aligned. */
2027 if (STRICT_ALIGNMENT
&& may_be_unaligned_p (base
, step
))
2030 base
= build_fold_addr_expr (base
);
2032 /* Substituting bases of IVs into the base expression might
2033 have caused folding opportunities. */
2034 if (TREE_CODE (base
) == ADDR_EXPR
)
2036 tree
*ref
= &TREE_OPERAND (base
, 0);
2037 while (handled_component_p (*ref
))
2038 ref
= &TREE_OPERAND (*ref
, 0);
2039 if (TREE_CODE (*ref
) == MEM_REF
)
2041 tree tem
= fold_binary (MEM_REF
, TREE_TYPE (*ref
),
2042 TREE_OPERAND (*ref
, 0),
2043 TREE_OPERAND (*ref
, 1));
2050 civ
= alloc_iv (base
, step
);
2051 record_group_use (data
, op_p
, civ
, stmt
, USE_ADDRESS
);
2055 for_each_index (op_p
, idx_record_use
, data
);
2058 /* Finds and records invariants used in STMT. */
2061 find_invariants_stmt (struct ivopts_data
*data
, gimple stmt
)
2064 use_operand_p use_p
;
2067 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2069 op
= USE_FROM_PTR (use_p
);
2070 record_invariant (data
, op
, false);
2074 /* Finds interesting uses of induction variables in the statement STMT. */
2077 find_interesting_uses_stmt (struct ivopts_data
*data
, gimple stmt
)
2080 tree op
, *lhs
, *rhs
;
2082 use_operand_p use_p
;
2083 enum tree_code code
;
2085 find_invariants_stmt (data
, stmt
);
2087 if (gimple_code (stmt
) == GIMPLE_COND
)
2089 find_interesting_uses_cond (data
, stmt
);
2093 if (is_gimple_assign (stmt
))
2095 lhs
= gimple_assign_lhs_ptr (stmt
);
2096 rhs
= gimple_assign_rhs1_ptr (stmt
);
2098 if (TREE_CODE (*lhs
) == SSA_NAME
)
2100 /* If the statement defines an induction variable, the uses are not
2101 interesting by themselves. */
2103 iv
= get_iv (data
, *lhs
);
2105 if (iv
&& !integer_zerop (iv
->step
))
2109 code
= gimple_assign_rhs_code (stmt
);
2110 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
2111 && (REFERENCE_CLASS_P (*rhs
)
2112 || is_gimple_val (*rhs
)))
2114 if (REFERENCE_CLASS_P (*rhs
))
2115 find_interesting_uses_address (data
, stmt
, rhs
);
2117 find_interesting_uses_op (data
, *rhs
);
2119 if (REFERENCE_CLASS_P (*lhs
))
2120 find_interesting_uses_address (data
, stmt
, lhs
);
2123 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
2125 find_interesting_uses_cond (data
, stmt
);
2129 /* TODO -- we should also handle address uses of type
2131 memory = call (whatever);
2138 if (gimple_code (stmt
) == GIMPLE_PHI
2139 && gimple_bb (stmt
) == data
->current_loop
->header
)
2141 iv
= get_iv (data
, PHI_RESULT (stmt
));
2143 if (iv
&& !integer_zerop (iv
->step
))
2147 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2149 op
= USE_FROM_PTR (use_p
);
2151 if (TREE_CODE (op
) != SSA_NAME
)
2154 iv
= get_iv (data
, op
);
2158 find_interesting_uses_op (data
, op
);
2162 /* Finds interesting uses of induction variables outside of loops
2163 on loop exit edge EXIT. */
2166 find_interesting_uses_outside (struct ivopts_data
*data
, edge exit
)
2172 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2175 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
2176 if (!virtual_operand_p (def
))
2177 find_interesting_uses_op (data
, def
);
2181 /* Finds uses of the induction variables that are interesting. */
2184 find_interesting_uses (struct ivopts_data
*data
)
2187 gimple_stmt_iterator bsi
;
2188 basic_block
*body
= get_loop_body (data
->current_loop
);
2190 struct version_info
*info
;
2193 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2194 fprintf (dump_file
, "Uses:\n\n");
2196 for (i
= 0; i
< data
->current_loop
->num_nodes
; i
++)
2201 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2202 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2203 && !flow_bb_inside_loop_p (data
->current_loop
, e
->dest
))
2204 find_interesting_uses_outside (data
, e
);
2206 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2207 find_interesting_uses_stmt (data
, gsi_stmt (bsi
));
2208 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2209 if (!is_gimple_debug (gsi_stmt (bsi
)))
2210 find_interesting_uses_stmt (data
, gsi_stmt (bsi
));
2213 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2217 fprintf (dump_file
, "\n");
2219 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
2221 info
= ver_info (data
, i
);
2224 fprintf (dump_file
, " ");
2225 print_generic_expr (dump_file
, info
->name
, TDF_SLIM
);
2226 fprintf (dump_file
, " is invariant (%d)%s\n",
2227 info
->inv_id
, info
->has_nonlin_use
? "" : ", eliminable");
2231 fprintf (dump_file
, "\n");
2237 /* Compute maximum offset of [base + offset] addressing mode
2238 for memory reference represented by USE. */
2240 static HOST_WIDE_INT
2241 compute_max_addr_offset (struct iv_use
*use
)
2245 HOST_WIDE_INT i
, off
;
2246 unsigned list_index
, num
;
2248 machine_mode mem_mode
, addr_mode
;
2249 static vec
<HOST_WIDE_INT
> max_offset_list
;
2251 as
= TYPE_ADDR_SPACE (TREE_TYPE (use
->iv
->base
));
2252 mem_mode
= TYPE_MODE (TREE_TYPE (*use
->op_p
));
2254 num
= max_offset_list
.length ();
2255 list_index
= (unsigned) as
* MAX_MACHINE_MODE
+ (unsigned) mem_mode
;
2256 if (list_index
>= num
)
2258 max_offset_list
.safe_grow (list_index
+ MAX_MACHINE_MODE
);
2259 for (; num
< max_offset_list
.length (); num
++)
2260 max_offset_list
[num
] = -1;
2263 off
= max_offset_list
[list_index
];
2267 addr_mode
= targetm
.addr_space
.address_mode (as
);
2268 reg
= gen_raw_REG (addr_mode
, LAST_VIRTUAL_REGISTER
+ 1);
2269 addr
= gen_rtx_fmt_ee (PLUS
, addr_mode
, reg
, NULL_RTX
);
2271 width
= GET_MODE_BITSIZE (addr_mode
) - 1;
2272 if (width
> (HOST_BITS_PER_WIDE_INT
- 1))
2273 width
= HOST_BITS_PER_WIDE_INT
- 1;
2275 for (i
= width
; i
> 0; i
--)
2277 off
= ((unsigned HOST_WIDE_INT
) 1 << i
) - 1;
2278 XEXP (addr
, 1) = gen_int_mode (off
, addr_mode
);
2279 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
2282 /* For some strict-alignment targets, the offset must be naturally
2283 aligned. Try an aligned offset if mem_mode is not QImode. */
2284 off
= ((unsigned HOST_WIDE_INT
) 1 << i
);
2285 if (off
> GET_MODE_SIZE (mem_mode
) && mem_mode
!= QImode
)
2287 off
-= GET_MODE_SIZE (mem_mode
);
2288 XEXP (addr
, 1) = gen_int_mode (off
, addr_mode
);
2289 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
2296 max_offset_list
[list_index
] = off
;
2300 /* Check if all small groups should be split. Return true if and
2303 1) At least one groups contain two uses with different offsets.
2304 2) No group contains more than two uses with different offsets.
2306 Return false otherwise. We want to split such groups because:
2308 1) Small groups don't have much benefit and may interfer with
2309 general candidate selection.
2310 2) Size for problem with only small groups is usually small and
2311 general algorithm can handle it well.
2313 TODO -- Above claim may not hold when auto increment is supported. */
2316 split_all_small_groups (struct ivopts_data
*data
)
2318 bool split_p
= false;
2319 unsigned int i
, n
, distinct
;
2320 struct iv_use
*pre
, *use
;
2322 n
= n_iv_uses (data
);
2323 for (i
= 0; i
< n
; i
++)
2325 use
= iv_use (data
, i
);
2330 gcc_assert (use
->type
== USE_ADDRESS
);
2331 for (pre
= use
, use
= use
->next
; use
; pre
= use
, use
= use
->next
)
2333 if (pre
->addr_offset
!= use
->addr_offset
)
2346 /* For each group of address type uses, this function further groups
2347 these uses according to the maximum offset supported by target's
2348 [base + offset] addressing mode. */
2351 group_address_uses (struct ivopts_data
*data
)
2353 HOST_WIDE_INT max_offset
= -1;
2354 unsigned int i
, n
, sub_id
;
2355 struct iv_use
*pre
, *use
;
2356 unsigned HOST_WIDE_INT addr_offset_first
;
2358 /* Reset max offset to split all small groups. */
2359 if (split_all_small_groups (data
))
2362 n
= n_iv_uses (data
);
2363 for (i
= 0; i
< n
; i
++)
2365 use
= iv_use (data
, i
);
2369 gcc_assert (use
->type
== USE_ADDRESS
);
2370 if (max_offset
!= 0)
2371 max_offset
= compute_max_addr_offset (use
);
2376 addr_offset_first
= use
->addr_offset
;
2377 /* Only uses with offset that can fit in offset part against
2378 the first use can be grouped together. */
2379 for (pre
= use
, use
= use
->next
;
2380 use
&& (use
->addr_offset
- addr_offset_first
2381 <= (unsigned HOST_WIDE_INT
) max_offset
);
2382 pre
= use
, use
= use
->next
)
2385 use
->sub_id
= ++sub_id
;
2388 /* Break the list and create new group. */
2392 use
->id
= n_iv_uses (data
);
2393 use
->related_cands
= BITMAP_ALLOC (NULL
);
2394 data
->iv_uses
.safe_push (use
);
2399 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2400 dump_uses (dump_file
, data
);
2403 /* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
2404 is true, assume we are inside an address. If TOP_COMPREF is true, assume
2405 we are at the top-level of the processed address. */
2408 strip_offset_1 (tree expr
, bool inside_addr
, bool top_compref
,
2409 HOST_WIDE_INT
*offset
)
2411 tree op0
= NULL_TREE
, op1
= NULL_TREE
, tmp
, step
;
2412 enum tree_code code
;
2413 tree type
, orig_type
= TREE_TYPE (expr
);
2414 HOST_WIDE_INT off0
, off1
, st
;
2415 tree orig_expr
= expr
;
2419 type
= TREE_TYPE (expr
);
2420 code
= TREE_CODE (expr
);
2426 if (!cst_and_fits_in_hwi (expr
)
2427 || integer_zerop (expr
))
2430 *offset
= int_cst_value (expr
);
2431 return build_int_cst (orig_type
, 0);
2433 case POINTER_PLUS_EXPR
:
2436 op0
= TREE_OPERAND (expr
, 0);
2437 op1
= TREE_OPERAND (expr
, 1);
2439 op0
= strip_offset_1 (op0
, false, false, &off0
);
2440 op1
= strip_offset_1 (op1
, false, false, &off1
);
2442 *offset
= (code
== MINUS_EXPR
? off0
- off1
: off0
+ off1
);
2443 if (op0
== TREE_OPERAND (expr
, 0)
2444 && op1
== TREE_OPERAND (expr
, 1))
2447 if (integer_zerop (op1
))
2449 else if (integer_zerop (op0
))
2451 if (code
== MINUS_EXPR
)
2452 expr
= fold_build1 (NEGATE_EXPR
, type
, op1
);
2457 expr
= fold_build2 (code
, type
, op0
, op1
);
2459 return fold_convert (orig_type
, expr
);
2462 op1
= TREE_OPERAND (expr
, 1);
2463 if (!cst_and_fits_in_hwi (op1
))
2466 op0
= TREE_OPERAND (expr
, 0);
2467 op0
= strip_offset_1 (op0
, false, false, &off0
);
2468 if (op0
== TREE_OPERAND (expr
, 0))
2471 *offset
= off0
* int_cst_value (op1
);
2472 if (integer_zerop (op0
))
2475 expr
= fold_build2 (MULT_EXPR
, type
, op0
, op1
);
2477 return fold_convert (orig_type
, expr
);
2480 case ARRAY_RANGE_REF
:
2484 step
= array_ref_element_size (expr
);
2485 if (!cst_and_fits_in_hwi (step
))
2488 st
= int_cst_value (step
);
2489 op1
= TREE_OPERAND (expr
, 1);
2490 op1
= strip_offset_1 (op1
, false, false, &off1
);
2491 *offset
= off1
* st
;
2494 && integer_zerop (op1
))
2496 /* Strip the component reference completely. */
2497 op0
= TREE_OPERAND (expr
, 0);
2498 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
2511 tmp
= component_ref_field_offset (expr
);
2512 field
= TREE_OPERAND (expr
, 1);
2514 && cst_and_fits_in_hwi (tmp
)
2515 && cst_and_fits_in_hwi (DECL_FIELD_BIT_OFFSET (field
)))
2517 HOST_WIDE_INT boffset
, abs_off
;
2519 /* Strip the component reference completely. */
2520 op0
= TREE_OPERAND (expr
, 0);
2521 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
2522 boffset
= int_cst_value (DECL_FIELD_BIT_OFFSET (field
));
2523 abs_off
= abs_hwi (boffset
) / BITS_PER_UNIT
;
2527 *offset
= off0
+ int_cst_value (tmp
) + abs_off
;
2534 op0
= TREE_OPERAND (expr
, 0);
2535 op0
= strip_offset_1 (op0
, true, true, &off0
);
2538 if (op0
== TREE_OPERAND (expr
, 0))
2541 expr
= build_fold_addr_expr (op0
);
2542 return fold_convert (orig_type
, expr
);
2545 /* ??? Offset operand? */
2546 inside_addr
= false;
2553 /* Default handling of expressions for that we want to recurse into
2554 the first operand. */
2555 op0
= TREE_OPERAND (expr
, 0);
2556 op0
= strip_offset_1 (op0
, inside_addr
, false, &off0
);
2559 if (op0
== TREE_OPERAND (expr
, 0)
2560 && (!op1
|| op1
== TREE_OPERAND (expr
, 1)))
2563 expr
= copy_node (expr
);
2564 TREE_OPERAND (expr
, 0) = op0
;
2566 TREE_OPERAND (expr
, 1) = op1
;
2568 /* Inside address, we might strip the top level component references,
2569 thus changing type of the expression. Handling of ADDR_EXPR
2571 expr
= fold_convert (orig_type
, expr
);
2576 /* Strips constant offsets from EXPR and stores them to OFFSET. */
2579 strip_offset (tree expr
, unsigned HOST_WIDE_INT
*offset
)
2582 tree core
= strip_offset_1 (expr
, false, false, &off
);
2587 /* Returns variant of TYPE that can be used as base for different uses.
2588 We return unsigned type with the same precision, which avoids problems
2592 generic_type_for (tree type
)
2594 if (POINTER_TYPE_P (type
))
2595 return unsigned_type_for (type
);
2597 if (TYPE_UNSIGNED (type
))
2600 return unsigned_type_for (type
);
2603 /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
2604 the bitmap to that we should store it. */
2606 static struct ivopts_data
*fd_ivopts_data
;
2608 find_depends (tree
*expr_p
, int *ws ATTRIBUTE_UNUSED
, void *data
)
2610 bitmap
*depends_on
= (bitmap
*) data
;
2611 struct version_info
*info
;
2613 if (TREE_CODE (*expr_p
) != SSA_NAME
)
2615 info
= name_info (fd_ivopts_data
, *expr_p
);
2617 if (!info
->inv_id
|| info
->has_nonlin_use
)
2621 *depends_on
= BITMAP_ALLOC (NULL
);
2622 bitmap_set_bit (*depends_on
, info
->inv_id
);
2627 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2628 position to POS. If USE is not NULL, the candidate is set as related to
2629 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
2630 replacement of the final value of the iv by a direct computation. */
2632 static struct iv_cand
*
2633 add_candidate_1 (struct ivopts_data
*data
,
2634 tree base
, tree step
, bool important
, enum iv_position pos
,
2635 struct iv_use
*use
, gimple incremented_at
)
2638 struct iv_cand
*cand
= NULL
;
2639 tree type
, orig_type
;
2641 /* For non-original variables, make sure their values are computed in a type
2642 that does not invoke undefined behavior on overflows (since in general,
2643 we cannot prove that these induction variables are non-wrapping). */
2644 if (pos
!= IP_ORIGINAL
)
2646 orig_type
= TREE_TYPE (base
);
2647 type
= generic_type_for (orig_type
);
2648 if (type
!= orig_type
)
2650 base
= fold_convert (type
, base
);
2651 step
= fold_convert (type
, step
);
2655 for (i
= 0; i
< n_iv_cands (data
); i
++)
2657 cand
= iv_cand (data
, i
);
2659 if (cand
->pos
!= pos
)
2662 if (cand
->incremented_at
!= incremented_at
2663 || ((pos
== IP_AFTER_USE
|| pos
== IP_BEFORE_USE
)
2664 && cand
->ainc_use
!= use
))
2678 if (operand_equal_p (base
, cand
->iv
->base
, 0)
2679 && operand_equal_p (step
, cand
->iv
->step
, 0)
2680 && (TYPE_PRECISION (TREE_TYPE (base
))
2681 == TYPE_PRECISION (TREE_TYPE (cand
->iv
->base
))))
2685 if (i
== n_iv_cands (data
))
2687 cand
= XCNEW (struct iv_cand
);
2693 cand
->iv
= alloc_iv (base
, step
);
2696 if (pos
!= IP_ORIGINAL
&& cand
->iv
)
2698 cand
->var_before
= create_tmp_var_raw (TREE_TYPE (base
), "ivtmp");
2699 cand
->var_after
= cand
->var_before
;
2701 cand
->important
= important
;
2702 cand
->incremented_at
= incremented_at
;
2703 data
->iv_candidates
.safe_push (cand
);
2706 && TREE_CODE (step
) != INTEGER_CST
)
2708 fd_ivopts_data
= data
;
2709 walk_tree (&step
, find_depends
, &cand
->depends_on
, NULL
);
2712 if (pos
== IP_AFTER_USE
|| pos
== IP_BEFORE_USE
)
2713 cand
->ainc_use
= use
;
2715 cand
->ainc_use
= NULL
;
2717 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2718 dump_cand (dump_file
, cand
);
2721 if (important
&& !cand
->important
)
2723 cand
->important
= true;
2724 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2725 fprintf (dump_file
, "Candidate %d is important\n", cand
->id
);
2730 bitmap_set_bit (use
->related_cands
, i
);
2731 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2732 fprintf (dump_file
, "Candidate %d is related to use %d\n",
2739 /* Returns true if incrementing the induction variable at the end of the LOOP
2742 The purpose is to avoid splitting latch edge with a biv increment, thus
2743 creating a jump, possibly confusing other optimization passes and leaving
2744 less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS
2745 is not available (so we do not have a better alternative), or if the latch
2746 edge is already nonempty. */
2749 allow_ip_end_pos_p (struct loop
*loop
)
2751 if (!ip_normal_pos (loop
))
2754 if (!empty_block_p (ip_end_pos (loop
)))
2760 /* If possible, adds autoincrement candidates BASE + STEP * i based on use USE.
2761 Important field is set to IMPORTANT. */
2764 add_autoinc_candidates (struct ivopts_data
*data
, tree base
, tree step
,
2765 bool important
, struct iv_use
*use
)
2767 basic_block use_bb
= gimple_bb (use
->stmt
);
2768 machine_mode mem_mode
;
2769 unsigned HOST_WIDE_INT cstepi
;
2771 /* If we insert the increment in any position other than the standard
2772 ones, we must ensure that it is incremented once per iteration.
2773 It must not be in an inner nested loop, or one side of an if
2775 if (use_bb
->loop_father
!= data
->current_loop
2776 || !dominated_by_p (CDI_DOMINATORS
, data
->current_loop
->latch
, use_bb
)
2777 || stmt_could_throw_p (use
->stmt
)
2778 || !cst_and_fits_in_hwi (step
))
2781 cstepi
= int_cst_value (step
);
2783 mem_mode
= TYPE_MODE (TREE_TYPE (*use
->op_p
));
2784 if (((USE_LOAD_PRE_INCREMENT (mem_mode
)
2785 || USE_STORE_PRE_INCREMENT (mem_mode
))
2786 && GET_MODE_SIZE (mem_mode
) == cstepi
)
2787 || ((USE_LOAD_PRE_DECREMENT (mem_mode
)
2788 || USE_STORE_PRE_DECREMENT (mem_mode
))
2789 && GET_MODE_SIZE (mem_mode
) == -cstepi
))
2791 enum tree_code code
= MINUS_EXPR
;
2793 tree new_step
= step
;
2795 if (POINTER_TYPE_P (TREE_TYPE (base
)))
2797 new_step
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (step
), step
);
2798 code
= POINTER_PLUS_EXPR
;
2801 new_step
= fold_convert (TREE_TYPE (base
), new_step
);
2802 new_base
= fold_build2 (code
, TREE_TYPE (base
), base
, new_step
);
2803 add_candidate_1 (data
, new_base
, step
, important
, IP_BEFORE_USE
, use
,
2806 if (((USE_LOAD_POST_INCREMENT (mem_mode
)
2807 || USE_STORE_POST_INCREMENT (mem_mode
))
2808 && GET_MODE_SIZE (mem_mode
) == cstepi
)
2809 || ((USE_LOAD_POST_DECREMENT (mem_mode
)
2810 || USE_STORE_POST_DECREMENT (mem_mode
))
2811 && GET_MODE_SIZE (mem_mode
) == -cstepi
))
2813 add_candidate_1 (data
, base
, step
, important
, IP_AFTER_USE
, use
,
2818 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2819 position to POS. If USE is not NULL, the candidate is set as related to
2820 it. The candidate computation is scheduled on all available positions. */
2823 add_candidate (struct ivopts_data
*data
,
2824 tree base
, tree step
, bool important
, struct iv_use
*use
)
2826 gcc_assert (use
== NULL
|| use
->sub_id
== 0);
2828 if (ip_normal_pos (data
->current_loop
))
2829 add_candidate_1 (data
, base
, step
, important
, IP_NORMAL
, use
, NULL
);
2830 if (ip_end_pos (data
->current_loop
)
2831 && allow_ip_end_pos_p (data
->current_loop
))
2832 add_candidate_1 (data
, base
, step
, important
, IP_END
, use
, NULL
);
2834 if (use
!= NULL
&& use
->type
== USE_ADDRESS
)
2835 add_autoinc_candidates (data
, base
, step
, important
, use
);
2838 /* Adds standard iv candidates. */
2841 add_standard_iv_candidates (struct ivopts_data
*data
)
2843 add_candidate (data
, integer_zero_node
, integer_one_node
, true, NULL
);
2845 /* The same for a double-integer type if it is still fast enough. */
2847 (long_integer_type_node
) > TYPE_PRECISION (integer_type_node
)
2848 && TYPE_PRECISION (long_integer_type_node
) <= BITS_PER_WORD
)
2849 add_candidate (data
, build_int_cst (long_integer_type_node
, 0),
2850 build_int_cst (long_integer_type_node
, 1), true, NULL
);
2852 /* The same for a double-integer type if it is still fast enough. */
2854 (long_long_integer_type_node
) > TYPE_PRECISION (long_integer_type_node
)
2855 && TYPE_PRECISION (long_long_integer_type_node
) <= BITS_PER_WORD
)
2856 add_candidate (data
, build_int_cst (long_long_integer_type_node
, 0),
2857 build_int_cst (long_long_integer_type_node
, 1), true, NULL
);
2861 /* Adds candidates bases on the old induction variable IV. */
2864 add_old_iv_candidates (struct ivopts_data
*data
, struct iv
*iv
)
2868 struct iv_cand
*cand
;
2870 add_candidate (data
, iv
->base
, iv
->step
, true, NULL
);
2872 /* The same, but with initial value zero. */
2873 if (POINTER_TYPE_P (TREE_TYPE (iv
->base
)))
2874 add_candidate (data
, size_int (0), iv
->step
, true, NULL
);
2876 add_candidate (data
, build_int_cst (TREE_TYPE (iv
->base
), 0),
2877 iv
->step
, true, NULL
);
2879 phi
= SSA_NAME_DEF_STMT (iv
->ssa_name
);
2880 if (gimple_code (phi
) == GIMPLE_PHI
)
2882 /* Additionally record the possibility of leaving the original iv
2884 def
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (data
->current_loop
));
2885 /* Don't add candidate if it's from another PHI node because
2886 it's an affine iv appearing in the form of PEELED_CHREC. */
2887 phi
= SSA_NAME_DEF_STMT (def
);
2888 if (gimple_code (phi
) != GIMPLE_PHI
)
2890 cand
= add_candidate_1 (data
,
2891 iv
->base
, iv
->step
, true, IP_ORIGINAL
, NULL
,
2892 SSA_NAME_DEF_STMT (def
));
2893 cand
->var_before
= iv
->ssa_name
;
2894 cand
->var_after
= def
;
2897 gcc_assert (gimple_bb (phi
) == data
->current_loop
->header
);
2901 /* Adds candidates based on the old induction variables. */
2904 add_old_ivs_candidates (struct ivopts_data
*data
)
2910 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
2912 iv
= ver_info (data
, i
)->iv
;
2913 if (iv
&& iv
->biv_p
&& !integer_zerop (iv
->step
))
2914 add_old_iv_candidates (data
, iv
);
2918 /* Adds candidates based on the value of the induction variable IV and USE. */
2921 add_iv_value_candidates (struct ivopts_data
*data
,
2922 struct iv
*iv
, struct iv_use
*use
)
2924 unsigned HOST_WIDE_INT offset
;
2928 add_candidate (data
, iv
->base
, iv
->step
, false, use
);
2930 /* The same, but with initial value zero. Make such variable important,
2931 since it is generic enough so that possibly many uses may be based
2933 basetype
= TREE_TYPE (iv
->base
);
2934 if (POINTER_TYPE_P (basetype
))
2935 basetype
= sizetype
;
2936 add_candidate (data
, build_int_cst (basetype
, 0),
2937 iv
->step
, true, use
);
2939 /* Third, try removing the constant offset. Make sure to even
2940 add a candidate for &a[0] vs. (T *)&a. */
2941 base
= strip_offset (iv
->base
, &offset
);
2943 || base
!= iv
->base
)
2944 add_candidate (data
, base
, iv
->step
, false, use
);
2947 /* Adds candidates based on the uses. */
2950 add_derived_ivs_candidates (struct ivopts_data
*data
)
2954 for (i
= 0; i
< n_iv_uses (data
); i
++)
2956 struct iv_use
*use
= iv_use (data
, i
);
2963 case USE_NONLINEAR_EXPR
:
2966 /* Just add the ivs based on the value of the iv used here. */
2967 add_iv_value_candidates (data
, use
->iv
, use
);
2976 /* Record important candidates and add them to related_cands bitmaps
2980 record_important_candidates (struct ivopts_data
*data
)
2985 for (i
= 0; i
< n_iv_cands (data
); i
++)
2987 struct iv_cand
*cand
= iv_cand (data
, i
);
2989 if (cand
->important
)
2990 bitmap_set_bit (data
->important_candidates
, i
);
2993 data
->consider_all_candidates
= (n_iv_cands (data
)
2994 <= CONSIDER_ALL_CANDIDATES_BOUND
);
2996 if (data
->consider_all_candidates
)
2998 /* We will not need "related_cands" bitmaps in this case,
2999 so release them to decrease peak memory consumption. */
3000 for (i
= 0; i
< n_iv_uses (data
); i
++)
3002 use
= iv_use (data
, i
);
3003 BITMAP_FREE (use
->related_cands
);
3008 /* Add important candidates to the related_cands bitmaps. */
3009 for (i
= 0; i
< n_iv_uses (data
); i
++)
3010 bitmap_ior_into (iv_use (data
, i
)->related_cands
,
3011 data
->important_candidates
);
3015 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
3016 If consider_all_candidates is true, we use a two-dimensional array, otherwise
3017 we allocate a simple list to every use. */
3020 alloc_use_cost_map (struct ivopts_data
*data
)
3022 unsigned i
, size
, s
;
3024 for (i
= 0; i
< n_iv_uses (data
); i
++)
3026 struct iv_use
*use
= iv_use (data
, i
);
3028 if (data
->consider_all_candidates
)
3029 size
= n_iv_cands (data
);
3032 s
= bitmap_count_bits (use
->related_cands
);
3034 /* Round up to the power of two, so that moduling by it is fast. */
3035 size
= s
? (1 << ceil_log2 (s
)) : 1;
3038 use
->n_map_members
= size
;
3039 use
->cost_map
= XCNEWVEC (struct cost_pair
, size
);
3043 /* Returns description of computation cost of expression whose runtime
3044 cost is RUNTIME and complexity corresponds to COMPLEXITY. */
3047 new_cost (unsigned runtime
, unsigned complexity
)
3051 cost
.cost
= runtime
;
3052 cost
.complexity
= complexity
;
3057 /* Returns true if COST is infinite. */
3060 infinite_cost_p (comp_cost cost
)
3062 return cost
.cost
== INFTY
;
3065 /* Adds costs COST1 and COST2. */
3068 add_costs (comp_cost cost1
, comp_cost cost2
)
3070 if (infinite_cost_p (cost1
) || infinite_cost_p (cost2
))
3071 return infinite_cost
;
3073 cost1
.cost
+= cost2
.cost
;
3074 cost1
.complexity
+= cost2
.complexity
;
3078 /* Subtracts costs COST1 and COST2. */
3081 sub_costs (comp_cost cost1
, comp_cost cost2
)
3083 cost1
.cost
-= cost2
.cost
;
3084 cost1
.complexity
-= cost2
.complexity
;
3089 /* Returns a negative number if COST1 < COST2, a positive number if
3090 COST1 > COST2, and 0 if COST1 = COST2. */
3093 compare_costs (comp_cost cost1
, comp_cost cost2
)
3095 if (cost1
.cost
== cost2
.cost
)
3096 return cost1
.complexity
- cost2
.complexity
;
3098 return cost1
.cost
- cost2
.cost
;
3101 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
3102 on invariants DEPENDS_ON and that the value used in expressing it
3103 is VALUE, and in case of iv elimination the comparison operator is COMP. */
3106 set_use_iv_cost (struct ivopts_data
*data
,
3107 struct iv_use
*use
, struct iv_cand
*cand
,
3108 comp_cost cost
, bitmap depends_on
, tree value
,
3109 enum tree_code comp
, int inv_expr_id
)
3113 if (infinite_cost_p (cost
))
3115 BITMAP_FREE (depends_on
);
3119 if (data
->consider_all_candidates
)
3121 use
->cost_map
[cand
->id
].cand
= cand
;
3122 use
->cost_map
[cand
->id
].cost
= cost
;
3123 use
->cost_map
[cand
->id
].depends_on
= depends_on
;
3124 use
->cost_map
[cand
->id
].value
= value
;
3125 use
->cost_map
[cand
->id
].comp
= comp
;
3126 use
->cost_map
[cand
->id
].inv_expr_id
= inv_expr_id
;
3130 /* n_map_members is a power of two, so this computes modulo. */
3131 s
= cand
->id
& (use
->n_map_members
- 1);
3132 for (i
= s
; i
< use
->n_map_members
; i
++)
3133 if (!use
->cost_map
[i
].cand
)
3135 for (i
= 0; i
< s
; i
++)
3136 if (!use
->cost_map
[i
].cand
)
3142 use
->cost_map
[i
].cand
= cand
;
3143 use
->cost_map
[i
].cost
= cost
;
3144 use
->cost_map
[i
].depends_on
= depends_on
;
3145 use
->cost_map
[i
].value
= value
;
3146 use
->cost_map
[i
].comp
= comp
;
3147 use
->cost_map
[i
].inv_expr_id
= inv_expr_id
;
3150 /* Gets cost of (USE, CANDIDATE) pair. */
3152 static struct cost_pair
*
3153 get_use_iv_cost (struct ivopts_data
*data
, struct iv_use
*use
,
3154 struct iv_cand
*cand
)
3157 struct cost_pair
*ret
;
3162 if (data
->consider_all_candidates
)
3164 ret
= use
->cost_map
+ cand
->id
;
3171 /* n_map_members is a power of two, so this computes modulo. */
3172 s
= cand
->id
& (use
->n_map_members
- 1);
3173 for (i
= s
; i
< use
->n_map_members
; i
++)
3174 if (use
->cost_map
[i
].cand
== cand
)
3175 return use
->cost_map
+ i
;
3176 else if (use
->cost_map
[i
].cand
== NULL
)
3178 for (i
= 0; i
< s
; i
++)
3179 if (use
->cost_map
[i
].cand
== cand
)
3180 return use
->cost_map
+ i
;
3181 else if (use
->cost_map
[i
].cand
== NULL
)
3187 /* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
3189 produce_memory_decl_rtl (tree obj
, int *regno
)
3191 addr_space_t as
= TYPE_ADDR_SPACE (TREE_TYPE (obj
));
3192 machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
3196 if (TREE_STATIC (obj
) || DECL_EXTERNAL (obj
))
3198 const char *name
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj
));
3199 x
= gen_rtx_SYMBOL_REF (address_mode
, name
);
3200 SET_SYMBOL_REF_DECL (x
, obj
);
3201 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
3202 set_mem_addr_space (x
, as
);
3203 targetm
.encode_section_info (obj
, x
, true);
3207 x
= gen_raw_REG (address_mode
, (*regno
)++);
3208 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
3209 set_mem_addr_space (x
, as
);
3215 /* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
3216 walk_tree. DATA contains the actual fake register number. */
3219 prepare_decl_rtl (tree
*expr_p
, int *ws
, void *data
)
3221 tree obj
= NULL_TREE
;
3223 int *regno
= (int *) data
;
3225 switch (TREE_CODE (*expr_p
))
3228 for (expr_p
= &TREE_OPERAND (*expr_p
, 0);
3229 handled_component_p (*expr_p
);
3230 expr_p
= &TREE_OPERAND (*expr_p
, 0))
3233 if (DECL_P (obj
) && HAS_RTL_P (obj
) && !DECL_RTL_SET_P (obj
))
3234 x
= produce_memory_decl_rtl (obj
, regno
);
3239 obj
= SSA_NAME_VAR (*expr_p
);
3240 /* Defer handling of anonymous SSA_NAMEs to the expander. */
3243 if (!DECL_RTL_SET_P (obj
))
3244 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
3253 if (DECL_RTL_SET_P (obj
))
3256 if (DECL_MODE (obj
) == BLKmode
)
3257 x
= produce_memory_decl_rtl (obj
, regno
);
3259 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
3269 decl_rtl_to_reset
.safe_push (obj
);
3270 SET_DECL_RTL (obj
, x
);
3276 /* Determines cost of the computation of EXPR. */
3279 computation_cost (tree expr
, bool speed
)
3283 tree type
= TREE_TYPE (expr
);
3285 /* Avoid using hard regs in ways which may be unsupported. */
3286 int regno
= LAST_VIRTUAL_REGISTER
+ 1;
3287 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
3288 enum node_frequency real_frequency
= node
->frequency
;
3290 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3291 crtl
->maybe_hot_insn_p
= speed
;
3292 walk_tree (&expr
, prepare_decl_rtl
, ®no
, NULL
);
3294 rslt
= expand_expr (expr
, NULL_RTX
, TYPE_MODE (type
), EXPAND_NORMAL
);
3297 default_rtl_profile ();
3298 node
->frequency
= real_frequency
;
3300 cost
= seq_cost (seq
, speed
);
3302 cost
+= address_cost (XEXP (rslt
, 0), TYPE_MODE (type
),
3303 TYPE_ADDR_SPACE (type
), speed
);
3304 else if (!REG_P (rslt
))
3305 cost
+= set_src_cost (rslt
, speed
);
3310 /* Returns variable containing the value of candidate CAND at statement AT. */
3313 var_at_stmt (struct loop
*loop
, struct iv_cand
*cand
, gimple stmt
)
3315 if (stmt_after_increment (loop
, cand
, stmt
))
3316 return cand
->var_after
;
3318 return cand
->var_before
;
3321 /* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
3322 same precision that is at least as wide as the precision of TYPE, stores
3323 BA to A and BB to B, and returns the type of BA. Otherwise, returns the
3327 determine_common_wider_type (tree
*a
, tree
*b
)
3329 tree wider_type
= NULL
;
3331 tree atype
= TREE_TYPE (*a
);
3333 if (CONVERT_EXPR_P (*a
))
3335 suba
= TREE_OPERAND (*a
, 0);
3336 wider_type
= TREE_TYPE (suba
);
3337 if (TYPE_PRECISION (wider_type
) < TYPE_PRECISION (atype
))
3343 if (CONVERT_EXPR_P (*b
))
3345 subb
= TREE_OPERAND (*b
, 0);
3346 if (TYPE_PRECISION (wider_type
) != TYPE_PRECISION (TREE_TYPE (subb
)))
3357 /* Determines the expression by that USE is expressed from induction variable
3358 CAND at statement AT in LOOP. The expression is stored in a decomposed
3359 form into AFF. Returns false if USE cannot be expressed using CAND. */
3362 get_computation_aff (struct loop
*loop
,
3363 struct iv_use
*use
, struct iv_cand
*cand
, gimple at
,
3364 struct aff_tree
*aff
)
3366 tree ubase
= use
->iv
->base
;
3367 tree ustep
= use
->iv
->step
;
3368 tree cbase
= cand
->iv
->base
;
3369 tree cstep
= cand
->iv
->step
, cstep_common
;
3370 tree utype
= TREE_TYPE (ubase
), ctype
= TREE_TYPE (cbase
);
3371 tree common_type
, var
;
3373 aff_tree cbase_aff
, var_aff
;
3376 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
3378 /* We do not have a precision to express the values of use. */
3382 var
= var_at_stmt (loop
, cand
, at
);
3383 uutype
= unsigned_type_for (utype
);
3385 /* If the conversion is not noop, perform it. */
3386 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
3388 cstep
= fold_convert (uutype
, cstep
);
3389 cbase
= fold_convert (uutype
, cbase
);
3390 var
= fold_convert (uutype
, var
);
3393 if (!constant_multiple_of (ustep
, cstep
, &rat
))
3396 /* In case both UBASE and CBASE are shortened to UUTYPE from some common
3397 type, we achieve better folding by computing their difference in this
3398 wider type, and cast the result to UUTYPE. We do not need to worry about
3399 overflows, as all the arithmetics will in the end be performed in UUTYPE
3401 common_type
= determine_common_wider_type (&ubase
, &cbase
);
3403 /* use = ubase - ratio * cbase + ratio * var. */
3404 tree_to_aff_combination (ubase
, common_type
, aff
);
3405 tree_to_aff_combination (cbase
, common_type
, &cbase_aff
);
3406 tree_to_aff_combination (var
, uutype
, &var_aff
);
3408 /* We need to shift the value if we are after the increment. */
3409 if (stmt_after_increment (loop
, cand
, at
))
3413 if (common_type
!= uutype
)
3414 cstep_common
= fold_convert (common_type
, cstep
);
3416 cstep_common
= cstep
;
3418 tree_to_aff_combination (cstep_common
, common_type
, &cstep_aff
);
3419 aff_combination_add (&cbase_aff
, &cstep_aff
);
3422 aff_combination_scale (&cbase_aff
, -rat
);
3423 aff_combination_add (aff
, &cbase_aff
);
3424 if (common_type
!= uutype
)
3425 aff_combination_convert (aff
, uutype
);
3427 aff_combination_scale (&var_aff
, rat
);
3428 aff_combination_add (aff
, &var_aff
);
3433 /* Return the type of USE. */
3436 get_use_type (struct iv_use
*use
)
3438 tree base_type
= TREE_TYPE (use
->iv
->base
);
3441 if (use
->type
== USE_ADDRESS
)
3443 /* The base_type may be a void pointer. Create a pointer type based on
3444 the mem_ref instead. */
3445 type
= build_pointer_type (TREE_TYPE (*use
->op_p
));
3446 gcc_assert (TYPE_ADDR_SPACE (TREE_TYPE (type
))
3447 == TYPE_ADDR_SPACE (TREE_TYPE (base_type
)));
3455 /* Determines the expression by that USE is expressed from induction variable
3456 CAND at statement AT in LOOP. The computation is unshared. */
3459 get_computation_at (struct loop
*loop
,
3460 struct iv_use
*use
, struct iv_cand
*cand
, gimple at
)
3463 tree type
= get_use_type (use
);
3465 if (!get_computation_aff (loop
, use
, cand
, at
, &aff
))
3467 unshare_aff_combination (&aff
);
3468 return fold_convert (type
, aff_combination_to_tree (&aff
));
3471 /* Determines the expression by that USE is expressed from induction variable
3472 CAND in LOOP. The computation is unshared. */
3475 get_computation (struct loop
*loop
, struct iv_use
*use
, struct iv_cand
*cand
)
3477 return get_computation_at (loop
, use
, cand
, use
->stmt
);
3480 /* Adjust the cost COST for being in loop setup rather than loop body.
3481 If we're optimizing for space, the loop setup overhead is constant;
3482 if we're optimizing for speed, amortize it over the per-iteration cost. */
3484 adjust_setup_cost (struct ivopts_data
*data
, unsigned cost
)
3488 else if (optimize_loop_for_speed_p (data
->current_loop
))
3489 return cost
/ avg_loop_niter (data
->current_loop
);
3494 /* Returns true if multiplying by RATIO is allowed in an address. Test the
3495 validity for a memory reference accessing memory of mode MODE in
3496 address space AS. */
3500 multiplier_allowed_in_address_p (HOST_WIDE_INT ratio
, machine_mode mode
,
3503 #define MAX_RATIO 128
3504 unsigned int data_index
= (int) as
* MAX_MACHINE_MODE
+ (int) mode
;
3505 static vec
<sbitmap
> valid_mult_list
;
3508 if (data_index
>= valid_mult_list
.length ())
3509 valid_mult_list
.safe_grow_cleared (data_index
+ 1);
3511 valid_mult
= valid_mult_list
[data_index
];
3514 machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
3515 rtx reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
3516 rtx reg2
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 2);
3520 valid_mult
= sbitmap_alloc (2 * MAX_RATIO
+ 1);
3521 bitmap_clear (valid_mult
);
3522 scaled
= gen_rtx_fmt_ee (MULT
, address_mode
, reg1
, NULL_RTX
);
3523 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, scaled
, reg2
);
3524 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
3526 XEXP (scaled
, 1) = gen_int_mode (i
, address_mode
);
3527 if (memory_address_addr_space_p (mode
, addr
, as
)
3528 || memory_address_addr_space_p (mode
, scaled
, as
))
3529 bitmap_set_bit (valid_mult
, i
+ MAX_RATIO
);
3532 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3534 fprintf (dump_file
, " allowed multipliers:");
3535 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
3536 if (bitmap_bit_p (valid_mult
, i
+ MAX_RATIO
))
3537 fprintf (dump_file
, " %d", (int) i
);
3538 fprintf (dump_file
, "\n");
3539 fprintf (dump_file
, "\n");
3542 valid_mult_list
[data_index
] = valid_mult
;
3545 if (ratio
> MAX_RATIO
|| ratio
< -MAX_RATIO
)
3548 return bitmap_bit_p (valid_mult
, ratio
+ MAX_RATIO
);
3551 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
3552 If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
3553 variable is omitted. Compute the cost for a memory reference that accesses
3554 a memory location of mode MEM_MODE in address space AS.
3556 MAY_AUTOINC is set to true if the autoincrement (increasing index by
3557 size of MEM_MODE / RATIO) is available. To make this determination, we
3558 look at the size of the increment to be made, which is given in CSTEP.
3559 CSTEP may be zero if the step is unknown.
3560 STMT_AFTER_INC is true iff the statement we're looking at is after the
3561 increment of the original biv.
3563 TODO -- there must be some better way. This all is quite crude. */
3567 AINC_PRE_INC
, /* Pre increment. */
3568 AINC_PRE_DEC
, /* Pre decrement. */
3569 AINC_POST_INC
, /* Post increment. */
3570 AINC_POST_DEC
, /* Post decrement. */
3571 AINC_NONE
/* Also the number of auto increment types. */
3574 typedef struct address_cost_data_s
3576 HOST_WIDE_INT min_offset
, max_offset
;
3577 unsigned costs
[2][2][2][2];
3578 unsigned ainc_costs
[AINC_NONE
];
3579 } *address_cost_data
;
3583 get_address_cost (bool symbol_present
, bool var_present
,
3584 unsigned HOST_WIDE_INT offset
, HOST_WIDE_INT ratio
,
3585 HOST_WIDE_INT cstep
, machine_mode mem_mode
,
3586 addr_space_t as
, bool speed
,
3587 bool stmt_after_inc
, bool *may_autoinc
)
3589 machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
3590 static vec
<address_cost_data
> address_cost_data_list
;
3591 unsigned int data_index
= (int) as
* MAX_MACHINE_MODE
+ (int) mem_mode
;
3592 address_cost_data data
;
3593 static bool has_preinc
[MAX_MACHINE_MODE
], has_postinc
[MAX_MACHINE_MODE
];
3594 static bool has_predec
[MAX_MACHINE_MODE
], has_postdec
[MAX_MACHINE_MODE
];
3595 unsigned cost
, acost
, complexity
;
3596 enum ainc_type autoinc_type
;
3597 bool offset_p
, ratio_p
, autoinc
;
3598 HOST_WIDE_INT s_offset
, autoinc_offset
, msize
;
3599 unsigned HOST_WIDE_INT mask
;
3602 if (data_index
>= address_cost_data_list
.length ())
3603 address_cost_data_list
.safe_grow_cleared (data_index
+ 1);
3605 data
= address_cost_data_list
[data_index
];
3609 HOST_WIDE_INT rat
, off
= 0;
3610 int old_cse_not_expected
, width
;
3611 unsigned sym_p
, var_p
, off_p
, rat_p
, add_c
;
3616 data
= (address_cost_data
) xcalloc (1, sizeof (*data
));
3618 reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
3620 width
= GET_MODE_BITSIZE (address_mode
) - 1;
3621 if (width
> (HOST_BITS_PER_WIDE_INT
- 1))
3622 width
= HOST_BITS_PER_WIDE_INT
- 1;
3623 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, reg1
, NULL_RTX
);
3625 for (i
= width
; i
>= 0; i
--)
3627 off
= -((unsigned HOST_WIDE_INT
) 1 << i
);
3628 XEXP (addr
, 1) = gen_int_mode (off
, address_mode
);
3629 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
3632 data
->min_offset
= (i
== -1? 0 : off
);
3634 for (i
= width
; i
>= 0; i
--)
3636 off
= ((unsigned HOST_WIDE_INT
) 1 << i
) - 1;
3637 XEXP (addr
, 1) = gen_int_mode (off
, address_mode
);
3638 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
3640 /* For some strict-alignment targets, the offset must be naturally
3641 aligned. Try an aligned offset if mem_mode is not QImode. */
3642 off
= mem_mode
!= QImode
3643 ? ((unsigned HOST_WIDE_INT
) 1 << i
)
3644 - GET_MODE_SIZE (mem_mode
)
3648 XEXP (addr
, 1) = gen_int_mode (off
, address_mode
);
3649 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
3655 data
->max_offset
= off
;
3657 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3659 fprintf (dump_file
, "get_address_cost:\n");
3660 fprintf (dump_file
, " min offset %s " HOST_WIDE_INT_PRINT_DEC
"\n",
3661 GET_MODE_NAME (mem_mode
),
3663 fprintf (dump_file
, " max offset %s " HOST_WIDE_INT_PRINT_DEC
"\n",
3664 GET_MODE_NAME (mem_mode
),
3669 for (i
= 2; i
<= MAX_RATIO
; i
++)
3670 if (multiplier_allowed_in_address_p (i
, mem_mode
, as
))
3676 /* Compute the cost of various addressing modes. */
3678 reg0
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
3679 reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 2);
3681 if (USE_LOAD_PRE_DECREMENT (mem_mode
)
3682 || USE_STORE_PRE_DECREMENT (mem_mode
))
3684 addr
= gen_rtx_PRE_DEC (address_mode
, reg0
);
3685 has_predec
[mem_mode
]
3686 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3688 if (has_predec
[mem_mode
])
3689 data
->ainc_costs
[AINC_PRE_DEC
]
3690 = address_cost (addr
, mem_mode
, as
, speed
);
3692 if (USE_LOAD_POST_DECREMENT (mem_mode
)
3693 || USE_STORE_POST_DECREMENT (mem_mode
))
3695 addr
= gen_rtx_POST_DEC (address_mode
, reg0
);
3696 has_postdec
[mem_mode
]
3697 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3699 if (has_postdec
[mem_mode
])
3700 data
->ainc_costs
[AINC_POST_DEC
]
3701 = address_cost (addr
, mem_mode
, as
, speed
);
3703 if (USE_LOAD_PRE_INCREMENT (mem_mode
)
3704 || USE_STORE_PRE_DECREMENT (mem_mode
))
3706 addr
= gen_rtx_PRE_INC (address_mode
, reg0
);
3707 has_preinc
[mem_mode
]
3708 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3710 if (has_preinc
[mem_mode
])
3711 data
->ainc_costs
[AINC_PRE_INC
]
3712 = address_cost (addr
, mem_mode
, as
, speed
);
3714 if (USE_LOAD_POST_INCREMENT (mem_mode
)
3715 || USE_STORE_POST_INCREMENT (mem_mode
))
3717 addr
= gen_rtx_POST_INC (address_mode
, reg0
);
3718 has_postinc
[mem_mode
]
3719 = memory_address_addr_space_p (mem_mode
, addr
, as
);
3721 if (has_postinc
[mem_mode
])
3722 data
->ainc_costs
[AINC_POST_INC
]
3723 = address_cost (addr
, mem_mode
, as
, speed
);
3725 for (i
= 0; i
< 16; i
++)
3728 var_p
= (i
>> 1) & 1;
3729 off_p
= (i
>> 2) & 1;
3730 rat_p
= (i
>> 3) & 1;
3734 addr
= gen_rtx_fmt_ee (MULT
, address_mode
, addr
,
3735 gen_int_mode (rat
, address_mode
));
3738 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, addr
, reg1
);
3742 base
= gen_rtx_SYMBOL_REF (address_mode
, ggc_strdup (""));
3743 /* ??? We can run into trouble with some backends by presenting
3744 it with symbols which haven't been properly passed through
3745 targetm.encode_section_info. By setting the local bit, we
3746 enhance the probability of things working. */
3747 SYMBOL_REF_FLAGS (base
) = SYMBOL_FLAG_LOCAL
;
3750 base
= gen_rtx_fmt_e (CONST
, address_mode
,
3752 (PLUS
, address_mode
, base
,
3753 gen_int_mode (off
, address_mode
)));
3756 base
= gen_int_mode (off
, address_mode
);
3761 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, addr
, base
);
3764 /* To avoid splitting addressing modes, pretend that no cse will
3766 old_cse_not_expected
= cse_not_expected
;
3767 cse_not_expected
= true;
3768 addr
= memory_address_addr_space (mem_mode
, addr
, as
);
3769 cse_not_expected
= old_cse_not_expected
;
3773 acost
= seq_cost (seq
, speed
);
3774 acost
+= address_cost (addr
, mem_mode
, as
, speed
);
3778 data
->costs
[sym_p
][var_p
][off_p
][rat_p
] = acost
;
3781 /* On some targets, it is quite expensive to load symbol to a register,
3782 which makes addresses that contain symbols look much more expensive.
3783 However, the symbol will have to be loaded in any case before the
3784 loop (and quite likely we have it in register already), so it does not
3785 make much sense to penalize them too heavily. So make some final
3786 tweaks for the SYMBOL_PRESENT modes:
3788 If VAR_PRESENT is false, and the mode obtained by changing symbol to
3789 var is cheaper, use this mode with small penalty.
3790 If VAR_PRESENT is true, try whether the mode with
3791 SYMBOL_PRESENT = false is cheaper even with cost of addition, and
3792 if this is the case, use it. */
3793 add_c
= add_cost (speed
, address_mode
);
3794 for (i
= 0; i
< 8; i
++)
3797 off_p
= (i
>> 1) & 1;
3798 rat_p
= (i
>> 2) & 1;
3800 acost
= data
->costs
[0][1][off_p
][rat_p
] + 1;
3804 if (acost
< data
->costs
[1][var_p
][off_p
][rat_p
])
3805 data
->costs
[1][var_p
][off_p
][rat_p
] = acost
;
3808 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3810 fprintf (dump_file
, "Address costs:\n");
3812 for (i
= 0; i
< 16; i
++)
3815 var_p
= (i
>> 1) & 1;
3816 off_p
= (i
>> 2) & 1;
3817 rat_p
= (i
>> 3) & 1;
3819 fprintf (dump_file
, " ");
3821 fprintf (dump_file
, "sym + ");
3823 fprintf (dump_file
, "var + ");
3825 fprintf (dump_file
, "cst + ");
3827 fprintf (dump_file
, "rat * ");
3829 acost
= data
->costs
[sym_p
][var_p
][off_p
][rat_p
];
3830 fprintf (dump_file
, "index costs %d\n", acost
);
3832 if (has_predec
[mem_mode
] || has_postdec
[mem_mode
]
3833 || has_preinc
[mem_mode
] || has_postinc
[mem_mode
])
3834 fprintf (dump_file
, " May include autoinc/dec\n");
3835 fprintf (dump_file
, "\n");
3838 address_cost_data_list
[data_index
] = data
;
3841 bits
= GET_MODE_BITSIZE (address_mode
);
3842 mask
= ~(~(unsigned HOST_WIDE_INT
) 0 << (bits
- 1) << 1);
3844 if ((offset
>> (bits
- 1) & 1))
3849 autoinc_type
= AINC_NONE
;
3850 msize
= GET_MODE_SIZE (mem_mode
);
3851 autoinc_offset
= offset
;
3853 autoinc_offset
+= ratio
* cstep
;
3854 if (symbol_present
|| var_present
|| ratio
!= 1)
3858 if (has_postinc
[mem_mode
] && autoinc_offset
== 0
3860 autoinc_type
= AINC_POST_INC
;
3861 else if (has_postdec
[mem_mode
] && autoinc_offset
== 0
3863 autoinc_type
= AINC_POST_DEC
;
3864 else if (has_preinc
[mem_mode
] && autoinc_offset
== msize
3866 autoinc_type
= AINC_PRE_INC
;
3867 else if (has_predec
[mem_mode
] && autoinc_offset
== -msize
3869 autoinc_type
= AINC_PRE_DEC
;
3871 if (autoinc_type
!= AINC_NONE
)
3876 offset_p
= (s_offset
!= 0
3877 && data
->min_offset
<= s_offset
3878 && s_offset
<= data
->max_offset
);
3879 ratio_p
= (ratio
!= 1
3880 && multiplier_allowed_in_address_p (ratio
, mem_mode
, as
));
3882 if (ratio
!= 1 && !ratio_p
)
3883 cost
+= mult_by_coeff_cost (ratio
, address_mode
, speed
);
3885 if (s_offset
&& !offset_p
&& !symbol_present
)
3886 cost
+= add_cost (speed
, address_mode
);
3889 *may_autoinc
= autoinc
;
3891 acost
= data
->ainc_costs
[autoinc_type
];
3893 acost
= data
->costs
[symbol_present
][var_present
][offset_p
][ratio_p
];
3894 complexity
= (symbol_present
!= 0) + (var_present
!= 0) + offset_p
+ ratio_p
;
3895 return new_cost (cost
+ acost
, complexity
);
3898 /* Calculate the SPEED or size cost of shiftadd EXPR in MODE. MULT is the
3899 the EXPR operand holding the shift. COST0 and COST1 are the costs for
3900 calculating the operands of EXPR. Returns true if successful, and returns
3901 the cost in COST. */
3904 get_shiftadd_cost (tree expr
, machine_mode mode
, comp_cost cost0
,
3905 comp_cost cost1
, tree mult
, bool speed
, comp_cost
*cost
)
3908 tree op1
= TREE_OPERAND (expr
, 1);
3909 tree cst
= TREE_OPERAND (mult
, 1);
3910 tree multop
= TREE_OPERAND (mult
, 0);
3911 int m
= exact_log2 (int_cst_value (cst
));
3912 int maxm
= MIN (BITS_PER_WORD
, GET_MODE_BITSIZE (mode
));
3913 int as_cost
, sa_cost
;
3916 if (!(m
>= 0 && m
< maxm
))
3919 mult_in_op1
= operand_equal_p (op1
, mult
, 0);
3921 as_cost
= add_cost (speed
, mode
) + shift_cost (speed
, mode
, m
);
3923 /* If the target has a cheap shift-and-add or shift-and-sub instruction,
3924 use that in preference to a shift insn followed by an add insn. */
3925 sa_cost
= (TREE_CODE (expr
) != MINUS_EXPR
3926 ? shiftadd_cost (speed
, mode
, m
)
3928 ? shiftsub1_cost (speed
, mode
, m
)
3929 : shiftsub0_cost (speed
, mode
, m
)));
3931 res
= new_cost (MIN (as_cost
, sa_cost
), 0);
3932 res
= add_costs (res
, mult_in_op1
? cost0
: cost1
);
3934 STRIP_NOPS (multop
);
3935 if (!is_gimple_val (multop
))
3936 res
= add_costs (res
, force_expr_to_var_cost (multop
, speed
));
3942 /* Estimates cost of forcing expression EXPR into a variable. */
3945 force_expr_to_var_cost (tree expr
, bool speed
)
3947 static bool costs_initialized
= false;
3948 static unsigned integer_cost
[2];
3949 static unsigned symbol_cost
[2];
3950 static unsigned address_cost
[2];
3952 comp_cost cost0
, cost1
, cost
;
3955 if (!costs_initialized
)
3957 tree type
= build_pointer_type (integer_type_node
);
3962 var
= create_tmp_var_raw (integer_type_node
, "test_var");
3963 TREE_STATIC (var
) = 1;
3964 x
= produce_memory_decl_rtl (var
, NULL
);
3965 SET_DECL_RTL (var
, x
);
3967 addr
= build1 (ADDR_EXPR
, type
, var
);
3970 for (i
= 0; i
< 2; i
++)
3972 integer_cost
[i
] = computation_cost (build_int_cst (integer_type_node
,
3975 symbol_cost
[i
] = computation_cost (addr
, i
) + 1;
3978 = computation_cost (fold_build_pointer_plus_hwi (addr
, 2000), i
) + 1;
3979 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3981 fprintf (dump_file
, "force_expr_to_var_cost %s costs:\n", i
? "speed" : "size");
3982 fprintf (dump_file
, " integer %d\n", (int) integer_cost
[i
]);
3983 fprintf (dump_file
, " symbol %d\n", (int) symbol_cost
[i
]);
3984 fprintf (dump_file
, " address %d\n", (int) address_cost
[i
]);
3985 fprintf (dump_file
, " other %d\n", (int) target_spill_cost
[i
]);
3986 fprintf (dump_file
, "\n");
3990 costs_initialized
= true;
3995 if (SSA_VAR_P (expr
))
3998 if (is_gimple_min_invariant (expr
))
4000 if (TREE_CODE (expr
) == INTEGER_CST
)
4001 return new_cost (integer_cost
[speed
], 0);
4003 if (TREE_CODE (expr
) == ADDR_EXPR
)
4005 tree obj
= TREE_OPERAND (expr
, 0);
4007 if (TREE_CODE (obj
) == VAR_DECL
4008 || TREE_CODE (obj
) == PARM_DECL
4009 || TREE_CODE (obj
) == RESULT_DECL
)
4010 return new_cost (symbol_cost
[speed
], 0);
4013 return new_cost (address_cost
[speed
], 0);
4016 switch (TREE_CODE (expr
))
4018 case POINTER_PLUS_EXPR
:
4022 op0
= TREE_OPERAND (expr
, 0);
4023 op1
= TREE_OPERAND (expr
, 1);
4030 op0
= TREE_OPERAND (expr
, 0);
4036 /* Just an arbitrary value, FIXME. */
4037 return new_cost (target_spill_cost
[speed
], 0);
4040 if (op0
== NULL_TREE
4041 || TREE_CODE (op0
) == SSA_NAME
|| CONSTANT_CLASS_P (op0
))
4044 cost0
= force_expr_to_var_cost (op0
, speed
);
4046 if (op1
== NULL_TREE
4047 || TREE_CODE (op1
) == SSA_NAME
|| CONSTANT_CLASS_P (op1
))
4050 cost1
= force_expr_to_var_cost (op1
, speed
);
4052 mode
= TYPE_MODE (TREE_TYPE (expr
));
4053 switch (TREE_CODE (expr
))
4055 case POINTER_PLUS_EXPR
:
4059 cost
= new_cost (add_cost (speed
, mode
), 0);
4060 if (TREE_CODE (expr
) != NEGATE_EXPR
)
4062 tree mult
= NULL_TREE
;
4064 if (TREE_CODE (op1
) == MULT_EXPR
)
4066 else if (TREE_CODE (op0
) == MULT_EXPR
)
4069 if (mult
!= NULL_TREE
4070 && cst_and_fits_in_hwi (TREE_OPERAND (mult
, 1))
4071 && get_shiftadd_cost (expr
, mode
, cost0
, cost1
, mult
,
4079 tree inner_mode
, outer_mode
;
4080 outer_mode
= TREE_TYPE (expr
);
4081 inner_mode
= TREE_TYPE (op0
);
4082 cost
= new_cost (convert_cost (TYPE_MODE (outer_mode
),
4083 TYPE_MODE (inner_mode
), speed
), 0);
4088 if (cst_and_fits_in_hwi (op0
))
4089 cost
= new_cost (mult_by_coeff_cost (int_cst_value (op0
),
4091 else if (cst_and_fits_in_hwi (op1
))
4092 cost
= new_cost (mult_by_coeff_cost (int_cst_value (op1
),
4095 return new_cost (target_spill_cost
[speed
], 0);
4102 cost
= add_costs (cost
, cost0
);
4103 cost
= add_costs (cost
, cost1
);
4105 /* Bound the cost by target_spill_cost. The parts of complicated
4106 computations often are either loop invariant or at least can
4107 be shared between several iv uses, so letting this grow without
4108 limits would not give reasonable results. */
4109 if (cost
.cost
> (int) target_spill_cost
[speed
])
4110 cost
.cost
= target_spill_cost
[speed
];
4115 /* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
4116 invariants the computation depends on. */
4119 force_var_cost (struct ivopts_data
*data
,
4120 tree expr
, bitmap
*depends_on
)
4124 fd_ivopts_data
= data
;
4125 walk_tree (&expr
, find_depends
, depends_on
, NULL
);
4128 return force_expr_to_var_cost (expr
, data
->speed
);
4131 /* Estimates cost of expressing address ADDR as var + symbol + offset. The
4132 value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
4133 to false if the corresponding part is missing. DEPENDS_ON is a set of the
4134 invariants the computation depends on. */
4137 split_address_cost (struct ivopts_data
*data
,
4138 tree addr
, bool *symbol_present
, bool *var_present
,
4139 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
4142 HOST_WIDE_INT bitsize
;
4143 HOST_WIDE_INT bitpos
;
4146 int unsignedp
, volatilep
;
4148 core
= get_inner_reference (addr
, &bitsize
, &bitpos
, &toffset
, &mode
,
4149 &unsignedp
, &volatilep
, false);
4152 || bitpos
% BITS_PER_UNIT
!= 0
4153 || TREE_CODE (core
) != VAR_DECL
)
4155 *symbol_present
= false;
4156 *var_present
= true;
4157 fd_ivopts_data
= data
;
4158 walk_tree (&addr
, find_depends
, depends_on
, NULL
);
4159 return new_cost (target_spill_cost
[data
->speed
], 0);
4162 *offset
+= bitpos
/ BITS_PER_UNIT
;
4163 if (TREE_STATIC (core
)
4164 || DECL_EXTERNAL (core
))
4166 *symbol_present
= true;
4167 *var_present
= false;
4171 *symbol_present
= false;
4172 *var_present
= true;
4176 /* Estimates cost of expressing difference of addresses E1 - E2 as
4177 var + symbol + offset. The value of offset is added to OFFSET,
4178 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
4179 part is missing. DEPENDS_ON is a set of the invariants the computation
4183 ptr_difference_cost (struct ivopts_data
*data
,
4184 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
4185 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
4187 HOST_WIDE_INT diff
= 0;
4188 aff_tree aff_e1
, aff_e2
;
4191 gcc_assert (TREE_CODE (e1
) == ADDR_EXPR
);
4193 if (ptr_difference_const (e1
, e2
, &diff
))
4196 *symbol_present
= false;
4197 *var_present
= false;
4201 if (integer_zerop (e2
))
4202 return split_address_cost (data
, TREE_OPERAND (e1
, 0),
4203 symbol_present
, var_present
, offset
, depends_on
);
4205 *symbol_present
= false;
4206 *var_present
= true;
4208 type
= signed_type_for (TREE_TYPE (e1
));
4209 tree_to_aff_combination (e1
, type
, &aff_e1
);
4210 tree_to_aff_combination (e2
, type
, &aff_e2
);
4211 aff_combination_scale (&aff_e2
, -1);
4212 aff_combination_add (&aff_e1
, &aff_e2
);
4214 return force_var_cost (data
, aff_combination_to_tree (&aff_e1
), depends_on
);
4217 /* Estimates cost of expressing difference E1 - E2 as
4218 var + symbol + offset. The value of offset is added to OFFSET,
4219 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
4220 part is missing. DEPENDS_ON is a set of the invariants the computation
4224 difference_cost (struct ivopts_data
*data
,
4225 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
4226 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
4228 machine_mode mode
= TYPE_MODE (TREE_TYPE (e1
));
4229 unsigned HOST_WIDE_INT off1
, off2
;
4230 aff_tree aff_e1
, aff_e2
;
4233 e1
= strip_offset (e1
, &off1
);
4234 e2
= strip_offset (e2
, &off2
);
4235 *offset
+= off1
- off2
;
4240 if (TREE_CODE (e1
) == ADDR_EXPR
)
4241 return ptr_difference_cost (data
, e1
, e2
, symbol_present
, var_present
,
4242 offset
, depends_on
);
4243 *symbol_present
= false;
4245 if (operand_equal_p (e1
, e2
, 0))
4247 *var_present
= false;
4251 *var_present
= true;
4253 if (integer_zerop (e2
))
4254 return force_var_cost (data
, e1
, depends_on
);
4256 if (integer_zerop (e1
))
4258 comp_cost cost
= force_var_cost (data
, e2
, depends_on
);
4259 cost
.cost
+= mult_by_coeff_cost (-1, mode
, data
->speed
);
4263 type
= signed_type_for (TREE_TYPE (e1
));
4264 tree_to_aff_combination (e1
, type
, &aff_e1
);
4265 tree_to_aff_combination (e2
, type
, &aff_e2
);
4266 aff_combination_scale (&aff_e2
, -1);
4267 aff_combination_add (&aff_e1
, &aff_e2
);
4269 return force_var_cost (data
, aff_combination_to_tree (&aff_e1
), depends_on
);
4272 /* Returns true if AFF1 and AFF2 are identical. */
4275 compare_aff_trees (aff_tree
*aff1
, aff_tree
*aff2
)
4279 if (aff1
->n
!= aff2
->n
)
4282 for (i
= 0; i
< aff1
->n
; i
++)
4284 if (aff1
->elts
[i
].coef
!= aff2
->elts
[i
].coef
)
4287 if (!operand_equal_p (aff1
->elts
[i
].val
, aff2
->elts
[i
].val
, 0))
4293 /* Stores EXPR in DATA->inv_expr_tab, and assigns it an inv_expr_id. */
4296 get_expr_id (struct ivopts_data
*data
, tree expr
)
4298 struct iv_inv_expr_ent ent
;
4299 struct iv_inv_expr_ent
**slot
;
4302 ent
.hash
= iterative_hash_expr (expr
, 0);
4303 slot
= data
->inv_expr_tab
->find_slot (&ent
, INSERT
);
4307 *slot
= XNEW (struct iv_inv_expr_ent
);
4308 (*slot
)->expr
= expr
;
4309 (*slot
)->hash
= ent
.hash
;
4310 (*slot
)->id
= data
->inv_expr_id
++;
4314 /* Returns the pseudo expr id if expression UBASE - RATIO * CBASE
4315 requires a new compiler generated temporary. Returns -1 otherwise.
4316 ADDRESS_P is a flag indicating if the expression is for address
4320 get_loop_invariant_expr_id (struct ivopts_data
*data
, tree ubase
,
4321 tree cbase
, HOST_WIDE_INT ratio
,
4324 aff_tree ubase_aff
, cbase_aff
;
4332 if ((TREE_CODE (ubase
) == INTEGER_CST
)
4333 && (TREE_CODE (cbase
) == INTEGER_CST
))
4336 /* Strips the constant part. */
4337 if (TREE_CODE (ubase
) == PLUS_EXPR
4338 || TREE_CODE (ubase
) == MINUS_EXPR
4339 || TREE_CODE (ubase
) == POINTER_PLUS_EXPR
)
4341 if (TREE_CODE (TREE_OPERAND (ubase
, 1)) == INTEGER_CST
)
4342 ubase
= TREE_OPERAND (ubase
, 0);
4345 /* Strips the constant part. */
4346 if (TREE_CODE (cbase
) == PLUS_EXPR
4347 || TREE_CODE (cbase
) == MINUS_EXPR
4348 || TREE_CODE (cbase
) == POINTER_PLUS_EXPR
)
4350 if (TREE_CODE (TREE_OPERAND (cbase
, 1)) == INTEGER_CST
)
4351 cbase
= TREE_OPERAND (cbase
, 0);
4356 if (((TREE_CODE (ubase
) == SSA_NAME
)
4357 || (TREE_CODE (ubase
) == ADDR_EXPR
4358 && is_gimple_min_invariant (ubase
)))
4359 && (TREE_CODE (cbase
) == INTEGER_CST
))
4362 if (((TREE_CODE (cbase
) == SSA_NAME
)
4363 || (TREE_CODE (cbase
) == ADDR_EXPR
4364 && is_gimple_min_invariant (cbase
)))
4365 && (TREE_CODE (ubase
) == INTEGER_CST
))
4371 if (operand_equal_p (ubase
, cbase
, 0))
4374 if (TREE_CODE (ubase
) == ADDR_EXPR
4375 && TREE_CODE (cbase
) == ADDR_EXPR
)
4379 usym
= TREE_OPERAND (ubase
, 0);
4380 csym
= TREE_OPERAND (cbase
, 0);
4381 if (TREE_CODE (usym
) == ARRAY_REF
)
4383 tree ind
= TREE_OPERAND (usym
, 1);
4384 if (TREE_CODE (ind
) == INTEGER_CST
4385 && tree_fits_shwi_p (ind
)
4386 && tree_to_shwi (ind
) == 0)
4387 usym
= TREE_OPERAND (usym
, 0);
4389 if (TREE_CODE (csym
) == ARRAY_REF
)
4391 tree ind
= TREE_OPERAND (csym
, 1);
4392 if (TREE_CODE (ind
) == INTEGER_CST
4393 && tree_fits_shwi_p (ind
)
4394 && tree_to_shwi (ind
) == 0)
4395 csym
= TREE_OPERAND (csym
, 0);
4397 if (operand_equal_p (usym
, csym
, 0))
4400 /* Now do more complex comparison */
4401 tree_to_aff_combination (ubase
, TREE_TYPE (ubase
), &ubase_aff
);
4402 tree_to_aff_combination (cbase
, TREE_TYPE (cbase
), &cbase_aff
);
4403 if (compare_aff_trees (&ubase_aff
, &cbase_aff
))
4407 tree_to_aff_combination (ub
, TREE_TYPE (ub
), &ubase_aff
);
4408 tree_to_aff_combination (cb
, TREE_TYPE (cb
), &cbase_aff
);
4410 aff_combination_scale (&cbase_aff
, -1 * ratio
);
4411 aff_combination_add (&ubase_aff
, &cbase_aff
);
4412 expr
= aff_combination_to_tree (&ubase_aff
);
4413 return get_expr_id (data
, expr
);
4418 /* Determines the cost of the computation by that USE is expressed
4419 from induction variable CAND. If ADDRESS_P is true, we just need
4420 to create an address from it, otherwise we want to get it into
4421 register. A set of invariants we depend on is stored in
4422 DEPENDS_ON. AT is the statement at that the value is computed.
4423 If CAN_AUTOINC is nonnull, use it to record whether autoinc
4424 addressing is likely. */
4427 get_computation_cost_at (struct ivopts_data
*data
,
4428 struct iv_use
*use
, struct iv_cand
*cand
,
4429 bool address_p
, bitmap
*depends_on
, gimple at
,
4433 tree ubase
= use
->iv
->base
, ustep
= use
->iv
->step
;
4435 tree utype
= TREE_TYPE (ubase
), ctype
;
4436 unsigned HOST_WIDE_INT cstepi
, offset
= 0;
4437 HOST_WIDE_INT ratio
, aratio
;
4438 bool var_present
, symbol_present
, stmt_is_after_inc
;
4441 bool speed
= optimize_bb_for_speed_p (gimple_bb (at
));
4442 machine_mode mem_mode
= (address_p
4443 ? TYPE_MODE (TREE_TYPE (*use
->op_p
))
4448 /* Only consider real candidates. */
4450 return infinite_cost
;
4452 cbase
= cand
->iv
->base
;
4453 cstep
= cand
->iv
->step
;
4454 ctype
= TREE_TYPE (cbase
);
4456 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
4458 /* We do not have a precision to express the values of use. */
4459 return infinite_cost
;
4463 || (use
->iv
->base_object
4464 && cand
->iv
->base_object
4465 && POINTER_TYPE_P (TREE_TYPE (use
->iv
->base_object
))
4466 && POINTER_TYPE_P (TREE_TYPE (cand
->iv
->base_object
))))
4468 /* Do not try to express address of an object with computation based
4469 on address of a different object. This may cause problems in rtl
4470 level alias analysis (that does not expect this to be happening,
4471 as this is illegal in C), and would be unlikely to be useful
4473 if (use
->iv
->base_object
4474 && cand
->iv
->base_object
4475 && !operand_equal_p (use
->iv
->base_object
, cand
->iv
->base_object
, 0))
4476 return infinite_cost
;
4479 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
4481 /* TODO -- add direct handling of this case. */
4485 /* CSTEPI is removed from the offset in case statement is after the
4486 increment. If the step is not constant, we use zero instead.
4487 This is a bit imprecise (there is the extra addition), but
4488 redundancy elimination is likely to transform the code so that
4489 it uses value of the variable before increment anyway,
4490 so it is not that much unrealistic. */
4491 if (cst_and_fits_in_hwi (cstep
))
4492 cstepi
= int_cst_value (cstep
);
4496 if (!constant_multiple_of (ustep
, cstep
, &rat
))
4497 return infinite_cost
;
4499 if (wi::fits_shwi_p (rat
))
4500 ratio
= rat
.to_shwi ();
4502 return infinite_cost
;
4505 ctype
= TREE_TYPE (cbase
);
4507 stmt_is_after_inc
= stmt_after_increment (data
->current_loop
, cand
, at
);
4509 /* use = ubase + ratio * (var - cbase). If either cbase is a constant
4510 or ratio == 1, it is better to handle this like
4512 ubase - ratio * cbase + ratio * var
4514 (also holds in the case ratio == -1, TODO. */
4516 if (cst_and_fits_in_hwi (cbase
))
4518 offset
= - ratio
* (unsigned HOST_WIDE_INT
) int_cst_value (cbase
);
4519 cost
= difference_cost (data
,
4520 ubase
, build_int_cst (utype
, 0),
4521 &symbol_present
, &var_present
, &offset
,
4523 cost
.cost
/= avg_loop_niter (data
->current_loop
);
4525 else if (ratio
== 1)
4527 tree real_cbase
= cbase
;
4529 /* Check to see if any adjustment is needed. */
4530 if (cstepi
== 0 && stmt_is_after_inc
)
4532 aff_tree real_cbase_aff
;
4535 tree_to_aff_combination (cbase
, TREE_TYPE (real_cbase
),
4537 tree_to_aff_combination (cstep
, TREE_TYPE (cstep
), &cstep_aff
);
4539 aff_combination_add (&real_cbase_aff
, &cstep_aff
);
4540 real_cbase
= aff_combination_to_tree (&real_cbase_aff
);
4543 cost
= difference_cost (data
,
4545 &symbol_present
, &var_present
, &offset
,
4547 cost
.cost
/= avg_loop_niter (data
->current_loop
);
4550 && !POINTER_TYPE_P (ctype
)
4551 && multiplier_allowed_in_address_p
4553 TYPE_ADDR_SPACE (TREE_TYPE (utype
))))
4556 = fold_build2 (MULT_EXPR
, ctype
, cbase
, build_int_cst (ctype
, ratio
));
4557 cost
= difference_cost (data
,
4559 &symbol_present
, &var_present
, &offset
,
4561 cost
.cost
/= avg_loop_niter (data
->current_loop
);
4565 cost
= force_var_cost (data
, cbase
, depends_on
);
4566 cost
= add_costs (cost
,
4567 difference_cost (data
,
4568 ubase
, build_int_cst (utype
, 0),
4569 &symbol_present
, &var_present
,
4570 &offset
, depends_on
));
4571 cost
.cost
/= avg_loop_niter (data
->current_loop
);
4572 cost
.cost
+= add_cost (data
->speed
, TYPE_MODE (ctype
));
4575 /* Set of invariants depended on by sub use has already been computed
4576 for the first use in the group. */
4580 if (depends_on
&& *depends_on
)
4581 bitmap_clear (*depends_on
);
4583 else if (inv_expr_id
)
4586 get_loop_invariant_expr_id (data
, ubase
, cbase
, ratio
, address_p
);
4587 /* Clear depends on. */
4588 if (*inv_expr_id
!= -1 && depends_on
&& *depends_on
)
4589 bitmap_clear (*depends_on
);
4592 /* If we are after the increment, the value of the candidate is higher by
4594 if (stmt_is_after_inc
)
4595 offset
-= ratio
* cstepi
;
4597 /* Now the computation is in shape symbol + var1 + const + ratio * var2.
4598 (symbol/var1/const parts may be omitted). If we are looking for an
4599 address, find the cost of addressing this. */
4601 return add_costs (cost
,
4602 get_address_cost (symbol_present
, var_present
,
4603 offset
, ratio
, cstepi
,
4605 TYPE_ADDR_SPACE (TREE_TYPE (utype
)),
4606 speed
, stmt_is_after_inc
,
4609 /* Otherwise estimate the costs for computing the expression. */
4610 if (!symbol_present
&& !var_present
&& !offset
)
4613 cost
.cost
+= mult_by_coeff_cost (ratio
, TYPE_MODE (ctype
), speed
);
4617 /* Symbol + offset should be compile-time computable so consider that they
4618 are added once to the variable, if present. */
4619 if (var_present
&& (symbol_present
|| offset
))
4620 cost
.cost
+= adjust_setup_cost (data
,
4621 add_cost (speed
, TYPE_MODE (ctype
)));
4623 /* Having offset does not affect runtime cost in case it is added to
4624 symbol, but it increases complexity. */
4628 cost
.cost
+= add_cost (speed
, TYPE_MODE (ctype
));
4630 aratio
= ratio
> 0 ? ratio
: -ratio
;
4632 cost
.cost
+= mult_by_coeff_cost (aratio
, TYPE_MODE (ctype
), speed
);
4637 *can_autoinc
= false;
4640 /* Just get the expression, expand it and measure the cost. */
4641 tree comp
= get_computation_at (data
->current_loop
, use
, cand
, at
);
4644 return infinite_cost
;
4647 comp
= build_simple_mem_ref (comp
);
4649 return new_cost (computation_cost (comp
, speed
), 0);
4653 /* Determines the cost of the computation by that USE is expressed
4654 from induction variable CAND. If ADDRESS_P is true, we just need
4655 to create an address from it, otherwise we want to get it into
4656 register. A set of invariants we depend on is stored in
4657 DEPENDS_ON. If CAN_AUTOINC is nonnull, use it to record whether
4658 autoinc addressing is likely. */
4661 get_computation_cost (struct ivopts_data
*data
,
4662 struct iv_use
*use
, struct iv_cand
*cand
,
4663 bool address_p
, bitmap
*depends_on
,
4664 bool *can_autoinc
, int *inv_expr_id
)
4666 return get_computation_cost_at (data
,
4667 use
, cand
, address_p
, depends_on
, use
->stmt
,
4668 can_autoinc
, inv_expr_id
);
4671 /* Determines cost of basing replacement of USE on CAND in a generic
4675 determine_use_iv_cost_generic (struct ivopts_data
*data
,
4676 struct iv_use
*use
, struct iv_cand
*cand
)
4680 int inv_expr_id
= -1;
4682 /* The simple case first -- if we need to express value of the preserved
4683 original biv, the cost is 0. This also prevents us from counting the
4684 cost of increment twice -- once at this use and once in the cost of
4686 if (cand
->pos
== IP_ORIGINAL
4687 && cand
->incremented_at
== use
->stmt
)
4689 set_use_iv_cost (data
, use
, cand
, no_cost
, NULL
, NULL_TREE
,
4694 cost
= get_computation_cost (data
, use
, cand
, false, &depends_on
,
4695 NULL
, &inv_expr_id
);
4697 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
, ERROR_MARK
,
4700 return !infinite_cost_p (cost
);
4703 /* Determines cost of basing replacement of USE on CAND in an address. */
4706 determine_use_iv_cost_address (struct ivopts_data
*data
,
4707 struct iv_use
*use
, struct iv_cand
*cand
)
4711 int inv_expr_id
= -1;
4712 struct iv_use
*sub_use
;
4714 comp_cost cost
= get_computation_cost (data
, use
, cand
, true, &depends_on
,
4715 &can_autoinc
, &inv_expr_id
);
4717 if (cand
->ainc_use
== use
)
4720 cost
.cost
-= cand
->cost_step
;
4721 /* If we generated the candidate solely for exploiting autoincrement
4722 opportunities, and it turns out it can't be used, set the cost to
4723 infinity to make sure we ignore it. */
4724 else if (cand
->pos
== IP_AFTER_USE
|| cand
->pos
== IP_BEFORE_USE
)
4725 cost
= infinite_cost
;
4727 for (sub_use
= use
->next
;
4728 sub_use
&& !infinite_cost_p (cost
);
4729 sub_use
= sub_use
->next
)
4731 sub_cost
= get_computation_cost (data
, sub_use
, cand
, true, &depends_on
,
4732 &can_autoinc
, &inv_expr_id
);
4733 cost
= add_costs (cost
, sub_cost
);
4736 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, NULL_TREE
, ERROR_MARK
,
4739 return !infinite_cost_p (cost
);
4742 /* Computes value of candidate CAND at position AT in iteration NITER, and
4743 stores it to VAL. */
4746 cand_value_at (struct loop
*loop
, struct iv_cand
*cand
, gimple at
, tree niter
,
4749 aff_tree step
, delta
, nit
;
4750 struct iv
*iv
= cand
->iv
;
4751 tree type
= TREE_TYPE (iv
->base
);
4752 tree steptype
= type
;
4753 if (POINTER_TYPE_P (type
))
4754 steptype
= sizetype
;
4755 steptype
= unsigned_type_for (type
);
4757 tree_to_aff_combination (iv
->step
, TREE_TYPE (iv
->step
), &step
);
4758 aff_combination_convert (&step
, steptype
);
4759 tree_to_aff_combination (niter
, TREE_TYPE (niter
), &nit
);
4760 aff_combination_convert (&nit
, steptype
);
4761 aff_combination_mult (&nit
, &step
, &delta
);
4762 if (stmt_after_increment (loop
, cand
, at
))
4763 aff_combination_add (&delta
, &step
);
4765 tree_to_aff_combination (iv
->base
, type
, val
);
4766 if (!POINTER_TYPE_P (type
))
4767 aff_combination_convert (val
, steptype
);
4768 aff_combination_add (val
, &delta
);
4771 /* Returns period of induction variable iv. */
4774 iv_period (struct iv
*iv
)
4776 tree step
= iv
->step
, period
, type
;
4779 gcc_assert (step
&& TREE_CODE (step
) == INTEGER_CST
);
4781 type
= unsigned_type_for (TREE_TYPE (step
));
4782 /* Period of the iv is lcm (step, type_range)/step -1,
4783 i.e., N*type_range/step - 1. Since type range is power
4784 of two, N == (step >> num_of_ending_zeros_binary (step),
4785 so the final result is
4787 (type_range >> num_of_ending_zeros_binary (step)) - 1
4790 pow2div
= num_ending_zeros (step
);
4792 period
= build_low_bits_mask (type
,
4793 (TYPE_PRECISION (type
)
4794 - tree_to_uhwi (pow2div
)));
4799 /* Returns the comparison operator used when eliminating the iv USE. */
4801 static enum tree_code
4802 iv_elimination_compare (struct ivopts_data
*data
, struct iv_use
*use
)
4804 struct loop
*loop
= data
->current_loop
;
4808 ex_bb
= gimple_bb (use
->stmt
);
4809 exit
= EDGE_SUCC (ex_bb
, 0);
4810 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
4811 exit
= EDGE_SUCC (ex_bb
, 1);
4813 return (exit
->flags
& EDGE_TRUE_VALUE
? EQ_EXPR
: NE_EXPR
);
4816 /* Returns true if we can prove that BASE - OFFSET does not overflow. For now,
4817 we only detect the situation that BASE = SOMETHING + OFFSET, where the
4818 calculation is performed in non-wrapping type.
4820 TODO: More generally, we could test for the situation that
4821 BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero.
4822 This would require knowing the sign of OFFSET. */
4825 difference_cannot_overflow_p (struct ivopts_data
*data
, tree base
, tree offset
)
4827 enum tree_code code
;
4829 aff_tree aff_e1
, aff_e2
, aff_offset
;
4831 if (!nowrap_type_p (TREE_TYPE (base
)))
4834 base
= expand_simple_operations (base
);
4836 if (TREE_CODE (base
) == SSA_NAME
)
4838 gimple stmt
= SSA_NAME_DEF_STMT (base
);
4840 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
4843 code
= gimple_assign_rhs_code (stmt
);
4844 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
4847 e1
= gimple_assign_rhs1 (stmt
);
4848 e2
= gimple_assign_rhs2 (stmt
);
4852 code
= TREE_CODE (base
);
4853 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
4855 e1
= TREE_OPERAND (base
, 0);
4856 e2
= TREE_OPERAND (base
, 1);
4859 /* Use affine expansion as deeper inspection to prove the equality. */
4860 tree_to_aff_combination_expand (e2
, TREE_TYPE (e2
),
4861 &aff_e2
, &data
->name_expansion_cache
);
4862 tree_to_aff_combination_expand (offset
, TREE_TYPE (offset
),
4863 &aff_offset
, &data
->name_expansion_cache
);
4864 aff_combination_scale (&aff_offset
, -1);
4868 aff_combination_add (&aff_e2
, &aff_offset
);
4869 if (aff_combination_zero_p (&aff_e2
))
4872 tree_to_aff_combination_expand (e1
, TREE_TYPE (e1
),
4873 &aff_e1
, &data
->name_expansion_cache
);
4874 aff_combination_add (&aff_e1
, &aff_offset
);
4875 return aff_combination_zero_p (&aff_e1
);
4877 case POINTER_PLUS_EXPR
:
4878 aff_combination_add (&aff_e2
, &aff_offset
);
4879 return aff_combination_zero_p (&aff_e2
);
4886 /* Tries to replace loop exit by one formulated in terms of a LT_EXPR
4887 comparison with CAND. NITER describes the number of iterations of
4888 the loops. If successful, the comparison in COMP_P is altered accordingly.
4890 We aim to handle the following situation:
4906 Here, the number of iterations of the loop is (a + 1 > b) ? 0 : b - a - 1.
4907 We aim to optimize this to
4915 while (p < p_0 - a + b);
4917 This preserves the correctness, since the pointer arithmetics does not
4918 overflow. More precisely:
4920 1) if a + 1 <= b, then p_0 - a + b is the final value of p, hence there is no
4921 overflow in computing it or the values of p.
4922 2) if a + 1 > b, then we need to verify that the expression p_0 - a does not
4923 overflow. To prove this, we use the fact that p_0 = base + a. */
4926 iv_elimination_compare_lt (struct ivopts_data
*data
,
4927 struct iv_cand
*cand
, enum tree_code
*comp_p
,
4928 struct tree_niter_desc
*niter
)
4930 tree cand_type
, a
, b
, mbz
, nit_type
= TREE_TYPE (niter
->niter
), offset
;
4931 struct aff_tree nit
, tmpa
, tmpb
;
4932 enum tree_code comp
;
4935 /* We need to know that the candidate induction variable does not overflow.
4936 While more complex analysis may be used to prove this, for now just
4937 check that the variable appears in the original program and that it
4938 is computed in a type that guarantees no overflows. */
4939 cand_type
= TREE_TYPE (cand
->iv
->base
);
4940 if (cand
->pos
!= IP_ORIGINAL
|| !nowrap_type_p (cand_type
))
4943 /* Make sure that the loop iterates till the loop bound is hit, as otherwise
4944 the calculation of the BOUND could overflow, making the comparison
4946 if (!data
->loop_single_exit_p
)
4949 /* We need to be able to decide whether candidate is increasing or decreasing
4950 in order to choose the right comparison operator. */
4951 if (!cst_and_fits_in_hwi (cand
->iv
->step
))
4953 step
= int_cst_value (cand
->iv
->step
);
4955 /* Check that the number of iterations matches the expected pattern:
4956 a + 1 > b ? 0 : b - a - 1. */
4957 mbz
= niter
->may_be_zero
;
4958 if (TREE_CODE (mbz
) == GT_EXPR
)
4960 /* Handle a + 1 > b. */
4961 tree op0
= TREE_OPERAND (mbz
, 0);
4962 if (TREE_CODE (op0
) == PLUS_EXPR
&& integer_onep (TREE_OPERAND (op0
, 1)))
4964 a
= TREE_OPERAND (op0
, 0);
4965 b
= TREE_OPERAND (mbz
, 1);
4970 else if (TREE_CODE (mbz
) == LT_EXPR
)
4972 tree op1
= TREE_OPERAND (mbz
, 1);
4974 /* Handle b < a + 1. */
4975 if (TREE_CODE (op1
) == PLUS_EXPR
&& integer_onep (TREE_OPERAND (op1
, 1)))
4977 a
= TREE_OPERAND (op1
, 0);
4978 b
= TREE_OPERAND (mbz
, 0);
4986 /* Expected number of iterations is B - A - 1. Check that it matches
4987 the actual number, i.e., that B - A - NITER = 1. */
4988 tree_to_aff_combination (niter
->niter
, nit_type
, &nit
);
4989 tree_to_aff_combination (fold_convert (nit_type
, a
), nit_type
, &tmpa
);
4990 tree_to_aff_combination (fold_convert (nit_type
, b
), nit_type
, &tmpb
);
4991 aff_combination_scale (&nit
, -1);
4992 aff_combination_scale (&tmpa
, -1);
4993 aff_combination_add (&tmpb
, &tmpa
);
4994 aff_combination_add (&tmpb
, &nit
);
4995 if (tmpb
.n
!= 0 || tmpb
.offset
!= 1)
4998 /* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not
5000 offset
= fold_build2 (MULT_EXPR
, TREE_TYPE (cand
->iv
->step
),
5002 fold_convert (TREE_TYPE (cand
->iv
->step
), a
));
5003 if (!difference_cannot_overflow_p (data
, cand
->iv
->base
, offset
))
5006 /* Determine the new comparison operator. */
5007 comp
= step
< 0 ? GT_EXPR
: LT_EXPR
;
5008 if (*comp_p
== NE_EXPR
)
5010 else if (*comp_p
== EQ_EXPR
)
5011 *comp_p
= invert_tree_comparison (comp
, false);
5018 /* Check whether it is possible to express the condition in USE by comparison
5019 of candidate CAND. If so, store the value compared with to BOUND, and the
5020 comparison operator to COMP. */
5023 may_eliminate_iv (struct ivopts_data
*data
,
5024 struct iv_use
*use
, struct iv_cand
*cand
, tree
*bound
,
5025 enum tree_code
*comp
)
5030 struct loop
*loop
= data
->current_loop
;
5032 struct tree_niter_desc
*desc
= NULL
;
5034 if (TREE_CODE (cand
->iv
->step
) != INTEGER_CST
)
5037 /* For now works only for exits that dominate the loop latch.
5038 TODO: extend to other conditions inside loop body. */
5039 ex_bb
= gimple_bb (use
->stmt
);
5040 if (use
->stmt
!= last_stmt (ex_bb
)
5041 || gimple_code (use
->stmt
) != GIMPLE_COND
5042 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, ex_bb
))
5045 exit
= EDGE_SUCC (ex_bb
, 0);
5046 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
5047 exit
= EDGE_SUCC (ex_bb
, 1);
5048 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
5051 desc
= niter_for_exit (data
, exit
);
5055 /* Determine whether we can use the variable to test the exit condition.
5056 This is the case iff the period of the induction variable is greater
5057 than the number of iterations for which the exit condition is true. */
5058 period
= iv_period (cand
->iv
);
5060 /* If the number of iterations is constant, compare against it directly. */
5061 if (TREE_CODE (desc
->niter
) == INTEGER_CST
)
5063 /* See cand_value_at. */
5064 if (stmt_after_increment (loop
, cand
, use
->stmt
))
5066 if (!tree_int_cst_lt (desc
->niter
, period
))
5071 if (tree_int_cst_lt (period
, desc
->niter
))
5076 /* If not, and if this is the only possible exit of the loop, see whether
5077 we can get a conservative estimate on the number of iterations of the
5078 entire loop and compare against that instead. */
5081 widest_int period_value
, max_niter
;
5083 max_niter
= desc
->max
;
5084 if (stmt_after_increment (loop
, cand
, use
->stmt
))
5086 period_value
= wi::to_widest (period
);
5087 if (wi::gtu_p (max_niter
, period_value
))
5089 /* See if we can take advantage of inferred loop bound information. */
5090 if (data
->loop_single_exit_p
)
5092 if (!max_loop_iterations (loop
, &max_niter
))
5094 /* The loop bound is already adjusted by adding 1. */
5095 if (wi::gtu_p (max_niter
, period_value
))
5103 cand_value_at (loop
, cand
, use
->stmt
, desc
->niter
, &bnd
);
5105 *bound
= fold_convert (TREE_TYPE (cand
->iv
->base
),
5106 aff_combination_to_tree (&bnd
));
5107 *comp
= iv_elimination_compare (data
, use
);
5109 /* It is unlikely that computing the number of iterations using division
5110 would be more profitable than keeping the original induction variable. */
5111 if (expression_expensive_p (*bound
))
5114 /* Sometimes, it is possible to handle the situation that the number of
5115 iterations may be zero unless additional assumtions by using <
5116 instead of != in the exit condition.
5118 TODO: we could also calculate the value MAY_BE_ZERO ? 0 : NITER and
5119 base the exit condition on it. However, that is often too
5121 if (!integer_zerop (desc
->may_be_zero
))
5122 return iv_elimination_compare_lt (data
, cand
, comp
, desc
);
5127 /* Calculates the cost of BOUND, if it is a PARM_DECL. A PARM_DECL must
5128 be copied, if is is used in the loop body and DATA->body_includes_call. */
5131 parm_decl_cost (struct ivopts_data
*data
, tree bound
)
5133 tree sbound
= bound
;
5134 STRIP_NOPS (sbound
);
5136 if (TREE_CODE (sbound
) == SSA_NAME
5137 && SSA_NAME_IS_DEFAULT_DEF (sbound
)
5138 && TREE_CODE (SSA_NAME_VAR (sbound
)) == PARM_DECL
5139 && data
->body_includes_call
)
5140 return COSTS_N_INSNS (1);
5145 /* Determines cost of basing replacement of USE on CAND in a condition. */
5148 determine_use_iv_cost_condition (struct ivopts_data
*data
,
5149 struct iv_use
*use
, struct iv_cand
*cand
)
5151 tree bound
= NULL_TREE
;
5153 bitmap depends_on_elim
= NULL
, depends_on_express
= NULL
, depends_on
;
5154 comp_cost elim_cost
, express_cost
, cost
, bound_cost
;
5156 int elim_inv_expr_id
= -1, express_inv_expr_id
= -1, inv_expr_id
;
5157 tree
*control_var
, *bound_cst
;
5158 enum tree_code comp
= ERROR_MARK
;
5160 /* Only consider real candidates. */
5163 set_use_iv_cost (data
, use
, cand
, infinite_cost
, NULL
, NULL_TREE
,
5168 /* Try iv elimination. */
5169 if (may_eliminate_iv (data
, use
, cand
, &bound
, &comp
))
5171 elim_cost
= force_var_cost (data
, bound
, &depends_on_elim
);
5172 if (elim_cost
.cost
== 0)
5173 elim_cost
.cost
= parm_decl_cost (data
, bound
);
5174 else if (TREE_CODE (bound
) == INTEGER_CST
)
5176 /* If we replace a loop condition 'i < n' with 'p < base + n',
5177 depends_on_elim will have 'base' and 'n' set, which implies
5178 that both 'base' and 'n' will be live during the loop. More likely,
5179 'base + n' will be loop invariant, resulting in only one live value
5180 during the loop. So in that case we clear depends_on_elim and set
5181 elim_inv_expr_id instead. */
5182 if (depends_on_elim
&& bitmap_count_bits (depends_on_elim
) > 1)
5184 elim_inv_expr_id
= get_expr_id (data
, bound
);
5185 bitmap_clear (depends_on_elim
);
5187 /* The bound is a loop invariant, so it will be only computed
5189 elim_cost
.cost
= adjust_setup_cost (data
, elim_cost
.cost
);
5192 elim_cost
= infinite_cost
;
5194 /* Try expressing the original giv. If it is compared with an invariant,
5195 note that we cannot get rid of it. */
5196 ok
= extract_cond_operands (data
, use
->stmt
, &control_var
, &bound_cst
,
5200 /* When the condition is a comparison of the candidate IV against
5201 zero, prefer this IV.
5203 TODO: The constant that we're subtracting from the cost should
5204 be target-dependent. This information should be added to the
5205 target costs for each backend. */
5206 if (!infinite_cost_p (elim_cost
) /* Do not try to decrease infinite! */
5207 && integer_zerop (*bound_cst
)
5208 && (operand_equal_p (*control_var
, cand
->var_after
, 0)
5209 || operand_equal_p (*control_var
, cand
->var_before
, 0)))
5210 elim_cost
.cost
-= 1;
5212 express_cost
= get_computation_cost (data
, use
, cand
, false,
5213 &depends_on_express
, NULL
,
5214 &express_inv_expr_id
);
5215 fd_ivopts_data
= data
;
5216 walk_tree (&cmp_iv
->base
, find_depends
, &depends_on_express
, NULL
);
5218 /* Count the cost of the original bound as well. */
5219 bound_cost
= force_var_cost (data
, *bound_cst
, NULL
);
5220 if (bound_cost
.cost
== 0)
5221 bound_cost
.cost
= parm_decl_cost (data
, *bound_cst
);
5222 else if (TREE_CODE (*bound_cst
) == INTEGER_CST
)
5223 bound_cost
.cost
= 0;
5224 express_cost
.cost
+= bound_cost
.cost
;
5226 /* Choose the better approach, preferring the eliminated IV. */
5227 if (compare_costs (elim_cost
, express_cost
) <= 0)
5230 depends_on
= depends_on_elim
;
5231 depends_on_elim
= NULL
;
5232 inv_expr_id
= elim_inv_expr_id
;
5236 cost
= express_cost
;
5237 depends_on
= depends_on_express
;
5238 depends_on_express
= NULL
;
5241 inv_expr_id
= express_inv_expr_id
;
5244 set_use_iv_cost (data
, use
, cand
, cost
, depends_on
, bound
, comp
, inv_expr_id
);
5246 if (depends_on_elim
)
5247 BITMAP_FREE (depends_on_elim
);
5248 if (depends_on_express
)
5249 BITMAP_FREE (depends_on_express
);
5251 return !infinite_cost_p (cost
);
5254 /* Determines cost of basing replacement of USE on CAND. Returns false
5255 if USE cannot be based on CAND. */
5258 determine_use_iv_cost (struct ivopts_data
*data
,
5259 struct iv_use
*use
, struct iv_cand
*cand
)
5263 case USE_NONLINEAR_EXPR
:
5264 return determine_use_iv_cost_generic (data
, use
, cand
);
5267 return determine_use_iv_cost_address (data
, use
, cand
);
5270 return determine_use_iv_cost_condition (data
, use
, cand
);
5277 /* Return true if get_computation_cost indicates that autoincrement is
5278 a possibility for the pair of USE and CAND, false otherwise. */
5281 autoinc_possible_for_pair (struct ivopts_data
*data
, struct iv_use
*use
,
5282 struct iv_cand
*cand
)
5288 if (use
->type
!= USE_ADDRESS
)
5291 cost
= get_computation_cost (data
, use
, cand
, true, &depends_on
,
5292 &can_autoinc
, NULL
);
5294 BITMAP_FREE (depends_on
);
5296 return !infinite_cost_p (cost
) && can_autoinc
;
5299 /* Examine IP_ORIGINAL candidates to see if they are incremented next to a
5300 use that allows autoincrement, and set their AINC_USE if possible. */
5303 set_autoinc_for_original_candidates (struct ivopts_data
*data
)
5307 for (i
= 0; i
< n_iv_cands (data
); i
++)
5309 struct iv_cand
*cand
= iv_cand (data
, i
);
5310 struct iv_use
*closest_before
= NULL
;
5311 struct iv_use
*closest_after
= NULL
;
5312 if (cand
->pos
!= IP_ORIGINAL
)
5315 for (j
= 0; j
< n_iv_uses (data
); j
++)
5317 struct iv_use
*use
= iv_use (data
, j
);
5318 unsigned uid
= gimple_uid (use
->stmt
);
5320 if (gimple_bb (use
->stmt
) != gimple_bb (cand
->incremented_at
))
5323 if (uid
< gimple_uid (cand
->incremented_at
)
5324 && (closest_before
== NULL
5325 || uid
> gimple_uid (closest_before
->stmt
)))
5326 closest_before
= use
;
5328 if (uid
> gimple_uid (cand
->incremented_at
)
5329 && (closest_after
== NULL
5330 || uid
< gimple_uid (closest_after
->stmt
)))
5331 closest_after
= use
;
5334 if (closest_before
!= NULL
5335 && autoinc_possible_for_pair (data
, closest_before
, cand
))
5336 cand
->ainc_use
= closest_before
;
5337 else if (closest_after
!= NULL
5338 && autoinc_possible_for_pair (data
, closest_after
, cand
))
5339 cand
->ainc_use
= closest_after
;
5343 /* Finds the candidates for the induction variables. */
5346 find_iv_candidates (struct ivopts_data
*data
)
5348 /* Add commonly used ivs. */
5349 add_standard_iv_candidates (data
);
5351 /* Add old induction variables. */
5352 add_old_ivs_candidates (data
);
5354 /* Add induction variables derived from uses. */
5355 add_derived_ivs_candidates (data
);
5357 set_autoinc_for_original_candidates (data
);
5359 /* Record the important candidates. */
5360 record_important_candidates (data
);
5363 /* Determines costs of basing the use of the iv on an iv candidate. */
5366 determine_use_iv_costs (struct ivopts_data
*data
)
5370 struct iv_cand
*cand
;
5371 bitmap to_clear
= BITMAP_ALLOC (NULL
);
5373 alloc_use_cost_map (data
);
5375 for (i
= 0; i
< n_iv_uses (data
); i
++)
5377 use
= iv_use (data
, i
);
5379 if (data
->consider_all_candidates
)
5381 for (j
= 0; j
< n_iv_cands (data
); j
++)
5383 cand
= iv_cand (data
, j
);
5384 determine_use_iv_cost (data
, use
, cand
);
5391 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, j
, bi
)
5393 cand
= iv_cand (data
, j
);
5394 if (!determine_use_iv_cost (data
, use
, cand
))
5395 bitmap_set_bit (to_clear
, j
);
5398 /* Remove the candidates for that the cost is infinite from
5399 the list of related candidates. */
5400 bitmap_and_compl_into (use
->related_cands
, to_clear
);
5401 bitmap_clear (to_clear
);
5405 BITMAP_FREE (to_clear
);
5407 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5409 fprintf (dump_file
, "Use-candidate costs:\n");
5411 for (i
= 0; i
< n_iv_uses (data
); i
++)
5413 use
= iv_use (data
, i
);
5415 fprintf (dump_file
, "Use %d:\n", i
);
5416 fprintf (dump_file
, " cand\tcost\tcompl.\tdepends on\n");
5417 for (j
= 0; j
< use
->n_map_members
; j
++)
5419 if (!use
->cost_map
[j
].cand
5420 || infinite_cost_p (use
->cost_map
[j
].cost
))
5423 fprintf (dump_file
, " %d\t%d\t%d\t",
5424 use
->cost_map
[j
].cand
->id
,
5425 use
->cost_map
[j
].cost
.cost
,
5426 use
->cost_map
[j
].cost
.complexity
);
5427 if (use
->cost_map
[j
].depends_on
)
5428 bitmap_print (dump_file
,
5429 use
->cost_map
[j
].depends_on
, "","");
5430 if (use
->cost_map
[j
].inv_expr_id
!= -1)
5431 fprintf (dump_file
, " inv_expr:%d", use
->cost_map
[j
].inv_expr_id
);
5432 fprintf (dump_file
, "\n");
5435 fprintf (dump_file
, "\n");
5437 fprintf (dump_file
, "\n");
5441 /* Determines cost of the candidate CAND. */
5444 determine_iv_cost (struct ivopts_data
*data
, struct iv_cand
*cand
)
5446 comp_cost cost_base
;
5447 unsigned cost
, cost_step
;
5456 /* There are two costs associated with the candidate -- its increment
5457 and its initialization. The second is almost negligible for any loop
5458 that rolls enough, so we take it just very little into account. */
5460 base
= cand
->iv
->base
;
5461 cost_base
= force_var_cost (data
, base
, NULL
);
5462 /* It will be exceptional that the iv register happens to be initialized with
5463 the proper value at no cost. In general, there will at least be a regcopy
5465 if (cost_base
.cost
== 0)
5466 cost_base
.cost
= COSTS_N_INSNS (1);
5467 cost_step
= add_cost (data
->speed
, TYPE_MODE (TREE_TYPE (base
)));
5469 cost
= cost_step
+ adjust_setup_cost (data
, cost_base
.cost
);
5471 /* Prefer the original ivs unless we may gain something by replacing it.
5472 The reason is to make debugging simpler; so this is not relevant for
5473 artificial ivs created by other optimization passes. */
5474 if (cand
->pos
!= IP_ORIGINAL
5475 || !SSA_NAME_VAR (cand
->var_before
)
5476 || DECL_ARTIFICIAL (SSA_NAME_VAR (cand
->var_before
)))
5479 /* Prefer not to insert statements into latch unless there are some
5480 already (so that we do not create unnecessary jumps). */
5481 if (cand
->pos
== IP_END
5482 && empty_block_p (ip_end_pos (data
->current_loop
)))
5486 cand
->cost_step
= cost_step
;
5489 /* Determines costs of computation of the candidates. */
5492 determine_iv_costs (struct ivopts_data
*data
)
5496 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5498 fprintf (dump_file
, "Candidate costs:\n");
5499 fprintf (dump_file
, " cand\tcost\n");
5502 for (i
= 0; i
< n_iv_cands (data
); i
++)
5504 struct iv_cand
*cand
= iv_cand (data
, i
);
5506 determine_iv_cost (data
, cand
);
5508 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5509 fprintf (dump_file
, " %d\t%d\n", i
, cand
->cost
);
5512 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5513 fprintf (dump_file
, "\n");
5516 /* Calculates cost for having SIZE induction variables. */
5519 ivopts_global_cost_for_size (struct ivopts_data
*data
, unsigned size
)
5521 /* We add size to the cost, so that we prefer eliminating ivs
5523 return size
+ estimate_reg_pressure_cost (size
, data
->regs_used
, data
->speed
,
5524 data
->body_includes_call
);
5527 /* For each size of the induction variable set determine the penalty. */
5530 determine_set_costs (struct ivopts_data
*data
)
5536 struct loop
*loop
= data
->current_loop
;
5539 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5541 fprintf (dump_file
, "Global costs:\n");
5542 fprintf (dump_file
, " target_avail_regs %d\n", target_avail_regs
);
5543 fprintf (dump_file
, " target_clobbered_regs %d\n", target_clobbered_regs
);
5544 fprintf (dump_file
, " target_reg_cost %d\n", target_reg_cost
[data
->speed
]);
5545 fprintf (dump_file
, " target_spill_cost %d\n", target_spill_cost
[data
->speed
]);
5549 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
5552 op
= PHI_RESULT (phi
);
5554 if (virtual_operand_p (op
))
5557 if (get_iv (data
, op
))
5563 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
5565 struct version_info
*info
= ver_info (data
, j
);
5567 if (info
->inv_id
&& info
->has_nonlin_use
)
5571 data
->regs_used
= n
;
5572 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5573 fprintf (dump_file
, " regs_used %d\n", n
);
5575 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5577 fprintf (dump_file
, " cost for size:\n");
5578 fprintf (dump_file
, " ivs\tcost\n");
5579 for (j
= 0; j
<= 2 * target_avail_regs
; j
++)
5580 fprintf (dump_file
, " %d\t%d\n", j
,
5581 ivopts_global_cost_for_size (data
, j
));
5582 fprintf (dump_file
, "\n");
5586 /* Returns true if A is a cheaper cost pair than B. */
5589 cheaper_cost_pair (struct cost_pair
*a
, struct cost_pair
*b
)
5599 cmp
= compare_costs (a
->cost
, b
->cost
);
5606 /* In case the costs are the same, prefer the cheaper candidate. */
5607 if (a
->cand
->cost
< b
->cand
->cost
)
5614 /* Returns candidate by that USE is expressed in IVS. */
5616 static struct cost_pair
*
5617 iv_ca_cand_for_use (struct iv_ca
*ivs
, struct iv_use
*use
)
5619 return ivs
->cand_for_use
[use
->id
];
5622 /* Computes the cost field of IVS structure. */
5625 iv_ca_recount_cost (struct ivopts_data
*data
, struct iv_ca
*ivs
)
5627 comp_cost cost
= ivs
->cand_use_cost
;
5629 cost
.cost
+= ivs
->cand_cost
;
5631 cost
.cost
+= ivopts_global_cost_for_size (data
,
5632 ivs
->n_regs
+ ivs
->num_used_inv_expr
);
5637 /* Remove invariants in set INVS to set IVS. */
5640 iv_ca_set_remove_invariants (struct iv_ca
*ivs
, bitmap invs
)
5648 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
5650 ivs
->n_invariant_uses
[iid
]--;
5651 if (ivs
->n_invariant_uses
[iid
] == 0)
5656 /* Set USE not to be expressed by any candidate in IVS. */
5659 iv_ca_set_no_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5662 unsigned uid
= use
->id
, cid
;
5663 struct cost_pair
*cp
;
5665 cp
= ivs
->cand_for_use
[uid
];
5671 ivs
->cand_for_use
[uid
] = NULL
;
5672 ivs
->n_cand_uses
[cid
]--;
5674 if (ivs
->n_cand_uses
[cid
] == 0)
5676 bitmap_clear_bit (ivs
->cands
, cid
);
5677 /* Do not count the pseudocandidates. */
5681 ivs
->cand_cost
-= cp
->cand
->cost
;
5683 iv_ca_set_remove_invariants (ivs
, cp
->cand
->depends_on
);
5686 ivs
->cand_use_cost
= sub_costs (ivs
->cand_use_cost
, cp
->cost
);
5688 iv_ca_set_remove_invariants (ivs
, cp
->depends_on
);
5690 if (cp
->inv_expr_id
!= -1)
5692 ivs
->used_inv_expr
[cp
->inv_expr_id
]--;
5693 if (ivs
->used_inv_expr
[cp
->inv_expr_id
] == 0)
5694 ivs
->num_used_inv_expr
--;
5696 iv_ca_recount_cost (data
, ivs
);
5699 /* Add invariants in set INVS to set IVS. */
5702 iv_ca_set_add_invariants (struct iv_ca
*ivs
, bitmap invs
)
5710 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
5712 ivs
->n_invariant_uses
[iid
]++;
5713 if (ivs
->n_invariant_uses
[iid
] == 1)
5718 /* Set cost pair for USE in set IVS to CP. */
5721 iv_ca_set_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5722 struct iv_use
*use
, struct cost_pair
*cp
)
5724 unsigned uid
= use
->id
, cid
;
5726 if (ivs
->cand_for_use
[uid
] == cp
)
5729 if (ivs
->cand_for_use
[uid
])
5730 iv_ca_set_no_cp (data
, ivs
, use
);
5737 ivs
->cand_for_use
[uid
] = cp
;
5738 ivs
->n_cand_uses
[cid
]++;
5739 if (ivs
->n_cand_uses
[cid
] == 1)
5741 bitmap_set_bit (ivs
->cands
, cid
);
5742 /* Do not count the pseudocandidates. */
5746 ivs
->cand_cost
+= cp
->cand
->cost
;
5748 iv_ca_set_add_invariants (ivs
, cp
->cand
->depends_on
);
5751 ivs
->cand_use_cost
= add_costs (ivs
->cand_use_cost
, cp
->cost
);
5752 iv_ca_set_add_invariants (ivs
, cp
->depends_on
);
5754 if (cp
->inv_expr_id
!= -1)
5756 ivs
->used_inv_expr
[cp
->inv_expr_id
]++;
5757 if (ivs
->used_inv_expr
[cp
->inv_expr_id
] == 1)
5758 ivs
->num_used_inv_expr
++;
5760 iv_ca_recount_cost (data
, ivs
);
5764 /* Extend set IVS by expressing USE by some of the candidates in it
5765 if possible. Consider all important candidates if candidates in
5766 set IVS don't give any result. */
5769 iv_ca_add_use (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5772 struct cost_pair
*best_cp
= NULL
, *cp
;
5775 struct iv_cand
*cand
;
5777 gcc_assert (ivs
->upto
>= use
->id
);
5781 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
5783 cand
= iv_cand (data
, i
);
5784 cp
= get_use_iv_cost (data
, use
, cand
);
5785 if (cheaper_cost_pair (cp
, best_cp
))
5789 if (best_cp
== NULL
)
5791 EXECUTE_IF_SET_IN_BITMAP (data
->important_candidates
, 0, i
, bi
)
5793 cand
= iv_cand (data
, i
);
5794 cp
= get_use_iv_cost (data
, use
, cand
);
5795 if (cheaper_cost_pair (cp
, best_cp
))
5800 iv_ca_set_cp (data
, ivs
, use
, best_cp
);
5803 /* Get cost for assignment IVS. */
5806 iv_ca_cost (struct iv_ca
*ivs
)
5808 /* This was a conditional expression but it triggered a bug in
5811 return infinite_cost
;
5816 /* Returns true if all dependences of CP are among invariants in IVS. */
5819 iv_ca_has_deps (struct iv_ca
*ivs
, struct cost_pair
*cp
)
5824 if (!cp
->depends_on
)
5827 EXECUTE_IF_SET_IN_BITMAP (cp
->depends_on
, 0, i
, bi
)
5829 if (ivs
->n_invariant_uses
[i
] == 0)
5836 /* Creates change of expressing USE by NEW_CP instead of OLD_CP and chains
5837 it before NEXT_CHANGE. */
5839 static struct iv_ca_delta
*
5840 iv_ca_delta_add (struct iv_use
*use
, struct cost_pair
*old_cp
,
5841 struct cost_pair
*new_cp
, struct iv_ca_delta
*next_change
)
5843 struct iv_ca_delta
*change
= XNEW (struct iv_ca_delta
);
5846 change
->old_cp
= old_cp
;
5847 change
->new_cp
= new_cp
;
5848 change
->next_change
= next_change
;
5853 /* Joins two lists of changes L1 and L2. Destructive -- old lists
5856 static struct iv_ca_delta
*
5857 iv_ca_delta_join (struct iv_ca_delta
*l1
, struct iv_ca_delta
*l2
)
5859 struct iv_ca_delta
*last
;
5867 for (last
= l1
; last
->next_change
; last
= last
->next_change
)
5869 last
->next_change
= l2
;
5874 /* Reverse the list of changes DELTA, forming the inverse to it. */
5876 static struct iv_ca_delta
*
5877 iv_ca_delta_reverse (struct iv_ca_delta
*delta
)
5879 struct iv_ca_delta
*act
, *next
, *prev
= NULL
;
5881 for (act
= delta
; act
; act
= next
)
5883 next
= act
->next_change
;
5884 act
->next_change
= prev
;
5887 std::swap (act
->old_cp
, act
->new_cp
);
5893 /* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
5894 reverted instead. */
5897 iv_ca_delta_commit (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5898 struct iv_ca_delta
*delta
, bool forward
)
5900 struct cost_pair
*from
, *to
;
5901 struct iv_ca_delta
*act
;
5904 delta
= iv_ca_delta_reverse (delta
);
5906 for (act
= delta
; act
; act
= act
->next_change
)
5910 gcc_assert (iv_ca_cand_for_use (ivs
, act
->use
) == from
);
5911 iv_ca_set_cp (data
, ivs
, act
->use
, to
);
5915 iv_ca_delta_reverse (delta
);
5918 /* Returns true if CAND is used in IVS. */
5921 iv_ca_cand_used_p (struct iv_ca
*ivs
, struct iv_cand
*cand
)
5923 return ivs
->n_cand_uses
[cand
->id
] > 0;
5926 /* Returns number of induction variable candidates in the set IVS. */
5929 iv_ca_n_cands (struct iv_ca
*ivs
)
5931 return ivs
->n_cands
;
5934 /* Free the list of changes DELTA. */
5937 iv_ca_delta_free (struct iv_ca_delta
**delta
)
5939 struct iv_ca_delta
*act
, *next
;
5941 for (act
= *delta
; act
; act
= next
)
5943 next
= act
->next_change
;
5950 /* Allocates new iv candidates assignment. */
5952 static struct iv_ca
*
5953 iv_ca_new (struct ivopts_data
*data
)
5955 struct iv_ca
*nw
= XNEW (struct iv_ca
);
5959 nw
->cand_for_use
= XCNEWVEC (struct cost_pair
*, n_iv_uses (data
));
5960 nw
->n_cand_uses
= XCNEWVEC (unsigned, n_iv_cands (data
));
5961 nw
->cands
= BITMAP_ALLOC (NULL
);
5964 nw
->cand_use_cost
= no_cost
;
5966 nw
->n_invariant_uses
= XCNEWVEC (unsigned, data
->max_inv_id
+ 1);
5968 nw
->used_inv_expr
= XCNEWVEC (unsigned, data
->inv_expr_id
+ 1);
5969 nw
->num_used_inv_expr
= 0;
5974 /* Free memory occupied by the set IVS. */
5977 iv_ca_free (struct iv_ca
**ivs
)
5979 free ((*ivs
)->cand_for_use
);
5980 free ((*ivs
)->n_cand_uses
);
5981 BITMAP_FREE ((*ivs
)->cands
);
5982 free ((*ivs
)->n_invariant_uses
);
5983 free ((*ivs
)->used_inv_expr
);
5988 /* Dumps IVS to FILE. */
5991 iv_ca_dump (struct ivopts_data
*data
, FILE *file
, struct iv_ca
*ivs
)
5993 const char *pref
= " invariants ";
5995 comp_cost cost
= iv_ca_cost (ivs
);
5997 fprintf (file
, " cost: %d (complexity %d)\n", cost
.cost
, cost
.complexity
);
5998 fprintf (file
, " cand_cost: %d\n cand_use_cost: %d (complexity %d)\n",
5999 ivs
->cand_cost
, ivs
->cand_use_cost
.cost
, ivs
->cand_use_cost
.complexity
);
6000 bitmap_print (file
, ivs
->cands
, " candidates: ","\n");
6002 for (i
= 0; i
< ivs
->upto
; i
++)
6004 struct iv_use
*use
= iv_use (data
, i
);
6005 struct cost_pair
*cp
= iv_ca_cand_for_use (ivs
, use
);
6007 fprintf (file
, " use:%d --> iv_cand:%d, cost=(%d,%d)\n",
6008 use
->id
, cp
->cand
->id
, cp
->cost
.cost
, cp
->cost
.complexity
);
6010 fprintf (file
, " use:%d --> ??\n", use
->id
);
6013 for (i
= 1; i
<= data
->max_inv_id
; i
++)
6014 if (ivs
->n_invariant_uses
[i
])
6016 fprintf (file
, "%s%d", pref
, i
);
6019 fprintf (file
, "\n\n");
6022 /* Try changing candidate in IVS to CAND for each use. Return cost of the
6023 new set, and store differences in DELTA. Number of induction variables
6024 in the new set is stored to N_IVS. MIN_NCAND is a flag. When it is true
6025 the function will try to find a solution with mimimal iv candidates. */
6028 iv_ca_extend (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6029 struct iv_cand
*cand
, struct iv_ca_delta
**delta
,
6030 unsigned *n_ivs
, bool min_ncand
)
6035 struct cost_pair
*old_cp
, *new_cp
;
6038 for (i
= 0; i
< ivs
->upto
; i
++)
6040 use
= iv_use (data
, i
);
6041 old_cp
= iv_ca_cand_for_use (ivs
, use
);
6044 && old_cp
->cand
== cand
)
6047 new_cp
= get_use_iv_cost (data
, use
, cand
);
6051 if (!min_ncand
&& !iv_ca_has_deps (ivs
, new_cp
))
6054 if (!min_ncand
&& !cheaper_cost_pair (new_cp
, old_cp
))
6057 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
6060 iv_ca_delta_commit (data
, ivs
, *delta
, true);
6061 cost
= iv_ca_cost (ivs
);
6063 *n_ivs
= iv_ca_n_cands (ivs
);
6064 iv_ca_delta_commit (data
, ivs
, *delta
, false);
6069 /* Try narrowing set IVS by removing CAND. Return the cost of
6070 the new set and store the differences in DELTA. START is
6071 the candidate with which we start narrowing. */
6074 iv_ca_narrow (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6075 struct iv_cand
*cand
, struct iv_cand
*start
,
6076 struct iv_ca_delta
**delta
)
6080 struct cost_pair
*old_cp
, *new_cp
, *cp
;
6082 struct iv_cand
*cnd
;
6083 comp_cost cost
, best_cost
, acost
;
6086 for (i
= 0; i
< n_iv_uses (data
); i
++)
6088 use
= iv_use (data
, i
);
6090 old_cp
= iv_ca_cand_for_use (ivs
, use
);
6091 if (old_cp
->cand
!= cand
)
6094 best_cost
= iv_ca_cost (ivs
);
6095 /* Start narrowing with START. */
6096 new_cp
= get_use_iv_cost (data
, use
, start
);
6098 if (data
->consider_all_candidates
)
6100 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, ci
, bi
)
6102 if (ci
== cand
->id
|| (start
&& ci
== start
->id
))
6105 cnd
= iv_cand (data
, ci
);
6107 cp
= get_use_iv_cost (data
, use
, cnd
);
6111 iv_ca_set_cp (data
, ivs
, use
, cp
);
6112 acost
= iv_ca_cost (ivs
);
6114 if (compare_costs (acost
, best_cost
) < 0)
6123 EXECUTE_IF_AND_IN_BITMAP (use
->related_cands
, ivs
->cands
, 0, ci
, bi
)
6125 if (ci
== cand
->id
|| (start
&& ci
== start
->id
))
6128 cnd
= iv_cand (data
, ci
);
6130 cp
= get_use_iv_cost (data
, use
, cnd
);
6134 iv_ca_set_cp (data
, ivs
, use
, cp
);
6135 acost
= iv_ca_cost (ivs
);
6137 if (compare_costs (acost
, best_cost
) < 0)
6144 /* Restore to old cp for use. */
6145 iv_ca_set_cp (data
, ivs
, use
, old_cp
);
6149 iv_ca_delta_free (delta
);
6150 return infinite_cost
;
6153 *delta
= iv_ca_delta_add (use
, old_cp
, new_cp
, *delta
);
6156 iv_ca_delta_commit (data
, ivs
, *delta
, true);
6157 cost
= iv_ca_cost (ivs
);
6158 iv_ca_delta_commit (data
, ivs
, *delta
, false);
6163 /* Try optimizing the set of candidates IVS by removing candidates different
6164 from to EXCEPT_CAND from it. Return cost of the new set, and store
6165 differences in DELTA. */
6168 iv_ca_prune (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6169 struct iv_cand
*except_cand
, struct iv_ca_delta
**delta
)
6172 struct iv_ca_delta
*act_delta
, *best_delta
;
6174 comp_cost best_cost
, acost
;
6175 struct iv_cand
*cand
;
6178 best_cost
= iv_ca_cost (ivs
);
6180 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
6182 cand
= iv_cand (data
, i
);
6184 if (cand
== except_cand
)
6187 acost
= iv_ca_narrow (data
, ivs
, cand
, except_cand
, &act_delta
);
6189 if (compare_costs (acost
, best_cost
) < 0)
6192 iv_ca_delta_free (&best_delta
);
6193 best_delta
= act_delta
;
6196 iv_ca_delta_free (&act_delta
);
6205 /* Recurse to possibly remove other unnecessary ivs. */
6206 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
6207 best_cost
= iv_ca_prune (data
, ivs
, except_cand
, delta
);
6208 iv_ca_delta_commit (data
, ivs
, best_delta
, false);
6209 *delta
= iv_ca_delta_join (best_delta
, *delta
);
6213 /* Check if CAND_IDX is a candidate other than OLD_CAND and has
6214 cheaper local cost for USE than BEST_CP. Return pointer to
6215 the corresponding cost_pair, otherwise just return BEST_CP. */
6217 static struct cost_pair
*
6218 cheaper_cost_with_cand (struct ivopts_data
*data
, struct iv_use
*use
,
6219 unsigned int cand_idx
, struct iv_cand
*old_cand
,
6220 struct cost_pair
*best_cp
)
6222 struct iv_cand
*cand
;
6223 struct cost_pair
*cp
;
6225 gcc_assert (old_cand
!= NULL
&& best_cp
!= NULL
);
6226 if (cand_idx
== old_cand
->id
)
6229 cand
= iv_cand (data
, cand_idx
);
6230 cp
= get_use_iv_cost (data
, use
, cand
);
6231 if (cp
!= NULL
&& cheaper_cost_pair (cp
, best_cp
))
6237 /* Try breaking local optimal fixed-point for IVS by replacing candidates
6238 which are used by more than one iv uses. For each of those candidates,
6239 this function tries to represent iv uses under that candidate using
6240 other ones with lower local cost, then tries to prune the new set.
6241 If the new set has lower cost, It returns the new cost after recording
6242 candidate replacement in list DELTA. */
6245 iv_ca_replace (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6246 struct iv_ca_delta
**delta
)
6248 bitmap_iterator bi
, bj
;
6249 unsigned int i
, j
, k
;
6251 struct iv_cand
*cand
;
6252 comp_cost orig_cost
, acost
;
6253 struct iv_ca_delta
*act_delta
, *tmp_delta
;
6254 struct cost_pair
*old_cp
, *best_cp
= NULL
;
6257 orig_cost
= iv_ca_cost (ivs
);
6259 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
6261 if (ivs
->n_cand_uses
[i
] == 1
6262 || ivs
->n_cand_uses
[i
] > ALWAYS_PRUNE_CAND_SET_BOUND
)
6265 cand
= iv_cand (data
, i
);
6268 /* Represent uses under current candidate using other ones with
6269 lower local cost. */
6270 for (j
= 0; j
< ivs
->upto
; j
++)
6272 use
= iv_use (data
, j
);
6273 old_cp
= iv_ca_cand_for_use (ivs
, use
);
6275 if (old_cp
->cand
!= cand
)
6279 if (data
->consider_all_candidates
)
6280 for (k
= 0; k
< n_iv_cands (data
); k
++)
6281 best_cp
= cheaper_cost_with_cand (data
, use
, k
,
6282 old_cp
->cand
, best_cp
);
6284 EXECUTE_IF_SET_IN_BITMAP (use
->related_cands
, 0, k
, bj
)
6285 best_cp
= cheaper_cost_with_cand (data
, use
, k
,
6286 old_cp
->cand
, best_cp
);
6288 if (best_cp
== old_cp
)
6291 act_delta
= iv_ca_delta_add (use
, old_cp
, best_cp
, act_delta
);
6293 /* No need for further prune. */
6297 /* Prune the new candidate set. */
6298 iv_ca_delta_commit (data
, ivs
, act_delta
, true);
6299 acost
= iv_ca_prune (data
, ivs
, NULL
, &tmp_delta
);
6300 iv_ca_delta_commit (data
, ivs
, act_delta
, false);
6301 act_delta
= iv_ca_delta_join (act_delta
, tmp_delta
);
6303 if (compare_costs (acost
, orig_cost
) < 0)
6309 iv_ca_delta_free (&act_delta
);
6315 /* Tries to extend the sets IVS in the best possible way in order
6316 to express the USE. If ORIGINALP is true, prefer candidates from
6317 the original set of IVs, otherwise favor important candidates not
6318 based on any memory object. */
6321 try_add_cand_for (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6322 struct iv_use
*use
, bool originalp
)
6324 comp_cost best_cost
, act_cost
;
6327 struct iv_cand
*cand
;
6328 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
;
6329 struct cost_pair
*cp
;
6331 iv_ca_add_use (data
, ivs
, use
);
6332 best_cost
= iv_ca_cost (ivs
);
6333 cp
= iv_ca_cand_for_use (ivs
, use
);
6336 best_delta
= iv_ca_delta_add (use
, NULL
, cp
, NULL
);
6337 iv_ca_set_no_cp (data
, ivs
, use
);
6340 /* If ORIGINALP is true, try to find the original IV for the use. Otherwise
6341 first try important candidates not based on any memory object. Only if
6342 this fails, try the specific ones. Rationale -- in loops with many
6343 variables the best choice often is to use just one generic biv. If we
6344 added here many ivs specific to the uses, the optimization algorithm later
6345 would be likely to get stuck in a local minimum, thus causing us to create
6346 too many ivs. The approach from few ivs to more seems more likely to be
6347 successful -- starting from few ivs, replacing an expensive use by a
6348 specific iv should always be a win. */
6349 EXECUTE_IF_SET_IN_BITMAP (data
->important_candidates
, 0, i
, bi
)
6351 cand
= iv_cand (data
, i
);
6353 if (originalp
&& cand
->pos
!=IP_ORIGINAL
)
6356 if (!originalp
&& cand
->iv
->base_object
!= NULL_TREE
)
6359 if (iv_ca_cand_used_p (ivs
, cand
))
6362 cp
= get_use_iv_cost (data
, use
, cand
);
6366 iv_ca_set_cp (data
, ivs
, use
, cp
);
6367 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
,
6369 iv_ca_set_no_cp (data
, ivs
, use
);
6370 act_delta
= iv_ca_delta_add (use
, NULL
, cp
, act_delta
);
6372 if (compare_costs (act_cost
, best_cost
) < 0)
6374 best_cost
= act_cost
;
6376 iv_ca_delta_free (&best_delta
);
6377 best_delta
= act_delta
;
6380 iv_ca_delta_free (&act_delta
);
6383 if (infinite_cost_p (best_cost
))
6385 for (i
= 0; i
< use
->n_map_members
; i
++)
6387 cp
= use
->cost_map
+ i
;
6392 /* Already tried this. */
6393 if (cand
->important
)
6395 if (originalp
&& cand
->pos
== IP_ORIGINAL
)
6397 if (!originalp
&& cand
->iv
->base_object
== NULL_TREE
)
6401 if (iv_ca_cand_used_p (ivs
, cand
))
6405 iv_ca_set_cp (data
, ivs
, use
, cp
);
6406 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
, true);
6407 iv_ca_set_no_cp (data
, ivs
, use
);
6408 act_delta
= iv_ca_delta_add (use
, iv_ca_cand_for_use (ivs
, use
),
6411 if (compare_costs (act_cost
, best_cost
) < 0)
6413 best_cost
= act_cost
;
6416 iv_ca_delta_free (&best_delta
);
6417 best_delta
= act_delta
;
6420 iv_ca_delta_free (&act_delta
);
6424 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
6425 iv_ca_delta_free (&best_delta
);
6427 return !infinite_cost_p (best_cost
);
6430 /* Finds an initial assignment of candidates to uses. */
6432 static struct iv_ca
*
6433 get_initial_solution (struct ivopts_data
*data
, bool originalp
)
6435 struct iv_ca
*ivs
= iv_ca_new (data
);
6438 for (i
= 0; i
< n_iv_uses (data
); i
++)
6439 if (!try_add_cand_for (data
, ivs
, iv_use (data
, i
), originalp
))
6448 /* Tries to improve set of induction variables IVS. TRY_REPLACE_P
6449 points to a bool variable, this function tries to break local
6450 optimal fixed-point by replacing candidates in IVS if it's true. */
6453 try_improve_iv_set (struct ivopts_data
*data
,
6454 struct iv_ca
*ivs
, bool *try_replace_p
)
6457 comp_cost acost
, best_cost
= iv_ca_cost (ivs
);
6458 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
, *tmp_delta
;
6459 struct iv_cand
*cand
;
6461 /* Try extending the set of induction variables by one. */
6462 for (i
= 0; i
< n_iv_cands (data
); i
++)
6464 cand
= iv_cand (data
, i
);
6466 if (iv_ca_cand_used_p (ivs
, cand
))
6469 acost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, &n_ivs
, false);
6473 /* If we successfully added the candidate and the set is small enough,
6474 try optimizing it by removing other candidates. */
6475 if (n_ivs
<= ALWAYS_PRUNE_CAND_SET_BOUND
)
6477 iv_ca_delta_commit (data
, ivs
, act_delta
, true);
6478 acost
= iv_ca_prune (data
, ivs
, cand
, &tmp_delta
);
6479 iv_ca_delta_commit (data
, ivs
, act_delta
, false);
6480 act_delta
= iv_ca_delta_join (act_delta
, tmp_delta
);
6483 if (compare_costs (acost
, best_cost
) < 0)
6486 iv_ca_delta_free (&best_delta
);
6487 best_delta
= act_delta
;
6490 iv_ca_delta_free (&act_delta
);
6495 /* Try removing the candidates from the set instead. */
6496 best_cost
= iv_ca_prune (data
, ivs
, NULL
, &best_delta
);
6498 if (!best_delta
&& *try_replace_p
)
6500 *try_replace_p
= false;
6501 /* So far candidate selecting algorithm tends to choose fewer IVs
6502 so that it can handle cases in which loops have many variables
6503 but the best choice is often to use only one general biv. One
6504 weakness is it can't handle opposite cases, in which different
6505 candidates should be chosen with respect to each use. To solve
6506 the problem, we replace candidates in a manner described by the
6507 comments of iv_ca_replace, thus give general algorithm a chance
6508 to break local optimal fixed-point in these cases. */
6509 best_cost
= iv_ca_replace (data
, ivs
, &best_delta
);
6516 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
6517 gcc_assert (compare_costs (best_cost
, iv_ca_cost (ivs
)) == 0);
6518 iv_ca_delta_free (&best_delta
);
6522 /* Attempts to find the optimal set of induction variables. We do simple
6523 greedy heuristic -- we try to replace at most one candidate in the selected
6524 solution and remove the unused ivs while this improves the cost. */
6526 static struct iv_ca
*
6527 find_optimal_iv_set_1 (struct ivopts_data
*data
, bool originalp
)
6530 bool try_replace_p
= true;
6532 /* Get the initial solution. */
6533 set
= get_initial_solution (data
, originalp
);
6536 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6537 fprintf (dump_file
, "Unable to substitute for ivs, failed.\n");
6541 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6543 fprintf (dump_file
, "Initial set of candidates:\n");
6544 iv_ca_dump (data
, dump_file
, set
);
6547 while (try_improve_iv_set (data
, set
, &try_replace_p
))
6549 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6551 fprintf (dump_file
, "Improved to:\n");
6552 iv_ca_dump (data
, dump_file
, set
);
6559 static struct iv_ca
*
6560 find_optimal_iv_set (struct ivopts_data
*data
)
6563 struct iv_ca
*set
, *origset
;
6565 comp_cost cost
, origcost
;
6567 /* Determine the cost based on a strategy that starts with original IVs,
6568 and try again using a strategy that prefers candidates not based
6570 origset
= find_optimal_iv_set_1 (data
, true);
6571 set
= find_optimal_iv_set_1 (data
, false);
6573 if (!origset
&& !set
)
6576 origcost
= origset
? iv_ca_cost (origset
) : infinite_cost
;
6577 cost
= set
? iv_ca_cost (set
) : infinite_cost
;
6579 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6581 fprintf (dump_file
, "Original cost %d (complexity %d)\n\n",
6582 origcost
.cost
, origcost
.complexity
);
6583 fprintf (dump_file
, "Final cost %d (complexity %d)\n\n",
6584 cost
.cost
, cost
.complexity
);
6587 /* Choose the one with the best cost. */
6588 if (compare_costs (origcost
, cost
) <= 0)
6595 iv_ca_free (&origset
);
6597 for (i
= 0; i
< n_iv_uses (data
); i
++)
6599 use
= iv_use (data
, i
);
6600 use
->selected
= iv_ca_cand_for_use (set
, use
)->cand
;
6606 /* Creates a new induction variable corresponding to CAND. */
6609 create_new_iv (struct ivopts_data
*data
, struct iv_cand
*cand
)
6611 gimple_stmt_iterator incr_pos
;
6621 incr_pos
= gsi_last_bb (ip_normal_pos (data
->current_loop
));
6625 incr_pos
= gsi_last_bb (ip_end_pos (data
->current_loop
));
6633 incr_pos
= gsi_for_stmt (cand
->incremented_at
);
6637 /* Mark that the iv is preserved. */
6638 name_info (data
, cand
->var_before
)->preserve_biv
= true;
6639 name_info (data
, cand
->var_after
)->preserve_biv
= true;
6641 /* Rewrite the increment so that it uses var_before directly. */
6642 find_interesting_uses_op (data
, cand
->var_after
)->selected
= cand
;
6646 gimple_add_tmp_var (cand
->var_before
);
6648 base
= unshare_expr (cand
->iv
->base
);
6650 create_iv (base
, unshare_expr (cand
->iv
->step
),
6651 cand
->var_before
, data
->current_loop
,
6652 &incr_pos
, after
, &cand
->var_before
, &cand
->var_after
);
6655 /* Creates new induction variables described in SET. */
6658 create_new_ivs (struct ivopts_data
*data
, struct iv_ca
*set
)
6661 struct iv_cand
*cand
;
6664 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
6666 cand
= iv_cand (data
, i
);
6667 create_new_iv (data
, cand
);
6670 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6672 fprintf (dump_file
, "Selected IV set for loop %d",
6673 data
->current_loop
->num
);
6674 if (data
->loop_loc
!= UNKNOWN_LOCATION
)
6675 fprintf (dump_file
, " at %s:%d", LOCATION_FILE (data
->loop_loc
),
6676 LOCATION_LINE (data
->loop_loc
));
6677 fprintf (dump_file
, ", %lu IVs:\n", bitmap_count_bits (set
->cands
));
6678 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
6680 cand
= iv_cand (data
, i
);
6681 dump_cand (dump_file
, cand
);
6683 fprintf (dump_file
, "\n");
6687 /* Rewrites USE (definition of iv used in a nonlinear expression)
6688 using candidate CAND. */
6691 rewrite_use_nonlinear_expr (struct ivopts_data
*data
,
6692 struct iv_use
*use
, struct iv_cand
*cand
)
6697 gimple_stmt_iterator bsi
;
6699 /* An important special case -- if we are asked to express value of
6700 the original iv by itself, just exit; there is no need to
6701 introduce a new computation (that might also need casting the
6702 variable to unsigned and back). */
6703 if (cand
->pos
== IP_ORIGINAL
6704 && cand
->incremented_at
== use
->stmt
)
6706 enum tree_code stmt_code
;
6708 gcc_assert (is_gimple_assign (use
->stmt
));
6709 gcc_assert (gimple_assign_lhs (use
->stmt
) == cand
->var_after
);
6711 /* Check whether we may leave the computation unchanged.
6712 This is the case only if it does not rely on other
6713 computations in the loop -- otherwise, the computation
6714 we rely upon may be removed in remove_unused_ivs,
6715 thus leading to ICE. */
6716 stmt_code
= gimple_assign_rhs_code (use
->stmt
);
6717 if (stmt_code
== PLUS_EXPR
6718 || stmt_code
== MINUS_EXPR
6719 || stmt_code
== POINTER_PLUS_EXPR
)
6721 if (gimple_assign_rhs1 (use
->stmt
) == cand
->var_before
)
6722 op
= gimple_assign_rhs2 (use
->stmt
);
6723 else if (gimple_assign_rhs2 (use
->stmt
) == cand
->var_before
)
6724 op
= gimple_assign_rhs1 (use
->stmt
);
6731 if (op
&& expr_invariant_in_loop_p (data
->current_loop
, op
))
6735 comp
= get_computation (data
->current_loop
, use
, cand
);
6736 gcc_assert (comp
!= NULL_TREE
);
6738 switch (gimple_code (use
->stmt
))
6741 tgt
= PHI_RESULT (use
->stmt
);
6743 /* If we should keep the biv, do not replace it. */
6744 if (name_info (data
, tgt
)->preserve_biv
)
6747 bsi
= gsi_after_labels (gimple_bb (use
->stmt
));
6751 tgt
= gimple_assign_lhs (use
->stmt
);
6752 bsi
= gsi_for_stmt (use
->stmt
);
6759 if (!valid_gimple_rhs_p (comp
)
6760 || (gimple_code (use
->stmt
) != GIMPLE_PHI
6761 /* We can't allow re-allocating the stmt as it might be pointed
6763 && (get_gimple_rhs_num_ops (TREE_CODE (comp
))
6764 >= gimple_num_ops (gsi_stmt (bsi
)))))
6766 comp
= force_gimple_operand_gsi (&bsi
, comp
, true, NULL_TREE
,
6767 true, GSI_SAME_STMT
);
6768 if (POINTER_TYPE_P (TREE_TYPE (tgt
)))
6770 duplicate_ssa_name_ptr_info (comp
, SSA_NAME_PTR_INFO (tgt
));
6771 /* As this isn't a plain copy we have to reset alignment
6773 if (SSA_NAME_PTR_INFO (comp
))
6774 mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (comp
));
6778 if (gimple_code (use
->stmt
) == GIMPLE_PHI
)
6780 ass
= gimple_build_assign (tgt
, comp
);
6781 gsi_insert_before (&bsi
, ass
, GSI_SAME_STMT
);
6783 bsi
= gsi_for_stmt (use
->stmt
);
6784 remove_phi_node (&bsi
, false);
6788 gimple_assign_set_rhs_from_tree (&bsi
, comp
);
6789 use
->stmt
= gsi_stmt (bsi
);
6793 /* Performs a peephole optimization to reorder the iv update statement with
6794 a mem ref to enable instruction combining in later phases. The mem ref uses
6795 the iv value before the update, so the reordering transformation requires
6796 adjustment of the offset. CAND is the selected IV_CAND.
6800 t = MEM_REF (base, iv1, 8, 16); // base, index, stride, offset
6808 directly propagating t over to (1) will introduce overlapping live range
6809 thus increase register pressure. This peephole transform it into:
6813 t = MEM_REF (base, iv2, 8, 8);
6820 adjust_iv_update_pos (struct iv_cand
*cand
, struct iv_use
*use
)
6823 gimple iv_update
, stmt
;
6825 gimple_stmt_iterator gsi
, gsi_iv
;
6827 if (cand
->pos
!= IP_NORMAL
)
6830 var_after
= cand
->var_after
;
6831 iv_update
= SSA_NAME_DEF_STMT (var_after
);
6833 bb
= gimple_bb (iv_update
);
6834 gsi
= gsi_last_nondebug_bb (bb
);
6835 stmt
= gsi_stmt (gsi
);
6837 /* Only handle conditional statement for now. */
6838 if (gimple_code (stmt
) != GIMPLE_COND
)
6841 gsi_prev_nondebug (&gsi
);
6842 stmt
= gsi_stmt (gsi
);
6843 if (stmt
!= iv_update
)
6846 gsi_prev_nondebug (&gsi
);
6847 if (gsi_end_p (gsi
))
6850 stmt
= gsi_stmt (gsi
);
6851 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
6854 if (stmt
!= use
->stmt
)
6857 if (TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
6860 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6862 fprintf (dump_file
, "Reordering \n");
6863 print_gimple_stmt (dump_file
, iv_update
, 0, 0);
6864 print_gimple_stmt (dump_file
, use
->stmt
, 0, 0);
6865 fprintf (dump_file
, "\n");
6868 gsi
= gsi_for_stmt (use
->stmt
);
6869 gsi_iv
= gsi_for_stmt (iv_update
);
6870 gsi_move_before (&gsi_iv
, &gsi
);
6872 cand
->pos
= IP_BEFORE_USE
;
6873 cand
->incremented_at
= use
->stmt
;
6876 /* Rewrites USE (address that is an iv) using candidate CAND. */
6879 rewrite_use_address_1 (struct ivopts_data
*data
,
6880 struct iv_use
*use
, struct iv_cand
*cand
)
6883 gimple_stmt_iterator bsi
= gsi_for_stmt (use
->stmt
);
6884 tree base_hint
= NULL_TREE
;
6888 adjust_iv_update_pos (cand
, use
);
6889 ok
= get_computation_aff (data
->current_loop
, use
, cand
, use
->stmt
, &aff
);
6891 unshare_aff_combination (&aff
);
6893 /* To avoid undefined overflow problems, all IV candidates use unsigned
6894 integer types. The drawback is that this makes it impossible for
6895 create_mem_ref to distinguish an IV that is based on a memory object
6896 from one that represents simply an offset.
6898 To work around this problem, we pass a hint to create_mem_ref that
6899 indicates which variable (if any) in aff is an IV based on a memory
6900 object. Note that we only consider the candidate. If this is not
6901 based on an object, the base of the reference is in some subexpression
6902 of the use -- but these will use pointer types, so they are recognized
6903 by the create_mem_ref heuristics anyway. */
6904 if (cand
->iv
->base_object
)
6905 base_hint
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
6907 iv
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
6908 ref
= create_mem_ref (&bsi
, TREE_TYPE (*use
->op_p
), &aff
,
6909 reference_alias_ptr_type (*use
->op_p
),
6910 iv
, base_hint
, data
->speed
);
6911 copy_ref_info (ref
, *use
->op_p
);
6915 /* Rewrites USE (address that is an iv) using candidate CAND. If it's the
6916 first use of a group, rewrites sub uses in the group too. */
6919 rewrite_use_address (struct ivopts_data
*data
,
6920 struct iv_use
*use
, struct iv_cand
*cand
)
6922 struct iv_use
*next
;
6924 gcc_assert (use
->sub_id
== 0);
6925 rewrite_use_address_1 (data
, use
, cand
);
6926 update_stmt (use
->stmt
);
6928 for (next
= use
->next
; next
!= NULL
; next
= next
->next
)
6930 rewrite_use_address_1 (data
, next
, cand
);
6931 update_stmt (next
->stmt
);
6937 /* Rewrites USE (the condition such that one of the arguments is an iv) using
6941 rewrite_use_compare (struct ivopts_data
*data
,
6942 struct iv_use
*use
, struct iv_cand
*cand
)
6944 tree comp
, *var_p
, op
, bound
;
6945 gimple_stmt_iterator bsi
= gsi_for_stmt (use
->stmt
);
6946 enum tree_code compare
;
6947 struct cost_pair
*cp
= get_use_iv_cost (data
, use
, cand
);
6953 tree var
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
6954 tree var_type
= TREE_TYPE (var
);
6957 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6959 fprintf (dump_file
, "Replacing exit test: ");
6960 print_gimple_stmt (dump_file
, use
->stmt
, 0, TDF_SLIM
);
6963 bound
= unshare_expr (fold_convert (var_type
, bound
));
6964 op
= force_gimple_operand (bound
, &stmts
, true, NULL_TREE
);
6966 gsi_insert_seq_on_edge_immediate (
6967 loop_preheader_edge (data
->current_loop
),
6970 gcond
*cond_stmt
= as_a
<gcond
*> (use
->stmt
);
6971 gimple_cond_set_lhs (cond_stmt
, var
);
6972 gimple_cond_set_code (cond_stmt
, compare
);
6973 gimple_cond_set_rhs (cond_stmt
, op
);
6977 /* The induction variable elimination failed; just express the original
6979 comp
= get_computation (data
->current_loop
, use
, cand
);
6980 gcc_assert (comp
!= NULL_TREE
);
6982 ok
= extract_cond_operands (data
, use
->stmt
, &var_p
, NULL
, NULL
, NULL
);
6985 *var_p
= force_gimple_operand_gsi (&bsi
, comp
, true, SSA_NAME_VAR (*var_p
),
6986 true, GSI_SAME_STMT
);
6989 /* Rewrites USE using candidate CAND. */
6992 rewrite_use (struct ivopts_data
*data
, struct iv_use
*use
, struct iv_cand
*cand
)
6996 case USE_NONLINEAR_EXPR
:
6997 rewrite_use_nonlinear_expr (data
, use
, cand
);
7001 rewrite_use_address (data
, use
, cand
);
7005 rewrite_use_compare (data
, use
, cand
);
7012 update_stmt (use
->stmt
);
7015 /* Rewrite the uses using the selected induction variables. */
7018 rewrite_uses (struct ivopts_data
*data
)
7021 struct iv_cand
*cand
;
7024 for (i
= 0; i
< n_iv_uses (data
); i
++)
7026 use
= iv_use (data
, i
);
7027 cand
= use
->selected
;
7030 rewrite_use (data
, use
, cand
);
7034 /* Removes the ivs that are not used after rewriting. */
7037 remove_unused_ivs (struct ivopts_data
*data
)
7041 bitmap toremove
= BITMAP_ALLOC (NULL
);
7043 /* Figure out an order in which to release SSA DEFs so that we don't
7044 release something that we'd have to propagate into a debug stmt
7046 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
7048 struct version_info
*info
;
7050 info
= ver_info (data
, j
);
7052 && !integer_zerop (info
->iv
->step
)
7054 && !info
->iv
->have_use_for
7055 && !info
->preserve_biv
)
7057 bitmap_set_bit (toremove
, SSA_NAME_VERSION (info
->iv
->ssa_name
));
7059 tree def
= info
->iv
->ssa_name
;
7061 if (MAY_HAVE_DEBUG_STMTS
&& SSA_NAME_DEF_STMT (def
))
7063 imm_use_iterator imm_iter
;
7064 use_operand_p use_p
;
7068 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, def
)
7070 if (!gimple_debug_bind_p (stmt
))
7073 /* We just want to determine whether to do nothing
7074 (count == 0), to substitute the computed
7075 expression into a single use of the SSA DEF by
7076 itself (count == 1), or to use a debug temp
7077 because the SSA DEF is used multiple times or as
7078 part of a larger expression (count > 1). */
7080 if (gimple_debug_bind_get_value (stmt
) != def
)
7084 BREAK_FROM_IMM_USE_STMT (imm_iter
);
7090 struct iv_use dummy_use
;
7091 struct iv_cand
*best_cand
= NULL
, *cand
;
7092 unsigned i
, best_pref
= 0, cand_pref
;
7094 memset (&dummy_use
, 0, sizeof (dummy_use
));
7095 dummy_use
.iv
= info
->iv
;
7096 for (i
= 0; i
< n_iv_uses (data
) && i
< 64; i
++)
7098 cand
= iv_use (data
, i
)->selected
;
7099 if (cand
== best_cand
)
7101 cand_pref
= operand_equal_p (cand
->iv
->step
,
7105 += TYPE_MODE (TREE_TYPE (cand
->iv
->base
))
7106 == TYPE_MODE (TREE_TYPE (info
->iv
->base
))
7109 += TREE_CODE (cand
->iv
->base
) == INTEGER_CST
7111 if (best_cand
== NULL
|| best_pref
< cand_pref
)
7114 best_pref
= cand_pref
;
7121 tree comp
= get_computation_at (data
->current_loop
,
7122 &dummy_use
, best_cand
,
7123 SSA_NAME_DEF_STMT (def
));
7129 tree vexpr
= make_node (DEBUG_EXPR_DECL
);
7130 DECL_ARTIFICIAL (vexpr
) = 1;
7131 TREE_TYPE (vexpr
) = TREE_TYPE (comp
);
7132 if (SSA_NAME_VAR (def
))
7133 DECL_MODE (vexpr
) = DECL_MODE (SSA_NAME_VAR (def
));
7135 DECL_MODE (vexpr
) = TYPE_MODE (TREE_TYPE (vexpr
));
7137 = gimple_build_debug_bind (vexpr
, comp
, NULL
);
7138 gimple_stmt_iterator gsi
;
7140 if (gimple_code (SSA_NAME_DEF_STMT (def
)) == GIMPLE_PHI
)
7141 gsi
= gsi_after_labels (gimple_bb
7142 (SSA_NAME_DEF_STMT (def
)));
7144 gsi
= gsi_for_stmt (SSA_NAME_DEF_STMT (def
));
7146 gsi_insert_before (&gsi
, def_temp
, GSI_SAME_STMT
);
7150 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, def
)
7152 if (!gimple_debug_bind_p (stmt
))
7155 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
7156 SET_USE (use_p
, comp
);
7164 release_defs_bitset (toremove
);
7166 BITMAP_FREE (toremove
);
7169 /* Frees memory occupied by struct tree_niter_desc in *VALUE. Callback
7170 for hash_map::traverse. */
7173 free_tree_niter_desc (edge
const &, tree_niter_desc
*const &value
, void *)
7179 /* Frees data allocated by the optimization of a single loop. */
7182 free_loop_data (struct ivopts_data
*data
)
7190 data
->niters
->traverse
<void *, free_tree_niter_desc
> (NULL
);
7191 delete data
->niters
;
7192 data
->niters
= NULL
;
7195 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
7197 struct version_info
*info
;
7199 info
= ver_info (data
, i
);
7202 info
->has_nonlin_use
= false;
7203 info
->preserve_biv
= false;
7206 bitmap_clear (data
->relevant
);
7207 bitmap_clear (data
->important_candidates
);
7209 for (i
= 0; i
< n_iv_uses (data
); i
++)
7211 struct iv_use
*use
= iv_use (data
, i
);
7212 struct iv_use
*pre
= use
, *sub
= use
->next
;
7216 gcc_assert (sub
->related_cands
== NULL
);
7217 gcc_assert (sub
->n_map_members
== 0 && sub
->cost_map
== NULL
);
7226 BITMAP_FREE (use
->related_cands
);
7227 for (j
= 0; j
< use
->n_map_members
; j
++)
7228 if (use
->cost_map
[j
].depends_on
)
7229 BITMAP_FREE (use
->cost_map
[j
].depends_on
);
7230 free (use
->cost_map
);
7233 data
->iv_uses
.truncate (0);
7235 for (i
= 0; i
< n_iv_cands (data
); i
++)
7237 struct iv_cand
*cand
= iv_cand (data
, i
);
7240 if (cand
->depends_on
)
7241 BITMAP_FREE (cand
->depends_on
);
7244 data
->iv_candidates
.truncate (0);
7246 if (data
->version_info_size
< num_ssa_names
)
7248 data
->version_info_size
= 2 * num_ssa_names
;
7249 free (data
->version_info
);
7250 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
7253 data
->max_inv_id
= 0;
7255 FOR_EACH_VEC_ELT (decl_rtl_to_reset
, i
, obj
)
7256 SET_DECL_RTL (obj
, NULL_RTX
);
7258 decl_rtl_to_reset
.truncate (0);
7260 data
->inv_expr_tab
->empty ();
7261 data
->inv_expr_id
= 0;
7264 /* Finalizes data structures used by the iv optimization pass. LOOPS is the
7268 tree_ssa_iv_optimize_finalize (struct ivopts_data
*data
)
7270 free_loop_data (data
);
7271 free (data
->version_info
);
7272 BITMAP_FREE (data
->relevant
);
7273 BITMAP_FREE (data
->important_candidates
);
7275 decl_rtl_to_reset
.release ();
7276 data
->iv_uses
.release ();
7277 data
->iv_candidates
.release ();
7278 delete data
->inv_expr_tab
;
7279 data
->inv_expr_tab
= NULL
;
7280 free_affine_expand_cache (&data
->name_expansion_cache
);
7283 /* Returns true if the loop body BODY includes any function calls. */
7286 loop_body_includes_call (basic_block
*body
, unsigned num_nodes
)
7288 gimple_stmt_iterator gsi
;
7291 for (i
= 0; i
< num_nodes
; i
++)
7292 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
7294 gimple stmt
= gsi_stmt (gsi
);
7295 if (is_gimple_call (stmt
)
7296 && !is_inexpensive_builtin (gimple_call_fndecl (stmt
)))
7302 /* Optimizes the LOOP. Returns true if anything changed. */
7305 tree_ssa_iv_optimize_loop (struct ivopts_data
*data
, struct loop
*loop
)
7307 bool changed
= false;
7308 struct iv_ca
*iv_ca
;
7309 edge exit
= single_dom_exit (loop
);
7312 gcc_assert (!data
->niters
);
7313 data
->current_loop
= loop
;
7314 data
->loop_loc
= find_loop_location (loop
);
7315 data
->speed
= optimize_loop_for_speed_p (loop
);
7317 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7319 fprintf (dump_file
, "Processing loop %d", loop
->num
);
7320 if (data
->loop_loc
!= UNKNOWN_LOCATION
)
7321 fprintf (dump_file
, " at %s:%d", LOCATION_FILE (data
->loop_loc
),
7322 LOCATION_LINE (data
->loop_loc
));
7323 fprintf (dump_file
, "\n");
7327 fprintf (dump_file
, " single exit %d -> %d, exit condition ",
7328 exit
->src
->index
, exit
->dest
->index
);
7329 print_gimple_stmt (dump_file
, last_stmt (exit
->src
), 0, TDF_SLIM
);
7330 fprintf (dump_file
, "\n");
7333 fprintf (dump_file
, "\n");
7336 body
= get_loop_body (loop
);
7337 data
->body_includes_call
= loop_body_includes_call (body
, loop
->num_nodes
);
7338 renumber_gimple_stmt_uids_in_blocks (body
, loop
->num_nodes
);
7341 data
->loop_single_exit_p
= exit
!= NULL
&& loop_only_exit_p (loop
, exit
);
7343 /* For each ssa name determines whether it behaves as an induction variable
7345 if (!find_induction_variables (data
))
7348 /* Finds interesting uses (item 1). */
7349 find_interesting_uses (data
);
7350 group_address_uses (data
);
7351 if (n_iv_uses (data
) > MAX_CONSIDERED_USES
)
7354 /* Finds candidates for the induction variables (item 2). */
7355 find_iv_candidates (data
);
7357 /* Calculates the costs (item 3, part 1). */
7358 determine_iv_costs (data
);
7359 determine_use_iv_costs (data
);
7360 determine_set_costs (data
);
7362 /* Find the optimal set of induction variables (item 3, part 2). */
7363 iv_ca
= find_optimal_iv_set (data
);
7368 /* Create the new induction variables (item 4, part 1). */
7369 create_new_ivs (data
, iv_ca
);
7370 iv_ca_free (&iv_ca
);
7372 /* Rewrite the uses (item 4, part 2). */
7373 rewrite_uses (data
);
7375 /* Remove the ivs that are unused after rewriting. */
7376 remove_unused_ivs (data
);
7378 /* We have changed the structure of induction variables; it might happen
7379 that definitions in the scev database refer to some of them that were
7384 free_loop_data (data
);
7389 /* Main entry point. Optimizes induction variables in loops. */
7392 tree_ssa_iv_optimize (void)
7395 struct ivopts_data data
;
7397 tree_ssa_iv_optimize_init (&data
);
7399 /* Optimize the loops starting with the innermost ones. */
7400 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
7402 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7403 flow_loop_dump (loop
, dump_file
, NULL
, 1);
7405 tree_ssa_iv_optimize_loop (&data
, loop
);
7408 tree_ssa_iv_optimize_finalize (&data
);