Data Structures
struct	biv_entry
struct	biv_entry_hasher

Enumerations
enum	iv_grd_result { GRD_INVALID, GRD_INVARIANT, GRD_MAYBE_BIV, GRD_SINGLE_DOM }

Functions
static bool	iv_analyze_op (rtx, rtx, struct rtx_iv *)
static enum rtx_code	iv_extend_to_rtx_code ()
void	dump_iv_info (FILE , struct rtx_iv )
void	dump_iv_info ()
rtx	lowpart_subreg (enum machine_mode outer_mode, rtx expr, enum machine_mode inner_mode)
static void	check_iv_ref_table_size ()
static bool	simple_reg_p ()
static void	clear_iv_info ()
void	iv_analysis_loop_init ()
static bool	latch_dominating_def ()
static enum iv_grd_result	iv_get_reaching_def ()
static bool	iv_constant ()
static bool	iv_subreg ()
static bool	iv_extend ()
static bool	iv_neg ()
static bool	iv_add ()
static bool	iv_mult ()
static bool	iv_shift ()
static bool	get_biv_step_1 (df_ref def, rtx reg, rtx inner_step, enum machine_mode inner_mode, enum iv_extend_code extend, enum machine_mode outer_mode, rtx outer_step)
static bool	get_biv_step (df_ref last_def, rtx reg, rtx inner_step, enum machine_mode inner_mode, enum iv_extend_code extend, enum machine_mode outer_mode, rtx *outer_step)
static void	record_iv ()
static bool	analyzed_for_bivness_p ()
static void	record_biv ()
static bool	iv_analyze_biv ()
bool	iv_analyze_expr ()
static bool	iv_analyze_def ()
static bool	iv_analyze_op ()
bool	iv_analyze ()
bool	iv_analyze_result ()
bool	biv_p ()
rtx	get_iv_value ()
void	iv_analysis_done ()
static unsigned HOST_WIDEST_INT	inverse ()
static int	altered_reg_used ()
static void	mark_altered ()
static bool	simple_rhs_p ()
static int	replace_single_def_regs ()
static bool	suitable_set_for_replacement ()
static void	replace_in_expr ()
static bool	implies_p ()
rtx	canon_condition ()
void	simplify_using_condition ()
static void	eliminate_implied_condition ()
static void	eliminate_implied_conditions ()
static void	simplify_using_initial_values ()
static void	shorten_into_mode (struct rtx_iv iv, enum machine_mode mode, enum rtx_code cond, bool signed_p, struct niter_desc desc)
static bool	canonicalize_iv_subregs (struct rtx_iv iv0, struct rtx_iv iv1, enum rtx_code cond, struct niter_desc *desc)
static unsigned HOST_WIDEST_INT	determine_max_iter ()
static void	iv_number_of_iterations (struct loop loop, rtx insn, rtx condition, struct niter_desc desc)
static void	check_simple_exit ()
void	find_simple_exit ()
struct niter_desc *	get_simple_loop_desc ()
void	free_simple_loop_desc ()

Variables
static bool	clean_slate = true
static unsigned int	iv_ref_table_size = 0
static struct rtx_iv **	iv_ref_table
static struct loop *	current_loop
static hash_table < biv_entry_hasher >	bivs

Enumeration Type Documentation

enum iv_grd_result

@verbatim

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/.

   This is a simple analysis of induction variables of the loop.  The major use
   is for determining the number of iterations of a loop for loop unrolling,
   doloop optimization and branch prediction.  The iv information is computed
   on demand.

   Induction variables are analyzed by walking the use-def chains.  When
   a basic induction variable (biv) is found, it is cached in the bivs
   hash table.  When register is proved to be a biv, its description
   is stored to DF_REF_DATA of the def reference.

   The analysis works always with one loop -- you must call
   iv_analysis_loop_init (loop) for it.  All the other functions then work with
   this loop.   When you need to work with another loop, just call
   iv_analysis_loop_init for it.  When you no longer need iv analysis, call
   iv_analysis_done () to clean up the memory.

   The available functions are:

   iv_analyze (insn, reg, iv): Stores the description of the induction variable
     corresponding to the use of register REG in INSN to IV.  Returns true if
     REG is an induction variable in INSN. false otherwise.
     If use of REG is not found in INSN, following insns are scanned (so that
     we may call this function on insn returned by get_condition).
   iv_analyze_result (insn, def, iv):  Stores to IV the description of the iv
     corresponding to DEF, which is a register defined in INSN.
   iv_analyze_expr (insn, rhs, mode, iv):  Stores to IV the description of iv
     corresponding to expression EXPR evaluated at INSN.  All registers used bu
     EXPR must also be used in INSN.

   Possible return values of iv_get_reaching_def.

Enumerator:

GRD_INVALID	More than one reaching def, or reaching def that does not dominate the use.
GRD_INVARIANT	The use is trivial invariant of the loop, i.e. is not changed inside the loop.
GRD_MAYBE_BIV	The use is reached by initial value and a value from the previous iteration.
GRD_SINGLE_DOM	The use has single dominating def.

Function Documentation

static int altered_reg_used ( )

static

   Checks whether register *REG is in set ALT.  Callback for for_each_rtx.

Referenced by canon_condition().

static bool analyzed_for_bivness_p ( )

static

   If DEF was already analyzed for bivness, store the description of the biv to
   IV and return true.  Otherwise return false.

bool biv_p ( )

   Checks whether definition of register REG in INSN is a basic induction
   variable.  IV analysis must have been initialized (via a call to
   iv_analysis_loop_init) for this function to produce a result.

References clean_slate, clear_iv_info(), df_finish_pass(), hash_table< Descriptor, Allocator >::dispose(), free(), and iv_ref_table_size.

rtx canon_condition ( )

   Canonicalizes COND so that

   (1) Ensure that operands are ordered according to
       swap_commutative_operands_p.
   (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
       for GE, GEU, and LEU.

           When cross-compiling, const_val might be sign-extended from
           BITS_PER_WORD to HOST_BITS_PER_WIDE_INT

References altered_reg_used(), const_true_rtx, exp(), for_each_rtx(), implies_p(), reversed_condition(), rtx_equal_p(), and simplify_replace_rtx().

static bool canonicalize_iv_subregs	(	struct rtx_iv *	iv0,
		struct rtx_iv *	iv1,
		enum rtx_code	cond,
		struct niter_desc *	desc
	)

static

   Transforms IV0 and IV1 compared by COND so that they are both compared as
   subregs of the same mode if possible (sometimes it is necessary to add
   some assumptions to DESC).

     If the ivs behave specially in the first iteration, or are
     added/multiplied after extending, we ignore them.

     If there is some extend, it must match signedness of the comparison.

     Values of both variables should be computed in the same mode.  These
     might indeed be different, if we have comparison like

     (compare (subreg:SI (iv0)) (subreg:SI (iv1)))

     and iv0 and iv1 are both ivs iterating in SI mode, but calculated
     in different modes.  This does not seem impossible to handle, but
     it hardly ever occurs in practice.

     The only exception is the case when one of operands is invariant.
     For example pentium 3 generates comparisons like
     (lt (subreg:HI (reg:SI)) 100).  Here we assign HImode to 100, but we
     definitely do not want this prevent the optimization.

     Check that both ivs belong to a range of a single mode.  If one of the
     operands is an invariant, we may need to shorten it into the common
     mode.

static void check_iv_ref_table_size ( )

static

References subreg_lowpart_p().

static void check_simple_exit ( )

static

   Checks whether E is a simple exit from LOOP and stores its description
   into DESC.

     It must belong directly to the loop.

     It must be tested (at least) once during any iteration.

     It must end in a simple conditional jump.

     Test whether the condition is suitable.

     Check that we are able to determine number of iterations and fill
     in information about it.

References niter_desc::assumptions, find_simple_exit(), niter_desc::infinite, iv_analysis_loop_init(), loop::simple_loop_desc, simple_loop_desc(), niter_desc::simple_p, and warning().

static void clear_iv_info ( )

static

   Clears the information about ivs stored in df.

References clean_slate, hash_table< Descriptor, Allocator >::create(), DF_DEFER_INSN_RESCAN, DF_EQ_NOTES, df_set_flags(), get_loop_body_in_dom_order(), and loop::num_nodes.

Referenced by biv_p().

static unsigned HOST_WIDEST_INT determine_max_iter ( )

static

   Tries to estimate the maximum number of iterations in LOOP, and return the
   result.  This function is called from iv_number_of_iterations with
   a number of fields in DESC already filled in.  OLD_NITER is the original
   expression for the number of iterations, before we tried to simplify it.

     We used to look for constant operand 0 of AND,
     but canonicalization should always make this impossible.

     We could use a binary search here, but for now improving the upper
     bound by just one eliminates one important corner case.

void dump_iv_info	(	FILE *	,
		struct rtx_iv *
	)

   Dumps information about IV to FILE.

void dump_iv_info ( )

static void eliminate_implied_condition ( )

static

   Use relationship between A and *B to eventually eliminate *B.
   OP is the operation we consider.

         If A implies *B, we may replace *B by true.

         If *B implies A, we may replace *B by false.

static void eliminate_implied_conditions ( )

static

   Eliminates the conditions in TAIL that are implied by HEAD.  OP is the
   operation we consider.

void find_simple_exit ( )

   Finds a simple exit of LOOP and stores its description into DESC.

                 Prefer constant iterations; the less the better.

                 Also if the actual exit may be infinite, while the old one
                 not, prefer the old one.

References ggc_free(), loop::simple_loop_desc, and simple_loop_desc().

void free_simple_loop_desc ( )

   Releases simple loop description for LOOP.

static bool get_biv_step	(	df_ref	last_def,
		rtx	reg,
		rtx *	inner_step,
		enum machine_mode *	inner_mode,
		enum iv_extend_code *	extend,
		enum machine_mode *	outer_mode,
		rtx *	outer_step
	)

static

   Gets the operation on register REG inside loop, in shape

   OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))

   If the operation cannot be described in this shape, return false.
   LAST_DEF is the definition of REG that dominates loop latch.

References hash_table< Descriptor, Allocator >::find_slot_with_hash(), biv_entry::iv, and biv_entry::regno.

static bool get_biv_step_1	(	df_ref	def,
		rtx	reg,
		rtx *	inner_step,
		enum machine_mode *	inner_mode,
		enum iv_extend_code *	extend,
		enum machine_mode	outer_mode,
		rtx *	outer_step
	)

static

   The recursive part of get_biv_step.  Gets the value of the single value
   defined by DEF wrto initial value of REG inside loop, in shape described
   at get_biv_step.

             ppc64 uses expressions like

             (set x:SI (plus:SI (subreg:SI y:DI) 1)).

             this is equivalent to

             (set x':DI (plus:DI y:DI 1))
             (set x:SI (subreg:SI (x':DI)).

             See comment in previous switch.

rtx get_iv_value ( )

   Calculates value of IV at ITERATION-th iteration.

     We would need to generate some if_then_else patterns, and so far
     it is not needed anywhere.

struct niter_desc* get_simple_loop_desc ( )

read

   Creates a simple loop description of LOOP if it was not computed
   already.

     At least desc->infinite is not always initialized by
     find_simple_loop_exit.

         Assume that no overflow happens and that the loop is finite.
         We already warned at the tree level if we ran optimizations there.

static bool implies_p ( )

static

   Checks whether A implies B.

     A < B implies A + 1 <= B.

     A < B or A > B imply A != B.  TODO: Likewise
     A + n < B implies A != B + n if neither wraps.

     For unsigned comparisons, A != 0 implies A > 0 and A >= 1.

     A != N is equivalent to A - (N + 1) <u -1.

         Avoid overflows.

     Likewise, A != N implies A - N > 0.

             Avoid overflows.

             Avoid overflows.

     A >s X, where X is positive, implies A <u Y, if Y is negative.

Referenced by canon_condition(), and simplify_using_condition().

static unsigned HOST_WIDEST_INT inverse ( )

static

   Computes inverse to X modulo (1 << MOD).

static bool iv_add ( )

static

   Evaluates addition or subtraction (according to OP) of IV1 to IV0.

     Extend the constant to extend_mode of the other operand if necessary.

     Handle addition of constant.

void iv_analysis_done ( void )

   Free the data for an induction variable analysis.

References function_invariant_p().

void iv_analysis_loop_init ( )

   Prepare the data for an induction variable analysis of a LOOP.

     Clear the information from the analysis of the previous loop.

     Get rid of the ud chains before processing the rescans.  Then add
     the problem back.

bool iv_analyze ( )

   Analyzes value VAL at INSN and stores the result to *IV.

     We must find the insn in that val is used, so that we get to UD chains.
     Since the function is sometimes called on result of get_condition,
     this does not necessarily have to be directly INSN; scan also the
     following insns.

static bool iv_analyze_biv ( )

static

   Determines whether DEF is a biv and if so, stores its description
   to *IV.

     Loop transforms base to es (base + inner_step) + outer_step,
     where es means extend of subreg between inner_mode and outer_mode.
     The corresponding induction variable is

     es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step

static bool iv_analyze_def ( )

static

   Analyzes iv DEF and stores the result to *IV.

bool iv_analyze_expr ( )

   Analyzes expression RHS used at INSN and stores the result to *IV.
   The mode of the induction variable is MODE.

static bool iv_analyze_op	(	rtx	,
		rtx	,
		struct rtx_iv *
	)

static

static bool iv_analyze_op ( )

static

   Analyzes operand OP of INSN and stores the result to *IV.

bool iv_analyze_result ( )

   Analyzes definition of DEF in INSN and stores the result to IV.

static bool iv_constant ( )

static

   Sets IV to invariant CST in MODE.  Always returns true (just for
   consistency with other iv manipulation functions that may fail).

static bool iv_extend ( )

static

   Evaluates application of EXTEND to MODE on IV.

     If iv is invariant, just calculate the new value.

References rtx_iv::base, rtx_iv::delta, rtx_iv::extend, rtx_iv::extend_mode, IV_UNKNOWN_EXTEND, rtx_iv::mult, simplify_gen_unary(), and rtx_iv::step.

static enum rtx_code iv_extend_to_rtx_code ( )

inlinestatic

   Return the RTX code corresponding to the IV extend code EXTEND.

static enum iv_grd_result iv_get_reaching_def ( )

static

   Gets definition of REG reaching its use in INSN and stores it to DEF.

     More than one reaching def.

     We do not handle setting only part of the register.

     The definition does not dominate the use.  This is still OK if
     this may be a use of a biv, i.e. if the def_bb dominates loop
     latch.

static bool iv_mult ( )

static

   Evaluates multiplication of IV by constant CST.

References rtx_iv::delta, rtx_iv::mult, and simplify_gen_binary().

static bool iv_neg ( )

static

   Evaluates negation of IV.

static void iv_number_of_iterations	(	struct loop *	loop,
		rtx	insn,
		rtx	condition,
		struct niter_desc *	desc
	)

static

   Computes number of iterations of the CONDITION in INSN in LOOP and stores
   the result into DESC.  Very similar to determine_number_of_iterations
   (basically its rtl version), complicated by things like subregs.

     The meaning of these assumptions is this:
     if !assumptions
       then the rest of information does not have to be valid
     if noloop_assumptions then the loop does not roll
     if infinite then this exit is never used

     The constant comparisons should be folded.

     We only handle integers or pointers.

     Check condition and normalize it.

     Handle extends.  This is relatively nontrivial, so we only try in some
     easy cases, when we can canonicalize the ivs (possibly by adding some
     assumptions) to shape subreg (base + i * step).  This function also fills
     in desc->mode and desc->signed_p.

     We can take care of the case of two induction variables chasing each other
     if the test is NE. I have never seen a loop using it, but still it is
     cool.

     This is either infinite loop or the one that ends immediately, depending
     on initial values.  Unswitching should remove this kind of conditions.

         Ignore loops of while (i-- < 10) type.

         We do not care about whether the step is power of two in this
         case.

     Some more condition normalization.  We must record some assumptions
     due to overflows.

           We want to take care only of non-sharp relationals; this is easy,
           as in cases the overflow would make the transformation unsafe
           the loop does not roll.  Seemingly it would make more sense to want
           to take care of sharp relationals instead, as NE is more similar to
           them, but the problem is that here the transformation would be more
           difficult due to possibly infinite loops.

           It will be useful to be able to tell the difference once more in
           LE -> NE reduction.

     Take care of trivially infinite loops.

                 Fill in the remaining fields somehow.

                 Fill in the remaining fields somehow.

     If we can we want to take care of NE conditions instead of size
     comparisons, as they are much more friendly (most importantly
     this takes care of special handling of loops with step 1).  We can
     do it if we first check that upper bound is greater or equal to
     lower bound, their difference is constant c modulo step and that
     there is not an overflow.

                 A special case.  We have transformed condition of type
                 for (i = 0; i < 4; i += 4)
                 into
                 for (i = 0; i <= 3; i += 4)
                 obviously if the test for overflow during that transformation
                 passed, we cannot overflow here.  Most importantly any
                 loop with sharp end condition and step 1 falls into this
                 category, so handling this case specially is definitely
                 worth the troubles.

             We perform the transformation always provided that it is not
             completely senseless.  This is OK, as we would need this assumption
             to determine the number of iterations anyway.

                 If the step is a power of two and the final value we have
                 computed overflows, the cycle is infinite.  Otherwise it
                 is nontrivial to compute the number of iterations.

             We are going to lose some information about upper bound on
             number of iterations in this step, so record the information
             here.

     Count the number of iterations.

         Everything we do here is just arithmetics modulo size of mode.  This
         makes us able to do more involved computations of number of iterations
         than in other cases.  First transform the condition into shape
         s * i <> c, with s positive.

         Let nsd (s, size of mode) = d.  If d does not divide c, the loop
         is infinite.  Otherwise, the number of iterations is
         (inverse(s/d) * (c/d)) mod (size of mode/d).

           Condition in shape a + s * i <= b
           We must know that b + s does not overflow and a <= b + s and then we
           can compute number of iterations as (b + s - a) / s.  (It might
           seem that we in fact could be more clever about testing the b + s
           overflow condition using some information about b - a mod s,
           but it was already taken into account during LE -> NE transform).

                 If s is power of 2, we know that the loop is infinite if
                 a % s <= b % s and b + s overflows.

             Condition in shape a <= b - s * i
             We must know that a - s does not overflow and a - s <= b and then
             we can again compute number of iterations as (b - (a - s)) / s.

                 If s is power of 2, we know that the loop is infinite if
                 a % s <= b % s and a - s overflows.

     Rerun the simplification.  Consider code (created by copying loop headers)

     i = 0;

     if (0 < n)
       {
         do
           {
             i++;
           } while (i < n);
       }

    The first pass determines that i = 0, the second pass uses it to eliminate
    noloop assumption.

         simplify_using_initial_values does a copy propagation on the registers
         in the expression for the number of iterations.  This prolongs life
         ranges of registers and increases register pressure, and usually
         brings no gain (and if it happens to do, the cse pass will take care
         of it anyway).  So prevent this behavior, unless it enabled us to
         derive that the number of iterations is a constant.

     Simplify the assumptions.

     Fallthru.

static bool iv_shift ( )

static

   Evaluates shift of IV by constant CST.

static bool iv_subreg ( )

static

   Evaluates application of subreg to MODE on IV.

     If iv is invariant, just calculate the new value.

static bool latch_dominating_def ( )

static

   Finds the definition of REG that dominates loop latch and stores
   it to DEF.  Returns false if there is not a single definition
   dominating the latch.  If REG has no definition in loop, DEF
   is set to NULL and true is returned.

         More than one reaching definition.

rtx lowpart_subreg	(	enum machine_mode	outer_mode,
		rtx	expr,
		enum machine_mode	inner_mode
	)

   Generates a subreg to get the least significant part of EXPR (in mode
   INNER_MODE) to OUTER_MODE.

static void mark_altered ( )

static

   Marks registers altered by EXPR in set ALT.

static void record_biv ( )

static

References rtx_iv::base, and dump_file.

static void record_iv ( )

static

   Records information that DEF is induction variable IV.

References dump_file, and print_rtl().

static void replace_in_expr ( )

static

   Using the data returned by suitable_set_for_replacement, replace DEST
   with SRC in *EXPR and return the new expression.  Also call
   replace_single_def_regs if the replacement changed something.

static int replace_single_def_regs ( )

static

   If REG has a single definition, replace it with its known value in EXPR.
   Callback for for_each_rtx.

static void shorten_into_mode	(	struct rtx_iv *	iv,
		enum machine_mode	mode,
		enum rtx_code	cond,
		bool	signed_p,
		struct niter_desc *	desc
	)

static

   Transforms invariant IV into MODE.  Adds assumptions based on the fact
   that IV occurs as left operands of comparison COND and its signedness
   is SIGNED_P to DESC.

static bool simple_reg_p ( )

static

   Checks whether REG is a well-behaved register.

static bool simple_rhs_p ( )

static

   Checks whether RHS is simple enough to process.

         Allow reg OP const and reg OP reg.

         Allow reg OP const.

void simplify_using_condition ( )

   Tries to use the fact that COND holds to simplify EXPR.  ALTERED is the
   set of altered regs.

     If some register gets altered later, we do not really speak about its
     value at the time of comparison.

     A proof by contradiction.  If *EXPR implies (not cond), *EXPR must
     be false.

     Similarly, If (not *EXPR) implies (not cond), *EXPR must be true.

     We would like to have some other tests here.  TODO.

References const_true_rtx, and implies_p().

static void simplify_using_initial_values ( )

static

   Simplifies *EXPR using initial values at the start of the LOOP.  If *EXPR
   is a list, its elements are assumed to be combined using OP.

                 Kill all call clobbered registers.

                     We can no longer use a condition that has been simplified
                     to a constant, and simplify_using_condition will abort if
                     we try.

                     Retry simplifications with this condition if either the
                     expression or the condition changed.

                 If we did not use this insn to make a replacement, any overlap
                 between stores in this insn and our expression will cause the
                 expression to become invalid.

                 Likewise for the conditions.

             If the expression now contains regs that have been altered, we
             can't return it to the caller.  However, it is still valid for
             further simplification, so keep searching to see if we can
             eventually turn it into a constant.

static bool suitable_set_for_replacement ( )

static

   A subroutine of simplify_using_initial_values, this function examines INSN
   to see if it contains a suitable set that we can use to make a replacement.
   If it is suitable, return true and set DEST and SRC to the lhs and rhs of
   the set; return false otherwise.

References const_true_rtx, and simplify_replace_rtx().

Variable Documentation

hash_table<biv_entry_hasher> bivs

static

   Bivs of the current loop.

bool clean_slate = true

static

Referenced by biv_p(), and clear_iv_info().

struct loop* current_loop

static

   The current loop.

struct rtx_iv** iv_ref_table

static

   Table of rtx_ivs indexed by the df_ref uid field.

unsigned int iv_ref_table_size = 0

static

Referenced by biv_p().

Data Structures

Enumerations

Functions

Variables

Enumeration Type Documentation

Function Documentation

Variable Documentation