#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "target.h"
#include "rtl.h"
#include "df.h"
#include "memmodel.h"
#include "tm_p.h"
#include "insn-config.h"
#include "recog.h"
#include "emit-rtl.h"
#include "cfgrtl.h"
#include "tree-pass.h"
#include "domwalk.h"

Include dependency graph for compare-elim.cc:

Data Structures
struct	comparison_use

struct	comparison

class	find_comparison_dom_walker

Macros
#define	MAX_CMP_USE 3

#define	SELECT_CC_MODE(A, B, C) (gcc_unreachable (), VOIDmode)

Functions
static bool	is_not (rtx x)

static rtx	strip_not (rtx x)

static rtx	conforming_compare (rtx_insn *insn)

static bool	arithmetic_flags_clobber_p (rtx_insn *insn)

static void	find_flags_uses_in_insn (struct comparison cmp, rtx_insn insn)

static bool	can_eliminate_compare (rtx compare, rtx eh_note, struct comparison *cmp)

static void	find_comparisons (void)

static rtx	maybe_select_cc_mode (struct comparison *cmp, rtx a, rtx b)

static rtx	equivalent_reg_at_start (rtx reg, rtx_insn end, rtx_insn start)

static bool	can_merge_compare_into_arith (rtx_insn cmp_insn, rtx_insn arith_insn)

static rtx	try_validate_parallel (rtx set_a, rtx set_b)

static bool	try_merge_compare (struct comparison *cmp)

static bool	try_eliminate_compare (struct comparison *cmp)

static unsigned int	execute_compare_elim_after_reload (void)

rtl_opt_pass *	make_pass_compare_elim_after_reload (gcc::context *ctxt)

Variables
static vec< comparison * >	all_compares

Macro Definition Documentation

◆ MAX_CMP_USE

#define MAX_CMP_USE 3

Post-reload compare elimination.
   Copyright (C) 2010-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/>.

There is a set of targets whose general-purpose move or addition
  instructions clobber the flags.  These targets cannot split their
  CBRANCH/CSTORE etc patterns before reload is complete, lest reload
  itself insert these instructions in between the flags setter and user.
  Because these targets cannot split the compare from the use, they
  cannot make use of the comparison elimination offered by the combine pass.

  This is a small pass intended to provide comparison elimination similar to
  what was available via NOTICE_UPDATE_CC for cc0 targets.

  This pass assumes:

  (0) CBRANCH/CSTORE etc have been split in pass_split_after_reload.

  (1) All comparison patterns are represented as

       [(set (reg:CC) (compare:CC (reg) (reg_or_immediate)))]

  (2) All insn patterns that modify the flags are represented as

       [(set (reg) (operation)
        (clobber (reg:CC))]

  (3) If an insn of form (2) can usefully set the flags, there is
      another pattern of the form

       [(set (reg:CCM) (compare:CCM (operation) (immediate)))
        (set (reg) (operation)]
        
      The mode CCM will be chosen as if by SELECT_CC_MODE.

  Note that unlike NOTICE_UPDATE_CC, we do not handle memory operands.
  This could be handled as a future enhancement.

These structures describe a comparison and how it is used.

The choice of maximum 3 uses comes from wanting to eliminate the two
duplicate compares from a three-way branch on the sign of a value.
This is also sufficient to eliminate the duplicate compare against the
high-part of a double-word comparison.

Referenced by find_flags_uses_in_insn().

◆ SELECT_CC_MODE

#define SELECT_CC_MODE	(	A,
		B,
		C ) (gcc_unreachable (), VOIDmode)

Function Documentation

◆ arithmetic_flags_clobber_p()

static bool arithmetic_flags_clobber_p ( rtx_insn * insn )

static

Look for a pattern of the "correct" form for an insn with a flags clobber
for which we may be able to eliminate a compare later.  We're not looking
to validate any inputs at this time, merely see that the basic shape is
correct.  The term "arithmetic" may be somewhat misleading...

References asm_noperands(), GET_CODE, ggc_alloc(), comparison_use::insn, NONJUMP_INSN_P, PATTERN(), REG_P, REGNO, SET, SET_DEST, targetm, XEXP, XVECEXP, and XVECLEN.

Referenced by find_comparison_dom_walker::before_dom_children().

◆ can_eliminate_compare()

static bool can_eliminate_compare	(	rtx	compare,
		rtx	eh_note,
		struct comparison *	cmp )

static

Return true if conforming COMPARE with EH_NOTE is redundant with comparison
CMP and can thus be eliminated.

References cfun, gen_rtx_REG(), GET_MODE, ggc_alloc(), is_not(), new_mode(), PATTERN(), rtx_equal_p(), strip_not(), targetm, validate_change(), and XEXP.

Referenced by find_comparison_dom_walker::before_dom_children().

◆ can_merge_compare_into_arith()

static bool can_merge_compare_into_arith	(	rtx_insn *	cmp_insn,
		rtx_insn *	arith_insn )

static

Return true if it is okay to merge the comparison CMP_INSN with
the instruction ARITH_INSN.  Both instructions are assumed to be in the
same basic block with ARITH_INSN appearing before CMP_INSN.  This checks
that there are no uses or defs of the condition flags or control flow
changes between the two instructions.

References DF_REF_REGNO, FOR_EACH_INSN_DEF, FOR_EACH_INSN_USE, GET_CODE, ggc_alloc(), comparison::insn, NONDEBUG_INSN_P, NONJUMP_INSN_P, PATTERN(), PREV_INSN(), and targetm.

Referenced by try_merge_compare().

◆ conforming_compare()

static rtx conforming_compare ( rtx_insn * insn )

static

Look for a "conforming" comparison, as defined above.  If valid, return
the rtx for the COMPARE itself.

References CONSTANT_P, GET_CODE, ggc_alloc(), i, comparison_use::insn, NULL, REG_P, REGNO, SET_DEST, SET_SRC, single_set(), strip_not(), targetm, XEXP, XVECEXP, and XVECLEN.

Referenced by find_comparison_dom_walker::before_dom_children().

◆ equivalent_reg_at_start()

static rtx equivalent_reg_at_start	(	rtx	reg,
		rtx_insn *	end,
		rtx_insn *	start )

static

Return a register RTX holding the same value at START as REG at END, or
NULL_RTX if there is none.

References BB_HEAD, BLOCK_FOR_INSN(), DEBUG_INSN_P, DF_REF_CONDITIONAL, DF_REF_FLAGS, DF_REF_IS_ARTIFICIAL, DF_REF_MAY_CLOBBER, DF_REF_MUST_CLOBBER, DF_REF_PARTIAL, DF_REF_PRE_POST_MODIFY, DF_REF_REGNO, DF_REF_SIGN_EXTRACT, DF_REF_STRICT_LOW_PART, DF_REF_ZERO_EXTRACT, end(), FOR_EACH_INSN_DEF, GET_MODE, ggc_alloc(), comparison::insn, NOTE_P, NULL, NULL_RTX, comparison::orig_mode, PREV_INSN(), REG_P, REGNO, SET_SRC, and single_set().

Referenced by try_eliminate_compare().

◆ execute_compare_elim_after_reload()

static unsigned int execute_compare_elim_after_reload ( void )

static

Main entry point to the pass.

References all_compares, df_analyze(), DF_LR_RUN_DCE, df_set_flags(), find_comparisons(), FOR_EACH_VEC_ELT, gcc_checking_assert, ggc_alloc(), i, and try_eliminate_compare().

◆ find_comparisons()

static void find_comparisons ( void )

static

Find all comparisons in the function.

References calculate_dominance_info(), CDI_DOMINATORS, cfun, clear_aux_for_blocks(), free_dominance_info(), and dom_walker::walk().

Referenced by execute_compare_elim_after_reload().

◆ find_flags_uses_in_insn()

static void find_flags_uses_in_insn	(	struct comparison *	cmp,
		rtx_insn *	insn )

static

Look for uses of FLAGS in INSN.  If we find one we can analyze, record
it in CMP; otherwise indicate that we've missed a use.

References COMPARISON_P, const0_rtx, DF_REF_LOC, DF_REF_REG_USE, DF_REF_REGNO, DF_REF_TYPE, FOR_EACH_INSN_USE, GET_CODE, ggc_alloc(), comparison_use::insn, comparison_use::loc, MAX_CMP_USE, PATTERN(), SET, SET_SRC, targetm, XEXP, and XVECEXP.

Referenced by find_comparison_dom_walker::before_dom_children().

◆ is_not()

static bool is_not ( rtx x )

static

Return whether X is a NOT unary expression.

References GET_CODE, and ggc_alloc().

Referenced by find_comparison_dom_walker::before_dom_children(), can_eliminate_compare(), and strip_not().

◆ make_pass_compare_elim_after_reload()

rtl_opt_pass * make_pass_compare_elim_after_reload ( gcc::context * ctxt )

References ggc_alloc().

◆ maybe_select_cc_mode()

static rtx maybe_select_cc_mode	(	struct comparison *	cmp,
		rtx	a,
		rtx	b )

static

Select an alternate CC_MODE for a comparison insn comparing A and B.
Note that inputs are almost certainly different than the IN_A and IN_B
stored in CMP -- we're called while attempting to eliminate the compare
after all.  Return the new FLAGS rtx if successful, else return NULL.
Note that this function may start a change group.

References a, b, gen_rtx_REG(), ggc_alloc(), i, new_mode(), NULL, SELECT_CC_MODE, targetm, and validate_change().

Referenced by try_eliminate_compare(), and try_merge_compare().

◆ strip_not()

static rtx strip_not ( rtx x )

static

Strip a NOT unary expression around X, if any.

References is_not(), and XEXP.

Referenced by find_comparison_dom_walker::before_dom_children(), can_eliminate_compare(), and conforming_compare().

◆ try_eliminate_compare()

static bool try_eliminate_compare ( struct comparison * cmp )

static

Attempt to replace a comparison with a prior arithmetic insn that can
compute the same flags value as the comparison itself.  Return true if
successful, having made all rtl modifications necessary.

References apply_change_group(), CONSTANT_P, copy_rtx(), delete_insn(), equivalent_reg_at_start(), find_reg_note(), find_regno_note(), gcc_unreachable, gen_rtx_REG(), GET_CODE, GET_MODE, ggc_alloc(), i, comparison::in_a, comparison::in_b, comparison::insn, maybe_select_cc_mode(), NULL, PATTERN(), r, REG_P, REGNO, remove_note(), rtvec_alloc(), RTVEC_ELT, rtx_equal_p(), SET_DEST, SET_SRC, side_effects_p(), targetm, try_merge_compare(), validate_change(), XEXP, XINT, XVECEXP, XVECLEN, and y.

Referenced by execute_compare_elim_after_reload().

◆ try_merge_compare()

static bool try_merge_compare ( struct comparison * cmp )

static

For a comparison instruction described by CMP check if it compares a
register with zero i.e. it is of the form CC := CMP R1, 0.
If it is, find the instruction defining R1 (say I1) and try to create a
PARALLEL consisting of I1 and the comparison, representing a flag-setting
arithmetic instruction.  Example:
I1: R1 := R2 + R3
<instructions that don't read the condition register>
I2: CC := CMP R1 0
I2 can be merged with I1 into:
I1: { CC := CMP (R2 + R3) 0 ; R1 := R2 + R3 }
This catches cases where R1 is used between I1 and I2 and therefore
combine and other RTL optimisations will not try to propagate it into
I2.  Return true if we succeeded in merging CMP.

References apply_change_group(), can_merge_compare_into_arith(), cancel_changes(), const0_rtx, CONST0_RTX, copy_rtx(), delete_insn(), DF_REF_REGNO, emit_insn_after(), FOR_EACH_INSN_USE, GET_MODE, ggc_alloc(), comparison::in_a, maybe_select_cc_mode(), NULL, PATTERN(), REGNO, SET_SRC, side_effects_p(), single_set(), and try_validate_parallel().

Referenced by try_eliminate_compare().

◆ try_validate_parallel()

static rtx try_validate_parallel	(	rtx	set_a,
		rtx	set_b )

static

Given two SET expressions, SET_A and SET_B determine whether they form
a recognizable pattern when emitted in parallel.  Return that parallel
if so.  Otherwise return NULL.

References crtl, gen_rtvec(), ggc_alloc(), comparison::insn, insn_invalid_p(), INSN_LOCATION(), make_insn_raw(), NULL_RTX, SET_NEXT_INSN(), and SET_PREV_INSN().

Referenced by try_merge_compare().

Variable Documentation

◆ all_compares

vec<comparison *> all_compares

static

Referenced by find_comparison_dom_walker::before_dom_children(), and execute_compare_elim_after_reload().

Data Structures

Macros

Functions

Variables

Macro Definition Documentation

◆ MAX_CMP_USE

◆ SELECT_CC_MODE

Function Documentation

◆ arithmetic_flags_clobber_p()

◆ can_eliminate_compare()

◆ can_merge_compare_into_arith()

◆ conforming_compare()

◆ equivalent_reg_at_start()

◆ execute_compare_elim_after_reload()

◆ find_comparisons()

◆ find_flags_uses_in_insn()

◆ is_not()

◆ make_pass_compare_elim_after_reload()

◆ maybe_select_cc_mode()

◆ strip_not()

◆ try_eliminate_compare()

◆ try_merge_compare()

◆ try_validate_parallel()

Variable Documentation

◆ all_compares