gimple-ssa-sccopy.cc File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "ssa.h"
#include "gimple-iterator.h"
#include "vec.h"
#include "hash-set.h"
#include "ssa-iterators.h"
#include "gimple-fold.h"
#include "gimplify.h"
#include "tree-cfg.h"
#include "tree-eh.h"
#include "builtins.h"
#include "tree-ssa-dce.h"
#include "fold-const.h"

Include dependency graph for gimple-ssa-sccopy.cc:

Macros
#define	INCLUDE_ALGORITHM

Functions
static bool	stmt_may_generate_copy (gimple *stmt)
static auto_vec< gimple * >	get_all_stmt_may_generate_copy (void)
static void	replace_scc_by_value (vec< gimple * > scc, tree val)
static void	sccopy_visit_op (tree op, hash_set< tree > &outer_ops, hash_set< gimple * > &scc_set, bool &is_inner, tree &last_outer_op)
static void	sccopy_propagate ()
static void	init_sccopy (void)
static void	finalize_sccopy (void)
gimple_opt_pass *	make_pass_sccopy (gcc::context *ctxt)

Macro Definition Documentation

INCLUDE_ALGORITHM

#define INCLUDE_ALGORITHM

Strongly-connected copy propagation pass for the GNU compiler.
   Copyright (C) 2023-2024 Free Software Foundation, Inc.
   Contributed by Filip Kastl <fkastl@suse.cz>

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

Function Documentation

finalize_sccopy()

static void finalize_sccopy ( void )

static

Called before pass execution ends.   

References BITMAP_FREE, cfun, FOR_EACH_BB_FN, ggc_alloc(), gimple_purge_dead_eh_edges(), and simple_dce_from_worklist().

get_all_stmt_may_generate_copy()

static auto_vec< gimple * > get_all_stmt_may_generate_copy ( void )

static

Return all statements in cfun that could generate copies.  All statements
for which stmt_may_generate_copy returns 'true'.   

References cfun, FOR_EACH_BB_FN, ggc_alloc(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), and stmt_may_generate_copy().

Referenced by sccopy_propagate().

init_sccopy()

static void init_sccopy ( void )

static

Called when pass execution starts.   

References BITMAP_ALLOC, ggc_alloc(), and NULL.

make_pass_sccopy()

gimple_opt_pass * make_pass_sccopy

(

gcc::context *

ctxt

)

References ggc_alloc().

replace_scc_by_value()

static void replace_scc_by_value ( vec< gimple * > scc, tree val )

static

For each statement from given SCC, replace its usages by value
VAL.   

References bitmap_set_bit, dump_file, ggc_alloc(), gimple_get_lhs(), replace_uses_by(), and SSA_NAME_VERSION.

Referenced by sccopy_propagate().

sccopy_propagate()

static void sccopy_propagate ( )

static

Main function of this pass.  Find and propagate all three types of copy
statements (see pass description above).

This is an implementation of an algorithm from the paper Simple and
Efficient Construction of Static Single Assignmemnt Form[1].  It is based
on strongly-connected components (SCCs) in dataflow graph.  The original
algorithm only considers PHI statements.  We extend it to also consider
assignment statements of type _2 = _1;.

The algorithm is based on this definition of a set of redundant PHIs[1]:

  A non-empty set P of PHI functions is redundant iff the PHI functions just
  reference each other or one other value

It uses this lemma[1]:

  Let P be a redundant set of PHI functions.  Then there is a
  strongly-connected component S subset of P that is also redundant.

The algorithm works in this way:

  1 Find SCCs
  2 For each SCC S in topological order:
  3   Construct set 'inner' of statements that only have other statements
      from S on their right hand side
  4   Construct set 'outer' of values that originate outside S and appear on
      right hand side of some statement from S
  5   If |outer| = 1, outer only contains a value v.  Statements in S only
      refer to each other or to v -- they are redundant.  Propagate v.
      Else, recurse on statements in inner.

The implementation is non-recursive.

References:

  [1] Simple and Efficient Construction of Static Single Assignmemnt Form,
  Braun, Buchwald, Hack, Leissa, Mallon, Zwinkau, 2013, LNCS vol. 7791,
  Section 3.2.   

References gcc_unreachable, get_all_stmt_may_generate_copy(), ggc_alloc(), gimple_assign_rhs1(), gimple_phi_arg_def(), gimple_phi_num_args(), NULL_TREE, replace_scc_by_value(), sccopy_visit_op(), and worklist.

sccopy_visit_op()

static void sccopy_visit_op ( tree op, hash_set< tree > & outer_ops, hash_set< gimple * > & scc_set, bool & is_inner, tree & last_outer_op )

static

Part of 'sccopy_propagate ()'.   

References ggc_alloc(), SSA_NAME_DEF_STMT, and TREE_CODE.

Referenced by sccopy_propagate().

stmt_may_generate_copy()

static bool stmt_may_generate_copy ( gimple * stmt )

static

Could this statement potentially be a copy statement?

This pass only considers statements for which this function returns 'true'.
Those are basically PHI functions and assignment statements similar to

_2 = _1;
or
_2 = 5;   

References ggc_alloc(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_single_p(), gimple_phi_arg_def(), gimple_phi_num_args(), gimple_phi_result(), i, is_gimple_min_invariant(), NULL_TREE, operand_equal_p(), POINTER_TYPE_P, SSA_NAME_OCCURS_IN_ABNORMAL_PHI, SSA_NAME_PTR_INFO, SSA_NAME_RANGE_INFO, TREE_CODE, and TREE_TYPE.

Referenced by get_all_stmt_may_generate_copy().