/* Natural loop functions
- Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004,
- 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
+ Copyright (C) 1987-2015 Free Software Foundation, Inc.
This file is part of GCC.
#ifndef GCC_CFGLOOP_H
#define GCC_CFGLOOP_H
-#include "basic-block.h"
-/* For rtx_code. */
-#include "rtl.h"
-#include "vecprim.h"
-#include "double-int.h"
+#include "bitmap.h"
+#include "sbitmap.h"
+#include "tm.h"
+#include "hard-reg-set.h"
+#include "function.h"
+#include "cfgloopmanip.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
unsigned times;
};
+/* The type of extend applied to an IV. */
+enum iv_extend_code
+{
+ IV_SIGN_EXTEND,
+ IV_ZERO_EXTEND,
+ IV_UNKNOWN_EXTEND
+};
+
/* The structure describing a bound on number of iterations of a loop. */
struct GTY ((chain_next ("%h.next"))) nb_iter_bound {
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;
+ widest_int bound;
- /* True if the statement will cause the loop to be leaved the (at most)
+ /* 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;
/* Description of the loop exit. */
-struct GTY (()) loop_exit {
+struct GTY ((for_user)) loop_exit {
/* The exit edge. */
- struct edge_def *e;
+ edge e;
/* Previous and next exit in the list of the exits of the loop. */
struct loop_exit *prev;
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;
-DEF_VEC_P (loop_p);
-DEF_VEC_ALLOC_P (loop_p, heap);
-DEF_VEC_ALLOC_P (loop_p, gc);
/* An integer estimation of the number of iterations. Estimate_state
describes what is the state of the estimation. */
/* Estimate was not computed yet. */
EST_NOT_COMPUTED,
/* Estimate is ready. */
- EST_AVAILABLE
+ EST_AVAILABLE,
+ EST_LAST
+};
+
+/* The structure describing non-overflow control induction variable for
+ loop's exit edge. */
+struct GTY ((chain_next ("%h.next"))) control_iv {
+ tree base;
+ tree step;
+ struct control_iv *next;
};
/* Structure to hold information for each natural loop. */
unsigned ninsns;
/* Basic block of loop header. */
- struct basic_block_def *header;
+ basic_block header;
/* Basic block of loop latch. */
- struct basic_block_def *latch;
+ basic_block latch;
/* For loop unrolling/peeling decision. */
struct lpt_decision lpt_decision;
unsigned num_nodes;
/* Superloops of the loop, starting with the outermost loop. */
- VEC (loop_p, gc) *superloops;
+ vec<loop_p, va_gc> *superloops;
/* The first inner (child) loop or NULL if innermost loop. */
struct loop *inner;
/* Auxiliary info specific to a pass. */
PTR GTY ((skip (""))) aux;
- /* The number of times the latch of the loop is executed.
- This is an INTEGER_CST or an expression containing symbolic
- names. Don't access this field directly:
- number_of_latch_executions computes and caches the computed
- information in this field. */
+ /* The number of times the latch of the loop is executed. This can be an
+ INTEGER_CST, or a symbolic expression representing the number of
+ iterations like "N - 1", or a COND_EXPR containing the runtime
+ conditions under which the number of iterations is non zero.
+
+ Don't access this field directly: number_of_latch_executions
+ computes and caches the computed information in this field. */
tree nb_iterations;
- /* An integer guaranteed to bound the number of iterations of the loop
- from above. */
- double_int nb_iterations_upper_bound;
+ /* An integer guaranteed to be greater or equal to nb_iterations. Only
+ valid if any_upper_bound is true. */
+ widest_int nb_iterations_upper_bound;
- /* An integer giving the expected number of iterations of the loop. */
- double_int nb_iterations_estimate;
+ /* An integer giving an estimate on nb_iterations. Unlike
+ nb_iterations_upper_bound, there is no guarantee that it is at least
+ nb_iterations. */
+ widest_int nb_iterations_estimate;
bool any_upper_bound;
bool any_estimate;
+ /* True if the loop can be parallel. */
+ bool can_be_parallel;
+
+ /* True if -Waggressive-loop-optimizations warned about this loop
+ already. */
+ bool warned_aggressive_loop_optimizations;
+
/* An integer estimation of the number of iterations. Estimate_state
describes what is the state of the estimation. */
enum loop_estimation estimate_state;
+ /* If > 0, an integer, where the user asserted that for any
+ I in [ 0, nb_iterations ) and for any J in
+ [ I, min ( I + safelen, nb_iterations ) ), the Ith and Jth iterations
+ of the loop can be safely evaluated concurrently. */
+ int safelen;
+
+ /* True if this loop should never be vectorized. */
+ bool dont_vectorize;
+
+ /* True if we should try harder to vectorize this loop. */
+ bool force_vectorize;
+
+ /* For SIMD loops, this is a unique identifier of the loop, referenced
+ by IFN_GOMP_SIMD_VF, IFN_GOMP_SIMD_LANE and IFN_GOMP_SIMD_LAST_LANE
+ builtins. */
+ tree simduid;
+
/* Upper bound on number of iterations of a loop. */
struct nb_iter_bound *bounds;
+ /* Non-overflow control ivs of a loop. */
+ struct control_iv *control_ivs;
+
/* Head of the cyclic list of the exits of the loop. */
struct loop_exit *exits;
- /* True if the loop can be parallel. */
- bool can_be_parallel;
+ /* Number of iteration analysis data for RTL. */
+ struct niter_desc *simple_loop_desc;
- /* The single induction variable of the loop when the loop is in
- normal form. */
- tree single_iv;
+ /* For sanity checking during loop fixup we record here the former
+ loop header for loops marked for removal. Note that this prevents
+ the basic-block from being collected but its index can still be
+ reused. */
+ basic_block former_header;
};
/* Flags for state of loop structure. */
int state;
/* Array of the loops. */
- VEC (loop_p, gc) *larray;
+ vec<loop_p, va_gc> *larray;
/* Maps edges to the list of their descriptions as loop exits. Edges
whose sources or destinations have loop_father == NULL (which may
happen during the cfg manipulations) should not appear in EXITS. */
- htab_t GTY((param_is (struct loop_exit))) exits;
+ hash_table<loop_exit_hasher> *GTY(()) exits;
/* Pointer to root of loop hierarchy tree. */
struct loop *tree_root;
};
/* Loop recognition. */
-extern int flow_loops_find (struct loops *);
+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 *,
struct loop *alloc_loop (void);
extern void flow_loop_free (struct loop *);
int flow_loop_nodes_find (basic_block, struct loop *);
-void fix_loop_structure (bitmap changed_bbs);
+unsigned fix_loop_structure (bitmap changed_bbs);
bool mark_irreducible_loops (void);
void release_recorded_exits (void);
void record_loop_exits (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 void add_loop (struct loop *, 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 unsigned tree_num_loop_insns (struct loop *, 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 is_loop_exit (struct loop *, basic_block);
+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);
/* Loops & cfg manipulation. */
extern basic_block *get_loop_body (const struct loop *);
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 *,
+extern basic_block *get_loop_body_in_custom_order (const struct loop *,
int (*) (const void *, const void *));
-extern VEC (edge, heap) *get_loop_exit_edges (const struct loop *);
-edge single_exit (const struct loop *);
+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 void cancel_loop_tree (struct loop *);
extern void delete_loop (struct loop *);
-enum
-{
- CP_SIMPLE_PREHEADERS = 1,
- CP_FALLTHRU_PREHEADERS = 2
-};
-
-basic_block create_preheader (struct loop *, int);
-extern void create_preheaders (int);
-extern void force_single_succ_latches (void);
extern void verify_loop_structure (void);
extern unsigned expected_loop_iterations (const struct loop *);
extern rtx doloop_condition_get (rtx);
-void estimate_numbers_of_iterations_loop (struct loop *);
-HOST_WIDE_INT estimated_loop_iterations_int (struct loop *, bool);
-bool estimated_loop_iterations (struct loop *, bool, double_int *);
-
-/* Loop manipulation. */
-extern bool can_duplicate_loop_p (const 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 edge create_empty_if_region_on_edge (edge, tree);
-extern struct loop *create_empty_loop_on_edge (edge, tree, tree, tree, tree,
- tree *, tree *, struct loop *);
-extern struct loop * duplicate_loop (struct loop *, struct loop *);
-extern void duplicate_subloops (struct loop *, struct loop *);
-extern bool duplicate_loop_to_header_edge (struct loop *, edge,
- unsigned, sbitmap, edge,
- VEC (edge, heap) **, int);
-extern struct loop *loopify (edge, edge,
- basic_block, edge, edge, bool,
- unsigned, unsigned);
-struct loop * loop_version (struct loop *, void *,
- basic_block *, unsigned, unsigned, unsigned, bool);
-extern bool remove_path (edge);
-void scale_loop_frequencies (struct loop *, int, int);
+void mark_loop_for_removal (loop_p);
/* Induction variable analysis. */
see the description above). */
rtx base, step;
- /* The type of extend applied to it (SIGN_EXTEND, ZERO_EXTEND or UNKNOWN). */
- enum rtx_code extend;
+ /* The type of extend applied to it (IV_SIGN_EXTEND, IV_ZERO_EXTEND,
+ or IV_UNKNOWN_EXTEND). */
+ enum iv_extend_code extend;
/* Operations applied in the extended mode. */
rtx delta, mult;
/* The mode it is extended to. */
- enum machine_mode extend_mode;
+ machine_mode extend_mode;
/* The mode the variable iterates in. */
- enum machine_mode mode;
+ 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
+struct GTY(()) niter_desc
{
/* The edge out of the loop. */
edge out_edge;
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;
+ uint64_t niter;
/* Assumptions under that the rest of the information is valid. */
rtx assumptions;
bool signed_p;
/* The mode in that niter_expr should be computed. */
- enum machine_mode mode;
+ 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 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, rtx);
+extern bool biv_p (rtx_insn *, rtx);
extern void find_simple_exit (struct loop *, struct niter_desc *);
extern void iv_analysis_done (void);
static inline struct niter_desc *
simple_loop_desc (struct loop *loop)
{
- return (struct niter_desc *) loop->aux;
+ return loop->simple_loop_desc;
}
/* Accessors for the loop structures. */
-/* Returns the loop with index NUM from current_loops. */
+/* Returns the loop with index NUM from FNs loop tree. */
static inline struct loop *
-get_loop (unsigned num)
+get_loop (struct function *fn, unsigned num)
{
- return VEC_index (loop_p, current_loops->larray, 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_length (loop_p, loop->superloops);
+ return vec_safe_length (loop->superloops);
}
/* Returns the immediate superloop of LOOP, or NULL if LOOP is the outermost
static inline struct loop *
loop_outer (const struct loop *loop)
{
- unsigned n = VEC_length (loop_p, loop->superloops);
+ unsigned n = vec_safe_length (loop->superloops);
if (n == 0)
return NULL;
- return VEC_index (loop_p, loop->superloops, n - 1);
+ return (*loop->superloops)[n - 1];
}
-/* Returns the list of loops in current_loops. */
+/* Returns true if LOOP has at least one exit edge. */
-static inline VEC (loop_p, gc) *
-get_loops (void)
+static inline bool
+loop_has_exit_edges (const struct loop *loop)
{
- if (!current_loops)
+ return loop->exits->next->e != NULL;
+}
+
+/* Returns the list of loops in FN. */
+
+inline vec<loop_p, va_gc> *
+get_loops (struct function *fn)
+{
+ struct loops *loops = loops_for_fn (fn);
+ if (!loops)
return NULL;
- return current_loops->larray;
+ return loops->larray;
}
-/* Returns the number of loops in current_loops (including the removed
+/* Returns the number of loops in FN (including the removed
ones and the fake loop that forms the root of the loop tree). */
static inline unsigned
-number_of_loops (void)
+number_of_loops (struct function *fn)
{
- if (!current_loops)
+ struct loops *loops = loops_for_fn (fn);
+ if (!loops)
return 0;
- return VEC_length (loop_p, current_loops->larray);
+ return vec_safe_length (loops->larray);
}
/* Returns true if state of the loops satisfies all properties
/* The iterator for loops. */
-typedef struct
+struct loop_iterator
{
+ loop_iterator (loop_p *loop, unsigned flags);
+ ~loop_iterator ();
+
+ inline loop_p next ();
+
/* The list of loops to visit. */
- VEC(int,heap) *to_visit;
+ vec<int> to_visit;
/* The index of the actual loop. */
unsigned idx;
-} loop_iterator;
+};
-static inline void
-fel_next (loop_iterator *li, loop_p *loop)
+inline loop_p
+loop_iterator::next ()
{
int anum;
- while (VEC_iterate (int, li->to_visit, li->idx, anum))
+ while (this->to_visit.iterate (this->idx, &anum))
{
- li->idx++;
- *loop = get_loop (anum);
- if (*loop)
- return;
+ this->idx++;
+ loop_p loop = get_loop (cfun, anum);
+ if (loop)
+ return loop;
}
- VEC_free (int, heap, li->to_visit);
- *loop = NULL;
+ return NULL;
}
-static inline void
-fel_init (loop_iterator *li, loop_p *loop, unsigned flags)
+inline
+loop_iterator::loop_iterator (loop_p *loop, unsigned flags)
{
struct loop *aloop;
unsigned i;
int mn;
- li->idx = 0;
+ this->idx = 0;
if (!current_loops)
{
- li->to_visit = NULL;
+ this->to_visit.create (0);
*loop = NULL;
return;
}
- li->to_visit = VEC_alloc (int, heap, number_of_loops ());
+ this->to_visit.create (number_of_loops (cfun));
mn = (flags & LI_INCLUDE_ROOT) ? 0 : 1;
if (flags & LI_ONLY_INNERMOST)
{
- for (i = 0; VEC_iterate (loop_p, current_loops->larray, i, aloop); i++)
+ for (i = 0; vec_safe_iterate (current_loops->larray, i, &aloop); i++)
if (aloop != NULL
&& aloop->inner == NULL
&& aloop->num >= mn)
- VEC_quick_push (int, li->to_visit, aloop->num);
+ this->to_visit.quick_push (aloop->num);
}
else if (flags & LI_FROM_INNERMOST)
{
while (1)
{
if (aloop->num >= mn)
- VEC_quick_push (int, li->to_visit, aloop->num);
+ this->to_visit.quick_push (aloop->num);
if (aloop->next)
{
while (1)
{
if (aloop->num >= mn)
- VEC_quick_push (int, li->to_visit, aloop->num);
+ this->to_visit.quick_push (aloop->num);
if (aloop->inner != NULL)
aloop = aloop->inner;
}
}
- fel_next (li, loop);
+ *loop = this->next ();
}
-#define FOR_EACH_LOOP(LI, LOOP, FLAGS) \
- for (fel_init (&(LI), &(LOOP), FLAGS); \
- (LOOP); \
- fel_next (&(LI), &(LOOP)))
+inline
+loop_iterator::~loop_iterator ()
+{
+ this->to_visit.release ();
+}
-#define FOR_EACH_LOOP_BREAK(LI) \
- { \
- VEC_free (int, heap, (LI)->to_visit); \
- break; \
- }
+#define FOR_EACH_LOOP(LOOP, FLAGS) \
+ for (loop_iterator li(&(LOOP), FLAGS); \
+ (LOOP); \
+ (LOOP) = li.next ())
/* The properties of the target. */
+struct target_cfgloop {
+ /* Number of available registers. */
+ unsigned x_target_avail_regs;
+
+ /* Number of available registers that are call-clobbered. */
+ unsigned x_target_clobbered_regs;
+
+ /* Number of registers reserved for temporary expressions. */
+ unsigned x_target_res_regs;
+
+ /* The cost for register when there still is some reserve, but we are
+ approaching the number of available registers. */
+ unsigned x_target_reg_cost[2];
-extern unsigned target_avail_regs;
-extern unsigned target_res_regs;
-extern unsigned target_reg_cost [2];
-extern unsigned target_spill_cost [2];
+ /* The cost for register when we need to spill. */
+ 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)
/* Register pressure estimation for induction variable optimizations & loop
invariant motion. */
-extern unsigned estimate_reg_pressure_cost (unsigned, unsigned, bool);
+extern unsigned estimate_reg_pressure_cost (unsigned, unsigned, bool, bool);
extern void init_set_costs (void);
/* Loop optimizer initialization. */
extern void loop_optimizer_finalize (void);
/* Optimization passes. */
-extern void unswitch_loops (void);
-
enum
{
- UAP_PEEL = 1, /* Enables loop peeling. */
- UAP_UNROLL = 2, /* Enables unrolling of loops if it seems profitable. */
- UAP_UNROLL_ALL = 4 /* Enables unrolling of all loops. */
+ UAP_UNROLL = 1, /* Enables unrolling of loops if it seems profitable. */
+ UAP_UNROLL_ALL = 2 /* Enables unrolling of all loops. */
};
-extern void unroll_and_peel_loops (int);
extern void doloop_optimize_loops (void);
extern void move_loop_invariants (void);
-extern bool finite_loop_p (struct loop *);
+extern vec<basic_block> get_loop_hot_path (const struct loop *loop);
+
+/* Returns the outermost loop of the loop nest that contains 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);
+
+/* Converts VAL to widest_int. */
+
+static inline widest_int
+gcov_type_to_wide_int (gcov_type val)
+{
+ HOST_WIDE_INT a[2];
+
+ a[0] = (unsigned HOST_WIDE_INT) val;
+ /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
+ the size of type. */
+ val >>= HOST_BITS_PER_WIDE_INT - 1;
+ val >>= 1;
+ a[1] = (unsigned HOST_WIDE_INT) val;
+
+ return widest_int::from_array (a, 2);
+}
#endif /* GCC_CFGLOOP_H */