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. */
+ /* 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;
- /* The next bound in a list. */
};
/* Structure to hold information for each natural loop. */
/* Average number of executed insns per iteration. */
unsigned av_ninsns;
- /* 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;
-
/* Number of blocks contained within the loop. */
unsigned num_nodes;
/* 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 when loop.c is replaced and removed. */
-
- /* 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 probable number of times the loop is executed at runtime.
This is an INTEGER_CST or an expression containing symbolic
names. Don't access this field directly:
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
+ {
+ /* 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;
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;
- /* Array of natural loop descriptors (scanning this array in reverse order
- will find the inner loops before their enclosing outer loops). */
- struct loop *array;
+ /* State of loops. */
+ int state;
- /* 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.
+ /* 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. */
/* Headers shared by multiple loops that should be merged. */
sbitmap shared_headers;
-
- /* State of loops. */
- int state;
};
/* The loop tree currently optimized. */
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 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 basic_block loop_split_edge_with (edge, rtx);
extern struct loop *loopify (struct loops *, edge, edge,
basic_block, edge, edge, bool);
struct loop * loop_version (struct loops *, struct loop *, void *,
- basic_block *);
+ basic_block *, bool);
extern bool remove_path (struct loops *, edge);
-extern edge split_loop_bb (basic_block, void *);
/* 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)
/* 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_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 */