1/* Natural loop functions
2 Copyright (C) 1987-2025 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; 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#ifndef GCC_CFGLOOP_H
21#define GCC_CFGLOOP_H
22
23#include "cfgloopmanip.h"
24
25/* Structure to hold decision about unrolling/peeling. */
26enum lpt_dec
27{
28 LPT_NONE,
29 LPT_UNROLL_CONSTANT,
30 LPT_UNROLL_RUNTIME,
31 LPT_UNROLL_STUPID
32};
33
34struct GTY (()) lpt_decision {
35 enum lpt_dec decision;
36 unsigned times;
37};
38
39/* The type of extend applied to an IV. */
40enum iv_extend_code
41{
42 IV_SIGN_EXTEND,
43 IV_ZERO_EXTEND,
44 IV_UNKNOWN_EXTEND
45};
46
47typedef generic_wide_int <fixed_wide_int_storage <WIDE_INT_MAX_INL_PRECISION> >
48 bound_wide_int;
49
50/* The structure describing a bound on number of iterations of a loop. */
51
52class GTY ((chain_next ("%h.next"))) nb_iter_bound {
53public:
54 /* The statement STMT is executed at most ... */
55 gimple *stmt;
56
57 /* ... BOUND + 1 times (BOUND must be an unsigned constant).
58 The + 1 is added for the following reasons:
59
60 a) 0 would otherwise be unused, while we would need to care more about
61 overflows (as MAX + 1 is sometimes produced as the estimate on number
62 of executions of STMT).
63 b) it is consistent with the result of number_of_iterations_exit. */
64 bound_wide_int bound;
65
66 /* True if, after executing the statement BOUND + 1 times, we will
67 leave the loop; that is, all the statements after it are executed at most
68 BOUND times. */
69 bool is_exit;
70
71 /* The next bound in the list. */
72 class nb_iter_bound *next;
73};
74
75/* Description of the loop exit. */
76
77struct GTY ((for_user)) loop_exit {
78 /* The exit edge. */
79 edge e;
80
81 /* Previous and next exit in the list of the exits of the loop. */
82 struct loop_exit *prev;
83 struct loop_exit *next;
84
85 /* Next element in the list of loops from that E exits. */
86 struct loop_exit *next_e;
87};
88
89struct loop_exit_hasher : ggc_ptr_hash<loop_exit>
90{
91 typedef edge compare_type;
92
93 static hashval_t hash (loop_exit *);
94 static bool equal (loop_exit *, edge);
95 static void remove (loop_exit *);
96};
97
98typedef class loop *loop_p;
99
100/* An integer estimation of the number of iterations. Estimate_state
101 describes what is the state of the estimation. */
102enum loop_estimation
103{
104 /* Estimate was not computed yet. */
105 EST_NOT_COMPUTED,
106 /* Estimate is ready. */
107 EST_AVAILABLE,
108 EST_LAST
109};
110
111/* The structure describing non-overflow control induction variable for
112 loop's exit edge. */
113struct GTY ((chain_next ("%h.next"))) control_iv {
114 tree base;
115 tree step;
116 struct control_iv *next;
117};
118
119/* Structure to hold information for each natural loop. */
120class GTY ((chain_next ("%h.next"))) loop {
121public:
122 /* Index into loops array. Note indices will never be reused after loop
123 is destroyed. */
124 int num;
125
126 /* Number of loop insns. */
127 unsigned ninsns;
128
129 /* Basic block of loop header. */
130 basic_block header;
131
132 /* Basic block of loop latch. */
133 basic_block latch;
134
135 /* For loop unrolling/peeling decision. */
136 struct lpt_decision lpt_decision;
137
138 /* Average number of executed insns per iteration. */
139 unsigned av_ninsns;
140
141 /* Number of blocks contained within the loop. */
142 unsigned num_nodes;
143
144 /* Superloops of the loop, starting with the outermost loop. */
145 vec<loop_p, va_gc> *superloops;
146
147 /* The first inner (child) loop or NULL if innermost loop. */
148 class loop *inner;
149
150 /* Link to the next (sibling) loop. */
151 class loop *next;
152
153 /* Auxiliary info specific to a pass. */
154 void *GTY ((skip (""))) aux;
155
156 /* The number of times the latch of the loop is executed. This can be an
157 INTEGER_CST, or a symbolic expression representing the number of
158 iterations like "N - 1", or a COND_EXPR containing the runtime
159 conditions under which the number of iterations is non zero.
160
161 Don't access this field directly: number_of_latch_executions
162 computes and caches the computed information in this field. */
163 tree nb_iterations;
164
165 /* An integer guaranteed to be greater or equal to nb_iterations. Only
166 valid if any_upper_bound is true. */
167 bound_wide_int nb_iterations_upper_bound;
168
169 bound_wide_int nb_iterations_likely_upper_bound;
170
171 /* An integer giving an estimate on nb_iterations. Unlike
172 nb_iterations_upper_bound, there is no guarantee that it is at least
173 nb_iterations. */
174 bound_wide_int nb_iterations_estimate;
175
176 /* If > 0, an integer, where the user asserted that for any
177 I in [ 0, nb_iterations ) and for any J in
178 [ I, min ( I + safelen, nb_iterations ) ), the Ith and Jth iterations
179 of the loop can be safely evaluated concurrently. */
180 int safelen;
181
182 /* Preferred vectorization factor for the loop if non-zero. */
183 int simdlen;
184
185 /* Constraints are generally set by consumers and affect certain
186 semantics of niter analyzer APIs. Currently the APIs affected are
187 number_of_iterations_exit* functions and their callers. One typical
188 use case of constraints is to vectorize possibly infinite loop:
189
190 1) Compute niter->assumptions by calling niter analyzer API and
191 record it as possible condition for loop versioning.
192 2) Clear buffered result of niter/scev analyzer.
193 3) Set constraint LOOP_C_FINITE assuming the loop is finite.
194 4) Analyze data references. Since data reference analysis depends
195 on niter/scev analyzer, the point is that niter/scev analysis
196 is done under circumstance of LOOP_C_FINITE constraint.
197 5) Version the loop with niter->assumptions computed in step 1).
198 6) Vectorize the versioned loop in which niter->assumptions is
199 checked to be true.
200 7) Update constraints in versioned loops so that niter analyzer
201 in following passes can use it.
202
203 Note consumers are usually the loop optimizers and it is consumers'
204 responsibility to set/clear constraints correctly. Failing to do
205 that might result in hard to track down bugs in niter/scev consumers. */
206 unsigned constraints;
207
208 /* An integer estimation of the number of iterations. Estimate_state
209 describes what is the state of the estimation. */
210 ENUM_BITFIELD(loop_estimation) estimate_state : 8;
211
212 unsigned any_upper_bound : 1;
213 unsigned any_estimate : 1;
214 unsigned any_likely_upper_bound : 1;
215
216 /* True if the loop can be parallel. */
217 unsigned can_be_parallel : 1;
218
219 /* True if -Waggressive-loop-optimizations warned about this loop
220 already. */
221 unsigned warned_aggressive_loop_optimizations : 1;
222
223 /* True if this loop should never be vectorized. */
224 unsigned dont_vectorize : 1;
225
226 /* True if we should try harder to vectorize this loop. */
227 unsigned force_vectorize : 1;
228
229 /* True if the loop is part of an oacc kernels region. */
230 unsigned in_oacc_kernels_region : 1;
231
232 /* True if the loop is known to be finite. This is a localized
233 flag_finite_loops or similar pragmas state. */
234 unsigned finite_p : 1;
235
236 /* The number of times to unroll the loop. 0 means no information given,
237 just do what we always do. A value of 1 means do not unroll the loop.
238 A value of USHRT_MAX means unroll with no specific unrolling factor.
239 Other values means unroll with the given unrolling factor. */
240 unsigned short unroll;
241
242 /* If this loop was inlined the main clique of the callee which does
243 not need remapping when copying the loop body. */
244 unsigned short owned_clique;
245
246 /* For SIMD loops, this is a unique identifier of the loop, referenced
247 by IFN_GOMP_SIMD_VF, IFN_GOMP_SIMD_LANE and IFN_GOMP_SIMD_LAST_LANE
248 builtins. */
249 tree simduid;
250
251 /* In loop optimization, it's common to generate loops from the original
252 loop. This field records the index of the original loop which can be
253 used to track the original loop from newly generated loops. This can
254 be done by calling function get_loop (cfun, orig_loop_num). Note the
255 original loop could be destroyed for various reasons thus no longer
256 exists, as a result, function call to get_loop returns NULL pointer.
257 In this case, this field should not be used and needs to be cleared
258 whenever possible. */
259 int orig_loop_num;
260
261 /* Upper bound on number of iterations of a loop. */
262 class nb_iter_bound *bounds;
263
264 /* Non-overflow control ivs of a loop. */
265 struct control_iv *control_ivs;
266
267 /* Head of the cyclic list of the exits of the loop. */
268 struct loop_exit *exits;
269
270 /* Number of iteration analysis data for RTL. */
271 class niter_desc *simple_loop_desc;
272
273 /* For sanity checking during loop fixup we record here the former
274 loop header for loops marked for removal. Note that this prevents
275 the basic-block from being collected but its index can still be
276 reused. */
277 basic_block former_header;
278};
279
280/* Set if the loop is known to be infinite. */
281#define LOOP_C_INFINITE (1 << 0)
282/* Set if the loop is known to be finite without any assumptions. */
283#define LOOP_C_FINITE (1 << 1)
284
285/* Set C to the LOOP constraint. */
286inline void
287loop_constraint_set (class loop *loop, unsigned c)
288{
289 loop->constraints |= c;
290}
291
292/* Clear C from the LOOP constraint. */
293inline void
294loop_constraint_clear (class loop *loop, unsigned c)
295{
296 loop->constraints &= ~c;
297}
298
299/* Check if C is set in the LOOP constraint. */
300inline bool
301loop_constraint_set_p (class loop *loop, unsigned c)
302{
303 return (loop->constraints & c) == c;
304}
305
306/* Flags for state of loop structure. */
307enum
308{
309 LOOPS_HAVE_PREHEADERS = 1,
310 LOOPS_HAVE_SIMPLE_LATCHES = 2,
311 LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4,
312 LOOPS_HAVE_RECORDED_EXITS = 8,
313 LOOPS_MAY_HAVE_MULTIPLE_LATCHES = 16,
314 LOOP_CLOSED_SSA = 32,
315 LOOPS_NEED_FIXUP = 64,
316 LOOPS_HAVE_FALLTHRU_PREHEADERS = 128
317};
318
319#define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \
320 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
321#define AVOID_CFG_MODIFICATIONS (LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
322
323/* Structure to hold CFG information about natural loops within a function. */
324struct GTY (()) loops {
325 /* State of loops. */
326 int state;
327
328 /* Array of the loops. */
329 vec<loop_p, va_gc> *larray;
330
331 /* Maps edges to the list of their descriptions as loop exits. Edges
332 whose sources or destinations have loop_father == NULL (which may
333 happen during the cfg manipulations) should not appear in EXITS. */
334 hash_table<loop_exit_hasher> *GTY(()) exits;
335
336 /* Pointer to root of loop hierarchy tree. */
337 class loop *tree_root;
338};
339
340/* Loop recognition. */
341bool bb_loop_header_p (basic_block);
342void init_loops_structure (struct function *, struct loops *, unsigned);
343extern struct loops *flow_loops_find (struct loops *);
344extern void disambiguate_loops_with_multiple_latches (void);
345extern void flow_loops_free (struct loops *);
346extern void flow_loops_dump (FILE *,
347 void (*)(const class loop *, FILE *, int), int);
348extern void flow_loop_dump (const class loop *, FILE *,
349 void (*)(const class loop *, FILE *, int), int);
350class loop *alloc_loop (void);
351extern void flow_loop_free (class loop *);
352int flow_loop_nodes_find (basic_block, class loop *);
353unsigned fix_loop_structure (bitmap changed_bbs);
354bool mark_irreducible_loops (void);
355void release_recorded_exits (function *);
356void record_loop_exits (void);
357void rescan_loop_exit (edge, bool, bool);
358void sort_sibling_loops (function *);
359
360/* Loop data structure manipulation/querying. */
361extern void flow_loop_tree_node_add (class loop *, class loop *,
362 class loop * = NULL);
363extern void flow_loop_tree_node_remove (class loop *);
364extern bool flow_loop_nested_p (const class loop *, const class loop *);
365extern bool flow_bb_inside_loop_p (const class loop *, const_basic_block);
366extern class loop * find_common_loop (class loop *, class loop *);
367class loop *superloop_at_depth (class loop *, unsigned);
368struct eni_weights;
369extern int num_loop_insns (const class loop *);
370extern int average_num_loop_insns (const class loop *);
371extern unsigned get_loop_level (const class loop *);
372extern bool loop_exit_edge_p (const class loop *, const_edge);
373extern bool loop_exits_to_bb_p (class loop *, basic_block);
374extern bool loop_exits_from_bb_p (class loop *, basic_block);
375extern void mark_loop_exit_edges (void);
376extern dump_user_location_t get_loop_location (class loop *loop);
377
378/* Loops & cfg manipulation. */
379extern basic_block *get_loop_body (const class loop *);
380extern unsigned get_loop_body_with_size (const class loop *, basic_block *,
381 unsigned);
382extern basic_block *get_loop_body_in_dom_order (const class loop *);
383extern basic_block *get_loop_body_in_bfs_order (const class loop *);
384extern basic_block *get_loop_body_in_custom_order (const class loop *,
385 int (*) (const void *, const void *));
386extern basic_block *get_loop_body_in_custom_order (const class loop *, void *,
387 int (*) (const void *, const void *, void *));
388
389extern auto_vec<edge> get_loop_exit_edges (const class loop *, basic_block * = NULL);
390extern edge single_exit (const class loop *);
391extern edge single_likely_exit (class loop *loop, const vec<edge> &);
392extern unsigned num_loop_branches (const class loop *);
393
394extern edge loop_preheader_edge (const class loop *);
395extern edge loop_latch_edge (const class loop *);
396
397extern void add_bb_to_loop (basic_block, class loop *);
398extern void remove_bb_from_loops (basic_block);
399
400extern void cancel_loop_tree (class loop *);
401extern void delete_loop (class loop *);
402
403
404extern void verify_loop_structure (void);
405
406/* Loop analysis. */
407extern bool just_once_each_iteration_p (const class loop *, const_basic_block);
408gcov_type expected_loop_iterations_unbounded (const class loop *,
409 bool *read_profile_p = NULL);
410extern bool expected_loop_iterations_by_profile (const class loop *loop,
411 sreal *ret,
412 bool *reliable = NULL);
413extern bool maybe_flat_loop_profile (const class loop *);
414extern unsigned expected_loop_iterations (class loop *);
415extern rtx doloop_condition_get (rtx_insn *);
416
417void mark_loop_for_removal (loop_p);
418void print_loop_info (FILE *file, const class loop *loop, const char *);
419
420/* Induction variable analysis. */
421
422/* The description of induction variable. The things are a bit complicated
423 due to need to handle subregs and extends. The value of the object described
424 by it can be obtained as follows (all computations are done in extend_mode):
425
426 Value in i-th iteration is
427 delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)).
428
429 If first_special is true, the value in the first iteration is
430 delta + mult * base
431
432 If extend = UNKNOWN, first_special must be false, delta 0, mult 1 and value is
433 subreg_{mode} (base + i * step)
434
435 The get_iv_value function can be used to obtain these expressions.
436
437 ??? Add a third mode field that would specify the mode in that inner
438 computation is done, which would enable it to be different from the
439 outer one? */
440
441class rtx_iv
442{
443public:
444 /* Its base and step (mode of base and step is supposed to be extend_mode,
445 see the description above). */
446 rtx base, step;
447
448 /* The type of extend applied to it (IV_SIGN_EXTEND, IV_ZERO_EXTEND,
449 or IV_UNKNOWN_EXTEND). */
450 enum iv_extend_code extend;
451
452 /* Operations applied in the extended mode. */
453 rtx delta, mult;
454
455 /* The mode it is extended to. */
456 scalar_int_mode extend_mode;
457
458 /* The mode the variable iterates in. */
459 scalar_int_mode mode;
460
461 /* Whether the first iteration needs to be handled specially. */
462 unsigned first_special : 1;
463};
464
465/* The description of an exit from the loop and of the number of iterations
466 till we take the exit. */
467
468class GTY(()) niter_desc
469{
470public:
471 /* The edge out of the loop. */
472 edge out_edge;
473
474 /* The other edge leading from the condition. */
475 edge in_edge;
476
477 /* True if we are able to say anything about number of iterations of the
478 loop. */
479 bool simple_p;
480
481 /* True if the loop iterates the constant number of times. */
482 bool const_iter;
483
484 /* Number of iterations if constant. */
485 uint64_t niter;
486
487 /* Assumptions under that the rest of the information is valid. */
488 rtx assumptions;
489
490 /* Assumptions under that the loop ends before reaching the latch,
491 even if value of niter_expr says otherwise. */
492 rtx noloop_assumptions;
493
494 /* Condition under that the loop is infinite. */
495 rtx infinite;
496
497 /* Whether the comparison is signed. */
498 bool signed_p;
499
500 /* The mode in that niter_expr should be computed. */
501 scalar_int_mode mode;
502
503 /* The number of iterations of the loop. */
504 rtx niter_expr;
505};
506
507extern void iv_analysis_loop_init (class loop *);
508extern bool iv_analyze (rtx_insn *, scalar_int_mode, rtx, class rtx_iv *);
509extern bool iv_analyze_result (rtx_insn *, rtx, class rtx_iv *);
510extern bool iv_analyze_expr (rtx_insn *, scalar_int_mode, rtx,
511 class rtx_iv *);
512extern rtx get_iv_value (class rtx_iv *, rtx);
513extern bool biv_p (rtx_insn *, scalar_int_mode, rtx);
514extern void iv_analysis_done (void);
515
516extern class niter_desc *get_simple_loop_desc (class loop *loop);
517extern void free_simple_loop_desc (class loop *loop);
518
519inline class niter_desc *
520simple_loop_desc (class loop *loop)
521{
522 return loop->simple_loop_desc;
523}
524
525/* Accessors for the loop structures. */
526
527/* Returns the loop with index NUM from FNs loop tree. */
528
529inline class loop *
530get_loop (struct function *fn, unsigned num)
531{
532 return (*loops_for_fn (fn)->larray)[num];
533}
534
535/* Returns the number of superloops of LOOP. */
536
537inline unsigned
538loop_depth (const class loop *loop)
539{
540 return vec_safe_length (v: loop->superloops);
541}
542
543/* Returns the immediate superloop of LOOP, or NULL if LOOP is the outermost
544 loop. */
545
546inline class loop *
547loop_outer (const class loop *loop)
548{
549 unsigned n = vec_safe_length (v: loop->superloops);
550
551 if (n == 0)
552 return NULL;
553
554 return (*loop->superloops)[n - 1];
555}
556
557/* Returns true if LOOP has at least one exit edge. */
558
559inline bool
560loop_has_exit_edges (const class loop *loop)
561{
562 return loop->exits->next->e != NULL;
563}
564
565/* Returns the list of loops in FN. */
566
567inline vec<loop_p, va_gc> *
568get_loops (struct function *fn)
569{
570 struct loops *loops = loops_for_fn (fn);
571 if (!loops)
572 return NULL;
573
574 return loops->larray;
575}
576
577/* Returns the number of loops in FN (including the removed
578 ones and the fake loop that forms the root of the loop tree). */
579
580inline unsigned
581number_of_loops (struct function *fn)
582{
583 struct loops *loops = loops_for_fn (fn);
584 if (!loops)
585 return 0;
586
587 return vec_safe_length (v: loops->larray);
588}
589
590/* Returns true if state of the loops satisfies all properties
591 described by FLAGS. */
592
593inline bool
594loops_state_satisfies_p (function *fn, unsigned flags)
595{
596 return (loops_for_fn (fn)->state & flags) == flags;
597}
598
599inline bool
600loops_state_satisfies_p (unsigned flags)
601{
602 return loops_state_satisfies_p (cfun, flags);
603}
604
605/* Sets FLAGS to the loops state. */
606
607inline void
608loops_state_set (function *fn, unsigned flags)
609{
610 loops_for_fn (fn)->state |= flags;
611}
612
613inline void
614loops_state_set (unsigned flags)
615{
616 loops_state_set (cfun, flags);
617}
618
619/* Clears FLAGS from the loops state. */
620
621inline void
622loops_state_clear (function *fn, unsigned flags)
623{
624 loops_for_fn (fn)->state &= ~flags;
625}
626
627inline void
628loops_state_clear (unsigned flags)
629{
630 if (!current_loops)
631 return;
632 loops_state_clear (cfun, flags);
633}
634
635/* Check loop structure invariants, if internal consistency checks are
636 enabled. */
637
638inline void
639checking_verify_loop_structure (void)
640{
641 /* VERIFY_LOOP_STRUCTURE essentially asserts that no loops need fixups.
642
643 The loop optimizers should never make changes to the CFG which
644 require loop fixups. But the low level CFG manipulation code may
645 set the flag conservatively.
646
647 Go ahead and clear the flag here. That avoids the assert inside
648 VERIFY_LOOP_STRUCTURE, and if there is an inconsistency in the loop
649 structures VERIFY_LOOP_STRUCTURE will detect it.
650
651 This also avoid the compile time cost of excessive fixups. */
652 loops_state_clear (flags: LOOPS_NEED_FIXUP);
653 if (flag_checking)
654 verify_loop_structure ();
655}
656
657/* Loop iterators. */
658
659/* Flags for loop iteration. */
660
661enum li_flags
662{
663 LI_INCLUDE_ROOT = 1, /* Include the fake root of the loop tree. */
664 LI_FROM_INNERMOST = 2, /* Iterate over the loops in the reverse order,
665 starting from innermost ones. */
666 LI_ONLY_INNERMOST = 4 /* Iterate only over innermost loops. */
667};
668
669/* Provide the functionality of std::as_const to support range-based for
670 to use const iterator. (We can't use std::as_const itself because it's
671 a C++17 feature.) */
672template <typename T>
673constexpr const T &
674as_const (T &t)
675{
676 return t;
677}
678
679/* A list for visiting loops, which contains the loop numbers instead of
680 the loop pointers. If the loop ROOT is offered (non-null), the visiting
681 will start from it, otherwise it would start from the tree_root of
682 loops_for_fn (FN) instead. The scope is restricted in function FN and
683 the visiting order is specified by FLAGS. */
684
685class loops_list
686{
687public:
688 loops_list (function *fn, unsigned flags, class loop *root = nullptr);
689
690 template <typename T> class Iter
691 {
692 public:
693 Iter (const loops_list &l, unsigned idx) : list (l), curr_idx (idx)
694 {
695 fill_curr_loop ();
696 }
697
698 T operator* () const { return curr_loop; }
699
700 Iter &
701 operator++ ()
702 {
703 if (curr_idx < list.to_visit.length ())
704 {
705 /* Bump the index and fill a new one. */
706 curr_idx++;
707 fill_curr_loop ();
708 }
709 else
710 gcc_assert (!curr_loop);
711
712 return *this;
713 }
714
715 bool
716 operator!= (const Iter &rhs) const
717 {
718 return this->curr_idx != rhs.curr_idx;
719 }
720
721 private:
722 /* Fill the current loop starting from the current index. */
723 void fill_curr_loop ();
724
725 /* Reference to the loop list to visit. */
726 const loops_list &list;
727
728 /* The current index in the list to visit. */
729 unsigned curr_idx;
730
731 /* The loop implied by the current index. */
732 class loop *curr_loop;
733 };
734
735 using iterator = Iter<class loop *>;
736 using const_iterator = Iter<const class loop *>;
737
738 iterator
739 begin ()
740 {
741 return iterator (*this, 0);
742 }
743
744 iterator
745 end ()
746 {
747 return iterator (*this, to_visit.length ());
748 }
749
750 const_iterator
751 begin () const
752 {
753 return const_iterator (*this, 0);
754 }
755
756 const_iterator
757 end () const
758 {
759 return const_iterator (*this, to_visit.length ());
760 }
761
762private:
763 /* Walk loop tree starting from ROOT as the visiting order specified
764 by FLAGS. */
765 void walk_loop_tree (class loop *root, unsigned flags);
766
767 /* The function we are visiting. */
768 function *fn;
769
770 /* The list of loops to visit. */
771 auto_vec<int, 16> to_visit;
772};
773
774/* Starting from current index CURR_IDX (inclusive), find one index
775 which stands for one valid loop and fill the found loop as CURR_LOOP,
776 if we can't find one, set CURR_LOOP as null. */
777
778template <typename T>
779inline void
780loops_list::Iter<T>::fill_curr_loop ()
781{
782 int anum;
783
784 while (this->list.to_visit.iterate (this->curr_idx, &anum))
785 {
786 class loop *loop = get_loop (this->list.fn, anum);
787 if (loop)
788 {
789 curr_loop = loop;
790 return;
791 }
792 this->curr_idx++;
793 }
794
795 curr_loop = nullptr;
796}
797
798/* Set up the loops list to visit according to the specified
799 function scope FN and iterating order FLAGS. If ROOT is
800 not null, the visiting would start from it, otherwise it
801 will start from tree_root of loops_for_fn (FN). */
802
803inline loops_list::loops_list (function *fn, unsigned flags, class loop *root)
804{
805 struct loops *loops = loops_for_fn (fn);
806 gcc_assert (!root || loops);
807
808 /* Check mutually exclusive flags should not co-exist. */
809 unsigned checked_flags = LI_ONLY_INNERMOST | LI_FROM_INNERMOST;
810 gcc_assert ((flags & checked_flags) != checked_flags);
811
812 this->fn = fn;
813 if (!loops)
814 return;
815
816 class loop *tree_root = root ? root : loops->tree_root;
817
818 this->to_visit.reserve_exact (nelems: number_of_loops (fn));
819
820 /* When root is tree_root of loops_for_fn (fn) and the visiting
821 order is LI_ONLY_INNERMOST, we would like to use linear
822 search here since it has a more stable bound than the
823 walk_loop_tree. */
824 if (flags & LI_ONLY_INNERMOST && tree_root == loops->tree_root)
825 {
826 gcc_assert (tree_root->num == 0);
827 if (tree_root->inner == NULL)
828 {
829 if (flags & LI_INCLUDE_ROOT)
830 this->to_visit.quick_push (obj: 0);
831
832 return;
833 }
834
835 class loop *aloop;
836 unsigned int i;
837 for (i = 1; vec_safe_iterate (v: loops->larray, ix: i, ptr: &aloop); i++)
838 if (aloop != NULL && aloop->inner == NULL)
839 this->to_visit.quick_push (obj: aloop->num);
840 }
841 else
842 walk_loop_tree (root: tree_root, flags);
843}
844
845/* The properties of the target. */
846struct target_cfgloop {
847 /* Number of available registers. */
848 unsigned x_target_avail_regs;
849
850 /* Number of available registers that are call-clobbered. */
851 unsigned x_target_clobbered_regs;
852
853 /* Number of registers reserved for temporary expressions. */
854 unsigned x_target_res_regs;
855
856 /* The cost for register when there still is some reserve, but we are
857 approaching the number of available registers. */
858 unsigned x_target_reg_cost[2];
859
860 /* The cost for register when we need to spill. */
861 unsigned x_target_spill_cost[2];
862};
863
864extern struct target_cfgloop default_target_cfgloop;
865#if SWITCHABLE_TARGET
866extern struct target_cfgloop *this_target_cfgloop;
867#else
868#define this_target_cfgloop (&default_target_cfgloop)
869#endif
870
871#define target_avail_regs \
872 (this_target_cfgloop->x_target_avail_regs)
873#define target_clobbered_regs \
874 (this_target_cfgloop->x_target_clobbered_regs)
875#define target_res_regs \
876 (this_target_cfgloop->x_target_res_regs)
877#define target_reg_cost \
878 (this_target_cfgloop->x_target_reg_cost)
879#define target_spill_cost \
880 (this_target_cfgloop->x_target_spill_cost)
881
882/* Register pressure estimation for induction variable optimizations & loop
883 invariant motion. */
884extern unsigned estimate_reg_pressure_cost (unsigned, unsigned, bool, bool);
885extern void init_set_costs (void);
886
887/* Loop optimizer initialization. */
888extern void loop_optimizer_init (unsigned);
889extern void loop_optimizer_finalize (function *, bool = false);
890inline void
891loop_optimizer_finalize ()
892{
893 loop_optimizer_finalize (cfun);
894}
895
896/* Optimization passes. */
897enum
898{
899 UAP_UNROLL = 1, /* Enables unrolling of loops if it seems profitable. */
900 UAP_UNROLL_ALL = 2 /* Enables unrolling of all loops. */
901};
902
903extern void doloop_optimize_loops (void);
904extern void move_loop_invariants (void);
905extern auto_vec<basic_block> get_loop_hot_path (const class loop *loop);
906
907/* Returns the outermost loop of the loop nest that contains LOOP.*/
908inline class loop *
909loop_outermost (class loop *loop)
910{
911 unsigned n = vec_safe_length (v: loop->superloops);
912
913 if (n <= 1)
914 return loop;
915
916 return (*loop->superloops)[1];
917}
918
919extern void record_niter_bound (class loop *, const widest_int &, bool, bool);
920extern HOST_WIDE_INT get_estimated_loop_iterations_int (class loop *);
921extern HOST_WIDE_INT get_max_loop_iterations_int (const class loop *);
922extern HOST_WIDE_INT get_likely_max_loop_iterations_int (class loop *);
923extern bool get_estimated_loop_iterations (class loop *loop, widest_int *nit);
924extern bool get_max_loop_iterations (const class loop *loop, widest_int *nit);
925extern bool get_likely_max_loop_iterations (class loop *loop, widest_int *nit);
926extern int bb_loop_depth (const_basic_block);
927extern edge single_dom_exit (class loop *);
928extern profile_count loop_count_in (const class loop *loop);
929
930/* Converts VAL to widest_int. */
931
932inline widest_int
933gcov_type_to_wide_int (gcov_type val)
934{
935 HOST_WIDE_INT a[2];
936
937 a[0] = (unsigned HOST_WIDE_INT) val;
938 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
939 the size of type. */
940 val >>= HOST_BITS_PER_WIDE_INT - 1;
941 val >>= 1;
942 a[1] = (unsigned HOST_WIDE_INT) val;
943
944 return widest_int::from_array (val: a, len: 2);
945}
946#endif /* GCC_CFGLOOP_H */
947

source code of gcc/cfgloop.h