/* Natural loop functions
- Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002
+ Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
Free Software Foundation, Inc.
This file is part of GCC.
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, 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
-{
- 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. */
-};
-
/* Structure to hold information for each natural loop. */
struct loop
{
/* 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;
/* Loop that is copy of this loop. */
struct loop *copy;
- /* Non-zero if the loop is invalid (e.g., contains setjmp.). */
+ /* Nonzero if the loop is invalid (e.g., contains setjmp.). */
int invalid;
/* Auxiliary info specific to a pass. */
/* The following are currently used by loop.c but they are likely to
disappear as loop.c is converted to use the CFG. */
- /* Non-zero if the loop has a NOTE_INSN_LOOP_VTOP. */
+ /* Nonzero if the loop has a NOTE_INSN_LOOP_VTOP. */
rtx vtop;
- /* Non-zero if the loop has a NOTE_INSN_LOOP_CONT.
+ /* Nonzero if the loop has a NOTE_INSN_LOOP_CONT.
A continue statement will generate a branch to NEXT_INSN (cont). */
rtx cont;
/* 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;
#define LOOP_ALL 15 /* All of the above */
/* Loop recognition. */
-extern int flow_loops_find PARAMS ((struct loops *, int flags));
-extern int flow_loops_update PARAMS ((struct loops *, int flags));
-extern void flow_loops_free PARAMS ((struct loops *));
-extern void flow_loops_dump PARAMS ((const struct loops *, FILE *,
- void (*)(const struct loop *,
- FILE *, int), int));
-extern void flow_loop_dump PARAMS ((const struct loop *, FILE *,
- void (*)(const struct loop *,
- FILE *, int), int));
-extern int flow_loop_scan PARAMS ((struct loops *,
- struct loop *, int));
-void mark_irreducible_loops PARAMS ((struct loops *));
-
-/* Loop datastructure manipulation/querying. */
-extern void flow_loop_tree_node_add PARAMS ((struct loop *, struct loop *));
-extern void flow_loop_tree_node_remove PARAMS ((struct loop *));
-extern bool flow_loop_outside_edge_p PARAMS ((const struct loop *, edge));
-extern bool flow_loop_nested_p PARAMS ((const struct loop *,
- const struct loop *));
-extern bool flow_bb_inside_loop_p PARAMS ((const struct loop *,
- basic_block));
-extern struct loop * find_common_loop PARAMS ((struct loop *, struct loop *));
-extern int num_loop_insns PARAMS ((struct loop *));
-extern int average_num_loop_insns PARAMS ((struct loop *));
+extern int flow_loops_find (struct loops *, int flags);
+extern int flow_loops_update (struct loops *, int flags);
+extern void flow_loops_free (struct loops *);
+extern void flow_loops_dump (const struct loops *, 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 loop *, int);
+extern void flow_loop_free (struct loop *);
+void mark_irreducible_loops (struct loops *);
+extern void create_loop_notes (void);
+
+/* 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 *);
+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 PARAMS ((const struct loop *));
+extern basic_block *get_loop_body (const struct loop *);
+extern basic_block *get_loop_body_in_dom_order (const struct loop *);
+extern edge *get_loop_exit_edges (const struct loop *, unsigned *);
+extern unsigned num_loop_branches (const struct loop *);
-extern edge loop_preheader_edge PARAMS ((const struct loop *));
-extern edge loop_latch_edge PARAMS ((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 PARAMS ((basic_block, struct loop *));
-extern void remove_bb_from_loops PARAMS ((basic_block));
+extern void add_bb_to_loop (basic_block, struct loop *);
+extern void remove_bb_from_loops (basic_block);
-extern void cancel_loop PARAMS ((struct loops *, struct loop *));
-extern void cancel_loop_tree PARAMS ((struct loops *, struct loop *));
+extern void cancel_loop (struct loops *, struct loop *);
+extern void cancel_loop_tree (struct loops *, struct loop *);
-extern basic_block loop_split_edge_with PARAMS ((edge, rtx, struct loops *));
+extern basic_block loop_split_edge_with (edge, rtx);
+extern int fix_loop_placement (struct loop *);
enum
{
- CP_SIMPLE_PREHEADERS = 1,
- CP_INSIDE_CFGLAYOUT = 2
+ CP_SIMPLE_PREHEADERS = 1
};
-extern void create_preheaders PARAMS ((struct loops *, int));
-extern void force_single_succ_latches PARAMS ((struct loops *));
+extern void create_preheaders (struct loops *, int);
+extern void force_single_succ_latches (struct loops *);
-extern void verify_loop_structure PARAMS ((struct loops *));
+extern void verify_loop_structure (struct loops *);
/* Loop analysis. */
-extern bool simple_loop_p PARAMS ((struct loops *, struct loop *,
- struct loop_desc *));
-extern rtx count_loop_iterations PARAMS ((struct loop_desc *, rtx, rtx));
-extern bool just_once_each_iteration_p PARAMS ((struct loops *,struct loop *,
- basic_block));
-extern unsigned expected_loop_iterations PARAMS ((const struct loop *));
+extern bool just_once_each_iteration_p (struct loop *, basic_block);
+extern unsigned expected_loop_iterations (const struct loop *);
+
+/* 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. */
+
+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 (basic_block, rtx);
+
+/* 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)).
+
+ If first_special is true, the value in the first iteration is
+ delta + mult * base
+
+ If extend = NIL, 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 NIL). */
+ 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 we have already filled the remaining fields. */
+ unsigned analysed : 1;
+
+ /* 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 rtx iv_get_reaching_def (rtx, rtx);
+extern bool iv_analyze (rtx, rtx, struct rtx_iv *);
+extern rtx get_iv_value (struct rtx_iv *, rtx);
+extern void find_simple_exit (struct loop *, struct niter_desc *);
+extern void iv_number_of_iterations (struct loop *, rtx, rtx,
+ struct niter_desc *);
+extern void iv_analysis_done (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 loop->aux;
+}
+
+/* Loop optimizer initialization. */
+extern struct loops *loop_optimizer_init (FILE *);
+extern void loop_optimizer_finalize (struct loops *, FILE *);
+
+/* Optimization passes. */
+extern void unswitch_loops (struct loops *);
+
+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. */
+};
+
+extern void unroll_and_peel_loops (struct loops *, int);
+extern void doloop_optimize_loops (struct loops *);
+
+#endif /* GCC_CFGLOOP_H */
OSDN Git Service
