/* Natural loop functions
- Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
- Free Software Foundation, Inc.
+ Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004,
+ 2005, 2006, 2007Free Software Foundation, Inc.
This file is part of GCC.
#include "basic-block.h"
/* For rtx_code. */
#include "rtl.h"
+#include "vecprim.h"
+#include "double-int.h"
/* Structure to hold decision about unrolling/peeling. */
enum lpt_dec
LPT_UNROLL_STUPID
};
-struct lpt_decision
+struct lpt_decision GTY (())
{
enum lpt_dec decision;
unsigned times;
/* The structure describing a bound on number of iterations of a loop. */
-struct nb_iter_bound
+struct nb_iter_bound GTY ((chain_next ("%h.next")))
{
- tree bound; /* The expression whose value is an upper bound on the
- number of executions of anything after ... */
- tree at_stmt; /* ... this statement during one execution of loop. */
- tree additional; /* A conjunction of conditions the operands of BOUND
- satisfy. The additional information about the value
- of the bound may be derived from it. */
+ /* The statement STMT is executed at most ... */
+ tree stmt;
+
+ /* ... BOUND + 1 times (BOUND must be an unsigned constant).
+ The + 1 is added for the following reasons:
+
+ a) 0 would otherwise be unused, while we would need to care more about
+ overflows (as MAX + 1 is sometimes produced as the estimate on number
+ of executions of STMT).
+ b) it is consistent with the result of number_of_iterations_exit. */
+ double_int bound;
+
+ /* True if the statement will cause the loop to be leaved the (at most)
+ BOUND + 1-st time it is executed, that is, all the statements after it
+ are executed at most BOUND times. */
+ bool is_exit;
+
+ /* The next bound in the list. */
struct nb_iter_bound *next;
- /* The next bound in a list. */
+};
+
+/* Description of the loop exit. */
+
+struct loop_exit GTY (())
+{
+ /* The exit edge. */
+ struct edge_def *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;
+};
+
+typedef struct loop *loop_p;
+DEF_VEC_P (loop_p);
+DEF_VEC_ALLOC_P (loop_p, heap);
+DEF_VEC_ALLOC_P (loop_p, gc);
+
+/* An integer estimation of the number of iterations. Estimate_state
+ describes what is the state of the estimation. */
+enum loop_estimation
+{
+ /* Estimate was not computed yet. */
+ EST_NOT_COMPUTED,
+ /* Estimate is ready. */
+ EST_AVAILABLE
};
/* Structure to hold information for each natural loop. */
-struct loop
+struct loop GTY ((chain_next ("%h.next")))
{
/* Index into loops array. */
int num;
/* Basic block of loop header. */
- basic_block header;
+ struct basic_block_def *header;
/* Basic block of loop latch. */
- basic_block latch;
+ struct basic_block_def *latch;
/* For loop unrolling/peeling decision. */
struct lpt_decision lpt_decision;
/* Number of blocks contained within the loop. */
unsigned num_nodes;
- /* The loop nesting depth. */
- int depth;
-
- /* Superloops of the loop. */
- struct loop **pred;
-
- /* The height of the loop (enclosed loop levels) within the loop
- hierarchy tree. */
- int level;
-
- /* The outer (parent) loop or NULL if outermost loop. */
- struct loop *outer;
+ /* Superloops of the loop, starting with the outermost loop. */
+ VEC (loop_p, gc) *superloops;
/* The first inner (child) loop or NULL if innermost loop. */
struct loop *inner;
/* Link to the next (sibling) loop. */
struct loop *next;
- /* Loop that is copy of this loop. */
- struct loop *copy;
-
/* Auxiliary info specific to a pass. */
- void *aux;
+ PTR GTY ((skip (""))) 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;
- /* An INTEGER_CST estimation of the number of iterations. NULL_TREE
- if there is no estimation. */
- tree estimated_nb_iterations;
+ /* An integer estimation of the number of iterations. Estimate_state
+ describes what is the state of the estimation. */
+ enum loop_estimation estimate_state;
+
+ /* An integer guaranteed to bound the number of iterations of the loop
+ from above. */
+ bool any_upper_bound;
+ double_int nb_iterations_upper_bound;
+
+ /* An integer giving the expected number of iterations of the loop. */
+ bool any_estimate;
+ double_int nb_iterations_estimate;
/* 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. */
- edge single_exit;
-
- /* True when the loop does not carry data dependences, and
- consequently the iterations can be executed in any order. False
- when the loop carries data dependences, or when the property is
- not decidable. */
- bool parallel_p;
+ /* 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,
+ LOOP_CLOSED_SSA = 32
};
#define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \
| LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
+#define AVOID_CFG_MODIFICATIONS (LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
/* Structure to hold CFG information about natural loops within a function. */
-struct loops
+struct loops GTY (())
{
- /* Number of natural loops in the function. */
- unsigned num;
-
/* State of loops. */
int state;
- /* We store just pointers to loops here.
- Note that a loop in this array may actually be NULL, if the loop
- has been removed and the entire loops structure has not been
- recomputed since that time. */
- struct loop **parray;
+ /* Array of the loops. */
+ VEC (loop_p, gc) *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 GTY((param_is (struct loop_exit))) exits;
/* Pointer to root of loop hierarchy tree. */
struct loop *tree_root;
-
- /* Information derived from the CFG. */
- struct cfg
- {
- /* The ordering of the basic blocks in a depth first search. */
- int *dfs_order;
-
- /* The reverse completion ordering of the basic blocks found in a
- depth first search. */
- int *rc_order;
- } cfg;
-
- /* Headers shared by multiple loops that should be merged. */
- sbitmap shared_headers;
};
-/* The loop tree currently optimized. */
-
-extern struct loops *current_loops;
-
/* 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 (const struct loops *, FILE *,
+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 (struct loops *, bitmap changed_bbs);
-void mark_irreducible_loops (struct loops *);
-void mark_single_exit_loops (struct loops *);
+void fix_loop_structure (bitmap changed_bbs);
+void mark_irreducible_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 *);
extern bool loop_exit_edge_p (const struct loop *, edge);
-extern void mark_loop_exit_edges (struct loops *);
+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 edge *get_loop_exit_edges (const struct loop *, unsigned *);
+extern VEC (edge, heap) *get_loop_exit_edges (const struct loop *);
+edge single_exit (const struct loop *);
extern unsigned num_loop_branches (const struct loop *);
extern edge loop_preheader_edge (const struct loop *);
extern void add_bb_to_loop (basic_block, struct loop *);
extern void remove_bb_from_loops (basic_block);
-extern void cancel_loop_tree (struct loops *, struct loop *);
-
-extern basic_block loop_split_edge_with (edge, rtx);
-extern int fix_loop_placement (struct loop *);
+extern void cancel_loop_tree (struct loop *);
+extern void delete_loop (struct loop *);
enum
{
CP_SIMPLE_PREHEADERS = 1
};
-extern void create_preheaders (struct loops *, int);
-extern void force_single_succ_latches (struct loops *);
+basic_block create_preheader (struct loop *, int);
+extern void create_preheaders (int);
+extern void force_single_succ_latches (void);
-extern void verify_loop_structure (struct loops *);
+extern void verify_loop_structure (void);
/* Loop analysis. */
extern bool just_once_each_iteration_p (const struct loop *, basic_block);
+gcov_type expected_loop_iterations_unbounded (const struct loop *);
extern unsigned expected_loop_iterations (const struct loop *);
extern rtx doloop_condition_get (rtx);
+void estimate_numbers_of_iterations_loop (struct loop *);
+HOST_WIDE_INT estimated_loop_iterations_int (struct loop *, bool);
+bool estimated_loop_iterations (struct loop *, bool, double_int *);
+
/* Loop manipulation. */
extern bool can_duplicate_loop_p (struct loop *loop);
#define DLTHE_FLAG_COMPLETTE_PEEL 4 /* Update frequencies expecting
a complete peeling. */
-extern struct loop * duplicate_loop (struct loops *, struct loop *,
- struct loop *);
-extern bool duplicate_loop_to_header_edge (struct loop *, edge, struct loops *,
- unsigned, sbitmap, edge, edge *,
- unsigned *, int);
-extern struct loop *loopify (struct loops *, edge, edge,
- basic_block, edge, edge, bool);
-struct loop * loop_version (struct loops *, struct loop *, void *,
- basic_block *, bool);
-extern bool remove_path (struct loops *, edge);
+extern struct loop * duplicate_loop (struct loop *, struct loop *);
+extern bool duplicate_loop_to_header_edge (struct loop *, edge,
+ unsigned, sbitmap, edge,
+ VEC (edge, heap) **, int);
+extern struct loop *loopify (edge, edge,
+ basic_block, edge, edge, bool,
+ unsigned, unsigned);
+struct loop * loop_version (struct loop *, void *,
+ basic_block *, unsigned, unsigned, unsigned, bool);
+extern bool remove_path (edge);
+void scale_loop_frequencies (struct loop *, int, int);
/* Induction variable analysis. */
If first_special is true, the value in the first iteration is
delta + mult * base
-
+
If extend = UNKNOWN, first_special must be false, delta 0, mult 1 and value is
subreg_{mode} (base + i * step)
extern bool biv_p (rtx, rtx);
extern void find_simple_exit (struct loop *, struct niter_desc *);
extern void iv_analysis_done (void);
-extern struct df *iv_current_loop_df (void);
extern struct niter_desc *get_simple_loop_desc (struct loop *loop);
extern void free_simple_loop_desc (struct loop *loop);
return (struct niter_desc *) loop->aux;
}
+/* Accessors for the loop structures. */
+
+/* Returns the loop with index NUM from current_loops. */
+
+static inline struct loop *
+get_loop (unsigned num)
+{
+ return VEC_index (loop_p, current_loops->larray, num);
+}
+
+/* Returns the number of superloops of LOOP. */
+
+static inline unsigned
+loop_depth (const struct loop *loop)
+{
+ return VEC_length (loop_p, loop->superloops);
+}
+
+/* Returns the immediate superloop of LOOP, or NULL if LOOP is the outermost
+ loop. */
+
+static inline struct loop *
+loop_outer (const struct loop *loop)
+{
+ unsigned n = VEC_length (loop_p, loop->superloops);
+
+ if (n == 0)
+ return NULL;
+
+ return VEC_index (loop_p, loop->superloops, n - 1);
+}
+
+/* Returns the list of loops in current_loops. */
+
+static inline VEC (loop_p, gc) *
+get_loops (void)
+{
+ if (!current_loops)
+ return NULL;
+
+ return current_loops->larray;
+}
+
+/* Returns the number of loops in current_loops (including the removed
+ ones and the fake loop that forms the root of the loop tree). */
+
+static inline unsigned
+number_of_loops (void)
+{
+ if (!current_loops)
+ return 0;
+
+ return VEC_length (loop_p, current_loops->larray);
+}
+
+/* Loop iterators. */
+
+/* Flags for loop iteration. */
+
+enum li_flags
+{
+ 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
+{
+ /* 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)
+{
+ int anum;
+
+ while (VEC_iterate (int, li->to_visit, li->idx, anum))
+ {
+ li->idx++;
+ *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->to_visit = NULL;
+ *loop = NULL;
+ return;
+ }
+
+ 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)
+ {
+ /* 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 (!loop_outer (aloop))
+ break;
+ else
+ aloop = loop_outer (aloop);
+ }
+ }
+ else
+ {
+ /* 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 = loop_outer (aloop);
+ if (aloop == NULL)
+ break;
+ aloop = aloop->next;
+ }
+ }
+ }
+
+ fel_next (li, loop);
+}
+
+#define FOR_EACH_LOOP(LI, LOOP, FLAGS) \
+ for (fel_init (&(LI), &(LOOP), FLAGS); \
+ (LOOP); \
+ fel_next (&(LI), &(LOOP)))
+
+#define FOR_EACH_LOOP_BREAK(LI) \
+ { \
+ VEC_free (int, heap, (LI)->to_visit); \
+ break; \
+ }
+
/* The properties of the target. */
-extern unsigned target_avail_regs; /* Number of available registers. */
-extern unsigned target_res_regs; /* Number of reserved registers. */
-extern unsigned target_small_cost; /* The cost for register when there
- is a free one. */
-extern unsigned target_pres_cost; /* The cost for register when there are
- not too many free ones. */
-extern unsigned target_spill_cost; /* The cost for register when we need
- to spill. */
+extern unsigned target_avail_regs;
+extern unsigned target_res_regs;
+extern unsigned target_reg_cost;
+extern unsigned target_spill_cost;
/* Register pressure estimation for induction variable optimizations & loop
invariant motion. */
-extern unsigned global_cost_for_size (unsigned, unsigned, unsigned);
+extern unsigned estimate_reg_pressure_cost (unsigned, unsigned);
extern void init_set_costs (void);
/* Loop optimizer initialization. */
-extern struct loops *loop_optimizer_init (unsigned);
-extern void loop_optimizer_finalize (struct loops *);
+extern void loop_optimizer_init (unsigned);
+extern void loop_optimizer_finalize (void);
/* Optimization passes. */
-extern void unswitch_loops (struct loops *);
+extern void unswitch_loops (void);
enum
{
UAP_PEEL = 1, /* Enables loop peeling. */
- UAP_UNROLL = 2, /* Enables peeling of loops if it seems profitable. */
- UAP_UNROLL_ALL = 4 /* Enables peeling of all loops. */
+ UAP_UNROLL = 2, /* Enables unrolling of loops if it seems profitable. */
+ UAP_UNROLL_ALL = 4 /* Enables unrolling of all loops. */
};
-extern void unroll_and_peel_loops (struct loops *, int);
-extern void doloop_optimize_loops (struct loops *);
-extern void move_loop_invariants (struct loops *);
-extern void record_estimate (struct loop *, tree, tree, tree);
+extern void unroll_and_peel_loops (int);
+extern void doloop_optimize_loops (void);
+extern void move_loop_invariants (void);
#endif /* GCC_CFGLOOP_H */