/* Rewrite a program in Normal form into SSA.
|
/* Rewrite a program in Normal form into SSA.
|
Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007
|
Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007
|
Free Software Foundation, Inc.
|
Free Software Foundation, Inc.
|
Contributed by Diego Novillo <dnovillo@redhat.com>
|
Contributed by Diego Novillo <dnovillo@redhat.com>
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify
|
GCC is free software; you can redistribute it and/or modify
|
it under the terms of the GNU General Public License as published by
|
it under the terms of the GNU General Public License as published by
|
the Free Software Foundation; either version 3, or (at your option)
|
the Free Software Foundation; either version 3, or (at your option)
|
any later version.
|
any later version.
|
|
|
GCC is distributed in the hope that it will be useful,
|
GCC is distributed in the hope that it will be useful,
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
GNU General Public License for more details.
|
GNU General Public License for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "tree.h"
|
#include "tree.h"
|
#include "flags.h"
|
#include "flags.h"
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "tm_p.h"
|
#include "tm_p.h"
|
#include "langhooks.h"
|
#include "langhooks.h"
|
#include "hard-reg-set.h"
|
#include "hard-reg-set.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "output.h"
|
#include "output.h"
|
#include "expr.h"
|
#include "expr.h"
|
#include "function.h"
|
#include "function.h"
|
#include "diagnostic.h"
|
#include "diagnostic.h"
|
#include "bitmap.h"
|
#include "bitmap.h"
|
#include "tree-flow.h"
|
#include "tree-flow.h"
|
#include "tree-gimple.h"
|
#include "tree-gimple.h"
|
#include "tree-inline.h"
|
#include "tree-inline.h"
|
#include "varray.h"
|
#include "varray.h"
|
#include "timevar.h"
|
#include "timevar.h"
|
#include "hashtab.h"
|
#include "hashtab.h"
|
#include "tree-dump.h"
|
#include "tree-dump.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
#include "cfgloop.h"
|
#include "cfgloop.h"
|
#include "domwalk.h"
|
#include "domwalk.h"
|
#include "ggc.h"
|
#include "ggc.h"
|
#include "params.h"
|
#include "params.h"
|
#include "vecprim.h"
|
#include "vecprim.h"
|
|
|
/* This file builds the SSA form for a function as described in:
|
/* This file builds the SSA form for a function as described in:
|
R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
|
R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
|
Computing Static Single Assignment Form and the Control Dependence
|
Computing Static Single Assignment Form and the Control Dependence
|
Graph. ACM Transactions on Programming Languages and Systems,
|
Graph. ACM Transactions on Programming Languages and Systems,
|
13(4):451-490, October 1991. */
|
13(4):451-490, October 1991. */
|
|
|
/* True if the code is in ssa form. */
|
/* True if the code is in ssa form. */
|
bool in_ssa_p;
|
bool in_ssa_p;
|
|
|
/* Structure to map a variable VAR to the set of blocks that contain
|
/* Structure to map a variable VAR to the set of blocks that contain
|
definitions for VAR. */
|
definitions for VAR. */
|
struct def_blocks_d
|
struct def_blocks_d
|
{
|
{
|
/* The variable. */
|
/* The variable. */
|
tree var;
|
tree var;
|
|
|
/* Blocks that contain definitions of VAR. Bit I will be set if the
|
/* Blocks that contain definitions of VAR. Bit I will be set if the
|
Ith block contains a definition of VAR. */
|
Ith block contains a definition of VAR. */
|
bitmap def_blocks;
|
bitmap def_blocks;
|
|
|
/* Blocks that contain a PHI node for VAR. */
|
/* Blocks that contain a PHI node for VAR. */
|
bitmap phi_blocks;
|
bitmap phi_blocks;
|
|
|
/* Blocks where VAR is live-on-entry. Similar semantics as
|
/* Blocks where VAR is live-on-entry. Similar semantics as
|
DEF_BLOCKS. */
|
DEF_BLOCKS. */
|
bitmap livein_blocks;
|
bitmap livein_blocks;
|
};
|
};
|
|
|
|
|
/* Each entry in DEF_BLOCKS contains an element of type STRUCT
|
/* Each entry in DEF_BLOCKS contains an element of type STRUCT
|
DEF_BLOCKS_D, mapping a variable VAR to a bitmap describing all the
|
DEF_BLOCKS_D, mapping a variable VAR to a bitmap describing all the
|
basic blocks where VAR is defined (assigned a new value). It also
|
basic blocks where VAR is defined (assigned a new value). It also
|
contains a bitmap of all the blocks where VAR is live-on-entry
|
contains a bitmap of all the blocks where VAR is live-on-entry
|
(i.e., there is a use of VAR in block B without a preceding
|
(i.e., there is a use of VAR in block B without a preceding
|
definition in B). The live-on-entry information is used when
|
definition in B). The live-on-entry information is used when
|
computing PHI pruning heuristics. */
|
computing PHI pruning heuristics. */
|
static htab_t def_blocks;
|
static htab_t def_blocks;
|
|
|
/* Stack of trees used to restore the global currdefs to its original
|
/* Stack of trees used to restore the global currdefs to its original
|
state after completing rewriting of a block and its dominator
|
state after completing rewriting of a block and its dominator
|
children. Its elements have the following properties:
|
children. Its elements have the following properties:
|
|
|
- An SSA_NAME indicates that the current definition of the
|
- An SSA_NAME indicates that the current definition of the
|
underlying variable should be set to the given SSA_NAME.
|
underlying variable should be set to the given SSA_NAME.
|
|
|
- A _DECL node indicates that the underlying variable has no
|
- A _DECL node indicates that the underlying variable has no
|
current definition.
|
current definition.
|
|
|
- A NULL node is used to mark the last node associated with the
|
- A NULL node is used to mark the last node associated with the
|
current block.
|
current block.
|
|
|
- A NULL node at the top entry is used to mark the last node
|
- A NULL node at the top entry is used to mark the last node
|
associated with the current block. */
|
associated with the current block. */
|
static VEC(tree,heap) *block_defs_stack;
|
static VEC(tree,heap) *block_defs_stack;
|
|
|
/* Set of existing SSA names being replaced by update_ssa. */
|
/* Set of existing SSA names being replaced by update_ssa. */
|
static sbitmap old_ssa_names;
|
static sbitmap old_ssa_names;
|
|
|
/* Set of new SSA names being added by update_ssa. Note that both
|
/* Set of new SSA names being added by update_ssa. Note that both
|
NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
|
NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
|
the operations done on them are presence tests. */
|
the operations done on them are presence tests. */
|
static sbitmap new_ssa_names;
|
static sbitmap new_ssa_names;
|
|
|
/* Symbols whose SSA form needs to be updated or created for the first
|
/* Symbols whose SSA form needs to be updated or created for the first
|
time. */
|
time. */
|
static bitmap syms_to_rename;
|
static bitmap syms_to_rename;
|
|
|
/* Set of SSA names that have been marked to be released after they
|
/* Set of SSA names that have been marked to be released after they
|
were registered in the replacement table. They will be finally
|
were registered in the replacement table. They will be finally
|
released after we finish updating the SSA web. */
|
released after we finish updating the SSA web. */
|
static bitmap names_to_release;
|
static bitmap names_to_release;
|
|
|
/* For each block, the phi nodes that need to be rewritten are stored into
|
/* For each block, the phi nodes that need to be rewritten are stored into
|
these vectors. */
|
these vectors. */
|
|
|
typedef VEC(tree, heap) *tree_vec;
|
typedef VEC(tree, heap) *tree_vec;
|
DEF_VEC_P (tree_vec);
|
DEF_VEC_P (tree_vec);
|
DEF_VEC_ALLOC_P (tree_vec, heap);
|
DEF_VEC_ALLOC_P (tree_vec, heap);
|
|
|
static VEC(tree_vec, heap) *phis_to_rewrite;
|
static VEC(tree_vec, heap) *phis_to_rewrite;
|
|
|
/* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
|
/* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */
|
|
|
static bitmap blocks_with_phis_to_rewrite;
|
static bitmap blocks_with_phis_to_rewrite;
|
|
|
/* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
|
/* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need
|
to grow as the callers to register_new_name_mapping will typically
|
to grow as the callers to register_new_name_mapping will typically
|
create new names on the fly. FIXME. Currently set to 1/3 to avoid
|
create new names on the fly. FIXME. Currently set to 1/3 to avoid
|
frequent reallocations but still need to find a reasonable growth
|
frequent reallocations but still need to find a reasonable growth
|
strategy. */
|
strategy. */
|
#define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
|
#define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
|
|
|
/* Tuple used to represent replacement mappings. */
|
/* Tuple used to represent replacement mappings. */
|
struct repl_map_d
|
struct repl_map_d
|
{
|
{
|
tree name;
|
tree name;
|
bitmap set;
|
bitmap set;
|
};
|
};
|
|
|
/* NEW -> OLD_SET replacement table. If we are replacing several
|
/* NEW -> OLD_SET replacement table. If we are replacing several
|
existing SSA names O_1, O_2, ..., O_j with a new name N_i,
|
existing SSA names O_1, O_2, ..., O_j with a new name N_i,
|
then REPL_TBL[N_i] = { O_1, O_2, ..., O_j }. */
|
then REPL_TBL[N_i] = { O_1, O_2, ..., O_j }. */
|
static htab_t repl_tbl;
|
static htab_t repl_tbl;
|
|
|
/* true if register_new_name_mapping needs to initialize the data
|
/* true if register_new_name_mapping needs to initialize the data
|
structures needed by update_ssa. */
|
structures needed by update_ssa. */
|
static bool need_to_initialize_update_ssa_p = true;
|
static bool need_to_initialize_update_ssa_p = true;
|
|
|
/* true if update_ssa needs to update virtual operands. */
|
/* true if update_ssa needs to update virtual operands. */
|
static bool need_to_update_vops_p = false;
|
static bool need_to_update_vops_p = false;
|
|
|
/* Statistics kept by update_ssa to use in the virtual mapping
|
/* Statistics kept by update_ssa to use in the virtual mapping
|
heuristic. If the number of virtual mappings is beyond certain
|
heuristic. If the number of virtual mappings is beyond certain
|
threshold, the updater will switch from using the mappings into
|
threshold, the updater will switch from using the mappings into
|
renaming the virtual symbols from scratch. In some cases, the
|
renaming the virtual symbols from scratch. In some cases, the
|
large number of name mappings for virtual names causes significant
|
large number of name mappings for virtual names causes significant
|
slowdowns in the PHI insertion code. */
|
slowdowns in the PHI insertion code. */
|
struct update_ssa_stats_d
|
struct update_ssa_stats_d
|
{
|
{
|
unsigned num_virtual_mappings;
|
unsigned num_virtual_mappings;
|
unsigned num_total_mappings;
|
unsigned num_total_mappings;
|
bitmap virtual_symbols;
|
bitmap virtual_symbols;
|
unsigned num_virtual_symbols;
|
unsigned num_virtual_symbols;
|
};
|
};
|
static struct update_ssa_stats_d update_ssa_stats;
|
static struct update_ssa_stats_d update_ssa_stats;
|
|
|
/* Global data to attach to the main dominator walk structure. */
|
/* Global data to attach to the main dominator walk structure. */
|
struct mark_def_sites_global_data
|
struct mark_def_sites_global_data
|
{
|
{
|
/* This bitmap contains the variables which are set before they
|
/* This bitmap contains the variables which are set before they
|
are used in a basic block. */
|
are used in a basic block. */
|
bitmap kills;
|
bitmap kills;
|
|
|
/* Bitmap of names to rename. */
|
/* Bitmap of names to rename. */
|
sbitmap names_to_rename;
|
sbitmap names_to_rename;
|
|
|
/* Set of blocks that mark_def_sites deems interesting for the
|
/* Set of blocks that mark_def_sites deems interesting for the
|
renamer to process. */
|
renamer to process. */
|
sbitmap interesting_blocks;
|
sbitmap interesting_blocks;
|
};
|
};
|
|
|
|
|
/* Information stored for SSA names. */
|
/* Information stored for SSA names. */
|
struct ssa_name_info
|
struct ssa_name_info
|
{
|
{
|
/* The actual definition of the ssa name. */
|
/* The actual definition of the ssa name. */
|
tree current_def;
|
tree current_def;
|
|
|
/* This field indicates whether or not the variable may need PHI nodes.
|
/* This field indicates whether or not the variable may need PHI nodes.
|
See the enum's definition for more detailed information about the
|
See the enum's definition for more detailed information about the
|
states. */
|
states. */
|
ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
|
ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
|
|
|
/* Age of this record (so that info_for_ssa_name table can be cleared
|
/* Age of this record (so that info_for_ssa_name table can be cleared
|
quicky); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
|
quicky); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
|
are assumed to be null. */
|
are assumed to be null. */
|
unsigned age;
|
unsigned age;
|
};
|
};
|
|
|
/* The information associated with names. */
|
/* The information associated with names. */
|
typedef struct ssa_name_info *ssa_name_info_p;
|
typedef struct ssa_name_info *ssa_name_info_p;
|
DEF_VEC_P (ssa_name_info_p);
|
DEF_VEC_P (ssa_name_info_p);
|
DEF_VEC_ALLOC_P (ssa_name_info_p, heap);
|
DEF_VEC_ALLOC_P (ssa_name_info_p, heap);
|
|
|
static VEC(ssa_name_info_p, heap) *info_for_ssa_name;
|
static VEC(ssa_name_info_p, heap) *info_for_ssa_name;
|
static unsigned current_info_for_ssa_name_age;
|
static unsigned current_info_for_ssa_name_age;
|
|
|
/* The set of blocks affected by update_ssa. */
|
/* The set of blocks affected by update_ssa. */
|
|
|
static bitmap blocks_to_update;
|
static bitmap blocks_to_update;
|
|
|
/* The main entry point to the SSA renamer (rewrite_blocks) may be
|
/* The main entry point to the SSA renamer (rewrite_blocks) may be
|
called several times to do different, but related, tasks.
|
called several times to do different, but related, tasks.
|
Initially, we need it to rename the whole program into SSA form.
|
Initially, we need it to rename the whole program into SSA form.
|
At other times, we may need it to only rename into SSA newly
|
At other times, we may need it to only rename into SSA newly
|
exposed symbols. Finally, we can also call it to incrementally fix
|
exposed symbols. Finally, we can also call it to incrementally fix
|
an already built SSA web. */
|
an already built SSA web. */
|
enum rewrite_mode {
|
enum rewrite_mode {
|
/* Convert the whole function into SSA form. */
|
/* Convert the whole function into SSA form. */
|
REWRITE_ALL,
|
REWRITE_ALL,
|
|
|
/* Incrementally update the SSA web by replacing existing SSA
|
/* Incrementally update the SSA web by replacing existing SSA
|
names with new ones. See update_ssa for details. */
|
names with new ones. See update_ssa for details. */
|
REWRITE_UPDATE
|
REWRITE_UPDATE
|
};
|
};
|
|
|
|
|
/* Use TREE_VISITED to keep track of which statements we want to
|
/* Use TREE_VISITED to keep track of which statements we want to
|
rename. When renaming a subset of the variables, not all
|
rename. When renaming a subset of the variables, not all
|
statements will be processed. This is decided in mark_def_sites. */
|
statements will be processed. This is decided in mark_def_sites. */
|
#define REWRITE_THIS_STMT(T) TREE_VISITED (T)
|
#define REWRITE_THIS_STMT(T) TREE_VISITED (T)
|
|
|
/* Use the unsigned flag to keep track of which statements we want to
|
/* Use the unsigned flag to keep track of which statements we want to
|
visit when marking new definition sites. This is slightly
|
visit when marking new definition sites. This is slightly
|
different than REWRITE_THIS_STMT: it's used by update_ssa to
|
different than REWRITE_THIS_STMT: it's used by update_ssa to
|
distinguish statements that need to have both uses and defs
|
distinguish statements that need to have both uses and defs
|
processed from those that only need to have their defs processed.
|
processed from those that only need to have their defs processed.
|
Statements that define new SSA names only need to have their defs
|
Statements that define new SSA names only need to have their defs
|
registered, but they don't need to have their uses renamed. */
|
registered, but they don't need to have their uses renamed. */
|
#define REGISTER_DEFS_IN_THIS_STMT(T) (T)->common.unsigned_flag
|
#define REGISTER_DEFS_IN_THIS_STMT(T) (T)->common.unsigned_flag
|
|
|
|
|
/* Prototypes for debugging functions. */
|
/* Prototypes for debugging functions. */
|
extern void dump_tree_ssa (FILE *);
|
extern void dump_tree_ssa (FILE *);
|
extern void debug_tree_ssa (void);
|
extern void debug_tree_ssa (void);
|
extern void debug_def_blocks (void);
|
extern void debug_def_blocks (void);
|
extern void dump_tree_ssa_stats (FILE *);
|
extern void dump_tree_ssa_stats (FILE *);
|
extern void debug_tree_ssa_stats (void);
|
extern void debug_tree_ssa_stats (void);
|
void dump_update_ssa (FILE *);
|
void dump_update_ssa (FILE *);
|
void debug_update_ssa (void);
|
void debug_update_ssa (void);
|
void dump_names_replaced_by (FILE *, tree);
|
void dump_names_replaced_by (FILE *, tree);
|
void debug_names_replaced_by (tree);
|
void debug_names_replaced_by (tree);
|
|
|
/* Get the information associated with NAME. */
|
/* Get the information associated with NAME. */
|
|
|
static inline struct ssa_name_info *
|
static inline struct ssa_name_info *
|
get_ssa_name_ann (tree name)
|
get_ssa_name_ann (tree name)
|
{
|
{
|
unsigned ver = SSA_NAME_VERSION (name);
|
unsigned ver = SSA_NAME_VERSION (name);
|
unsigned len = VEC_length (ssa_name_info_p, info_for_ssa_name);
|
unsigned len = VEC_length (ssa_name_info_p, info_for_ssa_name);
|
struct ssa_name_info *info;
|
struct ssa_name_info *info;
|
|
|
if (ver >= len)
|
if (ver >= len)
|
{
|
{
|
unsigned new_len = num_ssa_names;
|
unsigned new_len = num_ssa_names;
|
|
|
VEC_reserve (ssa_name_info_p, heap, info_for_ssa_name, new_len);
|
VEC_reserve (ssa_name_info_p, heap, info_for_ssa_name, new_len);
|
while (len++ < new_len)
|
while (len++ < new_len)
|
{
|
{
|
struct ssa_name_info *info = XCNEW (struct ssa_name_info);
|
struct ssa_name_info *info = XCNEW (struct ssa_name_info);
|
info->age = current_info_for_ssa_name_age;
|
info->age = current_info_for_ssa_name_age;
|
VEC_quick_push (ssa_name_info_p, info_for_ssa_name, info);
|
VEC_quick_push (ssa_name_info_p, info_for_ssa_name, info);
|
}
|
}
|
}
|
}
|
|
|
info = VEC_index (ssa_name_info_p, info_for_ssa_name, ver);
|
info = VEC_index (ssa_name_info_p, info_for_ssa_name, ver);
|
if (info->age < current_info_for_ssa_name_age)
|
if (info->age < current_info_for_ssa_name_age)
|
{
|
{
|
info->need_phi_state = 0;
|
info->need_phi_state = 0;
|
info->current_def = NULL_TREE;
|
info->current_def = NULL_TREE;
|
info->age = current_info_for_ssa_name_age;
|
info->age = current_info_for_ssa_name_age;
|
}
|
}
|
|
|
return info;
|
return info;
|
}
|
}
|
|
|
/* Clears info for ssa names. */
|
/* Clears info for ssa names. */
|
|
|
static void
|
static void
|
clear_ssa_name_info (void)
|
clear_ssa_name_info (void)
|
{
|
{
|
current_info_for_ssa_name_age++;
|
current_info_for_ssa_name_age++;
|
}
|
}
|
|
|
/* Gets phi_state field for VAR. */
|
/* Gets phi_state field for VAR. */
|
|
|
static inline enum need_phi_state
|
static inline enum need_phi_state
|
get_phi_state (tree var)
|
get_phi_state (tree var)
|
{
|
{
|
if (TREE_CODE (var) == SSA_NAME)
|
if (TREE_CODE (var) == SSA_NAME)
|
return get_ssa_name_ann (var)->need_phi_state;
|
return get_ssa_name_ann (var)->need_phi_state;
|
else
|
else
|
return var_ann (var)->need_phi_state;
|
return var_ann (var)->need_phi_state;
|
}
|
}
|
|
|
|
|
/* Sets phi_state field for VAR to STATE. */
|
/* Sets phi_state field for VAR to STATE. */
|
|
|
static inline void
|
static inline void
|
set_phi_state (tree var, enum need_phi_state state)
|
set_phi_state (tree var, enum need_phi_state state)
|
{
|
{
|
if (TREE_CODE (var) == SSA_NAME)
|
if (TREE_CODE (var) == SSA_NAME)
|
get_ssa_name_ann (var)->need_phi_state = state;
|
get_ssa_name_ann (var)->need_phi_state = state;
|
else
|
else
|
var_ann (var)->need_phi_state = state;
|
var_ann (var)->need_phi_state = state;
|
}
|
}
|
|
|
|
|
/* Return the current definition for VAR. */
|
/* Return the current definition for VAR. */
|
|
|
tree
|
tree
|
get_current_def (tree var)
|
get_current_def (tree var)
|
{
|
{
|
if (TREE_CODE (var) == SSA_NAME)
|
if (TREE_CODE (var) == SSA_NAME)
|
return get_ssa_name_ann (var)->current_def;
|
return get_ssa_name_ann (var)->current_def;
|
else
|
else
|
return var_ann (var)->current_def;
|
return var_ann (var)->current_def;
|
}
|
}
|
|
|
|
|
/* Sets current definition of VAR to DEF. */
|
/* Sets current definition of VAR to DEF. */
|
|
|
void
|
void
|
set_current_def (tree var, tree def)
|
set_current_def (tree var, tree def)
|
{
|
{
|
if (TREE_CODE (var) == SSA_NAME)
|
if (TREE_CODE (var) == SSA_NAME)
|
get_ssa_name_ann (var)->current_def = def;
|
get_ssa_name_ann (var)->current_def = def;
|
else
|
else
|
var_ann (var)->current_def = def;
|
var_ann (var)->current_def = def;
|
}
|
}
|
|
|
|
|
/* Compute global livein information given the set of blockx where
|
/* Compute global livein information given the set of blockx where
|
an object is locally live at the start of the block (LIVEIN)
|
an object is locally live at the start of the block (LIVEIN)
|
and the set of blocks where the object is defined (DEF_BLOCKS).
|
and the set of blocks where the object is defined (DEF_BLOCKS).
|
|
|
Note: This routine augments the existing local livein information
|
Note: This routine augments the existing local livein information
|
to include global livein (i.e., it modifies the underlying bitmap
|
to include global livein (i.e., it modifies the underlying bitmap
|
for LIVEIN). */
|
for LIVEIN). */
|
|
|
void
|
void
|
compute_global_livein (bitmap livein, bitmap def_blocks)
|
compute_global_livein (bitmap livein, bitmap def_blocks)
|
{
|
{
|
basic_block bb, *worklist, *tos;
|
basic_block bb, *worklist, *tos;
|
unsigned i;
|
unsigned i;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
|
|
tos = worklist
|
tos = worklist
|
= (basic_block *) xmalloc (sizeof (basic_block) * (last_basic_block + 1));
|
= (basic_block *) xmalloc (sizeof (basic_block) * (last_basic_block + 1));
|
|
|
EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
|
{
|
{
|
*tos++ = BASIC_BLOCK (i);
|
*tos++ = BASIC_BLOCK (i);
|
}
|
}
|
|
|
/* Iterate until the worklist is empty. */
|
/* Iterate until the worklist is empty. */
|
while (tos != worklist)
|
while (tos != worklist)
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
/* Pull a block off the worklist. */
|
/* Pull a block off the worklist. */
|
bb = *--tos;
|
bb = *--tos;
|
|
|
/* For each predecessor block. */
|
/* For each predecessor block. */
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
{
|
{
|
basic_block pred = e->src;
|
basic_block pred = e->src;
|
int pred_index = pred->index;
|
int pred_index = pred->index;
|
|
|
/* None of this is necessary for the entry block. */
|
/* None of this is necessary for the entry block. */
|
if (pred != ENTRY_BLOCK_PTR
|
if (pred != ENTRY_BLOCK_PTR
|
&& ! bitmap_bit_p (livein, pred_index)
|
&& ! bitmap_bit_p (livein, pred_index)
|
&& ! bitmap_bit_p (def_blocks, pred_index))
|
&& ! bitmap_bit_p (def_blocks, pred_index))
|
{
|
{
|
*tos++ = pred;
|
*tos++ = pred;
|
bitmap_set_bit (livein, pred_index);
|
bitmap_set_bit (livein, pred_index);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
free (worklist);
|
free (worklist);
|
}
|
}
|
|
|
|
|
/* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
|
/* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
|
all statements in basic block BB. */
|
all statements in basic block BB. */
|
|
|
static void
|
static void
|
initialize_flags_in_bb (basic_block bb)
|
initialize_flags_in_bb (basic_block bb)
|
{
|
{
|
tree phi, stmt;
|
tree phi, stmt;
|
block_stmt_iterator bsi;
|
block_stmt_iterator bsi;
|
|
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
{
|
{
|
REWRITE_THIS_STMT (phi) = 0;
|
REWRITE_THIS_STMT (phi) = 0;
|
REGISTER_DEFS_IN_THIS_STMT (phi) = 0;
|
REGISTER_DEFS_IN_THIS_STMT (phi) = 0;
|
}
|
}
|
|
|
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
|
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
|
{
|
{
|
stmt = bsi_stmt (bsi);
|
stmt = bsi_stmt (bsi);
|
/* We are going to use the operand cache API, such as
|
/* We are going to use the operand cache API, such as
|
SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
|
SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
|
cache for each statement should be up-to-date. */
|
cache for each statement should be up-to-date. */
|
gcc_assert (!stmt_modified_p (stmt));
|
gcc_assert (!stmt_modified_p (stmt));
|
REWRITE_THIS_STMT (stmt) = 0;
|
REWRITE_THIS_STMT (stmt) = 0;
|
REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
|
REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
|
}
|
}
|
}
|
}
|
|
|
/* Mark block BB as interesting for update_ssa. */
|
/* Mark block BB as interesting for update_ssa. */
|
|
|
static void
|
static void
|
mark_block_for_update (basic_block bb)
|
mark_block_for_update (basic_block bb)
|
{
|
{
|
gcc_assert (blocks_to_update != NULL);
|
gcc_assert (blocks_to_update != NULL);
|
if (bitmap_bit_p (blocks_to_update, bb->index))
|
if (bitmap_bit_p (blocks_to_update, bb->index))
|
return;
|
return;
|
bitmap_set_bit (blocks_to_update, bb->index);
|
bitmap_set_bit (blocks_to_update, bb->index);
|
initialize_flags_in_bb (bb);
|
initialize_flags_in_bb (bb);
|
}
|
}
|
|
|
/* Return the set of blocks where variable VAR is defined and the blocks
|
/* Return the set of blocks where variable VAR is defined and the blocks
|
where VAR is live on entry (livein). If no entry is found in
|
where VAR is live on entry (livein). If no entry is found in
|
DEF_BLOCKS, a new one is created and returned. */
|
DEF_BLOCKS, a new one is created and returned. */
|
|
|
static inline struct def_blocks_d *
|
static inline struct def_blocks_d *
|
get_def_blocks_for (tree var)
|
get_def_blocks_for (tree var)
|
{
|
{
|
struct def_blocks_d db, *db_p;
|
struct def_blocks_d db, *db_p;
|
void **slot;
|
void **slot;
|
|
|
db.var = var;
|
db.var = var;
|
slot = htab_find_slot (def_blocks, (void *) &db, INSERT);
|
slot = htab_find_slot (def_blocks, (void *) &db, INSERT);
|
if (*slot == NULL)
|
if (*slot == NULL)
|
{
|
{
|
db_p = XNEW (struct def_blocks_d);
|
db_p = XNEW (struct def_blocks_d);
|
db_p->var = var;
|
db_p->var = var;
|
db_p->def_blocks = BITMAP_ALLOC (NULL);
|
db_p->def_blocks = BITMAP_ALLOC (NULL);
|
db_p->phi_blocks = BITMAP_ALLOC (NULL);
|
db_p->phi_blocks = BITMAP_ALLOC (NULL);
|
db_p->livein_blocks = BITMAP_ALLOC (NULL);
|
db_p->livein_blocks = BITMAP_ALLOC (NULL);
|
*slot = (void *) db_p;
|
*slot = (void *) db_p;
|
}
|
}
|
else
|
else
|
db_p = (struct def_blocks_d *) *slot;
|
db_p = (struct def_blocks_d *) *slot;
|
|
|
return db_p;
|
return db_p;
|
}
|
}
|
|
|
|
|
/* Mark block BB as the definition site for variable VAR. PHI_P is true if
|
/* Mark block BB as the definition site for variable VAR. PHI_P is true if
|
VAR is defined by a PHI node. */
|
VAR is defined by a PHI node. */
|
|
|
static void
|
static void
|
set_def_block (tree var, basic_block bb, bool phi_p)
|
set_def_block (tree var, basic_block bb, bool phi_p)
|
{
|
{
|
struct def_blocks_d *db_p;
|
struct def_blocks_d *db_p;
|
enum need_phi_state state;
|
enum need_phi_state state;
|
|
|
state = get_phi_state (var);
|
state = get_phi_state (var);
|
db_p = get_def_blocks_for (var);
|
db_p = get_def_blocks_for (var);
|
|
|
/* Set the bit corresponding to the block where VAR is defined. */
|
/* Set the bit corresponding to the block where VAR is defined. */
|
bitmap_set_bit (db_p->def_blocks, bb->index);
|
bitmap_set_bit (db_p->def_blocks, bb->index);
|
if (phi_p)
|
if (phi_p)
|
bitmap_set_bit (db_p->phi_blocks, bb->index);
|
bitmap_set_bit (db_p->phi_blocks, bb->index);
|
|
|
/* Keep track of whether or not we may need to insert PHI nodes.
|
/* Keep track of whether or not we may need to insert PHI nodes.
|
|
|
If we are in the UNKNOWN state, then this is the first definition
|
If we are in the UNKNOWN state, then this is the first definition
|
of VAR. Additionally, we have not seen any uses of VAR yet, so
|
of VAR. Additionally, we have not seen any uses of VAR yet, so
|
we do not need a PHI node for this variable at this time (i.e.,
|
we do not need a PHI node for this variable at this time (i.e.,
|
transition to NEED_PHI_STATE_NO).
|
transition to NEED_PHI_STATE_NO).
|
|
|
If we are in any other state, then we either have multiple definitions
|
If we are in any other state, then we either have multiple definitions
|
of this variable occurring in different blocks or we saw a use of the
|
of this variable occurring in different blocks or we saw a use of the
|
variable which was not dominated by the block containing the
|
variable which was not dominated by the block containing the
|
definition(s). In this case we may need a PHI node, so enter
|
definition(s). In this case we may need a PHI node, so enter
|
state NEED_PHI_STATE_MAYBE. */
|
state NEED_PHI_STATE_MAYBE. */
|
if (state == NEED_PHI_STATE_UNKNOWN)
|
if (state == NEED_PHI_STATE_UNKNOWN)
|
set_phi_state (var, NEED_PHI_STATE_NO);
|
set_phi_state (var, NEED_PHI_STATE_NO);
|
else
|
else
|
set_phi_state (var, NEED_PHI_STATE_MAYBE);
|
set_phi_state (var, NEED_PHI_STATE_MAYBE);
|
}
|
}
|
|
|
|
|
/* Mark block BB as having VAR live at the entry to BB. */
|
/* Mark block BB as having VAR live at the entry to BB. */
|
|
|
static void
|
static void
|
set_livein_block (tree var, basic_block bb)
|
set_livein_block (tree var, basic_block bb)
|
{
|
{
|
struct def_blocks_d *db_p;
|
struct def_blocks_d *db_p;
|
enum need_phi_state state = get_phi_state (var);
|
enum need_phi_state state = get_phi_state (var);
|
|
|
db_p = get_def_blocks_for (var);
|
db_p = get_def_blocks_for (var);
|
|
|
/* Set the bit corresponding to the block where VAR is live in. */
|
/* Set the bit corresponding to the block where VAR is live in. */
|
bitmap_set_bit (db_p->livein_blocks, bb->index);
|
bitmap_set_bit (db_p->livein_blocks, bb->index);
|
|
|
/* Keep track of whether or not we may need to insert PHI nodes.
|
/* Keep track of whether or not we may need to insert PHI nodes.
|
|
|
If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
|
If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
|
by the single block containing the definition(s) of this variable. If
|
by the single block containing the definition(s) of this variable. If
|
it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
|
it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
|
NEED_PHI_STATE_MAYBE. */
|
NEED_PHI_STATE_MAYBE. */
|
if (state == NEED_PHI_STATE_NO)
|
if (state == NEED_PHI_STATE_NO)
|
{
|
{
|
int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
|
int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
|
|
|
if (def_block_index == -1
|
if (def_block_index == -1
|
|| ! dominated_by_p (CDI_DOMINATORS, bb,
|
|| ! dominated_by_p (CDI_DOMINATORS, bb,
|
BASIC_BLOCK (def_block_index)))
|
BASIC_BLOCK (def_block_index)))
|
set_phi_state (var, NEED_PHI_STATE_MAYBE);
|
set_phi_state (var, NEED_PHI_STATE_MAYBE);
|
}
|
}
|
else
|
else
|
set_phi_state (var, NEED_PHI_STATE_MAYBE);
|
set_phi_state (var, NEED_PHI_STATE_MAYBE);
|
}
|
}
|
|
|
|
|
/* Return true if symbol SYM is marked for renaming. */
|
/* Return true if symbol SYM is marked for renaming. */
|
|
|
static inline bool
|
static inline bool
|
symbol_marked_for_renaming (tree sym)
|
symbol_marked_for_renaming (tree sym)
|
{
|
{
|
gcc_assert (DECL_P (sym));
|
gcc_assert (DECL_P (sym));
|
return bitmap_bit_p (syms_to_rename, DECL_UID (sym));
|
return bitmap_bit_p (syms_to_rename, DECL_UID (sym));
|
}
|
}
|
|
|
|
|
/* Return true if NAME is in OLD_SSA_NAMES. */
|
/* Return true if NAME is in OLD_SSA_NAMES. */
|
|
|
static inline bool
|
static inline bool
|
is_old_name (tree name)
|
is_old_name (tree name)
|
{
|
{
|
unsigned ver = SSA_NAME_VERSION (name);
|
unsigned ver = SSA_NAME_VERSION (name);
|
return ver < new_ssa_names->n_bits && TEST_BIT (old_ssa_names, ver);
|
return ver < new_ssa_names->n_bits && TEST_BIT (old_ssa_names, ver);
|
}
|
}
|
|
|
|
|
/* Return true if NAME is in NEW_SSA_NAMES. */
|
/* Return true if NAME is in NEW_SSA_NAMES. */
|
|
|
static inline bool
|
static inline bool
|
is_new_name (tree name)
|
is_new_name (tree name)
|
{
|
{
|
unsigned ver = SSA_NAME_VERSION (name);
|
unsigned ver = SSA_NAME_VERSION (name);
|
return ver < new_ssa_names->n_bits && TEST_BIT (new_ssa_names, ver);
|
return ver < new_ssa_names->n_bits && TEST_BIT (new_ssa_names, ver);
|
}
|
}
|
|
|
|
|
/* Hashing and equality functions for REPL_TBL. */
|
/* Hashing and equality functions for REPL_TBL. */
|
|
|
static hashval_t
|
static hashval_t
|
repl_map_hash (const void *p)
|
repl_map_hash (const void *p)
|
{
|
{
|
return htab_hash_pointer ((const void *)((const struct repl_map_d *)p)->name);
|
return htab_hash_pointer ((const void *)((const struct repl_map_d *)p)->name);
|
}
|
}
|
|
|
static int
|
static int
|
repl_map_eq (const void *p1, const void *p2)
|
repl_map_eq (const void *p1, const void *p2)
|
{
|
{
|
return ((const struct repl_map_d *)p1)->name
|
return ((const struct repl_map_d *)p1)->name
|
== ((const struct repl_map_d *)p2)->name;
|
== ((const struct repl_map_d *)p2)->name;
|
}
|
}
|
|
|
static void
|
static void
|
repl_map_free (void *p)
|
repl_map_free (void *p)
|
{
|
{
|
BITMAP_FREE (((struct repl_map_d *)p)->set);
|
BITMAP_FREE (((struct repl_map_d *)p)->set);
|
free (p);
|
free (p);
|
}
|
}
|
|
|
|
|
/* Return the names replaced by NEW (i.e., REPL_TBL[NEW].SET). */
|
/* Return the names replaced by NEW (i.e., REPL_TBL[NEW].SET). */
|
|
|
static inline bitmap
|
static inline bitmap
|
names_replaced_by (tree new)
|
names_replaced_by (tree new)
|
{
|
{
|
struct repl_map_d m;
|
struct repl_map_d m;
|
void **slot;
|
void **slot;
|
|
|
m.name = new;
|
m.name = new;
|
slot = htab_find_slot (repl_tbl, (void *) &m, NO_INSERT);
|
slot = htab_find_slot (repl_tbl, (void *) &m, NO_INSERT);
|
|
|
/* If N was not registered in the replacement table, return NULL. */
|
/* If N was not registered in the replacement table, return NULL. */
|
if (slot == NULL || *slot == NULL)
|
if (slot == NULL || *slot == NULL)
|
return NULL;
|
return NULL;
|
|
|
return ((struct repl_map_d *) *slot)->set;
|
return ((struct repl_map_d *) *slot)->set;
|
}
|
}
|
|
|
|
|
/* Add OLD to REPL_TBL[NEW].SET. */
|
/* Add OLD to REPL_TBL[NEW].SET. */
|
|
|
static inline void
|
static inline void
|
add_to_repl_tbl (tree new, tree old)
|
add_to_repl_tbl (tree new, tree old)
|
{
|
{
|
struct repl_map_d m, *mp;
|
struct repl_map_d m, *mp;
|
void **slot;
|
void **slot;
|
|
|
m.name = new;
|
m.name = new;
|
slot = htab_find_slot (repl_tbl, (void *) &m, INSERT);
|
slot = htab_find_slot (repl_tbl, (void *) &m, INSERT);
|
if (*slot == NULL)
|
if (*slot == NULL)
|
{
|
{
|
mp = XNEW (struct repl_map_d);
|
mp = XNEW (struct repl_map_d);
|
mp->name = new;
|
mp->name = new;
|
mp->set = BITMAP_ALLOC (NULL);
|
mp->set = BITMAP_ALLOC (NULL);
|
*slot = (void *) mp;
|
*slot = (void *) mp;
|
}
|
}
|
else
|
else
|
mp = (struct repl_map_d *) *slot;
|
mp = (struct repl_map_d *) *slot;
|
|
|
bitmap_set_bit (mp->set, SSA_NAME_VERSION (old));
|
bitmap_set_bit (mp->set, SSA_NAME_VERSION (old));
|
}
|
}
|
|
|
|
|
/* Add a new mapping NEW -> OLD REPL_TBL. Every entry N_i in REPL_TBL
|
/* Add a new mapping NEW -> OLD REPL_TBL. Every entry N_i in REPL_TBL
|
represents the set of names O_1 ... O_j replaced by N_i. This is
|
represents the set of names O_1 ... O_j replaced by N_i. This is
|
used by update_ssa and its helpers to introduce new SSA names in an
|
used by update_ssa and its helpers to introduce new SSA names in an
|
already formed SSA web. */
|
already formed SSA web. */
|
|
|
static void
|
static void
|
add_new_name_mapping (tree new, tree old)
|
add_new_name_mapping (tree new, tree old)
|
{
|
{
|
timevar_push (TV_TREE_SSA_INCREMENTAL);
|
timevar_push (TV_TREE_SSA_INCREMENTAL);
|
|
|
/* OLD and NEW must be different SSA names for the same symbol. */
|
/* OLD and NEW must be different SSA names for the same symbol. */
|
gcc_assert (new != old && SSA_NAME_VAR (new) == SSA_NAME_VAR (old));
|
gcc_assert (new != old && SSA_NAME_VAR (new) == SSA_NAME_VAR (old));
|
|
|
/* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
|
/* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
|
caller may have created new names since the set was created. */
|
caller may have created new names since the set was created. */
|
if (new_ssa_names->n_bits <= num_ssa_names - 1)
|
if (new_ssa_names->n_bits <= num_ssa_names - 1)
|
{
|
{
|
unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
|
unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
|
new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
|
new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
|
old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
|
old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
|
}
|
}
|
|
|
/* If this mapping is for virtual names, we will need to update
|
/* If this mapping is for virtual names, we will need to update
|
virtual operands. */
|
virtual operands. */
|
if (!is_gimple_reg (new))
|
if (!is_gimple_reg (new))
|
{
|
{
|
tree sym;
|
tree sym;
|
size_t uid;
|
size_t uid;
|
|
|
need_to_update_vops_p = true;
|
need_to_update_vops_p = true;
|
|
|
/* Keep counts of virtual mappings and symbols to use in the
|
/* Keep counts of virtual mappings and symbols to use in the
|
virtual mapping heuristic. If we have large numbers of
|
virtual mapping heuristic. If we have large numbers of
|
virtual mappings for a relatively low number of symbols, it
|
virtual mappings for a relatively low number of symbols, it
|
will make more sense to rename the symbols from scratch.
|
will make more sense to rename the symbols from scratch.
|
Otherwise, the insertion of PHI nodes for each of the old
|
Otherwise, the insertion of PHI nodes for each of the old
|
names in these mappings will be very slow. */
|
names in these mappings will be very slow. */
|
sym = SSA_NAME_VAR (new);
|
sym = SSA_NAME_VAR (new);
|
uid = DECL_UID (sym);
|
uid = DECL_UID (sym);
|
update_ssa_stats.num_virtual_mappings++;
|
update_ssa_stats.num_virtual_mappings++;
|
if (!bitmap_bit_p (update_ssa_stats.virtual_symbols, uid))
|
if (!bitmap_bit_p (update_ssa_stats.virtual_symbols, uid))
|
{
|
{
|
bitmap_set_bit (update_ssa_stats.virtual_symbols, uid);
|
bitmap_set_bit (update_ssa_stats.virtual_symbols, uid);
|
update_ssa_stats.num_virtual_symbols++;
|
update_ssa_stats.num_virtual_symbols++;
|
}
|
}
|
}
|
}
|
|
|
/* Update the REPL_TBL table. */
|
/* Update the REPL_TBL table. */
|
add_to_repl_tbl (new, old);
|
add_to_repl_tbl (new, old);
|
|
|
/* If OLD had already been registered as a new name, then all the
|
/* If OLD had already been registered as a new name, then all the
|
names that OLD replaces should also be replaced by NEW. */
|
names that OLD replaces should also be replaced by NEW. */
|
if (is_new_name (old))
|
if (is_new_name (old))
|
bitmap_ior_into (names_replaced_by (new), names_replaced_by (old));
|
bitmap_ior_into (names_replaced_by (new), names_replaced_by (old));
|
|
|
/* Register NEW and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
|
/* Register NEW and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
|
respectively. */
|
respectively. */
|
SET_BIT (new_ssa_names, SSA_NAME_VERSION (new));
|
SET_BIT (new_ssa_names, SSA_NAME_VERSION (new));
|
SET_BIT (old_ssa_names, SSA_NAME_VERSION (old));
|
SET_BIT (old_ssa_names, SSA_NAME_VERSION (old));
|
|
|
/* Update mapping counter to use in the virtual mapping heuristic. */
|
/* Update mapping counter to use in the virtual mapping heuristic. */
|
update_ssa_stats.num_total_mappings++;
|
update_ssa_stats.num_total_mappings++;
|
|
|
timevar_pop (TV_TREE_SSA_INCREMENTAL);
|
timevar_pop (TV_TREE_SSA_INCREMENTAL);
|
}
|
}
|
|
|
|
|
/* Call back for walk_dominator_tree used to collect definition sites
|
/* Call back for walk_dominator_tree used to collect definition sites
|
for every variable in the function. For every statement S in block
|
for every variable in the function. For every statement S in block
|
BB:
|
BB:
|
|
|
1- Variables defined by S in the DEFS of S are marked in the bitmap
|
1- Variables defined by S in the DEFS of S are marked in the bitmap
|
WALK_DATA->GLOBAL_DATA->KILLS.
|
WALK_DATA->GLOBAL_DATA->KILLS.
|
|
|
2- If S uses a variable VAR and there is no preceding kill of VAR,
|
2- If S uses a variable VAR and there is no preceding kill of VAR,
|
then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
|
then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
|
|
|
This information is used to determine which variables are live
|
This information is used to determine which variables are live
|
across block boundaries to reduce the number of PHI nodes
|
across block boundaries to reduce the number of PHI nodes
|
we create. */
|
we create. */
|
|
|
static void
|
static void
|
mark_def_sites (struct dom_walk_data *walk_data,
|
mark_def_sites (struct dom_walk_data *walk_data,
|
basic_block bb,
|
basic_block bb,
|
block_stmt_iterator bsi)
|
block_stmt_iterator bsi)
|
{
|
{
|
struct mark_def_sites_global_data *gd =
|
struct mark_def_sites_global_data *gd =
|
(struct mark_def_sites_global_data *) walk_data->global_data;
|
(struct mark_def_sites_global_data *) walk_data->global_data;
|
bitmap kills = gd->kills;
|
bitmap kills = gd->kills;
|
tree stmt, def;
|
tree stmt, def;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
def_operand_p def_p;
|
def_operand_p def_p;
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
|
|
stmt = bsi_stmt (bsi);
|
stmt = bsi_stmt (bsi);
|
update_stmt_if_modified (stmt);
|
update_stmt_if_modified (stmt);
|
|
|
gcc_assert (blocks_to_update == NULL);
|
gcc_assert (blocks_to_update == NULL);
|
REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
|
REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
|
REWRITE_THIS_STMT (stmt) = 0;
|
REWRITE_THIS_STMT (stmt) = 0;
|
|
|
/* If a variable is used before being set, then the variable is live
|
/* If a variable is used before being set, then the variable is live
|
across a block boundary, so mark it live-on-entry to BB. */
|
across a block boundary, so mark it live-on-entry to BB. */
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
|
SSA_OP_USE | SSA_OP_VUSE | SSA_OP_VMUSTKILL)
|
SSA_OP_USE | SSA_OP_VUSE | SSA_OP_VMUSTKILL)
|
{
|
{
|
tree sym = USE_FROM_PTR (use_p);
|
tree sym = USE_FROM_PTR (use_p);
|
gcc_assert (DECL_P (sym));
|
gcc_assert (DECL_P (sym));
|
if (!bitmap_bit_p (kills, DECL_UID (sym)))
|
if (!bitmap_bit_p (kills, DECL_UID (sym)))
|
set_livein_block (sym, bb);
|
set_livein_block (sym, bb);
|
REWRITE_THIS_STMT (stmt) = 1;
|
REWRITE_THIS_STMT (stmt) = 1;
|
}
|
}
|
|
|
/* Note that virtual definitions are irrelevant for computing KILLS
|
/* Note that virtual definitions are irrelevant for computing KILLS
|
because a V_MAY_DEF does not constitute a killing definition of the
|
because a V_MAY_DEF does not constitute a killing definition of the
|
variable. However, the operand of a virtual definitions is a use
|
variable. However, the operand of a virtual definitions is a use
|
of the variable, so it may cause the variable to be considered
|
of the variable, so it may cause the variable to be considered
|
live-on-entry. */
|
live-on-entry. */
|
FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
|
FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
|
{
|
{
|
tree sym = USE_FROM_PTR (use_p);
|
tree sym = USE_FROM_PTR (use_p);
|
gcc_assert (DECL_P (sym));
|
gcc_assert (DECL_P (sym));
|
set_livein_block (sym, bb);
|
set_livein_block (sym, bb);
|
set_def_block (sym, bb, false);
|
set_def_block (sym, bb, false);
|
REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
|
REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
|
REWRITE_THIS_STMT (stmt) = 1;
|
REWRITE_THIS_STMT (stmt) = 1;
|
}
|
}
|
|
|
/* Now process the defs and must-defs made by this statement. */
|
/* Now process the defs and must-defs made by this statement. */
|
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF | SSA_OP_VMUSTDEF)
|
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF | SSA_OP_VMUSTDEF)
|
{
|
{
|
gcc_assert (DECL_P (def));
|
gcc_assert (DECL_P (def));
|
set_def_block (def, bb, false);
|
set_def_block (def, bb, false);
|
bitmap_set_bit (kills, DECL_UID (def));
|
bitmap_set_bit (kills, DECL_UID (def));
|
REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
|
REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
|
}
|
}
|
|
|
/* If we found the statement interesting then also mark the block BB
|
/* If we found the statement interesting then also mark the block BB
|
as interesting. */
|
as interesting. */
|
if (REWRITE_THIS_STMT (stmt) || REGISTER_DEFS_IN_THIS_STMT (stmt))
|
if (REWRITE_THIS_STMT (stmt) || REGISTER_DEFS_IN_THIS_STMT (stmt))
|
SET_BIT (gd->interesting_blocks, bb->index);
|
SET_BIT (gd->interesting_blocks, bb->index);
|
}
|
}
|
|
|
/* Structure used by prune_unused_phi_nodes to record bounds of the intervals
|
/* Structure used by prune_unused_phi_nodes to record bounds of the intervals
|
in the dfs numbering of the dominance tree. */
|
in the dfs numbering of the dominance tree. */
|
|
|
struct dom_dfsnum
|
struct dom_dfsnum
|
{
|
{
|
/* Basic block whose index this entry corresponds to. */
|
/* Basic block whose index this entry corresponds to. */
|
unsigned bb_index;
|
unsigned bb_index;
|
|
|
/* The dfs number of this node. */
|
/* The dfs number of this node. */
|
unsigned dfs_num;
|
unsigned dfs_num;
|
};
|
};
|
|
|
/* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
|
/* Compares two entries of type struct dom_dfsnum by dfs_num field. Callback
|
for qsort. */
|
for qsort. */
|
|
|
static int
|
static int
|
cmp_dfsnum (const void *a, const void *b)
|
cmp_dfsnum (const void *a, const void *b)
|
{
|
{
|
const struct dom_dfsnum *da = a;
|
const struct dom_dfsnum *da = a;
|
const struct dom_dfsnum *db = b;
|
const struct dom_dfsnum *db = b;
|
|
|
return (int) da->dfs_num - (int) db->dfs_num;
|
return (int) da->dfs_num - (int) db->dfs_num;
|
}
|
}
|
|
|
/* Among the intervals starting at the N points specified in DEFS, find
|
/* Among the intervals starting at the N points specified in DEFS, find
|
the one that contains S, and return its bb_index. */
|
the one that contains S, and return its bb_index. */
|
|
|
static unsigned
|
static unsigned
|
find_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s)
|
find_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s)
|
{
|
{
|
unsigned f = 0, t = n, m;
|
unsigned f = 0, t = n, m;
|
|
|
while (t > f + 1)
|
while (t > f + 1)
|
{
|
{
|
m = (f + t) / 2;
|
m = (f + t) / 2;
|
if (defs[m].dfs_num <= s)
|
if (defs[m].dfs_num <= s)
|
f = m;
|
f = m;
|
else
|
else
|
t = m;
|
t = m;
|
}
|
}
|
|
|
return defs[f].bb_index;
|
return defs[f].bb_index;
|
}
|
}
|
|
|
/* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
|
/* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
|
KILLS is a bitmap of blocks where the value is defined before any use. */
|
KILLS is a bitmap of blocks where the value is defined before any use. */
|
|
|
static void
|
static void
|
prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses)
|
prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses)
|
{
|
{
|
VEC(int, heap) *worklist;
|
VEC(int, heap) *worklist;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
unsigned i, b, p, u, top;
|
unsigned i, b, p, u, top;
|
bitmap live_phis;
|
bitmap live_phis;
|
basic_block def_bb, use_bb;
|
basic_block def_bb, use_bb;
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
bitmap to_remove;
|
bitmap to_remove;
|
struct dom_dfsnum *defs;
|
struct dom_dfsnum *defs;
|
unsigned n_defs, adef;
|
unsigned n_defs, adef;
|
|
|
if (bitmap_empty_p (uses))
|
if (bitmap_empty_p (uses))
|
{
|
{
|
bitmap_clear (phis);
|
bitmap_clear (phis);
|
return;
|
return;
|
}
|
}
|
|
|
/* The phi must dominate a use, or an argument of a live phi. Also, we
|
/* The phi must dominate a use, or an argument of a live phi. Also, we
|
do not create any phi nodes in def blocks, unless they are also livein. */
|
do not create any phi nodes in def blocks, unless they are also livein. */
|
to_remove = BITMAP_ALLOC (NULL);
|
to_remove = BITMAP_ALLOC (NULL);
|
bitmap_and_compl (to_remove, kills, uses);
|
bitmap_and_compl (to_remove, kills, uses);
|
bitmap_and_compl_into (phis, to_remove);
|
bitmap_and_compl_into (phis, to_remove);
|
if (bitmap_empty_p (phis))
|
if (bitmap_empty_p (phis))
|
{
|
{
|
BITMAP_FREE (to_remove);
|
BITMAP_FREE (to_remove);
|
return;
|
return;
|
}
|
}
|
|
|
/* We want to remove the unnecessary phi nodes, but we do not want to compute
|
/* We want to remove the unnecessary phi nodes, but we do not want to compute
|
liveness information, as that may be linear in the size of CFG, and if
|
liveness information, as that may be linear in the size of CFG, and if
|
there are lot of different variables to rewrite, this may lead to quadratic
|
there are lot of different variables to rewrite, this may lead to quadratic
|
behavior.
|
behavior.
|
|
|
Instead, we basically emulate standard dce. We put all uses to worklist,
|
Instead, we basically emulate standard dce. We put all uses to worklist,
|
then for each of them find the nearest def that dominates them. If this
|
then for each of them find the nearest def that dominates them. If this
|
def is a phi node, we mark it live, and if it was not live before, we
|
def is a phi node, we mark it live, and if it was not live before, we
|
add the predecessors of its basic block to the worklist.
|
add the predecessors of its basic block to the worklist.
|
|
|
To quickly locate the nearest def that dominates use, we use dfs numbering
|
To quickly locate the nearest def that dominates use, we use dfs numbering
|
of the dominance tree (that is already available in order to speed up
|
of the dominance tree (that is already available in order to speed up
|
queries). For each def, we have the interval given by the dfs number on
|
queries). For each def, we have the interval given by the dfs number on
|
entry to and on exit from the corresponding subtree in the dominance tree.
|
entry to and on exit from the corresponding subtree in the dominance tree.
|
The nearest dominator for a given use is the smallest of these intervals
|
The nearest dominator for a given use is the smallest of these intervals
|
that contains entry and exit dfs numbers for the basic block with the use.
|
that contains entry and exit dfs numbers for the basic block with the use.
|
If we store the bounds for all the uses to an array and sort it, we can
|
If we store the bounds for all the uses to an array and sort it, we can
|
locate the nearest dominating def in logarithmic time by binary search.*/
|
locate the nearest dominating def in logarithmic time by binary search.*/
|
bitmap_ior (to_remove, kills, phis);
|
bitmap_ior (to_remove, kills, phis);
|
n_defs = bitmap_count_bits (to_remove);
|
n_defs = bitmap_count_bits (to_remove);
|
defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1);
|
defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1);
|
defs[0].bb_index = 1;
|
defs[0].bb_index = 1;
|
defs[0].dfs_num = 0;
|
defs[0].dfs_num = 0;
|
adef = 1;
|
adef = 1;
|
EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi)
|
{
|
{
|
def_bb = BASIC_BLOCK (i);
|
def_bb = BASIC_BLOCK (i);
|
defs[adef].bb_index = i;
|
defs[adef].bb_index = i;
|
defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb);
|
defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb);
|
defs[adef + 1].bb_index = i;
|
defs[adef + 1].bb_index = i;
|
defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb);
|
defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb);
|
adef += 2;
|
adef += 2;
|
}
|
}
|
BITMAP_FREE (to_remove);
|
BITMAP_FREE (to_remove);
|
gcc_assert (adef == 2 * n_defs + 1);
|
gcc_assert (adef == 2 * n_defs + 1);
|
qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum);
|
qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum);
|
gcc_assert (defs[0].bb_index == 1);
|
gcc_assert (defs[0].bb_index == 1);
|
|
|
/* Now each DEFS entry contains the number of the basic block to that the
|
/* Now each DEFS entry contains the number of the basic block to that the
|
dfs number corresponds. Change them to the number of basic block that
|
dfs number corresponds. Change them to the number of basic block that
|
corresponds to the interval following the dfs number. Also, for the
|
corresponds to the interval following the dfs number. Also, for the
|
dfs_out numbers, increase the dfs number by one (so that it corresponds
|
dfs_out numbers, increase the dfs number by one (so that it corresponds
|
to the start of the following interval, not to the end of the current
|
to the start of the following interval, not to the end of the current
|
one). We use WORKLIST as a stack. */
|
one). We use WORKLIST as a stack. */
|
worklist = VEC_alloc (int, heap, n_defs + 1);
|
worklist = VEC_alloc (int, heap, n_defs + 1);
|
VEC_quick_push (int, worklist, 1);
|
VEC_quick_push (int, worklist, 1);
|
top = 1;
|
top = 1;
|
n_defs = 1;
|
n_defs = 1;
|
for (i = 1; i < adef; i++)
|
for (i = 1; i < adef; i++)
|
{
|
{
|
b = defs[i].bb_index;
|
b = defs[i].bb_index;
|
if (b == top)
|
if (b == top)
|
{
|
{
|
/* This is a closing element. Interval corresponding to the top
|
/* This is a closing element. Interval corresponding to the top
|
of the stack after removing it follows. */
|
of the stack after removing it follows. */
|
VEC_pop (int, worklist);
|
VEC_pop (int, worklist);
|
top = VEC_index (int, worklist, VEC_length (int, worklist) - 1);
|
top = VEC_index (int, worklist, VEC_length (int, worklist) - 1);
|
defs[n_defs].bb_index = top;
|
defs[n_defs].bb_index = top;
|
defs[n_defs].dfs_num = defs[i].dfs_num + 1;
|
defs[n_defs].dfs_num = defs[i].dfs_num + 1;
|
}
|
}
|
else
|
else
|
{
|
{
|
/* Opening element. Nothing to do, just push it to the stack and move
|
/* Opening element. Nothing to do, just push it to the stack and move
|
it to the correct position. */
|
it to the correct position. */
|
defs[n_defs].bb_index = defs[i].bb_index;
|
defs[n_defs].bb_index = defs[i].bb_index;
|
defs[n_defs].dfs_num = defs[i].dfs_num;
|
defs[n_defs].dfs_num = defs[i].dfs_num;
|
VEC_quick_push (int, worklist, b);
|
VEC_quick_push (int, worklist, b);
|
top = b;
|
top = b;
|
}
|
}
|
|
|
/* If this interval starts at the same point as the previous one, cancel
|
/* If this interval starts at the same point as the previous one, cancel
|
the previous one. */
|
the previous one. */
|
if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num)
|
if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num)
|
defs[n_defs - 1].bb_index = defs[n_defs].bb_index;
|
defs[n_defs - 1].bb_index = defs[n_defs].bb_index;
|
else
|
else
|
n_defs++;
|
n_defs++;
|
}
|
}
|
VEC_pop (int, worklist);
|
VEC_pop (int, worklist);
|
gcc_assert (VEC_empty (int, worklist));
|
gcc_assert (VEC_empty (int, worklist));
|
|
|
/* Now process the uses. */
|
/* Now process the uses. */
|
live_phis = BITMAP_ALLOC (NULL);
|
live_phis = BITMAP_ALLOC (NULL);
|
EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi)
|
{
|
{
|
VEC_safe_push (int, heap, worklist, i);
|
VEC_safe_push (int, heap, worklist, i);
|
}
|
}
|
|
|
while (!VEC_empty (int, worklist))
|
while (!VEC_empty (int, worklist))
|
{
|
{
|
b = VEC_pop (int, worklist);
|
b = VEC_pop (int, worklist);
|
if (b == ENTRY_BLOCK)
|
if (b == ENTRY_BLOCK)
|
continue;
|
continue;
|
|
|
/* If there is a phi node in USE_BB, it is made live. Otherwise,
|
/* If there is a phi node in USE_BB, it is made live. Otherwise,
|
find the def that dominates the immediate dominator of USE_BB
|
find the def that dominates the immediate dominator of USE_BB
|
(the kill in USE_BB does not dominate the use). */
|
(the kill in USE_BB does not dominate the use). */
|
if (bitmap_bit_p (phis, b))
|
if (bitmap_bit_p (phis, b))
|
p = b;
|
p = b;
|
else
|
else
|
{
|
{
|
use_bb = get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (b));
|
use_bb = get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (b));
|
p = find_dfsnum_interval (defs, n_defs,
|
p = find_dfsnum_interval (defs, n_defs,
|
bb_dom_dfs_in (CDI_DOMINATORS, use_bb));
|
bb_dom_dfs_in (CDI_DOMINATORS, use_bb));
|
if (!bitmap_bit_p (phis, p))
|
if (!bitmap_bit_p (phis, p))
|
continue;
|
continue;
|
}
|
}
|
|
|
/* If the phi node is already live, there is nothing to do. */
|
/* If the phi node is already live, there is nothing to do. */
|
if (bitmap_bit_p (live_phis, p))
|
if (bitmap_bit_p (live_phis, p))
|
continue;
|
continue;
|
|
|
/* Mark the phi as live, and add the new uses to the worklist. */
|
/* Mark the phi as live, and add the new uses to the worklist. */
|
bitmap_set_bit (live_phis, p);
|
bitmap_set_bit (live_phis, p);
|
def_bb = BASIC_BLOCK (p);
|
def_bb = BASIC_BLOCK (p);
|
FOR_EACH_EDGE (e, ei, def_bb->preds)
|
FOR_EACH_EDGE (e, ei, def_bb->preds)
|
{
|
{
|
u = e->src->index;
|
u = e->src->index;
|
if (bitmap_bit_p (uses, u))
|
if (bitmap_bit_p (uses, u))
|
continue;
|
continue;
|
|
|
/* In case there is a kill directly in the use block, do not record
|
/* In case there is a kill directly in the use block, do not record
|
the use (this is also necessary for correctness, as we assume that
|
the use (this is also necessary for correctness, as we assume that
|
uses dominated by a def directly in their block have been filtered
|
uses dominated by a def directly in their block have been filtered
|
out before). */
|
out before). */
|
if (bitmap_bit_p (kills, u))
|
if (bitmap_bit_p (kills, u))
|
continue;
|
continue;
|
|
|
bitmap_set_bit (uses, u);
|
bitmap_set_bit (uses, u);
|
VEC_safe_push (int, heap, worklist, u);
|
VEC_safe_push (int, heap, worklist, u);
|
}
|
}
|
}
|
}
|
|
|
VEC_free (int, heap, worklist);
|
VEC_free (int, heap, worklist);
|
bitmap_copy (phis, live_phis);
|
bitmap_copy (phis, live_phis);
|
BITMAP_FREE (live_phis);
|
BITMAP_FREE (live_phis);
|
free (defs);
|
free (defs);
|
}
|
}
|
|
|
/* Given a set of blocks with variable definitions (DEF_BLOCKS),
|
/* Given a set of blocks with variable definitions (DEF_BLOCKS),
|
return a bitmap with all the blocks in the iterated dominance
|
return a bitmap with all the blocks in the iterated dominance
|
frontier of the blocks in DEF_BLOCKS. DFS contains dominance
|
frontier of the blocks in DEF_BLOCKS. DFS contains dominance
|
frontier information as returned by compute_dominance_frontiers.
|
frontier information as returned by compute_dominance_frontiers.
|
|
|
The resulting set of blocks are the potential sites where PHI nodes
|
The resulting set of blocks are the potential sites where PHI nodes
|
are needed. The caller is responsible from freeing the memory
|
are needed. The caller is responsible from freeing the memory
|
allocated for the return value. */
|
allocated for the return value. */
|
|
|
static bitmap
|
static bitmap
|
find_idf (bitmap def_blocks, bitmap *dfs)
|
find_idf (bitmap def_blocks, bitmap *dfs)
|
{
|
{
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
unsigned bb_index;
|
unsigned bb_index;
|
VEC(int,heap) *work_stack;
|
VEC(int,heap) *work_stack;
|
bitmap phi_insertion_points;
|
bitmap phi_insertion_points;
|
|
|
work_stack = VEC_alloc (int, heap, n_basic_blocks);
|
work_stack = VEC_alloc (int, heap, n_basic_blocks);
|
phi_insertion_points = BITMAP_ALLOC (NULL);
|
phi_insertion_points = BITMAP_ALLOC (NULL);
|
|
|
/* Seed the work list with all the blocks in DEF_BLOCKS. */
|
/* Seed the work list with all the blocks in DEF_BLOCKS. */
|
EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi)
|
EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi)
|
/* We use VEC_quick_push here for speed. This is safe because we
|
/* We use VEC_quick_push here for speed. This is safe because we
|
know that the number of definition blocks is no greater than
|
know that the number of definition blocks is no greater than
|
the number of basic blocks, which is the initial capacity of
|
the number of basic blocks, which is the initial capacity of
|
WORK_STACK. */
|
WORK_STACK. */
|
VEC_quick_push (int, work_stack, bb_index);
|
VEC_quick_push (int, work_stack, bb_index);
|
|
|
/* Pop a block off the worklist, add every block that appears in
|
/* Pop a block off the worklist, add every block that appears in
|
the original block's DF that we have not already processed to
|
the original block's DF that we have not already processed to
|
the worklist. Iterate until the worklist is empty. Blocks
|
the worklist. Iterate until the worklist is empty. Blocks
|
which are added to the worklist are potential sites for
|
which are added to the worklist are potential sites for
|
PHI nodes. */
|
PHI nodes. */
|
while (VEC_length (int, work_stack) > 0)
|
while (VEC_length (int, work_stack) > 0)
|
{
|
{
|
bb_index = VEC_pop (int, work_stack);
|
bb_index = VEC_pop (int, work_stack);
|
|
|
/* Since the registration of NEW -> OLD name mappings is done
|
/* Since the registration of NEW -> OLD name mappings is done
|
separately from the call to update_ssa, when updating the SSA
|
separately from the call to update_ssa, when updating the SSA
|
form, the basic blocks where new and/or old names are defined
|
form, the basic blocks where new and/or old names are defined
|
may have disappeared by CFG cleanup calls. In this case,
|
may have disappeared by CFG cleanup calls. In this case,
|
we may pull a non-existing block from the work stack. */
|
we may pull a non-existing block from the work stack. */
|
gcc_assert (bb_index < (unsigned) last_basic_block);
|
gcc_assert (bb_index < (unsigned) last_basic_block);
|
|
|
EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points,
|
EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points,
|
0, bb_index, bi)
|
0, bb_index, bi)
|
{
|
{
|
/* Use a safe push because if there is a definition of VAR
|
/* Use a safe push because if there is a definition of VAR
|
in every basic block, then WORK_STACK may eventually have
|
in every basic block, then WORK_STACK may eventually have
|
more than N_BASIC_BLOCK entries. */
|
more than N_BASIC_BLOCK entries. */
|
VEC_safe_push (int, heap, work_stack, bb_index);
|
VEC_safe_push (int, heap, work_stack, bb_index);
|
bitmap_set_bit (phi_insertion_points, bb_index);
|
bitmap_set_bit (phi_insertion_points, bb_index);
|
}
|
}
|
}
|
}
|
|
|
VEC_free (int, heap, work_stack);
|
VEC_free (int, heap, work_stack);
|
|
|
return phi_insertion_points;
|
return phi_insertion_points;
|
}
|
}
|
|
|
|
|
/* Return the set of blocks where variable VAR is defined and the blocks
|
/* Return the set of blocks where variable VAR is defined and the blocks
|
where VAR is live on entry (livein). Return NULL, if no entry is
|
where VAR is live on entry (livein). Return NULL, if no entry is
|
found in DEF_BLOCKS. */
|
found in DEF_BLOCKS. */
|
|
|
static inline struct def_blocks_d *
|
static inline struct def_blocks_d *
|
find_def_blocks_for (tree var)
|
find_def_blocks_for (tree var)
|
{
|
{
|
struct def_blocks_d dm;
|
struct def_blocks_d dm;
|
dm.var = var;
|
dm.var = var;
|
return (struct def_blocks_d *) htab_find (def_blocks, &dm);
|
return (struct def_blocks_d *) htab_find (def_blocks, &dm);
|
}
|
}
|
|
|
|
|
/* Retrieve or create a default definition for symbol SYM. */
|
/* Retrieve or create a default definition for symbol SYM. */
|
|
|
static inline tree
|
static inline tree
|
get_default_def_for (tree sym)
|
get_default_def_for (tree sym)
|
{
|
{
|
tree ddef = default_def (sym);
|
tree ddef = default_def (sym);
|
|
|
if (ddef == NULL_TREE)
|
if (ddef == NULL_TREE)
|
{
|
{
|
ddef = make_ssa_name (sym, build_empty_stmt ());
|
ddef = make_ssa_name (sym, build_empty_stmt ());
|
set_default_def (sym, ddef);
|
set_default_def (sym, ddef);
|
}
|
}
|
|
|
return ddef;
|
return ddef;
|
}
|
}
|
|
|
|
|
/* Marks phi node PHI in basic block BB for rewrite. */
|
/* Marks phi node PHI in basic block BB for rewrite. */
|
|
|
static void
|
static void
|
mark_phi_for_rewrite (basic_block bb, tree phi)
|
mark_phi_for_rewrite (basic_block bb, tree phi)
|
{
|
{
|
tree_vec phis;
|
tree_vec phis;
|
unsigned i, idx = bb->index;
|
unsigned i, idx = bb->index;
|
|
|
if (REWRITE_THIS_STMT (phi))
|
if (REWRITE_THIS_STMT (phi))
|
return;
|
return;
|
REWRITE_THIS_STMT (phi) = 1;
|
REWRITE_THIS_STMT (phi) = 1;
|
|
|
if (!blocks_with_phis_to_rewrite)
|
if (!blocks_with_phis_to_rewrite)
|
return;
|
return;
|
|
|
bitmap_set_bit (blocks_with_phis_to_rewrite, idx);
|
bitmap_set_bit (blocks_with_phis_to_rewrite, idx);
|
VEC_reserve (tree_vec, heap, phis_to_rewrite, last_basic_block + 1);
|
VEC_reserve (tree_vec, heap, phis_to_rewrite, last_basic_block + 1);
|
for (i = VEC_length (tree_vec, phis_to_rewrite); i <= idx; i++)
|
for (i = VEC_length (tree_vec, phis_to_rewrite); i <= idx; i++)
|
VEC_quick_push (tree_vec, phis_to_rewrite, NULL);
|
VEC_quick_push (tree_vec, phis_to_rewrite, NULL);
|
|
|
phis = VEC_index (tree_vec, phis_to_rewrite, idx);
|
phis = VEC_index (tree_vec, phis_to_rewrite, idx);
|
if (!phis)
|
if (!phis)
|
phis = VEC_alloc (tree, heap, 10);
|
phis = VEC_alloc (tree, heap, 10);
|
|
|
VEC_safe_push (tree, heap, phis, phi);
|
VEC_safe_push (tree, heap, phis, phi);
|
VEC_replace (tree_vec, phis_to_rewrite, idx, phis);
|
VEC_replace (tree_vec, phis_to_rewrite, idx, phis);
|
}
|
}
|
|
|
/* Insert PHI nodes for variable VAR using the iterated dominance
|
/* Insert PHI nodes for variable VAR using the iterated dominance
|
frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
|
frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
|
function assumes that the caller is incrementally updating the SSA
|
function assumes that the caller is incrementally updating the SSA
|
form, in which case (1) VAR is assumed to be an SSA name, (2) a new
|
form, in which case (1) VAR is assumed to be an SSA name, (2) a new
|
SSA name is created for VAR's symbol, and, (3) all the arguments
|
SSA name is created for VAR's symbol, and, (3) all the arguments
|
for the newly created PHI node are set to VAR.
|
for the newly created PHI node are set to VAR.
|
|
|
PHI_INSERTION_POINTS is updated to reflect nodes that already had a
|
PHI_INSERTION_POINTS is updated to reflect nodes that already had a
|
PHI node for VAR. On exit, only the nodes that received a PHI node
|
PHI node for VAR. On exit, only the nodes that received a PHI node
|
for VAR will be present in PHI_INSERTION_POINTS. */
|
for VAR will be present in PHI_INSERTION_POINTS. */
|
|
|
static void
|
static void
|
insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
|
insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
|
{
|
{
|
unsigned bb_index;
|
unsigned bb_index;
|
edge e;
|
edge e;
|
tree phi;
|
tree phi;
|
basic_block bb;
|
basic_block bb;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
struct def_blocks_d *def_map;
|
struct def_blocks_d *def_map;
|
|
|
def_map = find_def_blocks_for (var);
|
def_map = find_def_blocks_for (var);
|
gcc_assert (def_map);
|
gcc_assert (def_map);
|
|
|
/* Remove the blocks where we already have PHI nodes for VAR. */
|
/* Remove the blocks where we already have PHI nodes for VAR. */
|
bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
|
bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
|
|
|
/* Remove obviously useless phi nodes. */
|
/* Remove obviously useless phi nodes. */
|
prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks,
|
prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks,
|
def_map->livein_blocks);
|
def_map->livein_blocks);
|
|
|
/* And insert the PHI nodes. */
|
/* And insert the PHI nodes. */
|
EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
|
EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
|
{
|
{
|
bb = BASIC_BLOCK (bb_index);
|
bb = BASIC_BLOCK (bb_index);
|
if (update_p)
|
if (update_p)
|
mark_block_for_update (bb);
|
mark_block_for_update (bb);
|
|
|
if (update_p && TREE_CODE (var) == SSA_NAME)
|
if (update_p && TREE_CODE (var) == SSA_NAME)
|
{
|
{
|
/* If we are rewriting SSA names, create the LHS of the PHI
|
/* If we are rewriting SSA names, create the LHS of the PHI
|
node by duplicating VAR. This is useful in the case of
|
node by duplicating VAR. This is useful in the case of
|
pointers, to also duplicate pointer attributes (alias
|
pointers, to also duplicate pointer attributes (alias
|
information, in particular). */
|
information, in particular). */
|
edge_iterator ei;
|
edge_iterator ei;
|
tree new_lhs;
|
tree new_lhs;
|
|
|
phi = create_phi_node (var, bb);
|
phi = create_phi_node (var, bb);
|
new_lhs = duplicate_ssa_name (var, phi);
|
new_lhs = duplicate_ssa_name (var, phi);
|
SET_PHI_RESULT (phi, new_lhs);
|
SET_PHI_RESULT (phi, new_lhs);
|
add_new_name_mapping (new_lhs, var);
|
add_new_name_mapping (new_lhs, var);
|
|
|
/* Add VAR to every argument slot of PHI. We need VAR in
|
/* Add VAR to every argument slot of PHI. We need VAR in
|
every argument so that rewrite_update_phi_arguments knows
|
every argument so that rewrite_update_phi_arguments knows
|
which name is this PHI node replacing. If VAR is a
|
which name is this PHI node replacing. If VAR is a
|
symbol marked for renaming, this is not necessary, the
|
symbol marked for renaming, this is not necessary, the
|
renamer will use the symbol on the LHS to get its
|
renamer will use the symbol on the LHS to get its
|
reaching definition. */
|
reaching definition. */
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
add_phi_arg (phi, var, e);
|
add_phi_arg (phi, var, e);
|
}
|
}
|
else
|
else
|
{
|
{
|
tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
|
tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
|
phi = create_phi_node (sym, bb);
|
phi = create_phi_node (sym, bb);
|
}
|
}
|
|
|
/* Mark this PHI node as interesting for update_ssa. */
|
/* Mark this PHI node as interesting for update_ssa. */
|
REGISTER_DEFS_IN_THIS_STMT (phi) = 1;
|
REGISTER_DEFS_IN_THIS_STMT (phi) = 1;
|
mark_phi_for_rewrite (bb, phi);
|
mark_phi_for_rewrite (bb, phi);
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Insert PHI nodes at the dominance frontier of blocks with variable
|
/* Insert PHI nodes at the dominance frontier of blocks with variable
|
definitions. DFS contains the dominance frontier information for
|
definitions. DFS contains the dominance frontier information for
|
the flowgraph. PHI nodes will only be inserted at the dominance
|
the flowgraph. PHI nodes will only be inserted at the dominance
|
frontier of definition blocks for variables whose NEED_PHI_STATE
|
frontier of definition blocks for variables whose NEED_PHI_STATE
|
annotation is marked as ``maybe'' or ``unknown'' (computed by
|
annotation is marked as ``maybe'' or ``unknown'' (computed by
|
mark_def_sites). */
|
mark_def_sites). */
|
|
|
static void
|
static void
|
insert_phi_nodes (bitmap *dfs)
|
insert_phi_nodes (bitmap *dfs)
|
{
|
{
|
referenced_var_iterator rvi;
|
referenced_var_iterator rvi;
|
tree var;
|
tree var;
|
|
|
timevar_push (TV_TREE_INSERT_PHI_NODES);
|
timevar_push (TV_TREE_INSERT_PHI_NODES);
|
|
|
FOR_EACH_REFERENCED_VAR (var, rvi)
|
FOR_EACH_REFERENCED_VAR (var, rvi)
|
{
|
{
|
struct def_blocks_d *def_map;
|
struct def_blocks_d *def_map;
|
bitmap idf;
|
bitmap idf;
|
|
|
def_map = find_def_blocks_for (var);
|
def_map = find_def_blocks_for (var);
|
if (def_map == NULL)
|
if (def_map == NULL)
|
continue;
|
continue;
|
|
|
if (get_phi_state (var) != NEED_PHI_STATE_NO)
|
if (get_phi_state (var) != NEED_PHI_STATE_NO)
|
{
|
{
|
idf = find_idf (def_map->def_blocks, dfs);
|
idf = find_idf (def_map->def_blocks, dfs);
|
insert_phi_nodes_for (var, idf, false);
|
insert_phi_nodes_for (var, idf, false);
|
BITMAP_FREE (idf);
|
BITMAP_FREE (idf);
|
}
|
}
|
}
|
}
|
|
|
timevar_pop (TV_TREE_INSERT_PHI_NODES);
|
timevar_pop (TV_TREE_INSERT_PHI_NODES);
|
}
|
}
|
|
|
|
|
/* Register DEF (an SSA_NAME) to be a new definition for its underlying
|
/* Register DEF (an SSA_NAME) to be a new definition for its underlying
|
variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition
|
variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition
|
into the stack pointed to by BLOCK_DEFS_P. */
|
into the stack pointed to by BLOCK_DEFS_P. */
|
|
|
void
|
void
|
register_new_def (tree def, VEC(tree,heap) **block_defs_p)
|
register_new_def (tree def, VEC(tree,heap) **block_defs_p)
|
{
|
{
|
tree var = SSA_NAME_VAR (def);
|
tree var = SSA_NAME_VAR (def);
|
tree currdef;
|
tree currdef;
|
|
|
/* If this variable is set in a single basic block and all uses are
|
/* If this variable is set in a single basic block and all uses are
|
dominated by the set(s) in that single basic block, then there is
|
dominated by the set(s) in that single basic block, then there is
|
no reason to record anything for this variable in the block local
|
no reason to record anything for this variable in the block local
|
definition stacks. Doing so just wastes time and memory.
|
definition stacks. Doing so just wastes time and memory.
|
|
|
This is the same test to prune the set of variables which may
|
This is the same test to prune the set of variables which may
|
need PHI nodes. So we just use that information since it's already
|
need PHI nodes. So we just use that information since it's already
|
computed and available for us to use. */
|
computed and available for us to use. */
|
if (get_phi_state (var) == NEED_PHI_STATE_NO)
|
if (get_phi_state (var) == NEED_PHI_STATE_NO)
|
{
|
{
|
set_current_def (var, def);
|
set_current_def (var, def);
|
return;
|
return;
|
}
|
}
|
|
|
currdef = get_current_def (var);
|
currdef = get_current_def (var);
|
|
|
/* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
|
/* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
|
later used by the dominator tree callbacks to restore the reaching
|
later used by the dominator tree callbacks to restore the reaching
|
definitions for all the variables defined in the block after a recursive
|
definitions for all the variables defined in the block after a recursive
|
visit to all its immediately dominated blocks. If there is no current
|
visit to all its immediately dominated blocks. If there is no current
|
reaching definition, then just record the underlying _DECL node. */
|
reaching definition, then just record the underlying _DECL node. */
|
VEC_safe_push (tree, heap, *block_defs_p, currdef ? currdef : var);
|
VEC_safe_push (tree, heap, *block_defs_p, currdef ? currdef : var);
|
|
|
/* Set the current reaching definition for VAR to be DEF. */
|
/* Set the current reaching definition for VAR to be DEF. */
|
set_current_def (var, def);
|
set_current_def (var, def);
|
}
|
}
|
|
|
|
|
/* Perform a depth-first traversal of the dominator tree looking for
|
/* Perform a depth-first traversal of the dominator tree looking for
|
variables to rename. BB is the block where to start searching.
|
variables to rename. BB is the block where to start searching.
|
Renaming is a five step process:
|
Renaming is a five step process:
|
|
|
1- Every definition made by PHI nodes at the start of the blocks is
|
1- Every definition made by PHI nodes at the start of the blocks is
|
registered as the current definition for the corresponding variable.
|
registered as the current definition for the corresponding variable.
|
|
|
2- Every statement in BB is rewritten. USE and VUSE operands are
|
2- Every statement in BB is rewritten. USE and VUSE operands are
|
rewritten with their corresponding reaching definition. DEF and
|
rewritten with their corresponding reaching definition. DEF and
|
VDEF targets are registered as new definitions.
|
VDEF targets are registered as new definitions.
|
|
|
3- All the PHI nodes in successor blocks of BB are visited. The
|
3- All the PHI nodes in successor blocks of BB are visited. The
|
argument corresponding to BB is replaced with its current reaching
|
argument corresponding to BB is replaced with its current reaching
|
definition.
|
definition.
|
|
|
4- Recursively rewrite every dominator child block of BB.
|
4- Recursively rewrite every dominator child block of BB.
|
|
|
5- Restore (in reverse order) the current reaching definition for every
|
5- Restore (in reverse order) the current reaching definition for every
|
new definition introduced in this block. This is done so that when
|
new definition introduced in this block. This is done so that when
|
we return from the recursive call, all the current reaching
|
we return from the recursive call, all the current reaching
|
definitions are restored to the names that were valid in the
|
definitions are restored to the names that were valid in the
|
dominator parent of BB. */
|
dominator parent of BB. */
|
|
|
/* SSA Rewriting Step 1. Initialization, create a block local stack
|
/* SSA Rewriting Step 1. Initialization, create a block local stack
|
of reaching definitions for new SSA names produced in this block
|
of reaching definitions for new SSA names produced in this block
|
(BLOCK_DEFS). Register new definitions for every PHI node in the
|
(BLOCK_DEFS). Register new definitions for every PHI node in the
|
block. */
|
block. */
|
|
|
static void
|
static void
|
rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
|
rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
|
basic_block bb)
|
basic_block bb)
|
{
|
{
|
tree phi;
|
tree phi;
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
|
fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
|
|
|
/* Mark the unwind point for this block. */
|
/* Mark the unwind point for this block. */
|
VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
|
VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
|
|
|
/* Step 1. Register new definitions for every PHI node in the block.
|
/* Step 1. Register new definitions for every PHI node in the block.
|
Conceptually, all the PHI nodes are executed in parallel and each PHI
|
Conceptually, all the PHI nodes are executed in parallel and each PHI
|
node introduces a new version for the associated variable. */
|
node introduces a new version for the associated variable. */
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
{
|
{
|
tree result = PHI_RESULT (phi);
|
tree result = PHI_RESULT (phi);
|
register_new_def (result, &block_defs_stack);
|
register_new_def (result, &block_defs_stack);
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Return the current definition for variable VAR. If none is found,
|
/* Return the current definition for variable VAR. If none is found,
|
create a new SSA name to act as the zeroth definition for VAR. If VAR
|
create a new SSA name to act as the zeroth definition for VAR. If VAR
|
is call clobbered and there exists a more recent definition of
|
is call clobbered and there exists a more recent definition of
|
GLOBAL_VAR, return the definition for GLOBAL_VAR. This means that VAR
|
GLOBAL_VAR, return the definition for GLOBAL_VAR. This means that VAR
|
has been clobbered by a function call since its last assignment. */
|
has been clobbered by a function call since its last assignment. */
|
|
|
static tree
|
static tree
|
get_reaching_def (tree var)
|
get_reaching_def (tree var)
|
{
|
{
|
tree currdef_var, avar;
|
tree currdef_var, avar;
|
|
|
/* Lookup the current reaching definition for VAR. */
|
/* Lookup the current reaching definition for VAR. */
|
currdef_var = get_current_def (var);
|
currdef_var = get_current_def (var);
|
|
|
/* If there is no reaching definition for VAR, create and register a
|
/* If there is no reaching definition for VAR, create and register a
|
default definition for it (if needed). */
|
default definition for it (if needed). */
|
if (currdef_var == NULL_TREE)
|
if (currdef_var == NULL_TREE)
|
{
|
{
|
avar = DECL_P (var) ? var : SSA_NAME_VAR (var);
|
avar = DECL_P (var) ? var : SSA_NAME_VAR (var);
|
currdef_var = get_default_def_for (avar);
|
currdef_var = get_default_def_for (avar);
|
set_current_def (var, currdef_var);
|
set_current_def (var, currdef_var);
|
}
|
}
|
|
|
/* Return the current reaching definition for VAR, or the default
|
/* Return the current reaching definition for VAR, or the default
|
definition, if we had to create one. */
|
definition, if we had to create one. */
|
return currdef_var;
|
return currdef_var;
|
}
|
}
|
|
|
|
|
/* SSA Rewriting Step 2. Rewrite every variable used in each statement in
|
/* SSA Rewriting Step 2. Rewrite every variable used in each statement in
|
the block with its immediate reaching definitions. Update the current
|
the block with its immediate reaching definitions. Update the current
|
definition of a variable when a new real or virtual definition is found. */
|
definition of a variable when a new real or virtual definition is found. */
|
|
|
static void
|
static void
|
rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
|
rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
|
basic_block bb ATTRIBUTE_UNUSED,
|
basic_block bb ATTRIBUTE_UNUSED,
|
block_stmt_iterator si)
|
block_stmt_iterator si)
|
{
|
{
|
tree stmt;
|
tree stmt;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
def_operand_p def_p;
|
def_operand_p def_p;
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
|
|
stmt = bsi_stmt (si);
|
stmt = bsi_stmt (si);
|
|
|
/* If mark_def_sites decided that we don't need to rewrite this
|
/* If mark_def_sites decided that we don't need to rewrite this
|
statement, ignore it. */
|
statement, ignore it. */
|
gcc_assert (blocks_to_update == NULL);
|
gcc_assert (blocks_to_update == NULL);
|
if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
|
if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
|
return;
|
return;
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "Renaming statement ");
|
fprintf (dump_file, "Renaming statement ");
|
print_generic_stmt (dump_file, stmt, TDF_SLIM);
|
print_generic_stmt (dump_file, stmt, TDF_SLIM);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
/* Step 1. Rewrite USES and VUSES in the statement. */
|
/* Step 1. Rewrite USES and VUSES in the statement. */
|
if (REWRITE_THIS_STMT (stmt))
|
if (REWRITE_THIS_STMT (stmt))
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
|
SSA_OP_ALL_USES|SSA_OP_ALL_KILLS)
|
SSA_OP_ALL_USES|SSA_OP_ALL_KILLS)
|
{
|
{
|
tree var = USE_FROM_PTR (use_p);
|
tree var = USE_FROM_PTR (use_p);
|
gcc_assert (DECL_P (var));
|
gcc_assert (DECL_P (var));
|
SET_USE (use_p, get_reaching_def (var));
|
SET_USE (use_p, get_reaching_def (var));
|
}
|
}
|
|
|
/* Step 2. Register the statement's DEF and VDEF operands. */
|
/* Step 2. Register the statement's DEF and VDEF operands. */
|
if (REGISTER_DEFS_IN_THIS_STMT (stmt))
|
if (REGISTER_DEFS_IN_THIS_STMT (stmt))
|
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
|
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
|
{
|
{
|
tree var = DEF_FROM_PTR (def_p);
|
tree var = DEF_FROM_PTR (def_p);
|
gcc_assert (DECL_P (var));
|
gcc_assert (DECL_P (var));
|
SET_DEF (def_p, make_ssa_name (var, stmt));
|
SET_DEF (def_p, make_ssa_name (var, stmt));
|
register_new_def (DEF_FROM_PTR (def_p), &block_defs_stack);
|
register_new_def (DEF_FROM_PTR (def_p), &block_defs_stack);
|
}
|
}
|
}
|
}
|
|
|
|
|
/* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
|
/* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
|
PHI nodes. For every PHI node found, add a new argument containing the
|
PHI nodes. For every PHI node found, add a new argument containing the
|
current reaching definition for the variable and the edge through which
|
current reaching definition for the variable and the edge through which
|
that definition is reaching the PHI node. */
|
that definition is reaching the PHI node. */
|
|
|
static void
|
static void
|
rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
|
rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
|
basic_block bb)
|
basic_block bb)
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
{
|
{
|
tree phi;
|
tree phi;
|
|
|
for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
|
{
|
{
|
tree currdef;
|
tree currdef;
|
currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
|
currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
|
add_phi_arg (phi, currdef, e);
|
add_phi_arg (phi, currdef, e);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Called after visiting basic block BB. Restore CURRDEFS to its
|
/* Called after visiting basic block BB. Restore CURRDEFS to its
|
original value. */
|
original value. */
|
|
|
static void
|
static void
|
rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
|
rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
|
basic_block bb ATTRIBUTE_UNUSED)
|
basic_block bb ATTRIBUTE_UNUSED)
|
{
|
{
|
/* Restore CURRDEFS to its original state. */
|
/* Restore CURRDEFS to its original state. */
|
while (VEC_length (tree, block_defs_stack) > 0)
|
while (VEC_length (tree, block_defs_stack) > 0)
|
{
|
{
|
tree tmp = VEC_pop (tree, block_defs_stack);
|
tree tmp = VEC_pop (tree, block_defs_stack);
|
tree saved_def, var;
|
tree saved_def, var;
|
|
|
if (tmp == NULL_TREE)
|
if (tmp == NULL_TREE)
|
break;
|
break;
|
|
|
/* If we recorded an SSA_NAME, then make the SSA_NAME the current
|
/* If we recorded an SSA_NAME, then make the SSA_NAME the current
|
definition of its underlying variable. If we recorded anything
|
definition of its underlying variable. If we recorded anything
|
else, it must have been an _DECL node and its current reaching
|
else, it must have been an _DECL node and its current reaching
|
definition must have been NULL. */
|
definition must have been NULL. */
|
if (TREE_CODE (tmp) == SSA_NAME)
|
if (TREE_CODE (tmp) == SSA_NAME)
|
{
|
{
|
saved_def = tmp;
|
saved_def = tmp;
|
var = SSA_NAME_VAR (saved_def);
|
var = SSA_NAME_VAR (saved_def);
|
}
|
}
|
else
|
else
|
{
|
{
|
saved_def = NULL;
|
saved_def = NULL;
|
var = tmp;
|
var = tmp;
|
}
|
}
|
|
|
set_current_def (var, saved_def);
|
set_current_def (var, saved_def);
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Dump SSA information to FILE. */
|
/* Dump SSA information to FILE. */
|
|
|
void
|
void
|
dump_tree_ssa (FILE *file)
|
dump_tree_ssa (FILE *file)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
const char *funcname
|
const char *funcname
|
= lang_hooks.decl_printable_name (current_function_decl, 2);
|
= lang_hooks.decl_printable_name (current_function_decl, 2);
|
|
|
fprintf (file, "SSA information for %s\n\n", funcname);
|
fprintf (file, "SSA information for %s\n\n", funcname);
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
dump_bb (bb, file, 0);
|
dump_bb (bb, file, 0);
|
fputs (" ", file);
|
fputs (" ", file);
|
print_generic_stmt (file, phi_nodes (bb), dump_flags);
|
print_generic_stmt (file, phi_nodes (bb), dump_flags);
|
fputs ("\n\n", file);
|
fputs ("\n\n", file);
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Dump SSA information to stderr. */
|
/* Dump SSA information to stderr. */
|
|
|
void
|
void
|
debug_tree_ssa (void)
|
debug_tree_ssa (void)
|
{
|
{
|
dump_tree_ssa (stderr);
|
dump_tree_ssa (stderr);
|
}
|
}
|
|
|
|
|
/* Dump statistics for the hash table HTAB. */
|
/* Dump statistics for the hash table HTAB. */
|
|
|
static void
|
static void
|
htab_statistics (FILE *file, htab_t htab)
|
htab_statistics (FILE *file, htab_t htab)
|
{
|
{
|
fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
|
fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
|
(long) htab_size (htab),
|
(long) htab_size (htab),
|
(long) htab_elements (htab),
|
(long) htab_elements (htab),
|
htab_collisions (htab));
|
htab_collisions (htab));
|
}
|
}
|
|
|
|
|
/* Dump SSA statistics on FILE. */
|
/* Dump SSA statistics on FILE. */
|
|
|
void
|
void
|
dump_tree_ssa_stats (FILE *file)
|
dump_tree_ssa_stats (FILE *file)
|
{
|
{
|
fprintf (file, "\nHash table statistics:\n");
|
fprintf (file, "\nHash table statistics:\n");
|
|
|
fprintf (file, " def_blocks: ");
|
fprintf (file, " def_blocks: ");
|
htab_statistics (file, def_blocks);
|
htab_statistics (file, def_blocks);
|
|
|
fprintf (file, "\n");
|
fprintf (file, "\n");
|
}
|
}
|
|
|
|
|
/* Dump SSA statistics on stderr. */
|
/* Dump SSA statistics on stderr. */
|
|
|
void
|
void
|
debug_tree_ssa_stats (void)
|
debug_tree_ssa_stats (void)
|
{
|
{
|
dump_tree_ssa_stats (stderr);
|
dump_tree_ssa_stats (stderr);
|
}
|
}
|
|
|
|
|
/* Hashing and equality functions for DEF_BLOCKS. */
|
/* Hashing and equality functions for DEF_BLOCKS. */
|
|
|
static hashval_t
|
static hashval_t
|
def_blocks_hash (const void *p)
|
def_blocks_hash (const void *p)
|
{
|
{
|
return htab_hash_pointer
|
return htab_hash_pointer
|
((const void *)((const struct def_blocks_d *)p)->var);
|
((const void *)((const struct def_blocks_d *)p)->var);
|
}
|
}
|
|
|
static int
|
static int
|
def_blocks_eq (const void *p1, const void *p2)
|
def_blocks_eq (const void *p1, const void *p2)
|
{
|
{
|
return ((const struct def_blocks_d *)p1)->var
|
return ((const struct def_blocks_d *)p1)->var
|
== ((const struct def_blocks_d *)p2)->var;
|
== ((const struct def_blocks_d *)p2)->var;
|
}
|
}
|
|
|
|
|
/* Free memory allocated by one entry in DEF_BLOCKS. */
|
/* Free memory allocated by one entry in DEF_BLOCKS. */
|
|
|
static void
|
static void
|
def_blocks_free (void *p)
|
def_blocks_free (void *p)
|
{
|
{
|
struct def_blocks_d *entry = (struct def_blocks_d *) p;
|
struct def_blocks_d *entry = (struct def_blocks_d *) p;
|
BITMAP_FREE (entry->def_blocks);
|
BITMAP_FREE (entry->def_blocks);
|
BITMAP_FREE (entry->phi_blocks);
|
BITMAP_FREE (entry->phi_blocks);
|
BITMAP_FREE (entry->livein_blocks);
|
BITMAP_FREE (entry->livein_blocks);
|
free (entry);
|
free (entry);
|
}
|
}
|
|
|
|
|
/* Callback for htab_traverse to dump the DEF_BLOCKS hash table. */
|
/* Callback for htab_traverse to dump the DEF_BLOCKS hash table. */
|
|
|
static int
|
static int
|
debug_def_blocks_r (void **slot, void *data ATTRIBUTE_UNUSED)
|
debug_def_blocks_r (void **slot, void *data ATTRIBUTE_UNUSED)
|
{
|
{
|
struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
|
struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
|
|
|
fprintf (stderr, "VAR: ");
|
fprintf (stderr, "VAR: ");
|
print_generic_expr (stderr, db_p->var, dump_flags);
|
print_generic_expr (stderr, db_p->var, dump_flags);
|
bitmap_print (stderr, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
|
bitmap_print (stderr, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
|
bitmap_print (stderr, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}\n");
|
bitmap_print (stderr, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}\n");
|
|
|
return 1;
|
return 1;
|
}
|
}
|
|
|
|
|
/* Dump the DEF_BLOCKS hash table on stderr. */
|
/* Dump the DEF_BLOCKS hash table on stderr. */
|
|
|
void
|
void
|
debug_def_blocks (void)
|
debug_def_blocks (void)
|
{
|
{
|
htab_traverse (def_blocks, debug_def_blocks_r, NULL);
|
htab_traverse (def_blocks, debug_def_blocks_r, NULL);
|
}
|
}
|
|
|
|
|
/* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
|
/* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
|
|
|
static inline void
|
static inline void
|
register_new_update_single (tree new_name, tree old_name)
|
register_new_update_single (tree new_name, tree old_name)
|
{
|
{
|
tree currdef = get_current_def (old_name);
|
tree currdef = get_current_def (old_name);
|
|
|
/* Push the current reaching definition into *BLOCK_DEFS_P.
|
/* Push the current reaching definition into *BLOCK_DEFS_P.
|
This stack is later used by the dominator tree callbacks to
|
This stack is later used by the dominator tree callbacks to
|
restore the reaching definitions for all the variables
|
restore the reaching definitions for all the variables
|
defined in the block after a recursive visit to all its
|
defined in the block after a recursive visit to all its
|
immediately dominated blocks. */
|
immediately dominated blocks. */
|
VEC_reserve (tree, heap, block_defs_stack, 2);
|
VEC_reserve (tree, heap, block_defs_stack, 2);
|
VEC_quick_push (tree, block_defs_stack, currdef);
|
VEC_quick_push (tree, block_defs_stack, currdef);
|
VEC_quick_push (tree, block_defs_stack, old_name);
|
VEC_quick_push (tree, block_defs_stack, old_name);
|
|
|
/* Set the current reaching definition for OLD_NAME to be
|
/* Set the current reaching definition for OLD_NAME to be
|
NEW_NAME. */
|
NEW_NAME. */
|
set_current_def (old_name, new_name);
|
set_current_def (old_name, new_name);
|
}
|
}
|
|
|
|
|
/* Register NEW_NAME to be the new reaching definition for all the
|
/* Register NEW_NAME to be the new reaching definition for all the
|
names in OLD_NAMES. Used by the incremental SSA update routines to
|
names in OLD_NAMES. Used by the incremental SSA update routines to
|
replace old SSA names with new ones. */
|
replace old SSA names with new ones. */
|
|
|
static inline void
|
static inline void
|
register_new_update_set (tree new_name, bitmap old_names)
|
register_new_update_set (tree new_name, bitmap old_names)
|
{
|
{
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
unsigned i;
|
unsigned i;
|
|
|
EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
|
register_new_update_single (new_name, ssa_name (i));
|
register_new_update_single (new_name, ssa_name (i));
|
}
|
}
|
|
|
|
|
/* Initialization of block data structures for the incremental SSA
|
/* Initialization of block data structures for the incremental SSA
|
update pass. Create a block local stack of reaching definitions
|
update pass. Create a block local stack of reaching definitions
|
for new SSA names produced in this block (BLOCK_DEFS). Register
|
for new SSA names produced in this block (BLOCK_DEFS). Register
|
new definitions for every PHI node in the block. */
|
new definitions for every PHI node in the block. */
|
|
|
static void
|
static void
|
rewrite_update_init_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
|
rewrite_update_init_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
|
basic_block bb)
|
basic_block bb)
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
tree phi;
|
tree phi;
|
bool is_abnormal_phi;
|
bool is_abnormal_phi;
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "\n\nRegistering new PHI nodes in block #%d\n\n",
|
fprintf (dump_file, "\n\nRegistering new PHI nodes in block #%d\n\n",
|
bb->index);
|
bb->index);
|
|
|
/* Mark the unwind point for this block. */
|
/* Mark the unwind point for this block. */
|
VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
|
VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
|
|
|
if (!bitmap_bit_p (blocks_to_update, bb->index))
|
if (!bitmap_bit_p (blocks_to_update, bb->index))
|
return;
|
return;
|
|
|
/* Mark the LHS if any of the arguments flows through an abnormal
|
/* Mark the LHS if any of the arguments flows through an abnormal
|
edge. */
|
edge. */
|
is_abnormal_phi = false;
|
is_abnormal_phi = false;
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
if (e->flags & EDGE_ABNORMAL)
|
if (e->flags & EDGE_ABNORMAL)
|
{
|
{
|
is_abnormal_phi = true;
|
is_abnormal_phi = true;
|
break;
|
break;
|
}
|
}
|
|
|
/* If any of the PHI nodes is a replacement for a name in
|
/* If any of the PHI nodes is a replacement for a name in
|
OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
|
OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
|
register it as a new definition for its corresponding name. Also
|
register it as a new definition for its corresponding name. Also
|
register definitions for names whose underlying symbols are
|
register definitions for names whose underlying symbols are
|
marked for renaming. */
|
marked for renaming. */
|
|
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
{
|
{
|
tree lhs, lhs_sym;
|
tree lhs, lhs_sym;
|
|
|
if (!REGISTER_DEFS_IN_THIS_STMT (phi))
|
if (!REGISTER_DEFS_IN_THIS_STMT (phi))
|
continue;
|
continue;
|
|
|
lhs = PHI_RESULT (phi);
|
lhs = PHI_RESULT (phi);
|
lhs_sym = SSA_NAME_VAR (lhs);
|
lhs_sym = SSA_NAME_VAR (lhs);
|
|
|
if (symbol_marked_for_renaming (lhs_sym))
|
if (symbol_marked_for_renaming (lhs_sym))
|
register_new_update_single (lhs, lhs_sym);
|
register_new_update_single (lhs, lhs_sym);
|
else
|
else
|
{
|
{
|
/* If LHS is a new name, register a new definition for all
|
/* If LHS is a new name, register a new definition for all
|
the names replaced by LHS. */
|
the names replaced by LHS. */
|
if (is_new_name (lhs))
|
if (is_new_name (lhs))
|
register_new_update_set (lhs, names_replaced_by (lhs));
|
register_new_update_set (lhs, names_replaced_by (lhs));
|
|
|
/* If LHS is an OLD name, register it as a new definition
|
/* If LHS is an OLD name, register it as a new definition
|
for itself. */
|
for itself. */
|
if (is_old_name (lhs))
|
if (is_old_name (lhs))
|
register_new_update_single (lhs, lhs);
|
register_new_update_single (lhs, lhs);
|
}
|
}
|
|
|
if (is_abnormal_phi)
|
if (is_abnormal_phi)
|
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
|
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
|
/* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
|
the current reaching definition of every name re-written in BB to
|
the current reaching definition of every name re-written in BB to
|
the original reaching definition before visiting BB. This
|
the original reaching definition before visiting BB. This
|
unwinding must be done in the opposite order to what is done in
|
unwinding must be done in the opposite order to what is done in
|
register_new_update_set. */
|
register_new_update_set. */
|
|
|
static void
|
static void
|
rewrite_update_fini_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
|
rewrite_update_fini_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
|
basic_block bb ATTRIBUTE_UNUSED)
|
basic_block bb ATTRIBUTE_UNUSED)
|
{
|
{
|
while (VEC_length (tree, block_defs_stack) > 0)
|
while (VEC_length (tree, block_defs_stack) > 0)
|
{
|
{
|
tree var = VEC_pop (tree, block_defs_stack);
|
tree var = VEC_pop (tree, block_defs_stack);
|
tree saved_def;
|
tree saved_def;
|
|
|
/* NULL indicates the unwind stop point for this block (see
|
/* NULL indicates the unwind stop point for this block (see
|
rewrite_update_init_block). */
|
rewrite_update_init_block). */
|
if (var == NULL)
|
if (var == NULL)
|
return;
|
return;
|
|
|
saved_def = VEC_pop (tree, block_defs_stack);
|
saved_def = VEC_pop (tree, block_defs_stack);
|
set_current_def (var, saved_def);
|
set_current_def (var, saved_def);
|
}
|
}
|
}
|
}
|
|
|
|
|
/* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
|
/* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
|
it is a symbol marked for renaming, replace it with USE_P's current
|
it is a symbol marked for renaming, replace it with USE_P's current
|
reaching definition. */
|
reaching definition. */
|
|
|
static inline void
|
static inline void
|
maybe_replace_use (use_operand_p use_p)
|
maybe_replace_use (use_operand_p use_p)
|
{
|
{
|
tree rdef = NULL_TREE;
|
tree rdef = NULL_TREE;
|
tree use = USE_FROM_PTR (use_p);
|
tree use = USE_FROM_PTR (use_p);
|
tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
|
tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
|
|
|
if (symbol_marked_for_renaming (sym))
|
if (symbol_marked_for_renaming (sym))
|
rdef = get_reaching_def (sym);
|
rdef = get_reaching_def (sym);
|
else if (is_old_name (use))
|
else if (is_old_name (use))
|
rdef = get_reaching_def (use);
|
rdef = get_reaching_def (use);
|
|
|
if (rdef && rdef != use)
|
if (rdef && rdef != use)
|
SET_USE (use_p, rdef);
|
SET_USE (use_p, rdef);
|
}
|
}
|
|
|
|
|
/* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
|
/* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
|
or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
|
or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
|
register it as the current definition for the names replaced by
|
register it as the current definition for the names replaced by
|
DEF_P. */
|
DEF_P. */
|
|
|
static inline void
|
static inline void
|
maybe_register_def (def_operand_p def_p, tree stmt)
|
maybe_register_def (def_operand_p def_p, tree stmt)
|
{
|
{
|
tree def = DEF_FROM_PTR (def_p);
|
tree def = DEF_FROM_PTR (def_p);
|
tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
|
tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
|
|
|
/* If DEF is a naked symbol that needs renaming, create a
|
/* If DEF is a naked symbol that needs renaming, create a
|
new name for it. */
|
new name for it. */
|
if (symbol_marked_for_renaming (sym))
|
if (symbol_marked_for_renaming (sym))
|
{
|
{
|
if (DECL_P (def))
|
if (DECL_P (def))
|
{
|
{
|
def = make_ssa_name (def, stmt);
|
def = make_ssa_name (def, stmt);
|
SET_DEF (def_p, def);
|
SET_DEF (def_p, def);
|
}
|
}
|
|
|
register_new_update_single (def, sym);
|
register_new_update_single (def, sym);
|
}
|
}
|
else
|
else
|
{
|
{
|
/* If DEF is a new name, register it as a new definition
|
/* If DEF is a new name, register it as a new definition
|
for all the names replaced by DEF. */
|
for all the names replaced by DEF. */
|
if (is_new_name (def))
|
if (is_new_name (def))
|
register_new_update_set (def, names_replaced_by (def));
|
register_new_update_set (def, names_replaced_by (def));
|
|
|
/* If DEF is an old name, register DEF as a new
|
/* If DEF is an old name, register DEF as a new
|
definition for itself. */
|
definition for itself. */
|
if (is_old_name (def))
|
if (is_old_name (def))
|
register_new_update_single (def, def);
|
register_new_update_single (def, def);
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Update every variable used in the statement pointed-to by SI. The
|
/* Update every variable used in the statement pointed-to by SI. The
|
statement is assumed to be in SSA form already. Names in
|
statement is assumed to be in SSA form already. Names in
|
OLD_SSA_NAMES used by SI will be updated to their current reaching
|
OLD_SSA_NAMES used by SI will be updated to their current reaching
|
definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
|
definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
|
will be registered as a new definition for their corresponding name
|
will be registered as a new definition for their corresponding name
|
in OLD_SSA_NAMES. */
|
in OLD_SSA_NAMES. */
|
|
|
static void
|
static void
|
rewrite_update_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
|
rewrite_update_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
|
basic_block bb ATTRIBUTE_UNUSED,
|
basic_block bb ATTRIBUTE_UNUSED,
|
block_stmt_iterator si)
|
block_stmt_iterator si)
|
{
|
{
|
stmt_ann_t ann;
|
stmt_ann_t ann;
|
tree stmt;
|
tree stmt;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
def_operand_p def_p;
|
def_operand_p def_p;
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
|
|
stmt = bsi_stmt (si);
|
stmt = bsi_stmt (si);
|
ann = stmt_ann (stmt);
|
ann = stmt_ann (stmt);
|
|
|
gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
|
gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
|
|
|
/* Only update marked statements. */
|
/* Only update marked statements. */
|
if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
|
if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
|
return;
|
return;
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "Updating SSA information for statement ");
|
fprintf (dump_file, "Updating SSA information for statement ");
|
print_generic_stmt (dump_file, stmt, TDF_SLIM);
|
print_generic_stmt (dump_file, stmt, TDF_SLIM);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
/* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
|
/* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
|
symbol is marked for renaming. */
|
symbol is marked for renaming. */
|
if (REWRITE_THIS_STMT (stmt))
|
if (REWRITE_THIS_STMT (stmt))
|
{
|
{
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
|
maybe_replace_use (use_p);
|
maybe_replace_use (use_p);
|
|
|
if (need_to_update_vops_p)
|
if (need_to_update_vops_p)
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
|
SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
|
SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
|
maybe_replace_use (use_p);
|
maybe_replace_use (use_p);
|
}
|
}
|
|
|
/* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
|
/* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
|
Also register definitions for names whose underlying symbol is
|
Also register definitions for names whose underlying symbol is
|
marked for renaming. */
|
marked for renaming. */
|
if (REGISTER_DEFS_IN_THIS_STMT (stmt))
|
if (REGISTER_DEFS_IN_THIS_STMT (stmt))
|
{
|
{
|
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
|
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
|
maybe_register_def (def_p, stmt);
|
maybe_register_def (def_p, stmt);
|
|
|
if (need_to_update_vops_p)
|
if (need_to_update_vops_p)
|
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_VIRTUAL_DEFS)
|
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_VIRTUAL_DEFS)
|
maybe_register_def (def_p, stmt);
|
maybe_register_def (def_p, stmt);
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Replace the operand pointed to by USE_P with USE's current reaching
|
/* Replace the operand pointed to by USE_P with USE's current reaching
|
definition. */
|
definition. */
|
|
|
static inline void
|
static inline void
|
replace_use (use_operand_p use_p, tree use)
|
replace_use (use_operand_p use_p, tree use)
|
{
|
{
|
tree rdef = get_reaching_def (use);
|
tree rdef = get_reaching_def (use);
|
if (rdef != use)
|
if (rdef != use)
|
SET_USE (use_p, rdef);
|
SET_USE (use_p, rdef);
|
}
|
}
|
|
|
|
|
/* Visit all the successor blocks of BB looking for PHI nodes. For
|
/* Visit all the successor blocks of BB looking for PHI nodes. For
|
every PHI node found, check if any of its arguments is in
|
every PHI node found, check if any of its arguments is in
|
OLD_SSA_NAMES. If so, and if the argument has a current reaching
|
OLD_SSA_NAMES. If so, and if the argument has a current reaching
|
definition, replace it. */
|
definition, replace it. */
|
|
|
static void
|
static void
|
rewrite_update_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
|
rewrite_update_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
|
basic_block bb)
|
basic_block bb)
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
unsigned i;
|
unsigned i;
|
|
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
{
|
{
|
tree phi;
|
tree phi;
|
tree_vec phis;
|
tree_vec phis;
|
|
|
if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
|
if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
|
continue;
|
continue;
|
|
|
phis = VEC_index (tree_vec, phis_to_rewrite, e->dest->index);
|
phis = VEC_index (tree_vec, phis_to_rewrite, e->dest->index);
|
for (i = 0; VEC_iterate (tree, phis, i, phi); i++)
|
for (i = 0; VEC_iterate (tree, phis, i, phi); i++)
|
{
|
{
|
tree arg;
|
tree arg;
|
use_operand_p arg_p;
|
use_operand_p arg_p;
|
|
|
gcc_assert (REWRITE_THIS_STMT (phi));
|
gcc_assert (REWRITE_THIS_STMT (phi));
|
|
|
arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
|
arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
|
arg = USE_FROM_PTR (arg_p);
|
arg = USE_FROM_PTR (arg_p);
|
|
|
if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
|
if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
|
continue;
|
continue;
|
|
|
if (arg == NULL_TREE)
|
if (arg == NULL_TREE)
|
{
|
{
|
/* When updating a PHI node for a recently introduced
|
/* When updating a PHI node for a recently introduced
|
symbol we may find NULL arguments. That's why we
|
symbol we may find NULL arguments. That's why we
|
take the symbol from the LHS of the PHI node. */
|
take the symbol from the LHS of the PHI node. */
|
replace_use (arg_p, SSA_NAME_VAR (PHI_RESULT (phi)));
|
replace_use (arg_p, SSA_NAME_VAR (PHI_RESULT (phi)));
|
}
|
}
|
else
|
else
|
{
|
{
|
tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
|
tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
|
|
|
if (symbol_marked_for_renaming (sym))
|
if (symbol_marked_for_renaming (sym))
|
replace_use (arg_p, sym);
|
replace_use (arg_p, sym);
|
else if (is_old_name (arg))
|
else if (is_old_name (arg))
|
replace_use (arg_p, arg);
|
replace_use (arg_p, arg);
|
}
|
}
|
|
|
if (e->flags & EDGE_ABNORMAL)
|
if (e->flags & EDGE_ABNORMAL)
|
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
|
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
|
/* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
|
form.
|
form.
|
|
|
ENTRY indicates the block where to start. Every block dominated by
|
ENTRY indicates the block where to start. Every block dominated by
|
ENTRY will be rewritten.
|
ENTRY will be rewritten.
|
|
|
WHAT indicates what actions will be taken by the renamer (see enum
|
WHAT indicates what actions will be taken by the renamer (see enum
|
rewrite_mode).
|
rewrite_mode).
|
|
|
BLOCKS are the set of interesting blocks for the dominator walker
|
BLOCKS are the set of interesting blocks for the dominator walker
|
to process. If this set is NULL, then all the nodes dominated
|
to process. If this set is NULL, then all the nodes dominated
|
by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
|
by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
|
are not present in BLOCKS are ignored. */
|
are not present in BLOCKS are ignored. */
|
|
|
static void
|
static void
|
rewrite_blocks (basic_block entry, enum rewrite_mode what, sbitmap blocks)
|
rewrite_blocks (basic_block entry, enum rewrite_mode what, sbitmap blocks)
|
{
|
{
|
struct dom_walk_data walk_data;
|
struct dom_walk_data walk_data;
|
|
|
/* Rewrite all the basic blocks in the program. */
|
/* Rewrite all the basic blocks in the program. */
|
timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
|
timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
|
|
|
/* Setup callbacks for the generic dominator tree walker. */
|
/* Setup callbacks for the generic dominator tree walker. */
|
memset (&walk_data, 0, sizeof (walk_data));
|
memset (&walk_data, 0, sizeof (walk_data));
|
|
|
walk_data.dom_direction = CDI_DOMINATORS;
|
walk_data.dom_direction = CDI_DOMINATORS;
|
walk_data.interesting_blocks = blocks;
|
walk_data.interesting_blocks = blocks;
|
|
|
if (what == REWRITE_UPDATE)
|
if (what == REWRITE_UPDATE)
|
walk_data.before_dom_children_before_stmts = rewrite_update_init_block;
|
walk_data.before_dom_children_before_stmts = rewrite_update_init_block;
|
else
|
else
|
walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
|
walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
|
|
|
if (what == REWRITE_ALL)
|
if (what == REWRITE_ALL)
|
walk_data.before_dom_children_walk_stmts = rewrite_stmt;
|
walk_data.before_dom_children_walk_stmts = rewrite_stmt;
|
else if (what == REWRITE_UPDATE)
|
else if (what == REWRITE_UPDATE)
|
walk_data.before_dom_children_walk_stmts = rewrite_update_stmt;
|
walk_data.before_dom_children_walk_stmts = rewrite_update_stmt;
|
else
|
else
|
gcc_unreachable ();
|
gcc_unreachable ();
|
|
|
if (what == REWRITE_ALL)
|
if (what == REWRITE_ALL)
|
walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
|
walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
|
else if (what == REWRITE_UPDATE)
|
else if (what == REWRITE_UPDATE)
|
walk_data.before_dom_children_after_stmts = rewrite_update_phi_arguments;
|
walk_data.before_dom_children_after_stmts = rewrite_update_phi_arguments;
|
else
|
else
|
gcc_unreachable ();
|
gcc_unreachable ();
|
|
|
if (what == REWRITE_ALL)
|
if (what == REWRITE_ALL)
|
walk_data.after_dom_children_after_stmts = rewrite_finalize_block;
|
walk_data.after_dom_children_after_stmts = rewrite_finalize_block;
|
else if (what == REWRITE_UPDATE)
|
else if (what == REWRITE_UPDATE)
|
walk_data.after_dom_children_after_stmts = rewrite_update_fini_block;
|
walk_data.after_dom_children_after_stmts = rewrite_update_fini_block;
|
else
|
else
|
gcc_unreachable ();
|
gcc_unreachable ();
|
|
|
block_defs_stack = VEC_alloc (tree, heap, 10);
|
block_defs_stack = VEC_alloc (tree, heap, 10);
|
|
|
/* Initialize the dominator walker. */
|
/* Initialize the dominator walker. */
|
init_walk_dominator_tree (&walk_data);
|
init_walk_dominator_tree (&walk_data);
|
|
|
/* Recursively walk the dominator tree rewriting each statement in
|
/* Recursively walk the dominator tree rewriting each statement in
|
each basic block. */
|
each basic block. */
|
walk_dominator_tree (&walk_data, entry);
|
walk_dominator_tree (&walk_data, entry);
|
|
|
/* Finalize the dominator walker. */
|
/* Finalize the dominator walker. */
|
fini_walk_dominator_tree (&walk_data);
|
fini_walk_dominator_tree (&walk_data);
|
|
|
/* Debugging dumps. */
|
/* Debugging dumps. */
|
if (dump_file && (dump_flags & TDF_STATS))
|
if (dump_file && (dump_flags & TDF_STATS))
|
{
|
{
|
dump_dfa_stats (dump_file);
|
dump_dfa_stats (dump_file);
|
if (def_blocks)
|
if (def_blocks)
|
dump_tree_ssa_stats (dump_file);
|
dump_tree_ssa_stats (dump_file);
|
}
|
}
|
|
|
if (def_blocks)
|
if (def_blocks)
|
{
|
{
|
htab_delete (def_blocks);
|
htab_delete (def_blocks);
|
def_blocks = NULL;
|
def_blocks = NULL;
|
}
|
}
|
|
|
VEC_free (tree, heap, block_defs_stack);
|
VEC_free (tree, heap, block_defs_stack);
|
|
|
timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
|
timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
|
}
|
}
|
|
|
|
|
/* Block initialization routine for mark_def_sites. Clear the
|
/* Block initialization routine for mark_def_sites. Clear the
|
KILLS bitmap at the start of each block. */
|
KILLS bitmap at the start of each block. */
|
|
|
static void
|
static void
|
mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
|
mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
|
basic_block bb ATTRIBUTE_UNUSED)
|
basic_block bb ATTRIBUTE_UNUSED)
|
{
|
{
|
struct mark_def_sites_global_data *gd =
|
struct mark_def_sites_global_data *gd =
|
(struct mark_def_sites_global_data *) walk_data->global_data;
|
(struct mark_def_sites_global_data *) walk_data->global_data;
|
bitmap kills = gd->kills;
|
bitmap kills = gd->kills;
|
bitmap_clear (kills);
|
bitmap_clear (kills);
|
}
|
}
|
|
|
|
|
/* Mark the definition site blocks for each variable, so that we know
|
/* Mark the definition site blocks for each variable, so that we know
|
where the variable is actually live.
|
where the variable is actually live.
|
|
|
INTERESTING_BLOCKS will be filled in with all the blocks that
|
INTERESTING_BLOCKS will be filled in with all the blocks that
|
should be processed by the renamer. It is assumed to be
|
should be processed by the renamer. It is assumed to be
|
initialized and zeroed by the caller. */
|
initialized and zeroed by the caller. */
|
|
|
static void
|
static void
|
mark_def_site_blocks (sbitmap interesting_blocks)
|
mark_def_site_blocks (sbitmap interesting_blocks)
|
{
|
{
|
struct dom_walk_data walk_data;
|
struct dom_walk_data walk_data;
|
struct mark_def_sites_global_data mark_def_sites_global_data;
|
struct mark_def_sites_global_data mark_def_sites_global_data;
|
referenced_var_iterator rvi;
|
referenced_var_iterator rvi;
|
tree var;
|
tree var;
|
|
|
/* Allocate memory for the DEF_BLOCKS hash table. */
|
/* Allocate memory for the DEF_BLOCKS hash table. */
|
def_blocks = htab_create (num_referenced_vars,
|
def_blocks = htab_create (num_referenced_vars,
|
def_blocks_hash, def_blocks_eq, def_blocks_free);
|
def_blocks_hash, def_blocks_eq, def_blocks_free);
|
FOR_EACH_REFERENCED_VAR(var, rvi)
|
FOR_EACH_REFERENCED_VAR(var, rvi)
|
set_current_def (var, NULL_TREE);
|
set_current_def (var, NULL_TREE);
|
|
|
/* Setup callbacks for the generic dominator tree walker to find and
|
/* Setup callbacks for the generic dominator tree walker to find and
|
mark definition sites. */
|
mark definition sites. */
|
walk_data.walk_stmts_backward = false;
|
walk_data.walk_stmts_backward = false;
|
walk_data.dom_direction = CDI_DOMINATORS;
|
walk_data.dom_direction = CDI_DOMINATORS;
|
walk_data.initialize_block_local_data = NULL;
|
walk_data.initialize_block_local_data = NULL;
|
walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block;
|
walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block;
|
walk_data.before_dom_children_walk_stmts = mark_def_sites;
|
walk_data.before_dom_children_walk_stmts = mark_def_sites;
|
walk_data.before_dom_children_after_stmts = NULL;
|
walk_data.before_dom_children_after_stmts = NULL;
|
walk_data.after_dom_children_before_stmts = NULL;
|
walk_data.after_dom_children_before_stmts = NULL;
|
walk_data.after_dom_children_walk_stmts = NULL;
|
walk_data.after_dom_children_walk_stmts = NULL;
|
walk_data.after_dom_children_after_stmts = NULL;
|
walk_data.after_dom_children_after_stmts = NULL;
|
walk_data.interesting_blocks = NULL;
|
walk_data.interesting_blocks = NULL;
|
|
|
/* Notice that this bitmap is indexed using variable UIDs, so it must be
|
/* Notice that this bitmap is indexed using variable UIDs, so it must be
|
large enough to accommodate all the variables referenced in the
|
large enough to accommodate all the variables referenced in the
|
function, not just the ones we are renaming. */
|
function, not just the ones we are renaming. */
|
mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
|
mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
|
|
|
/* Create the set of interesting blocks that will be filled by
|
/* Create the set of interesting blocks that will be filled by
|
mark_def_sites. */
|
mark_def_sites. */
|
mark_def_sites_global_data.interesting_blocks = interesting_blocks;
|
mark_def_sites_global_data.interesting_blocks = interesting_blocks;
|
walk_data.global_data = &mark_def_sites_global_data;
|
walk_data.global_data = &mark_def_sites_global_data;
|
|
|
/* We do not have any local data. */
|
/* We do not have any local data. */
|
walk_data.block_local_data_size = 0;
|
walk_data.block_local_data_size = 0;
|
|
|
/* Initialize the dominator walker. */
|
/* Initialize the dominator walker. */
|
init_walk_dominator_tree (&walk_data);
|
init_walk_dominator_tree (&walk_data);
|
|
|
/* Recursively walk the dominator tree. */
|
/* Recursively walk the dominator tree. */
|
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
|
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
|
|
|
/* Finalize the dominator walker. */
|
/* Finalize the dominator walker. */
|
fini_walk_dominator_tree (&walk_data);
|
fini_walk_dominator_tree (&walk_data);
|
|
|
/* We no longer need this bitmap, clear and free it. */
|
/* We no longer need this bitmap, clear and free it. */
|
BITMAP_FREE (mark_def_sites_global_data.kills);
|
BITMAP_FREE (mark_def_sites_global_data.kills);
|
}
|
}
|
|
|
|
|
/* Main entry point into the SSA builder. The renaming process
|
/* Main entry point into the SSA builder. The renaming process
|
proceeds in four main phases:
|
proceeds in four main phases:
|
|
|
1- Compute dominance frontier and immediate dominators, needed to
|
1- Compute dominance frontier and immediate dominators, needed to
|
insert PHI nodes and rename the function in dominator tree
|
insert PHI nodes and rename the function in dominator tree
|
order.
|
order.
|
|
|
2- Find and mark all the blocks that define variables
|
2- Find and mark all the blocks that define variables
|
(mark_def_site_blocks).
|
(mark_def_site_blocks).
|
|
|
3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
|
3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
|
|
|
4- Rename all the blocks (rewrite_blocks) and statements in the program.
|
4- Rename all the blocks (rewrite_blocks) and statements in the program.
|
|
|
Steps 3 and 4 are done using the dominator tree walker
|
Steps 3 and 4 are done using the dominator tree walker
|
(walk_dominator_tree). */
|
(walk_dominator_tree). */
|
|
|
static unsigned int
|
static unsigned int
|
rewrite_into_ssa (void)
|
rewrite_into_ssa (void)
|
{
|
{
|
bitmap *dfs;
|
bitmap *dfs;
|
basic_block bb;
|
basic_block bb;
|
sbitmap interesting_blocks;
|
sbitmap interesting_blocks;
|
|
|
timevar_push (TV_TREE_SSA_OTHER);
|
timevar_push (TV_TREE_SSA_OTHER);
|
|
|
/* Initialize operand data structures. */
|
/* Initialize operand data structures. */
|
init_ssa_operands ();
|
init_ssa_operands ();
|
|
|
/* Initialize the set of interesting blocks. The callback
|
/* Initialize the set of interesting blocks. The callback
|
mark_def_sites will add to this set those blocks that the renamer
|
mark_def_sites will add to this set those blocks that the renamer
|
should process. */
|
should process. */
|
interesting_blocks = sbitmap_alloc (last_basic_block);
|
interesting_blocks = sbitmap_alloc (last_basic_block);
|
sbitmap_zero (interesting_blocks);
|
sbitmap_zero (interesting_blocks);
|
|
|
/* Initialize dominance frontier. */
|
/* Initialize dominance frontier. */
|
dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap));
|
dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap));
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
dfs[bb->index] = BITMAP_ALLOC (NULL);
|
dfs[bb->index] = BITMAP_ALLOC (NULL);
|
|
|
/* 1- Compute dominance frontiers. */
|
/* 1- Compute dominance frontiers. */
|
calculate_dominance_info (CDI_DOMINATORS);
|
calculate_dominance_info (CDI_DOMINATORS);
|
compute_dominance_frontiers (dfs);
|
compute_dominance_frontiers (dfs);
|
|
|
/* 2- Find and mark definition sites. */
|
/* 2- Find and mark definition sites. */
|
mark_def_site_blocks (interesting_blocks);
|
mark_def_site_blocks (interesting_blocks);
|
|
|
/* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
|
/* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
|
insert_phi_nodes (dfs);
|
insert_phi_nodes (dfs);
|
|
|
/* 4- Rename all the blocks. */
|
/* 4- Rename all the blocks. */
|
rewrite_blocks (ENTRY_BLOCK_PTR, REWRITE_ALL, interesting_blocks);
|
rewrite_blocks (ENTRY_BLOCK_PTR, REWRITE_ALL, interesting_blocks);
|
|
|
/* Free allocated memory. */
|
/* Free allocated memory. */
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
BITMAP_FREE (dfs[bb->index]);
|
BITMAP_FREE (dfs[bb->index]);
|
free (dfs);
|
free (dfs);
|
sbitmap_free (interesting_blocks);
|
sbitmap_free (interesting_blocks);
|
|
|
timevar_pop (TV_TREE_SSA_OTHER);
|
timevar_pop (TV_TREE_SSA_OTHER);
|
in_ssa_p = true;
|
in_ssa_p = true;
|
return 0;
|
return 0;
|
}
|
}
|
|
|
|
|
struct tree_opt_pass pass_build_ssa =
|
struct tree_opt_pass pass_build_ssa =
|
{
|
{
|
"ssa", /* name */
|
"ssa", /* name */
|
NULL, /* gate */
|
NULL, /* gate */
|
rewrite_into_ssa, /* execute */
|
rewrite_into_ssa, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
0, /* tv_id */
|
0, /* tv_id */
|
PROP_cfg | PROP_referenced_vars, /* properties_required */
|
PROP_cfg | PROP_referenced_vars, /* properties_required */
|
PROP_ssa, /* properties_provided */
|
PROP_ssa, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_dump_func
|
TODO_dump_func
|
| TODO_verify_ssa
|
| TODO_verify_ssa
|
| TODO_remove_unused_locals, /* todo_flags_finish */
|
| TODO_remove_unused_locals, /* todo_flags_finish */
|
0 /* letter */
|
0 /* letter */
|
};
|
};
|
|
|
|
|
/* Mark the definition of VAR at STMT and BB as interesting for the
|
/* Mark the definition of VAR at STMT and BB as interesting for the
|
renamer. BLOCKS is the set of blocks that need updating. */
|
renamer. BLOCKS is the set of blocks that need updating. */
|
|
|
static void
|
static void
|
mark_def_interesting (tree var, tree stmt, basic_block bb, bool insert_phi_p)
|
mark_def_interesting (tree var, tree stmt, basic_block bb, bool insert_phi_p)
|
{
|
{
|
gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
|
gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
|
REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
|
REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
|
|
|
if (insert_phi_p)
|
if (insert_phi_p)
|
{
|
{
|
bool is_phi_p = TREE_CODE (stmt) == PHI_NODE;
|
bool is_phi_p = TREE_CODE (stmt) == PHI_NODE;
|
|
|
set_def_block (var, bb, is_phi_p);
|
set_def_block (var, bb, is_phi_p);
|
|
|
/* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
|
/* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
|
site for both itself and all the old names replaced by it. */
|
site for both itself and all the old names replaced by it. */
|
if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
|
if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
|
{
|
{
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
unsigned i;
|
unsigned i;
|
bitmap set = names_replaced_by (var);
|
bitmap set = names_replaced_by (var);
|
if (set)
|
if (set)
|
EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
|
set_def_block (ssa_name (i), bb, is_phi_p);
|
set_def_block (ssa_name (i), bb, is_phi_p);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Mark the use of VAR at STMT and BB as interesting for the
|
/* Mark the use of VAR at STMT and BB as interesting for the
|
renamer. INSERT_PHI_P is true if we are going to insert new PHI
|
renamer. INSERT_PHI_P is true if we are going to insert new PHI
|
nodes. */
|
nodes. */
|
|
|
static inline void
|
static inline void
|
mark_use_interesting (tree var, tree stmt, basic_block bb, bool insert_phi_p)
|
mark_use_interesting (tree var, tree stmt, basic_block bb, bool insert_phi_p)
|
{
|
{
|
basic_block def_bb = bb_for_stmt (stmt);
|
basic_block def_bb = bb_for_stmt (stmt);
|
|
|
mark_block_for_update (def_bb);
|
mark_block_for_update (def_bb);
|
mark_block_for_update (bb);
|
mark_block_for_update (bb);
|
|
|
if (TREE_CODE (stmt) == PHI_NODE)
|
if (TREE_CODE (stmt) == PHI_NODE)
|
mark_phi_for_rewrite (def_bb, stmt);
|
mark_phi_for_rewrite (def_bb, stmt);
|
else
|
else
|
REWRITE_THIS_STMT (stmt) = 1;
|
REWRITE_THIS_STMT (stmt) = 1;
|
|
|
/* If VAR has not been defined in BB, then it is live-on-entry
|
/* If VAR has not been defined in BB, then it is live-on-entry
|
to BB. Note that we cannot just use the block holding VAR's
|
to BB. Note that we cannot just use the block holding VAR's
|
definition because if VAR is one of the names in OLD_SSA_NAMES,
|
definition because if VAR is one of the names in OLD_SSA_NAMES,
|
it will have several definitions (itself and all the names that
|
it will have several definitions (itself and all the names that
|
replace it). */
|
replace it). */
|
if (insert_phi_p)
|
if (insert_phi_p)
|
{
|
{
|
struct def_blocks_d *db_p = get_def_blocks_for (var);
|
struct def_blocks_d *db_p = get_def_blocks_for (var);
|
if (!bitmap_bit_p (db_p->def_blocks, bb->index))
|
if (!bitmap_bit_p (db_p->def_blocks, bb->index))
|
set_livein_block (var, bb);
|
set_livein_block (var, bb);
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Do a dominator walk starting at BB processing statements that
|
/* Do a dominator walk starting at BB processing statements that
|
reference symbols in SYMS_TO_RENAME. This is very similar to
|
reference symbols in SYMS_TO_RENAME. This is very similar to
|
mark_def_sites, but the scan handles statements whose operands may
|
mark_def_sites, but the scan handles statements whose operands may
|
already be SSA names.
|
already be SSA names.
|
|
|
If INSERT_PHI_P is true, mark those uses as live in the
|
If INSERT_PHI_P is true, mark those uses as live in the
|
corresponding block. This is later used by the PHI placement
|
corresponding block. This is later used by the PHI placement
|
algorithm to make PHI pruning decisions. */
|
algorithm to make PHI pruning decisions. */
|
|
|
static void
|
static void
|
prepare_block_for_update (basic_block bb, bool insert_phi_p)
|
prepare_block_for_update (basic_block bb, bool insert_phi_p)
|
{
|
{
|
basic_block son;
|
basic_block son;
|
block_stmt_iterator si;
|
block_stmt_iterator si;
|
tree phi;
|
tree phi;
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
mark_block_for_update (bb);
|
mark_block_for_update (bb);
|
|
|
/* Process PHI nodes marking interesting those that define or use
|
/* Process PHI nodes marking interesting those that define or use
|
the symbols that we are interested in. */
|
the symbols that we are interested in. */
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
{
|
{
|
tree lhs_sym, lhs = PHI_RESULT (phi);
|
tree lhs_sym, lhs = PHI_RESULT (phi);
|
|
|
lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
|
lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
|
|
|
if (!symbol_marked_for_renaming (lhs_sym))
|
if (!symbol_marked_for_renaming (lhs_sym))
|
continue;
|
continue;
|
mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
|
mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
|
|
|
/* Mark the uses in phi nodes as interesting. It would be more correct
|
/* Mark the uses in phi nodes as interesting. It would be more correct
|
to process the arguments of the phi nodes of the successor edges of
|
to process the arguments of the phi nodes of the successor edges of
|
BB at the end of prepare_block_for_update, however, that turns out
|
BB at the end of prepare_block_for_update, however, that turns out
|
to be significantly more expensive. Doing it here is conservatively
|
to be significantly more expensive. Doing it here is conservatively
|
correct -- it may only cause us to believe a value to be live in a
|
correct -- it may only cause us to believe a value to be live in a
|
block that also contains its definition, and thus insert a few more
|
block that also contains its definition, and thus insert a few more
|
phi nodes for it. */
|
phi nodes for it. */
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
{
|
{
|
mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
|
mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
|
}
|
}
|
}
|
}
|
|
|
/* Process the statements. */
|
/* Process the statements. */
|
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
|
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
|
{
|
{
|
tree stmt;
|
tree stmt;
|
ssa_op_iter i;
|
ssa_op_iter i;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
def_operand_p def_p;
|
def_operand_p def_p;
|
|
|
stmt = bsi_stmt (si);
|
stmt = bsi_stmt (si);
|
|
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE)
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE)
|
{
|
{
|
tree use = USE_FROM_PTR (use_p);
|
tree use = USE_FROM_PTR (use_p);
|
tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
|
tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
|
if (symbol_marked_for_renaming (sym))
|
if (symbol_marked_for_renaming (sym))
|
mark_use_interesting (use, stmt, bb, insert_phi_p);
|
mark_use_interesting (use, stmt, bb, insert_phi_p);
|
}
|
}
|
|
|
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF)
|
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF)
|
{
|
{
|
tree def = DEF_FROM_PTR (def_p);
|
tree def = DEF_FROM_PTR (def_p);
|
tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
|
tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
|
|
|
if (symbol_marked_for_renaming (sym))
|
if (symbol_marked_for_renaming (sym))
|
mark_def_interesting (def, stmt, bb, insert_phi_p);
|
mark_def_interesting (def, stmt, bb, insert_phi_p);
|
}
|
}
|
|
|
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_VIRTUAL_DEFS)
|
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_VIRTUAL_DEFS)
|
{
|
{
|
tree def = DEF_FROM_PTR (def_p);
|
tree def = DEF_FROM_PTR (def_p);
|
tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
|
tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
|
|
|
if (symbol_marked_for_renaming (sym))
|
if (symbol_marked_for_renaming (sym))
|
{
|
{
|
mark_use_interesting (sym, stmt, bb, insert_phi_p);
|
mark_use_interesting (sym, stmt, bb, insert_phi_p);
|
mark_def_interesting (sym, stmt, bb, insert_phi_p);
|
mark_def_interesting (sym, stmt, bb, insert_phi_p);
|
}
|
}
|
}
|
}
|
|
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_VUSE)
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_VUSE)
|
{
|
{
|
tree use = USE_FROM_PTR (use_p);
|
tree use = USE_FROM_PTR (use_p);
|
tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
|
tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
|
|
|
if (symbol_marked_for_renaming (sym))
|
if (symbol_marked_for_renaming (sym))
|
mark_use_interesting (sym, stmt, bb, insert_phi_p);
|
mark_use_interesting (sym, stmt, bb, insert_phi_p);
|
}
|
}
|
}
|
}
|
|
|
/* Now visit all the blocks dominated by BB. */
|
/* Now visit all the blocks dominated by BB. */
|
for (son = first_dom_son (CDI_DOMINATORS, bb);
|
for (son = first_dom_son (CDI_DOMINATORS, bb);
|
son;
|
son;
|
son = next_dom_son (CDI_DOMINATORS, son))
|
son = next_dom_son (CDI_DOMINATORS, son))
|
prepare_block_for_update (son, insert_phi_p);
|
prepare_block_for_update (son, insert_phi_p);
|
}
|
}
|
|
|
|
|
/* Helper for prepare_names_to_update. Mark all the use sites for
|
/* Helper for prepare_names_to_update. Mark all the use sites for
|
NAME as interesting. BLOCKS and INSERT_PHI_P are as in
|
NAME as interesting. BLOCKS and INSERT_PHI_P are as in
|
prepare_names_to_update. */
|
prepare_names_to_update. */
|
|
|
static void
|
static void
|
prepare_use_sites_for (tree name, bool insert_phi_p)
|
prepare_use_sites_for (tree name, bool insert_phi_p)
|
{
|
{
|
use_operand_p use_p;
|
use_operand_p use_p;
|
imm_use_iterator iter;
|
imm_use_iterator iter;
|
|
|
FOR_EACH_IMM_USE_FAST (use_p, iter, name)
|
FOR_EACH_IMM_USE_FAST (use_p, iter, name)
|
{
|
{
|
tree stmt = USE_STMT (use_p);
|
tree stmt = USE_STMT (use_p);
|
basic_block bb = bb_for_stmt (stmt);
|
basic_block bb = bb_for_stmt (stmt);
|
|
|
if (TREE_CODE (stmt) == PHI_NODE)
|
if (TREE_CODE (stmt) == PHI_NODE)
|
{
|
{
|
int ix = PHI_ARG_INDEX_FROM_USE (use_p);
|
int ix = PHI_ARG_INDEX_FROM_USE (use_p);
|
edge e = PHI_ARG_EDGE (stmt, ix);
|
edge e = PHI_ARG_EDGE (stmt, ix);
|
mark_use_interesting (name, stmt, e->src, insert_phi_p);
|
mark_use_interesting (name, stmt, e->src, insert_phi_p);
|
}
|
}
|
else
|
else
|
{
|
{
|
/* For regular statements, mark this as an interesting use
|
/* For regular statements, mark this as an interesting use
|
for NAME. */
|
for NAME. */
|
mark_use_interesting (name, stmt, bb, insert_phi_p);
|
mark_use_interesting (name, stmt, bb, insert_phi_p);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Helper for prepare_names_to_update. Mark the definition site for
|
/* Helper for prepare_names_to_update. Mark the definition site for
|
NAME as interesting. BLOCKS and INSERT_PHI_P are as in
|
NAME as interesting. BLOCKS and INSERT_PHI_P are as in
|
prepare_names_to_update. */
|
prepare_names_to_update. */
|
|
|
static void
|
static void
|
prepare_def_site_for (tree name, bool insert_phi_p)
|
prepare_def_site_for (tree name, bool insert_phi_p)
|
{
|
{
|
tree stmt;
|
tree stmt;
|
basic_block bb;
|
basic_block bb;
|
|
|
gcc_assert (names_to_release == NULL
|
gcc_assert (names_to_release == NULL
|
|| !bitmap_bit_p (names_to_release, SSA_NAME_VERSION (name)));
|
|| !bitmap_bit_p (names_to_release, SSA_NAME_VERSION (name)));
|
|
|
stmt = SSA_NAME_DEF_STMT (name);
|
stmt = SSA_NAME_DEF_STMT (name);
|
bb = bb_for_stmt (stmt);
|
bb = bb_for_stmt (stmt);
|
if (bb)
|
if (bb)
|
{
|
{
|
gcc_assert (bb->index < last_basic_block);
|
gcc_assert (bb->index < last_basic_block);
|
mark_block_for_update (bb);
|
mark_block_for_update (bb);
|
mark_def_interesting (name, stmt, bb, insert_phi_p);
|
mark_def_interesting (name, stmt, bb, insert_phi_p);
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Mark definition and use sites of names in NEW_SSA_NAMES and
|
/* Mark definition and use sites of names in NEW_SSA_NAMES and
|
OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
|
OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
|
PHI nodes for newly created names. */
|
PHI nodes for newly created names. */
|
|
|
static void
|
static void
|
prepare_names_to_update (bool insert_phi_p)
|
prepare_names_to_update (bool insert_phi_p)
|
{
|
{
|
unsigned i = 0;
|
unsigned i = 0;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
sbitmap_iterator sbi;
|
sbitmap_iterator sbi;
|
|
|
/* If a name N from NEW_SSA_NAMES is also marked to be released,
|
/* If a name N from NEW_SSA_NAMES is also marked to be released,
|
remove it from NEW_SSA_NAMES so that we don't try to visit its
|
remove it from NEW_SSA_NAMES so that we don't try to visit its
|
defining basic block (which most likely doesn't exist). Notice
|
defining basic block (which most likely doesn't exist). Notice
|
that we cannot do the same with names in OLD_SSA_NAMES because we
|
that we cannot do the same with names in OLD_SSA_NAMES because we
|
want to replace existing instances. */
|
want to replace existing instances. */
|
if (names_to_release)
|
if (names_to_release)
|
EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
|
RESET_BIT (new_ssa_names, i);
|
RESET_BIT (new_ssa_names, i);
|
|
|
/* First process names in NEW_SSA_NAMES. Otherwise, uses of old
|
/* First process names in NEW_SSA_NAMES. Otherwise, uses of old
|
names may be considered to be live-in on blocks that contain
|
names may be considered to be live-in on blocks that contain
|
definitions for their replacements. */
|
definitions for their replacements. */
|
EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
|
EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
|
prepare_def_site_for (ssa_name (i), insert_phi_p);
|
prepare_def_site_for (ssa_name (i), insert_phi_p);
|
|
|
/* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
|
/* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
|
OLD_SSA_NAMES, but we have to ignore its definition site. */
|
OLD_SSA_NAMES, but we have to ignore its definition site. */
|
EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
|
EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
|
{
|
{
|
if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
|
if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
|
prepare_def_site_for (ssa_name (i), insert_phi_p);
|
prepare_def_site_for (ssa_name (i), insert_phi_p);
|
prepare_use_sites_for (ssa_name (i), insert_phi_p);
|
prepare_use_sites_for (ssa_name (i), insert_phi_p);
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Dump all the names replaced by NAME to FILE. */
|
/* Dump all the names replaced by NAME to FILE. */
|
|
|
void
|
void
|
dump_names_replaced_by (FILE *file, tree name)
|
dump_names_replaced_by (FILE *file, tree name)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
bitmap old_set;
|
bitmap old_set;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
|
|
print_generic_expr (file, name, 0);
|
print_generic_expr (file, name, 0);
|
fprintf (file, " -> { ");
|
fprintf (file, " -> { ");
|
|
|
old_set = names_replaced_by (name);
|
old_set = names_replaced_by (name);
|
EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
|
{
|
{
|
print_generic_expr (file, ssa_name (i), 0);
|
print_generic_expr (file, ssa_name (i), 0);
|
fprintf (file, " ");
|
fprintf (file, " ");
|
}
|
}
|
|
|
fprintf (file, "}\n");
|
fprintf (file, "}\n");
|
}
|
}
|
|
|
|
|
/* Dump all the names replaced by NAME to stderr. */
|
/* Dump all the names replaced by NAME to stderr. */
|
|
|
void
|
void
|
debug_names_replaced_by (tree name)
|
debug_names_replaced_by (tree name)
|
{
|
{
|
dump_names_replaced_by (stderr, name);
|
dump_names_replaced_by (stderr, name);
|
}
|
}
|
|
|
|
|
/* Dump SSA update information to FILE. */
|
/* Dump SSA update information to FILE. */
|
|
|
void
|
void
|
dump_update_ssa (FILE *file)
|
dump_update_ssa (FILE *file)
|
{
|
{
|
unsigned i = 0;
|
unsigned i = 0;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
|
|
if (!need_ssa_update_p ())
|
if (!need_ssa_update_p ())
|
return;
|
return;
|
|
|
if (new_ssa_names && sbitmap_first_set_bit (new_ssa_names) >= 0)
|
if (new_ssa_names && sbitmap_first_set_bit (new_ssa_names) >= 0)
|
{
|
{
|
sbitmap_iterator sbi;
|
sbitmap_iterator sbi;
|
|
|
fprintf (file, "\nSSA replacement table\n");
|
fprintf (file, "\nSSA replacement table\n");
|
fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
|
fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
|
"O_1, ..., O_j\n\n");
|
"O_1, ..., O_j\n\n");
|
|
|
EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
|
EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
|
dump_names_replaced_by (file, ssa_name (i));
|
dump_names_replaced_by (file, ssa_name (i));
|
|
|
fprintf (file, "\n");
|
fprintf (file, "\n");
|
fprintf (file, "Number of virtual NEW -> OLD mappings: %7u\n",
|
fprintf (file, "Number of virtual NEW -> OLD mappings: %7u\n",
|
update_ssa_stats.num_virtual_mappings);
|
update_ssa_stats.num_virtual_mappings);
|
fprintf (file, "Number of real NEW -> OLD mappings: %7u\n",
|
fprintf (file, "Number of real NEW -> OLD mappings: %7u\n",
|
update_ssa_stats.num_total_mappings
|
update_ssa_stats.num_total_mappings
|
- update_ssa_stats.num_virtual_mappings);
|
- update_ssa_stats.num_virtual_mappings);
|
fprintf (file, "Number of total NEW -> OLD mappings: %7u\n",
|
fprintf (file, "Number of total NEW -> OLD mappings: %7u\n",
|
update_ssa_stats.num_total_mappings);
|
update_ssa_stats.num_total_mappings);
|
|
|
fprintf (file, "\nNumber of virtual symbols: %u\n",
|
fprintf (file, "\nNumber of virtual symbols: %u\n",
|
update_ssa_stats.num_virtual_symbols);
|
update_ssa_stats.num_virtual_symbols);
|
}
|
}
|
|
|
if (syms_to_rename && !bitmap_empty_p (syms_to_rename))
|
if (syms_to_rename && !bitmap_empty_p (syms_to_rename))
|
{
|
{
|
fprintf (file, "\n\nSymbols to be put in SSA form\n\n");
|
fprintf (file, "\n\nSymbols to be put in SSA form\n\n");
|
EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
|
{
|
{
|
print_generic_expr (file, referenced_var (i), 0);
|
print_generic_expr (file, referenced_var (i), 0);
|
fprintf (file, " ");
|
fprintf (file, " ");
|
}
|
}
|
}
|
}
|
|
|
if (names_to_release && !bitmap_empty_p (names_to_release))
|
if (names_to_release && !bitmap_empty_p (names_to_release))
|
{
|
{
|
fprintf (file, "\n\nSSA names to release after updating the SSA web\n\n");
|
fprintf (file, "\n\nSSA names to release after updating the SSA web\n\n");
|
EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
|
{
|
{
|
print_generic_expr (file, ssa_name (i), 0);
|
print_generic_expr (file, ssa_name (i), 0);
|
fprintf (file, " ");
|
fprintf (file, " ");
|
}
|
}
|
}
|
}
|
|
|
fprintf (file, "\n\n");
|
fprintf (file, "\n\n");
|
}
|
}
|
|
|
|
|
/* Dump SSA update information to stderr. */
|
/* Dump SSA update information to stderr. */
|
|
|
void
|
void
|
debug_update_ssa (void)
|
debug_update_ssa (void)
|
{
|
{
|
dump_update_ssa (stderr);
|
dump_update_ssa (stderr);
|
}
|
}
|
|
|
|
|
/* Initialize data structures used for incremental SSA updates. */
|
/* Initialize data structures used for incremental SSA updates. */
|
|
|
static void
|
static void
|
init_update_ssa (void)
|
init_update_ssa (void)
|
{
|
{
|
/* Reserve more space than the current number of names. The calls to
|
/* Reserve more space than the current number of names. The calls to
|
add_new_name_mapping are typically done after creating new SSA
|
add_new_name_mapping are typically done after creating new SSA
|
names, so we'll need to reallocate these arrays. */
|
names, so we'll need to reallocate these arrays. */
|
old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
|
old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
|
sbitmap_zero (old_ssa_names);
|
sbitmap_zero (old_ssa_names);
|
|
|
new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
|
new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
|
sbitmap_zero (new_ssa_names);
|
sbitmap_zero (new_ssa_names);
|
|
|
repl_tbl = htab_create (20, repl_map_hash, repl_map_eq, repl_map_free);
|
repl_tbl = htab_create (20, repl_map_hash, repl_map_eq, repl_map_free);
|
need_to_initialize_update_ssa_p = false;
|
need_to_initialize_update_ssa_p = false;
|
need_to_update_vops_p = false;
|
need_to_update_vops_p = false;
|
syms_to_rename = BITMAP_ALLOC (NULL);
|
syms_to_rename = BITMAP_ALLOC (NULL);
|
names_to_release = NULL;
|
names_to_release = NULL;
|
memset (&update_ssa_stats, 0, sizeof (update_ssa_stats));
|
memset (&update_ssa_stats, 0, sizeof (update_ssa_stats));
|
update_ssa_stats.virtual_symbols = BITMAP_ALLOC (NULL);
|
update_ssa_stats.virtual_symbols = BITMAP_ALLOC (NULL);
|
}
|
}
|
|
|
|
|
/* Deallocate data structures used for incremental SSA updates. */
|
/* Deallocate data structures used for incremental SSA updates. */
|
|
|
void
|
void
|
delete_update_ssa (void)
|
delete_update_ssa (void)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
|
|
sbitmap_free (old_ssa_names);
|
sbitmap_free (old_ssa_names);
|
old_ssa_names = NULL;
|
old_ssa_names = NULL;
|
|
|
sbitmap_free (new_ssa_names);
|
sbitmap_free (new_ssa_names);
|
new_ssa_names = NULL;
|
new_ssa_names = NULL;
|
|
|
htab_delete (repl_tbl);
|
htab_delete (repl_tbl);
|
repl_tbl = NULL;
|
repl_tbl = NULL;
|
|
|
need_to_initialize_update_ssa_p = true;
|
need_to_initialize_update_ssa_p = true;
|
need_to_update_vops_p = false;
|
need_to_update_vops_p = false;
|
BITMAP_FREE (syms_to_rename);
|
BITMAP_FREE (syms_to_rename);
|
BITMAP_FREE (update_ssa_stats.virtual_symbols);
|
BITMAP_FREE (update_ssa_stats.virtual_symbols);
|
|
|
if (names_to_release)
|
if (names_to_release)
|
{
|
{
|
EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
|
release_ssa_name (ssa_name (i));
|
release_ssa_name (ssa_name (i));
|
BITMAP_FREE (names_to_release);
|
BITMAP_FREE (names_to_release);
|
}
|
}
|
|
|
clear_ssa_name_info ();
|
clear_ssa_name_info ();
|
}
|
}
|
|
|
|
|
/* Create a new name for OLD_NAME in statement STMT and replace the
|
/* Create a new name for OLD_NAME in statement STMT and replace the
|
operand pointed to by DEF_P with the newly created name. Return
|
operand pointed to by DEF_P with the newly created name. Return
|
the new name and register the replacement mapping <NEW, OLD> in
|
the new name and register the replacement mapping <NEW, OLD> in
|
update_ssa's tables. */
|
update_ssa's tables. */
|
|
|
tree
|
tree
|
create_new_def_for (tree old_name, tree stmt, def_operand_p def)
|
create_new_def_for (tree old_name, tree stmt, def_operand_p def)
|
{
|
{
|
tree new_name = duplicate_ssa_name (old_name, stmt);
|
tree new_name = duplicate_ssa_name (old_name, stmt);
|
|
|
SET_DEF (def, new_name);
|
SET_DEF (def, new_name);
|
|
|
if (TREE_CODE (stmt) == PHI_NODE)
|
if (TREE_CODE (stmt) == PHI_NODE)
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
basic_block bb = bb_for_stmt (stmt);
|
basic_block bb = bb_for_stmt (stmt);
|
|
|
/* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
|
/* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
if (e->flags & EDGE_ABNORMAL)
|
if (e->flags & EDGE_ABNORMAL)
|
{
|
{
|
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
|
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
|
break;
|
break;
|
}
|
}
|
}
|
}
|
|
|
register_new_name_mapping (new_name, old_name);
|
register_new_name_mapping (new_name, old_name);
|
|
|
/* For the benefit of passes that will be updating the SSA form on
|
/* For the benefit of passes that will be updating the SSA form on
|
their own, set the current reaching definition of OLD_NAME to be
|
their own, set the current reaching definition of OLD_NAME to be
|
NEW_NAME. */
|
NEW_NAME. */
|
set_current_def (old_name, new_name);
|
set_current_def (old_name, new_name);
|
|
|
return new_name;
|
return new_name;
|
}
|
}
|
|
|
|
|
/* Register name NEW to be a replacement for name OLD. This function
|
/* Register name NEW to be a replacement for name OLD. This function
|
must be called for every replacement that should be performed by
|
must be called for every replacement that should be performed by
|
update_ssa. */
|
update_ssa. */
|
|
|
void
|
void
|
register_new_name_mapping (tree new, tree old)
|
register_new_name_mapping (tree new, tree old)
|
{
|
{
|
if (need_to_initialize_update_ssa_p)
|
if (need_to_initialize_update_ssa_p)
|
init_update_ssa ();
|
init_update_ssa ();
|
|
|
add_new_name_mapping (new, old);
|
add_new_name_mapping (new, old);
|
}
|
}
|
|
|
|
|
/* Register symbol SYM to be renamed by update_ssa. */
|
/* Register symbol SYM to be renamed by update_ssa. */
|
|
|
void
|
void
|
mark_sym_for_renaming (tree sym)
|
mark_sym_for_renaming (tree sym)
|
{
|
{
|
if (need_to_initialize_update_ssa_p)
|
if (need_to_initialize_update_ssa_p)
|
init_update_ssa ();
|
init_update_ssa ();
|
|
|
bitmap_set_bit (syms_to_rename, DECL_UID (sym));
|
bitmap_set_bit (syms_to_rename, DECL_UID (sym));
|
|
|
if (!is_gimple_reg (sym))
|
if (!is_gimple_reg (sym))
|
need_to_update_vops_p = true;
|
need_to_update_vops_p = true;
|
}
|
}
|
|
|
|
|
/* Register all the symbols in SET to be renamed by update_ssa. */
|
/* Register all the symbols in SET to be renamed by update_ssa. */
|
|
|
void
|
void
|
mark_set_for_renaming (bitmap set)
|
mark_set_for_renaming (bitmap set)
|
{
|
{
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
unsigned i;
|
unsigned i;
|
|
|
if (bitmap_empty_p (set))
|
if (bitmap_empty_p (set))
|
return;
|
return;
|
|
|
if (need_to_initialize_update_ssa_p)
|
if (need_to_initialize_update_ssa_p)
|
init_update_ssa ();
|
init_update_ssa ();
|
|
|
bitmap_ior_into (syms_to_rename, set);
|
bitmap_ior_into (syms_to_rename, set);
|
|
|
EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
|
if (!is_gimple_reg (referenced_var (i)))
|
if (!is_gimple_reg (referenced_var (i)))
|
{
|
{
|
need_to_update_vops_p = true;
|
need_to_update_vops_p = true;
|
break;
|
break;
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Return true if there is any work to be done by update_ssa. */
|
/* Return true if there is any work to be done by update_ssa. */
|
|
|
bool
|
bool
|
need_ssa_update_p (void)
|
need_ssa_update_p (void)
|
{
|
{
|
return syms_to_rename || old_ssa_names || new_ssa_names;
|
return syms_to_rename || old_ssa_names || new_ssa_names;
|
}
|
}
|
|
|
|
|
/* Return true if name N has been registered in the replacement table. */
|
/* Return true if name N has been registered in the replacement table. */
|
|
|
bool
|
bool
|
name_registered_for_update_p (tree n)
|
name_registered_for_update_p (tree n)
|
{
|
{
|
if (!need_ssa_update_p ())
|
if (!need_ssa_update_p ())
|
return false;
|
return false;
|
|
|
return is_new_name (n)
|
return is_new_name (n)
|
|| is_old_name (n)
|
|| is_old_name (n)
|
|| symbol_marked_for_renaming (SSA_NAME_VAR (n));
|
|| symbol_marked_for_renaming (SSA_NAME_VAR (n));
|
}
|
}
|
|
|
|
|
/* Return the set of all the SSA names marked to be replaced. */
|
/* Return the set of all the SSA names marked to be replaced. */
|
|
|
bitmap
|
bitmap
|
ssa_names_to_replace (void)
|
ssa_names_to_replace (void)
|
{
|
{
|
unsigned i = 0;
|
unsigned i = 0;
|
bitmap ret;
|
bitmap ret;
|
sbitmap_iterator sbi;
|
sbitmap_iterator sbi;
|
|
|
ret = BITMAP_ALLOC (NULL);
|
ret = BITMAP_ALLOC (NULL);
|
EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
|
EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
|
bitmap_set_bit (ret, i);
|
bitmap_set_bit (ret, i);
|
|
|
return ret;
|
return ret;
|
}
|
}
|
|
|
|
|
/* Mark NAME to be released after update_ssa has finished. */
|
/* Mark NAME to be released after update_ssa has finished. */
|
|
|
void
|
void
|
release_ssa_name_after_update_ssa (tree name)
|
release_ssa_name_after_update_ssa (tree name)
|
{
|
{
|
gcc_assert (!need_to_initialize_update_ssa_p);
|
gcc_assert (!need_to_initialize_update_ssa_p);
|
|
|
if (names_to_release == NULL)
|
if (names_to_release == NULL)
|
names_to_release = BITMAP_ALLOC (NULL);
|
names_to_release = BITMAP_ALLOC (NULL);
|
|
|
bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
|
bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
|
}
|
}
|
|
|
|
|
/* Insert new PHI nodes to replace VAR. DFS contains dominance
|
/* Insert new PHI nodes to replace VAR. DFS contains dominance
|
frontier information. BLOCKS is the set of blocks to be updated.
|
frontier information. BLOCKS is the set of blocks to be updated.
|
|
|
This is slightly different than the regular PHI insertion
|
This is slightly different than the regular PHI insertion
|
algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
|
algorithm. The value of UPDATE_FLAGS controls how PHI nodes for
|
real names (i.e., GIMPLE registers) are inserted:
|
real names (i.e., GIMPLE registers) are inserted:
|
|
|
- If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
|
- If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
|
nodes inside the region affected by the block that defines VAR
|
nodes inside the region affected by the block that defines VAR
|
and the blocks that define all its replacements. All these
|
and the blocks that define all its replacements. All these
|
definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
|
definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
|
|
|
First, we compute the entry point to the region (ENTRY). This is
|
First, we compute the entry point to the region (ENTRY). This is
|
given by the nearest common dominator to all the definition
|
given by the nearest common dominator to all the definition
|
blocks. When computing the iterated dominance frontier (IDF), any
|
blocks. When computing the iterated dominance frontier (IDF), any
|
block not strictly dominated by ENTRY is ignored.
|
block not strictly dominated by ENTRY is ignored.
|
|
|
We then call the standard PHI insertion algorithm with the pruned
|
We then call the standard PHI insertion algorithm with the pruned
|
IDF.
|
IDF.
|
|
|
- If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
|
- If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
|
names is not pruned. PHI nodes are inserted at every IDF block. */
|
names is not pruned. PHI nodes are inserted at every IDF block. */
|
|
|
static void
|
static void
|
insert_updated_phi_nodes_for (tree var, bitmap *dfs, bitmap blocks,
|
insert_updated_phi_nodes_for (tree var, bitmap *dfs, bitmap blocks,
|
unsigned update_flags)
|
unsigned update_flags)
|
{
|
{
|
basic_block entry;
|
basic_block entry;
|
struct def_blocks_d *db;
|
struct def_blocks_d *db;
|
bitmap idf, pruned_idf;
|
bitmap idf, pruned_idf;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
unsigned i;
|
unsigned i;
|
|
|
#if defined ENABLE_CHECKING
|
#if defined ENABLE_CHECKING
|
if (TREE_CODE (var) == SSA_NAME)
|
if (TREE_CODE (var) == SSA_NAME)
|
gcc_assert (is_old_name (var));
|
gcc_assert (is_old_name (var));
|
else
|
else
|
gcc_assert (symbol_marked_for_renaming (var));
|
gcc_assert (symbol_marked_for_renaming (var));
|
#endif
|
#endif
|
|
|
/* Get all the definition sites for VAR. */
|
/* Get all the definition sites for VAR. */
|
db = find_def_blocks_for (var);
|
db = find_def_blocks_for (var);
|
|
|
/* No need to do anything if there were no definitions to VAR. */
|
/* No need to do anything if there were no definitions to VAR. */
|
if (db == NULL || bitmap_empty_p (db->def_blocks))
|
if (db == NULL || bitmap_empty_p (db->def_blocks))
|
return;
|
return;
|
|
|
/* Compute the initial iterated dominance frontier. */
|
/* Compute the initial iterated dominance frontier. */
|
idf = find_idf (db->def_blocks, dfs);
|
idf = find_idf (db->def_blocks, dfs);
|
pruned_idf = BITMAP_ALLOC (NULL);
|
pruned_idf = BITMAP_ALLOC (NULL);
|
|
|
if (TREE_CODE (var) == SSA_NAME)
|
if (TREE_CODE (var) == SSA_NAME)
|
{
|
{
|
if (update_flags == TODO_update_ssa)
|
if (update_flags == TODO_update_ssa)
|
{
|
{
|
/* If doing regular SSA updates for GIMPLE registers, we are
|
/* If doing regular SSA updates for GIMPLE registers, we are
|
only interested in IDF blocks dominated by the nearest
|
only interested in IDF blocks dominated by the nearest
|
common dominator of all the definition blocks. */
|
common dominator of all the definition blocks. */
|
entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
|
entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
|
db->def_blocks);
|
db->def_blocks);
|
|
|
if (entry != ENTRY_BLOCK_PTR)
|
if (entry != ENTRY_BLOCK_PTR)
|
EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
|
if (BASIC_BLOCK (i) != entry
|
if (BASIC_BLOCK (i) != entry
|
&& dominated_by_p (CDI_DOMINATORS, BASIC_BLOCK (i), entry))
|
&& dominated_by_p (CDI_DOMINATORS, BASIC_BLOCK (i), entry))
|
bitmap_set_bit (pruned_idf, i);
|
bitmap_set_bit (pruned_idf, i);
|
}
|
}
|
else
|
else
|
{
|
{
|
/* Otherwise, do not prune the IDF for VAR. */
|
/* Otherwise, do not prune the IDF for VAR. */
|
gcc_assert (update_flags == TODO_update_ssa_full_phi);
|
gcc_assert (update_flags == TODO_update_ssa_full_phi);
|
bitmap_copy (pruned_idf, idf);
|
bitmap_copy (pruned_idf, idf);
|
}
|
}
|
}
|
}
|
else
|
else
|
{
|
{
|
/* Otherwise, VAR is a symbol that needs to be put into SSA form
|
/* Otherwise, VAR is a symbol that needs to be put into SSA form
|
for the first time, so we need to compute the full IDF for
|
for the first time, so we need to compute the full IDF for
|
it. */
|
it. */
|
bitmap_copy (pruned_idf, idf);
|
bitmap_copy (pruned_idf, idf);
|
}
|
}
|
|
|
if (!bitmap_empty_p (pruned_idf))
|
if (!bitmap_empty_p (pruned_idf))
|
{
|
{
|
/* Make sure that PRUNED_IDF blocks and all their feeding blocks
|
/* Make sure that PRUNED_IDF blocks and all their feeding blocks
|
are included in the region to be updated. The feeding blocks
|
are included in the region to be updated. The feeding blocks
|
are important to guarantee that the PHI arguments are renamed
|
are important to guarantee that the PHI arguments are renamed
|
properly. */
|
properly. */
|
bitmap_ior_into (blocks, pruned_idf);
|
bitmap_ior_into (blocks, pruned_idf);
|
EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
basic_block bb = BASIC_BLOCK (i);
|
basic_block bb = BASIC_BLOCK (i);
|
|
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
if (e->src->index >= 0)
|
if (e->src->index >= 0)
|
bitmap_set_bit (blocks, e->src->index);
|
bitmap_set_bit (blocks, e->src->index);
|
}
|
}
|
|
|
insert_phi_nodes_for (var, pruned_idf, true);
|
insert_phi_nodes_for (var, pruned_idf, true);
|
}
|
}
|
|
|
BITMAP_FREE (pruned_idf);
|
BITMAP_FREE (pruned_idf);
|
BITMAP_FREE (idf);
|
BITMAP_FREE (idf);
|
}
|
}
|
|
|
|
|
/* Heuristic to determine whether SSA name mappings for virtual names
|
/* Heuristic to determine whether SSA name mappings for virtual names
|
should be discarded and their symbols rewritten from scratch. When
|
should be discarded and their symbols rewritten from scratch. When
|
there is a large number of mappings for virtual names, the
|
there is a large number of mappings for virtual names, the
|
insertion of PHI nodes for the old names in the mappings takes
|
insertion of PHI nodes for the old names in the mappings takes
|
considerable more time than if we inserted PHI nodes for the
|
considerable more time than if we inserted PHI nodes for the
|
symbols instead.
|
symbols instead.
|
|
|
Currently the heuristic takes these stats into account:
|
Currently the heuristic takes these stats into account:
|
|
|
- Number of mappings for virtual SSA names.
|
- Number of mappings for virtual SSA names.
|
- Number of distinct virtual symbols involved in those mappings.
|
- Number of distinct virtual symbols involved in those mappings.
|
|
|
If the number of virtual mappings is much larger than the number of
|
If the number of virtual mappings is much larger than the number of
|
virtual symbols, then it will be faster to compute PHI insertion
|
virtual symbols, then it will be faster to compute PHI insertion
|
spots for the symbols. Even if this involves traversing the whole
|
spots for the symbols. Even if this involves traversing the whole
|
CFG, which is what happens when symbols are renamed from scratch. */
|
CFG, which is what happens when symbols are renamed from scratch. */
|
|
|
static bool
|
static bool
|
switch_virtuals_to_full_rewrite_p (void)
|
switch_virtuals_to_full_rewrite_p (void)
|
{
|
{
|
if (update_ssa_stats.num_virtual_mappings < (unsigned) MIN_VIRTUAL_MAPPINGS)
|
if (update_ssa_stats.num_virtual_mappings < (unsigned) MIN_VIRTUAL_MAPPINGS)
|
return false;
|
return false;
|
|
|
if (update_ssa_stats.num_virtual_mappings
|
if (update_ssa_stats.num_virtual_mappings
|
> (unsigned) VIRTUAL_MAPPINGS_TO_SYMS_RATIO
|
> (unsigned) VIRTUAL_MAPPINGS_TO_SYMS_RATIO
|
* update_ssa_stats.num_virtual_symbols)
|
* update_ssa_stats.num_virtual_symbols)
|
return true;
|
return true;
|
|
|
return false;
|
return false;
|
}
|
}
|
|
|
|
|
/* Remove every virtual mapping and mark all the affected virtual
|
/* Remove every virtual mapping and mark all the affected virtual
|
symbols for renaming. */
|
symbols for renaming. */
|
|
|
static void
|
static void
|
switch_virtuals_to_full_rewrite (void)
|
switch_virtuals_to_full_rewrite (void)
|
{
|
{
|
unsigned i = 0;
|
unsigned i = 0;
|
sbitmap_iterator sbi;
|
sbitmap_iterator sbi;
|
|
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
fprintf (dump_file, "\nEnabled virtual name mapping heuristic.\n");
|
fprintf (dump_file, "\nEnabled virtual name mapping heuristic.\n");
|
fprintf (dump_file, "\tNumber of virtual mappings: %7u\n",
|
fprintf (dump_file, "\tNumber of virtual mappings: %7u\n",
|
update_ssa_stats.num_virtual_mappings);
|
update_ssa_stats.num_virtual_mappings);
|
fprintf (dump_file, "\tNumber of unique virtual symbols: %7u\n",
|
fprintf (dump_file, "\tNumber of unique virtual symbols: %7u\n",
|
update_ssa_stats.num_virtual_symbols);
|
update_ssa_stats.num_virtual_symbols);
|
fprintf (dump_file, "Updating FUD-chains from top of CFG will be "
|
fprintf (dump_file, "Updating FUD-chains from top of CFG will be "
|
"faster than processing\nthe name mappings.\n\n");
|
"faster than processing\nthe name mappings.\n\n");
|
}
|
}
|
|
|
/* Remove all virtual names from NEW_SSA_NAMES and OLD_SSA_NAMES.
|
/* Remove all virtual names from NEW_SSA_NAMES and OLD_SSA_NAMES.
|
Note that it is not really necessary to remove the mappings from
|
Note that it is not really necessary to remove the mappings from
|
REPL_TBL, that would only waste time. */
|
REPL_TBL, that would only waste time. */
|
EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
|
EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
|
if (!is_gimple_reg (ssa_name (i)))
|
if (!is_gimple_reg (ssa_name (i)))
|
RESET_BIT (new_ssa_names, i);
|
RESET_BIT (new_ssa_names, i);
|
|
|
EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
|
EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
|
if (!is_gimple_reg (ssa_name (i)))
|
if (!is_gimple_reg (ssa_name (i)))
|
RESET_BIT (old_ssa_names, i);
|
RESET_BIT (old_ssa_names, i);
|
|
|
bitmap_ior_into (syms_to_rename, update_ssa_stats.virtual_symbols);
|
bitmap_ior_into (syms_to_rename, update_ssa_stats.virtual_symbols);
|
}
|
}
|
|
|
|
|
/* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
|
/* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
|
existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
|
existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
|
|
|
1- The names in OLD_SSA_NAMES dominated by the definitions of
|
1- The names in OLD_SSA_NAMES dominated by the definitions of
|
NEW_SSA_NAMES are all re-written to be reached by the
|
NEW_SSA_NAMES are all re-written to be reached by the
|
appropriate definition from NEW_SSA_NAMES.
|
appropriate definition from NEW_SSA_NAMES.
|
|
|
2- If needed, new PHI nodes are added to the iterated dominance
|
2- If needed, new PHI nodes are added to the iterated dominance
|
frontier of the blocks where each of NEW_SSA_NAMES are defined.
|
frontier of the blocks where each of NEW_SSA_NAMES are defined.
|
|
|
The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
|
The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
|
calling register_new_name_mapping for every pair of names that the
|
calling register_new_name_mapping for every pair of names that the
|
caller wants to replace.
|
caller wants to replace.
|
|
|
The caller identifies the new names that have been inserted and the
|
The caller identifies the new names that have been inserted and the
|
names that need to be replaced by calling register_new_name_mapping
|
names that need to be replaced by calling register_new_name_mapping
|
for every pair <NEW, OLD>. Note that the function assumes that the
|
for every pair <NEW, OLD>. Note that the function assumes that the
|
new names have already been inserted in the IL.
|
new names have already been inserted in the IL.
|
|
|
For instance, given the following code:
|
For instance, given the following code:
|
|
|
1 L0:
|
1 L0:
|
2 x_1 = PHI (0, x_5)
|
2 x_1 = PHI (0, x_5)
|
3 if (x_1 < 10)
|
3 if (x_1 < 10)
|
4 if (x_1 > 7)
|
4 if (x_1 > 7)
|
5 y_2 = 0
|
5 y_2 = 0
|
6 else
|
6 else
|
7 y_3 = x_1 + x_7
|
7 y_3 = x_1 + x_7
|
8 endif
|
8 endif
|
9 x_5 = x_1 + 1
|
9 x_5 = x_1 + 1
|
10 goto L0;
|
10 goto L0;
|
11 endif
|
11 endif
|
|
|
Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
|
Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
|
|
|
1 L0:
|
1 L0:
|
2 x_1 = PHI (0, x_5)
|
2 x_1 = PHI (0, x_5)
|
3 if (x_1 < 10)
|
3 if (x_1 < 10)
|
4 x_10 = ...
|
4 x_10 = ...
|
5 if (x_1 > 7)
|
5 if (x_1 > 7)
|
6 y_2 = 0
|
6 y_2 = 0
|
7 else
|
7 else
|
8 x_11 = ...
|
8 x_11 = ...
|
9 y_3 = x_1 + x_7
|
9 y_3 = x_1 + x_7
|
10 endif
|
10 endif
|
11 x_5 = x_1 + 1
|
11 x_5 = x_1 + 1
|
12 goto L0;
|
12 goto L0;
|
13 endif
|
13 endif
|
|
|
We want to replace all the uses of x_1 with the new definitions of
|
We want to replace all the uses of x_1 with the new definitions of
|
x_10 and x_11. Note that the only uses that should be replaced are
|
x_10 and x_11. Note that the only uses that should be replaced are
|
those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
|
those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should
|
*not* be replaced (this is why we cannot just mark symbol 'x' for
|
*not* be replaced (this is why we cannot just mark symbol 'x' for
|
renaming).
|
renaming).
|
|
|
Additionally, we may need to insert a PHI node at line 11 because
|
Additionally, we may need to insert a PHI node at line 11 because
|
that is a merge point for x_10 and x_11. So the use of x_1 at line
|
that is a merge point for x_10 and x_11. So the use of x_1 at line
|
11 will be replaced with the new PHI node. The insertion of PHI
|
11 will be replaced with the new PHI node. The insertion of PHI
|
nodes is optional. They are not strictly necessary to preserve the
|
nodes is optional. They are not strictly necessary to preserve the
|
SSA form, and depending on what the caller inserted, they may not
|
SSA form, and depending on what the caller inserted, they may not
|
even be useful for the optimizers. UPDATE_FLAGS controls various
|
even be useful for the optimizers. UPDATE_FLAGS controls various
|
aspects of how update_ssa operates, see the documentation for
|
aspects of how update_ssa operates, see the documentation for
|
TODO_update_ssa*. */
|
TODO_update_ssa*. */
|
|
|
void
|
void
|
update_ssa (unsigned update_flags)
|
update_ssa (unsigned update_flags)
|
{
|
{
|
basic_block bb, start_bb;
|
basic_block bb, start_bb;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
unsigned i = 0;
|
unsigned i = 0;
|
sbitmap tmp;
|
sbitmap tmp;
|
bool insert_phi_p;
|
bool insert_phi_p;
|
sbitmap_iterator sbi;
|
sbitmap_iterator sbi;
|
|
|
if (!need_ssa_update_p ())
|
if (!need_ssa_update_p ())
|
return;
|
return;
|
|
|
timevar_push (TV_TREE_SSA_INCREMENTAL);
|
timevar_push (TV_TREE_SSA_INCREMENTAL);
|
|
|
blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
|
blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
|
if (!phis_to_rewrite)
|
if (!phis_to_rewrite)
|
phis_to_rewrite = VEC_alloc (tree_vec, heap, last_basic_block);
|
phis_to_rewrite = VEC_alloc (tree_vec, heap, last_basic_block);
|
blocks_to_update = BITMAP_ALLOC (NULL);
|
blocks_to_update = BITMAP_ALLOC (NULL);
|
|
|
/* Ensure that the dominance information is up-to-date. */
|
/* Ensure that the dominance information is up-to-date. */
|
calculate_dominance_info (CDI_DOMINATORS);
|
calculate_dominance_info (CDI_DOMINATORS);
|
|
|
/* Only one update flag should be set. */
|
/* Only one update flag should be set. */
|
gcc_assert (update_flags == TODO_update_ssa
|
gcc_assert (update_flags == TODO_update_ssa
|
|| update_flags == TODO_update_ssa_no_phi
|
|| update_flags == TODO_update_ssa_no_phi
|
|| update_flags == TODO_update_ssa_full_phi
|
|| update_flags == TODO_update_ssa_full_phi
|
|| update_flags == TODO_update_ssa_only_virtuals);
|
|| update_flags == TODO_update_ssa_only_virtuals);
|
|
|
/* If we only need to update virtuals, remove all the mappings for
|
/* If we only need to update virtuals, remove all the mappings for
|
real names before proceeding. The caller is responsible for
|
real names before proceeding. The caller is responsible for
|
having dealt with the name mappings before calling update_ssa. */
|
having dealt with the name mappings before calling update_ssa. */
|
if (update_flags == TODO_update_ssa_only_virtuals)
|
if (update_flags == TODO_update_ssa_only_virtuals)
|
{
|
{
|
sbitmap_zero (old_ssa_names);
|
sbitmap_zero (old_ssa_names);
|
sbitmap_zero (new_ssa_names);
|
sbitmap_zero (new_ssa_names);
|
htab_empty (repl_tbl);
|
htab_empty (repl_tbl);
|
}
|
}
|
|
|
insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
|
insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
|
|
|
if (insert_phi_p)
|
if (insert_phi_p)
|
{
|
{
|
/* If the caller requested PHI nodes to be added, initialize
|
/* If the caller requested PHI nodes to be added, initialize
|
live-in information data structures (DEF_BLOCKS). */
|
live-in information data structures (DEF_BLOCKS). */
|
|
|
/* For each SSA name N, the DEF_BLOCKS table describes where the
|
/* For each SSA name N, the DEF_BLOCKS table describes where the
|
name is defined, which blocks have PHI nodes for N, and which
|
name is defined, which blocks have PHI nodes for N, and which
|
blocks have uses of N (i.e., N is live-on-entry in those
|
blocks have uses of N (i.e., N is live-on-entry in those
|
blocks). */
|
blocks). */
|
def_blocks = htab_create (num_ssa_names, def_blocks_hash,
|
def_blocks = htab_create (num_ssa_names, def_blocks_hash,
|
def_blocks_eq, def_blocks_free);
|
def_blocks_eq, def_blocks_free);
|
}
|
}
|
else
|
else
|
{
|
{
|
def_blocks = NULL;
|
def_blocks = NULL;
|
}
|
}
|
|
|
/* Heuristic to avoid massive slow downs when the replacement
|
/* Heuristic to avoid massive slow downs when the replacement
|
mappings include lots of virtual names. */
|
mappings include lots of virtual names. */
|
if (insert_phi_p && switch_virtuals_to_full_rewrite_p ())
|
if (insert_phi_p && switch_virtuals_to_full_rewrite_p ())
|
switch_virtuals_to_full_rewrite ();
|
switch_virtuals_to_full_rewrite ();
|
|
|
/* If there are names defined in the replacement table, prepare
|
/* If there are names defined in the replacement table, prepare
|
definition and use sites for all the names in NEW_SSA_NAMES and
|
definition and use sites for all the names in NEW_SSA_NAMES and
|
OLD_SSA_NAMES. */
|
OLD_SSA_NAMES. */
|
if (sbitmap_first_set_bit (new_ssa_names) >= 0)
|
if (sbitmap_first_set_bit (new_ssa_names) >= 0)
|
{
|
{
|
prepare_names_to_update (insert_phi_p);
|
prepare_names_to_update (insert_phi_p);
|
|
|
/* If all the names in NEW_SSA_NAMES had been marked for
|
/* If all the names in NEW_SSA_NAMES had been marked for
|
removal, and there are no symbols to rename, then there's
|
removal, and there are no symbols to rename, then there's
|
nothing else to do. */
|
nothing else to do. */
|
if (sbitmap_first_set_bit (new_ssa_names) < 0
|
if (sbitmap_first_set_bit (new_ssa_names) < 0
|
&& bitmap_empty_p (syms_to_rename))
|
&& bitmap_empty_p (syms_to_rename))
|
goto done;
|
goto done;
|
}
|
}
|
|
|
/* Next, determine the block at which to start the renaming process. */
|
/* Next, determine the block at which to start the renaming process. */
|
if (!bitmap_empty_p (syms_to_rename))
|
if (!bitmap_empty_p (syms_to_rename))
|
{
|
{
|
/* If we have to rename some symbols from scratch, we need to
|
/* If we have to rename some symbols from scratch, we need to
|
start the process at the root of the CFG. FIXME, it should
|
start the process at the root of the CFG. FIXME, it should
|
be possible to determine the nearest block that had a
|
be possible to determine the nearest block that had a
|
definition for each of the symbols that are marked for
|
definition for each of the symbols that are marked for
|
updating. For now this seems more work than it's worth. */
|
updating. For now this seems more work than it's worth. */
|
start_bb = ENTRY_BLOCK_PTR;
|
start_bb = ENTRY_BLOCK_PTR;
|
|
|
/* Traverse the CFG looking for definitions and uses of symbols
|
/* Traverse the CFG looking for definitions and uses of symbols
|
in SYMS_TO_RENAME. Mark interesting blocks and statements
|
in SYMS_TO_RENAME. Mark interesting blocks and statements
|
and set local live-in information for the PHI placement
|
and set local live-in information for the PHI placement
|
heuristics. */
|
heuristics. */
|
prepare_block_for_update (start_bb, insert_phi_p);
|
prepare_block_for_update (start_bb, insert_phi_p);
|
}
|
}
|
else
|
else
|
{
|
{
|
/* Otherwise, the entry block to the region is the nearest
|
/* Otherwise, the entry block to the region is the nearest
|
common dominator for the blocks in BLOCKS. */
|
common dominator for the blocks in BLOCKS. */
|
start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
|
start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
|
blocks_to_update);
|
blocks_to_update);
|
}
|
}
|
|
|
/* If requested, insert PHI nodes at the iterated dominance frontier
|
/* If requested, insert PHI nodes at the iterated dominance frontier
|
of every block, creating new definitions for names in OLD_SSA_NAMES
|
of every block, creating new definitions for names in OLD_SSA_NAMES
|
and for symbols in SYMS_TO_RENAME. */
|
and for symbols in SYMS_TO_RENAME. */
|
if (insert_phi_p)
|
if (insert_phi_p)
|
{
|
{
|
bitmap *dfs;
|
bitmap *dfs;
|
|
|
/* If the caller requested PHI nodes to be added, compute
|
/* If the caller requested PHI nodes to be added, compute
|
dominance frontiers. */
|
dominance frontiers. */
|
dfs = XNEWVEC (bitmap, last_basic_block);
|
dfs = XNEWVEC (bitmap, last_basic_block);
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
dfs[bb->index] = BITMAP_ALLOC (NULL);
|
dfs[bb->index] = BITMAP_ALLOC (NULL);
|
compute_dominance_frontiers (dfs);
|
compute_dominance_frontiers (dfs);
|
|
|
if (sbitmap_first_set_bit (old_ssa_names) >= 0)
|
if (sbitmap_first_set_bit (old_ssa_names) >= 0)
|
{
|
{
|
sbitmap_iterator sbi;
|
sbitmap_iterator sbi;
|
|
|
/* insert_update_phi_nodes_for will call add_new_name_mapping
|
/* insert_update_phi_nodes_for will call add_new_name_mapping
|
when inserting new PHI nodes, so the set OLD_SSA_NAMES
|
when inserting new PHI nodes, so the set OLD_SSA_NAMES
|
will grow while we are traversing it (but it will not
|
will grow while we are traversing it (but it will not
|
gain any new members). Copy OLD_SSA_NAMES to a temporary
|
gain any new members). Copy OLD_SSA_NAMES to a temporary
|
for traversal. */
|
for traversal. */
|
sbitmap tmp = sbitmap_alloc (old_ssa_names->n_bits);
|
sbitmap tmp = sbitmap_alloc (old_ssa_names->n_bits);
|
sbitmap_copy (tmp, old_ssa_names);
|
sbitmap_copy (tmp, old_ssa_names);
|
EXECUTE_IF_SET_IN_SBITMAP (tmp, 0, i, sbi)
|
EXECUTE_IF_SET_IN_SBITMAP (tmp, 0, i, sbi)
|
insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
|
insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
|
update_flags);
|
update_flags);
|
sbitmap_free (tmp);
|
sbitmap_free (tmp);
|
}
|
}
|
|
|
EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
|
insert_updated_phi_nodes_for (referenced_var (i), dfs,
|
insert_updated_phi_nodes_for (referenced_var (i), dfs,
|
blocks_to_update, update_flags);
|
blocks_to_update, update_flags);
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
BITMAP_FREE (dfs[bb->index]);
|
BITMAP_FREE (dfs[bb->index]);
|
free (dfs);
|
free (dfs);
|
|
|
/* Insertion of PHI nodes may have added blocks to the region.
|
/* Insertion of PHI nodes may have added blocks to the region.
|
We need to re-compute START_BB to include the newly added
|
We need to re-compute START_BB to include the newly added
|
blocks. */
|
blocks. */
|
if (start_bb != ENTRY_BLOCK_PTR)
|
if (start_bb != ENTRY_BLOCK_PTR)
|
start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
|
start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
|
blocks_to_update);
|
blocks_to_update);
|
}
|
}
|
|
|
/* Reset the current definition for name and symbol before renaming
|
/* Reset the current definition for name and symbol before renaming
|
the sub-graph. */
|
the sub-graph. */
|
EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
|
EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
|
set_current_def (ssa_name (i), NULL_TREE);
|
set_current_def (ssa_name (i), NULL_TREE);
|
|
|
EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
|
set_current_def (referenced_var (i), NULL_TREE);
|
set_current_def (referenced_var (i), NULL_TREE);
|
|
|
/* Now start the renaming process at START_BB. */
|
/* Now start the renaming process at START_BB. */
|
tmp = sbitmap_alloc (last_basic_block);
|
tmp = sbitmap_alloc (last_basic_block);
|
sbitmap_zero (tmp);
|
sbitmap_zero (tmp);
|
EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
|
SET_BIT (tmp, i);
|
SET_BIT (tmp, i);
|
|
|
rewrite_blocks (start_bb, REWRITE_UPDATE, tmp);
|
rewrite_blocks (start_bb, REWRITE_UPDATE, tmp);
|
|
|
sbitmap_free (tmp);
|
sbitmap_free (tmp);
|
|
|
/* Debugging dumps. */
|
/* Debugging dumps. */
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
int c;
|
int c;
|
unsigned i;
|
unsigned i;
|
|
|
dump_update_ssa (dump_file);
|
dump_update_ssa (dump_file);
|
|
|
fprintf (dump_file, "Incremental SSA update started at block: %d\n\n",
|
fprintf (dump_file, "Incremental SSA update started at block: %d\n\n",
|
start_bb->index);
|
start_bb->index);
|
|
|
c = 0;
|
c = 0;
|
EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
|
c++;
|
c++;
|
fprintf (dump_file, "Number of blocks in CFG: %d\n", last_basic_block);
|
fprintf (dump_file, "Number of blocks in CFG: %d\n", last_basic_block);
|
fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n\n",
|
fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n\n",
|
c, PERCENT (c, last_basic_block));
|
c, PERCENT (c, last_basic_block));
|
|
|
if (dump_flags & TDF_DETAILS)
|
if (dump_flags & TDF_DETAILS)
|
{
|
{
|
fprintf (dump_file, "Affected blocks: ");
|
fprintf (dump_file, "Affected blocks: ");
|
EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
|
fprintf (dump_file, "%u ", i);
|
fprintf (dump_file, "%u ", i);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
fprintf (dump_file, "\n\n");
|
fprintf (dump_file, "\n\n");
|
}
|
}
|
|
|
/* Free allocated memory. */
|
/* Free allocated memory. */
|
done:
|
done:
|
EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
|
{
|
{
|
tree_vec phis = VEC_index (tree_vec, phis_to_rewrite, i);
|
tree_vec phis = VEC_index (tree_vec, phis_to_rewrite, i);
|
|
|
VEC_free (tree, heap, phis);
|
VEC_free (tree, heap, phis);
|
VEC_replace (tree_vec, phis_to_rewrite, i, NULL);
|
VEC_replace (tree_vec, phis_to_rewrite, i, NULL);
|
}
|
}
|
BITMAP_FREE (blocks_with_phis_to_rewrite);
|
BITMAP_FREE (blocks_with_phis_to_rewrite);
|
BITMAP_FREE (blocks_to_update);
|
BITMAP_FREE (blocks_to_update);
|
delete_update_ssa ();
|
delete_update_ssa ();
|
|
|
timevar_pop (TV_TREE_SSA_INCREMENTAL);
|
timevar_pop (TV_TREE_SSA_INCREMENTAL);
|
}
|
}
|
|
|
