1 /* Induction variable optimizations.
2 Copyright (C) 2003-2022 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 Note the interesting uses are categorized and handled in group.
34 Generally, address type uses are grouped together if their iv bases
35 are different in constant offset.
37 2) Candidates for the induction variables are found. This includes
39 -- old induction variables
40 -- the variables defined by expressions derived from the "interesting
43 3) The optimal (w.r. to a cost function) set of variables is chosen. The
44 cost function assigns a cost to sets of induction variables and consists
47 -- The group/use costs. Each of the interesting groups/uses chooses
48 the best induction variable in the set and adds its cost to the sum.
49 The cost reflects the time spent on modifying the induction variables
50 value to be usable for the given purpose (adding base and offset for
52 -- The variable costs. Each of the variables has a cost assigned that
53 reflects the costs associated with incrementing the value of the
54 variable. The original variables are somewhat preferred.
55 -- The set cost. Depending on the size of the set, extra cost may be
56 added to reflect register pressure.
58 All the costs are defined in a machine-specific way, using the target
59 hooks and machine descriptions to determine them.
61 4) The trees are transformed to use the new variables, the dead code is
64 All of this is done loop by loop. Doing it globally is theoretically
65 possible, it might give a better performance and it might enable us
66 to decide costs more precisely, but getting all the interactions right
69 For the targets supporting low-overhead loops, IVOPTs has to take care of
70 the loops which will probably be transformed in RTL doloop optimization,
71 to try to make selected IV candidate set optimal. The process of doloop
74 1) Analyze the current loop will be transformed to doloop or not, find and
75 mark its compare type IV use as doloop use (iv_group field doloop_p), and
76 set flag doloop_use_p of ivopts_data to notify subsequent processings on
77 doloop. See analyze_and_mark_doloop_use and its callees for the details.
78 The target hook predict_doloop_p can be used for target specific checks.
80 2) Add one doloop dedicated IV cand {(may_be_zero ? 1 : (niter + 1)), +, -1},
81 set flag doloop_p of iv_cand, step cost is set as zero and no extra cost
82 like biv. For cost determination between doloop IV cand and IV use, the
83 target hooks doloop_cost_for_generic and doloop_cost_for_address are
84 provided to add on extra costs for generic type and address type IV use.
85 Zero cost is assigned to the pair between doloop IV cand and doloop IV
86 use, and bound zero is set for IV elimination.
88 3) With the cost setting in step 2), the current cost model based IV
89 selection algorithm will process as usual, pick up doloop dedicated IV if
94 #include "coretypes.h"
100 #include "tree-pass.h"
101 #include "memmodel.h"
105 #include "insn-config.h"
106 #include "emit-rtl.h"
109 #include "gimple-pretty-print.h"
111 #include "fold-const.h"
112 #include "stor-layout.h"
114 #include "gimplify.h"
115 #include "gimple-iterator.h"
116 #include "gimplify-me.h"
117 #include "tree-cfg.h"
118 #include "tree-ssa-loop-ivopts.h"
119 #include "tree-ssa-loop-manip.h"
120 #include "tree-ssa-loop-niter.h"
121 #include "tree-ssa-loop.h"
124 #include "tree-dfa.h"
125 #include "tree-ssa.h"
127 #include "tree-scalar-evolution.h"
128 #include "tree-affine.h"
129 #include "tree-ssa-propagate.h"
130 #include "tree-ssa-address.h"
131 #include "builtins.h"
132 #include "tree-vectorizer.h"
135 /* For lang_hooks.types.type_for_mode. */
136 #include "langhooks.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. */
142 /* The infinite cost. */
143 #define INFTY 1000000000
145 /* Returns the expected number of loop iterations for LOOP.
146 The average trip count is computed from profile data if it
149 static inline HOST_WIDE_INT
150 avg_loop_niter (class loop
*loop
)
152 HOST_WIDE_INT niter
= estimated_stmt_executions_int (loop
);
155 niter
= likely_max_stmt_executions_int (loop
);
157 if (niter
== -1 || niter
> param_avg_loop_niter
)
158 return param_avg_loop_niter
;
166 /* Representation of the induction variable. */
169 tree base
; /* Initial value of the iv. */
170 tree base_object
; /* A memory object to that the induction variable points. */
171 tree step
; /* Step of the iv (constant only). */
172 tree ssa_name
; /* The ssa name with the value. */
173 struct iv_use
*nonlin_use
; /* The identifier in the use if it is the case. */
174 bool biv_p
; /* Is it a biv? */
175 bool no_overflow
; /* True if the iv doesn't overflow. */
176 bool have_address_use
;/* For biv, indicate if it's used in any address
180 /* Per-ssa version information (induction variable descriptions, etc.). */
183 tree name
; /* The ssa name. */
184 struct iv
*iv
; /* Induction variable description. */
185 bool has_nonlin_use
; /* For a loop-level invariant, whether it is used in
186 an expression that is not an induction variable. */
187 bool preserve_biv
; /* For the original biv, whether to preserve it. */
188 unsigned inv_id
; /* Id of an invariant. */
194 USE_NONLINEAR_EXPR
, /* Use in a nonlinear expression. */
195 USE_REF_ADDRESS
, /* Use is an address for an explicit memory
197 USE_PTR_ADDRESS
, /* Use is a pointer argument to a function in
198 cases where the expansion of the function
199 will turn the argument into a normal address. */
200 USE_COMPARE
/* Use is a compare. */
203 /* Cost of a computation. */
207 comp_cost (): cost (0), complexity (0), scratch (0)
210 comp_cost (int64_t cost
, unsigned complexity
, int64_t scratch
= 0)
211 : cost (cost
), complexity (complexity
), scratch (scratch
)
214 /* Returns true if COST is infinite. */
215 bool infinite_cost_p ();
217 /* Adds costs COST1 and COST2. */
218 friend comp_cost
operator+ (comp_cost cost1
, comp_cost cost2
);
220 /* Adds COST to the comp_cost. */
221 comp_cost
operator+= (comp_cost cost
);
223 /* Adds constant C to this comp_cost. */
224 comp_cost
operator+= (HOST_WIDE_INT c
);
226 /* Subtracts constant C to this comp_cost. */
227 comp_cost
operator-= (HOST_WIDE_INT c
);
229 /* Divide the comp_cost by constant C. */
230 comp_cost
operator/= (HOST_WIDE_INT c
);
232 /* Multiply the comp_cost by constant C. */
233 comp_cost
operator*= (HOST_WIDE_INT c
);
235 /* Subtracts costs COST1 and COST2. */
236 friend comp_cost
operator- (comp_cost cost1
, comp_cost cost2
);
238 /* Subtracts COST from this comp_cost. */
239 comp_cost
operator-= (comp_cost cost
);
241 /* Returns true if COST1 is smaller than COST2. */
242 friend bool operator< (comp_cost cost1
, comp_cost cost2
);
244 /* Returns true if COST1 and COST2 are equal. */
245 friend bool operator== (comp_cost cost1
, comp_cost cost2
);
247 /* Returns true if COST1 is smaller or equal than COST2. */
248 friend bool operator<= (comp_cost cost1
, comp_cost cost2
);
250 int64_t cost
; /* The runtime cost. */
251 unsigned complexity
; /* The estimate of the complexity of the code for
252 the computation (in no concrete units --
253 complexity field should be larger for more
254 complex expressions and addressing modes). */
255 int64_t scratch
; /* Scratch used during cost computation. */
258 static const comp_cost no_cost
;
259 static const comp_cost
infinite_cost (INFTY
, 0, INFTY
);
262 comp_cost::infinite_cost_p ()
264 return cost
== INFTY
;
268 operator+ (comp_cost cost1
, comp_cost cost2
)
270 if (cost1
.infinite_cost_p () || cost2
.infinite_cost_p ())
271 return infinite_cost
;
273 gcc_assert (cost1
.cost
+ cost2
.cost
< infinite_cost
.cost
);
274 cost1
.cost
+= cost2
.cost
;
275 cost1
.complexity
+= cost2
.complexity
;
281 operator- (comp_cost cost1
, comp_cost cost2
)
283 if (cost1
.infinite_cost_p ())
284 return infinite_cost
;
286 gcc_assert (!cost2
.infinite_cost_p ());
287 gcc_assert (cost1
.cost
- cost2
.cost
< infinite_cost
.cost
);
289 cost1
.cost
-= cost2
.cost
;
290 cost1
.complexity
-= cost2
.complexity
;
296 comp_cost::operator+= (comp_cost cost
)
298 *this = *this + cost
;
303 comp_cost::operator+= (HOST_WIDE_INT c
)
308 if (infinite_cost_p ())
311 gcc_assert (this->cost
+ c
< infinite_cost
.cost
);
318 comp_cost::operator-= (HOST_WIDE_INT c
)
320 if (infinite_cost_p ())
323 gcc_assert (this->cost
- c
< infinite_cost
.cost
);
330 comp_cost::operator/= (HOST_WIDE_INT c
)
333 if (infinite_cost_p ())
342 comp_cost::operator*= (HOST_WIDE_INT c
)
344 if (infinite_cost_p ())
347 gcc_assert (this->cost
* c
< infinite_cost
.cost
);
354 comp_cost::operator-= (comp_cost cost
)
356 *this = *this - cost
;
361 operator< (comp_cost cost1
, comp_cost cost2
)
363 if (cost1
.cost
== cost2
.cost
)
364 return cost1
.complexity
< cost2
.complexity
;
366 return cost1
.cost
< cost2
.cost
;
370 operator== (comp_cost cost1
, comp_cost cost2
)
372 return cost1
.cost
== cost2
.cost
373 && cost1
.complexity
== cost2
.complexity
;
377 operator<= (comp_cost cost1
, comp_cost cost2
)
379 return cost1
< cost2
|| cost1
== cost2
;
382 struct iv_inv_expr_ent
;
384 /* The candidate - cost pair. */
388 struct iv_cand
*cand
; /* The candidate. */
389 comp_cost cost
; /* The cost. */
390 enum tree_code comp
; /* For iv elimination, the comparison. */
391 bitmap inv_vars
; /* The list of invariant ssa_vars that have to be
392 preserved when representing iv_use with iv_cand. */
393 bitmap inv_exprs
; /* The list of newly created invariant expressions
394 when representing iv_use with iv_cand. */
395 tree value
; /* For final value elimination, the expression for
396 the final value of the iv. For iv elimination,
397 the new bound to compare with. */
403 unsigned id
; /* The id of the use. */
404 unsigned group_id
; /* The group id the use belongs to. */
405 enum use_type type
; /* Type of the use. */
406 tree mem_type
; /* The memory type to use when testing whether an
407 address is legitimate, and what the address's
409 struct iv
*iv
; /* The induction variable it is based on. */
410 gimple
*stmt
; /* Statement in that it occurs. */
411 tree
*op_p
; /* The place where it occurs. */
413 tree addr_base
; /* Base address with const offset stripped. */
414 poly_uint64_pod addr_offset
;
415 /* Const offset stripped from base address. */
421 /* The id of the group. */
423 /* Uses of the group are of the same type. */
425 /* The set of "related" IV candidates, plus the important ones. */
426 bitmap related_cands
;
427 /* Number of IV candidates in the cost_map. */
428 unsigned n_map_members
;
429 /* The costs wrto the iv candidates. */
430 class cost_pair
*cost_map
;
431 /* The selected candidate for the group. */
432 struct iv_cand
*selected
;
433 /* To indicate this is a doloop use group. */
435 /* Uses in the group. */
436 vec
<struct iv_use
*> vuses
;
439 /* The position where the iv is computed. */
442 IP_NORMAL
, /* At the end, just before the exit condition. */
443 IP_END
, /* At the end of the latch block. */
444 IP_BEFORE_USE
, /* Immediately before a specific use. */
445 IP_AFTER_USE
, /* Immediately after a specific use. */
446 IP_ORIGINAL
/* The original biv. */
449 /* The induction variable candidate. */
452 unsigned id
; /* The number of the candidate. */
453 bool important
; /* Whether this is an "important" candidate, i.e. such
454 that it should be considered by all uses. */
455 bool involves_undefs
; /* Whether the IV involves undefined values. */
456 ENUM_BITFIELD(iv_position
) pos
: 8; /* Where it is computed. */
457 gimple
*incremented_at
;/* For original biv, the statement where it is
459 tree var_before
; /* The variable used for it before increment. */
460 tree var_after
; /* The variable used for it after increment. */
461 struct iv
*iv
; /* The value of the candidate. NULL for
462 "pseudocandidate" used to indicate the possibility
463 to replace the final value of an iv by direct
464 computation of the value. */
465 unsigned cost
; /* Cost of the candidate. */
466 unsigned cost_step
; /* Cost of the candidate's increment operation. */
467 struct iv_use
*ainc_use
; /* For IP_{BEFORE,AFTER}_USE candidates, the place
468 where it is incremented. */
469 bitmap inv_vars
; /* The list of invariant ssa_vars used in step of the
471 bitmap inv_exprs
; /* If step is more complicated than a single ssa_var,
472 hanlde it as a new invariant expression which will
473 be hoisted out of loop. */
474 struct iv
*orig_iv
; /* The original iv if this cand is added from biv with
476 bool doloop_p
; /* Whether this is a doloop candidate. */
479 /* Hashtable entry for common candidate derived from iv uses. */
485 /* IV uses from which this common candidate is derived. */
486 auto_vec
<struct iv_use
*> uses
;
490 /* Hashtable helpers. */
492 struct iv_common_cand_hasher
: delete_ptr_hash
<iv_common_cand
>
494 static inline hashval_t
hash (const iv_common_cand
*);
495 static inline bool equal (const iv_common_cand
*, const iv_common_cand
*);
498 /* Hash function for possible common candidates. */
501 iv_common_cand_hasher::hash (const iv_common_cand
*ccand
)
506 /* Hash table equality function for common candidates. */
509 iv_common_cand_hasher::equal (const iv_common_cand
*ccand1
,
510 const iv_common_cand
*ccand2
)
512 return (ccand1
->hash
== ccand2
->hash
513 && operand_equal_p (ccand1
->base
, ccand2
->base
, 0)
514 && operand_equal_p (ccand1
->step
, ccand2
->step
, 0)
515 && (TYPE_PRECISION (TREE_TYPE (ccand1
->base
))
516 == TYPE_PRECISION (TREE_TYPE (ccand2
->base
))));
519 /* Loop invariant expression hashtable entry. */
521 struct iv_inv_expr_ent
523 /* Tree expression of the entry. */
525 /* Unique indentifier. */
531 /* Sort iv_inv_expr_ent pair A and B by id field. */
534 sort_iv_inv_expr_ent (const void *a
, const void *b
)
536 const iv_inv_expr_ent
* const *e1
= (const iv_inv_expr_ent
* const *) (a
);
537 const iv_inv_expr_ent
* const *e2
= (const iv_inv_expr_ent
* const *) (b
);
539 unsigned id1
= (*e1
)->id
;
540 unsigned id2
= (*e2
)->id
;
550 /* Hashtable helpers. */
552 struct iv_inv_expr_hasher
: free_ptr_hash
<iv_inv_expr_ent
>
554 static inline hashval_t
hash (const iv_inv_expr_ent
*);
555 static inline bool equal (const iv_inv_expr_ent
*, const iv_inv_expr_ent
*);
558 /* Return true if uses of type TYPE represent some form of address. */
561 address_p (use_type type
)
563 return type
== USE_REF_ADDRESS
|| type
== USE_PTR_ADDRESS
;
566 /* Hash function for loop invariant expressions. */
569 iv_inv_expr_hasher::hash (const iv_inv_expr_ent
*expr
)
574 /* Hash table equality function for expressions. */
577 iv_inv_expr_hasher::equal (const iv_inv_expr_ent
*expr1
,
578 const iv_inv_expr_ent
*expr2
)
580 return expr1
->hash
== expr2
->hash
581 && operand_equal_p (expr1
->expr
, expr2
->expr
, 0);
586 /* The currently optimized loop. */
587 class loop
*current_loop
;
590 /* Numbers of iterations for all exits of the current loop. */
591 hash_map
<edge
, tree_niter_desc
*> *niters
;
593 /* Number of registers used in it. */
596 /* The size of version_info array allocated. */
597 unsigned version_info_size
;
599 /* The array of information for the ssa names. */
600 struct version_info
*version_info
;
602 /* The hashtable of loop invariant expressions created
604 hash_table
<iv_inv_expr_hasher
> *inv_expr_tab
;
606 /* The bitmap of indices in version_info whose value was changed. */
609 /* The uses of induction variables. */
610 vec
<iv_group
*> vgroups
;
612 /* The candidates. */
613 vec
<iv_cand
*> vcands
;
615 /* A bitmap of important candidates. */
616 bitmap important_candidates
;
618 /* Cache used by tree_to_aff_combination_expand. */
619 hash_map
<tree
, name_expansion
*> *name_expansion_cache
;
621 /* The hashtable of common candidates derived from iv uses. */
622 hash_table
<iv_common_cand_hasher
> *iv_common_cand_tab
;
624 /* The common candidates. */
625 vec
<iv_common_cand
*> iv_common_cands
;
627 /* Hash map recording base object information of tree exp. */
628 hash_map
<tree
, tree
> *base_object_map
;
630 /* The maximum invariant variable id. */
631 unsigned max_inv_var_id
;
633 /* The maximum invariant expression id. */
634 unsigned max_inv_expr_id
;
636 /* Number of no_overflow BIVs which are not used in memory address. */
637 unsigned bivs_not_used_in_addr
;
639 /* Obstack for iv structure. */
640 struct obstack iv_obstack
;
642 /* Whether to consider just related and important candidates when replacing a
644 bool consider_all_candidates
;
646 /* Are we optimizing for speed? */
649 /* Whether the loop body includes any function calls. */
650 bool body_includes_call
;
652 /* Whether the loop body can only be exited via single exit. */
653 bool loop_single_exit_p
;
655 /* Whether the loop has doloop comparison use. */
659 /* An assignment of iv candidates to uses. */
664 /* The number of uses covered by the assignment. */
667 /* Number of uses that cannot be expressed by the candidates in the set. */
670 /* Candidate assigned to a use, together with the related costs. */
671 class cost_pair
**cand_for_group
;
673 /* Number of times each candidate is used. */
674 unsigned *n_cand_uses
;
676 /* The candidates used. */
679 /* The number of candidates in the set. */
682 /* The number of invariants needed, including both invariant variants and
683 invariant expressions. */
686 /* Total cost of expressing uses. */
687 comp_cost cand_use_cost
;
689 /* Total cost of candidates. */
692 /* Number of times each invariant variable is used. */
693 unsigned *n_inv_var_uses
;
695 /* Number of times each invariant expression is used. */
696 unsigned *n_inv_expr_uses
;
698 /* Total cost of the assignment. */
702 /* Difference of two iv candidate assignments. */
707 struct iv_group
*group
;
709 /* An old assignment (for rollback purposes). */
710 class cost_pair
*old_cp
;
712 /* A new assignment. */
713 class cost_pair
*new_cp
;
715 /* Next change in the list. */
716 struct iv_ca_delta
*next
;
719 /* Bound on number of candidates below that all candidates are considered. */
721 #define CONSIDER_ALL_CANDIDATES_BOUND \
722 ((unsigned) param_iv_consider_all_candidates_bound)
724 /* If there are more iv occurrences, we just give up (it is quite unlikely that
725 optimizing such a loop would help, and it would take ages). */
727 #define MAX_CONSIDERED_GROUPS \
728 ((unsigned) param_iv_max_considered_uses)
730 /* If there are at most this number of ivs in the set, try removing unnecessary
731 ivs from the set always. */
733 #define ALWAYS_PRUNE_CAND_SET_BOUND \
734 ((unsigned) param_iv_always_prune_cand_set_bound)
736 /* The list of trees for that the decl_rtl field must be reset is stored
739 static vec
<tree
> decl_rtl_to_reset
;
741 static comp_cost
force_expr_to_var_cost (tree
, bool);
743 /* The single loop exit if it dominates the latch, NULL otherwise. */
746 single_dom_exit (class loop
*loop
)
748 edge exit
= single_exit (loop
);
753 if (!just_once_each_iteration_p (loop
, exit
->src
))
759 /* Dumps information about the induction variable IV to FILE. Don't dump
760 variable's name if DUMP_NAME is FALSE. The information is dumped with
761 preceding spaces indicated by INDENT_LEVEL. */
764 dump_iv (FILE *file
, struct iv
*iv
, bool dump_name
, unsigned indent_level
)
767 const char spaces
[9] = {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '\0'};
769 if (indent_level
> 4)
771 p
= spaces
+ 8 - (indent_level
<< 1);
773 fprintf (file
, "%sIV struct:\n", p
);
774 if (iv
->ssa_name
&& dump_name
)
776 fprintf (file
, "%s SSA_NAME:\t", p
);
777 print_generic_expr (file
, iv
->ssa_name
, TDF_SLIM
);
778 fprintf (file
, "\n");
781 fprintf (file
, "%s Type:\t", p
);
782 print_generic_expr (file
, TREE_TYPE (iv
->base
), TDF_SLIM
);
783 fprintf (file
, "\n");
785 fprintf (file
, "%s Base:\t", p
);
786 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
787 fprintf (file
, "\n");
789 fprintf (file
, "%s Step:\t", p
);
790 print_generic_expr (file
, iv
->step
, TDF_SLIM
);
791 fprintf (file
, "\n");
795 fprintf (file
, "%s Object:\t", p
);
796 print_generic_expr (file
, iv
->base_object
, TDF_SLIM
);
797 fprintf (file
, "\n");
800 fprintf (file
, "%s Biv:\t%c\n", p
, iv
->biv_p
? 'Y' : 'N');
802 fprintf (file
, "%s Overflowness wrto loop niter:\t%s\n",
803 p
, iv
->no_overflow
? "No-overflow" : "Overflow");
806 /* Dumps information about the USE to FILE. */
809 dump_use (FILE *file
, struct iv_use
*use
)
811 fprintf (file
, " Use %d.%d:\n", use
->group_id
, use
->id
);
812 fprintf (file
, " At stmt:\t");
813 print_gimple_stmt (file
, use
->stmt
, 0);
814 fprintf (file
, " At pos:\t");
816 print_generic_expr (file
, *use
->op_p
, TDF_SLIM
);
817 fprintf (file
, "\n");
818 dump_iv (file
, use
->iv
, false, 2);
821 /* Dumps information about the uses to FILE. */
824 dump_groups (FILE *file
, struct ivopts_data
*data
)
827 struct iv_group
*group
;
829 for (i
= 0; i
< data
->vgroups
.length (); i
++)
831 group
= data
->vgroups
[i
];
832 fprintf (file
, "Group %d:\n", group
->id
);
833 if (group
->type
== USE_NONLINEAR_EXPR
)
834 fprintf (file
, " Type:\tGENERIC\n");
835 else if (group
->type
== USE_REF_ADDRESS
)
836 fprintf (file
, " Type:\tREFERENCE ADDRESS\n");
837 else if (group
->type
== USE_PTR_ADDRESS
)
838 fprintf (file
, " Type:\tPOINTER ARGUMENT ADDRESS\n");
841 gcc_assert (group
->type
== USE_COMPARE
);
842 fprintf (file
, " Type:\tCOMPARE\n");
844 for (j
= 0; j
< group
->vuses
.length (); j
++)
845 dump_use (file
, group
->vuses
[j
]);
849 /* Dumps information about induction variable candidate CAND to FILE. */
852 dump_cand (FILE *file
, struct iv_cand
*cand
)
854 struct iv
*iv
= cand
->iv
;
856 fprintf (file
, "Candidate %d:\n", cand
->id
);
859 fprintf (file
, " Depend on inv.vars: ");
860 dump_bitmap (file
, cand
->inv_vars
);
864 fprintf (file
, " Depend on inv.exprs: ");
865 dump_bitmap (file
, cand
->inv_exprs
);
868 if (cand
->var_before
)
870 fprintf (file
, " Var befor: ");
871 print_generic_expr (file
, cand
->var_before
, TDF_SLIM
);
872 fprintf (file
, "\n");
876 fprintf (file
, " Var after: ");
877 print_generic_expr (file
, cand
->var_after
, TDF_SLIM
);
878 fprintf (file
, "\n");
884 fprintf (file
, " Incr POS: before exit test\n");
888 fprintf (file
, " Incr POS: before use %d\n", cand
->ainc_use
->id
);
892 fprintf (file
, " Incr POS: after use %d\n", cand
->ainc_use
->id
);
896 fprintf (file
, " Incr POS: at end\n");
900 fprintf (file
, " Incr POS: orig biv\n");
904 dump_iv (file
, iv
, false, 1);
907 /* Returns the info for ssa version VER. */
909 static inline struct version_info
*
910 ver_info (struct ivopts_data
*data
, unsigned ver
)
912 return data
->version_info
+ ver
;
915 /* Returns the info for ssa name NAME. */
917 static inline struct version_info
*
918 name_info (struct ivopts_data
*data
, tree name
)
920 return ver_info (data
, SSA_NAME_VERSION (name
));
923 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
927 stmt_after_ip_normal_pos (class loop
*loop
, gimple
*stmt
)
929 basic_block bb
= ip_normal_pos (loop
), sbb
= gimple_bb (stmt
);
933 if (sbb
== loop
->latch
)
939 return stmt
== last_stmt (bb
);
942 /* Returns true if STMT if after the place where the original induction
943 variable CAND is incremented. If TRUE_IF_EQUAL is set, we return true
944 if the positions are identical. */
947 stmt_after_inc_pos (struct iv_cand
*cand
, gimple
*stmt
, bool true_if_equal
)
949 basic_block cand_bb
= gimple_bb (cand
->incremented_at
);
950 basic_block stmt_bb
= gimple_bb (stmt
);
952 if (!dominated_by_p (CDI_DOMINATORS
, stmt_bb
, cand_bb
))
955 if (stmt_bb
!= cand_bb
)
959 && gimple_uid (stmt
) == gimple_uid (cand
->incremented_at
))
961 return gimple_uid (stmt
) > gimple_uid (cand
->incremented_at
);
964 /* Returns true if STMT if after the place where the induction variable
965 CAND is incremented in LOOP. */
968 stmt_after_increment (class loop
*loop
, struct iv_cand
*cand
, gimple
*stmt
)
976 return stmt_after_ip_normal_pos (loop
, stmt
);
980 return stmt_after_inc_pos (cand
, stmt
, false);
983 return stmt_after_inc_pos (cand
, stmt
, true);
990 /* walk_tree callback for contains_abnormal_ssa_name_p. */
993 contains_abnormal_ssa_name_p_1 (tree
*tp
, int *walk_subtrees
, void *)
995 if (TREE_CODE (*tp
) == SSA_NAME
996 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (*tp
))
1005 /* Returns true if EXPR contains a ssa name that occurs in an
1006 abnormal phi node. */
1009 contains_abnormal_ssa_name_p (tree expr
)
1011 return walk_tree_without_duplicates
1012 (&expr
, contains_abnormal_ssa_name_p_1
, NULL
) != NULL_TREE
;
1015 /* Returns the structure describing number of iterations determined from
1016 EXIT of DATA->current_loop, or NULL if something goes wrong. */
1018 static class tree_niter_desc
*
1019 niter_for_exit (struct ivopts_data
*data
, edge exit
)
1021 class tree_niter_desc
*desc
;
1022 tree_niter_desc
**slot
;
1026 data
->niters
= new hash_map
<edge
, tree_niter_desc
*>;
1030 slot
= data
->niters
->get (exit
);
1034 /* Try to determine number of iterations. We cannot safely work with ssa
1035 names that appear in phi nodes on abnormal edges, so that we do not
1036 create overlapping life ranges for them (PR 27283). */
1037 desc
= XNEW (class tree_niter_desc
);
1038 if (!number_of_iterations_exit (data
->current_loop
,
1040 || contains_abnormal_ssa_name_p (desc
->niter
))
1045 data
->niters
->put (exit
, desc
);
1053 /* Returns the structure describing number of iterations determined from
1054 single dominating exit of DATA->current_loop, or NULL if something
1057 static class tree_niter_desc
*
1058 niter_for_single_dom_exit (struct ivopts_data
*data
)
1060 edge exit
= single_dom_exit (data
->current_loop
);
1065 return niter_for_exit (data
, exit
);
1068 /* Initializes data structures used by the iv optimization pass, stored
1072 tree_ssa_iv_optimize_init (struct ivopts_data
*data
)
1074 data
->version_info_size
= 2 * num_ssa_names
;
1075 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
1076 data
->relevant
= BITMAP_ALLOC (NULL
);
1077 data
->important_candidates
= BITMAP_ALLOC (NULL
);
1078 data
->max_inv_var_id
= 0;
1079 data
->max_inv_expr_id
= 0;
1080 data
->niters
= NULL
;
1081 data
->vgroups
.create (20);
1082 data
->vcands
.create (20);
1083 data
->inv_expr_tab
= new hash_table
<iv_inv_expr_hasher
> (10);
1084 data
->name_expansion_cache
= NULL
;
1085 data
->base_object_map
= NULL
;
1086 data
->iv_common_cand_tab
= new hash_table
<iv_common_cand_hasher
> (10);
1087 data
->iv_common_cands
.create (20);
1088 decl_rtl_to_reset
.create (20);
1089 gcc_obstack_init (&data
->iv_obstack
);
1092 /* walk_tree callback for determine_base_object. */
1095 determine_base_object_1 (tree
*tp
, int *walk_subtrees
, void *wdata
)
1097 tree_code code
= TREE_CODE (*tp
);
1098 tree obj
= NULL_TREE
;
1099 if (code
== ADDR_EXPR
)
1101 tree base
= get_base_address (TREE_OPERAND (*tp
, 0));
1104 else if (TREE_CODE (base
) != MEM_REF
)
1105 obj
= fold_convert (ptr_type_node
, build_fold_addr_expr (base
));
1107 else if (code
== SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (*tp
)))
1108 obj
= fold_convert (ptr_type_node
, *tp
);
1117 /* Record special node for multiple base objects and stop. */
1118 if (*static_cast<tree
*> (wdata
))
1120 *static_cast<tree
*> (wdata
) = integer_zero_node
;
1121 return integer_zero_node
;
1123 /* Record the base object and continue looking. */
1124 *static_cast<tree
*> (wdata
) = obj
;
1128 /* Returns a memory object to that EXPR points with caching. Return NULL if we
1129 are able to determine that it does not point to any such object; specially
1130 return integer_zero_node if EXPR contains multiple base objects. */
1133 determine_base_object (struct ivopts_data
*data
, tree expr
)
1135 tree
*slot
, obj
= NULL_TREE
;
1136 if (data
->base_object_map
)
1138 if ((slot
= data
->base_object_map
->get(expr
)) != NULL
)
1142 data
->base_object_map
= new hash_map
<tree
, tree
>;
1144 (void) walk_tree_without_duplicates (&expr
, determine_base_object_1
, &obj
);
1145 data
->base_object_map
->put (expr
, obj
);
1149 /* Return true if address expression with non-DECL_P operand appears
1153 contain_complex_addr_expr (tree expr
)
1158 switch (TREE_CODE (expr
))
1160 case POINTER_PLUS_EXPR
:
1163 res
|= contain_complex_addr_expr (TREE_OPERAND (expr
, 0));
1164 res
|= contain_complex_addr_expr (TREE_OPERAND (expr
, 1));
1168 return (!DECL_P (TREE_OPERAND (expr
, 0)));
1177 /* Allocates an induction variable with given initial value BASE and step STEP
1178 for loop LOOP. NO_OVERFLOW implies the iv doesn't overflow. */
1181 alloc_iv (struct ivopts_data
*data
, tree base
, tree step
,
1182 bool no_overflow
= false)
1185 struct iv
*iv
= (struct iv
*) obstack_alloc (&data
->iv_obstack
,
1186 sizeof (struct iv
));
1187 gcc_assert (step
!= NULL_TREE
);
1189 /* Lower address expression in base except ones with DECL_P as operand.
1191 1) More accurate cost can be computed for address expressions;
1192 2) Duplicate candidates won't be created for bases in different
1193 forms, like &a[0] and &a. */
1195 if ((TREE_CODE (expr
) == ADDR_EXPR
&& !DECL_P (TREE_OPERAND (expr
, 0)))
1196 || contain_complex_addr_expr (expr
))
1199 tree_to_aff_combination (expr
, TREE_TYPE (expr
), &comb
);
1200 base
= fold_convert (TREE_TYPE (base
), aff_combination_to_tree (&comb
));
1204 iv
->base_object
= determine_base_object (data
, base
);
1207 iv
->nonlin_use
= NULL
;
1208 iv
->ssa_name
= NULL_TREE
;
1210 && !iv_can_overflow_p (data
->current_loop
, TREE_TYPE (base
),
1213 iv
->no_overflow
= no_overflow
;
1214 iv
->have_address_use
= false;
1219 /* Sets STEP and BASE for induction variable IV. NO_OVERFLOW implies the IV
1220 doesn't overflow. */
1223 set_iv (struct ivopts_data
*data
, tree iv
, tree base
, tree step
,
1226 struct version_info
*info
= name_info (data
, iv
);
1228 gcc_assert (!info
->iv
);
1230 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (iv
));
1231 info
->iv
= alloc_iv (data
, base
, step
, no_overflow
);
1232 info
->iv
->ssa_name
= iv
;
1235 /* Finds induction variable declaration for VAR. */
1238 get_iv (struct ivopts_data
*data
, tree var
)
1241 tree type
= TREE_TYPE (var
);
1243 if (!POINTER_TYPE_P (type
)
1244 && !INTEGRAL_TYPE_P (type
))
1247 if (!name_info (data
, var
)->iv
)
1249 bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
1252 || !flow_bb_inside_loop_p (data
->current_loop
, bb
))
1254 if (POINTER_TYPE_P (type
))
1256 set_iv (data
, var
, var
, build_int_cst (type
, 0), true);
1260 return name_info (data
, var
)->iv
;
1263 /* Return the first non-invariant ssa var found in EXPR. */
1266 extract_single_var_from_expr (tree expr
)
1270 enum tree_code code
;
1272 if (!expr
|| is_gimple_min_invariant (expr
))
1275 code
= TREE_CODE (expr
);
1276 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1278 n
= TREE_OPERAND_LENGTH (expr
);
1279 for (i
= 0; i
< n
; i
++)
1281 tmp
= extract_single_var_from_expr (TREE_OPERAND (expr
, i
));
1287 return (TREE_CODE (expr
) == SSA_NAME
) ? expr
: NULL
;
1290 /* Finds basic ivs. */
1293 find_bivs (struct ivopts_data
*data
)
1297 tree step
, type
, base
, stop
;
1299 class loop
*loop
= data
->current_loop
;
1302 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1306 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
1309 if (virtual_operand_p (PHI_RESULT (phi
)))
1312 if (!simple_iv (loop
, loop
, PHI_RESULT (phi
), &iv
, true))
1315 if (integer_zerop (iv
.step
))
1319 base
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1320 /* Stop expanding iv base at the first ssa var referred by iv step.
1321 Ideally we should stop at any ssa var, because that's expensive
1322 and unusual to happen, we just do it on the first one.
1324 See PR64705 for the rationale. */
1325 stop
= extract_single_var_from_expr (step
);
1326 base
= expand_simple_operations (base
, stop
);
1327 if (contains_abnormal_ssa_name_p (base
)
1328 || contains_abnormal_ssa_name_p (step
))
1331 type
= TREE_TYPE (PHI_RESULT (phi
));
1332 base
= fold_convert (type
, base
);
1335 if (POINTER_TYPE_P (type
))
1336 step
= convert_to_ptrofftype (step
);
1338 step
= fold_convert (type
, step
);
1341 set_iv (data
, PHI_RESULT (phi
), base
, step
, iv
.no_overflow
);
1348 /* Marks basic ivs. */
1351 mark_bivs (struct ivopts_data
*data
)
1356 struct iv
*iv
, *incr_iv
;
1357 class loop
*loop
= data
->current_loop
;
1358 basic_block incr_bb
;
1361 data
->bivs_not_used_in_addr
= 0;
1362 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1366 iv
= get_iv (data
, PHI_RESULT (phi
));
1370 var
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
1371 def
= SSA_NAME_DEF_STMT (var
);
1372 /* Don't mark iv peeled from other one as biv. */
1374 && gimple_code (def
) == GIMPLE_PHI
1375 && gimple_bb (def
) == loop
->header
)
1378 incr_iv
= get_iv (data
, var
);
1382 /* If the increment is in the subloop, ignore it. */
1383 incr_bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
1384 if (incr_bb
->loop_father
!= data
->current_loop
1385 || (incr_bb
->flags
& BB_IRREDUCIBLE_LOOP
))
1389 incr_iv
->biv_p
= true;
1390 if (iv
->no_overflow
)
1391 data
->bivs_not_used_in_addr
++;
1392 if (incr_iv
->no_overflow
)
1393 data
->bivs_not_used_in_addr
++;
1397 /* Checks whether STMT defines a linear induction variable and stores its
1398 parameters to IV. */
1401 find_givs_in_stmt_scev (struct ivopts_data
*data
, gimple
*stmt
, affine_iv
*iv
)
1404 class loop
*loop
= data
->current_loop
;
1406 iv
->base
= NULL_TREE
;
1407 iv
->step
= NULL_TREE
;
1409 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1412 lhs
= gimple_assign_lhs (stmt
);
1413 if (TREE_CODE (lhs
) != SSA_NAME
)
1416 if (!simple_iv (loop
, loop_containing_stmt (stmt
), lhs
, iv
, true))
1419 /* Stop expanding iv base at the first ssa var referred by iv step.
1420 Ideally we should stop at any ssa var, because that's expensive
1421 and unusual to happen, we just do it on the first one.
1423 See PR64705 for the rationale. */
1424 stop
= extract_single_var_from_expr (iv
->step
);
1425 iv
->base
= expand_simple_operations (iv
->base
, stop
);
1426 if (contains_abnormal_ssa_name_p (iv
->base
)
1427 || contains_abnormal_ssa_name_p (iv
->step
))
1430 /* If STMT could throw, then do not consider STMT as defining a GIV.
1431 While this will suppress optimizations, we cannot safely delete this
1432 GIV and associated statements, even if it appears it is not used. */
1433 if (stmt_could_throw_p (cfun
, stmt
))
1439 /* Finds general ivs in statement STMT. */
1442 find_givs_in_stmt (struct ivopts_data
*data
, gimple
*stmt
)
1446 if (!find_givs_in_stmt_scev (data
, stmt
, &iv
))
1449 set_iv (data
, gimple_assign_lhs (stmt
), iv
.base
, iv
.step
, iv
.no_overflow
);
1452 /* Finds general ivs in basic block BB. */
1455 find_givs_in_bb (struct ivopts_data
*data
, basic_block bb
)
1457 gimple_stmt_iterator bsi
;
1459 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1460 find_givs_in_stmt (data
, gsi_stmt (bsi
));
1463 /* Finds general ivs. */
1466 find_givs (struct ivopts_data
*data
, basic_block
*body
)
1468 class loop
*loop
= data
->current_loop
;
1471 for (i
= 0; i
< loop
->num_nodes
; i
++)
1472 find_givs_in_bb (data
, body
[i
]);
1475 /* For each ssa name defined in LOOP determines whether it is an induction
1476 variable and if so, its initial value and step. */
1479 find_induction_variables (struct ivopts_data
*data
, basic_block
*body
)
1484 if (!find_bivs (data
))
1487 find_givs (data
, body
);
1490 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1492 class tree_niter_desc
*niter
= niter_for_single_dom_exit (data
);
1496 fprintf (dump_file
, " number of iterations ");
1497 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1498 if (!integer_zerop (niter
->may_be_zero
))
1500 fprintf (dump_file
, "; zero if ");
1501 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1503 fprintf (dump_file
, "\n");
1506 fprintf (dump_file
, "\n<Induction Vars>:\n");
1507 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1509 struct version_info
*info
= ver_info (data
, i
);
1510 if (info
->iv
&& info
->iv
->step
&& !integer_zerop (info
->iv
->step
))
1511 dump_iv (dump_file
, ver_info (data
, i
)->iv
, true, 0);
1518 /* Records a use of TYPE at *USE_P in STMT whose value is IV in GROUP.
1519 For address type use, ADDR_BASE is the stripped IV base, ADDR_OFFSET
1520 is the const offset stripped from IV base and MEM_TYPE is the type
1521 of the memory being addressed. For uses of other types, ADDR_BASE
1522 and ADDR_OFFSET are zero by default and MEM_TYPE is NULL_TREE. */
1524 static struct iv_use
*
1525 record_use (struct iv_group
*group
, tree
*use_p
, struct iv
*iv
,
1526 gimple
*stmt
, enum use_type type
, tree mem_type
,
1527 tree addr_base
, poly_uint64 addr_offset
)
1529 struct iv_use
*use
= XCNEW (struct iv_use
);
1531 use
->id
= group
->vuses
.length ();
1532 use
->group_id
= group
->id
;
1534 use
->mem_type
= mem_type
;
1538 use
->addr_base
= addr_base
;
1539 use
->addr_offset
= addr_offset
;
1541 group
->vuses
.safe_push (use
);
1545 /* Checks whether OP is a loop-level invariant and if so, records it.
1546 NONLINEAR_USE is true if the invariant is used in a way we do not
1547 handle specially. */
1550 record_invariant (struct ivopts_data
*data
, tree op
, bool nonlinear_use
)
1553 struct version_info
*info
;
1555 if (TREE_CODE (op
) != SSA_NAME
1556 || virtual_operand_p (op
))
1559 bb
= gimple_bb (SSA_NAME_DEF_STMT (op
));
1561 && flow_bb_inside_loop_p (data
->current_loop
, bb
))
1564 info
= name_info (data
, op
);
1566 info
->has_nonlin_use
|= nonlinear_use
;
1568 info
->inv_id
= ++data
->max_inv_var_id
;
1569 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (op
));
1572 /* Record a group of TYPE. */
1574 static struct iv_group
*
1575 record_group (struct ivopts_data
*data
, enum use_type type
)
1577 struct iv_group
*group
= XCNEW (struct iv_group
);
1579 group
->id
= data
->vgroups
.length ();
1581 group
->related_cands
= BITMAP_ALLOC (NULL
);
1582 group
->vuses
.create (1);
1583 group
->doloop_p
= false;
1585 data
->vgroups
.safe_push (group
);
1589 /* Record a use of TYPE at *USE_P in STMT whose value is IV in a group.
1590 New group will be created if there is no existing group for the use.
1591 MEM_TYPE is the type of memory being addressed, or NULL if this
1592 isn't an address reference. */
1594 static struct iv_use
*
1595 record_group_use (struct ivopts_data
*data
, tree
*use_p
,
1596 struct iv
*iv
, gimple
*stmt
, enum use_type type
,
1599 tree addr_base
= NULL
;
1600 struct iv_group
*group
= NULL
;
1601 poly_uint64 addr_offset
= 0;
1603 /* Record non address type use in a new group. */
1604 if (address_p (type
))
1608 addr_base
= strip_offset (iv
->base
, &addr_offset
);
1609 for (i
= 0; i
< data
->vgroups
.length (); i
++)
1613 group
= data
->vgroups
[i
];
1614 use
= group
->vuses
[0];
1615 if (!address_p (use
->type
))
1618 /* Check if it has the same stripped base and step. */
1619 if (operand_equal_p (iv
->base_object
, use
->iv
->base_object
, 0)
1620 && operand_equal_p (iv
->step
, use
->iv
->step
, 0)
1621 && operand_equal_p (addr_base
, use
->addr_base
, 0))
1624 if (i
== data
->vgroups
.length ())
1629 group
= record_group (data
, type
);
1631 return record_use (group
, use_p
, iv
, stmt
, type
, mem_type
,
1632 addr_base
, addr_offset
);
1635 /* Checks whether the use OP is interesting and if so, records it. */
1637 static struct iv_use
*
1638 find_interesting_uses_op (struct ivopts_data
*data
, tree op
)
1644 if (TREE_CODE (op
) != SSA_NAME
)
1647 iv
= get_iv (data
, op
);
1653 gcc_assert (iv
->nonlin_use
->type
== USE_NONLINEAR_EXPR
);
1654 return iv
->nonlin_use
;
1657 if (integer_zerop (iv
->step
))
1659 record_invariant (data
, op
, true);
1663 stmt
= SSA_NAME_DEF_STMT (op
);
1664 gcc_assert (gimple_code (stmt
) == GIMPLE_PHI
|| is_gimple_assign (stmt
));
1666 use
= record_group_use (data
, NULL
, iv
, stmt
, USE_NONLINEAR_EXPR
, NULL_TREE
);
1667 iv
->nonlin_use
= use
;
1671 /* Indicate how compare type iv_use can be handled. */
1672 enum comp_iv_rewrite
1675 /* We may rewrite compare type iv_use by expressing value of the iv_use. */
1677 /* We may rewrite compare type iv_uses on both sides of comparison by
1678 expressing value of each iv_use. */
1680 /* We may rewrite compare type iv_use by expressing value of the iv_use
1681 or by eliminating it with other iv_cand. */
1685 /* Given a condition in statement STMT, checks whether it is a compare
1686 of an induction variable and an invariant. If this is the case,
1687 CONTROL_VAR is set to location of the iv, BOUND to the location of
1688 the invariant, IV_VAR and IV_BOUND are set to the corresponding
1689 induction variable descriptions, and true is returned. If this is not
1690 the case, CONTROL_VAR and BOUND are set to the arguments of the
1691 condition and false is returned. */
1693 static enum comp_iv_rewrite
1694 extract_cond_operands (struct ivopts_data
*data
, gimple
*stmt
,
1695 tree
**control_var
, tree
**bound
,
1696 struct iv
**iv_var
, struct iv
**iv_bound
)
1698 /* The objects returned when COND has constant operands. */
1699 static struct iv const_iv
;
1701 tree
*op0
= &zero
, *op1
= &zero
;
1702 struct iv
*iv0
= &const_iv
, *iv1
= &const_iv
;
1703 enum comp_iv_rewrite rewrite_type
= COMP_IV_NA
;
1705 if (gimple_code (stmt
) == GIMPLE_COND
)
1707 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
1708 op0
= gimple_cond_lhs_ptr (cond_stmt
);
1709 op1
= gimple_cond_rhs_ptr (cond_stmt
);
1713 op0
= gimple_assign_rhs1_ptr (stmt
);
1714 op1
= gimple_assign_rhs2_ptr (stmt
);
1717 zero
= integer_zero_node
;
1718 const_iv
.step
= integer_zero_node
;
1720 if (TREE_CODE (*op0
) == SSA_NAME
)
1721 iv0
= get_iv (data
, *op0
);
1722 if (TREE_CODE (*op1
) == SSA_NAME
)
1723 iv1
= get_iv (data
, *op1
);
1725 /* If both sides of comparison are IVs. We can express ivs on both end. */
1726 if (iv0
&& iv1
&& !integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1728 rewrite_type
= COMP_IV_EXPR_2
;
1732 /* If none side of comparison is IV. */
1733 if ((!iv0
|| integer_zerop (iv0
->step
))
1734 && (!iv1
|| integer_zerop (iv1
->step
)))
1737 /* Control variable may be on the other side. */
1738 if (!iv0
|| integer_zerop (iv0
->step
))
1740 std::swap (op0
, op1
);
1741 std::swap (iv0
, iv1
);
1743 /* If one side is IV and the other side isn't loop invariant. */
1745 rewrite_type
= COMP_IV_EXPR
;
1746 /* If one side is IV and the other side is loop invariant. */
1747 else if (!integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1748 rewrite_type
= COMP_IV_ELIM
;
1760 return rewrite_type
;
1763 /* Checks whether the condition in STMT is interesting and if so,
1767 find_interesting_uses_cond (struct ivopts_data
*data
, gimple
*stmt
)
1769 tree
*var_p
, *bound_p
;
1770 struct iv
*var_iv
, *bound_iv
;
1771 enum comp_iv_rewrite ret
;
1773 ret
= extract_cond_operands (data
, stmt
,
1774 &var_p
, &bound_p
, &var_iv
, &bound_iv
);
1775 if (ret
== COMP_IV_NA
)
1777 find_interesting_uses_op (data
, *var_p
);
1778 find_interesting_uses_op (data
, *bound_p
);
1782 record_group_use (data
, var_p
, var_iv
, stmt
, USE_COMPARE
, NULL_TREE
);
1783 /* Record compare type iv_use for iv on the other side of comparison. */
1784 if (ret
== COMP_IV_EXPR_2
)
1785 record_group_use (data
, bound_p
, bound_iv
, stmt
, USE_COMPARE
, NULL_TREE
);
1788 /* Returns the outermost loop EXPR is obviously invariant in
1789 relative to the loop LOOP, i.e. if all its operands are defined
1790 outside of the returned loop. Returns NULL if EXPR is not
1791 even obviously invariant in LOOP. */
1794 outermost_invariant_loop_for_expr (class loop
*loop
, tree expr
)
1799 if (is_gimple_min_invariant (expr
))
1800 return current_loops
->tree_root
;
1802 if (TREE_CODE (expr
) == SSA_NAME
)
1804 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
1807 if (flow_bb_inside_loop_p (loop
, def_bb
))
1809 return superloop_at_depth (loop
,
1810 loop_depth (def_bb
->loop_father
) + 1);
1813 return current_loops
->tree_root
;
1819 unsigned maxdepth
= 0;
1820 len
= TREE_OPERAND_LENGTH (expr
);
1821 for (i
= 0; i
< len
; i
++)
1824 if (!TREE_OPERAND (expr
, i
))
1827 ivloop
= outermost_invariant_loop_for_expr (loop
, TREE_OPERAND (expr
, i
));
1830 maxdepth
= MAX (maxdepth
, loop_depth (ivloop
));
1833 return superloop_at_depth (loop
, maxdepth
);
1836 /* Returns true if expression EXPR is obviously invariant in LOOP,
1837 i.e. if all its operands are defined outside of the LOOP. LOOP
1838 should not be the function body. */
1841 expr_invariant_in_loop_p (class loop
*loop
, tree expr
)
1846 gcc_assert (loop_depth (loop
) > 0);
1848 if (is_gimple_min_invariant (expr
))
1851 if (TREE_CODE (expr
) == SSA_NAME
)
1853 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
1855 && flow_bb_inside_loop_p (loop
, def_bb
))
1864 len
= TREE_OPERAND_LENGTH (expr
);
1865 for (i
= 0; i
< len
; i
++)
1866 if (TREE_OPERAND (expr
, i
)
1867 && !expr_invariant_in_loop_p (loop
, TREE_OPERAND (expr
, i
)))
1873 /* Given expression EXPR which computes inductive values with respect
1874 to loop recorded in DATA, this function returns biv from which EXPR
1875 is derived by tracing definition chains of ssa variables in EXPR. */
1878 find_deriving_biv_for_expr (struct ivopts_data
*data
, tree expr
)
1883 enum tree_code code
;
1886 if (expr
== NULL_TREE
)
1889 if (is_gimple_min_invariant (expr
))
1892 code
= TREE_CODE (expr
);
1893 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1895 n
= TREE_OPERAND_LENGTH (expr
);
1896 for (i
= 0; i
< n
; i
++)
1898 iv
= find_deriving_biv_for_expr (data
, TREE_OPERAND (expr
, i
));
1904 /* Stop if it's not ssa name. */
1905 if (code
!= SSA_NAME
)
1908 iv
= get_iv (data
, expr
);
1909 if (!iv
|| integer_zerop (iv
->step
))
1914 stmt
= SSA_NAME_DEF_STMT (expr
);
1915 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
1918 use_operand_p use_p
;
1919 basic_block phi_bb
= gimple_bb (phi
);
1921 /* Skip loop header PHI that doesn't define biv. */
1922 if (phi_bb
->loop_father
== data
->current_loop
)
1925 if (virtual_operand_p (gimple_phi_result (phi
)))
1928 FOR_EACH_PHI_ARG (use_p
, phi
, iter
, SSA_OP_USE
)
1930 tree use
= USE_FROM_PTR (use_p
);
1931 iv
= find_deriving_biv_for_expr (data
, use
);
1937 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1940 e1
= gimple_assign_rhs1 (stmt
);
1941 code
= gimple_assign_rhs_code (stmt
);
1942 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1943 return find_deriving_biv_for_expr (data
, e1
);
1950 case POINTER_PLUS_EXPR
:
1951 /* Increments, decrements and multiplications by a constant
1953 e2
= gimple_assign_rhs2 (stmt
);
1954 iv
= find_deriving_biv_for_expr (data
, e2
);
1960 /* Casts are simple. */
1961 return find_deriving_biv_for_expr (data
, e1
);
1970 /* Record BIV, its predecessor and successor that they are used in
1971 address type uses. */
1974 record_biv_for_address_use (struct ivopts_data
*data
, struct iv
*biv
)
1977 tree type
, base_1
, base_2
;
1980 if (!biv
|| !biv
->biv_p
|| integer_zerop (biv
->step
)
1981 || biv
->have_address_use
|| !biv
->no_overflow
)
1984 type
= TREE_TYPE (biv
->base
);
1985 if (!INTEGRAL_TYPE_P (type
))
1988 biv
->have_address_use
= true;
1989 data
->bivs_not_used_in_addr
--;
1990 base_1
= fold_build2 (PLUS_EXPR
, type
, biv
->base
, biv
->step
);
1991 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1993 struct iv
*iv
= ver_info (data
, i
)->iv
;
1995 if (!iv
|| !iv
->biv_p
|| integer_zerop (iv
->step
)
1996 || iv
->have_address_use
|| !iv
->no_overflow
)
1999 if (type
!= TREE_TYPE (iv
->base
)
2000 || !INTEGRAL_TYPE_P (TREE_TYPE (iv
->base
)))
2003 if (!operand_equal_p (biv
->step
, iv
->step
, 0))
2006 base_2
= fold_build2 (PLUS_EXPR
, type
, iv
->base
, iv
->step
);
2007 if (operand_equal_p (base_1
, iv
->base
, 0)
2008 || operand_equal_p (base_2
, biv
->base
, 0))
2010 iv
->have_address_use
= true;
2011 data
->bivs_not_used_in_addr
--;
2016 /* Cumulates the steps of indices into DATA and replaces their values with the
2017 initial ones. Returns false when the value of the index cannot be determined.
2018 Callback for for_each_index. */
2020 struct ifs_ivopts_data
2022 struct ivopts_data
*ivopts_data
;
2028 idx_find_step (tree base
, tree
*idx
, void *data
)
2030 struct ifs_ivopts_data
*dta
= (struct ifs_ivopts_data
*) data
;
2032 bool use_overflow_semantics
= false;
2033 tree step
, iv_base
, iv_step
, lbound
, off
;
2034 class loop
*loop
= dta
->ivopts_data
->current_loop
;
2036 /* If base is a component ref, require that the offset of the reference
2038 if (TREE_CODE (base
) == COMPONENT_REF
)
2040 off
= component_ref_field_offset (base
);
2041 return expr_invariant_in_loop_p (loop
, off
);
2044 /* If base is array, first check whether we will be able to move the
2045 reference out of the loop (in order to take its address in strength
2046 reduction). In order for this to work we need both lower bound
2047 and step to be loop invariants. */
2048 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
2050 /* Moreover, for a range, the size needs to be invariant as well. */
2051 if (TREE_CODE (base
) == ARRAY_RANGE_REF
2052 && !expr_invariant_in_loop_p (loop
, TYPE_SIZE (TREE_TYPE (base
))))
2055 step
= array_ref_element_size (base
);
2056 lbound
= array_ref_low_bound (base
);
2058 if (!expr_invariant_in_loop_p (loop
, step
)
2059 || !expr_invariant_in_loop_p (loop
, lbound
))
2063 if (TREE_CODE (*idx
) != SSA_NAME
)
2066 iv
= get_iv (dta
->ivopts_data
, *idx
);
2070 /* XXX We produce for a base of *D42 with iv->base being &x[0]
2071 *&x[0], which is not folded and does not trigger the
2072 ARRAY_REF path below. */
2075 if (integer_zerop (iv
->step
))
2078 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
2080 step
= array_ref_element_size (base
);
2082 /* We only handle addresses whose step is an integer constant. */
2083 if (TREE_CODE (step
) != INTEGER_CST
)
2087 /* The step for pointer arithmetics already is 1 byte. */
2088 step
= size_one_node
;
2092 if (iv
->no_overflow
&& nowrap_type_p (TREE_TYPE (iv_step
)))
2093 use_overflow_semantics
= true;
2095 if (!convert_affine_scev (dta
->ivopts_data
->current_loop
,
2096 sizetype
, &iv_base
, &iv_step
, dta
->stmt
,
2097 use_overflow_semantics
))
2099 /* The index might wrap. */
2103 step
= fold_build2 (MULT_EXPR
, sizetype
, step
, iv_step
);
2104 dta
->step
= fold_build2 (PLUS_EXPR
, sizetype
, dta
->step
, step
);
2106 if (dta
->ivopts_data
->bivs_not_used_in_addr
)
2109 iv
= find_deriving_biv_for_expr (dta
->ivopts_data
, iv
->ssa_name
);
2111 record_biv_for_address_use (dta
->ivopts_data
, iv
);
2116 /* Records use in index IDX. Callback for for_each_index. Ivopts data
2117 object is passed to it in DATA. */
2120 idx_record_use (tree base
, tree
*idx
,
2123 struct ivopts_data
*data
= (struct ivopts_data
*) vdata
;
2124 find_interesting_uses_op (data
, *idx
);
2125 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
2127 if (TREE_OPERAND (base
, 2))
2128 find_interesting_uses_op (data
, TREE_OPERAND (base
, 2));
2129 if (TREE_OPERAND (base
, 3))
2130 find_interesting_uses_op (data
, TREE_OPERAND (base
, 3));
2135 /* If we can prove that TOP = cst * BOT for some constant cst,
2136 store cst to MUL and return true. Otherwise return false.
2137 The returned value is always sign-extended, regardless of the
2138 signedness of TOP and BOT. */
2141 constant_multiple_of (tree top
, tree bot
, widest_int
*mul
)
2144 enum tree_code code
;
2145 unsigned precision
= TYPE_PRECISION (TREE_TYPE (top
));
2146 widest_int res
, p0
, p1
;
2151 if (operand_equal_p (top
, bot
, 0))
2157 code
= TREE_CODE (top
);
2161 mby
= TREE_OPERAND (top
, 1);
2162 if (TREE_CODE (mby
) != INTEGER_CST
)
2165 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &res
))
2168 *mul
= wi::sext (res
* wi::to_widest (mby
), precision
);
2173 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &p0
)
2174 || !constant_multiple_of (TREE_OPERAND (top
, 1), bot
, &p1
))
2177 if (code
== MINUS_EXPR
)
2179 *mul
= wi::sext (p0
+ p1
, precision
);
2183 if (TREE_CODE (bot
) != INTEGER_CST
)
2186 p0
= widest_int::from (wi::to_wide (top
), SIGNED
);
2187 p1
= widest_int::from (wi::to_wide (bot
), SIGNED
);
2190 *mul
= wi::sext (wi::divmod_trunc (p0
, p1
, SIGNED
, &res
), precision
);
2194 if (POLY_INT_CST_P (top
)
2195 && POLY_INT_CST_P (bot
)
2196 && constant_multiple_p (wi::to_poly_widest (top
),
2197 wi::to_poly_widest (bot
), mul
))
2204 /* Return true if memory reference REF with step STEP may be unaligned. */
2207 may_be_unaligned_p (tree ref
, tree step
)
2209 /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
2210 thus they are not misaligned. */
2211 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
2214 unsigned int align
= TYPE_ALIGN (TREE_TYPE (ref
));
2215 if (GET_MODE_ALIGNMENT (TYPE_MODE (TREE_TYPE (ref
))) > align
)
2216 align
= GET_MODE_ALIGNMENT (TYPE_MODE (TREE_TYPE (ref
)));
2218 unsigned HOST_WIDE_INT bitpos
;
2219 unsigned int ref_align
;
2220 get_object_alignment_1 (ref
, &ref_align
, &bitpos
);
2221 if (ref_align
< align
2222 || (bitpos
% align
) != 0
2223 || (bitpos
% BITS_PER_UNIT
) != 0)
2226 unsigned int trailing_zeros
= tree_ctz (step
);
2227 if (trailing_zeros
< HOST_BITS_PER_INT
2228 && (1U << trailing_zeros
) * BITS_PER_UNIT
< align
)
2234 /* Return true if EXPR may be non-addressable. */
2237 may_be_nonaddressable_p (tree expr
)
2239 switch (TREE_CODE (expr
))
2242 /* Check if it's a register variable. */
2243 return DECL_HARD_REGISTER (expr
);
2245 case TARGET_MEM_REF
:
2246 /* TARGET_MEM_REFs are translated directly to valid MEMs on the
2247 target, thus they are always addressable. */
2251 /* Likewise for MEM_REFs, modulo the storage order. */
2252 return REF_REVERSE_STORAGE_ORDER (expr
);
2255 if (REF_REVERSE_STORAGE_ORDER (expr
))
2257 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
2260 if (TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (TREE_OPERAND (expr
, 0))))
2262 return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr
, 1))
2263 || may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
2266 case ARRAY_RANGE_REF
:
2267 if (TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (TREE_OPERAND (expr
, 0))))
2269 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
2271 case VIEW_CONVERT_EXPR
:
2272 /* This kind of view-conversions may wrap non-addressable objects
2273 and make them look addressable. After some processing the
2274 non-addressability may be uncovered again, causing ADDR_EXPRs
2275 of inappropriate objects to be built. */
2276 if (is_gimple_reg (TREE_OPERAND (expr
, 0))
2277 || !is_gimple_addressable (TREE_OPERAND (expr
, 0)))
2279 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
2291 /* Finds addresses in *OP_P inside STMT. */
2294 find_interesting_uses_address (struct ivopts_data
*data
, gimple
*stmt
,
2297 tree base
= *op_p
, step
= size_zero_node
;
2299 struct ifs_ivopts_data ifs_ivopts_data
;
2301 /* Do not play with volatile memory references. A bit too conservative,
2302 perhaps, but safe. */
2303 if (gimple_has_volatile_ops (stmt
))
2306 /* Ignore bitfields for now. Not really something terribly complicated
2308 if (TREE_CODE (base
) == BIT_FIELD_REF
)
2311 base
= unshare_expr (base
);
2313 if (TREE_CODE (base
) == TARGET_MEM_REF
)
2315 tree type
= build_pointer_type (TREE_TYPE (base
));
2319 && TREE_CODE (TMR_BASE (base
)) == SSA_NAME
)
2321 civ
= get_iv (data
, TMR_BASE (base
));
2325 TMR_BASE (base
) = civ
->base
;
2328 if (TMR_INDEX2 (base
)
2329 && TREE_CODE (TMR_INDEX2 (base
)) == SSA_NAME
)
2331 civ
= get_iv (data
, TMR_INDEX2 (base
));
2335 TMR_INDEX2 (base
) = civ
->base
;
2338 if (TMR_INDEX (base
)
2339 && TREE_CODE (TMR_INDEX (base
)) == SSA_NAME
)
2341 civ
= get_iv (data
, TMR_INDEX (base
));
2345 TMR_INDEX (base
) = civ
->base
;
2350 if (TMR_STEP (base
))
2351 astep
= fold_build2 (MULT_EXPR
, type
, TMR_STEP (base
), astep
);
2353 step
= fold_build2 (PLUS_EXPR
, type
, step
, astep
);
2357 if (integer_zerop (step
))
2359 base
= tree_mem_ref_addr (type
, base
);
2363 ifs_ivopts_data
.ivopts_data
= data
;
2364 ifs_ivopts_data
.stmt
= stmt
;
2365 ifs_ivopts_data
.step
= size_zero_node
;
2366 if (!for_each_index (&base
, idx_find_step
, &ifs_ivopts_data
)
2367 || integer_zerop (ifs_ivopts_data
.step
))
2369 step
= ifs_ivopts_data
.step
;
2371 /* Check that the base expression is addressable. This needs
2372 to be done after substituting bases of IVs into it. */
2373 if (may_be_nonaddressable_p (base
))
2376 /* Moreover, on strict alignment platforms, check that it is
2377 sufficiently aligned. */
2378 if (STRICT_ALIGNMENT
&& may_be_unaligned_p (base
, step
))
2381 base
= build_fold_addr_expr (base
);
2383 /* Substituting bases of IVs into the base expression might
2384 have caused folding opportunities. */
2385 if (TREE_CODE (base
) == ADDR_EXPR
)
2387 tree
*ref
= &TREE_OPERAND (base
, 0);
2388 while (handled_component_p (*ref
))
2389 ref
= &TREE_OPERAND (*ref
, 0);
2390 if (TREE_CODE (*ref
) == MEM_REF
)
2392 tree tem
= fold_binary (MEM_REF
, TREE_TYPE (*ref
),
2393 TREE_OPERAND (*ref
, 0),
2394 TREE_OPERAND (*ref
, 1));
2401 civ
= alloc_iv (data
, base
, step
);
2402 /* Fail if base object of this memory reference is unknown. */
2403 if (civ
->base_object
== NULL_TREE
)
2406 record_group_use (data
, op_p
, civ
, stmt
, USE_REF_ADDRESS
, TREE_TYPE (*op_p
));
2410 for_each_index (op_p
, idx_record_use
, data
);
2413 /* Finds and records invariants used in STMT. */
2416 find_invariants_stmt (struct ivopts_data
*data
, gimple
*stmt
)
2419 use_operand_p use_p
;
2422 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2424 op
= USE_FROM_PTR (use_p
);
2425 record_invariant (data
, op
, false);
2429 /* CALL calls an internal function. If operand *OP_P will become an
2430 address when the call is expanded, return the type of the memory
2431 being addressed, otherwise return null. */
2434 get_mem_type_for_internal_fn (gcall
*call
, tree
*op_p
)
2436 switch (gimple_call_internal_fn (call
))
2439 case IFN_MASK_LOAD_LANES
:
2441 if (op_p
== gimple_call_arg_ptr (call
, 0))
2442 return TREE_TYPE (gimple_call_lhs (call
));
2445 case IFN_MASK_STORE
:
2446 case IFN_MASK_STORE_LANES
:
2448 if (op_p
== gimple_call_arg_ptr (call
, 0))
2449 return TREE_TYPE (gimple_call_arg (call
, 3));
2457 /* IV is a (non-address) iv that describes operand *OP_P of STMT.
2458 Return true if the operand will become an address when STMT
2459 is expanded and record the associated address use if so. */
2462 find_address_like_use (struct ivopts_data
*data
, gimple
*stmt
, tree
*op_p
,
2465 /* Fail if base object of this memory reference is unknown. */
2466 if (iv
->base_object
== NULL_TREE
)
2469 tree mem_type
= NULL_TREE
;
2470 if (gcall
*call
= dyn_cast
<gcall
*> (stmt
))
2471 if (gimple_call_internal_p (call
))
2472 mem_type
= get_mem_type_for_internal_fn (call
, op_p
);
2475 iv
= alloc_iv (data
, iv
->base
, iv
->step
);
2476 record_group_use (data
, op_p
, iv
, stmt
, USE_PTR_ADDRESS
, mem_type
);
2482 /* Finds interesting uses of induction variables in the statement STMT. */
2485 find_interesting_uses_stmt (struct ivopts_data
*data
, gimple
*stmt
)
2488 tree op
, *lhs
, *rhs
;
2490 use_operand_p use_p
;
2491 enum tree_code code
;
2493 find_invariants_stmt (data
, stmt
);
2495 if (gimple_code (stmt
) == GIMPLE_COND
)
2497 find_interesting_uses_cond (data
, stmt
);
2501 if (is_gimple_assign (stmt
))
2503 lhs
= gimple_assign_lhs_ptr (stmt
);
2504 rhs
= gimple_assign_rhs1_ptr (stmt
);
2506 if (TREE_CODE (*lhs
) == SSA_NAME
)
2508 /* If the statement defines an induction variable, the uses are not
2509 interesting by themselves. */
2511 iv
= get_iv (data
, *lhs
);
2513 if (iv
&& !integer_zerop (iv
->step
))
2517 code
= gimple_assign_rhs_code (stmt
);
2518 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
2519 && (REFERENCE_CLASS_P (*rhs
)
2520 || is_gimple_val (*rhs
)))
2522 if (REFERENCE_CLASS_P (*rhs
))
2523 find_interesting_uses_address (data
, stmt
, rhs
);
2525 find_interesting_uses_op (data
, *rhs
);
2527 if (REFERENCE_CLASS_P (*lhs
))
2528 find_interesting_uses_address (data
, stmt
, lhs
);
2531 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
2533 find_interesting_uses_cond (data
, stmt
);
2537 /* TODO -- we should also handle address uses of type
2539 memory = call (whatever);
2546 if (gimple_code (stmt
) == GIMPLE_PHI
2547 && gimple_bb (stmt
) == data
->current_loop
->header
)
2549 iv
= get_iv (data
, PHI_RESULT (stmt
));
2551 if (iv
&& !integer_zerop (iv
->step
))
2555 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2557 op
= USE_FROM_PTR (use_p
);
2559 if (TREE_CODE (op
) != SSA_NAME
)
2562 iv
= get_iv (data
, op
);
2566 if (!find_address_like_use (data
, stmt
, use_p
->use
, iv
))
2567 find_interesting_uses_op (data
, op
);
2571 /* Finds interesting uses of induction variables outside of loops
2572 on loop exit edge EXIT. */
2575 find_interesting_uses_outside (struct ivopts_data
*data
, edge exit
)
2581 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2584 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
2585 if (!virtual_operand_p (def
))
2586 find_interesting_uses_op (data
, def
);
2590 /* Return TRUE if OFFSET is within the range of [base + offset] addressing
2591 mode for memory reference represented by USE. */
2593 static GTY (()) vec
<rtx
, va_gc
> *addr_list
;
2596 addr_offset_valid_p (struct iv_use
*use
, poly_int64 offset
)
2599 unsigned list_index
;
2600 addr_space_t as
= TYPE_ADDR_SPACE (TREE_TYPE (use
->iv
->base
));
2601 machine_mode addr_mode
, mem_mode
= TYPE_MODE (use
->mem_type
);
2603 list_index
= (unsigned) as
* MAX_MACHINE_MODE
+ (unsigned) mem_mode
;
2604 if (list_index
>= vec_safe_length (addr_list
))
2605 vec_safe_grow_cleared (addr_list
, list_index
+ MAX_MACHINE_MODE
, true);
2607 addr
= (*addr_list
)[list_index
];
2610 addr_mode
= targetm
.addr_space
.address_mode (as
);
2611 reg
= gen_raw_REG (addr_mode
, LAST_VIRTUAL_REGISTER
+ 1);
2612 addr
= gen_rtx_fmt_ee (PLUS
, addr_mode
, reg
, NULL_RTX
);
2613 (*addr_list
)[list_index
] = addr
;
2616 addr_mode
= GET_MODE (addr
);
2618 XEXP (addr
, 1) = gen_int_mode (offset
, addr_mode
);
2619 return (memory_address_addr_space_p (mem_mode
, addr
, as
));
2622 /* Comparison function to sort group in ascending order of addr_offset. */
2625 group_compare_offset (const void *a
, const void *b
)
2627 const struct iv_use
*const *u1
= (const struct iv_use
*const *) a
;
2628 const struct iv_use
*const *u2
= (const struct iv_use
*const *) b
;
2630 return compare_sizes_for_sort ((*u1
)->addr_offset
, (*u2
)->addr_offset
);
2633 /* Check if small groups should be split. Return true if no group
2634 contains more than two uses with distinct addr_offsets. Return
2635 false otherwise. We want to split such groups because:
2637 1) Small groups don't have much benefit and may interfer with
2638 general candidate selection.
2639 2) Size for problem with only small groups is usually small and
2640 general algorithm can handle it well.
2642 TODO -- Above claim may not hold when we want to merge memory
2643 accesses with conseuctive addresses. */
2646 split_small_address_groups_p (struct ivopts_data
*data
)
2648 unsigned int i
, j
, distinct
= 1;
2650 struct iv_group
*group
;
2652 for (i
= 0; i
< data
->vgroups
.length (); i
++)
2654 group
= data
->vgroups
[i
];
2655 if (group
->vuses
.length () == 1)
2658 gcc_assert (address_p (group
->type
));
2659 if (group
->vuses
.length () == 2)
2661 if (compare_sizes_for_sort (group
->vuses
[0]->addr_offset
,
2662 group
->vuses
[1]->addr_offset
) > 0)
2663 std::swap (group
->vuses
[0], group
->vuses
[1]);
2666 group
->vuses
.qsort (group_compare_offset
);
2672 for (pre
= group
->vuses
[0], j
= 1; j
< group
->vuses
.length (); j
++)
2674 if (maybe_ne (group
->vuses
[j
]->addr_offset
, pre
->addr_offset
))
2676 pre
= group
->vuses
[j
];
2685 return (distinct
<= 2);
2688 /* For each group of address type uses, this function further groups
2689 these uses according to the maximum offset supported by target's
2690 [base + offset] addressing mode. */
2693 split_address_groups (struct ivopts_data
*data
)
2696 /* Always split group. */
2697 bool split_p
= split_small_address_groups_p (data
);
2699 for (i
= 0; i
< data
->vgroups
.length (); i
++)
2701 struct iv_group
*new_group
= NULL
;
2702 struct iv_group
*group
= data
->vgroups
[i
];
2703 struct iv_use
*use
= group
->vuses
[0];
2706 use
->group_id
= group
->id
;
2707 if (group
->vuses
.length () == 1)
2710 gcc_assert (address_p (use
->type
));
2712 for (j
= 1; j
< group
->vuses
.length ();)
2714 struct iv_use
*next
= group
->vuses
[j
];
2715 poly_int64 offset
= next
->addr_offset
- use
->addr_offset
;
2717 /* Split group if aksed to, or the offset against the first
2718 use can't fit in offset part of addressing mode. IV uses
2719 having the same offset are still kept in one group. */
2720 if (maybe_ne (offset
, 0)
2721 && (split_p
|| !addr_offset_valid_p (use
, offset
)))
2724 new_group
= record_group (data
, group
->type
);
2725 group
->vuses
.ordered_remove (j
);
2726 new_group
->vuses
.safe_push (next
);
2731 next
->group_id
= group
->id
;
2737 /* Finds uses of the induction variables that are interesting. */
2740 find_interesting_uses (struct ivopts_data
*data
, basic_block
*body
)
2743 gimple_stmt_iterator bsi
;
2747 for (i
= 0; i
< data
->current_loop
->num_nodes
; i
++)
2752 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2753 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2754 && !flow_bb_inside_loop_p (data
->current_loop
, e
->dest
))
2755 find_interesting_uses_outside (data
, e
);
2757 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2758 find_interesting_uses_stmt (data
, gsi_stmt (bsi
));
2759 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2760 if (!is_gimple_debug (gsi_stmt (bsi
)))
2761 find_interesting_uses_stmt (data
, gsi_stmt (bsi
));
2764 split_address_groups (data
);
2766 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2768 fprintf (dump_file
, "\n<IV Groups>:\n");
2769 dump_groups (dump_file
, data
);
2770 fprintf (dump_file
, "\n");
2774 /* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
2775 is true, assume we are inside an address. If TOP_COMPREF is true, assume
2776 we are at the top-level of the processed address. */
2779 strip_offset_1 (tree expr
, bool inside_addr
, bool top_compref
,
2782 tree op0
= NULL_TREE
, op1
= NULL_TREE
, tmp
, step
;
2783 enum tree_code code
;
2784 tree type
, orig_type
= TREE_TYPE (expr
);
2785 poly_int64 off0
, off1
;
2787 tree orig_expr
= expr
;
2791 type
= TREE_TYPE (expr
);
2792 code
= TREE_CODE (expr
);
2797 case POINTER_PLUS_EXPR
:
2800 op0
= TREE_OPERAND (expr
, 0);
2801 op1
= TREE_OPERAND (expr
, 1);
2803 op0
= strip_offset_1 (op0
, false, false, &off0
);
2804 op1
= strip_offset_1 (op1
, false, false, &off1
);
2806 *offset
= (code
== MINUS_EXPR
? off0
- off1
: off0
+ off1
);
2807 if (op0
== TREE_OPERAND (expr
, 0)
2808 && op1
== TREE_OPERAND (expr
, 1))
2811 if (integer_zerop (op1
))
2813 else if (integer_zerop (op0
))
2815 if (code
== MINUS_EXPR
)
2816 expr
= fold_build1 (NEGATE_EXPR
, type
, op1
);
2821 expr
= fold_build2 (code
, type
, op0
, op1
);
2823 return fold_convert (orig_type
, expr
);
2826 op1
= TREE_OPERAND (expr
, 1);
2827 if (!cst_and_fits_in_hwi (op1
))
2830 op0
= TREE_OPERAND (expr
, 0);
2831 op0
= strip_offset_1 (op0
, false, false, &off0
);
2832 if (op0
== TREE_OPERAND (expr
, 0))
2835 *offset
= off0
* int_cst_value (op1
);
2836 if (integer_zerop (op0
))
2839 expr
= fold_build2 (MULT_EXPR
, type
, op0
, op1
);
2841 return fold_convert (orig_type
, expr
);
2844 case ARRAY_RANGE_REF
:
2848 step
= array_ref_element_size (expr
);
2849 if (!cst_and_fits_in_hwi (step
))
2852 st
= int_cst_value (step
);
2853 op1
= TREE_OPERAND (expr
, 1);
2854 op1
= strip_offset_1 (op1
, false, false, &off1
);
2855 *offset
= off1
* st
;
2858 && integer_zerop (op1
))
2860 /* Strip the component reference completely. */
2861 op0
= TREE_OPERAND (expr
, 0);
2862 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
2875 tmp
= component_ref_field_offset (expr
);
2876 field
= TREE_OPERAND (expr
, 1);
2878 && cst_and_fits_in_hwi (tmp
)
2879 && cst_and_fits_in_hwi (DECL_FIELD_BIT_OFFSET (field
)))
2881 HOST_WIDE_INT boffset
, abs_off
;
2883 /* Strip the component reference completely. */
2884 op0
= TREE_OPERAND (expr
, 0);
2885 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
2886 boffset
= int_cst_value (DECL_FIELD_BIT_OFFSET (field
));
2887 abs_off
= abs_hwi (boffset
) / BITS_PER_UNIT
;
2891 *offset
= off0
+ int_cst_value (tmp
) + abs_off
;
2898 op0
= TREE_OPERAND (expr
, 0);
2899 op0
= strip_offset_1 (op0
, true, true, &off0
);
2902 if (op0
== TREE_OPERAND (expr
, 0))
2905 expr
= build_fold_addr_expr (op0
);
2906 return fold_convert (orig_type
, expr
);
2909 /* ??? Offset operand? */
2910 inside_addr
= false;
2914 if (ptrdiff_tree_p (expr
, offset
) && maybe_ne (*offset
, 0))
2915 return build_int_cst (orig_type
, 0);
2919 /* Default handling of expressions for that we want to recurse into
2920 the first operand. */
2921 op0
= TREE_OPERAND (expr
, 0);
2922 op0
= strip_offset_1 (op0
, inside_addr
, false, &off0
);
2925 if (op0
== TREE_OPERAND (expr
, 0)
2926 && (!op1
|| op1
== TREE_OPERAND (expr
, 1)))
2929 expr
= copy_node (expr
);
2930 TREE_OPERAND (expr
, 0) = op0
;
2932 TREE_OPERAND (expr
, 1) = op1
;
2934 /* Inside address, we might strip the top level component references,
2935 thus changing type of the expression. Handling of ADDR_EXPR
2937 expr
= fold_convert (orig_type
, expr
);
2942 /* Strips constant offsets from EXPR and stores them to OFFSET. */
2945 strip_offset (tree expr
, poly_uint64_pod
*offset
)
2948 tree core
= strip_offset_1 (expr
, false, false, &off
);
2953 /* Returns variant of TYPE that can be used as base for different uses.
2954 We return unsigned type with the same precision, which avoids problems
2958 generic_type_for (tree type
)
2960 if (POINTER_TYPE_P (type
))
2961 return unsigned_type_for (type
);
2963 if (TYPE_UNSIGNED (type
))
2966 return unsigned_type_for (type
);
2969 /* Private data for walk_tree. */
2971 struct walk_tree_data
2974 struct ivopts_data
*idata
;
2977 /* Callback function for walk_tree, it records invariants and symbol
2978 reference in *EXPR_P. DATA is the structure storing result info. */
2981 find_inv_vars_cb (tree
*expr_p
, int *ws ATTRIBUTE_UNUSED
, void *data
)
2984 struct version_info
*info
;
2985 struct walk_tree_data
*wdata
= (struct walk_tree_data
*) data
;
2987 if (TREE_CODE (op
) != SSA_NAME
)
2990 info
= name_info (wdata
->idata
, op
);
2991 /* Because we expand simple operations when finding IVs, loop invariant
2992 variable that isn't referred by the original loop could be used now.
2993 Record such invariant variables here. */
2996 struct ivopts_data
*idata
= wdata
->idata
;
2997 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (op
));
2999 if (!bb
|| !flow_bb_inside_loop_p (idata
->current_loop
, bb
))
3001 tree steptype
= TREE_TYPE (op
);
3002 if (POINTER_TYPE_P (steptype
))
3003 steptype
= sizetype
;
3004 set_iv (idata
, op
, op
, build_int_cst (steptype
, 0), true);
3005 record_invariant (idata
, op
, false);
3008 if (!info
->inv_id
|| info
->has_nonlin_use
)
3011 if (!*wdata
->inv_vars
)
3012 *wdata
->inv_vars
= BITMAP_ALLOC (NULL
);
3013 bitmap_set_bit (*wdata
->inv_vars
, info
->inv_id
);
3018 /* Records invariants in *EXPR_P. INV_VARS is the bitmap to that we should
3022 find_inv_vars (struct ivopts_data
*data
, tree
*expr_p
, bitmap
*inv_vars
)
3024 struct walk_tree_data wdata
;
3030 wdata
.inv_vars
= inv_vars
;
3031 walk_tree (expr_p
, find_inv_vars_cb
, &wdata
, NULL
);
3034 /* Get entry from invariant expr hash table for INV_EXPR. New entry
3035 will be recorded if it doesn't exist yet. Given below two exprs:
3036 inv_expr + cst1, inv_expr + cst2
3037 It's hard to make decision whether constant part should be stripped
3038 or not. We choose to not strip based on below facts:
3039 1) We need to count ADD cost for constant part if it's stripped,
3040 which isn't always trivial where this functions is called.
3041 2) Stripping constant away may be conflict with following loop
3042 invariant hoisting pass.
3043 3) Not stripping constant away results in more invariant exprs,
3044 which usually leads to decision preferring lower reg pressure. */
3046 static iv_inv_expr_ent
*
3047 get_loop_invariant_expr (struct ivopts_data
*data
, tree inv_expr
)
3049 STRIP_NOPS (inv_expr
);
3051 if (poly_int_tree_p (inv_expr
)
3052 || TREE_CODE (inv_expr
) == SSA_NAME
)
3055 /* Don't strip constant part away as we used to. */
3057 /* Stores EXPR in DATA->inv_expr_tab, return pointer to iv_inv_expr_ent. */
3058 struct iv_inv_expr_ent ent
;
3059 ent
.expr
= inv_expr
;
3060 ent
.hash
= iterative_hash_expr (inv_expr
, 0);
3061 struct iv_inv_expr_ent
**slot
= data
->inv_expr_tab
->find_slot (&ent
, INSERT
);
3065 *slot
= XNEW (struct iv_inv_expr_ent
);
3066 (*slot
)->expr
= inv_expr
;
3067 (*slot
)->hash
= ent
.hash
;
3068 (*slot
)->id
= ++data
->max_inv_expr_id
;
3074 /* Find the first undefined SSA name in *TP. */
3077 find_ssa_undef (tree
*tp
, int *walk_subtrees
, void *)
3079 if (TREE_CODE (*tp
) == SSA_NAME
3080 && ssa_undefined_value_p (*tp
, false))
3087 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
3088 position to POS. If USE is not NULL, the candidate is set as related to
3089 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
3090 replacement of the final value of the iv by a direct computation. */
3092 static struct iv_cand
*
3093 add_candidate_1 (struct ivopts_data
*data
, tree base
, tree step
, bool important
,
3094 enum iv_position pos
, struct iv_use
*use
,
3095 gimple
*incremented_at
, struct iv
*orig_iv
= NULL
,
3096 bool doloop
= false)
3099 struct iv_cand
*cand
= NULL
;
3100 tree type
, orig_type
;
3102 gcc_assert (base
&& step
);
3104 /* -fkeep-gc-roots-live means that we have to keep a real pointer
3105 live, but the ivopts code may replace a real pointer with one
3106 pointing before or after the memory block that is then adjusted
3107 into the memory block during the loop. FIXME: It would likely be
3108 better to actually force the pointer live and still use ivopts;
3109 for example, it would be enough to write the pointer into memory
3110 and keep it there until after the loop. */
3111 if (flag_keep_gc_roots_live
&& POINTER_TYPE_P (TREE_TYPE (base
)))
3114 /* If BASE contains undefined SSA names make sure we only record
3116 bool involves_undefs
= false;
3117 if (walk_tree (&base
, find_ssa_undef
, NULL
, NULL
))
3119 if (pos
!= IP_ORIGINAL
)
3122 involves_undefs
= true;
3125 /* For non-original variables, make sure their values are computed in a type
3126 that does not invoke undefined behavior on overflows (since in general,
3127 we cannot prove that these induction variables are non-wrapping). */
3128 if (pos
!= IP_ORIGINAL
)
3130 orig_type
= TREE_TYPE (base
);
3131 type
= generic_type_for (orig_type
);
3132 if (type
!= orig_type
)
3134 base
= fold_convert (type
, base
);
3135 step
= fold_convert (type
, step
);
3139 for (i
= 0; i
< data
->vcands
.length (); i
++)
3141 cand
= data
->vcands
[i
];
3143 if (cand
->pos
!= pos
)
3146 if (cand
->incremented_at
!= incremented_at
3147 || ((pos
== IP_AFTER_USE
|| pos
== IP_BEFORE_USE
)
3148 && cand
->ainc_use
!= use
))
3151 if (operand_equal_p (base
, cand
->iv
->base
, 0)
3152 && operand_equal_p (step
, cand
->iv
->step
, 0)
3153 && (TYPE_PRECISION (TREE_TYPE (base
))
3154 == TYPE_PRECISION (TREE_TYPE (cand
->iv
->base
))))
3158 if (i
== data
->vcands
.length ())
3160 cand
= XCNEW (struct iv_cand
);
3162 cand
->iv
= alloc_iv (data
, base
, step
);
3164 if (pos
!= IP_ORIGINAL
)
3167 cand
->var_before
= create_tmp_var_raw (TREE_TYPE (base
), "doloop");
3169 cand
->var_before
= create_tmp_var_raw (TREE_TYPE (base
), "ivtmp");
3170 cand
->var_after
= cand
->var_before
;
3172 cand
->important
= important
;
3173 cand
->involves_undefs
= involves_undefs
;
3174 cand
->incremented_at
= incremented_at
;
3175 cand
->doloop_p
= doloop
;
3176 data
->vcands
.safe_push (cand
);
3178 if (!poly_int_tree_p (step
))
3180 find_inv_vars (data
, &step
, &cand
->inv_vars
);
3182 iv_inv_expr_ent
*inv_expr
= get_loop_invariant_expr (data
, step
);
3183 /* Share bitmap between inv_vars and inv_exprs for cand. */
3184 if (inv_expr
!= NULL
)
3186 cand
->inv_exprs
= cand
->inv_vars
;
3187 cand
->inv_vars
= NULL
;
3188 if (cand
->inv_exprs
)
3189 bitmap_clear (cand
->inv_exprs
);
3191 cand
->inv_exprs
= BITMAP_ALLOC (NULL
);
3193 bitmap_set_bit (cand
->inv_exprs
, inv_expr
->id
);
3197 if (pos
== IP_AFTER_USE
|| pos
== IP_BEFORE_USE
)
3198 cand
->ainc_use
= use
;
3200 cand
->ainc_use
= NULL
;
3202 cand
->orig_iv
= orig_iv
;
3203 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3204 dump_cand (dump_file
, cand
);
3207 cand
->important
|= important
;
3208 cand
->doloop_p
|= doloop
;
3210 /* Relate candidate to the group for which it is added. */
3212 bitmap_set_bit (data
->vgroups
[use
->group_id
]->related_cands
, i
);
3217 /* Returns true if incrementing the induction variable at the end of the LOOP
3220 The purpose is to avoid splitting latch edge with a biv increment, thus
3221 creating a jump, possibly confusing other optimization passes and leaving
3222 less freedom to scheduler. So we allow IP_END only if IP_NORMAL is not
3223 available (so we do not have a better alternative), or if the latch edge
3224 is already nonempty. */
3227 allow_ip_end_pos_p (class loop
*loop
)
3229 if (!ip_normal_pos (loop
))
3232 if (!empty_block_p (ip_end_pos (loop
)))
3238 /* If possible, adds autoincrement candidates BASE + STEP * i based on use USE.
3239 Important field is set to IMPORTANT. */
3242 add_autoinc_candidates (struct ivopts_data
*data
, tree base
, tree step
,
3243 bool important
, struct iv_use
*use
)
3245 basic_block use_bb
= gimple_bb (use
->stmt
);
3246 machine_mode mem_mode
;
3247 unsigned HOST_WIDE_INT cstepi
;
3249 /* If we insert the increment in any position other than the standard
3250 ones, we must ensure that it is incremented once per iteration.
3251 It must not be in an inner nested loop, or one side of an if
3253 if (use_bb
->loop_father
!= data
->current_loop
3254 || !dominated_by_p (CDI_DOMINATORS
, data
->current_loop
->latch
, use_bb
)
3255 || stmt_can_throw_internal (cfun
, use
->stmt
)
3256 || !cst_and_fits_in_hwi (step
))
3259 cstepi
= int_cst_value (step
);
3261 mem_mode
= TYPE_MODE (use
->mem_type
);
3262 if (((USE_LOAD_PRE_INCREMENT (mem_mode
)
3263 || USE_STORE_PRE_INCREMENT (mem_mode
))
3264 && known_eq (GET_MODE_SIZE (mem_mode
), cstepi
))
3265 || ((USE_LOAD_PRE_DECREMENT (mem_mode
)
3266 || USE_STORE_PRE_DECREMENT (mem_mode
))
3267 && known_eq (GET_MODE_SIZE (mem_mode
), -cstepi
)))
3269 enum tree_code code
= MINUS_EXPR
;
3271 tree new_step
= step
;
3273 if (POINTER_TYPE_P (TREE_TYPE (base
)))
3275 new_step
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (step
), step
);
3276 code
= POINTER_PLUS_EXPR
;
3279 new_step
= fold_convert (TREE_TYPE (base
), new_step
);
3280 new_base
= fold_build2 (code
, TREE_TYPE (base
), base
, new_step
);
3281 add_candidate_1 (data
, new_base
, step
, important
, IP_BEFORE_USE
, use
,
3284 if (((USE_LOAD_POST_INCREMENT (mem_mode
)
3285 || USE_STORE_POST_INCREMENT (mem_mode
))
3286 && known_eq (GET_MODE_SIZE (mem_mode
), cstepi
))
3287 || ((USE_LOAD_POST_DECREMENT (mem_mode
)
3288 || USE_STORE_POST_DECREMENT (mem_mode
))
3289 && known_eq (GET_MODE_SIZE (mem_mode
), -cstepi
)))
3291 add_candidate_1 (data
, base
, step
, important
, IP_AFTER_USE
, use
,
3296 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
3297 position to POS. If USE is not NULL, the candidate is set as related to
3298 it. The candidate computation is scheduled before exit condition and at
3302 add_candidate (struct ivopts_data
*data
, tree base
, tree step
, bool important
,
3303 struct iv_use
*use
, struct iv
*orig_iv
= NULL
,
3304 bool doloop
= false)
3306 if (ip_normal_pos (data
->current_loop
))
3307 add_candidate_1 (data
, base
, step
, important
, IP_NORMAL
, use
, NULL
, orig_iv
,
3309 /* Exclude doloop candidate here since it requires decrement then comparison
3310 and jump, the IP_END position doesn't match. */
3311 if (!doloop
&& ip_end_pos (data
->current_loop
)
3312 && allow_ip_end_pos_p (data
->current_loop
))
3313 add_candidate_1 (data
, base
, step
, important
, IP_END
, use
, NULL
, orig_iv
);
3316 /* Adds standard iv candidates. */
3319 add_standard_iv_candidates (struct ivopts_data
*data
)
3321 add_candidate (data
, integer_zero_node
, integer_one_node
, true, NULL
);
3323 /* The same for a double-integer type if it is still fast enough. */
3325 (long_integer_type_node
) > TYPE_PRECISION (integer_type_node
)
3326 && TYPE_PRECISION (long_integer_type_node
) <= BITS_PER_WORD
)
3327 add_candidate (data
, build_int_cst (long_integer_type_node
, 0),
3328 build_int_cst (long_integer_type_node
, 1), true, NULL
);
3330 /* The same for a double-integer type if it is still fast enough. */
3332 (long_long_integer_type_node
) > TYPE_PRECISION (long_integer_type_node
)
3333 && TYPE_PRECISION (long_long_integer_type_node
) <= BITS_PER_WORD
)
3334 add_candidate (data
, build_int_cst (long_long_integer_type_node
, 0),
3335 build_int_cst (long_long_integer_type_node
, 1), true, NULL
);
3339 /* Adds candidates bases on the old induction variable IV. */
3342 add_iv_candidate_for_biv (struct ivopts_data
*data
, struct iv
*iv
)
3346 struct iv_cand
*cand
;
3348 /* Check if this biv is used in address type use. */
3349 if (iv
->no_overflow
&& iv
->have_address_use
3350 && INTEGRAL_TYPE_P (TREE_TYPE (iv
->base
))
3351 && TYPE_PRECISION (TREE_TYPE (iv
->base
)) < TYPE_PRECISION (sizetype
))
3353 tree base
= fold_convert (sizetype
, iv
->base
);
3354 tree step
= fold_convert (sizetype
, iv
->step
);
3356 /* Add iv cand of same precision as index part in TARGET_MEM_REF. */
3357 add_candidate (data
, base
, step
, true, NULL
, iv
);
3358 /* Add iv cand of the original type only if it has nonlinear use. */
3360 add_candidate (data
, iv
->base
, iv
->step
, true, NULL
);
3363 add_candidate (data
, iv
->base
, iv
->step
, true, NULL
);
3365 /* The same, but with initial value zero. */
3366 if (POINTER_TYPE_P (TREE_TYPE (iv
->base
)))
3367 add_candidate (data
, size_int (0), iv
->step
, true, NULL
);
3369 add_candidate (data
, build_int_cst (TREE_TYPE (iv
->base
), 0),
3370 iv
->step
, true, NULL
);
3372 phi
= SSA_NAME_DEF_STMT (iv
->ssa_name
);
3373 if (gimple_code (phi
) == GIMPLE_PHI
)
3375 /* Additionally record the possibility of leaving the original iv
3377 def
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (data
->current_loop
));
3378 /* Don't add candidate if it's from another PHI node because
3379 it's an affine iv appearing in the form of PEELED_CHREC. */
3380 phi
= SSA_NAME_DEF_STMT (def
);
3381 if (gimple_code (phi
) != GIMPLE_PHI
)
3383 cand
= add_candidate_1 (data
,
3384 iv
->base
, iv
->step
, true, IP_ORIGINAL
, NULL
,
3385 SSA_NAME_DEF_STMT (def
));
3388 cand
->var_before
= iv
->ssa_name
;
3389 cand
->var_after
= def
;
3393 gcc_assert (gimple_bb (phi
) == data
->current_loop
->header
);
3397 /* Adds candidates based on the old induction variables. */
3400 add_iv_candidate_for_bivs (struct ivopts_data
*data
)
3406 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
3408 iv
= ver_info (data
, i
)->iv
;
3409 if (iv
&& iv
->biv_p
&& !integer_zerop (iv
->step
))
3410 add_iv_candidate_for_biv (data
, iv
);
3414 /* Record common candidate {BASE, STEP} derived from USE in hashtable. */
3417 record_common_cand (struct ivopts_data
*data
, tree base
,
3418 tree step
, struct iv_use
*use
)
3420 class iv_common_cand ent
;
3421 class iv_common_cand
**slot
;
3425 ent
.hash
= iterative_hash_expr (base
, 0);
3426 ent
.hash
= iterative_hash_expr (step
, ent
.hash
);
3428 slot
= data
->iv_common_cand_tab
->find_slot (&ent
, INSERT
);
3431 *slot
= new iv_common_cand ();
3432 (*slot
)->base
= base
;
3433 (*slot
)->step
= step
;
3434 (*slot
)->uses
.create (8);
3435 (*slot
)->hash
= ent
.hash
;
3436 data
->iv_common_cands
.safe_push ((*slot
));
3439 gcc_assert (use
!= NULL
);
3440 (*slot
)->uses
.safe_push (use
);
3444 /* Comparison function used to sort common candidates. */
3447 common_cand_cmp (const void *p1
, const void *p2
)
3450 const class iv_common_cand
*const *const ccand1
3451 = (const class iv_common_cand
*const *)p1
;
3452 const class iv_common_cand
*const *const ccand2
3453 = (const class iv_common_cand
*const *)p2
;
3455 n1
= (*ccand1
)->uses
.length ();
3456 n2
= (*ccand2
)->uses
.length ();
3460 /* Adds IV candidates based on common candidated recorded. */
3463 add_iv_candidate_derived_from_uses (struct ivopts_data
*data
)
3466 struct iv_cand
*cand_1
, *cand_2
;
3468 data
->iv_common_cands
.qsort (common_cand_cmp
);
3469 for (i
= 0; i
< data
->iv_common_cands
.length (); i
++)
3471 class iv_common_cand
*ptr
= data
->iv_common_cands
[i
];
3473 /* Only add IV candidate if it's derived from multiple uses. */
3474 if (ptr
->uses
.length () <= 1)
3479 if (ip_normal_pos (data
->current_loop
))
3480 cand_1
= add_candidate_1 (data
, ptr
->base
, ptr
->step
,
3481 false, IP_NORMAL
, NULL
, NULL
);
3483 if (ip_end_pos (data
->current_loop
)
3484 && allow_ip_end_pos_p (data
->current_loop
))
3485 cand_2
= add_candidate_1 (data
, ptr
->base
, ptr
->step
,
3486 false, IP_END
, NULL
, NULL
);
3488 /* Bind deriving uses and the new candidates. */
3489 for (j
= 0; j
< ptr
->uses
.length (); j
++)
3491 struct iv_group
*group
= data
->vgroups
[ptr
->uses
[j
]->group_id
];
3493 bitmap_set_bit (group
->related_cands
, cand_1
->id
);
3495 bitmap_set_bit (group
->related_cands
, cand_2
->id
);
3499 /* Release data since it is useless from this point. */
3500 data
->iv_common_cand_tab
->empty ();
3501 data
->iv_common_cands
.truncate (0);
3504 /* Adds candidates based on the value of USE's iv. */
3507 add_iv_candidate_for_use (struct ivopts_data
*data
, struct iv_use
*use
)
3511 struct iv
*iv
= use
->iv
;
3512 tree basetype
= TREE_TYPE (iv
->base
);
3514 /* Don't add candidate for iv_use with non integer, pointer or non-mode
3515 precision types, instead, add candidate for the corresponding scev in
3516 unsigned type with the same precision. See PR93674 for more info. */
3517 if ((TREE_CODE (basetype
) != INTEGER_TYPE
&& !POINTER_TYPE_P (basetype
))
3518 || !type_has_mode_precision_p (basetype
))
3520 basetype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (basetype
),
3521 TYPE_UNSIGNED (basetype
));
3522 add_candidate (data
, fold_convert (basetype
, iv
->base
),
3523 fold_convert (basetype
, iv
->step
), false, NULL
);
3527 add_candidate (data
, iv
->base
, iv
->step
, false, use
);
3529 /* Record common candidate for use in case it can be shared by others. */
3530 record_common_cand (data
, iv
->base
, iv
->step
, use
);
3532 /* Record common candidate with initial value zero. */
3533 basetype
= TREE_TYPE (iv
->base
);
3534 if (POINTER_TYPE_P (basetype
))
3535 basetype
= sizetype
;
3536 record_common_cand (data
, build_int_cst (basetype
, 0), iv
->step
, use
);
3538 /* Compare the cost of an address with an unscaled index with the cost of
3539 an address with a scaled index and add candidate if useful. */
3542 && poly_int_tree_p (iv
->step
, &step
)
3543 && address_p (use
->type
))
3545 poly_int64 new_step
;
3546 unsigned int fact
= preferred_mem_scale_factor
3548 TYPE_MODE (use
->mem_type
),
3549 optimize_loop_for_speed_p (data
->current_loop
));
3552 && multiple_p (step
, fact
, &new_step
))
3553 add_candidate (data
, size_int (0),
3554 wide_int_to_tree (sizetype
, new_step
),
3558 /* Record common candidate with constant offset stripped in base.
3559 Like the use itself, we also add candidate directly for it. */
3560 base
= strip_offset (iv
->base
, &offset
);
3561 if (maybe_ne (offset
, 0U) || base
!= iv
->base
)
3563 record_common_cand (data
, base
, iv
->step
, use
);
3564 add_candidate (data
, base
, iv
->step
, false, use
);
3567 /* Record common candidate with base_object removed in base. */
3570 if (iv
->base_object
!= NULL
&& TREE_CODE (base
) == POINTER_PLUS_EXPR
)
3572 tree step
= iv
->step
;
3575 base
= TREE_OPERAND (base
, 1);
3576 step
= fold_convert (sizetype
, step
);
3577 record_common_cand (data
, base
, step
, use
);
3578 /* Also record common candidate with offset stripped. */
3579 base
= strip_offset (base
, &offset
);
3580 if (maybe_ne (offset
, 0U))
3581 record_common_cand (data
, base
, step
, use
);
3584 /* At last, add auto-incremental candidates. Make such variables
3585 important since other iv uses with same base object may be based
3587 if (use
!= NULL
&& address_p (use
->type
))
3588 add_autoinc_candidates (data
, iv
->base
, iv
->step
, true, use
);
3591 /* Adds candidates based on the uses. */
3594 add_iv_candidate_for_groups (struct ivopts_data
*data
)
3598 /* Only add candidate for the first use in group. */
3599 for (i
= 0; i
< data
->vgroups
.length (); i
++)
3601 struct iv_group
*group
= data
->vgroups
[i
];
3603 gcc_assert (group
->vuses
[0] != NULL
);
3604 add_iv_candidate_for_use (data
, group
->vuses
[0]);
3606 add_iv_candidate_derived_from_uses (data
);
3609 /* Record important candidates and add them to related_cands bitmaps. */
3612 record_important_candidates (struct ivopts_data
*data
)
3615 struct iv_group
*group
;
3617 for (i
= 0; i
< data
->vcands
.length (); i
++)
3619 struct iv_cand
*cand
= data
->vcands
[i
];
3621 if (cand
->important
)
3622 bitmap_set_bit (data
->important_candidates
, i
);
3625 data
->consider_all_candidates
= (data
->vcands
.length ()
3626 <= CONSIDER_ALL_CANDIDATES_BOUND
);
3628 /* Add important candidates to groups' related_cands bitmaps. */
3629 for (i
= 0; i
< data
->vgroups
.length (); i
++)
3631 group
= data
->vgroups
[i
];
3632 bitmap_ior_into (group
->related_cands
, data
->important_candidates
);
3636 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
3637 If consider_all_candidates is true, we use a two-dimensional array, otherwise
3638 we allocate a simple list to every use. */
3641 alloc_use_cost_map (struct ivopts_data
*data
)
3643 unsigned i
, size
, s
;
3645 for (i
= 0; i
< data
->vgroups
.length (); i
++)
3647 struct iv_group
*group
= data
->vgroups
[i
];
3649 if (data
->consider_all_candidates
)
3650 size
= data
->vcands
.length ();
3653 s
= bitmap_count_bits (group
->related_cands
);
3655 /* Round up to the power of two, so that moduling by it is fast. */
3656 size
= s
? (1 << ceil_log2 (s
)) : 1;
3659 group
->n_map_members
= size
;
3660 group
->cost_map
= XCNEWVEC (class cost_pair
, size
);
3664 /* Sets cost of (GROUP, CAND) pair to COST and record that it depends
3665 on invariants INV_VARS and that the value used in expressing it is
3666 VALUE, and in case of iv elimination the comparison operator is COMP. */
3669 set_group_iv_cost (struct ivopts_data
*data
,
3670 struct iv_group
*group
, struct iv_cand
*cand
,
3671 comp_cost cost
, bitmap inv_vars
, tree value
,
3672 enum tree_code comp
, bitmap inv_exprs
)
3676 if (cost
.infinite_cost_p ())
3678 BITMAP_FREE (inv_vars
);
3679 BITMAP_FREE (inv_exprs
);
3683 if (data
->consider_all_candidates
)
3685 group
->cost_map
[cand
->id
].cand
= cand
;
3686 group
->cost_map
[cand
->id
].cost
= cost
;
3687 group
->cost_map
[cand
->id
].inv_vars
= inv_vars
;
3688 group
->cost_map
[cand
->id
].inv_exprs
= inv_exprs
;
3689 group
->cost_map
[cand
->id
].value
= value
;
3690 group
->cost_map
[cand
->id
].comp
= comp
;
3694 /* n_map_members is a power of two, so this computes modulo. */
3695 s
= cand
->id
& (group
->n_map_members
- 1);
3696 for (i
= s
; i
< group
->n_map_members
; i
++)
3697 if (!group
->cost_map
[i
].cand
)
3699 for (i
= 0; i
< s
; i
++)
3700 if (!group
->cost_map
[i
].cand
)
3706 group
->cost_map
[i
].cand
= cand
;
3707 group
->cost_map
[i
].cost
= cost
;
3708 group
->cost_map
[i
].inv_vars
= inv_vars
;
3709 group
->cost_map
[i
].inv_exprs
= inv_exprs
;
3710 group
->cost_map
[i
].value
= value
;
3711 group
->cost_map
[i
].comp
= comp
;
3714 /* Gets cost of (GROUP, CAND) pair. */
3716 static class cost_pair
*
3717 get_group_iv_cost (struct ivopts_data
*data
, struct iv_group
*group
,
3718 struct iv_cand
*cand
)
3721 class cost_pair
*ret
;
3726 if (data
->consider_all_candidates
)
3728 ret
= group
->cost_map
+ cand
->id
;
3735 /* n_map_members is a power of two, so this computes modulo. */
3736 s
= cand
->id
& (group
->n_map_members
- 1);
3737 for (i
= s
; i
< group
->n_map_members
; i
++)
3738 if (group
->cost_map
[i
].cand
== cand
)
3739 return group
->cost_map
+ i
;
3740 else if (group
->cost_map
[i
].cand
== NULL
)
3742 for (i
= 0; i
< s
; i
++)
3743 if (group
->cost_map
[i
].cand
== cand
)
3744 return group
->cost_map
+ i
;
3745 else if (group
->cost_map
[i
].cand
== NULL
)
3751 /* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
3753 produce_memory_decl_rtl (tree obj
, int *regno
)
3755 addr_space_t as
= TYPE_ADDR_SPACE (TREE_TYPE (obj
));
3756 machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
3760 if (TREE_STATIC (obj
) || DECL_EXTERNAL (obj
))
3762 const char *name
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj
));
3763 x
= gen_rtx_SYMBOL_REF (address_mode
, name
);
3764 SET_SYMBOL_REF_DECL (x
, obj
);
3765 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
3766 set_mem_addr_space (x
, as
);
3767 targetm
.encode_section_info (obj
, x
, true);
3771 x
= gen_raw_REG (address_mode
, (*regno
)++);
3772 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
3773 set_mem_addr_space (x
, as
);
3779 /* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
3780 walk_tree. DATA contains the actual fake register number. */
3783 prepare_decl_rtl (tree
*expr_p
, int *ws
, void *data
)
3785 tree obj
= NULL_TREE
;
3787 int *regno
= (int *) data
;
3789 switch (TREE_CODE (*expr_p
))
3792 for (expr_p
= &TREE_OPERAND (*expr_p
, 0);
3793 handled_component_p (*expr_p
);
3794 expr_p
= &TREE_OPERAND (*expr_p
, 0))
3797 if (DECL_P (obj
) && HAS_RTL_P (obj
) && !DECL_RTL_SET_P (obj
))
3798 x
= produce_memory_decl_rtl (obj
, regno
);
3803 obj
= SSA_NAME_VAR (*expr_p
);
3804 /* Defer handling of anonymous SSA_NAMEs to the expander. */
3807 if (!DECL_RTL_SET_P (obj
))
3808 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
3817 if (DECL_RTL_SET_P (obj
))
3820 if (DECL_MODE (obj
) == BLKmode
)
3821 x
= produce_memory_decl_rtl (obj
, regno
);
3823 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
3833 decl_rtl_to_reset
.safe_push (obj
);
3834 SET_DECL_RTL (obj
, x
);
3840 /* Predict whether the given loop will be transformed in the RTL
3841 doloop_optimize pass. Attempt to duplicate some doloop_optimize checks.
3842 This is only for target independent checks, see targetm.predict_doloop_p
3843 for the target dependent ones.
3845 Note that according to some initial investigation, some checks like costly
3846 niter check and invalid stmt scanning don't have much gains among general
3847 cases, so keep this as simple as possible first.
3849 Some RTL specific checks seems unable to be checked in gimple, if any new
3850 checks or easy checks _are_ missing here, please add them. */
3853 generic_predict_doloop_p (struct ivopts_data
*data
)
3855 class loop
*loop
= data
->current_loop
;
3857 /* Call target hook for target dependent checks. */
3858 if (!targetm
.predict_doloop_p (loop
))
3860 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3861 fprintf (dump_file
, "Predict doloop failure due to"
3862 " target specific checks.\n");
3866 /* Similar to doloop_optimize, check iteration description to know it's
3867 suitable or not. Keep it as simple as possible, feel free to extend it
3868 if you find any multiple exits cases matter. */
3869 edge exit
= single_dom_exit (loop
);
3870 class tree_niter_desc
*niter_desc
;
3871 if (!exit
|| !(niter_desc
= niter_for_exit (data
, exit
)))
3873 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3874 fprintf (dump_file
, "Predict doloop failure due to"
3875 " unexpected niters.\n");
3879 /* Similar to doloop_optimize, check whether iteration count too small
3880 and not profitable. */
3881 HOST_WIDE_INT est_niter
= get_estimated_loop_iterations_int (loop
);
3882 if (est_niter
== -1)
3883 est_niter
= get_likely_max_loop_iterations_int (loop
);
3884 if (est_niter
>= 0 && est_niter
< 3)
3886 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3888 "Predict doloop failure due to"
3889 " too few iterations (%u).\n",
3890 (unsigned int) est_niter
);
3897 /* Determines cost of the computation of EXPR. */
3900 computation_cost (tree expr
, bool speed
)
3904 tree type
= TREE_TYPE (expr
);
3906 /* Avoid using hard regs in ways which may be unsupported. */
3907 int regno
= LAST_VIRTUAL_REGISTER
+ 1;
3908 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
3909 enum node_frequency real_frequency
= node
->frequency
;
3911 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3912 crtl
->maybe_hot_insn_p
= speed
;
3913 walk_tree (&expr
, prepare_decl_rtl
, ®no
, NULL
);
3915 rslt
= expand_expr (expr
, NULL_RTX
, TYPE_MODE (type
), EXPAND_NORMAL
);
3918 default_rtl_profile ();
3919 node
->frequency
= real_frequency
;
3921 cost
= seq_cost (seq
, speed
);
3923 cost
+= address_cost (XEXP (rslt
, 0), TYPE_MODE (type
),
3924 TYPE_ADDR_SPACE (type
), speed
);
3925 else if (!REG_P (rslt
))
3926 cost
+= set_src_cost (rslt
, TYPE_MODE (type
), speed
);
3931 /* Returns variable containing the value of candidate CAND at statement AT. */
3934 var_at_stmt (class loop
*loop
, struct iv_cand
*cand
, gimple
*stmt
)
3936 if (stmt_after_increment (loop
, cand
, stmt
))
3937 return cand
->var_after
;
3939 return cand
->var_before
;
3942 /* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
3943 same precision that is at least as wide as the precision of TYPE, stores
3944 BA to A and BB to B, and returns the type of BA. Otherwise, returns the
3948 determine_common_wider_type (tree
*a
, tree
*b
)
3950 tree wider_type
= NULL
;
3952 tree atype
= TREE_TYPE (*a
);
3954 if (CONVERT_EXPR_P (*a
))
3956 suba
= TREE_OPERAND (*a
, 0);
3957 wider_type
= TREE_TYPE (suba
);
3958 if (TYPE_PRECISION (wider_type
) < TYPE_PRECISION (atype
))
3964 if (CONVERT_EXPR_P (*b
))
3966 subb
= TREE_OPERAND (*b
, 0);
3967 if (TYPE_PRECISION (wider_type
) != TYPE_PRECISION (TREE_TYPE (subb
)))
3978 /* Determines the expression by that USE is expressed from induction variable
3979 CAND at statement AT in LOOP. The expression is stored in two parts in a
3980 decomposed form. The invariant part is stored in AFF_INV; while variant
3981 part in AFF_VAR. Store ratio of CAND.step over USE.step in PRAT if it's
3982 non-null. Returns false if USE cannot be expressed using CAND. */
3985 get_computation_aff_1 (class loop
*loop
, gimple
*at
, struct iv_use
*use
,
3986 struct iv_cand
*cand
, class aff_tree
*aff_inv
,
3987 class aff_tree
*aff_var
, widest_int
*prat
= NULL
)
3989 tree ubase
= use
->iv
->base
, ustep
= use
->iv
->step
;
3990 tree cbase
= cand
->iv
->base
, cstep
= cand
->iv
->step
;
3991 tree common_type
, uutype
, var
, cstep_common
;
3992 tree utype
= TREE_TYPE (ubase
), ctype
= TREE_TYPE (cbase
);
3996 /* We must have a precision to express the values of use. */
3997 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
4000 var
= var_at_stmt (loop
, cand
, at
);
4001 uutype
= unsigned_type_for (utype
);
4003 /* If the conversion is not noop, perform it. */
4004 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
4006 if (cand
->orig_iv
!= NULL
&& CONVERT_EXPR_P (cbase
)
4007 && (CONVERT_EXPR_P (cstep
) || poly_int_tree_p (cstep
)))
4009 tree inner_base
, inner_step
, inner_type
;
4010 inner_base
= TREE_OPERAND (cbase
, 0);
4011 if (CONVERT_EXPR_P (cstep
))
4012 inner_step
= TREE_OPERAND (cstep
, 0);
4016 inner_type
= TREE_TYPE (inner_base
);
4017 /* If candidate is added from a biv whose type is smaller than
4018 ctype, we know both candidate and the biv won't overflow.
4019 In this case, it's safe to skip the convertion in candidate.
4020 As an example, (unsigned short)((unsigned long)A) equals to
4021 (unsigned short)A, if A has a type no larger than short. */
4022 if (TYPE_PRECISION (inner_type
) <= TYPE_PRECISION (uutype
))
4028 cbase
= fold_convert (uutype
, cbase
);
4029 cstep
= fold_convert (uutype
, cstep
);
4030 var
= fold_convert (uutype
, var
);
4033 /* Ratio is 1 when computing the value of biv cand by itself.
4034 We can't rely on constant_multiple_of in this case because the
4035 use is created after the original biv is selected. The call
4036 could fail because of inconsistent fold behavior. See PR68021
4037 for more information. */
4038 if (cand
->pos
== IP_ORIGINAL
&& cand
->incremented_at
== use
->stmt
)
4040 gcc_assert (is_gimple_assign (use
->stmt
));
4041 gcc_assert (use
->iv
->ssa_name
== cand
->var_after
);
4042 gcc_assert (gimple_assign_lhs (use
->stmt
) == cand
->var_after
);
4045 else if (!constant_multiple_of (ustep
, cstep
, &rat
))
4051 /* In case both UBASE and CBASE are shortened to UUTYPE from some common
4052 type, we achieve better folding by computing their difference in this
4053 wider type, and cast the result to UUTYPE. We do not need to worry about
4054 overflows, as all the arithmetics will in the end be performed in UUTYPE
4056 common_type
= determine_common_wider_type (&ubase
, &cbase
);
4058 /* use = ubase - ratio * cbase + ratio * var. */
4059 tree_to_aff_combination (ubase
, common_type
, aff_inv
);
4060 tree_to_aff_combination (cbase
, common_type
, &aff_cbase
);
4061 tree_to_aff_combination (var
, uutype
, aff_var
);
4063 /* We need to shift the value if we are after the increment. */
4064 if (stmt_after_increment (loop
, cand
, at
))
4068 if (common_type
!= uutype
)
4069 cstep_common
= fold_convert (common_type
, cstep
);
4071 cstep_common
= cstep
;
4073 tree_to_aff_combination (cstep_common
, common_type
, &cstep_aff
);
4074 aff_combination_add (&aff_cbase
, &cstep_aff
);
4077 aff_combination_scale (&aff_cbase
, -rat
);
4078 aff_combination_add (aff_inv
, &aff_cbase
);
4079 if (common_type
!= uutype
)
4080 aff_combination_convert (aff_inv
, uutype
);
4082 aff_combination_scale (aff_var
, rat
);
4086 /* Determines the expression by that USE is expressed from induction variable
4087 CAND at statement AT in LOOP. The expression is stored in a decomposed
4088 form into AFF. Returns false if USE cannot be expressed using CAND. */
4091 get_computation_aff (class loop
*loop
, gimple
*at
, struct iv_use
*use
,
4092 struct iv_cand
*cand
, class aff_tree
*aff
)
4096 if (!get_computation_aff_1 (loop
, at
, use
, cand
, aff
, &aff_var
))
4099 aff_combination_add (aff
, &aff_var
);
4103 /* Return the type of USE. */
4106 get_use_type (struct iv_use
*use
)
4108 tree base_type
= TREE_TYPE (use
->iv
->base
);
4111 if (use
->type
== USE_REF_ADDRESS
)
4113 /* The base_type may be a void pointer. Create a pointer type based on
4114 the mem_ref instead. */
4115 type
= build_pointer_type (TREE_TYPE (*use
->op_p
));
4116 gcc_assert (TYPE_ADDR_SPACE (TREE_TYPE (type
))
4117 == TYPE_ADDR_SPACE (TREE_TYPE (base_type
)));
4125 /* Determines the expression by that USE is expressed from induction variable
4126 CAND at statement AT in LOOP. The computation is unshared. */
4129 get_computation_at (class loop
*loop
, gimple
*at
,
4130 struct iv_use
*use
, struct iv_cand
*cand
)
4133 tree type
= get_use_type (use
);
4135 if (!get_computation_aff (loop
, at
, use
, cand
, &aff
))
4137 unshare_aff_combination (&aff
);
4138 return fold_convert (type
, aff_combination_to_tree (&aff
));
4141 /* Like get_computation_at, but try harder, even if the computation
4142 is more expensive. Intended for debug stmts. */
4145 get_debug_computation_at (class loop
*loop
, gimple
*at
,
4146 struct iv_use
*use
, struct iv_cand
*cand
)
4148 if (tree ret
= get_computation_at (loop
, at
, use
, cand
))
4151 tree ubase
= use
->iv
->base
, ustep
= use
->iv
->step
;
4152 tree cbase
= cand
->iv
->base
, cstep
= cand
->iv
->step
;
4154 tree utype
= TREE_TYPE (ubase
), ctype
= TREE_TYPE (cbase
);
4157 /* We must have a precision to express the values of use. */
4158 if (TYPE_PRECISION (utype
) >= TYPE_PRECISION (ctype
))
4161 /* Try to handle the case that get_computation_at doesn't,
4163 use = ubase + (var - cbase) / ratio. */
4164 if (!constant_multiple_of (cstep
, fold_convert (TREE_TYPE (cstep
), ustep
),
4169 if (wi::neg_p (rat
))
4171 if (TYPE_UNSIGNED (ctype
))
4174 rat
= wi::neg (rat
);
4177 /* If both IVs can wrap around and CAND doesn't have a power of two step,
4178 it is unsafe. Consider uint16_t CAND with step 9, when wrapping around,
4179 the values will be ... 0xfff0, 0xfff9, 2, 11 ... and when use is say
4180 uint8_t with step 3, those values divided by 3 cast to uint8_t will be
4181 ... 0x50, 0x53, 0, 3 ... rather than expected 0x50, 0x53, 0x56, 0x59. */
4182 if (!use
->iv
->no_overflow
4183 && !cand
->iv
->no_overflow
4184 && !integer_pow2p (cstep
))
4187 int bits
= wi::exact_log2 (rat
);
4189 bits
= wi::floor_log2 (rat
) + 1;
4190 if (!cand
->iv
->no_overflow
4191 && TYPE_PRECISION (utype
) + bits
> TYPE_PRECISION (ctype
))
4194 var
= var_at_stmt (loop
, cand
, at
);
4196 if (POINTER_TYPE_P (ctype
))
4198 ctype
= unsigned_type_for (ctype
);
4199 cbase
= fold_convert (ctype
, cbase
);
4200 cstep
= fold_convert (ctype
, cstep
);
4201 var
= fold_convert (ctype
, var
);
4204 if (stmt_after_increment (loop
, cand
, at
))
4205 var
= fold_build2 (MINUS_EXPR
, TREE_TYPE (var
), var
,
4206 unshare_expr (cstep
));
4208 var
= fold_build2 (MINUS_EXPR
, TREE_TYPE (var
), var
, cbase
);
4209 var
= fold_build2 (EXACT_DIV_EXPR
, TREE_TYPE (var
), var
,
4210 wide_int_to_tree (TREE_TYPE (var
), rat
));
4211 if (POINTER_TYPE_P (utype
))
4213 var
= fold_convert (sizetype
, var
);
4215 var
= fold_build1 (NEGATE_EXPR
, sizetype
, var
);
4216 var
= fold_build2 (POINTER_PLUS_EXPR
, utype
, ubase
, var
);
4220 var
= fold_convert (utype
, var
);
4221 var
= fold_build2 (neg_p
? MINUS_EXPR
: PLUS_EXPR
, utype
,
4227 /* Adjust the cost COST for being in loop setup rather than loop body.
4228 If we're optimizing for space, the loop setup overhead is constant;
4229 if we're optimizing for speed, amortize it over the per-iteration cost.
4230 If ROUND_UP_P is true, the result is round up rather than to zero when
4231 optimizing for speed. */
4233 adjust_setup_cost (struct ivopts_data
*data
, int64_t cost
,
4234 bool round_up_p
= false)
4238 else if (optimize_loop_for_speed_p (data
->current_loop
))
4240 int64_t niters
= (int64_t) avg_loop_niter (data
->current_loop
);
4241 return (cost
+ (round_up_p
? niters
- 1 : 0)) / niters
;
4247 /* Calculate the SPEED or size cost of shiftadd EXPR in MODE. MULT is the
4248 EXPR operand holding the shift. COST0 and COST1 are the costs for
4249 calculating the operands of EXPR. Returns true if successful, and returns
4250 the cost in COST. */
4253 get_shiftadd_cost (tree expr
, scalar_int_mode mode
, comp_cost cost0
,
4254 comp_cost cost1
, tree mult
, bool speed
, comp_cost
*cost
)
4257 tree op1
= TREE_OPERAND (expr
, 1);
4258 tree cst
= TREE_OPERAND (mult
, 1);
4259 tree multop
= TREE_OPERAND (mult
, 0);
4260 int m
= exact_log2 (int_cst_value (cst
));
4261 int maxm
= MIN (BITS_PER_WORD
, GET_MODE_BITSIZE (mode
));
4262 int as_cost
, sa_cost
;
4265 if (!(m
>= 0 && m
< maxm
))
4269 mult_in_op1
= operand_equal_p (op1
, mult
, 0);
4271 as_cost
= add_cost (speed
, mode
) + shift_cost (speed
, mode
, m
);
4273 /* If the target has a cheap shift-and-add or shift-and-sub instruction,
4274 use that in preference to a shift insn followed by an add insn. */
4275 sa_cost
= (TREE_CODE (expr
) != MINUS_EXPR
4276 ? shiftadd_cost (speed
, mode
, m
)
4278 ? shiftsub1_cost (speed
, mode
, m
)
4279 : shiftsub0_cost (speed
, mode
, m
)));
4281 res
= comp_cost (MIN (as_cost
, sa_cost
), 0);
4282 res
+= (mult_in_op1
? cost0
: cost1
);
4284 STRIP_NOPS (multop
);
4285 if (!is_gimple_val (multop
))
4286 res
+= force_expr_to_var_cost (multop
, speed
);
4292 /* Estimates cost of forcing expression EXPR into a variable. */
4295 force_expr_to_var_cost (tree expr
, bool speed
)
4297 static bool costs_initialized
= false;
4298 static unsigned integer_cost
[2];
4299 static unsigned symbol_cost
[2];
4300 static unsigned address_cost
[2];
4302 comp_cost cost0
, cost1
, cost
;
4304 scalar_int_mode int_mode
;
4306 if (!costs_initialized
)
4308 tree type
= build_pointer_type (integer_type_node
);
4313 var
= create_tmp_var_raw (integer_type_node
, "test_var");
4314 TREE_STATIC (var
) = 1;
4315 x
= produce_memory_decl_rtl (var
, NULL
);
4316 SET_DECL_RTL (var
, x
);
4318 addr
= build1 (ADDR_EXPR
, type
, var
);
4321 for (i
= 0; i
< 2; i
++)
4323 integer_cost
[i
] = computation_cost (build_int_cst (integer_type_node
,
4326 symbol_cost
[i
] = computation_cost (addr
, i
) + 1;
4329 = computation_cost (fold_build_pointer_plus_hwi (addr
, 2000), i
) + 1;
4330 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4332 fprintf (dump_file
, "force_expr_to_var_cost %s costs:\n", i
? "speed" : "size");
4333 fprintf (dump_file
, " integer %d\n", (int) integer_cost
[i
]);
4334 fprintf (dump_file
, " symbol %d\n", (int) symbol_cost
[i
]);
4335 fprintf (dump_file
, " address %d\n", (int) address_cost
[i
]);
4336 fprintf (dump_file
, " other %d\n", (int) target_spill_cost
[i
]);
4337 fprintf (dump_file
, "\n");
4341 costs_initialized
= true;
4346 if (SSA_VAR_P (expr
))
4349 if (is_gimple_min_invariant (expr
))
4351 if (poly_int_tree_p (expr
))
4352 return comp_cost (integer_cost
[speed
], 0);
4354 if (TREE_CODE (expr
) == ADDR_EXPR
)
4356 tree obj
= TREE_OPERAND (expr
, 0);
4359 || TREE_CODE (obj
) == PARM_DECL
4360 || TREE_CODE (obj
) == RESULT_DECL
)
4361 return comp_cost (symbol_cost
[speed
], 0);
4364 return comp_cost (address_cost
[speed
], 0);
4367 switch (TREE_CODE (expr
))
4369 case POINTER_PLUS_EXPR
:
4373 case TRUNC_DIV_EXPR
:
4378 op0
= TREE_OPERAND (expr
, 0);
4379 op1
= TREE_OPERAND (expr
, 1);
4387 op0
= TREE_OPERAND (expr
, 0);
4391 /* See add_iv_candidate_for_doloop, for doloop may_be_zero case, we
4392 introduce COND_EXPR for IV base, need to support better cost estimation
4393 for this COND_EXPR and tcc_comparison. */
4395 op0
= TREE_OPERAND (expr
, 1);
4397 op1
= TREE_OPERAND (expr
, 2);
4406 case UNORDERED_EXPR
:
4416 op0
= TREE_OPERAND (expr
, 0);
4418 op1
= TREE_OPERAND (expr
, 1);
4423 /* Just an arbitrary value, FIXME. */
4424 return comp_cost (target_spill_cost
[speed
], 0);
4427 if (op0
== NULL_TREE
4428 || TREE_CODE (op0
) == SSA_NAME
|| CONSTANT_CLASS_P (op0
))
4431 cost0
= force_expr_to_var_cost (op0
, speed
);
4433 if (op1
== NULL_TREE
4434 || TREE_CODE (op1
) == SSA_NAME
|| CONSTANT_CLASS_P (op1
))
4437 cost1
= force_expr_to_var_cost (op1
, speed
);
4439 mode
= TYPE_MODE (TREE_TYPE (expr
));
4440 switch (TREE_CODE (expr
))
4442 case POINTER_PLUS_EXPR
:
4446 cost
= comp_cost (add_cost (speed
, mode
), 0);
4447 if (TREE_CODE (expr
) != NEGATE_EXPR
)
4449 tree mult
= NULL_TREE
;
4451 if (TREE_CODE (op1
) == MULT_EXPR
)
4453 else if (TREE_CODE (op0
) == MULT_EXPR
)
4456 if (mult
!= NULL_TREE
4457 && is_a
<scalar_int_mode
> (mode
, &int_mode
)
4458 && cst_and_fits_in_hwi (TREE_OPERAND (mult
, 1))
4459 && get_shiftadd_cost (expr
, int_mode
, cost0
, cost1
, mult
,
4467 tree inner_mode
, outer_mode
;
4468 outer_mode
= TREE_TYPE (expr
);
4469 inner_mode
= TREE_TYPE (op0
);
4470 cost
= comp_cost (convert_cost (TYPE_MODE (outer_mode
),
4471 TYPE_MODE (inner_mode
), speed
), 0);
4476 if (cst_and_fits_in_hwi (op0
))
4477 cost
= comp_cost (mult_by_coeff_cost (int_cst_value (op0
),
4479 else if (cst_and_fits_in_hwi (op1
))
4480 cost
= comp_cost (mult_by_coeff_cost (int_cst_value (op1
),
4483 return comp_cost (target_spill_cost
[speed
], 0);
4486 case TRUNC_DIV_EXPR
:
4487 /* Division by power of two is usually cheap, so we allow it. Forbid
4489 if (integer_pow2p (TREE_OPERAND (expr
, 1)))
4490 cost
= comp_cost (add_cost (speed
, mode
), 0);
4492 cost
= comp_cost (target_spill_cost
[speed
], 0);
4500 cost
= comp_cost (add_cost (speed
, mode
), 0);
4503 op0
= TREE_OPERAND (expr
, 0);
4505 if (op0
== NULL_TREE
|| TREE_CODE (op0
) == SSA_NAME
4506 || CONSTANT_CLASS_P (op0
))
4509 cost
= force_expr_to_var_cost (op0
, speed
);
4517 case UNORDERED_EXPR
:
4527 /* Simply use add cost for now, FIXME if there is some more accurate cost
4529 cost
= comp_cost (add_cost (speed
, mode
), 0);
4541 /* Estimates cost of forcing EXPR into a variable. INV_VARS is a set of the
4542 invariants the computation depends on. */
4545 force_var_cost (struct ivopts_data
*data
, tree expr
, bitmap
*inv_vars
)
4550 find_inv_vars (data
, &expr
, inv_vars
);
4551 return force_expr_to_var_cost (expr
, data
->speed
);
4554 /* Returns cost of auto-modifying address expression in shape base + offset.
4555 AINC_STEP is step size of the address IV. AINC_OFFSET is offset of the
4556 address expression. The address expression has ADDR_MODE in addr space
4557 AS. The memory access has MEM_MODE. SPEED means we are optimizing for
4562 AINC_PRE_INC
, /* Pre increment. */
4563 AINC_PRE_DEC
, /* Pre decrement. */
4564 AINC_POST_INC
, /* Post increment. */
4565 AINC_POST_DEC
, /* Post decrement. */
4566 AINC_NONE
/* Also the number of auto increment types. */
4569 struct ainc_cost_data
4571 int64_t costs
[AINC_NONE
];
4575 get_address_cost_ainc (poly_int64 ainc_step
, poly_int64 ainc_offset
,
4576 machine_mode addr_mode
, machine_mode mem_mode
,
4577 addr_space_t as
, bool speed
)
4579 if (!USE_LOAD_PRE_DECREMENT (mem_mode
)
4580 && !USE_STORE_PRE_DECREMENT (mem_mode
)
4581 && !USE_LOAD_POST_DECREMENT (mem_mode
)
4582 && !USE_STORE_POST_DECREMENT (mem_mode
)
4583 && !USE_LOAD_PRE_INCREMENT (mem_mode
)
4584 && !USE_STORE_PRE_INCREMENT (mem_mode
)
4585 && !USE_LOAD_POST_INCREMENT (mem_mode
)
4586 && !USE_STORE_POST_INCREMENT (mem_mode
))
4587 return infinite_cost
;
4589 static vec
<ainc_cost_data
*> ainc_cost_data_list
;
4590 unsigned idx
= (unsigned) as
* MAX_MACHINE_MODE
+ (unsigned) mem_mode
;
4591 if (idx
>= ainc_cost_data_list
.length ())
4593 unsigned nsize
= ((unsigned) as
+ 1) *MAX_MACHINE_MODE
;
4595 gcc_assert (nsize
> idx
);
4596 ainc_cost_data_list
.safe_grow_cleared (nsize
, true);
4599 ainc_cost_data
*data
= ainc_cost_data_list
[idx
];
4602 rtx reg
= gen_raw_REG (addr_mode
, LAST_VIRTUAL_REGISTER
+ 1);
4604 data
= (ainc_cost_data
*) xcalloc (1, sizeof (*data
));
4605 data
->costs
[AINC_PRE_DEC
] = INFTY
;
4606 data
->costs
[AINC_POST_DEC
] = INFTY
;
4607 data
->costs
[AINC_PRE_INC
] = INFTY
;
4608 data
->costs
[AINC_POST_INC
] = INFTY
;
4609 if (USE_LOAD_PRE_DECREMENT (mem_mode
)
4610 || USE_STORE_PRE_DECREMENT (mem_mode
))
4612 rtx addr
= gen_rtx_PRE_DEC (addr_mode
, reg
);
4614 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
4615 data
->costs
[AINC_PRE_DEC
]
4616 = address_cost (addr
, mem_mode
, as
, speed
);
4618 if (USE_LOAD_POST_DECREMENT (mem_mode
)
4619 || USE_STORE_POST_DECREMENT (mem_mode
))
4621 rtx addr
= gen_rtx_POST_DEC (addr_mode
, reg
);
4623 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
4624 data
->costs
[AINC_POST_DEC
]
4625 = address_cost (addr
, mem_mode
, as
, speed
);
4627 if (USE_LOAD_PRE_INCREMENT (mem_mode
)
4628 || USE_STORE_PRE_INCREMENT (mem_mode
))
4630 rtx addr
= gen_rtx_PRE_INC (addr_mode
, reg
);
4632 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
4633 data
->costs
[AINC_PRE_INC
]
4634 = address_cost (addr
, mem_mode
, as
, speed
);
4636 if (USE_LOAD_POST_INCREMENT (mem_mode
)
4637 || USE_STORE_POST_INCREMENT (mem_mode
))
4639 rtx addr
= gen_rtx_POST_INC (addr_mode
, reg
);
4641 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
4642 data
->costs
[AINC_POST_INC
]
4643 = address_cost (addr
, mem_mode
, as
, speed
);
4645 ainc_cost_data_list
[idx
] = data
;
4648 poly_int64 msize
= GET_MODE_SIZE (mem_mode
);
4649 if (known_eq (ainc_offset
, 0) && known_eq (msize
, ainc_step
))
4650 return comp_cost (data
->costs
[AINC_POST_INC
], 0);
4651 if (known_eq (ainc_offset
, 0) && known_eq (msize
, -ainc_step
))
4652 return comp_cost (data
->costs
[AINC_POST_DEC
], 0);
4653 if (known_eq (ainc_offset
, msize
) && known_eq (msize
, ainc_step
))
4654 return comp_cost (data
->costs
[AINC_PRE_INC
], 0);
4655 if (known_eq (ainc_offset
, -msize
) && known_eq (msize
, -ainc_step
))
4656 return comp_cost (data
->costs
[AINC_PRE_DEC
], 0);
4658 return infinite_cost
;
4661 /* Return cost of computing USE's address expression by using CAND.
4662 AFF_INV and AFF_VAR represent invariant and variant parts of the
4663 address expression, respectively. If AFF_INV is simple, store
4664 the loop invariant variables which are depended by it in INV_VARS;
4665 if AFF_INV is complicated, handle it as a new invariant expression
4666 and record it in INV_EXPR. RATIO indicates multiple times between
4667 steps of USE and CAND. If CAN_AUTOINC is nonNULL, store boolean
4668 value to it indicating if this is an auto-increment address. */
4671 get_address_cost (struct ivopts_data
*data
, struct iv_use
*use
,
4672 struct iv_cand
*cand
, aff_tree
*aff_inv
,
4673 aff_tree
*aff_var
, HOST_WIDE_INT ratio
,
4674 bitmap
*inv_vars
, iv_inv_expr_ent
**inv_expr
,
4675 bool *can_autoinc
, bool speed
)
4678 bool simple_inv
= true;
4679 tree comp_inv
= NULL_TREE
, type
= aff_var
->type
;
4680 comp_cost var_cost
= no_cost
, cost
= no_cost
;
4681 struct mem_address parts
= {NULL_TREE
, integer_one_node
,
4682 NULL_TREE
, NULL_TREE
, NULL_TREE
};
4683 machine_mode addr_mode
= TYPE_MODE (type
);
4684 machine_mode mem_mode
= TYPE_MODE (use
->mem_type
);
4685 addr_space_t as
= TYPE_ADDR_SPACE (TREE_TYPE (use
->iv
->base
));
4686 /* Only true if ratio != 1. */
4687 bool ok_with_ratio_p
= false;
4688 bool ok_without_ratio_p
= false;
4690 if (!aff_combination_const_p (aff_inv
))
4692 parts
.index
= integer_one_node
;
4693 /* Addressing mode "base + index". */
4694 ok_without_ratio_p
= valid_mem_ref_p (mem_mode
, as
, &parts
);
4697 parts
.step
= wide_int_to_tree (type
, ratio
);
4698 /* Addressing mode "base + index << scale". */
4699 ok_with_ratio_p
= valid_mem_ref_p (mem_mode
, as
, &parts
);
4700 if (!ok_with_ratio_p
)
4701 parts
.step
= NULL_TREE
;
4703 if (ok_with_ratio_p
|| ok_without_ratio_p
)
4705 if (maybe_ne (aff_inv
->offset
, 0))
4707 parts
.offset
= wide_int_to_tree (sizetype
, aff_inv
->offset
);
4708 /* Addressing mode "base + index [<< scale] + offset". */
4709 if (!valid_mem_ref_p (mem_mode
, as
, &parts
))
4710 parts
.offset
= NULL_TREE
;
4712 aff_inv
->offset
= 0;
4715 move_fixed_address_to_symbol (&parts
, aff_inv
);
4716 /* Base is fixed address and is moved to symbol part. */
4717 if (parts
.symbol
!= NULL_TREE
&& aff_combination_zero_p (aff_inv
))
4718 parts
.base
= NULL_TREE
;
4720 /* Addressing mode "symbol + base + index [<< scale] [+ offset]". */
4721 if (parts
.symbol
!= NULL_TREE
4722 && !valid_mem_ref_p (mem_mode
, as
, &parts
))
4724 aff_combination_add_elt (aff_inv
, parts
.symbol
, 1);
4725 parts
.symbol
= NULL_TREE
;
4726 /* Reset SIMPLE_INV since symbol address needs to be computed
4727 outside of address expression in this case. */
4729 /* Symbol part is moved back to base part, it can't be NULL. */
4730 parts
.base
= integer_one_node
;
4734 parts
.index
= NULL_TREE
;
4738 poly_int64 ainc_step
;
4741 && ptrdiff_tree_p (cand
->iv
->step
, &ainc_step
))
4743 poly_int64 ainc_offset
= (aff_inv
->offset
).force_shwi ();
4745 if (stmt_after_increment (data
->current_loop
, cand
, use
->stmt
))
4746 ainc_offset
+= ainc_step
;
4747 cost
= get_address_cost_ainc (ainc_step
, ainc_offset
,
4748 addr_mode
, mem_mode
, as
, speed
);
4749 if (!cost
.infinite_cost_p ())
4751 *can_autoinc
= true;
4756 if (!aff_combination_zero_p (aff_inv
))
4758 parts
.offset
= wide_int_to_tree (sizetype
, aff_inv
->offset
);
4759 /* Addressing mode "base + offset". */
4760 if (!valid_mem_ref_p (mem_mode
, as
, &parts
))
4761 parts
.offset
= NULL_TREE
;
4763 aff_inv
->offset
= 0;
4768 simple_inv
= (aff_inv
== NULL
4769 || aff_combination_const_p (aff_inv
)
4770 || aff_combination_singleton_var_p (aff_inv
));
4771 if (!aff_combination_zero_p (aff_inv
))
4772 comp_inv
= aff_combination_to_tree (aff_inv
);
4773 if (comp_inv
!= NULL_TREE
)
4774 cost
= force_var_cost (data
, comp_inv
, inv_vars
);
4775 if (ratio
!= 1 && parts
.step
== NULL_TREE
)
4776 var_cost
+= mult_by_coeff_cost (ratio
, addr_mode
, speed
);
4777 if (comp_inv
!= NULL_TREE
&& parts
.index
== NULL_TREE
)
4778 var_cost
+= add_cost (speed
, addr_mode
);
4780 if (comp_inv
&& inv_expr
&& !simple_inv
)
4782 *inv_expr
= get_loop_invariant_expr (data
, comp_inv
);
4783 /* Clear depends on. */
4784 if (*inv_expr
!= NULL
&& inv_vars
&& *inv_vars
)
4785 bitmap_clear (*inv_vars
);
4787 /* Cost of small invariant expression adjusted against loop niters
4788 is usually zero, which makes it difficult to be differentiated
4789 from candidate based on loop invariant variables. Secondly, the
4790 generated invariant expression may not be hoisted out of loop by
4791 following pass. We penalize the cost by rounding up in order to
4792 neutralize such effects. */
4793 cost
.cost
= adjust_setup_cost (data
, cost
.cost
, true);
4794 cost
.scratch
= cost
.cost
;
4798 addr
= addr_for_mem_ref (&parts
, as
, false);
4799 gcc_assert (memory_address_addr_space_p (mem_mode
, addr
, as
));
4800 cost
+= address_cost (addr
, mem_mode
, as
, speed
);
4802 if (parts
.symbol
!= NULL_TREE
)
4803 cost
.complexity
+= 1;
4804 /* Don't increase the complexity of adding a scaled index if it's
4805 the only kind of index that the target allows. */
4806 if (parts
.step
!= NULL_TREE
&& ok_without_ratio_p
)
4807 cost
.complexity
+= 1;
4808 if (parts
.base
!= NULL_TREE
&& parts
.index
!= NULL_TREE
)
4809 cost
.complexity
+= 1;
4810 if (parts
.offset
!= NULL_TREE
&& !integer_zerop (parts
.offset
))
4811 cost
.complexity
+= 1;
4816 /* Scale (multiply) the computed COST (except scratch part that should be
4817 hoisted out a loop) by header->frequency / AT->frequency, which makes
4818 expected cost more accurate. */
4821 get_scaled_computation_cost_at (ivopts_data
*data
, gimple
*at
, comp_cost cost
)
4824 && data
->current_loop
->header
->count
.to_frequency (cfun
) > 0)
4826 basic_block bb
= gimple_bb (at
);
4827 gcc_assert (cost
.scratch
<= cost
.cost
);
4828 int scale_factor
= (int)(intptr_t) bb
->aux
;
4829 if (scale_factor
== 1)
4833 = cost
.scratch
+ (cost
.cost
- cost
.scratch
) * scale_factor
;
4835 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4836 fprintf (dump_file
, "Scaling cost based on bb prob by %2.2f: "
4837 "%" PRId64
" (scratch: %" PRId64
") -> %" PRId64
"\n",
4838 1.0f
* scale_factor
, cost
.cost
, cost
.scratch
, scaled_cost
);
4840 cost
.cost
= scaled_cost
;
4846 /* Determines the cost of the computation by that USE is expressed
4847 from induction variable CAND. If ADDRESS_P is true, we just need
4848 to create an address from it, otherwise we want to get it into
4849 register. A set of invariants we depend on is stored in INV_VARS.
4850 If CAN_AUTOINC is nonnull, use it to record whether autoinc
4851 addressing is likely. If INV_EXPR is nonnull, record invariant
4852 expr entry in it. */
4855 get_computation_cost (struct ivopts_data
*data
, struct iv_use
*use
,
4856 struct iv_cand
*cand
, bool address_p
, bitmap
*inv_vars
,
4857 bool *can_autoinc
, iv_inv_expr_ent
**inv_expr
)
4859 gimple
*at
= use
->stmt
;
4860 tree ubase
= use
->iv
->base
, cbase
= cand
->iv
->base
;
4861 tree utype
= TREE_TYPE (ubase
), ctype
= TREE_TYPE (cbase
);
4862 tree comp_inv
= NULL_TREE
;
4863 HOST_WIDE_INT ratio
, aratio
;
4866 aff_tree aff_inv
, aff_var
;
4867 bool speed
= optimize_bb_for_speed_p (gimple_bb (at
));
4872 *can_autoinc
= false;
4876 /* Check if we have enough precision to express the values of use. */
4877 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
4878 return infinite_cost
;
4881 || (use
->iv
->base_object
4882 && cand
->iv
->base_object
4883 && POINTER_TYPE_P (TREE_TYPE (use
->iv
->base_object
))
4884 && POINTER_TYPE_P (TREE_TYPE (cand
->iv
->base_object
))))
4886 /* Do not try to express address of an object with computation based
4887 on address of a different object. This may cause problems in rtl
4888 level alias analysis (that does not expect this to be happening,
4889 as this is illegal in C), and would be unlikely to be useful
4891 if (use
->iv
->base_object
4892 && cand
->iv
->base_object
4893 && !operand_equal_p (use
->iv
->base_object
, cand
->iv
->base_object
, 0))
4894 return infinite_cost
;
4897 if (!get_computation_aff_1 (data
->current_loop
, at
, use
,
4898 cand
, &aff_inv
, &aff_var
, &rat
)
4899 || !wi::fits_shwi_p (rat
))
4900 return infinite_cost
;
4902 ratio
= rat
.to_shwi ();
4905 cost
= get_address_cost (data
, use
, cand
, &aff_inv
, &aff_var
, ratio
,
4906 inv_vars
, inv_expr
, can_autoinc
, speed
);
4907 cost
= get_scaled_computation_cost_at (data
, at
, cost
);
4908 /* For doloop IV cand, add on the extra cost. */
4909 cost
+= cand
->doloop_p
? targetm
.doloop_cost_for_address
: 0;
4913 bool simple_inv
= (aff_combination_const_p (&aff_inv
)
4914 || aff_combination_singleton_var_p (&aff_inv
));
4915 tree signed_type
= signed_type_for (aff_combination_type (&aff_inv
));
4916 aff_combination_convert (&aff_inv
, signed_type
);
4917 if (!aff_combination_zero_p (&aff_inv
))
4918 comp_inv
= aff_combination_to_tree (&aff_inv
);
4920 cost
= force_var_cost (data
, comp_inv
, inv_vars
);
4921 if (comp_inv
&& inv_expr
&& !simple_inv
)
4923 *inv_expr
= get_loop_invariant_expr (data
, comp_inv
);
4924 /* Clear depends on. */
4925 if (*inv_expr
!= NULL
&& inv_vars
&& *inv_vars
)
4926 bitmap_clear (*inv_vars
);
4928 cost
.cost
= adjust_setup_cost (data
, cost
.cost
);
4929 /* Record setup cost in scratch field. */
4930 cost
.scratch
= cost
.cost
;
4932 /* Cost of constant integer can be covered when adding invariant part to
4934 else if (comp_inv
&& CONSTANT_CLASS_P (comp_inv
))
4937 /* Need type narrowing to represent use with cand. */
4938 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
4940 machine_mode outer_mode
= TYPE_MODE (utype
);
4941 machine_mode inner_mode
= TYPE_MODE (ctype
);
4942 cost
+= comp_cost (convert_cost (outer_mode
, inner_mode
, speed
), 0);
4945 /* Turn a + i * (-c) into a - i * c. */
4946 if (ratio
< 0 && comp_inv
&& !integer_zerop (comp_inv
))
4952 cost
+= mult_by_coeff_cost (aratio
, TYPE_MODE (utype
), speed
);
4954 /* TODO: We may also need to check if we can compute a + i * 4 in one
4956 /* Need to add up the invariant and variant parts. */
4957 if (comp_inv
&& !integer_zerop (comp_inv
))
4958 cost
+= add_cost (speed
, TYPE_MODE (utype
));
4960 cost
= get_scaled_computation_cost_at (data
, at
, cost
);
4962 /* For doloop IV cand, add on the extra cost. */
4963 if (cand
->doloop_p
&& use
->type
== USE_NONLINEAR_EXPR
)
4964 cost
+= targetm
.doloop_cost_for_generic
;
4969 /* Determines cost of computing the use in GROUP with CAND in a generic
4973 determine_group_iv_cost_generic (struct ivopts_data
*data
,
4974 struct iv_group
*group
, struct iv_cand
*cand
)
4977 iv_inv_expr_ent
*inv_expr
= NULL
;
4978 bitmap inv_vars
= NULL
, inv_exprs
= NULL
;
4979 struct iv_use
*use
= group
->vuses
[0];
4981 /* The simple case first -- if we need to express value of the preserved
4982 original biv, the cost is 0. This also prevents us from counting the
4983 cost of increment twice -- once at this use and once in the cost of
4985 if (cand
->pos
== IP_ORIGINAL
&& cand
->incremented_at
== use
->stmt
)
4987 /* If the IV candidate involves undefined SSA values and is not the
4988 same IV as on the USE avoid using that candidate here. */
4989 else if (cand
->involves_undefs
4990 && (!use
->iv
|| !operand_equal_p (cand
->iv
->base
, use
->iv
->base
, 0)))
4993 cost
= get_computation_cost (data
, use
, cand
, false,
4994 &inv_vars
, NULL
, &inv_expr
);
4998 inv_exprs
= BITMAP_ALLOC (NULL
);
4999 bitmap_set_bit (inv_exprs
, inv_expr
->id
);
5001 set_group_iv_cost (data
, group
, cand
, cost
, inv_vars
,
5002 NULL_TREE
, ERROR_MARK
, inv_exprs
);
5003 return !cost
.infinite_cost_p ();
5006 /* Determines cost of computing uses in GROUP with CAND in addresses. */
5009 determine_group_iv_cost_address (struct ivopts_data
*data
,
5010 struct iv_group
*group
, struct iv_cand
*cand
)
5013 bitmap inv_vars
= NULL
, inv_exprs
= NULL
;
5015 iv_inv_expr_ent
*inv_expr
= NULL
;
5016 struct iv_use
*use
= group
->vuses
[0];
5017 comp_cost sum_cost
= no_cost
, cost
;
5019 cost
= get_computation_cost (data
, use
, cand
, true,
5020 &inv_vars
, &can_autoinc
, &inv_expr
);
5024 inv_exprs
= BITMAP_ALLOC (NULL
);
5025 bitmap_set_bit (inv_exprs
, inv_expr
->id
);
5028 if (!sum_cost
.infinite_cost_p () && cand
->ainc_use
== use
)
5031 sum_cost
-= cand
->cost_step
;
5032 /* If we generated the candidate solely for exploiting autoincrement
5033 opportunities, and it turns out it can't be used, set the cost to
5034 infinity to make sure we ignore it. */
5035 else if (cand
->pos
== IP_AFTER_USE
|| cand
->pos
== IP_BEFORE_USE
)
5036 sum_cost
= infinite_cost
;
5039 /* Uses in a group can share setup code, so only add setup cost once. */
5040 cost
-= cost
.scratch
;
5041 /* Compute and add costs for rest uses of this group. */
5042 for (i
= 1; i
< group
->vuses
.length () && !sum_cost
.infinite_cost_p (); i
++)
5044 struct iv_use
*next
= group
->vuses
[i
];
5046 /* TODO: We could skip computing cost for sub iv_use when it has the
5047 same cost as the first iv_use, but the cost really depends on the
5048 offset and where the iv_use is. */
5049 cost
= get_computation_cost (data
, next
, cand
, true,
5050 NULL
, &can_autoinc
, &inv_expr
);
5054 inv_exprs
= BITMAP_ALLOC (NULL
);
5056 bitmap_set_bit (inv_exprs
, inv_expr
->id
);
5060 set_group_iv_cost (data
, group
, cand
, sum_cost
, inv_vars
,
5061 NULL_TREE
, ERROR_MARK
, inv_exprs
);
5063 return !sum_cost
.infinite_cost_p ();
5066 /* Computes value of candidate CAND at position AT in iteration DESC->NITER,
5067 and stores it to VAL. */
5070 cand_value_at (class loop
*loop
, struct iv_cand
*cand
, gimple
*at
,
5071 class tree_niter_desc
*desc
, aff_tree
*val
)
5073 aff_tree step
, delta
, nit
;
5074 struct iv
*iv
= cand
->iv
;
5075 tree type
= TREE_TYPE (iv
->base
);
5076 tree niter
= desc
->niter
;
5077 bool after_adjust
= stmt_after_increment (loop
, cand
, at
);
5080 if (POINTER_TYPE_P (type
))
5081 steptype
= sizetype
;
5083 steptype
= unsigned_type_for (type
);
5085 /* If AFTER_ADJUST is required, the code below generates the equivalent
5086 of BASE + NITER * STEP + STEP, when ideally we'd prefer the expression
5087 BASE + (NITER + 1) * STEP, especially when NITER is often of the form
5088 SSA_NAME - 1. Unfortunately, guaranteeing that adding 1 to NITER
5089 doesn't overflow is tricky, so we peek inside the TREE_NITER_DESC
5090 class for common idioms that we know are safe. */
5092 && desc
->control
.no_overflow
5093 && integer_onep (desc
->control
.step
)
5094 && (desc
->cmp
== LT_EXPR
5095 || desc
->cmp
== NE_EXPR
)
5096 && TREE_CODE (desc
->bound
) == SSA_NAME
)
5098 if (integer_onep (desc
->control
.base
))
5100 niter
= desc
->bound
;
5101 after_adjust
= false;
5103 else if (TREE_CODE (niter
) == MINUS_EXPR
5104 && integer_onep (TREE_OPERAND (niter
, 1)))
5106 niter
= TREE_OPERAND (niter
, 0);
5107 after_adjust
= false;
5111 tree_to_aff_combination (iv
->step
, TREE_TYPE (iv
->step
), &step
);
5112 aff_combination_convert (&step
, steptype
);
5113 tree_to_aff_combination (niter
, TREE_TYPE (niter
), &nit
);
5114 aff_combination_convert (&nit
, steptype
);
5115 aff_combination_mult (&nit
, &step
, &delta
);
5117 aff_combination_add (&delta
, &step
);
5119 tree_to_aff_combination (iv
->base
, type
, val
);
5120 if (!POINTER_TYPE_P (type
))
5121 aff_combination_convert (val
, steptype
);
5122 aff_combination_add (val
, &delta
);
5125 /* Returns period of induction variable iv. */
5128 iv_period (struct iv
*iv
)
5130 tree step
= iv
->step
, period
, type
;
5133 gcc_assert (step
&& TREE_CODE (step
) == INTEGER_CST
);
5135 type
= unsigned_type_for (TREE_TYPE (step
));
5136 /* Period of the iv is lcm (step, type_range)/step -1,
5137 i.e., N*type_range/step - 1. Since type range is power
5138 of two, N == (step >> num_of_ending_zeros_binary (step),
5139 so the final result is
5141 (type_range >> num_of_ending_zeros_binary (step)) - 1
5144 pow2div
= num_ending_zeros (step
);
5146 period
= build_low_bits_mask (type
,
5147 (TYPE_PRECISION (type
)
5148 - tree_to_uhwi (pow2div
)));
5153 /* Returns the comparison operator used when eliminating the iv USE. */
5155 static enum tree_code
5156 iv_elimination_compare (struct ivopts_data
*data
, struct iv_use
*use
)
5158 class loop
*loop
= data
->current_loop
;
5162 ex_bb
= gimple_bb (use
->stmt
);
5163 exit
= EDGE_SUCC (ex_bb
, 0);
5164 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
5165 exit
= EDGE_SUCC (ex_bb
, 1);
5167 return (exit
->flags
& EDGE_TRUE_VALUE
? EQ_EXPR
: NE_EXPR
);
5170 /* Returns true if we can prove that BASE - OFFSET does not overflow. For now,
5171 we only detect the situation that BASE = SOMETHING + OFFSET, where the
5172 calculation is performed in non-wrapping type.
5174 TODO: More generally, we could test for the situation that
5175 BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero.
5176 This would require knowing the sign of OFFSET. */
5179 difference_cannot_overflow_p (struct ivopts_data
*data
, tree base
, tree offset
)
5181 enum tree_code code
;
5183 aff_tree aff_e1
, aff_e2
, aff_offset
;
5185 if (!nowrap_type_p (TREE_TYPE (base
)))
5188 base
= expand_simple_operations (base
);
5190 if (TREE_CODE (base
) == SSA_NAME
)
5192 gimple
*stmt
= SSA_NAME_DEF_STMT (base
);
5194 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
5197 code
= gimple_assign_rhs_code (stmt
);
5198 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
5201 e1
= gimple_assign_rhs1 (stmt
);
5202 e2
= gimple_assign_rhs2 (stmt
);
5206 code
= TREE_CODE (base
);
5207 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
5209 e1
= TREE_OPERAND (base
, 0);
5210 e2
= TREE_OPERAND (base
, 1);
5213 /* Use affine expansion as deeper inspection to prove the equality. */
5214 tree_to_aff_combination_expand (e2
, TREE_TYPE (e2
),
5215 &aff_e2
, &data
->name_expansion_cache
);
5216 tree_to_aff_combination_expand (offset
, TREE_TYPE (offset
),
5217 &aff_offset
, &data
->name_expansion_cache
);
5218 aff_combination_scale (&aff_offset
, -1);
5222 aff_combination_add (&aff_e2
, &aff_offset
);
5223 if (aff_combination_zero_p (&aff_e2
))
5226 tree_to_aff_combination_expand (e1
, TREE_TYPE (e1
),
5227 &aff_e1
, &data
->name_expansion_cache
);
5228 aff_combination_add (&aff_e1
, &aff_offset
);
5229 return aff_combination_zero_p (&aff_e1
);
5231 case POINTER_PLUS_EXPR
:
5232 aff_combination_add (&aff_e2
, &aff_offset
);
5233 return aff_combination_zero_p (&aff_e2
);
5240 /* Tries to replace loop exit by one formulated in terms of a LT_EXPR
5241 comparison with CAND. NITER describes the number of iterations of
5242 the loops. If successful, the comparison in COMP_P is altered accordingly.
5244 We aim to handle the following situation:
5260 Here, the number of iterations of the loop is (a + 1 > b) ? 0 : b - a - 1.
5261 We aim to optimize this to
5269 while (p < p_0 - a + b);
5271 This preserves the correctness, since the pointer arithmetics does not
5272 overflow. More precisely:
5274 1) if a + 1 <= b, then p_0 - a + b is the final value of p, hence there is no
5275 overflow in computing it or the values of p.
5276 2) if a + 1 > b, then we need to verify that the expression p_0 - a does not
5277 overflow. To prove this, we use the fact that p_0 = base + a. */
5280 iv_elimination_compare_lt (struct ivopts_data
*data
,
5281 struct iv_cand
*cand
, enum tree_code
*comp_p
,
5282 class tree_niter_desc
*niter
)
5284 tree cand_type
, a
, b
, mbz
, nit_type
= TREE_TYPE (niter
->niter
), offset
;
5285 class aff_tree nit
, tmpa
, tmpb
;
5286 enum tree_code comp
;
5289 /* We need to know that the candidate induction variable does not overflow.
5290 While more complex analysis may be used to prove this, for now just
5291 check that the variable appears in the original program and that it
5292 is computed in a type that guarantees no overflows. */
5293 cand_type
= TREE_TYPE (cand
->iv
->base
);
5294 if (cand
->pos
!= IP_ORIGINAL
|| !nowrap_type_p (cand_type
))
5297 /* Make sure that the loop iterates till the loop bound is hit, as otherwise
5298 the calculation of the BOUND could overflow, making the comparison
5300 if (!data
->loop_single_exit_p
)
5303 /* We need to be able to decide whether candidate is increasing or decreasing
5304 in order to choose the right comparison operator. */
5305 if (!cst_and_fits_in_hwi (cand
->iv
->step
))
5307 step
= int_cst_value (cand
->iv
->step
);
5309 /* Check that the number of iterations matches the expected pattern:
5310 a + 1 > b ? 0 : b - a - 1. */
5311 mbz
= niter
->may_be_zero
;
5312 if (TREE_CODE (mbz
) == GT_EXPR
)
5314 /* Handle a + 1 > b. */
5315 tree op0
= TREE_OPERAND (mbz
, 0);
5316 if (TREE_CODE (op0
) == PLUS_EXPR
&& integer_onep (TREE_OPERAND (op0
, 1)))
5318 a
= TREE_OPERAND (op0
, 0);
5319 b
= TREE_OPERAND (mbz
, 1);
5324 else if (TREE_CODE (mbz
) == LT_EXPR
)
5326 tree op1
= TREE_OPERAND (mbz
, 1);
5328 /* Handle b < a + 1. */
5329 if (TREE_CODE (op1
) == PLUS_EXPR
&& integer_onep (TREE_OPERAND (op1
, 1)))
5331 a
= TREE_OPERAND (op1
, 0);
5332 b
= TREE_OPERAND (mbz
, 0);
5340 /* Expected number of iterations is B - A - 1. Check that it matches
5341 the actual number, i.e., that B - A - NITER = 1. */
5342 tree_to_aff_combination (niter
->niter
, nit_type
, &nit
);
5343 tree_to_aff_combination (fold_convert (nit_type
, a
), nit_type
, &tmpa
);
5344 tree_to_aff_combination (fold_convert (nit_type
, b
), nit_type
, &tmpb
);
5345 aff_combination_scale (&nit
, -1);
5346 aff_combination_scale (&tmpa
, -1);
5347 aff_combination_add (&tmpb
, &tmpa
);
5348 aff_combination_add (&tmpb
, &nit
);
5349 if (tmpb
.n
!= 0 || maybe_ne (tmpb
.offset
, 1))
5352 /* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not
5354 offset
= fold_build2 (MULT_EXPR
, TREE_TYPE (cand
->iv
->step
),
5356 fold_convert (TREE_TYPE (cand
->iv
->step
), a
));
5357 if (!difference_cannot_overflow_p (data
, cand
->iv
->base
, offset
))
5360 /* Determine the new comparison operator. */
5361 comp
= step
< 0 ? GT_EXPR
: LT_EXPR
;
5362 if (*comp_p
== NE_EXPR
)
5364 else if (*comp_p
== EQ_EXPR
)
5365 *comp_p
= invert_tree_comparison (comp
, false);
5372 /* Check whether it is possible to express the condition in USE by comparison
5373 of candidate CAND. If so, store the value compared with to BOUND, and the
5374 comparison operator to COMP. */
5377 may_eliminate_iv (struct ivopts_data
*data
,
5378 struct iv_use
*use
, struct iv_cand
*cand
, tree
*bound
,
5379 enum tree_code
*comp
)
5384 class loop
*loop
= data
->current_loop
;
5386 class tree_niter_desc
*desc
= NULL
;
5388 if (TREE_CODE (cand
->iv
->step
) != INTEGER_CST
)
5391 /* For now works only for exits that dominate the loop latch.
5392 TODO: extend to other conditions inside loop body. */
5393 ex_bb
= gimple_bb (use
->stmt
);
5394 if (use
->stmt
!= last_stmt (ex_bb
)
5395 || gimple_code (use
->stmt
) != GIMPLE_COND
5396 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, ex_bb
))
5399 exit
= EDGE_SUCC (ex_bb
, 0);
5400 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
5401 exit
= EDGE_SUCC (ex_bb
, 1);
5402 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
5405 desc
= niter_for_exit (data
, exit
);
5409 /* Determine whether we can use the variable to test the exit condition.
5410 This is the case iff the period of the induction variable is greater
5411 than the number of iterations for which the exit condition is true. */
5412 period
= iv_period (cand
->iv
);
5414 /* If the number of iterations is constant, compare against it directly. */
5415 if (TREE_CODE (desc
->niter
) == INTEGER_CST
)
5417 /* See cand_value_at. */
5418 if (stmt_after_increment (loop
, cand
, use
->stmt
))
5420 if (!tree_int_cst_lt (desc
->niter
, period
))
5425 if (tree_int_cst_lt (period
, desc
->niter
))
5430 /* If not, and if this is the only possible exit of the loop, see whether
5431 we can get a conservative estimate on the number of iterations of the
5432 entire loop and compare against that instead. */
5435 widest_int period_value
, max_niter
;
5437 max_niter
= desc
->max
;
5438 if (stmt_after_increment (loop
, cand
, use
->stmt
))
5440 period_value
= wi::to_widest (period
);
5441 if (wi::gtu_p (max_niter
, period_value
))
5443 /* See if we can take advantage of inferred loop bound
5445 if (data
->loop_single_exit_p
)
5447 if (!max_loop_iterations (loop
, &max_niter
))
5449 /* The loop bound is already adjusted by adding 1. */
5450 if (wi::gtu_p (max_niter
, period_value
))
5458 /* For doloop IV cand, the bound would be zero. It's safe whether
5459 may_be_zero set or not. */
5462 *bound
= build_int_cst (TREE_TYPE (cand
->iv
->base
), 0);
5463 *comp
= iv_elimination_compare (data
, use
);
5467 cand_value_at (loop
, cand
, use
->stmt
, desc
, &bnd
);
5469 *bound
= fold_convert (TREE_TYPE (cand
->iv
->base
),
5470 aff_combination_to_tree (&bnd
));
5471 *comp
= iv_elimination_compare (data
, use
);
5473 /* It is unlikely that computing the number of iterations using division
5474 would be more profitable than keeping the original induction variable. */
5475 if (expression_expensive_p (*bound
))
5478 /* Sometimes, it is possible to handle the situation that the number of
5479 iterations may be zero unless additional assumptions by using <
5480 instead of != in the exit condition.
5482 TODO: we could also calculate the value MAY_BE_ZERO ? 0 : NITER and
5483 base the exit condition on it. However, that is often too
5485 if (!integer_zerop (desc
->may_be_zero
))
5486 return iv_elimination_compare_lt (data
, cand
, comp
, desc
);
5491 /* Calculates the cost of BOUND, if it is a PARM_DECL. A PARM_DECL must
5492 be copied, if it is used in the loop body and DATA->body_includes_call. */
5495 parm_decl_cost (struct ivopts_data
*data
, tree bound
)
5497 tree sbound
= bound
;
5498 STRIP_NOPS (sbound
);
5500 if (TREE_CODE (sbound
) == SSA_NAME
5501 && SSA_NAME_IS_DEFAULT_DEF (sbound
)
5502 && TREE_CODE (SSA_NAME_VAR (sbound
)) == PARM_DECL
5503 && data
->body_includes_call
)
5504 return COSTS_N_INSNS (1);
5509 /* Determines cost of computing the use in GROUP with CAND in a condition. */
5512 determine_group_iv_cost_cond (struct ivopts_data
*data
,
5513 struct iv_group
*group
, struct iv_cand
*cand
)
5515 tree bound
= NULL_TREE
;
5517 bitmap inv_exprs
= NULL
;
5518 bitmap inv_vars_elim
= NULL
, inv_vars_express
= NULL
, inv_vars
;
5519 comp_cost elim_cost
= infinite_cost
, express_cost
, cost
, bound_cost
;
5520 enum comp_iv_rewrite rewrite_type
;
5521 iv_inv_expr_ent
*inv_expr_elim
= NULL
, *inv_expr_express
= NULL
, *inv_expr
;
5522 tree
*control_var
, *bound_cst
;
5523 enum tree_code comp
= ERROR_MARK
;
5524 struct iv_use
*use
= group
->vuses
[0];
5526 /* Extract condition operands. */
5527 rewrite_type
= extract_cond_operands (data
, use
->stmt
, &control_var
,
5528 &bound_cst
, NULL
, &cmp_iv
);
5529 gcc_assert (rewrite_type
!= COMP_IV_NA
);
5531 /* Try iv elimination. */
5532 if (rewrite_type
== COMP_IV_ELIM
5533 && may_eliminate_iv (data
, use
, cand
, &bound
, &comp
))
5535 elim_cost
= force_var_cost (data
, bound
, &inv_vars_elim
);
5536 if (elim_cost
.cost
== 0)
5537 elim_cost
.cost
= parm_decl_cost (data
, bound
);
5538 else if (TREE_CODE (bound
) == INTEGER_CST
)
5540 /* If we replace a loop condition 'i < n' with 'p < base + n',
5541 inv_vars_elim will have 'base' and 'n' set, which implies that both
5542 'base' and 'n' will be live during the loop. More likely,
5543 'base + n' will be loop invariant, resulting in only one live value
5544 during the loop. So in that case we clear inv_vars_elim and set
5545 inv_expr_elim instead. */
5546 if (inv_vars_elim
&& bitmap_count_bits (inv_vars_elim
) > 1)
5548 inv_expr_elim
= get_loop_invariant_expr (data
, bound
);
5549 bitmap_clear (inv_vars_elim
);
5551 /* The bound is a loop invariant, so it will be only computed
5553 elim_cost
.cost
= adjust_setup_cost (data
, elim_cost
.cost
);
5556 /* When the condition is a comparison of the candidate IV against
5557 zero, prefer this IV.
5559 TODO: The constant that we're subtracting from the cost should
5560 be target-dependent. This information should be added to the
5561 target costs for each backend. */
5562 if (!elim_cost
.infinite_cost_p () /* Do not try to decrease infinite! */
5563 && integer_zerop (*bound_cst
)
5564 && (operand_equal_p (*control_var
, cand
->var_after
, 0)
5565 || operand_equal_p (*control_var
, cand
->var_before
, 0)))
5568 express_cost
= get_computation_cost (data
, use
, cand
, false,
5569 &inv_vars_express
, NULL
,
5572 find_inv_vars (data
, &cmp_iv
->base
, &inv_vars_express
);
5574 /* Count the cost of the original bound as well. */
5575 bound_cost
= force_var_cost (data
, *bound_cst
, NULL
);
5576 if (bound_cost
.cost
== 0)
5577 bound_cost
.cost
= parm_decl_cost (data
, *bound_cst
);
5578 else if (TREE_CODE (*bound_cst
) == INTEGER_CST
)
5579 bound_cost
.cost
= 0;
5580 express_cost
+= bound_cost
;
5582 /* Choose the better approach, preferring the eliminated IV. */
5583 if (elim_cost
<= express_cost
)
5586 inv_vars
= inv_vars_elim
;
5587 inv_vars_elim
= NULL
;
5588 inv_expr
= inv_expr_elim
;
5589 /* For doloop candidate/use pair, adjust to zero cost. */
5590 if (group
->doloop_p
&& cand
->doloop_p
&& elim_cost
.cost
> no_cost
.cost
)
5595 cost
= express_cost
;
5596 inv_vars
= inv_vars_express
;
5597 inv_vars_express
= NULL
;
5600 inv_expr
= inv_expr_express
;
5605 inv_exprs
= BITMAP_ALLOC (NULL
);
5606 bitmap_set_bit (inv_exprs
, inv_expr
->id
);
5608 set_group_iv_cost (data
, group
, cand
, cost
,
5609 inv_vars
, bound
, comp
, inv_exprs
);
5612 BITMAP_FREE (inv_vars_elim
);
5613 if (inv_vars_express
)
5614 BITMAP_FREE (inv_vars_express
);
5616 return !cost
.infinite_cost_p ();
5619 /* Determines cost of computing uses in GROUP with CAND. Returns false
5620 if USE cannot be represented with CAND. */
5623 determine_group_iv_cost (struct ivopts_data
*data
,
5624 struct iv_group
*group
, struct iv_cand
*cand
)
5626 switch (group
->type
)
5628 case USE_NONLINEAR_EXPR
:
5629 return determine_group_iv_cost_generic (data
, group
, cand
);
5631 case USE_REF_ADDRESS
:
5632 case USE_PTR_ADDRESS
:
5633 return determine_group_iv_cost_address (data
, group
, cand
);
5636 return determine_group_iv_cost_cond (data
, group
, cand
);
5643 /* Return true if get_computation_cost indicates that autoincrement is
5644 a possibility for the pair of USE and CAND, false otherwise. */
5647 autoinc_possible_for_pair (struct ivopts_data
*data
, struct iv_use
*use
,
5648 struct iv_cand
*cand
)
5650 if (!address_p (use
->type
))
5653 bool can_autoinc
= false;
5654 get_computation_cost (data
, use
, cand
, true, NULL
, &can_autoinc
, NULL
);
5658 /* Examine IP_ORIGINAL candidates to see if they are incremented next to a
5659 use that allows autoincrement, and set their AINC_USE if possible. */
5662 set_autoinc_for_original_candidates (struct ivopts_data
*data
)
5666 for (i
= 0; i
< data
->vcands
.length (); i
++)
5668 struct iv_cand
*cand
= data
->vcands
[i
];
5669 struct iv_use
*closest_before
= NULL
;
5670 struct iv_use
*closest_after
= NULL
;
5671 if (cand
->pos
!= IP_ORIGINAL
)
5674 for (j
= 0; j
< data
->vgroups
.length (); j
++)
5676 struct iv_group
*group
= data
->vgroups
[j
];
5677 struct iv_use
*use
= group
->vuses
[0];
5678 unsigned uid
= gimple_uid (use
->stmt
);
5680 if (gimple_bb (use
->stmt
) != gimple_bb (cand
->incremented_at
))
5683 if (uid
< gimple_uid (cand
->incremented_at
)
5684 && (closest_before
== NULL
5685 || uid
> gimple_uid (closest_before
->stmt
)))
5686 closest_before
= use
;
5688 if (uid
> gimple_uid (cand
->incremented_at
)
5689 && (closest_after
== NULL
5690 || uid
< gimple_uid (closest_after
->stmt
)))
5691 closest_after
= use
;
5694 if (closest_before
!= NULL
5695 && autoinc_possible_for_pair (data
, closest_before
, cand
))
5696 cand
->ainc_use
= closest_before
;
5697 else if (closest_after
!= NULL
5698 && autoinc_possible_for_pair (data
, closest_after
, cand
))
5699 cand
->ainc_use
= closest_after
;
5703 /* Relate compare use with all candidates. */
5706 relate_compare_use_with_all_cands (struct ivopts_data
*data
)
5708 unsigned i
, count
= data
->vcands
.length ();
5709 for (i
= 0; i
< data
->vgroups
.length (); i
++)
5711 struct iv_group
*group
= data
->vgroups
[i
];
5713 if (group
->type
== USE_COMPARE
)
5714 bitmap_set_range (group
->related_cands
, 0, count
);
5718 /* If PREFERRED_MODE is suitable and profitable, use the preferred
5719 PREFERRED_MODE to compute doloop iv base from niter: base = niter + 1. */
5722 compute_doloop_base_on_mode (machine_mode preferred_mode
, tree niter
,
5723 const widest_int
&iterations_max
)
5725 tree ntype
= TREE_TYPE (niter
);
5726 tree pref_type
= lang_hooks
.types
.type_for_mode (preferred_mode
, 1);
5728 return fold_build2 (PLUS_EXPR
, ntype
, unshare_expr (niter
),
5729 build_int_cst (ntype
, 1));
5731 gcc_assert (TREE_CODE (pref_type
) == INTEGER_TYPE
);
5733 int prec
= TYPE_PRECISION (ntype
);
5734 int pref_prec
= TYPE_PRECISION (pref_type
);
5738 /* Check if the PREFERRED_MODED is able to present niter. */
5739 if (pref_prec
> prec
5740 || wi::ltu_p (iterations_max
,
5741 widest_int::from (wi::max_value (pref_prec
, UNSIGNED
),
5744 /* No wrap, it is safe to use preferred type after niter + 1. */
5745 if (wi::ltu_p (iterations_max
,
5746 widest_int::from (wi::max_value (prec
, UNSIGNED
),
5749 /* This could help to optimize "-1 +1" pair when niter looks
5750 like "n-1": n is in original mode. "base = (n - 1) + 1"
5751 in PREFERRED_MODED: it could be base = (PREFERRED_TYPE)n. */
5752 base
= fold_build2 (PLUS_EXPR
, ntype
, unshare_expr (niter
),
5753 build_int_cst (ntype
, 1));
5754 base
= fold_convert (pref_type
, base
);
5757 /* To avoid wrap, convert niter to preferred type before plus 1. */
5760 niter
= fold_convert (pref_type
, niter
);
5761 base
= fold_build2 (PLUS_EXPR
, pref_type
, unshare_expr (niter
),
5762 build_int_cst (pref_type
, 1));
5766 base
= fold_build2 (PLUS_EXPR
, ntype
, unshare_expr (niter
),
5767 build_int_cst (ntype
, 1));
5771 /* Add one doloop dedicated IV candidate:
5772 - Base is (may_be_zero ? 1 : (niter + 1)).
5776 add_iv_candidate_for_doloop (struct ivopts_data
*data
)
5778 tree_niter_desc
*niter_desc
= niter_for_single_dom_exit (data
);
5779 gcc_assert (niter_desc
&& niter_desc
->assumptions
);
5781 tree niter
= niter_desc
->niter
;
5782 tree ntype
= TREE_TYPE (niter
);
5783 gcc_assert (TREE_CODE (ntype
) == INTEGER_TYPE
);
5785 tree may_be_zero
= niter_desc
->may_be_zero
;
5786 if (may_be_zero
&& integer_zerop (may_be_zero
))
5787 may_be_zero
= NULL_TREE
;
5790 if (COMPARISON_CLASS_P (may_be_zero
))
5792 niter
= fold_build3 (COND_EXPR
, ntype
, may_be_zero
,
5793 build_int_cst (ntype
, 0),
5794 rewrite_to_non_trapping_overflow (niter
));
5796 /* Don't try to obtain the iteration count expression when may_be_zero is
5797 integer_nonzerop (actually iteration count is one) or else. */
5802 machine_mode mode
= TYPE_MODE (ntype
);
5803 machine_mode pref_mode
= targetm
.preferred_doloop_mode (mode
);
5806 if (mode
!= pref_mode
)
5808 base
= compute_doloop_base_on_mode (pref_mode
, niter
, niter_desc
->max
);
5809 ntype
= TREE_TYPE (base
);
5812 base
= fold_build2 (PLUS_EXPR
, ntype
, unshare_expr (niter
),
5813 build_int_cst (ntype
, 1));
5816 add_candidate (data
, base
, build_int_cst (ntype
, -1), true, NULL
, NULL
, true);
5819 /* Finds the candidates for the induction variables. */
5822 find_iv_candidates (struct ivopts_data
*data
)
5824 /* Add commonly used ivs. */
5825 add_standard_iv_candidates (data
);
5827 /* Add doloop dedicated ivs. */
5828 if (data
->doloop_use_p
)
5829 add_iv_candidate_for_doloop (data
);
5831 /* Add old induction variables. */
5832 add_iv_candidate_for_bivs (data
);
5834 /* Add induction variables derived from uses. */
5835 add_iv_candidate_for_groups (data
);
5837 set_autoinc_for_original_candidates (data
);
5839 /* Record the important candidates. */
5840 record_important_candidates (data
);
5842 /* Relate compare iv_use with all candidates. */
5843 if (!data
->consider_all_candidates
)
5844 relate_compare_use_with_all_cands (data
);
5846 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5850 fprintf (dump_file
, "\n<Important Candidates>:\t");
5851 for (i
= 0; i
< data
->vcands
.length (); i
++)
5852 if (data
->vcands
[i
]->important
)
5853 fprintf (dump_file
, " %d,", data
->vcands
[i
]->id
);
5854 fprintf (dump_file
, "\n");
5856 fprintf (dump_file
, "\n<Group, Cand> Related:\n");
5857 for (i
= 0; i
< data
->vgroups
.length (); i
++)
5859 struct iv_group
*group
= data
->vgroups
[i
];
5861 if (group
->related_cands
)
5863 fprintf (dump_file
, " Group %d:\t", group
->id
);
5864 dump_bitmap (dump_file
, group
->related_cands
);
5867 fprintf (dump_file
, "\n");
5871 /* Determines costs of computing use of iv with an iv candidate. */
5874 determine_group_iv_costs (struct ivopts_data
*data
)
5877 struct iv_cand
*cand
;
5878 struct iv_group
*group
;
5879 bitmap to_clear
= BITMAP_ALLOC (NULL
);
5881 alloc_use_cost_map (data
);
5883 for (i
= 0; i
< data
->vgroups
.length (); i
++)
5885 group
= data
->vgroups
[i
];
5887 if (data
->consider_all_candidates
)
5889 for (j
= 0; j
< data
->vcands
.length (); j
++)
5891 cand
= data
->vcands
[j
];
5892 determine_group_iv_cost (data
, group
, cand
);
5899 EXECUTE_IF_SET_IN_BITMAP (group
->related_cands
, 0, j
, bi
)
5901 cand
= data
->vcands
[j
];
5902 if (!determine_group_iv_cost (data
, group
, cand
))
5903 bitmap_set_bit (to_clear
, j
);
5906 /* Remove the candidates for that the cost is infinite from
5907 the list of related candidates. */
5908 bitmap_and_compl_into (group
->related_cands
, to_clear
);
5909 bitmap_clear (to_clear
);
5913 BITMAP_FREE (to_clear
);
5915 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5919 /* Dump invariant variables. */
5920 fprintf (dump_file
, "\n<Invariant Vars>:\n");
5921 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
5923 struct version_info
*info
= ver_info (data
, i
);
5926 fprintf (dump_file
, "Inv %d:\t", info
->inv_id
);
5927 print_generic_expr (dump_file
, info
->name
, TDF_SLIM
);
5928 fprintf (dump_file
, "%s\n",
5929 info
->has_nonlin_use
? "" : "\t(eliminable)");
5933 /* Dump invariant expressions. */
5934 fprintf (dump_file
, "\n<Invariant Expressions>:\n");
5935 auto_vec
<iv_inv_expr_ent
*> list (data
->inv_expr_tab
->elements ());
5937 for (hash_table
<iv_inv_expr_hasher
>::iterator it
5938 = data
->inv_expr_tab
->begin (); it
!= data
->inv_expr_tab
->end ();
5940 list
.safe_push (*it
);
5942 list
.qsort (sort_iv_inv_expr_ent
);
5944 for (i
= 0; i
< list
.length (); ++i
)
5946 fprintf (dump_file
, "inv_expr %d: \t", list
[i
]->id
);
5947 print_generic_expr (dump_file
, list
[i
]->expr
, TDF_SLIM
);
5948 fprintf (dump_file
, "\n");
5951 fprintf (dump_file
, "\n<Group-candidate Costs>:\n");
5953 for (i
= 0; i
< data
->vgroups
.length (); i
++)
5955 group
= data
->vgroups
[i
];
5957 fprintf (dump_file
, "Group %d:\n", i
);
5958 fprintf (dump_file
, " cand\tcost\tcompl.\tinv.expr.\tinv.vars\n");
5959 for (j
= 0; j
< group
->n_map_members
; j
++)
5961 if (!group
->cost_map
[j
].cand
5962 || group
->cost_map
[j
].cost
.infinite_cost_p ())
5965 fprintf (dump_file
, " %d\t%" PRId64
"\t%d\t",
5966 group
->cost_map
[j
].cand
->id
,
5967 group
->cost_map
[j
].cost
.cost
,
5968 group
->cost_map
[j
].cost
.complexity
);
5969 if (!group
->cost_map
[j
].inv_exprs
5970 || bitmap_empty_p (group
->cost_map
[j
].inv_exprs
))
5971 fprintf (dump_file
, "NIL;\t");
5973 bitmap_print (dump_file
,
5974 group
->cost_map
[j
].inv_exprs
, "", ";\t");
5975 if (!group
->cost_map
[j
].inv_vars
5976 || bitmap_empty_p (group
->cost_map
[j
].inv_vars
))
5977 fprintf (dump_file
, "NIL;\n");
5979 bitmap_print (dump_file
,
5980 group
->cost_map
[j
].inv_vars
, "", "\n");
5983 fprintf (dump_file
, "\n");
5985 fprintf (dump_file
, "\n");
5989 /* Determines cost of the candidate CAND. */
5992 determine_iv_cost (struct ivopts_data
*data
, struct iv_cand
*cand
)
5994 comp_cost cost_base
;
5995 int64_t cost
, cost_step
;
5998 gcc_assert (cand
->iv
!= NULL
);
6000 /* There are two costs associated with the candidate -- its increment
6001 and its initialization. The second is almost negligible for any loop
6002 that rolls enough, so we take it just very little into account. */
6004 base
= cand
->iv
->base
;
6005 cost_base
= force_var_cost (data
, base
, NULL
);
6006 /* It will be exceptional that the iv register happens to be initialized with
6007 the proper value at no cost. In general, there will at least be a regcopy
6009 if (cost_base
.cost
== 0)
6010 cost_base
.cost
= COSTS_N_INSNS (1);
6011 /* Doloop decrement should be considered as zero cost. */
6015 cost_step
= add_cost (data
->speed
, TYPE_MODE (TREE_TYPE (base
)));
6016 cost
= cost_step
+ adjust_setup_cost (data
, cost_base
.cost
);
6018 /* Prefer the original ivs unless we may gain something by replacing it.
6019 The reason is to make debugging simpler; so this is not relevant for
6020 artificial ivs created by other optimization passes. */
6021 if ((cand
->pos
!= IP_ORIGINAL
6022 || !SSA_NAME_VAR (cand
->var_before
)
6023 || DECL_ARTIFICIAL (SSA_NAME_VAR (cand
->var_before
)))
6024 /* Prefer doloop as well. */
6028 /* Prefer not to insert statements into latch unless there are some
6029 already (so that we do not create unnecessary jumps). */
6030 if (cand
->pos
== IP_END
6031 && empty_block_p (ip_end_pos (data
->current_loop
)))
6035 cand
->cost_step
= cost_step
;
6038 /* Determines costs of computation of the candidates. */
6041 determine_iv_costs (struct ivopts_data
*data
)
6045 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6047 fprintf (dump_file
, "<Candidate Costs>:\n");
6048 fprintf (dump_file
, " cand\tcost\n");
6051 for (i
= 0; i
< data
->vcands
.length (); i
++)
6053 struct iv_cand
*cand
= data
->vcands
[i
];
6055 determine_iv_cost (data
, cand
);
6057 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6058 fprintf (dump_file
, " %d\t%d\n", i
, cand
->cost
);
6061 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6062 fprintf (dump_file
, "\n");
6065 /* Estimate register pressure for loop having N_INVS invariants and N_CANDS
6066 induction variables. Note N_INVS includes both invariant variables and
6067 invariant expressions. */
6070 ivopts_estimate_reg_pressure (struct ivopts_data
*data
, unsigned n_invs
,
6074 unsigned n_old
= data
->regs_used
, n_new
= n_invs
+ n_cands
;
6075 unsigned regs_needed
= n_new
+ n_old
, available_regs
= target_avail_regs
;
6076 bool speed
= data
->speed
;
6078 /* If there is a call in the loop body, the call-clobbered registers
6079 are not available for loop invariants. */
6080 if (data
->body_includes_call
)
6081 available_regs
= available_regs
- target_clobbered_regs
;
6083 /* If we have enough registers. */
6084 if (regs_needed
+ target_res_regs
< available_regs
)
6086 /* If close to running out of registers, try to preserve them. */
6087 else if (regs_needed
<= available_regs
)
6088 cost
= target_reg_cost
[speed
] * regs_needed
;
6089 /* If we run out of available registers but the number of candidates
6090 does not, we penalize extra registers using target_spill_cost. */
6091 else if (n_cands
<= available_regs
)
6092 cost
= target_reg_cost
[speed
] * available_regs
6093 + target_spill_cost
[speed
] * (regs_needed
- available_regs
);
6094 /* If the number of candidates runs out available registers, we penalize
6095 extra candidate registers using target_spill_cost * 2. Because it is
6096 more expensive to spill induction variable than invariant. */
6098 cost
= target_reg_cost
[speed
] * available_regs
6099 + target_spill_cost
[speed
] * (n_cands
- available_regs
) * 2
6100 + target_spill_cost
[speed
] * (regs_needed
- n_cands
);
6102 /* Finally, add the number of candidates, so that we prefer eliminating
6103 induction variables if possible. */
6104 return cost
+ n_cands
;
6107 /* For each size of the induction variable set determine the penalty. */
6110 determine_set_costs (struct ivopts_data
*data
)
6116 class loop
*loop
= data
->current_loop
;
6119 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6121 fprintf (dump_file
, "<Global Costs>:\n");
6122 fprintf (dump_file
, " target_avail_regs %d\n", target_avail_regs
);
6123 fprintf (dump_file
, " target_clobbered_regs %d\n", target_clobbered_regs
);
6124 fprintf (dump_file
, " target_reg_cost %d\n", target_reg_cost
[data
->speed
]);
6125 fprintf (dump_file
, " target_spill_cost %d\n", target_spill_cost
[data
->speed
]);
6129 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
6132 op
= PHI_RESULT (phi
);
6134 if (virtual_operand_p (op
))
6137 if (get_iv (data
, op
))
6140 if (!POINTER_TYPE_P (TREE_TYPE (op
))
6141 && !INTEGRAL_TYPE_P (TREE_TYPE (op
)))
6147 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
6149 struct version_info
*info
= ver_info (data
, j
);
6151 if (info
->inv_id
&& info
->has_nonlin_use
)
6155 data
->regs_used
= n
;
6156 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6157 fprintf (dump_file
, " regs_used %d\n", n
);
6159 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6161 fprintf (dump_file
, " cost for size:\n");
6162 fprintf (dump_file
, " ivs\tcost\n");
6163 for (j
= 0; j
<= 2 * target_avail_regs
; j
++)
6164 fprintf (dump_file
, " %d\t%d\n", j
,
6165 ivopts_estimate_reg_pressure (data
, 0, j
));
6166 fprintf (dump_file
, "\n");
6170 /* Returns true if A is a cheaper cost pair than B. */
6173 cheaper_cost_pair (class cost_pair
*a
, class cost_pair
*b
)
6181 if (a
->cost
< b
->cost
)
6184 if (b
->cost
< a
->cost
)
6187 /* In case the costs are the same, prefer the cheaper candidate. */
6188 if (a
->cand
->cost
< b
->cand
->cost
)
6194 /* Compare if A is a more expensive cost pair than B. Return 1, 0 and -1
6195 for more expensive, equal and cheaper respectively. */
6198 compare_cost_pair (class cost_pair
*a
, class cost_pair
*b
)
6200 if (cheaper_cost_pair (a
, b
))
6202 if (cheaper_cost_pair (b
, a
))
6208 /* Returns candidate by that USE is expressed in IVS. */
6210 static class cost_pair
*
6211 iv_ca_cand_for_group (class iv_ca
*ivs
, struct iv_group
*group
)
6213 return ivs
->cand_for_group
[group
->id
];
6216 /* Computes the cost field of IVS structure. */
6219 iv_ca_recount_cost (struct ivopts_data
*data
, class iv_ca
*ivs
)
6221 comp_cost cost
= ivs
->cand_use_cost
;
6223 cost
+= ivs
->cand_cost
;
6224 cost
+= ivopts_estimate_reg_pressure (data
, ivs
->n_invs
, ivs
->n_cands
);
6228 /* Remove use of invariants in set INVS by decreasing counter in N_INV_USES
6232 iv_ca_set_remove_invs (class iv_ca
*ivs
, bitmap invs
, unsigned *n_inv_uses
)
6240 gcc_assert (n_inv_uses
!= NULL
);
6241 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
6244 if (n_inv_uses
[iid
] == 0)
6249 /* Set USE not to be expressed by any candidate in IVS. */
6252 iv_ca_set_no_cp (struct ivopts_data
*data
, class iv_ca
*ivs
,
6253 struct iv_group
*group
)
6255 unsigned gid
= group
->id
, cid
;
6256 class cost_pair
*cp
;
6258 cp
= ivs
->cand_for_group
[gid
];
6264 ivs
->cand_for_group
[gid
] = NULL
;
6265 ivs
->n_cand_uses
[cid
]--;
6267 if (ivs
->n_cand_uses
[cid
] == 0)
6269 bitmap_clear_bit (ivs
->cands
, cid
);
6270 if (!cp
->cand
->doloop_p
|| !targetm
.have_count_reg_decr_p
)
6272 ivs
->cand_cost
-= cp
->cand
->cost
;
6273 iv_ca_set_remove_invs (ivs
, cp
->cand
->inv_vars
, ivs
->n_inv_var_uses
);
6274 iv_ca_set_remove_invs (ivs
, cp
->cand
->inv_exprs
, ivs
->n_inv_expr_uses
);
6277 ivs
->cand_use_cost
-= cp
->cost
;
6278 iv_ca_set_remove_invs (ivs
, cp
->inv_vars
, ivs
->n_inv_var_uses
);
6279 iv_ca_set_remove_invs (ivs
, cp
->inv_exprs
, ivs
->n_inv_expr_uses
);
6280 iv_ca_recount_cost (data
, ivs
);
6283 /* Add use of invariants in set INVS by increasing counter in N_INV_USES and
6287 iv_ca_set_add_invs (class iv_ca
*ivs
, bitmap invs
, unsigned *n_inv_uses
)
6295 gcc_assert (n_inv_uses
!= NULL
);
6296 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
6299 if (n_inv_uses
[iid
] == 1)
6304 /* Set cost pair for GROUP in set IVS to CP. */
6307 iv_ca_set_cp (struct ivopts_data
*data
, class iv_ca
*ivs
,
6308 struct iv_group
*group
, class cost_pair
*cp
)
6310 unsigned gid
= group
->id
, cid
;
6312 if (ivs
->cand_for_group
[gid
] == cp
)
6315 if (ivs
->cand_for_group
[gid
])
6316 iv_ca_set_no_cp (data
, ivs
, group
);
6323 ivs
->cand_for_group
[gid
] = cp
;
6324 ivs
->n_cand_uses
[cid
]++;
6325 if (ivs
->n_cand_uses
[cid
] == 1)
6327 bitmap_set_bit (ivs
->cands
, cid
);
6328 if (!cp
->cand
->doloop_p
|| !targetm
.have_count_reg_decr_p
)
6330 ivs
->cand_cost
+= cp
->cand
->cost
;
6331 iv_ca_set_add_invs (ivs
, cp
->cand
->inv_vars
, ivs
->n_inv_var_uses
);
6332 iv_ca_set_add_invs (ivs
, cp
->cand
->inv_exprs
, ivs
->n_inv_expr_uses
);
6335 ivs
->cand_use_cost
+= cp
->cost
;
6336 iv_ca_set_add_invs (ivs
, cp
->inv_vars
, ivs
->n_inv_var_uses
);
6337 iv_ca_set_add_invs (ivs
, cp
->inv_exprs
, ivs
->n_inv_expr_uses
);
6338 iv_ca_recount_cost (data
, ivs
);
6342 /* Extend set IVS by expressing USE by some of the candidates in it
6343 if possible. Consider all important candidates if candidates in
6344 set IVS don't give any result. */
6347 iv_ca_add_group (struct ivopts_data
*data
, class iv_ca
*ivs
,
6348 struct iv_group
*group
)
6350 class cost_pair
*best_cp
= NULL
, *cp
;
6353 struct iv_cand
*cand
;
6355 gcc_assert (ivs
->upto
>= group
->id
);
6359 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
6361 cand
= data
->vcands
[i
];
6362 cp
= get_group_iv_cost (data
, group
, cand
);
6363 if (cheaper_cost_pair (cp
, best_cp
))
6367 if (best_cp
== NULL
)
6369 EXECUTE_IF_SET_IN_BITMAP (data
->important_candidates
, 0, i
, bi
)
6371 cand
= data
->vcands
[i
];
6372 cp
= get_group_iv_cost (data
, group
, cand
);
6373 if (cheaper_cost_pair (cp
, best_cp
))
6378 iv_ca_set_cp (data
, ivs
, group
, best_cp
);
6381 /* Get cost for assignment IVS. */
6384 iv_ca_cost (class iv_ca
*ivs
)
6386 /* This was a conditional expression but it triggered a bug in
6388 if (ivs
->bad_groups
)
6389 return infinite_cost
;
6394 /* Compare if applying NEW_CP to GROUP for IVS introduces more invariants
6395 than OLD_CP. Return 1, 0 and -1 for more, equal and fewer invariants
6399 iv_ca_compare_deps (struct ivopts_data
*data
, class iv_ca
*ivs
,
6400 struct iv_group
*group
, class cost_pair
*old_cp
,
6401 class cost_pair
*new_cp
)
6403 gcc_assert (old_cp
&& new_cp
&& old_cp
!= new_cp
);
6404 unsigned old_n_invs
= ivs
->n_invs
;
6405 iv_ca_set_cp (data
, ivs
, group
, new_cp
);
6406 unsigned new_n_invs
= ivs
->n_invs
;
6407 iv_ca_set_cp (data
, ivs
, group
, old_cp
);
6409 return new_n_invs
> old_n_invs
? 1 : (new_n_invs
< old_n_invs
? -1 : 0);
6412 /* Creates change of expressing GROUP by NEW_CP instead of OLD_CP and chains
6415 static struct iv_ca_delta
*
6416 iv_ca_delta_add (struct iv_group
*group
, class cost_pair
*old_cp
,
6417 class cost_pair
*new_cp
, struct iv_ca_delta
*next
)
6419 struct iv_ca_delta
*change
= XNEW (struct iv_ca_delta
);
6421 change
->group
= group
;
6422 change
->old_cp
= old_cp
;
6423 change
->new_cp
= new_cp
;
6424 change
->next
= next
;
6429 /* Joins two lists of changes L1 and L2. Destructive -- old lists
6432 static struct iv_ca_delta
*
6433 iv_ca_delta_join (struct iv_ca_delta
*l1
, struct iv_ca_delta
*l2
)
6435 struct iv_ca_delta
*last
;
6443 for (last
= l1
; last
->next
; last
= last
->next
)
6450 /* Reverse the list of changes DELTA, forming the inverse to it. */
6452 static struct iv_ca_delta
*
6453 iv_ca_delta_reverse (struct iv_ca_delta
*delta
)
6455 struct iv_ca_delta
*act
, *next
, *prev
= NULL
;
6457 for (act
= delta
; act
; act
= next
)
6463 std::swap (act
->old_cp
, act
->new_cp
);
6469 /* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
6470 reverted instead. */
6473 iv_ca_delta_commit (struct ivopts_data
*data
, class iv_ca
*ivs
,
6474 struct iv_ca_delta
*delta
, bool forward
)
6476 class cost_pair
*from
, *to
;
6477 struct iv_ca_delta
*act
;
6480 delta
= iv_ca_delta_reverse (delta
);
6482 for (act
= delta
; act
; act
= act
->next
)
6486 gcc_assert (iv_ca_cand_for_group (ivs
, act
->group
) == from
);
6487 iv_ca_set_cp (data
, ivs
, act
->group
, to
);
6491 iv_ca_delta_reverse (delta
);
6494 /* Returns true if CAND is used in IVS. */
6497 iv_ca_cand_used_p (class iv_ca
*ivs
, struct iv_cand
*cand
)
6499 return ivs
->n_cand_uses
[cand
->id
] > 0;
6502 /* Returns number of induction variable candidates in the set IVS. */
6505 iv_ca_n_cands (class iv_ca
*ivs
)
6507 return ivs
->n_cands
;
6510 /* Free the list of changes DELTA. */
6513 iv_ca_delta_free (struct iv_ca_delta
**delta
)
6515 struct iv_ca_delta
*act
, *next
;
6517 for (act
= *delta
; act
; act
= next
)
6526 /* Allocates new iv candidates assignment. */
6528 static class iv_ca
*
6529 iv_ca_new (struct ivopts_data
*data
)
6531 class iv_ca
*nw
= XNEW (class iv_ca
);
6535 nw
->cand_for_group
= XCNEWVEC (class cost_pair
*,
6536 data
->vgroups
.length ());
6537 nw
->n_cand_uses
= XCNEWVEC (unsigned, data
->vcands
.length ());
6538 nw
->cands
= BITMAP_ALLOC (NULL
);
6541 nw
->cand_use_cost
= no_cost
;
6543 nw
->n_inv_var_uses
= XCNEWVEC (unsigned, data
->max_inv_var_id
+ 1);
6544 nw
->n_inv_expr_uses
= XCNEWVEC (unsigned, data
->max_inv_expr_id
+ 1);
6550 /* Free memory occupied by the set IVS. */
6553 iv_ca_free (class iv_ca
**ivs
)
6555 free ((*ivs
)->cand_for_group
);
6556 free ((*ivs
)->n_cand_uses
);
6557 BITMAP_FREE ((*ivs
)->cands
);
6558 free ((*ivs
)->n_inv_var_uses
);
6559 free ((*ivs
)->n_inv_expr_uses
);
6564 /* Dumps IVS to FILE. */
6567 iv_ca_dump (struct ivopts_data
*data
, FILE *file
, class iv_ca
*ivs
)
6570 comp_cost cost
= iv_ca_cost (ivs
);
6572 fprintf (file
, " cost: %" PRId64
" (complexity %d)\n", cost
.cost
,
6574 fprintf (file
, " reg_cost: %d\n",
6575 ivopts_estimate_reg_pressure (data
, ivs
->n_invs
, ivs
->n_cands
));
6576 fprintf (file
, " cand_cost: %" PRId64
"\n cand_group_cost: "
6577 "%" PRId64
" (complexity %d)\n", ivs
->cand_cost
,
6578 ivs
->cand_use_cost
.cost
, ivs
->cand_use_cost
.complexity
);
6579 bitmap_print (file
, ivs
->cands
, " candidates: ","\n");
6581 for (i
= 0; i
< ivs
->upto
; i
++)
6583 struct iv_group
*group
= data
->vgroups
[i
];
6584 class cost_pair
*cp
= iv_ca_cand_for_group (ivs
, group
);
6586 fprintf (file
, " group:%d --> iv_cand:%d, cost=("
6587 "%" PRId64
",%d)\n", group
->id
, cp
->cand
->id
,
6588 cp
->cost
.cost
, cp
->cost
.complexity
);
6590 fprintf (file
, " group:%d --> ??\n", group
->id
);
6593 const char *pref
= "";
6594 fprintf (file
, " invariant variables: ");
6595 for (i
= 1; i
<= data
->max_inv_var_id
; i
++)
6596 if (ivs
->n_inv_var_uses
[i
])
6598 fprintf (file
, "%s%d", pref
, i
);
6603 fprintf (file
, "\n invariant expressions: ");
6604 for (i
= 1; i
<= data
->max_inv_expr_id
; i
++)
6605 if (ivs
->n_inv_expr_uses
[i
])
6607 fprintf (file
, "%s%d", pref
, i
);
6611 fprintf (file
, "\n\n");
6614 /* Try changing candidate in IVS to CAND for each use. Return cost of the
6615 new set, and store differences in DELTA. Number of induction variables
6616 in the new set is stored to N_IVS. MIN_NCAND is a flag. When it is true
6617 the function will try to find a solution with mimimal iv candidates. */
6620 iv_ca_extend (struct ivopts_data
*data
, class iv_ca
*ivs
,
6621 struct iv_cand
*cand
, struct iv_ca_delta
**delta
,
6622 unsigned *n_ivs
, bool min_ncand
)
6626 struct iv_group
*group
;
6627 class cost_pair
*old_cp
, *new_cp
;
6630 for (i
= 0; i
< ivs
->upto
; i
++)
6632 group
= data
->vgroups
[i
];
6633 old_cp
= iv_ca_cand_for_group (ivs
, group
);
6636 && old_cp
->cand
== cand
)
6639 new_cp
= get_group_iv_cost (data
, group
, cand
);
6645 int cmp_invs
= iv_ca_compare_deps (data
, ivs
, group
, old_cp
, new_cp
);
6646 /* Skip if new_cp depends on more invariants. */
6650 int cmp_cost
= compare_cost_pair (new_cp
, old_cp
);
6651 /* Skip if new_cp is not cheaper. */
6652 if (cmp_cost
> 0 || (cmp_cost
== 0 && cmp_invs
== 0))
6656 *delta
= iv_ca_delta_add (group
, old_cp
, new_cp
, *delta
);
6659 iv_ca_delta_commit (data
, ivs
, *delta
, true);
6660 cost
= iv_ca_cost (ivs
);
6662 *n_ivs
= iv_ca_n_cands (ivs
);
6663 iv_ca_delta_commit (data
, ivs
, *delta
, false);
6668 /* Try narrowing set IVS by removing CAND. Return the cost of
6669 the new set and store the differences in DELTA. START is
6670 the candidate with which we start narrowing. */
6673 iv_ca_narrow (struct ivopts_data
*data
, class iv_ca
*ivs
,
6674 struct iv_cand
*cand
, struct iv_cand
*start
,
6675 struct iv_ca_delta
**delta
)
6678 struct iv_group
*group
;
6679 class cost_pair
*old_cp
, *new_cp
, *cp
;
6681 struct iv_cand
*cnd
;
6682 comp_cost cost
, best_cost
, acost
;
6685 for (i
= 0; i
< data
->vgroups
.length (); i
++)
6687 group
= data
->vgroups
[i
];
6689 old_cp
= iv_ca_cand_for_group (ivs
, group
);
6690 if (old_cp
->cand
!= cand
)
6693 best_cost
= iv_ca_cost (ivs
);
6694 /* Start narrowing with START. */
6695 new_cp
= get_group_iv_cost (data
, group
, start
);
6697 if (data
->consider_all_candidates
)
6699 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, ci
, bi
)
6701 if (ci
== cand
->id
|| (start
&& ci
== start
->id
))
6704 cnd
= data
->vcands
[ci
];
6706 cp
= get_group_iv_cost (data
, group
, cnd
);
6710 iv_ca_set_cp (data
, ivs
, group
, cp
);
6711 acost
= iv_ca_cost (ivs
);
6713 if (acost
< best_cost
)
6722 EXECUTE_IF_AND_IN_BITMAP (group
->related_cands
, ivs
->cands
, 0, ci
, bi
)
6724 if (ci
== cand
->id
|| (start
&& ci
== start
->id
))
6727 cnd
= data
->vcands
[ci
];
6729 cp
= get_group_iv_cost (data
, group
, cnd
);
6733 iv_ca_set_cp (data
, ivs
, group
, cp
);
6734 acost
= iv_ca_cost (ivs
);
6736 if (acost
< best_cost
)
6743 /* Restore to old cp for use. */
6744 iv_ca_set_cp (data
, ivs
, group
, old_cp
);
6748 iv_ca_delta_free (delta
);
6749 return infinite_cost
;
6752 *delta
= iv_ca_delta_add (group
, old_cp
, new_cp
, *delta
);
6755 iv_ca_delta_commit (data
, ivs
, *delta
, true);
6756 cost
= iv_ca_cost (ivs
);
6757 iv_ca_delta_commit (data
, ivs
, *delta
, false);
6762 /* Try optimizing the set of candidates IVS by removing candidates different
6763 from to EXCEPT_CAND from it. Return cost of the new set, and store
6764 differences in DELTA. */
6767 iv_ca_prune (struct ivopts_data
*data
, class iv_ca
*ivs
,
6768 struct iv_cand
*except_cand
, struct iv_ca_delta
**delta
)
6771 struct iv_ca_delta
*act_delta
, *best_delta
;
6773 comp_cost best_cost
, acost
;
6774 struct iv_cand
*cand
;
6777 best_cost
= iv_ca_cost (ivs
);
6779 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
6781 cand
= data
->vcands
[i
];
6783 if (cand
== except_cand
)
6786 acost
= iv_ca_narrow (data
, ivs
, cand
, except_cand
, &act_delta
);
6788 if (acost
< best_cost
)
6791 iv_ca_delta_free (&best_delta
);
6792 best_delta
= act_delta
;
6795 iv_ca_delta_free (&act_delta
);
6804 /* Recurse to possibly remove other unnecessary ivs. */
6805 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
6806 best_cost
= iv_ca_prune (data
, ivs
, except_cand
, delta
);
6807 iv_ca_delta_commit (data
, ivs
, best_delta
, false);
6808 *delta
= iv_ca_delta_join (best_delta
, *delta
);
6812 /* Check if CAND_IDX is a candidate other than OLD_CAND and has
6813 cheaper local cost for GROUP than BEST_CP. Return pointer to
6814 the corresponding cost_pair, otherwise just return BEST_CP. */
6816 static class cost_pair
*
6817 cheaper_cost_with_cand (struct ivopts_data
*data
, struct iv_group
*group
,
6818 unsigned int cand_idx
, struct iv_cand
*old_cand
,
6819 class cost_pair
*best_cp
)
6821 struct iv_cand
*cand
;
6822 class cost_pair
*cp
;
6824 gcc_assert (old_cand
!= NULL
&& best_cp
!= NULL
);
6825 if (cand_idx
== old_cand
->id
)
6828 cand
= data
->vcands
[cand_idx
];
6829 cp
= get_group_iv_cost (data
, group
, cand
);
6830 if (cp
!= NULL
&& cheaper_cost_pair (cp
, best_cp
))
6836 /* Try breaking local optimal fixed-point for IVS by replacing candidates
6837 which are used by more than one iv uses. For each of those candidates,
6838 this function tries to represent iv uses under that candidate using
6839 other ones with lower local cost, then tries to prune the new set.
6840 If the new set has lower cost, It returns the new cost after recording
6841 candidate replacement in list DELTA. */
6844 iv_ca_replace (struct ivopts_data
*data
, class iv_ca
*ivs
,
6845 struct iv_ca_delta
**delta
)
6847 bitmap_iterator bi
, bj
;
6848 unsigned int i
, j
, k
;
6849 struct iv_cand
*cand
;
6850 comp_cost orig_cost
, acost
;
6851 struct iv_ca_delta
*act_delta
, *tmp_delta
;
6852 class cost_pair
*old_cp
, *best_cp
= NULL
;
6855 orig_cost
= iv_ca_cost (ivs
);
6857 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
6859 if (ivs
->n_cand_uses
[i
] == 1
6860 || ivs
->n_cand_uses
[i
] > ALWAYS_PRUNE_CAND_SET_BOUND
)
6863 cand
= data
->vcands
[i
];
6866 /* Represent uses under current candidate using other ones with
6867 lower local cost. */
6868 for (j
= 0; j
< ivs
->upto
; j
++)
6870 struct iv_group
*group
= data
->vgroups
[j
];
6871 old_cp
= iv_ca_cand_for_group (ivs
, group
);
6873 if (old_cp
->cand
!= cand
)
6877 if (data
->consider_all_candidates
)
6878 for (k
= 0; k
< data
->vcands
.length (); k
++)
6879 best_cp
= cheaper_cost_with_cand (data
, group
, k
,
6880 old_cp
->cand
, best_cp
);
6882 EXECUTE_IF_SET_IN_BITMAP (group
->related_cands
, 0, k
, bj
)
6883 best_cp
= cheaper_cost_with_cand (data
, group
, k
,
6884 old_cp
->cand
, best_cp
);
6886 if (best_cp
== old_cp
)
6889 act_delta
= iv_ca_delta_add (group
, old_cp
, best_cp
, act_delta
);
6891 /* No need for further prune. */
6895 /* Prune the new candidate set. */
6896 iv_ca_delta_commit (data
, ivs
, act_delta
, true);
6897 acost
= iv_ca_prune (data
, ivs
, NULL
, &tmp_delta
);
6898 iv_ca_delta_commit (data
, ivs
, act_delta
, false);
6899 act_delta
= iv_ca_delta_join (act_delta
, tmp_delta
);
6901 if (acost
< orig_cost
)
6907 iv_ca_delta_free (&act_delta
);
6913 /* Tries to extend the sets IVS in the best possible way in order to
6914 express the GROUP. If ORIGINALP is true, prefer candidates from
6915 the original set of IVs, otherwise favor important candidates not
6916 based on any memory object. */
6919 try_add_cand_for (struct ivopts_data
*data
, class iv_ca
*ivs
,
6920 struct iv_group
*group
, bool originalp
)
6922 comp_cost best_cost
, act_cost
;
6925 struct iv_cand
*cand
;
6926 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
;
6927 class cost_pair
*cp
;
6929 iv_ca_add_group (data
, ivs
, group
);
6930 best_cost
= iv_ca_cost (ivs
);
6931 cp
= iv_ca_cand_for_group (ivs
, group
);
6934 best_delta
= iv_ca_delta_add (group
, NULL
, cp
, NULL
);
6935 iv_ca_set_no_cp (data
, ivs
, group
);
6938 /* If ORIGINALP is true, try to find the original IV for the use. Otherwise
6939 first try important candidates not based on any memory object. Only if
6940 this fails, try the specific ones. Rationale -- in loops with many
6941 variables the best choice often is to use just one generic biv. If we
6942 added here many ivs specific to the uses, the optimization algorithm later
6943 would be likely to get stuck in a local minimum, thus causing us to create
6944 too many ivs. The approach from few ivs to more seems more likely to be
6945 successful -- starting from few ivs, replacing an expensive use by a
6946 specific iv should always be a win. */
6947 EXECUTE_IF_SET_IN_BITMAP (group
->related_cands
, 0, i
, bi
)
6949 cand
= data
->vcands
[i
];
6951 if (originalp
&& cand
->pos
!=IP_ORIGINAL
)
6954 if (!originalp
&& cand
->iv
->base_object
!= NULL_TREE
)
6957 if (iv_ca_cand_used_p (ivs
, cand
))
6960 cp
= get_group_iv_cost (data
, group
, cand
);
6964 iv_ca_set_cp (data
, ivs
, group
, cp
);
6965 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
,
6967 iv_ca_set_no_cp (data
, ivs
, group
);
6968 act_delta
= iv_ca_delta_add (group
, NULL
, cp
, act_delta
);
6970 if (act_cost
< best_cost
)
6972 best_cost
= act_cost
;
6974 iv_ca_delta_free (&best_delta
);
6975 best_delta
= act_delta
;
6978 iv_ca_delta_free (&act_delta
);
6981 if (best_cost
.infinite_cost_p ())
6983 for (i
= 0; i
< group
->n_map_members
; i
++)
6985 cp
= group
->cost_map
+ i
;
6990 /* Already tried this. */
6991 if (cand
->important
)
6993 if (originalp
&& cand
->pos
== IP_ORIGINAL
)
6995 if (!originalp
&& cand
->iv
->base_object
== NULL_TREE
)
6999 if (iv_ca_cand_used_p (ivs
, cand
))
7003 iv_ca_set_cp (data
, ivs
, group
, cp
);
7004 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
, true);
7005 iv_ca_set_no_cp (data
, ivs
, group
);
7006 act_delta
= iv_ca_delta_add (group
,
7007 iv_ca_cand_for_group (ivs
, group
),
7010 if (act_cost
< best_cost
)
7012 best_cost
= act_cost
;
7015 iv_ca_delta_free (&best_delta
);
7016 best_delta
= act_delta
;
7019 iv_ca_delta_free (&act_delta
);
7023 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
7024 iv_ca_delta_free (&best_delta
);
7026 return !best_cost
.infinite_cost_p ();
7029 /* Finds an initial assignment of candidates to uses. */
7031 static class iv_ca
*
7032 get_initial_solution (struct ivopts_data
*data
, bool originalp
)
7035 class iv_ca
*ivs
= iv_ca_new (data
);
7037 for (i
= 0; i
< data
->vgroups
.length (); i
++)
7038 if (!try_add_cand_for (data
, ivs
, data
->vgroups
[i
], originalp
))
7047 /* Tries to improve set of induction variables IVS. TRY_REPLACE_P
7048 points to a bool variable, this function tries to break local
7049 optimal fixed-point by replacing candidates in IVS if it's true. */
7052 try_improve_iv_set (struct ivopts_data
*data
,
7053 class iv_ca
*ivs
, bool *try_replace_p
)
7056 comp_cost acost
, best_cost
= iv_ca_cost (ivs
);
7057 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
, *tmp_delta
;
7058 struct iv_cand
*cand
;
7060 /* Try extending the set of induction variables by one. */
7061 for (i
= 0; i
< data
->vcands
.length (); i
++)
7063 cand
= data
->vcands
[i
];
7065 if (iv_ca_cand_used_p (ivs
, cand
))
7068 acost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, &n_ivs
, false);
7072 /* If we successfully added the candidate and the set is small enough,
7073 try optimizing it by removing other candidates. */
7074 if (n_ivs
<= ALWAYS_PRUNE_CAND_SET_BOUND
)
7076 iv_ca_delta_commit (data
, ivs
, act_delta
, true);
7077 acost
= iv_ca_prune (data
, ivs
, cand
, &tmp_delta
);
7078 iv_ca_delta_commit (data
, ivs
, act_delta
, false);
7079 act_delta
= iv_ca_delta_join (act_delta
, tmp_delta
);
7082 if (acost
< best_cost
)
7085 iv_ca_delta_free (&best_delta
);
7086 best_delta
= act_delta
;
7089 iv_ca_delta_free (&act_delta
);
7094 /* Try removing the candidates from the set instead. */
7095 best_cost
= iv_ca_prune (data
, ivs
, NULL
, &best_delta
);
7097 if (!best_delta
&& *try_replace_p
)
7099 *try_replace_p
= false;
7100 /* So far candidate selecting algorithm tends to choose fewer IVs
7101 so that it can handle cases in which loops have many variables
7102 but the best choice is often to use only one general biv. One
7103 weakness is it can't handle opposite cases, in which different
7104 candidates should be chosen with respect to each use. To solve
7105 the problem, we replace candidates in a manner described by the
7106 comments of iv_ca_replace, thus give general algorithm a chance
7107 to break local optimal fixed-point in these cases. */
7108 best_cost
= iv_ca_replace (data
, ivs
, &best_delta
);
7115 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
7116 iv_ca_delta_free (&best_delta
);
7117 return best_cost
== iv_ca_cost (ivs
);
7120 /* Attempts to find the optimal set of induction variables. We do simple
7121 greedy heuristic -- we try to replace at most one candidate in the selected
7122 solution and remove the unused ivs while this improves the cost. */
7124 static class iv_ca
*
7125 find_optimal_iv_set_1 (struct ivopts_data
*data
, bool originalp
)
7128 bool try_replace_p
= true;
7130 /* Get the initial solution. */
7131 set
= get_initial_solution (data
, originalp
);
7134 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7135 fprintf (dump_file
, "Unable to substitute for ivs, failed.\n");
7139 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7141 fprintf (dump_file
, "Initial set of candidates:\n");
7142 iv_ca_dump (data
, dump_file
, set
);
7145 while (try_improve_iv_set (data
, set
, &try_replace_p
))
7147 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7149 fprintf (dump_file
, "Improved to:\n");
7150 iv_ca_dump (data
, dump_file
, set
);
7154 /* If the set has infinite_cost, it can't be optimal. */
7155 if (iv_ca_cost (set
).infinite_cost_p ())
7157 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7159 "Overflow to infinite cost in try_improve_iv_set.\n");
7165 static class iv_ca
*
7166 find_optimal_iv_set (struct ivopts_data
*data
)
7169 comp_cost cost
, origcost
;
7170 class iv_ca
*set
, *origset
;
7172 /* Determine the cost based on a strategy that starts with original IVs,
7173 and try again using a strategy that prefers candidates not based
7175 origset
= find_optimal_iv_set_1 (data
, true);
7176 set
= find_optimal_iv_set_1 (data
, false);
7178 if (!origset
&& !set
)
7181 origcost
= origset
? iv_ca_cost (origset
) : infinite_cost
;
7182 cost
= set
? iv_ca_cost (set
) : infinite_cost
;
7184 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7186 fprintf (dump_file
, "Original cost %" PRId64
" (complexity %d)\n\n",
7187 origcost
.cost
, origcost
.complexity
);
7188 fprintf (dump_file
, "Final cost %" PRId64
" (complexity %d)\n\n",
7189 cost
.cost
, cost
.complexity
);
7192 /* Choose the one with the best cost. */
7193 if (origcost
<= cost
)
7200 iv_ca_free (&origset
);
7202 for (i
= 0; i
< data
->vgroups
.length (); i
++)
7204 struct iv_group
*group
= data
->vgroups
[i
];
7205 group
->selected
= iv_ca_cand_for_group (set
, group
)->cand
;
7211 /* Creates a new induction variable corresponding to CAND. */
7214 create_new_iv (struct ivopts_data
*data
, struct iv_cand
*cand
)
7216 gimple_stmt_iterator incr_pos
;
7219 struct iv_group
*group
;
7222 gcc_assert (cand
->iv
!= NULL
);
7227 incr_pos
= gsi_last_bb (ip_normal_pos (data
->current_loop
));
7231 incr_pos
= gsi_last_bb (ip_end_pos (data
->current_loop
));
7239 incr_pos
= gsi_for_stmt (cand
->incremented_at
);
7243 /* Mark that the iv is preserved. */
7244 name_info (data
, cand
->var_before
)->preserve_biv
= true;
7245 name_info (data
, cand
->var_after
)->preserve_biv
= true;
7247 /* Rewrite the increment so that it uses var_before directly. */
7248 use
= find_interesting_uses_op (data
, cand
->var_after
);
7249 group
= data
->vgroups
[use
->group_id
];
7250 group
->selected
= cand
;
7254 gimple_add_tmp_var (cand
->var_before
);
7256 base
= unshare_expr (cand
->iv
->base
);
7258 create_iv (base
, unshare_expr (cand
->iv
->step
),
7259 cand
->var_before
, data
->current_loop
,
7260 &incr_pos
, after
, &cand
->var_before
, &cand
->var_after
);
7263 /* Creates new induction variables described in SET. */
7266 create_new_ivs (struct ivopts_data
*data
, class iv_ca
*set
)
7269 struct iv_cand
*cand
;
7272 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
7274 cand
= data
->vcands
[i
];
7275 create_new_iv (data
, cand
);
7278 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7280 fprintf (dump_file
, "Selected IV set for loop %d",
7281 data
->current_loop
->num
);
7282 if (data
->loop_loc
!= UNKNOWN_LOCATION
)
7283 fprintf (dump_file
, " at %s:%d", LOCATION_FILE (data
->loop_loc
),
7284 LOCATION_LINE (data
->loop_loc
));
7285 fprintf (dump_file
, ", " HOST_WIDE_INT_PRINT_DEC
" avg niters",
7286 avg_loop_niter (data
->current_loop
));
7287 fprintf (dump_file
, ", %lu IVs:\n", bitmap_count_bits (set
->cands
));
7288 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
7290 cand
= data
->vcands
[i
];
7291 dump_cand (dump_file
, cand
);
7293 fprintf (dump_file
, "\n");
7297 /* Rewrites USE (definition of iv used in a nonlinear expression)
7298 using candidate CAND. */
7301 rewrite_use_nonlinear_expr (struct ivopts_data
*data
,
7302 struct iv_use
*use
, struct iv_cand
*cand
)
7305 gimple_stmt_iterator bsi
;
7306 tree comp
, type
= get_use_type (use
), tgt
;
7308 /* An important special case -- if we are asked to express value of
7309 the original iv by itself, just exit; there is no need to
7310 introduce a new computation (that might also need casting the
7311 variable to unsigned and back). */
7312 if (cand
->pos
== IP_ORIGINAL
7313 && cand
->incremented_at
== use
->stmt
)
7315 tree op
= NULL_TREE
;
7316 enum tree_code stmt_code
;
7318 gcc_assert (is_gimple_assign (use
->stmt
));
7319 gcc_assert (gimple_assign_lhs (use
->stmt
) == cand
->var_after
);
7321 /* Check whether we may leave the computation unchanged.
7322 This is the case only if it does not rely on other
7323 computations in the loop -- otherwise, the computation
7324 we rely upon may be removed in remove_unused_ivs,
7325 thus leading to ICE. */
7326 stmt_code
= gimple_assign_rhs_code (use
->stmt
);
7327 if (stmt_code
== PLUS_EXPR
7328 || stmt_code
== MINUS_EXPR
7329 || stmt_code
== POINTER_PLUS_EXPR
)
7331 if (gimple_assign_rhs1 (use
->stmt
) == cand
->var_before
)
7332 op
= gimple_assign_rhs2 (use
->stmt
);
7333 else if (gimple_assign_rhs2 (use
->stmt
) == cand
->var_before
)
7334 op
= gimple_assign_rhs1 (use
->stmt
);
7337 if (op
!= NULL_TREE
)
7339 if (expr_invariant_in_loop_p (data
->current_loop
, op
))
7341 if (TREE_CODE (op
) == SSA_NAME
)
7343 struct iv
*iv
= get_iv (data
, op
);
7344 if (iv
!= NULL
&& integer_zerop (iv
->step
))
7350 switch (gimple_code (use
->stmt
))
7353 tgt
= PHI_RESULT (use
->stmt
);
7355 /* If we should keep the biv, do not replace it. */
7356 if (name_info (data
, tgt
)->preserve_biv
)
7359 bsi
= gsi_after_labels (gimple_bb (use
->stmt
));
7363 tgt
= gimple_assign_lhs (use
->stmt
);
7364 bsi
= gsi_for_stmt (use
->stmt
);
7371 aff_tree aff_inv
, aff_var
;
7372 if (!get_computation_aff_1 (data
->current_loop
, use
->stmt
,
7373 use
, cand
, &aff_inv
, &aff_var
))
7376 unshare_aff_combination (&aff_inv
);
7377 unshare_aff_combination (&aff_var
);
7378 /* Prefer CSE opportunity than loop invariant by adding offset at last
7379 so that iv_uses have different offsets can be CSEed. */
7380 poly_widest_int offset
= aff_inv
.offset
;
7383 gimple_seq stmt_list
= NULL
, seq
= NULL
;
7384 tree comp_op1
= aff_combination_to_tree (&aff_inv
);
7385 tree comp_op2
= aff_combination_to_tree (&aff_var
);
7386 gcc_assert (comp_op1
&& comp_op2
);
7388 comp_op1
= force_gimple_operand (comp_op1
, &seq
, true, NULL
);
7389 gimple_seq_add_seq (&stmt_list
, seq
);
7390 comp_op2
= force_gimple_operand (comp_op2
, &seq
, true, NULL
);
7391 gimple_seq_add_seq (&stmt_list
, seq
);
7393 if (POINTER_TYPE_P (TREE_TYPE (comp_op2
)))
7394 std::swap (comp_op1
, comp_op2
);
7396 if (POINTER_TYPE_P (TREE_TYPE (comp_op1
)))
7398 comp
= fold_build_pointer_plus (comp_op1
,
7399 fold_convert (sizetype
, comp_op2
));
7400 comp
= fold_build_pointer_plus (comp
,
7401 wide_int_to_tree (sizetype
, offset
));
7405 comp
= fold_build2 (PLUS_EXPR
, TREE_TYPE (comp_op1
), comp_op1
,
7406 fold_convert (TREE_TYPE (comp_op1
), comp_op2
));
7407 comp
= fold_build2 (PLUS_EXPR
, TREE_TYPE (comp_op1
), comp
,
7408 wide_int_to_tree (TREE_TYPE (comp_op1
), offset
));
7411 comp
= fold_convert (type
, comp
);
7412 comp
= force_gimple_operand (comp
, &seq
, false, NULL
);
7413 gimple_seq_add_seq (&stmt_list
, seq
);
7414 if (gimple_code (use
->stmt
) != GIMPLE_PHI
7415 /* We can't allow re-allocating the stmt as it might be pointed
7417 && (get_gimple_rhs_num_ops (TREE_CODE (comp
))
7418 >= gimple_num_ops (gsi_stmt (bsi
))))
7420 comp
= force_gimple_operand (comp
, &seq
, true, NULL
);
7421 gimple_seq_add_seq (&stmt_list
, seq
);
7422 if (POINTER_TYPE_P (TREE_TYPE (tgt
)))
7424 duplicate_ssa_name_ptr_info (comp
, SSA_NAME_PTR_INFO (tgt
));
7425 /* As this isn't a plain copy we have to reset alignment
7427 if (SSA_NAME_PTR_INFO (comp
))
7428 mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (comp
));
7432 gsi_insert_seq_before (&bsi
, stmt_list
, GSI_SAME_STMT
);
7433 if (gimple_code (use
->stmt
) == GIMPLE_PHI
)
7435 ass
= gimple_build_assign (tgt
, comp
);
7436 gsi_insert_before (&bsi
, ass
, GSI_SAME_STMT
);
7438 bsi
= gsi_for_stmt (use
->stmt
);
7439 remove_phi_node (&bsi
, false);
7443 gimple_assign_set_rhs_from_tree (&bsi
, comp
);
7444 use
->stmt
= gsi_stmt (bsi
);
7448 /* Performs a peephole optimization to reorder the iv update statement with
7449 a mem ref to enable instruction combining in later phases. The mem ref uses
7450 the iv value before the update, so the reordering transformation requires
7451 adjustment of the offset. CAND is the selected IV_CAND.
7455 t = MEM_REF (base, iv1, 8, 16); // base, index, stride, offset
7463 directly propagating t over to (1) will introduce overlapping live range
7464 thus increase register pressure. This peephole transform it into:
7468 t = MEM_REF (base, iv2, 8, 8);
7475 adjust_iv_update_pos (struct iv_cand
*cand
, struct iv_use
*use
)
7478 gimple
*iv_update
, *stmt
;
7480 gimple_stmt_iterator gsi
, gsi_iv
;
7482 if (cand
->pos
!= IP_NORMAL
)
7485 var_after
= cand
->var_after
;
7486 iv_update
= SSA_NAME_DEF_STMT (var_after
);
7488 bb
= gimple_bb (iv_update
);
7489 gsi
= gsi_last_nondebug_bb (bb
);
7490 stmt
= gsi_stmt (gsi
);
7492 /* Only handle conditional statement for now. */
7493 if (gimple_code (stmt
) != GIMPLE_COND
)
7496 gsi_prev_nondebug (&gsi
);
7497 stmt
= gsi_stmt (gsi
);
7498 if (stmt
!= iv_update
)
7501 gsi_prev_nondebug (&gsi
);
7502 if (gsi_end_p (gsi
))
7505 stmt
= gsi_stmt (gsi
);
7506 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
7509 if (stmt
!= use
->stmt
)
7512 if (TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
7515 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7517 fprintf (dump_file
, "Reordering \n");
7518 print_gimple_stmt (dump_file
, iv_update
, 0);
7519 print_gimple_stmt (dump_file
, use
->stmt
, 0);
7520 fprintf (dump_file
, "\n");
7523 gsi
= gsi_for_stmt (use
->stmt
);
7524 gsi_iv
= gsi_for_stmt (iv_update
);
7525 gsi_move_before (&gsi_iv
, &gsi
);
7527 cand
->pos
= IP_BEFORE_USE
;
7528 cand
->incremented_at
= use
->stmt
;
7531 /* Return the alias pointer type that should be used for a MEM_REF
7532 associated with USE, which has type USE_PTR_ADDRESS. */
7535 get_alias_ptr_type_for_ptr_address (iv_use
*use
)
7537 gcall
*call
= as_a
<gcall
*> (use
->stmt
);
7538 switch (gimple_call_internal_fn (call
))
7541 case IFN_MASK_STORE
:
7542 case IFN_MASK_LOAD_LANES
:
7543 case IFN_MASK_STORE_LANES
:
7546 /* The second argument contains the correct alias type. */
7547 gcc_assert (use
->op_p
= gimple_call_arg_ptr (call
, 0));
7548 return TREE_TYPE (gimple_call_arg (call
, 1));
7556 /* Rewrites USE (address that is an iv) using candidate CAND. */
7559 rewrite_use_address (struct ivopts_data
*data
,
7560 struct iv_use
*use
, struct iv_cand
*cand
)
7565 adjust_iv_update_pos (cand
, use
);
7566 ok
= get_computation_aff (data
->current_loop
, use
->stmt
, use
, cand
, &aff
);
7568 unshare_aff_combination (&aff
);
7570 /* To avoid undefined overflow problems, all IV candidates use unsigned
7571 integer types. The drawback is that this makes it impossible for
7572 create_mem_ref to distinguish an IV that is based on a memory object
7573 from one that represents simply an offset.
7575 To work around this problem, we pass a hint to create_mem_ref that
7576 indicates which variable (if any) in aff is an IV based on a memory
7577 object. Note that we only consider the candidate. If this is not
7578 based on an object, the base of the reference is in some subexpression
7579 of the use -- but these will use pointer types, so they are recognized
7580 by the create_mem_ref heuristics anyway. */
7581 tree iv
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
7582 tree base_hint
= (cand
->iv
->base_object
) ? iv
: NULL_TREE
;
7583 gimple_stmt_iterator bsi
= gsi_for_stmt (use
->stmt
);
7584 tree type
= use
->mem_type
;
7585 tree alias_ptr_type
;
7586 if (use
->type
== USE_PTR_ADDRESS
)
7587 alias_ptr_type
= get_alias_ptr_type_for_ptr_address (use
);
7590 gcc_assert (type
== TREE_TYPE (*use
->op_p
));
7591 unsigned int align
= get_object_alignment (*use
->op_p
);
7592 if (align
!= TYPE_ALIGN (type
))
7593 type
= build_aligned_type (type
, align
);
7594 alias_ptr_type
= reference_alias_ptr_type (*use
->op_p
);
7596 tree ref
= create_mem_ref (&bsi
, type
, &aff
, alias_ptr_type
,
7597 iv
, base_hint
, data
->speed
);
7599 if (use
->type
== USE_PTR_ADDRESS
)
7601 ref
= fold_build1 (ADDR_EXPR
, build_pointer_type (use
->mem_type
), ref
);
7602 ref
= fold_convert (get_use_type (use
), ref
);
7603 ref
= force_gimple_operand_gsi (&bsi
, ref
, true, NULL_TREE
,
7604 true, GSI_SAME_STMT
);
7607 copy_ref_info (ref
, *use
->op_p
);
7612 /* Rewrites USE (the condition such that one of the arguments is an iv) using
7616 rewrite_use_compare (struct ivopts_data
*data
,
7617 struct iv_use
*use
, struct iv_cand
*cand
)
7619 tree comp
, op
, bound
;
7620 gimple_stmt_iterator bsi
= gsi_for_stmt (use
->stmt
);
7621 enum tree_code compare
;
7622 struct iv_group
*group
= data
->vgroups
[use
->group_id
];
7623 class cost_pair
*cp
= get_group_iv_cost (data
, group
, cand
);
7628 tree var
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
7629 tree var_type
= TREE_TYPE (var
);
7632 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7634 fprintf (dump_file
, "Replacing exit test: ");
7635 print_gimple_stmt (dump_file
, use
->stmt
, 0, TDF_SLIM
);
7638 bound
= unshare_expr (fold_convert (var_type
, bound
));
7639 op
= force_gimple_operand (bound
, &stmts
, true, NULL_TREE
);
7641 gsi_insert_seq_on_edge_immediate (
7642 loop_preheader_edge (data
->current_loop
),
7645 gcond
*cond_stmt
= as_a
<gcond
*> (use
->stmt
);
7646 gimple_cond_set_lhs (cond_stmt
, var
);
7647 gimple_cond_set_code (cond_stmt
, compare
);
7648 gimple_cond_set_rhs (cond_stmt
, op
);
7652 /* The induction variable elimination failed; just express the original
7654 comp
= get_computation_at (data
->current_loop
, use
->stmt
, use
, cand
);
7655 gcc_assert (comp
!= NULL_TREE
);
7656 gcc_assert (use
->op_p
!= NULL
);
7657 *use
->op_p
= force_gimple_operand_gsi (&bsi
, comp
, true,
7658 SSA_NAME_VAR (*use
->op_p
),
7659 true, GSI_SAME_STMT
);
7662 /* Rewrite the groups using the selected induction variables. */
7665 rewrite_groups (struct ivopts_data
*data
)
7669 for (i
= 0; i
< data
->vgroups
.length (); i
++)
7671 struct iv_group
*group
= data
->vgroups
[i
];
7672 struct iv_cand
*cand
= group
->selected
;
7676 if (group
->type
== USE_NONLINEAR_EXPR
)
7678 for (j
= 0; j
< group
->vuses
.length (); j
++)
7680 rewrite_use_nonlinear_expr (data
, group
->vuses
[j
], cand
);
7681 update_stmt (group
->vuses
[j
]->stmt
);
7684 else if (address_p (group
->type
))
7686 for (j
= 0; j
< group
->vuses
.length (); j
++)
7688 rewrite_use_address (data
, group
->vuses
[j
], cand
);
7689 update_stmt (group
->vuses
[j
]->stmt
);
7694 gcc_assert (group
->type
== USE_COMPARE
);
7696 for (j
= 0; j
< group
->vuses
.length (); j
++)
7698 rewrite_use_compare (data
, group
->vuses
[j
], cand
);
7699 update_stmt (group
->vuses
[j
]->stmt
);
7705 /* Removes the ivs that are not used after rewriting. */
7708 remove_unused_ivs (struct ivopts_data
*data
, bitmap toremove
)
7713 /* Figure out an order in which to release SSA DEFs so that we don't
7714 release something that we'd have to propagate into a debug stmt
7716 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
7718 struct version_info
*info
;
7720 info
= ver_info (data
, j
);
7722 && !integer_zerop (info
->iv
->step
)
7724 && !info
->iv
->nonlin_use
7725 && !info
->preserve_biv
)
7727 bitmap_set_bit (toremove
, SSA_NAME_VERSION (info
->iv
->ssa_name
));
7729 tree def
= info
->iv
->ssa_name
;
7731 if (MAY_HAVE_DEBUG_BIND_STMTS
&& SSA_NAME_DEF_STMT (def
))
7733 imm_use_iterator imm_iter
;
7734 use_operand_p use_p
;
7738 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, def
)
7740 if (!gimple_debug_bind_p (stmt
))
7743 /* We just want to determine whether to do nothing
7744 (count == 0), to substitute the computed
7745 expression into a single use of the SSA DEF by
7746 itself (count == 1), or to use a debug temp
7747 because the SSA DEF is used multiple times or as
7748 part of a larger expression (count > 1). */
7750 if (gimple_debug_bind_get_value (stmt
) != def
)
7760 struct iv_use dummy_use
;
7761 struct iv_cand
*best_cand
= NULL
, *cand
;
7762 unsigned i
, best_pref
= 0, cand_pref
;
7763 tree comp
= NULL_TREE
;
7765 memset (&dummy_use
, 0, sizeof (dummy_use
));
7766 dummy_use
.iv
= info
->iv
;
7767 for (i
= 0; i
< data
->vgroups
.length () && i
< 64; i
++)
7769 cand
= data
->vgroups
[i
]->selected
;
7770 if (cand
== best_cand
)
7772 cand_pref
= operand_equal_p (cand
->iv
->step
,
7776 += TYPE_MODE (TREE_TYPE (cand
->iv
->base
))
7777 == TYPE_MODE (TREE_TYPE (info
->iv
->base
))
7780 += TREE_CODE (cand
->iv
->base
) == INTEGER_CST
7782 if (best_cand
== NULL
|| best_pref
< cand_pref
)
7785 = get_debug_computation_at (data
->current_loop
,
7786 SSA_NAME_DEF_STMT (def
),
7791 best_pref
= cand_pref
;
7800 comp
= unshare_expr (comp
);
7803 tree vexpr
= build_debug_expr_decl (TREE_TYPE (comp
));
7804 /* FIXME: Is setting the mode really necessary? */
7805 if (SSA_NAME_VAR (def
))
7806 SET_DECL_MODE (vexpr
, DECL_MODE (SSA_NAME_VAR (def
)));
7808 SET_DECL_MODE (vexpr
, TYPE_MODE (TREE_TYPE (vexpr
)));
7810 = gimple_build_debug_bind (vexpr
, comp
, NULL
);
7811 gimple_stmt_iterator gsi
;
7813 if (gimple_code (SSA_NAME_DEF_STMT (def
)) == GIMPLE_PHI
)
7814 gsi
= gsi_after_labels (gimple_bb
7815 (SSA_NAME_DEF_STMT (def
)));
7817 gsi
= gsi_for_stmt (SSA_NAME_DEF_STMT (def
));
7819 gsi_insert_before (&gsi
, def_temp
, GSI_SAME_STMT
);
7823 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, def
)
7825 if (!gimple_debug_bind_p (stmt
))
7828 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
7829 SET_USE (use_p
, comp
);
7838 /* Frees memory occupied by class tree_niter_desc in *VALUE. Callback
7839 for hash_map::traverse. */
7842 free_tree_niter_desc (edge
const &, tree_niter_desc
*const &value
, void *)
7848 /* Frees data allocated by the optimization of a single loop. */
7851 free_loop_data (struct ivopts_data
*data
)
7859 data
->niters
->traverse
<void *, free_tree_niter_desc
> (NULL
);
7860 delete data
->niters
;
7861 data
->niters
= NULL
;
7864 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
7866 struct version_info
*info
;
7868 info
= ver_info (data
, i
);
7870 info
->has_nonlin_use
= false;
7871 info
->preserve_biv
= false;
7874 bitmap_clear (data
->relevant
);
7875 bitmap_clear (data
->important_candidates
);
7877 for (i
= 0; i
< data
->vgroups
.length (); i
++)
7879 struct iv_group
*group
= data
->vgroups
[i
];
7881 for (j
= 0; j
< group
->vuses
.length (); j
++)
7882 free (group
->vuses
[j
]);
7883 group
->vuses
.release ();
7885 BITMAP_FREE (group
->related_cands
);
7886 for (j
= 0; j
< group
->n_map_members
; j
++)
7888 if (group
->cost_map
[j
].inv_vars
)
7889 BITMAP_FREE (group
->cost_map
[j
].inv_vars
);
7890 if (group
->cost_map
[j
].inv_exprs
)
7891 BITMAP_FREE (group
->cost_map
[j
].inv_exprs
);
7894 free (group
->cost_map
);
7897 data
->vgroups
.truncate (0);
7899 for (i
= 0; i
< data
->vcands
.length (); i
++)
7901 struct iv_cand
*cand
= data
->vcands
[i
];
7904 BITMAP_FREE (cand
->inv_vars
);
7905 if (cand
->inv_exprs
)
7906 BITMAP_FREE (cand
->inv_exprs
);
7909 data
->vcands
.truncate (0);
7911 if (data
->version_info_size
< num_ssa_names
)
7913 data
->version_info_size
= 2 * num_ssa_names
;
7914 free (data
->version_info
);
7915 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
7918 data
->max_inv_var_id
= 0;
7919 data
->max_inv_expr_id
= 0;
7921 FOR_EACH_VEC_ELT (decl_rtl_to_reset
, i
, obj
)
7922 SET_DECL_RTL (obj
, NULL_RTX
);
7924 decl_rtl_to_reset
.truncate (0);
7926 data
->inv_expr_tab
->empty ();
7928 data
->iv_common_cand_tab
->empty ();
7929 data
->iv_common_cands
.truncate (0);
7932 /* Finalizes data structures used by the iv optimization pass. LOOPS is the
7936 tree_ssa_iv_optimize_finalize (struct ivopts_data
*data
)
7938 free_loop_data (data
);
7939 free (data
->version_info
);
7940 BITMAP_FREE (data
->relevant
);
7941 BITMAP_FREE (data
->important_candidates
);
7943 decl_rtl_to_reset
.release ();
7944 data
->vgroups
.release ();
7945 data
->vcands
.release ();
7946 delete data
->inv_expr_tab
;
7947 data
->inv_expr_tab
= NULL
;
7948 free_affine_expand_cache (&data
->name_expansion_cache
);
7949 if (data
->base_object_map
)
7950 delete data
->base_object_map
;
7951 delete data
->iv_common_cand_tab
;
7952 data
->iv_common_cand_tab
= NULL
;
7953 data
->iv_common_cands
.release ();
7954 obstack_free (&data
->iv_obstack
, NULL
);
7957 /* Returns true if the loop body BODY includes any function calls. */
7960 loop_body_includes_call (basic_block
*body
, unsigned num_nodes
)
7962 gimple_stmt_iterator gsi
;
7965 for (i
= 0; i
< num_nodes
; i
++)
7966 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
7968 gimple
*stmt
= gsi_stmt (gsi
);
7969 if (is_gimple_call (stmt
)
7970 && !gimple_call_internal_p (stmt
)
7971 && !is_inexpensive_builtin (gimple_call_fndecl (stmt
)))
7977 /* Determine cost scaling factor for basic blocks in loop. */
7978 #define COST_SCALING_FACTOR_BOUND (20)
7981 determine_scaling_factor (struct ivopts_data
*data
, basic_block
*body
)
7983 int lfreq
= data
->current_loop
->header
->count
.to_frequency (cfun
);
7984 if (!data
->speed
|| lfreq
<= 0)
7987 int max_freq
= lfreq
;
7988 for (unsigned i
= 0; i
< data
->current_loop
->num_nodes
; i
++)
7990 body
[i
]->aux
= (void *)(intptr_t) 1;
7991 if (max_freq
< body
[i
]->count
.to_frequency (cfun
))
7992 max_freq
= body
[i
]->count
.to_frequency (cfun
);
7994 if (max_freq
> lfreq
)
7996 int divisor
, factor
;
7997 /* Check if scaling factor itself needs to be scaled by the bound. This
7998 is to avoid overflow when scaling cost according to profile info. */
7999 if (max_freq
/ lfreq
> COST_SCALING_FACTOR_BOUND
)
8002 factor
= COST_SCALING_FACTOR_BOUND
;
8009 for (unsigned i
= 0; i
< data
->current_loop
->num_nodes
; i
++)
8011 int bfreq
= body
[i
]->count
.to_frequency (cfun
);
8015 body
[i
]->aux
= (void*)(intptr_t) (factor
* bfreq
/ divisor
);
8020 /* Find doloop comparison use and set its doloop_p on if found. */
8023 find_doloop_use (struct ivopts_data
*data
)
8025 struct loop
*loop
= data
->current_loop
;
8027 for (unsigned i
= 0; i
< data
->vgroups
.length (); i
++)
8029 struct iv_group
*group
= data
->vgroups
[i
];
8030 if (group
->type
== USE_COMPARE
)
8032 gcc_assert (group
->vuses
.length () == 1);
8033 struct iv_use
*use
= group
->vuses
[0];
8034 gimple
*stmt
= use
->stmt
;
8035 if (gimple_code (stmt
) == GIMPLE_COND
)
8037 basic_block bb
= gimple_bb (stmt
);
8038 edge true_edge
, false_edge
;
8039 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
8040 /* This comparison is used for loop latch. Require latch is empty
8042 if ((loop
->latch
== true_edge
->dest
8043 || loop
->latch
== false_edge
->dest
)
8044 && empty_block_p (loop
->latch
))
8046 group
->doloop_p
= true;
8047 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
8049 fprintf (dump_file
, "Doloop cmp iv use: ");
8050 print_gimple_stmt (dump_file
, stmt
, TDF_DETAILS
);
8061 /* For the targets which support doloop, to predict whether later RTL doloop
8062 transformation will perform on this loop, further detect the doloop use and
8063 mark the flag doloop_use_p if predicted. */
8066 analyze_and_mark_doloop_use (struct ivopts_data
*data
)
8068 data
->doloop_use_p
= false;
8070 if (!flag_branch_on_count_reg
)
8073 if (data
->current_loop
->unroll
== USHRT_MAX
)
8076 if (!generic_predict_doloop_p (data
))
8079 if (find_doloop_use (data
))
8081 data
->doloop_use_p
= true;
8082 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
8084 struct loop
*loop
= data
->current_loop
;
8086 "Predict loop %d can perform"
8087 " doloop optimization later.\n",
8089 flow_loop_dump (loop
, dump_file
, NULL
, 1);
8094 /* Optimizes the LOOP. Returns true if anything changed. */
8097 tree_ssa_iv_optimize_loop (struct ivopts_data
*data
, class loop
*loop
,
8100 bool changed
= false;
8102 edge exit
= single_dom_exit (loop
);
8105 gcc_assert (!data
->niters
);
8106 data
->current_loop
= loop
;
8107 data
->loop_loc
= find_loop_location (loop
).get_location_t ();
8108 data
->speed
= optimize_loop_for_speed_p (loop
);
8110 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
8112 fprintf (dump_file
, "Processing loop %d", loop
->num
);
8113 if (data
->loop_loc
!= UNKNOWN_LOCATION
)
8114 fprintf (dump_file
, " at %s:%d", LOCATION_FILE (data
->loop_loc
),
8115 LOCATION_LINE (data
->loop_loc
));
8116 fprintf (dump_file
, "\n");
8120 fprintf (dump_file
, " single exit %d -> %d, exit condition ",
8121 exit
->src
->index
, exit
->dest
->index
);
8122 print_gimple_stmt (dump_file
, last_stmt (exit
->src
), 0, TDF_SLIM
);
8123 fprintf (dump_file
, "\n");
8126 fprintf (dump_file
, "\n");
8129 body
= get_loop_body (loop
);
8130 data
->body_includes_call
= loop_body_includes_call (body
, loop
->num_nodes
);
8131 renumber_gimple_stmt_uids_in_blocks (body
, loop
->num_nodes
);
8133 data
->loop_single_exit_p
8134 = exit
!= NULL
&& loop_only_exit_p (loop
, body
, exit
);
8136 /* For each ssa name determines whether it behaves as an induction variable
8138 if (!find_induction_variables (data
, body
))
8141 /* Finds interesting uses (item 1). */
8142 find_interesting_uses (data
, body
);
8143 if (data
->vgroups
.length () > MAX_CONSIDERED_GROUPS
)
8146 /* Determine cost scaling factor for basic blocks in loop. */
8147 determine_scaling_factor (data
, body
);
8149 /* Analyze doloop possibility and mark the doloop use if predicted. */
8150 analyze_and_mark_doloop_use (data
);
8152 /* Finds candidates for the induction variables (item 2). */
8153 find_iv_candidates (data
);
8155 /* Calculates the costs (item 3, part 1). */
8156 determine_iv_costs (data
);
8157 determine_group_iv_costs (data
);
8158 determine_set_costs (data
);
8160 /* Find the optimal set of induction variables (item 3, part 2). */
8161 iv_ca
= find_optimal_iv_set (data
);
8162 /* Cleanup basic block aux field. */
8163 for (unsigned i
= 0; i
< data
->current_loop
->num_nodes
; i
++)
8164 body
[i
]->aux
= NULL
;
8169 /* Create the new induction variables (item 4, part 1). */
8170 create_new_ivs (data
, iv_ca
);
8171 iv_ca_free (&iv_ca
);
8173 /* Rewrite the uses (item 4, part 2). */
8174 rewrite_groups (data
);
8176 /* Remove the ivs that are unused after rewriting. */
8177 remove_unused_ivs (data
, toremove
);
8181 free_loop_data (data
);
8186 /* Main entry point. Optimizes induction variables in loops. */
8189 tree_ssa_iv_optimize (void)
8191 struct ivopts_data data
;
8192 auto_bitmap toremove
;
8194 tree_ssa_iv_optimize_init (&data
);
8196 /* Optimize the loops starting with the innermost ones. */
8197 for (auto loop
: loops_list (cfun
, LI_FROM_INNERMOST
))
8199 if (!dbg_cnt (ivopts_loop
))
8202 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
8203 flow_loop_dump (loop
, dump_file
, NULL
, 1);
8205 tree_ssa_iv_optimize_loop (&data
, loop
, toremove
);
8208 /* Remove eliminated IV defs. */
8209 release_defs_bitset (toremove
);
8211 /* We have changed the structure of induction variables; it might happen
8212 that definitions in the scev database refer to some of them that were
8215 /* Likewise niter and control-IV information. */
8216 free_numbers_of_iterations_estimates (cfun
);
8218 tree_ssa_iv_optimize_finalize (&data
);
8221 #include "gt-tree-ssa-loop-ivopts.h"