Branch data Line data Source code
1 : : /* Natural loop functions
2 : : Copyright (C) 1987-2024 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 : 7142 : loop_constraint_set (class loop *loop, unsigned c)
288 : : {
289 : 7142 : loop->constraints |= c;
290 : 7142 : }
291 : :
292 : : /* Clear C from the LOOP constraint. */
293 : : inline void
294 : 44131 : loop_constraint_clear (class loop *loop, unsigned c)
295 : : {
296 : 44131 : loop->constraints &= ~c;
297 : : }
298 : :
299 : : /* Check if C is set in the LOOP constraint. */
300 : : inline bool
301 : 31648215 : loop_constraint_set_p (class loop *loop, unsigned c)
302 : : {
303 : 31648215 : 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 bool loop_exits_to_bb_p (class loop *, basic_block);
374 : : extern bool 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 : 1845162 : 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 : 498948 : 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 : 5379596 : simple_loop_desc (class loop *loop)
521 : : {
522 : 5379596 : 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 : 1048754038 : get_loop (struct function *fn, unsigned num)
531 : : {
532 : 1610289709 : return (*loops_for_fn (fn)->larray)[num];
533 : : }
534 : :
535 : : /* Returns the number of superloops of LOOP. */
536 : :
537 : : inline unsigned
538 : 1267128089 : loop_depth (const class loop *loop)
539 : : {
540 : 2477811165 : 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 : 740368824 : loop_outer (const class loop *loop)
548 : : {
549 : 740368824 : unsigned n = vec_safe_length (loop->superloops);
550 : :
551 : 575763018 : if (n == 0)
552 : : return NULL;
553 : :
554 : 575763018 : return (*loop->superloops)[n - 1];
555 : : }
556 : :
557 : : /* Returns true if LOOP has at least one exit edge. */
558 : :
559 : : inline bool
560 : 1014865 : loop_has_exit_edges (const class loop *loop)
561 : : {
562 : 1014865 : 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 : 71098743 : get_loops (struct function *fn)
569 : : {
570 : 68861397 : struct loops *loops = loops_for_fn (fn);
571 : 68861397 : if (!loops)
572 : : return NULL;
573 : :
574 : 71098743 : 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 : 1711776186 : number_of_loops (struct function *fn)
582 : : {
583 : 543483773 : struct loops *loops = loops_for_fn (fn);
584 : 544792676 : if (!loops)
585 : : return 0;
586 : :
587 : 1106684586 : 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 : 3456443427 : loops_state_satisfies_p (function *fn, unsigned flags)
595 : : {
596 : 803338559 : return (loops_for_fn (fn)->state & flags) == flags;
597 : : }
598 : :
599 : : inline bool
600 : 3382592966 : loops_state_satisfies_p (unsigned flags)
601 : : {
602 : 3382657388 : return loops_state_satisfies_p (cfun, flags);
603 : : }
604 : :
605 : : /* Sets FLAGS to the loops state. */
606 : :
607 : : inline void
608 : 261454881 : loops_state_set (function *fn, unsigned flags)
609 : : {
610 : 232469312 : loops_for_fn (fn)->state |= flags;
611 : : }
612 : :
613 : : inline void
614 : 227315145 : loops_state_set (unsigned flags)
615 : : {
616 : 144481557 : loops_state_set (cfun, flags);
617 : 124676998 : }
618 : :
619 : : /* Clears FLAGS from the loops state. */
620 : :
621 : : inline void
622 : 196011290 : loops_state_clear (function *fn, unsigned flags)
623 : : {
624 : 60039844 : loops_for_fn (fn)->state &= ~flags;
625 : 10105044 : }
626 : :
627 : : inline void
628 : 145859101 : loops_state_clear (unsigned flags)
629 : : {
630 : 55661360 : if (!current_loops)
631 : : return;
632 : 145859101 : loops_state_clear (cfun, flags);
633 : : }
634 : :
635 : : /* Check loop structure invariants, if internal consistency checks are
636 : : enabled. */
637 : :
638 : : inline void
639 : 97241980 : 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 : 97241980 : loops_state_clear (LOOPS_NEED_FIXUP);
653 : 97241980 : if (flag_checking)
654 : 97239937 : verify_loop_structure ();
655 : 97241980 : }
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 : 1240936960 : 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 : 2481873920 : Iter (const loops_list &l, unsigned idx) : list (l), curr_idx (idx)
694 : : {
695 : 2481873920 : fill_curr_loop ();
696 : : }
697 : :
698 : 747644846 : T operator* () const { return curr_loop; }
699 : :
700 : : Iter &
701 : 747570974 : operator++ ()
702 : : {
703 : 1495141948 : if (curr_idx < list.to_visit.length ())
704 : : {
705 : : /* Bump the index and fill a new one. */
706 : 747570974 : curr_idx++;
707 : 747570974 : fill_curr_loop ();
708 : : }
709 : : else
710 : 0 : gcc_assert (!curr_loop);
711 : :
712 : 747570974 : return *this;
713 : : }
714 : :
715 : : bool
716 : 1988507934 : operator!= (const Iter &rhs) const
717 : : {
718 : 1988507934 : 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 : 1240936960 : begin ()
740 : : {
741 : 1240936960 : return iterator (*this, 0);
742 : : }
743 : :
744 : : iterator
745 : 1240936960 : end ()
746 : : {
747 : 2481873920 : 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 : 3229444894 : loops_list::Iter<T>::fill_curr_loop ()
781 : : {
782 : : int anum;
783 : :
784 : 3229444894 : while (this->list.to_visit.iterate (this->curr_idx, &anum))
785 : : {
786 : 747644846 : class loop *loop = get_loop (this->list.fn, anum);
787 : 747644846 : if (loop)
788 : : {
789 : 747644846 : curr_loop = loop;
790 : 747644846 : return;
791 : : }
792 : 0 : this->curr_idx++;
793 : : }
794 : :
795 : 2481800048 : 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 : 1240936960 : inline loops_list::loops_list (function *fn, unsigned flags, class loop *root)
804 : : {
805 : 1240936960 : struct loops *loops = loops_for_fn (fn);
806 : 1240936960 : gcc_assert (!root || loops);
807 : :
808 : : /* Check mutually exclusive flags should not co-exist. */
809 : 1240936960 : unsigned checked_flags = LI_ONLY_INNERMOST | LI_FROM_INNERMOST;
810 : 1240936960 : gcc_assert ((flags & checked_flags) != checked_flags);
811 : :
812 : 1240936960 : this->fn = fn;
813 : 1240936960 : if (!loops)
814 : : return;
815 : :
816 : 1240936960 : class loop *tree_root = root ? root : loops->tree_root;
817 : :
818 : 2481873920 : 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 : 1240936960 : if (flags & LI_ONLY_INNERMOST && tree_root == loops->tree_root)
825 : : {
826 : 4291920 : gcc_assert (tree_root->num == 0);
827 : 4291920 : if (tree_root->inner == NULL)
828 : : {
829 : 3320085 : if (flags & LI_INCLUDE_ROOT)
830 : 0 : this->to_visit.quick_push (0);
831 : :
832 : 3320085 : return;
833 : : }
834 : :
835 : : class loop *aloop;
836 : : unsigned int i;
837 : 4301711 : for (i = 1; vec_safe_iterate (loops->larray, i, &aloop); i++)
838 : 3329876 : if (aloop != NULL && aloop->inner == NULL)
839 : 2225274 : this->to_visit.quick_push (aloop->num);
840 : : }
841 : : else
842 : 1236645040 : 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 : 41608779 : loop_optimizer_finalize ()
892 : : {
893 : 41608779 : loop_optimizer_finalize (cfun);
894 : 8859890 : }
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 */
|
