/* Natural loop functions
- Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003
+ Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
Free Software Foundation, Inc.
This file is part of GCC.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
+
+#ifndef GCC_CFGLOOP_H
+#define GCC_CFGLOOP_H
+
+#include "basic-block.h"
+/* For rtx_code. */
+#include "rtl.h"
/* Structure to hold decision about unrolling/peeling. */
enum lpt_dec
unsigned times;
};
-/* Description of loop for simple loop unrolling. */
-struct loop_desc
+/* The structure describing a bound on number of iterations of a loop. */
+
+struct nb_iter_bound
{
- int postincr; /* 1 if increment/decrement is done after loop exit condition. */
- rtx stride; /* Value added to VAR in each iteration. */
- rtx var; /* Loop control variable. */
- rtx var_alts; /* List of definitions of its initial value. */
- rtx lim; /* Expression var is compared with. */
- rtx lim_alts; /* List of definitions of its initial value. */
- bool const_iter; /* True if it iterates constant number of times. */
- unsigned HOST_WIDE_INT niter;
- /* Number of iterations if it is constant. */
- bool may_be_zero; /* If we cannot determine that the first iteration will pass. */
- enum rtx_code cond; /* Exit condition. */
- int neg; /* Set to 1 if loop ends when condition is satisfied. */
- edge out_edge; /* The exit edge. */
- edge in_edge; /* And the other one. */
- int n_branches; /* Number of branches inside the loop. */
+ /* 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;
+
+ /* True if the bound is "realistic" -- i.e., most likely the loop really has
+ number of iterations close to the bound. Exact bounds (if the number of
+ iterations of a loop is a constant) and bounds derived from the size of
+ data accessed in the loop are considered realistic. */
+ bool realistic;
+
+ /* The next bound in the list. */
+ 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. */
/* Basic block of loop latch. */
basic_block latch;
- /* Basic block of loop preheader or NULL if it does not exist. */
- basic_block pre_header;
-
/* For loop unrolling/peeling decision. */
struct lpt_decision lpt_decision;
- /* Simple loop description. */
- int simple;
- struct loop_desc desc;
- int has_desc;
-
/* Number of loop insns. */
unsigned ninsns;
/* Average number of executed insns per iteration. */
unsigned av_ninsns;
- /* Array of edges along the preheader extended basic block trace.
- The source of the first edge is the root node of preheader
- extended basic block, if it exists. */
- edge *pre_header_edges;
-
- /* Number of edges along the pre_header extended basic block trace. */
- int num_pre_header_edges;
-
- /* The first block in the loop. This is not necessarily the same as
- the loop header. */
- basic_block first;
-
- /* The last block in the loop. This is not necessarily the same as
- the loop latch. */
- basic_block last;
-
- /* Bitmap of blocks contained within the loop. */
- sbitmap nodes;
-
/* Number of blocks contained within the loop. */
unsigned num_nodes;
- /* Array of edges that enter the loop. */
- edge *entry_edges;
-
- /* Number of edges that enter the loop. */
- int num_entries;
-
- /* Array of edges that exit the loop. */
- edge *exit_edges;
-
- /* Number of edges that exit the loop. */
- int num_exits;
-
- /* Bitmap of blocks that dominate all exits of the loop. */
- sbitmap exits_doms;
-
/* 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;
/* Loop that is copy of this loop. */
struct loop *copy;
- /* Nonzero if the loop is invalid (e.g., contains setjmp.). */
- int invalid;
-
/* Auxiliary info specific to a pass. */
void *aux;
- /* The following are currently used by loop.c but they are likely to
- disappear as loop.c is converted to use the CFG. */
-
- /* Nonzero if the loop has a NOTE_INSN_LOOP_VTOP. */
- rtx vtop;
-
- /* Nonzero if the loop has a NOTE_INSN_LOOP_CONT.
- A continue statement will generate a branch to NEXT_INSN (cont). */
- rtx cont;
-
- /* The dominator of cont. */
- rtx cont_dominator;
-
- /* The NOTE_INSN_LOOP_BEG. */
- rtx start;
-
- /* The NOTE_INSN_LOOP_END. */
- rtx end;
-
- /* For a rotated loop that is entered near the bottom,
- this is the label at the top. Otherwise it is zero. */
- rtx top;
-
- /* Place in the loop where control enters. */
- rtx scan_start;
-
- /* The position where to sink insns out of the loop. */
- rtx sink;
-
- /* List of all LABEL_REFs which refer to code labels outside the
- loop. Used by routines that need to know all loop exits, such as
- final_biv_value and final_giv_value.
-
- This does not include loop exits due to return instructions.
- This is because all bivs and givs are pseudos, and hence must be
- dead after a return, so the presence of a return does not affect
- any of the optimizations that use this info. It is simpler to
- just not include return instructions on this list. */
- rtx exit_labels;
-
- /* The number of LABEL_REFs on exit_labels for this loop and all
- loops nested inside it. */
- int exit_count;
+ /* 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;
+
+ /* An integer estimation of the number of iterations. Estimate_state
+ describes what is the state of the estimation. */
+ enum
+ {
+ /* Estimate was not computed yet. */
+ EST_NOT_COMPUTED,
+ /* Estimate was computed, but we could derive no useful bound. */
+ EST_NOT_AVAILABLE,
+ /* Estimate is ready. */
+ EST_AVAILABLE
+ } estimate_state;
+ double_int estimated_nb_iterations;
+
+ /* Upper bound on number of iterations of a loop. */
+ struct nb_iter_bound *bounds;
+
+ /* 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_IRREDUCIBLE_REGIONS = 4,
+ LOOPS_HAVE_RECORDED_EXITS = 8
};
+#define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \
+ | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
+
+typedef struct loop *loop_p;
+DEF_VEC_P (loop_p);
+DEF_VEC_ALLOC_P (loop_p, heap);
+
/* Structure to hold CFG information about natural loops within a function. */
struct loops
{
- /* Number of natural loops in the function. */
- unsigned num;
-
- /* Maximum nested loop level in the function. */
- unsigned levels;
+ /* State of loops. */
+ int state;
- /* Array of natural loop descriptors (scanning this array in reverse order
- will find the inner loops before their enclosing outer loops). */
- struct loop *array;
+ /* Array of the loops. */
+ VEC (loop_p, heap) *larray;
- /* The above array is unused in new loop infrastructure and is kept only for
- purposes of the old loop optimizer. Instead we store just pointers to
- loops here. */
- struct loop **parray;
+ /* 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;
-
- /* Information derived from the CFG. */
- struct cfg
- {
- /* The bitmap vector of dominators or NULL if not computed. */
- dominance_info dom;
-
- /* 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;
-
- /* State of loops. */
- int state;
};
-/* Flags for loop discovery. */
-
-#define LOOP_TREE 1 /* Build loop hierarchy tree. */
-#define LOOP_PRE_HEADER 2 /* Analyze loop preheader. */
-#define LOOP_ENTRY_EDGES 4 /* Find entry edges. */
-#define LOOP_EXIT_EDGES 8 /* Find exit edges. */
-#define LOOP_EDGES (LOOP_ENTRY_EDGES | LOOP_EXIT_EDGES)
-#define LOOP_ALL 15 /* All of the above */
-
/* Loop recognition. */
-extern int flow_loops_find (struct loops *, int flags);
-extern int flow_loops_update (struct loops *, int flags);
+extern int flow_loops_find (struct loops *);
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);
-extern int flow_loop_scan (struct loops *, struct loop *, int);
+struct loop *alloc_loop (void);
extern void flow_loop_free (struct loop *);
-void mark_irreducible_loops (struct loops *);
+int flow_loop_nodes_find (basic_block, struct loop *);
+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 bool flow_loop_outside_edge_p (const struct loop *, edge);
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 *);
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 (void);
/* Loops & cfg manipulation. */
extern basic_block *get_loop_body (const struct loop *);
-extern edge *get_loop_exit_edges (const struct loop *, 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 *);
+extern unsigned num_loop_branches (const struct loop *);
extern edge loop_preheader_edge (const struct loop *);
extern edge loop_latch_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 (struct loops *, struct loop *);
-extern void cancel_loop_tree (struct loops *, struct loop *);
+extern void cancel_loop_tree (struct loop *);
+extern void delete_loop (struct loop *);
-extern basic_block loop_split_edge_with (edge, rtx, struct loops *);
extern int fix_loop_placement (struct loop *);
enum
CP_SIMPLE_PREHEADERS = 1
};
-extern void create_preheaders (struct loops *, int);
-extern void force_single_succ_latches (struct loops *);
+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 simple_loop_p (struct loops *, struct loop *, struct loop_desc *);
-extern rtx count_loop_iterations (struct loop_desc *, rtx, rtx);
-extern bool just_once_each_iteration_p (struct loops *,struct loop *,
- basic_block);
+extern bool just_once_each_iteration_p (const struct loop *, basic_block);
extern unsigned expected_loop_iterations (const struct loop *);
+extern rtx doloop_condition_get (rtx);
/* Loop manipulation. */
extern bool can_duplicate_loop_p (struct loop *loop);
#define DLTHE_FLAG_UPDATE_FREQ 1 /* Update frequencies in
duplicate_loop_to_header_edge. */
+#define DLTHE_RECORD_COPY_NUMBER 2 /* Record copy number in the aux
+ field of newly create BB. */
+#define DLTHE_FLAG_COMPLETTE_PEEL 4 /* Update frequencies expecting
+ a complete peeling. */
+
+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. */
+
+/* The description of induction variable. The things are a bit complicated
+ due to need to handle subregs and extends. The value of the object described
+ by it can be obtained as follows (all computations are done in extend_mode):
+
+ Value in i-th iteration is
+ delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)).
-extern int 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);
-extern void unloop (struct loops *, struct loop *);
-extern bool remove_path (struct loops *, edge);
-extern edge split_loop_bb (struct loops *, basic_block, rtx);
+ 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)
+
+ The get_iv_value function can be used to obtain these expressions.
+
+ ??? Add a third mode field that would specify the mode in that inner
+ computation is done, which would enable it to be different from the
+ outer one? */
+
+struct rtx_iv
+{
+ /* Its base and step (mode of base and step is supposed to be extend_mode,
+ see the description above). */
+ rtx base, step;
+
+ /* The type of extend applied to it (SIGN_EXTEND, ZERO_EXTEND or UNKNOWN). */
+ enum rtx_code extend;
+
+ /* Operations applied in the extended mode. */
+ rtx delta, mult;
+
+ /* The mode it is extended to. */
+ enum machine_mode extend_mode;
+
+ /* The mode the variable iterates in. */
+ enum machine_mode mode;
+
+ /* Whether the first iteration needs to be handled specially. */
+ unsigned first_special : 1;
+};
+
+/* The description of an exit from the loop and of the number of iterations
+ till we take the exit. */
+
+struct niter_desc
+{
+ /* The edge out of the loop. */
+ edge out_edge;
+
+ /* The other edge leading from the condition. */
+ edge in_edge;
+
+ /* True if we are able to say anything about number of iterations of the
+ loop. */
+ bool simple_p;
+
+ /* True if the loop iterates the constant number of times. */
+ bool const_iter;
+
+ /* Number of iterations if constant. */
+ unsigned HOST_WIDEST_INT niter;
+
+ /* Upper bound on the number of iterations. */
+ unsigned HOST_WIDEST_INT niter_max;
+
+ /* Assumptions under that the rest of the information is valid. */
+ rtx assumptions;
+
+ /* Assumptions under that the loop ends before reaching the latch,
+ even if value of niter_expr says otherwise. */
+ rtx noloop_assumptions;
+
+ /* Condition under that the loop is infinite. */
+ rtx infinite;
+
+ /* Whether the comparison is signed. */
+ bool signed_p;
+
+ /* The mode in that niter_expr should be computed. */
+ enum machine_mode mode;
+
+ /* The number of iterations of the loop. */
+ rtx niter_expr;
+};
+
+extern void iv_analysis_loop_init (struct loop *);
+extern bool iv_analyze (rtx, rtx, struct rtx_iv *);
+extern bool iv_analyze_result (rtx, rtx, struct rtx_iv *);
+extern bool iv_analyze_expr (rtx, rtx, enum machine_mode, struct rtx_iv *);
+extern rtx get_iv_value (struct rtx_iv *, rtx);
+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);
+
+static inline struct niter_desc *
+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 list of loops in current_loops. */
+
+static inline VEC (loop_p, heap) *
+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. */
+ LI_ONLY_OLD = 8 /* Do not traverse the loops created during the
+ traversal (this is the default behavior with
+ LI_FROM_INNERMOST). */
+};
+
+/* The iterator for loops. */
+
+typedef struct
+{
+ int idx; /* Index of the actual loop. */
+ int end; /* Only loops before end should be traversed. */
+} loop_iterator;
+
+static inline void
+fel_next (loop_iterator *li, loop_p *loop, unsigned flags)
+{
+ 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
+ {
+ 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 = NULL;
+}
+
+static inline void
+fel_init (loop_iterator *li, loop_p *loop, unsigned flags)
+{
+ if (!current_loops)
+ {
+ li->idx = 0;
+ li->end = 0;
+ *loop = NULL;
+ return;
+ }
+
+ if (flags & LI_FROM_INNERMOST)
+ {
+ li->idx = number_of_loops ();
+ li->end = (flags & LI_INCLUDE_ROOT) ? -1 : 0;
+ }
+ else
+ {
+ li->idx = (flags & LI_INCLUDE_ROOT) ? -1 : 0;
+ li->end = number_of_loops ();
+ }
+ fel_next (li, loop, flags);
+}
+
+#define FOR_EACH_LOOP(LI, LOOP, FLAGS) \
+ for (fel_init (&(LI), &(LOOP), FLAGS); \
+ (LOOP); \
+ fel_next (&(LI), &(LOOP), FLAGS))
+
+/* 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. */
+
+/* Register pressure estimation for induction variable optimizations & loop
+ invariant motion. */
+extern unsigned global_cost_for_size (unsigned, unsigned, unsigned);
+extern void init_set_costs (void);
/* Loop optimizer initialization. */
-extern struct loops *loop_optimizer_init (FILE *);
-extern void loop_optimizer_finalize (struct loops *, FILE *);
+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 unroll_and_peel_loops (int);
+extern void doloop_optimize_loops (void);
+extern void move_loop_invariants (void);
+
+#endif /* GCC_CFGLOOP_H */