blob: 1d845729e5ea3b046c391579bf394ad39726df82 [file] [log] [blame]
/* Natural loop functions
Copyright (C) 1987-2015 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 3, 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 COPYING3. If not see
<http://www.gnu.org/licenses/>. */
#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"
/* Structure to hold decision about unrolling/peeling. */
enum lpt_dec
{
LPT_NONE,
LPT_UNROLL_CONSTANT,
LPT_UNROLL_RUNTIME,
LPT_UNROLL_STUPID
};
struct GTY (()) lpt_decision {
enum lpt_dec decision;
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 {
/* The statement STMT is executed at most ... */
gimple stmt;
/* ... BOUND + 1 times (BOUND must be an unsigned constant).
The + 1 is added for the following reasons:
a) 0 would otherwise be unused, while we would need to care more about
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. */
widest_int bound;
/* 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;
/* The next bound in the list. */
struct nb_iter_bound *next;
};
/* Description of the loop exit. */
struct GTY ((for_user)) loop_exit {
/* The exit edge. */
edge e;
/* Previous and next exit in the list of the exits of the loop. */
struct loop_exit *prev;
struct loop_exit *next;
/* Next element in the list of loops from that E exits. */
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;
/* An integer estimation of the number of iterations. Estimate_state
describes what is the state of the estimation. */
enum loop_estimation
{
/* Estimate was not computed yet. */
EST_NOT_COMPUTED,
/* Estimate is ready. */
EST_AVAILABLE,
EST_LAST
};
/* Structure to hold information for each natural loop. */
struct GTY ((chain_next ("%h.next"))) loop {
/* Index into loops array. */
int num;
/* Number of loop insns. */
unsigned ninsns;
/* 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;
/* Average number of executed insns per iteration. */
unsigned av_ninsns;
/* Number of blocks contained within the loop. */
unsigned num_nodes;
/* Superloops of the loop, starting with the outermost loop. */
vec<loop_p, va_gc> *superloops;
/* The first inner (child) loop or NULL if innermost loop. */
struct loop *inner;
/* Link to the next (sibling) loop. */
struct loop *next;
/* Auxiliary info specific to a pass. */
PTR GTY ((skip (""))) aux;
/* 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 be greater or equal to nb_iterations. Only
valid if any_upper_bound is true. */
widest_int nb_iterations_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;
/* 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;
/* Head of the cyclic list of the exits of the loop. */
struct loop_exit *exits;
/* Number of iteration analysis data for RTL. */
struct 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
the basic-block from being collected but its index can still be
reused. */
basic_block former_header;
};
/* Flags for state of loop structure. */
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)
/* Structure to hold CFG information about natural loops within a function. */
struct GTY (()) loops {
/* State of loops. */
int state;
/* Array of the loops. */
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. */
hash_table<loop_exit_hasher> *GTY(()) exits;
/* Pointer to root of loop hierarchy tree. */
struct loop *tree_root;
};
/* Loop recognition. */
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);
/* 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);
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);
/* Loops & cfg manipulation. */
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);
/* 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);
void mark_loop_for_removal (loop_p);
/* 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 (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. */
machine_mode extend_mode;
/* The mode the variable iterates in. */
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 GTY(()) 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. */
uint64_t niter;
/* 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. */
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_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;
}
/* Accessors for the loop structures. */
/* Returns the loop with index NUM from FNs loop tree. */
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);
}
/* Returns the immediate superloop of LOOP, or NULL if LOOP is the outermost
loop. */
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];
}
/* Returns true if LOOP has at least one exit edge. */
static inline bool
loop_has_exit_edges (const struct loop *loop)
{
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 loops->larray;
}
/* 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 (struct function *fn)
{
struct loops *loops = loops_for_fn (fn);
if (!loops)
return 0;
return vec_safe_length (loops->larray);
}
/* Returns true if state of the loops satisfies all properties
described by FLAGS. */
static inline bool
loops_state_satisfies_p (unsigned flags)
{
return (current_loops->state & flags) == flags;
}
/* Sets FLAGS to the loops state. */
static inline void
loops_state_set (unsigned flags)
{
current_loops->state |= flags;
}
/* Clears FLAGS from the loops state. */
static inline void
loops_state_clear (unsigned flags)
{
if (!current_loops)
return;
current_loops->state &= ~flags;
}
/* Loop iterators. */
/* Flags for loop iteration. */
enum li_flags
{
LI_INCLUDE_ROOT = 1, /* Include the fake root of the loop tree. */
LI_FROM_INNERMOST = 2, /* Iterate over the loops in the reverse order,
starting from innermost ones. */
LI_ONLY_INNERMOST = 4 /* Iterate only over innermost loops. */
};
/* The iterator for loops. */
struct loop_iterator
{
loop_iterator (loop_p *loop, unsigned flags);
~loop_iterator ();
inline loop_p next ();
/* The list of loops to visit. */
vec<int> to_visit;
/* The index of the actual loop. */
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)
{
/* Push the loops to LI->TO_VISIT in postorder. */
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
{
/* Push the loops to LI->TO_VISIT in preorder. */
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 ())
/* 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];
/* 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, bool);
extern void init_set_costs (void);
/* Loop optimizer initialization. */
extern void loop_optimizer_init (unsigned);
extern void loop_optimizer_finalize (void);
/* Optimization passes. */
enum
{
UAP_UNROLL = 1, /* Enables unrolling of loops if it seems profitable. */
UAP_UNROLL_ALL = 2 /* Enables unrolling of all loops. */
};
extern void doloop_optimize_loops (void);
extern void move_loop_invariants (void);
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 */