Line data Source code
1 : /* Natural loop functions
2 : Copyright (C) 1987-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify it under
7 : the terms of the GNU General Public License as published by the Free
8 : Software Foundation; either version 3, or (at your option) any later
9 : version.
10 :
11 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : 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.
15 :
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/>. */
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. */
26 : enum lpt_dec
27 : {
28 : LPT_NONE,
29 : LPT_UNROLL_CONSTANT,
30 : LPT_UNROLL_RUNTIME,
31 : LPT_UNROLL_STUPID
32 : };
33 :
34 : struct GTY (()) lpt_decision {
35 : enum lpt_dec decision;
36 : unsigned times;
37 : };
38 :
39 : /* The type of extend applied to an IV. */
40 : enum iv_extend_code
41 : {
42 : IV_SIGN_EXTEND,
43 : IV_ZERO_EXTEND,
44 : IV_UNKNOWN_EXTEND
45 : };
46 :
47 : typedef 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 :
52 : class GTY ((chain_next ("%h.next"))) nb_iter_bound {
53 : public:
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 :
77 : struct 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 :
89 : struct 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 :
98 : typedef 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. */
102 : enum 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. */
113 : struct 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. */
120 : class GTY ((chain_next ("%h.next"))) loop {
121 : public:
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. */
286 : inline void
287 8260 : loop_constraint_set (class loop *loop, unsigned c)
288 : {
289 8260 : loop->constraints |= c;
290 8260 : }
291 :
292 : /* Clear C from the LOOP constraint. */
293 : inline void
294 65098 : loop_constraint_clear (class loop *loop, unsigned c)
295 : {
296 65098 : loop->constraints &= ~c;
297 : }
298 :
299 : /* Check if C is set in the LOOP constraint. */
300 : inline bool
301 36804297 : loop_constraint_set_p (class loop *loop, unsigned c)
302 : {
303 36804297 : return (loop->constraints & c) == c;
304 : }
305 :
306 : /* Flags for state of loop structure. */
307 : enum
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. */
324 : struct 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. */
341 : bool bb_loop_header_p (basic_block);
342 : void init_loops_structure (struct function *, struct loops *, unsigned);
343 : extern struct loops *flow_loops_find (struct loops *);
344 : extern void disambiguate_loops_with_multiple_latches (void);
345 : extern void flow_loops_free (struct loops *);
346 : extern void flow_loops_dump (FILE *,
347 : void (*)(const class loop *, FILE *, int), int);
348 : extern void flow_loop_dump (const class loop *, FILE *,
349 : void (*)(const class loop *, FILE *, int), int);
350 : class loop *alloc_loop (void);
351 : extern void flow_loop_free (class loop *);
352 : int flow_loop_nodes_find (basic_block, class loop *);
353 : unsigned fix_loop_structure (bitmap changed_bbs);
354 : bool mark_irreducible_loops (void);
355 : void release_recorded_exits (function *);
356 : void record_loop_exits (void);
357 : void rescan_loop_exit (edge, bool, bool);
358 : void sort_sibling_loops (function *);
359 :
360 : /* Loop data structure manipulation/querying. */
361 : extern void flow_loop_tree_node_add (class loop *, class loop *,
362 : class loop * = NULL);
363 : extern void flow_loop_tree_node_remove (class loop *);
364 : extern bool flow_loop_nested_p (const class loop *, const class loop *);
365 : extern bool flow_bb_inside_loop_p (const class loop *, const_basic_block);
366 : extern class loop * find_common_loop (class loop *, class loop *);
367 : class loop *superloop_at_depth (class loop *, unsigned);
368 : struct eni_weights;
369 : extern int num_loop_insns (const class loop *);
370 : extern int average_num_loop_insns (const class loop *);
371 : extern unsigned get_loop_level (const class loop *);
372 : extern bool loop_exit_edge_p (const class loop *, const_edge);
373 : extern edge loop_exits_to_bb_p (class loop *, basic_block);
374 : extern edge loop_exits_from_bb_p (class loop *, basic_block);
375 : extern void mark_loop_exit_edges (void);
376 : extern dump_user_location_t get_loop_location (class loop *loop);
377 :
378 : /* Loops & cfg manipulation. */
379 : extern basic_block *get_loop_body (const class loop *);
380 : extern unsigned get_loop_body_with_size (const class loop *, basic_block *,
381 : unsigned);
382 : extern basic_block *get_loop_body_in_dom_order (const class loop *);
383 : extern basic_block *get_loop_body_in_bfs_order (const class loop *);
384 : extern basic_block *get_loop_body_in_custom_order (const class loop *,
385 : int (*) (const void *, const void *));
386 : extern basic_block *get_loop_body_in_custom_order (const class loop *, void *,
387 : int (*) (const void *, const void *, void *));
388 :
389 : extern auto_vec<edge> get_loop_exit_edges (const class loop *, basic_block * = NULL);
390 : extern edge single_exit (const class loop *);
391 : extern edge single_likely_exit (class loop *loop, const vec<edge> &);
392 : extern unsigned num_loop_branches (const class loop *);
393 :
394 : extern edge loop_preheader_edge (const class loop *);
395 : extern edge loop_latch_edge (const class loop *);
396 :
397 : extern void add_bb_to_loop (basic_block, class loop *);
398 : extern void remove_bb_from_loops (basic_block);
399 :
400 : extern void cancel_loop_tree (class loop *);
401 : extern void delete_loop (class loop *);
402 :
403 :
404 : extern void verify_loop_structure (void);
405 :
406 : /* Loop analysis. */
407 : extern bool just_once_each_iteration_p (const class loop *, const_basic_block);
408 : gcov_type expected_loop_iterations_unbounded (const class loop *,
409 : bool *read_profile_p = NULL);
410 : extern bool expected_loop_iterations_by_profile (const class loop *loop,
411 : sreal *ret,
412 : bool *reliable = NULL);
413 : extern bool maybe_flat_loop_profile (const class loop *);
414 : extern unsigned expected_loop_iterations (class loop *);
415 : extern rtx doloop_condition_get (rtx_insn *);
416 :
417 : void mark_loop_for_removal (loop_p);
418 : void 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 :
441 2936353 : class rtx_iv
442 : {
443 : public:
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 :
468 591598 : class GTY(()) niter_desc
469 : {
470 : public:
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 :
507 : extern void iv_analysis_loop_init (class loop *);
508 : extern bool iv_analyze (rtx_insn *, scalar_int_mode, rtx, class rtx_iv *);
509 : extern bool iv_analyze_result (rtx_insn *, rtx, class rtx_iv *);
510 : extern bool iv_analyze_expr (rtx_insn *, scalar_int_mode, rtx,
511 : class rtx_iv *);
512 : extern rtx get_iv_value (class rtx_iv *, rtx);
513 : extern bool biv_p (rtx_insn *, scalar_int_mode, rtx);
514 : extern void iv_analysis_done (void);
515 :
516 : extern class niter_desc *get_simple_loop_desc (class loop *loop);
517 : extern void free_simple_loop_desc (class loop *loop);
518 :
519 : inline class niter_desc *
520 7062011 : simple_loop_desc (class loop *loop)
521 : {
522 7062011 : 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 :
529 : inline class loop *
530 1267917847 : get_loop (struct function *fn, unsigned num)
531 : {
532 1882840219 : return (*loops_for_fn (fn)->larray)[num];
533 : }
534 :
535 : /* Returns the number of superloops of LOOP. */
536 :
537 : inline unsigned
538 1477767302 : loop_depth (const class loop *loop)
539 : {
540 2828684953 : return vec_safe_length (loop->superloops);
541 : }
542 :
543 : /* Returns the immediate superloop of LOOP, or NULL if LOOP is the outermost
544 : loop. */
545 :
546 : inline class loop *
547 875187753 : loop_outer (const class loop *loop)
548 : {
549 875187753 : unsigned n = vec_safe_length (loop->superloops);
550 :
551 682441479 : if (n == 0)
552 : return NULL;
553 :
554 682441479 : return (*loop->superloops)[n - 1];
555 : }
556 :
557 : /* Returns true if LOOP has at least one exit edge. */
558 :
559 : inline bool
560 1192024 : loop_has_exit_edges (const class loop *loop)
561 : {
562 1192024 : return loop->exits->next->e != NULL;
563 : }
564 :
565 : /* Returns the list of loops in FN. */
566 :
567 : inline vec<loop_p, va_gc> *
568 75794015 : get_loops (struct function *fn)
569 : {
570 73345760 : struct loops *loops = loops_for_fn (fn);
571 73345760 : if (!loops)
572 : return NULL;
573 :
574 75794015 : 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 :
580 : inline unsigned
581 1887452878 : number_of_loops (struct function *fn)
582 : {
583 602647126 : struct loops *loops = loops_for_fn (fn);
584 604100206 : if (!loops)
585 : return 0;
586 :
587 1220181907 : return vec_safe_length (loops->larray);
588 : }
589 :
590 : /* Returns true if state of the loops satisfies all properties
591 : described by FLAGS. */
592 :
593 : inline bool
594 3933818041 : loops_state_satisfies_p (function *fn, unsigned flags)
595 : {
596 901018727 : return (loops_for_fn (fn)->state & flags) == flags;
597 : }
598 :
599 : inline bool
600 3852404383 : loops_state_satisfies_p (unsigned flags)
601 : {
602 3852404383 : return loops_state_satisfies_p (cfun, flags);
603 : }
604 :
605 : /* Sets FLAGS to the loops state. */
606 :
607 : inline void
608 291953781 : loops_state_set (function *fn, unsigned flags)
609 : {
610 259424249 : loops_for_fn (fn)->state |= flags;
611 : }
612 :
613 : inline void
614 254830514 : loops_state_set (unsigned flags)
615 : {
616 157820214 : loops_state_set (cfun, flags);
617 142511557 : }
618 :
619 : /* Clears FLAGS from the loops state. */
620 :
621 : inline void
622 214747537 : loops_state_clear (function *fn, unsigned flags)
623 : {
624 65731142 : loops_for_fn (fn)->state &= ~flags;
625 11284733 : }
626 :
627 : inline void
628 160059676 : loops_state_clear (unsigned flags)
629 : {
630 60874663 : if (!current_loops)
631 : return;
632 160059676 : loops_state_clear (cfun, flags);
633 : }
634 :
635 : /* Check loop structure invariants, if internal consistency checks are
636 : enabled. */
637 :
638 : inline void
639 107100737 : checking_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 107100737 : loops_state_clear (LOOPS_NEED_FIXUP);
653 107100737 : if (flag_checking)
654 107099000 : verify_loop_structure ();
655 107100737 : }
656 :
657 : /* Loop iterators. */
658 :
659 : /* Flags for loop iteration. */
660 :
661 : enum 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.) */
672 : template <typename T>
673 : constexpr const T &
674 : as_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 :
685 1369371032 : class loops_list
686 : {
687 : public:
688 : loops_list (function *fn, unsigned flags, class loop *root = nullptr);
689 :
690 : template <typename T> class Iter
691 : {
692 : public:
693 2738742064 : Iter (const loops_list &l, unsigned idx) : list (l), curr_idx (idx)
694 : {
695 2738742064 : fill_curr_loop ();
696 : }
697 :
698 923079174 : T operator* () const { return curr_loop; }
699 :
700 : Iter &
701 923002442 : operator++ ()
702 : {
703 923002442 : if (curr_idx < list.to_visit.length ())
704 : {
705 : /* Bump the index and fill a new one. */
706 923002442 : curr_idx++;
707 923002442 : fill_curr_loop ();
708 : }
709 : else
710 0 : gcc_assert (!curr_loop);
711 :
712 923002442 : return *this;
713 : }
714 :
715 : bool
716 2292373474 : operator!= (const Iter &rhs) const
717 : {
718 2292373474 : 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 1369371032 : begin ()
740 : {
741 1369371032 : return iterator (*this, 0);
742 : }
743 :
744 : iterator
745 1369371032 : end ()
746 : {
747 2738742064 : 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 :
762 : private:
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 :
778 : template <typename T>
779 : inline void
780 3661744506 : loops_list::Iter<T>::fill_curr_loop ()
781 : {
782 : int anum;
783 :
784 3661744506 : while (this->list.to_visit.iterate (this->curr_idx, &anum))
785 : {
786 923079174 : class loop *loop = get_loop (this->list.fn, anum);
787 923079174 : if (loop)
788 : {
789 923079174 : curr_loop = loop;
790 923079174 : return;
791 : }
792 0 : this->curr_idx++;
793 : }
794 :
795 2738665332 : 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 :
803 1369371032 : inline loops_list::loops_list (function *fn, unsigned flags, class loop *root)
804 : {
805 1369371032 : struct loops *loops = loops_for_fn (fn);
806 1369371032 : gcc_assert (!root || loops);
807 :
808 : /* Check mutually exclusive flags should not co-exist. */
809 1369371032 : unsigned checked_flags = LI_ONLY_INNERMOST | LI_FROM_INNERMOST;
810 1369371032 : gcc_assert ((flags & checked_flags) != checked_flags);
811 :
812 1369371032 : this->fn = fn;
813 1369371032 : if (!loops)
814 : return;
815 :
816 1369371032 : class loop *tree_root = root ? root : loops->tree_root;
817 :
818 2738742064 : this->to_visit.reserve_exact (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 1369371032 : if (flags & LI_ONLY_INNERMOST && tree_root == loops->tree_root)
825 : {
826 4940766 : gcc_assert (tree_root->num == 0);
827 4940766 : if (tree_root->inner == NULL)
828 : {
829 3654175 : if (flags & LI_INCLUDE_ROOT)
830 0 : this->to_visit.quick_push (0);
831 :
832 3654175 : return;
833 : }
834 :
835 : class loop *aloop;
836 : unsigned int i;
837 6073294 : for (i = 1; vec_safe_iterate (loops->larray, i, &aloop); i++)
838 4786703 : if (aloop != NULL && aloop->inner == NULL)
839 3113632 : this->to_visit.quick_push (aloop->num);
840 : }
841 : else
842 1364430266 : walk_loop_tree (tree_root, flags);
843 : }
844 :
845 : /* The properties of the target. */
846 : struct 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 :
864 : extern struct target_cfgloop default_target_cfgloop;
865 : #if SWITCHABLE_TARGET
866 : extern 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. */
884 : extern unsigned estimate_reg_pressure_cost (unsigned, unsigned, bool, bool);
885 : extern void init_set_costs (void);
886 :
887 : /* Loop optimizer initialization. */
888 : extern void loop_optimizer_init (unsigned);
889 : extern void loop_optimizer_finalize (function *, bool = false);
890 : inline void
891 46064217 : loop_optimizer_finalize ()
892 : {
893 46064217 : loop_optimizer_finalize (cfun);
894 9718344 : }
895 :
896 : /* Optimization passes. */
897 : enum
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 :
903 : extern void doloop_optimize_loops (void);
904 : extern void move_loop_invariants (void);
905 : extern 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.*/
908 : inline class loop *
909 187 : loop_outermost (class loop *loop)
910 : {
911 187 : unsigned n = vec_safe_length (loop->superloops);
912 :
913 187 : if (n <= 1)
914 : return loop;
915 :
916 12 : return (*loop->superloops)[1];
917 : }
918 :
919 : extern void record_niter_bound (class loop *, const widest_int &, bool, bool);
920 : extern HOST_WIDE_INT get_estimated_loop_iterations_int (class loop *);
921 : extern HOST_WIDE_INT get_max_loop_iterations_int (const class loop *);
922 : extern HOST_WIDE_INT get_likely_max_loop_iterations_int (class loop *);
923 : extern bool get_estimated_loop_iterations (class loop *loop, widest_int *nit);
924 : extern bool get_max_loop_iterations (const class loop *loop, widest_int *nit);
925 : extern bool get_likely_max_loop_iterations (class loop *loop, widest_int *nit);
926 : extern int bb_loop_depth (const_basic_block);
927 : extern edge single_dom_exit (class loop *);
928 : extern profile_count loop_count_in (const class loop *loop);
929 :
930 : /* Converts VAL to widest_int. */
931 :
932 : inline widest_int
933 : gcov_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 (a, 2);
945 : }
946 : #endif /* GCC_CFGLOOP_H */
|
