1/* Induction variable optimizations.
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it
7under the terms of the GNU General Public License as published by the
8Free Software Foundation; either version 3, or (at your option) any
9later version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT
12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
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
25 following steps:
26
27 1) The interesting uses of induction variables are found. This includes
28
29 -- uses of induction variables in non-linear expressions
30 -- addresses of arrays
31 -- comparisons of induction variables
32
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.
36
37 2) Candidates for the induction variables are found. This includes
38
39 -- old induction variables
40 -- the variables defined by expressions derived from the "interesting
41 groups/uses" above
42
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
45 of three parts:
46
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
51 arrays, etc.).
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.
57
58 All the costs are defined in a machine-specific way, using the target
59 hooks and machine descriptions to determine them.
60
61 4) The trees are transformed to use the new variables, the dead code is
62 removed.
63
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. */
68
69#include "config.h"
70#include "system.h"
71#include "coretypes.h"
72#include "backend.h"
73#include "rtl.h"
74#include "tree.h"
75#include "gimple.h"
76#include "cfghooks.h"
77#include "tree-pass.h"
78#include "memmodel.h"
79#include "tm_p.h"
80#include "ssa.h"
81#include "expmed.h"
82#include "insn-config.h"
83#include "emit-rtl.h"
84#include "recog.h"
85#include "cgraph.h"
86#include "gimple-pretty-print.h"
87#include "alias.h"
88#include "fold-const.h"
89#include "stor-layout.h"
90#include "tree-eh.h"
91#include "gimplify.h"
92#include "gimple-iterator.h"
93#include "gimplify-me.h"
94#include "tree-cfg.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"
99#include "explow.h"
100#include "expr.h"
101#include "tree-dfa.h"
102#include "tree-ssa.h"
103#include "cfgloop.h"
104#include "tree-scalar-evolution.h"
105#include "params.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"
111
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. */
115
116/* The infinite cost. */
117#define INFTY 10000000
118
119/* Returns the expected number of loop iterations for LOOP.
120 The average trip count is computed from profile data if it
121 exists. */
122
123static inline HOST_WIDE_INT
124avg_loop_niter (struct loop *loop)
125{
126 HOST_WIDE_INT niter = estimated_stmt_executions_int (loop);
127 if (niter == -1)
128 {
129 niter = likely_max_stmt_executions_int (loop);
130
131 if (niter == -1 || niter > PARAM_VALUE (PARAM_AVG_LOOP_NITER))
132 return PARAM_VALUE (PARAM_AVG_LOOP_NITER);
133 }
134
135 return niter;
136}
137
138struct iv_use;
139
140/* Representation of the induction variable. */
141struct iv
142{
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
151 type use. */
152};
153
154/* Per-ssa version information (induction variable descriptions, etc.). */
155struct version_info
156{
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. */
163};
164
165/* Types of uses. */
166enum use_type
167{
168 USE_NONLINEAR_EXPR, /* Use in a nonlinear expression. */
169 USE_ADDRESS, /* Use in an address. */
170 USE_COMPARE /* Use is a compare. */
171};
172
173/* Cost of a computation. */
174struct comp_cost
175{
176 comp_cost (): cost (0), complexity (0), scratch (0)
177 {}
178
179 comp_cost (int cost, unsigned complexity, int scratch = 0)
180 : cost (cost), complexity (complexity), scratch (scratch)
181 {}
182
183 /* Returns true if COST is infinite. */
184 bool infinite_cost_p ();
185
186 /* Adds costs COST1 and COST2. */
187 friend comp_cost operator+ (comp_cost cost1, comp_cost cost2);
188
189 /* Adds COST to the comp_cost. */
190 comp_cost operator+= (comp_cost cost);
191
192 /* Adds constant C to this comp_cost. */
193 comp_cost operator+= (HOST_WIDE_INT c);
194
195 /* Subtracts constant C to this comp_cost. */
196 comp_cost operator-= (HOST_WIDE_INT c);
197
198 /* Divide the comp_cost by constant C. */
199 comp_cost operator/= (HOST_WIDE_INT c);
200
201 /* Multiply the comp_cost by constant C. */
202 comp_cost operator*= (HOST_WIDE_INT c);
203
204 /* Subtracts costs COST1 and COST2. */
205 friend comp_cost operator- (comp_cost cost1, comp_cost cost2);
206
207 /* Subtracts COST from this comp_cost. */
208 comp_cost operator-= (comp_cost cost);
209
210 /* Returns true if COST1 is smaller than COST2. */
211 friend bool operator< (comp_cost cost1, comp_cost cost2);
212
213 /* Returns true if COST1 and COST2 are equal. */
214 friend bool operator== (comp_cost cost1, comp_cost cost2);
215
216 /* Returns true if COST1 is smaller or equal than COST2. */
217 friend bool operator<= (comp_cost cost1, comp_cost cost2);
218
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. */
225};
226
227static const comp_cost no_cost;
228static const comp_cost infinite_cost (INFTY, INFTY, INFTY);
229
230bool
231comp_cost::infinite_cost_p ()
232{
233 return cost == INFTY;
234}
235
236comp_cost
237operator+ (comp_cost cost1, comp_cost cost2)
238{
239 if (cost1.infinite_cost_p () || cost2.infinite_cost_p ())
240 return infinite_cost;
241
242 cost1.cost += cost2.cost;
243 cost1.complexity += cost2.complexity;
244
245 return cost1;
246}
247
248comp_cost
249operator- (comp_cost cost1, comp_cost cost2)
250{
251 if (cost1.infinite_cost_p ())
252 return infinite_cost;
253
254 gcc_assert (!cost2.infinite_cost_p ());
255
256 cost1.cost -= cost2.cost;
257 cost1.complexity -= cost2.complexity;
258
259 return cost1;
260}
261
262comp_cost
263comp_cost::operator+= (comp_cost cost)
264{
265 *this = *this + cost;
266 return *this;
267}
268
269comp_cost
270comp_cost::operator+= (HOST_WIDE_INT c)
271{
272 if (infinite_cost_p ())
273 return *this;
274
275 this->cost += c;
276
277 return *this;
278}
279
280comp_cost
281comp_cost::operator-= (HOST_WIDE_INT c)
282{
283 if (infinite_cost_p ())
284 return *this;
285
286 this->cost -= c;
287
288 return *this;
289}
290
291comp_cost
292comp_cost::operator/= (HOST_WIDE_INT c)
293{
294 if (infinite_cost_p ())
295 return *this;
296
297 this->cost /= c;
298
299 return *this;
300}
301
302comp_cost
303comp_cost::operator*= (HOST_WIDE_INT c)
304{
305 if (infinite_cost_p ())
306 return *this;
307
308 this->cost *= c;
309
310 return *this;
311}
312
313comp_cost
314comp_cost::operator-= (comp_cost cost)
315{
316 *this = *this - cost;
317 return *this;
318}
319
320bool
321operator< (comp_cost cost1, comp_cost cost2)
322{
323 if (cost1.cost == cost2.cost)
324 return cost1.complexity < cost2.complexity;
325
326 return cost1.cost < cost2.cost;
327}
328
329bool
330operator== (comp_cost cost1, comp_cost cost2)
331{
332 return cost1.cost == cost2.cost
333 && cost1.complexity == cost2.complexity;
334}
335
336bool
337operator<= (comp_cost cost1, comp_cost cost2)
338{
339 return cost1 < cost2 || cost1 == cost2;
340}
341
342struct iv_inv_expr_ent;
343
344/* The candidate - cost pair. */
345struct cost_pair
346{
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. */
357};
358
359/* Use. */
360struct iv_use
361{
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. */
368
369 tree addr_base; /* Base address with const offset stripped. */
370 unsigned HOST_WIDE_INT addr_offset;
371 /* Const offset stripped from base address. */
372};
373
374/* Group of uses. */
375struct iv_group
376{
377 /* The id of the group. */
378 unsigned id;
379 /* Uses of the group are of the same type. */
380 enum use_type 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;
391};
392
393/* The position where the iv is computed. */
394enum iv_position
395{
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. */
401};
402
403/* The induction variable candidate. */
404struct iv_cand
405{
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
411 incremented. */
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
423 iv_cand. */
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
428 smaller type. */
429};
430
431/* Hashtable entry for common candidate derived from iv uses. */
432struct iv_common_cand
433{
434 tree base;
435 tree step;
436 /* IV uses from which this common candidate is derived. */
437 auto_vec<struct iv_use *> uses;
438 hashval_t hash;
439};
440
441/* Hashtable helpers. */
442
443struct iv_common_cand_hasher : delete_ptr_hash <iv_common_cand>
444{
445 static inline hashval_t hash (const iv_common_cand *);
446 static inline bool equal (const iv_common_cand *, const iv_common_cand *);
447};
448
449/* Hash function for possible common candidates. */
450
451inline hashval_t
452iv_common_cand_hasher::hash (const iv_common_cand *ccand)
453{
454 return ccand->hash;
455}
456
457/* Hash table equality function for common candidates. */
458
459inline bool
460iv_common_cand_hasher::equal (const iv_common_cand *ccand1,
461 const iv_common_cand *ccand2)
462{
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))));
468}
469
470/* Loop invariant expression hashtable entry. */
471
472struct iv_inv_expr_ent
473{
474 /* Tree expression of the entry. */
475 tree expr;
476 /* Unique indentifier. */
477 int id;
478 /* Hash value. */
479 hashval_t hash;
480};
481
482/* Sort iv_inv_expr_ent pair A and B by id field. */
483
484static int
485sort_iv_inv_expr_ent (const void *a, const void *b)
486{
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);
489
490 unsigned id1 = (*e1)->id;
491 unsigned id2 = (*e2)->id;
492
493 if (id1 < id2)
494 return -1;
495 else if (id1 > id2)
496 return 1;
497 else
498 return 0;
499}
500
501/* Hashtable helpers. */
502
503struct iv_inv_expr_hasher : free_ptr_hash <iv_inv_expr_ent>
504{
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 *);
507};
508
509/* Hash function for loop invariant expressions. */
510
511inline hashval_t
512iv_inv_expr_hasher::hash (const iv_inv_expr_ent *expr)
513{
514 return expr->hash;
515}
516
517/* Hash table equality function for expressions. */
518
519inline bool
520iv_inv_expr_hasher::equal (const iv_inv_expr_ent *expr1,
521 const iv_inv_expr_ent *expr2)
522{
523 return expr1->hash == expr2->hash
524 && operand_equal_p (expr1->expr, expr2->expr, 0);
525}
526
527struct ivopts_data
528{
529 /* The currently optimized loop. */
530 struct loop *current_loop;
531 source_location loop_loc;
532
533 /* Numbers of iterations for all exits of the current loop. */
534 hash_map<edge, tree_niter_desc *> *niters;
535
536 /* Number of registers used in it. */
537 unsigned regs_used;
538
539 /* The size of version_info array allocated. */
540 unsigned version_info_size;
541
542 /* The array of information for the ssa names. */
543 struct version_info *version_info;
544
545 /* The hashtable of loop invariant expressions created
546 by ivopt. */
547 hash_table<iv_inv_expr_hasher> *inv_expr_tab;
548
549 /* The bitmap of indices in version_info whose value was changed. */
550 bitmap relevant;
551
552 /* The uses of induction variables. */
553 vec<iv_group *> vgroups;
554
555 /* The candidates. */
556 vec<iv_cand *> vcands;
557
558 /* A bitmap of important candidates. */
559 bitmap important_candidates;
560
561 /* Cache used by tree_to_aff_combination_expand. */
562 hash_map<tree, name_expansion *> *name_expansion_cache;
563
564 /* The hashtable of common candidates derived from iv uses. */
565 hash_table<iv_common_cand_hasher> *iv_common_cand_tab;
566
567 /* The common candidates. */
568 vec<iv_common_cand *> iv_common_cands;
569
570 /* The maximum invariant variable id. */
571 unsigned max_inv_var_id;
572
573 /* The maximum invariant expression id. */
574 unsigned max_inv_expr_id;
575
576 /* Number of no_overflow BIVs which are not used in memory address. */
577 unsigned bivs_not_used_in_addr;
578
579 /* Obstack for iv structure. */
580 struct obstack iv_obstack;
581
582 /* Whether to consider just related and important candidates when replacing a
583 use. */
584 bool consider_all_candidates;
585
586 /* Are we optimizing for speed? */
587 bool speed;
588
589 /* Whether the loop body includes any function calls. */
590 bool body_includes_call;
591
592 /* Whether the loop body can only be exited via single exit. */
593 bool loop_single_exit_p;
594};
595
596/* An assignment of iv candidates to uses. */
597
598struct iv_ca
599{
600 /* The number of uses covered by the assignment. */
601 unsigned upto;
602
603 /* Number of uses that cannot be expressed by the candidates in the set. */
604 unsigned bad_groups;
605
606 /* Candidate assigned to a use, together with the related costs. */
607 struct cost_pair **cand_for_group;
608
609 /* Number of times each candidate is used. */
610 unsigned *n_cand_uses;
611
612 /* The candidates used. */
613 bitmap cands;
614
615 /* The number of candidates in the set. */
616 unsigned n_cands;
617
618 /* The number of invariants needed, including both invariant variants and
619 invariant expressions. */
620 unsigned n_invs;
621
622 /* Total cost of expressing uses. */
623 comp_cost cand_use_cost;
624
625 /* Total cost of candidates. */
626 unsigned cand_cost;
627
628 /* Number of times each invariant variable is used. */
629 unsigned *n_inv_var_uses;
630
631 /* Number of times each invariant expression is used. */
632 unsigned *n_inv_expr_uses;
633
634 /* Total cost of the assignment. */
635 comp_cost cost;
636};
637
638/* Difference of two iv candidate assignments. */
639
640struct iv_ca_delta
641{
642 /* Changed group. */
643 struct iv_group *group;
644
645 /* An old assignment (for rollback purposes). */
646 struct cost_pair *old_cp;
647
648 /* A new assignment. */
649 struct cost_pair *new_cp;
650
651 /* Next change in the list. */
652 struct iv_ca_delta *next;
653};
654
655/* Bound on number of candidates below that all candidates are considered. */
656
657#define CONSIDER_ALL_CANDIDATES_BOUND \
658 ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND))
659
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). */
662
663#define MAX_CONSIDERED_GROUPS \
664 ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
665
666/* If there are at most this number of ivs in the set, try removing unnecessary
667 ivs from the set always. */
668
669#define ALWAYS_PRUNE_CAND_SET_BOUND \
670 ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
671
672/* The list of trees for that the decl_rtl field must be reset is stored
673 here. */
674
675static vec<tree> decl_rtl_to_reset;
676
677static comp_cost force_expr_to_var_cost (tree, bool);
678
679/* The single loop exit if it dominates the latch, NULL otherwise. */
680
681edge
682single_dom_exit (struct loop *loop)
683{
684 edge exit = single_exit (loop);
685
686 if (!exit)
687 return NULL;
688
689 if (!just_once_each_iteration_p (loop, exit->src))
690 return NULL;
691
692 return exit;
693}
694
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. */
698
699void
700dump_iv (FILE *file, struct iv *iv, bool dump_name, unsigned indent_level)
701{
702 const char *p;
703 const char spaces[9] = {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '\0'};
704
705 if (indent_level > 4)
706 indent_level = 4;
707 p = spaces + 8 - (indent_level << 1);
708
709 fprintf (file, "%sIV struct:\n", p);
710 if (iv->ssa_name && dump_name)
711 {
712 fprintf (file, "%s SSA_NAME:\t", p);
713 print_generic_expr (file, iv->ssa_name, TDF_SLIM);
714 fprintf (file, "\n");
715 }
716
717 fprintf (file, "%s Type:\t", p);
718 print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
719 fprintf (file, "\n");
720
721 fprintf (file, "%s Base:\t", p);
722 print_generic_expr (file, iv->base, TDF_SLIM);
723 fprintf (file, "\n");
724
725 fprintf (file, "%s Step:\t", p);
726 print_generic_expr (file, iv->step, TDF_SLIM);
727 fprintf (file, "\n");
728
729 if (iv->base_object)
730 {
731 fprintf (file, "%s Object:\t", p);
732 print_generic_expr (file, iv->base_object, TDF_SLIM);
733 fprintf (file, "\n");
734 }
735
736 fprintf (file, "%s Biv:\t%c\n", p, iv->biv_p ? 'Y' : 'N');
737
738 fprintf (file, "%s Overflowness wrto loop niter:\t%s\n",
739 p, iv->no_overflow ? "No-overflow" : "Overflow");
740}
741
742/* Dumps information about the USE to FILE. */
743
744void
745dump_use (FILE *file, struct iv_use *use)
746{
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);
750 fprintf (file, " At pos:\t");
751 if (use->op_p)
752 print_generic_expr (file, *use->op_p, TDF_SLIM);
753 fprintf (file, "\n");
754 dump_iv (file, use->iv, false, 2);
755}
756
757/* Dumps information about the uses to FILE. */
758
759void
760dump_groups (FILE *file, struct ivopts_data *data)
761{
762 unsigned i, j;
763 struct iv_group *group;
764
765 for (i = 0; i < data->vgroups.length (); i++)
766 {
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");
773 else
774 {
775 gcc_assert (group->type == USE_COMPARE);
776 fprintf (file, " Type:\tCOMPARE\n");
777 }
778 for (j = 0; j < group->vuses.length (); j++)
779 dump_use (file, group->vuses[j]);
780 }
781}
782
783/* Dumps information about induction variable candidate CAND to FILE. */
784
785void
786dump_cand (FILE *file, struct iv_cand *cand)
787{
788 struct iv *iv = cand->iv;
789
790 fprintf (file, "Candidate %d:\n", cand->id);
791 if (cand->inv_vars)
792 {
793 fprintf (file, " Depend on inv.vars: ");
794 dump_bitmap (file, cand->inv_vars);
795 }
796 if (cand->inv_exprs)
797 {
798 fprintf (file, " Depend on inv.exprs: ");
799 dump_bitmap (file, cand->inv_exprs);
800 }
801
802 if (cand->var_before)
803 {
804 fprintf (file, " Var befor: ");
805 print_generic_expr (file, cand->var_before, TDF_SLIM);
806 fprintf (file, "\n");
807 }
808 if (cand->var_after)
809 {
810 fprintf (file, " Var after: ");
811 print_generic_expr (file, cand->var_after, TDF_SLIM);
812 fprintf (file, "\n");
813 }
814
815 switch (cand->pos)
816 {
817 case IP_NORMAL:
818 fprintf (file, " Incr POS: before exit test\n");
819 break;
820
821 case IP_BEFORE_USE:
822 fprintf (file, " Incr POS: before use %d\n", cand->ainc_use->id);
823 break;
824
825 case IP_AFTER_USE:
826 fprintf (file, " Incr POS: after use %d\n", cand->ainc_use->id);
827 break;
828
829 case IP_END:
830 fprintf (file, " Incr POS: at end\n");
831 break;
832
833 case IP_ORIGINAL:
834 fprintf (file, " Incr POS: orig biv\n");
835 break;
836 }
837
838 dump_iv (file, iv, false, 1);
839}
840
841/* Returns the info for ssa version VER. */
842
843static inline struct version_info *
844ver_info (struct ivopts_data *data, unsigned ver)
845{
846 return data->version_info + ver;
847}
848
849/* Returns the info for ssa name NAME. */
850
851static inline struct version_info *
852name_info (struct ivopts_data *data, tree name)
853{
854 return ver_info (data, SSA_NAME_VERSION (name));
855}
856
857/* Returns true if STMT is after the place where the IP_NORMAL ivs will be
858 emitted in LOOP. */
859
860static bool
861stmt_after_ip_normal_pos (struct loop *loop, gimple *stmt)
862{
863 basic_block bb = ip_normal_pos (loop), sbb = gimple_bb (stmt);
864
865 gcc_assert (bb);
866
867 if (sbb == loop->latch)
868 return true;
869
870 if (sbb != bb)
871 return false;
872
873 return stmt == last_stmt (bb);
874}
875
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. */
879
880static bool
881stmt_after_inc_pos (struct iv_cand *cand, gimple *stmt, bool true_if_equal)
882{
883 basic_block cand_bb = gimple_bb (cand->incremented_at);
884 basic_block stmt_bb = gimple_bb (stmt);
885
886 if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
887 return false;
888
889 if (stmt_bb != cand_bb)
890 return true;
891
892 if (true_if_equal
893 && gimple_uid (stmt) == gimple_uid (cand->incremented_at))
894 return true;
895 return gimple_uid (stmt) > gimple_uid (cand->incremented_at);
896}
897
898/* Returns true if STMT if after the place where the induction variable
899 CAND is incremented in LOOP. */
900
901static bool
902stmt_after_increment (struct loop *loop, struct iv_cand *cand, gimple *stmt)
903{
904 switch (cand->pos)
905 {
906 case IP_END:
907 return false;
908
909 case IP_NORMAL:
910 return stmt_after_ip_normal_pos (loop, stmt);
911
912 case IP_ORIGINAL:
913 case IP_AFTER_USE:
914 return stmt_after_inc_pos (cand, stmt, false);
915
916 case IP_BEFORE_USE:
917 return stmt_after_inc_pos (cand, stmt, true);
918
919 default:
920 gcc_unreachable ();
921 }
922}
923
924/* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */
925
926static bool
927abnormal_ssa_name_p (tree exp)
928{
929 if (!exp)
930 return false;
931
932 if (TREE_CODE (exp) != SSA_NAME)
933 return false;
934
935 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) != 0;
936}
937
938/* Returns false if BASE or INDEX contains a ssa name that occurs in an
939 abnormal phi node. Callback for for_each_index. */
940
941static bool
942idx_contains_abnormal_ssa_name_p (tree base, tree *index,
943 void *data ATTRIBUTE_UNUSED)
944{
945 if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
946 {
947 if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
948 return false;
949 if (abnormal_ssa_name_p (TREE_OPERAND (base, 3)))
950 return false;
951 }
952
953 return !abnormal_ssa_name_p (*index);
954}
955
956/* Returns true if EXPR contains a ssa name that occurs in an
957 abnormal phi node. */
958
959bool
960contains_abnormal_ssa_name_p (tree expr)
961{
962 enum tree_code code;
963 enum tree_code_class codeclass;
964
965 if (!expr)
966 return false;
967
968 code = TREE_CODE (expr);
969 codeclass = TREE_CODE_CLASS (code);
970
971 if (code == SSA_NAME)
972 return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
973
974 if (code == INTEGER_CST
975 || is_gimple_min_invariant (expr))
976 return false;
977
978 if (code == ADDR_EXPR)
979 return !for_each_index (&TREE_OPERAND (expr, 0),
980 idx_contains_abnormal_ssa_name_p,
981 NULL);
982
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));
987
988 switch (codeclass)
989 {
990 case tcc_binary:
991 case tcc_comparison:
992 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1)))
993 return true;
994
995 /* Fallthru. */
996 case tcc_unary:
997 if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0)))
998 return true;
999
1000 break;
1001
1002 default:
1003 gcc_unreachable ();
1004 }
1005
1006 return false;
1007}
1008
1009/* Returns the structure describing number of iterations determined from
1010 EXIT of DATA->current_loop, or NULL if something goes wrong. */
1011
1012static struct tree_niter_desc *
1013niter_for_exit (struct ivopts_data *data, edge exit)
1014{
1015 struct tree_niter_desc *desc;
1016 tree_niter_desc **slot;
1017
1018 if (!data->niters)
1019 {
1020 data->niters = new hash_map<edge, tree_niter_desc *>;
1021 slot = NULL;
1022 }
1023 else
1024 slot = data->niters->get (exit);
1025
1026 if (!slot)
1027 {
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,
1033 exit, desc, true)
1034 || contains_abnormal_ssa_name_p (desc->niter))
1035 {
1036 XDELETE (desc);
1037 desc = NULL;
1038 }
1039 data->niters->put (exit, desc);
1040 }
1041 else
1042 desc = *slot;
1043
1044 return desc;
1045}
1046
1047/* Returns the structure describing number of iterations determined from
1048 single dominating exit of DATA->current_loop, or NULL if something
1049 goes wrong. */
1050
1051static struct tree_niter_desc *
1052niter_for_single_dom_exit (struct ivopts_data *data)
1053{
1054 edge exit = single_dom_exit (data->current_loop);
1055
1056 if (!exit)
1057 return NULL;
1058
1059 return niter_for_exit (data, exit);
1060}
1061
1062/* Initializes data structures used by the iv optimization pass, stored
1063 in DATA. */
1064
1065static void
1066tree_ssa_iv_optimize_init (struct ivopts_data *data)
1067{
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);
1083}
1084
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. */
1087
1088static tree
1089determine_base_object (tree expr)
1090{
1091 enum tree_code code = TREE_CODE (expr);
1092 tree base, obj;
1093
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));
1099
1100 if (!POINTER_TYPE_P (TREE_TYPE (expr)))
1101 return NULL_TREE;
1102
1103 switch (code)
1104 {
1105 case INTEGER_CST:
1106 return NULL_TREE;
1107
1108 case ADDR_EXPR:
1109 obj = TREE_OPERAND (expr, 0);
1110 base = get_base_address (obj);
1111
1112 if (!base)
1113 return expr;
1114
1115 if (TREE_CODE (base) == MEM_REF)
1116 return determine_base_object (TREE_OPERAND (base, 0));
1117
1118 return fold_convert (ptr_type_node,
1119 build_fold_addr_expr (base));
1120
1121 case POINTER_PLUS_EXPR:
1122 return determine_base_object (TREE_OPERAND (expr, 0));
1123
1124 case PLUS_EXPR:
1125 case MINUS_EXPR:
1126 /* Pointer addition is done solely using POINTER_PLUS_EXPR. */
1127 gcc_unreachable ();
1128
1129 default:
1130 return fold_convert (ptr_type_node, expr);
1131 }
1132}
1133
1134/* Return true if address expression with non-DECL_P operand appears
1135 in EXPR. */
1136
1137static bool
1138contain_complex_addr_expr (tree expr)
1139{
1140 bool res = false;
1141
1142 STRIP_NOPS (expr);
1143 switch (TREE_CODE (expr))
1144 {
1145 case POINTER_PLUS_EXPR:
1146 case PLUS_EXPR:
1147 case MINUS_EXPR:
1148 res |= contain_complex_addr_expr (TREE_OPERAND (expr, 0));
1149 res |= contain_complex_addr_expr (TREE_OPERAND (expr, 1));
1150 break;
1151
1152 case ADDR_EXPR:
1153 return (!DECL_P (TREE_OPERAND (expr, 0)));
1154
1155 default:
1156 return false;
1157 }
1158
1159 return res;
1160}
1161
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. */
1164
1165static struct iv *
1166alloc_iv (struct ivopts_data *data, tree base, tree step,
1167 bool no_overflow = false)
1168{
1169 tree expr = base;
1170 struct iv *iv = (struct iv*) obstack_alloc (&data->iv_obstack,
1171 sizeof (struct iv));
1172 gcc_assert (step != NULL_TREE);
1173
1174 /* Lower address expression in base except ones with DECL_P as operand.
1175 By doing this:
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. */
1179 STRIP_NOPS (expr);
1180 if ((TREE_CODE (expr) == ADDR_EXPR && !DECL_P (TREE_OPERAND (expr, 0)))
1181 || contain_complex_addr_expr (expr))
1182 {
1183 aff_tree comb;
1184 tree_to_aff_combination (expr, TREE_TYPE (expr), &comb);
1185 base = fold_convert (TREE_TYPE (base), aff_combination_to_tree (&comb));
1186 }
1187
1188 iv->base = base;
1189 iv->base_object = determine_base_object (base);
1190 iv->step = step;
1191 iv->biv_p = false;
1192 iv->nonlin_use = NULL;
1193 iv->ssa_name = NULL_TREE;
1194 if (!no_overflow
1195 && !iv_can_overflow_p (data->current_loop, TREE_TYPE (base),
1196 base, step))
1197 no_overflow = true;
1198 iv->no_overflow = no_overflow;
1199 iv->have_address_use = false;
1200
1201 return iv;
1202}
1203
1204/* Sets STEP and BASE for induction variable IV. NO_OVERFLOW implies the IV
1205 doesn't overflow. */
1206
1207static void
1208set_iv (struct ivopts_data *data, tree iv, tree base, tree step,
1209 bool no_overflow)
1210{
1211 struct version_info *info = name_info (data, iv);
1212
1213 gcc_assert (!info->iv);
1214
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;
1218}
1219
1220/* Finds induction variable declaration for VAR. */
1221
1222static struct iv *
1223get_iv (struct ivopts_data *data, tree var)
1224{
1225 basic_block bb;
1226 tree type = TREE_TYPE (var);
1227
1228 if (!POINTER_TYPE_P (type)
1229 && !INTEGRAL_TYPE_P (type))
1230 return NULL;
1231
1232 if (!name_info (data, var)->iv)
1233 {
1234 bb = gimple_bb (SSA_NAME_DEF_STMT (var));
1235
1236 if (!bb
1237 || !flow_bb_inside_loop_p (data->current_loop, bb))
1238 set_iv (data, var, var, build_int_cst (type, 0), true);
1239 }
1240
1241 return name_info (data, var)->iv;
1242}
1243
1244/* Return the first non-invariant ssa var found in EXPR. */
1245
1246static tree
1247extract_single_var_from_expr (tree expr)
1248{
1249 int i, n;
1250 tree tmp;
1251 enum tree_code code;
1252
1253 if (!expr || is_gimple_min_invariant (expr))
1254 return NULL;
1255
1256 code = TREE_CODE (expr);
1257 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
1258 {
1259 n = TREE_OPERAND_LENGTH (expr);
1260 for (i = 0; i < n; i++)
1261 {
1262 tmp = extract_single_var_from_expr (TREE_OPERAND (expr, i));
1263
1264 if (tmp)
1265 return tmp;
1266 }
1267 }
1268 return (TREE_CODE (expr) == SSA_NAME) ? expr : NULL;
1269}
1270
1271/* Finds basic ivs. */
1272
1273static bool
1274find_bivs (struct ivopts_data *data)
1275{
1276 gphi *phi;
1277 affine_iv iv;
1278 tree step, type, base, stop;
1279 bool found = false;
1280 struct loop *loop = data->current_loop;
1281 gphi_iterator psi;
1282
1283 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
1284 {
1285 phi = psi.phi ();
1286
1287 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
1288 continue;
1289
1290 if (virtual_operand_p (PHI_RESULT (phi)))
1291 continue;
1292
1293 if (!simple_iv (loop, loop, PHI_RESULT (phi), &iv, true))
1294 continue;
1295
1296 if (integer_zerop (iv.step))
1297 continue;
1298
1299 step = 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.
1304
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))
1310 continue;
1311
1312 type = TREE_TYPE (PHI_RESULT (phi));
1313 base = fold_convert (type, base);
1314 if (step)
1315 {
1316 if (POINTER_TYPE_P (type))
1317 step = convert_to_ptrofftype (step);
1318 else
1319 step = fold_convert (type, step);
1320 }
1321
1322 set_iv (data, PHI_RESULT (phi), base, step, iv.no_overflow);
1323 found = true;
1324 }
1325
1326 return found;
1327}
1328
1329/* Marks basic ivs. */
1330
1331static void
1332mark_bivs (struct ivopts_data *data)
1333{
1334 gphi *phi;
1335 gimple *def;
1336 tree var;
1337 struct iv *iv, *incr_iv;
1338 struct loop *loop = data->current_loop;
1339 basic_block incr_bb;
1340 gphi_iterator psi;
1341
1342 data->bivs_not_used_in_addr = 0;
1343 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
1344 {
1345 phi = psi.phi ();
1346
1347 iv = get_iv (data, PHI_RESULT (phi));
1348 if (!iv)
1349 continue;
1350
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. */
1354 if (def
1355 && gimple_code (def) == GIMPLE_PHI
1356 && gimple_bb (def) == loop->header)
1357 continue;
1358
1359 incr_iv = get_iv (data, var);
1360 if (!incr_iv)
1361 continue;
1362
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))
1367 continue;
1368
1369 iv->biv_p = true;
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++;
1375 }
1376}
1377
1378/* Checks whether STMT defines a linear induction variable and stores its
1379 parameters to IV. */
1380
1381static bool
1382find_givs_in_stmt_scev (struct ivopts_data *data, gimple *stmt, affine_iv *iv)
1383{
1384 tree lhs, stop;
1385 struct loop *loop = data->current_loop;
1386
1387 iv->base = NULL_TREE;
1388 iv->step = NULL_TREE;
1389
1390 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1391 return false;
1392
1393 lhs = gimple_assign_lhs (stmt);
1394 if (TREE_CODE (lhs) != SSA_NAME)
1395 return false;
1396
1397 if (!simple_iv (loop, loop_containing_stmt (stmt), lhs, iv, true))
1398 return false;
1399
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.
1403
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))
1409 return false;
1410
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))
1415 return false;
1416
1417 return true;
1418}
1419
1420/* Finds general ivs in statement STMT. */
1421
1422static void
1423find_givs_in_stmt (struct ivopts_data *data, gimple *stmt)
1424{
1425 affine_iv iv;
1426
1427 if (!find_givs_in_stmt_scev (data, stmt, &iv))
1428 return;
1429
1430 set_iv (data, gimple_assign_lhs (stmt), iv.base, iv.step, iv.no_overflow);
1431}
1432
1433/* Finds general ivs in basic block BB. */
1434
1435static void
1436find_givs_in_bb (struct ivopts_data *data, basic_block bb)
1437{
1438 gimple_stmt_iterator bsi;
1439
1440 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1441 find_givs_in_stmt (data, gsi_stmt (bsi));
1442}
1443
1444/* Finds general ivs. */
1445
1446static void
1447find_givs (struct ivopts_data *data)
1448{
1449 struct loop *loop = data->current_loop;
1450 basic_block *body = get_loop_body_in_dom_order (loop);
1451 unsigned i;
1452
1453 for (i = 0; i < loop->num_nodes; i++)
1454 find_givs_in_bb (data, body[i]);
1455 free (body);
1456}
1457
1458/* For each ssa name defined in LOOP determines whether it is an induction
1459 variable and if so, its initial value and step. */
1460
1461static bool
1462find_induction_variables (struct ivopts_data *data)
1463{
1464 unsigned i;
1465 bitmap_iterator bi;
1466
1467 if (!find_bivs (data))
1468 return false;
1469
1470 find_givs (data);
1471 mark_bivs (data);
1472
1473 if (dump_file && (dump_flags & TDF_DETAILS))
1474 {
1475 struct tree_niter_desc *niter = niter_for_single_dom_exit (data);
1476
1477 if (niter)
1478 {
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))
1482 {
1483 fprintf (dump_file, "; zero if ");
1484 print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
1485 }
1486 fprintf (dump_file, "\n");
1487 };
1488
1489 fprintf (dump_file, "\n<Induction Vars>:\n");
1490 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
1491 {
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);
1495 }
1496 }
1497
1498 return true;
1499}
1500
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. */
1505
1506static struct iv_use *
1507record_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)
1510{
1511 struct iv_use *use = XCNEW (struct iv_use);
1512
1513 use->id = group->vuses.length ();
1514 use->group_id = group->id;
1515 use->type = type;
1516 use->iv = iv;
1517 use->stmt = stmt;
1518 use->op_p = use_p;
1519 use->addr_base = addr_base;
1520 use->addr_offset = addr_offset;
1521
1522 group->vuses.safe_push (use);
1523 return use;
1524}
1525
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. */
1529
1530static void
1531record_invariant (struct ivopts_data *data, tree op, bool nonlinear_use)
1532{
1533 basic_block bb;
1534 struct version_info *info;
1535
1536 if (TREE_CODE (op) != SSA_NAME
1537 || virtual_operand_p (op))
1538 return;
1539
1540 bb = gimple_bb (SSA_NAME_DEF_STMT (op));
1541 if (bb
1542 && flow_bb_inside_loop_p (data->current_loop, bb))
1543 return;
1544
1545 info = name_info (data, op);
1546 info->name = op;
1547 info->has_nonlin_use |= nonlinear_use;
1548 if (!info->inv_id)
1549 info->inv_id = ++data->max_inv_var_id;
1550 bitmap_set_bit (data->relevant, SSA_NAME_VERSION (op));
1551}
1552
1553/* Record a group of TYPE. */
1554
1555static struct iv_group *
1556record_group (struct ivopts_data *data, enum use_type type)
1557{
1558 struct iv_group *group = XCNEW (struct iv_group);
1559
1560 group->id = data->vgroups.length ();
1561 group->type = type;
1562 group->related_cands = BITMAP_ALLOC (NULL);
1563 group->vuses.create (1);
1564
1565 data->vgroups.safe_push (group);
1566 return group;
1567}
1568
1569/* Record a use of TYPE at *USE_P in STMT whose value is IV in a group.
1570 New group will be created if there is no existing group for the use. */
1571
1572static struct iv_use *
1573record_group_use (struct ivopts_data *data, tree *use_p,
1574 struct iv *iv, gimple *stmt, enum use_type type)
1575{
1576 tree addr_base = NULL;
1577 struct iv_group *group = NULL;
1578 unsigned HOST_WIDE_INT addr_offset = 0;
1579
1580 /* Record non address type use in a new group. */
1581 if (type == USE_ADDRESS && iv->base_object)
1582 {
1583 unsigned int i;
1584
1585 addr_base = strip_offset (iv->base, &addr_offset);
1586 for (i = 0; i < data->vgroups.length (); i++)
1587 {
1588 struct iv_use *use;
1589
1590 group = data->vgroups[i];
1591 use = group->vuses[0];
1592 if (use->type != USE_ADDRESS || !use->iv->base_object)
1593 continue;
1594
1595 /* Check if it has the same stripped base and step. */
1596 if (operand_equal_p (iv->base_object, use->iv->base_object, 0)
1597 && operand_equal_p (iv->step, use->iv->step, 0)
1598 && operand_equal_p (addr_base, use->addr_base, 0))
1599 break;
1600 }
1601 if (i == data->vgroups.length ())
1602 group = NULL;
1603 }
1604
1605 if (!group)
1606 group = record_group (data, type);
1607
1608 return record_use (group, use_p, iv, stmt, type, addr_base, addr_offset);
1609}
1610
1611/* Checks whether the use OP is interesting and if so, records it. */
1612
1613static struct iv_use *
1614find_interesting_uses_op (struct ivopts_data *data, tree op)
1615{
1616 struct iv *iv;
1617 gimple *stmt;
1618 struct iv_use *use;
1619
1620 if (TREE_CODE (op) != SSA_NAME)
1621 return NULL;
1622
1623 iv = get_iv (data, op);
1624 if (!iv)
1625 return NULL;
1626
1627 if (iv->nonlin_use)
1628 {
1629 gcc_assert (iv->nonlin_use->type == USE_NONLINEAR_EXPR);
1630 return iv->nonlin_use;
1631 }
1632
1633 if (integer_zerop (iv->step))
1634 {
1635 record_invariant (data, op, true);
1636 return NULL;
1637 }
1638
1639 stmt = SSA_NAME_DEF_STMT (op);
1640 gcc_assert (gimple_code (stmt) == GIMPLE_PHI || is_gimple_assign (stmt));
1641
1642 use = record_group_use (data, NULL, iv, stmt, USE_NONLINEAR_EXPR);
1643 iv->nonlin_use = use;
1644 return use;
1645}
1646
1647/* Indicate how compare type iv_use can be handled. */
1648enum comp_iv_rewrite
1649{
1650 COMP_IV_NA,
1651 /* We may rewrite compare type iv_use by expressing value of the iv_use. */
1652 COMP_IV_EXPR,
1653 /* We may rewrite compare type iv_uses on both sides of comparison by
1654 expressing value of each iv_use. */
1655 COMP_IV_EXPR_2,
1656 /* We may rewrite compare type iv_use by expressing value of the iv_use
1657 or by eliminating it with other iv_cand. */
1658 COMP_IV_ELIM
1659};
1660
1661/* Given a condition in statement STMT, checks whether it is a compare
1662 of an induction variable and an invariant. If this is the case,
1663 CONTROL_VAR is set to location of the iv, BOUND to the location of
1664 the invariant, IV_VAR and IV_BOUND are set to the corresponding
1665 induction variable descriptions, and true is returned. If this is not
1666 the case, CONTROL_VAR and BOUND are set to the arguments of the
1667 condition and false is returned. */
1668
1669static enum comp_iv_rewrite
1670extract_cond_operands (struct ivopts_data *data, gimple *stmt,
1671 tree **control_var, tree **bound,
1672 struct iv **iv_var, struct iv **iv_bound)
1673{
1674 /* The objects returned when COND has constant operands. */
1675 static struct iv const_iv;
1676 static tree zero;
1677 tree *op0 = &zero, *op1 = &zero;
1678 struct iv *iv0 = &const_iv, *iv1 = &const_iv;
1679 enum comp_iv_rewrite rewrite_type = COMP_IV_NA;
1680
1681 if (gimple_code (stmt) == GIMPLE_COND)
1682 {
1683 gcond *cond_stmt = as_a <gcond *> (stmt);
1684 op0 = gimple_cond_lhs_ptr (cond_stmt);
1685 op1 = gimple_cond_rhs_ptr (cond_stmt);
1686 }
1687 else
1688 {
1689 op0 = gimple_assign_rhs1_ptr (stmt);
1690 op1 = gimple_assign_rhs2_ptr (stmt);
1691 }
1692
1693 zero = integer_zero_node;
1694 const_iv.step = integer_zero_node;
1695
1696 if (TREE_CODE (*op0) == SSA_NAME)
1697 iv0 = get_iv (data, *op0);
1698 if (TREE_CODE (*op1) == SSA_NAME)
1699 iv1 = get_iv (data, *op1);
1700
1701 /* If both sides of comparison are IVs. We can express ivs on both end. */
1702 if (iv0 && iv1 && !integer_zerop (iv0->step) && !integer_zerop (iv1->step))
1703 {
1704 rewrite_type = COMP_IV_EXPR_2;
1705 goto end;
1706 }
1707
1708 /* If none side of comparison is IV. */
1709 if ((!iv0 || integer_zerop (iv0->step))
1710 && (!iv1 || integer_zerop (iv1->step)))
1711 goto end;
1712
1713 /* Control variable may be on the other side. */
1714 if (!iv0 || integer_zerop (iv0->step))
1715 {
1716 std::swap (op0, op1);
1717 std::swap (iv0, iv1);
1718 }
1719 /* If one side is IV and the other side isn't loop invariant. */
1720 if (!iv1)
1721 rewrite_type = COMP_IV_EXPR;
1722 /* If one side is IV and the other side is loop invariant. */
1723 else if (!integer_zerop (iv0->step) && integer_zerop (iv1->step))
1724 rewrite_type = COMP_IV_ELIM;
1725
1726end:
1727 if (control_var)
1728 *control_var = op0;
1729 if (iv_var)
1730 *iv_var = iv0;
1731 if (bound)
1732 *bound = op1;
1733 if (iv_bound)
1734 *iv_bound = iv1;
1735
1736 return rewrite_type;
1737}
1738
1739/* Checks whether the condition in STMT is interesting and if so,
1740 records it. */
1741
1742static void
1743find_interesting_uses_cond (struct ivopts_data *data, gimple *stmt)
1744{
1745 tree *var_p, *bound_p;
1746 struct iv *var_iv, *bound_iv;
1747 enum comp_iv_rewrite ret;
1748
1749 ret = extract_cond_operands (data, stmt,
1750 &var_p, &bound_p, &var_iv, &bound_iv);
1751 if (ret == COMP_IV_NA)
1752 {
1753 find_interesting_uses_op (data, *var_p);
1754 find_interesting_uses_op (data, *bound_p);
1755 return;
1756 }
1757
1758 record_group_use (data, var_p, var_iv, stmt, USE_COMPARE);
1759 /* Record compare type iv_use for iv on the other side of comparison. */
1760 if (ret == COMP_IV_EXPR_2)
1761 record_group_use (data, bound_p, bound_iv, stmt, USE_COMPARE);
1762}
1763
1764/* Returns the outermost loop EXPR is obviously invariant in
1765 relative to the loop LOOP, i.e. if all its operands are defined
1766 outside of the returned loop. Returns NULL if EXPR is not
1767 even obviously invariant in LOOP. */
1768
1769struct loop *
1770outermost_invariant_loop_for_expr (struct loop *loop, tree expr)
1771{
1772 basic_block def_bb;
1773 unsigned i, len;
1774
1775 if (is_gimple_min_invariant (expr))
1776 return current_loops->tree_root;
1777
1778 if (TREE_CODE (expr) == SSA_NAME)
1779 {
1780 def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
1781 if (def_bb)
1782 {
1783 if (flow_bb_inside_loop_p (loop, def_bb))
1784 return NULL;
1785 return superloop_at_depth (loop,
1786 loop_depth (def_bb->loop_father) + 1);
1787 }
1788
1789 return current_loops->tree_root;
1790 }
1791
1792 if (!EXPR_P (expr))
1793 return NULL;
1794
1795 unsigned maxdepth = 0;
1796 len = TREE_OPERAND_LENGTH (expr);
1797 for (i = 0; i < len; i++)
1798 {
1799 struct loop *ivloop;
1800 if (!TREE_OPERAND (expr, i))
1801 continue;
1802
1803 ivloop = outermost_invariant_loop_for_expr (loop, TREE_OPERAND (expr, i));
1804 if (!ivloop)
1805 return NULL;
1806 maxdepth = MAX (maxdepth, loop_depth (ivloop));
1807 }
1808
1809 return superloop_at_depth (loop, maxdepth);
1810}
1811
1812/* Returns true if expression EXPR is obviously invariant in LOOP,
1813 i.e. if all its operands are defined outside of the LOOP. LOOP
1814 should not be the function body. */
1815
1816bool
1817expr_invariant_in_loop_p (struct loop *loop, tree expr)
1818{
1819 basic_block def_bb;
1820 unsigned i, len;
1821
1822 gcc_assert (loop_depth (loop) > 0);
1823
1824 if (is_gimple_min_invariant (expr))
1825 return true;
1826
1827 if (TREE_CODE (expr) == SSA_NAME)
1828 {
1829 def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
1830 if (def_bb
1831 && flow_bb_inside_loop_p (loop, def_bb))
1832 return false;
1833
1834 return true;
1835 }
1836
1837 if (!EXPR_P (expr))
1838 return false;
1839
1840 len = TREE_OPERAND_LENGTH (expr);
1841 for (i = 0; i < len; i++)
1842 if (TREE_OPERAND (expr, i)
1843 && !expr_invariant_in_loop_p (loop, TREE_OPERAND (expr, i)))
1844 return false;
1845
1846 return true;
1847}
1848
1849/* Given expression EXPR which computes inductive values with respect
1850 to loop recorded in DATA, this function returns biv from which EXPR
1851 is derived by tracing definition chains of ssa variables in EXPR. */
1852
1853static struct iv*
1854find_deriving_biv_for_expr (struct ivopts_data *data, tree expr)
1855{
1856 struct iv *iv;
1857 unsigned i, n;
1858 tree e2, e1;
1859 enum tree_code code;
1860 gimple *stmt;
1861
1862 if (expr == NULL_TREE)
1863 return NULL;
1864
1865 if (is_gimple_min_invariant (expr))
1866 return NULL;
1867
1868 code = TREE_CODE (expr);
1869 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
1870 {
1871 n = TREE_OPERAND_LENGTH (expr);
1872 for (i = 0; i < n; i++)
1873 {
1874 iv = find_deriving_biv_for_expr (data, TREE_OPERAND (expr, i));
1875 if (iv)
1876 return iv;
1877 }
1878 }
1879
1880 /* Stop if it's not ssa name. */
1881 if (code != SSA_NAME)
1882 return NULL;
1883
1884 iv = get_iv (data, expr);
1885 if (!iv || integer_zerop (iv->step))
1886 return NULL;
1887 else if (iv->biv_p)
1888 return iv;
1889
1890 stmt = SSA_NAME_DEF_STMT (expr);
1891 if (gphi *phi = dyn_cast <gphi *> (stmt))
1892 {
1893 ssa_op_iter iter;
1894 use_operand_p use_p;
1895 basic_block phi_bb = gimple_bb (phi);
1896
1897 /* Skip loop header PHI that doesn't define biv. */
1898 if (phi_bb->loop_father == data->current_loop)
1899 return NULL;
1900
1901 if (virtual_operand_p (gimple_phi_result (phi)))
1902 return NULL;
1903
1904 FOR_EACH_PHI_ARG (use_p, phi, iter, SSA_OP_USE)
1905 {
1906 tree use = USE_FROM_PTR (use_p);
1907 iv = find_deriving_biv_for_expr (data, use);
1908 if (iv)
1909 return iv;
1910 }
1911 return NULL;
1912 }
1913 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1914 return NULL;
1915
1916 e1 = gimple_assign_rhs1 (stmt);
1917 code = gimple_assign_rhs_code (stmt);
1918 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1919 return find_deriving_biv_for_expr (data, e1);
1920
1921 switch (code)
1922 {
1923 case MULT_EXPR:
1924 case PLUS_EXPR:
1925 case MINUS_EXPR:
1926 case POINTER_PLUS_EXPR:
1927 /* Increments, decrements and multiplications by a constant
1928 are simple. */
1929 e2 = gimple_assign_rhs2 (stmt);
1930 iv = find_deriving_biv_for_expr (data, e2);
1931 if (iv)
1932 return iv;
1933 gcc_fallthrough ();
1934
1935 CASE_CONVERT:
1936 /* Casts are simple. */
1937 return find_deriving_biv_for_expr (data, e1);
1938
1939 default:
1940 break;
1941 }
1942
1943 return NULL;
1944}
1945
1946/* Record BIV, its predecessor and successor that they are used in
1947 address type uses. */
1948
1949static void
1950record_biv_for_address_use (struct ivopts_data *data, struct iv *biv)
1951{
1952 unsigned i;
1953 tree type, base_1, base_2;
1954 bitmap_iterator bi;
1955
1956 if (!biv || !biv->biv_p || integer_zerop (biv->step)
1957 || biv->have_address_use || !biv->no_overflow)
1958 return;
1959
1960 type = TREE_TYPE (biv->base);
1961 if (!INTEGRAL_TYPE_P (type))
1962 return;
1963
1964 biv->have_address_use = true;
1965 data->bivs_not_used_in_addr--;
1966 base_1 = fold_build2 (PLUS_EXPR, type, biv->base, biv->step);
1967 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
1968 {
1969 struct iv *iv = ver_info (data, i)->iv;
1970
1971 if (!iv || !iv->biv_p || integer_zerop (iv->step)
1972 || iv->have_address_use || !iv->no_overflow)
1973 continue;
1974
1975 if (type != TREE_TYPE (iv->base)
1976 || !INTEGRAL_TYPE_P (TREE_TYPE (iv->base)))
1977 continue;
1978
1979 if (!operand_equal_p (biv->step, iv->step, 0))
1980 continue;
1981
1982 base_2 = fold_build2 (PLUS_EXPR, type, iv->base, iv->step);
1983 if (operand_equal_p (base_1, iv->base, 0)
1984 || operand_equal_p (base_2, biv->base, 0))
1985 {
1986 iv->have_address_use = true;
1987 data->bivs_not_used_in_addr--;
1988 }
1989 }
1990}
1991
1992/* Cumulates the steps of indices into DATA and replaces their values with the
1993 initial ones. Returns false when the value of the index cannot be determined.
1994 Callback for for_each_index. */
1995
1996struct ifs_ivopts_data
1997{
1998 struct ivopts_data *ivopts_data;
1999 gimple *stmt;
2000 tree step;
2001};
2002
2003static bool
2004idx_find_step (tree base, tree *idx, void *data)
2005{
2006 struct ifs_ivopts_data *dta = (struct ifs_ivopts_data *) data;
2007 struct iv *iv;
2008 bool use_overflow_semantics = false;
2009 tree step, iv_base, iv_step, lbound, off;
2010 struct loop *loop = dta->ivopts_data->current_loop;
2011
2012 /* If base is a component ref, require that the offset of the reference
2013 be invariant. */
2014 if (TREE_CODE (base) == COMPONENT_REF)
2015 {
2016 off = component_ref_field_offset (base);
2017 return expr_invariant_in_loop_p (loop, off);
2018 }
2019
2020 /* If base is array, first check whether we will be able to move the
2021 reference out of the loop (in order to take its address in strength
2022 reduction). In order for this to work we need both lower bound
2023 and step to be loop invariants. */
2024 if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
2025 {
2026 /* Moreover, for a range, the size needs to be invariant as well. */
2027 if (TREE_CODE (base) == ARRAY_RANGE_REF
2028 && !expr_invariant_in_loop_p (loop, TYPE_SIZE (TREE_TYPE (base))))
2029 return false;
2030
2031 step = array_ref_element_size (base);
2032 lbound = array_ref_low_bound (base);
2033
2034 if (!expr_invariant_in_loop_p (loop, step)
2035 || !expr_invariant_in_loop_p (loop, lbound))
2036 return false;
2037 }
2038
2039 if (TREE_CODE (*idx) != SSA_NAME)
2040 return true;
2041
2042 iv = get_iv (dta->ivopts_data, *idx);
2043 if (!iv)
2044 return false;
2045
2046 /* XXX We produce for a base of *D42 with iv->base being &x[0]
2047 *&x[0], which is not folded and does not trigger the
2048 ARRAY_REF path below. */
2049 *idx = iv->base;
2050
2051 if (integer_zerop (iv->step))
2052 return true;
2053
2054 if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
2055 {
2056 step = array_ref_element_size (base);
2057
2058 /* We only handle addresses whose step is an integer constant. */
2059 if (TREE_CODE (step) != INTEGER_CST)
2060 return false;
2061 }
2062 else
2063 /* The step for pointer arithmetics already is 1 byte. */
2064 step = size_one_node;
2065
2066 iv_base = iv->base;
2067 iv_step = iv->step;
2068 if (iv->no_overflow && nowrap_type_p (TREE_TYPE (iv_step)))
2069 use_overflow_semantics = true;
2070
2071 if (!convert_affine_scev (dta->ivopts_data->current_loop,
2072 sizetype, &iv_base, &iv_step, dta->stmt,
2073 use_overflow_semantics))
2074 {
2075 /* The index might wrap. */
2076 return false;
2077 }
2078
2079 step = fold_build2 (MULT_EXPR, sizetype, step, iv_step);
2080 dta->step = fold_build2 (PLUS_EXPR, sizetype, dta->step, step);
2081
2082 if (dta->ivopts_data->bivs_not_used_in_addr)
2083 {
2084 if (!iv->biv_p)
2085 iv = find_deriving_biv_for_expr (dta->ivopts_data, iv->ssa_name);
2086
2087 record_biv_for_address_use (dta->ivopts_data, iv);
2088 }
2089 return true;
2090}
2091
2092/* Records use in index IDX. Callback for for_each_index. Ivopts data
2093 object is passed to it in DATA. */
2094
2095static bool
2096idx_record_use (tree base, tree *idx,
2097 void *vdata)
2098{
2099 struct ivopts_data *data = (struct ivopts_data *) vdata;
2100 find_interesting_uses_op (data, *idx);
2101 if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
2102 {
2103 find_interesting_uses_op (data, array_ref_element_size (base));
2104 find_interesting_uses_op (data, array_ref_low_bound (base));
2105 }
2106 return true;
2107}
2108
2109/* If we can prove that TOP = cst * BOT for some constant cst,
2110 store cst to MUL and return true. Otherwise return false.
2111 The returned value is always sign-extended, regardless of the
2112 signedness of TOP and BOT. */
2113
2114static bool
2115constant_multiple_of (tree top, tree bot, widest_int *mul)
2116{
2117 tree mby;
2118 enum tree_code code;
2119 unsigned precision = TYPE_PRECISION (TREE_TYPE (top));
2120 widest_int res, p0, p1;
2121
2122 STRIP_NOPS (top);
2123 STRIP_NOPS (bot);
2124
2125 if (operand_equal_p (top, bot, 0))
2126 {
2127 *mul = 1;
2128 return true;
2129 }
2130
2131 code = TREE_CODE (top);
2132 switch (code)
2133 {
2134 case MULT_EXPR:
2135 mby = TREE_OPERAND (top, 1);
2136 if (TREE_CODE (mby) != INTEGER_CST)
2137 return false;
2138
2139 if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &res))
2140 return false;
2141
2142 *mul = wi::sext (res * wi::to_widest (mby), precision);
2143 return true;
2144
2145 case PLUS_EXPR:
2146 case MINUS_EXPR:
2147 if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &p0)
2148 || !constant_multiple_of (TREE_OPERAND (top, 1), bot, &p1))
2149 return false;
2150
2151 if (code == MINUS_EXPR)
2152 p1 = -p1;
2153 *mul = wi::sext (p0 + p1, precision);
2154 return true;
2155
2156 case INTEGER_CST:
2157 if (TREE_CODE (bot) != INTEGER_CST)
2158 return false;
2159
2160 p0 = widest_int::from (wi::to_wide (top), SIGNED);
2161 p1 = widest_int::from (wi::to_wide (bot), SIGNED);
2162 if (p1 == 0)
2163 return false;
2164 *mul = wi::sext (wi::divmod_trunc (p0, p1, SIGNED, &res), precision);
2165 return res == 0;
2166
2167 default:
2168 return false;
2169 }
2170}
2171
2172/* Return true if memory reference REF with step STEP may be unaligned. */
2173
2174static bool
2175may_be_unaligned_p (tree ref, tree step)
2176{
2177 /* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
2178 thus they are not misaligned. */
2179 if (TREE_CODE (ref) == TARGET_MEM_REF)
2180 return false;
2181
2182 unsigned int align = TYPE_ALIGN (TREE_TYPE (ref));
2183 if (GET_MODE_ALIGNMENT (TYPE_MODE (TREE_TYPE (ref))) > align)
2184 align = GET_MODE_ALIGNMENT (TYPE_MODE (TREE_TYPE (ref)));
2185
2186 unsigned HOST_WIDE_INT bitpos;
2187 unsigned int ref_align;
2188 get_object_alignment_1 (ref, &ref_align, &bitpos);
2189 if (ref_align < align
2190 || (bitpos % align) != 0
2191 || (bitpos % BITS_PER_UNIT) != 0)
2192 return true;
2193
2194 unsigned int trailing_zeros = tree_ctz (step);
2195 if (trailing_zeros < HOST_BITS_PER_INT
2196 && (1U << trailing_zeros) * BITS_PER_UNIT < align)
2197 return true;
2198
2199 return false;
2200}
2201
2202/* Return true if EXPR may be non-addressable. */
2203
2204bool
2205may_be_nonaddressable_p (tree expr)
2206{
2207 switch (TREE_CODE (expr))
2208 {
2209 case TARGET_MEM_REF:
2210 /* TARGET_MEM_REFs are translated directly to valid MEMs on the
2211 target, thus they are always addressable. */
2212 return false;
2213
2214 case MEM_REF:
2215 /* Likewise for MEM_REFs, modulo the storage order. */
2216 return REF_REVERSE_STORAGE_ORDER (expr);
2217
2218 case BIT_FIELD_REF:
2219 if (REF_REVERSE_STORAGE_ORDER (expr))
2220 return true;
2221 return may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
2222
2223 case COMPONENT_REF:
2224 if (TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (TREE_OPERAND (expr, 0))))
2225 return true;
2226 return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr, 1))
2227 || may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
2228
2229 case ARRAY_REF:
2230 case ARRAY_RANGE_REF:
2231 if (TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (TREE_OPERAND (expr, 0))))
2232 return true;
2233 return may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
2234
2235 case VIEW_CONVERT_EXPR:
2236 /* This kind of view-conversions may wrap non-addressable objects
2237 and make them look addressable. After some processing the
2238 non-addressability may be uncovered again, causing ADDR_EXPRs
2239 of inappropriate objects to be built. */
2240 if (is_gimple_reg (TREE_OPERAND (expr, 0))
2241 || !is_gimple_addressable (TREE_OPERAND (expr, 0)))
2242 return true;
2243 return may_be_nonaddressable_p (TREE_OPERAND (expr, 0));
2244
2245 CASE_CONVERT:
2246 return true;
2247
2248 default:
2249 break;
2250 }
2251
2252 return false;
2253}
2254
2255/* Finds addresses in *OP_P inside STMT. */
2256
2257static void
2258find_interesting_uses_address (struct ivopts_data *data, gimple *stmt,
2259 tree *op_p)
2260{
2261 tree base = *op_p, step = size_zero_node;
2262 struct iv *civ;
2263 struct ifs_ivopts_data ifs_ivopts_data;
2264
2265 /* Do not play with volatile memory references. A bit too conservative,
2266 perhaps, but safe. */
2267 if (gimple_has_volatile_ops (stmt))
2268 goto fail;
2269
2270 /* Ignore bitfields for now. Not really something terribly complicated
2271 to handle. TODO. */
2272 if (TREE_CODE (base) == BIT_FIELD_REF)
2273 goto fail;
2274
2275 base = unshare_expr (base);
2276
2277 if (TREE_CODE (base) == TARGET_MEM_REF)
2278 {
2279 tree type = build_pointer_type (TREE_TYPE (base));
2280 tree astep;
2281
2282 if (TMR_BASE (base)
2283 && TREE_CODE (TMR_BASE (base)) == SSA_NAME)
2284 {
2285 civ = get_iv (data, TMR_BASE (base));
2286 if (!civ)
2287 goto fail;
2288
2289 TMR_BASE (base) = civ->base;
2290 step = civ->step;
2291 }
2292 if (TMR_INDEX2 (base)
2293 && TREE_CODE (TMR_INDEX2 (base)) == SSA_NAME)
2294 {
2295 civ = get_iv (data, TMR_INDEX2 (base));
2296 if (!civ)
2297 goto fail;
2298
2299 TMR_INDEX2 (base) = civ->base;
2300 step = civ->step;
2301 }
2302 if (TMR_INDEX (base)
2303 && TREE_CODE (TMR_INDEX (base)) == SSA_NAME)
2304 {
2305 civ = get_iv (data, TMR_INDEX (base));
2306 if (!civ)
2307 goto fail;
2308
2309 TMR_INDEX (base) = civ->base;
2310 astep = civ->step;
2311
2312 if (astep)
2313 {
2314 if (TMR_STEP (base))
2315 astep = fold_build2 (MULT_EXPR, type, TMR_STEP (base), astep);
2316
2317 step = fold_build2 (PLUS_EXPR, type, step, astep);
2318 }
2319 }
2320
2321 if (integer_zerop (step))
2322 goto fail;
2323 base = tree_mem_ref_addr (type, base);
2324 }
2325 else
2326 {
2327 ifs_ivopts_data.ivopts_data = data;
2328 ifs_ivopts_data.stmt = stmt;
2329 ifs_ivopts_data.step = size_zero_node;
2330 if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
2331 || integer_zerop (ifs_ivopts_data.step))
2332 goto fail;
2333 step = ifs_ivopts_data.step;
2334
2335 /* Check that the base expression is addressable. This needs
2336 to be done after substituting bases of IVs into it. */
2337 if (may_be_nonaddressable_p (base))
2338 goto fail;
2339
2340 /* Moreover, on strict alignment platforms, check that it is
2341 sufficiently aligned. */
2342 if (STRICT_ALIGNMENT && may_be_unaligned_p (base, step))
2343 goto fail;
2344
2345 base = build_fold_addr_expr (base);
2346
2347 /* Substituting bases of IVs into the base expression might
2348 have caused folding opportunities. */
2349 if (TREE_CODE (base) == ADDR_EXPR)
2350 {
2351 tree *ref = &TREE_OPERAND (base, 0);
2352 while (handled_component_p (*ref))
2353 ref = &TREE_OPERAND (*ref, 0);
2354 if (TREE_CODE (*ref) == MEM_REF)
2355 {
2356 tree tem = fold_binary (MEM_REF, TREE_TYPE (*ref),
2357 TREE_OPERAND (*ref, 0),
2358 TREE_OPERAND (*ref, 1));
2359 if (tem)
2360 *ref = tem;
2361 }
2362 }
2363 }
2364
2365 civ = alloc_iv (data, base, step);
2366 /* Fail if base object of this memory reference is unknown. */
2367 if (civ->base_object == NULL_TREE)
2368 goto fail;
2369
2370 record_group_use (data, op_p, civ, stmt, USE_ADDRESS);
2371 return;
2372
2373fail:
2374 for_each_index (op_p, idx_record_use, data);
2375}
2376
2377/* Finds and records invariants used in STMT. */
2378
2379static void
2380find_invariants_stmt (struct ivopts_data *data, gimple *stmt)
2381{
2382 ssa_op_iter iter;
2383 use_operand_p use_p;
2384 tree op;
2385
2386 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2387 {
2388 op = USE_FROM_PTR (use_p);
2389 record_invariant (data, op, false);
2390 }
2391}
2392
2393/* Finds interesting uses of induction variables in the statement STMT. */
2394
2395static void
2396find_interesting_uses_stmt (struct ivopts_data *data, gimple *stmt)
2397{
2398 struct iv *iv;
2399 tree op, *lhs, *rhs;
2400 ssa_op_iter iter;
2401 use_operand_p use_p;
2402 enum tree_code code;
2403
2404 find_invariants_stmt (data, stmt);
2405
2406 if (gimple_code (stmt) == GIMPLE_COND)
2407 {
2408 find_interesting_uses_cond (data, stmt);
2409 return;
2410 }
2411
2412 if (is_gimple_assign (stmt))
2413 {
2414 lhs = gimple_assign_lhs_ptr (stmt);
2415 rhs = gimple_assign_rhs1_ptr (stmt);
2416
2417 if (TREE_CODE (*lhs) == SSA_NAME)
2418 {
2419 /* If the statement defines an induction variable, the uses are not
2420 interesting by themselves. */
2421
2422 iv = get_iv (data, *lhs);
2423
2424 if (iv && !integer_zerop (iv->step))
2425 return;
2426 }
2427
2428 code = gimple_assign_rhs_code (stmt);
2429 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
2430 && (REFERENCE_CLASS_P (*rhs)
2431 || is_gimple_val (*rhs)))
2432 {
2433 if (REFERENCE_CLASS_P (*rhs))
2434 find_interesting_uses_address (data, stmt, rhs);
2435 else
2436 find_interesting_uses_op (data, *rhs);
2437
2438 if (REFERENCE_CLASS_P (*lhs))
2439 find_interesting_uses_address (data, stmt, lhs);
2440 return;
2441 }
2442 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2443 {
2444 find_interesting_uses_cond (data, stmt);
2445 return;
2446 }
2447
2448 /* TODO -- we should also handle address uses of type
2449
2450 memory = call (whatever);
2451
2452 and
2453
2454 call (memory). */
2455 }
2456
2457 if (gimple_code (stmt) == GIMPLE_PHI
2458 && gimple_bb (stmt) == data->current_loop->header)
2459 {
2460 iv = get_iv (data, PHI_RESULT (stmt));
2461
2462 if (iv && !integer_zerop (iv->step))
2463 return;
2464 }
2465
2466 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2467 {
2468 op = USE_FROM_PTR (use_p);
2469
2470 if (TREE_CODE (op) != SSA_NAME)
2471 continue;
2472
2473 iv = get_iv (data, op);
2474 if (!iv)
2475 continue;
2476
2477 find_interesting_uses_op (data, op);
2478 }
2479}
2480
2481/* Finds interesting uses of induction variables outside of loops
2482 on loop exit edge EXIT. */
2483
2484static void
2485find_interesting_uses_outside (struct ivopts_data *data, edge exit)
2486{
2487 gphi *phi;
2488 gphi_iterator psi;
2489 tree def;
2490
2491 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2492 {
2493 phi = psi.phi ();
2494 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
2495 if (!virtual_operand_p (def))
2496 find_interesting_uses_op (data, def);
2497 }
2498}
2499
2500/* Return TRUE if OFFSET is within the range of [base + offset] addressing
2501 mode for memory reference represented by USE. */
2502
2503static GTY (()) vec<rtx, va_gc> *addr_list;
2504
2505static bool
2506addr_offset_valid_p (struct iv_use *use, HOST_WIDE_INT offset)
2507{
2508 rtx reg, addr;
2509 unsigned list_index;
2510 addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (use->iv->base));
2511 machine_mode addr_mode, mem_mode = TYPE_MODE (TREE_TYPE (*use->op_p));
2512
2513 list_index = (unsigned) as * MAX_MACHINE_MODE + (unsigned) mem_mode;
2514 if (list_index >= vec_safe_length (addr_list))
2515 vec_safe_grow_cleared (addr_list, list_index + MAX_MACHINE_MODE);
2516
2517 addr = (*addr_list)[list_index];
2518 if (!addr)
2519 {
2520 addr_mode = targetm.addr_space.address_mode (as);
2521 reg = gen_raw_REG (addr_mode, LAST_VIRTUAL_REGISTER + 1);
2522 addr = gen_rtx_fmt_ee (PLUS, addr_mode, reg, NULL_RTX);
2523 (*addr_list)[list_index] = addr;
2524 }
2525 else
2526 addr_mode = GET_MODE (addr);
2527
2528 XEXP (addr, 1) = gen_int_mode (offset, addr_mode);
2529 return (memory_address_addr_space_p (mem_mode, addr, as));
2530}
2531
2532/* Comparison function to sort group in ascending order of addr_offset. */
2533
2534static int
2535group_compare_offset (const void *a, const void *b)
2536{
2537 const struct iv_use *const *u1 = (const struct iv_use *const *) a;
2538 const struct iv_use *const *u2 = (const struct iv_use *const *) b;
2539
2540 if ((*u1)->addr_offset != (*u2)->addr_offset)
2541 return (*u1)->addr_offset < (*u2)->addr_offset ? -1 : 1;
2542 else
2543 return 0;
2544}
2545
2546/* Check if small groups should be split. Return true if no group
2547 contains more than two uses with distinct addr_offsets. Return
2548 false otherwise. We want to split such groups because:
2549
2550 1) Small groups don't have much benefit and may interfer with
2551 general candidate selection.
2552 2) Size for problem with only small groups is usually small and
2553 general algorithm can handle it well.
2554
2555 TODO -- Above claim may not hold when we want to merge memory
2556 accesses with conseuctive addresses. */
2557
2558static bool
2559split_small_address_groups_p (struct ivopts_data *data)
2560{
2561 unsigned int i, j, distinct = 1;
2562 struct iv_use *pre;
2563 struct iv_group *group;
2564
2565 for (i = 0; i < data->vgroups.length (); i++)
2566 {
2567 group = data->vgroups[i];
2568 if (group->vuses.length () == 1)
2569 continue;
2570
2571 gcc_assert (group->type == USE_ADDRESS);
2572 if (group->vuses.length () == 2)
2573 {
2574 if (group->vuses[0]->addr_offset > group->vuses[1]->addr_offset)
2575 std::swap (group->vuses[0], group->vuses[1]);
2576 }
2577 else
2578 group->vuses.qsort (group_compare_offset);
2579
2580 if (distinct > 2)
2581 continue;
2582
2583 distinct = 1;
2584 for (pre = group->vuses[0], j = 1; j < group->vuses.length (); j++)
2585 {
2586 if (group->vuses[j]->addr_offset != pre->addr_offset)
2587 {
2588 pre = group->vuses[j];
2589 distinct++;
2590 }
2591
2592 if (distinct > 2)
2593 break;
2594 }
2595 }
2596
2597 return (distinct <= 2);
2598}
2599
2600/* For each group of address type uses, this function further groups
2601 these uses according to the maximum offset supported by target's
2602 [base + offset] addressing mode. */
2603
2604static void
2605split_address_groups (struct ivopts_data *data)
2606{
2607 unsigned int i, j;
2608 /* Always split group. */
2609 bool split_p = split_small_address_groups_p (data);
2610
2611 for (i = 0; i < data->vgroups.length (); i++)
2612 {
2613 struct iv_group *new_group = NULL;
2614 struct iv_group *group = data->vgroups[i];
2615 struct iv_use *use = group->vuses[0];
2616
2617 use->id = 0;
2618 use->group_id = group->id;
2619 if (group->vuses.length () == 1)
2620 continue;
2621
2622 gcc_assert (group->type == USE_ADDRESS);
2623
2624 for (j = 1; j < group->vuses.length ();)
2625 {
2626 struct iv_use *next = group->vuses[j];
2627 HOST_WIDE_INT offset = next->addr_offset - use->addr_offset;
2628
2629 /* Split group if aksed to, or the offset against the first
2630 use can't fit in offset part of addressing mode. IV uses
2631 having the same offset are still kept in one group. */
2632 if (offset != 0 &&
2633 (split_p || !addr_offset_valid_p (use, offset)))
2634 {
2635 if (!new_group)
2636 new_group = record_group (data, group->type);
2637 group->vuses.ordered_remove (j);
2638 new_group->vuses.safe_push (next);
2639 continue;
2640 }
2641
2642 next->id = j;
2643 next->group_id = group->id;
2644 j++;
2645 }
2646 }
2647}
2648
2649/* Finds uses of the induction variables that are interesting. */
2650
2651static void
2652find_interesting_uses (struct ivopts_data *data)
2653{
2654 basic_block bb;
2655 gimple_stmt_iterator bsi;
2656 basic_block *body = get_loop_body (data->current_loop);
2657 unsigned i;
2658 edge e;
2659
2660 for (i = 0; i < data->current_loop->num_nodes; i++)
2661 {
2662 edge_iterator ei;
2663 bb = body[i];
2664
2665 FOR_EACH_EDGE (e, ei, bb->succs)
2666 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
2667 && !flow_bb_inside_loop_p (data->current_loop, e->dest))
2668 find_interesting_uses_outside (data, e);
2669
2670 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2671 find_interesting_uses_stmt (data, gsi_stmt (bsi));
2672 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2673 if (!is_gimple_debug (gsi_stmt (bsi)))
2674 find_interesting_uses_stmt (data, gsi_stmt (bsi));
2675 }
2676 free (body);
2677
2678 split_address_groups (data);
2679
2680 if (dump_file && (dump_flags & TDF_DETAILS))
2681 {
2682 fprintf (dump_file, "\n<IV Groups>:\n");
2683 dump_groups (dump_file, data);
2684 fprintf (dump_file, "\n");
2685 }
2686}
2687
2688/* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
2689 is true, assume we are inside an address. If TOP_COMPREF is true, assume
2690 we are at the top-level of the processed address. */
2691
2692static tree
2693strip_offset_1 (tree expr, bool inside_addr, bool top_compref,
2694 HOST_WIDE_INT *offset)
2695{
2696 tree op0 = NULL_TREE, op1 = NULL_TREE, tmp, step;
2697 enum tree_code code;
2698 tree type, orig_type = TREE_TYPE (expr);
2699 HOST_WIDE_INT off0, off1, st;
2700 tree orig_expr = expr;
2701
2702 STRIP_NOPS (expr);
2703
2704 type = TREE_TYPE (expr);
2705 code = TREE_CODE (expr);
2706 *offset = 0;
2707
2708 switch (code)
2709 {
2710 case INTEGER_CST:
2711 if (!cst_and_fits_in_hwi (expr)
2712 || integer_zerop (expr))
2713 return orig_expr;
2714
2715 *offset = int_cst_value (expr);
2716 return build_int_cst (orig_type, 0);
2717
2718 case POINTER_PLUS_EXPR:
2719 case PLUS_EXPR:
2720 case MINUS_EXPR:
2721 op0 = TREE_OPERAND (expr, 0);
2722 op1 = TREE_OPERAND (expr, 1);
2723
2724 op0 = strip_offset_1 (op0, false, false, &off0);
2725 op1 = strip_offset_1 (op1, false, false, &off1);
2726
2727 *offset = (code == MINUS_EXPR ? off0 - off1 : off0 + off1);
2728 if (op0 == TREE_OPERAND (expr, 0)
2729 && op1 == TREE_OPERAND (expr, 1))
2730 return orig_expr;
2731
2732 if (integer_zerop (op1))
2733 expr = op0;
2734 else if (integer_zerop (op0))
2735 {
2736 if (code == MINUS_EXPR)
2737 expr = fold_build1 (NEGATE_EXPR, type, op1);
2738 else
2739 expr = op1;
2740 }
2741 else
2742 expr = fold_build2 (code, type, op0, op1);
2743
2744 return fold_convert (orig_type, expr);
2745
2746 case MULT_EXPR:
2747 op1 = TREE_OPERAND (expr, 1);
2748 if (!cst_and_fits_in_hwi (op1))
2749 return orig_expr;
2750
2751 op0 = TREE_OPERAND (expr, 0);
2752 op0 = strip_offset_1 (op0, false, false, &off0);
2753 if (op0 == TREE_OPERAND (expr, 0))
2754 return orig_expr;
2755
2756 *offset = off0 * int_cst_value (op1);
2757 if (integer_zerop (op0))
2758 expr = op0;
2759 else
2760 expr = fold_build2 (MULT_EXPR, type, op0, op1);
2761
2762 return fold_convert (orig_type, expr);
2763
2764 case ARRAY_REF:
2765 case ARRAY_RANGE_REF:
2766 if (!inside_addr)
2767 return orig_expr;
2768
2769 step = array_ref_element_size (expr);
2770 if (!cst_and_fits_in_hwi (step))
2771 break;
2772
2773 st = int_cst_value (step);
2774 op1 = TREE_OPERAND (expr, 1);
2775 op1 = strip_offset_1 (op1, false, false, &off1);
2776 *offset = off1 * st;
2777
2778 if (top_compref
2779 && integer_zerop (op1))
2780 {
2781 /* Strip the component reference completely. */
2782 op0 = TREE_OPERAND (expr, 0);
2783 op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
2784 *offset += off0;
2785 return op0;
2786 }
2787 break;
2788
2789 case COMPONENT_REF:
2790 {
2791 tree field;
2792
2793 if (!inside_addr)
2794 return orig_expr;
2795
2796 tmp = component_ref_field_offset (expr);
2797 field = TREE_OPERAND (expr, 1);
2798 if (top_compref
2799 && cst_and_fits_in_hwi (tmp)
2800 && cst_and_fits_in_hwi (DECL_FIELD_BIT_OFFSET (field)))
2801 {
2802 HOST_WIDE_INT boffset, abs_off;
2803
2804 /* Strip the component reference completely. */
2805 op0 = TREE_OPERAND (expr, 0);
2806 op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
2807 boffset = int_cst_value (DECL_FIELD_BIT_OFFSET (field));
2808 abs_off = abs_hwi (boffset) / BITS_PER_UNIT;
2809 if (boffset < 0)
2810 abs_off = -abs_off;
2811
2812 *offset = off0 + int_cst_value (tmp) + abs_off;
2813 return op0;
2814 }
2815 }
2816 break;
2817
2818 case ADDR_EXPR:
2819 op0 = TREE_OPERAND (expr, 0);
2820 op0 = strip_offset_1 (op0, true, true, &off0);
2821 *offset += off0;
2822
2823 if (op0 == TREE_OPERAND (expr, 0))
2824 return orig_expr;
2825
2826 expr = build_fold_addr_expr (op0);
2827 return fold_convert (orig_type, expr);
2828
2829 case MEM_REF:
2830 /* ??? Offset operand? */
2831 inside_addr = false;
2832 break;
2833
2834 default:
2835 return orig_expr;
2836 }
2837
2838 /* Default handling of expressions for that we want to recurse into
2839 the first operand. */
2840 op0 = TREE_OPERAND (expr, 0);
2841 op0 = strip_offset_1 (op0, inside_addr, false, &off0);
2842 *offset += off0;
2843
2844 if (op0 == TREE_OPERAND (expr, 0)
2845 && (!op1 || op1 == TREE_OPERAND (expr, 1)))
2846 return orig_expr;
2847
2848 expr = copy_node (expr);
2849 TREE_OPERAND (expr, 0) = op0;
2850 if (op1)
2851 TREE_OPERAND (expr, 1) = op1;
2852
2853 /* Inside address, we might strip the top level component references,
2854 thus changing type of the expression. Handling of ADDR_EXPR
2855 will fix that. */
2856 expr = fold_convert (orig_type, expr);
2857
2858 return expr;
2859}
2860
2861/* Strips constant offsets from EXPR and stores them to OFFSET. */
2862
2863tree
2864strip_offset (tree expr, unsigned HOST_WIDE_INT *offset)
2865{
2866 HOST_WIDE_INT off;
2867 tree core = strip_offset_1 (expr, false, false, &off);
2868 *offset = off;
2869 return core;
2870}
2871
2872/* Returns variant of TYPE that can be used as base for different uses.
2873 We return unsigned type with the same precision, which avoids problems
2874 with overflows. */
2875
2876static tree
2877generic_type_for (tree type)
2878{
2879 if (POINTER_TYPE_P (type))
2880 return unsigned_type_for (type);
2881
2882 if (TYPE_UNSIGNED (type))
2883 return type;
2884
2885 return unsigned_type_for (type);
2886}
2887
2888/* Private data for walk_tree. */
2889
2890struct walk_tree_data
2891{
2892 bitmap *inv_vars;
2893 struct ivopts_data *idata;
2894};
2895
2896/* Callback function for walk_tree, it records invariants and symbol
2897 reference in *EXPR_P. DATA is the structure storing result info. */
2898
2899static tree
2900find_inv_vars_cb (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
2901{
2902 tree op = *expr_p;
2903 struct version_info *info;
2904 struct walk_tree_data *wdata = (struct walk_tree_data*) data;
2905
2906 if (TREE_CODE (op) != SSA_NAME)
2907 return NULL_TREE;
2908
2909 info = name_info (wdata->idata, op);
2910 /* Because we expand simple operations when finding IVs, loop invariant
2911 variable that isn't referred by the original loop could be used now.
2912 Record such invariant variables here. */
2913 if (!info->iv)
2914 {
2915 struct ivopts_data *idata = wdata->idata;
2916 basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (op));
2917
2918 if (!bb || !flow_bb_inside_loop_p (idata->current_loop, bb))
2919 {
2920 set_iv (idata, op, op, build_int_cst (TREE_TYPE (op), 0), true);
2921 record_invariant (idata, op, false);
2922 }
2923 }
2924 if (!info->inv_id || info->has_nonlin_use)
2925 return NULL_TREE;
2926
2927 if (!*wdata->inv_vars)
2928 *wdata->inv_vars = BITMAP_ALLOC (NULL);
2929 bitmap_set_bit (*wdata->inv_vars, info->inv_id);
2930
2931 return NULL_TREE;
2932}
2933
2934/* Records invariants in *EXPR_P. INV_VARS is the bitmap to that we should
2935 store it. */
2936
2937static inline void
2938find_inv_vars (struct ivopts_data *data, tree *expr_p, bitmap *inv_vars)
2939{
2940 struct walk_tree_data wdata;
2941
2942 if (!inv_vars)
2943 return;
2944
2945 wdata.idata = data;
2946 wdata.inv_vars = inv_vars;
2947 walk_tree (expr_p, find_inv_vars_cb, &wdata, NULL);
2948}
2949
2950/* Get entry from invariant expr hash table for INV_EXPR. New entry
2951 will be recorded if it doesn't exist yet. Given below two exprs:
2952 inv_expr + cst1, inv_expr + cst2
2953 It's hard to make decision whether constant part should be stripped
2954 or not. We choose to not strip based on below facts:
2955 1) We need to count ADD cost for constant part if it's stripped,
2956 which is't always trivial where this functions is called.
2957 2) Stripping constant away may be conflict with following loop
2958 invariant hoisting pass.
2959 3) Not stripping constant away results in more invariant exprs,
2960 which usually leads to decision preferring lower reg pressure. */
2961
2962static iv_inv_expr_ent *
2963get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
2964{
2965 STRIP_NOPS (inv_expr);
2966
2967 if (TREE_CODE (inv_expr) == INTEGER_CST || TREE_CODE (inv_expr) == SSA_NAME)
2968 return NULL;
2969
2970 /* Don't strip constant part away as we used to. */
2971
2972 /* Stores EXPR in DATA->inv_expr_tab, return pointer to iv_inv_expr_ent. */
2973 struct iv_inv_expr_ent ent;
2974 ent.expr = inv_expr;
2975 ent.hash = iterative_hash_expr (inv_expr, 0);
2976 struct iv_inv_expr_ent **slot = data->inv_expr_tab->find_slot (&ent, INSERT);
2977
2978 if (!*slot)
2979 {
2980 *slot = XNEW (struct iv_inv_expr_ent);
2981 (*slot)->expr = inv_expr;
2982 (*slot)->hash = ent.hash;
2983 (*slot)->id = ++data->max_inv_expr_id;
2984 }
2985
2986 return *slot;
2987}
2988
2989/* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
2990 position to POS. If USE is not NULL, the candidate is set as related to
2991 it. If both BASE and STEP are NULL, we add a pseudocandidate for the
2992 replacement of the final value of the iv by a direct computation. */
2993
2994static struct iv_cand *
2995add_candidate_1 (struct ivopts_data *data,
2996 tree base, tree step, bool important, enum iv_position pos,
2997 struct iv_use *use, gimple *incremented_at,
2998 struct iv *orig_iv = NULL)
2999{
3000 unsigned i;
3001 struct iv_cand *cand = NULL;
3002 tree type, orig_type;
3003
3004 gcc_assert (base && step);
3005
3006 /* -fkeep-gc-roots-live means that we have to keep a real pointer
3007 live, but the ivopts code may replace a real pointer with one
3008 pointing before or after the memory block that is then adjusted
3009 into the memory block during the loop. FIXME: It would likely be
3010 better to actually force the pointer live and still use ivopts;
3011 for example, it would be enough to write the pointer into memory
3012 and keep it there until after the loop. */
3013 if (flag_keep_gc_roots_live && POINTER_TYPE_P (TREE_TYPE (base)))
3014 return NULL;
3015
3016 /* For non-original variables, make sure their values are computed in a type
3017 that does not invoke undefined behavior on overflows (since in general,
3018 we cannot prove that these induction variables are non-wrapping). */
3019 if (pos != IP_ORIGINAL)
3020 {
3021 orig_type = TREE_TYPE (base);
3022 type = generic_type_for (orig_type);
3023 if (type != orig_type)
3024 {
3025 base = fold_convert (type, base);
3026 step = fold_convert (type, step);
3027 }
3028 }
3029
3030 for (i = 0; i < data->vcands.length (); i++)
3031 {
3032 cand = data->vcands[i];
3033
3034 if (cand->pos != pos)
3035 continue;
3036
3037 if (cand->incremented_at != incremented_at
3038 || ((pos == IP_AFTER_USE || pos == IP_BEFORE_USE)
3039 && cand->ainc_use != use))
3040 continue;
3041
3042 if (operand_equal_p (base, cand->iv->base, 0)
3043 && operand_equal_p (step, cand->iv->step, 0)
3044 && (TYPE_PRECISION (TREE_TYPE (base))
3045 == TYPE_PRECISION (TREE_TYPE (cand->iv->base))))
3046 break;
3047 }
3048
3049 if (i == data->vcands.length ())
3050 {
3051 cand = XCNEW (struct iv_cand);
3052 cand->id = i;
3053 cand->iv = alloc_iv (data, base, step);
3054 cand->pos = pos;
3055 if (pos != IP_ORIGINAL)
3056 {
3057 cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp");
3058 cand->var_after = cand->var_before;
3059 }
3060 cand->important = important;
3061 cand->incremented_at = incremented_at;
3062 data->vcands.safe_push (cand);
3063
3064 if (TREE_CODE (step) != INTEGER_CST)
3065 {
3066 find_inv_vars (data, &step, &cand->inv_vars);
3067
3068 iv_inv_expr_ent *inv_expr = get_loop_invariant_expr (data, step);
3069 /* Share bitmap between inv_vars and inv_exprs for cand. */
3070 if (inv_expr != NULL)
3071 {
3072 cand->inv_exprs = cand->inv_vars;
3073 cand->inv_vars = NULL;
3074 if (cand->inv_exprs)
3075 bitmap_clear (cand->inv_exprs);
3076 else
3077 cand->inv_exprs = BITMAP_ALLOC (NULL);
3078
3079 bitmap_set_bit (cand->inv_exprs, inv_expr->id);
3080 }
3081 }
3082
3083 if (pos == IP_AFTER_USE || pos == IP_BEFORE_USE)
3084 cand->ainc_use = use;
3085 else
3086 cand->ainc_use = NULL;
3087
3088 cand->orig_iv = orig_iv;
3089 if (dump_file && (dump_flags & TDF_DETAILS))
3090 dump_cand (dump_file, cand);
3091 }
3092
3093 cand->important |= important;
3094
3095 /* Relate candidate to the group for which it is added. */
3096 if (use)
3097 bitmap_set_bit (data->vgroups[use->group_id]->related_cands, i);
3098
3099 return cand;
3100}
3101
3102/* Returns true if incrementing the induction variable at the end of the LOOP
3103 is allowed.
3104
3105 The purpose is to avoid splitting latch edge with a biv increment, thus
3106 creating a jump, possibly confusing other optimization passes and leaving
3107 less freedom to scheduler. So we allow IP_END only if IP_NORMAL is not
3108 available (so we do not have a better alternative), or if the latch edge
3109 is already nonempty. */
3110
3111static bool
3112allow_ip_end_pos_p (struct loop *loop)
3113{
3114 if (!ip_normal_pos (loop))
3115 return true;
3116
3117 if (!empty_block_p (ip_end_pos (loop)))
3118 return true;
3119
3120 return false;
3121}
3122
3123/* If possible, adds autoincrement candidates BASE + STEP * i based on use USE.
3124 Important field is set to IMPORTANT. */
3125
3126static void
3127add_autoinc_candidates (struct ivopts_data *data, tree base, tree step,
3128 bool important, struct iv_use *use)
3129{
3130 basic_block use_bb = gimple_bb (use->stmt);
3131 machine_mode mem_mode;
3132 unsigned HOST_WIDE_INT cstepi;
3133
3134 /* If we insert the increment in any position other than the standard
3135 ones, we must ensure that it is incremented once per iteration.
3136 It must not be in an inner nested loop, or one side of an if
3137 statement. */
3138 if (use_bb->loop_father != data->current_loop
3139 || !dominated_by_p (CDI_DOMINATORS, data->current_loop->latch, use_bb)
3140 || stmt_can_throw_internal (use->stmt)
3141 || !cst_and_fits_in_hwi (step))
3142 return;
3143
3144 cstepi = int_cst_value (step);
3145
3146 mem_mode = TYPE_MODE (TREE_TYPE (*use->op_p));
3147 if (((USE_LOAD_PRE_INCREMENT (mem_mode)
3148 || USE_STORE_PRE_INCREMENT (mem_mode))
3149 && GET_MODE_SIZE (mem_mode) == cstepi)
3150 || ((USE_LOAD_PRE_DECREMENT (mem_mode)
3151 || USE_STORE_PRE_DECREMENT (mem_mode))
3152 && GET_MODE_SIZE (mem_mode) == -cstepi))
3153 {
3154 enum tree_code code = MINUS_EXPR;
3155 tree new_base;
3156 tree new_step = step;
3157
3158 if (POINTER_TYPE_P (TREE_TYPE (base)))
3159 {
3160 new_step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
3161 code = POINTER_PLUS_EXPR;
3162 }
3163 else
3164 new_step = fold_convert (TREE_TYPE (base), new_step);
3165 new_base = fold_build2 (code, TREE_TYPE (base), base, new_step);
3166 add_candidate_1 (data, new_base, step, important, IP_BEFORE_USE, use,
3167 use->stmt);
3168 }
3169 if (((USE_LOAD_POST_INCREMENT (mem_mode)
3170 || USE_STORE_POST_INCREMENT (mem_mode))
3171 && GET_MODE_SIZE (mem_mode) == cstepi)
3172 || ((USE_LOAD_POST_DECREMENT (mem_mode)
3173 || USE_STORE_POST_DECREMENT (mem_mode))
3174 && GET_MODE_SIZE (mem_mode) == -cstepi))
3175 {
3176 add_candidate_1 (data, base, step, important, IP_AFTER_USE, use,
3177 use->stmt);
3178 }
3179}
3180
3181/* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
3182 position to POS. If USE is not NULL, the candidate is set as related to
3183 it. The candidate computation is scheduled before exit condition and at
3184 the end of loop. */
3185
3186static void
3187add_candidate (struct ivopts_data *data,
3188 tree base, tree step, bool important, struct iv_use *use,
3189 struct iv *orig_iv = NULL)
3190{
3191 if (ip_normal_pos (data->current_loop))
3192 add_candidate_1 (data, base, step, important,
3193 IP_NORMAL, use, NULL, orig_iv);
3194 if (ip_end_pos (data->current_loop)
3195 && allow_ip_end_pos_p (data->current_loop))
3196 add_candidate_1 (data, base, step, important, IP_END, use, NULL, orig_iv);
3197}
3198
3199/* Adds standard iv candidates. */
3200
3201static void
3202add_standard_iv_candidates (struct ivopts_data *data)
3203{
3204 add_candidate (data, integer_zero_node, integer_one_node, true, NULL);
3205
3206 /* The same for a double-integer type if it is still fast enough. */
3207 if (TYPE_PRECISION
3208 (long_integer_type_node) > TYPE_PRECISION (integer_type_node)
3209 && TYPE_PRECISION (long_integer_type_node) <= BITS_PER_WORD)
3210 add_candidate (data, build_int_cst (long_integer_type_node, 0),
3211 build_int_cst (long_integer_type_node, 1), true, NULL);
3212
3213 /* The same for a double-integer type if it is still fast enough. */
3214 if (TYPE_PRECISION
3215 (long_long_integer_type_node) > TYPE_PRECISION (long_integer_type_node)
3216 && TYPE_PRECISION (long_long_integer_type_node) <= BITS_PER_WORD)
3217 add_candidate (data, build_int_cst (long_long_integer_type_node, 0),
3218 build_int_cst (long_long_integer_type_node, 1), true, NULL);
3219}
3220
3221
3222/* Adds candidates bases on the old induction variable IV. */
3223
3224static void
3225add_iv_candidate_for_biv (struct ivopts_data *data, struct iv *iv)
3226{
3227 gimple *phi;
3228 tree def;
3229 struct iv_cand *cand;
3230
3231 /* Check if this biv is used in address type use. */
3232 if (iv->no_overflow && iv->have_address_use
3233 && INTEGRAL_TYPE_P (TREE_TYPE (iv->base))
3234 && TYPE_PRECISION (TREE_TYPE (iv->base)) < TYPE_PRECISION (sizetype))
3235 {
3236 tree base = fold_convert (sizetype, iv->base);
3237 tree step = fold_convert (sizetype, iv->step);
3238
3239 /* Add iv cand of same precision as index part in TARGET_MEM_REF. */
3240 add_candidate (data, base, step, true, NULL, iv);
3241 /* Add iv cand of the original type only if it has nonlinear use. */
3242 if (iv->nonlin_use)
3243 add_candidate (data, iv->base, iv->step, true, NULL);
3244 }
3245 else
3246 add_candidate (data, iv->base, iv->step, true, NULL);
3247
3248 /* The same, but with initial value zero. */
3249 if (POINTER_TYPE_P (TREE_TYPE (iv->base)))
3250 add_candidate (data, size_int (0), iv->step, true, NULL);
3251 else
3252 add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
3253 iv->step, true, NULL);
3254
3255 phi = SSA_NAME_DEF_STMT (iv->ssa_name);
3256 if (gimple_code (phi) == GIMPLE_PHI)
3257 {
3258 /* Additionally record the possibility of leaving the original iv
3259 untouched. */
3260 def = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (data->current_loop));
3261 /* Don't add candidate if it's from another PHI node because
3262 it's an affine iv appearing in the form of PEELED_CHREC. */
3263 phi = SSA_NAME_DEF_STMT (def);
3264 if (gimple_code (phi) != GIMPLE_PHI)
3265 {
3266 cand = add_candidate_1 (data,
3267 iv->base, iv->step, true, IP_ORIGINAL, NULL,
3268 SSA_NAME_DEF_STMT (def));
3269 if (cand)
3270 {
3271 cand->var_before = iv->ssa_name;
3272 cand->var_after = def;
3273 }
3274 }
3275 else
3276 gcc_assert (gimple_bb (phi) == data->current_loop->header);
3277 }
3278}
3279
3280/* Adds candidates based on the old induction variables. */
3281
3282static void
3283add_iv_candidate_for_bivs (struct ivopts_data *data)
3284{
3285 unsigned i;
3286 struct iv *iv;
3287 bitmap_iterator bi;
3288
3289 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
3290 {
3291 iv = ver_info (data, i)->iv;
3292 if (iv && iv->biv_p && !integer_zerop (iv->step))
3293 add_iv_candidate_for_biv (data, iv);
3294 }
3295}
3296
3297/* Record common candidate {BASE, STEP} derived from USE in hashtable. */
3298
3299static void
3300record_common_cand (struct ivopts_data *data, tree base,
3301 tree step, struct iv_use *use)
3302{
3303 struct iv_common_cand ent;
3304 struct iv_common_cand **slot;
3305
3306 ent.base = base;
3307 ent.step = step;
3308 ent.hash = iterative_hash_expr (base, 0);
3309 ent.hash = iterative_hash_expr (step, ent.hash);
3310
3311 slot = data->iv_common_cand_tab->find_slot (&ent, INSERT);
3312 if (*slot == NULL)
3313 {
3314 *slot = new iv_common_cand ();
3315 (*slot)->base = base;
3316 (*slot)->step = step;
3317 (*slot)->uses.create (8);
3318 (*slot)->hash = ent.hash;
3319 data->iv_common_cands.safe_push ((*slot));
3320 }
3321
3322 gcc_assert (use != NULL);
3323 (*slot)->uses.safe_push (use);
3324 return;
3325}
3326
3327/* Comparison function used to sort common candidates. */
3328
3329static int
3330common_cand_cmp (const void *p1, const void *p2)
3331{
3332 unsigned n1, n2;
3333 const struct iv_common_cand *const *const ccand1
3334 = (const struct iv_common_cand *const *)p1;
3335 const struct iv_common_cand *const *const ccand2
3336 = (const struct iv_common_cand *const *)p2;
3337
3338 n1 = (*ccand1)->uses.length ();
3339 n2 = (*ccand2)->uses.length ();
3340 return n2 - n1;
3341}
3342
3343/* Adds IV candidates based on common candidated recorded. */
3344
3345static void
3346add_iv_candidate_derived_from_uses (struct ivopts_data *data)
3347{
3348 unsigned i, j;
3349 struct iv_cand *cand_1, *cand_2;
3350
3351 data->iv_common_cands.qsort (common_cand_cmp);
3352 for (i = 0; i < data->iv_common_cands.length (); i++)
3353 {
3354 struct iv_common_cand *ptr = data->iv_common_cands[i];
3355
3356 /* Only add IV candidate if it's derived from multiple uses. */
3357 if (ptr->uses.length () <= 1)
3358 break;
3359
3360 cand_1 = NULL;
3361 cand_2 = NULL;
3362 if (ip_normal_pos (data->current_loop))
3363 cand_1 = add_candidate_1 (data, ptr->base, ptr->step,
3364 false, IP_NORMAL, NULL, NULL);
3365
3366 if (ip_end_pos (data->current_loop)
3367 && allow_ip_end_pos_p (data->current_loop))
3368 cand_2 = add_candidate_1 (data, ptr->base, ptr->step,
3369 false, IP_END, NULL, NULL);
3370
3371 /* Bind deriving uses and the new candidates. */
3372 for (j = 0; j < ptr->uses.length (); j++)
3373 {
3374 struct iv_group *group = data->vgroups[ptr->uses[j]->group_id];
3375 if (cand_1)
3376 bitmap_set_bit (group->related_cands, cand_1->id);
3377 if (cand_2)
3378 bitmap_set_bit (group->related_cands, cand_2->id);
3379 }
3380 }
3381
3382 /* Release data since it is useless from this point. */
3383 data->iv_common_cand_tab->empty ();
3384 data->iv_common_cands.truncate (0);
3385}
3386
3387/* Adds candidates based on the value of USE's iv. */
3388
3389static void
3390add_iv_candidate_for_use (struct ivopts_data *data, struct iv_use *use)
3391{
3392 unsigned HOST_WIDE_INT offset;
3393 tree base;
3394 tree basetype;
3395 struct iv *iv = use->iv;
3396
3397 add_candidate (data, iv->base, iv->step, false, use);
3398
3399 /* Record common candidate for use in case it can be shared by others. */
3400 record_common_cand (data, iv->base, iv->step, use);
3401
3402 /* Record common candidate with initial value zero. */
3403 basetype = TREE_TYPE (iv->base);
3404 if (POINTER_TYPE_P (basetype))
3405 basetype = sizetype;
3406 record_common_cand (data, build_int_cst (basetype, 0), iv->step, use);
3407
3408 /* Record common candidate with constant offset stripped in base.
3409 Like the use itself, we also add candidate directly for it. */
3410 base = strip_offset (iv->base, &offset);
3411 if (offset || base != iv->base)
3412 {
3413 record_common_cand (data, base, iv->step, use);
3414 add_candidate (data, base, iv->step, false, use);
3415 }
3416
3417 /* Record common candidate with base_object removed in base. */
3418 base = iv->base;
3419 STRIP_NOPS (base);
3420 if (iv->base_object != NULL && TREE_CODE (base) == POINTER_PLUS_EXPR)
3421 {
3422 tree step = iv->step;
3423
3424 STRIP_NOPS (step);
3425 base = TREE_OPERAND (base, 1);
3426 step = fold_convert (sizetype, step);
3427 record_common_cand (data, base, step, use);
3428 /* Also record common candidate with offset stripped. */
3429 base = strip_offset (base, &offset);
3430 if (offset)
3431 record_common_cand (data, base, step, use);
3432 }
3433
3434 /* At last, add auto-incremental candidates. Make such variables
3435 important since other iv uses with same base object may be based
3436 on it. */
3437 if (use != NULL && use->type == USE_ADDRESS)
3438 add_autoinc_candidates (data, iv->base, iv->step, true, use);
3439}
3440
3441/* Adds candidates based on the uses. */
3442
3443static void
3444add_iv_candidate_for_groups (struct ivopts_data *data)
3445{
3446 unsigned i;
3447
3448 /* Only add candidate for the first use in group. */
3449 for (i = 0; i < data->vgroups.length (); i++)
3450 {
3451 struct iv_group *group = data->vgroups[i];
3452
3453 gcc_assert (group->vuses[0] != NULL);
3454 add_iv_candidate_for_use (data, group->vuses[0]);
3455 }
3456 add_iv_candidate_derived_from_uses (data);
3457}
3458
3459/* Record important candidates and add them to related_cands bitmaps. */
3460
3461static void
3462record_important_candidates (struct ivopts_data *data)
3463{
3464 unsigned i;
3465 struct iv_group *group;
3466
3467 for (i = 0; i < data->vcands.length (); i++)
3468 {
3469 struct iv_cand *cand = data->vcands[i];
3470
3471 if (cand->important)
3472 bitmap_set_bit (data->important_candidates, i);
3473 }
3474
3475 data->consider_all_candidates = (data->vcands.length ()
3476 <= CONSIDER_ALL_CANDIDATES_BOUND);
3477
3478 /* Add important candidates to groups' related_cands bitmaps. */
3479 for (i = 0; i < data->vgroups.length (); i++)
3480 {
3481 group = data->vgroups[i];
3482 bitmap_ior_into (group->related_cands, data->important_candidates);
3483 }
3484}
3485
3486/* Allocates the data structure mapping the (use, candidate) pairs to costs.
3487 If consider_all_candidates is true, we use a two-dimensional array, otherwise
3488 we allocate a simple list to every use. */
3489
3490static void
3491alloc_use_cost_map (struct ivopts_data *data)
3492{
3493 unsigned i, size, s;
3494
3495 for (i = 0; i < data->vgroups.length (); i++)
3496 {
3497 struct iv_group *group = data->vgroups[i];
3498
3499 if (data->consider_all_candidates)
3500 size = data->vcands.length ();
3501 else
3502 {
3503 s = bitmap_count_bits (group->related_cands);
3504
3505 /* Round up to the power of two, so that moduling by it is fast. */
3506 size = s ? (1 << ceil_log2 (s)) : 1;
3507 }
3508
3509 group->n_map_members = size;
3510 group->cost_map = XCNEWVEC (struct cost_pair, size);
3511 }
3512}
3513
3514/* Sets cost of (GROUP, CAND) pair to COST and record that it depends
3515 on invariants INV_VARS and that the value used in expressing it is
3516 VALUE, and in case of iv elimination the comparison operator is COMP. */
3517
3518static void
3519set_group_iv_cost (struct ivopts_data *data,
3520 struct iv_group *group, struct iv_cand *cand,
3521 comp_cost cost, bitmap inv_vars, tree value,
3522 enum tree_code comp, bitmap inv_exprs)
3523{
3524 unsigned i, s;
3525
3526 if (cost.infinite_cost_p ())
3527 {
3528 BITMAP_FREE (inv_vars);
3529 BITMAP_FREE (inv_exprs);
3530 return;
3531 }
3532
3533 if (data->consider_all_candidates)
3534 {
3535 group->cost_map[cand->id].cand = cand;
3536 group->cost_map[cand->id].cost = cost;
3537 group->cost_map[cand->id].inv_vars = inv_vars;
3538 group->cost_map[cand->id].inv_exprs = inv_exprs;
3539 group->cost_map[cand->id].value = value;
3540 group->cost_map[cand->id].comp = comp;
3541 return;
3542 }
3543
3544 /* n_map_members is a power of two, so this computes modulo. */
3545 s = cand->id & (group->n_map_members - 1);
3546 for (i = s; i < group->n_map_members; i++)
3547 if (!group->cost_map[i].cand)
3548 goto found;
3549 for (i = 0; i < s; i++)
3550 if (!group->cost_map[i].cand)
3551 goto found;
3552
3553 gcc_unreachable ();
3554
3555found:
3556 group->cost_map[i].cand = cand;
3557 group->cost_map[i].cost = cost;
3558 group->cost_map[i].inv_vars = inv_vars;
3559 group->cost_map[i].inv_exprs = inv_exprs;
3560 group->cost_map[i].value = value;
3561 group->cost_map[i].comp = comp;
3562}
3563
3564/* Gets cost of (GROUP, CAND) pair. */
3565
3566static struct cost_pair *
3567get_group_iv_cost (struct ivopts_data *data, struct iv_group *group,
3568 struct iv_cand *cand)
3569{
3570 unsigned i, s;
3571 struct cost_pair *ret;
3572
3573 if (!cand)
3574 return NULL;
3575
3576 if (data->consider_all_candidates)
3577 {
3578 ret = group->cost_map + cand->id;
3579 if (!ret->cand)
3580 return NULL;
3581
3582 return ret;
3583 }
3584
3585 /* n_map_members is a power of two, so this computes modulo. */
3586 s = cand->id & (group->n_map_members - 1);
3587 for (i = s; i < group->n_map_members; i++)
3588 if (group->cost_map[i].cand == cand)
3589 return group->cost_map + i;
3590 else if (group->cost_map[i].cand == NULL)
3591 return NULL;
3592 for (i = 0; i < s; i++)
3593 if (group->cost_map[i].cand == cand)
3594 return group->cost_map + i;
3595 else if (group->cost_map[i].cand == NULL)
3596 return NULL;
3597
3598 return NULL;
3599}
3600
3601/* Produce DECL_RTL for object obj so it looks like it is stored in memory. */
3602static rtx
3603produce_memory_decl_rtl (tree obj, int *regno)
3604{
3605 addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (obj));
3606 machine_mode address_mode = targetm.addr_space.address_mode (as);
3607 rtx x;
3608
3609 gcc_assert (obj);
3610 if (TREE_STATIC (obj) || DECL_EXTERNAL (obj))
3611 {
3612 const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj));
3613 x = gen_rtx_SYMBOL_REF (address_mode, name);
3614 SET_SYMBOL_REF_DECL (x, obj);
3615 x = gen_rtx_MEM (DECL_MODE (obj), x);
3616 set_mem_addr_space (x, as);
3617 targetm.encode_section_info (obj, x, true);
3618 }
3619 else
3620 {
3621 x = gen_raw_REG (address_mode, (*regno)++);
3622 x = gen_rtx_MEM (DECL_MODE (obj), x);
3623 set_mem_addr_space (x, as);
3624 }
3625
3626 return x;
3627}
3628
3629/* Prepares decl_rtl for variables referred in *EXPR_P. Callback for
3630 walk_tree. DATA contains the actual fake register number. */
3631
3632static tree
3633prepare_decl_rtl (tree *expr_p, int *ws, void *data)
3634{
3635 tree obj = NULL_TREE;
3636 rtx x = NULL_RTX;
3637 int *regno = (int *) data;
3638
3639 switch (TREE_CODE (*expr_p))
3640 {
3641 case ADDR_EXPR:
3642 for (expr_p = &TREE_OPERAND (*expr_p, 0);
3643 handled_component_p (*expr_p);
3644 expr_p = &TREE_OPERAND (*expr_p, 0))
3645 continue;
3646 obj = *expr_p;
3647 if (DECL_P (obj) && HAS_RTL_P (obj) && !DECL_RTL_SET_P (obj))
3648 x = produce_memory_decl_rtl (obj, regno);
3649 break;
3650
3651 case SSA_NAME:
3652 *ws = 0;
3653 obj = SSA_NAME_VAR (*expr_p);
3654 /* Defer handling of anonymous SSA_NAMEs to the expander. */
3655 if (!obj)
3656 return NULL_TREE;
3657 if (!DECL_RTL_SET_P (obj))
3658 x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
3659 break;
3660
3661 case VAR_DECL:
3662 case PARM_DECL:
3663 case RESULT_DECL:
3664 *ws = 0;
3665 obj = *expr_p;
3666
3667 if (DECL_RTL_SET_P (obj))
3668 break;
3669
3670 if (DECL_MODE (obj) == BLKmode)
3671 x = produce_memory_decl_rtl (obj, regno);
3672 else
3673 x = gen_raw_REG (DECL_MODE (obj), (*regno)++);
3674
3675 break;
3676
3677 default:
3678 break;
3679 }
3680
3681 if (x)
3682 {
3683 decl_rtl_to_reset.safe_push (obj);
3684 SET_DECL_RTL (obj, x);
3685 }
3686
3687 return NULL_TREE;
3688}
3689
3690/* Determines cost of the computation of EXPR. */
3691
3692static unsigned
3693computation_cost (tree expr, bool speed)
3694{
3695 rtx_insn *seq;
3696 rtx rslt;
3697 tree type = TREE_TYPE (expr);
3698 unsigned cost;
3699 /* Avoid using hard regs in ways which may be unsupported. */
3700 int regno = LAST_VIRTUAL_REGISTER + 1;
3701 struct cgraph_node *node = cgraph_node::get (current_function_decl);
3702 enum node_frequency real_frequency = node->frequency;
3703
3704 node->frequency = NODE_FREQUENCY_NORMAL;
3705 crtl->maybe_hot_insn_p = speed;
3706 walk_tree (&expr, prepare_decl_rtl, &regno, NULL);
3707 start_sequence ();
3708 rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL);
3709 seq = get_insns ();
3710 end_sequence ();
3711 default_rtl_profile ();
3712 node->frequency = real_frequency;
3713
3714 cost = seq_cost (seq, speed);
3715 if (MEM_P (rslt))
3716 cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type),
3717 TYPE_ADDR_SPACE (type), speed);
3718 else if (!REG_P (rslt))
3719 cost += set_src_cost (rslt, TYPE_MODE (type), speed);
3720
3721 return cost;
3722}
3723
3724/* Returns variable containing the value of candidate CAND at statement AT. */
3725
3726static tree
3727var_at_stmt (struct loop *loop, struct iv_cand *cand, gimple *stmt)
3728{
3729 if (stmt_after_increment (loop, cand, stmt))
3730 return cand->var_after;
3731 else
3732 return cand->var_before;
3733}
3734
3735/* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
3736 same precision that is at least as wide as the precision of TYPE, stores
3737 BA to A and BB to B, and returns the type of BA. Otherwise, returns the
3738 type of A and B. */
3739
3740static tree
3741determine_common_wider_type (tree *a, tree *b)
3742{
3743 tree wider_type = NULL;
3744 tree suba, subb;
3745 tree atype = TREE_TYPE (*a);
3746
3747 if (CONVERT_EXPR_P (*a))
3748 {
3749 suba = TREE_OPERAND (*a, 0);
3750 wider_type = TREE_TYPE (suba);
3751 if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (atype))
3752 return atype;
3753 }
3754 else
3755 return atype;
3756
3757 if (CONVERT_EXPR_P (*b))
3758 {
3759 subb = TREE_OPERAND (*b, 0);
3760 if (TYPE_PRECISION (wider_type) != TYPE_PRECISION (TREE_TYPE (subb)))
3761 return atype;
3762 }
3763 else
3764 return atype;
3765
3766 *a = suba;
3767 *b = subb;
3768 return wider_type;
3769}
3770
3771/* Determines the expression by that USE is expressed from induction variable
3772 CAND at statement AT in LOOP. The expression is stored in two parts in a
3773 decomposed form. The invariant part is stored in AFF_INV; while variant
3774 part in AFF_VAR. Store ratio of CAND.step over USE.step in PRAT if it's
3775 non-null. Returns false if USE cannot be expressed using CAND. */
3776
3777static bool
3778get_computation_aff_1 (struct loop *loop, gimple *at, struct iv_use *use,
3779 struct iv_cand *cand, struct aff_tree *aff_inv,
3780 struct aff_tree *aff_var, widest_int *prat = NULL)
3781{
3782 tree ubase = use->iv->base, ustep = use->iv->step;
3783 tree cbase = cand->iv->base, cstep = cand->iv->step;
3784 tree common_type, uutype, var, cstep_common;
3785 tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
3786 aff_tree aff_cbase;
3787 widest_int rat;
3788
3789 /* We must have a precision to express the values of use. */
3790 if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
3791 return false;
3792
3793 var = var_at_stmt (loop, cand, at);
3794 uutype = unsigned_type_for (utype);
3795
3796 /* If the conversion is not noop, perform it. */
3797 if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
3798 {
3799 if (cand->orig_iv != NULL && CONVERT_EXPR_P (cbase)
3800 && (CONVERT_EXPR_P (cstep) || TREE_CODE (cstep) == INTEGER_CST))
3801 {
3802 tree inner_base, inner_step, inner_type;
3803 inner_base = TREE_OPERAND (cbase, 0);
3804 if (CONVERT_EXPR_P (cstep))
3805 inner_step = TREE_OPERAND (cstep, 0);
3806 else
3807 inner_step = cstep;
3808
3809 inner_type = TREE_TYPE (inner_base);
3810 /* If candidate is added from a biv whose type is smaller than
3811 ctype, we know both candidate and the biv won't overflow.
3812 In this case, it's safe to skip the convertion in candidate.
3813 As an example, (unsigned short)((unsigned long)A) equals to
3814 (unsigned short)A, if A has a type no larger than short. */
3815 if (TYPE_PRECISION (inner_type) <= TYPE_PRECISION (uutype))
3816 {
3817 cbase = inner_base;
3818 cstep = inner_step;
3819 }
3820 }
3821 cbase = fold_convert (uutype, cbase);
3822 cstep = fold_convert (uutype, cstep);
3823 var = fold_convert (uutype, var);
3824 }
3825
3826 /* Ratio is 1 when computing the value of biv cand by itself.
3827 We can't rely on constant_multiple_of in this case because the
3828 use is created after the original biv is selected. The call
3829 could fail because of inconsistent fold behavior. See PR68021
3830 for more information. */
3831 if (cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt)
3832 {
3833 gcc_assert (is_gimple_assign (use->stmt));
3834 gcc_assert (use->iv->ssa_name == cand->var_after);
3835 gcc_assert (gimple_assign_lhs (use->stmt) == cand->var_after);
3836 rat = 1;
3837 }
3838 else if (!constant_multiple_of (ustep, cstep, &rat))
3839 return false;
3840
3841 if (prat)
3842 *prat = rat;
3843
3844 /* In case both UBASE and CBASE are shortened to UUTYPE from some common
3845 type, we achieve better folding by computing their difference in this
3846 wider type, and cast the result to UUTYPE. We do not need to worry about
3847 overflows, as all the arithmetics will in the end be performed in UUTYPE
3848 anyway. */
3849 common_type = determine_common_wider_type (&ubase, &cbase);
3850
3851 /* use = ubase - ratio * cbase + ratio * var. */
3852 tree_to_aff_combination (ubase, common_type, aff_inv);
3853 tree_to_aff_combination (cbase, common_type, &aff_cbase);
3854 tree_to_aff_combination (var, uutype, aff_var);
3855
3856 /* We need to shift the value if we are after the increment. */
3857 if (stmt_after_increment (loop, cand, at))
3858 {
3859 aff_tree cstep_aff;
3860
3861 if (common_type != uutype)
3862 cstep_common = fold_convert (common_type, cstep);
3863 else
3864 cstep_common = cstep;
3865
3866 tree_to_aff_combination (cstep_common, common_type, &cstep_aff);
3867 aff_combination_add (&aff_cbase, &cstep_aff);
3868 }
3869
3870 aff_combination_scale (&aff_cbase, -rat);
3871 aff_combination_add (aff_inv, &aff_cbase);
3872 if (common_type != uutype)
3873 aff_combination_convert (aff_inv, uutype);
3874
3875 aff_combination_scale (aff_var, rat);
3876 return true;
3877}
3878
3879/* Determines the expression by that USE is expressed from induction variable
3880 CAND at statement AT in LOOP. The expression is stored in a decomposed
3881 form into AFF. Returns false if USE cannot be expressed using CAND. */
3882
3883static bool
3884get_computation_aff (struct loop *loop, gimple *at, struct iv_use *use,
3885 struct iv_cand *cand, struct aff_tree *aff)
3886{
3887 aff_tree aff_var;
3888
3889 if (!get_computation_aff_1 (loop, at, use, cand, aff, &aff_var))
3890 return false;
3891
3892 aff_combination_add (aff, &aff_var);
3893 return true;
3894}
3895
3896/* Return the type of USE. */
3897
3898static tree
3899get_use_type (struct iv_use *use)
3900{
3901 tree base_type = TREE_TYPE (use->iv->base);
3902 tree type;
3903
3904 if (use->type == USE_ADDRESS)
3905 {
3906 /* The base_type may be a void pointer. Create a pointer type based on
3907 the mem_ref instead. */
3908 type = build_pointer_type (TREE_TYPE (*use->op_p));
3909 gcc_assert (TYPE_ADDR_SPACE (TREE_TYPE (type))
3910 == TYPE_ADDR_SPACE (TREE_TYPE (base_type)));
3911 }
3912 else
3913 type = base_type;
3914
3915 return type;
3916}
3917
3918/* Determines the expression by that USE is expressed from induction variable
3919 CAND at statement AT in LOOP. The computation is unshared. */
3920
3921static tree
3922get_computation_at (struct loop *loop, gimple *at,
3923 struct iv_use *use, struct iv_cand *cand)
3924{
3925 aff_tree aff;
3926 tree type = get_use_type (use);
3927
3928 if (!get_computation_aff (loop, at, use, cand, &aff))
3929 return NULL_TREE;
3930 unshare_aff_combination (&aff);
3931 return fold_convert (type, aff_combination_to_tree (&aff));
3932}
3933
3934/* Adjust the cost COST for being in loop setup rather than loop body.
3935 If we're optimizing for space, the loop setup overhead is constant;
3936 if we're optimizing for speed, amortize it over the per-iteration cost.
3937 If ROUND_UP_P is true, the result is round up rather than to zero when
3938 optimizing for speed. */
3939static unsigned
3940adjust_setup_cost (struct ivopts_data *data, unsigned cost,
3941 bool round_up_p = false)
3942{
3943 if (cost == INFTY)
3944 return cost;
3945 else if (optimize_loop_for_speed_p (data->current_loop))
3946 {
3947 HOST_WIDE_INT niters = avg_loop_niter (data->current_loop);
3948 return ((HOST_WIDE_INT) cost + (round_up_p ? niters - 1 : 0)) / niters;
3949 }
3950 else
3951 return cost;
3952}
3953
3954/* Calculate the SPEED or size cost of shiftadd EXPR in MODE. MULT is the
3955 EXPR operand holding the shift. COST0 and COST1 are the costs for
3956 calculating the operands of EXPR. Returns true if successful, and returns
3957 the cost in COST. */
3958
3959static bool
3960get_shiftadd_cost (tree expr, scalar_int_mode mode, comp_cost cost0,
3961 comp_cost cost1, tree mult, bool speed, comp_cost *cost)
3962{
3963 comp_cost res;
3964 tree op1 = TREE_OPERAND (expr, 1);
3965 tree cst = TREE_OPERAND (mult, 1);
3966 tree multop = TREE_OPERAND (mult, 0);
3967 int m = exact_log2 (int_cst_value (cst));
3968 int maxm = MIN (BITS_PER_WORD, GET_MODE_BITSIZE (mode));
3969 int as_cost, sa_cost;
3970 bool mult_in_op1;
3971
3972 if (!(m >= 0 && m < maxm))
3973 return false;
3974
3975 STRIP_NOPS (op1);
3976 mult_in_op1 = operand_equal_p (op1, mult, 0);
3977
3978 as_cost = add_cost (speed, mode) + shift_cost (speed, mode, m);
3979
3980 /* If the target has a cheap shift-and-add or shift-and-sub instruction,
3981 use that in preference to a shift insn followed by an add insn. */
3982 sa_cost = (TREE_CODE (expr) != MINUS_EXPR
3983 ? shiftadd_cost (speed, mode, m)
3984 : (mult_in_op1
3985 ? shiftsub1_cost (speed, mode, m)
3986 : shiftsub0_cost (speed, mode, m)));
3987
3988 res = comp_cost (MIN (as_cost, sa_cost), 0);
3989 res += (mult_in_op1 ? cost0 : cost1);
3990
3991 STRIP_NOPS (multop);
3992 if (!is_gimple_val (multop))
3993 res += force_expr_to_var_cost (multop, speed);
3994
3995 *cost = res;
3996 return true;
3997}
3998
3999/* Estimates cost of forcing expression EXPR into a variable. */
4000
4001static comp_cost
4002force_expr_to_var_cost (tree expr, bool speed)
4003{
4004 static bool costs_initialized = false;
4005 static unsigned integer_cost [2];
4006 static unsigned symbol_cost [2];
4007 static unsigned address_cost [2];
4008 tree op0, op1;
4009 comp_cost cost0, cost1, cost;
4010 machine_mode mode;
4011 scalar_int_mode int_mode;
4012
4013 if (!costs_initialized)
4014 {
4015 tree type = build_pointer_type (integer_type_node);
4016 tree var, addr;
4017 rtx x;
4018 int i;
4019
4020 var = create_tmp_var_raw (integer_type_node, "test_var");
4021 TREE_STATIC (var) = 1;
4022 x = produce_memory_decl_rtl (var, NULL);
4023 SET_DECL_RTL (var, x);
4024
4025 addr = build1 (ADDR_EXPR, type, var);
4026
4027
4028 for (i = 0; i < 2; i++)
4029 {
4030 integer_cost[i] = computation_cost (build_int_cst (integer_type_node,
4031 2000), i);
4032
4033 symbol_cost[i] = computation_cost (addr, i) + 1;
4034
4035 address_cost[i]
4036 = computation_cost (fold_build_pointer_plus_hwi (addr, 2000), i) + 1;
4037 if (dump_file && (dump_flags & TDF_DETAILS))
4038 {
4039 fprintf (dump_file, "force_expr_to_var_cost %s costs:\n", i ? "speed" : "size");
4040 fprintf (dump_file, " integer %d\n", (int) integer_cost[i]);
4041 fprintf (dump_file, " symbol %d\n", (int) symbol_cost[i]);
4042 fprintf (dump_file, " address %d\n", (int) address_cost[i]);
4043 fprintf (dump_file, " other %d\n", (int) target_spill_cost[i]);
4044 fprintf (dump_file, "\n");
4045 }
4046 }
4047
4048 costs_initialized = true;
4049 }
4050
4051 STRIP_NOPS (expr);
4052
4053 if (SSA_VAR_P (expr))
4054 return no_cost;
4055
4056 if (is_gimple_min_invariant (expr))
4057 {
4058 if (TREE_CODE (expr) == INTEGER_CST)
4059 return comp_cost (integer_cost [speed], 0);
4060
4061 if (TREE_CODE (expr) == ADDR_EXPR)
4062 {
4063 tree obj = TREE_OPERAND (expr, 0);
4064
4065 if (VAR_P (obj)
4066 || TREE_CODE (obj) == PARM_DECL
4067 || TREE_CODE (obj) == RESULT_DECL)
4068 return comp_cost (symbol_cost [speed], 0);
4069 }
4070
4071 return comp_cost (address_cost [speed], 0);
4072 }
4073
4074 switch (TREE_CODE (expr))
4075 {
4076 case POINTER_PLUS_EXPR:
4077 case PLUS_EXPR:
4078 case MINUS_EXPR:
4079 case MULT_EXPR:
4080 case TRUNC_DIV_EXPR:
4081 case BIT_AND_EXPR:
4082 case BIT_IOR_EXPR:
4083 case LSHIFT_EXPR:
4084 case RSHIFT_EXPR:
4085 op0 = TREE_OPERAND (expr, 0);
4086 op1 = TREE_OPERAND (expr, 1);
4087 STRIP_NOPS (op0);
4088 STRIP_NOPS (op1);
4089 break;
4090
4091 CASE_CONVERT:
4092 case NEGATE_EXPR:
4093 case BIT_NOT_EXPR:
4094 op0 = TREE_OPERAND (expr, 0);
4095 STRIP_NOPS (op0);
4096 op1 = NULL_TREE;
4097 break;
4098
4099 default:
4100 /* Just an arbitrary value, FIXME. */
4101 return comp_cost (target_spill_cost[speed], 0);
4102 }
4103
4104 if (op0 == NULL_TREE
4105 || TREE_CODE (op0) == SSA_NAME || CONSTANT_CLASS_P (op0))
4106 cost0 = no_cost;
4107 else
4108 cost0 = force_expr_to_var_cost (op0, speed);
4109
4110 if (op1 == NULL_TREE
4111 || TREE_CODE (op1) == SSA_NAME || CONSTANT_CLASS_P (op1))
4112 cost1 = no_cost;
4113 else
4114 cost1 = force_expr_to_var_cost (op1, speed);
4115
4116 mode = TYPE_MODE (TREE_TYPE (expr));
4117 switch (TREE_CODE (expr))
4118 {
4119 case POINTER_PLUS_EXPR:
4120 case PLUS_EXPR:
4121 case MINUS_EXPR:
4122 case NEGATE_EXPR:
4123 cost = comp_cost (add_cost (speed, mode), 0);
4124 if (TREE_CODE (expr) != NEGATE_EXPR)
4125 {
4126 tree mult = NULL_TREE;
4127 comp_cost sa_cost;
4128 if (TREE_CODE (op1) == MULT_EXPR)
4129 mult = op1;
4130 else if (TREE_CODE (op0) == MULT_EXPR)
4131 mult = op0;
4132
4133 if (mult != NULL_TREE
4134 && is_a <scalar_int_mode> (mode, &int_mode)
4135 && cst_and_fits_in_hwi (TREE_OPERAND (mult, 1))
4136 && get_shiftadd_cost (expr, int_mode, cost0, cost1, mult,
4137 speed, &sa_cost))
4138 return sa_cost;
4139 }
4140 break;
4141
4142 CASE_CONVERT:
4143 {
4144 tree inner_mode, outer_mode;
4145 outer_mode = TREE_TYPE (expr);
4146 inner_mode = TREE_TYPE (op0);
4147 cost = comp_cost (convert_cost (TYPE_MODE (outer_mode),
4148 TYPE_MODE (inner_mode), speed), 0);
4149 }
4150 break;
4151
4152 case MULT_EXPR:
4153 if (cst_and_fits_in_hwi (op0))
4154 cost = comp_cost (mult_by_coeff_cost (int_cst_value (op0),
4155 mode, speed), 0);
4156 else if (cst_and_fits_in_hwi (op1))
4157 cost = comp_cost (mult_by_coeff_cost (int_cst_value (op1),
4158 mode, speed), 0);
4159 else
4160 return comp_cost (target_spill_cost [speed], 0);
4161 break;
4162
4163 case TRUNC_DIV_EXPR:
4164 /* Division by power of two is usually cheap, so we allow it. Forbid
4165 anything else. */
4166 if (integer_pow2p (TREE_OPERAND (expr, 1)))
4167 cost = comp_cost (add_cost (speed, mode), 0);
4168 else
4169 cost = comp_cost (target_spill_cost[speed], 0);
4170 break;
4171
4172 case BIT_AND_EXPR:
4173 case BIT_IOR_EXPR:
4174 case BIT_NOT_EXPR:
4175 case LSHIFT_EXPR:
4176 case RSHIFT_EXPR:
4177 cost = comp_cost (add_cost (speed, mode), 0);
4178 break;
4179
4180 default:
4181 gcc_unreachable ();
4182 }
4183
4184 cost += cost0;
4185 cost += cost1;
4186 return cost;
4187}
4188
4189/* Estimates cost of forcing EXPR into a variable. INV_VARS is a set of the
4190 invariants the computation depends on. */
4191
4192static comp_cost
4193force_var_cost (struct ivopts_data *data, tree expr, bitmap *inv_vars)
4194{
4195 if (!expr)
4196 return no_cost;
4197
4198 find_inv_vars (data, &expr, inv_vars);
4199 return force_expr_to_var_cost (expr, data->speed);
4200}
4201
4202/* Returns cost of auto-modifying address expression in shape base + offset.
4203 AINC_STEP is step size of the address IV. AINC_OFFSET is offset of the
4204 address expression. The address expression has ADDR_MODE in addr space
4205 AS. The memory access has MEM_MODE. SPEED means we are optimizing for
4206 speed or size. */
4207
4208enum ainc_type
4209{
4210 AINC_PRE_INC, /* Pre increment. */
4211 AINC_PRE_DEC, /* Pre decrement. */
4212 AINC_POST_INC, /* Post increment. */
4213 AINC_POST_DEC, /* Post decrement. */
4214 AINC_NONE /* Also the number of auto increment types. */
4215};
4216
4217struct ainc_cost_data
4218{
4219 unsigned costs[AINC_NONE];
4220};
4221
4222static comp_cost
4223get_address_cost_ainc (HOST_WIDE_INT ainc_step, HOST_WIDE_INT ainc_offset,
4224 machine_mode addr_mode, machine_mode mem_mode,
4225 addr_space_t as, bool speed)
4226{
4227 if (!USE_LOAD_PRE_DECREMENT (mem_mode)
4228 && !USE_STORE_PRE_DECREMENT (mem_mode)
4229 && !USE_LOAD_POST_DECREMENT (mem_mode)
4230 && !USE_STORE_POST_DECREMENT (mem_mode)
4231 && !USE_LOAD_PRE_INCREMENT (mem_mode)
4232 && !USE_STORE_PRE_INCREMENT (mem_mode)
4233 && !USE_LOAD_POST_INCREMENT (mem_mode)
4234 && !USE_STORE_POST_INCREMENT (mem_mode))
4235 return infinite_cost;
4236
4237 static vec<ainc_cost_data *> ainc_cost_data_list;
4238 unsigned idx = (unsigned) as * MAX_MACHINE_MODE + (unsigned) mem_mode;
4239 if (idx >= ainc_cost_data_list.length ())
4240 {
4241 unsigned nsize = ((unsigned) as + 1) *MAX_MACHINE_MODE;
4242
4243 gcc_assert (nsize > idx);
4244 ainc_cost_data_list.safe_grow_cleared (nsize);
4245 }
4246
4247 ainc_cost_data *data = ainc_cost_data_list[idx];
4248 if (data == NULL)
4249 {
4250 rtx reg = gen_raw_REG (addr_mode, LAST_VIRTUAL_REGISTER + 1);
4251
4252 data = (ainc_cost_data *) xcalloc (1, sizeof (*data));
4253 data->costs[AINC_PRE_DEC] = INFTY;
4254 data->costs[AINC_POST_DEC] = INFTY;
4255 data->costs[AINC_PRE_INC] = INFTY;
4256 data->costs[AINC_POST_INC] = INFTY;
4257 if (USE_LOAD_PRE_DECREMENT (mem_mode)
4258 || USE_STORE_PRE_DECREMENT (mem_mode))
4259 {
4260 rtx addr = gen_rtx_PRE_DEC (addr_mode, reg);
4261
4262 if (memory_address_addr_space_p (mem_mode, addr, as))
4263 data->costs[AINC_PRE_DEC]
4264 = address_cost (addr, mem_mode, as, speed);
4265 }
4266 if (USE_LOAD_POST_DECREMENT (mem_mode)
4267 || USE_STORE_POST_DECREMENT (mem_mode))
4268 {
4269 rtx addr = gen_rtx_POST_DEC (addr_mode, reg);
4270
4271 if (memory_address_addr_space_p (mem_mode, addr, as))
4272 data->costs[AINC_POST_DEC]
4273 = address_cost (addr, mem_mode, as, speed);
4274 }
4275 if (USE_LOAD_PRE_INCREMENT (mem_mode)
4276 || USE_STORE_PRE_INCREMENT (mem_mode))
4277 {
4278 rtx addr = gen_rtx_PRE_INC (addr_mode, reg);
4279
4280 if (memory_address_addr_space_p (mem_mode, addr, as))
4281 data->costs[AINC_PRE_INC]
4282 = address_cost (addr, mem_mode, as, speed);
4283 }
4284 if (USE_LOAD_POST_INCREMENT (mem_mode)
4285 || USE_STORE_POST_INCREMENT (mem_mode))
4286 {
4287 rtx addr = gen_rtx_POST_INC (addr_mode, reg);
4288
4289 if (memory_address_addr_space_p (mem_mode, addr, as))
4290 data->costs[AINC_POST_INC]
4291 = address_cost (addr, mem_mode, as, speed);
4292 }
4293 ainc_cost_data_list[idx] =