Daily bump.
[official-gcc.git] / gcc / gimple-loop-versioning.cc
blob15e0803dc299bbe1cbf38d3c0da96bfabbb6f34f
1 /* Loop versioning pass.
2 Copyright (C) 2018-2021 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
9 later version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "tree.h"
25 #include "gimple.h"
26 #include "gimple-iterator.h"
27 #include "tree-pass.h"
28 #include "gimplify-me.h"
29 #include "cfgloop.h"
30 #include "tree-ssa-loop.h"
31 #include "ssa.h"
32 #include "tree-scalar-evolution.h"
33 #include "tree-ssa-loop-ivopts.h"
34 #include "fold-const.h"
35 #include "tree-ssa-propagate.h"
36 #include "tree-inline.h"
37 #include "domwalk.h"
38 #include "tree-vectorizer.h"
39 #include "omp-general.h"
40 #include "predict.h"
41 #include "tree-into-ssa.h"
42 #include "gimple-range.h"
43 #include "tree-cfg.h"
45 namespace {
47 /* This pass looks for loops that could be simplified if certain loop
48 invariant conditions were true. It is effectively a form of loop
49 splitting in which the pass produces the split conditions itself,
50 instead of using ones that are already present in the IL.
52 Versioning for when strides are 1
53 ---------------------------------
55 At the moment the only thing the pass looks for are memory references
56 like:
58 for (auto i : ...)
59 ...x[i * stride]...
61 It considers changing such loops to:
63 if (stride == 1)
64 for (auto i : ...) [A]
65 ...x[i]...
66 else
67 for (auto i : ...) [B]
68 ...x[i * stride]...
70 This can have several benefits:
72 (1) [A] is often easier or cheaper to vectorize than [B].
74 (2) The scalar code in [A] is simpler than the scalar code in [B]
75 (if the loops cannot be vectorized or need an epilogue loop).
77 (3) We might recognize [A] as a pattern, such as a memcpy or memset.
79 (4) [A] has simpler address evolutions, which can help other passes
80 like loop interchange.
82 The optimization is particularly useful for assumed-shape arrays in
83 Fortran, where the stride of the innermost dimension depends on the
84 array descriptor but is often equal to 1 in practice. For example:
86 subroutine f1(x)
87 real :: x(:)
88 x(:) = 100
89 end subroutine f1
91 generates the equivalent of:
93 raw_stride = *x.dim[0].stride;
94 stride = raw_stride != 0 ? raw_stride : 1;
95 x_base = *x.data;
96 ...
97 tmp1 = stride * S;
98 tmp2 = tmp1 - stride;
99 *x_base[tmp2] = 1.0e+2;
101 but in the common case that stride == 1, the last three statements
102 simplify to:
104 tmp3 = S + -1;
105 *x_base[tmp3] = 1.0e+2;
107 The optimization is in principle very simple. The difficult parts are:
109 (a) deciding which parts of a general address calculation correspond
110 to the inner dimension of an array, since this usually isn't explicit
111 in the IL, and for C often isn't even explicit in the source code
113 (b) estimating when the transformation is worthwhile
115 Structure
116 ---------
118 The pass has four phases:
120 (1) Walk through the statements looking for and recording potential
121 versioning opportunities. Stop if there are none.
123 (2) Use context-sensitive range information to see whether any versioning
124 conditions are impossible in practice. Remove them if so, and stop
125 if no opportunities remain.
127 (We do this only after (1) to keep compile time down when no
128 versioning opportunities exist.)
130 (3) Apply the cost model. Decide which versioning opportunities are
131 worthwhile and at which nesting level they should be applied.
133 (4) Attempt to version all the loops selected by (3), so that:
135 for (...)
138 becomes:
140 if (!cond)
141 for (...) // Original loop
143 else
144 for (...) // New loop
147 Use the version condition COND to simplify the new loop. */
149 /* Enumerates the likelihood that a particular value indexes the inner
150 dimension of an array. */
151 enum inner_likelihood {
152 INNER_UNLIKELY,
153 INNER_DONT_KNOW,
154 INNER_LIKELY
157 /* Information about one term of an address_info. */
158 struct address_term_info
160 /* The value of the term is EXPR * MULTIPLIER. */
161 tree expr;
162 unsigned HOST_WIDE_INT multiplier;
164 /* The stride applied by EXPR in each iteration of some unrecorded loop,
165 or null if no stride has been identified. */
166 tree stride;
168 /* Enumerates the likelihood that EXPR indexes the inner dimension
169 of an array. */
170 enum inner_likelihood inner_likelihood;
172 /* True if STRIDE == 1 is a versioning opportunity when considered
173 in isolation. */
174 bool versioning_opportunity_p;
177 /* Information about an address calculation, and the range of constant
178 offsets applied to it. */
179 class address_info
181 public:
182 static const unsigned int MAX_TERMS = 8;
184 /* One statement that calculates the address. If multiple statements
185 share the same address, we only record the first. */
186 gimple *stmt;
188 /* The loop containing STMT (cached for convenience). If multiple
189 statements share the same address, they all belong to this loop. */
190 class loop *loop;
192 /* A decomposition of the calculation into a sum of terms plus an
193 optional base. When BASE is provided, it is never an SSA name.
194 Once initialization is complete, all members of TERMs are SSA names. */
195 tree base;
196 auto_vec<address_term_info, MAX_TERMS> terms;
198 /* All bytes accessed from the address fall in the offset range
199 [MIN_OFFSET, MAX_OFFSET). */
200 HOST_WIDE_INT min_offset, max_offset;
203 /* Stores addresses based on their base and terms (ignoring the offsets). */
204 struct address_info_hasher : nofree_ptr_hash <address_info>
206 static hashval_t hash (const address_info *);
207 static bool equal (const address_info *, const address_info *);
210 /* Information about the versioning we'd like to apply to a loop. */
211 class loop_info
213 public:
214 bool worth_versioning_p () const;
216 /* True if we've decided not to version this loop. The remaining
217 fields are meaningless if so. */
218 bool rejected_p;
220 /* True if at least one subloop of this loop benefits from versioning. */
221 bool subloops_benefit_p;
223 /* An estimate of the total number of instructions in the loop,
224 excluding those in subloops that benefit from versioning. */
225 unsigned int num_insns;
227 /* The outermost loop that can handle all the version checks
228 described below. */
229 class loop *outermost;
231 /* The first entry in the list of blocks that belong to this loop
232 (and not to subloops). m_next_block_in_loop provides the chain
233 pointers for the list. */
234 basic_block block_list;
236 /* We'd like to version the loop for the case in which these SSA names
237 (keyed off their SSA_NAME_VERSION) are all equal to 1 at runtime. */
238 bitmap_head unity_names;
240 /* If versioning succeeds, this points the version of the loop that
241 assumes the version conditions holds. */
242 class loop *optimized_loop;
245 /* The main pass structure. */
246 class loop_versioning
248 public:
249 loop_versioning (function *);
250 ~loop_versioning ();
251 unsigned int run ();
253 private:
254 /* Used to walk the dominator tree to find loop versioning conditions
255 that are always false. */
256 class lv_dom_walker : public dom_walker
258 public:
259 lv_dom_walker (loop_versioning &);
261 edge before_dom_children (basic_block) FINAL OVERRIDE;
263 private:
264 /* The parent pass. */
265 loop_versioning &m_lv;
268 /* Used to simplify statements based on conditions that are established
269 by the version checks. */
270 class name_prop : public substitute_and_fold_engine
272 public:
273 name_prop (loop_info &li) : m_li (li) {}
274 tree value_of_expr (tree name, gimple *) FINAL OVERRIDE;
276 private:
277 /* Information about the versioning we've performed on the loop. */
278 loop_info &m_li;
281 loop_info &get_loop_info (class loop *loop) { return m_loops[loop->num]; }
283 unsigned int max_insns_for_loop (class loop *);
284 bool expensive_stmt_p (gimple *);
286 void version_for_unity (gimple *, tree);
287 bool acceptable_multiplier_p (tree, unsigned HOST_WIDE_INT,
288 unsigned HOST_WIDE_INT * = 0);
289 bool acceptable_type_p (tree, unsigned HOST_WIDE_INT *);
290 bool multiply_term_by (address_term_info &, tree);
291 inner_likelihood get_inner_likelihood (tree, unsigned HOST_WIDE_INT);
292 void dump_inner_likelihood (address_info &, address_term_info &);
293 void analyze_stride (address_info &, address_term_info &,
294 tree, class loop *);
295 bool find_per_loop_multiplication (address_info &, address_term_info &);
296 bool analyze_term_using_scevs (address_info &, address_term_info &);
297 void analyze_arbitrary_term (address_info &, address_term_info &);
298 void analyze_address_fragment (address_info &);
299 void record_address_fragment (gimple *, unsigned HOST_WIDE_INT,
300 tree, unsigned HOST_WIDE_INT, HOST_WIDE_INT);
301 void analyze_expr (gimple *, tree);
302 bool analyze_block (basic_block);
303 bool analyze_blocks ();
305 void prune_loop_conditions (class loop *);
306 bool prune_conditions ();
308 void merge_loop_info (class loop *, class loop *);
309 void add_loop_to_queue (class loop *);
310 bool decide_whether_loop_is_versionable (class loop *);
311 bool make_versioning_decisions ();
313 bool version_loop (class loop *);
314 void implement_versioning_decisions ();
316 /* The function we're optimizing. */
317 function *m_fn;
319 /* The obstack to use for all pass-specific bitmaps. */
320 bitmap_obstack m_bitmap_obstack;
322 /* An obstack to use for general allocation. */
323 obstack m_obstack;
325 /* The number of loops in the function. */
326 unsigned int m_nloops;
328 /* The total number of loop version conditions we've found. */
329 unsigned int m_num_conditions;
331 /* Assume that an address fragment of the form i * stride * scale
332 (for variable stride and constant scale) will not benefit from
333 versioning for stride == 1 when scale is greater than this value. */
334 unsigned HOST_WIDE_INT m_maximum_scale;
336 /* Information about each loop. */
337 auto_vec<loop_info> m_loops;
339 /* Used to form a linked list of blocks that belong to a loop,
340 started by loop_info::block_list. */
341 auto_vec<basic_block> m_next_block_in_loop;
343 /* The list of loops that we've decided to version. */
344 auto_vec<class loop *> m_loops_to_version;
346 /* A table of addresses in the current loop, keyed off their values
347 but not their offsets. */
348 hash_table <address_info_hasher> m_address_table;
350 /* A list of all addresses in M_ADDRESS_TABLE, in a predictable order. */
351 auto_vec <address_info *, 32> m_address_list;
354 /* If EXPR is an SSA name and not a default definition, return the
355 defining statement, otherwise return null. */
357 static gimple *
358 maybe_get_stmt (tree expr)
360 if (TREE_CODE (expr) == SSA_NAME && !SSA_NAME_IS_DEFAULT_DEF (expr))
361 return SSA_NAME_DEF_STMT (expr);
362 return NULL;
365 /* Like maybe_get_stmt, but also return null if the defining
366 statement isn't an assignment. */
368 static gassign *
369 maybe_get_assign (tree expr)
371 return safe_dyn_cast <gassign *> (maybe_get_stmt (expr));
374 /* Return true if this pass should look through a cast of expression FROM
375 to type TYPE when analyzing pieces of an address. */
377 static bool
378 look_through_cast_p (tree type, tree from)
380 return (INTEGRAL_TYPE_P (TREE_TYPE (from)) == INTEGRAL_TYPE_P (type)
381 && POINTER_TYPE_P (TREE_TYPE (from)) == POINTER_TYPE_P (type));
384 /* Strip all conversions of integers or pointers from EXPR, regardless
385 of whether the conversions are nops. This is useful in the context
386 of this pass because we're not trying to fold or simulate the
387 expression; we just want to see how it's structured. */
389 static tree
390 strip_casts (tree expr)
392 const unsigned int MAX_NITERS = 4;
394 tree type = TREE_TYPE (expr);
395 while (CONVERT_EXPR_P (expr)
396 && look_through_cast_p (type, TREE_OPERAND (expr, 0)))
397 expr = TREE_OPERAND (expr, 0);
399 for (unsigned int niters = 0; niters < MAX_NITERS; ++niters)
401 gassign *assign = maybe_get_assign (expr);
402 if (assign
403 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (assign))
404 && look_through_cast_p (type, gimple_assign_rhs1 (assign)))
405 expr = gimple_assign_rhs1 (assign);
406 else
407 break;
409 return expr;
412 /* Compare two address_term_infos in the same address_info. */
414 static int
415 compare_address_terms (const void *a_uncast, const void *b_uncast)
417 const address_term_info *a = (const address_term_info *) a_uncast;
418 const address_term_info *b = (const address_term_info *) b_uncast;
420 if (a->expr != b->expr)
421 return SSA_NAME_VERSION (a->expr) < SSA_NAME_VERSION (b->expr) ? -1 : 1;
423 if (a->multiplier != b->multiplier)
424 return a->multiplier < b->multiplier ? -1 : 1;
426 return 0;
429 /* Dump ADDRESS using flags FLAGS. */
431 static void
432 dump_address_info (dump_flags_t flags, address_info &address)
434 if (address.base)
435 dump_printf (flags, "%T + ", address.base);
436 for (unsigned int i = 0; i < address.terms.length (); ++i)
438 if (i != 0)
439 dump_printf (flags, " + ");
440 dump_printf (flags, "%T", address.terms[i].expr);
441 if (address.terms[i].multiplier != 1)
442 dump_printf (flags, " * %wd", address.terms[i].multiplier);
444 dump_printf (flags, " + [%wd, %wd]",
445 address.min_offset, address.max_offset - 1);
448 /* Hash an address_info based on its base and terms. */
450 hashval_t
451 address_info_hasher::hash (const address_info *info)
453 inchash::hash hash;
454 hash.add_int (info->base ? TREE_CODE (info->base) : 0);
455 hash.add_int (info->terms.length ());
456 for (unsigned int i = 0; i < info->terms.length (); ++i)
458 hash.add_int (SSA_NAME_VERSION (info->terms[i].expr));
459 hash.add_hwi (info->terms[i].multiplier);
461 return hash.end ();
464 /* Return true if two address_infos have equal bases and terms. Other
465 properties might be different (such as the statement or constant
466 offset range). */
468 bool
469 address_info_hasher::equal (const address_info *a, const address_info *b)
471 if (a->base != b->base
472 && (!a->base || !b->base || !operand_equal_p (a->base, b->base, 0)))
473 return false;
475 if (a->terms.length () != b->terms.length ())
476 return false;
478 for (unsigned int i = 0; i < a->terms.length (); ++i)
479 if (a->terms[i].expr != b->terms[i].expr
480 || a->terms[i].multiplier != b->terms[i].multiplier)
481 return false;
483 return true;
486 /* Return true if we want to version the loop, i.e. if we have a
487 specific reason for doing so and no specific reason not to. */
489 bool
490 loop_info::worth_versioning_p () const
492 return (!rejected_p
493 && (!bitmap_empty_p (&unity_names) || subloops_benefit_p));
496 loop_versioning::lv_dom_walker::lv_dom_walker (loop_versioning &lv)
497 : dom_walker (CDI_DOMINATORS), m_lv (lv)
501 /* Process BB before processing the blocks it dominates. */
503 edge
504 loop_versioning::lv_dom_walker::before_dom_children (basic_block bb)
506 if (bb == bb->loop_father->header)
507 m_lv.prune_loop_conditions (bb->loop_father);
509 return NULL;
512 /* Decide whether to replace VAL with a new value in a versioned loop.
513 Return the new value if so, otherwise return null. */
515 tree
516 loop_versioning::name_prop::value_of_expr (tree val, gimple *)
518 if (TREE_CODE (val) == SSA_NAME
519 && bitmap_bit_p (&m_li.unity_names, SSA_NAME_VERSION (val)))
520 return build_one_cst (TREE_TYPE (val));
521 return NULL_TREE;
524 /* Initialize the structure to optimize FN. */
526 loop_versioning::loop_versioning (function *fn)
527 : m_fn (fn),
528 m_nloops (number_of_loops (fn)),
529 m_num_conditions (0),
530 m_address_table (31)
532 bitmap_obstack_initialize (&m_bitmap_obstack);
533 gcc_obstack_init (&m_obstack);
535 /* Initialize the loop information. */
536 m_loops.safe_grow_cleared (m_nloops, true);
537 for (unsigned int i = 0; i < m_nloops; ++i)
539 m_loops[i].outermost = get_loop (m_fn, 0);
540 bitmap_initialize (&m_loops[i].unity_names, &m_bitmap_obstack);
543 /* Initialize the list of blocks that belong to each loop. */
544 unsigned int nbbs = last_basic_block_for_fn (fn);
545 m_next_block_in_loop.safe_grow (nbbs, true);
546 basic_block bb;
547 FOR_EACH_BB_FN (bb, fn)
549 loop_info &li = get_loop_info (bb->loop_father);
550 m_next_block_in_loop[bb->index] = li.block_list;
551 li.block_list = bb;
554 /* MAX_FIXED_MODE_SIZE should be a reasonable maximum scale for
555 unvectorizable code, since it is the largest size that can be
556 handled efficiently by scalar code. omp_max_vf calculates the
557 maximum number of bytes in a vector, when such a value is relevant
558 to loop optimization. */
559 m_maximum_scale = estimated_poly_value (omp_max_vf ());
560 m_maximum_scale = MAX (m_maximum_scale, MAX_FIXED_MODE_SIZE);
563 loop_versioning::~loop_versioning ()
565 bitmap_obstack_release (&m_bitmap_obstack);
566 obstack_free (&m_obstack, NULL);
569 /* Return the maximum number of instructions allowed in LOOP before
570 it becomes too big for versioning.
572 There are separate limits for inner and outer loops. The limit for
573 inner loops applies only to loops that benefit directly from versioning.
574 The limit for outer loops applies to all code in the outer loop and
575 its subloops that *doesn't* benefit directly from versioning; such code
576 would be "taken along for the ride". The idea is that if the cost of
577 the latter is small, it is better to version outer loops rather than
578 inner loops, both to reduce the number of repeated checks and to enable
579 more of the loop nest to be optimized as a natural nest (e.g. by loop
580 interchange or outer-loop vectorization). */
582 unsigned int
583 loop_versioning::max_insns_for_loop (class loop *loop)
585 return (loop->inner
586 ? param_loop_versioning_max_outer_insns
587 : param_loop_versioning_max_inner_insns);
590 /* Return true if for cost reasons we should avoid versioning any loop
591 that contains STMT.
593 Note that we don't need to check whether versioning is invalid for
594 correctness reasons, since the versioning process does that for us.
595 The conditions involved are too rare to be worth duplicating here. */
597 bool
598 loop_versioning::expensive_stmt_p (gimple *stmt)
600 if (gcall *call = dyn_cast <gcall *> (stmt))
601 /* Assume for now that the time spent in an "expensive" call would
602 overwhelm any saving from versioning. */
603 return !gimple_inexpensive_call_p (call);
604 return false;
607 /* Record that we want to version the loop that contains STMT for the
608 case in which SSA name NAME is equal to 1. We already know that NAME
609 is invariant in the loop. */
611 void
612 loop_versioning::version_for_unity (gimple *stmt, tree name)
614 class loop *loop = loop_containing_stmt (stmt);
615 loop_info &li = get_loop_info (loop);
617 if (bitmap_set_bit (&li.unity_names, SSA_NAME_VERSION (name)))
619 /* This is the first time we've wanted to version LOOP for NAME.
620 Keep track of the outermost loop that can handle all versioning
621 checks in LI. */
622 class loop *outermost
623 = outermost_invariant_loop_for_expr (loop, name);
624 if (loop_depth (li.outermost) < loop_depth (outermost))
625 li.outermost = outermost;
627 if (dump_enabled_p ())
629 dump_printf_loc (MSG_NOTE, stmt, "want to version containing loop"
630 " for when %T == 1", name);
631 if (outermost == loop)
632 dump_printf (MSG_NOTE, "; cannot hoist check further");
633 else
635 dump_printf (MSG_NOTE, "; could implement the check at loop"
636 " depth %d", loop_depth (outermost));
637 if (loop_depth (li.outermost) > loop_depth (outermost))
638 dump_printf (MSG_NOTE, ", but other checks only allow"
639 " a depth of %d", loop_depth (li.outermost));
641 dump_printf (MSG_NOTE, "\n");
644 m_num_conditions += 1;
646 else
648 /* This is a duplicate request. */
649 if (dump_enabled_p ())
650 dump_printf_loc (MSG_NOTE, stmt, "already asked to version containing"
651 " loop for when %T == 1\n", name);
655 /* Return true if OP1_TREE is constant and if in principle it is worth
656 versioning an address fragment of the form:
658 i * OP1_TREE * OP2 * stride
660 for the case in which stride == 1. This in practice means testing
661 whether:
663 OP1_TREE * OP2 <= M_MAXIMUM_SCALE.
665 If RESULT is nonnull, store OP1_TREE * OP2 there when returning true. */
667 bool
668 loop_versioning::acceptable_multiplier_p (tree op1_tree,
669 unsigned HOST_WIDE_INT op2,
670 unsigned HOST_WIDE_INT *result)
672 if (tree_fits_uhwi_p (op1_tree))
674 unsigned HOST_WIDE_INT op1 = tree_to_uhwi (op1_tree);
675 /* The first part checks for overflow. */
676 if (op1 * op2 >= op2 && op1 * op2 <= m_maximum_scale)
678 if (result)
679 *result = op1 * op2;
680 return true;
683 return false;
686 /* Return true if it is worth using loop versioning on a memory access
687 of type TYPE. Store the size of the access in *SIZE if so. */
689 bool
690 loop_versioning::acceptable_type_p (tree type, unsigned HOST_WIDE_INT *size)
692 return (TYPE_SIZE_UNIT (type)
693 && acceptable_multiplier_p (TYPE_SIZE_UNIT (type), 1, size));
696 /* See whether OP is constant and whether we can multiply TERM by that
697 constant without exceeding M_MAXIMUM_SCALE. Return true and update
698 TERM if so. */
700 bool
701 loop_versioning::multiply_term_by (address_term_info &term, tree op)
703 return acceptable_multiplier_p (op, term.multiplier, &term.multiplier);
706 /* Decide whether an address fragment of the form STRIDE * MULTIPLIER
707 is likely to be indexing an innermost dimension, returning the result
708 as an INNER_* probability. */
710 inner_likelihood
711 loop_versioning::get_inner_likelihood (tree stride,
712 unsigned HOST_WIDE_INT multiplier)
714 const unsigned int MAX_NITERS = 8;
716 /* Iterate over possible values of STRIDE. Return INNER_LIKELY if at
717 least one of those values is likely to be for the innermost dimension.
718 Record in UNLIKELY_P if at least one of those values is unlikely to be
719 for the innermost dimension.
721 E.g. for:
723 stride = cond ? a * b : 1
725 we should treat STRIDE as being a likely inner dimension, since
726 we know that it is 1 under at least some circumstances. (See the
727 Fortran example below.) However:
729 stride = a * b
731 on its own is unlikely to be for the innermost dimension, since
732 that would require both a and b to be 1 at runtime. */
733 bool unlikely_p = false;
734 tree worklist[MAX_NITERS];
735 unsigned int length = 0;
736 worklist[length++] = stride;
737 for (unsigned int i = 0; i < length; ++i)
739 tree expr = worklist[i];
741 if (CONSTANT_CLASS_P (expr))
743 /* See if EXPR * MULTIPLIER would be consistent with an individual
744 access or a small grouped access. */
745 if (acceptable_multiplier_p (expr, multiplier))
746 return INNER_LIKELY;
747 else
748 unlikely_p = true;
750 else if (gimple *stmt = maybe_get_stmt (expr))
752 /* If EXPR is set by a PHI node, queue its arguments in case
753 we find one that is consistent with an inner dimension.
755 An important instance of this is the Fortran handling of array
756 descriptors, which calculates the stride of the inner dimension
757 using a PHI equivalent of:
759 raw_stride = a.dim[0].stride;
760 stride = raw_stride != 0 ? raw_stride : 1;
762 (Strides for outer dimensions do not treat 0 specially.) */
763 if (gphi *phi = dyn_cast <gphi *> (stmt))
765 unsigned int nargs = gimple_phi_num_args (phi);
766 for (unsigned int j = 0; j < nargs && length < MAX_NITERS; ++j)
767 worklist[length++] = strip_casts (gimple_phi_arg_def (phi, j));
769 /* If the value is set by an assignment, expect it to be read
770 from memory (such as an array descriptor) rather than be
771 calculated. */
772 else if (gassign *assign = dyn_cast <gassign *> (stmt))
774 if (!gimple_assign_load_p (assign))
775 unlikely_p = true;
777 /* Things like calls don't really tell us anything. */
781 /* We didn't find any possible values of STRIDE that were likely to be
782 for the innermost dimension. If we found one that was actively
783 unlikely to be for the innermost dimension, assume that that applies
784 to STRIDE too. */
785 return unlikely_p ? INNER_UNLIKELY : INNER_DONT_KNOW;
788 /* Dump the likelihood that TERM's stride is for the innermost dimension.
789 ADDRESS is the address that contains TERM. */
791 void
792 loop_versioning::dump_inner_likelihood (address_info &address,
793 address_term_info &term)
795 if (term.inner_likelihood == INNER_LIKELY)
796 dump_printf_loc (MSG_NOTE, address.stmt, "%T is likely to be the"
797 " innermost dimension\n", term.stride);
798 else if (term.inner_likelihood == INNER_UNLIKELY)
799 dump_printf_loc (MSG_NOTE, address.stmt, "%T is probably not the"
800 " innermost dimension\n", term.stride);
801 else
802 dump_printf_loc (MSG_NOTE, address.stmt, "cannot tell whether %T"
803 " is the innermost dimension\n", term.stride);
806 /* The caller has identified that STRIDE is the stride of interest
807 in TERM, and that the stride is applied in OP_LOOP. Record this
808 information in TERM, deciding whether STRIDE is likely to be for
809 the innermost dimension of an array and whether it represents a
810 versioning opportunity. ADDRESS is the address that contains TERM. */
812 void
813 loop_versioning::analyze_stride (address_info &address,
814 address_term_info &term,
815 tree stride, class loop *op_loop)
817 term.stride = stride;
819 term.inner_likelihood = get_inner_likelihood (stride, term.multiplier);
820 if (dump_enabled_p ())
821 dump_inner_likelihood (address, term);
823 /* To be a versioning opportunity we require:
825 - The multiplier applied by TERM is equal to the access size,
826 so that when STRIDE is 1, the accesses in successive loop
827 iterations are consecutive.
829 This is deliberately conservative. We could relax it to handle
830 other cases (such as those with gaps between iterations) if we
831 find any real testcases for which it's useful.
833 - the stride is applied in the same loop as STMT rather than
834 in an outer loop. Although versioning for strides applied in
835 outer loops could help in some cases -- such as enabling
836 more loop interchange -- the savings are much lower than for
837 inner loops.
839 - the stride is an SSA name that is invariant in STMT's loop,
840 since otherwise versioning isn't possible. */
841 unsigned HOST_WIDE_INT access_size = address.max_offset - address.min_offset;
842 if (term.multiplier == access_size
843 && address.loop == op_loop
844 && TREE_CODE (stride) == SSA_NAME
845 && expr_invariant_in_loop_p (address.loop, stride))
847 term.versioning_opportunity_p = true;
848 if (dump_enabled_p ())
849 dump_printf_loc (MSG_NOTE, address.stmt, "%T == 1 is a versioning"
850 " opportunity\n", stride);
854 /* See whether address term TERM (which belongs to ADDRESS) is the result
855 of multiplying a varying SSA name by a loop-invariant SSA name.
856 Return true and update TERM if so.
858 This handles both cases that SCEV might handle, such as:
860 for (int i = 0; i < n; ++i)
861 res += a[i * stride];
863 and ones in which the term varies arbitrarily between iterations, such as:
865 for (int i = 0; i < n; ++i)
866 res += a[index[i] * stride]; */
868 bool
869 loop_versioning::find_per_loop_multiplication (address_info &address,
870 address_term_info &term)
872 gassign *mult = maybe_get_assign (term.expr);
873 if (!mult || gimple_assign_rhs_code (mult) != MULT_EXPR)
874 return false;
876 class loop *mult_loop = loop_containing_stmt (mult);
877 if (!loop_outer (mult_loop))
878 return false;
880 tree op1 = strip_casts (gimple_assign_rhs1 (mult));
881 tree op2 = strip_casts (gimple_assign_rhs2 (mult));
882 if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
883 return false;
885 bool invariant1_p = expr_invariant_in_loop_p (mult_loop, op1);
886 bool invariant2_p = expr_invariant_in_loop_p (mult_loop, op2);
887 if (invariant1_p == invariant2_p)
888 return false;
890 /* Make sure that the loop invariant is OP2 rather than OP1. */
891 if (invariant1_p)
892 std::swap (op1, op2);
894 if (dump_enabled_p ())
895 dump_printf_loc (MSG_NOTE, address.stmt, "address term %T = varying %T"
896 " * loop-invariant %T\n", term.expr, op1, op2);
897 analyze_stride (address, term, op2, mult_loop);
898 return true;
901 /* Try to use scalar evolutions to find an address stride for TERM,
902 which belongs to ADDRESS. Return true and update TERM if so.
904 Here we are interested in any evolution information we can find,
905 not just evolutions wrt ADDRESS->LOOP. For example, if we find that
906 an outer loop obviously iterates over the inner dimension of an array,
907 that information can help us eliminate worthless versioning opportunities
908 in inner loops. */
910 bool
911 loop_versioning::analyze_term_using_scevs (address_info &address,
912 address_term_info &term)
914 gimple *setter = maybe_get_stmt (term.expr);
915 if (!setter)
916 return false;
918 class loop *wrt_loop = loop_containing_stmt (setter);
919 if (!loop_outer (wrt_loop))
920 return false;
922 tree chrec = strip_casts (analyze_scalar_evolution (wrt_loop, term.expr));
923 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
925 if (dump_enabled_p ())
926 dump_printf_loc (MSG_NOTE, address.stmt,
927 "address term %T = %T\n", term.expr, chrec);
929 /* Peel casts and accumulate constant multiplications, up to the
930 limit allowed by M_MAXIMUM_SCALE. */
931 tree stride = strip_casts (CHREC_RIGHT (chrec));
932 while (TREE_CODE (stride) == MULT_EXPR
933 && multiply_term_by (term, TREE_OPERAND (stride, 1)))
934 stride = strip_casts (TREE_OPERAND (stride, 0));
936 gassign *assign;
937 while ((assign = maybe_get_assign (stride))
938 && gimple_assign_rhs_code (assign) == MULT_EXPR
939 && multiply_term_by (term, gimple_assign_rhs2 (assign)))
941 if (dump_enabled_p ())
942 dump_printf_loc (MSG_NOTE, address.stmt,
943 "looking through %G", assign);
944 stride = strip_casts (gimple_assign_rhs1 (assign));
947 analyze_stride (address, term, stride, get_chrec_loop (chrec));
948 return true;
951 return false;
954 /* Address term TERM is an arbitrary term that provides no versioning
955 opportunities. Analyze it to see whether it contains any likely
956 inner strides, so that we don't mistakenly version for other
957 (less likely) candidates.
959 This copes with invariant innermost indices such as:
961 x(i, :) = 100
963 where the "i" component of the address is invariant in the loop
964 but provides the real inner stride.
966 ADDRESS is the address that contains TERM. */
968 void
969 loop_versioning::analyze_arbitrary_term (address_info &address,
970 address_term_info &term)
973 /* A multiplication offers two potential strides. Pick the one that
974 is most likely to be an innermost stride. */
975 tree expr = term.expr, alt = NULL_TREE;
976 gassign *mult = maybe_get_assign (expr);
977 if (mult && gimple_assign_rhs_code (mult) == MULT_EXPR)
979 expr = strip_casts (gimple_assign_rhs1 (mult));
980 alt = strip_casts (gimple_assign_rhs2 (mult));
982 term.stride = expr;
983 term.inner_likelihood = get_inner_likelihood (expr, term.multiplier);
984 if (alt)
986 inner_likelihood alt_l = get_inner_likelihood (alt, term.multiplier);
987 if (alt_l > term.inner_likelihood)
989 term.stride = alt;
990 term.inner_likelihood = alt_l;
993 if (dump_enabled_p ())
994 dump_inner_likelihood (address, term);
997 /* Try to identify loop strides in ADDRESS and try to choose realistic
998 versioning opportunities based on these strides.
1000 The main difficulty here isn't finding strides that could be used
1001 in a version check (that's pretty easy). The problem instead is to
1002 avoid versioning for some stride S that is unlikely ever to be 1 at
1003 runtime. Versioning for S == 1 on its own would lead to unnecessary
1004 code bloat, while adding S == 1 to more realistic version conditions
1005 would lose the optimisation opportunity offered by those other conditions.
1007 For example, versioning for a stride of 1 in the Fortran code:
1009 integer :: a(:,:)
1010 a(1,:) = 1
1012 is not usually a good idea, since the assignment is iterating over
1013 an outer dimension and is relatively unlikely to have a stride of 1.
1014 (It isn't impossible, since the inner dimension might be 1, or the
1015 array might be transposed.) Similarly, in:
1017 integer :: a(:,:), b(:,:)
1018 b(:,1) = a(1,:)
1020 b(:,1) is relatively likely to have a stride of 1 while a(1,:) isn't.
1021 Versioning for when both strides are 1 would lose most of the benefit
1022 of versioning for b's access.
1024 The approach we take is as follows:
1026 - Analyze each term to see whether it has an identifiable stride,
1027 regardless of which loop applies the stride.
1029 - Evaluate the likelihood that each such stride is for the innermost
1030 dimension of an array, on the scale "likely", "don't know" or "unlikely".
1032 - If there is a single "likely" innermost stride, and that stride is
1033 applied in the loop that contains STMT, version the loop for when the
1034 stride is 1. This deals with the cases in which we're fairly
1035 confident of doing the right thing, such as the b(:,1) reference above.
1037 - If there are no "likely" innermost strides, and the loop that contains
1038 STMT uses a stride that we rated as "don't know", version for when
1039 that stride is 1. This is principally used for C code such as:
1041 for (int i = 0; i < n; ++i)
1042 a[i * x] = ...;
1044 and:
1046 for (int j = 0; j < n; ++j)
1047 for (int i = 0; i < n; ++i)
1048 a[i * x + j * y] = ...;
1050 where nothing in the way "x" and "y" are set gives a hint as to
1051 whether "i" iterates over the innermost dimension of the array.
1052 In these situations it seems reasonable to assume the
1053 programmer has nested the loops appropriately (although of course
1054 there are examples like GEMM in which this assumption doesn't hold
1055 for all accesses in the loop).
1057 This case is also useful for the Fortran equivalent of the
1058 above C code. */
1060 void
1061 loop_versioning::analyze_address_fragment (address_info &address)
1063 if (dump_enabled_p ())
1065 dump_printf_loc (MSG_NOTE, address.stmt, "analyzing address fragment ");
1066 dump_address_info (MSG_NOTE, address);
1067 dump_printf (MSG_NOTE, "\n");
1070 /* Analyze each component of the sum to see whether it involves an
1071 apparent stride.
1073 There is an overlap between the addresses that
1074 find_per_loop_multiplication and analyze_term_using_scevs can handle,
1075 but the former is much cheaper than SCEV analysis, so try it first. */
1076 for (unsigned int i = 0; i < address.terms.length (); ++i)
1077 if (!find_per_loop_multiplication (address, address.terms[i])
1078 && !analyze_term_using_scevs (address, address.terms[i])
1079 && !POINTER_TYPE_P (TREE_TYPE (address.terms[i].expr)))
1080 analyze_arbitrary_term (address, address.terms[i]);
1082 /* Check for strides that are likely to be for the innermost dimension.
1084 1. If there is a single likely inner stride, if it is an SSA name,
1085 and if it is worth versioning the loop for when the SSA name
1086 equals 1, record that we want to do so.
1088 2. Otherwise, if there any likely inner strides, bail out. This means
1089 one of:
1091 (a) There are multiple likely inner strides. This suggests we're
1092 confused and be can't be confident of doing the right thing.
1094 (b) There is a single likely inner stride and it is a constant
1095 rather than an SSA name. This can mean either that the access
1096 is a natural one without any variable strides, such as:
1098 for (int i = 0; i < n; ++i)
1099 a[i] += 1;
1101 or that a variable stride is applied to an outer dimension,
1102 such as:
1104 for (int i = 0; i < n; ++i)
1105 for (int j = 0; j < n; ++j)
1106 a[j * stride][i] += 1;
1108 (c) There is a single likely inner stride, and it is an SSA name,
1109 but it isn't a worthwhile versioning opportunity. This usually
1110 means that the variable stride is applied by an outer loop,
1111 such as:
1113 for (int i = 0; i < n; ++i)
1114 for (int j = 0; j < n; ++j)
1115 a[j][i * stride] += 1;
1117 or (using an example with a more natural loop nesting):
1119 for (int i = 0; i < n; ++i)
1120 for (int j = 0; j < n; ++j)
1121 a[i][j] += b[i * stride];
1123 in cases where b[i * stride] cannot (yet) be hoisted for
1124 aliasing reasons.
1126 3. If there are no likely inner strides, fall through to the next
1127 set of checks.
1129 Pointer equality is enough to check for uniqueness in (1), since we
1130 only care about SSA names. */
1131 tree chosen_stride = NULL_TREE;
1132 tree version_stride = NULL_TREE;
1133 for (unsigned int i = 0; i < address.terms.length (); ++i)
1134 if (chosen_stride != address.terms[i].stride
1135 && address.terms[i].inner_likelihood == INNER_LIKELY)
1137 if (chosen_stride)
1138 return;
1139 chosen_stride = address.terms[i].stride;
1140 if (address.terms[i].versioning_opportunity_p)
1141 version_stride = chosen_stride;
1144 /* If there are no likely inner strides, see if there is a single
1145 versioning opportunity for a stride that was rated as INNER_DONT_KNOW.
1146 See the comment above the function for the cases that this code
1147 handles. */
1148 if (!chosen_stride)
1149 for (unsigned int i = 0; i < address.terms.length (); ++i)
1150 if (version_stride != address.terms[i].stride
1151 && address.terms[i].inner_likelihood == INNER_DONT_KNOW
1152 && address.terms[i].versioning_opportunity_p)
1154 if (version_stride)
1155 return;
1156 version_stride = address.terms[i].stride;
1159 if (version_stride)
1160 version_for_unity (address.stmt, version_stride);
1163 /* Treat EXPR * MULTIPLIER + OFFSET as a fragment of an address that addresses
1164 TYPE_SIZE bytes and record this address fragment for later processing.
1165 STMT is the statement that contains the address. */
1167 void
1168 loop_versioning::record_address_fragment (gimple *stmt,
1169 unsigned HOST_WIDE_INT type_size,
1170 tree expr,
1171 unsigned HOST_WIDE_INT multiplier,
1172 HOST_WIDE_INT offset)
1174 /* We're only interested in computed values. */
1175 if (TREE_CODE (expr) != SSA_NAME)
1176 return;
1178 /* Quick exit if no part of the address is calculated in STMT's loop,
1179 since such addresses have no versioning opportunities. */
1180 class loop *loop = loop_containing_stmt (stmt);
1181 if (expr_invariant_in_loop_p (loop, expr))
1182 return;
1184 /* Set up an address_info for EXPR * MULTIPLIER. */
1185 address_info *address = XOBNEW (&m_obstack, address_info);
1186 new (address) address_info;
1187 address->stmt = stmt;
1188 address->loop = loop;
1189 address->base = NULL_TREE;
1190 address->terms.quick_grow (1);
1191 address->terms[0].expr = expr;
1192 address->terms[0].multiplier = multiplier;
1193 address->terms[0].stride = NULL_TREE;
1194 address->terms[0].inner_likelihood = INNER_UNLIKELY;
1195 address->terms[0].versioning_opportunity_p = false;
1196 address->min_offset = offset;
1198 /* Peel apart the expression into a sum of address_terms, where each
1199 term is multiplied by a constant. Treat a + b and a - b the same,
1200 since it doesn't matter for our purposes whether an address is
1201 increasing or decreasing. Distribute (a + b) * constant into
1202 a * constant + b * constant.
1204 We don't care which loop each term belongs to, since we want to
1205 examine as many candidate strides as possible when determining
1206 which is likely to be for the innermost dimension. We therefore
1207 don't limit the search to statements in STMT's loop. */
1208 for (unsigned int i = 0; i < address->terms.length (); )
1210 if (gassign *assign = maybe_get_assign (address->terms[i].expr))
1212 tree_code code = gimple_assign_rhs_code (assign);
1213 if (code == PLUS_EXPR
1214 || code == POINTER_PLUS_EXPR
1215 || code == MINUS_EXPR)
1217 tree op1 = gimple_assign_rhs1 (assign);
1218 tree op2 = gimple_assign_rhs2 (assign);
1219 if (TREE_CODE (op2) == INTEGER_CST)
1221 address->terms[i].expr = strip_casts (op1);
1222 /* This is heuristic only, so don't worry about truncation
1223 or overflow. */
1224 address->min_offset += (TREE_INT_CST_LOW (op2)
1225 * address->terms[i].multiplier);
1226 continue;
1228 else if (address->terms.length () < address_info::MAX_TERMS)
1230 unsigned int j = address->terms.length ();
1231 address->terms.quick_push (address->terms[i]);
1232 address->terms[i].expr = strip_casts (op1);
1233 address->terms[j].expr = strip_casts (op2);
1234 continue;
1237 if (code == MULT_EXPR)
1239 tree op1 = gimple_assign_rhs1 (assign);
1240 tree op2 = gimple_assign_rhs2 (assign);
1241 if (multiply_term_by (address->terms[i], op2))
1243 address->terms[i].expr = strip_casts (op1);
1244 continue;
1247 if (CONVERT_EXPR_CODE_P (code))
1249 tree op1 = gimple_assign_rhs1 (assign);
1250 address->terms[i].expr = strip_casts (op1);
1251 continue;
1254 i += 1;
1257 /* Peel off any symbolic pointer. */
1258 if (TREE_CODE (address->terms[0].expr) != SSA_NAME
1259 && address->terms[0].multiplier == 1)
1261 if (address->terms.length () == 1)
1263 obstack_free (&m_obstack, address);
1264 return;
1266 address->base = address->terms[0].expr;
1267 address->terms.ordered_remove (0);
1270 /* Require all remaining terms to be SSA names. (This could be false
1271 for unfolded statements, but they aren't worth dealing with.) */
1272 for (unsigned int i = 0; i < address->terms.length (); ++i)
1273 if (TREE_CODE (address->terms[i].expr) != SSA_NAME)
1275 obstack_free (&m_obstack, address);
1276 return;
1279 /* The loop above set MIN_OFFSET based on the first byte of the
1280 referenced data. Calculate the end + 1. */
1281 address->max_offset = address->min_offset + type_size;
1283 /* Put the terms into a canonical order for the hash table lookup below. */
1284 address->terms.qsort (compare_address_terms);
1286 if (dump_enabled_p ())
1288 dump_printf_loc (MSG_NOTE, stmt, "recording address fragment %T", expr);
1289 if (multiplier != 1)
1290 dump_printf (MSG_NOTE, " * %wd", multiplier);
1291 dump_printf (MSG_NOTE, " = ");
1292 dump_address_info (MSG_NOTE, *address);
1293 dump_printf (MSG_NOTE, "\n");
1296 /* Pool address information with the same terms (but potentially
1297 different offsets). */
1298 address_info **slot = m_address_table.find_slot (address, INSERT);
1299 if (address_info *old_address = *slot)
1301 /* We've already seen an address with the same terms. Extend the
1302 offset range to account for this access. Doing this can paper
1303 over gaps, such as in:
1305 a[i * stride * 4] + a[i * stride * 4 + 3];
1307 where nothing references "+ 1" or "+ 2". However, the vectorizer
1308 handles such gapped accesses without problems, so it's not worth
1309 trying to exclude them. */
1310 if (old_address->min_offset > address->min_offset)
1311 old_address->min_offset = address->min_offset;
1312 if (old_address->max_offset < address->max_offset)
1313 old_address->max_offset = address->max_offset;
1314 obstack_free (&m_obstack, address);
1316 else
1318 /* This is the first time we've seen an address with these terms. */
1319 *slot = address;
1320 m_address_list.safe_push (address);
1324 /* Analyze expression EXPR, which occurs in STMT. */
1326 void
1327 loop_versioning::analyze_expr (gimple *stmt, tree expr)
1329 unsigned HOST_WIDE_INT type_size;
1331 while (handled_component_p (expr))
1333 /* See whether we can use versioning to avoid a multiplication
1334 in an array index. */
1335 if (TREE_CODE (expr) == ARRAY_REF
1336 && acceptable_type_p (TREE_TYPE (expr), &type_size))
1337 record_address_fragment (stmt, type_size,
1338 TREE_OPERAND (expr, 1), type_size, 0);
1339 expr = TREE_OPERAND (expr, 0);
1342 /* See whether we can use versioning to avoid a multiplication
1343 in the pointer calculation of a MEM_REF. */
1344 if (TREE_CODE (expr) == MEM_REF
1345 && acceptable_type_p (TREE_TYPE (expr), &type_size))
1346 record_address_fragment (stmt, type_size, TREE_OPERAND (expr, 0), 1,
1347 /* This is heuristic only, so don't worry
1348 about truncation or overflow. */
1349 TREE_INT_CST_LOW (TREE_OPERAND (expr, 1)));
1351 /* These would be easy to handle if they existed at this stage. */
1352 gcc_checking_assert (TREE_CODE (expr) != TARGET_MEM_REF);
1355 /* Analyze all the statements in BB looking for useful version checks.
1356 Return true on success, false if something prevents the block from
1357 being versioned. */
1359 bool
1360 loop_versioning::analyze_block (basic_block bb)
1362 class loop *loop = bb->loop_father;
1363 loop_info &li = get_loop_info (loop);
1364 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1365 gsi_next (&gsi))
1367 gimple *stmt = gsi_stmt (gsi);
1368 if (is_gimple_debug (stmt))
1369 continue;
1371 if (expensive_stmt_p (stmt))
1373 if (dump_enabled_p ())
1374 dump_printf_loc (MSG_NOTE, stmt, "expensive statement"
1375 " prevents versioning: %G", stmt);
1376 return false;
1379 /* Only look for direct versioning opportunities in inner loops
1380 since the benefit tends to be much smaller for outer loops. */
1381 if (!loop->inner)
1383 unsigned int nops = gimple_num_ops (stmt);
1384 for (unsigned int i = 0; i < nops; ++i)
1385 if (tree op = gimple_op (stmt, i))
1386 analyze_expr (stmt, op);
1389 /* The point of the instruction limit is to prevent excessive
1390 code growth, so this is a size-based estimate even though
1391 the optimization is aimed at speed. */
1392 li.num_insns += estimate_num_insns (stmt, &eni_size_weights);
1395 return true;
1398 /* Analyze all the blocks in the function, looking for useful version checks.
1399 Return true if we found one. */
1401 bool
1402 loop_versioning::analyze_blocks ()
1404 AUTO_DUMP_SCOPE ("analyze_blocks",
1405 dump_user_location_t::from_function_decl (m_fn->decl));
1407 /* For now we don't try to version the whole function, although
1408 versioning at that level could be useful in some cases. */
1409 get_loop_info (get_loop (m_fn, 0)).rejected_p = true;
1411 for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1413 loop_info &linfo = get_loop_info (loop);
1415 /* Ignore cold loops. */
1416 if (!optimize_loop_for_speed_p (loop))
1417 linfo.rejected_p = true;
1419 /* See whether an inner loop prevents versioning of this loop. */
1420 if (!linfo.rejected_p)
1421 for (class loop *inner = loop->inner; inner; inner = inner->next)
1422 if (get_loop_info (inner).rejected_p)
1424 linfo.rejected_p = true;
1425 break;
1428 /* If versioning the loop is still a possibility, examine the
1429 statements in the loop to look for versioning opportunities. */
1430 if (!linfo.rejected_p)
1432 void *start_point = obstack_alloc (&m_obstack, 0);
1434 for (basic_block bb = linfo.block_list; bb;
1435 bb = m_next_block_in_loop[bb->index])
1436 if (!analyze_block (bb))
1438 linfo.rejected_p = true;
1439 break;
1442 if (!linfo.rejected_p)
1444 /* Process any queued address fragments, now that we have
1445 complete grouping information. */
1446 address_info *address;
1447 unsigned int i;
1448 FOR_EACH_VEC_ELT (m_address_list, i, address)
1449 analyze_address_fragment (*address);
1452 m_address_table.empty ();
1453 m_address_list.truncate (0);
1454 obstack_free (&m_obstack, start_point);
1458 return m_num_conditions != 0;
1461 /* Use the ranges in VRS to remove impossible versioning conditions from
1462 LOOP. */
1464 void
1465 loop_versioning::prune_loop_conditions (class loop *loop)
1467 loop_info &li = get_loop_info (loop);
1469 int to_remove = -1;
1470 bitmap_iterator bi;
1471 unsigned int i;
1472 int_range_max r;
1473 EXECUTE_IF_SET_IN_BITMAP (&li.unity_names, 0, i, bi)
1475 tree name = ssa_name (i);
1476 gimple *stmt = first_stmt (loop->header);
1478 if (get_range_query (cfun)->range_of_expr (r, name, stmt)
1479 && !r.contains_p (build_one_cst (TREE_TYPE (name))))
1481 if (dump_enabled_p ())
1482 dump_printf_loc (MSG_NOTE, find_loop_location (loop),
1483 "%T can never be 1 in this loop\n", name);
1485 if (to_remove >= 0)
1486 bitmap_clear_bit (&li.unity_names, to_remove);
1487 to_remove = i;
1488 m_num_conditions -= 1;
1491 if (to_remove >= 0)
1492 bitmap_clear_bit (&li.unity_names, to_remove);
1495 /* Remove any scheduled loop version conditions that will never be true.
1496 Return true if any remain. */
1498 bool
1499 loop_versioning::prune_conditions ()
1501 AUTO_DUMP_SCOPE ("prune_loop_conditions",
1502 dump_user_location_t::from_function_decl (m_fn->decl));
1504 calculate_dominance_info (CDI_DOMINATORS);
1505 lv_dom_walker dom_walker (*this);
1506 dom_walker.walk (ENTRY_BLOCK_PTR_FOR_FN (m_fn));
1507 return m_num_conditions != 0;
1510 /* Merge the version checks for INNER into immediately-enclosing loop
1511 OUTER. */
1513 void
1514 loop_versioning::merge_loop_info (class loop *outer, class loop *inner)
1516 loop_info &inner_li = get_loop_info (inner);
1517 loop_info &outer_li = get_loop_info (outer);
1519 if (dump_enabled_p ())
1521 bitmap_iterator bi;
1522 unsigned int i;
1523 EXECUTE_IF_SET_IN_BITMAP (&inner_li.unity_names, 0, i, bi)
1524 if (!bitmap_bit_p (&outer_li.unity_names, i))
1525 dump_printf_loc (MSG_NOTE, find_loop_location (inner),
1526 "hoisting check that %T == 1 to outer loop\n",
1527 ssa_name (i));
1530 bitmap_ior_into (&outer_li.unity_names, &inner_li.unity_names);
1531 if (loop_depth (outer_li.outermost) < loop_depth (inner_li.outermost))
1532 outer_li.outermost = inner_li.outermost;
1535 /* Add LOOP to the queue of loops to version. */
1537 void
1538 loop_versioning::add_loop_to_queue (class loop *loop)
1540 loop_info &li = get_loop_info (loop);
1542 if (dump_enabled_p ())
1543 dump_printf_loc (MSG_NOTE, find_loop_location (loop),
1544 "queuing this loop for versioning\n");
1545 m_loops_to_version.safe_push (loop);
1547 /* Don't try to version superloops. */
1548 li.rejected_p = true;
1551 /* Decide whether the cost model would allow us to version LOOP,
1552 either directly or as part of a parent loop, and return true if so.
1553 This does not imply that the loop is actually worth versioning in its
1554 own right, just that it would be valid to version it if something
1555 benefited.
1557 We have already made this decision for all inner loops of LOOP. */
1559 bool
1560 loop_versioning::decide_whether_loop_is_versionable (class loop *loop)
1562 loop_info &li = get_loop_info (loop);
1564 if (li.rejected_p)
1565 return false;
1567 /* Examine the decisions made for inner loops. */
1568 for (class loop *inner = loop->inner; inner; inner = inner->next)
1570 loop_info &inner_li = get_loop_info (inner);
1571 if (inner_li.rejected_p)
1573 if (dump_enabled_p ())
1574 dump_printf_loc (MSG_NOTE, find_loop_location (loop),
1575 "not versioning this loop because one of its"
1576 " inner loops should not be versioned\n");
1577 return false;
1580 if (inner_li.worth_versioning_p ())
1581 li.subloops_benefit_p = true;
1583 /* Accumulate the number of instructions from subloops that are not
1584 the innermost, or that don't benefit from versioning. Only the
1585 instructions from innermost loops that benefit from versioning
1586 should be weighed against loop-versioning-max-inner-insns;
1587 everything else should be weighed against
1588 loop-versioning-max-outer-insns. */
1589 if (!inner_li.worth_versioning_p () || inner->inner)
1591 if (dump_enabled_p ())
1592 dump_printf_loc (MSG_NOTE, find_loop_location (loop),
1593 "counting %d instructions from this loop"
1594 " against its parent loop\n", inner_li.num_insns);
1595 li.num_insns += inner_li.num_insns;
1599 /* Enforce the size limits. */
1600 if (li.worth_versioning_p ())
1602 unsigned int max_num_insns = max_insns_for_loop (loop);
1603 if (dump_enabled_p ())
1604 dump_printf_loc (MSG_NOTE, find_loop_location (loop),
1605 "this loop has %d instructions, against"
1606 " a versioning limit of %d\n",
1607 li.num_insns, max_num_insns);
1608 if (li.num_insns > max_num_insns)
1610 if (dump_enabled_p ())
1611 dump_printf_loc (MSG_MISSED_OPTIMIZATION
1612 | MSG_PRIORITY_USER_FACING,
1613 find_loop_location (loop),
1614 "this loop is too big to version");
1615 return false;
1619 /* Hoist all version checks from subloops to this loop. */
1620 for (class loop *subloop = loop->inner; subloop; subloop = subloop->next)
1621 merge_loop_info (loop, subloop);
1623 return true;
1626 /* Decide which loops to version and add them to the versioning queue.
1627 Return true if there are any loops to version. */
1629 bool
1630 loop_versioning::make_versioning_decisions ()
1632 AUTO_DUMP_SCOPE ("make_versioning_decisions",
1633 dump_user_location_t::from_function_decl (m_fn->decl));
1635 for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1637 loop_info &linfo = get_loop_info (loop);
1638 if (decide_whether_loop_is_versionable (loop))
1640 /* Commit to versioning LOOP directly if we can't hoist the
1641 version checks any further. */
1642 if (linfo.worth_versioning_p ()
1643 && (loop_depth (loop) == 1 || linfo.outermost == loop))
1644 add_loop_to_queue (loop);
1646 else
1648 /* We can't version this loop, so individually version any
1649 subloops that would benefit and haven't been versioned yet. */
1650 linfo.rejected_p = true;
1651 for (class loop *subloop = loop->inner; subloop;
1652 subloop = subloop->next)
1653 if (get_loop_info (subloop).worth_versioning_p ())
1654 add_loop_to_queue (subloop);
1658 return !m_loops_to_version.is_empty ();
1661 /* Attempt to implement loop versioning for LOOP, using the information
1662 cached in the associated loop_info. Return true on success. */
1664 bool
1665 loop_versioning::version_loop (class loop *loop)
1667 loop_info &li = get_loop_info (loop);
1669 /* Build up a condition that selects the original loop instead of
1670 the simplified loop. */
1671 tree cond = boolean_false_node;
1672 bitmap_iterator bi;
1673 unsigned int i;
1674 EXECUTE_IF_SET_IN_BITMAP (&li.unity_names, 0, i, bi)
1676 tree name = ssa_name (i);
1677 tree ne_one = fold_build2 (NE_EXPR, boolean_type_node, name,
1678 build_one_cst (TREE_TYPE (name)));
1679 cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, cond, ne_one);
1682 /* Convert the condition into a suitable gcond. */
1683 gimple_seq stmts = NULL;
1684 cond = force_gimple_operand_1 (cond, &stmts, is_gimple_condexpr, NULL_TREE);
1686 /* Version the loop. */
1687 initialize_original_copy_tables ();
1688 basic_block cond_bb;
1689 li.optimized_loop = loop_version (loop, cond, &cond_bb,
1690 profile_probability::unlikely (),
1691 profile_probability::likely (),
1692 profile_probability::unlikely (),
1693 profile_probability::likely (), true);
1694 free_original_copy_tables ();
1695 if (!li.optimized_loop)
1697 if (dump_enabled_p ())
1698 dump_printf_loc (MSG_MISSED_OPTIMIZATION, find_loop_location (loop),
1699 "tried but failed to version this loop for when"
1700 " certain strides are 1\n");
1701 return false;
1704 if (dump_enabled_p ())
1705 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, find_loop_location (loop),
1706 "versioned this loop for when certain strides are 1\n");
1708 /* Insert the statements that feed COND. */
1709 if (stmts)
1711 gimple_stmt_iterator gsi = gsi_last_bb (cond_bb);
1712 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
1715 return true;
1718 /* Attempt to version all loops in the versioning queue. */
1720 void
1721 loop_versioning::implement_versioning_decisions ()
1723 /* No AUTO_DUMP_SCOPE here since all messages are top-level and
1724 user-facing at this point. */
1726 bool any_succeeded_p = false;
1727 class loop *loop;
1728 unsigned int i;
1729 FOR_EACH_VEC_ELT (m_loops_to_version, i, loop)
1730 if (version_loop (loop))
1731 any_succeeded_p = true;
1732 if (!any_succeeded_p)
1733 return;
1735 update_ssa (TODO_update_ssa);
1737 /* Simplify the new loop, which is used when COND is false. */
1738 FOR_EACH_VEC_ELT (m_loops_to_version, i, loop)
1740 loop_info &linfo = get_loop_info (loop);
1741 if (linfo.optimized_loop)
1742 name_prop (linfo).substitute_and_fold (linfo.optimized_loop->header);
1746 /* Run the pass and return a set of TODO_* flags. */
1748 unsigned int
1749 loop_versioning::run ()
1751 gcc_assert (scev_initialized_p ());
1753 if (analyze_blocks ()
1754 && prune_conditions ()
1755 && make_versioning_decisions ())
1756 implement_versioning_decisions ();
1758 return 0;
1761 /* Loop versioning pass. */
1763 const pass_data pass_data_loop_versioning =
1765 GIMPLE_PASS, /* type */
1766 "lversion", /* name */
1767 OPTGROUP_LOOP, /* optinfo_flags */
1768 TV_LOOP_VERSIONING, /* tv_id */
1769 PROP_cfg, /* properties_required */
1770 0, /* properties_provided */
1771 0, /* properties_destroyed */
1772 0, /* todo_flags_start */
1773 0, /* todo_flags_finish */
1776 class pass_loop_versioning : public gimple_opt_pass
1778 public:
1779 pass_loop_versioning (gcc::context *ctxt)
1780 : gimple_opt_pass (pass_data_loop_versioning, ctxt)
1783 /* opt_pass methods: */
1784 virtual bool gate (function *) { return flag_version_loops_for_strides; }
1785 virtual unsigned int execute (function *);
1788 unsigned int
1789 pass_loop_versioning::execute (function *fn)
1791 if (number_of_loops (fn) <= 1)
1792 return 0;
1794 enable_ranger (fn);
1795 unsigned int ret = loop_versioning (fn).run ();
1796 disable_ranger (fn);
1797 return ret;
1800 } // anon namespace
1802 gimple_opt_pass *
1803 make_pass_loop_versioning (gcc::context *ctxt)
1805 return new pass_loop_versioning (ctxt);