X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fcfgloop.h;h=9df217eb509c84eeb7aa43e6e61d54193d363e71;hb=7c1ab928ec2df070c5c9a55efe0c276a5e1aa004;hp=c5db9149c9d96e0d369e0b43f005901a8f080128;hpb=a5414ff59071320dd80a6541af5befab853ca6ff;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index c5db9149c9d..9df217eb509 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -1,5 +1,5 @@ /* Natural loop functions - Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003 + Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc. This file is part of GCC. @@ -19,6 +19,13 @@ 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. */ +#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 { @@ -36,24 +43,18 @@ struct lpt_decision 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. */ + 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. */ @@ -74,11 +75,6 @@ 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; @@ -101,9 +97,6 @@ struct loop 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; @@ -144,24 +137,14 @@ struct loop /* 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. */ 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. */ - - /* Non-zero if the loop has a NOTE_INSN_LOOP_VTOP. */ - rtx vtop; - - /* Non-zero 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; + disappear when loop.c is replaced and removed. */ /* The NOTE_INSN_LOOP_BEG. */ rtx start; @@ -193,6 +176,30 @@ struct loop /* 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: + number_of_iterations_in_loop computes and caches the computed + 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. */ @@ -200,7 +207,8 @@ enum { LOOPS_HAVE_PREHEADERS = 1, LOOPS_HAVE_SIMPLE_LATCHES = 2, - LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4 + LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4, + LOOPS_HAVE_MARKED_SINGLE_EXITS = 8 }; /* Structure to hold CFG information about natural loops within a function. */ @@ -227,9 +235,6 @@ struct loops /* 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; @@ -245,6 +250,10 @@ struct loops int state; }; +/* The loop tree currently optimized. */ + +extern struct loops *current_loops; + /* Flags for loop discovery. */ #define LOOP_TREE 1 /* Build loop hierarchy tree. */ @@ -255,90 +264,209 @@ struct loops #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)); -extern void flow_loop_free PARAMS ((struct loop *)); -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 *, - const 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 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 *); +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 *); +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 *); /* Loops & cfg manipulation. */ -extern basic_block *get_loop_body PARAMS ((const struct loop *)); -extern edge *get_loop_exit_edges PARAMS ((const struct loop *, unsigned *)); +extern basic_block *get_loop_body (const struct loop *); +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 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 int fix_loop_placement PARAMS ((struct loop *)); +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 PARAMS ((struct loop *loop)); +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 PARAMS ((struct loop *, edge, - struct loops *, unsigned, - sbitmap, edge, edge *, - unsigned *, int)); -extern struct loop *loopify PARAMS ((struct loops *, edge, - edge, basic_block)); -extern void unloop PARAMS ((struct loops *, struct loop *)); -extern bool remove_path PARAMS ((struct loops *, edge)); -extern edge split_loop_bb PARAMS ((struct loops *, basic_block, - rtx)); +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, edge, edge, bool); +extern bool remove_path (struct loops *, edge); +extern edge split_loop_bb (basic_block, void *); + +/* 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 = 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 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 bool biv_p (rtx, rtx); +extern void find_simple_exit (struct loop *, 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; +} + +/* 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 PARAMS ((FILE *)); -extern void loop_optimizer_finalize PARAMS ((struct loops *, FILE *)); +extern struct loops *loop_optimizer_init (FILE *); +extern void loop_optimizer_finalize (struct loops *, FILE *); /* Optimization passes. */ -extern void unswitch_loops PARAMS ((struct loops *)); +extern void unswitch_loops (struct loops *); enum { @@ -347,4 +475,16 @@ enum UAP_UNROLL_ALL = 4 /* Enables peeling of all loops. */ }; -extern void unroll_and_peel_loops PARAMS ((struct loops *, int)); +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 */