GCC Middle and Back End API Reference
tree-outof-ssa.cc File Reference
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "cfghooks.h"
#include "ssa.h"
#include "tree-ssa.h"
#include "memmodel.h"
#include "emit-rtl.h"
#include "gimple-pretty-print.h"
#include "diagnostic-core.h"
#include "tree-dfa.h"
#include "stor-layout.h"
#include "cfgrtl.h"
#include "cfganal.h"
#include "tree-eh.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "dumpfile.h"
#include "tree-ssa-live.h"
#include "tree-ssa-ter.h"
#include "tree-ssa-coalesce.h"
#include "tree-outof-ssa.h"
#include "dojump.h"
#include "explow.h"
#include "expr.h"
Include dependency graph for tree-outof-ssa.cc:

Data Structures

class  elim_graph
 

Macros

#define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE)
 
#define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE)
 

Typedefs

typedef std::pair< var_map, bitmapparm_default_def_partition_arg
 

Functions

bool ssa_is_replaceable_p (gimple *stmt)
 
static void set_location_for_edge (edge e)
 
static rtx_insnemit_partition_copy (rtx dest, rtx src, int unsignedsrcp, tree sizeexp)
 
static void insert_partition_copy_on_edge (edge e, int dest, int src, location_t locus)
 
static void insert_value_copy_on_edge (edge e, int dest, tree src, location_t locus)
 
static void insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp, location_t locus)
 
static void insert_part_to_rtx_on_edge (edge e, rtx dest, int src, location_t locus)
 
static void clear_elim_graph (elim_graph *g)
 
static int elim_graph_size (elim_graph *g)
 
static void elim_graph_add_node (elim_graph *g, int node)
 
static void elim_graph_add_edge (elim_graph *g, int pred, int succ, location_t locus)
 
static int elim_graph_remove_succ_edge (elim_graph *g, int node, location_t *locus)
 
static void eliminate_name (elim_graph *g, int T)
 
static bool queue_phi_copy_p (var_map map, tree t)
 
static void eliminate_build (elim_graph *g)
 
static void elim_forward (elim_graph *g, int T)
 
static int elim_unvisited_predecessor (elim_graph *g, int T)
 
static void elim_backward (elim_graph *g, int T)
 
static rtx get_temp_reg (tree name)
 
static void elim_create (elim_graph *g, int T)
 
static void eliminate_phi (edge e, elim_graph *g)
 
static void remove_gimple_phi_args (gphi *phi)
 
static void eliminate_useless_phis (void)
 
static void rewrite_trees (var_map map)
 
static void create_default_def (tree var, void *arg)
 
static void for_all_parms (void(*callback)(tree var, void *arg), void *arg)
 
static void set_parm_default_def_partition (tree var, void *arg_)
 
static bitmap get_parm_default_def_partitions (var_map map)
 
static bitmap get_undefined_value_partitions (var_map map)
 
void expand_phi_nodes (struct ssaexpand *sa)
 
static void remove_ssa_form (bool perform_ter, struct ssaexpand *sa)
 
static void maybe_renumber_stmts_bb (basic_block bb)
 
static bool trivially_conflicts_p (basic_block bb, tree result, tree arg)
 
static void insert_backedge_copies (void)
 
static void remove_indirect_clobbers (void)
 
void finish_out_of_ssa (struct ssaexpand *sa)
 
unsigned int rewrite_out_of_ssa (struct ssaexpand *sa)
 

Macro Definition Documentation

◆ FOR_EACH_ELIM_GRAPH_PRED

#define FOR_EACH_ELIM_GRAPH_PRED ( GRAPH,
NODE,
VAR,
LOCUS,
CODE )
Value:
do { \
unsigned x_; \
int y_; \
for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
{ \
y_ = (GRAPH)->edge_list[x_ + 1]; \
if (y_ != (NODE)) \
continue; \
(void) ((VAR) = (GRAPH)->edge_list[x_]); \
(void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
CODE; \
} \
} while (0)
Definition cfganal.h:27
Find all the nodes which are predecessors of NODE in the edge list for
GRAPH.  VAR will hold the partition number found.  CODE is the
code fragment executed for every node found.   

Referenced by elim_backward(), elim_create(), and elim_unvisited_predecessor().

◆ FOR_EACH_ELIM_GRAPH_SUCC

#define FOR_EACH_ELIM_GRAPH_SUCC ( GRAPH,
NODE,
VAR,
LOCUS,
CODE )
Value:
do { \
unsigned x_; \
int y_; \
for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2) \
{ \
y_ = (GRAPH)->edge_list[x_]; \
if (y_ != (NODE)) \
continue; \
(void) ((VAR) = (GRAPH)->edge_list[x_ + 1]); \
(void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]); \
CODE; \
} \
} while (0)
Find all the nodes in GRAPH which are successors to NODE in the
edge list.  VAR will hold the partition number found.  CODE is the
code fragment executed for every node found.   

Referenced by elim_forward().

Typedef Documentation

◆ parm_default_def_partition_arg

We need to pass two arguments to set_parm_default_def_partition,
but for_all_parms only supports one.  Use a pair.   

Function Documentation

◆ clear_elim_graph()

static void clear_elim_graph ( elim_graph * g)
inlinestatic
Empty elimination graph G.   

References g.

Referenced by eliminate_build().

◆ create_default_def()

static void create_default_def ( tree var,
void * arg )
static
Create a default def for VAR.   

References cfun, gcc_assert, get_or_create_ssa_default_def(), and is_gimple_reg().

Referenced by remove_ssa_form().

◆ elim_backward()

static void elim_backward ( elim_graph * g,
int T )
static
Process predecessors first, and insert a copy.   

References bitmap_bit_p, bitmap_set_bit, elim_backward(), FOR_EACH_ELIM_GRAPH_PRED, g, and insert_partition_copy_on_edge().

Referenced by elim_backward(), and elim_create().

◆ elim_create()

static void elim_create ( elim_graph * g,
int T )
static
Insert required copies for T in graph G.  Check for a strongly connected
region, and create a temporary to break the cycle if one is found.   

References bitmap_bit_p, bitmap_set_bit, elim_backward(), elim_graph_remove_succ_edge(), elim_unvisited_predecessor(), FOR_EACH_ELIM_GRAPH_PRED, g, get_temp_reg(), insert_part_to_rtx_on_edge(), insert_partition_copy_on_edge(), insert_rtx_to_part_on_edge(), partition_to_var(), S, TREE_TYPE, TYPE_UNSIGNED, and UNKNOWN_LOCATION.

Referenced by eliminate_phi().

◆ elim_forward()

static void elim_forward ( elim_graph * g,
int T )
static
Push successors of T onto the elimination stack for G.   

References bitmap_bit_p, bitmap_set_bit, elim_forward(), FOR_EACH_ELIM_GRAPH_SUCC, g, and S.

Referenced by elim_forward(), and eliminate_phi().

◆ elim_graph_add_edge()

static void elim_graph_add_edge ( elim_graph * g,
int pred,
int succ,
location_t locus )
inlinestatic
Add the edge PRED->SUCC to graph G.   

References g.

Referenced by eliminate_build().

◆ elim_graph_add_node()

static void elim_graph_add_node ( elim_graph * g,
int node )
inlinestatic
Add NODE to graph G, if it doesn't exist already.   

References FOR_EACH_VEC_ELT, and g.

Referenced by eliminate_name().

◆ elim_graph_remove_succ_edge()

static int elim_graph_remove_succ_edge ( elim_graph * g,
int node,
location_t * locus )
inlinestatic
Remove an edge from graph G for which NODE is the predecessor, and
return the successor node.  -1 is returned if there is no such edge.   

References g, UNKNOWN_LOCATION, and y.

Referenced by elim_create().

◆ elim_graph_size()

static int elim_graph_size ( elim_graph * g)
inlinestatic
Return the number of nodes in graph G.   

References g.

Referenced by eliminate_phi().

◆ elim_unvisited_predecessor()

static int elim_unvisited_predecessor ( elim_graph * g,
int T )
static
Return 1 if there unvisited predecessors of T in graph G.   

References bitmap_bit_p, FOR_EACH_ELIM_GRAPH_PRED, and g.

Referenced by elim_create().

◆ eliminate_build()

◆ eliminate_name()

static void eliminate_name ( elim_graph * g,
int T )
inlinestatic
Add T to elimination graph G.   

References elim_graph_add_node(), and g.

Referenced by eliminate_build().

◆ eliminate_phi()

static void eliminate_phi ( edge e,
elim_graph * g )
static

◆ eliminate_useless_phis()

static void eliminate_useless_phis ( void )
static

◆ emit_partition_copy()

static rtx_insn * emit_partition_copy ( rtx dest,
rtx src,
int unsignedsrcp,
tree sizeexp )
inlinestatic
Emit insns to copy SRC into DEST converting SRC if necessary.  As
SRC/DEST might be BLKmode memory locations SIZEEXP is a tree from
which we deduce the size to copy in that case.   

References BLOCK_OP_NORMAL, convert_to_mode(), do_pending_stack_adjust(), emit_block_move(), emit_move_insn(), end_sequence(), expr_size(), gcc_assert, get_insns(), GET_MODE, and start_sequence().

Referenced by insert_part_to_rtx_on_edge(), insert_partition_copy_on_edge(), and insert_rtx_to_part_on_edge().

◆ expand_phi_nodes()

void expand_phi_nodes ( struct ssaexpand * sa)
Given the out-of-ssa info object SA (with prepared partitions)
eliminate all phi nodes in all basic blocks.  Afterwards no
basic block will have phi nodes anymore and there are possibly
some RTL instructions inserted on edges.   

References cfun, ei_next(), ei_safe_edge(), ei_start, eliminate_phi(), ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, FOR_BB_BETWEEN, FOR_EACH_EDGE, g, gimple_seq_empty_p(), insns, ssaexpand::map, NULL, phi_nodes(), basic_block_def::preds, set_phi_nodes(), single_pred_edge(), single_pred_p(), and split_edge().

◆ finish_out_of_ssa()

void finish_out_of_ssa ( struct ssaexpand * sa)
Free all memory associated with going out of SSA form.  SA is
the outof-SSA info object.   

References BITMAP_FREE, delete_var_map(), free(), ssaexpand::map, ssaexpand::partition_to_pseudo, ssaexpand::partitions_for_parm_default_defs, ssaexpand::partitions_for_undefined_values, and ssaexpand::values.

◆ for_all_parms()

static void for_all_parms ( void(* callback )(tree var, void *arg),
void * arg )
static
Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which
assign_parms may ask for a default partition.   

References cfun, current_function_decl, DECL_ARGUMENTS, DECL_CHAIN, DECL_RESULT, TREE_TYPE, and VOID_TYPE_P.

Referenced by get_parm_default_def_partitions(), and remove_ssa_form().

◆ get_parm_default_def_partitions()

static bitmap get_parm_default_def_partitions ( var_map map)
static
Allocate and return a bitmap that has a bit set for each partition
that contains a default def for a parameter.   

References BITMAP_ALLOC, for_all_parms(), map, NULL, and set_parm_default_def_partition().

Referenced by remove_ssa_form().

◆ get_temp_reg()

static rtx get_temp_reg ( tree name)
static
Allocate a new pseudo register usable for storing values sitting
in NAME (a decl or SSA name), i.e. with matching mode and attributes.   

References assign_temp(), gen_reg_rtx(), mark_reg_pointer(), POINTER_TYPE_P, promote_ssa_mode(), reg_mode, TREE_TYPE, and TYPE_ALIGN.

Referenced by elim_create().

◆ get_undefined_value_partitions()

static bitmap get_undefined_value_partitions ( var_map map)
static
Allocate and return a bitmap that has a bit set for each partition
that contains an undefined value.   

References BITMAP_ALLOC, bitmap_set_bit, has_zero_uses(), i, map, NO_PARTITION, NULL, num_ssa_names, ssa_name, ssa_undefined_value_p(), var_to_partition(), and virtual_operand_p().

Referenced by remove_ssa_form().

◆ insert_backedge_copies()

static void insert_backedge_copies ( void )
static
Search every PHI node for arguments associated with backedges which
we can trivially determine will need a copy (the argument is either
not an SSA_NAME or the argument has a different underlying variable
than the PHI result).

Insert a copy from the PHI argument to a new destination at the
end of the block with the backedge to the top of the loop.  Update
the PHI argument to reference this new destination.   

References basic_block_def::aux, cfun, copy_ssa_name(), EDGE_CRITICAL_P, FOR_EACH_BB_FN, FOR_EACH_IMM_USE_ON_STMT, FOR_EACH_IMM_USE_STMT, gimple_bb(), gimple_build_assign(), gimple_nop_p(), gimple_phi_arg_def(), gimple_phi_arg_edge(), gimple_phi_arg_has_location(), gimple_phi_arg_location(), gimple_phi_num_args(), gimple_phi_result(), gimple_set_location(), gimple_uid(), gsi_end_p(), gsi_for_stmt(), gsi_insert_after(), gsi_insert_before(), gsi_last_bb(), GSI_NEW_STMT, gsi_next(), GSI_SAME_STMT, gsi_start_phis(), gsi_stmt(), i, last, mark_dfs_back_edges(), maybe_renumber_stmts_bb(), NULL, gphi_iterator::phi(), SET_PHI_ARG_DEF, SET_USE, SSA_NAME_DEF_STMT, stmt_ends_bb_p(), TREE_CODE, trivially_conflicts_p(), and virtual_operand_p().

Referenced by rewrite_out_of_ssa().

◆ insert_part_to_rtx_on_edge()

static void insert_part_to_rtx_on_edge ( edge e,
rtx dest,
int src,
location_t locus )
static

◆ insert_partition_copy_on_edge()

static void insert_partition_copy_on_edge ( edge e,
int dest,
int src,
location_t locus )
static

◆ insert_rtx_to_part_on_edge()

static void insert_rtx_to_part_on_edge ( edge e,
int dest,
rtx src,
int unsignedsrcp,
location_t locus )
static

◆ insert_value_copy_on_edge()

◆ maybe_renumber_stmts_bb()

static void maybe_renumber_stmts_bb ( basic_block bb)
static
If not already done so for basic block BB, assign increasing uids
to each of its instructions.   

References basic_block_def::aux, gimple_set_uid(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), i, and NULL.

Referenced by insert_backedge_copies(), and trivially_conflicts_p().

◆ queue_phi_copy_p()

static bool queue_phi_copy_p ( var_map map,
tree t )
inlinestatic
Return true if this phi argument T should have a copy queued when using
var_map MAP.  PHI nodes should contain only ssa_names and invariants.  A
test for ssa_name is definitely simpler, but don't let invalid contents
slip through in the meantime.   

References gcc_checking_assert, is_gimple_min_invariant(), map, NO_PARTITION, TREE_CODE, and var_to_partition().

Referenced by eliminate_build().

◆ remove_gimple_phi_args()

static void remove_gimple_phi_args ( gphi * phi)
static
Remove each argument from PHI.  If an arg was the last use of an SSA_NAME,
check to see if this allows another PHI node to be removed.   

References as_a(), dump_file, dump_flags, FOR_EACH_PHI_ARG, gsi_for_stmt(), has_zero_uses(), NULL_TREE, print_gimple_stmt(), remove_gimple_phi_args(), remove_phi_node(), SET_USE, SSA_NAME_DEF_STMT, SSA_OP_USE, TDF_DETAILS, TDF_SLIM, TREE_CODE, and USE_FROM_PTR.

Referenced by eliminate_useless_phis(), and remove_gimple_phi_args().

◆ remove_indirect_clobbers()

static void remove_indirect_clobbers ( void )
static

◆ remove_ssa_form()

static void remove_ssa_form ( bool perform_ter,
struct ssaexpand * sa )
static

◆ rewrite_out_of_ssa()

unsigned int rewrite_out_of_ssa ( struct ssaexpand * sa)
Take the current function out of SSA form, translating PHIs as described in
R. Morgan, ``Building an Optimizing Compiler'',
Butterworth-Heinemann, Boston, MA, 1998. pp 176-186.   

References dump_file, dump_flags, eliminate_useless_phis(), gimple_dump_cfg(), insert_backedge_copies(), remove_indirect_clobbers(), remove_ssa_form(), and TDF_DETAILS.

◆ rewrite_trees()

static void rewrite_trees ( var_map map)
static
This function will rewrite the current program using the variable mapping
found in MAP.  If the replacement vector VALUES is provided, any
occurrences of partitions with non-null entries in the vector will be
replaced with the expression in the vector instead of its mapped
variable.   

References cfun, FOR_EACH_BB_FN, gimple_phi_num_args(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), i, internal_error(), map, NO_PARTITION, NULL_TREE, gphi_iterator::phi(), PHI_ARG_DEF, print_generic_expr(), print_gimple_stmt(), TDF_SLIM, TREE_CODE, var_to_partition(), and var_to_partition_to_var().

Referenced by remove_ssa_form().

◆ set_location_for_edge()

static void set_location_for_edge ( edge e)
static
For an edge E find out a good source location to associate with
instructions inserted on edge E.  If E has an implicit goto set,
use its location.  Otherwise search instructions in predecessors
of E for a location, and use that one.  That makes sense because
we insert on edges for PHI nodes, and effects of PHIs happen on
the end of the predecessor conceptually.  An exception is made
for EH edges because we don't want to drag the source location
of unrelated statements at the beginning of handlers; they would
be further reused for various EH constructs, which would damage
the coverage information.   

References gimple_block(), gimple_has_location(), gimple_location(), gsi_end_p(), gsi_last_bb(), gsi_next(), gsi_prev(), gsi_start_bb(), gsi_stmt(), is_gimple_debug(), set_curr_insn_location(), single_pred(), single_pred_p(), single_succ(), and single_succ_p().

Referenced by insert_part_to_rtx_on_edge(), insert_partition_copy_on_edge(), insert_rtx_to_part_on_edge(), and insert_value_copy_on_edge().

◆ set_parm_default_def_partition()

static void set_parm_default_def_partition ( tree var,
void * arg_ )
static
Set in ARG's PARTS bitmap the bit corresponding to the partition in
ARG's MAP containing VAR's default def.   

References bitmap_set_bit, cfun, changed, gcc_assert, is_gimple_reg(), map, NO_PARTITION, ssa_default_def(), and var_to_partition().

Referenced by get_parm_default_def_partitions().

◆ ssa_is_replaceable_p()

bool ssa_is_replaceable_p ( gimple * stmt)
Convert a program in SSA form into Normal form.
   Copyright (C) 2004-2024 Free Software Foundation, Inc.
   Contributed by Andrew Macleod <amacleod@redhat.com>

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/>.   
FIXME: A lot of code here deals with expanding to RTL.  All that code
should be in cfgexpand.cc.   
Return TRUE if expression STMT is suitable for replacement.   

References cfun, DECL_HARD_REGISTER, FLOAT_TYPE_P, gimple_assign_rhs1(), gimple_assign_rhs_code(), gimple_has_volatile_ops(), gimple_vdef(), is_gimple_assign(), is_gimple_call(), single_imm_use(), SINGLE_SSA_TREE_OPERAND, SSA_OP_DEF, stmt_could_throw_p(), and TREE_TYPE.

Referenced by stmt_is_replaceable_p(), and ter_is_replaceable_p().

◆ trivially_conflicts_p()

static bool trivially_conflicts_p ( basic_block bb,
tree result,
tree arg )
static
Return true if we can determine that the SSA_NAMEs RESULT (a result
of a PHI node) and ARG (one of its arguments) conflict.  Return false
otherwise, also when we simply aren't sure.   

References FOR_EACH_IMM_USE_FAST, gimple_bb(), gimple_uid(), is_gimple_debug(), maybe_renumber_stmts_bb(), SSA_NAME_DEF_STMT, and USE_STMT.

Referenced by insert_backedge_copies().