]>
Commit | Line | Data |
---|---|---|
862be747 | 1 | /* Natural loop functions |
d353bf18 | 2 | Copyright (C) 1987-2015 Free Software Foundation, Inc. |
862be747 | 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 | |
8c4c00c1 | 8 | Software Foundation; either version 3, or (at your option) any later |
862be747 | 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 | |
8c4c00c1 | 17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
862be747 | 19 | |
bcf3c70d | 20 | #ifndef GCC_CFGLOOP_H |
21 | #define GCC_CFGLOOP_H | |
22 | ||
0f71a633 | 23 | #include "bitmap.h" |
24 | #include "sbitmap.h" | |
a3020f2f | 25 | #include "tm.h" |
26 | #include "hard-reg-set.h" | |
424a4a92 | 27 | #include "function.h" |
e5a23585 | 28 | #include "cfgloopmanip.h" |
0f71a633 | 29 | |
862be747 | 30 | /* Structure to hold decision about unrolling/peeling. */ |
31 | enum lpt_dec | |
32 | { | |
33 | LPT_NONE, | |
862be747 | 34 | LPT_UNROLL_CONSTANT, |
35 | LPT_UNROLL_RUNTIME, | |
36 | LPT_UNROLL_STUPID | |
37 | }; | |
38 | ||
fb1e4f4a | 39 | struct GTY (()) lpt_decision { |
862be747 | 40 | enum lpt_dec decision; |
41 | unsigned times; | |
42 | }; | |
43 | ||
aedb7bf8 | 44 | /* The type of extend applied to an IV. */ |
45 | enum iv_extend_code | |
46 | { | |
47 | IV_SIGN_EXTEND, | |
48 | IV_ZERO_EXTEND, | |
49 | IV_UNKNOWN_EXTEND | |
50 | }; | |
51 | ||
bc3c8ad4 | 52 | /* The structure describing a bound on number of iterations of a loop. */ |
53 | ||
fb1e4f4a | 54 | struct GTY ((chain_next ("%h.next"))) nb_iter_bound { |
faa56cf9 | 55 | /* The statement STMT is executed at most ... */ |
75a70cf9 | 56 | gimple stmt; |
faa56cf9 | 57 | |
58 | /* ... BOUND + 1 times (BOUND must be an unsigned constant). | |
59 | The + 1 is added for the following reasons: | |
60 | ||
61 | a) 0 would otherwise be unused, while we would need to care more about | |
62 | overflows (as MAX + 1 is sometimes produced as the estimate on number | |
63 | of executions of STMT). | |
64 | b) it is consistent with the result of number_of_iterations_exit. */ | |
5de9d3ed | 65 | widest_int bound; |
faa56cf9 | 66 | |
48e1416a | 67 | /* True if the statement will cause the loop to be leaved the (at most) |
faa56cf9 | 68 | BOUND + 1-st time it is executed, that is, all the statements after it |
69 | are executed at most BOUND times. */ | |
70 | bool is_exit; | |
71 | ||
faa56cf9 | 72 | /* The next bound in the list. */ |
bc3c8ad4 | 73 | struct nb_iter_bound *next; |
bc3c8ad4 | 74 | }; |
75 | ||
dce58e66 | 76 | /* Description of the loop exit. */ |
77 | ||
2ef51f0e | 78 | struct GTY ((for_user)) loop_exit { |
dce58e66 | 79 | /* The exit edge. */ |
161dfa6e | 80 | edge e; |
dce58e66 | 81 | |
82 | /* Previous and next exit in the list of the exits of the loop. */ | |
83 | struct loop_exit *prev; | |
84 | struct loop_exit *next; | |
85 | ||
86 | /* Next element in the list of loops from that E exits. */ | |
87 | struct loop_exit *next_e; | |
88 | }; | |
89 | ||
2ef51f0e | 90 | struct loop_exit_hasher : ggc_hasher<loop_exit *> |
91 | { | |
92 | typedef edge compare_type; | |
93 | ||
94 | static hashval_t hash (loop_exit *); | |
95 | static bool equal (loop_exit *, edge); | |
96 | static void remove (loop_exit *); | |
97 | }; | |
98 | ||
9e3536f4 | 99 | typedef struct loop *loop_p; |
9e3536f4 | 100 | |
f780cc25 | 101 | /* An integer estimation of the number of iterations. Estimate_state |
102 | describes what is the state of the estimation. */ | |
103 | enum loop_estimation | |
104 | { | |
105 | /* Estimate was not computed yet. */ | |
106 | EST_NOT_COMPUTED, | |
107 | /* Estimate is ready. */ | |
7a569539 | 108 | EST_AVAILABLE, |
109 | EST_LAST | |
f780cc25 | 110 | }; |
111 | ||
05032b10 | 112 | /* The structure describing non-overflow control induction variable for |
113 | loop's exit edge. */ | |
114 | struct GTY ((chain_next ("%h.next"))) control_iv { | |
115 | tree base; | |
116 | tree step; | |
117 | struct control_iv *next; | |
118 | }; | |
119 | ||
862be747 | 120 | /* Structure to hold information for each natural loop. */ |
fb1e4f4a | 121 | struct GTY ((chain_next ("%h.next"))) loop { |
862be747 | 122 | /* Index into loops array. */ |
123 | int num; | |
124 | ||
0ac758f7 | 125 | /* Number of loop insns. */ |
126 | unsigned ninsns; | |
127 | ||
862be747 | 128 | /* Basic block of loop header. */ |
161dfa6e | 129 | basic_block header; |
862be747 | 130 | |
131 | /* Basic block of loop latch. */ | |
161dfa6e | 132 | basic_block latch; |
862be747 | 133 | |
862be747 | 134 | /* For loop unrolling/peeling decision. */ |
135 | struct lpt_decision lpt_decision; | |
136 | ||
862be747 | 137 | /* Average number of executed insns per iteration. */ |
138 | unsigned av_ninsns; | |
139 | ||
862be747 | 140 | /* Number of blocks contained within the loop. */ |
141 | unsigned num_nodes; | |
142 | ||
9e3536f4 | 143 | /* Superloops of the loop, starting with the outermost loop. */ |
f1f41a6c | 144 | vec<loop_p, va_gc> *superloops; |
862be747 | 145 | |
146 | /* The first inner (child) loop or NULL if innermost loop. */ | |
147 | struct loop *inner; | |
148 | ||
149 | /* Link to the next (sibling) loop. */ | |
150 | struct loop *next; | |
151 | ||
862be747 | 152 | /* Auxiliary info specific to a pass. */ |
ccae4f9f | 153 | PTR GTY ((skip (""))) aux; |
862be747 | 154 | |
134c053e | 155 | /* The number of times the latch of the loop is executed. This can be an |
156 | INTEGER_CST, or a symbolic expression representing the number of | |
157 | iterations like "N - 1", or a COND_EXPR containing the runtime | |
158 | conditions under which the number of iterations is non zero. | |
159 | ||
160 | Don't access this field directly: number_of_latch_executions | |
161 | computes and caches the computed information in this field. */ | |
c2c3fd24 | 162 | tree nb_iterations; |
163 | ||
8fe79ba5 | 164 | /* An integer guaranteed to be greater or equal to nb_iterations. Only |
165 | valid if any_upper_bound is true. */ | |
5de9d3ed | 166 | widest_int nb_iterations_upper_bound; |
4b4ab846 | 167 | |
8fe79ba5 | 168 | /* An integer giving an estimate on nb_iterations. Unlike |
169 | nb_iterations_upper_bound, there is no guarantee that it is at least | |
170 | nb_iterations. */ | |
5de9d3ed | 171 | widest_int nb_iterations_estimate; |
bc3c8ad4 | 172 | |
0ac758f7 | 173 | bool any_upper_bound; |
174 | bool any_estimate; | |
175 | ||
609c710b | 176 | /* True if the loop can be parallel. */ |
177 | bool can_be_parallel; | |
178 | ||
228bf2b8 | 179 | /* True if -Waggressive-loop-optimizations warned about this loop |
180 | already. */ | |
181 | bool warned_aggressive_loop_optimizations; | |
182 | ||
0ac758f7 | 183 | /* An integer estimation of the number of iterations. Estimate_state |
184 | describes what is the state of the estimation. */ | |
185 | enum loop_estimation estimate_state; | |
186 | ||
3d483a94 | 187 | /* If > 0, an integer, where the user asserted that for any |
188 | I in [ 0, nb_iterations ) and for any J in | |
189 | [ I, min ( I + safelen, nb_iterations ) ), the Ith and Jth iterations | |
190 | of the loop can be safely evaluated concurrently. */ | |
191 | int safelen; | |
192 | ||
c71d3c24 | 193 | /* True if this loop should never be vectorized. */ |
194 | bool dont_vectorize; | |
195 | ||
eb71996d | 196 | /* True if we should try harder to vectorize this loop. */ |
197 | bool force_vectorize; | |
198 | ||
3d483a94 | 199 | /* For SIMD loops, this is a unique identifier of the loop, referenced |
200 | by IFN_GOMP_SIMD_VF, IFN_GOMP_SIMD_LANE and IFN_GOMP_SIMD_LAST_LANE | |
201 | builtins. */ | |
202 | tree simduid; | |
203 | ||
b9d73ea6 | 204 | /* Upper bound on number of iterations of a loop. */ |
205 | struct nb_iter_bound *bounds; | |
bb445479 | 206 | |
05032b10 | 207 | /* Non-overflow control ivs of a loop. */ |
208 | struct control_iv *control_ivs; | |
209 | ||
dce58e66 | 210 | /* Head of the cyclic list of the exits of the loop. */ |
ccae4f9f | 211 | struct loop_exit *exits; |
427286b3 | 212 | |
213 | /* Number of iteration analysis data for RTL. */ | |
214 | struct niter_desc *simple_loop_desc; | |
6437689e | 215 | |
6437689e | 216 | /* For sanity checking during loop fixup we record here the former |
217 | loop header for loops marked for removal. Note that this prevents | |
218 | the basic-block from being collected but its index can still be | |
219 | reused. */ | |
220 | basic_block former_header; | |
862be747 | 221 | }; |
222 | ||
223 | /* Flags for state of loop structure. */ | |
224 | enum | |
225 | { | |
226 | LOOPS_HAVE_PREHEADERS = 1, | |
227 | LOOPS_HAVE_SIMPLE_LATCHES = 2, | |
bb445479 | 228 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4, |
4a6f9e19 | 229 | LOOPS_HAVE_RECORDED_EXITS = 8, |
d8a0d6b8 | 230 | LOOPS_MAY_HAVE_MULTIPLE_LATCHES = 16, |
eb2a640e | 231 | LOOP_CLOSED_SSA = 32, |
e1ab7874 | 232 | LOOPS_NEED_FIXUP = 64, |
233 | LOOPS_HAVE_FALLTHRU_PREHEADERS = 128 | |
862be747 | 234 | }; |
235 | ||
c8d055f6 | 236 | #define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \ |
237 | | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) | |
4a6f9e19 | 238 | #define AVOID_CFG_MODIFICATIONS (LOOPS_MAY_HAVE_MULTIPLE_LATCHES) |
c8d055f6 | 239 | |
862be747 | 240 | /* Structure to hold CFG information about natural loops within a function. */ |
fb1e4f4a | 241 | struct GTY (()) loops { |
677144a0 | 242 | /* State of loops. */ |
243 | int state; | |
862be747 | 244 | |
17519ba0 | 245 | /* Array of the loops. */ |
f1f41a6c | 246 | vec<loop_p, va_gc> *larray; |
862be747 | 247 | |
dce58e66 | 248 | /* Maps edges to the list of their descriptions as loop exits. Edges |
249 | whose sources or destinations have loop_father == NULL (which may | |
250 | happen during the cfg manipulations) should not appear in EXITS. */ | |
2ef51f0e | 251 | hash_table<loop_exit_hasher> *GTY(()) exits; |
dce58e66 | 252 | |
862be747 | 253 | /* Pointer to root of loop hierarchy tree. */ |
254 | struct loop *tree_root; | |
862be747 | 255 | }; |
256 | ||
862be747 | 257 | /* Loop recognition. */ |
ff829efa | 258 | bool bb_loop_header_p (basic_block); |
7a569539 | 259 | void init_loops_structure (struct function *, struct loops *, unsigned); |
ff829efa | 260 | extern struct loops *flow_loops_find (struct loops *); |
4a6f9e19 | 261 | extern void disambiguate_loops_with_multiple_latches (void); |
4c9e08a4 | 262 | extern void flow_loops_free (struct loops *); |
7194de72 | 263 | extern void flow_loops_dump (FILE *, |
4c9e08a4 | 264 | void (*)(const struct loop *, FILE *, int), int); |
265 | extern void flow_loop_dump (const struct loop *, FILE *, | |
266 | void (*)(const struct loop *, FILE *, int), int); | |
dce58e66 | 267 | struct loop *alloc_loop (void); |
4c9e08a4 | 268 | extern void flow_loop_free (struct loop *); |
053fdd99 | 269 | int flow_loop_nodes_find (basic_block, struct loop *); |
b6f3c6f1 | 270 | unsigned fix_loop_structure (bitmap changed_bbs); |
c9263b6a | 271 | bool mark_irreducible_loops (void); |
dce58e66 | 272 | void release_recorded_exits (void); |
273 | void record_loop_exits (void); | |
274 | void rescan_loop_exit (edge, bool, bool); | |
862be747 | 275 | |
917bbcab | 276 | /* Loop data structure manipulation/querying. */ |
4c9e08a4 | 277 | extern void flow_loop_tree_node_add (struct loop *, struct loop *); |
278 | extern void flow_loop_tree_node_remove (struct loop *); | |
4c9e08a4 | 279 | extern bool flow_loop_nested_p (const struct loop *, const struct loop *); |
7ecb5bb2 | 280 | extern bool flow_bb_inside_loop_p (const struct loop *, const_basic_block); |
4c9e08a4 | 281 | extern struct loop * find_common_loop (struct loop *, struct loop *); |
7d23383d | 282 | struct loop *superloop_at_depth (struct loop *, unsigned); |
bc8bb825 | 283 | struct eni_weights_d; |
7ecb5bb2 | 284 | extern int num_loop_insns (const struct loop *); |
285 | extern int average_num_loop_insns (const struct loop *); | |
2d49f824 | 286 | extern unsigned get_loop_level (const struct loop *); |
7ecb5bb2 | 287 | extern bool loop_exit_edge_p (const struct loop *, const_edge); |
259c0e44 | 288 | extern bool loop_exits_to_bb_p (struct loop *, basic_block); |
289 | extern bool loop_exits_from_bb_p (struct loop *, basic_block); | |
7194de72 | 290 | extern void mark_loop_exit_edges (void); |
f55775aa | 291 | extern location_t get_loop_location (struct loop *loop); |
862be747 | 292 | |
293 | /* Loops & cfg manipulation. */ | |
4c9e08a4 | 294 | extern basic_block *get_loop_body (const struct loop *); |
4a6f9e19 | 295 | extern unsigned get_loop_body_with_size (const struct loop *, basic_block *, |
296 | unsigned); | |
f9cce2dc | 297 | extern basic_block *get_loop_body_in_dom_order (const struct loop *); |
07c03fb0 | 298 | extern basic_block *get_loop_body_in_bfs_order (const struct loop *); |
48e1416a | 299 | extern basic_block *get_loop_body_in_custom_order (const struct loop *, |
e1ab7874 | 300 | int (*) (const void *, const void *)); |
301 | ||
f1f41a6c | 302 | extern vec<edge> get_loop_exit_edges (const struct loop *); |
97fc8ad6 | 303 | extern edge single_exit (const struct loop *); |
304 | extern edge single_likely_exit (struct loop *loop); | |
f9cce2dc | 305 | extern unsigned num_loop_branches (const struct loop *); |
862be747 | 306 | |
4c9e08a4 | 307 | extern edge loop_preheader_edge (const struct loop *); |
308 | extern edge loop_latch_edge (const struct loop *); | |
862be747 | 309 | |
4c9e08a4 | 310 | extern void add_bb_to_loop (basic_block, struct loop *); |
311 | extern void remove_bb_from_loops (basic_block); | |
862be747 | 312 | |
7194de72 | 313 | extern void cancel_loop_tree (struct loop *); |
17519ba0 | 314 | extern void delete_loop (struct loop *); |
862be747 | 315 | |
862be747 | 316 | |
7194de72 | 317 | extern void verify_loop_structure (void); |
862be747 | 318 | |
319 | /* Loop analysis. */ | |
7ecb5bb2 | 320 | extern bool just_once_each_iteration_p (const struct loop *, const_basic_block); |
d97e22fb | 321 | gcov_type expected_loop_iterations_unbounded (const struct loop *); |
4c9e08a4 | 322 | extern unsigned expected_loop_iterations (const struct loop *); |
fc2abfd3 | 323 | extern rtx doloop_condition_get (rtx); |
6a606e3c | 324 | |
d25159cc | 325 | void mark_loop_for_removal (loop_p); |
326 | ||
f9cce2dc | 327 | /* Induction variable analysis. */ |
328 | ||
329 | /* The description of induction variable. The things are a bit complicated | |
330 | due to need to handle subregs and extends. The value of the object described | |
331 | by it can be obtained as follows (all computations are done in extend_mode): | |
332 | ||
333 | Value in i-th iteration is | |
334 | delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)). | |
335 | ||
336 | If first_special is true, the value in the first iteration is | |
337 | delta + mult * base | |
a0c938f0 | 338 | |
21f1e711 | 339 | If extend = UNKNOWN, first_special must be false, delta 0, mult 1 and value is |
f9cce2dc | 340 | subreg_{mode} (base + i * step) |
341 | ||
342 | The get_iv_value function can be used to obtain these expressions. | |
343 | ||
344 | ??? Add a third mode field that would specify the mode in that inner | |
345 | computation is done, which would enable it to be different from the | |
346 | outer one? */ | |
347 | ||
348 | struct rtx_iv | |
349 | { | |
350 | /* Its base and step (mode of base and step is supposed to be extend_mode, | |
351 | see the description above). */ | |
352 | rtx base, step; | |
353 | ||
aedb7bf8 | 354 | /* The type of extend applied to it (IV_SIGN_EXTEND, IV_ZERO_EXTEND, |
355 | or IV_UNKNOWN_EXTEND). */ | |
356 | enum iv_extend_code extend; | |
f9cce2dc | 357 | |
358 | /* Operations applied in the extended mode. */ | |
359 | rtx delta, mult; | |
360 | ||
361 | /* The mode it is extended to. */ | |
3754d046 | 362 | machine_mode extend_mode; |
f9cce2dc | 363 | |
364 | /* The mode the variable iterates in. */ | |
3754d046 | 365 | machine_mode mode; |
f9cce2dc | 366 | |
f9cce2dc | 367 | /* Whether the first iteration needs to be handled specially. */ |
368 | unsigned first_special : 1; | |
369 | }; | |
370 | ||
9c1ccc0f | 371 | /* The description of an exit from the loop and of the number of iterations |
372 | till we take the exit. */ | |
f9cce2dc | 373 | |
427286b3 | 374 | struct GTY(()) niter_desc |
f9cce2dc | 375 | { |
376 | /* The edge out of the loop. */ | |
377 | edge out_edge; | |
378 | ||
379 | /* The other edge leading from the condition. */ | |
380 | edge in_edge; | |
381 | ||
382 | /* True if we are able to say anything about number of iterations of the | |
383 | loop. */ | |
384 | bool simple_p; | |
385 | ||
386 | /* True if the loop iterates the constant number of times. */ | |
387 | bool const_iter; | |
388 | ||
389 | /* Number of iterations if constant. */ | |
3a4303e7 | 390 | uint64_t niter; |
f9cce2dc | 391 | |
f9cce2dc | 392 | /* Assumptions under that the rest of the information is valid. */ |
393 | rtx assumptions; | |
394 | ||
395 | /* Assumptions under that the loop ends before reaching the latch, | |
396 | even if value of niter_expr says otherwise. */ | |
397 | rtx noloop_assumptions; | |
398 | ||
399 | /* Condition under that the loop is infinite. */ | |
400 | rtx infinite; | |
401 | ||
402 | /* Whether the comparison is signed. */ | |
403 | bool signed_p; | |
404 | ||
405 | /* The mode in that niter_expr should be computed. */ | |
3754d046 | 406 | machine_mode mode; |
f9cce2dc | 407 | |
408 | /* The number of iterations of the loop. */ | |
409 | rtx niter_expr; | |
410 | }; | |
411 | ||
412 | extern void iv_analysis_loop_init (struct loop *); | |
3eeb4f9a | 413 | extern bool iv_analyze (rtx_insn *, rtx, struct rtx_iv *); |
414 | extern bool iv_analyze_result (rtx_insn *, rtx, struct rtx_iv *); | |
3754d046 | 415 | extern bool iv_analyze_expr (rtx_insn *, rtx, machine_mode, |
3eeb4f9a | 416 | struct rtx_iv *); |
f9cce2dc | 417 | extern rtx get_iv_value (struct rtx_iv *, rtx); |
3eeb4f9a | 418 | extern bool biv_p (rtx_insn *, rtx); |
f9cce2dc | 419 | extern void find_simple_exit (struct loop *, struct niter_desc *); |
f9cce2dc | 420 | extern void iv_analysis_done (void); |
421 | ||
422 | extern struct niter_desc *get_simple_loop_desc (struct loop *loop); | |
423 | extern void free_simple_loop_desc (struct loop *loop); | |
424 | ||
425 | static inline struct niter_desc * | |
426 | simple_loop_desc (struct loop *loop) | |
427 | { | |
427286b3 | 428 | return loop->simple_loop_desc; |
f9cce2dc | 429 | } |
430 | ||
17519ba0 | 431 | /* Accessors for the loop structures. */ |
432 | ||
41f75a99 | 433 | /* Returns the loop with index NUM from FNs loop tree. */ |
17519ba0 | 434 | |
435 | static inline struct loop * | |
41f75a99 | 436 | get_loop (struct function *fn, unsigned num) |
17519ba0 | 437 | { |
41f75a99 | 438 | return (*loops_for_fn (fn)->larray)[num]; |
17519ba0 | 439 | } |
440 | ||
9e3536f4 | 441 | /* Returns the number of superloops of LOOP. */ |
442 | ||
443 | static inline unsigned | |
444 | loop_depth (const struct loop *loop) | |
445 | { | |
f1f41a6c | 446 | return vec_safe_length (loop->superloops); |
9e3536f4 | 447 | } |
448 | ||
449 | /* Returns the immediate superloop of LOOP, or NULL if LOOP is the outermost | |
450 | loop. */ | |
451 | ||
452 | static inline struct loop * | |
453 | loop_outer (const struct loop *loop) | |
454 | { | |
f1f41a6c | 455 | unsigned n = vec_safe_length (loop->superloops); |
9e3536f4 | 456 | |
457 | if (n == 0) | |
458 | return NULL; | |
459 | ||
f1f41a6c | 460 | return (*loop->superloops)[n - 1]; |
9e3536f4 | 461 | } |
462 | ||
a8d6ade3 | 463 | /* Returns true if LOOP has at least one exit edge. */ |
464 | ||
465 | static inline bool | |
466 | loop_has_exit_edges (const struct loop *loop) | |
467 | { | |
468 | return loop->exits->next->e != NULL; | |
469 | } | |
470 | ||
41f75a99 | 471 | /* Returns the list of loops in FN. */ |
17519ba0 | 472 | |
41f75a99 | 473 | inline vec<loop_p, va_gc> * |
474 | get_loops (struct function *fn) | |
17519ba0 | 475 | { |
41f75a99 | 476 | struct loops *loops = loops_for_fn (fn); |
477 | if (!loops) | |
17519ba0 | 478 | return NULL; |
479 | ||
41f75a99 | 480 | return loops->larray; |
17519ba0 | 481 | } |
482 | ||
41f75a99 | 483 | /* Returns the number of loops in FN (including the removed |
17519ba0 | 484 | ones and the fake loop that forms the root of the loop tree). */ |
485 | ||
486 | static inline unsigned | |
41f75a99 | 487 | number_of_loops (struct function *fn) |
17519ba0 | 488 | { |
41f75a99 | 489 | struct loops *loops = loops_for_fn (fn); |
de15b4bb | 490 | if (!loops) |
17519ba0 | 491 | return 0; |
492 | ||
41f75a99 | 493 | return vec_safe_length (loops->larray); |
17519ba0 | 494 | } |
495 | ||
f24ec26f | 496 | /* Returns true if state of the loops satisfies all properties |
497 | described by FLAGS. */ | |
498 | ||
499 | static inline bool | |
500 | loops_state_satisfies_p (unsigned flags) | |
501 | { | |
502 | return (current_loops->state & flags) == flags; | |
503 | } | |
504 | ||
505 | /* Sets FLAGS to the loops state. */ | |
506 | ||
507 | static inline void | |
508 | loops_state_set (unsigned flags) | |
509 | { | |
510 | current_loops->state |= flags; | |
511 | } | |
512 | ||
513 | /* Clears FLAGS from the loops state. */ | |
514 | ||
515 | static inline void | |
516 | loops_state_clear (unsigned flags) | |
517 | { | |
518 | if (!current_loops) | |
519 | return; | |
520 | current_loops->state &= ~flags; | |
521 | } | |
522 | ||
17519ba0 | 523 | /* Loop iterators. */ |
524 | ||
525 | /* Flags for loop iteration. */ | |
526 | ||
527 | enum li_flags | |
528 | { | |
3bbbcdff | 529 | LI_INCLUDE_ROOT = 1, /* Include the fake root of the loop tree. */ |
530 | LI_FROM_INNERMOST = 2, /* Iterate over the loops in the reverse order, | |
531 | starting from innermost ones. */ | |
532 | LI_ONLY_INNERMOST = 4 /* Iterate only over innermost loops. */ | |
17519ba0 | 533 | }; |
534 | ||
535 | /* The iterator for loops. */ | |
536 | ||
f21d4d00 | 537 | struct loop_iterator |
17519ba0 | 538 | { |
f21d4d00 | 539 | loop_iterator (loop_p *loop, unsigned flags); |
540 | ~loop_iterator (); | |
541 | ||
542 | inline loop_p next (); | |
543 | ||
3bbbcdff | 544 | /* The list of loops to visit. */ |
f1f41a6c | 545 | vec<int> to_visit; |
3bbbcdff | 546 | |
547 | /* The index of the actual loop. */ | |
548 | unsigned idx; | |
f21d4d00 | 549 | }; |
17519ba0 | 550 | |
f21d4d00 | 551 | inline loop_p |
552 | loop_iterator::next () | |
17519ba0 | 553 | { |
3bbbcdff | 554 | int anum; |
555 | ||
f21d4d00 | 556 | while (this->to_visit.iterate (this->idx, &anum)) |
17519ba0 | 557 | { |
f21d4d00 | 558 | this->idx++; |
559 | loop_p loop = get_loop (cfun, anum); | |
560 | if (loop) | |
561 | return loop; | |
17519ba0 | 562 | } |
563 | ||
f21d4d00 | 564 | return NULL; |
17519ba0 | 565 | } |
566 | ||
f21d4d00 | 567 | inline |
568 | loop_iterator::loop_iterator (loop_p *loop, unsigned flags) | |
17519ba0 | 569 | { |
3bbbcdff | 570 | struct loop *aloop; |
571 | unsigned i; | |
572 | int mn; | |
573 | ||
f21d4d00 | 574 | this->idx = 0; |
17519ba0 | 575 | if (!current_loops) |
576 | { | |
f21d4d00 | 577 | this->to_visit.create (0); |
17519ba0 | 578 | *loop = NULL; |
579 | return; | |
580 | } | |
581 | ||
f21d4d00 | 582 | this->to_visit.create (number_of_loops (cfun)); |
3bbbcdff | 583 | mn = (flags & LI_INCLUDE_ROOT) ? 0 : 1; |
584 | ||
585 | if (flags & LI_ONLY_INNERMOST) | |
586 | { | |
f1f41a6c | 587 | for (i = 0; vec_safe_iterate (current_loops->larray, i, &aloop); i++) |
3bbbcdff | 588 | if (aloop != NULL |
589 | && aloop->inner == NULL | |
590 | && aloop->num >= mn) | |
f21d4d00 | 591 | this->to_visit.quick_push (aloop->num); |
3bbbcdff | 592 | } |
593 | else if (flags & LI_FROM_INNERMOST) | |
17519ba0 | 594 | { |
3bbbcdff | 595 | /* Push the loops to LI->TO_VISIT in postorder. */ |
596 | for (aloop = current_loops->tree_root; | |
597 | aloop->inner != NULL; | |
598 | aloop = aloop->inner) | |
599 | continue; | |
600 | ||
601 | while (1) | |
602 | { | |
603 | if (aloop->num >= mn) | |
f21d4d00 | 604 | this->to_visit.quick_push (aloop->num); |
3bbbcdff | 605 | |
606 | if (aloop->next) | |
607 | { | |
608 | for (aloop = aloop->next; | |
609 | aloop->inner != NULL; | |
610 | aloop = aloop->inner) | |
611 | continue; | |
612 | } | |
9e3536f4 | 613 | else if (!loop_outer (aloop)) |
3bbbcdff | 614 | break; |
615 | else | |
9e3536f4 | 616 | aloop = loop_outer (aloop); |
3bbbcdff | 617 | } |
17519ba0 | 618 | } |
619 | else | |
620 | { | |
3bbbcdff | 621 | /* Push the loops to LI->TO_VISIT in preorder. */ |
622 | aloop = current_loops->tree_root; | |
623 | while (1) | |
624 | { | |
625 | if (aloop->num >= mn) | |
f21d4d00 | 626 | this->to_visit.quick_push (aloop->num); |
3bbbcdff | 627 | |
628 | if (aloop->inner != NULL) | |
629 | aloop = aloop->inner; | |
630 | else | |
631 | { | |
632 | while (aloop != NULL && aloop->next == NULL) | |
9e3536f4 | 633 | aloop = loop_outer (aloop); |
3bbbcdff | 634 | if (aloop == NULL) |
635 | break; | |
636 | aloop = aloop->next; | |
637 | } | |
638 | } | |
17519ba0 | 639 | } |
3bbbcdff | 640 | |
f21d4d00 | 641 | *loop = this->next (); |
17519ba0 | 642 | } |
643 | ||
f21d4d00 | 644 | inline |
645 | loop_iterator::~loop_iterator () | |
646 | { | |
647 | this->to_visit.release (); | |
648 | } | |
3bbbcdff | 649 | |
f21d4d00 | 650 | #define FOR_EACH_LOOP(LOOP, FLAGS) \ |
651 | for (loop_iterator li(&(LOOP), FLAGS); \ | |
652 | (LOOP); \ | |
653 | (LOOP) = li.next ()) | |
17519ba0 | 654 | |
dec41e98 | 655 | /* The properties of the target. */ |
e8aa5a28 | 656 | struct target_cfgloop { |
657 | /* Number of available registers. */ | |
658 | unsigned x_target_avail_regs; | |
dec41e98 | 659 | |
e8aa5a28 | 660 | /* Number of available registers that are call-clobbered. */ |
661 | unsigned x_target_clobbered_regs; | |
662 | ||
663 | /* Number of registers reserved for temporary expressions. */ | |
664 | unsigned x_target_res_regs; | |
665 | ||
666 | /* The cost for register when there still is some reserve, but we are | |
667 | approaching the number of available registers. */ | |
668 | unsigned x_target_reg_cost[2]; | |
669 | ||
670 | /* The cost for register when we need to spill. */ | |
671 | unsigned x_target_spill_cost[2]; | |
672 | }; | |
673 | ||
674 | extern struct target_cfgloop default_target_cfgloop; | |
675 | #if SWITCHABLE_TARGET | |
676 | extern struct target_cfgloop *this_target_cfgloop; | |
677 | #else | |
678 | #define this_target_cfgloop (&default_target_cfgloop) | |
679 | #endif | |
680 | ||
681 | #define target_avail_regs \ | |
682 | (this_target_cfgloop->x_target_avail_regs) | |
683 | #define target_clobbered_regs \ | |
684 | (this_target_cfgloop->x_target_clobbered_regs) | |
685 | #define target_res_regs \ | |
686 | (this_target_cfgloop->x_target_res_regs) | |
687 | #define target_reg_cost \ | |
688 | (this_target_cfgloop->x_target_reg_cost) | |
689 | #define target_spill_cost \ | |
690 | (this_target_cfgloop->x_target_spill_cost) | |
dec41e98 | 691 | |
3a0ecac2 | 692 | /* Register pressure estimation for induction variable optimizations & loop |
693 | invariant motion. */ | |
a6b74a67 | 694 | extern unsigned estimate_reg_pressure_cost (unsigned, unsigned, bool, bool); |
3a0ecac2 | 695 | extern void init_set_costs (void); |
696 | ||
6a606e3c | 697 | /* Loop optimizer initialization. */ |
88e6f696 | 698 | extern void loop_optimizer_init (unsigned); |
699 | extern void loop_optimizer_finalize (void); | |
6a606e3c | 700 | |
701 | /* Optimization passes. */ | |
ce32fe65 | 702 | enum |
703 | { | |
c836de3f | 704 | UAP_UNROLL = 1, /* Enables unrolling of loops if it seems profitable. */ |
705 | UAP_UNROLL_ALL = 2 /* Enables unrolling of all loops. */ | |
ce32fe65 | 706 | }; |
707 | ||
7194de72 | 708 | extern void doloop_optimize_loops (void); |
709 | extern void move_loop_invariants (void); | |
f1f41a6c | 710 | extern vec<basic_block> get_loop_hot_path (const struct loop *loop); |
bcf3c70d | 711 | |
7b64e7e0 | 712 | /* Returns the outermost loop of the loop nest that contains LOOP.*/ |
713 | static inline struct loop * | |
714 | loop_outermost (struct loop *loop) | |
715 | { | |
f1f41a6c | 716 | unsigned n = vec_safe_length (loop->superloops); |
7b64e7e0 | 717 | |
718 | if (n <= 1) | |
719 | return loop; | |
720 | ||
f1f41a6c | 721 | return (*loop->superloops)[1]; |
7b64e7e0 | 722 | } |
723 | ||
5de9d3ed | 724 | extern void record_niter_bound (struct loop *, const widest_int &, bool, bool); |
4e948f5a | 725 | extern HOST_WIDE_INT get_estimated_loop_iterations_int (struct loop *); |
726 | extern HOST_WIDE_INT get_max_loop_iterations_int (struct loop *); | |
5de9d3ed | 727 | extern bool get_estimated_loop_iterations (struct loop *loop, widest_int *nit); |
728 | extern bool get_max_loop_iterations (struct loop *loop, widest_int *nit); | |
424a4a92 | 729 | extern int bb_loop_depth (const_basic_block); |
7b64e7e0 | 730 | |
5de9d3ed | 731 | /* Converts VAL to widest_int. */ |
f86b328b | 732 | |
5de9d3ed | 733 | static inline widest_int |
6b409616 | 734 | gcov_type_to_wide_int (gcov_type val) |
f86b328b | 735 | { |
6b409616 | 736 | HOST_WIDE_INT a[2]; |
f86b328b | 737 | |
6b409616 | 738 | a[0] = (unsigned HOST_WIDE_INT) val; |
f86b328b | 739 | /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by |
740 | the size of type. */ | |
741 | val >>= HOST_BITS_PER_WIDE_INT - 1; | |
742 | val >>= 1; | |
6b409616 | 743 | a[1] = (unsigned HOST_WIDE_INT) val; |
f86b328b | 744 | |
5de9d3ed | 745 | return widest_int::from_array (a, 2); |
f86b328b | 746 | } |
bcf3c70d | 747 | #endif /* GCC_CFGLOOP_H */ |