#include "basic-block.h"
/* For rtx_code. */
#include "rtl.h"
+#include "vecprim.h"
/* Structure to hold decision about unrolling/peeling. */
enum lpt_dec
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
{
/* 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;
/* 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. */
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);
/* 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 *);
/* 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 *);
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
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. */
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. */
OSDN Git Service
