[go: nahoru, domu]
Google Git
Sign in
android / platform / prebuilts / gcc / darwin-x86 / arm / arm-eabi-4.6 / refs/heads/l-preview / . / lib / gcc / arm-eabi / 4.6.x-google / plugin / include / cfgloop.h
blob: c6178e827649ddeaa6f6fbe479ec7087c9debd50 [file] [log] [blame]
Jing Yu21b2cba2012-04-24 14:08:37 -0700[diff] [blame]1/* Natural loop functions
2 Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004,
3 2005, 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#ifndef GCC_CFGLOOP_H
22#define GCC_CFGLOOP_H
23
24#include "basic-block.h"
25/* For rtx_code. */
26#include "rtl.h"
27#include "vecprim.h"
28#include "double-int.h"
29
30#include "bitmap.h"
31#include "sbitmap.h"
32
33/* Structure to hold decision about unrolling/peeling. */
34enum lpt_dec
35{
36 LPT_NONE,
37 LPT_PEEL_COMPLETELY,
38 LPT_PEEL_SIMPLE,
39 LPT_UNROLL_CONSTANT,
40 LPT_UNROLL_RUNTIME,
41 LPT_UNROLL_STUPID
42};
43
44struct GTY (()) lpt_decision {
45 enum lpt_dec decision;
46 unsigned times;
47};
48
49/* The structure describing a bound on number of iterations of a loop. */
50
51struct GTY ((chain_next ("%h.next"))) nb_iter_bound {
52 /* The statement STMT is executed at most ... */
53 gimple stmt;
54
55 /* ... BOUND + 1 times (BOUND must be an unsigned constant).
56 The + 1 is added for the following reasons:
57
58 a) 0 would otherwise be unused, while we would need to care more about
59 overflows (as MAX + 1 is sometimes produced as the estimate on number
60 of executions of STMT).
61 b) it is consistent with the result of number_of_iterations_exit. */
62 double_int bound;
63
64 /* True if the statement will cause the loop to be leaved the (at most)
65 BOUND + 1-st time it is executed, that is, all the statements after it
66 are executed at most BOUND times. */
67 bool is_exit;
68
69 /* The next bound in the list. */
70 struct nb_iter_bound *next;
71};
72
73/* Description of the loop exit. */
74
75struct GTY (()) loop_exit {
76 /* The exit edge. */
77 struct edge_def *e;
78
79 /* Previous and next exit in the list of the exits of the loop. */
80 struct loop_exit *prev;
81 struct loop_exit *next;
82
83 /* Next element in the list of loops from that E exits. */
84 struct loop_exit *next_e;
85};
86
87typedef struct loop *loop_p;
88DEF_VEC_P (loop_p);
89DEF_VEC_ALLOC_P (loop_p, heap);
90DEF_VEC_ALLOC_P (loop_p, gc);
91
92/* An integer estimation of the number of iterations. Estimate_state
93 describes what is the state of the estimation. */
94enum loop_estimation
95{
96 /* Estimate was not computed yet. */
97 EST_NOT_COMPUTED,
98 /* Estimate is ready. */
99 EST_AVAILABLE
100};
101
102/* Structure to hold information for each natural loop. */
103struct GTY ((chain_next ("%h.next"))) loop {
104 /* Index into loops array. */
105 int num;
106
107 /* Number of loop insns. */
108 unsigned ninsns;
109
110 /* Basic block of loop header. */
111 struct basic_block_def *header;
112
113 /* Basic block of loop latch. */
114 struct basic_block_def *latch;
115
116 /* For loop unrolling/peeling decision. */
117 struct lpt_decision lpt_decision;
118
119 /* Average number of executed insns per iteration. */
120 unsigned av_ninsns;
121
122 /* Number of blocks contained within the loop. */
123 unsigned num_nodes;
124
125 /* Superloops of the loop, starting with the outermost loop. */
126 VEC (loop_p, gc) *superloops;
127
128 /* The first inner (child) loop or NULL if innermost loop. */
129 struct loop *inner;
130
131 /* Link to the next (sibling) loop. */
132 struct loop *next;
133
134 /* Auxiliary info specific to a pass. */
135 PTR GTY ((skip (""))) aux;
136
137 /* The number of times the latch of the loop is executed. This can be an
138 INTEGER_CST, or a symbolic expression representing the number of
139 iterations like "N - 1", or a COND_EXPR containing the runtime
140 conditions under which the number of iterations is non zero.
141
142 Don't access this field directly: number_of_latch_executions
143 computes and caches the computed information in this field. */
144 tree nb_iterations;
145
146 /* An integer guaranteed to bound the number of iterations of the loop
147 from above. */
148 double_int nb_iterations_upper_bound;
149
150 /* An integer giving the expected number of iterations of the loop. */
151 double_int nb_iterations_estimate;
152
153 bool any_upper_bound;
154 bool any_estimate;
155
156 /* True if the loop can be parallel. */
157 bool can_be_parallel;
158
159 /* An integer estimation of the number of iterations. Estimate_state
160 describes what is the state of the estimation. */
161 enum loop_estimation estimate_state;
162
163 /* Upper bound on number of iterations of a loop. */
164 struct nb_iter_bound *bounds;
165
166 /* Head of the cyclic list of the exits of the loop. */
167 struct loop_exit *exits;
168};
169
170/* Flags for state of loop structure. */
171enum
172{
173 LOOPS_HAVE_PREHEADERS = 1,
174 LOOPS_HAVE_SIMPLE_LATCHES = 2,
175 LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4,
176 LOOPS_HAVE_RECORDED_EXITS = 8,
177 LOOPS_MAY_HAVE_MULTIPLE_LATCHES = 16,
178 LOOP_CLOSED_SSA = 32,
179 LOOPS_NEED_FIXUP = 64,
180 LOOPS_HAVE_FALLTHRU_PREHEADERS = 128
181};
182
183#define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \
184 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
185#define AVOID_CFG_MODIFICATIONS (LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
186
187/* Structure to hold CFG information about natural loops within a function. */
188struct GTY (()) loops {
189 /* State of loops. */
190 int state;
191
192 /* Array of the loops. */
193 VEC (loop_p, gc) *larray;
194
195 /* Maps edges to the list of their descriptions as loop exits. Edges
196 whose sources or destinations have loop_father == NULL (which may
197 happen during the cfg manipulations) should not appear in EXITS. */
198 htab_t GTY((param_is (struct loop_exit))) exits;
199
200 /* Pointer to root of loop hierarchy tree. */
201 struct loop *tree_root;
202};
203
204/* Loop recognition. */
205extern int flow_loops_find (struct loops *);
206extern void disambiguate_loops_with_multiple_latches (void);
207extern void flow_loops_free (struct loops *);
208extern void flow_loops_dump (FILE *,
209 void (*)(const struct loop *, FILE *, int), int);
210extern void flow_loop_dump (const struct loop *, FILE *,
211 void (*)(const struct loop *, FILE *, int), int);
212struct loop *alloc_loop (void);
213extern void flow_loop_free (struct loop *);
214int flow_loop_nodes_find (basic_block, struct loop *);
215void fix_loop_structure (bitmap changed_bbs);
216bool mark_irreducible_loops (void);
217void release_recorded_exits (void);
218void record_loop_exits (void);
219void rescan_loop_exit (edge, bool, bool);
220
221/* Loop data structure manipulation/querying. */
222extern void flow_loop_tree_node_add (struct loop *, struct loop *);
223extern void flow_loop_tree_node_remove (struct loop *);
224extern void add_loop (struct loop *, struct loop *);
225extern bool flow_loop_nested_p (const struct loop *, const struct loop *);
226extern bool flow_bb_inside_loop_p (const struct loop *, const_basic_block);
227extern struct loop * find_common_loop (struct loop *, struct loop *);
228struct loop *superloop_at_depth (struct loop *, unsigned);
229struct eni_weights_d;
230extern unsigned tree_num_loop_insns (struct loop *, struct eni_weights_d *);
231extern int num_loop_insns (const struct loop *);
232extern int average_num_loop_insns (const struct loop *);
233extern unsigned get_loop_level (const struct loop *);
234extern bool loop_exit_edge_p (const struct loop *, const_edge);
235extern bool loop_exits_to_bb_p (struct loop *, basic_block);
236extern bool loop_exits_from_bb_p (struct loop *, basic_block);
237extern void mark_loop_exit_edges (void);
238extern location_t get_loop_location (struct loop *loop);
239
240/* Loops & cfg manipulation. */
241extern basic_block *get_loop_body (const struct loop *);
242extern unsigned get_loop_body_with_size (const struct loop *, basic_block *,
243 unsigned);
244extern basic_block *get_loop_body_in_dom_order (const struct loop *);
245extern basic_block *get_loop_body_in_bfs_order (const struct loop *);
246extern basic_block *get_loop_body_in_custom_order (const struct loop *,
247 int (*) (const void *, const void *));
248
249extern VEC (edge, heap) *get_loop_exit_edges (const struct loop *);
250edge single_exit (const struct loop *);
251extern unsigned num_loop_branches (const struct loop *);
252
253extern edge loop_preheader_edge (const struct loop *);
254extern edge loop_latch_edge (const struct loop *);
255
256extern void add_bb_to_loop (basic_block, struct loop *);
257extern void remove_bb_from_loops (basic_block);
258
259extern void cancel_loop_tree (struct loop *);
260extern void delete_loop (struct loop *);
261
262enum
263{
264 CP_SIMPLE_PREHEADERS = 1,
265 CP_FALLTHRU_PREHEADERS = 2
266};
267
268basic_block create_preheader (struct loop *, int);
269extern void create_preheaders (int);
270extern void force_single_succ_latches (void);
271
272extern void verify_loop_structure (void);
273
274/* Loop analysis. */
275extern bool just_once_each_iteration_p (const struct loop *, const_basic_block);
276gcov_type expected_loop_iterations_unbounded (const struct loop *);
277extern unsigned expected_loop_iterations (const struct loop *);
278extern rtx doloop_condition_get (rtx);
279
280void estimate_numbers_of_iterations_loop (struct loop *, bool);
281HOST_WIDE_INT estimated_loop_iterations_int (struct loop *, bool);
282bool estimated_loop_iterations (struct loop *, bool, double_int *);
283
284/* Loop manipulation. */
285extern bool can_duplicate_loop_p (const struct loop *loop);
286
287#define DLTHE_FLAG_UPDATE_FREQ 1 /* Update frequencies in
288 duplicate_loop_to_header_edge. */
289#define DLTHE_RECORD_COPY_NUMBER 2 /* Record copy number in the aux
290 field of newly create BB. */
291#define DLTHE_FLAG_COMPLETTE_PEEL 4 /* Update frequencies expecting
292 a complete peeling. */
293
294extern edge create_empty_if_region_on_edge (edge, tree);
295extern struct loop *create_empty_loop_on_edge (edge, tree, tree, tree, tree,
296 tree *, tree *, struct loop *);
297extern struct loop * duplicate_loop (struct loop *, struct loop *);
298extern void duplicate_subloops (struct loop *, struct loop *);
299extern bool duplicate_loop_to_header_edge (struct loop *, edge,
300 unsigned, sbitmap, edge,
301 VEC (edge, heap) **, int);
302extern struct loop *loopify (edge, edge,
303 basic_block, edge, edge, bool,
304 unsigned, unsigned);
305struct loop * loop_version (struct loop *, void *,
306 basic_block *, unsigned, unsigned, unsigned, bool);
307extern bool remove_path (edge);
308void scale_loop_frequencies (struct loop *, int, int);
309
310/* Induction variable analysis. */
311
312/* The description of induction variable. The things are a bit complicated
313 due to need to handle subregs and extends. The value of the object described
314 by it can be obtained as follows (all computations are done in extend_mode):
315
316 Value in i-th iteration is
317 delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)).
318
319 If first_special is true, the value in the first iteration is
320 delta + mult * base
321
322 If extend = UNKNOWN, first_special must be false, delta 0, mult 1 and value is
323 subreg_{mode} (base + i * step)
324
325 The get_iv_value function can be used to obtain these expressions.
326
327 ??? Add a third mode field that would specify the mode in that inner
328 computation is done, which would enable it to be different from the
329 outer one? */
330
331struct rtx_iv
332{
333 /* Its base and step (mode of base and step is supposed to be extend_mode,
334 see the description above). */
335 rtx base, step;
336
337 /* The type of extend applied to it (SIGN_EXTEND, ZERO_EXTEND or UNKNOWN). */
338 enum rtx_code extend;
339
340 /* Operations applied in the extended mode. */
341 rtx delta, mult;
342
343 /* The mode it is extended to. */
344 enum machine_mode extend_mode;
345
346 /* The mode the variable iterates in. */
347 enum machine_mode mode;
348
349 /* Whether the first iteration needs to be handled specially. */
350 unsigned first_special : 1;
351};
352
353/* The description of an exit from the loop and of the number of iterations
354 till we take the exit. */
355
356struct niter_desc
357{
358 /* The edge out of the loop. */
359 edge out_edge;
360
361 /* The other edge leading from the condition. */
362 edge in_edge;
363
364 /* True if we are able to say anything about number of iterations of the
365 loop. */
366 bool simple_p;
367
368 /* True if the loop iterates the constant number of times. */
369 bool const_iter;
370
371 /* Number of iterations if constant. */
372 unsigned HOST_WIDEST_INT niter;
373
374 /* Upper bound on the number of iterations. */
375 unsigned HOST_WIDEST_INT niter_max;
376
377 /* Assumptions under that the rest of the information is valid. */
378 rtx assumptions;
379
380 /* Assumptions under that the loop ends before reaching the latch,
381 even if value of niter_expr says otherwise. */
382 rtx noloop_assumptions;
383
384 /* Condition under that the loop is infinite. */
385 rtx infinite;
386
387 /* Whether the comparison is signed. */
388 bool signed_p;
389
390 /* The mode in that niter_expr should be computed. */
391 enum machine_mode mode;
392
393 /* The number of iterations of the loop. */
394 rtx niter_expr;
395};
396
397extern void iv_analysis_loop_init (struct loop *);
398extern bool iv_analyze (rtx, rtx, struct rtx_iv *);
399extern bool iv_analyze_result (rtx, rtx, struct rtx_iv *);
400extern bool iv_analyze_expr (rtx, rtx, enum machine_mode, struct rtx_iv *);
401extern rtx get_iv_value (struct rtx_iv *, rtx);
402extern bool biv_p (rtx, rtx);
403extern void find_simple_exit (struct loop *, struct niter_desc *);
404extern void iv_analysis_done (void);
405
406extern struct niter_desc *get_simple_loop_desc (struct loop *loop);
407extern void free_simple_loop_desc (struct loop *loop);
408
409static inline struct niter_desc *
410simple_loop_desc (struct loop *loop)
411{
412 return (struct niter_desc *) loop->aux;
413}
414
415/* Accessors for the loop structures. */
416
417/* Returns the loop with index NUM from current_loops. */
418
419static inline struct loop *
420get_loop (unsigned num)
421{
422 return VEC_index (loop_p, current_loops->larray, num);
423}
424
425/* Returns the number of superloops of LOOP. */
426
427static inline unsigned
428loop_depth (const struct loop *loop)
429{
430 return VEC_length (loop_p, loop->superloops);
431}
432
433/* Returns the immediate superloop of LOOP, or NULL if LOOP is the outermost
434 loop. */
435
436static inline struct loop *
437loop_outer (const struct loop *loop)
438{
439 unsigned n = VEC_length (loop_p, loop->superloops);
440
441 if (n == 0)
442 return NULL;
443
444 return VEC_index (loop_p, loop->superloops, n - 1);
445}
446
447/* Returns true if LOOP has at least one exit edge. */
448
449static inline bool
450loop_has_exit_edges (const struct loop *loop)
451{
452 return loop->exits->next->e != NULL;
453}
454
455/* Returns the list of loops in current_loops. */
456
457static inline VEC (loop_p, gc) *
458get_loops (void)
459{
460 if (!current_loops)
461 return NULL;
462
463 return current_loops->larray;
464}
465
466/* Returns the number of loops in current_loops (including the removed
467 ones and the fake loop that forms the root of the loop tree). */
468
469static inline unsigned
470number_of_loops (void)
471{
472 if (!current_loops)
473 return 0;
474
475 return VEC_length (loop_p, current_loops->larray);
476}
477
478/* Returns true if state of the loops satisfies all properties
479 described by FLAGS. */
480
481static inline bool
482loops_state_satisfies_p (unsigned flags)
483{
484 return (current_loops->state & flags) == flags;
485}
486
487/* Sets FLAGS to the loops state. */
488
489static inline void
490loops_state_set (unsigned flags)
491{
492 current_loops->state |= flags;
493}
494
495/* Clears FLAGS from the loops state. */
496
497static inline void
498loops_state_clear (unsigned flags)
499{
500 if (!current_loops)
501 return;
502 current_loops->state &= ~flags;
503}
504
505/* Loop iterators. */
506
507/* Flags for loop iteration. */
508
509enum li_flags
510{
511 LI_INCLUDE_ROOT = 1, /* Include the fake root of the loop tree. */
512 LI_FROM_INNERMOST = 2, /* Iterate over the loops in the reverse order,
513 starting from innermost ones. */
514 LI_ONLY_INNERMOST = 4 /* Iterate only over innermost loops. */
515};
516
517/* The iterator for loops. */
518
519typedef struct
520{
521 /* The list of loops to visit. */
522 VEC(int,heap) *to_visit;
523
524 /* The index of the actual loop. */
525 unsigned idx;
526} loop_iterator;
527
528static inline void
529fel_next (loop_iterator *li, loop_p *loop)
530{
531 int anum;
532
533 while (VEC_iterate (int, li->to_visit, li->idx, anum))
534 {
535 li->idx++;
536 *loop = get_loop (anum);
537 if (*loop)
538 return;
539 }
540
541 VEC_free (int, heap, li->to_visit);
542 *loop = NULL;
543}
544
545static inline void
546fel_init (loop_iterator *li, loop_p *loop, unsigned flags)
547{
548 struct loop *aloop;
549 unsigned i;
550 int mn;
551
552 li->idx = 0;
553 if (!current_loops)
554 {
555 li->to_visit = NULL;
556 *loop = NULL;
557 return;
558 }
559
560 li->to_visit = VEC_alloc (int, heap, number_of_loops ());
561 mn = (flags & LI_INCLUDE_ROOT) ? 0 : 1;
562
563 if (flags & LI_ONLY_INNERMOST)
564 {
565 for (i = 0; VEC_iterate (loop_p, current_loops->larray, i, aloop); i++)
566 if (aloop != NULL
567 && aloop->inner == NULL
568 && aloop->num >= mn)
569 VEC_quick_push (int, li->to_visit, aloop->num);
570 }
571 else if (flags & LI_FROM_INNERMOST)
572 {
573 /* Push the loops to LI->TO_VISIT in postorder. */
574 for (aloop = current_loops->tree_root;
575 aloop->inner != NULL;
576 aloop = aloop->inner)
577 continue;
578
579 while (1)
580 {
581 if (aloop->num >= mn)
582 VEC_quick_push (int, li->to_visit, aloop->num);
583
584 if (aloop->next)
585 {
586 for (aloop = aloop->next;
587 aloop->inner != NULL;
588 aloop = aloop->inner)
589 continue;
590 }
591 else if (!loop_outer (aloop))
592 break;
593 else
594 aloop = loop_outer (aloop);
595 }
596 }
597 else
598 {
599 /* Push the loops to LI->TO_VISIT in preorder. */
600 aloop = current_loops->tree_root;
601 while (1)
602 {
603 if (aloop->num >= mn)
604 VEC_quick_push (int, li->to_visit, aloop->num);
605
606 if (aloop->inner != NULL)
607 aloop = aloop->inner;
608 else
609 {
610 while (aloop != NULL && aloop->next == NULL)
611 aloop = loop_outer (aloop);
612 if (aloop == NULL)
613 break;
614 aloop = aloop->next;
615 }
616 }
617 }
618
619 fel_next (li, loop);
620}
621
622#define FOR_EACH_LOOP(LI, LOOP, FLAGS) \
623 for (fel_init (&(LI), &(LOOP), FLAGS); \
624 (LOOP); \
625 fel_next (&(LI), &(LOOP)))
626
627#define FOR_EACH_LOOP_BREAK(LI) \
628 { \
629 VEC_free (int, heap, (LI)->to_visit); \
630 break; \
631 }
632
633/* The properties of the target. */
634struct target_cfgloop {
635 /* Number of available registers. */
636 unsigned x_target_avail_regs;
637
638 /* Number of available registers that are call-clobbered. */
639 unsigned x_target_clobbered_regs;
640
641 /* Number of registers reserved for temporary expressions. */
642 unsigned x_target_res_regs;
643
644 /* The cost for register when there still is some reserve, but we are
645 approaching the number of available registers. */
646 unsigned x_target_reg_cost[2];
647
648 /* The cost for register when we need to spill. */
649 unsigned x_target_spill_cost[2];
650};
651
652extern struct target_cfgloop default_target_cfgloop;
653#if SWITCHABLE_TARGET
654extern struct target_cfgloop *this_target_cfgloop;
655#else
656#define this_target_cfgloop (&default_target_cfgloop)
657#endif
658
659#define target_avail_regs \
660 (this_target_cfgloop->x_target_avail_regs)
661#define target_clobbered_regs \
662 (this_target_cfgloop->x_target_clobbered_regs)
663#define target_res_regs \
664 (this_target_cfgloop->x_target_res_regs)
665#define target_reg_cost \
666 (this_target_cfgloop->x_target_reg_cost)
667#define target_spill_cost \
668 (this_target_cfgloop->x_target_spill_cost)
669
670/* Register pressure estimation for induction variable optimizations & loop
671 invariant motion. */
672extern unsigned estimate_reg_pressure_cost (unsigned, unsigned, bool, bool);
673extern void init_set_costs (void);
674
675/* Loop optimizer initialization. */
676extern void loop_optimizer_init (unsigned);
677extern void loop_optimizer_finalize (void);
678
679/* Optimization passes. */
680extern void unswitch_loops (void);
681
682enum
683{
684 UAP_PEEL = 1, /* Enables loop peeling. */
685 UAP_UNROLL = 2, /* Enables unrolling of loops if it seems profitable. */
686 UAP_UNROLL_ALL = 4 /* Enables unrolling of all loops. */
687};
688
689extern void unroll_and_peel_loops (int);
690extern void doloop_optimize_loops (void);
691extern void move_loop_invariants (void);
692extern bool finite_loop_p (struct loop *);
693
694#endif /* GCC_CFGLOOP_H */