123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743 |
- #ifndef GCC_CFGLOOP_H
- #define GCC_CFGLOOP_H
- #include "double-int.h"
- #include "wide-int.h"
- #include "bitmap.h"
- #include "sbitmap.h"
- #include "hashtab.h"
- #include "hash-set.h"
- #include "vec.h"
- #include "machmode.h"
- #include "tm.h"
- #include "hard-reg-set.h"
- #include "input.h"
- #include "function.h"
- #include "cfgloopmanip.h"
- enum lpt_dec
- {
- LPT_NONE,
- LPT_UNROLL_CONSTANT,
- LPT_UNROLL_RUNTIME,
- LPT_UNROLL_STUPID
- };
- struct GTY (()) lpt_decision {
- enum lpt_dec decision;
- unsigned times;
- };
- enum iv_extend_code
- {
- IV_SIGN_EXTEND,
- IV_ZERO_EXTEND,
- IV_UNKNOWN_EXTEND
- };
- struct GTY ((chain_next ("%h.next"))) nb_iter_bound {
-
- gimple stmt;
-
- widest_int bound;
-
- bool is_exit;
-
- struct nb_iter_bound *next;
- };
- struct GTY ((for_user)) loop_exit {
-
- edge e;
-
- struct loop_exit *prev;
- struct loop_exit *next;
-
- struct loop_exit *next_e;
- };
- struct loop_exit_hasher : ggc_hasher<loop_exit *>
- {
- typedef edge compare_type;
- static hashval_t hash (loop_exit *);
- static bool equal (loop_exit *, edge);
- static void remove (loop_exit *);
- };
- typedef struct loop *loop_p;
- enum loop_estimation
- {
-
- EST_NOT_COMPUTED,
-
- EST_AVAILABLE,
- EST_LAST
- };
- struct GTY ((chain_next ("%h.next"))) loop {
-
- int num;
-
- unsigned ninsns;
-
- basic_block header;
-
- basic_block latch;
-
- struct lpt_decision lpt_decision;
-
- unsigned av_ninsns;
-
- unsigned num_nodes;
-
- vec<loop_p, va_gc> *superloops;
-
- struct loop *inner;
-
- struct loop *next;
-
- PTR GTY ((skip (""))) aux;
-
- tree nb_iterations;
-
- widest_int nb_iterations_upper_bound;
-
- widest_int nb_iterations_estimate;
- bool any_upper_bound;
- bool any_estimate;
-
- bool can_be_parallel;
-
- bool warned_aggressive_loop_optimizations;
-
- enum loop_estimation estimate_state;
-
- int safelen;
-
- bool dont_vectorize;
-
- bool force_vectorize;
-
- tree simduid;
-
- struct nb_iter_bound *bounds;
-
- struct loop_exit *exits;
-
- struct niter_desc *simple_loop_desc;
-
- basic_block former_header;
- };
- enum
- {
- LOOPS_HAVE_PREHEADERS = 1,
- LOOPS_HAVE_SIMPLE_LATCHES = 2,
- LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4,
- LOOPS_HAVE_RECORDED_EXITS = 8,
- LOOPS_MAY_HAVE_MULTIPLE_LATCHES = 16,
- LOOP_CLOSED_SSA = 32,
- LOOPS_NEED_FIXUP = 64,
- LOOPS_HAVE_FALLTHRU_PREHEADERS = 128
- };
- #define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \
- | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
- #define AVOID_CFG_MODIFICATIONS (LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
- struct GTY (()) loops {
-
- int state;
-
- vec<loop_p, va_gc> *larray;
-
- hash_table<loop_exit_hasher> *GTY(()) exits;
-
- struct loop *tree_root;
- };
- bool bb_loop_header_p (basic_block);
- void init_loops_structure (struct function *, struct loops *, unsigned);
- extern struct loops *flow_loops_find (struct loops *);
- extern void disambiguate_loops_with_multiple_latches (void);
- extern void flow_loops_free (struct loops *);
- extern void flow_loops_dump (FILE *,
- void (*)(const struct loop *, FILE *, int), int);
- extern void flow_loop_dump (const struct loop *, FILE *,
- void (*)(const struct loop *, FILE *, int), int);
- struct loop *alloc_loop (void);
- extern void flow_loop_free (struct loop *);
- int flow_loop_nodes_find (basic_block, struct loop *);
- unsigned fix_loop_structure (bitmap changed_bbs);
- bool mark_irreducible_loops (void);
- void release_recorded_exits (void);
- void record_loop_exits (void);
- void rescan_loop_exit (edge, bool, bool);
- 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);
- struct eni_weights_d;
- extern int num_loop_insns (const struct loop *);
- extern int average_num_loop_insns (const struct loop *);
- extern unsigned get_loop_level (const struct loop *);
- extern bool loop_exit_edge_p (const struct loop *, const_edge);
- extern bool loop_exits_to_bb_p (struct loop *, basic_block);
- extern bool loop_exits_from_bb_p (struct loop *, basic_block);
- extern void mark_loop_exit_edges (void);
- extern location_t get_loop_location (struct loop *loop);
- extern basic_block *get_loop_body (const struct loop *);
- extern unsigned get_loop_body_with_size (const struct loop *, basic_block *,
- unsigned);
- 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 basic_block *get_loop_body_in_custom_order (const struct loop *,
- int (*) (const void *, const void *));
- extern vec<edge> get_loop_exit_edges (const struct loop *);
- extern edge single_exit (const struct loop *);
- extern edge single_likely_exit (struct loop *loop);
- 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 loop *);
- extern void delete_loop (struct loop *);
- extern void verify_loop_structure (void);
- extern bool just_once_each_iteration_p (const struct loop *, const_basic_block);
- gcov_type expected_loop_iterations_unbounded (const struct loop *);
- extern unsigned expected_loop_iterations (const struct loop *);
- extern rtx doloop_condition_get (rtx);
- void mark_loop_for_removal (loop_p);
- struct rtx_iv
- {
-
- rtx base, step;
-
- enum iv_extend_code extend;
-
- rtx delta, mult;
-
- machine_mode extend_mode;
-
- machine_mode mode;
-
- unsigned first_special : 1;
- };
- struct GTY(()) niter_desc
- {
-
- edge out_edge;
-
- edge in_edge;
-
- bool simple_p;
-
- bool const_iter;
-
- uint64_t niter;
-
- rtx assumptions;
-
- rtx noloop_assumptions;
-
- rtx infinite;
-
- bool signed_p;
-
- machine_mode mode;
-
- rtx niter_expr;
- };
- extern void iv_analysis_loop_init (struct loop *);
- extern bool iv_analyze (rtx_insn *, rtx, struct rtx_iv *);
- extern bool iv_analyze_result (rtx_insn *, rtx, struct rtx_iv *);
- extern bool iv_analyze_expr (rtx_insn *, rtx, machine_mode,
- struct rtx_iv *);
- extern rtx get_iv_value (struct rtx_iv *, rtx);
- extern bool biv_p (rtx_insn *, 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->simple_loop_desc;
- }
- static inline struct loop *
- get_loop (struct function *fn, unsigned num)
- {
- return (*loops_for_fn (fn)->larray)[num];
- }
- /* Returns the number of superloops of LOOP. */
- static inline unsigned
- loop_depth (const struct loop *loop)
- {
- return vec_safe_length (loop->superloops);
- }
- static inline struct loop *
- loop_outer (const struct loop *loop)
- {
- unsigned n = vec_safe_length (loop->superloops);
- if (n == 0)
- return NULL;
- return (*loop->superloops)[n - 1];
- }
- static inline bool
- loop_has_exit_edges (const struct loop *loop)
- {
- return loop->exits->next->e != NULL;
- }
- inline vec<loop_p, va_gc> *
- get_loops (struct function *fn)
- {
- struct loops *loops = loops_for_fn (fn);
- if (!loops)
- return NULL;
- return loops->larray;
- }
- static inline unsigned
- number_of_loops (struct function *fn)
- {
- struct loops *loops = loops_for_fn (fn);
- if (!loops)
- return 0;
- return vec_safe_length (loops->larray);
- }
- static inline bool
- loops_state_satisfies_p (unsigned flags)
- {
- return (current_loops->state & flags) == flags;
- }
- static inline void
- loops_state_set (unsigned flags)
- {
- current_loops->state |= flags;
- }
- static inline void
- loops_state_clear (unsigned flags)
- {
- if (!current_loops)
- return;
- current_loops->state &= ~flags;
- }
- enum li_flags
- {
- LI_INCLUDE_ROOT = 1,
- LI_FROM_INNERMOST = 2,
- LI_ONLY_INNERMOST = 4
- };
- struct loop_iterator
- {
- loop_iterator (loop_p *loop, unsigned flags);
- ~loop_iterator ();
- inline loop_p next ();
-
- vec<int> to_visit;
-
- unsigned idx;
- };
- inline loop_p
- loop_iterator::next ()
- {
- int anum;
- while (this->to_visit.iterate (this->idx, &anum))
- {
- this->idx++;
- loop_p loop = get_loop (cfun, anum);
- if (loop)
- return loop;
- }
- return NULL;
- }
- inline
- loop_iterator::loop_iterator (loop_p *loop, unsigned flags)
- {
- struct loop *aloop;
- unsigned i;
- int mn;
- this->idx = 0;
- if (!current_loops)
- {
- this->to_visit.create (0);
- *loop = NULL;
- return;
- }
- this->to_visit.create (number_of_loops (cfun));
- mn = (flags & LI_INCLUDE_ROOT) ? 0 : 1;
- if (flags & LI_ONLY_INNERMOST)
- {
- for (i = 0; vec_safe_iterate (current_loops->larray, i, &aloop); i++)
- if (aloop != NULL
- && aloop->inner == NULL
- && aloop->num >= mn)
- this->to_visit.quick_push (aloop->num);
- }
- else if (flags & LI_FROM_INNERMOST)
- {
-
- for (aloop = current_loops->tree_root;
- aloop->inner != NULL;
- aloop = aloop->inner)
- continue;
- while (1)
- {
- if (aloop->num >= mn)
- this->to_visit.quick_push (aloop->num);
- if (aloop->next)
- {
- for (aloop = aloop->next;
- aloop->inner != NULL;
- aloop = aloop->inner)
- continue;
- }
- else if (!loop_outer (aloop))
- break;
- else
- aloop = loop_outer (aloop);
- }
- }
- else
- {
-
- aloop = current_loops->tree_root;
- while (1)
- {
- if (aloop->num >= mn)
- this->to_visit.quick_push (aloop->num);
- if (aloop->inner != NULL)
- aloop = aloop->inner;
- else
- {
- while (aloop != NULL && aloop->next == NULL)
- aloop = loop_outer (aloop);
- if (aloop == NULL)
- break;
- aloop = aloop->next;
- }
- }
- }
- *loop = this->next ();
- }
- inline
- loop_iterator::~loop_iterator ()
- {
- this->to_visit.release ();
- }
- #define FOR_EACH_LOOP(LOOP, FLAGS) \
- for (loop_iterator li(&(LOOP), FLAGS); \
- (LOOP); \
- (LOOP) = li.next ())
- struct target_cfgloop {
-
- unsigned x_target_avail_regs;
-
- unsigned x_target_clobbered_regs;
-
- unsigned x_target_res_regs;
-
- unsigned x_target_reg_cost[2];
-
- unsigned x_target_spill_cost[2];
- };
- extern struct target_cfgloop default_target_cfgloop;
- #if SWITCHABLE_TARGET
- extern struct target_cfgloop *this_target_cfgloop;
- #else
- #define this_target_cfgloop (&default_target_cfgloop)
- #endif
- #define target_avail_regs \
- (this_target_cfgloop->x_target_avail_regs)
- #define target_clobbered_regs \
- (this_target_cfgloop->x_target_clobbered_regs)
- #define target_res_regs \
- (this_target_cfgloop->x_target_res_regs)
- #define target_reg_cost \
- (this_target_cfgloop->x_target_reg_cost)
- #define target_spill_cost \
- (this_target_cfgloop->x_target_spill_cost)
- extern unsigned estimate_reg_pressure_cost (unsigned, unsigned, bool, bool);
- extern void init_set_costs (void);
- extern void loop_optimizer_init (unsigned);
- extern void loop_optimizer_finalize (void);
- enum
- {
- UAP_UNROLL = 1,
- UAP_UNROLL_ALL = 2
- };
- extern void doloop_optimize_loops (void);
- extern void move_loop_invariants (void);
- extern vec<basic_block> get_loop_hot_path (const struct loop *loop);
- static inline struct loop *
- loop_outermost (struct loop *loop)
- {
- unsigned n = vec_safe_length (loop->superloops);
- if (n <= 1)
- return loop;
- return (*loop->superloops)[1];
- }
- extern void record_niter_bound (struct loop *, const widest_int &, bool, bool);
- extern HOST_WIDE_INT get_estimated_loop_iterations_int (struct loop *);
- extern HOST_WIDE_INT get_max_loop_iterations_int (struct loop *);
- extern bool get_estimated_loop_iterations (struct loop *loop, widest_int *nit);
- extern bool get_max_loop_iterations (struct loop *loop, widest_int *nit);
- extern int bb_loop_depth (const_basic_block);
- static inline widest_int
- gcov_type_to_wide_int (gcov_type val)
- {
- HOST_WIDE_INT a[2];
- a[0] = (unsigned HOST_WIDE_INT) val;
-
- val >>= HOST_BITS_PER_WIDE_INT - 1;
- val >>= 1;
- a[1] = (unsigned HOST_WIDE_INT) val;
- return widest_int::from_array (a, 2);
- }
- #endif
|