diff options
Diffstat (limited to 'gcc/cfgloop.h')
| -rw-r--r-- | gcc/cfgloop.h | 403 |
1 files changed, 403 insertions, 0 deletions
diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h new file mode 100644 index 0000000..6838677 --- /dev/null +++ b/gcc/cfgloop.h @@ -0,0 +1,403 @@ +/* Natural loop functions + Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 + Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +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, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, 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 +{ + LPT_NONE, + LPT_PEEL_COMPLETELY, + LPT_PEEL_SIMPLE, + LPT_UNROLL_CONSTANT, + LPT_UNROLL_RUNTIME, + LPT_UNROLL_STUPID +}; + +struct lpt_decision +{ + enum lpt_dec decision; + unsigned times; +}; + +/* The structure describing a bound on number of iterations of a loop. */ + +struct nb_iter_bound +{ + tree bound; /* The constant expression whose value is an upper + bound on the number of executions of ... */ + tree at_stmt; /* ... this statement during one execution of + a loop. */ + struct nb_iter_bound *next; + /* The next bound in a list. */ +}; + +/* Structure to hold information for each natural loop. */ +struct loop +{ + /* Index into loops array. */ + int num; + + /* Basic block of loop header. */ + basic_block header; + + /* Basic block of loop latch. */ + basic_block latch; + + /* For loop unrolling/peeling decision. */ + struct lpt_decision lpt_decision; + + /* Number of loop insns. */ + unsigned ninsns; + + /* Average number of executed insns per iteration. */ + unsigned av_ninsns; + + /* Number of blocks contained within the loop. */ + unsigned num_nodes; + + /* The loop nesting depth. */ + int depth; + + /* Superloops of the loop. */ + struct loop **pred; + + /* The height of the loop (enclosed loop levels) within the loop + hierarchy tree. */ + int level; + + /* The outer (parent) loop or NULL if outermost loop. */ + struct loop *outer; + + /* The first inner (child) loop or NULL if innermost loop. */ + struct loop *inner; + + /* Link to the next (sibling) loop. */ + struct loop *next; + + /* Loop that is copy of this loop. */ + struct loop *copy; + + /* Auxiliary info specific to a pass. */ + void *aux; + + /* 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. */ +enum +{ + LOOPS_HAVE_PREHEADERS = 1, + LOOPS_HAVE_SIMPLE_LATCHES = 2, + LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4, + 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; + + /* State of loops. */ + int state; + + /* 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. */ + struct loop **parray; + + /* Pointer to root of loop hierarchy tree. */ + struct loop *tree_root; + + /* Information derived from the CFG. */ + struct cfg + { + /* The ordering of the basic blocks in a depth first search. */ + int *dfs_order; + + /* The reverse completion ordering of the basic blocks found in a + depth first search. */ + int *rc_order; + } cfg; + + /* Headers shared by multiple loops that should be merged. */ + sbitmap shared_headers; +}; + +/* The loop tree currently optimized. */ + +extern struct loops *current_loops; + +/* Loop recognition. */ +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 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 *); + +/* 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_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 *); +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 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 *); + +extern void add_bb_to_loop (basic_block, struct loop *); +extern void remove_bb_from_loops (basic_block); + +extern void cancel_loop_tree (struct loops *, struct loop *); + +extern basic_block loop_split_edge_with (edge, rtx); +extern int fix_loop_placement (struct loop *); + +enum +{ + CP_SIMPLE_PREHEADERS = 1 +}; + +extern void create_preheaders (struct loops *, int); +extern void force_single_succ_latches (struct loops *); + +extern void verify_loop_structure (struct loops *); + +/* Loop analysis. */ +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 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); + +/* 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 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 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 (struct niter_desc *) 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 (unsigned); +extern void loop_optimizer_finalize (struct loops *); + +/* 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 *); +extern void move_loop_invariants (struct loops *); +extern void record_estimate (struct loop *, tree, tree, tree); + +#endif /* GCC_CFGLOOP_H */ |
