1 /* Induction variable optimizations.
2 Copyright (C) 2003-2017 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"
82 #include "insn-config.h"
86 #include "gimple-pretty-print.h"
88 #include "fold-const.h"
89 #include "stor-layout.h"
92 #include "gimple-iterator.h"
93 #include "gimplify-me.h"
95 #include "tree-ssa-loop-ivopts.h"
96 #include "tree-ssa-loop-manip.h"
97 #include "tree-ssa-loop-niter.h"
98 #include "tree-ssa-loop.h"
101 #include "tree-dfa.h"
102 #include "tree-ssa.h"
104 #include "tree-scalar-evolution.h"
106 #include "tree-affine.h"
107 #include "tree-ssa-propagate.h"
108 #include "tree-ssa-address.h"
109 #include "builtins.h"
110 #include "tree-vectorizer.h"
112 /* FIXME: Expressions are expanded to RTL in this pass to determine the
113 cost of different addressing modes. This should be moved to a TBD
114 interface between the GIMPLE and RTL worlds. */
116 /* The infinite cost. */
117 #define INFTY 10000000
119 /* Returns the expected number of loop iterations for LOOP.
120 The average trip count is computed from profile data if it
123 static inline HOST_WIDE_INT
124 avg_loop_niter (struct loop
*loop
)
126 HOST_WIDE_INT niter
= estimated_stmt_executions_int (loop
);
129 niter
= likely_max_stmt_executions_int (loop
);
131 if (niter
== -1 || niter
> PARAM_VALUE (PARAM_AVG_LOOP_NITER
))
132 return PARAM_VALUE (PARAM_AVG_LOOP_NITER
);
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 enum tree_code comp
; /* For iv elimination, the comparison. */
350 bitmap inv_vars
; /* The list of invariant ssa_vars that have to be
351 preserved when representing iv_use with iv_cand. */
352 bitmap inv_exprs
; /* The list of newly created invariant expressions
353 when representing iv_use with iv_cand. */
354 tree value
; /* For final value elimination, the expression for
355 the final value of the iv. For iv elimination,
356 the new bound to compare with. */
362 unsigned id
; /* The id of the use. */
363 unsigned group_id
; /* The group id the use belongs to. */
364 enum use_type type
; /* Type of the use. */
365 struct iv
*iv
; /* The induction variable it is based on. */
366 gimple
*stmt
; /* Statement in that it occurs. */
367 tree
*op_p
; /* The place where it occurs. */
369 tree addr_base
; /* Base address with const offset stripped. */
370 unsigned HOST_WIDE_INT addr_offset
;
371 /* Const offset stripped from base address. */
377 /* The id of the group. */
379 /* Uses of the group are of the same type. */
381 /* The set of "related" IV candidates, plus the important ones. */
382 bitmap related_cands
;
383 /* Number of IV candidates in the cost_map. */
384 unsigned n_map_members
;
385 /* The costs wrto the iv candidates. */
386 struct cost_pair
*cost_map
;
387 /* The selected candidate for the group. */
388 struct iv_cand
*selected
;
389 /* Uses in the group. */
390 vec
<struct iv_use
*> vuses
;
393 /* The position where the iv is computed. */
396 IP_NORMAL
, /* At the end, just before the exit condition. */
397 IP_END
, /* At the end of the latch block. */
398 IP_BEFORE_USE
, /* Immediately before a specific use. */
399 IP_AFTER_USE
, /* Immediately after a specific use. */
400 IP_ORIGINAL
/* The original biv. */
403 /* The induction variable candidate. */
406 unsigned id
; /* The number of the candidate. */
407 bool important
; /* Whether this is an "important" candidate, i.e. such
408 that it should be considered by all uses. */
409 ENUM_BITFIELD(iv_position
) pos
: 8; /* Where it is computed. */
410 gimple
*incremented_at
;/* For original biv, the statement where it is
412 tree var_before
; /* The variable used for it before increment. */
413 tree var_after
; /* The variable used for it after increment. */
414 struct iv
*iv
; /* The value of the candidate. NULL for
415 "pseudocandidate" used to indicate the possibility
416 to replace the final value of an iv by direct
417 computation of the value. */
418 unsigned cost
; /* Cost of the candidate. */
419 unsigned cost_step
; /* Cost of the candidate's increment operation. */
420 struct iv_use
*ainc_use
; /* For IP_{BEFORE,AFTER}_USE candidates, the place
421 where it is incremented. */
422 bitmap inv_vars
; /* The list of invariant ssa_vars used in step of the
424 bitmap inv_exprs
; /* If step is more complicated than a single ssa_var,
425 hanlde it as a new invariant expression which will
426 be hoisted out of loop. */
427 struct iv
*orig_iv
; /* The original iv if this cand is added from biv with
431 /* Hashtable entry for common candidate derived from iv uses. */
432 struct iv_common_cand
436 /* IV uses from which this common candidate is derived. */
437 auto_vec
<struct iv_use
*> uses
;
441 /* Hashtable helpers. */
443 struct iv_common_cand_hasher
: delete_ptr_hash
<iv_common_cand
>
445 static inline hashval_t
hash (const iv_common_cand
*);
446 static inline bool equal (const iv_common_cand
*, const iv_common_cand
*);
449 /* Hash function for possible common candidates. */
452 iv_common_cand_hasher::hash (const iv_common_cand
*ccand
)
457 /* Hash table equality function for common candidates. */
460 iv_common_cand_hasher::equal (const iv_common_cand
*ccand1
,
461 const iv_common_cand
*ccand2
)
463 return (ccand1
->hash
== ccand2
->hash
464 && operand_equal_p (ccand1
->base
, ccand2
->base
, 0)
465 && operand_equal_p (ccand1
->step
, ccand2
->step
, 0)
466 && (TYPE_PRECISION (TREE_TYPE (ccand1
->base
))
467 == TYPE_PRECISION (TREE_TYPE (ccand2
->base
))));
470 /* Loop invariant expression hashtable entry. */
472 struct iv_inv_expr_ent
474 /* Tree expression of the entry. */
476 /* Unique indentifier. */
482 /* Sort iv_inv_expr_ent pair A and B by id field. */
485 sort_iv_inv_expr_ent (const void *a
, const void *b
)
487 const iv_inv_expr_ent
* const *e1
= (const iv_inv_expr_ent
* const *) (a
);
488 const iv_inv_expr_ent
* const *e2
= (const iv_inv_expr_ent
* const *) (b
);
490 unsigned id1
= (*e1
)->id
;
491 unsigned id2
= (*e2
)->id
;
501 /* Hashtable helpers. */
503 struct iv_inv_expr_hasher
: free_ptr_hash
<iv_inv_expr_ent
>
505 static inline hashval_t
hash (const iv_inv_expr_ent
*);
506 static inline bool equal (const iv_inv_expr_ent
*, const iv_inv_expr_ent
*);
509 /* Hash function for loop invariant expressions. */
512 iv_inv_expr_hasher::hash (const iv_inv_expr_ent
*expr
)
517 /* Hash table equality function for expressions. */
520 iv_inv_expr_hasher::equal (const iv_inv_expr_ent
*expr1
,
521 const iv_inv_expr_ent
*expr2
)
523 return expr1
->hash
== expr2
->hash
524 && operand_equal_p (expr1
->expr
, expr2
->expr
, 0);
529 /* The currently optimized loop. */
530 struct loop
*current_loop
;
531 source_location loop_loc
;
533 /* Numbers of iterations for all exits of the current loop. */
534 hash_map
<edge
, tree_niter_desc
*> *niters
;
536 /* Number of registers used in it. */
539 /* The size of version_info array allocated. */
540 unsigned version_info_size
;
542 /* The array of information for the ssa names. */
543 struct version_info
*version_info
;
545 /* The hashtable of loop invariant expressions created
547 hash_table
<iv_inv_expr_hasher
> *inv_expr_tab
;
549 /* The bitmap of indices in version_info whose value was changed. */
552 /* The uses of induction variables. */
553 vec
<iv_group
*> vgroups
;
555 /* The candidates. */
556 vec
<iv_cand
*> vcands
;
558 /* A bitmap of important candidates. */
559 bitmap important_candidates
;
561 /* Cache used by tree_to_aff_combination_expand. */
562 hash_map
<tree
, name_expansion
*> *name_expansion_cache
;
564 /* The hashtable of common candidates derived from iv uses. */
565 hash_table
<iv_common_cand_hasher
> *iv_common_cand_tab
;
567 /* The common candidates. */
568 vec
<iv_common_cand
*> iv_common_cands
;
570 /* The maximum invariant variable id. */
571 unsigned max_inv_var_id
;
573 /* The maximum invariant expression id. */
574 unsigned max_inv_expr_id
;
576 /* Number of no_overflow BIVs which are not used in memory address. */
577 unsigned bivs_not_used_in_addr
;
579 /* Obstack for iv structure. */
580 struct obstack iv_obstack
;
582 /* Whether to consider just related and important candidates when replacing a
584 bool consider_all_candidates
;
586 /* Are we optimizing for speed? */
589 /* Whether the loop body includes any function calls. */
590 bool body_includes_call
;
592 /* Whether the loop body can only be exited via single exit. */
593 bool loop_single_exit_p
;
596 /* An assignment of iv candidates to uses. */
600 /* The number of uses covered by the assignment. */
603 /* Number of uses that cannot be expressed by the candidates in the set. */
606 /* Candidate assigned to a use, together with the related costs. */
607 struct cost_pair
**cand_for_group
;
609 /* Number of times each candidate is used. */
610 unsigned *n_cand_uses
;
612 /* The candidates used. */
615 /* The number of candidates in the set. */
618 /* The number of invariants needed, including both invariant variants and
619 invariant expressions. */
622 /* Total cost of expressing uses. */
623 comp_cost cand_use_cost
;
625 /* Total cost of candidates. */
628 /* Number of times each invariant variable is used. */
629 unsigned *n_inv_var_uses
;
631 /* Number of times each invariant expression is used. */
632 unsigned *n_inv_expr_uses
;
634 /* Total cost of the assignment. */
638 /* Difference of two iv candidate assignments. */
643 struct iv_group
*group
;
645 /* An old assignment (for rollback purposes). */
646 struct cost_pair
*old_cp
;
648 /* A new assignment. */
649 struct cost_pair
*new_cp
;
651 /* Next change in the list. */
652 struct iv_ca_delta
*next
;
655 /* Bound on number of candidates below that all candidates are considered. */
657 #define CONSIDER_ALL_CANDIDATES_BOUND \
658 ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
660 /* If there are more iv occurrences, we just give up (it is quite unlikely that
661 optimizing such a loop would help, and it would take ages). */
663 #define MAX_CONSIDERED_GROUPS \
664 ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
666 /* If there are at most this number of ivs in the set, try removing unnecessary
667 ivs from the set always. */
669 #define ALWAYS_PRUNE_CAND_SET_BOUND \
670 ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
672 /* The list of trees for that the decl_rtl field must be reset is stored
675 static vec
<tree
> decl_rtl_to_reset
;
677 static comp_cost
force_expr_to_var_cost (tree
, bool);
679 /* The single loop exit if it dominates the latch, NULL otherwise. */
682 single_dom_exit (struct loop
*loop
)
684 edge exit
= single_exit (loop
);
689 if (!just_once_each_iteration_p (loop
, exit
->src
))
695 /* Dumps information about the induction variable IV to FILE. Don't dump
696 variable's name if DUMP_NAME is FALSE. The information is dumped with
697 preceding spaces indicated by INDENT_LEVEL. */
700 dump_iv (FILE *file
, struct iv
*iv
, bool dump_name
, unsigned indent_level
)
703 const char spaces
[9] = {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '\0'};
705 if (indent_level
> 4)
707 p
= spaces
+ 8 - (indent_level
<< 1);
709 fprintf (file
, "%sIV struct:\n", p
);
710 if (iv
->ssa_name
&& dump_name
)
712 fprintf (file
, "%s SSA_NAME:\t", p
);
713 print_generic_expr (file
, iv
->ssa_name
, TDF_SLIM
);
714 fprintf (file
, "\n");
717 fprintf (file
, "%s Type:\t", p
);
718 print_generic_expr (file
, TREE_TYPE (iv
->base
), TDF_SLIM
);
719 fprintf (file
, "\n");
721 fprintf (file
, "%s Base:\t", p
);
722 print_generic_expr (file
, iv
->base
, TDF_SLIM
);
723 fprintf (file
, "\n");
725 fprintf (file
, "%s Step:\t", p
);
726 print_generic_expr (file
, iv
->step
, TDF_SLIM
);
727 fprintf (file
, "\n");
731 fprintf (file
, "%s Object:\t", p
);
732 print_generic_expr (file
, iv
->base_object
, TDF_SLIM
);
733 fprintf (file
, "\n");
736 fprintf (file
, "%s Biv:\t%c\n", p
, iv
->biv_p
? 'Y' : 'N');
738 fprintf (file
, "%s Overflowness wrto loop niter:\t%s\n",
739 p
, iv
->no_overflow
? "No-overflow" : "Overflow");
742 /* Dumps information about the USE to FILE. */
745 dump_use (FILE *file
, struct iv_use
*use
)
747 fprintf (file
, " Use %d.%d:\n", use
->group_id
, use
->id
);
748 fprintf (file
, " At stmt:\t");
749 print_gimple_stmt (file
, use
->stmt
, 0, 0);
750 fprintf (file
, " At pos:\t");
752 print_generic_expr (file
, *use
->op_p
, TDF_SLIM
);
753 fprintf (file
, "\n");
754 dump_iv (file
, use
->iv
, false, 2);
757 /* Dumps information about the uses to FILE. */
760 dump_groups (FILE *file
, struct ivopts_data
*data
)
763 struct iv_group
*group
;
765 for (i
= 0; i
< data
->vgroups
.length (); i
++)
767 group
= data
->vgroups
[i
];
768 fprintf (file
, "Group %d:\n", group
->id
);
769 if (group
->type
== USE_NONLINEAR_EXPR
)
770 fprintf (file
, " Type:\tGENERIC\n");
771 else if (group
->type
== USE_ADDRESS
)
772 fprintf (file
, " Type:\tADDRESS\n");
775 gcc_assert (group
->type
== USE_COMPARE
);
776 fprintf (file
, " Type:\tCOMPARE\n");
778 for (j
= 0; j
< group
->vuses
.length (); j
++)
779 dump_use (file
, group
->vuses
[j
]);
783 /* Dumps information about induction variable candidate CAND to FILE. */
786 dump_cand (FILE *file
, struct iv_cand
*cand
)
788 struct iv
*iv
= cand
->iv
;
790 fprintf (file
, "Candidate %d:\n", cand
->id
);
793 fprintf (file
, " Depend on inv.vars: ");
794 dump_bitmap (file
, cand
->inv_vars
);
798 fprintf (file
, " Depend on inv.exprs: ");
799 dump_bitmap (file
, cand
->inv_exprs
);
802 if (cand
->var_before
)
804 fprintf (file
, " Var befor: ");
805 print_generic_expr (file
, cand
->var_before
, TDF_SLIM
);
806 fprintf (file
, "\n");
810 fprintf (file
, " Var after: ");
811 print_generic_expr (file
, cand
->var_after
, TDF_SLIM
);
812 fprintf (file
, "\n");
818 fprintf (file
, " Incr POS: before exit test\n");
822 fprintf (file
, " Incr POS: before use %d\n", cand
->ainc_use
->id
);
826 fprintf (file
, " Incr POS: after use %d\n", cand
->ainc_use
->id
);
830 fprintf (file
, " Incr POS: at end\n");
834 fprintf (file
, " Incr POS: orig biv\n");
838 dump_iv (file
, iv
, false, 1);
841 /* Returns the info for ssa version VER. */
843 static inline struct version_info
*
844 ver_info (struct ivopts_data
*data
, unsigned ver
)
846 return data
->version_info
+ ver
;
849 /* Returns the info for ssa name NAME. */
851 static inline struct version_info
*
852 name_info (struct ivopts_data
*data
, tree name
)
854 return ver_info (data
, SSA_NAME_VERSION (name
));
857 /* Returns true if STMT is after the place where the IP_NORMAL ivs will be
861 stmt_after_ip_normal_pos (struct loop
*loop
, gimple
*stmt
)
863 basic_block bb
= ip_normal_pos (loop
), sbb
= gimple_bb (stmt
);
867 if (sbb
== loop
->latch
)
873 return stmt
== last_stmt (bb
);
876 /* Returns true if STMT if after the place where the original induction
877 variable CAND is incremented. If TRUE_IF_EQUAL is set, we return true
878 if the positions are identical. */
881 stmt_after_inc_pos (struct iv_cand
*cand
, gimple
*stmt
, bool true_if_equal
)
883 basic_block cand_bb
= gimple_bb (cand
->incremented_at
);
884 basic_block stmt_bb
= gimple_bb (stmt
);
886 if (!dominated_by_p (CDI_DOMINATORS
, stmt_bb
, cand_bb
))
889 if (stmt_bb
!= cand_bb
)
893 && gimple_uid (stmt
) == gimple_uid (cand
->incremented_at
))
895 return gimple_uid (stmt
) > gimple_uid (cand
->incremented_at
);
898 /* Returns true if STMT if after the place where the induction variable
899 CAND is incremented in LOOP. */
902 stmt_after_increment (struct loop
*loop
, struct iv_cand
*cand
, gimple
*stmt
)
910 return stmt_after_ip_normal_pos (loop
, stmt
);
914 return stmt_after_inc_pos (cand
, stmt
, false);
917 return stmt_after_inc_pos (cand
, stmt
, true);
924 /* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
927 abnormal_ssa_name_p (tree exp
)
932 if (TREE_CODE (exp
) != SSA_NAME
)
935 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
) != 0;
938 /* Returns false if BASE or INDEX contains a ssa name that occurs in an
939 abnormal phi node. Callback for for_each_index. */
942 idx_contains_abnormal_ssa_name_p (tree base
, tree
*index
,
943 void *data ATTRIBUTE_UNUSED
)
945 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
947 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 2)))
949 if (abnormal_ssa_name_p (TREE_OPERAND (base
, 3)))
953 return !abnormal_ssa_name_p (*index
);
956 /* Returns true if EXPR contains a ssa name that occurs in an
957 abnormal phi node. */
960 contains_abnormal_ssa_name_p (tree expr
)
963 enum tree_code_class codeclass
;
968 code
= TREE_CODE (expr
);
969 codeclass
= TREE_CODE_CLASS (code
);
971 if (code
== SSA_NAME
)
972 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr
) != 0;
974 if (code
== INTEGER_CST
975 || is_gimple_min_invariant (expr
))
978 if (code
== ADDR_EXPR
)
979 return !for_each_index (&TREE_OPERAND (expr
, 0),
980 idx_contains_abnormal_ssa_name_p
,
983 if (code
== COND_EXPR
)
984 return contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0))
985 || contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1))
986 || contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 2));
992 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 1)))
997 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr
, 0)))
1009 /* Returns the structure describing number of iterations determined from
1010 EXIT of DATA->current_loop, or NULL if something goes wrong. */
1012 static struct tree_niter_desc
*
1013 niter_for_exit (struct ivopts_data
*data
, edge exit
)
1015 struct tree_niter_desc
*desc
;
1016 tree_niter_desc
**slot
;
1020 data
->niters
= new hash_map
<edge
, tree_niter_desc
*>;
1024 slot
= data
->niters
->get (exit
);
1028 /* Try to determine number of iterations. We cannot safely work with ssa
1029 names that appear in phi nodes on abnormal edges, so that we do not
1030 create overlapping life ranges for them (PR 27283). */
1031 desc
= XNEW (struct tree_niter_desc
);
1032 if (!number_of_iterations_exit (data
->current_loop
,
1034 || contains_abnormal_ssa_name_p (desc
->niter
))
1039 data
->niters
->put (exit
, desc
);
1047 /* Returns the structure describing number of iterations determined from
1048 single dominating exit of DATA->current_loop, or NULL if something
1051 static struct tree_niter_desc
*
1052 niter_for_single_dom_exit (struct ivopts_data
*data
)
1054 edge exit
= single_dom_exit (data
->current_loop
);
1059 return niter_for_exit (data
, exit
);
1062 /* Initializes data structures used by the iv optimization pass, stored
1066 tree_ssa_iv_optimize_init (struct ivopts_data
*data
)
1068 data
->version_info_size
= 2 * num_ssa_names
;
1069 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
1070 data
->relevant
= BITMAP_ALLOC (NULL
);
1071 data
->important_candidates
= BITMAP_ALLOC (NULL
);
1072 data
->max_inv_var_id
= 0;
1073 data
->max_inv_expr_id
= 0;
1074 data
->niters
= NULL
;
1075 data
->vgroups
.create (20);
1076 data
->vcands
.create (20);
1077 data
->inv_expr_tab
= new hash_table
<iv_inv_expr_hasher
> (10);
1078 data
->name_expansion_cache
= NULL
;
1079 data
->iv_common_cand_tab
= new hash_table
<iv_common_cand_hasher
> (10);
1080 data
->iv_common_cands
.create (20);
1081 decl_rtl_to_reset
.create (20);
1082 gcc_obstack_init (&data
->iv_obstack
);
1085 /* Returns a memory object to that EXPR points. In case we are able to
1086 determine that it does not point to any such object, NULL is returned. */
1089 determine_base_object (tree expr
)
1091 enum tree_code code
= TREE_CODE (expr
);
1094 /* If this is a pointer casted to any type, we need to determine
1095 the base object for the pointer; so handle conversions before
1096 throwing away non-pointer expressions. */
1097 if (CONVERT_EXPR_P (expr
))
1098 return determine_base_object (TREE_OPERAND (expr
, 0));
1100 if (!POINTER_TYPE_P (TREE_TYPE (expr
)))
1109 obj
= TREE_OPERAND (expr
, 0);
1110 base
= get_base_address (obj
);
1115 if (TREE_CODE (base
) == MEM_REF
)
1116 return determine_base_object (TREE_OPERAND (base
, 0));
1118 return fold_convert (ptr_type_node
,
1119 build_fold_addr_expr (base
));
1121 case POINTER_PLUS_EXPR
:
1122 return determine_base_object (TREE_OPERAND (expr
, 0));
1126 /* Pointer addition is done solely using POINTER_PLUS_EXPR. */
1130 return fold_convert (ptr_type_node
, expr
);
1134 /* Return true if address expression with non-DECL_P operand appears
1138 contain_complex_addr_expr (tree expr
)
1143 switch (TREE_CODE (expr
))
1145 case POINTER_PLUS_EXPR
:
1148 res
|= contain_complex_addr_expr (TREE_OPERAND (expr
, 0));
1149 res
|= contain_complex_addr_expr (TREE_OPERAND (expr
, 1));
1153 return (!DECL_P (TREE_OPERAND (expr
, 0)));
1162 /* Allocates an induction variable with given initial value BASE and step STEP
1163 for loop LOOP. NO_OVERFLOW implies the iv doesn't overflow. */
1166 alloc_iv (struct ivopts_data
*data
, tree base
, tree step
,
1167 bool no_overflow
= false)
1170 struct iv
*iv
= (struct iv
*) obstack_alloc (&data
->iv_obstack
,
1171 sizeof (struct iv
));
1172 gcc_assert (step
!= NULL_TREE
);
1174 /* Lower address expression in base except ones with DECL_P as operand.
1176 1) More accurate cost can be computed for address expressions;
1177 2) Duplicate candidates won't be created for bases in different
1178 forms, like &a[0] and &a. */
1180 if ((TREE_CODE (expr
) == ADDR_EXPR
&& !DECL_P (TREE_OPERAND (expr
, 0)))
1181 || contain_complex_addr_expr (expr
))
1184 tree_to_aff_combination (expr
, TREE_TYPE (expr
), &comb
);
1185 base
= fold_convert (TREE_TYPE (base
), aff_combination_to_tree (&comb
));
1189 iv
->base_object
= determine_base_object (base
);
1192 iv
->nonlin_use
= NULL
;
1193 iv
->ssa_name
= NULL_TREE
;
1195 && !iv_can_overflow_p (data
->current_loop
, TREE_TYPE (base
),
1198 iv
->no_overflow
= no_overflow
;
1199 iv
->have_address_use
= false;
1204 /* Sets STEP and BASE for induction variable IV. NO_OVERFLOW implies the IV
1205 doesn't overflow. */
1208 set_iv (struct ivopts_data
*data
, tree iv
, tree base
, tree step
,
1211 struct version_info
*info
= name_info (data
, iv
);
1213 gcc_assert (!info
->iv
);
1215 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (iv
));
1216 info
->iv
= alloc_iv (data
, base
, step
, no_overflow
);
1217 info
->iv
->ssa_name
= iv
;
1220 /* Finds induction variable declaration for VAR. */
1223 get_iv (struct ivopts_data
*data
, tree var
)
1226 tree type
= TREE_TYPE (var
);
1228 if (!POINTER_TYPE_P (type
)
1229 && !INTEGRAL_TYPE_P (type
))
1232 if (!name_info (data
, var
)->iv
)
1234 bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
1237 || !flow_bb_inside_loop_p (data
->current_loop
, bb
))
1238 set_iv (data
, var
, var
, build_int_cst (type
, 0), true);
1241 return name_info (data
, var
)->iv
;
1244 /* Return the first non-invariant ssa var found in EXPR. */
1247 extract_single_var_from_expr (tree expr
)
1251 enum tree_code code
;
1253 if (!expr
|| is_gimple_min_invariant (expr
))
1256 code
= TREE_CODE (expr
);
1257 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1259 n
= TREE_OPERAND_LENGTH (expr
);
1260 for (i
= 0; i
< n
; i
++)
1262 tmp
= extract_single_var_from_expr (TREE_OPERAND (expr
, i
));
1268 return (TREE_CODE (expr
) == SSA_NAME
) ? expr
: NULL
;
1271 /* Finds basic ivs. */
1274 find_bivs (struct ivopts_data
*data
)
1278 tree step
, type
, base
, stop
;
1280 struct loop
*loop
= data
->current_loop
;
1283 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1287 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi
)))
1290 if (virtual_operand_p (PHI_RESULT (phi
)))
1293 if (!simple_iv (loop
, loop
, PHI_RESULT (phi
), &iv
, true))
1296 if (integer_zerop (iv
.step
))
1300 base
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1301 /* Stop expanding iv base at the first ssa var referred by iv step.
1302 Ideally we should stop at any ssa var, because that's expensive
1303 and unusual to happen, we just do it on the first one.
1305 See PR64705 for the rationale. */
1306 stop
= extract_single_var_from_expr (step
);
1307 base
= expand_simple_operations (base
, stop
);
1308 if (contains_abnormal_ssa_name_p (base
)
1309 || contains_abnormal_ssa_name_p (step
))
1312 type
= TREE_TYPE (PHI_RESULT (phi
));
1313 base
= fold_convert (type
, base
);
1316 if (POINTER_TYPE_P (type
))
1317 step
= convert_to_ptrofftype (step
);
1319 step
= fold_convert (type
, step
);
1322 set_iv (data
, PHI_RESULT (phi
), base
, step
, iv
.no_overflow
);
1329 /* Marks basic ivs. */
1332 mark_bivs (struct ivopts_data
*data
)
1337 struct iv
*iv
, *incr_iv
;
1338 struct loop
*loop
= data
->current_loop
;
1339 basic_block incr_bb
;
1342 data
->bivs_not_used_in_addr
= 0;
1343 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1347 iv
= get_iv (data
, PHI_RESULT (phi
));
1351 var
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
1352 def
= SSA_NAME_DEF_STMT (var
);
1353 /* Don't mark iv peeled from other one as biv. */
1355 && gimple_code (def
) == GIMPLE_PHI
1356 && gimple_bb (def
) == loop
->header
)
1359 incr_iv
= get_iv (data
, var
);
1363 /* If the increment is in the subloop, ignore it. */
1364 incr_bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
1365 if (incr_bb
->loop_father
!= data
->current_loop
1366 || (incr_bb
->flags
& BB_IRREDUCIBLE_LOOP
))
1370 incr_iv
->biv_p
= true;
1371 if (iv
->no_overflow
)
1372 data
->bivs_not_used_in_addr
++;
1373 if (incr_iv
->no_overflow
)
1374 data
->bivs_not_used_in_addr
++;
1378 /* Checks whether STMT defines a linear induction variable and stores its
1379 parameters to IV. */
1382 find_givs_in_stmt_scev (struct ivopts_data
*data
, gimple
*stmt
, affine_iv
*iv
)
1385 struct loop
*loop
= data
->current_loop
;
1387 iv
->base
= NULL_TREE
;
1388 iv
->step
= NULL_TREE
;
1390 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1393 lhs
= gimple_assign_lhs (stmt
);
1394 if (TREE_CODE (lhs
) != SSA_NAME
)
1397 if (!simple_iv (loop
, loop_containing_stmt (stmt
), lhs
, iv
, true))
1400 /* Stop expanding iv base at the first ssa var referred by iv step.
1401 Ideally we should stop at any ssa var, because that's expensive
1402 and unusual to happen, we just do it on the first one.
1404 See PR64705 for the rationale. */
1405 stop
= extract_single_var_from_expr (iv
->step
);
1406 iv
->base
= expand_simple_operations (iv
->base
, stop
);
1407 if (contains_abnormal_ssa_name_p (iv
->base
)
1408 || contains_abnormal_ssa_name_p (iv
->step
))
1411 /* If STMT could throw, then do not consider STMT as defining a GIV.
1412 While this will suppress optimizations, we can not safely delete this
1413 GIV and associated statements, even if it appears it is not used. */
1414 if (stmt_could_throw_p (stmt
))
1420 /* Finds general ivs in statement STMT. */
1423 find_givs_in_stmt (struct ivopts_data
*data
, gimple
*stmt
)
1427 if (!find_givs_in_stmt_scev (data
, stmt
, &iv
))
1430 set_iv (data
, gimple_assign_lhs (stmt
), iv
.base
, iv
.step
, iv
.no_overflow
);
1433 /* Finds general ivs in basic block BB. */
1436 find_givs_in_bb (struct ivopts_data
*data
, basic_block bb
)
1438 gimple_stmt_iterator bsi
;
1440 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1441 find_givs_in_stmt (data
, gsi_stmt (bsi
));
1444 /* Finds general ivs. */
1447 find_givs (struct ivopts_data
*data
)
1449 struct loop
*loop
= data
->current_loop
;
1450 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1453 for (i
= 0; i
< loop
->num_nodes
; i
++)
1454 find_givs_in_bb (data
, body
[i
]);
1458 /* For each ssa name defined in LOOP determines whether it is an induction
1459 variable and if so, its initial value and step. */
1462 find_induction_variables (struct ivopts_data
*data
)
1467 if (!find_bivs (data
))
1473 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1475 struct tree_niter_desc
*niter
= niter_for_single_dom_exit (data
);
1479 fprintf (dump_file
, " number of iterations ");
1480 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1481 if (!integer_zerop (niter
->may_be_zero
))
1483 fprintf (dump_file
, "; zero if ");
1484 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1486 fprintf (dump_file
, "\n");
1489 fprintf (dump_file
, "\n<Induction Vars>:\n");
1490 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1492 struct version_info
*info
= ver_info (data
, i
);
1493 if (info
->iv
&& info
->iv
->step
&& !integer_zerop (info
->iv
->step
))
1494 dump_iv (dump_file
, ver_info (data
, i
)->iv
, true, 0);
1501 /* Records a use of TYPE at *USE_P in STMT whose value is IV in GROUP.
1502 For address type use, ADDR_BASE is the stripped IV base, ADDR_OFFSET
1503 is the const offset stripped from IV base; for other types use, both
1504 are zero by default. */
1506 static struct iv_use
*
1507 record_use (struct iv_group
*group
, tree
*use_p
, struct iv
*iv
,
1508 gimple
*stmt
, enum use_type type
, tree addr_base
,
1509 unsigned HOST_WIDE_INT addr_offset
)
1511 struct iv_use
*use
= XCNEW (struct iv_use
);
1513 use
->id
= group
->vuses
.length ();
1514 use
->group_id
= group
->id
;
1519 use
->addr_base
= addr_base
;
1520 use
->addr_offset
= addr_offset
;
1522 group
->vuses
.safe_push (use
);
1526 /* Checks whether OP is a loop-level invariant and if so, records it.
1527 NONLINEAR_USE is true if the invariant is used in a way we do not
1528 handle specially. */
1531 record_invariant (struct ivopts_data
*data
, tree op
, bool nonlinear_use
)
1534 struct version_info
*info
;
1536 if (TREE_CODE (op
) != SSA_NAME
1537 || virtual_operand_p (op
))
1540 bb
= gimple_bb (SSA_NAME_DEF_STMT (op
));
1542 && flow_bb_inside_loop_p (data
->current_loop
, bb
))
1545 info
= name_info (data
, op
);
1547 info
->has_nonlin_use
|= nonlinear_use
;
1549 info
->inv_id
= ++data
->max_inv_var_id
;
1550 bitmap_set_bit (data
->relevant
, SSA_NAME_VERSION (op
));
1554 strip_offset (tree expr
, unsigned HOST_WIDE_INT
*offset
);
1556 /* Record a group of TYPE. */
1558 static struct iv_group
*
1559 record_group (struct ivopts_data
*data
, enum use_type type
)
1561 struct iv_group
*group
= XCNEW (struct iv_group
);
1563 group
->id
= data
->vgroups
.length ();
1565 group
->related_cands
= BITMAP_ALLOC (NULL
);
1566 group
->vuses
.create (1);
1568 data
->vgroups
.safe_push (group
);
1572 /* Record a use of TYPE at *USE_P in STMT whose value is IV in a group.
1573 New group will be created if there is no existing group for the use. */
1575 static struct iv_use
*
1576 record_group_use (struct ivopts_data
*data
, tree
*use_p
,
1577 struct iv
*iv
, gimple
*stmt
, enum use_type type
)
1579 tree addr_base
= NULL
;
1580 struct iv_group
*group
= NULL
;
1581 unsigned HOST_WIDE_INT addr_offset
= 0;
1583 /* Record non address type use in a new group. */
1584 if (type
== USE_ADDRESS
&& iv
->base_object
)
1588 addr_base
= strip_offset (iv
->base
, &addr_offset
);
1589 for (i
= 0; i
< data
->vgroups
.length (); i
++)
1593 group
= data
->vgroups
[i
];
1594 use
= group
->vuses
[0];
1595 if (use
->type
!= USE_ADDRESS
|| !use
->iv
->base_object
)
1598 /* Check if it has the same stripped base and step. */
1599 if (operand_equal_p (iv
->base_object
, use
->iv
->base_object
, 0)
1600 && operand_equal_p (iv
->step
, use
->iv
->step
, 0)
1601 && operand_equal_p (addr_base
, use
->addr_base
, 0))
1604 if (i
== data
->vgroups
.length ())
1609 group
= record_group (data
, type
);
1611 return record_use (group
, use_p
, iv
, stmt
, type
, addr_base
, addr_offset
);
1614 /* Checks whether the use OP is interesting and if so, records it. */
1616 static struct iv_use
*
1617 find_interesting_uses_op (struct ivopts_data
*data
, tree op
)
1623 if (TREE_CODE (op
) != SSA_NAME
)
1626 iv
= get_iv (data
, op
);
1632 gcc_assert (iv
->nonlin_use
->type
== USE_NONLINEAR_EXPR
);
1633 return iv
->nonlin_use
;
1636 if (integer_zerop (iv
->step
))
1638 record_invariant (data
, op
, true);
1642 stmt
= SSA_NAME_DEF_STMT (op
);
1643 gcc_assert (gimple_code (stmt
) == GIMPLE_PHI
|| is_gimple_assign (stmt
));
1645 use
= record_group_use (data
, NULL
, iv
, stmt
, USE_NONLINEAR_EXPR
);
1646 iv
->nonlin_use
= use
;
1650 /* Indicate how compare type iv_use can be handled. */
1651 enum comp_iv_rewrite
1654 /* We may rewrite compare type iv_use by expressing value of the iv_use. */
1656 /* We may rewrite compare type iv_uses on both sides of comparison by
1657 expressing value of each iv_use. */
1659 /* We may rewrite compare type iv_use by expressing value of the iv_use
1660 or by eliminating it with other iv_cand. */
1664 /* Given a condition in statement STMT, checks whether it is a compare
1665 of an induction variable and an invariant. If this is the case,
1666 CONTROL_VAR is set to location of the iv, BOUND to the location of
1667 the invariant, IV_VAR and IV_BOUND are set to the corresponding
1668 induction variable descriptions, and true is returned. If this is not
1669 the case, CONTROL_VAR and BOUND are set to the arguments of the
1670 condition and false is returned. */
1672 static enum comp_iv_rewrite
1673 extract_cond_operands (struct ivopts_data
*data
, gimple
*stmt
,
1674 tree
**control_var
, tree
**bound
,
1675 struct iv
**iv_var
, struct iv
**iv_bound
)
1677 /* The objects returned when COND has constant operands. */
1678 static struct iv const_iv
;
1680 tree
*op0
= &zero
, *op1
= &zero
;
1681 struct iv
*iv0
= &const_iv
, *iv1
= &const_iv
;
1682 enum comp_iv_rewrite rewrite_type
= COMP_IV_NA
;
1684 if (gimple_code (stmt
) == GIMPLE_COND
)
1686 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
1687 op0
= gimple_cond_lhs_ptr (cond_stmt
);
1688 op1
= gimple_cond_rhs_ptr (cond_stmt
);
1692 op0
= gimple_assign_rhs1_ptr (stmt
);
1693 op1
= gimple_assign_rhs2_ptr (stmt
);
1696 zero
= integer_zero_node
;
1697 const_iv
.step
= integer_zero_node
;
1699 if (TREE_CODE (*op0
) == SSA_NAME
)
1700 iv0
= get_iv (data
, *op0
);
1701 if (TREE_CODE (*op1
) == SSA_NAME
)
1702 iv1
= get_iv (data
, *op1
);
1704 /* If both sides of comparison are IVs. We can express ivs on both end. */
1705 if (iv0
&& iv1
&& !integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1707 rewrite_type
= COMP_IV_EXPR_2
;
1711 /* If none side of comparison is IV. */
1712 if ((!iv0
|| integer_zerop (iv0
->step
))
1713 && (!iv1
|| integer_zerop (iv1
->step
)))
1716 /* Control variable may be on the other side. */
1717 if (!iv0
|| integer_zerop (iv0
->step
))
1719 std::swap (op0
, op1
);
1720 std::swap (iv0
, iv1
);
1722 /* If one side is IV and the other side isn't loop invariant. */
1724 rewrite_type
= COMP_IV_EXPR
;
1725 /* If one side is IV and the other side is loop invariant. */
1726 else if (!integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1727 rewrite_type
= COMP_IV_ELIM
;
1739 return rewrite_type
;
1742 /* Checks whether the condition in STMT is interesting and if so,
1746 find_interesting_uses_cond (struct ivopts_data
*data
, gimple
*stmt
)
1748 tree
*var_p
, *bound_p
;
1749 struct iv
*var_iv
, *bound_iv
;
1750 enum comp_iv_rewrite ret
;
1752 ret
= extract_cond_operands (data
, stmt
,
1753 &var_p
, &bound_p
, &var_iv
, &bound_iv
);
1754 if (ret
== COMP_IV_NA
)
1756 find_interesting_uses_op (data
, *var_p
);
1757 find_interesting_uses_op (data
, *bound_p
);
1761 record_group_use (data
, var_p
, var_iv
, stmt
, USE_COMPARE
);
1762 /* Record compare type iv_use for iv on the other side of comparison. */
1763 if (ret
== COMP_IV_EXPR_2
)
1764 record_group_use (data
, bound_p
, bound_iv
, stmt
, USE_COMPARE
);
1767 /* Returns the outermost loop EXPR is obviously invariant in
1768 relative to the loop LOOP, i.e. if all its operands are defined
1769 outside of the returned loop. Returns NULL if EXPR is not
1770 even obviously invariant in LOOP. */
1773 outermost_invariant_loop_for_expr (struct loop
*loop
, tree expr
)
1778 if (is_gimple_min_invariant (expr
))
1779 return current_loops
->tree_root
;
1781 if (TREE_CODE (expr
) == SSA_NAME
)
1783 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
1786 if (flow_bb_inside_loop_p (loop
, def_bb
))
1788 return superloop_at_depth (loop
,
1789 loop_depth (def_bb
->loop_father
) + 1);
1792 return current_loops
->tree_root
;
1798 unsigned maxdepth
= 0;
1799 len
= TREE_OPERAND_LENGTH (expr
);
1800 for (i
= 0; i
< len
; i
++)
1802 struct loop
*ivloop
;
1803 if (!TREE_OPERAND (expr
, i
))
1806 ivloop
= outermost_invariant_loop_for_expr (loop
, TREE_OPERAND (expr
, i
));
1809 maxdepth
= MAX (maxdepth
, loop_depth (ivloop
));
1812 return superloop_at_depth (loop
, maxdepth
);
1815 /* Returns true if expression EXPR is obviously invariant in LOOP,
1816 i.e. if all its operands are defined outside of the LOOP. LOOP
1817 should not be the function body. */
1820 expr_invariant_in_loop_p (struct loop
*loop
, tree expr
)
1825 gcc_assert (loop_depth (loop
) > 0);
1827 if (is_gimple_min_invariant (expr
))
1830 if (TREE_CODE (expr
) == SSA_NAME
)
1832 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
1834 && flow_bb_inside_loop_p (loop
, def_bb
))
1843 len
= TREE_OPERAND_LENGTH (expr
);
1844 for (i
= 0; i
< len
; i
++)
1845 if (TREE_OPERAND (expr
, i
)
1846 && !expr_invariant_in_loop_p (loop
, TREE_OPERAND (expr
, i
)))
1852 /* Given expression EXPR which computes inductive values with respect
1853 to loop recorded in DATA, this function returns biv from which EXPR
1854 is derived by tracing definition chains of ssa variables in EXPR. */
1857 find_deriving_biv_for_expr (struct ivopts_data
*data
, tree expr
)
1862 enum tree_code code
;
1865 if (expr
== NULL_TREE
)
1868 if (is_gimple_min_invariant (expr
))
1871 code
= TREE_CODE (expr
);
1872 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1874 n
= TREE_OPERAND_LENGTH (expr
);
1875 for (i
= 0; i
< n
; i
++)
1877 iv
= find_deriving_biv_for_expr (data
, TREE_OPERAND (expr
, i
));
1883 /* Stop if it's not ssa name. */
1884 if (code
!= SSA_NAME
)
1887 iv
= get_iv (data
, expr
);
1888 if (!iv
|| integer_zerop (iv
->step
))
1893 stmt
= SSA_NAME_DEF_STMT (expr
);
1894 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
1897 use_operand_p use_p
;
1898 basic_block phi_bb
= gimple_bb (phi
);
1900 /* Skip loop header PHI that doesn't define biv. */
1901 if (phi_bb
->loop_father
== data
->current_loop
)
1904 if (virtual_operand_p (gimple_phi_result (phi
)))
1907 FOR_EACH_PHI_ARG (use_p
, phi
, iter
, SSA_OP_USE
)
1909 tree use
= USE_FROM_PTR (use_p
);
1910 iv
= find_deriving_biv_for_expr (data
, use
);
1916 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1919 e1
= gimple_assign_rhs1 (stmt
);
1920 code
= gimple_assign_rhs_code (stmt
);
1921 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1922 return find_deriving_biv_for_expr (data
, e1
);
1929 case POINTER_PLUS_EXPR
:
1930 /* Increments, decrements and multiplications by a constant
1932 e2
= gimple_assign_rhs2 (stmt
);
1933 iv
= find_deriving_biv_for_expr (data
, e2
);
1939 /* Casts are simple. */
1940 return find_deriving_biv_for_expr (data
, e1
);
1949 /* Record BIV, its predecessor and successor that they are used in
1950 address type uses. */
1953 record_biv_for_address_use (struct ivopts_data
*data
, struct iv
*biv
)
1956 tree type
, base_1
, base_2
;
1959 if (!biv
|| !biv
->biv_p
|| integer_zerop (biv
->step
)
1960 || biv
->have_address_use
|| !biv
->no_overflow
)
1963 type
= TREE_TYPE (biv
->base
);
1964 if (!INTEGRAL_TYPE_P (type
))
1967 biv
->have_address_use
= true;
1968 data
->bivs_not_used_in_addr
--;
1969 base_1
= fold_build2 (PLUS_EXPR
, type
, biv
->base
, biv
->step
);
1970 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
1972 struct iv
*iv
= ver_info (data
, i
)->iv
;
1974 if (!iv
|| !iv
->biv_p
|| integer_zerop (iv
->step
)
1975 || iv
->have_address_use
|| !iv
->no_overflow
)
1978 if (type
!= TREE_TYPE (iv
->base
)
1979 || !INTEGRAL_TYPE_P (TREE_TYPE (iv
->base
)))
1982 if (!operand_equal_p (biv
->step
, iv
->step
, 0))
1985 base_2
= fold_build2 (PLUS_EXPR
, type
, iv
->base
, iv
->step
);
1986 if (operand_equal_p (base_1
, iv
->base
, 0)
1987 || operand_equal_p (base_2
, biv
->base
, 0))
1989 iv
->have_address_use
= true;
1990 data
->bivs_not_used_in_addr
--;
1995 /* Cumulates the steps of indices into DATA and replaces their values with the
1996 initial ones. Returns false when the value of the index cannot be determined.
1997 Callback for for_each_index. */
1999 struct ifs_ivopts_data
2001 struct ivopts_data
*ivopts_data
;
2007 idx_find_step (tree base
, tree
*idx
, void *data
)
2009 struct ifs_ivopts_data
*dta
= (struct ifs_ivopts_data
*) data
;
2011 bool use_overflow_semantics
= false;
2012 tree step
, iv_base
, iv_step
, lbound
, off
;
2013 struct loop
*loop
= dta
->ivopts_data
->current_loop
;
2015 /* If base is a component ref, require that the offset of the reference
2017 if (TREE_CODE (base
) == COMPONENT_REF
)
2019 off
= component_ref_field_offset (base
);
2020 return expr_invariant_in_loop_p (loop
, off
);
2023 /* If base is array, first check whether we will be able to move the
2024 reference out of the loop (in order to take its address in strength
2025 reduction). In order for this to work we need both lower bound
2026 and step to be loop invariants. */
2027 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
2029 /* Moreover, for a range, the size needs to be invariant as well. */
2030 if (TREE_CODE (base
) == ARRAY_RANGE_REF
2031 && !expr_invariant_in_loop_p (loop
, TYPE_SIZE (TREE_TYPE (base
))))
2034 step
= array_ref_element_size (base
);
2035 lbound
= array_ref_low_bound (base
);
2037 if (!expr_invariant_in_loop_p (loop
, step
)
2038 || !expr_invariant_in_loop_p (loop
, lbound
))
2042 if (TREE_CODE (*idx
) != SSA_NAME
)
2045 iv
= get_iv (dta
->ivopts_data
, *idx
);
2049 /* XXX We produce for a base of *D42 with iv->base being &x[0]
2050 *&x[0], which is not folded and does not trigger the
2051 ARRAY_REF path below. */
2054 if (integer_zerop (iv
->step
))
2057 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
2059 step
= array_ref_element_size (base
);
2061 /* We only handle addresses whose step is an integer constant. */
2062 if (TREE_CODE (step
) != INTEGER_CST
)
2066 /* The step for pointer arithmetics already is 1 byte. */
2067 step
= size_one_node
;
2071 if (iv
->no_overflow
&& nowrap_type_p (TREE_TYPE (iv_step
)))
2072 use_overflow_semantics
= true;
2074 if (!convert_affine_scev (dta
->ivopts_data
->current_loop
,
2075 sizetype
, &iv_base
, &iv_step
, dta
->stmt
,
2076 use_overflow_semantics
))
2078 /* The index might wrap. */
2082 step
= fold_build2 (MULT_EXPR
, sizetype
, step
, iv_step
);
2083 dta
->step
= fold_build2 (PLUS_EXPR
, sizetype
, dta
->step
, step
);
2085 if (dta
->ivopts_data
->bivs_not_used_in_addr
)
2088 iv
= find_deriving_biv_for_expr (dta
->ivopts_data
, iv
->ssa_name
);
2090 record_biv_for_address_use (dta
->ivopts_data
, iv
);
2095 /* Records use in index IDX. Callback for for_each_index. Ivopts data
2096 object is passed to it in DATA. */
2099 idx_record_use (tree base
, tree
*idx
,
2102 struct ivopts_data
*data
= (struct ivopts_data
*) vdata
;
2103 find_interesting_uses_op (data
, *idx
);
2104 if (TREE_CODE (base
) == ARRAY_REF
|| TREE_CODE (base
) == ARRAY_RANGE_REF
)
2106 find_interesting_uses_op (data
, array_ref_element_size (base
));
2107 find_interesting_uses_op (data
, array_ref_low_bound (base
));
2112 /* If we can prove that TOP = cst * BOT for some constant cst,
2113 store cst to MUL and return true. Otherwise return false.
2114 The returned value is always sign-extended, regardless of the
2115 signedness of TOP and BOT. */
2118 constant_multiple_of (tree top
, tree bot
, widest_int
*mul
)
2121 enum tree_code code
;
2122 unsigned precision
= TYPE_PRECISION (TREE_TYPE (top
));
2123 widest_int res
, p0
, p1
;
2128 if (operand_equal_p (top
, bot
, 0))
2134 code
= TREE_CODE (top
);
2138 mby
= TREE_OPERAND (top
, 1);
2139 if (TREE_CODE (mby
) != INTEGER_CST
)
2142 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &res
))
2145 *mul
= wi::sext (res
* wi::to_widest (mby
), precision
);
2150 if (!constant_multiple_of (TREE_OPERAND (top
, 0), bot
, &p0
)
2151 || !constant_multiple_of (TREE_OPERAND (top
, 1), bot
, &p1
))
2154 if (code
== MINUS_EXPR
)
2156 *mul
= wi::sext (p0
+ p1
, precision
);
2160 if (TREE_CODE (bot
) != INTEGER_CST
)
2163 p0
= widest_int::from (top
, SIGNED
);
2164 p1
= widest_int::from (bot
, SIGNED
);
2167 *mul
= wi::sext (wi::divmod_trunc (p0
, p1
, SIGNED
, &res
), precision
);
2175 /* Return true if memory reference REF with step STEP may be unaligned. */
2178 may_be_unaligned_p (tree ref
, tree step
)
2180 /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
2181 thus they are not misaligned. */
2182 if (TREE_CODE (ref
) == TARGET_MEM_REF
)
2185 unsigned int align
= TYPE_ALIGN (TREE_TYPE (ref
));
2186 if (GET_MODE_ALIGNMENT (TYPE_MODE (TREE_TYPE (ref
))) > align
)
2187 align
= GET_MODE_ALIGNMENT (TYPE_MODE (TREE_TYPE (ref
)));
2189 unsigned HOST_WIDE_INT bitpos
;
2190 unsigned int ref_align
;
2191 get_object_alignment_1 (ref
, &ref_align
, &bitpos
);
2192 if (ref_align
< align
2193 || (bitpos
% align
) != 0
2194 || (bitpos
% BITS_PER_UNIT
) != 0)
2197 unsigned int trailing_zeros
= tree_ctz (step
);
2198 if (trailing_zeros
< HOST_BITS_PER_INT
2199 && (1U << trailing_zeros
) * BITS_PER_UNIT
< align
)
2205 /* Return true if EXPR may be non-addressable. */
2208 may_be_nonaddressable_p (tree expr
)
2210 switch (TREE_CODE (expr
))
2212 case TARGET_MEM_REF
:
2213 /* TARGET_MEM_REFs are translated directly to valid MEMs on the
2214 target, thus they are always addressable. */
2218 /* Likewise for MEM_REFs, modulo the storage order. */
2219 return REF_REVERSE_STORAGE_ORDER (expr
);
2222 if (REF_REVERSE_STORAGE_ORDER (expr
))
2224 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
2227 if (TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (TREE_OPERAND (expr
, 0))))
2229 return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr
, 1))
2230 || may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
2233 case ARRAY_RANGE_REF
:
2234 if (TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (TREE_OPERAND (expr
, 0))))
2236 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
2238 case VIEW_CONVERT_EXPR
:
2239 /* This kind of view-conversions may wrap non-addressable objects
2240 and make them look addressable. After some processing the
2241 non-addressability may be uncovered again, causing ADDR_EXPRs
2242 of inappropriate objects to be built. */
2243 if (is_gimple_reg (TREE_OPERAND (expr
, 0))
2244 || !is_gimple_addressable (TREE_OPERAND (expr
, 0)))
2246 return may_be_nonaddressable_p (TREE_OPERAND (expr
, 0));
2258 /* Finds addresses in *OP_P inside STMT. */
2261 find_interesting_uses_address (struct ivopts_data
*data
, gimple
*stmt
,
2264 tree base
= *op_p
, step
= size_zero_node
;
2266 struct ifs_ivopts_data ifs_ivopts_data
;
2268 /* Do not play with volatile memory references. A bit too conservative,
2269 perhaps, but safe. */
2270 if (gimple_has_volatile_ops (stmt
))
2273 /* Ignore bitfields for now. Not really something terribly complicated
2275 if (TREE_CODE (base
) == BIT_FIELD_REF
)
2278 base
= unshare_expr (base
);
2280 if (TREE_CODE (base
) == TARGET_MEM_REF
)
2282 tree type
= build_pointer_type (TREE_TYPE (base
));
2286 && TREE_CODE (TMR_BASE (base
)) == SSA_NAME
)
2288 civ
= get_iv (data
, TMR_BASE (base
));
2292 TMR_BASE (base
) = civ
->base
;
2295 if (TMR_INDEX2 (base
)
2296 && TREE_CODE (TMR_INDEX2 (base
)) == SSA_NAME
)
2298 civ
= get_iv (data
, TMR_INDEX2 (base
));
2302 TMR_INDEX2 (base
) = civ
->base
;
2305 if (TMR_INDEX (base
)
2306 && TREE_CODE (TMR_INDEX (base
)) == SSA_NAME
)
2308 civ
= get_iv (data
, TMR_INDEX (base
));
2312 TMR_INDEX (base
) = civ
->base
;
2317 if (TMR_STEP (base
))
2318 astep
= fold_build2 (MULT_EXPR
, type
, TMR_STEP (base
), astep
);
2320 step
= fold_build2 (PLUS_EXPR
, type
, step
, astep
);
2324 if (integer_zerop (step
))
2326 base
= tree_mem_ref_addr (type
, base
);
2330 ifs_ivopts_data
.ivopts_data
= data
;
2331 ifs_ivopts_data
.stmt
= stmt
;
2332 ifs_ivopts_data
.step
= size_zero_node
;
2333 if (!for_each_index (&base
, idx_find_step
, &ifs_ivopts_data
)
2334 || integer_zerop (ifs_ivopts_data
.step
))
2336 step
= ifs_ivopts_data
.step
;
2338 /* Check that the base expression is addressable. This needs
2339 to be done after substituting bases of IVs into it. */
2340 if (may_be_nonaddressable_p (base
))
2343 /* Moreover, on strict alignment platforms, check that it is
2344 sufficiently aligned. */
2345 if (STRICT_ALIGNMENT
&& may_be_unaligned_p (base
, step
))
2348 base
= build_fold_addr_expr (base
);
2350 /* Substituting bases of IVs into the base expression might
2351 have caused folding opportunities. */
2352 if (TREE_CODE (base
) == ADDR_EXPR
)
2354 tree
*ref
= &TREE_OPERAND (base
, 0);
2355 while (handled_component_p (*ref
))
2356 ref
= &TREE_OPERAND (*ref
, 0);
2357 if (TREE_CODE (*ref
) == MEM_REF
)
2359 tree tem
= fold_binary (MEM_REF
, TREE_TYPE (*ref
),
2360 TREE_OPERAND (*ref
, 0),
2361 TREE_OPERAND (*ref
, 1));
2368 civ
= alloc_iv (data
, base
, step
);
2369 /* Fail if base object of this memory reference is unknown. */
2370 if (civ
->base_object
== NULL_TREE
)
2373 record_group_use (data
, op_p
, civ
, stmt
, USE_ADDRESS
);
2377 for_each_index (op_p
, idx_record_use
, data
);
2380 /* Finds and records invariants used in STMT. */
2383 find_invariants_stmt (struct ivopts_data
*data
, gimple
*stmt
)
2386 use_operand_p use_p
;
2389 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2391 op
= USE_FROM_PTR (use_p
);
2392 record_invariant (data
, op
, false);
2396 /* Finds interesting uses of induction variables in the statement STMT. */
2399 find_interesting_uses_stmt (struct ivopts_data
*data
, gimple
*stmt
)
2402 tree op
, *lhs
, *rhs
;
2404 use_operand_p use_p
;
2405 enum tree_code code
;
2407 find_invariants_stmt (data
, stmt
);
2409 if (gimple_code (stmt
) == GIMPLE_COND
)
2411 find_interesting_uses_cond (data
, stmt
);
2415 if (is_gimple_assign (stmt
))
2417 lhs
= gimple_assign_lhs_ptr (stmt
);
2418 rhs
= gimple_assign_rhs1_ptr (stmt
);
2420 if (TREE_CODE (*lhs
) == SSA_NAME
)
2422 /* If the statement defines an induction variable, the uses are not
2423 interesting by themselves. */
2425 iv
= get_iv (data
, *lhs
);
2427 if (iv
&& !integer_zerop (iv
->step
))
2431 code
= gimple_assign_rhs_code (stmt
);
2432 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
2433 && (REFERENCE_CLASS_P (*rhs
)
2434 || is_gimple_val (*rhs
)))
2436 if (REFERENCE_CLASS_P (*rhs
))
2437 find_interesting_uses_address (data
, stmt
, rhs
);
2439 find_interesting_uses_op (data
, *rhs
);
2441 if (REFERENCE_CLASS_P (*lhs
))
2442 find_interesting_uses_address (data
, stmt
, lhs
);
2445 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
2447 find_interesting_uses_cond (data
, stmt
);
2451 /* TODO -- we should also handle address uses of type
2453 memory = call (whatever);
2460 if (gimple_code (stmt
) == GIMPLE_PHI
2461 && gimple_bb (stmt
) == data
->current_loop
->header
)
2463 iv
= get_iv (data
, PHI_RESULT (stmt
));
2465 if (iv
&& !integer_zerop (iv
->step
))
2469 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2471 op
= USE_FROM_PTR (use_p
);
2473 if (TREE_CODE (op
) != SSA_NAME
)
2476 iv
= get_iv (data
, op
);
2480 find_interesting_uses_op (data
, op
);
2484 /* Finds interesting uses of induction variables outside of loops
2485 on loop exit edge EXIT. */
2488 find_interesting_uses_outside (struct ivopts_data
*data
, edge exit
)
2494 for (psi
= gsi_start_phis (exit
->dest
); !gsi_end_p (psi
); gsi_next (&psi
))
2497 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
2498 if (!virtual_operand_p (def
))
2499 find_interesting_uses_op (data
, def
);
2503 /* Return TRUE if OFFSET is within the range of [base + offset] addressing
2504 mode for memory reference represented by USE. */
2506 static GTY (()) vec
<rtx
, va_gc
> *addr_list
;
2509 addr_offset_valid_p (struct iv_use
*use
, HOST_WIDE_INT offset
)
2512 unsigned list_index
;
2513 addr_space_t as
= TYPE_ADDR_SPACE (TREE_TYPE (use
->iv
->base
));
2514 machine_mode addr_mode
, mem_mode
= TYPE_MODE (TREE_TYPE (*use
->op_p
));
2516 list_index
= (unsigned) as
* MAX_MACHINE_MODE
+ (unsigned) mem_mode
;
2517 if (list_index
>= vec_safe_length (addr_list
))
2518 vec_safe_grow_cleared (addr_list
, list_index
+ MAX_MACHINE_MODE
);
2520 addr
= (*addr_list
)[list_index
];
2523 addr_mode
= targetm
.addr_space
.address_mode (as
);
2524 reg
= gen_raw_REG (addr_mode
, LAST_VIRTUAL_REGISTER
+ 1);
2525 addr
= gen_rtx_fmt_ee (PLUS
, addr_mode
, reg
, NULL_RTX
);
2526 (*addr_list
)[list_index
] = addr
;
2529 addr_mode
= GET_MODE (addr
);
2531 XEXP (addr
, 1) = gen_int_mode (offset
, addr_mode
);
2532 return (memory_address_addr_space_p (mem_mode
, addr
, as
));
2535 /* Comparison function to sort group in ascending order of addr_offset. */
2538 group_compare_offset (const void *a
, const void *b
)
2540 const struct iv_use
*const *u1
= (const struct iv_use
*const *) a
;
2541 const struct iv_use
*const *u2
= (const struct iv_use
*const *) b
;
2543 if ((*u1
)->addr_offset
!= (*u2
)->addr_offset
)
2544 return (*u1
)->addr_offset
< (*u2
)->addr_offset
? -1 : 1;
2549 /* Check if small groups should be split. Return true if no group
2550 contains more than two uses with distinct addr_offsets. Return
2551 false otherwise. We want to split such groups because:
2553 1) Small groups don't have much benefit and may interfer with
2554 general candidate selection.
2555 2) Size for problem with only small groups is usually small and
2556 general algorithm can handle it well.
2558 TODO -- Above claim may not hold when we want to merge memory
2559 accesses with conseuctive addresses. */
2562 split_small_address_groups_p (struct ivopts_data
*data
)
2564 unsigned int i
, j
, distinct
= 1;
2566 struct iv_group
*group
;
2568 for (i
= 0; i
< data
->vgroups
.length (); i
++)
2570 group
= data
->vgroups
[i
];
2571 if (group
->vuses
.length () == 1)
2574 gcc_assert (group
->type
== USE_ADDRESS
);
2575 if (group
->vuses
.length () == 2)
2577 if (group
->vuses
[0]->addr_offset
> group
->vuses
[1]->addr_offset
)
2578 std::swap (group
->vuses
[0], group
->vuses
[1]);
2581 group
->vuses
.qsort (group_compare_offset
);
2587 for (pre
= group
->vuses
[0], j
= 1; j
< group
->vuses
.length (); j
++)
2589 if (group
->vuses
[j
]->addr_offset
!= pre
->addr_offset
)
2591 pre
= group
->vuses
[j
];
2600 return (distinct
<= 2);
2603 /* For each group of address type uses, this function further groups
2604 these uses according to the maximum offset supported by target's
2605 [base + offset] addressing mode. */
2608 split_address_groups (struct ivopts_data
*data
)
2611 /* Always split group. */
2612 bool split_p
= split_small_address_groups_p (data
);
2614 for (i
= 0; i
< data
->vgroups
.length (); i
++)
2616 struct iv_group
*new_group
= NULL
;
2617 struct iv_group
*group
= data
->vgroups
[i
];
2618 struct iv_use
*use
= group
->vuses
[0];
2621 use
->group_id
= group
->id
;
2622 if (group
->vuses
.length () == 1)
2625 gcc_assert (group
->type
== USE_ADDRESS
);
2627 for (j
= 1; j
< group
->vuses
.length ();)
2629 struct iv_use
*next
= group
->vuses
[j
];
2630 HOST_WIDE_INT offset
= next
->addr_offset
- use
->addr_offset
;
2632 /* Split group if aksed to, or the offset against the first
2633 use can't fit in offset part of addressing mode. IV uses
2634 having the same offset are still kept in one group. */
2636 (split_p
|| !addr_offset_valid_p (use
, offset
)))
2639 new_group
= record_group (data
, group
->type
);
2640 group
->vuses
.ordered_remove (j
);
2641 new_group
->vuses
.safe_push (next
);
2646 next
->group_id
= group
->id
;
2652 /* Finds uses of the induction variables that are interesting. */
2655 find_interesting_uses (struct ivopts_data
*data
)
2658 gimple_stmt_iterator bsi
;
2659 basic_block
*body
= get_loop_body (data
->current_loop
);
2663 for (i
= 0; i
< data
->current_loop
->num_nodes
; i
++)
2668 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2669 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2670 && !flow_bb_inside_loop_p (data
->current_loop
, e
->dest
))
2671 find_interesting_uses_outside (data
, e
);
2673 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2674 find_interesting_uses_stmt (data
, gsi_stmt (bsi
));
2675 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2676 if (!is_gimple_debug (gsi_stmt (bsi
)))
2677 find_interesting_uses_stmt (data
, gsi_stmt (bsi
));
2680 split_address_groups (data
);
2682 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2686 fprintf (dump_file
, "\n<Invariant Vars>:\n");
2687 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
2689 struct version_info
*info
= ver_info (data
, i
);
2692 fprintf (dump_file
, "Inv %d:\t", info
->inv_id
);
2693 print_generic_expr (dump_file
, info
->name
, TDF_SLIM
);
2694 fprintf (dump_file
, "%s\n",
2695 info
->has_nonlin_use
? "" : "\t(eliminable)");
2699 fprintf (dump_file
, "\n<IV Groups>:\n");
2700 dump_groups (dump_file
, data
);
2701 fprintf (dump_file
, "\n");
2707 /* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
2708 is true, assume we are inside an address. If TOP_COMPREF is true, assume
2709 we are at the top-level of the processed address. */
2712 strip_offset_1 (tree expr
, bool inside_addr
, bool top_compref
,
2713 HOST_WIDE_INT
*offset
)
2715 tree op0
= NULL_TREE
, op1
= NULL_TREE
, tmp
, step
;
2716 enum tree_code code
;
2717 tree type
, orig_type
= TREE_TYPE (expr
);
2718 HOST_WIDE_INT off0
, off1
, st
;
2719 tree orig_expr
= expr
;
2723 type
= TREE_TYPE (expr
);
2724 code
= TREE_CODE (expr
);
2730 if (!cst_and_fits_in_hwi (expr
)
2731 || integer_zerop (expr
))
2734 *offset
= int_cst_value (expr
);
2735 return build_int_cst (orig_type
, 0);
2737 case POINTER_PLUS_EXPR
:
2740 op0
= TREE_OPERAND (expr
, 0);
2741 op1
= TREE_OPERAND (expr
, 1);
2743 op0
= strip_offset_1 (op0
, false, false, &off0
);
2744 op1
= strip_offset_1 (op1
, false, false, &off1
);
2746 *offset
= (code
== MINUS_EXPR
? off0
- off1
: off0
+ off1
);
2747 if (op0
== TREE_OPERAND (expr
, 0)
2748 && op1
== TREE_OPERAND (expr
, 1))
2751 if (integer_zerop (op1
))
2753 else if (integer_zerop (op0
))
2755 if (code
== MINUS_EXPR
)
2756 expr
= fold_build1 (NEGATE_EXPR
, type
, op1
);
2761 expr
= fold_build2 (code
, type
, op0
, op1
);
2763 return fold_convert (orig_type
, expr
);
2766 op1
= TREE_OPERAND (expr
, 1);
2767 if (!cst_and_fits_in_hwi (op1
))
2770 op0
= TREE_OPERAND (expr
, 0);
2771 op0
= strip_offset_1 (op0
, false, false, &off0
);
2772 if (op0
== TREE_OPERAND (expr
, 0))
2775 *offset
= off0
* int_cst_value (op1
);
2776 if (integer_zerop (op0
))
2779 expr
= fold_build2 (MULT_EXPR
, type
, op0
, op1
);
2781 return fold_convert (orig_type
, expr
);
2784 case ARRAY_RANGE_REF
:
2788 step
= array_ref_element_size (expr
);
2789 if (!cst_and_fits_in_hwi (step
))
2792 st
= int_cst_value (step
);
2793 op1
= TREE_OPERAND (expr
, 1);
2794 op1
= strip_offset_1 (op1
, false, false, &off1
);
2795 *offset
= off1
* st
;
2798 && integer_zerop (op1
))
2800 /* Strip the component reference completely. */
2801 op0
= TREE_OPERAND (expr
, 0);
2802 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
2815 tmp
= component_ref_field_offset (expr
);
2816 field
= TREE_OPERAND (expr
, 1);
2818 && cst_and_fits_in_hwi (tmp
)
2819 && cst_and_fits_in_hwi (DECL_FIELD_BIT_OFFSET (field
)))
2821 HOST_WIDE_INT boffset
, abs_off
;
2823 /* Strip the component reference completely. */
2824 op0
= TREE_OPERAND (expr
, 0);
2825 op0
= strip_offset_1 (op0
, inside_addr
, top_compref
, &off0
);
2826 boffset
= int_cst_value (DECL_FIELD_BIT_OFFSET (field
));
2827 abs_off
= abs_hwi (boffset
) / BITS_PER_UNIT
;
2831 *offset
= off0
+ int_cst_value (tmp
) + abs_off
;
2838 op0
= TREE_OPERAND (expr
, 0);
2839 op0
= strip_offset_1 (op0
, true, true, &off0
);
2842 if (op0
== TREE_OPERAND (expr
, 0))
2845 expr
= build_fold_addr_expr (op0
);
2846 return fold_convert (orig_type
, expr
);
2849 /* ??? Offset operand? */
2850 inside_addr
= false;
2857 /* Default handling of expressions for that we want to recurse into
2858 the first operand. */
2859 op0
= TREE_OPERAND (expr
, 0);
2860 op0
= strip_offset_1 (op0
, inside_addr
, false, &off0
);
2863 if (op0
== TREE_OPERAND (expr
, 0)
2864 && (!op1
|| op1
== TREE_OPERAND (expr
, 1)))
2867 expr
= copy_node (expr
);
2868 TREE_OPERAND (expr
, 0) = op0
;
2870 TREE_OPERAND (expr
, 1) = op1
;
2872 /* Inside address, we might strip the top level component references,
2873 thus changing type of the expression. Handling of ADDR_EXPR
2875 expr
= fold_convert (orig_type
, expr
);
2880 /* Strips constant offsets from EXPR and stores them to OFFSET. */
2883 strip_offset (tree expr
, unsigned HOST_WIDE_INT
*offset
)
2886 tree core
= strip_offset_1 (expr
, false, false, &off
);
2891 /* Returns variant of TYPE that can be used as base for different uses.
2892 We return unsigned type with the same precision, which avoids problems
2896 generic_type_for (tree type
)
2898 if (POINTER_TYPE_P (type
))
2899 return unsigned_type_for (type
);
2901 if (TYPE_UNSIGNED (type
))
2904 return unsigned_type_for (type
);
2907 /* Private data for walk_tree. */
2909 struct walk_tree_data
2912 struct ivopts_data
*idata
;
2915 /* Callback function for walk_tree, it records invariants and symbol
2916 reference in *EXPR_P. DATA is the structure storing result info. */
2919 find_inv_vars_cb (tree
*expr_p
, int *ws ATTRIBUTE_UNUSED
, void *data
)
2921 struct walk_tree_data
*wdata
= (struct walk_tree_data
*) data
;
2922 struct version_info
*info
;
2924 if (TREE_CODE (*expr_p
) != SSA_NAME
)
2927 info
= name_info (wdata
->idata
, *expr_p
);
2928 if (!info
->inv_id
|| info
->has_nonlin_use
)
2931 if (!*wdata
->inv_vars
)
2932 *wdata
->inv_vars
= BITMAP_ALLOC (NULL
);
2933 bitmap_set_bit (*wdata
->inv_vars
, info
->inv_id
);
2938 /* Records invariants in *EXPR_P. INV_VARS is the bitmap to that we should
2942 find_inv_vars (struct ivopts_data
*data
, tree
*expr_p
, bitmap
*inv_vars
)
2944 struct walk_tree_data wdata
;
2950 wdata
.inv_vars
= inv_vars
;
2951 walk_tree (expr_p
, find_inv_vars_cb
, &wdata
, NULL
);
2954 /* Get entry from invariant expr hash table for INV_EXPR. New entry
2955 will be recorded if it doesn't exist yet. Given below two exprs:
2956 inv_expr + cst1, inv_expr + cst2
2957 It's hard to make decision whether constant part should be stripped
2958 or not. We choose to not strip based on below facts:
2959 1) We need to count ADD cost for constant part if it's stripped,
2960 which is't always trivial where this functions is called.
2961 2) Stripping constant away may be conflict with following loop
2962 invariant hoisting pass.
2963 3) Not stripping constant away results in more invariant exprs,
2964 which usually leads to decision preferring lower reg pressure. */
2966 static iv_inv_expr_ent
*
2967 get_loop_invariant_expr (struct ivopts_data
*data
, tree inv_expr
)
2969 STRIP_NOPS (inv_expr
);
2971 if (TREE_CODE (inv_expr
) == INTEGER_CST
|| TREE_CODE (inv_expr
) == SSA_NAME
)
2974 /* Don't strip constant part away as we used to. */
2976 /* Stores EXPR in DATA->inv_expr_tab, return pointer to iv_inv_expr_ent. */
2977 struct iv_inv_expr_ent ent
;
2978 ent
.expr
= inv_expr
;
2979 ent
.hash
= iterative_hash_expr (inv_expr
, 0);
2980 struct iv_inv_expr_ent
**slot
= data
->inv_expr_tab
->find_slot (&ent
, INSERT
);
2984 *slot
= XNEW (struct iv_inv_expr_ent
);
2985 (*slot
)->expr
= inv_expr
;
2986 (*slot
)->hash
= ent
.hash
;
2987 (*slot
)->id
= ++data
->max_inv_expr_id
;
2993 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2994 position to POS. If USE is not NULL, the candidate is set as related to
2995 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
2996 replacement of the final value of the iv by a direct computation. */
2998 static struct iv_cand
*
2999 add_candidate_1 (struct ivopts_data
*data
,
3000 tree base
, tree step
, bool important
, enum iv_position pos
,
3001 struct iv_use
*use
, gimple
*incremented_at
,
3002 struct iv
*orig_iv
= NULL
)
3005 struct iv_cand
*cand
= NULL
;
3006 tree type
, orig_type
;
3008 gcc_assert (base
&& step
);
3010 /* -fkeep-gc-roots-live means that we have to keep a real pointer
3011 live, but the ivopts code may replace a real pointer with one
3012 pointing before or after the memory block that is then adjusted
3013 into the memory block during the loop. FIXME: It would likely be
3014 better to actually force the pointer live and still use ivopts;
3015 for example, it would be enough to write the pointer into memory
3016 and keep it there until after the loop. */
3017 if (flag_keep_gc_roots_live
&& POINTER_TYPE_P (TREE_TYPE (base
)))
3020 /* For non-original variables, make sure their values are computed in a type
3021 that does not invoke undefined behavior on overflows (since in general,
3022 we cannot prove that these induction variables are non-wrapping). */
3023 if (pos
!= IP_ORIGINAL
)
3025 orig_type
= TREE_TYPE (base
);
3026 type
= generic_type_for (orig_type
);
3027 if (type
!= orig_type
)
3029 base
= fold_convert (type
, base
);
3030 step
= fold_convert (type
, step
);
3034 for (i
= 0; i
< data
->vcands
.length (); i
++)
3036 cand
= data
->vcands
[i
];
3038 if (cand
->pos
!= pos
)
3041 if (cand
->incremented_at
!= incremented_at
3042 || ((pos
== IP_AFTER_USE
|| pos
== IP_BEFORE_USE
)
3043 && cand
->ainc_use
!= use
))
3046 if (operand_equal_p (base
, cand
->iv
->base
, 0)
3047 && operand_equal_p (step
, cand
->iv
->step
, 0)
3048 && (TYPE_PRECISION (TREE_TYPE (base
))
3049 == TYPE_PRECISION (TREE_TYPE (cand
->iv
->base
))))
3053 if (i
== data
->vcands
.length ())
3055 cand
= XCNEW (struct iv_cand
);
3057 cand
->iv
= alloc_iv (data
, base
, step
);
3059 if (pos
!= IP_ORIGINAL
)
3061 cand
->var_before
= create_tmp_var_raw (TREE_TYPE (base
), "ivtmp");
3062 cand
->var_after
= cand
->var_before
;
3064 cand
->important
= important
;
3065 cand
->incremented_at
= incremented_at
;
3066 data
->vcands
.safe_push (cand
);
3068 if (TREE_CODE (step
) != INTEGER_CST
)
3070 find_inv_vars (data
, &step
, &cand
->inv_vars
);
3072 iv_inv_expr_ent
*inv_expr
= get_loop_invariant_expr (data
, step
);
3073 /* Share bitmap between inv_vars and inv_exprs for cand. */
3074 if (inv_expr
!= NULL
)
3076 cand
->inv_exprs
= cand
->inv_vars
;
3077 cand
->inv_vars
= NULL
;
3078 if (cand
->inv_exprs
)
3079 bitmap_clear (cand
->inv_exprs
);
3081 cand
->inv_exprs
= BITMAP_ALLOC (NULL
);
3083 bitmap_set_bit (cand
->inv_exprs
, inv_expr
->id
);
3087 if (pos
== IP_AFTER_USE
|| pos
== IP_BEFORE_USE
)
3088 cand
->ainc_use
= use
;
3090 cand
->ainc_use
= NULL
;
3092 cand
->orig_iv
= orig_iv
;
3093 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3094 dump_cand (dump_file
, cand
);
3097 cand
->important
|= important
;
3099 /* Relate candidate to the group for which it is added. */
3101 bitmap_set_bit (data
->vgroups
[use
->group_id
]->related_cands
, i
);
3106 /* Returns true if incrementing the induction variable at the end of the LOOP
3109 The purpose is to avoid splitting latch edge with a biv increment, thus
3110 creating a jump, possibly confusing other optimization passes and leaving
3111 less freedom to scheduler. So we allow IP_END only if IP_NORMAL is not
3112 available (so we do not have a better alternative), or if the latch edge
3113 is already nonempty. */
3116 allow_ip_end_pos_p (struct loop
*loop
)
3118 if (!ip_normal_pos (loop
))
3121 if (!empty_block_p (ip_end_pos (loop
)))
3127 /* If possible, adds autoincrement candidates BASE + STEP * i based on use USE.
3128 Important field is set to IMPORTANT. */
3131 add_autoinc_candidates (struct ivopts_data
*data
, tree base
, tree step
,
3132 bool important
, struct iv_use
*use
)
3134 basic_block use_bb
= gimple_bb (use
->stmt
);
3135 machine_mode mem_mode
;
3136 unsigned HOST_WIDE_INT cstepi
;
3138 /* If we insert the increment in any position other than the standard
3139 ones, we must ensure that it is incremented once per iteration.
3140 It must not be in an inner nested loop, or one side of an if
3142 if (use_bb
->loop_father
!= data
->current_loop
3143 || !dominated_by_p (CDI_DOMINATORS
, data
->current_loop
->latch
, use_bb
)
3144 || stmt_could_throw_p (use
->stmt
)
3145 || !cst_and_fits_in_hwi (step
))
3148 cstepi
= int_cst_value (step
);
3150 mem_mode
= TYPE_MODE (TREE_TYPE (*use
->op_p
));
3151 if (((USE_LOAD_PRE_INCREMENT (mem_mode
)
3152 || USE_STORE_PRE_INCREMENT (mem_mode
))
3153 && GET_MODE_SIZE (mem_mode
) == cstepi
)
3154 || ((USE_LOAD_PRE_DECREMENT (mem_mode
)
3155 || USE_STORE_PRE_DECREMENT (mem_mode
))
3156 && GET_MODE_SIZE (mem_mode
) == -cstepi
))
3158 enum tree_code code
= MINUS_EXPR
;
3160 tree new_step
= step
;
3162 if (POINTER_TYPE_P (TREE_TYPE (base
)))
3164 new_step
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (step
), step
);
3165 code
= POINTER_PLUS_EXPR
;
3168 new_step
= fold_convert (TREE_TYPE (base
), new_step
);
3169 new_base
= fold_build2 (code
, TREE_TYPE (base
), base
, new_step
);
3170 add_candidate_1 (data
, new_base
, step
, important
, IP_BEFORE_USE
, use
,
3173 if (((USE_LOAD_POST_INCREMENT (mem_mode
)
3174 || USE_STORE_POST_INCREMENT (mem_mode
))
3175 && GET_MODE_SIZE (mem_mode
) == cstepi
)
3176 || ((USE_LOAD_POST_DECREMENT (mem_mode
)
3177 || USE_STORE_POST_DECREMENT (mem_mode
))
3178 && GET_MODE_SIZE (mem_mode
) == -cstepi
))
3180 add_candidate_1 (data
, base
, step
, important
, IP_AFTER_USE
, use
,
3185 /* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
3186 position to POS. If USE is not NULL, the candidate is set as related to
3187 it. The candidate computation is scheduled before exit condition and at
3191 add_candidate (struct ivopts_data
*data
,
3192 tree base
, tree step
, bool important
, struct iv_use
*use
,
3193 struct iv
*orig_iv
= NULL
)
3195 if (ip_normal_pos (data
->current_loop
))
3196 add_candidate_1 (data
, base
, step
, important
,
3197 IP_NORMAL
, use
, NULL
, orig_iv
);
3198 if (ip_end_pos (data
->current_loop
)
3199 && allow_ip_end_pos_p (data
->current_loop
))
3200 add_candidate_1 (data
, base
, step
, important
, IP_END
, use
, NULL
, orig_iv
);
3203 /* Adds standard iv candidates. */
3206 add_standard_iv_candidates (struct ivopts_data
*data
)
3208 add_candidate (data
, integer_zero_node
, integer_one_node
, true, NULL
);
3210 /* The same for a double-integer type if it is still fast enough. */
3212 (long_integer_type_node
) > TYPE_PRECISION (integer_type_node
)
3213 && TYPE_PRECISION (long_integer_type_node
) <= BITS_PER_WORD
)
3214 add_candidate (data
, build_int_cst (long_integer_type_node
, 0),
3215 build_int_cst (long_integer_type_node
, 1), true, NULL
);
3217 /* The same for a double-integer type if it is still fast enough. */
3219 (long_long_integer_type_node
) > TYPE_PRECISION (long_integer_type_node
)
3220 && TYPE_PRECISION (long_long_integer_type_node
) <= BITS_PER_WORD
)
3221 add_candidate (data
, build_int_cst (long_long_integer_type_node
, 0),
3222 build_int_cst (long_long_integer_type_node
, 1), true, NULL
);
3226 /* Adds candidates bases on the old induction variable IV. */
3229 add_iv_candidate_for_biv (struct ivopts_data
*data
, struct iv
*iv
)
3233 struct iv_cand
*cand
;
3235 /* Check if this biv is used in address type use. */
3236 if (iv
->no_overflow
&& iv
->have_address_use
3237 && INTEGRAL_TYPE_P (TREE_TYPE (iv
->base
))
3238 && TYPE_PRECISION (TREE_TYPE (iv
->base
)) < TYPE_PRECISION (sizetype
))
3240 tree base
= fold_convert (sizetype
, iv
->base
);
3241 tree step
= fold_convert (sizetype
, iv
->step
);
3243 /* Add iv cand of same precision as index part in TARGET_MEM_REF. */
3244 add_candidate (data
, base
, step
, true, NULL
, iv
);
3245 /* Add iv cand of the original type only if it has nonlinear use. */
3247 add_candidate (data
, iv
->base
, iv
->step
, true, NULL
);
3250 add_candidate (data
, iv
->base
, iv
->step
, true, NULL
);
3252 /* The same, but with initial value zero. */
3253 if (POINTER_TYPE_P (TREE_TYPE (iv
->base
)))
3254 add_candidate (data
, size_int (0), iv
->step
, true, NULL
);
3256 add_candidate (data
, build_int_cst (TREE_TYPE (iv
->base
), 0),
3257 iv
->step
, true, NULL
);
3259 phi
= SSA_NAME_DEF_STMT (iv
->ssa_name
);
3260 if (gimple_code (phi
) == GIMPLE_PHI
)
3262 /* Additionally record the possibility of leaving the original iv
3264 def
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (data
->current_loop
));
3265 /* Don't add candidate if it's from another PHI node because
3266 it's an affine iv appearing in the form of PEELED_CHREC. */
3267 phi
= SSA_NAME_DEF_STMT (def
);
3268 if (gimple_code (phi
) != GIMPLE_PHI
)
3270 cand
= add_candidate_1 (data
,
3271 iv
->base
, iv
->step
, true, IP_ORIGINAL
, NULL
,
3272 SSA_NAME_DEF_STMT (def
));
3275 cand
->var_before
= iv
->ssa_name
;
3276 cand
->var_after
= def
;
3280 gcc_assert (gimple_bb (phi
) == data
->current_loop
->header
);
3284 /* Adds candidates based on the old induction variables. */
3287 add_iv_candidate_for_bivs (struct ivopts_data
*data
)
3293 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
3295 iv
= ver_info (data
, i
)->iv
;
3296 if (iv
&& iv
->biv_p
&& !integer_zerop (iv
->step
))
3297 add_iv_candidate_for_biv (data
, iv
);
3301 /* Record common candidate {BASE, STEP} derived from USE in hashtable. */
3304 record_common_cand (struct ivopts_data
*data
, tree base
,
3305 tree step
, struct iv_use
*use
)
3307 struct iv_common_cand ent
;
3308 struct iv_common_cand
**slot
;
3312 ent
.hash
= iterative_hash_expr (base
, 0);
3313 ent
.hash
= iterative_hash_expr (step
, ent
.hash
);
3315 slot
= data
->iv_common_cand_tab
->find_slot (&ent
, INSERT
);
3318 *slot
= new iv_common_cand ();
3319 (*slot
)->base
= base
;
3320 (*slot
)->step
= step
;
3321 (*slot
)->uses
.create (8);
3322 (*slot
)->hash
= ent
.hash
;
3323 data
->iv_common_cands
.safe_push ((*slot
));
3326 gcc_assert (use
!= NULL
);
3327 (*slot
)->uses
.safe_push (use
);
3331 /* Comparison function used to sort common candidates. */
3334 common_cand_cmp (const void *p1
, const void *p2
)
3337 const struct iv_common_cand
*const *const ccand1
3338 = (const struct iv_common_cand
*const *)p1
;
3339 const struct iv_common_cand
*const *const ccand2
3340 = (const struct iv_common_cand
*const *)p2
;
3342 n1
= (*ccand1
)->uses
.length ();
3343 n2
= (*ccand2
)->uses
.length ();
3347 /* Adds IV candidates based on common candidated recorded. */
3350 add_iv_candidate_derived_from_uses (struct ivopts_data
*data
)
3353 struct iv_cand
*cand_1
, *cand_2
;
3355 data
->iv_common_cands
.qsort (common_cand_cmp
);
3356 for (i
= 0; i
< data
->iv_common_cands
.length (); i
++)
3358 struct iv_common_cand
*ptr
= data
->iv_common_cands
[i
];
3360 /* Only add IV candidate if it's derived from multiple uses. */
3361 if (ptr
->uses
.length () <= 1)
3366 if (ip_normal_pos (data
->current_loop
))
3367 cand_1
= add_candidate_1 (data
, ptr
->base
, ptr
->step
,
3368 false, IP_NORMAL
, NULL
, NULL
);
3370 if (ip_end_pos (data
->current_loop
)
3371 && allow_ip_end_pos_p (data
->current_loop
))
3372 cand_2
= add_candidate_1 (data
, ptr
->base
, ptr
->step
,
3373 false, IP_END
, NULL
, NULL
);
3375 /* Bind deriving uses and the new candidates. */
3376 for (j
= 0; j
< ptr
->uses
.length (); j
++)
3378 struct iv_group
*group
= data
->vgroups
[ptr
->uses
[j
]->group_id
];
3380 bitmap_set_bit (group
->related_cands
, cand_1
->id
);
3382 bitmap_set_bit (group
->related_cands
, cand_2
->id
);
3386 /* Release data since it is useless from this point. */
3387 data
->iv_common_cand_tab
->empty ();
3388 data
->iv_common_cands
.truncate (0);
3391 /* Adds candidates based on the value of USE's iv. */
3394 add_iv_candidate_for_use (struct ivopts_data
*data
, struct iv_use
*use
)
3396 unsigned HOST_WIDE_INT offset
;
3399 struct iv
*iv
= use
->iv
;
3401 add_candidate (data
, iv
->base
, iv
->step
, false, use
);
3403 /* Record common candidate for use in case it can be shared by others. */
3404 record_common_cand (data
, iv
->base
, iv
->step
, use
);
3406 /* Record common candidate with initial value zero. */
3407 basetype
= TREE_TYPE (iv
->base
);
3408 if (POINTER_TYPE_P (basetype
))
3409 basetype
= sizetype
;
3410 record_common_cand (data
, build_int_cst (basetype
, 0), iv
->step
, use
);
3412 /* Record common candidate with constant offset stripped in base.
3413 Like the use itself, we also add candidate directly for it. */
3414 base
= strip_offset (iv
->base
, &offset
);
3415 if (offset
|| base
!= iv
->base
)
3417 record_common_cand (data
, base
, iv
->step
, use
);
3418 add_candidate (data
, base
, iv
->step
, false, use
);
3421 /* Record common candidate with base_object removed in base. */
3424 if (iv
->base_object
!= NULL
&& TREE_CODE (base
) == POINTER_PLUS_EXPR
)
3426 tree step
= iv
->step
;
3429 base
= TREE_OPERAND (base
, 1);
3430 step
= fold_convert (sizetype
, step
);
3431 record_common_cand (data
, base
, step
, use
);
3432 /* Also record common candidate with offset stripped. */
3433 base
= strip_offset (base
, &offset
);
3435 record_common_cand (data
, base
, step
, use
);
3438 /* At last, add auto-incremental candidates. Make such variables
3439 important since other iv uses with same base object may be based
3441 if (use
!= NULL
&& use
->type
== USE_ADDRESS
)
3442 add_autoinc_candidates (data
, iv
->base
, iv
->step
, true, use
);
3445 /* Adds candidates based on the uses. */
3448 add_iv_candidate_for_groups (struct ivopts_data
*data
)
3452 /* Only add candidate for the first use in group. */
3453 for (i
= 0; i
< data
->vgroups
.length (); i
++)
3455 struct iv_group
*group
= data
->vgroups
[i
];
3457 gcc_assert (group
->vuses
[0] != NULL
);
3458 add_iv_candidate_for_use (data
, group
->vuses
[0]);
3460 add_iv_candidate_derived_from_uses (data
);
3463 /* Record important candidates and add them to related_cands bitmaps. */
3466 record_important_candidates (struct ivopts_data
*data
)
3469 struct iv_group
*group
;
3471 for (i
= 0; i
< data
->vcands
.length (); i
++)
3473 struct iv_cand
*cand
= data
->vcands
[i
];
3475 if (cand
->important
)
3476 bitmap_set_bit (data
->important_candidates
, i
);
3479 data
->consider_all_candidates
= (data
->vcands
.length ()
3480 <= CONSIDER_ALL_CANDIDATES_BOUND
);
3482 /* Add important candidates to groups' related_cands bitmaps. */
3483 for (i
= 0; i
< data
->vgroups
.length (); i
++)
3485 group
= data
->vgroups
[i
];
3486 bitmap_ior_into (group
->related_cands
, data
->important_candidates
);
3490 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
3491 If consider_all_candidates is true, we use a two-dimensional array, otherwise
3492 we allocate a simple list to every use. */
3495 alloc_use_cost_map (struct ivopts_data
*data
)
3497 unsigned i
, size
, s
;
3499 for (i
= 0; i
< data
->vgroups
.length (); i
++)
3501 struct iv_group
*group
= data
->vgroups
[i
];
3503 if (data
->consider_all_candidates
)
3504 size
= data
->vcands
.length ();
3507 s
= bitmap_count_bits (group
->related_cands
);
3509 /* Round up to the power of two, so that moduling by it is fast. */
3510 size
= s
? (1 << ceil_log2 (s
)) : 1;
3513 group
->n_map_members
= size
;
3514 group
->cost_map
= XCNEWVEC (struct cost_pair
, size
);
3518 /* Sets cost of (GROUP, CAND) pair to COST and record that it depends
3519 on invariants INV_VARS and that the value used in expressing it is
3520 VALUE, and in case of iv elimination the comparison operator is COMP. */
3523 set_group_iv_cost (struct ivopts_data
*data
,
3524 struct iv_group
*group
, struct iv_cand
*cand
,
3525 comp_cost cost
, bitmap inv_vars
, tree value
,
3526 enum tree_code comp
, bitmap inv_exprs
)
3530 if (cost
.infinite_cost_p ())
3532 BITMAP_FREE (inv_vars
);
3533 BITMAP_FREE (inv_exprs
);
3537 if (data
->consider_all_candidates
)
3539 group
->cost_map
[cand
->id
].cand
= cand
;
3540 group
->cost_map
[cand
->id
].cost
= cost
;
3541 group
->cost_map
[cand
->id
].inv_vars
= inv_vars
;
3542 group
->cost_map
[cand
->id
].inv_exprs
= inv_exprs
;
3543 group
->cost_map
[cand
->id
].value
= value
;
3544 group
->cost_map
[cand
->id
].comp
= comp
;
3548 /* n_map_members is a power of two, so this computes modulo. */
3549 s
= cand
->id
& (group
->n_map_members
- 1);
3550 for (i
= s
; i
< group
->n_map_members
; i
++)
3551 if (!group
->cost_map
[i
].cand
)
3553 for (i
= 0; i
< s
; i
++)
3554 if (!group
->cost_map
[i
].cand
)
3560 group
->cost_map
[i
].cand
= cand
;
3561 group
->cost_map
[i
].cost
= cost
;
3562 group
->cost_map
[i
].inv_vars
= inv_vars
;
3563 group
->cost_map
[i
].inv_exprs
= inv_exprs
;
3564 group
->cost_map
[i
].value
= value
;
3565 group
->cost_map
[i
].comp
= comp
;
3568 /* Gets cost of (GROUP, CAND) pair. */
3570 static struct cost_pair
*
3571 get_group_iv_cost (struct ivopts_data
*data
, struct iv_group
*group
,
3572 struct iv_cand
*cand
)
3575 struct cost_pair
*ret
;
3580 if (data
->consider_all_candidates
)
3582 ret
= group
->cost_map
+ cand
->id
;
3589 /* n_map_members is a power of two, so this computes modulo. */
3590 s
= cand
->id
& (group
->n_map_members
- 1);
3591 for (i
= s
; i
< group
->n_map_members
; i
++)
3592 if (group
->cost_map
[i
].cand
== cand
)
3593 return group
->cost_map
+ i
;
3594 else if (group
->cost_map
[i
].cand
== NULL
)
3596 for (i
= 0; i
< s
; i
++)
3597 if (group
->cost_map
[i
].cand
== cand
)
3598 return group
->cost_map
+ i
;
3599 else if (group
->cost_map
[i
].cand
== NULL
)
3605 /* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
3607 produce_memory_decl_rtl (tree obj
, int *regno
)
3609 addr_space_t as
= TYPE_ADDR_SPACE (TREE_TYPE (obj
));
3610 machine_mode address_mode
= targetm
.addr_space
.address_mode (as
);
3614 if (TREE_STATIC (obj
) || DECL_EXTERNAL (obj
))
3616 const char *name
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj
));
3617 x
= gen_rtx_SYMBOL_REF (address_mode
, name
);
3618 SET_SYMBOL_REF_DECL (x
, obj
);
3619 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
3620 set_mem_addr_space (x
, as
);
3621 targetm
.encode_section_info (obj
, x
, true);
3625 x
= gen_raw_REG (address_mode
, (*regno
)++);
3626 x
= gen_rtx_MEM (DECL_MODE (obj
), x
);
3627 set_mem_addr_space (x
, as
);
3633 /* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
3634 walk_tree. DATA contains the actual fake register number. */
3637 prepare_decl_rtl (tree
*expr_p
, int *ws
, void *data
)
3639 tree obj
= NULL_TREE
;
3641 int *regno
= (int *) data
;
3643 switch (TREE_CODE (*expr_p
))
3646 for (expr_p
= &TREE_OPERAND (*expr_p
, 0);
3647 handled_component_p (*expr_p
);
3648 expr_p
= &TREE_OPERAND (*expr_p
, 0))
3651 if (DECL_P (obj
) && HAS_RTL_P (obj
) && !DECL_RTL_SET_P (obj
))
3652 x
= produce_memory_decl_rtl (obj
, regno
);
3657 obj
= SSA_NAME_VAR (*expr_p
);
3658 /* Defer handling of anonymous SSA_NAMEs to the expander. */
3661 if (!DECL_RTL_SET_P (obj
))
3662 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
3671 if (DECL_RTL_SET_P (obj
))
3674 if (DECL_MODE (obj
) == BLKmode
)
3675 x
= produce_memory_decl_rtl (obj
, regno
);
3677 x
= gen_raw_REG (DECL_MODE (obj
), (*regno
)++);
3687 decl_rtl_to_reset
.safe_push (obj
);
3688 SET_DECL_RTL (obj
, x
);
3694 /* Determines cost of the computation of EXPR. */
3697 computation_cost (tree expr
, bool speed
)
3701 tree type
= TREE_TYPE (expr
);
3703 /* Avoid using hard regs in ways which may be unsupported. */
3704 int regno
= LAST_VIRTUAL_REGISTER
+ 1;
3705 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
3706 enum node_frequency real_frequency
= node
->frequency
;
3708 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3709 crtl
->maybe_hot_insn_p
= speed
;
3710 walk_tree (&expr
, prepare_decl_rtl
, ®no
, NULL
);
3712 rslt
= expand_expr (expr
, NULL_RTX
, TYPE_MODE (type
), EXPAND_NORMAL
);
3715 default_rtl_profile ();
3716 node
->frequency
= real_frequency
;
3718 cost
= seq_cost (seq
, speed
);
3720 cost
+= address_cost (XEXP (rslt
, 0), TYPE_MODE (type
),
3721 TYPE_ADDR_SPACE (type
), speed
);
3722 else if (!REG_P (rslt
))
3723 cost
+= set_src_cost (rslt
, TYPE_MODE (type
), speed
);
3728 /* Returns variable containing the value of candidate CAND at statement AT. */
3731 var_at_stmt (struct loop
*loop
, struct iv_cand
*cand
, gimple
*stmt
)
3733 if (stmt_after_increment (loop
, cand
, stmt
))
3734 return cand
->var_after
;
3736 return cand
->var_before
;
3739 /* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
3740 same precision that is at least as wide as the precision of TYPE, stores
3741 BA to A and BB to B, and returns the type of BA. Otherwise, returns the
3745 determine_common_wider_type (tree
*a
, tree
*b
)
3747 tree wider_type
= NULL
;
3749 tree atype
= TREE_TYPE (*a
);
3751 if (CONVERT_EXPR_P (*a
))
3753 suba
= TREE_OPERAND (*a
, 0);
3754 wider_type
= TREE_TYPE (suba
);
3755 if (TYPE_PRECISION (wider_type
) < TYPE_PRECISION (atype
))
3761 if (CONVERT_EXPR_P (*b
))
3763 subb
= TREE_OPERAND (*b
, 0);
3764 if (TYPE_PRECISION (wider_type
) != TYPE_PRECISION (TREE_TYPE (subb
)))
3775 /* Determines the expression by that USE is expressed from induction variable
3776 CAND at statement AT in LOOP. The expression is stored in two parts in a
3777 decomposed form. The invariant part is stored in AFF_INV; while variant
3778 part in AFF_VAR. Store ratio of CAND.step over USE.step in PRAT if it's
3779 non-null. Returns false if USE cannot be expressed using CAND. */
3782 get_computation_aff_1 (struct loop
*loop
, gimple
*at
, struct iv_use
*use
,
3783 struct iv_cand
*cand
, struct aff_tree
*aff_inv
,
3784 struct aff_tree
*aff_var
, widest_int
*prat
= NULL
)
3786 tree ubase
= use
->iv
->base
, ustep
= use
->iv
->step
;
3787 tree cbase
= cand
->iv
->base
, cstep
= cand
->iv
->step
;
3788 tree common_type
, uutype
, var
, cstep_common
;
3789 tree utype
= TREE_TYPE (ubase
), ctype
= TREE_TYPE (cbase
);
3793 /* We must have a precision to express the values of use. */
3794 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
3797 var
= var_at_stmt (loop
, cand
, at
);
3798 uutype
= unsigned_type_for (utype
);
3800 /* If the conversion is not noop, perform it. */
3801 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
3803 if (cand
->orig_iv
!= NULL
&& CONVERT_EXPR_P (cbase
)
3804 && (CONVERT_EXPR_P (cstep
) || TREE_CODE (cstep
) == INTEGER_CST
))
3806 tree inner_base
, inner_step
, inner_type
;
3807 inner_base
= TREE_OPERAND (cbase
, 0);
3808 if (CONVERT_EXPR_P (cstep
))
3809 inner_step
= TREE_OPERAND (cstep
, 0);
3813 inner_type
= TREE_TYPE (inner_base
);
3814 /* If candidate is added from a biv whose type is smaller than
3815 ctype, we know both candidate and the biv won't overflow.
3816 In this case, it's safe to skip the convertion in candidate.
3817 As an example, (unsigned short)((unsigned long)A) equals to
3818 (unsigned short)A, if A has a type no larger than short. */
3819 if (TYPE_PRECISION (inner_type
) <= TYPE_PRECISION (uutype
))
3825 cbase
= fold_convert (uutype
, cbase
);
3826 cstep
= fold_convert (uutype
, cstep
);
3827 var
= fold_convert (uutype
, var
);
3830 /* Ratio is 1 when computing the value of biv cand by itself.
3831 We can't rely on constant_multiple_of in this case because the
3832 use is created after the original biv is selected. The call
3833 could fail because of inconsistent fold behavior. See PR68021
3834 for more information. */
3835 if (cand
->pos
== IP_ORIGINAL
&& cand
->incremented_at
== use
->stmt
)
3837 gcc_assert (is_gimple_assign (use
->stmt
));
3838 gcc_assert (use
->iv
->ssa_name
== cand
->var_after
);
3839 gcc_assert (gimple_assign_lhs (use
->stmt
) == cand
->var_after
);
3842 else if (!constant_multiple_of (ustep
, cstep
, &rat
))
3848 /* In case both UBASE and CBASE are shortened to UUTYPE from some common
3849 type, we achieve better folding by computing their difference in this
3850 wider type, and cast the result to UUTYPE. We do not need to worry about
3851 overflows, as all the arithmetics will in the end be performed in UUTYPE
3853 common_type
= determine_common_wider_type (&ubase
, &cbase
);
3855 /* use = ubase - ratio * cbase + ratio * var. */
3856 tree_to_aff_combination (ubase
, common_type
, aff_inv
);
3857 tree_to_aff_combination (cbase
, common_type
, &aff_cbase
);
3858 tree_to_aff_combination (var
, uutype
, aff_var
);
3860 /* We need to shift the value if we are after the increment. */
3861 if (stmt_after_increment (loop
, cand
, at
))
3865 if (common_type
!= uutype
)
3866 cstep_common
= fold_convert (common_type
, cstep
);
3868 cstep_common
= cstep
;
3870 tree_to_aff_combination (cstep_common
, common_type
, &cstep_aff
);
3871 aff_combination_add (&aff_cbase
, &cstep_aff
);
3874 aff_combination_scale (&aff_cbase
, -rat
);
3875 aff_combination_add (aff_inv
, &aff_cbase
);
3876 if (common_type
!= uutype
)
3877 aff_combination_convert (aff_inv
, uutype
);
3879 aff_combination_scale (aff_var
, rat
);
3883 /* Determines the expression by that USE is expressed from induction variable
3884 CAND at statement AT in LOOP. The expression is stored in a decomposed
3885 form into AFF. Returns false if USE cannot be expressed using CAND. */
3888 get_computation_aff (struct loop
*loop
, gimple
*at
, struct iv_use
*use
,
3889 struct iv_cand
*cand
, struct aff_tree
*aff
)
3893 if (!get_computation_aff_1 (loop
, at
, use
, cand
, aff
, &aff_var
))
3896 aff_combination_add (aff
, &aff_var
);
3900 /* Return the type of USE. */
3903 get_use_type (struct iv_use
*use
)
3905 tree base_type
= TREE_TYPE (use
->iv
->base
);
3908 if (use
->type
== USE_ADDRESS
)
3910 /* The base_type may be a void pointer. Create a pointer type based on
3911 the mem_ref instead. */
3912 type
= build_pointer_type (TREE_TYPE (*use
->op_p
));
3913 gcc_assert (TYPE_ADDR_SPACE (TREE_TYPE (type
))
3914 == TYPE_ADDR_SPACE (TREE_TYPE (base_type
)));
3922 /* Determines the expression by that USE is expressed from induction variable
3923 CAND at statement AT in LOOP. The computation is unshared. */
3926 get_computation_at (struct loop
*loop
, gimple
*at
,
3927 struct iv_use
*use
, struct iv_cand
*cand
)
3930 tree type
= get_use_type (use
);
3932 if (!get_computation_aff (loop
, at
, use
, cand
, &aff
))
3934 unshare_aff_combination (&aff
);
3935 return fold_convert (type
, aff_combination_to_tree (&aff
));
3938 /* Adjust the cost COST for being in loop setup rather than loop body.
3939 If we're optimizing for space, the loop setup overhead is constant;
3940 if we're optimizing for speed, amortize it over the per-iteration cost.
3941 If ROUND_UP_P is true, the result is round up rather than to zero when
3942 optimizing for speed. */
3944 adjust_setup_cost (struct ivopts_data
*data
, unsigned cost
,
3945 bool round_up_p
= false)
3949 else if (optimize_loop_for_speed_p (data
->current_loop
))
3951 HOST_WIDE_INT niters
= avg_loop_niter (data
->current_loop
);
3952 return ((HOST_WIDE_INT
) cost
+ (round_up_p
? niters
- 1 : 0)) / niters
;
3958 /* Calculate the SPEED or size cost of shiftadd EXPR in MODE. MULT is the
3959 EXPR operand holding the shift. COST0 and COST1 are the costs for
3960 calculating the operands of EXPR. Returns true if successful, and returns
3961 the cost in COST. */
3964 get_shiftadd_cost (tree expr
, machine_mode mode
, comp_cost cost0
,
3965 comp_cost cost1
, tree mult
, bool speed
, comp_cost
*cost
)
3968 tree op1
= TREE_OPERAND (expr
, 1);
3969 tree cst
= TREE_OPERAND (mult
, 1);
3970 tree multop
= TREE_OPERAND (mult
, 0);
3971 int m
= exact_log2 (int_cst_value (cst
));
3972 int maxm
= MIN (BITS_PER_WORD
, GET_MODE_BITSIZE (mode
));
3973 int as_cost
, sa_cost
;
3976 if (!(m
>= 0 && m
< maxm
))
3980 mult_in_op1
= operand_equal_p (op1
, mult
, 0);
3982 as_cost
= add_cost (speed
, mode
) + shift_cost (speed
, mode
, m
);
3984 /* If the target has a cheap shift-and-add or shift-and-sub instruction,
3985 use that in preference to a shift insn followed by an add insn. */
3986 sa_cost
= (TREE_CODE (expr
) != MINUS_EXPR
3987 ? shiftadd_cost (speed
, mode
, m
)
3989 ? shiftsub1_cost (speed
, mode
, m
)
3990 : shiftsub0_cost (speed
, mode
, m
)));
3992 res
= comp_cost (MIN (as_cost
, sa_cost
), 0);
3993 res
+= (mult_in_op1
? cost0
: cost1
);
3995 STRIP_NOPS (multop
);
3996 if (!is_gimple_val (multop
))
3997 res
+= force_expr_to_var_cost (multop
, speed
);
4003 /* Estimates cost of forcing expression EXPR into a variable. */
4006 force_expr_to_var_cost (tree expr
, bool speed
)
4008 static bool costs_initialized
= false;
4009 static unsigned integer_cost
[2];
4010 static unsigned symbol_cost
[2];
4011 static unsigned address_cost
[2];
4013 comp_cost cost0
, cost1
, cost
;
4016 if (!costs_initialized
)
4018 tree type
= build_pointer_type (integer_type_node
);
4023 var
= create_tmp_var_raw (integer_type_node
, "test_var");
4024 TREE_STATIC (var
) = 1;
4025 x
= produce_memory_decl_rtl (var
, NULL
);
4026 SET_DECL_RTL (var
, x
);
4028 addr
= build1 (ADDR_EXPR
, type
, var
);
4031 for (i
= 0; i
< 2; i
++)
4033 integer_cost
[i
] = computation_cost (build_int_cst (integer_type_node
,
4036 symbol_cost
[i
] = computation_cost (addr
, i
) + 1;
4039 = computation_cost (fold_build_pointer_plus_hwi (addr
, 2000), i
) + 1;
4040 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4042 fprintf (dump_file
, "force_expr_to_var_cost %s costs:\n", i
? "speed" : "size");
4043 fprintf (dump_file
, " integer %d\n", (int) integer_cost
[i
]);
4044 fprintf (dump_file
, " symbol %d\n", (int) symbol_cost
[i
]);
4045 fprintf (dump_file
, " address %d\n", (int) address_cost
[i
]);
4046 fprintf (dump_file
, " other %d\n", (int) target_spill_cost
[i
]);
4047 fprintf (dump_file
, "\n");
4051 costs_initialized
= true;
4056 if (SSA_VAR_P (expr
))
4059 if (is_gimple_min_invariant (expr
))
4061 if (TREE_CODE (expr
) == INTEGER_CST
)
4062 return comp_cost (integer_cost
[speed
], 0);
4064 if (TREE_CODE (expr
) == ADDR_EXPR
)
4066 tree obj
= TREE_OPERAND (expr
, 0);
4069 || TREE_CODE (obj
) == PARM_DECL
4070 || TREE_CODE (obj
) == RESULT_DECL
)
4071 return comp_cost (symbol_cost
[speed
], 0);
4074 return comp_cost (address_cost
[speed
], 0);
4077 switch (TREE_CODE (expr
))
4079 case POINTER_PLUS_EXPR
:
4083 case TRUNC_DIV_EXPR
:
4088 op0
= TREE_OPERAND (expr
, 0);
4089 op1
= TREE_OPERAND (expr
, 1);
4097 op0
= TREE_OPERAND (expr
, 0);
4103 /* Just an arbitrary value, FIXME. */
4104 return comp_cost (target_spill_cost
[speed
], 0);
4107 if (op0
== NULL_TREE
4108 || TREE_CODE (op0
) == SSA_NAME
|| CONSTANT_CLASS_P (op0
))
4111 cost0
= force_expr_to_var_cost (op0
, speed
);
4113 if (op1
== NULL_TREE
4114 || TREE_CODE (op1
) == SSA_NAME
|| CONSTANT_CLASS_P (op1
))
4117 cost1
= force_expr_to_var_cost (op1
, speed
);
4119 mode
= TYPE_MODE (TREE_TYPE (expr
));
4120 switch (TREE_CODE (expr
))
4122 case POINTER_PLUS_EXPR
:
4126 cost
= comp_cost (add_cost (speed
, mode
), 0);
4127 if (TREE_CODE (expr
) != NEGATE_EXPR
)
4129 tree mult
= NULL_TREE
;
4131 if (TREE_CODE (op1
) == MULT_EXPR
)
4133 else if (TREE_CODE (op0
) == MULT_EXPR
)
4136 if (mult
!= NULL_TREE
4137 && cst_and_fits_in_hwi (TREE_OPERAND (mult
, 1))
4138 && get_shiftadd_cost (expr
, mode
, cost0
, cost1
, mult
,
4146 tree inner_mode
, outer_mode
;
4147 outer_mode
= TREE_TYPE (expr
);
4148 inner_mode
= TREE_TYPE (op0
);
4149 cost
= comp_cost (convert_cost (TYPE_MODE (outer_mode
),
4150 TYPE_MODE (inner_mode
), speed
), 0);
4155 if (cst_and_fits_in_hwi (op0
))
4156 cost
= comp_cost (mult_by_coeff_cost (int_cst_value (op0
),
4158 else if (cst_and_fits_in_hwi (op1
))
4159 cost
= comp_cost (mult_by_coeff_cost (int_cst_value (op1
),
4162 return comp_cost (target_spill_cost
[speed
], 0);
4165 case TRUNC_DIV_EXPR
:
4166 /* Division by power of two is usually cheap, so we allow it. Forbid
4168 if (integer_pow2p (TREE_OPERAND (expr
, 1)))
4169 cost
= comp_cost (add_cost (speed
, mode
), 0);
4171 cost
= comp_cost (target_spill_cost
[speed
], 0);
4179 cost
= comp_cost (add_cost (speed
, mode
), 0);
4191 /* Estimates cost of forcing EXPR into a variable. INV_VARS is a set of the
4192 invariants the computation depends on. */
4195 force_var_cost (struct ivopts_data
*data
, tree expr
, bitmap
*inv_vars
)
4200 find_inv_vars (data
, &expr
, inv_vars
);
4201 return force_expr_to_var_cost (expr
, data
->speed
);
4204 /* Returns cost of auto-modifying address expression in shape base + offset.
4205 AINC_STEP is step size of the address IV. AINC_OFFSET is offset of the
4206 address expression. The address expression has ADDR_MODE in addr space
4207 AS. The memory access has MEM_MODE. SPEED means we are optimizing for
4212 AINC_PRE_INC
, /* Pre increment. */
4213 AINC_PRE_DEC
, /* Pre decrement. */
4214 AINC_POST_INC
, /* Post increment. */
4215 AINC_POST_DEC
, /* Post decrement. */
4216 AINC_NONE
/* Also the number of auto increment types. */
4219 struct ainc_cost_data
4221 unsigned costs
[AINC_NONE
];
4225 get_address_cost_ainc (HOST_WIDE_INT ainc_step
, HOST_WIDE_INT ainc_offset
,
4226 machine_mode addr_mode
, machine_mode mem_mode
,
4227 addr_space_t as
, bool speed
)
4229 if (!USE_LOAD_PRE_DECREMENT (mem_mode
)
4230 && !USE_STORE_PRE_DECREMENT (mem_mode
)
4231 && !USE_LOAD_POST_DECREMENT (mem_mode
)
4232 && !USE_STORE_POST_DECREMENT (mem_mode
)
4233 && !USE_LOAD_PRE_INCREMENT (mem_mode
)
4234 && !USE_STORE_PRE_INCREMENT (mem_mode
)
4235 && !USE_LOAD_POST_INCREMENT (mem_mode
)
4236 && !USE_STORE_POST_INCREMENT (mem_mode
))
4237 return infinite_cost
;
4239 static vec
<ainc_cost_data
*> ainc_cost_data_list
;
4240 unsigned idx
= (unsigned) as
* MAX_MACHINE_MODE
+ (unsigned) mem_mode
;
4241 if (idx
>= ainc_cost_data_list
.length ())
4243 unsigned nsize
= ((unsigned) as
+ 1) *MAX_MACHINE_MODE
;
4245 gcc_assert (nsize
> idx
);
4246 ainc_cost_data_list
.safe_grow_cleared (nsize
);
4249 ainc_cost_data
*data
= ainc_cost_data_list
[idx
];
4252 rtx reg
= gen_raw_REG (addr_mode
, LAST_VIRTUAL_REGISTER
+ 1);
4254 data
= (ainc_cost_data
*) xcalloc (1, sizeof (*data
));
4255 data
->costs
[AINC_PRE_DEC
] = INFTY
;
4256 data
->costs
[AINC_POST_DEC
] = INFTY
;
4257 data
->costs
[AINC_PRE_INC
] = INFTY
;
4258 data
->costs
[AINC_POST_INC
] = INFTY
;
4259 if (USE_LOAD_PRE_DECREMENT (mem_mode
)
4260 || USE_STORE_PRE_DECREMENT (mem_mode
))
4262 rtx addr
= gen_rtx_PRE_DEC (addr_mode
, reg
);
4264 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
4265 data
->costs
[AINC_PRE_DEC
]
4266 = address_cost (addr
, mem_mode
, as
, speed
);
4268 if (USE_LOAD_POST_DECREMENT (mem_mode
)
4269 || USE_STORE_POST_DECREMENT (mem_mode
))
4271 rtx addr
= gen_rtx_POST_DEC (addr_mode
, reg
);
4273 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
4274 data
->costs
[AINC_POST_DEC
]
4275 = address_cost (addr
, mem_mode
, as
, speed
);
4277 if (USE_LOAD_PRE_INCREMENT (mem_mode
)
4278 || USE_STORE_PRE_INCREMENT (mem_mode
))
4280 rtx addr
= gen_rtx_PRE_INC (addr_mode
, reg
);
4282 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
4283 data
->costs
[AINC_PRE_INC
]
4284 = address_cost (addr
, mem_mode
, as
, speed
);
4286 if (USE_LOAD_POST_INCREMENT (mem_mode
)
4287 || USE_STORE_POST_INCREMENT (mem_mode
))
4289 rtx addr
= gen_rtx_POST_INC (addr_mode
, reg
);
4291 if (memory_address_addr_space_p (mem_mode
, addr
, as
))
4292 data
->costs
[AINC_POST_INC
]
4293 = address_cost (addr
, mem_mode
, as
, speed
);
4295 ainc_cost_data_list
[idx
] = data
;
4298 HOST_WIDE_INT msize
= GET_MODE_SIZE (mem_mode
);
4299 if (ainc_offset
== 0 && msize
== ainc_step
)
4300 return comp_cost (data
->costs
[AINC_POST_INC
], 0);
4301 if (ainc_offset
== 0 && msize
== -ainc_step
)
4302 return comp_cost (data
->costs
[AINC_POST_DEC
], 0);
4303 if (ainc_offset
== msize
&& msize
== ainc_step
)
4304 return comp_cost (data
->costs
[AINC_PRE_INC
], 0);
4305 if (ainc_offset
== -msize
&& msize
== -ainc_step
)
4306 return comp_cost (data
->costs
[AINC_PRE_DEC
], 0);
4308 return infinite_cost
;
4311 /* Return cost of computing USE's address expression by using CAND.
4312 AFF_INV and AFF_VAR represent invariant and variant parts of the
4313 address expression, respectively. If AFF_INV is simple, store
4314 the loop invariant variables which are depended by it in INV_VARS;
4315 if AFF_INV is complicated, handle it as a new invariant expression
4316 and record it in INV_EXPR. RATIO indicates multiple times between
4317 steps of USE and CAND. If CAN_AUTOINC is nonNULL, store boolean
4318 value to it indicating if this is an auto-increment address. */
4321 get_address_cost (struct ivopts_data
*data
, struct iv_use
*use
,
4322 struct iv_cand
*cand
, aff_tree
*aff_inv
,
4323 aff_tree
*aff_var
, HOST_WIDE_INT ratio
,
4324 bitmap
*inv_vars
, iv_inv_expr_ent
**inv_expr
,
4325 bool *can_autoinc
, bool speed
)
4328 bool simple_inv
= true;
4329 tree comp_inv
= NULL_TREE
, type
= aff_var
->type
;
4330 comp_cost var_cost
= no_cost
, cost
= no_cost
;
4331 struct mem_address parts
= {NULL_TREE
, integer_one_node
,
4332 NULL_TREE
, NULL_TREE
, NULL_TREE
};
4333 machine_mode addr_mode
= TYPE_MODE (type
);
4334 machine_mode mem_mode
= TYPE_MODE (TREE_TYPE (*use
->op_p
));
4335 addr_space_t as
= TYPE_ADDR_SPACE (TREE_TYPE (use
->iv
->base
));
4337 if (!aff_combination_const_p (aff_inv
))
4339 parts
.index
= integer_one_node
;
4340 /* Addressing mode "base + index". */
4341 if (valid_mem_ref_p (mem_mode
, as
, &parts
))
4343 parts
.step
= wide_int_to_tree (type
, ratio
);
4344 /* Addressing mode "base + index << scale". */
4345 if (ratio
!= 1 && !valid_mem_ref_p (mem_mode
, as
, &parts
))
4346 parts
.step
= NULL_TREE
;
4348 if (aff_inv
->offset
!= 0)
4350 parts
.offset
= wide_int_to_tree (sizetype
, aff_inv
->offset
);
4351 /* Addressing mode "base + index [<< scale] + offset". */
4352 if (!valid_mem_ref_p (mem_mode
, as
, &parts
))
4353 parts
.offset
= NULL_TREE
;
4355 aff_inv
->offset
= 0;
4358 move_fixed_address_to_symbol (&parts
, aff_inv
);
4359 /* Base is fixed address and is moved to symbol part. */
4360 if (parts
.symbol
!= NULL_TREE
&& aff_combination_zero_p (aff_inv
))
4361 parts
.base
= NULL_TREE
;
4363 /* Addressing mode "symbol + base + index [<< scale] [+ offset]". */
4364 if (parts
.symbol
!= NULL_TREE
4365 && !valid_mem_ref_p (mem_mode
, as
, &parts
))
4367 aff_combination_add_elt (aff_inv
, parts
.symbol
, 1);
4368 parts
.symbol
= NULL_TREE
;
4369 /* Reset SIMPLE_INV since symbol address needs to be computed
4370 outside of address expression in this case. */
4372 /* Symbol part is moved back to base part, it can't be NULL. */
4373 parts
.base
= integer_one_node
;
4377 parts
.index
= NULL_TREE
;
4381 if (can_autoinc
&& ratio
== 1 && cst_and_fits_in_hwi (cand
->iv
->step
))
4383 HOST_WIDE_INT ainc_step
= int_cst_value (cand
->iv
->step
);
4384 HOST_WIDE_INT ainc_offset
= (aff_inv
->offset
).to_shwi ();
4386 if (stmt_after_increment (data
->current_loop
, cand
, use
->stmt
))
4387 ainc_offset
+= ainc_step
;
4388 cost
= get_address_cost_ainc (ainc_step
, ainc_offset
,
4389 addr_mode
, mem_mode
, as
, speed
);
4390 if (!cost
.infinite_cost_p ())
4392 *can_autoinc
= true;
4397 if (!aff_combination_zero_p (aff_inv
))
4399 parts
.offset
= wide_int_to_tree (sizetype
, aff_inv
->offset
);
4400 /* Addressing mode "base + offset". */
4401 if (!valid_mem_ref_p (mem_mode
, as
, &parts
))
4402 parts
.offset
= NULL_TREE
;
4404 aff_inv
->offset
= 0;
4409 simple_inv
= (aff_inv
== NULL
4410 || aff_combination_const_p (aff_inv
)
4411 || aff_combination_singleton_var_p (aff_inv
));
4412 if (!aff_combination_zero_p (aff_inv
))
4413 comp_inv
= aff_combination_to_tree (aff_inv
);
4414 if (comp_inv
!= NULL_TREE
)
4415 cost
= force_var_cost (data
, comp_inv
, inv_vars
);
4416 if (ratio
!= 1 && parts
.step
== NULL_TREE
)
4417 var_cost
+= mult_by_coeff_cost (ratio
, addr_mode
, speed
);
4418 if (comp_inv
!= NULL_TREE
&& parts
.index
== NULL_TREE
)
4419 var_cost
+= add_cost (speed
, addr_mode
);
4421 if (comp_inv
&& inv_expr
&& !simple_inv
)
4423 *inv_expr
= get_loop_invariant_expr (data
, comp_inv
);
4424 /* Clear depends on. */
4425 if (*inv_expr
!= NULL
&& inv_vars
&& *inv_vars
)
4426 bitmap_clear (*inv_vars
);
4428 /* Cost of small invariant expression adjusted against loop niters
4429 is usually zero, which makes it difficult to be differentiated
4430 from candidate based on loop invariant variables. Secondly, the
4431 generated invariant expression may not be hoisted out of loop by
4432 following pass. We penalize the cost by rounding up in order to
4433 neutralize such effects. */
4434 cost
.cost
= adjust_setup_cost (data
, cost
.cost
, true);
4435 cost
.scratch
= cost
.cost
;
4439 addr
= addr_for_mem_ref (&parts
, as
, false);
4440 gcc_assert (memory_address_addr_space_p (mem_mode
, addr
, as
));
4441 cost
+= address_cost (addr
, mem_mode
, as
, speed
);
4443 if (parts
.symbol
!= NULL_TREE
)
4444 cost
.complexity
+= 1;
4445 if (parts
.step
!= NULL_TREE
&& !integer_onep (parts
.step
))
4446 cost
.complexity
+= 1;
4447 if (parts
.base
!= NULL_TREE
&& parts
.index
!= NULL_TREE
)
4448 cost
.complexity
+= 1;
4449 if (parts
.offset
!= NULL_TREE
&& !integer_zerop (parts
.offset
))
4450 cost
.complexity
+= 1;
4455 /* Scale (multiply) the computed COST (except scratch part that should be
4456 hoisted out a loop) by header->frequency / AT->frequency, which makes
4457 expected cost more accurate. */
4460 get_scaled_computation_cost_at (ivopts_data
*data
, gimple
*at
, comp_cost cost
)
4462 int loop_freq
= data
->current_loop
->header
->frequency
;
4463 int bb_freq
= gimple_bb (at
)->frequency
;
4466 gcc_assert (cost
.scratch
<= cost
.cost
);
4468 = cost
.scratch
+ (cost
.cost
- cost
.scratch
) * bb_freq
/ loop_freq
;
4470 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4471 fprintf (dump_file
, "Scaling cost based on bb prob "
4472 "by %2.2f: %d (scratch: %d) -> %d (%d/%d)\n",
4473 1.0f
* bb_freq
/ loop_freq
, cost
.cost
,
4474 cost
.scratch
, scaled_cost
, bb_freq
, loop_freq
);
4476 cost
.cost
= scaled_cost
;
4482 /* Determines the cost of the computation by that USE is expressed
4483 from induction variable CAND. If ADDRESS_P is true, we just need
4484 to create an address from it, otherwise we want to get it into
4485 register. A set of invariants we depend on is stored in INV_VARS.
4486 If CAN_AUTOINC is nonnull, use it to record whether autoinc
4487 addressing is likely. If INV_EXPR is nonnull, record invariant
4488 expr entry in it. */
4491 get_computation_cost (struct ivopts_data
*data
, struct iv_use
*use
,
4492 struct iv_cand
*cand
, bool address_p
, bitmap
*inv_vars
,
4493 bool *can_autoinc
, iv_inv_expr_ent
**inv_expr
)
4495 gimple
*at
= use
->stmt
;
4496 tree ubase
= use
->iv
->base
, cbase
= cand
->iv
->base
;
4497 tree utype
= TREE_TYPE (ubase
), ctype
= TREE_TYPE (cbase
);
4498 tree comp_inv
= NULL_TREE
;
4499 HOST_WIDE_INT ratio
, aratio
;
4502 aff_tree aff_inv
, aff_var
;
4503 bool speed
= optimize_bb_for_speed_p (gimple_bb (at
));
4508 *can_autoinc
= false;
4512 /* Check if we have enough precision to express the values of use. */
4513 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (ctype
))
4514 return infinite_cost
;
4517 || (use
->iv
->base_object
4518 && cand
->iv
->base_object
4519 && POINTER_TYPE_P (TREE_TYPE (use
->iv
->base_object
))
4520 && POINTER_TYPE_P (TREE_TYPE (cand
->iv
->base_object
))))
4522 /* Do not try to express address of an object with computation based
4523 on address of a different object. This may cause problems in rtl
4524 level alias analysis (that does not expect this to be happening,
4525 as this is illegal in C), and would be unlikely to be useful
4527 if (use
->iv
->base_object
4528 && cand
->iv
->base_object
4529 && !operand_equal_p (use
->iv
->base_object
, cand
->iv
->base_object
, 0))
4530 return infinite_cost
;
4533 if (!get_computation_aff_1 (data
->current_loop
, at
, use
,
4534 cand
, &aff_inv
, &aff_var
, &rat
)
4535 || !wi::fits_shwi_p (rat
))
4536 return infinite_cost
;
4538 ratio
= rat
.to_shwi ();
4541 cost
= get_address_cost (data
, use
, cand
, &aff_inv
, &aff_var
, ratio
,
4542 inv_vars
, inv_expr
, can_autoinc
, speed
);
4543 return get_scaled_computation_cost_at (data
, at
, cost
);
4546 bool simple_inv
= (aff_combination_const_p (&aff_inv
)
4547 || aff_combination_singleton_var_p (&aff_inv
));
4548 tree signed_type
= signed_type_for (aff_combination_type (&aff_inv
));
4549 aff_combination_convert (&aff_inv
, signed_type
);
4550 if (!aff_combination_zero_p (&aff_inv
))
4551 comp_inv
= aff_combination_to_tree (&aff_inv
);
4553 cost
= force_var_cost (data
, comp_inv
, inv_vars
);
4554 if (comp_inv
&& inv_expr
&& !simple_inv
)
4556 *inv_expr
= get_loop_invariant_expr (data
, comp_inv
);
4557 /* Clear depends on. */
4558 if (*inv_expr
!= NULL
&& inv_vars
&& *inv_vars
)
4559 bitmap_clear (*inv_vars
);
4561 cost
.cost
= adjust_setup_cost (data
, cost
.cost
);
4562 /* Record setup cost in scratch field. */
4563 cost
.scratch
= cost
.cost
;
4565 /* Cost of constant integer can be covered when adding invariant part to
4567 else if (comp_inv
&& CONSTANT_CLASS_P (comp_inv
))
4570 /* Need type narrowing to represent use with cand. */
4571 if (TYPE_PRECISION (utype
) < TYPE_PRECISION (ctype
))
4573 machine_mode outer_mode
= TYPE_MODE (utype
);
4574 machine_mode inner_mode
= TYPE_MODE (ctype
);
4575 cost
+= comp_cost (convert_cost (outer_mode
, inner_mode
, speed
), 0);
4578 /* Turn a + i * (-c) into a - i * c. */
4579 if (ratio
< 0 && comp_inv
&& !integer_zerop (comp_inv
))
4585 cost
+= mult_by_coeff_cost (aratio
, TYPE_MODE (utype
), speed
);
4587 /* TODO: We may also need to check if we can compute a + i * 4 in one
4589 /* Need to add up the invariant and variant parts. */
4590 if (comp_inv
&& !integer_zerop (comp_inv
))
4591 cost
+= add_cost (speed
, TYPE_MODE (utype
));
4593 return get_scaled_computation_cost_at (data
, at
, cost
);
4596 /* Determines cost of computing the use in GROUP with CAND in a generic
4600 determine_group_iv_cost_generic (struct ivopts_data
*data
,
4601 struct iv_group
*group
, struct iv_cand
*cand
)
4604 iv_inv_expr_ent
*inv_expr
= NULL
;
4605 bitmap inv_vars
= NULL
, inv_exprs
= NULL
;
4606 struct iv_use
*use
= group
->vuses
[0];
4608 /* The simple case first -- if we need to express value of the preserved
4609 original biv, the cost is 0. This also prevents us from counting the
4610 cost of increment twice -- once at this use and once in the cost of
4612 if (cand
->pos
== IP_ORIGINAL
&& cand
->incremented_at
== use
->stmt
)
4615 cost
= get_computation_cost (data
, use
, cand
, false,
4616 &inv_vars
, NULL
, &inv_expr
);
4620 inv_exprs
= BITMAP_ALLOC (NULL
);
4621 bitmap_set_bit (inv_exprs
, inv_expr
->id
);
4623 set_group_iv_cost (data
, group
, cand
, cost
, inv_vars
,
4624 NULL_TREE
, ERROR_MARK
, inv_exprs
);
4625 return !cost
.infinite_cost_p ();
4628 /* Determines cost of computing uses in GROUP with CAND in addresses. */
4631 determine_group_iv_cost_address (struct ivopts_data
*data
,
4632 struct iv_group
*group
, struct iv_cand
*cand
)
4635 bitmap inv_vars
= NULL
, inv_exprs
= NULL
;
4637 iv_inv_expr_ent
*inv_expr
= NULL
;
4638 struct iv_use
*use
= group
->vuses
[0];
4639 comp_cost sum_cost
= no_cost
, cost
;
4641 cost
= get_computation_cost (data
, use
, cand
, true,
4642 &inv_vars
, &can_autoinc
, &inv_expr
);
4646 inv_exprs
= BITMAP_ALLOC (NULL
);
4647 bitmap_set_bit (inv_exprs
, inv_expr
->id
);
4650 if (!sum_cost
.infinite_cost_p () && cand
->ainc_use
== use
)
4653 sum_cost
-= cand
->cost_step
;
4654 /* If we generated the candidate solely for exploiting autoincrement
4655 opportunities, and it turns out it can't be used, set the cost to
4656 infinity to make sure we ignore it. */
4657 else if (cand
->pos
== IP_AFTER_USE
|| cand
->pos
== IP_BEFORE_USE
)
4658 sum_cost
= infinite_cost
;
4661 /* Uses in a group can share setup code, so only add setup cost once. */
4662 cost
-= cost
.scratch
;
4663 /* Compute and add costs for rest uses of this group. */
4664 for (i
= 1; i
< group
->vuses
.length () && !sum_cost
.infinite_cost_p (); i
++)
4666 struct iv_use
*next
= group
->vuses
[i
];
4668 /* TODO: We could skip computing cost for sub iv_use when it has the
4669 same cost as the first iv_use, but the cost really depends on the
4670 offset and where the iv_use is. */
4671 cost
= get_computation_cost (data
, next
, cand
, true,
4672 NULL
, &can_autoinc
, &inv_expr
);
4676 inv_exprs
= BITMAP_ALLOC (NULL
);
4678 bitmap_set_bit (inv_exprs
, inv_expr
->id
);
4682 set_group_iv_cost (data
, group
, cand
, sum_cost
, inv_vars
,
4683 NULL_TREE
, ERROR_MARK
, inv_exprs
);
4685 return !sum_cost
.infinite_cost_p ();
4688 /* Computes value of candidate CAND at position AT in iteration NITER, and
4689 stores it to VAL. */
4692 cand_value_at (struct loop
*loop
, struct iv_cand
*cand
, gimple
*at
, tree niter
,
4695 aff_tree step
, delta
, nit
;
4696 struct iv
*iv
= cand
->iv
;
4697 tree type
= TREE_TYPE (iv
->base
);
4699 if (POINTER_TYPE_P (type
))
4700 steptype
= sizetype
;
4702 steptype
= unsigned_type_for (type
);
4704 tree_to_aff_combination (iv
->step
, TREE_TYPE (iv
->step
), &step
);
4705 aff_combination_convert (&step
, steptype
);
4706 tree_to_aff_combination (niter
, TREE_TYPE (niter
), &nit
);
4707 aff_combination_convert (&nit
, steptype
);
4708 aff_combination_mult (&nit
, &step
, &delta
);
4709 if (stmt_after_increment (loop
, cand
, at
))
4710 aff_combination_add (&delta
, &step
);
4712 tree_to_aff_combination (iv
->base
, type
, val
);
4713 if (!POINTER_TYPE_P (type
))
4714 aff_combination_convert (val
, steptype
);
4715 aff_combination_add (val
, &delta
);
4718 /* Returns period of induction variable iv. */
4721 iv_period (struct iv
*iv
)
4723 tree step
= iv
->step
, period
, type
;
4726 gcc_assert (step
&& TREE_CODE (step
) == INTEGER_CST
);
4728 type
= unsigned_type_for (TREE_TYPE (step
));
4729 /* Period of the iv is lcm (step, type_range)/step -1,
4730 i.e., N*type_range/step - 1. Since type range is power
4731 of two, N == (step >> num_of_ending_zeros_binary (step),
4732 so the final result is
4734 (type_range >> num_of_ending_zeros_binary (step)) - 1
4737 pow2div
= num_ending_zeros (step
);
4739 period
= build_low_bits_mask (type
,
4740 (TYPE_PRECISION (type
)
4741 - tree_to_uhwi (pow2div
)));
4746 /* Returns the comparison operator used when eliminating the iv USE. */
4748 static enum tree_code
4749 iv_elimination_compare (struct ivopts_data
*data
, struct iv_use
*use
)
4751 struct loop
*loop
= data
->current_loop
;
4755 ex_bb
= gimple_bb (use
->stmt
);
4756 exit
= EDGE_SUCC (ex_bb
, 0);
4757 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
4758 exit
= EDGE_SUCC (ex_bb
, 1);
4760 return (exit
->flags
& EDGE_TRUE_VALUE
? EQ_EXPR
: NE_EXPR
);
4763 /* Returns true if we can prove that BASE - OFFSET does not overflow. For now,
4764 we only detect the situation that BASE = SOMETHING + OFFSET, where the
4765 calculation is performed in non-wrapping type.
4767 TODO: More generally, we could test for the situation that
4768 BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero.
4769 This would require knowing the sign of OFFSET. */
4772 difference_cannot_overflow_p (struct ivopts_data
*data
, tree base
, tree offset
)
4774 enum tree_code code
;
4776 aff_tree aff_e1
, aff_e2
, aff_offset
;
4778 if (!nowrap_type_p (TREE_TYPE (base
)))
4781 base
= expand_simple_operations (base
);
4783 if (TREE_CODE (base
) == SSA_NAME
)
4785 gimple
*stmt
= SSA_NAME_DEF_STMT (base
);
4787 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
4790 code
= gimple_assign_rhs_code (stmt
);
4791 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
4794 e1
= gimple_assign_rhs1 (stmt
);
4795 e2
= gimple_assign_rhs2 (stmt
);
4799 code
= TREE_CODE (base
);
4800 if (get_gimple_rhs_class (code
) != GIMPLE_BINARY_RHS
)
4802 e1
= TREE_OPERAND (base
, 0);
4803 e2
= TREE_OPERAND (base
, 1);
4806 /* Use affine expansion as deeper inspection to prove the equality. */
4807 tree_to_aff_combination_expand (e2
, TREE_TYPE (e2
),
4808 &aff_e2
, &data
->name_expansion_cache
);
4809 tree_to_aff_combination_expand (offset
, TREE_TYPE (offset
),
4810 &aff_offset
, &data
->name_expansion_cache
);
4811 aff_combination_scale (&aff_offset
, -1);
4815 aff_combination_add (&aff_e2
, &aff_offset
);
4816 if (aff_combination_zero_p (&aff_e2
))
4819 tree_to_aff_combination_expand (e1
, TREE_TYPE (e1
),
4820 &aff_e1
, &data
->name_expansion_cache
);
4821 aff_combination_add (&aff_e1
, &aff_offset
);
4822 return aff_combination_zero_p (&aff_e1
);
4824 case POINTER_PLUS_EXPR
:
4825 aff_combination_add (&aff_e2
, &aff_offset
);
4826 return aff_combination_zero_p (&aff_e2
);
4833 /* Tries to replace loop exit by one formulated in terms of a LT_EXPR
4834 comparison with CAND. NITER describes the number of iterations of
4835 the loops. If successful, the comparison in COMP_P is altered accordingly.
4837 We aim to handle the following situation:
4853 Here, the number of iterations of the loop is (a + 1 > b) ? 0 : b - a - 1.
4854 We aim to optimize this to
4862 while (p < p_0 - a + b);
4864 This preserves the correctness, since the pointer arithmetics does not
4865 overflow. More precisely:
4867 1) if a + 1 <= b, then p_0 - a + b is the final value of p, hence there is no
4868 overflow in computing it or the values of p.
4869 2) if a + 1 > b, then we need to verify that the expression p_0 - a does not
4870 overflow. To prove this, we use the fact that p_0 = base + a. */
4873 iv_elimination_compare_lt (struct ivopts_data
*data
,
4874 struct iv_cand
*cand
, enum tree_code
*comp_p
,
4875 struct tree_niter_desc
*niter
)
4877 tree cand_type
, a
, b
, mbz
, nit_type
= TREE_TYPE (niter
->niter
), offset
;
4878 struct aff_tree nit
, tmpa
, tmpb
;
4879 enum tree_code comp
;
4882 /* We need to know that the candidate induction variable does not overflow.
4883 While more complex analysis may be used to prove this, for now just
4884 check that the variable appears in the original program and that it
4885 is computed in a type that guarantees no overflows. */
4886 cand_type
= TREE_TYPE (cand
->iv
->base
);
4887 if (cand
->pos
!= IP_ORIGINAL
|| !nowrap_type_p (cand_type
))
4890 /* Make sure that the loop iterates till the loop bound is hit, as otherwise
4891 the calculation of the BOUND could overflow, making the comparison
4893 if (!data
->loop_single_exit_p
)
4896 /* We need to be able to decide whether candidate is increasing or decreasing
4897 in order to choose the right comparison operator. */
4898 if (!cst_and_fits_in_hwi (cand
->iv
->step
))
4900 step
= int_cst_value (cand
->iv
->step
);
4902 /* Check that the number of iterations matches the expected pattern:
4903 a + 1 > b ? 0 : b - a - 1. */
4904 mbz
= niter
->may_be_zero
;
4905 if (TREE_CODE (mbz
) == GT_EXPR
)
4907 /* Handle a + 1 > b. */
4908 tree op0
= TREE_OPERAND (mbz
, 0);
4909 if (TREE_CODE (op0
) == PLUS_EXPR
&& integer_onep (TREE_OPERAND (op0
, 1)))
4911 a
= TREE_OPERAND (op0
, 0);
4912 b
= TREE_OPERAND (mbz
, 1);
4917 else if (TREE_CODE (mbz
) == LT_EXPR
)
4919 tree op1
= TREE_OPERAND (mbz
, 1);
4921 /* Handle b < a + 1. */
4922 if (TREE_CODE (op1
) == PLUS_EXPR
&& integer_onep (TREE_OPERAND (op1
, 1)))
4924 a
= TREE_OPERAND (op1
, 0);
4925 b
= TREE_OPERAND (mbz
, 0);
4933 /* Expected number of iterations is B - A - 1. Check that it matches
4934 the actual number, i.e., that B - A - NITER = 1. */
4935 tree_to_aff_combination (niter
->niter
, nit_type
, &nit
);
4936 tree_to_aff_combination (fold_convert (nit_type
, a
), nit_type
, &tmpa
);
4937 tree_to_aff_combination (fold_convert (nit_type
, b
), nit_type
, &tmpb
);
4938 aff_combination_scale (&nit
, -1);
4939 aff_combination_scale (&tmpa
, -1);
4940 aff_combination_add (&tmpb
, &tmpa
);
4941 aff_combination_add (&tmpb
, &nit
);
4942 if (tmpb
.n
!= 0 || tmpb
.offset
!= 1)
4945 /* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not
4947 offset
= fold_build2 (MULT_EXPR
, TREE_TYPE (cand
->iv
->step
),
4949 fold_convert (TREE_TYPE (cand
->iv
->step
), a
));
4950 if (!difference_cannot_overflow_p (data
, cand
->iv
->base
, offset
))
4953 /* Determine the new comparison operator. */
4954 comp
= step
< 0 ? GT_EXPR
: LT_EXPR
;
4955 if (*comp_p
== NE_EXPR
)
4957 else if (*comp_p
== EQ_EXPR
)
4958 *comp_p
= invert_tree_comparison (comp
, false);
4965 /* Check whether it is possible to express the condition in USE by comparison
4966 of candidate CAND. If so, store the value compared with to BOUND, and the
4967 comparison operator to COMP. */
4970 may_eliminate_iv (struct ivopts_data
*data
,
4971 struct iv_use
*use
, struct iv_cand
*cand
, tree
*bound
,
4972 enum tree_code
*comp
)
4977 struct loop
*loop
= data
->current_loop
;
4979 struct tree_niter_desc
*desc
= NULL
;
4981 if (TREE_CODE (cand
->iv
->step
) != INTEGER_CST
)
4984 /* For now works only for exits that dominate the loop latch.
4985 TODO: extend to other conditions inside loop body. */
4986 ex_bb
= gimple_bb (use
->stmt
);
4987 if (use
->stmt
!= last_stmt (ex_bb
)
4988 || gimple_code (use
->stmt
) != GIMPLE_COND
4989 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, ex_bb
))
4992 exit
= EDGE_SUCC (ex_bb
, 0);
4993 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
4994 exit
= EDGE_SUCC (ex_bb
, 1);
4995 if (flow_bb_inside_loop_p (loop
, exit
->dest
))
4998 desc
= niter_for_exit (data
, exit
);
5002 /* Determine whether we can use the variable to test the exit condition.
5003 This is the case iff the period of the induction variable is greater
5004 than the number of iterations for which the exit condition is true. */
5005 period
= iv_period (cand
->iv
);
5007 /* If the number of iterations is constant, compare against it directly. */
5008 if (TREE_CODE (desc
->niter
) == INTEGER_CST
)
5010 /* See cand_value_at. */
5011 if (stmt_after_increment (loop
, cand
, use
->stmt
))
5013 if (!tree_int_cst_lt (desc
->niter
, period
))
5018 if (tree_int_cst_lt (period
, desc
->niter
))
5023 /* If not, and if this is the only possible exit of the loop, see whether
5024 we can get a conservative estimate on the number of iterations of the
5025 entire loop and compare against that instead. */
5028 widest_int period_value
, max_niter
;
5030 max_niter
= desc
->max
;
5031 if (stmt_after_increment (loop
, cand
, use
->stmt
))
5033 period_value
= wi::to_widest (period
);
5034 if (wi::gtu_p (max_niter
, period_value
))
5036 /* See if we can take advantage of inferred loop bound
5038 if (data
->loop_single_exit_p
)
5040 if (!max_loop_iterations (loop
, &max_niter
))
5042 /* The loop bound is already adjusted by adding 1. */
5043 if (wi::gtu_p (max_niter
, period_value
))
5051 cand_value_at (loop
, cand
, use
->stmt
, desc
->niter
, &bnd
);
5053 *bound
= fold_convert (TREE_TYPE (cand
->iv
->base
),
5054 aff_combination_to_tree (&bnd
));
5055 *comp
= iv_elimination_compare (data
, use
);
5057 /* It is unlikely that computing the number of iterations using division
5058 would be more profitable than keeping the original induction variable. */
5059 if (expression_expensive_p (*bound
))
5062 /* Sometimes, it is possible to handle the situation that the number of
5063 iterations may be zero unless additional assumptions by using <
5064 instead of != in the exit condition.
5066 TODO: we could also calculate the value MAY_BE_ZERO ? 0 : NITER and
5067 base the exit condition on it. However, that is often too
5069 if (!integer_zerop (desc
->may_be_zero
))
5070 return iv_elimination_compare_lt (data
, cand
, comp
, desc
);
5075 /* Calculates the cost of BOUND, if it is a PARM_DECL. A PARM_DECL must
5076 be copied, if it is used in the loop body and DATA->body_includes_call. */
5079 parm_decl_cost (struct ivopts_data
*data
, tree bound
)
5081 tree sbound
= bound
;
5082 STRIP_NOPS (sbound
);
5084 if (TREE_CODE (sbound
) == SSA_NAME
5085 && SSA_NAME_IS_DEFAULT_DEF (sbound
)
5086 && TREE_CODE (SSA_NAME_VAR (sbound
)) == PARM_DECL
5087 && data
->body_includes_call
)
5088 return COSTS_N_INSNS (1);
5093 /* Determines cost of computing the use in GROUP with CAND in a condition. */
5096 determine_group_iv_cost_cond (struct ivopts_data
*data
,
5097 struct iv_group
*group
, struct iv_cand
*cand
)
5099 tree bound
= NULL_TREE
;
5101 bitmap inv_exprs
= NULL
;
5102 bitmap inv_vars_elim
= NULL
, inv_vars_express
= NULL
, inv_vars
;
5103 comp_cost elim_cost
= infinite_cost
, express_cost
, cost
, bound_cost
;
5104 enum comp_iv_rewrite rewrite_type
;
5105 iv_inv_expr_ent
*inv_expr_elim
= NULL
, *inv_expr_express
= NULL
, *inv_expr
;
5106 tree
*control_var
, *bound_cst
;
5107 enum tree_code comp
= ERROR_MARK
;
5108 struct iv_use
*use
= group
->vuses
[0];
5110 /* Extract condition operands. */
5111 rewrite_type
= extract_cond_operands (data
, use
->stmt
, &control_var
,
5112 &bound_cst
, NULL
, &cmp_iv
);
5113 gcc_assert (rewrite_type
!= COMP_IV_NA
);
5115 /* Try iv elimination. */
5116 if (rewrite_type
== COMP_IV_ELIM
5117 && may_eliminate_iv (data
, use
, cand
, &bound
, &comp
))
5119 elim_cost
= force_var_cost (data
, bound
, &inv_vars_elim
);
5120 if (elim_cost
.cost
== 0)
5121 elim_cost
.cost
= parm_decl_cost (data
, bound
);
5122 else if (TREE_CODE (bound
) == INTEGER_CST
)
5124 /* If we replace a loop condition 'i < n' with 'p < base + n',
5125 inv_vars_elim will have 'base' and 'n' set, which implies that both
5126 'base' and 'n' will be live during the loop. More likely,
5127 'base + n' will be loop invariant, resulting in only one live value
5128 during the loop. So in that case we clear inv_vars_elim and set
5129 inv_expr_elim instead. */
5130 if (inv_vars_elim
&& bitmap_count_bits (inv_vars_elim
) > 1)
5132 inv_expr_elim
= get_loop_invariant_expr (data
, bound
);
5133 bitmap_clear (inv_vars_elim
);
5135 /* The bound is a loop invariant, so it will be only computed
5137 elim_cost
.cost
= adjust_setup_cost (data
, elim_cost
.cost
);
5140 /* When the condition is a comparison of the candidate IV against
5141 zero, prefer this IV.
5143 TODO: The constant that we're subtracting from the cost should
5144 be target-dependent. This information should be added to the
5145 target costs for each backend. */
5146 if (!elim_cost
.infinite_cost_p () /* Do not try to decrease infinite! */
5147 && integer_zerop (*bound_cst
)
5148 && (operand_equal_p (*control_var
, cand
->var_after
, 0)
5149 || operand_equal_p (*control_var
, cand
->var_before
, 0)))
5152 express_cost
= get_computation_cost (data
, use
, cand
, false,
5153 &inv_vars_express
, NULL
,
5156 find_inv_vars (data
, &cmp_iv
->base
, &inv_vars_express
);
5158 /* Count the cost of the original bound as well. */
5159 bound_cost
= force_var_cost (data
, *bound_cst
, NULL
);
5160 if (bound_cost
.cost
== 0)
5161 bound_cost
.cost
= parm_decl_cost (data
, *bound_cst
);
5162 else if (TREE_CODE (*bound_cst
) == INTEGER_CST
)
5163 bound_cost
.cost
= 0;
5164 express_cost
+= bound_cost
;
5166 /* Choose the better approach, preferring the eliminated IV. */
5167 if (elim_cost
<= express_cost
)
5170 inv_vars
= inv_vars_elim
;
5171 inv_vars_elim
= NULL
;
5172 inv_expr
= inv_expr_elim
;
5176 cost
= express_cost
;
5177 inv_vars
= inv_vars_express
;
5178 inv_vars_express
= NULL
;
5181 inv_expr
= inv_expr_express
;
5186 inv_exprs
= BITMAP_ALLOC (NULL
);
5187 bitmap_set_bit (inv_exprs
, inv_expr
->id
);
5189 set_group_iv_cost (data
, group
, cand
, cost
,
5190 inv_vars
, bound
, comp
, inv_exprs
);
5193 BITMAP_FREE (inv_vars_elim
);
5194 if (inv_vars_express
)
5195 BITMAP_FREE (inv_vars_express
);
5197 return !cost
.infinite_cost_p ();
5200 /* Determines cost of computing uses in GROUP with CAND. Returns false
5201 if USE cannot be represented with CAND. */
5204 determine_group_iv_cost (struct ivopts_data
*data
,
5205 struct iv_group
*group
, struct iv_cand
*cand
)
5207 switch (group
->type
)
5209 case USE_NONLINEAR_EXPR
:
5210 return determine_group_iv_cost_generic (data
, group
, cand
);
5213 return determine_group_iv_cost_address (data
, group
, cand
);
5216 return determine_group_iv_cost_cond (data
, group
, cand
);
5223 /* Return true if get_computation_cost indicates that autoincrement is
5224 a possibility for the pair of USE and CAND, false otherwise. */
5227 autoinc_possible_for_pair (struct ivopts_data
*data
, struct iv_use
*use
,
5228 struct iv_cand
*cand
)
5230 if (use
->type
!= USE_ADDRESS
)
5233 bool can_autoinc
= false;
5234 get_computation_cost (data
, use
, cand
, true, NULL
, &can_autoinc
, NULL
);
5238 /* Examine IP_ORIGINAL candidates to see if they are incremented next to a
5239 use that allows autoincrement, and set their AINC_USE if possible. */
5242 set_autoinc_for_original_candidates (struct ivopts_data
*data
)
5246 for (i
= 0; i
< data
->vcands
.length (); i
++)
5248 struct iv_cand
*cand
= data
->vcands
[i
];
5249 struct iv_use
*closest_before
= NULL
;
5250 struct iv_use
*closest_after
= NULL
;
5251 if (cand
->pos
!= IP_ORIGINAL
)
5254 for (j
= 0; j
< data
->vgroups
.length (); j
++)
5256 struct iv_group
*group
= data
->vgroups
[j
];
5257 struct iv_use
*use
= group
->vuses
[0];
5258 unsigned uid
= gimple_uid (use
->stmt
);
5260 if (gimple_bb (use
->stmt
) != gimple_bb (cand
->incremented_at
))
5263 if (uid
< gimple_uid (cand
->incremented_at
)
5264 && (closest_before
== NULL
5265 || uid
> gimple_uid (closest_before
->stmt
)))
5266 closest_before
= use
;
5268 if (uid
> gimple_uid (cand
->incremented_at
)
5269 && (closest_after
== NULL
5270 || uid
< gimple_uid (closest_after
->stmt
)))
5271 closest_after
= use
;
5274 if (closest_before
!= NULL
5275 && autoinc_possible_for_pair (data
, closest_before
, cand
))
5276 cand
->ainc_use
= closest_before
;
5277 else if (closest_after
!= NULL
5278 && autoinc_possible_for_pair (data
, closest_after
, cand
))
5279 cand
->ainc_use
= closest_after
;
5283 /* Relate compare use with all candidates. */
5286 relate_compare_use_with_all_cands (struct ivopts_data
*data
)
5288 unsigned i
, max_id
= data
->vcands
.length () - 1;
5289 for (i
= 0; i
< data
->vgroups
.length (); i
++)
5291 struct iv_group
*group
= data
->vgroups
[i
];
5293 if (group
->type
== USE_COMPARE
)
5294 bitmap_set_range (group
->related_cands
, 0, max_id
);
5298 /* Finds the candidates for the induction variables. */
5301 find_iv_candidates (struct ivopts_data
*data
)
5303 /* Add commonly used ivs. */
5304 add_standard_iv_candidates (data
);
5306 /* Add old induction variables. */
5307 add_iv_candidate_for_bivs (data
);
5309 /* Add induction variables derived from uses. */
5310 add_iv_candidate_for_groups (data
);
5312 set_autoinc_for_original_candidates (data
);
5314 /* Record the important candidates. */
5315 record_important_candidates (data
);
5317 /* Relate compare iv_use with all candidates. */
5318 if (!data
->consider_all_candidates
)
5319 relate_compare_use_with_all_cands (data
);
5321 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5325 fprintf (dump_file
, "\n<Important Candidates>:\t");
5326 for (i
= 0; i
< data
->vcands
.length (); i
++)
5327 if (data
->vcands
[i
]->important
)
5328 fprintf (dump_file
, " %d,", data
->vcands
[i
]->id
);
5329 fprintf (dump_file
, "\n");
5331 fprintf (dump_file
, "\n<Group, Cand> Related:\n");
5332 for (i
= 0; i
< data
->vgroups
.length (); i
++)
5334 struct iv_group
*group
= data
->vgroups
[i
];
5336 if (group
->related_cands
)
5338 fprintf (dump_file
, " Group %d:\t", group
->id
);
5339 dump_bitmap (dump_file
, group
->related_cands
);
5342 fprintf (dump_file
, "\n");
5346 /* Determines costs of computing use of iv with an iv candidate. */
5349 determine_group_iv_costs (struct ivopts_data
*data
)
5352 struct iv_cand
*cand
;
5353 struct iv_group
*group
;
5354 bitmap to_clear
= BITMAP_ALLOC (NULL
);
5356 alloc_use_cost_map (data
);
5358 for (i
= 0; i
< data
->vgroups
.length (); i
++)
5360 group
= data
->vgroups
[i
];
5362 if (data
->consider_all_candidates
)
5364 for (j
= 0; j
< data
->vcands
.length (); j
++)
5366 cand
= data
->vcands
[j
];
5367 determine_group_iv_cost (data
, group
, cand
);
5374 EXECUTE_IF_SET_IN_BITMAP (group
->related_cands
, 0, j
, bi
)
5376 cand
= data
->vcands
[j
];
5377 if (!determine_group_iv_cost (data
, group
, cand
))
5378 bitmap_set_bit (to_clear
, j
);
5381 /* Remove the candidates for that the cost is infinite from
5382 the list of related candidates. */
5383 bitmap_and_compl_into (group
->related_cands
, to_clear
);
5384 bitmap_clear (to_clear
);
5388 BITMAP_FREE (to_clear
);
5390 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5392 fprintf (dump_file
, "\n<Invariant Expressions>:\n");
5393 auto_vec
<iv_inv_expr_ent
*> list (data
->inv_expr_tab
->elements ());
5395 for (hash_table
<iv_inv_expr_hasher
>::iterator it
5396 = data
->inv_expr_tab
->begin (); it
!= data
->inv_expr_tab
->end ();
5398 list
.safe_push (*it
);
5400 list
.qsort (sort_iv_inv_expr_ent
);
5402 for (i
= 0; i
< list
.length (); ++i
)
5404 fprintf (dump_file
, "inv_expr %d: \t", list
[i
]->id
);
5405 print_generic_expr (dump_file
, list
[i
]->expr
, TDF_SLIM
);
5406 fprintf (dump_file
, "\n");
5409 fprintf (dump_file
, "\n<Group-candidate Costs>:\n");
5411 for (i
= 0; i
< data
->vgroups
.length (); i
++)
5413 group
= data
->vgroups
[i
];
5415 fprintf (dump_file
, "Group %d:\n", i
);
5416 fprintf (dump_file
, " cand\tcost\tcompl.\tinv.expr.\tinv.vars\n");
5417 for (j
= 0; j
< group
->n_map_members
; j
++)
5419 if (!group
->cost_map
[j
].cand
5420 || group
->cost_map
[j
].cost
.infinite_cost_p ())
5423 fprintf (dump_file
, " %d\t%d\t%d\t",
5424 group
->cost_map
[j
].cand
->id
,
5425 group
->cost_map
[j
].cost
.cost
,
5426 group
->cost_map
[j
].cost
.complexity
);
5427 if (!group
->cost_map
[j
].inv_exprs
5428 || bitmap_empty_p (group
->cost_map
[j
].inv_exprs
))
5429 fprintf (dump_file
, "NIL;\t");
5431 bitmap_print (dump_file
,
5432 group
->cost_map
[j
].inv_exprs
, "", ";\t");
5433 if (!group
->cost_map
[j
].inv_vars
5434 || bitmap_empty_p (group
->cost_map
[j
].inv_vars
))
5435 fprintf (dump_file
, "NIL;\n");
5437 bitmap_print (dump_file
,
5438 group
->cost_map
[j
].inv_vars
, "", "\n");
5441 fprintf (dump_file
, "\n");
5443 fprintf (dump_file
, "\n");
5447 /* Determines cost of the candidate CAND. */
5450 determine_iv_cost (struct ivopts_data
*data
, struct iv_cand
*cand
)
5452 comp_cost cost_base
;
5453 unsigned cost
, cost_step
;
5456 gcc_assert (cand
->iv
!= NULL
);
5458 /* There are two costs associated with the candidate -- its increment
5459 and its initialization. The second is almost negligible for any loop
5460 that rolls enough, so we take it just very little into account. */
5462 base
= cand
->iv
->base
;
5463 cost_base
= force_var_cost (data
, base
, NULL
);
5464 /* It will be exceptional that the iv register happens to be initialized with
5465 the proper value at no cost. In general, there will at least be a regcopy
5467 if (cost_base
.cost
== 0)
5468 cost_base
.cost
= COSTS_N_INSNS (1);
5469 cost_step
= add_cost (data
->speed
, TYPE_MODE (TREE_TYPE (base
)));
5471 cost
= cost_step
+ adjust_setup_cost (data
, cost_base
.cost
);
5473 /* Prefer the original ivs unless we may gain something by replacing it.
5474 The reason is to make debugging simpler; so this is not relevant for
5475 artificial ivs created by other optimization passes. */
5476 if (cand
->pos
!= IP_ORIGINAL
5477 || !SSA_NAME_VAR (cand
->var_before
)
5478 || DECL_ARTIFICIAL (SSA_NAME_VAR (cand
->var_before
)))
5481 /* Prefer not to insert statements into latch unless there are some
5482 already (so that we do not create unnecessary jumps). */
5483 if (cand
->pos
== IP_END
5484 && empty_block_p (ip_end_pos (data
->current_loop
)))
5488 cand
->cost_step
= cost_step
;
5491 /* Determines costs of computation of the candidates. */
5494 determine_iv_costs (struct ivopts_data
*data
)
5498 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5500 fprintf (dump_file
, "<Candidate Costs>:\n");
5501 fprintf (dump_file
, " cand\tcost\n");
5504 for (i
= 0; i
< data
->vcands
.length (); i
++)
5506 struct iv_cand
*cand
= data
->vcands
[i
];
5508 determine_iv_cost (data
, cand
);
5510 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5511 fprintf (dump_file
, " %d\t%d\n", i
, cand
->cost
);
5514 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5515 fprintf (dump_file
, "\n");
5518 /* Calculates cost for having N_REGS registers. This number includes
5519 induction variables, invariant variables and invariant expressions. */
5522 ivopts_global_cost_for_size (struct ivopts_data
*data
, unsigned n_regs
)
5524 unsigned cost
= estimate_reg_pressure_cost (n_regs
,
5525 data
->regs_used
, data
->speed
,
5526 data
->body_includes_call
);
5527 /* Add n_regs to the cost, so that we prefer eliminating ivs if possible. */
5528 return n_regs
+ cost
;
5531 /* For each size of the induction variable set determine the penalty. */
5534 determine_set_costs (struct ivopts_data
*data
)
5540 struct loop
*loop
= data
->current_loop
;
5543 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5545 fprintf (dump_file
, "<Global Costs>:\n");
5546 fprintf (dump_file
, " target_avail_regs %d\n", target_avail_regs
);
5547 fprintf (dump_file
, " target_clobbered_regs %d\n", target_clobbered_regs
);
5548 fprintf (dump_file
, " target_reg_cost %d\n", target_reg_cost
[data
->speed
]);
5549 fprintf (dump_file
, " target_spill_cost %d\n", target_spill_cost
[data
->speed
]);
5553 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
5556 op
= PHI_RESULT (phi
);
5558 if (virtual_operand_p (op
))
5561 if (get_iv (data
, op
))
5567 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
5569 struct version_info
*info
= ver_info (data
, j
);
5571 if (info
->inv_id
&& info
->has_nonlin_use
)
5575 data
->regs_used
= n
;
5576 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5577 fprintf (dump_file
, " regs_used %d\n", n
);
5579 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5581 fprintf (dump_file
, " cost for size:\n");
5582 fprintf (dump_file
, " ivs\tcost\n");
5583 for (j
= 0; j
<= 2 * target_avail_regs
; j
++)
5584 fprintf (dump_file
, " %d\t%d\n", j
,
5585 ivopts_global_cost_for_size (data
, j
));
5586 fprintf (dump_file
, "\n");
5590 /* Returns true if A is a cheaper cost pair than B. */
5593 cheaper_cost_pair (struct cost_pair
*a
, struct cost_pair
*b
)
5601 if (a
->cost
< b
->cost
)
5604 if (b
->cost
< a
->cost
)
5607 /* In case the costs are the same, prefer the cheaper candidate. */
5608 if (a
->cand
->cost
< b
->cand
->cost
)
5615 /* Returns candidate by that USE is expressed in IVS. */
5617 static struct cost_pair
*
5618 iv_ca_cand_for_group (struct iv_ca
*ivs
, struct iv_group
*group
)
5620 return ivs
->cand_for_group
[group
->id
];
5623 /* Computes the cost field of IVS structure. */
5626 iv_ca_recount_cost (struct ivopts_data
*data
, struct iv_ca
*ivs
)
5628 comp_cost cost
= ivs
->cand_use_cost
;
5630 cost
+= ivs
->cand_cost
;
5631 cost
+= ivopts_global_cost_for_size (data
, ivs
->n_invs
+ ivs
->n_cands
);
5635 /* Remove use of invariants in set INVS by decreasing counter in N_INV_USES
5639 iv_ca_set_remove_invs (struct iv_ca
*ivs
, bitmap invs
, unsigned *n_inv_uses
)
5647 gcc_assert (n_inv_uses
!= NULL
);
5648 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
5651 if (n_inv_uses
[iid
] == 0)
5656 /* Set USE not to be expressed by any candidate in IVS. */
5659 iv_ca_set_no_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5660 struct iv_group
*group
)
5662 unsigned gid
= group
->id
, cid
;
5663 struct cost_pair
*cp
;
5665 cp
= ivs
->cand_for_group
[gid
];
5671 ivs
->cand_for_group
[gid
] = NULL
;
5672 ivs
->n_cand_uses
[cid
]--;
5674 if (ivs
->n_cand_uses
[cid
] == 0)
5676 bitmap_clear_bit (ivs
->cands
, cid
);
5678 ivs
->cand_cost
-= cp
->cand
->cost
;
5679 iv_ca_set_remove_invs (ivs
, cp
->cand
->inv_vars
, ivs
->n_inv_var_uses
);
5680 iv_ca_set_remove_invs (ivs
, cp
->cand
->inv_exprs
, ivs
->n_inv_expr_uses
);
5683 ivs
->cand_use_cost
-= cp
->cost
;
5684 iv_ca_set_remove_invs (ivs
, cp
->inv_vars
, ivs
->n_inv_var_uses
);
5685 iv_ca_set_remove_invs (ivs
, cp
->inv_exprs
, ivs
->n_inv_expr_uses
);
5686 iv_ca_recount_cost (data
, ivs
);
5689 /* Add use of invariants in set INVS by increasing counter in N_INV_USES and
5693 iv_ca_set_add_invs (struct iv_ca
*ivs
, bitmap invs
, unsigned *n_inv_uses
)
5701 gcc_assert (n_inv_uses
!= NULL
);
5702 EXECUTE_IF_SET_IN_BITMAP (invs
, 0, iid
, bi
)
5705 if (n_inv_uses
[iid
] == 1)
5710 /* Set cost pair for GROUP in set IVS to CP. */
5713 iv_ca_set_cp (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5714 struct iv_group
*group
, struct cost_pair
*cp
)
5716 unsigned gid
= group
->id
, cid
;
5718 if (ivs
->cand_for_group
[gid
] == cp
)
5721 if (ivs
->cand_for_group
[gid
])
5722 iv_ca_set_no_cp (data
, ivs
, group
);
5729 ivs
->cand_for_group
[gid
] = cp
;
5730 ivs
->n_cand_uses
[cid
]++;
5731 if (ivs
->n_cand_uses
[cid
] == 1)
5733 bitmap_set_bit (ivs
->cands
, cid
);
5735 ivs
->cand_cost
+= cp
->cand
->cost
;
5736 iv_ca_set_add_invs (ivs
, cp
->cand
->inv_vars
, ivs
->n_inv_var_uses
);
5737 iv_ca_set_add_invs (ivs
, cp
->cand
->inv_exprs
, ivs
->n_inv_expr_uses
);
5740 ivs
->cand_use_cost
+= cp
->cost
;
5741 iv_ca_set_add_invs (ivs
, cp
->inv_vars
, ivs
->n_inv_var_uses
);
5742 iv_ca_set_add_invs (ivs
, cp
->inv_exprs
, ivs
->n_inv_expr_uses
);
5743 iv_ca_recount_cost (data
, ivs
);
5747 /* Extend set IVS by expressing USE by some of the candidates in it
5748 if possible. Consider all important candidates if candidates in
5749 set IVS don't give any result. */
5752 iv_ca_add_group (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5753 struct iv_group
*group
)
5755 struct cost_pair
*best_cp
= NULL
, *cp
;
5758 struct iv_cand
*cand
;
5760 gcc_assert (ivs
->upto
>= group
->id
);
5764 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
5766 cand
= data
->vcands
[i
];
5767 cp
= get_group_iv_cost (data
, group
, cand
);
5768 if (cheaper_cost_pair (cp
, best_cp
))
5772 if (best_cp
== NULL
)
5774 EXECUTE_IF_SET_IN_BITMAP (data
->important_candidates
, 0, i
, bi
)
5776 cand
= data
->vcands
[i
];
5777 cp
= get_group_iv_cost (data
, group
, cand
);
5778 if (cheaper_cost_pair (cp
, best_cp
))
5783 iv_ca_set_cp (data
, ivs
, group
, best_cp
);
5786 /* Get cost for assignment IVS. */
5789 iv_ca_cost (struct iv_ca
*ivs
)
5791 /* This was a conditional expression but it triggered a bug in
5793 if (ivs
->bad_groups
)
5794 return infinite_cost
;
5799 /* Returns true if applying NEW_CP to GROUP for IVS introduces more
5800 invariants than OLD_CP. */
5803 iv_ca_more_deps (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5804 struct iv_group
*group
, struct cost_pair
*old_cp
,
5805 struct cost_pair
*new_cp
)
5807 gcc_assert (old_cp
&& new_cp
&& old_cp
!= new_cp
);
5808 unsigned old_n_invs
= ivs
->n_invs
;
5809 iv_ca_set_cp (data
, ivs
, group
, new_cp
);
5810 unsigned new_n_invs
= ivs
->n_invs
;
5811 iv_ca_set_cp (data
, ivs
, group
, old_cp
);
5813 return (new_n_invs
> old_n_invs
);
5816 /* Creates change of expressing GROUP by NEW_CP instead of OLD_CP and chains
5819 static struct iv_ca_delta
*
5820 iv_ca_delta_add (struct iv_group
*group
, struct cost_pair
*old_cp
,
5821 struct cost_pair
*new_cp
, struct iv_ca_delta
*next
)
5823 struct iv_ca_delta
*change
= XNEW (struct iv_ca_delta
);
5825 change
->group
= group
;
5826 change
->old_cp
= old_cp
;
5827 change
->new_cp
= new_cp
;
5828 change
->next
= next
;
5833 /* Joins two lists of changes L1 and L2. Destructive -- old lists
5836 static struct iv_ca_delta
*
5837 iv_ca_delta_join (struct iv_ca_delta
*l1
, struct iv_ca_delta
*l2
)
5839 struct iv_ca_delta
*last
;
5847 for (last
= l1
; last
->next
; last
= last
->next
)
5854 /* Reverse the list of changes DELTA, forming the inverse to it. */
5856 static struct iv_ca_delta
*
5857 iv_ca_delta_reverse (struct iv_ca_delta
*delta
)
5859 struct iv_ca_delta
*act
, *next
, *prev
= NULL
;
5861 for (act
= delta
; act
; act
= next
)
5867 std::swap (act
->old_cp
, act
->new_cp
);
5873 /* Commit changes in DELTA to IVS. If FORWARD is false, the changes are
5874 reverted instead. */
5877 iv_ca_delta_commit (struct ivopts_data
*data
, struct iv_ca
*ivs
,
5878 struct iv_ca_delta
*delta
, bool forward
)
5880 struct cost_pair
*from
, *to
;
5881 struct iv_ca_delta
*act
;
5884 delta
= iv_ca_delta_reverse (delta
);
5886 for (act
= delta
; act
; act
= act
->next
)
5890 gcc_assert (iv_ca_cand_for_group (ivs
, act
->group
) == from
);
5891 iv_ca_set_cp (data
, ivs
, act
->group
, to
);
5895 iv_ca_delta_reverse (delta
);
5898 /* Returns true if CAND is used in IVS. */
5901 iv_ca_cand_used_p (struct iv_ca
*ivs
, struct iv_cand
*cand
)
5903 return ivs
->n_cand_uses
[cand
->id
] > 0;
5906 /* Returns number of induction variable candidates in the set IVS. */
5909 iv_ca_n_cands (struct iv_ca
*ivs
)
5911 return ivs
->n_cands
;
5914 /* Free the list of changes DELTA. */
5917 iv_ca_delta_free (struct iv_ca_delta
**delta
)
5919 struct iv_ca_delta
*act
, *next
;
5921 for (act
= *delta
; act
; act
= next
)
5930 /* Allocates new iv candidates assignment. */
5932 static struct iv_ca
*
5933 iv_ca_new (struct ivopts_data
*data
)
5935 struct iv_ca
*nw
= XNEW (struct iv_ca
);
5939 nw
->cand_for_group
= XCNEWVEC (struct cost_pair
*,
5940 data
->vgroups
.length ());
5941 nw
->n_cand_uses
= XCNEWVEC (unsigned, data
->vcands
.length ());
5942 nw
->cands
= BITMAP_ALLOC (NULL
);
5945 nw
->cand_use_cost
= no_cost
;
5947 nw
->n_inv_var_uses
= XCNEWVEC (unsigned, data
->max_inv_var_id
+ 1);
5948 nw
->n_inv_expr_uses
= XCNEWVEC (unsigned, data
->max_inv_expr_id
+ 1);
5954 /* Free memory occupied by the set IVS. */
5957 iv_ca_free (struct iv_ca
**ivs
)
5959 free ((*ivs
)->cand_for_group
);
5960 free ((*ivs
)->n_cand_uses
);
5961 BITMAP_FREE ((*ivs
)->cands
);
5962 free ((*ivs
)->n_inv_var_uses
);
5963 free ((*ivs
)->n_inv_expr_uses
);
5968 /* Dumps IVS to FILE. */
5971 iv_ca_dump (struct ivopts_data
*data
, FILE *file
, struct iv_ca
*ivs
)
5974 comp_cost cost
= iv_ca_cost (ivs
);
5976 fprintf (file
, " cost: %d (complexity %d)\n", cost
.cost
,
5978 fprintf (file
, " cand_cost: %d\n cand_group_cost: %d (complexity %d)\n",
5979 ivs
->cand_cost
, ivs
->cand_use_cost
.cost
,
5980 ivs
->cand_use_cost
.complexity
);
5981 bitmap_print (file
, ivs
->cands
, " candidates: ","\n");
5983 for (i
= 0; i
< ivs
->upto
; i
++)
5985 struct iv_group
*group
= data
->vgroups
[i
];
5986 struct cost_pair
*cp
= iv_ca_cand_for_group (ivs
, group
);
5988 fprintf (file
, " group:%d --> iv_cand:%d, cost=(%d,%d)\n",
5989 group
->id
, cp
->cand
->id
, cp
->cost
.cost
,
5990 cp
->cost
.complexity
);
5992 fprintf (file
, " group:%d --> ??\n", group
->id
);
5995 const char *pref
= "";
5996 fprintf (file
, " invariant variables: ");
5997 for (i
= 1; i
<= data
->max_inv_var_id
; i
++)
5998 if (ivs
->n_inv_var_uses
[i
])
6000 fprintf (file
, "%s%d", pref
, i
);
6005 fprintf (file
, "\n invariant expressions: ");
6006 for (i
= 1; i
<= data
->max_inv_expr_id
; i
++)
6007 if (ivs
->n_inv_expr_uses
[i
])
6009 fprintf (file
, "%s%d", pref
, i
);
6013 fprintf (file
, "\n\n");
6016 /* Try changing candidate in IVS to CAND for each use. Return cost of the
6017 new set, and store differences in DELTA. Number of induction variables
6018 in the new set is stored to N_IVS. MIN_NCAND is a flag. When it is true
6019 the function will try to find a solution with mimimal iv candidates. */
6022 iv_ca_extend (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6023 struct iv_cand
*cand
, struct iv_ca_delta
**delta
,
6024 unsigned *n_ivs
, bool min_ncand
)
6028 struct iv_group
*group
;
6029 struct cost_pair
*old_cp
, *new_cp
;
6032 for (i
= 0; i
< ivs
->upto
; i
++)
6034 group
= data
->vgroups
[i
];
6035 old_cp
= iv_ca_cand_for_group (ivs
, group
);
6038 && old_cp
->cand
== cand
)
6041 new_cp
= get_group_iv_cost (data
, group
, cand
);
6045 if (!min_ncand
&& iv_ca_more_deps (data
, ivs
, group
, old_cp
, new_cp
))
6048 if (!min_ncand
&& !cheaper_cost_pair (new_cp
, old_cp
))
6051 *delta
= iv_ca_delta_add (group
, old_cp
, new_cp
, *delta
);
6054 iv_ca_delta_commit (data
, ivs
, *delta
, true);
6055 cost
= iv_ca_cost (ivs
);
6057 *n_ivs
= iv_ca_n_cands (ivs
);
6058 iv_ca_delta_commit (data
, ivs
, *delta
, false);
6063 /* Try narrowing set IVS by removing CAND. Return the cost of
6064 the new set and store the differences in DELTA. START is
6065 the candidate with which we start narrowing. */
6068 iv_ca_narrow (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6069 struct iv_cand
*cand
, struct iv_cand
*start
,
6070 struct iv_ca_delta
**delta
)
6073 struct iv_group
*group
;
6074 struct cost_pair
*old_cp
, *new_cp
, *cp
;
6076 struct iv_cand
*cnd
;
6077 comp_cost cost
, best_cost
, acost
;
6080 for (i
= 0; i
< data
->vgroups
.length (); i
++)
6082 group
= data
->vgroups
[i
];
6084 old_cp
= iv_ca_cand_for_group (ivs
, group
);
6085 if (old_cp
->cand
!= cand
)
6088 best_cost
= iv_ca_cost (ivs
);
6089 /* Start narrowing with START. */
6090 new_cp
= get_group_iv_cost (data
, group
, start
);
6092 if (data
->consider_all_candidates
)
6094 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, ci
, bi
)
6096 if (ci
== cand
->id
|| (start
&& ci
== start
->id
))
6099 cnd
= data
->vcands
[ci
];
6101 cp
= get_group_iv_cost (data
, group
, cnd
);
6105 iv_ca_set_cp (data
, ivs
, group
, cp
);
6106 acost
= iv_ca_cost (ivs
);
6108 if (acost
< best_cost
)
6117 EXECUTE_IF_AND_IN_BITMAP (group
->related_cands
, ivs
->cands
, 0, ci
, bi
)
6119 if (ci
== cand
->id
|| (start
&& ci
== start
->id
))
6122 cnd
= data
->vcands
[ci
];
6124 cp
= get_group_iv_cost (data
, group
, cnd
);
6128 iv_ca_set_cp (data
, ivs
, group
, cp
);
6129 acost
= iv_ca_cost (ivs
);
6131 if (acost
< best_cost
)
6138 /* Restore to old cp for use. */
6139 iv_ca_set_cp (data
, ivs
, group
, old_cp
);
6143 iv_ca_delta_free (delta
);
6144 return infinite_cost
;
6147 *delta
= iv_ca_delta_add (group
, old_cp
, new_cp
, *delta
);
6150 iv_ca_delta_commit (data
, ivs
, *delta
, true);
6151 cost
= iv_ca_cost (ivs
);
6152 iv_ca_delta_commit (data
, ivs
, *delta
, false);
6157 /* Try optimizing the set of candidates IVS by removing candidates different
6158 from to EXCEPT_CAND from it. Return cost of the new set, and store
6159 differences in DELTA. */
6162 iv_ca_prune (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6163 struct iv_cand
*except_cand
, struct iv_ca_delta
**delta
)
6166 struct iv_ca_delta
*act_delta
, *best_delta
;
6168 comp_cost best_cost
, acost
;
6169 struct iv_cand
*cand
;
6172 best_cost
= iv_ca_cost (ivs
);
6174 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
6176 cand
= data
->vcands
[i
];
6178 if (cand
== except_cand
)
6181 acost
= iv_ca_narrow (data
, ivs
, cand
, except_cand
, &act_delta
);
6183 if (acost
< best_cost
)
6186 iv_ca_delta_free (&best_delta
);
6187 best_delta
= act_delta
;
6190 iv_ca_delta_free (&act_delta
);
6199 /* Recurse to possibly remove other unnecessary ivs. */
6200 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
6201 best_cost
= iv_ca_prune (data
, ivs
, except_cand
, delta
);
6202 iv_ca_delta_commit (data
, ivs
, best_delta
, false);
6203 *delta
= iv_ca_delta_join (best_delta
, *delta
);
6207 /* Check if CAND_IDX is a candidate other than OLD_CAND and has
6208 cheaper local cost for GROUP than BEST_CP. Return pointer to
6209 the corresponding cost_pair, otherwise just return BEST_CP. */
6211 static struct cost_pair
*
6212 cheaper_cost_with_cand (struct ivopts_data
*data
, struct iv_group
*group
,
6213 unsigned int cand_idx
, struct iv_cand
*old_cand
,
6214 struct cost_pair
*best_cp
)
6216 struct iv_cand
*cand
;
6217 struct cost_pair
*cp
;
6219 gcc_assert (old_cand
!= NULL
&& best_cp
!= NULL
);
6220 if (cand_idx
== old_cand
->id
)
6223 cand
= data
->vcands
[cand_idx
];
6224 cp
= get_group_iv_cost (data
, group
, cand
);
6225 if (cp
!= NULL
&& cheaper_cost_pair (cp
, best_cp
))
6231 /* Try breaking local optimal fixed-point for IVS by replacing candidates
6232 which are used by more than one iv uses. For each of those candidates,
6233 this function tries to represent iv uses under that candidate using
6234 other ones with lower local cost, then tries to prune the new set.
6235 If the new set has lower cost, It returns the new cost after recording
6236 candidate replacement in list DELTA. */
6239 iv_ca_replace (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6240 struct iv_ca_delta
**delta
)
6242 bitmap_iterator bi
, bj
;
6243 unsigned int i
, j
, k
;
6244 struct iv_cand
*cand
;
6245 comp_cost orig_cost
, acost
;
6246 struct iv_ca_delta
*act_delta
, *tmp_delta
;
6247 struct cost_pair
*old_cp
, *best_cp
= NULL
;
6250 orig_cost
= iv_ca_cost (ivs
);
6252 EXECUTE_IF_SET_IN_BITMAP (ivs
->cands
, 0, i
, bi
)
6254 if (ivs
->n_cand_uses
[i
] == 1
6255 || ivs
->n_cand_uses
[i
] > ALWAYS_PRUNE_CAND_SET_BOUND
)
6258 cand
= data
->vcands
[i
];
6261 /* Represent uses under current candidate using other ones with
6262 lower local cost. */
6263 for (j
= 0; j
< ivs
->upto
; j
++)
6265 struct iv_group
*group
= data
->vgroups
[j
];
6266 old_cp
= iv_ca_cand_for_group (ivs
, group
);
6268 if (old_cp
->cand
!= cand
)
6272 if (data
->consider_all_candidates
)
6273 for (k
= 0; k
< data
->vcands
.length (); k
++)
6274 best_cp
= cheaper_cost_with_cand (data
, group
, k
,
6275 old_cp
->cand
, best_cp
);
6277 EXECUTE_IF_SET_IN_BITMAP (group
->related_cands
, 0, k
, bj
)
6278 best_cp
= cheaper_cost_with_cand (data
, group
, k
,
6279 old_cp
->cand
, best_cp
);
6281 if (best_cp
== old_cp
)
6284 act_delta
= iv_ca_delta_add (group
, old_cp
, best_cp
, act_delta
);
6286 /* No need for further prune. */
6290 /* Prune the new candidate set. */
6291 iv_ca_delta_commit (data
, ivs
, act_delta
, true);
6292 acost
= iv_ca_prune (data
, ivs
, NULL
, &tmp_delta
);
6293 iv_ca_delta_commit (data
, ivs
, act_delta
, false);
6294 act_delta
= iv_ca_delta_join (act_delta
, tmp_delta
);
6296 if (acost
< orig_cost
)
6302 iv_ca_delta_free (&act_delta
);
6308 /* Tries to extend the sets IVS in the best possible way in order to
6309 express the GROUP. If ORIGINALP is true, prefer candidates from
6310 the original set of IVs, otherwise favor important candidates not
6311 based on any memory object. */
6314 try_add_cand_for (struct ivopts_data
*data
, struct iv_ca
*ivs
,
6315 struct iv_group
*group
, bool originalp
)
6317 comp_cost best_cost
, act_cost
;
6320 struct iv_cand
*cand
;
6321 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
;
6322 struct cost_pair
*cp
;
6324 iv_ca_add_group (data
, ivs
, group
);
6325 best_cost
= iv_ca_cost (ivs
);
6326 cp
= iv_ca_cand_for_group (ivs
, group
);
6329 best_delta
= iv_ca_delta_add (group
, NULL
, cp
, NULL
);
6330 iv_ca_set_no_cp (data
, ivs
, group
);
6333 /* If ORIGINALP is true, try to find the original IV for the use. Otherwise
6334 first try important candidates not based on any memory object. Only if
6335 this fails, try the specific ones. Rationale -- in loops with many
6336 variables the best choice often is to use just one generic biv. If we
6337 added here many ivs specific to the uses, the optimization algorithm later
6338 would be likely to get stuck in a local minimum, thus causing us to create
6339 too many ivs. The approach from few ivs to more seems more likely to be
6340 successful -- starting from few ivs, replacing an expensive use by a
6341 specific iv should always be a win. */
6342 EXECUTE_IF_SET_IN_BITMAP (group
->related_cands
, 0, i
, bi
)
6344 cand
= data
->vcands
[i
];
6346 if (originalp
&& cand
->pos
!=IP_ORIGINAL
)
6349 if (!originalp
&& cand
->iv
->base_object
!= NULL_TREE
)
6352 if (iv_ca_cand_used_p (ivs
, cand
))
6355 cp
= get_group_iv_cost (data
, group
, cand
);
6359 iv_ca_set_cp (data
, ivs
, group
, cp
);
6360 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
,
6362 iv_ca_set_no_cp (data
, ivs
, group
);
6363 act_delta
= iv_ca_delta_add (group
, NULL
, cp
, act_delta
);
6365 if (act_cost
< best_cost
)
6367 best_cost
= act_cost
;
6369 iv_ca_delta_free (&best_delta
);
6370 best_delta
= act_delta
;
6373 iv_ca_delta_free (&act_delta
);
6376 if (best_cost
.infinite_cost_p ())
6378 for (i
= 0; i
< group
->n_map_members
; i
++)
6380 cp
= group
->cost_map
+ i
;
6385 /* Already tried this. */
6386 if (cand
->important
)
6388 if (originalp
&& cand
->pos
== IP_ORIGINAL
)
6390 if (!originalp
&& cand
->iv
->base_object
== NULL_TREE
)
6394 if (iv_ca_cand_used_p (ivs
, cand
))
6398 iv_ca_set_cp (data
, ivs
, group
, cp
);
6399 act_cost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, NULL
, true);
6400 iv_ca_set_no_cp (data
, ivs
, group
);
6401 act_delta
= iv_ca_delta_add (group
,
6402 iv_ca_cand_for_group (ivs
, group
),
6405 if (act_cost
< best_cost
)
6407 best_cost
= act_cost
;
6410 iv_ca_delta_free (&best_delta
);
6411 best_delta
= act_delta
;
6414 iv_ca_delta_free (&act_delta
);
6418 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
6419 iv_ca_delta_free (&best_delta
);
6421 return !best_cost
.infinite_cost_p ();
6424 /* Finds an initial assignment of candidates to uses. */
6426 static struct iv_ca
*
6427 get_initial_solution (struct ivopts_data
*data
, bool originalp
)
6430 struct iv_ca
*ivs
= iv_ca_new (data
);
6432 for (i
= 0; i
< data
->vgroups
.length (); i
++)
6433 if (!try_add_cand_for (data
, ivs
, data
->vgroups
[i
], originalp
))
6442 /* Tries to improve set of induction variables IVS. TRY_REPLACE_P
6443 points to a bool variable, this function tries to break local
6444 optimal fixed-point by replacing candidates in IVS if it's true. */
6447 try_improve_iv_set (struct ivopts_data
*data
,
6448 struct iv_ca
*ivs
, bool *try_replace_p
)
6451 comp_cost acost
, best_cost
= iv_ca_cost (ivs
);
6452 struct iv_ca_delta
*best_delta
= NULL
, *act_delta
, *tmp_delta
;
6453 struct iv_cand
*cand
;
6455 /* Try extending the set of induction variables by one. */
6456 for (i
= 0; i
< data
->vcands
.length (); i
++)
6458 cand
= data
->vcands
[i
];
6460 if (iv_ca_cand_used_p (ivs
, cand
))
6463 acost
= iv_ca_extend (data
, ivs
, cand
, &act_delta
, &n_ivs
, false);
6467 /* If we successfully added the candidate and the set is small enough,
6468 try optimizing it by removing other candidates. */
6469 if (n_ivs
<= ALWAYS_PRUNE_CAND_SET_BOUND
)
6471 iv_ca_delta_commit (data
, ivs
, act_delta
, true);
6472 acost
= iv_ca_prune (data
, ivs
, cand
, &tmp_delta
);
6473 iv_ca_delta_commit (data
, ivs
, act_delta
, false);
6474 act_delta
= iv_ca_delta_join (act_delta
, tmp_delta
);
6477 if (acost
< best_cost
)
6480 iv_ca_delta_free (&best_delta
);
6481 best_delta
= act_delta
;
6484 iv_ca_delta_free (&act_delta
);
6489 /* Try removing the candidates from the set instead. */
6490 best_cost
= iv_ca_prune (data
, ivs
, NULL
, &best_delta
);
6492 if (!best_delta
&& *try_replace_p
)
6494 *try_replace_p
= false;
6495 /* So far candidate selecting algorithm tends to choose fewer IVs
6496 so that it can handle cases in which loops have many variables
6497 but the best choice is often to use only one general biv. One
6498 weakness is it can't handle opposite cases, in which different
6499 candidates should be chosen with respect to each use. To solve
6500 the problem, we replace candidates in a manner described by the
6501 comments of iv_ca_replace, thus give general algorithm a chance
6502 to break local optimal fixed-point in these cases. */
6503 best_cost
= iv_ca_replace (data
, ivs
, &best_delta
);
6510 iv_ca_delta_commit (data
, ivs
, best_delta
, true);
6511 gcc_assert (best_cost
== iv_ca_cost (ivs
));
6512 iv_ca_delta_free (&best_delta
);
6516 /* Attempts to find the optimal set of induction variables. We do simple
6517 greedy heuristic -- we try to replace at most one candidate in the selected
6518 solution and remove the unused ivs while this improves the cost. */
6520 static struct iv_ca
*
6521 find_optimal_iv_set_1 (struct ivopts_data
*data
, bool originalp
)
6524 bool try_replace_p
= true;
6526 /* Get the initial solution. */
6527 set
= get_initial_solution (data
, originalp
);
6530 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6531 fprintf (dump_file
, "Unable to substitute for ivs, failed.\n");
6535 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6537 fprintf (dump_file
, "Initial set of candidates:\n");
6538 iv_ca_dump (data
, dump_file
, set
);
6541 while (try_improve_iv_set (data
, set
, &try_replace_p
))
6543 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6545 fprintf (dump_file
, "Improved to:\n");
6546 iv_ca_dump (data
, dump_file
, set
);
6553 static struct iv_ca
*
6554 find_optimal_iv_set (struct ivopts_data
*data
)
6557 comp_cost cost
, origcost
;
6558 struct iv_ca
*set
, *origset
;
6560 /* Determine the cost based on a strategy that starts with original IVs,
6561 and try again using a strategy that prefers candidates not based
6563 origset
= find_optimal_iv_set_1 (data
, true);
6564 set
= find_optimal_iv_set_1 (data
, false);
6566 if (!origset
&& !set
)
6569 origcost
= origset
? iv_ca_cost (origset
) : infinite_cost
;
6570 cost
= set
? iv_ca_cost (set
) : infinite_cost
;
6572 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6574 fprintf (dump_file
, "Original cost %d (complexity %d)\n\n",
6575 origcost
.cost
, origcost
.complexity
);
6576 fprintf (dump_file
, "Final cost %d (complexity %d)\n\n",
6577 cost
.cost
, cost
.complexity
);
6580 /* Choose the one with the best cost. */
6581 if (origcost
<= cost
)
6588 iv_ca_free (&origset
);
6590 for (i
= 0; i
< data
->vgroups
.length (); i
++)
6592 struct iv_group
*group
= data
->vgroups
[i
];
6593 group
->selected
= iv_ca_cand_for_group (set
, group
)->cand
;
6599 /* Creates a new induction variable corresponding to CAND. */
6602 create_new_iv (struct ivopts_data
*data
, struct iv_cand
*cand
)
6604 gimple_stmt_iterator incr_pos
;
6607 struct iv_group
*group
;
6610 gcc_assert (cand
->iv
!= NULL
);
6615 incr_pos
= gsi_last_bb (ip_normal_pos (data
->current_loop
));
6619 incr_pos
= gsi_last_bb (ip_end_pos (data
->current_loop
));
6627 incr_pos
= gsi_for_stmt (cand
->incremented_at
);
6631 /* Mark that the iv is preserved. */
6632 name_info (data
, cand
->var_before
)->preserve_biv
= true;
6633 name_info (data
, cand
->var_after
)->preserve_biv
= true;
6635 /* Rewrite the increment so that it uses var_before directly. */
6636 use
= find_interesting_uses_op (data
, cand
->var_after
);
6637 group
= data
->vgroups
[use
->group_id
];
6638 group
->selected
= cand
;
6642 gimple_add_tmp_var (cand
->var_before
);
6644 base
= unshare_expr (cand
->iv
->base
);
6646 create_iv (base
, unshare_expr (cand
->iv
->step
),
6647 cand
->var_before
, data
->current_loop
,
6648 &incr_pos
, after
, &cand
->var_before
, &cand
->var_after
);
6651 /* Creates new induction variables described in SET. */
6654 create_new_ivs (struct ivopts_data
*data
, struct iv_ca
*set
)
6657 struct iv_cand
*cand
;
6660 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
6662 cand
= data
->vcands
[i
];
6663 create_new_iv (data
, cand
);
6666 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6668 fprintf (dump_file
, "Selected IV set for loop %d",
6669 data
->current_loop
->num
);
6670 if (data
->loop_loc
!= UNKNOWN_LOCATION
)
6671 fprintf (dump_file
, " at %s:%d", LOCATION_FILE (data
->loop_loc
),
6672 LOCATION_LINE (data
->loop_loc
));
6673 fprintf (dump_file
, ", " HOST_WIDE_INT_PRINT_DEC
" avg niters",
6674 avg_loop_niter (data
->current_loop
));
6675 fprintf (dump_file
, ", %lu IVs:\n", bitmap_count_bits (set
->cands
));
6676 EXECUTE_IF_SET_IN_BITMAP (set
->cands
, 0, i
, bi
)
6678 cand
= data
->vcands
[i
];
6679 dump_cand (dump_file
, cand
);
6681 fprintf (dump_file
, "\n");
6685 /* Rewrites USE (definition of iv used in a nonlinear expression)
6686 using candidate CAND. */
6689 rewrite_use_nonlinear_expr (struct ivopts_data
*data
,
6690 struct iv_use
*use
, struct iv_cand
*cand
)
6693 gimple_stmt_iterator bsi
;
6694 tree comp
, type
= get_use_type (use
), tgt
;
6696 /* An important special case -- if we are asked to express value of
6697 the original iv by itself, just exit; there is no need to
6698 introduce a new computation (that might also need casting the
6699 variable to unsigned and back). */
6700 if (cand
->pos
== IP_ORIGINAL
6701 && cand
->incremented_at
== use
->stmt
)
6703 tree op
= NULL_TREE
;
6704 enum tree_code stmt_code
;
6706 gcc_assert (is_gimple_assign (use
->stmt
));
6707 gcc_assert (gimple_assign_lhs (use
->stmt
) == cand
->var_after
);
6709 /* Check whether we may leave the computation unchanged.
6710 This is the case only if it does not rely on other
6711 computations in the loop -- otherwise, the computation
6712 we rely upon may be removed in remove_unused_ivs,
6713 thus leading to ICE. */
6714 stmt_code
= gimple_assign_rhs_code (use
->stmt
);
6715 if (stmt_code
== PLUS_EXPR
6716 || stmt_code
== MINUS_EXPR
6717 || stmt_code
== POINTER_PLUS_EXPR
)
6719 if (gimple_assign_rhs1 (use
->stmt
) == cand
->var_before
)
6720 op
= gimple_assign_rhs2 (use
->stmt
);
6721 else if (gimple_assign_rhs2 (use
->stmt
) == cand
->var_before
)
6722 op
= gimple_assign_rhs1 (use
->stmt
);
6725 if (op
!= NULL_TREE
)
6727 if (expr_invariant_in_loop_p (data
->current_loop
, op
))
6729 if (TREE_CODE (op
) == SSA_NAME
)
6731 struct iv
*iv
= get_iv (data
, op
);
6732 if (iv
!= NULL
&& integer_zerop (iv
->step
))
6738 switch (gimple_code (use
->stmt
))
6741 tgt
= PHI_RESULT (use
->stmt
);
6743 /* If we should keep the biv, do not replace it. */
6744 if (name_info (data
, tgt
)->preserve_biv
)
6747 bsi
= gsi_after_labels (gimple_bb (use
->stmt
));
6751 tgt
= gimple_assign_lhs (use
->stmt
);
6752 bsi
= gsi_for_stmt (use
->stmt
);
6759 aff_tree aff_inv
, aff_var
;
6760 if (!get_computation_aff_1 (data
->current_loop
, use
->stmt
,
6761 use
, cand
, &aff_inv
, &aff_var
))
6764 unshare_aff_combination (&aff_inv
);
6765 unshare_aff_combination (&aff_var
);
6766 /* Prefer CSE opportunity than loop invariant by adding offset at last
6767 so that iv_uses have different offsets can be CSEed. */
6768 widest_int offset
= aff_inv
.offset
;
6771 gimple_seq stmt_list
= NULL
, seq
= NULL
;
6772 tree comp_op1
= aff_combination_to_tree (&aff_inv
);
6773 tree comp_op2
= aff_combination_to_tree (&aff_var
);
6774 gcc_assert (comp_op1
&& comp_op2
);
6776 comp_op1
= force_gimple_operand (comp_op1
, &seq
, true, NULL
);
6777 gimple_seq_add_seq (&stmt_list
, seq
);
6778 comp_op2
= force_gimple_operand (comp_op2
, &seq
, true, NULL
);
6779 gimple_seq_add_seq (&stmt_list
, seq
);
6781 if (POINTER_TYPE_P (TREE_TYPE (comp_op2
)))
6782 std::swap (comp_op1
, comp_op2
);
6784 if (POINTER_TYPE_P (TREE_TYPE (comp_op1
)))
6786 comp
= fold_build_pointer_plus (comp_op1
,
6787 fold_convert (sizetype
, comp_op2
));
6788 comp
= fold_build_pointer_plus (comp
,
6789 wide_int_to_tree (sizetype
, offset
));
6793 comp
= fold_build2 (PLUS_EXPR
, TREE_TYPE (comp_op1
), comp_op1
,
6794 fold_convert (TREE_TYPE (comp_op1
), comp_op2
));
6795 comp
= fold_build2 (PLUS_EXPR
, TREE_TYPE (comp_op1
), comp
,
6796 wide_int_to_tree (TREE_TYPE (comp_op1
), offset
));
6799 comp
= fold_convert (type
, comp
);
6800 if (!valid_gimple_rhs_p (comp
)
6801 || (gimple_code (use
->stmt
) != GIMPLE_PHI
6802 /* We can't allow re-allocating the stmt as it might be pointed
6804 && (get_gimple_rhs_num_ops (TREE_CODE (comp
))
6805 >= gimple_num_ops (gsi_stmt (bsi
)))))
6807 comp
= force_gimple_operand (comp
, &seq
, true, NULL
);
6808 gimple_seq_add_seq (&stmt_list
, seq
);
6809 if (POINTER_TYPE_P (TREE_TYPE (tgt
)))
6811 duplicate_ssa_name_ptr_info (comp
, SSA_NAME_PTR_INFO (tgt
));
6812 /* As this isn't a plain copy we have to reset alignment
6814 if (SSA_NAME_PTR_INFO (comp
))
6815 mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (comp
));
6819 gsi_insert_seq_before (&bsi
, stmt_list
, GSI_SAME_STMT
);
6820 if (gimple_code (use
->stmt
) == GIMPLE_PHI
)
6822 ass
= gimple_build_assign (tgt
, comp
);
6823 gsi_insert_before (&bsi
, ass
, GSI_SAME_STMT
);
6825 bsi
= gsi_for_stmt (use
->stmt
);
6826 remove_phi_node (&bsi
, false);
6830 gimple_assign_set_rhs_from_tree (&bsi
, comp
);
6831 use
->stmt
= gsi_stmt (bsi
);
6835 /* Performs a peephole optimization to reorder the iv update statement with
6836 a mem ref to enable instruction combining in later phases. The mem ref uses
6837 the iv value before the update, so the reordering transformation requires
6838 adjustment of the offset. CAND is the selected IV_CAND.
6842 t = MEM_REF (base, iv1, 8, 16); // base, index, stride, offset
6850 directly propagating t over to (1) will introduce overlapping live range
6851 thus increase register pressure. This peephole transform it into:
6855 t = MEM_REF (base, iv2, 8, 8);
6862 adjust_iv_update_pos (struct iv_cand
*cand
, struct iv_use
*use
)
6865 gimple
*iv_update
, *stmt
;
6867 gimple_stmt_iterator gsi
, gsi_iv
;
6869 if (cand
->pos
!= IP_NORMAL
)
6872 var_after
= cand
->var_after
;
6873 iv_update
= SSA_NAME_DEF_STMT (var_after
);
6875 bb
= gimple_bb (iv_update
);
6876 gsi
= gsi_last_nondebug_bb (bb
);
6877 stmt
= gsi_stmt (gsi
);
6879 /* Only handle conditional statement for now. */
6880 if (gimple_code (stmt
) != GIMPLE_COND
)
6883 gsi_prev_nondebug (&gsi
);
6884 stmt
= gsi_stmt (gsi
);
6885 if (stmt
!= iv_update
)
6888 gsi_prev_nondebug (&gsi
);
6889 if (gsi_end_p (gsi
))
6892 stmt
= gsi_stmt (gsi
);
6893 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
6896 if (stmt
!= use
->stmt
)
6899 if (TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
6902 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6904 fprintf (dump_file
, "Reordering \n");
6905 print_gimple_stmt (dump_file
, iv_update
, 0, 0);
6906 print_gimple_stmt (dump_file
, use
->stmt
, 0, 0);
6907 fprintf (dump_file
, "\n");
6910 gsi
= gsi_for_stmt (use
->stmt
);
6911 gsi_iv
= gsi_for_stmt (iv_update
);
6912 gsi_move_before (&gsi_iv
, &gsi
);
6914 cand
->pos
= IP_BEFORE_USE
;
6915 cand
->incremented_at
= use
->stmt
;
6918 /* Rewrites USE (address that is an iv) using candidate CAND. */
6921 rewrite_use_address (struct ivopts_data
*data
,
6922 struct iv_use
*use
, struct iv_cand
*cand
)
6927 adjust_iv_update_pos (cand
, use
);
6928 ok
= get_computation_aff (data
->current_loop
, use
->stmt
, use
, cand
, &aff
);
6930 unshare_aff_combination (&aff
);
6932 /* To avoid undefined overflow problems, all IV candidates use unsigned
6933 integer types. The drawback is that this makes it impossible for
6934 create_mem_ref to distinguish an IV that is based on a memory object
6935 from one that represents simply an offset.
6937 To work around this problem, we pass a hint to create_mem_ref that
6938 indicates which variable (if any) in aff is an IV based on a memory
6939 object. Note that we only consider the candidate. If this is not
6940 based on an object, the base of the reference is in some subexpression
6941 of the use -- but these will use pointer types, so they are recognized
6942 by the create_mem_ref heuristics anyway. */
6943 tree iv
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
6944 tree base_hint
= (cand
->iv
->base_object
) ? iv
: NULL_TREE
;
6945 gimple_stmt_iterator bsi
= gsi_for_stmt (use
->stmt
);
6946 tree type
= TREE_TYPE (*use
->op_p
);
6947 unsigned int align
= get_object_alignment (*use
->op_p
);
6948 if (align
!= TYPE_ALIGN (type
))
6949 type
= build_aligned_type (type
, align
);
6951 tree ref
= create_mem_ref (&bsi
, type
, &aff
,
6952 reference_alias_ptr_type (*use
->op_p
),
6953 iv
, base_hint
, data
->speed
);
6955 copy_ref_info (ref
, *use
->op_p
);
6959 /* Rewrites USE (the condition such that one of the arguments is an iv) using
6963 rewrite_use_compare (struct ivopts_data
*data
,
6964 struct iv_use
*use
, struct iv_cand
*cand
)
6966 tree comp
, op
, bound
;
6967 gimple_stmt_iterator bsi
= gsi_for_stmt (use
->stmt
);
6968 enum tree_code compare
;
6969 struct iv_group
*group
= data
->vgroups
[use
->group_id
];
6970 struct cost_pair
*cp
= get_group_iv_cost (data
, group
, cand
);
6975 tree var
= var_at_stmt (data
->current_loop
, cand
, use
->stmt
);
6976 tree var_type
= TREE_TYPE (var
);
6979 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
6981 fprintf (dump_file
, "Replacing exit test: ");
6982 print_gimple_stmt (dump_file
, use
->stmt
, 0, TDF_SLIM
);
6985 bound
= unshare_expr (fold_convert (var_type
, bound
));
6986 op
= force_gimple_operand (bound
, &stmts
, true, NULL_TREE
);
6988 gsi_insert_seq_on_edge_immediate (
6989 loop_preheader_edge (data
->current_loop
),
6992 gcond
*cond_stmt
= as_a
<gcond
*> (use
->stmt
);
6993 gimple_cond_set_lhs (cond_stmt
, var
);
6994 gimple_cond_set_code (cond_stmt
, compare
);
6995 gimple_cond_set_rhs (cond_stmt
, op
);
6999 /* The induction variable elimination failed; just express the original
7001 comp
= get_computation_at (data
->current_loop
, use
->stmt
, use
, cand
);
7002 gcc_assert (comp
!= NULL_TREE
);
7003 gcc_assert (use
->op_p
!= NULL
);
7004 *use
->op_p
= force_gimple_operand_gsi (&bsi
, comp
, true,
7005 SSA_NAME_VAR (*use
->op_p
),
7006 true, GSI_SAME_STMT
);
7009 /* Rewrite the groups using the selected induction variables. */
7012 rewrite_groups (struct ivopts_data
*data
)
7016 for (i
= 0; i
< data
->vgroups
.length (); i
++)
7018 struct iv_group
*group
= data
->vgroups
[i
];
7019 struct iv_cand
*cand
= group
->selected
;
7023 if (group
->type
== USE_NONLINEAR_EXPR
)
7025 for (j
= 0; j
< group
->vuses
.length (); j
++)
7027 rewrite_use_nonlinear_expr (data
, group
->vuses
[j
], cand
);
7028 update_stmt (group
->vuses
[j
]->stmt
);
7031 else if (group
->type
== USE_ADDRESS
)
7033 for (j
= 0; j
< group
->vuses
.length (); j
++)
7035 rewrite_use_address (data
, group
->vuses
[j
], cand
);
7036 update_stmt (group
->vuses
[j
]->stmt
);
7041 gcc_assert (group
->type
== USE_COMPARE
);
7043 for (j
= 0; j
< group
->vuses
.length (); j
++)
7045 rewrite_use_compare (data
, group
->vuses
[j
], cand
);
7046 update_stmt (group
->vuses
[j
]->stmt
);
7052 /* Removes the ivs that are not used after rewriting. */
7055 remove_unused_ivs (struct ivopts_data
*data
)
7059 bitmap toremove
= BITMAP_ALLOC (NULL
);
7061 /* Figure out an order in which to release SSA DEFs so that we don't
7062 release something that we'd have to propagate into a debug stmt
7064 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, j
, bi
)
7066 struct version_info
*info
;
7068 info
= ver_info (data
, j
);
7070 && !integer_zerop (info
->iv
->step
)
7072 && !info
->iv
->nonlin_use
7073 && !info
->preserve_biv
)
7075 bitmap_set_bit (toremove
, SSA_NAME_VERSION (info
->iv
->ssa_name
));
7077 tree def
= info
->iv
->ssa_name
;
7079 if (MAY_HAVE_DEBUG_STMTS
&& SSA_NAME_DEF_STMT (def
))
7081 imm_use_iterator imm_iter
;
7082 use_operand_p use_p
;
7086 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, def
)
7088 if (!gimple_debug_bind_p (stmt
))
7091 /* We just want to determine whether to do nothing
7092 (count == 0), to substitute the computed
7093 expression into a single use of the SSA DEF by
7094 itself (count == 1), or to use a debug temp
7095 because the SSA DEF is used multiple times or as
7096 part of a larger expression (count > 1). */
7098 if (gimple_debug_bind_get_value (stmt
) != def
)
7102 BREAK_FROM_IMM_USE_STMT (imm_iter
);
7108 struct iv_use dummy_use
;
7109 struct iv_cand
*best_cand
= NULL
, *cand
;
7110 unsigned i
, best_pref
= 0, cand_pref
;
7112 memset (&dummy_use
, 0, sizeof (dummy_use
));
7113 dummy_use
.iv
= info
->iv
;
7114 for (i
= 0; i
< data
->vgroups
.length () && i
< 64; i
++)
7116 cand
= data
->vgroups
[i
]->selected
;
7117 if (cand
== best_cand
)
7119 cand_pref
= operand_equal_p (cand
->iv
->step
,
7123 += TYPE_MODE (TREE_TYPE (cand
->iv
->base
))
7124 == TYPE_MODE (TREE_TYPE (info
->iv
->base
))
7127 += TREE_CODE (cand
->iv
->base
) == INTEGER_CST
7129 if (best_cand
== NULL
|| best_pref
< cand_pref
)
7132 best_pref
= cand_pref
;
7139 tree comp
= get_computation_at (data
->current_loop
,
7140 SSA_NAME_DEF_STMT (def
),
7141 &dummy_use
, best_cand
);
7147 tree vexpr
= make_node (DEBUG_EXPR_DECL
);
7148 DECL_ARTIFICIAL (vexpr
) = 1;
7149 TREE_TYPE (vexpr
) = TREE_TYPE (comp
);
7150 if (SSA_NAME_VAR (def
))
7151 SET_DECL_MODE (vexpr
, DECL_MODE (SSA_NAME_VAR (def
)));
7153 SET_DECL_MODE (vexpr
, TYPE_MODE (TREE_TYPE (vexpr
)));
7155 = gimple_build_debug_bind (vexpr
, comp
, NULL
);
7156 gimple_stmt_iterator gsi
;
7158 if (gimple_code (SSA_NAME_DEF_STMT (def
)) == GIMPLE_PHI
)
7159 gsi
= gsi_after_labels (gimple_bb
7160 (SSA_NAME_DEF_STMT (def
)));
7162 gsi
= gsi_for_stmt (SSA_NAME_DEF_STMT (def
));
7164 gsi_insert_before (&gsi
, def_temp
, GSI_SAME_STMT
);
7168 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, def
)
7170 if (!gimple_debug_bind_p (stmt
))
7173 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
7174 SET_USE (use_p
, comp
);
7182 release_defs_bitset (toremove
);
7184 BITMAP_FREE (toremove
);
7187 /* Frees memory occupied by struct tree_niter_desc in *VALUE. Callback
7188 for hash_map::traverse. */
7191 free_tree_niter_desc (edge
const &, tree_niter_desc
*const &value
, void *)
7197 /* Frees data allocated by the optimization of a single loop. */
7200 free_loop_data (struct ivopts_data
*data
)
7208 data
->niters
->traverse
<void *, free_tree_niter_desc
> (NULL
);
7209 delete data
->niters
;
7210 data
->niters
= NULL
;
7213 EXECUTE_IF_SET_IN_BITMAP (data
->relevant
, 0, i
, bi
)
7215 struct version_info
*info
;
7217 info
= ver_info (data
, i
);
7219 info
->has_nonlin_use
= false;
7220 info
->preserve_biv
= false;
7223 bitmap_clear (data
->relevant
);
7224 bitmap_clear (data
->important_candidates
);
7226 for (i
= 0; i
< data
->vgroups
.length (); i
++)
7228 struct iv_group
*group
= data
->vgroups
[i
];
7230 for (j
= 0; j
< group
->vuses
.length (); j
++)
7231 free (group
->vuses
[j
]);
7232 group
->vuses
.release ();
7234 BITMAP_FREE (group
->related_cands
);
7235 for (j
= 0; j
< group
->n_map_members
; j
++)
7237 if (group
->cost_map
[j
].inv_vars
)
7238 BITMAP_FREE (group
->cost_map
[j
].inv_vars
);
7239 if (group
->cost_map
[j
].inv_exprs
)
7240 BITMAP_FREE (group
->cost_map
[j
].inv_exprs
);
7243 free (group
->cost_map
);
7246 data
->vgroups
.truncate (0);
7248 for (i
= 0; i
< data
->vcands
.length (); i
++)
7250 struct iv_cand
*cand
= data
->vcands
[i
];
7253 BITMAP_FREE (cand
->inv_vars
);
7254 if (cand
->inv_exprs
)
7255 BITMAP_FREE (cand
->inv_exprs
);
7258 data
->vcands
.truncate (0);
7260 if (data
->version_info_size
< num_ssa_names
)
7262 data
->version_info_size
= 2 * num_ssa_names
;
7263 free (data
->version_info
);
7264 data
->version_info
= XCNEWVEC (struct version_info
, data
->version_info_size
);
7267 data
->max_inv_var_id
= 0;
7268 data
->max_inv_expr_id
= 0;
7270 FOR_EACH_VEC_ELT (decl_rtl_to_reset
, i
, obj
)
7271 SET_DECL_RTL (obj
, NULL_RTX
);
7273 decl_rtl_to_reset
.truncate (0);
7275 data
->inv_expr_tab
->empty ();
7277 data
->iv_common_cand_tab
->empty ();
7278 data
->iv_common_cands
.truncate (0);
7281 /* Finalizes data structures used by the iv optimization pass. LOOPS is the
7285 tree_ssa_iv_optimize_finalize (struct ivopts_data
*data
)
7287 free_loop_data (data
);
7288 free (data
->version_info
);
7289 BITMAP_FREE (data
->relevant
);
7290 BITMAP_FREE (data
->important_candidates
);
7292 decl_rtl_to_reset
.release ();
7293 data
->vgroups
.release ();
7294 data
->vcands
.release ();
7295 delete data
->inv_expr_tab
;
7296 data
->inv_expr_tab
= NULL
;
7297 free_affine_expand_cache (&data
->name_expansion_cache
);
7298 delete data
->iv_common_cand_tab
;
7299 data
->iv_common_cand_tab
= NULL
;
7300 data
->iv_common_cands
.release ();
7301 obstack_free (&data
->iv_obstack
, NULL
);
7304 /* Returns true if the loop body BODY includes any function calls. */
7307 loop_body_includes_call (basic_block
*body
, unsigned num_nodes
)
7309 gimple_stmt_iterator gsi
;
7312 for (i
= 0; i
< num_nodes
; i
++)
7313 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
7315 gimple
*stmt
= gsi_stmt (gsi
);
7316 if (is_gimple_call (stmt
)
7317 && !gimple_call_internal_p (stmt
)
7318 && !is_inexpensive_builtin (gimple_call_fndecl (stmt
)))
7324 /* Optimizes the LOOP. Returns true if anything changed. */
7327 tree_ssa_iv_optimize_loop (struct ivopts_data
*data
, struct loop
*loop
)
7329 bool changed
= false;
7330 struct iv_ca
*iv_ca
;
7331 edge exit
= single_dom_exit (loop
);
7334 gcc_assert (!data
->niters
);
7335 data
->current_loop
= loop
;
7336 data
->loop_loc
= find_loop_location (loop
);
7337 data
->speed
= optimize_loop_for_speed_p (loop
);
7339 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7341 fprintf (dump_file
, "Processing loop %d", loop
->num
);
7342 if (data
->loop_loc
!= UNKNOWN_LOCATION
)
7343 fprintf (dump_file
, " at %s:%d", LOCATION_FILE (data
->loop_loc
),
7344 LOCATION_LINE (data
->loop_loc
));
7345 fprintf (dump_file
, "\n");
7349 fprintf (dump_file
, " single exit %d -> %d, exit condition ",
7350 exit
->src
->index
, exit
->dest
->index
);
7351 print_gimple_stmt (dump_file
, last_stmt (exit
->src
), 0, TDF_SLIM
);
7352 fprintf (dump_file
, "\n");
7355 fprintf (dump_file
, "\n");
7358 body
= get_loop_body (loop
);
7359 data
->body_includes_call
= loop_body_includes_call (body
, loop
->num_nodes
);
7360 renumber_gimple_stmt_uids_in_blocks (body
, loop
->num_nodes
);
7363 data
->loop_single_exit_p
= exit
!= NULL
&& loop_only_exit_p (loop
, exit
);
7365 /* For each ssa name determines whether it behaves as an induction variable
7367 if (!find_induction_variables (data
))
7370 /* Finds interesting uses (item 1). */
7371 find_interesting_uses (data
);
7372 if (data
->vgroups
.length () > MAX_CONSIDERED_GROUPS
)
7375 /* Finds candidates for the induction variables (item 2). */
7376 find_iv_candidates (data
);
7378 /* Calculates the costs (item 3, part 1). */
7379 determine_iv_costs (data
);
7380 determine_group_iv_costs (data
);
7381 determine_set_costs (data
);
7383 /* Find the optimal set of induction variables (item 3, part 2). */
7384 iv_ca
= find_optimal_iv_set (data
);
7389 /* Create the new induction variables (item 4, part 1). */
7390 create_new_ivs (data
, iv_ca
);
7391 iv_ca_free (&iv_ca
);
7393 /* Rewrite the uses (item 4, part 2). */
7394 rewrite_groups (data
);
7396 /* Remove the ivs that are unused after rewriting. */
7397 remove_unused_ivs (data
);
7399 /* We have changed the structure of induction variables; it might happen
7400 that definitions in the scev database refer to some of them that were
7405 free_loop_data (data
);
7410 /* Main entry point. Optimizes induction variables in loops. */
7413 tree_ssa_iv_optimize (void)
7416 struct ivopts_data data
;
7418 tree_ssa_iv_optimize_init (&data
);
7420 /* Optimize the loops starting with the innermost ones. */
7421 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
7423 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
7424 flow_loop_dump (loop
, dump_file
, NULL
, 1);
7426 tree_ssa_iv_optimize_loop (&data
, loop
);
7429 tree_ssa_iv_optimize_finalize (&data
);
7432 #include "gt-tree-ssa-loop-ivopts.h"