/* Natural loop functions
- Copyright (C) 1987-2016 Free Software Foundation, Inc.
+ Copyright (C) 1987-2019 Free Software Foundation, Inc.
This file is part of GCC.
/* The structure describing a bound on number of iterations of a loop. */
-struct GTY ((chain_next ("%h.next"))) nb_iter_bound {
+class GTY ((chain_next ("%h.next"))) nb_iter_bound {
+public:
/* The statement STMT is executed at most ... */
gimple *stmt;
bool is_exit;
/* The next bound in the list. */
- struct nb_iter_bound *next;
+ class nb_iter_bound *next;
};
/* Description of the loop exit. */
static void remove (loop_exit *);
};
-typedef struct loop *loop_p;
+typedef class loop *loop_p;
/* An integer estimation of the number of iterations. Estimate_state
describes what is the state of the estimation. */
};
/* Structure to hold information for each natural loop. */
-struct GTY ((chain_next ("%h.next"))) loop {
- /* Index into loops array. */
+class GTY ((chain_next ("%h.next"))) loop {
+public:
+ /* Index into loops array. Note indices will never be reused after loop
+ is destroyed. */
int num;
/* Number of loop insns. */
vec<loop_p, va_gc> *superloops;
/* The first inner (child) loop or NULL if innermost loop. */
- struct loop *inner;
+ class loop *inner;
/* Link to the next (sibling) loop. */
- struct loop *next;
+ class loop *next;
/* Auxiliary info specific to a pass. */
PTR GTY ((skip (""))) aux;
valid if any_upper_bound is true. */
widest_int nb_iterations_upper_bound;
+ widest_int nb_iterations_likely_upper_bound;
+
/* 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;
+ /* Preferred vectorization factor for the loop if non-zero. */
+ int simdlen;
+
+ /* Constraints are generally set by consumers and affect certain
+ semantics of niter analyzer APIs. Currently the APIs affected are
+ number_of_iterations_exit* functions and their callers. One typical
+ use case of constraints is to vectorize possibly infinite loop:
+
+ 1) Compute niter->assumptions by calling niter analyzer API and
+ record it as possible condition for loop versioning.
+ 2) Clear buffered result of niter/scev analyzer.
+ 3) Set constraint LOOP_C_FINITE assuming the loop is finite.
+ 4) Analyze data references. Since data reference analysis depends
+ on niter/scev analyzer, the point is that niter/scev analysis
+ is done under circumstance of LOOP_C_FINITE constraint.
+ 5) Version the loop with niter->assumptions computed in step 1).
+ 6) Vectorize the versioned loop in which niter->assumptions is
+ checked to be true.
+ 7) Update constraints in versioned loops so that niter analyzer
+ in following passes can use it.
+
+ Note consumers are usually the loop optimizers and it is consumers'
+ responsibility to set/clear constraints correctly. Failing to do
+ that might result in hard to track down bugs in niter/scev consumers. */
+ unsigned constraints;
+
+ /* An integer estimation of the number of iterations. Estimate_state
+ describes what is the state of the estimation. */
+ ENUM_BITFIELD(loop_estimation) estimate_state : 8;
+
+ unsigned any_upper_bound : 1;
+ unsigned any_estimate : 1;
+ unsigned any_likely_upper_bound : 1;
+
+ /* True if the loop can be parallel. */
+ unsigned can_be_parallel : 1;
+
+ /* True if -Waggressive-loop-optimizations warned about this loop
+ already. */
+ unsigned warned_aggressive_loop_optimizations : 1;
+
/* True if this loop should never be vectorized. */
- bool dont_vectorize;
+ unsigned dont_vectorize : 1;
/* True if we should try harder to vectorize this loop. */
- bool force_vectorize;
+ unsigned force_vectorize : 1;
/* True if the loop is part of an oacc kernels region. */
- bool in_oacc_kernels_region;
+ unsigned in_oacc_kernels_region : 1;
+
+ /* The number of times to unroll the loop. 0 means no information given,
+ just do what we always do. A value of 1 means do not unroll the loop.
+ A value of USHRT_MAX means unroll with no specific unrolling factor.
+ Other values means unroll with the given unrolling factor. */
+ unsigned short unroll;
+
+ /* If this loop was inlined the main clique of the callee which does
+ not need remapping when copying the loop body. */
+ unsigned short owned_clique;
/* 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;
+ /* In loop optimization, it's common to generate loops from the original
+ loop. This field records the index of the original loop which can be
+ used to track the original loop from newly generated loops. This can
+ be done by calling function get_loop (cfun, orig_loop_num). Note the
+ original loop could be destroyed for various reasons thus no longer
+ exists, as a result, function call to get_loop returns NULL pointer.
+ In this case, this field should not be used and needs to be cleared
+ whenever possible. */
+ int orig_loop_num;
+
/* Upper bound on number of iterations of a loop. */
- struct nb_iter_bound *bounds;
+ class nb_iter_bound *bounds;
/* Non-overflow control ivs of a loop. */
struct control_iv *control_ivs;
struct loop_exit *exits;
/* Number of iteration analysis data for RTL. */
- struct niter_desc *simple_loop_desc;
+ class niter_desc *simple_loop_desc;
/* For sanity checking during loop fixup we record here the former
loop header for loops marked for removal. Note that this prevents
basic_block former_header;
};
+/* Set if the loop is known to be infinite. */
+#define LOOP_C_INFINITE (1 << 0)
+/* Set if the loop is known to be finite without any assumptions. */
+#define LOOP_C_FINITE (1 << 1)
+
+/* Set C to the LOOP constraint. */
+static inline void
+loop_constraint_set (class loop *loop, unsigned c)
+{
+ loop->constraints |= c;
+}
+
+/* Clear C from the LOOP constraint. */
+static inline void
+loop_constraint_clear (class loop *loop, unsigned c)
+{
+ loop->constraints &= ~c;
+}
+
+/* Check if C is set in the LOOP constraint. */
+static inline bool
+loop_constraint_set_p (class loop *loop, unsigned c)
+{
+ return (loop->constraints & c) == c;
+}
+
/* Flags for state of loop structure. */
enum
{
hash_table<loop_exit_hasher> *GTY(()) exits;
/* Pointer to root of loop hierarchy tree. */
- struct loop *tree_root;
+ class loop *tree_root;
};
/* Loop recognition. */
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 *);
+ void (*)(const class loop *, FILE *, int), int);
+extern void flow_loop_dump (const class loop *, FILE *,
+ void (*)(const class loop *, FILE *, int), int);
+class loop *alloc_loop (void);
+extern void flow_loop_free (class loop *);
+int flow_loop_nodes_find (basic_block, class loop *);
unsigned fix_loop_structure (bitmap changed_bbs);
bool mark_irreducible_loops (void);
void release_recorded_exits (function *);
void record_loop_exits (void);
void rescan_loop_exit (edge, bool, bool);
+void sort_sibling_loops (function *);
/* 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 void flow_loop_tree_node_add (class loop *, class loop *,
+ class loop * = NULL);
+extern void flow_loop_tree_node_remove (class loop *);
+extern bool flow_loop_nested_p (const class loop *, const class loop *);
+extern bool flow_bb_inside_loop_p (const class loop *, const_basic_block);
+extern class loop * find_common_loop (class loop *, class loop *);
+class loop *superloop_at_depth (class loop *, unsigned);
struct eni_weights;
-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 int num_loop_insns (const class loop *);
+extern int average_num_loop_insns (const class loop *);
+extern unsigned get_loop_level (const class loop *);
+extern bool loop_exit_edge_p (const class loop *, const_edge);
+extern bool loop_exits_to_bb_p (class loop *, basic_block);
+extern bool loop_exits_from_bb_p (class loop *, basic_block);
extern void mark_loop_exit_edges (void);
-extern location_t get_loop_location (struct loop *loop);
+extern dump_user_location_t get_loop_location (class loop *loop);
/* Loops & cfg manipulation. */
-extern basic_block *get_loop_body (const struct loop *);
-extern unsigned get_loop_body_with_size (const struct loop *, basic_block *,
+extern basic_block *get_loop_body (const class loop *);
+extern unsigned get_loop_body_with_size (const class 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 *,
+extern basic_block *get_loop_body_in_dom_order (const class loop *);
+extern basic_block *get_loop_body_in_bfs_order (const class loop *);
+extern basic_block *get_loop_body_in_custom_order (const class 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 vec<edge> get_loop_exit_edges (const class loop *);
+extern edge single_exit (const class loop *);
+extern edge single_likely_exit (class loop *loop);
+extern unsigned num_loop_branches (const class loop *);
-extern edge loop_preheader_edge (const struct loop *);
-extern edge loop_latch_edge (const struct loop *);
+extern edge loop_preheader_edge (const class loop *);
+extern edge loop_latch_edge (const class loop *);
-extern void add_bb_to_loop (basic_block, struct loop *);
+extern void add_bb_to_loop (basic_block, class loop *);
extern void remove_bb_from_loops (basic_block);
-extern void cancel_loop_tree (struct loop *);
-extern void delete_loop (struct loop *);
+extern void cancel_loop_tree (class loop *);
+extern void delete_loop (class loop *);
extern void verify_loop_structure (void);
-/* Check loop structure invariants, if internal consistency checks are
- enabled. */
-
-static inline void
-checking_verify_loop_structure (void)
-{
- if (flag_checking)
- verify_loop_structure ();
-}
-
/* Loop analysis. */
-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);
+extern bool just_once_each_iteration_p (const class loop *, const_basic_block);
+gcov_type expected_loop_iterations_unbounded (const class loop *,
+ bool *read_profile_p = NULL, bool by_profile_only = false);
+extern unsigned expected_loop_iterations (class loop *);
+extern rtx doloop_condition_get (rtx_insn *);
void mark_loop_for_removal (loop_p);
computation is done, which would enable it to be different from the
outer one? */
-struct rtx_iv
+class rtx_iv
{
+public:
/* Its base and step (mode of base and step is supposed to be extend_mode,
see the description above). */
rtx base, step;
rtx delta, mult;
/* The mode it is extended to. */
- machine_mode extend_mode;
+ scalar_int_mode extend_mode;
/* The mode the variable iterates in. */
- machine_mode mode;
+ scalar_int_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 GTY(()) niter_desc
+class GTY(()) niter_desc
{
+public:
/* The edge out of the loop. */
edge out_edge;
bool signed_p;
/* The mode in that niter_expr should be computed. */
- machine_mode mode;
+ scalar_int_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_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_loop_init (class loop *);
+extern bool iv_analyze (rtx_insn *, scalar_int_mode, rtx, class rtx_iv *);
+extern bool iv_analyze_result (rtx_insn *, rtx, class rtx_iv *);
+extern bool iv_analyze_expr (rtx_insn *, scalar_int_mode, rtx,
+ class rtx_iv *);
+extern rtx get_iv_value (class rtx_iv *, rtx);
+extern bool biv_p (rtx_insn *, scalar_int_mode, rtx);
+extern void find_simple_exit (class loop *, class 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);
+extern class niter_desc *get_simple_loop_desc (class loop *loop);
+extern void free_simple_loop_desc (class loop *loop);
-static inline struct niter_desc *
-simple_loop_desc (struct loop *loop)
+static inline class niter_desc *
+simple_loop_desc (class loop *loop)
{
return loop->simple_loop_desc;
}
/* Returns the loop with index NUM from FNs loop tree. */
-static inline struct loop *
+static inline class 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)
+loop_depth (const class loop *loop)
{
return vec_safe_length (loop->superloops);
}
/* Returns the immediate superloop of LOOP, or NULL if LOOP is the outermost
loop. */
-static inline struct loop *
-loop_outer (const struct loop *loop)
+static inline class loop *
+loop_outer (const class loop *loop)
{
unsigned n = vec_safe_length (loop->superloops);
/* Returns true if LOOP has at least one exit edge. */
static inline bool
-loop_has_exit_edges (const struct loop *loop)
+loop_has_exit_edges (const class loop *loop)
{
return loop->exits->next->e != NULL;
}
loops_state_clear (cfun, flags);
}
+/* Check loop structure invariants, if internal consistency checks are
+ enabled. */
+
+static inline void
+checking_verify_loop_structure (void)
+{
+ /* VERIFY_LOOP_STRUCTURE essentially asserts that no loops need fixups.
+
+ The loop optimizers should never make changes to the CFG which
+ require loop fixups. But the low level CFG manipulation code may
+ set the flag conservatively.
+
+ Go ahead and clear the flag here. That avoids the assert inside
+ VERIFY_LOOP_STRUCTURE, and if there is an inconsistency in the loop
+ structures VERIFY_LOOP_STRUCTURE will detect it.
+
+ This also avoid the compile time cost of excessive fixups. */
+ loops_state_clear (LOOPS_NEED_FIXUP);
+ if (flag_checking)
+ verify_loop_structure ();
+}
+
/* Loop iterators. */
/* Flags for loop iteration. */
/* The iterator for loops. */
-struct loop_iterator
+class loop_iterator
{
+public:
loop_iterator (function *fn, loop_p *loop, unsigned flags);
~loop_iterator ();
inline
loop_iterator::loop_iterator (function *fn, loop_p *loop, unsigned flags)
{
- struct loop *aloop;
+ class loop *aloop;
unsigned i;
int mn;
(LOOP) = li.next ())
#define FOR_EACH_LOOP_FN(FN, LOOP, FLAGS) \
- for (loop_iterator li(fn, &(LOOP), FLAGS); \
+ for (loop_iterator li(FN, &(LOOP), FLAGS); \
(LOOP); \
(LOOP) = li.next ())
extern void doloop_optimize_loops (void);
extern void move_loop_invariants (void);
-extern vec<basic_block> get_loop_hot_path (const struct loop *loop);
+extern vec<basic_block> get_loop_hot_path (const class loop *loop);
/* Returns the outermost loop of the loop nest that contains LOOP.*/
-static inline struct loop *
-loop_outermost (struct loop *loop)
+static inline class loop *
+loop_outermost (class loop *loop)
{
unsigned n = vec_safe_length (loop->superloops);
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 void record_niter_bound (class loop *, const widest_int &, bool, bool);
+extern HOST_WIDE_INT get_estimated_loop_iterations_int (class loop *);
+extern HOST_WIDE_INT get_max_loop_iterations_int (const class loop *);
+extern HOST_WIDE_INT get_likely_max_loop_iterations_int (class loop *);
+extern bool get_estimated_loop_iterations (class loop *loop, widest_int *nit);
+extern bool get_max_loop_iterations (const class loop *loop, widest_int *nit);
+extern bool get_likely_max_loop_iterations (class loop *loop, widest_int *nit);
extern int bb_loop_depth (const_basic_block);
/* Converts VAL to widest_int. */
projects / thirdparty / gcc.git / blobdiff