/* Natural loop functions
- Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
+ 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
unsigned times;
};
+/* The structure describing a bound on number of iterations of a loop. */
+
+struct nb_iter_bound
+{
+ 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. */
+ struct nb_iter_bound *next;
+ /* The next bound in a list. */
+};
+
/* Structure to hold information for each natural loop. */
struct 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;
/* 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 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;
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. */
+ disappear when loop.c is replaced and removed. */
/* The NOTE_INSN_LOOP_BEG. */
rtx start;
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;
+
/* 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;
};
/* Flags for state of loop structure. */
LOOPS_HAVE_MARKED_SINGLE_EXITS = 8
};
+#define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \
+ | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
+
/* 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;
-
/* Array of natural loop descriptors (scanning this array in reverse order
will find the inner loops before their enclosing outer loops). */
struct loop *array;
/* 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. */
+ 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;
/* Pointer to root of loop hierarchy tree. */
extern struct loops *current_loops;
-/* 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 *,
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 *);
+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 *);
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 *);
+extern bool loop_exit_edge_p (const struct loop *, edge);
+extern void mark_loop_exit_edges (struct loops *);
/* Loops & cfg manipulation. */
extern basic_block *get_loop_body (const struct loop *);
extern void verify_loop_structure (struct loops *);
/* Loop analysis. */
-extern bool just_once_each_iteration_p (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 loops *, struct loop *,
struct loop *);
-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 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 edge split_loop_bb (basic_block, rtx);
/* Induction variable analysis. */
/* 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;
};
};
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 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_number_of_iterations (struct loop *, rtx, rtx,
- 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 loop->aux;
+ return (struct niter_desc *) loop->aux;
}
/* The properties of the target. */
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 struct loops *loop_optimizer_init (unsigned);
+extern void loop_optimizer_finalize (struct loops *);
/* Optimization passes. */
extern void unswitch_loops (struct 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);
/* Old loop optimizer interface. */
/* Flags passed to loop_optimize. */
#define LOOP_PREFETCH 1
-extern void loop_optimize (rtx, FILE *, int);
-
#endif /* GCC_CFGLOOP_H */