#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "df.h"
#include "memmodel.h"
#include "emit-rtl.h"
#include "diagnostic-core.h"
#include "cfgloop.h"
#include "intl.h"
#include "dumpfile.h"
#include "rtl-iter.h"
#include "tree-ssa-loop-niter.h"
#include "regs.h"
#include "function-abi.h"

Include dependency graph for loop-iv.cc:

Data Structures
class	biv_entry

struct	biv_entry_hasher

Macros
#define	DF_REF_IV(REF) iv_ref_table[DF_REF_ID (REF)]

#define	DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID (REF)] = (IV)

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

Functions
static bool	iv_analyze_op (rtx_insn , scalar_int_mode, rtx, class rtx_iv )

static enum rtx_code	iv_extend_to_rtx_code (enum iv_extend_code extend)

void	dump_iv_info (FILE , class rtx_iv )

static void	check_iv_ref_table_size (void)

static bool	simple_reg_p (rtx reg)

static void	clear_iv_info (void)

void	iv_analysis_loop_init (class loop *loop)

static bool	latch_dominating_def (rtx reg, df_ref *def)

static enum iv_grd_result	iv_get_reaching_def (rtx_insn insn, rtx reg, df_ref def)

static bool	iv_constant (class rtx_iv *iv, scalar_int_mode mode, rtx cst)

static bool	iv_subreg (class rtx_iv *iv, scalar_int_mode mode)

static bool	iv_extend (class rtx_iv *iv, enum iv_extend_code extend, scalar_int_mode mode)

static bool	iv_neg (class rtx_iv *iv)

static bool	iv_add (class rtx_iv iv0, class rtx_iv iv1, enum rtx_code op)

static bool	iv_mult (class rtx_iv *iv, rtx mby)

static bool	iv_shift (class rtx_iv *iv, rtx mby)

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

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

static void	record_iv (df_ref def, class rtx_iv *iv)

static bool	analyzed_for_bivness_p (rtx def, class rtx_iv *iv)

static void	record_biv (rtx def, class rtx_iv *iv)

static bool	iv_analyze_biv (scalar_int_mode outer_mode, rtx def, class rtx_iv *iv)

bool	iv_analyze_expr (rtx_insn insn, scalar_int_mode mode, rtx rhs, class rtx_iv iv)

static bool	iv_analyze_def (df_ref def, class rtx_iv *iv)

bool	iv_analyze (rtx_insn insn, scalar_int_mode mode, rtx val, class rtx_iv iv)

bool	iv_analyze_result (rtx_insn insn, rtx def, class rtx_iv iv)

bool	biv_p (rtx_insn *insn, scalar_int_mode mode, rtx reg)

rtx	get_iv_value (class rtx_iv *iv, rtx iteration)

void	iv_analysis_done (void)

static uint64_t	inverse (uint64_t x, int mod)

static bool	altered_reg_used (const_rtx x, bitmap alt)

static void	mark_altered (rtx expr, const_rtx by, void *alt)

static bool	simple_rhs_p (rtx rhs)

static void	replace_single_def_regs (rtx *expr)

static bool	suitable_set_for_replacement (rtx_insn insn, rtx dest, rtx *src)

static void	replace_in_expr (rtx *expr, rtx dest, rtx src)

static bool	implies_p (rtx a, rtx b)

rtx	canon_condition (rtx cond)

static rtx	reversed_condition (rtx cond)

void	simplify_using_condition (rtx cond, rtx *expr, regset altered)

static void	eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)

static void	eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)

static void	simplify_using_initial_values (class loop loop, enum rtx_code op, rtx expr)

static void	shorten_into_mode (class rtx_iv iv, scalar_int_mode mode, enum rtx_code cond, bool signed_p, class niter_desc desc)

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

static uint64_t	determine_max_iter (class loop loop, class niter_desc desc, rtx old_niter)

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

static void	check_simple_exit (class loop loop, edge e, class niter_desc desc)

static void	find_simple_exit (class loop loop, class niter_desc desc)

class niter_desc *	get_simple_loop_desc (class loop *loop)

void	free_simple_loop_desc (class loop *loop)

Variables
static bool	clean_slate = true

static unsigned int	iv_ref_table_size = 0

static class rtx_iv **	iv_ref_table

static class loop *	current_loop

static hash_table< biv_entry_hasher > *	bivs

Macro Definition Documentation

◆ DF_REF_IV

#define DF_REF_IV ( REF ) iv_ref_table[DF_REF_ID (REF)]

Induction variable stored at the reference.

Referenced by iv_analyze_def().

◆ DF_REF_IV_SET

#define DF_REF_IV_SET	(		REF,
			IV ) iv_ref_table[DF_REF_ID (REF)] = (IV)

Referenced by record_iv().

Enumeration Type Documentation

◆ iv_grd_result

enum iv_grd_result

Rtl-level induction variable analysis.
   Copyright (C) 2004-2024 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/>.

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, mode, reg, iv): Stores the description of the induction
    variable corresponding to the use of register REG in INSN to IV, given
    that REG has mode MODE.  Returns true if REG is an induction variable
    in INSN. false otherwise.  If a use of REG is not found in INSN,
    the following insns are scanned (so that we may call this function
    on insns 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, mode, expr, iv):  Stores to IV the description of iv
    corresponding to expression EXPR evaluated at INSN.  All registers used by
    EXPR must also be used in INSN.  MODE is the mode of EXPR.

Possible return values of iv_get_reaching_def.

Enumerator
GRD_INVALID
GRD_INVARIANT
GRD_MAYBE_BIV
GRD_SINGLE_DOM

Function Documentation

◆ altered_reg_used()

static bool altered_reg_used	(	const_rtx	x,
		bitmap	alt )

static

Checks whether any register in X is in set ALT.

References FOR_EACH_SUBRTX, ggc_alloc(), REG_P, REGNO, and REGNO_REG_SET_P.

Referenced by simplify_using_condition(), and simplify_using_initial_values().

◆ analyzed_for_bivness_p()

static bool analyzed_for_bivness_p	(	rtx	def,
		class rtx_iv *	iv )

static

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

References bivs, ggc_alloc(), and REGNO.

Referenced by iv_analyze_biv().

◆ biv_p()

bool biv_p	(	rtx_insn *	insn,
		scalar_int_mode	mode,
		rtx	reg )

Checks whether definition of register REG in INSN is a basic induction
variable.  MODE is the mode of REG.

IV analysis must have been initialized (via a call to
iv_analysis_loop_init) for this function to produce a result.

References const0_rtx, df_find_def(), gcc_assert, ggc_alloc(), iv_analyze_biv(), latch_dominating_def(), rtx_iv::mode, NULL, simple_reg_p(), and iv::step.

Referenced by analyze_iv_to_split_insn().

◆ canon_condition()

rtx canon_condition ( rtx cond )

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.

References wi::add(), CONST_SCALAR_INT_P, const_val, gcc_assert, GET_CODE, GET_MODE, GET_MODE_CLASS, ggc_alloc(), immed_wide_int_const(), wi::max_value(), wi::min_value(), rtx_iv::mode, wi::ne_p(), SIGNED, wi::sub(), swap_commutative_operands_p(), swap_condition(), and XEXP.

Referenced by simplify_using_condition().

◆ canonicalize_iv_subregs()

static bool canonicalize_iv_subregs	(	class rtx_iv *	iv0,
		class rtx_iv *	iv1,
		enum rtx_code	cond,
		class 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).

References const0_rtx, const1_rtx, gcc_unreachable, GET_MODE_BITSIZE(), ggc_alloc(), IV_SIGN_EXTEND, IV_UNKNOWN_EXTEND, IV_ZERO_EXTEND, niter_desc::mode, shorten_into_mode(), niter_desc::signed_p, simplify_gen_unary(), and swap_condition().

Referenced by iv_number_of_iterations().

◆ check_iv_ref_table_size()

static void check_iv_ref_table_size ( void )

static

References DF_DEFS_TABLE_SIZE, ggc_alloc(), iv_ref_table, and iv_ref_table_size.

Referenced by clear_iv_info(), iv_analysis_loop_init(), iv_analyze_def(), and record_iv().

◆ check_simple_exit()

static void check_simple_exit	(	class loop *	loop,
		edge	e,
		class niter_desc *	desc )

static

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

References any_condjump_p(), BB_END, CDI_DOMINATORS, dominated_by_p(), EDGE_SUCC, get_condition(), ggc_alloc(), niter_desc::in_edge, iv_number_of_iterations(), loop::latch, basic_block_def::loop_father, onlyjump_p(), niter_desc::out_edge, reversed_condition(), and niter_desc::simple_p.

Referenced by find_simple_exit().

◆ clear_iv_info()

static void clear_iv_info ( void )

static

Clears the information about ivs stored in df.

References bivs, check_iv_ref_table_size(), DF_DEFS_TABLE_SIZE, free(), ggc_alloc(), i, iv_ref_table, and NULL.

Referenced by iv_analysis_done(), and iv_analysis_loop_init().

◆ determine_max_iter()

static uint64_t determine_max_iter	(	class loop *	loop,
		class niter_desc *	desc,
		rtx	old_niter )

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.

References CONST_INT_P, const_true_rtx, dump_file, gcc_checking_assert, GET_CODE, get_mode_bounds(), ggc_alloc(), INTVAL, MIN, niter_desc::mode, niter_desc::niter_expr, PRId64, niter_desc::signed_p, simplify_gen_relational(), simplify_using_initial_values(), UINTVAL, and XEXP.

Referenced by iv_number_of_iterations().

◆ dump_iv_info()

void dump_iv_info	(	FILE *	file,
		class rtx_iv *	iv )

extern

Dumps information about IV to FILE.

References iv::base, const0_rtx, const1_rtx, GET_MODE_NAME, ggc_alloc(), iv_extend_to_rtx_code(), print_rtl(), rtx_name, and iv::step.

Referenced by iv_analyze_biv(), iv_analyze_def(), and iv_analyze_op().

◆ eliminate_implied_condition()

static void eliminate_implied_condition	(	enum rtx_code	op,
		rtx	a,
		rtx *	b )

static

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

References a, b, const0_rtx, const_true_rtx, gcc_unreachable, ggc_alloc(), and implies_p().

Referenced by eliminate_implied_conditions().

◆ eliminate_implied_conditions()

static void eliminate_implied_conditions	(	enum rtx_code	op,
		rtx *	head,
		rtx	tail )

static

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

References eliminate_implied_condition(), and XEXP.

Referenced by simplify_using_initial_values().

◆ find_simple_exit()

static void find_simple_exit	(	class loop *	loop,
		class niter_desc *	desc )

static

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

References niter_desc::assumptions, check_simple_exit(), niter_desc::const_iter, dump_file, finite_loop_p(), flow_bb_inside_loop_p(), FOR_EACH_EDGE, free(), get_estimated_loop_iterations_int(), get_likely_max_loop_iterations_int(), get_loop_body(), get_max_loop_iterations_int(), ggc_alloc(), i, niter_desc::infinite, niter_desc::niter, niter_desc::niter_expr, niter_desc::noloop_assumptions, NULL_RTX, loop::num, loop::num_nodes, niter_desc::out_edge, print_rtl(), niter_desc::simple_p, and single_exit().

Referenced by get_simple_loop_desc().

◆ free_simple_loop_desc()

void free_simple_loop_desc ( class loop * loop )

Releases simple loop description for LOOP.

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

Referenced by loop_optimizer_finalize().

◆ get_biv_step()

static bool get_biv_step	(	df_ref	last_def,
		scalar_int_mode	outer_mode,
		rtx	reg,
		rtx *	inner_step,
		scalar_int_mode *	inner_mode,
		enum iv_extend_code *	extend,
		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 const0_rtx, gcc_assert, get_biv_step_1(), ggc_alloc(), and IV_UNKNOWN_EXTEND.

Referenced by iv_analyze_biv().

◆ get_biv_step_1()

static bool get_biv_step_1	(	df_ref	def,
		scalar_int_mode	outer_mode,
		rtx	reg,
		rtx *	inner_step,
		scalar_int_mode *	inner_mode,
		enum iv_extend_code *	extend,
		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.

References const0_rtx, CONSTANT_P, DF_REF_INSN, find_reg_equal_equiv_note(), gcc_assert, get_biv_step_1(), GET_CODE, GET_MODE, GET_MODE_SIZE(), ggc_alloc(), GRD_INVALID, GRD_INVARIANT, GRD_MAYBE_BIV, iv_get_reaching_def(), IV_SIGN_EXTEND, IV_UNKNOWN_EXTEND, IV_ZERO_EXTEND, NULL_RTX, rtx_equal_p(), SET_SRC, simple_reg_p(), simplify_gen_binary(), single_set(), subreg_lowpart_p(), SUBREG_REG, and XEXP.

Referenced by get_biv_step(), and get_biv_step_1().

◆ get_iv_value()

rtx get_iv_value	(	class rtx_iv *	iv,
		rtx	iteration )

Calculates value of IV at ITERATION-th iteration.

References iv::base, const0_rtx, gcc_assert, ggc_alloc(), iv_extend_to_rtx_code(), IV_UNKNOWN_EXTEND, lowpart_subreg(), simplify_gen_binary(), simplify_gen_unary(), and iv::step.

Referenced by iv_extend(), and iv_subreg().

◆ get_simple_loop_desc()

class niter_desc * get_simple_loop_desc ( class loop * loop )

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

References find_simple_exit(), ggc_alloc(), iv_analysis_loop_init(), loop::simple_loop_desc, and simple_loop_desc().

Referenced by decide_unroll_constant_iterations(), decide_unroll_runtime_iterations(), decide_unroll_stupid(), doloop_optimize(), get_loop_location(), loop_exit_at_end_p(), unroll_loop_constant_iterations(), unroll_loop_runtime_iterations(), and unroll_loop_stupid().

◆ implies_p()

static bool implies_p	(	rtx	a,
		rtx	b )

static

Checks whether A implies B.

References a, b, const0_rtx, const1_rtx, CONST_INT_P, const_true_rtx, constm1_rtx, GET_CODE, GET_MODE, GET_RTX_CLASS, ggc_alloc(), HOST_BITS_PER_WIDE_INT, HOST_WIDE_INT_1U, INTVAL, rtx_iv::mode, r, REG_P, RTX_COMM_COMPARE, RTX_COMPARE, rtx_equal_p(), SCALAR_INT_MODE_P, simplify_gen_binary(), simplify_replace_rtx(), SUBREG_REG, and XEXP.

Referenced by eliminate_implied_condition(), and simplify_using_condition().

◆ inverse()

static uint64_t inverse	(	uint64_t	x,
		int	mod )

static

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

References ggc_alloc(), and i.

Referenced by iv_number_of_iterations(), and record_argument_state_1().

◆ iv_add()

static bool iv_add	(	class rtx_iv *	iv0,
		class rtx_iv *	iv1,
		enum rtx_code	op )

static

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

References const0_rtx, GET_MODE_SIZE(), ggc_alloc(), iv_neg(), IV_UNKNOWN_EXTEND, simplify_gen_binary(), and simplify_gen_unary().

Referenced by iv_analyze_expr().

◆ iv_analysis_done()

void iv_analysis_done ( void )

Free the data for an induction variable analysis.

References bivs, clean_slate, clear_iv_info(), df_finish_pass(), free(), iv_ref_table, iv_ref_table_size, and NULL.

Referenced by doloop_optimize_loops(), and unroll_loops().

◆ iv_analysis_loop_init()

void iv_analysis_loop_init ( class loop * loop )

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

References bivs, check_iv_ref_table_size(), clean_slate, clear_iv_info(), current_loop, df_analyze_loop(), df_chain, df_chain_add_problem(), DF_DEFER_INSN_RESCAN, df_dump_region(), DF_EQ_NOTES, df_note_add_problem(), df_process_deferred_rescans(), DF_RD_PRUNE_DEAD_DEFS, df_remove_problem(), df_set_flags(), DF_UD_CHAIN, dump_file, and ggc_alloc().

Referenced by analyze_insns_in_loop(), doloop_optimize(), and get_simple_loop_desc().

◆ iv_analyze()

bool iv_analyze	(	rtx_insn *	insn,
		scalar_int_mode	mode,
		rtx	val,
		class rtx_iv *	iv )

Analyzes value VAL at INSN and stores the result to *IV.  MODE is the
mode of VAL.

References df_find_use(), GET_CODE, ggc_alloc(), iv_analyze_op(), rtx_iv::mode, NEXT_INSN(), simple_reg_p(), and SUBREG_REG.

Referenced by iv_number_of_iterations().

◆ iv_analyze_biv()

static bool iv_analyze_biv	(	scalar_int_mode	outer_mode,
		rtx	def,
		class rtx_iv *	iv )

static

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

References analyzed_for_bivness_p(), iv::base, const1_rtx, CONSTANT_P, dump_file, dump_iv_info(), end(), get_biv_step(), ggc_alloc(), iv_constant(), latch_dominating_def(), NULL_RTX, print_rtl(), record_biv(), REG_P, simplify_gen_binary(), and iv::step.

Referenced by biv_p(), and iv_analyze_op().

◆ iv_analyze_def()

static bool iv_analyze_def	(	df_ref	def,
		class rtx_iv *	iv )

static

Analyzes iv DEF and stores the result to *IV.

References iv::base, check_iv_ref_table_size(), DF_REF_INSN, DF_REF_IV, DF_REF_REG, dump_file, dump_iv_info(), find_reg_equal_equiv_note(), gcc_assert, GET_MODE, ggc_alloc(), iv_analyze_expr(), rtx_iv::mode, NULL_RTX, print_rtl(), print_rtl_single(), record_iv(), REG_P, SET_DEST, SET_SRC, single_set(), iv::step, and XEXP.

Referenced by iv_analyze_op(), and iv_analyze_result().

◆ iv_analyze_expr()

bool iv_analyze_expr	(	rtx_insn *	insn,
		scalar_int_mode	mode,
		rtx	rhs,
		class rtx_iv *	iv )

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

References iv::base, CONSTANT_P, gcc_assert, GET_CODE, GET_MODE, ggc_alloc(), iv_add(), iv_analyze_expr(), iv_analyze_op(), iv_extend(), iv_mult(), iv_neg(), iv_shift(), IV_SIGN_EXTEND, IV_ZERO_EXTEND, rtx_iv::mode, NULL_RTX, REG_P, iv::step, and XEXP.

Referenced by iv_analyze_def(), and iv_analyze_expr().

◆ iv_analyze_op()

static bool iv_analyze_op	(	rtx_insn *	insn,
		scalar_int_mode	mode,
		rtx	op,
		class rtx_iv *	iv )

static

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

References dump_file, dump_iv_info(), function_invariant_p(), GET_CODE, GET_MODE, ggc_alloc(), GRD_INVALID, GRD_INVARIANT, GRD_MAYBE_BIV, iv_analyze_biv(), iv_analyze_def(), iv_analyze_op(), iv_constant(), iv_get_reaching_def(), iv_subreg(), rtx_iv::mode, NULL, print_rtl(), print_rtl_single(), subreg_lowpart_p(), and SUBREG_REG.

Referenced by iv_analyze(), iv_analyze_expr(), and iv_analyze_op().

◆ iv_analyze_result()

bool iv_analyze_result	(	rtx_insn *	insn,
		rtx	def,
		class rtx_iv *	iv )

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

References df_find_def(), ggc_alloc(), and iv_analyze_def().

Referenced by analyze_iv_to_split_insn().

◆ iv_constant()

static bool iv_constant	(	class rtx_iv *	iv,
		scalar_int_mode	mode,
		rtx	cst )

static

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

References iv::base, const0_rtx, const1_rtx, ggc_alloc(), IV_UNKNOWN_EXTEND, and iv::step.

Referenced by iv_analyze_biv(), and iv_analyze_op().

◆ iv_extend()

static bool iv_extend	(	class rtx_iv *	iv,
		enum iv_extend_code	extend,
		scalar_int_mode	mode )

static

Evaluates application of EXTEND to MODE on IV.

References iv::base, const0_rtx, const1_rtx, get_iv_value(), iv_extend_to_rtx_code(), IV_UNKNOWN_EXTEND, lowpart_subreg(), simplify_gen_unary(), and iv::step.

Referenced by iv_analyze_expr().

◆ iv_extend_to_rtx_code()

static enum rtx_code iv_extend_to_rtx_code ( enum iv_extend_code extend )

inlinestatic

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

References gcc_unreachable, ggc_alloc(), IV_SIGN_EXTEND, IV_UNKNOWN_EXTEND, and IV_ZERO_EXTEND.

Referenced by dump_iv_info(), get_iv_value(), and iv_extend().

◆ iv_get_reaching_def()

static enum iv_grd_result iv_get_reaching_def	(	rtx_insn *	insn,
		rtx	reg,
		df_ref *	def )

static

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

References BLOCK_FOR_INSN(), CDI_DOMINATORS, current_loop, df_find_use(), DF_INSN_LUID, DF_REF_BB, DF_REF_CHAIN, DF_REF_FLAGS, DF_REF_INSN, DF_REF_READ_WRITE, dominated_by_p(), gcc_assert, GET_CODE, ggc_alloc(), GRD_INVALID, GRD_INVARIANT, GRD_MAYBE_BIV, GRD_SINGLE_DOM, just_once_each_iteration_p(), NULL, REG_P, simple_reg_p(), and SUBREG_REG.

Referenced by get_biv_step_1(), and iv_analyze_op().

◆ iv_mult()

static bool iv_mult	(	class rtx_iv *	iv,
		rtx	mby )

static

Evaluates multiplication of IV by constant CST.

References iv::base, GET_MODE, ggc_alloc(), IV_UNKNOWN_EXTEND, simplify_gen_binary(), and iv::step.

Referenced by iv_analyze_expr().

◆ iv_neg()

static bool iv_neg ( class rtx_iv * iv )

static

Evaluates negation of IV.

References iv::base, ggc_alloc(), IV_UNKNOWN_EXTEND, simplify_gen_unary(), and iv::step.

Referenced by iv_add(), and iv_analyze_expr().

◆ iv_number_of_iterations()

static void iv_number_of_iterations	(	class loop *	loop,
		rtx_insn *	insn,
		rtx	condition,
		class 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.

References alloc_EXPR_LIST(), niter_desc::assumptions, canonicalize_iv_subregs(), COMPARISON_P, const0_rtx, const1_rtx, CONST_INT_P, niter_desc::const_iter, const_true_rtx, constm1_rtx, copy_rtx(), rtx_iv::delta, determine_max_iter(), gcc_assert, gen_int_mode(), GET_CODE, GET_MODE, GET_MODE_BITSIZE(), get_mode_bounds(), GET_MODE_MASK, GET_MODE_PRECISION(), ggc_alloc(), HOST_BITS_PER_WIDE_INT, niter_desc::infinite, INTVAL, inverse(), iv_analyze(), lowpart_subreg(), rtx_iv::mode, niter_desc::mode, niter_desc::niter, niter_desc::niter_expr, niter_desc::noloop_assumptions, NULL_RTX, record_niter_bound(), reverse_condition(), rtx_equal_p(), niter_desc::simple_p, simplify_gen_binary(), simplify_gen_relational(), simplify_gen_unary(), simplify_using_initial_values(), rtx_iv::step, swap_condition(), and XEXP.

Referenced by check_simple_exit().

◆ iv_shift()

static bool iv_shift	(	class rtx_iv *	iv,
		rtx	mby )

static

Evaluates shift of IV by constant CST.

References iv::base, GET_MODE, ggc_alloc(), IV_UNKNOWN_EXTEND, simplify_gen_binary(), and iv::step.

Referenced by iv_analyze_expr().

◆ iv_subreg()

static bool iv_subreg	(	class rtx_iv *	iv,
		scalar_int_mode	mode )

static

Evaluates application of subreg to MODE on IV.

References iv::base, const0_rtx, const1_rtx, get_iv_value(), GET_MODE_BITSIZE(), ggc_alloc(), IV_UNKNOWN_EXTEND, lowpart_subreg(), simplify_gen_binary(), and iv::step.

Referenced by iv_analyze_op().

◆ latch_dominating_def()

static bool latch_dominating_def	(	rtx	reg,
		df_ref *	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.

References bitmap_bit_p, df_d::blocks_to_analyze, current_loop, df, DF_RD_BB_INFO, DF_REF_BB, DF_REF_BBNO, DF_REF_ID, DF_REF_NEXT_REG, DF_REG_DEF_CHAIN, ggc_alloc(), just_once_each_iteration_p(), loop::latch, NULL, and REGNO.

Referenced by biv_p(), and iv_analyze_biv().

◆ mark_altered()

static void mark_altered	(	rtx	expr,
		const_rtx	by,
		void *	alt )

static

Marks registers altered by EXPR in set ALT.

References GET_CODE, ggc_alloc(), REG_P, REGNO, SET_REGNO_REG_SET, and SUBREG_REG.

Referenced by simplify_using_initial_values().

◆ record_biv()

static void record_biv	(	rtx	def,
		class rtx_iv *	iv )

static

References bivs, gcc_assert, ggc_alloc(), biv_entry::iv, and REGNO.

Referenced by iv_analyze_biv().

◆ record_iv()

static void record_iv	(	df_ref	def,
		class rtx_iv *	iv )

static

Records information that DEF is induction variable IV.

References check_iv_ref_table_size(), DF_REF_IV_SET, and ggc_alloc().

Referenced by iv_analyze_def().

◆ replace_in_expr()

static void replace_in_expr	(	rtx *	expr,
		rtx	dest,
		rtx	src )

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.

References expr, replace_single_def_regs(), and simplify_replace_rtx().

Referenced by simplify_using_initial_values().

◆ replace_single_def_regs()

static void replace_single_def_regs ( rtx * expr )

static

If any registers in *EXPR that have a single definition, try to replace
them with the known-equivalent values.

References df_find_single_def_src(), FOR_EACH_SUBRTX_VAR, ggc_alloc(), REG_P, and simplify_replace_rtx().

Referenced by replace_in_expr(), and simplify_using_initial_values().

◆ reversed_condition()

static rtx reversed_condition ( rtx cond )

static

Reverses CONDition; returns NULL if we cannot.

References GET_MODE, ggc_alloc(), NULL, NULL_RTX, reversed_comparison_code(), and XEXP.

Referenced by check_simple_exit(), simplify_using_condition(), and simplify_using_initial_values().

◆ shorten_into_mode()

static void shorten_into_mode	(	class rtx_iv *	iv,
		scalar_int_mode	mode,
		enum rtx_code	cond,
		bool	signed_p,
		class 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.

References alloc_EXPR_LIST(), iv::base, const0_rtx, gcc_unreachable, get_mode_bounds(), ggc_alloc(), niter_desc::infinite, IV_SIGN_EXTEND, IV_ZERO_EXTEND, rtx_iv::mode, niter_desc::noloop_assumptions, and simplify_gen_relational().

Referenced by canonicalize_iv_subregs().

◆ simple_reg_p()

static bool simple_reg_p ( rtx reg )

static

Checks whether REG is a well-behaved register.

References GET_CODE, GET_MODE, GET_MODE_CLASS, ggc_alloc(), HARD_REGISTER_NUM_P, r, REG_P, REGNO, subreg_lowpart_p(), and SUBREG_REG.

Referenced by biv_p(), get_biv_step_1(), iv_analyze(), and iv_get_reaching_def().

◆ simple_rhs_p()

static bool simple_rhs_p ( rtx rhs )

static

Checks whether RHS is simple enough to process.

References function_invariant_p(), GET_CODE, ggc_alloc(), HARD_REGISTER_P, REG_P, and XEXP.

Referenced by suitable_set_for_replacement().

◆ simplify_using_condition()

void simplify_using_condition	(	rtx	cond,
		rtx *	expr,
		regset	altered )

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

References altered_reg_used(), canon_condition(), COMPARISON_P, const0_rtx, const_true_rtx, CONSTANT_P, exp(), expr, GET_CODE, ggc_alloc(), implies_p(), REG_P, reversed_condition(), rtx_equal_p(), simplify_replace_rtx(), and XEXP.

Referenced by simplify_using_initial_values().

◆ simplify_using_initial_values()

static void simplify_using_initial_values	(	class loop *	loop,
		enum rtx_code	op,
		rtx *	expr )

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.

References alloc_EXPR_LIST(), ALLOC_REG_SET, altered_reg_used(), any_condjump_p(), BB_END, CALL_P, cfun, CLEAR_REG_SET, const0_rtx, const_true_rtx, CONSTANT_P, eliminate_implied_conditions(), ENTRY_BLOCK_PTR_FOR_FN, expr, FOR_BB_INSNS_REVERSE, free_EXPR_LIST_list(), free_EXPR_LIST_node(), FREE_REG_SET, gcc_assert, gcc_unreachable, GET_CODE, get_condition(), ggc_alloc(), insn_callee_abi(), INSN_P, IOR_REG_SET, IOR_REG_SET_HRS, loop_preheader_edge(), mark_altered(), note_stores(), NULL, NULL_RTX, onlyjump_p(), reg_obstack, replace_in_expr(), replace_single_def_regs(), reversed_condition(), simplify_using_condition(), simplify_using_initial_values(), single_pred(), single_pred_edge(), single_pred_p(), suitable_set_for_replacement(), and XEXP.

Referenced by determine_max_iter(), iv_number_of_iterations(), and simplify_using_initial_values().

◆ suitable_set_for_replacement()

static bool suitable_set_for_replacement	(	rtx_insn *	insn,
		rtx *	dest,
		rtx *	src )

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 find_reg_equal_equiv_note(), NULL_RTX, REG_P, SET_DEST, SET_SRC, simple_rhs_p(), single_set(), and XEXP.

Referenced by simplify_using_initial_values().

Variable Documentation

◆ bivs

hash_table<biv_entry_hasher>* bivs

static

Bivs of the current loop.

Referenced by analyzed_for_bivness_p(), clear_iv_info(), iv_analysis_done(), iv_analysis_loop_init(), and record_biv().

◆ clean_slate

bool clean_slate = true

static

Referenced by iv_analysis_done(), iv_analysis_loop_init(), and run_rtl_passes().

◆ current_loop

class loop* current_loop

static

The current loop.

Referenced by iv_analysis_loop_init(), iv_get_reaching_def(), and latch_dominating_def().

◆ iv_ref_table

class rtx_iv** iv_ref_table

static

Table of rtx_ivs indexed by the df_ref uid field.

Referenced by check_iv_ref_table_size(), clear_iv_info(), and iv_analysis_done().

◆ iv_ref_table_size

unsigned int iv_ref_table_size = 0

static

Referenced by check_iv_ref_table_size(), and iv_analysis_done().

Data Structures

Macros

Enumerations

Functions

Variables

Macro Definition Documentation

◆ DF_REF_IV

◆ DF_REF_IV_SET

Enumeration Type Documentation

◆ iv_grd_result

Function Documentation

◆ altered_reg_used()

◆ analyzed_for_bivness_p()

◆ biv_p()

◆ canon_condition()

◆ canonicalize_iv_subregs()

◆ check_iv_ref_table_size()

◆ check_simple_exit()

◆ clear_iv_info()

◆ determine_max_iter()

◆ dump_iv_info()

◆ eliminate_implied_condition()

◆ eliminate_implied_conditions()

◆ find_simple_exit()

◆ free_simple_loop_desc()

◆ get_biv_step()

◆ get_biv_step_1()

◆ get_iv_value()

◆ get_simple_loop_desc()

◆ implies_p()

◆ inverse()

◆ iv_add()

◆ iv_analysis_done()

◆ iv_analysis_loop_init()

◆ iv_analyze()

◆ iv_analyze_biv()

◆ iv_analyze_def()

◆ iv_analyze_expr()

◆ iv_analyze_op()

◆ iv_analyze_result()

◆ iv_constant()

◆ iv_extend()

◆ iv_extend_to_rtx_code()

◆ iv_get_reaching_def()

◆ iv_mult()

◆ iv_neg()

◆ iv_number_of_iterations()

◆ iv_shift()

◆ iv_subreg()

◆ latch_dominating_def()

◆ mark_altered()

◆ record_biv()

◆ record_iv()

◆ replace_in_expr()

◆ replace_single_def_regs()

◆ reversed_condition()

◆ shorten_into_mode()

◆ simple_reg_p()

◆ simple_rhs_p()

◆ simplify_using_condition()

◆ simplify_using_initial_values()

◆ suitable_set_for_replacement()

Variable Documentation

◆ bivs

◆ clean_slate

◆ current_loop

◆ iv_ref_table

◆ iv_ref_table_size