X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Fcfgloop.h;h=1562736faae0e4902fca36eb931e919f0d10e1bd;hp=4d8c67dd35d357ab059d27850c891660eb9f8028;hb=67f3526e422c69b4b0b0fc6fc72345e243433e5f;hpb=0051c76acf69e4b8a5e9f2fadc6af1bd27399c0c diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index 4d8c67dd35d..1562736faae 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,27 +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. */ - enum machine_mode inner_mode; - /* The mode from that it is extended. */ - enum rtx_code extend; /* With this extend. */ - 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. */ @@ -77,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; @@ -104,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; @@ -154,17 +144,7 @@ struct loop 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; + disappear when loop.c is replaced and removed. */ /* The NOTE_INSN_LOOP_BEG. */ rtx start; @@ -196,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. */ @@ -203,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. */ @@ -212,16 +217,16 @@ 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. */ @@ -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. */ @@ -256,7 +265,6 @@ struct loops /* Loop recognition. */ 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); @@ -265,6 +273,8 @@ extern void flow_loop_dump (const struct loop *, FILE *, 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 *); @@ -273,12 +283,18 @@ 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 (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 (const struct loop *); extern edge loop_latch_edge (const struct loop *); @@ -303,8 +319,6 @@ extern void force_single_succ_latches (struct loops *); extern void verify_loop_structure (struct loops *); /* Loop analysis. */ -extern bool simple_loop_p (struct loop *, struct loop_desc *); -extern rtx count_loop_iterations (struct loop_desc *, rtx, rtx); extern bool just_once_each_iteration_p (struct loop *, basic_block); extern unsigned expected_loop_iterations (const struct loop *); @@ -314,13 +328,138 @@ extern bool can_duplicate_loop_p (struct loop *loop); #define DLTHE_FLAG_UPDATE_FREQ 1 /* Update frequencies in duplicate_loop_to_header_edge. */ +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 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, rtx); +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 (FILE *); @@ -337,3 +476,15 @@ enum }; 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 */