X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fcfgloop.h;h=09eef08ca3de1aba309e50f074cf10b95456b7a1;hb=5e016dfc61b8e84dcbd0df9a4807394e1ca173bf;hp=d523acf001cc24ff91bba3f4221d736ba4492640;hpb=17519ba0dc05161d1dd4fba308eee373e9a9841b;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index d523acf001c..09eef08ca3d 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -25,6 +25,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #include "basic-block.h" /* For rtx_code. */ #include "rtl.h" +#include "vecprim.h" /* Structure to hold decision about unrolling/peeling. */ enum lpt_dec @@ -74,6 +75,21 @@ struct nb_iter_bound struct nb_iter_bound *next; }; +/* Description of the loop exit. */ + +struct loop_exit +{ + /* The exit edge. */ + edge e; + + /* Previous and next exit in the list of the exits of the loop. */ + struct loop_exit *prev; + struct loop_exit *next; + + /* Next element in the list of loops from that E exits. */ + struct loop_exit *next_e; +}; + /* Structure to hold information for each natural loop. */ struct loop { @@ -119,10 +135,10 @@ struct loop /* Auxiliary info specific to a pass. */ void *aux; - /* The probable number of times the loop is executed at runtime. + /* The number of times the latch of the loop is executed. This is an INTEGER_CST or an expression containing symbolic names. Don't access this field directly: - number_of_iterations_in_loop computes and caches the computed + number_of_latch_executions computes and caches the computed information in this field. */ tree nb_iterations; @@ -142,10 +158,8 @@ struct loop /* Upper bound on number of iterations of a loop. */ struct nb_iter_bound *bounds; - /* If not NULL, loop has just single exit edge stored here (edges to the - EXIT_BLOCK_PTR do not count. Do not use directly; this field should - only be accessed via single_exit/set_single_exit functions. */ - edge single_exit_; + /* Head of the cyclic list of the exits of the loop. */ + struct loop_exit exits; }; /* Flags for state of loop structure. */ @@ -154,11 +168,13 @@ enum LOOPS_HAVE_PREHEADERS = 1, LOOPS_HAVE_SIMPLE_LATCHES = 2, LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4, - LOOPS_HAVE_MARKED_SINGLE_EXITS = 8 + LOOPS_HAVE_RECORDED_EXITS = 8, + LOOPS_MAY_HAVE_MULTIPLE_LATCHES = 16 }; #define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \ | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) +#define AVOID_CFG_MODIFICATIONS (LOOPS_MAY_HAVE_MULTIPLE_LATCHES) typedef struct loop *loop_p; DEF_VEC_P (loop_p); @@ -173,31 +189,42 @@ struct loops /* Array of the loops. */ VEC (loop_p, heap) *larray; + /* Maps edges to the list of their descriptions as loop exits. Edges + whose sources or destinations have loop_father == NULL (which may + happen during the cfg manipulations) should not appear in EXITS. */ + htab_t exits; + /* Pointer to root of loop hierarchy tree. */ struct loop *tree_root; }; /* Loop recognition. */ extern int flow_loops_find (struct loops *); +extern void disambiguate_loops_with_multiple_latches (void); extern void flow_loops_free (struct loops *); extern void flow_loops_dump (FILE *, void (*)(const struct loop *, FILE *, int), int); extern void flow_loop_dump (const struct loop *, FILE *, void (*)(const struct loop *, FILE *, int), int); +struct loop *alloc_loop (void); extern void flow_loop_free (struct loop *); int flow_loop_nodes_find (basic_block, struct loop *); void fix_loop_structure (bitmap changed_bbs); void mark_irreducible_loops (void); -void mark_single_exit_loops (void); +void release_recorded_exits (void); +void record_loop_exits (void); +void rescan_loop_exit (edge, bool, bool); /* Loop data structure manipulation/querying. */ extern void flow_loop_tree_node_add (struct loop *, struct loop *); extern void flow_loop_tree_node_remove (struct loop *); +extern void add_loop (struct loop *, struct loop *); extern bool flow_loop_nested_p (const struct loop *, const struct loop *); extern bool flow_bb_inside_loop_p (const struct loop *, const basic_block); extern struct loop * find_common_loop (struct loop *, struct loop *); struct loop *superloop_at_depth (struct loop *, unsigned); -extern unsigned tree_num_loop_insns (struct loop *); +struct eni_weights_d; +extern unsigned tree_num_loop_insns (struct loop *, struct eni_weights_d *); extern int num_loop_insns (struct loop *); extern int average_num_loop_insns (struct loop *); extern unsigned get_loop_level (const struct loop *); @@ -206,11 +233,12 @@ extern void mark_loop_exit_edges (void); /* Loops & cfg manipulation. */ extern basic_block *get_loop_body (const struct loop *); +extern unsigned get_loop_body_with_size (const struct loop *, basic_block *, + unsigned); extern basic_block *get_loop_body_in_dom_order (const struct loop *); extern basic_block *get_loop_body_in_bfs_order (const struct loop *); extern VEC (edge, heap) *get_loop_exit_edges (const struct loop *); edge single_exit (const struct loop *); -void set_single_exit (struct loop *, edge); extern unsigned num_loop_branches (const struct loop *); extern edge loop_preheader_edge (const struct loop *); @@ -222,8 +250,6 @@ extern void remove_bb_from_loops (basic_block); extern void cancel_loop_tree (struct loop *); extern void delete_loop (struct loop *); -extern int fix_loop_placement (struct loop *); - enum { CP_SIMPLE_PREHEADERS = 1 @@ -251,13 +277,15 @@ extern bool can_duplicate_loop_p (struct loop *loop); extern struct loop * duplicate_loop (struct loop *, struct loop *); extern bool duplicate_loop_to_header_edge (struct loop *, edge, - unsigned, sbitmap, edge, edge *, - unsigned *, int); + unsigned, sbitmap, edge, + VEC (edge, heap) **, int); extern struct loop *loopify (edge, edge, - basic_block, edge, edge, bool); + basic_block, edge, edge, bool, + unsigned, unsigned); struct loop * loop_version (struct loop *, void *, - basic_block *, bool); + basic_block *, unsigned, unsigned, unsigned, bool); extern bool remove_path (edge); +void scale_loop_frequencies (struct loop *, int, int); /* Induction variable analysis. */ @@ -404,84 +432,127 @@ number_of_loops (void) enum li_flags { - LI_INCLUDE_ROOT, /* Include the fake root of the loop tree. */ - LI_FROM_INNERMOST, /* Iterate over the loops in the reverse order, - starting from innermost ones. */ - LI_ONLY_INNERMOST, /* Iterate only over innermost loops. */ - LI_ONLY_OLD /* Do not traverse the loops created during the - traversal (this is the default behavior with - LI_FROM_INNERMOST). */ + LI_INCLUDE_ROOT = 1, /* Include the fake root of the loop tree. */ + LI_FROM_INNERMOST = 2, /* Iterate over the loops in the reverse order, + starting from innermost ones. */ + LI_ONLY_INNERMOST = 4 /* Iterate only over innermost loops. */ }; /* The iterator for loops. */ typedef struct { - int idx; /* Index of the actual loop. */ - int end; /* Only loops before end should be traversed. */ + /* The list of loops to visit. */ + VEC(int,heap) *to_visit; + + /* The index of the actual loop. */ + unsigned idx; } loop_iterator; static inline void -fel_next (loop_iterator *li, loop_p *loop, unsigned flags) +fel_next (loop_iterator *li, loop_p *loop) { - if (flags & LI_FROM_INNERMOST) - { - li->idx--; - for (; li->idx > li->end; li->idx--) - { - *loop = VEC_index (loop_p, current_loops->larray, li->idx); - if (*loop - && (!(flags & LI_ONLY_INNERMOST) - || (*loop)->inner == NULL)) - return; - } - } - else + int anum; + + while (VEC_iterate (int, li->to_visit, li->idx, anum)) { - if (!(flags & LI_ONLY_OLD)) - li->end = number_of_loops (); li->idx++; - for (; li->idx < li->end; li->idx++) - { - *loop = VEC_index (loop_p, current_loops->larray, li->idx); - if (*loop - && (!(flags & LI_ONLY_INNERMOST) - || (*loop)->inner == NULL)) - return; - } + *loop = get_loop (anum); + if (*loop) + return; } + VEC_free (int, heap, li->to_visit); *loop = NULL; } static inline void fel_init (loop_iterator *li, loop_p *loop, unsigned flags) { + struct loop *aloop; + unsigned i; + int mn; + + li->idx = 0; if (!current_loops) { - li->idx = 0; - li->end = 0; + li->to_visit = NULL; *loop = NULL; return; } - if (flags & LI_FROM_INNERMOST) + li->to_visit = VEC_alloc (int, heap, number_of_loops ()); + mn = (flags & LI_INCLUDE_ROOT) ? 0 : 1; + + if (flags & LI_ONLY_INNERMOST) + { + for (i = 0; VEC_iterate (loop_p, current_loops->larray, i, aloop); i++) + if (aloop != NULL + && aloop->inner == NULL + && aloop->num >= mn) + VEC_quick_push (int, li->to_visit, aloop->num); + } + else if (flags & LI_FROM_INNERMOST) { - li->idx = number_of_loops (); - li->end = (flags & LI_INCLUDE_ROOT) ? -1 : 0; + /* Push the loops to LI->TO_VISIT in postorder. */ + for (aloop = current_loops->tree_root; + aloop->inner != NULL; + aloop = aloop->inner) + continue; + + while (1) + { + if (aloop->num >= mn) + VEC_quick_push (int, li->to_visit, aloop->num); + + if (aloop->next) + { + for (aloop = aloop->next; + aloop->inner != NULL; + aloop = aloop->inner) + continue; + } + else if (!aloop->outer) + break; + else + aloop = aloop->outer; + } } else { - li->idx = (flags & LI_INCLUDE_ROOT) ? -1 : 0; - li->end = number_of_loops (); + /* Push the loops to LI->TO_VISIT in preorder. */ + aloop = current_loops->tree_root; + while (1) + { + if (aloop->num >= mn) + VEC_quick_push (int, li->to_visit, aloop->num); + + if (aloop->inner != NULL) + aloop = aloop->inner; + else + { + while (aloop != NULL && aloop->next == NULL) + aloop = aloop->outer; + if (aloop == NULL) + break; + aloop = aloop->next; + } + } } - fel_next (li, loop, flags); + + fel_next (li, loop); } #define FOR_EACH_LOOP(LI, LOOP, FLAGS) \ for (fel_init (&(LI), &(LOOP), FLAGS); \ (LOOP); \ - fel_next (&(LI), &(LOOP), FLAGS)) + fel_next (&(LI), &(LOOP))) + +#define FOR_EACH_LOOP_BREAK(LI) \ + { \ + VEC_free (int, heap, (LI)->to_visit); \ + break; \ + } /* The properties of the target. */