1 /* Induction variable optimizations.
2 Copyright (C) 2003-2016 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
67 would be complicated. */
71 #include "coretypes.h"
77 #include "tree-pass.h"
81 #include "insn-config.h"
85 #include "gimple-pretty-print.h"
87 #include "fold-const.h"
88 #include "stor-layout.h"
91 #include "gimple-iterator.h"
92 #include "gimplify-me.h"
94 #include "tree-ssa-loop-ivopts.h"
95 #include "tree-ssa-loop-manip.h"
96 #include "tree-ssa-loop-niter.h"
97 #include "tree-ssa-loop.h"
100 #include "tree-dfa.h"
101 #include "tree-ssa.h"
103 #include "tree-scalar-evolution.h"
105 #include "tree-affine.h"
106 #include "tree-ssa-propagate.h"
107 #include "tree-ssa-address.h"
108 #include "builtins.h"
109 #include "tree-vectorizer.h"
111 /* FIXME: Expressions are expanded to RTL in this pass to determine the
112 cost of different addressing modes. This should be moved to a TBD
113 interface between the GIMPLE and RTL worlds. */
115 /* The infinite cost. */
116 #define INFTY 10000000
118 #define AVG_LOOP_NITER(LOOP) 5
120 /* Returns the expected number of loop iterations for LOOP.
121 The average trip count is computed from profile data if it
124 static inline HOST_WIDE_INT
125 avg_loop_niter (struct loop
*loop
)
127 HOST_WIDE_INT niter
= estimated_stmt_executions_int (loop
);
130 niter
= likely_max_stmt_executions_int (loop
);
131 if (niter
== -1 || niter
> AVG_LOOP_NITER (loop
))
132 return AVG_LOOP_NITER (loop
);
140 /* Representation of the induction variable. */
143 tree base
; /* Initial value of the iv. */
144 tree base_object
; /* A memory object to that the induction variable points. */
145 tree step
; /* Step of the iv (constant only). */
146 tree ssa_name
; /* The ssa name with the value. */
147 struct iv_use
*nonlin_use
; /* The identifier in the use if it is the case. */
148 bool biv_p
; /* Is it a biv? */
149 bool no_overflow
; /* True if the iv doesn't overflow. */
150 bool have_address_use
;/* For biv, indicate if it's used in any address
154 /* Per-ssa version information (induction variable descriptions, etc.). */
157 tree name
; /* The ssa name. */
158 struct iv
*iv
; /* Induction variable description. */
159 bool has_nonlin_use
; /* For a loop-level invariant, whether it is used in
160 an expression that is not an induction variable. */
161 bool preserve_biv
; /* For the original biv, whether to preserve it. */
162 unsigned inv_id
; /* Id of an invariant. */
168 USE_NONLINEAR_EXPR
, /* Use in a nonlinear expression. */
169 USE_ADDRESS
, /* Use in an address. */
170 USE_COMPARE
/* Use is a compare. */
173 /* Cost of a computation. */
176 comp_cost (): cost (0), complexity (0), scratch (0)
179 comp_cost (int cost
, unsigned complexity
, int scratch
= 0)
180 : cost (cost
), complexity (complexity
), scratch (scratch
)
183 /* Returns true if COST is infinite. */
184 bool infinite_cost_p ();
186 /* Adds costs COST1 and COST2. */
187 friend comp_cost
operator+ (comp_cost cost1
, comp_cost cost2
);
189 /* Adds COST to the comp_cost. */
190 comp_cost
operator+= (comp_cost cost
);
192 /* Adds constant C to this comp_cost. */
193 comp_cost
operator+= (HOST_WIDE_INT c
);
195 /* Subtracts constant C to this comp_cost. */
196 comp_cost
operator-= (HOST_WIDE_INT c
);
198 /* Divide the comp_cost by constant C. */
199 comp_cost
operator/= (HOST_WIDE_INT c
);
201 /* Multiply the comp_cost by constant C. */
202 comp_cost
operator*= (HOST_WIDE_INT c
);
204 /* Subtracts costs COST1 and COST2. */
205 friend comp_cost
operator- (comp_cost cost1
, comp_cost cost2
);
207 /* Subtracts COST from this comp_cost. */
208 comp_cost
operator-= (comp_cost cost
);
210 /* Returns true if COST1 is smaller than COST2. */
211 friend bool operator< (comp_cost cost1
, comp_cost cost2
);
213 /* Returns true if COST1 and COST2 are equal. */
214 friend bool operator== (comp_cost cost1
, comp_cost cost2
);
216 /* Returns true if COST1 is smaller or equal than COST2. */
217 friend bool operator<= (comp_cost cost1
, comp_cost cost2
);
219 int cost
; /* The runtime cost. */
220 unsigned complexity
; /* The estimate of the complexity of the code for
221 the computation (in no concrete units --
222 complexity field should be larger for more
223 complex expressions and addressing modes). */
224 int scratch
; /* Scratch used during cost computation. */
227 static const comp_cost no_cost
;
228 static const comp_cost
infinite_cost (INFTY
, INFTY
, INFTY
);
231 comp_cost::infinite_cost_p ()
233 return cost
== INFTY
;
237 operator+ (comp_cost cost1
, comp_cost cost2
)
239 if (cost1
.infinite_cost_p () || cost2
.infinite_cost_p ())
240 return infinite_cost
;
242 cost1
.cost
+= cost2
.cost
;
243 cost1
.complexity
+= cost2
.complexity
;
249 operator- (comp_cost cost1
, comp_cost cost2
)
251 if (cost1
.infinite_cost_p ())
252 return infinite_cost
;
254 gcc_assert (!cost2
.infinite_cost_p ());
256 cost1
.cost
-= cost2
.cost
;
257 cost1
.complexity
-= cost2
.complexity
;
263 comp_cost::operator+= (comp_cost cost
)
265 *this = *this + cost
;
270 comp_cost::operator+= (HOST_WIDE_INT c
)
272 if (infinite_cost_p ())
281 comp_cost::operator-= (HOST_WIDE_INT c
)
283 if (infinite_cost_p ())
292 comp_cost::operator/= (HOST_WIDE_INT c
)
294 if (infinite_cost_p ())
303 comp_cost::operator*= (HOST_WIDE_INT c
)
305 if (infinite_cost_p ())
314 comp_cost::operator-= (comp_cost cost
)
316 *this = *this - cost
;
321 operator< (comp_cost cost1
, comp_cost cost2
)
323 if (cost1
.cost
== cost2
.cost
)
324 return cost1
.complexity
< cost2
.complexity
;
326 return cost1
.cost
< cost2
.cost
;
330 operator== (comp_cost cost1
, comp_cost cost2
)
332 return cost1
.cost
== cost2
.cost
333 && cost1
.complexity
== cost2
.complexity
;
337 operator<= (comp_cost cost1
, comp_cost cost2
)
339 return cost1
< cost2
|| cost1
== cost2
;
342 struct iv_inv_expr_ent
;
344 /* The candidate - cost pair. */
347 struct iv_cand
*cand
; /* The candidate. */
348 comp_cost cost
; /* The cost. */
349 bitmap depends_on
; /* The list of invariants that have to be
351 tree value
; /* For final value elimination, the expression for
352 the final value of the iv. For iv elimination,
353 the new bound to compare with. */
354 enum tree_code comp
; /* For iv elimination, the comparison. */
355 iv_inv_expr_ent
*inv_expr
; /* Loop invariant expression. */
361 unsigned id
; /* The id of the use. */
362 unsigned group_id
; /* The group id the use belongs to. */
363 enum use_type type
; /* Type of the use. */
364 struct iv
*iv
; /* The induction variable it is based on. */
365 gimple
*stmt
; /* Statement in that it occurs. */
366 tree
*op_p
; /* The place where it occurs. */
368 tree addr_base
; /* Base address with const offset stripped. */
369 unsigned HOST_WIDE_INT addr_offset
;
370 /* Const offset stripped from base address. */
376 /* The id of the group. */
378 /* Uses of the group are of the same type. */
380 /* The set of "related" IV candidates, plus the important ones. */
381 bitmap related_cands
;
382 /* Number of IV candidates in the cost_map. */
383 unsigned n_map_members
;
384 /* The costs wrto the iv candidates. */
385 struct cost_pair
*cost_map
;
386 /* The selected candidate for the group. */
387 struct iv_cand
*selected
;
388 /* Uses in the group. */
389 vec
<struct iv_use
*> vuses
;
392 /* The position where the iv is computed. */
395 IP_NORMAL
, /* At the end, just before the exit condition. */
396 IP_END
, /* At the end of the latch block. */
397 IP_BEFORE_USE
, /* Immediately before a specific use. */
398 IP_AFTER_USE
, /* Immediately after a specific use. */
399 IP_ORIGINAL
/* The original biv. */
402 /* The induction variable candidate. */
405 unsigned id
; /* The number of the candidate. */
406 bool important
; /* Whether this is an "important" candidate, i.e. such
407 that it should be considered by all uses. */
408 ENUM_BITFIELD(iv_position
) pos
: 8; /* Where it is computed. */
409 gimple
*incremented_at
;/* For original biv, the statement where it is
411 tree var_before
; /* The variable used for it before increment. */
412 tree var_after
; /* The variable used for it after increment. */
413 struct iv
*iv
; /* The value of the candidate. NULL for
414 "pseudocandidate" used to indicate the possibility
415 to replace the final value of an iv by direct
416 computation of the value. */
417 unsigned cost
; /* Cost of the candidate. */
418 unsigned cost_step
; /* Cost of the candidate's increment operation. */
419 struct iv_use
*ainc_use
; /* For IP_{BEFORE,AFTER}_USE candidates, the place
420 where it is incremented. */
421 bitmap depends_on
; /* The list of invariants that are used in step of the
423 struct iv
*orig_iv
; /* The original iv if this cand is added from biv with
427 /* Hashtable entry for common candidate derived from iv uses. */
428 struct iv_common_cand
432 /* IV uses from which this common candidate is derived. */
433 auto_vec
<struct iv_use
*> uses
;
437 /* Hashtable helpers. */
439 struct iv_common_cand_hasher
: delete_ptr_hash
<iv_common_cand
>
441 static inline hashval_t
hash (const iv_common_cand
*);
442 static inline bool equal (const iv_common_cand
*, const iv_common_cand
*);
445 /* Hash function for possible common candidates. */
448 iv_common_cand_hasher::hash (const iv_common_cand
*ccand
)
453 /* Hash table equality function for common candidates. */
456 iv_common_cand_hasher::equal (const iv_common_cand
*ccand1
,
457 const iv_common_cand
*ccand2
)
459 return (ccand1
->hash
== ccand2
->hash
460 && operand_equal_p (ccand1
->base
, ccand2
->base
, 0)
461 && operand_equal_p (ccand1
->step
, ccand2
->step
, 0)
462 && (TYPE_PRECISION (TREE_TYPE (ccand1
->base
))
463 == TYPE_PRECISION (TREE_TYPE (ccand2
->base
))));
466 /* Loop invariant expression hashtable entry. */
468 struct iv_inv_expr_ent
470 /* Tree expression of the entry. */
472 /* Unique indentifier. */
478 /* Sort iv_inv_expr_ent pair A and B by id field. */
481 sort_iv_inv_expr_ent (const void *a
, const void *b
)
483 const iv_inv_expr_ent
* const *e1
= (const iv_inv_expr_ent
* const *) (a
);
484 const iv_inv_expr_ent
* const *e2
= (const iv_inv_expr_ent
* const *) (b
);
486 unsigned id1
= (*e1
)->id
;
487 unsigned id2
= (*e2
)->id
;
497 /* Hashtable helpers. */
499 struct iv_inv_expr_hasher
: free_ptr_hash
<iv_inv_expr_ent
>
501 static inline hashval_t
hash (const iv_inv_expr_ent
*);
502 static inline bool equal (const iv_inv_expr_ent
*, const iv_inv_expr_ent
*);
505 /* Hash function for loop invariant expressions. */
508 iv_inv_expr_hasher::hash (const iv_inv_expr_ent
*expr
)
513 /* Hash table equality function for expressions. */
516 iv_inv_expr_hasher::equal (const iv_inv_expr_ent
*expr1
,
517 const iv_inv_expr_ent
*expr2
)
519 return expr1
->hash
== expr2
->hash
520 && operand_equal_p (expr1
->expr
, expr2
->expr
, 0);
525 /* The currently optimized loop. */
526 struct loop
*current_loop
;
527 source_location loop_loc
;
529 /* Numbers of iterations for all exits of the current loop. */
530 hash_map
<edge
, tree_niter_desc
*> *niters
;
532 /* Number of registers used in it. */
535 /* The size of version_info array allocated. */
536 unsigned version_info_size
;
538 /* The array of information for the ssa names. */
539 struct version_info
*version_info
;
541 /* The hashtable of loop invariant expressions created
543 hash_table
<iv_inv_expr_hasher
> *inv_expr_tab
;
545 /* Loop invariant expression id. */
548 /* The bitmap of indices in version_info whose value was changed. */
551 /* The uses of induction variables. */
552 vec
<iv_group
*> vgroups
;
554 /* The candidates. */
555 vec
<iv_cand
*> vcands
;
557 /* A bitmap of important candidates. */
558 bitmap important_candidates
;
560 /* Cache used by tree_to_aff_combination_expand. */
561 hash_map
<tree
, name_expansion
*> *name_expansion_cache
;
563 /* The hashtable of common candidates derived from iv uses. */
564 hash_table
<iv_common_cand_hasher
> *iv_common_cand_tab
;
566 /* The common candidates. */
567 vec
<iv_common_cand
*> iv_common_cands
;
569 /* The maximum invariant id. */
572 /* Number of no_overflow BIVs which are not used in memory address. */
573 unsigned bivs_not_used_in_addr
;
575 /* Obstack for iv structure. */
576 struct obstack iv_obstack
;
578 /* Whether to consider just related and important candidates when replacing a
580 bool consider_all_candidates
;
582 /* Are we optimizing for speed? */
585 /* Whether the loop body includes any function calls. */
586 bool body_includes_call
;
588 /* Whether the loop body can only be exited via single exit. */
589 bool loop_single_exit_p
;
592 /* An assignment of iv candidates to uses. */
596 /* The number of uses covered by the assignment. */
599 /* Number of uses that cannot be expressed by the candidates in the set. */
602 /* Candidate assigned to a use, together with the related costs. */
603 struct cost_pair
**cand_for_group
;
605 /* Number of times each candidate is used. */
606 unsigned *n_cand_uses
;
608 /* The candidates used. */
611 /* The number of candidates in the set. */
614 /* Total number of registers needed. */
617 /* Total cost of expressing uses. */
618 comp_cost cand_use_cost
;
620 /* Total cost of candidates. */
623 /* Number of times each invariant is used. */
624 unsigned *n_invariant_uses
;
626 /* Hash set with used invariant expression. */
627 hash_map
<iv_inv_expr_ent
*, unsigned> *used_inv_exprs
;
629 /* Total cost of the assignment. */
633 /* Difference of two iv candidate assignments. */
638 struct iv_group
*group
;
640 /* An old assignment (for rollback purposes). */
641 struct cost_pair
*old_cp
;
643 /* A new assignment. */
644 struct cost_pair
*new_cp
;
646 /* Next change in the list. */
647 struct iv_ca_delta
*next
;
650 /* Bound on number of candidates below that all candidates are considered. */
652 #define CONSIDER_ALL_CANDIDATES_BOUND \
653 ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
655 /* If there are more iv occurrences, we just give up (it is quite unlikely that
656 optimizing such a loop would help, and it would take ages). */
658 #define MAX_CONSIDERED_GROUPS \
659 ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
661 /* If there are at most this number of ivs in the set, try removing unnecessary
662 ivs from the set always. */
664 #define ALWAYS_PRUNE_CAND_SET_BOUND \
665 ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
667 /* The list of trees for that the decl_rtl field must be reset is stored
670 static vec
<tree
> decl_rtl_to_reset
;
672 static comp_cost
force_expr_to_var_cost (tree
, bool);
674 /* The single loop exit if it dominates the latch, NULL otherwise. */
677 single_dom_exit (struct loop
*loop
)
679 edge exit
= single_exit (loop
);
684 if (!just_once_each_iteration_p (loop
, exit
->src
))
690 /* Dumps information about the induction variable IV to FILE. Don't dump
691 variable's name if DUMP_NAME is FALSE. The information is dumped with
692 preceding spaces indicated by INDENT_LEVEL. */
695 dump_iv (FILE *file
, struct iv
*iv
, bool dump_name
, unsigned indent_level
)
698 const char spaces
[9] = {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '\0'};
700 if (indent_level
> 4)
702 p
= spaces
+ 8 - (indent_level
<< 1);
704 fprintf (file
, "%sIV struct:\n", p
);
705 if (iv
->ssa_name
&& dump_name
)
707 fprintf (file
, "%s SSA_NAME:\t", p
);
708 print_generic_expr (file
, iv
->ssa_name
, TDF_SLIM
);
709 fprintf (file
, "\n");
712 fprintf (file
, "%s Type:\t", p
);
713 print_generic_expr (file
, TREE_TYPE (iv
->base
), TDF_SLIM
);
714 fprintf (file
, "\n");
716 fprintf (file
, "%s Base:\t", p
);
717 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
718 fprintf (file
, "\n");
720 fprintf (file
, "%s Step:\t", p
);
721 print_generic_expr (file
, iv
->step
, TDF_SLIM
);
722 fprintf (file
, "\n");
726 fprintf (file
, "%s Object:\t", p
);
727 print_generic_expr (file
, iv
->base_object
, TDF_SLIM
);
728 fprintf (file
, "\n");
731 fprintf (file
, "%s Biv:\t%c\n", p
, iv
->biv_p
? 'Y' : 'N');
733 fprintf (file
, "%s Overflowness wrto loop niter:\t%s\n",
734 p
, iv
->no_overflow
? "No-overflow" : "Overflow");
737 /* Dumps information about the USE to FILE. */
740 dump_use (FILE *file
, struct iv_use
*use
)
742 fprintf (file
, " Use %d.%d:\n", use
->group_id
, use
->id
);
743 fprintf (file
, " At stmt:\t");
744 print_gimple_stmt (file
, use
->stmt
, 0, 0);
745 fprintf (file
, " At pos:\t");
747 print_generic_expr (file
, *use
->op_p
, TDF_SLIM
);
748 fprintf (file
, "\n");
749 dump_iv (file
, use
->iv
, false, 2);
752 /* Dumps information about the uses to FILE. */
755 dump_groups (FILE *file
, struct ivopts_data
*data
)
758 struct iv_group
*group
;
760 for (i
= 0; i
< data
->vgroups
.length (); i
++)
762 group
= data
->vgroups
[i
];
763 fprintf (file
, "Group %d:\n", group
->id
);
764 if (group
->type
== USE_NONLINEAR_EXPR
)
765 fprintf (file
, " Type:\tGENERIC\n");
766 else if (group
->type
== USE_ADDRESS
)
767 fprintf (file
, " Type:\tADDRESS\n");
770 gcc_assert (group
->type
== USE_COMPARE
);
771 fprintf (file
, " Type:\tCOMPARE\n");
773 for (j
= 0; j
< group
->vuses
.length (); j
++)
774 dump_use (file
, group
->vuses
[j
]);
778 /* Dumps information about induction variable candidate CAND to FILE. */
781 dump_cand (FILE *file
, struct iv_cand
*cand
)
783 struct iv
*iv
= cand
->iv
;
785 fprintf (file
, "Candidate %d:\n", cand
->id
);
786 if (cand
->depends_on
)
788 fprintf (file
, " Depend on: ");
789 dump_bitmap (file
, cand
->depends_on
);
792 if (cand
->var_before
)
794 fprintf (file
, " Var befor: ");
795 print_generic_expr (file
, cand
->var_before
, TDF_SLIM
);
796 fprintf (file
, "\n");
800 fprintf (file
, " Var after: ");
801 print_generic_expr (file
, cand
->var_after
, TDF_SLIM
);
802 fprintf (file
, "\n");
808 fprintf (file
, " Incr POS: before exit test\n");
812 fprintf (file
, " Incr POS: before use %d\n", cand
->ainc_use
->id
);
816 fprintf (file
, " Incr POS: after use %d\n", cand
->ainc_use
->id
);
820 fprintf (file
, " Incr POS: at end\n");
824 fprintf (file
, " Incr POS: orig biv\n");
828 dump_iv (file
, iv
, false, 1);
831 /* Returns the info for ssa version VER. */
833 static inline struct version_info
*
834 ver_info (struct ivopts_data
*data
, unsigned ver
)
836 return data
->version_info
+ ver
;
839 /* Returns the info for ssa name NAME. */
841 static inline struct version_info
*
842 name_info (struct ivopts_data
*data
, tree name
)
844 return ver_info (data
, SSA_NAME_VERSION (name
));
847 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
851 stmt_after_ip_normal_pos (struct loop
*loop
, gimple
*stmt
)
853 basic_block bb
= ip_normal_pos (loop
), sbb
= gimple_bb (stmt
);
857 if (sbb
== loop
->latch
)
863 return stmt
== last_stmt (bb
);
866 /* Returns true if STMT if after the place where the original induction
867 variable CAND is incremented. If TRUE_IF_EQUAL is set, we return true
868 if the positions are identical. */
871 stmt_after_inc_pos (struct iv_cand
*cand
, gimple
*stmt
, bool true_if_equal
)
873 basic_block cand_bb
= gimple_bb (cand
->incremented_at
);
874 basic_block stmt_bb
= gimple_bb (stmt
);
876 if (!dominated_by_p (CDI_DOMINATORS
, stmt_bb
, cand_bb
))
879 if (stmt_bb
!= cand_bb
)
883 && gimple_uid (stmt
) == gimple_uid (cand
->incremented_at
))
885 return gimple_uid (stmt
) > gimple_uid (cand
->incremented_at
);
888 /* Returns true if STMT if after the place where the induction variable
889 CAND is incremented in LOOP. */
892 stmt_after_increment (struct loop
*loop
, struct iv_cand
*cand
, gimple
*stmt
)
900 return stmt_after_ip_normal_pos (loop
, stmt
);
904 return stmt_after_inc_pos (cand
, stmt
, false);
907 return stmt_after_inc_pos (cand
, stmt
, true);
914 /* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
917 abnormal_ssa_name_p (tree exp
)
922 if (TREE_CODE (exp
) != SSA_NAME
)
925 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
) != 0;
928 /* Returns false if BASE or INDEX contains a ssa name that occurs in an
929 abnormal phi node. Callback for for_each_index. */
932 idx_contains_abnormal_ssa_name_p (tree base
, tree
*index
,
933 void *data ATTRIBUTE_UNUSED
)
935 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
937 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 2)))
939 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 3)))
943 return !abnormal_ssa_name_p (*index
);
946 /* Returns true if EXPR contains a ssa name that occurs in an
947 abnormal phi node. */
950 contains_abnormal_ssa_name_p (tree expr
)
953 enum tree_code_class codeclass
;
958 code
= TREE_CODE (expr
);
959 codeclass
= TREE_CODE_CLASS (code
);
961 if (code
== SSA_NAME
)
962 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr
) != 0;
964 if (code
== INTEGER_CST
965 || is_gimple_min_invariant (expr
))
968 if (code
== ADDR_EXPR
)
969 return !for_each_index (&TREE_OPERAND (expr
, 0),
970 idx_contains_abnormal_ssa_name_p
,
973 if (code
== COND_EXPR
)
974 return contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0))
975 || contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1))
976 || contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 2));
982 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1)))
987 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0)))
999 /* Returns the structure describing number of iterations determined from
1000 EXIT of DATA->current_loop, or NULL if something goes wrong. */
1002 static struct tree_niter_desc
*
1003 niter_for_exit (struct ivopts_data
*data
, edge exit
)
1005 struct tree_niter_desc
*desc
;
1006 tree_niter_desc
**slot
;
1010 data
->niters
= new hash_map
<edge
, tree_niter_desc
*>;
1014 slot
= data
->niters
->get (exit
);
1018 /* Try to determine number of iterations. We cannot safely work with ssa
1019 names that appear in phi nodes on abnormal edges, so that we do not
1020 create overlapping life ranges for them (PR 27283). */
1021 desc
= XNEW (struct tree_niter_desc
);
1022 if (!number_of_iterations_exit (data
->current_loop
,
1024 || contains_abnormal_ssa_name_p (desc
->niter
))
1029 data
->niters
->put (exit
, desc
);
1037 /* Returns the structure describing number of iterations determined from
1038 single dominating exit of DATA->current_loop, or NULL if something
1041 static struct tree_niter_desc
*
1042 niter_for_single_dom_exit (struct ivopts_data
*data
)
1044 edge exit
= single_dom_exit (data
->current_loop
);
1049 return niter_for_exit (data
, exit
);
1052 /* Initializes data structures used by the iv optimization pass, stored
1056 tree_ssa_iv_optimize_init (struct ivopts_data
*data
)
1058 data
->version_info_size
= 2 * num_ssa_names
;
1059 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
1060 data
->relevant
= BITMAP_ALLOC (NULL
);
1061 data
->important_candidates
= BITMAP_ALLOC (NULL
);
1062 data
->max_inv_id
= 0;
1063 data
->niters
= NULL
;
1064 data
->vgroups
.create (20);
1065 data
->vcands
.create (20);
1066 data
->inv_expr_tab
= new hash_table
<iv_inv_expr_hasher
> (10);
1067 data
->max_inv_expr_id
= 0;
1068 data
->name_expansion_cache
= NULL
;
1069 data
->iv_common_cand_tab
= new hash_table
<iv_common_cand_hasher
> (10);
1070 data
->iv_common_cands
.create (20);
1071 decl_rtl_to_reset
.create (20);
1072 gcc_obstack_init (&data
->iv_obstack
);
1075 /* Returns a memory object to that EXPR points. In case we are able to
1076 determine that it does not point to any such object, NULL is returned. */
1079 determine_base_object (tree expr
)
1081 enum tree_code code
= TREE_CODE (expr
);
1084 /* If this is a pointer casted to any type, we need to determine
1085 the base object for the pointer; so handle conversions before
1086 throwing away non-pointer expressions. */
1087 if (CONVERT_EXPR_P (expr
))
1088 return determine_base_object (TREE_OPERAND (expr
, 0));
1090 if (!POINTER_TYPE_P (TREE_TYPE (expr
)))
1099 obj
= TREE_OPERAND (expr
, 0);
1100 base
= get_base_address (obj
);
1105 if (TREE_CODE (base
) == MEM_REF
)
1106 return determine_base_object (TREE_OPERAND (base
, 0));
1108 return fold_convert (ptr_type_node
,
1109 build_fold_addr_expr (base
));
1111 case POINTER_PLUS_EXPR
:
1112 return determine_base_object (TREE_OPERAND (expr
, 0));
1116 /* Pointer addition is done solely using POINTER_PLUS_EXPR. */
1120 return fold_convert (ptr_type_node
, expr
);
1124 /* Return true if address expression with non-DECL_P operand appears
1128 contain_complex_addr_expr (tree expr
)
1133 switch (TREE_CODE (expr
))
1135 case POINTER_PLUS_EXPR
:
1138 res
|= contain_complex_addr_expr (TREE_OPERAND (expr
, 0));
1139 res
|= contain_complex_addr_expr (TREE_OPERAND (expr
, 1));
1143 return (!DECL_P (TREE_OPERAND (expr
, 0)));
1152 /* Allocates an induction variable with given initial value BASE and step STEP
1153 for loop LOOP. NO_OVERFLOW implies the iv doesn't overflow. */
1156 alloc_iv (struct ivopts_data
*data
, tree base
, tree step
,
1157 bool no_overflow
= false)
1160 struct iv
*iv
= (struct iv
*) obstack_alloc (&data
->iv_obstack
,
1161 sizeof (struct iv
));
1162 gcc_assert (step
!= NULL_TREE
);
1164 /* Lower address expression in base except ones with DECL_P as operand.
1166 1) More accurate cost can be computed for address expressions;
1167 2) Duplicate candidates won't be created for bases in different
1168 forms, like &a[0] and &a. */
1170 if ((TREE_CODE (expr
) == ADDR_EXPR
&& !DECL_P (TREE_OPERAND (expr
, 0)))
1171 || contain_complex_addr_expr (expr
))
1174 tree_to_aff_combination (expr
, TREE_TYPE (base
), &comb
);
1175 base
= fold_convert (TREE_TYPE (base
), aff_combination_to_tree (&comb
));
1179 iv
->base_object
= determine_base_object (base
);
1182 iv
->nonlin_use
= NULL
;
1183 iv
->ssa_name
= NULL_TREE
;
1185 && !iv_can_overflow_p (data
->current_loop
, TREE_TYPE (base
),
1188 iv
->no_overflow
= no_overflow
;
1189 iv
->have_address_use
= false;
1194 /* Sets STEP and BASE for induction variable IV. NO_OVERFLOW implies the IV
1195 doesn't overflow. */
1198 set_iv (struct ivopts_data
*data
, tree iv
, tree base
, tree step
,
1201 struct version_info
*info
= name_info (data
, iv
);
1203 gcc_assert (!info
->iv
);
1205 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (iv
));
1206 info
->iv
= alloc_iv (data
, base
, step
, no_overflow
);
1207 info
->iv
->ssa_name
= iv
;
1210 /* Finds induction variable declaration for VAR. */
1213 get_iv (struct ivopts_data
*data
, tree var
)
1216 tree type
= TREE_TYPE (var
);
1218 if (!POINTER_TYPE_P (type
)
1219 && !INTEGRAL_TYPE_P (type
))
1222 if (!name_info (data
, var
)->iv
)
1224 bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
1227 || !flow_bb_inside_loop_p (data
->current_loop
, bb
))
1228 set_iv (data
, var
, var
, build_int_cst (type
, 0), true);
1231 return name_info (data
, var
)->iv
;
1234 /* Return the first non-invariant ssa var found in EXPR. */
1237 extract_single_var_from_expr (tree expr
)
1241 enum tree_code code
;
1243 if (!expr
|| is_gimple_min_invariant (expr
))
1246 code
= TREE_CODE (expr
);
1247 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1249 n
= TREE_OPERAND_LENGTH (expr
);
1250 for (i
= 0; i
< n
; i
++)
1252 tmp
= extract_single_var_from_expr (TREE_OPERAND (expr
, i
));
1258 return (TREE_CODE (expr
) == SSA_NAME
) ? expr
: NULL
;
1261 /* Finds basic ivs. */
1264 find_bivs (struct ivopts_data
*data
)
1268 tree step
, type
, base
, stop
;
1270 struct loop
*loop
= data
->current_loop
;
1273 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1277 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
1280 if (virtual_operand_p (PHI_RESULT (phi
)))
1283 if (!simple_iv (loop
, loop
, PHI_RESULT (phi
), &iv
, true))
1286 if (integer_zerop (iv
.step
))
1290 base
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1291 /* Stop expanding iv base at the first ssa var referred by iv step.
1292 Ideally we should stop at any ssa var, because that's expensive
1293 and unusual to happen, we just do it on the first one.
1295 See PR64705 for the rationale. */
1296 stop
= extract_single_var_from_expr (step
);
1297 base
= expand_simple_operations (base
, stop
);
1298 if (contains_abnormal_ssa_name_p (base
)
1299 || contains_abnormal_ssa_name_p (step
))
1302 type
= TREE_TYPE (PHI_RESULT (phi
));
1303 base
= fold_convert (type
, base
);
1306 if (POINTER_TYPE_P (type
))
1307 step
= convert_to_ptrofftype (step
);
1309 step
= fold_convert (type
, step
);
1312 set_iv (data
, PHI_RESULT (phi
), base
, step
, iv
.no_overflow
);
1319 /* Marks basic ivs. */
1322 mark_bivs (struct ivopts_data
*data
)
1327 struct iv
*iv
, *incr_iv
;
1328 struct loop
*loop
= data
->current_loop
;
1329 basic_block incr_bb
;
1332 data
->bivs_not_used_in_addr
= 0;
1333 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1337 iv
= get_iv (data
, PHI_RESULT (phi
));
1341 var
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
1342 def
= SSA_NAME_DEF_STMT (var
);
1343 /* Don't mark iv peeled from other one as biv. */
1345 && gimple_code (def
) == GIMPLE_PHI
1346 && gimple_bb (def
) == loop
->header
)
1349 incr_iv
= get_iv (data
, var
);
1353 /* If the increment is in the subloop, ignore it. */
1354 incr_bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
1355 if (incr_bb
->loop_father
!= data
->current_loop
1356 || (incr_bb
->flags
& BB_IRREDUCIBLE_LOOP
))
1360 incr_iv
->biv_p
= true;
1361 if (iv
->no_overflow
)
1362 data
->bivs_not_used_in_addr
++;
1363 if (incr_iv
->no_overflow
)
1364 data
->bivs_not_used_in_addr
++;
1368 /* Checks whether STMT defines a linear induction variable and stores its
1369 parameters to IV. */
1372 find_givs_in_stmt_scev (struct ivopts_data
*data
, gimple
*stmt
, affine_iv
*iv
)
1375 struct loop
*loop
= data
->current_loop
;
1377 iv
->base
= NULL_TREE
;
1378 iv
->step
= NULL_TREE
;
1380 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1383 lhs
= gimple_assign_lhs (stmt
);
1384 if (TREE_CODE (lhs
) != SSA_NAME
)
1387 if (!simple_iv (loop
, loop_containing_stmt (stmt
), lhs
, iv
, true))
1390 /* Stop expanding iv base at the first ssa var referred by iv step.
1391 Ideally we should stop at any ssa var, because that's expensive
1392 and unusual to happen, we just do it on the first one.
1394 See PR64705 for the rationale. */
1395 stop
= extract_single_var_from_expr (iv
->step
);
1396 iv
->base
= expand_simple_operations (iv
->base
, stop
);
1397 if (contains_abnormal_ssa_name_p (iv
->base
)
1398 || contains_abnormal_ssa_name_p (iv
->step
))
1401 /* If STMT could throw, then do not consider STMT as defining a GIV.
1402 While this will suppress optimizations, we can not safely delete this
1403 GIV and associated statements, even if it appears it is not used. */
1404 if (stmt_could_throw_p (stmt
))
1410 /* Finds general ivs in statement STMT. */
1413 find_givs_in_stmt (struct ivopts_data
*data
, gimple
*stmt
)
1417 if (!find_givs_in_stmt_scev (data
, stmt
, &iv
))
1420 set_iv (data
, gimple_assign_lhs (stmt
), iv
.base
, iv
.step
, iv
.no_overflow
);
1423 /* Finds general ivs in basic block BB. */
1426 find_givs_in_bb (struct ivopts_data
*data
, basic_block bb
)
1428 gimple_stmt_iterator bsi
;
1430 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1431 find_givs_in_stmt (data
, gsi_stmt (bsi
));
1434 /* Finds general ivs. */
1437 find_givs (struct ivopts_data
*data
)
1439 struct loop
*loop
= data
->current_loop
;
1440 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1443 for (i
= 0; i
< loop
->num_nodes
; i
++)
1444 find_givs_in_bb (data
, body
[i
]);
1448 /* For each ssa name defined in LOOP determines whether it is an induction
1449 variable and if so, its initial value and step. */
1452 find_induction_variables (struct ivopts_data
*data
)
1457 if (!find_bivs (data
))
1463 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1465 struct tree_niter_desc
*niter
= niter_for_single_dom_exit (data
);
1469 fprintf (dump_file
, " number of iterations ");
1470 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1471 if (!integer_zerop (niter
->may_be_zero
))
1473 fprintf (dump_file
, "; zero if ");
1474 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1476 fprintf (dump_file
, "\n");
1479 fprintf (dump_file
, "\n<Induction Vars>:\n");
1480 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1482 struct version_info
*info
= ver_info (data
, i
);
1483 if (info
->iv
&& info
->iv
->step
&& !integer_zerop (info
->iv
->step
))
1484 dump_iv (dump_file
, ver_info (data
, i
)->iv
, true, 0);
1491 /* Records a use of TYPE at *USE_P in STMT whose value is IV in GROUP.
1492 For address type use, ADDR_BASE is the stripped IV base, ADDR_OFFSET
1493 is the const offset stripped from IV base; for other types use, both
1494 are zero by default. */
1496 static struct iv_use
*
1497 record_use (struct iv_group
*group
, tree
*use_p
, struct iv
*iv
,
1498 gimple
*stmt
, enum use_type type
, tree addr_base
,
1499 unsigned HOST_WIDE_INT addr_offset
)
1501 struct iv_use
*use
= XCNEW (struct iv_use
);
1503 use
->id
= group
->vuses
.length ();
1504 use
->group_id
= group
->id
;
1509 use
->addr_base
= addr_base
;
1510 use
->addr_offset
= addr_offset
;
1512 group
->vuses
.safe_push (use
);
1516 /* Checks whether OP is a loop-level invariant and if so, records it.
1517 NONLINEAR_USE is true if the invariant is used in a way we do not
1518 handle specially. */
1521 record_invariant (struct ivopts_data
*data
, tree op
, bool nonlinear_use
)
1524 struct version_info
*info
;
1526 if (TREE_CODE (op
) != SSA_NAME
1527 || virtual_operand_p (op
))
1530 bb
= gimple_bb (SSA_NAME_DEF_STMT (op
));
1532 && flow_bb_inside_loop_p (data
->current_loop
, bb
))
1535 info
= name_info (data
, op
);
1537 info
->has_nonlin_use
|= nonlinear_use
;
1539 info
->inv_id
= ++data
->max_inv_id
;
1540 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (op
));
1544 strip_offset (tree expr
, unsigned HOST_WIDE_INT
*offset
);
1546 /* Record a group of TYPE. */
1548 static struct iv_group
*
1549 record_group (struct ivopts_data
*data
, enum use_type type
)
1551 struct iv_group
*group
= XCNEW (struct iv_group
);
1553 group
->id
= data
->vgroups
.length ();
1555 group
->related_cands
= BITMAP_ALLOC (NULL
);
1556 group
->vuses
.create (1);
1558 data
->vgroups
.safe_push (group
);
1562 /* Record a use of TYPE at *USE_P in STMT whose value is IV in a group.
1563 New group will be created if there is no existing group for the use. */
1565 static struct iv_use
*
1566 record_group_use (struct ivopts_data
*data
, tree
*use_p
,
1567 struct iv
*iv
, gimple
*stmt
, enum use_type type
)
1569 tree addr_base
= NULL
;
1570 struct iv_group
*group
= NULL
;
1571 unsigned HOST_WIDE_INT addr_offset
= 0;
1573 /* Record non address type use in a new group. */
1574 if (type
== USE_ADDRESS
&& iv
->base_object
)
1578 addr_base
= strip_offset (iv
->base
, &addr_offset
);
1579 for (i
= 0; i
< data
->vgroups
.length (); i
++)
1583 group
= data
->vgroups
[i
];
1584 use
= group
->vuses
[0];
1585 if (use
->type
!= USE_ADDRESS
|| !use
->iv
->base_object
)
1588 /* Check if it has the same stripped base and step. */
1589 if (operand_equal_p (iv
->base_object
, use
->iv
->base_object
, 0)
1590 && operand_equal_p (iv
->step
, use
->iv
->step
, 0)
1591 && operand_equal_p (addr_base
, use
->addr_base
, 0))
1594 if (i
== data
->vgroups
.length ())
1599 group
= record_group (data
, type
);
1601 return record_use (group
, use_p
, iv
, stmt
, type
, addr_base
, addr_offset
);
1604 /* Checks whether the use OP is interesting and if so, records it. */
1606 static struct iv_use
*
1607 find_interesting_uses_op (struct ivopts_data
*data
, tree op
)
1613 if (TREE_CODE (op
) != SSA_NAME
)
1616 iv
= get_iv (data
, op
);
1622 gcc_assert (iv
->nonlin_use
->type
== USE_NONLINEAR_EXPR
);
1623 return iv
->nonlin_use
;
1626 if (integer_zerop (iv
->step
))
1628 record_invariant (data
, op
, true);
1632 stmt
= SSA_NAME_DEF_STMT (op
);
1633 gcc_assert (gimple_code (stmt
) == GIMPLE_PHI
|| is_gimple_assign (stmt
));
1635 use
= record_group_use (data
, NULL
, iv
, stmt
, USE_NONLINEAR_EXPR
);
1636 iv
->nonlin_use
= use
;
1640 /* Given a condition in statement STMT, checks whether it is a compare
1641 of an induction variable and an invariant. If this is the case,
1642 CONTROL_VAR is set to location of the iv, BOUND to the location of
1643 the invariant, IV_VAR and IV_BOUND are set to the corresponding
1644 induction variable descriptions, and true is returned. If this is not
1645 the case, CONTROL_VAR and BOUND are set to the arguments of the
1646 condition and false is returned. */
1649 extract_cond_operands (struct ivopts_data
*data
, gimple
*stmt
,
1650 tree
**control_var
, tree
**bound
,
1651 struct iv
**iv_var
, struct iv
**iv_bound
)
1653 /* The objects returned when COND has constant operands. */
1654 static struct iv const_iv
;
1656 tree
*op0
= &zero
, *op1
= &zero
;
1657 struct iv
*iv0
= &const_iv
, *iv1
= &const_iv
;
1660 if (gimple_code (stmt
) == GIMPLE_COND
)
1662 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
1663 op0
= gimple_cond_lhs_ptr (cond_stmt
);
1664 op1
= gimple_cond_rhs_ptr (cond_stmt
);
1668 op0
= gimple_assign_rhs1_ptr (stmt
);
1669 op1
= gimple_assign_rhs2_ptr (stmt
);
1672 zero
= integer_zero_node
;
1673 const_iv
.step
= integer_zero_node
;
1675 if (TREE_CODE (*op0
) == SSA_NAME
)
1676 iv0
= get_iv (data
, *op0
);
1677 if (TREE_CODE (*op1
) == SSA_NAME
)
1678 iv1
= get_iv (data
, *op1
);
1680 /* Exactly one of the compared values must be an iv, and the other one must
1685 if (integer_zerop (iv0
->step
))
1687 /* Control variable may be on the other side. */
1688 std::swap (op0
, op1
);
1689 std::swap (iv0
, iv1
);
1691 ret
= !integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
);
1706 /* Checks whether the condition in STMT is interesting and if so,
1710 find_interesting_uses_cond (struct ivopts_data
*data
, gimple
*stmt
)
1712 tree
*var_p
, *bound_p
;
1715 if (!extract_cond_operands (data
, stmt
, &var_p
, &bound_p
, &var_iv
, NULL
))
1717 find_interesting_uses_op (data
, *var_p
);
1718 find_interesting_uses_op (data
, *bound_p
);
1722 record_group_use (data
, NULL
, var_iv
, stmt
, USE_COMPARE
);
1725 /* Returns the outermost loop EXPR is obviously invariant in
1726 relative to the loop LOOP, i.e. if all its operands are defined
1727 outside of the returned loop. Returns NULL if EXPR is not
1728 even obviously invariant in LOOP. */
1731 outermost_invariant_loop_for_expr (struct loop
*loop
, tree expr
)
1736 if (is_gimple_min_invariant (expr
))
1737 return current_loops
->tree_root
;
1739 if (TREE_CODE (expr
) == SSA_NAME
)
1741 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
1744 if (flow_bb_inside_loop_p (loop
, def_bb
))
1746 return superloop_at_depth (loop
,
1747 loop_depth (def_bb
->loop_father
) + 1);
1750 return current_loops
->tree_root
;
1756 unsigned maxdepth
= 0;
1757 len
= TREE_OPERAND_LENGTH (expr
);
1758 for (i
= 0; i
< len
; i
++)
1760 struct loop
*ivloop
;
1761 if (!TREE_OPERAND (expr
, i
))
1764 ivloop
= outermost_invariant_loop_for_expr (loop
, TREE_OPERAND (expr
, i
));
1767 maxdepth
= MAX (maxdepth
, loop_depth (ivloop
));
1770 return superloop_at_depth (loop
, maxdepth
);
1773 /* Returns true if expression EXPR is obviously invariant in LOOP,
1774 i.e. if all its operands are defined outside of the LOOP. LOOP
1775 should not be the function body. */
1778 expr_invariant_in_loop_p (struct loop
*loop
, tree expr
)
1783 gcc_assert (loop_depth (loop
) > 0);
1785 if (is_gimple_min_invariant (expr
))
1788 if (TREE_CODE (expr
) == SSA_NAME
)
1790 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
1792 && flow_bb_inside_loop_p (loop
, def_bb
))
1801 len
= TREE_OPERAND_LENGTH (expr
);
1802 for (i
= 0; i
< len
; i
++)
1803 if (TREE_OPERAND (expr
, i
)
1804 && !expr_invariant_in_loop_p (loop
, TREE_OPERAND (expr
, i
)))
1810 /* Given expression EXPR which computes inductive values with respect
1811 to loop recorded in DATA, this function returns biv from which EXPR
1812 is derived by tracing definition chains of ssa variables in EXPR. */
1815 find_deriving_biv_for_expr (struct ivopts_data
*data
, tree expr
)
1820 enum tree_code code
;
1823 if (expr
== NULL_TREE
)
1826 if (is_gimple_min_invariant (expr
))
1829 code
= TREE_CODE (expr
);
1830 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1832 n
= TREE_OPERAND_LENGTH (expr
);
1833 for (i
= 0; i
< n
; i
++)
1835 iv
= find_deriving_biv_for_expr (data
, TREE_OPERAND (expr
, i
));
1841 /* Stop if it's not ssa name. */
1842 if (code
!= SSA_NAME
)
1845 iv
= get_iv (data
, expr
);
1846 if (!iv
|| integer_zerop (iv
->step
))
1851 stmt
= SSA_NAME_DEF_STMT (expr
);
1852 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
1855 use_operand_p use_p
;
1857 if (virtual_operand_p (gimple_phi_result (phi
)))
1860 FOR_EACH_PHI_ARG (use_p
, phi
, iter
, SSA_OP_USE
)
1862 tree use
= USE_FROM_PTR (use_p
);
1863 iv
= find_deriving_biv_for_expr (data
, use
);
1869 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1872 e1
= gimple_assign_rhs1 (stmt
);
1873 code
= gimple_assign_rhs_code (stmt
);
1874 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1875 return find_deriving_biv_for_expr (data
, e1
);
1882 case POINTER_PLUS_EXPR
:
1883 /* Increments, decrements and multiplications by a constant
1885 e2
= gimple_assign_rhs2 (stmt
);
1886 iv
= find_deriving_biv_for_expr (data
, e2
);
1892 /* Casts are simple. */
1893 return find_deriving_biv_for_expr (data
, e1
);
1902 /* Record BIV, its predecessor and successor that they are used in
1903 address type uses. */
1906 record_biv_for_address_use (struct ivopts_data
*data
, struct iv
*biv
)
1909 tree type
, base_1
, base_2
;
1912 if (!biv
|| !biv
->biv_p
|| integer_zerop (biv
->step
)
1913 || biv
->have_address_use
|| !biv
->no_overflow
)
1916 type
= TREE_TYPE (biv
->base
);
1917 if (!INTEGRAL_TYPE_P (type
))
1920 biv
->have_address_use
= true;
1921 data
->bivs_not_used_in_addr
--;
1922 base_1
= fold_build2 (PLUS_EXPR
, type
, biv
->base
, biv
->step
);
1923 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1925 struct iv
*iv
= ver_info (data
, i
)->iv
;
1927 if (!iv
|| !iv
->biv_p
|| integer_zerop (iv
->step
)
1928 || iv
->have_address_use
|| !iv
->no_overflow
)
1931 if (type
!= TREE_TYPE (iv
->base
)
1932 || !INTEGRAL_TYPE_P (TREE_TYPE (iv
->base
)))
1935 if (!operand_equal_p (biv
->step
, iv
->step
, 0))
1938 base_2
= fold_build2 (PLUS_EXPR
, type
, iv
->base
, iv
->step
);
1939 if (operand_equal_p (base_1
, iv
->base
, 0)
1940 || operand_equal_p (base_2
, biv
->base
, 0))
1942 iv
->have_address_use
= true;
1943 data
->bivs_not_used_in_addr
--;
1948 /* Cumulates the steps of indices into DATA and replaces their values with the
1949 initial ones. Returns false when the value of the index cannot be determined.
1950 Callback for for_each_index. */
1952 struct ifs_ivopts_data
1954 struct ivopts_data
*ivopts_data
;
1960 idx_find_step (tree base
, tree
*idx
, void *data
)
1962 struct ifs_ivopts_data
*dta
= (struct ifs_ivopts_data
*) data
;
1964 bool use_overflow_semantics
= false;
1965 tree step
, iv_base
, iv_step
, lbound
, off
;
1966 struct loop
*loop
= dta
->ivopts_data
->current_loop
;
1968 /* If base is a component ref, require that the offset of the reference
1970 if (TREE_CODE (base
) == COMPONENT_REF
)
1972 off
= component_ref_field_offset (base
);
1973 return expr_invariant_in_loop_p (loop
, off
);
1976 /* If base is array, first check whether we will be able to move the
1977 reference out of the loop (in order to take its address in strength
1978 reduction). In order for this to work we need both lower bound
1979 and step to be loop invariants. */
1980 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
1982 /* Moreover, for a range, the size needs to be invariant as well. */
1983 if (TREE_CODE (base
) == ARRAY_RANGE_REF
1984 && !expr_invariant_in_loop_p (loop
, TYPE_SIZE (TREE_TYPE (base
))))
1987 step
= array_ref_element_size (base
);
1988 lbound
= array_ref_low_bound (base
);
1990 if (!expr_invariant_in_loop_p (loop
, step
)
1991 || !expr_invariant_in_loop_p (loop
, lbound
))
1995 if (TREE_CODE (*idx
) != SSA_NAME
)
1998 iv
= get_iv (dta
->ivopts_data
, *idx
);
2002 /* XXX We produce for a base of *D42 with iv->base being &x[0]
2003 *&x[0], which is not folded and does not trigger the
2004 ARRAY_REF path below. */
2007 if (integer_zerop (iv
->step
))
2010 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
2012 step
= array_ref_element_size (base
);
2014 /* We only handle addresses whose step is an integer constant. */
2015 if (TREE_CODE (step
) != INTEGER_CST
)
2019 /* The step for pointer arithmetics already is 1 byte. */
2020 step
= size_one_node
;
2024 if (iv
->no_overflow
&& nowrap_type_p (TREE_TYPE (iv_step
)))
2025 use_overflow_semantics
= true;
2027 if (!convert_affine_scev (dta
->ivopts_data
->current_loop
,
2028 sizetype
, &iv_base
, &iv_step
, dta
->stmt
,
2029 use_overflow_semantics
))
2031 /* The index might wrap. */
2035 step
= fold_build2 (MULT_EXPR
, sizetype
, step
, iv_step
);
2036 dta
->step
= fold_build2 (PLUS_EXPR
, sizetype
, dta
->step
, step
);
2038 if (dta
->ivopts_data
->bivs_not_used_in_addr
)
2041 iv
= find_deriving_biv_for_expr (dta
->ivopts_data
, iv
->ssa_name
);
2043 record_biv_for_address_use (dta
->ivopts_data
, iv
);
2048 /* Records use in index IDX. Callback for for_each_index. Ivopts data
2049 object is passed to it in DATA. */
2052 idx_record_use (tree base
, tree
*idx
,
2055 struct ivopts_data
*data
= (struct ivopts_data
*) vdata
;
2056 find_interesting_uses_op (data
, *idx
);
2057 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
2059 find_interesting_uses_op (data
, array_ref_element_size (base
));
2060 find_interesting_uses_op (data
, array_ref_low_bound (base
));
2065 /* If we can prove that TOP = cst * BOT for some constant cst,
2066 store cst to MUL and return true. Otherwise return false.
2067 The returned value is always sign-extended, regardless of the
2068 signedness of TOP and BOT. */
2071 constant_multiple_of (tree top
, tree bot
, widest_int
*mul
)
2074 enum tree_code code
;
2075 unsigned precision
= TYPE_PRECISION (TREE_TYPE (top
));
2076 widest_int res
, p0
, p1
;
2081 if (operand_equal_p (top
, bot
, 0))
2087 code
= TREE_CODE (top
);
2091 mby
= TREE_OPERAND (top
, 1);
2092 if (TREE_CODE (mby
) != INTEGER_CST
)
2095 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &res
))
2098 *mul
= wi::sext (res
* wi::to_widest (mby
), precision
);
2103 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &p0
)
2104 || !constant_multiple_of (TREE_OPERAND (top
, 1), bot
, &p1
))
2107 if (code
== MINUS_EXPR
)
2109 *mul
= wi::sext (p0
+ p1
, precision
);
2113 if (TREE_CODE (bot
) != INTEGER_CST
)
2116 p0
= widest_int::from (top
, SIGNED
);
2117 p1
= widest_int::from (bot
, SIGNED
);
2120 *mul
= wi::sext (wi::divmod_trunc (p0
, p1
, SIGNED
, &res
), precision
);
2128 /* Return true if memory reference REF with step STEP may be unaligned. */
2131 may_be_unaligned_p (tree ref
, tree step
)
2133 /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
2134 thus they are not misaligned. */
2135 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
2138 unsigned int align
= TYPE_ALIGN (TREE_TYPE (ref
));
2139 if (GET_MODE_ALIGNMENT (TYPE_MODE (TREE_TYPE (ref
))) > align
)
2140 align
= GET_MODE_ALIGNMENT (TYPE_MODE (TREE_TYPE (ref
)));
2142 unsigned HOST_WIDE_INT bitpos
;
2143 unsigned int ref_align
;
2144 get_object_alignment_1 (ref
, &ref_align
, &bitpos
);
2145 if (ref_align
< align
2146 || (bitpos
% align
) != 0
2147 || (bitpos
% BITS_PER_UNIT
) != 0)
2150 unsigned int trailing_zeros
= tree_ctz (step
);
2151 if (trailing_zeros
< HOST_BITS_PER_INT
2152 && (1U << trailing_zeros
) * BITS_PER_UNIT
< align
)
2158 /* Return true if EXPR may be non-addressable. */
2161 may_be_nonaddressable_p (tree expr
)
2163 switch (TREE_CODE (expr
))
2165 case TARGET_MEM_REF
:
2166 /* TARGET_MEM_REFs are translated directly to valid MEMs on the
2167 target, thus they are always addressable. */
2171 /* Likewise for MEM_REFs, modulo the storage order. */
2172 return REF_REVERSE_STORAGE_ORDER (expr
);
2175 if (REF_REVERSE_STORAGE_ORDER (expr
))
2177 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
2180 if (TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (TREE_OPERAND (expr
, 0))))
2182 return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr
, 1))
2183 || may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
2186 case ARRAY_RANGE_REF
:
2187 if (TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (TREE_OPERAND (expr
, 0))))
2189 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
2191 case VIEW_CONVERT_EXPR
:
2192 /* This kind of view-conversions may wrap non-addressable objects
2193 and make them look addressable. After some processing the
2194 non-addressability may be uncovered again, causing ADDR_EXPRs
2195 of inappropriate objects to be built. */
2196 if (is_gimple_reg (TREE_OPERAND (expr
, 0))
2197 || !is_gimple_addressable (TREE_OPERAND (expr
, 0)))
2199 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
2211 /* Finds addresses in *OP_P inside STMT. */
2214 find_interesting_uses_address (struct ivopts_data
*data
, gimple
*stmt
,
2217 tree base
= *op_p
, step
= size_zero_node
;
2219 struct ifs_ivopts_data ifs_ivopts_data
;
2221 /* Do not play with volatile memory references. A bit too conservative,
2222 perhaps, but safe. */
2223 if (gimple_has_volatile_ops (stmt
))
2226 /* Ignore bitfields for now. Not really something terribly complicated
2228 if (TREE_CODE (base
) == BIT_FIELD_REF
)
2231 base
= unshare_expr (base
);
2233 if (TREE_CODE (base
) == TARGET_MEM_REF
)
2235 tree type
= build_pointer_type (TREE_TYPE (base
));
2239 && TREE_CODE (TMR_BASE (base
)) == SSA_NAME
)
2241 civ
= get_iv (data
, TMR_BASE (base
));
2245 TMR_BASE (base
) = civ
->base
;
2248 if (TMR_INDEX2 (base
)
2249 && TREE_CODE (TMR_INDEX2 (base
)) == SSA_NAME
)
2251 civ
= get_iv (data
, TMR_INDEX2 (base
));
2255 TMR_INDEX2 (base
) = civ
->base
;
2258 if (TMR_INDEX (base
)
2259 && TREE_CODE (TMR_INDEX (base
)) == SSA_NAME
)
2261 civ
= get_iv (data
, TMR_INDEX (base
));
2265 TMR_INDEX (base
) = civ
->base
;
2270 if (TMR_STEP (base
))
2271 astep
= fold_build2 (MULT_EXPR
, type
, TMR_STEP (base
), astep
);
2273 step
= fold_build2 (PLUS_EXPR
, type
, step
, astep
);
2277 if (integer_zerop (step
))
2279 base
= tree_mem_ref_addr (type
, base
);
2283 ifs_ivopts_data
.ivopts_data
= data
;
2284 ifs_ivopts_data
.stmt
= stmt
;
2285 ifs_ivopts_data
.step
= size_zero_node
;
2286 if (!for_each_index (&base
, idx_find_step
, &ifs_ivopts_data
)
2287 || integer_zerop (ifs_ivopts_data
.step
))
2289 step
= ifs_ivopts_data
.step
;
2291 /* Check that the base expression is addressable. This needs
2292 to be done after substituting bases of IVs into it. */
2293 if (may_be_nonaddressable_p (base
))
2296 /* Moreover, on strict alignment platforms, check that it is
2297 sufficiently aligned. */
2298 if (STRICT_ALIGNMENT
&& may_be_unaligned_p (base
, step
))
2301 base
= build_fold_addr_expr (base
);
2303 /* Substituting bases of IVs into the base expression might
2304 have caused folding opportunities. */
2305 if (TREE_CODE (base
) == ADDR_EXPR
)
2307 tree
*ref
= &TREE_OPERAND (base
, 0);
2308 while (handled_component_p (*ref
))
2309 ref
= &TREE_OPERAND (*ref
, 0);
2310 if (TREE_CODE (*ref
) == MEM_REF
)
2312 tree tem
= fold_binary (MEM_REF
, TREE_TYPE (*ref
),
2313 TREE_OPERAND (*ref
, 0),
2314 TREE_OPERAND (*ref
, 1));
2321 civ
= alloc_iv (data
, base
, step
);
2322 record_group_use (data
, op_p
, civ
, stmt
, USE_ADDRESS
);
2326 for_each_index (op_p
, idx_record_use
, data
);
2329 /* Finds and records invariants used in STMT. */
2332 find_invariants_stmt (struct ivopts_data
*data
, gimple
*stmt
)
2335 use_operand_p use_p
;
2338 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2340 op
= USE_FROM_PTR (use_p
);
2341 record_invariant (data
, op
, false);
2345 /* Finds interesting uses of induction variables in the statement STMT. */
2348 find_interesting_uses_stmt (struct ivopts_data
*data
, gimple
*stmt
)
2351 tree op
, *lhs
, *rhs
;
2353 use_operand_p use_p
;
2354 enum tree_code code
;
2356 find_invariants_stmt (data
, stmt
);
2358 if (gimple_code (stmt
) == GIMPLE_COND
)
2360 find_interesting_uses_cond (data
, stmt
);
2364 if (is_gimple_assign (stmt
))
2366 lhs
= gimple_assign_lhs_ptr (stmt
);
2367 rhs
= gimple_assign_rhs1_ptr (stmt
);
2369 if (TREE_CODE (*lhs
) == SSA_NAME
)
2371 /* If the statement defines an induction variable, the uses are not
2372 interesting by themselves. */
2374 iv
= get_iv (data
, *lhs
);
2376 if (iv
&& !integer_zerop (iv
->step
))
2380 code
= gimple_assign_rhs_code (stmt
);
2381 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
2382 && (REFERENCE_CLASS_P (*rhs
)
2383 || is_gimple_val (*rhs
)))
2385 if (REFERENCE_CLASS_P (*rhs
))
2386 find_interesting_uses_address (data
, stmt
, rhs
);
2388 find_interesting_uses_op (data
, *rhs
);
2390 if (REFERENCE_CLASS_P (*lhs
))
2391 find_interesting_uses_address (data
, stmt
, lhs
);
2394 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
2396 find_interesting_uses_cond (data
, stmt
);
2400 /* TODO -- we should also handle address uses of type
2402 memory = call (whatever);
2409 if (gimple_code (stmt
) == GIMPLE_PHI
2410 && gimple_bb (stmt
) == data
->current_loop
->header
)
2412 iv
= get_iv (data
, PHI_RESULT (stmt
));
2414 if (iv
&& !integer_zerop (iv
->step
))
2418 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2420 op
= USE_FROM_PTR (use_p
);
2422 if (TREE_CODE (op
) != SSA_NAME
)
2425 iv
= get_iv (data
, op
);
2429 find_interesting_uses_op (data
, op
);
2433 /* Finds interesting uses of induction variables outside of loops
2434 on loop exit edge EXIT. */
2437 find_interesting_uses_outside (struct ivopts_data
*data
, edge exit
)
2443 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2446 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
2447 if (!virtual_operand_p (def
))
2448 find_interesting_uses_op (data
, def
);
2452 /* Compute maximum offset of [base + offset] addressing mode
2453 for memory reference represented by USE. */
2455 static HOST_WIDE_INT
2456 compute_max_addr_offset (struct iv_use
*use
)
2460 HOST_WIDE_INT i
, off
;
2461 unsigned list_index
, num
;
2463 machine_mode mem_mode
, addr_mode
;
2464 static vec
<HOST_WIDE_INT
> max_offset_list
;
2466 as
= TYPE_ADDR_SPACE (TREE_TYPE (use
->iv
->base
));
2467 mem_mode
= TYPE_MODE (TREE_TYPE (*use
->op_p
));
2469 num
= max_offset_list
.length ();
2470 list_index
= (unsigned) as
* MAX_MACHINE_MODE
+ (unsigned) mem_mode
;
2471 if (list_index
>= num
)
2473 max_offset_list
.safe_grow (list_index
+ MAX_MACHINE_MODE
);
2474 for (; num
< max_offset_list
.length (); num
++)
2475 max_offset_list
[num
] = -1;
2478 off
= max_offset_list
[list_index
];
2482 addr_mode
= targetm
.addr_space
.address_mode (as
);
2483 reg
= gen_raw_REG (addr_mode
, LAST_VIRTUAL_REGISTER
+ 1);
2484 addr
= gen_rtx_fmt_ee (PLUS
, addr_mode
, reg
, NULL_RTX
);
2486 width
= GET_MODE_BITSIZE (addr_mode
) - 1;
2487 if (width
> (HOST_BITS_PER_WIDE_INT
- 1))
2488 width
= HOST_BITS_PER_WIDE_INT
- 1;
2490 for (i
= width
; i
> 0; i
--)
2492 off
= ((unsigned HOST_WIDE_INT
) 1 << i
) - 1;
2493 XEXP (addr
, 1) = gen_int_mode (off
, addr_mode
);
2494 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
2497 /* For some strict-alignment targets, the offset must be naturally
2498 aligned. Try an aligned offset if mem_mode is not QImode. */
2499 off
= ((unsigned HOST_WIDE_INT
) 1 << i
);
2500 if (off
> GET_MODE_SIZE (mem_mode
) && mem_mode
!= QImode
)
2502 off
-= GET_MODE_SIZE (mem_mode
);
2503 XEXP (addr
, 1) = gen_int_mode (off
, addr_mode
);
2504 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
2511 max_offset_list
[list_index
] = off
;
2515 /* Comparison function to sort group in ascending order of addr_offset. */
2518 group_compare_offset (const void *a
, const void *b
)
2520 const struct iv_use
*const *u1
= (const struct iv_use
*const *) a
;
2521 const struct iv_use
*const *u2
= (const struct iv_use
*const *) b
;
2523 if ((*u1
)->addr_offset
!= (*u2
)->addr_offset
)
2524 return (*u1
)->addr_offset
< (*u2
)->addr_offset
? -1 : 1;
2529 /* Check if small groups should be split. Return true if no group
2530 contains more than two uses with distinct addr_offsets. Return
2531 false otherwise. We want to split such groups because:
2533 1) Small groups don't have much benefit and may interfer with
2534 general candidate selection.
2535 2) Size for problem with only small groups is usually small and
2536 general algorithm can handle it well.
2538 TODO -- Above claim may not hold when we want to merge memory
2539 accesses with conseuctive addresses. */
2542 split_small_address_groups_p (struct ivopts_data
*data
)
2544 unsigned int i
, j
, distinct
= 1;
2546 struct iv_group
*group
;
2548 for (i
= 0; i
< data
->vgroups
.length (); i
++)
2550 group
= data
->vgroups
[i
];
2551 if (group
->vuses
.length () == 1)
2554 gcc_assert (group
->type
== USE_ADDRESS
);
2555 if (group
->vuses
.length () == 2)
2557 if (group
->vuses
[0]->addr_offset
> group
->vuses
[1]->addr_offset
)
2558 std::swap (group
->vuses
[0], group
->vuses
[1]);
2561 group
->vuses
.qsort (group_compare_offset
);
2567 for (pre
= group
->vuses
[0], j
= 1; j
< group
->vuses
.length (); j
++)
2569 if (group
->vuses
[j
]->addr_offset
!= pre
->addr_offset
)
2571 pre
= group
->vuses
[j
];
2580 return (distinct
<= 2);
2583 /* For each group of address type uses, this function further groups
2584 these uses according to the maximum offset supported by target's
2585 [base + offset] addressing mode. */
2588 split_address_groups (struct ivopts_data
*data
)
2591 HOST_WIDE_INT max_offset
= -1;
2593 /* Reset max offset to split all small groups. */
2594 if (split_small_address_groups_p (data
))
2597 for (i
= 0; i
< data
->vgroups
.length (); i
++)
2599 struct iv_group
*group
= data
->vgroups
[i
];
2600 struct iv_use
*use
= group
->vuses
[0];
2603 use
->group_id
= group
->id
;
2604 if (group
->vuses
.length () == 1)
2607 if (max_offset
!= 0)
2608 max_offset
= compute_max_addr_offset (use
);
2610 for (j
= 1; j
< group
->vuses
.length (); j
++)
2612 struct iv_use
*next
= group
->vuses
[j
];
2614 /* Only uses with offset that can fit in offset part against
2615 the first use can be grouped together. */
2616 if (next
->addr_offset
- use
->addr_offset
2617 > (unsigned HOST_WIDE_INT
) max_offset
)
2621 next
->group_id
= group
->id
;
2624 if (j
< group
->vuses
.length ())
2626 struct iv_group
*new_group
= record_group (data
, group
->type
);
2627 new_group
->vuses
.safe_splice (group
->vuses
);
2628 new_group
->vuses
.block_remove (0, j
);
2629 group
->vuses
.truncate (j
);
2634 /* Finds uses of the induction variables that are interesting. */
2637 find_interesting_uses (struct ivopts_data
*data
)
2640 gimple_stmt_iterator bsi
;
2641 basic_block
*body
= get_loop_body (data
->current_loop
);
2645 for (i
= 0; i
< data
->current_loop
->num_nodes
; i
++)
2650 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2651 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2652 && !flow_bb_inside_loop_p (data
->current_loop
, e
->dest
))
2653 find_interesting_uses_outside (data
, e
);
2655 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2656 find_interesting_uses_stmt (data
, gsi_stmt (bsi
));
2657 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2658 if (!is_gimple_debug (gsi_stmt (bsi
)))
2659 find_interesting_uses_stmt (data
, gsi_stmt (bsi
));
2662 split_address_groups (data
);
2664 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2668 fprintf (dump_file
, "\n<Invariant Vars>:\n");
2669 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
2671 struct version_info
*info
= ver_info (data
, i
);
2674 fprintf (dump_file
, "Inv %d:\t", info
->inv_id
);
2675 print_generic_expr (dump_file
, info
->name
, TDF_SLIM
);
2676 fprintf (dump_file
, "%s\n",
2677 info
->has_nonlin_use
? "" : "\t(eliminable)");
2681 fprintf (dump_file
, "\n<IV Groups>:\n");
2682 dump_groups (dump_file
, data
);
2683 fprintf (dump_file
, "\n");
2689 /* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
2690 is true, assume we are inside an address. If TOP_COMPREF is true, assume
2691 we are at the top-level of the processed address. */
2694 strip_offset_1 (tree expr
, bool inside_addr
, bool top_compref
,
2695 HOST_WIDE_INT
*offset
)
2697 tree op0
= NULL_TREE
, op1
= NULL_TREE
, tmp
, step
;
2698 enum tree_code code
;
2699 tree type
, orig_type
= TREE_TYPE (expr
);
2700 HOST_WIDE_INT off0
, off1
, st
;
2701 tree orig_expr
= expr
;
2705 type
= TREE_TYPE (expr
);
2706 code
= TREE_CODE (expr
);
2712 if (!cst_and_fits_in_hwi (expr
)
2713 || integer_zerop (expr
))
2716 *offset
= int_cst_value (expr
);
2717 return build_int_cst (orig_type
, 0);
2719 case POINTER_PLUS_EXPR
:
2722 op0
= TREE_OPERAND (expr
, 0);
2723 op1
= TREE_OPERAND (expr
, 1);
2725 op0
= strip_offset_1 (op0
, false, false, &off0
);
2726 op1
= strip_offset_1 (op1
, false, false, &off1
);
2728 *offset
= (code
== MINUS_EXPR
? off0
- off1
: off0
+ off1
);
2729 if (op0
== TREE_OPERAND (expr
, 0)
2730 && op1
== TREE_OPERAND (expr
, 1))
2733 if (integer_zerop (op1
))
2735 else if (integer_zerop (op0
))
2737 if (code
== MINUS_EXPR
)
2738 expr
= fold_build1 (NEGATE_EXPR
, type
, op1
);
2743 expr
= fold_build2 (code
, type
, op0
, op1
);
2745 return fold_convert (orig_type
, expr
);
2748 op1
= TREE_OPERAND (expr
, 1);
2749 if (!cst_and_fits_in_hwi (op1
))
2752 op0
= TREE_OPERAND (expr
, 0);
2753 op0
= strip_offset_1 (op0
, false, false, &off0
);
2754 if (op0
== TREE_OPERAND (expr
, 0))
2757 *offset
= off0
* int_cst_value (op1
);
2758 if (integer_zerop (op0
))
2761 expr
= fold_build2 (MULT_EXPR
, type
, op0
, op1
);
2763 return fold_convert (orig_type
, expr
);
2766 case ARRAY_RANGE_REF
:
2770 step
= array_ref_element_size (expr
);
2771 if (!cst_and_fits_in_hwi (step
))
2774 st
= int_cst_value (step
);
2775 op1
= TREE_OPERAND (expr
, 1);
2776 op1
= strip_offset_1 (op1
, false, false, &off1
);
2777 *offset
= off1
* st
;
2780 && integer_zerop (op1
))
2782 /* Strip the component reference completely. */
2783 op0
= TREE_OPERAND (expr
, 0);
2784 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
2797 tmp
= component_ref_field_offset (expr
);
2798 field
= TREE_OPERAND (expr
, 1);
2800 && cst_and_fits_in_hwi (tmp
)
2801 && cst_and_fits_in_hwi (DECL_FIELD_BIT_OFFSET (field
)))
2803 HOST_WIDE_INT boffset
, abs_off
;
2805 /* Strip the component reference completely. */
2806 op0
= TREE_OPERAND (expr
, 0);
2807 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
2808 boffset
= int_cst_value (DECL_FIELD_BIT_OFFSET (field
));
2809 abs_off
= abs_hwi (boffset
) / BITS_PER_UNIT
;
2813 *offset
= off0
+ int_cst_value (tmp
) + abs_off
;
2820 op0
= TREE_OPERAND (expr
, 0);
2821 op0
= strip_offset_1 (op0
, true, true, &off0
);
2824 if (op0
== TREE_OPERAND (expr
, 0))
2827 expr
= build_fold_addr_expr (op0
);
2828 return fold_convert (orig_type
, expr
);
2831 /* ??? Offset operand? */
2832 inside_addr
= false;
2839 /* Default handling of expressions for that we want to recurse into
2840 the first operand. */
2841 op0
= TREE_OPERAND (expr
, 0);
2842 op0
= strip_offset_1 (op0
, inside_addr
, false, &off0
);
2845 if (op0
== TREE_OPERAND (expr
, 0)
2846 && (!op1
|| op1
== TREE_OPERAND (expr
, 1)))
2849 expr
= copy_node (expr
);
2850 TREE_OPERAND (expr
, 0) = op0
;
2852 TREE_OPERAND (expr
, 1) = op1
;
2854 /* Inside address, we might strip the top level component references,
2855 thus changing type of the expression. Handling of ADDR_EXPR
2857 expr
= fold_convert (orig_type
, expr
);
2862 /* Strips constant offsets from EXPR and stores them to OFFSET. */
2865 strip_offset (tree expr
, unsigned HOST_WIDE_INT
*offset
)
2868 tree core
= strip_offset_1 (expr
, false, false, &off
);
2873 /* Returns variant of TYPE that can be used as base for different uses.
2874 We return unsigned type with the same precision, which avoids problems
2878 generic_type_for (tree type
)
2880 if (POINTER_TYPE_P (type
))
2881 return unsigned_type_for (type
);
2883 if (TYPE_UNSIGNED (type
))
2886 return unsigned_type_for (type
);
2889 /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
2890 the bitmap to that we should store it. */
2892 static struct ivopts_data
*fd_ivopts_data
;
2894 find_depends (tree
*expr_p
, int *ws ATTRIBUTE_UNUSED
, void *data
)
2896 bitmap
*depends_on
= (bitmap
*) data
;
2897 struct version_info
*info
;
2899 if (TREE_CODE (*expr_p
) != SSA_NAME
)
2901 info
= name_info (fd_ivopts_data
, *expr_p
);
2903 if (!info
->inv_id
|| info
->has_nonlin_use
)
2907 *depends_on
= BITMAP_ALLOC (NULL
);
2908 bitmap_set_bit (*depends_on
, info
->inv_id
);
2913 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2914 position to POS. If USE is not NULL, the candidate is set as related to
2915 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
2916 replacement of the final value of the iv by a direct computation. */
2918 static struct iv_cand
*
2919 add_candidate_1 (struct ivopts_data
*data
,
2920 tree base
, tree step
, bool important
, enum iv_position pos
,
2921 struct iv_use
*use
, gimple
*incremented_at
,
2922 struct iv
*orig_iv
= NULL
)
2925 struct iv_cand
*cand
= NULL
;
2926 tree type
, orig_type
;
2928 gcc_assert (base
&& step
);
2930 /* -fkeep-gc-roots-live means that we have to keep a real pointer
2931 live, but the ivopts code may replace a real pointer with one
2932 pointing before or after the memory block that is then adjusted
2933 into the memory block during the loop. FIXME: It would likely be
2934 better to actually force the pointer live and still use ivopts;
2935 for example, it would be enough to write the pointer into memory
2936 and keep it there until after the loop. */
2937 if (flag_keep_gc_roots_live
&& POINTER_TYPE_P (TREE_TYPE (base
)))
2940 /* For non-original variables, make sure their values are computed in a type
2941 that does not invoke undefined behavior on overflows (since in general,
2942 we cannot prove that these induction variables are non-wrapping). */
2943 if (pos
!= IP_ORIGINAL
)
2945 orig_type
= TREE_TYPE (base
);
2946 type
= generic_type_for (orig_type
);
2947 if (type
!= orig_type
)
2949 base
= fold_convert (type
, base
);
2950 step
= fold_convert (type
, step
);
2954 for (i
= 0; i
< data
->vcands
.length (); i
++)
2956 cand
= data
->vcands
[i
];
2958 if (cand
->pos
!= pos
)
2961 if (cand
->incremented_at
!= incremented_at
2962 || ((pos
== IP_AFTER_USE
|| pos
== IP_BEFORE_USE
)
2963 && cand
->ainc_use
!= use
))
2966 if (operand_equal_p (base
, cand
->iv
->base
, 0)
2967 && operand_equal_p (step
, cand
->iv
->step
, 0)
2968 && (TYPE_PRECISION (TREE_TYPE (base
))
2969 == TYPE_PRECISION (TREE_TYPE (cand
->iv
->base
))))
2973 if (i
== data
->vcands
.length ())
2975 cand
= XCNEW (struct iv_cand
);
2977 cand
->iv
= alloc_iv (data
, base
, step
);
2979 if (pos
!= IP_ORIGINAL
)
2981 cand
->var_before
= create_tmp_var_raw (TREE_TYPE (base
), "ivtmp");
2982 cand
->var_after
= cand
->var_before
;
2984 cand
->important
= important
;
2985 cand
->incremented_at
= incremented_at
;
2986 data
->vcands
.safe_push (cand
);
2988 if (TREE_CODE (step
) != INTEGER_CST
)
2990 fd_ivopts_data
= data
;
2991 walk_tree (&step
, find_depends
, &cand
->depends_on
, NULL
);
2994 if (pos
== IP_AFTER_USE
|| pos
== IP_BEFORE_USE
)
2995 cand
->ainc_use
= use
;
2997 cand
->ainc_use
= NULL
;
2999 cand
->orig_iv
= orig_iv
;
3000 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3001 dump_cand (dump_file
, cand
);
3004 cand
->important
|= important
;
3006 /* Relate candidate to the group for which it is added. */
3008 bitmap_set_bit (data
->vgroups
[use
->group_id
]->related_cands
, i
);
3013 /* Returns true if incrementing the induction variable at the end of the LOOP
3016 The purpose is to avoid splitting latch edge with a biv increment, thus
3017 creating a jump, possibly confusing other optimization passes and leaving
3018 less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS
3019 is not available (so we do not have a better alternative), or if the latch
3020 edge is already nonempty. */
3023 allow_ip_end_pos_p (struct loop
*loop
)
3025 if (!ip_normal_pos (loop
))
3028 if (!empty_block_p (ip_end_pos (loop
)))
3034 /* If possible, adds autoincrement candidates BASE + STEP * i based on use USE.
3035 Important field is set to IMPORTANT. */
3038 add_autoinc_candidates (struct ivopts_data
*data
, tree base
, tree step
,
3039 bool important
, struct iv_use
*use
)
3041 basic_block use_bb
= gimple_bb (use
->stmt
);
3042 machine_mode mem_mode
;
3043 unsigned HOST_WIDE_INT cstepi
;
3045 /* If we insert the increment in any position other than the standard
3046 ones, we must ensure that it is incremented once per iteration.
3047 It must not be in an inner nested loop, or one side of an if
3049 if (use_bb
->loop_father
!= data
->current_loop
3050 || !dominated_by_p (CDI_DOMINATORS
, data
->current_loop
->latch
, use_bb
)
3051 || stmt_could_throw_p (use
->stmt
)
3052 || !cst_and_fits_in_hwi (step
))
3055 cstepi
= int_cst_value (step
);
3057 mem_mode
= TYPE_MODE (TREE_TYPE (*use
->op_p
));
3058 if (((USE_LOAD_PRE_INCREMENT (mem_mode
)
3059 || USE_STORE_PRE_INCREMENT (mem_mode
))
3060 && GET_MODE_SIZE (mem_mode
) == cstepi
)
3061 || ((USE_LOAD_PRE_DECREMENT (mem_mode
)
3062 || USE_STORE_PRE_DECREMENT (mem_mode
))
3063 && GET_MODE_SIZE (mem_mode
) == -cstepi
))
3065 enum tree_code code
= MINUS_EXPR
;
3067 tree new_step
= step
;
3069 if (POINTER_TYPE_P (TREE_TYPE (base
)))
3071 new_step
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (step
), step
);
3072 code
= POINTER_PLUS_EXPR
;
3075 new_step
= fold_convert (TREE_TYPE (base
), new_step
);
3076 new_base
= fold_build2 (code
, TREE_TYPE (base
), base
, new_step
);
3077 add_candidate_1 (data
, new_base
, step
, important
, IP_BEFORE_USE
, use
,
3080 if (((USE_LOAD_POST_INCREMENT (mem_mode
)
3081 || USE_STORE_POST_INCREMENT (mem_mode
))
3082 && GET_MODE_SIZE (mem_mode
) == cstepi
)
3083 || ((USE_LOAD_POST_DECREMENT (mem_mode
)
3084 || USE_STORE_POST_DECREMENT (mem_mode
))
3085 && GET_MODE_SIZE (mem_mode
) == -cstepi
))
3087 add_candidate_1 (data
, base
, step
, important
, IP_AFTER_USE
, use
,
3092 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
3093 position to POS. If USE is not NULL, the candidate is set as related to
3094 it. The candidate computation is scheduled before exit condition and at
3098 add_candidate (struct ivopts_data
*data
,
3099 tree base
, tree step
, bool important
, struct iv_use
*use
,
3100 struct iv
*orig_iv
= NULL
)
3102 if (ip_normal_pos (data
->current_loop
))
3103 add_candidate_1 (data
, base
, step
, important
,
3104 IP_NORMAL
, use
, NULL
, orig_iv
);
3105 if (ip_end_pos (data
->current_loop
)
3106 && allow_ip_end_pos_p (data
->current_loop
))
3107 add_candidate_1 (data
, base
, step
, important
, IP_END
, use
, NULL
, orig_iv
);
3110 /* Adds standard iv candidates. */
3113 add_standard_iv_candidates (struct ivopts_data
*data
)
3115 add_candidate (data
, integer_zero_node
, integer_one_node
, true, NULL
);
3117 /* The same for a double-integer type if it is still fast enough. */
3119 (long_integer_type_node
) > TYPE_PRECISION (integer_type_node
)
3120 && TYPE_PRECISION (long_integer_type_node
) <= BITS_PER_WORD
)
3121 add_candidate (data
, build_int_cst (long_integer_type_node
, 0),
3122 build_int_cst (long_integer_type_node
, 1), true, NULL
);
3124 /* The same for a double-integer type if it is still fast enough. */
3126 (long_long_integer_type_node
) > TYPE_PRECISION (long_integer_type_node
)
3127 && TYPE_PRECISION (long_long_integer_type_node
) <= BITS_PER_WORD
)
3128 add_candidate (data
, build_int_cst (long_long_integer_type_node
, 0),
3129 build_int_cst (long_long_integer_type_node
, 1), true, NULL
);
3133 /* Adds candidates bases on the old induction variable IV. */
3136 add_iv_candidate_for_biv (struct ivopts_data
*data
, struct iv
*iv
)
3140 struct iv_cand
*cand
;
3142 /* Check if this biv is used in address type use. */
3143 if (iv
->no_overflow
&& iv
->have_address_use
3144 && INTEGRAL_TYPE_P (TREE_TYPE (iv
->base
))
3145 && TYPE_PRECISION (TREE_TYPE (iv
->base
)) < TYPE_PRECISION (sizetype
))
3147 tree base
= fold_convert (sizetype
, iv
->base
);
3148 tree step
= fold_convert (sizetype
, iv
->step
);
3150 /* Add iv cand of same precision as index part in TARGET_MEM_REF. */
3151 add_candidate (data
, base
, step
, true, NULL
, iv
);
3152 /* Add iv cand of the original type only if it has nonlinear use. */
3154 add_candidate (data
, iv
->base
, iv
->step
, true, NULL
);
3157 add_candidate (data
, iv
->base
, iv
->step
, true, NULL
);
3159 /* The same, but with initial value zero. */
3160 if (POINTER_TYPE_P (TREE_TYPE (iv
->base
)))
3161 add_candidate (data
, size_int (0), iv
->step
, true, NULL
);
3163 add_candidate (data
, build_int_cst (TREE_TYPE (iv
->base
), 0),
3164 iv
->step
, true, NULL
);
3166 phi
= SSA_NAME_DEF_STMT (iv
->ssa_name
);
3167 if (gimple_code (phi
) == GIMPLE_PHI
)
3169 /* Additionally record the possibility of leaving the original iv
3171 def
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (data
->current_loop
));
3172 /* Don't add candidate if it's from another PHI node because
3173 it's an affine iv appearing in the form of PEELED_CHREC. */
3174 phi
= SSA_NAME_DEF_STMT (def
);
3175 if (gimple_code (phi
) != GIMPLE_PHI
)
3177 cand
= add_candidate_1 (data
,
3178 iv
->base
, iv
->step
, true, IP_ORIGINAL
, NULL
,
3179 SSA_NAME_DEF_STMT (def
));
3182 cand
->var_before
= iv
->ssa_name
;
3183 cand
->var_after
= def
;
3187 gcc_assert (gimple_bb (phi
) == data
->current_loop
->header
);
3191 /* Adds candidates based on the old induction variables. */
3194 add_iv_candidate_for_bivs (struct ivopts_data
*data
)
3200 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
3202 iv
= ver_info (data
, i
)->iv
;
3203 if (iv
&& iv
->biv_p
&& !integer_zerop (iv
->step
))
3204 add_iv_candidate_for_biv (data
, iv
);
3208 /* Record common candidate {BASE, STEP} derived from USE in hashtable. */
3211 record_common_cand (struct ivopts_data
*data
, tree base
,
3212 tree step
, struct iv_use
*use
)
3214 struct iv_common_cand ent
;
3215 struct iv_common_cand
**slot
;
3219 ent
.hash
= iterative_hash_expr (base
, 0);
3220 ent
.hash
= iterative_hash_expr (step
, ent
.hash
);
3222 slot
= data
->iv_common_cand_tab
->find_slot (&ent
, INSERT
);
3225 *slot
= new iv_common_cand ();
3226 (*slot
)->base
= base
;
3227 (*slot
)->step
= step
;
3228 (*slot
)->uses
.create (8);
3229 (*slot
)->hash
= ent
.hash
;
3230 data
->iv_common_cands
.safe_push ((*slot
));
3233 gcc_assert (use
!= NULL
);
3234 (*slot
)->uses
.safe_push (use
);
3238 /* Comparison function used to sort common candidates. */
3241 common_cand_cmp (const void *p1
, const void *p2
)
3244 const struct iv_common_cand
*const *const ccand1
3245 = (const struct iv_common_cand
*const *)p1
;
3246 const struct iv_common_cand
*const *const ccand2
3247 = (const struct iv_common_cand
*const *)p2
;
3249 n1
= (*ccand1
)->uses
.length ();
3250 n2
= (*ccand2
)->uses
.length ();
3254 /* Adds IV candidates based on common candidated recorded. */
3257 add_iv_candidate_derived_from_uses (struct ivopts_data
*data
)
3260 struct iv_cand
*cand_1
, *cand_2
;
3262 data
->iv_common_cands
.qsort (common_cand_cmp
);
3263 for (i
= 0; i
< data
->iv_common_cands
.length (); i
++)
3265 struct iv_common_cand
*ptr
= data
->iv_common_cands
[i
];
3267 /* Only add IV candidate if it's derived from multiple uses. */
3268 if (ptr
->uses
.length () <= 1)
3273 if (ip_normal_pos (data
->current_loop
))
3274 cand_1
= add_candidate_1 (data
, ptr
->base
, ptr
->step
,
3275 false, IP_NORMAL
, NULL
, NULL
);
3277 if (ip_end_pos (data
->current_loop
)
3278 && allow_ip_end_pos_p (data
->current_loop
))
3279 cand_2
= add_candidate_1 (data
, ptr
->base
, ptr
->step
,
3280 false, IP_END
, NULL
, NULL
);
3282 /* Bind deriving uses and the new candidates. */
3283 for (j
= 0; j
< ptr
->uses
.length (); j
++)
3285 struct iv_group
*group
= data
->vgroups
[ptr
->uses
[j
]->group_id
];
3287 bitmap_set_bit (group
->related_cands
, cand_1
->id
);
3289 bitmap_set_bit (group
->related_cands
, cand_2
->id
);
3293 /* Release data since it is useless from this point. */
3294 data
->iv_common_cand_tab
->empty ();
3295 data
->iv_common_cands
.truncate (0);
3298 /* Adds candidates based on the value of USE's iv. */
3301 add_iv_candidate_for_use (struct ivopts_data
*data
, struct iv_use
*use
)
3303 unsigned HOST_WIDE_INT offset
;
3306 struct iv
*iv
= use
->iv
;
3308 add_candidate (data
, iv
->base
, iv
->step
, false, use
);
3310 /* Record common candidate for use in case it can be shared by others. */
3311 record_common_cand (data
, iv
->base
, iv
->step
, use
);
3313 /* Record common candidate with initial value zero. */
3314 basetype
= TREE_TYPE (iv
->base
);
3315 if (POINTER_TYPE_P (basetype
))
3316 basetype
= sizetype
;
3317 record_common_cand (data
, build_int_cst (basetype
, 0), iv
->step
, use
);
3319 /* Record common candidate with constant offset stripped in base.
3320 Like the use itself, we also add candidate directly for it. */
3321 base
= strip_offset (iv
->base
, &offset
);
3322 if (offset
|| base
!= iv
->base
)
3324 record_common_cand (data
, base
, iv
->step
, use
);
3325 add_candidate (data
, base
, iv
->step
, false, use
);
3328 /* Record common candidate with base_object removed in base. */
3329 if (iv
->base_object
!= NULL
)
3333 tree step
, base_object
= iv
->base_object
;
3339 STRIP_NOPS (base_object
);
3340 tree_to_aff_combination (base
, TREE_TYPE (base
), &aff_base
);
3341 for (i
= 0; i
< aff_base
.n
; i
++)
3343 if (aff_base
.elts
[i
].coef
!= 1)
3346 if (operand_equal_p (aff_base
.elts
[i
].val
, base_object
, 0))
3351 aff_combination_remove_elt (&aff_base
, i
);
3352 base
= aff_combination_to_tree (&aff_base
);
3353 basetype
= TREE_TYPE (base
);
3354 if (POINTER_TYPE_P (basetype
))
3355 basetype
= sizetype
;
3357 step
= fold_convert (basetype
, step
);
3358 record_common_cand (data
, base
, step
, use
);
3359 /* Also record common candidate with offset stripped. */
3360 base
= strip_offset (base
, &offset
);
3362 record_common_cand (data
, base
, step
, use
);
3366 /* At last, add auto-incremental candidates. Make such variables
3367 important since other iv uses with same base object may be based
3369 if (use
!= NULL
&& use
->type
== USE_ADDRESS
)
3370 add_autoinc_candidates (data
, iv
->base
, iv
->step
, true, use
);
3373 /* Adds candidates based on the uses. */
3376 add_iv_candidate_for_groups (struct ivopts_data
*data
)
3380 /* Only add candidate for the first use in group. */
3381 for (i
= 0; i
< data
->vgroups
.length (); i
++)
3383 struct iv_group
*group
= data
->vgroups
[i
];
3385 gcc_assert (group
->vuses
[0] != NULL
);
3386 add_iv_candidate_for_use (data
, group
->vuses
[0]);
3388 add_iv_candidate_derived_from_uses (data
);
3391 /* Record important candidates and add them to related_cands bitmaps. */
3394 record_important_candidates (struct ivopts_data
*data
)
3397 struct iv_group
*group
;
3399 for (i
= 0; i
< data
->vcands
.length (); i
++)
3401 struct iv_cand
*cand
= data
->vcands
[i
];
3403 if (cand
->important
)
3404 bitmap_set_bit (data
->important_candidates
, i
);
3407 data
->consider_all_candidates
= (data
->vcands
.length ()
3408 <= CONSIDER_ALL_CANDIDATES_BOUND
);
3410 /* Add important candidates to groups' related_cands bitmaps. */
3411 for (i
= 0; i
< data
->vgroups
.length (); i
++)
3413 group
= data
->vgroups
[i
];
3414 bitmap_ior_into (group
->related_cands
, data
->important_candidates
);
3418 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
3419 If consider_all_candidates is true, we use a two-dimensional array, otherwise
3420 we allocate a simple list to every use. */
3423 alloc_use_cost_map (struct ivopts_data
*data
)
3425 unsigned i
, size
, s
;
3427 for (i
= 0; i
< data
->vgroups
.length (); i
++)
3429 struct iv_group
*group
= data
->vgroups
[i
];
3431 if (data
->consider_all_candidates
)
3432 size
= data
->vcands
.length ();
3435 s
= bitmap_count_bits (group
->related_cands
);
3437 /* Round up to the power of two, so that moduling by it is fast. */
3438 size
= s
? (1 << ceil_log2 (s
)) : 1;
3441 group
->n_map_members
= size
;
3442 group
->cost_map
= XCNEWVEC (struct cost_pair
, size
);
3446 /* Sets cost of (GROUP, CAND) pair to COST and record that it depends
3447 on invariants DEPENDS_ON and that the value used in expressing it
3448 is VALUE, and in case of iv elimination the comparison operator is COMP. */
3451 set_group_iv_cost (struct ivopts_data
*data
,
3452 struct iv_group
*group
, struct iv_cand
*cand
,
3453 comp_cost cost
, bitmap depends_on
, tree value
,
3454 enum tree_code comp
, iv_inv_expr_ent
*inv_expr
)
3458 if (cost
.infinite_cost_p ())
3460 BITMAP_FREE (depends_on
);
3464 if (data
->consider_all_candidates
)
3466 group
->cost_map
[cand
->id
].cand
= cand
;
3467 group
->cost_map
[cand
->id
].cost
= cost
;
3468 group
->cost_map
[cand
->id
].depends_on
= depends_on
;
3469 group
->cost_map
[cand
->id
].value
= value
;
3470 group
->cost_map
[cand
->id
].comp
= comp
;
3471 group
->cost_map
[cand
->id
].inv_expr
= inv_expr
;
3475 /* n_map_members is a power of two, so this computes modulo. */
3476 s
= cand
->id
& (group
->n_map_members
- 1);
3477 for (i
= s
; i
< group
->n_map_members
; i
++)
3478 if (!group
->cost_map
[i
].cand
)
3480 for (i
= 0; i
< s
; i
++)
3481 if (!group
->cost_map
[i
].cand
)
3487 group
->cost_map
[i
].cand
= cand
;
3488 group
->cost_map
[i
].cost
= cost
;
3489 group
->cost_map
[i
].depends_on
= depends_on
;
3490 group
->cost_map
[i
].value
= value
;
3491 group
->cost_map
[i
].comp
= comp
;
3492 group
->cost_map
[i
].inv_expr
= inv_expr
;
3495 /* Gets cost of (GROUP, CAND) pair. */
3497 static struct cost_pair
*
3498 get_group_iv_cost (struct ivopts_data
*data
, struct iv_group
*group
,
3499 struct iv_cand
*cand
)
3502 struct cost_pair
*ret
;
3507 if (data
->consider_all_candidates
)
3509 ret
= group
->cost_map
+ cand
->id
;
3516 /* n_map_members is a power of two, so this computes modulo. */
3517 s
= cand
->id
& (group
->n_map_members
- 1);
3518 for (i
= s
; i
< group
->n_map_members
; i
++)
3519 if (group
->cost_map
[i
].cand
== cand
)
3520 return group
->cost_map
+ i
;
3521 else if (group
->cost_map
[i
].cand
== NULL
)
3523 for (i
= 0; i
< s
; i
++)
3524 if (group
->cost_map
[i
].cand
== cand
)
3525 return group
->cost_map
+ i
;
3526 else if (group
->cost_map
[i
].cand
== NULL
)
3532 /* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
3534 produce_memory_decl_rtl (tree obj
, int *regno
)
3536 addr_space_t as
= TYPE_ADDR_SPACE (TREE_TYPE (obj
));
3537 machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
3541 if (TREE_STATIC (obj
) || DECL_EXTERNAL (obj
))
3543 const char *name
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj
));
3544 x
= gen_rtx_SYMBOL_REF (address_mode
, name
);
3545 SET_SYMBOL_REF_DECL (x
, obj
);
3546 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
3547 set_mem_addr_space (x
, as
);
3548 targetm
.encode_section_info (obj
, x
, true);
3552 x
= gen_raw_REG (address_mode
, (*regno
)++);
3553 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
3554 set_mem_addr_space (x
, as
);
3560 /* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
3561 walk_tree. DATA contains the actual fake register number. */
3564 prepare_decl_rtl (tree
*expr_p
, int *ws
, void *data
)
3566 tree obj
= NULL_TREE
;
3568 int *regno
= (int *) data
;
3570 switch (TREE_CODE (*expr_p
))
3573 for (expr_p
= &TREE_OPERAND (*expr_p
, 0);
3574 handled_component_p (*expr_p
);
3575 expr_p
= &TREE_OPERAND (*expr_p
, 0))
3578 if (DECL_P (obj
) && HAS_RTL_P (obj
) && !DECL_RTL_SET_P (obj
))
3579 x
= produce_memory_decl_rtl (obj
, regno
);
3584 obj
= SSA_NAME_VAR (*expr_p
);
3585 /* Defer handling of anonymous SSA_NAMEs to the expander. */
3588 if (!DECL_RTL_SET_P (obj
))
3589 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
3598 if (DECL_RTL_SET_P (obj
))
3601 if (DECL_MODE (obj
) == BLKmode
)
3602 x
= produce_memory_decl_rtl (obj
, regno
);
3604 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
3614 decl_rtl_to_reset
.safe_push (obj
);
3615 SET_DECL_RTL (obj
, x
);
3621 /* Determines cost of the computation of EXPR. */
3624 computation_cost (tree expr
, bool speed
)
3628 tree type
= TREE_TYPE (expr
);
3630 /* Avoid using hard regs in ways which may be unsupported. */
3631 int regno
= LAST_VIRTUAL_REGISTER
+ 1;
3632 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
3633 enum node_frequency real_frequency
= node
->frequency
;
3635 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3636 crtl
->maybe_hot_insn_p
= speed
;
3637 walk_tree (&expr
, prepare_decl_rtl
, ®no
, NULL
);
3639 rslt
= expand_expr (expr
, NULL_RTX
, TYPE_MODE (type
), EXPAND_NORMAL
);
3642 default_rtl_profile ();
3643 node
->frequency
= real_frequency
;
3645 cost
= seq_cost (seq
, speed
);
3647 cost
+= address_cost (XEXP (rslt
, 0), TYPE_MODE (type
),
3648 TYPE_ADDR_SPACE (type
), speed
);
3649 else if (!REG_P (rslt
))
3650 cost
+= set_src_cost (rslt
, TYPE_MODE (type
), speed
);
3655 /* Returns variable containing the value of candidate CAND at statement AT. */
3658 var_at_stmt (struct loop
*loop
, struct iv_cand
*cand
, gimple
*stmt
)
3660 if (stmt_after_increment (loop
, cand
, stmt
))
3661 return cand
->var_after
;
3663 return cand
->var_before
;
3666 /* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
3667 same precision that is at least as wide as the precision of TYPE, stores
3668 BA to A and BB to B, and returns the type of BA. Otherwise, returns the
3672 determine_common_wider_type (tree
*a
, tree
*b
)
3674 tree wider_type
= NULL
;
3676 tree atype
= TREE_TYPE (*a
);
3678 if (CONVERT_EXPR_P (*a
))
3680 suba
= TREE_OPERAND (*a
, 0);
3681 wider_type
= TREE_TYPE (suba
);
3682 if (TYPE_PRECISION (wider_type
) < TYPE_PRECISION (atype
))
3688 if (CONVERT_EXPR_P (*b
))
3690 subb
= TREE_OPERAND (*b
, 0);
3691 if (TYPE_PRECISION (wider_type
) != TYPE_PRECISION (TREE_TYPE (subb
)))
3702 /* Determines the expression by that USE is expressed from induction variable
3703 CAND at statement AT in LOOP. The expression is stored in a decomposed
3704 form into AFF. Returns false if USE cannot be expressed using CAND. */
3707 get_computation_aff (struct loop
*loop
,
3708 struct iv_use
*use
, struct iv_cand
*cand
, gimple
*at
,
3709 struct aff_tree
*aff
)
3711 tree ubase
= use
->iv
->base
;
3712 tree ustep
= use
->iv
->step
;
3713 tree cbase
= cand
->iv
->base
;
3714 tree cstep
= cand
->iv
->step
, cstep_common
;
3715 tree utype
= TREE_TYPE (ubase
), ctype
= TREE_TYPE (cbase
);
3716 tree common_type
, var
;
3718 aff_tree cbase_aff
, var_aff
;
3721 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
3723 /* We do not have a precision to express the values of use. */
3727 var
= var_at_stmt (loop
, cand
, at
);
3728 uutype
= unsigned_type_for (utype
);
3730 /* If the conversion is not noop, perform it. */
3731 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
3733 if (cand
->orig_iv
!= NULL
&& CONVERT_EXPR_P (cbase
)
3734 && (CONVERT_EXPR_P (cstep
) || TREE_CODE (cstep
) == INTEGER_CST
))
3736 tree inner_base
, inner_step
, inner_type
;
3737 inner_base
= TREE_OPERAND (cbase
, 0);
3738 if (CONVERT_EXPR_P (cstep
))
3739 inner_step
= TREE_OPERAND (cstep
, 0);
3743 inner_type
= TREE_TYPE (inner_base
);
3744 /* If candidate is added from a biv whose type is smaller than
3745 ctype, we know both candidate and the biv won't overflow.
3746 In this case, it's safe to skip the convertion in candidate.
3747 As an example, (unsigned short)((unsigned long)A) equals to
3748 (unsigned short)A, if A has a type no larger than short. */
3749 if (TYPE_PRECISION (inner_type
) <= TYPE_PRECISION (uutype
))
3755 cstep
= fold_convert (uutype
, cstep
);
3756 cbase
= fold_convert (uutype
, cbase
);
3757 var
= fold_convert (uutype
, var
);
3760 /* Ratio is 1 when computing the value of biv cand by itself.
3761 We can't rely on constant_multiple_of in this case because the
3762 use is created after the original biv is selected. The call
3763 could fail because of inconsistent fold behavior. See PR68021
3764 for more information. */
3765 if (cand
->pos
== IP_ORIGINAL
&& cand
->incremented_at
== use
->stmt
)
3767 gcc_assert (is_gimple_assign (use
->stmt
));
3768 gcc_assert (use
->iv
->ssa_name
== cand
->var_after
);
3769 gcc_assert (gimple_assign_lhs (use
->stmt
) == cand
->var_after
);
3772 else if (!constant_multiple_of (ustep
, cstep
, &rat
))
3775 /* In case both UBASE and CBASE are shortened to UUTYPE from some common
3776 type, we achieve better folding by computing their difference in this
3777 wider type, and cast the result to UUTYPE. We do not need to worry about
3778 overflows, as all the arithmetics will in the end be performed in UUTYPE
3780 common_type
= determine_common_wider_type (&ubase
, &cbase
);
3782 /* use = ubase - ratio * cbase + ratio * var. */
3783 tree_to_aff_combination (ubase
, common_type
, aff
);
3784 tree_to_aff_combination (cbase
, common_type
, &cbase_aff
);
3785 tree_to_aff_combination (var
, uutype
, &var_aff
);
3787 /* We need to shift the value if we are after the increment. */
3788 if (stmt_after_increment (loop
, cand
, at
))
3792 if (common_type
!= uutype
)
3793 cstep_common
= fold_convert (common_type
, cstep
);
3795 cstep_common
= cstep
;
3797 tree_to_aff_combination (cstep_common
, common_type
, &cstep_aff
);
3798 aff_combination_add (&cbase_aff
, &cstep_aff
);
3801 aff_combination_scale (&cbase_aff
, -rat
);
3802 aff_combination_add (aff
, &cbase_aff
);
3803 if (common_type
!= uutype
)
3804 aff_combination_convert (aff
, uutype
);
3806 aff_combination_scale (&var_aff
, rat
);
3807 aff_combination_add (aff
, &var_aff
);
3812 /* Return the type of USE. */
3815 get_use_type (struct iv_use
*use
)
3817 tree base_type
= TREE_TYPE (use
->iv
->base
);
3820 if (use
->type
== USE_ADDRESS
)
3822 /* The base_type may be a void pointer. Create a pointer type based on
3823 the mem_ref instead. */
3824 type
= build_pointer_type (TREE_TYPE (*use
->op_p
));
3825 gcc_assert (TYPE_ADDR_SPACE (TREE_TYPE (type
))
3826 == TYPE_ADDR_SPACE (TREE_TYPE (base_type
)));
3834 /* Determines the expression by that USE is expressed from induction variable
3835 CAND at statement AT in LOOP. The computation is unshared. */
3838 get_computation_at (struct loop
*loop
,
3839 struct iv_use
*use
, struct iv_cand
*cand
, gimple
*at
)
3842 tree type
= get_use_type (use
);
3844 if (!get_computation_aff (loop
, use
, cand
, at
, &aff
))
3846 unshare_aff_combination (&aff
);
3847 return fold_convert (type
, aff_combination_to_tree (&aff
));
3850 /* Determines the expression by that USE is expressed from induction variable
3851 CAND in LOOP. The computation is unshared. */
3854 get_computation (struct loop
*loop
, struct iv_use
*use
, struct iv_cand
*cand
)
3856 return get_computation_at (loop
, use
, cand
, use
->stmt
);
3859 /* Adjust the cost COST for being in loop setup rather than loop body.
3860 If we're optimizing for space, the loop setup overhead is constant;
3861 if we're optimizing for speed, amortize it over the per-iteration cost. */
3863 adjust_setup_cost (struct ivopts_data
*data
, unsigned cost
)
3867 else if (optimize_loop_for_speed_p (data
->current_loop
))
3868 return cost
/ avg_loop_niter (data
->current_loop
);
3873 /* Returns true if multiplying by RATIO is allowed in an address. Test the
3874 validity for a memory reference accessing memory of mode MODE in
3875 address space AS. */
3879 multiplier_allowed_in_address_p (HOST_WIDE_INT ratio
, machine_mode mode
,
3882 #define MAX_RATIO 128
3883 unsigned int data_index
= (int) as
* MAX_MACHINE_MODE
+ (int) mode
;
3884 static vec
<sbitmap
> valid_mult_list
;
3887 if (data_index
>= valid_mult_list
.length ())
3888 valid_mult_list
.safe_grow_cleared (data_index
+ 1);
3890 valid_mult
= valid_mult_list
[data_index
];
3893 machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
3894 rtx reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
3895 rtx reg2
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 2);
3899 valid_mult
= sbitmap_alloc (2 * MAX_RATIO
+ 1);
3900 bitmap_clear (valid_mult
);
3901 scaled
= gen_rtx_fmt_ee (MULT
, address_mode
, reg1
, NULL_RTX
);
3902 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, scaled
, reg2
);
3903 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
3905 XEXP (scaled
, 1) = gen_int_mode (i
, address_mode
);
3906 if (memory_address_addr_space_p (mode
, addr
, as
)
3907 || memory_address_addr_space_p (mode
, scaled
, as
))
3908 bitmap_set_bit (valid_mult
, i
+ MAX_RATIO
);
3911 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3913 fprintf (dump_file
, " allowed multipliers:");
3914 for (i
= -MAX_RATIO
; i
<= MAX_RATIO
; i
++)
3915 if (bitmap_bit_p (valid_mult
, i
+ MAX_RATIO
))
3916 fprintf (dump_file
, " %d", (int) i
);
3917 fprintf (dump_file
, "\n");
3918 fprintf (dump_file
, "\n");
3921 valid_mult_list
[data_index
] = valid_mult
;
3924 if (ratio
> MAX_RATIO
|| ratio
< -MAX_RATIO
)
3927 return bitmap_bit_p (valid_mult
, ratio
+ MAX_RATIO
);
3930 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
3931 If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false,
3932 variable is omitted. Compute the cost for a memory reference that accesses
3933 a memory location of mode MEM_MODE in address space AS.
3935 MAY_AUTOINC is set to true if the autoincrement (increasing index by
3936 size of MEM_MODE / RATIO) is available. To make this determination, we
3937 look at the size of the increment to be made, which is given in CSTEP.
3938 CSTEP may be zero if the step is unknown.
3939 STMT_AFTER_INC is true iff the statement we're looking at is after the
3940 increment of the original biv.
3942 TODO -- there must be some better way. This all is quite crude. */
3946 AINC_PRE_INC
, /* Pre increment. */
3947 AINC_PRE_DEC
, /* Pre decrement. */
3948 AINC_POST_INC
, /* Post increment. */
3949 AINC_POST_DEC
, /* Post decrement. */
3950 AINC_NONE
/* Also the number of auto increment types. */
3953 struct address_cost_data
3955 HOST_WIDE_INT min_offset
, max_offset
;
3956 unsigned costs
[2][2][2][2];
3957 unsigned ainc_costs
[AINC_NONE
];
3962 get_address_cost (bool symbol_present
, bool var_present
,
3963 unsigned HOST_WIDE_INT offset
, HOST_WIDE_INT ratio
,
3964 HOST_WIDE_INT cstep
, machine_mode mem_mode
,
3965 addr_space_t as
, bool speed
,
3966 bool stmt_after_inc
, bool *may_autoinc
)
3968 machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
3969 static vec
<address_cost_data
*> address_cost_data_list
;
3970 unsigned int data_index
= (int) as
* MAX_MACHINE_MODE
+ (int) mem_mode
;
3971 address_cost_data
*data
;
3972 static bool has_preinc
[MAX_MACHINE_MODE
], has_postinc
[MAX_MACHINE_MODE
];
3973 static bool has_predec
[MAX_MACHINE_MODE
], has_postdec
[MAX_MACHINE_MODE
];
3974 unsigned cost
, acost
, complexity
;
3975 enum ainc_type autoinc_type
;
3976 bool offset_p
, ratio_p
, autoinc
;
3977 HOST_WIDE_INT s_offset
, autoinc_offset
, msize
;
3978 unsigned HOST_WIDE_INT mask
;
3981 if (data_index
>= address_cost_data_list
.length ())
3982 address_cost_data_list
.safe_grow_cleared (data_index
+ 1);
3984 data
= address_cost_data_list
[data_index
];
3988 HOST_WIDE_INT rat
, off
= 0;
3989 int old_cse_not_expected
, width
;
3990 unsigned sym_p
, var_p
, off_p
, rat_p
, add_c
;
3995 data
= (address_cost_data
*) xcalloc (1, sizeof (*data
));
3997 reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
3999 width
= GET_MODE_BITSIZE (address_mode
) - 1;
4000 if (width
> (HOST_BITS_PER_WIDE_INT
- 1))
4001 width
= HOST_BITS_PER_WIDE_INT
- 1;
4002 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, reg1
, NULL_RTX
);
4004 for (i
= width
; i
>= 0; i
--)
4006 off
= -((unsigned HOST_WIDE_INT
) 1 << i
);
4007 XEXP (addr
, 1) = gen_int_mode (off
, address_mode
);
4008 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
4011 data
->min_offset
= (i
== -1? 0 : off
);
4013 for (i
= width
; i
>= 0; i
--)
4015 off
= ((unsigned HOST_WIDE_INT
) 1 << i
) - 1;
4016 XEXP (addr
, 1) = gen_int_mode (off
, address_mode
);
4017 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
4019 /* For some strict-alignment targets, the offset must be naturally
4020 aligned. Try an aligned offset if mem_mode is not QImode. */
4021 off
= mem_mode
!= QImode
4022 ? ((unsigned HOST_WIDE_INT
) 1 << i
)
4023 - GET_MODE_SIZE (mem_mode
)
4027 XEXP (addr
, 1) = gen_int_mode (off
, address_mode
);
4028 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
4034 data
->max_offset
= off
;
4036 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4038 fprintf (dump_file
, "get_address_cost:\n");
4039 fprintf (dump_file
, " min offset %s " HOST_WIDE_INT_PRINT_DEC
"\n",
4040 GET_MODE_NAME (mem_mode
),
4042 fprintf (dump_file
, " max offset %s " HOST_WIDE_INT_PRINT_DEC
"\n",
4043 GET_MODE_NAME (mem_mode
),
4048 for (i
= 2; i
<= MAX_RATIO
; i
++)
4049 if (multiplier_allowed_in_address_p (i
, mem_mode
, as
))
4055 /* Compute the cost of various addressing modes. */
4057 reg0
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 1);
4058 reg1
= gen_raw_REG (address_mode
, LAST_VIRTUAL_REGISTER
+ 2);
4060 if (USE_LOAD_PRE_DECREMENT (mem_mode
)
4061 || USE_STORE_PRE_DECREMENT (mem_mode
))
4063 addr
= gen_rtx_PRE_DEC (address_mode
, reg0
);
4064 has_predec
[mem_mode
]
4065 = memory_address_addr_space_p (mem_mode
, addr
, as
);
4067 if (has_predec
[mem_mode
])
4068 data
->ainc_costs
[AINC_PRE_DEC
]
4069 = address_cost (addr
, mem_mode
, as
, speed
);
4071 if (USE_LOAD_POST_DECREMENT (mem_mode
)
4072 || USE_STORE_POST_DECREMENT (mem_mode
))
4074 addr
= gen_rtx_POST_DEC (address_mode
, reg0
);
4075 has_postdec
[mem_mode
]
4076 = memory_address_addr_space_p (mem_mode
, addr
, as
);
4078 if (has_postdec
[mem_mode
])
4079 data
->ainc_costs
[AINC_POST_DEC
]
4080 = address_cost (addr
, mem_mode
, as
, speed
);
4082 if (USE_LOAD_PRE_INCREMENT (mem_mode
)
4083 || USE_STORE_PRE_DECREMENT (mem_mode
))
4085 addr
= gen_rtx_PRE_INC (address_mode
, reg0
);
4086 has_preinc
[mem_mode
]
4087 = memory_address_addr_space_p (mem_mode
, addr
, as
);
4089 if (has_preinc
[mem_mode
])
4090 data
->ainc_costs
[AINC_PRE_INC
]
4091 = address_cost (addr
, mem_mode
, as
, speed
);
4093 if (USE_LOAD_POST_INCREMENT (mem_mode
)
4094 || USE_STORE_POST_INCREMENT (mem_mode
))
4096 addr
= gen_rtx_POST_INC (address_mode
, reg0
);
4097 has_postinc
[mem_mode
]
4098 = memory_address_addr_space_p (mem_mode
, addr
, as
);
4100 if (has_postinc
[mem_mode
])
4101 data
->ainc_costs
[AINC_POST_INC
]
4102 = address_cost (addr
, mem_mode
, as
, speed
);
4104 for (i
= 0; i
< 16; i
++)
4107 var_p
= (i
>> 1) & 1;
4108 off_p
= (i
>> 2) & 1;
4109 rat_p
= (i
>> 3) & 1;
4113 addr
= gen_rtx_fmt_ee (MULT
, address_mode
, addr
,
4114 gen_int_mode (rat
, address_mode
));
4117 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, addr
, reg1
);
4121 base
= gen_rtx_SYMBOL_REF (address_mode
, ggc_strdup (""));
4122 /* ??? We can run into trouble with some backends by presenting
4123 it with symbols which haven't been properly passed through
4124 targetm.encode_section_info. By setting the local bit, we
4125 enhance the probability of things working. */
4126 SYMBOL_REF_FLAGS (base
) = SYMBOL_FLAG_LOCAL
;
4129 base
= gen_rtx_fmt_e (CONST
, address_mode
,
4131 (PLUS
, address_mode
, base
,
4132 gen_int_mode (off
, address_mode
)));
4135 base
= gen_int_mode (off
, address_mode
);
4140 addr
= gen_rtx_fmt_ee (PLUS
, address_mode
, addr
, base
);
4143 /* To avoid splitting addressing modes, pretend that no cse will
4145 old_cse_not_expected
= cse_not_expected
;
4146 cse_not_expected
= true;
4147 addr
= memory_address_addr_space (mem_mode
, addr
, as
);
4148 cse_not_expected
= old_cse_not_expected
;
4152 acost
= seq_cost (seq
, speed
);
4153 acost
+= address_cost (addr
, mem_mode
, as
, speed
);
4157 data
->costs
[sym_p
][var_p
][off_p
][rat_p
] = acost
;
4160 /* On some targets, it is quite expensive to load symbol to a register,
4161 which makes addresses that contain symbols look much more expensive.
4162 However, the symbol will have to be loaded in any case before the
4163 loop (and quite likely we have it in register already), so it does not
4164 make much sense to penalize them too heavily. So make some final
4165 tweaks for the SYMBOL_PRESENT modes:
4167 If VAR_PRESENT is false, and the mode obtained by changing symbol to
4168 var is cheaper, use this mode with small penalty.
4169 If VAR_PRESENT is true, try whether the mode with
4170 SYMBOL_PRESENT = false is cheaper even with cost of addition, and
4171 if this is the case, use it. */
4172 add_c
= add_cost (speed
, address_mode
);
4173 for (i
= 0; i
< 8; i
++)
4176 off_p
= (i
>> 1) & 1;
4177 rat_p
= (i
>> 2) & 1;
4179 acost
= data
->costs
[0][1][off_p
][rat_p
] + 1;
4183 if (acost
< data
->costs
[1][var_p
][off_p
][rat_p
])
4184 data
->costs
[1][var_p
][off_p
][rat_p
] = acost
;
4187 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4189 fprintf (dump_file
, "<Address Costs>:\n");
4191 for (i
= 0; i
< 16; i
++)
4194 var_p
= (i
>> 1) & 1;
4195 off_p
= (i
>> 2) & 1;
4196 rat_p
= (i
>> 3) & 1;
4198 fprintf (dump_file
, " ");
4200 fprintf (dump_file
, "sym + ");
4202 fprintf (dump_file
, "var + ");
4204 fprintf (dump_file
, "cst + ");
4206 fprintf (dump_file
, "rat * ");
4208 acost
= data
->costs
[sym_p
][var_p
][off_p
][rat_p
];
4209 fprintf (dump_file
, "index costs %d\n", acost
);
4211 if (has_predec
[mem_mode
] || has_postdec
[mem_mode
]
4212 || has_preinc
[mem_mode
] || has_postinc
[mem_mode
])
4213 fprintf (dump_file
, " May include autoinc/dec\n");
4214 fprintf (dump_file
, "\n");
4217 address_cost_data_list
[data_index
] = data
;
4220 bits
= GET_MODE_BITSIZE (address_mode
);
4221 mask
= ~(~(unsigned HOST_WIDE_INT
) 0 << (bits
- 1) << 1);
4223 if ((offset
>> (bits
- 1) & 1))
4228 autoinc_type
= AINC_NONE
;
4229 msize
= GET_MODE_SIZE (mem_mode
);
4230 autoinc_offset
= offset
;
4232 autoinc_offset
+= ratio
* cstep
;
4233 if (symbol_present
|| var_present
|| ratio
!= 1)
4237 if (has_postinc
[mem_mode
] && autoinc_offset
== 0
4239 autoinc_type
= AINC_POST_INC
;
4240 else if (has_postdec
[mem_mode
] && autoinc_offset
== 0
4242 autoinc_type
= AINC_POST_DEC
;
4243 else if (has_preinc
[mem_mode
] && autoinc_offset
== msize
4245 autoinc_type
= AINC_PRE_INC
;
4246 else if (has_predec
[mem_mode
] && autoinc_offset
== -msize
4248 autoinc_type
= AINC_PRE_DEC
;
4250 if (autoinc_type
!= AINC_NONE
)
4255 offset_p
= (s_offset
!= 0
4256 && data
->min_offset
<= s_offset
4257 && s_offset
<= data
->max_offset
);
4258 ratio_p
= (ratio
!= 1
4259 && multiplier_allowed_in_address_p (ratio
, mem_mode
, as
));
4261 if (ratio
!= 1 && !ratio_p
)
4262 cost
+= mult_by_coeff_cost (ratio
, address_mode
, speed
);
4264 if (s_offset
&& !offset_p
&& !symbol_present
)
4265 cost
+= add_cost (speed
, address_mode
);
4268 *may_autoinc
= autoinc
;
4270 acost
= data
->ainc_costs
[autoinc_type
];
4272 acost
= data
->costs
[symbol_present
][var_present
][offset_p
][ratio_p
];
4273 complexity
= (symbol_present
!= 0) + (var_present
!= 0) + offset_p
+ ratio_p
;
4274 return comp_cost (cost
+ acost
, complexity
);
4277 /* Calculate the SPEED or size cost of shiftadd EXPR in MODE. MULT is the
4278 EXPR operand holding the shift. COST0 and COST1 are the costs for
4279 calculating the operands of EXPR. Returns true if successful, and returns
4280 the cost in COST. */
4283 get_shiftadd_cost (tree expr
, machine_mode mode
, comp_cost cost0
,
4284 comp_cost cost1
, tree mult
, bool speed
, comp_cost
*cost
)
4287 tree op1
= TREE_OPERAND (expr
, 1);
4288 tree cst
= TREE_OPERAND (mult
, 1);
4289 tree multop
= TREE_OPERAND (mult
, 0);
4290 int m
= exact_log2 (int_cst_value (cst
));
4291 int maxm
= MIN (BITS_PER_WORD
, GET_MODE_BITSIZE (mode
));
4292 int as_cost
, sa_cost
;
4295 if (!(m
>= 0 && m
< maxm
))
4299 mult_in_op1
= operand_equal_p (op1
, mult
, 0);
4301 as_cost
= add_cost (speed
, mode
) + shift_cost (speed
, mode
, m
);
4303 /* If the target has a cheap shift-and-add or shift-and-sub instruction,
4304 use that in preference to a shift insn followed by an add insn. */
4305 sa_cost
= (TREE_CODE (expr
) != MINUS_EXPR
4306 ? shiftadd_cost (speed
, mode
, m
)
4308 ? shiftsub1_cost (speed
, mode
, m
)
4309 : shiftsub0_cost (speed
, mode
, m
)));
4311 res
= comp_cost (MIN (as_cost
, sa_cost
), 0);
4312 res
+= (mult_in_op1
? cost0
: cost1
);
4314 STRIP_NOPS (multop
);
4315 if (!is_gimple_val (multop
))
4316 res
+= force_expr_to_var_cost (multop
, speed
);
4322 /* Estimates cost of forcing expression EXPR into a variable. */
4325 force_expr_to_var_cost (tree expr
, bool speed
)
4327 static bool costs_initialized
= false;
4328 static unsigned integer_cost
[2];
4329 static unsigned symbol_cost
[2];
4330 static unsigned address_cost
[2];
4332 comp_cost cost0
, cost1
, cost
;
4335 if (!costs_initialized
)
4337 tree type
= build_pointer_type (integer_type_node
);
4342 var
= create_tmp_var_raw (integer_type_node
, "test_var");
4343 TREE_STATIC (var
) = 1;
4344 x
= produce_memory_decl_rtl (var
, NULL
);
4345 SET_DECL_RTL (var
, x
);
4347 addr
= build1 (ADDR_EXPR
, type
, var
);
4350 for (i
= 0; i
< 2; i
++)
4352 integer_cost
[i
] = computation_cost (build_int_cst (integer_type_node
,
4355 symbol_cost
[i
] = computation_cost (addr
, i
) + 1;
4358 = computation_cost (fold_build_pointer_plus_hwi (addr
, 2000), i
) + 1;
4359 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4361 fprintf (dump_file
, "force_expr_to_var_cost %s costs:\n", i
? "speed" : "size");
4362 fprintf (dump_file
, " integer %d\n", (int) integer_cost
[i
]);
4363 fprintf (dump_file
, " symbol %d\n", (int) symbol_cost
[i
]);
4364 fprintf (dump_file
, " address %d\n", (int) address_cost
[i
]);
4365 fprintf (dump_file
, " other %d\n", (int) target_spill_cost
[i
]);
4366 fprintf (dump_file
, "\n");
4370 costs_initialized
= true;
4375 if (SSA_VAR_P (expr
))
4378 if (is_gimple_min_invariant (expr
))
4380 if (TREE_CODE (expr
) == INTEGER_CST
)
4381 return comp_cost (integer_cost
[speed
], 0);
4383 if (TREE_CODE (expr
) == ADDR_EXPR
)
4385 tree obj
= TREE_OPERAND (expr
, 0);
4387 if (TREE_CODE (obj
) == VAR_DECL
4388 || TREE_CODE (obj
) == PARM_DECL
4389 || TREE_CODE (obj
) == RESULT_DECL
)
4390 return comp_cost (symbol_cost
[speed
], 0);
4393 return comp_cost (address_cost
[speed
], 0);
4396 switch (TREE_CODE (expr
))
4398 case POINTER_PLUS_EXPR
:
4402 op0
= TREE_OPERAND (expr
, 0);
4403 op1
= TREE_OPERAND (expr
, 1);
4410 op0
= TREE_OPERAND (expr
, 0);
4416 /* Just an arbitrary value, FIXME. */
4417 return comp_cost (target_spill_cost
[speed
], 0);
4420 if (op0
== NULL_TREE
4421 || TREE_CODE (op0
) == SSA_NAME
|| CONSTANT_CLASS_P (op0
))
4424 cost0
= force_expr_to_var_cost (op0
, speed
);
4426 if (op1
== NULL_TREE
4427 || TREE_CODE (op1
) == SSA_NAME
|| CONSTANT_CLASS_P (op1
))
4430 cost1
= force_expr_to_var_cost (op1
, speed
);
4432 mode
= TYPE_MODE (TREE_TYPE (expr
));
4433 switch (TREE_CODE (expr
))
4435 case POINTER_PLUS_EXPR
:
4439 cost
= comp_cost (add_cost (speed
, mode
), 0);
4440 if (TREE_CODE (expr
) != NEGATE_EXPR
)
4442 tree mult
= NULL_TREE
;
4444 if (TREE_CODE (op1
) == MULT_EXPR
)
4446 else if (TREE_CODE (op0
) == MULT_EXPR
)
4449 if (mult
!= NULL_TREE
4450 && cst_and_fits_in_hwi (TREE_OPERAND (mult
, 1))
4451 && get_shiftadd_cost (expr
, mode
, cost0
, cost1
, mult
,
4459 tree inner_mode
, outer_mode
;
4460 outer_mode
= TREE_TYPE (expr
);
4461 inner_mode
= TREE_TYPE (op0
);
4462 cost
= comp_cost (convert_cost (TYPE_MODE (outer_mode
),
4463 TYPE_MODE (inner_mode
), speed
), 0);
4468 if (cst_and_fits_in_hwi (op0
))
4469 cost
= comp_cost (mult_by_coeff_cost (int_cst_value (op0
),
4471 else if (cst_and_fits_in_hwi (op1
))
4472 cost
= comp_cost (mult_by_coeff_cost (int_cst_value (op1
),
4475 return comp_cost (target_spill_cost
[speed
], 0);
4485 /* Bound the cost by target_spill_cost. The parts of complicated
4486 computations often are either loop invariant or at least can
4487 be shared between several iv uses, so letting this grow without
4488 limits would not give reasonable results. */
4489 if (cost
.cost
> (int) target_spill_cost
[speed
])
4490 cost
.cost
= target_spill_cost
[speed
];
4495 /* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
4496 invariants the computation depends on. */
4499 force_var_cost (struct ivopts_data
*data
,
4500 tree expr
, bitmap
*depends_on
)
4504 fd_ivopts_data
= data
;
4505 walk_tree (&expr
, find_depends
, depends_on
, NULL
);
4508 return force_expr_to_var_cost (expr
, data
->speed
);
4511 /* Estimates cost of expressing address ADDR as var + symbol + offset. The
4512 value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
4513 to false if the corresponding part is missing. DEPENDS_ON is a set of the
4514 invariants the computation depends on. */
4517 split_address_cost (struct ivopts_data
*data
,
4518 tree addr
, bool *symbol_present
, bool *var_present
,
4519 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
4522 HOST_WIDE_INT bitsize
;
4523 HOST_WIDE_INT bitpos
;
4526 int unsignedp
, reversep
, volatilep
;
4528 core
= get_inner_reference (addr
, &bitsize
, &bitpos
, &toffset
, &mode
,
4529 &unsignedp
, &reversep
, &volatilep
);
4532 || bitpos
% BITS_PER_UNIT
!= 0
4534 || TREE_CODE (core
) != VAR_DECL
)
4536 *symbol_present
= false;
4537 *var_present
= true;
4538 fd_ivopts_data
= data
;
4540 walk_tree (&addr
, find_depends
, depends_on
, NULL
);
4542 return comp_cost (target_spill_cost
[data
->speed
], 0);
4545 *offset
+= bitpos
/ BITS_PER_UNIT
;
4546 if (TREE_STATIC (core
)
4547 || DECL_EXTERNAL (core
))
4549 *symbol_present
= true;
4550 *var_present
= false;
4554 *symbol_present
= false;
4555 *var_present
= true;
4559 /* Estimates cost of expressing difference of addresses E1 - E2 as
4560 var + symbol + offset. The value of offset is added to OFFSET,
4561 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
4562 part is missing. DEPENDS_ON is a set of the invariants the computation
4566 ptr_difference_cost (struct ivopts_data
*data
,
4567 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
4568 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
4570 HOST_WIDE_INT diff
= 0;
4571 aff_tree aff_e1
, aff_e2
;
4574 gcc_assert (TREE_CODE (e1
) == ADDR_EXPR
);
4576 if (ptr_difference_const (e1
, e2
, &diff
))
4579 *symbol_present
= false;
4580 *var_present
= false;
4584 if (integer_zerop (e2
))
4585 return split_address_cost (data
, TREE_OPERAND (e1
, 0),
4586 symbol_present
, var_present
, offset
, depends_on
);
4588 *symbol_present
= false;
4589 *var_present
= true;
4591 type
= signed_type_for (TREE_TYPE (e1
));
4592 tree_to_aff_combination (e1
, type
, &aff_e1
);
4593 tree_to_aff_combination (e2
, type
, &aff_e2
);
4594 aff_combination_scale (&aff_e2
, -1);
4595 aff_combination_add (&aff_e1
, &aff_e2
);
4597 return force_var_cost (data
, aff_combination_to_tree (&aff_e1
), depends_on
);
4600 /* Estimates cost of expressing difference E1 - E2 as
4601 var + symbol + offset. The value of offset is added to OFFSET,
4602 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
4603 part is missing. DEPENDS_ON is a set of the invariants the computation
4607 difference_cost (struct ivopts_data
*data
,
4608 tree e1
, tree e2
, bool *symbol_present
, bool *var_present
,
4609 unsigned HOST_WIDE_INT
*offset
, bitmap
*depends_on
)
4611 machine_mode mode
= TYPE_MODE (TREE_TYPE (e1
));
4612 unsigned HOST_WIDE_INT off1
, off2
;
4613 aff_tree aff_e1
, aff_e2
;
4616 e1
= strip_offset (e1
, &off1
);
4617 e2
= strip_offset (e2
, &off2
);
4618 *offset
+= off1
- off2
;
4623 if (TREE_CODE (e1
) == ADDR_EXPR
)
4624 return ptr_difference_cost (data
, e1
, e2
, symbol_present
, var_present
,
4625 offset
, depends_on
);
4626 *symbol_present
= false;
4628 if (operand_equal_p (e1
, e2
, 0))
4630 *var_present
= false;
4634 *var_present
= true;
4636 if (integer_zerop (e2
))
4637 return force_var_cost (data
, e1
, depends_on
);
4639 if (integer_zerop (e1
))
4641 comp_cost cost
= force_var_cost (data
, e2
, depends_on
);
4642 cost
+= mult_by_coeff_cost (-1, mode
, data
->speed
);
4646 type
= signed_type_for (TREE_TYPE (e1
));
4647 tree_to_aff_combination (e1
, type
, &aff_e1
);
4648 tree_to_aff_combination (e2
, type
, &aff_e2
);
4649 aff_combination_scale (&aff_e2
, -1);
4650 aff_combination_add (&aff_e1
, &aff_e2
);
4652 return force_var_cost (data
, aff_combination_to_tree (&aff_e1
), depends_on
);
4655 /* Returns true if AFF1 and AFF2 are identical. */
4658 compare_aff_trees (aff_tree
*aff1
, aff_tree
*aff2
)
4662 if (aff1
->n
!= aff2
->n
)
4665 for (i
= 0; i
< aff1
->n
; i
++)
4667 if (aff1
->elts
[i
].coef
!= aff2
->elts
[i
].coef
)
4670 if (!operand_equal_p (aff1
->elts
[i
].val
, aff2
->elts
[i
].val
, 0))
4676 /* Stores EXPR in DATA->inv_expr_tab, return pointer to iv_inv_expr_ent. */
4678 static iv_inv_expr_ent
*
4679 record_inv_expr (struct ivopts_data
*data
, tree expr
)
4681 struct iv_inv_expr_ent ent
;
4682 struct iv_inv_expr_ent
**slot
;
4685 ent
.hash
= iterative_hash_expr (expr
, 0);
4686 slot
= data
->inv_expr_tab
->find_slot (&ent
, INSERT
);
4690 *slot
= XNEW (struct iv_inv_expr_ent
);
4691 (*slot
)->expr
= expr
;
4692 (*slot
)->hash
= ent
.hash
;
4693 (*slot
)->id
= data
->max_inv_expr_id
++;
4699 /* Returns the invariant expression if expression UBASE - RATIO * CBASE
4700 requires a new compiler generated temporary. Returns -1 otherwise.
4701 ADDRESS_P is a flag indicating if the expression is for address
4704 static iv_inv_expr_ent
*
4705 get_loop_invariant_expr (struct ivopts_data
*data
, tree ubase
,
4706 tree cbase
, HOST_WIDE_INT ratio
,
4709 aff_tree ubase_aff
, cbase_aff
;
4717 if ((TREE_CODE (ubase
) == INTEGER_CST
)
4718 && (TREE_CODE (cbase
) == INTEGER_CST
))
4721 /* Strips the constant part. */
4722 if (TREE_CODE (ubase
) == PLUS_EXPR
4723 || TREE_CODE (ubase
) == MINUS_EXPR
4724 || TREE_CODE (ubase
) == POINTER_PLUS_EXPR
)
4726 if (TREE_CODE (TREE_OPERAND (ubase
, 1)) == INTEGER_CST
)
4727 ubase
= TREE_OPERAND (ubase
, 0);
4730 /* Strips the constant part. */
4731 if (TREE_CODE (cbase
) == PLUS_EXPR
4732 || TREE_CODE (cbase
) == MINUS_EXPR
4733 || TREE_CODE (cbase
) == POINTER_PLUS_EXPR
)
4735 if (TREE_CODE (TREE_OPERAND (cbase
, 1)) == INTEGER_CST
)
4736 cbase
= TREE_OPERAND (cbase
, 0);
4741 if (((TREE_CODE (ubase
) == SSA_NAME
)
4742 || (TREE_CODE (ubase
) == ADDR_EXPR
4743 && is_gimple_min_invariant (ubase
)))
4744 && (TREE_CODE (cbase
) == INTEGER_CST
))
4747 if (((TREE_CODE (cbase
) == SSA_NAME
)
4748 || (TREE_CODE (cbase
) == ADDR_EXPR
4749 && is_gimple_min_invariant (cbase
)))
4750 && (TREE_CODE (ubase
) == INTEGER_CST
))
4756 if (operand_equal_p (ubase
, cbase
, 0))
4759 if (TREE_CODE (ubase
) == ADDR_EXPR
4760 && TREE_CODE (cbase
) == ADDR_EXPR
)
4764 usym
= TREE_OPERAND (ubase
, 0);
4765 csym
= TREE_OPERAND (cbase
, 0);
4766 if (TREE_CODE (usym
) == ARRAY_REF
)
4768 tree ind
= TREE_OPERAND (usym
, 1);
4769 if (TREE_CODE (ind
) == INTEGER_CST
4770 && tree_fits_shwi_p (ind
)
4771 && tree_to_shwi (ind
) == 0)
4772 usym
= TREE_OPERAND (usym
, 0);
4774 if (TREE_CODE (csym
) == ARRAY_REF
)
4776 tree ind
= TREE_OPERAND (csym
, 1);
4777 if (TREE_CODE (ind
) == INTEGER_CST
4778 && tree_fits_shwi_p (ind
)
4779 && tree_to_shwi (ind
) == 0)
4780 csym
= TREE_OPERAND (csym
, 0);
4782 if (operand_equal_p (usym
, csym
, 0))
4785 /* Now do more complex comparison */
4786 tree_to_aff_combination (ubase
, TREE_TYPE (ubase
), &ubase_aff
);
4787 tree_to_aff_combination (cbase
, TREE_TYPE (cbase
), &cbase_aff
);
4788 if (compare_aff_trees (&ubase_aff
, &cbase_aff
))
4792 tree_to_aff_combination (ub
, TREE_TYPE (ub
), &ubase_aff
);
4793 tree_to_aff_combination (cb
, TREE_TYPE (cb
), &cbase_aff
);
4795 aff_combination_scale (&cbase_aff
, -1 * ratio
);
4796 aff_combination_add (&ubase_aff
, &cbase_aff
);
4797 expr
= aff_combination_to_tree (&ubase_aff
);
4798 return record_inv_expr (data
, expr
);
4801 /* Scale (multiply) the computed COST (except scratch part that should be
4802 hoisted out a loop) by header->frequency / AT->frequency,
4803 which makes expected cost more accurate. */
4806 get_scaled_computation_cost_at (ivopts_data
*data
, gimple
*at
, iv_cand
*cand
,
4809 int loop_freq
= data
->current_loop
->header
->frequency
;
4810 int bb_freq
= at
->bb
->frequency
;
4813 gcc_assert (cost
.scratch
<= cost
.cost
);
4815 = cost
.scratch
+ (cost
.cost
- cost
.scratch
) * bb_freq
/ loop_freq
;
4817 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4818 fprintf (dump_file
, "Scaling iv_use based on cand %d "
4819 "by %2.2f: %d (scratch: %d) -> %d (%d/%d)\n",
4820 cand
->id
, 1.0f
* bb_freq
/ loop_freq
, cost
.cost
,
4821 cost
.scratch
, scaled_cost
, bb_freq
, loop_freq
);
4823 cost
.cost
= scaled_cost
;
4829 /* Determines the cost of the computation by that USE is expressed
4830 from induction variable CAND. If ADDRESS_P is true, we just need
4831 to create an address from it, otherwise we want to get it into
4832 register. A set of invariants we depend on is stored in
4833 DEPENDS_ON. AT is the statement at that the value is computed.
4834 If CAN_AUTOINC is nonnull, use it to record whether autoinc
4835 addressing is likely. */
4838 get_computation_cost_at (struct ivopts_data
*data
,
4839 struct iv_use
*use
, struct iv_cand
*cand
,
4840 bool address_p
, bitmap
*depends_on
, gimple
*at
,
4842 iv_inv_expr_ent
**inv_expr
)
4844 tree ubase
= use
->iv
->base
, ustep
= use
->iv
->step
;
4846 tree utype
= TREE_TYPE (ubase
), ctype
;
4847 unsigned HOST_WIDE_INT cstepi
, offset
= 0;
4848 HOST_WIDE_INT ratio
, aratio
;
4849 bool var_present
, symbol_present
, stmt_is_after_inc
;
4852 bool speed
= optimize_bb_for_speed_p (gimple_bb (at
));
4853 machine_mode mem_mode
= (address_p
4854 ? TYPE_MODE (TREE_TYPE (*use
->op_p
))
4860 /* Only consider real candidates. */
4862 return infinite_cost
;
4864 cbase
= cand
->iv
->base
;
4865 cstep
= cand
->iv
->step
;
4866 ctype
= TREE_TYPE (cbase
);
4868 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
4870 /* We do not have a precision to express the values of use. */
4871 return infinite_cost
;
4875 || (use
->iv
->base_object
4876 && cand
->iv
->base_object
4877 && POINTER_TYPE_P (TREE_TYPE (use
->iv
->base_object
))
4878 && POINTER_TYPE_P (TREE_TYPE (cand
->iv
->base_object
))))
4880 /* Do not try to express address of an object with computation based
4881 on address of a different object. This may cause problems in rtl
4882 level alias analysis (that does not expect this to be happening,
4883 as this is illegal in C), and would be unlikely to be useful
4885 if (use
->iv
->base_object
4886 && cand
->iv
->base_object
4887 && !operand_equal_p (use
->iv
->base_object
, cand
->iv
->base_object
, 0))
4888 return infinite_cost
;
4891 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
4893 /* TODO -- add direct handling of this case. */
4897 /* CSTEPI is removed from the offset in case statement is after the
4898 increment. If the step is not constant, we use zero instead.
4899 This is a bit imprecise (there is the extra addition), but
4900 redundancy elimination is likely to transform the code so that
4901 it uses value of the variable before increment anyway,
4902 so it is not that much unrealistic. */
4903 if (cst_and_fits_in_hwi (cstep
))
4904 cstepi
= int_cst_value (cstep
);
4908 if (!constant_multiple_of (ustep
, cstep
, &rat
))
4909 return infinite_cost
;
4911 if (wi::fits_shwi_p (rat
))
4912 ratio
= rat
.to_shwi ();
4914 return infinite_cost
;
4917 ctype
= TREE_TYPE (cbase
);
4919 stmt_is_after_inc
= stmt_after_increment (data
->current_loop
, cand
, at
);
4921 /* use = ubase + ratio * (var - cbase). If either cbase is a constant
4922 or ratio == 1, it is better to handle this like
4924 ubase - ratio * cbase + ratio * var
4926 (also holds in the case ratio == -1, TODO. */
4928 if (cst_and_fits_in_hwi (cbase
))
4930 offset
= - ratio
* (unsigned HOST_WIDE_INT
) int_cst_value (cbase
);
4931 cost
= difference_cost (data
,
4932 ubase
, build_int_cst (utype
, 0),
4933 &symbol_present
, &var_present
, &offset
,
4935 cost
/= avg_loop_niter (data
->current_loop
);
4937 else if (ratio
== 1)
4939 tree real_cbase
= cbase
;
4941 /* Check to see if any adjustment is needed. */
4942 if (cstepi
== 0 && stmt_is_after_inc
)
4944 aff_tree real_cbase_aff
;
4947 tree_to_aff_combination (cbase
, TREE_TYPE (real_cbase
),
4949 tree_to_aff_combination (cstep
, TREE_TYPE (cstep
), &cstep_aff
);
4951 aff_combination_add (&real_cbase_aff
, &cstep_aff
);
4952 real_cbase
= aff_combination_to_tree (&real_cbase_aff
);
4955 cost
= difference_cost (data
,
4957 &symbol_present
, &var_present
, &offset
,
4959 cost
/= avg_loop_niter (data
->current_loop
);
4962 && !POINTER_TYPE_P (ctype
)
4963 && multiplier_allowed_in_address_p
4965 TYPE_ADDR_SPACE (TREE_TYPE (utype
))))
4967 tree real_cbase
= cbase
;
4969 if (cstepi
== 0 && stmt_is_after_inc
)
4971 if (POINTER_TYPE_P (ctype
))
4972 real_cbase
= fold_build2 (POINTER_PLUS_EXPR
, ctype
, cbase
, cstep
);
4974 real_cbase
= fold_build2 (PLUS_EXPR
, ctype
, cbase
, cstep
);
4976 real_cbase
= fold_build2 (MULT_EXPR
, ctype
, real_cbase
,
4977 build_int_cst (ctype
, ratio
));
4978 cost
= difference_cost (data
,
4980 &symbol_present
, &var_present
, &offset
,
4982 cost
/= avg_loop_niter (data
->current_loop
);
4986 cost
= force_var_cost (data
, cbase
, depends_on
);
4987 cost
+= difference_cost (data
, ubase
, build_int_cst (utype
, 0),
4988 &symbol_present
, &var_present
, &offset
,
4990 cost
/= avg_loop_niter (data
->current_loop
);
4991 cost
+= add_cost (data
->speed
, TYPE_MODE (ctype
));
4994 /* Record setup cost in scratch field. */
4995 cost
.scratch
= cost
.cost
;
4997 if (inv_expr
&& depends_on
&& *depends_on
)
4999 *inv_expr
= get_loop_invariant_expr (data
, ubase
, cbase
, ratio
,
5001 /* Clear depends on. */
5002 if (*inv_expr
!= NULL
)
5003 bitmap_clear (*depends_on
);
5006 /* If we are after the increment, the value of the candidate is higher by
5008 if (stmt_is_after_inc
)
5009 offset
-= ratio
* cstepi
;
5011 /* Now the computation is in shape symbol + var1 + const + ratio * var2.
5012 (symbol/var1/const parts may be omitted). If we are looking for an
5013 address, find the cost of addressing this. */
5016 cost
+= get_address_cost (symbol_present
, var_present
,
5017 offset
, ratio
, cstepi
,
5019 TYPE_ADDR_SPACE (TREE_TYPE (utype
)),
5020 speed
, stmt_is_after_inc
, can_autoinc
);
5021 return get_scaled_computation_cost_at (data
, at
, cand
, cost
);
5024 /* Otherwise estimate the costs for computing the expression. */
5025 if (!symbol_present
&& !var_present
&& !offset
)
5028 cost
+= mult_by_coeff_cost (ratio
, TYPE_MODE (ctype
), speed
);
5029 return get_scaled_computation_cost_at (data
, at
, cand
, cost
);
5032 /* Symbol + offset should be compile-time computable so consider that they
5033 are added once to the variable, if present. */
5034 if (var_present
&& (symbol_present
|| offset
))
5035 cost
+= adjust_setup_cost (data
,
5036 add_cost (speed
, TYPE_MODE (ctype
)));
5038 /* Having offset does not affect runtime cost in case it is added to
5039 symbol, but it increases complexity. */
5043 cost
+= add_cost (speed
, TYPE_MODE (ctype
));
5045 aratio
= ratio
> 0 ? ratio
: -ratio
;
5047 cost
+= mult_by_coeff_cost (aratio
, TYPE_MODE (ctype
), speed
);
5049 return get_scaled_computation_cost_at (data
, at
, cand
, cost
);
5053 *can_autoinc
= false;
5055 /* Just get the expression, expand it and measure the cost. */
5056 tree comp
= get_computation_at (data
->current_loop
, use
, cand
, at
);
5059 return infinite_cost
;
5062 comp
= build_simple_mem_ref (comp
);
5064 cost
= comp_cost (computation_cost (comp
, speed
), 0);
5066 return get_scaled_computation_cost_at (data
, at
, cand
, cost
);
5069 /* Determines the cost of the computation by that USE is expressed
5070 from induction variable CAND. If ADDRESS_P is true, we just need
5071 to create an address from it, otherwise we want to get it into
5072 register. A set of invariants we depend on is stored in
5073 DEPENDS_ON. If CAN_AUTOINC is nonnull, use it to record whether
5074 autoinc addressing is likely. */
5077 get_computation_cost (struct ivopts_data
*data
,
5078 struct iv_use
*use
, struct iv_cand
*cand
,
5079 bool address_p
, bitmap
*depends_on
,
5080 bool *can_autoinc
, iv_inv_expr_ent
**inv_expr
)
5082 return get_computation_cost_at (data
,
5083 use
, cand
, address_p
, depends_on
, use
->stmt
,
5084 can_autoinc
, inv_expr
);
5087 /* Determines cost of computing the use in GROUP with CAND in a generic
5091 determine_group_iv_cost_generic (struct ivopts_data
*data
,
5092 struct iv_group
*group
, struct iv_cand
*cand
)
5095 iv_inv_expr_ent
*inv_expr
= NULL
;
5096 bitmap depends_on
= NULL
;
5097 struct iv_use
*use
= group
->vuses
[0];
5099 /* The simple case first -- if we need to express value of the preserved
5100 original biv, the cost is 0. This also prevents us from counting the
5101 cost of increment twice -- once at this use and once in the cost of
5103 if (cand
->pos
== IP_ORIGINAL
&& cand
->incremented_at
== use
->stmt
)
5106 cost
= get_computation_cost (data
, use
, cand
, false,
5107 &depends_on
, NULL
, &inv_expr
);
5109 set_group_iv_cost (data
, group
, cand
, cost
, depends_on
,
5110 NULL_TREE
, ERROR_MARK
, inv_expr
);
5111 return !cost
.infinite_cost_p ();
5114 /* Determines cost of computing uses in GROUP with CAND in addresses. */
5117 determine_group_iv_cost_address (struct ivopts_data
*data
,
5118 struct iv_group
*group
, struct iv_cand
*cand
)
5123 iv_inv_expr_ent
*inv_expr
= NULL
;
5124 struct iv_use
*use
= group
->vuses
[0];
5125 comp_cost sum_cost
= no_cost
, cost
;
5127 cost
= get_computation_cost (data
, use
, cand
, true,
5128 &depends_on
, &can_autoinc
, &inv_expr
);
5131 if (!sum_cost
.infinite_cost_p () && cand
->ainc_use
== use
)
5134 sum_cost
-= cand
->cost_step
;
5135 /* If we generated the candidate solely for exploiting autoincrement
5136 opportunities, and it turns out it can't be used, set the cost to
5137 infinity to make sure we ignore it. */
5138 else if (cand
->pos
== IP_AFTER_USE
|| cand
->pos
== IP_BEFORE_USE
)
5139 sum_cost
= infinite_cost
;
5142 /* Uses in a group can share setup code, so only add setup cost once. */
5143 cost
-= cost
.scratch
;
5144 /* Compute and add costs for rest uses of this group. */
5145 for (i
= 1; i
< group
->vuses
.length () && !sum_cost
.infinite_cost_p (); i
++)
5147 struct iv_use
*next
= group
->vuses
[i
];
5149 /* TODO: We could skip computing cost for sub iv_use when it has the
5150 same cost as the first iv_use, but the cost really depends on the
5151 offset and where the iv_use is. */
5152 cost
= get_computation_cost (data
, next
, cand
, true,
5153 NULL
, &can_autoinc
, NULL
);
5156 set_group_iv_cost (data
, group
, cand
, sum_cost
, depends_on
,
5157 NULL_TREE
, ERROR_MARK
, inv_expr
);
5159 return !sum_cost
.infinite_cost_p ();
5162 /* Computes value of candidate CAND at position AT in iteration NITER, and
5163 stores it to VAL. */
5166 cand_value_at (struct loop
*loop
, struct iv_cand
*cand
, gimple
*at
, tree niter
,
5169 aff_tree step
, delta
, nit
;
5170 struct iv
*iv
= cand
->iv
;
5171 tree type
= TREE_TYPE (iv
->base
);
5172 tree steptype
= type
;
5173 if (POINTER_TYPE_P (type
))
5174 steptype
= sizetype
;
5175 steptype
= unsigned_type_for (type
);
5177 tree_to_aff_combination (iv
->step
, TREE_TYPE (iv
->step
), &step
);
5178 aff_combination_convert (&step
, steptype
);
5179 tree_to_aff_combination (niter
, TREE_TYPE (niter
), &nit
);
5180 aff_combination_convert (&nit
, steptype
);
5181 aff_combination_mult (&nit
, &step
, &delta
);
5182 if (stmt_after_increment (loop
, cand
, at
))
5183 aff_combination_add (&delta
, &step
);
5185 tree_to_aff_combination (iv
->base
, type
, val
);
5186 if (!POINTER_TYPE_P (type
))
5187 aff_combination_convert (val
, steptype
);
5188 aff_combination_add (val
, &delta
);
5191 /* Returns period of induction variable iv. */
5194 iv_period (struct iv
*iv
)
5196 tree step
= iv
->step
, period
, type
;
5199 gcc_assert (step
&& TREE_CODE (step
) == INTEGER_CST
);
5201 type
= unsigned_type_for (TREE_TYPE (step
));
5202 /* Period of the iv is lcm (step, type_range)/step -1,
5203 i.e., N*type_range/step - 1. Since type range is power
5204 of two, N == (step >> num_of_ending_zeros_binary (step),
5205 so the final result is
5207 (type_range >> num_of_ending_zeros_binary (step)) - 1
5210 pow2div
= num_ending_zeros (step
);
5212 period
= build_low_bits_mask (type
,
5213 (TYPE_PRECISION (type
)
5214 - tree_to_uhwi (pow2div
)));
5219 /* Returns the comparison operator used when eliminating the iv USE. */
5221 static enum tree_code
5222 iv_elimination_compare (struct ivopts_data
*data
, struct iv_use
*use
)
5224 struct loop
*loop
= data
->current_loop
;
5228 ex_bb
= gimple_bb (use
->stmt
);
5229 exit
= EDGE_SUCC (ex_bb
, 0);
5230 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
5231 exit
= EDGE_SUCC (ex_bb
, 1);
5233 return (exit
->flags
& EDGE_TRUE_VALUE
? EQ_EXPR
: NE_EXPR
);
5236 /* Returns true if we can prove that BASE - OFFSET does not overflow. For now,
5237 we only detect the situation that BASE = SOMETHING + OFFSET, where the
5238 calculation is performed in non-wrapping type.
5240 TODO: More generally, we could test for the situation that
5241 BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero.
5242 This would require knowing the sign of OFFSET. */
5245 difference_cannot_overflow_p (struct ivopts_data
*data
, tree base
, tree offset
)
5247 enum tree_code code
;
5249 aff_tree aff_e1
, aff_e2
, aff_offset
;
5251 if (!nowrap_type_p (TREE_TYPE (base
)))
5254 base
= expand_simple_operations (base
);
5256 if (TREE_CODE (base
) == SSA_NAME
)
5258 gimple
*stmt
= SSA_NAME_DEF_STMT (base
);
5260 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
5263 code
= gimple_assign_rhs_code (stmt
);
5264 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
5267 e1
= gimple_assign_rhs1 (stmt
);
5268 e2
= gimple_assign_rhs2 (stmt
);
5272 code
= TREE_CODE (base
);
5273 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
5275 e1
= TREE_OPERAND (base
, 0);
5276 e2
= TREE_OPERAND (base
, 1);
5279 /* Use affine expansion as deeper inspection to prove the equality. */
5280 tree_to_aff_combination_expand (e2
, TREE_TYPE (e2
),
5281 &aff_e2
, &data
->name_expansion_cache
);
5282 tree_to_aff_combination_expand (offset
, TREE_TYPE (offset
),
5283 &aff_offset
, &data
->name_expansion_cache
);
5284 aff_combination_scale (&aff_offset
, -1);
5288 aff_combination_add (&aff_e2
, &aff_offset
);
5289 if (aff_combination_zero_p (&aff_e2
))
5292 tree_to_aff_combination_expand (e1
, TREE_TYPE (e1
),
5293 &aff_e1
, &data
->name_expansion_cache
);
5294 aff_combination_add (&aff_e1
, &aff_offset
);
5295 return aff_combination_zero_p (&aff_e1
);
5297 case POINTER_PLUS_EXPR
:
5298 aff_combination_add (&aff_e2
, &aff_offset
);
5299 return aff_combination_zero_p (&aff_e2
);
5306 /* Tries to replace loop exit by one formulated in terms of a LT_EXPR
5307 comparison with CAND. NITER describes the number of iterations of
5308 the loops. If successful, the comparison in COMP_P is altered accordingly.
5310 We aim to handle the following situation:
5326 Here, the number of iterations of the loop is (a + 1 > b) ? 0 : b - a - 1.
5327 We aim to optimize this to
5335 while (p < p_0 - a + b);
5337 This preserves the correctness, since the pointer arithmetics does not
5338 overflow. More precisely:
5340 1) if a + 1 <= b, then p_0 - a + b is the final value of p, hence there is no
5341 overflow in computing it or the values of p.
5342 2) if a + 1 > b, then we need to verify that the expression p_0 - a does not
5343 overflow. To prove this, we use the fact that p_0 = base + a. */
5346 iv_elimination_compare_lt (struct ivopts_data
*data
,
5347 struct iv_cand
*cand
, enum tree_code
*comp_p
,
5348 struct tree_niter_desc
*niter
)
5350 tree cand_type
, a
, b
, mbz
, nit_type
= TREE_TYPE (niter
->niter
), offset
;
5351 struct aff_tree nit
, tmpa
, tmpb
;
5352 enum tree_code comp
;
5355 /* We need to know that the candidate induction variable does not overflow.
5356 While more complex analysis may be used to prove this, for now just
5357 check that the variable appears in the original program and that it
5358 is computed in a type that guarantees no overflows. */
5359 cand_type
= TREE_TYPE (cand
->iv
->base
);
5360 if (cand
->pos
!= IP_ORIGINAL
|| !nowrap_type_p (cand_type
))
5363 /* Make sure that the loop iterates till the loop bound is hit, as otherwise
5364 the calculation of the BOUND could overflow, making the comparison
5366 if (!data
->loop_single_exit_p
)
5369 /* We need to be able to decide whether candidate is increasing or decreasing
5370 in order to choose the right comparison operator. */
5371 if (!cst_and_fits_in_hwi (cand
->iv
->step
))
5373 step
= int_cst_value (cand
->iv
->step
);
5375 /* Check that the number of iterations matches the expected pattern:
5376 a + 1 > b ? 0 : b - a - 1. */
5377 mbz
= niter
->may_be_zero
;
5378 if (TREE_CODE (mbz
) == GT_EXPR
)
5380 /* Handle a + 1 > b. */
5381 tree op0
= TREE_OPERAND (mbz
, 0);
5382 if (TREE_CODE (op0
) == PLUS_EXPR
&& integer_onep (TREE_OPERAND (op0
, 1)))
5384 a
= TREE_OPERAND (op0
, 0);
5385 b
= TREE_OPERAND (mbz
, 1);
5390 else if (TREE_CODE (mbz
) == LT_EXPR
)
5392 tree op1
= TREE_OPERAND (mbz
, 1);
5394 /* Handle b < a + 1. */
5395 if (TREE_CODE (op1
) == PLUS_EXPR
&& integer_onep (TREE_OPERAND (op1
, 1)))
5397 a
= TREE_OPERAND (op1
, 0);
5398 b
= TREE_OPERAND (mbz
, 0);
5406 /* Expected number of iterations is B - A - 1. Check that it matches
5407 the actual number, i.e., that B - A - NITER = 1. */
5408 tree_to_aff_combination (niter
->niter
, nit_type
, &nit
);
5409 tree_to_aff_combination (fold_convert (nit_type
, a
), nit_type
, &tmpa
);
5410 tree_to_aff_combination (fold_convert (nit_type
, b
), nit_type
, &tmpb
);
5411 aff_combination_scale (&nit
, -1);
5412 aff_combination_scale (&tmpa
, -1);
5413 aff_combination_add (&tmpb
, &tmpa
);
5414 aff_combination_add (&tmpb
, &nit
);
5415 if (tmpb
.n
!= 0 || tmpb
.offset
!= 1)
5418 /* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not
5420 offset
= fold_build2 (MULT_EXPR
, TREE_TYPE (cand
->iv
->step
),
5422 fold_convert (TREE_TYPE (cand
->iv
->step
), a
));
5423 if (!difference_cannot_overflow_p (data
, cand
->iv
->base
, offset
))
5426 /* Determine the new comparison operator. */
5427 comp
= step
< 0 ? GT_EXPR
: LT_EXPR
;
5428 if (*comp_p
== NE_EXPR
)
5430 else if (*comp_p
== EQ_EXPR
)
5431 *comp_p
= invert_tree_comparison (comp
, false);
5438 /* Check whether it is possible to express the condition in USE by comparison
5439 of candidate CAND. If so, store the value compared with to BOUND, and the
5440 comparison operator to COMP. */
5443 may_eliminate_iv (struct ivopts_data
*data
,
5444 struct iv_use
*use
, struct iv_cand
*cand
, tree
*bound
,
5445 enum tree_code
*comp
)
5450 struct loop
*loop
= data
->current_loop
;
5452 struct tree_niter_desc
*desc
= NULL
;
5454 if (TREE_CODE (cand
->iv
->step
) != INTEGER_CST
)
5457 /* For now works only for exits that dominate the loop latch.
5458 TODO: extend to other conditions inside loop body. */
5459 ex_bb
= gimple_bb (use
->stmt
);
5460 if (use
->stmt
!= last_stmt (ex_bb
)
5461 || gimple_code (use
->stmt
) != GIMPLE_COND
5462 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, ex_bb
))
5465 exit
= EDGE_SUCC (ex_bb
, 0);
5466 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
5467 exit
= EDGE_SUCC (ex_bb
, 1);
5468 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
5471 desc
= niter_for_exit (data
, exit
);
5475 /* Determine whether we can use the variable to test the exit condition.
5476 This is the case iff the period of the induction variable is greater
5477 than the number of iterations for which the exit condition is true. */
5478 period
= iv_period (cand
->iv
);
5480 /* If the number of iterations is constant, compare against it directly. */
5481 if (TREE_CODE (desc
->niter
) == INTEGER_CST
)
5483 /* See cand_value_at. */
5484 if (stmt_after_increment (loop
, cand
, use
->stmt
))
5486 if (!tree_int_cst_lt (desc
->niter
, period
))
5491 if (tree_int_cst_lt (period
, desc
->niter
))
5496 /* If not, and if this is the only possible exit of the loop, see whether
5497 we can get a conservative estimate on the number of iterations of the
5498 entire loop and compare against that instead. */
5501 widest_int period_value
, max_niter
;
5503 max_niter
= desc
->max
;
5504 if (stmt_after_increment (loop
, cand
, use
->stmt
))
5506 period_value
= wi::to_widest (period
);
5507 if (wi::gtu_p (max_niter
, period_value
))
5509 /* See if we can take advantage of inferred loop bound
5511 if (data
->loop_single_exit_p
)
5513 if (!max_loop_iterations (loop
, &max_niter
))
5515 /* The loop bound is already adjusted by adding 1. */
5516 if (wi::gtu_p (max_niter
, period_value
))
5524 cand_value_at (loop
, cand
, use
->stmt
, desc
->niter
, &bnd
);
5526 *bound
= fold_convert (TREE_TYPE (cand
->iv
->base
),
5527 aff_combination_to_tree (&bnd
));
5528 *comp
= iv_elimination_compare (data
, use
);
5530 /* It is unlikely that computing the number of iterations using division
5531 would be more profitable than keeping the original induction variable. */
5532 if (expression_expensive_p (*bound
))
5535 /* Sometimes, it is possible to handle the situation that the number of
5536 iterations may be zero unless additional assumtions by using <
5537 instead of != in the exit condition.
5539 TODO: we could also calculate the value MAY_BE_ZERO ? 0 : NITER and
5540 base the exit condition on it. However, that is often too
5542 if (!integer_zerop (desc
->may_be_zero
))
5543 return iv_elimination_compare_lt (data
, cand
, comp
, desc
);
5548 /* Calculates the cost of BOUND, if it is a PARM_DECL. A PARM_DECL must
5549 be copied, if it is used in the loop body and DATA->body_includes_call. */
5552 parm_decl_cost (struct ivopts_data
*data
, tree bound
)
5554 tree sbound
= bound
;
5555 STRIP_NOPS (sbound
);
5557 if (TREE_CODE (sbound
) == SSA_NAME
5558 && SSA_NAME_IS_DEFAULT_DEF (sbound
)
5559 && TREE_CODE (SSA_NAME_VAR (sbound
)) == PARM_DECL
5560 && data
->body_includes_call
)
5561 return COSTS_N_INSNS (1);
5566 /* Determines cost of computing the use in GROUP with CAND in a condition. */
5569 determine_group_iv_cost_cond (struct ivopts_data
*data
,
5570 struct iv_group
*group
, struct iv_cand
*cand
)
5572 tree bound
= NULL_TREE
;
5574 bitmap depends_on_elim
= NULL
, depends_on_express
= NULL
, depends_on
;
5575 comp_cost elim_cost
, express_cost
, cost
, bound_cost
;
5577 iv_inv_expr_ent
*elim_inv_expr
= NULL
, *express_inv_expr
= NULL
, *inv_expr
;
5578 tree
*control_var
, *bound_cst
;
5579 enum tree_code comp
= ERROR_MARK
;
5580 struct iv_use
*use
= group
->vuses
[0];
5582 gcc_assert (cand
->iv
);
5584 /* Try iv elimination. */
5585 if (may_eliminate_iv (data
, use
, cand
, &bound
, &comp
))
5587 elim_cost
= force_var_cost (data
, bound
, &depends_on_elim
);
5588 if (elim_cost
.cost
== 0)
5589 elim_cost
.cost
= parm_decl_cost (data
, bound
);
5590 else if (TREE_CODE (bound
) == INTEGER_CST
)
5592 /* If we replace a loop condition 'i < n' with 'p < base + n',
5593 depends_on_elim will have 'base' and 'n' set, which implies
5594 that both 'base' and 'n' will be live during the loop. More likely,
5595 'base + n' will be loop invariant, resulting in only one live value
5596 during the loop. So in that case we clear depends_on_elim and set
5597 elim_inv_expr_id instead. */
5598 if (depends_on_elim
&& bitmap_count_bits (depends_on_elim
) > 1)
5600 elim_inv_expr
= record_inv_expr (data
, bound
);
5601 bitmap_clear (depends_on_elim
);
5603 /* The bound is a loop invariant, so it will be only computed
5605 elim_cost
.cost
= adjust_setup_cost (data
, elim_cost
.cost
);
5608 elim_cost
= infinite_cost
;
5610 /* Try expressing the original giv. If it is compared with an invariant,
5611 note that we cannot get rid of it. */
5612 ok
= extract_cond_operands (data
, use
->stmt
, &control_var
, &bound_cst
,
5616 /* When the condition is a comparison of the candidate IV against
5617 zero, prefer this IV.
5619 TODO: The constant that we're subtracting from the cost should
5620 be target-dependent. This information should be added to the
5621 target costs for each backend. */
5622 if (!elim_cost
.infinite_cost_p () /* Do not try to decrease infinite! */
5623 && integer_zerop (*bound_cst
)
5624 && (operand_equal_p (*control_var
, cand
->var_after
, 0)
5625 || operand_equal_p (*control_var
, cand
->var_before
, 0)))
5628 express_cost
= get_computation_cost (data
, use
, cand
, false,
5629 &depends_on_express
, NULL
,
5631 fd_ivopts_data
= data
;
5632 walk_tree (&cmp_iv
->base
, find_depends
, &depends_on_express
, NULL
);
5634 /* Count the cost of the original bound as well. */
5635 bound_cost
= force_var_cost (data
, *bound_cst
, NULL
);
5636 if (bound_cost
.cost
== 0)
5637 bound_cost
.cost
= parm_decl_cost (data
, *bound_cst
);
5638 else if (TREE_CODE (*bound_cst
) == INTEGER_CST
)
5639 bound_cost
.cost
= 0;
5640 express_cost
+= bound_cost
;
5642 /* Choose the better approach, preferring the eliminated IV. */
5643 if (elim_cost
<= express_cost
)
5646 depends_on
= depends_on_elim
;
5647 depends_on_elim
= NULL
;
5648 inv_expr
= elim_inv_expr
;
5652 cost
= express_cost
;
5653 depends_on
= depends_on_express
;
5654 depends_on_express
= NULL
;
5657 inv_expr
= express_inv_expr
;
5660 set_group_iv_cost (data
, group
, cand
, cost
,
5661 depends_on
, bound
, comp
, inv_expr
);
5663 if (depends_on_elim
)
5664 BITMAP_FREE (depends_on_elim
);
5665 if (depends_on_express
)
5666 BITMAP_FREE (depends_on_express
);
5668 return !cost
.infinite_cost_p ();
5671 /* Determines cost of computing uses in GROUP with CAND. Returns false
5672 if USE cannot be represented with CAND. */
5675 determine_group_iv_cost (struct ivopts_data
*data
,
5676 struct iv_group
*group
, struct iv_cand
*cand
)
5678 switch (group
->type
)
5680 case USE_NONLINEAR_EXPR
:
5681 return determine_group_iv_cost_generic (data
, group
, cand
);
5684 return determine_group_iv_cost_address (data
, group
, cand
);
5687 return determine_group_iv_cost_cond (data
, group
, cand
);
5694 /* Return true if get_computation_cost indicates that autoincrement is
5695 a possibility for the pair of USE and CAND, false otherwise. */
5698 autoinc_possible_for_pair (struct ivopts_data
*data
, struct iv_use
*use
,
5699 struct iv_cand
*cand
)
5705 if (use
->type
!= USE_ADDRESS
)
5708 cost
= get_computation_cost (data
, use
, cand
, true, &depends_on
,
5709 &can_autoinc
, NULL
);
5711 BITMAP_FREE (depends_on
);
5713 return !cost
.infinite_cost_p () && can_autoinc
;
5716 /* Examine IP_ORIGINAL candidates to see if they are incremented next to a
5717 use that allows autoincrement, and set their AINC_USE if possible. */
5720 set_autoinc_for_original_candidates (struct ivopts_data
*data
)
5724 for (i
= 0; i
< data
->vcands
.length (); i
++)
5726 struct iv_cand
*cand
= data
->vcands
[i
];
5727 struct iv_use
*closest_before
= NULL
;
5728 struct iv_use
*closest_after
= NULL
;
5729 if (cand
->pos
!= IP_ORIGINAL
)
5732 for (j
= 0; j
< data
->vgroups
.length (); j
++)
5734 struct iv_group
*group
= data
->vgroups
[j
];
5735 struct iv_use
*use
= group
->vuses
[0];
5736 unsigned uid
= gimple_uid (use
->stmt
);
5738 if (gimple_bb (use
->stmt
) != gimple_bb (cand
->incremented_at
))
5741 if (uid
< gimple_uid (cand
->incremented_at
)
5742 && (closest_before
== NULL
5743 || uid
> gimple_uid (closest_before
->stmt
)))
5744 closest_before
= use
;
5746 if (uid
> gimple_uid (cand
->incremented_at
)
5747 && (closest_after
== NULL
5748 || uid
< gimple_uid (closest_after
->stmt
)))
5749 closest_after
= use
;
5752 if (closest_before
!= NULL
5753 && autoinc_possible_for_pair (data
, closest_before
, cand
))
5754 cand
->ainc_use
= closest_before
;
5755 else if (closest_after
!= NULL
5756 && autoinc_possible_for_pair (data
, closest_after
, cand
))
5757 cand
->ainc_use
= closest_after
;
5761 /* Finds the candidates for the induction variables. */
5764 find_iv_candidates (struct ivopts_data
*data
)
5766 /* Add commonly used ivs. */
5767 add_standard_iv_candidates (data
);
5769 /* Add old induction variables. */
5770 add_iv_candidate_for_bivs (data
);
5772 /* Add induction variables derived from uses. */
5773 add_iv_candidate_for_groups (data
);
5775 set_autoinc_for_original_candidates (data
);
5777 /* Record the important candidates. */
5778 record_important_candidates (data
);
5780 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5784 fprintf (dump_file
, "\n<Important Candidates>:\t");
5785 for (i
= 0; i
< data
->vcands
.length (); i
++)
5786 if (data
->vcands
[i
]->important
)
5787 fprintf (dump_file
, " %d,", data
->vcands
[i
]->id
);
5788 fprintf (dump_file
, "\n");
5790 fprintf (dump_file
, "\n<Group, Cand> Related:\n");
5791 for (i
= 0; i
< data
->vgroups
.length (); i
++)
5793 struct iv_group
*group
= data
->vgroups
[i
];
5795 if (group
->related_cands
)
5797 fprintf (dump_file
, " Group %d:\t", group
->id
);
5798 dump_bitmap (dump_file
, group
->related_cands
);
5801 fprintf (dump_file
, "\n");
5805 /* Determines costs of computing use of iv with an iv candidate. */
5808 determine_group_iv_costs (struct ivopts_data
*data
)
5811 struct iv_cand
*cand
;
5812 struct iv_group
*group
;
5813 bitmap to_clear
= BITMAP_ALLOC (NULL
);
5815 alloc_use_cost_map (data
);
5817 for (i
= 0; i
< data
->vgroups
.length (); i
++)
5819 group
= data
->vgroups
[i
];
5821 if (data
->consider_all_candidates
)
5823 for (j
= 0; j
< data
->vcands
.length (); j
++)
5825 cand
= data
->vcands
[j
];
5826 determine_group_iv_cost (data
, group
, cand
);
5833 EXECUTE_IF_SET_IN_BITMAP (group
->related_cands
, 0, j
, bi
)
5835 cand
= data
->vcands
[j
];
5836 if (!determine_group_iv_cost (data
, group
, cand
))
5837 bitmap_set_bit (to_clear
, j
);
5840 /* Remove the candidates for that the cost is infinite from
5841 the list of related candidates. */
5842 bitmap_and_compl_into (group
->related_cands
, to_clear
);
5843 bitmap_clear (to_clear
);
5847 BITMAP_FREE (to_clear
);
5849 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5851 fprintf (dump_file
, "\n<Invariant Expressions>:\n");
5852 auto_vec
<iv_inv_expr_ent
*> list (data
->inv_expr_tab
->elements ());
5854 for (hash_table
<iv_inv_expr_hasher
>::iterator it
5855 = data
->inv_expr_tab
->begin (); it
!= data
->inv_expr_tab
->end ();
5857 list
.safe_push (*it
);
5859 list
.qsort (sort_iv_inv_expr_ent
);
5861 for (i
= 0; i
< list
.length (); ++i
)
5863 fprintf (dump_file
, "inv_expr %d: \t", i
);
5864 print_generic_expr (dump_file
, list
[i
]->expr
, TDF_SLIM
);
5865 fprintf (dump_file
, "\n");
5868 fprintf (dump_file
, "\n<Group-candidate Costs>:\n");
5870 for (i
= 0; i
< data
->vgroups
.length (); i
++)
5872 group
= data
->vgroups
[i
];
5874 fprintf (dump_file
, "Group %d:\n", i
);
5875 fprintf (dump_file
, " cand\tcost\tcompl.\tinv.ex.\tdepends on\n");
5876 for (j
= 0; j
< group
->n_map_members
; j
++)
5878 if (!group
->cost_map
[j
].cand
5879 || group
->cost_map
[j
].cost
.infinite_cost_p ())
5882 fprintf (dump_file
, " %d\t%d\t%d\t",
5883 group
->cost_map
[j
].cand
->id
,
5884 group
->cost_map
[j
].cost
.cost
,
5885 group
->cost_map
[j
].cost
.complexity
);
5886 if (group
->cost_map
[j
].inv_expr
!= NULL
)
5887 fprintf (dump_file
, "%d\t",
5888 group
->cost_map
[j
].inv_expr
->id
);
5890 fprintf (dump_file
, "\t");
5891 if (group
->cost_map
[j
].depends_on
)
5892 bitmap_print (dump_file
,
5893 group
->cost_map
[j
].depends_on
, "","");
5894 fprintf (dump_file
, "\n");
5897 fprintf (dump_file
, "\n");
5899 fprintf (dump_file
, "\n");
5903 /* Determines cost of the candidate CAND. */
5906 determine_iv_cost (struct ivopts_data
*data
, struct iv_cand
*cand
)
5908 comp_cost cost_base
;
5909 unsigned cost
, cost_step
;
5918 /* There are two costs associated with the candidate -- its increment
5919 and its initialization. The second is almost negligible for any loop
5920 that rolls enough, so we take it just very little into account. */
5922 base
= cand
->iv
->base
;
5923 cost_base
= force_var_cost (data
, base
, NULL
);
5924 /* It will be exceptional that the iv register happens to be initialized with
5925 the proper value at no cost. In general, there will at least be a regcopy
5927 if (cost_base
.cost
== 0)
5928 cost_base
.cost
= COSTS_N_INSNS (1);
5929 cost_step
= add_cost (data
->speed
, TYPE_MODE (TREE_TYPE (base
)));
5931 cost
= cost_step
+ adjust_setup_cost (data
, cost_base
.cost
);
5933 /* Prefer the original ivs unless we may gain something by replacing it.
5934 The reason is to make debugging simpler; so this is not relevant for
5935 artificial ivs created by other optimization passes. */
5936 if (cand
->pos
!= IP_ORIGINAL
5937 || !SSA_NAME_VAR (cand
->var_before
)
5938 || DECL_ARTIFICIAL (SSA_NAME_VAR (cand
->var_before
)))
5941 /* Prefer not to insert statements into latch unless there are some
5942 already (so that we do not create unnecessary jumps). */
5943 if (cand
->pos
== IP_END
5944 && empty_block_p (ip_end_pos (data
->current_loop
)))
5948 cand
->cost_step
= cost_step
;
5951 /* Determines costs of computation of the candidates. */
5954 determine_iv_costs (struct ivopts_data
*data
)
5958 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5960 fprintf (dump_file
, "<Candidate Costs>:\n");
5961 fprintf (dump_file
, " cand\tcost\n");
5964 for (i
= 0; i
< data
->vcands
.length (); i
++)
5966 struct iv_cand
*cand
= data
->vcands
[i
];
5968 determine_iv_cost (data
, cand
);
5970 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5971 fprintf (dump_file
, " %d\t%d\n", i
, cand
->cost
);
5974 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5975 fprintf (dump_file
, "\n");
5978 /* Calculates cost for having SIZE induction variables. */
5981 ivopts_global_cost_for_size (struct ivopts_data
*data
, unsigned size
)
5983 /* We add size to the cost, so that we prefer eliminating ivs
5985 return size
+ estimate_reg_pressure_cost (size
, data
->regs_used
, data
->speed
,
5986 data
->body_includes_call
);
5989 /* For each size of the induction variable set determine the penalty. */
5992 determine_set_costs (struct ivopts_data
*data
)
5998 struct loop
*loop
= data
->current_loop
;
6001 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6003 fprintf (dump_file
, "<Global Costs>:\n");
6004 fprintf (dump_file
, " target_avail_regs %d\n", target_avail_regs
);
6005 fprintf (dump_file
, " target_clobbered_regs %d\n", target_clobbered_regs
);
6006 fprintf (dump_file
, " target_reg_cost %d\n", target_reg_cost
[data
->speed
]);
6007 fprintf (dump_file
, " target_spill_cost %d\n", target_spill_cost
[data
->speed
]);
6011 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
6014 op
= PHI_RESULT (phi
);
6016 if (virtual_operand_p (op
))
6019 if (get_iv (data
, op
))
6025 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
6027 struct version_info
*info
= ver_info (data
, j
);
6029 if (info
->inv_id
&& info
->has_nonlin_use
)
6033 data
->regs_used
= n
;
6034 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6035 fprintf (dump_file
, " regs_used %d\n", n
);
6037 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6039 fprintf (dump_file
, " cost for size:\n");
6040 fprintf (dump_file
, " ivs\tcost\n");
6041 for (j
= 0; j
<= 2 * target_avail_regs
; j
++)
6042 fprintf (dump_file
, " %d\t%d\n", j
,
6043 ivopts_global_cost_for_size (data
, j
));
6044 fprintf (dump_file
, "\n");
6048 /* Returns true if A is a cheaper cost pair than B. */
6051 cheaper_cost_pair (struct cost_pair
*a
, struct cost_pair
*b
)
6059 if (a
->cost
< b
->cost
)
6062 if (b
->cost
< a
->cost
)
6065 /* In case the costs are the same, prefer the cheaper candidate. */
6066 if (a
->cand
->cost
< b
->cand
->cost
)
6073 /* Returns candidate by that USE is expressed in IVS. */
6075 static struct cost_pair
*
6076 iv_ca_cand_for_group (struct iv_ca
*ivs
, struct iv_group
*group
)
6078 return ivs
->cand_for_group
[group
->id
];
6081 /* Computes the cost field of IVS structure. */
6084 iv_ca_recount_cost (struct ivopts_data
*data
, struct iv_ca
*ivs
)
6086 comp_cost cost
= ivs
->cand_use_cost
;
6088 cost
+= ivs
->cand_cost
;
6090 cost
+= ivopts_global_cost_for_size (data
,
6092 + ivs
->used_inv_exprs
->elements ());
6097 /* Remove invariants in set INVS to set IVS. */
6100 iv_ca_set_remove_invariants (struct iv_ca
*ivs
, bitmap invs
)
6108 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
6110 ivs
->n_invariant_uses
[iid
]--;
6111 if (ivs
->n_invariant_uses
[iid
] == 0)
6116 /* Set USE not to be expressed by any candidate in IVS. */
6119 iv_ca_set_no_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6120 struct iv_group
*group
)
6122 unsigned gid
= group
->id
, cid
;
6123 struct cost_pair
*cp
;
6125 cp
= ivs
->cand_for_group
[gid
];
6131 ivs
->cand_for_group
[gid
] = NULL
;
6132 ivs
->n_cand_uses
[cid
]--;
6134 if (ivs
->n_cand_uses
[cid
] == 0)
6136 bitmap_clear_bit (ivs
->cands
, cid
);
6137 /* Do not count the pseudocandidates. */
6141 ivs
->cand_cost
-= cp
->cand
->cost
;
6143 iv_ca_set_remove_invariants (ivs
, cp
->cand
->depends_on
);
6146 ivs
->cand_use_cost
-= cp
->cost
;
6148 iv_ca_set_remove_invariants (ivs
, cp
->depends_on
);
6150 if (cp
->inv_expr
!= NULL
)
6152 unsigned *slot
= ivs
->used_inv_exprs
->get (cp
->inv_expr
);
6155 ivs
->used_inv_exprs
->remove (cp
->inv_expr
);
6157 iv_ca_recount_cost (data
, ivs
);
6160 /* Add invariants in set INVS to set IVS. */
6163 iv_ca_set_add_invariants (struct iv_ca
*ivs
, bitmap invs
)
6171 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
6173 ivs
->n_invariant_uses
[iid
]++;
6174 if (ivs
->n_invariant_uses
[iid
] == 1)
6179 /* Set cost pair for GROUP in set IVS to CP. */
6182 iv_ca_set_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6183 struct iv_group
*group
, struct cost_pair
*cp
)
6185 unsigned gid
= group
->id
, cid
;
6187 if (ivs
->cand_for_group
[gid
] == cp
)
6190 if (ivs
->cand_for_group
[gid
])
6191 iv_ca_set_no_cp (data
, ivs
, group
);
6198 ivs
->cand_for_group
[gid
] = cp
;
6199 ivs
->n_cand_uses
[cid
]++;
6200 if (ivs
->n_cand_uses
[cid
] == 1)
6202 bitmap_set_bit (ivs
->cands
, cid
);
6203 /* Do not count the pseudocandidates. */
6207 ivs
->cand_cost
+= cp
->cand
->cost
;
6209 iv_ca_set_add_invariants (ivs
, cp
->cand
->depends_on
);
6212 ivs
->cand_use_cost
+= cp
->cost
;
6213 iv_ca_set_add_invariants (ivs
, cp
->depends_on
);
6215 if (cp
->inv_expr
!= NULL
)
6217 unsigned *slot
= &ivs
->used_inv_exprs
->get_or_insert (cp
->inv_expr
);
6220 iv_ca_recount_cost (data
, ivs
);
6224 /* Extend set IVS by expressing USE by some of the candidates in it
6225 if possible. Consider all important candidates if candidates in
6226 set IVS don't give any result. */
6229 iv_ca_add_group (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6230 struct iv_group
*group
)
6232 struct cost_pair
*best_cp
= NULL
, *cp
;
6235 struct iv_cand
*cand
;
6237 gcc_assert (ivs
->upto
>= group
->id
);
6241 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
6243 cand
= data
->vcands
[i
];
6244 cp
= get_group_iv_cost (data
, group
, cand
);
6245 if (cheaper_cost_pair (cp
, best_cp
))
6249 if (best_cp
== NULL
)
6251 EXECUTE_IF_SET_IN_BITMAP (data
->important_candidates
, 0, i
, bi
)
6253 cand
= data
->vcands
[i
];
6254 cp
= get_group_iv_cost (data
, group
, cand
);
6255 if (cheaper_cost_pair (cp
, best_cp
))
6260 iv_ca_set_cp (data
, ivs
, group
, best_cp
);
6263 /* Get cost for assignment IVS. */
6266 iv_ca_cost (struct iv_ca
*ivs
)
6268 /* This was a conditional expression but it triggered a bug in
6270 if (ivs
->bad_groups
)
6271 return infinite_cost
;
6276 /* Returns true if all dependences of CP are among invariants in IVS. */
6279 iv_ca_has_deps (struct iv_ca
*ivs
, struct cost_pair
*cp
)
6284 if (!cp
->depends_on
)
6287 EXECUTE_IF_SET_IN_BITMAP (cp
->depends_on
, 0, i
, bi
)
6289 if (ivs
->n_invariant_uses
[i
] == 0)
6296 /* Creates change of expressing GROUP by NEW_CP instead of OLD_CP and chains
6299 static struct iv_ca_delta
*
6300 iv_ca_delta_add (struct iv_group
*group
, struct cost_pair
*old_cp
,
6301 struct cost_pair
*new_cp
, struct iv_ca_delta
*next
)
6303 struct iv_ca_delta
*change
= XNEW (struct iv_ca_delta
);
6305 change
->group
= group
;
6306 change
->old_cp
= old_cp
;
6307 change
->new_cp
= new_cp
;
6308 change
->next
= next
;
6313 /* Joins two lists of changes L1 and L2. Destructive -- old lists
6316 static struct iv_ca_delta
*
6317 iv_ca_delta_join (struct iv_ca_delta
*l1
, struct iv_ca_delta
*l2
)
6319 struct iv_ca_delta
*last
;
6327 for (last
= l1
; last
->next
; last
= last
->next
)
6334 /* Reverse the list of changes DELTA, forming the inverse to it. */
6336 static struct iv_ca_delta
*
6337 iv_ca_delta_reverse (struct iv_ca_delta
*delta
)
6339 struct iv_ca_delta
*act
, *next
, *prev
= NULL
;
6341 for (act
= delta
; act
; act
= next
)
6347 std::swap (act
->old_cp
, act
->new_cp
);
6353 /* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
6354 reverted instead. */
6357 iv_ca_delta_commit (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6358 struct iv_ca_delta
*delta
, bool forward
)
6360 struct cost_pair
*from
, *to
;
6361 struct iv_ca_delta
*act
;
6364 delta
= iv_ca_delta_reverse (delta
);
6366 for (act
= delta
; act
; act
= act
->next
)
6370 gcc_assert (iv_ca_cand_for_group (ivs
, act
->group
) == from
);
6371 iv_ca_set_cp (data
, ivs
, act
->group
, to
);
6375 iv_ca_delta_reverse (delta
);
6378 /* Returns true if CAND is used in IVS. */
6381 iv_ca_cand_used_p (struct iv_ca
*ivs
, struct iv_cand
*cand
)
6383 return ivs
->n_cand_uses
[cand
->id
] > 0;
6386 /* Returns number of induction variable candidates in the set IVS. */
6389 iv_ca_n_cands (struct iv_ca
*ivs
)
6391 return ivs
->n_cands
;
6394 /* Free the list of changes DELTA. */
6397 iv_ca_delta_free (struct iv_ca_delta
**delta
)
6399 struct iv_ca_delta
*act
, *next
;
6401 for (act
= *delta
; act
; act
= next
)
6410 /* Allocates new iv candidates assignment. */
6412 static struct iv_ca
*
6413 iv_ca_new (struct ivopts_data
*data
)
6415 struct iv_ca
*nw
= XNEW (struct iv_ca
);
6419 nw
->cand_for_group
= XCNEWVEC (struct cost_pair
*,
6420 data
->vgroups
.length ());
6421 nw
->n_cand_uses
= XCNEWVEC (unsigned, data
->vcands
.length ());
6422 nw
->cands
= BITMAP_ALLOC (NULL
);
6425 nw
->cand_use_cost
= no_cost
;
6427 nw
->n_invariant_uses
= XCNEWVEC (unsigned, data
->max_inv_id
+ 1);
6428 nw
->used_inv_exprs
= new hash_map
<iv_inv_expr_ent
*, unsigned> (13);
6434 /* Free memory occupied by the set IVS. */
6437 iv_ca_free (struct iv_ca
**ivs
)
6439 free ((*ivs
)->cand_for_group
);
6440 free ((*ivs
)->n_cand_uses
);
6441 BITMAP_FREE ((*ivs
)->cands
);
6442 free ((*ivs
)->n_invariant_uses
);
6443 delete ((*ivs
)->used_inv_exprs
);
6448 /* Dumps IVS to FILE. */
6451 iv_ca_dump (struct ivopts_data
*data
, FILE *file
, struct iv_ca
*ivs
)
6454 comp_cost cost
= iv_ca_cost (ivs
);
6456 fprintf (file
, " cost: %d (complexity %d)\n", cost
.cost
,
6458 fprintf (file
, " cand_cost: %d\n cand_group_cost: %d (complexity %d)\n",
6459 ivs
->cand_cost
, ivs
->cand_use_cost
.cost
,
6460 ivs
->cand_use_cost
.complexity
);
6461 bitmap_print (file
, ivs
->cands
, " candidates: ","\n");
6463 for (i
= 0; i
< ivs
->upto
; i
++)
6465 struct iv_group
*group
= data
->vgroups
[i
];
6466 struct cost_pair
*cp
= iv_ca_cand_for_group (ivs
, group
);
6468 fprintf (file
, " group:%d --> iv_cand:%d, cost=(%d,%d)\n",
6469 group
->id
, cp
->cand
->id
, cp
->cost
.cost
,
6470 cp
->cost
.complexity
);
6472 fprintf (file
, " group:%d --> ??\n", group
->id
);
6475 const char *pref
= "";
6476 fprintf (file
, " invariant variables: ");
6477 for (i
= 1; i
<= data
->max_inv_id
; i
++)
6478 if (ivs
->n_invariant_uses
[i
])
6480 fprintf (file
, "%s%d", pref
, i
);
6485 fprintf (file
, "\n invariant expressions: ");
6486 for (hash_map
<iv_inv_expr_ent
*, unsigned>::iterator it
6487 = ivs
->used_inv_exprs
->begin (); it
!= ivs
->used_inv_exprs
->end (); ++it
)
6489 fprintf (file
, "%s%d", pref
, (*it
).first
->id
);
6493 fprintf (file
, "\n\n");
6496 /* Try changing candidate in IVS to CAND for each use. Return cost of the
6497 new set, and store differences in DELTA. Number of induction variables
6498 in the new set is stored to N_IVS. MIN_NCAND is a flag. When it is true
6499 the function will try to find a solution with mimimal iv candidates. */
6502 iv_ca_extend (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6503 struct iv_cand
*cand
, struct iv_ca_delta
**delta
,
6504 unsigned *n_ivs
, bool min_ncand
)
6508 struct iv_group
*group
;
6509 struct cost_pair
*old_cp
, *new_cp
;
6512 for (i
= 0; i
< ivs
->upto
; i
++)
6514 group
= data
->vgroups
[i
];
6515 old_cp
= iv_ca_cand_for_group (ivs
, group
);
6518 && old_cp
->cand
== cand
)
6521 new_cp
= get_group_iv_cost (data
, group
, cand
);
6525 if (!min_ncand
&& !iv_ca_has_deps (ivs
, new_cp
))
6528 if (!min_ncand
&& !cheaper_cost_pair (new_cp
, old_cp
))
6531 *delta
= iv_ca_delta_add (group
, old_cp
, new_cp
, *delta
);
6534 iv_ca_delta_commit (data
, ivs
, *delta
, true);
6535 cost
= iv_ca_cost (ivs
);
6537 *n_ivs
= iv_ca_n_cands (ivs
);
6538 iv_ca_delta_commit (data
, ivs
, *delta
, false);
6543 /* Try narrowing set IVS by removing CAND. Return the cost of
6544 the new set and store the differences in DELTA. START is
6545 the candidate with which we start narrowing. */
6548 iv_ca_narrow (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6549 struct iv_cand
*cand
, struct iv_cand
*start
,
6550 struct iv_ca_delta
**delta
)
6553 struct iv_group
*group
;
6554 struct cost_pair
*old_cp
, *new_cp
, *cp
;
6556 struct iv_cand
*cnd
;
6557 comp_cost cost
, best_cost
, acost
;
6560 for (i
= 0; i
< data
->vgroups
.length (); i
++)
6562 group
= data
->vgroups
[i
];
6564 old_cp
= iv_ca_cand_for_group (ivs
, group
);
6565 if (old_cp
->cand
!= cand
)
6568 best_cost
= iv_ca_cost (ivs
);
6569 /* Start narrowing with START. */
6570 new_cp
= get_group_iv_cost (data
, group
, start
);
6572 if (data
->consider_all_candidates
)
6574 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, ci
, bi
)
6576 if (ci
== cand
->id
|| (start
&& ci
== start
->id
))
6579 cnd
= data
->vcands
[ci
];
6581 cp
= get_group_iv_cost (data
, group
, cnd
);
6585 iv_ca_set_cp (data
, ivs
, group
, cp
);
6586 acost
= iv_ca_cost (ivs
);
6588 if (acost
< best_cost
)
6597 EXECUTE_IF_AND_IN_BITMAP (group
->related_cands
, ivs
->cands
, 0, ci
, bi
)
6599 if (ci
== cand
->id
|| (start
&& ci
== start
->id
))
6602 cnd
= data
->vcands
[ci
];
6604 cp
= get_group_iv_cost (data
, group
, cnd
);
6608 iv_ca_set_cp (data
, ivs
, group
, cp
);
6609 acost
= iv_ca_cost (ivs
);
6611 if (acost
< best_cost
)
6618 /* Restore to old cp for use. */
6619 iv_ca_set_cp (data
, ivs
, group
, old_cp
);
6623 iv_ca_delta_free (delta
);
6624 return infinite_cost
;
6627 *delta
= iv_ca_delta_add (group
, old_cp
, new_cp
, *delta
);
6630 iv_ca_delta_commit (data
, ivs
, *delta
, true);
6631 cost
= iv_ca_cost (ivs
);
6632 iv_ca_delta_commit (data
, ivs
, *delta
, false);
6637 /* Try optimizing the set of candidates IVS by removing candidates different
6638 from to EXCEPT_CAND from it. Return cost of the new set, and store
6639 differences in DELTA. */
6642 iv_ca_prune (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6643 struct iv_cand
*except_cand
, struct iv_ca_delta
**delta
)
6646 struct iv_ca_delta
*act_delta
, *best_delta
;
6648 comp_cost best_cost
, acost
;
6649 struct iv_cand
*cand
;
6652 best_cost
= iv_ca_cost (ivs
);
6654 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
6656 cand
= data
->vcands
[i
];
6658 if (cand
== except_cand
)
6661 acost
= iv_ca_narrow (data
, ivs
, cand
, except_cand
, &act_delta
);
6663 if (acost
< best_cost
)
6666 iv_ca_delta_free (&best_delta
);
6667 best_delta
= act_delta
;
6670 iv_ca_delta_free (&act_delta
);
6679 /* Recurse to possibly remove other unnecessary ivs. */
6680 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
6681 best_cost
= iv_ca_prune (data
, ivs
, except_cand
, delta
);
6682 iv_ca_delta_commit (data
, ivs
, best_delta
, false);
6683 *delta
= iv_ca_delta_join (best_delta
, *delta
);
6687 /* Check if CAND_IDX is a candidate other than OLD_CAND and has
6688 cheaper local cost for GROUP than BEST_CP. Return pointer to
6689 the corresponding cost_pair, otherwise just return BEST_CP. */
6691 static struct cost_pair
*
6692 cheaper_cost_with_cand (struct ivopts_data
*data
, struct iv_group
*group
,
6693 unsigned int cand_idx
, struct iv_cand
*old_cand
,
6694 struct cost_pair
*best_cp
)
6696 struct iv_cand
*cand
;
6697 struct cost_pair
*cp
;
6699 gcc_assert (old_cand
!= NULL
&& best_cp
!= NULL
);
6700 if (cand_idx
== old_cand
->id
)
6703 cand
= data
->vcands
[cand_idx
];
6704 cp
= get_group_iv_cost (data
, group
, cand
);
6705 if (cp
!= NULL
&& cheaper_cost_pair (cp
, best_cp
))
6711 /* Try breaking local optimal fixed-point for IVS by replacing candidates
6712 which are used by more than one iv uses. For each of those candidates,
6713 this function tries to represent iv uses under that candidate using
6714 other ones with lower local cost, then tries to prune the new set.
6715 If the new set has lower cost, It returns the new cost after recording
6716 candidate replacement in list DELTA. */
6719 iv_ca_replace (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6720 struct iv_ca_delta
**delta
)
6722 bitmap_iterator bi
, bj
;
6723 unsigned int i
, j
, k
;
6724 struct iv_cand
*cand
;
6725 comp_cost orig_cost
, acost
;
6726 struct iv_ca_delta
*act_delta
, *tmp_delta
;
6727 struct cost_pair
*old_cp
, *best_cp
= NULL
;
6730 orig_cost
= iv_ca_cost (ivs
);
6732 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
6734 if (ivs
->n_cand_uses
[i
] == 1
6735 || ivs
->n_cand_uses
[i
] > ALWAYS_PRUNE_CAND_SET_BOUND
)
6738 cand
= data
->vcands
[i
];
6741 /* Represent uses under current candidate using other ones with
6742 lower local cost. */
6743 for (j
= 0; j
< ivs
->upto
; j
++)
6745 struct iv_group
*group
= data
->vgroups
[j
];
6746 old_cp
= iv_ca_cand_for_group (ivs
, group
);
6748 if (old_cp
->cand
!= cand
)
6752 if (data
->consider_all_candidates
)
6753 for (k
= 0; k
< data
->vcands
.length (); k
++)
6754 best_cp
= cheaper_cost_with_cand (data
, group
, k
,
6755 old_cp
->cand
, best_cp
);
6757 EXECUTE_IF_SET_IN_BITMAP (group
->related_cands
, 0, k
, bj
)
6758 best_cp
= cheaper_cost_with_cand (data
, group
, k
,
6759 old_cp
->cand
, best_cp
);
6761 if (best_cp
== old_cp
)
6764 act_delta
= iv_ca_delta_add (group
, old_cp
, best_cp
, act_delta
);
6766 /* No need for further prune. */
6770 /* Prune the new candidate set. */
6771 iv_ca_delta_commit (data
, ivs
, act_delta
, true);
6772 acost
= iv_ca_prune (data
, ivs
, NULL
, &tmp_delta
);
6773 iv_ca_delta_commit (data
, ivs
, act_delta
, false);
6774 act_delta
= iv_ca_delta_join (act_delta
, tmp_delta
);
6776 if (acost
< orig_cost
)
6782 iv_ca_delta_free (&act_delta
);
6788 /* Tries to extend the sets IVS in the best possible way in order to
6789 express the GROUP. If ORIGINALP is true, prefer candidates from
6790 the original set of IVs, otherwise favor important candidates not
6791 based on any memory object. */
6794 try_add_cand_for (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6795 struct iv_group
*group
, bool originalp
)
6797 comp_cost best_cost
, act_cost
;
6800 struct iv_cand
*cand
;
6801 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
;
6802 struct cost_pair
*cp
;
6804 iv_ca_add_group (data
, ivs
, group
);
6805 best_cost
= iv_ca_cost (ivs
);
6806 cp
= iv_ca_cand_for_group (ivs
, group
);
6809 best_delta
= iv_ca_delta_add (group
, NULL
, cp
, NULL
);
6810 iv_ca_set_no_cp (data
, ivs
, group
);
6813 /* If ORIGINALP is true, try to find the original IV for the use. Otherwise
6814 first try important candidates not based on any memory object. Only if
6815 this fails, try the specific ones. Rationale -- in loops with many
6816 variables the best choice often is to use just one generic biv. If we
6817 added here many ivs specific to the uses, the optimization algorithm later
6818 would be likely to get stuck in a local minimum, thus causing us to create
6819 too many ivs. The approach from few ivs to more seems more likely to be
6820 successful -- starting from few ivs, replacing an expensive use by a
6821 specific iv should always be a win. */
6822 EXECUTE_IF_SET_IN_BITMAP (group
->related_cands
, 0, i
, bi
)
6824 cand
= data
->vcands
[i
];
6826 if (originalp
&& cand
->pos
!=IP_ORIGINAL
)
6829 if (!originalp
&& cand
->iv
->base_object
!= NULL_TREE
)
6832 if (iv_ca_cand_used_p (ivs
, cand
))
6835 cp
= get_group_iv_cost (data
, group
, cand
);
6839 iv_ca_set_cp (data
, ivs
, group
, cp
);
6840 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
,
6842 iv_ca_set_no_cp (data
, ivs
, group
);
6843 act_delta
= iv_ca_delta_add (group
, NULL
, cp
, act_delta
);
6845 if (act_cost
< best_cost
)
6847 best_cost
= act_cost
;
6849 iv_ca_delta_free (&best_delta
);
6850 best_delta
= act_delta
;
6853 iv_ca_delta_free (&act_delta
);
6856 if (best_cost
.infinite_cost_p ())
6858 for (i
= 0; i
< group
->n_map_members
; i
++)
6860 cp
= group
->cost_map
+ i
;
6865 /* Already tried this. */
6866 if (cand
->important
)
6868 if (originalp
&& cand
->pos
== IP_ORIGINAL
)
6870 if (!originalp
&& cand
->iv
->base_object
== NULL_TREE
)
6874 if (iv_ca_cand_used_p (ivs
, cand
))
6878 iv_ca_set_cp (data
, ivs
, group
, cp
);
6879 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
, true);
6880 iv_ca_set_no_cp (data
, ivs
, group
);
6881 act_delta
= iv_ca_delta_add (group
,
6882 iv_ca_cand_for_group (ivs
, group
),
6885 if (act_cost
< best_cost
)
6887 best_cost
= act_cost
;
6890 iv_ca_delta_free (&best_delta
);
6891 best_delta
= act_delta
;
6894 iv_ca_delta_free (&act_delta
);
6898 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
6899 iv_ca_delta_free (&best_delta
);
6901 return !best_cost
.infinite_cost_p ();
6904 /* Finds an initial assignment of candidates to uses. */
6906 static struct iv_ca
*
6907 get_initial_solution (struct ivopts_data
*data
, bool originalp
)
6910 struct iv_ca
*ivs
= iv_ca_new (data
);
6912 for (i
= 0; i
< data
->vgroups
.length (); i
++)
6913 if (!try_add_cand_for (data
, ivs
, data
->vgroups
[i
], originalp
))
6922 /* Tries to improve set of induction variables IVS. TRY_REPLACE_P
6923 points to a bool variable, this function tries to break local
6924 optimal fixed-point by replacing candidates in IVS if it's true. */
6927 try_improve_iv_set (struct ivopts_data
*data
,
6928 struct iv_ca
*ivs
, bool *try_replace_p
)
6931 comp_cost acost
, best_cost
= iv_ca_cost (ivs
);
6932 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
, *tmp_delta
;
6933 struct iv_cand
*cand
;
6935 /* Try extending the set of induction variables by one. */
6936 for (i
= 0; i
< data
->vcands
.length (); i
++)
6938 cand
= data
->vcands
[i
];
6940 if (iv_ca_cand_used_p (ivs
, cand
))
6943 acost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, &n_ivs
, false);
6947 /* If we successfully added the candidate and the set is small enough,
6948 try optimizing it by removing other candidates. */
6949 if (n_ivs
<= ALWAYS_PRUNE_CAND_SET_BOUND
)
6951 iv_ca_delta_commit (data
, ivs
, act_delta
, true);
6952 acost
= iv_ca_prune (data
, ivs
, cand
, &tmp_delta
);
6953 iv_ca_delta_commit (data
, ivs
, act_delta
, false);
6954 act_delta
= iv_ca_delta_join (act_delta
, tmp_delta
);
6957 if (acost
< best_cost
)
6960 iv_ca_delta_free (&best_delta
);
6961 best_delta
= act_delta
;
6964 iv_ca_delta_free (&act_delta
);
6969 /* Try removing the candidates from the set instead. */
6970 best_cost
= iv_ca_prune (data
, ivs
, NULL
, &best_delta
);
6972 if (!best_delta
&& *try_replace_p
)
6974 *try_replace_p
= false;
6975 /* So far candidate selecting algorithm tends to choose fewer IVs
6976 so that it can handle cases in which loops have many variables
6977 but the best choice is often to use only one general biv. One
6978 weakness is it can't handle opposite cases, in which different
6979 candidates should be chosen with respect to each use. To solve
6980 the problem, we replace candidates in a manner described by the
6981 comments of iv_ca_replace, thus give general algorithm a chance
6982 to break local optimal fixed-point in these cases. */
6983 best_cost
= iv_ca_replace (data
, ivs
, &best_delta
);
6990 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
6991 gcc_assert (best_cost
== iv_ca_cost (ivs
));
6992 iv_ca_delta_free (&best_delta
);
6996 /* Attempts to find the optimal set of induction variables. We do simple
6997 greedy heuristic -- we try to replace at most one candidate in the selected
6998 solution and remove the unused ivs while this improves the cost. */
7000 static struct iv_ca
*
7001 find_optimal_iv_set_1 (struct ivopts_data
*data
, bool originalp
)
7004 bool try_replace_p
= true;
7006 /* Get the initial solution. */
7007 set
= get_initial_solution (data
, originalp
);
7010 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7011 fprintf (dump_file
, "Unable to substitute for ivs, failed.\n");
7015 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7017 fprintf (dump_file
, "Initial set of candidates:\n");
7018 iv_ca_dump (data
, dump_file
, set
);
7021 while (try_improve_iv_set (data
, set
, &try_replace_p
))
7023 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7025 fprintf (dump_file
, "Improved to:\n");
7026 iv_ca_dump (data
, dump_file
, set
);
7033 static struct iv_ca
*
7034 find_optimal_iv_set (struct ivopts_data
*data
)
7037 comp_cost cost
, origcost
;
7038 struct iv_ca
*set
, *origset
;
7040 /* Determine the cost based on a strategy that starts with original IVs,
7041 and try again using a strategy that prefers candidates not based
7043 origset
= find_optimal_iv_set_1 (data
, true);
7044 set
= find_optimal_iv_set_1 (data
, false);
7046 if (!origset
&& !set
)
7049 origcost
= origset
? iv_ca_cost (origset
) : infinite_cost
;
7050 cost
= set
? iv_ca_cost (set
) : infinite_cost
;
7052 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7054 fprintf (dump_file
, "Original cost %d (complexity %d)\n\n",
7055 origcost
.cost
, origcost
.complexity
);
7056 fprintf (dump_file
, "Final cost %d (complexity %d)\n\n",
7057 cost
.cost
, cost
.complexity
);
7060 /* Choose the one with the best cost. */
7061 if (origcost
<= cost
)
7068 iv_ca_free (&origset
);
7070 for (i
= 0; i
< data
->vgroups
.length (); i
++)
7072 struct iv_group
*group
= data
->vgroups
[i
];
7073 group
->selected
= iv_ca_cand_for_group (set
, group
)->cand
;
7079 /* Creates a new induction variable corresponding to CAND. */
7082 create_new_iv (struct ivopts_data
*data
, struct iv_cand
*cand
)
7084 gimple_stmt_iterator incr_pos
;
7087 struct iv_group
*group
;
7096 incr_pos
= gsi_last_bb (ip_normal_pos (data
->current_loop
));
7100 incr_pos
= gsi_last_bb (ip_end_pos (data
->current_loop
));
7108 incr_pos
= gsi_for_stmt (cand
->incremented_at
);
7112 /* Mark that the iv is preserved. */
7113 name_info (data
, cand
->var_before
)->preserve_biv
= true;
7114 name_info (data
, cand
->var_after
)->preserve_biv
= true;
7116 /* Rewrite the increment so that it uses var_before directly. */
7117 use
= find_interesting_uses_op (data
, cand
->var_after
);
7118 group
= data
->vgroups
[use
->group_id
];
7119 group
->selected
= cand
;
7123 gimple_add_tmp_var (cand
->var_before
);
7125 base
= unshare_expr (cand
->iv
->base
);
7127 create_iv (base
, unshare_expr (cand
->iv
->step
),
7128 cand
->var_before
, data
->current_loop
,
7129 &incr_pos
, after
, &cand
->var_before
, &cand
->var_after
);
7132 /* Creates new induction variables described in SET. */
7135 create_new_ivs (struct ivopts_data
*data
, struct iv_ca
*set
)
7138 struct iv_cand
*cand
;
7141 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
7143 cand
= data
->vcands
[i
];
7144 create_new_iv (data
, cand
);
7147 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7149 fprintf (dump_file
, "Selected IV set for loop %d",
7150 data
->current_loop
->num
);
7151 if (data
->loop_loc
!= UNKNOWN_LOCATION
)
7152 fprintf (dump_file
, " at %s:%d", LOCATION_FILE (data
->loop_loc
),
7153 LOCATION_LINE (data
->loop_loc
));
7154 fprintf (dump_file
, ", " HOST_WIDE_INT_PRINT_DEC
" avg niters",
7155 avg_loop_niter (data
->current_loop
));
7156 fprintf (dump_file
, ", " HOST_WIDE_INT_PRINT_UNSIGNED
" expressions",
7157 (unsigned HOST_WIDE_INT
) set
->used_inv_exprs
->elements ());
7158 fprintf (dump_file
, ", %lu IVs:\n", bitmap_count_bits (set
->cands
));
7159 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
7161 cand
= data
->vcands
[i
];
7162 dump_cand (dump_file
, cand
);
7164 fprintf (dump_file
, "\n");
7168 /* Rewrites USE (definition of iv used in a nonlinear expression)
7169 using candidate CAND. */
7172 rewrite_use_nonlinear_expr (struct ivopts_data
*data
,
7173 struct iv_use
*use
, struct iv_cand
*cand
)
7178 gimple_stmt_iterator bsi
;
7180 /* An important special case -- if we are asked to express value of
7181 the original iv by itself, just exit; there is no need to
7182 introduce a new computation (that might also need casting the
7183 variable to unsigned and back). */
7184 if (cand
->pos
== IP_ORIGINAL
7185 && cand
->incremented_at
== use
->stmt
)
7187 enum tree_code stmt_code
;
7189 gcc_assert (is_gimple_assign (use
->stmt
));
7190 gcc_assert (gimple_assign_lhs (use
->stmt
) == cand
->var_after
);
7192 /* Check whether we may leave the computation unchanged.
7193 This is the case only if it does not rely on other
7194 computations in the loop -- otherwise, the computation
7195 we rely upon may be removed in remove_unused_ivs,
7196 thus leading to ICE. */
7197 stmt_code
= gimple_assign_rhs_code (use
->stmt
);
7198 if (stmt_code
== PLUS_EXPR
7199 || stmt_code
== MINUS_EXPR
7200 || stmt_code
== POINTER_PLUS_EXPR
)
7202 if (gimple_assign_rhs1 (use
->stmt
) == cand
->var_before
)
7203 op
= gimple_assign_rhs2 (use
->stmt
);
7204 else if (gimple_assign_rhs2 (use
->stmt
) == cand
->var_before
)
7205 op
= gimple_assign_rhs1 (use
->stmt
);
7212 if (op
&& expr_invariant_in_loop_p (data
->current_loop
, op
))
7216 comp
= get_computation (data
->current_loop
, use
, cand
);
7217 gcc_assert (comp
!= NULL_TREE
);
7219 switch (gimple_code (use
->stmt
))
7222 tgt
= PHI_RESULT (use
->stmt
);
7224 /* If we should keep the biv, do not replace it. */
7225 if (name_info (data
, tgt
)->preserve_biv
)
7228 bsi
= gsi_after_labels (gimple_bb (use
->stmt
));
7232 tgt
= gimple_assign_lhs (use
->stmt
);
7233 bsi
= gsi_for_stmt (use
->stmt
);
7240 if (!valid_gimple_rhs_p (comp
)
7241 || (gimple_code (use
->stmt
) != GIMPLE_PHI
7242 /* We can't allow re-allocating the stmt as it might be pointed
7244 && (get_gimple_rhs_num_ops (TREE_CODE (comp
))
7245 >= gimple_num_ops (gsi_stmt (bsi
)))))
7247 comp
= force_gimple_operand_gsi (&bsi
, comp
, true, NULL_TREE
,
7248 true, GSI_SAME_STMT
);
7249 if (POINTER_TYPE_P (TREE_TYPE (tgt
)))
7251 duplicate_ssa_name_ptr_info (comp
, SSA_NAME_PTR_INFO (tgt
));
7252 /* As this isn't a plain copy we have to reset alignment
7254 if (SSA_NAME_PTR_INFO (comp
))
7255 mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (comp
));
7259 if (gimple_code (use
->stmt
) == GIMPLE_PHI
)
7261 ass
= gimple_build_assign (tgt
, comp
);
7262 gsi_insert_before (&bsi
, ass
, GSI_SAME_STMT
);
7264 bsi
= gsi_for_stmt (use
->stmt
);
7265 remove_phi_node (&bsi
, false);
7269 gimple_assign_set_rhs_from_tree (&bsi
, comp
);
7270 use
->stmt
= gsi_stmt (bsi
);
7274 /* Performs a peephole optimization to reorder the iv update statement with
7275 a mem ref to enable instruction combining in later phases. The mem ref uses
7276 the iv value before the update, so the reordering transformation requires
7277 adjustment of the offset. CAND is the selected IV_CAND.
7281 t = MEM_REF (base, iv1, 8, 16); // base, index, stride, offset
7289 directly propagating t over to (1) will introduce overlapping live range
7290 thus increase register pressure. This peephole transform it into:
7294 t = MEM_REF (base, iv2, 8, 8);
7301 adjust_iv_update_pos (struct iv_cand
*cand
, struct iv_use
*use
)
7304 gimple
*iv_update
, *stmt
;
7306 gimple_stmt_iterator gsi
, gsi_iv
;
7308 if (cand
->pos
!= IP_NORMAL
)
7311 var_after
= cand
->var_after
;
7312 iv_update
= SSA_NAME_DEF_STMT (var_after
);
7314 bb
= gimple_bb (iv_update
);
7315 gsi
= gsi_last_nondebug_bb (bb
);
7316 stmt
= gsi_stmt (gsi
);
7318 /* Only handle conditional statement for now. */
7319 if (gimple_code (stmt
) != GIMPLE_COND
)
7322 gsi_prev_nondebug (&gsi
);
7323 stmt
= gsi_stmt (gsi
);
7324 if (stmt
!= iv_update
)
7327 gsi_prev_nondebug (&gsi
);
7328 if (gsi_end_p (gsi
))
7331 stmt
= gsi_stmt (gsi
);
7332 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
7335 if (stmt
!= use
->stmt
)
7338 if (TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
7341 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7343 fprintf (dump_file
, "Reordering \n");
7344 print_gimple_stmt (dump_file
, iv_update
, 0, 0);
7345 print_gimple_stmt (dump_file
, use
->stmt
, 0, 0);
7346 fprintf (dump_file
, "\n");
7349 gsi
= gsi_for_stmt (use
->stmt
);
7350 gsi_iv
= gsi_for_stmt (iv_update
);
7351 gsi_move_before (&gsi_iv
, &gsi
);
7353 cand
->pos
= IP_BEFORE_USE
;
7354 cand
->incremented_at
= use
->stmt
;
7357 /* Rewrites USE (address that is an iv) using candidate CAND. */
7360 rewrite_use_address (struct ivopts_data
*data
,
7361 struct iv_use
*use
, struct iv_cand
*cand
)
7364 gimple_stmt_iterator bsi
= gsi_for_stmt (use
->stmt
);
7365 tree base_hint
= NULL_TREE
;
7369 adjust_iv_update_pos (cand
, use
);
7370 ok
= get_computation_aff (data
->current_loop
, use
, cand
, use
->stmt
, &aff
);
7372 unshare_aff_combination (&aff
);
7374 /* To avoid undefined overflow problems, all IV candidates use unsigned
7375 integer types. The drawback is that this makes it impossible for
7376 create_mem_ref to distinguish an IV that is based on a memory object
7377 from one that represents simply an offset.
7379 To work around this problem, we pass a hint to create_mem_ref that
7380 indicates which variable (if any) in aff is an IV based on a memory
7381 object. Note that we only consider the candidate. If this is not
7382 based on an object, the base of the reference is in some subexpression
7383 of the use -- but these will use pointer types, so they are recognized
7384 by the create_mem_ref heuristics anyway. */
7385 if (cand
->iv
->base_object
)
7386 base_hint
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
7388 iv
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
7389 ref
= create_mem_ref (&bsi
, TREE_TYPE (*use
->op_p
), &aff
,
7390 reference_alias_ptr_type (*use
->op_p
),
7391 iv
, base_hint
, data
->speed
);
7392 copy_ref_info (ref
, *use
->op_p
);
7396 /* Rewrites USE (the condition such that one of the arguments is an iv) using
7400 rewrite_use_compare (struct ivopts_data
*data
,
7401 struct iv_use
*use
, struct iv_cand
*cand
)
7403 tree comp
, *var_p
, op
, bound
;
7404 gimple_stmt_iterator bsi
= gsi_for_stmt (use
->stmt
);
7405 enum tree_code compare
;
7406 struct iv_group
*group
= data
->vgroups
[use
->group_id
];
7407 struct cost_pair
*cp
= get_group_iv_cost (data
, group
, cand
);
7413 tree var
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
7414 tree var_type
= TREE_TYPE (var
);
7417 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7419 fprintf (dump_file
, "Replacing exit test: ");
7420 print_gimple_stmt (dump_file
, use
->stmt
, 0, TDF_SLIM
);
7423 bound
= unshare_expr (fold_convert (var_type
, bound
));
7424 op
= force_gimple_operand (bound
, &stmts
, true, NULL_TREE
);
7426 gsi_insert_seq_on_edge_immediate (
7427 loop_preheader_edge (data
->current_loop
),
7430 gcond
*cond_stmt
= as_a
<gcond
*> (use
->stmt
);
7431 gimple_cond_set_lhs (cond_stmt
, var
);
7432 gimple_cond_set_code (cond_stmt
, compare
);
7433 gimple_cond_set_rhs (cond_stmt
, op
);
7437 /* The induction variable elimination failed; just express the original
7439 comp
= get_computation (data
->current_loop
, use
, cand
);
7440 gcc_assert (comp
!= NULL_TREE
);
7442 ok
= extract_cond_operands (data
, use
->stmt
, &var_p
, NULL
, NULL
, NULL
);
7445 *var_p
= force_gimple_operand_gsi (&bsi
, comp
, true, SSA_NAME_VAR (*var_p
),
7446 true, GSI_SAME_STMT
);
7449 /* Rewrite the groups using the selected induction variables. */
7452 rewrite_groups (struct ivopts_data
*data
)
7456 for (i
= 0; i
< data
->vgroups
.length (); i
++)
7458 struct iv_group
*group
= data
->vgroups
[i
];
7459 struct iv_cand
*cand
= group
->selected
;
7463 if (group
->type
== USE_NONLINEAR_EXPR
)
7465 for (j
= 0; j
< group
->vuses
.length (); j
++)
7467 rewrite_use_nonlinear_expr (data
, group
->vuses
[j
], cand
);
7468 update_stmt (group
->vuses
[j
]->stmt
);
7471 else if (group
->type
== USE_ADDRESS
)
7473 for (j
= 0; j
< group
->vuses
.length (); j
++)
7475 rewrite_use_address (data
, group
->vuses
[j
], cand
);
7476 update_stmt (group
->vuses
[j
]->stmt
);
7481 gcc_assert (group
->type
== USE_COMPARE
);
7483 for (j
= 0; j
< group
->vuses
.length (); j
++)
7485 rewrite_use_compare (data
, group
->vuses
[j
], cand
);
7486 update_stmt (group
->vuses
[j
]->stmt
);
7492 /* Removes the ivs that are not used after rewriting. */
7495 remove_unused_ivs (struct ivopts_data
*data
)
7499 bitmap toremove
= BITMAP_ALLOC (NULL
);
7501 /* Figure out an order in which to release SSA DEFs so that we don't
7502 release something that we'd have to propagate into a debug stmt
7504 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
7506 struct version_info
*info
;
7508 info
= ver_info (data
, j
);
7510 && !integer_zerop (info
->iv
->step
)
7512 && !info
->iv
->nonlin_use
7513 && !info
->preserve_biv
)
7515 bitmap_set_bit (toremove
, SSA_NAME_VERSION (info
->iv
->ssa_name
));
7517 tree def
= info
->iv
->ssa_name
;
7519 if (MAY_HAVE_DEBUG_STMTS
&& SSA_NAME_DEF_STMT (def
))
7521 imm_use_iterator imm_iter
;
7522 use_operand_p use_p
;
7526 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, def
)
7528 if (!gimple_debug_bind_p (stmt
))
7531 /* We just want to determine whether to do nothing
7532 (count == 0), to substitute the computed
7533 expression into a single use of the SSA DEF by
7534 itself (count == 1), or to use a debug temp
7535 because the SSA DEF is used multiple times or as
7536 part of a larger expression (count > 1). */
7538 if (gimple_debug_bind_get_value (stmt
) != def
)
7542 BREAK_FROM_IMM_USE_STMT (imm_iter
);
7548 struct iv_use dummy_use
;
7549 struct iv_cand
*best_cand
= NULL
, *cand
;
7550 unsigned i
, best_pref
= 0, cand_pref
;
7552 memset (&dummy_use
, 0, sizeof (dummy_use
));
7553 dummy_use
.iv
= info
->iv
;
7554 for (i
= 0; i
< data
->vgroups
.length () && i
< 64; i
++)
7556 cand
= data
->vgroups
[i
]->selected
;
7557 if (cand
== best_cand
)
7559 cand_pref
= operand_equal_p (cand
->iv
->step
,
7563 += TYPE_MODE (TREE_TYPE (cand
->iv
->base
))
7564 == TYPE_MODE (TREE_TYPE (info
->iv
->base
))
7567 += TREE_CODE (cand
->iv
->base
) == INTEGER_CST
7569 if (best_cand
== NULL
|| best_pref
< cand_pref
)
7572 best_pref
= cand_pref
;
7579 tree comp
= get_computation_at (data
->current_loop
,
7580 &dummy_use
, best_cand
,
7581 SSA_NAME_DEF_STMT (def
));
7587 tree vexpr
= make_node (DEBUG_EXPR_DECL
);
7588 DECL_ARTIFICIAL (vexpr
) = 1;
7589 TREE_TYPE (vexpr
) = TREE_TYPE (comp
);
7590 if (SSA_NAME_VAR (def
))
7591 DECL_MODE (vexpr
) = DECL_MODE (SSA_NAME_VAR (def
));
7593 DECL_MODE (vexpr
) = TYPE_MODE (TREE_TYPE (vexpr
));
7595 = gimple_build_debug_bind (vexpr
, comp
, NULL
);
7596 gimple_stmt_iterator gsi
;
7598 if (gimple_code (SSA_NAME_DEF_STMT (def
)) == GIMPLE_PHI
)
7599 gsi
= gsi_after_labels (gimple_bb
7600 (SSA_NAME_DEF_STMT (def
)));
7602 gsi
= gsi_for_stmt (SSA_NAME_DEF_STMT (def
));
7604 gsi_insert_before (&gsi
, def_temp
, GSI_SAME_STMT
);
7608 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, def
)
7610 if (!gimple_debug_bind_p (stmt
))
7613 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
7614 SET_USE (use_p
, comp
);
7622 release_defs_bitset (toremove
);
7624 BITMAP_FREE (toremove
);
7627 /* Frees memory occupied by struct tree_niter_desc in *VALUE. Callback
7628 for hash_map::traverse. */
7631 free_tree_niter_desc (edge
const &, tree_niter_desc
*const &value
, void *)
7637 /* Frees data allocated by the optimization of a single loop. */
7640 free_loop_data (struct ivopts_data
*data
)
7648 data
->niters
->traverse
<void *, free_tree_niter_desc
> (NULL
);
7649 delete data
->niters
;
7650 data
->niters
= NULL
;
7653 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
7655 struct version_info
*info
;
7657 info
= ver_info (data
, i
);
7659 info
->has_nonlin_use
= false;
7660 info
->preserve_biv
= false;
7663 bitmap_clear (data
->relevant
);
7664 bitmap_clear (data
->important_candidates
);
7666 for (i
= 0; i
< data
->vgroups
.length (); i
++)
7668 struct iv_group
*group
= data
->vgroups
[i
];
7670 for (j
= 0; j
< group
->vuses
.length (); j
++)
7671 free (group
->vuses
[j
]);
7672 group
->vuses
.release ();
7674 BITMAP_FREE (group
->related_cands
);
7675 for (j
= 0; j
< group
->n_map_members
; j
++)
7676 if (group
->cost_map
[j
].depends_on
)
7677 BITMAP_FREE (group
->cost_map
[j
].depends_on
);
7679 free (group
->cost_map
);
7682 data
->vgroups
.truncate (0);
7684 for (i
= 0; i
< data
->vcands
.length (); i
++)
7686 struct iv_cand
*cand
= data
->vcands
[i
];
7688 if (cand
->depends_on
)
7689 BITMAP_FREE (cand
->depends_on
);
7692 data
->vcands
.truncate (0);
7694 if (data
->version_info_size
< num_ssa_names
)
7696 data
->version_info_size
= 2 * num_ssa_names
;
7697 free (data
->version_info
);
7698 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
7701 data
->max_inv_id
= 0;
7703 FOR_EACH_VEC_ELT (decl_rtl_to_reset
, i
, obj
)
7704 SET_DECL_RTL (obj
, NULL_RTX
);
7706 decl_rtl_to_reset
.truncate (0);
7708 data
->inv_expr_tab
->empty ();
7709 data
->max_inv_expr_id
= 0;
7711 data
->iv_common_cand_tab
->empty ();
7712 data
->iv_common_cands
.truncate (0);
7715 /* Finalizes data structures used by the iv optimization pass. LOOPS is the
7719 tree_ssa_iv_optimize_finalize (struct ivopts_data
*data
)
7721 free_loop_data (data
);
7722 free (data
->version_info
);
7723 BITMAP_FREE (data
->relevant
);
7724 BITMAP_FREE (data
->important_candidates
);
7726 decl_rtl_to_reset
.release ();
7727 data
->vgroups
.release ();
7728 data
->vcands
.release ();
7729 delete data
->inv_expr_tab
;
7730 data
->inv_expr_tab
= NULL
;
7731 free_affine_expand_cache (&data
->name_expansion_cache
);
7732 delete data
->iv_common_cand_tab
;
7733 data
->iv_common_cand_tab
= NULL
;
7734 data
->iv_common_cands
.release ();
7735 obstack_free (&data
->iv_obstack
, NULL
);
7738 /* Returns true if the loop body BODY includes any function calls. */
7741 loop_body_includes_call (basic_block
*body
, unsigned num_nodes
)
7743 gimple_stmt_iterator gsi
;
7746 for (i
= 0; i
< num_nodes
; i
++)
7747 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
7749 gimple
*stmt
= gsi_stmt (gsi
);
7750 if (is_gimple_call (stmt
)
7751 && !gimple_call_internal_p (stmt
)
7752 && !is_inexpensive_builtin (gimple_call_fndecl (stmt
)))
7758 /* Optimizes the LOOP. Returns true if anything changed. */
7761 tree_ssa_iv_optimize_loop (struct ivopts_data
*data
, struct loop
*loop
)
7763 bool changed
= false;
7764 struct iv_ca
*iv_ca
;
7765 edge exit
= single_dom_exit (loop
);
7768 gcc_assert (!data
->niters
);
7769 data
->current_loop
= loop
;
7770 data
->loop_loc
= find_loop_location (loop
);
7771 data
->speed
= optimize_loop_for_speed_p (loop
);
7773 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7775 fprintf (dump_file
, "Processing loop %d", loop
->num
);
7776 if (data
->loop_loc
!= UNKNOWN_LOCATION
)
7777 fprintf (dump_file
, " at %s:%d", LOCATION_FILE (data
->loop_loc
),
7778 LOCATION_LINE (data
->loop_loc
));
7779 fprintf (dump_file
, "\n");
7783 fprintf (dump_file
, " single exit %d -> %d, exit condition ",
7784 exit
->src
->index
, exit
->dest
->index
);
7785 print_gimple_stmt (dump_file
, last_stmt (exit
->src
), 0, TDF_SLIM
);
7786 fprintf (dump_file
, "\n");
7789 fprintf (dump_file
, "\n");
7792 body
= get_loop_body (loop
);
7793 data
->body_includes_call
= loop_body_includes_call (body
, loop
->num_nodes
);
7794 renumber_gimple_stmt_uids_in_blocks (body
, loop
->num_nodes
);
7797 data
->loop_single_exit_p
= exit
!= NULL
&& loop_only_exit_p (loop
, exit
);
7799 /* For each ssa name determines whether it behaves as an induction variable
7801 if (!find_induction_variables (data
))
7804 /* Finds interesting uses (item 1). */
7805 find_interesting_uses (data
);
7806 if (data
->vgroups
.length () > MAX_CONSIDERED_GROUPS
)
7809 /* Finds candidates for the induction variables (item 2). */
7810 find_iv_candidates (data
);
7812 /* Calculates the costs (item 3, part 1). */
7813 determine_iv_costs (data
);
7814 determine_group_iv_costs (data
);
7815 determine_set_costs (data
);
7817 /* Find the optimal set of induction variables (item 3, part 2). */
7818 iv_ca
= find_optimal_iv_set (data
);
7823 /* Create the new induction variables (item 4, part 1). */
7824 create_new_ivs (data
, iv_ca
);
7825 iv_ca_free (&iv_ca
);
7827 /* Rewrite the uses (item 4, part 2). */
7828 rewrite_groups (data
);
7830 /* Remove the ivs that are unused after rewriting. */
7831 remove_unused_ivs (data
);
7833 /* We have changed the structure of induction variables; it might happen
7834 that definitions in the scev database refer to some of them that were
7839 free_loop_data (data
);
7844 /* Main entry point. Optimizes induction variables in loops. */
7847 tree_ssa_iv_optimize (void)
7850 struct ivopts_data data
;
7852 tree_ssa_iv_optimize_init (&data
);
7854 /* Optimize the loops starting with the innermost ones. */
7855 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
7857 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7858 flow_loop_dump (loop
, dump_file
, NULL
, 1);
7860 tree_ssa_iv_optimize_loop (&data
, loop
);
7863 tree_ssa_iv_optimize_finalize (&data
);