/* Natural loop functions
Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004,
- 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
+ 2005, 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
This file is part of GCC.
#include "vecprim.h"
#include "double-int.h"
+#include "bitmap.h"
+#include "sbitmap.h"
+
/* Structure to hold decision about unrolling/peeling. */
enum lpt_dec
{
LPT_UNROLL_STUPID
};
-struct lpt_decision GTY (())
-{
+struct GTY (()) lpt_decision {
enum lpt_dec decision;
unsigned times;
};
/* The structure describing a bound on number of iterations of a loop. */
-struct nb_iter_bound GTY ((chain_next ("%h.next")))
-{
+struct GTY ((chain_next ("%h.next"))) nb_iter_bound {
/* The statement STMT is executed at most ... */
gimple 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)
+ /* 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;
/* Description of the loop exit. */
-struct loop_exit GTY (())
-{
+struct GTY (()) loop_exit {
/* The exit edge. */
struct edge_def *e;
};
/* Structure to hold information for each natural loop. */
-struct loop GTY ((chain_next ("%h.next")))
-{
+struct GTY ((chain_next ("%h.next"))) loop {
/* Index into loops array. */
int num;
+ /* Number of loop insns. */
+ unsigned ninsns;
+
/* Basic block of loop header. */
struct basic_block_def *header;
/* For loop unrolling/peeling decision. */
struct lpt_decision lpt_decision;
- /* Number of loop insns. */
- unsigned ninsns;
-
/* Average number of executed insns per iteration. */
unsigned av_ninsns;
/* Auxiliary info specific to a pass. */
PTR GTY ((skip (""))) aux;
- /* 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_latch_executions computes and caches the computed
- information in this field. */
- tree nb_iterations;
+ /* The number of times the latch of the loop is executed. This can be an
+ INTEGER_CST, or a symbolic expression representing the number of
+ iterations like "N - 1", or a COND_EXPR containing the runtime
+ conditions under which the number of iterations is non zero.
- /* An integer estimation of the number of iterations. Estimate_state
- describes what is the state of the estimation. */
- enum loop_estimation estimate_state;
+ Don't access this field directly: number_of_latch_executions
+ computes and caches the computed information in this field. */
+ tree nb_iterations;
- /* An integer guaranteed to bound the number of iterations of the loop
- from above. */
- bool any_upper_bound;
+ /* An integer guaranteed to be greater or equal to nb_iterations. Only
+ valid if any_upper_bound is true. */
double_int nb_iterations_upper_bound;
- /* An integer giving the expected number of iterations of the loop. */
- bool any_estimate;
+ /* An integer giving an estimate on nb_iterations. Unlike
+ nb_iterations_upper_bound, there is no guarantee that it is at least
+ nb_iterations. */
double_int nb_iterations_estimate;
+ bool any_upper_bound;
+ bool any_estimate;
+
+ /* True if the loop can be parallel. */
+ bool can_be_parallel;
+
+ /* An integer estimation of the number of iterations. Estimate_state
+ describes what is the state of the estimation. */
+ enum loop_estimation estimate_state;
+
/* Upper bound on number of iterations of a loop. */
struct nb_iter_bound *bounds;
#define AVOID_CFG_MODIFICATIONS (LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
/* Structure to hold CFG information about natural loops within a function. */
-struct loops GTY (())
-{
+struct GTY (()) loops {
/* State of loops. */
int state;
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);
+bool mark_irreducible_loops (void);
void release_recorded_exits (void);
void record_loop_exits (void);
void rescan_loop_exit (edge, bool, bool);
extern int average_num_loop_insns (const struct loop *);
extern unsigned get_loop_level (const struct loop *);
extern bool loop_exit_edge_p (const struct loop *, const_edge);
-extern bool is_loop_exit (struct loop *, basic_block);
+extern bool loop_exits_to_bb_p (struct loop *, basic_block);
+extern bool loop_exits_from_bb_p (struct loop *, basic_block);
extern void mark_loop_exit_edges (void);
/* Loops & cfg manipulation. */
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 basic_block *get_loop_body_in_custom_order (const struct loop *,
+extern basic_block *get_loop_body_in_custom_order (const struct loop *,
int (*) (const void *, const void *));
extern VEC (edge, heap) *get_loop_exit_edges (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 *);
+void estimate_numbers_of_iterations_loop (struct loop *, bool);
HOST_WIDE_INT estimated_loop_iterations_int (struct loop *, bool);
+HOST_WIDE_INT max_stmt_executions_int (struct loop *, bool);
bool estimated_loop_iterations (struct loop *, bool, double_int *);
+bool max_stmt_executions (struct loop *, bool, double_int *);
/* Loop manipulation. */
extern bool can_duplicate_loop_p (const struct loop *loop);
extern edge create_empty_if_region_on_edge (edge, tree);
extern struct loop *create_empty_loop_on_edge (edge, tree, tree, tree, tree,
- tree *, struct loop *);
+ tree *, tree *, struct loop *);
extern struct loop * duplicate_loop (struct loop *, struct loop *);
-extern bool duplicate_loop_to_header_edge (struct loop *, edge,
+extern void duplicate_subloops (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,
return VEC_index (loop_p, loop->superloops, n - 1);
}
+/* Returns true if LOOP has at least one exit edge. */
+
+static inline bool
+loop_has_exit_edges (const struct loop *loop)
+{
+ return loop->exits->next->e != NULL;
+}
+
/* Returns the list of loops in current_loops. */
static inline VEC (loop_p, gc) *
}
/* The properties of the target. */
+struct target_cfgloop {
+ /* Number of available registers. */
+ unsigned x_target_avail_regs;
+
+ /* Number of available registers that are call-clobbered. */
+ unsigned x_target_clobbered_regs;
+
+ /* Number of registers reserved for temporary expressions. */
+ unsigned x_target_res_regs;
+
+ /* The cost for register when there still is some reserve, but we are
+ approaching the number of available registers. */
+ unsigned x_target_reg_cost[2];
+
+ /* The cost for register when we need to spill. */
+ unsigned x_target_spill_cost[2];
+};
-extern unsigned target_avail_regs;
-extern unsigned target_res_regs;
-extern unsigned target_reg_cost [2];
-extern unsigned target_spill_cost [2];
+extern struct target_cfgloop default_target_cfgloop;
+#if SWITCHABLE_TARGET
+extern struct target_cfgloop *this_target_cfgloop;
+#else
+#define this_target_cfgloop (&default_target_cfgloop)
+#endif
+
+#define target_avail_regs \
+ (this_target_cfgloop->x_target_avail_regs)
+#define target_clobbered_regs \
+ (this_target_cfgloop->x_target_clobbered_regs)
+#define target_res_regs \
+ (this_target_cfgloop->x_target_res_regs)
+#define target_reg_cost \
+ (this_target_cfgloop->x_target_reg_cost)
+#define target_spill_cost \
+ (this_target_cfgloop->x_target_spill_cost)
/* Register pressure estimation for induction variable optimizations & loop
invariant motion. */
-extern unsigned estimate_reg_pressure_cost (unsigned, unsigned, bool);
+extern unsigned estimate_reg_pressure_cost (unsigned, unsigned, bool, bool);
extern void init_set_costs (void);
/* Loop optimizer initialization. */
extern void unroll_and_peel_loops (int);
extern void doloop_optimize_loops (void);
extern void move_loop_invariants (void);
+extern bool finite_loop_p (struct loop *);
#endif /* GCC_CFGLOOP_H */